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. Remove extra comments - FIXME,TODO,SUPU
54 * 2. Use GNUNET_Log to debug
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 GNUNET_NETWORK_STRUCT_BEGIN
81 * 1) Bloomfilter is not required for X-Vine.
82 * Keep the field now but remove it when implementing PUT/GET.
83 * 2) also, check the field of put/get/result if all are required for
92 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
94 struct GNUNET_MessageHeader header;
99 uint32_t options GNUNET_PACKED;
104 uint32_t type GNUNET_PACKED;
109 uint32_t hop_count GNUNET_PACKED;
112 * Replication level for this message
114 uint32_t desired_replication_level GNUNET_PACKED;
117 * Length of the PUT path that follows (if tracked).
119 uint32_t put_path_length GNUNET_PACKED;
122 * When does the content expire?
124 struct GNUNET_TIME_AbsoluteNBO expiration_time;
127 * Bloomfilter (for peer identities) to stop circular routes
129 char bloomfilter[DHT_BLOOM_SIZE];
132 * The key we are storing under.
134 struct GNUNET_HashCode key;
136 /* put path (if tracked) */
146 struct PeerResultMessage
149 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
151 struct GNUNET_MessageHeader header;
156 uint32_t type GNUNET_PACKED;
159 * Length of the PUT path that follows (if tracked).
161 uint32_t put_path_length GNUNET_PACKED;
164 * Length of the GET path that follows (if tracked).
166 uint32_t get_path_length GNUNET_PACKED;
169 * When does the content expire?
171 struct GNUNET_TIME_AbsoluteNBO expiration_time;
174 * The key of the corresponding GET request.
176 struct GNUNET_HashCode key;
178 /* put path (if tracked) */
180 /* get path (if tracked) */
190 struct PeerGetMessage
193 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
195 struct GNUNET_MessageHeader header;
200 uint32_t options GNUNET_PACKED;
203 * Desired content type.
205 uint32_t type GNUNET_PACKED;
210 uint32_t hop_count GNUNET_PACKED;
213 * Desired replication level for this request.
215 uint32_t desired_replication_level GNUNET_PACKED;
218 * Size of the extended query.
220 uint32_t xquery_size;
223 * Bloomfilter mutator.
228 * Bloomfilter (for peer identities) to stop circular routes
230 char bloomfilter[DHT_BLOOM_SIZE];
233 * The key we are looking for.
235 struct GNUNET_HashCode key;
241 * FIXME: I have defined this struct between GNUNET_NETWORK_STRUCT_BEGIN. Is
242 * it correct? Also, I am using the same struct inside finger info and trailsetup
243 * trailsetupresult message. Is it correct? Verify while testing. */
245 * Linked List of peers which are part of trail to reach a particular Finger.
250 * Pointer to next item in the list
252 struct TrailPeerList *next;
255 * Pointer to previous item in the list
257 struct TrailPeerList *prev;
260 * An element in this trail list
262 struct GNUNET_PeerIdentity *peer;
268 * FIXME : I am using the same struct TrailPeerList in both finger info
269 * and peertrailsetupmessage. Verify if its okay.
270 * P2P Trail setup message
272 struct PeerTrailSetupMessage
275 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
277 struct GNUNET_MessageHeader header;
280 * Source peer which wants to find trail to one of its finger.
282 struct GNUNET_PeerIdentity *source_peer;
285 * Finger id to which we want to set up the trail to.
287 struct GNUNET_PeerIdentity *destination_finger;
290 * This field contains the peer to which this packet is forwarded.
292 struct GNUNET_PeerIdentity *current_destination;
295 * Head of trail list.
297 struct TrailPeerList *head;
300 * Tail of trail list.
302 struct TrailPeerList *tail;
308 * P2P Trail setup Result message
310 struct PeerTrailSetupResultMessage
313 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
315 struct GNUNET_MessageHeader header;
318 * Finger to which we have found the path.
320 struct GNUNET_PeerIdentity *finger;
323 * Peer which was looking for the trail to finger.
325 struct GNUNET_PeerIdentity *destination_peer;
328 * This field contains the peer to which this packet is forwarded.
330 struct GNUNET_PeerIdentity *current_destination;
333 * Head of trail list.
335 struct TrailPeerList *head;
338 * Tail of trail list.
340 struct TrailPeerList *tail;
344 GNUNET_NETWORK_STRUCT_END
348 * Linked list of messages to send to a particular other peer.
350 struct P2PPendingMessage
353 * Pointer to next item in the list
355 struct P2PPendingMessage *next;
358 * Pointer to previous item in the list
360 struct P2PPendingMessage *prev;
363 * When does this message time out?
365 struct GNUNET_TIME_Absolute timeout;
368 * Message importance level. FIXME: used? useful?
370 unsigned int importance;
373 * Actual message to be sent, allocated at the end of the struct:
374 * // msg = (cast) &pm[1];
375 * // memcpy (&pm[1], data, len);
377 const struct GNUNET_MessageHeader *msg;
382 * Entry in friend_peers map.
388 * What is the identity of the peer?
390 struct GNUNET_PeerIdentity id;
393 * Count of outstanding messages for peer.
395 unsigned int pending_count;
398 * Head of pending messages to be sent to this peer.
400 struct P2PPendingMessage *head;
403 * Tail of pending messages to be sent to this peer.
405 struct P2PPendingMessage *tail;
408 * TODO - How and where to use this?
409 * Core handle for sending messages to this peer.
411 struct GNUNET_CORE_TransmitHandle *th;
416 * Entry in finger_peers map.
421 * What is the identity of the finger peer?
423 struct GNUNET_PeerIdentity id;
426 * Start of the interval of keys for which this finger is responsible.
428 unsigned int interval_start;
431 * End of the interval of keys for which this finger is responsible.
433 unsigned int interval_end;
436 * Head of trail list.
438 struct TrailPeerList *head;
441 * Tail of trail list.
443 struct TrailPeerList *tail;
449 * Task that sends FIND FINGER TRAIL requests.
451 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
454 * Identity of this peer.
456 static struct GNUNET_PeerIdentity my_identity;
459 * FIXME: Not used anywhere in the code yet.
460 * Hash of the identity of this peer.
462 static struct GNUNET_HashCode my_identity_hash;
465 * Hash map of all the friends of a peer
467 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peers;
470 * Hash map of all the fingers of a peer
472 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peers;
475 * TODO: Ask whats the use of ATS.
478 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
483 static struct GNUNET_CORE_Handle *core_api;
486 * The current finger index that we have found trail to.
488 static unsigned int current_finger_index;
492 * Called when core is ready to send a message we asked for
493 * out to the destination.
495 * @param cls the 'struct FriendInfo' of the target friend peer
496 * @param size number of bytes available in buf
497 * @param buf where the callee should write the message
498 * @return number of bytes written to buf
501 core_transmit_notify (void *cls, size_t size, void *buf)
503 struct FriendInfo *peer = cls;
505 struct P2PPendingMessage *pending;
510 while ((NULL != (pending = peer->head)) &&
511 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
513 peer->pending_count--;
514 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
515 GNUNET_free (pending);
519 /* no messages pending */
525 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
527 GNUNET_TIME_absolute_get_remaining
528 (pending->timeout), &peer->id,
529 ntohs (pending->msg->size),
530 &core_transmit_notify, peer);
531 GNUNET_break (NULL != peer->th);
535 while ((NULL != (pending = peer->head)) &&
536 (size - off >= (msize = ntohs (pending->msg->size))))
538 GNUNET_STATISTICS_update (GDS_stats,
540 ("# Bytes transmitted to other peers"), msize,
542 memcpy (&cbuf[off], pending->msg, msize);
544 peer->pending_count--;
545 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
546 GNUNET_free (pending);
548 if (peer->head != NULL)
551 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
553 GNUNET_TIME_absolute_get_remaining
554 (pending->timeout), &peer->id, msize,
555 &core_transmit_notify, peer);
556 GNUNET_break (NULL != peer->th);
563 * Transmit all messages in the friend's message queue.
565 * @param peer message queue to process
568 process_friend_queue (struct FriendInfo *peer)
570 struct P2PPendingMessage *pending;
572 if (NULL == (pending = peer->head))
574 if (NULL != peer->th)
576 GNUNET_STATISTICS_update (GDS_stats,
578 ("# Bytes of bandwidth requested from core"),
579 ntohs (pending->msg->size), GNUNET_NO);
581 /*FIXME : here I don't know the use of importance, time out
582 Will check at run time if its all correct. */
584 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
586 GNUNET_TIME_absolute_get_remaining
587 (pending->timeout), &peer->id,
588 ntohs (pending->msg->size),
589 &core_transmit_notify, peer);
590 GNUNET_break (NULL != peer->th);
595 * FIXME: Check the parameters.
596 * Set up the trial message and forwards this message to friend.
598 * @param Finger id to which we want to setup the trail.
599 * @param Friend id through which we will try to setup the trail.
602 GDS_NEIGHBOURS_trail_setup(struct GNUNET_PeerIdentity *finger_id,
603 struct FriendInfo *target_friend)
606 * FIXME: check if pending message actually contains the correct data.
608 struct P2PPendingMessage *pending;
609 /* FIXME: why I have defined as **? verify by testing. */
610 struct PeerTrailSetupMessage *tsm;
612 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
614 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
618 /* SUPU: Verify if this copy between pending message, tsm is correct? */
619 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
620 /*SUPU: What does this code do? Does this initialize pending with
622 tsm = (struct PeerTrailSetupMessage *) &pending[1];
623 pending->msg = &tsm->header;
624 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
625 tsm->destination_finger = finger_id;
626 tsm->source_peer = &my_identity;
627 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
628 target_friend->pending_count++;
629 process_friend_queue(target_friend);
633 /**FIXME: Old implementation just to remove error
634 * TODO: Modify this function to handle our get request.
635 * Perform a GET operation. Forwards the given request to other
636 * peers. Does not lookup the key locally. May do nothing if this is
637 * the only peer in the network (or if we are the closest peer in the
640 * @param type type of the block
641 * @param options routing options
642 * @param desired_replication_level desired replication count
643 * @param hop_count how many hops did this request traverse so far?
644 * @param key key for the content
645 * @param xquery extended query
646 * @param xquery_size number of bytes in @a xquery
647 * @param reply_bf bloomfilter to filter duplicates
648 * @param reply_bf_mutator mutator for @a reply_bf
649 * @param peer_bf filter for peers not to select (again)
652 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
653 enum GNUNET_DHT_RouteOption options,
654 uint32_t desired_replication_level,
655 uint32_t hop_count, const struct GNUNET_HashCode * key,
656 const void *xquery, size_t xquery_size,
657 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
658 uint32_t reply_bf_mutator,
659 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
664 /**FIXME: Old implementation just to remove error.
665 * TODO: Modify this function to handle our put request.
666 * Perform a PUT operation. Forwards the given request to other
667 * peers. Does not store the data locally. Does not give the
668 * data to local clients. May do nothing if this is the only
669 * peer in the network (or if we are the closest peer in the
672 * @param type type of the block
673 * @param options routing options
674 * @param desired_replication_level desired replication count
675 * @param expiration_time when does the content expire
676 * @param hop_count how many hops has this message traversed so far
677 * @param bf Bloom filter of peers this PUT has already traversed
678 * @param key key for the content
679 * @param put_path_length number of entries in @a put_path
680 * @param put_path peers this request has traversed so far (if tracked)
681 * @param data payload to store
682 * @param data_size number of bytes in @a data
685 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
686 enum GNUNET_DHT_RouteOption options,
687 uint32_t desired_replication_level,
688 struct GNUNET_TIME_Absolute expiration_time,
690 struct GNUNET_CONTAINER_BloomFilter *bf,
691 const struct GNUNET_HashCode *key,
692 unsigned int put_path_length,
693 struct GNUNET_PeerIdentity *put_path,
694 const void *data, size_t data_size)
700 /**FIXME: Old implementation just to remove error.
701 * Handle a reply (route to origin). Only forwards the reply back to
702 * other peers waiting for it. Does not do local caching or
703 * forwarding to local clients.
705 * @param target neighbour that should receive the block (if still connected)
706 * @param type type of the block
707 * @param expiration_time when does the content expire
708 * @param key key for the content
709 * @param put_path_length number of entries in put_path
710 * @param put_path peers the original PUT traversed (if tracked)
711 * @param get_path_length number of entries in put_path
712 * @param get_path peers this reply has traversed so far (if tracked)
713 * @param data payload of the reply
714 * @param data_size number of bytes in data
717 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
718 enum GNUNET_BLOCK_Type type,
719 struct GNUNET_TIME_Absolute expiration_time,
720 const struct GNUNET_HashCode * key,
721 unsigned int put_path_length,
722 const struct GNUNET_PeerIdentity *put_path,
723 unsigned int get_path_length,
724 const struct GNUNET_PeerIdentity *get_path,
725 const void *data, size_t data_size)
733 * I have written a code where
734 * 1. I choose a random index from 0 to current size of my map.
735 * 2. Create an iterator.
736 * 3. set the iterator value to the current index id.
737 * 4. get the element stored at that index id.
738 * 5. return the index to calling function.
739 * I have not yet tested this function and I am not sure if its correct.
740 * Randomly choose one of your friends from the friends_peer map
743 static struct FriendInfo *
746 unsigned int current_size;
749 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
750 struct GNUNET_PeerIdentity key_ret;
751 struct FriendInfo *friend;
753 current_size = GNUNET_CONTAINER_multipeermap_size(friend_peers);
755 /* Element stored at this index in friend_peers map should be chosen friend. */
756 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
758 /* Create an iterator for friend_peers map. */
759 iter = GNUNET_CONTAINER_multipeermap_iterator_create(friend_peers);
761 /* Set the position of iterator to index. */
764 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,NULL,NULL))
770 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,&key_ret,(const void **)&friend))
780 * Find finger id to which we want to setup the trail
784 struct GNUNET_PeerIdentity *
785 compute_finger_identity()
787 struct GNUNET_PeerIdentity *finger_identity;
789 finger_identity = GNUNET_CRYPTO_compute_finger(&my_identity,current_finger_index);
791 current_finger_index = (current_finger_index+1) % MAX_FINGERS;
793 /* Check if you already have an entry in finger_peers for this finger_id.
794 If yes then again look for a new finger_id.
795 FIXME: Should we return NULL here?
796 if(NULL != GNUNET_CONTAINER_multipeermap_get(finger_peers,finger_peer_id))
798 finger_peer_id = compute_finger_identity();
800 return finger_identity;
804 * TODO: Implement after testing friend/finger map.
805 * TODO: Handle the case when we already have a trail to our predecessor in
807 * This function will be needed when we are handling node joins/fails
808 * to maintain correct pointer to our predecessor and successor in the network.
809 * Find immediate predecessor in the network.
810 * @param me my own identity
811 * @return peer identity of immediate predecessor.
814 struct GNUNET_PeerIdentity *
815 find_immediate_predecessor()
817 /* Using your own peer identity, calculate your predecessor
818 * in the network. Try to setup path to this predecessor using
819 * the same logic as used for other fingers.
820 * If we already have a trail to our predecessor then send NULL and
821 * calling function should be able to handle that case.
828 * Task to send a find finger trail message. We attempt to find trail
829 * to our finger in the network.
831 * @param cls closure for this task
832 * @param tc the context under which the task is running
835 send_find_finger_trail_message (void *cls,
836 const struct GNUNET_SCHEDULER_TaskContext *tc)
838 struct GNUNET_PeerIdentity *finger_peer_id;
839 struct FriendInfo *friend_peer_id;
840 struct GNUNET_TIME_Relative next_send_time;
842 /* We already have found trail to each of our possible fingers in the network. */
843 if (GNUNET_CONTAINER_multipeermap_size(finger_peers) == MAX_FINGERS)
845 /* We can find trail to our immediate predecessor in the network. */
846 finger_peer_id = find_immediate_predecessor();
847 if(NULL == finger_peer_id)
849 /* We already have a trail to reach to immediate predecessor. */
850 goto new_find_trail_request;
855 /* Find the finger_peer_id for which we want to setup the trail */
856 finger_peer_id = compute_finger_identity();
859 /* Choose a friend randomly from your friend_peers map. */
860 friend_peer_id = get_random_friend();
862 /* We found a friend.*/
863 if(NULL != friend_peer_id)
864 GDS_NEIGHBOURS_trail_setup(finger_peer_id, friend_peer_id);
867 new_find_trail_request:
869 next_send_time.rel_value_us =
870 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
871 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
872 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
873 (current_finger_index + 1));
875 find_finger_trail_task =
876 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
882 * Method called whenever a peer connects.
885 * @param peer peer identity this notification is about
888 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer)
890 struct FriendInfo *ret;
892 /* Check for connect to self message */
893 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
896 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
900 /* If peer already exists in our friend_peers, then exit. */
902 GNUNET_CONTAINER_multipeermap_contains (friend_peers,
909 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
912 ret = GNUNET_new (struct FriendInfo);
915 GNUNET_assert (GNUNET_OK ==
916 GNUNET_CONTAINER_multipeermap_put (friend_peers,
918 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
920 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
921 if (1 == GNUNET_CONTAINER_multipeermap_size(friend_peers))
922 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
927 * FIXME: Implement after testing finger/friend table setup.
928 * Method called whenever a peer disconnects.
931 * @param peer peer identity this notification is about
934 handle_core_disconnect (void *cls,
935 const struct GNUNET_PeerIdentity *peer)
938 * 1. remove the friend from the friend map.
939 * 2. remove the trail for the fingers for which this peer was the first hop.
940 * 3. start send_find_finger_trail for these fingers to find a new trail
942 * 4. Also when a node gets disconnected, how should we update pointers of its
943 * immediate successor and predecessor in the network ?
944 * 5. Also how do we distribute the keys in the network?
945 * 6. Here is case where we started put operation but a peer got disconnected and
946 we removed the entry from the table. How to handle such a case.
952 * To be called on core init/fail.
954 * @param cls service closure
955 * @param identity the public identity of this peer
958 core_init (void *cls,
959 const struct GNUNET_PeerIdentity *identity)
961 my_identity = *identity;
962 GNUNET_CRYPTO_hash (identity,
963 sizeof (struct GNUNET_PeerIdentity),
969 * Core handler for p2p put requests.
972 * @param peer sender of the request
973 * @param message message
974 * @param peer peer identity this notification is about
975 * @return #GNUNET_OK to keep the connection open,
976 * #GNUNET_SYSERR to close it (signal serious error)
979 handle_dht_p2p_put (void *cls,
980 const struct GNUNET_PeerIdentity *peer,
981 const struct GNUNET_MessageHeader *message)
984 1. Search the friend,finger and check your own id to find the closest
985 * predecessor the given key. --> find_predecessor()
986 2. If self then datache_store
987 3. If friend, then add to peer queue
988 4. If finger, then add to the peer queue of the first hop.
989 * in put message also maintain a field current_destination and use
990 * same logic as trail setup to understand if you are just part of trail
991 * to reach to a particular peer or you are endpoint of trail or just a friend.
999 * Core handler for p2p get requests.
1001 * @param cls closure
1002 * @param peer sender of the request
1003 * @param message message
1004 * @return #GNUNET_OK to keep the connection open,
1005 * #GNUNET_SYSERR to close it (signal serious error)
1008 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1009 const struct GNUNET_MessageHeader *message)
1016 * Core handler for p2p result messages.
1018 * @param cls closure
1019 * @param message message
1020 * @param peer peer identity this notification is about
1021 * @return #GNUNET_YES (do not cut p2p connection)
1024 handle_dht_p2p_result (void *cls, const struct GNUNET_PeerIdentity *peer,
1025 const struct GNUNET_MessageHeader *message)
1032 * FIXME:1. Check if current_destination field is set correctly.
1033 * 2. Is it correct to use GNUNET_CMP_PEER_IDENTITY to find out the successor
1035 * 3. We should check the interval of the keys for which a peer is responsible
1036 * when we are looking to find the correct peer to store a key. But
1037 * --> How do we maintain this interval?
1038 * --> Should we check this interval when we are looking for trail to a finger
1039 * as in this function?
1040 * The code flow seems to be very large. Could do better.
1041 * @param destination peer id's predecessor we are looking for.
1044 static struct GNUNET_PeerIdentity *
1045 find_successor(struct GNUNET_PeerIdentity *destination, struct GNUNET_PeerIdentity *current_destination)
1047 unsigned int friend_index;
1048 unsigned int finger_index;
1049 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1050 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1051 struct GNUNET_PeerIdentity key_ret;
1052 struct FriendInfo *friend;
1053 struct FingerInfo *finger;
1054 struct GNUNET_PeerIdentity *current_successor;
1056 /* FIXME: Temporary field used to understand if we got a friend or finger
1057 as next successor. find something better.*/
1059 int finger_peer = 0;
1060 int friend_peer = 1;
1063 current_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1065 /* initialize current_successor with your own identity.*/
1066 memcpy(current_successor,&my_identity,sizeof(struct GNUNET_PeerIdentity));
1069 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peers);
1071 /*iterate over friend map till you reach a peer id such that destination <= peer id */
1072 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peers); friend_index++)
1074 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1076 if(0 > GNUNET_CRYPTO_cmp_peer_identity(&friend->id,destination) ||
1077 (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id,destination)))
1079 /* If yes then check if finger <= current_successor */
1080 if(0 < GNUNET_CRYPTO_cmp_peer_identity(&friend->id,current_successor) ||
1081 (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id,current_successor)))
1083 memcpy(current_successor,friend,sizeof(struct GNUNET_PeerIdentity));
1084 successor = friend_peer;
1091 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peers);
1092 /*iterate over finger map till you reach a peer id such that destination <= peer id */
1093 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peers); finger_index++)
1095 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1097 if(0 > GNUNET_CRYPTO_cmp_peer_identity(&finger->id,destination) ||
1098 (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->id,destination)))
1100 /* If yes then check if finger <= current_friend_successor */
1101 if(0 < GNUNET_CRYPTO_cmp_peer_identity(&finger->id,current_successor)
1102 || (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->id,current_successor)))
1104 memcpy(current_successor,finger,sizeof(struct GNUNET_PeerIdentity));
1105 successor = finger_peer;
1111 if(successor == finger_peer)
1113 memcpy(current_destination,current_successor,sizeof(struct GNUNET_PeerIdentity));
1117 /* The successor is either my_identity or friend. */
1118 current_destination = NULL;
1121 return current_successor;
1125 /* Traverse the trail list to find the prev hop to store in routing table. */
1127 struct GNUNET_PeerIdentity *
1128 find_trail_list_prev_hop(struct PeerTrailSetupMessage *trail_result)
1130 /*FIXME: I don't see any function in existing dll implementation, to
1131 just read the dll backward or forward. So, I would implement one here.
1132 * As no one else uses this functionality so I guess its okay to just
1133 * implement it here. */
1140 * 1. Check if we are maintaining the 64k size of struct PeerTrailSetupMessage.
1141 * when we add ourself to the trail list.
1142 * 2. Ensure every case is handled for current_destination.
1143 * Core handler for P2P trail setup message.
1144 * @param cls closure
1145 * @param message message
1146 * @param peer peer identity this notification is about
1147 * @return #GNUNET_YES
1150 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1151 const struct GNUNET_MessageHeader *message)
1153 struct PeerTrailSetupMessage *trail_setup;
1154 struct GNUNET_PeerIdentity *next_hop;
1155 struct GNUNET_PeerIdentity *prev_hop;
1156 struct FriendInfo *friend;
1157 struct TrailPeerList *peer_entry;
1158 struct P2PPendingMessage *pending;
1162 msize = ntohs (message->size);
1163 if (msize < sizeof (struct PeerTrailSetupMessage))
1165 GNUNET_break_op (0);
1169 trail_setup = (struct PeerTrailSetupMessage *) message;
1171 GNUNET_STATISTICS_update (GDS_stats,
1172 gettext_noop ("# TRAIL SETUP requests received"), 1,
1174 GNUNET_STATISTICS_update (GDS_stats,
1175 gettext_noop ("# TRAIL SETUP bytes received"), msize,
1179 /* Check the value of current_destination and handle the respective case. */
1180 if(trail_setup->current_destination == NULL)
1182 /* Find the next peer to pass the trail setup message. */
1183 next_hop = find_successor(trail_setup->destination_finger,trail_setup->current_destination);
1185 else if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_setup->current_destination,&my_identity)))
1187 /* I am current destination, find the next peer to pass the trail setup message. */
1188 next_hop = find_successor(trail_setup->destination_finger,trail_setup->current_destination);
1192 /* I am part of the trail to reach to current_destination. */
1193 next_hop = GDS_Routing_search(trail_setup->source_peer, trail_setup->current_destination, trail_setup->tail->peer);
1197 if(0 == (GNUNET_CRYPTO_cmp_peer_identity(next_hop,&my_identity)))
1199 /* I am the closest successor of the destination finger in the network. */
1201 1. Prepare a trail setup result message.
1202 2. Add yourself to trail list.
1203 3. send packet to last element in the list.
1209 * Do we really need to pass the whole trail_setup? I guess
1210 * we can just pass the double linked list.
1212 prev_hop = find_trail_list_prev_hop(trail_setup);
1214 GDS_ROUTING_add(trail_setup->source_peer,trail_setup->current_destination,prev_hop,next_hop);
1216 peer_entry = GNUNET_malloc (sizeof (struct TrailPeerList));
1217 peer_entry->peer = &my_identity;
1218 peer_entry->next = NULL;
1219 peer_entry->prev = NULL;
1221 /*SUPU what is this stupid code that I have written. */
1222 GNUNET_CONTAINER_DLL_insert_tail(trail_setup->head->next,trail_setup->tail->prev,peer_entry);
1224 /* Find the struct FriendInfo for next_hop peer id. */
1225 friend = GNUNET_CONTAINER_multipeermap_get(friend_peers,next_hop);
1227 if (friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1229 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1233 /* Send trail setup message to next hop friend. */
1234 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
1236 /* FIXME: Check if we are properly initializing pending. */
1237 trail_setup = (struct PeerTrailSetupMessage *) &pending[1];
1238 pending->msg = &trail_setup->header;
1239 GNUNET_CONTAINER_DLL_insert_tail (friend->head, friend->tail, pending);
1240 friend->pending_count++;
1241 process_friend_queue(friend);
1246 /* Add an entry to finger table. */
1248 void finger_table_add(struct PeerTrailSetupResultMessage *result)
1250 /* 1. create a struct FingerInfo and copy respective members
1251 * of result into this struct.
1252 * Add the whole trail in your finger table,
1253 also add interval. */
1257 /* Traverse the trail list to find the next hop to pass the result message. */
1259 struct GNUNET_PeerIdentity *
1260 find_trail_list_next_hop(struct PeerTrailSetupResultMessage *trail_result)
1262 /* Setup the current_destination value to new next hop found. */
1268 * Core handle for p2p trail construction result messages.
1269 * @param cls closure
1270 * @param message message
1271 * @param peer peer identity this notification is about
1272 * @return #GNUNET_YES (do not cut p2p connection)
1276 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1277 const struct GNUNET_MessageHeader *message)
1279 /* FIXME: Should it be const? */
1280 struct PeerTrailSetupResultMessage *trail_result;
1281 struct GNUNET_PeerIdentity *next_hop;
1282 struct FriendInfo *friend;
1283 struct P2PPendingMessage *pending;
1284 trail_result = (struct PeerTrailSetupResultMessage *) message;
1288 msize = ntohs (message->size);
1289 if (msize < sizeof (struct PeerTrailSetupResultMessage))
1291 GNUNET_break_op (0);
1295 /* This should always be the case. */
1296 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_result->current_destination,&my_identity)))
1298 /* Am I the destination ? */
1299 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_result->destination_peer,&my_identity)))
1301 /* I am the destination. Add the trail to my finger table. */
1302 finger_table_add(trail_result);
1307 /* Find the next peer in the trail list to pass the message to. */
1308 next_hop = find_trail_list_next_hop(trail_result);
1310 /* Find the struct FriendInfo for next_hop peer id. */
1311 friend = GNUNET_CONTAINER_multipeermap_get(friend_peers,next_hop);
1313 if (friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1315 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1318 /* Send trail setup result message to next hop friend. */
1320 I have not yet written the code to copy struct trail message to
1321 pending message. Also, before sending the message I need to check
1322 the MAXIMUM_PENDNIG_PEER limit is not crossed. Modify the same part
1323 of code for handle_dht_p2p_trail_setup. */
1324 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
1325 trail_result = (struct PeerTrailSetupResultMessage *) &pending[1];
1326 pending->msg = &trail_result->header;
1327 GNUNET_CONTAINER_DLL_insert_tail (friend->head, friend->tail, pending);
1328 friend->pending_count++;
1329 process_friend_queue(friend);
1335 return GNUNET_SYSERR;
1340 * Initialize neighbours subsystem.
1341 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1344 GDS_NEIGHBOURS_init()
1346 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
1347 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
1348 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
1349 {&handle_dht_p2p_result, GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT, 0},
1350 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
1351 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
1355 /*ASK: What is ATS? Why do we need it? */
1356 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
1358 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
1359 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
1360 GNUNET_NO, core_handlers);
1361 if (core_api == NULL)
1362 return GNUNET_SYSERR;
1364 friend_peers = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1365 finger_peers = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1372 * Shutdown neighbours subsystem.
1375 GDS_NEIGHBOURS_done ()
1377 if (NULL == core_api)
1379 GNUNET_CORE_disconnect (core_api);
1381 GNUNET_ATS_performance_done (atsAPI);
1384 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peers));
1385 GNUNET_CONTAINER_multipeermap_destroy (friend_peers);
1386 friend_peers = NULL;
1388 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peers));
1389 GNUNET_CONTAINER_multipeermap_destroy (finger_peers);
1390 finger_peers = NULL;
1392 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
1394 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
1395 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
1401 * Get the ID of the local node.
1403 * @return identity of the local node
1405 struct GNUNET_PeerIdentity *
1406 GDS_NEIGHBOURS_get_id ()
1408 return &my_identity;
1412 /* end of gnunet-service-xdht_neighbours.c */