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 : #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 1820 : NodeInfo(NodeInfo&&) = default;
47 1544 : NodeInfo(std::shared_ptr<dhtnet::ChannelSocketInterface> socket_)
48 1544 : : socket(socket_)
49 1547 : {}
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 : {
59 : public:
60 : static constexpr int BUCKET_MAX_SIZE = 2;
61 :
62 : Bucket() = delete;
63 : Bucket(const Bucket&) = delete;
64 : Bucket(const NodeId&);
65 :
66 : /**
67 : * Add Node socket to bucket
68 : * @param socket
69 : * @return true if node was added, false if not
70 : */
71 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket);
72 :
73 : /**
74 : * Add NodeInfo to bucket
75 : * @param nodeInfo
76 : * @return true if node was added, false if not
77 : */
78 : bool addNode(NodeInfo&& info);
79 :
80 : /**
81 : * Remove NodeId socket from bucket and insert it in known_nodes or
82 : * mobile_nodes depending on its type
83 : * @param nodeId
84 : * @return true if node was removed, false if not
85 : */
86 : bool removeNode(const NodeId& nodeId);
87 :
88 : /**
89 : * Get connected nodes from bucket
90 : * @return map of NodeId and NodeInfo
91 : */
92 350 : 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 374 : 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 1660 : 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 299 : bool hasKnownNode(const NodeId& nodeId) const
139 : {
140 299 : return known_nodes.find(nodeId) != known_nodes.end();
141 : }
142 :
143 : /**
144 : * Add NodeId to mobile_nodes if it doesn't exist in nodes
145 : * @param nodeId
146 : * @return true if mobile node was added, false if not
147 : */
148 : bool addMobileNode(const NodeId& nodeId);
149 :
150 : /**
151 : * Remove NodeId from mobile_nodes
152 : * @param nodeId
153 : */
154 14 : void removeMobileNode(const NodeId& nodeId) { mobile_nodes.erase(nodeId); }
155 :
156 : /**
157 : * Test if NodeId exist in mobile_nodes
158 : * @param nodeId
159 : * @return true if mobile node exists, false if not
160 : */
161 13 : bool hasMobileNode(const NodeId& nodeId)
162 : {
163 13 : return mobile_nodes.find(nodeId) != mobile_nodes.end();
164 : }
165 :
166 : /**
167 : * Get NodeIds from mobile_nodes
168 : * @return set of mobile NodeIds
169 : */
170 7013 : const std::set<NodeId>& getMobileNodes() const { return mobile_nodes; }
171 :
172 : /**
173 : * Add NodeId to connecting_nodes if it doesn't exist in nodes
174 : * @param nodeId
175 : * @param nodeInfo
176 : * @return true if connecting node was added, false if not
177 : */
178 : bool addConnectingNode(const NodeId& nodeId);
179 :
180 : /**
181 : * Remove NodeId from connecting_nodes
182 : * @param nodeId
183 : */
184 234 : void removeConnectingNode(const NodeId& nodeId) { connecting_nodes.erase(nodeId); }
185 :
186 : /** Get NodeIds of connecting_nodes
187 : * @return set of connecting NodeIds
188 : */
189 370 : const std::set<NodeId>& getConnectingNodes() const { return connecting_nodes; };
190 :
191 : /**
192 : * Test if NodeId exist in connecting_nodes
193 : * @param nodeId
194 : * @return true if connecting node exists, false if not
195 : */
196 18 : bool hasConnectingNode(const NodeId& nodeId) const
197 : {
198 18 : return connecting_nodes.find(nodeId) != connecting_nodes.end();
199 : }
200 :
201 2151 : bool isEmpty() const { return nodes.empty(); }
202 :
203 : /**
204 : * Indicate if bucket is full
205 : * @return true if bucket is full, false if not
206 : */
207 1864 : bool isFull() const { return nodes.size() == BUCKET_MAX_SIZE; };
208 :
209 : /**
210 : * Returns random numberNodes NodeId from known_nodes
211 : * @param numberNodes
212 : * @param rd
213 : * @return set of numberNodes random known NodeIds
214 : */
215 : std::set<NodeId> getKnownNodesRandom(unsigned numberNodes, std::mt19937_64& rd) const;
216 :
217 : /**
218 : * Returns random NodeId from known_nodes
219 : * @param rd
220 : * @return random known NodeId
221 : */
222 1 : NodeId randomId(std::mt19937_64& rd) const
223 : {
224 1 : auto node = getKnownNodesRandom(1, rd);
225 2 : return *node.begin();
226 1 : }
227 :
228 : /**
229 : * Returns socket's timer
230 : * @param socket
231 : * @return timer
232 : */
233 : asio::steady_timer& getNodeTimer(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket);
234 :
235 : /**
236 : * Shutdowns socket and removes it from nodes.
237 : * The corresponding node is moved to known_nodes or mobile_nodes
238 : * @param socket
239 : * @return true if node was shutdown, false if not found
240 : */
241 : bool shutdownNode(const NodeId& nodeId);
242 :
243 : /**
244 : * Shutdowns all sockets in nodes through shutdownNode
245 : */
246 : void shutdownAllNodes();
247 :
248 : /**
249 : * Prints bucket and bucket's number
250 : */
251 : void printBucket(unsigned number) const;
252 :
253 : /**
254 : * Change mobility of specific node, mobile or not
255 : */
256 : void changeMobility(const NodeId& nodeId, bool isMobile);
257 :
258 : /**
259 : * Returns number of nodes in bucket
260 : * @return size of nodes
261 : */
262 1823 : unsigned getNodesSize() const { return nodes.size(); }
263 :
264 : /**
265 : * Returns number of knwon_nodes in bucket
266 : * @return size of knwon_nodes
267 : */
268 1541 : unsigned getKnownNodesSize() const { return known_nodes.size(); }
269 :
270 : /**
271 : * Returns number of mobile_nodes in bucket
272 : * @return size of mobile_nodes
273 : */
274 2961 : unsigned getConnectingNodesSize() const { return connecting_nodes.size(); }
275 :
276 : /**
277 : * Returns bucket lower limit
278 : * @return NodeId lower limit
279 : */
280 27724 : NodeId getLowerLimit() const { return lowerLimit_; };
281 :
282 : /**
283 : * Set bucket's lower limit
284 : * @param nodeId
285 : */
286 : void setLowerLimit(const NodeId& nodeId) { lowerLimit_ = nodeId; }
287 :
288 : // For tests
289 :
290 : /**
291 : * Get sockets from bucket
292 : * @return set of sockets
293 : */
294 : std::set<std::shared_ptr<dhtnet::ChannelSocketInterface>> getNodeSockets() const;
295 :
296 : private:
297 : NodeId lowerLimit_;
298 : std::map<NodeId, NodeInfo> nodes;
299 : std::set<NodeId> known_nodes;
300 : std::set<NodeId> connecting_nodes;
301 : std::set<NodeId> mobile_nodes;
302 : mutable std::mutex mutex;
303 : };
304 :
305 : // ####################################################################################################
306 :
307 : class RoutingTable
308 : {
309 : public:
310 : RoutingTable();
311 :
312 : /**
313 : * Add socket to bucket
314 : * @param socket
315 : * @return true if socket was added, false if not
316 : */
317 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket);
318 :
319 : /**
320 : * Add socket to specific bucket
321 : * @param channel
322 : * @param bucket
323 : * @return true if socket was added to bucket, false if not
324 : */
325 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& channel,
326 : std::list<Bucket>::iterator& bucket);
327 :
328 : /**
329 : * Removes node from routing table
330 : * Adds it to known_nodes or mobile_nodes depending on mobility
331 : * @param socket
332 : * @return true if node was removed, false if not
333 : */
334 : bool removeNode(const NodeId& nodeId);
335 :
336 : /**
337 : * Check if connected node exsits in routing table
338 : * @param nodeId
339 : * @return true if node exists, false if not
340 : */
341 : bool hasNode(const NodeId& nodeId);
342 :
343 : /**
344 : * Add known node to routing table
345 : * @param nodeId
346 : * @return true if known node was added, false if not
347 : */
348 : bool addKnownNode(const NodeId& nodeId);
349 :
350 : /**
351 : * Checks if known node exists in routing table
352 : * @param nodeId
353 : * @return true if known node exists, false if not
354 : */
355 292 : bool hasKnownNode(const NodeId& nodeId) const
356 : {
357 292 : auto bucket = findBucket(nodeId);
358 584 : return bucket->hasKnownNode(nodeId);
359 : }
360 :
361 : /**
362 : * Add mobile node to routing table
363 : * @param nodeId
364 : * @return true if mobile node was added, false if not
365 : */
366 : bool addMobileNode(const NodeId& nodeId);
367 :
368 : /**
369 : * Remove mobile node to routing table
370 : * @param nodeId
371 : * @return true if mobile node was removed, false if not
372 : */
373 : void removeMobileNode(const NodeId& nodeId);
374 :
375 : /**
376 : * Check if mobile node exists in routing table
377 : * @param nodeId
378 : * @return true if mobile node exists, false if not
379 : */
380 : bool hasMobileNode(const NodeId& nodeId);
381 :
382 : /**
383 : * Add connecting node to routing table
384 : * @param nodeId
385 : * @return true if connecting node was added, false if not
386 : */
387 : bool addConnectingNode(const NodeId& nodeId);
388 :
389 : /**
390 : * Remove connecting connecting node to routing table
391 : * @param nodeId
392 : * @return true if connecting node was removed, false if not
393 : */
394 : void removeConnectingNode(const NodeId& nodeId);
395 :
396 : /**
397 : * Check if Connecting node exists in routing table
398 : * @param nodeId
399 : * @return true if connecting node exists, false if not
400 : */
401 6 : bool hasConnectingNode(const NodeId& nodeId) const
402 : {
403 6 : auto bucket = findBucket(nodeId);
404 12 : return bucket->hasConnectingNode(nodeId);
405 : }
406 :
407 : /**
408 : * Returns bucket iterator containing nodeId
409 : * @param nodeId
410 : * @return bucket iterator
411 : */
412 : std::list<Bucket>::iterator findBucket(const NodeId& nodeId);
413 :
414 : /**
415 : * Returns bucket iterator containing nodeId
416 : * @param nodeId
417 : * @return bucket iterator
418 : */
419 298 : inline const std::list<Bucket>::const_iterator findBucket(const NodeId& nodeId) const
420 : {
421 298 : return std::list<Bucket>::const_iterator(
422 596 : const_cast<RoutingTable*>(this)->findBucket(nodeId));
423 : }
424 :
425 : /**
426 : * Returns the count closest nodes to a specific nodeId
427 : * @param nodeId
428 : * @param count
429 : * @return vector of nodeIds
430 : */
431 : std::vector<NodeId> closestNodes(const NodeId& nodeId, unsigned count);
432 :
433 : /**
434 : * Returns number of buckets in routing table
435 : * @return size of buckets
436 : */
437 : unsigned getRoutingTableSize() const { return buckets.size(); }
438 :
439 : /**
440 : * Returns number of total nodes in routing table
441 : * @return size of nodes
442 : */
443 10 : unsigned getRoutingTableNodeCount() const
444 : {
445 10 : size_t count = 0;
446 48 : for (const auto& b : buckets)
447 38 : count += b.getNodesSize();
448 10 : return count;
449 : }
450 :
451 : /**
452 : * Prints routing table
453 : */
454 : void printRoutingTable() const;
455 :
456 : /**
457 : * Shutdowns a node
458 : * @param nodeId
459 : */
460 : void shutdownNode(const NodeId& nodeId);
461 :
462 : /**
463 : * Shutdowns all nodes in routing table and add them to known_nodes or mobile_nodes
464 : */
465 616 : void shutdownAllNodes()
466 : {
467 1582 : for (auto& bucket : buckets)
468 966 : bucket.shutdownAllNodes();
469 616 : }
470 :
471 : /**
472 : * Sets id for routing table
473 : * @param node
474 : */
475 588 : void setId(const NodeId& node) { id_ = node; }
476 :
477 : /**
478 : * Returns id for routing table
479 : * @return Nodeid
480 : */
481 : NodeId getId() const { return id_; }
482 :
483 : /**
484 : * Returns buckets in routing table
485 : * @return list buckets
486 : */
487 1128 : std::list<Bucket>& getBuckets() { return buckets; }
488 :
489 : /**
490 : * Returns all routing table's connected nodes
491 : * @return vector of nodeIds
492 : */
493 : std::vector<NodeId> getNodes() const;
494 :
495 : /**
496 : * Returns all routing table's known nodes
497 : *@return vector of nodeIds
498 : */
499 : std::vector<NodeId> getKnownNodes() const;
500 :
501 : /**
502 : * Returns all routing table's mobile nodes
503 : * @return vector of nodeIds
504 : */
505 : std::vector<NodeId> getMobileNodes() const;
506 :
507 : /**
508 : * Returns all routing table's connecting nodes
509 : * @return vector of nodeIds
510 : */
511 : std::vector<NodeId> getConnectingNodes() const;
512 :
513 : /**
514 : * Returns mobile nodes corresponding to the swarm's id
515 : * @return vector of nodeIds
516 : */
517 : std::vector<NodeId> getBucketMobileNodes() const;
518 :
519 : /**
520 : * Test if connected nodeId is in specific bucket
521 : * @param it
522 : * @param nodeId
523 : * @return true if nodeId is in bucket, false if not
524 : */
525 : bool contains(const std::list<Bucket>::iterator& it, const NodeId& nodeId) const;
526 :
527 : /**
528 : * Return every node from each bucket
529 : */
530 : std::vector<NodeId> getAllNodes() const;
531 :
532 : /**
533 : * Delete node from every table in bucket
534 : */
535 : void deleteNode(const NodeId& nodeId);
536 :
537 : private:
538 : RoutingTable(const RoutingTable&) = delete;
539 : RoutingTable& operator=(const RoutingTable&) = delete;
540 :
541 : /**
542 : * Returns middle of routing table
543 : * @param it
544 : * @return NodeId
545 : */
546 : NodeId middle(std::list<Bucket>::iterator& it) const;
547 :
548 : /**
549 : * Returns depth of routing table
550 : * @param bucket
551 : * @return depth
552 : */
553 : unsigned depth(std::list<Bucket>::iterator& bucket) const;
554 :
555 : /**
556 : * Splits bucket
557 : * @param bucket
558 : * @return true if bucket was split, false if not
559 : */
560 : bool split(std::list<Bucket>::iterator& bucket);
561 :
562 : NodeId id_;
563 :
564 : std::list<Bucket> buckets;
565 :
566 : mutable std::mutex mutex_;
567 : };
568 : }; // namespace jami
|
