src/surf/surf_routing.c

   1 /* Copyright (c) 2009, 2010. 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 #include "surf_routing_private.h"
   9 #include "surf/surf_routing.h"
  10 #include "surf/surfxml_parse_values.h"
  11
  12 xbt_lib_t host_lib;
  13 int ROUTING_HOST_LEVEL; //Routing level
  14 int     SURF_CPU_LEVEL;         //Surf cpu level
  15 int SURF_WKS_LEVEL;             //Surf workstation level
  16 int SIMIX_HOST_LEVEL;   //Simix level
  17 int     MSG_HOST_LEVEL;         //Msg level
  18 int     SD_HOST_LEVEL;          //Simdag level
  19 int     COORD_HOST_LEVEL;       //Coordinates level
  20 int NS3_HOST_LEVEL;             //host node for ns3
  21
  22 xbt_lib_t link_lib;
  23 int SD_LINK_LEVEL;              //Simdag level
  24 int SURF_LINK_LEVEL;    //Surf level
  25 int NS3_LINK_LEVEL;             //link for ns3
  26
  27 xbt_lib_t as_router_lib;
  28 int ROUTING_ASR_LEVEL;  //Routing level
  29 int COORD_ASR_LEVEL;    //Coordinates level
  30 int NS3_ASR_LEVEL;              //host node for ns3
  31
  32 static xbt_dict_t patterns = NULL;
  33 static xbt_dict_t random_value = NULL;
  34
  35 /* Global vars */
  36 routing_global_t global_routing = NULL;
  37 routing_component_t current_routing = NULL;
  38 model_type_t current_routing_model = NULL;
  39
  40 /* global parse functions */
  41 xbt_dynar_t link_list = NULL;    /* temporary store of current list link of a route */
  42 static const char *src = NULL;        /* temporary store the source name of a route */
  43 static const char *dst = NULL;        /* temporary store the destination name of a route */
  44 static char *gw_src = NULL;     /* temporary store the gateway source name of a route */
  45 static char *gw_dst = NULL;     /* temporary store the gateway destination name of a route */
  46 static double_f_cpvoid_t get_link_latency = NULL;
  47
  48 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route, surf, "Routing part of surf");
  49
  50 static void routing_parse_Speer(void);          /* peer bypass */
  51 static void routing_parse_Srandom(void);        /* random bypass */
  52 static void routing_parse_Erandom(void);        /* random bypass */
  53
  54 static void routing_parse_Sconfig(void);        /* config Tag */
  55 static void routing_parse_Econfig(void);        /* config Tag */
  56
  57 static char* replace_random_parameter(char * chaine);
  58 static void clean_routing_after_parse(void);
  59
  60 /* this lines are only for replace use like index in the model table */
  61 typedef enum {
  62   SURF_MODEL_FULL = 0,
  63   SURF_MODEL_FLOYD,
  64   SURF_MODEL_DIJKSTRA,
  65   SURF_MODEL_DIJKSTRACACHE,
  66   SURF_MODEL_NONE,
  67   SURF_MODEL_RULEBASED,
  68   SURF_MODEL_VIVALDI,
  69   SURF_MODEL_CLUSTER
  70 } e_routing_types;
  71
  72 struct s_model_type routing_models[] = { {"Full",
  73                                           "Full routing data (fast, large memory requirements, fully expressive)",
  74                                           model_full_create,
  75                                           model_full_load,
  76                                           model_full_unload,
  77                                           model_full_end},
  78 {"Floyd",
  79  "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)",
  80  model_floyd_create, model_floyd_load, model_floyd_unload,
  81  model_floyd_end},
  82 {"Dijkstra",
  83  "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)",
  84  model_dijkstra_create, model_dijkstra_both_load,
  85  model_dijkstra_both_unload, model_dijkstra_both_end},
  86 {"DijkstraCache",
  87  "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)",
  88  model_dijkstracache_create, model_dijkstra_both_load,
  89  model_dijkstra_both_unload, model_dijkstra_both_end},
  90 {"none", "No routing (usable with Constant network only)",
  91  model_none_create, model_none_load, model_none_unload, model_none_end},
  92 {"RuleBased", "Rule-Based routing data (...)", model_rulebased_create,
  93  model_rulebased_load, model_rulebased_unload, model_rulebased_end},
  94 {"Vivaldi", "Vivaldi routing", model_rulebased_create,
  95   model_rulebased_load, model_rulebased_unload, model_rulebased_end},
  96 {"Cluster", "Cluster routing", model_cluster_create,
  97   model_cluster_load, model_cluster_unload, model_cluster_end},
  98 {NULL, NULL, NULL, NULL, NULL, NULL}
  99 };
 100
 101 static double euclidean_dist_comp(int index, xbt_dynar_t src, xbt_dynar_t dst)
 102 {
 103         double src_coord, dst_coord;
 104
 105         src_coord = atof(xbt_dynar_get_as(src, index, char *));
 106         dst_coord = atof(xbt_dynar_get_as(dst, index, char *));
 107
 108         return (src_coord-dst_coord)*(src_coord-dst_coord);
 109
 110 }
 111
 112 static double base_vivaldi_get_latency (const char *src, const char *dst)
 113 {
 114   double euclidean_dist;
 115   xbt_dynar_t src_ctn, dst_ctn;
 116   src_ctn = xbt_lib_get_or_null(host_lib, src, COORD_HOST_LEVEL);
 117   if(!src_ctn) src_ctn = xbt_lib_get_or_null(as_router_lib, src, COORD_ASR_LEVEL);
 118   dst_ctn = xbt_lib_get_or_null(host_lib, dst, COORD_HOST_LEVEL);
 119   if(!dst_ctn) dst_ctn = xbt_lib_get_or_null(as_router_lib, dst, COORD_ASR_LEVEL);
 120
 121   if(dst_ctn == NULL || src_ctn == NULL)
 122   xbt_die("Coord src '%s' :%p   dst '%s' :%p",src,src_ctn,dst,dst_ctn);
 123
 124   euclidean_dist = sqrt (euclidean_dist_comp(0,src_ctn,dst_ctn)+euclidean_dist_comp(1,src_ctn,dst_ctn))
 125                                  + fabs(atof(xbt_dynar_get_as(src_ctn, 2, char *)))+fabs(atof(xbt_dynar_get_as(dst_ctn, 2, char *)));
 126
 127   xbt_assert(euclidean_dist>=0, "Euclidean Dist is less than 0\"%s\" and \"%.2f\"", src, euclidean_dist);
 128
 129   //From .ms to .s
 130   return euclidean_dist / 1000;
 131 }
 132
 133 static double vivaldi_get_link_latency (routing_component_t rc,const char *src, const char *dst, route_extended_t e_route)
 134 {
 135   if(get_network_element_type(src) == SURF_NETWORK_ELEMENT_AS) {
 136           int need_to_clean = e_route?0:1;
 137           double latency;
 138           e_route = e_route?e_route:(*(rc->get_route)) (rc, src, dst);
 139           latency = base_vivaldi_get_latency(e_route->src_gateway,e_route->dst_gateway);
 140           if(need_to_clean) generic_free_extended_route(e_route);
 141           return latency;
 142   } else {
 143           return base_vivaldi_get_latency(src,dst);
 144   }
 145 }
 146
 147 /**
 148  * \brief Add a "host" to the network element list
 149  */
 150 static void parse_S_host(const char *host_id, const char* coord)
 151 {
 152   network_element_info_t info = NULL;
 153   if (current_routing->hierarchy == SURF_ROUTING_NULL)
 154     current_routing->hierarchy = SURF_ROUTING_BASE;
 155   xbt_assert(!xbt_lib_get_or_null(host_lib, host_id,ROUTING_HOST_LEVEL),
 156               "Reading a host, processing unit \"%s\" already exists",
 157               host_id);
 158   xbt_assert(current_routing->set_processing_unit,
 159               "no defined method \"set_processing_unit\" in \"%s\"",
 160               current_routing->name);
 161   (*(current_routing->set_processing_unit)) (current_routing, host_id);
 162   info = xbt_new0(s_network_element_info_t, 1);
 163   info->rc_component = current_routing;
 164   info->rc_type = SURF_NETWORK_ELEMENT_HOST;
 165   xbt_lib_set(host_lib,host_id,ROUTING_HOST_LEVEL,(void *) info);
 166   if (strcmp(coord,"")) {
 167         if(!COORD_HOST_LEVEL) xbt_die("To use coordinates, you must set configuration 'coordinates' to 'yes'");
 168     xbt_dynar_t ctn = xbt_str_split_str(coord, " ");
 169     xbt_dynar_shrink(ctn, 0);
 170     xbt_lib_set(host_lib,host_id,COORD_HOST_LEVEL,(void *) ctn);
 171   }
 172 }
 173
 174 static void parse_E_host(void)
 175 {
 176          xbt_dict_cursor_t cursor = NULL;
 177           char *key;
 178           char *elem;
 179
 180           xbt_dict_foreach(current_property_set, cursor, key, elem) {
 181                   XBT_DEBUG("property : %s = %s",key,elem);
 182                 }
 183 }
 184
 185 /*
 186  * \brief Add a host to the network element list from XML
 187  */
 188 static void parse_S_host_XML(void)
 189 {
 190         parse_S_host(A_surfxml_host_id, A_surfxml_host_coordinates);
 191 }
 192 static void parse_E_host_XML(void)
 193 {
 194         parse_E_host();
 195 }
 196
 197 /*
 198  * \brief Add a host to the network element list from lua script
 199  */
 200 static void parse_S_host_lua(const char *host_id, const char *coord)
 201 {
 202   parse_S_host(host_id, coord);
 203 }
 204
 205
 206 /**
 207  * \brief Add a "router" to the network element list
 208  */
 209 static void parse_S_router(void)
 210 {
 211   network_element_info_t info = NULL;
 212   if (current_routing->hierarchy == SURF_ROUTING_NULL)
 213     current_routing->hierarchy = SURF_ROUTING_BASE;
 214   xbt_assert(!xbt_lib_get_or_null(as_router_lib,struct_router->V_router_id, ROUTING_ASR_LEVEL),
 215               "Reading a router, processing unit \"%s\" already exists",
 216               struct_router->V_router_id);
 217   xbt_assert(current_routing->set_processing_unit,
 218               "no defined method \"set_processing_unit\" in \"%s\"",
 219               current_routing->name);
 220   (*(current_routing->set_processing_unit)) (current_routing,
 221                   struct_router->V_router_id);
 222   info = xbt_new0(s_network_element_info_t, 1);
 223   info->rc_component = current_routing;
 224   info->rc_type = SURF_NETWORK_ELEMENT_ROUTER;
 225
 226   xbt_lib_set(as_router_lib,struct_router->V_router_id,ROUTING_ASR_LEVEL,(void *) info);
 227   if (strcmp(A_surfxml_router_coordinates,"")) {
 228         if(!COORD_ASR_LEVEL) xbt_die("To use coordinates, you must set configuration 'coordinates' to 'yes'");
 229     xbt_dynar_t ctn = xbt_str_split_str(A_surfxml_router_coordinates, " ");
 230     xbt_dynar_shrink(ctn, 0);
 231     xbt_lib_set(as_router_lib,struct_router->V_router_id,COORD_ASR_LEVEL,(void *) ctn);
 232   }
 233 }
 234
 235 /**
 236  * brief Add a "router" to the network element list from XML description
 237  */
 238 static void parse_S_router_XML(void)
 239 {
 240         return parse_S_router();
 241 }
 242
 243 /**
 244  * brief Add a "router" to the network element list from XML description
 245  */
 246 static void parse_S_router_lua(const char* router_id)
 247 {
 248         struct_router->V_router_id = xbt_strdup(router_id);
 249         struct_router->V_router_coord = xbt_strdup("");
 250         return parse_S_router();
 251 }
 252
 253 /**
 254  * \brief Set the endponints for a route
 255  */
 256 static void parse_S_route_new_and_endpoints(const char *src_id, const char *dst_id)
 257 {
 258   if (src != NULL && dst != NULL && link_list != NULL)
 259     THROWF(arg_error, 0, "Route between %s to %s can not be defined",
 260            src_id, dst_id);
 261   src = src_id;
 262   dst = dst_id;
 263   xbt_assert(strlen(src) > 0 || strlen(dst) > 0,
 264               "Some limits are null in the route between \"%s\" and \"%s\"",
 265               src, dst);
 266   link_list = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
 267 }
 268
 269 /**
 270  * \brief Set the endpoints for a route from XML
 271  */
 272 static void parse_S_route_new_and_endpoints_XML(void)
 273 {
 274   parse_S_route_new_and_endpoints(A_surfxml_route_src,
 275                                   A_surfxml_route_dst);
 276 }
 277
 278 /**
 279  * \brief Set the endpoints for a route from lua
 280  */
 281 static void parse_S_route_new_and_endpoints_lua(const char *id_src, const char *id_dst)
 282 {
 283   parse_S_route_new_and_endpoints(id_src, id_dst);
 284 }
 285
 286 /**
 287  * \brief Set the endponints and gateways for a ASroute
 288  */
 289 static void parse_S_ASroute_new_and_endpoints(void)
 290 {
 291   if (src != NULL && dst != NULL && link_list != NULL)
 292     THROWF(arg_error, 0, "Route between %s to %s can not be defined",
 293            A_surfxml_ASroute_src, A_surfxml_ASroute_dst);
 294   src = A_surfxml_ASroute_src;
 295   dst = A_surfxml_ASroute_dst;
 296   gw_src = A_surfxml_ASroute_gw_src;
 297   gw_dst = A_surfxml_ASroute_gw_dst;
 298   xbt_assert(strlen(src) > 0 || strlen(dst) > 0 || strlen(gw_src) > 0
 299               || strlen(gw_dst) > 0,
 300               "Some limits are null in the route between \"%s\" and \"%s\"",
 301               src, dst);
 302   link_list = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
 303 }
 304
 305 /**
 306  * \brief Set the endponints for a bypassRoute
 307  */
 308 static void parse_S_bypassRoute_new_and_endpoints(void)
 309 {
 310   if (src != NULL && dst != NULL && link_list != NULL)
 311     THROWF(arg_error, 0,
 312            "Bypass Route between %s to %s can not be defined",
 313            A_surfxml_bypassRoute_src, A_surfxml_bypassRoute_dst);
 314   src = A_surfxml_bypassRoute_src;
 315   dst = A_surfxml_bypassRoute_dst;
 316   gw_src = A_surfxml_bypassRoute_gw_src;
 317   gw_dst = A_surfxml_bypassRoute_gw_dst;
 318   xbt_assert(strlen(src) > 0 || strlen(dst) > 0 || strlen(gw_src) > 0
 319               || strlen(gw_dst) > 0,
 320               "Some limits are null in the route between \"%s\" and \"%s\"",
 321               src, dst);
 322   link_list = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
 323 }
 324
 325 /**
 326  * \brief Set a new link on the actual list of link for a route or ASroute
 327  */
 328 static void parse_E_link_ctn_new_elem(const char *link_id)
 329 {
 330   char *val;
 331   val = xbt_strdup(link_id);
 332   xbt_dynar_push(link_list, &val);
 333 }
 334
 335 /**
 336  * \brief Set a new link on the actual list of link for a route or ASroute from XML
 337  */
 338
 339 static void parse_E_link_ctn_new_elem_XML(void)
 340 {
 341   if (A_surfxml_link_ctn_direction == A_surfxml_link_ctn_direction_NONE)
 342     parse_E_link_ctn_new_elem(A_surfxml_link_ctn_id);
 343   if (A_surfxml_link_ctn_direction == A_surfxml_link_ctn_direction_UP) {
 344     char *link_id = bprintf("%s_UP", A_surfxml_link_ctn_id);
 345     parse_E_link_ctn_new_elem(link_id);
 346     free(link_id);
 347   }
 348   if (A_surfxml_link_ctn_direction == A_surfxml_link_ctn_direction_DOWN) {
 349     char *link_id = bprintf("%s_DOWN", A_surfxml_link_ctn_id);
 350     parse_E_link_ctn_new_elem(link_id);
 351     free(link_id);
 352   }
 353 }
 354
 355 /**
 356  * \brief Set a new link on the actual list of link for a route or ASroute from lua
 357  */
 358 static void parse_E_link_c_ctn_new_elem_lua(const char *link_id)
 359 {
 360   parse_E_link_ctn_new_elem(link_id);
 361 }
 362
 363 /**
 364  * \brief Store the route by calling the set_route function of the current routing component
 365  */
 366 static void parse_E_route_store_route(void)
 367 {
 368   name_route_extended_t route = xbt_new0(s_name_route_extended_t, 1);
 369   route->generic_route.link_list = link_list;
 370   xbt_assert(current_routing->set_route,
 371               "no defined method \"set_route\" in \"%s\"",
 372               current_routing->name);
 373   (*(current_routing->set_route)) (current_routing, src, dst, route);
 374   link_list = NULL;
 375   src = NULL;
 376   dst = NULL;
 377 }
 378
 379 /**
 380  * \brief Store the ASroute by calling the set_ASroute function of the current routing component
 381  */
 382 static void parse_E_ASroute_store_route(void)
 383 {
 384   name_route_extended_t e_route = xbt_new0(s_name_route_extended_t, 1);
 385   e_route->generic_route.link_list = link_list;
 386   e_route->src_gateway = xbt_strdup(gw_src);
 387   e_route->dst_gateway = xbt_strdup(gw_dst);
 388   xbt_assert(current_routing->set_ASroute,
 389               "no defined method \"set_ASroute\" in \"%s\"",
 390               current_routing->name);
 391   (*(current_routing->set_ASroute)) (current_routing, src, dst, e_route);
 392   link_list = NULL;
 393   src = NULL;
 394   dst = NULL;
 395   gw_src = NULL;
 396   gw_dst = NULL;
 397 }
 398
 399 /**
 400  * \brief Store the bypass route by calling the set_bypassroute function of the current routing component
 401  */
 402 static void parse_E_bypassRoute_store_route(void)
 403 {
 404   route_extended_t e_route = xbt_new0(s_route_extended_t, 1);
 405   e_route->generic_route.link_list = link_list;
 406   e_route->src_gateway = xbt_strdup(gw_src);
 407   e_route->dst_gateway = xbt_strdup(gw_dst);
 408   xbt_assert(current_routing->set_bypassroute,
 409               "no defined method \"set_bypassroute\" in \"%s\"",
 410               current_routing->name);
 411   (*(current_routing->set_bypassroute)) (current_routing, src, dst,
 412                                          e_route);
 413   link_list = NULL;
 414   src = NULL;
 415   dst = NULL;
 416   gw_src = NULL;
 417   gw_dst = NULL;
 418 }
 419
 420 /**
 421  * \brief Make a new routing component
 422  *
 423  * make the new structure and
 424  * set the parsing functions to allows parsing the part of the routing tree
 425  */
 426 void routing_AS_init(const char *AS_id, const char *wanted_routing_type)
 427 {
 428   routing_component_t new_routing;
 429   model_type_t model = NULL;
 430   int cpt;
 431   /* search the routing model */
 432   for (cpt = 0; routing_models[cpt].name; cpt++)
 433     if (!strcmp(wanted_routing_type, routing_models[cpt].name))
 434       model = &routing_models[cpt];
 435   /* if its not exist, error */
 436   if (model == NULL) {
 437     fprintf(stderr, "Routing model %s not found. Existing models:\n",
 438             wanted_routing_type);
 439     for (cpt = 0; routing_models[cpt].name; cpt++)
 440         fprintf(stderr, "   %s: %s\n", routing_models[cpt].name,
 441                 routing_models[cpt].desc);
 442     xbt_die(NULL);
 443   }
 444
 445   /* make a new routing component */
 446   new_routing = (routing_component_t) (*(model->create)) ();
 447   new_routing->routing = model;
 448   new_routing->hierarchy = SURF_ROUTING_NULL;
 449   new_routing->name = xbt_strdup(AS_id);
 450   new_routing->routing_sons = xbt_dict_new();
 451
 452   /* Hack for Vivaldi */
 453   if(!strcmp(model->name,"Vivaldi"))
 454         new_routing->get_latency = vivaldi_get_link_latency;
 455
 456   if (current_routing == NULL && global_routing->root == NULL) {
 457
 458     /* it is the first one */
 459     new_routing->routing_father = NULL;
 460     global_routing->root = new_routing;
 461
 462   } else if (current_routing != NULL && global_routing->root != NULL) {
 463
 464     xbt_assert(!xbt_dict_get_or_null
 465                 (current_routing->routing_sons, AS_id),
 466                 "The AS \"%s\" already exists", AS_id);
 467     /* it is a part of the tree */
 468     new_routing->routing_father = current_routing;
 469     /* set the father behavior */
 470     if (current_routing->hierarchy == SURF_ROUTING_NULL)
 471       current_routing->hierarchy = SURF_ROUTING_RECURSIVE;
 472     /* add to the sons dictionary */
 473     xbt_dict_set(current_routing->routing_sons, AS_id,
 474                  (void *) new_routing, NULL);
 475     /* add to the father element list */
 476     (*(current_routing->set_autonomous_system)) (current_routing, AS_id);
 477     /* unload the prev parse rules */
 478     (*(current_routing->routing->unload)) ();
 479
 480   } else {
 481     THROWF(arg_error, 0, "All defined components must be belong to a AS");
 482   }
 483   /* set the new parse rules */
 484   (*(new_routing->routing->load)) ();
 485   /* set the new current component of the tree */
 486   current_routing = new_routing;
 487 }
 488
 489 /*
 490  * Detect the routing model type of the routing component from XML platforms
 491  */
 492 static void parse_S_AS(void)
 493 {
 494   routing_AS_init(A_surfxml_AS_id, A_surfxml_AS_routing);
 495 }
 496
 497
 498 /**
 499  * \brief Finish the creation of a new routing component
 500  *
 501  * When you finish to read the routing component, other structures must be created.
 502  * the "end" method allow to do that for any routing model type
 503  */
 504 void routing_AS_end(const char *AS_id)
 505 {
 506
 507   if (current_routing == NULL) {
 508     THROWF(arg_error, 0, "Close AS(%s), that were never opened", AS_id);
 509   } else {
 510     network_element_info_t info = NULL;
 511     xbt_assert(!xbt_lib_get_or_null(as_router_lib,current_routing->name, ROUTING_ASR_LEVEL),
 512                 "The AS \"%s\" already exists",current_routing->name);
 513     info = xbt_new0(s_network_element_info_t, 1);
 514     info->rc_component = current_routing->routing_father;
 515     info->rc_type = SURF_NETWORK_ELEMENT_AS;
 516     xbt_lib_set(as_router_lib,current_routing->name,ROUTING_ASR_LEVEL,(void *) info);
 517
 518     (*(current_routing->routing->unload)) ();
 519     (*(current_routing->routing->end)) ();
 520     current_routing = current_routing->routing_father;
 521     if (current_routing != NULL)
 522       (*(current_routing->routing->load)) ();
 523   }
 524 }
 525
 526 /*
 527  * \brief Finish the creation of a new routing component from XML
 528  */
 529 static void parse_E_AS(void)
 530 {
 531   routing_AS_end(A_surfxml_AS_id);
 532 }
 533
 534 /* Aux Business methods */
 535
 536 /**
 537  * \brief Get the AS name of the element
 538  *
 539  * \param name the host name
 540  *
 541  */
 542 static char* elements_As_name(const char *name)
 543 {
 544   routing_component_t as_comp;
 545
 546   /* (1) find the as where the host is located */
 547   as_comp = ((network_element_info_t)
 548             xbt_lib_get_or_null(host_lib,name, ROUTING_HOST_LEVEL))->rc_component;
 549   return as_comp->name;
 550 }
 551
 552
 553 /**
 554  * \brief Get the AS father and the first elements of the chain
 555  *
 556  * \param src the source host name
 557  * \param dst the destination host name
 558  *
 559  * Get the common father of the to processing units, and the first different
 560  * father in the chain
 561  */
 562 static void elements_father(const char *src, const char *dst,
 563                             routing_component_t *res_father,
 564                             routing_component_t *res_src,
 565                             routing_component_t *res_dst)
 566 {
 567   xbt_assert(src && dst, "bad parameters for \"elements_father\" method");
 568 #define ELEMENTS_FATHER_MAXDEPTH 16 /* increase if it is not enough */
 569   routing_component_t src_as, dst_as;
 570   routing_component_t path_src[ELEMENTS_FATHER_MAXDEPTH];
 571   routing_component_t path_dst[ELEMENTS_FATHER_MAXDEPTH];
 572   int index_src = 0;
 573   int index_dst = 0;
 574   routing_component_t current;
 575   routing_component_t current_src;
 576   routing_component_t current_dst;
 577   routing_component_t father;
 578
 579   /* (1) find the as where the src and dst are located */
 580   network_element_info_t src_data = xbt_lib_get_or_null(host_lib, src,
 581                                                         ROUTING_HOST_LEVEL);
 582   network_element_info_t dst_data = xbt_lib_get_or_null(host_lib, dst,
 583                                                         ROUTING_HOST_LEVEL);
 584   if (!src_data)
 585     src_data = xbt_lib_get_or_null(as_router_lib, src, ROUTING_ASR_LEVEL);
 586   if (!dst_data)
 587     dst_data = xbt_lib_get_or_null(as_router_lib, dst, ROUTING_ASR_LEVEL);
 588   src_as = src_data->rc_component;
 589   dst_as = dst_data->rc_component;
 590
 591   xbt_assert(src_as && dst_as,
 592              "Ask for route \"from\"(%s) or \"to\"(%s) no found", src, dst);
 593
 594   /* (2) find the path to the root routing component */
 595   for (current = src_as ; current != NULL ; current = current->routing_father) {
 596     if (index_src >= ELEMENTS_FATHER_MAXDEPTH)
 597       xbt_die("ELEMENTS_FATHER_MAXDEPTH should be increased for path_src");
 598     path_src[index_src++] = current;
 599   }
 600   for (current = dst_as ; current != NULL ; current = current->routing_father) {
 601     if (index_dst >= ELEMENTS_FATHER_MAXDEPTH)
 602       xbt_die("ELEMENTS_FATHER_MAXDEPTH should be increased for path_dst");
 603     path_dst[index_dst++] = current;
 604   }
 605
 606   /* (3) find the common father */
 607   do {
 608     current_src = path_src[--index_src];
 609     current_dst = path_dst[--index_dst];
 610   } while (index_src > 0 && index_dst > 0 && current_src == current_dst);
 611
 612   /* (4) they are not in the same routing component, make the path */
 613   if (current_src == current_dst)
 614     father = current_src;
 615   else
 616     father = path_src[index_src + 1];
 617
 618   /* (5) result generation */
 619   *res_father = father;         /* first the common father of src and dst */
 620   *res_src = current_src;       /* second the first different father of src */
 621   *res_dst = current_dst;       /* three  the first different father of dst */
 622
 623 #undef ELEMENTS_FATHER_MAXDEPTH
 624 }
 625
 626 /* Global Business methods */
 627
 628 /**
 629  * \brief Recursive function for get_route_latency
 630  *
 631  * \param src the source host name
 632  * \param dst the destination host name
 633  * \param *e_route the route where the links are stored
 634  * \param *latency the latency, if needed
 635  *
 636  * This function is called by "get_route" and "get_latency". It allows to walk
 637  * recursively through the routing components tree.
 638  */
 639 static void _get_route_latency(const char *src, const char *dst,
 640                                xbt_dynar_t *route, double *latency)
 641 {
 642   XBT_DEBUG("Solve route/latency  \"%s\" to \"%s\"", src, dst);
 643   xbt_assert(src && dst, "bad parameters for \"_get_route_latency\" method");
 644
 645   routing_component_t common_father;
 646   routing_component_t src_father;
 647   routing_component_t dst_father;
 648   elements_father(src, dst, &common_father, &src_father, &dst_father);
 649
 650   if (src_father == dst_father) { /* SURF_ROUTING_BASE */
 651
 652     route_extended_t e_route = NULL;
 653     if (route) {
 654       e_route = common_father->get_route(common_father, src, dst);
 655       xbt_assert(e_route, "no route between \"%s\" and \"%s\"", src, dst);
 656       *route = e_route->generic_route.link_list;
 657     }
 658     if (latency) {
 659       *latency = common_father->get_latency(common_father, src, dst, e_route);
 660       xbt_assert(*latency >= 0.0,
 661                  "latency error on route between \"%s\" and \"%s\"", src, dst);
 662     }
 663     if (e_route) {
 664       xbt_free(e_route->src_gateway);
 665       xbt_free(e_route->dst_gateway);
 666       xbt_free(e_route);
 667     }
 668
 669   } else {                      /* SURF_ROUTING_RECURSIVE */
 670
 671     route_extended_t e_route_bypass = NULL;
 672     if (common_father->get_bypass_route)
 673       e_route_bypass = common_father->get_bypass_route(common_father, src, dst);
 674
 675     xbt_assert(!latency || !e_route_bypass,
 676                "Bypass cannot work yet with get_latency");
 677
 678     route_extended_t e_route_cnt = e_route_bypass
 679       ? e_route_bypass
 680       : common_father->get_route(common_father,
 681                                src_father->name, dst_father->name);
 682
 683     xbt_assert(e_route_cnt, "no route between \"%s\" and \"%s\"",
 684                src_father->name, dst_father->name);
 685
 686     xbt_assert((e_route_cnt->src_gateway == NULL) ==
 687                (e_route_cnt->dst_gateway == NULL),
 688                "bad gateway for route between \"%s\" and \"%s\"", src, dst);
 689
 690     if (route) {
 691       *route = xbt_dynar_new(global_routing->size_of_link, NULL);
 692     }
 693     if (latency) {
 694       *latency = common_father->get_latency(common_father,
 695                                             src_father->name, dst_father->name,
 696                                             e_route_cnt);
 697       xbt_assert(*latency >= 0.0,
 698                  "latency error on route between \"%s\" and \"%s\"",
 699                  src_father->name, dst_father->name);
 700     }
 701
 702     void *link;
 703     unsigned int cpt;
 704
 705     if (strcmp(src, e_route_cnt->src_gateway)) {
 706       double latency_src;
 707       xbt_dynar_t route_src;
 708
 709       _get_route_latency(src, e_route_cnt->src_gateway,
 710                          (route ? &route_src : NULL),
 711                          (latency ? &latency_src : NULL));
 712       if (route) {
 713         xbt_assert(route_src, "no route between \"%s\" and \"%s\"",
 714                    src, e_route_cnt->src_gateway);
 715         xbt_dynar_foreach(route_src, cpt, link) {
 716           xbt_dynar_push(*route, &link);
 717         }
 718         xbt_dynar_free(&route_src);
 719       }
 720       if (latency) {
 721         xbt_assert(latency_src >= 0.0,
 722                    "latency error on route between \"%s\" and \"%s\"",
 723                    src, e_route_cnt->src_gateway);
 724         *latency += latency_src;
 725       }
 726     }
 727
 728     if (route) {
 729       xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
 730         xbt_dynar_push(*route, &link);
 731       }
 732     }
 733
 734     if (strcmp(e_route_cnt->dst_gateway, dst)) {
 735       double latency_dst;
 736       xbt_dynar_t route_dst;
 737
 738       _get_route_latency(e_route_cnt->dst_gateway, dst,
 739                          (route ? &route_dst : NULL),
 740                          (latency ? &latency_dst : NULL));
 741       if (route) {
 742         xbt_assert(route_dst, "no route between \"%s\" and \"%s\"",
 743                    e_route_cnt->dst_gateway, dst);
 744         xbt_dynar_foreach(route_dst, cpt, link) {
 745           xbt_dynar_push(*route, &link);
 746         }
 747         xbt_dynar_free(&route_dst);
 748       }
 749       if (latency) {
 750         xbt_assert(latency_dst >= 0.0,
 751                    "latency error on route between \"%s\" and \"%s\"",
 752                    e_route_cnt->dst_gateway, dst);
 753         *latency += latency_dst;
 754       }
 755     }
 756
 757     generic_free_extended_route(e_route_cnt);
 758   }
 759 }
 760
 761 /**
 762  * \brief Generic function for get_route, get_route_no_cleanup, and get_latency
 763  */
 764 static void get_route_latency(const char *src, const char *dst,
 765                               xbt_dynar_t *route, double *latency, int cleanup)
 766 {
 767   _get_route_latency(src, dst, route, latency);
 768   xbt_assert(!route || *route, "no route between \"%s\" and \"%s\"", src, dst);
 769   xbt_assert(!latency || *latency >= 0.0,
 770              "latency error on route between \"%s\" and \"%s\"", src, dst);
 771   if (route) {
 772     xbt_dynar_free(&global_routing->last_route);
 773     global_routing->last_route = cleanup ? *route : NULL;
 774   }
 775 }
 776
 777 /**
 778  * \brief Generic method: find a route between hosts
 779  *
 780  * \param src the source host name
 781  * \param dst the destination host name
 782  *
 783  * walk through the routing components tree and find a route between hosts
 784  * by calling the differents "get_route" functions in each routing component.
 785  * No need to free the returned dynar. It will be freed at the next call.
 786  */
 787 static xbt_dynar_t get_route(const char *src, const char *dst)
 788 {
 789   xbt_dynar_t route = NULL;
 790   get_route_latency(src, dst, &route, NULL, 1);
 791   return route;
 792 }
 793
 794 /**
 795  * \brief Generic method: find a route between hosts
 796  *
 797  * \param src the source host name
 798  * \param dst the destination host name
 799  *
 800  * same as get_route, but return NULL if any exception is raised.
 801  */
 802 static xbt_dynar_t get_route_or_null(const char *src, const char *dst)
 803 {
 804   xbt_dynar_t route = NULL;
 805   xbt_ex_t exception;
 806   TRY {
 807     get_route_latency(src, dst, &route, NULL, 1);
 808   }CATCH(exception) {
 809     xbt_ex_free(exception);
 810     return NULL;
 811   }
 812   return route;
 813 }
 814
 815 /**
 816  * \brief Generic method: find a route between hosts
 817  *
 818  * \param src the source host name
 819  * \param dst the destination host name
 820  *
 821  * walk through the routing components tree and find a route between hosts
 822  * by calling the differents "get_route" functions in each routing component.
 823  * Leaves the caller the responsability to clean the returned dynar.
 824  */
 825 static xbt_dynar_t get_route_no_cleanup(const char *src, const char *dst)
 826 {
 827   xbt_dynar_t route = NULL;
 828   get_route_latency(src, dst, &route, NULL, 0);
 829   return route;
 830 }
 831
 832 /*Get Latency*/
 833 static double get_latency(const char *src, const char *dst)
 834 {
 835   double latency = -1.0;
 836   get_route_latency(src, dst, NULL, &latency, 0);
 837   return latency;
 838 }
 839
 840 static int surf_parse_models_setup_already_called=0;
 841 /* Call the last initialization functions, that must be called after the
 842  * <config> tag, if any, and before the first of cluster|peer|AS|trace|trace_connect
 843  */
 844 void surf_parse_models_setup()
 845 {
 846   if (surf_parse_models_setup_already_called)
 847     return;
 848   surf_parse_models_setup_already_called=1;
 849   routing_parse_Erandom();
 850   surf_config_models_setup();
 851 }
 852
 853
 854 /**
 855  * \brief Recursive function for finalize
 856  *
 857  * \param rc the source host name
 858  *
 859  * This fuction is call by "finalize". It allow to finalize the
 860  * AS or routing components. It delete all the structures.
 861  */
 862 static void _finalize(routing_component_t rc)
 863 {
 864   if (rc) {
 865     xbt_dict_cursor_t cursor = NULL;
 866     char *key;
 867     routing_component_t elem;
 868     xbt_dict_foreach(rc->routing_sons, cursor, key, elem) {
 869       _finalize(elem);
 870     }
 871     xbt_dict_t tmp_sons = rc->routing_sons;
 872     char *tmp_name = rc->name;
 873     xbt_dict_free(&tmp_sons);
 874     xbt_free(tmp_name);
 875     xbt_assert(rc->finalize, "no defined method \"finalize\" in \"%s\"",
 876                 current_routing->name);
 877     (*(rc->finalize)) (rc);
 878   }
 879 }
 880
 881 /**
 882  * \brief Generic method: delete all the routing structures
 883  *
 884  * walk through the routing components tree and delete the structures
 885  * by calling the differents "finalize" functions in each routing component
 886  */
 887 static void finalize(void)
 888 {
 889   /* delete recursibly all the tree */
 890   _finalize(global_routing->root);
 891   /* delete last_route */
 892   xbt_dynar_free(&(global_routing->last_route));
 893   /* delete global routing structure */
 894   xbt_free(global_routing);
 895   /* make sure that we will reinit the models while loading the platf once reinited -- HACK but there is no proper surf_routing_init() */
 896   surf_parse_models_setup_already_called = 0;
 897 }
 898
 899 static xbt_dynar_t recursive_get_onelink_routes(routing_component_t rc)
 900 {
 901   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
 902
 903   //adding my one link routes
 904   unsigned int cpt;
 905   void *link;
 906   xbt_dynar_t onelink_mine = rc->get_onelink_routes(rc);
 907   if (onelink_mine) {
 908     xbt_dynar_foreach(onelink_mine, cpt, link) {
 909       xbt_dynar_push(ret, &link);
 910     }
 911   }
 912   //recursing
 913   char *key;
 914   xbt_dict_cursor_t cursor = NULL;
 915   routing_component_t rc_child;
 916   xbt_dict_foreach(rc->routing_sons, cursor, key, rc_child) {
 917     xbt_dynar_t onelink_child = recursive_get_onelink_routes(rc_child);
 918     if (onelink_child) {
 919       xbt_dynar_foreach(onelink_child, cpt, link) {
 920         xbt_dynar_push(ret, &link);
 921       }
 922     }
 923   }
 924   return ret;
 925 }
 926
 927 static xbt_dynar_t get_onelink_routes(void)
 928 {
 929   return recursive_get_onelink_routes(global_routing->root);
 930 }
 931
 932 e_surf_network_element_type_t get_network_element_type(const char
 933                                                               *name)
 934 {
 935   network_element_info_t rc = NULL;
 936
 937   rc = xbt_lib_get_or_null(host_lib, name, ROUTING_HOST_LEVEL);
 938   if(rc) return rc->rc_type;
 939
 940   rc = xbt_lib_get_or_null(as_router_lib, name, ROUTING_ASR_LEVEL);
 941   if(rc) return rc->rc_type;
 942
 943   return SURF_NETWORK_ELEMENT_NULL;
 944 }
 945
 946 /**
 947  * \brief Generic method: create the global routing schema
 948  *
 949  * Make a global routing structure and set all the parsing functions.
 950  */
 951 void routing_model_create(size_t size_of_links, void *loopback, double_f_cpvoid_t get_link_latency_fun)
 952 {
 953   /* config the uniq global routing */
 954   global_routing = xbt_new0(s_routing_global_t, 1);
 955   global_routing->root = NULL;
 956   global_routing->get_route = get_route;
 957   global_routing->get_route_or_null = get_route_or_null;
 958   global_routing->get_latency = get_latency;
 959   global_routing->get_route_no_cleanup = get_route_no_cleanup;
 960   global_routing->get_onelink_routes = get_onelink_routes;
 961   global_routing->get_route_latency = get_route_latency;
 962   global_routing->get_network_element_type = get_network_element_type;
 963   global_routing->finalize = finalize;
 964   global_routing->loopback = loopback;
 965   global_routing->size_of_link = size_of_links;
 966   global_routing->last_route = NULL;
 967   get_link_latency = get_link_latency_fun;
 968   /* no current routing at moment */
 969   current_routing = NULL;
 970
 971   /* parse generic elements */
 972   surfxml_add_callback(STag_surfxml_host_cb_list, &parse_S_host_XML);
 973   surfxml_add_callback(ETag_surfxml_host_cb_list, &parse_E_host_XML);
 974   surfxml_add_callback(STag_surfxml_router_cb_list, &parse_S_router_XML);
 975
 976   surfxml_add_callback(STag_surfxml_route_cb_list,
 977                        &parse_S_route_new_and_endpoints_XML);
 978   surfxml_add_callback(STag_surfxml_ASroute_cb_list,
 979                        &parse_S_ASroute_new_and_endpoints);
 980   surfxml_add_callback(STag_surfxml_bypassRoute_cb_list,
 981                        &parse_S_bypassRoute_new_and_endpoints);
 982
 983   surfxml_add_callback(ETag_surfxml_link_ctn_cb_list,
 984                        &parse_E_link_ctn_new_elem_XML);
 985
 986   surfxml_add_callback(ETag_surfxml_route_cb_list,
 987                        &parse_E_route_store_route);
 988   surfxml_add_callback(ETag_surfxml_ASroute_cb_list,
 989                        &parse_E_ASroute_store_route);
 990   surfxml_add_callback(ETag_surfxml_bypassRoute_cb_list,
 991                        &parse_E_bypassRoute_store_route);
 992
 993   surfxml_add_callback(STag_surfxml_AS_cb_list, &parse_S_AS);
 994   surfxml_add_callback(ETag_surfxml_AS_cb_list, &parse_E_AS);
 995
 996   surfxml_add_callback(STag_surfxml_cluster_cb_list,
 997                        &routing_parse_Scluster);
 998
 999   surfxml_add_callback(STag_surfxml_peer_cb_list,
1000                          &routing_parse_Speer);
1001
1002   surfxml_add_callback(ETag_surfxml_platform_cb_list,
1003                                                   &clean_routing_after_parse);
1004
1005 #ifdef HAVE_TRACING
1006   instr_routing_define_callbacks();
1007 #endif
1008 }
1009
1010 void surf_parse_add_callback_config(void)
1011 {
1012         surfxml_add_callback(STag_surfxml_config_cb_list, &routing_parse_Sconfig);
1013         surfxml_add_callback(ETag_surfxml_config_cb_list, &routing_parse_Econfig);
1014         surfxml_add_callback(STag_surfxml_prop_cb_list, &parse_properties_XML);
1015         surfxml_add_callback(STag_surfxml_random_cb_list, &routing_parse_Srandom);
1016 }
1017
1018 /* ************************************************** */
1019 /* ********** PATERN FOR NEW ROUTING **************** */
1020
1021 /* The minimal configuration of a new routing model need the next functions,
1022  * also you need to set at the start of the file, the new model in the model
1023  * list. Remember keep the null ending of the list.
1024  */
1025 /*** Routing model structure ***/
1026 // typedef struct {
1027 //   s_routing_component_t generic_routing;
1028 //   /* things that your routing model need */
1029 // } s_routing_component_NEW_t,*routing_component_NEW_t;
1030
1031 /*** Parse routing model functions ***/
1032 // static void model_NEW_set_processing_unit(routing_component_t rc, const char* name) {}
1033 // static void model_NEW_set_autonomous_system(routing_component_t rc, const char* name) {}
1034 // static void model_NEW_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {}
1035 // static void model_NEW_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t route) {}
1036 // static void model_NEW_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {}
1037
1038 /*** Business methods ***/
1039 // static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
1040 // static route_extended_t NEW_get_bypass_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
1041 // static void NEW_finalize(routing_component_t rc) { xbt_free(rc);}
1042
1043 /*** Creation routing model functions ***/
1044 // static void* model_NEW_create(void) {
1045 //   routing_component_NEW_t new_component =  xbt_new0(s_routing_component_NEW_t,1);
1046 //   new_component->generic_routing.set_processing_unit = model_NEW_set_processing_unit;
1047 //   new_component->generic_routing.set_autonomous_system = model_NEW_set_autonomous_system;
1048 //   new_component->generic_routing.set_route = model_NEW_set_route;
1049 //   new_component->generic_routing.set_ASroute = model_NEW_set_ASroute;
1050 //   new_component->generic_routing.set_bypassroute = model_NEW_set_bypassroute;
1051 //   new_component->generic_routing.get_route = NEW_get_route;
1052 //   new_component->generic_routing.get_bypass_route = NEW_get_bypass_route;
1053 //   new_component->generic_routing.finalize = NEW_finalize;
1054 //   /* initialization of internal structures */
1055 //   return new_component;
1056 // } /* mandatory */
1057 // static void  model_NEW_load(void) {}   /* mandatory */
1058 // static void  model_NEW_unload(void) {} /* mandatory */
1059 // static void  model_NEW_end(void) {}    /* mandatory */
1060
1061 /* ************************************************************************** */
1062 /* ************************* GENERIC PARSE FUNCTIONS ************************ */
1063
1064 void generic_set_processing_unit(routing_component_t rc,
1065                                         const char *name)
1066 {
1067   XBT_DEBUG("Load process unit \"%s\"", name);
1068   int *id = xbt_new0(int, 1);
1069   xbt_dict_t _to_index;
1070   _to_index = current_routing->to_index;
1071   *id = xbt_dict_length(_to_index);
1072   xbt_dict_set(_to_index, name, id, xbt_free);
1073 }
1074
1075 void generic_set_autonomous_system(routing_component_t rc,
1076                                           const char *name)
1077 {
1078   XBT_DEBUG("Load Autonomous system \"%s\"", name);
1079   int *id = xbt_new0(int, 1);
1080   xbt_dict_t _to_index;
1081   _to_index = current_routing->to_index;
1082   *id = xbt_dict_length(_to_index);
1083   xbt_dict_set(_to_index, name, id, xbt_free);
1084 }
1085
1086 int surf_pointer_resource_cmp(const void *a, const void *b)
1087 {
1088   return a != b;
1089 }
1090
1091 int surf_link_resource_cmp(const void *a, const void *b)
1092 {
1093   return !!memcmp(a,b,global_routing->size_of_link);
1094 }
1095
1096 void generic_set_bypassroute(routing_component_t rc,
1097                                     const char *src, const char *dst,
1098                                     route_extended_t e_route)
1099 {
1100   XBT_DEBUG("Load bypassRoute from \"%s\" to \"%s\"", src, dst);
1101   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
1102   char *route_name;
1103
1104   route_name = bprintf("%s#%s", src, dst);
1105   xbt_assert(xbt_dynar_length(e_route->generic_route.link_list) > 0,
1106               "Invalid count of links, must be greater than zero (%s,%s)",
1107               src, dst);
1108   xbt_assert(!xbt_dict_get_or_null(dict_bypassRoutes, route_name),
1109               "The bypass route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exists",
1110               src, e_route->src_gateway, dst, e_route->dst_gateway);
1111
1112   route_extended_t new_e_route =
1113       generic_new_extended_route(SURF_ROUTING_RECURSIVE, e_route, 0);
1114   xbt_dynar_free(&(e_route->generic_route.link_list));
1115   xbt_free(e_route);
1116
1117   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route,
1118                (void (*)(void *)) generic_free_extended_route);
1119   xbt_free(route_name);
1120 }
1121
1122 /* ************************************************************************** */
1123 /* *********************** GENERIC BUSINESS METHODS ************************* */
1124
1125 double generic_get_link_latency(routing_component_t rc,
1126                                        const char *src, const char *dst,
1127                                        route_extended_t route)
1128 {
1129         int need_to_clean = route?0:1;
1130         void * link;
1131         unsigned int i;
1132         double latency = 0.0;
1133
1134         route = route?route:rc->get_route(rc,src,dst);
1135
1136         xbt_dynar_foreach(route->generic_route.link_list,i,link) {
1137                 latency += get_link_latency(link);
1138         }
1139         if(need_to_clean) generic_free_extended_route(route);
1140   return latency;
1141 }
1142
1143 xbt_dynar_t generic_get_onelink_routes(routing_component_t rc)
1144 {
1145   xbt_die("\"generic_get_onelink_routes\" not implemented yet");
1146 }
1147
1148 route_extended_t generic_get_bypassroute(routing_component_t rc,
1149                                                 const char *src,
1150                                                 const char *dst)
1151 {
1152   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
1153   routing_component_t src_as, dst_as;
1154   int index_src, index_dst;
1155   xbt_dynar_t path_src = NULL;
1156   xbt_dynar_t path_dst = NULL;
1157   routing_component_t current = NULL;
1158   routing_component_t *current_src = NULL;
1159   routing_component_t *current_dst = NULL;
1160
1161   /* (1) find the as where the src and dst are located */
1162   void * src_data = xbt_lib_get_or_null(host_lib,src, ROUTING_HOST_LEVEL);
1163   void * dst_data = xbt_lib_get_or_null(host_lib,dst, ROUTING_HOST_LEVEL);
1164   if(!src_data) src_data = xbt_lib_get_or_null(as_router_lib,src, ROUTING_ASR_LEVEL);
1165   if(!dst_data) dst_data = xbt_lib_get_or_null(as_router_lib,dst, ROUTING_ASR_LEVEL);
1166
1167   if(src_data == NULL || dst_data == NULL)
1168           xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
1169                      src, dst, rc->name);
1170
1171   src_as = ((network_element_info_t)src_data)->rc_component;
1172   dst_as = ((network_element_info_t)dst_data)->rc_component;
1173
1174   /* (2) find the path to the root routing component */
1175   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
1176   current = src_as;
1177   while (current != NULL) {
1178     xbt_dynar_push(path_src, &current);
1179     current = current->routing_father;
1180   }
1181   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
1182   current = dst_as;
1183   while (current != NULL) {
1184     xbt_dynar_push(path_dst, &current);
1185     current = current->routing_father;
1186   }
1187
1188   /* (3) find the common father */
1189   index_src = path_src->used - 1;
1190   index_dst = path_dst->used - 1;
1191   current_src = xbt_dynar_get_ptr(path_src, index_src);
1192   current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
1193   while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
1194     xbt_dynar_pop_ptr(path_src);
1195     xbt_dynar_pop_ptr(path_dst);
1196     index_src--;
1197     index_dst--;
1198     current_src = xbt_dynar_get_ptr(path_src, index_src);
1199     current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
1200   }
1201
1202   int max_index_src = path_src->used - 1;
1203   int max_index_dst = path_dst->used - 1;
1204
1205   int max_index = max(max_index_src, max_index_dst);
1206   int i, max;
1207
1208   route_extended_t e_route_bypass = NULL;
1209
1210   for (max = 0; max <= max_index; max++) {
1211     for (i = 0; i < max; i++) {
1212       if (i <= max_index_src && max <= max_index_dst) {
1213         char *route_name = bprintf("%s#%s",
1214                                    (*(routing_component_t *)
1215                                     (xbt_dynar_get_ptr
1216                                      (path_src, i)))->name,
1217                                    (*(routing_component_t *)
1218                                     (xbt_dynar_get_ptr
1219                                      (path_dst, max)))->name);
1220         e_route_bypass =
1221             xbt_dict_get_or_null(dict_bypassRoutes, route_name);
1222         xbt_free(route_name);
1223       }
1224       if (e_route_bypass)
1225         break;
1226       if (max <= max_index_src && i <= max_index_dst) {
1227         char *route_name = bprintf("%s#%s",
1228                                    (*(routing_component_t *)
1229                                     (xbt_dynar_get_ptr
1230                                      (path_src, max)))->name,
1231                                    (*(routing_component_t *)
1232                                     (xbt_dynar_get_ptr
1233                                      (path_dst, i)))->name);
1234         e_route_bypass =
1235             xbt_dict_get_or_null(dict_bypassRoutes, route_name);
1236         xbt_free(route_name);
1237       }
1238       if (e_route_bypass)
1239         break;
1240     }
1241
1242     if (e_route_bypass)
1243       break;
1244
1245     if (max <= max_index_src && max <= max_index_dst) {
1246       char *route_name = bprintf("%s#%s",
1247                                  (*(routing_component_t *)
1248                                   (xbt_dynar_get_ptr
1249                                    (path_src, max)))->name,
1250                                  (*(routing_component_t *)
1251                                   (xbt_dynar_get_ptr
1252                                    (path_dst, max)))->name);
1253       e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
1254       xbt_free(route_name);
1255     }
1256     if (e_route_bypass)
1257       break;
1258   }
1259
1260   xbt_dynar_free(&path_src);
1261   xbt_dynar_free(&path_dst);
1262
1263   route_extended_t new_e_route = NULL;
1264
1265   if (e_route_bypass) {
1266     void *link;
1267     unsigned int cpt = 0;
1268     new_e_route = xbt_new0(s_route_extended_t, 1);
1269     new_e_route->src_gateway = xbt_strdup(e_route_bypass->src_gateway);
1270     new_e_route->dst_gateway = xbt_strdup(e_route_bypass->dst_gateway);
1271     new_e_route->generic_route.link_list =
1272         xbt_dynar_new(global_routing->size_of_link, NULL);
1273     xbt_dynar_foreach(e_route_bypass->generic_route.link_list, cpt, link) {
1274       xbt_dynar_push(new_e_route->generic_route.link_list, &link);
1275     }
1276   }
1277
1278   return new_e_route;
1279 }
1280
1281 /* ************************************************************************** */
1282 /* ************************* GENERIC AUX FUNCTIONS ************************** */
1283
1284 route_t
1285 generic_new_route(e_surf_routing_hierarchy_t hierarchy,
1286                            void *data, int order)
1287 {
1288
1289   char *link_name;
1290   route_t new_route;
1291   unsigned int cpt;
1292   xbt_dynar_t links = NULL, links_id = NULL;
1293
1294   new_route = xbt_new0(s_route_t, 1);
1295   new_route->link_list =
1296       xbt_dynar_new(global_routing->size_of_link, NULL);
1297
1298   xbt_assert(hierarchy == SURF_ROUTING_BASE,
1299               "the hierarchy type is not SURF_ROUTING_BASE");
1300
1301   links = ((route_t) data)->link_list;
1302
1303
1304   links_id = new_route->link_list;
1305
1306   xbt_dynar_foreach(links, cpt, link_name) {
1307
1308     void *link =
1309                 xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
1310     if (link) {
1311       if (order)
1312         xbt_dynar_push(links_id, &link);
1313       else
1314         xbt_dynar_unshift(links_id, &link);
1315     } else
1316       THROWF(mismatch_error, 0, "Link %s not found", link_name);
1317   }
1318
1319   return new_route;
1320 }
1321
1322 route_extended_t
1323 generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy,
1324                            void *data, int order)
1325 {
1326
1327   char *link_name;
1328   route_extended_t e_route, new_e_route;
1329   route_t route;
1330   unsigned int cpt;
1331   xbt_dynar_t links = NULL, links_id = NULL;
1332
1333   new_e_route = xbt_new0(s_route_extended_t, 1);
1334   new_e_route->generic_route.link_list =
1335       xbt_dynar_new(global_routing->size_of_link, NULL);
1336   new_e_route->src_gateway = NULL;
1337   new_e_route->dst_gateway = NULL;
1338
1339   xbt_assert(hierarchy == SURF_ROUTING_BASE
1340               || hierarchy == SURF_ROUTING_RECURSIVE,
1341               "the hierarchy type is not defined");
1342
1343   if (hierarchy == SURF_ROUTING_BASE) {
1344
1345     route = (route_t) data;
1346     links = route->link_list;
1347
1348   } else if (hierarchy == SURF_ROUTING_RECURSIVE) {
1349
1350     e_route = (route_extended_t) data;
1351     xbt_assert(e_route->src_gateway
1352                 && e_route->dst_gateway, "bad gateway, is null");
1353     links = e_route->generic_route.link_list;
1354
1355     /* remeber not erase the gateway names */
1356     new_e_route->src_gateway = strdup(e_route->src_gateway);
1357     new_e_route->dst_gateway = strdup(e_route->dst_gateway);
1358   }
1359
1360   links_id = new_e_route->generic_route.link_list;
1361
1362   xbt_dynar_foreach(links, cpt, link_name) {
1363
1364     void *link =
1365                 xbt_lib_get_or_null(link_lib, link_name, SURF_LINK_LEVEL);
1366     if (link) {
1367       if (order)
1368         xbt_dynar_push(links_id, &link);
1369       else
1370         xbt_dynar_unshift(links_id, &link);
1371     } else
1372       THROWF(mismatch_error, 0, "Link %s not found", link_name);
1373   }
1374
1375   return new_e_route;
1376 }
1377
1378 void generic_free_route(route_t route)
1379 {
1380   if (route) {
1381     xbt_dynar_free(&(route->link_list));
1382     xbt_free(route);
1383   }
1384 }
1385
1386 void generic_free_extended_route(route_extended_t e_route)
1387 {
1388   if (e_route) {
1389     xbt_dynar_free(&(e_route->generic_route.link_list));
1390     if (e_route->src_gateway)
1391       xbt_free(e_route->src_gateway);
1392     if (e_route->dst_gateway)
1393       xbt_free(e_route->dst_gateway);
1394     xbt_free(e_route);
1395   }
1396 }
1397
1398 static routing_component_t generic_as_exist(routing_component_t find_from,
1399                                             routing_component_t to_find)
1400 {
1401   //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
1402   xbt_dict_cursor_t cursor = NULL;
1403   char *key;
1404   int found = 0;
1405   routing_component_t elem;
1406   xbt_dict_foreach(find_from->routing_sons, cursor, key, elem) {
1407     if (to_find == elem || generic_as_exist(elem, to_find)) {
1408       found = 1;
1409       break;
1410     }
1411   }
1412   if (found)
1413     return to_find;
1414   return NULL;
1415 }
1416
1417 routing_component_t
1418 generic_autonomous_system_exist(routing_component_t rc, char *element)
1419 {
1420   //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
1421   routing_component_t element_as, result, elem;
1422   xbt_dict_cursor_t cursor = NULL;
1423   char *key;
1424   element_as = ((network_element_info_t)
1425                 xbt_lib_get_or_null(as_router_lib, element, ROUTING_ASR_LEVEL))->rc_component;
1426   result = ((routing_component_t) - 1);
1427   if (element_as != rc)
1428     result = generic_as_exist(rc, element_as);
1429
1430   int found = 0;
1431   if (result) {
1432     xbt_dict_foreach(element_as->routing_sons, cursor, key, elem) {
1433       found = !strcmp(elem->name, element);
1434       if (found)
1435         break;
1436     }
1437     if (found)
1438       return element_as;
1439   }
1440   return NULL;
1441 }
1442
1443 routing_component_t
1444 generic_processing_units_exist(routing_component_t rc, char *element)
1445 {
1446   routing_component_t element_as;
1447   element_as = ((network_element_info_t)
1448                 xbt_lib_get_or_null(host_lib,
1449                  element, ROUTING_HOST_LEVEL))->rc_component;
1450   if (element_as == rc)
1451     return element_as;
1452   return generic_as_exist(rc, element_as);
1453 }
1454
1455 void generic_src_dst_check(routing_component_t rc, const char *src,
1456                                   const char *dst)
1457 {
1458
1459   void * src_data = xbt_lib_get_or_null(host_lib,src, ROUTING_HOST_LEVEL);
1460   void * dst_data = xbt_lib_get_or_null(host_lib,dst, ROUTING_HOST_LEVEL);
1461   if(!src_data) src_data = xbt_lib_get_or_null(as_router_lib,src, ROUTING_ASR_LEVEL);
1462   if(!dst_data) dst_data = xbt_lib_get_or_null(as_router_lib,dst, ROUTING_ASR_LEVEL);
1463
1464   if(src_data == NULL || dst_data == NULL)
1465           xbt_die("Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
1466                      src, dst, rc->name);
1467
1468   routing_component_t src_as = ((network_element_info_t)src_data)->rc_component;
1469   routing_component_t dst_as = ((network_element_info_t)dst_data)->rc_component;
1470
1471   if(src_as != dst_as)
1472           xbt_die("The src(%s in %s) and dst(%s in %s) are in differents AS",
1473               src, src_as->name, dst, dst_as->name);
1474   if(rc != dst_as)
1475          xbt_die("The routing component of src'%s' and dst'%s' is not the same as the network elements belong (%s?=%s?=%s)",
1476      src,dst,src_as->name, dst_as->name,rc->name);
1477 }
1478
1479 static void routing_parse_Sconfig(void)
1480 {
1481   XBT_DEBUG("START configuration name = %s",A_surfxml_config_id);
1482 }
1483
1484 static void routing_parse_Econfig(void)
1485 {
1486   xbt_dict_cursor_t cursor = NULL;
1487   char *key;
1488   char *elem;
1489   char *cfg;
1490   xbt_dict_foreach(current_property_set, cursor, key, elem) {
1491           cfg = bprintf("%s:%s",key,elem);
1492           if(xbt_cfg_is_default_value(_surf_cfg_set, key))
1493                   xbt_cfg_set_parse(_surf_cfg_set, cfg);
1494           else
1495                   XBT_INFO("The custom configuration '%s' is already defined by user!",key);
1496           free(cfg);
1497   }
1498   XBT_DEBUG("End configuration name = %s",A_surfxml_config_id);
1499 }
1500
1501 void routing_parse_Scluster(void)
1502 {
1503   static int AX_ptr = 0;
1504   char *host_id, *groups, *link_id = NULL;
1505   char *availability_file = xbt_strdup(A_surfxml_cluster_availability_file);
1506   char *state_file = xbt_strdup(A_surfxml_cluster_state_file);
1507
1508   if(xbt_dict_size(patterns)==0)
1509           patterns = xbt_dict_new();
1510
1511   xbt_dict_set(patterns,"id",struct_cluster->V_cluster_id,NULL);
1512   xbt_dict_set(patterns,"prefix",struct_cluster->V_cluster_prefix,NULL);
1513   xbt_dict_set(patterns,"suffix",struct_cluster->V_cluster_suffix,NULL);
1514
1515   char *route_src_dst;
1516   unsigned int iter;
1517   int start, end, i;
1518   xbt_dynar_t radical_elements;
1519   xbt_dynar_t radical_ends;
1520   int cluster_sharing_policy = AX_surfxml_cluster_sharing_policy;
1521   int cluster_bb_sharing_policy = AX_surfxml_cluster_bb_sharing_policy;
1522
1523   static unsigned int surfxml_buffer_stack_stack_ptr = 1;
1524   static unsigned int surfxml_buffer_stack_stack[1024];
1525
1526   surfxml_buffer_stack_stack[0] = 0;
1527
1528   surfxml_bufferstack_push(1);
1529
1530   SURFXML_BUFFER_SET(AS_id, struct_cluster->V_cluster_id);
1531   SURFXML_BUFFER_SET(AS_routing, "RuleBased");
1532   XBT_DEBUG("<AS id=\"%s\"\trouting=\"RuleBased\">", struct_cluster->V_cluster_id);
1533   SURFXML_START_TAG(AS);
1534
1535   radical_elements = xbt_str_split(struct_cluster->V_cluster_radical, ",");
1536   xbt_dynar_foreach(radical_elements, iter, groups) {
1537     radical_ends = xbt_str_split(groups, "-");
1538     switch (xbt_dynar_length(radical_ends)) {
1539     case 1:
1540       surf_parse_get_int(&start, xbt_dynar_get_as(radical_ends, 0, char *));
1541       host_id = bprintf("%s%d%s", struct_cluster->V_cluster_prefix, start, struct_cluster->V_cluster_suffix);
1542       link_id = bprintf("%s_link_%d", struct_cluster->V_cluster_id, start);
1543       xbt_dict_set(patterns, "radical", bprintf("%d", start), xbt_free);
1544       A_surfxml_host_state = A_surfxml_host_state_ON;
1545
1546       XBT_DEBUG("<host\tid=\"%s\"\tpower=\"%s\">", host_id, struct_cluster->S_cluster_power);
1547       SURFXML_BUFFER_SET(host_id, host_id);
1548       SURFXML_BUFFER_SET(host_power, struct_cluster->S_cluster_power);
1549
1550       if(!strcmp(A_surfxml_cluster_availability_file,"")){
1551                   char* tmp_availability_file = xbt_strdup(availability_file);
1552                   xbt_str_varsubst(tmp_availability_file,patterns);
1553                   XBT_DEBUG("\tavailability_file=\"%s\"",tmp_availability_file);
1554               SURFXML_BUFFER_SET(host_availability_file, tmp_availability_file);
1555               xbt_free(tmp_availability_file);
1556       }
1557       else
1558       {
1559                   XBT_DEBUG("\tavailability_file=\"\"");
1560                   SURFXML_BUFFER_SET(host_availability_file, "");
1561       }
1562       if(!strcmp(A_surfxml_cluster_state_file,"")){
1563                   char *tmp_state_file = xbt_strdup(state_file);
1564                   xbt_str_varsubst(tmp_state_file,patterns);
1565                   XBT_DEBUG("\tstate_file=\"%s\"",tmp_state_file);
1566               SURFXML_BUFFER_SET(host_state_file, tmp_state_file);
1567               xbt_free(tmp_state_file);
1568       }
1569       else
1570       {
1571           XBT_DEBUG("\tstate_file=\"\"");
1572           SURFXML_BUFFER_SET(host_state_file, "");
1573       }
1574
1575       SURFXML_BUFFER_SET(host_core, struct_cluster->S_cluster_core);
1576       SURFXML_BUFFER_SET(host_availability, "1.0");
1577       SURFXML_BUFFER_SET(host_coordinates, "");
1578       SURFXML_START_TAG(host);
1579       SURFXML_END_TAG(host);
1580       XBT_DEBUG("</host>");
1581
1582       A_surfxml_link_state = A_surfxml_link_state_ON;
1583       A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
1584       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
1585           {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
1586       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
1587           {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
1588
1589       XBT_DEBUG("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id,struct_cluster->S_cluster_bw, struct_cluster->S_cluster_lat);
1590
1591       SURFXML_BUFFER_SET(link_id, link_id);
1592       SURFXML_BUFFER_SET(link_bandwidth, struct_cluster->S_cluster_bw);
1593       SURFXML_BUFFER_SET(link_latency, struct_cluster->S_cluster_lat);
1594       SURFXML_BUFFER_SET(link_bandwidth_file, "");
1595       SURFXML_BUFFER_SET(link_latency_file, "");
1596       SURFXML_BUFFER_SET(link_state_file, "");
1597       SURFXML_START_TAG(link);
1598       SURFXML_END_TAG(link);
1599
1600       free(link_id);
1601       free(host_id);
1602       break;
1603
1604     case 2:
1605
1606       surf_parse_get_int(&start,
1607                          xbt_dynar_get_as(radical_ends, 0, char *));
1608       surf_parse_get_int(&end, xbt_dynar_get_as(radical_ends, 1, char *));
1609       for (i = start; i <= end; i++) {
1610                   host_id = bprintf("%s%d%s", struct_cluster->V_cluster_prefix, i, struct_cluster->V_cluster_suffix);
1611                   link_id = bprintf("%s_link_%d", struct_cluster->V_cluster_id, i);
1612                   xbt_dict_set(patterns, "radical", bprintf("%d", i), xbt_free);
1613                   A_surfxml_host_state = A_surfxml_host_state_ON;
1614
1615               XBT_DEBUG("<host\tid=\"%s\"\tpower=\"%s\">", host_id, struct_cluster->S_cluster_power);
1616               SURFXML_BUFFER_SET(host_id, host_id);
1617               SURFXML_BUFFER_SET(host_power, struct_cluster->S_cluster_power);
1618
1619               if(!strcmp(A_surfxml_cluster_availability_file,"")){
1620                           char* tmp_availability_file = xbt_strdup(availability_file);
1621                           xbt_str_varsubst(tmp_availability_file,patterns);
1622                           XBT_DEBUG("\tavailability_file=\"%s\"",tmp_availability_file);
1623                       SURFXML_BUFFER_SET(host_availability_file, tmp_availability_file);
1624                       xbt_free(tmp_availability_file);
1625               }
1626               else
1627               {
1628                           XBT_DEBUG("\tavailability_file=\"\"");
1629                           SURFXML_BUFFER_SET(host_availability_file, "");
1630               }
1631               if(!strcmp(A_surfxml_cluster_state_file,"")){
1632                           char *tmp_state_file = xbt_strdup(state_file);
1633                           xbt_str_varsubst(tmp_state_file,patterns);
1634                           XBT_DEBUG("\tstate_file=\"%s\"",tmp_state_file);
1635                       SURFXML_BUFFER_SET(host_state_file, tmp_state_file);
1636                       xbt_free(tmp_state_file);
1637               }
1638               else
1639               {
1640                   XBT_DEBUG("\tstate_file=\"\"");
1641                   SURFXML_BUFFER_SET(host_state_file, "");
1642               }
1643
1644               SURFXML_BUFFER_SET(host_core, struct_cluster->S_cluster_core);
1645               SURFXML_BUFFER_SET(host_availability, "1.0");
1646               SURFXML_BUFFER_SET(host_coordinates, "");
1647               SURFXML_START_TAG(host);
1648               SURFXML_END_TAG(host);
1649               XBT_DEBUG("</host>");
1650
1651                   A_surfxml_link_state = A_surfxml_link_state_ON;
1652                   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
1653                   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
1654                   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
1655                   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
1656                   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
1657
1658                   XBT_DEBUG("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id,struct_cluster->S_cluster_bw, struct_cluster->S_cluster_lat);
1659
1660                   SURFXML_BUFFER_SET(link_id, link_id);
1661                   SURFXML_BUFFER_SET(link_bandwidth, struct_cluster->S_cluster_bw);
1662                   SURFXML_BUFFER_SET(link_latency, struct_cluster->S_cluster_lat);
1663                   SURFXML_BUFFER_SET(link_bandwidth_file, "");
1664                   SURFXML_BUFFER_SET(link_latency_file, "");
1665                   SURFXML_BUFFER_SET(link_state_file, "");
1666                   SURFXML_START_TAG(link);
1667                   SURFXML_END_TAG(link);
1668
1669                   free(link_id);
1670                   free(host_id);
1671       }
1672       break;
1673
1674     default:
1675       XBT_DEBUG("Malformed radical");
1676       break;
1677     }
1678
1679     xbt_dynar_free(&radical_ends);
1680   }
1681   xbt_dynar_free(&radical_elements);
1682
1683   XBT_DEBUG(" ");
1684   XBT_DEBUG("<router id=\"%s\"/>", struct_cluster->S_cluster_router_id);
1685   SURFXML_BUFFER_SET(router_id, struct_cluster->S_cluster_router_id);
1686   SURFXML_BUFFER_SET(router_coordinates, "");
1687   SURFXML_START_TAG(router);
1688   SURFXML_END_TAG(router);
1689
1690   if( strcmp(struct_cluster->S_cluster_bb_bw,"")  && strcmp(struct_cluster->S_cluster_bb_lat,"")  ){
1691   char *link_backbone = bprintf("%s_backbone", struct_cluster->V_cluster_id);
1692   XBT_DEBUG("<link\tid=\"%s\" bw=\"%s\" lat=\"%s\"/>", link_backbone,struct_cluster->S_cluster_bb_bw, struct_cluster->S_cluster_bb_lat);
1693   A_surfxml_link_state = A_surfxml_link_state_ON;
1694   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
1695   if(cluster_bb_sharing_policy == A_surfxml_cluster_bb_sharing_policy_FATPIPE)
1696   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
1697   SURFXML_BUFFER_SET(link_id, link_backbone);
1698   SURFXML_BUFFER_SET(link_bandwidth, struct_cluster->S_cluster_bb_bw);
1699   SURFXML_BUFFER_SET(link_latency, struct_cluster->S_cluster_bb_lat);
1700   SURFXML_BUFFER_SET(link_bandwidth_file, "");
1701   SURFXML_BUFFER_SET(link_latency_file, "");
1702   SURFXML_BUFFER_SET(link_state_file, "");
1703   SURFXML_START_TAG(link);
1704   SURFXML_END_TAG(link);
1705   free(link_backbone);
1706   }
1707
1708   XBT_DEBUG(" ");
1709
1710   char *new_suffix = xbt_strdup("");
1711
1712   radical_elements = xbt_str_split(struct_cluster->V_cluster_suffix, ".");
1713   xbt_dynar_foreach(radical_elements, iter, groups) {
1714     if (strcmp(groups, "")) {
1715       char *old_suffix = new_suffix;
1716       new_suffix = bprintf("%s\\.%s", old_suffix, groups);
1717       free(old_suffix);
1718     }
1719   }
1720   route_src_dst = bprintf("%s(.*)%s", struct_cluster->V_cluster_prefix, new_suffix);
1721   xbt_dynar_free(&radical_elements);
1722   xbt_free(new_suffix);
1723
1724   char *pcre_link_src = bprintf("%s_link_$1src", struct_cluster->V_cluster_id);
1725   char *pcre_link_backbone = bprintf("%s_backbone", struct_cluster->V_cluster_id);
1726   char *pcre_link_dst = bprintf("%s_link_$1dst", struct_cluster->V_cluster_id);
1727
1728   //from router to router
1729   XBT_DEBUG("<route\tsrc=\"%s\"\tdst=\"%s\"", struct_cluster->S_cluster_router_id, struct_cluster->S_cluster_router_id);
1730   XBT_DEBUG("symmetrical=\"NO\">");
1731   SURFXML_BUFFER_SET(route_src, struct_cluster->S_cluster_router_id);
1732   SURFXML_BUFFER_SET(route_dst, struct_cluster->S_cluster_router_id);
1733   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
1734   SURFXML_START_TAG(route);
1735
1736   if( strcmp(struct_cluster->S_cluster_bb_bw,"")  && strcmp(struct_cluster->S_cluster_bb_lat,"")  ){
1737   XBT_DEBUG("<link_ctn\tid=\"%s\"/>", pcre_link_backbone);
1738   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_backbone);
1739   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
1740   SURFXML_START_TAG(link_ctn);
1741   SURFXML_END_TAG(link_ctn);
1742   }
1743
1744   XBT_DEBUG("</route>");
1745   SURFXML_END_TAG(route);
1746
1747   //from host to router
1748   XBT_DEBUG("<route\tsrc=\"%s\"\tdst=\"%s\"", route_src_dst, struct_cluster->S_cluster_router_id);
1749   XBT_DEBUG("symmetrical=\"NO\">");
1750   SURFXML_BUFFER_SET(route_src, route_src_dst);
1751   SURFXML_BUFFER_SET(route_dst, struct_cluster->S_cluster_router_id);
1752   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
1753   SURFXML_START_TAG(route);
1754
1755   XBT_DEBUG("<link_ctn\tid=\"%s\"/>", pcre_link_src);
1756   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_src);
1757   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
1758   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
1759   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
1760   SURFXML_START_TAG(link_ctn);
1761   SURFXML_END_TAG(link_ctn);
1762
1763   if( strcmp(struct_cluster->S_cluster_bb_bw,"")  && strcmp(struct_cluster->S_cluster_bb_lat,"")  ){
1764   XBT_DEBUG("<link_ctn\tid=\"%s\"/>", pcre_link_backbone);
1765   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_backbone);
1766   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
1767   SURFXML_START_TAG(link_ctn);
1768   SURFXML_END_TAG(link_ctn);
1769   }
1770
1771   XBT_DEBUG("</route>");
1772   SURFXML_END_TAG(route);
1773
1774   //from router to host
1775   XBT_DEBUG("<route\tsrc=\"%s\"\tdst=\"%s\"", struct_cluster->S_cluster_router_id, route_src_dst);
1776   XBT_DEBUG("symmetrical=\"NO\">");
1777   SURFXML_BUFFER_SET(route_src, struct_cluster->S_cluster_router_id);
1778   SURFXML_BUFFER_SET(route_dst, route_src_dst);
1779   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
1780   SURFXML_START_TAG(route);
1781
1782   if( strcmp(struct_cluster->S_cluster_bb_bw,"")  && strcmp(struct_cluster->S_cluster_bb_lat,"")  ){
1783   XBT_DEBUG("<link_ctn\tid=\"%s\"/>", pcre_link_backbone);
1784   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_backbone);
1785   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
1786   SURFXML_START_TAG(link_ctn);
1787   SURFXML_END_TAG(link_ctn);
1788   }
1789
1790   XBT_DEBUG("<link_ctn\tid=\"%s\"/>", pcre_link_dst);
1791   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_dst);
1792   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
1793   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
1794   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
1795   SURFXML_START_TAG(link_ctn);
1796   SURFXML_END_TAG(link_ctn);
1797
1798   XBT_DEBUG("</route>");
1799   SURFXML_END_TAG(route);
1800
1801   //from host to host
1802   XBT_DEBUG("<route\tsrc=\"%s\"\tdst=\"%s\"", route_src_dst, route_src_dst);
1803   XBT_DEBUG("symmetrical=\"NO\">");
1804   SURFXML_BUFFER_SET(route_src, route_src_dst);
1805   SURFXML_BUFFER_SET(route_dst, route_src_dst);
1806   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
1807   SURFXML_START_TAG(route);
1808
1809   XBT_DEBUG("<link_ctn\tid=\"%s\"/>", pcre_link_src);
1810   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_src);
1811   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
1812   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
1813   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
1814   SURFXML_START_TAG(link_ctn);
1815   SURFXML_END_TAG(link_ctn);
1816
1817   if( strcmp(struct_cluster->S_cluster_bb_bw,"")  && strcmp(struct_cluster->S_cluster_bb_lat,"")  ){
1818   XBT_DEBUG("<link_ctn\tid=\"%s\"/>", pcre_link_backbone);
1819   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_backbone);
1820   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
1821   SURFXML_START_TAG(link_ctn);
1822   SURFXML_END_TAG(link_ctn);
1823   }
1824
1825   XBT_DEBUG("<link_ctn\tid=\"%s\"/>", pcre_link_dst);
1826   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_dst);
1827   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
1828   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
1829   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_DOWN;}
1830   SURFXML_START_TAG(link_ctn);
1831   SURFXML_END_TAG(link_ctn);
1832
1833   XBT_DEBUG("</route>");
1834   SURFXML_END_TAG(route);
1835
1836   free(pcre_link_dst);
1837   free(pcre_link_backbone);
1838   free(pcre_link_src);
1839   free(route_src_dst);
1840
1841   xbt_free(availability_file);
1842   xbt_free(state_file);
1843
1844   xbt_dict_free(&patterns);
1845
1846   XBT_DEBUG("</AS>");
1847   SURFXML_END_TAG(AS);
1848   XBT_DEBUG(" ");
1849
1850   surfxml_bufferstack_pop(1);
1851 }
1852 /*
1853  * This function take a string and replace parameters from patterns dict.
1854  * It returns the new value.
1855  */
1856 static char* replace_random_parameter(char * string)
1857 {
1858   char *test_string = NULL;
1859
1860   if(xbt_dict_size(random_value)==0)
1861     return string;
1862
1863   string = xbt_str_varsubst(string, patterns); // for patterns of cluster
1864   test_string = bprintf("${%s}", string);
1865   test_string = xbt_str_varsubst(test_string,random_value); //Add ${xxxxx} for random Generator
1866
1867   if (strcmp(test_string,"")) { //if not empty, keep this value.
1868     xbt_free(string);
1869     string = test_string;
1870   } //In other case take old value (without ${})
1871   else
1872         free(test_string);
1873   return string;
1874 }
1875
1876 static void clean_routing_after_parse(void)
1877 {
1878         xbt_dict_free(&random_value);
1879         xbt_dict_free(&patterns);
1880 }
1881
1882 static void routing_parse_Speer(void)
1883 {
1884   static int AX_ptr = 0;
1885   char *host_id = NULL;
1886   char *router_id, *link_router, *link_backbone, *link_id_up, *link_id_down;
1887
1888   static unsigned int surfxml_buffer_stack_stack_ptr = 1;
1889   static unsigned int surfxml_buffer_stack_stack[1024];
1890
1891   surfxml_buffer_stack_stack[0] = 0;
1892
1893   surfxml_bufferstack_push(1);
1894
1895   SURFXML_BUFFER_SET(AS_id, struct_peer->V_peer_id);
1896
1897   SURFXML_BUFFER_SET(AS_routing, "Full");
1898   XBT_DEBUG("<AS id=\"%s\"\trouting=\"Full\">", struct_peer->V_peer_id);
1899
1900   SURFXML_START_TAG(AS);
1901
1902   XBT_DEBUG(" ");
1903   host_id = bprintf("peer_%s", struct_peer->V_peer_id);
1904   router_id = bprintf("router_%s", struct_peer->V_peer_id);
1905   link_id_up = bprintf("link_%s_up", struct_peer->V_peer_id);
1906   link_id_down = bprintf("link_%s_down", struct_peer->V_peer_id);
1907
1908   link_router = bprintf("%s_link_router", struct_peer->V_peer_id);
1909   link_backbone = bprintf("%s_backbone", struct_peer->V_peer_id);
1910
1911   XBT_DEBUG("<host\tid=\"%s\"\tpower=\"%s\"/>", host_id, struct_peer->V_peer_power);
1912   A_surfxml_host_state = A_surfxml_host_state_ON;
1913   SURFXML_BUFFER_SET(host_id, host_id);
1914   SURFXML_BUFFER_SET(host_power, struct_peer->V_peer_power);
1915   SURFXML_BUFFER_SET(host_availability, "1.0");
1916   SURFXML_BUFFER_SET(host_availability_file, struct_peer->V_peer_availability_trace);
1917   SURFXML_BUFFER_SET(host_state_file, struct_peer->V_peer_state_trace);
1918   SURFXML_BUFFER_SET(host_coordinates, "");
1919   SURFXML_BUFFER_SET(host_core, "1.0");
1920   SURFXML_START_TAG(host);
1921   SURFXML_END_TAG(host);
1922
1923   XBT_DEBUG("<router id=\"%s\"\tcoordinates=\"%s\"/>", router_id, struct_peer->V_peer_coord);
1924   SURFXML_BUFFER_SET(router_id, router_id);
1925   SURFXML_BUFFER_SET(router_coordinates, struct_peer->V_peer_coord);
1926   SURFXML_START_TAG(router);
1927   SURFXML_END_TAG(router);
1928
1929   XBT_DEBUG("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id_up, struct_peer->V_peer_bw_in, struct_peer->V_peer_lat);
1930   A_surfxml_link_state = A_surfxml_link_state_ON;
1931   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
1932   SURFXML_BUFFER_SET(link_id, link_id_up);
1933   SURFXML_BUFFER_SET(link_bandwidth, struct_peer->V_peer_bw_in);
1934   SURFXML_BUFFER_SET(link_latency, struct_peer->V_peer_lat);
1935   SURFXML_BUFFER_SET(link_bandwidth_file, "");
1936   SURFXML_BUFFER_SET(link_latency_file, "");
1937   SURFXML_BUFFER_SET(link_state_file, "");
1938   SURFXML_START_TAG(link);
1939   SURFXML_END_TAG(link);
1940
1941   XBT_DEBUG("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id_down, struct_peer->V_peer_bw_out, struct_peer->V_peer_lat);
1942   A_surfxml_link_state = A_surfxml_link_state_ON;
1943   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
1944   SURFXML_BUFFER_SET(link_id, link_id_down);
1945   SURFXML_BUFFER_SET(link_bandwidth, struct_peer->V_peer_bw_out);
1946   SURFXML_BUFFER_SET(link_latency, struct_peer->V_peer_lat);
1947   SURFXML_BUFFER_SET(link_bandwidth_file, "");
1948   SURFXML_BUFFER_SET(link_latency_file, "");
1949   SURFXML_BUFFER_SET(link_state_file, "");
1950   SURFXML_START_TAG(link);
1951   SURFXML_END_TAG(link);
1952
1953   XBT_DEBUG(" ");
1954
1955   // begin here
1956   XBT_DEBUG("<route\tsrc=\"%s\"\tdst=\"%s\"", host_id, router_id);
1957   XBT_DEBUG("symmetrical=\"NO\">");
1958   SURFXML_BUFFER_SET(route_src, host_id);
1959   SURFXML_BUFFER_SET(route_dst, router_id);
1960   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
1961   SURFXML_START_TAG(route);
1962
1963   XBT_DEBUG("<link_ctn\tid=\"%s\"/>", link_id_up);
1964   SURFXML_BUFFER_SET(link_ctn_id, link_id_up);
1965   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
1966   SURFXML_START_TAG(link_ctn);
1967   SURFXML_END_TAG(link_ctn);
1968
1969   XBT_DEBUG("</route>");
1970   SURFXML_END_TAG(route);
1971
1972   //Opposite Route
1973   XBT_DEBUG("<route\tsrc=\"%s\"\tdst=\"%s\"", router_id, host_id);
1974   XBT_DEBUG("symmetrical=\"NO\">");
1975   SURFXML_BUFFER_SET(route_src, router_id);
1976   SURFXML_BUFFER_SET(route_dst, host_id);
1977   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
1978   SURFXML_START_TAG(route);
1979
1980   XBT_DEBUG("<link_ctn\tid=\"%s\"/>", link_id_down);
1981   SURFXML_BUFFER_SET(link_ctn_id, link_id_down);
1982   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
1983   SURFXML_START_TAG(link_ctn);
1984   SURFXML_END_TAG(link_ctn);
1985
1986   XBT_DEBUG("</route>");
1987   SURFXML_END_TAG(route);
1988
1989   XBT_DEBUG("</AS>");
1990   SURFXML_END_TAG(AS);
1991   XBT_DEBUG(" ");
1992
1993   //xbt_dynar_free(&tab_elements_num);
1994         free(host_id);
1995         free(router_id);
1996         free(link_router);
1997         free(link_backbone);
1998         free(link_id_up);
1999         free(link_id_down);
2000   surfxml_bufferstack_pop(1);
2001 }
2002
2003 static void routing_parse_Srandom(void)
2004 {
2005           double mean, std, min, max, seed;
2006           char *random_id = A_surfxml_random_id;
2007           char *random_radical = A_surfxml_random_radical;
2008           char *rd_name = NULL;
2009           char *rd_value;
2010           surf_parse_get_double(&mean,A_surfxml_random_mean);
2011           surf_parse_get_double(&std,A_surfxml_random_std_deviation);
2012           surf_parse_get_double(&min,A_surfxml_random_min);
2013           surf_parse_get_double(&max,A_surfxml_random_max);
2014           surf_parse_get_double(&seed,A_surfxml_random_seed);
2015
2016           double res = 0;
2017           int i = 0;
2018           random_data_t random = xbt_new0(s_random_data_t, 1);
2019           char *tmpbuf;
2020
2021           xbt_dynar_t radical_elements;
2022           unsigned int iter;
2023           char *groups;
2024           int start, end;
2025           xbt_dynar_t radical_ends;
2026
2027           random->generator = A_surfxml_random_generator;
2028           random->seed = seed;
2029           random->min = min;
2030           random->max = max;
2031
2032           /* Check user stupidities */
2033           if (max < min)
2034             THROWF(arg_error, 0, "random->max < random->min (%f < %f)", max, min);
2035           if (mean < min)
2036             THROWF(arg_error, 0, "random->mean < random->min (%f < %f)", mean,
2037                    min);
2038           if (mean > max)
2039             THROWF(arg_error, 0, "random->mean > random->max (%f > %f)", mean,
2040                    max);
2041
2042           /* normalize the mean and standard deviation before storing */
2043           random->mean = (mean - min) / (max - min);
2044           random->std = std / (max - min);
2045
2046           if (random->mean * (1 - random->mean) < random->std * random->std)
2047             THROWF(arg_error, 0, "Invalid mean and standard deviation (%f and %f)",
2048                    random->mean, random->std);
2049
2050           XBT_DEBUG("id = '%s' min = '%f' max = '%f' mean = '%f' std_deviatinon = '%f' generator = '%d' seed = '%ld' radical = '%s'",
2051           random_id,
2052           random->min,
2053           random->max,
2054           random->mean,
2055           random->std,
2056           random->generator,
2057           random->seed,
2058           random_radical);
2059
2060           if(xbt_dict_size(random_value)==0)
2061                   random_value = xbt_dict_new();
2062
2063           if(!strcmp(random_radical,""))
2064           {
2065                   res = random_generate(random);
2066                   rd_value = bprintf("%f",res);
2067                   xbt_dict_set(random_value, random_id, rd_value, free);
2068           }
2069           else
2070           {
2071                   radical_elements = xbt_str_split(random_radical, ",");
2072                   xbt_dynar_foreach(radical_elements, iter, groups) {
2073                         radical_ends = xbt_str_split(groups, "-");
2074                         switch (xbt_dynar_length(radical_ends)) {
2075                         case 1:
2076                                           xbt_assert(!xbt_dict_get_or_null(random_value,random_id),"Custom Random '%s' already exists !",random_id);
2077                                           res = random_generate(random);
2078                                           tmpbuf = bprintf("%s%d",random_id,atoi(xbt_dynar_getfirst_as(radical_ends,char *)));
2079                                           xbt_dict_set(random_value, tmpbuf, bprintf("%f",res), free);
2080                                           xbt_free(tmpbuf);
2081                                           break;
2082
2083                         case 2:   surf_parse_get_int(&start,
2084                                                                                  xbt_dynar_get_as(radical_ends, 0, char *));
2085                                           surf_parse_get_int(&end, xbt_dynar_get_as(radical_ends, 1, char *));
2086                                           for (i = start; i <= end; i++) {
2087                                                   xbt_assert(!xbt_dict_get_or_null(random_value,random_id),"Custom Random '%s' already exists !",bprintf("%s%d",random_id,i));
2088                                                   res = random_generate(random);
2089                           tmpbuf = bprintf("%s%d",random_id,i);
2090                                                   xbt_dict_set(random_value, tmpbuf, bprintf("%f",res), free);
2091                           xbt_free(tmpbuf);
2092                                           }
2093                                           break;
2094                         default:
2095                                 XBT_INFO("Malformed radical");
2096                                 break;
2097                         }
2098                         res = random_generate(random);
2099                         rd_name  = bprintf("%s_router",random_id);
2100                         rd_value = bprintf("%f",res);
2101                         xbt_dict_set(random_value, rd_name, rd_value, free);
2102
2103                         xbt_dynar_free(&radical_ends);
2104                   }
2105                   free(rd_name);
2106                   xbt_dynar_free(&radical_elements);
2107           }
2108 }
2109
2110 static void routing_parse_Erandom(void)
2111 {
2112         /*xbt_dict_cursor_t cursor = NULL;
2113         char *key;
2114         char *elem;
2115
2116         xbt_dict_foreach(random_value, cursor, key, elem) {
2117           XBT_DEBUG("%s = %s",key,elem);
2118         }
2119 */
2120 }
2121
2122 /*
2123  * New methods to init the routing model component from the lua script
2124  */
2125
2126
2127 /*
2128  * add a host to the network element list
2129  */
2130
2131 void routing_add_host(const char *host_id)
2132 {
2133   parse_S_host_lua((char *) host_id, (char*)""); // FIXME propagate coordinate system to lua
2134 }
2135
2136 /*
2137  * Set a new link on the actual list of link for a route or ASroute
2138  */
2139 void routing_add_link(const char *link_id)
2140 {
2141   parse_E_link_c_ctn_new_elem_lua((char *) link_id);
2142 }
2143
2144 /*
2145  *Set the endpoints for a route
2146  */
2147 void routing_set_route(const char *src_id, const char *dst_id)
2148 {
2149   parse_S_route_new_and_endpoints_lua(src_id, dst_id);
2150 }
2151
2152 /*
2153  * Store the route by calling parse_E_route_store_route
2154  */
2155 void routing_store_route(void)
2156 {
2157   parse_E_route_store_route();
2158 }