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