Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Add a variable to see if having set a bypass route or not.
[simgrid.git] / src / surf / surf_routing_generic.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
7 #include <pcre.h>               /* regular expression library */
8
9 #include "simgrid/platf_interface.h"    // platform creation API internal interface
10
11 #include "surf_routing_private.h"
12 #include "surf/surf_routing.h"
13 #include "surf/surfxml_parse_values.h"
14
15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_routing_generic, surf_route, "Generic implementation of the surf routing");
16
17 static int having_set_bypassroute = 0;
18
19 AS_t model_generic_create_sized(size_t childsize) {
20   AS_t new_component = model_none_create_sized(childsize);
21
22   new_component->parse_PU = generic_parse_PU;
23   new_component->parse_AS = generic_parse_AS;
24   new_component->parse_route = NULL;
25   new_component->parse_ASroute = NULL;
26   new_component->parse_bypassroute = generic_parse_bypassroute;
27   new_component->get_route_and_latency = NULL;
28   new_component->get_onelink_routes = NULL;
29   new_component->get_bypass_route =
30       generic_get_bypassroute;
31   new_component->finalize = model_generic_finalize;
32
33   new_component->to_index = xbt_dict_new_homogeneous(xbt_free);
34   new_component->bypassRoutes = xbt_dict_new_homogeneous((void (*)(void *)) generic_free_route);
35
36   return new_component;
37 }
38 void model_generic_finalize(AS_t as) {
39   xbt_dict_free(&as->to_index);
40   xbt_dict_free(&as->bypassRoutes);
41   model_none_finalize(as);
42 }
43
44 void generic_parse_PU(AS_t as, const char *name)
45 {
46   XBT_DEBUG("Load process unit \"%s\"", name);
47   int *id = xbt_new0(int, 1);
48   xbt_dict_t _to_index;
49   _to_index = as->to_index;
50   *id = xbt_dict_length(_to_index);
51   xbt_dict_set(_to_index, name, id, NULL);
52 }
53
54 void generic_parse_AS(AS_t as, const char *name)
55 {
56   XBT_DEBUG("Load Autonomous system \"%s\"", name);
57   int *id = xbt_new0(int, 1);
58   xbt_dict_t _to_index;
59   _to_index = as->to_index;
60   *id = xbt_dict_length(_to_index);
61   xbt_dict_set(_to_index, name, id, NULL);
62 }
63
64 void generic_parse_bypassroute(AS_t rc,
65                              const char *src, const char *dst,
66                              route_t e_route)
67 {
68   XBT_DEBUG("Load bypassRoute from \"%s\" to \"%s\"", src, dst);
69   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
70   char *route_name;
71
72   route_name = bprintf("%s#%s", src, dst);
73   xbt_assert(!xbt_dynar_is_empty(e_route->link_list),
74              "Invalid count of links, must be greater than zero (%s,%s)",
75              src, dst);
76   xbt_assert(!xbt_dict_get_or_null(dict_bypassRoutes, route_name),
77              "The bypass route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exists",
78              src, e_route->src_gateway, dst, e_route->dst_gateway);
79
80   route_t new_e_route =
81       generic_new_extended_route(SURF_ROUTING_RECURSIVE, e_route, 0);
82   xbt_dynar_free(&(e_route->link_list));
83   xbt_free(e_route);
84
85   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route, NULL);
86   having_set_bypassroute = 1;
87   xbt_free(route_name);
88 }
89
90 /* ************************************************************************** */
91 /* *********************** GENERIC BUSINESS METHODS ************************* */
92
93 xbt_dynar_t generic_get_onelink_routes(AS_t rc) { // FIXME: kill that stub
94   xbt_die("\"generic_get_onelink_routes\" not implemented yet");
95   return NULL;
96 }
97
98 route_t generic_get_bypassroute(AS_t rc, const char *src, const char *dst)
99 {
100   // If never set a bypass route return NULL
101   if(!having_set_bypassroute)
102     return NULL;
103
104   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
105   AS_t src_as, dst_as;
106   int index_src, index_dst;
107   xbt_dynar_t path_src = NULL;
108   xbt_dynar_t path_dst = NULL;
109   AS_t current = NULL;
110   AS_t *current_src = NULL;
111   AS_t *current_dst = NULL;
112
113   /* (1) find the as where the src and dst are located */
114   void *src_data = xbt_lib_get_or_null(host_lib, src, ROUTING_HOST_LEVEL);
115   void *dst_data = xbt_lib_get_or_null(host_lib, dst, ROUTING_HOST_LEVEL);
116   if (!src_data)
117     src_data = xbt_lib_get_or_null(as_router_lib, src, ROUTING_ASR_LEVEL);
118   if (!dst_data)
119     dst_data = xbt_lib_get_or_null(as_router_lib, dst, ROUTING_ASR_LEVEL);
120
121   if (src_data == NULL || dst_data == NULL)
122     xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
123             src, dst, rc->name);
124
125   src_as = ((network_element_info_t) src_data)->rc_component;
126   dst_as = ((network_element_info_t) dst_data)->rc_component;
127
128   /* (2) find the path to the root routing component */
129   path_src = xbt_dynar_new(sizeof(AS_t), NULL);
130   current = src_as;
131   while (current != NULL) {
132     xbt_dynar_push(path_src, &current);
133     current = current->routing_father;
134   }
135   path_dst = xbt_dynar_new(sizeof(AS_t), NULL);
136   current = dst_as;
137   while (current != NULL) {
138     xbt_dynar_push(path_dst, &current);
139     current = current->routing_father;
140   }
141
142   /* (3) find the common father */
143   index_src = path_src->used - 1;
144   index_dst = path_dst->used - 1;
145   current_src = xbt_dynar_get_ptr(path_src, index_src);
146   current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
147   while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
148     xbt_dynar_pop_ptr(path_src);
149     xbt_dynar_pop_ptr(path_dst);
150     index_src--;
151     index_dst--;
152     current_src = xbt_dynar_get_ptr(path_src, index_src);
153     current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
154   }
155
156   int max_index_src = path_src->used - 1;
157   int max_index_dst = path_dst->used - 1;
158
159   int max_index = max(max_index_src, max_index_dst);
160   int i, max;
161
162   route_t e_route_bypass = NULL;
163
164   for (max = 0; max <= max_index; max++) {
165     for (i = 0; i < max; i++) {
166       if (i <= max_index_src && max <= max_index_dst) {
167         char *route_name = bprintf("%s#%s",
168                                    (*(AS_t *)
169                                     (xbt_dynar_get_ptr(path_src, i)))->name,
170                                    (*(AS_t *)
171                                     (xbt_dynar_get_ptr(path_dst, max)))->name);
172         e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
173         xbt_free(route_name);
174       }
175       if (e_route_bypass)
176         break;
177       if (max <= max_index_src && i <= max_index_dst) {
178         char *route_name = bprintf("%s#%s",
179                                    (*(AS_t *)
180                                     (xbt_dynar_get_ptr(path_src, max)))->name,
181                                    (*(AS_t *)
182                                     (xbt_dynar_get_ptr(path_dst, i)))->name);
183         e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
184         xbt_free(route_name);
185       }
186       if (e_route_bypass)
187         break;
188     }
189
190     if (e_route_bypass)
191       break;
192
193     if (max <= max_index_src && max <= max_index_dst) {
194       char *route_name = bprintf("%s#%s",
195                                  (*(AS_t *)
196                                   (xbt_dynar_get_ptr(path_src, max)))->name,
197                                  (*(AS_t *)
198                                   (xbt_dynar_get_ptr(path_dst, max)))->name);
199       e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
200       xbt_free(route_name);
201     }
202     if (e_route_bypass)
203       break;
204   }
205
206   xbt_dynar_free(&path_src);
207   xbt_dynar_free(&path_dst);
208
209   route_t new_e_route = NULL;
210
211   if (e_route_bypass) {
212     void *link;
213     unsigned int cpt = 0;
214     new_e_route = xbt_new0(s_route_t, 1);
215     new_e_route->src_gateway = xbt_strdup(e_route_bypass->src_gateway);
216     new_e_route->dst_gateway = xbt_strdup(e_route_bypass->dst_gateway);
217     new_e_route->link_list =
218         xbt_dynar_new(global_routing->size_of_link, NULL);
219     xbt_dynar_foreach(e_route_bypass->link_list, cpt, link) {
220       xbt_dynar_push(new_e_route->link_list, &link);
221     }
222   }
223
224   return new_e_route;
225 }
226
227 /* ************************************************************************** */
228 /* ************************* GENERIC AUX FUNCTIONS ************************** */
229
230 route_t
231 generic_new_route(e_surf_routing_hierarchy_t hierarchy, void *data, int order)
232 {
233
234   char *link_name;
235   route_t new_route;
236   unsigned int cpt;
237   xbt_dynar_t links = NULL, links_id = NULL;
238
239   new_route = xbt_new0(s_route_t, 1);
240   new_route->link_list = xbt_dynar_new(global_routing->size_of_link, NULL);
241
242   xbt_assert(hierarchy == SURF_ROUTING_BASE,
243              "the hierarchy type is not SURF_ROUTING_BASE");
244
245   links = ((route_t) data)->link_list;
246
247
248   links_id = new_route->link_list;
249
250   xbt_dynar_foreach(links, cpt, link_name) {
251
252     void *link = xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
253     if (link) {
254       if (order)
255         xbt_dynar_push(links_id, &link);
256       else
257         xbt_dynar_unshift(links_id, &link);
258     } else
259       THROWF(mismatch_error, 0, "Link %s not found", link_name);
260   }
261
262   return new_route;
263 }
264
265 route_t
266 generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy,
267                            void *data, int order)
268 {
269
270   char *link_name;
271   route_t e_route, new_e_route;
272   route_t route;
273   unsigned int cpt;
274   xbt_dynar_t links = NULL, links_id = NULL;
275
276   new_e_route = xbt_new0(s_route_t, 1);
277   new_e_route->link_list = xbt_dynar_new(global_routing->size_of_link, NULL);
278
279   xbt_assert(hierarchy == SURF_ROUTING_BASE
280              || hierarchy == SURF_ROUTING_RECURSIVE,
281              "the hierarchy type is not defined");
282
283   if (hierarchy == SURF_ROUTING_BASE) {
284
285     route = (route_t) data;
286     links = route->link_list;
287
288   } else if (hierarchy == SURF_ROUTING_RECURSIVE) {
289
290     e_route = (route_t) data;
291     xbt_assert(e_route->src_gateway
292                && e_route->dst_gateway, "bad gateway, is null");
293     links = e_route->link_list;
294
295     /* remeber not erase the gateway names */
296     new_e_route->src_gateway = strdup(e_route->src_gateway);
297     new_e_route->dst_gateway = strdup(e_route->dst_gateway);
298   }
299
300   links_id = new_e_route->link_list;
301
302   xbt_dynar_foreach(links, cpt, link_name) {
303
304     void *link = xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
305     if (link) {
306       if (order)
307         xbt_dynar_push(links_id, &link);
308       else
309         xbt_dynar_unshift(links_id, &link);
310     } else
311       THROWF(mismatch_error, 0, "Link %s not found", link_name);
312   }
313
314   return new_e_route;
315 }
316
317 void generic_free_route(route_t route)
318 {
319   if (route) {
320     xbt_dynar_free(&route->link_list);
321     xbt_free(route->src_gateway);
322     xbt_free(route->dst_gateway);
323     xbt_free(route);
324   }
325 }
326
327 static AS_t generic_as_exist(AS_t find_from,
328                                             AS_t to_find)
329 {
330   //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
331   xbt_dict_cursor_t cursor = NULL;
332   char *key;
333   int found = 0;
334   AS_t elem;
335   xbt_dict_foreach(find_from->routing_sons, cursor, key, elem) {
336     if (to_find == elem || generic_as_exist(elem, to_find)) {
337       found = 1;
338       break;
339     }
340   }
341   if (found)
342     return to_find;
343   return NULL;
344 }
345
346 AS_t
347 generic_autonomous_system_exist(AS_t rc, char *element)
348 {
349   //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
350   AS_t element_as, result, elem;
351   xbt_dict_cursor_t cursor = NULL;
352   char *key;
353   element_as = ((network_element_info_t)
354                 xbt_lib_get_or_null(as_router_lib, element,
355                                     ROUTING_ASR_LEVEL))->rc_component;
356   result = ((AS_t) - 1);
357   if (element_as != rc)
358     result = generic_as_exist(rc, element_as);
359
360   int found = 0;
361   if (result) {
362     xbt_dict_foreach(element_as->routing_sons, cursor, key, elem) {
363       found = !strcmp(elem->name, element);
364       if (found)
365         break;
366     }
367     if (found)
368       return element_as;
369   }
370   return NULL;
371 }
372
373 AS_t
374 generic_processing_units_exist(AS_t rc, char *element)
375 {
376   AS_t element_as;
377   element_as = ((network_element_info_t)
378                 xbt_lib_get_or_null(host_lib,
379                                     element, ROUTING_HOST_LEVEL))->rc_component;
380   if (element_as == rc)
381     return element_as;
382   return generic_as_exist(rc, element_as);
383 }
384
385 void generic_src_dst_check(AS_t rc, const char *src,
386                            const char *dst)
387 {
388
389   void *src_data = xbt_lib_get_or_null(host_lib, src, ROUTING_HOST_LEVEL);
390   void *dst_data = xbt_lib_get_or_null(host_lib, dst, ROUTING_HOST_LEVEL);
391   if (!src_data)
392     src_data = xbt_lib_get_or_null(as_router_lib, src, ROUTING_ASR_LEVEL);
393   if (!dst_data)
394     dst_data = xbt_lib_get_or_null(as_router_lib, dst, ROUTING_ASR_LEVEL);
395
396   if (src_data == NULL || dst_data == NULL)
397     xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
398             src, dst, rc->name);
399
400   AS_t src_as =
401       ((network_element_info_t) src_data)->rc_component;
402   AS_t dst_as =
403       ((network_element_info_t) dst_data)->rc_component;
404
405   if (src_as != dst_as)
406     xbt_die("The src(%s in %s) and dst(%s in %s) are in differents AS",
407             src, src_as->name, dst, dst_as->name);
408   if (rc != dst_as)
409     xbt_die
410         ("The routing component of src'%s' and dst'%s' is not the same as the network elements belong (%s?=%s?=%s)",
411          src, dst, src_as->name, dst_as->name, rc->name);
412 }