From: navarrop Date: Tue, 28 Sep 2010 08:52:34 +0000 (+0000) Subject: add the dijkstra routing and cache too X-Git-Tag: v3_5~588 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/e42e598c9498ad5c9eb99938741933d94beb8edb add the dijkstra routing and cache too git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@8236 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- diff --git a/src/surf/surf_routing.c b/src/surf/surf_routing.c index d8f8b7cfdf..4a79babde4 100644 --- a/src/surf/surf_routing.c +++ b/src/surf/surf_routing.c @@ -13,7 +13,6 @@ #include "xbt/set.h" XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf"); - //////////////////////////////////////////////////////////////////////////////// // HERE START THE NEW CODE @@ -21,7 +20,7 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf"); //...... DEBUG ONLY .... // static void print_tree(routing_component_t rc); -static void print_global(); +static void print_global(void); static void print_AS_start(void); static void print_AS_end(void); static void print_host(void); @@ -50,15 +49,12 @@ static void model_floyd_load(void); /* load parse functions for floyd routing static void model_floyd_unload(void); /* unload parse functions for floyd routing model */ static void model_floyd_end(void); /* finalize the creation of floyd routing model */ -static void* model_dijkstra_create(void); /* create structures for dijkstra routing model */ -static void model_dijkstra_load(void); /* load parse functions for dijkstra routing model */ -static void model_dijkstra_unload(void); /* unload parse functions for dijkstra routing model */ -static void model_dijkstra_end(void); /* finalize the creation of dijkstra routing model */ - +static void* model_dijkstra_both_create(int cached); /* create by calling dijkstra or dijkstracache */ +static void* model_dijkstra_create(void); /* create structures for dijkstra routing model */ static void* model_dijkstracache_create(void); /* create structures for dijkstracache routing model */ -static void model_dijkstracache_load(void); /* load parse functions for dijkstracache routing model */ -static void model_dijkstracache_unload(void); /* unload parse functions for dijkstracache routing model */ -static void model_dijkstracache_end(void); /* finalize the creation of dijkstracache routing model */ +static void model_dijkstra_both_load(void); /* load parse functions for dijkstra routing model */ +static void model_dijkstra_both_unload(void); /* unload parse functions for dijkstra routing model */ +static void model_dijkstra_both_end(void); /* finalize the creation of dijkstra routing model */ static void* model_none_create(void); /* none routing model */ static void model_none_load(void); /* none routing model */ @@ -74,6 +70,7 @@ static void model_none_end(void); /* none routing model */ // SURF_MODEL_NONE // } e_surf_model_type_t; +/* this lines are olny for replace use like index in the model table */ #define SURF_MODEL_FULL 0 #define SURF_MODEL_FLOYD 1 #define SURF_MODEL_DIJKSTRA 2 @@ -87,9 +84,9 @@ struct s_model_type routing_models[] = {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)", model_floyd_create, model_floyd_load, model_floyd_unload, model_floyd_end }, {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)", - model_dijkstra_create ,model_dijkstra_load, model_dijkstra_unload, model_dijkstra_end }, + model_dijkstra_create ,model_dijkstra_both_load, model_dijkstra_both_unload, model_dijkstra_both_end }, {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)", - model_dijkstracache_create, model_dijkstracache_load, model_dijkstracache_unload, model_dijkstracache_end }, + model_dijkstracache_create, model_dijkstra_both_load, model_dijkstra_both_unload, model_dijkstra_both_end }, {"none", "No routing (usable with Constant network only)", model_none_create, model_none_load, model_none_unload, model_none_end }, {NULL,NULL,NULL,NULL,NULL,NULL}}; @@ -176,7 +173,7 @@ static void parse_E_route_store_route(void) { // FIXME: checked by parser // xbt_assert1(current_routing->hierarchy==SURF_ROUTING_BASE, // "Bad declaration of route in \"%s\"",current_routing->name); - route_t route = xbt_new(s_route_t,1); + route_t route = xbt_new0(s_route_t,1); route->link_list = link_list; // TODO check if are correct (*(current_routing->set_route))(current_routing,src,dst,route); @@ -192,7 +189,7 @@ static void parse_E_ASroute_store_route(void) { // FIXME: checked by parser // xbt_assert1(current_routing->hierarchy==SURF_ROUTING_RECURSIVE, // "Bad declaration of ASroute in \"%s\"",current_routing->name); - route_extended_t e_route = xbt_new(s_route_extended_t,1); + route_extended_t e_route = xbt_new0(s_route_extended_t,1); e_route->generic_route.link_list = link_list; e_route->src_gateway = xbt_strdup(gw_src); e_route->dst_gateway = xbt_strdup(gw_dst); @@ -646,11 +643,12 @@ static route_extended_t full_get_route(routing_component_t rc, const char* src,c routing_component_full_t routing = (routing_component_full_t)rc; int table_size = xbt_dict_length(routing->to_index); - xbt_assert1(src && dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name); + xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name); routing_component_t src_as, dst_as; int *src_id,*dst_id; + // TODO: MAKE A FUNCTION FOR GENERIC CHECK src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src); dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst); @@ -707,7 +705,7 @@ static void full_finalize(routing_component_t rc) { /* Creation routing model functions */ -static void* model_full_create() { +static void* model_full_create(void) { routing_component_full_t new_component = xbt_new0(s_routing_component_full_t,1); new_component->generic_routing.set_processing_units = generic_set_processing_units; new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system; @@ -720,15 +718,15 @@ static void* model_full_create() { return new_component; } -static void model_full_load() { +static void model_full_load(void) { /* use "surfxml_add_callback" to add a parse function call */ } -static void model_full_unload() { +static void model_full_unload(void) { /* use "surfxml_del_callback" to remove a parse function call */ } -static void model_full_end() { +static void model_full_end(void) { char *key, *src_name, *dst_name; const char* sep = "#"; @@ -751,6 +749,8 @@ static void model_full_end() { /* Put the routes in position */ xbt_dict_foreach(routing->parse_routes, cursor, key, data) { + // FIXME: there are a misstake, is nesesary to use a different way to save the src_name and dst_name. + // or use a restricted char for separator (maybe space) keys = xbt_str_split_str(key, sep); src_name = xbt_dynar_get_as(keys, 0, char*); @@ -778,15 +778,17 @@ static void model_full_end() { xbt_dict_free(&(routing->parse_routes)); /* Add the loopback if needed */ - for (i = 0; i < table_size; i++) { - e_route = TO_ROUTE_FULL(i, i); - if(!e_route) { // && !xbt_dynar_length(e_route->generic_route.link_list) - e_route = xbt_new0(s_route_extended_t,1); - e_route->src_gateway = NULL; - e_route->dst_gateway = NULL; - e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL); - xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback); - TO_ROUTE_FULL(i, i) = e_route; + if(current_routing->hierarchy == SURF_ROUTING_BASE) { + for (i = 0; i < table_size; i++) { + e_route = TO_ROUTE_FULL(i, i); + if(!e_route) { // && !xbt_dynar_length(e_route->generic_route.link_list) + e_route = xbt_new0(s_route_extended_t,1); + e_route->src_gateway = NULL; + e_route->dst_gateway = NULL; + e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL); + xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback); + TO_ROUTE_FULL(i, i) = e_route; + } } } @@ -820,7 +822,7 @@ typedef struct { static route_extended_t floyd_get_route(routing_component_t rc, const char* src,const char* dst) { - xbt_assert1(src && dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name); + xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name); /* set utils vars */ routing_component_floyd_t routing = (routing_component_floyd_t) rc; @@ -831,6 +833,16 @@ static route_extended_t floyd_get_route(routing_component_t rc, const char* src, new_e_route->src_gateway = NULL; new_e_route->dst_gateway = NULL; + routing_component_t src_as, dst_as; + + // TODO: MAKE A FUNCTION FOR GENERIC CHECK + src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src); + dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst); + + xbt_assert3(src_as != NULL && dst_as != NULL, "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",src,dst,rc->name); + xbt_assert4(src_as == dst_as, "The src(%s in %s) and dst(%s in %s) are in differents AS",src,src_as->name,dst,dst_as->name); + xbt_assert2(rc == dst_as, "The routing component of src and dst is not the same as the network elements belong (%s==%s)",rc->name,dst_as->name); + int *src_id = xbt_dict_get(routing->to_index,src); int *dst_id = xbt_dict_get(routing->to_index,dst); xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s) or \"to\"(%s) no found in the local table",src,dst); @@ -928,15 +940,15 @@ static void* model_floyd_create(void) { return new_component; } -static void model_floyd_load() { +static void model_floyd_load(void) { /* use "surfxml_add_callback" to add a parse function call */ } -static void model_floyd_unload() { +static void model_floyd_unload(void) { /* use "surfxml_del_callback" to remove a parse function call */ } -static void model_floyd_end() { +static void model_floyd_end(void) { routing_component_floyd_t routing = ((routing_component_floyd_t)current_routing); xbt_dict_cursor_t cursor = NULL; @@ -965,7 +977,9 @@ static void model_floyd_end() { /* Put the routes in position */ xbt_dict_foreach(routing->parse_routes, cursor, key, data) { - + + // FIXME: there are a misstake, is nesesary to use a different way to save the src_name and dst_name. + // or use a restricted char for separator (maybe space) keys = xbt_str_split_str(key, sep); src_name = xbt_dynar_get_as(keys, 0, char*); @@ -981,26 +995,27 @@ static void model_floyd_end() { TO_FLOYD_PRED(*src_id,*dst_id) = *src_id; //link cost - TO_FLOYD_COST(*src_id,*dst_id) = 1; // assume 1 for now + TO_FLOYD_COST(*src_id,*dst_id) = 1; // assume 1 for now // TODO DAVID REDO xbt_dynar_free(&keys); } /* Add the loopback if needed */ - for (i = 0; i < table_size; i++) { - route_extended_t e_route = TO_FLOYD_LINK(i, i); - if(!e_route) { // && !xbt_dynar_length(e_route->generic_route.link_list) - e_route = xbt_new0(s_route_extended_t,1); - e_route->src_gateway = NULL; - e_route->dst_gateway = NULL; - e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL); - xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback); - TO_FLOYD_LINK(i,i) = e_route; - TO_FLOYD_PRED(i,i) = i; - TO_FLOYD_COST(i,i) = 1; + if(current_routing->hierarchy == SURF_ROUTING_BASE) { + for (i = 0; i < table_size; i++) { + route_extended_t e_route = TO_FLOYD_LINK(i, i); + if(!e_route) { // && !xbt_dynar_length(e_route->generic_route.link_list) + e_route = xbt_new0(s_route_extended_t,1); + e_route->src_gateway = NULL; + e_route->dst_gateway = NULL; + e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL); + xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback); + TO_FLOYD_LINK(i,i) = e_route; + TO_FLOYD_PRED(i,i) = i; + TO_FLOYD_COST(i,i) = 1; + } } } - //Calculate path costs for(c=0;cparse_routes)); //cleanup - free(cost_table); + xbt_free(cost_table); } /* ************************************************************************** */ @@ -1035,43 +1050,424 @@ static void model_floyd_end() { typedef struct { s_routing_component_t generic_routing; - xbt_graph_t route_graph; - xbt_dict_t graph_node_map; - xbt_dict_t route_cache; - xbt_dynar_t last_route; + xbt_dict_t parse_routes; + xbt_dict_t to_index; + xbt_graph_t route_graph; /* xbt_graph */ + xbt_dict_t graph_node_map; /* map */ + xbt_dict_t route_cache; /* use in cache mode */ int cached; } s_routing_component_dijkstra_t,*routing_component_dijkstra_t; -/* Parse routing model functions */ + +typedef struct graph_node_data { + int id; + int graph_id; //used for caching internal graph id's +} s_graph_node_data_t, * graph_node_data_t; + +typedef struct graph_node_map_element { + xbt_node_t node; +} s_graph_node_map_element_t, * graph_node_map_element_t; + +typedef struct route_cache_element { + int * pred_arr; + int size; +} s_route_cache_element_t, * route_cache_element_t; + +/* Free functions */ + +static void route_cache_elem_free(void *e) { + route_cache_element_t elm=(route_cache_element_t)e; + if (elm) { + xbt_free(elm->pred_arr); + xbt_free(elm); + } +} + +static void graph_node_map_elem_free(void *e) { + graph_node_map_element_t elm = (graph_node_map_element_t)e; + if(elm) { + xbt_free(elm); + } +} + +static void graph_edge_data_free(void *e) { + route_extended_t e_route = (route_extended_t)e; + if(e_route) { + xbt_dynar_free(&(e_route->generic_route.link_list)); + if(e_route->src_gateway) xbt_free(e_route->src_gateway); + if(e_route->dst_gateway) xbt_free(e_route->dst_gateway); + xbt_free(e_route); + } +} + +/* Utility functions */ + +static xbt_node_t route_graph_new_node(routing_component_dijkstra_t rc, int id, int graph_id) { + routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc; + xbt_node_t node = NULL; + graph_node_data_t data = NULL; + graph_node_map_element_t elm = NULL; + + data = xbt_new0(struct graph_node_data, 1); // FIXED by david + data->id = id; + data->graph_id = graph_id; + node = xbt_graph_new_node(routing->route_graph, data); + + elm = xbt_new0(struct graph_node_map_element, 1); // FIXED by david + elm->node = node; + xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free); + + return node; +} + +static graph_node_map_element_t graph_node_map_search(routing_component_dijkstra_t rc, int id) { + routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc; + 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)); + return elm; +} + +/* Parsing */ + +static void route_new_dijkstra(routing_component_dijkstra_t rc, int src_id, int dst_id, route_extended_t e_route ) { + routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc; + + xbt_node_t src = NULL; + xbt_node_t dst = NULL; + 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)); + 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)); + + if(src_elm) + src = src_elm->node; + + if(dst_elm) + dst = dst_elm->node; + + //add nodes if they don't exist in the graph + if(src_id == dst_id && src == NULL && dst == NULL) { + src = route_graph_new_node(rc,src_id, -1); + dst = src; + } else { + if(src == NULL) { + src = route_graph_new_node(rc,src_id, -1); + } + if(dst == NULL) { + dst = route_graph_new_node(rc,dst_id, -1); + } + } + + //add link as edge to graph + xbt_graph_new_edge(routing->route_graph, src, dst, e_route); +} + +static void add_loopback_dijkstra(routing_component_dijkstra_t rc) { + routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc; + + xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph); + + xbt_node_t node = NULL; + unsigned int cursor2; + xbt_dynar_foreach(nodes, cursor2, node) { + xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node); + xbt_edge_t edge = NULL; + unsigned int cursor; + + int found = 0; + xbt_dynar_foreach(out_edges, cursor, edge) { + xbt_node_t other_node = xbt_graph_edge_get_target(edge); + if(other_node == node) { + found = 1; + break; + } + } + + if(!found) { + route_extended_t e_route = xbt_new0(s_route_extended_t,1); + e_route->src_gateway = NULL; + e_route->dst_gateway = NULL; + e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL); + xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback); + xbt_graph_new_edge(routing->route_graph, node, node, e_route); + } + } +} /* Business methods */ -/* Creation routing model functions */ +static route_extended_t dijkstra_get_route(routing_component_t rc, const char* src,const char* dst) { + + routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc; + + xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name); + + int * pred_arr = NULL; + int src_node_id = 0; + int dst_node_id = 0; + int * nodeid = NULL; + int v; + routing_component_t src_as, dst_as; + int *src_id,*dst_id; + route_extended_t e_route; + int size = 0; + unsigned int cpt; + void* link; + xbt_dynar_t links = NULL; + route_cache_element_t elm = NULL; + xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph); + + route_extended_t new_e_route = xbt_new0(s_route_extended_t,1); + new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL); + new_e_route->src_gateway = NULL; + new_e_route->dst_gateway = NULL; -static void* model_dijkstra_create() { - return NULL; + // TODO: MAKE A FUNCTION FOR GENERIC CHECK + src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src); + dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst); + + xbt_assert3(src_as != NULL && dst_as != NULL, "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",src,dst,rc->name); + xbt_assert4(src_as == dst_as, "The src(%s in %s) and dst(%s in %s) are in differents AS",src,src_as->name,dst,dst_as->name); + xbt_assert2(rc == dst_as, "The routing component of src and dst is not the same as the network elements belong (%s==%s)",rc->name,dst_as->name); + + src_id = xbt_dict_get_or_null(routing->to_index,src); + dst_id = xbt_dict_get_or_null(routing->to_index,dst); + xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s) or \"to\"(%s) no found in the local table",src,dst); + + /*Use the graph_node id mapping set to quickly find the nodes */ + graph_node_map_element_t src_elm = graph_node_map_search(routing,*src_id); + graph_node_map_element_t dst_elm = graph_node_map_search(routing,*dst_id); + xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", *src_id, *dst_id); + src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id; + dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id; + + /* if the src and dst are the same */ // FIXED by david + if( src_node_id == dst_node_id ) { + + xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t); + xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t); + xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_s_v, node_e_v); + + xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id, *dst_id); + + e_route = (route_extended_t)xbt_graph_edge_get_data(edge); + + links = e_route->generic_route.link_list; + xbt_dynar_foreach(links, cpt, link) { + xbt_dynar_push(new_e_route->generic_route.link_list,&link); + } + + return new_e_route; + } + + if(routing->cached) { + /*check if there is a cached predecessor list avail */ + elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int)); + } + + if(elm) { //cached mode and cache hit + pred_arr = elm->pred_arr; + } else { //not cached mode or cache miss + double * cost_arr = NULL; + xbt_heap_t pqueue = NULL; + int i = 0; + + int nr_nodes = xbt_dynar_length(nodes); + cost_arr = xbt_new0(double, nr_nodes); // link cost from src to other hosts + pred_arr = xbt_new0(int, nr_nodes); // predecessors in path from src + pqueue = xbt_heap_new(nr_nodes, xbt_free); + + //initialize + cost_arr[src_node_id] = 0.0; + + for(i = 0; i < nr_nodes; i++) { + if(i != src_node_id) { + cost_arr[i] = DBL_MAX; + } + + pred_arr[i] = 0; + + //initialize priority queue + nodeid = xbt_new0(int, 1); + *nodeid = i; + xbt_heap_push(pqueue, nodeid, cost_arr[i]); + + } + + // apply dijkstra using the indexes from the graph's node array + while(xbt_heap_size(pqueue) > 0) { + int * v_id = xbt_heap_pop(pqueue); + xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t); + xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node); + xbt_edge_t edge = NULL; + unsigned int cursor; + + xbt_dynar_foreach(out_edges, cursor, edge) { + xbt_node_t u_node = xbt_graph_edge_get_target(edge); + graph_node_data_t data = xbt_graph_node_get_data(u_node); + int u_id = data->graph_id; + int cost_v_u = 1; //fixed link cost for now // TODO DAVID REDO + + if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) { + pred_arr[u_id] = *v_id; + cost_arr[u_id] = cost_v_u + cost_arr[*v_id]; + nodeid = xbt_new0(int, 1); + *nodeid = u_id; + xbt_heap_push(pqueue, nodeid, cost_arr[u_id]); + } + } + + //free item popped from pqueue + xbt_free(v_id); + } + + xbt_free(cost_arr); + xbt_heap_free(pqueue); + + } + + //compose route path with links + for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) { + xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t); + xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t); + xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v); + + xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id, *dst_id); + + e_route = (route_extended_t)xbt_graph_edge_get_data(edge); + + if(v==dst_node_id) + new_e_route->src_gateway=e_route->src_gateway; + new_e_route->dst_gateway=e_route->dst_gateway; + + links = e_route->generic_route.link_list; + xbt_dynar_foreach(links, cpt, link) { + xbt_dynar_push(new_e_route->generic_route.link_list,&link); + } + size++; + } + + if(routing->cached && elm == NULL) { + //add to predecessor list of the current src-host to cache + elm = xbt_new0(struct route_cache_element, 1); // FIXED by david + elm->pred_arr = pred_arr; + elm->size = size; + xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free); + } + + if(!routing->cached) + xbt_free(pred_arr); + + return new_e_route; } -static void model_dijkstra_load() { +static void dijkstra_finalize(routing_component_t rc) { + routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc; + + if (routing) { + xbt_graph_free_graph(routing->route_graph, &xbt_free, &graph_edge_data_free, &xbt_free); + xbt_dict_free(&routing->graph_node_map); + if(routing->cached) + xbt_dict_free(&routing->route_cache); + xbt_dict_free(&routing->to_index); + xbt_free(routing); + } } -static void model_dijkstra_unload() { +/* Creation routing model functions */ + +static void* model_dijkstra_both_create(int cached) { + routing_component_dijkstra_t new_component = xbt_new0(s_routing_component_dijkstra_t,1); + new_component->generic_routing.set_processing_units = generic_set_processing_units; + new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system; + new_component->generic_routing.set_route = generic_set_route; + new_component->generic_routing.set_ASroute = generic_set_ASroute; + new_component->generic_routing.get_route = dijkstra_get_route; + new_component->generic_routing.finalize = dijkstra_finalize; + new_component->cached = cached; + new_component->to_index = xbt_dict_new(); + new_component->parse_routes = xbt_dict_new(); + return new_component; } -static void model_dijkstra_end() { +static void* model_dijkstra_create(void) { + return model_dijkstra_both_create(0); } -static void* model_dijkstracache_create() { - return NULL; +static void* model_dijkstracache_create(void) { + return model_dijkstra_both_create(1); } -static void model_dijkstracache_load() { +static void model_dijkstra_both_load(void) { + /* use "surfxml_add_callback" to add a parse function call */ } -static void model_dijkstracache_unload() { +static void model_dijkstra_both_unload(void) { + /* use "surfxml_del_callback" to remove a parse function call */ } -static void model_dijkstracache_end() { +static void model_dijkstra_both_end(void) { + routing_component_dijkstra_t routing = (routing_component_dijkstra_t) current_routing; + xbt_dict_cursor_t cursor = NULL; + char *key, *data; + const char *sep = "#"; + xbt_dynar_t keys; + xbt_node_t node = NULL; + unsigned int cursor2; + xbt_dynar_t nodes = NULL; + char *src_name, *dst_name; + int *src_id, *dst_id; + route_t route; + + /* Create the topology graph */ + routing->route_graph = xbt_graph_new_graph(1, NULL); + routing->graph_node_map = xbt_dict_new(); + + if(routing->cached) + routing->route_cache = xbt_dict_new(); + + /* Put the routes in position */ + xbt_dict_foreach(routing->parse_routes, cursor, key, data) { + + // FIXME: there are a misstake, is nesesary to use a different way to save the src_name and dst_name. + // or use a restricted char for separator (maybe space) + keys = xbt_str_split_str(key, sep); + + src_name = xbt_dynar_get_as(keys, 0, char*); + dst_name = xbt_dynar_get_as(keys, 1, char*); + + src_id = xbt_dict_get_or_null(routing->to_index, src_name); + dst_id = xbt_dict_get_or_null(routing->to_index, dst_name); + + if (src_id == NULL || dst_id == NULL ) + THROW2(mismatch_error,0,"Network elements %s or %s not found", src_name, dst_name); + + route_extended_t e_route = generic_new_extended_route(current_routing,data); + + route_new_dijkstra(routing,*src_id,*dst_id,e_route); + + xbt_dynar_free(&keys); + } + + /* delete the parse table */ + xbt_dict_foreach(routing->parse_routes, cursor, key, data) { + route = (route_t)data; + xbt_dynar_free(&(route->link_list)); + xbt_free(data); + } + + /* delete parse dict */ + xbt_dict_free(&(routing->parse_routes)); + + /* Add the loopback if needed */ + if(current_routing->hierarchy == SURF_ROUTING_BASE) + add_loopback_dijkstra(routing); + + /* initialize graph indexes in nodes after graph has been built */ + nodes = xbt_graph_get_nodes(routing->route_graph); + + xbt_dynar_foreach(nodes, cursor2, node) { + graph_node_data_t data = xbt_graph_node_get_data(node); + data->graph_id = cursor2; + } + } @@ -1092,7 +1488,7 @@ static void none_finalize(routing_component_t rc) { } /* Creation routing model functions */ -static void* model_none_create() { +static void* model_none_create(void) { routing_component_none_t new_component = xbt_new0(s_routing_component_none_t,1); new_component->generic_routing.set_processing_units = NULL; new_component->generic_routing.set_autonomous_system = NULL; @@ -1103,65 +1499,71 @@ static void* model_none_create() { return new_component; } -static void model_none_load() {} -static void model_none_unload() {} -static void model_none_end() {} - -/* ************************************************** */ -/* ********** PATERN FOR NEW ROUTING **************** */ - -/* The minimal configuration of a new routing model need the next functions, - * also you need to set at the start of the file, the new model in the model - * list. Remember keep the null ending of the list. - */ -/* Routing model structure */ -typedef struct { - s_routing_component_t generic_routing; - /* things that your routing model need */ -} s_routing_component_NEW_t,*routing_component_NEW_t; - -/* Parse routing model functions */ -static void NEW_parse_S_host(void) {} /* example*/ - -/* Business methods */ -static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {return NULL;} /* mandatory */ -static void NEW_finalize(routing_component_t rc) {} /* mandatory */ +static void model_none_load(void) {} +static void model_none_unload(void) {} +static void model_none_end(void) {} -/* Creation routing model functions */ -static void* model_NEW_create() {return NULL;} /* mandatory */ -static void model_NEW_load() {} /* mandatory */ -static void model_NEW_unload() {} /* mandatory */ -static void model_NEW_end() {} /* mandatory */ +// /* ************************************************** */ +// /* ********** PATERN FOR NEW ROUTING **************** */ +// +// /* The minimal configuration of a new routing model need the next functions, +// * also you need to set at the start of the file, the new model in the model +// * list. Remember keep the null ending of the list. +// */ +// /* Routing model structure */ +// typedef struct { +// s_routing_component_t generic_routing; +// /* things that your routing model need */ +// } s_routing_component_NEW_t,*routing_component_NEW_t; +// +// /* Parse routing model functions */ +// static void NEW_parse_S_host(void) {} /* example*/ +// +// /* Business methods */ +// static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {return NULL;} /* mandatory */ +// static void NEW_finalize(routing_component_t rc) {} /* mandatory */ +// +// /* Creation routing model functions */ +// static void* model_NEW_create(void) {return NULL;} /* mandatory */ +// static void model_NEW_load(void) {} /* mandatory */ +// static void model_NEW_unload(void) {} /* mandatory */ +// static void model_NEW_end(void) {} /* mandatory */ /* ************************************************************************** */ /* ************************* GENERIC PARSE FUNCTIONS ************************ */ static void generic_set_processing_units(routing_component_t rc, const char* name) { - DEBUG1("Full - Load process unit \"%s\"",name); - model_type_t modeltype = rc->routing; - int *id = xbt_new0(int,1); // xbt_malloc(sizeof(int)); ? - xbt_dict_t index; - if(modeltype==&routing_models[SURF_MODEL_FULL]) - index = ((routing_component_full_t)current_routing)->to_index; - else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) - index = ((routing_component_floyd_t)current_routing)->to_index; - else xbt_die("\"generic_set_processing_units\" not support"); - *id = xbt_dict_length(index); - xbt_dict_set(index,name,id,xbt_free); + DEBUG1("Full - Load process unit \"%s\"",name); + model_type_t modeltype = rc->routing; + int *id = xbt_new0(int,1); // xbt_malloc(sizeof(int)); ? + xbt_dict_t index; + if(modeltype==&routing_models[SURF_MODEL_FULL]) + index = ((routing_component_full_t)current_routing)->to_index; + else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) + index = ((routing_component_floyd_t)current_routing)->to_index; + else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]|| + modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) + index = ((routing_component_dijkstra_t)current_routing)->to_index; + else xbt_die("\"generic_set_processing_units\" not support"); + *id = xbt_dict_length(index); + xbt_dict_set(index,name,id,xbt_free); } static void generic_set_autonomous_system(routing_component_t rc, const char* name) { - DEBUG1("Full - Load Autonomous system \"%s\"",name); - model_type_t modeltype = rc->routing; - int *id = xbt_new0(int,1); // xbt_malloc(sizeof(int)); ? - xbt_dict_t index; - if(modeltype==&routing_models[SURF_MODEL_FULL]) - index = ((routing_component_full_t)current_routing)->to_index; - else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) - index = ((routing_component_floyd_t)current_routing)->to_index; - else xbt_die("\"generic_set_autonomous_system\" not support"); - *id = xbt_dict_length(index); - xbt_dict_set(index,name,id,xbt_free); + DEBUG1("Full - Load Autonomous system \"%s\"",name); + model_type_t modeltype = rc->routing; + int *id = xbt_new0(int,1); // xbt_malloc(sizeof(int)); ? + xbt_dict_t index; + if(modeltype==&routing_models[SURF_MODEL_FULL]) + index = ((routing_component_full_t)current_routing)->to_index; + else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) + index = ((routing_component_floyd_t)current_routing)->to_index; + else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]|| + modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) + index = ((routing_component_dijkstra_t)current_routing)->to_index; + else xbt_die("\"generic_set_autonomous_system\" not support"); + *id = xbt_dict_length(index); + xbt_dict_set(index,name,id,xbt_free); } static void generic_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) { @@ -1172,6 +1574,9 @@ static void generic_set_route(routing_component_t rc, const char* src, const cha parseroutes = ((routing_component_full_t)current_routing)->parse_routes; else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) parseroutes = ((routing_component_floyd_t)current_routing)->parse_routes; + else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]|| + modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) + parseroutes = ((routing_component_dijkstra_t)current_routing)->parse_routes; else xbt_die("\"generic_set_autonomous_system\" not support"); char *route_name; route_name = bprintf("%s#%s",src,dst); @@ -1179,7 +1584,7 @@ static void generic_set_route(routing_component_t rc, const char* src, const cha xbt_assert2(!xbt_dict_get_or_null(parseroutes,route_name), "The route between \"%s\" and \"%s\" already exist",src,dst); xbt_dict_set(parseroutes, route_name, route, NULL); - free(route_name); + xbt_free(route_name); } static void generic_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) { @@ -1190,6 +1595,9 @@ static void generic_set_ASroute(routing_component_t rc, const char* src, const c parseroutes = ((routing_component_full_t)current_routing)->parse_routes; else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) parseroutes = ((routing_component_floyd_t)current_routing)->parse_routes; + else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]|| + modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) + parseroutes = ((routing_component_dijkstra_t)current_routing)->parse_routes; else xbt_die("\"generic_set_autonomous_system\" not support"); char *route_name; route_name = bprintf("%s#%s",src,dst); @@ -1197,7 +1605,7 @@ static void generic_set_ASroute(routing_component_t rc, const char* src, const c xbt_assert4(!xbt_dict_get_or_null(parseroutes,route_name), "The route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exist",src,e_route->src_gateway,dst,e_route->dst_gateway); xbt_dict_set(parseroutes, route_name, e_route, NULL); - free(route_name); + xbt_free(route_name); } /* ************************************************************************** */ @@ -1298,30 +1706,33 @@ static void print_ctn(void) { printf("ctn!!! %s\n",A_surfxml_link_c_ctn_id) //...... DEBUG ONLY .... // static void DEBUG_exit(void) { - printf("-------- print tree elements -----\n"); - print_tree(global_routing->root); - printf("----------------------------------\n\n"); - - printf("-------- network_elements --------\n"); - print_global(); - printf("----------------------------------\n\n"); +// printf("-------- print tree elements -----\n"); +// print_tree(global_routing->root); +// printf("----------------------------------\n\n"); +// +// printf("-------- network_elements --------\n"); +// print_global(); +// printf("----------------------------------\n\n"); -// char* names[] = { "11.A","11.B","11.C","121.A","121.B","122.A","13.A","13.B"}; +// const char* names[] = { "11.A","11.B","11.C","121.A","121.B","122.A","13.A","13.B"}; // int i,j,total = 8; // printf("-- print all the example routes --\n"); -// char* names[] = { "11.A","11.B","11.C"}; +// const char* names[] = { "11.A","11.B","11.C"}; // int i,j,total = 3; -// char* names[] = { "141.A","141.B","143.A","143.B"}; +// const char* names[] = { "141.A","141.B","143.A","143.B"}; // int i,j,total = 4; -// char* names[] = { "142.A","142.B","142.C" }; +// const char* names[] = { "15.A","15.B","15.C" }; // int i,j,total = 3; // const char* names[] = { "142.A","142.B","142.C", "11.A","11.B","11.C","141.A","141.B","143.A","143.B","11.A","11.B","11.C","121.A","121.B","122.A","13.A","13.B"}; // int i,j,total = 3+4+8+3; +// const char* names[] = { "142.A","142.B","142.C" }; +// int i,j,total = 3; + const char* names[] = { "11.A","11.B","11.C", "121.A","121.B", "122.A",