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