src/kernel/routing/NetZoneImpl.cpp

   1 /* Copyright (c) 2006-2018. 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/NetZoneImpl.hpp"
   7 #include "simgrid/kernel/routing/NetPoint.hpp"
   8 #include "simgrid/s4u/Engine.hpp"
   9 #include "simgrid/s4u/Host.hpp"
  10 #include "src/surf/cpu_interface.hpp"
  11 #include "src/surf/network_interface.hpp"
  12 #include "src/surf/xml/platf_private.hpp"
  13 #include "surf/surf.hpp"
  14
  15 XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(surf_route);
  16
  17 namespace simgrid {
  18 namespace kernel {
  19 namespace routing {
  20
  21 class BypassRoute {
  22 public:
  23   explicit BypassRoute(NetPoint* gwSrc, NetPoint* gwDst) : gw_src(gwSrc), gw_dst(gwDst) {}
  24   NetPoint* gw_src;
  25   NetPoint* gw_dst;
  26   std::vector<resource::LinkImpl*> links;
  27 };
  28
  29 NetZoneImpl::NetZoneImpl(NetZoneImpl* father, std::string name) : piface_(this), father_(father), name_(name)
  30 {
  31   xbt_assert(nullptr == simgrid::s4u::Engine::get_instance()->netpoint_by_name_or_null(name.c_str()),
  32              "Refusing to create a second NetZone called '%s'.", name.c_str());
  33
  34   netpoint_ = new NetPoint(name, NetPoint::Type::NetZone, father);
  35   XBT_DEBUG("NetZone '%s' created with the id '%u'", name.c_str(), netpoint_->id());
  36 }
  37
  38 NetZoneImpl::~NetZoneImpl()
  39 {
  40   for (auto const& nz : children_)
  41     delete nz;
  42
  43   for (auto const& kv : bypass_routes_)
  44     delete kv.second;
  45
  46   simgrid::s4u::Engine::get_instance()->netpoint_unregister(netpoint_);
  47 }
  48 const char* NetZoneImpl::get_cname() const
  49 {
  50   return name_.c_str();
  51 }
  52 NetZoneImpl* NetZoneImpl::get_father()
  53 {
  54   return father_;
  55 }
  56 void NetZoneImpl::seal()
  57 {
  58   sealed_ = true;
  59 }
  60 /** @brief Returns the list of direct children (no grand-children)
  61  *
  62  * This returns the internal data, no copy. Don't mess with it.
  63  */
  64 std::vector<NetZoneImpl*>* NetZoneImpl::get_children()
  65 {
  66   return &children_;
  67 }
  68 /** @brief Returns the list of the hosts found in this NetZone (not recursively)
  69  *
  70  * Only the hosts that are directly contained in this NetZone are retrieved,
  71  * not the ones contained in sub-netzones.
  72  */
  73 std::vector<s4u::Host*> NetZoneImpl::get_all_hosts()
  74 {
  75   std::vector<s4u::Host*> res;
  76   for (auto const& card : get_vertices()) {
  77     s4u::Host* host = simgrid::s4u::Host::by_name_or_null(card->get_name());
  78     if (host != nullptr)
  79       res.push_back(host);
  80   }
  81   return res;
  82 }
  83 int NetZoneImpl::get_host_count()
  84 {
  85   int count = 0;
  86   for (auto const& card : get_vertices()) {
  87     s4u::Host* host = simgrid::s4u::Host::by_name_or_null(card->get_name());
  88     if (host != nullptr)
  89       count++;
  90   }
  91   return count;
  92 }
  93
  94 simgrid::s4u::Host* NetZoneImpl::create_host(const char* name, std::vector<double>* speedPerPstate, int coreAmount,
  95                                              std::map<std::string, std::string>* props)
  96 {
  97   simgrid::s4u::Host* res = new simgrid::s4u::Host(name);
  98
  99   if (hierarchy_ == RoutingMode::unset)
 100     hierarchy_ = RoutingMode::base;
 101
 102   res->pimpl_netpoint = new NetPoint(name, NetPoint::Type::Host, this);
 103
 104   surf_cpu_model_pm->create_cpu(res, speedPerPstate, coreAmount);
 105
 106   if (props != nullptr)
 107     for (auto const& kv : *props)
 108       res->set_property(kv.first, kv.second);
 109
 110   simgrid::s4u::Host::on_creation(*res); // notify the signal
 111
 112   return res;
 113 }
 114
 115 int NetZoneImpl::add_component(kernel::routing::NetPoint* elm)
 116 {
 117   vertices_.push_back(elm);
 118   return vertices_.size() - 1; // The rank of the newly created object
 119 }
 120 void NetZoneImpl::add_route(kernel::routing::NetPoint* /*src*/, kernel::routing::NetPoint* /*dst*/,
 121                             kernel::routing::NetPoint* /*gw_src*/, kernel::routing::NetPoint* /*gw_dst*/,
 122                             std::vector<kernel::resource::LinkImpl*>& /*link_list*/, bool /*symmetrical*/)
 123 {
 124   xbt_die("NetZone '%s' does not accept new routes (wrong class).", name_.c_str());
 125 }
 126
 127 void NetZoneImpl::add_bypass_route(NetPoint* src, NetPoint* dst, NetPoint* gw_src, NetPoint* gw_dst,
 128                                    std::vector<resource::LinkImpl*>& link_list, bool symmetrical)
 129 {
 130   /* Argument validity checks */
 131   if (gw_dst) {
 132     XBT_DEBUG("Load bypassNetzoneRoute from %s@%s to %s@%s", src->get_cname(), gw_src->get_cname(), dst->get_cname(),
 133               gw_dst->get_cname());
 134     xbt_assert(not link_list.empty(), "Bypass route between %s@%s and %s@%s cannot be empty.", src->get_cname(),
 135                gw_src->get_cname(), dst->get_cname(), gw_dst->get_cname());
 136     xbt_assert(bypass_routes_.find({src, dst}) == bypass_routes_.end(),
 137                "The bypass route between %s@%s and %s@%s already exists.", src->get_cname(), gw_src->get_cname(),
 138                dst->get_cname(), gw_dst->get_cname());
 139   } else {
 140     XBT_DEBUG("Load bypassRoute from %s to %s", src->get_cname(), dst->get_cname());
 141     xbt_assert(not link_list.empty(), "Bypass route between %s and %s cannot be empty.", src->get_cname(),
 142                dst->get_cname());
 143     xbt_assert(bypass_routes_.find({src, dst}) == bypass_routes_.end(),
 144                "The bypass route between %s and %s already exists.", src->get_cname(), dst->get_cname());
 145   }
 146
 147   /* Build a copy that will be stored in the dict */
 148   kernel::routing::BypassRoute* newRoute = new kernel::routing::BypassRoute(gw_src, gw_dst);
 149   for (auto const& link : link_list)
 150     newRoute->links.push_back(link);
 151
 152   /* Store it */
 153   bypass_routes_.insert({{src, dst}, newRoute});
 154 }
 155
 156 /** @brief Get the common ancestor and its first children in each line leading to src and dst
 157  *
 158  * In the recursive case, this sets common_ancestor, src_ancestor and dst_ancestor are set as follows.
 159  * @verbatim
 160  *         platform root
 161  *               |
 162  *              ...                <- possibly long path
 163  *               |
 164  *         common_ancestor
 165  *           /        \
 166  *          /          \
 167  *         /            \          <- direct links
 168  *        /              \
 169  *       /                \
 170  *  src_ancestor     dst_ancestor  <- must be different in the recursive case
 171  *      |                   |
 172  *     ...                 ...     <-- possibly long paths (one hop or more)
 173  *      |                   |
 174  *     src                 dst
 175  *  @endverbatim
 176  *
 177  *  In the base case (when src and dst are in the same netzone), things are as follows:
 178  *  @verbatim
 179  *                  platform root
 180  *                        |
 181  *                       ...                      <-- possibly long path
 182  *                        |
 183  * common_ancestor==src_ancestor==dst_ancestor    <-- all the same value
 184  *                   /        \
 185  *                  /          \                  <-- direct links (exactly one hop)
 186  *                 /            \
 187  *              src              dst
 188  *  @endverbatim
 189  *
 190  * A specific recursive case occurs when src is the ancestor of dst. In this case,
 191  * the base case routing should be used so the common_ancestor is specifically set
 192  * to src_ancestor==dst_ancestor.
 193  * Naturally, things are completely symmetrical if dst is the ancestor of src.
 194  * @verbatim
 195  *            platform root
 196  *                  |
 197  *                 ...                <-- possibly long path
 198  *                  |
 199  *  src == src_ancestor==dst_ancestor==common_ancestor <-- same value
 200  *                  |
 201  *                 ...                <-- possibly long path (one hop or more)
 202  *                  |
 203  *                 dst
 204  *  @endverbatim
 205  */
 206 static void find_common_ancestors(NetPoint* src, NetPoint* dst,
 207                                   /* OUT */ NetZoneImpl** common_ancestor, NetZoneImpl** src_ancestor,
 208                                   NetZoneImpl** dst_ancestor)
 209 {
 210   /* Deal with the easy base case */
 211   if (src->get_englobing_zone() == dst->get_englobing_zone()) {
 212     *common_ancestor = src->get_englobing_zone();
 213     *src_ancestor    = *common_ancestor;
 214     *dst_ancestor    = *common_ancestor;
 215     return;
 216   }
 217
 218   /* engage the full recursive search */
 219
 220   /* (1) find the path to root of src and dst*/
 221   NetZoneImpl* src_as = src->get_englobing_zone();
 222   NetZoneImpl* dst_as = dst->get_englobing_zone();
 223
 224   xbt_assert(src_as, "Host %s must be in a netzone", src->get_cname());
 225   xbt_assert(dst_as, "Host %s must be in a netzone", dst->get_cname());
 226
 227   /* (2) find the path to the root routing component */
 228   std::vector<NetZoneImpl*> path_src;
 229   NetZoneImpl* current = src->get_englobing_zone();
 230   while (current != nullptr) {
 231     path_src.push_back(current);
 232     current = static_cast<NetZoneImpl*>(current->get_father());
 233   }
 234   std::vector<NetZoneImpl*> path_dst;
 235   current = dst->get_englobing_zone();
 236   while (current != nullptr) {
 237     path_dst.push_back(current);
 238     current = static_cast<NetZoneImpl*>(current->get_father());
 239   }
 240
 241   /* (3) find the common father.
 242    * Before that, index_src and index_dst may be different, they both point to nullptr in path_src/path_dst
 243    * So we move them down simultaneously as long as they point to the same content.
 244    *
 245    * This works because all SimGrid platform have a unique root element (that is the last element of both paths).
 246    */
 247   NetZoneImpl* father = nullptr; // the netzone we dropped on the previous loop iteration
 248   while (path_src.size() > 1 && path_dst.size() > 1 &&
 249          path_src.at(path_src.size() - 1) == path_dst.at(path_dst.size() - 1)) {
 250     father = path_src.at(path_src.size() - 1);
 251     path_src.pop_back();
 252     path_dst.pop_back();
 253   }
 254
 255   /* (4) we found the difference at least. Finalize the returned values */
 256   *src_ancestor = path_src.at(path_src.size() - 1); /* the first different father of src */
 257   *dst_ancestor = path_dst.at(path_dst.size() - 1); /* the first different father of dst */
 258   if (*src_ancestor == *dst_ancestor) {             // src is the ancestor of dst, or the contrary
 259     *common_ancestor = *src_ancestor;
 260   } else {
 261     *common_ancestor = father;
 262   }
 263 }
 264
 265 /* PRECONDITION: this is the common ancestor of src and dst */
 266 bool NetZoneImpl::get_bypass_route(routing::NetPoint* src, routing::NetPoint* dst,
 267                                    /* OUT */ std::vector<resource::LinkImpl*>& links, double* latency)
 268 {
 269   // If never set a bypass route return nullptr without any further computations
 270   if (bypass_routes_.empty())
 271     return false;
 272
 273   /* Base case, no recursion is needed */
 274   if (dst->get_englobing_zone() == this && src->get_englobing_zone() == this) {
 275     if (bypass_routes_.find({src, dst}) != bypass_routes_.end()) {
 276       BypassRoute* bypassedRoute = bypass_routes_.at({src, dst});
 277       for (resource::LinkImpl* const& link : bypassedRoute->links) {
 278         links.push_back(link);
 279         if (latency)
 280           *latency += link->get_latency();
 281       }
 282       XBT_DEBUG("Found a bypass route from '%s' to '%s' with %zu links", src->get_cname(), dst->get_cname(),
 283                 bypassedRoute->links.size());
 284       return true;
 285     }
 286     return false;
 287   }
 288
 289   /* Engage recursive search */
 290
 291   /* (1) find the path to the root routing component */
 292   std::vector<NetZoneImpl*> path_src;
 293   NetZoneImpl* current = src->get_englobing_zone();
 294   while (current != nullptr) {
 295     path_src.push_back(static_cast<NetZoneImpl*>(current));
 296     current = current->father_;
 297   }
 298
 299   std::vector<NetZoneImpl*> path_dst;
 300   current = dst->get_englobing_zone();
 301   while (current != nullptr) {
 302     path_dst.push_back(static_cast<NetZoneImpl*>(current));
 303     current = current->father_;
 304   }
 305
 306   /* (2) find the common father */
 307   while (path_src.size() > 1 && path_dst.size() > 1 &&
 308          path_src.at(path_src.size() - 1) == path_dst.at(path_dst.size() - 1)) {
 309     path_src.pop_back();
 310     path_dst.pop_back();
 311   }
 312
 313   int max_index_src = path_src.size() - 1;
 314   int max_index_dst = path_dst.size() - 1;
 315
 316   int max_index = std::max(max_index_src, max_index_dst);
 317
 318   /* (3) Search for a bypass making the path up to the ancestor useless */
 319   BypassRoute* bypassedRoute = nullptr;
 320   std::pair<kernel::routing::NetPoint*, kernel::routing::NetPoint*> key;
 321   for (int max = 0; max <= max_index; max++) {
 322     for (int i = 0; i < max; i++) {
 323       if (i <= max_index_src && max <= max_index_dst) {
 324         key = {path_src.at(i)->netpoint_, path_dst.at(max)->netpoint_};
 325         auto bpr = bypass_routes_.find(key);
 326         if (bpr != bypass_routes_.end()) {
 327           bypassedRoute = bpr->second;
 328           break;
 329         }
 330       }
 331       if (max <= max_index_src && i <= max_index_dst) {
 332         key = {path_src.at(max)->netpoint_, path_dst.at(i)->netpoint_};
 333         auto bpr = bypass_routes_.find(key);
 334         if (bpr != bypass_routes_.end()) {
 335           bypassedRoute = bpr->second;
 336           break;
 337         }
 338       }
 339     }
 340
 341     if (bypassedRoute)
 342       break;
 343
 344     if (max <= max_index_src && max <= max_index_dst) {
 345       key = {path_src.at(max)->netpoint_, path_dst.at(max)->netpoint_};
 346       auto bpr = bypass_routes_.find(key);
 347       if (bpr != bypass_routes_.end()) {
 348         bypassedRoute = bpr->second;
 349         break;
 350       }
 351     }
 352   }
 353
 354   /* (4) If we have the bypass, use it. If not, caller will do the Right Thing. */
 355   if (bypassedRoute) {
 356     XBT_DEBUG("Found a bypass route from '%s' to '%s' with %zu links. We may have to complete it with recursive "
 357               "calls to getRoute",
 358               src->get_cname(), dst->get_cname(), bypassedRoute->links.size());
 359     if (src != key.first)
 360       get_global_route(src, bypassedRoute->gw_src, links, latency);
 361     for (resource::LinkImpl* const& link : bypassedRoute->links) {
 362       links.push_back(link);
 363       if (latency)
 364         *latency += link->get_latency();
 365     }
 366     if (dst != key.second)
 367       get_global_route(bypassedRoute->gw_dst, dst, links, latency);
 368     return true;
 369   }
 370   XBT_DEBUG("No bypass route from '%s' to '%s'.", src->get_cname(), dst->get_cname());
 371   return false;
 372 }
 373
 374 void NetZoneImpl::get_global_route(NetPoint* src, NetPoint* dst,
 375                                    /* OUT */ std::vector<resource::LinkImpl*>& links, double* latency)
 376 {
 377   RouteCreationArgs route;
 378
 379   XBT_DEBUG("Resolve route from '%s' to '%s'", src->get_cname(), dst->get_cname());
 380
 381   /* Find how src and dst are interconnected */
 382   NetZoneImpl *common_ancestor;
 383   NetZoneImpl *src_ancestor;
 384   NetZoneImpl *dst_ancestor;
 385   find_common_ancestors(src, dst, &common_ancestor, &src_ancestor, &dst_ancestor);
 386   XBT_DEBUG("elements_father: common ancestor '%s' src ancestor '%s' dst ancestor '%s'", common_ancestor->get_cname(),
 387             src_ancestor->get_cname(), dst_ancestor->get_cname());
 388
 389   /* Check whether a direct bypass is defined. If so, use it and bail out */
 390   if (common_ancestor->get_bypass_route(src, dst, links, latency))
 391     return;
 392
 393   /* If src and dst are in the same netzone, life is good */
 394   if (src_ancestor == dst_ancestor) { /* SURF_ROUTING_BASE */
 395     route.link_list = std::move(links);
 396     common_ancestor->get_local_route(src, dst, &route, latency);
 397     links = std::move(route.link_list);
 398     return;
 399   }
 400
 401   /* Not in the same netzone, no bypass. We'll have to find our path between the netzones recursively */
 402
 403   common_ancestor->get_local_route(src_ancestor->netpoint_, dst_ancestor->netpoint_, &route, latency);
 404   xbt_assert((route.gw_src != nullptr) && (route.gw_dst != nullptr), "bad gateways for route from \"%s\" to \"%s\"",
 405              src->get_cname(), dst->get_cname());
 406
 407   /* If source gateway is not our source, we have to recursively find our way up to this point */
 408   if (src != route.gw_src)
 409     get_global_route(src, route.gw_src, links, latency);
 410   for (auto const& link : route.link_list)
 411     links.push_back(link);
 412
 413   /* If dest gateway is not our destination, we have to recursively find our way from this point */
 414   if (route.gw_dst != dst)
 415     get_global_route(route.gw_dst, dst, links, latency);
 416 }
 417 }
 418 }
 419 } // namespace