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(NetCard */*src*/, NetCard */*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(NetCard *elm)
  59 {
  60   XBT_DEBUG("Load process unit \"%s\"", elm->getName());
  61   xbt_dynar_push_as(p_indexNetworkElm, NetCard*, elm);
  62   return xbt_dynar_length(p_indexNetworkElm)-1;
  63 }
  64
  65 int AsGeneric::parseAS(NetCard *elm)
  66 {
  67   XBT_DEBUG("Load Autonomous system \"%s\"", elm->getName());
  68   xbt_dynar_push_as(p_indexNetworkElm, NetCard*, 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 void AsGeneric::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edges)
 160 {
 161   int src, dst;
 162   int table_size = xbt_dynar_length(p_indexNetworkElm);
 163
 164
 165   for (src = 0; src < table_size; src++) {
 166     NetCard *my_src =
 167         xbt_dynar_get_as(p_indexNetworkElm, src, NetCard*);
 168     for (dst = 0; dst < table_size; dst++) {
 169       if (src == dst)
 170         continue;
 171       NetCard *my_dst =
 172           xbt_dynar_get_as(p_indexNetworkElm, dst, NetCard*);
 173
 174       sg_platf_route_cbarg_t route = xbt_new0(s_sg_platf_route_cbarg_t, 1);
 175       route->link_list = xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
 176
 177       getRouteAndLatency(my_src, my_dst, route, NULL);
 178
 179       XBT_DEBUG ("get_route_and_latency %s -> %s", my_src->getName(), my_dst->getName());
 180
 181       unsigned int cpt;
 182       void *link;
 183
 184       xbt_node_t current, previous;
 185       const char *previous_name, *current_name;
 186
 187       if (route->gw_src) {
 188         previous = new_xbt_graph_node(graph, route->gw_src->getName(), nodes);
 189         previous_name = route->gw_src->getName();
 190       } else {
 191         previous = new_xbt_graph_node(graph, my_src->getName(), nodes);
 192         previous_name = my_src->getName();
 193       }
 194
 195       xbt_dynar_foreach(route->link_list, cpt, link) {
 196         const char *link_name = static_cast<simgrid::surf::Resource*>(
 197           link)->getName();
 198         current = new_xbt_graph_node(graph, link_name, nodes);
 199         current_name = link_name;
 200         new_xbt_graph_edge(graph, previous, current, edges);
 201         XBT_DEBUG ("  %s -> %s", previous_name, current_name);
 202         previous = current;
 203         previous_name = current_name;
 204       }
 205
 206       if (route->gw_dst) {
 207         current = new_xbt_graph_node(graph, route->gw_dst->getName(), nodes);
 208         current_name = route->gw_dst->getName();
 209       } else {
 210         current = new_xbt_graph_node(graph, my_dst->getName(), nodes);
 211         current_name = my_dst->getName();
 212       }
 213       new_xbt_graph_edge(graph, previous, current, edges);
 214       XBT_DEBUG ("  %s -> %s", previous_name, current_name);
 215
 216       xbt_dynar_free (&(route->link_list));
 217       xbt_free (route);
 218     }
 219   }
 220 }
 221
 222 sg_platf_route_cbarg_t AsGeneric::getBypassRoute(NetCard *src,
 223                                                NetCard *dst,
 224                                                double *lat)
 225 {
 226   // If never set a bypass route return NULL without any further computations
 227   XBT_DEBUG("generic_get_bypassroute from %s to %s", src->getName(), dst->getName());
 228   if (no_bypassroute_declared)
 229     return NULL;
 230
 231   sg_platf_route_cbarg_t e_route_bypass = NULL;
 232   xbt_dict_t dict_bypassRoutes = p_bypassRoutes;
 233
 234   if(dst->getRcComponent() == this && src->getRcComponent() == this ){
 235     char *route_name = bprintf("%s#%s", src->getName(), dst->getName());
 236     e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 237     if(e_route_bypass)
 238       XBT_DEBUG("Find bypass route with %ld links",xbt_dynar_length(e_route_bypass->link_list));
 239     free(route_name);
 240   }
 241   else{
 242     As *src_as, *dst_as;
 243     int index_src, index_dst;
 244     xbt_dynar_t path_src = NULL;
 245     xbt_dynar_t path_dst = NULL;
 246     As *current = NULL;
 247     As **current_src = NULL;
 248     As **current_dst = NULL;
 249
 250     if (src == NULL || dst == NULL)
 251       xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
 252               src ? src->getName() : "(null)",
 253               dst ? dst->getName() : "(null)", p_name);
 254
 255     src_as = src->getRcComponent();
 256     dst_as = dst->getRcComponent();
 257
 258     /* (2) find the path to the root routing component */
 259     path_src = xbt_dynar_new(sizeof(As*), NULL);
 260     current = src_as;
 261     while (current != NULL) {
 262       xbt_dynar_push(path_src, &current);
 263       current = current->p_routingFather;
 264     }
 265     path_dst = xbt_dynar_new(sizeof(As*), NULL);
 266     current = dst_as;
 267     while (current != NULL) {
 268       xbt_dynar_push(path_dst, &current);
 269       current = current->p_routingFather;
 270     }
 271
 272     /* (3) find the common father */
 273     index_src = path_src->used - 1;
 274     index_dst = path_dst->used - 1;
 275     current_src = (As **) xbt_dynar_get_ptr(path_src, index_src);
 276     current_dst = (As **) xbt_dynar_get_ptr(path_dst, index_dst);
 277     while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
 278       xbt_dynar_pop_ptr(path_src);
 279       xbt_dynar_pop_ptr(path_dst);
 280       index_src--;
 281       index_dst--;
 282       current_src = (As **) xbt_dynar_get_ptr(path_src, index_src);
 283       current_dst = (As **) xbt_dynar_get_ptr(path_dst, index_dst);
 284     }
 285
 286     int max_index_src = path_src->used - 1;
 287     int max_index_dst = path_dst->used - 1;
 288
 289     int max_index = std::max(max_index_src, max_index_dst);
 290     int i, max;
 291
 292     for (max = 0; max <= max_index; max++) {
 293       for (i = 0; i < max; i++) {
 294         if (i <= max_index_src && max <= max_index_dst) {
 295           char *route_name = bprintf("%s#%s",
 296               (*(As **)
 297                   (xbt_dynar_get_ptr(path_src, i)))->p_name,
 298                   (*(As **)
 299                       (xbt_dynar_get_ptr(path_dst, max)))->p_name);
 300           e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 301           xbt_free(route_name);
 302         }
 303         if (e_route_bypass)
 304           break;
 305         if (max <= max_index_src && i <= max_index_dst) {
 306           char *route_name = bprintf("%s#%s",
 307               (*(As **)
 308                   (xbt_dynar_get_ptr(path_src, max)))->p_name,
 309                   (*(As **)
 310                       (xbt_dynar_get_ptr(path_dst, i)))->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       if (e_route_bypass)
 319         break;
 320
 321       if (max <= max_index_src && max <= max_index_dst) {
 322         char *route_name = bprintf("%s#%s",
 323             (*(As **)
 324                 (xbt_dynar_get_ptr(path_src, max)))->p_name,
 325                 (*(As **)
 326                     (xbt_dynar_get_ptr(path_dst, max)))->p_name);
 327         e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 328         xbt_free(route_name);
 329       }
 330       if (e_route_bypass)
 331         break;
 332     }
 333
 334     xbt_dynar_free(&path_src);
 335     xbt_dynar_free(&path_dst);
 336   }
 337
 338   sg_platf_route_cbarg_t new_e_route = NULL;
 339   if (e_route_bypass) {
 340           Link* link;
 341     unsigned int cpt = 0;
 342     new_e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1);
 343     new_e_route->gw_src = e_route_bypass->gw_src;
 344     new_e_route->gw_dst = e_route_bypass->gw_dst;
 345     new_e_route->link_list =
 346         xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
 347     xbt_dynar_foreach(e_route_bypass->link_list, cpt, link) {
 348       xbt_dynar_push(new_e_route->link_list, &link);
 349       if (lat)
 350         *lat += link->getLatency();
 351     }
 352   }
 353
 354   return new_e_route;
 355 }
 356
 357 /* ************************************************************************** */
 358 /* ************************* GENERIC AUX FUNCTIONS ************************** */
 359 /* change a route containing link names into a route containing link entities */
 360 sg_platf_route_cbarg_t AsGeneric::newExtendedRoute(e_surf_routing_hierarchy_t hierarchy,
 361       sg_platf_route_cbarg_t routearg, int change_order) {
 362
 363   sg_platf_route_cbarg_t result;
 364   char *link_name;
 365   unsigned int cpt;
 366
 367   result = xbt_new0(s_sg_platf_route_cbarg_t, 1);
 368   result->link_list = xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
 369
 370   xbt_assert(hierarchy == SURF_ROUTING_BASE
 371       || hierarchy == SURF_ROUTING_RECURSIVE,
 372       "The hierarchy of this AS is neither BASIC nor RECURSIVE, I'm lost here.");
 373
 374   if (hierarchy == SURF_ROUTING_RECURSIVE) {
 375
 376     xbt_assert(routearg->gw_src && routearg->gw_dst,
 377         "NULL is obviously a bad gateway");
 378
 379     /* remember not erase the gateway names */
 380     result->gw_src = routearg->gw_src;
 381     result->gw_dst = routearg->gw_dst;
 382   }
 383
 384   xbt_dynar_foreach(routearg->link_list, cpt, link_name) {
 385
 386     Link *link = Link::byName(link_name);
 387     if (link) {
 388       if (change_order)
 389         xbt_dynar_push(result->link_list, &link);
 390       else
 391         xbt_dynar_unshift(result->link_list, &link);
 392     } else
 393       THROWF(mismatch_error, 0, "Link '%s' not found", link_name);
 394   }
 395
 396   return result;
 397 }
 398
 399
 400
 401 As *AsGeneric::asExist(As *to_find)
 402 {
 403   //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
 404   xbt_dict_cursor_t cursor = NULL;
 405   char *key;
 406   int found = 0;
 407   AsGeneric *elem;
 408   xbt_dict_foreach(p_routingSons, cursor, key, elem) {
 409     if (to_find == elem || elem->asExist(to_find)) {
 410       found = 1;
 411       break;
 412     }
 413   }
 414   if (found)
 415     return to_find;
 416   return NULL;
 417 }
 418
 419 As *AsGeneric::autonomousSystemExist(char *element)
 420 {
 421   //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
 422   As *element_as, *result, *elem;
 423   xbt_dict_cursor_t cursor = NULL;
 424   char *key;
 425   element_as = ((NetCard*)
 426       xbt_lib_get_or_null(as_router_lib, element,
 427           ROUTING_ASR_LEVEL))->getRcComponent();
 428   result = ((As*) - 1);
 429   if (element_as != this)
 430     result = asExist(element_as);
 431
 432   int found = 0;
 433   if (result) {
 434     xbt_dict_foreach(element_as->p_routingSons, cursor, key, elem) {
 435       found = !strcmp(elem->p_name, element);
 436       if (found)
 437         break;
 438     }
 439     if (found)
 440       return element_as;
 441   }
 442   return NULL;
 443 }
 444
 445 As *AsGeneric::processingUnitsExist(char *element)
 446 {
 447   As *element_as = sg_host_by_name(element)->pimpl_netcard ->getRcComponent();
 448   if (element_as == this)
 449     return element_as;
 450   return asExist(element_as);
 451 }
 452
 453 void AsGeneric::srcDstCheck(NetCard *src, NetCard *dst)
 454 {
 455   if (src == NULL || dst == NULL)
 456     xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
 457             src ? src->getName() : "(null)",
 458             dst ? dst->getName() : "(null)",
 459             p_name);
 460
 461   As *src_as = src->getRcComponent();
 462   As *dst_as = dst->getRcComponent();
 463
 464   if (src_as != dst_as)
 465     xbt_die("The src(%s in %s) and dst(%s in %s) are in differents AS",
 466         src->getName(), src_as->p_name,
 467         dst->getName(), dst_as->p_name);
 468
 469   if (this != dst_as)
 470     xbt_die
 471     ("The routing component of src'%s' and dst'%s' is not the same as the network elements belong (%s?=%s?=%s)",
 472         src->getName(),
 473         dst->getName(),
 474         src_as->p_name,
 475         dst_as->p_name,
 476         p_name);
 477 }
 478
 479 }
 480 }