1 /* Copyright (c) 2009-2014. The SimGrid Team.
2 * All rights reserved. */
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. */
7 #include "simgrid/platf_interface.h" // platform creation API internal interface
9 #include "surf_routing_generic.hpp"
10 #include "network_interface.hpp"
11 #include "xbt/graph.h"
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_routing_generic, surf_route, "Generic implementation of the surf routing");
15 static int no_bypassroute_declared = 1;
17 void generic_free_route(sg_platf_route_cbarg_t route)
20 xbt_dynar_free(&route->link_list);
25 void AsGeneric::parseRoute(sg_platf_route_cbarg_t /*route*/){
29 void AsGeneric::parseASroute(sg_platf_route_cbarg_t /*route*/){
33 void AsGeneric::getRouteAndLatency(RoutingEdgePtr /*src*/, RoutingEdgePtr /*dst*/, sg_platf_route_cbarg_t /*into*/, double */*latency*/){
37 AsGeneric::AsGeneric() {
38 p_bypassRoutes = xbt_dict_new_homogeneous((void (*)(void *)) generic_free_route);
41 AsGeneric::~AsGeneric() {
42 xbt_dict_free(&p_bypassRoutes);
45 int AsGeneric::parsePU(RoutingEdgePtr elm)
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;
52 int AsGeneric::parseAS(RoutingEdgePtr elm)
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;
59 void AsGeneric::parseBypassroute(sg_platf_route_cbarg_t e_route)
61 char *src = (char*)(e_route->src);
62 char *dst = (char*)(e_route->dst);
65 XBT_DEBUG("Load bypassASroute from \"%s\" to \"%s\"", src, dst);
67 XBT_DEBUG("Load bypassRoute from \"%s\" to \"%s\"", src, dst);
68 xbt_dict_t dict_bypassRoutes = p_bypassRoutes;
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)",
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());
79 sg_platf_route_cbarg_t new_e_route = NULL;
81 new_e_route = newExtendedRoute(SURF_ROUTING_RECURSIVE, e_route, 1);
83 new_e_route = newExtendedRoute(SURF_ROUTING_BASE, e_route, 1);
85 xbt_dynar_free(&(e_route->link_list));
87 xbt_dict_set(dict_bypassRoutes, route_name, new_e_route, NULL);
88 no_bypassroute_declared = 0;
92 /* ************************************************************************** */
93 /* *********************** GENERIC BUSINESS METHODS ************************* */
95 xbt_dynar_t AsGeneric::getOneLinkRoutes() { // FIXME: kill that stub
96 xbt_die("\"generic_get_onelink_routes\" not implemented yet");
100 static const char *instr_node_name(xbt_node_t node)
102 void *data = xbt_graph_node_get_data(node);
103 char *str = (char *) data;
107 xbt_node_t new_xbt_graph_node(xbt_graph_t graph, const char *name,
110 xbt_node_t ret = (xbt_node_t) xbt_dict_get_or_null(nodes, name);
114 ret = xbt_graph_new_node(graph, xbt_strdup(name));
115 xbt_dict_set(nodes, name, ret, NULL);
119 xbt_edge_t new_xbt_graph_edge(xbt_graph_t graph, xbt_node_t s, xbt_node_t d,
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));
130 snprintf(name, len, "%s%s", sn, dn);
131 ret = (xbt_edge_t) xbt_dict_get_or_null(edges, name);
133 snprintf(name, len, "%s%s", dn, sn);
134 ret = (xbt_edge_t) xbt_dict_get_or_null(edges, name);
138 ret = xbt_graph_new_edge(graph, s, d, NULL);
139 xbt_dict_set(edges, name, ret, NULL);
145 void AsGeneric::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edges)
148 int table_size = xbt_dynar_length(p_indexNetworkElm);
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++) {
157 RoutingEdgePtr my_dst =
158 xbt_dynar_get_as(p_indexNetworkElm, dst, RoutingEdgePtr);
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);
163 getRouteAndLatency(my_src, my_dst, route, NULL);
165 XBT_DEBUG ("get_route_and_latency %s -> %s", my_src->getName(), my_dst->getName());
170 xbt_node_t current, previous;
171 const char *previous_name, *current_name;
174 previous = new_xbt_graph_node(graph, route->gw_src->getName(), nodes);
175 previous_name = route->gw_src->getName();
177 previous = new_xbt_graph_node(graph, my_src->getName(), nodes);
178 previous_name = my_src->getName();
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);
188 previous_name = current_name;
192 current = new_xbt_graph_node(graph, route->gw_dst->getName(), nodes);
193 current_name = route->gw_dst->getName();
195 current = new_xbt_graph_node(graph, my_dst->getName(), nodes);
196 current_name = my_dst->getName();
198 new_xbt_graph_edge(graph, previous, current, edges);
199 XBT_DEBUG (" %s -> %s", previous_name, current_name);
201 xbt_dynar_free (&(route->link_list));
207 sg_platf_route_cbarg_t AsGeneric::getBypassRoute(RoutingEdgePtr src,
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)
216 sg_platf_route_cbarg_t e_route_bypass = NULL;
217 xbt_dict_t dict_bypassRoutes = p_bypassRoutes;
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);
223 XBT_DEBUG("Find bypass route with %ld links",xbt_dynar_length(e_route_bypass->link_list));
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;
235 if (src == NULL || dst == NULL)
236 xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
237 src ? src->getName() : "(null)",
238 dst ? dst->getName() : "(null)", p_name);
240 src_as = src->getRcComponent();
241 dst_as = dst->getRcComponent();
243 /* (2) find the path to the root routing component */
244 path_src = xbt_dynar_new(sizeof(AsPtr), NULL);
246 while (current != NULL) {
247 xbt_dynar_push(path_src, ¤t);
248 current = current->p_routingFather;
250 path_dst = xbt_dynar_new(sizeof(AsPtr), NULL);
252 while (current != NULL) {
253 xbt_dynar_push(path_dst, ¤t);
254 current = current->p_routingFather;
257 /* (3) find the common father */
258 index_src = path_src->used - 1;
259 index_dst = path_dst->used - 1;
260 current_src = (AsPtr *) xbt_dynar_get_ptr(path_src, index_src);
261 current_dst = (AsPtr *) xbt_dynar_get_ptr(path_dst, index_dst);
262 while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
263 xbt_dynar_pop_ptr(path_src);
264 xbt_dynar_pop_ptr(path_dst);
267 current_src = (AsPtr *) xbt_dynar_get_ptr(path_src, index_src);
268 current_dst = (AsPtr *) xbt_dynar_get_ptr(path_dst, index_dst);
271 int max_index_src = path_src->used - 1;
272 int max_index_dst = path_dst->used - 1;
274 int max_index = max(max_index_src, max_index_dst);
277 for (max = 0; max <= max_index; max++) {
278 for (i = 0; i < max; i++) {
279 if (i <= max_index_src && max <= max_index_dst) {
280 char *route_name = bprintf("%s#%s",
282 (xbt_dynar_get_ptr(path_src, i)))->p_name,
284 (xbt_dynar_get_ptr(path_dst, max)))->p_name);
285 e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
286 xbt_free(route_name);
290 if (max <= max_index_src && i <= max_index_dst) {
291 char *route_name = bprintf("%s#%s",
293 (xbt_dynar_get_ptr(path_src, max)))->p_name,
295 (xbt_dynar_get_ptr(path_dst, i)))->p_name);
296 e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
297 xbt_free(route_name);
306 if (max <= max_index_src && max <= max_index_dst) {
307 char *route_name = bprintf("%s#%s",
309 (xbt_dynar_get_ptr(path_src, max)))->p_name,
311 (xbt_dynar_get_ptr(path_dst, max)))->p_name);
312 e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
313 xbt_free(route_name);
319 xbt_dynar_free(&path_src);
320 xbt_dynar_free(&path_dst);
323 sg_platf_route_cbarg_t new_e_route = NULL;
324 if (e_route_bypass) {
326 unsigned int cpt = 0;
327 new_e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1);
328 new_e_route->gw_src = e_route_bypass->gw_src;
329 new_e_route->gw_dst = e_route_bypass->gw_dst;
330 new_e_route->link_list =
331 xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
332 xbt_dynar_foreach(e_route_bypass->link_list, cpt, link) {
333 xbt_dynar_push(new_e_route->link_list, &link);
335 *lat += link->getLatency();
342 /* ************************************************************************** */
343 /* ************************* GENERIC AUX FUNCTIONS ************************** */
344 /* change a route containing link names into a route containing link entities */
345 sg_platf_route_cbarg_t AsGeneric::newExtendedRoute(e_surf_routing_hierarchy_t hierarchy,
346 sg_platf_route_cbarg_t routearg, int change_order) {
348 sg_platf_route_cbarg_t result;
352 result = xbt_new0(s_sg_platf_route_cbarg_t, 1);
353 result->link_list = xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
355 xbt_assert(hierarchy == SURF_ROUTING_BASE
356 || hierarchy == SURF_ROUTING_RECURSIVE,
357 "The hierarchy of this AS is neither BASIC nor RECURSIVE, I'm lost here.");
359 if (hierarchy == SURF_ROUTING_RECURSIVE) {
361 xbt_assert(routearg->gw_src && routearg->gw_dst,
362 "NULL is obviously a bad gateway");
364 /* remeber not erase the gateway names */
365 result->gw_src = routearg->gw_src;
366 result->gw_dst = routearg->gw_dst;
369 xbt_dynar_foreach(routearg->link_list, cpt, link_name) {
371 void *link = xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
374 xbt_dynar_push(result->link_list, &link);
376 xbt_dynar_unshift(result->link_list, &link);
378 THROWF(mismatch_error, 0, "Link %s not found", link_name);
386 AsPtr AsGeneric::asExist(AsPtr to_find)
388 //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
389 xbt_dict_cursor_t cursor = NULL;
393 xbt_dict_foreach(p_routingSons, cursor, key, elem) {
394 if (to_find == elem || elem->asExist(to_find)) {
404 AsPtr AsGeneric::autonomousSystemExist(char *element)
406 //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
407 AsPtr element_as, result, elem;
408 xbt_dict_cursor_t cursor = NULL;
410 element_as = ((RoutingEdgePtr)
411 xbt_lib_get_or_null(as_router_lib, element,
412 ROUTING_ASR_LEVEL))->getRcComponent();
413 result = ((AsPtr) - 1);
414 if (element_as != this)
415 result = asExist(element_as);
419 xbt_dict_foreach(element_as->p_routingSons, cursor, key, elem) {
420 found = !strcmp(elem->p_name, element);
430 AsPtr AsGeneric::processingUnitsExist(char *element)
433 element_as = ((RoutingEdgePtr)
434 xbt_lib_get_or_null(host_lib,
435 element, ROUTING_HOST_LEVEL))->getRcComponent();
436 if (element_as == this)
438 return asExist(element_as);
441 void AsGeneric::srcDstCheck(RoutingEdgePtr src, RoutingEdgePtr dst)
443 if (src == NULL || dst == NULL)
444 xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
445 src ? src->getName() : "(null)",
446 dst ? dst->getName() : "(null)",
449 AsPtr src_as = src->getRcComponent();
450 AsPtr dst_as = dst->getRcComponent();
452 if (src_as != dst_as)
453 xbt_die("The src(%s in %s) and dst(%s in %s) are in differents AS",
454 src->getName(), src_as->p_name,
455 dst->getName(), dst_as->p_name);
459 ("The routing component of src'%s' and dst'%s' is not the same as the network elements belong (%s?=%s?=%s)",