2 This file is part of GNUnet.
3 Copyright (C) 2009-2016 GNUnet e.V.
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
21 * @file dht/gnunet-service-wdht_neighbours.c
22 * @brief GNUnet DHT service's finger and friend table management code
23 * @author Supriti Singh
24 * @author Christian Grothoff
25 * @author Arthur Dewarumez
28 * - initiate finding of successors
31 #include "gnunet_util_lib.h"
32 #include "gnunet_block_lib.h"
33 #include "gnunet_hello_lib.h"
34 #include "gnunet_constants.h"
35 #include "gnunet_protocols.h"
36 #include "gnunet_ats_service.h"
37 #include "gnunet_core_service.h"
38 #include "gnunet_datacache_lib.h"
39 #include "gnunet_transport_service.h"
40 #include "gnunet_dht_service.h"
41 #include "gnunet_statistics_service.h"
42 #include "gnunet-service-dht.h"
43 #include "gnunet-service-dht_datacache.h"
44 #include "gnunet-service-dht_neighbours.h"
45 #include "gnunet-service-dht_nse.h"
49 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
52 * Trail timeout. After what time do trails always die?
54 #define TRAIL_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 42)
57 * Random walk delay. How often do we walk the overlay?
59 #define RANDOM_WALK_DELAY GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 42)
62 * The number of layered ID to use.
64 #define NUMBER_LAYERED_ID 8
67 * The number of random walk to launch at the beginning of the initialization
69 /* FIXME: find a better value */
70 #define NUMBER_RANDOM_WALK 20
73 /******************* The db structure and related functions *******************/
76 * Entry in #friends_peermap.
86 * Information we keep per trail.
92 * Identifier of the trail with the predecessor.
94 struct GNUNET_HashCode pred_id;
97 * Identifier of the trail with the successor.
99 struct GNUNET_HashCode succ_id;
102 * When does this trail expire.
104 struct GNUNET_TIME_Absolute expiration_time;
107 * MDLL entry in the list of all trails with the same predecessor.
109 struct Trail *prev_succ;
112 * MDLL entry in the list of all trails with the same predecessor.
114 struct Trail *next_succ;
117 * MDLL entry in the list of all trails with the same predecessor.
119 struct Trail *prev_pred;
122 * MDLL entry in the list of all trails with the same predecessor.
124 struct Trail *next_pred;
127 * Our predecessor in the trail, NULL if we are initiator (?).
129 struct FriendInfo *pred;
132 * Our successor in the trail, NULL if we are the last peer.
134 struct FriendInfo *succ;
137 * Location of this trail in the heap.
139 struct GNUNET_CONTAINER_HeapNode *hn;
142 * If this peer started the to create a Finger (and thus @e pred is
143 * NULL), this is the finger table of the finger we are trying to
146 struct FingerTable *ft;
149 * If this peer started the trail to create a Finger (and thus @e
150 * pred is NULL), this is the offset of the finger we are trying to
151 * intialize in the unsorted array.
153 unsigned int finger_off;
159 * Entry in #friends_peermap.
166 const struct GNUNET_PeerIdentity *id;
171 struct Trail *pred_head;
176 struct Trail *pred_tail;
181 struct Trail *succ_head;
186 struct Trail *succ_tail;
189 * Core handle for sending messages to this friend.
191 struct GNUNET_MQ_Handle *mq;
209 struct FingerTable *ft;
214 struct GNUNET_HashCode destination;
217 * #GNUNET_YES if a response has been received. Otherwise #GNUNET_NO.
226 * Array of our fingers, unsorted.
228 struct Finger **fingers;
231 * Size of the finger array.
233 unsigned int finger_array_size;
236 * Number of valid entries in @e fingers
238 unsigned int number_valid_fingers;
241 * Which offset in @e fingers will we redo next.
243 unsigned int walk_offset;
246 * Is the finger array sorted?
253 /*********************** end of the db structure part ***********************/
256 GNUNET_NETWORK_STRUCT_BEGIN
259 * Setup a finger using the underlay topology ("social network").
261 struct RandomWalkMessage
264 * Type: #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK
266 struct GNUNET_MessageHeader header;
269 * Number of hops this message has taken so far, we stop at
272 uint16_t hops_taken GNUNET_PACKED;
275 * Layer for the request, in NBO.
277 uint16_t layer GNUNET_PACKED;
280 * Unique (random) identifier this peer will use to
281 * identify the trail (in future messages).
283 struct GNUNET_HashCode trail_id;
288 * Response to a `struct RandomWalkMessage`.
290 struct RandomWalkResponseMessage
293 * Type: #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE
295 struct GNUNET_MessageHeader header;
298 * Zero, for alignment.
300 uint32_t reserved GNUNET_PACKED;
303 * Unique (random) identifier from the
304 * `struct RandomWalkMessage`.
306 struct GNUNET_HashCode trail_id;
309 * Random location in the respective layer where the
310 * random path of the finger setup terminated.
312 struct GNUNET_HashCode location;
317 * Response to an event that causes a trail to die.
319 struct TrailDestroyMessage
322 * Type: #GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY
324 struct GNUNET_MessageHeader header;
327 * Zero, for alignment.
329 uint32_t reserved GNUNET_PACKED;
332 * Unique (random) identifier this peer will use to
333 * identify the finger (in future messages).
335 struct GNUNET_HashCode trail_id;
341 * Send a message along a trail.
343 struct FindSuccessorMessage
346 * Type: #GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND
348 struct GNUNET_MessageHeader header;
351 * Zero, for alignment.
353 uint32_t reserved GNUNET_PACKED;
356 * Key for which we would like close values returned.
357 * identify the finger (in future messages).
359 struct GNUNET_HashCode key;
365 * Send a message along a trail.
367 struct TrailRouteMessage
370 * Type: #GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE
372 struct GNUNET_MessageHeader header;
375 * #GNUNET_YES if the path should be recorded, #GNUNET_NO if not; in NBO.
377 uint16_t record_path GNUNET_PACKED;
380 * Length of the recorded trail, 0 if @e record_path is #GNUNET_NO; in NBO.
382 uint16_t path_length GNUNET_PACKED;
385 * Unique (random) identifier this peer will use to
386 * identify the finger (in future messages).
388 struct GNUNET_HashCode trail_id;
391 * Path the message has taken so far (excluding sender).
393 /* struct GNUNET_PeerIdentity path[path_length]; */
395 /* followed by payload (another `struct GNUNET_MessageHeader`) to
396 send along the trail */
403 struct PeerPutMessage
406 * Type: #GNUNET_MESSAGE_TYPE_WDHT_PUT
408 struct GNUNET_MessageHeader header;
413 uint32_t options GNUNET_PACKED;
418 uint32_t block_type GNUNET_PACKED;
423 uint32_t hop_count GNUNET_PACKED;
426 * Replication level for this message
427 * In the current implementation, this value is not used.
429 uint32_t desired_replication_level GNUNET_PACKED;
432 * Length of the PUT path that follows (if tracked).
434 uint32_t put_path_length GNUNET_PACKED;
437 * When does the content expire?
439 struct GNUNET_TIME_AbsoluteNBO expiration_time;
442 * The key to store the value under.
444 struct GNUNET_HashCode key GNUNET_PACKED;
446 /* put path (if tracked) */
455 struct PeerGetMessage
458 * Type: #GNUNET_MESSAGE_TYPE_WDHT_GET
460 struct GNUNET_MessageHeader header;
465 uint32_t options GNUNET_PACKED;
468 * Desired content type.
470 uint32_t block_type GNUNET_PACKED;
475 uint32_t hop_count GNUNET_PACKED;
478 * Desired replication level for this request.
479 * In the current implementation, this value is not used.
481 uint32_t desired_replication_level GNUNET_PACKED;
484 * Total number of peers in get path.
486 unsigned int get_path_length;
489 * The key we are looking for.
491 struct GNUNET_HashCode key;
494 /* struct GNUNET_PeerIdentity[]*/
501 struct PeerGetResultMessage
504 * Type: #GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT
506 struct GNUNET_MessageHeader header;
509 * The type for the data in NBO.
511 uint32_t type GNUNET_PACKED;
514 * Number of peers recorded in the outgoing path from source to the
515 * stored location of this message.
517 uint32_t put_path_length GNUNET_PACKED;
520 * When does the content expire?
522 struct GNUNET_TIME_AbsoluteNBO expiration_time;
525 * The key of the corresponding GET request.
527 struct GNUNET_HashCode key;
529 /* put path (if tracked) */
535 GNUNET_NETWORK_STRUCT_END
539 * Contains all the layered IDs of this peer.
541 struct GNUNET_PeerIdentity layered_id[NUMBER_LAYERED_ID];
544 * Task to timeout trails that have expired.
546 static struct GNUNET_SCHEDULER_Task *trail_timeout_task;
549 * Task to perform random walks.
551 static struct GNUNET_SCHEDULER_Task *random_walk_task;
554 * Identity of this peer.
556 static struct GNUNET_PeerIdentity my_identity;
559 * Peer map of all the friends of a peer
561 static struct GNUNET_CONTAINER_MultiPeerMap *friends_peermap;
566 static struct FingerTable fingers[NUMBER_LAYERED_ID];
569 * Tail map, mapping tail identifiers to `struct Trail`s
571 static struct GNUNET_CONTAINER_MultiHashMap *trail_map;
574 * Tail heap, organizing trails by expiration time.
576 static struct GNUNET_CONTAINER_Heap *trail_heap;
581 static struct GNUNET_CORE_Handle *core_api;
585 * Handle the put request from the client.
587 * @param block_type Type of the block
588 * @param options routing options
589 * @param desired_replication_level desired replication level
590 * @param expiration_time when does the content expire
591 * @param hop_count how many hops has this message traversed so far
592 * @param bf Bloom filter of peers this PUT has already traversed
593 * @param key key for the content
594 * @param put_path_length number of entries in put_path
595 * @param put_path peers this request has traversed so far (if tracked)
596 * @param data payload to store
597 * @param data_size number of bytes in data
598 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
601 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type block_type,
602 enum GNUNET_DHT_RouteOption options,
603 uint32_t desired_replication_level,
604 struct GNUNET_TIME_Absolute expiration_time,
606 struct GNUNET_CONTAINER_BloomFilter *bf,
607 const struct GNUNET_HashCode *key,
608 unsigned int put_path_length,
609 struct GNUNET_PeerIdentity *put_path,
613 GDS_DATACACHE_handle_put (expiration_time,
619 GDS_CLIENTS_process_put (options,
622 desired_replication_level,
623 put_path_length, put_path,
628 return GNUNET_OK; /* FIXME... */
633 * Perform a GET operation. Forwards the given request to other
634 * peers. Does not lookup the key locally. May do nothing if this is
635 * the only peer in the network (or if we are the closest peer in the
638 * @param type type of the block
639 * @param options routing options
640 * @param desired_replication_level desired replication count
641 * @param hop_count how many hops did this request traverse so far?
642 * @param key key for the content
643 * @param xquery extended query
644 * @param xquery_size number of bytes in @a xquery
645 * @param reply_bf bloomfilter to filter duplicates
646 * @param reply_bf_mutator mutator for @a reply_bf
647 * @param peer_bf filter for peers not to select (again, updated)
648 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
651 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
652 enum GNUNET_DHT_RouteOption options,
653 uint32_t desired_replication_level,
655 const struct GNUNET_HashCode *key,
656 const void *xquery, size_t xquery_size,
657 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
658 uint32_t reply_bf_mutator,
659 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
661 // find closest finger(s) on all layers
662 // use TrailRoute with PeerGetMessage embedded to contact peer
663 // NOTE: actually more complicated, see paper!
664 GNUNET_break (0); // not implemented!
665 return GNUNET_SYSERR;
670 * Delete a trail, it died (timeout, link failure, etc.).
672 * @param trail trail to delete from all data structures
673 * @param inform_pred should we notify the predecessor?
674 * @param inform_succ should we inform the successor?
677 delete_trail (struct Trail *trail,
681 struct FriendInfo *friend;
682 struct GNUNET_MQ_Envelope *env;
683 struct TrailDestroyMessage *tdm;
684 struct Finger *finger;
686 friend = trail->pred;
689 if (GNUNET_YES == inform_pred)
691 env = GNUNET_MQ_msg (tdm,
692 GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
693 tdm->trail_id = trail->pred_id;
694 GNUNET_MQ_send (friend->mq,
697 GNUNET_CONTAINER_MDLL_remove (pred,
702 friend = trail->succ;
705 if (GNUNET_YES == inform_succ)
707 env = GNUNET_MQ_msg (tdm,
708 GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
709 tdm->trail_id = trail->pred_id;
710 GNUNET_MQ_send (friend->mq,
713 GNUNET_CONTAINER_MDLL_remove (succ,
718 GNUNET_break (trail ==
719 GNUNET_CONTAINER_heap_remove_node (trail->hn));
720 finger = trail->ft->fingers[trail->finger_off];
723 trail->ft->fingers[trail->finger_off] = NULL;
724 trail->ft->number_valid_fingers--;
725 GNUNET_free (finger);
732 * Forward the given payload message along the trail.
734 * @param next_target which direction along the trail should we forward
735 * @param trail_id which trail should we forward along
736 * @param have_path do we track the forwarding path?
737 * @param predecessor which peer do we tack on to the path?
738 * @param path path the message has taken so far along the trail
739 * @param path_length number of entries in @a path
740 * @param payload payload of the message
743 forward_message_on_trail (struct FriendInfo *next_target,
744 const struct GNUNET_HashCode *trail_id,
746 const struct GNUNET_PeerIdentity *predecessor,
747 const struct GNUNET_PeerIdentity *path,
748 uint16_t path_length,
749 const struct GNUNET_MessageHeader *payload)
751 struct GNUNET_MQ_Envelope *env;
752 struct TrailRouteMessage *trm;
753 struct GNUNET_PeerIdentity *new_path;
755 uint16_t payload_len;
757 payload_len = ntohs (payload->size);
760 plen = path_length + 1;
761 if (plen >= (GNUNET_SERVER_MAX_MESSAGE_SIZE
763 - sizeof (struct TrailRouteMessage))
764 / sizeof (struct GNUNET_PeerIdentity))
766 /* Should really not have paths this long... */
774 GNUNET_break_op (0 == path_length);
778 env = GNUNET_MQ_msg_extra (trm,
780 plen * sizeof (struct GNUNET_PeerIdentity),
781 GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE);
782 trm->record_path = htons (have_path);
783 trm->path_length = htons (plen);
784 trm->trail_id = *trail_id;
785 new_path = (struct GNUNET_PeerIdentity *) &trm[1];
788 GNUNET_memcpy (new_path,
790 path_length * sizeof (struct GNUNET_PeerIdentity));
791 new_path[path_length] = *predecessor;
793 GNUNET_memcpy (&new_path[plen],
796 GNUNET_MQ_send (next_target->mq,
802 * Send the get result to requesting client.
804 * @param cls trail identifying where to send the result to, NULL for us
805 * @param options routing options (from GET request)
806 * @param key Key of the requested data.
807 * @param type Block type
808 * @param put_path_length Number of peers in @a put_path
809 * @param put_path Path taken to put the data at its stored location.
810 * @param expiration When will this result expire?
811 * @param data Payload to store
812 * @param data_size Size of the @a data
815 GDS_NEIGHBOURS_send_get_result (void *cls,
816 enum GNUNET_DHT_RouteOption options,
817 const struct GNUNET_HashCode *key,
818 enum GNUNET_BLOCK_Type type,
819 unsigned int put_path_length,
820 const struct GNUNET_PeerIdentity *put_path,
821 struct GNUNET_TIME_Absolute expiration,
825 const struct GNUNET_HashCode *trail_id = cls;
826 struct GNUNET_MessageHeader *payload;
829 trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
833 /* TODO: inform statistics */
836 if (NULL == trail->pred)
838 /* result is for *us* (local client) */
839 GDS_CLIENTS_handle_reply (expiration,
842 put_path_length, put_path,
849 payload = GNUNET_malloc(sizeof(struct GNUNET_MessageHeader) + data_size);
850 payload->size = data_size;
851 payload->type = GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT;
853 forward_message_on_trail (trail->pred,
855 0 != (options & GNUNET_DHT_RO_RECORD_ROUTE),
859 GNUNET_free (payload);
864 * Method called whenever a peer disconnects.
867 * @param peer peer identity this notification is about
868 * @param internal_cls our `struct FriendInfo` for @a peer
871 handle_core_disconnect (void *cls,
872 const struct GNUNET_PeerIdentity *peer,
875 struct FriendInfo *remove_friend = internal_cls;
878 /* If disconnected to own identity, then return. */
879 if (NULL == remove_friend)
881 GNUNET_assert (GNUNET_YES ==
882 GNUNET_CONTAINER_multipeermap_remove (friends_peermap,
885 while (NULL != (t = remove_friend->succ_head))
889 while (NULL != (t = remove_friend->pred_head))
893 GNUNET_free (remove_friend);
894 if (0 == GNUNET_CONTAINER_multipeermap_size (friends_peermap))
896 GNUNET_SCHEDULER_cancel (random_walk_task);
897 random_walk_task = NULL;
903 * Function called with a random friend to be returned.
905 * @param cls a `struct FriendInfo **` with where to store the result
906 * @param peer the peer identity of the friend (ignored)
907 * @param value the `struct FriendInfo *` that was selected at random
908 * @return #GNUNET_OK (all good)
911 pick_random_helper (void *cls,
912 const struct GNUNET_PeerIdentity *peer,
915 struct FriendInfo **fi = cls;
916 struct FriendInfo *v = value;
924 * Pick random friend from friends for random walk.
926 * @return NULL if we have no friends
928 static struct FriendInfo *
929 pick_random_friend ()
931 struct FriendInfo *ret;
935 GNUNET_CONTAINER_multipeermap_get_random (friends_peermap,
944 * One of our trails might have timed out, check and
945 * possibly initiate cleanup.
950 trail_timeout_callback (void *cls)
953 struct GNUNET_TIME_Relative left;
955 trail_timeout_task = NULL;
956 while (NULL != (trail = GNUNET_CONTAINER_heap_peek (trail_heap)))
958 left = GNUNET_TIME_absolute_get_remaining (trail->expiration_time);
959 if (0 != left.rel_value_us)
966 trail_timeout_task = GNUNET_SCHEDULER_add_delayed (left,
967 &trail_timeout_callback,
973 * Compute how big our finger arrays should be (at least).
975 * @return size of the finger array, never 0
978 get_desired_finger_array_size ()
980 /* FIXME: This is just a stub... */
986 * Initiate a random walk.
991 do_random_walk (void *cls)
993 static unsigned int walk_layer;
994 struct FriendInfo *friend;
995 struct GNUNET_MQ_Envelope *env;
996 struct RandomWalkMessage *rwm;
997 struct FingerTable *ft;
998 struct Finger *finger;
1002 random_walk_task = NULL;
1003 friend = pick_random_friend ();
1005 trail = GNUNET_new (struct Trail);
1006 /* We create the random walk so, no predecessor */
1007 trail->succ = friend;
1008 GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1011 GNUNET_CONTAINER_multihashmap_put (trail_map,
1014 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1017 GNUNET_free (trail);
1020 GNUNET_CONTAINER_MDLL_insert (succ,
1024 trail->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
1025 trail->hn = GNUNET_CONTAINER_heap_insert (trail_heap,
1027 trail->expiration_time.abs_value_us);
1028 if (NULL == trail_timeout_task)
1029 trail_timeout_task = GNUNET_SCHEDULER_add_delayed (TRAIL_TIMEOUT,
1030 &trail_timeout_callback,
1032 env = GNUNET_MQ_msg (rwm,
1033 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
1034 rwm->hops_taken = htonl (0);
1035 rwm->trail_id = trail->succ_id;
1036 GNUNET_MQ_send (friend->mq,
1038 /* clean up 'old' entry (implicitly via trail cleanup) */
1039 ft = &fingers[walk_layer];
1041 if ( (NULL != ft->fingers) &&
1042 (NULL != (finger = ft->fingers[ft->walk_offset])) )
1043 delete_trail (finger->trail,
1046 if (ft->finger_array_size < (nsize = get_desired_finger_array_size()) )
1047 GNUNET_array_grow (ft->fingers,
1048 ft->finger_array_size,
1050 GNUNET_assert (NULL == ft->fingers[ft->walk_offset]);
1052 trail->finger_off = ft->walk_offset;
1053 finger = GNUNET_new (struct Finger);
1054 finger->trail = trail;
1056 ft->fingers[ft->walk_offset] = finger;
1057 ft->is_sorted = GNUNET_NO;
1058 ft->number_valid_fingers++;
1059 ft->walk_offset = (ft->walk_offset + 1) % ft->finger_array_size;
1061 walk_layer = (walk_layer + 1) % NUMBER_LAYERED_ID;
1062 random_walk_task = GNUNET_SCHEDULER_add_delayed (RANDOM_WALK_DELAY,
1069 * Method called whenever a peer connects.
1071 * @param cls closure
1072 * @param peer_identity peer identity this notification is about
1073 * @param mq message queue for transmission to @a peer_identity
1074 * @return the `struct FriendInfo` for the @a peer_identity, NULL for us
1077 handle_core_connect (void *cls,
1078 const struct GNUNET_PeerIdentity *peer_identity,
1079 struct GNUNET_MQ_Handle *mq)
1081 struct FriendInfo *friend;
1083 /* Check for connect to self message */
1084 if (0 == memcmp (&my_identity,
1086 sizeof (struct GNUNET_PeerIdentity)))
1089 friend = GNUNET_new (struct FriendInfo);
1090 friend->id = peer_identity;
1092 GNUNET_assert (GNUNET_OK ==
1093 GNUNET_CONTAINER_multipeermap_put (friends_peermap,
1096 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1097 if (NULL == random_walk_task)
1099 /* random walk needs to be started -- we have a first connection */
1100 random_walk_task = GNUNET_SCHEDULER_add_now (&do_random_walk,
1108 * To be called on core init/fail.
1110 * @param cls service closure
1111 * @param identity the public identity of this peer
1114 core_init (void *cls,
1115 const struct GNUNET_PeerIdentity *identity)
1117 my_identity = *identity;
1122 * Handle a `struct RandomWalkMessage` from a
1123 * #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK message.
1125 * @param cls the `struct FriendInfo` for the sender
1126 * @param m the setup message
1129 handle_dht_p2p_random_walk (void *cls,
1130 const struct RandomWalkMessage *m)
1132 struct FriendInfo *pred = cls;
1136 layer = ntohs (m->layer);
1137 if (layer > NUMBER_LAYERED_ID)
1139 GNUNET_break_op (0);
1142 t = GNUNET_new (struct Trail);
1143 t->pred_id = m->trail_id;
1146 GNUNET_CONTAINER_multihashmap_put (trail_map,
1149 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1151 GNUNET_break_op (0);
1155 GNUNET_CONTAINER_MDLL_insert (pred,
1159 t->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
1160 t->hn = GNUNET_CONTAINER_heap_insert (trail_heap,
1162 t->expiration_time.abs_value_us);
1163 if (NULL == trail_timeout_task)
1164 trail_timeout_task = GNUNET_SCHEDULER_add_delayed (TRAIL_TIMEOUT,
1165 &trail_timeout_callback,
1168 if (ntohl (m->hops_taken) > GDS_NSE_get ())
1170 /* We are the last hop, generate response */
1171 struct GNUNET_MQ_Envelope *env;
1172 struct RandomWalkResponseMessage *rwrm;
1174 env = GNUNET_MQ_msg (rwrm,
1175 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE);
1176 rwrm->reserved = htonl (0);
1177 rwrm->trail_id = m->trail_id;
1179 (void) GDS_DATACACHE_get_random_key (&rwrm->location);
1182 struct FingerTable *ft;
1184 ft = &fingers[layer-1];
1185 if (0 == ft->number_valid_fingers)
1187 GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1196 off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
1197 ft->number_valid_fingers);
1198 for (i=0; (NULL == (f = ft->fingers[i])) || (off > 0); i++)
1199 if (NULL != f) off--;
1200 rwrm->location = f->destination;
1203 GNUNET_MQ_send (pred->mq,
1208 struct GNUNET_MQ_Envelope *env;
1209 struct RandomWalkMessage *rwm;
1210 struct FriendInfo *succ;
1212 /* extend the trail by another random hop */
1213 succ = pick_random_friend ();
1214 GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1218 GNUNET_CONTAINER_multihashmap_put (trail_map,
1221 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1224 GNUNET_CONTAINER_MDLL_remove (pred,
1231 GNUNET_CONTAINER_MDLL_insert (succ,
1235 env = GNUNET_MQ_msg (rwm,
1236 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
1237 rwm->hops_taken = htons (1 + ntohs (m->hops_taken));
1238 rwm->layer = m->layer;
1239 rwm->trail_id = t->succ_id;
1240 GNUNET_MQ_send (succ->mq,
1247 * Handle a `struct RandomWalkResponseMessage`.
1249 * @param cls closure
1250 * @param rwrm the setup response message
1253 handle_dht_p2p_random_walk_response (void *cls,
1254 const struct RandomWalkResponseMessage *rwrm)
1256 struct Trail *trail;
1257 struct FriendInfo *pred;
1258 struct FingerTable *ft;
1259 struct Finger *finger;
1261 trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1265 /* TODO: log/statistics: we didn't find the trail (can happen) */
1268 if (NULL != (pred = trail->pred))
1270 /* We are not the first hop, keep forwarding */
1271 struct GNUNET_MQ_Envelope *env;
1272 struct RandomWalkResponseMessage *rwrm2;
1274 env = GNUNET_MQ_msg (rwrm2,
1275 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE);
1276 rwrm2->reserved = htonl (0);
1277 rwrm2->location = rwrm->location;
1278 rwrm2->trail_id = trail->pred_id;
1279 GNUNET_MQ_send (pred->mq,
1283 /* We are the first hop, complete finger */
1284 if (NULL == (ft = trail->ft))
1286 /* Eh, why did we create the trail if we have no FT? */
1288 delete_trail (trail,
1293 if (NULL == (finger = ft->fingers[trail->finger_off]))
1295 /* Eh, finger got deleted, but why not the trail as well? */
1297 delete_trail (trail,
1304 // 1) lookup trail => find Finger entry => fill in 'destination' and mark valid, move to end of sorted array,
1305 //mark unsorted, update links from 'trails'
1308 * 1 check if we are the correct layer
1309 * 1.a if true : add the returned value (finger) in the db structure
1310 * 1.b if true : do nothing
1312 /* FIXME: add the value in db structure 1.a */
1318 * Handle a `struct TrailDestroyMessage`.
1320 * @param cls closure
1321 * @param tdm the trail destroy message
1324 handle_dht_p2p_trail_destroy (void *cls,
1325 const struct TrailDestroyMessage *tdm)
1327 struct FriendInfo *sender = cls;
1328 struct Trail *trail;
1330 trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1332 delete_trail (trail,
1333 ( (NULL != trail->succ) &&
1334 (0 == memcmp (sender->id,
1336 sizeof (struct GNUNET_PeerIdentity))) ),
1337 ( (NULL != trail->pred) &&
1338 (0 == memcmp (sender->id,
1340 sizeof (struct GNUNET_PeerIdentity))) ));
1345 * Handle a `struct FindSuccessorMessage` from a #GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND
1348 * @param cls closure (NULL)
1349 * @param trail_id path to the originator
1350 * @param trail_path path the message took on the trail, if available
1351 * @param trail_path_length number of entries on the @a trail_path
1352 * @param message the finger setup message
1353 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1356 handle_dht_p2p_successor_find (void *cls,
1357 const struct GNUNET_HashCode *trail_id,
1358 const struct GNUNET_PeerIdentity *trail_path,
1359 unsigned int trail_path_length,
1360 const struct GNUNET_MessageHeader *message)
1362 const struct FindSuccessorMessage *fsm;
1364 /* We do not expect to track trails for the forward-direction
1365 of successor finding... */
1366 GNUNET_break_op (0 == trail_path_length);
1367 fsm = (const struct FindSuccessorMessage *) message;
1368 GDS_DATACACHE_get_successors (&fsm->key,
1369 &GDS_NEIGHBOURS_send_get_result,
1376 * Handle a `struct PeerGetMessage`.
1378 * @param cls closure (NULL)
1379 * @param trail_id path to the originator
1380 * @param trail_path path the message took on the trail, if available
1381 * @param trail_path_length number of entries on the @a trail_path
1382 * @param message the peer get message
1383 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1386 handle_dht_p2p_peer_get (void *cls,
1387 const struct GNUNET_HashCode *trail_id,
1388 const struct GNUNET_PeerIdentity *trail_path,
1389 unsigned int trail_path_length,
1390 const struct GNUNET_MessageHeader *message)
1393 const struct PeerGetMessage *pgm;
1395 // FIXME: note: never called like this, message embedded with trail route!
1396 pgm = (const struct PeerGetMessage *) message;
1398 // -> lookup in datacache (figure out way to remember trail!)
1401 * 1 extract the result
1403 * 3 send it using the good trail
1405 * What do i do when i don't have the key/value?
1413 * Handle a `struct PeerGetResultMessage`.
1415 * @param cls closure (NULL)
1416 * @param trail_id path to the originator
1417 * @param trail_path path the message took on the trail, if available
1418 * @param trail_path_length number of entries on the @a trail_path
1419 * @param message the peer get result message
1420 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1423 handle_dht_p2p_peer_get_result (void *cls,
1424 const struct GNUNET_HashCode *trail_id,
1425 const struct GNUNET_PeerIdentity *trail_path,
1426 unsigned int trail_path_length,
1427 const struct GNUNET_MessageHeader *message)
1430 const struct PeerGetResultMessage *pgrm;
1432 pgrm = (const struct PeerGetResultMessage *) message;
1434 // pretty much: parse, & pass to client (there is some call for that...)
1437 GDS_CLIENTS_process_get (options,
1442 (void) GDS_DATACACHE_handle_get (trail_id,
1455 * Handle a `struct PeerPutMessage`.
1457 * @param cls closure (NULL)
1458 * @param trail_id path to the originator
1459 * @param trail_path path the message took on the trail, if available
1460 * @param trail_path_length number of entries on the @a trail_path
1461 * @param message the peer put message
1462 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1465 handle_dht_p2p_peer_put (void *cls,
1466 const struct GNUNET_HashCode *trail_id,
1467 const struct GNUNET_PeerIdentity *trail_path,
1468 unsigned int trail_path_length,
1469 const struct GNUNET_MessageHeader *message)
1472 const struct PeerGetResultMessage *pgrm;
1474 pgrm = (const struct PeerGetResultMessage *) message;
1476 // parse & store in datacache, this is in response to us asking for successors.
1479 * 1 check the size of the message
1480 * 2 use the API to add the value in the "database". Check on the xdht file, how to do it.
1481 * 3 Did i a have to return a notification or did i have to return GNUNET_[OK|SYSERR]?
1484 GDS_DATACACHE_handle_put (expiration_time,
1486 combined_path_length, combined_path,
1490 GDS_CLIENTS_process_put (options,
1493 combined_path_length, combined_path,
1504 * Handler for a message we received along some trail.
1506 * @param cls closure
1507 * @param trail_id trail identifier
1508 * @param trail_path path the message took on the trail, if available
1509 * @param trail_path_length number of entries on the @a trail_path
1510 * @param message the message we got
1511 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1514 (*TrailHandlerCallback)(void *cls,
1515 const struct GNUNET_HashCode *trail_id,
1516 const struct GNUNET_PeerIdentity *trail_path,
1517 unsigned int trail_path_length,
1518 const struct GNUNET_MessageHeader *message);
1522 * Definition of a handler for a message received along some trail.
1527 * NULL for end-of-list.
1529 TrailHandlerCallback callback;
1532 * Closure for @e callback.
1537 * Message type this handler addresses.
1539 uint16_t message_type;
1542 * Use 0 for variable-size.
1544 uint16_t message_size;
1549 * Check that a `struct TrailRouteMessage` is well-formed.
1551 * @param cls closure
1552 * @param trm the finger destroy message
1553 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1556 check_dht_p2p_trail_route (void *cls,
1557 const struct TrailRouteMessage *trm)
1559 const struct GNUNET_PeerIdentity *path;
1560 uint16_t path_length;
1561 const struct GNUNET_MessageHeader *payload;
1564 msize = ntohs (trm->header.size);
1565 path_length = ntohs (trm->path_length);
1566 if (msize < sizeof (struct TrailRouteMessage) +
1567 path_length * sizeof (struct GNUNET_PeerIdentity) +
1568 sizeof (struct GNUNET_MessageHeader) )
1570 GNUNET_break_op (0);
1571 return GNUNET_SYSERR;
1573 path = (const struct GNUNET_PeerIdentity *) &trm[1];
1574 payload = (const struct GNUNET_MessageHeader *) &path[path_length];
1575 if (msize != (ntohs (payload->size) +
1576 sizeof (struct TrailRouteMessage) +
1577 path_length * sizeof (struct GNUNET_PeerIdentity)))
1579 GNUNET_break_op (0);
1580 return GNUNET_SYSERR;
1582 /* FIXME: verify payload is OK!? */
1588 * Handle a `struct TrailRouteMessage`.
1590 * @param cls closure
1591 * @param trm the finger destroy message
1594 handle_dht_p2p_trail_route (void *cls,
1595 const struct TrailRouteMessage *trm)
1597 static const struct TrailHandler handlers[] = {
1598 { &handle_dht_p2p_successor_find, NULL,
1599 GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND,
1600 sizeof (struct FindSuccessorMessage) },
1601 { &handle_dht_p2p_peer_get, NULL,
1602 GNUNET_MESSAGE_TYPE_WDHT_GET,
1604 { &handle_dht_p2p_peer_get_result, NULL,
1605 GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT,
1607 { &handle_dht_p2p_peer_put, NULL,
1608 GNUNET_MESSAGE_TYPE_WDHT_PUT,
1610 { NULL, NULL, 0, 0 }
1612 struct FriendInfo *sender = cls;
1614 const struct GNUNET_PeerIdentity *path;
1615 uint16_t path_length;
1616 const struct GNUNET_MessageHeader *payload;
1617 const struct TrailHandler *th;
1618 struct Trail *trail;
1620 path_length = ntohs (trm->path_length);
1621 path = (const struct GNUNET_PeerIdentity *) &trm[1];
1622 payload = (const struct GNUNET_MessageHeader *) &path[path_length];
1623 /* Is this message for us? */
1624 trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1626 if ( (NULL != trail->pred) &&
1627 (0 == memcmp (sender->id,
1629 sizeof (struct GNUNET_PeerIdentity))) )
1631 /* forward to 'successor' */
1632 if (NULL != trail->succ)
1634 forward_message_on_trail (trail->succ,
1636 ntohs (trm->record_path),
1646 /* forward to 'predecessor' */
1647 GNUNET_break_op ( (NULL != trail->succ) &&
1648 (0 == memcmp (sender->id,
1650 sizeof (struct GNUNET_PeerIdentity))) );
1651 if (NULL != trail->pred)
1653 forward_message_on_trail (trail->pred,
1655 ntohs (trm->record_path),
1664 /* Message is for us, dispatch to handler */
1666 for (i=0; NULL != handlers[i].callback; i++)
1669 if (ntohs (payload->type) == th->message_type)
1671 if ( (0 == th->message_size) ||
1672 (ntohs (payload->size) == th->message_size) )
1673 th->callback (th->cls,
1679 GNUNET_break_op (0);
1683 GNUNET_break_op (NULL != th);
1688 * Initialize neighbours subsystem.
1690 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1693 GDS_NEIGHBOURS_init (void)
1695 struct GNUNET_MQ_MessageHandler core_handlers[] = {
1696 GNUNET_MQ_hd_fixed_size (dht_p2p_random_walk,
1697 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK,
1698 struct RandomWalkMessage,
1700 GNUNET_MQ_hd_fixed_size (dht_p2p_random_walk_response,
1701 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE,
1702 struct RandomWalkResponseMessage,
1704 GNUNET_MQ_hd_fixed_size (dht_p2p_trail_destroy,
1705 GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY,
1706 struct TrailDestroyMessage,
1708 GNUNET_MQ_hd_var_size (dht_p2p_trail_route,
1709 GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE,
1710 struct TrailRouteMessage,
1712 GNUNET_MQ_handler_end ()
1715 core_api = GNUNET_CORE_connecT (GDS_cfg, NULL,
1717 &handle_core_connect,
1718 &handle_core_disconnect,
1720 if (NULL == core_api)
1721 return GNUNET_SYSERR;
1722 friends_peermap = GNUNET_CONTAINER_multipeermap_create (256,
1724 trail_map = GNUNET_CONTAINER_multihashmap_create (1024,
1726 trail_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
1732 * Shutdown neighbours subsystem.
1735 GDS_NEIGHBOURS_done (void)
1737 if (NULL == core_api)
1739 GNUNET_CORE_disconnecT (core_api);
1741 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friends_peermap));
1742 GNUNET_CONTAINER_multipeermap_destroy (friends_peermap);
1743 friends_peermap = NULL;
1744 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (trail_map));
1745 GNUNET_CONTAINER_multihashmap_destroy (trail_map);
1747 GNUNET_CONTAINER_heap_destroy (trail_heap);
1749 if (NULL != trail_timeout_task)
1751 GNUNET_SCHEDULER_cancel (trail_timeout_task);
1752 trail_timeout_task = NULL;
1760 * @return my identity
1762 struct GNUNET_PeerIdentity *
1763 GDS_NEIGHBOURS_get_id (void)
1765 return &my_identity;
1768 /* end of gnunet-service-wdht_neighbours.c */