Logo AND Algorithmique Numérique Distribuée

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