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 * Head of trail to reach this finger.
589 struct TrailPeerList *head;
592 * Tail of trail to reach this finger.
594 struct TrailPeerList *tail;
600 * Task that sends FIND FINGER TRAIL requests.
602 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
606 * Task that periodically checks for who is my successor.
608 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
611 * Identity of this peer.
613 static struct GNUNET_PeerIdentity my_identity;
616 * Hash map of all the friends of a peer
618 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
621 * Hash map of all the fingers of a peer
623 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
628 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
633 static struct GNUNET_CORE_Handle *core_api;
636 * FIXME: Is it safe to assume its initialized to 0 by default.
637 * The current finger index that we have found trail to.
639 static unsigned int current_finger_index;
643 * Called when core is ready to send a message we asked for
644 * out to the destination.
646 * @param cls the 'struct PeerInfo' of the target peer
647 * @param size number of bytes available in buf
648 * @param buf where the callee should write the message
649 * @return number of bytes written to buf
652 core_transmit_notify (void *cls, size_t size, void *buf)
654 struct FriendInfo *peer = cls;
656 struct P2PPendingMessage *pending;
661 while ((NULL != (pending = peer->head)) &&
662 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
664 peer->pending_count--;
665 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
666 GNUNET_free (pending);
670 /* no messages pending */
676 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
677 GNUNET_CORE_PRIO_BEST_EFFORT,
678 GNUNET_TIME_absolute_get_remaining
679 (pending->timeout), &peer->id,
680 ntohs (pending->msg->size),
681 &core_transmit_notify, peer);
682 GNUNET_break (NULL != peer->th);
686 while ((NULL != (pending = peer->head)) &&
687 (size - off >= (msize = ntohs (pending->msg->size))))
689 GNUNET_STATISTICS_update (GDS_stats,
691 ("# Bytes transmitted to other peers"), msize,
693 memcpy (&cbuf[off], pending->msg, msize);
695 peer->pending_count--;
696 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
697 GNUNET_free (pending);
699 if (peer->head != NULL)
702 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
703 GNUNET_CORE_PRIO_BEST_EFFORT,
704 GNUNET_TIME_absolute_get_remaining
705 (pending->timeout), &peer->id, msize,
706 &core_transmit_notify, peer);
707 GNUNET_break (NULL != peer->th);
714 * Transmit all messages in the friend's message queue.
716 * @param peer message queue to process
719 process_friend_queue (struct FriendInfo *peer)
721 struct P2PPendingMessage *pending;
723 if (NULL == (pending = peer->head))
725 if (NULL != peer->th)
728 GNUNET_STATISTICS_update (GDS_stats,
730 ("# Bytes of bandwidth requested from core"),
731 ntohs (pending->msg->size), GNUNET_NO);
733 /* FIXME: Are we correctly initializing importance and pending. */
735 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
737 GNUNET_TIME_absolute_get_remaining
738 (pending->timeout), &peer->id,
739 ntohs (pending->msg->size),
740 &core_transmit_notify, peer);
741 GNUNET_break (NULL != peer->th);
746 * Setup the trail message and forward it to a friend.
747 * @param source_peer Peer which wants to set up the trail to one of its finger.
748 * @param destination_finger Peer to which we want to set up the trail to.
749 * @param target_friend Current friend to which this message should be forwarded.
750 * @param trail_length Numbers of peers in the trail.
751 * @param trail_peer_list peers this request has traversed so far
752 * @param successor_flag If 1 then we are looking for trail to our successor.
753 * @param predecessor_flag If 1, then we are looking for trail to our predecessor.
754 * @param current_finger_index Finger index in finger peer map
757 GDS_NEIGHBOURS_handle_trail_setup (struct GNUNET_PeerIdentity *source_peer,
758 uint64_t *destination_finger,
759 struct FriendInfo *target_friend,
760 unsigned int trail_length,
761 struct GNUNET_PeerIdentity *trail_peer_list,
762 unsigned int successor_flag,
763 unsigned int predecessor_flag,
764 unsigned int current_finger_index)
766 struct P2PPendingMessage *pending;
767 struct PeerTrailSetupMessage *tsm;
768 struct GNUNET_PeerIdentity *peer_list;
771 msize = sizeof (struct PeerTrailSetupMessage) +
772 (trail_length * sizeof (struct GNUNET_PeerIdentity));
774 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
780 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
782 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
786 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
787 pending->importance = 0; /* FIXME */
788 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
789 tsm = (struct PeerTrailSetupMessage *) &pending[1];
790 pending->msg = &tsm->header;
791 tsm->header.size = htons (msize);
792 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
793 memcpy (&(tsm->destination_finger), destination_finger, sizeof (uint64_t)); /* FIXME: Wrong value of finger identity goes to the target peer in
794 * handle_dht_p2p_trail_setup */
795 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
796 memcpy (&(tsm->current_destination), &(target_friend->id),
797 sizeof (struct GNUNET_PeerIdentity));
798 tsm->current_destination_type = htonl (FRIEND);
799 tsm->trail_length = htonl (trail_length);
800 tsm->finger_map_index = htonl (current_finger_index);
801 if(1 == successor_flag)
803 tsm->successor_flag = htonl(1);
804 tsm->predecessor_flag = htonl (0);
806 else if (1 == predecessor_flag)
808 tsm->predecessor_flag = htonl(1);
809 tsm->successor_flag = htonl(0);
813 tsm->successor_flag = htonl(0);
814 tsm->predecessor_flag = htonl(0);
816 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
817 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
818 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
819 target_friend->pending_count++;
820 process_friend_queue (target_friend);
826 * Handle a tail setup result message.
827 * @param destination_peer Peer which will get the trail to one of its finger.
828 * @param source_finger Peer to which the trail has been setup to.
829 * @param target_friend Friend to which this message should be forwarded.
830 * @param trail_length Numbers of peers in the trail.
831 * @param trail_peer_list Peers which are part of the trail from source to destination.
832 * @param current_trail_index Index in trail_peer_list.
833 * @param successor_flag If 1, then this is the trail to our successor.
834 * @param predecessor_flag If 1, then this is the trail to our predecessor.
835 * @param finger_map_index Finger index in finger peer map
838 GDS_NEIGHBOURS_handle_trail_setup_result (struct GNUNET_PeerIdentity *destination_peer,
839 struct GNUNET_PeerIdentity *source_finger,
840 struct FriendInfo *target_friend,
841 unsigned int trail_length,
842 struct GNUNET_PeerIdentity *trail_peer_list,
843 unsigned int current_trail_index,
844 unsigned int successor_flag,
845 unsigned int predecessor_flag,
846 unsigned int finger_map_index)
848 struct P2PPendingMessage *pending;
849 struct PeerTrailSetupResultMessage *tsrm;
850 struct GNUNET_PeerIdentity *peer_list;
853 msize = sizeof (struct PeerTrailSetupResultMessage) +
854 (trail_length * sizeof (struct GNUNET_PeerIdentity));
856 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
862 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
864 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
868 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
869 pending->importance = 0;
870 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
871 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
872 pending->msg = &tsrm->header;
873 tsrm->header.size = htons (msize);
874 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
875 memcpy (&(tsrm->current_destination), &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
876 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
877 memcpy (&(tsrm->finger), source_finger, sizeof (struct GNUNET_PeerIdentity));
878 tsrm->trail_length = htonl (trail_length);
879 tsrm->current_index = htonl (current_trail_index);
880 tsrm->successor_flag = htonl (successor_flag);
881 tsrm->predecessor_flag = htonl (predecessor_flag);
882 tsrm->finger_map_index = htonl (finger_map_index);
883 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
884 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
886 /* Send the message to chosen friend. */
887 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
888 target_friend->pending_count++;
889 process_friend_queue (target_friend);
894 * Construct a PeerVerifySuccessor message and send it to friend.
895 * @param source_peer Peer which wants to verify its successor
896 * @param successor Peer which is our current successor
897 * @param target_friend Friend to which this message should be forwarded.
898 * @param trail_peer_list Peer which are part of trail from source to destination
899 * @param trail_length Number of peers in the trail list.
900 * @param current_trail_index Index in the trial list at which receiving peer should
901 * get the next element.
903 void GDS_NEIGHBOURS_handle_verify_successor(struct GNUNET_PeerIdentity *source_peer,
904 struct GNUNET_PeerIdentity *successor,
905 struct FriendInfo *target_friend,
906 struct GNUNET_PeerIdentity *trail_peer_list,
907 unsigned int trail_length,
908 unsigned int current_trail_index)
910 struct PeerVerifySuccessorMessage *vsm;
911 struct P2PPendingMessage *pending;
912 struct GNUNET_PeerIdentity *peer_list;
915 msize = sizeof (struct PeerVerifySuccessorMessage) +
916 (trail_length * sizeof (struct GNUNET_PeerIdentity));
918 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
924 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
926 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
930 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
931 pending->importance = 0; /* FIXME */
932 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
933 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
934 pending->msg = &vsm->header;
935 vsm->header.size = htons (msize);
936 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
937 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
938 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
939 vsm->trail_length = htonl (trail_length);
940 vsm->current_trail_index = htonl (current_trail_index);
941 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
942 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
944 /* Send the message to chosen friend. */
945 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
946 target_friend->pending_count++;
947 process_friend_queue (target_friend);
953 * Construct a PeerVerifySuccessorResult message and send it to friend.
954 * @param destination_peer Peer which sent verify successor message
955 * @param source_successor Peer to which verify successor message was sent.
956 * @param my_predecessor source_successor predecessor.
957 * @param target_friend Friend to which this message should be forwarded.
958 * @param trail_peer_list Peer which are part of trail from source to destination
959 * @param trail_length Number of peers in the trail list.
960 * @param current_trail_index Index in the trial list at which receiving peer should
961 * get the next element.
963 void GDS_NEIGHBOURS_handle_verify_successor_result (struct GNUNET_PeerIdentity *destination_peer,
964 struct GNUNET_PeerIdentity *source_successor,
965 struct GNUNET_PeerIdentity *my_predecessor,
966 struct FriendInfo *target_friend,
967 struct GNUNET_PeerIdentity *trail_peer_list,
968 unsigned int trail_length,
969 unsigned int current_trail_index)
971 struct PeerVerifySuccessorResultMessage *vsmr;
972 struct P2PPendingMessage *pending;
973 struct GNUNET_PeerIdentity *peer_list;
976 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
977 (trail_length * sizeof(struct GNUNET_PeerIdentity));
979 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
985 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
987 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
991 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
992 pending->importance = 0; /* FIXME */
993 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
994 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
995 pending->msg = &vsmr->header;
996 vsmr->header.size = htons (msize);
997 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
998 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
999 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1000 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1001 vsmr->trail_length = htonl (trail_length);
1002 vsmr->current_index = htonl (current_trail_index);
1004 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1005 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1007 /* Send the message to chosen friend. */
1008 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1009 target_friend->pending_count++;
1010 process_friend_queue (target_friend);
1015 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1016 * @param source_peer Peer which is sending notify message to its new successor.
1017 * @param destination_peer Peer which is the new destination.
1018 * @param target_friend Next friend to pass this message to.
1019 * @param peer_list List of peers in the trail to reach to destination_peer.
1020 * @param current_trail_index Index of peer_list for next target friend position.
1021 * @param trail_length Total number of peers in peer list
1024 GDS_NEIGHBOURS_notify_new_successor (struct GNUNET_PeerIdentity *source_peer,
1025 struct GNUNET_PeerIdentity *destination_peer,
1026 struct FriendInfo *target_friend,
1027 struct GNUNET_PeerIdentity *trail_peer_list,
1028 unsigned int trail_length,
1029 unsigned int current_trail_index)
1031 struct PeerNotifyNewSuccessorMessage *nsm;
1032 struct P2PPendingMessage *pending;
1033 struct GNUNET_PeerIdentity *peer_list;
1036 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1037 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1039 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1045 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1047 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1051 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1052 pending->importance = 0; /* FIXME */
1053 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1054 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1055 pending->msg = &nsm->header;
1056 nsm->header.size = htons (msize);
1057 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1058 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1059 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1060 nsm->trail_length = htonl (trail_length);
1061 nsm->current_index = htonl (current_trail_index);
1063 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1064 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1066 /* Send the message to chosen friend. */
1067 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1068 target_friend->pending_count++;
1069 process_friend_queue (target_friend);
1073 /**FIXME: Old implementation just to remove error
1074 * TODO: Modify this function to handle our get request.
1075 * Perform a GET operation. Forwards the given request to other
1076 * peers. Does not lookup the key locally. May do nothing if this is
1077 * the only peer in the network (or if we are the closest peer in the
1080 * @param type type of the block
1081 * @param options routing options
1082 * @param desired_replication_level desired replication count
1083 * @param hop_count how many hops did this request traverse so far?
1084 * @param key key for the content
1085 * @param xquery extended query
1086 * @param xquery_size number of bytes in @a xquery
1087 * @param reply_bf bloomfilter to filter duplicates
1088 * @param reply_bf_mutator mutator for @a reply_bf
1089 * @param peer_bf filter for peers not to select (again)
1092 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1093 enum GNUNET_DHT_RouteOption options,
1094 uint32_t desired_replication_level,
1095 uint32_t hop_count, const struct GNUNET_HashCode * key,
1096 const void *xquery, size_t xquery_size,
1097 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
1098 uint32_t reply_bf_mutator,
1099 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1103 1. take the key, get the 64 bit value of the key.
1104 2. call find_successor to get the successor of the key.
1105 3. successor can be either a friend or finger.
1106 4. update the field in get message to reflect if its a friend or finger table
1107 5. add the put message to pending message and send it.
1112 /**FIXME: Old implementation just to remove error.
1113 * TODO: Modify this function to handle our put request.
1114 * Perform a PUT operation. Forwards the given request to other
1115 * peers. Does not store the data locally. Does not give the
1116 * data to local clients. May do nothing if this is the only
1117 * peer in the network (or if we are the closest peer in the
1120 * @param type type of the block
1121 * @param options routing options
1122 * @param desired_replication_level desired replication count
1123 * @param expiration_time when does the content expire
1124 * @param hop_count how many hops has this message traversed so far
1125 * @param bf Bloom filter of peers this PUT has already traversed
1126 * @param key key for the content
1127 * @param put_path_length number of entries in @a put_path
1128 * @param put_path peers this request has traversed so far (if tracked)
1129 * @param data payload to store
1130 * @param data_size number of bytes in @a data
1133 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1134 enum GNUNET_DHT_RouteOption options,
1135 uint32_t desired_replication_level,
1136 struct GNUNET_TIME_Absolute expiration_time,
1138 struct GNUNET_CONTAINER_BloomFilter *bf,
1139 const struct GNUNET_HashCode *key,
1140 unsigned int put_path_length,
1141 struct GNUNET_PeerIdentity *put_path,
1142 const void *data, size_t data_size)
1146 1. take the key, get the 64 bit value of the key.
1147 2. call find_successor to get the successor of the key.
1148 3. successor can be either a friend or finger.
1149 4. update the field in put message to reflect if its a friend or finger table
1150 5. add the put message to pending message and send it.
1152 /* SUPU: Call is made to this function from client. It does not seem to be
1153 waiting for a confirmation So, once we got the request, we use the key and
1154 try to find the closest successor, but in this case when we reach to the
1155 closest successor in handle_dht_p2p_put, then just do datacache_put. As the calling
1156 function does not need any confirmation, we don't need the result back. */
1161 * Randomly choose one of your friends from the friends_peer map
1164 static struct FriendInfo *
1165 select_random_friend()
1167 unsigned int current_size;
1168 unsigned int *index;
1170 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1171 struct GNUNET_PeerIdentity key_ret;
1172 struct FriendInfo *friend;
1174 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1176 /* Element stored at this index in friend_peermap should be selected friend. */
1177 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1179 /* Create an iterator for friend_peermap. */
1180 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1182 /* Set the position of iterator to index. */
1185 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1193 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1203 * Compute finger_identity to which we want to setup the trail
1204 * @return finger_identity
1207 compute_finger_identity()
1210 uint64_t *finger_identity64;
1212 my_id64 = GNUNET_malloc (sizeof (uint64_t));
1213 finger_identity64 = GNUNET_malloc (sizeof (uint64_t));
1215 memcpy (my_id64, &(my_identity.public_key.q_y), sizeof (uint64_t));
1216 *finger_identity64 = fmod ((*my_id64 + pow (2,current_finger_index)),( (pow (2,MAX_FINGERS))));
1218 return finger_identity64;
1223 * Compute immediate predecessor identity in the network.
1224 * @return peer identity of immediate predecessor.
1227 compute_predecessor_identity()
1230 uint64_t *predecessor;
1232 my_id = GNUNET_malloc (sizeof (uint64_t));
1233 predecessor = GNUNET_malloc (sizeof (uint64_t));
1235 memcpy (my_id, &(my_identity.public_key.q_y), sizeof (uint64_t));
1236 *predecessor = fmod ((*my_id -1), (pow (2,MAX_FINGERS)));
1243 * SUPU: You should pass the trail index from where next peer should read. read
1244 * position should be set and after you read you should update the read position
1245 * for next peer in the trail list.
1246 * Periodically ping your successor to ask its current predecessor
1248 * @param cls closure for this task
1249 * @param tc the context under which the task is running
1252 send_verify_successor_message (void *cls,
1253 const struct GNUNET_SCHEDULER_TaskContext *tc )
1255 struct GNUNET_TIME_Relative next_send_time;
1256 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1257 struct GNUNET_PeerIdentity key_ret;
1258 struct FriendInfo *target_friend;
1259 struct GNUNET_PeerIdentity *next_hop;
1260 struct GNUNET_PeerIdentity *peer_list;
1261 unsigned int finger_trail_current_index;
1262 struct FingerInfo *finger;
1263 unsigned int finger_index;
1266 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1267 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1269 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1270 (const void **)&finger))
1272 if (1 == finger->successor)
1276 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1278 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->trail_length);
1280 /* Iterate over your linked list of trail and copy it into peer_list. */
1281 struct TrailPeerList *iterate;
1282 iterate = finger->head;
1284 while ( i < (finger->trail_length))
1286 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1287 iterate = iterate->next;
1291 /* element stored at location 0 is my own identity. element stored at location 1
1293 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1294 memcpy (next_hop, &peer_list[1], sizeof (struct GNUNET_PeerIdentity));
1297 /* Find the friend corresponding to this next hop. */
1298 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1299 finger_trail_current_index = 2;
1300 GDS_NEIGHBOURS_handle_verify_successor (&my_identity,
1301 &(finger->finger_identity),
1304 finger->trail_length,
1305 finger_trail_current_index);
1308 /* FIXME: Use a random value so that this message is send not at the same
1309 interval as send_find_finger_trail_message. */
1310 next_send_time.rel_value_us =
1311 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1312 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1313 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1314 (current_finger_index + 1));
1317 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1323 * Task to send a find finger trail message. We attempt to find trail
1324 * to our fingers, successor and predecessor in the network.
1326 * @param cls closure for this task
1327 * @param tc the context under which the task is running
1330 send_find_finger_trail_message (void *cls,
1331 const struct GNUNET_SCHEDULER_TaskContext *tc)
1333 struct FriendInfo *target_friend;
1334 struct GNUNET_TIME_Relative next_send_time;
1335 struct GNUNET_PeerIdentity *peer_list;
1336 unsigned int successor_flag;
1337 unsigned int predecessor_flag;
1338 uint64_t *finger_identity;
1339 unsigned int finger_index;
1341 /* Initialize flag values */
1342 predecessor_flag = 0;
1345 if (1 == current_finger_index)
1347 /* We have started the process to find the successor. We should search
1348 for our predecessor. */
1349 finger_identity = compute_predecessor_identity();
1350 predecessor_flag = 1;
1355 finger_identity = compute_finger_identity();
1358 if(0 == current_finger_index)
1360 /* We are searching for our successor in the network. */
1365 finger_index = current_finger_index;
1366 current_finger_index = ( current_finger_index + 1) % MAX_FINGERS;
1368 target_friend = select_random_friend();
1370 /* We found a friend.*/
1371 if(NULL != target_friend)
1373 /* Add yourself and selected friend in the trail list. */
1374 unsigned int trail_length = 2;
1375 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
1376 memcpy (&peer_list[0], &(my_identity), sizeof (struct GNUNET_PeerIdentity));
1377 memcpy (&peer_list[1], &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1379 GDS_NEIGHBOURS_handle_trail_setup (&my_identity, finger_identity,
1380 target_friend, trail_length, peer_list,
1381 successor_flag, predecessor_flag,
1385 /* FIXME: Should we be using current_finger_index to generate random interval.*/
1386 next_send_time.rel_value_us =
1387 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1388 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1389 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1390 (current_finger_index + 1));
1392 find_finger_trail_task =
1393 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1399 * Method called whenever a peer connects.
1401 * @param cls closure
1402 * @param peer_identity peer identity this notification is about
1405 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
1407 struct FriendInfo *friend;
1409 /* Check for connect to self message */
1410 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
1413 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
1415 /* If peer already exists in our friend_peermap, then exit. */
1416 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
1422 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
1426 friend = GNUNET_new (struct FriendInfo);
1427 friend->id = *peer_identity;
1429 GNUNET_assert (GNUNET_OK ==
1430 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
1431 peer_identity, friend,
1432 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1435 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
1436 if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
1437 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
1442 * Method called whenever a peer disconnects.
1444 * @param cls closure
1445 * @param peer peer identity this notification is about
1448 handle_core_disconnect (void *cls,
1449 const struct GNUNET_PeerIdentity *peer)
1451 struct FriendInfo *remove_friend;
1453 /* Check for self message. */
1454 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1457 /* Search for peer to remove in your friend_peermap. */
1459 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
1461 if (NULL == remove_friend)
1467 /* Remove the friend from friend_peermap. */
1468 GNUNET_assert (GNUNET_YES ==
1469 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
1473 /* If the peer is removed then all the trail which goes through this
1474 peer also becomes invalid. */
1475 /* FIXME: Iterate over finger peermap, get the trail index and find all the
1476 finger whose trail's first peer was this peer. and remove them from finger
1477 peermap. Assumption that in send_find_finger_trail we will eventually reach
1478 to this finger and we will setup up the new trail.
1479 So, we need a threshold on number of trail thats can go through a node
1480 so that if that nodes go away then also our system is up and runnning.
1481 Where can we specify that threshold.*/
1486 * To be called on core init/fail.
1488 * @param cls service closure
1489 * @param identity the public identity of this peer
1492 core_init (void *cls,
1493 const struct GNUNET_PeerIdentity *identity)
1495 my_identity = *identity;
1500 * Core handler for p2p put requests.
1502 * @param cls closure
1503 * @param peer sender of the request
1504 * @param message message
1505 * @param peer peer identity this notification is about
1506 * @return #GNUNET_OK to keep the connection open,
1507 * #GNUNET_SYSERR to close it (signal serious error)
1510 handle_dht_p2p_put (void *cls,
1511 const struct GNUNET_PeerIdentity *peer,
1512 const struct GNUNET_MessageHeader *message)
1515 1. Check if destination is friend or finger.
1516 2. If finger then get the next hop from routing table and
1517 * call GDS_NEGIHBOURS_handle_get.
1518 3. If friend then call find_successor to get the next hop and again
1519 * call GDS_NEIGHBOURS_handle_get to send to chosen hop.
1520 4. If you are the destination then do datacache_store.
1527 * Core handler for p2p get requests.
1529 * @param cls closure
1530 * @param peer sender of the request
1531 * @param message message
1532 * @return #GNUNET_OK to keep the connection open,
1533 * #GNUNET_SYSERR to close it (signal serious error)
1536 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1537 const struct GNUNET_MessageHeader *message)
1540 1. Check if destination is friend or finger.
1541 2. If finger then get the next hop from routing table and
1542 * call GDS_NEGIHBOURS_handle_get.
1543 3. If friend then call find_successor to get the next hop and again
1544 * call GDS_NEIGHBOURS_handle_get to send to chosen hop.
1545 4. If you are the destination then send the data back to source peer
1546 * Assuming we have trail setup we can
1547 * either store the whole trail or again do the search process..
1554 * Compare two peer identities.
1555 * @param p1 Peer identity
1556 * @param p2 Peer identity
1557 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
1561 compare_peer_id (const void *p1, const void *p2)
1563 return memcmp (p1, p2, sizeof (uint64_t));;
1568 * Returns the previous element of value in all_known_peers.
1569 * @param all_known_peers list of all the peers
1570 * @param value value we have to search in the all_known_peers.
1574 static struct GNUNET_PeerIdentity *
1575 binary_search(struct GNUNET_PeerIdentity *all_known_peers, uint64_t *value,
1581 struct GNUNET_PeerIdentity *successor;
1582 successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1586 middle = (first + last)/2;
1588 while(first <= last)
1590 if(compare_peer_id(&all_known_peers[middle], &value) > 0)
1594 else if(0 == compare_peer_id(&all_known_peers[middle], &value))
1598 memcpy (successor, &(all_known_peers[size - 1]), sizeof (struct GNUNET_PeerIdentity));
1602 memcpy (successor, &(all_known_peers[middle-1]), sizeof (struct GNUNET_PeerIdentity));
1610 middle = (first + last)/2;
1618 * Find closest successor for the value.
1619 * @param value Value for which we are looking for successor
1620 * @param current_destination NULL if my_identity is successor else finger/friend
1622 * @param type Next destination type
1623 * @return Peer identity of next destination i.e. successor of value.
1625 static struct GNUNET_PeerIdentity *
1626 find_successor(uint64_t *value, struct GNUNET_PeerIdentity *current_destination,
1627 enum current_destination_type *type)
1630 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1631 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1632 struct GNUNET_PeerIdentity key_ret;
1633 struct FriendInfo *friend;
1634 struct FingerInfo *finger;
1635 unsigned int finger_index;
1636 unsigned int friend_index;
1637 struct GNUNET_PeerIdentity *all_known_peers;
1638 struct GNUNET_PeerIdentity *successor;
1642 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
1643 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
1644 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
1647 all_known_peers = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * size);
1649 /* Copy your identity at 0th index in all_known_peers. */
1651 memcpy (&all_known_peers[j], &(my_identity), sizeof (struct GNUNET_PeerIdentity));
1653 /* Copy the value that you are searching at index 1 in all_known_peers. */
1655 memcpy (&all_known_peers[j], value, sizeof(uint64_t));
1657 /* Iterate over friend peer map and copy all the elements into array. */
1658 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1659 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1661 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1663 memcpy (&all_known_peers[j], &(friend->id), sizeof (struct GNUNET_PeerIdentity));
1668 /* Iterate over finger map and copy all the entries into all_known_peers array. */
1669 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1670 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1672 /* FIXME: I don't think we are actually iterating.
1673 Read about how to iterate over the multi peer map. */
1674 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1676 memcpy (&all_known_peers[j], &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1681 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1682 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
1684 /* FIMXE : Should we not sort it for 64 bits. */
1685 qsort (all_known_peers, size, sizeof (uint64_t), &compare_peer_id);
1687 /* search value in all_known_peers array. */
1688 successor = binary_search (all_known_peers, value, size);
1690 /* compare successor with my_identity, finger and friend */
1691 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&(my_identity), successor))
1693 FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
1697 else if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
1700 FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
1702 memcpy (current_destination, successor, sizeof (struct GNUNET_PeerIdentity));
1705 else if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (finger_peermap,
1708 FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
1710 memcpy (current_destination, successor, sizeof (struct GNUNET_PeerIdentity));
1711 /* get the corresponding finger for succcesor and read the first element from
1712 the trail list and return that element. */
1713 struct FingerInfo *successor_finger;
1714 struct GNUNET_PeerIdentity *next_hop;
1715 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1716 successor_finger = GNUNET_CONTAINER_multipeermap_get (finger_peermap, successor);
1717 //memcpy (next_hop, &(successor_finger->trail_peer_list[0]), sizeof (struct GNUNET_PeerIdentity));
1720 FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
1724 return &my_identity;
1729 * SUPU: The first element in the trail setup message is your identity.
1730 * in this function you should increment the trail length.
1731 * Handle a PeerTrailSetupMessage.
1732 * @param cls closure
1733 * @param message message
1734 * @param peer peer identity this notification is about
1735 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1738 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1739 const struct GNUNET_MessageHeader *message)
1741 struct PeerTrailSetupMessage *trail_setup;
1742 struct GNUNET_PeerIdentity *next_hop;
1743 struct FriendInfo *target_friend;
1745 uint32_t trail_length;
1746 enum current_destination_type peer_type;
1747 struct GNUNET_PeerIdentity *trail_peer_list;
1748 uint32_t current_trail_index;
1749 unsigned int finger_map_index;
1750 struct GNUNET_PeerIdentity *next_peer;
1751 unsigned int successor_flag;
1752 unsigned int predecessor_flag;
1754 /* parse and validate message. */
1755 msize = ntohs (message->size);
1756 if (msize < sizeof (struct PeerTrailSetupMessage))
1758 GNUNET_break_op (0);
1763 trail_setup = (struct PeerTrailSetupMessage *) message;
1764 trail_length = ntohl (trail_setup->trail_length);
1765 peer_type = ntohl (trail_setup->current_destination_type);
1766 finger_map_index = ntohl (trail_setup->finger_map_index);
1767 successor_flag = ntohl (trail_setup->successor_flag);
1768 predecessor_flag = ntohl (trail_setup->predecessor_flag);
1770 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_setup[1];
1773 sizeof (struct PeerTrailSetupMessage) +
1774 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1776 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1778 GNUNET_break_op (0);
1782 GNUNET_STATISTICS_update (GDS_stats,
1783 gettext_noop ("# TRAIL SETUP requests received"), 1,
1785 GNUNET_STATISTICS_update (GDS_stats,
1786 gettext_noop ("# TRAIL SETUP bytes received"), msize,
1789 if (peer_type == FRIEND)
1791 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
1794 next_hop = find_successor (&(trail_setup->destination_finger),
1795 &(trail_setup->current_destination),
1799 return GNUNET_SYSERR;
1801 else if (peer_type == FINGER)
1803 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
1806 next_hop = GDS_ROUTING_search (&(trail_setup->source_peer),
1807 &(trail_setup->current_destination));
1810 /* This is an optimization. Uncomment when basic code is running first. */
1811 /* I am part of trail.*/
1812 struct GNUNET_PeerIdentity *next_peer_routing_table;
1813 next_peer_routing_table = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1814 next_peer_routing_table = GDS_ROUTING_search (&(trail_setup->source_peer),
1815 &(trail_setup->current_destination));
1817 struct GNUNET_PeerIdentity *next_peer_find_successor;
1818 next_peer_find_successor = find_successor (&(trail_setup->destination_finger),
1819 &(trail_setup->current_destination),
1822 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1823 next_hop = find_closest_destination (next_peer_routing_table,
1824 next_peer_find_successor,
1825 &(trail_setup->destination_finger) );
1830 /* I am the current_destination finger */
1831 next_hop = find_successor (&(trail_setup->destination_finger),
1832 &(trail_setup->current_destination), &(peer_type));
1836 /* If you are the next hop, then you are the final destination */
1837 if (peer_type == MY_ID)
1840 1. You were the destination of this message which means you were already added
1841 in the peer list by previous calling function.
1842 2. current_trail_index should point to the trail element at which the peer
1843 which receives this message should look for the next peer to forward the packet
1845 current_trail_index = trail_length - 2;
1846 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1847 memcpy (next_peer, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
1848 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
1849 GNUNET_free (next_peer);
1851 if(current_trail_index != 0)
1852 current_trail_index = current_trail_index - 1;
1854 GDS_NEIGHBOURS_handle_trail_setup_result (&(trail_setup->source_peer),
1856 target_friend, trail_length,
1857 trail_peer_list, current_trail_index,
1865 /* Add next hop to list of peers. */
1866 struct GNUNET_PeerIdentity *peer_list;
1867 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1));
1868 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1869 memcpy (&peer_list[trail_length], next_hop, sizeof (struct GNUNET_PeerIdentity));
1872 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1874 if(peer_type == FINGER)
1876 GDS_ROUTING_add (&(trail_setup->source_peer),
1877 &(trail_setup->current_destination),
1881 GDS_NEIGHBOURS_handle_trail_setup (&(trail_setup->source_peer),
1882 &(trail_setup->destination_finger),
1884 trail_setup->trail_length,
1885 peer_list,trail_setup->successor_flag,
1886 trail_setup->predecessor_flag,
1894 * FIXME: For redundant routing, we may start looking for different
1895 * paths to reach to same finger. So, in send_find_finger, we are starting
1896 * the search for trail to a finger, even if we already have found trail to
1897 * reach to it. There are several reasons for doing so
1898 * 1. We may reach to a closer successor than we have at the moment. So, we
1899 * should keep looking for the successor.
1900 * 2. We may reach to the same successor but through a shorter path.
1901 * 3. As I don't know how keys are distributed and how put/get will react
1902 * because of this, I have to think further before implementing it.
1903 * Add an entry in finger table.
1904 * @param finger Finger to be added to finger table
1905 * @param peer_list peers this request has traversed so far
1906 * @param trail_length Numbers of peers in the trail.
1909 void finger_table_add (struct GNUNET_PeerIdentity *finger,
1910 struct GNUNET_PeerIdentity *peer_list,
1911 unsigned int trail_length,
1912 unsigned int successor_flag,
1913 unsigned int predecessor_flag,
1914 unsigned int finger_map_index)
1916 struct FingerInfo *new_finger_entry;
1918 /** SUPU: when we add an entry then we should look if
1919 * we already have an entry for that index. If yes, then
1920 * 1) if both the finger identity are same, and same first friend, then choose
1921 * the one with shorter trail length.
1922 * 2) if the finger identity is different, then keep the one which is closest.*/
1924 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
1925 memcpy (&(new_finger_entry->finger_identity), finger, sizeof (struct GNUNET_PeerIdentity));
1928 /* Insert elements of peer_list into TrailPeerList. */
1930 while (i < trail_length)
1932 struct TrailPeerList *element;
1933 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1934 element->next = NULL;
1935 element->prev = NULL;
1937 memcpy (&(element->peer), &peer_list[i], sizeof(struct GNUNET_PeerIdentity));
1938 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
1943 new_finger_entry->successor = successor_flag;
1944 new_finger_entry->predecessor = predecessor_flag;
1945 new_finger_entry->finger_map_index = finger_map_index;
1946 new_finger_entry->trail_length = trail_length;
1949 GNUNET_assert (GNUNET_OK ==
1950 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1951 &(new_finger_entry->finger_identity),
1953 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1955 /*FIXME: Is it really a good time to call verify successor message. */
1956 if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap))
1958 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1964 * Core handle for p2p trail construction result messages.
1965 * @param cls closure
1966 * @param message message
1967 * @param peer peer identity this notification is about
1968 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1971 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1972 const struct GNUNET_MessageHeader *message)
1974 struct PeerTrailSetupResultMessage *trail_result;
1976 unsigned int trail_length;
1977 struct GNUNET_PeerIdentity *trail_peer_list;
1978 unsigned int current_trail_index;
1979 struct GNUNET_PeerIdentity *next_peer;
1980 struct FriendInfo *target_friend;
1981 unsigned int finger_map_index;
1982 unsigned int successor_flag;
1983 unsigned int predecessor_flag;
1985 msize = ntohs (message->size);
1986 if (msize < sizeof (struct PeerTrailSetupMessage))
1988 GNUNET_break_op (0);
1992 trail_result = (struct PeerTrailSetupResultMessage *) message;
1993 trail_length = ntohl (trail_result->trail_length);
1996 sizeof (struct PeerTrailSetupResultMessage) +
1997 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1999 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2001 GNUNET_break_op (0);
2005 current_trail_index = ntohl (trail_result->current_index);
2006 successor_flag = ntohl (trail_result->successor_flag);
2007 predecessor_flag = ntohl (trail_result->predecessor_flag);
2008 finger_map_index = ntohl (trail_result->finger_map_index);
2010 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
2012 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->current_destination),
2015 if ( 0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2019 /* SUPU: Here I have removed myself from the trail before storing it in
2020 th finger table - to save space, but in case of verify successor result
2021 the result trail does not contain me, and I will never get the message back.
2022 So, keeping myself in the trail list. Think of better solution.*/
2023 struct GNUNET_PeerIdentity *finger_trail;
2024 finger_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - 1));
2026 /* Copy the whole trail_peer_list except the first element into trail */
2028 i = trail_length - 1;
2031 memcpy (&finger_trail[i], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity));
2034 trail_length = trail_length -1 ; SUPU: As you removed yourself from the trail.*/
2037 finger_table_add (&(trail_result->finger), trail_peer_list, trail_length,
2038 successor_flag, predecessor_flag,
2045 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2046 memcpy (next_peer, &(trail_peer_list[current_trail_index]),
2047 sizeof (struct GNUNET_PeerIdentity));
2048 /* SUPU: here current trail index will always be greater than 0.
2049 so no need for this check here. trail index = 0, contains the final
2050 destination, and if we are in this loop we have not yet reached the
2051 final destination. */
2052 current_trail_index = current_trail_index - 1;
2054 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
2055 GNUNET_free (next_peer);
2057 GDS_NEIGHBOURS_handle_trail_setup_result (&(trail_result->destination_peer),
2058 &(trail_result->finger),
2059 target_friend, trail_length,
2060 trail_peer_list,current_trail_index,
2061 trail_result->successor_flag,
2062 trail_result->predecessor_flag,
2068 return GNUNET_SYSERR;
2073 * SUPU: In this function you don't do anything with trail length
2074 * You increment the current trail index so that you find the correct
2075 * peer to send the packet forward.
2076 * Core handle for p2p verify successor messages.
2077 * @param cls closure
2078 * @param message message
2079 * @param peer peer identity this notification is about
2080 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2083 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2084 const struct GNUNET_MessageHeader *message)
2086 struct PeerVerifySuccessorMessage *vsm;
2088 unsigned int trail_length;
2089 struct GNUNET_PeerIdentity *trail_peer_list;
2090 unsigned int current_trail_index;
2091 struct FriendInfo *target_friend;
2092 struct GNUNET_PeerIdentity *next_hop;
2094 msize = ntohs (message->size);
2095 if (msize < sizeof (struct PeerVerifySuccessorMessage))
2097 GNUNET_break_op (0);
2101 vsm = (struct PeerVerifySuccessorMessage *) message;
2102 trail_length = ntohl (vsm->trail_length);
2105 sizeof (struct PeerVerifySuccessorMessage) +
2106 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2108 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2110 GNUNET_break_op (0);
2114 current_trail_index = ntohl (vsm->current_trail_index);
2116 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
2118 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2120 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),
2123 /* I am the successor, check who is my predecessor. If my predecessor is not
2124 same as source peer then update the trail and send back to calling function.
2126 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2127 struct GNUNET_PeerIdentity key_ret;
2128 unsigned int finger_index;
2129 struct FingerInfo *my_predecessor;
2130 struct GNUNET_PeerIdentity *destination_peer;
2132 /* Iterate over finger peer map and extract your predecessor. */
2133 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2134 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2136 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
2137 (finger_iter,&key_ret,(const void **)&my_predecessor))
2139 if(1 == my_predecessor->predecessor)
2144 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2145 destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2146 memcpy (destination_peer, &(vsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
2147 current_trail_index = trail_length - 2; /*SUPU: I am the last element in the trail.*/
2148 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2149 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2150 GNUNET_free (next_hop);
2152 if (current_trail_index != 0)
2153 current_trail_index = current_trail_index - 1;
2155 /* FIXME: Here we should check if our predecessor is source peer or not.
2156 If not then, we can send an updated trail that goes through us. Instead of
2157 looking for a new trail to reach to the new successor, source peer
2158 can just use this trail. It may not be an optimal route. */
2159 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->source_peer),
2160 &(my_predecessor->finger_identity))))
2162 /*If we have a new predecessor, then create a new trail to reach from
2163 vsm source peer to this new successor of source peer. */
2164 struct GNUNET_PeerIdentity *new_successor_trail;
2165 unsigned int my_predecessor_trail_length;
2166 unsigned int new_trail_length;
2169 /* SUPU: The trail that we store corresponding to each finger contains
2170 * me as the first element. So, we are included twice when we join the
2172 my_predecessor_trail_length = (my_predecessor->trail_length) - 1; /*SUPU: Removing myself from the trail */
2173 new_trail_length = trail_length + my_predecessor_trail_length;
2175 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
2176 * new_trail_length);
2177 memcpy (new_successor_trail, trail_peer_list,
2178 trail_length * sizeof (struct GNUNET_PeerIdentity));
2180 struct TrailPeerList *iterator;
2181 iterator = my_predecessor->head->next; /* FIXME: Check if you are removing yourself */
2183 while (i < new_trail_length)
2185 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2186 iterator = iterator->next;
2191 GDS_NEIGHBOURS_handle_verify_successor_result (destination_peer,
2193 &(my_predecessor->finger_identity),
2195 new_successor_trail,
2197 current_trail_index);
2200 GDS_NEIGHBOURS_handle_verify_successor_result (destination_peer,
2202 &(my_predecessor->finger_identity),
2206 current_trail_index);
2211 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2212 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2213 GNUNET_free (next_hop);
2215 current_trail_index = current_trail_index + 1;
2217 GDS_NEIGHBOURS_handle_verify_successor(&(vsm->source_peer),
2222 current_trail_index);
2229 * Update successor field in finger table with new successor.
2230 * @param successor New successor which is the predecessor my old successor.
2231 * @param peer_list Trail list to reach to new successor = trail to reach old
2232 * successor + trail to reach to new successor from that old successor.
2233 * @param trail_length Number of peers to reach to the new successor.
2236 update_successor (struct GNUNET_PeerIdentity *successor_identity,
2237 struct GNUNET_PeerIdentity *peer_list,
2238 unsigned int trail_length)
2240 struct FingerInfo *new_finger_entry;
2243 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2244 new_finger_entry->predecessor = 0;
2245 new_finger_entry->successor = 1;
2246 new_finger_entry->trail_length = trail_length;
2247 new_finger_entry->finger_map_index = 0;
2248 memcpy (&(new_finger_entry->finger_identity), successor_identity, sizeof (struct GNUNET_PeerIdentity));
2251 while (i < trail_length)
2253 struct TrailPeerList *element;
2254 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2255 element->next = NULL;
2256 element->prev = NULL;
2258 memcpy (&(element->peer), &peer_list[i], sizeof(struct GNUNET_PeerIdentity));
2259 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
2266 * FIXME: Also copy the trail list in reverse direction that is the path to
2267 * reach to your predecessor.
2268 * Replace your predecessor with new predecessor.
2269 * @param predecessor My new predecessor
2270 * @param peer_list Trail list to reach to my new predecessor
2271 * @param trail_length Number of peers in the trail.
2274 update_predecessor (struct GNUNET_PeerIdentity *predecessor,
2275 struct GNUNET_PeerIdentity *peer_list,
2276 unsigned int trail_length)
2278 struct GNUNET_PeerIdentity *trail_peer_list;
2279 struct FingerInfo *new_finger_entry;
2283 i = trail_length - 1;
2285 trail_peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2289 memcpy( &trail_peer_list[j], &peer_list[i], sizeof (struct GNUNET_PeerIdentity));
2293 memcpy (&trail_peer_list[j], &peer_list[i], sizeof(struct GNUNET_PeerIdentity));
2295 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2296 memcpy (&(new_finger_entry->finger_identity), predecessor, sizeof (struct GNUNET_PeerIdentity));
2297 new_finger_entry->finger_map_index = 1;
2298 new_finger_entry->predecessor = 1;
2299 new_finger_entry->successor = 0;
2302 while (i < trail_length)
2304 struct TrailPeerList *element;
2305 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2306 element->next = NULL;
2307 element->prev = NULL;
2309 memcpy (&(element->peer), &trail_peer_list[i], sizeof(struct GNUNET_PeerIdentity));
2310 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
2317 * Core handle for p2p notify new successor messages.
2318 * @param cls closure
2319 * @param message message
2320 * @param peer peer identity this notification is about
2321 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2324 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2325 const struct GNUNET_MessageHeader *message)
2327 struct PeerNotifyNewSuccessorMessage *nsm;
2329 unsigned int trail_length;
2330 struct GNUNET_PeerIdentity *trail_peer_list;
2331 unsigned int current_trail_index;
2333 msize = ntohs (message->size);
2334 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
2336 GNUNET_break_op (0);
2340 /* Again in the function you have the whole trail to reach to the destination. */
2341 nsm = (struct PeerNotifyNewSuccessorMessage *) message;
2342 trail_length = ntohl (nsm->trail_length);
2345 sizeof (struct PeerNotifyNewSuccessorMessage) +
2346 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2348 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2350 GNUNET_break_op (0);
2354 current_trail_index = ntohl (nsm->current_index);
2355 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
2357 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer),
2360 update_predecessor (&(nsm->source_peer),
2367 struct FriendInfo *target_friend;
2368 target_friend = GNUNET_malloc (sizeof (struct FriendInfo));
2369 struct GNUNET_PeerIdentity *next_hop;
2370 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2371 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2372 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2373 GNUNET_free (next_hop);
2374 current_trail_index = current_trail_index + 1;
2376 GDS_NEIGHBOURS_notify_new_successor (&(nsm->source_peer),
2377 &(nsm->destination_peer),
2378 target_friend, trail_peer_list, trail_length,
2379 current_trail_index);
2386 * Core handle for p2p verify successor result messages.
2387 * @param cls closure
2388 * @param message message
2389 * @param peer peer identity this notification is about
2390 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2393 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2394 const struct GNUNET_MessageHeader *message)
2396 struct PeerVerifySuccessorResultMessage *vsrm;
2398 struct FriendInfo *target_friend;
2399 unsigned int current_trail_index;
2400 struct GNUNET_PeerIdentity *trail_peer_list;
2401 struct GNUNET_PeerIdentity *next_hop;
2402 unsigned int trail_length;
2404 msize = ntohs (message->size);
2405 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
2407 GNUNET_break_op (0);
2411 /* Again in the function you have the whole trail to reach to the destination. */
2412 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
2413 current_trail_index = ntohl (vsrm->current_index);
2414 trail_length = ntohl (vsrm->trail_length);
2416 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
2419 sizeof (struct PeerVerifySuccessorResultMessage) +
2420 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2422 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2424 GNUNET_break_op (0);
2428 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer),
2431 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor),
2434 update_successor (&(vsrm->my_predecessor), trail_peer_list, trail_length);
2436 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2437 /* FIXME: Assuming that I am also in trail list and I am the first peer. */
2438 memcpy (next_hop, &trail_peer_list[1], sizeof (struct GNUNET_PeerIdentity));
2439 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2440 GNUNET_free (next_hop);
2442 GDS_NEIGHBOURS_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
2443 target_friend, trail_peer_list,
2444 trail_length, current_trail_index);
2449 /* Read the peer trail list and find out the next destination to forward this
2451 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2453 /* FIXME: Assuming that I am also in trail list and I am the first peer. */
2454 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2455 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2456 GNUNET_free (next_hop);
2457 current_trail_index = current_trail_index - 1;
2459 GDS_NEIGHBOURS_handle_verify_successor_result (&(vsrm->destination_peer),
2460 &(vsrm->source_successor),
2461 &(vsrm->my_predecessor),
2465 current_trail_index);
2472 * Initialize neighbours subsystem.
2473 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2476 GDS_NEIGHBOURS_init()
2478 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
2479 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
2480 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
2481 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
2482 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
2483 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
2484 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
2485 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
2490 /*TODO: What is ATS? Why do we need it? */
2491 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
2493 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
2494 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
2495 GNUNET_NO, core_handlers);
2496 if (NULL == core_api)
2497 return GNUNET_SYSERR;
2499 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
2500 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS, GNUNET_NO);
2507 * Shutdown neighbours subsystem.
2510 GDS_NEIGHBOURS_done ()
2512 if (NULL == core_api)
2515 GNUNET_CORE_disconnect (core_api);
2517 GNUNET_ATS_performance_done (atsAPI);
2520 /* FIXME: In case of friends, every time we are disconnected from a friend
2521 we remove it from friend table. So, this assertion works for friend.
2522 But in case of finger_peermap, we never remove any entry from our
2523 finger peermap. So, either when we remove the friend from friend peermap,then
2524 I remove all the finger for which that friend was the first trail and leave
2525 it on send_find_finger_trail to eventually find path to that finger. In that
2526 case may be assertion for finger peermap will also succed. Or else if
2527 peermap are not empty check it and empty it and then destroy because
2528 multipeermpa_destroy does not free individual entries. */
2529 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
2530 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
2531 friend_peermap = NULL;
2533 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
2534 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
2535 finger_peermap = NULL;
2537 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
2539 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
2540 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
2543 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
2545 GNUNET_SCHEDULER_cancel (verify_successor);
2546 verify_successor = GNUNET_SCHEDULER_NO_TASK;
2553 * Get the ID of the local node.
2555 * @return identity of the local node
2557 struct GNUNET_PeerIdentity *
2558 GDS_NEIGHBOURS_get_id ()
2560 return &my_identity;
2564 /* end of gnunet-service-xdht_neighbours.c */