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