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 * Maximum number of trails that can go through a friend.
85 #define TRAIL_THROUGH_FRIEND_THRESHOLD 64
88 * Finger map index for predecessor entry in finger peermap.
90 #define PREDECESSOR_FINGER_ID 64
93 * Maximum number of trails allowed to go through a friend.
95 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
97 GNUNET_NETWORK_STRUCT_BEGIN
100 * P2P Trail setup message
102 struct PeerTrailSetupMessage
105 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
107 struct GNUNET_MessageHeader header;
110 * Peer closest to this value will be our finger.
112 uint64_t ultimate_destination_finger;
115 * Source peer which wants to setup the trail to one of its finger.
117 struct GNUNET_PeerIdentity source_peer;
120 * Peer to which this packet is forwarded.
122 struct GNUNET_PeerIdentity next_destination;
125 * Index into finger peer map, in Network Byte Order.
127 uint32_t finger_map_index;
130 * Number of entries in trail list, in Network Byte Order.
132 uint32_t trail_length GNUNET_PACKED;
135 * Trail id of any intermediate trail we may encounter while doing trail setup.
137 struct GNUNET_HashCode intermediate_trail_id;
140 * Trail id for trail which we are trying to setup.
142 struct GNUNET_HashCode new_trail_id;
144 /* Trail formed in the process. */
148 * P2P Trail Setup Result message
150 struct PeerTrailSetupResultMessage
154 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
156 struct GNUNET_MessageHeader header;
159 * Finger to which we have found the path.
161 struct GNUNET_PeerIdentity finger_identity;
164 * Peer which was looking for the trail to finger.
166 struct GNUNET_PeerIdentity destination_peer;
169 * Index into finger peer map in NBO.
171 uint32_t finger_map_index;
174 * Number of entries in trail list in NBO.
176 uint32_t trail_length GNUNET_PACKED;
179 * Identifier of the trail.
181 struct GNUNET_HashCode trail_id;
183 /* Trail from destination_peer to finger_identity */
187 * P2P Verify Successor Message.
189 struct PeerVerifySuccessorMessage
192 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
194 struct GNUNET_MessageHeader header;
197 * Source peer which wants to verify its successor.
199 struct GNUNET_PeerIdentity source_peer;
202 * My current successor.
204 struct GNUNET_PeerIdentity successor;
207 * Identifier of trail to reach from source_peer to successor.
209 struct GNUNET_HashCode trail_id;
212 * Total number of peers to reach from source to successor.
214 unsigned int trail_length;
220 * P2P Verify Successor Result Message
222 struct PeerVerifySuccessorResultMessage
225 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
227 struct GNUNET_MessageHeader header;
230 * Destination peer which sent the request to verify its successor.
232 struct GNUNET_PeerIdentity destination_peer;
235 * Successor to which PeerVerifySuccessorMessage was sent.
237 struct GNUNET_PeerIdentity source_successor;
240 * source_successor's predecessor
242 struct GNUNET_PeerIdentity my_predecessor;
245 * Trail identifier of trail from my_predecessor to source_successor.
247 struct GNUNET_HashCode trail_id;
250 * Direction in which we are looking at the trail.
252 enum GDS_ROUTING_trail_direction trail_direction;
255 * Total number of peers in trail from source_successor to my_predecessor
256 * if my_predecessor is not same as destination_peer.
258 uint32_t trail_length;
260 /* Trail from source_successor to my_predecessor where
261 * my_predecessor != destination_peer*/
265 * P2P Notify New Successor Message.
267 struct PeerNotifyNewSuccessorMessage
270 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
272 struct GNUNET_MessageHeader header;
275 * Source peer which wants to notify its new successor.
277 struct GNUNET_PeerIdentity source_peer;
280 * New successor identity.
282 struct GNUNET_PeerIdentity destination_peer;
285 * Total number of peers in trail from source_peer to destination_peer
287 unsigned int trail_length;
290 * Unique identifier of the trail.
292 struct GNUNET_HashCode trail_id;
298 * P2P Trail Compression Message.
300 struct PeerTrailCompressionMessage
303 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION
305 struct GNUNET_MessageHeader header;
308 * Source peer of this trail.
310 struct GNUNET_PeerIdentity source_peer;
313 * Destination of this trail.
315 struct GNUNET_PeerIdentity destination_peer;
318 * Trail from source_peer to destination_peer compressed such that
319 * new_first_friend is the first hop in the trail from source to
322 struct GNUNET_PeerIdentity new_first_friend;
325 * Unique identifier of trail.
327 struct GNUNET_HashCode trail_id;
332 * P2P Trail Tear Down message.
334 struct PeerTrailTearDownMessage
337 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
339 struct GNUNET_MessageHeader header;
342 * Source peer of the trail.
344 struct GNUNET_PeerIdentity source_peer;
347 * Destination peer of the trail.
349 struct GNUNET_PeerIdentity destination_peer;
352 * Unique identifier of the trail.
354 struct GNUNET_HashCode TRAIL_ID;
357 * Direction of trail.
359 enum GDS_ROUTING_trail_direction trail_direction;
364 * P2P Trail Rejection Message.
366 struct PeerTrailRejectionMessage
369 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
371 struct GNUNET_MessageHeader header;
374 * Source peer which wants to set up the trail.
376 struct GNUNET_PeerIdentity source_peer;
379 * Peer which sent trail rejection message.
381 struct GNUNET_PeerIdentity congested_peer;
384 * Peer identity which will be successor to this value will be finger of
387 uint64_t ultimate_destination_finger_identity_value;
390 * Index in finger peer map of source peer.
392 uint32_t finger_map_index;
395 * Total number of peers in the trail.
397 uint32_t trail_length;
400 * Identifier for the trail source peer is trying to setup.
402 struct GNUNET_HashCode trail_id;
404 * Relative time for which congested_peer will remain congested.
406 struct GNUNET_TIME_Relative congestion_time;
408 /* Trail_list from source_peer to peer which sent the message for trail setup
409 * to congested peer.*/
413 * P2P Add Trail Message.
415 struct PeerAddTrailMessage
418 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL
420 struct GNUNET_MessageHeader header;
423 * Source peer of the routing trail.
425 struct GNUNET_PeerIdentity source_peer;
428 * Destination peer of the routing trail.
430 struct GNUNET_PeerIdentity destination_peer;
433 * Total number of peers from source peer to destination peer.
435 unsigned int trail_length;
438 * Unique identifier of the trail.
440 struct GNUNET_HashCode trail_id;
442 /* Trail from source peer to destination peer. */
445 GNUNET_NETWORK_STRUCT_END
448 * Linked list of messages to send to a particular other peer.
450 struct P2PPendingMessage
453 * Pointer to next item in the list
455 struct P2PPendingMessage *next;
458 * Pointer to previous item in the list
460 struct P2PPendingMessage *prev;
463 * Message importance level. FIXME: used? useful?
465 unsigned int importance;
468 * When does this message time out?
470 struct GNUNET_TIME_Absolute timeout;
473 * Actual message to be sent, allocated at the end of the struct:
474 * // msg = (cast) &pm[1];
475 * // memcpy (&pm[1], data, len);
477 const struct GNUNET_MessageHeader *msg;
483 * Entry in friend_peermap.
490 struct GNUNET_PeerIdentity id;
493 * Number of trails for which this friend is the first hop.
495 unsigned int trails_count;
498 * Count of outstanding messages for this friend.
500 unsigned int pending_count;
503 * In case not 0, then amount of time for which this friend is congested.
505 struct GNUNET_TIME_Absolute congestion_duration;
508 * Head of pending messages to be sent to this friend.
510 struct P2PPendingMessage *head;
513 * Tail of pending messages to be sent to this friend.
515 struct P2PPendingMessage *tail;
518 * Core handle for sending messages to this friend.
520 struct GNUNET_CORE_TransmitHandle *th;
525 * An individual trail to reach to a finger.
530 * Pointer to next item in the list
535 * Pointer to prev item in the list
540 * An element in this trail.
542 struct GNUNET_PeerIdentity peer;
546 * List of all trails to reach a particular finger.
553 struct Trail *trail_head;
558 struct Trail *trail_tail;
561 * Unique identifier of this trail.
563 struct GNUNET_HashCode trail_id;
566 * Length of trail pointed
568 unsigned int trail_length;
571 * Number of trails that the first friend of this trail is a part of.
573 unsigned int first_friend_trail_count;
577 * An entry in finger_hashmap.
584 struct GNUNET_PeerIdentity finger_identity;
587 * Index in finger peer map
589 unsigned int finger_map_index;
592 * Number of trails setup so far for this finger.
594 unsigned int trails_count;
599 struct TrailList trail_list[MAXIMUM_TRAILS_PER_FINGER];
603 * Data structure to keep track of closest peer seen so far in find_successor()
608 * 64 bit value of the peer
613 * Trail id to reach to peer.
615 struct GNUNET_HashCode trail_id;
618 * First hop, NULL in case of friend and my_identity
620 struct GNUNET_PeerIdentity next_hop;
623 * Next destination. In case of friend and my_identity , it is same as next_hop
624 * In case of finger it is finger identity.
626 struct GNUNET_PeerIdentity next_destination;
630 * Data structure to store the trail chosen to reach to finger.
635 * First friend in the trail to reach finger.
637 struct FriendInfo friend;
640 * Identifier of this trail.
642 struct GNUNET_HashCode trail_id;
645 * Total number of peers in this trail.
647 unsigned int trail_length;
651 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
652 * get our first friend.
654 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
657 * Identity of this peer.
659 static struct GNUNET_PeerIdentity my_identity;
662 * Peer map of all the friends of a peer
664 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
667 * Hash map of all the fingers of a peer
669 static struct GNUNET_CONTAINER_MultiHashMap32 *finger_hashmap;
674 static struct GNUNET_CORE_Handle *core_api;
677 * The current finger index that we have want to find trail to. We start the
678 * search with value = 0, i.e. successor peer and then go to PREDCESSOR_FINGER_ID
679 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
680 * we reset this index to 0.
682 static unsigned int current_search_finger_index;
686 * Called when core is ready to send a message we asked for
687 * out to the destination.
689 * @param cls the 'struct FriendInfo' of the target friend
690 * @param size number of bytes available in buf
691 * @param buf where the callee should write the message
692 * @return number of bytes written to buf
695 core_transmit_notify (void *cls, size_t size, void *buf)
697 struct FriendInfo *peer = cls;
699 struct P2PPendingMessage *pending;
704 while ((NULL != (pending = peer->head)) &&
705 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
707 peer->pending_count--;
708 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
709 GNUNET_free (pending);
713 /* no messages pending */
719 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
720 GNUNET_CORE_PRIO_BEST_EFFORT,
721 GNUNET_TIME_absolute_get_remaining
722 (pending->timeout), &peer->id,
723 ntohs (pending->msg->size),
724 &core_transmit_notify, peer);
725 GNUNET_break (NULL != peer->th);
729 while ((NULL != (pending = peer->head)) &&
730 (size - off >= (msize = ntohs (pending->msg->size))))
732 GNUNET_STATISTICS_update (GDS_stats,
734 ("# Bytes transmitted to other peers"), msize,
736 memcpy (&cbuf[off], pending->msg, msize);
738 peer->pending_count--;
739 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
740 GNUNET_free (pending);
742 if (peer->head != NULL)
745 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
746 GNUNET_CORE_PRIO_BEST_EFFORT,
747 GNUNET_TIME_absolute_get_remaining
748 (pending->timeout), &peer->id, msize,
749 &core_transmit_notify, peer);
750 GNUNET_break (NULL != peer->th);
758 * FIXME: assertion fails at the end of this function. also in core_api.c at 1299.
759 * Transmit all messages in the friend's message queue.
761 * @param peer message queue to process
764 process_friend_queue (struct FriendInfo *peer)
766 struct P2PPendingMessage *pending;
768 if (NULL == (pending = peer->head))
770 if (NULL != peer->th)
773 GNUNET_STATISTICS_update (GDS_stats,
775 ("# Bytes of bandwidth requested from core"),
776 ntohs (pending->msg->size), GNUNET_NO);
779 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
781 GNUNET_TIME_absolute_get_remaining
782 (pending->timeout), &peer->id,
783 ntohs (pending->msg->size),
784 &core_transmit_notify, peer);
785 GNUNET_break (NULL != peer->th);
790 * Construct a trail setup message and forward it to target_friend
791 * @param source_peer Source peer which wants to setup the trail
792 * @param ultimate_destination_finger Peer identity closest to this value will
793 * be finger to @a source_peer
794 * @param next_destination Peer which should get the packet. I can be same as
795 * target_friend or different.
796 * @param target_friend Friend to which message is forwarded now.
797 * @param trail_length Total number of peers in trail setup so far.
798 * @param trail_peer_list Trail setup so far
799 * @param finger_map_index Index in finger map for which we are looking for finger.
800 * @param trail_id Unique identifier for the trail we are trying to setup.
801 * @param intermediate_trail_id Trail id of any intermediate trail we may have to
802 * traverse during trail setup. If not used then set to
806 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity source_peer,
807 uint64_t ultimate_destination_finger,
808 struct GNUNET_PeerIdentity next_destination,
809 struct FriendInfo *target_friend,
810 unsigned int trail_length,
811 const struct GNUNET_PeerIdentity *trail_peer_list,
812 unsigned int finger_map_index,
813 struct GNUNET_HashCode new_trail_id,
814 struct GNUNET_HashCode intermediate_trail_id)
816 struct P2PPendingMessage *pending;
817 struct PeerTrailSetupMessage *tsm;
818 struct GNUNET_PeerIdentity *peer_list;
821 msize = sizeof (struct PeerTrailSetupMessage) +
822 (trail_length * sizeof (struct GNUNET_PeerIdentity));
824 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
830 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
832 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
836 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
837 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
838 tsm = (struct PeerTrailSetupMessage *) &pending[1];
839 pending->msg = &tsm->header;
840 tsm->header.size = htons (msize);
841 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
842 tsm->ultimate_destination_finger = GNUNET_htonll (ultimate_destination_finger);
843 tsm->source_peer = source_peer;
844 tsm->next_destination = next_destination;
845 tsm->trail_length = htonl (trail_length);
846 tsm->finger_map_index = htonl (finger_map_index);
847 tsm->new_trail_id = new_trail_id;
848 tsm->intermediate_trail_id = intermediate_trail_id;
849 if (trail_length > 0)
851 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
852 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
855 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
856 target_friend->pending_count++;
857 process_friend_queue (target_friend);
862 * Construct a trail setup result message and forward it to target friend.
863 * @param destination_peer Peer which will get the trail to one of its finger.
864 * @param source_finger Peer to which the trail has been setup to.
865 * @param target_friend Friend to which this message should be forwarded.
866 * @param trail_length Numbers of peers in the trail.
867 * @param trail_peer_list Peers which are part of the trail from source to destination.
868 * @param finger_map_index Index in finger peer map
869 * @param trail_id Unique identifier of the trail.
872 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity destination_peer,
873 struct GNUNET_PeerIdentity source_finger,
874 struct FriendInfo *target_friend,
875 unsigned int trail_length,
876 const struct GNUNET_PeerIdentity *trail_peer_list,
877 unsigned int finger_map_index,
878 struct GNUNET_HashCode trail_id)
880 struct P2PPendingMessage *pending;
881 struct PeerTrailSetupResultMessage *tsrm;
882 struct GNUNET_PeerIdentity *peer_list;
885 msize = sizeof (struct PeerTrailSetupResultMessage) +
886 (trail_length * sizeof (struct GNUNET_PeerIdentity));
888 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
894 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
896 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
900 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
901 pending->importance = 0;
902 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
903 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
904 pending->msg = &tsrm->header;
905 tsrm->header.size = htons (msize);
906 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
907 tsrm->destination_peer = destination_peer;
908 tsrm->finger_identity = source_finger;
909 tsrm->trail_length = htonl (trail_length);
910 tsrm->finger_map_index = htonl (finger_map_index);
911 tsrm->trail_id = trail_id;
913 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
914 if (trail_length > 0)
916 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
918 /* Send the message to chosen friend. */
919 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
920 target_friend->pending_count++;
921 process_friend_queue (target_friend);
926 * Send trail rejection message to next_hop
927 * @param source_peer Source peer which is trying to setup the trail.
928 * @param finger_identity Peer closest to this value will be @a source_peer's finger
929 * @param congested_peer Peer which sent this message as it is congested.
930 * @param next_hop Peer to which we are forwarding this message.
931 * @param finger_map_index Index in finger peermap for which we are searching for finger.
932 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
934 * @param trail_length Total number of peers in trail_peer_list
935 * @param trail_id Unique identifier of this trail.
936 * @param congestion_timeout Duration given by congested peer as an estimate of
937 * how long it may remain congested.
940 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
941 uint64_t finger_identity,
942 struct GNUNET_PeerIdentity congested_peer,
943 unsigned int finger_map_index,
944 struct GNUNET_PeerIdentity *trail_peer_list,
945 unsigned int trail_length,
946 struct GNUNET_HashCode trail_id,
947 struct FriendInfo *target_friend,
948 const struct GNUNET_TIME_Relative congestion_timeout)
950 struct PeerTrailRejectionMessage *trm;
951 struct P2PPendingMessage *pending;
952 struct GNUNET_PeerIdentity *peer_list;
955 msize = sizeof (struct PeerTrailRejectionMessage) +
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;
972 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
973 trm = (struct PeerTrailRejectionMessage *)&pending[1];
974 pending->msg = &trm->header;
975 trm->header.size = htons (msize);
976 trm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION);
977 trm->source_peer = source_peer;
978 trm->congested_peer = congested_peer;
979 trm->congestion_time = congestion_timeout;
980 trm->finger_map_index = htonl (finger_map_index);
981 trm->trail_id = trail_id;
983 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
984 if (trail_length > 0)
986 memcpy (peer_list, trail_peer_list, 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);
996 * Construct a verify successor message and forward it to target_friend.
997 * @param source_peer Peer which wants to verify its successor.
998 * @param successor Peer which is @a source_peer's current successor.
999 * @param trail_id Identifier of trail to reach successor.
1000 * @param trail Trail to reach from source_peer to successor
1001 * @param trail_length Total number of peers in @a trail.
1002 * @param target_friend Message send to this friend.
1005 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1006 struct GNUNET_PeerIdentity successor,
1007 const struct GNUNET_HashCode trail_id,
1008 struct GNUNET_PeerIdentity *trail,
1009 unsigned int trail_length,
1010 struct FriendInfo *target_friend)
1012 struct PeerVerifySuccessorMessage *vsm;
1013 struct P2PPendingMessage *pending;
1014 struct GNUNET_PeerIdentity *peer_list;
1017 msize = sizeof (struct PeerVerifySuccessorMessage);
1018 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1024 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1026 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1030 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1031 pending->importance = 0; /* FIXME */
1032 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1033 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1034 pending->msg = &vsm->header;
1035 vsm->header.size = htons (msize);
1036 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1037 vsm->source_peer = source_peer;
1038 vsm->successor = successor;
1039 vsm->trail_id = trail_id;
1040 vsm->trail_length = htonl (trail_length);
1042 if (trail_length > 0)
1044 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1045 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1048 /* Send the message to chosen friend. */
1049 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1050 target_friend->pending_count++;
1051 process_friend_queue (target_friend);
1056 * Construct a trail teardown message and send it to target_friend
1057 * @param source_peer Source of the trail.
1058 * @param destination_peer Destination of the trail.
1059 * @param trail_id Unique identifier of the trail.
1060 * @param trail_direction Direction of trail.
1061 * @param target_friend Friend to get this message.
1064 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_PeerIdentity source_peer,
1065 struct GNUNET_PeerIdentity destination_peer,
1066 struct GNUNET_HashCode trail_id,
1067 enum GDS_ROUTING_trail_direction trail_direction,
1068 struct FriendInfo *target_friend)
1070 struct PeerTrailTearDownMessage *ttdm;
1071 struct P2PPendingMessage *pending;
1074 msize = sizeof (struct PeerTrailTearDownMessage);
1076 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1082 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1084 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1088 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1089 pending->importance = 0; /* FIXME */
1090 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1091 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1092 pending->msg = &ttdm->header;
1093 ttdm->header.size = htons (msize);
1094 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1095 ttdm->source_peer = source_peer;
1096 ttdm->destination_peer = destination_peer;
1097 ttdm->TRAIL_ID = trail_id;
1098 ttdm->trail_direction = htonl (trail_direction);
1100 /* Send the message to chosen friend. */
1101 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1102 target_friend->pending_count++;
1103 process_friend_queue (target_friend);
1108 * Construct a verify successor message and send it to target_friend
1109 * @param destination_peer
1110 * @param source_successor
1111 * @param succ_predecessor
1114 * @param trail_length
1115 * @param target_friend
1118 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity destination_peer,
1119 struct GNUNET_PeerIdentity source_successor,
1120 struct GNUNET_PeerIdentity succ_predecessor,
1121 struct GNUNET_HashCode trail_id,
1122 const struct GNUNET_PeerIdentity *trail,
1123 unsigned int trail_length,
1124 enum GDS_ROUTING_trail_direction trail_direction,
1125 struct FriendInfo *target_friend)
1127 struct PeerVerifySuccessorResultMessage *vsmr;
1128 struct P2PPendingMessage *pending;
1129 struct GNUNET_PeerIdentity *peer_list;
1132 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1133 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1135 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1141 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1143 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1147 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1148 pending->importance = 0; /* FIXME */
1149 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1150 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1151 pending->msg = &vsmr->header;
1152 vsmr->header.size = htons (msize);
1153 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1154 vsmr->destination_peer = destination_peer;
1155 vsmr->my_predecessor = succ_predecessor;
1156 vsmr->source_successor = source_successor;
1157 vsmr->trail_direction = htonl (trail_direction);
1159 if (trail_length > 0)
1161 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1162 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1165 /* Send the message to chosen friend. */
1166 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1167 target_friend->pending_count++;
1168 process_friend_queue (target_friend);
1173 * Construct a notify new successor message and send it to target_friend
1174 * @param source_peer
1175 * @param new_successor
1176 * @param new_successor_trail
1177 * @param new_successor_trail_length
1178 * @param new_succesor_trail_id
1181 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1182 struct GNUNET_PeerIdentity new_successor,
1183 struct GNUNET_PeerIdentity *new_successor_trail,
1184 unsigned int new_successor_trail_length,
1185 struct GNUNET_HashCode new_succesor_trail_id,
1186 struct FriendInfo *target_friend)
1188 struct PeerNotifyNewSuccessorMessage *nsm;
1189 struct P2PPendingMessage *pending;
1190 struct GNUNET_PeerIdentity *peer_list;
1193 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1194 (new_successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1196 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1202 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1204 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1208 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1209 pending->importance = 0; /* FIXME */
1210 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1211 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1212 pending->msg = &nsm->header;
1213 nsm->header.size = htons (msize);
1214 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1215 nsm->source_peer = source_peer;
1216 nsm->destination_peer = new_successor;
1217 nsm->trail_length = htonl (new_successor_trail_length);
1218 nsm->trail_id = new_succesor_trail_id;
1219 if (new_successor_trail_length > 0)
1221 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1222 memcpy (peer_list, new_successor_trail,
1223 new_successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1226 /* Send the message to chosen friend. */
1227 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1228 target_friend->pending_count++;
1229 process_friend_queue (target_friend);
1234 * Construct an add_trail message and send it to target_friend
1235 * @param source_peer Source of the trail.
1236 * @param destination_peer Destination of the trail.
1237 * @param trail_id Unique identifer of the trail
1238 * @param trail Trail from @a source_peer to @a destination_peer
1239 * @param trail_length Total number of peers in @a trail.
1240 * @param target_friend Next peer to get this message.
1243 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1244 struct GNUNET_PeerIdentity destination_peer,
1245 struct GNUNET_HashCode trail_id,
1246 struct GNUNET_PeerIdentity *trail,
1247 unsigned int trail_length,
1248 struct FriendInfo *target_friend)
1250 struct PeerAddTrailMessage *adm;
1251 struct GNUNET_PeerIdentity *peer_list;
1252 struct P2PPendingMessage *pending;
1255 msize = sizeof (struct PeerAddTrailMessage) +
1256 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1258 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1264 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1266 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1270 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1271 pending->importance = 0; /* FIXME */
1272 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1273 adm = (struct PeerAddTrailMessage *) &pending[1];
1274 pending->msg = &adm->header;
1275 adm->header.size = htons (msize);
1276 adm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL);
1277 adm->source_peer = source_peer;
1278 adm->destination_peer = destination_peer;
1279 adm->trail_length = htonl (trail_length);
1280 adm->trail_id = trail_id;
1282 if (trail_length > 0)
1284 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1285 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1288 /* Send the message to chosen friend. */
1289 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1290 target_friend->pending_count++;
1291 process_friend_queue (target_friend);
1297 * Construct a trail compression message and send it to target_friend.
1298 * @param source_peer Source of the trail.
1299 * @param destination_finger Destination of trail.
1300 * @param trail_id Unique identifier of trail.
1301 * @param first_friend First hop in compressed trail to reach from source to finger
1302 * @param target_friend Next friend to get this message.
1305 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1306 struct GNUNET_PeerIdentity destination_peer,
1307 struct GNUNET_HashCode trail_id,
1308 struct GNUNET_PeerIdentity first_friend,
1309 struct FriendInfo *target_friend)
1311 struct P2PPendingMessage *pending;
1312 struct PeerTrailCompressionMessage *tcm;
1315 msize = sizeof (struct PeerTrailCompressionMessage);
1317 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1323 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1325 GNUNET_STATISTICS_update (GDS_stats,
1326 gettext_noop ("# P2P messages dropped due to full queue"),
1330 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1331 pending->importance = 0; /* FIXME */
1332 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1333 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1334 pending->msg = &tcm->header;
1335 tcm->header.size = htons (msize);
1336 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION);
1337 tcm->source_peer = source_peer;
1338 tcm->new_first_friend = first_friend;
1339 tcm->trail_id = trail_id;
1340 tcm->destination_peer = destination_peer;
1342 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1343 target_friend->pending_count++;
1344 process_friend_queue (target_friend);
1350 * Seach my location in trail.
1351 * @param trail List of peers
1352 * @return my_index if found
1353 * #GNUNET_SYSERR if no entry found.
1356 search_my_index (const struct GNUNET_PeerIdentity *trail,
1361 for (i = 0; i < trail_length; i++)
1363 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1367 return GNUNET_SYSERR;
1372 * Iterate over the list of all the trails to reach Finger. In case the first
1373 * friend to reach the finger has crossed the trail threshold or is congested,
1374 * then don't select it. In case there multiple available good trails to reach
1375 * to Finger, choose the one with shortest trail length.
1376 * @param finger Finger
1377 * @return struct Correct_Trail which contains the first friend , trail id
1378 * and trail length. NULL in case none of the trails are free.
1380 static struct Correct_Trail *
1381 select_trail_to_finger (struct FingerInfo *finger)
1383 struct FriendInfo *friend;
1384 struct TrailList *iterator;
1385 struct Correct_Trail *finger_trail;
1388 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1392 finger_trail = GNUNET_new (struct Correct_Trail);
1394 for (i = 0; i < finger->trails_count; i++)
1396 iterator = &finger->trail_list[i];
1397 if (iterator->trail_length > 0)
1399 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1400 &iterator->trail_head->peer);
1404 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1405 &finger->finger_identity);
1408 if ((friend->trails_count < TRAIL_THROUGH_FRIEND_THRESHOLD)||
1409 ((0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us)))
1411 if (iterator->trail_length == 0)
1413 finger_trail->friend = *friend;
1414 //finger_trail->trail_id = 0;
1415 finger_trail->trail_length = 0;
1416 return finger_trail;
1419 if (finger_trail->trail_length > iterator->trail_length)
1421 finger_trail->friend = *friend;
1422 finger_trail->trail_id = iterator->trail_id;
1423 finger_trail->trail_length = iterator->trail_length;
1428 return finger_trail;
1433 * Select closest finger to value.
1434 * @param peer1 First peer
1435 * @param peer2 Second peer
1436 * @param value Value to be compare
1437 * @return Closest peer
1439 static struct GNUNET_PeerIdentity *
1440 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1441 struct GNUNET_PeerIdentity *peer2,
1444 uint64_t peer1_value;
1445 uint64_t peer2_value;
1447 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1448 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1450 if ((peer1_value <= value) && (value <= peer2_value))
1452 else if ((peer2_value <= value) && (value <= peer1_value))
1454 else if ((peer1_value <= peer2_value) && (peer2_value <= value))
1456 else if ((peer2_value <= peer1_value) && (peer1_value <= value))
1458 else if ((value <= peer1_value) && (peer1_value <= peer2_value))
1460 else /*if ((value <= peer2_value) && (peer2_value <= peer1_value))*/
1466 * Select closest predecessor to value.
1467 * @param peer1 First peer
1468 * @param peer2 Second peer
1469 * @param value Value to be compare
1470 * @return Closest peer
1472 static struct GNUNET_PeerIdentity *
1473 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1474 struct GNUNET_PeerIdentity *peer2,
1477 uint64_t peer1_value;
1478 uint64_t peer2_value;
1480 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1481 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1483 if ((peer1_value <= value) && (value <= peer2_value))
1485 else if ((peer2_value <= value) && (value <= peer1_value))
1487 else if ((peer1_value <= peer2_value) && (peer2_value <= value))
1489 else if ((peer2_value <= peer1_value) && (peer1_value <= value))
1491 else if ((value <= peer1_value) && (peer1_value <= peer2_value))
1493 else /*if ((value <= peer2_value) && (peer2_value <= peer1_value))*/
1499 * Select the closest peer among two peers (which should not be same)
1500 * with respect to value and finger_map_index
1501 * @param peer1 First peer
1502 * @param peer2 Second peer
1503 * @param value Value relative to which we find the closest
1504 * @param finger_map_index Index in finger map. If equal to PREDECESSOR_FINGER_ID,
1505 * then we use different logic than other
1507 * @return Closest peer among two peers.
1509 static struct GNUNET_PeerIdentity *
1510 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1511 struct GNUNET_PeerIdentity *peer2,
1513 unsigned int finger_map_index)
1515 struct GNUNET_PeerIdentity *closest_peer;
1517 if (PREDECESSOR_FINGER_ID == finger_map_index)
1518 closest_peer = select_closest_predecessor (peer1, peer2, value);
1520 closest_peer = select_closest_finger (peer1, peer2, value);
1522 return closest_peer;
1527 * Find the successor for destination_finger_value among my_identity, all my
1528 * friend and all my fingers. Don't consider friends/ fingers with first friend in
1529 * the trail which are congested or have crossed the threshold.
1530 * @param destination_finger_value Peer closest to this value will be the next successor.
1531 * @param next_destination [out] Updated to friend identity in case a friend is
1532 * successor, updated to first friend to reach to finger
1533 * in case finger is the destination.
1534 * @param new_intermediate_trail_id [out] In case we finger is the @a next_destination,
1535 * then we updated the field with trail id to reach
1537 * @param finger_map_index Index in finger peermap for which we are looking for a finger.
1540 static struct GNUNET_PeerIdentity *
1541 find_successor (uint64_t destination_finger_value,
1542 struct GNUNET_PeerIdentity *next_destination,
1543 struct GNUNET_HashCode *new_intermediate_trail_id,
1544 unsigned int finger_map_index)
1546 struct Closest_Peer *successor;
1547 struct GNUNET_PeerIdentity *next_hop;
1548 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1549 struct GNUNET_CONTAINER_MultiHashMap32Iterator *finger_iter;
1550 struct GNUNET_PeerIdentity *closest_peer;
1551 struct Correct_Trail *finger_trail;
1552 struct FriendInfo *friend;
1553 struct FingerInfo *finger;
1556 successor = GNUNET_new (struct Closest_Peer);
1557 memcpy (&successor->value, &my_identity, sizeof (uint64_t));
1558 //successor->trail_id = 0;
1559 successor->next_hop = my_identity;
1560 successor->next_destination = my_identity;
1562 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1563 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1565 GNUNET_assert (GNUNET_YES ==
1566 GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter, NULL,
1567 (const void **)&friend));
1568 if ((friend->trails_count > TRAIL_THROUGH_FRIEND_THRESHOLD)||
1569 (0 != GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us))
1572 closest_peer = select_closest_peer (&my_identity, &friend->id,
1573 destination_finger_value,
1575 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, &friend->id))
1577 memcpy (&successor->value, &friend->id, sizeof (uint64_t));
1578 //successor->trail_id = 0;
1579 successor->next_hop = friend->id;
1580 successor->next_destination = friend->id;
1584 finger_iter = GNUNET_CONTAINER_multihashmap32_iterator_create (finger_hashmap);
1585 for (i = 0; i < GNUNET_CONTAINER_multihashmap32_size (finger_hashmap); i++)
1587 GNUNET_assert (GNUNET_YES ==
1588 GNUNET_CONTAINER_multihashmap32_iterator_next (finger_iter, NULL,
1590 finger_trail = select_trail_to_finger (finger);
1591 if (NULL == finger_trail)
1594 closest_peer = select_closest_peer (&my_identity,
1595 &finger->finger_identity,
1596 destination_finger_value,
1598 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
1599 &finger->finger_identity))
1601 memcpy (&successor->value, &finger->finger_identity, sizeof (uint64_t));
1602 successor->trail_id = finger_trail->trail_id;
1603 successor->next_hop = finger_trail->friend.id;
1604 successor->next_destination = finger->finger_identity;
1608 next_destination = &successor->next_destination;
1609 new_intermediate_trail_id = &successor->trail_id;
1610 next_hop = &successor->next_hop;
1616 * Construct a Put message and send it to target_peer.
1617 * @param key Key for the content
1618 * @param block_type Type of the block
1619 * @param options Routing options
1620 * @param desired_replication_level Desired replication count
1621 * @param current_destination Next current destination which will get this message.
1622 * @param current_source Source for @a current_destination
1623 * @param target_peer Peer to which this message will be forwarded.
1624 * @param hop_count Number of hops traversed so far.
1625 * @param put_path_length Total number of peers in @a put_path
1626 * @param put_path Number of peers traversed so far
1627 * @param expiration_time When does the content expire
1628 * @param data Content to store
1629 * @param data_size Size of content @a data in bytes
1632 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
1633 enum GNUNET_BLOCK_Type block_type,
1634 enum GNUNET_DHT_RouteOption options,
1635 uint32_t desired_replication_level,
1636 struct GNUNET_PeerIdentity current_destination,
1637 struct GNUNET_PeerIdentity current_source,
1638 struct GNUNET_PeerIdentity *target_peer,
1640 uint32_t put_path_length,
1641 struct GNUNET_PeerIdentity *put_path,
1642 struct GNUNET_TIME_Absolute expiration_time,
1643 const void *data, size_t data_size)
1649 * Construct a Get message and send it to target_peer.
1650 * @param key Key for the content
1651 * @param block_type Type of the block
1652 * @param options Routing options
1653 * @param desired_replication_level Desired replication count
1654 * @param current_destination Next current destination which will get this message.
1655 * @param current_source Source for @a current_destination
1656 * @param target_peer Peer to which this message will be forwarded.
1657 * @param hop_count Number of hops traversed so far.
1658 * @param data Content to store
1659 * @param data_size Size of content @a data in bytes
1660 * @param get_path_length Total number of peers in @a get_path
1661 * @param get_path Number of peers traversed so far
1664 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
1665 enum GNUNET_BLOCK_Type block_type,
1666 enum GNUNET_DHT_RouteOption options,
1667 uint32_t desired_replication_level,
1668 struct GNUNET_PeerIdentity current_destination,
1669 struct GNUNET_PeerIdentity current_source,
1670 struct GNUNET_PeerIdentity *target_peer,
1672 uint32_t get_path_length,
1673 struct GNUNET_PeerIdentity *get_path)
1680 * Send the get result to requesting client.
1681 * @param key Key of the requested data.
1682 * @param type Block type
1683 * @param target_peer Next peer to forward the message to.
1684 * @param source_peer Peer which has the data for the key.
1685 * @param put_path_length Number of peers in @a put_path
1686 * @param put_path Path taken to put the data at its stored location.
1687 * @param get_path_length Number of peers in @a get_path
1688 * @param get_path Path taken to reach to the location of the key.
1689 * @param expiration When will this result expire?
1690 * @param data Payload to store
1691 * @param data_size Size of the @a data
1694 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
1695 enum GNUNET_BLOCK_Type type,
1696 struct GNUNET_PeerIdentity *target_peer,
1697 struct GNUNET_PeerIdentity *source_peer,
1698 unsigned int put_path_length,
1699 const struct GNUNET_PeerIdentity *put_path,
1700 unsigned int get_path_length,
1701 struct GNUNET_PeerIdentity *get_path,
1702 struct GNUNET_TIME_Absolute expiration,
1703 const void *data, size_t data_size)
1710 * Randomly choose one of your friends (which is not congested and have not crossed
1711 * trail threshold) from the friends_peer map
1712 * @return Friend Randomly chosen friend.
1713 * NULL in case friend peermap is empty, or all the friends are either
1714 * congested or have crossed trail threshold.
1716 static struct FriendInfo *
1717 select_random_friend ()
1719 unsigned int current_size;
1722 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1723 struct GNUNET_PeerIdentity key_ret;
1724 struct FriendInfo *friend;
1726 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1727 if (0 == current_size)
1730 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1731 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1733 for (j = 0; j < index ; j++)
1734 GNUNET_assert (GNUNET_YES ==
1735 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
1738 if (j == current_size)
1741 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1742 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1745 GNUNET_assert (GNUNET_YES ==
1746 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
1748 (const void **)&friend));
1751 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1752 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us))
1758 } while (j != index);
1760 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1766 * Compute finger_identity to which we want to setup the trail
1767 * @return finger_identity
1770 compute_finger_identity()
1774 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1775 my_id64 = GNUNET_ntohll (my_id64);
1776 return (my_id64 + (unsigned long) pow (2, current_search_finger_index));
1781 * Compute immediate predecessor identity in the network.
1782 * @return peer identity of immediate predecessor.
1785 compute_predecessor_identity()
1789 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1790 my_id64 = GNUNET_ntohll (my_id64);
1791 return (my_id64 -1);
1796 * Choose a random friend and start looking for the trail to reach to
1797 * finger identity through this random friend.
1799 * @param cls closure for this task
1800 * @param tc the context under which the task is running
1803 send_find_finger_trail_message (void *cls,
1804 const struct GNUNET_SCHEDULER_TaskContext *tc)
1806 struct FriendInfo *target_friend;
1807 struct GNUNET_TIME_Relative next_send_time;
1808 struct GNUNET_HashCode trail_id;
1809 uint64_t trail_id_value;
1810 struct GNUNET_HashCode intermediate_trail_id;
1811 unsigned int finger_map_index;
1812 uint64_t finger_identity;
1814 next_send_time.rel_value_us =
1815 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1816 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1817 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1818 find_finger_trail_task =
1819 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1822 target_friend = select_random_friend ();
1823 if (NULL == target_friend)
1828 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
1830 finger_identity = compute_predecessor_identity();
1834 finger_identity = compute_finger_identity();
1837 finger_map_index = current_search_finger_index;
1839 trail_id_value = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_STRONG, UINT64_MAX);
1840 memcpy (&trail_id, &trail_id_value, sizeof (struct GNUNET_HashCode));
1841 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_identity,
1842 target_friend->id, target_friend, 0, NULL,
1843 finger_map_index, trail_id, intermediate_trail_id);
1848 * In case there are already maximum number of possible trail to reach to a finger,
1849 * then check if the new trail's length is lesser than any of the existing trails.
1850 * If yes then replace that old trail by new trail.
1851 * Note: Here we are taking length as a parameter to choose the best possible trail,
1852 * but there could be other parameters also like - 1. duration of existence of a
1853 * trail - older the better. 2. if the new trail is completely disjoint than the
1854 * other trails, then may be choosing it is better.
1855 * @param existing_finger
1856 * @param new_finger_trail
1857 * @param new_finger_trail_length
1858 * @param new_finger_trail_id
1861 select_and_replace_trail (struct FingerInfo *existing_finger,
1862 struct GNUNET_PeerIdentity *new_trail,
1863 unsigned int new_trail_length,
1864 struct GNUNET_HashCode new_trail_id)
1866 struct TrailList *trail_list_iterator;
1867 unsigned int largest_trail_length;
1868 unsigned int largest_trail_index;
1869 struct Trail *trail_element;
1872 largest_trail_length = new_trail_length;
1873 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
1875 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
1877 for (i = 0; i < existing_finger->trails_count; i++)
1879 trail_list_iterator = &existing_finger->trail_list[i];
1880 if (trail_list_iterator->trail_length > largest_trail_length)
1882 largest_trail_length = trail_list_iterator->trail_length;
1883 largest_trail_index = i;
1887 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
1890 /* Send trail teardown message across the replaced trail. */
1891 struct TrailList *replace_trail = &existing_finger->trail_list[largest_trail_index];
1892 struct FriendInfo *target_friend =
1893 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1894 &replace_trail->trail_head->peer);
1896 GDS_NEIGHBOURS_send_trail_teardown (my_identity,
1897 existing_finger->finger_identity,
1898 replace_trail->trail_id,
1899 GDS_ROUTING_SRC_TO_DEST, target_friend);
1900 /* Free the trail .*/
1901 while (NULL != (trail_element = replace_trail->trail_head))
1903 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
1904 replace_trail->trail_tail, trail_element);
1905 GNUNET_free (trail_element);
1908 /* Add new trial at that location. */
1910 while ( i < new_trail_length)
1912 struct Trail *element = GNUNET_new (struct Trail);
1913 element->next = NULL;
1914 element->prev = NULL;
1915 element->peer = new_trail[0];
1917 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
1918 replace_trail->trail_tail,
1925 * Check if the new trail to reach to finger is unique or do we already have
1926 * such a trail present for finger.
1927 * @param existing_finger Finger identity
1928 * @param new_trail New trail to reach @a existing_finger
1929 * @param trail_length Total number of peers in new_trail.
1930 * @return #GNUNET_YES if the new trail is unique
1931 * #GNUNET_NO if same trail is already present.
1934 is_new_trail_unique (struct FingerInfo *existing_finger,
1935 struct GNUNET_PeerIdentity *new_trail,
1936 unsigned int trail_length)
1938 struct TrailList *trail_list_iterator;
1939 struct Trail *trail_element;
1942 int trail_unique = GNUNET_NO;
1944 for (i = 0; i < existing_finger->trails_count; i++)
1946 trail_list_iterator = &existing_finger->trail_list[i];
1947 trail_element = trail_list_iterator->trail_head;
1948 for (j = 0; j < trail_list_iterator->trail_length; j++)
1950 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
1951 &trail_element->peer))
1953 trail_unique = GNUNET_YES;
1958 return trail_unique;
1963 * Add a new trail to existing finger.
1964 * @param existing_finger
1965 * @param new_finger_trail
1966 * @param new_finger_trail_length
1967 * @param new_finger_trail_id
1970 add_new_trail (struct FingerInfo *existing_finger,
1971 struct GNUNET_PeerIdentity *new_trail,
1972 unsigned int new_trail_length,
1973 struct GNUNET_HashCode new_trail_id)
1975 struct TrailList *trail_list_iterator;
1976 struct FriendInfo *first_friend;
1980 if (GNUNET_NO == is_new_trail_unique (existing_finger,
1987 trail_list_iterator = &existing_finger->trail_list[i];
1989 } while (trail_list_iterator->trail_head != NULL);
1991 if (new_trail_length > 0)
1992 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1995 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1996 &(existing_finger->finger_identity));
1997 first_friend->trails_count++;
1998 trail_list_iterator->first_friend_trail_count = first_friend->trails_count;
1999 trail_list_iterator->trail_length = new_trail_length;
2001 for (j = 0; j < new_trail_length; j++)
2003 struct Trail *element;
2004 element = GNUNET_new (struct Trail);
2006 element->next = NULL;
2007 element->prev = NULL;
2008 element->peer = new_trail[j];
2009 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2010 trail_list_iterator->trail_tail,
2013 existing_finger->trails_count++;
2018 * Send trail teardown message on all trails associated with finger.
2019 * @param finger_to_be_removed
2022 send_trail_teardown (struct FingerInfo *finger)
2024 struct TrailList *trail_list_iterator;
2025 struct GNUNET_HashCode trail_id;
2026 struct FriendInfo *target_friend;
2029 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity, &my_identity)
2030 || (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2031 &finger->finger_identity)))
2034 for (i = 0; i < finger->trails_count; i++)
2036 trail_list_iterator = &finger->trail_list[i];
2037 if (trail_list_iterator->trail_length > 0)
2039 trail_id = trail_list_iterator->trail_id;
2041 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2042 &trail_list_iterator->trail_head->peer);
2043 GDS_NEIGHBOURS_send_trail_teardown (my_identity, finger->finger_identity,
2044 trail_id, GDS_ROUTING_SRC_TO_DEST,
2052 * Decrement the trail count of the first friend to reach the finger
2053 * In case finger is the friend, then decrement its trail count.
2057 decrement_friend_trail_count (struct FingerInfo *finger)
2059 struct TrailList *trail_list_iterator;
2060 struct FriendInfo *target_friend;
2063 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2067 for (i = 0; i < finger->trails_count; i++)
2069 trail_list_iterator = &finger->trail_list[i];
2070 if (trail_list_iterator->trail_length > 0)
2072 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2073 &trail_list_iterator->trail_head->peer);
2076 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2077 &finger->finger_identity);
2079 target_friend->trails_count--;
2080 trail_list_iterator->first_friend_trail_count--;
2087 * Free finger and its trail.
2088 * @param finger Finger to be freed.
2091 free_finger (struct FingerInfo *finger)
2093 struct TrailList *trail_list_iterator;
2094 struct Trail *trail_element;
2097 for (i = 0; i < finger->trails_count; i++)
2099 trail_list_iterator = &finger->trail_list[i];
2100 while (NULL != (trail_element = trail_list_iterator->trail_head))
2102 GNUNET_CONTAINER_DLL_remove (trail_list_iterator->trail_head,
2103 trail_list_iterator->trail_tail, trail_element);
2104 GNUNET_free (trail_element);
2107 GNUNET_free (finger);
2112 * Check if new finger is closer than existing_finger. If both new finger and
2113 * existing finger are same then we may add a new trail (if there is space)
2114 * or choose the best trail among existing trails and new trails.
2115 * @param existing_finger Finger present in finger_peermap at @a finger_map_index
2116 * @param new_finger_identity Peer identity of new finger.
2117 * @param new_finger_trail Trail to reach from source to new_finger.
2118 * @param new_finger_trail_length Total number of peers in @a new_finger_trail.
2119 * @param trail_id Unique identifier of trail.
2120 * @param finger_map_index Index in finger map.
2121 * @return #GNUNET_YES if the new finger is closest.
2122 * #GNUNET_NO either new_finger and existing_finger are same, or
2123 * existing_finger is closest.
2126 is_new_finger_closest (struct FingerInfo *existing_finger,
2127 struct GNUNET_PeerIdentity new_finger_identity,
2128 struct GNUNET_PeerIdentity *new_finger_trail,
2129 unsigned int new_finger_trail_length,
2130 struct GNUNET_HashCode new_finger_trail_id,
2131 unsigned int finger_map_index)
2133 struct GNUNET_PeerIdentity *closest_peer;
2136 if (NULL == existing_finger)
2139 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
2140 &new_finger_identity))
2142 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2143 closest_peer = select_closest_peer (&existing_finger->finger_identity,
2144 &new_finger_identity,
2145 my_id64, finger_map_index);
2147 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity, closest_peer))
2149 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2150 &new_finger_identity)) /* FIXME: not sure what to do here? */
2153 send_trail_teardown (existing_finger);
2154 decrement_friend_trail_count (existing_finger);
2155 free_finger (existing_finger);
2161 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
2165 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2166 &(existing_finger->finger_identity)))
2168 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
2169 add_new_trail (existing_finger, new_finger_trail,
2170 new_finger_trail_length, new_finger_trail_id);
2172 select_and_replace_trail (existing_finger, new_finger_trail,
2173 new_finger_trail_length, new_finger_trail_id);
2182 * Add a new entry in finger hashmap at finger_map_index
2183 * @param finger_identity Peer Identity of new finger
2184 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2185 * @param finger_trail_length Total number of peers in @a finger_trail.
2186 * @param trail_id Unique identifier of the trail.
2187 * @param finger_map_index Index in finger hashmap.
2188 * @return #GNUNET_OK if new entry is added
2189 * #GNUNET_NO -- FIXME: need to check what value does hahsmap put
2190 * returns on failure.
2193 add_new_entry (struct GNUNET_PeerIdentity finger_identity,
2194 struct GNUNET_PeerIdentity *finger_trail,
2195 unsigned int finger_trail_length,
2196 struct GNUNET_HashCode trail_id,
2197 unsigned int finger_map_index)
2199 struct FingerInfo *new_entry;
2200 struct FriendInfo *first_trail_hop;
2201 struct TrailList *first_trail;
2204 new_entry = GNUNET_new (struct FingerInfo);
2205 new_entry->finger_identity = finger_identity;
2206 new_entry->finger_map_index = finger_map_index;
2207 new_entry->trails_count = 1;
2209 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2211 if (finger_trail_length > 0)
2213 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2218 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2222 first_trail_hop->trails_count++;
2223 first_trail = &new_entry->trail_list[0];
2224 first_trail->first_friend_trail_count = first_trail_hop->trails_count;
2226 while (i < finger_trail_length)
2228 struct Trail *element = GNUNET_new (struct Trail);
2230 element->next = NULL;
2231 element->prev = NULL;
2232 element->peer = finger_trail[i];
2233 GNUNET_CONTAINER_DLL_insert_tail (first_trail->trail_head,
2234 first_trail->trail_tail,
2240 return GNUNET_CONTAINER_multihashmap32_put (finger_hashmap,
2241 new_entry->finger_map_index,
2243 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
2248 * Scan the trail to check if there is any other friend in the trail other than
2249 * first hop. If yes the shortcut the trail, send trail compression message to
2250 * peers which are no longer part of trail and send back the updated trail
2251 * and trail_length to calling function.
2252 * @param finger_identity Finger whose trail we will scan.
2253 * @param finger_trail [in, out] Trail to reach from source to finger,
2254 * @param finger_trail_length Total number of peers in original finger_trail.
2255 * @param finger_trail_id Unique identifier of the finger trail.
2256 * @return updated trail length in case we shortcut the trail, else original
2260 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2261 struct GNUNET_PeerIdentity *trail,
2262 unsigned int trail_length,
2263 struct GNUNET_HashCode trail_id)
2265 struct FriendInfo *target_friend;
2268 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2274 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
2276 if (trail_length > 0)
2278 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2280 GDS_NEIGHBOURS_send_trail_compression (my_identity, finger_identity,
2281 trail_id, finger_identity,
2288 for ( i = trail_length - 1; i > 0; i--)
2290 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
2292 struct FriendInfo *target_friend;
2295 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2297 GDS_NEIGHBOURS_send_trail_compression (my_identity, finger_identity,
2301 /* Copy the trail from index i to index trail_length -1 and change
2302 trail length and return */
2303 while (i < trail_length)
2305 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
2313 return trail_length;
2318 * Send verify successor message to your successor on all trails to reach successor.
2319 * @param successor My current successor
2322 send_verify_successor_message (struct FingerInfo *successor)
2324 struct TrailList *trail_list_iterator;
2325 struct GNUNET_HashCode trail_id;
2326 struct GNUNET_PeerIdentity next_hop;
2327 struct FriendInfo *target_friend;
2328 struct GNUNET_PeerIdentity *trail;
2329 unsigned int trail_length;
2333 for (i = 0; i < successor->trails_count; i++)
2335 trail_list_iterator = &successor->trail_list[i];
2337 if (trail_list_iterator->trail_length > 0)
2339 trail_length = trail_list_iterator->trail_length;
2341 trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2343 struct Trail *element;
2344 element = trail_list_iterator->trail_head;
2345 while ( j < trail_length)
2347 trail[j] = element->peer;
2348 element = element->next;
2351 next_hop = trail_list_iterator->trail_head->peer;
2357 next_hop = successor->finger_identity;
2359 trail_id = trail_list_iterator->trail_id;
2360 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2361 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
2362 successor->finger_identity,
2363 trail_id, trail, trail_length,
2370 * Check if there is already an entry in finger peermap for given finger map index.
2371 * If yes, then select the closest finger. If new and existing finger are same,
2372 * the check if you can store more trails. If yes then add trail, else keep the best
2373 * trails to reach to the finger. If the new finger is closest, add it.
2374 * Then, update current_search_finger_index.
2375 * @param new_finger_identity Peer Identity of new finger
2376 * @param new_finger_trail Trail to reach the new finger
2377 * @param new_finger_length Total number of peers in @a new_finger_trail.
2378 * @param finger_map_index Index in finger peermap.
2379 * @param new_finger_trail_id Unique identifier of @new_finger_trail.
2380 * @return #GNUNET_YES if the new entry is added
2381 * #GNUNET_NO if new entry is not added, either it was discarded or
2382 * it was same as existing finger at finger map index.
2385 finger_table_add (struct GNUNET_PeerIdentity new_finger_identity,
2386 struct GNUNET_PeerIdentity *new_finger_trail,
2387 unsigned int new_finger_trail_length,
2388 unsigned int finger_map_index,
2389 struct GNUNET_HashCode new_finger_trail_id)
2391 struct FingerInfo *existing_finger;
2392 struct FingerInfo *successor;
2393 unsigned int new_entry_added = GNUNET_NO;
2395 int new_finger_updated_trail_length =
2396 scan_and_compress_trail (new_finger_identity, new_finger_trail,
2397 new_finger_trail_length, new_finger_trail_id);
2399 existing_finger = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2402 if (GNUNET_YES == is_new_finger_closest (existing_finger,
2403 new_finger_identity,
2405 new_finger_updated_trail_length,
2406 new_finger_trail_id, finger_map_index))
2408 GNUNET_assert (GNUNET_YES == add_new_entry (new_finger_identity,
2410 new_finger_updated_trail_length,
2411 new_finger_trail_id,
2413 new_entry_added = GNUNET_YES;
2416 successor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2418 if (0 == finger_map_index)
2420 current_search_finger_index = PREDECESSOR_FINGER_ID;
2422 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,&new_finger_identity))
2424 send_verify_successor_message (successor);
2427 else if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity,
2428 &(successor->finger_identity)))
2430 current_search_finger_index = 0;
2433 current_search_finger_index = current_search_finger_index - 1;
2435 return new_entry_added;
2440 * Core handler for P2P put messages.
2441 * @param cls closure
2442 * @param peer sender of the request
2443 * @param message message
2444 * @return #GNUNET_OK to keep the connection open,
2445 * #GNUNET_SYSERR to close it (signal serious error)
2448 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2449 const struct GNUNET_MessageHeader *message)
2456 * Core handler for p2p get requests.
2458 * @param cls closure
2459 * @param peer sender of the request
2460 * @param message message
2461 * @return #GNUNET_OK to keep the connection open,
2462 * #GNUNET_SYSERR to close it (signal serious error)
2465 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2466 const struct GNUNET_MessageHeader *message)
2473 * Core handler for get result
2474 * @param cls closure
2475 * @param peer sender of the request
2476 * @param message message
2477 * @return #GNUNET_OK to keep the connection open,
2478 * #GNUNET_SYSERR to close it (signal serious error)
2481 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
2482 const struct GNUNET_MessageHeader *message)
2488 /* Core handle for PeerTrailSetupMessage.
2489 * @param cls closure
2490 * @param message message
2491 * @param peer peer identity this notification is about
2492 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2495 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
2496 const struct GNUNET_MessageHeader *message)
2498 struct PeerTrailSetupMessage *trail_setup;
2499 struct GNUNET_PeerIdentity *trail_peer_list;
2500 struct GNUNET_PeerIdentity next_destination;
2501 struct GNUNET_PeerIdentity *current_destination;
2502 struct GNUNET_PeerIdentity *next_hop;
2503 struct GNUNET_PeerIdentity next_peer;
2504 struct FriendInfo *target_friend;
2505 struct GNUNET_PeerIdentity source;
2506 uint64_t ultimate_destination_finger_value;
2507 struct GNUNET_HashCode new_intermediate_trail_id;
2508 struct GNUNET_HashCode intermediate_trail_id;
2509 struct GNUNET_HashCode new_trail_id;
2510 unsigned int finger_map_index;
2511 uint32_t trail_length;
2514 msize = ntohs (message->size);
2515 if (msize != sizeof (struct PeerTrailSetupMessage))
2517 GNUNET_break_op (0);
2521 trail_setup = (struct PeerTrailSetupMessage *) message;
2522 trail_length = ntohl (trail_setup->trail_length);
2523 if ((msize != sizeof (struct PeerTrailSetupMessage) +
2524 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2526 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2528 GNUNET_break_op (0);
2532 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
2533 current_destination = &trail_setup->next_destination;
2534 intermediate_trail_id = trail_setup->intermediate_trail_id;
2535 new_trail_id = trail_setup->new_trail_id;
2536 ultimate_destination_finger_value = GNUNET_ntohll (trail_setup->ultimate_destination_finger);
2537 source = trail_setup->source_peer;
2538 finger_map_index = ntohl (trail_setup->finger_map_index);
2540 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2542 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2543 GDS_NEIGHBOURS_send_trail_rejection (source, ultimate_destination_finger_value,
2544 my_identity, finger_map_index,
2545 trail_peer_list, trail_length,
2546 new_trail_id, target_friend,
2547 CONGESTION_TIMEOUT);
2551 next_hop = find_successor (ultimate_destination_finger_value, &next_destination,
2552 &new_intermediate_trail_id, finger_map_index);
2554 if (0 != (GNUNET_CRYPTO_cmp_peer_identity(&my_identity, current_destination)))
2556 struct GNUNET_PeerIdentity *closest_peer;
2557 struct GNUNET_PeerIdentity *peer1 =
2558 GDS_ROUTING_get_next_hop (intermediate_trail_id, GDS_ROUTING_SRC_TO_DEST);
2559 if (0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, next_hop))
2561 closest_peer = select_closest_peer (peer1, next_hop,
2562 ultimate_destination_finger_value,
2565 if (0 == GNUNET_CRYPTO_cmp_peer_identity (peer1, closest_peer) ||
2566 (0 == GNUNET_CRYPTO_cmp_peer_identity (peer1, next_hop)))
2569 next_destination = *current_destination;
2570 new_intermediate_trail_id = intermediate_trail_id;
2574 GNUNET_assert (NULL != next_hop);
2575 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
2577 if (0 == trail_length)
2578 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
2580 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
2582 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
2583 GDS_NEIGHBOURS_send_trail_setup_result (source,
2585 target_friend, trail_length,
2587 finger_map_index, new_trail_id);
2591 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
2593 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2594 peer_list[trail_length] = my_identity;
2595 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2596 GDS_NEIGHBOURS_send_trail_setup (source,
2597 ultimate_destination_finger_value,
2599 target_friend, trail_length + 1, peer_list,
2600 finger_map_index, new_trail_id,
2601 new_intermediate_trail_id);
2608 * Core handle for p2p trail construction result messages.
2610 * @param message message
2611 * @param peer peer identity this notification is about
2612 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2615 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2616 const struct GNUNET_MessageHeader *message)
2618 struct PeerTrailSetupResultMessage *trail_result;
2619 struct GNUNET_PeerIdentity *trail_peer_list;
2620 struct GNUNET_PeerIdentity destination_peer;
2621 struct GNUNET_PeerIdentity finger_identity;
2622 uint32_t trail_length;
2623 uint32_t finger_map_index;
2624 struct GNUNET_HashCode trail_id;
2627 msize = ntohs (message->size);
2628 if (msize != sizeof (struct PeerTrailSetupResultMessage))
2630 GNUNET_break_op (0);
2634 trail_result = (struct PeerTrailSetupResultMessage *) message;
2635 trail_length = ntohl (trail_result->trail_length);
2638 sizeof (struct PeerTrailSetupResultMessage) +
2639 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2641 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2643 GNUNET_break_op (0);
2647 finger_map_index = htonl (trail_result->finger_map_index);
2648 destination_peer = trail_result->destination_peer;
2649 finger_identity = trail_result->finger_identity;
2650 trail_id = trail_result->trail_id;
2651 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
2653 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer,
2656 finger_table_add (finger_identity, trail_peer_list,
2658 finger_map_index, trail_id);
2662 struct GNUNET_PeerIdentity next_hop;
2663 struct FriendInfo *target_friend;
2666 my_index = search_my_index(trail_peer_list, trail_length);
2667 if (my_index == GNUNET_SYSERR)
2670 return GNUNET_SYSERR;
2674 next_hop = trail_result->destination_peer;
2676 next_hop = trail_peer_list[my_index - 1];
2678 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2679 &(trail_result->finger_identity))))
2681 GDS_ROUTING_add (trail_id, next_hop, *peer);
2684 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2685 GDS_NEIGHBOURS_send_trail_setup_result (destination_peer, finger_identity,
2686 target_friend, trail_length, trail_peer_list,
2687 finger_map_index, trail_id);
2694 * @param trail Trail to be inverted
2695 * @param trail_length Total number of peers in the trail.
2696 * @return Updated trail
2698 static struct GNUNET_PeerIdentity *
2699 invert_trail (struct GNUNET_PeerIdentity *trail,
2700 unsigned int trail_length)
2704 struct GNUNET_PeerIdentity *inverted_trail;
2706 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
2709 j = trail_length - 1;
2710 while (i < trail_length)
2712 inverted_trail[i] = trail[j];
2716 return inverted_trail;
2721 * Check if the new finger can be our predecessor. If yes then update predecessor
2724 * @param new_finger_trail
2725 * @param new_finger_trail_length
2729 is_new_entry_correct_predecessor (struct FingerInfo *my_predecessor,
2730 struct GNUNET_PeerIdentity new_finger,
2731 struct GNUNET_PeerIdentity *new_finger_trail,
2732 unsigned int new_finger_trail_length)
2734 struct GNUNET_PeerIdentity *updated_trail;
2735 struct GNUNET_HashCode new_trail_id;
2737 updated_trail = invert_trail (new_finger_trail, new_finger_trail_length);
2738 if (GNUNET_YES == is_new_finger_closest (my_predecessor, new_finger,
2740 new_finger_trail_length,
2741 new_trail_id, PREDECESSOR_FINGER_ID))
2743 add_new_entry (new_finger, updated_trail, new_finger_trail_length,
2744 new_trail_id, PREDECESSOR_FINGER_ID);
2745 /* FIXME: check where you send add trail message */
2752 * In case the source peer of verify successor message is not my successor,
2753 * then construct a trail from source peer to my current predecessor.
2754 * @param my_predecessor my current predecessor.
2755 * @param current_trail Trail from source to me.
2756 * @param current_trail_length Total number of peers in @a current_trail
2757 * @param new_trail_length [out] Total number of peers in updated trail.
2758 * @return Updated trail from source peer to my_predecessor.
2760 static struct GNUNET_PeerIdentity *
2761 trail_source_to_my_predecessor (struct FingerInfo *my_predecessor,
2762 struct GNUNET_PeerIdentity *current_trail,
2763 unsigned int current_trail_length,
2764 unsigned int *new_trail_length)
2766 struct GNUNET_PeerIdentity *new_trail;
2767 struct TrailList *trail_list_iterator;
2768 struct Trail *trail_iterator;
2771 unsigned int shortest_trail_length = 0;
2772 unsigned int trail_index = 0;
2774 for (i = 0; i < my_predecessor->trails_count; i++)
2776 trail_list_iterator = &my_predecessor->trail_list[i];
2777 if (trail_list_iterator->trail_length > shortest_trail_length)
2779 shortest_trail_length = trail_list_iterator->trail_length;
2783 *new_trail_length = current_trail_length + shortest_trail_length + 1;
2784 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2786 memcpy (new_trail, current_trail,
2787 current_trail_length * sizeof (struct GNUNET_PeerIdentity));
2788 new_trail[current_trail_length + 1] = my_identity;
2791 j = current_trail_length + 1;
2792 trail_list_iterator = &my_predecessor->trail_list[trail_index];
2793 trail_iterator = trail_list_iterator->trail_head;
2794 while ( i < shortest_trail_length)
2796 new_trail[j] = trail_iterator->peer;
2799 trail_iterator = trail_iterator->next;
2802 *new_trail_length = j;
2808 * Core handle for p2p verify successor messages.
2809 * @param cls closure
2810 * @param message message
2811 * @param peer peer identity this notification is about
2812 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2815 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2816 const struct GNUNET_MessageHeader *message)
2818 struct PeerVerifySuccessorMessage *vsm;
2819 struct GNUNET_PeerIdentity successor;
2820 struct GNUNET_PeerIdentity source_peer;
2821 struct GNUNET_PeerIdentity *next_hop;
2822 struct FriendInfo *target_friend;
2823 struct GNUNET_HashCode trail_id;
2824 struct FingerInfo *my_predecessor;
2825 struct GNUNET_PeerIdentity *trail;
2826 struct GNUNET_PeerIdentity *new_trail;
2827 unsigned int trail_length;
2828 unsigned int new_trail_length;
2831 msize = ntohs (message->size);
2832 if (msize != sizeof (struct PeerVerifySuccessorMessage))
2834 GNUNET_break_op (0);
2838 vsm = (struct PeerVerifySuccessorMessage *) message;
2839 trail_length = ntohl (vsm->trail_length);
2840 if ((msize != sizeof (struct PeerVerifySuccessorMessage) +
2841 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2842 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2844 GNUNET_break_op (0);
2847 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
2848 source_peer = vsm->source_peer;
2849 successor = vsm->successor;
2850 trail_id = vsm->trail_id;
2852 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
2854 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
2855 if (NULL == next_hop)
2858 return GNUNET_SYSERR;
2860 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2861 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
2862 trail_id, trail, trail_length,
2867 my_predecessor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2868 PREDECESSOR_FINGER_ID);
2869 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2870 if (GNUNET_NO == is_new_entry_correct_predecessor (my_predecessor, source_peer,
2871 trail, trail_length))
2873 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
2874 &my_predecessor->finger_identity))
2876 new_trail = trail_source_to_my_predecessor (my_predecessor, trail,
2877 trail_length, &new_trail_length);
2882 my_predecessor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2883 PREDECESSOR_FINGER_ID);
2884 GDS_NEIGHBOURS_send_add_trail (my_predecessor->finger_identity,
2885 source_peer, trail_id,
2886 trail, trail_length,
2888 new_trail_length = trail_length;
2889 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2891 memcpy (new_trail, trail, sizeof (struct GNUNET_PeerIdentity) *
2895 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
2896 my_predecessor->finger_identity,
2897 trail_id, new_trail,
2899 GDS_ROUTING_DEST_TO_SRC,
2906 * FIXME: I will keep the logic to remove the old trail to reach from me to
2907 * my old successor here and move adding a new trail from me to new successor to notify
2908 * new successor. And in case if the new successor also take it as predecessor
2909 * then call add_trail.
2910 * Core handle for p2p verify successor result messages.
2911 * @param cls closure
2912 * @param message message
2913 * @param peer peer identity this notification is about
2914 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2917 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2918 const struct GNUNET_MessageHeader *message)
2920 struct PeerVerifySuccessorResultMessage *vsrm;
2921 enum GDS_ROUTING_trail_direction trail_direction;
2922 struct GNUNET_HashCode trail_id;
2923 unsigned int new_trail_length;
2924 struct GNUNET_PeerIdentity *new_trail;
2925 struct GNUNET_PeerIdentity destination_peer;
2926 struct GNUNET_PeerIdentity my_new_successor;
2927 struct GNUNET_PeerIdentity old_successor;
2928 struct GNUNET_PeerIdentity *next_hop;
2929 struct FriendInfo *target_friend;
2932 msize = ntohs (message->size);
2933 if (msize != sizeof (struct PeerVerifySuccessorResultMessage))
2935 GNUNET_break_op (0);
2938 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
2939 new_trail_length = ntohl (vsrm->trail_length);
2940 trail_direction = ntohl (vsrm->trail_direction);
2941 trail_id = vsrm->trail_id;
2944 sizeof (struct PeerVerifySuccessorResultMessage) +
2946 sizeof (struct GNUNET_PeerIdentity)) ||
2948 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2950 GNUNET_break_op (0);
2954 new_trail = (struct GNUNET_PeerIdentity *) &vsrm[1];
2955 destination_peer = vsrm->destination_peer;
2956 my_new_successor = vsrm->my_predecessor;
2957 old_successor = vsrm->source_successor;
2959 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer, &my_identity)))
2961 struct GNUNET_HashCode new_finger_trail_id;
2962 /* FIXME: generate a new trail id. */
2963 if (GNUNET_YES == finger_table_add (my_new_successor,
2966 PREDECESSOR_FINGER_ID, new_finger_trail_id))
2968 if (new_trail_length > 0)
2969 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2972 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2974 GDS_NEIGHBOURS_send_trail_teardown (my_identity, old_successor, trail_id,
2975 GDS_ROUTING_SRC_TO_DEST, target_friend);
2976 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, my_new_successor,
2979 new_finger_trail_id, target_friend);
2984 GNUNET_assert (NULL != (next_hop =
2985 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
2986 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2987 GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2988 vsrm->source_successor,
2989 my_new_successor, trail_id,
2992 trail_direction, target_friend);
2998 * Core handle for p2p notify new successor messages.
2999 * @param cls closure
3000 * @param message message
3001 * @param peer peer identity this notification is about
3002 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3005 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3006 const struct GNUNET_MessageHeader *message)
3008 struct PeerNotifyNewSuccessorMessage *nsm;
3009 struct GNUNET_PeerIdentity *trail;
3010 struct GNUNET_PeerIdentity source;
3011 struct GNUNET_PeerIdentity destination;
3012 struct FriendInfo *target_friend;
3013 struct GNUNET_HashCode trail_id;
3014 unsigned int my_index;
3015 struct GNUNET_PeerIdentity next_hop;
3017 uint32_t trail_length;
3019 msize = ntohs (message->size);
3020 if (msize != sizeof (struct PeerNotifyNewSuccessorMessage))
3022 GNUNET_break_op (0);
3026 nsm = (struct PeerNotifyNewSuccessorMessage *) message;
3027 trail_length = ntohl (nsm->trail_length);
3029 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3030 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3032 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3034 GNUNET_break_op (0);
3038 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
3039 source = nsm->source_peer;
3040 destination = nsm->destination_peer;
3041 trail_id = nsm->trail_id;
3043 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination))
3045 struct GNUNET_HashCode new_trail_id;
3046 struct FingerInfo *my_predecessor;
3049 GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
3050 PREDECESSOR_FINGER_ID);
3051 /* FIXME: get new_trail_id*/
3053 if (GNUNET_YES == is_new_entry_correct_predecessor (my_predecessor,
3058 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3060 GDS_NEIGHBOURS_send_add_trail (my_identity, source, new_trail_id,
3061 trail, trail_length, target_friend);
3066 my_index = search_my_index (trail, trail_length);
3067 if (GNUNET_SYSERR == my_index)
3069 GNUNET_break_op (0);
3070 return GNUNET_SYSERR;
3072 if (trail_length == my_index)
3073 next_hop = destination;
3075 next_hop = trail[my_index + 1];
3076 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
3077 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3078 GDS_NEIGHBOURS_send_notify_new_successor (source, destination, trail,
3080 trail_id, target_friend);
3086 * FIXME: Here you should keep the trail id with you.
3087 * Core handler for P2P trail rejection message
3088 * @param cls closure
3089 * @param message message
3090 * @param peer peer identity this notification is about
3091 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3094 handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3095 const struct GNUNET_MessageHeader *message)
3097 struct PeerTrailRejectionMessage *trail_rejection;
3098 unsigned int trail_length;
3099 struct GNUNET_PeerIdentity *trail_peer_list;
3100 struct FriendInfo *target_friend;
3101 struct GNUNET_TIME_Relative congestion_timeout;
3102 struct GNUNET_HashCode trail_id;
3103 struct GNUNET_PeerIdentity next_destination;
3104 struct GNUNET_HashCode new_intermediate_trail_id;
3105 struct GNUNET_PeerIdentity next_peer;
3106 struct GNUNET_PeerIdentity source;
3107 struct GNUNET_PeerIdentity *next_hop;
3108 uint64_t ultimate_destination_finger_value;
3109 unsigned int finger_map_index;
3112 msize = ntohs (message->size);
3113 if (msize != sizeof (struct PeerTrailRejectionMessage))
3115 GNUNET_break_op (0);
3119 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3120 trail_length = ntohl (trail_rejection->trail_length);
3122 if ((msize != sizeof (struct PeerTrailRejectionMessage) +
3123 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3125 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3127 GNUNET_break_op (0);
3131 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3132 finger_map_index = ntohl (trail_rejection->finger_map_index);
3133 congestion_timeout = trail_rejection->congestion_time;
3134 source = trail_rejection->source_peer;
3135 trail_id = trail_rejection->trail_id;
3136 ultimate_destination_finger_value =
3137 trail_rejection->ultimate_destination_finger_identity_value;
3139 /* First set the congestion time of the friend that sent you this message. */
3140 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3141 target_friend->congestion_duration = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
3142 congestion_timeout);
3144 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
3149 /* If I am congested then pass this message to peer before me in trail. */
3150 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
3152 struct GNUNET_PeerIdentity *new_trail;
3153 unsigned int new_trail_length;
3155 if (trail_length == 1)
3158 new_trail_length = 0;
3163 next_hop = &trail_peer_list[trail_length - 2];
3164 /* Remove myself from the trail. */
3165 new_trail_length = trail_length -1;
3166 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
3167 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
3170 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3171 GDS_NEIGHBOURS_send_trail_rejection (source,
3172 ultimate_destination_finger_value,
3173 my_identity, finger_map_index,
3174 new_trail,new_trail_length,trail_id,
3175 target_friend, CONGESTION_TIMEOUT);
3179 /* Look for next_hop to pass the trail setup message */
3180 next_hop = find_successor (ultimate_destination_finger_value,
3182 &new_intermediate_trail_id,
3185 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
3187 if (0 == trail_length)
3190 next_peer = trail_peer_list[trail_length-1];
3192 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3193 GDS_NEIGHBOURS_send_trail_setup_result (source,
3195 target_friend, trail_length,
3197 finger_map_index, trail_id);
3201 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3203 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3204 peer_list[trail_length] = my_identity;
3206 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3207 GDS_NEIGHBOURS_send_trail_setup (source,
3208 ultimate_destination_finger_value,
3210 target_friend, trail_length + 1, peer_list,
3211 finger_map_index, trail_id,
3212 new_intermediate_trail_id);
3219 * Core handle for p2p trail tear down messages.
3220 * @param cls closure
3221 * @param message message
3222 * @param peer peer identity this notification is about
3223 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3226 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
3227 const struct GNUNET_MessageHeader *message)
3229 struct PeerTrailCompressionMessage *trail_compression;
3230 struct GNUNET_PeerIdentity *next_hop;
3231 struct GNUNET_HashCode trail_id;
3232 struct FriendInfo *target_friend;
3235 msize = ntohs (message->size);
3236 if (msize != sizeof (struct PeerTrailCompressionMessage))
3238 GNUNET_break_op (0);
3242 trail_compression = (struct PeerTrailCompressionMessage *) message;
3243 trail_id = trail_compression->trail_id;
3245 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->new_first_friend),
3248 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->destination_peer),
3251 GDS_ROUTING_update_trail_prev_hop (trail_id,
3252 trail_compression->source_peer);
3257 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
3258 if (NULL == next_hop)
3260 GNUNET_break (0); /*FIXME: How to handle this case. */
3263 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
3264 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3265 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
3266 trail_compression->destination_peer,
3268 trail_compression->new_first_friend,
3275 * Core handler for trail teardown message.
3276 * @param cls closure
3277 * @param message message
3278 * @param peer peer identity this notification is about
3279 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3282 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
3283 const struct GNUNET_MessageHeader *message)
3285 struct PeerTrailTearDownMessage *trail_teardown;
3286 struct GNUNET_HashCode trail_id;
3287 enum GDS_ROUTING_trail_direction trail_direction;
3290 msize = ntohs (message->size);
3291 if (msize != sizeof (struct PeerTrailTearDownMessage))
3293 GNUNET_break_op (0);
3297 trail_teardown = (struct PeerTrailTearDownMessage *) message;
3298 trail_direction = ntohl (trail_teardown->trail_direction);
3299 trail_id = trail_teardown->TRAIL_ID;
3301 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3302 &trail_teardown->destination_peer))
3304 struct GNUNET_PeerIdentity *next_hop;
3305 struct FriendInfo *target_friend;
3307 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
3308 if (NULL == next_hop)
3311 return GNUNET_SYSERR;
3314 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3316 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
3317 GDS_NEIGHBOURS_send_trail_teardown (trail_teardown->source_peer,
3318 trail_teardown->destination_peer,
3319 trail_id, trail_direction,
3327 * Fixme: this function is called only in case in notify new successor, the new
3328 * successor wants to add the source of the peer as its predecessor. Identify
3329 * if there is any other use case where it is required and if yes then adapt the
3331 * Core handle for p2p add trail message.
3332 * @param cls closure
3333 * @param message message
3334 * @param peer peer identity this notification is about
3335 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3338 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
3339 const struct GNUNET_MessageHeader *message)
3341 struct PeerAddTrailMessage *add_trail;
3342 struct GNUNET_PeerIdentity *trail;
3343 struct GNUNET_HashCode trail_id;
3344 struct GNUNET_PeerIdentity destination_peer;
3345 struct GNUNET_PeerIdentity source_peer;
3346 struct GNUNET_PeerIdentity next_hop;
3347 unsigned int trail_length;
3348 unsigned int my_index;
3351 msize = ntohs (message->size);
3352 if (msize != sizeof (struct PeerAddTrailMessage))
3354 GNUNET_break_op (0);
3358 add_trail = (struct PeerAddTrailMessage *) message;
3359 trail_length = ntohl (add_trail->trail_length);
3361 if ((msize < sizeof (struct PeerAddTrailMessage) +
3362 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3364 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3366 GNUNET_break_op (0);
3370 trail = (struct GNUNET_PeerIdentity *)&add_trail[1];
3371 destination_peer = add_trail->destination_peer;
3372 source_peer = add_trail->source_peer;
3373 trail_id = add_trail->trail_id;
3375 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3378 struct FriendInfo *target_friend;
3380 my_index = search_my_index (trail, trail_length);
3381 if (GNUNET_SYSERR == my_index)
3383 GNUNET_break_op (0);
3384 return GNUNET_SYSERR;
3388 next_hop = source_peer;
3390 next_hop = trail[trail_length - 1];
3392 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
3393 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3394 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
3395 trail, trail_length, target_friend);
3402 *FIXME; call send_trail_teardown_message on all the trails of the finger that
3403 * you remove. Also you don't need to decerement friend trail count as that
3404 * friend is removed. But you can not send trail teardown message as the friend
3405 * is disconnected. then you don't have any next_hop. and in case there are
3406 * multiple trails. and friend is the first trail then you remove only the trail.
3407 * Iterate over finger_hashmap, and remove entries if finger is the disconnected
3408 * peer or if disconnected peer is the first friend in the trail to reach the
3410 * @param cls closure
3411 * @param key current public key
3412 * @param value value in the hash map
3413 * @return #GNUNET_YES if we should continue to
3415 * #GNUNET_NO if not.
3418 remove_matching_finger (void *cls,
3422 struct FingerInfo *remove_finger = value;
3423 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
3424 struct TrailList *trail_list;
3427 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
3430 GNUNET_assert (GNUNET_YES ==
3431 GNUNET_CONTAINER_multihashmap32_remove (finger_hashmap,
3434 free_finger (remove_finger);
3438 for (i = 0; i< remove_finger->trails_count; i++)
3440 trail_list = &remove_finger->trail_list[i];
3441 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_list->trail_head->peer,
3444 GNUNET_assert (GNUNET_YES ==
3445 GNUNET_CONTAINER_multihashmap32_remove (finger_hashmap,
3448 free_finger (remove_finger);
3457 * Method called whenever a peer disconnects.
3459 * @param cls closure
3460 * @param peer peer identity this notification is about
3463 handle_core_disconnect (void *cls,
3464 const struct GNUNET_PeerIdentity *peer)
3466 struct FriendInfo *remove_friend;
3468 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
3472 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3474 if (NULL == remove_friend)
3480 GNUNET_assert (GNUNET_SYSERR !=
3481 GNUNET_CONTAINER_multihashmap32_iterate (finger_hashmap,
3482 &remove_matching_finger,
3484 GDS_ROUTING_remove_trail_by_peer (peer);
3485 GNUNET_assert (GNUNET_YES ==
3486 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
3490 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
3493 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3495 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3496 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3504 * Method called whenever a peer connects.
3506 * @param cls closure
3507 * @param peer_identity peer identity this notification is about
3510 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
3512 struct FriendInfo *friend;
3514 /* Check for connect to self message */
3515 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
3518 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
3520 /* If peer already exists in our friend_peermap, then exit. */
3521 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
3527 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
3530 friend = GNUNET_new (struct FriendInfo);
3531 friend->id = *peer_identity;
3533 GNUNET_assert (GNUNET_OK ==
3534 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
3535 peer_identity, friend,
3536 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
3538 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
3539 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
3540 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
3545 * To be called on core init/fail.
3547 * @param cls service closure
3548 * @param identity the public identity of this peer
3551 core_init (void *cls,
3552 const struct GNUNET_PeerIdentity *identity)
3554 my_identity = *identity;
3559 * Initialize neighbours subsystem.
3560 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3563 GDS_NEIGHBOURS_init (void)
3565 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
3566 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
3567 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
3568 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
3569 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
3570 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
3571 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
3572 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
3573 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
3574 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
3575 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION, 0},
3576 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
3577 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL, 0},
3582 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
3583 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
3584 GNUNET_NO, core_handlers);
3585 if (NULL == core_api)
3586 return GNUNET_SYSERR;
3588 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
3589 finger_hashmap = GNUNET_CONTAINER_multihashmap32_create (MAX_FINGERS * 4/3);
3595 * Shutdown neighbours subsystem.
3598 GDS_NEIGHBOURS_done (void)
3600 if (NULL == core_api)
3603 GNUNET_CORE_disconnect (core_api);
3606 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
3607 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
3608 friend_peermap = NULL;
3610 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap32_size (finger_hashmap));
3611 GNUNET_CONTAINER_multihashmap32_destroy (finger_hashmap);
3612 finger_hashmap = NULL;
3614 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3617 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3618 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3626 * @return my identity
3628 struct GNUNET_PeerIdentity
3629 GDS_NEIGHBOURS_get_my_id (void)