Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
c6ace477f33b2024010d5620848c0faa7565208f
[simgrid.git] / src / kernel / routing / FloydZone.cpp
1 /* Copyright (c) 2009-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/FloydZone.hpp"
7 #include "simgrid/kernel/routing/NetPoint.hpp"
8 #include "src/surf/network_interface.hpp"
9 #include "xbt/log.h"
10 #include "src/surf/xml/platf_private.hpp"
11
12 #include <cfloat>
13 #include <limits>
14
15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_floyd, surf, "Routing part of surf");
16
17 #define TO_FLOYD_COST(i, j) (cost_table_)[(i) + (j)*table_size]
18 #define TO_FLOYD_PRED(i, j) (predecessor_table_)[(i) + (j)*table_size]
19 #define TO_FLOYD_LINK(i, j) (link_table_)[(i) + (j)*table_size]
20
21 namespace simgrid {
22 namespace kernel {
23 namespace routing {
24
25 FloydZone::FloydZone(NetZone* father, std::string name) : RoutedZone(father, name)
26 {
27   predecessor_table_ = nullptr;
28   cost_table_        = nullptr;
29   link_table_        = nullptr;
30 }
31
32 FloydZone::~FloydZone()
33 {
34   if (link_table_ == nullptr) // Dealing with a parse error in the file?
35     return;
36   unsigned int table_size = getTableSize();
37   /* Delete link_table */
38   for (unsigned int i = 0; i < table_size; i++)
39     for (unsigned int j = 0; j < table_size; j++)
40       delete TO_FLOYD_LINK(i, j);
41   delete[] link_table_;
42
43   delete[] predecessor_table_;
44   delete[] cost_table_;
45 }
46
47 void FloydZone::get_local_route(NetPoint* src, NetPoint* dst, RouteCreationArgs* route, double* lat)
48 {
49   unsigned int table_size = getTableSize();
50
51   getRouteCheckParams(src, dst);
52
53   /* create a result route */
54   std::vector<RouteCreationArgs*> route_stack;
55   unsigned int cur = dst->id();
56   do {
57     int pred = TO_FLOYD_PRED(src->id(), cur);
58     if (pred == -1)
59       THROWF(arg_error, 0, "No route from '%s' to '%s'", src->get_cname(), dst->get_cname());
60     route_stack.push_back(TO_FLOYD_LINK(pred, cur));
61     cur = pred;
62   } while (cur != src->id());
63
64   if (hierarchy_ == RoutingMode::recursive) {
65     route->gw_src = route_stack.back()->gw_src;
66     route->gw_dst = route_stack.front()->gw_dst;
67   }
68
69   sg_netpoint_t prev_dst_gw = nullptr;
70   while (not route_stack.empty()) {
71     RouteCreationArgs* e_route = route_stack.back();
72     route_stack.pop_back();
73     if (hierarchy_ == RoutingMode::recursive && prev_dst_gw != nullptr &&
74         prev_dst_gw->get_cname() != e_route->gw_src->get_cname()) {
75       get_global_route(prev_dst_gw, e_route->gw_src, route->link_list, lat);
76     }
77
78     for (auto const& link : e_route->link_list) {
79       route->link_list.push_back(link);
80       if (lat)
81         *lat += link->latency();
82     }
83
84     prev_dst_gw = e_route->gw_dst;
85   }
86 }
87
88 void FloydZone::add_route(kernel::routing::NetPoint* src, kernel::routing::NetPoint* dst,
89                           kernel::routing::NetPoint* gw_src, kernel::routing::NetPoint* gw_dst,
90                           std::vector<simgrid::surf::LinkImpl*>& link_list, bool symmetrical)
91 {
92   /* set the size of table routing */
93   unsigned int table_size = getTableSize();
94
95   addRouteCheckParams(src, dst, gw_src, gw_dst, link_list, symmetrical);
96
97   if (not link_table_) {
98     /* Create Cost, Predecessor and Link tables */
99     cost_table_        = new double[table_size * table_size];             /* link cost from host to host */
100     predecessor_table_ = new int[table_size * table_size];                /* predecessor host numbers */
101     link_table_        = new RouteCreationArgs*[table_size * table_size]; /* actual link between src and dst */
102
103     /* Initialize costs and predecessors */
104     for (unsigned int i = 0; i < table_size; i++)
105       for (unsigned int j = 0; j < table_size; j++) {
106         TO_FLOYD_COST(i, j) = DBL_MAX;
107         TO_FLOYD_PRED(i, j) = -1;
108         TO_FLOYD_LINK(i, j) = nullptr;
109       }
110   }
111
112   /* Check that the route does not already exist */
113   if (gw_dst) // netzone route (to adapt the error message, if any)
114     xbt_assert(nullptr == TO_FLOYD_LINK(src->id(), dst->id()),
115                "The route between %s@%s and %s@%s already exists (Rq: routes are symmetrical by default).",
116                src->get_cname(), gw_src->get_cname(), dst->get_cname(), gw_dst->get_cname());
117   else
118     xbt_assert(nullptr == TO_FLOYD_LINK(src->id(), dst->id()),
119                "The route between %s and %s already exists (Rq: routes are symmetrical by default).", src->get_cname(),
120                dst->get_cname());
121
122   TO_FLOYD_LINK(src->id(), dst->id()) =
123       newExtendedRoute(hierarchy_, src, dst, gw_src, gw_dst, link_list, symmetrical, 1);
124   TO_FLOYD_PRED(src->id(), dst->id()) = src->id();
125   TO_FLOYD_COST(src->id(), dst->id()) = (TO_FLOYD_LINK(src->id(), dst->id()))->link_list.size();
126
127   if (symmetrical == true) {
128     if (gw_dst) // netzone route (to adapt the error message, if any)
129       xbt_assert(
130           nullptr == TO_FLOYD_LINK(dst->id(), src->id()),
131           "The route between %s@%s and %s@%s already exists. You should not declare the reverse path as symmetrical.",
132           dst->get_cname(), gw_dst->get_cname(), src->get_cname(), gw_src->get_cname());
133     else
134       xbt_assert(nullptr == TO_FLOYD_LINK(dst->id(), src->id()),
135                  "The route between %s and %s already exists. You should not declare the reverse path as symmetrical.",
136                  dst->get_cname(), src->get_cname());
137
138     if (gw_dst && gw_src) {
139       NetPoint* gw_tmp = gw_src;
140       gw_src           = gw_dst;
141       gw_dst           = gw_tmp;
142     }
143
144     if (not gw_src || not gw_dst)
145       XBT_DEBUG("Load Route from \"%s\" to \"%s\"", dst->get_cname(), src->get_cname());
146     else
147       XBT_DEBUG("Load NetzoneRoute from \"%s(%s)\" to \"%s(%s)\"", dst->get_cname(), gw_src->get_cname(),
148                 src->get_cname(), gw_dst->get_cname());
149
150     TO_FLOYD_LINK(dst->id(), src->id()) =
151         newExtendedRoute(hierarchy_, src, dst, gw_src, gw_dst, link_list, symmetrical, 0);
152     TO_FLOYD_PRED(dst->id(), src->id()) = dst->id();
153     TO_FLOYD_COST(dst->id(), src->id()) =
154         (TO_FLOYD_LINK(dst->id(), src->id()))->link_list.size(); /* count of links, old model assume 1 */
155   }
156 }
157
158 void FloydZone::seal()
159 {
160   /* set the size of table routing */
161   unsigned int table_size = getTableSize();
162
163   if (not link_table_) {
164     /* Create Cost, Predecessor and Link tables */
165     cost_table_        = new double[table_size * table_size];             /* link cost from host to host */
166     predecessor_table_ = new int[table_size * table_size];                /* predecessor host numbers */
167     link_table_        = new RouteCreationArgs*[table_size * table_size]; /* actual link between src and dst */
168
169     /* Initialize costs and predecessors */
170     for (unsigned int i = 0; i < table_size; i++)
171       for (unsigned int j = 0; j < table_size; j++) {
172         TO_FLOYD_COST(i, j) = DBL_MAX;
173         TO_FLOYD_PRED(i, j) = -1;
174         TO_FLOYD_LINK(i, j) = nullptr;
175       }
176   }
177
178   /* Add the loopback if needed */
179   if (surf_network_model->loopback_ && hierarchy_ == RoutingMode::base) {
180     for (unsigned int i = 0; i < table_size; i++) {
181       RouteCreationArgs* e_route = TO_FLOYD_LINK(i, i);
182       if (not e_route) {
183         e_route = new RouteCreationArgs();
184         e_route->link_list.push_back(surf_network_model->loopback_);
185         TO_FLOYD_LINK(i, i) = e_route;
186         TO_FLOYD_PRED(i, i) = i;
187         TO_FLOYD_COST(i, i) = 1;
188       }
189     }
190   }
191   /* Calculate path costs */
192   for (unsigned int c = 0; c < table_size; c++) {
193     for (unsigned int a = 0; a < table_size; a++) {
194       for (unsigned int b = 0; b < table_size; b++) {
195         if (TO_FLOYD_COST(a, c) < DBL_MAX && TO_FLOYD_COST(c, b) < DBL_MAX &&
196             (fabs(TO_FLOYD_COST(a, b) - DBL_MAX) < std::numeric_limits<double>::epsilon() ||
197              (TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b) < TO_FLOYD_COST(a, b)))) {
198           TO_FLOYD_COST(a, b) = TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b);
199           TO_FLOYD_PRED(a, b) = TO_FLOYD_PRED(c, b);
200         }
201       }
202     }
203   }
204 }
205 }
206 }
207 }