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. Add content and route replication later.
54 *2. Algorithm to shorten the trail length - one possible solution could be
55 * when we are in trail seutp result part. each peer in the trail check if any of
56 * the corresponding peers is its friend list. Then it can shortcut the path.
57 * But this will have O(n) run time at each peer, where n = trail_length.\
58 * or rather O(n)+O(n-1)+..O(1) =O(n).
59 * 3. Add a new field finger index to keep track of which finger respongs to which
61 * 4. As we start looking for finger from i = 0, using this parameter to
62 * generate random value does not look smart in send_find_finger_trail_message.
63 * 5. Need to store the interval in finger and friend table which will be used
64 * to find the correct successor.
69 * Maximum possible fingers of a peer.
71 #define MAX_FINGERS 256
74 * Maximum allowed number of pending messages per friend peer.
76 #define MAXIMUM_PENDING_PER_FRIEND 64
79 * How long at least to wait before sending another find finger trail request.
81 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
84 * How long at most to wait before sending another find finger trail request.
86 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 10)
89 * FIXME: Currently used in GDS_NEIGHBOURS_handle_trail_setup.
90 * I have just copied it from gnunet-service-dht_neighbours. Will it work here?
91 * How long at most to wait for transmission of a GET request to another peer?
93 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
95 GNUNET_NETWORK_STRUCT_BEGIN
98 * 1) Bloomfilter is not required for X-Vine.
99 * Keep the field now but remove it when implementing PUT/GET.
100 * 2) also, check the field of put/get/result if all are required for
106 struct PeerPutMessage
109 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
111 struct GNUNET_MessageHeader header;
116 uint32_t options GNUNET_PACKED;
121 uint32_t type GNUNET_PACKED;
126 uint32_t hop_count GNUNET_PACKED;
129 * Replication level for this message
131 uint32_t desired_replication_level GNUNET_PACKED;
134 * Length of the PUT path that follows (if tracked).
136 uint32_t put_path_length GNUNET_PACKED;
139 * When does the content expire?
141 struct GNUNET_TIME_AbsoluteNBO expiration_time;
144 * Bloomfilter (for peer identities) to stop circular routes
146 char bloomfilter[DHT_BLOOM_SIZE];
149 * The key we are storing under.
151 struct GNUNET_HashCode key;
153 /* put path (if tracked) */
163 struct PeerResultMessage
166 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
168 struct GNUNET_MessageHeader header;
173 uint32_t type GNUNET_PACKED;
176 * Length of the PUT path that follows (if tracked).
178 uint32_t put_path_length GNUNET_PACKED;
181 * Length of the GET path that follows (if tracked).
183 uint32_t get_path_length GNUNET_PACKED;
186 * When does the content expire?
188 struct GNUNET_TIME_AbsoluteNBO expiration_time;
191 * The key of the corresponding GET request.
193 struct GNUNET_HashCode key;
195 /* put path (if tracked) */
197 /* get path (if tracked) */
207 struct PeerGetMessage
210 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
212 struct GNUNET_MessageHeader header;
217 uint32_t options GNUNET_PACKED;
220 * Desired content type.
222 uint32_t type GNUNET_PACKED;
227 uint32_t hop_count GNUNET_PACKED;
230 * Desired replication level for this request.
232 uint32_t desired_replication_level GNUNET_PACKED;
235 * Size of the extended query.
237 uint32_t xquery_size;
240 * Bloomfilter mutator.
245 * Bloomfilter (for peer identities) to stop circular routes
247 char bloomfilter[DHT_BLOOM_SIZE];
250 * The key we are looking for.
252 struct GNUNET_HashCode key;
258 * A destination can be either a friend or finger.
260 enum current_destination_type
271 * P2P Trail setup message
272 * TODO: Take reference from put_path and get_path to understand how to use size of trail list.
274 struct PeerTrailSetupMessage
277 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
279 struct GNUNET_MessageHeader header;
282 * Source peer which wants to find trail to one of its finger.
284 struct GNUNET_PeerIdentity source_peer;
287 * Finger id to which we want to set up the trail to.
289 struct GNUNET_PeerIdentity destination_finger;
291 /* FIXME: Temporary field to handle current_destination properly.
292 If flag = 0, then this message's current_destination is a friend.
293 If flag = 1, then the message's current destination is a finger. */
296 enum current_destination_type current_destination_type;
299 * This field contains the peer to which this packet is forwarded.
301 struct GNUNET_PeerIdentity current_destination;
304 * Number of entries in trail list.
305 * FIXME: Is this data type correct?
306 * FIMXE: Is usage of GNUNET_PACKED correct?
308 uint32_t trail_length GNUNET_PACKED;
310 /* FIXME: Add this field later.
311 * The finger index in finger map.
312 unsigned int finger_index;*/
318 * P2P Trail setup Result message
320 struct PeerTrailSetupResultMessage
323 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
325 struct GNUNET_MessageHeader header;
328 * Finger to which we have found the path.
330 struct GNUNET_PeerIdentity finger;
333 * Peer which was looking for the trail to finger.
335 struct GNUNET_PeerIdentity destination_peer;
338 * This field contains the peer to which this packet is forwarded.
340 struct GNUNET_PeerIdentity current_destination;
343 * FIXME: Temporary field used to remember at which index we should read
344 * to get our next peer.
346 unsigned int current_index;
349 * Number of entries in trail list.
350 * FIXME: Is this data type correct?
351 * FIXME: Is usage of GNUNET_PACKED correct?
353 uint32_t trail_length GNUNET_PACKED;
357 GNUNET_NETWORK_STRUCT_END
361 * Linked list of messages to send to a particular other peer.
363 struct P2PPendingMessage
366 * Pointer to next item in the list
368 struct P2PPendingMessage *next;
371 * Pointer to previous item in the list
373 struct P2PPendingMessage *prev;
376 * When does this message time out?
378 struct GNUNET_TIME_Absolute timeout;
381 * Message importance level. FIXME: used? useful?
383 unsigned int importance;
386 * Actual message to be sent, allocated at the end of the struct:
387 * // msg = (cast) &pm[1];
388 * // memcpy (&pm[1], data, len);
390 const struct GNUNET_MessageHeader *msg;
396 * Linked List of peers which are part of trail to reach a particular Finger.
401 * Pointer to next item in the list
403 struct TrailPeerList *next;
406 * Pointer to previous item in the list
408 struct TrailPeerList *prev;
411 * An element in this trail list
413 struct GNUNET_PeerIdentity peer;
419 * Entry in friend_peermap.
424 * What is the identity of the peer?
426 struct GNUNET_PeerIdentity id;
429 * Count of outstanding messages for peer.
431 unsigned int pending_count;
435 * 1. We need some mechanism to check the interval of values for which
436 * a peer is responsible. If we can somehow maintain the peer id of
437 * next peer in the friend map, then we will be able to check. Or else
438 * we iterate over friend map twice will results in O(n^2) complexity.
439 * So, the tradeoff is between space and run time complexity.
440 * Peer id of next friend in friend peermap in 64 bit format.
442 uint64_t interval_end;
445 * Head of pending messages to be sent to this peer.
447 struct P2PPendingMessage *head;
450 * Tail of pending messages to be sent to this peer.
452 struct P2PPendingMessage *tail;
455 * TODO - How and where to use this?
456 * Core handle for sending messages to this peer.
458 struct GNUNET_CORE_TransmitHandle *th;
464 * Entry in finger_peermap.
469 * What is the identity of the finger peer?
471 struct GNUNET_PeerIdentity id;
474 * Start of the interval of keys for which this finger is responsible.
476 unsigned int interval_start;
479 * End of the interval of keys for which this finger is responsible.
481 unsigned int interval_end;
484 * List of peers in the trail.
486 const struct GNUNET_PeerIdentity *trail_peer_list;
491 unsigned int finger_index;
496 * Task that sends FIND FINGER TRAIL requests.
498 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
501 * Identity of this peer.
503 static struct GNUNET_PeerIdentity my_identity;
506 * FIXME: Not used anywhere in the code yet.
507 * Hash of the identity of this peer.
509 static struct GNUNET_HashCode my_identity_hash;
512 * Hash map of all the friends of a peer
514 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
517 * Hash map of all the fingers of a peer
519 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
522 * TODO: Ask whats the use of ATS.
525 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
530 static struct GNUNET_CORE_Handle *core_api;
533 * The current finger index that we have found trail to.
535 static unsigned int current_finger_index;
539 * Called when core is ready to send a message we asked for
540 * out to the destination.
542 * @param cls the 'struct PeerInfo' of the target peer
543 * @param size number of bytes available in buf
544 * @param buf where the callee should write the message
545 * @return number of bytes written to buf
548 core_transmit_notify (void *cls, size_t size, void *buf)
550 struct FriendInfo *peer = cls;
552 struct P2PPendingMessage *pending;
557 while ((NULL != (pending = peer->head)) &&
558 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
560 peer->pending_count--;
561 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
562 GNUNET_free (pending);
566 /* no messages pending */
572 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
573 GNUNET_CORE_PRIO_BEST_EFFORT,
574 GNUNET_TIME_absolute_get_remaining
575 (pending->timeout), &peer->id,
576 ntohs (pending->msg->size),
577 &core_transmit_notify, peer);
578 GNUNET_break (NULL != peer->th);
582 while ((NULL != (pending = peer->head)) &&
583 (size - off >= (msize = ntohs (pending->msg->size))))
585 GNUNET_STATISTICS_update (GDS_stats,
587 ("# Bytes transmitted to other peers"), msize,
589 memcpy (&cbuf[off], pending->msg, msize);
591 peer->pending_count--;
592 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
593 GNUNET_free (pending);
595 if (peer->head != NULL)
598 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
599 GNUNET_CORE_PRIO_BEST_EFFORT,
600 GNUNET_TIME_absolute_get_remaining
601 (pending->timeout), &peer->id, msize,
602 &core_transmit_notify, peer);
603 GNUNET_break (NULL != peer->th);
610 * Transmit all messages in the friend's message queue.
612 * @param peer message queue to process
615 process_friend_queue (struct FriendInfo *peer)
617 struct P2PPendingMessage *pending;
619 if (NULL == (pending = peer->head))
621 if (NULL != peer->th)
624 GNUNET_STATISTICS_update (GDS_stats,
626 ("# Bytes of bandwidth requested from core"),
627 ntohs (pending->msg->size), GNUNET_NO);
629 /* FIXME: Are we correctly initializing importance and pending. */
631 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
633 GNUNET_TIME_absolute_get_remaining
634 (pending->timeout), &peer->id,
635 ntohs (pending->msg->size),
636 &core_transmit_notify, peer);
637 GNUNET_break (NULL != peer->th);
643 * 1. trail_length is already incremented in the calling function
644 * i.e. in send_find_finger_trail, we send trail_length = 1, and then we
646 * 2. in handle_dht_p2p_trail_setup, we send trail_length = trail_length+1;
647 * and we already have added the id of current_destination in our peer_list so
648 * we need not to do anything else.
649 * Setup the trail message and forward it to a friend.
650 * @param source_peer Peer which wants to set up the trail to one of its finger.
651 * @param destination_finger Peer to which we want to set up the trail to.
652 * @param current_destination Current peer to which this message should be forwarded.
653 * @param trail_length Numbers of peers in the trail.
654 * @param trail_peer_list peers this request has traversed so far
657 GDS_NEIGHBOURS_handle_trail_setup(struct GNUNET_PeerIdentity *source_peer,
658 struct GNUNET_PeerIdentity *destination_finger,
659 struct FriendInfo *current_destination,
660 unsigned int trail_length,
661 struct GNUNET_PeerIdentity *trail_peer_list)
663 struct P2PPendingMessage *pending;
664 struct PeerTrailSetupMessage *tsm;
665 struct GNUNET_PeerIdentity *peer_list;
668 msize = sizeof(struct PeerTrailSetupMessage) +
669 (trail_length * sizeof(struct GNUNET_PeerIdentity));
671 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
677 if (current_destination->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
679 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
683 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
684 pending->importance = 0; /* FIXME */
685 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
686 tsm = (struct PeerTrailSetupMessage *) &pending[1];
687 pending->msg = &tsm->header;
688 tsm->header.size = htons (msize);
689 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
690 memcpy(&(tsm->destination_finger), destination_finger, sizeof (struct GNUNET_PeerIdentity));
691 memcpy(&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
692 memcpy(&(tsm->current_destination),&(current_destination->id), sizeof (struct GNUNET_PeerIdentity));
693 tsm->current_destination_type = htonl(FRIEND);
694 tsm->trail_length = htonl(trail_length);
695 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
696 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
698 if(NULL == trail_peer_list)
700 /* FIXME: Shift this logic to send_find_finger_trail_message. */
701 memcpy(peer_list, &(current_destination->id), sizeof(struct GNUNET_PeerIdentity));
705 memcpy(peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
708 GNUNET_CONTAINER_DLL_insert_tail (current_destination->head, current_destination->tail, pending);
709 current_destination->pending_count++;
710 process_friend_queue (current_destination);
715 * Handle a tail setup result message.
716 * @param destination_peer Peer which will get the trail to one of its finger.
717 * @param source_finger Peer to which the trail has been setup to.
718 * @param current_destination Current peer to which this message should be forwarded.
719 * @param trail_length Numbers of peers in the trail.
720 * @param trail_peer_list peers this request has traversed so far
721 * @param current_trail_index Index in trail_peer_list.
724 GDS_NEIGHBOURS_handle_trail_setup_result(struct GNUNET_PeerIdentity *destination_peer,
725 struct GNUNET_PeerIdentity *source_finger,
726 struct FriendInfo *current_destination,
727 unsigned int trail_length,
728 const struct GNUNET_PeerIdentity *trail_peer_list,
729 unsigned int current_trial_index)
731 struct P2PPendingMessage *pending;
732 struct PeerTrailSetupResultMessage *tsrm;
733 struct GNUNET_PeerIdentity *peer_list;
736 msize = sizeof(struct PeerTrailSetupMessage) +
737 (trail_length * sizeof(struct GNUNET_PeerIdentity));
739 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
745 if (current_destination->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
747 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
751 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
752 pending->importance = 0; /* FIXME */
753 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
754 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
755 pending->msg = &tsrm->header;
756 tsrm->header.size = htons (msize);
757 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
758 memcpy(&(tsrm->current_destination), &(current_destination->id), sizeof(struct GNUNET_PeerIdentity));
759 memcpy(&(tsrm->destination_peer), destination_peer, sizeof(struct GNUNET_PeerIdentity));
760 memcpy(&(tsrm->finger), source_finger, sizeof(struct GNUNET_PeerIdentity));
761 tsrm->trail_length = htonl(trail_length);
762 tsrm->current_index = htonl(current_trial_index);
763 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
764 memcpy(peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
766 /* Send the message to chosen friend. */
767 GNUNET_CONTAINER_DLL_insert_tail (current_destination->head, current_destination->tail, pending);
768 current_destination->pending_count++;
769 process_friend_queue (current_destination);
773 /**FIXME: Old implementation just to remove error
774 * TODO: Modify this function to handle our get request.
775 * Perform a GET operation. Forwards the given request to other
776 * peers. Does not lookup the key locally. May do nothing if this is
777 * the only peer in the network (or if we are the closest peer in the
780 * @param type type of the block
781 * @param options routing options
782 * @param desired_replication_level desired replication count
783 * @param hop_count how many hops did this request traverse so far?
784 * @param key key for the content
785 * @param xquery extended query
786 * @param xquery_size number of bytes in @a xquery
787 * @param reply_bf bloomfilter to filter duplicates
788 * @param reply_bf_mutator mutator for @a reply_bf
789 * @param peer_bf filter for peers not to select (again)
792 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
793 enum GNUNET_DHT_RouteOption options,
794 uint32_t desired_replication_level,
795 uint32_t hop_count, const struct GNUNET_HashCode * key,
796 const void *xquery, size_t xquery_size,
797 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
798 uint32_t reply_bf_mutator,
799 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
804 /**FIXME: Old implementation just to remove error.
805 * TODO: Modify this function to handle our put request.
806 * Perform a PUT operation. Forwards the given request to other
807 * peers. Does not store the data locally. Does not give the
808 * data to local clients. May do nothing if this is the only
809 * peer in the network (or if we are the closest peer in the
812 * @param type type of the block
813 * @param options routing options
814 * @param desired_replication_level desired replication count
815 * @param expiration_time when does the content expire
816 * @param hop_count how many hops has this message traversed so far
817 * @param bf Bloom filter of peers this PUT has already traversed
818 * @param key key for the content
819 * @param put_path_length number of entries in @a put_path
820 * @param put_path peers this request has traversed so far (if tracked)
821 * @param data payload to store
822 * @param data_size number of bytes in @a data
825 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
826 enum GNUNET_DHT_RouteOption options,
827 uint32_t desired_replication_level,
828 struct GNUNET_TIME_Absolute expiration_time,
830 struct GNUNET_CONTAINER_BloomFilter *bf,
831 const struct GNUNET_HashCode *key,
832 unsigned int put_path_length,
833 struct GNUNET_PeerIdentity *put_path,
834 const void *data, size_t data_size)
840 /**FIXME: Old implementation just to remove error.
841 * Handle a reply (route to origin). Only forwards the reply back to
842 * other peers waiting for it. Does not do local caching or
843 * forwarding to local clients.
845 * @param target neighbour that should receive the block (if still connected)
846 * @param type type of the block
847 * @param expiration_time when does the content expire
848 * @param key key for the content
849 * @param put_path_length number of entries in put_path
850 * @param put_path peers the original PUT traversed (if tracked)
851 * @param get_path_length number of entries in put_path
852 * @param get_path peers this reply has traversed so far (if tracked)
853 * @param data payload of the reply
854 * @param data_size number of bytes in data
857 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
858 enum GNUNET_BLOCK_Type type,
859 struct GNUNET_TIME_Absolute expiration_time,
860 const struct GNUNET_HashCode * key,
861 unsigned int put_path_length,
862 const struct GNUNET_PeerIdentity *put_path,
863 unsigned int get_path_length,
864 const struct GNUNET_PeerIdentity *get_path,
865 const void *data, size_t data_size)
872 * Randomly choose one of your friends from the friends_peer map
875 static struct FriendInfo *
876 select_random_friend()
878 unsigned int current_size;
881 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
882 struct GNUNET_PeerIdentity key_ret;
883 struct FriendInfo *friend;
885 current_size = GNUNET_CONTAINER_multipeermap_size(friend_peermap);
887 /* Element stored at this index in friend_peermap should be selected friend. */
888 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
890 /* Create an iterator for friend_peermap. */
891 iter = GNUNET_CONTAINER_multipeermap_iterator_create(friend_peermap);
893 /* Set the position of iterator to index. */
896 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,NULL,NULL))
902 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,&key_ret,(const void **)&friend))
912 * Compute finger_identity to which we want to setup the trail
913 * FIXME: If we maintain a index that is value of current_finger_index
914 * to which a particular entry in finger map corresponds then should we first
915 * check if there is already an entry for that index. If yes then don't
916 * search for trail to that finger.
917 * @return finger_identity
920 struct GNUNET_PeerIdentity *
921 compute_finger_identity()
923 struct GNUNET_PeerIdentity *finger_identity;
925 finger_identity = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
926 finger_identity = GNUNET_CRYPTO_compute_finger_identity(&my_identity,current_finger_index );
928 current_finger_index = (current_finger_index+1) % MAX_FINGERS;
930 /* Check if you already have an entry in finger_peermap for this finger_id.
931 If yes then again look for a new finger_id.
932 FIXME: Should we return NULL here?
933 if(NULL != GNUNET_CONTAINER_multipeermap_get(finger_peermap,finger_peer_id))
935 finger_peer_id = compute_finger_identity();
938 return finger_identity;
943 * TODO: Implement after testing friend/finger map.
944 * TODO: Handle the case when we already have a trail to our predecessor in
946 * This function will be needed when we are handling node joins/fails
947 * to maintain correct pointer to our predecessor and successor in the network.
948 * Find immediate predecessor in the network.
949 * @param me my own identity
950 * @return peer identity of immediate predecessor.
953 struct GNUNET_PeerIdentity *
954 find_immediate_predecessor()
956 /* Using your own peer identity, calculate your predecessor
957 * in the network. Try to setup path to this predecessor using
958 * the same logic as used for other fingers.
959 * If we already have a trail to our predecessor then send NULL and
960 * calling function should be able to handle that case.
967 * Task to send a find finger trail message. We attempt to find trail
968 * to our finger in the network.
970 * @param cls closure for this task
971 * @param tc the context under which the task is running
974 send_find_finger_trail_message (void *cls,
975 const struct GNUNET_SCHEDULER_TaskContext *tc)
977 struct GNUNET_PeerIdentity *finger_identity;
978 struct FriendInfo *friend;
979 struct GNUNET_TIME_Relative next_send_time;
981 /* We already have found trail to each of our possible fingers in the network. */
982 if (GNUNET_CONTAINER_multipeermap_size (finger_peermap) == MAX_FINGERS)
984 /* FIXME: I call find_immediate_predecessor when I have found trail to
985 * all the possible fingers in the network. But we need to find immediate
986 * predecessor when there is a node failure/join. It may happen before.
987 * Think of a better strategy to decide when to call this function.
988 * We can find trail to our immediate predecessor in the network.
990 finger_identity = find_immediate_predecessor();
992 if(NULL == finger_identity)
994 /* We already have a trail to reach to immediate predecessor. */
995 goto new_find_finger_trail_request;
1000 /* Find the finger_peer_id for which we want to setup the trail */
1001 finger_identity = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1002 finger_identity = compute_finger_identity();
1004 if(finger_identity == NULL)
1006 goto new_find_finger_trail_request;
1010 friend = GNUNET_malloc (sizeof (struct FriendInfo));
1011 friend = select_random_friend();
1013 /* We found a friend.*/
1016 GDS_NEIGHBOURS_handle_trail_setup(&my_identity,finger_identity,friend,1,NULL);
1019 /* FIXME: Should we be using current_finger_index to generate random interval.*/
1020 new_find_finger_trail_request:
1021 next_send_time.rel_value_us =
1022 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1023 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1024 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1025 (current_finger_index + 1));
1027 find_finger_trail_task =
1028 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1034 * Method called whenever a peer connects.
1036 * @param cls closure
1037 * @param peer peer identity this notification is about
1040 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer)
1042 struct FriendInfo *ret;
1044 /* Check for connect to self message */
1045 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1048 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1049 "Connected to %s\n",
1052 /* If peer already exists in our friend_peermap, then exit. */
1054 GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
1061 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
1064 ret = GNUNET_new (struct FriendInfo);
1067 GNUNET_assert (GNUNET_OK ==
1068 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
1070 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1072 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
1073 if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
1074 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
1079 * FIXME: Implement after testing finger/friend table setup.
1080 * Method called whenever a peer disconnects.
1082 * @param cls closure
1083 * @param peer peer identity this notification is about
1086 handle_core_disconnect (void *cls,
1087 const struct GNUNET_PeerIdentity *peer)
1090 * 1. remove the friend from the friend map.
1091 * 2. remove the trail for the fingers for which this peer was the first hop.
1092 * 3. start send_find_finger_trail for these fingers to find a new trail
1094 * 4. Also when a node gets disconnected, how should we update pointers of its
1095 * immediate successor and predecessor in the network ?
1096 * 5. Also how do we distribute the keys in the network?
1097 * 6. Here is case where we started put operation but a peer got disconnected and
1098 we removed the entry from the table. How to handle such a case.
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;
1114 GNUNET_CRYPTO_hash (identity,
1115 sizeof (struct GNUNET_PeerIdentity),
1121 * Core handler for p2p put requests.
1123 * @param cls closure
1124 * @param peer sender of the request
1125 * @param message message
1126 * @param peer peer identity this notification is about
1127 * @return #GNUNET_OK to keep the connection open,
1128 * #GNUNET_SYSERR to close it (signal serious error)
1131 handle_dht_p2p_put (void *cls,
1132 const struct GNUNET_PeerIdentity *peer,
1133 const struct GNUNET_MessageHeader *message)
1136 1. Search the friend,finger and check your own id to find the closest
1137 * predecessor the given key. --> find_predecessor()
1138 2. If self then datache_store
1139 3. If friend, then add to peer queue
1140 4. If finger, then add to the peer queue of the first hop.
1141 * in put message also maintain a field current_destination and use
1142 * same logic as trail setup to understand if you are just part of trail
1143 * to reach to a particular peer or you are endpoint of trail or just a friend.
1151 * Core handler for p2p get requests.
1153 * @param cls closure
1154 * @param peer sender of the request
1155 * @param message message
1156 * @return #GNUNET_OK to keep the connection open,
1157 * #GNUNET_SYSERR to close it (signal serious error)
1160 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1161 const struct GNUNET_MessageHeader *message)
1168 * Core handler for p2p result messages.
1170 * @param cls closure
1171 * @param message message
1172 * @param peer peer identity this notification is about
1173 * @return #GNUNET_YES (do not cut p2p connection)
1176 handle_dht_p2p_result (void *cls, const struct GNUNET_PeerIdentity *peer,
1177 const struct GNUNET_MessageHeader *message)
1185 * 1. Where do we use mod MAX_FINGERS?
1186 * 2. You are not using mod when searching for the closest successor of a finger.
1187 * 3. * 6. When I change the logic for find_successor, then I need to compare the interval
1188 * of two fingers. for that do I need to maintain a finger index and calculate
1190 * @param destination
1191 * @param flag Set the value of flag to 0, if next_hop = friend/1 if next_hop = finger.
1192 * @param current_destination We should set this field to finger id/friend id chosen to be next_hop.
1195 static struct GNUNET_PeerIdentity *
1196 find_successor(struct GNUNET_PeerIdentity *destination,
1197 struct GNUNET_PeerIdentity *current_destination,
1198 enum current_destination_type *type)
1201 * 1. Compare your identity with destination identity.
1202 * 2. Iterate over friend_map to find the peer identity with identity >= destination
1203 * 3. Iterate over finger_map to find the peer identity with identity >= destination
1204 * 4. Compare id,friend and finger to select one which is the least and still >= destination.
1205 * 5. If friend/my_identity then flag = 0
1206 * 6. If finger, then flag = 1.
1207 * 7. Set the current_destination value with chosen friend/finger/my_identity
1208 * 8. If finger, then search in your own finger table send the next hop to reach that finger.
1210 unsigned int friend_index;
1211 unsigned int finger_index;
1212 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1213 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1214 struct GNUNET_PeerIdentity key_ret;
1215 struct FriendInfo *friend;
1216 struct FingerInfo *finger;
1217 struct GNUNET_PeerIdentity *current_successor;
1219 /* FIXME: Temporary field used to understand if we got a friend or finger
1220 as next successor. find something better. */
1222 int finger_peer = 0;
1223 int friend_peer = 1;
1226 current_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1228 /* initialize current_successor with your own identity. */
1229 memcpy(current_successor,&my_identity,sizeof(struct GNUNET_PeerIdentity));
1232 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1234 /*iterate over friend map till you reach a peer id such that destination <= peer id */
1235 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1237 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1239 if(0 > GNUNET_CRYPTO_cmp_peer_identity(&friend->id,destination) ||
1240 (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id,destination)))
1242 /* If yes then check if finger <= current_successor */
1243 if(0 < GNUNET_CRYPTO_cmp_peer_identity(&friend->id,current_successor) ||
1244 (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id,current_successor)))
1246 memcpy(current_successor,friend,sizeof(struct GNUNET_PeerIdentity));
1247 successor = friend_peer;
1254 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1255 /* iterate over finger map till you reach a peer id such that destination <= peer id */
1256 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1258 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1260 if(0 > GNUNET_CRYPTO_cmp_peer_identity(&finger->id,destination) ||
1261 (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->id,destination)))
1263 /* If yes then check if finger <= current_friend_successor */
1264 if(0 < GNUNET_CRYPTO_cmp_peer_identity(&finger->id,current_successor)
1265 || (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->id,current_successor)))
1267 memcpy(current_successor,finger,sizeof(struct GNUNET_PeerIdentity));
1268 successor = finger_peer;
1274 memcpy(current_destination,current_successor,sizeof(struct GNUNET_PeerIdentity));
1276 if(successor == finger_peer)
1282 /* The successor is either my_identity or friend. */
1286 return current_successor;
1291 * @param cls closure
1292 * @param message message
1293 * @param peer peer identity this notification is about
1294 * @return #GNUNET_YES
1297 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1298 const struct GNUNET_MessageHeader *message)
1300 struct PeerTrailSetupMessage *trail_setup;
1301 struct GNUNET_PeerIdentity *next_hop;
1302 struct FriendInfo *target_friend;
1303 struct FriendInfo *new_target_friend;
1305 uint32_t trail_length;
1306 enum current_destination_type peer_type;
1307 struct GNUNET_PeerIdentity *trail_peer_list;
1308 uint32_t current_trail_index;
1309 struct GNUNET_PeerIdentity *next_peer;
1311 /* parse and validate message. */
1312 msize = ntohs (message->size);
1313 if (msize < sizeof (struct PeerTrailSetupMessage))
1315 GNUNET_break_op (0);
1319 trail_setup = (struct PeerTrailSetupMessage *) message;
1320 trail_length = ntohl (trail_setup->trail_length);
1321 peer_type = ntohl (trail_setup->current_destination_type);
1322 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_setup[1];
1325 sizeof (struct PeerTrailSetupMessage) +
1326 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1328 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1330 GNUNET_break_op (0);
1335 GNUNET_STATISTICS_update (GDS_stats,
1336 gettext_noop ("# TRAIL SETUP requests received"), 1,
1338 GNUNET_STATISTICS_update (GDS_stats,
1339 gettext_noop ("# TRAIL SETUP bytes received"), msize,
1342 if(peer_type == FRIEND)
1344 if(0 == (GNUNET_CRYPTO_cmp_peer_identity(&(trail_setup->current_destination),&my_identity)))
1346 next_hop = find_successor(&(trail_setup->destination_finger),&(trail_setup->current_destination),&(peer_type));
1349 return GNUNET_SYSERR;
1353 if(0 != (GNUNET_CRYPTO_cmp_peer_identity(&(trail_setup->current_destination),&my_identity)))
1355 /* I am part of trail. */
1356 next_hop = GDS_ROUTING_search(&(trail_setup->source_peer),&(trail_setup->destination_finger));
1359 call find_successor and compare the two peer ids
1360 and choose whichever is closest to the destination finger. */
1364 /* I am the current_destination finger */
1365 next_hop = find_successor(&(trail_setup->destination_finger),&(trail_setup->current_destination),&(peer_type));
1369 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1371 /* Add yourself to list of peers that trail setup message have traversed so far
1372 and increment trail length. */
1373 struct GNUNET_PeerIdentity *peer_list;
1374 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1));
1375 memcpy(peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1376 memcpy(&peer_list[trail_length], next_hop, sizeof (struct GNUNET_PeerIdentity));
1379 /* Check if you are next hop, if yes then you have reached the final destination. */
1380 if(0 == (GNUNET_CRYPTO_cmp_peer_identity(next_hop,&my_identity)))
1382 /* FIXME: Trail length should be const. */
1383 if(trail_length >= 1)
1385 current_trail_index = trail_length - 2;
1386 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); //FIXME: Do we need to allocate the memory?
1387 memcpy(next_peer, &peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
1389 new_target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
1391 /* FIXME: It does not find a friend. Could be possible error in find_successor
1392 function. Change the logic in find_successor and change it again. */
1393 /*if(GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains(friend_peermap,new_target_friend))
1396 return GNUNET_SYSERR;
1399 GDS_NEIGHBOURS_handle_trail_setup_result(&(trail_setup->source_peer),
1400 &(trail_setup->destination_finger),
1401 new_target_friend, trail_length,
1402 peer_list,current_trail_index);
1407 if(peer_type == FINGER)
1409 GDS_ROUTING_add(&(trail_setup->source_peer),&(trail_setup->current_destination),next_hop);
1412 GDS_NEIGHBOURS_handle_trail_setup(&(trail_setup->source_peer),
1413 &(trail_setup->destination_finger),
1415 trail_setup->trail_length,
1422 * FIXME : Add interval field.
1423 * Add an entry in finger table.
1424 * @param finger Finger to be added to finger table
1425 * @param peer_list peers this request has traversed so far
1426 * @param trail_length Numbers of peers in the trail.
1429 void finger_table_add(struct GNUNET_PeerIdentity *finger,
1430 const struct GNUNET_PeerIdentity *peer_list,
1431 unsigned int trail_length)
1433 struct FingerInfo *finger_entry;
1434 finger_entry = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
1435 memcpy(&(finger_entry->id), finger, sizeof(struct GNUNET_PeerIdentity));
1436 memcpy(&(finger_entry->trail_peer_list), peer_list, sizeof(struct GNUNET_PeerIdentity)
1442 * Core handle for p2p trail construction result messages.
1443 * @param cls closure
1444 * @param message message
1445 * @param peer peer identity this notification is about
1446 * @return #GNUNET_YES
1449 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1450 const struct GNUNET_MessageHeader *message)
1452 struct PeerTrailSetupResultMessage *trail_result;
1454 uint32_t trail_length;
1455 const struct GNUNET_PeerIdentity *trail_peer_list;
1456 uint32_t current_trail_index;
1457 struct GNUNET_PeerIdentity *next_peer;
1458 struct FriendInfo *target_friend;
1460 msize = ntohs (message->size);
1461 if (msize < sizeof (struct PeerTrailSetupMessage))
1463 GNUNET_break_op (0);
1467 trail_result = (struct PeerTrailSetupResultMessage *) message;
1468 trail_length = ntohl (trail_result->trail_length);
1469 current_trail_index = ntohl(trail_result->current_index);
1470 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
1473 sizeof (struct PeerTrailSetupResultMessage) +
1474 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1476 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1478 GNUNET_break_op (0);
1482 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->current_destination), &my_identity)))
1484 /* Am I the destination? */
1485 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(&(trail_result->destination_peer), &my_identity)))
1487 finger_table_add(&(trail_result->finger), trail_peer_list,trail_length);
1492 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1493 current_trail_index = current_trail_index - 1;
1494 memcpy(next_peer, &(trail_peer_list[trail_length-1]), sizeof (struct GNUNET_PeerIdentity));
1495 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
1497 GDS_NEIGHBOURS_handle_trail_setup_result(&(trail_result->destination_peer),
1498 &(trail_result->finger),
1499 target_friend, trail_length,
1500 trail_peer_list,current_trail_index);
1505 return GNUNET_SYSERR;
1510 * Initialize neighbours subsystem.
1511 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1514 GDS_NEIGHBOURS_init()
1516 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
1517 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
1518 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
1519 {&handle_dht_p2p_result, GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT, 0},
1520 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
1521 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
1525 /*ASK: What is ATS? Why do we need it? */
1526 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
1528 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
1529 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
1530 GNUNET_NO, core_handlers);
1531 if (core_api == NULL)
1532 return GNUNET_SYSERR;
1534 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1535 finger_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1542 * Shutdown neighbours subsystem.
1545 GDS_NEIGHBOURS_done ()
1547 if (NULL == core_api)
1550 GNUNET_CORE_disconnect (core_api);
1552 GNUNET_ATS_performance_done (atsAPI);
1555 /* FIXME: Once handle_core_disconnect is implemented, both below assertion should not
1557 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
1558 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
1559 friend_peermap = NULL;
1561 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
1562 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
1563 finger_peermap = NULL;
1565 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
1567 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
1568 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
1574 * Get the ID of the local node.
1576 * @return identity of the local node
1578 struct GNUNET_PeerIdentity *
1579 GDS_NEIGHBOURS_get_id ()
1581 return &my_identity;
1585 /* end of gnunet-service-xdht_neighbours.c */