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
247 * P2P Trail setup message
249 struct PeerTrailSetupMessage
253 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
255 struct GNUNET_MessageHeader header;
258 * Source peer which wants to setup the trail to one of its finger.
260 struct GNUNET_PeerIdentity source_peer;
263 * Finger id to which we want to set up the trail to.
265 uint64_t destination_finger;
268 * If set to 1, then we are looking for trail to our immediate successor.
270 unsigned int successor_flag;
273 * If set to 1, then we are looking for trail to our immediate predecessor.
275 unsigned int predecessor_flag;
278 * Peer which gets this message can be either an intermediate finger or friend.
280 enum current_destination_type current_destination_type;
283 * Peer to which this packet is forwarded.
285 struct GNUNET_PeerIdentity current_destination;
288 * Index into finger peer map.
290 unsigned int finger_map_index;
293 * Number of entries in trail list.
295 uint32_t trail_length GNUNET_PACKED;
301 * P2P Trail setup Result message
303 struct PeerTrailSetupResultMessage
307 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
309 struct GNUNET_MessageHeader header;
312 * Finger to which we have found the path.
314 struct GNUNET_PeerIdentity finger;
317 * Peer which was looking for the trail to finger.
319 struct GNUNET_PeerIdentity destination_peer;
322 * Peer to which this packet is forwarded next.
324 struct GNUNET_PeerIdentity current_destination;
327 * Index at which peer list should be accessed.
329 unsigned int current_index;
332 * If set to 1, then this trail is the trail to our successor.
334 unsigned int successor_flag;
337 * If set to 1, then this trail is the trail to our predecessor.
339 unsigned int predecessor_flag;
342 * Index into finger peer map
344 unsigned int finger_map_index;
347 * Number of entries in trail list.
349 uint32_t trail_length GNUNET_PACKED;
355 * P2P verify successor message.
357 struct PeerVerifySuccessorMessage
361 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
363 struct GNUNET_MessageHeader header;
366 * Source peer which wants to verify its successor.
368 struct GNUNET_PeerIdentity source_peer;
371 * My current successor.
373 struct GNUNET_PeerIdentity successor;
376 * Total number of peers in trail to current successor.
378 unsigned int trail_length;
381 * Index in trail which points to next destination to send this message.
383 unsigned int current_trail_index;
389 * P2P verify successor result message.
391 struct PeerVerifySuccessorResultMessage
395 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
397 struct GNUNET_MessageHeader header;
400 * Destination peer which sent the request to verify its successor.
402 struct GNUNET_PeerIdentity destination_peer;
405 * Successor to which PeerVerifySuccessorMessage was sent.
407 struct GNUNET_PeerIdentity source_successor;
410 * source_successor's predecessor
412 struct GNUNET_PeerIdentity my_predecessor;
415 * Total number of peers in trail.
416 * If source_successor is not destination peer, then trail is from destination_peer
418 * If source_successor is destination peer, then trail is from destination_peer
419 * to source_successor.
421 unsigned int trail_length;
424 * Index in trail which points to next destination to send this message.
426 unsigned int current_index;
431 * P2P notify new successor message.
433 struct PeerNotifyNewSuccessorMessage
436 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
438 struct GNUNET_MessageHeader header;
441 * Source peer which wants to notify its new successor.
443 struct GNUNET_PeerIdentity source_peer;
446 * New successor identity.
448 struct GNUNET_PeerIdentity destination_peer;
451 * Number of peers in trail from source_peer to new successor.
453 unsigned int trail_length;
456 * Index in trail which points to next destination to send this message.
458 unsigned int current_index;
463 GNUNET_NETWORK_STRUCT_END
467 * Linked list of messages to send to a particular other peer.
469 struct P2PPendingMessage
472 * Pointer to next item in the list
474 struct P2PPendingMessage *next;
477 * Pointer to previous item in the list
479 struct P2PPendingMessage *prev;
482 * When does this message time out?
484 struct GNUNET_TIME_Absolute timeout;
487 * Message importance level. FIXME: used? useful?
489 unsigned int importance;
492 * Actual message to be sent, allocated at the end of the struct:
493 * // msg = (cast) &pm[1];
494 * // memcpy (&pm[1], data, len);
496 const struct GNUNET_MessageHeader *msg;
502 * Linked List of peers which are part of trail to reach a particular Finger.
507 * Pointer to next item in the list
509 struct TrailPeerList *next;
512 * Pointer to previous item in the list
514 struct TrailPeerList *prev;
517 * An element in this trail list
519 struct GNUNET_PeerIdentity peer;
525 * Entry in friend_peermap.
532 struct GNUNET_PeerIdentity id;
535 * Count of outstanding messages for this friend.
537 unsigned int pending_count;
540 * Head of pending messages to be sent to this friend.
542 struct P2PPendingMessage *head;
545 * Tail of pending messages to be sent to this friend.
547 struct P2PPendingMessage *tail;
550 * Core handle for sending messages to this friend.
552 struct GNUNET_CORE_TransmitHandle *th;
558 * Entry in finger_peermap.
565 struct GNUNET_PeerIdentity finger_identity;
568 * If 1, then this finger entry is my first finger(successor).
570 unsigned int successor;
573 * If 1, then this finger entry is my first predecessor.
575 unsigned int predecessor;
578 * Index in finger peer map
580 unsigned int finger_map_index;
583 * Total number of entries in trail from me to finger.
585 unsigned int trail_length;
588 * Head of trail to reach this finger.
590 struct TrailPeerList *head;
593 * Tail of trail to reach this finger.
595 struct TrailPeerList *tail;
600 * Data structure passed to sorting algorithm in find_successor.
604 /* 64 bit value of peer identity */
607 /* Type : MY_ID, FINGER, FINGER */
608 enum current_destination_type type;
610 /* Pointer to original data structure linked to peer id. */
616 * Task that sends FIND FINGER TRAIL requests.
618 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
622 * Task that periodically checks for who is my successor.
624 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
627 * Identity of this peer.
629 static struct GNUNET_PeerIdentity my_identity;
632 * Hash map of all the friends of a peer
634 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
637 * Hash map of all the fingers of a peer
639 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
644 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
649 static struct GNUNET_CORE_Handle *core_api;
652 * FIXME: Is it safe to assume its initialized to 0 by default.
653 * The current finger index that we have found trail to.
655 static unsigned int current_finger_index;
659 * Called when core is ready to send a message we asked for
660 * out to the destination.
662 * @param cls the 'struct PeerInfo' of the target peer
663 * @param size number of bytes available in buf
664 * @param buf where the callee should write the message
665 * @return number of bytes written to buf
668 core_transmit_notify (void *cls, size_t size, void *buf)
670 struct FriendInfo *peer = cls;
672 struct P2PPendingMessage *pending;
677 while ((NULL != (pending = peer->head)) &&
678 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
680 peer->pending_count--;
681 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
682 GNUNET_free (pending);
686 /* no messages pending */
692 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
693 GNUNET_CORE_PRIO_BEST_EFFORT,
694 GNUNET_TIME_absolute_get_remaining
695 (pending->timeout), &peer->id,
696 ntohs (pending->msg->size),
697 &core_transmit_notify, peer);
698 GNUNET_break (NULL != peer->th);
702 while ((NULL != (pending = peer->head)) &&
703 (size - off >= (msize = ntohs (pending->msg->size))))
705 GNUNET_STATISTICS_update (GDS_stats,
707 ("# Bytes transmitted to other peers"), msize,
709 memcpy (&cbuf[off], pending->msg, msize);
711 peer->pending_count--;
712 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
713 GNUNET_free (pending);
715 if (peer->head != NULL)
718 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
719 GNUNET_CORE_PRIO_BEST_EFFORT,
720 GNUNET_TIME_absolute_get_remaining
721 (pending->timeout), &peer->id, msize,
722 &core_transmit_notify, peer);
723 GNUNET_break (NULL != peer->th);
730 * Transmit all messages in the friend's message queue.
732 * @param peer message queue to process
735 process_friend_queue (struct FriendInfo *peer)
737 struct P2PPendingMessage *pending;
739 if (NULL == (pending = peer->head))
741 if (NULL != peer->th)
744 GNUNET_STATISTICS_update (GDS_stats,
746 ("# Bytes of bandwidth requested from core"),
747 ntohs (pending->msg->size), GNUNET_NO);
749 /* FIXME: Are we correctly initializing importance and pending. */
751 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
753 GNUNET_TIME_absolute_get_remaining
754 (pending->timeout), &peer->id,
755 ntohs (pending->msg->size),
756 &core_transmit_notify, peer);
757 GNUNET_break (NULL != peer->th);
762 * Setup the trail message and forward it to a friend.
763 * @param source_peer Peer which wants to set up the trail to one of its finger.
764 * @param destination_finger Peer to which we want to set up the trail to.
765 * @param target_friend Current friend to which this message should be forwarded.
766 * @param trail_length Numbers of peers in the trail.
767 * @param trail_peer_list peers this request has traversed so far
768 * @param successor_flag If 1 then we are looking for trail to our successor.
769 * @param predecessor_flag If 1, then we are looking for trail to our predecessor.
770 * @param current_finger_index Finger index in finger peer map
773 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity *source_peer,
774 uint64_t destination_finger,
775 struct FriendInfo *target_friend,
776 unsigned int trail_length,
777 struct GNUNET_PeerIdentity *trail_peer_list,
778 unsigned int successor_flag,
779 unsigned int predecessor_flag,
780 unsigned int current_finger_index)
782 struct P2PPendingMessage *pending;
783 struct PeerTrailSetupMessage *tsm;
784 struct GNUNET_PeerIdentity *peer_list;
787 msize = sizeof (struct PeerTrailSetupMessage) +
788 (trail_length * sizeof (struct GNUNET_PeerIdentity));
790 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
796 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
798 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
802 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
803 pending->importance = 0; /* FIXME */
804 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
805 tsm = (struct PeerTrailSetupMessage *) &pending[1];
806 pending->msg = &tsm->header;
807 tsm->header.size = htons (msize);
808 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
809 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
810 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
811 memcpy (&(tsm->current_destination), &(target_friend->id),
812 sizeof (struct GNUNET_PeerIdentity));
813 tsm->current_destination_type = htonl (FRIEND);
814 tsm->trail_length = htonl (trail_length);
815 tsm->finger_map_index = htonl (current_finger_index);
816 if(1 == successor_flag)
818 tsm->successor_flag = htonl(1);
819 tsm->predecessor_flag = htonl (0);
821 else if (1 == predecessor_flag)
823 tsm->predecessor_flag = htonl(1);
824 tsm->successor_flag = htonl(0);
828 tsm->successor_flag = htonl(0);
829 tsm->predecessor_flag = htonl(0);
832 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
833 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
834 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
835 target_friend->pending_count++;
836 process_friend_queue (target_friend);
842 * Handle a tail setup result message.
843 * @param destination_peer Peer which will get the trail to one of its finger.
844 * @param source_finger Peer to which the trail has been setup to.
845 * @param target_friend Friend to which this message should be forwarded.
846 * @param trail_length Numbers of peers in the trail.
847 * @param trail_peer_list Peers which are part of the trail from source to destination.
848 * @param current_trail_index Index in trail_peer_list.
849 * @param successor_flag If 1, then this is the trail to our successor.
850 * @param predecessor_flag If 1, then this is the trail to our predecessor.
851 * @param finger_map_index Finger index in finger peer map
854 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity *destination_peer,
855 struct GNUNET_PeerIdentity *source_finger,
856 struct FriendInfo *target_friend,
857 unsigned int trail_length,
858 struct GNUNET_PeerIdentity *trail_peer_list,
859 unsigned int current_trail_index,
860 unsigned int successor_flag,
861 unsigned int predecessor_flag,
862 unsigned int finger_map_index)
864 struct P2PPendingMessage *pending;
865 struct PeerTrailSetupResultMessage *tsrm;
866 struct GNUNET_PeerIdentity *peer_list;
869 msize = sizeof (struct PeerTrailSetupResultMessage) +
870 (trail_length * sizeof (struct GNUNET_PeerIdentity));
872 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
878 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
880 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
884 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
885 pending->importance = 0;
886 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
887 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
888 pending->msg = &tsrm->header;
889 tsrm->header.size = htons (msize);
890 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
891 memcpy (&(tsrm->current_destination), &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
892 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
893 memcpy (&(tsrm->finger), source_finger, sizeof (struct GNUNET_PeerIdentity));
894 tsrm->trail_length = htonl (trail_length);
895 tsrm->current_index = htonl (current_trail_index);
896 tsrm->successor_flag = htonl (successor_flag);
897 tsrm->predecessor_flag = htonl (predecessor_flag);
898 tsrm->finger_map_index = htonl (finger_map_index);
899 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
900 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
902 /* Send the message to chosen friend. */
903 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
904 target_friend->pending_count++;
905 process_friend_queue (target_friend);
910 * Construct a PeerVerifySuccessor message and send it to friend.
911 * @param source_peer Peer which wants to verify its successor
912 * @param successor Peer which is our current successor
913 * @param target_friend Friend to which this message should be forwarded.
914 * @param trail_peer_list Peer which are part of trail from source to destination
915 * @param trail_length Number of peers in the trail list.
916 * @param current_trail_index Index in the trial list at which receiving peer should
917 * get the next element.
919 void GDS_NEIGHBOURS_send_verify_successor(struct GNUNET_PeerIdentity *source_peer,
920 struct GNUNET_PeerIdentity *successor,
921 struct FriendInfo *target_friend,
922 struct GNUNET_PeerIdentity *trail_peer_list,
923 unsigned int trail_length,
924 unsigned int current_trail_index)
926 struct PeerVerifySuccessorMessage *vsm;
927 struct P2PPendingMessage *pending;
928 struct GNUNET_PeerIdentity *peer_list;
931 msize = sizeof (struct PeerVerifySuccessorMessage) +
932 (trail_length * sizeof (struct GNUNET_PeerIdentity));
934 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
940 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
942 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
946 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
947 pending->importance = 0; /* FIXME */
948 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
949 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
950 pending->msg = &vsm->header;
951 vsm->header.size = htons (msize);
952 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
953 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
954 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
955 vsm->trail_length = htonl (trail_length);
956 vsm->current_trail_index = htonl (current_trail_index);
957 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
958 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
960 /* Send the message to chosen friend. */
961 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
962 target_friend->pending_count++;
963 process_friend_queue (target_friend);
969 * Construct a PeerVerifySuccessorResult message and send it to friend.
970 * @param destination_peer Peer which sent verify successor message
971 * @param source_successor Peer to which verify successor message was sent.
972 * @param my_predecessor source_successor predecessor.
973 * @param target_friend Friend to which this message should be forwarded.
974 * @param trail_peer_list Peer which are part of trail from source to destination
975 * @param trail_length Number of peers in the trail list.
976 * @param current_trail_index Index in the trial list at which receiving peer should
977 * get the next element.
979 void GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity *destination_peer,
980 struct GNUNET_PeerIdentity *source_successor,
981 struct GNUNET_PeerIdentity *my_predecessor,
982 struct FriendInfo *target_friend,
983 struct GNUNET_PeerIdentity *trail_peer_list,
984 unsigned int trail_length,
985 unsigned int current_trail_index)
987 struct PeerVerifySuccessorResultMessage *vsmr;
988 struct P2PPendingMessage *pending;
989 struct GNUNET_PeerIdentity *peer_list;
992 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
993 (trail_length * sizeof(struct GNUNET_PeerIdentity));
995 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1002 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1004 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1008 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1009 pending->importance = 0; /* FIXME */
1010 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1011 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1012 pending->msg = &vsmr->header;
1013 vsmr->header.size = htons (msize);
1014 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1015 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1016 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1017 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1018 vsmr->trail_length = htonl (trail_length);
1019 vsmr->current_index = htonl (current_trail_index);
1021 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1022 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1024 /* Send the message to chosen friend. */
1025 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1026 target_friend->pending_count++;
1027 process_friend_queue (target_friend);
1032 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1033 * @param source_peer Peer which is sending notify message to its new successor.
1034 * @param destination_peer Peer which is the new destination.
1035 * @param target_friend Next friend to pass this message to.
1036 * @param peer_list List of peers in the trail to reach to destination_peer.
1037 * @param current_trail_index Index of peer_list for next target friend position.
1038 * @param trail_length Total number of peers in peer list
1041 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity *source_peer,
1042 struct GNUNET_PeerIdentity *destination_peer,
1043 struct FriendInfo *target_friend,
1044 struct GNUNET_PeerIdentity *trail_peer_list,
1045 unsigned int trail_length,
1046 unsigned int current_trail_index)
1048 struct PeerNotifyNewSuccessorMessage *nsm;
1049 struct P2PPendingMessage *pending;
1050 struct GNUNET_PeerIdentity *peer_list;
1053 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1054 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1056 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1062 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1064 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1068 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1069 pending->importance = 0; /* FIXME */
1070 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1071 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1072 pending->msg = &nsm->header;
1073 nsm->header.size = htons (msize);
1074 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1075 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1076 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1077 nsm->trail_length = htonl (trail_length);
1078 nsm->current_index = htonl (current_trail_index);
1080 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1081 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1083 /* Send the message to chosen friend. */
1084 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1085 target_friend->pending_count++;
1086 process_friend_queue (target_friend);
1090 /**FIXME: Old implementation just to remove error
1091 * TODO: Modify this function to handle our get request.
1092 * Perform a GET operation. Forwards the given request to other
1093 * peers. Does not lookup the key locally. May do nothing if this is
1094 * the only peer in the network (or if we are the closest peer in the
1097 * @param type type of the block
1098 * @param options routing options
1099 * @param desired_replication_level desired replication count
1100 * @param hop_count how many hops did this request traverse so far?
1101 * @param key key for the content
1102 * @param xquery extended query
1103 * @param xquery_size number of bytes in @a xquery
1104 * @param reply_bf bloomfilter to filter duplicates
1105 * @param reply_bf_mutator mutator for @a reply_bf
1106 * @param peer_bf filter for peers not to select (again)
1109 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1110 enum GNUNET_DHT_RouteOption options,
1111 uint32_t desired_replication_level,
1112 uint32_t hop_count, const struct GNUNET_HashCode * key,
1113 const void *xquery, size_t xquery_size,
1114 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
1115 uint32_t reply_bf_mutator,
1116 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1120 1. take the key, get the 64 bit value of the key.
1121 2. call find_successor to get the successor of the key.
1122 3. successor can be either a friend or finger.
1123 4. update the field in get message to reflect if its a friend or finger table
1124 5. add the put message to pending message and send it.
1129 /**FIXME: Old implementation just to remove error.
1130 * TODO: Modify this function to handle our put request.
1131 * Perform a PUT operation. Forwards the given request to other
1132 * peers. Does not store the data locally. Does not give the
1133 * data to local clients. May do nothing if this is the only
1134 * peer in the network (or if we are the closest peer in the
1137 * @param type type of the block
1138 * @param options routing options
1139 * @param desired_replication_level desired replication count
1140 * @param expiration_time when does the content expire
1141 * @param hop_count how many hops has this message traversed so far
1142 * @param bf Bloom filter of peers this PUT has already traversed
1143 * @param key key for the content
1144 * @param put_path_length number of entries in @a put_path
1145 * @param put_path peers this request has traversed so far (if tracked)
1146 * @param data payload to store
1147 * @param data_size number of bytes in @a data
1150 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1151 enum GNUNET_DHT_RouteOption options,
1152 uint32_t desired_replication_level,
1153 struct GNUNET_TIME_Absolute expiration_time,
1155 struct GNUNET_CONTAINER_BloomFilter *bf,
1156 const struct GNUNET_HashCode *key,
1157 unsigned int put_path_length,
1158 struct GNUNET_PeerIdentity *put_path,
1159 const void *data, size_t data_size)
1163 1. take the key, get the 64 bit value of the key.
1164 2. call find_successor to get the successor of the key.
1165 3. successor can be either a friend or finger.
1166 4. update the field in put message to reflect if its a friend or finger table
1167 5. add the put message to pending message and send it.
1169 /* SUPU: Call is made to this function from client. It does not seem to be
1170 waiting for a confirmation So, once we got the request, we use the key and
1171 try to find the closest successor, but in this case when we reach to the
1172 closest successor in handle_dht_p2p_put, then just do datacache_put. As the calling
1173 function does not need any confirmation, we don't need the result back. */
1178 * Randomly choose one of your friends from the friends_peer map
1181 static struct FriendInfo *
1182 select_random_friend()
1184 unsigned int current_size;
1185 unsigned int *index;
1187 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1188 struct GNUNET_PeerIdentity key_ret;
1189 struct FriendInfo *friend;
1191 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1193 /* Element stored at this index in friend_peermap should be selected friend. */
1194 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1196 /* Create an iterator for friend_peermap. */
1197 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1199 /* Set the position of iterator to index. */
1202 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1210 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1220 * Compute finger_identity to which we want to setup the trail
1221 * @return finger_identity
1224 compute_finger_identity()
1227 uint64_t *finger_identity64;
1229 my_id64 = GNUNET_malloc (sizeof (uint64_t));
1230 finger_identity64 = GNUNET_malloc (sizeof (uint64_t));
1232 memcpy (my_id64, &(my_identity.public_key.q_y), sizeof (uint64_t));
1233 *finger_identity64 = fmod ((*my_id64 + pow (2,current_finger_index)),( (pow (2,MAX_FINGERS))));
1235 return finger_identity64;
1240 * Compute immediate predecessor identity in the network.
1241 * @return peer identity of immediate predecessor.
1244 compute_predecessor_identity()
1247 uint64_t *predecessor;
1249 my_id = GNUNET_malloc (sizeof (uint64_t));
1250 predecessor = GNUNET_malloc (sizeof (uint64_t));
1252 memcpy (my_id, &(my_identity.public_key.q_y), sizeof (uint64_t));
1253 *predecessor = fmod ((*my_id -1), (pow (2,MAX_FINGERS)));
1260 * SUPU: You should pass the trail index from where next peer should read. read
1261 * position should be set and after you read you should update the read position
1262 * for next peer in the trail list.
1263 * Periodically ping your successor to ask its current predecessor
1265 * @param cls closure for this task
1266 * @param tc the context under which the task is running
1269 send_verify_successor_message (void *cls,
1270 const struct GNUNET_SCHEDULER_TaskContext *tc )
1272 struct GNUNET_TIME_Relative next_send_time;
1273 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1274 struct GNUNET_PeerIdentity key_ret;
1275 struct FriendInfo *target_friend;
1276 struct GNUNET_PeerIdentity *next_hop;
1277 struct GNUNET_PeerIdentity *peer_list;
1278 unsigned int finger_trail_current_index;
1279 struct FingerInfo *finger;
1280 unsigned int finger_index;
1283 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1284 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1286 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1287 (const void **)&finger))
1289 if (1 == finger->successor)
1293 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1295 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->trail_length);
1297 /* Iterate over your linked list of trail and copy it into peer_list. */
1298 struct TrailPeerList *iterate;
1299 iterate = finger->head;
1301 while ( i < (finger->trail_length))
1303 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1304 iterate = iterate->next;
1308 /* element stored at location 0 is my own identity. element stored at location 1
1310 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1311 memcpy (next_hop, &peer_list[1], sizeof (struct GNUNET_PeerIdentity));
1312 /* Find the friend corresponding to this next hop. */
1313 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1314 finger_trail_current_index = 2;
1316 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1317 &(finger->finger_identity),
1320 finger->trail_length,
1321 finger_trail_current_index);
1324 /* FIXME: Use a random value so that this message is send not at the same
1325 interval as send_find_finger_trail_message. */
1326 next_send_time.rel_value_us =
1327 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1328 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1329 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1330 (current_finger_index + 50));
1333 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1339 * Task to send a find finger trail message. We attempt to find trail
1340 * to our fingers, successor and predecessor in the network.
1342 * @param cls closure for this task
1343 * @param tc the context under which the task is running
1346 send_find_finger_trail_message (void *cls,
1347 const struct GNUNET_SCHEDULER_TaskContext *tc)
1349 struct FriendInfo *target_friend;
1350 struct GNUNET_TIME_Relative next_send_time;
1351 struct GNUNET_PeerIdentity *peer_list;
1352 unsigned int successor_flag;
1353 unsigned int predecessor_flag;
1354 uint64_t *finger_identity;
1355 unsigned int finger_index;
1357 /* Initialize flag values */
1358 predecessor_flag = 0;
1361 if (1 == current_finger_index)
1363 /* We have started the process to find the successor. We should search
1364 for our predecessor. */
1365 finger_identity = compute_predecessor_identity();
1366 predecessor_flag = 1;
1371 finger_identity = compute_finger_identity();
1374 if(0 == current_finger_index)
1376 /* We are searching for our successor in the network. */
1381 finger_index = current_finger_index;
1382 current_finger_index = ( current_finger_index + 1) % MAX_FINGERS;
1384 target_friend = select_random_friend();
1386 /* We found a friend.*/
1387 if(NULL != target_friend)
1389 /* Add yourself and selected friend in the trail list. */
1390 unsigned int trail_length = 2;
1391 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
1392 memcpy (&peer_list[0], &(my_identity), sizeof (struct GNUNET_PeerIdentity));
1393 memcpy (&peer_list[1], &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1395 /* TODO send trail setup */
1396 GDS_NEIGHBOURS_send_trail_setup (&my_identity, *finger_identity,
1397 target_friend, trail_length, peer_list,
1398 successor_flag, predecessor_flag,
1402 /* FIXME: Should we be using current_finger_index to generate random interval.*/
1403 next_send_time.rel_value_us =
1404 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1405 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1406 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1407 (current_finger_index + 10));
1409 find_finger_trail_task =
1410 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1416 * Method called whenever a peer connects.
1418 * @param cls closure
1419 * @param peer_identity peer identity this notification is about
1422 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
1424 struct FriendInfo *friend;
1426 /* Check for connect to self message */
1427 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
1430 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
1432 /* If peer already exists in our friend_peermap, then exit. */
1433 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
1439 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
1443 friend = GNUNET_new (struct FriendInfo);
1444 friend->id = *peer_identity;
1446 GNUNET_assert (GNUNET_OK ==
1447 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
1448 peer_identity, friend,
1449 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1451 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
1452 if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
1453 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
1458 * Method called whenever a peer disconnects.
1460 * @param cls closure
1461 * @param peer peer identity this notification is about
1464 handle_core_disconnect (void *cls,
1465 const struct GNUNET_PeerIdentity *peer)
1467 struct FriendInfo *remove_friend;
1469 /* Check for self message. */
1470 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1473 /* Search for peer to remove in your friend_peermap. */
1475 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
1477 if (NULL == remove_friend)
1483 /* Remove the friend from friend_peermap. */
1484 GNUNET_assert (GNUNET_YES ==
1485 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
1489 /* If the peer is removed then all the trail which goes through this
1490 peer also becomes invalid. */
1491 /* FIXME: Iterate over finger peermap, get the trail index and find all the
1492 finger whose trail's first peer was this peer. and remove them from finger
1493 peermap. Assumption that in send_find_finger_trail we will eventually reach
1494 to this finger and we will setup up the new trail.
1495 So, we need a threshold on number of trail thats can go through a node
1496 so that if that nodes go away then also our system is up and runnning.
1497 Where can we specify that threshold.*/
1502 * To be called on core init/fail.
1504 * @param cls service closure
1505 * @param identity the public identity of this peer
1508 core_init (void *cls,
1509 const struct GNUNET_PeerIdentity *identity)
1511 my_identity = *identity;
1516 * Core handler for p2p put requests.
1518 * @param cls closure
1519 * @param peer sender of the request
1520 * @param message message
1521 * @param peer peer identity this notification is about
1522 * @return #GNUNET_OK to keep the connection open,
1523 * #GNUNET_SYSERR to close it (signal serious error)
1526 handle_dht_p2p_put (void *cls,
1527 const struct GNUNET_PeerIdentity *peer,
1528 const struct GNUNET_MessageHeader *message)
1531 1. Check if destination is friend or finger.
1532 2. If finger then get the next hop from routing table and
1533 * call GDS_NEGIHBOURS_handle_get.
1534 3. If friend then call find_successor to get the next hop and again
1535 * call GDS_NEIGHBOURS_handle_get to send to chosen hop.
1536 4. If you are the destination then do datacache_store.
1543 * Core handler for p2p get requests.
1545 * @param cls closure
1546 * @param peer sender of the request
1547 * @param message message
1548 * @return #GNUNET_OK to keep the connection open,
1549 * #GNUNET_SYSERR to close it (signal serious error)
1552 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1553 const struct GNUNET_MessageHeader *message)
1556 1. Check if destination is friend or finger.
1557 2. If finger then get the next hop from routing table and
1558 * call GDS_NEGIHBOURS_handle_get.
1559 3. If friend then call find_successor to get the next hop and again
1560 * call GDS_NEIGHBOURS_handle_get to send to chosen hop.
1561 4. If you are the destination then send the data back to source peer
1562 * Assuming we have trail setup we can
1563 * either store the whole trail or again do the search process..
1569 * FIXME: For redundant routing, we may start looking for different
1570 * paths to reach to same finger. So, in send_find_finger, we are starting
1571 * the search for trail to a finger, even if we already have found trail to
1572 * reach to it. There are several reasons for doing so
1573 * 1. We may reach to a closer successor than we have at the moment. So, we
1574 * should keep looking for the successor.
1575 * 2. We may reach to the same successor but through a shorter path.
1576 * 3. As I don't know how keys are distributed and how put/get will react
1577 * because of this, I have to think further before implementing it.
1578 * Add an entry in finger table.
1579 * @param finger Finger to be added to finger table
1580 * @param peer_list peers this request has traversed so far
1581 * @param trail_length Numbers of peers in the trail.
1584 void finger_table_add (struct GNUNET_PeerIdentity *finger,
1585 struct GNUNET_PeerIdentity *peer_list,
1586 unsigned int trail_length,
1587 unsigned int successor_flag,
1588 unsigned int predecessor_flag,
1589 unsigned int finger_map_index)
1591 struct FingerInfo *new_finger_entry;
1593 /** SUPU: when we add an entry then we should look if
1594 * we already have an entry for that index. If yes, then
1595 * 1) if both the finger identity are same, and same first friend, then choose
1596 * the one with shorter trail length.
1597 * 2) if the finger identity is different, then keep the one which is closest.*/
1599 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (finger_peermap, finger))
1603 /* Optimization. For the moment we just ignore and do nothing.*/
1604 /* We already have an entry for this finger. */
1605 struct GNUNET_PeerIdentity *first_friend;
1606 struct FingerInfo *exisiting_finger_entry;
1608 struct TrailPeerList *iterator;
1609 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
1610 exisiting_finger_entry = GNUNET_CONTAINER_multipeermap_get(finger_peermap, finger);
1611 iterator = exisiting_finger_entry->head;
1612 memcpy (first_friend, &(iterator->peer), sizeof(struct GNUNET_PeerIdentity));
1614 if(0 == GNUNET_CRYPTO_cmp_peer_identity(first_friend, finger))
1621 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
1622 memcpy (&(new_finger_entry->finger_identity), finger, sizeof (struct GNUNET_PeerIdentity));
1625 /* Insert elements of peer_list into TrailPeerList. */
1627 while (i < trail_length)
1629 struct TrailPeerList *element;
1630 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1631 element->next = NULL;
1632 element->prev = NULL;
1634 memcpy (&(element->peer), &peer_list[i], sizeof(struct GNUNET_PeerIdentity));
1635 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
1640 new_finger_entry->successor = successor_flag;
1641 new_finger_entry->predecessor = predecessor_flag;
1642 new_finger_entry->finger_map_index = finger_map_index;
1643 new_finger_entry->trail_length = trail_length;
1646 GNUNET_assert (GNUNET_OK ==
1647 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1648 &(new_finger_entry->finger_identity),
1650 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1652 /*FIXME: Is it really a good time to call verify successor message. */
1653 if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap))
1655 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1661 * FIXME: Also copy the trail list in reverse direction that is the path to
1662 * reach to your predecessor.
1663 * Replace your predecessor with new predecessor.
1664 * @param predecessor My new predecessor
1665 * @param peer_list Trail list to reach to my new predecessor
1666 * @param trail_length Number of peers in the trail.
1669 update_predecessor (struct GNUNET_PeerIdentity *predecessor,
1670 struct GNUNET_PeerIdentity *peer_list,
1671 unsigned int trail_length)
1673 struct GNUNET_PeerIdentity *trail_peer_list;
1674 struct FingerInfo *new_finger_entry;
1675 struct FingerInfo *finger;
1676 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1677 struct GNUNET_PeerIdentity key_ret;
1683 /* Check if you already have a predecessor. Then remove it and add the new
1685 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1686 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1688 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1689 (const void **)&finger))
1691 if (1 == finger->predecessor)
1698 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1699 /* check if you come out of the loop or because of the conditoin*/
1702 goto add_new_predecessor;
1706 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains(finger_peermap, &(finger->finger_identity)))
1708 /* compare peer ids of new finger and old finger if they are same don't remove and exit
1709 if different then remove and exit. */
1710 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&(finger->finger_identity), predecessor))
1717 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_remove(finger_peermap, &(finger->finger_identity), finger))
1719 goto add_new_predecessor;
1728 add_new_predecessor:
1729 i = trail_length - 1;
1731 trail_peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
1735 memcpy( &trail_peer_list[j], &peer_list[i], sizeof (struct GNUNET_PeerIdentity));
1739 memcpy (&trail_peer_list[j], &peer_list[i], sizeof(struct GNUNET_PeerIdentity));
1741 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
1742 memcpy (&(new_finger_entry->finger_identity), predecessor, sizeof (struct GNUNET_PeerIdentity));
1743 new_finger_entry->finger_map_index = 1;
1744 new_finger_entry->predecessor = 1;
1745 new_finger_entry->successor = 0;
1746 new_finger_entry->trail_length = trail_length;
1749 while (i < trail_length)
1751 struct TrailPeerList *element;
1752 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1753 element->next = NULL;
1754 element->prev = NULL;
1756 memcpy (&(element->peer), &trail_peer_list[i], sizeof(struct GNUNET_PeerIdentity));
1757 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
1764 * Compare two peer identities.
1765 * @param p1 Peer identity
1766 * @param p2 Peer identity
1767 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
1770 compare_peer_id (const void *p1, const void *p2)
1772 struct Sorting_List *p11;
1773 struct Sorting_List *p22;
1775 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
1776 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
1777 p11 = (struct Sorting_List *)p1;
1778 p22 = (struct Sorting_List *)p2;
1779 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
1780 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
1786 * Returns the previous element of value in all_known_peers.
1787 * @param all_known_peers list of all the peers
1788 * @param value value we have to search in the all_known_peers.
1791 static struct Sorting_List *
1792 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
1801 middle = (first + last)/2;
1803 while(first <= last)
1805 if(all_known_peers[middle].peer_id < value)
1809 else if(all_known_peers[middle].peer_id == value)
1811 if(middle == (size -1))
1813 return &all_known_peers[0];
1817 return &all_known_peers[middle+1];
1825 middle = (first + last)/2;
1832 * Find closest successor for the value.
1833 * @param value Value for which we are looking for successor
1834 * @param current_destination NULL if my_identity is successor else finger/friend
1836 * @param type Next destination type
1837 * @return Peer identity of next destination i.e. successor of value.
1839 static struct GNUNET_PeerIdentity *
1840 find_successor(uint64_t value, struct GNUNET_PeerIdentity *current_destination,
1841 enum current_destination_type *type)
1843 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1844 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1845 struct GNUNET_PeerIdentity key_ret;
1846 struct FriendInfo *friend;
1847 struct FingerInfo *finger;
1848 unsigned int finger_index;
1849 unsigned int friend_index;
1850 struct Sorting_List *successor;
1854 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
1855 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
1856 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
1859 struct Sorting_List all_known_peers[size];
1862 for (k = 0; k < size; k++)
1863 all_known_peers[k].peer_id = 0;
1865 /* Copy your identity at 0th index in all_known_peers. */
1867 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
1868 all_known_peers[j].type = MY_ID;
1869 all_known_peers[j].data = 0;
1873 all_known_peers[j].peer_id = value;
1874 all_known_peers[j].type = VALUE;
1875 all_known_peers[j].data = 0;
1878 /* Iterate over friend peer map and copy all the elements into array. */
1879 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1880 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1882 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1884 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
1885 all_known_peers[j].type = FRIEND;
1886 all_known_peers[j].data = friend;
1891 /* Iterate over finger map and copy all the entries into all_known_peers array. */
1892 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1893 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1895 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1897 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
1898 all_known_peers[j].type = FINGER;
1899 all_known_peers[j].data = finger;
1904 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1905 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
1907 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
1909 /* search value in all_known_peers array. */
1910 successor = find_closest_successor (all_known_peers, value, size);
1912 if (successor->type == MY_ID)
1917 else if (successor->type == FRIEND)
1920 struct FriendInfo *target_friend;
1921 target_friend = (struct FriendInfo *)successor->data;
1922 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1923 return current_destination;
1925 else if (successor->type == FINGER)
1928 struct GNUNET_PeerIdentity *next_hop;
1929 struct FingerInfo *finger;
1930 struct TrailPeerList *iterator;
1931 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
1932 finger = successor->data;
1933 iterator = finger->head->next;
1934 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1935 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
1936 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1948 * SUPU: The first element in the trail setup message is your identity.
1949 * in this function you should increment the trail length.
1950 * Handle a PeerTrailSetupMessage.
1951 * @param cls closure
1952 * @param message message
1953 * @param peer peer identity this notification is about
1954 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1957 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1958 const struct GNUNET_MessageHeader *message)
1960 struct PeerTrailSetupMessage *trail_setup;
1961 struct GNUNET_PeerIdentity *next_hop;
1962 struct FriendInfo *target_friend;
1964 uint32_t trail_length;
1965 enum current_destination_type peer_type;
1966 struct GNUNET_PeerIdentity *trail_peer_list;
1967 uint32_t current_trail_index;
1968 unsigned int finger_map_index;
1969 struct GNUNET_PeerIdentity *next_peer;
1970 unsigned int successor_flag;
1971 unsigned int predecessor_flag;
1973 struct GNUNET_PeerIdentity *current_destination;
1974 current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1976 /* parse and validate message. */
1977 msize = ntohs (message->size);
1978 if (msize < sizeof (struct PeerTrailSetupMessage))
1980 GNUNET_break_op (0);
1985 trail_setup = (struct PeerTrailSetupMessage *) message;
1986 trail_length = ntohl (trail_setup->trail_length);
1987 peer_type = ntohl (trail_setup->current_destination_type);
1988 finger_map_index = ntohl (trail_setup->finger_map_index);
1989 successor_flag = ntohl (trail_setup->successor_flag);
1990 predecessor_flag = ntohl (trail_setup->predecessor_flag);
1991 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_setup[1];
1992 value = trail_setup->destination_finger;
1995 sizeof (struct PeerTrailSetupMessage) +
1996 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1998 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2000 GNUNET_break_op (0);
2004 GNUNET_STATISTICS_update (GDS_stats,
2005 gettext_noop ("# TRAIL SETUP requests received"), 1,
2007 GNUNET_STATISTICS_update (GDS_stats,
2008 gettext_noop ("# TRAIL SETUP bytes received"), msize,
2011 if (peer_type == FRIEND)
2013 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
2016 next_hop = find_successor (value,
2017 current_destination,
2021 return GNUNET_SYSERR;
2023 else if (peer_type == FINGER)
2025 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
2028 next_hop = GDS_ROUTING_search (&(trail_setup->source_peer),
2029 &(trail_setup->current_destination));
2032 /* This is an optimization. Uncomment when basic code is running first. */
2033 /* I am part of trail.*/
2034 struct GNUNET_PeerIdentity *next_peer_routing_table;
2035 next_peer_routing_table = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2036 next_peer_routing_table = GDS_ROUTING_search (&(trail_setup->source_peer),
2037 &(trail_setup->current_destination));
2039 struct GNUNET_PeerIdentity *next_peer_find_successor;
2040 next_peer_find_successor = find_successor (&(trail_setup->destination_finger),
2041 &(trail_setup->current_destination),
2044 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2045 next_hop = find_closest_destination (next_peer_routing_table,
2046 next_peer_find_successor,
2047 &(trail_setup->destination_finger) );
2052 /* I am the current_destination finger */
2053 next_hop = find_successor (value,
2054 current_destination, &(peer_type));
2058 /* If you are the next hop, then you are the final destination */
2059 if (peer_type == MY_ID)
2062 1. You were the destination of this message which means you were already added
2063 in the peer list by previous calling function.
2064 2. current_trail_index should point to the trail element at which the peer
2065 which receives this message should look for the next peer to forward the packet
2067 current_trail_index = trail_length - 2;
2068 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2069 memcpy (next_peer, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2070 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
2071 GNUNET_free (next_peer);
2073 if(current_trail_index != 0)
2074 current_trail_index = current_trail_index - 1;
2076 update_predecessor (&(trail_setup->source_peer), trail_peer_list, trail_length );
2077 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_setup->source_peer),
2079 target_friend, trail_length,
2080 trail_peer_list, current_trail_index,
2088 /* Add next hop to list of peers. */
2089 struct GNUNET_PeerIdentity *peer_list;
2090 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1));
2091 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2092 memcpy (&peer_list[trail_length], next_hop, sizeof (struct GNUNET_PeerIdentity));
2095 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2097 if(peer_type == FINGER)
2099 GDS_ROUTING_add (&(trail_setup->source_peer),
2100 &(trail_setup->current_destination),
2104 GDS_NEIGHBOURS_send_trail_setup (&(trail_setup->source_peer),
2105 trail_setup->destination_finger,
2107 trail_setup->trail_length,
2108 peer_list,trail_setup->successor_flag,
2109 trail_setup->predecessor_flag,
2117 * Core handle for p2p trail construction result messages.
2118 * @param cls closure
2119 * @param message message
2120 * @param peer peer identity this notification is about
2121 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2124 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2125 const struct GNUNET_MessageHeader *message)
2127 struct PeerTrailSetupResultMessage *trail_result;
2129 unsigned int trail_length;
2130 struct GNUNET_PeerIdentity *trail_peer_list;
2131 unsigned int current_trail_index;
2132 struct GNUNET_PeerIdentity *next_peer;
2133 struct FriendInfo *target_friend;
2134 unsigned int finger_map_index;
2135 unsigned int successor_flag;
2136 unsigned int predecessor_flag;
2138 msize = ntohs (message->size);
2139 if (msize < sizeof (struct PeerTrailSetupMessage))
2141 GNUNET_break_op (0);
2145 trail_result = (struct PeerTrailSetupResultMessage *) message;
2146 trail_length = ntohl (trail_result->trail_length);
2149 sizeof (struct PeerTrailSetupResultMessage) +
2150 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2152 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2154 GNUNET_break_op (0);
2158 current_trail_index = ntohl (trail_result->current_index);
2159 successor_flag = ntohl (trail_result->successor_flag);
2160 predecessor_flag = ntohl (trail_result->predecessor_flag);
2161 finger_map_index = ntohl (trail_result->finger_map_index);
2163 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
2165 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->current_destination),
2168 if ( 0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2172 /* SUPU: Here I have removed myself from the trail before storing it in
2173 th finger table - to save space, but in case of verify successor result
2174 the result trail does not contain me, and I will never get the message back.
2175 So, keeping myself in the trail list. Think of better solution.*/
2176 struct GNUNET_PeerIdentity *finger_trail;
2177 finger_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - 1));
2179 /* Copy the whole trail_peer_list except the first element into trail */
2181 i = trail_length - 1;
2184 memcpy (&finger_trail[i], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity));
2187 trail_length = trail_length -1 ; SUPU: As you removed yourself from the trail.*/
2190 finger_table_add (&(trail_result->finger), trail_peer_list, trail_length,
2191 successor_flag, predecessor_flag,
2198 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2199 memcpy (next_peer, &(trail_peer_list[current_trail_index]),
2200 sizeof (struct GNUNET_PeerIdentity));
2201 /* SUPU: here current trail index will always be greater than 0.
2202 so no need for this check here. trail index = 0, contains the final
2203 destination, and if we are in this loop we have not yet reached the
2204 final destination. */
2205 current_trail_index = current_trail_index - 1;
2207 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
2208 GNUNET_free (next_peer);
2210 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
2211 &(trail_result->finger),
2212 target_friend, trail_length,
2213 trail_peer_list,current_trail_index,
2214 trail_result->successor_flag,
2215 trail_result->predecessor_flag,
2221 return GNUNET_SYSERR;
2226 * SUPU: In this function you don't do anything with trail length
2227 * You increment the current trail index so that you find the correct
2228 * peer to send the packet forward.
2229 * Core handle for p2p verify successor messages.
2230 * @param cls closure
2231 * @param message message
2232 * @param peer peer identity this notification is about
2233 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2236 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2237 const struct GNUNET_MessageHeader *message)
2239 struct PeerVerifySuccessorMessage *vsm;
2241 unsigned int trail_length;
2242 struct GNUNET_PeerIdentity *trail_peer_list;
2243 unsigned int current_trail_index;
2244 struct FriendInfo *target_friend;
2245 struct GNUNET_PeerIdentity *next_hop;
2247 msize = ntohs (message->size);
2248 if (msize < sizeof (struct PeerVerifySuccessorMessage))
2250 GNUNET_break_op (0);
2254 vsm = (struct PeerVerifySuccessorMessage *) message;
2255 trail_length = ntohl (vsm->trail_length);
2258 sizeof (struct PeerVerifySuccessorMessage) +
2259 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2261 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2263 GNUNET_break_op (0);
2267 current_trail_index = ntohl (vsm->current_trail_index);
2268 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
2270 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2271 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),
2274 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2275 struct GNUNET_PeerIdentity key_ret;
2276 unsigned int finger_index;
2277 struct FingerInfo *my_predecessor;
2278 struct GNUNET_PeerIdentity *destination_peer;
2280 /* Iterate over finger peer map and extract your predecessor. */
2281 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2282 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2284 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
2285 (finger_iter,&key_ret,(const void **)&my_predecessor))
2287 if(1 == my_predecessor->predecessor)
2291 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2293 destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2294 memcpy (destination_peer, &(vsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
2295 current_trail_index = trail_length - 2;
2296 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2297 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2298 GNUNET_free (next_hop);
2300 if (current_trail_index != 0)
2301 current_trail_index = current_trail_index - 1;
2304 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->source_peer),
2305 &(my_predecessor->finger_identity))))
2307 struct GNUNET_PeerIdentity *new_successor_trail;
2308 unsigned int new_trail_length;
2311 new_trail_length = trail_length + my_predecessor->trail_length - 1;
2312 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
2313 * new_trail_length);
2315 /* Copy the trail from source peer to me. */
2316 memcpy (new_successor_trail, trail_peer_list,
2317 (trail_length) * sizeof (struct GNUNET_PeerIdentity));
2319 /* Copy the trail from me to my predecessor excluding me. */
2320 struct TrailPeerList *iterator;
2321 iterator = my_predecessor->head->next;
2323 while (i < new_trail_length)
2325 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2326 iterator = iterator->next;
2330 GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2332 &(my_predecessor->finger_identity),
2334 new_successor_trail,
2336 current_trail_index);
2339 GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2341 &(my_predecessor->finger_identity),
2345 current_trail_index);
2350 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2351 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2352 GNUNET_free (next_hop);
2354 current_trail_index = current_trail_index + 1;
2356 GDS_NEIGHBOURS_send_verify_successor(&(vsm->source_peer),
2361 current_trail_index);
2368 * Update successor field in finger table with new successor.
2369 * @param successor New successor which is the predecessor my old successor.
2370 * @param peer_list Trail list to reach to new successor = trail to reach old
2371 * successor + trail to reach to new successor from that old successor.
2372 * @param trail_length Number of peers to reach to the new successor.
2375 update_successor (struct GNUNET_PeerIdentity *successor_identity,
2376 struct GNUNET_PeerIdentity *peer_list,
2377 unsigned int trail_length)
2379 struct FingerInfo *new_finger_entry;
2381 struct FingerInfo *finger;
2382 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2383 struct GNUNET_PeerIdentity key_ret;
2387 /* Check if you already have a predecessor. Then remove it and add the new
2389 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2390 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2392 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
2393 (const void **)&finger))
2395 if (1 == finger->successor)
2402 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2403 /* check if you come out of the loop or because of the conditoin*/
2406 goto add_new_successor;
2410 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains(finger_peermap, &(finger->finger_identity)))
2412 /* compare peer ids of new finger and old finger if they are same don't remove and exit
2413 if different then remove and exit. */
2414 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&(finger->finger_identity), successor_identity))
2421 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_remove(finger_peermap, &(finger->finger_identity), finger))
2423 goto add_new_successor;
2433 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2434 new_finger_entry->predecessor = 0;
2435 new_finger_entry->successor = 1;
2436 new_finger_entry->trail_length = trail_length;
2437 new_finger_entry->finger_map_index = 0;
2438 memcpy (&(new_finger_entry->finger_identity), successor_identity, sizeof (struct GNUNET_PeerIdentity));
2441 while (i < trail_length)
2443 struct TrailPeerList *element;
2444 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2445 element->next = NULL;
2446 element->prev = NULL;
2448 memcpy (&(element->peer), &peer_list[i], sizeof(struct GNUNET_PeerIdentity));
2449 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
2456 * Core handle for p2p notify new successor messages.
2457 * @param cls closure
2458 * @param message message
2459 * @param peer peer identity this notification is about
2460 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2463 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2464 const struct GNUNET_MessageHeader *message)
2466 struct PeerNotifyNewSuccessorMessage *nsm;
2468 unsigned int trail_length;
2469 struct GNUNET_PeerIdentity *trail_peer_list;
2470 unsigned int current_trail_index;
2472 msize = ntohs (message->size);
2473 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
2475 GNUNET_break_op (0);
2479 nsm = (struct PeerNotifyNewSuccessorMessage *) message;
2480 trail_length = ntohl (nsm->trail_length);
2483 sizeof (struct PeerNotifyNewSuccessorMessage) +
2484 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2486 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2488 GNUNET_break_op (0);
2492 current_trail_index = ntohl (nsm->current_index);
2493 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
2495 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer),
2498 update_predecessor (&(nsm->source_peer),
2505 struct FriendInfo *target_friend;
2506 target_friend = GNUNET_malloc (sizeof (struct FriendInfo));
2507 struct GNUNET_PeerIdentity *next_hop;
2508 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2509 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2512 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2513 GNUNET_free (next_hop);
2514 current_trail_index = current_trail_index + 1;
2516 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
2517 &(nsm->destination_peer),
2518 target_friend, trail_peer_list, trail_length,
2519 current_trail_index);
2526 * Core handle for p2p verify successor result messages.
2527 * @param cls closure
2528 * @param message message
2529 * @param peer peer identity this notification is about
2530 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2533 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2534 const struct GNUNET_MessageHeader *message)
2536 struct PeerVerifySuccessorResultMessage *vsrm;
2538 struct FriendInfo *target_friend;
2539 unsigned int current_trail_index;
2540 struct GNUNET_PeerIdentity *trail_peer_list;
2541 struct GNUNET_PeerIdentity *next_hop;
2542 unsigned int trail_length;
2544 msize = ntohs (message->size);
2545 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
2547 GNUNET_break_op (0);
2551 /* Again in the function you have the whole trail to reach to the destination. */
2552 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
2553 current_trail_index = ntohl (vsrm->current_index);
2554 trail_length = ntohl (vsrm->trail_length);
2556 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
2559 sizeof (struct PeerVerifySuccessorResultMessage) +
2560 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2562 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2564 GNUNET_break_op (0);
2568 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer),
2571 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor),
2574 update_successor (&(vsrm->my_predecessor), trail_peer_list, trail_length);
2576 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2577 memcpy (next_hop, &trail_peer_list[1], sizeof (struct GNUNET_PeerIdentity));
2578 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2579 current_trail_index = 2;
2580 GNUNET_free (next_hop);
2582 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
2583 target_friend, trail_peer_list,
2584 trail_length, current_trail_index);
2589 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2591 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2592 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2593 GNUNET_free (next_hop);
2594 current_trail_index = current_trail_index - 1;
2596 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
2597 &(vsrm->source_successor),
2598 &(vsrm->my_predecessor),
2602 current_trail_index);
2609 * Initialize neighbours subsystem.
2610 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2613 GDS_NEIGHBOURS_init()
2615 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
2616 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
2617 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
2618 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
2619 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
2620 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
2621 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
2622 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
2627 /*TODO: What is ATS? Why do we need it? */
2628 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
2630 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
2631 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
2632 GNUNET_NO, core_handlers);
2633 if (NULL == core_api)
2634 return GNUNET_SYSERR;
2636 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
2637 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS, GNUNET_NO);
2644 * Shutdown neighbours subsystem.
2647 GDS_NEIGHBOURS_done ()
2649 if (NULL == core_api)
2652 GNUNET_CORE_disconnect (core_api);
2654 GNUNET_ATS_performance_done (atsAPI);
2657 /* FIXME: In case of friends, every time we are disconnected from a friend
2658 we remove it from friend table. So, this assertion works for friend.
2659 But in case of finger_peermap, we never remove any entry from our
2660 finger peermap. So, either when we remove the friend from friend peermap,then
2661 I remove all the finger for which that friend was the first trail and leave
2662 it on send_find_finger_trail to eventually find path to that finger. In that
2663 case may be assertion for finger peermap will also succed. Or else if
2664 peermap are not empty check it and empty it and then destroy because
2665 multipeermpa_destroy does not free individual entries. */
2666 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
2667 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
2668 friend_peermap = NULL;
2670 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
2671 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
2672 finger_peermap = NULL;
2674 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
2676 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
2677 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
2680 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
2682 GNUNET_SCHEDULER_cancel (verify_successor);
2683 verify_successor = GNUNET_SCHEDULER_NO_TASK;
2690 * Get the ID of the local node.
2692 * @return identity of the local node
2694 struct GNUNET_PeerIdentity *
2695 GDS_NEIGHBOURS_get_id ()
2697 return &my_identity;
2701 /* end of gnunet-service-xdht_neighbours.c */