2 This file is part of GNUnet.
3 Copyright (C) 2009-2015 Christian Grothoff (and other contributing authors)
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-wdht.h"
43 #include "gnunet-service-wdht_clients.h"
44 #include "gnunet-service-wdht_datacache.h"
45 #include "gnunet-service-wdht_neighbours.h"
46 #include "gnunet-service-wdht_nse.h"
50 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
53 * Trail timeout. After what time do trails always die?
55 #define TRAIL_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 42)
58 * Random walk delay. How often do we walk the overlay?
60 #define RANDOM_WALK_DELAY GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 42)
63 * The number of layered ID to use.
65 #define NUMBER_LAYERED_ID 8
68 * The number of random walk to launch at the beginning of the initialization
70 /* FIXME: find a better value */
71 #define NUMBER_RANDOM_WALK 20
74 /******************* The db structure and related functions *******************/
77 * Entry in #friends_peermap.
87 * Information we keep per trail.
93 * Identifier of the trail with the predecessor.
95 struct GNUNET_HashCode pred_id;
98 * Identifier of the trail with the successor.
100 struct GNUNET_HashCode succ_id;
103 * When does this trail expire.
105 struct GNUNET_TIME_Absolute expiration_time;
108 * MDLL entry in the list of all trails with the same predecessor.
110 struct Trail *prev_succ;
113 * MDLL entry in the list of all trails with the same predecessor.
115 struct Trail *next_succ;
118 * MDLL entry in the list of all trails with the same predecessor.
120 struct Trail *prev_pred;
123 * MDLL entry in the list of all trails with the same predecessor.
125 struct Trail *next_pred;
128 * Our predecessor in the trail, NULL if we are initiator (?).
130 struct FriendInfo *pred;
133 * Our successor in the trail, NULL if we are the last peer.
135 struct FriendInfo *succ;
138 * Location of this trail in the heap.
140 struct GNUNET_CONTAINER_HeapNode *hn;
143 * If this peer started the to create a Finger (and thus @e pred is
144 * NULL), this is the finger table of the finger we are trying to
147 struct FingerTable *ft;
150 * If this peer started the trail to create a Finger (and thus @e
151 * pred is NULL), this is the offset of the finger we are trying to
152 * intialize in the unsorted array.
154 unsigned int finger_off;
160 * Entry in #friends_peermap.
167 struct GNUNET_PeerIdentity id;
172 struct Trail *pred_head;
177 struct Trail *pred_tail;
182 struct Trail *succ_head;
187 struct Trail *succ_tail;
190 * Core handle for sending messages to this friend.
192 struct GNUNET_MQ_Handle *mq;
210 struct FingerTable *ft;
215 struct GNUNET_HashCode destination;
218 * #GNUNET_YES if a response has been received. Otherwise #GNUNET_NO.
227 * Array of our fingers, unsorted.
229 struct Finger **fingers;
232 * Size of the finger array.
234 unsigned int finger_array_size;
237 * Number of valid entries in @e fingers
239 unsigned int number_valid_fingers;
242 * Which offset in @e fingers will we redo next.
244 unsigned int walk_offset;
247 * Is the finger array sorted?
254 /*********************** end of the db structure part ***********************/
257 GNUNET_NETWORK_STRUCT_BEGIN
260 * Setup a finger using the underlay topology ("social network").
262 struct RandomWalkMessage
265 * Type: #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK
267 struct GNUNET_MessageHeader header;
270 * Number of hops this message has taken so far, we stop at
273 uint16_t hops_taken GNUNET_PACKED;
276 * Layer for the request, in NBO.
278 uint16_t layer GNUNET_PACKED;
281 * Unique (random) identifier this peer will use to
282 * identify the trail (in future messages).
284 struct GNUNET_HashCode trail_id;
289 * Response to a `struct RandomWalkMessage`.
291 struct RandomWalkResponseMessage
294 * Type: #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE
296 struct GNUNET_MessageHeader header;
299 * Zero, for alignment.
301 uint32_t reserved GNUNET_PACKED;
304 * Unique (random) identifier from the
305 * `struct RandomWalkMessage`.
307 struct GNUNET_HashCode trail_id;
310 * Random location in the respective layer where the
311 * random path of the finger setup terminated.
313 struct GNUNET_HashCode location;
318 * Response to an event that causes a trail to die.
320 struct TrailDestroyMessage
323 * Type: #GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY
325 struct GNUNET_MessageHeader header;
328 * Zero, for alignment.
330 uint32_t reserved GNUNET_PACKED;
333 * Unique (random) identifier this peer will use to
334 * identify the finger (in future messages).
336 struct GNUNET_HashCode trail_id;
342 * Send a message along a trail.
344 struct FindSuccessorMessage
347 * Type: #GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND
349 struct GNUNET_MessageHeader header;
352 * Zero, for alignment.
354 uint32_t reserved GNUNET_PACKED;
357 * Key for which we would like close values returned.
358 * identify the finger (in future messages).
360 struct GNUNET_HashCode key;
366 * Send a message along a trail.
368 struct TrailRouteMessage
371 * Type: #GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE
373 struct GNUNET_MessageHeader header;
376 * #GNUNET_YES if the path should be recorded, #GNUNET_NO if not; in NBO.
378 uint16_t record_path GNUNET_PACKED;
381 * Length of the recorded trail, 0 if @e record_path is #GNUNET_NO; in NBO.
383 uint16_t path_length GNUNET_PACKED;
386 * Unique (random) identifier this peer will use to
387 * identify the finger (in future messages).
389 struct GNUNET_HashCode trail_id;
392 * Path the message has taken so far (excluding sender).
394 /* struct GNUNET_PeerIdentity path[path_length]; */
396 /* followed by payload (another `struct GNUNET_MessageHeader`) to
397 send along the trail */
404 struct PeerPutMessage
407 * Type: #GNUNET_MESSAGE_TYPE_WDHT_PUT
409 struct GNUNET_MessageHeader header;
414 uint32_t options GNUNET_PACKED;
419 uint32_t block_type GNUNET_PACKED;
424 uint32_t hop_count GNUNET_PACKED;
427 * Replication level for this message
428 * In the current implementation, this value is not used.
430 uint32_t desired_replication_level GNUNET_PACKED;
433 * Length of the PUT path that follows (if tracked).
435 uint32_t put_path_length GNUNET_PACKED;
438 * When does the content expire?
440 struct GNUNET_TIME_AbsoluteNBO expiration_time;
443 * The key to store the value under.
445 struct GNUNET_HashCode key GNUNET_PACKED;
447 /* put path (if tracked) */
456 struct PeerGetMessage
459 * Type: #GNUNET_MESSAGE_TYPE_WDHT_GET
461 struct GNUNET_MessageHeader header;
466 uint32_t options GNUNET_PACKED;
469 * Desired content type.
471 uint32_t block_type GNUNET_PACKED;
476 uint32_t hop_count GNUNET_PACKED;
479 * Desired replication level for this request.
480 * In the current implementation, this value is not used.
482 uint32_t desired_replication_level GNUNET_PACKED;
485 * Total number of peers in get path.
487 unsigned int get_path_length;
490 * The key we are looking for.
492 struct GNUNET_HashCode key;
495 /* struct GNUNET_PeerIdentity[]*/
502 struct PeerGetResultMessage
505 * Type: #GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT
507 struct GNUNET_MessageHeader header;
510 * The type for the data in NBO.
512 uint32_t type GNUNET_PACKED;
515 * Number of peers recorded in the outgoing path from source to the
516 * stored location of this message.
518 uint32_t put_path_length GNUNET_PACKED;
521 * When does the content expire?
523 struct GNUNET_TIME_AbsoluteNBO expiration_time;
526 * The key of the corresponding GET request.
528 struct GNUNET_HashCode key;
530 /* put path (if tracked) */
536 GNUNET_NETWORK_STRUCT_END
540 * Contains all the layered IDs of this peer.
542 struct GNUNET_PeerIdentity layered_id[NUMBER_LAYERED_ID];
545 * Task to timeout trails that have expired.
547 static struct GNUNET_SCHEDULER_Task *trail_timeout_task;
550 * Task to perform random walks.
552 static struct GNUNET_SCHEDULER_Task *random_walk_task;
555 * Identity of this peer.
557 static struct GNUNET_PeerIdentity my_identity;
560 * Peer map of all the friends of a peer
562 static struct GNUNET_CONTAINER_MultiPeerMap *friends_peermap;
567 static struct FingerTable fingers[NUMBER_LAYERED_ID];
570 * Tail map, mapping tail identifiers to `struct Trail`s
572 static struct GNUNET_CONTAINER_MultiHashMap *trail_map;
575 * Tail heap, organizing trails by expiration time.
577 static struct GNUNET_CONTAINER_Heap *trail_heap;
582 static struct GNUNET_CORE_Handle *core_api;
586 * Handle the put request from the client.
588 * @param key Key for the content
589 * @param block_type Type of the block
590 * @param options Routing options
591 * @param desired_replication_level Desired replication count
592 * @param expiration_time When does the content expire
593 * @param data Content to store
594 * @param data_size Size of content @a data in bytes
597 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
598 enum GNUNET_BLOCK_Type block_type,
599 enum GNUNET_DHT_RouteOption options,
600 uint32_t desired_replication_level,
601 struct GNUNET_TIME_Absolute expiration_time,
605 GDS_DATACACHE_handle_put (expiration_time,
612 GDS_CLIENTS_process_put (options,
624 * Handle the get request from the client file. If I am destination do
625 * datacache put and return. Else find the target friend and forward message
628 * @param key Key for the content
629 * @param block_type Type of the block
630 * @param options Routing options
631 * @param desired_replication_level Desired replication count
634 GDS_NEIGHBOURS_handle_get (const struct GNUNET_HashCode *key,
635 enum GNUNET_BLOCK_Type block_type,
636 enum GNUNET_DHT_RouteOption options,
637 uint32_t desired_replication_level)
639 // find closest finger(s) on all layers
640 // use TrailRoute with PeerGetMessage embedded to contact peer
641 // NOTE: actually more complicated, see paper!
646 * Delete a trail, it died (timeout, link failure, etc.).
648 * @param trail trail to delete from all data structures
649 * @param inform_pred should we notify the predecessor?
650 * @param inform_succ should we inform the successor?
653 delete_trail (struct Trail *trail,
657 struct FriendInfo *friend;
658 struct GNUNET_MQ_Envelope *env;
659 struct TrailDestroyMessage *tdm;
660 struct Finger *finger;
662 friend = trail->pred;
665 if (GNUNET_YES == inform_pred)
667 env = GNUNET_MQ_msg (tdm,
668 GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
669 tdm->trail_id = trail->pred_id;
670 GNUNET_MQ_send (friend->mq,
673 GNUNET_CONTAINER_MDLL_remove (pred,
678 friend = trail->succ;
681 if (GNUNET_YES == inform_succ)
683 env = GNUNET_MQ_msg (tdm,
684 GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
685 tdm->trail_id = trail->pred_id;
686 GNUNET_MQ_send (friend->mq,
689 GNUNET_CONTAINER_MDLL_remove (succ,
694 GNUNET_break (trail ==
695 GNUNET_CONTAINER_heap_remove_node (trail->hn));
696 finger = trail->ft->fingers[trail->finger_off];
699 trail->ft->fingers[trail->finger_off] = NULL;
700 trail->ft->number_valid_fingers--;
701 GNUNET_free (finger);
708 * Forward the given payload message along the trail.
710 * @param next_target which direction along the trail should we forward
711 * @param trail_id which trail should we forward along
712 * @param have_path do we track the forwarding path?
713 * @param predecessor which peer do we tack on to the path?
714 * @param path path the message has taken so far along the trail
715 * @param path_length number of entries in @a path
716 * @param payload payload of the message
719 forward_message_on_trail (struct FriendInfo *next_target,
720 const struct GNUNET_HashCode *trail_id,
722 const struct GNUNET_PeerIdentity *predecessor,
723 const struct GNUNET_PeerIdentity *path,
724 uint16_t path_length,
725 const struct GNUNET_MessageHeader *payload)
727 struct GNUNET_MQ_Envelope *env;
728 struct TrailRouteMessage *trm;
729 struct GNUNET_PeerIdentity *new_path;
731 uint16_t payload_len;
733 payload_len = ntohs (payload->size);
736 plen = path_length + 1;
737 if (plen >= (GNUNET_SERVER_MAX_MESSAGE_SIZE
739 - sizeof (struct TrailRouteMessage))
740 / sizeof (struct GNUNET_PeerIdentity))
742 /* Should really not have paths this long... */
750 GNUNET_break_op (0 == path_length);
754 env = GNUNET_MQ_msg_extra (trm,
756 plen * sizeof (struct GNUNET_PeerIdentity),
757 GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE);
758 trm->record_path = htons (have_path);
759 trm->path_length = htons (plen);
760 trm->trail_id = *trail_id;
761 new_path = (struct GNUNET_PeerIdentity *) &trm[1];
766 path_length * sizeof (struct GNUNET_PeerIdentity));
767 new_path[path_length] = *predecessor;
769 memcpy (&new_path[plen],
772 GNUNET_MQ_send (next_target->mq,
778 * Send the get result to requesting client.
780 * @param trail_id trail identifying where to send the result to, NULL for us
781 * @param options routing options (from GET request)
782 * @param key Key of the requested data.
783 * @param type Block type
784 * @param put_path_length Number of peers in @a put_path
785 * @param put_path Path taken to put the data at its stored location.
786 * @param expiration When will this result expire?
787 * @param data Payload to store
788 * @param data_size Size of the @a data
791 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *trail_id,
792 enum GNUNET_DHT_RouteOption options,
793 const struct GNUNET_HashCode *key,
794 enum GNUNET_BLOCK_Type type,
795 unsigned int put_path_length,
796 const struct GNUNET_PeerIdentity *put_path,
797 struct GNUNET_TIME_Absolute expiration,
801 struct GNUNET_MessageHeader *payload;
804 trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
808 /* TODO: inform statistics */
811 if (NULL == trail->pred)
813 /* result is for *us* (local client) */
814 GDS_CLIENTS_handle_reply (expiration,
817 put_path_length, put_path,
824 payload = GNUNET_malloc(sizeof(struct GNUNET_MessageHeader) + data_size);
825 payload->size = data_size;
826 payload->type = GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT;
828 forward_message_on_trail (trail->pred,
830 0 != (options & GNUNET_DHT_RO_RECORD_ROUTE),
834 GNUNET_free (payload);
839 * Method called whenever a peer disconnects.
842 * @param peer peer identity this notification is about
845 handle_core_disconnect (void *cls,
846 const struct GNUNET_PeerIdentity *peer)
848 struct FriendInfo *remove_friend;
851 /* If disconnected to own identity, then return. */
852 if (0 == memcmp (&my_identity,
854 sizeof (struct GNUNET_PeerIdentity)))
857 if (NULL == (remove_friend =
858 GNUNET_CONTAINER_multipeermap_get (friends_peermap,
865 GNUNET_assert (GNUNET_YES ==
866 GNUNET_CONTAINER_multipeermap_remove (friends_peermap,
869 while (NULL != (t = remove_friend->succ_head))
873 while (NULL != (t = remove_friend->pred_head))
877 GNUNET_MQ_destroy (remove_friend->mq);
878 GNUNET_free (remove_friend);
880 GNUNET_CONTAINER_multipeermap_size (friends_peermap))
882 GNUNET_SCHEDULER_cancel (random_walk_task);
883 random_walk_task = NULL;
889 * Function called with a random friend to be returned.
891 * @param cls a `struct FriendInfo **` with where to store the result
892 * @param peer the peer identity of the friend (ignored)
893 * @param value the `struct FriendInfo *` that was selected at random
894 * @return #GNUNET_OK (all good)
897 pick_random_helper (void *cls,
898 const struct GNUNET_PeerIdentity *peer,
901 struct FriendInfo **fi = cls;
902 struct FriendInfo *v = value;
910 * Pick random friend from friends for random walk.
912 * @return NULL if we have no friends
914 static struct FriendInfo *
915 pick_random_friend ()
917 struct FriendInfo *ret;
921 GNUNET_CONTAINER_multipeermap_get_random (friends_peermap,
930 * One of our trails might have timed out, check and
931 * possibly initiate cleanup.
937 trail_timeout_callback (void *cls,
938 const struct GNUNET_SCHEDULER_TaskContext *tc)
941 struct GNUNET_TIME_Relative left;
943 trail_timeout_task = NULL;
944 while (NULL != (trail = GNUNET_CONTAINER_heap_peek (trail_heap)))
946 left = GNUNET_TIME_absolute_get_remaining (trail->expiration_time);
947 if (0 != left.rel_value_us)
954 trail_timeout_task = GNUNET_SCHEDULER_add_delayed (left,
955 &trail_timeout_callback,
961 * Compute how big our finger arrays should be (at least).
963 * @return size of the finger array, never 0
966 get_desired_finger_array_size ()
968 /* FIXME: This is just a stub... */
974 * Initiate a random walk.
980 do_random_walk (void *cls,
981 const struct GNUNET_SCHEDULER_TaskContext *tc)
983 static unsigned int walk_layer;
984 struct FriendInfo *friend;
985 struct GNUNET_MQ_Envelope *env;
986 struct RandomWalkMessage *rwm;
987 struct FingerTable *ft;
988 struct Finger *finger;
992 random_walk_task = NULL;
993 friend = pick_random_friend ();
995 trail = GNUNET_new (struct Trail);
996 /* We create the random walk so, no predecessor */
997 trail->succ = friend;
998 GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1001 GNUNET_CONTAINER_multihashmap_put (trail_map,
1004 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1007 GNUNET_free (trail);
1010 GNUNET_CONTAINER_MDLL_insert (succ,
1014 trail->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
1015 trail->hn = GNUNET_CONTAINER_heap_insert (trail_heap,
1017 trail->expiration_time.abs_value_us);
1018 if (NULL == trail_timeout_task)
1019 trail_timeout_task = GNUNET_SCHEDULER_add_delayed (TRAIL_TIMEOUT,
1020 &trail_timeout_callback,
1022 env = GNUNET_MQ_msg (rwm,
1023 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
1024 rwm->hops_taken = htonl (0);
1025 rwm->trail_id = trail->succ_id;
1026 GNUNET_MQ_send (friend->mq,
1028 /* clean up 'old' entry (implicitly via trail cleanup) */
1029 ft = &fingers[walk_layer];
1031 if ( (NULL != ft->fingers) &&
1032 (NULL != (finger = ft->fingers[ft->walk_offset])) )
1033 delete_trail (finger->trail,
1036 if (ft->finger_array_size < (nsize = get_desired_finger_array_size()) )
1037 GNUNET_array_grow (ft->fingers,
1038 ft->finger_array_size,
1040 GNUNET_assert (NULL == ft->fingers[ft->walk_offset]);
1042 trail->finger_off = ft->walk_offset;
1043 finger = GNUNET_new (struct Finger);
1044 finger->trail = trail;
1046 ft->fingers[ft->walk_offset] = finger;
1047 ft->is_sorted = GNUNET_NO;
1048 ft->number_valid_fingers++;
1049 ft->walk_offset = (ft->walk_offset + 1) % ft->finger_array_size;
1051 walk_layer = (walk_layer + 1) % NUMBER_LAYERED_ID;
1052 random_walk_task = GNUNET_SCHEDULER_add_delayed (RANDOM_WALK_DELAY,
1059 * Method called whenever a peer connects.
1061 * @param cls closure
1062 * @param peer_identity peer identity this notification is about
1065 handle_core_connect (void *cls,
1066 const struct GNUNET_PeerIdentity *peer_identity)
1068 struct FriendInfo *friend;
1070 /* Check for connect to self message */
1071 if (0 == memcmp (&my_identity,
1073 sizeof (struct GNUNET_PeerIdentity)))
1076 /* If peer already exists in our friend_peermap, then exit. */
1078 GNUNET_CONTAINER_multipeermap_contains (friends_peermap,
1085 friend = GNUNET_new (struct FriendInfo);
1086 friend->id = *peer_identity;
1087 friend->mq = GNUNET_CORE_mq_create (core_api,
1089 GNUNET_assert (GNUNET_OK ==
1090 GNUNET_CONTAINER_multipeermap_put (friends_peermap,
1093 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1094 if (NULL == random_walk_task)
1096 /* random walk needs to be started -- we have a first connection */
1097 random_walk_task = GNUNET_SCHEDULER_add_now (&do_random_walk,
1104 * To be called on core init/fail.
1106 * @param cls service closure
1107 * @param identity the public identity of this peer
1110 core_init (void *cls,
1111 const struct GNUNET_PeerIdentity *identity)
1113 my_identity = *identity;
1118 * Handle a `struct RandomWalkMessage` from a
1119 * #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK message.
1121 * @param cls closure (NULL)
1122 * @param peer sender identity
1123 * @param message the setup message
1124 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1127 handle_dht_p2p_random_walk (void *cls,
1128 const struct GNUNET_PeerIdentity *peer,
1129 const struct GNUNET_MessageHeader *message)
1131 const struct RandomWalkMessage *m;
1133 struct FriendInfo *pred;
1136 m = (const struct RandomWalkMessage *) message;
1137 layer = ntohs (m->layer);
1138 if (layer > NUMBER_LAYERED_ID)
1140 GNUNET_break_op (0);
1141 return GNUNET_SYSERR;
1143 pred = GNUNET_CONTAINER_multipeermap_get (friends_peermap,
1145 t = GNUNET_new (struct Trail);
1146 t->pred_id = m->trail_id;
1149 GNUNET_CONTAINER_multihashmap_put (trail_map,
1152 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1154 GNUNET_break_op (0);
1156 return GNUNET_SYSERR;
1158 GNUNET_CONTAINER_MDLL_insert (pred,
1162 t->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
1163 t->hn = GNUNET_CONTAINER_heap_insert (trail_heap,
1165 t->expiration_time.abs_value_us);
1166 if (NULL == trail_timeout_task)
1167 trail_timeout_task = GNUNET_SCHEDULER_add_delayed (TRAIL_TIMEOUT,
1168 &trail_timeout_callback,
1171 if (ntohl (m->hops_taken) > GDS_NSE_get ())
1173 /* We are the last hop, generate response */
1174 struct GNUNET_MQ_Envelope *env;
1175 struct RandomWalkResponseMessage *rwrm;
1177 env = GNUNET_MQ_msg (rwrm,
1178 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE);
1179 rwrm->reserved = htonl (0);
1180 rwrm->trail_id = m->trail_id;
1182 (void) GDS_DATACACHE_get_random_key (&rwrm->location);
1185 struct FingerTable *ft;
1187 ft = &fingers[layer-1];
1188 if (0 == ft->number_valid_fingers)
1190 GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1199 off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
1200 ft->number_valid_fingers);
1201 for (i=0; (NULL == (f = ft->fingers[i])) || (off > 0); i++)
1202 if (NULL != f) off--;
1203 rwrm->location = f->destination;
1206 GNUNET_MQ_send (pred->mq,
1211 struct GNUNET_MQ_Envelope *env;
1212 struct RandomWalkMessage *rwm;
1213 struct FriendInfo *succ;
1215 /* extend the trail by another random hop */
1216 succ = pick_random_friend ();
1217 GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1221 GNUNET_CONTAINER_multihashmap_put (trail_map,
1224 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1227 GNUNET_CONTAINER_MDLL_remove (pred,
1234 GNUNET_CONTAINER_MDLL_insert (succ,
1238 env = GNUNET_MQ_msg (rwm,
1239 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
1240 rwm->hops_taken = htons (1 + ntohs (m->hops_taken));
1241 rwm->layer = m->layer;
1242 rwm->trail_id = t->succ_id;
1243 GNUNET_MQ_send (succ->mq,
1251 * Handle a `struct RandomWalkResponseMessage`.
1253 * @param cls closure (NULL)
1254 * @param peer sender identity
1255 * @param message the setup response message
1256 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1259 handle_dht_p2p_random_walk_response (void *cls,
1260 const struct GNUNET_PeerIdentity *peer,
1261 const struct GNUNET_MessageHeader *message)
1263 const struct RandomWalkResponseMessage *rwrm;
1264 struct Trail *trail;
1265 struct FriendInfo *pred;
1266 struct FingerTable *ft;
1267 struct Finger *finger;
1269 rwrm = (const struct RandomWalkResponseMessage *) message;
1270 trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1274 /* TODO: log/statistics: we didn't find the trail (can happen) */
1277 if (NULL != (pred = trail->pred))
1279 /* We are not the first hop, keep forwarding */
1280 struct GNUNET_MQ_Envelope *env;
1281 struct RandomWalkResponseMessage *rwrm2;
1283 env = GNUNET_MQ_msg (rwrm2,
1284 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE);
1285 rwrm2->reserved = htonl (0);
1286 rwrm2->location = rwrm->location;
1287 rwrm2->trail_id = trail->pred_id;
1288 GNUNET_MQ_send (pred->mq,
1292 /* We are the first hop, complete finger */
1293 if (NULL == (ft = trail->ft))
1295 /* Eh, why did we create the trail if we have no FT? */
1297 delete_trail (trail,
1302 if (NULL == (finger = ft->fingers[trail->finger_off]))
1304 /* Eh, finger got deleted, but why not the trail as well? */
1306 delete_trail (trail,
1313 // 1) lookup trail => find Finger entry => fill in 'destination' and mark valid, move to end of sorted array,
1314 //mark unsorted, update links from 'trails'
1317 * 1 check if we are the correct layer
1318 * 1.a if true : add the returned value (finger) in the db structure
1319 * 1.b if true : do nothing
1321 /* FIXME: add the value in db structure 1.a */
1328 * Handle a `struct TrailDestroyMessage`.
1330 * @param cls closure (NULL)
1331 * @param peer sender identity
1332 * @param message the finger destroy message
1333 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1336 handle_dht_p2p_trail_destroy (void *cls,
1337 const struct GNUNET_PeerIdentity *peer,
1338 const struct GNUNET_MessageHeader *message)
1340 const struct TrailDestroyMessage *tdm;
1341 struct Trail *trail;
1343 tdm = (const struct TrailDestroyMessage *) message;
1344 trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1346 delete_trail (trail,
1347 ( (NULL != trail->succ) &&
1350 sizeof (struct GNUNET_PeerIdentity))) ),
1351 ( (NULL != trail->pred) &&
1354 sizeof (struct GNUNET_PeerIdentity))) ));
1360 * Handle a `struct FindSuccessorMessage` from a #GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND
1363 * @param cls closure (NULL)
1364 * @param trail_id path to the originator
1365 * @param trail_path path the message took on the trail, if available
1366 * @param trail_path_length number of entries on the @a trail_path
1367 * @param message the finger setup message
1368 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1371 handle_dht_p2p_successor_find (void *cls,
1372 const struct GNUNET_HashCode *trail_id,
1373 const struct GNUNET_PeerIdentity *trail_path,
1374 unsigned int trail_path_length,
1375 const struct GNUNET_MessageHeader *message)
1377 const struct FindSuccessorMessage *fsm;
1379 /* We do not expect to track trails for the forward-direction
1380 of successor finding... */
1381 GNUNET_break_op (0 == trail_path_length);
1382 fsm = (const struct FindSuccessorMessage *) message;
1383 GDS_DATACACHE_get_successors (trail_id,
1390 * Handle a `struct PeerGetMessage`.
1392 * @param cls closure (NULL)
1393 * @param trail_id path to the originator
1394 * @param trail_path path the message took on the trail, if available
1395 * @param trail_path_length number of entries on the @a trail_path
1396 * @param message the peer get message
1397 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1400 handle_dht_p2p_peer_get (void *cls,
1401 const struct GNUNET_HashCode *trail_id,
1402 const struct GNUNET_PeerIdentity *trail_path,
1403 unsigned int trail_path_length,
1404 const struct GNUNET_MessageHeader *message)
1406 const struct PeerGetMessage *pgm;
1408 // FIXME: note: never called like this, message embedded with trail route!
1409 pgm = (const struct PeerGetMessage *) message;
1410 // -> lookup in datacache (figure out way to remember trail!)
1413 * 1 extract the result
1415 * 3 send it using the good trail
1417 * What do i do when i don't have the key/value?
1425 * Handle a `struct PeerGetResultMessage`.
1427 * @param cls closure (NULL)
1428 * @param trail_id path to the originator
1429 * @param trail_path path the message took on the trail, if available
1430 * @param trail_path_length number of entries on the @a trail_path
1431 * @param message the peer get result message
1432 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1435 handle_dht_p2p_peer_get_result (void *cls,
1436 const struct GNUNET_HashCode *trail_id,
1437 const struct GNUNET_PeerIdentity *trail_path,
1438 unsigned int trail_path_length,
1439 const struct GNUNET_MessageHeader *message)
1441 const struct PeerGetResultMessage *pgrm;
1443 pgrm = (const struct PeerGetResultMessage *) message;
1444 // pretty much: parse, & pass to client (there is some call for that...)
1447 GDS_CLIENTS_process_get (options,
1452 (void) GDS_DATACACHE_handle_get (trail_id,
1465 * Handle a `struct PeerPutMessage`.
1467 * @param cls closure (NULL)
1468 * @param trail_id path to the originator
1469 * @param trail_path path the message took on the trail, if available
1470 * @param trail_path_length number of entries on the @a trail_path
1471 * @param message the peer put message
1472 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1475 handle_dht_p2p_peer_put (void *cls,
1476 const struct GNUNET_HashCode *trail_id,
1477 const struct GNUNET_PeerIdentity *trail_path,
1478 unsigned int trail_path_length,
1479 const struct GNUNET_MessageHeader *message)
1481 const struct PeerGetResultMessage *pgrm;
1483 pgrm = (const struct PeerGetResultMessage *) message;
1484 // parse & store in datacache, this is in response to us asking for successors.
1487 * 1 check the size of the message
1488 * 2 use the API to add the value in the "database". Check on the xdht file, how to do it.
1489 * 3 Did i a have to return a notification or did i have to return GNUNET_[OK|SYSERR]?
1492 GDS_DATACACHE_handle_put (expiration_time,
1494 combined_path_length, combined_path,
1498 GDS_CLIENTS_process_put (options,
1501 combined_path_length, combined_path,
1512 * Handler for a message we received along some trail.
1514 * @param cls closure
1515 * @param trail_id trail identifier
1516 * @param trail_path path the message took on the trail, if available
1517 * @param trail_path_length number of entries on the @a trail_path
1518 * @param message the message we got
1519 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1522 (*TrailHandlerCallback)(void *cls,
1523 const struct GNUNET_HashCode *trail_id,
1524 const struct GNUNET_PeerIdentity *trail_path,
1525 unsigned int trail_path_length,
1526 const struct GNUNET_MessageHeader *message);
1530 * Definition of a handler for a message received along some trail.
1535 * NULL for end-of-list.
1537 TrailHandlerCallback callback;
1540 * Closure for @e callback.
1545 * Message type this handler addresses.
1547 uint16_t message_type;
1550 * Use 0 for variable-size.
1552 uint16_t message_size;
1557 * Handle a `struct TrailRouteMessage`.
1559 * @param cls closure (NULL)
1560 * @param peer sender identity
1561 * @param message the finger destroy message
1562 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1565 handle_dht_p2p_trail_route (void *cls,
1566 const struct GNUNET_PeerIdentity *peer,
1567 const struct GNUNET_MessageHeader *message)
1569 static const struct TrailHandler handlers[] = {
1570 { &handle_dht_p2p_successor_find, NULL,
1571 GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND,
1572 sizeof (struct FindSuccessorMessage) },
1573 { &handle_dht_p2p_peer_get, NULL,
1574 GNUNET_MESSAGE_TYPE_WDHT_GET,
1576 { &handle_dht_p2p_peer_get_result, NULL,
1577 GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT,
1579 { &handle_dht_p2p_peer_put, NULL,
1580 GNUNET_MESSAGE_TYPE_WDHT_PUT,
1582 { NULL, NULL, 0, 0 }
1585 const struct TrailRouteMessage *trm;
1586 const struct GNUNET_PeerIdentity *path;
1587 uint16_t path_length;
1588 const struct GNUNET_MessageHeader *payload;
1589 const struct TrailHandler *th;
1590 struct Trail *trail;
1593 /* Parse and check message is well-formed */
1594 msize = ntohs (message->size);
1595 if (msize < sizeof (struct TrailRouteMessage))
1597 GNUNET_break_op (0);
1600 trm = (const struct TrailRouteMessage *) message;
1601 path_length = ntohs (trm->path_length);
1602 if (msize < sizeof (struct TrailRouteMessage) +
1603 path_length * sizeof (struct GNUNET_PeerIdentity) +
1604 sizeof (struct GNUNET_MessageHeader) )
1606 GNUNET_break_op (0);
1609 path = (const struct GNUNET_PeerIdentity *) &trm[1];
1610 payload = (const struct GNUNET_MessageHeader *) &path[path_length];
1611 if (msize != (ntohs (payload->size) +
1612 sizeof (struct TrailRouteMessage) +
1613 path_length * sizeof (struct GNUNET_PeerIdentity)))
1615 GNUNET_break_op (0);
1619 /* Is this message for us? */
1620 trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1622 if ( (NULL != trail->pred) &&
1625 sizeof (struct GNUNET_PeerIdentity))) )
1627 /* forward to 'successor' */
1628 if (NULL != trail->succ)
1630 forward_message_on_trail (trail->succ,
1632 ntohs (trm->record_path),
1642 /* forward to 'predecessor' */
1643 GNUNET_break_op ( (NULL != trail->succ) &&
1646 sizeof (struct GNUNET_PeerIdentity))) );
1647 if (NULL != trail->pred)
1649 forward_message_on_trail (trail->pred,
1651 ntohs (trm->record_path),
1660 /* Message is for us, dispatch to handler */
1662 for (i=0; NULL != handlers[i].callback; i++)
1665 if (ntohs (payload->type) == th->message_type)
1667 if ( (0 == th->message_size) ||
1668 (ntohs (payload->size) == th->message_size) )
1669 th->callback (th->cls,
1675 GNUNET_break_op (0);
1679 GNUNET_break_op (NULL != th);
1685 * Initialize neighbours subsystem.
1687 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1690 GDS_NEIGHBOURS_init (void)
1692 static const struct GNUNET_CORE_MessageHandler core_handlers[] = {
1693 { &handle_dht_p2p_random_walk,
1694 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK,
1695 sizeof (struct RandomWalkMessage) },
1696 { &handle_dht_p2p_random_walk_response,
1697 GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE,
1698 sizeof (struct RandomWalkResponseMessage) },
1699 { &handle_dht_p2p_trail_destroy,
1700 GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY,
1701 sizeof (struct TrailDestroyMessage) },
1702 { &handle_dht_p2p_trail_route,
1703 GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE,
1709 GNUNET_CORE_connect (GDS_cfg, NULL,
1711 &handle_core_connect,
1712 &handle_core_disconnect,
1717 if (NULL == core_api)
1718 return GNUNET_SYSERR;
1719 friends_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1720 trail_map = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_YES);
1721 trail_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
1727 * Shutdown neighbours subsystem.
1730 GDS_NEIGHBOURS_done (void)
1732 if (NULL == core_api)
1734 GNUNET_CORE_disconnect (core_api);
1736 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friends_peermap));
1737 GNUNET_CONTAINER_multipeermap_destroy (friends_peermap);
1738 friends_peermap = NULL;
1739 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (trail_map));
1740 GNUNET_CONTAINER_multihashmap_destroy (trail_map);
1742 GNUNET_CONTAINER_heap_destroy (trail_heap);
1744 if (NULL != trail_timeout_task)
1746 GNUNET_SCHEDULER_cancel (trail_timeout_task);
1747 trail_timeout_task = NULL;
1755 * @return my identity
1757 struct GNUNET_PeerIdentity
1758 GDS_NEIGHBOURS_get_my_id (void)
1763 /* end of gnunet-service-wdht_neighbours.c */