Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
908e46ecb8f97c315b0b1dc5f2fd5b7931dac0ed
[simgrid.git] / src / surf / surf_routing_generic.cpp
1 /* Copyright (c) 2009-2014. 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 "simgrid/platf_interface.h"    // platform creation API internal interface
8
9 #include "surf_routing_generic.hpp"
10 #include "network_interface.hpp"
11 #include "xbt/graph.h"
12
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_routing_generic, surf_route, "Generic implementation of the surf routing");
14
15 static int no_bypassroute_declared = 1;
16
17 void generic_free_route(sg_platf_route_cbarg_t route)
18 {
19   if (route) {
20     xbt_dynar_free(&route->link_list);
21     xbt_free(route);
22   }
23 }
24
25 void AsGeneric::parseRoute(sg_platf_route_cbarg_t /*route*/){
26   THROW_IMPOSSIBLE;
27 }
28
29 void AsGeneric::parseASroute(sg_platf_route_cbarg_t /*route*/){
30   THROW_IMPOSSIBLE;
31 }
32
33 void AsGeneric::getRouteAndLatency(RoutingEdgePtr /*src*/, RoutingEdgePtr /*dst*/, sg_platf_route_cbarg_t /*into*/, double */*latency*/){
34   THROW_IMPOSSIBLE;
35 }
36
37 AsGeneric::AsGeneric() {
38   p_bypassRoutes = xbt_dict_new_homogeneous((void (*)(void *)) generic_free_route);
39 }
40
41 AsGeneric::~AsGeneric() {
42   xbt_dict_free(&p_bypassRoutes);
43 }
44
45 int AsGeneric::parsePU(RoutingEdgePtr elm)
46 {
47   XBT_DEBUG("Load process unit \"%s\"", elm->getName());
48   xbt_dynar_push_as(p_indexNetworkElm, RoutingEdgePtr, elm);
49   return xbt_dynar_length(p_indexNetworkElm)-1;
50 }
51
52 int AsGeneric::parseAS(RoutingEdgePtr elm)
53 {
54   XBT_DEBUG("Load Autonomous system \"%s\"", elm->getName());
55   xbt_dynar_push_as(p_indexNetworkElm, RoutingEdgePtr, elm);
56   return xbt_dynar_length(p_indexNetworkElm)-1;
57 }
58
59 void AsGeneric::parseBypassroute(sg_platf_route_cbarg_t e_route)
60 {
61   char *src = (char*)(e_route->src);
62   char *dst = (char*)(e_route->dst);
63
64   if(e_route->gw_dst)
65     XBT_DEBUG("Load bypassASroute from \"%s\" to \"%s\"", src, dst);
66   else
67     XBT_DEBUG("Load bypassRoute from \"%s\" to \"%s\"", src, dst);
68   xbt_dict_t dict_bypassRoutes = p_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->gw_src->getName(), dst, e_route->gw_dst->getName());
78
79   sg_platf_route_cbarg_t new_e_route = NULL;
80   if(e_route->gw_dst)
81     new_e_route =  newExtendedRoute(SURF_ROUTING_RECURSIVE, e_route, 1);
82   else
83     new_e_route =  newExtendedRoute(SURF_ROUTING_BASE, e_route, 1);
84
85   xbt_dynar_free(&(e_route->link_list));
86
87   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route, NULL);
88   no_bypassroute_declared = 0;
89   xbt_free(route_name);
90 }
91
92 /* ************************************************************************** */
93 /* *********************** GENERIC BUSINESS METHODS ************************* */
94
95 xbt_dynar_t AsGeneric::getOneLinkRoutes() { // FIXME: kill that stub
96   xbt_die("\"generic_get_onelink_routes\" not implemented yet");
97   return NULL;
98 }
99
100 static const char *instr_node_name(xbt_node_t node)
101 {
102   void *data = xbt_graph_node_get_data(node);
103   char *str = (char *) data;
104   return str;
105 }
106
107 xbt_node_t new_xbt_graph_node(xbt_graph_t graph, const char *name,
108                               xbt_dict_t nodes)
109 {
110   xbt_node_t ret = (xbt_node_t) xbt_dict_get_or_null(nodes, name);
111   if (ret)
112     return ret;
113
114   ret = xbt_graph_new_node(graph, xbt_strdup(name));
115   xbt_dict_set(nodes, name, ret, NULL);
116   return ret;
117 }
118
119 xbt_edge_t new_xbt_graph_edge(xbt_graph_t graph, xbt_node_t s, xbt_node_t d,
120                               xbt_dict_t edges)
121 {
122   xbt_edge_t ret;
123
124   const char *sn = instr_node_name(s);
125   const char *dn = instr_node_name(d);
126   int len = strlen(sn) + strlen(dn) + 1;
127   char *name = (char *) xbt_malloc(len * sizeof(char));
128
129
130   snprintf(name, len, "%s%s", sn, dn);
131   ret = (xbt_edge_t) xbt_dict_get_or_null(edges, name);
132   if (ret == NULL) {
133     snprintf(name, len, "%s%s", dn, sn);
134     ret = (xbt_edge_t) xbt_dict_get_or_null(edges, name);
135   }
136
137   if (ret == NULL) {
138     ret = xbt_graph_new_edge(graph, s, d, NULL);
139     xbt_dict_set(edges, name, ret, NULL);
140   }
141   free(name);
142   return ret;
143 }
144
145 void AsGeneric::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edges)
146 {
147   int src, dst;
148   int table_size = xbt_dynar_length(p_indexNetworkElm);
149
150
151   for (src = 0; src < table_size; src++) {
152     RoutingEdgePtr my_src =
153         xbt_dynar_get_as(p_indexNetworkElm, src, RoutingEdgePtr);
154     for (dst = 0; dst < table_size; dst++) {
155       if (src == dst)
156         continue;
157       RoutingEdgePtr my_dst =
158           xbt_dynar_get_as(p_indexNetworkElm, dst, RoutingEdgePtr);
159
160       sg_platf_route_cbarg_t route = xbt_new0(s_sg_platf_route_cbarg_t, 1);
161       route->link_list = xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
162
163       getRouteAndLatency(my_src, my_dst, route, NULL);
164
165       XBT_DEBUG ("get_route_and_latency %s -> %s", my_src->getName(), my_dst->getName());
166
167       unsigned int cpt;
168       void *link;
169
170       xbt_node_t current, previous;
171       const char *previous_name, *current_name;
172
173       if (route->gw_src) {
174         previous = new_xbt_graph_node(graph, route->gw_src->getName(), nodes);
175         previous_name = route->gw_src->getName();
176       } else {
177         previous = new_xbt_graph_node(graph, my_src->getName(), nodes);
178         previous_name = my_src->getName();
179       }
180
181       xbt_dynar_foreach(route->link_list, cpt, link) {
182         const char *link_name = ((ResourcePtr) link)->getName();
183         current = new_xbt_graph_node(graph, link_name, nodes);
184         current_name = link_name;
185         new_xbt_graph_edge(graph, previous, current, edges);
186         XBT_DEBUG ("  %s -> %s", previous_name, current_name);
187         previous = current;
188         previous_name = current_name;
189       }
190
191       if (route->gw_dst) {
192         current = new_xbt_graph_node(graph, route->gw_dst->getName(), nodes);
193         current_name = route->gw_dst->getName();
194       } else {
195         current = new_xbt_graph_node(graph, my_dst->getName(), nodes);
196         current_name = my_dst->getName();
197       }
198       new_xbt_graph_edge(graph, previous, current, edges);
199       XBT_DEBUG ("  %s -> %s", previous_name, current_name);
200
201       xbt_dynar_free (&(route->link_list));
202       xbt_free (route);
203     }
204   }
205 }
206
207 sg_platf_route_cbarg_t AsGeneric::getBypassRoute(RoutingEdgePtr src,
208                                                RoutingEdgePtr dst,
209                                                double *lat)
210 {
211   // If never set a bypass route return NULL without any further computations
212   XBT_DEBUG("generic_get_bypassroute from %s to %s", src->getName(), dst->getName());
213   if (no_bypassroute_declared)
214     return NULL;
215
216   sg_platf_route_cbarg_t e_route_bypass = NULL;
217   xbt_dict_t dict_bypassRoutes = p_bypassRoutes;
218
219   if(dst->getRcComponent() == this && src->getRcComponent() == this ){
220     char *route_name = bprintf("%s#%s", src->getName(), dst->getName());
221     e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
222     if(e_route_bypass)
223       XBT_DEBUG("Find bypass route with %ld links",xbt_dynar_length(e_route_bypass->link_list));
224     free(route_name);
225   }
226   else{
227     AsPtr src_as, dst_as;
228     int index_src, index_dst;
229     xbt_dynar_t path_src = NULL;
230     xbt_dynar_t path_dst = NULL;
231     AsPtr current = NULL;
232     AsPtr *current_src = NULL;
233     AsPtr *current_dst = NULL;
234
235     if (src == NULL || dst == NULL)
236       xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
237           src->getName(), dst->getName(), p_name);
238
239     src_as = src->getRcComponent();
240     dst_as = dst->getRcComponent();
241
242     /* (2) find the path to the root routing component */
243     path_src = xbt_dynar_new(sizeof(AsPtr), NULL);
244     current = src_as;
245     while (current != NULL) {
246       xbt_dynar_push(path_src, &current);
247       current = current->p_routingFather;
248     }
249     path_dst = xbt_dynar_new(sizeof(AsPtr), NULL);
250     current = dst_as;
251     while (current != NULL) {
252       xbt_dynar_push(path_dst, &current);
253       current = current->p_routingFather;
254     }
255
256     /* (3) find the common father */
257     index_src = path_src->used - 1;
258     index_dst = path_dst->used - 1;
259     current_src = (AsPtr *) xbt_dynar_get_ptr(path_src, index_src);
260     current_dst = (AsPtr *) xbt_dynar_get_ptr(path_dst, index_dst);
261     while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
262       xbt_dynar_pop_ptr(path_src);
263       xbt_dynar_pop_ptr(path_dst);
264       index_src--;
265       index_dst--;
266       current_src = (AsPtr *) xbt_dynar_get_ptr(path_src, index_src);
267       current_dst = (AsPtr *) xbt_dynar_get_ptr(path_dst, index_dst);
268     }
269
270     int max_index_src = path_src->used - 1;
271     int max_index_dst = path_dst->used - 1;
272
273     int max_index = max(max_index_src, max_index_dst);
274     int i, max;
275
276     for (max = 0; max <= max_index; max++) {
277       for (i = 0; i < max; i++) {
278         if (i <= max_index_src && max <= max_index_dst) {
279           char *route_name = bprintf("%s#%s",
280               (*(AsPtr *)
281                   (xbt_dynar_get_ptr(path_src, i)))->p_name,
282                   (*(AsPtr *)
283                       (xbt_dynar_get_ptr(path_dst, max)))->p_name);
284           e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
285           xbt_free(route_name);
286         }
287         if (e_route_bypass)
288           break;
289         if (max <= max_index_src && i <= max_index_dst) {
290           char *route_name = bprintf("%s#%s",
291               (*(AsPtr *)
292                   (xbt_dynar_get_ptr(path_src, max)))->p_name,
293                   (*(AsPtr *)
294                       (xbt_dynar_get_ptr(path_dst, i)))->p_name);
295           e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
296           xbt_free(route_name);
297         }
298         if (e_route_bypass)
299           break;
300       }
301
302       if (e_route_bypass)
303         break;
304
305       if (max <= max_index_src && max <= max_index_dst) {
306         char *route_name = bprintf("%s#%s",
307             (*(AsPtr *)
308                 (xbt_dynar_get_ptr(path_src, max)))->p_name,
309                 (*(AsPtr *)
310                     (xbt_dynar_get_ptr(path_dst, max)))->p_name);
311         e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
312         xbt_free(route_name);
313       }
314       if (e_route_bypass)
315         break;
316     }
317
318     xbt_dynar_free(&path_src);
319     xbt_dynar_free(&path_dst);
320   }
321
322   sg_platf_route_cbarg_t new_e_route = NULL;
323   if (e_route_bypass) {
324     NetworkLinkPtr link;
325     unsigned int cpt = 0;
326     new_e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1);
327     new_e_route->gw_src = e_route_bypass->gw_src;
328     new_e_route->gw_dst = e_route_bypass->gw_dst;
329     new_e_route->link_list =
330         xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
331     xbt_dynar_foreach(e_route_bypass->link_list, cpt, link) {
332       xbt_dynar_push(new_e_route->link_list, &link);
333       if (lat)
334         *lat += link->getLatency();
335     }
336   }
337
338   return new_e_route;
339 }
340
341 /* ************************************************************************** */
342 /* ************************* GENERIC AUX FUNCTIONS ************************** */
343 /* change a route containing link names into a route containing link entities */
344 sg_platf_route_cbarg_t AsGeneric::newExtendedRoute(e_surf_routing_hierarchy_t hierarchy,
345       sg_platf_route_cbarg_t routearg, int change_order) {
346
347   sg_platf_route_cbarg_t result;
348   char *link_name;
349   unsigned int cpt;
350
351   result = xbt_new0(s_sg_platf_route_cbarg_t, 1);
352   result->link_list = xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
353
354   xbt_assert(hierarchy == SURF_ROUTING_BASE
355       || hierarchy == SURF_ROUTING_RECURSIVE,
356       "The hierarchy of this AS is neither BASIC nor RECURSIVE, I'm lost here.");
357
358   if (hierarchy == SURF_ROUTING_RECURSIVE) {
359
360     xbt_assert(routearg->gw_src && routearg->gw_dst,
361         "NULL is obviously a bad gateway");
362
363     /* remeber not erase the gateway names */
364     result->gw_src = routearg->gw_src;
365     result->gw_dst = routearg->gw_dst;
366   }
367
368   xbt_dynar_foreach(routearg->link_list, cpt, link_name) {
369
370     void *link = xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
371     if (link) {
372       if (change_order)
373         xbt_dynar_push(result->link_list, &link);
374       else
375         xbt_dynar_unshift(result->link_list, &link);
376     } else
377       THROWF(mismatch_error, 0, "Link %s not found", link_name);
378   }
379
380   return result;
381 }
382
383
384
385 AsPtr AsGeneric::asExist(AsPtr to_find)
386 {
387   //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
388   xbt_dict_cursor_t cursor = NULL;
389   char *key;
390   int found = 0;
391   AsGenericPtr elem;
392   xbt_dict_foreach(p_routingSons, cursor, key, elem) {
393     if (to_find == elem || elem->asExist(to_find)) {
394       found = 1;
395       break;
396     }
397   }
398   if (found)
399     return to_find;
400   return NULL;
401 }
402
403 AsPtr AsGeneric::autonomousSystemExist(char *element)
404 {
405   //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
406   AsPtr element_as, result, elem;
407   xbt_dict_cursor_t cursor = NULL;
408   char *key;
409   element_as = ((RoutingEdgePtr)
410       xbt_lib_get_or_null(as_router_lib, element,
411           ROUTING_ASR_LEVEL))->getRcComponent();
412   result = ((AsPtr) - 1);
413   if (element_as != this)
414     result = asExist(element_as);
415
416   int found = 0;
417   if (result) {
418     xbt_dict_foreach(element_as->p_routingSons, cursor, key, elem) {
419       found = !strcmp(elem->p_name, element);
420       if (found)
421         break;
422     }
423     if (found)
424       return element_as;
425   }
426   return NULL;
427 }
428
429 AsPtr AsGeneric::processingUnitsExist(char *element)
430 {
431   AsPtr element_as;
432   element_as = ((RoutingEdgePtr)
433       xbt_lib_get_or_null(host_lib,
434           element, ROUTING_HOST_LEVEL))->getRcComponent();
435   if (element_as == this)
436     return element_as;
437   return asExist(element_as);
438 }
439
440 void AsGeneric::srcDstCheck(RoutingEdgePtr src, RoutingEdgePtr dst)
441 {
442
443   RoutingEdgePtr src_data = src;
444   RoutingEdgePtr dst_data = dst;
445
446   if (src_data == NULL || dst_data == NULL)
447     xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
448         src->getName(),
449         dst->getName(),
450         p_name);
451
452   AsPtr src_as =
453       (src_data)->getRcComponent();
454   AsPtr dst_as =
455       (dst_data)->getRcComponent();
456
457   if (src_as != dst_as)
458     xbt_die("The src(%s in %s) and dst(%s in %s) are in differents AS",
459         src->getName(), src_as->p_name,
460         dst->getName(), dst_as->p_name);
461
462   if (this != dst_as)
463     xbt_die
464     ("The routing component of src'%s' and dst'%s' is not the same as the network elements belong (%s?=%s?=%s)",
465         src->getName(),
466         dst->getName(),
467         src_as->p_name,
468         dst_as->p_name,
469         p_name);
470 }