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 * Get the message queue for peer @a cp.
270 * @param cp peer to modify
271 * @return message queue (can be NULL)
273 struct GNUNET_MQ_Handle *
274 GCP_get_mq (struct CadetPeer *cp)
281 * Set the message queue to @a mq for peer @a cp and notify watchers.
283 * @param cp peer to modify
284 * @param mq message queue to set (can be NULL)
287 GCP_set_mq (struct CadetPeer *cp,
288 struct GNUNET_MQ_Handle *mq)
291 for (struct GCP_MessageQueueManager *mqm = cp->mqm_head;
294 mqm->cb (mqm->cb_cls,
300 * Send the message in @a env to @a cp.
303 * @param env envelope with the message to send
306 GCP_send (struct CadetPeer *cp,
307 struct GNUNET_MQ_Envelope *env)
309 GNUNET_assert (NULL != cp->core_mq);
310 GNUNET_MQ_send (cp->core_mq,
316 * Function called to destroy a peer now.
319 * @param pid identity of the peer (unused)
320 * @param value the `struct CadetPeer` to clean up
321 * @return #GNUNET_OK (continue to iterate)
324 destroy_iterator_cb (void *cls,
325 const struct GNUNET_PeerIdentity *pid,
328 struct CadetPeer *cp = value;
330 if (NULL != cp->destroy_task)
332 GNUNET_SCHEDULER_cancel (cp->destroy_task);
333 cp->destroy_task = NULL;
341 * Clean up all entries about all peers.
342 * Must only be called after all tunnels, CORE-connections and
343 * connections are down.
346 GCP_destroy_all_peers ()
348 GNUNET_CONTAINER_multipeermap_iterate (peers,
349 &destroy_iterator_cb,
355 * This peer may no longer be needed, consider cleaning it up.
357 * @param cp peer to clean up
360 consider_peer_destroy (struct CadetPeer *cp);
364 * We really no longere care about a peer, stop hogging memory with paths to it.
365 * Afterwards, see if there is more to be cleaned up about this peer.
367 * @param cls a `struct CadetPeer`.
370 drop_paths (void *cls)
372 struct CadetPeer *cp = cls;
373 struct CadetPeerPath *path;
375 cp->destroy_task = NULL;
376 while (NULL != (path = GNUNET_CONTAINER_heap_remove_root (cp->path_heap)))
378 consider_peer_destroy (cp);
383 * This peer may no longer be needed, consider cleaning it up.
385 * @param cp peer to clean up
388 consider_peer_destroy (struct CadetPeer *cp)
390 struct GNUNET_TIME_Relative exp;
392 if (NULL != cp->destroy_task)
394 GNUNET_SCHEDULER_cancel (cp->destroy_task);
395 cp->destroy_task = NULL;
398 return; /* still relevant! */
399 if (NULL != cp->core_mq)
400 return; /* still relevant! */
401 if (0 != GNUNET_CONTAINER_multishortmap_size (cp->connections))
402 return; /* still relevant! */
403 if (0 < GNUNET_CONTAINER_heap_get_size (cp->path_heap))
405 cp->destroy_task = GNUNET_SCHEDULER_add_delayed (IDLE_PATH_TIMEOUT,
410 if (0 < cp->path_dll_length)
411 return; /* still relevant! */
412 if (NULL != cp->hello)
414 /* relevant only until HELLO expires */
415 exp = GNUNET_TIME_absolute_get_remaining (GNUNET_HELLO_get_last_expiration (cp->hello));
416 cp->destroy_task = GNUNET_SCHEDULER_add_delayed (exp,
421 cp->destroy_task = GNUNET_SCHEDULER_add_delayed (IDLE_PEER_TIMEOUT,
428 * Add an entry to the DLL of all of the paths that this peer is on.
430 * @param cp peer to modify
431 * @param entry an entry on a path
432 * @param off offset of this peer on the path
435 GCP_path_entry_add (struct CadetPeer *cp,
436 struct CadetPeerPathEntry *entry,
439 if (off >= cp->path_dll_length)
441 unsigned int len = cp->path_dll_length;
443 GNUNET_array_grow (cp->path_heads,
446 GNUNET_array_grow (cp->path_tails,
450 GNUNET_CONTAINER_DLL_insert (cp->path_heads[off],
455 /* If we have a tunnel to this peer, tell the tunnel that there is a
456 new path available. */
458 GCT_consider_path (cp->t,
465 * Remove an entry from the DLL of all of the paths that this peer is on.
467 * @param cp peer to modify
468 * @param entry an entry on a path
469 * @param off offset of this peer on the path
472 GCP_path_entry_remove (struct CadetPeer *cp,
473 struct CadetPeerPathEntry *entry,
476 GNUNET_CONTAINER_DLL_remove (cp->path_heads[off],
479 GNUNET_assert (0 < cp->num_paths);
485 * Try adding a @a path to this @a peer. If the peer already
486 * has plenty of paths, return NULL.
488 * @param cp peer to which the @a path leads to
489 * @param path a path looking for an owner; may not be fully initialized yet!
490 * @param off offset of @a cp in @a path
491 * @return NULL if this peer does not care to become a new owner,
492 * otherwise the node in the peer's path heap for the @a path.
494 struct GNUNET_CONTAINER_HeapNode *
495 GCP_attach_path (struct CadetPeer *cp,
496 struct CadetPeerPath *path,
499 GNUNET_CONTAINER_HeapCostType desirability;
500 struct CadetPeerPath *root;
501 GNUNET_CONTAINER_HeapCostType root_desirability;
502 struct GNUNET_CONTAINER_HeapNode *hn;
504 /* FIXME: desirability is not yet initialized; tricky! */
505 desirability = GCPP_get_desirability (path);
507 GNUNET_CONTAINER_heap_peek2 (cp->path_heap,
512 root_desirability = 0;
515 if ( (DESIRED_CONNECTIONS_PER_TUNNEL > cp->num_paths) &&
516 (desirability < root_desirability) )
519 /* Yes, we'd like to add this path, add to our heap */
520 hn = GNUNET_CONTAINER_heap_insert (cp->path_heap,
524 /* Consider maybe dropping other paths because of the new one */
525 if (GNUNET_CONTAINER_heap_get_size (cp->path_heap) >=
526 2 * DESIRED_CONNECTIONS_PER_TUNNEL)
528 /* Now we have way too many, drop least desirable UNLESS it is in use!
529 (Note that this intentionally keeps highly desireable, but currently
530 unused paths around in the hope that we might be able to switch, even
531 if the number of paths exceeds the threshold.) */
532 root = GNUNET_CONTAINER_heap_peek (cp->path_heap);
534 GCPP_get_connection (root,
536 GCPP_get_length (root) - 1))
538 /* Got plenty of paths to this destination, and this is a low-quality
539 one that we don't care, allow it to die. */
540 GNUNET_assert (root ==
541 GNUNET_CONTAINER_heap_remove_root (cp->path_heap));
550 * This peer can no longer own @a path as the path
551 * has been extended and a peer further down the line
552 * is now the new owner.
554 * @param cp old owner of the @a path
555 * @param path path where the ownership is lost
556 * @param hn note in @a cp's path heap that must be deleted
559 GCP_detach_path (struct CadetPeer *cp,
560 struct CadetPeerPath *path,
561 struct GNUNET_CONTAINER_HeapNode *hn)
563 GNUNET_assert (path ==
564 GNUNET_CONTAINER_heap_remove_node (hn));
569 * Add a @a connection to this @a cp.
571 * @param cp peer via which the @a connection goes
572 * @param cc the connection to add
575 GCP_add_connection (struct CadetPeer *cp,
576 struct CadetConnection *cc)
578 GNUNET_assert (GNUNET_OK ==
579 GNUNET_CONTAINER_multishortmap_put (cp->connections,
580 &GCC_get_id (cc)->connection_of_tunnel,
582 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
587 * Remove a @a connection that went via this @a cp.
589 * @param cp peer via which the @a connection went
590 * @param cc the connection to remove
593 GCP_remove_connection (struct CadetPeer *cp,
594 struct CadetConnection *cc)
596 GNUNET_assert (GNUNET_YES ==
597 GNUNET_CONTAINER_multishortmap_remove (cp->connections,
598 &GCC_get_id (cc)->connection_of_tunnel,
604 * This peer is now on more "active" duty, activate processes related to it.
606 * @param cp the more-active peer
609 consider_peer_activate (struct CadetPeer *cp)
613 if (NULL != cp->destroy_task)
615 /* It's active, do not destory! */
616 GNUNET_SCHEDULER_cancel (cp->destroy_task);
617 cp->destroy_task = NULL;
619 if ( (0 == GNUNET_CONTAINER_multishortmap_size (cp->connections)) &&
622 /* We're just on a path or directly connected; don't bother too much */
623 if (NULL != cp->connectivity_suggestion)
625 GNUNET_ATS_connectivity_suggest_cancel (cp->connectivity_suggestion);
626 cp->connectivity_suggestion = NULL;
628 if (NULL != cp->search_h)
630 GCD_search_stop (cp->search_h);
635 if (NULL == cp->core_mq)
637 /* Lacks direct connection, try to create one by querying the DHT */
638 if ( (NULL == cp->search_h) &&
639 (DESIRED_CONNECTIONS_PER_TUNNEL < cp->num_paths) )
641 = GCD_search (&cp->pid);
645 /* Have direct connection, stop DHT search if active */
646 if (NULL != cp->search_h)
648 GCD_search_stop (cp->search_h);
653 /* If we have a tunnel, our urge for connections is much bigger */
654 strength = (NULL != cp->t) ? 32 : 1;
655 if (NULL != cp->connectivity_suggestion)
656 GNUNET_ATS_connectivity_suggest_cancel (cp->connectivity_suggestion);
657 cp->connectivity_suggestion
658 = GNUNET_ATS_connectivity_suggest (ats_ch,
665 * Retrieve the CadetPeer stucture associated with the
666 * peer. Optionally create one and insert it in the appropriate
667 * structures if the peer is not known yet.
669 * @param peer_id Full identity of the peer.
670 * @param create #GNUNET_YES if a new peer should be created if unknown.
671 * #GNUNET_NO to return NULL if peer is unknown.
672 * @return Existing or newly created peer structure.
673 * NULL if unknown and not requested @a create
676 GCP_get (const struct GNUNET_PeerIdentity *peer_id,
679 struct CadetPeer *cp;
681 cp = GNUNET_CONTAINER_multipeermap_get (peers,
685 if (GNUNET_NO == create)
687 cp = GNUNET_new (struct CadetPeer);
689 cp->connections = GNUNET_CONTAINER_multishortmap_create (32,
691 cp->path_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
692 GNUNET_assert (GNUNET_YES ==
693 GNUNET_CONTAINER_multipeermap_put (peers,
696 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
702 * Obtain the peer identity for a `struct CadetPeer`.
704 * @param cp our peer handle
705 * @return the peer identity
707 const struct GNUNET_PeerIdentity *
708 GCP_get_id (struct CadetPeer *cp)
715 * Iterate over all known peers.
717 * @param iter Iterator.
718 * @param cls Closure for @c iter.
721 GCP_iterate_all (GNUNET_CONTAINER_PeerMapIterator iter,
724 GNUNET_CONTAINER_multipeermap_iterate (peers,
731 * Count the number of known paths toward the peer.
733 * @param peer Peer to get path info.
734 * @return Number of known paths.
737 GCP_count_paths (const struct CadetPeer *peer)
739 return peer->num_paths;
744 * Iterate over the paths to a peer.
746 * @param peer Peer to get path info.
747 * @param callback Function to call for every path.
748 * @param callback_cls Closure for @a callback.
749 * @return Number of iterated paths.
752 GCP_iterate_paths (struct CadetPeer *peer,
753 GCP_PathIterator callback,
756 unsigned int ret = 0;
758 for (unsigned int i=0;i<peer->path_dll_length;i++)
760 for (struct CadetPeerPathEntry *pe = peer->path_heads[i];
765 callback (callback_cls,
777 * Iterate over the paths to @a peer where
778 * @a peer is at distance @a dist from us.
780 * @param peer Peer to get path info.
781 * @param dist desired distance of @a peer to us on the path
782 * @param callback Function to call for every path.
783 * @param callback_cls Closure for @a callback.
784 * @return Number of iterated paths.
787 GCP_iterate_paths_at (struct CadetPeer *peer,
789 GCP_PathIterator callback,
792 unsigned int ret = 0;
794 if (dist<peer->path_dll_length)
796 for (struct CadetPeerPathEntry *pe = peer->path_heads[dist];
801 callback (callback_cls,
812 * Get the tunnel towards a peer.
814 * @param peer Peer to get from.
815 * @param create #GNUNET_YES to create a tunnel if we do not have one
816 * @return Tunnel towards peer.
819 GCP_get_tunnel (struct CadetPeer *peer,
824 if ( (NULL != peer->t) ||
825 (GNUNET_NO == create) )
827 peer->t = GCT_create_tunnel (peer);
828 consider_peer_activate (peer);
834 * We got a HELLO for a @a peer, remember it, and possibly
835 * trigger adequate actions (like trying to connect).
837 * @param peer the peer we got a HELLO for
838 * @param hello the HELLO to remember
841 GCP_set_hello (struct CadetPeer *peer,
842 const struct GNUNET_HELLO_Message *hello)
844 /* FIXME: keep HELLO, possibly offer to TRANSPORT... */
846 consider_peer_destroy (peer);
851 * The tunnel to the given peer no longer exists, remove it from our
852 * data structures, and possibly clean up the peer itself.
854 * @param peer the peer affected
855 * @param t the dead tunnel
858 GCP_drop_tunnel (struct CadetPeer *peer,
859 struct CadetTunnel *t)
861 GNUNET_assert (peer->t == t);
863 consider_peer_destroy (peer);
868 * Start message queue change notifications.
870 * @param cp peer to notify for
871 * @param cb function to call if mq becomes available or unavailable
872 * @param cb_cls closure for @a cb
873 * @return handle to cancel request
875 struct GCP_MessageQueueManager *
876 GCP_request_mq (struct CadetPeer *cp,
877 GCP_MessageQueueNotificationCallback cb,
880 struct GCP_MessageQueueManager *mqm;
882 mqm = GNUNET_new (struct GCP_MessageQueueManager);
884 mqm->cb_cls = cb_cls;
886 GNUNET_CONTAINER_DLL_insert (cp->mqm_head,
889 if (NULL != cp->core_mq)
897 * Stops message queue change notifications.
899 * @param mqm handle matching request to cancel
902 GCP_request_mq_cancel (struct GCP_MessageQueueManager *mqm)
904 struct CadetPeer *cp = mqm->cp;
906 GNUNET_CONTAINER_DLL_remove (cp->mqm_head,
914 /* end of gnunet-service-cadet-new_peer.c */