src/kernel/routing/NetZoneImpl.cpp

   1 /* Copyright (c) 2006-2022. The SimGrid Team. All rights reserved.          */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include <simgrid/kernel/routing/NetPoint.hpp>
   7 #include <simgrid/kernel/routing/NetZoneImpl.hpp>
   8 #include <simgrid/s4u/Engine.hpp>
   9 #include <simgrid/s4u/Host.hpp>
  10 #include <simgrid/s4u/VirtualMachine.hpp>
  11
  12 #include "src/include/simgrid/sg_config.hpp"
  13 #include "src/kernel/EngineImpl.hpp"
  14 #include "src/kernel/resource/CpuImpl.hpp"
  15 #include "src/kernel/resource/DiskImpl.hpp"
  16 #include "src/kernel/resource/NetworkModel.hpp"
  17 #include "src/kernel/resource/SplitDuplexLinkImpl.hpp"
  18 #include "src/kernel/resource/StandardLinkImpl.hpp"
  19 #include "src/kernel/resource/VirtualMachineImpl.hpp"
  20 #include "src/surf/HostImpl.hpp"
  21
  22 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(ker_routing, kernel, "Kernel routing-related information");
  23
  24 namespace simgrid {
  25 namespace kernel {
  26 namespace routing {
  27
  28 /* Pick the right models for CPU, net and host, and call their model_init_preparse */
  29 static void surf_config_models_setup()
  30 {
  31   std::string host_model_name    = simgrid::config::get_value<std::string>("host/model");
  32   std::string network_model_name = simgrid::config::get_value<std::string>("network/model");
  33   std::string cpu_model_name     = simgrid::config::get_value<std::string>("cpu/model");
  34   std::string disk_model_name    = simgrid::config::get_value<std::string>("disk/model");
  35
  36   /* The compound host model is needed when using non-default net/cpu models */
  37   if ((not simgrid::config::is_default("network/model") || not simgrid::config::is_default("cpu/model")) &&
  38       simgrid::config::is_default("host/model")) {
  39     host_model_name = "compound";
  40     simgrid::config::set_value("host/model", host_model_name);
  41   }
  42
  43   XBT_DEBUG("host model: %s", host_model_name.c_str());
  44   if (host_model_name == "compound") {
  45     xbt_assert(not cpu_model_name.empty(), "Set a cpu model to use with the 'compound' host model");
  46     xbt_assert(not network_model_name.empty(), "Set a network model to use with the 'compound' host model");
  47
  48     const auto* cpu_model = find_model_description(surf_cpu_model_description, cpu_model_name);
  49     cpu_model->model_init_preparse();
  50
  51     const auto* network_model = find_model_description(surf_network_model_description, network_model_name);
  52     network_model->model_init_preparse();
  53   }
  54
  55   XBT_DEBUG("Call host_model_init");
  56   const auto* host_model = find_model_description(surf_host_model_description, host_model_name);
  57   host_model->model_init_preparse();
  58
  59   XBT_DEBUG("Call vm_model_init");
  60   /* ideally we should get back the pointer to CpuModel from model_init_preparse(), but this
  61    * requires changing the declaration of surf_cpu_model_description.
  62    * To be reviewed in the future */
  63   surf_vm_model_init_HL13(
  64       simgrid::s4u::Engine::get_instance()->get_netzone_root()->get_impl()->get_cpu_pm_model().get());
  65
  66   XBT_DEBUG("Call disk_model_init");
  67   const auto* disk_model = find_model_description(surf_disk_model_description, disk_model_name);
  68   disk_model->model_init_preparse();
  69 }
  70
  71 xbt::signal<void(bool symmetrical, kernel::routing::NetPoint* src, kernel::routing::NetPoint* dst,
  72                  kernel::routing::NetPoint* gw_src, kernel::routing::NetPoint* gw_dst,
  73                  std::vector<kernel::resource::StandardLinkImpl*> const& link_list)>
  74     NetZoneImpl::on_route_creation;
  75
  76 template <typename Resource> void NetZoneImpl::ResourceDeleter::operator()(Resource* res) const
  77 {
  78   res->destroy();
  79 }
  80
  81 NetZoneImpl::NetZoneImpl(const std::string& name) : piface_(this), name_(name)
  82 {
  83   auto* engine = s4u::Engine::get_instance();
  84   /* workaroud: first netzoneImpl will be the root netzone.
  85    * Without globals and with current surf_*_model_description init functions, we need
  86    * the root netzone to exist when creating the models.
  87    * This was usually done at sg_platf.cpp, during XML parsing */
  88   if (not engine->get_netzone_root()) {
  89     engine->set_netzone_root(&piface_);
  90     /* root netzone set, initialize models */
  91     simgrid::s4u::Engine::on_platform_creation();
  92
  93     /* Initialize the surf models. That must be done after we got all config, and before we need the models.
  94      * That is, after the last <config> tag, if any, and before the first of cluster|peer|zone|trace|trace_cb
  95      *
  96      * I'm not sure for <trace> and <trace_cb>, there may be a bug here
  97      * (FIXME: check it out by creating a file beginning with one of these tags)
  98      * but cluster and peer come down to zone creations, so putting this verification here is correct.
  99      */
 100     surf_config_models_setup();
 101   }
 102
 103   xbt_assert(nullptr == engine->netpoint_by_name_or_null(get_name()),
 104              "Refusing to create a second NetZone called '%s'.", get_cname());
 105   netpoint_ = new NetPoint(name_, NetPoint::Type::NetZone);
 106   XBT_DEBUG("NetZone '%s' created with the id '%lu'", get_cname(), netpoint_->id());
 107   _sg_cfg_init_status = 2; /* HACK: direct access to the global controlling the level of configuration to prevent
 108                             * any further config now that we created some real content */
 109   simgrid::s4u::NetZone::on_creation(piface_); // notify the signal
 110 }
 111
 112 NetZoneImpl::~NetZoneImpl()
 113 {
 114   for (auto const& nz : children_)
 115     delete nz;
 116
 117   /* Since hosts_ is a std::map, the hosts are destroyed in the lexicographic order, which ensures that the output is
 118    * reproducible.
 119    */
 120   for (auto& host : hosts_) {
 121     host.second->destroy();
 122   }
 123   hosts_.clear();
 124
 125   for (auto const& kv : bypass_routes_)
 126     delete kv.second;
 127
 128   s4u::Engine::get_instance()->netpoint_unregister(netpoint_);
 129 }
 130
 131 void NetZoneImpl::add_child(NetZoneImpl* new_zone)
 132 {
 133   xbt_assert(not sealed_, "Cannot add a new child to the sealed zone %s", get_cname());
 134   /* set the parent behavior */
 135   hierarchy_ = RoutingMode::recursive;
 136   children_.push_back(new_zone);
 137 }
 138
 139 /** @brief Returns the list of the hosts found in this NetZone (not recursively)
 140  *
 141  * Only the hosts that are directly contained in this NetZone are retrieved,
 142  * not the ones contained in sub-netzones.
 143  */
 144 std::vector<s4u::Host*> NetZoneImpl::get_all_hosts() const
 145 {
 146   return s4u::Engine::get_instance()->get_filtered_hosts(
 147       [this](const s4u::Host* host) { return host->get_impl()->get_englobing_zone() == this; });
 148 }
 149 size_t NetZoneImpl::get_host_count() const
 150 {
 151   return get_all_hosts().size();
 152 }
 153
 154 std::vector<s4u::Link*> NetZoneImpl::get_filtered_links(const std::function<bool(s4u::Link*)>& filter) const
 155 {
 156   std::vector<s4u::Link*> filtered_list;
 157   for (auto const& kv : links_) {
 158     s4u::Link* l = kv.second->get_iface();
 159     if (filter(l))
 160       filtered_list.push_back(l);
 161   }
 162
 163   for (const auto* child : children_) {
 164     auto child_links = child->get_filtered_links(filter);
 165     filtered_list.insert(filtered_list.end(), std::make_move_iterator(child_links.begin()),
 166                          std::make_move_iterator(child_links.end()));
 167   }
 168   return filtered_list;
 169 }
 170
 171 std::vector<s4u::Link*> NetZoneImpl::get_all_links() const
 172 {
 173   return get_filtered_links([](const s4u::Link*) { return true; });
 174 }
 175
 176 size_t NetZoneImpl::get_link_count() const
 177 {
 178   size_t total = links_.size();
 179   for (const auto* child : children_) {
 180     total += child->get_link_count();
 181   }
 182   return total;
 183 }
 184
 185 s4u::Host* NetZoneImpl::create_host(const std::string& name, const std::vector<double>& speed_per_pstate)
 186 {
 187   xbt_assert(cpu_model_pm_,
 188              "Impossible to create host: %s. Invalid CPU model: nullptr. Have you set the parent of this NetZone: %s?",
 189              name.c_str(), get_cname());
 190   xbt_assert(not sealed_, "Impossible to create host: %s. NetZone %s already sealed", name.c_str(), get_cname());
 191   auto* host   = (new resource::HostImpl(name))->set_englobing_zone(this);
 192   hosts_[name] = host;
 193   host->get_iface()->set_netpoint((new NetPoint(name, NetPoint::Type::Host))->set_englobing_zone(this));
 194
 195   cpu_model_pm_->create_cpu(host->get_iface(), speed_per_pstate);
 196
 197   return host->get_iface();
 198 }
 199
 200 resource::StandardLinkImpl* NetZoneImpl::do_create_link(const std::string& name, const std::vector<double>& bandwidths)
 201 {
 202   return network_model_->create_link(name, bandwidths);
 203 }
 204
 205 s4u::Link* NetZoneImpl::create_link(const std::string& name, const std::vector<double>& bandwidths)
 206 {
 207   xbt_assert(
 208       network_model_,
 209       "Impossible to create link: %s. Invalid network model: nullptr. Have you set the parent of this NetZone: %s?",
 210       name.c_str(), get_cname());
 211   xbt_assert(not sealed_, "Impossible to create link: %s. NetZone %s already sealed", name.c_str(), get_cname());
 212   links_[name].reset(do_create_link(name, bandwidths)->set_englobing_zone(this));
 213   return links_[name]->get_iface();
 214 }
 215
 216 s4u::SplitDuplexLink* NetZoneImpl::create_split_duplex_link(const std::string& name,
 217                                                             const std::vector<double>& bandwidths)
 218 {
 219   xbt_assert(
 220       network_model_,
 221       "Impossible to create link: %s. Invalid network model: nullptr. Have you set the parent of this NetZone: %s?",
 222       name.c_str(), get_cname());
 223   xbt_assert(not sealed_, "Impossible to create link: %s. NetZone %s already sealed", name.c_str(), get_cname());
 224
 225   auto* link_up             = create_link(name + "_UP", bandwidths)->get_impl()->set_englobing_zone(this);
 226   auto* link_down           = create_link(name + "_DOWN", bandwidths)->get_impl()->set_englobing_zone(this);
 227   split_duplex_links_[name] = std::make_unique<resource::SplitDuplexLinkImpl>(name, link_up, link_down);
 228   return split_duplex_links_[name]->get_iface();
 229 }
 230
 231 s4u::Disk* NetZoneImpl::create_disk(const std::string& name, double read_bandwidth, double write_bandwidth)
 232 {
 233   xbt_assert(disk_model_,
 234              "Impossible to create disk: %s. Invalid disk model: nullptr. Have you set the parent of this NetZone: %s?",
 235              name.c_str(), get_cname());
 236   xbt_assert(not sealed_, "Impossible to create disk: %s. NetZone %s already sealed", name.c_str(), get_cname());
 237   auto* l = disk_model_->create_disk(name, read_bandwidth, write_bandwidth);
 238
 239   return l->get_iface();
 240 }
 241
 242 NetPoint* NetZoneImpl::create_router(const std::string& name)
 243 {
 244   xbt_assert(nullptr == s4u::Engine::get_instance()->netpoint_by_name_or_null(name),
 245              "Refusing to create a router named '%s': this name already describes a node.", name.c_str());
 246   xbt_assert(not sealed_, "Impossible to create router: %s. NetZone %s already sealed", name.c_str(), get_cname());
 247
 248   return (new NetPoint(name, NetPoint::Type::Router))->set_englobing_zone(this);
 249 }
 250
 251 unsigned long NetZoneImpl::add_component(NetPoint* elm)
 252 {
 253   vertices_.push_back(elm);
 254   return vertices_.size() - 1; // The rank of the newly created object
 255 }
 256
 257 std::vector<resource::StandardLinkImpl*> NetZoneImpl::get_link_list_impl(const std::vector<s4u::LinkInRoute>& link_list,
 258                                                                          bool backroute) const
 259 {
 260   std::vector<resource::StandardLinkImpl*> links;
 261
 262   for (const auto& link : link_list) {
 263     if (link.get_link()->get_sharing_policy() != s4u::Link::SharingPolicy::SPLITDUPLEX) {
 264       links.push_back(link.get_link()->get_impl());
 265       continue;
 266     }
 267     // split-duplex links
 268     const auto* sd_link = dynamic_cast<const s4u::SplitDuplexLink*>(link.get_link());
 269     xbt_assert(sd_link,
 270                "Add_route: cast to SpliDuplexLink impossible. This should not happen, please contact SimGrid team");
 271     resource::StandardLinkImpl* link_impl;
 272     switch (link.get_direction()) {
 273       case s4u::LinkInRoute::Direction::UP:
 274         if (backroute)
 275           link_impl = sd_link->get_link_down()->get_impl();
 276         else
 277           link_impl = sd_link->get_link_up()->get_impl();
 278         break;
 279       case s4u::LinkInRoute::Direction::DOWN:
 280         if (backroute)
 281           link_impl = sd_link->get_link_up()->get_impl();
 282         else
 283           link_impl = sd_link->get_link_down()->get_impl();
 284         break;
 285       default:
 286         throw std::invalid_argument("Invalid add_route. Split-Duplex link without a direction: " +
 287                                     link.get_link()->get_name());
 288     }
 289     links.push_back(link_impl);
 290   }
 291   return links;
 292 }
 293
 294 resource::StandardLinkImpl* NetZoneImpl::get_link_by_name_or_null(const std::string& name) const
 295 {
 296   auto link_it = links_.find(name);
 297   if (link_it != links_.end())
 298     return link_it->second.get();
 299
 300   for (const auto* child : children_) {
 301     auto* link = child->get_link_by_name_or_null(name);
 302     if (link)
 303       return link;
 304   }
 305
 306   return nullptr;
 307 }
 308
 309 resource::SplitDuplexLinkImpl* NetZoneImpl::get_split_duplex_link_by_name_or_null(const std::string& name) const
 310 {
 311   auto link_it = split_duplex_links_.find(name);
 312   if (link_it != split_duplex_links_.end())
 313     return link_it->second.get();
 314
 315   for (const auto* child : children_) {
 316     auto* link = child->get_split_duplex_link_by_name_or_null(name);
 317     if (link)
 318       return link;
 319   }
 320
 321   return nullptr;
 322 }
 323
 324 resource::HostImpl* NetZoneImpl::get_host_by_name_or_null(const std::string& name) const
 325 {
 326   for (auto const& kv : hosts_) {
 327     auto* host = kv.second;
 328     if (host->get_name() == name)
 329       return host;
 330     /* keep old behavior where host and VMs were saved together on EngineImpl::hosts_
 331      * get hosts returns VMs too */
 332     auto* vm = host->get_vm_by_name_or_null(name);
 333     if (vm)
 334       return vm;
 335   }
 336
 337   for (const auto* child : children_) {
 338     auto* host = child->get_host_by_name_or_null(name);
 339     if (host)
 340       return host;
 341   }
 342
 343   return nullptr;
 344 }
 345
 346 std::vector<s4u::Host*> NetZoneImpl::get_filtered_hosts(const std::function<bool(s4u::Host*)>& filter) const
 347 {
 348   std::vector<s4u::Host*> filtered_list;
 349   for (auto const& kv : hosts_) {
 350     s4u::Host* h = kv.second->get_iface();
 351     if (filter(h))
 352       filtered_list.push_back(h);
 353     /* Engine::get_hosts returns the VMs too */
 354     for (auto* vm : h->get_impl()->get_vms()) {
 355       if (filter(vm))
 356         filtered_list.push_back(vm);
 357     }
 358   }
 359
 360   for (const auto* child : children_) {
 361     auto child_links = child->get_filtered_hosts(filter);
 362     filtered_list.insert(filtered_list.end(), std::make_move_iterator(child_links.begin()),
 363                          std::make_move_iterator(child_links.end()));
 364   }
 365   return filtered_list;
 366 }
 367
 368 void NetZoneImpl::add_route(NetPoint* /*src*/, NetPoint* /*dst*/, NetPoint* /*gw_src*/, NetPoint* /*gw_dst*/,
 369                             const std::vector<s4u::LinkInRoute>& /*link_list_*/, bool /*symmetrical*/)
 370 {
 371   xbt_die("NetZone '%s' does not accept new routes (wrong class).", get_cname());
 372 }
 373
 374 void NetZoneImpl::add_bypass_route(NetPoint* src, NetPoint* dst, NetPoint* gw_src, NetPoint* gw_dst,
 375                                    const std::vector<s4u::LinkInRoute>& link_list)
 376 {
 377   /* Argument validity checks */
 378   if (gw_dst) {
 379     XBT_DEBUG("Load bypassNetzoneRoute from %s@%s to %s@%s", src->get_cname(), gw_src->get_cname(), dst->get_cname(),
 380               gw_dst->get_cname());
 381     xbt_assert(not link_list.empty(), "Bypass route between %s@%s and %s@%s cannot be empty.", src->get_cname(),
 382                gw_src->get_cname(), dst->get_cname(), gw_dst->get_cname());
 383     xbt_assert(bypass_routes_.find({src, dst}) == bypass_routes_.end(),
 384                "The bypass route between %s@%s and %s@%s already exists.", src->get_cname(), gw_src->get_cname(),
 385                dst->get_cname(), gw_dst->get_cname());
 386   } else {
 387     XBT_DEBUG("Load bypassRoute from %s to %s", src->get_cname(), dst->get_cname());
 388     xbt_assert(not link_list.empty(), "Bypass route between %s and %s cannot be empty.", src->get_cname(),
 389                dst->get_cname());
 390     xbt_assert(bypass_routes_.find({src, dst}) == bypass_routes_.end(),
 391                "The bypass route between %s and %s already exists.", src->get_cname(), dst->get_cname());
 392   }
 393
 394   /* Build a copy that will be stored in the dict */
 395   auto* newRoute = new BypassRoute(gw_src, gw_dst);
 396   auto converted_list = get_link_list_impl(link_list, false);
 397   newRoute->links.insert(newRoute->links.end(), begin(converted_list), end(converted_list));
 398
 399   /* Store it */
 400   bypass_routes_.insert({{src, dst}, newRoute});
 401 }
 402
 403 /** @brief Get the common ancestor and its first children in each line leading to src and dst
 404  *
 405  * In the recursive case, this sets common_ancestor, src_ancestor and dst_ancestor are set as follows.
 406  * @verbatim
 407  *         platform root
 408  *               |
 409  *              ...                <- possibly long path
 410  *               |
 411  *         common_ancestor
 412  *           /        \
 413  *          /          \
 414  *         /            \          <- direct links
 415  *        /              \
 416  *       /                \
 417  *  src_ancestor     dst_ancestor  <- must be different in the recursive case
 418  *      |                   |
 419  *     ...                 ...     <-- possibly long paths (one hop or more)
 420  *      |                   |
 421  *     src                 dst
 422  *  @endverbatim
 423  *
 424  *  In the base case (when src and dst are in the same netzone), things are as follows:
 425  *  @verbatim
 426  *                  platform root
 427  *                        |
 428  *                       ...                      <-- possibly long path
 429  *                        |
 430  * common_ancestor==src_ancestor==dst_ancestor    <-- all the same value
 431  *                   /        \
 432  *                  /          \                  <-- direct links (exactly one hop)
 433  *                 /            \
 434  *              src              dst
 435  *  @endverbatim
 436  *
 437  * A specific recursive case occurs when src is the ancestor of dst. In this case,
 438  * the base case routing should be used so the common_ancestor is specifically set
 439  * to src_ancestor==dst_ancestor.
 440  * Naturally, things are completely symmetrical if dst is the ancestor of src.
 441  * @verbatim
 442  *            platform root
 443  *                  |
 444  *                 ...                <-- possibly long path
 445  *                  |
 446  *  src == src_ancestor==dst_ancestor==common_ancestor <-- same value
 447  *                  |
 448  *                 ...                <-- possibly long path (one hop or more)
 449  *                  |
 450  *                 dst
 451  *  @endverbatim
 452  */
 453 static void find_common_ancestors(const NetPoint* src, const NetPoint* dst,
 454                                   /* OUT */ NetZoneImpl** common_ancestor, NetZoneImpl** src_ancestor,
 455                                   NetZoneImpl** dst_ancestor)
 456 {
 457   /* Deal with the easy base case */
 458   if (src->get_englobing_zone() == dst->get_englobing_zone()) {
 459     *common_ancestor = src->get_englobing_zone();
 460     *src_ancestor    = *common_ancestor;
 461     *dst_ancestor    = *common_ancestor;
 462     return;
 463   }
 464
 465   /* engage the full recursive search */
 466
 467   /* (1) find the path to root of src and dst*/
 468   const NetZoneImpl* src_as = src->get_englobing_zone();
 469   const NetZoneImpl* dst_as = dst->get_englobing_zone();
 470
 471   xbt_assert(src_as, "Host %s must be in a netzone", src->get_cname());
 472   xbt_assert(dst_as, "Host %s must be in a netzone", dst->get_cname());
 473
 474   /* (2) find the path to the root routing component */
 475   std::vector<NetZoneImpl*> path_src;
 476   NetZoneImpl* current = src->get_englobing_zone();
 477   while (current != nullptr) {
 478     path_src.push_back(current);
 479     current = current->get_parent();
 480   }
 481   std::vector<NetZoneImpl*> path_dst;
 482   current = dst->get_englobing_zone();
 483   while (current != nullptr) {
 484     path_dst.push_back(current);
 485     current = current->get_parent();
 486   }
 487
 488   /* (3) find the common parent.
 489    * Before that, index_src and index_dst may be different, they both point to nullptr in path_src/path_dst
 490    * So we move them down simultaneously as long as they point to the same content.
 491    *
 492    * This works because all SimGrid platform have a unique root element (that is the last element of both paths).
 493    */
 494   NetZoneImpl* parent = nullptr; // the netzone we dropped on the previous loop iteration
 495   while (path_src.size() > 1 && path_dst.size() > 1 && path_src.back() == path_dst.back()) {
 496     parent = path_src.back();
 497     path_src.pop_back();
 498     path_dst.pop_back();
 499   }
 500
 501   /* (4) we found the difference at least. Finalize the returned values */
 502   *src_ancestor = path_src.back();                  /* the first different parent of src */
 503   *dst_ancestor = path_dst.back();                  /* the first different parent of dst */
 504   if (*src_ancestor == *dst_ancestor) {             // src is the ancestor of dst, or the contrary
 505     *common_ancestor = *src_ancestor;
 506   } else {
 507     xbt_assert(parent != nullptr);
 508     *common_ancestor = parent;
 509   }
 510 }
 511
 512 /* PRECONDITION: this is the common ancestor of src and dst */
 513 bool NetZoneImpl::get_bypass_route(const NetPoint* src, const NetPoint* dst,
 514                                    /* OUT */ std::vector<resource::StandardLinkImpl*>& links, double* latency,
 515                                    std::unordered_set<NetZoneImpl*>& netzones)
 516 {
 517   // If never set a bypass route return nullptr without any further computations
 518   if (bypass_routes_.empty())
 519     return false;
 520
 521   /* Base case, no recursion is needed */
 522   if (dst->get_englobing_zone() == this && src->get_englobing_zone() == this) {
 523     if (bypass_routes_.find({src, dst}) != bypass_routes_.end()) {
 524       const BypassRoute* bypassedRoute = bypass_routes_.at({src, dst});
 525       add_link_latency(links, bypassedRoute->links, latency);
 526       XBT_DEBUG("Found a bypass route from '%s' to '%s' with %zu links", src->get_cname(), dst->get_cname(),
 527                 bypassedRoute->links.size());
 528       return true;
 529     }
 530     return false;
 531   }
 532
 533   /* Engage recursive search */
 534
 535   /* (1) find the path to the root routing component */
 536   std::vector<NetZoneImpl*> path_src;
 537   NetZoneImpl* current = src->get_englobing_zone();
 538   while (current != nullptr) {
 539     path_src.push_back(current);
 540     current = current->parent_;
 541   }
 542
 543   std::vector<NetZoneImpl*> path_dst;
 544   current = dst->get_englobing_zone();
 545   while (current != nullptr) {
 546     path_dst.push_back(current);
 547     current = current->parent_;
 548   }
 549
 550   /* (2) find the common parent */
 551   while (path_src.size() > 1 && path_dst.size() > 1 && path_src.back() == path_dst.back()) {
 552     path_src.pop_back();
 553     path_dst.pop_back();
 554   }
 555
 556   /* (3) Search for a bypass making the path up to the ancestor useless */
 557   const BypassRoute* bypassedRoute = nullptr;
 558   std::pair<kernel::routing::NetPoint*, kernel::routing::NetPoint*> key;
 559   // Search for a bypass with the given indices. Returns true if found. Initialize variables `bypassedRoute' and `key'.
 560   auto lookup = [&bypassedRoute, &key, &path_src, &path_dst, this](unsigned src_index, unsigned dst_index) {
 561     if (src_index < path_src.size() && dst_index < path_dst.size()) {
 562       key      = {path_src[src_index]->netpoint_, path_dst[dst_index]->netpoint_};
 563       auto bpr = bypass_routes_.find(key);
 564       if (bpr != bypass_routes_.end()) {
 565         bypassedRoute = bpr->second;
 566         return true;
 567       }
 568     }
 569     return false;
 570   };
 571
 572   for (unsigned max = 0, max_index = std::max(path_src.size(), path_dst.size()); max < max_index; max++) {
 573     for (unsigned i = 0; i < max; i++) {
 574       if (lookup(i, max) || lookup(max, i))
 575         break;
 576     }
 577     if (bypassedRoute || lookup(max, max))
 578       break;
 579   }
 580
 581   /* (4) If we have the bypass, use it. If not, caller will do the Right Thing. */
 582   if (bypassedRoute) {
 583     XBT_DEBUG("Found a bypass route from '%s' to '%s' with %zu links. We may have to complete it with recursive "
 584               "calls to getRoute",
 585               src->get_cname(), dst->get_cname(), bypassedRoute->links.size());
 586     if (src != key.first)
 587       get_global_route_with_netzones(src, bypassedRoute->gw_src, links, latency, netzones);
 588     add_link_latency(links, bypassedRoute->links, latency);
 589     if (dst != key.second)
 590       get_global_route_with_netzones(bypassedRoute->gw_dst, dst, links, latency, netzones);
 591     return true;
 592   }
 593   XBT_DEBUG("No bypass route from '%s' to '%s'.", src->get_cname(), dst->get_cname());
 594   return false;
 595 }
 596
 597 void NetZoneImpl::get_global_route(const NetPoint* src, const NetPoint* dst,
 598                                    /* OUT */ std::vector<resource::StandardLinkImpl*>& links, double* latency)
 599 {
 600   std::unordered_set<NetZoneImpl*> netzones;
 601   get_global_route_with_netzones(src, dst, links, latency, netzones);
 602 }
 603
 604 void NetZoneImpl::get_global_route_with_netzones(const NetPoint* src, const NetPoint* dst,
 605                                                  /* OUT */ std::vector<resource::StandardLinkImpl*>& links,
 606                                                  double* latency, std::unordered_set<NetZoneImpl*>& netzones)
 607 {
 608   Route route;
 609
 610   XBT_DEBUG("Resolve route from '%s' to '%s'", src->get_cname(), dst->get_cname());
 611
 612   /* Find how src and dst are interconnected */
 613   NetZoneImpl* common_ancestor;
 614   NetZoneImpl* src_ancestor;
 615   NetZoneImpl* dst_ancestor;
 616   find_common_ancestors(src, dst, &common_ancestor, &src_ancestor, &dst_ancestor);
 617   XBT_DEBUG("find_common_ancestors: common ancestor '%s' src ancestor '%s' dst ancestor '%s'",
 618             common_ancestor->get_cname(), src_ancestor->get_cname(), dst_ancestor->get_cname());
 619
 620   netzones.insert(src->get_englobing_zone());
 621   netzones.insert(dst->get_englobing_zone());
 622   netzones.insert(common_ancestor);
 623   /* Check whether a direct bypass is defined. If so, use it and bail out */
 624   if (common_ancestor->get_bypass_route(src, dst, links, latency, netzones))
 625     return;
 626
 627   /* If src and dst are in the same netzone, life is good */
 628   if (src_ancestor == dst_ancestor) { /* SURF_ROUTING_BASE */
 629     route.link_list_ = std::move(links);
 630     common_ancestor->get_local_route(src, dst, &route, latency);
 631     links = std::move(route.link_list_);
 632     return;
 633   }
 634
 635   /* Not in the same netzone, no bypass. We'll have to find our path between the netzones recursively */
 636   common_ancestor->get_local_route(src_ancestor->netpoint_, dst_ancestor->netpoint_, &route, latency);
 637   xbt_assert((route.gw_src_ != nullptr) && (route.gw_dst_ != nullptr), "Bad gateways for route from '%s' to '%s'.",
 638              src->get_cname(), dst->get_cname());
 639
 640   /* If source gateway is not our source, we have to recursively find our way up to this point */
 641   if (src != route.gw_src_)
 642     get_global_route_with_netzones(src, route.gw_src_, links, latency, netzones);
 643   links.insert(links.end(), begin(route.link_list_), end(route.link_list_));
 644
 645   /* If dest gateway is not our destination, we have to recursively find our way from this point */
 646   if (route.gw_dst_ != dst)
 647     get_global_route_with_netzones(route.gw_dst_, dst, links, latency, netzones);
 648 }
 649
 650 void NetZoneImpl::seal()
 651 {
 652   /* already sealed netzone */
 653   if (sealed_)
 654     return;
 655   do_seal(); // derived class' specific sealing procedure
 656
 657   /* seals sub-netzones and hosts */
 658   for (auto* host : get_all_hosts()) {
 659     host->seal();
 660   }
 661
 662   /* sealing links */
 663   for (auto const& kv : links_)
 664     kv.second->get_iface()->seal();
 665
 666   for (auto* sub_net : get_children()) {
 667     sub_net->seal();
 668   }
 669   sealed_ = true;
 670   s4u::NetZone::on_seal(piface_);
 671 }
 672
 673 void NetZoneImpl::set_parent(NetZoneImpl* parent)
 674 {
 675   xbt_assert(not sealed_, "Impossible to set parent to an already sealed NetZone(%s)", this->get_cname());
 676   parent_ = parent;
 677   netpoint_->set_englobing_zone(parent_);
 678   if (parent) {
 679     /* adding this class as child */
 680     parent->add_child(this);
 681     /* copying models from parent host, to be reviewed when we allow multi-models */
 682     set_network_model(parent->get_network_model());
 683     set_cpu_pm_model(parent->get_cpu_pm_model());
 684     set_cpu_vm_model(parent->get_cpu_vm_model());
 685     set_disk_model(parent->get_disk_model());
 686     set_host_model(parent->get_host_model());
 687   }
 688 }
 689
 690 void NetZoneImpl::set_network_model(std::shared_ptr<resource::NetworkModel> netmodel)
 691 {
 692   xbt_assert(not sealed_, "Impossible to set network model to an already sealed NetZone(%s)", this->get_cname());
 693   network_model_ = std::move(netmodel);
 694 }
 695
 696 void NetZoneImpl::set_cpu_vm_model(std::shared_ptr<resource::CpuModel> cpu_model)
 697 {
 698   xbt_assert(not sealed_, "Impossible to set CPU model to an already sealed NetZone(%s)", this->get_cname());
 699   cpu_model_vm_ = std::move(cpu_model);
 700 }
 701
 702 void NetZoneImpl::set_cpu_pm_model(std::shared_ptr<resource::CpuModel> cpu_model)
 703 {
 704   xbt_assert(not sealed_, "Impossible to set CPU model to an already sealed NetZone(%s)", this->get_cname());
 705   cpu_model_pm_ = std::move(cpu_model);
 706 }
 707
 708 void NetZoneImpl::set_disk_model(std::shared_ptr<resource::DiskModel> disk_model)
 709 {
 710   xbt_assert(not sealed_, "Impossible to set disk model to an already sealed NetZone(%s)", this->get_cname());
 711   disk_model_ = std::move(disk_model);
 712 }
 713
 714 void NetZoneImpl::set_host_model(std::shared_ptr<resource::HostModel> host_model)
 715 {
 716   xbt_assert(not sealed_, "Impossible to set host model to an already sealed NetZone(%s)", this->get_cname());
 717   host_model_ = std::move(host_model);
 718 }
 719
 720 const NetZoneImpl* NetZoneImpl::get_netzone_recursive(const NetPoint* netpoint) const
 721 {
 722   xbt_assert(netpoint && netpoint->is_netzone(), "Netpoint %s must be of the type NetZone",
 723              netpoint ? netpoint->get_cname() : "nullptr");
 724
 725   if (netpoint == netpoint_)
 726     return this;
 727
 728   for (const auto* children : children_) {
 729     const NetZoneImpl* netzone = children->get_netzone_recursive(netpoint);
 730     if (netzone)
 731       return netzone;
 732   }
 733   return nullptr;
 734 }
 735
 736 bool NetZoneImpl::is_component_recursive(const NetPoint* netpoint) const
 737 {
 738   /* check direct components */
 739   if (std::any_of(begin(vertices_), end(vertices_), [netpoint](const auto* elem) { return elem == netpoint; }))
 740     return true;
 741
 742   /* check childrens */
 743   return std::any_of(begin(children_), end(children_),
 744                      [netpoint](const auto* child) { return child->is_component_recursive(netpoint); });
 745 }
 746 } // namespace routing
 747 } // namespace kernel
 748 } // namespace simgrid