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 : #pragma once
18 :
19 : #include "manager.h"
20 :
21 : #include <dhtnet/multiplexed_socket.h>
22 :
23 : #include <opendht/infohash.h>
24 :
25 : #include <asio.hpp>
26 : #include <asio/detail/deadline_timer_service.hpp>
27 :
28 : #include <utility>
29 : #include <vector>
30 : #include <memory>
31 : #include <list>
32 : #include <set>
33 :
34 : using NodeId = dht::PkId;
35 :
36 : namespace jami {
37 :
38 : static constexpr const std::chrono::minutes FIND_PERIOD {10};
39 :
40 : struct NodeInfo
41 : {
42 : bool isMobile_ {false};
43 : std::shared_ptr<dhtnet::ChannelSocketInterface> socket {};
44 : asio::steady_timer refresh_timer {*Manager::instance().ioContext(), FIND_PERIOD};
45 : NodeInfo() = delete;
46 2247 : NodeInfo(NodeInfo&&) noexcept = default;
47 1838 : NodeInfo(std::shared_ptr<dhtnet::ChannelSocketInterface> socket_)
48 1838 : : socket(std::move(socket_))
49 1838 : {}
50 1 : NodeInfo(bool mobile, std::shared_ptr<dhtnet::ChannelSocketInterface> socket_)
51 1 : : isMobile_(mobile)
52 1 : , socket(std::move(socket_))
53 1 : {}
54 : };
55 :
56 : class Bucket
57 : {
58 : public:
59 : static constexpr int BUCKET_MAX_SIZE = 2;
60 :
61 : Bucket() = delete;
62 : Bucket(const Bucket&) = delete;
63 : Bucket(const NodeId&);
64 :
65 : /**
66 : * Add Node socket to bucket
67 : * @param socket
68 : * @return true if node was added, false if not
69 : */
70 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket);
71 :
72 : /**
73 : * Add NodeInfo to bucket
74 : * @param nodeInfo
75 : * @return true if node was added, false if not
76 : */
77 : bool addNode(NodeInfo&& info);
78 :
79 : /**
80 : * Remove NodeId socket from bucket and insert it in known_nodes or
81 : * mobile_nodes depending on its type
82 : * @param nodeId
83 : * @return true if node was removed, false if not
84 : */
85 : bool removeNode(const NodeId& nodeId);
86 :
87 : /**
88 : * Get connected nodes from bucket
89 : * @return map of NodeId and NodeInfo
90 : */
91 5569 : const std::map<NodeId, NodeInfo>& getNodes() const { return nodes; }
92 402 : std::map<NodeId, NodeInfo>& getNodes() { return nodes; }
93 :
94 : /**
95 : * Get NodeIds from bucket
96 : * @return set of NodeIds
97 : */
98 : std::set<NodeId> getNodeIds() const;
99 :
100 : /**
101 : * Test if socket exists in nodes
102 : * @param nodeId
103 : * @return true if node exists, false if not
104 : */
105 : bool hasNode(const NodeId& nodeId) const;
106 :
107 : /**
108 : * Add NodeId to known_nodes if it doesn't exist in nodes
109 : * @param nodeId
110 : * @return true if known node was added, false if not
111 : */
112 : bool addKnownNode(const NodeId& nodeId);
113 :
114 : /**
115 : * Remove NodeId from known_nodes
116 : * @param nodeId
117 : */
118 125 : void removeKnownNode(const NodeId& nodeId) { known_nodes.erase(nodeId); }
119 :
120 : /**
121 : * Get NodeIds from known_nodes
122 : * @return set of known NodeIds
123 : */
124 2944 : const std::set<NodeId>& getKnownNodes() const { return known_nodes; }
125 :
126 : /**
127 : * Returns NodeId from known_nodes at index
128 : * @param index
129 : * @return NodeId
130 : */
131 : NodeId getKnownNode(unsigned index) const;
132 :
133 : /**
134 : * Test if NodeId exist in known_nodes
135 : * @param nodeId
136 : * @return true if known node exists, false if not
137 : */
138 14 : bool hasKnownNode(const NodeId& nodeId) const { return known_nodes.find(nodeId) != known_nodes.end(); }
139 :
140 : /**
141 : * Add NodeId to mobile_nodes if it doesn't exist in nodes
142 : * @param nodeId
143 : * @return true if mobile node was added, false if not
144 : */
145 : bool addMobileNode(const NodeId& nodeId);
146 :
147 : /**
148 : * Remove NodeId from mobile_nodes
149 : * @param nodeId
150 : */
151 30 : void removeMobileNode(const NodeId& nodeId) { mobile_nodes.erase(nodeId); }
152 :
153 : /**
154 : * Test if NodeId exist in mobile_nodes
155 : * @param nodeId
156 : * @return true if mobile node exists, false if not
157 : */
158 113 : bool hasMobileNode(const NodeId& nodeId) const { return mobile_nodes.find(nodeId) != mobile_nodes.end(); }
159 :
160 : /**
161 : * Get NodeIds from mobile_nodes
162 : * @return set of mobile NodeIds
163 : */
164 7636 : const std::set<NodeId>& getMobileNodes() const { return mobile_nodes; }
165 :
166 : /**
167 : * Add NodeId to connecting_nodes if it doesn't exist in nodes
168 : * @param nodeId
169 : * @param nodeInfo
170 : * @return true if connecting node was added, false if not
171 : */
172 : bool addConnectingNode(const NodeId& nodeId);
173 :
174 : /**
175 : * Remove NodeId from connecting_nodes
176 : * @param nodeId
177 : */
178 340 : void removeConnectingNode(const NodeId& nodeId) { connecting_nodes.erase(nodeId); }
179 :
180 : /** Get NodeIds of connecting_nodes
181 : * @return set of connecting NodeIds
182 : */
183 430 : const std::set<NodeId>& getConnectingNodes() const { return connecting_nodes; };
184 :
185 : /**
186 : * Test if NodeId exist in connecting_nodes
187 : * @param nodeId
188 : * @return true if connecting node exists, false if not
189 : */
190 25 : bool hasConnectingNode(const NodeId& nodeId) const
191 : {
192 25 : return connecting_nodes.find(nodeId) != connecting_nodes.end();
193 : }
194 :
195 5869 : bool isEmpty() const { return nodes.empty(); }
196 :
197 : /**
198 : * Indicate if bucket is full
199 : * @return true if bucket is full, false if not
200 : */
201 2208 : bool isFull() const { return nodes.size() == BUCKET_MAX_SIZE; };
202 :
203 : /**
204 : * Returns random numberNodes NodeId from known_nodes
205 : * @param numberNodes
206 : * @param rd
207 : * @return set of numberNodes random known NodeIds
208 : */
209 : std::set<NodeId> getKnownNodesRandom(unsigned numberNodes, std::mt19937_64& rd) const;
210 :
211 : /**
212 : * Returns random NodeId from known_nodes
213 : * @param rd
214 : * @return random known NodeId
215 : */
216 1 : NodeId randomId(std::mt19937_64& rd) const
217 : {
218 1 : auto node = getKnownNodesRandom(1, rd);
219 2 : return *node.begin();
220 1 : }
221 :
222 : /**
223 : * Returns socket's timer
224 : * @param socket
225 : * @return timer
226 : */
227 : asio::steady_timer& getNodeTimer(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket);
228 :
229 : /**
230 : * Shutdowns socket and removes it from nodes.
231 : * The corresponding node is moved to known_nodes or mobile_nodes
232 : * @param socket
233 : * @return true if node was shutdown, false if not found
234 : */
235 : bool shutdownNode(const NodeId& nodeId);
236 :
237 : /**
238 : * Shutdowns all sockets in nodes through shutdownNode
239 : */
240 : void shutdownAllNodes();
241 :
242 : /**
243 : * Prints bucket and bucket's number
244 : */
245 : void printBucket(unsigned number) const;
246 :
247 : /**
248 : * Change mobility of specific node, mobile or not
249 : */
250 : void changeMobility(const NodeId& nodeId, bool isMobile);
251 :
252 : /**
253 : * Returns number of nodes in bucket
254 : * @return size of nodes
255 : */
256 3059 : unsigned getNodesSize() const { return nodes.size(); }
257 :
258 : /**
259 : * Returns number of knwon_nodes in bucket
260 : * @return size of knwon_nodes
261 : */
262 2735 : unsigned getKnownNodesSize() const { return known_nodes.size(); }
263 :
264 : /**
265 : * Returns number of mobile_nodes in bucket
266 : * @return size of mobile_nodes
267 : */
268 4870 : unsigned getConnectingNodesSize() const { return connecting_nodes.size(); }
269 :
270 : /**
271 : * Returns bucket lower limit
272 : * @return NodeId lower limit
273 : */
274 32435 : NodeId getLowerLimit() const { return lowerLimit_; };
275 :
276 : /**
277 : * Set bucket's lower limit
278 : * @param nodeId
279 : */
280 : void setLowerLimit(const NodeId& nodeId) { lowerLimit_ = nodeId; }
281 :
282 : // For tests
283 :
284 : /**
285 : * Get sockets from bucket
286 : * @return set of sockets
287 : */
288 : std::set<std::shared_ptr<dhtnet::ChannelSocketInterface>> getNodeSockets() const;
289 :
290 : private:
291 : NodeId lowerLimit_;
292 : std::map<NodeId, NodeInfo> nodes;
293 : std::set<NodeId> known_nodes;
294 : std::set<NodeId> connecting_nodes;
295 : std::set<NodeId> mobile_nodes;
296 : mutable std::mutex mutex;
297 : };
298 :
299 : // ####################################################################################################
300 :
301 : class RoutingTable
302 : {
303 : public:
304 : static constexpr unsigned MOBILE_WAKE_REDUNDANCY = 2;
305 :
306 : RoutingTable();
307 :
308 : bool isEmpty() const;
309 :
310 : /**
311 : * Add socket to bucket
312 : * @param socket
313 : * @return true if socket was added, false if not
314 : */
315 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket);
316 :
317 : /**
318 : * Add socket to specific bucket
319 : * @param channel
320 : * @param bucket
321 : * @return true if socket was added to bucket, false if not
322 : */
323 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& channel, std::list<Bucket>::iterator& bucket);
324 :
325 : /**
326 : * Removes node from routing table
327 : * Adds it to known_nodes or mobile_nodes depending on mobility
328 : * @param socket
329 : * @return true if node was removed, false if not
330 : */
331 : bool removeNode(const NodeId& nodeId);
332 :
333 : /**
334 : * Check if connected node exsits in routing table
335 : * @param nodeId
336 : * @return true if node exists, false if not
337 : */
338 : bool hasNode(const NodeId& nodeId);
339 :
340 : /**
341 : * Add known node to routing table
342 : * @param nodeId
343 : * @return true if known node was added, false if not
344 : */
345 : bool addKnownNode(const NodeId& nodeId);
346 :
347 : /**
348 : * Checks if known node exists in routing table
349 : * @param nodeId
350 : * @return true if known node exists, false if not
351 : */
352 7 : bool hasKnownNode(const NodeId& nodeId) const
353 : {
354 7 : auto bucket = findBucket(nodeId);
355 14 : return bucket->hasKnownNode(nodeId);
356 : }
357 :
358 : /**
359 : * Add mobile node to routing table
360 : * @param nodeId
361 : * @return true if mobile node was added, false if not
362 : */
363 : bool addMobileNode(const NodeId& nodeId);
364 :
365 : /**
366 : * Remove mobile node to routing table
367 : * @param nodeId
368 : * @return true if mobile node was removed, false if not
369 : */
370 : void removeMobileNode(const NodeId& nodeId);
371 :
372 : /**
373 : * Check if mobile node exists in routing table
374 : * @param nodeId
375 : * @return true if mobile node exists, false if not
376 : */
377 : bool hasMobileNode(const NodeId& nodeId);
378 :
379 : /**
380 : * Add connecting node to routing table
381 : * @param nodeId
382 : * @return true if connecting node was added, false if not
383 : */
384 : bool addConnectingNode(const NodeId& nodeId);
385 :
386 : /**
387 : * Remove connecting connecting node to routing table
388 : * @param nodeId
389 : * @return true if connecting node was removed, false if not
390 : */
391 : void removeConnectingNode(const NodeId& nodeId);
392 :
393 : /**
394 : * Check if Connecting node exists in routing table
395 : * @param nodeId
396 : * @return true if connecting node exists, false if not
397 : */
398 9 : bool hasConnectingNode(const NodeId& nodeId) const
399 : {
400 9 : auto bucket = findBucket(nodeId);
401 18 : return bucket->hasConnectingNode(nodeId);
402 : }
403 :
404 : /**
405 : * Returns bucket iterator containing nodeId
406 : * @param nodeId
407 : * @return bucket iterator
408 : */
409 : std::list<Bucket>::iterator findBucket(const NodeId& nodeId);
410 :
411 : /**
412 : * Returns bucket iterator containing nodeId
413 : * @param nodeId
414 : * @return bucket iterator
415 : */
416 1782 : inline const std::list<Bucket>::const_iterator findBucket(const NodeId& nodeId) const
417 : {
418 1782 : return std::list<Bucket>::const_iterator(const_cast<RoutingTable*>(this)->findBucket(nodeId));
419 : }
420 :
421 : /**
422 : * Returns the count closest nodes to a specific nodeId
423 : * @param nodeId
424 : * @param count
425 : * @return vector of nodeIds
426 : */
427 : std::vector<NodeId> closestNodes(const NodeId& nodeId, unsigned count) const;
428 :
429 : /**
430 : * Returns number of buckets in routing table
431 : * @return size of buckets
432 : */
433 : unsigned size() const { return buckets.size(); }
434 :
435 : /**
436 : * Returns number of total nodes in routing table
437 : * @return size of nodes
438 : */
439 10 : unsigned getNodeCount() const
440 : {
441 10 : size_t count = 0;
442 44 : for (const auto& b : buckets)
443 34 : count += b.getNodesSize();
444 10 : return count;
445 : }
446 :
447 585 : unsigned getActiveNodesCount() const
448 : {
449 585 : size_t count = 0;
450 1250 : for (const auto& b : buckets)
451 665 : count += b.getNodesSize() + b.getConnectingNodesSize();
452 585 : return count;
453 : }
454 :
455 : /**
456 : * Prints routing table
457 : */
458 : void printRoutingTable() const;
459 :
460 : /**
461 : * Shutdowns a node
462 : * @param nodeId
463 : */
464 : void shutdownNode(const NodeId& nodeId);
465 :
466 : /**
467 : * Shutdowns all nodes in routing table and add them to known_nodes or mobile_nodes
468 : */
469 720 : void shutdownAllNodes()
470 : {
471 1821 : for (auto& bucket : buckets)
472 1101 : bucket.shutdownAllNodes();
473 720 : }
474 :
475 : /**
476 : * Sets id for routing table
477 : * @param node
478 : */
479 708 : void setId(const NodeId& node) { id_ = node; }
480 :
481 : /**
482 : * Returns id for routing table
483 : * @return Nodeid
484 : */
485 5 : NodeId getId() const { return id_; }
486 :
487 : /**
488 : * Returns buckets in routing table
489 : * @return list buckets
490 : */
491 1876 : std::list<Bucket>& getBuckets() { return buckets; }
492 :
493 : /**
494 : * Returns all routing table's connected nodes
495 : * @return vector of nodeIds
496 : */
497 : std::vector<NodeId> getNodes() const;
498 :
499 : /**
500 : * Returns all routing table's known nodes
501 : *@return vector of nodeIds
502 : */
503 : std::vector<NodeId> getKnownNodes() const;
504 :
505 : /**
506 : * Returns all routing table's mobile nodes
507 : * @return vector of nodeIds
508 : */
509 : std::vector<NodeId> getMobileNodes() const;
510 :
511 : /**
512 : * Returns the mobile nodes this table's owner is responsible for
513 : * waking up. The closest MOBILE_WAKE_REDUNDANCY nodes in the local
514 : * Kademlia view independently take responsibility.
515 : * @return vector of nodeIds
516 : */
517 : std::vector<NodeId> getMobileNodesToNotify() const;
518 :
519 : /**
520 : * Returns every node known to be mobile: disconnected mobile nodes
521 : * (mobile_nodes) plus connected nodes flagged as mobile.
522 : * Used to persist mobility knowledge across restarts.
523 : * @return vector of nodeIds
524 : */
525 : std::vector<NodeId> getKnownMobileNodes() const;
526 :
527 : /**
528 : * Returns all routing table's connecting nodes
529 : * @return vector of nodeIds
530 : */
531 : std::vector<NodeId> getConnectingNodes() const;
532 :
533 : /**
534 : * Returns mobile nodes corresponding to the swarm's id
535 : * @return vector of nodeIds
536 : */
537 : std::vector<NodeId> getBucketMobileNodes() const;
538 :
539 : std::vector<NodeId> getConnectedNodes() const;
540 :
541 : /**
542 : * Test if connected nodeId is in specific bucket
543 : * @param it
544 : * @param nodeId
545 : * @return true if nodeId is in bucket, false if not
546 : */
547 : bool contains(const std::list<Bucket>::iterator& it, const NodeId& nodeId) const;
548 :
549 : /**
550 : * Return every node from each bucket
551 : */
552 : std::vector<NodeId> getAllNodes() const;
553 :
554 : /**
555 : * Delete node from every table in bucket
556 : */
557 : void deleteNode(const NodeId& nodeId);
558 :
559 : struct NodeStats
560 : {
561 : std::string id;
562 : std::string status;
563 : std::string remoteAddress;
564 : std::chrono::system_clock::time_point connectionTime;
565 : bool isMobile;
566 : };
567 : std::vector<NodeStats> getRoutingTableStats() const;
568 :
569 : private:
570 : RoutingTable(const RoutingTable&) = delete;
571 : RoutingTable& operator=(const RoutingTable&) = delete;
572 :
573 : /**
574 : * Returns middle of routing table
575 : * @param it
576 : * @return NodeId
577 : */
578 : NodeId middle(std::list<Bucket>::iterator& it) const;
579 :
580 : /**
581 : * Returns depth of routing table
582 : * @param bucket
583 : * @return depth
584 : */
585 : unsigned depth(std::list<Bucket>::iterator& bucket) const;
586 :
587 : /**
588 : * Splits bucket
589 : * @param bucket
590 : * @return true if bucket was split, false if not
591 : */
592 : bool split(std::list<Bucket>::iterator& bucket);
593 :
594 : NodeId id_;
595 :
596 : std::list<Bucket> buckets;
597 :
598 : mutable std::mutex mutex_;
599 : };
600 : }; // namespace jami
|
