Logo AND Algorithmique Numérique Distribuée

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