src/surf/surf_routing_generic.cpp

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