2 This file is part of GNUnet.
3 (C) 2009-2013 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., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file dht/gnunet-service-xdht_neighbours.c
23 * @brief GNUnet DHT service's finger and friend table management code
24 * @author Supriti Singh
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_nse_service.h"
34 #include "gnunet_ats_service.h"
35 #include "gnunet_core_service.h"
36 #include "gnunet_datacache_lib.h"
37 #include "gnunet_transport_service.h"
38 #include "gnunet_hello_lib.h"
39 #include "gnunet_dht_service.h"
40 #include "gnunet_statistics_service.h"
41 #include "gnunet-service-xdht.h"
42 #include "gnunet-service-xdht_clients.h"
43 #include "gnunet-service-xdht_datacache.h"
44 #include "gnunet-service-xdht_hello.h"
45 #include "gnunet-service-xdht_neighbours.h"
46 #include "gnunet-service-xdht_nse.h"
47 #include "gnunet-service-xdht_routing.h"
53 1. You are not using mod when searching for the closest successor of a finger.
58 * Maximum possible fingers of a peer.
60 #define MAX_FINGERS 256
63 * Maximum allowed number of pending messages per friend peer.
65 #define MAXIMUM_PENDING_PER_FRIEND 64
68 * How long at least to wait before sending another find finger trail request.
70 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
73 * How long at most to wait before sending another find finger trail request.
75 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 10)
78 * FIXME: Currently used in GDS_NEIGHBOURS_handle_trail_setup.
79 * I have just copied it from gnunet-service-dht_neighbours. Will it work here?
80 * How long at most to wait for transmission of a GET request to another peer?
82 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
84 GNUNET_NETWORK_STRUCT_BEGIN
87 * 1) Bloomfilter is not required for X-Vine.
88 * Keep the field now but remove it when implementing PUT/GET.
89 * 2) also, check the field of put/get/result if all are required for
98 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
100 struct GNUNET_MessageHeader header;
105 uint32_t options GNUNET_PACKED;
110 uint32_t type GNUNET_PACKED;
115 uint32_t hop_count GNUNET_PACKED;
118 * Replication level for this message
120 uint32_t desired_replication_level GNUNET_PACKED;
123 * Length of the PUT path that follows (if tracked).
125 uint32_t put_path_length GNUNET_PACKED;
128 * When does the content expire?
130 struct GNUNET_TIME_AbsoluteNBO expiration_time;
133 * Bloomfilter (for peer identities) to stop circular routes
135 char bloomfilter[DHT_BLOOM_SIZE];
138 * The key we are storing under.
140 struct GNUNET_HashCode key;
142 /* put path (if tracked) */
152 struct PeerResultMessage
155 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
157 struct GNUNET_MessageHeader header;
162 uint32_t type GNUNET_PACKED;
165 * Length of the PUT path that follows (if tracked).
167 uint32_t put_path_length GNUNET_PACKED;
170 * Length of the GET path that follows (if tracked).
172 uint32_t get_path_length GNUNET_PACKED;
175 * When does the content expire?
177 struct GNUNET_TIME_AbsoluteNBO expiration_time;
180 * The key of the corresponding GET request.
182 struct GNUNET_HashCode key;
184 /* put path (if tracked) */
186 /* get path (if tracked) */
196 struct PeerGetMessage
199 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
201 struct GNUNET_MessageHeader header;
206 uint32_t options GNUNET_PACKED;
209 * Desired content type.
211 uint32_t type GNUNET_PACKED;
216 uint32_t hop_count GNUNET_PACKED;
219 * Desired replication level for this request.
221 uint32_t desired_replication_level GNUNET_PACKED;
224 * Size of the extended query.
226 uint32_t xquery_size;
229 * Bloomfilter mutator.
234 * Bloomfilter (for peer identities) to stop circular routes
236 char bloomfilter[DHT_BLOOM_SIZE];
239 * The key we are looking for.
241 struct GNUNET_HashCode key;
247 * P2P Trail setup message
248 * TODO: Take reference from put_path and get_path to understand how to use size of trail list.
250 struct PeerTrailSetupMessage
253 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
255 struct GNUNET_MessageHeader header;
258 * Source peer which wants to find trail to one of its finger.
260 struct GNUNET_PeerIdentity source_peer;
263 * Finger id to which we want to set up the trail to.
265 struct GNUNET_PeerIdentity destination_finger;
267 /* FIXME: Temporary field to handle current_destination properly.
268 If flag = 0, then this message's current_destination is a friend.
269 If flag = 1, then the message's current destination is a finger. */
272 * This field contains the peer to which this packet is forwarded.
274 struct GNUNET_PeerIdentity current_destination;
277 * Number of entries in trail list.
278 * FIXME: Is this data type correct?
279 * FIMXE: Is usage of GNUNET_PACKED correct?
281 uint32_t trail_length GNUNET_PACKED;
283 /* The finger index in finger map. */
284 unsigned int finger_index;
290 * P2P Trail setup Result message
292 struct PeerTrailSetupResultMessage
295 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
297 struct GNUNET_MessageHeader header;
300 * Finger to which we have found the path.
302 struct GNUNET_PeerIdentity finger;
305 * Peer which was looking for the trail to finger.
307 struct GNUNET_PeerIdentity destination_peer;
310 * This field contains the peer to which this packet is forwarded.
312 struct GNUNET_PeerIdentity current_destination;
315 * FIXME: Temporary field used to remember at which index we should read
316 * to get our next peer.
318 unsigned int current_index;
321 * Number of entries in trail list.
322 * FIXME: Is this data type correct?
323 * FIXME: Is usage of GNUNET_PACKED correct?
325 uint32_t list_size GNUNET_PACKED;
329 GNUNET_NETWORK_STRUCT_END
333 * Linked list of messages to send to a particular other peer.
335 struct P2PPendingMessage
338 * Pointer to next item in the list
340 struct P2PPendingMessage *next;
343 * Pointer to previous item in the list
345 struct P2PPendingMessage *prev;
348 * When does this message time out?
350 struct GNUNET_TIME_Absolute timeout;
353 * Message importance level. FIXME: used? useful?
355 unsigned int importance;
358 * Actual message to be sent, allocated at the end of the struct:
359 * // msg = (cast) &pm[1];
360 * // memcpy (&pm[1], data, len);
362 const struct GNUNET_MessageHeader *msg;
368 * Linked List of peers which are part of trail to reach a particular Finger.
373 * Pointer to next item in the list
375 struct TrailPeerList *next;
378 * Pointer to previous item in the list
380 struct TrailPeerList *prev;
383 * An element in this trail list
385 struct GNUNET_PeerIdentity peer;
391 * Entry in friend_peermap.
396 * What is the identity of the peer?
398 struct GNUNET_PeerIdentity id;
401 * Count of outstanding messages for peer.
403 unsigned int pending_count;
406 * Peer id of next friend in friend peermap in 64 bit format.
408 uint64_t interval_end;
411 * Head of pending messages to be sent to this peer.
413 struct P2PPendingMessage *head;
416 * Tail of pending messages to be sent to this peer.
418 struct P2PPendingMessage *tail;
421 * TODO - How and where to use this?
422 * Core handle for sending messages to this peer.
424 struct GNUNET_CORE_TransmitHandle *th;
430 * Entry in finger_peermap.
435 * What is the identity of the finger peer?
437 struct GNUNET_PeerIdentity id;
440 * Start of the interval of keys for which this finger is responsible.
442 unsigned int interval_start;
445 * End of the interval of keys for which this finger is responsible.
447 unsigned int interval_end;
450 * Head of trail list.
452 struct TrailPeerList *head;
455 * Tail of trail list.
457 struct TrailPeerList *tail;
462 unsigned int finger_index;
467 * Task that sends FIND FINGER TRAIL requests.
469 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
472 * Identity of this peer.
474 static struct GNUNET_PeerIdentity my_identity;
477 * FIXME: Not used anywhere in the code yet.
478 * Hash of the identity of this peer.
480 static struct GNUNET_HashCode my_identity_hash;
483 * Hash map of all the friends of a peer
485 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
488 * Hash map of all the fingers of a peer
490 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
493 * TODO: Ask whats the use of ATS.
496 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
501 static struct GNUNET_CORE_Handle *core_api;
504 * The current finger index that we have found trail to.
506 static unsigned int current_finger_index;
510 * Called when core is ready to send a message we asked for
511 * out to the destination.
513 * @param cls the 'struct PeerInfo' of the target peer
514 * @param size number of bytes available in buf
515 * @param buf where the callee should write the message
516 * @return number of bytes written to buf
519 core_transmit_notify (void *cls, size_t size, void *buf)
521 struct FriendInfo *peer = cls;
523 struct P2PPendingMessage *pending;
528 while ((NULL != (pending = peer->head)) &&
529 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
531 peer->pending_count--;
532 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
533 GNUNET_free (pending);
537 /* no messages pending */
543 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
544 GNUNET_CORE_PRIO_BEST_EFFORT,
545 GNUNET_TIME_absolute_get_remaining
546 (pending->timeout), &peer->id,
547 ntohs (pending->msg->size),
548 &core_transmit_notify, peer);
549 GNUNET_break (NULL != peer->th);
553 while ((NULL != (pending = peer->head)) &&
554 (size - off >= (msize = ntohs (pending->msg->size))))
556 GNUNET_STATISTICS_update (GDS_stats,
558 ("# Bytes transmitted to other peers"), msize,
560 memcpy (&cbuf[off], pending->msg, msize);
562 peer->pending_count--;
563 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
564 GNUNET_free (pending);
566 if (peer->head != NULL)
569 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
570 GNUNET_CORE_PRIO_BEST_EFFORT,
571 GNUNET_TIME_absolute_get_remaining
572 (pending->timeout), &peer->id, msize,
573 &core_transmit_notify, peer);
574 GNUNET_break (NULL != peer->th);
581 * Transmit all messages in the friend's message queue.
583 * @param peer message queue to process
586 process_friend_queue (struct FriendInfo *peer)
588 struct P2PPendingMessage *pending;
590 if (NULL == (pending = peer->head))
592 if (NULL != peer->th)
595 GNUNET_STATISTICS_update (GDS_stats,
597 ("# Bytes of bandwidth requested from core"),
598 ntohs (pending->msg->size), GNUNET_NO);
600 /* FIXME: Are we correctly initializing importance and pending. */
602 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
604 GNUNET_TIME_absolute_get_remaining
605 (pending->timeout), &peer->id,
606 ntohs (pending->msg->size),
607 &core_transmit_notify, peer);
608 GNUNET_break (NULL != peer->th);
613 * FIXME: Do we need to use some block type in this function?
614 * Set up the trial message and forwards this message to friend.
616 * @param Finger id to which we want to setup the trail.
617 * @param Friend id through which we will try to setup the trail.
620 GDS_NEIGHBOURS_handle_trail_setup(struct GNUNET_PeerIdentity *finger_id,
621 struct FriendInfo *target_friend,
622 unsigned int finger_index)
624 struct P2PPendingMessage *pending;
625 struct PeerTrailSetupMessage *tsm;
626 struct GNUNET_PeerIdentity *peer_id;
629 /* We will add target_friend to our trail_list. Hence, we add its size to size
630 of PeerTrailSetupMessage to get msize. */
631 msize = sizeof(struct PeerTrailSetupMessage) + sizeof(struct GNUNET_PeerIdentity);
633 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
639 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
641 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
645 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
646 pending->importance = 0; /* FIXME */
647 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
648 tsm = (struct PeerTrailSetupMessage *) &pending[1];
649 pending->msg = &tsm->header;
650 tsm->header.size = htons (msize);
651 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
652 memcpy(&(tsm->destination_finger), finger_id, sizeof (struct GNUNET_PeerIdentity));
653 memcpy(&(tsm->source_peer), &my_identity, sizeof (struct GNUNET_PeerIdentity));
654 memcpy(&(tsm->current_destination),&(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
655 tsm->flag = 0; /*FIXME: Replace 0 by enum for friend/finger.*/
656 tsm->finger_index = finger_index;
657 tsm->trail_length = 1;
659 peer_id = (struct GNUNET_PeerIdentity *)&tsm[1];
660 memcpy(peer_id, target_friend, sizeof (struct GNUNET_PeerIdentity));
662 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
664 target_friend->pending_count++;
665 process_friend_queue (target_friend);
670 * Handle a trail setup result message.
671 * @tsm PeerTrailSetupMessage
674 GDS_NEIGHBOURS_handle_trail_setup_result(struct PeerTrailSetupMessage *tsm)
676 /* In this function, you need to setup the trail result message. */
677 struct PeerTrailSetupResultMessage *tsrm;
678 struct P2PPendingMessage *pending;
679 struct FriendInfo *friend;
680 struct GNUNET_PeerIdentity *peer;
683 /* FIXME: Check if this msize is correct or not. */
684 msize = sizeof(struct PeerTrailSetupMessage) + (tsm->trail_length * sizeof(struct GNUNET_PeerIdentity));
686 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
692 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
693 pending->importance = 0; /* FIXME */
694 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
695 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
696 pending->msg = &tsrm->header;
697 tsrm->header.size = htons (msize);
698 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
699 memcpy(&(tsrm->finger), &(tsm->current_destination), sizeof(struct GNUNET_PeerIdentity));
700 memcpy(&(tsrm->destination_peer), &(tsm->source_peer), sizeof(struct GNUNET_PeerIdentity));
701 tsrm->list_size = tsm->trail_length;
703 /* TODO: Copy the whole trail list into tsrm. */
705 /* Read the elements of trail list backwards to get the target friend to sent
706 the packet to. Assuming we did not add ourself to the trail list, the last element
707 will be the element to which we want to send the packet. */
708 peer = (struct GNUNET_PeerIdentity *)&tsm[tsm->trail_length];
710 /* Get the friend corresponding to this peer. */
711 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
713 if (friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
715 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
719 /* call process_friend_queue. */
720 GNUNET_CONTAINER_DLL_insert_tail (friend->head, friend->tail, pending);
722 friend->pending_count++;
723 process_friend_queue (friend);
727 /**FIXME: Old implementation just to remove error
728 * TODO: Modify this function to handle our get request.
729 * Perform a GET operation. Forwards the given request to other
730 * peers. Does not lookup the key locally. May do nothing if this is
731 * the only peer in the network (or if we are the closest peer in the
734 * @param type type of the block
735 * @param options routing options
736 * @param desired_replication_level desired replication count
737 * @param hop_count how many hops did this request traverse so far?
738 * @param key key for the content
739 * @param xquery extended query
740 * @param xquery_size number of bytes in @a xquery
741 * @param reply_bf bloomfilter to filter duplicates
742 * @param reply_bf_mutator mutator for @a reply_bf
743 * @param peer_bf filter for peers not to select (again)
746 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
747 enum GNUNET_DHT_RouteOption options,
748 uint32_t desired_replication_level,
749 uint32_t hop_count, const struct GNUNET_HashCode * key,
750 const void *xquery, size_t xquery_size,
751 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
752 uint32_t reply_bf_mutator,
753 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
758 /**FIXME: Old implementation just to remove error.
759 * TODO: Modify this function to handle our put request.
760 * Perform a PUT operation. Forwards the given request to other
761 * peers. Does not store the data locally. Does not give the
762 * data to local clients. May do nothing if this is the only
763 * peer in the network (or if we are the closest peer in the
766 * @param type type of the block
767 * @param options routing options
768 * @param desired_replication_level desired replication count
769 * @param expiration_time when does the content expire
770 * @param hop_count how many hops has this message traversed so far
771 * @param bf Bloom filter of peers this PUT has already traversed
772 * @param key key for the content
773 * @param put_path_length number of entries in @a put_path
774 * @param put_path peers this request has traversed so far (if tracked)
775 * @param data payload to store
776 * @param data_size number of bytes in @a data
779 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
780 enum GNUNET_DHT_RouteOption options,
781 uint32_t desired_replication_level,
782 struct GNUNET_TIME_Absolute expiration_time,
784 struct GNUNET_CONTAINER_BloomFilter *bf,
785 const struct GNUNET_HashCode *key,
786 unsigned int put_path_length,
787 struct GNUNET_PeerIdentity *put_path,
788 const void *data, size_t data_size)
794 /**FIXME: Old implementation just to remove error.
795 * Handle a reply (route to origin). Only forwards the reply back to
796 * other peers waiting for it. Does not do local caching or
797 * forwarding to local clients.
799 * @param target neighbour that should receive the block (if still connected)
800 * @param type type of the block
801 * @param expiration_time when does the content expire
802 * @param key key for the content
803 * @param put_path_length number of entries in put_path
804 * @param put_path peers the original PUT traversed (if tracked)
805 * @param get_path_length number of entries in put_path
806 * @param get_path peers this reply has traversed so far (if tracked)
807 * @param data payload of the reply
808 * @param data_size number of bytes in data
811 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
812 enum GNUNET_BLOCK_Type type,
813 struct GNUNET_TIME_Absolute expiration_time,
814 const struct GNUNET_HashCode * key,
815 unsigned int put_path_length,
816 const struct GNUNET_PeerIdentity *put_path,
817 unsigned int get_path_length,
818 const struct GNUNET_PeerIdentity *get_path,
819 const void *data, size_t data_size)
826 * Randomly choose one of your friends from the friends_peer map
829 static struct FriendInfo *
830 select_random_friend()
832 unsigned int current_size;
835 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
836 struct GNUNET_PeerIdentity key_ret;
837 struct FriendInfo *friend;
839 current_size = GNUNET_CONTAINER_multipeermap_size(friend_peermap);
841 /* Element stored at this index in friend_peermap should be selected friend. */
842 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
844 /* Create an iterator for friend_peermap. */
845 iter = GNUNET_CONTAINER_multipeermap_iterator_create(friend_peermap);
847 /* Set the position of iterator to index. */
850 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,NULL,NULL))
856 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,&key_ret,(const void **)&friend))
866 * Compute finger_identity to which we want to setup the trail
867 * @return finger_identity
870 struct GNUNET_PeerIdentity *
871 compute_finger_identity()
873 struct GNUNET_PeerIdentity *finger_identity;
875 finger_identity = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
876 finger_identity = GNUNET_CRYPTO_compute_finger_identity(&my_identity,current_finger_index );
882 current_finger_index = (current_finger_index+1) % MAX_FINGERS;
884 /* Check if you already have an entry in finger_peermap for this finger_id.
885 If yes then again look for a new finger_id.
886 FIXME: Should we return NULL here?
887 if(NULL != GNUNET_CONTAINER_multipeermap_get(finger_peermap,finger_peer_id))
889 finger_peer_id = compute_finger_identity();
892 return finger_identity;
897 * TODO: Implement after testing friend/finger map.
898 * TODO: Handle the case when we already have a trail to our predecessor in
900 * This function will be needed when we are handling node joins/fails
901 * to maintain correct pointer to our predecessor and successor in the network.
902 * Find immediate predecessor in the network.
903 * @param me my own identity
904 * @return peer identity of immediate predecessor.
907 struct GNUNET_PeerIdentity *
908 find_immediate_predecessor()
910 /* Using your own peer identity, calculate your predecessor
911 * in the network. Try to setup path to this predecessor using
912 * the same logic as used for other fingers.
913 * If we already have a trail to our predecessor then send NULL and
914 * calling function should be able to handle that case.
921 * Task to send a find finger trail message. We attempt to find trail
922 * to our finger in the network.
924 * @param cls closure for this task
925 * @param tc the context under which the task is running
928 send_find_finger_trail_message (void *cls,
929 const struct GNUNET_SCHEDULER_TaskContext *tc)
931 struct GNUNET_PeerIdentity *finger_identity;
932 struct FriendInfo *friend;
933 struct GNUNET_TIME_Relative next_send_time;
934 unsigned int finger_index;
936 /* FIXME: How do we use the finger_index in rest of the algorithm
937 If not use then remove later. */
938 finger_index = current_finger_index;
940 /* We already have found trail to each of our possible fingers in the network. */
941 if (GNUNET_CONTAINER_multipeermap_size (finger_peermap) == MAX_FINGERS)
943 /* FIXME: I call find_immediate_predecessor when I have found trail to
944 * all the possible fingers in the network. But we need to find immediate
945 * predecessor when there is a node failure/join. It may happen before.
946 * Think of a better strategy to decide when to call this function.
947 * We can find trail to our immediate predecessor in the network.
949 finger_identity = find_immediate_predecessor();
951 if(NULL == finger_identity)
953 /* We already have a trail to reach to immediate predecessor. */
954 goto new_find_finger_trail_request;
959 /* Find the finger_peer_id for which we want to setup the trail */
960 finger_identity = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
961 finger_identity = compute_finger_identity();
963 if(finger_identity == NULL)
965 goto new_find_finger_trail_request;
969 friend = GNUNET_malloc (sizeof (struct FriendInfo));
970 friend = select_random_friend();
972 /* We found a friend.*/
974 GDS_NEIGHBOURS_handle_trail_setup(finger_identity, friend, finger_index);
976 /* FIXME: Should we be using current_finger_index to generate random interval.*/
977 new_find_finger_trail_request:
978 next_send_time.rel_value_us =
979 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
980 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
981 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
982 (current_finger_index + 1));
984 find_finger_trail_task =
985 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
991 * Method called whenever a peer connects.
994 * @param peer peer identity this notification is about
997 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer)
999 struct FriendInfo *ret;
1001 /* Check for connect to self message */
1002 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1005 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1006 "Connected to %s\n",
1009 /* If peer already exists in our friend_peermap, then exit. */
1011 GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
1018 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
1021 ret = GNUNET_new (struct FriendInfo);
1024 GNUNET_assert (GNUNET_OK ==
1025 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
1027 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1029 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
1030 if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
1031 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
1036 * FIXME: Implement after testing finger/friend table setup.
1037 * Method called whenever a peer disconnects.
1039 * @param cls closure
1040 * @param peer peer identity this notification is about
1043 handle_core_disconnect (void *cls,
1044 const struct GNUNET_PeerIdentity *peer)
1047 * 1. remove the friend from the friend map.
1048 * 2. remove the trail for the fingers for which this peer was the first hop.
1049 * 3. start send_find_finger_trail for these fingers to find a new trail
1051 * 4. Also when a node gets disconnected, how should we update pointers of its
1052 * immediate successor and predecessor in the network ?
1053 * 5. Also how do we distribute the keys in the network?
1054 * 6. Here is case where we started put operation but a peer got disconnected and
1055 we removed the entry from the table. How to handle such a case.
1061 * To be called on core init/fail.
1063 * @param cls service closure
1064 * @param identity the public identity of this peer
1067 core_init (void *cls,
1068 const struct GNUNET_PeerIdentity *identity)
1070 my_identity = *identity;
1071 GNUNET_CRYPTO_hash (identity,
1072 sizeof (struct GNUNET_PeerIdentity),
1078 * Core handler for p2p put requests.
1080 * @param cls closure
1081 * @param peer sender of the request
1082 * @param message message
1083 * @param peer peer identity this notification is about
1084 * @return #GNUNET_OK to keep the connection open,
1085 * #GNUNET_SYSERR to close it (signal serious error)
1088 handle_dht_p2p_put (void *cls,
1089 const struct GNUNET_PeerIdentity *peer,
1090 const struct GNUNET_MessageHeader *message)
1093 1. Search the friend,finger and check your own id to find the closest
1094 * predecessor the given key. --> find_predecessor()
1095 2. If self then datache_store
1096 3. If friend, then add to peer queue
1097 4. If finger, then add to the peer queue of the first hop.
1098 * in put message also maintain a field current_destination and use
1099 * same logic as trail setup to understand if you are just part of trail
1100 * to reach to a particular peer or you are endpoint of trail or just a friend.
1108 * Core handler for p2p get requests.
1110 * @param cls closure
1111 * @param peer sender of the request
1112 * @param message message
1113 * @return #GNUNET_OK to keep the connection open,
1114 * #GNUNET_SYSERR to close it (signal serious error)
1117 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1118 const struct GNUNET_MessageHeader *message)
1125 * Core handler for p2p result messages.
1127 * @param cls closure
1128 * @param message message
1129 * @param peer peer identity this notification is about
1130 * @return #GNUNET_YES (do not cut p2p connection)
1133 handle_dht_p2p_result (void *cls, const struct GNUNET_PeerIdentity *peer,
1134 const struct GNUNET_MessageHeader *message)
1141 * FIXMEl Where do we use mod MAX_FINGERS?
1142 * @param destination
1143 * @param flag Set the value of flag to 0, if next_hop = friend/1 if next_hop = finger.
1144 * @param current_destination We should set this field to finger id/friend id chosen to be next_hop.
1147 static struct GNUNET_PeerIdentity *
1148 find_successor(struct GNUNET_PeerIdentity *destination, struct GNUNET_PeerIdentity *current_destination,int *flag)
1151 * 1. Compare your identity with destination identity.
1152 * 2. Iterate over friend_map to find the peer identity with identity >= destination
1153 * 3. Iterate over finger_map to find the peer identity with identity >= destination
1154 * 4. Compare id,friend and finger to select one which is the least and still >= destination.
1155 * 5. If friend/my_identity then flag = 0
1156 * 6. If finger, then flag = 1.
1157 * 7. Set the current_destination value with chosen friend/finger/my_identity
1158 * 8. If finger, then search in your own finger table send the next hop to reach that finger.
1160 unsigned int friend_index;
1161 unsigned int finger_index;
1162 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1163 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1164 struct GNUNET_PeerIdentity key_ret;
1165 struct FriendInfo *friend;
1166 struct FingerInfo *finger;
1167 struct GNUNET_PeerIdentity *current_successor;
1169 /* FIXME: Temporary field used to understand if we got a friend or finger
1170 as next successor. find something better. */
1172 int finger_peer = 0;
1173 int friend_peer = 1;
1176 current_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1178 /* initialize current_successor with your own identity. */
1179 memcpy(current_successor,&my_identity,sizeof(struct GNUNET_PeerIdentity));
1182 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1184 /*iterate over friend map till you reach a peer id such that destination <= peer id */
1185 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1187 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1189 if(0 > GNUNET_CRYPTO_cmp_peer_identity(&friend->id,destination) ||
1190 (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id,destination)))
1192 /* If yes then check if finger <= current_successor */
1193 if(0 < GNUNET_CRYPTO_cmp_peer_identity(&friend->id,current_successor) ||
1194 (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id,current_successor)))
1196 memcpy(current_successor,friend,sizeof(struct GNUNET_PeerIdentity));
1197 successor = friend_peer;
1204 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1205 /* iterate over finger map till you reach a peer id such that destination <= peer id */
1206 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1208 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1210 if(0 > GNUNET_CRYPTO_cmp_peer_identity(&finger->id,destination) ||
1211 (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->id,destination)))
1213 /* If yes then check if finger <= current_friend_successor */
1214 if(0 < GNUNET_CRYPTO_cmp_peer_identity(&finger->id,current_successor)
1215 || (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->id,current_successor)))
1217 memcpy(current_successor,finger,sizeof(struct GNUNET_PeerIdentity));
1218 successor = finger_peer;
1224 memcpy(current_destination,current_successor,sizeof(struct GNUNET_PeerIdentity));
1226 if(successor == finger_peer)
1232 /* The successor is either my_identity or friend. */
1236 return current_successor;
1242 * 1. Check if we are correctly adding peer to our message and sending
1243 * the message correctly to next friend.
1244 * @param cls closure
1245 * @param message message
1246 * @param peer peer identity this notification is about
1247 * @return #GNUNET_YES
1250 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1251 const struct GNUNET_MessageHeader *message)
1253 struct PeerTrailSetupMessage *trail_setup;
1254 struct GNUNET_PeerIdentity *next_hop;
1255 struct GNUNET_PeerIdentity *peer_identity_trail;
1256 struct FriendInfo *target_friend;
1257 struct P2PPendingMessage *pending;
1259 uint32_t trail_length;
1261 /* parse and validate message. */
1262 msize = ntohs (message->size);
1263 if (msize < sizeof (struct PeerTrailSetupMessage))
1265 GNUNET_break_op (0);
1269 trail_setup = (struct PeerTrailSetupMessage *) message;
1270 trail_length = trail_setup->trail_length; // FIXME: should we use ntohl?
1273 sizeof (struct PeerTrailSetupMessage) +
1274 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1276 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1278 GNUNET_break_op (0);
1282 GNUNET_STATISTICS_update (GDS_stats,
1283 gettext_noop ("# TRAIL SETUP requests received"), 1,
1285 GNUNET_STATISTICS_update (GDS_stats,
1286 gettext_noop ("# TRAIL SETUP bytes received"), msize,
1290 * 1. Temporary logic using flag. Think something optmial.
1291 * 2. Set the value of flag correctly everywhere. */
1292 /* flag == 0, so this packet is for a friend. */
1293 if(trail_setup->flag == 0)
1295 /* This should always be the case. This packet is sent to me and I have received it. */
1296 if(0 == (GNUNET_CRYPTO_cmp_peer_identity(&(trail_setup->current_destination),&my_identity)))
1298 next_hop = find_successor(&(trail_setup->destination_finger),&(trail_setup->current_destination),&(trail_setup->flag));
1301 return GNUNET_SYSERR;
1305 /* The value of flag == 1, so this packet is send to an intermediate finger.
1306 So, either I am the finger or I am the part of trail. */
1307 if(0 != (GNUNET_CRYPTO_cmp_peer_identity(&(trail_setup->current_destination),&my_identity)))
1309 /* I am part of trail.
1310 * FIXME: Do we need to add a field prev_hop in this function call? For same
1311 * source and destination can we get different paths from different prev_hop. */
1312 next_hop = GDS_ROUTING_search(&(trail_setup->source_peer),&(trail_setup->destination_finger));
1314 /*FIXME: Add logic to call find_successor and compare the two peer ids
1315 and choose whichever is closest to the destination finger. */
1319 /* I am the current_destination finger */
1320 next_hop = find_successor(&(trail_setup->destination_finger),&(trail_setup->current_destination),&(trail_setup->flag));
1325 /* At this point, we have found our next hop. */
1326 /* Check if your are next hop, if yes then you have reached the final destination. */
1327 if(0 == (GNUNET_CRYPTO_cmp_peer_identity(next_hop,&my_identity)))
1329 GDS_NEIGHBOURS_handle_trail_setup_result(trail_setup);
1333 /* FIXME: Do we need to add an entry if we are just passing the packet to
1334 * one of the friend.*/
1335 if(trail_setup->flag == 1)
1337 /* This packet is sent to an intermediate finger. Add an entry in routing table. */
1338 GDS_ROUTING_add(&(trail_setup->source_peer),&(trail_setup->current_destination),next_hop);
1341 /* Add yourself to peer list. */
1342 peer_identity_trail = (struct GNUNET_PeerIdentity *)&trail_setup[1];
1343 memcpy(peer_identity_trail, next_hop, sizeof(struct GNUNET_PeerIdentity));
1345 /* FIXME: Are we correctly incrementing trail_length and msize.
1346 * Construct the new message to send it to next_hop. */
1347 trail_setup->trail_length++;
1348 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1350 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1351 pending->importance = 0; /* FIXME */
1352 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1353 trail_setup = (struct PeerTrailSetupMessage *) &pending[1];
1355 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1357 target_friend->pending_count++;
1358 process_friend_queue(target_friend);
1363 /* Add an entry to finger table.
1365 1.I have not added logic to find out the interval of keys for which
1366 a finger is responsible. Possible logic
1367 --> finger[i].interval = [finger[i].start,finger[i+1].start)
1368 * This logic needs to be implemented as we will need it for PUT/GET.
1369 * 2. Also, check the logic again when initializing fields of finger. */
1371 void finger_table_add(struct PeerTrailSetupResultMessage *result)
1373 /* 1. create a struct FingerInfo and copy respective members
1374 * of result into this struct.
1375 * Add the whole trail in your finger table,
1376 also add interval. */
1381 * Core handle for p2p trail construction result messages.
1382 * @param cls closure
1383 * @param message message
1384 * @param peer peer identity this notification is about
1385 * @return #GNUNET_YES (do not cut p2p connection)
1389 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1390 const struct GNUNET_MessageHeader *message)
1392 struct PeerTrailSetupResultMessage *trail_result;
1395 trail_result = (struct PeerTrailSetupResultMessage *)message;
1397 msize = ntohs (message->size);
1398 if(msize < sizeof (struct PeerTrailSetupResultMessage))
1404 /* This should always be the case. */
1405 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->current_destination), &my_identity)))
1407 /* Am I the destination? */
1408 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(&(trail_result->destination_peer), &my_identity)))
1410 finger_table_add(trail_result);
1415 /* read the trail list, get the next hop to send the packet to.*/
1416 /* TODO: Use the current index to access the correct element. */
1421 return GNUNET_SYSERR;
1426 * Initialize neighbours subsystem.
1427 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1430 GDS_NEIGHBOURS_init()
1432 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
1433 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
1434 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
1435 {&handle_dht_p2p_result, GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT, 0},
1436 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
1437 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
1441 /*ASK: What is ATS? Why do we need it? */
1442 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
1444 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
1445 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
1446 GNUNET_NO, core_handlers);
1447 if (core_api == NULL)
1448 return GNUNET_SYSERR;
1450 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1451 finger_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1458 * Shutdown neighbours subsystem.
1461 GDS_NEIGHBOURS_done ()
1463 if (NULL == core_api)
1465 GNUNET_CORE_disconnect (core_api);
1467 GNUNET_ATS_performance_done (atsAPI);
1470 /* FIXME: Once handle_core_disconnect is implemented, this assertion should not
1472 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
1473 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
1474 friend_peermap = NULL;
1476 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
1477 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
1478 finger_peermap = NULL;
1480 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
1482 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
1483 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
1489 * Get the ID of the local node.
1491 * @return identity of the local node
1493 struct GNUNET_PeerIdentity *
1494 GDS_NEIGHBOURS_get_id ()
1496 return &my_identity;
1500 /* end of gnunet-service-xdht_neighbours.c */