Line data Source code
1 : /*
2 : * Copyright (C) 2024 Savoir-faire Linux Inc.
3 : *
4 : * Author: Fadi Shehadeh <fadi.shehadeh@savoirfairelinux.com>
5 : *
6 : * This program is free software; you can redistribute it and/or modify
7 : * it under the terms of the GNU General Public License as published by
8 : * the Free Software Foundation; either version 3 of the License, or
9 : * (at your option) any later version.
10 : *
11 : * This program is distributed in the hope that it will be useful,
12 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : * GNU General Public License for more details.
15 : *
16 : * You should have received a copy of the GNU General Public License
17 : * along with this program; if not, write to the Free Software
18 : * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
19 : */
20 :
21 : #pragma once
22 :
23 : #include "manager.h"
24 :
25 : #include <dhtnet/multiplexed_socket.h>
26 :
27 : #include <opendht/infohash.h>
28 :
29 : #include <asio.hpp>
30 : #include <asio/detail/deadline_timer_service.hpp>
31 :
32 : #include <vector>
33 : #include <memory>
34 : #include <list>
35 : #include <set>
36 : #include <algorithm>
37 :
38 : using NodeId = dht::PkId;
39 :
40 : namespace jami {
41 :
42 : static constexpr const std::chrono::minutes FIND_PERIOD {10};
43 :
44 : struct NodeInfo
45 : {
46 : bool isMobile_ {false};
47 : std::shared_ptr<dhtnet::ChannelSocketInterface> socket {};
48 : asio::steady_timer refresh_timer {*Manager::instance().ioContext(), FIND_PERIOD};
49 : NodeInfo() = delete;
50 1665 : NodeInfo(NodeInfo&&) = default;
51 1392 : NodeInfo(std::shared_ptr<dhtnet::ChannelSocketInterface> socket_)
52 1392 : : socket(socket_)
53 1393 : {}
54 1 : NodeInfo(bool mobile, std::shared_ptr<dhtnet::ChannelSocketInterface> socket_)
55 1 : : isMobile_(mobile)
56 1 : , socket(socket_)
57 1 : {}
58 : };
59 :
60 : class Bucket
61 :
62 : {
63 : public:
64 : static constexpr int BUCKET_MAX_SIZE = 2;
65 :
66 : Bucket() = delete;
67 : Bucket(const Bucket&) = delete;
68 : Bucket(const NodeId&);
69 :
70 : /**
71 : * Add Node socket to bucket
72 : * @param socket
73 : * @return true if node was added, false if not
74 : */
75 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket);
76 :
77 : /**
78 : * Add NodeInfo to bucket
79 : * @param nodeInfo
80 : * @return true if node was added, false if not
81 : */
82 : bool addNode(NodeInfo&& info);
83 :
84 : /**
85 : * Remove NodeId socket from bucket and insert it in known_nodes or
86 : * mobile_nodes depending on its type
87 : * @param nodeId
88 : * @return true if node was removed, false if not
89 : */
90 : bool removeNode(const NodeId& nodeId);
91 :
92 : /**
93 : * Get connected nodes from bucket
94 : * @return map of NodeId and NodeInfo
95 : */
96 343 : std::map<NodeId, NodeInfo>& getNodes() { return nodes; }
97 :
98 : /**
99 : * Get NodeIds from bucket
100 : * @return set of NodeIds
101 : */
102 : std::set<NodeId> getNodeIds() const;
103 :
104 : /**
105 : * Test if socket exists in nodes
106 : * @param nodeId
107 : * @return true if node exists, false if not
108 : */
109 : bool hasNode(const NodeId& nodeId) const;
110 :
111 : /**
112 : * Add NodeId to known_nodes if it doesn't exist in nodes
113 : * @param nodeId
114 : * @return true if known node was added, false if not
115 : */
116 : bool addKnownNode(const NodeId& nodeId);
117 :
118 : /**
119 : * Remove NodeId from known_nodes
120 : * @param nodeId
121 : */
122 299 : void removeKnownNode(const NodeId& nodeId) { known_nodes.erase(nodeId); }
123 :
124 : /**
125 : * Get NodeIds from known_nodes
126 : * @return set of known NodeIds
127 : */
128 1482 : const std::set<NodeId>& getKnownNodes() const { return known_nodes; }
129 :
130 : /**
131 : * Returns NodeId from known_nodes at index
132 : * @param index
133 : * @return NodeId
134 : */
135 : NodeId getKnownNode(unsigned index) const;
136 :
137 : /**
138 : * Test if NodeId exist in known_nodes
139 : * @param nodeId
140 : * @return true if known node exists, false if not
141 : */
142 168 : bool hasKnownNode(const NodeId& nodeId) const
143 : {
144 168 : return known_nodes.find(nodeId) != known_nodes.end();
145 : }
146 :
147 : /**
148 : * Add NodeId to mobile_nodes if it doesn't exist in nodes
149 : * @param nodeId
150 : * @return true if mobile node was added, false if not
151 : */
152 : bool addMobileNode(const NodeId& nodeId);
153 :
154 : /**
155 : * Remove NodeId from mobile_nodes
156 : * @param nodeId
157 : */
158 3 : void removeMobileNode(const NodeId& nodeId) { mobile_nodes.erase(nodeId); }
159 :
160 : /**
161 : * Test if NodeId exist in mobile_nodes
162 : * @param nodeId
163 : * @return true if mobile node exists, false if not
164 : */
165 13 : bool hasMobileNode(const NodeId& nodeId)
166 : {
167 13 : return mobile_nodes.find(nodeId) != mobile_nodes.end();
168 : }
169 :
170 : /**
171 : * Get NodeIds from mobile_nodes
172 : * @return set of mobile NodeIds
173 : */
174 12068 : const std::set<NodeId>& getMobileNodes() const { return mobile_nodes; }
175 :
176 : /**
177 : * Add NodeId to connecting_nodes if it doesn't exist in nodes
178 : * @param nodeId
179 : * @param nodeInfo
180 : * @return true if connecting node was added, false if not
181 : */
182 : bool addConnectingNode(const NodeId& nodeId);
183 :
184 : /**
185 : * Remove NodeId from connecting_nodes
186 : * @param nodeId
187 : */
188 358 : void removeConnectingNode(const NodeId& nodeId) { connecting_nodes.erase(nodeId); }
189 :
190 : /** Get NodeIds of connecting_nodes
191 : * @return set of connecting NodeIds
192 : */
193 346 : const std::set<NodeId>& getConnectingNodes() const { return connecting_nodes; };
194 :
195 : /**
196 : * Test if NodeId exist in connecting_nodes
197 : * @param nodeId
198 : * @return true if connecting node exists, false if not
199 : */
200 18 : bool hasConnectingNode(const NodeId& nodeId) const
201 : {
202 18 : return connecting_nodes.find(nodeId) != connecting_nodes.end();
203 : }
204 :
205 1999 : bool isEmpty() const { return nodes.empty(); }
206 :
207 : /**
208 : * Indicate if bucket is full
209 : * @return true if bucket is full, false if not
210 : */
211 1705 : bool isFull() const { return nodes.size() == BUCKET_MAX_SIZE; };
212 :
213 : /**
214 : * Returns random numberNodes NodeId from known_nodes
215 : * @param numberNodes
216 : * @param rd
217 : * @return set of numberNodes random known NodeIds
218 : */
219 : std::set<NodeId> getKnownNodesRandom(unsigned numberNodes, std::mt19937_64& rd) const;
220 :
221 : /**
222 : * Returns random NodeId from known_nodes
223 : * @param rd
224 : * @return random known NodeId
225 : */
226 1 : NodeId randomId(std::mt19937_64& rd) const
227 : {
228 1 : auto node = getKnownNodesRandom(1, rd);
229 2 : return *node.begin();
230 1 : }
231 :
232 : /**
233 : * Returns socket's timer
234 : * @param socket
235 : * @return timer
236 : */
237 : asio::steady_timer& getNodeTimer(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket);
238 :
239 : /**
240 : * Shutdowns socket and removes it from nodes.
241 : * The corresponding node is moved to known_nodes or mobile_nodes
242 : * @param socket
243 : * @return true if node was shutdown, false if not found
244 : */
245 : bool shutdownNode(const NodeId& nodeId);
246 :
247 : /**
248 : * Shutdowns all sockets in nodes through shutdownNode
249 : */
250 : void shutdownAllNodes();
251 :
252 : /**
253 : * Prints bucket and bucket's number
254 : */
255 : void printBucket(unsigned number) const;
256 :
257 : /**
258 : * Change mobility of specific node, mobile or not
259 : */
260 : void changeMobility(const NodeId& nodeId, bool isMobile);
261 :
262 : /**
263 : * Returns number of nodes in bucket
264 : * @return size of nodes
265 : */
266 1804 : unsigned getNodesSize() const { return nodes.size(); }
267 :
268 : /**
269 : * Returns number of knwon_nodes in bucket
270 : * @return size of knwon_nodes
271 : */
272 1346 : unsigned getKnownNodesSize() const { return known_nodes.size(); }
273 :
274 : /**
275 : * Returns number of mobile_nodes in bucket
276 : * @return size of mobile_nodes
277 : */
278 2874 : unsigned getConnectingNodesSize() const { return connecting_nodes.size(); }
279 :
280 : /**
281 : * Returns bucket lower limit
282 : * @return NodeId lower limit
283 : */
284 28139 : NodeId getLowerLimit() const { return lowerLimit_; };
285 :
286 : /**
287 : * Set bucket's lower limit
288 : * @param nodeId
289 : */
290 : void setLowerLimit(const NodeId& nodeId) { lowerLimit_ = nodeId; }
291 :
292 : // For tests
293 :
294 : /**
295 : * Get sockets from bucket
296 : * @return set of sockets
297 : */
298 : std::set<std::shared_ptr<dhtnet::ChannelSocketInterface>> getNodeSockets() const;
299 :
300 : private:
301 : NodeId lowerLimit_;
302 : std::map<NodeId, NodeInfo> nodes;
303 : std::set<NodeId> known_nodes;
304 : std::set<NodeId> connecting_nodes;
305 : std::set<NodeId> mobile_nodes;
306 : mutable std::mutex mutex;
307 : };
308 :
309 : // ####################################################################################################
310 :
311 : class RoutingTable
312 : {
313 : public:
314 : RoutingTable();
315 :
316 : /**
317 : * Add socket to bucket
318 : * @param socket
319 : * @return true if socket was added, false if not
320 : */
321 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& socket);
322 :
323 : /**
324 : * Add socket to specific bucket
325 : * @param channel
326 : * @param bucket
327 : * @return true if socket was added to bucket, false if not
328 : */
329 : bool addNode(const std::shared_ptr<dhtnet::ChannelSocketInterface>& channel,
330 : std::list<Bucket>::iterator& bucket);
331 :
332 : /**
333 : * Removes node from routing table
334 : * Adds it to known_nodes or mobile_nodes depending on mobility
335 : * @param socket
336 : * @return true if node was removed, false if not
337 : */
338 : bool removeNode(const NodeId& nodeId);
339 :
340 : /**
341 : * Check if connected node exsits in routing table
342 : * @param nodeId
343 : * @return true if node exists, false if not
344 : */
345 : bool hasNode(const NodeId& nodeId);
346 :
347 : /**
348 : * Add known node to routing table
349 : * @param nodeId
350 : * @return true if known node was added, false if not
351 : */
352 : bool addKnownNode(const NodeId& nodeId);
353 :
354 : /**
355 : * Checks if known node exists in routing table
356 : * @param nodeId
357 : * @return true if known node exists, false if not
358 : */
359 161 : bool hasKnownNode(const NodeId& nodeId) const
360 : {
361 161 : auto bucket = findBucket(nodeId);
362 322 : return bucket->hasKnownNode(nodeId);
363 : }
364 :
365 : /**
366 : * Add mobile node to routing table
367 : * @param nodeId
368 : * @return true if mobile node was added, false if not
369 : */
370 : bool addMobileNode(const NodeId& nodeId);
371 :
372 : /**
373 : * Remove mobile node to routing table
374 : * @param nodeId
375 : * @return true if mobile node was removed, false if not
376 : */
377 : void removeMobileNode(const NodeId& nodeId);
378 :
379 : /**
380 : * Check if mobile node exists in routing table
381 : * @param nodeId
382 : * @return true if mobile node exists, false if not
383 : */
384 : bool hasMobileNode(const NodeId& nodeId);
385 :
386 : /**
387 : * Add connecting node to routing table
388 : * @param nodeId
389 : * @return true if connecting node was added, false if not
390 : */
391 : bool addConnectingNode(const NodeId& nodeId);
392 :
393 : /**
394 : * Remove connecting connecting node to routing table
395 : * @param nodeId
396 : * @return true if connecting node was removed, false if not
397 : */
398 : void removeConnectingNode(const NodeId& nodeId);
399 :
400 : /**
401 : * Check if Connecting node exists in routing table
402 : * @param nodeId
403 : * @return true if connecting node exists, false if not
404 : */
405 6 : bool hasConnectingNode(const NodeId& nodeId) const
406 : {
407 6 : auto bucket = findBucket(nodeId);
408 12 : return bucket->hasConnectingNode(nodeId);
409 : }
410 :
411 : /**
412 : * Returns bucket iterator containing nodeId
413 : * @param nodeId
414 : * @return bucket iterator
415 : */
416 : std::list<Bucket>::iterator findBucket(const NodeId& nodeId);
417 :
418 : /**
419 : * Returns bucket iterator containing nodeId
420 : * @param nodeId
421 : * @return bucket iterator
422 : */
423 167 : inline const std::list<Bucket>::const_iterator findBucket(const NodeId& nodeId) const
424 : {
425 167 : return std::list<Bucket>::const_iterator(
426 334 : const_cast<RoutingTable*>(this)->findBucket(nodeId));
427 : }
428 :
429 : /**
430 : * Returns the count closest nodes to a specific nodeId
431 : * @param nodeId
432 : * @param count
433 : * @return vector of nodeIds
434 : */
435 : std::vector<NodeId> closestNodes(const NodeId& nodeId, unsigned count);
436 :
437 : /**
438 : * Returns number of buckets in routing table
439 : * @return size of buckets
440 : */
441 : unsigned getRoutingTableSize() const { return buckets.size(); }
442 :
443 : /**
444 : * Returns number of total nodes in routing table
445 : * @return size of nodes
446 : */
447 10 : unsigned getRoutingTableNodeCount() const
448 : {
449 10 : size_t count = 0;
450 43 : for (const auto& b : buckets)
451 33 : count += b.getNodesSize();
452 10 : 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 404 : void shutdownAllNodes()
470 : {
471 1151 : for (auto& bucket : buckets)
472 747 : bucket.shutdownAllNodes();
473 404 : }
474 :
475 : /**
476 : * Sets id for routing table
477 : * @param node
478 : */
479 404 : void setId(const NodeId& node) { id_ = node; }
480 :
481 : /**
482 : * Returns id for routing table
483 : * @return Nodeid
484 : */
485 : NodeId getId() const { return id_; }
486 :
487 : /**
488 : * Returns buckets in routing table
489 : * @return list buckets
490 : */
491 901 : 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 all routing table's connecting nodes
513 : * @return vector of nodeIds
514 : */
515 : std::vector<NodeId> getConnectingNodes() const;
516 :
517 : /**
518 : * Returns mobile nodes corresponding to the swarm's id
519 : * @return vector of nodeIds
520 : */
521 : std::vector<NodeId> getBucketMobileNodes() const;
522 :
523 : /**
524 : * Test if connected nodeId is in specific bucket
525 : * @param it
526 : * @param nodeId
527 : * @return true if nodeId is in bucket, false if not
528 : */
529 : bool contains(const std::list<Bucket>::iterator& it, const NodeId& nodeId) const;
530 :
531 : /**
532 : * Return every node from each bucket
533 : */
534 : std::vector<NodeId> getAllNodes() const;
535 :
536 : /**
537 : * Delete node from every table in bucket
538 : */
539 : void deleteNode(const NodeId& nodeId);
540 :
541 : private:
542 : RoutingTable(const RoutingTable&) = delete;
543 : RoutingTable& operator=(const RoutingTable&) = delete;
544 :
545 : /**
546 : * Returns middle of routing table
547 : * @param it
548 : * @return NodeId
549 : */
550 : NodeId middle(std::list<Bucket>::iterator& it) const;
551 :
552 : /**
553 : * Returns depth of routing table
554 : * @param bucket
555 : * @return depth
556 : */
557 : unsigned depth(std::list<Bucket>::iterator& bucket) const;
558 :
559 : /**
560 : * Splits bucket
561 : * @param bucket
562 : * @return true if bucket was split, false if not
563 : */
564 : bool split(std::list<Bucket>::iterator& bucket);
565 :
566 : NodeId id_;
567 :
568 : std::list<Bucket> buckets;
569 :
570 : mutable std::mutex mutex_;
571 : };
572 : }; // namespace jami
|
