Logo AND Algorithmique Numérique Distribuée

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