Line data Source code
1 : /*
2 : * Copyright (C) 2004-2025 Savoir-faire Linux Inc.
3 : *
4 : * This program is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 3 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * This program is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : *
14 : * You should have received a copy of the GNU General Public License
15 : * along with this program. If not, see <https://www.gnu.org/licenses/>.
16 : */
17 :
18 : #include "routing_table.h"
19 :
20 : #include <dhtnet/multiplexed_socket.h>
21 : #include <opendht/infohash.h>
22 :
23 : #include <math.h>
24 : #include <stdio.h>
25 : #include <iostream>
26 : #include <iterator>
27 : #include <stdlib.h>
28 : #include <time.h>
29 :
30 : using namespace std::placeholders;
31 :
32 : namespace jami {
33 :
34 : using namespace dht;
35 :
36 845 : Bucket::Bucket(const NodeId& id)
37 845 : : lowerLimit_(id)
38 845 : {}
39 :
40 : bool
41 1159 : Bucket::addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket)
42 : {
43 1159 : return addNode(NodeInfo(socket));
44 : }
45 :
46 : bool
47 1393 : Bucket::addNode(NodeInfo&& info)
48 : {
49 1393 : auto nodeId = info.socket->deviceId();
50 1393 : if (nodes.try_emplace(nodeId, std::move(info)).second) {
51 1392 : connecting_nodes.erase(nodeId);
52 1392 : known_nodes.erase(nodeId);
53 1392 : mobile_nodes.erase(nodeId);
54 1392 : return true;
55 : }
56 1 : return false;
57 : }
58 :
59 : bool
60 1162 : Bucket::removeNode(const NodeId& nodeId)
61 : {
62 1162 : auto node = nodes.find(nodeId);
63 1162 : auto isMobile = node->second.isMobile_;
64 1162 : if (node == nodes.end())
65 3 : return false;
66 1159 : nodes.erase(nodeId);
67 1159 : if (isMobile) {
68 89 : addMobileNode(nodeId);
69 : } else {
70 1070 : addKnownNode(nodeId);
71 : }
72 :
73 1159 : return true;
74 : }
75 :
76 : std::set<NodeId>
77 10437 : Bucket::getNodeIds() const
78 : {
79 10437 : std::set<NodeId> nodesId;
80 28463 : for (auto const& key : nodes)
81 18026 : nodesId.insert(key.first);
82 10437 : return nodesId;
83 0 : }
84 :
85 : bool
86 8452 : Bucket::hasNode(const NodeId& nodeId) const
87 : {
88 8452 : return nodes.find(nodeId) != nodes.end();
89 : }
90 :
91 : bool
92 5349 : Bucket::addKnownNode(const NodeId& nodeId)
93 : {
94 5349 : if (!hasNode(nodeId)) {
95 4599 : if (known_nodes.emplace(nodeId).second) {
96 4321 : return true;
97 : }
98 : }
99 1028 : return false;
100 : }
101 :
102 : NodeId
103 205 : Bucket::getKnownNode(unsigned index) const
104 : {
105 205 : if (index > known_nodes.size()) {
106 1 : throw std::out_of_range("End of table for get known Node Id " + std::to_string(index));
107 : }
108 204 : auto it = known_nodes.begin();
109 204 : std::advance(it, index);
110 :
111 204 : return *it;
112 : }
113 :
114 : bool
115 103 : Bucket::addMobileNode(const NodeId& nodeId)
116 : {
117 103 : if (!hasNode(nodeId)) {
118 102 : if (mobile_nodes.emplace(nodeId).second) {
119 102 : known_nodes.erase(nodeId);
120 102 : return true;
121 : }
122 : }
123 1 : return false;
124 : }
125 :
126 : bool
127 991 : Bucket::addConnectingNode(const NodeId& nodeId)
128 : {
129 991 : if (!hasNode(nodeId)) {
130 991 : if (connecting_nodes.emplace(nodeId).second) {
131 939 : known_nodes.erase(nodeId);
132 939 : mobile_nodes.erase(nodeId);
133 939 : return true;
134 : }
135 : }
136 52 : return false;
137 : }
138 :
139 : std::set<NodeId>
140 1122 : Bucket::getKnownNodesRandom(unsigned numberNodes, std::mt19937_64& rd) const
141 : {
142 1122 : std::set<NodeId> nodesToReturn;
143 :
144 1122 : if (getKnownNodesSize() <= numberNodes)
145 973 : return getKnownNodes();
146 :
147 149 : std::uniform_int_distribution<unsigned> distrib(0, getKnownNodesSize() - 1);
148 :
149 353 : while (nodesToReturn.size() < numberNodes) {
150 204 : nodesToReturn.emplace(getKnownNode(distrib(rd)));
151 : }
152 :
153 149 : return nodesToReturn;
154 1122 : }
155 :
156 : asio::steady_timer&
157 0 : Bucket::getNodeTimer(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket)
158 : {
159 0 : auto node = nodes.find(socket->deviceId());
160 0 : if (node == nodes.end()) {
161 0 : throw std::range_error("Unable to find timer " + socket->deviceId().toString());
162 : }
163 0 : return node->second.refresh_timer;
164 : }
165 :
166 : bool
167 14 : Bucket::shutdownNode(const NodeId& nodeId)
168 : {
169 14 : auto node = nodes.find(nodeId);
170 :
171 14 : if (node != nodes.end()) {
172 12 : auto socket = node->second.socket;
173 12 : auto node = socket->deviceId();
174 12 : socket->shutdown();
175 12 : removeNode(node);
176 12 : return true;
177 12 : }
178 2 : return false;
179 : }
180 :
181 : void
182 877 : Bucket::shutdownAllNodes()
183 : {
184 1645 : while (not nodes.empty()) {
185 768 : auto it = nodes.begin();
186 768 : it->second.socket->shutdown();
187 768 : auto nodeId = it->first;
188 768 : removeNode(nodeId);
189 : }
190 877 : }
191 :
192 : void
193 0 : Bucket::printBucket(unsigned number) const
194 : {
195 0 : JAMI_ERROR("BUCKET Number: {:d}", number);
196 :
197 0 : unsigned nodeNum = 1;
198 0 : for (auto it = nodes.begin(); it != nodes.end(); ++it) {
199 0 : JAMI_DEBUG("Node {:s} Id: {:s} isMobile: {:s}",
200 : std::to_string(nodeNum),
201 : it->first.toString(),
202 : std::to_string(it->second.isMobile_));
203 0 : nodeNum++;
204 : }
205 0 : JAMI_ERROR("Mobile Nodes");
206 0 : nodeNum = 0;
207 0 : for (auto it = mobile_nodes.begin(); it != mobile_nodes.end(); ++it) {
208 0 : JAMI_DEBUG("Node {:s} Id: {:s}", std::to_string(nodeNum), (*it).toString());
209 0 : nodeNum++;
210 : }
211 :
212 0 : JAMI_ERROR("Known Nodes");
213 0 : nodeNum = 0;
214 0 : for (auto it = known_nodes.begin(); it != known_nodes.end(); ++it) {
215 0 : JAMI_DEBUG("Node {:s} Id: {:s}", std::to_string(nodeNum), (*it).toString());
216 0 : nodeNum++;
217 : }
218 0 : JAMI_ERROR("Connecting_nodes");
219 0 : nodeNum = 0;
220 0 : for (auto it = connecting_nodes.begin(); it != connecting_nodes.end(); ++it) {
221 0 : JAMI_DEBUG("Node {:s} Id: {:s}", std::to_string(nodeNum), (*it).toString());
222 0 : nodeNum++;
223 : }
224 0 : };
225 :
226 : void
227 176 : Bucket::changeMobility(const NodeId& nodeId, bool isMobile)
228 : {
229 176 : auto itn = nodes.find(nodeId);
230 176 : if (itn != nodes.end()) {
231 176 : itn->second.isMobile_ = isMobile;
232 : }
233 176 : }
234 :
235 : // For tests
236 :
237 : std::set<std::shared_ptr<dhtnet::ChannelSocketInterface>>
238 1 : Bucket::getNodeSockets() const
239 : {
240 1 : std::set<std::shared_ptr<dhtnet::ChannelSocketInterface>> sockets;
241 3 : for (auto const& info : nodes)
242 2 : sockets.insert(info.second.socket);
243 1 : return sockets;
244 0 : }
245 :
246 : // ####################################################################################################
247 :
248 579 : RoutingTable::RoutingTable()
249 : {
250 579 : buckets.emplace_back(NodeId::zero());
251 579 : }
252 :
253 : bool
254 10 : RoutingTable::addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket)
255 : {
256 10 : auto bucket = findBucket(socket->deviceId());
257 20 : return addNode(socket, bucket);
258 : }
259 :
260 : bool
261 1591 : RoutingTable::addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& channel,
262 : std::list<Bucket>::iterator& bucket)
263 : {
264 1591 : NodeId nodeId = channel->deviceId();
265 :
266 1591 : if (bucket->hasNode(nodeId) || id_ == nodeId) {
267 464 : return false;
268 : }
269 :
270 1391 : while (bucket->isFull()) {
271 374 : if (contains(bucket, id_)) {
272 264 : split(bucket);
273 264 : bucket = findBucket(nodeId);
274 :
275 : } else {
276 110 : return bucket->addNode(std::move(channel));
277 : }
278 : }
279 1017 : return bucket->addNode(std::move(channel));
280 : }
281 :
282 : bool
283 379 : RoutingTable::removeNode(const NodeId& nodeId)
284 : {
285 379 : return findBucket(nodeId)->removeNode(nodeId);
286 : }
287 :
288 : bool
289 410 : RoutingTable::hasNode(const NodeId& nodeId)
290 : {
291 410 : return findBucket(nodeId)->hasNode(nodeId);
292 : }
293 :
294 : bool
295 5198 : RoutingTable::addKnownNode(const NodeId& nodeId)
296 : {
297 5198 : if (id_ == nodeId)
298 1223 : return false;
299 :
300 3975 : auto bucket = findBucket(nodeId);
301 3975 : if (bucket == buckets.end())
302 0 : return false;
303 :
304 3975 : return bucket->addKnownNode(nodeId);
305 : }
306 :
307 : bool
308 15 : RoutingTable::addMobileNode(const NodeId& nodeId)
309 : {
310 15 : if (id_ == nodeId)
311 1 : return false;
312 :
313 14 : auto bucket = findBucket(nodeId);
314 :
315 14 : if (bucket == buckets.end())
316 0 : return 0;
317 :
318 14 : bucket->addMobileNode(nodeId);
319 14 : return 1;
320 : }
321 :
322 : void
323 2 : RoutingTable::removeMobileNode(const NodeId& nodeId)
324 : {
325 2 : return findBucket(nodeId)->removeMobileNode(nodeId);
326 : }
327 :
328 : bool
329 7 : RoutingTable::hasMobileNode(const NodeId& nodeId)
330 : {
331 7 : return findBucket(nodeId)->hasMobileNode(nodeId);
332 : };
333 :
334 : bool
335 887 : RoutingTable::addConnectingNode(const NodeId& nodeId)
336 : {
337 887 : if (id_ == nodeId)
338 1 : return false;
339 :
340 886 : auto bucket = findBucket(nodeId);
341 :
342 886 : if (bucket == buckets.end())
343 0 : return 0;
344 :
345 886 : bucket->addConnectingNode(nodeId);
346 886 : return 1;
347 : }
348 :
349 : void
350 0 : RoutingTable::removeConnectingNode(const NodeId& nodeId)
351 : {
352 0 : findBucket(nodeId)->removeConnectingNode(nodeId);
353 0 : }
354 :
355 : std::list<Bucket>::iterator
356 12766 : RoutingTable::findBucket(const NodeId& nodeId)
357 : {
358 12766 : if (buckets.empty())
359 0 : throw std::runtime_error("No bucket");
360 :
361 12766 : auto b = buckets.begin();
362 :
363 : while (true) {
364 19517 : auto next = std::next(b);
365 19517 : if (next == buckets.end())
366 12766 : return b;
367 10664 : if (std::memcmp(nodeId.data(), next->getLowerLimit().data(), nodeId.size()) < 0)
368 3913 : return b;
369 6751 : b = next;
370 6751 : }
371 : }
372 :
373 : std::vector<NodeId>
374 1036 : RoutingTable::closestNodes(const NodeId& nodeId, unsigned count)
375 : {
376 1036 : std::vector<NodeId> closestNodes;
377 1036 : auto bucket = findBucket(nodeId);
378 2392 : auto sortedBucketInsert = [&](const std::list<Bucket>::iterator& b) {
379 2392 : auto nodes = b->getNodeIds();
380 6894 : for (auto n : nodes) {
381 4502 : if (n != nodeId) {
382 3468 : auto here = std::find_if(closestNodes.begin(),
383 : closestNodes.end(),
384 9516 : [&nodeId, &n](NodeId& NodeId) {
385 9516 : return nodeId.xorCmp(n, NodeId) < 0;
386 : });
387 :
388 3468 : closestNodes.insert(here, n);
389 : }
390 : }
391 2392 : };
392 :
393 1036 : auto itn = bucket;
394 1036 : auto itp = (bucket == buckets.begin()) ? buckets.end() : std::prev(bucket);
395 2934 : while (itn != buckets.end() || itp != buckets.end()) {
396 1898 : if (itn != buckets.end()) {
397 1673 : sortedBucketInsert(itn);
398 1673 : itn = std::next(itn);
399 : }
400 1898 : if (itp != buckets.end()) {
401 719 : sortedBucketInsert(itp);
402 719 : itp = (itp == buckets.begin()) ? buckets.end() : std::prev(itp);
403 : }
404 : }
405 :
406 1036 : if (closestNodes.size() > count) {
407 491 : closestNodes.resize(count);
408 : }
409 :
410 2072 : return closestNodes;
411 0 : }
412 :
413 : void
414 0 : RoutingTable::printRoutingTable() const
415 : {
416 0 : int counter = 1;
417 0 : JAMI_DEBUG("SWARM: {:s} ", id_.toString());
418 0 : for (auto it = buckets.begin(); it != buckets.end(); ++it) {
419 0 : it->printBucket(counter);
420 0 : counter++;
421 : }
422 0 : JAMI_DEBUG("_____________________________________________________________________________");
423 0 : }
424 :
425 : void
426 2 : RoutingTable::shutdownNode(const NodeId& nodeId)
427 : {
428 2 : findBucket(nodeId)->shutdownNode(nodeId);
429 2 : }
430 :
431 : std::vector<NodeId>
432 4157 : RoutingTable::getNodes() const
433 : {
434 4157 : std::lock_guard lock(mutex_);
435 4157 : std::vector<NodeId> ret;
436 12179 : for (const auto& b : buckets) {
437 8022 : const auto& nodes = b.getNodeIds();
438 8022 : ret.insert(ret.end(), nodes.begin(), nodes.end());
439 8022 : }
440 8314 : return ret;
441 4157 : }
442 :
443 : std::vector<NodeId>
444 1 : RoutingTable::getKnownNodes() const
445 : {
446 1 : std::vector<NodeId> ret;
447 2 : for (const auto& b : buckets) {
448 1 : const auto& nodes = b.getKnownNodes();
449 1 : ret.insert(ret.end(), nodes.begin(), nodes.end());
450 : }
451 1 : return ret;
452 0 : }
453 :
454 : std::vector<NodeId>
455 1755 : RoutingTable::getMobileNodes() const
456 : {
457 1755 : std::vector<NodeId> ret;
458 5360 : for (const auto& b : buckets) {
459 3605 : const auto& nodes = b.getMobileNodes();
460 3605 : ret.insert(ret.end(), nodes.begin(), nodes.end());
461 : }
462 1755 : return ret;
463 0 : }
464 :
465 : std::vector<NodeId>
466 1 : RoutingTable::getConnectingNodes() const
467 : {
468 1 : std::vector<NodeId> ret;
469 2 : for (const auto& b : buckets) {
470 1 : const auto& nodes = b.getConnectingNodes();
471 1 : ret.insert(ret.end(), nodes.begin(), nodes.end());
472 : }
473 1 : return ret;
474 0 : }
475 :
476 : std::vector<NodeId>
477 0 : RoutingTable::getBucketMobileNodes() const
478 : {
479 0 : std::vector<NodeId> ret;
480 0 : auto bucket = findBucket(id_);
481 0 : const auto& nodes = bucket->getMobileNodes();
482 0 : ret.insert(ret.end(), nodes.begin(), nodes.end());
483 :
484 0 : return ret;
485 0 : }
486 :
487 : bool
488 3548 : RoutingTable::contains(const std::list<Bucket>::iterator& bucket, const NodeId& nodeId) const
489 : {
490 3548 : return NodeId::cmp(bucket->getLowerLimit(), nodeId) <= 0
491 5765 : && (std::next(bucket) == buckets.end()
492 5765 : || NodeId::cmp(nodeId, std::next(bucket)->getLowerLimit()) < 0);
493 : }
494 :
495 : std::vector<NodeId>
496 16 : RoutingTable::getAllNodes() const
497 : {
498 16 : std::vector<NodeId> ret;
499 32 : for (const auto& b : buckets) {
500 16 : const auto& nodes = b.getNodeIds();
501 16 : const auto& knownNodes = b.getKnownNodes();
502 16 : const auto& mobileNodes = b.getMobileNodes();
503 16 : const auto& connectingNodes = b.getConnectingNodes();
504 16 : ret.reserve(nodes.size() + knownNodes.size() + mobileNodes.size() + connectingNodes.size());
505 16 : ret.insert(ret.end(), nodes.begin(), nodes.end());
506 16 : ret.insert(ret.end(), knownNodes.begin(), knownNodes.end());
507 16 : ret.insert(ret.end(), mobileNodes.begin(), mobileNodes.end());
508 16 : ret.insert(ret.end(), connectingNodes.begin(), connectingNodes.end());
509 16 : }
510 16 : return ret;
511 0 : }
512 :
513 : void
514 11 : RoutingTable::deleteNode(const NodeId& nodeId)
515 : {
516 11 : auto bucket = findBucket(nodeId);
517 11 : bucket->shutdownNode(nodeId);
518 11 : bucket->removeConnectingNode(nodeId);
519 11 : bucket->removeKnownNode(nodeId);
520 11 : bucket->removeMobileNode(nodeId);
521 11 : }
522 :
523 : NodeId
524 264 : RoutingTable::middle(std::list<Bucket>::iterator& it) const
525 : {
526 264 : unsigned bit = depth(it);
527 264 : if (bit >= 8 * HASH_LEN)
528 0 : throw std::out_of_range("End of table");
529 :
530 264 : NodeId id = it->getLowerLimit();
531 264 : id.setBit(bit, true);
532 264 : return id;
533 : }
534 :
535 : unsigned
536 264 : RoutingTable::depth(std::list<Bucket>::iterator& bucket) const
537 : {
538 264 : int bit1 = bucket->getLowerLimit().lowbit();
539 264 : int bit2 = std::next(bucket) != buckets.end() ? std::next(bucket)->getLowerLimit().lowbit()
540 264 : : -1;
541 264 : return std::max(bit1, bit2) + 1;
542 : }
543 :
544 : bool
545 264 : RoutingTable::split(std::list<Bucket>::iterator& bucket)
546 : {
547 264 : NodeId id = middle(bucket);
548 264 : auto newBucketIt = buckets.emplace(std::next(bucket), id);
549 : // Re-assign nodes
550 264 : auto& nodeSwap = bucket->getNodes();
551 :
552 792 : for (auto it = nodeSwap.begin(); it != nodeSwap.end();) {
553 528 : auto& node = *it;
554 :
555 528 : auto nodeId = it->first;
556 :
557 528 : if (!contains(bucket, nodeId)) {
558 233 : newBucketIt->addNode(std::move(node.second));
559 233 : it = nodeSwap.erase(it);
560 : } else {
561 295 : ++it;
562 : }
563 : }
564 :
565 264 : auto connectingSwap = bucket->getConnectingNodes();
566 476 : for (auto it = connectingSwap.begin(); it != connectingSwap.end();) {
567 212 : auto nodeId = *it;
568 :
569 212 : if (!contains(bucket, nodeId)) {
570 103 : newBucketIt->addConnectingNode(nodeId);
571 103 : it = connectingSwap.erase(it);
572 103 : bucket->removeConnectingNode(nodeId);
573 : } else {
574 109 : ++it;
575 : }
576 : }
577 :
578 264 : auto knownSwap = bucket->getKnownNodes();
579 714 : for (auto it = knownSwap.begin(); it != knownSwap.end();) {
580 450 : auto nodeId = *it;
581 :
582 450 : if (!contains(bucket, nodeId)) {
583 239 : newBucketIt->addKnownNode(nodeId);
584 239 : it = knownSwap.erase(it);
585 239 : bucket->removeKnownNode(nodeId);
586 : } else {
587 211 : ++it;
588 : }
589 : }
590 :
591 264 : auto mobileSwap = bucket->getMobileNodes();
592 264 : for (auto it = mobileSwap.begin(); it != mobileSwap.end();) {
593 0 : auto nodeId = *it;
594 :
595 0 : if (!contains(bucket, nodeId)) {
596 0 : newBucketIt->addMobileNode(nodeId);
597 0 : it = mobileSwap.erase(it);
598 0 : bucket->removeMobileNode(nodeId);
599 : } else {
600 0 : ++it;
601 : }
602 : }
603 :
604 264 : return true;
605 264 : }
606 :
607 : } // namespace jami
|
