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 "simgrid/platf_interface.h"    // platform creation API internal interface
   8
   9 #include "surf_routing_private.h"
  10 #include "surf/surf_routing.h"
  11 #include "surf/surfxml_parse_values.h"
  12
  13 #include <pcre.h>               /* regular expression library */
  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, sg_routing_edge_t elm)
  42 {
  43   XBT_DEBUG("Load process unit \"%s\"", elm->name);
  44   xbt_dynar_push_as(as->index_network_elm,sg_routing_edge_t,elm);
  45   return xbt_dynar_length(as->index_network_elm)-1;
  46 }
  47
  48 int generic_parse_AS(AS_t as, sg_routing_edge_t elm)
  49 {
  50   XBT_DEBUG("Load Autonomous system \"%s\"", elm->name);
  51   xbt_dynar_push_as(as->index_network_elm,sg_routing_edge_t,elm);
  52   return xbt_dynar_length(as->index_network_elm)-1;
  53 }
  54
  55 void generic_parse_bypassroute(AS_t rc, sg_platf_route_cbarg_t e_route)
  56 {
  57   char *src = (char*)(e_route->src);
  58   char *dst = (char*)(e_route->dst);
  59
  60   if(e_route->gw_dst)
  61     XBT_DEBUG("Load bypassASroute from \"%s\" to \"%s\"", src, dst);
  62   else
  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->gw_src->name, dst, e_route->gw_dst->name);
  74
  75   sg_platf_route_cbarg_t new_e_route = NULL;
  76   if(e_route->gw_dst)
  77     new_e_route =  generic_new_extended_route(SURF_ROUTING_RECURSIVE, e_route, 1);
  78   else
  79     new_e_route =  generic_new_extended_route(SURF_ROUTING_BASE, e_route, 1);
  80
  81   xbt_dynar_free(&(e_route->link_list));
  82
  83   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route, NULL);
  84   no_bypassroute_declared = 0;
  85   xbt_free(route_name);
  86 }
  87
  88 /* ************************************************************************** */
  89 /* *********************** GENERIC BUSINESS METHODS ************************* */
  90
  91 xbt_dynar_t generic_get_onelink_routes(AS_t rc) { // FIXME: kill that stub
  92   xbt_die("\"generic_get_onelink_routes\" not implemented yet");
  93   return NULL;
  94 }
  95
  96 sg_platf_route_cbarg_t generic_get_bypassroute(AS_t rc, sg_routing_edge_t src, sg_routing_edge_t dst, double *lat)
  97 {
  98   // If never set a bypass route return NULL without any further computations
  99   XBT_DEBUG("generic_get_bypassroute from %s to %s",src->name,dst->name);
 100   if(no_bypassroute_declared)
 101     return NULL;
 102
 103   sg_platf_route_cbarg_t e_route_bypass = NULL;
 104   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
 105
 106   if(dst->rc_component == rc && src->rc_component == rc ){
 107     char *route_name = bprintf("%s#%s", src->name, dst->name);
 108     e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 109     if(e_route_bypass)
 110       XBT_DEBUG("Find bypass route with %ld links",xbt_dynar_length(e_route_bypass->link_list));
 111     free(route_name);
 112   }
 113   else{
 114     AS_t src_as, dst_as;
 115     int index_src, index_dst;
 116     xbt_dynar_t path_src = NULL;
 117     xbt_dynar_t path_dst = NULL;
 118     AS_t current = NULL;
 119     AS_t *current_src = NULL;
 120     AS_t *current_dst = NULL;
 121
 122     if (src == NULL || dst == NULL)
 123       xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
 124           src->name, dst->name, rc->name);
 125
 126     src_as = src->rc_component;
 127     dst_as = dst->rc_component;
 128
 129     /* (2) find the path to the root routing component */
 130     path_src = xbt_dynar_new(sizeof(AS_t), NULL);
 131     current = src_as;
 132     while (current != NULL) {
 133       xbt_dynar_push(path_src, &current);
 134       current = current->routing_father;
 135     }
 136     path_dst = xbt_dynar_new(sizeof(AS_t), NULL);
 137     current = dst_as;
 138     while (current != NULL) {
 139       xbt_dynar_push(path_dst, &current);
 140       current = current->routing_father;
 141     }
 142
 143     /* (3) find the common father */
 144     index_src = path_src->used - 1;
 145     index_dst = path_dst->used - 1;
 146     current_src = xbt_dynar_get_ptr(path_src, index_src);
 147     current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
 148     while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
 149       xbt_dynar_pop_ptr(path_src);
 150       xbt_dynar_pop_ptr(path_dst);
 151       index_src--;
 152       index_dst--;
 153       current_src = xbt_dynar_get_ptr(path_src, index_src);
 154       current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
 155     }
 156
 157     int max_index_src = path_src->used - 1;
 158     int max_index_dst = path_dst->used - 1;
 159
 160     int max_index = max(max_index_src, max_index_dst);
 161     int i, max;
 162
 163     for (max = 0; max <= max_index; max++) {
 164       for (i = 0; i < max; i++) {
 165         if (i <= max_index_src && max <= max_index_dst) {
 166           char *route_name = bprintf("%s#%s",
 167               (*(AS_t *)
 168                   (xbt_dynar_get_ptr(path_src, i)))->name,
 169                   (*(AS_t *)
 170                       (xbt_dynar_get_ptr(path_dst, max)))->name);
 171           e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 172           xbt_free(route_name);
 173         }
 174         if (e_route_bypass)
 175           break;
 176         if (max <= max_index_src && i <= max_index_dst) {
 177           char *route_name = bprintf("%s#%s",
 178               (*(AS_t *)
 179                   (xbt_dynar_get_ptr(path_src, max)))->name,
 180                   (*(AS_t *)
 181                       (xbt_dynar_get_ptr(path_dst, i)))->name);
 182           e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 183           xbt_free(route_name);
 184         }
 185         if (e_route_bypass)
 186           break;
 187       }
 188
 189       if (e_route_bypass)
 190         break;
 191
 192       if (max <= max_index_src && max <= max_index_dst) {
 193         char *route_name = bprintf("%s#%s",
 194             (*(AS_t *)
 195                 (xbt_dynar_get_ptr(path_src, max)))->name,
 196                 (*(AS_t *)
 197                     (xbt_dynar_get_ptr(path_dst, max)))->name);
 198         e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
 199         xbt_free(route_name);
 200       }
 201       if (e_route_bypass)
 202         break;
 203     }
 204
 205     xbt_dynar_free(&path_src);
 206     xbt_dynar_free(&path_dst);
 207   }
 208
 209   sg_platf_route_cbarg_t new_e_route = NULL;
 210   if (e_route_bypass) {
 211     void *link;
 212     unsigned int cpt = 0;
 213     new_e_route = xbt_new0(s_sg_platf_route_cbarg_t, 1);
 214     new_e_route->gw_src = e_route_bypass->gw_src;
 215     new_e_route->gw_dst = e_route_bypass->gw_dst;
 216     new_e_route->link_list =
 217         xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
 218     xbt_dynar_foreach(e_route_bypass->link_list, cpt, link) {
 219       xbt_dynar_push(new_e_route->link_list, &link);
 220       if (lat)
 221         *lat += surf_network_model->extension.network.get_link_latency(link);
 222     }
 223   }
 224
 225   return new_e_route;
 226 }
 227
 228 /* ************************************************************************** */
 229 /* ************************* GENERIC AUX FUNCTIONS ************************** */
 230 /* change a route containing link names into a route containing link entities */
 231 sg_platf_route_cbarg_t
 232 generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy,
 233     sg_platf_route_cbarg_t routearg, int change_order) {
 234
 235   sg_platf_route_cbarg_t result;
 236   char *link_name;
 237   unsigned int cpt;
 238
 239   result = xbt_new0(s_sg_platf_route_cbarg_t, 1);
 240   result->link_list = xbt_dynar_new(sizeof(sg_routing_link_t), NULL);
 241
 242   xbt_assert(hierarchy == SURF_ROUTING_BASE
 243       || hierarchy == SURF_ROUTING_RECURSIVE,
 244       "The hierarchy of this AS is neither BASIC nor RECURSIVE, I'm lost here.");
 245
 246   if (hierarchy == SURF_ROUTING_RECURSIVE) {
 247
 248     xbt_assert(routearg->gw_src && routearg->gw_dst,
 249         "NULL is obviously a bad gateway");
 250
 251     /* remeber not erase the gateway names */
 252     result->gw_src = routearg->gw_src;
 253     result->gw_dst = routearg->gw_dst;
 254   }
 255
 256   xbt_dynar_foreach(routearg->link_list, cpt, link_name) {
 257
 258     void *link = xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
 259     if (link) {
 260       if (change_order)
 261         xbt_dynar_push(result->link_list, &link);
 262       else
 263         xbt_dynar_unshift(result->link_list, &link);
 264     } else
 265       THROWF(mismatch_error, 0, "Link %s not found", link_name);
 266   }
 267
 268   return result;
 269 }
 270
 271 void generic_free_route(sg_platf_route_cbarg_t route)
 272 {
 273   if (route) {
 274     xbt_dynar_free(&route->link_list);
 275     xbt_free(route);
 276   }
 277 }
 278
 279 static AS_t generic_as_exist(AS_t find_from,
 280     AS_t to_find)
 281 {
 282   //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
 283   xbt_dict_cursor_t cursor = NULL;
 284   char *key;
 285   int found = 0;
 286   AS_t elem;
 287   xbt_dict_foreach(find_from->routing_sons, cursor, key, elem) {
 288     if (to_find == elem || generic_as_exist(elem, to_find)) {
 289       found = 1;
 290       break;
 291     }
 292   }
 293   if (found)
 294     return to_find;
 295   return NULL;
 296 }
 297
 298 AS_t
 299 generic_autonomous_system_exist(AS_t rc, char *element)
 300 {
 301   //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
 302   AS_t element_as, result, elem;
 303   xbt_dict_cursor_t cursor = NULL;
 304   char *key;
 305   element_as = ((sg_routing_edge_t)
 306       xbt_lib_get_or_null(as_router_lib, element,
 307           ROUTING_ASR_LEVEL))->rc_component;
 308   result = ((AS_t) - 1);
 309   if (element_as != rc)
 310     result = generic_as_exist(rc, element_as);
 311
 312   int found = 0;
 313   if (result) {
 314     xbt_dict_foreach(element_as->routing_sons, cursor, key, elem) {
 315       found = !strcmp(elem->name, element);
 316       if (found)
 317         break;
 318     }
 319     if (found)
 320       return element_as;
 321   }
 322   return NULL;
 323 }
 324
 325 AS_t
 326 generic_processing_units_exist(AS_t rc, char *element)
 327 {
 328   AS_t element_as;
 329   element_as = ((sg_routing_edge_t)
 330       xbt_lib_get_or_null(host_lib,
 331           element, ROUTING_HOST_LEVEL))->rc_component;
 332   if (element_as == rc)
 333     return element_as;
 334   return generic_as_exist(rc, element_as);
 335 }
 336
 337 void generic_src_dst_check(AS_t rc, sg_routing_edge_t src,
 338     sg_routing_edge_t dst)
 339 {
 340
 341   sg_routing_edge_t src_data = src;
 342   sg_routing_edge_t dst_data = dst;
 343
 344   if (src_data == NULL || dst_data == NULL)
 345     xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
 346         src->name,
 347         dst->name,
 348         rc->name);
 349
 350   AS_t src_as =
 351       (src_data)->rc_component;
 352   AS_t dst_as =
 353       (dst_data)->rc_component;
 354
 355   if (src_as != dst_as)
 356     xbt_die("The src(%s in %s) and dst(%s in %s) are in differents AS",
 357         src->name, src_as->name,
 358         dst->name, dst_as->name);
 359
 360   if (rc != dst_as)
 361     xbt_die
 362     ("The routing component of src'%s' and dst'%s' is not the same as the network elements belong (%s?=%s?=%s)",
 363         src->name,
 364         dst->name,
 365         src_as->name,
 366         dst_as->name,
 367         rc->name);
 368 }