1 /* Copyright (c) 2009 The SimGrid team. All rights reserved. */
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. */
7 #include "surf_private.h"
10 #include "xbt/config.h"
11 #include "xbt/graph.h"
14 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf");
16 routing_t used_routing = NULL;
18 /* Prototypes of each model */
19 static void routing_model_full_create(size_t size_of_link,void *loopback);
20 static void routing_model_floyd_create(size_t size_of_link, void*loopback);
21 static void routing_model_dijkstra_create(size_t size_of_link, void*loopback);
22 static void routing_model_dijkstracache_create(size_t size_of_link, void*loopback);
23 static void routing_model_none_create(size_t size_of_link, void*loopback);
25 /* Definition of each model */
29 void (*fun)(size_t,void*);
31 struct model_type models[] =
32 { {"Full", "Full routing data (fast, large memory requirements, fully expressive)", routing_model_full_create },
33 {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)", routing_model_floyd_create },
34 {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)", routing_model_dijkstra_create },
35 {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)", routing_model_dijkstracache_create },
36 {"none", "No routing (usable with Constant network only)", routing_model_none_create },
40 void routing_model_create(size_t size_of_links, void* loopback) {
42 char * wanted=xbt_cfg_get_string(_surf_cfg_set,"routing");
44 for (cpt=0;models[cpt].name;cpt++) {
45 if (!strcmp(wanted,models[cpt].name)) {
46 (*(models[cpt].fun))(size_of_links,loopback);
50 fprintf(stderr,"Routing model %s not found. Existing models:\n",wanted);
51 for (cpt=0;models[cpt].name;cpt++)
52 if (!strcmp(wanted,models[cpt].name))
53 fprintf(stderr," %s: %s\n",models[cpt].name,models[cpt].desc);
57 /* ************************************************************************** */
58 /* *************************** FULL ROUTING ********************************* */
60 s_routing_t generic_routing;
61 xbt_dynar_t *routing_table;
64 } s_routing_full_t,*routing_full_t;
66 #define ROUTE_FULL(i,j) ((routing_full_t)used_routing)->routing_table[(i)+(j)*(used_routing)->host_count]
71 static void routing_full_parse_Shost(void) {
72 int *val = xbt_malloc(sizeof(int));
73 DEBUG2("Seen host %s (#%d)",A_surfxml_host_id,used_routing->host_count);
74 *val = used_routing->host_count++;
75 xbt_dict_set(used_routing->host_id,A_surfxml_host_id,val,xbt_free);
77 static int src_id = -1;
78 static int dst_id = -1;
79 static void routing_full_parse_Sroute_set_endpoints(void)
81 src_id = *(int*)xbt_dict_get(used_routing->host_id,A_surfxml_route_src);
82 dst_id = *(int*)xbt_dict_get(used_routing->host_id,A_surfxml_route_dst);
83 DEBUG4("Route %s %d -> %s %d",A_surfxml_route_src,src_id,A_surfxml_route_dst,dst_id);
84 route_action = A_surfxml_route_action;
86 static void routing_full_parse_Eroute(void)
89 if (src_id != -1 && dst_id != -1) {
90 name = bprintf("%x#%x", src_id, dst_id);
91 manage_route(route_table, name, route_action, 0);
96 /* Cluster tag functions */
98 static void routing_full_parse_change_cpu_data(const char *hostName,
99 const char *surfxml_host_power,
100 const char *surfxml_host_availability,
101 const char *surfxml_host_availability_file,
102 const char *surfxml_host_state_file)
106 SURFXML_BUFFER_SET(host_id, hostName);
107 SURFXML_BUFFER_SET(host_power, surfxml_host_power /*hostPower */ );
108 SURFXML_BUFFER_SET(host_availability, surfxml_host_availability);
109 SURFXML_BUFFER_SET(host_availability_file, surfxml_host_availability_file);
110 SURFXML_BUFFER_SET(host_state_file, surfxml_host_state_file);
113 static void routing_full_parse_change_link_data(const char *linkName,
114 const char *surfxml_link_bandwidth,
115 const char *surfxml_link_bandwidth_file,
116 const char *surfxml_link_latency,
117 const char *surfxml_link_latency_file,
118 const char *surfxml_link_state_file)
122 SURFXML_BUFFER_SET(link_id, linkName);
123 SURFXML_BUFFER_SET(link_bandwidth, surfxml_link_bandwidth);
124 SURFXML_BUFFER_SET(link_bandwidth_file, surfxml_link_bandwidth_file);
125 SURFXML_BUFFER_SET(link_latency, surfxml_link_latency);
126 SURFXML_BUFFER_SET(link_latency_file, surfxml_link_latency_file);
127 SURFXML_BUFFER_SET(link_state_file, surfxml_link_state_file);
130 static void routing_full_parse_Scluster(void)
132 static int AX_ptr = 0;
134 char *cluster_id = A_surfxml_cluster_id;
135 char *cluster_prefix = A_surfxml_cluster_prefix;
136 char *cluster_suffix = A_surfxml_cluster_suffix;
137 char *cluster_radical = A_surfxml_cluster_radical;
138 char *cluster_power = A_surfxml_cluster_power;
139 char *cluster_bw = A_surfxml_cluster_bw;
140 char *cluster_lat = A_surfxml_cluster_lat;
141 char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
142 char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
145 surfxml_bufferstack_push(1);
148 SURFXML_BUFFER_SET(set_id, cluster_id);
149 SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
150 SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
151 SURFXML_BUFFER_SET(set_radical, cluster_radical);
153 SURFXML_START_TAG(set);
154 SURFXML_END_TAG(set);
157 SURFXML_BUFFER_SET(foreach_set_id, cluster_id);
159 SURFXML_START_TAG(foreach);
161 /* Make host for the foreach */
162 routing_full_parse_change_cpu_data("$1", cluster_power, "1.0", "", "");
163 A_surfxml_host_state = A_surfxml_host_state_ON;
165 SURFXML_START_TAG(host);
166 SURFXML_END_TAG(host);
168 /* Make link for the foreach */
169 routing_full_parse_change_link_data("$1", cluster_bw, "", cluster_lat, "", "");
170 A_surfxml_link_state = A_surfxml_link_state_ON;
171 A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
173 SURFXML_START_TAG(link);
174 SURFXML_END_TAG(link);
176 SURFXML_END_TAG(foreach);
178 /* Make backbone link */
179 backbone_name = bprintf("%s_bb", cluster_id);
180 routing_full_parse_change_link_data(backbone_name, cluster_bb_bw, "", cluster_bb_lat, "",
182 A_surfxml_link_state = A_surfxml_link_state_ON;
183 A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_FATPIPE;
185 SURFXML_START_TAG(link);
186 SURFXML_END_TAG(link);
188 /* Make route multi with the outside world, i.e. cluster->$* */
189 SURFXML_BUFFER_SET(route_c_multi_src, cluster_id);
190 SURFXML_BUFFER_SET(route_c_multi_dst, "$*");
191 A_surfxml_route_c_multi_symmetric = A_surfxml_route_c_multi_symmetric_NO;
192 A_surfxml_route_c_multi_action = A_surfxml_route_c_multi_action_OVERRIDE;
194 SURFXML_START_TAG(route_c_multi);
196 SURFXML_BUFFER_SET(link_c_ctn_id, "$src");
198 SURFXML_START_TAG(link_c_ctn);
199 SURFXML_END_TAG(link_c_ctn);
201 SURFXML_END_TAG(route_c_multi);
203 /* Make route multi between cluster hosts, i.e. cluster->cluster */
204 SURFXML_BUFFER_SET(route_c_multi_src, cluster_id);
205 SURFXML_BUFFER_SET(route_c_multi_dst, cluster_id);
206 A_surfxml_route_c_multi_action = A_surfxml_route_c_multi_action_POSTPEND;
207 A_surfxml_route_c_multi_symmetric = A_surfxml_route_c_multi_symmetric_NO;
209 SURFXML_START_TAG(route_c_multi);
211 SURFXML_BUFFER_SET(link_c_ctn_id, backbone_name);
213 SURFXML_START_TAG(link_c_ctn);
214 SURFXML_END_TAG(link_c_ctn);
216 SURFXML_END_TAG(route_c_multi);
221 surfxml_bufferstack_pop(1);
225 static void routing_full_parse_end(void) {
226 routing_full_t routing = (routing_full_t) used_routing;
228 unsigned int cpt = 0;
229 xbt_dict_cursor_t cursor = NULL;
230 char *key, *data, *end;
231 const char *sep = "#";
232 xbt_dynar_t links, keys;
233 char *link_name = NULL;
236 int host_count = routing->generic_routing.host_count;
238 /* Create the routing table */
239 routing->routing_table = xbt_new0(xbt_dynar_t, host_count * host_count);
240 for (i=0;i<host_count;i++)
241 for (j=0;j<host_count;j++)
242 ROUTE_FULL(i,j) = xbt_dynar_new(routing->size_of_link,NULL);
244 /* Put the routes in position */
245 xbt_dict_foreach(route_table, cursor, key, data) {
247 links = (xbt_dynar_t) data;
248 keys = xbt_str_split_str(key, sep);
250 src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
251 dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
252 xbt_dynar_free(&keys);
254 DEBUG4("Handle %d %d (from %d hosts): %ld links",
255 src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
256 xbt_dynar_foreach(links, cpt, link_name) {
257 void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
259 xbt_dynar_push(ROUTE_FULL(src_id,dst_id),&link);
261 THROW1(mismatch_error,0,"Link %s not found", link_name);
265 /* Add the loopback if needed */
266 for (i = 0; i < host_count; i++)
267 if (!xbt_dynar_length(ROUTE_FULL(i, i)))
268 xbt_dynar_push(ROUTE_FULL(i,i),&routing->loopback);
270 /* Shrink the dynar routes (save unused slots) */
271 for (i=0;i<host_count;i++)
272 for (j=0;j<host_count;j++)
273 xbt_dynar_shrink(ROUTE_FULL(i,j),0);
279 static xbt_dynar_t routing_full_get_route(int src,int dst) {
280 return ROUTE_FULL(src,dst);
283 static void routing_full_finalize(void) {
284 routing_full_t routing = (routing_full_t)used_routing;
288 for (i = 0; i < used_routing->host_count; i++)
289 for (j = 0; j < used_routing->host_count; j++)
290 xbt_dynar_free(&ROUTE_FULL(i, j));
291 free(routing->routing_table);
292 xbt_dict_free(&used_routing->host_id);
298 static void routing_model_full_create(size_t size_of_link,void *loopback) {
299 /* initialize our structure */
300 routing_full_t routing = xbt_new0(s_routing_full_t,1);
301 routing->generic_routing.name = "Full";
302 routing->generic_routing.host_count = 0;
303 routing->generic_routing.get_route = routing_full_get_route;
304 routing->generic_routing.finalize = routing_full_finalize;
305 routing->size_of_link = size_of_link;
306 routing->loopback = loopback;
308 /* Set it in position */
309 used_routing = (routing_t) routing;
311 /* Setup the parsing callbacks we need */
312 routing->generic_routing.host_id = xbt_dict_new();
313 surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
314 surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_full_parse_end);
315 surfxml_add_callback(STag_surfxml_route_cb_list,
316 &routing_full_parse_Sroute_set_endpoints);
317 surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
318 surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_full_parse_Scluster);
321 /* ************************************************************************** */
323 static void routing_shortest_path_parse_Scluster(void)
325 static int AX_ptr = 0;
327 char *cluster_id = A_surfxml_cluster_id;
328 char *cluster_prefix = A_surfxml_cluster_prefix;
329 char *cluster_suffix = A_surfxml_cluster_suffix;
330 char *cluster_radical = A_surfxml_cluster_radical;
331 char *cluster_power = A_surfxml_cluster_power;
332 char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
333 char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
336 surfxml_bufferstack_push(1);
339 SURFXML_BUFFER_SET(set_id, cluster_id);
340 SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
341 SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
342 SURFXML_BUFFER_SET(set_radical, cluster_radical);
344 SURFXML_START_TAG(set);
345 SURFXML_END_TAG(set);
348 SURFXML_BUFFER_SET(foreach_set_id, cluster_id);
350 SURFXML_START_TAG(foreach);
352 /* Make host for the foreach */
353 routing_full_parse_change_cpu_data("$1", cluster_power, "1.0", "", "");
354 A_surfxml_host_state = A_surfxml_host_state_ON;
356 SURFXML_START_TAG(host);
357 SURFXML_END_TAG(host);
359 SURFXML_END_TAG(foreach);
361 /* Make backbone link */
362 backbone_name = bprintf("%s_bb", cluster_id);
363 routing_full_parse_change_link_data(backbone_name, cluster_bb_bw, "", cluster_bb_lat, "",
365 A_surfxml_link_state = A_surfxml_link_state_ON;
366 A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_FATPIPE;
368 SURFXML_START_TAG(link);
369 SURFXML_END_TAG(link);
374 surfxml_bufferstack_pop(1);
377 /* ************************************************************************** */
378 /* *************************** FLOYD ROUTING ********************************* */
380 s_routing_t generic_routing;
381 int *predecessor_table;
383 xbt_dynar_t last_route;
386 } s_routing_floyd_t,*routing_floyd_t;
388 #define FLOYD_COST(i,j) cost_table[(i)+(j)*(used_routing)->host_count]
389 #define FLOYD_PRED(i,j) ((routing_floyd_t)used_routing)->predecessor_table[(i)+(j)*(used_routing)->host_count]
390 #define FLOYD_LINK(i,j) ((routing_floyd_t)used_routing)->link_table[(i)+(j)*(used_routing)->host_count]
392 static void routing_floyd_parse_end(void) {
394 routing_floyd_t routing = (routing_floyd_t) used_routing;
396 void* link_list = NULL;
398 xbt_dict_cursor_t cursor = NULL;
399 char *key,*data, *end;
400 const char *sep = "#";
401 xbt_dynar_t links, keys;
405 int host_count = routing->generic_routing.host_count;
407 /* Create Cost, Predecessor and Link tables */
408 cost_table = xbt_new0(double, host_count * host_count); //link cost from host to host
409 routing->predecessor_table = xbt_new0(int, host_count*host_count); //predecessor host numbers
410 routing->link_table = xbt_new0(void*,host_count*host_count); //actual link between src and dst
411 routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
413 /* Initialize costs and predecessors*/
414 for(i = 0; i<host_count;i++)
415 for(j = 0; j<host_count;j++) {
416 FLOYD_COST(i,j) = DBL_MAX;
417 FLOYD_PRED(i,j) = -1;
420 /* Put the routes in position */
421 xbt_dict_foreach(route_table, cursor, key, data) {
423 links = (xbt_dynar_t)data;
424 keys = xbt_str_split_str(key, sep);
427 src_id = strtol(xbt_dynar_get_as(keys, 0, char*), &end, 16);
428 dst_id = strtol(xbt_dynar_get_as(keys, 1, char*), &end, 16);
429 xbt_dynar_free(&keys);
431 DEBUG4("Handle %d %d (from %d hosts): %ld links",
432 src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
433 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);
435 char * link_name = xbt_dynar_getfirst_as(links, char*);
436 void * link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
440 THROW1(mismatch_error,0,"Link %s not found", link_name);
443 FLOYD_LINK(src_id,dst_id) = link_list;
444 FLOYD_PRED(src_id, dst_id) = src_id;
447 FLOYD_COST(src_id, dst_id) = 1; // assume 1 for now
451 /* Add the loopback if needed */
452 for (i = 0; i < host_count; i++)
453 if (!FLOYD_PRED(i, i)) {
454 FLOYD_PRED(i, i) = i;
455 FLOYD_COST(i, i) = 1;
456 FLOYD_LINK(i, i) = routing->loopback;
460 //Calculate path costs
462 for(c=0;c<host_count;c++) {
463 for(a=0;a<host_count;a++) {
464 for(b=0;b<host_count;b++) {
465 if(FLOYD_COST(a,c) < DBL_MAX && FLOYD_COST(c,b) < DBL_MAX) {
466 if(FLOYD_COST(a,b) == DBL_MAX || (FLOYD_COST(a,c)+FLOYD_COST(c,b) < FLOYD_COST(a,b))) {
467 FLOYD_COST(a,b) = FLOYD_COST(a,c)+FLOYD_COST(c,b);
468 FLOYD_PRED(a,b) = FLOYD_PRED(c,b);
482 static xbt_dynar_t routing_floyd_get_route(int src_id,int dst_id) {
484 routing_floyd_t routing = (routing_floyd_t) used_routing;
489 xbt_dynar_reset(routing->last_route);
493 pred = FLOYD_PRED(src_id, pred);
495 if(pred == -1) // if no pred in route -> no route to host
498 xbt_dynar_unshift(routing->last_route, &FLOYD_LINK(pred,prev_pred));
500 } while(pred != src_id);
502 xbt_assert2(pred != -1, "no route from host %d to %d", src_id, dst_id);
504 return routing->last_route;
507 static void routing_floyd_finalize(void) {
508 routing_floyd_t routing = (routing_floyd_t)used_routing;
511 free(routing->link_table);
512 free(routing->predecessor_table);
513 xbt_dynar_free(&routing->last_route);
514 xbt_dict_free(&used_routing->host_id);
520 static void routing_model_floyd_create(size_t size_of_link,void *loopback) {
521 /* initialize our structure */
522 routing_floyd_t routing = xbt_new0(s_routing_floyd_t,1);
523 routing->generic_routing.name = "Floyd";
524 routing->generic_routing.host_count = 0;
525 routing->generic_routing.host_id = xbt_dict_new();
526 routing->generic_routing.get_route = routing_floyd_get_route;
527 routing->generic_routing.finalize = routing_floyd_finalize;
528 routing->size_of_link = size_of_link;
529 routing->loopback = loopback;
531 /* Set it in position */
532 used_routing = (routing_t) routing;
534 /* Setup the parsing callbacks we need */
535 surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
536 surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_floyd_parse_end);
537 surfxml_add_callback(STag_surfxml_route_cb_list,
538 &routing_full_parse_Sroute_set_endpoints);
539 surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
540 surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);
544 /* ************************************************************************** */
545 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
547 s_routing_t generic_routing;
548 xbt_graph_t route_graph;
549 xbt_dict_t graph_node_map;
550 xbt_dict_t route_cache;
551 xbt_dynar_t last_route;
555 } s_routing_dijkstra_t,*routing_dijkstra_t;
558 typedef struct graph_node_data {
560 int graph_id; //used for caching internal graph id's
561 } s_graph_node_data_t, * graph_node_data_t;
563 typedef struct graph_node_map_element {
565 } s_graph_node_map_element_t, * graph_node_map_element_t;
567 typedef struct route_cache_element {
570 } s_route_cache_element_t, * route_cache_element_t;
575 static void route_cache_elem_free(void *e) {
576 route_cache_element_t elm=(route_cache_element_t)e;
584 static void graph_node_map_elem_free(void *e) {
585 graph_node_map_element_t elm = (graph_node_map_element_t)e;
595 static xbt_node_t route_graph_new_node(int id, int graph_id) {
596 routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
598 graph_node_data_t data = xbt_new0(struct graph_node_data, sizeof(struct graph_node_data));
600 data->graph_id = graph_id;
601 xbt_node_t node = xbt_graph_new_node(routing->route_graph, data);
603 graph_node_map_element_t elm = xbt_new0(struct graph_node_map_element, sizeof(struct graph_node_map_element));
605 xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);
610 static graph_node_map_element_t graph_node_map_search(int id) {
611 routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
613 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));
621 static void route_new_dijkstra(int src_id, int dst_id, void* link) {
622 routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
624 xbt_node_t src = NULL;
625 xbt_node_t dst = NULL;
626 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));
627 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));
635 //add nodes if they don't exist in the graph
636 if(src_id == dst_id && src == NULL && dst == NULL) {
637 src = route_graph_new_node(src_id, -1);
641 src = route_graph_new_node(src_id, -1);
645 dst = route_graph_new_node(dst_id, -1);
649 //add link as edge to graph
650 xbt_graph_new_edge(routing->route_graph, src, dst, link);
654 static void add_loopback_dijkstra(void) {
655 routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
657 xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
659 xbt_node_t node = NULL;
660 unsigned int cursor2;
661 xbt_dynar_foreach(nodes, cursor2, node) {
662 xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
663 xbt_edge_t edge = NULL;
667 xbt_dynar_foreach(out_edges, cursor, edge) {
668 xbt_node_t other_node = xbt_graph_edge_get_target(edge);
669 if(other_node == node) {
676 xbt_graph_new_edge(routing->route_graph, node, node, &routing->loopback);
680 static void routing_dijkstra_parse_end(void) {
681 routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
683 xbt_dict_cursor_t cursor = NULL;
684 char *key, *data, *end;
685 const char *sep = "#";
686 xbt_dynar_t links, keys;
688 /* Create the topology graph */
689 routing->route_graph = xbt_graph_new_graph(1, NULL);
690 routing->graph_node_map = xbt_dict_new();
691 routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
693 routing->route_cache = xbt_dict_new();
696 /* Put the routes in position */
697 xbt_dict_foreach(route_table, cursor, key, data) {
699 links = (xbt_dynar_t) data;
700 keys = xbt_str_split_str(key, sep);
702 src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
703 dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
704 xbt_dynar_free(&keys);
706 DEBUG4("Handle %d %d (from %d hosts): %ld links",
707 src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
709 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);
711 char* link_name = xbt_dynar_getfirst_as(links, char*);
712 void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
714 route_new_dijkstra(src_id,dst_id,link);
716 THROW1(mismatch_error,0,"Link %s not found", link_name);
720 /* Add the loopback if needed */
721 add_loopback_dijkstra();
723 /* initialize graph indexes in nodes after graph has been built */
724 xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
726 xbt_node_t node = NULL;
727 unsigned int cursor2;
728 xbt_dynar_foreach(nodes, cursor2, node) {
729 graph_node_data_t data = xbt_graph_node_get_data(node);
730 data->graph_id = cursor2;
738 static xbt_dynar_t routing_dijkstra_get_route(int src_id,int dst_id) {
740 routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
741 int * pred_arr = NULL;
743 xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
745 /*Use the graph_node id mapping set to quickly find the nodes */
746 graph_node_map_element_t src_elm = graph_node_map_search(src_id);
747 graph_node_map_element_t dst_elm = graph_node_map_search(dst_id);
748 xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", src_id, dst_id);
749 int src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id;
750 int dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id;
752 route_cache_element_t elm = NULL;
753 if(routing->cached) {
754 /*check if there is a cached predecessor list avail */
755 elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int));
758 if(elm) { //cached mode and cache hit
759 pred_arr = elm->pred_arr;
760 } else { //not cached mode or cache miss
761 double * cost_arr = NULL;
762 xbt_heap_t pqueue = NULL;
765 int nr_nodes = xbt_dynar_length(nodes);
766 cost_arr = xbt_new0(double, nr_nodes); //link cost from src to other hosts
767 pred_arr = xbt_new0(int, nr_nodes); //predecessors in path from src
768 pqueue = xbt_heap_new(nr_nodes, free);
771 cost_arr[src_node_id] = 0.0;
773 for(i = 0; i < nr_nodes; i++) {
774 if(i != src_node_id) {
775 cost_arr[i] = DBL_MAX;
780 //initialize priority queue
781 int * nodeid = xbt_new0(int, 1);
783 xbt_heap_push(pqueue, nodeid, cost_arr[i]);
787 // apply dijkstra using the indexes from the graph's node array
788 while(xbt_heap_size(pqueue) > 0) {
789 int * v_id = xbt_heap_pop(pqueue);
790 xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
791 xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
792 xbt_edge_t edge = NULL;
795 xbt_dynar_foreach(out_edges, cursor, edge) {
796 xbt_node_t u_node = xbt_graph_edge_get_target(edge);
797 graph_node_data_t data = xbt_graph_node_get_data(u_node);
798 int u_id = data->graph_id;
799 int cost_v_u = 1; //fixed link cost for now
801 if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
802 pred_arr[u_id] = *v_id;
803 cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
804 int * nodeid = xbt_new0(int, 1);
806 xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
810 //free item popped from pqueue
815 xbt_heap_free(pqueue);
819 //compose route path with links
820 xbt_dynar_reset(routing->last_route);
824 for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
825 xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
826 xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
827 xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
829 xbt_assert2(edge != NULL, "no route between host %d and %d", src_id, dst_id);
831 void * link = xbt_graph_edge_get_data(edge);
832 xbt_dynar_unshift(routing->last_route, &link);
837 if(routing->cached && elm == NULL) {
838 //add to predecessor list of the current src-host to cache
839 elm = xbt_new0(struct route_cache_element, sizeof(struct route_cache_element));
840 elm->pred_arr = pred_arr;
842 xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free);
848 return routing->last_route;
852 static void routing_dijkstra_finalize(void) {
853 routing_dijkstra_t routing = (routing_dijkstra_t)used_routing;
856 xbt_graph_free_graph(routing->route_graph, &free, NULL, &free);
857 xbt_dict_free(&routing->graph_node_map);
859 xbt_dict_free(&routing->route_cache);
860 xbt_dynar_free(&routing->last_route);
861 xbt_dict_free(&used_routing->host_id);
870 static void routing_model_dijkstraboth_create(size_t size_of_link,void *loopback, int cached) {
871 /* initialize our structure */
872 routing_dijkstra_t routing = xbt_new0(s_routing_dijkstra_t,1);
873 routing->generic_routing.name = "Dijkstra";
874 routing->generic_routing.host_count = 0;
875 routing->generic_routing.get_route = routing_dijkstra_get_route;
876 routing->generic_routing.finalize = routing_dijkstra_finalize;
877 routing->size_of_link = size_of_link;
878 routing->loopback = loopback;
879 routing->cached = cached;
881 /* Set it in position */
882 used_routing = (routing_t) routing;
884 /* Setup the parsing callbacks we need */
885 routing->generic_routing.host_id = xbt_dict_new();
886 surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
887 surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_dijkstra_parse_end);
888 surfxml_add_callback(STag_surfxml_route_cb_list,
889 &routing_full_parse_Sroute_set_endpoints);
890 surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
891 surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);
894 static void routing_model_dijkstra_create(size_t size_of_link,void *loopback) {
895 routing_model_dijkstraboth_create(size_of_link, loopback, 0);
898 static void routing_model_dijkstracache_create(size_t size_of_link,void *loopback) {
899 routing_model_dijkstraboth_create(size_of_link, loopback, 1);
902 /* ************************************************** */
903 /* ********** NO ROUTING **************************** */
905 static void routing_none_finalize(void) {
907 xbt_dict_free(&used_routing->host_id);
913 static void routing_model_none_create(size_t size_of_link,void *loopback) {
914 routing_t routing = xbt_new0(s_routing_t,1);
915 INFO0("Null routing");
916 routing->name = "none";
917 routing->host_count = 0;
918 routing->host_id = xbt_dict_new();
919 routing->get_route = NULL;
920 routing->finalize = routing_none_finalize;
922 /* Set it in position */
923 used_routing = (routing_t) routing;