Logo AND Algorithmique Numérique Distribuée

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