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 routing_route_free(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(const char*name)
  51   : AsNone(name)
  52 {
  53   p_bypassRoutes = xbt_dict_new_homogeneous((void (*)(void *)) routing_route_free);
  54 }
  55
  56 AsGeneric::~AsGeneric()
  57 {
  58   xbt_dict_free(&p_bypassRoutes);
  59 }
  60
  61 int AsGeneric::parsePU(NetCard *elm)
  62 {
  63   XBT_DEBUG("Load process unit \"%s\"", elm->getName());
  64   xbt_dynar_push_as(p_indexNetworkElm, NetCard*, elm);
  65   return xbt_dynar_length(p_indexNetworkElm)-1;
  66 }
  67
  68 int AsGeneric::parseAS(NetCard *elm)
  69 {
  70   XBT_DEBUG("Load Autonomous system \"%s\"", elm->getName());
  71   xbt_dynar_push_as(p_indexNetworkElm, NetCard*, elm);
  72   return xbt_dynar_length(p_indexNetworkElm)-1;
  73 }
  74
  75 void AsGeneric::parseBypassroute(sg_platf_route_cbarg_t e_route)
  76 {
  77   char *src = (char*)(e_route->src);
  78   char *dst = (char*)(e_route->dst);
  79
  80   if(e_route->gw_dst)
  81     XBT_DEBUG("Load bypassASroute from \"%s\" to \"%s\"", src, dst);
  82   else
  83     XBT_DEBUG("Load bypassRoute from \"%s\" to \"%s\"", src, dst);
  84   xbt_dict_t dict_bypassRoutes = p_bypassRoutes;
  85   char *route_name;
  86
  87   route_name = bprintf("%s#%s", src, dst);
  88   xbt_assert(!xbt_dynar_is_empty(e_route->link_list),
  89       "Invalid count of links, must be greater than zero (%s,%s)",
  90       src, dst);
  91   xbt_assert(!xbt_dict_get_or_null(dict_bypassRoutes, route_name),
  92       "The bypass route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exists",
  93       src, e_route->gw_src->getName(), dst, e_route->gw_dst->getName());
  94
  95   sg_platf_route_cbarg_t new_e_route = NULL;
  96   if(e_route->gw_dst)
  97     new_e_route =  newExtendedRoute(SURF_ROUTING_RECURSIVE, e_route, 1);
  98   else
  99     new_e_route =  newExtendedRoute(SURF_ROUTING_BASE, e_route, 1);
 100
 101   xbt_dynar_free(&(e_route->link_list));
 102
 103   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route, NULL);
 104   no_bypassroute_declared = 0;
 105   xbt_free(route_name);
 106 }
 107
 108 }
 109 }
 110
 111 /* ************************************************************************** */
 112 /* *********************** GENERIC BUSINESS METHODS ************************* */
 113
 114 static const char *instr_node_name(xbt_node_t node)
 115 {
 116   void *data = xbt_graph_node_get_data(node);
 117   char *str = (char *) data;
 118   return str;
 119 }
 120
 121 xbt_node_t new_xbt_graph_node(xbt_graph_t graph, const char *name,
 122                               xbt_dict_t nodes)
 123 {
 124   xbt_node_t ret = (xbt_node_t) xbt_dict_get_or_null(nodes, name);
 125   if (ret)
 126     return ret;
 127
 128   ret = xbt_graph_new_node(graph, xbt_strdup(name));
 129   xbt_dict_set(nodes, name, ret, NULL);
 130   return ret;
 131 }
 132
 133 xbt_edge_t new_xbt_graph_edge(xbt_graph_t graph, xbt_node_t s, xbt_node_t d,
 134                               xbt_dict_t edges)
 135 {
 136   xbt_edge_t ret;
 137
 138   const char *sn = instr_node_name(s);
 139   const char *dn = instr_node_name(d);
 140   int len = strlen(sn) + strlen(dn) + 1;
 141   char *name = (char *) xbt_malloc(len * sizeof(char));
 142
 143
 144   snprintf(name, len, "%s%s", sn, dn);
 145   ret = (xbt_edge_t) xbt_dict_get_or_null(edges, name);
 146   if (ret == NULL) {
 147     snprintf(name, len, "%s%s", dn, sn);
 148     ret = (xbt_edge_t) xbt_dict_get_or_null(edges, name);
 149   }
 150
 151   if (ret == NULL) {
 152     ret = xbt_graph_new_edge(graph, s, d, NULL);
 153     xbt_dict_set(edges, name, ret, NULL);
 154   }
 155   free(name);
 156   return ret;
 157 }
 158
 159 namespace simgrid {
 160 namespace surf {
 161
 162 void AsGeneric::getGraph(xbt_graph_t graph, xbt_dict_t nodes, xbt_dict_t edges)
 163 {
 164   int src, dst;
 165   int table_size = xbt_dynar_length(p_indexNetworkElm);
 166
 167
 168   for (src = 0; src < table_size; src++) {
 169     NetCard *my_src =
 170         xbt_dynar_get_as(p_indexNetworkElm, src, NetCard*);
 171     for (dst = 0; dst < table_size; dst++) {
 172       if (src == dst)
 173         continue;
 174       NetCard *my_dst =
 175           xbt_dynar_get_as(p_indexNetworkElm, dst, NetCard*);
 176
 177       sg_platf_route_cbarg_t route = xbt_new0(s_sg_platf_route_cbarg_t, 1);
 178       route->link_list = xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
 179
 180       getRouteAndLatency(my_src, my_dst, route, NULL);
 181
 182       XBT_DEBUG ("get_route_and_latency %s -> %s", my_src->getName(), my_dst->getName());
 183
 184       unsigned int cpt;
 185       void *link;
 186
 187       xbt_node_t current, previous;
 188       const char *previous_name, *current_name;
 189
 190       if (route->gw_src) {
 191         previous = new_xbt_graph_node(graph, route->gw_src->getName(), nodes);
 192         previous_name = route->gw_src->getName();
 193       } else {
 194         previous = new_xbt_graph_node(graph, my_src->getName(), nodes);
 195         previous_name = my_src->getName();
 196       }
 197
 198       xbt_dynar_foreach(route->link_list, cpt, link) {
 199         const char *link_name = static_cast<simgrid::surf::Resource*>(
 200           link)->getName();
 201         current = new_xbt_graph_node(graph, link_name, nodes);
 202         current_name = link_name;
 203         new_xbt_graph_edge(graph, previous, current, edges);
 204         XBT_DEBUG ("  %s -> %s", previous_name, current_name);
 205         previous = current;
 206         previous_name = current_name;
 207       }
 208
 209       if (route->gw_dst) {
 210         current = new_xbt_graph_node(graph, route->gw_dst->getName(), nodes);
 211         current_name = route->gw_dst->getName();
 212       } else {
 213         current = new_xbt_graph_node(graph, my_dst->getName(), nodes);
 214         current_name = my_dst->getName();
 215       }
 216       new_xbt_graph_edge(graph, previous, current, edges);
 217       XBT_DEBUG ("  %s -> %s", previous_name, current_name);
 218
 219       xbt_dynar_free (&(route->link_list));
 220       xbt_free (route);
 221     }
 222   }
 223 }
 224
 225 sg_platf_route_cbarg_t AsGeneric::getBypassRoute(NetCard *src,
 226                                                NetCard *dst,
 227                                                double *lat)
 228 {
 229   // If never set a bypass route return NULL without any further computations
 230   XBT_DEBUG("generic_get_bypassroute from %s to %s", src->getName(), dst->getName());
 231   if (no_bypassroute_declared)
 232     return NULL;
 233
 234   sg_platf_route_cbarg_t e_route_bypass = NULL;
 235   xbt_dict_t dict_bypassRoutes = p_bypassRoutes;
 236
 237   if(dst->getRcComponent() == this && src->getRcComponent() == this ){
 238     char *route_name = bprintf("%s#%s", src->getName(), dst->getName());
 239     e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 240     if(e_route_bypass)
 241       XBT_DEBUG("Find bypass route with %ld links",xbt_dynar_length(e_route_bypass->link_list));
 242     free(route_name);
 243   }
 244   else{
 245     As *src_as, *dst_as;
 246     int index_src, index_dst;
 247     xbt_dynar_t path_src = NULL;
 248     xbt_dynar_t path_dst = NULL;
 249     As *current = NULL;
 250     As **current_src = NULL;
 251     As **current_dst = NULL;
 252
 253     if (src == NULL || dst == NULL)
 254       xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
 255               src ? src->getName() : "(null)",
 256               dst ? dst->getName() : "(null)", p_name);
 257
 258     src_as = src->getRcComponent();
 259     dst_as = dst->getRcComponent();
 260
 261     /* (2) find the path to the root routing component */
 262     path_src = xbt_dynar_new(sizeof(As*), NULL);
 263     current = src_as;
 264     while (current != NULL) {
 265       xbt_dynar_push(path_src, &current);
 266       current = current->p_routingFather;
 267     }
 268     path_dst = xbt_dynar_new(sizeof(As*), NULL);
 269     current = dst_as;
 270     while (current != NULL) {
 271       xbt_dynar_push(path_dst, &current);
 272       current = current->p_routingFather;
 273     }
 274
 275     /* (3) find the common father */
 276     index_src = path_src->used - 1;
 277     index_dst = path_dst->used - 1;
 278     current_src = (As **) xbt_dynar_get_ptr(path_src, index_src);
 279     current_dst = (As **) xbt_dynar_get_ptr(path_dst, index_dst);
 280     while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
 281       xbt_dynar_pop_ptr(path_src);
 282       xbt_dynar_pop_ptr(path_dst);
 283       index_src--;
 284       index_dst--;
 285       current_src = (As **) xbt_dynar_get_ptr(path_src, index_src);
 286       current_dst = (As **) xbt_dynar_get_ptr(path_dst, index_dst);
 287     }
 288
 289     int max_index_src = path_src->used - 1;
 290     int max_index_dst = path_dst->used - 1;
 291
 292     int max_index = std::max(max_index_src, max_index_dst);
 293     int i, max;
 294
 295     for (max = 0; max <= max_index; max++) {
 296       for (i = 0; i < max; i++) {
 297         if (i <= max_index_src && max <= max_index_dst) {
 298           char *route_name = bprintf("%s#%s",
 299               (*(As **)
 300                   (xbt_dynar_get_ptr(path_src, i)))->p_name,
 301                   (*(As **)
 302                       (xbt_dynar_get_ptr(path_dst, max)))->p_name);
 303           e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 304           xbt_free(route_name);
 305         }
 306         if (e_route_bypass)
 307           break;
 308         if (max <= max_index_src && i <= max_index_dst) {
 309           char *route_name = bprintf("%s#%s",
 310               (*(As **)
 311                   (xbt_dynar_get_ptr(path_src, max)))->p_name,
 312                   (*(As **)
 313                       (xbt_dynar_get_ptr(path_dst, i)))->p_name);
 314           e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 315           xbt_free(route_name);
 316         }
 317         if (e_route_bypass)
 318           break;
 319       }
 320
 321       if (e_route_bypass)
 322         break;
 323
 324       if (max <= max_index_src && max <= max_index_dst) {
 325         char *route_name = bprintf("%s#%s",
 326             (*(As **)
 327                 (xbt_dynar_get_ptr(path_src, max)))->p_name,
 328                 (*(As **)
 329                     (xbt_dynar_get_ptr(path_dst, max)))->p_name);
 330         e_route_bypass = (sg_platf_route_cbarg_t) xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 331         xbt_free(route_name);
 332       }
 333       if (e_route_bypass)
 334         break;
 335     }
 336
 337     xbt_dynar_free(&path_src);
 338     xbt_dynar_free(&path_dst);
 339   }
 340
 341   sg_platf_route_cbarg_t new_e_route = NULL;
 342   if (e_route_bypass) {
 343     Link* link;
 344     unsigned int cpt = 0;
 345     new_e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1);
 346     new_e_route->gw_src = e_route_bypass->gw_src;
 347     new_e_route->gw_dst = e_route_bypass->gw_dst;
 348     new_e_route->link_list =
 349         xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
 350     xbt_dynar_foreach(e_route_bypass->link_list, cpt, link) {
 351       xbt_dynar_push(new_e_route->link_list, &link);
 352       if (lat)
 353         *lat += link->getLatency();
 354     }
 355   }
 356
 357   return new_e_route;
 358 }
 359
 360 /* ************************************************************************** */
 361 /* ************************* GENERIC AUX FUNCTIONS ************************** */
 362 /* change a route containing link names into a route containing link entities */
 363 sg_platf_route_cbarg_t AsGeneric::newExtendedRoute(e_surf_routing_hierarchy_t hierarchy,
 364       sg_platf_route_cbarg_t routearg, int change_order) {
 365
 366   sg_platf_route_cbarg_t result;
 367   char *link_name;
 368   unsigned int cpt;
 369
 370   result = xbt_new0(s_sg_platf_route_cbarg_t, 1);
 371   result->link_list = xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
 372
 373   xbt_assert(hierarchy == SURF_ROUTING_BASE
 374       || hierarchy == SURF_ROUTING_RECURSIVE,
 375       "The hierarchy of this AS is neither BASIC nor RECURSIVE, I'm lost here.");
 376
 377   if (hierarchy == SURF_ROUTING_RECURSIVE) {
 378
 379     xbt_assert(routearg->gw_src && routearg->gw_dst,
 380         "NULL is obviously a bad gateway");
 381
 382     /* remember not erase the gateway names */
 383     result->gw_src = routearg->gw_src;
 384     result->gw_dst = routearg->gw_dst;
 385   }
 386
 387   xbt_dynar_foreach(routearg->link_list, cpt, link_name) {
 388
 389     Link *link = Link::byName(link_name);
 390     if (link) {
 391       if (change_order)
 392         xbt_dynar_push(result->link_list, &link);
 393       else
 394         xbt_dynar_unshift(result->link_list, &link);
 395     } else
 396       THROWF(mismatch_error, 0, "Link '%s' not found", link_name);
 397   }
 398
 399   return result;
 400 }
 401
 402 void AsGeneric::srcDstCheck(NetCard *src, NetCard *dst)
 403 {
 404   if (src == NULL || dst == NULL)
 405     xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
 406             src ? src->getName() : "(null)",
 407             dst ? dst->getName() : "(null)",
 408             p_name);
 409
 410   As *src_as = src->getRcComponent();
 411   As *dst_as = dst->getRcComponent();
 412
 413   if (src_as != dst_as)
 414     xbt_die("The src(%s in %s) and dst(%s in %s) are in differents AS",
 415         src->getName(), src_as->p_name,
 416         dst->getName(), dst_as->p_name);
 417
 418   if (this != dst_as)
 419     xbt_die
 420     ("The routing component of src'%s' and dst'%s' is not the same as the network elements belong (%s?=%s?=%s)",
 421         src->getName(),
 422         dst->getName(),
 423         src_as->p_name,
 424         dst_as->p_name,
 425         p_name);
 426 }
 427
 428 }
 429 }