Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
snake_case LinkImpl (but the part that should to the engine)
[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 "src/surf/xml/platf_private.hpp"
10 #include "surf/surf.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   NetPoint* 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->get_latency();
82     }
83
84     prev_dst_gw = e_route->gw_dst;
85   }
86 }
87
88 void FloydZone::add_route(NetPoint* src, NetPoint* dst, NetPoint* gw_src, NetPoint* gw_dst,
89                           std::vector<resource::LinkImpl*>& link_list, bool symmetrical)
90 {
91   /* set the size of table routing */
92   unsigned int table_size = getTableSize();
93
94   addRouteCheckParams(src, dst, gw_src, gw_dst, link_list, symmetrical);
95
96   if (not link_table_) {
97     /* Create Cost, Predecessor and Link tables */
98     cost_table_        = new double[table_size * table_size];             /* link cost from host to host */
99     predecessor_table_ = new int[table_size * table_size];                /* predecessor host numbers */
100     link_table_        = new RouteCreationArgs*[table_size * table_size]; /* actual link between src and dst */
101
102     /* Initialize costs and predecessors */
103     for (unsigned int i = 0; i < table_size; i++)
104       for (unsigned int j = 0; j < table_size; j++) {
105         TO_FLOYD_COST(i, j) = DBL_MAX;
106         TO_FLOYD_PRED(i, j) = -1;
107         TO_FLOYD_LINK(i, j) = nullptr;
108       }
109   }
110
111   /* Check that the route does not already exist */
112   if (gw_dst) // netzone route (to adapt the error message, if any)
113     xbt_assert(nullptr == TO_FLOYD_LINK(src->id(), dst->id()),
114                "The route between %s@%s and %s@%s already exists (Rq: routes are symmetrical by default).",
115                src->get_cname(), gw_src->get_cname(), dst->get_cname(), gw_dst->get_cname());
116   else
117     xbt_assert(nullptr == TO_FLOYD_LINK(src->id(), dst->id()),
118                "The route between %s and %s already exists (Rq: routes are symmetrical by default).", src->get_cname(),
119                dst->get_cname());
120
121   TO_FLOYD_LINK(src->id(), dst->id()) =
122       newExtendedRoute(hierarchy_, src, dst, gw_src, gw_dst, link_list, symmetrical, 1);
123   TO_FLOYD_PRED(src->id(), dst->id()) = src->id();
124   TO_FLOYD_COST(src->id(), dst->id()) = (TO_FLOYD_LINK(src->id(), dst->id()))->link_list.size();
125
126   if (symmetrical == true) {
127     if (gw_dst) // netzone route (to adapt the error message, if any)
128       xbt_assert(
129           nullptr == TO_FLOYD_LINK(dst->id(), src->id()),
130           "The route between %s@%s and %s@%s already exists. You should not declare the reverse path as symmetrical.",
131           dst->get_cname(), gw_dst->get_cname(), src->get_cname(), gw_src->get_cname());
132     else
133       xbt_assert(nullptr == TO_FLOYD_LINK(dst->id(), src->id()),
134                  "The route between %s and %s already exists. You should not declare the reverse path as symmetrical.",
135                  dst->get_cname(), src->get_cname());
136
137     if (gw_dst && gw_src) {
138       NetPoint* gw_tmp = gw_src;
139       gw_src           = gw_dst;
140       gw_dst           = gw_tmp;
141     }
142
143     if (not gw_src || not gw_dst)
144       XBT_DEBUG("Load Route from \"%s\" to \"%s\"", dst->get_cname(), src->get_cname());
145     else
146       XBT_DEBUG("Load NetzoneRoute from \"%s(%s)\" to \"%s(%s)\"", dst->get_cname(), gw_src->get_cname(),
147                 src->get_cname(), gw_dst->get_cname());
148
149     TO_FLOYD_LINK(dst->id(), src->id()) =
150         newExtendedRoute(hierarchy_, src, dst, gw_src, gw_dst, link_list, symmetrical, 0);
151     TO_FLOYD_PRED(dst->id(), src->id()) = dst->id();
152     TO_FLOYD_COST(dst->id(), src->id()) =
153         (TO_FLOYD_LINK(dst->id(), src->id()))->link_list.size(); /* count of links, old model assume 1 */
154   }
155 }
156
157 void FloydZone::seal()
158 {
159   /* set the size of table routing */
160   unsigned int table_size = getTableSize();
161
162   if (not link_table_) {
163     /* Create Cost, Predecessor and Link tables */
164     cost_table_        = new double[table_size * table_size];             /* link cost from host to host */
165     predecessor_table_ = new int[table_size * table_size];                /* predecessor host numbers */
166     link_table_        = new RouteCreationArgs*[table_size * table_size]; /* actual link between src and dst */
167
168     /* Initialize costs and predecessors */
169     for (unsigned int i = 0; i < table_size; i++)
170       for (unsigned int j = 0; j < table_size; j++) {
171         TO_FLOYD_COST(i, j) = DBL_MAX;
172         TO_FLOYD_PRED(i, j) = -1;
173         TO_FLOYD_LINK(i, j) = nullptr;
174       }
175   }
176
177   /* Add the loopback if needed */
178   if (surf_network_model->loopback_ && hierarchy_ == RoutingMode::base) {
179     for (unsigned int i = 0; i < table_size; i++) {
180       RouteCreationArgs* e_route = TO_FLOYD_LINK(i, i);
181       if (not e_route) {
182         e_route = new RouteCreationArgs();
183         e_route->link_list.push_back(surf_network_model->loopback_);
184         TO_FLOYD_LINK(i, i) = e_route;
185         TO_FLOYD_PRED(i, i) = i;
186         TO_FLOYD_COST(i, i) = 1;
187       }
188     }
189   }
190   /* Calculate path costs */
191   for (unsigned int c = 0; c < table_size; c++) {
192     for (unsigned int a = 0; a < table_size; a++) {
193       for (unsigned int b = 0; b < table_size; b++) {
194         if (TO_FLOYD_COST(a, c) < DBL_MAX && TO_FLOYD_COST(c, b) < DBL_MAX &&
195             (fabs(TO_FLOYD_COST(a, b) - DBL_MAX) < std::numeric_limits<double>::epsilon() ||
196              (TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b) < TO_FLOYD_COST(a, b)))) {
197           TO_FLOYD_COST(a, b) = TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b);
198           TO_FLOYD_PRED(a, b) = TO_FLOYD_PRED(c, b);
199         }
200       }
201     }
202   }
203 }
204 }
205 }
206 }