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