src/surf/surf_routing_floyd.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 "surf_routing_private.h"
   8
   9 /* Global vars */
  10 extern routing_global_t global_routing;
  11
  12 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_floyd, surf, "Routing part of surf");
  13
  14 #define TO_FLOYD_COST(i,j) (as->cost_table)[(i)+(j)*table_size]
  15 #define TO_FLOYD_PRED(i,j) (as->predecessor_table)[(i)+(j)*table_size]
  16 #define TO_FLOYD_LINK(i,j) (as->link_table)[(i)+(j)*table_size]
  17
  18 /* Routing model structure */
  19
  20 typedef struct {
  21   s_as_t generic_routing;
  22   /* vars for calculate the floyd algorith. */
  23   int *predecessor_table;
  24   double *cost_table;
  25   route_t *link_table;
  26 } s_as_floyd_t, *as_floyd_t;
  27
  28 static void floyd_get_route(AS_t asg, const char *src, const char *dst, route_t res);
  29
  30 /* Business methods */
  31 static xbt_dynar_t floyd_get_onelink_routes(AS_t asg)
  32 {
  33   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
  34
  35   route_t route =   xbt_new0(s_route_t, 1);
  36   route->link_list = xbt_dynar_new(global_routing->size_of_link, NULL);
  37
  38   xbt_dict_cursor_t c1 = NULL, c2 = NULL;
  39   char *k1, *d1, *k2, *d2;
  40   xbt_dict_foreach(asg->to_index, c1, k1, d1) {
  41     xbt_dict_foreach(asg->to_index, c2, k2, d2) {
  42       xbt_dynar_reset(route->link_list);
  43       floyd_get_route(asg, k1, k2, route);
  44       if (xbt_dynar_length(route->link_list) == 1) {
  45         void *link = *(void **) xbt_dynar_get_ptr(route->link_list, 0);
  46         onelink_t onelink = xbt_new0(s_onelink_t, 1);
  47         onelink->link_ptr = link;
  48         if (asg->hierarchy == SURF_ROUTING_BASE) {
  49           onelink->src = xbt_strdup(k1);
  50           onelink->dst = xbt_strdup(k2);
  51         } else if (asg->hierarchy == SURF_ROUTING_RECURSIVE) {
  52           onelink->src = xbt_strdup(route->src_gateway);
  53           onelink->dst = xbt_strdup(route->dst_gateway);
  54         }
  55         xbt_dynar_push(ret, &onelink);
  56       }
  57     }
  58   }
  59   return ret;
  60 }
  61
  62 static void floyd_get_route(AS_t asg, const char *src, const char *dst, route_t res)
  63 {
  64
  65   /* set utils vars */
  66   as_floyd_t as = (as_floyd_t)asg;
  67   size_t table_size = xbt_dict_length(asg->to_index);
  68
  69   generic_src_dst_check(asg, src, dst);
  70   int *src_id = xbt_dict_get_or_null(asg->to_index, src);
  71   int *dst_id = xbt_dict_get_or_null(asg->to_index, dst);
  72   if (src_id == NULL || dst_id == NULL)
  73     THROWF(arg_error,0,"No route from '%s' to '%s'",src,dst);
  74
  75   /* create a result route */
  76
  77   int first = 1;
  78   int pred = *dst_id;
  79   int prev_pred = 0;
  80   char *gw_src = NULL, *gw_dst = NULL, *prev_gw_src, *first_gw = NULL;
  81   unsigned int cpt;
  82   void *link;
  83   xbt_dynar_t links;
  84
  85   do {
  86     prev_pred = pred;
  87     pred = TO_FLOYD_PRED(*src_id, pred);
  88     if (pred == -1)             /* if no pred in route -> no route to host */
  89       break;
  90     xbt_assert(TO_FLOYD_LINK(pred, prev_pred),
  91                 "Invalid link for the route between \"%s\" or \"%s\"", src,
  92                 dst);
  93
  94     prev_gw_src = gw_src;
  95
  96     route_t e_route = TO_FLOYD_LINK(pred, prev_pred);
  97     gw_src = e_route->src_gateway;
  98     gw_dst = e_route->dst_gateway;
  99
 100     if (first)
 101       first_gw = gw_dst;
 102
 103     if (asg->hierarchy == SURF_ROUTING_RECURSIVE && !first
 104         && strcmp(gw_dst, prev_gw_src)) {
 105       xbt_dynar_t e_route_as_to_as=NULL;
 106       routing_get_route_and_latency(gw_dst, prev_gw_src,&e_route_as_to_as,NULL);
 107       links = e_route_as_to_as;
 108       int pos = 0;
 109       xbt_dynar_foreach(links, cpt, link) {
 110         xbt_dynar_insert_at(res->link_list, pos, &link);
 111         pos++;
 112       }
 113     }
 114
 115     links = e_route->link_list;
 116     xbt_dynar_foreach(links, cpt, link) {
 117       xbt_dynar_unshift(res->link_list, &link);
 118     }
 119     first = 0;
 120
 121   } while (pred != *src_id);
 122   if (pred == -1)
 123     THROWF(arg_error,0,"No route from '%s' to '%s'",src,dst);
 124
 125   if (asg->hierarchy == SURF_ROUTING_RECURSIVE) {
 126     res->src_gateway = xbt_strdup(gw_src);
 127     res->dst_gateway = xbt_strdup(first_gw);
 128   }
 129 }
 130
 131 static void floyd_finalize(AS_t rc)
 132 {
 133   as_floyd_t as = (as_floyd_t) rc;
 134   int i, j;
 135   size_t table_size;
 136   if (as) {
 137     table_size = xbt_dict_length(as->generic_routing.to_index);
 138     /* Delete link_table */
 139     for (i = 0; i < table_size; i++)
 140       for (j = 0; j < table_size; j++)
 141         generic_free_route(TO_FLOYD_LINK(i, j));
 142     xbt_free(as->link_table);
 143     /* Delete bypass dict */
 144     xbt_dict_free(&as->generic_routing.bypassRoutes);
 145     /* Delete index dict */
 146     xbt_dict_free(&(as->generic_routing.to_index));
 147     /* Delete dictionary index dict, predecessor and links table */
 148     xbt_free(as->predecessor_table);
 149     /* Delete structure */
 150     xbt_free(rc);
 151   }
 152 }
 153
 154 AS_t model_floyd_create(void)
 155 {
 156   as_floyd_t new_component = (as_floyd_t)model_generic_create_sized(sizeof(s_as_floyd_t));
 157   new_component->generic_routing.parse_route = model_floyd_parse_route;
 158   new_component->generic_routing.parse_ASroute = model_floyd_parse_route;
 159   new_component->generic_routing.get_route = floyd_get_route;
 160   new_component->generic_routing.get_onelink_routes =
 161       floyd_get_onelink_routes;
 162   new_component->generic_routing.finalize = floyd_finalize;
 163   return (AS_t)new_component;
 164 }
 165
 166 void model_floyd_end(AS_t current_routing)
 167 {
 168
 169         as_floyd_t as =
 170           ((as_floyd_t) current_routing);
 171
 172         unsigned int i, j, a, b, c;
 173
 174         /* set the size of table routing */
 175         size_t table_size = xbt_dict_length(as->generic_routing.to_index);
 176
 177         if(!as->link_table)
 178         {
 179                 /* Create Cost, Predecessor and Link tables */
 180                 as->cost_table = xbt_new0(double, table_size * table_size);       /* link cost from host to host */
 181                 as->predecessor_table = xbt_new0(int, table_size * table_size);  /* predecessor host numbers */
 182                 as->link_table = xbt_new0(route_t, table_size * table_size);    /* actual link between src and dst */
 183
 184                 /* Initialize costs and predecessors */
 185                 for (i = 0; i < table_size; i++)
 186                 for (j = 0; j < table_size; j++) {
 187                   TO_FLOYD_COST(i, j) = DBL_MAX;
 188                   TO_FLOYD_PRED(i, j) = -1;
 189                   TO_FLOYD_LINK(i, j) = NULL;       /* fixed, missing in the previous version */
 190                 }
 191         }
 192
 193         /* Add the loopback if needed */
 194         if (current_routing->hierarchy == SURF_ROUTING_BASE) {
 195                 for (i = 0; i < table_size; i++) {
 196                   route_t e_route = TO_FLOYD_LINK(i, i);
 197                   if (!e_route) {
 198                         e_route = xbt_new0(s_route_t, 1);
 199                         e_route->src_gateway = NULL;
 200                         e_route->dst_gateway = NULL;
 201                         e_route->link_list =
 202                                 xbt_dynar_new(global_routing->size_of_link, NULL);
 203                         xbt_dynar_push(e_route->link_list, &global_routing->loopback);
 204                         TO_FLOYD_LINK(i, i) = e_route;
 205                         TO_FLOYD_PRED(i, i) = i;
 206                         TO_FLOYD_COST(i, i) = 1;
 207                   }
 208                 }
 209         }
 210         /* Calculate path costs */
 211         for (c = 0; c < table_size; c++) {
 212                 for (a = 0; a < table_size; a++) {
 213                   for (b = 0; b < table_size; b++) {
 214                         if (TO_FLOYD_COST(a, c) < DBL_MAX && TO_FLOYD_COST(c, b) < DBL_MAX) {
 215                           if (TO_FLOYD_COST(a, b) == DBL_MAX ||
 216                                   (TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b) <
 217                                    TO_FLOYD_COST(a, b))) {
 218                                 TO_FLOYD_COST(a, b) =
 219                                         TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b);
 220                                 TO_FLOYD_PRED(a, b) = TO_FLOYD_PRED(c, b);
 221                           }
 222                         }
 223                   }
 224                 }
 225         }
 226 }
 227
 228 static int surf_pointer_resource_cmp(const void *a, const void *b) {
 229   return a != b;
 230 }
 231
 232 //FIXME: kill dupplicates in next function with full routing
 233
 234 void model_floyd_parse_route(AS_t rc, const char *src,
 235         const char *dst, route_t route)
 236 {
 237         as_floyd_t as = (as_floyd_t) rc;
 238
 239         /* set the size of table routing */
 240         size_t table_size = xbt_dict_length(rc->to_index);
 241         int *src_id, *dst_id;
 242         int i,j;
 243
 244         src_id = xbt_dict_get_or_null(rc->to_index, src);
 245         dst_id = xbt_dict_get_or_null(rc->to_index, dst);
 246
 247         xbt_assert(src_id, "Network elements %s not found", src);
 248         xbt_assert(dst_id, "Network elements %s not found", dst);
 249
 250         if(!as->link_table)
 251         {
 252                 /* Create Cost, Predecessor and Link tables */
 253                 as->cost_table = xbt_new0(double, table_size * table_size);       /* link cost from host to host */
 254                 as->predecessor_table = xbt_new0(int, table_size * table_size);  /* predecessor host numbers */
 255                 as->link_table = xbt_new0(route_t, table_size * table_size);    /* actual link between src and dst */
 256
 257                 /* Initialize costs and predecessors */
 258                 for (i = 0; i < table_size; i++)
 259                 for (j = 0; j < table_size; j++) {
 260                   TO_FLOYD_COST(i, j) = DBL_MAX;
 261                   TO_FLOYD_PRED(i, j) = -1;
 262                   TO_FLOYD_LINK(i, j) = NULL;       /* fixed, missing in the previous version */
 263                 }
 264         }
 265
 266         if(TO_FLOYD_LINK(*src_id, *dst_id))
 267         {
 268                 if(!route->dst_gateway && !route->src_gateway)
 269                         XBT_DEBUG("See Route from \"%s\" to \"%s\"", src, dst);
 270                 else
 271                         XBT_DEBUG("See ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
 272                                  route->src_gateway, dst, route->dst_gateway);
 273                 char * link_name;
 274                 unsigned int cpt;
 275                 xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
 276                 xbt_dynar_foreach(route->link_list,cpt,link_name)
 277                 {
 278                         void *link = xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
 279                         xbt_assert(link,"Link : '%s' doesn't exists.",link_name);
 280                         xbt_dynar_push(link_route_to_test,&link);
 281                 }
 282                 xbt_assert(!xbt_dynar_compare(
 283                           (void*)TO_FLOYD_LINK(*src_id, *dst_id)->link_list,
 284                           (void*)link_route_to_test,
 285                           (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
 286                           "The route between \"%s\" and \"%s\" already exists", src,dst);
 287         }
 288         else
 289         {
 290                 if(!route->dst_gateway && !route->src_gateway)
 291                   XBT_DEBUG("Load Route from \"%s\" to \"%s\"", src, dst);
 292                 else{
 293                         XBT_DEBUG("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
 294                                  route->src_gateway, dst, route->dst_gateway);
 295                         if(routing_get_network_element_type((const char*)route->dst_gateway) == SURF_NETWORK_ELEMENT_NULL)
 296                                 xbt_die("The dst_gateway '%s' does not exist!",route->dst_gateway);
 297                         if(routing_get_network_element_type((const char*)route->src_gateway) == SURF_NETWORK_ELEMENT_NULL)
 298                                 xbt_die("The src_gateway '%s' does not exist!",route->src_gateway);
 299                 }
 300             TO_FLOYD_LINK(*src_id, *dst_id) =
 301                         generic_new_extended_route(rc->hierarchy, route, 1);
 302             TO_FLOYD_PRED(*src_id, *dst_id) = *src_id;
 303             TO_FLOYD_COST(*src_id, *dst_id) =
 304                         ((TO_FLOYD_LINK(*src_id, *dst_id))->link_list)->used;   /* count of links, old model assume 1 */
 305         }
 306
 307         if( A_surfxml_route_symmetrical == A_surfxml_route_symmetrical_YES
 308                 || A_surfxml_ASroute_symmetrical == A_surfxml_ASroute_symmetrical_YES )
 309         {
 310                 if(TO_FLOYD_LINK(*dst_id, *src_id))
 311                 {
 312                         if(!route->dst_gateway && !route->src_gateway)
 313                           XBT_DEBUG("See Route from \"%s\" to \"%s\"", dst, src);
 314                         else
 315                           XBT_DEBUG("See ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
 316                                          route->src_gateway, src, route->dst_gateway);
 317                         char * link_name;
 318                         unsigned int i;
 319                         xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
 320                         for(i=xbt_dynar_length(route->link_list) ;i>0 ;i--)
 321                         {
 322                                 link_name = xbt_dynar_get_as(route->link_list,i-1,void *);
 323                                 void *link = xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
 324                                 xbt_assert(link,"Link : '%s' doesn't exists.",link_name);
 325                                 xbt_dynar_push(link_route_to_test,&link);
 326                         }
 327                         xbt_assert(!xbt_dynar_compare(
 328                                   (void*)TO_FLOYD_LINK(*dst_id, *src_id)->link_list,
 329                               (void*)link_route_to_test,
 330                                   (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
 331                                   "The route between \"%s\" and \"%s\" already exists", src,dst);
 332                 }
 333                 else
 334                 {
 335                         if(route->dst_gateway && route->src_gateway)
 336                         {
 337                           char *gw_src = xbt_strdup(route->src_gateway);
 338                           char *gw_dst = xbt_strdup(route->dst_gateway);
 339                           route->src_gateway = gw_dst;
 340                           route->dst_gateway = gw_src;
 341                         }
 342
 343                         if(!route->dst_gateway && !route->src_gateway)
 344                           XBT_DEBUG("Load Route from \"%s\" to \"%s\"", dst, src);
 345                         else
 346                           XBT_DEBUG("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
 347                                          route->src_gateway, src, route->dst_gateway);
 348
 349                     TO_FLOYD_LINK(*dst_id, *src_id) =
 350                                 generic_new_extended_route(rc->hierarchy, route, 0);
 351                     TO_FLOYD_PRED(*dst_id, *src_id) = *dst_id;
 352                     TO_FLOYD_COST(*dst_id, *src_id) =
 353                                 ((TO_FLOYD_LINK(*dst_id, *src_id))->link_list)->used;   /* count of links, old model assume 1 */
 354                 }
 355         }
 356 }