Logo AND Algorithmique Numérique Distribuée

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