Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
fef83e49b4048d814457cd1c92577d014ba6a252
[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_host_id, *val);
104   TRACE_surf_host_declaration (A_surfxml_host_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
176   surfxml_bufferstack_push(1);
177
178   /* Make set a set to parse the prefix/suffix/radical into a neat list of names */
179   DEBUG4("Make <set id='%s' prefix='%s' suffix='%s' radical='%s'>",
180       cluster_id,cluster_prefix,cluster_suffix,cluster_radical);
181   SURFXML_BUFFER_SET(set_id, cluster_id);
182   SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
183   SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
184   SURFXML_BUFFER_SET(set_radical, cluster_radical);
185
186   SURFXML_START_TAG(set);
187   SURFXML_END_TAG(set);
188
189   xbt_dynar_t names = xbt_dict_get(set_list,cluster_id);
190
191   unsigned int it1,it2;
192   char *name1,*name2;
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
500   int host_count = routing->generic_routing.host_count;
501
502   /* Create Cost, Predecessor and Link tables */
503   cost_table = xbt_new0(double, host_count * host_count); //link cost from host to host
504   routing->predecessor_table = xbt_new0(int, host_count*host_count); //predecessor host numbers
505   routing->link_table = xbt_new0(void*,host_count*host_count); //actual link between src and dst
506   routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
507
508   /* Initialize costs and predecessors*/
509   for(i = 0; i<host_count;i++)
510     for(j = 0; j<host_count;j++) {
511         FLOYD_COST(i,j) = DBL_MAX;
512         FLOYD_PRED(i,j) = -1;
513     }
514
515    /* Put the routes in position */
516   xbt_dict_foreach(route_table, cursor, key, data) {
517     nb_link = 0;
518     links = (xbt_dynar_t)data;
519     keys = xbt_str_split_str(key, sep);
520
521     
522     src_id = strtol(xbt_dynar_get_as(keys, 0, char*), &end, 16);
523     dst_id = strtol(xbt_dynar_get_as(keys, 1, char*), &end, 16);
524     xbt_dynar_free(&keys);
525  
526     DEBUG4("Handle %d %d (from %d hosts): %ld links",
527         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
528     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);
529     
530     char * link_name = xbt_dynar_getfirst_as(links, char*);
531     void * link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
532     if (link)
533       link_list = link;
534     else
535       THROW1(mismatch_error,0,"Link %s not found", link_name);
536     
537
538     FLOYD_LINK(src_id,dst_id) = link_list;
539     FLOYD_PRED(src_id, dst_id) = src_id;
540
541     //link cost
542     FLOYD_COST(src_id, dst_id) = 1; // assume 1 for now
543
544   }
545
546     /* Add the loopback if needed */
547   for (i = 0; i < host_count; i++)
548     if (!FLOYD_PRED(i, i)) {
549       FLOYD_PRED(i, i) = i;
550       FLOYD_COST(i, i) = 1;
551       FLOYD_LINK(i, i) = routing->loopback;
552     }
553
554
555   //Calculate path costs 
556   unsigned int a,b,c;
557   for(c=0;c<host_count;c++) {
558     for(a=0;a<host_count;a++) {
559       for(b=0;b<host_count;b++) {
560         if(FLOYD_COST(a,c) < DBL_MAX && FLOYD_COST(c,b) < DBL_MAX) {
561           if(FLOYD_COST(a,b) == DBL_MAX || (FLOYD_COST(a,c)+FLOYD_COST(c,b) < FLOYD_COST(a,b))) {
562             FLOYD_COST(a,b) = FLOYD_COST(a,c)+FLOYD_COST(c,b);
563             FLOYD_PRED(a,b) = FLOYD_PRED(c,b);
564           }
565         }
566       }
567     }
568   }
569
570   //cleanup
571   free(cost_table);
572 }
573
574 /*
575  * Business methods
576  */
577 static xbt_dynar_t routing_floyd_get_route(int src_id,int dst_id) {
578
579   routing_floyd_t routing = (routing_floyd_t) used_routing;
580
581   int pred = dst_id;
582   int prev_pred = 0;
583
584   xbt_dynar_reset(routing->last_route);
585
586   do {
587     prev_pred = pred;
588     pred = FLOYD_PRED(src_id, pred);
589
590     if(pred == -1) // if no pred in route -> no route to host
591         break;
592
593     xbt_dynar_unshift(routing->last_route, &FLOYD_LINK(pred,prev_pred));
594
595   } while(pred != src_id);
596
597   xbt_assert2(pred != -1, "no route from host %d to %d", src_id, dst_id);
598
599   return routing->last_route;
600 }
601
602 static void routing_floyd_finalize(void) {
603   routing_floyd_t routing = (routing_floyd_t)used_routing;
604
605   if (routing) {
606     free(routing->link_table);
607     free(routing->predecessor_table);
608     xbt_dynar_free(&routing->last_route);
609     xbt_dict_free(&used_routing->host_id);
610     free(routing);
611     routing=NULL;
612   }
613 }
614
615 static xbt_dict_t routing_floyd_get_onelink_routes(void){
616   xbt_assert0(0,"The get_onelink_routes feature is not supported in routing model Floyd");
617 }
618
619 static int routing_floyd_is_router(int id){
620   xbt_assert0(0,"The get_is_router feature is not supported in routing model Floyd");
621 }
622
623 static void routing_model_floyd_create(size_t size_of_link,void *loopback) {
624   /* initialize our structure */
625   routing_floyd_t routing = xbt_new0(s_routing_floyd_t,1);
626   routing->generic_routing.name = "Floyd";
627   routing->generic_routing.host_count = 0;
628   routing->generic_routing.host_id = xbt_dict_new();
629   routing->generic_routing.get_route = routing_floyd_get_route;
630   routing->generic_routing.get_onelink_routes = routing_floyd_get_onelink_routes;
631   routing->generic_routing.is_router = routing_floyd_is_router;
632   routing->generic_routing.finalize = routing_floyd_finalize;
633   routing->size_of_link = size_of_link;
634   routing->loopback = loopback;
635
636   /* Set it in position */
637   used_routing = (routing_t) routing;
638   
639   /* Setup the parsing callbacks we need */
640   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
641   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_floyd_parse_end);
642   surfxml_add_callback(STag_surfxml_route_cb_list, 
643       &routing_full_parse_Sroute_set_endpoints);
644   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
645   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);
646   
647 }
648
649 /* ************************************************************************** */
650 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
651 typedef struct {
652   s_routing_t generic_routing;
653   xbt_graph_t route_graph;
654   xbt_dict_t graph_node_map;
655   xbt_dict_t route_cache;
656   xbt_dynar_t last_route;
657   int cached;
658   void *loopback;
659   size_t size_of_link;
660 } s_routing_dijkstra_t,*routing_dijkstra_t;
661
662
663 typedef struct graph_node_data {
664   int id; 
665   int graph_id; //used for caching internal graph id's
666 } s_graph_node_data_t, * graph_node_data_t;
667
668 typedef struct graph_node_map_element {
669   xbt_node_t node;
670 } s_graph_node_map_element_t, * graph_node_map_element_t;
671
672 typedef struct route_cache_element {
673   int * pred_arr;
674   int size;
675 } s_route_cache_element_t, * route_cache_element_t;     
676
677 /*
678  * Free functions
679  */
680 static void route_cache_elem_free(void *e) {
681   route_cache_element_t elm=(route_cache_element_t)e;
682
683   if (elm) {
684     free(elm->pred_arr);
685     free(elm);
686   }
687 }
688
689 static void graph_node_map_elem_free(void *e) {
690   graph_node_map_element_t elm = (graph_node_map_element_t)e;
691
692   if(elm) {
693     free(elm);
694   }
695 }
696
697 /*
698  * Utility functions
699 */
700 static xbt_node_t route_graph_new_node(int id, int graph_id) {
701   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
702
703   graph_node_data_t data = xbt_new0(struct graph_node_data, sizeof(struct graph_node_data));
704   data->id = id;
705   data->graph_id = graph_id;
706   xbt_node_t node = xbt_graph_new_node(routing->route_graph, data);
707
708   graph_node_map_element_t elm = xbt_new0(struct graph_node_map_element, sizeof(struct graph_node_map_element));
709   elm->node = node;
710   xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);
711
712   return node;
713 }
714
715 static graph_node_map_element_t graph_node_map_search(int id) {
716   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
717
718   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));
719
720   return elm;
721 }
722
723 /*
724  * Parsing
725  */
726 static void route_new_dijkstra(int src_id, int dst_id, void* link) {
727   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
728
729   xbt_node_t src = NULL;
730   xbt_node_t dst = NULL;
731   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));
732   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));
733
734   if(src_elm)
735     src = src_elm->node;
736
737   if(dst_elm)
738     dst = dst_elm->node;
739
740   //add nodes if they don't exist in the graph
741   if(src_id == dst_id && src == NULL && dst == NULL) {
742     src = route_graph_new_node(src_id, -1);
743     dst = src;
744   } else {
745     if(src == NULL) {
746       src = route_graph_new_node(src_id, -1);
747     }
748         
749     if(dst == NULL) {
750       dst = route_graph_new_node(dst_id, -1);
751     }
752   }
753
754   //add link as edge to graph
755   xbt_graph_new_edge(routing->route_graph, src, dst, link);
756   
757 }
758
759 static void add_loopback_dijkstra(void) {
760   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
761
762         xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
763         
764         xbt_node_t node = NULL;
765         unsigned int cursor2;
766         xbt_dynar_foreach(nodes, cursor2, node) {
767                 xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node); 
768                 xbt_edge_t edge = NULL;
769                 unsigned int cursor;
770         
771                 int found = 0;
772                 xbt_dynar_foreach(out_edges, cursor, edge) {
773                         xbt_node_t other_node = xbt_graph_edge_get_target(edge);
774                         if(other_node == node) {
775                                 found = 1;
776                                 break;
777                         }
778                 }
779
780                 if(!found)
781                         xbt_graph_new_edge(routing->route_graph, node, node, &routing->loopback);
782         }
783 }
784
785 static void routing_dijkstra_parse_end(void) {
786   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
787   int nb_link = 0;
788   xbt_dict_cursor_t cursor = NULL;
789   char *key, *data, *end;
790   const char *sep = "#";
791   xbt_dynar_t links, keys;
792
793   /* Create the topology graph */
794   routing->route_graph = xbt_graph_new_graph(1, NULL);
795   routing->graph_node_map = xbt_dict_new();
796   routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
797   if(routing->cached)
798     routing->route_cache = xbt_dict_new();
799
800
801   /* Put the routes in position */
802   xbt_dict_foreach(route_table, cursor, key, data) {
803     nb_link = 0;
804     links = (xbt_dynar_t) data;
805     keys = xbt_str_split_str(key, sep);
806
807     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
808     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
809     xbt_dynar_free(&keys);
810
811     DEBUG4("Handle %d %d (from %d hosts): %ld links",
812         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
813
814     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);
815
816     char* link_name = xbt_dynar_getfirst_as(links, char*);
817     void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
818     if (link)
819       route_new_dijkstra(src_id,dst_id,link);
820     else
821       THROW1(mismatch_error,0,"Link %s not found", link_name);
822     
823   }
824
825   /* Add the loopback if needed */
826   add_loopback_dijkstra();
827
828   /* initialize graph indexes in nodes after graph has been built */
829   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
830
831   xbt_node_t node = NULL;
832   unsigned int cursor2;
833   xbt_dynar_foreach(nodes, cursor2, node) {
834     graph_node_data_t data = xbt_graph_node_get_data(node);
835     data->graph_id = cursor2;
836   }
837
838 }
839
840 /*
841  * Business methods
842  */
843 static xbt_dynar_t routing_dijkstra_get_route(int src_id,int dst_id) {
844
845   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
846   int * pred_arr = NULL;
847   
848   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
849
850   /*Use the graph_node id mapping set to quickly find the nodes */
851   graph_node_map_element_t src_elm = graph_node_map_search(src_id);
852   graph_node_map_element_t dst_elm = graph_node_map_search(dst_id);
853   xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", src_id, dst_id);
854   int src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id;
855   int dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id;
856
857   route_cache_element_t elm = NULL;
858   if(routing->cached) {
859     /*check if there is a cached predecessor list avail */
860     elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int));
861   }
862
863   if(elm) { //cached mode and cache hit
864     pred_arr = elm->pred_arr;
865   } else { //not cached mode or cache miss
866     double * cost_arr = NULL;
867     xbt_heap_t pqueue = NULL;
868     int i = 0;
869
870     int nr_nodes = xbt_dynar_length(nodes);
871     cost_arr = xbt_new0(double, nr_nodes); //link cost from src to other hosts
872     pred_arr = xbt_new0(int, nr_nodes); //predecessors in path from src
873     pqueue = xbt_heap_new(nr_nodes, free);
874
875     //initialize
876     cost_arr[src_node_id] = 0.0;
877
878     for(i = 0; i < nr_nodes; i++) {
879       if(i != src_node_id) {
880         cost_arr[i] = DBL_MAX;
881       }
882
883       pred_arr[i] = 0;
884
885       //initialize priority queue
886       int * nodeid = xbt_new0(int, 1);
887       *nodeid = i;
888       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
889
890     }
891
892     // apply dijkstra using the indexes from the graph's node array
893     while(xbt_heap_size(pqueue) > 0) {
894       int * v_id = xbt_heap_pop(pqueue);
895       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
896       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node); 
897       xbt_edge_t edge = NULL;
898       unsigned int cursor;
899
900       xbt_dynar_foreach(out_edges, cursor, edge) {
901         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
902         graph_node_data_t data = xbt_graph_node_get_data(u_node);
903         int u_id = data->graph_id;
904         int cost_v_u = 1; //fixed link cost for now
905
906         if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
907           pred_arr[u_id] = *v_id;
908           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
909           int * nodeid = xbt_new0(int, 1);
910           *nodeid = u_id;
911           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
912         }
913       }
914
915       //free item popped from pqueue
916       free(v_id);
917     }
918
919     free(cost_arr);
920     xbt_heap_free(pqueue);
921
922   }
923
924   //compose route path with links
925   xbt_dynar_reset(routing->last_route);
926
927   int v;
928   int size = 0;
929   for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
930     xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
931     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
932     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
933
934     xbt_assert2(edge != NULL, "no route between host %d and %d", src_id, dst_id);
935
936     void * link = xbt_graph_edge_get_data(edge);
937     xbt_dynar_unshift(routing->last_route, &link);
938     size++;
939   }
940
941
942   if(routing->cached && elm == NULL) {
943     //add to predecessor list of the current src-host to cache
944     elm = xbt_new0(struct route_cache_element, sizeof(struct route_cache_element));
945     elm->pred_arr = pred_arr;
946     elm->size = size;
947     xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free);
948   }
949
950   if(!routing->cached)
951     free(pred_arr);
952
953   return routing->last_route;
954 }
955
956
957 static void routing_dijkstra_finalize(void) {
958   routing_dijkstra_t routing = (routing_dijkstra_t)used_routing;
959
960   if (routing) {
961     xbt_graph_free_graph(routing->route_graph, &free, NULL, &free);
962     xbt_dict_free(&routing->graph_node_map);
963     if(routing->cached)
964       xbt_dict_free(&routing->route_cache);
965     xbt_dynar_free(&routing->last_route);
966     xbt_dict_free(&used_routing->host_id);
967     free(routing);
968     routing=NULL;
969   }
970 }
971
972 static xbt_dict_t routing_dijkstraboth_get_onelink_routes(void){
973   xbt_assert0(0,"The get_onelink_routes feature is not supported in routing model dijkstraboth");
974 }
975
976 static int routing_dijkstraboth_is_router(int id){
977   xbt_assert0(0,"The get_is_router feature is not supported in routing model dijkstraboth");
978 }
979
980 /*
981  *
982  */
983 static void routing_model_dijkstraboth_create(size_t size_of_link,void *loopback, int cached) {
984   /* initialize our structure */
985   routing_dijkstra_t routing = xbt_new0(s_routing_dijkstra_t,1);
986   routing->generic_routing.name = "Dijkstra";
987   routing->generic_routing.host_count = 0;
988   routing->generic_routing.get_route = routing_dijkstra_get_route;
989   routing->generic_routing.get_onelink_routes = routing_dijkstraboth_get_onelink_routes;
990   routing->generic_routing.is_router = routing_dijkstraboth_is_router;
991   routing->generic_routing.finalize = routing_dijkstra_finalize;
992   routing->size_of_link = size_of_link;
993   routing->loopback = loopback;
994   routing->cached = cached;
995
996   /* Set it in position */
997   used_routing = (routing_t) routing;
998
999   /* Setup the parsing callbacks we need */
1000   routing->generic_routing.host_id = xbt_dict_new();
1001   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
1002   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_dijkstra_parse_end);
1003   surfxml_add_callback(STag_surfxml_route_cb_list,
1004       &routing_full_parse_Sroute_set_endpoints);
1005   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
1006   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);
1007 }
1008
1009 static void routing_model_dijkstra_create(size_t size_of_link,void *loopback) {
1010   routing_model_dijkstraboth_create(size_of_link, loopback, 0);
1011 }
1012
1013 static void routing_model_dijkstracache_create(size_t size_of_link,void *loopback) {
1014   routing_model_dijkstraboth_create(size_of_link, loopback, 1);
1015 }
1016
1017 /* ************************************************** */
1018 /* ********** NO ROUTING **************************** */
1019
1020
1021 static void routing_none_finalize(void) {
1022   if (used_routing) {
1023     xbt_dict_free(&used_routing->host_id);
1024     free(used_routing);
1025     used_routing=NULL;
1026   }
1027 }
1028
1029 static void routing_model_none_create(size_t size_of_link,void *loopback) {
1030   routing_t routing = xbt_new0(s_routing_t,1);
1031   INFO0("Null routing");
1032   routing->name = "none";
1033   routing->host_count = 0;
1034   routing->host_id = xbt_dict_new();
1035   routing->get_onelink_routes = NULL;
1036   routing->is_router = NULL;
1037   routing->get_route = NULL;
1038
1039   routing->finalize = routing_none_finalize;
1040
1041   /* Set it in position */
1042   used_routing = (routing_t) routing;
1043 }