Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
8ed16fc65b2d91423738431a665428933096f791
[simgrid.git] / 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 <float.h>
8 #include "surf_private.h"
9 #include "xbt/dynar.h"
10 #include "xbt/str.h"
11 #include "xbt/config.h"
12 #include "xbt/graph.h"
13 #include "xbt/set.h"
14
15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf");
16
17 routing_t used_routing = NULL;
18 xbt_dict_t onelink_routes = NULL;
19
20 /* Prototypes of each model */
21 static void routing_model_full_create(size_t size_of_link,void *loopback);
22 static void routing_model_floyd_create(size_t size_of_link, void*loopback);
23 static void routing_model_dijkstra_create(size_t size_of_link, void*loopback);
24 static void routing_model_dijkstracache_create(size_t size_of_link, void*loopback);
25 static void routing_model_none_create(size_t size_of_link, void*loopback);
26
27 /* Definition of each model */
28 struct model_type {
29   const char *name;
30   const char *desc;
31   void (*fun)(size_t,void*);
32 };
33 struct model_type models[] =
34 { {"Full", "Full routing data (fast, large memory requirements, fully expressive)", routing_model_full_create },
35   {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)", routing_model_floyd_create },
36   {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)", routing_model_dijkstra_create },
37   {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)", routing_model_dijkstracache_create },
38   {"none", "No routing (usable with Constant network only)", routing_model_none_create },
39     {NULL,NULL,NULL}};
40
41
42 void routing_model_create(size_t size_of_links, void* loopback) {
43
44   char * wanted=xbt_cfg_get_string(_surf_cfg_set,"routing");
45   int cpt;
46   for (cpt=0;models[cpt].name;cpt++) {
47     if (!strcmp(wanted,models[cpt].name)) {
48       (*(models[cpt].fun))(size_of_links,loopback);
49       return;
50     }
51   }
52   fprintf(stderr,"Routing model %s not found. Existing models:\n",wanted);
53   for (cpt=0;models[cpt].name;cpt++)
54     if (!strcmp(wanted,models[cpt].name))
55       fprintf(stderr,"   %s: %s\n",models[cpt].name,models[cpt].desc);
56   exit(1);
57 }
58
59 /* ************************************************************************** */
60 /* *************************** FULL ROUTING ********************************* */
61 typedef struct {
62   s_routing_t generic_routing;
63   xbt_dynar_t *routing_table;
64   void *loopback;
65   size_t size_of_link;
66 } s_routing_full_t,*routing_full_t;
67
68 #define ROUTE_FULL(i,j) ((routing_full_t)used_routing)->routing_table[(i)+(j)*(used_routing)->host_count]
69 #define HOST2ROUTER(id) ((id)+(2<<29))
70 #define ROUTER2HOST(id) ((id)-(2<<29))
71 #define ISROUTER(id) ((id)>=(2<<29))
72
73 /*
74  * Free the onelink routes
75  */
76 static void onelink_route_elem_free(void *e) {
77   s_onelink_t tmp = (s_onelink_t)e;
78   if(tmp) {
79     free(tmp);
80   }
81 }
82
83 /*
84  * Parsing
85  */
86 static void routing_full_parse_Shost(void) {
87   int *val = xbt_malloc(sizeof(int));
88   DEBUG2("Seen host %s (#%d)",A_surfxml_host_id,used_routing->host_count);
89   *val = used_routing->host_count++;
90   xbt_dict_set(used_routing->host_id,A_surfxml_host_id,val,xbt_free);
91 #ifdef HAVE_TRACING
92   TRACE_surf_host_define_id (A_surfxml_host_id, *val);
93 #endif
94 }
95
96 static void routing_full_parse_Srouter(void) {
97         int *val = xbt_malloc(sizeof(int));
98   DEBUG3("Seen router %s (%d -> #%d)",A_surfxml_router_id,used_routing->router_count,
99                 HOST2ROUTER(used_routing->router_count));
100   *val = HOST2ROUTER(used_routing->router_count++);
101   xbt_dict_set(used_routing->host_id,A_surfxml_router_id,val,xbt_free);
102 #ifdef HAVE_TRACING
103   TRACE_surf_host_define_id (A_surfxml_router_id, *val);
104   TRACE_surf_host_declaration (A_surfxml_router_id, 0);
105 #endif
106 }
107
108 static int src_id = -1;
109 static int dst_id = -1;
110 static void routing_full_parse_Sroute_set_endpoints(void)
111 {
112   src_id = *(int*)xbt_dict_get(used_routing->host_id,A_surfxml_route_src);
113   dst_id = *(int*)xbt_dict_get(used_routing->host_id,A_surfxml_route_dst);
114   DEBUG4("Route %s %d -> %s %d",A_surfxml_route_src,src_id,A_surfxml_route_dst,dst_id);
115   route_action = A_surfxml_route_action;
116 }
117 static void routing_full_parse_Eroute(void)
118 {
119   char *name;
120   if (src_id != -1 && dst_id != -1) {
121     name = bprintf("%x#%x", src_id, dst_id);
122     manage_route(route_table, name, route_action, 0);
123     free(name);
124   }
125 }
126
127 /* Cluster tag functions */
128
129 static void routing_full_parse_change_cpu_data(const char *hostName,
130                                   const char *surfxml_host_power,
131                                   const char *surfxml_host_availability,
132                                   const char *surfxml_host_availability_file,
133                                   const char *surfxml_host_state_file)
134 {
135   int AX_ptr = 0;
136
137   SURFXML_BUFFER_SET(host_id, hostName);
138   SURFXML_BUFFER_SET(host_power, surfxml_host_power /*hostPower */ );
139   SURFXML_BUFFER_SET(host_availability, surfxml_host_availability);
140   SURFXML_BUFFER_SET(host_availability_file, surfxml_host_availability_file);
141   SURFXML_BUFFER_SET(host_state_file, surfxml_host_state_file);
142 }
143
144 static void routing_full_parse_change_link_data(const char *linkName,
145                                    const char *surfxml_link_bandwidth,
146                                    const char *surfxml_link_bandwidth_file,
147                                    const char *surfxml_link_latency,
148                                    const char *surfxml_link_latency_file,
149                                    const char *surfxml_link_state_file)
150 {
151   int AX_ptr = 0;
152
153   SURFXML_BUFFER_SET(link_id, linkName);
154   SURFXML_BUFFER_SET(link_bandwidth, surfxml_link_bandwidth);
155   SURFXML_BUFFER_SET(link_bandwidth_file, surfxml_link_bandwidth_file);
156   SURFXML_BUFFER_SET(link_latency, surfxml_link_latency);
157   SURFXML_BUFFER_SET(link_latency_file, surfxml_link_latency_file);
158   SURFXML_BUFFER_SET(link_state_file, surfxml_link_state_file);
159 }
160
161 static void routing_full_parse_Scluster(void)
162 {
163   static int AX_ptr = 0;
164
165   char *cluster_id = A_surfxml_cluster_id;
166   char *cluster_prefix = A_surfxml_cluster_prefix;
167   char *cluster_suffix = A_surfxml_cluster_suffix;
168   char *cluster_radical = A_surfxml_cluster_radical;
169   char *cluster_power = A_surfxml_cluster_power;
170   char *cluster_bw = A_surfxml_cluster_bw;
171   char *cluster_lat = A_surfxml_cluster_lat;
172   char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
173   char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
174   char *backbone_name;
175   unsigned int it1,it2;
176   char *name1,*name2;
177   xbt_dynar_t names = NULL;
178   surfxml_bufferstack_push(1);
179
180   /* Make set a set to parse the prefix/suffix/radical into a neat list of names */
181   DEBUG4("Make <set id='%s' prefix='%s' suffix='%s' radical='%s'>",
182       cluster_id,cluster_prefix,cluster_suffix,cluster_radical);
183   SURFXML_BUFFER_SET(set_id, cluster_id);
184   SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
185   SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
186   SURFXML_BUFFER_SET(set_radical, cluster_radical);
187
188   SURFXML_START_TAG(set);
189   SURFXML_END_TAG(set);
190
191   names = xbt_dict_get(set_list,cluster_id);
192
193   xbt_dynar_foreach(names,it1,name1) {
194     /* create the host */
195     routing_full_parse_change_cpu_data(name1, cluster_power, "1.0", "", "");
196     A_surfxml_host_state = A_surfxml_host_state_ON;
197
198     SURFXML_START_TAG(host);
199     SURFXML_END_TAG(host);
200
201     /* Here comes the link */
202     routing_full_parse_change_link_data(name1, cluster_bw, "", cluster_lat, "", "");
203     A_surfxml_link_state = A_surfxml_link_state_ON;
204     A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
205
206     SURFXML_START_TAG(link);
207     SURFXML_END_TAG(link);
208   }
209
210   /* Make backbone link */
211   backbone_name = bprintf("%s_bb", cluster_id);
212   routing_full_parse_change_link_data(backbone_name, cluster_bb_bw, "", cluster_bb_lat, "",
213                          "");
214   A_surfxml_link_state = A_surfxml_link_state_ON;
215   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_FATPIPE;
216
217   SURFXML_START_TAG(link);
218   SURFXML_END_TAG(link);
219
220   /* And now the internal routes */
221   xbt_dynar_foreach(names,it1,name1) {
222     xbt_dynar_foreach(names,it2,name2) {
223       if (strcmp(name1,name2)) {
224         A_surfxml_route_action = A_surfxml_route_action_POSTPEND;
225         SURFXML_BUFFER_SET(route_src,name1);
226         SURFXML_BUFFER_SET(route_dst,name2);
227         SURFXML_START_TAG(route); {
228           /* FIXME: name1 link is added by error about 20 lines below, so don't add it here
229           SURFXML_BUFFER_SET(link_c_ctn_id, name1);
230           SURFXML_START_TAG(link_c_ctn);
231           SURFXML_END_TAG(link_c_ctn);
232            */
233           SURFXML_BUFFER_SET(link_c_ctn_id, backbone_name);
234           SURFXML_START_TAG(link_c_ctn);
235           SURFXML_END_TAG(link_c_ctn);
236
237           SURFXML_BUFFER_SET(link_c_ctn_id, name2);
238           SURFXML_START_TAG(link_c_ctn);
239           SURFXML_END_TAG(link_c_ctn);
240
241         } SURFXML_END_TAG(route);
242       }
243     }
244   }
245
246   /* Make route multi with the outside world, i.e. cluster->$* */
247
248   /* FIXME
249    * This also adds an elements to the routes within the cluster,
250    * and I guess it's wrong, but since this element is commented out in the above
251    * code creating the internal routes, we're good.
252    * To fix it, I'd say that we need a way to understand "$*-${cluster_id}" as "whole world, but the guys in that cluster"
253    * But for that, we need to install a real expression parser for src/dst attributes
254    *
255    * FIXME
256    * This also adds a dumb element (the private link) in place of the loopback. Then, since
257    * the loopback is added only if no link to self already exist, this fails.
258    * That's really dumb.
259    *
260    * FIXME
261    * It seems to me that it does not add the backbone to the path to outside world...
262    */
263   SURFXML_BUFFER_SET(route_c_multi_src, cluster_id);
264   SURFXML_BUFFER_SET(route_c_multi_dst, "$*");
265   A_surfxml_route_c_multi_symmetric = A_surfxml_route_c_multi_symmetric_NO;
266   A_surfxml_route_c_multi_action = A_surfxml_route_c_multi_action_PREPEND;
267
268   SURFXML_START_TAG(route_c_multi);
269
270   SURFXML_BUFFER_SET(link_c_ctn_id, "$src");
271
272   SURFXML_START_TAG(link_c_ctn);
273   SURFXML_END_TAG(link_c_ctn);
274
275   SURFXML_END_TAG(route_c_multi);
276
277   free(backbone_name);
278
279   /* Restore buff */
280   surfxml_bufferstack_pop(1);
281 }
282
283
284 static void routing_full_parse_end(void) {
285   routing_full_t routing = (routing_full_t) used_routing;
286   int nb_link = 0;
287   unsigned int cpt = 0;
288   xbt_dict_cursor_t cursor = NULL;
289   char *key, *data, *end;
290   const char *sep = "#";
291   xbt_dynar_t links, keys;
292   char *link_name = NULL;
293   int i,j;
294
295   int host_count = routing->generic_routing.host_count;
296
297   /* Create the routing table */
298   routing->routing_table = xbt_new0(xbt_dynar_t, host_count * host_count);
299   for (i=0;i<host_count;i++)
300     for (j=0;j<host_count;j++)
301       ROUTE_FULL(i,j) = xbt_dynar_new(routing->size_of_link,NULL);
302
303   /* Put the routes in position */
304   xbt_dict_foreach(route_table, cursor, key, data) {
305     nb_link = 0;
306     links = (xbt_dynar_t) data;
307     keys = xbt_str_split_str(key, sep);
308
309     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
310     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
311     xbt_dynar_free(&keys);
312
313     if(xbt_dynar_length(links) == 1){
314       s_onelink_t new_link = (s_onelink_t) xbt_malloc0(sizeof(s_onelink));
315       new_link->src_id = src_id;
316       new_link->dst_id = dst_id;
317       link_name = xbt_dynar_getfirst_as(links, char*);
318       new_link->link_ptr = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
319       DEBUG3("Adding onelink route from (#%d) to (#%d), link_name %s",src_id, dst_id, link_name);
320       xbt_dict_set(onelink_routes, link_name, (void *)new_link, onelink_route_elem_free);
321 #ifdef HAVE_TRACING
322       TRACE_surf_link_save_endpoints (link_name, src_id, dst_id);
323 #endif
324     }
325
326     if(ISROUTER(src_id) || ISROUTER(dst_id)) {
327                                 DEBUG2("There is route with a router here: (%d ,%d)",src_id,dst_id);
328                                 /* Check there is only one link in the route and store the information */
329                                 continue;
330     }
331
332     DEBUG4("Handle %d %d (from %d hosts): %ld links",
333         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
334     xbt_dynar_foreach(links, cpt, link_name) {
335       void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
336       if (link)
337         xbt_dynar_push(ROUTE_FULL(src_id,dst_id),&link);
338       else
339         THROW1(mismatch_error,0,"Link %s not found", link_name);
340     }
341   }
342
343   /* Add the loopback if needed */
344   for (i = 0; i < host_count; i++)
345     if (!xbt_dynar_length(ROUTE_FULL(i, i)))
346       xbt_dynar_push(ROUTE_FULL(i,i),&routing->loopback);
347
348   /* Shrink the dynar routes (save unused slots) */
349   for (i=0;i<host_count;i++)
350     for (j=0;j<host_count;j++)
351       xbt_dynar_shrink(ROUTE_FULL(i,j),0);
352 }
353
354 /*
355  * Business methods
356  */
357 static xbt_dynar_t routing_full_get_route(int src,int dst) {
358   xbt_assert0(!(ISROUTER(src) || ISROUTER(dst)), "Ask for route \"from\" or \"to\" a router node");
359   return ROUTE_FULL(src,dst);
360 }
361
362 static xbt_dict_t routing_full_get_onelink_routes(void){
363   return onelink_routes;
364 }
365
366 static int routing_full_is_router(int id){
367         return ISROUTER(id);
368 }
369
370 static void routing_full_finalize(void) {
371   routing_full_t routing = (routing_full_t)used_routing;
372   int i,j;
373
374   if (routing) {
375     for (i = 0; i < used_routing->host_count; i++)
376       for (j = 0; j < used_routing->host_count; j++)
377         xbt_dynar_free(&ROUTE_FULL(i, j));
378     free(routing->routing_table);
379     xbt_dict_free(&used_routing->host_id);
380     xbt_dict_free(&onelink_routes);
381     free(routing);
382     routing=NULL;
383   }
384 }
385
386 static void routing_model_full_create(size_t size_of_link,void *loopback) {
387   /* initialize our structure */
388   routing_full_t routing = xbt_new0(s_routing_full_t,1);
389   routing->generic_routing.name = "Full";
390   routing->generic_routing.host_count = 0;
391   routing->generic_routing.get_route = routing_full_get_route;
392   routing->generic_routing.get_onelink_routes = routing_full_get_onelink_routes;
393   routing->generic_routing.is_router = routing_full_is_router;
394   routing->generic_routing.finalize = routing_full_finalize;
395
396   routing->size_of_link = size_of_link;
397   routing->loopback = loopback;
398
399   /* Set it in position */
400   used_routing = (routing_t) routing;
401
402   /* Set the dict for onehop routes */
403   onelink_routes =  xbt_dict_new();
404
405   /* Setup the parsing callbacks we need */
406   routing->generic_routing.host_id = xbt_dict_new();
407   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
408   surfxml_add_callback(STag_surfxml_router_cb_list, &routing_full_parse_Srouter);
409   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_full_parse_end);
410   surfxml_add_callback(STag_surfxml_route_cb_list,
411       &routing_full_parse_Sroute_set_endpoints);
412   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
413   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_full_parse_Scluster);
414 }
415
416 /* ************************************************************************** */
417
418 static void routing_shortest_path_parse_Scluster(void)
419 {
420   static int AX_ptr = 0;
421
422   char *cluster_id = A_surfxml_cluster_id;
423   char *cluster_prefix = A_surfxml_cluster_prefix;
424   char *cluster_suffix = A_surfxml_cluster_suffix;
425   char *cluster_radical = A_surfxml_cluster_radical;
426   char *cluster_power = A_surfxml_cluster_power;
427   char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
428   char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
429   char *backbone_name;
430
431   surfxml_bufferstack_push(1);
432
433   /* Make set */
434   SURFXML_BUFFER_SET(set_id, cluster_id);
435   SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
436   SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
437   SURFXML_BUFFER_SET(set_radical, cluster_radical);
438
439   SURFXML_START_TAG(set);
440   SURFXML_END_TAG(set);
441
442   /* Make foreach */
443   SURFXML_BUFFER_SET(foreach_set_id, cluster_id);
444
445   SURFXML_START_TAG(foreach);
446
447   /* Make host for the foreach */
448   routing_full_parse_change_cpu_data("$1", cluster_power, "1.0", "", "");
449   A_surfxml_host_state = A_surfxml_host_state_ON;
450
451   SURFXML_START_TAG(host);
452   SURFXML_END_TAG(host);
453
454   SURFXML_END_TAG(foreach);
455
456   /* Make backbone link */
457   backbone_name = bprintf("%s_bb", cluster_id);
458   routing_full_parse_change_link_data(backbone_name, cluster_bb_bw, "", cluster_bb_lat, "",
459                          "");
460   A_surfxml_link_state = A_surfxml_link_state_ON;
461   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_FATPIPE;
462
463   SURFXML_START_TAG(link);
464   SURFXML_END_TAG(link);
465
466   free(backbone_name);
467
468   /* Restore buff */
469   surfxml_bufferstack_pop(1);
470 }
471
472 /* ************************************************************************** */
473 /* *************************** FLOYD ROUTING ********************************* */
474 typedef struct {
475   s_routing_t generic_routing;
476   int *predecessor_table;
477   void** link_table;
478   xbt_dynar_t last_route;
479   void *loopback;
480   size_t size_of_link;
481 } s_routing_floyd_t,*routing_floyd_t;
482
483 #define FLOYD_COST(i,j) cost_table[(i)+(j)*(used_routing)->host_count]
484 #define FLOYD_PRED(i,j) ((routing_floyd_t)used_routing)->predecessor_table[(i)+(j)*(used_routing)->host_count]
485 #define FLOYD_LINK(i,j) ((routing_floyd_t)used_routing)->link_table[(i)+(j)*(used_routing)->host_count]
486
487 static void routing_floyd_parse_end(void) {
488
489   routing_floyd_t routing = (routing_floyd_t) used_routing;
490   int nb_link = 0;
491   void* link_list = NULL;
492   double * cost_table;
493   xbt_dict_cursor_t cursor = NULL;
494   char *key,*data, *end;
495   const char *sep = "#";
496   xbt_dynar_t links, keys;
497
498   unsigned int i,j;
499   unsigned int a,b,c;
500   int host_count = routing->generic_routing.host_count;
501   char * link_name = NULL;
502   void * link = NULL;
503
504   /* Create Cost, Predecessor and Link tables */
505   cost_table = xbt_new0(double, host_count * host_count); //link cost from host to host
506   routing->predecessor_table = xbt_new0(int, host_count*host_count); //predecessor host numbers
507   routing->link_table = xbt_new0(void*,host_count*host_count); //actual link between src and dst
508   routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
509
510   /* Initialize costs and predecessors*/
511   for(i = 0; i<host_count;i++)
512     for(j = 0; j<host_count;j++) {
513         FLOYD_COST(i,j) = DBL_MAX;
514         FLOYD_PRED(i,j) = -1;
515     }
516
517    /* Put the routes in position */
518   xbt_dict_foreach(route_table, cursor, key, data) {
519     nb_link = 0;
520     links = (xbt_dynar_t)data;
521     keys = xbt_str_split_str(key, sep);
522
523     
524     src_id = strtol(xbt_dynar_get_as(keys, 0, char*), &end, 16);
525     dst_id = strtol(xbt_dynar_get_as(keys, 1, char*), &end, 16);
526     xbt_dynar_free(&keys);
527  
528     DEBUG4("Handle %d %d (from %d hosts): %ld links",
529         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
530     xbt_assert3(xbt_dynar_length(links) == 1, "%ld links in route between host %d and %d, should be 1", xbt_dynar_length(links), src_id, dst_id);
531     
532     link_name = xbt_dynar_getfirst_as(links, char*);
533     link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
534
535     if (link)
536       link_list = link;
537     else
538       THROW1(mismatch_error,0,"Link %s not found", link_name);
539     
540
541     FLOYD_LINK(src_id,dst_id) = link_list;
542     FLOYD_PRED(src_id, dst_id) = src_id;
543
544     //link cost
545     FLOYD_COST(src_id, dst_id) = 1; // assume 1 for now
546
547   }
548
549     /* Add the loopback if needed */
550   for (i = 0; i < host_count; i++)
551     if (!FLOYD_PRED(i, i)) {
552       FLOYD_PRED(i, i) = i;
553       FLOYD_COST(i, i) = 1;
554       FLOYD_LINK(i, i) = routing->loopback;
555     }
556
557
558   //Calculate path costs 
559
560   for(c=0;c<host_count;c++) {
561     for(a=0;a<host_count;a++) {
562       for(b=0;b<host_count;b++) {
563         if(FLOYD_COST(a,c) < DBL_MAX && FLOYD_COST(c,b) < DBL_MAX) {
564           if(FLOYD_COST(a,b) == DBL_MAX || (FLOYD_COST(a,c)+FLOYD_COST(c,b) < FLOYD_COST(a,b))) {
565             FLOYD_COST(a,b) = FLOYD_COST(a,c)+FLOYD_COST(c,b);
566             FLOYD_PRED(a,b) = FLOYD_PRED(c,b);
567           }
568         }
569       }
570     }
571   }
572
573   //cleanup
574   free(cost_table);
575 }
576
577 /*
578  * Business methods
579  */
580 static xbt_dynar_t routing_floyd_get_route(int src_id,int dst_id) {
581
582   routing_floyd_t routing = (routing_floyd_t) used_routing;
583
584   int pred = dst_id;
585   int prev_pred = 0;
586
587   xbt_dynar_reset(routing->last_route);
588
589   do {
590     prev_pred = pred;
591     pred = FLOYD_PRED(src_id, pred);
592
593     if(pred == -1) // if no pred in route -> no route to host
594         break;
595
596     xbt_dynar_unshift(routing->last_route, &FLOYD_LINK(pred,prev_pred));
597
598   } while(pred != src_id);
599
600   xbt_assert2(pred != -1, "no route from host %d to %d", src_id, dst_id);
601
602   return routing->last_route;
603 }
604
605 static void routing_floyd_finalize(void) {
606   routing_floyd_t routing = (routing_floyd_t)used_routing;
607
608   if (routing) {
609     free(routing->link_table);
610     free(routing->predecessor_table);
611     xbt_dynar_free(&routing->last_route);
612     xbt_dict_free(&used_routing->host_id);
613     free(routing);
614     routing=NULL;
615   }
616 }
617
618 static xbt_dict_t routing_floyd_get_onelink_routes(void){
619   xbt_assert0(0,"The get_onelink_routes feature is not supported in routing model Floyd");
620 }
621
622 static int routing_floyd_is_router(int id){
623   xbt_assert0(0,"The get_is_router feature is not supported in routing model Floyd");
624 }
625
626 static void routing_model_floyd_create(size_t size_of_link,void *loopback) {
627   /* initialize our structure */
628   routing_floyd_t routing = xbt_new0(s_routing_floyd_t,1);
629   routing->generic_routing.name = "Floyd";
630   routing->generic_routing.host_count = 0;
631   routing->generic_routing.host_id = xbt_dict_new();
632   routing->generic_routing.get_route = routing_floyd_get_route;
633   routing->generic_routing.get_onelink_routes = routing_floyd_get_onelink_routes;
634   routing->generic_routing.is_router = routing_floyd_is_router;
635   routing->generic_routing.finalize = routing_floyd_finalize;
636   routing->size_of_link = size_of_link;
637   routing->loopback = loopback;
638
639   /* Set it in position */
640   used_routing = (routing_t) routing;
641   
642   /* Setup the parsing callbacks we need */
643   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
644   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_floyd_parse_end);
645   surfxml_add_callback(STag_surfxml_route_cb_list, 
646       &routing_full_parse_Sroute_set_endpoints);
647   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
648   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);
649   
650 }
651
652 /* ************************************************************************** */
653 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
654 typedef struct {
655   s_routing_t generic_routing;
656   xbt_graph_t route_graph;
657   xbt_dict_t graph_node_map;
658   xbt_dict_t route_cache;
659   xbt_dynar_t last_route;
660   int cached;
661   void *loopback;
662   size_t size_of_link;
663 } s_routing_dijkstra_t,*routing_dijkstra_t;
664
665
666 typedef struct graph_node_data {
667   int id; 
668   int graph_id; //used for caching internal graph id's
669 } s_graph_node_data_t, * graph_node_data_t;
670
671 typedef struct graph_node_map_element {
672   xbt_node_t node;
673 } s_graph_node_map_element_t, * graph_node_map_element_t;
674
675 typedef struct route_cache_element {
676   int * pred_arr;
677   int size;
678 } s_route_cache_element_t, * route_cache_element_t;     
679
680 /*
681  * Free functions
682  */
683 static void route_cache_elem_free(void *e) {
684   route_cache_element_t elm=(route_cache_element_t)e;
685
686   if (elm) {
687     free(elm->pred_arr);
688     free(elm);
689   }
690 }
691
692 static void graph_node_map_elem_free(void *e) {
693   graph_node_map_element_t elm = (graph_node_map_element_t)e;
694
695   if(elm) {
696     free(elm);
697   }
698 }
699
700 /*
701  * Utility functions
702 */
703 static xbt_node_t route_graph_new_node(int id, int graph_id) {
704   xbt_node_t node = NULL;
705   graph_node_data_t data = NULL;
706   graph_node_map_element_t elm = NULL;
707   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
708
709   data = xbt_new0(struct graph_node_data, sizeof(struct graph_node_data));
710   data->id = id;
711   data->graph_id = graph_id;
712   node = xbt_graph_new_node(routing->route_graph, data);
713
714   elm = xbt_new0(struct graph_node_map_element, sizeof(struct graph_node_map_element));
715   elm->node = node;
716   xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);
717
718   return node;
719 }
720
721 static graph_node_map_element_t graph_node_map_search(int id) {
722   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
723
724   graph_node_map_element_t elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&id), sizeof(int));
725
726   return elm;
727 }
728
729 /*
730  * Parsing
731  */
732 static void route_new_dijkstra(int src_id, int dst_id, void* link) {
733   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
734
735   xbt_node_t src = NULL;
736   xbt_node_t dst = NULL;
737   graph_node_map_element_t src_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&src_id), sizeof(int));
738   graph_node_map_element_t dst_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&dst_id), sizeof(int));
739
740   if(src_elm)
741     src = src_elm->node;
742
743   if(dst_elm)
744     dst = dst_elm->node;
745
746   //add nodes if they don't exist in the graph
747   if(src_id == dst_id && src == NULL && dst == NULL) {
748     src = route_graph_new_node(src_id, -1);
749     dst = src;
750   } else {
751     if(src == NULL) {
752       src = route_graph_new_node(src_id, -1);
753     }
754         
755     if(dst == NULL) {
756       dst = route_graph_new_node(dst_id, -1);
757     }
758   }
759
760   //add link as edge to graph
761   xbt_graph_new_edge(routing->route_graph, src, dst, link);
762   
763 }
764
765 static void add_loopback_dijkstra(void) {
766   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
767
768         xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
769         
770         xbt_node_t node = NULL;
771         unsigned int cursor2;
772         xbt_dynar_foreach(nodes, cursor2, node) {
773                 xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node); 
774                 xbt_edge_t edge = NULL;
775                 unsigned int cursor;
776         
777                 int found = 0;
778                 xbt_dynar_foreach(out_edges, cursor, edge) {
779                         xbt_node_t other_node = xbt_graph_edge_get_target(edge);
780                         if(other_node == node) {
781                                 found = 1;
782                                 break;
783                         }
784                 }
785
786                 if(!found)
787                         xbt_graph_new_edge(routing->route_graph, node, node, &routing->loopback);
788         }
789 }
790
791 static void routing_dijkstra_parse_end(void) {
792   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
793   int nb_link = 0;
794   xbt_dict_cursor_t cursor = NULL;
795   char *key, *data, *end;
796   const char *sep = "#";
797   xbt_dynar_t links, keys;
798   char* link_name = NULL;
799   void* link = NULL;
800   xbt_node_t node = NULL;
801   unsigned int cursor2;
802   xbt_dynar_t nodes = NULL;
803   /* Create the topology graph */
804   routing->route_graph = xbt_graph_new_graph(1, NULL);
805   routing->graph_node_map = xbt_dict_new();
806   routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
807   if(routing->cached)
808     routing->route_cache = xbt_dict_new();
809
810
811   /* Put the routes in position */
812   xbt_dict_foreach(route_table, cursor, key, data) {
813     nb_link = 0;
814     links = (xbt_dynar_t) data;
815     keys = xbt_str_split_str(key, sep);
816
817     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
818     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
819     xbt_dynar_free(&keys);
820
821     DEBUG4("Handle %d %d (from %d hosts): %ld links",
822         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
823
824     xbt_assert3(xbt_dynar_length(links) == 1, "%ld links in route between host %d and %d, should be 1", xbt_dynar_length(links), src_id, dst_id);
825
826     link_name = xbt_dynar_getfirst_as(links, char*);
827     link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
828     if (link)
829       route_new_dijkstra(src_id,dst_id,link);
830     else
831       THROW1(mismatch_error,0,"Link %s not found", link_name);
832     
833   }
834
835   /* Add the loopback if needed */
836   add_loopback_dijkstra();
837
838   /* initialize graph indexes in nodes after graph has been built */
839   nodes = xbt_graph_get_nodes(routing->route_graph);
840
841   xbt_dynar_foreach(nodes, cursor2, node) {
842     graph_node_data_t data = xbt_graph_node_get_data(node);
843     data->graph_id = cursor2;
844   }
845
846 }
847
848 /*
849  * Business methods
850  */
851 static xbt_dynar_t routing_dijkstra_get_route(int src_id,int dst_id) {
852
853   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
854   int * pred_arr = NULL;
855   int src_node_id = 0;
856   int dst_node_id = 0;
857   int * nodeid = NULL;
858   int v;
859   int size = 0;
860   void * link = NULL;
861   route_cache_element_t elm = NULL;
862   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
863
864   /*Use the graph_node id mapping set to quickly find the nodes */
865   graph_node_map_element_t src_elm = graph_node_map_search(src_id);
866   graph_node_map_element_t dst_elm = graph_node_map_search(dst_id);
867   xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", src_id, dst_id);
868   src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id;
869   dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id;
870
871   if(routing->cached) {
872     /*check if there is a cached predecessor list avail */
873     elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int));
874   }
875
876   if(elm) { //cached mode and cache hit
877     pred_arr = elm->pred_arr;
878   } else { //not cached mode or cache miss
879     double * cost_arr = NULL;
880     xbt_heap_t pqueue = NULL;
881     int i = 0;
882
883     int nr_nodes = xbt_dynar_length(nodes);
884     cost_arr = xbt_new0(double, nr_nodes); //link cost from src to other hosts
885     pred_arr = xbt_new0(int, nr_nodes); //predecessors in path from src
886     pqueue = xbt_heap_new(nr_nodes, free);
887
888     //initialize
889     cost_arr[src_node_id] = 0.0;
890
891     for(i = 0; i < nr_nodes; i++) {
892       if(i != src_node_id) {
893         cost_arr[i] = DBL_MAX;
894       }
895
896       pred_arr[i] = 0;
897
898       //initialize priority queue
899       nodeid = xbt_new0(int, 1);
900       *nodeid = i;
901       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
902
903     }
904
905     // apply dijkstra using the indexes from the graph's node array
906     while(xbt_heap_size(pqueue) > 0) {
907       int * v_id = xbt_heap_pop(pqueue);
908       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
909       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node); 
910       xbt_edge_t edge = NULL;
911       unsigned int cursor;
912
913       xbt_dynar_foreach(out_edges, cursor, edge) {
914         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
915         graph_node_data_t data = xbt_graph_node_get_data(u_node);
916         int u_id = data->graph_id;
917         int cost_v_u = 1; //fixed link cost for now
918
919         if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
920           pred_arr[u_id] = *v_id;
921           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
922           nodeid = xbt_new0(int, 1);
923           *nodeid = u_id;
924           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
925         }
926       }
927
928       //free item popped from pqueue
929       free(v_id);
930     }
931
932     free(cost_arr);
933     xbt_heap_free(pqueue);
934
935   }
936
937   //compose route path with links
938   xbt_dynar_reset(routing->last_route);
939
940   for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
941     xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
942     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
943     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
944
945     xbt_assert2(edge != NULL, "no route between host %d and %d", src_id, dst_id);
946
947     link = xbt_graph_edge_get_data(edge);
948     xbt_dynar_unshift(routing->last_route, &link);
949     size++;
950   }
951
952
953   if(routing->cached && elm == NULL) {
954     //add to predecessor list of the current src-host to cache
955     elm = xbt_new0(struct route_cache_element, sizeof(struct route_cache_element));
956     elm->pred_arr = pred_arr;
957     elm->size = size;
958     xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free);
959   }
960
961   if(!routing->cached)
962     free(pred_arr);
963
964   return routing->last_route;
965 }
966
967
968 static void routing_dijkstra_finalize(void) {
969   routing_dijkstra_t routing = (routing_dijkstra_t)used_routing;
970
971   if (routing) {
972     xbt_graph_free_graph(routing->route_graph, &free, NULL, &free);
973     xbt_dict_free(&routing->graph_node_map);
974     if(routing->cached)
975       xbt_dict_free(&routing->route_cache);
976     xbt_dynar_free(&routing->last_route);
977     xbt_dict_free(&used_routing->host_id);
978     free(routing);
979     routing=NULL;
980   }
981 }
982
983 static xbt_dict_t routing_dijkstraboth_get_onelink_routes(void){
984   xbt_assert0(0,"The get_onelink_routes feature is not supported in routing model dijkstraboth");
985 }
986
987 static int routing_dijkstraboth_is_router(int id){
988   xbt_assert0(0,"The get_is_router feature is not supported in routing model dijkstraboth");
989 }
990
991 /*
992  *
993  */
994 static void routing_model_dijkstraboth_create(size_t size_of_link,void *loopback, int cached) {
995   /* initialize our structure */
996   routing_dijkstra_t routing = xbt_new0(s_routing_dijkstra_t,1);
997   routing->generic_routing.name = "Dijkstra";
998   routing->generic_routing.host_count = 0;
999   routing->generic_routing.get_route = routing_dijkstra_get_route;
1000   routing->generic_routing.get_onelink_routes = routing_dijkstraboth_get_onelink_routes;
1001   routing->generic_routing.is_router = routing_dijkstraboth_is_router;
1002   routing->generic_routing.finalize = routing_dijkstra_finalize;
1003   routing->size_of_link = size_of_link;
1004   routing->loopback = loopback;
1005   routing->cached = cached;
1006
1007   /* Set it in position */
1008   used_routing = (routing_t) routing;
1009
1010   /* Setup the parsing callbacks we need */
1011   routing->generic_routing.host_id = xbt_dict_new();
1012   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
1013   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_dijkstra_parse_end);
1014   surfxml_add_callback(STag_surfxml_route_cb_list,
1015       &routing_full_parse_Sroute_set_endpoints);
1016   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
1017   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);
1018 }
1019
1020 static void routing_model_dijkstra_create(size_t size_of_link,void *loopback) {
1021   routing_model_dijkstraboth_create(size_of_link, loopback, 0);
1022 }
1023
1024 static void routing_model_dijkstracache_create(size_t size_of_link,void *loopback) {
1025   routing_model_dijkstraboth_create(size_of_link, loopback, 1);
1026 }
1027
1028 /* ************************************************** */
1029 /* ********** NO ROUTING **************************** */
1030
1031
1032 static void routing_none_finalize(void) {
1033   if (used_routing) {
1034     xbt_dict_free(&used_routing->host_id);
1035     free(used_routing);
1036     used_routing=NULL;
1037   }
1038 }
1039
1040 static void routing_model_none_create(size_t size_of_link,void *loopback) {
1041   routing_t routing = xbt_new0(s_routing_t,1);
1042   routing->name = "none";
1043   routing->host_count = 0;
1044   routing->host_id = xbt_dict_new();
1045   routing->get_onelink_routes = NULL;
1046   routing->is_router = NULL;
1047   routing->get_route = NULL;
1048
1049   routing->finalize = routing_none_finalize;
1050
1051   /* Set it in position */
1052   used_routing = (routing_t) routing;
1053 }
1054
1055 /*****************************************************************/
1056 /******************* BYBASS THE PARSER ***************************/
1057
1058 /*
1059  * FIXME : better to add to the routing model instead !!
1060  *
1061  */
1062 void routing_add_route(char *source_id,char *destination_id,xbt_dynar_t links_id,int action)
1063 {
1064     char * link_id;
1065     char * name;
1066     unsigned int i;
1067     src_id = *(int*)xbt_dict_get(used_routing->host_id,source_id);
1068     dst_id = *(int*)xbt_dict_get(used_routing->host_id,destination_id);
1069     DEBUG4("Route %s %d -> %s %d",source_id,src_id,destination_id,dst_id);
1070         //set Links
1071     xbt_dynar_foreach(links_id,i,link_id)
1072      {
1073         surf_add_route_element(link_id);
1074      }
1075     route_action = action;
1076         if (src_id != -1 && dst_id != -1) {
1077            name = bprintf("%x#%x", src_id, dst_id);
1078            manage_route(route_table, name, route_action, 0);
1079            free(name);
1080         }
1081
1082 }
1083
1084 void routing_add_host(char* host_id)
1085 {
1086         int *val = xbt_malloc(sizeof(int));
1087         DEBUG2("Seen host %s (#%d)",host_id,used_routing->host_count);
1088         *val = used_routing->host_count++;
1089         xbt_dict_set(used_routing->host_id,host_id,val,xbt_free);
1090         #ifdef HAVE_TRACING
1091           TRACE_surf_host_define_id (host_id, *val);
1092         #endif
1093 }
1094
1095 void routing_set_routes()
1096 {
1097         routing_full_parse_end();
1098 }