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