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
98 * Wrap around in peer identity circle.
100 #define PEER_IDENTITES_WRAP_AROUND pow(2, 256) - 1
102 GNUNET_NETWORK_STRUCT_BEGIN
105 * P2P Trail setup message
107 struct PeerTrailSetupMessage
110 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
112 struct GNUNET_MessageHeader header;
114 /* Bitmask of options, 1 = IS_PREDECESSOR */
118 * Peer closest to this value will be our finger.
120 uint64_t ultimate_destination_finger;
123 * Source peer which wants to setup the trail to one of its finger.
125 struct GNUNET_PeerIdentity source_peer;
128 * Peer to which this packet is forwarded.
130 struct GNUNET_PeerIdentity next_destination; // rename "best_known_dest"
133 * Index into finger peer map, in Network Byte Order.
135 uint32_t finger_map_index; // remove this, include ultimate_destination_finger in response, calculate index from it
138 * Number of entries in trail_list, in Network Byte Order.
140 uint32_t trail_length GNUNET_PACKED; // remove this, calculte length from message size
143 * Trail id of any intermediate trail we may encounter while doing trail setup.
145 struct GNUNET_HashCode intermediate_trail_id;
148 * Trail id for trail which we are trying to setup.
150 struct GNUNET_HashCode new_trail_id; // rename to "trail_id"
152 /* Trail formed in the process. */
153 /* GNUNET_PeerIdentity trail_list[] */
157 * P2P Trail Setup Result message
159 struct PeerTrailSetupResultMessage
163 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
165 struct GNUNET_MessageHeader header;
168 * Finger to which we have found the path.
170 struct GNUNET_PeerIdentity finger_identity;
173 * Peer which was looking for the trail to finger.
175 struct GNUNET_PeerIdentity destination_peer; // querying_peer
178 * Index into finger peer map in NBO.
180 uint32_t finger_map_index; // flag/option with IS_PREDECESSOR
183 * Number of entries in trail list in NBO.
185 uint32_t trail_length GNUNET_PACKED; // remove, calculate
188 * Identifier of the trail.
190 struct GNUNET_HashCode trail_id;
192 /* Trail from "destination_peer" to finger_identity, NOT including both */
193 /* struct GNUNET_PeerIdentity trail[] */
197 * P2P Verify Successor Message.
199 struct PeerVerifySuccessorMessage
202 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
204 struct GNUNET_MessageHeader header;
207 * Source peer which wants to verify its successor.
209 struct GNUNET_PeerIdentity source_peer;
212 * My current successor.
214 struct GNUNET_PeerIdentity successor;
217 * Identifier of trail to reach from source_peer to successor.
219 struct GNUNET_HashCode trail_id;
222 * Total number of peers to reach from source to successor.
224 unsigned int trail_length;
230 * P2P Verify Successor Result Message
232 struct PeerVerifySuccessorResultMessage
235 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
237 struct GNUNET_MessageHeader header;
240 * Destination peer which sent the request to verify its successor.
242 struct GNUNET_PeerIdentity destination_peer;
245 * Successor to which PeerVerifySuccessorMessage was sent.
247 struct GNUNET_PeerIdentity source_successor;
250 * source_successor's predecessor
252 struct GNUNET_PeerIdentity my_predecessor;
255 * Trail identifier of trail from my_predecessor to source_successor.
257 struct GNUNET_HashCode trail_id;
260 * Direction in which we are looking at the trail.
262 enum GDS_ROUTING_trail_direction trail_direction;
265 * Total number of peers in trail from source_successor to my_predecessor
266 * if my_predecessor is not same as destination_peer.
268 uint32_t trail_length;
270 /* Trail from source_successor to my_predecessor where
271 * my_predecessor != destination_peer*/
275 * P2P Notify New Successor Message.
277 struct PeerNotifyNewSuccessorMessage
280 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
282 struct GNUNET_MessageHeader header;
285 * Source peer which wants to notify its new successor.
287 struct GNUNET_PeerIdentity source_peer;
290 * New successor identity.
292 struct GNUNET_PeerIdentity destination_peer;
295 * Total number of peers in trail from source_peer to destination_peer
297 unsigned int trail_length;
300 * Unique identifier of the trail.
302 struct GNUNET_HashCode trail_id;
308 * P2P Trail Compression Message.
310 struct PeerTrailCompressionMessage
313 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION
315 struct GNUNET_MessageHeader header;
318 * Source peer of this trail.
320 struct GNUNET_PeerIdentity source_peer;
323 * Destination of this trail.
325 struct GNUNET_PeerIdentity destination_peer;
328 * Trail from source_peer to destination_peer compressed such that
329 * new_first_friend is the first hop in the trail from source to
332 struct GNUNET_PeerIdentity new_first_friend;
335 * Unique identifier of trail.
337 struct GNUNET_HashCode trail_id;
342 * P2P Trail Tear Down message.
344 struct PeerTrailTearDownMessage
347 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
349 struct GNUNET_MessageHeader header;
352 * Source peer of the trail.
354 struct GNUNET_PeerIdentity source_peer;
357 * Destination peer of the trail.
359 struct GNUNET_PeerIdentity destination_peer;
362 * Unique identifier of the trail.
364 struct GNUNET_HashCode TRAIL_ID;
367 * Direction of trail.
369 enum GDS_ROUTING_trail_direction trail_direction;
374 * P2P Trail Rejection Message.
376 struct PeerTrailRejectionMessage
379 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
381 struct GNUNET_MessageHeader header;
384 * Source peer which wants to set up the trail.
386 struct GNUNET_PeerIdentity source_peer;
389 * Peer which sent trail rejection message.
391 struct GNUNET_PeerIdentity congested_peer;
394 * Peer identity which will be successor to this value will be finger of
397 uint64_t ultimate_destination_finger_identity_value;
400 * Index in finger peer map of source peer.
402 uint32_t finger_map_index;
405 * Total number of peers in the trail.
407 uint32_t trail_length;
410 * Identifier for the trail source peer is trying to setup.
412 struct GNUNET_HashCode trail_id;
414 * Relative time for which congested_peer will remain congested.
416 struct GNUNET_TIME_Relative congestion_time;
418 /* Trail_list from source_peer to peer which sent the message for trail setup
419 * to congested peer.*/
423 * P2P Add Trail Message.
425 struct PeerAddTrailMessage
428 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL
430 struct GNUNET_MessageHeader header;
433 * Source peer of the routing trail.
435 struct GNUNET_PeerIdentity source_peer;
438 * Destination peer of the routing trail.
440 struct GNUNET_PeerIdentity destination_peer;
443 * Total number of peers from source peer to destination peer.
445 unsigned int trail_length;
448 * Unique identifier of the trail.
450 struct GNUNET_HashCode trail_id;
452 /* Trail from source peer to destination peer. */
455 GNUNET_NETWORK_STRUCT_END
458 * Linked list of messages to send to a particular other peer.
460 struct P2PPendingMessage
463 * Pointer to next item in the list
465 struct P2PPendingMessage *next;
468 * Pointer to previous item in the list
470 struct P2PPendingMessage *prev;
473 * Message importance level. FIXME: used? useful?
475 unsigned int importance;
478 * When does this message time out?
480 struct GNUNET_TIME_Absolute timeout;
483 * Actual message to be sent, allocated at the end of the struct:
484 * // msg = (cast) &pm[1];
485 * // memcpy (&pm[1], data, len);
487 const struct GNUNET_MessageHeader *msg;
493 * Entry in friend_peermap.
500 struct GNUNET_PeerIdentity id;
503 * Number of trails for which this friend is the first hop.
505 unsigned int trails_count;
508 * Count of outstanding messages for this friend.
510 unsigned int pending_count;
513 * In case not 0, then amount of time for which this friend is congested.
515 struct GNUNET_TIME_Absolute congestion_timestamp;
518 * Head of pending messages to be sent to this friend.
520 struct P2PPendingMessage *head;
523 * Tail of pending messages to be sent to this friend.
525 struct P2PPendingMessage *tail;
528 * Core handle for sending messages to this friend.
530 struct GNUNET_CORE_TransmitHandle *th;
535 * An individual trail to reach to a finger.
537 struct Trail // "node" "element" "relay"
540 * Pointer to next item in the list
545 * Pointer to prev item in the list
550 * An element in this trail.
552 struct GNUNET_PeerIdentity peer;
556 * List of all trails to reach a particular finger.
558 struct TrailList // "trail": list of "elements"
563 struct Trail *trail_head;
568 struct Trail *trail_tail;
571 * Unique identifier of this trail.
573 struct GNUNET_HashCode trail_id;
576 * Length of trail pointed
578 unsigned int trail_length;
581 * Number of trails that the first friend of this trail is a part of.
583 unsigned int first_friend_trail_count; // remove this, duplicate variable!
584 // include a pointer to Friend or function that calculates it
588 * An entry in finger_hashmap.
595 struct GNUNET_PeerIdentity finger_identity;
598 * Index in finger peer map
600 uint32_t finger_map_index;
603 * Number of trails setup so far for this finger.
605 uint32_t trails_count;
610 struct TrailList trail_list[MAXIMUM_TRAILS_PER_FINGER]; // OK!
614 * Data structure to keep track of closest peer seen so far in find_successor()
619 * 64 bit value of the peer
624 * Trail id to reach to peer.
626 struct GNUNET_HashCode trail_id;
629 * First hop, NULL in case of friend and my_identity
631 struct GNUNET_PeerIdentity next_hop;
634 * Next destination. In case of friend and my_identity , it is same as next_hop
635 * In case of finger it is finger identity.
637 struct GNUNET_PeerIdentity next_destination;
641 * Data structure to store the trail chosen to reach to finger.
646 * First friend in the trail to reach finger.
648 struct FriendInfo friend;
651 * Identifier of this trail.
653 struct GNUNET_HashCode trail_id;
656 * Total number of peers in this trail.
658 unsigned int trail_length;
662 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
663 * get our first friend.
665 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
668 * Identity of this peer.
670 static struct GNUNET_PeerIdentity my_identity;
673 * Peer map of all the friends of a peer
675 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
678 * Hash map of all the fingers of a peer
680 static struct GNUNET_CONTAINER_MultiHashMap32 *finger_hashmap;
685 static struct GNUNET_CORE_Handle *core_api;
688 * The current finger index that we have want to find trail to. We start the
689 * search with value = 0, i.e. successor peer and then go to PREDCESSOR_FINGER_ID
690 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
691 * we reset this index to 0.
693 static unsigned int current_search_finger_index;
697 * Called when core is ready to send a message we asked for
698 * out to the destination.
700 * @param cls the 'struct FriendInfo' of the target friend
701 * @param size number of bytes available in buf
702 * @param buf where the callee should write the message
703 * @return number of bytes written to buf
706 core_transmit_notify (void *cls, size_t size, void *buf)
708 struct FriendInfo *peer = cls;
710 struct P2PPendingMessage *pending;
715 while ((NULL != (pending = peer->head)) &&
716 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
718 peer->pending_count--;
719 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
720 GNUNET_free (pending);
724 /* no messages pending */
730 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
731 GNUNET_CORE_PRIO_BEST_EFFORT,
732 GNUNET_TIME_absolute_get_remaining
733 (pending->timeout), &peer->id,
734 ntohs (pending->msg->size),
735 &core_transmit_notify, peer);
736 GNUNET_break (NULL != peer->th);
740 while ((NULL != (pending = peer->head)) &&
741 (size - off >= (msize = ntohs (pending->msg->size))))
743 GNUNET_STATISTICS_update (GDS_stats,
745 ("# Bytes transmitted to other peers"), msize,
747 memcpy (&cbuf[off], pending->msg, msize);
749 peer->pending_count--;
750 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
751 GNUNET_free (pending);
753 if (peer->head != NULL)
756 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
757 GNUNET_CORE_PRIO_BEST_EFFORT,
758 GNUNET_TIME_absolute_get_remaining
759 (pending->timeout), &peer->id, msize,
760 &core_transmit_notify, peer);
761 GNUNET_break (NULL != peer->th);
769 * FIXME: assertion fails at the end of this function. also in core_api.c at 1299.
770 * Transmit all messages in the friend's message queue.
772 * @param peer message queue to process
775 process_friend_queue (struct FriendInfo *peer)
777 struct P2PPendingMessage *pending;
779 if (NULL == (pending = peer->head))
781 if (NULL != peer->th)
784 GNUNET_STATISTICS_update (GDS_stats,
786 ("# Bytes of bandwidth requested from core"),
787 ntohs (pending->msg->size), GNUNET_NO);
790 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
792 GNUNET_TIME_absolute_get_remaining
793 (pending->timeout), &peer->id,
794 ntohs (pending->msg->size),
795 &core_transmit_notify, peer);
796 GNUNET_break (NULL != peer->th);
801 * Construct a trail setup message and forward it to target_friend
802 * @param source_peer Source peer which wants to setup the trail
803 * @param ultimate_destination_finger Peer identity closest to this value will
804 * be finger to @a source_peer
805 * @param next_destination Peer which should get the packet. I can be same as
806 * target_friend or different.
807 * @param target_friend Friend to which message is forwarded now.
808 * @param trail_length Total number of peers in trail setup so far.
809 * @param trail_peer_list Trail setup so far
810 * @param finger_map_index Index in finger map for which we are looking for finger.
811 * @param trail_id Unique identifier for the trail we are trying to setup.
812 * @param intermediate_trail_id Trail id of any intermediate trail we may have to
813 * traverse during trail setup. If not used then set to
817 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity source_peer,
818 uint64_t ultimate_destination_finger,
819 struct GNUNET_PeerIdentity next_destination,
820 struct FriendInfo *target_friend,
821 unsigned int trail_length,
822 const struct GNUNET_PeerIdentity *trail_peer_list,
823 unsigned int finger_map_index,
824 struct GNUNET_HashCode new_trail_id,
825 struct GNUNET_HashCode *intermediate_trail_id)
827 struct P2PPendingMessage *pending;
828 struct PeerTrailSetupMessage *tsm;
829 struct GNUNET_PeerIdentity *peer_list;
832 msize = sizeof (struct PeerTrailSetupMessage) +
833 (trail_length * sizeof (struct GNUNET_PeerIdentity));
835 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
841 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
843 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
847 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
848 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
849 tsm = (struct PeerTrailSetupMessage *) &pending[1];
850 pending->msg = &tsm->header;
851 tsm->header.size = htons (msize);
852 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
853 tsm->ultimate_destination_finger = GNUNET_htonll (ultimate_destination_finger);
854 tsm->source_peer = source_peer;
855 tsm->next_destination = next_destination;
856 tsm->trail_length = htonl (trail_length);
857 tsm->finger_map_index = htonl (finger_map_index);
858 tsm->new_trail_id = new_trail_id;
859 if (NULL == intermediate_trail_id)
860 memset (&tsm->intermediate_trail_id, 0, sizeof (tsm->intermediate_trail_id));
862 tsm->intermediate_trail_id = *intermediate_trail_id;
863 if (trail_length > 0)
865 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
866 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
869 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
870 target_friend->pending_count++;
871 process_friend_queue (target_friend);
876 * Construct a trail setup result message and forward it to target friend.
877 * @param destination_peer Peer which will get the trail to one of its finger.
878 * @param source_finger Peer to which the trail has been setup to.
879 * @param target_friend Friend to which this message should be forwarded.
880 * @param trail_length Numbers of peers in the trail.
881 * @param trail_peer_list Peers which are part of the trail from source to destination.
882 * @param finger_map_index Index in finger peer map
883 * @param trail_id Unique identifier of the trail.
886 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity destination_peer,
887 struct GNUNET_PeerIdentity source_finger,
888 struct FriendInfo *target_friend,
889 unsigned int trail_length,
890 const struct GNUNET_PeerIdentity *trail_peer_list,
891 unsigned int finger_map_index,
892 struct GNUNET_HashCode trail_id)
894 struct P2PPendingMessage *pending;
895 struct PeerTrailSetupResultMessage *tsrm;
896 struct GNUNET_PeerIdentity *peer_list;
899 msize = sizeof (struct PeerTrailSetupResultMessage) +
900 (trail_length * sizeof (struct GNUNET_PeerIdentity));
902 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
908 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
910 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
914 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
915 pending->importance = 0;
916 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
917 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
918 pending->msg = &tsrm->header;
919 tsrm->header.size = htons (msize);
920 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
921 tsrm->destination_peer = destination_peer;
922 tsrm->finger_identity = source_finger;
923 tsrm->trail_length = htonl (trail_length);
924 tsrm->finger_map_index = htonl (finger_map_index);
925 tsrm->trail_id = trail_id;
927 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
928 if (trail_length > 0)
930 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
932 /* Send the message to chosen friend. */
933 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
934 target_friend->pending_count++;
935 process_friend_queue (target_friend);
940 * Send trail rejection message to next_hop
941 * @param source_peer Source peer which is trying to setup the trail.
942 * @param finger_identity Peer closest to this value will be @a source_peer's finger
943 * @param congested_peer Peer which sent this message as it is congested.
944 * @param next_hop Peer to which we are forwarding this message.
945 * @param finger_map_index Index in finger peermap for which we are searching for finger.
946 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
948 * @param trail_length Total number of peers in trail_peer_list
949 * @param trail_id Unique identifier of this trail.
950 * @param congestion_timeout Duration given by congested peer as an estimate of
951 * how long it may remain congested.
954 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
955 uint64_t finger_identity,
956 struct GNUNET_PeerIdentity congested_peer,
957 unsigned int finger_map_index,
958 struct GNUNET_PeerIdentity *trail_peer_list,
959 unsigned int trail_length,
960 struct GNUNET_HashCode trail_id,
961 struct FriendInfo *target_friend,
962 const struct GNUNET_TIME_Relative congestion_timeout)
964 struct PeerTrailRejectionMessage *trm;
965 struct P2PPendingMessage *pending;
966 struct GNUNET_PeerIdentity *peer_list;
969 msize = sizeof (struct PeerTrailRejectionMessage) +
970 (trail_length * sizeof (struct GNUNET_PeerIdentity));
972 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
978 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
980 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
984 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
985 pending->importance = 0;
986 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
987 trm = (struct PeerTrailRejectionMessage *)&pending[1];
988 pending->msg = &trm->header;
989 trm->header.size = htons (msize);
990 trm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION);
991 trm->source_peer = source_peer;
992 trm->congested_peer = congested_peer;
993 trm->congestion_time = congestion_timeout;
994 trm->finger_map_index = htonl (finger_map_index);
995 trm->trail_id = trail_id;
997 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
998 if (trail_length > 0)
1000 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1002 /* Send the message to chosen friend. */
1003 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1004 target_friend->pending_count++;
1005 process_friend_queue (target_friend);
1010 * Construct a verify successor message and forward it to target_friend.
1011 * @param source_peer Peer which wants to verify its successor.
1012 * @param successor Peer which is @a source_peer's current successor.
1013 * @param trail_id Identifier of trail to reach successor.
1014 * @param trail Trail to reach from source_peer to successor
1015 * @param trail_length Total number of peers in @a trail.
1016 * @param target_friend Message send to this friend.
1019 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1020 struct GNUNET_PeerIdentity successor,
1021 const struct GNUNET_HashCode trail_id,
1022 struct GNUNET_PeerIdentity *trail,
1023 unsigned int trail_length,
1024 struct FriendInfo *target_friend)
1026 struct PeerVerifySuccessorMessage *vsm;
1027 struct P2PPendingMessage *pending;
1028 struct GNUNET_PeerIdentity *peer_list;
1031 msize = sizeof (struct PeerVerifySuccessorMessage);
1032 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1038 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1040 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1044 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1045 pending->importance = 0; /* FIXME */
1046 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1047 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1048 pending->msg = &vsm->header;
1049 vsm->header.size = htons (msize);
1050 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1051 vsm->source_peer = source_peer;
1052 vsm->successor = successor;
1053 vsm->trail_id = trail_id;
1054 vsm->trail_length = htonl (trail_length);
1056 if (trail_length > 0)
1058 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1059 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1062 /* Send the message to chosen friend. */
1063 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1064 target_friend->pending_count++;
1065 process_friend_queue (target_friend);
1070 * Construct a trail teardown message and send it to target_friend
1071 * @param source_peer Source of the trail.
1072 * @param destination_peer Destination of the trail.
1073 * @param trail_id Unique identifier of the trail.
1074 * @param trail_direction Direction of trail.
1075 * @param target_friend Friend to get this message.
1078 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_PeerIdentity source_peer,
1079 struct GNUNET_PeerIdentity destination_peer,
1080 struct GNUNET_HashCode trail_id,
1081 enum GDS_ROUTING_trail_direction trail_direction,
1082 struct FriendInfo *target_friend)
1084 struct PeerTrailTearDownMessage *ttdm;
1085 struct P2PPendingMessage *pending;
1088 msize = sizeof (struct PeerTrailTearDownMessage);
1090 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1096 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1098 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1102 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1103 pending->importance = 0; /* FIXME */
1104 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1105 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1106 pending->msg = &ttdm->header;
1107 ttdm->header.size = htons (msize);
1108 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1109 ttdm->source_peer = source_peer;
1110 ttdm->destination_peer = destination_peer;
1111 ttdm->TRAIL_ID = trail_id;
1112 ttdm->trail_direction = htonl (trail_direction);
1114 /* Send the message to chosen friend. */
1115 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1116 target_friend->pending_count++;
1117 process_friend_queue (target_friend);
1122 * Construct a verify successor message and send it to target_friend
1123 * @param destination_peer
1124 * @param source_successor
1125 * @param succ_predecessor
1128 * @param trail_length
1129 * @param target_friend
1132 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity destination_peer,
1133 struct GNUNET_PeerIdentity source_successor,
1134 struct GNUNET_PeerIdentity succ_predecessor,
1135 struct GNUNET_HashCode trail_id,
1136 const struct GNUNET_PeerIdentity *trail,
1137 unsigned int trail_length,
1138 enum GDS_ROUTING_trail_direction trail_direction,
1139 struct FriendInfo *target_friend)
1141 struct PeerVerifySuccessorResultMessage *vsmr;
1142 struct P2PPendingMessage *pending;
1143 struct GNUNET_PeerIdentity *peer_list;
1146 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1147 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1149 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1155 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1157 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1161 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1162 pending->importance = 0; /* FIXME */
1163 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1164 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1165 pending->msg = &vsmr->header;
1166 vsmr->header.size = htons (msize);
1167 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1168 vsmr->destination_peer = destination_peer;
1169 vsmr->my_predecessor = succ_predecessor;
1170 vsmr->source_successor = source_successor;
1171 vsmr->trail_direction = htonl (trail_direction);
1173 if (trail_length > 0)
1175 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1176 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1179 /* Send the message to chosen friend. */
1180 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1181 target_friend->pending_count++;
1182 process_friend_queue (target_friend);
1187 * Construct a notify new successor message and send it to target_friend
1188 * @param source_peer
1189 * @param new_successor
1190 * @param new_successor_trail
1191 * @param new_successor_trail_length
1192 * @param new_succesor_trail_id
1195 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1196 struct GNUNET_PeerIdentity new_successor,
1197 struct GNUNET_PeerIdentity *new_successor_trail,
1198 unsigned int new_successor_trail_length,
1199 struct GNUNET_HashCode new_succesor_trail_id,
1200 struct FriendInfo *target_friend)
1202 struct PeerNotifyNewSuccessorMessage *nsm;
1203 struct P2PPendingMessage *pending;
1204 struct GNUNET_PeerIdentity *peer_list;
1207 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1208 (new_successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1210 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1216 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1218 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1222 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1223 pending->importance = 0; /* FIXME */
1224 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1225 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1226 pending->msg = &nsm->header;
1227 nsm->header.size = htons (msize);
1228 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1229 nsm->source_peer = source_peer;
1230 nsm->destination_peer = new_successor;
1231 nsm->trail_length = htonl (new_successor_trail_length);
1232 nsm->trail_id = new_succesor_trail_id;
1233 if (new_successor_trail_length > 0)
1235 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1236 memcpy (peer_list, new_successor_trail,
1237 new_successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1240 /* Send the message to chosen friend. */
1241 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1242 target_friend->pending_count++;
1243 process_friend_queue (target_friend);
1248 * Construct an add_trail message and send it to target_friend
1249 * @param source_peer Source of the trail.
1250 * @param destination_peer Destination of the trail.
1251 * @param trail_id Unique identifer of the trail
1252 * @param trail Trail from @a source_peer to @a destination_peer
1253 * @param trail_length Total number of peers in @a trail.
1254 * @param target_friend Next peer to get this message.
1257 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1258 struct GNUNET_PeerIdentity destination_peer,
1259 struct GNUNET_HashCode trail_id,
1260 struct GNUNET_PeerIdentity *trail,
1261 unsigned int trail_length,
1262 struct FriendInfo *target_friend)
1264 struct PeerAddTrailMessage *adm;
1265 struct GNUNET_PeerIdentity *peer_list;
1266 struct P2PPendingMessage *pending;
1269 msize = sizeof (struct PeerAddTrailMessage) +
1270 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1272 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1278 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1280 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1284 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1285 pending->importance = 0; /* FIXME */
1286 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1287 adm = (struct PeerAddTrailMessage *) &pending[1];
1288 pending->msg = &adm->header;
1289 adm->header.size = htons (msize);
1290 adm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL);
1291 adm->source_peer = source_peer;
1292 adm->destination_peer = destination_peer;
1293 adm->trail_length = htonl (trail_length);
1294 adm->trail_id = trail_id;
1296 if (trail_length > 0)
1298 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1299 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1302 /* Send the message to chosen friend. */
1303 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1304 target_friend->pending_count++;
1305 process_friend_queue (target_friend);
1311 * Merge into "teardown", add source and "last/new_first" in message struct.
1312 * Construct a trail compression message and send it to target_friend.
1313 * @param source_peer Source of the trail.
1314 * @param destination_finger Destination of trail.
1315 * @param trail_id Unique identifier of trail.
1316 * @param first_friend First hop in compressed trail to reach from source to finger
1317 * @param target_friend Next friend to get this message.
1320 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1321 struct GNUNET_PeerIdentity destination_peer,
1322 struct GNUNET_HashCode trail_id,
1323 struct GNUNET_PeerIdentity first_friend,
1324 struct FriendInfo *target_friend)
1326 struct P2PPendingMessage *pending;
1327 struct PeerTrailCompressionMessage *tcm;
1330 msize = sizeof (struct PeerTrailCompressionMessage);
1332 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1338 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1340 GNUNET_STATISTICS_update (GDS_stats,
1341 gettext_noop ("# P2P messages dropped due to full queue"),
1345 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1346 pending->importance = 0; /* FIXME */
1347 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1348 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1349 pending->msg = &tcm->header;
1350 tcm->header.size = htons (msize);
1351 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION);
1352 tcm->source_peer = source_peer;
1353 tcm->new_first_friend = first_friend;
1354 tcm->trail_id = trail_id;
1355 tcm->destination_peer = destination_peer;
1357 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1358 target_friend->pending_count++;
1359 process_friend_queue (target_friend);
1365 * Seach my location in trail.
1366 * @param trail List of peers
1367 * @return my_index if found
1368 * -1 if no entry found.
1371 search_my_index (const struct GNUNET_PeerIdentity *trail,
1376 for (i = 0; i < trail_length; i++)
1378 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1387 * Iterate over the list of all the trails to reach Finger. In case the first
1388 * friend to reach the finger has crossed the trail threshold or is congested,
1389 * then don't select it. In case there multiple available good trails to reach
1390 * to Finger, choose the one with shortest trail length.
1391 * @param finger Finger
1392 * @return struct Correct_Trail which contains the first friend , trail id
1393 * and trail length. NULL in case none of the trails are free.
1395 static struct Correct_Trail *
1396 select_trail_to_finger (struct FingerInfo *finger)
1398 struct FriendInfo *friend;
1399 struct TrailList *iterator;
1400 struct Correct_Trail *finger_trail;
1403 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1407 finger_trail = GNUNET_new (struct Correct_Trail);
1409 for (i = 0; i < finger->trails_count; i++)
1411 iterator = &finger->trail_list[i];
1412 if (iterator->trail_length > 0)
1414 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1415 &iterator->trail_head->peer);
1419 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1420 &finger->finger_identity);
1423 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD)||
1424 ((0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us)))
1426 if (iterator->trail_length == 0)
1428 finger_trail->friend = *friend;
1429 //finger_trail->trail_id = 0;
1430 finger_trail->trail_length = 0;
1431 return finger_trail;
1434 if (finger_trail->trail_length > iterator->trail_length)
1436 finger_trail->friend = *friend;
1437 finger_trail->trail_id = iterator->trail_id;
1438 finger_trail->trail_length = iterator->trail_length;
1443 return finger_trail;
1448 * Select closest finger to value.
1449 * @param peer1 First peer
1450 * @param peer2 Second peer
1451 * @param value Value to be compare
1452 * @return Closest peer
1454 static struct GNUNET_PeerIdentity *
1455 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1456 struct GNUNET_PeerIdentity *peer2,
1460 uint64_t peer1_value;
1461 uint64_t peer2_value;
1463 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1464 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1466 if ((peer1_value <= value) && (value <= peer2_value))
1468 else if ((peer2_value <= value) && (value <= peer1_value))
1470 else if ((peer1_value <= peer2_value) && (peer2_value <= value))
1472 else if ((peer2_value <= peer1_value) && (peer1_value <= value))
1474 else if ((value <= peer1_value) && (peer1_value <= peer2_value))
1476 else /*if ((value <= peer2_value) && (peer2_value <= peer1_value))*/
1484 * Select closest predecessor to value.
1485 * @param peer1 First peer
1486 * @param peer2 Second peer
1487 * @param value Value to be compare
1488 * @return Closest peer
1490 static struct GNUNET_PeerIdentity *
1491 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1492 struct GNUNET_PeerIdentity *peer2,
1496 uint64_t peer1_value;
1497 uint64_t peer2_value;
1499 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1500 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1508 * Select the closest peer among two peers (which should not be same)
1509 * with respect to value and finger_map_index
1510 * @param peer1 First peer
1511 * @param peer2 Second peer
1512 * @param value Value relative to which we find the closest
1513 * @param finger_map_index Index in finger map. If equal to PREDECESSOR_FINGER_ID,
1514 * then we use different logic than other
1516 * @return Closest peer among two peers.
1518 static struct GNUNET_PeerIdentity *
1519 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1520 struct GNUNET_PeerIdentity *peer2,
1522 unsigned int finger_map_index)
1524 struct GNUNET_PeerIdentity *closest_peer;
1526 if (PREDECESSOR_FINGER_ID == finger_map_index)
1527 closest_peer = select_closest_predecessor (peer1, peer2, value);
1529 closest_peer = select_closest_finger (peer1, peer2, value);
1531 return closest_peer;
1536 * Find the successor for destination_finger_value among my_identity, all my
1537 * friend and all my fingers. Don't consider friends or fingers
1538 * which are congested or have crossed the threshold.
1539 * @param destination_finger_value Peer closest to this value will be the next successor.
1540 * @param next_destination [out] Updated to friend identity in case a friend is
1541 * successor, updated to first friend to reach to finger
1542 * in case finger is the destination.
1543 * @param new_intermediate_trail_id [out] In case we finger is the @a next_destination,
1544 * then we updated the field with trail id to reach
1546 * @param finger_map_index Index in finger peermap for which we are
1547 * looking for a finger, to discern between
1548 * IS_PREDECESSOR or not.
1551 static struct GNUNET_PeerIdentity *
1552 find_successor (uint64_t destination_finger_value,
1553 struct GNUNET_PeerIdentity *next_destination,
1554 struct GNUNET_HashCode *new_intermediate_trail_id,
1555 unsigned int finger_map_index)
1557 struct Closest_Peer *successor;
1558 struct GNUNET_PeerIdentity *next_hop;
1559 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1560 struct GNUNET_CONTAINER_MultiHashMap32Iterator *finger_iter;
1561 struct GNUNET_PeerIdentity *closest_peer;
1562 struct Correct_Trail *finger_trail;
1563 struct FriendInfo *friend;
1564 struct FingerInfo *finger;
1567 successor = GNUNET_new (struct Closest_Peer);
1568 memcpy (&successor->value, &my_identity, sizeof (uint64_t));
1569 //successor->trail_id = 0; /* FIXME:Default value for trail id */
1570 successor->next_hop = my_identity;
1571 successor->next_destination = my_identity;
1573 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1574 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1576 GNUNET_assert (GNUNET_YES ==
1577 GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter, NULL,
1578 (const void **)&friend));
1579 if ((friend->trails_count > TRAILS_THROUGH_FRIEND_THRESHOLD)||
1580 (0 != GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
1583 closest_peer = select_closest_peer (&my_identity, &friend->id,
1584 destination_finger_value,
1586 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, &friend->id))
1588 memcpy (&successor->value, &friend->id, sizeof (uint64_t));
1589 //successor->trail_id = 0;
1590 successor->next_hop = friend->id;
1591 successor->next_destination = friend->id;
1595 finger_iter = GNUNET_CONTAINER_multihashmap32_iterator_create (finger_hashmap);
1596 for (i = 0; i < GNUNET_CONTAINER_multihashmap32_size (finger_hashmap); i++)
1598 GNUNET_assert (GNUNET_YES ==
1599 GNUNET_CONTAINER_multihashmap32_iterator_next (finger_iter, NULL,
1601 finger_trail = select_trail_to_finger (finger);
1602 if (NULL == finger_trail)
1605 closest_peer = select_closest_peer (&my_identity,
1606 &finger->finger_identity,
1607 destination_finger_value,
1609 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
1610 &finger->finger_identity))
1612 memcpy (&successor->value, &finger->finger_identity, sizeof (uint64_t));
1613 successor->trail_id = finger_trail->trail_id;
1614 successor->next_hop = finger_trail->friend.id;
1615 successor->next_destination = finger->finger_identity;
1619 next_destination = &successor->next_destination;
1620 new_intermediate_trail_id = &successor->trail_id;
1621 next_hop = &successor->next_hop;
1627 * Construct a Put message and send it to target_peer.
1628 * @param key Key for the content
1629 * @param block_type Type of the block
1630 * @param options Routing options
1631 * @param desired_replication_level Desired replication count
1632 * @param current_destination Next current destination which will get this message.
1633 * @param current_source Source for @a current_destination
1634 * @param target_peer Peer to which this message will be forwarded.
1635 * @param hop_count Number of hops traversed so far.
1636 * @param put_path_length Total number of peers in @a put_path
1637 * @param put_path Number of peers traversed so far
1638 * @param expiration_time When does the content expire
1639 * @param data Content to store
1640 * @param data_size Size of content @a data in bytes
1643 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
1644 enum GNUNET_BLOCK_Type block_type,
1645 enum GNUNET_DHT_RouteOption options,
1646 uint32_t desired_replication_level,
1647 struct GNUNET_PeerIdentity current_destination,
1648 struct GNUNET_PeerIdentity current_source,
1649 struct GNUNET_PeerIdentity *target_peer,
1651 uint32_t put_path_length,
1652 struct GNUNET_PeerIdentity *put_path,
1653 struct GNUNET_TIME_Absolute expiration_time,
1654 const void *data, size_t data_size)
1660 * Construct a Get message and send it to target_peer.
1661 * @param key Key for the content
1662 * @param block_type Type of the block
1663 * @param options Routing options
1664 * @param desired_replication_level Desired replication count
1665 * @param current_destination Next current destination which will get this message.
1666 * @param current_source Source for @a current_destination
1667 * @param target_peer Peer to which this message will be forwarded.
1668 * @param hop_count Number of hops traversed so far.
1669 * @param data Content to store
1670 * @param data_size Size of content @a data in bytes
1671 * @param get_path_length Total number of peers in @a get_path
1672 * @param get_path Number of peers traversed so far
1675 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
1676 enum GNUNET_BLOCK_Type block_type,
1677 enum GNUNET_DHT_RouteOption options,
1678 uint32_t desired_replication_level,
1679 struct GNUNET_PeerIdentity current_destination,
1680 struct GNUNET_PeerIdentity current_source,
1681 struct GNUNET_PeerIdentity *target_peer,
1683 uint32_t get_path_length,
1684 struct GNUNET_PeerIdentity *get_path)
1691 * Send the get result to requesting client.
1692 * @param key Key of the requested data.
1693 * @param type Block type
1694 * @param target_peer Next peer to forward the message to.
1695 * @param source_peer Peer which has the data for the key.
1696 * @param put_path_length Number of peers in @a put_path
1697 * @param put_path Path taken to put the data at its stored location.
1698 * @param get_path_length Number of peers in @a get_path
1699 * @param get_path Path taken to reach to the location of the key.
1700 * @param expiration When will this result expire?
1701 * @param data Payload to store
1702 * @param data_size Size of the @a data
1705 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
1706 enum GNUNET_BLOCK_Type type,
1707 struct GNUNET_PeerIdentity *target_peer,
1708 struct GNUNET_PeerIdentity *source_peer,
1709 unsigned int put_path_length,
1710 const struct GNUNET_PeerIdentity *put_path,
1711 unsigned int get_path_length,
1712 struct GNUNET_PeerIdentity *get_path,
1713 struct GNUNET_TIME_Absolute expiration,
1714 const void *data, size_t data_size)
1721 * Randomly choose one of your friends (which is not congested and have not crossed
1722 * trail threshold) from the friends_peer map
1723 * @return Friend Randomly chosen friend.
1724 * NULL in case friend peermap is empty, or all the friends are either
1725 * congested or have crossed trail threshold.
1727 static struct FriendInfo *
1728 select_random_friend ()
1730 unsigned int current_size;
1733 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1734 struct GNUNET_PeerIdentity key_ret;
1735 struct FriendInfo *friend;
1737 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1738 if (0 == current_size)
1741 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1742 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1744 for (j = 0; j < index ; j++)
1745 GNUNET_assert (GNUNET_YES ==
1746 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
1749 if (j == current_size)
1752 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1753 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1756 GNUNET_assert (GNUNET_YES ==
1757 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
1759 (const void **)&friend));
1762 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1763 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
1769 } while (j != index);
1771 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1777 * FIXME: pass current_search_finger_index as parameter
1778 * Compute finger_identity to which we want to setup the trail
1779 * @return finger_identity
1782 compute_finger_identity()
1786 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1787 my_id64 = GNUNET_ntohll (my_id64);
1788 return (my_id64 + (unsigned long) pow (2, current_search_finger_index));
1793 * Compute immediate predecessor identity in the network.
1794 * @return peer identity of immediate predecessor.
1797 compute_predecessor_identity()
1801 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1802 my_id64 = GNUNET_ntohll (my_id64);
1803 return (my_id64 -1);
1808 * Choose a random friend and start looking for the trail to reach to
1809 * finger identity through this random friend.
1811 * @param cls closure for this task
1812 * @param tc the context under which the task is running
1815 send_find_finger_trail_message (void *cls,
1816 const struct GNUNET_SCHEDULER_TaskContext *tc)
1818 struct FriendInfo *target_friend;
1819 struct GNUNET_TIME_Relative next_send_time;
1820 struct GNUNET_HashCode trail_id;
1821 unsigned int finger_map_index;
1822 uint64_t finger_identity;
1824 next_send_time.rel_value_us =
1825 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1826 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1827 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1828 find_finger_trail_task =
1829 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1832 target_friend = select_random_friend ();
1833 if (NULL == target_friend)
1838 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
1840 finger_identity = compute_predecessor_identity();
1844 finger_identity = compute_finger_identity();
1847 finger_map_index = current_search_finger_index;
1849 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
1850 &trail_id, sizeof (trail_id));
1851 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_identity,
1852 target_friend->id, target_friend, 0, NULL,
1853 finger_map_index, trail_id, NULL);
1858 * In case there are already maximum number of possible trails to reach to a
1859 * finger, then check if the new trail's length is lesser than any of the
1861 * If yes then replace that old trail by new trail.
1863 * Note: Here we are taking length as a parameter to choose the best possible
1864 * trail, but there could be other parameters also like:
1865 * 1. duration of existence of a trail - older the better.
1866 * 2. if the new trail is completely disjoint than the
1867 * other trails, then may be choosing it is better.
1869 * @param existing_finger
1870 * @param new_finger_trail
1871 * @param new_finger_trail_length
1872 * @param new_finger_trail_id
1875 select_and_replace_trail (struct FingerInfo *existing_finger,
1876 struct GNUNET_PeerIdentity *new_trail,
1877 unsigned int new_trail_length,
1878 struct GNUNET_HashCode new_trail_id)
1880 struct TrailList *trail_list_iterator;
1881 unsigned int largest_trail_length;
1882 unsigned int largest_trail_index;
1883 struct Trail *trail_element;
1886 largest_trail_length = new_trail_length;
1887 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
1889 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
1891 for (i = 0; i < existing_finger->trails_count; i++)
1893 trail_list_iterator = &existing_finger->trail_list[i];
1894 if (trail_list_iterator->trail_length > largest_trail_length)
1896 largest_trail_length = trail_list_iterator->trail_length;
1897 largest_trail_index = i;
1901 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
1903 // tear down new trail: it's not better than the existing ones
1907 /* Send trail teardown message across the replaced trail. */
1908 struct TrailList *replace_trail = &existing_finger->trail_list[largest_trail_index];
1909 struct FriendInfo *target_friend =
1910 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1911 &replace_trail->trail_head->peer);
1913 GDS_NEIGHBOURS_send_trail_teardown (my_identity,
1914 existing_finger->finger_identity,
1915 replace_trail->trail_id,
1916 GDS_ROUTING_SRC_TO_DEST, target_friend);
1917 /* Free the trail. */
1918 while (NULL != (trail_element = replace_trail->trail_head))
1920 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
1921 replace_trail->trail_tail, trail_element);
1922 GNUNET_free (trail_element);
1925 /* Add new trial at that location. */
1927 while (i < new_trail_length)
1929 struct Trail *element = GNUNET_new (struct Trail);
1930 element->peer = new_trail[i];
1932 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
1933 replace_trail->trail_tail,
1940 * Check if the new trail to reach to finger is unique or do we already have
1941 * such a trail present for finger.
1942 * @param existing_finger Finger identity
1943 * @param new_trail New trail to reach @a existing_finger
1944 * @param trail_length Total number of peers in new_trail.
1945 * @return #GNUNET_YES if the new trail is unique
1946 * #GNUNET_NO if same trail is already present.
1949 is_new_trail_unique (struct FingerInfo *existing_finger,
1950 struct GNUNET_PeerIdentity *new_trail,
1951 unsigned int trail_length)
1953 struct TrailList *trail_list_iterator;
1954 struct Trail *trail_element;
1957 int trail_unique = GNUNET_NO;
1959 for (i = 0; i < existing_finger->trails_count; i++)
1961 trail_list_iterator = &existing_finger->trail_list[i];
1962 if (trail_list_iterator->trail_length != trail_length)
1964 trail_element = trail_list_iterator->trail_head;
1965 for (j = 0; j < trail_list_iterator->trail_length; j++)
1967 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
1968 &trail_element->peer))
1970 trail_unique = GNUNET_YES;
1975 return trail_unique;
1980 * Add a new trail to existing finger.
1981 * @param existing_finger
1982 * @param new_finger_trail
1983 * @param new_finger_trail_length
1984 * @param new_finger_trail_id
1987 add_new_trail (struct FingerInfo *existing_finger,
1988 struct GNUNET_PeerIdentity *new_trail,
1989 unsigned int new_trail_length,
1990 struct GNUNET_HashCode new_trail_id)
1992 struct TrailList *trail_list_iterator;
1993 struct FriendInfo *first_friend;
1996 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2002 // FIXME checking trail_head is NOT a valid way to verify an open slot
2003 for (i = 0; existing_finger->trail_list[i].trail_head != NULL; i++)
2004 GNUNET_assert (i < MAXIMUM_TRAILS_PER_FINGER);
2006 trail_list_iterator = &existing_finger->trail_list[i];
2008 if (new_trail_length > 0)
2009 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2012 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2013 &(existing_finger->finger_identity));
2014 first_friend->trails_count++;
2015 trail_list_iterator->first_friend_trail_count = first_friend->trails_count;
2016 trail_list_iterator->trail_length = new_trail_length;
2018 for (i = 0; i < new_trail_length; i++)
2020 struct Trail *element;
2021 element = GNUNET_new (struct Trail);
2023 element->peer = new_trail[i];
2024 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2025 trail_list_iterator->trail_tail,
2028 existing_finger->trails_count++;
2033 * Send trail teardown message on all trails associated with finger.
2034 * @param finger_to_be_removed
2037 send_trail_teardown (struct FingerInfo *finger)
2039 struct TrailList *trail_list_iterator;
2040 struct FriendInfo *target_friend;
2043 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity, &my_identity)
2044 || (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2045 &finger->finger_identity)))
2048 for (i = 0; i < finger->trails_count; i++)
2050 trail_list_iterator = &finger->trail_list[i];
2051 if (trail_list_iterator->trail_length > 0)
2054 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2055 &trail_list_iterator->trail_head->peer);
2056 // check target_friend
2057 GDS_NEIGHBOURS_send_trail_teardown (my_identity, finger->finger_identity,
2058 trail_list_iterator->trail_id,
2059 GDS_ROUTING_SRC_TO_DEST,
2067 * Decrement the trail count of the first friend to reach the finger
2068 * In case finger is the friend, then decrement its trail count.
2072 decrement_friend_trail_count (struct FingerInfo *finger)
2074 struct TrailList *trail_list_iterator;
2075 struct FriendInfo *target_friend;
2078 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2082 for (i = 0; i < finger->trails_count; i++)
2084 trail_list_iterator = &finger->trail_list[i];
2085 if (trail_list_iterator->trail_length > 0)
2087 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2088 &trail_list_iterator->trail_head->peer);
2091 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2092 &finger->finger_identity);
2094 // check target_friend for NULL
2095 target_friend->trails_count--;
2096 trail_list_iterator->first_friend_trail_count--;
2103 * Free finger and its trail.
2104 * @param finger Finger to be freed.
2107 free_finger (struct FingerInfo *finger)
2109 struct TrailList *trail_list_iterator;
2110 struct Trail *trail_element;
2113 for (i = 0; i < finger->trails_count; i++)
2115 trail_list_iterator = &finger->trail_list[i];
2116 while (NULL != (trail_element = trail_list_iterator->trail_head))
2118 GNUNET_CONTAINER_DLL_remove (trail_list_iterator->trail_head,
2119 trail_list_iterator->trail_tail,
2121 GNUNET_free (trail_element);
2124 GNUNET_free (finger);
2129 * FIXME: merge into finger_table_add
2130 * FIXME: leave as simple a check
2131 * Check if new finger is closer than existing_finger. If both new finger and
2132 * existing finger are same then we may add a new trail (if there is space)
2133 * or choose the best trail among existing trails and new trails.
2134 * @param existing_finger Finger present in finger_peermap at @a finger_map_index
2136 * @param new_finger_identity Peer identity of new finger.
2137 * FIXME: all the following params *should* not be necessary
2138 * @param new_finger_trail Trail to reach from source to new_finger.
2139 * @param new_finger_trail_length Total number of peers in @a new_finger_trail.
2140 * @param trail_id Unique identifier of trail.
2141 * @param finger_map_index Index in finger map.
2142 * @return #GNUNET_YES if the new finger is closest.
2143 * #GNUNET_NO either new_finger and existing_finger are same, or
2144 * existing_finger is closest.
2147 is_new_finger_closest (struct FingerInfo *existing_finger,
2148 struct GNUNET_PeerIdentity new_finger_identity,
2149 struct GNUNET_PeerIdentity *new_finger_trail,
2150 unsigned int new_finger_trail_length,
2151 struct GNUNET_HashCode new_finger_trail_id,
2152 unsigned int finger_map_index)
2154 struct GNUNET_PeerIdentity *closest_peer;
2155 uint64_t finger_identity_value;
2158 if (NULL == existing_finger)
2161 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2162 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
2163 &new_finger_identity))
2165 if (PREDECESSOR_FINGER_ID == finger_map_index)
2166 finger_identity_value = my_id64 - 1;
2168 finger_identity_value = my_id64 + (unsigned long) pow (2, finger_map_index);
2169 closest_peer = select_closest_peer (&existing_finger->finger_identity,
2170 &new_finger_identity,
2171 finger_identity_value, finger_map_index);
2173 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity, closest_peer))
2175 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2176 &new_finger_identity));
2178 send_trail_teardown (existing_finger);
2179 decrement_friend_trail_count (existing_finger);
2180 free_finger (existing_finger);
2186 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
2192 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2193 &(existing_finger->finger_identity)))
2195 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
2196 add_new_trail (existing_finger, new_finger_trail,
2197 new_finger_trail_length, new_finger_trail_id);
2199 select_and_replace_trail (existing_finger, new_finger_trail,
2200 new_finger_trail_length, new_finger_trail_id);
2208 * Add a new entry in finger hashmap at finger_map_index
2209 * @param finger_identity Peer Identity of new finger
2210 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2211 * @param finger_trail_length Total number of peers in @a finger_trail.
2212 * @param trail_id Unique identifier of the trail.
2213 * @param finger_map_index Index in finger hashmap.
2214 * @return #GNUNET_OK if new entry is added
2215 * #GNUNET_NO -- FIXME: need to check what value does hahsmap put
2216 * returns on failure.
2219 add_new_entry (struct GNUNET_PeerIdentity finger_identity,
2220 struct GNUNET_PeerIdentity *finger_trail,
2221 unsigned int finger_trail_length,
2222 struct GNUNET_HashCode trail_id,
2223 unsigned int finger_map_index)
2225 struct FingerInfo *new_entry;
2226 struct FriendInfo *first_trail_hop;
2227 struct TrailList *first_trail;
2230 new_entry = GNUNET_new (struct FingerInfo);
2231 new_entry->finger_identity = finger_identity;
2232 new_entry->finger_map_index = finger_map_index;
2233 new_entry->trails_count = 1;
2235 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2237 if (finger_trail_length > 0)
2239 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2244 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2248 first_trail_hop->trails_count++;
2249 first_trail = &new_entry->trail_list[0];
2250 first_trail->first_friend_trail_count = first_trail_hop->trails_count;
2252 while (i < finger_trail_length)
2254 struct Trail *element = GNUNET_new (struct Trail);
2256 element->next = NULL;
2257 element->prev = NULL;
2258 element->peer = finger_trail[i];
2259 GNUNET_CONTAINER_DLL_insert_tail (first_trail->trail_head,
2260 first_trail->trail_tail,
2266 return GNUNET_CONTAINER_multihashmap32_put (finger_hashmap,
2267 new_entry->finger_map_index,
2269 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
2274 * Scan the trail to check if there is any other friend in the trail other than
2275 * first hop. If yes then shortcut the trail, send trail compression message to
2276 * peers which are no longer part of trail and send back the updated trail
2277 * and trail_length to calling function.
2278 * @param finger_identity Finger whose trail we will scan.
2279 * @param finger_trail [in, out] Trail to reach from source to finger,
2280 * @param finger_trail_length Total number of peers in original finger_trail.
2281 * @param finger_trail_id Unique identifier of the finger trail.
2282 * @return updated trail length in case we shortcut the trail, else original
2286 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2287 struct GNUNET_PeerIdentity *trail,
2288 unsigned int trail_length,
2289 struct GNUNET_HashCode trail_id)
2291 struct FriendInfo *target_friend;
2294 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2299 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
2301 if (trail_length > 0)
2303 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2305 GDS_NEIGHBOURS_send_trail_compression (my_identity, finger_identity,
2306 trail_id, finger_identity,
2313 for (i = trail_length - 1; i > 0; i--)
2315 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
2317 struct FriendInfo *target_friend;
2320 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2322 GDS_NEIGHBOURS_send_trail_compression (my_identity, finger_identity,
2326 // FIXME WARNING WARNING WARNING rewrite!!! consider directly creating a
2327 // struct TrailList (current) // struct Trial (after renaming).
2329 /* Copy the trail from index i to index trail_length -1 and change
2330 trail length and return */
2331 while (i < trail_length)
2333 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
2341 return trail_length;
2346 * Send verify successor message to your successor on all trails to reach
2348 * @param successor My current successor
2351 send_verify_successor_message (struct FingerInfo *successor)
2353 struct TrailList *trail_list_iterator;
2354 struct GNUNET_HashCode trail_id;
2355 struct GNUNET_PeerIdentity next_hop;
2356 struct FriendInfo *target_friend;
2357 struct GNUNET_PeerIdentity *trail;
2358 unsigned int trail_length;
2362 for (i = 0; i < MAXIMUM_TRAILS_PER_FINGER; i++)
2364 trail_list_iterator = &successor->trail_list[i];
2366 // FIXME check if this entry in the trail list is valid!
2367 // if (NULL == trail_list_iterator->SOMETHING)
2370 if (trail_list_iterator->trail_length > 0)
2372 struct Trail *element;
2374 trail_length = trail_list_iterator->trail_length;
2375 trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
2377 element = trail_list_iterator->trail_head;
2378 for (j = 0; j < trail_length; j++, element = element->next)
2379 trail[j] = element->peer;
2380 next_hop = trail_list_iterator->trail_head->peer;
2386 next_hop = successor->finger_identity;
2388 trail_id = trail_list_iterator->trail_id;
2389 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2390 // check friend for NULL
2391 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
2392 successor->finger_identity,
2393 trail_id, trail, trail_length,
2395 GNUNET_free_non_null (trail);
2401 * Check if there is already an entry in finger peermap for given finger map index.
2402 * If yes, then select the closest finger. If new and existing finger are same,
2403 * the check if you can store more trails. If yes then add trail, else keep the best
2404 * trails to reach to the finger. If the new finger is closest, add it.
2405 * Then, update current_search_finger_index.
2406 * @param new_finger_identity Peer Identity of new finger
2407 * @param new_finger_trail Trail to reach the new finger
2408 * @param new_finger_length Total number of peers in @a new_finger_trail.
2409 * @param finger_map_index Index in finger peermap.
2410 * @param new_finger_trail_id Unique identifier of @new_finger_trail.
2411 * @return #GNUNET_YES if the new entry is added
2412 * #GNUNET_NO if new entry is not added, either it was discarded or
2413 * it was same as existing finger at finger map index.
2416 finger_table_add (struct GNUNET_PeerIdentity new_finger_identity, // "finger_id"
2417 struct GNUNET_PeerIdentity *new_finger_trail, // "trail"
2418 unsigned int new_finger_trail_length,
2419 unsigned int finger_map_index,
2420 struct GNUNET_HashCode new_finger_trail_id)
2422 struct FingerInfo *existing_finger;
2423 struct FingerInfo *successor;
2424 unsigned int new_entry_added = GNUNET_NO;
2425 int new_finger_updated_trail_length; // new_finger_trail_length
2427 new_finger_updated_trail_length =
2428 scan_and_compress_trail (new_finger_identity, new_finger_trail,
2429 new_finger_trail_length, new_finger_trail_id);
2431 existing_finger = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2434 if (GNUNET_YES == is_new_finger_closest (existing_finger,
2435 new_finger_identity,
2437 new_finger_updated_trail_length,
2438 new_finger_trail_id, finger_map_index))
2440 // send_destroy_existing_finger ...
2441 // free_exisiting_finger ...
2442 GNUNET_assert (GNUNET_YES == add_new_entry (new_finger_identity,
2444 new_finger_updated_trail_length,
2445 new_finger_trail_id,
2447 new_entry_added = GNUNET_YES;
2449 // else if if_new_finger_equal () {
2452 // else // existing finger is closest
2457 // FIXME move block to "update_succesor"
2459 successor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap, 0);
2460 // WARNING FIXME check that current_search_finger_index does not go out of bounds
2461 if (0 == finger_map_index)
2463 current_search_finger_index = PREDECESSOR_FINGER_ID;
2465 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_finger_identity))
2467 send_verify_successor_message (successor);
2470 else if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity,
2471 &(successor->finger_identity)))
2473 current_search_finger_index = 0;
2476 current_search_finger_index = current_search_finger_index - 1;
2479 return new_entry_added;
2484 * Core handler for P2P put messages.
2485 * @param cls closure
2486 * @param peer sender of the request
2487 * @param message message
2488 * @return #GNUNET_OK to keep the connection open,
2489 * #GNUNET_SYSERR to close it (signal serious error)
2492 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2493 const struct GNUNET_MessageHeader *message)
2500 * Core handler for p2p get requests.
2502 * @param cls closure
2503 * @param peer sender of the request
2504 * @param message message
2505 * @return #GNUNET_OK to keep the connection open,
2506 * #GNUNET_SYSERR to close it (signal serious error)
2509 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2510 const struct GNUNET_MessageHeader *message)
2517 * Core handler for get result
2518 * @param cls closure
2519 * @param peer sender of the request
2520 * @param message message
2521 * @return #GNUNET_OK to keep the connection open,
2522 * #GNUNET_SYSERR to close it (signal serious error)
2525 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
2526 const struct GNUNET_MessageHeader *message)
2532 /* Core handle for PeerTrailSetupMessage.
2533 * @param cls closure
2534 * @param message message
2535 * @param peer peer identity this notification is about
2536 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2539 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
2540 const struct GNUNET_MessageHeader *message)
2542 struct PeerTrailSetupMessage *trail_setup;
2543 struct GNUNET_PeerIdentity *trail_peer_list;
2544 struct GNUNET_PeerIdentity next_destination; // "local_best_known_destination"
2545 struct GNUNET_PeerIdentity *current_destination;
2546 struct GNUNET_PeerIdentity *next_hop;
2547 struct GNUNET_PeerIdentity next_peer;
2548 struct FriendInfo *target_friend;
2549 struct GNUNET_PeerIdentity source;
2550 uint64_t ultimate_destination_finger_value;
2551 struct GNUNET_HashCode new_intermediate_trail_id;
2552 //struct GNUNET_HashCode *intermediate_trail_id;
2553 struct GNUNET_HashCode new_trail_id;
2554 unsigned int finger_map_index;
2555 uint32_t trail_length;
2558 msize = ntohs (message->size);
2559 /* There are PeerId's appended to the end of the message! */
2560 if (msize < sizeof (struct PeerTrailSetupMessage))
2562 GNUNET_break_op (0);
2566 trail_setup = (struct PeerTrailSetupMessage *) message;
2567 trail_length = ntohl (trail_setup->trail_length); // (msize - sizeof (msg)) / sizeof(PI)
2568 // if ((msize - sizeof (msg)) % sizeof(PI) != 0)
2569 if ((msize != sizeof (struct PeerTrailSetupMessage) +
2570 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2572 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2574 GNUNET_break_op (0);
2578 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
2579 current_destination = &trail_setup->next_destination;
2580 new_trail_id = trail_setup->new_trail_id;
2581 ultimate_destination_finger_value = GNUNET_ntohll (trail_setup->ultimate_destination_finger);
2582 source = trail_setup->source_peer;
2583 finger_map_index = ntohl (trail_setup->finger_map_index);
2584 //intermediate_trail_id = &trail_setup->intermediate_trail_id;
2586 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2588 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2589 GDS_NEIGHBOURS_send_trail_rejection (source, ultimate_destination_finger_value,
2590 my_identity, finger_map_index,
2591 trail_peer_list, trail_length,
2592 new_trail_id, target_friend,
2593 CONGESTION_TIMEOUT);
2597 next_hop = find_successor (ultimate_destination_finger_value, &next_destination,
2598 &new_intermediate_trail_id, finger_map_index);
2600 /* Are we just a part of a trail towards a finger? */
2601 if (0 != (GNUNET_CRYPTO_cmp_peer_identity(&my_identity, current_destination)))
2603 // struct GNUNET_PeerIdentity *closest_peer;
2604 // struct GNUNET_PeerIdentity *peer1 =
2605 // GDS_ROUTING_get_next_hop (intermediate_trail_id,
2606 // GDS_ROUTING_SRC_TO_DEST);
2607 /* Is next_destination better than the original best_known_dest? */
2609 // if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_destination,
2610 // current_destination))
2612 // closest_peer = select_closest_peer (peer1, next_hop,
2613 // ultimate_destination_finger_value,
2614 // finger_map_index);
2616 // if (0 == GNUNET_CRYPTO_cmp_peer_identity (peer1, closest_peer) ||
2617 // (0 == GNUNET_CRYPTO_cmp_peer_identity (peer1, next_hop)))
2619 // next_hop = peer1;
2620 // next_destination = *current_destination;
2621 // new_intermediate_trail_id = intermediate_trail_id;
2626 GNUNET_assert (NULL != next_hop);
2627 /* Am I the final destination? */
2628 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))
2630 if (0 == trail_length)
2631 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
2633 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
2635 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
2636 GDS_NEIGHBOURS_send_trail_setup_result (source,
2638 target_friend, trail_length,
2640 finger_map_index, new_trail_id);
2644 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
2646 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2647 peer_list[trail_length] = my_identity;
2648 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2649 GDS_NEIGHBOURS_send_trail_setup (source,
2650 ultimate_destination_finger_value,
2652 target_friend, trail_length + 1, peer_list,
2653 finger_map_index, new_trail_id,
2654 &new_intermediate_trail_id);
2661 * Core handle for p2p trail construction result messages.
2663 * @param message message
2664 * @param peer peer identity this notification is about
2665 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2668 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2669 const struct GNUNET_MessageHeader *message)
2671 struct PeerTrailSetupResultMessage *trail_result;
2672 struct GNUNET_PeerIdentity *trail_peer_list;
2673 struct GNUNET_PeerIdentity destination_peer;
2674 struct GNUNET_PeerIdentity finger_identity;
2675 uint32_t trail_length;
2676 uint32_t finger_map_index;
2677 struct GNUNET_HashCode trail_id;
2680 msize = ntohs (message->size);
2681 if (msize < sizeof (struct PeerTrailSetupResultMessage))
2683 GNUNET_break_op (0);
2687 trail_result = (struct PeerTrailSetupResultMessage *) message;
2689 // calculate trail_length with message size, check for % 0
2690 trail_length = ntohl (trail_result->trail_length);
2692 sizeof (struct PeerTrailSetupResultMessage) +
2693 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2695 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2697 GNUNET_break_op (0);
2701 finger_map_index = htonl (trail_result->finger_map_index);
2702 destination_peer = trail_result->destination_peer;
2703 finger_identity = trail_result->finger_identity;
2704 trail_id = trail_result->trail_id;
2705 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
2707 // FIXME: check that trail_peer_list[my_index + 1] == peer or
2708 // my_index == trail_length - 1 AND finger_identity == peer
2710 /* Am I the one who initiated the query? */
2711 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer,
2714 finger_table_add (finger_identity, trail_peer_list,
2716 finger_map_index, trail_id);
2720 struct GNUNET_PeerIdentity next_hop;
2721 struct FriendInfo *target_friend;
2724 my_index = search_my_index(trail_peer_list, trail_length);
2728 return GNUNET_SYSERR;
2733 next_hop = trail_result->destination_peer;
2735 next_hop = trail_peer_list[my_index - 1];
2737 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2738 &(trail_result->finger_identity))))
2740 GDS_ROUTING_add (trail_id, next_hop, *peer);
2743 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2744 GDS_NEIGHBOURS_send_trail_setup_result (destination_peer, finger_identity,
2745 target_friend, trail_length, trail_peer_list,
2746 finger_map_index, trail_id);
2753 * @param trail Trail to be inverted
2754 * @param trail_length Total number of peers in the trail.
2755 * @return Updated trail
2757 static struct GNUNET_PeerIdentity *
2758 invert_trail (struct GNUNET_PeerIdentity *trail,
2759 unsigned int trail_length)
2763 struct GNUNET_PeerIdentity *inverted_trail;
2765 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
2768 j = trail_length - 1;
2769 while (i < trail_length)
2771 inverted_trail[i] = trail[j];
2775 return inverted_trail;
2780 * Check if the new finger can be our predecessor. If yes then update predecessor
2783 * @param new_finger_trail
2784 * @param new_finger_trail_length
2788 is_new_entry_correct_predecessor (struct FingerInfo *my_predecessor,
2789 struct GNUNET_PeerIdentity new_finger,
2790 struct GNUNET_PeerIdentity *new_finger_trail,
2791 unsigned int new_finger_trail_length)
2793 struct GNUNET_PeerIdentity *updated_trail;
2794 struct GNUNET_HashCode new_trail_id;
2796 updated_trail = invert_trail (new_finger_trail, new_finger_trail_length);
2797 if (GNUNET_YES == is_new_finger_closest (my_predecessor, new_finger,
2799 new_finger_trail_length,
2800 new_trail_id, PREDECESSOR_FINGER_ID))
2802 add_new_entry (new_finger, updated_trail, new_finger_trail_length,
2803 new_trail_id, PREDECESSOR_FINGER_ID);
2804 /* FIXME: check where you send add trail message */
2811 * In case the source peer of verify successor message is not my successor,
2812 * then construct a trail from source peer to my current predecessor.
2813 * @param my_predecessor my current predecessor.
2814 * @param current_trail Trail from source to me.
2815 * @param current_trail_length Total number of peers in @a current_trail
2816 * @param new_trail_length [out] Total number of peers in updated trail.
2817 * @return Updated trail from source peer to my_predecessor.
2819 static struct GNUNET_PeerIdentity *
2820 trail_source_to_my_predecessor (struct FingerInfo *my_predecessor,
2821 struct GNUNET_PeerIdentity *current_trail,
2822 unsigned int current_trail_length,
2823 unsigned int *new_trail_length)
2825 struct GNUNET_PeerIdentity *new_trail;
2826 struct TrailList *trail_list_iterator;
2827 struct Trail *trail_iterator;
2830 unsigned int shortest_trail_length = 0;
2831 unsigned int trail_index = 0;
2833 for (i = 0; i < my_predecessor->trails_count; i++)
2835 trail_list_iterator = &my_predecessor->trail_list[i];
2836 if (trail_list_iterator->trail_length > shortest_trail_length)
2838 shortest_trail_length = trail_list_iterator->trail_length;
2842 *new_trail_length = current_trail_length + shortest_trail_length + 1;
2843 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2845 memcpy (new_trail, current_trail,
2846 current_trail_length * sizeof (struct GNUNET_PeerIdentity));
2847 new_trail[current_trail_length + 1] = my_identity;
2850 j = current_trail_length + 1;
2851 trail_list_iterator = &my_predecessor->trail_list[trail_index];
2852 trail_iterator = trail_list_iterator->trail_head;
2853 while ( i < shortest_trail_length)
2855 new_trail[j] = trail_iterator->peer;
2858 trail_iterator = trail_iterator->next;
2861 *new_trail_length = j;
2867 * Core handle for p2p verify successor messages.
2868 * @param cls closure
2869 * @param message message
2870 * @param peer peer identity this notification is about
2871 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2874 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2875 const struct GNUNET_MessageHeader *message)
2877 struct PeerVerifySuccessorMessage *vsm;
2878 struct GNUNET_PeerIdentity successor;
2879 struct GNUNET_PeerIdentity source_peer;
2880 struct GNUNET_PeerIdentity *next_hop;
2881 struct FriendInfo *target_friend;
2882 struct GNUNET_HashCode trail_id;
2883 struct FingerInfo *my_predecessor;
2884 struct GNUNET_PeerIdentity *trail;
2885 struct GNUNET_PeerIdentity *new_trail;
2886 unsigned int trail_length;
2887 unsigned int new_trail_length;
2890 msize = ntohs (message->size);
2891 if (msize != sizeof (struct PeerVerifySuccessorMessage))
2893 GNUNET_break_op (0);
2897 vsm = (struct PeerVerifySuccessorMessage *) message;
2898 trail_length = ntohl (vsm->trail_length);
2899 if ((msize != sizeof (struct PeerVerifySuccessorMessage) +
2900 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2901 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2903 GNUNET_break_op (0);
2906 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
2907 source_peer = vsm->source_peer;
2908 successor = vsm->successor;
2909 trail_id = vsm->trail_id;
2911 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
2913 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
2914 if (NULL == next_hop)
2917 return GNUNET_SYSERR;
2919 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2920 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
2921 trail_id, trail, trail_length,
2926 my_predecessor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2927 PREDECESSOR_FINGER_ID);
2928 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2929 if (GNUNET_NO == is_new_entry_correct_predecessor (my_predecessor, source_peer,
2930 trail, trail_length))
2932 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
2933 &my_predecessor->finger_identity))
2935 new_trail = trail_source_to_my_predecessor (my_predecessor, trail,
2936 trail_length, &new_trail_length);
2941 my_predecessor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2942 PREDECESSOR_FINGER_ID);
2943 GDS_NEIGHBOURS_send_add_trail (my_predecessor->finger_identity,
2944 source_peer, trail_id,
2945 trail, trail_length,
2947 new_trail_length = trail_length;
2948 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2950 memcpy (new_trail, trail, sizeof (struct GNUNET_PeerIdentity) *
2954 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
2955 my_predecessor->finger_identity,
2956 trail_id, new_trail,
2958 GDS_ROUTING_DEST_TO_SRC,
2965 * FIXME: I will keep the logic to remove the old trail to reach from me to
2966 * my old successor here and move adding a new trail from me to new successor to notify
2967 * new successor. And in case if the new successor also take it as predecessor
2968 * then call add_trail.
2969 * Core handle for p2p verify successor result messages.
2970 * @param cls closure
2971 * @param message message
2972 * @param peer peer identity this notification is about
2973 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2976 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2977 const struct GNUNET_MessageHeader *message)
2979 struct PeerVerifySuccessorResultMessage *vsrm;
2980 enum GDS_ROUTING_trail_direction trail_direction;
2981 struct GNUNET_HashCode trail_id;
2982 unsigned int new_trail_length;
2983 struct GNUNET_PeerIdentity *new_trail;
2984 struct GNUNET_PeerIdentity destination_peer;
2985 struct GNUNET_PeerIdentity my_new_successor;
2986 struct GNUNET_PeerIdentity old_successor;
2987 struct GNUNET_PeerIdentity *next_hop;
2988 struct FriendInfo *target_friend;
2991 msize = ntohs (message->size);
2992 if (msize != sizeof (struct PeerVerifySuccessorResultMessage))
2994 GNUNET_break_op (0);
2997 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
2998 new_trail_length = ntohl (vsrm->trail_length);
2999 trail_direction = ntohl (vsrm->trail_direction);
3000 trail_id = vsrm->trail_id;
3003 sizeof (struct PeerVerifySuccessorResultMessage) +
3005 sizeof (struct GNUNET_PeerIdentity)) ||
3007 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3009 GNUNET_break_op (0);
3013 new_trail = (struct GNUNET_PeerIdentity *) &vsrm[1];
3014 destination_peer = vsrm->destination_peer;
3015 my_new_successor = vsrm->my_predecessor;
3016 old_successor = vsrm->source_successor;
3018 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer, &my_identity)))
3020 struct GNUNET_HashCode new_finger_trail_id;
3021 /* FIXME: generate a new trail id. */
3022 if (GNUNET_YES == finger_table_add (my_new_successor,
3025 PREDECESSOR_FINGER_ID, new_finger_trail_id))
3027 if (new_trail_length > 0)
3028 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3031 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3033 GDS_NEIGHBOURS_send_trail_teardown (my_identity, old_successor, trail_id,
3034 GDS_ROUTING_SRC_TO_DEST, target_friend);
3035 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, my_new_successor,
3038 new_finger_trail_id, target_friend);
3043 GNUNET_assert (NULL != (next_hop =
3044 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
3045 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3046 GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
3047 vsrm->source_successor,
3048 my_new_successor, trail_id,
3051 trail_direction, target_friend);
3057 * Core handle for p2p notify new successor messages.
3058 * @param cls closure
3059 * @param message message
3060 * @param peer peer identity this notification is about
3061 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3064 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3065 const struct GNUNET_MessageHeader *message)
3067 struct PeerNotifyNewSuccessorMessage *nsm;
3068 struct GNUNET_PeerIdentity *trail;
3069 struct GNUNET_PeerIdentity source;
3070 struct GNUNET_PeerIdentity destination;
3071 struct FriendInfo *target_friend;
3072 struct GNUNET_HashCode trail_id;
3073 unsigned int my_index;
3074 struct GNUNET_PeerIdentity next_hop;
3076 uint32_t trail_length;
3078 msize = ntohs (message->size);
3079 if (msize != sizeof (struct PeerNotifyNewSuccessorMessage))
3081 GNUNET_break_op (0);
3085 nsm = (struct PeerNotifyNewSuccessorMessage *) message;
3086 trail_length = ntohl (nsm->trail_length);
3088 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3089 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3091 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3093 GNUNET_break_op (0);
3097 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
3098 source = nsm->source_peer;
3099 destination = nsm->destination_peer;
3100 trail_id = nsm->trail_id;
3102 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination))
3104 struct GNUNET_HashCode new_trail_id;
3105 struct FingerInfo *my_predecessor;
3108 GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
3109 PREDECESSOR_FINGER_ID);
3110 /* FIXME: get new_trail_id*/
3112 if (GNUNET_YES == is_new_entry_correct_predecessor (my_predecessor,
3117 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3119 GDS_NEIGHBOURS_send_add_trail (my_identity, source, new_trail_id,
3120 trail, trail_length, target_friend);
3125 my_index = search_my_index (trail, trail_length);
3126 if (GNUNET_SYSERR == my_index)
3128 GNUNET_break_op (0);
3129 return GNUNET_SYSERR;
3131 if (trail_length == my_index)
3132 next_hop = destination;
3134 next_hop = trail[my_index + 1];
3135 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
3136 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3137 GDS_NEIGHBOURS_send_notify_new_successor (source, destination, trail,
3139 trail_id, target_friend);
3145 * FIXME: Here you should keep the trail id with you.
3146 * Core handler for P2P trail rejection message
3147 * @param cls closure
3148 * @param message message
3149 * @param peer peer identity this notification is about
3150 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3153 handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3154 const struct GNUNET_MessageHeader *message)
3156 struct PeerTrailRejectionMessage *trail_rejection;
3157 unsigned int trail_length;
3158 struct GNUNET_PeerIdentity *trail_peer_list;
3159 struct FriendInfo *target_friend;
3160 struct GNUNET_TIME_Relative congestion_timeout;
3161 struct GNUNET_HashCode trail_id;
3162 struct GNUNET_PeerIdentity next_destination;
3163 struct GNUNET_HashCode new_intermediate_trail_id;
3164 struct GNUNET_PeerIdentity next_peer;
3165 struct GNUNET_PeerIdentity source;
3166 struct GNUNET_PeerIdentity *next_hop;
3167 uint64_t ultimate_destination_finger_value;
3168 unsigned int finger_map_index;
3171 msize = ntohs (message->size);
3172 if (msize != sizeof (struct PeerTrailRejectionMessage))
3174 GNUNET_break_op (0);
3178 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3179 trail_length = ntohl (trail_rejection->trail_length);
3181 if ((msize != sizeof (struct PeerTrailRejectionMessage) +
3182 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3184 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3186 GNUNET_break_op (0);
3190 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3191 finger_map_index = ntohl (trail_rejection->finger_map_index);
3192 congestion_timeout = trail_rejection->congestion_time;
3193 source = trail_rejection->source_peer;
3194 trail_id = trail_rejection->trail_id;
3195 ultimate_destination_finger_value =
3196 trail_rejection->ultimate_destination_finger_identity_value;
3198 /* First set the congestion time of the friend that sent you this message. */
3199 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3200 target_friend->congestion_timestamp = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
3201 congestion_timeout);
3203 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
3208 /* If I am congested then pass this message to peer before me in trail. */
3209 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
3211 struct GNUNET_PeerIdentity *new_trail;
3212 unsigned int new_trail_length;
3214 if (trail_length == 1)
3217 new_trail_length = 0;
3222 next_hop = &trail_peer_list[trail_length - 2];
3223 /* Remove myself from the trail. */
3224 new_trail_length = trail_length -1;
3225 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
3226 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
3229 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3230 GDS_NEIGHBOURS_send_trail_rejection (source,
3231 ultimate_destination_finger_value,
3232 my_identity, finger_map_index,
3233 new_trail,new_trail_length,trail_id,
3234 target_friend, CONGESTION_TIMEOUT);
3238 /* Look for next_hop to pass the trail setup message */
3239 next_hop = find_successor (ultimate_destination_finger_value,
3241 &new_intermediate_trail_id,
3244 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
3246 if (0 == trail_length)
3249 next_peer = trail_peer_list[trail_length-1];
3251 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3252 GDS_NEIGHBOURS_send_trail_setup_result (source,
3254 target_friend, trail_length,
3256 finger_map_index, trail_id);
3260 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3262 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3263 peer_list[trail_length] = my_identity;
3265 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3266 GDS_NEIGHBOURS_send_trail_setup (source,
3267 ultimate_destination_finger_value,
3269 target_friend, trail_length + 1, peer_list,
3270 finger_map_index, trail_id,
3271 &new_intermediate_trail_id);
3278 * Core handle for p2p trail tear down messages.
3279 * @param cls closure
3280 * @param message message
3281 * @param peer peer identity this notification is about
3282 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3285 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
3286 const struct GNUNET_MessageHeader *message)
3288 struct PeerTrailCompressionMessage *trail_compression;
3289 struct GNUNET_PeerIdentity *next_hop;
3290 struct GNUNET_HashCode trail_id;
3291 struct FriendInfo *target_friend;
3294 msize = ntohs (message->size);
3295 if (msize != sizeof (struct PeerTrailCompressionMessage))
3297 GNUNET_break_op (0);
3301 trail_compression = (struct PeerTrailCompressionMessage *) message;
3302 trail_id = trail_compression->trail_id;
3304 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->new_first_friend),
3307 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->destination_peer),
3310 GDS_ROUTING_update_trail_prev_hop (trail_id,
3311 trail_compression->source_peer);
3316 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
3317 if (NULL == next_hop)
3319 GNUNET_break (0); /*FIXME: How to handle this case. */
3322 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
3323 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3324 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
3325 trail_compression->destination_peer,
3327 trail_compression->new_first_friend,
3334 * Core handler for trail teardown message.
3335 * @param cls closure
3336 * @param message message
3337 * @param peer peer identity this notification is about
3338 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3341 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
3342 const struct GNUNET_MessageHeader *message)
3344 struct PeerTrailTearDownMessage *trail_teardown;
3345 struct GNUNET_HashCode trail_id;
3346 enum GDS_ROUTING_trail_direction trail_direction;
3349 msize = ntohs (message->size);
3350 if (msize != sizeof (struct PeerTrailTearDownMessage))
3352 GNUNET_break_op (0);
3356 trail_teardown = (struct PeerTrailTearDownMessage *) message;
3357 trail_direction = ntohl (trail_teardown->trail_direction);
3358 trail_id = trail_teardown->TRAIL_ID;
3360 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3361 &trail_teardown->destination_peer))
3363 struct GNUNET_PeerIdentity *next_hop;
3364 struct FriendInfo *target_friend;
3366 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
3367 if (NULL == next_hop)
3370 return GNUNET_SYSERR;
3373 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3375 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
3376 GDS_NEIGHBOURS_send_trail_teardown (trail_teardown->source_peer,
3377 trail_teardown->destination_peer,
3378 trail_id, trail_direction,
3386 * Fixme: this function is called only in case in notify new successor, the new
3387 * successor wants to add the source of the peer as its predecessor. Identify
3388 * if there is any other use case where it is required and if yes then adapt the
3390 * Core handle for p2p add trail message.
3391 * @param cls closure
3392 * @param message message
3393 * @param peer peer identity this notification is about
3394 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3397 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
3398 const struct GNUNET_MessageHeader *message)
3400 struct PeerAddTrailMessage *add_trail;
3401 struct GNUNET_PeerIdentity *trail;
3402 struct GNUNET_HashCode trail_id;
3403 struct GNUNET_PeerIdentity destination_peer;
3404 struct GNUNET_PeerIdentity source_peer;
3405 struct GNUNET_PeerIdentity next_hop;
3406 unsigned int trail_length;
3407 unsigned int my_index;
3410 msize = ntohs (message->size);
3411 if (msize != sizeof (struct PeerAddTrailMessage))
3413 GNUNET_break_op (0);
3417 add_trail = (struct PeerAddTrailMessage *) message;
3418 trail_length = ntohl (add_trail->trail_length);
3420 if ((msize < sizeof (struct PeerAddTrailMessage) +
3421 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3423 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3425 GNUNET_break_op (0);
3429 trail = (struct GNUNET_PeerIdentity *)&add_trail[1];
3430 destination_peer = add_trail->destination_peer;
3431 source_peer = add_trail->source_peer;
3432 trail_id = add_trail->trail_id;
3434 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3437 struct FriendInfo *target_friend;
3439 my_index = search_my_index (trail, trail_length);
3440 if (GNUNET_SYSERR == my_index)
3442 GNUNET_break_op (0);
3443 return GNUNET_SYSERR;
3447 next_hop = source_peer;
3449 next_hop = trail[trail_length - 1];
3451 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
3452 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3453 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
3454 trail, trail_length, target_friend);
3461 *FIXME; call send_trail_teardown_message on all the trails of the finger that
3462 * you remove. Also you don't need to decerement friend trail count as that
3463 * friend is removed. But you can not send trail teardown message as the friend
3464 * is disconnected. then you don't have any next_hop. and in case there are
3465 * multiple trails. and friend is the first trail then you remove only the trail.
3466 * Iterate over finger_hashmap, and remove entries if finger is the disconnected
3467 * peer or if disconnected peer is the first friend in the trail to reach the
3469 * @param cls closure
3470 * @param key current public key
3471 * @param value value in the hash map
3472 * @return #GNUNET_YES if we should continue to
3474 * #GNUNET_NO if not.
3477 remove_matching_finger (void *cls,
3481 struct FingerInfo *remove_finger = value;
3482 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
3483 struct TrailList *trail_list;
3486 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
3489 GNUNET_assert (GNUNET_YES ==
3490 GNUNET_CONTAINER_multihashmap32_remove (finger_hashmap,
3493 free_finger (remove_finger);
3497 for (i = 0; i< remove_finger->trails_count; i++)
3499 trail_list = &remove_finger->trail_list[i];
3500 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_list->trail_head->peer,
3503 GNUNET_assert (GNUNET_YES ==
3504 GNUNET_CONTAINER_multihashmap32_remove (finger_hashmap,
3507 free_finger (remove_finger);
3516 * Method called whenever a peer disconnects.
3518 * @param cls closure
3519 * @param peer peer identity this notification is about
3522 handle_core_disconnect (void *cls,
3523 const struct GNUNET_PeerIdentity *peer)
3525 struct FriendInfo *remove_friend;
3527 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
3531 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3533 if (NULL == remove_friend)
3539 GNUNET_assert (GNUNET_SYSERR !=
3540 GNUNET_CONTAINER_multihashmap32_iterate (finger_hashmap,
3541 &remove_matching_finger,
3543 GDS_ROUTING_remove_trail_by_peer (peer);
3544 GNUNET_assert (GNUNET_YES ==
3545 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
3549 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
3552 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3554 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3555 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3563 * Method called whenever a peer connects.
3565 * @param cls closure
3566 * @param peer_identity peer identity this notification is about
3569 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
3571 struct FriendInfo *friend;
3573 /* Check for connect to self message */
3574 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
3577 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
3579 /* If peer already exists in our friend_peermap, then exit. */
3580 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
3586 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
3589 friend = GNUNET_new (struct FriendInfo);
3590 friend->id = *peer_identity;
3592 GNUNET_assert (GNUNET_OK ==
3593 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
3594 peer_identity, friend,
3595 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
3597 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
3598 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
3599 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
3604 * To be called on core init/fail.
3606 * @param cls service closure
3607 * @param identity the public identity of this peer
3610 core_init (void *cls,
3611 const struct GNUNET_PeerIdentity *identity)
3613 my_identity = *identity;
3618 * Initialize neighbours subsystem.
3619 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3622 GDS_NEIGHBOURS_init (void)
3624 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
3625 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
3626 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
3627 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
3628 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
3629 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
3630 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
3631 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
3632 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
3633 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
3634 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION, 0},
3635 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
3636 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL, 0},
3641 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
3642 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
3643 GNUNET_NO, core_handlers);
3644 if (NULL == core_api)
3645 return GNUNET_SYSERR;
3647 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
3648 finger_hashmap = GNUNET_CONTAINER_multihashmap32_create (MAX_FINGERS * 4/3);
3654 * Shutdown neighbours subsystem.
3657 GDS_NEIGHBOURS_done (void)
3659 if (NULL == core_api)
3662 GNUNET_CORE_disconnect (core_api);
3665 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
3666 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
3667 friend_peermap = NULL;
3669 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap32_size (finger_hashmap));
3670 GNUNET_CONTAINER_multihashmap32_destroy (finger_hashmap);
3671 finger_hashmap = NULL;
3673 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3676 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3677 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3685 * @return my identity
3687 struct GNUNET_PeerIdentity
3688 GDS_NEIGHBOURS_get_my_id (void)