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