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 * - implement GCP_set_hello() / do HELLO advertising properly
30 * - optimize stopping/restarting DHT search to situations
31 * where we actually need it (i.e. not if we have a direct connection,
32 * or if we already have plenty of good short ones, or maybe even
33 * to take a break if we have some connections and have searched a lot (?))
34 * - optimize MQM ready scans (O(n) -> O(1))
37 #include "gnunet_util_lib.h"
38 #include "gnunet_signatures.h"
39 #include "gnunet_transport_service.h"
40 #include "gnunet_ats_service.h"
41 #include "gnunet_core_service.h"
42 #include "gnunet_statistics_service.h"
43 #include "cadet_protocol.h"
44 #include "cadet_path.h"
45 #include "gnunet-service-cadet-new.h"
46 #include "gnunet-service-cadet-new_connection.h"
47 #include "gnunet-service-cadet-new_dht.h"
48 #include "gnunet-service-cadet-new_peer.h"
49 #include "gnunet-service-cadet-new_paths.h"
50 #include "gnunet-service-cadet-new_tunnels.h"
53 * How long do we wait until tearing down an idle peer?
55 #define IDLE_PEER_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 5)
58 * How long do we keep paths around if we no longer care about the peer?
60 #define IDLE_PATH_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
66 * Data structure used to track whom we have to notify about changes
67 * to our message queue.
69 struct GCP_MessageQueueManager
75 struct GCP_MessageQueueManager *next;
80 struct GCP_MessageQueueManager *prev;
83 * Function to call with updated message queue object.
85 GCP_MessageQueueNotificationCallback cb;
93 * The peer this is for.
98 * Envelope this manager would like to transmit once it is its turn.
100 struct GNUNET_MQ_Envelope *env;
106 * Struct containing all information regarding a given peer
113 struct GNUNET_PeerIdentity pid;
116 * Last time we heard from this peer
118 struct GNUNET_TIME_Absolute last_contact;
121 * Array of DLLs of paths traversing the peer, organized by the
122 * offset of the peer on the larger path.
124 struct CadetPeerPathEntry **path_heads;
127 * Array of DLL of paths traversing the peer, organized by the
128 * offset of the peer on the larger path.
130 struct CadetPeerPathEntry **path_tails;
133 * Notifications to call when @e core_mq changes.
135 struct GCP_MessageQueueManager *mqm_head;
138 * Notifications to call when @e core_mq changes.
140 struct GCP_MessageQueueManager *mqm_tail;
143 * MIN-heap of paths owned by this peer (they also end at this
144 * peer). Ordered by desirability.
146 struct GNUNET_CONTAINER_Heap *path_heap;
149 * Handle to stop the DHT search for paths to this peer
151 struct GCD_search_handle *search_h;
154 * Task to stop the DHT search for paths to this peer
156 struct GNUNET_SCHEDULER_Task *search_delayedXXX;
159 * Task to destroy this entry.
161 struct GNUNET_SCHEDULER_Task *destroy_task;
164 * Tunnel to this peer, if any.
166 struct CadetTunnel *t;
169 * Connections that go through this peer; indexed by tid.
171 struct GNUNET_CONTAINER_MultiShortmap *connections;
174 * Handle for core transmissions.
176 struct GNUNET_MQ_Handle *core_mq;
179 * Hello message of the peer.
181 struct GNUNET_HELLO_Message *hello;
184 * Handle to us offering the HELLO to the transport.
186 struct GNUNET_TRANSPORT_OfferHelloHandle *hello_offer;
189 * Handle to our ATS request asking ATS to suggest an address
190 * to TRANSPORT for this peer (to establish a direct link).
192 struct GNUNET_ATS_ConnectivitySuggestHandle *connectivity_suggestion;
195 * How many messages are in the queue to this peer.
197 unsigned int queue_n;
200 * How many paths do we have to this peer (in all @e path_heads DLLs combined).
202 unsigned int num_paths;
205 * Number of message queue managers of this peer that have a message in waiting.
207 * Used to quickly see if we need to bother scanning the @e msm_head DLL.
208 * TODO: could be replaced by another DLL that would then allow us to avoid
209 * the O(n)-scan of the DLL for ready entries!
211 unsigned int mqm_ready_counter;
214 * Current length of the @e path_heads and @path_tails arrays.
215 * The arrays should be grown as needed.
217 unsigned int path_dll_length;
223 * Get the static string for a peer ID.
227 * @return Static string for it's ID.
230 GCP_2s (const struct CadetPeer *peer)
234 return GNUNET_i2s (&peer->pid);
239 * This peer is no longer be needed, clean it up now.
241 * @param cls peer to clean up
244 destroy_peer (void *cls)
246 struct CadetPeer *cp = cls;
248 cp->destroy_task = NULL;
249 GNUNET_assert (NULL == cp->t);
250 GNUNET_assert (NULL == cp->core_mq);
251 GNUNET_assert (0 == cp->path_dll_length);
252 GNUNET_assert (0 == GNUNET_CONTAINER_multishortmap_size (cp->connections));
253 GNUNET_assert (GNUNET_YES ==
254 GNUNET_CONTAINER_multipeermap_remove (peers,
257 GNUNET_free_non_null (cp->path_heads);
258 GNUNET_free_non_null (cp->path_tails);
259 cp->path_dll_length = 0;
260 if (NULL != cp->search_h)
262 GCD_search_stop (cp->search_h);
265 /* FIXME: clean up search_delayedXXX! */
267 if (NULL != cp->hello_offer)
269 GNUNET_TRANSPORT_offer_hello_cancel (cp->hello_offer);
270 cp->hello_offer = NULL;
272 if (NULL != cp->connectivity_suggestion)
274 GNUNET_ATS_connectivity_suggest_cancel (cp->connectivity_suggestion);
275 cp->connectivity_suggestion = NULL;
277 GNUNET_CONTAINER_multishortmap_destroy (cp->connections);
278 GNUNET_CONTAINER_heap_destroy (cp->path_heap);
279 GNUNET_free_non_null (cp->hello);
280 /* Peer should not be freed if paths exist; if there are no paths,
281 there ought to be no connections, and without connections, no
282 notifications. Thus we can assert that mqm_head is empty at this
284 GNUNET_assert (NULL == cp->mqm_head);
290 * Set the message queue to @a mq for peer @a cp and notify watchers.
292 * @param cp peer to modify
293 * @param mq message queue to set (can be NULL)
296 GCP_set_mq (struct CadetPeer *cp,
297 struct GNUNET_MQ_Handle *mq)
301 for (struct GCP_MessageQueueManager *mqm = cp->mqm_head;
307 if (NULL != mqm->env)
309 GNUNET_MQ_discard (mqm->env);
311 mqm->cb (mqm->cb_cls,
316 mqm->cb (mqm->cb_cls,
322 GNUNET_assert (NULL == mqm->env);
323 mqm->cb (mqm->cb_cls,
331 * Transmit current envelope from this @a mqm.
333 * @param mqm mqm to transmit message for now
336 mqm_execute (struct GCP_MessageQueueManager *mqm)
338 struct CadetPeer *cp = mqm->cp;
340 /* Move entry to the end of the DLL, to be fair. */
341 if (mqm != cp->mqm_tail)
343 GNUNET_CONTAINER_DLL_remove (cp->mqm_head,
346 GNUNET_CONTAINER_DLL_insert_tail (cp->mqm_head,
350 GNUNET_MQ_send (cp->core_mq,
353 cp->mqm_ready_counter--;
358 * Function called when CORE took one of the messages from
359 * a message queue manager and transmitted it.
361 * @param cls the `struct CadetPeeer` where we made progress
364 mqm_send_done (void *cls)
366 struct CadetPeer *cp = cls;
368 if (0 == cp->mqm_ready_counter)
369 return; /* nothing to do */
370 for (struct GCP_MessageQueueManager *mqm = cp->mqm_head;
374 if (NULL == mqm->env)
383 * Send the message in @a env to @a cp.
385 * @param mqm the message queue manager to use for transmission
386 * @param env envelope with the message to send; must NOT
387 * yet have a #GNUNET_MQ_notify_sent() callback attached to it
390 GCP_send (struct GCP_MessageQueueManager *mqm,
391 struct GNUNET_MQ_Envelope *env)
393 struct CadetPeer *cp = mqm->cp;
395 GNUNET_assert (NULL != cp->core_mq);
396 GNUNET_assert (NULL == mqm->env);
397 GNUNET_MQ_notify_sent (env,
401 cp->mqm_ready_counter++;
402 if (0 != GNUNET_MQ_get_length (cp->core_mq))
409 * Function called to destroy a peer now.
412 * @param pid identity of the peer (unused)
413 * @param value the `struct CadetPeer` to clean up
414 * @return #GNUNET_OK (continue to iterate)
417 destroy_iterator_cb (void *cls,
418 const struct GNUNET_PeerIdentity *pid,
421 struct CadetPeer *cp = value;
423 if (NULL != cp->destroy_task)
425 GNUNET_SCHEDULER_cancel (cp->destroy_task);
426 cp->destroy_task = NULL;
434 * Clean up all entries about all peers.
435 * Must only be called after all tunnels, CORE-connections and
436 * connections are down.
439 GCP_destroy_all_peers ()
441 GNUNET_CONTAINER_multipeermap_iterate (peers,
442 &destroy_iterator_cb,
448 * This peer may no longer be needed, consider cleaning it up.
450 * @param cp peer to clean up
453 consider_peer_destroy (struct CadetPeer *cp);
457 * We really no longere care about a peer, stop hogging memory with paths to it.
458 * Afterwards, see if there is more to be cleaned up about this peer.
460 * @param cls a `struct CadetPeer`.
463 drop_paths (void *cls)
465 struct CadetPeer *cp = cls;
466 struct CadetPeerPath *path;
468 cp->destroy_task = NULL;
469 while (NULL != (path = GNUNET_CONTAINER_heap_remove_root (cp->path_heap)))
471 consider_peer_destroy (cp);
476 * This peer may no longer be needed, consider cleaning it up.
478 * @param cp peer to clean up
481 consider_peer_destroy (struct CadetPeer *cp)
483 struct GNUNET_TIME_Relative exp;
485 if (NULL != cp->destroy_task)
487 GNUNET_SCHEDULER_cancel (cp->destroy_task);
488 cp->destroy_task = NULL;
491 return; /* still relevant! */
492 if (NULL != cp->core_mq)
493 return; /* still relevant! */
494 if (0 != GNUNET_CONTAINER_multishortmap_size (cp->connections))
495 return; /* still relevant! */
496 if (0 < GNUNET_CONTAINER_heap_get_size (cp->path_heap))
498 cp->destroy_task = GNUNET_SCHEDULER_add_delayed (IDLE_PATH_TIMEOUT,
503 if (0 < cp->path_dll_length)
504 return; /* still relevant! */
505 if (NULL != cp->hello)
507 /* relevant only until HELLO expires */
508 exp = GNUNET_TIME_absolute_get_remaining (GNUNET_HELLO_get_last_expiration (cp->hello));
509 cp->destroy_task = GNUNET_SCHEDULER_add_delayed (exp,
514 cp->destroy_task = GNUNET_SCHEDULER_add_delayed (IDLE_PEER_TIMEOUT,
521 * Add an entry to the DLL of all of the paths that this peer is on.
523 * @param cp peer to modify
524 * @param entry an entry on a path
525 * @param off offset of this peer on the path
528 GCP_path_entry_add (struct CadetPeer *cp,
529 struct CadetPeerPathEntry *entry,
532 if (off >= cp->path_dll_length)
534 unsigned int len = cp->path_dll_length;
536 GNUNET_array_grow (cp->path_heads,
539 GNUNET_array_grow (cp->path_tails,
543 GNUNET_CONTAINER_DLL_insert (cp->path_heads[off],
548 /* If we have a tunnel to this peer, tell the tunnel that there is a
549 new path available. */
551 GCT_consider_path (cp->t,
558 * Remove an entry from the DLL of all of the paths that this peer is on.
560 * @param cp peer to modify
561 * @param entry an entry on a path
562 * @param off offset of this peer on the path
565 GCP_path_entry_remove (struct CadetPeer *cp,
566 struct CadetPeerPathEntry *entry,
569 GNUNET_CONTAINER_DLL_remove (cp->path_heads[off],
572 GNUNET_assert (0 < cp->num_paths);
578 * Try adding a @a path to this @a peer. If the peer already
579 * has plenty of paths, return NULL.
581 * @param cp peer to which the @a path leads to
582 * @param path a path looking for an owner; may not be fully initialized yet!
583 * @param off offset of @a cp in @a path
584 * @return NULL if this peer does not care to become a new owner,
585 * otherwise the node in the peer's path heap for the @a path.
587 struct GNUNET_CONTAINER_HeapNode *
588 GCP_attach_path (struct CadetPeer *cp,
589 struct CadetPeerPath *path,
592 GNUNET_CONTAINER_HeapCostType desirability;
593 struct CadetPeerPath *root;
594 GNUNET_CONTAINER_HeapCostType root_desirability;
595 struct GNUNET_CONTAINER_HeapNode *hn;
597 /* FIXME: desirability is not yet initialized; tricky! */
598 desirability = GCPP_get_desirability (path);
600 GNUNET_CONTAINER_heap_peek2 (cp->path_heap,
605 root_desirability = 0;
608 if ( (DESIRED_CONNECTIONS_PER_TUNNEL > cp->num_paths) &&
609 (desirability < root_desirability) )
612 /* Yes, we'd like to add this path, add to our heap */
613 hn = GNUNET_CONTAINER_heap_insert (cp->path_heap,
617 /* Consider maybe dropping other paths because of the new one */
618 if (GNUNET_CONTAINER_heap_get_size (cp->path_heap) >=
619 2 * DESIRED_CONNECTIONS_PER_TUNNEL)
621 /* Now we have way too many, drop least desirable UNLESS it is in use!
622 (Note that this intentionally keeps highly desireable, but currently
623 unused paths around in the hope that we might be able to switch, even
624 if the number of paths exceeds the threshold.) */
625 root = GNUNET_CONTAINER_heap_peek (cp->path_heap);
627 GCPP_get_connection (root,
629 GCPP_get_length (root) - 1))
631 /* Got plenty of paths to this destination, and this is a low-quality
632 one that we don't care, allow it to die. */
633 GNUNET_assert (root ==
634 GNUNET_CONTAINER_heap_remove_root (cp->path_heap));
643 * This peer can no longer own @a path as the path
644 * has been extended and a peer further down the line
645 * is now the new owner.
647 * @param cp old owner of the @a path
648 * @param path path where the ownership is lost
649 * @param hn note in @a cp's path heap that must be deleted
652 GCP_detach_path (struct CadetPeer *cp,
653 struct CadetPeerPath *path,
654 struct GNUNET_CONTAINER_HeapNode *hn)
656 GNUNET_assert (path ==
657 GNUNET_CONTAINER_heap_remove_node (hn));
662 * Add a @a connection to this @a cp.
664 * @param cp peer via which the @a connection goes
665 * @param cc the connection to add
668 GCP_add_connection (struct CadetPeer *cp,
669 struct CadetConnection *cc)
671 GNUNET_assert (GNUNET_OK ==
672 GNUNET_CONTAINER_multishortmap_put (cp->connections,
673 &GCC_get_id (cc)->connection_of_tunnel,
675 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
680 * Remove a @a connection that went via this @a cp.
682 * @param cp peer via which the @a connection went
683 * @param cc the connection to remove
686 GCP_remove_connection (struct CadetPeer *cp,
687 struct CadetConnection *cc)
689 GNUNET_assert (GNUNET_YES ==
690 GNUNET_CONTAINER_multishortmap_remove (cp->connections,
691 &GCC_get_id (cc)->connection_of_tunnel,
697 * This peer is now on more "active" duty, activate processes related to it.
699 * @param cp the more-active peer
702 consider_peer_activate (struct CadetPeer *cp)
706 if (NULL != cp->destroy_task)
708 /* It's active, do not destory! */
709 GNUNET_SCHEDULER_cancel (cp->destroy_task);
710 cp->destroy_task = NULL;
712 if ( (0 == GNUNET_CONTAINER_multishortmap_size (cp->connections)) &&
715 /* We're just on a path or directly connected; don't bother too much */
716 if (NULL != cp->connectivity_suggestion)
718 GNUNET_ATS_connectivity_suggest_cancel (cp->connectivity_suggestion);
719 cp->connectivity_suggestion = NULL;
721 if (NULL != cp->search_h)
723 GCD_search_stop (cp->search_h);
728 if (NULL == cp->core_mq)
730 /* Lacks direct connection, try to create one by querying the DHT */
731 if ( (NULL == cp->search_h) &&
732 (DESIRED_CONNECTIONS_PER_TUNNEL < cp->num_paths) )
734 = GCD_search (&cp->pid);
738 /* Have direct connection, stop DHT search if active */
739 if (NULL != cp->search_h)
741 GCD_search_stop (cp->search_h);
746 /* If we have a tunnel, our urge for connections is much bigger */
747 strength = (NULL != cp->t) ? 32 : 1;
748 if (NULL != cp->connectivity_suggestion)
749 GNUNET_ATS_connectivity_suggest_cancel (cp->connectivity_suggestion);
750 cp->connectivity_suggestion
751 = GNUNET_ATS_connectivity_suggest (ats_ch,
758 * Retrieve the CadetPeer stucture associated with the
759 * peer. Optionally create one and insert it in the appropriate
760 * structures if the peer is not known yet.
762 * @param peer_id Full identity of the peer.
763 * @param create #GNUNET_YES if a new peer should be created if unknown.
764 * #GNUNET_NO to return NULL if peer is unknown.
765 * @return Existing or newly created peer structure.
766 * NULL if unknown and not requested @a create
769 GCP_get (const struct GNUNET_PeerIdentity *peer_id,
772 struct CadetPeer *cp;
774 cp = GNUNET_CONTAINER_multipeermap_get (peers,
778 if (GNUNET_NO == create)
780 cp = GNUNET_new (struct CadetPeer);
782 cp->connections = GNUNET_CONTAINER_multishortmap_create (32,
784 cp->path_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
785 GNUNET_assert (GNUNET_YES ==
786 GNUNET_CONTAINER_multipeermap_put (peers,
789 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
795 * Obtain the peer identity for a `struct CadetPeer`.
797 * @param cp our peer handle
798 * @return the peer identity
800 const struct GNUNET_PeerIdentity *
801 GCP_get_id (struct CadetPeer *cp)
808 * Iterate over all known peers.
810 * @param iter Iterator.
811 * @param cls Closure for @c iter.
814 GCP_iterate_all (GNUNET_CONTAINER_PeerMapIterator iter,
817 GNUNET_CONTAINER_multipeermap_iterate (peers,
824 * Count the number of known paths toward the peer.
826 * @param peer Peer to get path info.
827 * @return Number of known paths.
830 GCP_count_paths (const struct CadetPeer *peer)
832 return peer->num_paths;
837 * Iterate over the paths to a peer.
839 * @param peer Peer to get path info.
840 * @param callback Function to call for every path.
841 * @param callback_cls Closure for @a callback.
842 * @return Number of iterated paths.
845 GCP_iterate_paths (struct CadetPeer *peer,
846 GCP_PathIterator callback,
849 unsigned int ret = 0;
851 for (unsigned int i=0;i<peer->path_dll_length;i++)
853 for (struct CadetPeerPathEntry *pe = peer->path_heads[i];
858 callback (callback_cls,
870 * Iterate over the paths to @a peer where
871 * @a peer is at distance @a dist from us.
873 * @param peer Peer to get path info.
874 * @param dist desired distance of @a peer to us on the path
875 * @param callback Function to call for every path.
876 * @param callback_cls Closure for @a callback.
877 * @return Number of iterated paths.
880 GCP_iterate_paths_at (struct CadetPeer *peer,
882 GCP_PathIterator callback,
885 unsigned int ret = 0;
887 if (dist<peer->path_dll_length)
889 for (struct CadetPeerPathEntry *pe = peer->path_heads[dist];
894 callback (callback_cls,
905 * Get the tunnel towards a peer.
907 * @param peer Peer to get from.
908 * @param create #GNUNET_YES to create a tunnel if we do not have one
909 * @return Tunnel towards peer.
912 GCP_get_tunnel (struct CadetPeer *peer,
917 if ( (NULL != peer->t) ||
918 (GNUNET_NO == create) )
920 peer->t = GCT_create_tunnel (peer);
921 consider_peer_activate (peer);
927 * We got a HELLO for a @a peer, remember it, and possibly
928 * trigger adequate actions (like trying to connect).
930 * @param peer the peer we got a HELLO for
931 * @param hello the HELLO to remember
934 GCP_set_hello (struct CadetPeer *peer,
935 const struct GNUNET_HELLO_Message *hello)
937 /* FIXME: keep HELLO, possibly offer to TRANSPORT... */
939 consider_peer_destroy (peer);
944 * The tunnel to the given peer no longer exists, remove it from our
945 * data structures, and possibly clean up the peer itself.
947 * @param peer the peer affected
948 * @param t the dead tunnel
951 GCP_drop_tunnel (struct CadetPeer *peer,
952 struct CadetTunnel *t)
954 GNUNET_assert (peer->t == t);
956 consider_peer_destroy (peer);
961 * Test if @a cp has a core-level connection
963 * @param cp peer to test
964 * @return #GNUNET_YES if @a cp has a core-level connection
967 GCP_has_core_connection (struct CadetPeer *cp)
969 return (NULL != cp->core_mq) ? GNUNET_YES : GNUNET_NO;
974 * Start message queue change notifications.
976 * @param cp peer to notify for
977 * @param cb function to call if mq becomes available or unavailable
978 * @param cb_cls closure for @a cb
979 * @return handle to cancel request
981 struct GCP_MessageQueueManager *
982 GCP_request_mq (struct CadetPeer *cp,
983 GCP_MessageQueueNotificationCallback cb,
986 struct GCP_MessageQueueManager *mqm;
988 mqm = GNUNET_new (struct GCP_MessageQueueManager);
990 mqm->cb_cls = cb_cls;
992 GNUNET_CONTAINER_DLL_insert (cp->mqm_head,
995 if (NULL != cp->core_mq)
1003 * Stops message queue change notifications.
1005 * @param mqm handle matching request to cancel
1006 * @param last_env final message to transmit, or NULL
1009 GCP_request_mq_cancel (struct GCP_MessageQueueManager *mqm,
1010 struct GNUNET_MQ_Envelope *last_env)
1012 struct CadetPeer *cp = mqm->cp;
1014 if (NULL != mqm->env)
1015 GNUNET_MQ_discard (mqm->env);
1016 if (NULL != last_env)
1018 if (NULL != cp->core_mq)
1019 GNUNET_MQ_send (cp->core_mq,
1022 GNUNET_MQ_discard (last_env);
1024 GNUNET_CONTAINER_DLL_remove (cp->mqm_head,
1032 * Send the message in @a env to @a cp, overriding queueing logic.
1033 * This function should only be used to send error messages outside
1034 * of flow and congestion control, similar to ICMP. Note that
1035 * the envelope may be silently discarded as well.
1037 * @param cp peer to send the message to
1038 * @param env envelope with the message to send
1041 GCP_send_ooo (struct CadetPeer *cp,
1042 struct GNUNET_MQ_Envelope *env)
1044 if (NULL == cp->core_mq)
1046 GNUNET_MQ_discard (env);
1049 GNUNET_MQ_send (cp->core_mq,
1056 /* end of gnunet-service-cadet-new_peer.c */