src/kernel/routing/DijkstraZone.cpp

   1 /* Copyright (c) 2009-2023. 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/DijkstraZone.hpp>
   7 #include <simgrid/kernel/routing/NetPoint.hpp>
   8 #include <xbt/string.hpp>
   9
  10 #include "src/kernel/resource/NetworkModel.hpp"
  11
  12 #include <climits>
  13 #include <queue>
  14 #include <vector>
  15
  16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(ker_routing_dijkstra, ker_platform, "Kernel Dijkstra Routing");
  17
  18 namespace simgrid {
  19 namespace kernel::routing {
  20
  21 class GraphNodeData {
  22 public:
  23   explicit GraphNodeData(unsigned long id) : id_(id) {}
  24   unsigned long id_;
  25   unsigned long graph_id_ = UINT_MAX; /* used for caching internal graph id's */
  26 };
  27
  28 void DijkstraZone::route_graph_delete(xbt_graph_t g)
  29 {
  30   xbt_graph_free_graph(
  31       g, [](void* n) { delete static_cast<GraphNodeData*>(n); }, [](void* e) { delete static_cast<Route*>(e); },
  32       nullptr);
  33 }
  34
  35 void DijkstraZone::do_seal()
  36 {
  37   unsigned int cursor;
  38   xbt_node_t node = nullptr;
  39
  40   /* Add the loopback if needed */
  41   if (get_network_model()->loopback_ && get_hierarchy() == RoutingMode::base) {
  42     xbt_dynar_foreach (xbt_graph_get_nodes(route_graph_.get()), cursor, node) {
  43       bool found      = false;
  44       xbt_edge_t edge = nullptr;
  45       unsigned int cursor2;
  46       xbt_dynar_foreach (xbt_graph_node_get_outedges(node), cursor2, edge) {
  47         if (xbt_graph_edge_get_target(edge) == node) { // There is an edge from node to itself
  48           found = true;
  49           break;
  50         }
  51       }
  52
  53       if (not found) {
  54         auto* route = new Route();
  55         route->link_list_.push_back(get_network_model()->loopback_.get());
  56         xbt_graph_new_edge(route_graph_.get(), node, node, route);
  57       }
  58     }
  59   }
  60
  61   /* initialize graph indexes in nodes after graph has been built */
  62   const_xbt_dynar_t nodes = xbt_graph_get_nodes(route_graph_.get());
  63
  64   xbt_dynar_foreach (nodes, cursor, node) {
  65     auto* data      = static_cast<GraphNodeData*>(xbt_graph_node_get_data(node));
  66     data->graph_id_ = cursor;
  67   }
  68 }
  69
  70 xbt_node_t DijkstraZone::route_graph_new_node(unsigned long id)
  71 {
  72   xbt_node_t node = xbt_graph_new_node(route_graph_.get(), new GraphNodeData(id));
  73   graph_node_map_.emplace(id, node);
  74
  75   return node;
  76 }
  77
  78 xbt_node_t DijkstraZone::node_map_search(unsigned long id)
  79 {
  80   auto ret = graph_node_map_.find(id);
  81   return ret == graph_node_map_.end() ? nullptr : ret->second;
  82 }
  83
  84 /* Parsing */
  85
  86 void DijkstraZone::get_local_route(const NetPoint* src, const NetPoint* dst, Route* route, double* lat)
  87 {
  88   get_route_check_params(src, dst);
  89   unsigned long src_id = src->id();
  90   unsigned long dst_id = dst->id();
  91
  92   const_xbt_dynar_t nodes = xbt_graph_get_nodes(route_graph_.get());
  93
  94   /* Use the graph_node id mapping set to quickly find the nodes */
  95   const s_xbt_node_t* src_elm = node_map_search(src_id);
  96   const s_xbt_node_t* dst_elm = node_map_search(dst_id);
  97
  98   unsigned long src_node_id = static_cast<GraphNodeData*>(xbt_graph_node_get_data(src_elm))->graph_id_;
  99   unsigned long dst_node_id = static_cast<GraphNodeData*>(xbt_graph_node_get_data(dst_elm))->graph_id_;
 100
 101   /* if the src and dst are the same */
 102   if (src_node_id == dst_node_id) {
 103     const s_xbt_node_t* node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
 104     const s_xbt_node_t* node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
 105     const s_xbt_edge_t* edge     = xbt_graph_get_edge(route_graph_.get(), node_s_v, node_e_v);
 106
 107     if (edge == nullptr)
 108       throw std::invalid_argument(xbt::string_printf("No route from '%s' to '%s'", src->get_cname(), dst->get_cname()));
 109
 110     const Route* e_route = static_cast<Route*>(xbt_graph_edge_get_data(edge));
 111
 112     insert_link_latency(route->link_list_, e_route->link_list_, lat);
 113   }
 114
 115   auto [elm, inserted]                 = route_cache_.try_emplace(src_id);
 116   std::vector<unsigned long>& pred_arr = elm->second;
 117
 118   if (inserted) { /* new element was inserted (not cached mode, or cache miss) */
 119     unsigned long nr_nodes = xbt_dynar_length(nodes);
 120     std::vector<unsigned long> cost_arr(nr_nodes); /* link cost from src to other hosts */
 121     pred_arr.resize(nr_nodes);              /* predecessors in path from src */
 122     using Qelt = std::pair<double, unsigned long>;
 123     std::priority_queue<Qelt, std::vector<Qelt>, std::greater<>> pqueue;
 124
 125     /* initialize */
 126     cost_arr[src_node_id] = 0;
 127
 128     for (unsigned long i = 0; i < nr_nodes; i++) {
 129       if (i != src_node_id) {
 130         cost_arr[i] = ULONG_MAX;
 131       }
 132
 133       pred_arr[i] = 0;
 134
 135       /* initialize priority queue */
 136       pqueue.emplace(cost_arr[i], i);
 137     }
 138
 139     /* apply dijkstra using the indexes from the graph's node array */
 140     while (not pqueue.empty()) {
 141       unsigned long v_id = pqueue.top().second;
 142       pqueue.pop();
 143       const s_xbt_node_t* v_node = xbt_dynar_get_as(nodes, v_id, xbt_node_t);
 144       xbt_edge_t edge            = nullptr;
 145       unsigned int cursor;
 146
 147       xbt_dynar_foreach (xbt_graph_node_get_outedges(v_node), cursor, edge) {
 148         const s_xbt_node_t* u_node           = xbt_graph_edge_get_target(edge);
 149         const GraphNodeData* data            = static_cast<GraphNodeData*>(xbt_graph_node_get_data(u_node));
 150         unsigned long u_id                   = data->graph_id_;
 151         const Route* tmp_e_route             = static_cast<Route*>(xbt_graph_edge_get_data(edge));
 152         unsigned long cost_v_u               = tmp_e_route->link_list_.size(); /* count of links, old model assume 1 */
 153
 154         if (cost_v_u + cost_arr[v_id] < cost_arr[u_id]) {
 155           pred_arr[u_id] = v_id;
 156           cost_arr[u_id] = cost_v_u + cost_arr[v_id];
 157           pqueue.emplace(cost_arr[u_id], u_id);
 158         }
 159       }
 160     }
 161   }
 162
 163   /* compose route path with links */
 164   NetPoint* gw_src   = nullptr;
 165   NetPoint* first_gw = nullptr;
 166
 167   for (unsigned long v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
 168     const s_xbt_node_t* node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
 169     const s_xbt_node_t* node_v      = xbt_dynar_get_as(nodes, v, xbt_node_t);
 170     const s_xbt_edge_t* edge        = xbt_graph_get_edge(route_graph_.get(), node_pred_v, node_v);
 171
 172     if (edge == nullptr)
 173       throw std::invalid_argument(xbt::string_printf("No route from '%s' to '%s'", src->get_cname(), dst->get_cname()));
 174
 175     const Route* e_route = static_cast<Route*>(xbt_graph_edge_get_data(edge));
 176
 177     const NetPoint* prev_gw_src = gw_src;
 178     gw_src                      = e_route->gw_src_;
 179     NetPoint* gw_dst            = e_route->gw_dst_;
 180
 181     if (v == dst_node_id)
 182       first_gw = gw_dst;
 183
 184     if (get_hierarchy() == RoutingMode::recursive && v != dst_node_id &&
 185         gw_dst->get_name() != prev_gw_src->get_name()) {
 186       std::vector<resource::StandardLinkImpl*> e_route_as_to_as;
 187
 188       const NetPoint* gw_dst_net_elm      = nullptr;
 189       const NetPoint* prev_gw_src_net_elm = nullptr;
 190       get_global_route(gw_dst_net_elm, prev_gw_src_net_elm, e_route_as_to_as, nullptr);
 191       std::reverse(begin(e_route_as_to_as), end(e_route_as_to_as));
 192       insert_link_latency(route->link_list_, e_route_as_to_as, lat);
 193     }
 194
 195     insert_link_latency(route->link_list_, e_route->link_list_, lat);
 196   }
 197
 198   if (get_hierarchy() == RoutingMode::recursive) {
 199     route->gw_src_ = gw_src;
 200     route->gw_dst_ = first_gw;
 201   }
 202
 203   if (not cached_)
 204     route_cache_.clear();
 205 }
 206
 207 void DijkstraZone::add_route(NetPoint* src, NetPoint* dst, NetPoint* gw_src, NetPoint* gw_dst,
 208                              const std::vector<s4u::LinkInRoute>& link_list, bool symmetrical)
 209 {
 210   add_route_check_params(src, dst, gw_src, gw_dst, link_list, symmetrical);
 211
 212   new_edge(src->id(), dst->id(),
 213            new_extended_route(get_hierarchy(), gw_src, gw_dst, get_link_list_impl(link_list, false), true));
 214
 215   if (symmetrical)
 216     new_edge(dst->id(), src->id(),
 217              new_extended_route(get_hierarchy(), gw_dst, gw_src, get_link_list_impl(link_list, true), false));
 218 }
 219
 220 void DijkstraZone::new_edge(unsigned long src_id, unsigned long dst_id, Route* route)
 221 {
 222   XBT_DEBUG("Create Route from '%lu' to '%lu'", src_id, dst_id);
 223
 224   // Get the extremities, or create them if they don't exist yet
 225   xbt_node_t src = node_map_search(src_id);
 226   if (src == nullptr)
 227     src = route_graph_new_node(src_id);
 228
 229   xbt_node_t dst = node_map_search(dst_id);
 230   if (dst == nullptr)
 231     dst = route_graph_new_node(dst_id);
 232
 233   // Make sure that this graph edge was not already added to the graph
 234   if (xbt_graph_get_edge(route_graph_.get(), src, dst) != nullptr) {
 235     if (route->gw_dst_ == nullptr || route->gw_src_ == nullptr)
 236       throw std::invalid_argument(
 237           xbt::string_printf("Route from %s to %s already exists", route->src_->get_cname(), route->dst_->get_cname()));
 238     else
 239       throw std::invalid_argument(xbt::string_printf("Route from %s@%s to %s@%s already exists",
 240                                                      route->src_->get_cname(), route->gw_src_->get_cname(),
 241                                                      route->dst_->get_cname(), route->gw_dst_->get_cname()));
 242   }
 243
 244   // Finally add it
 245   xbt_graph_new_edge(route_graph_.get(), src, dst, route);
 246 }
 247 } // namespace kernel::routing
 248
 249 namespace s4u {
 250 NetZone* create_dijkstra_zone(const std::string& name, bool cache)
 251 {
 252   return (new kernel::routing::DijkstraZone(name, cache))->get_iface();
 253 }
 254 } // namespace s4u
 255
 256 } // namespace simgrid