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;
109 /* Bitmask of options, 1 = IS_PREDECESSOR */
113 * Peer closest to this value will be our finger.
115 uint64_t ultimate_destination_finger;
118 * Source peer which wants to setup the trail to one of its finger.
120 struct GNUNET_PeerIdentity source_peer;
123 * Peer to which this packet is forwarded.
125 struct GNUNET_PeerIdentity next_destination; // rename "best_known_dest"
128 * Index into finger peer map, in Network Byte Order.
130 uint32_t finger_map_index; // remove this, include ultimate_destination_finger in response, calculate index from it
133 * Number of entries in trail_list, in Network Byte Order.
135 uint32_t trail_length GNUNET_PACKED; // remove this, calculte length from message size
138 * Trail id of any intermediate trail we may encounter while doing trail setup.
140 struct GNUNET_HashCode intermediate_trail_id;
143 * Trail id for trail which we are trying to setup.
145 struct GNUNET_HashCode new_trail_id; // rename to "trail_id"
147 /* Trail formed in the process. */
148 /* GNUNET_PeerIdentity trail_list[] */
152 * P2P Trail Setup Result message
154 struct PeerTrailSetupResultMessage
158 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
160 struct GNUNET_MessageHeader header;
163 * Finger to which we have found the path.
165 struct GNUNET_PeerIdentity finger_identity;
168 * Peer which was looking for the trail to finger.
170 struct GNUNET_PeerIdentity destination_peer; // querying_peer
173 * Index into finger peer map in NBO.
175 uint32_t finger_map_index; // flag/option with IS_PREDECESSOR
178 * Number of entries in trail list in NBO.
180 uint32_t trail_length GNUNET_PACKED; // remove, calculate
183 * Identifier of the trail.
185 struct GNUNET_HashCode trail_id;
187 /* Trail from "destination_peer" to finger_identity, NOT including both */
188 /* struct GNUNET_PeerIdentity trail[] */
192 * P2P Verify Successor Message.
194 struct PeerVerifySuccessorMessage
197 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
199 struct GNUNET_MessageHeader header;
202 * Source peer which wants to verify its successor.
204 struct GNUNET_PeerIdentity source_peer;
207 * My current successor.
209 struct GNUNET_PeerIdentity successor;
212 * Identifier of trail to reach from source_peer to successor.
214 struct GNUNET_HashCode trail_id;
217 * Total number of peers to reach from source to successor.
219 unsigned int trail_length;
225 * P2P Verify Successor Result Message
227 struct PeerVerifySuccessorResultMessage
230 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
232 struct GNUNET_MessageHeader header;
235 * Destination peer which sent the request to verify its successor.
237 struct GNUNET_PeerIdentity destination_peer;
240 * Successor to which PeerVerifySuccessorMessage was sent.
242 struct GNUNET_PeerIdentity source_successor;
245 * source_successor's predecessor
247 struct GNUNET_PeerIdentity my_predecessor;
250 * Trail identifier of trail from my_predecessor to source_successor.
252 struct GNUNET_HashCode trail_id;
255 * Direction in which we are looking at the trail.
257 enum GDS_ROUTING_trail_direction trail_direction;
260 * Total number of peers in trail from source_successor to my_predecessor
261 * if my_predecessor is not same as destination_peer.
263 uint32_t trail_length;
265 /* Trail from source_successor to my_predecessor where
266 * my_predecessor != destination_peer*/
270 * P2P Notify New Successor Message.
272 struct PeerNotifyNewSuccessorMessage
275 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
277 struct GNUNET_MessageHeader header;
280 * Source peer which wants to notify its new successor.
282 struct GNUNET_PeerIdentity source_peer;
285 * New successor identity.
287 struct GNUNET_PeerIdentity destination_peer;
290 * Total number of peers in trail from source_peer to destination_peer
292 unsigned int trail_length;
295 * Unique identifier of the trail.
297 struct GNUNET_HashCode trail_id;
303 * P2P Trail Compression Message.
305 struct PeerTrailCompressionMessage
308 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION
310 struct GNUNET_MessageHeader header;
313 * Source peer of this trail.
315 struct GNUNET_PeerIdentity source_peer;
318 * Destination of this trail.
320 struct GNUNET_PeerIdentity destination_peer;
323 * Trail from source_peer to destination_peer compressed such that
324 * new_first_friend is the first hop in the trail from source to
327 struct GNUNET_PeerIdentity new_first_friend;
330 * Unique identifier of trail.
332 struct GNUNET_HashCode trail_id;
337 * P2P Trail Tear Down message.
339 struct PeerTrailTearDownMessage
342 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
344 struct GNUNET_MessageHeader header;
347 * Source peer of the trail.
349 struct GNUNET_PeerIdentity source_peer;
352 * Destination peer of the trail.
354 struct GNUNET_PeerIdentity destination_peer;
357 * Unique identifier of the trail.
359 struct GNUNET_HashCode TRAIL_ID;
362 * Direction of trail.
364 enum GDS_ROUTING_trail_direction trail_direction;
369 * P2P Trail Rejection Message.
371 struct PeerTrailRejectionMessage
374 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
376 struct GNUNET_MessageHeader header;
379 * Source peer which wants to set up the trail.
381 struct GNUNET_PeerIdentity source_peer;
384 * Peer which sent trail rejection message.
386 struct GNUNET_PeerIdentity congested_peer;
389 * Peer identity which will be successor to this value will be finger of
392 uint64_t ultimate_destination_finger_identity_value;
395 * Index in finger peer map of source peer.
397 uint32_t finger_map_index;
400 * Total number of peers in the trail.
402 uint32_t trail_length;
405 * Identifier for the trail source peer is trying to setup.
407 struct GNUNET_HashCode trail_id;
409 * Relative time for which congested_peer will remain congested.
411 struct GNUNET_TIME_Relative congestion_time;
413 /* Trail_list from source_peer to peer which sent the message for trail setup
414 * to congested peer.*/
418 * P2P Add Trail Message.
420 struct PeerAddTrailMessage
423 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL
425 struct GNUNET_MessageHeader header;
428 * Source peer of the routing trail.
430 struct GNUNET_PeerIdentity source_peer;
433 * Destination peer of the routing trail.
435 struct GNUNET_PeerIdentity destination_peer;
438 * Total number of peers from source peer to destination peer.
440 unsigned int trail_length;
443 * Unique identifier of the trail.
445 struct GNUNET_HashCode trail_id;
447 /* Trail from source peer to destination peer. */
450 GNUNET_NETWORK_STRUCT_END
453 * Linked list of messages to send to a particular other peer.
455 struct P2PPendingMessage
458 * Pointer to next item in the list
460 struct P2PPendingMessage *next;
463 * Pointer to previous item in the list
465 struct P2PPendingMessage *prev;
468 * Message importance level. FIXME: used? useful?
470 unsigned int importance;
473 * When does this message time out?
475 struct GNUNET_TIME_Absolute timeout;
478 * Actual message to be sent, allocated at the end of the struct:
479 * // msg = (cast) &pm[1];
480 * // memcpy (&pm[1], data, len);
482 const struct GNUNET_MessageHeader *msg;
488 * Entry in friend_peermap.
495 struct GNUNET_PeerIdentity id;
498 * Number of trails for which this friend is the first hop.
500 unsigned int trails_count;
503 * Count of outstanding messages for this friend.
505 unsigned int pending_count;
508 * In case not 0, then amount of time for which this friend is congested.
510 struct GNUNET_TIME_Absolute congestion_timestamp;
513 * Head of pending messages to be sent to this friend.
515 struct P2PPendingMessage *head;
518 * Tail of pending messages to be sent to this friend.
520 struct P2PPendingMessage *tail;
523 * Core handle for sending messages to this friend.
525 struct GNUNET_CORE_TransmitHandle *th;
530 * An individual trail to reach to a finger.
532 struct Trail // "node" "element" "relay"
535 * Pointer to next item in the list
540 * Pointer to prev item in the list
545 * An element in this trail.
547 struct GNUNET_PeerIdentity peer;
551 * List of all trails to reach a particular finger.
553 struct TrailList // "trail": list of "elements"
558 struct Trail *trail_head;
563 struct Trail *trail_tail;
566 * Unique identifier of this trail.
568 struct GNUNET_HashCode trail_id;
571 * Length of trail pointed
573 unsigned int trail_length;
576 * Number of trails that the first friend of this trail is a part of.
578 unsigned int first_friend_trail_count; // remove this, duplicate variable!
579 // include a pointer to Friend or function that calculates it
583 * An entry in finger_hashmap.
590 struct GNUNET_PeerIdentity finger_identity;
593 * Index in finger peer map
595 uint32_t finger_map_index;
598 * Number of trails setup so far for this finger.
600 uint32_t trails_count;
605 struct TrailList trail_list[MAXIMUM_TRAILS_PER_FINGER]; // OK!
609 * Data structure to keep track of closest peer seen so far in find_successor()
614 * 64 bit value of the peer
619 * Trail id to reach to peer.
621 struct GNUNET_HashCode trail_id;
624 * First hop, NULL in case of friend and my_identity
626 struct GNUNET_PeerIdentity next_hop;
629 * Next destination. In case of friend and my_identity , it is same as next_hop
630 * In case of finger it is finger identity.
632 struct GNUNET_PeerIdentity next_destination;
636 * Data structure to store the trail chosen to reach to finger.
641 * First friend in the trail to reach finger.
643 struct FriendInfo friend;
646 * Identifier of this trail.
648 struct GNUNET_HashCode trail_id;
651 * Total number of peers in this trail.
653 unsigned int trail_length;
657 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
658 * get our first friend.
660 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
663 * Identity of this peer.
665 static struct GNUNET_PeerIdentity my_identity;
668 * Peer map of all the friends of a peer
670 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
673 * Hash map of all the fingers of a peer
675 static struct GNUNET_CONTAINER_MultiHashMap32 *finger_hashmap;
680 static struct GNUNET_CORE_Handle *core_api;
683 * The current finger index that we have want to find trail to. We start the
684 * search with value = 0, i.e. successor peer and then go to PREDCESSOR_FINGER_ID
685 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
686 * we reset this index to 0.
688 static unsigned int current_search_finger_index;
692 * Called when core is ready to send a message we asked for
693 * out to the destination.
695 * @param cls the 'struct FriendInfo' of the target friend
696 * @param size number of bytes available in buf
697 * @param buf where the callee should write the message
698 * @return number of bytes written to buf
701 core_transmit_notify (void *cls, size_t size, void *buf)
703 struct FriendInfo *peer = cls;
705 struct P2PPendingMessage *pending;
710 while ((NULL != (pending = peer->head)) &&
711 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
713 peer->pending_count--;
714 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
715 GNUNET_free (pending);
719 /* no messages pending */
725 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
726 GNUNET_CORE_PRIO_BEST_EFFORT,
727 GNUNET_TIME_absolute_get_remaining
728 (pending->timeout), &peer->id,
729 ntohs (pending->msg->size),
730 &core_transmit_notify, peer);
731 GNUNET_break (NULL != peer->th);
735 while ((NULL != (pending = peer->head)) &&
736 (size - off >= (msize = ntohs (pending->msg->size))))
738 GNUNET_STATISTICS_update (GDS_stats,
740 ("# Bytes transmitted to other peers"), msize,
742 memcpy (&cbuf[off], pending->msg, msize);
744 peer->pending_count--;
745 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
746 GNUNET_free (pending);
748 if (peer->head != NULL)
751 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
752 GNUNET_CORE_PRIO_BEST_EFFORT,
753 GNUNET_TIME_absolute_get_remaining
754 (pending->timeout), &peer->id, msize,
755 &core_transmit_notify, peer);
756 GNUNET_break (NULL != peer->th);
764 * FIXME: assertion fails at the end of this function. also in core_api.c at 1299.
765 * Transmit all messages in the friend's message queue.
767 * @param peer message queue to process
770 process_friend_queue (struct FriendInfo *peer)
772 struct P2PPendingMessage *pending;
774 if (NULL == (pending = peer->head))
776 if (NULL != peer->th)
779 GNUNET_STATISTICS_update (GDS_stats,
781 ("# Bytes of bandwidth requested from core"),
782 ntohs (pending->msg->size), GNUNET_NO);
785 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
787 GNUNET_TIME_absolute_get_remaining
788 (pending->timeout), &peer->id,
789 ntohs (pending->msg->size),
790 &core_transmit_notify, peer);
791 GNUNET_break (NULL != peer->th);
796 * Construct a trail setup message and forward it to target_friend
797 * @param source_peer Source peer which wants to setup the trail
798 * @param ultimate_destination_finger Peer identity closest to this value will
799 * be finger to @a source_peer
800 * @param next_destination Peer which should get the packet. I can be same as
801 * target_friend or different.
802 * @param target_friend Friend to which message is forwarded now.
803 * @param trail_length Total number of peers in trail setup so far.
804 * @param trail_peer_list Trail setup so far
805 * @param finger_map_index Index in finger map for which we are looking for finger.
806 * @param trail_id Unique identifier for the trail we are trying to setup.
807 * @param intermediate_trail_id Trail id of any intermediate trail we may have to
808 * traverse during trail setup. If not used then set to
812 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity source_peer,
813 uint64_t ultimate_destination_finger,
814 struct GNUNET_PeerIdentity next_destination,
815 struct FriendInfo *target_friend,
816 unsigned int trail_length,
817 const struct GNUNET_PeerIdentity *trail_peer_list,
818 unsigned int finger_map_index,
819 struct GNUNET_HashCode new_trail_id,
820 struct GNUNET_HashCode *intermediate_trail_id)
822 struct P2PPendingMessage *pending;
823 struct PeerTrailSetupMessage *tsm;
824 struct GNUNET_PeerIdentity *peer_list;
827 msize = sizeof (struct PeerTrailSetupMessage) +
828 (trail_length * sizeof (struct GNUNET_PeerIdentity));
830 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
836 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
838 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
842 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
843 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
844 tsm = (struct PeerTrailSetupMessage *) &pending[1];
845 pending->msg = &tsm->header;
846 tsm->header.size = htons (msize);
847 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
848 tsm->ultimate_destination_finger = GNUNET_htonll (ultimate_destination_finger);
849 tsm->source_peer = source_peer;
850 tsm->next_destination = next_destination;
851 tsm->trail_length = htonl (trail_length);
852 tsm->finger_map_index = htonl (finger_map_index);
853 tsm->new_trail_id = new_trail_id;
854 if (NULL == intermediate_trail_id)
855 memset (tsm->intermediate_trail_id, 0, sizeof (tsm->intermediate_trail_id));
857 tsm->intermediate_trail_id = *intermediate_trail_id;
858 if (trail_length > 0)
860 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
861 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
864 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
865 target_friend->pending_count++;
866 process_friend_queue (target_friend);
871 * Construct a trail setup result message and forward it to target friend.
872 * @param destination_peer Peer which will get the trail to one of its finger.
873 * @param source_finger Peer to which the trail has been setup to.
874 * @param target_friend Friend to which this message should be forwarded.
875 * @param trail_length Numbers of peers in the trail.
876 * @param trail_peer_list Peers which are part of the trail from source to destination.
877 * @param finger_map_index Index in finger peer map
878 * @param trail_id Unique identifier of the trail.
881 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity destination_peer,
882 struct GNUNET_PeerIdentity source_finger,
883 struct FriendInfo *target_friend,
884 unsigned int trail_length,
885 const struct GNUNET_PeerIdentity *trail_peer_list,
886 unsigned int finger_map_index,
887 struct GNUNET_HashCode trail_id)
889 struct P2PPendingMessage *pending;
890 struct PeerTrailSetupResultMessage *tsrm;
891 struct GNUNET_PeerIdentity *peer_list;
894 msize = sizeof (struct PeerTrailSetupResultMessage) +
895 (trail_length * sizeof (struct GNUNET_PeerIdentity));
897 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
903 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
905 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
909 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
910 pending->importance = 0;
911 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
912 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
913 pending->msg = &tsrm->header;
914 tsrm->header.size = htons (msize);
915 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
916 tsrm->destination_peer = destination_peer;
917 tsrm->finger_identity = source_finger;
918 tsrm->trail_length = htonl (trail_length);
919 tsrm->finger_map_index = htonl (finger_map_index);
920 tsrm->trail_id = trail_id;
922 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
923 if (trail_length > 0)
925 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
927 /* Send the message to chosen friend. */
928 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
929 target_friend->pending_count++;
930 process_friend_queue (target_friend);
935 * Send trail rejection message to next_hop
936 * @param source_peer Source peer which is trying to setup the trail.
937 * @param finger_identity Peer closest to this value will be @a source_peer's finger
938 * @param congested_peer Peer which sent this message as it is congested.
939 * @param next_hop Peer to which we are forwarding this message.
940 * @param finger_map_index Index in finger peermap for which we are searching for finger.
941 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
943 * @param trail_length Total number of peers in trail_peer_list
944 * @param trail_id Unique identifier of this trail.
945 * @param congestion_timeout Duration given by congested peer as an estimate of
946 * how long it may remain congested.
949 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
950 uint64_t finger_identity,
951 struct GNUNET_PeerIdentity congested_peer,
952 unsigned int finger_map_index,
953 struct GNUNET_PeerIdentity *trail_peer_list,
954 unsigned int trail_length,
955 struct GNUNET_HashCode trail_id,
956 struct FriendInfo *target_friend,
957 const struct GNUNET_TIME_Relative congestion_timeout)
959 struct PeerTrailRejectionMessage *trm;
960 struct P2PPendingMessage *pending;
961 struct GNUNET_PeerIdentity *peer_list;
964 msize = sizeof (struct PeerTrailRejectionMessage) +
965 (trail_length * sizeof (struct GNUNET_PeerIdentity));
967 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
973 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
975 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
979 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
980 pending->importance = 0;
981 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
982 trm = (struct PeerTrailRejectionMessage *)&pending[1];
983 pending->msg = &trm->header;
984 trm->header.size = htons (msize);
985 trm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION);
986 trm->source_peer = source_peer;
987 trm->congested_peer = congested_peer;
988 trm->congestion_time = congestion_timeout;
989 trm->finger_map_index = htonl (finger_map_index);
990 trm->trail_id = trail_id;
992 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
993 if (trail_length > 0)
995 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
997 /* Send the message to chosen friend. */
998 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
999 target_friend->pending_count++;
1000 process_friend_queue (target_friend);
1005 * Construct a verify successor message and forward it to target_friend.
1006 * @param source_peer Peer which wants to verify its successor.
1007 * @param successor Peer which is @a source_peer's current successor.
1008 * @param trail_id Identifier of trail to reach successor.
1009 * @param trail Trail to reach from source_peer to successor
1010 * @param trail_length Total number of peers in @a trail.
1011 * @param target_friend Message send to this friend.
1014 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1015 struct GNUNET_PeerIdentity successor,
1016 const struct GNUNET_HashCode trail_id,
1017 struct GNUNET_PeerIdentity *trail,
1018 unsigned int trail_length,
1019 struct FriendInfo *target_friend)
1021 struct PeerVerifySuccessorMessage *vsm;
1022 struct P2PPendingMessage *pending;
1023 struct GNUNET_PeerIdentity *peer_list;
1026 msize = sizeof (struct PeerVerifySuccessorMessage);
1027 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1033 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1035 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1039 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1040 pending->importance = 0; /* FIXME */
1041 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1042 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1043 pending->msg = &vsm->header;
1044 vsm->header.size = htons (msize);
1045 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1046 vsm->source_peer = source_peer;
1047 vsm->successor = successor;
1048 vsm->trail_id = trail_id;
1049 vsm->trail_length = htonl (trail_length);
1051 if (trail_length > 0)
1053 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1054 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1057 /* Send the message to chosen friend. */
1058 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1059 target_friend->pending_count++;
1060 process_friend_queue (target_friend);
1065 * Construct a trail teardown message and send it to target_friend
1066 * @param source_peer Source of the trail.
1067 * @param destination_peer Destination of the trail.
1068 * @param trail_id Unique identifier of the trail.
1069 * @param trail_direction Direction of trail.
1070 * @param target_friend Friend to get this message.
1073 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_PeerIdentity source_peer,
1074 struct GNUNET_PeerIdentity destination_peer,
1075 struct GNUNET_HashCode trail_id,
1076 enum GDS_ROUTING_trail_direction trail_direction,
1077 struct FriendInfo *target_friend)
1079 struct PeerTrailTearDownMessage *ttdm;
1080 struct P2PPendingMessage *pending;
1083 msize = sizeof (struct PeerTrailTearDownMessage);
1085 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1091 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1093 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1097 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1098 pending->importance = 0; /* FIXME */
1099 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1100 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1101 pending->msg = &ttdm->header;
1102 ttdm->header.size = htons (msize);
1103 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1104 ttdm->source_peer = source_peer;
1105 ttdm->destination_peer = destination_peer;
1106 ttdm->TRAIL_ID = trail_id;
1107 ttdm->trail_direction = htonl (trail_direction);
1109 /* Send the message to chosen friend. */
1110 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1111 target_friend->pending_count++;
1112 process_friend_queue (target_friend);
1117 * Construct a verify successor message and send it to target_friend
1118 * @param destination_peer
1119 * @param source_successor
1120 * @param succ_predecessor
1123 * @param trail_length
1124 * @param target_friend
1127 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity destination_peer,
1128 struct GNUNET_PeerIdentity source_successor,
1129 struct GNUNET_PeerIdentity succ_predecessor,
1130 struct GNUNET_HashCode trail_id,
1131 const struct GNUNET_PeerIdentity *trail,
1132 unsigned int trail_length,
1133 enum GDS_ROUTING_trail_direction trail_direction,
1134 struct FriendInfo *target_friend)
1136 struct PeerVerifySuccessorResultMessage *vsmr;
1137 struct P2PPendingMessage *pending;
1138 struct GNUNET_PeerIdentity *peer_list;
1141 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1142 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1144 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1150 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1152 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1156 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1157 pending->importance = 0; /* FIXME */
1158 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1159 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1160 pending->msg = &vsmr->header;
1161 vsmr->header.size = htons (msize);
1162 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1163 vsmr->destination_peer = destination_peer;
1164 vsmr->my_predecessor = succ_predecessor;
1165 vsmr->source_successor = source_successor;
1166 vsmr->trail_direction = htonl (trail_direction);
1168 if (trail_length > 0)
1170 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1171 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1174 /* Send the message to chosen friend. */
1175 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1176 target_friend->pending_count++;
1177 process_friend_queue (target_friend);
1182 * Construct a notify new successor message and send it to target_friend
1183 * @param source_peer
1184 * @param new_successor
1185 * @param new_successor_trail
1186 * @param new_successor_trail_length
1187 * @param new_succesor_trail_id
1190 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1191 struct GNUNET_PeerIdentity new_successor,
1192 struct GNUNET_PeerIdentity *new_successor_trail,
1193 unsigned int new_successor_trail_length,
1194 struct GNUNET_HashCode new_succesor_trail_id,
1195 struct FriendInfo *target_friend)
1197 struct PeerNotifyNewSuccessorMessage *nsm;
1198 struct P2PPendingMessage *pending;
1199 struct GNUNET_PeerIdentity *peer_list;
1202 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1203 (new_successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1205 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1211 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1213 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1217 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1218 pending->importance = 0; /* FIXME */
1219 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1220 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1221 pending->msg = &nsm->header;
1222 nsm->header.size = htons (msize);
1223 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1224 nsm->source_peer = source_peer;
1225 nsm->destination_peer = new_successor;
1226 nsm->trail_length = htonl (new_successor_trail_length);
1227 nsm->trail_id = new_succesor_trail_id;
1228 if (new_successor_trail_length > 0)
1230 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1231 memcpy (peer_list, new_successor_trail,
1232 new_successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1235 /* Send the message to chosen friend. */
1236 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1237 target_friend->pending_count++;
1238 process_friend_queue (target_friend);
1243 * Construct an add_trail message and send it to target_friend
1244 * @param source_peer Source of the trail.
1245 * @param destination_peer Destination of the trail.
1246 * @param trail_id Unique identifer of the trail
1247 * @param trail Trail from @a source_peer to @a destination_peer
1248 * @param trail_length Total number of peers in @a trail.
1249 * @param target_friend Next peer to get this message.
1252 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1253 struct GNUNET_PeerIdentity destination_peer,
1254 struct GNUNET_HashCode trail_id,
1255 struct GNUNET_PeerIdentity *trail,
1256 unsigned int trail_length,
1257 struct FriendInfo *target_friend)
1259 struct PeerAddTrailMessage *adm;
1260 struct GNUNET_PeerIdentity *peer_list;
1261 struct P2PPendingMessage *pending;
1264 msize = sizeof (struct PeerAddTrailMessage) +
1265 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1267 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1273 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1275 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1279 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1280 pending->importance = 0; /* FIXME */
1281 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1282 adm = (struct PeerAddTrailMessage *) &pending[1];
1283 pending->msg = &adm->header;
1284 adm->header.size = htons (msize);
1285 adm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL);
1286 adm->source_peer = source_peer;
1287 adm->destination_peer = destination_peer;
1288 adm->trail_length = htonl (trail_length);
1289 adm->trail_id = trail_id;
1291 if (trail_length > 0)
1293 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1294 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1297 /* Send the message to chosen friend. */
1298 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1299 target_friend->pending_count++;
1300 process_friend_queue (target_friend);
1306 * Merge into "teardown", add source and "last/new_first" in message struct.
1307 * Construct a trail compression message and send it to target_friend.
1308 * @param source_peer Source of the trail.
1309 * @param destination_finger Destination of trail.
1310 * @param trail_id Unique identifier of trail.
1311 * @param first_friend First hop in compressed trail to reach from source to finger
1312 * @param target_friend Next friend to get this message.
1315 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1316 struct GNUNET_PeerIdentity destination_peer,
1317 struct GNUNET_HashCode trail_id,
1318 struct GNUNET_PeerIdentity first_friend,
1319 struct FriendInfo *target_friend)
1321 struct P2PPendingMessage *pending;
1322 struct PeerTrailCompressionMessage *tcm;
1325 msize = sizeof (struct PeerTrailCompressionMessage);
1327 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1333 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1335 GNUNET_STATISTICS_update (GDS_stats,
1336 gettext_noop ("# P2P messages dropped due to full queue"),
1340 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1341 pending->importance = 0; /* FIXME */
1342 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1343 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1344 pending->msg = &tcm->header;
1345 tcm->header.size = htons (msize);
1346 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION);
1347 tcm->source_peer = source_peer;
1348 tcm->new_first_friend = first_friend;
1349 tcm->trail_id = trail_id;
1350 tcm->destination_peer = destination_peer;
1352 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1353 target_friend->pending_count++;
1354 process_friend_queue (target_friend);
1360 * Seach my location in trail.
1361 * @param trail List of peers
1362 * @return my_index if found
1363 * -1 if no entry found.
1366 search_my_index (const struct GNUNET_PeerIdentity *trail,
1371 for (i = 0; i < trail_length; i++)
1373 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1382 * Iterate over the list of all the trails to reach Finger. In case the first
1383 * friend to reach the finger has crossed the trail threshold or is congested,
1384 * then don't select it. In case there multiple available good trails to reach
1385 * to Finger, choose the one with shortest trail length.
1386 * @param finger Finger
1387 * @return struct Correct_Trail which contains the first friend , trail id
1388 * and trail length. NULL in case none of the trails are free.
1390 static struct Correct_Trail *
1391 select_trail_to_finger (struct FingerInfo *finger)
1393 struct FriendInfo *friend;
1394 struct TrailList *iterator;
1395 struct Correct_Trail *finger_trail;
1398 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1402 finger_trail = GNUNET_new (struct Correct_Trail);
1404 for (i = 0; i < finger->trails_count; i++)
1406 iterator = &finger->trail_list[i];
1407 if (iterator->trail_length > 0)
1409 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1410 &iterator->trail_head->peer);
1414 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1415 &finger->finger_identity);
1418 if ((friend->trails_count < TRAIL_THROUGH_FRIEND_THRESHOLD)||
1419 ((0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us)))
1421 if (iterator->trail_length == 0)
1423 finger_trail->friend = *friend;
1424 //finger_trail->trail_id = 0;
1425 finger_trail->trail_length = 0;
1426 return finger_trail;
1429 if (finger_trail->trail_length > iterator->trail_length)
1431 finger_trail->friend = *friend;
1432 finger_trail->trail_id = iterator->trail_id;
1433 finger_trail->trail_length = iterator->trail_length;
1438 return finger_trail;
1443 * Select closest finger to value.
1444 * @param peer1 First peer
1445 * @param peer2 Second peer
1446 * @param value Value to be compare
1447 * @return Closest peer
1449 static struct GNUNET_PeerIdentity *
1450 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1451 struct GNUNET_PeerIdentity *peer2,
1454 uint64_t peer1_value;
1455 uint64_t peer2_value;
1457 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1458 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1460 if ((peer1_value <= value) && (value <= peer2_value))
1462 else if ((peer2_value <= value) && (value <= peer1_value))
1464 else if ((peer1_value <= peer2_value) && (peer2_value <= value))
1466 else if ((peer2_value <= peer1_value) && (peer1_value <= value))
1468 else if ((value <= peer1_value) && (peer1_value <= peer2_value))
1470 else /*if ((value <= peer2_value) && (peer2_value <= peer1_value))*/
1476 * Select closest predecessor to value.
1477 * @param peer1 First peer
1478 * @param peer2 Second peer
1479 * @param value Value to be compare
1480 * @return Closest peer
1482 static struct GNUNET_PeerIdentity *
1483 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1484 struct GNUNET_PeerIdentity *peer2,
1487 uint64_t peer1_value;
1488 uint64_t peer2_value;
1490 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1491 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1493 if ((peer1_value <= value) && (value <= peer2_value))
1495 else if ((peer2_value <= value) && (value <= peer1_value))
1497 else if ((peer1_value <= peer2_value) && (peer2_value <= value))
1499 else if ((peer2_value <= peer1_value) && (peer1_value <= value))
1501 else if ((value <= peer1_value) && (peer1_value <= peer2_value))
1503 else /*if ((value <= peer2_value) && (peer2_value <= peer1_value))*/
1509 * Select the closest peer among two peers (which should not be same)
1510 * with respect to value and finger_map_index
1511 * @param peer1 First peer
1512 * @param peer2 Second peer
1513 * @param value Value relative to which we find the closest
1514 * @param finger_map_index Index in finger map. If equal to PREDECESSOR_FINGER_ID,
1515 * then we use different logic than other
1517 * @return Closest peer among two peers.
1519 static struct GNUNET_PeerIdentity *
1520 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1521 struct GNUNET_PeerIdentity *peer2,
1523 unsigned int finger_map_index)
1525 struct GNUNET_PeerIdentity *closest_peer;
1527 if (PREDECESSOR_FINGER_ID == finger_map_index)
1528 closest_peer = select_closest_predecessor (peer1, peer2, value);
1530 closest_peer = select_closest_finger (peer1, peer2, value);
1532 return closest_peer;
1537 * Find the successor for destination_finger_value among my_identity, all my
1538 * friend and all my fingers. Don't consider friends or fingers
1539 * which are congested or have crossed the threshold.
1540 * @param destination_finger_value Peer closest to this value will be the next successor.
1541 * @param next_destination [out] Updated to friend identity in case a friend is
1542 * successor, updated to first friend to reach to finger
1543 * in case finger is the destination.
1544 * @param new_intermediate_trail_id [out] In case we finger is the @a next_destination,
1545 * then we updated the field with trail id to reach
1547 * @param finger_map_index Index in finger peermap for which we are
1548 * looking for a finger, to discern between
1549 * IS_PREDECESSOR or not.
1552 static struct GNUNET_PeerIdentity *
1553 find_successor (uint64_t destination_finger_value,
1554 struct GNUNET_PeerIdentity *next_destination,
1555 struct GNUNET_HashCode *new_intermediate_trail_id,
1556 unsigned int finger_map_index)
1558 struct Closest_Peer *successor;
1559 struct GNUNET_PeerIdentity *next_hop;
1560 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1561 struct GNUNET_CONTAINER_MultiHashMap32Iterator *finger_iter;
1562 struct GNUNET_PeerIdentity *closest_peer;
1563 struct Correct_Trail *finger_trail;
1564 struct FriendInfo *friend;
1565 struct FingerInfo *finger;
1568 successor = GNUNET_new (struct Closest_Peer);
1569 memcpy (&successor->value, &my_identity, sizeof (uint64_t));
1570 //successor->trail_id = 0;
1571 successor->next_hop = my_identity;
1572 successor->next_destination = my_identity;
1574 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1575 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1577 GNUNET_assert (GNUNET_YES ==
1578 GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter, NULL,
1579 (const void **)&friend));
1580 if ((friend->trails_count > TRAIL_THROUGH_FRIEND_THRESHOLD)||
1581 (0 != GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us))
1584 closest_peer = select_closest_peer (&my_identity, &friend->id,
1585 destination_finger_value,
1587 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, &friend->id))
1589 memcpy (&successor->value, &friend->id, sizeof (uint64_t));
1590 //successor->trail_id = 0;
1591 successor->next_hop = friend->id;
1592 successor->next_destination = friend->id;
1596 finger_iter = GNUNET_CONTAINER_multihashmap32_iterator_create (finger_hashmap);
1597 for (i = 0; i < GNUNET_CONTAINER_multihashmap32_size (finger_hashmap); i++)
1599 GNUNET_assert (GNUNET_YES ==
1600 GNUNET_CONTAINER_multihashmap32_iterator_next (finger_iter, NULL,
1602 finger_trail = select_trail_to_finger (finger);
1603 if (NULL == finger_trail)
1606 closest_peer = select_closest_peer (&my_identity,
1607 &finger->finger_identity,
1608 destination_finger_value,
1610 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
1611 &finger->finger_identity))
1613 memcpy (&successor->value, &finger->finger_identity, sizeof (uint64_t));
1614 successor->trail_id = finger_trail->trail_id;
1615 successor->next_hop = finger_trail->friend.id;
1616 successor->next_destination = finger->finger_identity;
1620 next_destination = &successor->next_destination;
1621 new_intermediate_trail_id = &successor->trail_id;
1622 next_hop = &successor->next_hop;
1628 * Construct a Put message and send it to target_peer.
1629 * @param key Key for the content
1630 * @param block_type Type of the block
1631 * @param options Routing options
1632 * @param desired_replication_level Desired replication count
1633 * @param current_destination Next current destination which will get this message.
1634 * @param current_source Source for @a current_destination
1635 * @param target_peer Peer to which this message will be forwarded.
1636 * @param hop_count Number of hops traversed so far.
1637 * @param put_path_length Total number of peers in @a put_path
1638 * @param put_path Number of peers traversed so far
1639 * @param expiration_time When does the content expire
1640 * @param data Content to store
1641 * @param data_size Size of content @a data in bytes
1644 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
1645 enum GNUNET_BLOCK_Type block_type,
1646 enum GNUNET_DHT_RouteOption options,
1647 uint32_t desired_replication_level,
1648 struct GNUNET_PeerIdentity current_destination,
1649 struct GNUNET_PeerIdentity current_source,
1650 struct GNUNET_PeerIdentity *target_peer,
1652 uint32_t put_path_length,
1653 struct GNUNET_PeerIdentity *put_path,
1654 struct GNUNET_TIME_Absolute expiration_time,
1655 const void *data, size_t data_size)
1661 * Construct a Get message and send it to target_peer.
1662 * @param key Key for the content
1663 * @param block_type Type of the block
1664 * @param options Routing options
1665 * @param desired_replication_level Desired replication count
1666 * @param current_destination Next current destination which will get this message.
1667 * @param current_source Source for @a current_destination
1668 * @param target_peer Peer to which this message will be forwarded.
1669 * @param hop_count Number of hops traversed so far.
1670 * @param data Content to store
1671 * @param data_size Size of content @a data in bytes
1672 * @param get_path_length Total number of peers in @a get_path
1673 * @param get_path Number of peers traversed so far
1676 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
1677 enum GNUNET_BLOCK_Type block_type,
1678 enum GNUNET_DHT_RouteOption options,
1679 uint32_t desired_replication_level,
1680 struct GNUNET_PeerIdentity current_destination,
1681 struct GNUNET_PeerIdentity current_source,
1682 struct GNUNET_PeerIdentity *target_peer,
1684 uint32_t get_path_length,
1685 struct GNUNET_PeerIdentity *get_path)
1692 * Send the get result to requesting client.
1693 * @param key Key of the requested data.
1694 * @param type Block type
1695 * @param target_peer Next peer to forward the message to.
1696 * @param source_peer Peer which has the data for the key.
1697 * @param put_path_length Number of peers in @a put_path
1698 * @param put_path Path taken to put the data at its stored location.
1699 * @param get_path_length Number of peers in @a get_path
1700 * @param get_path Path taken to reach to the location of the key.
1701 * @param expiration When will this result expire?
1702 * @param data Payload to store
1703 * @param data_size Size of the @a data
1706 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
1707 enum GNUNET_BLOCK_Type type,
1708 struct GNUNET_PeerIdentity *target_peer,
1709 struct GNUNET_PeerIdentity *source_peer,
1710 unsigned int put_path_length,
1711 const struct GNUNET_PeerIdentity *put_path,
1712 unsigned int get_path_length,
1713 struct GNUNET_PeerIdentity *get_path,
1714 struct GNUNET_TIME_Absolute expiration,
1715 const void *data, size_t data_size)
1722 * Randomly choose one of your friends (which is not congested and have not crossed
1723 * trail threshold) from the friends_peer map
1724 * @return Friend Randomly chosen friend.
1725 * NULL in case friend peermap is empty, or all the friends are either
1726 * congested or have crossed trail threshold.
1728 static struct FriendInfo *
1729 select_random_friend ()
1731 unsigned int current_size;
1734 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1735 struct GNUNET_PeerIdentity key_ret;
1736 struct FriendInfo *friend;
1738 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1739 if (0 == current_size)
1742 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1743 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1745 for (j = 0; j < index ; j++)
1746 GNUNET_assert (GNUNET_YES ==
1747 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
1750 if (j == current_size)
1753 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1754 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1757 GNUNET_assert (GNUNET_YES ==
1758 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
1760 (const void **)&friend));
1763 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1764 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us))
1770 } while (j != index);
1772 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1778 * FIXME: pass current_search_finger_index as parameter
1779 * Compute finger_identity to which we want to setup the trail
1780 * @return finger_identity
1783 compute_finger_identity()
1787 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1788 my_id64 = GNUNET_ntohll (my_id64);
1789 return (my_id64 + (unsigned long) pow (2, current_search_finger_index));
1794 * Compute immediate predecessor identity in the network.
1795 * @return peer identity of immediate predecessor.
1798 compute_predecessor_identity()
1802 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1803 my_id64 = GNUNET_ntohll (my_id64);
1804 return (my_id64 -1);
1809 * Choose a random friend and start looking for the trail to reach to
1810 * finger identity through this random friend.
1812 * @param cls closure for this task
1813 * @param tc the context under which the task is running
1816 send_find_finger_trail_message (void *cls,
1817 const struct GNUNET_SCHEDULER_TaskContext *tc)
1819 struct FriendInfo *target_friend;
1820 struct GNUNET_TIME_Relative next_send_time;
1821 struct GNUNET_HashCode trail_id;
1822 unsigned int finger_map_index;
1823 uint64_t finger_identity;
1825 next_send_time.rel_value_us =
1826 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1827 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1828 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1829 find_finger_trail_task =
1830 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1833 target_friend = select_random_friend ();
1834 if (NULL == target_friend)
1839 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
1841 finger_identity = compute_predecessor_identity();
1845 finger_identity = compute_finger_identity();
1848 finger_map_index = current_search_finger_index;
1850 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
1851 &trail_id, sizeof (trail_id));
1852 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_identity,
1853 target_friend->id, target_friend, 0, NULL,
1854 finger_map_index, trail_id, NULL);
1859 * In case there are already maximum number of possible trails to reach to a
1860 * finger, then check if the new trail's length is lesser than any of the
1862 * If yes then replace that old trail by new trail.
1864 * Note: Here we are taking length as a parameter to choose the best possible
1865 * trail, but there could be other parameters also like:
1866 * 1. duration of existence of a trail - older the better.
1867 * 2. if the new trail is completely disjoint than the
1868 * other trails, then may be choosing it is better.
1870 * @param existing_finger
1871 * @param new_finger_trail
1872 * @param new_finger_trail_length
1873 * @param new_finger_trail_id
1876 select_and_replace_trail (struct FingerInfo *existing_finger,
1877 struct GNUNET_PeerIdentity *new_trail,
1878 unsigned int new_trail_length,
1879 struct GNUNET_HashCode new_trail_id)
1881 struct TrailList *trail_list_iterator;
1882 unsigned int largest_trail_length;
1883 unsigned int largest_trail_index;
1884 struct Trail *trail_element;
1887 largest_trail_length = new_trail_length;
1888 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
1890 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
1892 for (i = 0; i < existing_finger->trails_count; i++)
1894 trail_list_iterator = &existing_finger->trail_list[i];
1895 if (trail_list_iterator->trail_length > largest_trail_length)
1897 largest_trail_length = trail_list_iterator->trail_length;
1898 largest_trail_index = i;
1902 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
1904 // tear down new trail: it's not better than the existing ones
1908 /* Send trail teardown message across the replaced trail. */
1909 struct TrailList *replace_trail = &existing_finger->trail_list[largest_trail_index];
1910 struct FriendInfo *target_friend =
1911 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1912 &replace_trail->trail_head->peer);
1914 GDS_NEIGHBOURS_send_trail_teardown (my_identity,
1915 existing_finger->finger_identity,
1916 replace_trail->trail_id,
1917 GDS_ROUTING_SRC_TO_DEST, target_friend);
1918 /* Free the trail. */
1919 while (NULL != (trail_element = replace_trail->trail_head))
1921 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
1922 replace_trail->trail_tail, trail_element);
1923 GNUNET_free (trail_element);
1926 /* Add new trial at that location. */
1928 while (i < new_trail_length)
1930 struct Trail *element = GNUNET_new (struct Trail);
1931 element->peer = new_trail[i];
1933 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
1934 replace_trail->trail_tail,
1941 * Check if the new trail to reach to finger is unique or do we already have
1942 * such a trail present for finger.
1943 * @param existing_finger Finger identity
1944 * @param new_trail New trail to reach @a existing_finger
1945 * @param trail_length Total number of peers in new_trail.
1946 * @return #GNUNET_YES if the new trail is unique
1947 * #GNUNET_NO if same trail is already present.
1950 is_new_trail_unique (struct FingerInfo *existing_finger,
1951 struct GNUNET_PeerIdentity *new_trail,
1952 unsigned int trail_length)
1954 struct TrailList *trail_list_iterator;
1955 struct Trail *trail_element;
1958 int trail_unique = GNUNET_NO;
1960 for (i = 0; i < existing_finger->trails_count; i++)
1962 trail_list_iterator = &existing_finger->trail_list[i];
1963 if (trail_list_iterator->trail_length != trail_length)
1965 trail_element = trail_list_iterator->trail_head;
1966 for (j = 0; j < trail_list_iterator->trail_length; j++)
1968 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
1969 &trail_element->peer))
1971 trail_unique = GNUNET_YES;
1976 return trail_unique;
1981 * Add a new trail to existing finger.
1982 * @param existing_finger
1983 * @param new_finger_trail
1984 * @param new_finger_trail_length
1985 * @param new_finger_trail_id
1988 add_new_trail (struct FingerInfo *existing_finger,
1989 struct GNUNET_PeerIdentity *new_trail,
1990 unsigned int new_trail_length,
1991 struct GNUNET_HashCode new_trail_id)
1993 struct TrailList *trail_list_iterator;
1994 struct FriendInfo *first_friend;
1997 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2003 // FIXME checking trail_head is NOT a valid way to verify an open slot
2004 for (i = 0; existing_finger->trail_list[i]->trail_head != NULL; i++)
2005 GNUNET_assert (i < MAXIMUM_TRAILS_PER_FINGER);
2007 trail_list_iterator = &existing_finger->trail_list[i];
2009 if (new_trail_length > 0)
2010 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2013 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2014 &(existing_finger->finger_identity));
2015 first_friend->trails_count++;
2016 trail_list_iterator->first_friend_trail_count = first_friend->trails_count;
2017 trail_list_iterator->trail_length = new_trail_length;
2019 for (i = 0; i < new_trail_length; i++)
2021 struct Trail *element;
2022 element = GNUNET_new (struct Trail);
2024 element->peer = new_trail[i];
2025 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2026 trail_list_iterator->trail_tail,
2029 existing_finger->trails_count++;
2034 * Send trail teardown message on all trails associated with finger.
2035 * @param finger_to_be_removed
2038 send_trail_teardown (struct FingerInfo *finger)
2040 struct TrailList *trail_list_iterator;
2041 struct FriendInfo *target_friend;
2044 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity, &my_identity)
2045 || (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2046 &finger->finger_identity)))
2049 for (i = 0; i < finger->trails_count; i++)
2051 trail_list_iterator = &finger->trail_list[i];
2052 if (trail_list_iterator->trail_length > 0)
2055 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2056 &trail_list_iterator->trail_head->peer);
2057 // check target_friend
2058 GDS_NEIGHBOURS_send_trail_teardown (my_identity, finger->finger_identity,
2059 trail_list_iterator->trail_id,
2060 GDS_ROUTING_SRC_TO_DEST,
2068 * Decrement the trail count of the first friend to reach the finger
2069 * In case finger is the friend, then decrement its trail count.
2073 decrement_friend_trail_count (struct FingerInfo *finger)
2075 struct TrailList *trail_list_iterator;
2076 struct FriendInfo *target_friend;
2079 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2083 for (i = 0; i < finger->trails_count; i++)
2085 trail_list_iterator = &finger->trail_list[i];
2086 if (trail_list_iterator->trail_length > 0)
2088 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2089 &trail_list_iterator->trail_head->peer);
2092 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2093 &finger->finger_identity);
2095 // check target_friend for NULL
2096 target_friend->trails_count--;
2097 trail_list_iterator->first_friend_trail_count--;
2104 * Free finger and its trail.
2105 * @param finger Finger to be freed.
2108 free_finger (struct FingerInfo *finger)
2110 struct TrailList *trail_list_iterator;
2111 struct Trail *trail_element;
2114 for (i = 0; i < finger->trails_count; i++)
2116 trail_list_iterator = &finger->trail_list[i];
2117 while (NULL != (trail_element = trail_list_iterator->trail_head))
2119 GNUNET_CONTAINER_DLL_remove (trail_list_iterator->trail_head,
2120 trail_list_iterator->trail_tail,
2122 GNUNET_free (trail_element);
2125 GNUNET_free (finger);
2130 * FIXME: merge into finger_table_add
2131 * FIXME: leave as simple a check
2132 * Check if new finger is closer than existing_finger. If both new finger and
2133 * existing finger are same then we may add a new trail (if there is space)
2134 * or choose the best trail among existing trails and new trails.
2135 * @param existing_finger Finger present in finger_peermap at @a finger_map_index
2137 * @param new_finger_identity Peer identity of new finger.
2138 * FIXME: all the following params *should* not be necessary
2139 * @param new_finger_trail Trail to reach from source to new_finger.
2140 * @param new_finger_trail_length Total number of peers in @a new_finger_trail.
2141 * @param trail_id Unique identifier of trail.
2142 * @param finger_map_index Index in finger map.
2143 * @return #GNUNET_YES if the new finger is closest.
2144 * #GNUNET_NO either new_finger and existing_finger are same, or
2145 * existing_finger is closest.
2148 is_new_finger_closest (struct FingerInfo *existing_finger,
2149 struct GNUNET_PeerIdentity new_finger_identity,
2150 struct GNUNET_PeerIdentity *new_finger_trail,
2151 unsigned int new_finger_trail_length,
2152 struct GNUNET_HashCode new_finger_trail_id,
2153 unsigned int finger_map_index)
2155 struct GNUNET_PeerIdentity *closest_peer;
2158 if (NULL == existing_finger)
2161 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
2162 &new_finger_identity))
2164 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2165 closest_peer = select_closest_peer (&existing_finger->finger_identity,
2166 &new_finger_identity,
2167 my_id64, finger_map_index);
2169 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity, closest_peer))
2171 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2172 &new_finger_identity));
2174 send_trail_teardown (existing_finger);
2175 decrement_friend_trail_count (existing_finger);
2176 free_finger (existing_finger);
2182 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
2188 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2189 &(existing_finger->finger_identity)))
2191 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
2192 add_new_trail (existing_finger, new_finger_trail,
2193 new_finger_trail_length, new_finger_trail_id);
2195 select_and_replace_trail (existing_finger, new_finger_trail,
2196 new_finger_trail_length, new_finger_trail_id);
2204 * Add a new entry in finger hashmap at finger_map_index
2205 * @param finger_identity Peer Identity of new finger
2206 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2207 * @param finger_trail_length Total number of peers in @a finger_trail.
2208 * @param trail_id Unique identifier of the trail.
2209 * @param finger_map_index Index in finger hashmap.
2210 * @return #GNUNET_OK if new entry is added
2211 * #GNUNET_NO -- FIXME: need to check what value does hahsmap put
2212 * returns on failure.
2215 add_new_entry (struct GNUNET_PeerIdentity finger_identity,
2216 struct GNUNET_PeerIdentity *finger_trail,
2217 unsigned int finger_trail_length,
2218 struct GNUNET_HashCode trail_id,
2219 unsigned int finger_map_index)
2221 struct FingerInfo *new_entry;
2222 struct FriendInfo *first_trail_hop;
2223 struct TrailList *first_trail;
2226 new_entry = GNUNET_new (struct FingerInfo);
2227 new_entry->finger_identity = finger_identity;
2228 new_entry->finger_map_index = finger_map_index;
2229 new_entry->trails_count = 1;
2231 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2233 if (finger_trail_length > 0)
2235 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2240 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2244 first_trail_hop->trails_count++;
2245 first_trail = &new_entry->trail_list[0];
2246 first_trail->first_friend_trail_count = first_trail_hop->trails_count;
2248 while (i < finger_trail_length)
2250 struct Trail *element = GNUNET_new (struct Trail);
2252 element->next = NULL;
2253 element->prev = NULL;
2254 element->peer = finger_trail[i];
2255 GNUNET_CONTAINER_DLL_insert_tail (first_trail->trail_head,
2256 first_trail->trail_tail,
2262 return GNUNET_CONTAINER_multihashmap32_put (finger_hashmap,
2263 new_entry->finger_map_index,
2265 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
2270 * Scan the trail to check if there is any other friend in the trail other than
2271 * first hop. If yes then shortcut the trail, send trail compression message to
2272 * peers which are no longer part of trail and send back the updated trail
2273 * and trail_length to calling function.
2274 * @param finger_identity Finger whose trail we will scan.
2275 * @param finger_trail [in, out] Trail to reach from source to finger,
2276 * @param finger_trail_length Total number of peers in original finger_trail.
2277 * @param finger_trail_id Unique identifier of the finger trail.
2278 * @return updated trail length in case we shortcut the trail, else original
2282 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2283 const struct GNUNET_PeerIdentity *trail,
2284 unsigned int trail_length,
2285 struct GNUNET_HashCode trail_id)
2287 struct FriendInfo *target_friend;
2290 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2295 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
2297 if (trail_length > 0)
2299 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2301 GDS_NEIGHBOURS_send_trail_compression (my_identity, finger_identity,
2302 trail_id, finger_identity,
2309 for (i = trail_length - 1; i > 0; i--)
2311 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
2313 struct FriendInfo *target_friend;
2316 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2318 GDS_NEIGHBOURS_send_trail_compression (my_identity, finger_identity,
2322 // FIXME WARNING WARNING WARNING rewrite!!! consider directly creating a
2323 // struct TrailList (current) // struct Trial (after renaming).
2325 /* Copy the trail from index i to index trail_length -1 and change
2326 trail length and return */
2327 while (i < trail_length)
2329 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
2337 return trail_length;
2342 * Send verify successor message to your successor on all trails to reach
2344 * @param successor My current successor
2347 send_verify_successor_message (struct FingerInfo *successor)
2349 struct TrailList *trail_list_iterator;
2350 struct GNUNET_HashCode trail_id;
2351 struct GNUNET_PeerIdentity next_hop;
2352 struct FriendInfo *target_friend;
2353 struct GNUNET_PeerIdentity *trail;
2354 unsigned int trail_length;
2358 for (i = 0; i < MAXIMUM_TRAILS_PER_FINGER; i++)
2360 trail_list_iterator = &successor->trail_list[i];
2362 // FIXME check if this entry in the trail list is valid!
2363 // if (NULL == trail_list_iterator->SOMETHING)
2366 if (trail_list_iterator->trail_length > 0)
2368 struct Trail *element;
2370 trail_length = trail_list_iterator->trail_length;
2371 trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
2373 element = trail_list_iterator->trail_head;
2374 for (j = 0; j < trail_length; j++, element = element->next)
2375 trail[j] = element->peer;
2376 next_hop = trail_list_iterator->trail_head->peer;
2382 next_hop = successor->finger_identity;
2384 trail_id = trail_list_iterator->trail_id;
2385 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2386 // check friend for NULL
2387 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
2388 successor->finger_identity,
2389 trail_id, trail, trail_length,
2391 GNUNET_free_non_null (trail);
2397 * Check if there is already an entry in finger peermap for given finger map index.
2398 * If yes, then select the closest finger. If new and existing finger are same,
2399 * the check if you can store more trails. If yes then add trail, else keep the best
2400 * trails to reach to the finger. If the new finger is closest, add it.
2401 * Then, update current_search_finger_index.
2402 * @param new_finger_identity Peer Identity of new finger
2403 * @param new_finger_trail Trail to reach the new finger
2404 * @param new_finger_length Total number of peers in @a new_finger_trail.
2405 * @param finger_map_index Index in finger peermap.
2406 * @param new_finger_trail_id Unique identifier of @new_finger_trail.
2407 * @return #GNUNET_YES if the new entry is added
2408 * #GNUNET_NO if new entry is not added, either it was discarded or
2409 * it was same as existing finger at finger map index.
2412 finger_table_add (struct GNUNET_PeerIdentity new_finger_identity, // "finger_id"
2413 const struct GNUNET_PeerIdentity *new_finger_trail, // "trail"
2414 unsigned int new_finger_trail_length,
2415 unsigned int finger_map_index,
2416 struct GNUNET_HashCode new_finger_trail_id)
2418 struct FingerInfo *existing_finger;
2419 struct FingerInfo *successor;
2420 unsigned int new_entry_added = GNUNET_NO;
2421 int new_finger_updated_trail_length; // new_finger_trail_length
2423 new_finger_updated_trail_length =
2424 scan_and_compress_trail (new_finger_identity, new_finger_trail,
2425 new_finger_trail_length, new_finger_trail_id);
2427 existing_finger = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2430 if (GNUNET_YES == is_new_finger_closest (existing_finger,
2431 new_finger_identity,
2433 new_finger_updated_trail_length,
2434 new_finger_trail_id, finger_map_index))
2436 // send_destroy_existing_finger ...
2437 // free_exisiting_finger ...
2438 GNUNET_assert (GNUNET_YES == add_new_entry (new_finger_identity,
2440 new_finger_updated_trail_length,
2441 new_finger_trail_id,
2443 new_entry_added = GNUNET_YES;
2445 // else if if_new_finger_equal () {
2448 // else // existing finger is closest
2453 // FIXME move block to "update_succesor"
2455 successor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap, 0);
2456 // WARNING FIXME check that current_search_finger_index does not go out of bounds
2457 if (0 == finger_map_index)
2459 current_search_finger_index = PREDECESSOR_FINGER_ID;
2461 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_finger_identity))
2463 send_verify_successor_message (successor);
2466 else if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity,
2467 &(successor->finger_identity)))
2469 current_search_finger_index = 0;
2472 current_search_finger_index = current_search_finger_index - 1;
2475 return new_entry_added;
2480 * Core handler for P2P put messages.
2481 * @param cls closure
2482 * @param peer sender of the request
2483 * @param message message
2484 * @return #GNUNET_OK to keep the connection open,
2485 * #GNUNET_SYSERR to close it (signal serious error)
2488 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2489 const struct GNUNET_MessageHeader *message)
2496 * Core handler for p2p get requests.
2498 * @param cls closure
2499 * @param peer sender of the request
2500 * @param message message
2501 * @return #GNUNET_OK to keep the connection open,
2502 * #GNUNET_SYSERR to close it (signal serious error)
2505 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2506 const struct GNUNET_MessageHeader *message)
2513 * Core handler for get result
2514 * @param cls closure
2515 * @param peer sender of the request
2516 * @param message message
2517 * @return #GNUNET_OK to keep the connection open,
2518 * #GNUNET_SYSERR to close it (signal serious error)
2521 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
2522 const struct GNUNET_MessageHeader *message)
2528 /* Core handle for PeerTrailSetupMessage.
2529 * @param cls closure
2530 * @param message message
2531 * @param peer peer identity this notification is about
2532 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2535 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
2536 const struct GNUNET_MessageHeader *message)
2538 struct PeerTrailSetupMessage *trail_setup;
2539 struct GNUNET_PeerIdentity *trail_peer_list;
2540 struct GNUNET_PeerIdentity next_destination; // "local_best_known_destination"
2541 struct GNUNET_PeerIdentity *current_destination;
2542 struct GNUNET_PeerIdentity *next_hop;
2543 struct GNUNET_PeerIdentity next_peer;
2544 struct FriendInfo *target_friend;
2545 struct GNUNET_PeerIdentity source;
2546 uint64_t ultimate_destination_finger_value;
2547 struct GNUNET_HashCode new_intermediate_trail_id;
2548 struct GNUNET_HashCode intermediate_trail_id;
2549 struct GNUNET_HashCode new_trail_id;
2550 unsigned int finger_map_index;
2551 uint32_t trail_length;
2554 msize = ntohs (message->size);
2555 /* There are PeerId's appended to the end of the message! */
2556 if (msize < sizeof (struct PeerTrailSetupMessage))
2558 GNUNET_break_op (0);
2562 trail_setup = (struct PeerTrailSetupMessage *) message;
2563 trail_length = ntohl (trail_setup->trail_length); // (msize - sizeof (msg)) / sizeof(PI)
2564 // if ((msize - sizeof (msg)) % sizeof(PI) != 0)
2565 if ((msize != sizeof (struct PeerTrailSetupMessage) +
2566 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2568 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2570 GNUNET_break_op (0);
2574 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
2575 current_destination = &trail_setup->next_destination;
2576 intermediate_trail_id = trail_setup->intermediate_trail_id;
2577 new_trail_id = trail_setup->new_trail_id;
2578 ultimate_destination_finger_value = GNUNET_ntohll (trail_setup->ultimate_destination_finger);
2579 source = trail_setup->source_peer;
2580 finger_map_index = ntohl (trail_setup->finger_map_index);
2582 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2584 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2585 GDS_NEIGHBOURS_send_trail_rejection (source, ultimate_destination_finger_value,
2586 my_identity, finger_map_index,
2587 trail_peer_list, trail_length,
2588 new_trail_id, target_friend,
2589 CONGESTION_TIMEOUT);
2593 next_hop = find_successor (ultimate_destination_finger_value, &next_destination,
2594 &new_intermediate_trail_id, finger_map_index);
2596 /* Are we just a part of a trail towards a finger? */
2597 if (0 != (GNUNET_CRYPTO_cmp_peer_identity(&my_identity, current_destination)))
2599 struct GNUNET_PeerIdentity *closest_peer;
2600 // struct GNUNET_PeerIdentity *peer1 =
2601 // GDS_ROUTING_get_next_hop (intermediate_trail_id,
2602 // GDS_ROUTING_SRC_TO_DEST);
2603 /* Is next_destination better than the original best_known_dest? */
2605 // if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_destination,
2606 // current_destination))
2608 // closest_peer = select_closest_peer (peer1, next_hop,
2609 // ultimate_destination_finger_value,
2610 // finger_map_index);
2612 // if (0 == GNUNET_CRYPTO_cmp_peer_identity (peer1, closest_peer) ||
2613 // (0 == GNUNET_CRYPTO_cmp_peer_identity (peer1, next_hop)))
2615 // next_hop = peer1;
2616 // next_destination = *current_destination;
2617 // new_intermediate_trail_id = intermediate_trail_id;
2622 GNUNET_assert (NULL != next_hop);
2623 /* Am I the final destination? */
2624 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))
2626 if (0 == trail_length)
2627 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
2629 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
2631 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
2632 GDS_NEIGHBOURS_send_trail_setup_result (source,
2634 target_friend, trail_length,
2636 finger_map_index, new_trail_id);
2640 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
2642 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2643 peer_list[trail_length] = my_identity;
2644 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2645 GDS_NEIGHBOURS_send_trail_setup (source,
2646 ultimate_destination_finger_value,
2648 target_friend, trail_length + 1, peer_list,
2649 finger_map_index, new_trail_id,
2650 new_intermediate_trail_id);
2657 * Core handle for p2p trail construction result messages.
2659 * @param message message
2660 * @param peer peer identity this notification is about
2661 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2664 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2665 const struct GNUNET_MessageHeader *message)
2667 const struct PeerTrailSetupResultMessage *trail_result;
2668 const struct GNUNET_PeerIdentity *trail_peer_list;
2669 struct GNUNET_PeerIdentity destination_peer;
2670 struct GNUNET_PeerIdentity finger_identity;
2671 uint32_t trail_length;
2672 uint32_t finger_map_index;
2673 struct GNUNET_HashCode trail_id;
2676 msize = ntohs (message->size);
2677 if (msize < sizeof (struct PeerTrailSetupResultMessage))
2679 GNUNET_break_op (0);
2683 trail_result = (const struct PeerTrailSetupResultMessage *) message;
2685 // calculate trail_length with message size, check for % 0
2686 trail_length = ntohl (trail_result->trail_length);
2688 sizeof (struct PeerTrailSetupResultMessage) +
2689 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2691 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2693 GNUNET_break_op (0);
2697 finger_map_index = htonl (trail_result->finger_map_index);
2698 destination_peer = trail_result->destination_peer;
2699 finger_identity = trail_result->finger_identity;
2700 trail_id = trail_result->trail_id;
2701 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
2703 // FIXME: check that trail_peer_list[my_index + 1] == peer or
2704 // my_index == trail_length - 1 AND finger_identity == peer
2706 /* Am I the one who initiated the query? */
2707 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer,
2710 finger_table_add (finger_identity, trail_peer_list,
2712 finger_map_index, trail_id);
2716 struct GNUNET_PeerIdentity next_hop;
2717 struct FriendInfo *target_friend;
2720 my_index = search_my_index(trail_peer_list, trail_length);
2724 return GNUNET_SYSERR;
2729 next_hop = trail_result->destination_peer;
2731 next_hop = trail_peer_list[my_index - 1];
2733 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2734 &(trail_result->finger_identity))))
2736 GDS_ROUTING_add (trail_id, next_hop, *peer);
2739 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2740 GDS_NEIGHBOURS_send_trail_setup_result (destination_peer, finger_identity,
2741 target_friend, trail_length, trail_peer_list,
2742 finger_map_index, trail_id);
2749 * @param trail Trail to be inverted
2750 * @param trail_length Total number of peers in the trail.
2751 * @return Updated trail
2753 static struct GNUNET_PeerIdentity *
2754 invert_trail (struct GNUNET_PeerIdentity *trail,
2755 unsigned int trail_length)
2759 struct GNUNET_PeerIdentity *inverted_trail;
2761 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
2764 j = trail_length - 1;
2765 while (i < trail_length)
2767 inverted_trail[i] = trail[j];
2771 return inverted_trail;
2776 * Check if the new finger can be our predecessor. If yes then update predecessor
2779 * @param new_finger_trail
2780 * @param new_finger_trail_length
2784 is_new_entry_correct_predecessor (struct FingerInfo *my_predecessor,
2785 struct GNUNET_PeerIdentity new_finger,
2786 struct GNUNET_PeerIdentity *new_finger_trail,
2787 unsigned int new_finger_trail_length)
2789 struct GNUNET_PeerIdentity *updated_trail;
2790 struct GNUNET_HashCode new_trail_id;
2792 updated_trail = invert_trail (new_finger_trail, new_finger_trail_length);
2793 if (GNUNET_YES == is_new_finger_closest (my_predecessor, new_finger,
2795 new_finger_trail_length,
2796 new_trail_id, PREDECESSOR_FINGER_ID))
2798 add_new_entry (new_finger, updated_trail, new_finger_trail_length,
2799 new_trail_id, PREDECESSOR_FINGER_ID);
2800 /* FIXME: check where you send add trail message */
2807 * In case the source peer of verify successor message is not my successor,
2808 * then construct a trail from source peer to my current predecessor.
2809 * @param my_predecessor my current predecessor.
2810 * @param current_trail Trail from source to me.
2811 * @param current_trail_length Total number of peers in @a current_trail
2812 * @param new_trail_length [out] Total number of peers in updated trail.
2813 * @return Updated trail from source peer to my_predecessor.
2815 static struct GNUNET_PeerIdentity *
2816 trail_source_to_my_predecessor (struct FingerInfo *my_predecessor,
2817 struct GNUNET_PeerIdentity *current_trail,
2818 unsigned int current_trail_length,
2819 unsigned int *new_trail_length)
2821 struct GNUNET_PeerIdentity *new_trail;
2822 struct TrailList *trail_list_iterator;
2823 struct Trail *trail_iterator;
2826 unsigned int shortest_trail_length = 0;
2827 unsigned int trail_index = 0;
2829 for (i = 0; i < my_predecessor->trails_count; i++)
2831 trail_list_iterator = &my_predecessor->trail_list[i];
2832 if (trail_list_iterator->trail_length > shortest_trail_length)
2834 shortest_trail_length = trail_list_iterator->trail_length;
2838 *new_trail_length = current_trail_length + shortest_trail_length + 1;
2839 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2841 memcpy (new_trail, current_trail,
2842 current_trail_length * sizeof (struct GNUNET_PeerIdentity));
2843 new_trail[current_trail_length + 1] = my_identity;
2846 j = current_trail_length + 1;
2847 trail_list_iterator = &my_predecessor->trail_list[trail_index];
2848 trail_iterator = trail_list_iterator->trail_head;
2849 while ( i < shortest_trail_length)
2851 new_trail[j] = trail_iterator->peer;
2854 trail_iterator = trail_iterator->next;
2857 *new_trail_length = j;
2863 * Core handle for p2p verify successor messages.
2864 * @param cls closure
2865 * @param message message
2866 * @param peer peer identity this notification is about
2867 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2870 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2871 const struct GNUNET_MessageHeader *message)
2873 struct PeerVerifySuccessorMessage *vsm;
2874 struct GNUNET_PeerIdentity successor;
2875 struct GNUNET_PeerIdentity source_peer;
2876 struct GNUNET_PeerIdentity *next_hop;
2877 struct FriendInfo *target_friend;
2878 struct GNUNET_HashCode trail_id;
2879 struct FingerInfo *my_predecessor;
2880 struct GNUNET_PeerIdentity *trail;
2881 struct GNUNET_PeerIdentity *new_trail;
2882 unsigned int trail_length;
2883 unsigned int new_trail_length;
2886 msize = ntohs (message->size);
2887 if (msize != sizeof (struct PeerVerifySuccessorMessage))
2889 GNUNET_break_op (0);
2893 vsm = (struct PeerVerifySuccessorMessage *) message;
2894 trail_length = ntohl (vsm->trail_length);
2895 if ((msize != sizeof (struct PeerVerifySuccessorMessage) +
2896 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2897 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2899 GNUNET_break_op (0);
2902 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
2903 source_peer = vsm->source_peer;
2904 successor = vsm->successor;
2905 trail_id = vsm->trail_id;
2907 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
2909 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
2910 if (NULL == next_hop)
2913 return GNUNET_SYSERR;
2915 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2916 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
2917 trail_id, trail, trail_length,
2922 my_predecessor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2923 PREDECESSOR_FINGER_ID);
2924 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2925 if (GNUNET_NO == is_new_entry_correct_predecessor (my_predecessor, source_peer,
2926 trail, trail_length))
2928 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
2929 &my_predecessor->finger_identity))
2931 new_trail = trail_source_to_my_predecessor (my_predecessor, trail,
2932 trail_length, &new_trail_length);
2937 my_predecessor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2938 PREDECESSOR_FINGER_ID);
2939 GDS_NEIGHBOURS_send_add_trail (my_predecessor->finger_identity,
2940 source_peer, trail_id,
2941 trail, trail_length,
2943 new_trail_length = trail_length;
2944 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2946 memcpy (new_trail, trail, sizeof (struct GNUNET_PeerIdentity) *
2950 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
2951 my_predecessor->finger_identity,
2952 trail_id, new_trail,
2954 GDS_ROUTING_DEST_TO_SRC,
2961 * FIXME: I will keep the logic to remove the old trail to reach from me to
2962 * my old successor here and move adding a new trail from me to new successor to notify
2963 * new successor. And in case if the new successor also take it as predecessor
2964 * then call add_trail.
2965 * Core handle for p2p verify successor result messages.
2966 * @param cls closure
2967 * @param message message
2968 * @param peer peer identity this notification is about
2969 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2972 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2973 const struct GNUNET_MessageHeader *message)
2975 struct PeerVerifySuccessorResultMessage *vsrm;
2976 enum GDS_ROUTING_trail_direction trail_direction;
2977 struct GNUNET_HashCode trail_id;
2978 unsigned int new_trail_length;
2979 struct GNUNET_PeerIdentity *new_trail;
2980 struct GNUNET_PeerIdentity destination_peer;
2981 struct GNUNET_PeerIdentity my_new_successor;
2982 struct GNUNET_PeerIdentity old_successor;
2983 struct GNUNET_PeerIdentity *next_hop;
2984 struct FriendInfo *target_friend;
2987 msize = ntohs (message->size);
2988 if (msize != sizeof (struct PeerVerifySuccessorResultMessage))
2990 GNUNET_break_op (0);
2993 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
2994 new_trail_length = ntohl (vsrm->trail_length);
2995 trail_direction = ntohl (vsrm->trail_direction);
2996 trail_id = vsrm->trail_id;
2999 sizeof (struct PeerVerifySuccessorResultMessage) +
3001 sizeof (struct GNUNET_PeerIdentity)) ||
3003 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3005 GNUNET_break_op (0);
3009 new_trail = (struct GNUNET_PeerIdentity *) &vsrm[1];
3010 destination_peer = vsrm->destination_peer;
3011 my_new_successor = vsrm->my_predecessor;
3012 old_successor = vsrm->source_successor;
3014 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer, &my_identity)))
3016 struct GNUNET_HashCode new_finger_trail_id;
3017 /* FIXME: generate a new trail id. */
3018 if (GNUNET_YES == finger_table_add (my_new_successor,
3021 PREDECESSOR_FINGER_ID, new_finger_trail_id))
3023 if (new_trail_length > 0)
3024 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3027 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3029 GDS_NEIGHBOURS_send_trail_teardown (my_identity, old_successor, trail_id,
3030 GDS_ROUTING_SRC_TO_DEST, target_friend);
3031 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, my_new_successor,
3034 new_finger_trail_id, target_friend);
3039 GNUNET_assert (NULL != (next_hop =
3040 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
3041 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3042 GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
3043 vsrm->source_successor,
3044 my_new_successor, trail_id,
3047 trail_direction, target_friend);
3053 * Core handle for p2p notify new successor messages.
3054 * @param cls closure
3055 * @param message message
3056 * @param peer peer identity this notification is about
3057 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3060 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3061 const struct GNUNET_MessageHeader *message)
3063 struct PeerNotifyNewSuccessorMessage *nsm;
3064 struct GNUNET_PeerIdentity *trail;
3065 struct GNUNET_PeerIdentity source;
3066 struct GNUNET_PeerIdentity destination;
3067 struct FriendInfo *target_friend;
3068 struct GNUNET_HashCode trail_id;
3069 unsigned int my_index;
3070 struct GNUNET_PeerIdentity next_hop;
3072 uint32_t trail_length;
3074 msize = ntohs (message->size);
3075 if (msize != sizeof (struct PeerNotifyNewSuccessorMessage))
3077 GNUNET_break_op (0);
3081 nsm = (struct PeerNotifyNewSuccessorMessage *) message;
3082 trail_length = ntohl (nsm->trail_length);
3084 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3085 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3087 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3089 GNUNET_break_op (0);
3093 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
3094 source = nsm->source_peer;
3095 destination = nsm->destination_peer;
3096 trail_id = nsm->trail_id;
3098 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination))
3100 struct GNUNET_HashCode new_trail_id;
3101 struct FingerInfo *my_predecessor;
3104 GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
3105 PREDECESSOR_FINGER_ID);
3106 /* FIXME: get new_trail_id*/
3108 if (GNUNET_YES == is_new_entry_correct_predecessor (my_predecessor,
3113 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3115 GDS_NEIGHBOURS_send_add_trail (my_identity, source, new_trail_id,
3116 trail, trail_length, target_friend);
3121 my_index = search_my_index (trail, trail_length);
3122 if (GNUNET_SYSERR == my_index)
3124 GNUNET_break_op (0);
3125 return GNUNET_SYSERR;
3127 if (trail_length == my_index)
3128 next_hop = destination;
3130 next_hop = trail[my_index + 1];
3131 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
3132 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3133 GDS_NEIGHBOURS_send_notify_new_successor (source, destination, trail,
3135 trail_id, target_friend);
3141 * FIXME: Here you should keep the trail id with you.
3142 * Core handler for P2P trail rejection message
3143 * @param cls closure
3144 * @param message message
3145 * @param peer peer identity this notification is about
3146 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3149 handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3150 const struct GNUNET_MessageHeader *message)
3152 struct PeerTrailRejectionMessage *trail_rejection;
3153 unsigned int trail_length;
3154 struct GNUNET_PeerIdentity *trail_peer_list;
3155 struct FriendInfo *target_friend;
3156 struct GNUNET_TIME_Relative congestion_timeout;
3157 struct GNUNET_HashCode trail_id;
3158 struct GNUNET_PeerIdentity next_destination;
3159 struct GNUNET_HashCode new_intermediate_trail_id;
3160 struct GNUNET_PeerIdentity next_peer;
3161 struct GNUNET_PeerIdentity source;
3162 struct GNUNET_PeerIdentity *next_hop;
3163 uint64_t ultimate_destination_finger_value;
3164 unsigned int finger_map_index;
3167 msize = ntohs (message->size);
3168 if (msize != sizeof (struct PeerTrailRejectionMessage))
3170 GNUNET_break_op (0);
3174 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3175 trail_length = ntohl (trail_rejection->trail_length);
3177 if ((msize != sizeof (struct PeerTrailRejectionMessage) +
3178 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3180 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3182 GNUNET_break_op (0);
3186 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3187 finger_map_index = ntohl (trail_rejection->finger_map_index);
3188 congestion_timeout = trail_rejection->congestion_time;
3189 source = trail_rejection->source_peer;
3190 trail_id = trail_rejection->trail_id;
3191 ultimate_destination_finger_value =
3192 trail_rejection->ultimate_destination_finger_identity_value;
3194 /* First set the congestion time of the friend that sent you this message. */
3195 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3196 target_friend->congestion_timestamp = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
3197 congestion_timeout);
3199 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
3204 /* If I am congested then pass this message to peer before me in trail. */
3205 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
3207 struct GNUNET_PeerIdentity *new_trail;
3208 unsigned int new_trail_length;
3210 if (trail_length == 1)
3213 new_trail_length = 0;
3218 next_hop = &trail_peer_list[trail_length - 2];
3219 /* Remove myself from the trail. */
3220 new_trail_length = trail_length -1;
3221 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
3222 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
3225 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3226 GDS_NEIGHBOURS_send_trail_rejection (source,
3227 ultimate_destination_finger_value,
3228 my_identity, finger_map_index,
3229 new_trail,new_trail_length,trail_id,
3230 target_friend, CONGESTION_TIMEOUT);
3234 /* Look for next_hop to pass the trail setup message */
3235 next_hop = find_successor (ultimate_destination_finger_value,
3237 &new_intermediate_trail_id,
3240 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
3242 if (0 == trail_length)
3245 next_peer = trail_peer_list[trail_length-1];
3247 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3248 GDS_NEIGHBOURS_send_trail_setup_result (source,
3250 target_friend, trail_length,
3252 finger_map_index, trail_id);
3256 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3258 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3259 peer_list[trail_length] = my_identity;
3261 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3262 GDS_NEIGHBOURS_send_trail_setup (source,
3263 ultimate_destination_finger_value,
3265 target_friend, trail_length + 1, peer_list,
3266 finger_map_index, trail_id,
3267 new_intermediate_trail_id);
3274 * Core handle for p2p trail tear down messages.
3275 * @param cls closure
3276 * @param message message
3277 * @param peer peer identity this notification is about
3278 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3281 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
3282 const struct GNUNET_MessageHeader *message)
3284 struct PeerTrailCompressionMessage *trail_compression;
3285 struct GNUNET_PeerIdentity *next_hop;
3286 struct GNUNET_HashCode trail_id;
3287 struct FriendInfo *target_friend;
3290 msize = ntohs (message->size);
3291 if (msize != sizeof (struct PeerTrailCompressionMessage))
3293 GNUNET_break_op (0);
3297 trail_compression = (struct PeerTrailCompressionMessage *) message;
3298 trail_id = trail_compression->trail_id;
3300 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->new_first_friend),
3303 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->destination_peer),
3306 GDS_ROUTING_update_trail_prev_hop (trail_id,
3307 trail_compression->source_peer);
3312 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
3313 if (NULL == next_hop)
3315 GNUNET_break (0); /*FIXME: How to handle this case. */
3318 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
3319 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3320 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
3321 trail_compression->destination_peer,
3323 trail_compression->new_first_friend,
3330 * Core handler for trail teardown message.
3331 * @param cls closure
3332 * @param message message
3333 * @param peer peer identity this notification is about
3334 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3337 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
3338 const struct GNUNET_MessageHeader *message)
3340 struct PeerTrailTearDownMessage *trail_teardown;
3341 struct GNUNET_HashCode trail_id;
3342 enum GDS_ROUTING_trail_direction trail_direction;
3345 msize = ntohs (message->size);
3346 if (msize != sizeof (struct PeerTrailTearDownMessage))
3348 GNUNET_break_op (0);
3352 trail_teardown = (struct PeerTrailTearDownMessage *) message;
3353 trail_direction = ntohl (trail_teardown->trail_direction);
3354 trail_id = trail_teardown->TRAIL_ID;
3356 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3357 &trail_teardown->destination_peer))
3359 struct GNUNET_PeerIdentity *next_hop;
3360 struct FriendInfo *target_friend;
3362 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
3363 if (NULL == next_hop)
3366 return GNUNET_SYSERR;
3369 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3371 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
3372 GDS_NEIGHBOURS_send_trail_teardown (trail_teardown->source_peer,
3373 trail_teardown->destination_peer,
3374 trail_id, trail_direction,
3382 * Fixme: this function is called only in case in notify new successor, the new
3383 * successor wants to add the source of the peer as its predecessor. Identify
3384 * if there is any other use case where it is required and if yes then adapt the
3386 * Core handle for p2p add trail message.
3387 * @param cls closure
3388 * @param message message
3389 * @param peer peer identity this notification is about
3390 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3393 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
3394 const struct GNUNET_MessageHeader *message)
3396 struct PeerAddTrailMessage *add_trail;
3397 struct GNUNET_PeerIdentity *trail;
3398 struct GNUNET_HashCode trail_id;
3399 struct GNUNET_PeerIdentity destination_peer;
3400 struct GNUNET_PeerIdentity source_peer;
3401 struct GNUNET_PeerIdentity next_hop;
3402 unsigned int trail_length;
3403 unsigned int my_index;
3406 msize = ntohs (message->size);
3407 if (msize != sizeof (struct PeerAddTrailMessage))
3409 GNUNET_break_op (0);
3413 add_trail = (struct PeerAddTrailMessage *) message;
3414 trail_length = ntohl (add_trail->trail_length);
3416 if ((msize < sizeof (struct PeerAddTrailMessage) +
3417 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3419 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3421 GNUNET_break_op (0);
3425 trail = (struct GNUNET_PeerIdentity *)&add_trail[1];
3426 destination_peer = add_trail->destination_peer;
3427 source_peer = add_trail->source_peer;
3428 trail_id = add_trail->trail_id;
3430 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3433 struct FriendInfo *target_friend;
3435 my_index = search_my_index (trail, trail_length);
3436 if (GNUNET_SYSERR == my_index)
3438 GNUNET_break_op (0);
3439 return GNUNET_SYSERR;
3443 next_hop = source_peer;
3445 next_hop = trail[trail_length - 1];
3447 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
3448 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3449 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
3450 trail, trail_length, target_friend);
3457 *FIXME; call send_trail_teardown_message on all the trails of the finger that
3458 * you remove. Also you don't need to decerement friend trail count as that
3459 * friend is removed. But you can not send trail teardown message as the friend
3460 * is disconnected. then you don't have any next_hop. and in case there are
3461 * multiple trails. and friend is the first trail then you remove only the trail.
3462 * Iterate over finger_hashmap, and remove entries if finger is the disconnected
3463 * peer or if disconnected peer is the first friend in the trail to reach the
3465 * @param cls closure
3466 * @param key current public key
3467 * @param value value in the hash map
3468 * @return #GNUNET_YES if we should continue to
3470 * #GNUNET_NO if not.
3473 remove_matching_finger (void *cls,
3477 struct FingerInfo *remove_finger = value;
3478 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
3479 struct TrailList *trail_list;
3482 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
3485 GNUNET_assert (GNUNET_YES ==
3486 GNUNET_CONTAINER_multihashmap32_remove (finger_hashmap,
3489 free_finger (remove_finger);
3493 for (i = 0; i< remove_finger->trails_count; i++)
3495 trail_list = &remove_finger->trail_list[i];
3496 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_list->trail_head->peer,
3499 GNUNET_assert (GNUNET_YES ==
3500 GNUNET_CONTAINER_multihashmap32_remove (finger_hashmap,
3503 free_finger (remove_finger);
3512 * Method called whenever a peer disconnects.
3514 * @param cls closure
3515 * @param peer peer identity this notification is about
3518 handle_core_disconnect (void *cls,
3519 const struct GNUNET_PeerIdentity *peer)
3521 struct FriendInfo *remove_friend;
3523 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
3527 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3529 if (NULL == remove_friend)
3535 GNUNET_assert (GNUNET_SYSERR !=
3536 GNUNET_CONTAINER_multihashmap32_iterate (finger_hashmap,
3537 &remove_matching_finger,
3539 GDS_ROUTING_remove_trail_by_peer (peer);
3540 GNUNET_assert (GNUNET_YES ==
3541 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
3545 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
3548 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3550 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3551 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3559 * Method called whenever a peer connects.
3561 * @param cls closure
3562 * @param peer_identity peer identity this notification is about
3565 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
3567 struct FriendInfo *friend;
3569 /* Check for connect to self message */
3570 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
3573 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
3575 /* If peer already exists in our friend_peermap, then exit. */
3576 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
3582 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
3585 friend = GNUNET_new (struct FriendInfo);
3586 friend->id = *peer_identity;
3588 GNUNET_assert (GNUNET_OK ==
3589 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
3590 peer_identity, friend,
3591 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
3593 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
3594 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
3595 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
3600 * To be called on core init/fail.
3602 * @param cls service closure
3603 * @param identity the public identity of this peer
3606 core_init (void *cls,
3607 const struct GNUNET_PeerIdentity *identity)
3609 my_identity = *identity;
3614 * Initialize neighbours subsystem.
3615 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3618 GDS_NEIGHBOURS_init (void)
3620 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
3621 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
3622 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
3623 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
3624 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
3625 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
3626 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
3627 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
3628 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
3629 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
3630 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION, 0},
3631 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
3632 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL, 0},
3637 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
3638 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
3639 GNUNET_NO, core_handlers);
3640 if (NULL == core_api)
3641 return GNUNET_SYSERR;
3643 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
3644 finger_hashmap = GNUNET_CONTAINER_multihashmap32_create (MAX_FINGERS * 4/3);
3650 * Shutdown neighbours subsystem.
3653 GDS_NEIGHBOURS_done (void)
3655 if (NULL == core_api)
3658 GNUNET_CORE_disconnect (core_api);
3661 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
3662 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
3663 friend_peermap = NULL;
3665 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap32_size (finger_hashmap));
3666 GNUNET_CONTAINER_multihashmap32_destroy (finger_hashmap);
3667 finger_hashmap = NULL;
3669 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3672 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3673 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3681 * @return my identity
3683 struct GNUNET_PeerIdentity
3684 GDS_NEIGHBOURS_get_my_id (void)