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