src/surf/surf_routing_generic.cpp

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