Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
plug a bunch of memleaks
[simgrid.git] / src / surf / surf_routing_rulebased.c
1 /* Copyright (c) 2009, 2010, 2011. The SimGrid Team.
2  * All rights reserved.                                                     */
3
4 /* This program is free software; you can redistribute it and/or modify it
5  * under the terms of the license (GNU LGPL) which comes with this package. */
6 #include "surf_routing_private.h"
7 #include <pcre.h>               /* regular expression library */
8
9 /* Global vars */
10 extern routing_global_t global_routing;
11 extern xbt_dynar_t parsed_link_list;
12
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_rulebased, surf, "Routing part of surf");
14
15 /* Routing model structure */
16
17 typedef struct {
18   s_as_t generic_routing;
19   xbt_dict_t dict_processing_units;
20   xbt_dict_t dict_autonomous_systems;
21   xbt_dynar_t list_route;
22   xbt_dynar_t list_ASroute;
23 } s_AS_rulebased_t, *AS_rulebased_t;
24
25 typedef struct s_rule_route s_rule_route_t, *rule_route_t;
26 typedef struct s_rule_route_extended s_rule_route_extended_t,
27     *rule_route_extended_t;
28
29 struct s_rule_route {
30   xbt_dynar_t re_str_link;      // dynar of char*
31   pcre *re_src;
32   pcre *re_dst;
33 };
34
35 struct s_rule_route_extended {
36   s_rule_route_t generic_rule_route;
37   char *re_src_gateway;
38   char *re_dst_gateway;
39 };
40
41 static void rule_route_free(void *e)
42 {
43   rule_route_t *elem = (rule_route_t *) (e);
44   if (*elem) {
45     xbt_dynar_free(&(*elem)->re_str_link);
46     pcre_free((*elem)->re_src);
47     pcre_free((*elem)->re_dst);
48     xbt_free(*elem);
49   }
50   *elem = NULL;
51 }
52
53 static void rule_route_extended_free(void *e)
54 {
55   rule_route_extended_t *elem = (rule_route_extended_t *) e;
56   if (*elem) {
57     xbt_dynar_free(&(*elem)->generic_rule_route.re_str_link);
58     pcre_free((*elem)->generic_rule_route.re_src);
59     pcre_free((*elem)->generic_rule_route.re_dst);
60     xbt_free((*elem)->re_src_gateway);
61     xbt_free((*elem)->re_dst_gateway);
62     xbt_free(*elem);
63   }
64 }
65
66 /* Parse routing model functions */
67
68 static void model_rulebased_parse_PU(AS_t rc, const char *name)
69 {
70   AS_rulebased_t routing = (AS_rulebased_t) rc;
71   xbt_dict_set(routing->dict_processing_units, name, (void *) (-1), NULL);
72 }
73
74 static void model_rulebased_parse_AS(AS_t rc, const char *name)
75 {
76   AS_rulebased_t routing = (AS_rulebased_t) rc;
77   xbt_dict_set(routing->dict_autonomous_systems, name, (void *) (-1),
78                NULL);
79 }
80
81 static void model_rulebased_parse_route(AS_t rc,
82                                       const char *src, const char *dst,
83                                       route_t route)
84 {
85   AS_rulebased_t routing = (AS_rulebased_t) rc;
86   rule_route_t ruleroute = xbt_new0(s_rule_route_t, 1);
87   const char *error;
88   int erroffset;
89
90   if(!strcmp(rc->model_desc->name,"Vivaldi")){
91           if(!xbt_dynar_is_empty(route->link_list))
92                   xbt_die("You can't have link_ctn with Model Vivaldi.");
93   }
94
95   ruleroute->re_src = pcre_compile(src, 0, &error, &erroffset, NULL);
96   xbt_assert(ruleroute->re_src,
97               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
98               erroffset, src, error);
99   ruleroute->re_dst = pcre_compile(dst, 0, &error, &erroffset, NULL);
100   xbt_assert(ruleroute->re_src,
101               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
102               erroffset, dst, error);
103
104   ruleroute->re_str_link = route->link_list;
105   route->link_list = NULL; // Don't free it twice in each container
106
107   xbt_dynar_push(routing->list_route, &ruleroute);
108 }
109
110 static void model_rulebased_parse_ASroute(AS_t rc,
111                                         const char *src, const char *dst,
112                                         route_t route)
113 {
114   AS_rulebased_t routing = (AS_rulebased_t) rc;
115   rule_route_extended_t ruleroute_e = xbt_new0(s_rule_route_extended_t, 1);
116   const char *error;
117   int erroffset;
118
119   if(!strcmp(rc->model_desc->name,"Vivaldi")){
120           if(!xbt_dynar_is_empty(route->link_list))
121                   xbt_die("You can't have link_ctn with Model Vivaldi.");
122   }
123
124   ruleroute_e->generic_rule_route.re_src =
125       pcre_compile(src, 0, &error, &erroffset, NULL);
126   xbt_assert(ruleroute_e->generic_rule_route.re_src,
127               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
128               erroffset, src, error);
129   ruleroute_e->generic_rule_route.re_dst =
130       pcre_compile(dst, 0, &error, &erroffset, NULL);
131   xbt_assert(ruleroute_e->generic_rule_route.re_src,
132               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
133               erroffset, dst, error);
134   ruleroute_e->generic_rule_route.re_str_link =
135       route->link_list;
136   ruleroute_e->re_src_gateway = route->src_gateway;
137   ruleroute_e->re_dst_gateway = route->dst_gateway;
138   xbt_dynar_push(routing->list_ASroute, &ruleroute_e);
139
140   /* make sure that they don't get freed */
141   route->link_list = NULL;
142   route->src_gateway = route->dst_gateway = NULL;
143 }
144
145 static void model_rulebased_parse_bypassroute(AS_t rc,
146                                             const char *src,
147                                             const char *dst,
148                                             route_t e_route)
149 {
150   xbt_die("bypass routing not supported for Route-Based model");
151 }
152
153 #define BUFFER_SIZE 4096        /* result buffer size */
154 #define OVECCOUNT 30            /* should be a multiple of 3 */
155
156 static char *remplace(char *value, const char **src_list, int src_size,
157                       const char **dst_list, int dst_size)
158 {
159   char result[BUFFER_SIZE];
160   int i_res = 0;
161   int i = 0;
162
163   while (value[i]) {
164     if (value[i] == '$') {
165       i++;                      /* skip the '$' */
166       if (value[i] < '0' || value[i] > '9')
167         xbt_die("bad string parameter, no number indication, at offset: "
168                 "%d (\"%s\")", i, value);
169
170       /* solve the number */
171       int number = value[i++] - '0';
172       while (value[i] >= '0' && value[i] <= '9')
173         number = 10 * number + (value[i++] - '0');
174
175       /* solve the indication */
176       const char **param_list;
177       _XBT_GNUC_UNUSED int param_size;
178       if (value[i] == 's' && value[i + 1] == 'r' && value[i + 2] == 'c') {
179         param_list = src_list;
180         param_size = src_size;
181       } else if (value[i] == 'd' && value[i + 1] == 's'
182                  && value[i + 2] == 't') {
183         param_list = dst_list;
184         param_size = dst_size;
185       } else {
186         xbt_die("bad string parameter, support only \"src\" and \"dst\", "
187                 "at offset: %d (\"%s\")", i, value);
188       }
189       i += 3;
190
191       xbt_assert(number < param_size,
192                  "bad string parameter, not enough length param_size, "
193                  "at offset: %d (\"%s\") %d %d", i, value, param_size, number);
194
195       const char *param = param_list[number];
196       int j = 0;
197       while (param[j] && i_res < BUFFER_SIZE)
198         result[i_res++] = param[j++];
199     } else {
200       result[i_res++] = value[i++]; /* next char */
201     }
202     if (i_res >= BUFFER_SIZE)
203       xbt_die("solving string \"%s\", small buffer size (%d)",
204               value, BUFFER_SIZE);
205   }
206   result[i_res++] = '\0';
207   char *res = xbt_malloc(i_res);
208   return memcpy(res, result, i_res);
209 }
210
211 static void rulebased_get_route_and_latency(AS_t rc,
212                                 const char *src, const char *dst,
213                                 route_t res,double*lat);
214 static xbt_dynar_t rulebased_get_onelink_routes(AS_t rc)
215 {
216   xbt_dynar_t ret = xbt_dynar_new (sizeof(onelink_t), xbt_free);
217
218   //We have already bypass cluster routes with network NS3
219   if(!strcmp(surf_network_model->name,"network NS3"))
220         return ret;
221
222   AS_rulebased_t routing = (AS_rulebased_t)rc;
223
224   xbt_dict_cursor_t c1 = NULL;
225   char *k1, *d1;
226
227   //find router
228   char *router = NULL;
229   xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
230     if (routing_get_network_element_type(k1) == SURF_NETWORK_ELEMENT_ROUTER){
231       router = k1;
232       break;
233     }
234   }
235
236   if (!router)
237     xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
238
239   xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
240     route_t route = xbt_new0(s_route_t,1);
241     route->link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
242     rulebased_get_route_and_latency (rc, router, k1, route,NULL);
243
244     int number_of_links = xbt_dynar_length(route->link_list);
245
246     if(number_of_links == 1) {
247                 //loopback
248     }
249     else{
250                 if (number_of_links != 2) {
251                   xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
252                 }
253
254                 void *link_ptr;
255                 xbt_dynar_get_cpy (route->link_list, 1, &link_ptr);
256                 onelink_t onelink = xbt_new0 (s_onelink_t, 1);
257                 onelink->src = xbt_strdup (k1);
258                 onelink->dst = xbt_strdup (router);
259                 onelink->link_ptr = link_ptr;
260                 xbt_dynar_push (ret, &onelink);
261     }
262   }
263   return ret;
264 }
265
266 /* Business methods */
267 static void rulebased_get_route_and_latency(AS_t rc,
268                                 const char *src, const char *dst,
269                                 route_t route, double *lat)
270 {
271   xbt_assert(rc && src
272               && dst,
273               "Invalid params for \"get_route\" function at AS \"%s\"",
274               rc->name);
275
276   /* set utils vars */
277   AS_rulebased_t routing = (AS_rulebased_t) rc;
278
279   int are_processing_units=0;
280   xbt_dynar_t rule_list;
281   if (xbt_dict_get_or_null(routing->dict_processing_units, src)
282       && xbt_dict_get_or_null(routing->dict_processing_units, dst)) {
283     are_processing_units = 1;
284     rule_list = routing->list_route;
285   } else if (xbt_dict_get_or_null(routing->dict_autonomous_systems, src)
286              && xbt_dict_get_or_null(routing->dict_autonomous_systems,
287                                      dst)) {
288     are_processing_units = 0;
289     rule_list = routing->list_ASroute;
290   } else
291     THROWF(arg_error,0,"No route from '%s' to '%s'",src,dst);
292
293   int rc_src = -1;
294   int rc_dst = -1;
295   int src_length = (int) strlen(src);
296   int dst_length = (int) strlen(dst);
297
298   rule_route_t ruleroute;
299   unsigned int cpt;
300   int ovector_src[OVECCOUNT];
301   int ovector_dst[OVECCOUNT];
302   const char **list_src = NULL;
303   const char **list_dst = NULL;
304   _XBT_GNUC_UNUSED int res;
305   xbt_dynar_foreach(rule_list, cpt, ruleroute) {
306     rc_src =
307         pcre_exec(ruleroute->re_src, NULL, src, src_length, 0, 0,
308                   ovector_src, OVECCOUNT);
309     if (rc_src >= 0) {
310       rc_dst =
311           pcre_exec(ruleroute->re_dst, NULL, dst, dst_length, 0, 0,
312                     ovector_dst, OVECCOUNT);
313       if (rc_dst >= 0) {
314         res = pcre_get_substring_list(src, ovector_src, rc_src, &list_src);
315         xbt_assert(!res, "error solving substring list for src \"%s\"", src);
316         res = pcre_get_substring_list(dst, ovector_dst, rc_dst, &list_dst);
317         xbt_assert(!res, "error solving substring list for src \"%s\"", dst);
318         char *link_name;
319         xbt_dynar_foreach(ruleroute->re_str_link, cpt, link_name) {
320           char *new_link_name =
321               remplace(link_name, list_src, rc_src, list_dst, rc_dst);
322           void *link =
323                           xbt_lib_get_or_null(link_lib, new_link_name, SURF_LINK_LEVEL);
324           if (link) {
325             xbt_dynar_push(route->link_list, &link);
326             if (lat)
327               *lat += surf_network_model->extension.network.get_link_latency(link);
328           } else
329             THROWF(mismatch_error, 0, "Link %s not found", new_link_name);
330           xbt_free(new_link_name);
331         }
332       }
333     }
334     if (rc_src >= 0 && rc_dst >= 0)
335       break;
336   }
337
338   if (rc_src >= 0 && rc_dst >= 0) {
339     /* matched src and dest, nothing more to do (?) */
340   } else if (!strcmp(src, dst) && are_processing_units) {
341     xbt_dynar_push(route->link_list, &(global_routing->loopback));
342     if (lat)
343       *lat += surf_network_model->extension.network.get_link_latency(link);
344   } else {
345     THROWF(arg_error,0,"No route from '%s' to '%s'??",src,dst);
346     //xbt_dynar_reset(route->link_list);
347   }
348
349   if (!are_processing_units && !xbt_dynar_is_empty(route->link_list)) {
350     rule_route_extended_t ruleroute_extended =
351         (rule_route_extended_t) ruleroute;
352     route->src_gateway =
353         remplace(ruleroute_extended->re_src_gateway, list_src, rc_src,
354                  list_dst, rc_dst);
355     route->dst_gateway =
356         remplace(ruleroute_extended->re_dst_gateway, list_src, rc_src,
357                  list_dst, rc_dst);
358   }
359
360   if (list_src)
361     pcre_free_substring_list(list_src);
362   if (list_dst)
363     pcre_free_substring_list(list_dst);
364 }
365
366 static route_t rulebased_get_bypass_route(AS_t rc, const char *src, const char *dst) {
367   return NULL;
368 }
369
370 static void rulebased_finalize(AS_t rc)
371 {
372   AS_rulebased_t routing =
373       (AS_rulebased_t) rc;
374   if (routing) {
375     xbt_dict_free(&routing->dict_processing_units);
376     xbt_dict_free(&routing->dict_autonomous_systems);
377     xbt_dynar_free(&routing->list_route);
378     xbt_dynar_free(&routing->list_ASroute);
379
380     model_generic_finalize(rc);
381   }
382 }
383
384 /* Creation routing model functions */
385 AS_t model_rulebased_create(void) {
386
387   AS_rulebased_t new_component = (AS_rulebased_t)
388       model_generic_create_sized(sizeof(s_AS_rulebased_t));
389
390   new_component->generic_routing.parse_PU = model_rulebased_parse_PU;
391   new_component->generic_routing.parse_AS = model_rulebased_parse_AS;
392   new_component->generic_routing.parse_route = model_rulebased_parse_route;
393   new_component->generic_routing.parse_ASroute = model_rulebased_parse_ASroute;
394   new_component->generic_routing.parse_bypassroute = model_rulebased_parse_bypassroute;
395   new_component->generic_routing.get_onelink_routes = rulebased_get_onelink_routes;
396   new_component->generic_routing.get_route_and_latency = rulebased_get_route_and_latency;
397   new_component->generic_routing.get_bypass_route = rulebased_get_bypass_route;
398   new_component->generic_routing.finalize = rulebased_finalize;
399   /* initialization of internal structures */
400   new_component->dict_processing_units = xbt_dict_new();
401   new_component->dict_autonomous_systems = xbt_dict_new();
402   new_component->list_route = xbt_dynar_new(sizeof(rule_route_t), &rule_route_free);
403   new_component->list_ASroute =
404       xbt_dynar_new(sizeof(rule_route_extended_t),
405                     &rule_route_extended_free);
406
407   return (AS_t) new_component;
408 }