X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/2e6e0403b58b48d323fbf61d6f210a6e2732b4ea..bc08348d5094ea3a908be4ab825efb1cc98dc332:/src/kernel/routing/AsImpl.cpp diff --git a/src/kernel/routing/AsImpl.cpp b/src/kernel/routing/AsImpl.cpp index 75d2dc2191..30fe08537a 100644 --- a/src/kernel/routing/AsImpl.cpp +++ b/src/kernel/routing/AsImpl.cpp @@ -41,52 +41,86 @@ namespace simgrid { /** @brief Get the common ancestor and its first children in each line leading to src and dst * - * After this call, common_ancestor, src_ancestor and dst_ancestor are set as follows. + * In the recursive case, this sets common_ancestor, src_ancestor and dst_ancestor are set as follows. * @verbatim * platform root * | - * ... + * ... <- possibly long path * | * common_ancestor - * / \ - * / \ - * / \ - * / \ - * src_ancestor dst_ancestor + * / \ + * / \ + * / \ <- direct links + * / \ + * / \ + * src_ancestor dst_ancestor <- must be different in the recursive case * | | - * ... ... <-- possibly long pathes + * ... ... <-- possibly long pathes (one hop or more) * | | * src dst * @endverbatim + * + * In the base case (when src and dst are in the same AS), things are as follows: + * @verbatim + * platform root + * | + * ... <-- possibly long path + * | + * common_ancestor==src_ancestor==dst_ancestor <-- all the same value + * / \ + * / \ <-- direct links (exactly one hop) + * / \ + * src dst + * @endverbatim + * + * A specific recursive case occurs when src is the ancestor of dst. In this case, + * the base case routing should be used so the common_ancestor is specifically set + * to src_ancestor==dst_ancestor. + * Naturally, things are completely symmetrical if dst is the ancestor of src. + * @verbatim + * platform root + * | + * ... <-- possibly long path + * | + * src == src_ancestor==dst_ancestor==common_ancestor <-- same value + * | + * ... <-- possibly long path (one hop or more) + * | + * dst + * @endverbatim */ static void find_common_ancestors(NetCard* src, NetCard* dst, /* OUT */ AsImpl** common_ancestor, AsImpl** src_ancestor, AsImpl** dst_ancestor) { -#define ROUTING_HIERARCHY_MAXDEPTH 32 /* increase if it is not enough */ - AsImpl* path_src[ROUTING_HIERARCHY_MAXDEPTH]; - AsImpl* path_dst[ROUTING_HIERARCHY_MAXDEPTH]; - int index_src = 0; - int index_dst = 0; - AsImpl* current_src; - AsImpl* current_dst; - AsImpl* father; + /* Deal with the easy base case */ + if (src->containingAS() == dst->containingAS()) { + *common_ancestor = src->containingAS(); + *src_ancestor = *common_ancestor; + *dst_ancestor = *common_ancestor; + return; + } + + /* engage the full recursive search */ /* (1) find the path to root of src and dst*/ AsImpl* src_as = src->containingAS(); AsImpl* dst_as = dst->containingAS(); - xbt_assert(src_as, "Host %s must be in an AS", src->name()); - xbt_assert(dst_as, "Host %s must be in an AS", dst->name()); + xbt_assert(src_as, "Host %s must be in an AS", src->name().c_str()); + xbt_assert(dst_as, "Host %s must be in an AS", dst->name().c_str()); /* (2) find the path to the root routing component */ - for (AsImpl* current = src_as; current != nullptr; current = static_cast(current->father())) { - xbt_assert(index_src < ROUTING_HIERARCHY_MAXDEPTH, - "ROUTING_HIERARCHY_MAXDEPTH should be increased for element %s", src->name()); - path_src[index_src++] = current; + std::vector path_src; + AsImpl* current = src->containingAS(); + while (current != nullptr) { + path_src.push_back(current); + current = static_cast(current->father()); } - for (AsImpl* current = dst_as; current != nullptr; current = static_cast(current->father())) { - xbt_assert(index_dst < ROUTING_HIERARCHY_MAXDEPTH, "ROUTING_HIERARCHY_MAXDEPTH should be increased for path_dst"); - path_dst[index_dst++] = current; + std::vector path_dst; + current = dst->containingAS(); + while (current != nullptr) { + path_dst.push_back(current); + current = static_cast(current->father()); } /* (3) find the common father. @@ -95,102 +129,91 @@ namespace simgrid { * * This works because all SimGrid platform have a unique root element (that is the last element of both paths). */ - 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) if we did not find a difference (index_src or index_dst went to 0), both elements are in the same AS */ - if (current_src == current_dst) - father = current_src; - else // we found a difference - father = path_src[index_src + 1]; - - /* (5) result generation */ - *common_ancestor = father; /* the common father of src and dst */ - *src_ancestor = current_src; /* the first different father of src */ - *dst_ancestor = current_dst; /* the first different father of dst */ -#undef ROUTING_HIERARCHY_MAXDEPTH + AsImpl* father = nullptr; // the AS we dropped on the previous loop iteration + while (path_src.size() > 1 && path_dst.size() > 1 && + path_src.at(path_src.size() - 1) == path_dst.at(path_dst.size() - 1)) { + father = path_src.at(path_src.size() - 1); + path_src.pop_back(); + path_dst.pop_back(); } - /* PRECONDITION: this is the common ancestor of src and dst */ - bool AsImpl::getBypassRoute(routing::NetCard* src, routing::NetCard* dst, - /* OUT */ std::vector* links, double* latency) - { - // If never set a bypass route return nullptr without any further computations - XBT_DEBUG("generic_get_bypassroute from %s to %s", src->name(), dst->name()); - if (bypassRoutes_.empty()) - return false; - - /* Base case, no recursion is needed */ - if(dst->containingAS() == this && src->containingAS() == this ){ - if (bypassRoutes_.find({src->name(),dst->name()}) != bypassRoutes_.end()) { - std::vector* bypassedRoute = bypassRoutes_.at({src->name(), dst->name()}); - for (surf::Link* link : *bypassedRoute) { - links->push_back(link); - if (latency) - *latency += link->latency(); - } - XBT_DEBUG("Found a bypass route with %zu links",bypassedRoute->size()); - return true; + /* (4) we found the difference at least. Finalize the returned values */ + *src_ancestor = path_src.at(path_src.size() - 1); /* the first different father of src */ + *dst_ancestor = path_dst.at(path_dst.size() - 1); /* the first different father of dst */ + if (*src_ancestor == *dst_ancestor) { // src is the ancestor of dst, or the contrary + *common_ancestor = *src_ancestor; + } else { + *common_ancestor = father; + } + } + + /* PRECONDITION: this is the common ancestor of src and dst */ + bool AsImpl::getBypassRoute(routing::NetCard* src, routing::NetCard* dst, + /* OUT */ std::vector* links, double* latency) + { + // If never set a bypass route return nullptr without any further computations + XBT_DEBUG("generic_get_bypassroute from %s to %s", src->name().c_str(), dst->name().c_str()); + if (bypassRoutes_.empty()) + return false; + + /* Base case, no recursion is needed */ + if (dst->containingAS() == this && src->containingAS() == this) { + if (bypassRoutes_.find({src, dst}) != bypassRoutes_.end()) { + std::vector* bypassedRoute = bypassRoutes_.at({src, dst}); + for (surf::Link* link : *bypassedRoute) { + links->push_back(link); + if (latency) + *latency += link->latency(); } - return false; + XBT_DEBUG("Found a bypass route with %zu links", bypassedRoute->size()); + return true; } + return false; + } - /* Engage recursive search */ + /* Engage recursive search */ - std::vector* bypassedRoute = nullptr; + std::vector* bypassedRoute = nullptr; - /* (1) find the path to the root routing component */ - std::vector path_src; - As *current = src->containingAS(); - while (current != nullptr) { - path_src.push_back(current); - current = current->father_; - } + /* (1) find the path to the root routing component */ + std::vector path_src; + As* current = src->containingAS(); + while (current != nullptr) { + path_src.push_back(static_cast(current)); + current = current->father_; + } - std::vector path_dst; - current = dst->containingAS(); - while (current != nullptr) { - path_dst.push_back(current); - current = current->father_; - } + std::vector path_dst; + current = dst->containingAS(); + while (current != nullptr) { + path_dst.push_back(static_cast(current)); + current = current->father_; + } - /* (2) find the common father */ - while (path_src.size() > 1 && path_dst.size() >1 - && path_src.at(path_src.size() -1) == path_dst.at(path_dst.size() -1)) { - path_src.pop_back(); - path_dst.pop_back(); - } + /* (2) find the common father */ + while (path_src.size() > 1 && path_dst.size() > 1 && + path_src.at(path_src.size() - 1) == path_dst.at(path_dst.size() - 1)) { + path_src.pop_back(); + path_dst.pop_back(); + } - int max_index_src = path_src.size() - 1; - int max_index_dst = path_dst.size() - 1; + int max_index_src = path_src.size() - 1; + int max_index_dst = path_dst.size() - 1; - int max_index = std::max(max_index_src, max_index_dst); + int max_index = std::max(max_index_src, max_index_dst); - for (int max = 0; max <= max_index; max++) { - for (int i = 0; i < max; i++) { - if (i <= max_index_src && max <= max_index_dst) { - const std::pair key = {path_src.at(i)->name(), path_dst.at(max)->name()}; - if (bypassRoutes_.find(key) != bypassRoutes_.end()) { - bypassedRoute = bypassRoutes_.at(key); - break; - } - } - if (max <= max_index_src && i <= max_index_dst) { - const std::pair key = {path_src.at(max)->name(), path_dst.at(i)->name()}; - if (bypassRoutes_.find(key) != bypassRoutes_.end()) { - bypassedRoute = bypassRoutes_.at(key); - break; - } + std::pair key; + for (int max = 0; max <= max_index; max++) { + for (int i = 0; i < max; i++) { + if (i <= max_index_src && max <= max_index_dst) { + key = {path_src.at(i)->netcard_, path_dst.at(max)->netcard_}; + if (bypassRoutes_.find(key) != bypassRoutes_.end()) { + bypassedRoute = bypassRoutes_.at(key); + break; } } - - if (bypassedRoute) - break; - - if (max <= max_index_src && max <= max_index_dst) { - const std::pair key = {path_src.at(max)->name(), path_dst.at(max)->name()}; + if (max <= max_index_src && i <= max_index_dst) { + key = {path_src.at(max)->netcard_, path_dst.at(i)->netcard_}; if (bypassRoutes_.find(key) != bypassRoutes_.end()) { bypassedRoute = bypassRoutes_.at(key); break; @@ -198,15 +221,27 @@ namespace simgrid { } } - if (bypassedRoute) { - for (surf::Link* link : *bypassedRoute) { - links->push_back(link); - if (latency) - *latency += link->latency(); + if (bypassedRoute) + break; + + if (max <= max_index_src && max <= max_index_dst) { + key = {path_src.at(max)->netcard_, path_dst.at(max)->netcard_}; + if (bypassRoutes_.find(key) != bypassRoutes_.end()) { + bypassedRoute = bypassRoutes_.at(key); + break; } - return true; } - return false; + } + + if (bypassedRoute) { + for (surf::Link* link : *bypassedRoute) { + links->push_back(link); + if (latency) + *latency += link->latency(); + } + return true; + } + return false; } /** @@ -223,7 +258,7 @@ namespace simgrid { s_sg_platf_route_cbarg_t route; memset(&route,0,sizeof(route)); - XBT_DEBUG("Solve route/latency \"%s\" to \"%s\"", src->name(), dst->name()); + XBT_DEBUG("Solve route/latency \"%s\" to \"%s\"", src->name().c_str(), dst->name().c_str()); /* Find how src and dst are interconnected */ AsImpl *common_ancestor, *src_ancestor, *dst_ancestor; @@ -247,8 +282,8 @@ namespace simgrid { route.link_list = new std::vector(); common_ancestor->getRouteAndLatency(src_ancestor->netcard_, dst_ancestor->netcard_, &route, latency); - xbt_assert((route.gw_src != nullptr) && (route.gw_dst != nullptr), - "bad gateways for route from \"%s\" to \"%s\"", src->name(), dst->name()); + xbt_assert((route.gw_src != nullptr) && (route.gw_dst != nullptr), "bad gateways for route from \"%s\" to \"%s\"", + src->name().c_str(), dst->name().c_str()); /* If source gateway is not our source, we have to recursively find our way up to this point */ if (src != route.gw_src)