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