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