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"
52 * Maximum possible fingers of a peer.
54 #define MAX_FINGERS 64
57 * Maximum allowed number of pending messages per friend peer.
59 #define MAXIMUM_PENDING_PER_FRIEND 64
62 * How long at least to wait before sending another find finger trail request.
64 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
67 * How long at most to wait before sending another find finger trail request.
69 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 10)
72 * How long at most to wait for transmission of a GET request to another peer?
74 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
76 GNUNET_NETWORK_STRUCT_BEGIN
84 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
86 struct GNUNET_MessageHeader header;
91 uint32_t options GNUNET_PACKED;
96 uint32_t type GNUNET_PACKED;
101 uint32_t hop_count GNUNET_PACKED;
104 * Replication level for this message
106 uint32_t desired_replication_level GNUNET_PACKED;
109 * Length of the PUT path that follows (if tracked).
111 uint32_t put_path_length GNUNET_PACKED;
114 * When does the content expire?
116 struct GNUNET_TIME_AbsoluteNBO expiration_time;
119 * Bloomfilter (for peer identities) to stop circular routes
121 char bloomfilter[DHT_BLOOM_SIZE];
124 * The key we are storing under.
126 struct GNUNET_HashCode key;
128 /* put path (if tracked) */
138 struct PeerResultMessage
141 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
143 struct GNUNET_MessageHeader header;
148 uint32_t type GNUNET_PACKED;
151 * Length of the PUT path that follows (if tracked).
153 uint32_t put_path_length GNUNET_PACKED;
156 * Length of the GET path that follows (if tracked).
158 uint32_t get_path_length GNUNET_PACKED;
161 * When does the content expire?
163 struct GNUNET_TIME_AbsoluteNBO expiration_time;
166 * The key of the corresponding GET request.
168 struct GNUNET_HashCode key;
170 /* put path (if tracked) */
172 /* get path (if tracked) */
182 struct PeerGetMessage
185 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
187 struct GNUNET_MessageHeader header;
192 uint32_t options GNUNET_PACKED;
195 * Desired content type.
197 uint32_t type GNUNET_PACKED;
202 uint32_t hop_count GNUNET_PACKED;
205 * Desired replication level for this request.
207 uint32_t desired_replication_level GNUNET_PACKED;
210 * Size of the extended query.
212 uint32_t xquery_size;
215 * Bloomfilter mutator.
220 * Bloomfilter (for peer identities) to stop circular routes
222 char bloomfilter[DHT_BLOOM_SIZE];
225 * The key we are looking for.
227 struct GNUNET_HashCode key;
233 * A destination can be either a friend, finger or me.
234 * Used in trail setup to understand if the message is sent to an intermediate
235 * finger or a friend.
237 enum current_destination_type
246 * P2P Trail setup message
248 struct PeerTrailSetupMessage
252 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
254 struct GNUNET_MessageHeader header;
257 * Source peer which wants to setup the trail to one of its finger.
259 struct GNUNET_PeerIdentity source_peer;
262 * Finger id to which we want to set up the trail to.
264 uint64_t destination_finger;
267 * If set to 1, then we are looking for trail to our immediate successor.
269 unsigned int successor_flag;
272 * If set to 1, then we are looking for trail to our immediate predecessor.
274 unsigned int predecessor_flag;
277 * Peer which gets this message can be either an intermediate finger or friend.
279 enum current_destination_type current_destination_type;
282 * Peer to which this packet is forwarded.
284 struct GNUNET_PeerIdentity current_destination;
287 * Index into finger peer map.
289 unsigned int finger_map_index;
292 * Number of entries in trail list.
294 uint32_t trail_length GNUNET_PACKED;
300 * P2P Trail setup Result message
302 struct PeerTrailSetupResultMessage
306 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
308 struct GNUNET_MessageHeader header;
311 * Finger to which we have found the path.
313 struct GNUNET_PeerIdentity finger;
316 * Peer which was looking for the trail to finger.
318 struct GNUNET_PeerIdentity destination_peer;
321 * Peer to which this packet is forwarded next.
323 struct GNUNET_PeerIdentity current_destination;
326 * Index at which peer list should be accessed.
328 unsigned int current_index;
331 * If set to 1, then this trail is the trail to our successor.
333 unsigned int successor_flag;
336 * If set to 1, then this trail is the trail to our predecessor.
338 unsigned int predecessor_flag;
341 * Index into finger peer map
343 unsigned int finger_map_index;
346 * Number of entries in trail list.
348 uint32_t trail_length GNUNET_PACKED;
354 * P2P verify successor message.
356 struct PeerVerifySuccessorMessage
360 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
362 struct GNUNET_MessageHeader header;
365 * Source peer which wants to verify its successor.
367 struct GNUNET_PeerIdentity source_peer;
370 * My current successor.
372 struct GNUNET_PeerIdentity successor;
375 * Total number of peers in trail to current successor.
377 unsigned int trail_length;
380 * Index in trail which points to next destination to send this message.
382 unsigned int current_trail_index;
388 * P2P verify successor result message.
390 struct PeerVerifySuccessorResultMessage
394 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
396 struct GNUNET_MessageHeader header;
399 * Destination peer which sent the request to verify its successor.
401 struct GNUNET_PeerIdentity destination_peer;
404 * Successor to which PeerVerifySuccessorMessage was sent.
406 struct GNUNET_PeerIdentity source_successor;
409 * source_successor's predecessor
411 struct GNUNET_PeerIdentity my_predecessor;
414 * Total number of peers in trail.
415 * If source_successor is not destination peer, then trail is from destination_peer
417 * If source_successor is destination peer, then trail is from destination_peer
418 * to source_successor.
420 unsigned int trail_length;
423 * Index in trail which points to next destination to send this message.
425 unsigned int current_index;
430 * P2P notify new successor message.
432 struct PeerNotifyNewSuccessorMessage
435 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
437 struct GNUNET_MessageHeader header;
440 * Source peer which wants to notify its new successor.
442 struct GNUNET_PeerIdentity source_peer;
445 * New successor identity.
447 struct GNUNET_PeerIdentity destination_peer;
450 * Number of peers in trail from source_peer to new successor.
452 unsigned int trail_length;
455 * Index in trail which points to next destination to send this message.
457 unsigned int current_index;
462 GNUNET_NETWORK_STRUCT_END
466 * Linked list of messages to send to a particular other peer.
468 struct P2PPendingMessage
471 * Pointer to next item in the list
473 struct P2PPendingMessage *next;
476 * Pointer to previous item in the list
478 struct P2PPendingMessage *prev;
481 * When does this message time out?
483 struct GNUNET_TIME_Absolute timeout;
486 * Message importance level. FIXME: used? useful?
488 unsigned int importance;
491 * Actual message to be sent, allocated at the end of the struct:
492 * // msg = (cast) &pm[1];
493 * // memcpy (&pm[1], data, len);
495 const struct GNUNET_MessageHeader *msg;
501 * Linked List of peers which are part of trail to reach a particular Finger.
506 * Pointer to next item in the list
508 struct TrailPeerList *next;
511 * Pointer to previous item in the list
513 struct TrailPeerList *prev;
516 * An element in this trail list
518 struct GNUNET_PeerIdentity peer;
524 * Entry in friend_peermap.
531 struct GNUNET_PeerIdentity id;
534 * Count of outstanding messages for this friend.
536 unsigned int pending_count;
539 * Head of pending messages to be sent to this friend.
541 struct P2PPendingMessage *head;
544 * Tail of pending messages to be sent to this friend.
546 struct P2PPendingMessage *tail;
549 * Core handle for sending messages to this friend.
551 struct GNUNET_CORE_TransmitHandle *th;
557 * Entry in finger_peermap.
564 struct GNUNET_PeerIdentity finger_identity;
567 * If 1, then this finger entry is my first finger(successor).
569 unsigned int successor;
572 * If 1, then this finger entry is my first predecessor.
574 unsigned int predecessor;
577 * Index in finger peer map
579 unsigned int finger_map_index;
582 * Total number of entries in trail from me to finger.
584 unsigned int trail_length;
587 * List of peers in the trail to reach this finger.
589 struct GNUNET_PeerIdentity *trail_peer_list;
595 * Task that sends FIND FINGER TRAIL requests.
597 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
601 * Task that periodically checks for who is my successor.
603 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
606 * Identity of this peer.
608 static struct GNUNET_PeerIdentity my_identity;
611 * Hash map of all the friends of a peer
613 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
616 * Hash map of all the fingers of a peer
618 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
623 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
628 static struct GNUNET_CORE_Handle *core_api;
631 * FIXME: Is it safe to assume its initialized to 0 by default.
632 * The current finger index that we have found trail to.
634 static unsigned int current_finger_index;
638 * Called when core is ready to send a message we asked for
639 * out to the destination.
641 * @param cls the 'struct PeerInfo' of the target peer
642 * @param size number of bytes available in buf
643 * @param buf where the callee should write the message
644 * @return number of bytes written to buf
647 core_transmit_notify (void *cls, size_t size, void *buf)
649 struct FriendInfo *peer = cls;
651 struct P2PPendingMessage *pending;
656 while ((NULL != (pending = peer->head)) &&
657 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
659 peer->pending_count--;
660 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
661 GNUNET_free (pending);
665 /* no messages pending */
671 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
672 GNUNET_CORE_PRIO_BEST_EFFORT,
673 GNUNET_TIME_absolute_get_remaining
674 (pending->timeout), &peer->id,
675 ntohs (pending->msg->size),
676 &core_transmit_notify, peer);
677 GNUNET_break (NULL != peer->th);
681 while ((NULL != (pending = peer->head)) &&
682 (size - off >= (msize = ntohs (pending->msg->size))))
684 GNUNET_STATISTICS_update (GDS_stats,
686 ("# Bytes transmitted to other peers"), msize,
688 memcpy (&cbuf[off], pending->msg, msize);
690 peer->pending_count--;
691 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
692 GNUNET_free (pending);
694 if (peer->head != NULL)
697 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
698 GNUNET_CORE_PRIO_BEST_EFFORT,
699 GNUNET_TIME_absolute_get_remaining
700 (pending->timeout), &peer->id, msize,
701 &core_transmit_notify, peer);
702 GNUNET_break (NULL != peer->th);
709 * Transmit all messages in the friend's message queue.
711 * @param peer message queue to process
714 process_friend_queue (struct FriendInfo *peer)
716 struct P2PPendingMessage *pending;
718 if (NULL == (pending = peer->head))
720 if (NULL != peer->th)
723 GNUNET_STATISTICS_update (GDS_stats,
725 ("# Bytes of bandwidth requested from core"),
726 ntohs (pending->msg->size), GNUNET_NO);
728 /* FIXME: Are we correctly initializing importance and pending. */
730 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
732 GNUNET_TIME_absolute_get_remaining
733 (pending->timeout), &peer->id,
734 ntohs (pending->msg->size),
735 &core_transmit_notify, peer);
736 GNUNET_break (NULL != peer->th);
741 * Setup the trail message and forward it to a friend.
742 * @param source_peer Peer which wants to set up the trail to one of its finger.
743 * @param destination_finger Peer to which we want to set up the trail to.
744 * @param target_friend Current friend to which this message should be forwarded.
745 * @param trail_length Numbers of peers in the trail.
746 * @param trail_peer_list peers this request has traversed so far
747 * @param successor_flag If 1 then we are looking for trail to our successor.
748 * @param predecessor_flag If 1, then we are looking for trail to our predecessor.
749 * @param current_finger_index Finger index in finger peer map
752 GDS_NEIGHBOURS_handle_trail_setup (struct GNUNET_PeerIdentity *source_peer,
753 uint64_t *destination_finger,
754 struct FriendInfo *target_friend,
755 unsigned int trail_length,
756 struct GNUNET_PeerIdentity *trail_peer_list,
757 unsigned int successor_flag,
758 unsigned int predecessor_flag,
759 unsigned int current_finger_index)
761 struct P2PPendingMessage *pending;
762 struct PeerTrailSetupMessage *tsm;
763 struct GNUNET_PeerIdentity *peer_list;
766 msize = sizeof (struct PeerTrailSetupMessage) +
767 (trail_length * sizeof (struct GNUNET_PeerIdentity));
769 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
775 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
777 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
781 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
782 pending->importance = 0; /* FIXME */
783 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
784 tsm = (struct PeerTrailSetupMessage *) &pending[1];
785 pending->msg = &tsm->header;
786 tsm->header.size = htons (msize);
787 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
788 memcpy (&(tsm->destination_finger), destination_finger, sizeof (uint64_t));
789 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
790 memcpy (&(tsm->current_destination), &(target_friend->id),
791 sizeof (struct GNUNET_PeerIdentity));
792 tsm->current_destination_type = htonl (FRIEND);
793 tsm->trail_length = htonl (trail_length);
794 tsm->finger_map_index = htonl (current_finger_index);
795 if(1 == successor_flag)
797 tsm->successor_flag = 1;
798 tsm->predecessor_flag = 0;
800 else if (1 == predecessor_flag)
802 tsm->predecessor_flag = 1;
803 tsm->successor_flag = 0;
807 tsm->successor_flag = 0;
808 tsm->predecessor_flag = 0;
811 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
812 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
813 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
815 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
816 target_friend->pending_count++;
817 process_friend_queue (target_friend);
823 * Handle a tail setup result message.
824 * @param destination_peer Peer which will get the trail to one of its finger.
825 * @param source_finger Peer to which the trail has been setup to.
826 * @param target_friend Friend to which this message should be forwarded.
827 * @param trail_length Numbers of peers in the trail.
828 * @param trail_peer_list Peers which are part of the trail from source to destination.
829 * @param current_trail_index Index in trail_peer_list.
830 * @param successor_flag If 1, then this is the trail to our successor.
831 * @param predecessor_flag If 1, then this is the trail to our predecessor.
832 * @param finger_map_index Finger index in finger peer map
835 GDS_NEIGHBOURS_handle_trail_setup_result (struct GNUNET_PeerIdentity *destination_peer,
836 struct GNUNET_PeerIdentity *source_finger,
837 struct FriendInfo *target_friend,
838 unsigned int trail_length,
839 struct GNUNET_PeerIdentity *trail_peer_list,
840 unsigned int current_trail_index,
841 unsigned int successor_flag,
842 unsigned int predecessor_flag,
843 unsigned int finger_map_index)
845 struct P2PPendingMessage *pending;
846 struct PeerTrailSetupResultMessage *tsrm;
847 struct GNUNET_PeerIdentity *peer_list;
850 msize = sizeof (struct PeerTrailSetupResultMessage) +
851 (trail_length * sizeof (struct GNUNET_PeerIdentity));
853 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
859 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
861 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
865 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
866 pending->importance = 0;
867 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
868 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
869 pending->msg = &tsrm->header;
870 tsrm->header.size = htons (msize);
871 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
872 memcpy (&(tsrm->current_destination), &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
873 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
874 memcpy (&(tsrm->finger), source_finger, sizeof (struct GNUNET_PeerIdentity));
875 tsrm->trail_length = htonl (trail_length);
876 tsrm->current_index = htonl (current_trail_index);
877 tsrm->successor_flag = htonl (successor_flag);
878 tsrm->predecessor_flag = htonl (predecessor_flag);
879 tsrm->finger_map_index = htonl (finger_map_index);
880 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
881 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
883 /* Send the message to chosen friend. */
884 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
885 target_friend->pending_count++;
886 process_friend_queue (target_friend);
891 * Construct a PeerVerifySuccessor message and send it to friend.
892 * @param source_peer Peer which wants to verify its successor
893 * @param successor Peer which is our current successor
894 * @param target_friend Friend to which this message should be forwarded.
895 * @param trail_peer_list Peer which are part of trail from source to destination
896 * @param trail_length Number of peers in the trail list.
897 * @param current_trail_index Index in the trial list at which receiving peer should
898 * get the next element.
900 void GDS_NEIGUBOURS_handle_verify_successor(struct GNUNET_PeerIdentity *source_peer,
901 struct GNUNET_PeerIdentity *successor,
902 struct FriendInfo *target_friend,
903 struct GNUNET_PeerIdentity *trail_peer_list,
904 unsigned int trail_length,
905 unsigned int current_trail_index)
907 struct PeerVerifySuccessorMessage *vsm;
908 struct P2PPendingMessage *pending;
909 struct GNUNET_PeerIdentity *peer_list;
912 msize = sizeof (struct PeerVerifySuccessorMessage) +
913 (trail_length * sizeof (struct GNUNET_PeerIdentity));
915 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
921 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
923 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
927 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
928 pending->importance = 0; /* FIXME */
929 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
930 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
931 pending->msg = &vsm->header;
932 vsm->header.size = htons (msize);
933 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
934 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
935 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
936 vsm->trail_length = htonl (trail_length);
937 vsm->current_trail_index = htonl (current_trail_index);
939 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
940 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
942 /* Send the message to chosen friend. */
943 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
944 target_friend->pending_count++;
945 process_friend_queue (target_friend);
951 * Construct a PeerVerifySuccessorResult message and send it to friend.
952 * @param destination_peer Peer which sent verify successor message
953 * @param source_successor Peer to which verify successor message was sent.
954 * @param my_predecessor source_successor predecessor.
955 * @param target_friend Friend to which this message should be forwarded.
956 * @param trail_peer_list Peer which are part of trail from source to destination
957 * @param trail_length Number of peers in the trail list.
958 * @param current_trail_index Index in the trial list at which receiving peer should
959 * get the next element.
961 void GDS_NEIGHBOURS_handle_verify_successor_result (struct GNUNET_PeerIdentity *destination_peer,
962 struct GNUNET_PeerIdentity *source_successor,
963 struct GNUNET_PeerIdentity *my_predecessor,
964 struct FriendInfo *target_friend,
965 struct GNUNET_PeerIdentity *trail_peer_list,
966 unsigned int trail_length,
967 unsigned int current_trail_index)
969 struct PeerVerifySuccessorResultMessage *vsmr;
970 struct P2PPendingMessage *pending;
971 struct GNUNET_PeerIdentity *peer_list;
974 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
975 (trail_length * sizeof(struct GNUNET_PeerIdentity));
977 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
983 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
985 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
989 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
990 pending->importance = 0; /* FIXME */
991 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
992 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
993 pending->msg = &vsmr->header;
994 vsmr->header.size = htons (msize);
995 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
996 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
997 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
998 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
999 vsmr->trail_length = htonl (trail_length);
1000 vsmr->current_index = htonl (current_trail_index);
1002 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1003 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1005 /* Send the message to chosen friend. */
1006 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1007 target_friend->pending_count++;
1008 process_friend_queue (target_friend);
1013 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1014 * @param source_peer Peer which is sending notify message to its new successor.
1015 * @param destination_peer Peer which is the new destination.
1016 * @param target_friend Next friend to pass this message to.
1017 * @param peer_list List of peers in the trail to reach to destination_peer.
1018 * @param current_trail_index Index of peer_list for next target friend position.
1019 * @param trail_length Total number of peers in peer list
1022 GDS_NEIGHBOURS_notify_new_successor (struct GNUNET_PeerIdentity *source_peer,
1023 struct GNUNET_PeerIdentity *destination_peer,
1024 struct FriendInfo *target_friend,
1025 struct GNUNET_PeerIdentity *trail_peer_list,
1026 unsigned int trail_length,
1027 unsigned int current_trail_index)
1029 struct PeerNotifyNewSuccessorMessage *nsm;
1030 struct P2PPendingMessage *pending;
1031 struct GNUNET_PeerIdentity *peer_list;
1034 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1035 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1037 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1043 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1045 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1049 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1050 pending->importance = 0; /* FIXME */
1051 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1052 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1053 pending->msg = &nsm->header;
1054 nsm->header.size = htons (msize);
1055 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1056 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1057 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1058 nsm->trail_length = htonl (trail_length);
1059 nsm->current_index = htonl (current_trail_index);
1061 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1062 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1064 /* Send the message to chosen friend. */
1065 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1066 target_friend->pending_count++;
1067 process_friend_queue (target_friend);
1071 /**FIXME: Old implementation just to remove error
1072 * TODO: Modify this function to handle our get request.
1073 * Perform a GET operation. Forwards the given request to other
1074 * peers. Does not lookup the key locally. May do nothing if this is
1075 * the only peer in the network (or if we are the closest peer in the
1078 * @param type type of the block
1079 * @param options routing options
1080 * @param desired_replication_level desired replication count
1081 * @param hop_count how many hops did this request traverse so far?
1082 * @param key key for the content
1083 * @param xquery extended query
1084 * @param xquery_size number of bytes in @a xquery
1085 * @param reply_bf bloomfilter to filter duplicates
1086 * @param reply_bf_mutator mutator for @a reply_bf
1087 * @param peer_bf filter for peers not to select (again)
1090 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1091 enum GNUNET_DHT_RouteOption options,
1092 uint32_t desired_replication_level,
1093 uint32_t hop_count, const struct GNUNET_HashCode * key,
1094 const void *xquery, size_t xquery_size,
1095 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
1096 uint32_t reply_bf_mutator,
1097 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1101 1. take the key, get the 64 bit value of the key.
1102 2. call find_successor to get the successor of the key.
1103 3. successor can be either a friend or finger.
1104 4. update the field in get message to reflect if its a friend or finger table
1105 5. add the put message to pending message and send it.
1109 /**FIXME: Old implementation just to remove error.
1110 * TODO: Modify this function to handle our put request.
1111 * Perform a PUT operation. Forwards the given request to other
1112 * peers. Does not store the data locally. Does not give the
1113 * data to local clients. May do nothing if this is the only
1114 * peer in the network (or if we are the closest peer in the
1117 * @param type type of the block
1118 * @param options routing options
1119 * @param desired_replication_level desired replication count
1120 * @param expiration_time when does the content expire
1121 * @param hop_count how many hops has this message traversed so far
1122 * @param bf Bloom filter of peers this PUT has already traversed
1123 * @param key key for the content
1124 * @param put_path_length number of entries in @a put_path
1125 * @param put_path peers this request has traversed so far (if tracked)
1126 * @param data payload to store
1127 * @param data_size number of bytes in @a data
1130 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1131 enum GNUNET_DHT_RouteOption options,
1132 uint32_t desired_replication_level,
1133 struct GNUNET_TIME_Absolute expiration_time,
1135 struct GNUNET_CONTAINER_BloomFilter *bf,
1136 const struct GNUNET_HashCode *key,
1137 unsigned int put_path_length,
1138 struct GNUNET_PeerIdentity *put_path,
1139 const void *data, size_t data_size)
1143 1. take the key, get the 64 bit value of the key.
1144 2. call find_successor to get the successor of the key.
1145 3. successor can be either a friend or finger.
1146 4. update the field in put message to reflect if its a friend or finger table
1147 5. add the put message to pending message and send it.
1153 * FIXME: Check if this function actually iterates or not.
1154 * Randomly choose one of your friends from the friends_peer map
1157 static struct FriendInfo *
1158 select_random_friend()
1160 unsigned int current_size;
1161 unsigned int *index;
1163 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1164 struct GNUNET_PeerIdentity key_ret;
1165 struct FriendInfo *friend;
1167 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1169 /* Element stored at this index in friend_peermap should be selected friend. */
1170 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1172 /* Create an iterator for friend_peermap. */
1173 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1175 /* Set the position of iterator to index. */
1178 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1180 /* FIXME: I don't think we are actually incrementing iter. iter is always
1181 pointing to the same element. */
1188 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1198 * Compute finger_identity to which we want to setup the trail
1199 * FIXME: If we maintain a index that is value of current_finger_index
1200 * to which a particular entry in finger map corresponds then should we first
1201 * check if there is already an entry for that index. If yes then don't
1202 * search for trail to that finger.
1203 * @return finger_identity
1206 compute_finger_identity()
1209 uint64_t *finger_identity64;
1211 my_id64 = GNUNET_malloc (sizeof (uint64_t));
1212 finger_identity64 = GNUNET_malloc (sizeof (uint64_t));
1214 /* Check if for current_finger_index you already have an entry in finger table.
1215 If yes it means you should try to find the trail for finger identifier
1216 corresponding to next current_finger_index. */
1217 /*FIXME: Create an iterator, read all the elements of finger_peermap one by one
1218 and if finger_index == current_finger_index, then (
1219 current_finger_index = current_finger_index + 1) % MAX_FINGERS. We can either
1220 return NULL or just restart the process to find finger. When we remove the
1221 friend in handle_core_disconnect, then we also remove the entry from finger
1222 * peermap. Thats why there can be gap in our logic. ;*/
1224 memcpy (my_id64, &(my_identity.public_key.q_y), sizeof (uint64_t));
1225 *finger_identity64 = fmod ((*my_id64 + pow (2,current_finger_index)),( (pow (2,MAX_FINGERS))));
1227 return finger_identity64;
1232 * Find immediate predecessor in the network.
1233 * @param me my own identity
1234 * @return peer identity of immediate predecessor.
1240 uint64_t *predecessor;
1242 my_id = GNUNET_malloc (sizeof (uint64_t));
1243 predecessor = GNUNET_malloc (sizeof (uint64_t));
1245 memcpy (my_id, &(my_identity.public_key.q_y), sizeof (uint64_t));
1246 *predecessor = fmod ((*my_id -1), (pow (2,MAX_FINGERS)));
1253 * FIXME: At the moment no one is calling this function.
1254 * Need to find the correct place to call this function.
1262 * 1. Choose a random finger index using GNUNET_CRYPTO_random.
1263 * 2. call find_successor for that finger. now here you have to send
1264 * what value how do you remember which index you used. so its important
1265 * to have finger index in finger table.
1273 * SUPU: You should pass the trail index from where next peer should read. read
1274 * position should be set and after you read you should update the read position
1275 * for next peer in the trail list.
1276 * Periodically ping your successor to ask its current predecessor
1278 * @param cls closure for this task
1279 * @param tc the context under which the task is running
1282 send_verify_successor_message (void *cls,
1283 const struct GNUNET_SCHEDULER_TaskContext *tc )
1285 struct GNUNET_TIME_Relative next_send_time;
1286 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1287 struct GNUNET_PeerIdentity key_ret;
1288 struct FriendInfo *target_friend;
1289 struct GNUNET_PeerIdentity *next_hop;
1290 struct GNUNET_PeerIdentity *finger_trail;
1291 unsigned int finger_trail_length;
1292 unsigned int finger_trail_current_index;
1293 struct FingerInfo *finger;
1294 unsigned int finger_index;
1296 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1297 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1299 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1300 (const void **)&finger))
1302 if (1 == finger->successor)
1307 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1309 finger_trail = GNUNET_malloc ((finger->trail_length *
1310 sizeof (struct GNUNET_PeerIdentity)));
1311 target_friend = GNUNET_malloc (sizeof (struct FriendInfo));
1312 memcpy (finger_trail, finger->trail_peer_list,
1313 (finger->trail_length * sizeof (struct GNUNET_PeerIdentity)));
1314 finger_trail_length = finger->trail_length;
1315 /* FIXME: Here I am the first element in the trail to reach to any finger.
1316 So, our first target friend is situated at trail index = 1 and target friend
1317 should read from finger_Trial_current_index. Check in the function that
1318 finger_trail_current_index < trail_length.*/
1319 finger_trail_current_index = 2;
1320 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1321 memcpy (next_hop, &finger_trail[1],
1322 sizeof (struct GNUNET_PeerIdentity));
1324 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1325 GNUNET_free (next_hop);
1327 GDS_NEIGUBOURS_handle_verify_successor (&my_identity,
1328 &(finger->finger_identity),
1331 finger_trail_length,
1332 finger_trail_current_index);
1335 /* FIXME: Use a random value so that this message is send not at the same
1336 interval as send_find_finger_trail_message. */
1337 next_send_time.rel_value_us =
1338 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1339 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1340 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1341 (current_finger_index + 1));
1344 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1350 * Task to send a find finger trail message. We attempt to find trail
1351 * to our fingers, successor and predecessor in the network.
1353 * @param cls closure for this task
1354 * @param tc the context under which the task is running
1357 send_find_finger_trail_message (void *cls,
1358 const struct GNUNET_SCHEDULER_TaskContext *tc)
1360 struct FriendInfo *target_friend;
1361 struct GNUNET_TIME_Relative next_send_time;
1362 struct GNUNET_PeerIdentity *peer_list;
1363 unsigned int successor_flag;
1364 unsigned int predecessor_flag;
1365 uint64_t *finger_identity;
1366 unsigned int finger_index;
1368 predecessor_flag = 0;
1371 if (1 == current_finger_index)
1373 /* We have started the process to find the successor. We should search
1374 for our predecessor. */
1375 finger_identity = find_predecessor();
1377 /* FIXME: There is no case in find_predecessor which returns NULL. It can
1378 return NULL, only if we already have found a trail to predecessor. is it
1379 required or not need to check.*/
1380 if(NULL == finger_identity)
1382 /* We already have a trail to reach to immediate predecessor. */
1383 goto new_find_finger_trail_request;
1385 predecessor_flag = 1;
1390 finger_identity = compute_finger_identity();
1392 /* Here again we can get NULL, only if we already have an entry for that
1393 index value in our finger peer map. That will be checked in compute_finger_identity
1394 Also, it may be beneficial to keep checking for the new trail and only when
1395 adding the entry into finger table, we check if the new route is shorter
1396 or else we may want to keep more than one route (redundant routing). There can be
1397 no case when it return NULL. */
1398 if(finger_identity == NULL)
1400 goto new_find_finger_trail_request;
1404 if(0 == current_finger_index)
1406 /* We are searching for our successor in the network. */
1411 finger_index = current_finger_index;
1412 current_finger_index = ( current_finger_index + 1) % MAX_FINGERS;
1414 target_friend = select_random_friend();
1416 /* We found a friend.*/
1417 if(NULL != target_friend)
1419 /*SUPU: Here you are adding yourself to peer list so that trail result
1420 reaches back to you. Highest trail index = trail_length - 1; */
1421 unsigned int trail_length = 2;
1422 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
1423 memcpy (&peer_list[0], &(my_identity), sizeof (struct GNUNET_PeerIdentity));
1424 memcpy (&peer_list[1], &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1426 /* FIXME: Here why are you sending the current_finger_index ? */
1427 GDS_NEIGHBOURS_handle_trail_setup (&my_identity, finger_identity,
1428 target_friend, trail_length, peer_list,
1429 successor_flag, predecessor_flag,
1433 /* FIXME: Should we be using current_finger_index to generate random interval.*/
1434 new_find_finger_trail_request:
1435 next_send_time.rel_value_us =
1436 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1437 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1438 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1439 (current_finger_index + 1));
1441 find_finger_trail_task =
1442 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1448 * Method called whenever a peer connects.
1450 * @param cls closure
1451 * @param peer peer identity this notification is about
1454 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer)
1456 struct FriendInfo *ret;
1458 /* Check for connect to self message */
1459 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1462 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1463 "Connected to %s\n",
1466 /* If peer already exists in our friend_peermap, then exit. */
1468 GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
1475 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
1479 ret = GNUNET_new (struct FriendInfo);
1482 GNUNET_assert (GNUNET_OK ==
1483 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
1485 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1488 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
1489 if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
1490 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
1495 * Method called whenever a peer disconnects.
1497 * @param cls closure
1498 * @param peer peer identity this notification is about
1501 handle_core_disconnect (void *cls,
1502 const struct GNUNET_PeerIdentity *peer)
1504 struct FriendInfo *remove_friend;
1506 /* Check for self message. */
1507 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1510 /* Search for peer to remove in your friend_peermap. */
1512 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
1514 if (NULL == remove_friend)
1520 /* Remove the friend from friend_peermap. */
1521 GNUNET_assert (GNUNET_YES ==
1522 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
1526 /* If the peer is removed then all the trail which goes through this
1527 peer also becomes invalid. */
1528 /* FIXME: Iterate over finger peermap, get the trail index and find all the
1529 finger whose trail's first peer was this peer. and remove them from finger
1530 peermap. Assumption that in send_find_finger_trail we will eventually reach
1531 to this finger and we will setup up the new trail.
1532 So, we need a threshold on number of trail thats can go through a node
1533 so that if that nodes go away then also our system is up and runnning.
1534 Where can we specify that threshold.*/
1539 * To be called on core init/fail.
1541 * @param cls service closure
1542 * @param identity the public identity of this peer
1545 core_init (void *cls,
1546 const struct GNUNET_PeerIdentity *identity)
1548 my_identity = *identity;
1553 * Core handler for p2p put requests.
1555 * @param cls closure
1556 * @param peer sender of the request
1557 * @param message message
1558 * @param peer peer identity this notification is about
1559 * @return #GNUNET_OK to keep the connection open,
1560 * #GNUNET_SYSERR to close it (signal serious error)
1563 handle_dht_p2p_put (void *cls,
1564 const struct GNUNET_PeerIdentity *peer,
1565 const struct GNUNET_MessageHeader *message)
1568 1. Check if destination is friend or finger.
1569 2. If finger then get the next hop from routing table and
1570 * call GDS_NEGIHBOURS_handle_get.
1571 3. If friend then call find_successor to get the next hop and again
1572 * call GDS_NEIGHBOURS_handle_get to send to chosen hop.
1573 4. If you are the destination then do datacache_store.
1580 * Core handler for p2p get requests.
1582 * @param cls closure
1583 * @param peer sender of the request
1584 * @param message message
1585 * @return #GNUNET_OK to keep the connection open,
1586 * #GNUNET_SYSERR to close it (signal serious error)
1589 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1590 const struct GNUNET_MessageHeader *message)
1593 1. Check if destination is friend or finger.
1594 2. If finger then get the next hop from routing table and
1595 * call GDS_NEGIHBOURS_handle_get.
1596 3. If friend then call find_successor to get the next hop and again
1597 * call GDS_NEIGHBOURS_handle_get to send to chosen hop.
1598 4. If you are the destination then send the data back to source peer
1599 * Assuming we have trail setup we can
1600 * either store the whole trail or again do the search process..
1607 * Compare two peer identities.
1608 * @param p1 Peer identity
1609 * @param p2 Peer identity
1610 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
1613 compare_peer_id (const void *p1, const void *p2)
1615 return memcmp (p1, p2, sizeof (uint64_t));
1620 * Returns the previous element of value in all_known_peers.
1621 * @param all_known_peers list of all the peers
1622 * @param value value we have to search in the all_known_peers.
1625 static struct GNUNET_PeerIdentity *
1626 binary_search(struct GNUNET_PeerIdentity *all_known_peers, uint64_t *value,
1631 unsigned int middle;
1632 struct GNUNET_PeerIdentity *successor;
1633 successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1637 middle = (first + last)/2;
1639 while(first <= last)
1641 /* all_known_peers[middle] > value*/
1642 if(0 > compare_peer_id(&all_known_peers[middle], &value))
1646 else if(0 == compare_peer_id(&all_known_peers[middle], &value))
1650 successor = &(all_known_peers[size - 1]);
1653 successor = &(all_known_peers[middle-1]);
1660 middle = (first + last)/2;
1667 * Find closest successor for the value.
1668 * @param value Value for which we are looking for successor
1669 * @param current_destination NULL if my_identity is successor else finger/friend
1671 * @param type Next destination type
1672 * @return Peer identity of next destination i.e. successor of value.
1674 static struct GNUNET_PeerIdentity *
1675 find_successor(uint64_t *value, struct GNUNET_PeerIdentity *current_destination,
1676 enum current_destination_type *type)
1678 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1679 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1680 struct GNUNET_PeerIdentity key_ret;
1681 struct FriendInfo *friend;
1682 struct FingerInfo *finger;
1683 unsigned int finger_index;
1684 unsigned int friend_index;
1685 struct GNUNET_PeerIdentity *all_known_peers;
1686 struct GNUNET_PeerIdentity *successor;
1689 /* SUPU: 2 is added for my_identity and value. */
1690 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
1691 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
1694 all_known_peers = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * size);
1697 memcpy (&all_known_peers[j], &(my_identity), sizeof (struct GNUNET_PeerIdentity));
1699 memcpy (&all_known_peers[j], value, sizeof(struct GNUNET_PeerIdentity));
1701 /* Iterate over friend peermap and copy all the elements into array. */
1702 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1703 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1705 /* FIXME: I don't think we are actually iterating.
1706 Read about how to iterate over the multipeermap. */
1707 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1709 memcpy (&all_known_peers[j], &(friend->id), sizeof (struct GNUNET_PeerIdentity));
1714 /* Iterate over finger map and copy all the entries into all_known_peers array. */
1715 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1716 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1718 /* FIXME: I don't think we are actually iterating.
1719 Read about how to iterate over the multi peer map. */
1720 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1722 memcpy (&all_known_peers[j], &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1727 /* FIXME: If this is correct. */
1728 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1729 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
1731 qsort (all_known_peers, size, sizeof (struct GNUNET_PeerIdentity), &compare_peer_id);
1733 /* search value in all_known_peers array. */
1734 successor = binary_search (all_known_peers, value, size);
1736 /* compare successor with my_identity, finger and friend */
1737 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&(my_identity), successor))
1742 else if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
1746 memcpy (current_destination, successor, sizeof (struct GNUNET_PeerIdentity));
1749 else if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (finger_peermap,
1753 memcpy (current_destination, successor, sizeof (struct GNUNET_PeerIdentity));
1754 /* get the corresponding finger for succcesor and read the first element from
1755 the trail list and return that element. */
1756 struct FingerInfo *successor_finger;
1757 struct GNUNET_PeerIdentity *next_hop;
1758 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1759 successor_finger = GNUNET_CONTAINER_multipeermap_get (finger_peermap, successor);
1760 memcpy (next_hop, &(successor_finger->trail_peer_list[0]), sizeof (struct GNUNET_PeerIdentity));
1761 GNUNET_free (next_hop);
1770 * Compare two peer id's and find the closest peer id for value.
1771 * @param peer1 some peer id
1772 * @param peer2 some peer id
1773 * @param value value to which one of the peer id should be closest.
1776 static struct GNUNET_PeerIdentity *
1777 find_closest_destination (struct GNUNET_PeerIdentity *peer1,
1778 struct GNUNET_PeerIdentity *peer2,
1781 /* Compare value with peer1 and peer2 and find the closest peer to this value.*/
1787 * SUPU: The first element in the trail setup message is your identity.
1788 * in this function you should increment the trail length.
1789 * Handle a PeerTrailSetupMessage.
1790 * @param cls closure
1791 * @param message message
1792 * @param peer peer identity this notification is about
1793 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1796 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1797 const struct GNUNET_MessageHeader *message)
1799 struct PeerTrailSetupMessage *trail_setup;
1800 struct GNUNET_PeerIdentity *next_hop;
1801 struct FriendInfo *target_friend;
1803 uint32_t trail_length;
1804 enum current_destination_type peer_type;
1805 struct GNUNET_PeerIdentity *trail_peer_list;
1806 uint32_t current_trail_index;
1807 unsigned int finger_map_index;
1808 struct GNUNET_PeerIdentity *next_peer;
1810 /* parse and validate message. */
1811 msize = ntohs (message->size);
1812 if (msize < sizeof (struct PeerTrailSetupMessage))
1814 GNUNET_break_op (0);
1818 trail_setup = (struct PeerTrailSetupMessage *) message;
1819 trail_length = ntohl (trail_setup->trail_length);
1820 peer_type = ntohl (trail_setup->current_destination_type);
1821 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_setup[1];
1822 finger_map_index = ntohl (trail_setup->finger_map_index);
1825 sizeof (struct PeerTrailSetupMessage) +
1826 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1828 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1830 GNUNET_break_op (0);
1834 GNUNET_STATISTICS_update (GDS_stats,
1835 gettext_noop ("# TRAIL SETUP requests received"), 1,
1837 GNUNET_STATISTICS_update (GDS_stats,
1838 gettext_noop ("# TRAIL SETUP bytes received"), msize,
1841 if (peer_type == FRIEND)
1843 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
1846 next_hop = find_successor (&(trail_setup->destination_finger),
1847 &(trail_setup->current_destination),
1851 return GNUNET_SYSERR;
1853 else if (peer_type == FINGER)
1855 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
1858 next_hop = GDS_ROUTING_search (&(trail_setup->source_peer),
1859 &(trail_setup->current_destination));
1862 /* This is an optimization. Uncomment when basic code is running first. */
1863 /* I am part of trail.*/
1864 struct GNUNET_PeerIdentity *next_peer_routing_table;
1865 next_peer_routing_table = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1866 next_peer_routing_table = GDS_ROUTING_search (&(trail_setup->source_peer),
1867 &(trail_setup->current_destination));
1869 struct GNUNET_PeerIdentity *next_peer_find_successor;
1870 next_peer_find_successor = find_successor (&(trail_setup->destination_finger),
1871 &(trail_setup->current_destination),
1874 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1875 next_hop = find_closest_destination (next_peer_routing_table,
1876 next_peer_find_successor,
1877 &(trail_setup->destination_finger) );
1882 /* I am the current_destination finger */
1883 next_hop = find_successor (&(trail_setup->destination_finger),
1884 &(trail_setup->current_destination), &(peer_type));
1888 /* If you are the next hop, then you are the final destination */
1889 if (peer_type == MY_ID)
1892 1. You were the destination of this message which means you were already added
1893 in the peer list by previous calling function.
1894 2. current_trail_index should point to the trail element at which the peer
1895 which receives this message should look for the next peer to forward the packet
1897 current_trail_index = trail_length - 2;
1899 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1900 memcpy (next_peer, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
1901 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
1902 GNUNET_free (next_peer);
1904 if(current_trail_index != 0)
1905 current_trail_index = current_trail_index - 1;
1907 GDS_NEIGHBOURS_handle_trail_setup_result (&(trail_setup->source_peer),
1909 target_friend, trail_length,
1910 trail_peer_list, current_trail_index,
1911 trail_setup->successor_flag,
1912 trail_setup->predecessor_flag,
1918 /* Add next hop to list of peers. */
1919 struct GNUNET_PeerIdentity *peer_list;
1920 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1));
1921 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1922 memcpy (&peer_list[trail_length], next_hop, sizeof (struct GNUNET_PeerIdentity));
1925 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1927 if(peer_type == FINGER)
1929 GDS_ROUTING_add (&(trail_setup->source_peer),
1930 &(trail_setup->current_destination),
1934 GDS_NEIGHBOURS_handle_trail_setup (&(trail_setup->source_peer),
1935 &(trail_setup->destination_finger),
1937 trail_setup->trail_length,
1938 peer_list,trail_setup->successor_flag,
1939 trail_setup->predecessor_flag,
1946 * FIXME: For redundant routing, we may start looking for different
1947 * paths to reach to same finger. So, in send_find_finger, we are starting
1948 * the search for trail to a finger, even if we already have found trail to
1949 * reach to it. There are several reasons for doing so
1950 * 1. We may reach to a closer successor than we have at the moment. So, we
1951 * should keep looking for the successor.
1952 * 2. We may reach to the same successor but through a shorter path.
1953 * 3. As I don't know how keys are distributed and how put/get will react
1954 * because of this, I have to think further before implementing it.
1955 * Add an entry in finger table.
1956 * @param finger Finger to be added to finger table
1957 * @param peer_list peers this request has traversed so far
1958 * @param trail_length Numbers of peers in the trail.
1961 void finger_table_add (struct GNUNET_PeerIdentity *finger,
1962 struct GNUNET_PeerIdentity *peer_list,
1963 unsigned int trail_length,
1964 unsigned int successor_flag,
1965 unsigned int predecessor_flag,
1966 unsigned int finger_map_index)
1968 struct FingerInfo *new_finger_entry;
1970 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
1971 memcpy (&(new_finger_entry->finger_identity), finger, sizeof (struct GNUNET_PeerIdentity));
1972 memcpy (&(new_finger_entry->trail_peer_list), peer_list,
1973 sizeof (struct GNUNET_PeerIdentity)* trail_length);
1974 new_finger_entry->successor = successor_flag;
1975 new_finger_entry->predecessor = predecessor_flag;
1976 new_finger_entry->finger_map_index = finger_map_index;
1978 /*FIXME: Is it really a good time to call verify successor message. */
1979 if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap))
1980 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1985 * Core handle for p2p trail construction result messages.
1986 * @param cls closure
1987 * @param message message
1988 * @param peer peer identity this notification is about
1989 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1992 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1993 const struct GNUNET_MessageHeader *message)
1995 struct PeerTrailSetupResultMessage *trail_result;
1997 unsigned int trail_length;
1998 struct GNUNET_PeerIdentity *trail_peer_list;
1999 unsigned int current_trail_index;
2000 struct GNUNET_PeerIdentity *next_peer;
2001 struct FriendInfo *target_friend;
2002 unsigned int finger_map_index;
2004 msize = ntohs (message->size);
2005 if (msize < sizeof (struct PeerTrailSetupMessage))
2007 GNUNET_break_op (0);
2011 trail_result = (struct PeerTrailSetupResultMessage *) message;
2012 trail_length = ntohl (trail_result->trail_length);
2013 current_trail_index = ntohl (trail_result->current_index);
2014 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
2015 finger_map_index = ntohl (trail_result->finger_map_index);
2018 sizeof (struct PeerTrailSetupResultMessage) +
2019 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2021 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2023 GNUNET_break_op (0);
2027 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->current_destination),
2030 if ( 0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2034 /* SUPU: Here I have removed myself from the trail before storing it in
2035 th finger table - to save space, but in case of verify successor result
2036 the result trail does not contain me, and I will never get the message back.
2037 So, keeping myself in the trail list. Think of better solution.*/
2038 struct GNUNET_PeerIdentity *finger_trail;
2039 finger_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - 1));
2041 /* Copy the whole trail_peer_list except the first element into trail */
2043 i = trail_length - 1;
2046 memcpy (&finger_trail[i], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity));
2049 trail_length = trail_length -1 ; /* SUPU: As you removed yourself from the trail.*/
2052 finger_table_add (&(trail_result->finger), trail_peer_list, trail_length,
2053 trail_result->successor_flag, trail_result->predecessor_flag,
2054 trail_result->finger_map_index);
2060 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2061 memcpy (next_peer, &(trail_peer_list[current_trail_index]),
2062 sizeof (struct GNUNET_PeerIdentity));
2063 /* SUPU: here current trail index will always be greater than 0.
2064 so no need for this check here. trail index = 0, contains the final
2065 destination, and if we are in this loop we have not yet reached the
2066 final destination. */
2067 current_trail_index = current_trail_index - 1;
2069 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
2070 GNUNET_free (next_peer);
2072 GDS_NEIGHBOURS_handle_trail_setup_result (&(trail_result->destination_peer),
2073 &(trail_result->finger),
2074 target_friend, trail_length,
2075 trail_peer_list,current_trail_index,
2076 trail_result->successor_flag,
2077 trail_result->predecessor_flag,
2083 return GNUNET_SYSERR;
2088 * SUPU: In this function you don't do anything with trail length
2089 * You increment the current trail index so that you find the correct
2090 * peer to send the packet forward.
2091 * Core handle for p2p verify successor messages.
2092 * @param cls closure
2093 * @param message message
2094 * @param peer peer identity this notification is about
2095 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2098 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2099 const struct GNUNET_MessageHeader *message)
2101 struct PeerVerifySuccessorMessage *vsm;
2103 unsigned int trail_length;
2104 struct GNUNET_PeerIdentity *trail_peer_list;
2105 unsigned int current_trail_index;
2106 struct FriendInfo *target_friend;
2107 struct GNUNET_PeerIdentity *next_hop;
2109 msize = ntohs (message->size);
2110 if (msize < sizeof (struct PeerVerifySuccessorMessage))
2112 GNUNET_break_op (0);
2116 vsm = (struct PeerVerifySuccessorMessage *) message;
2117 trail_length = ntohl (vsm->trail_length);
2118 current_trail_index = ntohl (vsm->current_trail_index);
2120 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
2123 sizeof (struct PeerVerifySuccessorMessage) +
2124 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2126 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2128 GNUNET_break_op (0);
2132 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2134 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),
2137 /* I am the successor, check who is my predecessor. If my predecessor is not
2138 same as source peer then update the trail and send back to calling function.
2140 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2141 struct GNUNET_PeerIdentity key_ret;
2142 unsigned int finger_index;
2143 struct FingerInfo *my_predecessor;
2144 struct GNUNET_PeerIdentity *destination_peer;
2146 /* Iterate over finger peer map and extract your predecessor. */
2147 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2148 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2150 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
2151 (finger_iter,&key_ret,(const void **)&my_predecessor))
2153 if(1 == my_predecessor->predecessor)
2158 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2160 destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2161 memcpy (destination_peer, &(vsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
2162 current_trail_index = trail_length - 2; /*SUPU: I am the last element in the trail.*/
2163 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2164 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2165 GNUNET_free (next_hop);
2167 current_trail_index = current_trail_index - 1;
2169 /* FIXME: Here we should check if our predecessor is source peer or not.
2170 If not then, we can send an updated trail that goes through us. Instead of
2171 looking for a new trail to reach to the new successor, source peer
2172 can just use this trail. It may not be an optimal route. */
2173 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->source_peer),
2174 &(my_predecessor->finger_identity))))
2176 /*If we have a new predecessor, then create a new trail to reach from
2177 vsm source peer to this new successor of source peer. */
2178 struct GNUNET_PeerIdentity *new_successor_trail;
2179 unsigned int my_predecessor_trail_length;
2180 unsigned int new_trail_length;
2183 /* SUPU:my_predecessor_trail will not contain my identity. But the trail
2184 that I got from the requesting peer will contain my identity. */
2185 my_predecessor_trail_length = my_predecessor->trail_length;
2186 new_trail_length = trail_length + my_predecessor_trail_length;
2188 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
2189 * new_trail_length);
2190 memcpy (new_successor_trail, trail_peer_list,
2191 trail_length * sizeof (struct GNUNET_PeerIdentity));
2194 while (i < new_trail_length)
2196 memcpy (&new_successor_trail[i],&(my_predecessor->trail_peer_list[i]),
2197 sizeof (struct GNUNET_PeerIdentity));
2202 GDS_NEIGHBOURS_handle_verify_successor_result (destination_peer,
2204 &(my_predecessor->finger_identity),
2206 new_successor_trail,
2208 current_trail_index);
2211 GDS_NEIGHBOURS_handle_verify_successor_result (destination_peer,
2213 &(my_predecessor->finger_identity),
2217 current_trail_index);
2222 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2223 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2224 GNUNET_free (next_hop);
2226 current_trail_index = current_trail_index + 1;
2228 GDS_NEIGUBOURS_handle_verify_successor(&(vsm->source_peer),
2233 current_trail_index);
2240 * Update successor field in finger table with new successor.
2241 * @param successor New successor which is the predecessor my old successor.
2242 * @param peer_list Trail list to reach to new successor = trail to reach old
2243 * successor + trail to reach to new successor from that old successor.
2244 * @param trail_length Number of peers to reach to the new successor.
2247 update_successor (struct GNUNET_PeerIdentity *successor,
2248 struct GNUNET_PeerIdentity *peer_list,
2249 unsigned int trail_length)
2251 /* FIXME: Here you can call fix_fingers. */
2257 * FIXME: Also copy the trail list in reverse direction that is the path to
2258 * reach to your predecessor.
2259 * Replace your predecessor with new predecessor.
2260 * @param predecessor My new predecessor
2261 * @param peer_list Trail list to reach to my new predecessor
2262 * @param trail_length Number of peers in the trail.
2265 update_predecessor (struct GNUNET_PeerIdentity *predecessor,
2266 struct GNUNET_PeerIdentity *peer_list,
2267 unsigned int trail_length)
2269 /* In this function, you should first read the whole peer_list in
2270 * opposite direction and copy in into trail_peer field of finger entry.
2271 * also search for pervious predecessor and change the predecessor flag to 0.
2272 * add the entry into finger table with predecessor flag = 1.
2274 unsigned int successor_flag;
2275 unsigned int predecessor_flag;
2276 unsigned int finger_index;
2279 predecessor_flag = 1;
2281 /* FIXME: Assumption that predecessor is always stored at current_finger_index = 1.*/
2282 finger_table_add (predecessor, peer_list, trail_length, successor_flag,
2283 predecessor_flag, finger_index);
2285 /* FIXME: Here you should call fix_Fingers. */
2290 * Core handle for p2p notify new successor messages.
2291 * @param cls closure
2292 * @param message message
2293 * @param peer peer identity this notification is about
2294 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2297 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2298 const struct GNUNET_MessageHeader *message)
2300 struct PeerNotifyNewSuccessorMessage *nsm;
2302 unsigned int trail_length;
2303 struct GNUNET_PeerIdentity *trail_peer_list;
2304 unsigned int current_trail_index;
2306 msize = ntohs (message->size);
2307 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
2309 GNUNET_break_op (0);
2313 /* Again in the function you have the whole trail to reach to the destination. */
2314 nsm = (struct PeerNotifyNewSuccessorMessage *) message;
2315 current_trail_index = ntohl (nsm->current_index);
2316 trail_length = ntohl (nsm->trail_length);
2318 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
2321 sizeof (struct PeerNotifyNewSuccessorMessage) +
2322 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2324 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2326 GNUNET_break_op (0);
2330 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer),
2333 update_predecessor (&(nsm->source_peer),
2340 struct FriendInfo *target_friend;
2341 target_friend = GNUNET_malloc (sizeof (struct FriendInfo));
2342 struct GNUNET_PeerIdentity *next_hop;
2343 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2344 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2345 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2346 GNUNET_free (next_hop);
2347 current_trail_index = current_trail_index + 1;
2349 GDS_NEIGHBOURS_notify_new_successor (&(nsm->source_peer),
2350 &(nsm->destination_peer),
2351 target_friend, trail_peer_list, trail_length,
2352 current_trail_index);
2359 * Core handle for p2p verify successor result messages.
2360 * @param cls closure
2361 * @param message message
2362 * @param peer peer identity this notification is about
2363 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2366 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2367 const struct GNUNET_MessageHeader *message)
2369 struct PeerVerifySuccessorResultMessage *vsrm;
2371 struct FriendInfo *target_friend;
2372 unsigned int current_trail_index;
2373 struct GNUNET_PeerIdentity *trail_peer_list;
2374 struct GNUNET_PeerIdentity *next_hop;
2375 unsigned int trail_length;
2377 msize = ntohs (message->size);
2378 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
2380 GNUNET_break_op (0);
2384 /* Again in the function you have the whole trail to reach to the destination. */
2385 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
2386 current_trail_index = ntohl (vsrm->current_index);
2387 trail_length = ntohl (vsrm->trail_length);
2389 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
2392 sizeof (struct PeerVerifySuccessorResultMessage) +
2393 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2395 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2397 GNUNET_break_op (0);
2401 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer),
2405 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor),
2408 update_successor (&(vsrm->my_predecessor), trail_peer_list, trail_length);
2410 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2411 /* FIXME: Assuming that I am also in trail list and I am the first peer. */
2412 memcpy (next_hop, &trail_peer_list[1], sizeof (struct GNUNET_PeerIdentity));
2413 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2414 GNUNET_free (next_hop);
2416 GDS_NEIGHBOURS_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
2417 target_friend, trail_peer_list,
2418 trail_length, current_trail_index);
2423 /* Read the peer trail list and find out the next destination to forward this
2425 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2427 /* FIXME: Assuming that I am also in trail list and I am the first peer. */
2428 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2429 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2430 GNUNET_free (next_hop);
2431 current_trail_index = current_trail_index - 1;
2433 GDS_NEIGHBOURS_handle_verify_successor_result (&(vsrm->destination_peer),
2434 &(vsrm->source_successor),
2435 &(vsrm->my_predecessor),
2439 current_trail_index);
2446 * Initialize neighbours subsystem.
2447 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2450 GDS_NEIGHBOURS_init()
2452 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
2453 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
2454 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
2455 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
2456 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
2457 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
2458 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
2459 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
2463 /*TODO: What is ATS? Why do we need it? */
2464 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
2466 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
2467 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
2468 GNUNET_NO, core_handlers);
2469 if (core_api == NULL)
2470 return GNUNET_SYSERR;
2472 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
2473 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS, GNUNET_NO);
2480 * Shutdown neighbours subsystem.
2483 GDS_NEIGHBOURS_done ()
2485 if (NULL == core_api)
2488 GNUNET_CORE_disconnect (core_api);
2490 GNUNET_ATS_performance_done (atsAPI);
2493 /* FIXME: In case of friends, every time we are disconnected from a friend
2494 we remove it from friend table. So, this assertion works for friend.
2495 But in case of finger_peermap, we never remove any entry from our
2496 finger peermap. So, either when we remove the friend from friend peermap,then
2497 I remove all the finger for which that friend was the first trail and leave
2498 it on send_find_finger_trail to eventually find path to that finger. In that
2499 case may be assertion for finger peermap will also succed. Or else if
2500 peermap are not empty check it and empty it and then destroy because
2501 multipeermpa_destroy does not free individual entries. */
2502 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
2503 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
2504 friend_peermap = NULL;
2506 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
2507 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
2508 finger_peermap = NULL;
2510 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
2512 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
2513 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
2516 /* FIXME: fix_fingers will also be a task like this.
2518 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
2520 GNUNET_SCHEDULER_cancel (verify_successor);
2521 verify_successor = GNUNET_SCHEDULER_NO_TASK;
2528 * Get the ID of the local node.
2530 * @return identity of the local node
2532 struct GNUNET_PeerIdentity *
2533 GDS_NEIGHBOURS_get_id ()
2535 return &my_identity;
2539 /* end of gnunet-service-xdht_neighbours.c */