2 This file is part of GNUnet.
3 (C) 2009-2014 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_ats_service.h"
34 #include "gnunet_core_service.h"
35 #include "gnunet_datacache_lib.h"
36 #include "gnunet_transport_service.h"
37 #include "gnunet_dht_service.h"
38 #include "gnunet_statistics_service.h"
39 #include "gnunet-service-xdht.h"
40 #include "gnunet-service-xdht_clients.h"
41 #include "gnunet-service-xdht_datacache.h"
42 #include "gnunet-service-xdht_neighbours.h"
43 #include "gnunet-service-xdht_routing.h"
48 * Maximum possible fingers of a peer.
50 #define MAX_FINGERS 65
53 * Maximum allowed number of pending messages per friend peer.
55 #define MAXIMUM_PENDING_PER_FRIEND 64
58 * How long to wait before sending another find finger trail request
60 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
63 * How long at most to wait for transmission of a request to another peer?
65 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
68 * How long will I remain congested?
70 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
73 * Maximum number of trails stored per finger.
75 #define MAXIMUM_TRAILS_PER_FINGER 2
78 * Used to distinguish put/get request use of find_successor() from others
80 #define PUT_GET_REQUEST 65
83 * Finger map index for predecessor entry in finger peermap.
85 #define PREDECESSOR_FINGER_ID 64
88 * Maximum number of trails allowed to go through a friend.
90 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
92 GNUNET_NETWORK_STRUCT_BEGIN
95 * P2P Trail setup message
97 struct PeerTrailSetupMessage
100 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
102 struct GNUNET_MessageHeader header;
105 * Peer closest to this value will be our finger.
107 uint64_t ultimate_destination_finger;
110 * Source peer which wants to setup the trail to one of its finger.
112 struct GNUNET_PeerIdentity source_peer;
115 * Peer to which this packet is forwarded.
117 struct GNUNET_PeerIdentity next_destination;
120 * Index into finger peer map, in Network Byte Order.
122 uint32_t finger_map_index;
125 * Number of entries in trail list, in Network Byte Order.
127 uint32_t trail_length GNUNET_PACKED;
130 * Trail id of any intermediate trail we may encounter while doing trail setup.
132 struct GNUNET_HashCode intermediate_trail_id;
135 * Trail id for trail which we are trying to setup.
137 struct GNUNET_HashCode new_trail_id;
139 /* Trail formed in the process. */
143 * P2P Trail Setup Result message
145 struct PeerTrailSetupResultMessage
149 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
151 struct GNUNET_MessageHeader header;
154 * Finger to which we have found the path.
156 struct GNUNET_PeerIdentity finger_identity;
159 * Peer which was looking for the trail to finger.
161 struct GNUNET_PeerIdentity destination_peer;
164 * Index into finger peer map in NBO.
166 uint32_t finger_map_index;
169 * Number of entries in trail list in NBO.
171 uint32_t trail_length GNUNET_PACKED;
174 * Identifier of the trail.
176 struct GNUNET_HashCode trail_id;
177 /* Trail from destination_peer to finger_identity */
181 struct PeerVerifySuccessorMessage
184 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
186 struct GNUNET_MessageHeader header;
189 * Source peer which wants to verify its successor.
191 struct GNUNET_PeerIdentity source_peer;
194 * My current successor.
196 struct GNUNET_PeerIdentity successor;
199 * Identifier of trail to reach from source_peer to successor.
201 struct GNUNET_HashCode trail_id;
204 struct PeerVerifySuccessorResultMessage
207 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
209 struct GNUNET_MessageHeader header;
212 * Destination peer which sent the request to verify its successor.
214 struct GNUNET_PeerIdentity destination_peer;
217 * Successor to which PeerVerifySuccessorMessage was sent.
219 struct GNUNET_PeerIdentity source_successor;
222 * source_successor's predecessor
224 struct GNUNET_PeerIdentity my_predecessor;
227 * Trail identifier of trail from my_predecessor to source_successor.
229 struct GNUNET_HashCode trail_id;
231 enum GDS_ROUTING_trail_direction trail_direction;
233 * Total number of peers in trail from source_successor to my_predecessor
234 * if my_predecessor is not same as destination_peer.
236 uint32_t trail_length;
238 /* Trail from source_successor to my_predecessor where
239 * my_predecessor != destination_peer*/
242 struct PeerNotifyNewSuccessorMessage
245 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
247 struct GNUNET_MessageHeader header;
250 * Source peer which wants to notify its new successor.
252 struct GNUNET_PeerIdentity source_peer;
255 * New successor identity.
257 struct GNUNET_PeerIdentity destination_peer;
259 unsigned int trail_length;
261 struct GNUNET_HashCode trail_id;
267 * Trail compressiong message.
269 struct PeerTrailCompressionMessage
272 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION
274 struct GNUNET_MessageHeader header;
277 * Source peer of this trail.
279 struct GNUNET_PeerIdentity source_peer;
282 * Destination of this trail.
284 struct GNUNET_PeerIdentity destination_peer;
287 * Trail from source_peer to destination_peer compressed such that
288 * new_first_friend is the first hop in the trail from source to
291 struct GNUNET_PeerIdentity new_first_friend;
294 * Unique identifier of trail.
296 struct GNUNET_HashCode trail_id;
300 * Trail Tear Down message.
302 struct PeerTrailTearDownMessage
305 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
307 struct GNUNET_MessageHeader header;
311 * Trail Rejection Message.
313 struct PeerTrailRejectionMessage
316 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
318 struct GNUNET_MessageHeader header;
321 * Source peer which wants to set up the trail.
323 struct GNUNET_PeerIdentity source_peer;
326 * Peer which sent trail rejection message.
328 struct GNUNET_PeerIdentity congested_peer;
331 * Peer identity which will be successor to this value will be finger of
334 uint64_t ultimate_destination_finger_identity_value;
337 * Index in finger peer map of source peer.
339 uint32_t finger_map_index;
342 * Total number of peers in the trail.
344 uint32_t trail_length;
347 * Identifier for the trail source peer is trying to setup.
349 struct GNUNET_HashCode trail_id;
351 * Relative time for which congested_peer will remain congested.
353 struct GNUNET_TIME_Relative congestion_time;
355 /* Trail_list from source_peer to peer which sent the message for trail setup
356 * to congested peer.*/
359 GNUNET_NETWORK_STRUCT_END
362 * Linked list of messages to send to a particular other peer.
364 struct P2PPendingMessage
367 * Pointer to next item in the list
369 struct P2PPendingMessage *next;
372 * Pointer to previous item in the list
374 struct P2PPendingMessage *prev;
377 * Message importance level. FIXME: used? useful?
379 unsigned int importance;
382 * When does this message time out?
384 struct GNUNET_TIME_Absolute timeout;
387 * Actual message to be sent, allocated at the end of the struct:
388 * // msg = (cast) &pm[1];
389 * // memcpy (&pm[1], data, len);
391 const struct GNUNET_MessageHeader *msg;
397 * Entry in friend_peermap.
404 struct GNUNET_PeerIdentity id;
407 * Number of trails for which this friend is the first hop.
409 unsigned int trails_count;
412 * Count of outstanding messages for this friend.
414 unsigned int pending_count;
417 * In case not 0, then amount of time for which this friend is congested.
419 struct GNUNET_TIME_Absolute congestion_duration;
422 * Head of pending messages to be sent to this friend.
424 struct P2PPendingMessage *head;
427 * Tail of pending messages to be sent to this friend.
429 struct P2PPendingMessage *tail;
432 * Core handle for sending messages to this friend.
434 struct GNUNET_CORE_TransmitHandle *th;
439 * An individual trail to reach to a finger.
444 * Pointer to next item in the list
449 * Pointer to prev item in the list
454 * An element in this trail.
456 struct GNUNET_PeerIdentity peer;
460 * List of all trails to reach a particular finger.
467 struct Trail *trail_head;
472 struct Trail *trail_tail;
475 * Unique identifier of this trail.
477 struct GNUNET_HashCode trail_id;
480 * Length of trail pointed
482 unsigned int trail_length;
485 * Number of trails that the first friend of this trail is a part of.
487 unsigned int first_friend_trail_count;
492 * An entry in finger_hashmap.
499 struct GNUNET_PeerIdentity finger_identity;
502 * Index in finger peer map
504 unsigned int finger_map_index;
507 * Number of trails setup so far for this finger.
509 unsigned int trails_count;
514 struct TrailList trail_list[MAXIMUM_TRAILS_PER_FINGER];
519 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
520 * get our first friend.
522 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
525 * Identity of this peer.
527 static struct GNUNET_PeerIdentity my_identity;
530 * Peer map of all the friends of a peer
532 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
535 * Hash map of all the fingers of a peer
537 static struct GNUNET_CONTAINER_MultiHashMap32 *finger_hashmap;
542 static struct GNUNET_CORE_Handle *core_api;
545 * The current finger index that we have want to find trail to. We start the
546 * search with value = 0, i.e. successor peer and then go to PREDCESSOR_FINGER_ID
547 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
548 * we reset this index to 0.
550 static unsigned int current_search_finger_index;
554 * Called when core is ready to send a message we asked for
555 * out to the destination.
557 * @param cls the 'struct FriendInfo' of the target friend
558 * @param size number of bytes available in buf
559 * @param buf where the callee should write the message
560 * @return number of bytes written to buf
563 core_transmit_notify (void *cls, size_t size, void *buf)
565 struct FriendInfo *peer = cls;
567 struct P2PPendingMessage *pending;
572 while ((NULL != (pending = peer->head)) &&
573 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
575 peer->pending_count--;
576 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
577 GNUNET_free (pending);
581 /* no messages pending */
587 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
588 GNUNET_CORE_PRIO_BEST_EFFORT,
589 GNUNET_TIME_absolute_get_remaining
590 (pending->timeout), &peer->id,
591 ntohs (pending->msg->size),
592 &core_transmit_notify, peer);
593 GNUNET_break (NULL != peer->th);
597 while ((NULL != (pending = peer->head)) &&
598 (size - off >= (msize = ntohs (pending->msg->size))))
600 GNUNET_STATISTICS_update (GDS_stats,
602 ("# Bytes transmitted to other peers"), msize,
604 memcpy (&cbuf[off], pending->msg, msize);
606 peer->pending_count--;
607 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
608 GNUNET_free (pending);
610 if (peer->head != NULL)
613 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
614 GNUNET_CORE_PRIO_BEST_EFFORT,
615 GNUNET_TIME_absolute_get_remaining
616 (pending->timeout), &peer->id, msize,
617 &core_transmit_notify, peer);
618 GNUNET_break (NULL != peer->th);
626 * FIXME: assertion fails at the end of this function. also in core_api.c at 1299.
627 * Transmit all messages in the friend's message queue.
629 * @param peer message queue to process
632 process_friend_queue (struct FriendInfo *peer)
634 struct P2PPendingMessage *pending;
636 if (NULL == (pending = peer->head))
638 if (NULL != peer->th)
641 GNUNET_STATISTICS_update (GDS_stats,
643 ("# Bytes of bandwidth requested from core"),
644 ntohs (pending->msg->size), GNUNET_NO);
647 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
649 GNUNET_TIME_absolute_get_remaining
650 (pending->timeout), &peer->id,
651 ntohs (pending->msg->size),
652 &core_transmit_notify, peer);
653 GNUNET_break (NULL != peer->th);
658 * Construct a trail setup message and forward it to target_friend
659 * @param source_peer Source peer which wants to setup the trail
660 * @param ultimate_destination_finger Peer identity closest to this value will
661 * be finger to @a source_peer
662 * @param next_destination Peer which should get the packet. I can be same as
663 * target_friend or different.
664 * @param target_friend Friend to which message is forwarded now.
665 * @param trail_length Total number of peers in trail setup so far.
666 * @param trail_peer_list Trail setup so far
667 * @param finger_map_index Index in finger map for which we are looking for finger.
668 * @param trail_id Unique identifier for the trail we are trying to setup.
669 * @param intermediate_trail_id Trail id of any intermediate trail we may have to
670 * traverse during trail setup. If not used then set to
674 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity source_peer,
675 uint64_t ultimate_destination_finger,
676 struct GNUNET_PeerIdentity next_destination,
677 struct FriendInfo *target_friend,
678 unsigned int trail_length,
679 const struct GNUNET_PeerIdentity *trail_peer_list,
680 unsigned int finger_map_index,
681 struct GNUNET_HashCode new_trail_id,
682 struct GNUNET_HashCode intermediate_trail_id)
684 struct P2PPendingMessage *pending;
685 struct PeerTrailSetupMessage *tsm;
686 struct GNUNET_PeerIdentity *peer_list;
689 msize = sizeof (struct PeerTrailSetupMessage) +
690 (trail_length * sizeof (struct GNUNET_PeerIdentity));
692 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
698 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
700 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
704 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
705 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
706 tsm = (struct PeerTrailSetupMessage *) &pending[1];
707 pending->msg = &tsm->header;
708 tsm->header.size = htons (msize);
709 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
710 tsm->ultimate_destination_finger = GNUNET_htonll (ultimate_destination_finger);
711 tsm->source_peer = source_peer;
712 tsm->next_destination = next_destination;
713 tsm->trail_length = htonl (trail_length);
714 tsm->finger_map_index = htonl (finger_map_index);
715 tsm->new_trail_id = new_trail_id;
716 tsm->intermediate_trail_id = intermediate_trail_id;
717 if (trail_length > 0)
719 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
720 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
723 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
724 target_friend->pending_count++;
725 process_friend_queue (target_friend);
730 * Construct a trail setup result message and forward it to target friend.
731 * @param destination_peer
732 * @param source_finger
733 * @param target_friend
734 * @param trail_length
735 * @param trail_peer_list
736 * @param finger_map_index
740 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity destination_peer,
741 struct GNUNET_PeerIdentity source_finger,
742 struct FriendInfo *target_friend,
743 unsigned int trail_length,
744 const struct GNUNET_PeerIdentity *trail_peer_list,
745 unsigned int finger_map_index,
746 struct GNUNET_HashCode trail_id)
748 struct P2PPendingMessage *pending;
749 struct PeerTrailSetupResultMessage *tsrm;
750 struct GNUNET_PeerIdentity *peer_list;
753 msize = sizeof (struct PeerTrailSetupResultMessage) +
754 (trail_length * sizeof (struct GNUNET_PeerIdentity));
756 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
762 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
764 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
768 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
769 pending->importance = 0;
770 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
771 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
772 pending->msg = &tsrm->header;
773 tsrm->header.size = htons (msize);
774 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
775 tsrm->destination_peer = destination_peer;
776 tsrm->finger_identity = source_finger;
777 tsrm->trail_length = htonl (trail_length);
778 tsrm->finger_map_index = htonl (finger_map_index);
779 tsrm->trail_id = trail_id;
781 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
782 if (trail_length > 0)
784 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
786 /* Send the message to chosen friend. */
787 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
788 target_friend->pending_count++;
789 process_friend_queue (target_friend);
794 * Send trail rejection message to next_hop
795 * @param source_peer Source peer which is trying to setup the trail.
796 * @param finger_identity Peer closest to this value will be @a source_peer's finger
797 * @param congested_peer Peer which sent this message as it is congested.
798 * @param next_hop Peer to which we are forwarding this message.
799 * @param finger_map_index Index in finger peermap for which we are searching for finger.
800 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
802 * @param trail_length Total number of peers in trail_peer_list
803 * @param trail_id Unique identifier of this trail.
804 * @param congestion_timeout Duration given by congested peer as an estimate of
805 * how long it may remain congested.
808 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
809 uint64_t finger_identity,
810 struct GNUNET_PeerIdentity congested_peer,
811 unsigned int finger_map_index,
812 struct GNUNET_PeerIdentity *trail_peer_list,
813 unsigned int trail_length,
814 struct GNUNET_HashCode trail_id,
815 struct FriendInfo *target_friend,
816 const struct GNUNET_TIME_Relative congestion_timeout)
818 struct PeerTrailRejectionMessage *trm;
819 struct P2PPendingMessage *pending;
820 struct GNUNET_PeerIdentity *peer_list;
823 msize = sizeof (struct PeerTrailRejectionMessage) +
824 (trail_length * sizeof (struct GNUNET_PeerIdentity));
826 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
832 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
834 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
838 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
839 pending->importance = 0;
840 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
841 trm = (struct PeerTrailRejectionMessage *)&pending[1];
842 pending->msg = &trm->header;
843 trm->header.size = htons (msize);
844 trm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION);
845 trm->source_peer = source_peer;
846 trm->congested_peer = congested_peer;
847 trm->congestion_time = congestion_timeout;
848 trm->finger_map_index = htonl (finger_map_index);
849 trm->trail_id = trail_id;
851 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
852 if (trail_length > 0)
854 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
856 /* Send the message to chosen friend. */
857 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
858 target_friend->pending_count++;
859 process_friend_queue (target_friend);
864 * Construct a verify successor message and forward it to target_friend.
865 * @param source_peer Peer which wants to verify its successor.
866 * @param successor Peer which is @a source_peer's current successor.
867 * @param trail_id Identifier of trail to reach successor.
868 * @param target_friend Message send to this friend.
871 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
872 struct GNUNET_PeerIdentity successor,
873 const struct GNUNET_HashCode trail_id,
874 struct FriendInfo *target_friend)
876 struct PeerVerifySuccessorMessage *vsm;
877 struct P2PPendingMessage *pending;
880 msize = sizeof (struct PeerVerifySuccessorMessage);
881 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
887 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
889 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
893 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
894 pending->importance = 0; /* FIXME */
895 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
896 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
897 pending->msg = &vsm->header;
898 vsm->header.size = htons (msize);
899 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
900 vsm->source_peer = source_peer;
901 vsm->successor = successor;
902 vsm->trail_id = trail_id;
904 /* Send the message to chosen friend. */
905 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
906 target_friend->pending_count++;
907 process_friend_queue (target_friend);
914 * @param destination_peer
916 * @param trail_direction
917 * @param target_friend
920 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_PeerIdentity source_peer,
921 struct GNUNET_PeerIdentity destination_peer,
922 struct GNUNET_HashCode trail_id,
923 enum GDS_ROUTING_trail_direction trail_direction,
924 struct FriendInfo *target_friend)
932 * @param destination_peer
933 * @param source_successor
934 * @param succ_predecessor
937 * @param trail_length
938 * @param target_friend
941 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity destination_peer,
942 struct GNUNET_PeerIdentity source_successor,
943 struct GNUNET_PeerIdentity succ_predecessor,
944 struct GNUNET_HashCode trail_id,
945 const struct GNUNET_PeerIdentity *trail,
946 unsigned int trail_length,
947 enum GDS_ROUTING_trail_direction trail_direction,
948 struct FriendInfo *target_friend)
950 struct PeerVerifySuccessorResultMessage *vsmr;
951 struct P2PPendingMessage *pending;
952 struct GNUNET_PeerIdentity *peer_list;
955 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
956 (trail_length * sizeof(struct GNUNET_PeerIdentity));
958 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
964 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
966 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
970 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
971 pending->importance = 0; /* FIXME */
972 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
973 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
974 pending->msg = &vsmr->header;
975 vsmr->header.size = htons (msize);
976 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
977 vsmr->destination_peer = destination_peer;
978 vsmr->my_predecessor = succ_predecessor;
979 vsmr->source_successor = source_successor;
980 vsmr->trail_direction = htonl (trail_direction);
982 if (trail_length > 0)
984 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
985 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
988 /* Send the message to chosen friend. */
989 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
990 target_friend->pending_count++;
991 process_friend_queue (target_friend);
998 * @param new_successor
999 * @param new_successor_trail
1000 * @param new_successor_trail_length
1001 * @param new_succesor_trail_id
1004 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1005 struct GNUNET_PeerIdentity new_successor,
1006 struct GNUNET_PeerIdentity *new_successor_trail,
1007 unsigned int new_successor_trail_length,
1008 struct GNUNET_HashCode new_succesor_trail_id,
1009 struct FriendInfo *target_friend)
1011 struct PeerNotifyNewSuccessorMessage *nsm;
1012 struct P2PPendingMessage *pending;
1013 struct GNUNET_PeerIdentity *peer_list;
1016 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1017 (new_successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1019 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1025 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1027 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1031 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1032 pending->importance = 0; /* FIXME */
1033 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1034 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1035 pending->msg = &nsm->header;
1036 nsm->header.size = htons (msize);
1037 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1038 nsm->source_peer = source_peer;
1039 nsm->destination_peer = new_successor;
1040 nsm->trail_length = htonl (new_successor_trail_length);
1041 nsm->trail_id = new_succesor_trail_id;
1042 if (new_successor_trail_length > 0)
1044 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1045 memcpy (peer_list, new_successor_trail,
1046 new_successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1049 /* Send the message to chosen friend. */
1050 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1051 target_friend->pending_count++;
1052 process_friend_queue (target_friend);
1057 * Send a trail compression message to target_friend.
1058 * @param source_peer Source of the trail.
1059 * @param destination_finger Destination of trail.
1060 * @param trail_id Unique identifier of trail.
1061 * @param first_friend First hop in compressed trail to reach from source to finger
1062 * @param target_friend Next friend to get this message.
1065 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1066 struct GNUNET_PeerIdentity destination_peer,
1067 struct GNUNET_HashCode trail_id,
1068 struct GNUNET_PeerIdentity first_friend,
1069 struct FriendInfo *target_friend)
1071 struct P2PPendingMessage *pending;
1072 struct PeerTrailCompressionMessage *tcm;
1075 msize = sizeof (struct PeerTrailCompressionMessage);
1077 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1083 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1085 GNUNET_STATISTICS_update (GDS_stats,
1086 gettext_noop ("# P2P messages dropped due to full queue"),
1090 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1091 pending->importance = 0; /* FIXME */
1092 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1093 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1094 pending->msg = &tcm->header;
1095 tcm->header.size = htons (msize);
1096 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION);
1097 tcm->source_peer = source_peer;
1098 tcm->new_first_friend = first_friend;
1099 tcm->trail_id = trail_id;
1100 tcm->destination_peer = destination_peer;
1102 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1103 target_friend->pending_count++;
1104 process_friend_queue (target_friend);
1109 * Construct a Put message and send it to target_peer.
1110 * @param key Key for the content
1111 * @param block_type Type of the block
1112 * @param options Routing options
1113 * @param desired_replication_level Desired replication count
1114 * @param current_destination Next current destination which will get this message.
1115 * @param current_source Source for @a current_destination
1116 * @param target_peer Peer to which this message will be forwarded.
1117 * @param hop_count Number of hops traversed so far.
1118 * @param put_path_length Total number of peers in @a put_path
1119 * @param put_path Number of peers traversed so far
1120 * @param expiration_time When does the content expire
1121 * @param data Content to store
1122 * @param data_size Size of content @a data in bytes
1125 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
1126 enum GNUNET_BLOCK_Type block_type,
1127 enum GNUNET_DHT_RouteOption options,
1128 uint32_t desired_replication_level,
1129 struct GNUNET_PeerIdentity current_destination,
1130 struct GNUNET_PeerIdentity current_source,
1131 struct GNUNET_PeerIdentity *target_peer,
1133 uint32_t put_path_length,
1134 struct GNUNET_PeerIdentity *put_path,
1135 struct GNUNET_TIME_Absolute expiration_time,
1136 const void *data, size_t data_size)
1142 * Construct a Get message and send it to target_peer.
1143 * @param key Key for the content
1144 * @param block_type Type of the block
1145 * @param options Routing options
1146 * @param desired_replication_level Desired replication count
1147 * @param current_destination Next current destination which will get this message.
1148 * @param current_source Source for @a current_destination
1149 * @param target_peer Peer to which this message will be forwarded.
1150 * @param hop_count Number of hops traversed so far.
1151 * @param data Content to store
1152 * @param data_size Size of content @a data in bytes
1153 * @param get_path_length Total number of peers in @a get_path
1154 * @param get_path Number of peers traversed so far
1157 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
1158 enum GNUNET_BLOCK_Type block_type,
1159 enum GNUNET_DHT_RouteOption options,
1160 uint32_t desired_replication_level,
1161 struct GNUNET_PeerIdentity current_destination,
1162 struct GNUNET_PeerIdentity current_source,
1163 struct GNUNET_PeerIdentity *target_peer,
1165 uint32_t get_path_length,
1166 struct GNUNET_PeerIdentity *get_path)
1173 * Send the get result to requesting client.
1174 * @param key Key of the requested data.
1175 * @param type Block type
1176 * @param target_peer Next peer to forward the message to.
1177 * @param source_peer Peer which has the data for the key.
1178 * @param put_path_length Number of peers in @a put_path
1179 * @param put_path Path taken to put the data at its stored location.
1180 * @param get_path_length Number of peers in @a get_path
1181 * @param get_path Path taken to reach to the location of the key.
1182 * @param expiration When will this result expire?
1183 * @param data Payload to store
1184 * @param data_size Size of the @a data
1187 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
1188 enum GNUNET_BLOCK_Type type,
1189 struct GNUNET_PeerIdentity *target_peer,
1190 struct GNUNET_PeerIdentity *source_peer,
1191 unsigned int put_path_length,
1192 const struct GNUNET_PeerIdentity *put_path,
1193 unsigned int get_path_length,
1194 struct GNUNET_PeerIdentity *get_path,
1195 struct GNUNET_TIME_Absolute expiration,
1196 const void *data, size_t data_size)
1203 * Seach my location in trail.
1204 * @param trail List of peers
1205 * @return my_index if found
1206 * #GNUNET_SYSERR if no entry found.
1209 search_my_index (const struct GNUNET_PeerIdentity *trail,
1214 for (i = 0; i < trail_length; i++)
1216 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1220 return GNUNET_SYSERR;
1225 * Find the successor for destination_finger_value among my_identity, all my
1226 * friend and all my fingers. Don't consider friends/ fingers with first friend in
1227 * the trail which are congested or have crossed the threshold.
1228 * @param destination_finger_value Peer closest to this value will be the next successor.
1229 * @param next_destination [out] Updated to friend identity in case a friend is
1230 * successor, updated to first friend to reach to finger
1231 * in case finger is the destination.
1232 * @param new_intermediate_trail_id [out] In case we finger is the @a next_destination,
1233 * then we updated the field with trail id to reach
1235 * @param finger_map_index Index in finger peermap for which we are looking for a finger.
1238 static struct GNUNET_PeerIdentity *
1239 find_successor (uint64_t destination_finger_value,
1240 struct GNUNET_PeerIdentity *next_destination,
1241 struct GNUNET_HashCode *new_intermediate_trail_id,
1242 unsigned int finger_map_index)
1244 /* FIXME; IMPLEMENT*/
1250 * Select closest finger to value.
1251 * @param peer1 First peer
1252 * @param peer2 Second peer
1253 * @param value Value to be compare
1254 * @return Closest peer
1256 static struct GNUNET_PeerIdentity *
1257 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1258 struct GNUNET_PeerIdentity *peer2,
1261 uint64_t peer1_value;
1262 uint64_t peer2_value;
1264 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1265 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1267 if ((peer1_value <= value) && (value <= peer2_value))
1269 else if ((peer2_value <= value) && (value <= peer1_value))
1271 else if ((peer1_value <= peer2_value) && (peer2_value <= value))
1273 else if ((peer2_value <= peer1_value) && (peer1_value <= value))
1275 else if ((value <= peer1_value) && (peer1_value <= peer2_value))
1277 else /*if ((value <= peer2_value) && (peer2_value <= peer1_value))*/
1283 * Select closest predecessor to value.
1284 * @param peer1 First peer
1285 * @param peer2 Second peer
1286 * @param value Value to be compare
1287 * @return Closest peer
1289 static struct GNUNET_PeerIdentity *
1290 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1291 struct GNUNET_PeerIdentity *peer2,
1294 uint64_t peer1_value;
1295 uint64_t peer2_value;
1297 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1298 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1300 if ((peer1_value <= value) && (value <= peer2_value))
1302 else if ((peer2_value <= value) && (value <= peer1_value))
1304 else if ((peer1_value <= peer2_value) && (peer2_value <= value))
1306 else if ((peer2_value <= peer1_value) && (peer1_value <= value))
1308 else if ((value <= peer1_value) && (peer1_value <= peer2_value))
1310 else /*if ((value <= peer2_value) && (peer2_value <= peer1_value))*/
1316 * Select the closest peer among two peers (which should not be same)
1317 * with respect to value and finger_map_index
1318 * @param peer1 First peer
1319 * @param peer2 Second peer
1320 * @param value Value relative to which we find the closest
1321 * @param finger_map_index Index in finger map. If equal to PREDECESSOR_FINGER_ID,
1322 * then we use different logic than other
1324 * @return Closest peer among two peers.
1326 static struct GNUNET_PeerIdentity *
1327 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1328 struct GNUNET_PeerIdentity *peer2,
1330 unsigned int finger_map_index)
1332 struct GNUNET_PeerIdentity *closest_peer;
1334 if (PREDECESSOR_FINGER_ID == finger_map_index)
1335 closest_peer = select_closest_predecessor (peer1, peer2, value);
1337 closest_peer = select_closest_finger (peer1, peer2, value);
1339 return closest_peer;
1345 * Randomly choose one of your friends (which is not congested and have not crossed
1346 * trail threshold) from the friends_peer map
1347 * @return Friend Randomly chosen friend.
1348 * NULL in case friend peermap is empty, or all the friends are either
1349 * congested or have crossed trail threshold.
1351 static struct FriendInfo *
1352 select_random_friend ()
1354 unsigned int current_size;
1357 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1358 struct GNUNET_PeerIdentity key_ret;
1359 struct FriendInfo *friend;
1361 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1362 if (0 == current_size)
1365 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1366 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1368 for (j = 0; j < index ; j++)
1369 GNUNET_assert (GNUNET_YES ==
1370 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
1373 if (j == current_size)
1376 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1377 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1380 GNUNET_assert (GNUNET_YES ==
1381 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
1383 (const void **)&friend));
1386 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1387 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us))
1393 } while (j != index);
1395 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1401 * Compute finger_identity to which we want to setup the trail
1402 * @return finger_identity
1405 compute_finger_identity()
1409 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1410 my_id64 = GNUNET_ntohll (my_id64);
1411 return (my_id64 + (unsigned long) pow (2, current_search_finger_index));
1416 * Compute immediate predecessor identity in the network.
1417 * @return peer identity of immediate predecessor.
1420 compute_predecessor_identity()
1424 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1425 my_id64 = GNUNET_ntohll (my_id64);
1426 return (my_id64 -1);
1431 * Choose a random friend and start looking for the trail to reach to
1432 * finger identity through this random friend.
1434 * @param cls closure for this task
1435 * @param tc the context under which the task is running
1438 send_find_finger_trail_message (void *cls,
1439 const struct GNUNET_SCHEDULER_TaskContext *tc)
1441 struct FriendInfo *target_friend;
1442 struct GNUNET_TIME_Relative next_send_time;
1443 struct GNUNET_HashCode trail_id;
1444 struct GNUNET_HashCode intermediate_trail_id;
1445 unsigned int finger_map_index;
1446 uint64_t finger_identity;
1448 next_send_time.rel_value_us =
1449 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1450 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1451 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1452 find_finger_trail_task =
1453 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1456 target_friend = select_random_friend ();
1457 if (NULL == target_friend)
1462 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
1464 finger_identity = compute_predecessor_identity();
1468 finger_identity = compute_finger_identity();
1471 finger_map_index = current_search_finger_index;
1473 /* FIXME: Find the correct function to generate a random trail id which is of
1474 * type struct GNUNET_HashCode. */
1475 //trail_id = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_STRONG, UINT64_MAX);
1477 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_identity,
1478 target_friend->id, target_friend, 0, NULL,
1479 finger_map_index, trail_id, intermediate_trail_id);
1484 * In case there are already maximum number of possible trail to reach to a finger,
1485 * then check if the new trail's length is lesser than any of the existing trails.
1486 * If yes then replace that old trail by new trail.
1487 * Note: Here we are taking length as a parameter to choose the best possible trail,
1488 * but there could be other parameters also like - 1. duration of existence of a
1489 * trail - older the better. 2. if the new trail is completely disjoint than the
1490 * other trails, then may be choosing it is better.
1491 * @param existing_finger
1492 * @param new_finger_trail
1493 * @param new_finger_trail_length
1494 * @param new_finger_trail_id
1497 select_and_replace_trail (struct FingerInfo *existing_finger,
1498 struct GNUNET_PeerIdentity *new_trail,
1499 unsigned int new_trail_length,
1500 struct GNUNET_HashCode new_trail_id)
1502 struct TrailList *trail_list_iterator;
1503 unsigned int largest_trail_length;
1504 unsigned int largest_trail_index;
1505 struct Trail *trail_element;
1508 largest_trail_length = new_trail_length;
1509 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
1511 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
1513 for (i = 0; i < existing_finger->trails_count; i++)
1515 trail_list_iterator = &existing_finger->trail_list[i];
1516 if (trail_list_iterator->trail_length > largest_trail_length)
1518 largest_trail_length = trail_list_iterator->trail_length;
1519 largest_trail_index = i;
1523 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
1526 /* Send trail teardown message across the replaced trail. */
1527 struct TrailList *replace_trail = &existing_finger->trail_list[largest_trail_index];
1528 struct FriendInfo *target_friend =
1529 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1530 &replace_trail->trail_head->peer);
1532 GDS_NEIGHBOURS_send_trail_teardown (my_identity,
1533 existing_finger->finger_identity,
1534 replace_trail->trail_id,
1535 GDS_ROUTING_SRC_TO_DEST, target_friend);
1536 /* Free the trail .*/
1537 while (NULL != (trail_element = replace_trail->trail_head))
1539 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
1540 replace_trail->trail_tail, trail_element);
1541 GNUNET_free (trail_element);
1544 /* Add new trial at that location. */
1546 while ( i < new_trail_length)
1548 struct Trail *element = GNUNET_new (struct Trail);
1549 element->next = NULL;
1550 element->prev = NULL;
1551 element->peer = new_trail[0];
1553 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
1554 replace_trail->trail_tail,
1561 * Check if the new trail to reach to finger is unique or do we already have
1562 * such a trail present for finger.
1563 * @param existing_finger Finger identity
1564 * @param new_trail New trail to reach @a existing_finger
1565 * @param trail_length Total number of peers in new_trail.
1566 * @return #GNUNET_YES if the new trail is unique
1567 * #GNUNET_NO if same trail is already present.
1570 is_new_trail_unique (struct FingerInfo *existing_finger,
1571 struct GNUNET_PeerIdentity *new_trail,
1572 unsigned int trail_length)
1574 struct TrailList *trail_list_iterator;
1575 struct Trail *trail_element;
1578 int trail_unique = GNUNET_NO;
1580 for (i = 0; i < existing_finger->trails_count; i++)
1582 trail_list_iterator = &existing_finger->trail_list[i];
1583 trail_element = trail_list_iterator->trail_head;
1584 for (j = 0; j < trail_list_iterator->trail_length; j++)
1586 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
1587 &trail_element->peer))
1589 trail_unique = GNUNET_YES;
1594 return trail_unique;
1599 * Add a new trail to existing finger.
1600 * @param existing_finger
1601 * @param new_finger_trail
1602 * @param new_finger_trail_length
1603 * @param new_finger_trail_id
1606 add_new_trail (struct FingerInfo *existing_finger,
1607 struct GNUNET_PeerIdentity *new_trail,
1608 unsigned int new_trail_length,
1609 struct GNUNET_HashCode new_trail_id)
1611 struct TrailList *trail_list_iterator;
1612 struct FriendInfo *first_friend;
1616 if (GNUNET_NO == is_new_trail_unique (existing_finger,
1623 trail_list_iterator = &existing_finger->trail_list[i];
1625 } while (trail_list_iterator->trail_head != NULL);
1627 if (new_trail_length > 0)
1628 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1631 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1632 &(existing_finger->finger_identity));
1633 first_friend->trails_count++;
1634 trail_list_iterator->first_friend_trail_count = first_friend->trails_count;
1635 trail_list_iterator->trail_length = new_trail_length;
1637 for (j = 0; j < new_trail_length; j++)
1639 struct Trail *element;
1640 element = GNUNET_new (struct Trail);
1642 element->next = NULL;
1643 element->prev = NULL;
1644 element->peer = new_trail[j];
1645 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
1646 trail_list_iterator->trail_tail,
1649 existing_finger->trails_count++;
1654 * Send trail teardown message on all trails associated with finger.
1655 * @param finger_to_be_removed
1658 send_trail_teardown (struct FingerInfo *finger)
1660 struct TrailList *trail_list_iterator;
1661 struct GNUNET_HashCode trail_id;
1662 struct FriendInfo *target_friend;
1665 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity, &my_identity)
1666 || (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1667 &finger->finger_identity)))
1670 for (i = 0; i < finger->trails_count; i++)
1672 trail_list_iterator = &finger->trail_list[i];
1673 if (trail_list_iterator->trail_length > 0)
1675 trail_id = trail_list_iterator->trail_id;
1677 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1678 &trail_list_iterator->trail_head->peer);
1679 GDS_NEIGHBOURS_send_trail_teardown (my_identity, finger->finger_identity,
1680 trail_id, GDS_ROUTING_SRC_TO_DEST,
1688 * Decrement the trail count of the first friend to reach the finger
1689 * In case finger is the friend, then decrement its trail count.
1693 decrement_friend_trail_count (struct FingerInfo *finger)
1695 struct TrailList *trail_list_iterator;
1696 struct FriendInfo *target_friend;
1699 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1703 for (i = 0; i < finger->trails_count; i++)
1705 trail_list_iterator = &finger->trail_list[i];
1706 if (trail_list_iterator->trail_length > 0)
1708 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1709 &trail_list_iterator->trail_head->peer);
1712 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1713 &finger->finger_identity);
1715 target_friend->trails_count--;
1716 trail_list_iterator->first_friend_trail_count--;
1723 * Free finger and its trail.
1724 * @param finger Finger to be freed.
1727 free_finger (struct FingerInfo *finger)
1729 struct TrailList *trail_list_iterator;
1730 struct Trail *trail_element;
1733 for (i = 0; i < finger->trails_count; i++)
1735 trail_list_iterator = &finger->trail_list[i];
1736 while (NULL != (trail_element = trail_list_iterator->trail_head))
1738 GNUNET_CONTAINER_DLL_remove (trail_list_iterator->trail_head,
1739 trail_list_iterator->trail_tail, trail_element);
1740 GNUNET_free (trail_element);
1743 GNUNET_free (finger);
1748 * Check if new finger is closer than existing_finger. If both new finger and
1749 * existing finger are same then we may add a new trail (if there is space)
1750 * or choose the best trail among existing trails and new trails.
1751 * @param existing_finger Finger present in finger_peermap at @a finger_map_index
1752 * @param new_finger_identity Peer identity of new finger.
1753 * @param new_finger_trail Trail to reach from source to new_finger.
1754 * @param new_finger_trail_length Total number of peers in @a new_finger_trail.
1755 * @param trail_id Unique identifier of trail.
1756 * @param finger_map_index Index in finger map.
1757 * @return #GNUNET_YES if the new finger is closest.
1758 * #GNUNET_NO either new_finger and existing_finger are same, or
1759 * existing_finger is closest.
1762 is_new_finger_closest (struct FingerInfo *existing_finger,
1763 struct GNUNET_PeerIdentity new_finger_identity,
1764 struct GNUNET_PeerIdentity *new_finger_trail,
1765 unsigned int new_finger_trail_length,
1766 struct GNUNET_HashCode new_finger_trail_id,
1767 unsigned int finger_map_index)
1769 struct GNUNET_PeerIdentity *closest_peer;
1772 if (NULL == existing_finger)
1775 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
1776 &new_finger_identity))
1778 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1779 closest_peer = select_closest_peer (&existing_finger->finger_identity,
1780 &new_finger_identity,
1781 my_id64, finger_map_index);
1783 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity, closest_peer))
1785 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
1786 &new_finger_identity)) /* FIXME: not sure what to do here? */
1789 send_trail_teardown (existing_finger);
1790 decrement_friend_trail_count (existing_finger);
1791 free_finger (existing_finger);
1797 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
1801 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1802 &(existing_finger->finger_identity)))
1804 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
1805 add_new_trail (existing_finger, new_finger_trail,
1806 new_finger_trail_length, new_finger_trail_id);
1808 select_and_replace_trail (existing_finger, new_finger_trail,
1809 new_finger_trail_length, new_finger_trail_id);
1818 * Add a new entry in finger hashmap at finger_map_index
1819 * @param finger_identity Peer Identity of new finger
1820 * @param finger_trail Trail to reach from me to finger (excluding both end points).
1821 * @param finger_trail_length Total number of peers in @a finger_trail.
1822 * @param trail_id Unique identifier of the trail.
1823 * @param finger_map_index Index in finger hashmap.
1824 * @return #GNUNET_OK if new entry is added
1825 * #GNUNET_NO -- FIXME: need to check what value does hahsmap put
1826 * returns on failure.
1829 add_new_entry (struct GNUNET_PeerIdentity finger_identity,
1830 struct GNUNET_PeerIdentity *finger_trail,
1831 unsigned int finger_trail_length,
1832 struct GNUNET_HashCode trail_id,
1833 unsigned int finger_map_index)
1835 struct FingerInfo *new_entry;
1836 struct FriendInfo *first_trail_hop;
1837 struct TrailList *first_trail;
1840 new_entry = GNUNET_new (struct FingerInfo);
1841 new_entry->finger_identity = finger_identity;
1842 new_entry->finger_map_index = finger_map_index;
1843 new_entry->trails_count = 1;
1845 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
1847 if (finger_trail_length > 0)
1849 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1854 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1858 first_trail_hop->trails_count++;
1859 first_trail = &new_entry->trail_list[0];
1860 first_trail->first_friend_trail_count = first_trail_hop->trails_count;
1862 while (i < finger_trail_length)
1864 struct Trail *element = GNUNET_new (struct Trail);
1866 element->next = NULL;
1867 element->prev = NULL;
1868 element->peer = finger_trail[i];
1869 GNUNET_CONTAINER_DLL_insert_tail (first_trail->trail_head,
1870 first_trail->trail_tail,
1876 return GNUNET_CONTAINER_multihashmap32_put (finger_hashmap,
1877 new_entry->finger_map_index,
1879 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
1884 * Scan the trail to check if there is any other friend in the trail other than
1885 * first hop. If yes the shortcut the trail, send trail compression message to
1886 * peers which are no longer part of trail and send back the updated trail
1887 * and trail_length to calling function.
1888 * @param finger_identity Finger whose trail we will scan.
1889 * @param finger_trail [in, out] Trail to reach from source to finger,
1890 * @param finger_trail_length Total number of peers in original finger_trail.
1891 * @param finger_trail_id Unique identifier of the finger trail.
1892 * @return updated trail length in case we shortcut the trail, else original
1896 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
1897 struct GNUNET_PeerIdentity *trail,
1898 unsigned int trail_length,
1899 struct GNUNET_HashCode trail_id)
1901 struct FriendInfo *target_friend;
1904 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
1910 if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
1912 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1914 GDS_NEIGHBOURS_send_trail_compression (my_identity, finger_identity,
1915 trail_id, finger_identity,
1921 for ( i = trail_length - 1; i > 0; i--)
1923 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
1925 struct FriendInfo *target_friend;
1928 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1930 GDS_NEIGHBOURS_send_trail_compression (my_identity, finger_identity,
1934 /* Copy the trail from index i to index trail_length -1 and change
1935 trail length and return */
1936 while (i < trail_length)
1938 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
1946 return trail_length;
1951 * Send verify successor message to your successor on all trails to reach successor.
1952 * @param successor My current successor
1955 send_verify_successor_message (struct FingerInfo *successor)
1957 struct TrailList *trail_list_iterator;
1958 struct GNUNET_HashCode trail_id;
1959 struct GNUNET_PeerIdentity next_hop;
1960 struct FriendInfo *target_friend;
1963 for (i = 0; i < successor->trails_count; i++)
1965 trail_list_iterator = &successor->trail_list[i];
1966 if (trail_list_iterator->trail_length > 0)
1967 next_hop = trail_list_iterator->trail_head->peer;
1969 next_hop = successor->finger_identity;
1971 trail_id = trail_list_iterator->trail_id;
1972 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
1973 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
1974 successor->finger_identity,
1975 trail_id, target_friend);
1981 * Check if there is already an entry in finger peermap for given finger map index.
1982 * If yes, then select the closest finger. If new and existing finger are same,
1983 * the check if you can store more trails. If yes then add trail, else keep the best
1984 * trails to reach to the finger. If the new finger is closest, add it.
1985 * Then, update current_search_finger_index.
1986 * @param new_finger_identity Peer Identity of new finger
1987 * @param new_finger_trail Trail to reach the new finger
1988 * @param new_finger_length Total number of peers in @a new_finger_trail.
1989 * @param finger_map_index Index in finger peermap.
1990 * @param new_finger_trail_id Unique identifier of @new_finger_trail.
1991 * @return #GNUNET_YES if the new entry is added
1992 * #GNUNET_NO if new entry is not added, either it was discarded or
1993 * it was same as existing finger at finger map index.
1996 finger_table_add (struct GNUNET_PeerIdentity new_finger_identity,
1997 struct GNUNET_PeerIdentity *new_finger_trail,
1998 unsigned int new_finger_trail_length,
1999 unsigned int finger_map_index,
2000 struct GNUNET_HashCode new_finger_trail_id)
2002 struct FingerInfo *existing_finger;
2003 struct FingerInfo *successor;
2004 unsigned int new_entry_added = GNUNET_NO;
2006 int new_finger_updated_trail_length =
2007 scan_and_compress_trail (new_finger_identity, new_finger_trail,
2008 new_finger_trail_length, new_finger_trail_id);
2010 successor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2012 existing_finger = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2015 if (GNUNET_YES == is_new_finger_closest (existing_finger,
2016 new_finger_identity,
2018 new_finger_updated_trail_length,
2019 new_finger_trail_id, finger_map_index))
2021 GNUNET_assert (GNUNET_YES == add_new_entry (new_finger_identity,
2023 new_finger_updated_trail_length,
2024 new_finger_trail_id,
2026 new_entry_added = GNUNET_YES;
2029 if (0 == finger_map_index)
2031 current_search_finger_index = PREDECESSOR_FINGER_ID;
2033 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,&new_finger_identity))
2035 send_verify_successor_message (successor);
2038 else if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity,
2039 &(successor->finger_identity)))
2041 current_search_finger_index = 0;
2044 current_search_finger_index = current_search_finger_index - 1;
2046 return new_entry_added;
2051 * Core handler for P2P put messages.
2052 * @param cls closure
2053 * @param peer sender of the request
2054 * @param message message
2055 * @return #GNUNET_OK to keep the connection open,
2056 * #GNUNET_SYSERR to close it (signal serious error)
2059 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2060 const struct GNUNET_MessageHeader *message)
2067 * Core handler for p2p get requests.
2069 * @param cls closure
2070 * @param peer sender of the request
2071 * @param message message
2072 * @return #GNUNET_OK to keep the connection open,
2073 * #GNUNET_SYSERR to close it (signal serious error)
2076 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2077 const struct GNUNET_MessageHeader *message)
2084 * Core handler for get result
2085 * @param cls closure
2086 * @param peer sender of the request
2087 * @param message message
2088 * @return #GNUNET_OK to keep the connection open,
2089 * #GNUNET_SYSERR to close it (signal serious error)
2092 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
2093 const struct GNUNET_MessageHeader *message)
2099 /* Core handle for PeerTrailSetupMessage.
2100 * @param cls closure
2101 * @param message message
2102 * @param peer peer identity this notification is about
2103 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2106 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
2107 const struct GNUNET_MessageHeader *message)
2109 struct PeerTrailSetupMessage *trail_setup;
2110 struct GNUNET_PeerIdentity *trail_peer_list;
2111 struct GNUNET_PeerIdentity next_destination;
2112 struct GNUNET_PeerIdentity *current_destination;
2113 struct GNUNET_PeerIdentity *next_hop;
2114 struct GNUNET_PeerIdentity next_peer;
2115 struct FriendInfo *target_friend;
2116 struct GNUNET_PeerIdentity source;
2117 uint64_t ultimate_destination_finger_value;
2118 struct GNUNET_HashCode new_intermediate_trail_id;
2119 struct GNUNET_HashCode intermediate_trail_id;
2120 struct GNUNET_HashCode new_trail_id;
2121 unsigned int finger_map_index;
2122 uint32_t trail_length;
2125 msize = ntohs (message->size);
2126 if (msize != sizeof (struct PeerTrailSetupMessage))
2128 GNUNET_break_op (0);
2132 trail_setup = (struct PeerTrailSetupMessage *) message;
2133 trail_length = ntohl (trail_setup->trail_length);
2134 if ((msize != sizeof (struct PeerTrailSetupMessage) +
2135 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2137 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2139 GNUNET_break_op (0);
2143 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
2144 current_destination = &trail_setup->next_destination;
2145 intermediate_trail_id = trail_setup->intermediate_trail_id;
2146 new_trail_id = trail_setup->new_trail_id;
2147 ultimate_destination_finger_value = GNUNET_ntohll (trail_setup->ultimate_destination_finger);
2148 source = trail_setup->source_peer;
2149 finger_map_index = ntohl (trail_setup->finger_map_index);
2151 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2153 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2154 GDS_NEIGHBOURS_send_trail_rejection (source, ultimate_destination_finger_value,
2155 my_identity, finger_map_index,
2156 trail_peer_list, trail_length,
2157 new_trail_id, target_friend,
2158 CONGESTION_TIMEOUT);
2162 next_hop = find_successor (ultimate_destination_finger_value, &next_destination,
2163 &new_intermediate_trail_id, finger_map_index);
2165 if (0 != (GNUNET_CRYPTO_cmp_peer_identity(&my_identity, current_destination)))
2167 struct GNUNET_PeerIdentity *closest_peer;
2168 struct GNUNET_PeerIdentity *peer1 =
2169 GDS_ROUTING_get_next_hop (intermediate_trail_id, GDS_ROUTING_SRC_TO_DEST);
2170 if (0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, next_hop))
2172 closest_peer = select_closest_peer (peer1, next_hop,
2173 ultimate_destination_finger_value,
2176 if (0 == GNUNET_CRYPTO_cmp_peer_identity (peer1, closest_peer) ||
2177 (0 == GNUNET_CRYPTO_cmp_peer_identity (peer1, next_hop)))
2180 next_destination = *current_destination;
2181 new_intermediate_trail_id = intermediate_trail_id;
2185 GNUNET_assert (NULL != next_hop);
2186 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
2188 if (0 == trail_length)
2189 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
2191 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
2193 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
2194 GDS_NEIGHBOURS_send_trail_setup_result (source,
2196 target_friend, trail_length,
2198 finger_map_index, new_trail_id);
2202 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
2204 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2205 peer_list[trail_length] = my_identity;
2206 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2207 GDS_NEIGHBOURS_send_trail_setup (source,
2208 ultimate_destination_finger_value,
2210 target_friend, trail_length + 1, peer_list,
2211 finger_map_index, new_trail_id,
2212 new_intermediate_trail_id);
2219 * Core handle for p2p trail construction result messages.
2221 * @param message message
2222 * @param peer peer identity this notification is about
2223 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2226 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2227 const struct GNUNET_MessageHeader *message)
2229 struct PeerTrailSetupResultMessage *trail_result;
2230 struct GNUNET_PeerIdentity *trail_peer_list;
2231 struct GNUNET_PeerIdentity destination_peer;
2232 struct GNUNET_PeerIdentity finger_identity;
2233 uint32_t trail_length;
2234 uint32_t finger_map_index;
2235 struct GNUNET_HashCode trail_id;
2238 msize = ntohs (message->size);
2239 if (msize != sizeof (struct PeerTrailSetupResultMessage))
2241 GNUNET_break_op (0);
2245 trail_result = (struct PeerTrailSetupResultMessage *) message;
2246 trail_length = ntohl (trail_result->trail_length);
2249 sizeof (struct PeerTrailSetupResultMessage) +
2250 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2252 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2254 GNUNET_break_op (0);
2258 finger_map_index = htonl (trail_result->finger_map_index);
2259 destination_peer = trail_result->destination_peer;
2260 finger_identity = trail_result->finger_identity;
2261 trail_id = trail_result->trail_id;
2262 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
2264 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer,
2267 finger_table_add (finger_identity, trail_peer_list,
2269 finger_map_index, trail_id);
2273 struct GNUNET_PeerIdentity next_hop;
2274 struct FriendInfo *target_friend;
2277 my_index = search_my_index(trail_peer_list, trail_length);
2278 if (my_index == GNUNET_SYSERR)
2281 return GNUNET_SYSERR;
2285 next_hop = trail_result->destination_peer;
2287 next_hop = trail_peer_list[my_index - 1];
2289 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2290 &(trail_result->finger_identity))))
2292 GDS_ROUTING_add (trail_id, &next_hop, peer);
2295 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2296 GDS_NEIGHBOURS_send_trail_setup_result (destination_peer, finger_identity,
2297 target_friend, trail_length, trail_peer_list,
2298 finger_map_index, trail_id);
2304 * Core handle for p2p verify successor messages.
2305 * @param cls closure
2306 * @param message message
2307 * @param peer peer identity this notification is about
2308 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2311 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2312 const struct GNUNET_MessageHeader *message)
2314 struct PeerVerifySuccessorMessage *vsm;
2315 struct GNUNET_PeerIdentity successor;
2316 struct GNUNET_PeerIdentity source_peer;
2317 struct GNUNET_PeerIdentity *next_hop;
2318 struct FriendInfo *target_friend;
2319 //struct FingerInfo *my_predecessor;
2320 //struct GNUNET_PeerIdentity *my_predecessor_trail;
2321 //unsigned int my_predecessor_trail_length;
2322 struct GNUNET_HashCode trail_id;
2325 msize = ntohs (message->size);
2326 if (msize != sizeof (struct PeerVerifySuccessorMessage))
2328 GNUNET_break_op (0);
2332 vsm = (struct PeerVerifySuccessorMessage *) message;
2333 source_peer = vsm->source_peer;
2334 successor = vsm->successor;
2335 trail_id = vsm->trail_id;
2337 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
2339 GNUNET_assert (NULL != (next_hop =
2340 GDS_ROUTING_get_next_hop (trail_id,
2341 GDS_ROUTING_SRC_TO_DEST)));
2342 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2343 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
2344 trail_id, target_friend);
2348 my_predecessor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2349 PREDECESSOR_FINGER_ID);
2350 if (NULL == my_predecessor) /* FIXME: not sure how to handle this case */
2353 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
2354 &(my_predecessor->finger_identity))))
2356 my_predecessor_trail = NULL;
2357 my_predecessor_trail_length = 0;
2361 /* FIXME: copy from my_predecessor trail. now we may have multiple routes
2362 choose the one with shortest length and send that one. */
2365 /* Here you are sending the result back along the trail through which the source
2366 peer send the message to you. now you have to specify the direction such
2367 that the trail id is used but now prev_hop is next_hop. */
2369 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
2370 my_predecessor->finger_identity,
2372 my_predecessor_trail,
2373 my_predecessor_trail_length,
2374 GDS_ROUTING_DEST_TO_SRC,
2382 * Core handle for p2p verify successor result messages.
2383 * @param cls closure
2384 * @param message message
2385 * @param peer peer identity this notification is about
2386 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2389 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2390 const struct GNUNET_MessageHeader *message)
2392 struct PeerVerifySuccessorResultMessage *vsrm;
2393 enum GDS_ROUTING_trail_direction trail_direction;
2394 struct GNUNET_HashCode trail_id;
2395 unsigned int successor_current_predecessor_trail_length;
2396 struct GNUNET_PeerIdentity *successor_current_predecessor_trail;
2397 struct GNUNET_PeerIdentity destination_peer;
2398 struct GNUNET_PeerIdentity my_new_successor;
2399 struct GNUNET_PeerIdentity *next_hop;
2400 struct FriendInfo *target_friend;
2403 msize = ntohs (message->size);
2404 if (msize != sizeof (struct PeerVerifySuccessorResultMessage))
2406 GNUNET_break_op (0);
2409 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
2410 successor_current_predecessor_trail_length = ntohl (vsrm->trail_length);
2411 trail_direction = ntohl (vsrm->trail_direction);
2412 trail_id = vsrm->trail_id;
2415 sizeof (struct PeerVerifySuccessorResultMessage) +
2416 successor_current_predecessor_trail_length *
2417 sizeof (struct GNUNET_PeerIdentity)) ||
2418 (successor_current_predecessor_trail_length >
2419 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2421 GNUNET_break_op (0);
2425 successor_current_predecessor_trail = (struct GNUNET_PeerIdentity *) &vsrm[1];
2426 destination_peer = vsrm->destination_peer;
2427 my_new_successor = vsrm->my_predecessor;
2429 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer, &my_identity)))
2434 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
2435 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2436 GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2437 vsrm->source_successor,
2438 my_new_successor, trail_id,
2439 successor_current_predecessor_trail,
2440 successor_current_predecessor_trail_length,
2441 trail_direction, target_friend);
2448 * Adapt it to use trail list array.
2449 * Core handle for p2p verify successor result messages.
2450 * @param cls closure
2451 * @param message message
2452 * @param peer peer identity this notification is about
2453 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2456 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2457 const struct GNUNET_MessageHeader *message)
2460 const struct PeerVerifySuccessorResultMessage *vsrm;
2461 unsigned int trail_length;
2462 struct GNUNET_HashCode trail_id;
2463 struct GNUNET_PeerIdentity *trail;
2464 struct FriendInfo *target_friend;
2465 struct GNUNET_PeerIdentity *next_hop;
2466 struct GNUNET_PeerIdentity destination_peer;
2467 struct GNUNET_PeerIdentity my_new_successor;
2468 struct FingerInfo *current_successor;
2469 struct GNUNET_HashCode old_successor_trail_id;
2472 msize = ntohs (message->size);
2473 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
2475 GNUNET_break_op (0);
2478 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
2479 trail_length = ntohl (vsrm->trail_length);
2480 trail_id = vsrm->trail_id;
2483 sizeof (struct PeerVerifySuccessorResultMessage) +
2484 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2486 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2488 GNUNET_break_op (0);
2492 trail = (struct GNUNET_PeerIdentity *) &vsrm[1];
2493 destination_peer = vsrm->destination_peer;
2494 my_new_successor = vsrm->my_predecessor;
2496 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer, &my_identity)))
2498 unsigned int *new_trail_length;
2499 struct GNUNET_PeerIdentity *new_trail;
2500 struct GNUNET_HashCode new_finger_trail_id;
2502 /* FIXME: generate a new_finger_trail_id */
2503 current_successor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap, 0);
2504 old_successor_trail_id = current_successor->head->trail_id;
2506 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2507 &(current_successor->head->head->peer));
2509 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_new_successor,
2510 ¤t_successor->finger_identity))
2512 *new_trail_length = 0;
2513 new_trail = update_trail_to_new_predecessor (current_successor,
2514 trail_length, trail,
2517 if (GNUNET_OK == finger_table_add (&my_new_successor, new_trail,
2518 new_trail_length , 0, new_finger_trail_id))
2521 *Here you should send a trail teardown message for old trail id
2522 and trail add for new trail. */
2524 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, my_new_successor,
2525 new_trail, new_trail_length,
2526 new_finger_trail_id, target_friend);
2530 next_hop = GDS_ROUTING_get_next_hop (trail_id);
2531 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2532 GDS_NEIGHBOURS_send_verify_successor_result (vsrm->destination_peer,
2533 vsrm->source_successor,
2534 vsrm->my_predecessor,
2535 vsrm->trail_id, trail,
2539 trail_length, target_friend);
2544 * Core handle for p2p notify new successor messages.
2545 * @param cls closure
2546 * @param message message
2547 * @param peer peer identity this notification is about
2548 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2551 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2552 const struct GNUNET_MessageHeader *message)
2554 /* Here we need to pass the whole trail to reach to new successor as we
2555 don't have that stored in our routing table. while passing through each
2556 peer we will have to add an entry. also when you are the destination and
2557 if you have added it back as pred, then you also need to add the trail in
2558 your own finger table and send add trail message to add this trail. you
2559 shoudl generate a new trail id. although they are same trails but you have
2560 to ahve different trail id. */
2566 * FIXME: Here you should keep the trail id with you.
2567 * Core handler for P2P trail rejection message
2568 * @param cls closure
2569 * @param message message
2570 * @param peer peer identity this notification is about
2571 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2574 handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
2575 const struct GNUNET_MessageHeader *message)
2577 struct PeerTrailRejectionMessage *trail_rejection;
2578 unsigned int trail_length;
2579 struct GNUNET_PeerIdentity *trail_peer_list;
2580 struct FriendInfo *target_friend;
2581 struct GNUNET_TIME_Relative congestion_timeout;
2582 struct GNUNET_HashCode trail_id;
2583 struct GNUNET_PeerIdentity next_destination;
2584 struct GNUNET_HashCode new_intermediate_trail_id;
2585 struct GNUNET_PeerIdentity next_peer;
2586 struct GNUNET_PeerIdentity source;
2587 struct GNUNET_PeerIdentity *next_hop;
2588 uint64_t ultimate_destination_finger_value;
2589 unsigned int finger_map_index;
2592 msize = ntohs (message->size);
2593 if (msize != sizeof (struct PeerTrailRejectionMessage))
2595 GNUNET_break_op (0);
2599 trail_rejection = (struct PeerTrailRejectionMessage *) message;
2600 trail_length = ntohl (trail_rejection->trail_length);
2602 if ((msize != sizeof (struct PeerTrailRejectionMessage) +
2603 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2605 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2607 GNUNET_break_op (0);
2611 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2612 finger_map_index = ntohl (trail_rejection->finger_map_index);
2613 congestion_timeout = trail_rejection->congestion_time;
2614 source = trail_rejection->source_peer;
2615 trail_id = trail_rejection->trail_id;
2616 ultimate_destination_finger_value =
2617 trail_rejection->ultimate_destination_finger_identity_value;
2619 /* First set the congestion time of the friend that sent you this message. */
2620 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2621 target_friend->congestion_duration = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
2622 congestion_timeout);
2624 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
2629 /* If I am congested then pass this message to peer before me in trail. */
2630 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
2632 struct GNUNET_PeerIdentity *new_trail;
2633 unsigned int new_trail_length;
2635 if (trail_length == 1)
2638 new_trail_length = 0;
2643 next_hop = &trail_peer_list[trail_length - 2];
2644 /* Remove myself from the trail. */
2645 new_trail_length = trail_length -1;
2646 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
2647 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
2650 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2651 GDS_NEIGHBOURS_send_trail_rejection (source,
2652 ultimate_destination_finger_value,
2653 my_identity, finger_map_index,
2654 new_trail,new_trail_length,trail_id,
2655 target_friend, CONGESTION_TIMEOUT);
2659 /* Look for next_hop to pass the trail setup message */
2660 next_hop = find_successor (ultimate_destination_finger_value,
2662 &new_intermediate_trail_id,
2665 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
2667 if (0 == trail_length)
2670 next_peer = trail_peer_list[trail_length-1];
2672 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
2673 GDS_NEIGHBOURS_send_trail_setup_result (source,
2675 target_friend, trail_length,
2677 finger_map_index, trail_id);
2681 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
2683 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2684 peer_list[trail_length] = my_identity;
2686 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2687 GDS_NEIGHBOURS_send_trail_setup (source,
2688 ultimate_destination_finger_value,
2690 target_friend, trail_length + 1, peer_list,
2691 finger_map_index, trail_id,
2692 new_intermediate_trail_id);
2699 * Core handle for p2p trail tear down messages.
2700 * @param cls closure
2701 * @param message message
2702 * @param peer peer identity this notification is about
2703 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2706 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
2707 const struct GNUNET_MessageHeader *message)
2709 struct PeerTrailCompressionMessage *trail_compression;
2710 struct GNUNET_PeerIdentity *next_hop;
2711 struct GNUNET_HashCode trail_id;
2712 struct FriendInfo *target_friend;
2715 msize = ntohs (message->size);
2716 if (msize != sizeof (struct PeerTrailCompressionMessage))
2718 GNUNET_break_op (0);
2722 trail_compression = (struct PeerTrailCompressionMessage *) message;
2723 trail_id = trail_compression->trail_id;
2725 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->new_first_friend),
2728 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->destination_peer),
2731 GDS_ROUTING_update_trail_prev_hop (trail_id,
2732 trail_compression->source_peer);
2737 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
2738 if (NULL == next_hop)
2740 GNUNET_break (0); /*FIXME: How to handle this case. */
2743 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
2744 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2745 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
2746 trail_compression->destination_peer,
2748 trail_compression->new_first_friend,
2755 * Core handler for trail teardown message.
2756 * @param cls closure
2757 * @param message message
2758 * @param peer peer identity this notification is about
2759 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2762 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
2763 const struct GNUNET_MessageHeader *message)
2770 * TRAIL ID and each peer should add an entry in the routing table.
2771 * Core handle for p2p add trail message.
2772 * @param cls closure
2773 * @param message message
2774 * @param peer peer identity this notification is about
2775 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2778 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
2779 const struct GNUNET_MessageHeader *message)
2786 *FIXME; call send_trail_teardown_message on all the trails of the finger that
2787 * you remove. Also you don't need to decerement friend trail count as that
2788 * friend is removed. But you can not send trail teardown message as the friend
2789 * is disconnected. then you don't have any next_hop. and in case there are
2790 * multiple trails. and friend is the first trail then you remove only the trail.
2791 * Iterate over finger_hashmap, and remove entries if finger is the disconnected
2792 * peer or if disconnected peer is the first friend in the trail to reach the
2794 * @param cls closure
2795 * @param key current public key
2796 * @param value value in the hash map
2797 * @return #GNUNET_YES if we should continue to
2799 * #GNUNET_NO if not.
2802 remove_matching_finger (void *cls,
2806 struct FingerInfo *remove_finger = value;
2807 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
2808 struct TrailList *trail_list;
2811 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
2814 GNUNET_assert (GNUNET_YES ==
2815 GNUNET_CONTAINER_multihashmap32_remove (finger_hashmap,
2818 free_finger (remove_finger);
2822 for (i = 0; i< remove_finger->trails_count; i++)
2824 trail_list = &remove_finger->trail_list[i];
2825 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_list->trail_head->peer,
2828 GNUNET_assert (GNUNET_YES ==
2829 GNUNET_CONTAINER_multihashmap32_remove (finger_hashmap,
2832 free_finger (remove_finger);
2841 * Method called whenever a peer disconnects.
2843 * @param cls closure
2844 * @param peer peer identity this notification is about
2847 handle_core_disconnect (void *cls,
2848 const struct GNUNET_PeerIdentity *peer)
2850 struct FriendInfo *remove_friend;
2852 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
2856 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2858 if (NULL == remove_friend)
2864 GNUNET_assert (GNUNET_SYSERR !=
2865 GNUNET_CONTAINER_multihashmap32_iterate (finger_hashmap,
2866 &remove_matching_finger,
2868 GDS_ROUTING_remove_trail_by_peer (peer);
2869 GNUNET_assert (GNUNET_YES ==
2870 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
2874 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
2877 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
2879 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
2880 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
2888 * Method called whenever a peer connects.
2890 * @param cls closure
2891 * @param peer_identity peer identity this notification is about
2894 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
2896 struct FriendInfo *friend;
2898 /* Check for connect to self message */
2899 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
2902 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
2904 /* If peer already exists in our friend_peermap, then exit. */
2905 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
2911 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
2914 friend = GNUNET_new (struct FriendInfo);
2915 friend->id = *peer_identity;
2917 GNUNET_assert (GNUNET_OK ==
2918 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
2919 peer_identity, friend,
2920 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
2922 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
2923 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
2924 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
2929 * To be called on core init/fail.
2931 * @param cls service closure
2932 * @param identity the public identity of this peer
2935 core_init (void *cls,
2936 const struct GNUNET_PeerIdentity *identity)
2938 my_identity = *identity;
2943 * Initialize neighbours subsystem.
2944 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2947 GDS_NEIGHBOURS_init (void)
2949 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
2950 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
2951 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
2952 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
2953 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
2954 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
2955 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
2956 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
2957 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
2958 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
2959 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION, 0},
2960 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
2961 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL, 0},
2966 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
2967 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
2968 GNUNET_NO, core_handlers);
2969 if (NULL == core_api)
2970 return GNUNET_SYSERR;
2972 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
2973 finger_hashmap = GNUNET_CONTAINER_multihashmap32_create (MAX_FINGERS * 4/3);
2979 * Shutdown neighbours subsystem.
2982 GDS_NEIGHBOURS_done (void)
2984 if (NULL == core_api)
2987 GNUNET_CORE_disconnect (core_api);
2990 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
2991 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
2992 friend_peermap = NULL;
2994 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap32_size (finger_hashmap));
2995 GNUNET_CONTAINER_multihashmap32_destroy (finger_hashmap);
2996 finger_hashmap = NULL;
2998 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3001 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3002 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3010 * @return my identity
3012 struct GNUNET_PeerIdentity
3013 GDS_NEIGHBOURS_get_my_id (void)