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 : constexpr const std::chrono::minutes FIND_PERIOD {10};
31 : using namespace std::placeholders;
32 :
33 : namespace jami {
34 :
35 : using namespace dht;
36 :
37 795 : Bucket::Bucket(const NodeId& id)
38 795 : : lowerLimit_(id)
39 795 : {}
40 :
41 : bool
42 1152 : Bucket::addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket)
43 : {
44 1152 : return addNode(NodeInfo(socket));
45 : }
46 :
47 : bool
48 1483 : Bucket::addNode(NodeInfo&& info)
49 : {
50 1483 : auto nodeId = info.socket->deviceId();
51 1483 : if (nodes.try_emplace(nodeId, std::move(info)).second) {
52 1482 : connecting_nodes.erase(nodeId);
53 1482 : known_nodes.erase(nodeId);
54 1482 : mobile_nodes.erase(nodeId);
55 1482 : return true;
56 : }
57 1 : return false;
58 : }
59 :
60 : bool
61 1155 : Bucket::removeNode(const NodeId& nodeId)
62 : {
63 1155 : auto node = nodes.find(nodeId);
64 1155 : auto isMobile = node->second.isMobile_;
65 1155 : if (node == nodes.end())
66 3 : return false;
67 1152 : nodes.erase(nodeId);
68 1152 : if (isMobile) {
69 98 : addMobileNode(nodeId);
70 : } else {
71 1054 : addKnownNode(nodeId);
72 : }
73 :
74 1152 : return true;
75 : }
76 :
77 : std::set<NodeId>
78 10194 : Bucket::getNodeIds() const
79 : {
80 10194 : std::set<NodeId> nodesId;
81 28766 : for (auto const& key : nodes)
82 18572 : nodesId.insert(key.first);
83 10194 : return nodesId;
84 0 : }
85 :
86 : bool
87 6716 : Bucket::hasNode(const NodeId& nodeId) const
88 : {
89 6716 : return nodes.find(nodeId) != nodes.end();
90 : }
91 :
92 : bool
93 3505 : Bucket::addKnownNode(const NodeId& nodeId)
94 : {
95 3505 : if (!hasNode(nodeId)) {
96 2718 : if (known_nodes.emplace(nodeId).second) {
97 2412 : return true;
98 : }
99 : }
100 1093 : return false;
101 : }
102 :
103 : NodeId
104 203 : Bucket::getKnownNode(unsigned index) const
105 : {
106 203 : if (index > known_nodes.size()) {
107 1 : throw std::out_of_range("End of table for get known Node Id " + std::to_string(index));
108 : }
109 202 : auto it = known_nodes.begin();
110 202 : std::advance(it, index);
111 :
112 202 : return *it;
113 : }
114 :
115 : bool
116 112 : Bucket::addMobileNode(const NodeId& nodeId)
117 : {
118 112 : if (!hasNode(nodeId)) {
119 111 : if (mobile_nodes.emplace(nodeId).second) {
120 111 : known_nodes.erase(nodeId);
121 111 : return true;
122 : }
123 : }
124 1 : return false;
125 : }
126 :
127 : bool
128 1021 : Bucket::addConnectingNode(const NodeId& nodeId)
129 : {
130 1021 : if (!hasNode(nodeId)) {
131 1021 : if (connecting_nodes.emplace(nodeId).second) {
132 959 : known_nodes.erase(nodeId);
133 959 : mobile_nodes.erase(nodeId);
134 959 : return true;
135 : }
136 : }
137 62 : return false;
138 : }
139 :
140 : std::set<NodeId>
141 1220 : Bucket::getKnownNodesRandom(unsigned numberNodes, std::mt19937_64& rd) const
142 : {
143 1220 : std::set<NodeId> nodesToReturn;
144 :
145 1220 : if (getKnownNodesSize() <= numberNodes)
146 1066 : return getKnownNodes();
147 :
148 154 : std::uniform_int_distribution<unsigned> distrib(0, getKnownNodesSize() - 1);
149 :
150 356 : while (nodesToReturn.size() < numberNodes) {
151 202 : nodesToReturn.emplace(getKnownNode(distrib(rd)));
152 : }
153 :
154 154 : return nodesToReturn;
155 1220 : }
156 :
157 : asio::steady_timer&
158 0 : Bucket::getNodeTimer(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket)
159 : {
160 0 : auto node = nodes.find(socket->deviceId());
161 0 : if (node == nodes.end()) {
162 0 : throw std::range_error("Unable to find timer " + socket->deviceId().toString());
163 : }
164 0 : return node->second.refresh_timer;
165 : }
166 :
167 : bool
168 13 : Bucket::shutdownNode(const NodeId& nodeId)
169 : {
170 13 : auto node = nodes.find(nodeId);
171 :
172 13 : if (node != nodes.end()) {
173 11 : auto socket = node->second.socket;
174 11 : auto node = socket->deviceId();
175 11 : socket->shutdown();
176 11 : removeNode(node);
177 11 : return true;
178 11 : }
179 2 : return false;
180 : }
181 :
182 : void
183 818 : Bucket::shutdownAllNodes()
184 : {
185 1562 : while (not nodes.empty()) {
186 744 : auto it = nodes.begin();
187 744 : it->second.socket->shutdown();
188 744 : auto nodeId = it->first;
189 744 : removeNode(nodeId);
190 : }
191 818 : }
192 :
193 : void
194 0 : Bucket::printBucket(unsigned number) const
195 : {
196 0 : JAMI_ERROR("BUCKET Number: {:d}", number);
197 :
198 0 : unsigned nodeNum = 1;
199 0 : for (auto it = nodes.begin(); it != nodes.end(); ++it) {
200 0 : JAMI_DEBUG("Node {:s} Id: {:s} isMobile: {:s}", std::to_string(nodeNum), it->first.toString(), std::to_string(it->second.isMobile_));
201 0 : nodeNum++;
202 : }
203 0 : JAMI_ERROR("Mobile Nodes");
204 0 : nodeNum = 0;
205 0 : for (auto it = mobile_nodes.begin(); it != mobile_nodes.end(); ++it) {
206 0 : JAMI_DEBUG("Node {:s} Id: {:s}", std::to_string(nodeNum), (*it).toString());
207 0 : nodeNum++;
208 : }
209 :
210 0 : JAMI_ERROR("Known Nodes");
211 0 : nodeNum = 0;
212 0 : for (auto it = known_nodes.begin(); it != known_nodes.end(); ++it) {
213 0 : JAMI_DEBUG("Node {:s} Id: {:s}", std::to_string(nodeNum), (*it).toString());
214 0 : nodeNum++;
215 : }
216 0 : JAMI_ERROR("Connecting_nodes");
217 0 : nodeNum = 0;
218 0 : for (auto it = connecting_nodes.begin(); it != connecting_nodes.end(); ++it) {
219 0 : JAMI_DEBUG("Node {:s} Id: {:s}", std::to_string(nodeNum), (*it).toString());
220 0 : nodeNum++;
221 : }
222 0 : };
223 :
224 : void
225 194 : Bucket::changeMobility(const NodeId& nodeId, bool isMobile)
226 : {
227 194 : auto itn = nodes.find(nodeId);
228 194 : if (itn != nodes.end()) {
229 194 : itn->second.isMobile_ = isMobile;
230 : }
231 194 : }
232 :
233 : // For tests
234 :
235 : std::set<std::shared_ptr<dhtnet::ChannelSocketInterface>>
236 1 : Bucket::getNodeSockets() const
237 : {
238 1 : std::set<std::shared_ptr<dhtnet::ChannelSocketInterface>> sockets;
239 3 : for (auto const& info : nodes)
240 2 : sockets.insert(info.second.socket);
241 1 : return sockets;
242 0 : }
243 :
244 : // ####################################################################################################
245 :
246 496 : RoutingTable::RoutingTable()
247 : {
248 496 : buckets.emplace_back(NodeId::zero());
249 496 : }
250 :
251 : bool
252 10 : RoutingTable::addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket)
253 : {
254 10 : auto bucket = findBucket(socket->deviceId());
255 20 : return addNode(socket, bucket);
256 : }
257 :
258 : bool
259 1546 : RoutingTable::addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& channel,
260 : std::list<Bucket>::iterator& bucket)
261 : {
262 1546 : NodeId nodeId = channel->deviceId();
263 :
264 1546 : if (bucket->hasNode(nodeId) || id_ == nodeId) {
265 426 : return false;
266 : }
267 :
268 1417 : while (bucket->isFull()) {
269 405 : if (contains(bucket, id_)) {
270 297 : split(bucket);
271 297 : bucket = findBucket(nodeId);
272 :
273 : } else {
274 108 : return bucket->addNode(std::move(channel));
275 : }
276 : }
277 1012 : return bucket->addNode(std::move(channel));
278 : }
279 :
280 : bool
281 397 : RoutingTable::removeNode(const NodeId& nodeId)
282 : {
283 397 : return findBucket(nodeId)->removeNode(nodeId);
284 : }
285 :
286 : bool
287 524 : RoutingTable::hasNode(const NodeId& nodeId)
288 : {
289 524 : return findBucket(nodeId)->hasNode(nodeId);
290 : }
291 :
292 : bool
293 3087 : RoutingTable::addKnownNode(const NodeId& nodeId)
294 : {
295 3087 : if (id_ == nodeId)
296 1020 : return false;
297 :
298 2067 : auto bucket = findBucket(nodeId);
299 2067 : if (bucket == buckets.end())
300 0 : return false;
301 :
302 2067 : return bucket->addKnownNode(nodeId);
303 : }
304 :
305 : bool
306 15 : RoutingTable::addMobileNode(const NodeId& nodeId)
307 : {
308 15 : if (id_ == nodeId)
309 1 : return false;
310 :
311 14 : auto bucket = findBucket(nodeId);
312 :
313 14 : if (bucket == buckets.end())
314 0 : return 0;
315 :
316 14 : bucket->addMobileNode(nodeId);
317 14 : return 1;
318 : }
319 :
320 : void
321 2 : RoutingTable::removeMobileNode(const NodeId& nodeId)
322 : {
323 2 : return findBucket(nodeId)->removeMobileNode(nodeId);
324 : }
325 :
326 : bool
327 7 : RoutingTable::hasMobileNode(const NodeId& nodeId)
328 : {
329 7 : return findBucket(nodeId)->hasMobileNode(nodeId);
330 : };
331 :
332 : bool
333 891 : RoutingTable::addConnectingNode(const NodeId& nodeId)
334 : {
335 891 : if (id_ == nodeId)
336 1 : return false;
337 :
338 890 : auto bucket = findBucket(nodeId);
339 :
340 890 : if (bucket == buckets.end())
341 0 : return 0;
342 :
343 890 : bucket->addConnectingNode(nodeId);
344 890 : return 1;
345 : }
346 :
347 : void
348 0 : RoutingTable::removeConnectingNode(const NodeId& nodeId)
349 : {
350 0 : findBucket(nodeId)->removeConnectingNode(nodeId);
351 0 : }
352 :
353 : std::list<Bucket>::iterator
354 10917 : RoutingTable::findBucket(const NodeId& nodeId)
355 : {
356 10917 : if (buckets.empty())
357 0 : throw std::runtime_error("No bucket");
358 :
359 10917 : auto b = buckets.begin();
360 :
361 : while (true) {
362 18740 : auto next = std::next(b);
363 18740 : if (next == buckets.end())
364 10917 : return b;
365 11829 : if (std::memcmp(nodeId.data(), next->getLowerLimit().data(), nodeId.size()) < 0)
366 4006 : return b;
367 7823 : b = next;
368 7823 : }
369 : }
370 :
371 : std::vector<NodeId>
372 1034 : RoutingTable::closestNodes(const NodeId& nodeId, unsigned count)
373 : {
374 1034 : std::vector<NodeId> closestNodes;
375 1034 : auto bucket = findBucket(nodeId);
376 2504 : auto sortedBucketInsert = [&](const std::list<Bucket>::iterator& b) {
377 2504 : auto nodes = b->getNodeIds();
378 7265 : for (auto n : nodes) {
379 4761 : if (n != nodeId) {
380 3730 : auto here = std::find_if(closestNodes.begin(),
381 : closestNodes.end(),
382 10052 : [&nodeId, &n](NodeId& NodeId) {
383 10052 : return nodeId.xorCmp(n, NodeId) < 0;
384 : });
385 :
386 3730 : closestNodes.insert(here, n);
387 : }
388 : }
389 2504 : };
390 :
391 1034 : auto itn = bucket;
392 1034 : auto itp = (bucket == buckets.begin()) ? buckets.end() : std::prev(bucket);
393 3029 : while (itn != buckets.end() || itp != buckets.end()) {
394 1995 : if (itn != buckets.end()) {
395 1774 : sortedBucketInsert(itn);
396 1774 : itn = std::next(itn);
397 : }
398 1995 : if (itp != buckets.end()) {
399 730 : sortedBucketInsert(itp);
400 730 : itp = (itp == buckets.begin()) ? buckets.end() : std::prev(itp);
401 : }
402 : }
403 :
404 1034 : if (closestNodes.size() > count) {
405 543 : closestNodes.resize(count);
406 : }
407 :
408 2068 : return closestNodes;
409 0 : }
410 :
411 : void
412 0 : RoutingTable::printRoutingTable() const
413 : {
414 0 : int counter = 1;
415 0 : JAMI_DEBUG("SWARM: {:s} ", id_.toString());
416 0 : for (auto it = buckets.begin(); it != buckets.end(); ++it) {
417 0 : it->printBucket(counter);
418 0 : counter++;
419 : }
420 0 : JAMI_DEBUG("_____________________________________________________________________________");
421 0 : }
422 :
423 : void
424 2 : RoutingTable::shutdownNode(const NodeId& nodeId)
425 : {
426 2 : findBucket(nodeId)->shutdownNode(nodeId);
427 2 : }
428 :
429 : std::vector<NodeId>
430 3742 : RoutingTable::getNodes() const
431 : {
432 3742 : std::lock_guard lock(mutex_);
433 3742 : std::vector<NodeId> ret;
434 11409 : for (const auto& b : buckets) {
435 7667 : const auto& nodes = b.getNodeIds();
436 7667 : ret.insert(ret.end(), nodes.begin(), nodes.end());
437 7667 : }
438 7484 : return ret;
439 3742 : }
440 :
441 : std::vector<NodeId>
442 1 : RoutingTable::getKnownNodes() const
443 : {
444 1 : std::vector<NodeId> ret;
445 2 : for (const auto& b : buckets) {
446 1 : const auto& nodes = b.getKnownNodes();
447 1 : ret.insert(ret.end(), nodes.begin(), nodes.end());
448 : }
449 1 : return ret;
450 0 : }
451 :
452 : std::vector<NodeId>
453 1579 : RoutingTable::getMobileNodes() const
454 : {
455 1579 : std::vector<NodeId> ret;
456 4982 : for (const auto& b : buckets) {
457 3403 : const auto& nodes = b.getMobileNodes();
458 3403 : ret.insert(ret.end(), nodes.begin(), nodes.end());
459 : }
460 1579 : return ret;
461 0 : }
462 :
463 : std::vector<NodeId>
464 1 : RoutingTable::getConnectingNodes() const
465 : {
466 1 : std::vector<NodeId> ret;
467 2 : for (const auto& b : buckets) {
468 1 : const auto& nodes = b.getConnectingNodes();
469 1 : ret.insert(ret.end(), nodes.begin(), nodes.end());
470 : }
471 1 : return ret;
472 0 : }
473 :
474 : std::vector<NodeId>
475 0 : RoutingTable::getBucketMobileNodes() const
476 : {
477 0 : std::vector<NodeId> ret;
478 0 : auto bucket = findBucket(id_);
479 0 : const auto& nodes = bucket->getMobileNodes();
480 0 : ret.insert(ret.end(), nodes.begin(), nodes.end());
481 :
482 0 : return ret;
483 0 : }
484 :
485 : bool
486 4014 : RoutingTable::contains(const std::list<Bucket>::iterator& bucket, const NodeId& nodeId) const
487 : {
488 4014 : return NodeId::cmp(bucket->getLowerLimit(), nodeId) <= 0
489 6599 : && (std::next(bucket) == buckets.end()
490 6599 : || NodeId::cmp(nodeId, std::next(bucket)->getLowerLimit()) < 0);
491 : }
492 :
493 : std::vector<NodeId>
494 16 : RoutingTable::getAllNodes() const
495 : {
496 16 : std::vector<NodeId> ret;
497 32 : for (const auto& b : buckets) {
498 16 : const auto& nodes = b.getNodeIds();
499 16 : const auto& knownNodes = b.getKnownNodes();
500 16 : const auto& mobileNodes = b.getMobileNodes();
501 16 : const auto& connectingNodes = b.getConnectingNodes();
502 16 : ret.reserve(nodes.size() + knownNodes.size() + mobileNodes.size() + connectingNodes.size());
503 16 : ret.insert(ret.end(), nodes.begin(), nodes.end());
504 16 : ret.insert(ret.end(), knownNodes.begin(), knownNodes.end());
505 16 : ret.insert(ret.end(), mobileNodes.begin(), mobileNodes.end());
506 16 : ret.insert(ret.end(), connectingNodes.begin(), connectingNodes.end());
507 16 : }
508 16 : return ret;
509 0 : }
510 :
511 : void
512 10 : RoutingTable::deleteNode(const NodeId& nodeId)
513 : {
514 10 : auto bucket = findBucket(nodeId);
515 10 : bucket->shutdownNode(nodeId);
516 10 : bucket->removeConnectingNode(nodeId);
517 10 : bucket->removeKnownNode(nodeId);
518 10 : bucket->removeMobileNode(nodeId);
519 10 : }
520 :
521 : NodeId
522 297 : RoutingTable::middle(std::list<Bucket>::iterator& it) const
523 : {
524 297 : unsigned bit = depth(it);
525 297 : if (bit >= 8 * HASH_LEN)
526 0 : throw std::out_of_range("End of table");
527 :
528 297 : NodeId id = it->getLowerLimit();
529 297 : id.setBit(bit, true);
530 297 : return id;
531 : }
532 :
533 : unsigned
534 297 : RoutingTable::depth(std::list<Bucket>::iterator& bucket) const
535 : {
536 297 : int bit1 = bucket->getLowerLimit().lowbit();
537 297 : int bit2 = std::next(bucket) != buckets.end() ? std::next(bucket)->getLowerLimit().lowbit()
538 297 : : -1;
539 297 : return std::max(bit1, bit2) + 1;
540 : }
541 :
542 : bool
543 297 : RoutingTable::split(std::list<Bucket>::iterator& bucket)
544 : {
545 297 : NodeId id = middle(bucket);
546 297 : auto newBucketIt = buckets.emplace(std::next(bucket), id);
547 : // Re-assign nodes
548 297 : auto& nodeSwap = bucket->getNodes();
549 :
550 891 : for (auto it = nodeSwap.begin(); it != nodeSwap.end();) {
551 594 : auto& node = *it;
552 :
553 594 : auto nodeId = it->first;
554 :
555 594 : if (!contains(bucket, nodeId)) {
556 330 : newBucketIt->addNode(std::move(node.second));
557 330 : it = nodeSwap.erase(it);
558 : } else {
559 264 : ++it;
560 : }
561 : }
562 :
563 297 : auto connectingSwap = bucket->getConnectingNodes();
564 548 : for (auto it = connectingSwap.begin(); it != connectingSwap.end();) {
565 251 : auto nodeId = *it;
566 :
567 251 : if (!contains(bucket, nodeId)) {
568 129 : newBucketIt->addConnectingNode(nodeId);
569 129 : it = connectingSwap.erase(it);
570 129 : bucket->removeConnectingNode(nodeId);
571 : } else {
572 122 : ++it;
573 : }
574 : }
575 :
576 297 : auto knownSwap = bucket->getKnownNodes();
577 797 : for (auto it = knownSwap.begin(); it != knownSwap.end();) {
578 500 : auto nodeId = *it;
579 :
580 500 : if (!contains(bucket, nodeId)) {
581 307 : newBucketIt->addKnownNode(nodeId);
582 307 : it = knownSwap.erase(it);
583 307 : bucket->removeKnownNode(nodeId);
584 : } else {
585 193 : ++it;
586 : }
587 : }
588 :
589 297 : auto mobileSwap = bucket->getMobileNodes();
590 297 : for (auto it = mobileSwap.begin(); it != mobileSwap.end();) {
591 0 : auto nodeId = *it;
592 :
593 0 : if (!contains(bucket, nodeId)) {
594 0 : newBucketIt->addMobileNode(nodeId);
595 0 : it = mobileSwap.erase(it);
596 0 : bucket->removeMobileNode(nodeId);
597 : } else {
598 0 : ++it;
599 : }
600 : }
601 :
602 297 : return true;
603 297 : }
604 :
605 : } // namespace jami
|
