3 This file is part of GNUnet.
4 Copyright (C) 2001-2017 GNUnet e.V.
6 GNUnet is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published
8 by the Free Software Foundation; either version 3, or (at your
9 option) any later version.
11 GNUnet is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNUnet; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA.
23 * @file cadet/gnunet-service-cadet-new_peer.c
24 * @brief Information we track per peer.
25 * @author Bartlomiej Polot
26 * @author Christian Grothoff
29 #include "gnunet_util_lib.h"
30 #include "gnunet_signatures.h"
31 #include "gnunet_transport_service.h"
32 #include "gnunet_ats_service.h"
33 #include "gnunet_core_service.h"
34 #include "gnunet_statistics_service.h"
35 #include "cadet_protocol.h"
36 #include "cadet_path.h"
37 #include "gnunet-service-cadet-new.h"
38 #include "gnunet-service-cadet-new_connection.h"
39 #include "gnunet-service-cadet-new_dht.h"
40 #include "gnunet-service-cadet-new_peer.h"
41 #include "gnunet-service-cadet-new_paths.h"
42 #include "gnunet-service-cadet-new_tunnels.h"
45 * How long do we wait until tearing down an idle peer?
47 #define IDLE_PEER_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 5)
50 * How long do we keep paths around if we no longer care about the peer?
52 #define IDLE_PATH_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
58 * Data structure used to track whom we have to notify about changes
59 * to our message queue.
61 struct GCP_MessageQueueManager
67 struct GCP_MessageQueueManager *next;
72 struct GCP_MessageQueueManager *prev;
75 * Function to call with updated message queue object.
77 GCP_MessageQueueNotificationCallback cb;
85 * The peer this is for.
93 * Struct containing all information regarding a given peer
100 struct GNUNET_PeerIdentity pid;
103 * Last time we heard from this peer
105 struct GNUNET_TIME_Absolute last_contact;
108 * Array of DLLs of paths traversing the peer, organized by the
109 * offset of the peer on the larger path.
111 struct CadetPeerPathEntry **path_heads;
114 * Array of DLL of paths traversing the peer, organized by the
115 * offset of the peer on the larger path.
117 struct CadetPeerPathEntry **path_tails;
120 * Notifications to call when @e core_mq changes.
122 struct GCP_MessageQueueManager *mqm_head;
125 * Notifications to call when @e core_mq changes.
127 struct GCP_MessageQueueManager *mqm_tail;
130 * MIN-heap of paths owned by this peer (they also end at this
131 * peer). Ordered by desirability.
133 struct GNUNET_CONTAINER_Heap *path_heap;
136 * Handle to stop the DHT search for paths to this peer
138 struct GCD_search_handle *search_h;
141 * Task to stop the DHT search for paths to this peer
143 struct GNUNET_SCHEDULER_Task *search_delayedXXX;
146 * Task to destroy this entry.
148 struct GNUNET_SCHEDULER_Task *destroy_task;
151 * Tunnel to this peer, if any.
153 struct CadetTunnel *t;
156 * Connections that go through this peer; indexed by tid.
158 struct GNUNET_CONTAINER_MultiShortmap *connections;
161 * Handle for core transmissions.
163 struct GNUNET_MQ_Handle *core_mq;
166 * Hello message of the peer.
168 struct GNUNET_HELLO_Message *hello;
171 * Handle to us offering the HELLO to the transport.
173 struct GNUNET_TRANSPORT_OfferHelloHandle *hello_offer;
176 * Handle to our ATS request asking ATS to suggest an address
177 * to TRANSPORT for this peer (to establish a direct link).
179 struct GNUNET_ATS_ConnectivitySuggestHandle *connectivity_suggestion;
182 * How many messages are in the queue to this peer.
184 unsigned int queue_n;
187 * How many paths do we have to this peer (in all @e path_heads DLLs combined).
189 unsigned int num_paths;
192 * Current length of the @e path_heads and @path_tails arrays.
193 * The arrays should be grown as needed.
195 unsigned int path_dll_length;
201 * Get the static string for a peer ID.
205 * @return Static string for it's ID.
208 GCP_2s (const struct CadetPeer *peer)
212 return GNUNET_i2s (&peer->pid);
217 * This peer is no longer be needed, clean it up now.
219 * @param cls peer to clean up
222 destroy_peer (void *cls)
224 struct CadetPeer *cp = cls;
226 cp->destroy_task = NULL;
227 GNUNET_assert (NULL == cp->t);
228 GNUNET_assert (NULL == cp->core_mq);
229 GNUNET_assert (0 == cp->path_dll_length);
230 GNUNET_assert (0 == GNUNET_CONTAINER_multishortmap_size (cp->connections));
231 GNUNET_assert (GNUNET_YES ==
232 GNUNET_CONTAINER_multipeermap_remove (peers,
235 GNUNET_free_non_null (cp->path_heads);
236 GNUNET_free_non_null (cp->path_tails);
237 cp->path_dll_length = 0;
238 if (NULL != cp->search_h)
240 GCD_search_stop (cp->search_h);
243 /* FIXME: clean up search_delayedXXX! */
245 if (NULL != cp->hello_offer)
247 GNUNET_TRANSPORT_offer_hello_cancel (cp->hello_offer);
248 cp->hello_offer = NULL;
250 if (NULL != cp->connectivity_suggestion)
252 GNUNET_ATS_connectivity_suggest_cancel (cp->connectivity_suggestion);
253 cp->connectivity_suggestion = NULL;
255 GNUNET_CONTAINER_multishortmap_destroy (cp->connections);
256 GNUNET_CONTAINER_heap_destroy (cp->path_heap);
257 GNUNET_free_non_null (cp->hello);
258 /* Peer should not be freed if paths exist; if there are no paths,
259 there ought to be no connections, and without connections, no
260 notifications. Thus we can assert that mqm_head is empty at this
262 GNUNET_assert (NULL == cp->mqm_head);
268 * Set the message queue to @a mq for peer @a cp and notify watchers.
270 * @param cp peer to modify
271 * @param mq message queue to set (can be NULL)
274 GCP_set_mq (struct CadetPeer *cp,
275 struct GNUNET_MQ_Handle *mq)
278 for (struct GCP_MessageQueueManager *mqm = cp->mqm_head;
281 mqm->cb (mqm->cb_cls,
287 * Send the message in @a env to @a cp.
290 * @param env envelope with the message to send
293 GCP_send (struct CadetPeer *cp,
294 struct GNUNET_MQ_Envelope *env)
296 GNUNET_assert (NULL != cp->core_mq);
297 GNUNET_MQ_send (cp->core_mq,
303 * Function called to destroy a peer now.
306 * @param pid identity of the peer (unused)
307 * @param value the `struct CadetPeer` to clean up
308 * @return #GNUNET_OK (continue to iterate)
311 destroy_iterator_cb (void *cls,
312 const struct GNUNET_PeerIdentity *pid,
315 struct CadetPeer *cp = value;
317 if (NULL != cp->destroy_task)
319 GNUNET_SCHEDULER_cancel (cp->destroy_task);
320 cp->destroy_task = NULL;
328 * Clean up all entries about all peers.
329 * Must only be called after all tunnels, CORE-connections and
330 * connections are down.
333 GCP_destroy_all_peers ()
335 GNUNET_CONTAINER_multipeermap_iterate (peers,
336 &destroy_iterator_cb,
342 * This peer may no longer be needed, consider cleaning it up.
344 * @param cp peer to clean up
347 consider_peer_destroy (struct CadetPeer *cp);
351 * We really no longere care about a peer, stop hogging memory with paths to it.
352 * Afterwards, see if there is more to be cleaned up about this peer.
354 * @param cls a `struct CadetPeer`.
357 drop_paths (void *cls)
359 struct CadetPeer *cp = cls;
360 struct CadetPeerPath *path;
362 cp->destroy_task = NULL;
363 while (NULL != (path = GNUNET_CONTAINER_heap_remove_root (cp->path_heap)))
365 consider_peer_destroy (cp);
370 * This peer may no longer be needed, consider cleaning it up.
372 * @param cp peer to clean up
375 consider_peer_destroy (struct CadetPeer *cp)
377 struct GNUNET_TIME_Relative exp;
379 if (NULL != cp->destroy_task)
381 GNUNET_SCHEDULER_cancel (cp->destroy_task);
382 cp->destroy_task = NULL;
385 return; /* still relevant! */
386 if (NULL != cp->core_mq)
387 return; /* still relevant! */
388 if (0 != GNUNET_CONTAINER_multishortmap_size (cp->connections))
389 return; /* still relevant! */
390 if (0 < GNUNET_CONTAINER_heap_get_size (cp->path_heap))
392 cp->destroy_task = GNUNET_SCHEDULER_add_delayed (IDLE_PATH_TIMEOUT,
397 if (0 < cp->path_dll_length)
398 return; /* still relevant! */
399 if (NULL != cp->hello)
401 /* relevant only until HELLO expires */
402 exp = GNUNET_TIME_absolute_get_remaining (GNUNET_HELLO_get_last_expiration (cp->hello));
403 cp->destroy_task = GNUNET_SCHEDULER_add_delayed (exp,
408 cp->destroy_task = GNUNET_SCHEDULER_add_delayed (IDLE_PEER_TIMEOUT,
415 * Add an entry to the DLL of all of the paths that this peer is on.
417 * @param cp peer to modify
418 * @param entry an entry on a path
419 * @param off offset of this peer on the path
422 GCP_path_entry_add (struct CadetPeer *cp,
423 struct CadetPeerPathEntry *entry,
426 if (off >= cp->path_dll_length)
428 unsigned int len = cp->path_dll_length;
430 GNUNET_array_grow (cp->path_heads,
433 GNUNET_array_grow (cp->path_tails,
437 GNUNET_CONTAINER_DLL_insert (cp->path_heads[off],
442 /* If we have a tunnel to this peer, tell the tunnel that there is a
443 new path available. */
445 GCT_consider_path (cp->t,
452 * Remove an entry from the DLL of all of the paths that this peer is on.
454 * @param cp peer to modify
455 * @param entry an entry on a path
456 * @param off offset of this peer on the path
459 GCP_path_entry_remove (struct CadetPeer *cp,
460 struct CadetPeerPathEntry *entry,
463 GNUNET_CONTAINER_DLL_remove (cp->path_heads[off],
466 GNUNET_assert (0 < cp->num_paths);
472 * Try adding a @a path to this @a peer. If the peer already
473 * has plenty of paths, return NULL.
475 * @param cp peer to which the @a path leads to
476 * @param path a path looking for an owner; may not be fully initialized yet!
477 * @param off offset of @a cp in @a path
478 * @return NULL if this peer does not care to become a new owner,
479 * otherwise the node in the peer's path heap for the @a path.
481 struct GNUNET_CONTAINER_HeapNode *
482 GCP_attach_path (struct CadetPeer *cp,
483 struct CadetPeerPath *path,
486 GNUNET_CONTAINER_HeapCostType desirability;
487 struct CadetPeerPath *root;
488 GNUNET_CONTAINER_HeapCostType root_desirability;
489 struct GNUNET_CONTAINER_HeapNode *hn;
491 /* FIXME: desirability is not yet initialized; tricky! */
492 desirability = GCPP_get_desirability (path);
494 GNUNET_CONTAINER_heap_peek2 (cp->path_heap,
499 root_desirability = 0;
502 if ( (DESIRED_CONNECTIONS_PER_TUNNEL > cp->num_paths) &&
503 (desirability < root_desirability) )
506 /* Yes, we'd like to add this path, add to our heap */
507 hn = GNUNET_CONTAINER_heap_insert (cp->path_heap,
511 /* Consider maybe dropping other paths because of the new one */
512 if (GNUNET_CONTAINER_heap_get_size (cp->path_heap) >=
513 2 * DESIRED_CONNECTIONS_PER_TUNNEL)
515 /* Now we have way too many, drop least desirable UNLESS it is in use!
516 (Note that this intentionally keeps highly desireable, but currently
517 unused paths around in the hope that we might be able to switch, even
518 if the number of paths exceeds the threshold.) */
519 root = GNUNET_CONTAINER_heap_peek (cp->path_heap);
521 GCPP_get_connection (root,
523 GCPP_get_length (root) - 1))
525 /* Got plenty of paths to this destination, and this is a low-quality
526 one that we don't care, allow it to die. */
527 GNUNET_assert (root ==
528 GNUNET_CONTAINER_heap_remove_root (cp->path_heap));
537 * This peer can no longer own @a path as the path
538 * has been extended and a peer further down the line
539 * is now the new owner.
541 * @param cp old owner of the @a path
542 * @param path path where the ownership is lost
543 * @param hn note in @a cp's path heap that must be deleted
546 GCP_detach_path (struct CadetPeer *cp,
547 struct CadetPeerPath *path,
548 struct GNUNET_CONTAINER_HeapNode *hn)
550 GNUNET_assert (path ==
551 GNUNET_CONTAINER_heap_remove_node (hn));
556 * Add a @a connection to this @a cp.
558 * @param cp peer via which the @a connection goes
559 * @param cc the connection to add
562 GCP_add_connection (struct CadetPeer *cp,
563 struct CadetConnection *cc)
565 GNUNET_assert (GNUNET_OK ==
566 GNUNET_CONTAINER_multishortmap_put (cp->connections,
567 &GCC_get_id (cc)->connection_of_tunnel,
569 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
574 * Remove a @a connection that went via this @a cp.
576 * @param cp peer via which the @a connection went
577 * @param cc the connection to remove
580 GCP_remove_connection (struct CadetPeer *cp,
581 struct CadetConnection *cc)
583 GNUNET_assert (GNUNET_YES ==
584 GNUNET_CONTAINER_multishortmap_remove (cp->connections,
585 &GCC_get_id (cc)->connection_of_tunnel,
591 * This peer is now on more "active" duty, activate processes related to it.
593 * @param cp the more-active peer
596 consider_peer_activate (struct CadetPeer *cp)
600 if (NULL != cp->destroy_task)
602 /* It's active, do not destory! */
603 GNUNET_SCHEDULER_cancel (cp->destroy_task);
604 cp->destroy_task = NULL;
606 if ( (0 == GNUNET_CONTAINER_multishortmap_size (cp->connections)) &&
609 /* We're just on a path or directly connected; don't bother too much */
610 if (NULL != cp->connectivity_suggestion)
612 GNUNET_ATS_connectivity_suggest_cancel (cp->connectivity_suggestion);
613 cp->connectivity_suggestion = NULL;
615 if (NULL != cp->search_h)
617 GCD_search_stop (cp->search_h);
622 if (NULL == cp->core_mq)
624 /* Lacks direct connection, try to create one by querying the DHT */
625 if ( (NULL == cp->search_h) &&
626 (DESIRED_CONNECTIONS_PER_TUNNEL < cp->num_paths) )
628 = GCD_search (&cp->pid);
632 /* Have direct connection, stop DHT search if active */
633 if (NULL != cp->search_h)
635 GCD_search_stop (cp->search_h);
640 /* If we have a tunnel, our urge for connections is much bigger */
641 strength = (NULL != cp->t) ? 32 : 1;
642 if (NULL != cp->connectivity_suggestion)
643 GNUNET_ATS_connectivity_suggest_cancel (cp->connectivity_suggestion);
644 cp->connectivity_suggestion
645 = GNUNET_ATS_connectivity_suggest (ats_ch,
652 * Retrieve the CadetPeer stucture associated with the
653 * peer. Optionally create one and insert it in the appropriate
654 * structures if the peer is not known yet.
656 * @param peer_id Full identity of the peer.
657 * @param create #GNUNET_YES if a new peer should be created if unknown.
658 * #GNUNET_NO to return NULL if peer is unknown.
659 * @return Existing or newly created peer structure.
660 * NULL if unknown and not requested @a create
663 GCP_get (const struct GNUNET_PeerIdentity *peer_id,
666 struct CadetPeer *cp;
668 cp = GNUNET_CONTAINER_multipeermap_get (peers,
672 if (GNUNET_NO == create)
674 cp = GNUNET_new (struct CadetPeer);
676 cp->connections = GNUNET_CONTAINER_multishortmap_create (32,
678 cp->path_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
679 GNUNET_assert (GNUNET_YES ==
680 GNUNET_CONTAINER_multipeermap_put (peers,
683 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
689 * Obtain the peer identity for a `struct CadetPeer`.
691 * @param cp our peer handle
692 * @return the peer identity
694 const struct GNUNET_PeerIdentity *
695 GCP_get_id (struct CadetPeer *cp)
702 * Iterate over all known peers.
704 * @param iter Iterator.
705 * @param cls Closure for @c iter.
708 GCP_iterate_all (GNUNET_CONTAINER_PeerMapIterator iter,
711 GNUNET_CONTAINER_multipeermap_iterate (peers,
718 * Count the number of known paths toward the peer.
720 * @param peer Peer to get path info.
721 * @return Number of known paths.
724 GCP_count_paths (const struct CadetPeer *peer)
726 return peer->num_paths;
731 * Iterate over the paths to a peer.
733 * @param peer Peer to get path info.
734 * @param callback Function to call for every path.
735 * @param callback_cls Closure for @a callback.
736 * @return Number of iterated paths.
739 GCP_iterate_paths (struct CadetPeer *peer,
740 GCP_PathIterator callback,
743 unsigned int ret = 0;
745 for (unsigned int i=0;i<peer->path_dll_length;i++)
747 for (struct CadetPeerPathEntry *pe = peer->path_heads[i];
752 callback (callback_cls,
764 * Iterate over the paths to @a peer where
765 * @a peer is at distance @a dist from us.
767 * @param peer Peer to get path info.
768 * @param dist desired distance of @a peer to us on the path
769 * @param callback Function to call for every path.
770 * @param callback_cls Closure for @a callback.
771 * @return Number of iterated paths.
774 GCP_iterate_paths_at (struct CadetPeer *peer,
776 GCP_PathIterator callback,
779 unsigned int ret = 0;
781 if (dist<peer->path_dll_length)
783 for (struct CadetPeerPathEntry *pe = peer->path_heads[dist];
788 callback (callback_cls,
799 * Get the tunnel towards a peer.
801 * @param peer Peer to get from.
802 * @param create #GNUNET_YES to create a tunnel if we do not have one
803 * @return Tunnel towards peer.
806 GCP_get_tunnel (struct CadetPeer *peer,
811 if ( (NULL != peer->t) ||
812 (GNUNET_NO == create) )
814 peer->t = GCT_create_tunnel (peer);
815 consider_peer_activate (peer);
821 * We got a HELLO for a @a peer, remember it, and possibly
822 * trigger adequate actions (like trying to connect).
824 * @param peer the peer we got a HELLO for
825 * @param hello the HELLO to remember
828 GCP_set_hello (struct CadetPeer *peer,
829 const struct GNUNET_HELLO_Message *hello)
831 /* FIXME: keep HELLO, possibly offer to TRANSPORT... */
833 consider_peer_destroy (peer);
838 * The tunnel to the given peer no longer exists, remove it from our
839 * data structures, and possibly clean up the peer itself.
841 * @param peer the peer affected
842 * @param t the dead tunnel
845 GCP_drop_tunnel (struct CadetPeer *peer,
846 struct CadetTunnel *t)
848 GNUNET_assert (peer->t == t);
850 consider_peer_destroy (peer);
855 * Start message queue change notifications.
857 * @param cp peer to notify for
858 * @param cb function to call if mq becomes available or unavailable
859 * @param cb_cls closure for @a cb
860 * @return handle to cancel request
862 struct GCP_MessageQueueManager *
863 GCP_request_mq (struct CadetPeer *cp,
864 GCP_MessageQueueNotificationCallback cb,
867 struct GCP_MessageQueueManager *mqm;
869 mqm = GNUNET_new (struct GCP_MessageQueueManager);
871 mqm->cb_cls = cb_cls;
873 GNUNET_CONTAINER_DLL_insert (cp->mqm_head,
876 if (NULL != cp->core_mq)
884 * Stops message queue change notifications.
886 * @param mqm handle matching request to cancel
889 GCP_request_mq_cancel (struct GCP_MessageQueueManager *mqm)
891 struct CadetPeer *cp = mqm->cp;
893 GNUNET_CONTAINER_DLL_remove (cp->mqm_head,
901 /* end of gnunet-service-cadet-new_peer.c */