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 : #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 <vector>
29 : #include <memory>
30 : #include <list>
31 : #include <set>
32 : #include <algorithm>
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 954 : NodeInfo(NodeInfo&&) = default;
47 832 : NodeInfo(std::shared_ptr<dhtnet::ChannelSocketInterface> socket_)
48 832 : : socket(socket_)
49 831 : {}
50 1 : NodeInfo(bool mobile, std::shared_ptr<dhtnet::ChannelSocketInterface> socket_)
51 1 : : isMobile_(mobile)
52 1 : , socket(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 3477 : const std::map<NodeId, NodeInfo>& getNodes() const { return nodes; }
92 135 : 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 246 : 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 864 : 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 303 : 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 13 : 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 9 : bool hasMobileNode(const NodeId& nodeId) { return mobile_nodes.find(nodeId) != mobile_nodes.end(); }
159 :
160 : /**
161 : * Get NodeIds from mobile_nodes
162 : * @return set of mobile NodeIds
163 : */
164 4338 : 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 128 : void removeConnectingNode(const NodeId& nodeId) { connecting_nodes.erase(nodeId); }
179 :
180 : /** Get NodeIds of connecting_nodes
181 : * @return set of connecting NodeIds
182 : */
183 154 : 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 18 : bool hasConnectingNode(const NodeId& nodeId) const
191 : {
192 18 : return connecting_nodes.find(nodeId) != connecting_nodes.end();
193 : }
194 :
195 3460 : 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 936 : 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 756 : unsigned getNodesSize() const { return nodes.size(); }
257 :
258 : /**
259 : * Returns number of knwon_nodes in bucket
260 : * @return size of knwon_nodes
261 : */
262 929 : 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 1516 : unsigned getConnectingNodesSize() const { return connecting_nodes.size(); }
269 :
270 : /**
271 : * Returns bucket lower limit
272 : * @return NodeId lower limit
273 : */
274 10453 : 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 : RoutingTable();
305 :
306 : bool isEmpty() const;
307 :
308 : /**
309 : * Add socket to bucket
310 : * @param socket
311 : * @return true if socket was added, false if not
312 : */
313 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket);
314 :
315 : /**
316 : * Add socket to specific bucket
317 : * @param channel
318 : * @param bucket
319 : * @return true if socket was added to bucket, false if not
320 : */
321 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& channel, std::list<Bucket>::iterator& bucket);
322 :
323 : /**
324 : * Removes node from routing table
325 : * Adds it to known_nodes or mobile_nodes depending on mobility
326 : * @param socket
327 : * @return true if node was removed, false if not
328 : */
329 : bool removeNode(const NodeId& nodeId);
330 :
331 : /**
332 : * Check if connected node exsits in routing table
333 : * @param nodeId
334 : * @return true if node exists, false if not
335 : */
336 : bool hasNode(const NodeId& nodeId);
337 :
338 : /**
339 : * Add known node to routing table
340 : * @param nodeId
341 : * @return true if known node was added, false if not
342 : */
343 : bool addKnownNode(const NodeId& nodeId);
344 :
345 : /**
346 : * Checks if known node exists in routing table
347 : * @param nodeId
348 : * @return true if known node exists, false if not
349 : */
350 296 : bool hasKnownNode(const NodeId& nodeId) const
351 : {
352 296 : auto bucket = findBucket(nodeId);
353 592 : return bucket->hasKnownNode(nodeId);
354 : }
355 :
356 : /**
357 : * Add mobile node to routing table
358 : * @param nodeId
359 : * @return true if mobile node was added, false if not
360 : */
361 : bool addMobileNode(const NodeId& nodeId);
362 :
363 : /**
364 : * Remove mobile node to routing table
365 : * @param nodeId
366 : * @return true if mobile node was removed, false if not
367 : */
368 : void removeMobileNode(const NodeId& nodeId);
369 :
370 : /**
371 : * Check if mobile node exists in routing table
372 : * @param nodeId
373 : * @return true if mobile node exists, false if not
374 : */
375 : bool hasMobileNode(const NodeId& nodeId);
376 :
377 : /**
378 : * Add connecting node to routing table
379 : * @param nodeId
380 : * @return true if connecting node was added, false if not
381 : */
382 : bool addConnectingNode(const NodeId& nodeId);
383 :
384 : /**
385 : * Remove connecting connecting node to routing table
386 : * @param nodeId
387 : * @return true if connecting node was removed, false if not
388 : */
389 : void removeConnectingNode(const NodeId& nodeId);
390 :
391 : /**
392 : * Check if Connecting node exists in routing table
393 : * @param nodeId
394 : * @return true if connecting node exists, false if not
395 : */
396 6 : bool hasConnectingNode(const NodeId& nodeId) const
397 : {
398 6 : auto bucket = findBucket(nodeId);
399 12 : return bucket->hasConnectingNode(nodeId);
400 : }
401 :
402 : /**
403 : * Returns bucket iterator containing nodeId
404 : * @param nodeId
405 : * @return bucket iterator
406 : */
407 : std::list<Bucket>::iterator findBucket(const NodeId& nodeId);
408 :
409 : /**
410 : * Returns bucket iterator containing nodeId
411 : * @param nodeId
412 : * @return bucket iterator
413 : */
414 302 : inline const std::list<Bucket>::const_iterator findBucket(const NodeId& nodeId) const
415 : {
416 302 : return std::list<Bucket>::const_iterator(const_cast<RoutingTable*>(this)->findBucket(nodeId));
417 : }
418 :
419 : /**
420 : * Returns the count closest nodes to a specific nodeId
421 : * @param nodeId
422 : * @param count
423 : * @return vector of nodeIds
424 : */
425 : std::vector<NodeId> closestNodes(const NodeId& nodeId, unsigned count);
426 :
427 : /**
428 : * Returns number of buckets in routing table
429 : * @return size of buckets
430 : */
431 : unsigned size() const { return buckets.size(); }
432 :
433 : /**
434 : * Returns number of total nodes in routing table
435 : * @return size of nodes
436 : */
437 10 : unsigned getNodeCount() const
438 : {
439 10 : size_t count = 0;
440 44 : for (const auto& b : buckets)
441 34 : count += b.getNodesSize();
442 10 : return count;
443 : }
444 :
445 : /**
446 : * Prints routing table
447 : */
448 : void printRoutingTable() const;
449 :
450 : /**
451 : * Shutdowns a node
452 : * @param nodeId
453 : */
454 : void shutdownNode(const NodeId& nodeId);
455 :
456 : /**
457 : * Shutdowns all nodes in routing table and add them to known_nodes or mobile_nodes
458 : */
459 620 : void shutdownAllNodes()
460 : {
461 1375 : for (auto& bucket : buckets)
462 755 : bucket.shutdownAllNodes();
463 620 : }
464 :
465 : /**
466 : * Sets id for routing table
467 : * @param node
468 : */
469 583 : void setId(const NodeId& node) { id_ = node; }
470 :
471 : /**
472 : * Returns id for routing table
473 : * @return Nodeid
474 : */
475 : NodeId getId() const { return id_; }
476 :
477 : /**
478 : * Returns buckets in routing table
479 : * @return list buckets
480 : */
481 757 : std::list<Bucket>& getBuckets() { return buckets; }
482 :
483 : /**
484 : * Returns all routing table's connected nodes
485 : * @return vector of nodeIds
486 : */
487 : std::vector<NodeId> getNodes() const;
488 :
489 : /**
490 : * Returns all routing table's known nodes
491 : *@return vector of nodeIds
492 : */
493 : std::vector<NodeId> getKnownNodes() const;
494 :
495 : /**
496 : * Returns all routing table's mobile nodes
497 : * @return vector of nodeIds
498 : */
499 : std::vector<NodeId> getMobileNodes() const;
500 :
501 : /**
502 : * Returns all routing table's connecting nodes
503 : * @return vector of nodeIds
504 : */
505 : std::vector<NodeId> getConnectingNodes() const;
506 :
507 : /**
508 : * Returns mobile nodes corresponding to the swarm's id
509 : * @return vector of nodeIds
510 : */
511 : std::vector<NodeId> getBucketMobileNodes() const;
512 :
513 : std::vector<NodeId> getConnectedNodes() const;
514 :
515 : /**
516 : * Test if connected nodeId is in specific bucket
517 : * @param it
518 : * @param nodeId
519 : * @return true if nodeId is in bucket, false if not
520 : */
521 : bool contains(const std::list<Bucket>::iterator& it, const NodeId& nodeId) const;
522 :
523 : /**
524 : * Return every node from each bucket
525 : */
526 : std::vector<NodeId> getAllNodes() const;
527 :
528 : /**
529 : * Delete node from every table in bucket
530 : */
531 : void deleteNode(const NodeId& nodeId);
532 :
533 : private:
534 : RoutingTable(const RoutingTable&) = delete;
535 : RoutingTable& operator=(const RoutingTable&) = delete;
536 :
537 : /**
538 : * Returns middle of routing table
539 : * @param it
540 : * @return NodeId
541 : */
542 : NodeId middle(std::list<Bucket>::iterator& it) const;
543 :
544 : /**
545 : * Returns depth of routing table
546 : * @param bucket
547 : * @return depth
548 : */
549 : unsigned depth(std::list<Bucket>::iterator& bucket) const;
550 :
551 : /**
552 : * Splits bucket
553 : * @param bucket
554 : * @return true if bucket was split, false if not
555 : */
556 : bool split(std::list<Bucket>::iterator& bucket);
557 :
558 : NodeId id_;
559 :
560 : std::list<Bucket> buckets;
561 :
562 : mutable std::mutex mutex_;
563 : };
564 : }; // namespace jami
|
