X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/9e8d76f5eb3db584150db55fc3929623188b6b08..66a6b6eefde8b9d5aac551b3e0008d3df3ddeba7:/src/surf/surf_routing.c diff --git a/src/surf/surf_routing.c b/src/surf/surf_routing.c index f18024e93f..65abb38f6f 100644 --- a/src/surf/surf_routing.c +++ b/src/surf/surf_routing.c @@ -127,7 +127,8 @@ static double base_vivaldi_get_latency (const char *src, const char *dst) xbt_assert(euclidean_dist>=0, "Euclidean Dist is less than 0\"%s\" and \"%.2f\"", src, euclidean_dist); - return euclidean_dist; + //From .ms to .s + return euclidean_dist / 1000; } static double vivaldi_get_link_latency (routing_component_t rc,const char *src, const char *dst, route_extended_t e_route) @@ -576,265 +577,219 @@ static char* elements_As_name(const char *name) * Get the common father of the to processing units, and the first different * father in the chain */ -static xbt_dynar_t elements_father(const char *src, const char *dst) +static void elements_father(const char *src, const char *dst, + routing_component_t *res_father, + routing_component_t *res_src, + routing_component_t *res_dst) { - xbt_assert(src && dst, "bad parameters for \"elements_father\" method"); - - xbt_dynar_t result = xbt_dynar_new(sizeof(char *), NULL); - +#define ELEMENTS_FATHER_MAXDEPTH 16 /* increase if it is not enough */ routing_component_t src_as, dst_as; - int index_src, index_dst, index_father_src, index_father_dst; - xbt_dynar_t path_src = NULL; - xbt_dynar_t path_dst = NULL; - routing_component_t current = NULL; - routing_component_t *current_src = NULL; - routing_component_t *current_dst = NULL; - routing_component_t *father = NULL; + routing_component_t path_src[ELEMENTS_FATHER_MAXDEPTH]; + routing_component_t path_dst[ELEMENTS_FATHER_MAXDEPTH]; + int index_src = 0; + int index_dst = 0; + routing_component_t current; + routing_component_t current_src; + routing_component_t current_dst; + routing_component_t father; /* (1) find the as where the src and dst are located */ - void * src_data = xbt_lib_get_or_null(host_lib,src, ROUTING_HOST_LEVEL); - void * dst_data = xbt_lib_get_or_null(host_lib,dst, ROUTING_HOST_LEVEL); - if(!src_data) src_data = xbt_lib_get_or_null(as_router_lib,src, ROUTING_ASR_LEVEL); - if(!dst_data) dst_data = xbt_lib_get_or_null(as_router_lib,dst, ROUTING_ASR_LEVEL); - src_as = ((network_element_info_t)src_data)->rc_component; - dst_as = ((network_element_info_t)dst_data)->rc_component; - - xbt_assert(src_as - && dst_as, - "Ask for route \"from\"(%s) or \"to\"(%s) no found", src, - dst); + network_element_info_t src_data = xbt_lib_get_or_null(host_lib, src, + ROUTING_HOST_LEVEL); + network_element_info_t dst_data = xbt_lib_get_or_null(host_lib, dst, + ROUTING_HOST_LEVEL); + if (!src_data) + src_data = xbt_lib_get_or_null(as_router_lib, src, ROUTING_ASR_LEVEL); + if (!dst_data) + dst_data = xbt_lib_get_or_null(as_router_lib, dst, ROUTING_ASR_LEVEL); + src_as = src_data->rc_component; + dst_as = dst_data->rc_component; + + xbt_assert(src_as && dst_as, + "Ask for route \"from\"(%s) or \"to\"(%s) no found", src, dst); /* (2) find the path to the root routing component */ - path_src = xbt_dynar_new(sizeof(routing_component_t), NULL); - current = src_as; - while (current != NULL) { - xbt_dynar_push(path_src, ¤t); - current = current->routing_father; + for (current = src_as ; current != NULL ; current = current->routing_father) { + if (index_src >= ELEMENTS_FATHER_MAXDEPTH) + xbt_die("ELEMENTS_FATHER_MAXDEPTH should be increased for path_src"); + path_src[index_src++] = current; } - path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL); - current = dst_as; - while (current != NULL) { - xbt_dynar_push(path_dst, ¤t); - current = current->routing_father; + for (current = dst_as ; current != NULL ; current = current->routing_father) { + if (index_dst >= ELEMENTS_FATHER_MAXDEPTH) + xbt_die("ELEMENTS_FATHER_MAXDEPTH should be increased for path_dst"); + path_dst[index_dst++] = current; } /* (3) find the common father */ - index_src = path_src->used - 1; - index_dst = path_dst->used - 1; - current_src = xbt_dynar_get_ptr(path_src, index_src); - current_dst = xbt_dynar_get_ptr(path_dst, index_dst); - while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) { - current_src = xbt_dynar_get_ptr(path_src, index_src); - current_dst = xbt_dynar_get_ptr(path_dst, index_dst); - index_src--; - index_dst--; - } - index_src++; - index_dst++; - current_src = xbt_dynar_get_ptr(path_src, index_src); - current_dst = xbt_dynar_get_ptr(path_dst, index_dst); + do { + current_src = path_src[--index_src]; + current_dst = path_dst[--index_dst]; + } while (index_src > 0 && index_dst > 0 && current_src == current_dst); /* (4) they are not in the same routing component, make the path */ - index_father_src = index_src + 1; - index_father_dst = index_dst + 1; - - if (*current_src == *current_dst) + if (current_src == current_dst) father = current_src; else - father = xbt_dynar_get_ptr(path_src, index_father_src); + father = path_src[index_src + 1]; /* (5) result generation */ - xbt_dynar_push(result, father); /* first same the father of src and dst */ - xbt_dynar_push(result, current_src); /* second the first different father of src */ - xbt_dynar_push(result, current_dst); /* three the first different father of dst */ - - xbt_dynar_free(&path_src); - xbt_dynar_free(&path_dst); + *res_father = father; /* first the common father of src and dst */ + *res_src = current_src; /* second the first different father of src */ + *res_dst = current_dst; /* three the first different father of dst */ - return result; +#undef ELEMENTS_FATHER_MAXDEPTH } /* Global Business methods */ /** - * \brief Recursive function for get_route + * \brief Recursive function for get_route_latency * * \param src the source host name * \param dst the destination host name + * \param *e_route the route where the links are stored + * \param *latency the latency, if needed * - * This function is called by "get_route". It allows to walk recursively - * through the routing components tree. + * This function is called by "get_route" and "get_latency". It allows to walk + * recursively through the routing components tree. */ -static route_extended_t _get_route(const char *src, const char *dst) +static void _get_route_latency(const char *src, const char *dst, + xbt_dynar_t *route, double *latency) { + XBT_DEBUG("Solve route/latency \"%s\" to \"%s\"", src, dst); + xbt_assert(src && dst, "bad parameters for \"_get_route_latency\" method"); - void *link; - unsigned int cpt = 0; - - XBT_DEBUG("Solve route \"%s\" to \"%s\"", src, dst); - - xbt_assert(src && dst, "bad parameters for \"_get_route\" method"); - - route_extended_t e_route, e_route_cnt, e_route_src = NULL, e_route_dst = - NULL; - - xbt_dynar_t elem_father_list = elements_father(src, dst); + routing_component_t common_father; + routing_component_t src_father; + routing_component_t dst_father; + elements_father(src, dst, &common_father, &src_father, &dst_father); - routing_component_t common_father = - xbt_dynar_get_as(elem_father_list, 0, routing_component_t); - routing_component_t src_father = - xbt_dynar_get_as(elem_father_list, 1, routing_component_t); - routing_component_t dst_father = - xbt_dynar_get_as(elem_father_list, 2, routing_component_t); + if (src_father == dst_father) { /* SURF_ROUTING_BASE */ - 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); - - if (src_father == dst_father) { /* SURF_ROUTING_BASE */ - - e_route_cnt = - (*(common_father->get_route)) (common_father, src, dst); - xbt_assert(e_route_cnt, "no route between \"%s\" and \"%s\"", src, - dst); - // FIXME (optim): faire une copie et pas une série de push - xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) { - xbt_dynar_push(e_route->generic_route.link_list, &link); - } - generic_free_extended_route(e_route_cnt); + route_extended_t e_route = NULL; + if (route) { + e_route = common_father->get_route(common_father, src, dst); + xbt_assert(e_route, "no route between \"%s\" and \"%s\"", src, dst); + *route = e_route->generic_route.link_list; + } + if (latency) { + *latency = common_father->get_latency(common_father, src, dst, e_route); + xbt_assert(*latency >= 0.0, + "latency error on route between \"%s\" and \"%s\"", src, dst); + } + if (e_route) { + xbt_free(e_route->src_gateway); + xbt_free(e_route->dst_gateway); + xbt_free(e_route); + } } else { /* SURF_ROUTING_RECURSIVE */ route_extended_t e_route_bypass = NULL; - if (common_father->get_bypass_route) - e_route_bypass = - (*(common_father->get_bypass_route)) (common_father, src, dst); + e_route_bypass = common_father->get_bypass_route(common_father, src, dst); - if (e_route_bypass) - e_route_cnt = e_route_bypass; - else - e_route_cnt = - (*(common_father->get_route)) (common_father, src_father->name, - dst_father->name); + xbt_assert(!latency || !e_route_bypass, + "Bypass cannot work yet with get_latency"); + + route_extended_t e_route_cnt = e_route_bypass + ? e_route_bypass + : common_father->get_route(common_father, + src_father->name, dst_father->name); xbt_assert(e_route_cnt, "no route between \"%s\" and \"%s\"", - src_father->name, dst_father->name); + src_father->name, dst_father->name); xbt_assert((e_route_cnt->src_gateway == NULL) == - (e_route_cnt->dst_gateway == NULL), - "bad gateway for route between \"%s\" and \"%s\"", src, - dst); + (e_route_cnt->dst_gateway == NULL), + "bad gateway for route between \"%s\" and \"%s\"", src, dst); + + if (route) { + *route = xbt_dynar_new(global_routing->size_of_link, NULL); + } + if (latency) { + *latency = common_father->get_latency(common_father, + src_father->name, dst_father->name, + e_route_cnt); + xbt_assert(*latency >= 0.0, + "latency error on route between \"%s\" and \"%s\"", + src_father->name, dst_father->name); + } + + void *link; + unsigned int cpt; if (strcmp(src, e_route_cnt->src_gateway)) { - e_route_src = _get_route(src, e_route_cnt->src_gateway); - xbt_assert(e_route_src, "no route between \"%s\" and \"%s\"", src, - e_route_cnt->src_gateway); - xbt_dynar_foreach(e_route_src->generic_route.link_list, cpt, link) { - xbt_dynar_push(e_route->generic_route.link_list, &link); + double latency_src; + xbt_dynar_t route_src; + + _get_route_latency(src, e_route_cnt->src_gateway, + (route ? &route_src : NULL), + (latency ? &latency_src : NULL)); + if (route) { + xbt_assert(route_src, "no route between \"%s\" and \"%s\"", + src, e_route_cnt->src_gateway); + xbt_dynar_foreach(route_src, cpt, link) { + xbt_dynar_push(*route, &link); + } + xbt_dynar_free(&route_src); + } + if (latency) { + xbt_assert(latency_src >= 0.0, + "latency error on route between \"%s\" and \"%s\"", + src, e_route_cnt->src_gateway); + *latency += latency_src; } } - xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) { - xbt_dynar_push(e_route->generic_route.link_list, &link); + if (route) { + xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) { + xbt_dynar_push(*route, &link); + } } if (strcmp(e_route_cnt->dst_gateway, dst)) { - e_route_dst = _get_route(e_route_cnt->dst_gateway, dst); - xbt_assert(e_route_dst, "no route between \"%s\" and \"%s\"", - e_route_cnt->dst_gateway, dst); - xbt_dynar_foreach(e_route_dst->generic_route.link_list, cpt, link) { - xbt_dynar_push(e_route->generic_route.link_list, &link); + double latency_dst; + xbt_dynar_t route_dst; + + _get_route_latency(e_route_cnt->dst_gateway, dst, + (route ? &route_dst : NULL), + (latency ? &latency_dst : NULL)); + if (route) { + xbt_assert(route_dst, "no route between \"%s\" and \"%s\"", + e_route_cnt->dst_gateway, dst); + xbt_dynar_foreach(route_dst, cpt, link) { + xbt_dynar_push(*route, &link); + } + xbt_dynar_free(&route_dst); + } + if (latency) { + xbt_assert(latency_dst >= 0.0, + "latency error on route between \"%s\" and \"%s\"", + e_route_cnt->dst_gateway, dst); + *latency += latency_dst; } } - e_route->src_gateway = xbt_strdup(e_route_cnt->src_gateway); - e_route->dst_gateway = xbt_strdup(e_route_cnt->dst_gateway); - - generic_free_extended_route(e_route_src); generic_free_extended_route(e_route_cnt); - generic_free_extended_route(e_route_dst); } - - xbt_dynar_free(&elem_father_list); - - return e_route; } -static double _get_latency(const char *src, const char *dst) +/** + * \brief Generic function for get_route, get_route_no_cleanup, and get_latency + */ +static void get_route_latency(const char *src, const char *dst, + xbt_dynar_t *route, double *latency, int cleanup) { - double latency, latency_src, latency_dst = 0.0; - - XBT_DEBUG("Solve route \"%s\" to \"%s\"", src, dst); - xbt_assert(src && dst, "bad parameters for \"_get_route\" method"); - - route_extended_t e_route_cnt; - - xbt_dynar_t elem_father_list = elements_father(src, dst); - - routing_component_t common_father = - xbt_dynar_get_as(elem_father_list, 0, routing_component_t); - routing_component_t src_father = - xbt_dynar_get_as(elem_father_list, 1, routing_component_t); - routing_component_t dst_father = - xbt_dynar_get_as(elem_father_list, 2, routing_component_t); - - if (src_father == dst_father) { /* SURF_ROUTING_BASE */ - - latency = - (*(common_father->get_latency)) (common_father, src, dst, NULL); - xbt_assert(latency>=0, "no route between \"%s\" and \"%s\"", src, - dst); - - } else { /* SURF_ROUTING_RECURSIVE */ - route_extended_t e_route_bypass = NULL; - if (common_father->get_bypass_route) - e_route_bypass = - (*(common_father->get_bypass_route)) (common_father, src, dst); - - xbt_assert(!e_route_bypass,"Bypass cannot work yet with get_latency"); - - e_route_cnt = - (*(common_father->get_route)) (common_father, src_father->name, - dst_father->name); - - xbt_assert(e_route_cnt, "no route between \"%s\" and \"%s\"", - src_father->name, dst_father->name); - - xbt_assert((e_route_cnt->src_gateway == NULL) == - (e_route_cnt->dst_gateway == NULL), - "bad gateway for route between \"%s\" and \"%s\"", src, - dst); - - latency = (*(common_father->get_latency)) (common_father, src_father->name, dst_father->name, e_route_cnt); - - xbt_assert(latency>=0, "no route between \"%s\" and \"%s\"", - src_father->name, dst_father->name); - - if (strcmp(src,e_route_cnt->src_gateway)) { - - latency_src = _get_latency(src, e_route_cnt->src_gateway); - xbt_assert(latency_src>=0, "no route between \"%s\" and \"%s\"", src, - e_route_cnt->src_gateway); - latency += latency_src; - } - - if (strcmp(e_route_cnt->dst_gateway,dst)) { - - latency_dst = _get_latency(e_route_cnt->dst_gateway, dst); - xbt_assert(latency_dst>=0, "no route between \"%s\" and \"%s\"", - e_route_cnt->dst_gateway, dst); - latency += latency_dst; - } - + _get_route_latency(src, dst, route, latency); + xbt_assert(!route || *route, "no route between \"%s\" and \"%s\"", src, dst); + xbt_assert(!latency || *latency >= 0.0, + "latency error on route between \"%s\" and \"%s\"", src, dst); + if (route) { + xbt_dynar_free(&global_routing->last_route); + global_routing->last_route = cleanup ? *route : NULL; } - - xbt_dynar_free(&elem_father_list); - - return latency; } /** @@ -849,24 +804,9 @@ static double _get_latency(const char *src, const char *dst) */ static xbt_dynar_t get_route(const char *src, const char *dst) { - - route_extended_t e_route; - - e_route = _get_route(src, dst); - xbt_assert(e_route, "no route between \"%s\" and \"%s\"", src, dst); - - if (global_routing->last_route) - xbt_dynar_free(&(global_routing->last_route)); - global_routing->last_route = 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); - - return global_routing->last_route; + xbt_dynar_t route = NULL; + get_route_latency(src, dst, &route, NULL, 1); + return route; } /** @@ -881,18 +821,16 @@ static xbt_dynar_t get_route(const char *src, const char *dst) */ static xbt_dynar_t get_route_no_cleanup(const char *src, const char *dst) { - xbt_dynar_t d = get_route(src,dst); - global_routing->last_route = NULL; - return d; + xbt_dynar_t route = NULL; + get_route_latency(src, dst, &route, NULL, 0); + return route; } /*Get Latency*/ static double get_latency(const char *src, const char *dst) { - double latency = -1.0; - latency = _get_latency(src, dst); - xbt_assert(latency>=0.0, "no route between \"%s\" and \"%s\"", src, dst); + get_route_latency(src, dst, NULL, &latency, 0); return latency; } @@ -1000,6 +938,7 @@ void routing_model_create(size_t size_of_links, void *loopback, double_f_cpvoid_ global_routing->get_latency = get_latency; global_routing->get_route_no_cleanup = get_route_no_cleanup; global_routing->get_onelink_routes = get_onelink_routes; + global_routing->get_route_latency = get_route_latency; global_routing->get_network_element_type = get_network_element_type; global_routing->finalize = finalize; global_routing->loopback = loopback; @@ -1241,9 +1180,8 @@ route_extended_t generic_get_bypassroute(routing_component_t rc, current_src = xbt_dynar_get_ptr(path_src, index_src); current_dst = xbt_dynar_get_ptr(path_dst, index_dst); while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) { - routing_component_t *tmp_src, *tmp_dst; - tmp_src = xbt_dynar_pop_ptr(path_src); - tmp_dst = xbt_dynar_pop_ptr(path_dst); + xbt_dynar_pop_ptr(path_src); + xbt_dynar_pop_ptr(path_dst); index_src--; index_dst--; current_src = xbt_dynar_get_ptr(path_src, index_src);