src/surf/surf_routing_generic.c

   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 <pcre.h>               /* regular expression library */
   8
   9 #include "simgrid/platf_interface.h"    // platform creation API internal interface
  10
  11 #include "surf_routing_private.h"
  12 #include "surf/surf_routing.h"
  13 #include "surf/surfxml_parse_values.h"
  14
  15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_routing_generic, surf_route, "Generic implementation of the surf routing");
  16
  17 extern routing_component_t current_routing;
  18
  19 routing_component_t routmod_generic_create(size_t childsize) {
  20   routing_component_t new_component = xbt_malloc0(childsize);
  21
  22   new_component->parse_PU = generic_parse_PU;
  23   new_component->parse_AS = generic_parse_AS;
  24   new_component->parse_route = NULL;
  25   new_component->parse_ASroute = NULL;
  26   new_component->parse_bypassroute = generic_parse_bypassroute;
  27   new_component->get_route = NULL;
  28   new_component->get_latency = generic_get_link_latency;
  29   new_component->get_onelink_routes = NULL;
  30   new_component->get_bypass_route =
  31       generic_get_bypassroute;
  32   new_component->finalize = NULL;
  33   new_component->to_index = xbt_dict_new();
  34   new_component->bypassRoutes = xbt_dict_new();
  35   new_component->get_network_element_type = get_network_element_type;
  36
  37   return new_component;
  38 }
  39
  40
  41 void generic_parse_PU(routing_component_t rc, const char *name)
  42 {
  43   XBT_DEBUG("Load process unit \"%s\"", name);
  44   int *id = xbt_new0(int, 1);
  45   xbt_dict_t _to_index;
  46   _to_index = current_routing->to_index;
  47   *id = xbt_dict_length(_to_index);
  48   xbt_dict_set(_to_index, name, id, xbt_free);
  49 }
  50
  51 void generic_parse_AS(routing_component_t rc, const char *name)
  52 {
  53   XBT_DEBUG("Load Autonomous system \"%s\"", name);
  54   int *id = xbt_new0(int, 1);
  55   xbt_dict_t _to_index;
  56   _to_index = current_routing->to_index;
  57   *id = xbt_dict_length(_to_index);
  58   xbt_dict_set(_to_index, name, id, xbt_free);
  59 }
  60
  61 void generic_parse_bypassroute(routing_component_t rc,
  62                              const char *src, const char *dst,
  63                              route_extended_t e_route)
  64 {
  65   XBT_DEBUG("Load bypassRoute from \"%s\" to \"%s\"", src, dst);
  66   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
  67   char *route_name;
  68
  69   route_name = bprintf("%s#%s", src, dst);
  70   xbt_assert(xbt_dynar_length(e_route->generic_route.link_list) > 0,
  71              "Invalid count of links, must be greater than zero (%s,%s)",
  72              src, dst);
  73   xbt_assert(!xbt_dict_get_or_null(dict_bypassRoutes, route_name),
  74              "The bypass route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exists",
  75              src, e_route->src_gateway, dst, e_route->dst_gateway);
  76
  77   route_extended_t new_e_route =
  78       generic_new_extended_route(SURF_ROUTING_RECURSIVE, e_route, 0);
  79   xbt_dynar_free(&(e_route->generic_route.link_list));
  80   xbt_free(e_route);
  81
  82   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route,
  83                (void (*)(void *)) generic_free_extended_route);
  84   xbt_free(route_name);
  85 }
  86
  87 /* ************************************************************************** */
  88 /* *********************** GENERIC BUSINESS METHODS ************************* */
  89
  90 double generic_get_link_latency(routing_component_t rc,
  91                                 const char *src, const char *dst,
  92                                 route_extended_t route)
  93 {
  94   int need_to_clean = route ? 0 : 1;
  95   void *link;
  96   unsigned int i;
  97   double latency = 0.0;
  98
  99   route = route ? route : rc->get_route(rc, src, dst);
 100
 101   xbt_dynar_foreach(route->generic_route.link_list, i, link) {
 102     latency += surf_network_model->extension.network.get_link_latency(link);
 103   }
 104   if (need_to_clean)
 105     generic_free_extended_route(route);
 106   return latency;
 107 }
 108
 109 xbt_dynar_t generic_get_onelink_routes(routing_component_t rc)
 110 {
 111   xbt_die("\"generic_get_onelink_routes\" not implemented yet");
 112 }
 113
 114 route_extended_t generic_get_bypassroute(routing_component_t rc,
 115                                          const char *src, const char *dst)
 116 {
 117   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
 118   routing_component_t src_as, dst_as;
 119   int index_src, index_dst;
 120   xbt_dynar_t path_src = NULL;
 121   xbt_dynar_t path_dst = NULL;
 122   routing_component_t current = NULL;
 123   routing_component_t *current_src = NULL;
 124   routing_component_t *current_dst = NULL;
 125
 126   /* (1) find the as where the src and dst are located */
 127   void *src_data = xbt_lib_get_or_null(host_lib, src, ROUTING_HOST_LEVEL);
 128   void *dst_data = xbt_lib_get_or_null(host_lib, dst, ROUTING_HOST_LEVEL);
 129   if (!src_data)
 130     src_data = xbt_lib_get_or_null(as_router_lib, src, ROUTING_ASR_LEVEL);
 131   if (!dst_data)
 132     dst_data = xbt_lib_get_or_null(as_router_lib, dst, ROUTING_ASR_LEVEL);
 133
 134   if (src_data == NULL || dst_data == NULL)
 135     xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
 136             src, dst, rc->name);
 137
 138   src_as = ((network_element_info_t) src_data)->rc_component;
 139   dst_as = ((network_element_info_t) dst_data)->rc_component;
 140
 141   /* (2) find the path to the root routing component */
 142   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
 143   current = src_as;
 144   while (current != NULL) {
 145     xbt_dynar_push(path_src, &current);
 146     current = current->routing_father;
 147   }
 148   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
 149   current = dst_as;
 150   while (current != NULL) {
 151     xbt_dynar_push(path_dst, &current);
 152     current = current->routing_father;
 153   }
 154
 155   /* (3) find the common father */
 156   index_src = path_src->used - 1;
 157   index_dst = path_dst->used - 1;
 158   current_src = xbt_dynar_get_ptr(path_src, index_src);
 159   current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
 160   while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
 161     xbt_dynar_pop_ptr(path_src);
 162     xbt_dynar_pop_ptr(path_dst);
 163     index_src--;
 164     index_dst--;
 165     current_src = xbt_dynar_get_ptr(path_src, index_src);
 166     current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
 167   }
 168
 169   int max_index_src = path_src->used - 1;
 170   int max_index_dst = path_dst->used - 1;
 171
 172   int max_index = max(max_index_src, max_index_dst);
 173   int i, max;
 174
 175   route_extended_t e_route_bypass = NULL;
 176
 177   for (max = 0; max <= max_index; max++) {
 178     for (i = 0; i < max; i++) {
 179       if (i <= max_index_src && max <= max_index_dst) {
 180         char *route_name = bprintf("%s#%s",
 181                                    (*(routing_component_t *)
 182                                     (xbt_dynar_get_ptr(path_src, i)))->name,
 183                                    (*(routing_component_t *)
 184                                     (xbt_dynar_get_ptr(path_dst, max)))->name);
 185         e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 186         xbt_free(route_name);
 187       }
 188       if (e_route_bypass)
 189         break;
 190       if (max <= max_index_src && i <= max_index_dst) {
 191         char *route_name = bprintf("%s#%s",
 192                                    (*(routing_component_t *)
 193                                     (xbt_dynar_get_ptr(path_src, max)))->name,
 194                                    (*(routing_component_t *)
 195                                     (xbt_dynar_get_ptr(path_dst, i)))->name);
 196         e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 197         xbt_free(route_name);
 198       }
 199       if (e_route_bypass)
 200         break;
 201     }
 202
 203     if (e_route_bypass)
 204       break;
 205
 206     if (max <= max_index_src && max <= max_index_dst) {
 207       char *route_name = bprintf("%s#%s",
 208                                  (*(routing_component_t *)
 209                                   (xbt_dynar_get_ptr(path_src, max)))->name,
 210                                  (*(routing_component_t *)
 211                                   (xbt_dynar_get_ptr(path_dst, max)))->name);
 212       e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 213       xbt_free(route_name);
 214     }
 215     if (e_route_bypass)
 216       break;
 217   }
 218
 219   xbt_dynar_free(&path_src);
 220   xbt_dynar_free(&path_dst);
 221
 222   route_extended_t new_e_route = NULL;
 223
 224   if (e_route_bypass) {
 225     void *link;
 226     unsigned int cpt = 0;
 227     new_e_route = xbt_new0(s_route_extended_t, 1);
 228     new_e_route->src_gateway = xbt_strdup(e_route_bypass->src_gateway);
 229     new_e_route->dst_gateway = xbt_strdup(e_route_bypass->dst_gateway);
 230     new_e_route->generic_route.link_list =
 231         xbt_dynar_new(global_routing->size_of_link, NULL);
 232     xbt_dynar_foreach(e_route_bypass->generic_route.link_list, cpt, link) {
 233       xbt_dynar_push(new_e_route->generic_route.link_list, &link);
 234     }
 235   }
 236
 237   return new_e_route;
 238 }
 239
 240 /* ************************************************************************** */
 241 /* ************************* GENERIC AUX FUNCTIONS ************************** */
 242
 243 route_t
 244 generic_new_route(e_surf_routing_hierarchy_t hierarchy, void *data, int order)
 245 {
 246
 247   char *link_name;
 248   route_t new_route;
 249   unsigned int cpt;
 250   xbt_dynar_t links = NULL, links_id = NULL;
 251
 252   new_route = xbt_new0(s_route_t, 1);
 253   new_route->link_list = xbt_dynar_new(global_routing->size_of_link, NULL);
 254
 255   xbt_assert(hierarchy == SURF_ROUTING_BASE,
 256              "the hierarchy type is not SURF_ROUTING_BASE");
 257
 258   links = ((route_t) data)->link_list;
 259
 260
 261   links_id = new_route->link_list;
 262
 263   xbt_dynar_foreach(links, cpt, link_name) {
 264
 265     void *link = xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
 266     if (link) {
 267       if (order)
 268         xbt_dynar_push(links_id, &link);
 269       else
 270         xbt_dynar_unshift(links_id, &link);
 271     } else
 272       THROWF(mismatch_error, 0, "Link %s not found", link_name);
 273   }
 274
 275   return new_route;
 276 }
 277
 278 route_extended_t
 279 generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy,
 280                            void *data, int order)
 281 {
 282
 283   char *link_name;
 284   route_extended_t e_route, new_e_route;
 285   route_t route;
 286   unsigned int cpt;
 287   xbt_dynar_t links = NULL, links_id = NULL;
 288
 289   new_e_route = xbt_new0(s_route_extended_t, 1);
 290   new_e_route->generic_route.link_list =
 291       xbt_dynar_new(global_routing->size_of_link, NULL);
 292   new_e_route->src_gateway = NULL;
 293   new_e_route->dst_gateway = NULL;
 294
 295   xbt_assert(hierarchy == SURF_ROUTING_BASE
 296              || hierarchy == SURF_ROUTING_RECURSIVE,
 297              "the hierarchy type is not defined");
 298
 299   if (hierarchy == SURF_ROUTING_BASE) {
 300
 301     route = (route_t) data;
 302     links = route->link_list;
 303
 304   } else if (hierarchy == SURF_ROUTING_RECURSIVE) {
 305
 306     e_route = (route_extended_t) data;
 307     xbt_assert(e_route->src_gateway
 308                && e_route->dst_gateway, "bad gateway, is null");
 309     links = e_route->generic_route.link_list;
 310
 311     /* remeber not erase the gateway names */
 312     new_e_route->src_gateway = strdup(e_route->src_gateway);
 313     new_e_route->dst_gateway = strdup(e_route->dst_gateway);
 314   }
 315
 316   links_id = new_e_route->generic_route.link_list;
 317
 318   xbt_dynar_foreach(links, cpt, link_name) {
 319
 320     void *link = xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
 321     if (link) {
 322       if (order)
 323         xbt_dynar_push(links_id, &link);
 324       else
 325         xbt_dynar_unshift(links_id, &link);
 326     } else
 327       THROWF(mismatch_error, 0, "Link %s not found", link_name);
 328   }
 329
 330   return new_e_route;
 331 }
 332
 333 void generic_free_route(route_t route)
 334 {
 335   if (route) {
 336     xbt_dynar_free(&(route->link_list));
 337     xbt_free(route);
 338   }
 339 }
 340
 341 void generic_free_extended_route(route_extended_t e_route)
 342 {
 343   if (e_route) {
 344     xbt_dynar_free(&(e_route->generic_route.link_list));
 345     xbt_free(e_route->src_gateway);
 346     xbt_free(e_route->dst_gateway);
 347     xbt_free(e_route);
 348   }
 349 }
 350
 351 static routing_component_t generic_as_exist(routing_component_t find_from,
 352                                             routing_component_t to_find)
 353 {
 354   //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
 355   xbt_dict_cursor_t cursor = NULL;
 356   char *key;
 357   int found = 0;
 358   routing_component_t elem;
 359   xbt_dict_foreach(find_from->routing_sons, cursor, key, elem) {
 360     if (to_find == elem || generic_as_exist(elem, to_find)) {
 361       found = 1;
 362       break;
 363     }
 364   }
 365   if (found)
 366     return to_find;
 367   return NULL;
 368 }
 369
 370 routing_component_t
 371 generic_autonomous_system_exist(routing_component_t rc, char *element)
 372 {
 373   //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
 374   routing_component_t element_as, result, elem;
 375   xbt_dict_cursor_t cursor = NULL;
 376   char *key;
 377   element_as = ((network_element_info_t)
 378                 xbt_lib_get_or_null(as_router_lib, element,
 379                                     ROUTING_ASR_LEVEL))->rc_component;
 380   result = ((routing_component_t) - 1);
 381   if (element_as != rc)
 382     result = generic_as_exist(rc, element_as);
 383
 384   int found = 0;
 385   if (result) {
 386     xbt_dict_foreach(element_as->routing_sons, cursor, key, elem) {
 387       found = !strcmp(elem->name, element);
 388       if (found)
 389         break;
 390     }
 391     if (found)
 392       return element_as;
 393   }
 394   return NULL;
 395 }
 396
 397 routing_component_t
 398 generic_processing_units_exist(routing_component_t rc, char *element)
 399 {
 400   routing_component_t element_as;
 401   element_as = ((network_element_info_t)
 402                 xbt_lib_get_or_null(host_lib,
 403                                     element, ROUTING_HOST_LEVEL))->rc_component;
 404   if (element_as == rc)
 405     return element_as;
 406   return generic_as_exist(rc, element_as);
 407 }
 408
 409 void generic_src_dst_check(routing_component_t rc, const char *src,
 410                            const char *dst)
 411 {
 412
 413   void *src_data = xbt_lib_get_or_null(host_lib, src, ROUTING_HOST_LEVEL);
 414   void *dst_data = xbt_lib_get_or_null(host_lib, dst, ROUTING_HOST_LEVEL);
 415   if (!src_data)
 416     src_data = xbt_lib_get_or_null(as_router_lib, src, ROUTING_ASR_LEVEL);
 417   if (!dst_data)
 418     dst_data = xbt_lib_get_or_null(as_router_lib, dst, ROUTING_ASR_LEVEL);
 419
 420   if (src_data == NULL || dst_data == NULL)
 421     xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
 422             src, dst, rc->name);
 423
 424   routing_component_t src_as =
 425       ((network_element_info_t) src_data)->rc_component;
 426   routing_component_t dst_as =
 427       ((network_element_info_t) dst_data)->rc_component;
 428
 429   if (src_as != dst_as)
 430     xbt_die("The src(%s in %s) and dst(%s in %s) are in differents AS",
 431             src, src_as->name, dst, dst_as->name);
 432   if (rc != dst_as)
 433     xbt_die
 434         ("The routing component of src'%s' and dst'%s' is not the same as the network elements belong (%s?=%s?=%s)",
 435          src, dst, src_as->name, dst_as->name, rc->name);
 436 }