2 This file is part of GNUnet.
3 Copyright (C) 2009-2014, 2016 GNUnet e.V.
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., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, 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
25 * @author Christian Grothoff
29 #include "gnunet_util_lib.h"
30 #include "gnunet_block_lib.h"
31 #include "gnunet_hello_lib.h"
32 #include "gnunet_constants.h"
33 #include "gnunet_protocols.h"
34 #include "gnunet_ats_service.h"
35 #include "gnunet_core_service.h"
36 #include "gnunet_datacache_lib.h"
37 #include "gnunet_transport_service.h"
38 #include "gnunet_dht_service.h"
39 #include "gnunet_statistics_service.h"
40 #include "gnunet-service-dht.h"
41 #include "gnunet-service-dht_datacache.h"
42 #include "gnunet-service-dht_neighbours.h"
43 #include "gnunet-service-xdht_routing.h"
48 * 1. In X-Vine paper, there is no policy defined for replicating the data to
49 * recover in case of peer failure. We can do it in Chord way. In R5N, the key
50 * is hashed and then data is stored according to the key value generated after
55 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
58 * Maximum possible fingers (including predecessor) of a peer
60 #define MAX_FINGERS 65
63 * Maximum allowed number of pending messages per friend peer.
65 #define MAXIMUM_PENDING_PER_FRIEND 64
68 * How long to wait before sending another find finger trail request
70 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
73 * How long to wait before sending another verify successor message.
75 #define DHT_SEND_VERIFY_SUCCESSOR_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
78 * How long to wait before sending another verify successor message.
80 #define DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
83 * How long to wait before retrying notify successor.
85 #define DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
88 * How long at most to wait for transmission of a request to a friend ?
90 #define PENDING_MESSAGE_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
93 * Duration for which I may remain congested.
94 * Note: Its a static value. In future, a peer may do some analysis and calculate
95 * congestion_timeout based on 'some' parameters.
97 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
100 * In case we don't hear back from the current successor, then we can start
103 #define WAIT_NOTIFY_CONFIRMATION GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 200)
106 * Maximum number of trails allowed to go through a friend.
108 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
111 * Maximum number of trails stored per finger.
113 #define MAXIMUM_TRAILS_PER_FINGER 4
116 * Finger map index for predecessor entry in finger table.
118 #define PREDECESSOR_FINGER_ID 64
121 * FIXME: Its use only at 3 places check if you can remove it.
122 * To check if a finger is predecessor or not.
124 enum GDS_NEIGHBOURS_finger_type
126 GDS_FINGER_TYPE_PREDECESSOR = 1,
127 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
130 GNUNET_NETWORK_STRUCT_BEGIN
135 struct PeerPutMessage
138 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
140 struct GNUNET_MessageHeader header;
145 uint32_t options GNUNET_PACKED;
150 uint32_t block_type GNUNET_PACKED;
155 uint32_t hop_count GNUNET_PACKED;
158 * Replication level for this message
159 * In the current implementation, this value is not used.
161 uint32_t desired_replication_level GNUNET_PACKED;
164 * Length of the PUT path that follows (if tracked).
166 uint32_t put_path_length GNUNET_PACKED;
169 * Best known destination (could be my friend or finger) which should
170 * get this message next.
172 struct GNUNET_PeerIdentity best_known_destination;
175 * In case best_known_destination is a finger, then trail to reach
176 * to that finger. Else its default value is 0.
178 struct GNUNET_HashCode intermediate_trail_id;
181 * When does the content expire?
183 struct GNUNET_TIME_AbsoluteNBO expiration_time;
186 * The key to store the value under.
188 struct GNUNET_HashCode key GNUNET_PACKED;
190 /* put path (if tracked) */
199 struct PeerGetMessage
202 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
204 struct GNUNET_MessageHeader header;
209 uint32_t options GNUNET_PACKED;
212 * Desired content type.
214 uint32_t block_type GNUNET_PACKED;
219 uint32_t hop_count GNUNET_PACKED;
222 * Desired replication level for this request.
223 * In the current implementation, this value is not used.
225 uint32_t desired_replication_level GNUNET_PACKED;
228 * Total number of peers in get path.
230 unsigned int get_path_length;
233 * Best known destination (could be my friend or finger) which should
234 * get this message next.
236 struct GNUNET_PeerIdentity best_known_destination;
239 * In case best_known_destination is a finger, then trail to reach
240 * to that finger. Else its default value is 0.
242 struct GNUNET_HashCode intermediate_trail_id;
245 * The key we are looking for.
247 struct GNUNET_HashCode key;
250 /* struct GNUNET_PeerIdentity[]*/
256 struct PeerGetResultMessage
259 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
261 struct GNUNET_MessageHeader header;
264 * The type for the data.
266 uint32_t type GNUNET_PACKED;
269 * Number of peers recorded in the outgoing path from source to the
270 * stored location of this message.
272 uint32_t put_path_length GNUNET_PACKED;
275 * Length of the GET path that follows (if tracked).
277 uint32_t get_path_length GNUNET_PACKED;
280 * Peer which queried for get and should get the result.
282 struct GNUNET_PeerIdentity querying_peer;
285 * When does the content expire?
287 struct GNUNET_TIME_AbsoluteNBO expiration_time;
290 * The key of the corresponding GET request.
292 struct GNUNET_HashCode key;
294 /* put path (if tracked) */
296 /* get path (if tracked) */
303 * P2P Trail setup message
305 struct PeerTrailSetupMessage
308 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
310 struct GNUNET_MessageHeader header;
313 * Is source_peer trying to setup the trail to a predecessor or any finger.
315 uint32_t is_predecessor;
318 * Peer closest to this value will be our finger.
320 uint64_t final_destination_finger_value;
323 * Source peer which wants to setup the trail to one of its finger.
325 struct GNUNET_PeerIdentity source_peer;
328 * Best known destination (could be my friend or finger) which should
329 * get this message next.
331 * FIXME: this could be removed if we include trail_source / trail_dest
332 * in the routing table. This way we save 32 bytes of bandwidth by using
333 * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID))
335 struct GNUNET_PeerIdentity best_known_destination;
338 * In case best_known_destination is a finger, then trail id of trail to
339 * reach to this finger.
341 struct GNUNET_HashCode intermediate_trail_id;
344 * Trail id for trail which we are trying to setup.
346 struct GNUNET_HashCode trail_id;
348 /* List of peers which are part of trail setup so far.
349 * Trail does NOT include source_peer and peer which will be closest to
350 * ultimate_destination_finger_value.
351 * struct GNUNET_PeerIdentity trail[]
356 * P2P Trail Setup Result message
358 struct PeerTrailSetupResultMessage
362 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
364 struct GNUNET_MessageHeader header;
367 * Finger to which we have found the path.
369 struct GNUNET_PeerIdentity finger_identity;
372 * Peer which started trail_setup to find trail to finger_identity
374 struct GNUNET_PeerIdentity querying_peer;
377 * Is the trail setup to querying_peer's predecessor or finger?
379 uint32_t is_predecessor;
382 * Value to which finger_identity is the closest peer.
384 uint64_t ultimate_destination_finger_value;
387 * Identifier of the trail from querying peer to finger_identity, NOT
388 * including both endpoints.
390 struct GNUNET_HashCode trail_id;
392 /* List of peers which are part of the trail from querying peer to
393 * finger_identity, NOT including both endpoints.
394 * struct GNUNET_PeerIdentity trail[]
399 * P2P Verify Successor Message.
401 struct PeerVerifySuccessorMessage
404 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
406 struct GNUNET_MessageHeader header;
409 * Peer which wants to verify its successor.
411 struct GNUNET_PeerIdentity source_peer;
414 * Source Peer's current successor.
416 struct GNUNET_PeerIdentity successor;
419 * Identifier of trail to reach from source_peer to successor.
421 struct GNUNET_HashCode trail_id;
423 /* List of the peers which are part of trail to reach from source_peer
424 * to successor, NOT including them
425 * struct GNUNET_PeerIdentity trail[]
430 * P2P Verify Successor Result Message
432 struct PeerVerifySuccessorResultMessage
435 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
437 struct GNUNET_MessageHeader header;
440 * Peer which sent the request to verify its successor.
442 struct GNUNET_PeerIdentity querying_peer;
445 * Successor to which PeerVerifySuccessorMessage was sent.
447 struct GNUNET_PeerIdentity current_successor;
450 * Current Predecessor of source_successor. It can be same as querying peer
451 * or different. In case it is different then it can be querying_peer's
452 * probable successor.
454 struct GNUNET_PeerIdentity probable_successor;
457 * Trail identifier of trail from querying_peer to current_successor.
459 struct GNUNET_HashCode trail_id;
462 * Direction in which we are looking at the trail.
464 uint32_t trail_direction;
466 /* In case probable_successor != querying_peer, then trail to reach from
467 * querying_peer to probable_successor, NOT including end points.
468 * struct GNUNET_PeerIdentity trail[]
473 * P2P Notify New Successor Message.
475 struct PeerNotifyNewSuccessorMessage
478 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
480 struct GNUNET_MessageHeader header;
483 * Peer which wants to notify its new successor.
485 struct GNUNET_PeerIdentity source_peer;
488 * New successor of source_peer.
490 struct GNUNET_PeerIdentity new_successor;
493 * Unique identifier of the trail from source_peer to new_successor,
494 * NOT including the endpoints.
496 struct GNUNET_HashCode trail_id;
498 /* List of peers in trail from source_peer to new_successor,
499 * NOT including the endpoints.
500 * struct GNUNET_PeerIdentity trail[]
505 * P2P Notify Successor Confirmation message.
507 struct PeerNotifyConfirmationMessage
510 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
512 struct GNUNET_MessageHeader header;
515 * Unique identifier of the trail.
517 struct GNUNET_HashCode trail_id;
520 * Direction of trail.
522 uint32_t trail_direction;
527 * P2P Trail Tear Down message.
529 struct PeerTrailTearDownMessage
532 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
534 struct GNUNET_MessageHeader header;
537 * Unique identifier of the trail.
539 struct GNUNET_HashCode trail_id;
542 * Direction of trail.
544 uint32_t trail_direction;
549 * P2P Trail Rejection Message.
551 struct PeerTrailRejectionMessage
554 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
556 struct GNUNET_MessageHeader header;
559 * Peer which wants to set up the trail.
561 struct GNUNET_PeerIdentity source_peer;
564 * Peer which sent trail rejection message as it it congested.
566 struct GNUNET_PeerIdentity congested_peer;
569 * Peer identity closest to this value will be finger of
572 uint64_t ultimate_destination_finger_value;
575 * Is source_peer trying to setup the trail to its predecessor or finger.
577 uint32_t is_predecessor;
580 * Identifier for the trail that source peer is trying to setup.
582 struct GNUNET_HashCode trail_id;
585 * Relative time for which congested_peer will remain congested.
587 struct GNUNET_TIME_Relative congestion_time;
589 /* Trail_list from source_peer to peer which sent the message for trail setup
590 * to congested peer. This trail does NOT include source_peer.
591 struct GNUNET_PeerIdnetity trail[]*/
595 * P2P Add Trail Message.
597 struct PeerAddTrailMessage
600 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
602 struct GNUNET_MessageHeader header;
605 * Source of the routing trail.
607 struct GNUNET_PeerIdentity source_peer;
610 * Destination of the routing trail.
612 struct GNUNET_PeerIdentity destination_peer;
615 * Unique identifier of the trail from source_peer to destination_peer,
616 * NOT including the endpoints.
618 struct GNUNET_HashCode trail_id;
620 /* Trail from source peer to destination peer, NOT including them.
621 * struct GNUNET_PeerIdentity trail[]
626 GNUNET_NETWORK_STRUCT_END
630 * Entry in friend_peermap.
637 const struct GNUNET_PeerIdentity *id;
640 * Number of trails for which this friend is the first hop or if the friend
643 unsigned int trails_count;
646 * In case not 0, then amount of time for which this friend is congested.
648 struct GNUNET_TIME_Absolute congestion_timestamp;
651 * Handle for sending messages to this friend.
653 struct GNUNET_MQ_Handle *mq;
658 * An individual element of the trail to reach to a finger.
663 * Pointer to next item in the list
665 struct Trail_Element *next;
668 * Pointer to prev item in the list
670 struct Trail_Element *prev;
673 * An element in this trail.
675 struct GNUNET_PeerIdentity peer;
679 * Information about an individual trail.
686 struct Trail_Element *trail_head;
691 struct Trail_Element *trail_tail;
694 * Unique identifier of this trail.
696 struct GNUNET_HashCode trail_id;
699 * Length of trail pointed
701 unsigned int trail_length;
704 * Is there a valid trail entry.
706 unsigned int is_present;
710 * An entry in finger_table
717 struct GNUNET_PeerIdentity finger_identity;
720 * In case not 0, this amount is time to wait for notify successor message.
721 * Used ONLY for successor. NOT for any other finger.
723 struct GNUNET_TIME_Absolute wait_notify_confirmation;
726 * Is any finger stored at this finger index.
728 unsigned int is_present;
731 * Index in finger peer map
733 uint32_t finger_table_index;
736 * Number of trails setup so far for this finger.
737 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
739 uint32_t trails_count;
742 * Array of trails to reach to this finger.
744 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
749 * Stores information about the peer which is closest to destination_finger_value.
750 * 'closest' can be either successor or predecessor depending on is_predecessor
756 * Destination finger value.
758 uint64_t destination_finger_value;
761 * Is finger_value a predecessor or any other finger.
763 unsigned int is_predecessor;
766 * Trail id to reach to peer.
767 * In case peer is my identity or friend, it is set to 0.
769 struct GNUNET_HashCode trail_id;
772 * Next destination. In case of friend and my_identity , it is same as next_hop
773 * In case of finger it is finger identity.
775 struct GNUNET_PeerIdentity best_known_destination;
778 * In case best_known_destination is a finger, then first friend in the trail
779 * to reach to it. In other case, same as best_known_destination.
781 struct GNUNET_PeerIdentity next_hop;
784 * In case finger is the next hop, it contains a valid finger table index
785 * at which the finger is stored. Else, It contains 65, which is out of range
786 * of finger table index.
788 unsigned int finger_table_index;
792 * Context for send_verify_successor_task.
794 struct VerifySuccessorContext
797 * Number of times this has been scheduled.
799 unsigned int num_retries_scheduled;
803 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
804 * get our first friend.
806 static struct GNUNET_SCHEDULER_Task *find_finger_trail_task;
809 * Task that sends verify successor message. This task is started when we get
810 * our successor for the first time.
812 static struct GNUNET_SCHEDULER_Task *send_verify_successor_task;
815 * Task that sends verify successor message. This task is started when we get
816 * our successor for the first time.
818 static struct GNUNET_SCHEDULER_Task *send_verify_successor_retry_task;
821 * Task that sends verify successor message. This task is started when we get
822 * our successor for the first time.
824 static struct GNUNET_SCHEDULER_Task *send_notify_new_successor_retry_task;
827 * Identity of this peer.
829 static struct GNUNET_PeerIdentity my_identity;
832 * Peer map of all the friends of a peer
834 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
837 * Array of all the fingers.
839 static struct FingerInfo finger_table [MAX_FINGERS];
844 static struct GNUNET_CORE_Handle *core_api;
847 * The current finger index that we have want to find trail to. We start the
848 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
849 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
850 * we reset this index to 0.
852 static unsigned int current_search_finger_index;
855 * Time duration to schedule find finger trail task.
857 static struct GNUNET_TIME_Relative find_finger_trail_task_next_send_time;
860 * Time duration to schedule verify successor task.
862 static struct GNUNET_TIME_Relative verify_successor_next_send_time;
865 * Time duration to send verify successor again, if result was not received in time.
867 static struct GNUNET_TIME_Relative verify_successor_retry_time;
870 * Time duration to retry send_notify_successor.
872 static struct GNUNET_TIME_Relative notify_successor_retry_time;
875 * Are we waiting for confirmation from our new successor that it got the
878 //static unsigned int waiting_for_notify_confirmation;
880 /* Below variables are used only for testing, and statistics collection. */
882 * Should we store our topology predecessor and successor IDs into statistics?
884 unsigned int track_topology;
887 * Count of fingers found. Ideally we should have O(logn) fingers for a
890 static unsigned int total_fingers_found;
893 * Number of times we found the same successor.
895 static unsigned int successor_times;
898 * Number of rounds for which we should search for finger.
900 static unsigned int fingers_round_count;
904 * Construct a trail setup message and forward it to @a target_friend
906 * @param source_peer Peer which wants to setup the trail
907 * @param ultimate_destination_finger_value Peer identity closest to this value
908 * will be finger to @a source_peer
909 * @param best_known_destination Best known destination (could be finger or friend)
910 * which should get this message. In case it is
911 * friend, then it is same as target_friend
912 * @param target_friend Friend to which message is forwarded now.
913 * @param trail_length Total number of peers in trail setup so far.
914 * @param trail_peer_list Trail setup so far
915 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
916 * @param trail_id Unique identifier for the trail we are trying to setup.
917 * @param intermediate_trail_id Trail id of intermediate trail to reach to
918 * best_known_destination when its a finger. If not
919 * used then set to 0.
922 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
923 uint64_t ultimate_destination_finger_value,
924 const struct GNUNET_PeerIdentity *best_known_destination,
925 const struct FriendInfo *target_friend,
926 unsigned int trail_length,
927 const struct GNUNET_PeerIdentity *trail_peer_list,
928 unsigned int is_predecessor,
929 const struct GNUNET_HashCode *trail_id,
930 const struct GNUNET_HashCode *intermediate_trail_id)
932 struct GNUNET_MQ_Envelope *env;
933 struct PeerTrailSetupMessage *tsm;
936 msize = trail_length * sizeof (struct GNUNET_PeerIdentity);
937 if (msize + sizeof (struct PeerTrailSetupMessage)
938 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
943 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
945 GNUNET_STATISTICS_update (GDS_stats,
946 gettext_noop ("# P2P messages dropped due to full queue"),
951 env = GNUNET_MQ_msg_extra (tsm,
953 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
954 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
955 tsm->source_peer = *source_peer;
956 tsm->best_known_destination = *best_known_destination;
957 tsm->is_predecessor = htonl (is_predecessor);
958 tsm->trail_id = *trail_id;
959 tsm->intermediate_trail_id = *intermediate_trail_id;
960 GNUNET_memcpy (&tsm[1],
963 GNUNET_MQ_send (target_friend->mq,
969 * Construct a trail setup result message and forward it to @a target_friend.
971 * @param querying_peer Peer which sent the trail setup request and should get
973 * @param Finger Peer to which the trail has been setup to.
974 * @param target_friend Friend to which this message should be forwarded.
975 * @param trail_length Numbers of peers in the trail.
976 * @param trail_peer_list Peers which are part of the trail from
977 * querying_peer to Finger, NOT including them.
978 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
979 * @param ultimate_destination_finger_value Value to which @a finger is the closest
981 * @param trail_id Unique identifier of the trail.
984 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *querying_peer,
985 const struct GNUNET_PeerIdentity *finger,
986 struct FriendInfo *target_friend,
987 unsigned int trail_length,
988 const struct GNUNET_PeerIdentity *trail_peer_list,
989 unsigned int is_predecessor,
990 uint64_t ultimate_destination_finger_value,
991 const struct GNUNET_HashCode *trail_id)
993 struct GNUNET_MQ_Envelope *env;
994 struct PeerTrailSetupResultMessage *tsrm;
997 msize = trail_length * sizeof (struct GNUNET_PeerIdentity);
998 if (msize + sizeof (struct PeerTrailSetupResultMessage)
999 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1004 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1006 GNUNET_STATISTICS_update (GDS_stats,
1007 gettext_noop ("# P2P messages dropped due to full queue"),
1012 env = GNUNET_MQ_msg_extra (tsrm,
1014 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1015 tsrm->querying_peer = *querying_peer;
1016 tsrm->finger_identity = *finger;
1017 tsrm->is_predecessor = htonl (is_predecessor);
1018 tsrm->trail_id = *trail_id;
1019 tsrm->ultimate_destination_finger_value
1020 = GNUNET_htonll (ultimate_destination_finger_value);
1021 GNUNET_memcpy (&tsrm[1],
1024 GNUNET_MQ_send (target_friend->mq,
1030 * Send notify successor confirmation message.
1032 * @param trail_id Unique Identifier of the trail.
1033 * @param trail_direction Destination to Source.
1034 * @param target_friend Friend to get this message next.
1037 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (const struct GNUNET_HashCode *trail_id,
1038 unsigned int trail_direction,
1039 struct FriendInfo *target_friend)
1041 struct PeerNotifyConfirmationMessage *ncm;
1042 struct GNUNET_MQ_Envelope *env;
1044 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1046 GNUNET_STATISTICS_update (GDS_stats,
1047 gettext_noop ("# P2P messages dropped due to full queue"),
1052 env = GNUNET_MQ_msg (ncm,
1053 GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION);
1054 ncm->trail_id = *trail_id;
1055 ncm->trail_direction = htonl (trail_direction);
1056 GNUNET_MQ_send (target_friend->mq,
1062 * Send trail rejection message to @a target_friend
1064 * @param source_peer Peer which is trying to setup the trail.
1065 * @param ultimate_destination_finger_value Peer closest to this value will be
1066 * @a source_peer's finger
1067 * @param congested_peer Peer which sent this message as it is congested.
1068 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1069 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1070 * by congested_peer. This does NOT include @a source_peer
1071 * and congested_peer.
1072 * @param trail_length Total number of peers in trail_peer_list, NOT including
1073 * @a source_peer and @a congested_peer
1074 * @param trail_id Unique identifier of this trail.
1075 * @param congestion_timeout Duration given by congested peer as an estimate of
1076 * how long it may remain congested.
1079 GDS_NEIGHBOURS_send_trail_rejection (const struct GNUNET_PeerIdentity *source_peer,
1080 uint64_t ultimate_destination_finger_value,
1081 const struct GNUNET_PeerIdentity *congested_peer,
1082 unsigned int is_predecessor,
1083 const struct GNUNET_PeerIdentity *trail_peer_list,
1084 unsigned int trail_length,
1085 const struct GNUNET_HashCode *trail_id,
1086 struct FriendInfo *target_friend,
1087 const struct GNUNET_TIME_Relative congestion_timeout)
1089 struct PeerTrailRejectionMessage *trm;
1090 struct GNUNET_MQ_Envelope *env;
1093 msize = trail_length * sizeof (struct GNUNET_PeerIdentity);
1094 if (msize + sizeof (struct PeerTrailRejectionMessage)
1095 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1100 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1102 GNUNET_STATISTICS_update (GDS_stats,
1103 gettext_noop ("# P2P messages dropped due to full queue"),
1108 env = GNUNET_MQ_msg_extra (trm,
1110 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1111 trm->source_peer = *source_peer;
1112 trm->congested_peer = *congested_peer;
1113 trm->congestion_time = congestion_timeout;
1114 trm->is_predecessor = htonl (is_predecessor);
1115 trm->trail_id = *trail_id;
1116 trm->ultimate_destination_finger_value
1117 = GNUNET_htonll (ultimate_destination_finger_value);
1118 GNUNET_memcpy (&trm[1],
1121 GNUNET_MQ_send (target_friend->mq,
1127 * Construct a verify successor message and forward it to target_friend.
1128 * @param source_peer Peer which wants to verify its successor.
1129 * @param successor Peer which is @a source_peer's current successor.
1130 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1131 * NOT including them.
1132 * @param trail List of peers which are part of trail to reach from @a source_peer
1133 * to @a successor, NOT including them.
1134 * @param trail_length Total number of peers in @a trail.
1135 * @param target_friend Next friend to get this message.
1138 GDS_NEIGHBOURS_send_verify_successor_message (const struct GNUNET_PeerIdentity *source_peer,
1139 const struct GNUNET_PeerIdentity *successor,
1140 const struct GNUNET_HashCode *trail_id,
1141 struct GNUNET_PeerIdentity *trail,
1142 unsigned int trail_length,
1143 struct FriendInfo *target_friend)
1145 struct PeerVerifySuccessorMessage *vsm;
1146 struct GNUNET_MQ_Envelope *env;
1149 msize = trail_length * sizeof (struct GNUNET_PeerIdentity);
1150 if (msize + sizeof (*vsm) >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1155 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1157 GNUNET_STATISTICS_update (GDS_stats,
1158 gettext_noop ("# P2P messages dropped due to full queue"),
1163 env = GNUNET_MQ_msg_extra (vsm,
1165 GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1166 vsm->source_peer = *source_peer;
1167 vsm->successor = *successor;
1168 vsm->trail_id = *trail_id;
1169 GNUNET_memcpy (&vsm[1],
1172 GNUNET_MQ_send (target_friend->mq,
1178 * FIXME: In every function we pass target friend except for this one.
1179 * so, either change everything or this one. also, should we just store
1180 * the pointer to friend in routing table rather than gnunet_peeridentity.
1181 * if yes then we should keep friend info in.h andmake lot of changes.
1182 * Construct a trail teardown message and forward it to target friend.
1184 * @param trail_id Unique identifier of the trail.
1185 * @param trail_direction Direction of trail.
1186 * @param target_friend Friend to get this message.
1189 GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_HashCode *trail_id,
1190 unsigned int trail_direction,
1191 const struct GNUNET_PeerIdentity *peer)
1193 struct PeerTrailTearDownMessage *ttdm;
1194 struct GNUNET_MQ_Envelope *env;
1195 struct FriendInfo *target_friend;
1197 if (NULL == (target_friend =
1198 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1201 /* FIXME: In what case friend can be null. ?*/
1205 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1207 GNUNET_STATISTICS_update (GDS_stats,
1208 gettext_noop ("# P2P messages dropped due to full queue"),
1213 env = GNUNET_MQ_msg (ttdm,
1214 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1215 ttdm->trail_id = *trail_id;
1216 ttdm->trail_direction = htonl (trail_direction);
1217 GNUNET_MQ_send (target_friend->mq,
1223 * Construct a verify successor result message and send it to target_friend
1225 * @param querying_peer Peer which sent the verify successor message.
1226 * @param source_successor Current_successor of @a querying_peer.
1227 * @param current_predecessor Current predecessor of @a successor. Could be same
1228 * or different from @a querying_peer.
1229 * @param trail_id Unique identifier of the trail from @a querying_peer to
1230 * @a successor, NOT including them.
1231 * @param trail List of peers which are part of trail from @a querying_peer to
1232 * @a successor, NOT including them.
1233 * @param trail_length Total number of peers in @a trail
1234 * @param trail_direction Direction in which we are sending the message. In this
1235 * case we are sending result from @a successor to @a querying_peer.
1236 * @param target_friend Next friend to get this message.
1239 GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *querying_peer,
1240 const struct GNUNET_PeerIdentity *current_successor,
1241 const struct GNUNET_PeerIdentity *probable_successor,
1242 const struct GNUNET_HashCode *trail_id,
1243 const struct GNUNET_PeerIdentity *trail,
1244 unsigned int trail_length,
1245 enum GDS_ROUTING_trail_direction trail_direction,
1246 struct FriendInfo *target_friend)
1248 struct PeerVerifySuccessorResultMessage *vsmr;
1249 struct GNUNET_MQ_Envelope *env;
1252 msize = trail_length * sizeof(struct GNUNET_PeerIdentity);
1253 if (msize + sizeof (struct PeerVerifySuccessorResultMessage)
1254 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1259 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1261 GNUNET_STATISTICS_update (GDS_stats,
1262 gettext_noop ("# P2P messages dropped due to full queue"),
1267 env = GNUNET_MQ_msg_extra (vsmr,
1269 GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1270 vsmr->querying_peer = *querying_peer;
1271 vsmr->current_successor = *current_successor;
1272 vsmr->probable_successor = *probable_successor;
1273 vsmr->trail_direction = htonl (trail_direction);
1274 vsmr->trail_id = *trail_id;
1275 GNUNET_memcpy (&vsmr[1],
1278 GNUNET_MQ_send (target_friend->mq,
1284 * Construct a notify new successor message and send it to target_friend
1285 * @param source_peer Peer which wants to notify to its new successor that it
1286 * could be its predecessor.
1287 * @param successor New successor of @a source_peer
1288 * @param successor_trail List of peers in Trail to reach from
1289 * @a source_peer to @a new_successor, NOT including
1291 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1292 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1293 * @param target_friend Next friend to get this message.
1296 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1297 const struct GNUNET_PeerIdentity *successor,
1298 const struct GNUNET_PeerIdentity *successor_trail,
1299 unsigned int successor_trail_length,
1300 const struct GNUNET_HashCode *succesor_trail_id,
1301 struct FriendInfo *target_friend)
1303 struct PeerNotifyNewSuccessorMessage *nsm;
1304 struct GNUNET_MQ_Envelope *env;
1307 msize = successor_trail_length * sizeof(struct GNUNET_PeerIdentity);
1308 if (msize + sizeof (struct PeerNotifyNewSuccessorMessage)
1309 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1314 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1316 GNUNET_STATISTICS_update (GDS_stats,
1317 gettext_noop ("# P2P messages dropped due to full queue"),
1322 env = GNUNET_MQ_msg_extra (nsm,
1324 GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1325 nsm->new_successor = *successor;
1326 nsm->source_peer = *source_peer;
1327 nsm->trail_id = *succesor_trail_id;
1328 GNUNET_memcpy (&nsm[1],
1331 GNUNET_MQ_send (target_friend->mq,
1337 * Construct an add_trail message and send it to target_friend
1339 * @param source_peer Source of the trail.
1340 * @param destination_peer Destination of the trail.
1341 * @param trail_id Unique identifier of the trail from
1342 * @a source_peer to @a destination_peer, NOT including the endpoints.
1343 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1344 * NOT including the endpoints.
1345 * @param trail_length Total number of peers in @a trail.
1346 * @param target_friend Next friend to get this message.
1349 GDS_NEIGHBOURS_send_add_trail (const struct GNUNET_PeerIdentity *source_peer,
1350 const struct GNUNET_PeerIdentity *destination_peer,
1351 const struct GNUNET_HashCode *trail_id,
1352 const struct GNUNET_PeerIdentity *trail,
1353 unsigned int trail_length,
1354 struct FriendInfo *target_friend)
1356 struct PeerAddTrailMessage *adm;
1357 struct GNUNET_MQ_Envelope *env;
1360 msize = trail_length * sizeof(struct GNUNET_PeerIdentity);
1361 if (msize + sizeof (struct PeerAddTrailMessage)
1362 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1367 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1369 GNUNET_STATISTICS_update (GDS_stats,
1370 gettext_noop ("# P2P messages dropped due to full queue"),
1375 env = GNUNET_MQ_msg_extra (adm,
1377 GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1378 adm->source_peer = *source_peer;
1379 adm->destination_peer = *destination_peer;
1380 adm->trail_id = *trail_id;
1381 GNUNET_memcpy (&adm[1],
1384 GNUNET_MQ_send (target_friend->mq,
1390 * Search my location in trail. In case I am present more than once in the
1391 * trail (can happen during trail setup), then return my lowest index.
1393 * @param trail List of peers
1394 * @return my_index if found
1395 * trail_length + 1 if an entry is present twice, It is an error.
1396 * -1 if no entry found.
1399 search_my_index (const struct GNUNET_PeerIdentity *trail,
1403 int index_seen = trail_length + 1;
1406 for (i = 0; i < trail_length; i++)
1408 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1411 if(index_seen == (trail_length + 1))
1415 DEBUG("Entry is present twice in trail. Its not allowed\n");
1428 * Check if the friend is congested or have reached maximum number of trails
1429 * it can be part of of.
1430 * @param friend Friend to be checked.
1431 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1432 * #GNUNET_YES if friend is either congested or have crossed threshold
1435 is_friend_congested (struct FriendInfo *friend)
1437 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1438 ((0 == GNUNET_TIME_absolute_get_remaining
1439 (friend->congestion_timestamp).rel_value_us)))
1446 * Select closest finger to value.
1448 * @param peer1 First peer
1449 * @param peer2 Second peer
1450 * @param value Value to be compare
1451 * @return Closest peer
1453 static const struct GNUNET_PeerIdentity *
1454 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1455 const struct GNUNET_PeerIdentity *peer2,
1458 uint64_t peer1_value;
1459 uint64_t peer2_value;
1461 GNUNET_memcpy (&peer1_value, peer1, sizeof (uint64_t));
1462 GNUNET_memcpy (&peer2_value, peer2, sizeof (uint64_t));
1463 peer1_value = GNUNET_ntohll (peer1_value);
1464 peer2_value = GNUNET_ntohll (peer2_value);
1466 if (peer1_value == value)
1471 if (peer2_value == value)
1476 if (value < peer1_value && peer1_value < peer2_value)
1480 else if (value < peer2_value && peer2_value < peer1_value)
1484 else if (peer1_value < value && value < peer2_value)
1488 else if (peer2_value < value && value < peer1_value)
1492 else if (peer1_value < peer2_value && peer2_value < value)
1496 else // if (peer2_value < peer1_value && peer1_value < value)
1504 * Select closest predecessor to value.
1506 * @param peer1 First peer
1507 * @param peer2 Second peer
1508 * @param value Value to be compare
1509 * @return Peer which precedes value in the network.
1511 static const struct GNUNET_PeerIdentity *
1512 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1513 const struct GNUNET_PeerIdentity *peer2,
1516 uint64_t peer1_value;
1517 uint64_t peer2_value;
1519 GNUNET_memcpy (&peer1_value, peer1, sizeof (uint64_t));
1520 GNUNET_memcpy (&peer2_value, peer2, sizeof (uint64_t));
1521 peer1_value = GNUNET_ntohll (peer1_value);
1522 peer2_value = GNUNET_ntohll (peer2_value);
1524 if (peer1_value == value)
1529 if (peer2_value == value)
1534 if (value < peer1_value && peer1_value < peer2_value)
1538 else if (value < peer2_value && peer2_value < peer1_value)
1542 else if (peer1_value < value && value < peer2_value)
1546 else if (peer2_value < value && value < peer1_value)
1550 else if (peer1_value < peer2_value && peer2_value < value)
1554 else // if (peer2_value < peer1_value && peer1_value < value)
1566 test_print_trail (struct GNUNET_PeerIdentity *trail,
1567 unsigned int trail_length)
1569 struct GNUNET_PeerIdentity print_peer;
1572 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1573 __FILE__, __func__,__LINE__,trail_length);
1574 for (i =0 ; i< trail_length; i++)
1576 print_peer = trail[i];
1577 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1578 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1585 * This is a test function to print all the entries of friend table.
1588 test_friend_peermap_print ()
1590 struct FriendInfo *friend;
1591 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1592 struct GNUNET_PeerIdentity print_peer;
1593 struct GNUNET_PeerIdentity key_ret;
1596 print_peer = my_identity;
1597 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1598 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1600 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1602 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1604 (const void **)&friend))
1606 GNUNET_memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1607 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1608 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1616 * This is a test function, to print all the entries of finger table.
1619 test_finger_table_print()
1621 struct FingerInfo *finger;
1622 struct GNUNET_PeerIdentity print_peer;
1623 //struct Trail *trail;
1627 print_peer = my_identity;
1628 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1629 for (i = 0; i < MAX_FINGERS; i++)
1631 finger = &finger_table[i];
1633 if (GNUNET_NO == finger->is_present)
1636 print_peer = finger->finger_identity;
1637 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1638 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1641 for (j = 0; j < finger->trails_count; j++)
1643 trail = &finger->trail_list[j];
1644 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1645 struct Trail_Element *element;
1646 element = trail->trail_head;
1647 for (k = 0; k < trail->trail_length; k++)
1649 print_peer = element->peer;
1650 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1651 element = element->next;
1660 * Select the closest peer among two peers (which should not be same)
1661 * with respect to value and finger_table_index
1662 * NOTE: peer1 != peer2
1663 * @param peer1 First peer
1664 * @param peer2 Second peer
1665 * @param value Value relative to which we find the closest
1666 * @param is_predecessor Is value a predecessor or any other finger.
1667 * @return Closest peer among two peers.
1669 static const struct GNUNET_PeerIdentity *
1670 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1671 const struct GNUNET_PeerIdentity *peer2,
1673 unsigned int is_predecessor)
1675 /* This check is here to ensure that calling function never sends
1676 same peer value in peer1 and peer2. Remove it later. */
1677 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1678 if (1 == is_predecessor)
1679 return select_closest_predecessor (peer1, peer2, value);
1681 // TODO: Change name to something like select_closest_successor!!
1682 return select_closest_finger (peer1, peer2, value);
1687 * Iterate over the list of all the trails of a finger. In case the first
1688 * friend to reach the finger has reached trail threshold or is congested,
1689 * then don't select it. In case there multiple available good trails to reach
1690 * to Finger, choose the one with shortest trail length.
1691 * Note: We use length as parameter. But we can use any other suitable parameter
1693 * @param finger Finger Finger whose trail we have to select.
1694 * @return Trail Selected Trail.
1696 static struct Trail *
1697 select_finger_trail (struct FingerInfo *finger)
1699 struct FriendInfo *friend;
1700 struct Trail *current_finger_trail;
1701 struct Trail *best_trail = NULL;
1704 GNUNET_assert (finger->trails_count > 0);
1705 for (i = 0; i < finger->trails_count; i++)
1707 current_finger_trail = &finger->trail_list[i];
1709 /* No trail stored at this index. */
1710 if (GNUNET_NO == current_finger_trail->is_present)
1713 GNUNET_assert (NULL !=
1715 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1716 ¤t_finger_trail->trail_head->peer)));
1718 /* First friend to reach trail is not free. */
1719 if (GNUNET_YES == is_friend_congested (friend))
1722 if (NULL == best_trail ||
1723 best_trail->trail_length > current_finger_trail->trail_length)
1725 best_trail = current_finger_trail;
1734 * Compare FINGER entry with current successor. If finger's first friend of all
1735 * its trail is not congested and has not crossed trail threshold, then check
1736 * if finger peer identity is closer to final_destination_finger_value than
1737 * current_successor. If yes then update current_successor.
1738 * @param current_successor[in/out]
1742 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
1744 struct FingerInfo *finger;
1745 const struct GNUNET_PeerIdentity *closest_peer;
1746 struct Trail *finger_trail;
1749 /* Iterate over finger table. */
1750 for (i = 0; i < MAX_FINGERS; i++)
1752 finger = &finger_table[i];
1754 if (GNUNET_NO == finger->is_present)
1757 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1758 ¤t_closest_peer->best_known_destination))
1761 /* If I am my own finger, then ignore this finger. */
1762 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1766 /* If finger is a friend, we have already checked it in previous function. */
1767 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1768 &finger->finger_identity)))
1773 closest_peer = select_closest_peer (&finger->finger_identity,
1774 ¤t_closest_peer->best_known_destination,
1775 current_closest_peer->destination_finger_value,
1776 current_closest_peer->is_predecessor);
1778 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity,
1781 /* Choose one of the trail to reach to finger. */
1782 finger_trail = select_finger_trail (finger);
1784 /* In case no trail found, ignore this finger. */
1785 if (NULL == finger_trail)
1788 current_closest_peer->best_known_destination = *closest_peer;
1789 current_closest_peer->next_hop = finger_trail->trail_head->peer;
1790 current_closest_peer->trail_id = finger_trail->trail_id;
1791 current_closest_peer->finger_table_index = i;
1799 * Compare friend entry with current successor.
1800 * If friend identity and current_successor is same, then do nothing.
1801 * If friend is not congested and has not crossed trail threshold, then check
1802 * if friend peer identity is closer to final_destination_finger_value than
1803 * current_successor. If yes then update current_successor.
1805 * @param cls closure
1806 * @param key current public key
1807 * @param value struct Closest_Peer
1808 * @return #GNUNET_YES if we should continue to iterate,
1809 * #GNUNET_NO if not.
1812 compare_friend_and_current_closest_peer (void *cls,
1813 const struct GNUNET_PeerIdentity *key,
1816 struct FriendInfo *friend = value;
1817 struct Closest_Peer *current_closest_peer = cls;
1818 const struct GNUNET_PeerIdentity *closest_peer;
1820 /* Friend is either congested or has crossed threshold. */
1821 if (GNUNET_YES == is_friend_congested (friend))
1824 /* If current_closest_peer and friend identity are same, then do nothing.*/
1825 if (0 == GNUNET_CRYPTO_cmp_peer_identity (friend->id,
1826 ¤t_closest_peer->best_known_destination))
1832 closest_peer = select_closest_peer (friend->id,
1833 ¤t_closest_peer->best_known_destination,
1834 current_closest_peer->destination_finger_value,
1835 current_closest_peer->is_predecessor);
1837 /* Is friend the closest successor? */
1838 if (0 == GNUNET_CRYPTO_cmp_peer_identity (friend->id,
1841 current_closest_peer->best_known_destination = *friend->id;
1842 current_closest_peer->next_hop = *friend->id;
1849 * Initialize current_successor to my_identity.
1850 * @param my_identity My peer identity
1851 * @return Updated closest_peer
1853 static struct Closest_Peer
1854 init_closest_peer (struct GNUNET_PeerIdentity my_identity,
1855 uint64_t destination_finger_value,
1856 unsigned int is_predecessor)
1858 struct Closest_Peer current_closest_peer;
1860 memset (¤t_closest_peer.trail_id,
1862 sizeof(struct GNUNET_HashCode));
1863 current_closest_peer.destination_finger_value = destination_finger_value;
1864 current_closest_peer.is_predecessor = is_predecessor;
1865 current_closest_peer.next_hop = my_identity;
1866 current_closest_peer.best_known_destination = my_identity;
1867 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
1868 return current_closest_peer;
1873 * Find locally best known peer, among your own identity, friend and finger list,
1874 * which is closest to given destination_finger_value.
1876 * NOTE: In case a friend is also a finger, then it is always chosen as friend
1878 * @param destination_finger_value Peer closest to this value will be the next destination.
1879 * @param is_predecessor Are we looking for predecessor or finger?
1880 * @return Closest_Peer that contains all the relevant field to reach to
1881 * @a destination_finger_value
1883 static struct Closest_Peer
1884 find_local_best_known_next_hop (uint64_t destination_finger_value,
1885 unsigned int is_predecessor)
1887 struct Closest_Peer current_closest_peer;
1889 /* Initialize current_successor to my_identity. */
1890 current_closest_peer = init_closest_peer (my_identity,
1891 destination_finger_value,
1894 /* Compare each friend entry with current_successor and update current_successor
1895 * with friend if its closest. */
1898 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
1899 &compare_friend_and_current_closest_peer,
1900 ¤t_closest_peer));
1902 /* Compare each finger entry with current_successor and update current_successor
1903 * with finger if its closest. */
1904 compare_finger_and_current_closest_peer (¤t_closest_peer);
1905 return current_closest_peer;
1910 * Construct a Put message and send it to target_peer.
1911 * @param key Key for the content
1912 * @param block_type Type of the block
1913 * @param options Routing options
1914 * @param desired_replication_level Desired replication count
1915 * @param best_known_dest Peer to which this message should reach eventually,
1916 * as it is best known destination to me.
1917 * @param intermediate_trail_id Trail id in case
1918 * @param target_peer Peer to which this message will be forwarded.
1919 * @param hop_count Number of hops traversed so far.
1920 * @param put_path_length Total number of peers in @a put_path
1921 * @param put_path Number of peers traversed so far
1922 * @param expiration_time When does the content expire
1923 * @param data Content to store
1924 * @param data_size Size of content @a data in bytes
1927 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
1928 enum GNUNET_BLOCK_Type block_type,
1929 enum GNUNET_DHT_RouteOption options,
1930 uint32_t desired_replication_level,
1931 struct GNUNET_PeerIdentity best_known_dest,
1932 struct GNUNET_HashCode intermediate_trail_id,
1933 struct GNUNET_PeerIdentity *target_peer,
1935 uint32_t put_path_length,
1936 struct GNUNET_PeerIdentity *put_path,
1937 struct GNUNET_TIME_Absolute expiration_time,
1938 const void *data, size_t data_size)
1940 struct PeerPutMessage *ppm;
1941 struct GNUNET_MQ_Envelope *env;
1942 struct FriendInfo *target_friend;
1943 struct GNUNET_PeerIdentity *pp;
1946 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size;
1947 if (msize + sizeof (struct PeerPutMessage)
1948 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1950 put_path_length = 0;
1953 if (msize + sizeof (struct PeerPutMessage)
1954 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1960 GNUNET_assert (NULL !=
1962 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1964 env = GNUNET_MQ_msg_extra (ppm,
1966 GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
1967 ppm->options = htonl (options);
1968 ppm->block_type = htonl (block_type);
1969 ppm->hop_count = htonl (hop_count + 1);
1970 ppm->desired_replication_level = htonl (desired_replication_level);
1971 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1972 ppm->best_known_destination = best_known_dest;
1973 ppm->intermediate_trail_id = intermediate_trail_id;
1975 ppm->put_path_length = htonl (put_path_length);
1976 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
1979 put_path_length * sizeof (struct GNUNET_PeerIdentity));
1980 GNUNET_memcpy (&pp[put_path_length],
1983 GNUNET_MQ_send (target_friend->mq,
1989 * Handle the put request from the client.
1991 * @param block_type Type of the block
1992 * @param options Routing options
1993 * @param desired_replication_level Desired replication count
1994 * @param expiration_time When does the content expire
1995 * @param hop_count how many hops has this message traversed so far
1996 * @param bf Bloom filter of peers this PUT has already traversed
1997 * @param key Key for the content
1998 * @param put_path_length number of entries in put_path
1999 * @param put_path peers this request has traversed so far (if tracked)
2000 * @param data Content to store
2001 * @param data_size Size of content @a data in bytes
2002 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
2005 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type block_type,
2006 enum GNUNET_DHT_RouteOption options,
2007 uint32_t desired_replication_level,
2008 struct GNUNET_TIME_Absolute expiration_time,
2010 struct GNUNET_CONTAINER_BloomFilter *bf,
2011 const struct GNUNET_HashCode *key,
2012 unsigned int put_path_length,
2013 struct GNUNET_PeerIdentity *put_path,
2017 struct GNUNET_PeerIdentity best_known_dest;
2018 struct GNUNET_HashCode intermediate_trail_id;
2019 struct GNUNET_PeerIdentity next_hop;
2021 struct Closest_Peer successor;
2023 GNUNET_memcpy (&key_value,
2026 key_value = GNUNET_ntohll (key_value);
2027 successor = find_local_best_known_next_hop (key_value,
2028 GDS_FINGER_TYPE_NON_PREDECESSOR);
2029 best_known_dest = successor.best_known_destination;
2030 next_hop = successor.next_hop;
2031 intermediate_trail_id = successor.trail_id;
2033 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest,
2036 DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",
2038 /* I am the destination. */
2039 GDS_DATACACHE_handle_put (expiration_time,
2046 GDS_CLIENTS_process_put (options,
2049 ntohl (desired_replication_level),
2058 /* In case we are sending the request to a finger, then send across all of its
2060 GDS_NEIGHBOURS_send_put (key,
2063 desired_replication_level,
2065 intermediate_trail_id,
2078 * Construct a Get message and send it to target_peer.
2080 * @param key Key for the content
2081 * @param block_type Type of the block
2082 * @param options Routing options
2083 * @param desired_replication_level Desired replication count
2084 * @param best_known_dest Peer which should get this message. Same as target peer
2085 * if best_known_dest is a friend else its a finger.
2086 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2087 * in case it is a finger else set to 0.
2088 * @param target_peer Peer to which this message will be forwarded.
2089 * @param hop_count Number of hops traversed so far.
2090 * @param data Content to store
2091 * @param data_size Size of content @a data in bytes
2092 * @param get_path_length Total number of peers in @a get_path
2093 * @param get_path Number of peers traversed so far
2096 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2097 enum GNUNET_BLOCK_Type block_type,
2098 enum GNUNET_DHT_RouteOption options,
2099 uint32_t desired_replication_level,
2100 const struct GNUNET_PeerIdentity *best_known_dest,
2101 const struct GNUNET_HashCode *intermediate_trail_id,
2102 const struct GNUNET_PeerIdentity *target_peer,
2104 uint32_t get_path_length,
2105 const struct GNUNET_PeerIdentity *get_path)
2107 struct PeerGetMessage *pgm;
2108 struct GNUNET_MQ_Envelope *env;
2109 struct FriendInfo *target_friend;
2112 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity);
2113 if (msize + sizeof (struct PeerGetMessage)
2114 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2119 GNUNET_assert (NULL !=
2121 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2123 env = GNUNET_MQ_msg_extra (pgm,
2125 GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2126 pgm->get_path_length = htonl (get_path_length);
2127 pgm->best_known_destination = *best_known_dest;
2129 pgm->intermediate_trail_id = *intermediate_trail_id;
2130 pgm->hop_count = htonl (hop_count + 1);
2131 pgm->get_path_length = htonl (get_path_length);
2132 GNUNET_memcpy (&pgm[1],
2135 GNUNET_MQ_send (target_friend->mq,
2141 * Send the get result to requesting client.
2143 * @param key Key of the requested data.
2144 * @param block_type Block type
2145 * @param target_peer Next peer to forward the message to.
2146 * @param source_peer Peer which has the data for the key.
2147 * @param put_path_length Number of peers in @a put_path
2148 * @param put_path Path taken to put the data at its stored location.
2149 * @param get_path_length Number of peers in @a get_path
2150 * @param get_path Path taken to reach to the location of the key.
2151 * @param expiration When will this result expire?
2152 * @param data Payload to store
2153 * @param data_size Size of the @a data
2156 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2157 enum GNUNET_BLOCK_Type block_type,
2158 const struct GNUNET_PeerIdentity *target_peer,
2159 const struct GNUNET_PeerIdentity *source_peer,
2160 unsigned int put_path_length,
2161 const struct GNUNET_PeerIdentity *put_path,
2162 unsigned int get_path_length,
2163 const struct GNUNET_PeerIdentity *get_path,
2164 struct GNUNET_TIME_Absolute expiration,
2165 const void *data, size_t data_size)
2167 struct PeerGetResultMessage *get_result;
2168 struct GNUNET_PeerIdentity *paths;
2169 struct GNUNET_MQ_Envelope *env;
2170 struct FriendInfo *target_friend;
2171 int current_path_index;
2174 msize = (put_path_length + get_path_length) * sizeof (struct GNUNET_PeerIdentity) +
2176 if (msize + sizeof (struct PeerGetResultMessage)
2177 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2179 put_path_length = 0;
2182 if (msize + sizeof (struct PeerGetResultMessage)
2183 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2188 current_path_index = 0;
2189 if (get_path_length > 0)
2191 current_path_index = search_my_index (get_path,
2193 if (-1 == current_path_index)
2198 if ((get_path_length + 1) == current_path_index)
2200 DEBUG ("Peer found twice in get path. Not allowed \n");
2205 if (0 == current_path_index)
2207 DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",
2209 GNUNET_i2s (&my_identity));
2210 GDS_CLIENTS_handle_reply (expiration,
2221 env = GNUNET_MQ_msg_extra (get_result,
2223 GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2224 get_result->key = *key;
2225 get_result->querying_peer = *source_peer;
2226 get_result->expiration_time = GNUNET_TIME_absolute_hton (expiration);
2227 get_result->get_path_length = htonl (get_path_length);
2228 get_result->put_path_length = htonl (put_path_length);
2229 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2230 GNUNET_memcpy (paths,
2232 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2233 GNUNET_memcpy (&paths[put_path_length],
2235 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2236 GNUNET_memcpy (&paths[put_path_length + get_path_length],
2240 GNUNET_assert (NULL !=
2242 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2243 &get_path[current_path_index - 1])));
2244 GNUNET_MQ_send (target_friend->mq,
2250 * Handle a result for a GET operation.
2252 * @param cls closure
2253 * @param type type of the block
2254 * @param expiration_time when does the content expire
2255 * @param key key for the content
2256 * @param put_path_length number of entries in @a put_path
2257 * @param put_path peers the original PUT traversed (if tracked)
2258 * @param get_path_length number of entries in @a get_path
2259 * @param get_path peers this reply has traversed so far (if tracked)
2260 * @param data payload of the reply
2261 * @param data_size number of bytes in @a data
2265 enum GNUNET_BLOCK_Type type,
2266 struct GNUNET_TIME_Absolute expiration_time,
2267 const struct GNUNET_HashCode *key,
2268 unsigned int put_path_length,
2269 const struct GNUNET_PeerIdentity *put_path,
2270 unsigned int get_path_length,
2271 const struct GNUNET_PeerIdentity *get_path,
2275 struct GNUNET_PeerIdentity *target_peer = cls;
2277 GDS_NEIGHBOURS_send_get_result (key,
2292 * Perform a GET operation. Forwards the given request to other
2293 * peers. Does not lookup the key locally. May do nothing if this is
2294 * the only peer in the network (or if we are the closest peer in the
2297 * @param block_type type of the block
2298 * @param options routing options
2299 * @param desired_replication_level desired replication count
2300 * @param hop_count how many hops did this request traverse so far?
2301 * @param key key for the content
2302 * @param xquery extended query
2303 * @param xquery_size number of bytes in @a xquery
2304 * @param reply_bf bloomfilter to filter duplicates
2305 * @param reply_bf_mutator mutator for @a reply_bf
2306 * @param peer_bf filter for peers not to select (again, updated)
2307 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
2310 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type block_type,
2311 enum GNUNET_DHT_RouteOption options,
2312 uint32_t desired_replication_level,
2314 const struct GNUNET_HashCode *key,
2315 const void *xquery, size_t xquery_size,
2316 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
2317 uint32_t reply_bf_mutator,
2318 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
2320 struct Closest_Peer successor;
2321 struct GNUNET_PeerIdentity best_known_dest;
2322 struct GNUNET_HashCode intermediate_trail_id;
2325 GNUNET_memcpy (&key_value,
2328 key_value = GNUNET_ntohll (key_value);
2329 successor = find_local_best_known_next_hop (key_value,
2330 GDS_FINGER_TYPE_NON_PREDECESSOR);
2331 best_known_dest = successor.best_known_destination;
2332 intermediate_trail_id = successor.trail_id;
2334 /* I am the destination. I have the data. */
2335 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2338 GDS_DATACACHE_handle_get (key,
2349 GDS_NEIGHBOURS_send_get (key,
2352 desired_replication_level,
2354 &intermediate_trail_id,
2355 &successor.next_hop,
2364 * Randomly choose one of your friends (which is not congested and have not crossed
2365 * trail threshold) from the friend_peermap
2366 * @return Friend Randomly chosen friend.
2367 * NULL in case friend peermap is empty, or all the friends are either
2368 * congested or have crossed trail threshold.
2370 static struct FriendInfo *
2371 select_random_friend ()
2373 unsigned int current_size;
2376 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2377 struct GNUNET_PeerIdentity key_ret;
2378 struct FriendInfo *friend;
2380 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2383 if (0 == current_size)
2386 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2387 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2389 /* Iterate till you don't reach to index. */
2390 for (j = 0; j < index ; j++)
2391 GNUNET_assert (GNUNET_YES ==
2392 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2396 /* Reset the index in friend peermap to 0 as we reached to the end. */
2397 if (j == current_size)
2400 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2401 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2405 /* Get the friend stored at the index, j*/
2406 GNUNET_assert (GNUNET_YES ==
2407 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2409 (const void **)&friend));
2411 /* This friend is not congested and has not crossed trail threshold. */
2412 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2413 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2419 } while (j != index);
2421 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2427 * Compute 64 bit value of finger_identity corresponding to a finger index using
2429 * For all fingers, n.finger[i] = n + pow (2,i),
2430 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2431 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2433 * @param finger_index Index corresponding to which we calculate 64 bit value.
2434 * @return 64 bit value.
2437 compute_finger_identity_value (unsigned int finger_index)
2441 GNUNET_memcpy (&my_id64,
2444 my_id64 = GNUNET_ntohll (my_id64);
2446 /* Are we looking for immediate predecessor? */
2447 if (PREDECESSOR_FINGER_ID == finger_index)
2448 return (my_id64 - 1);
2449 uint64_t add = (uint64_t)1 << finger_index;
2450 return (my_id64 + add);
2455 * Choose a random friend. Calculate the next finger identity to search,from
2456 * current_search_finger_index. Start looking for the trail to reach to
2457 * finger identity through this random friend.
2459 * @param cls closure for this task
2462 send_find_finger_trail_message (void *cls)
2464 struct FriendInfo *target_friend;
2465 struct GNUNET_HashCode trail_id;
2466 struct GNUNET_HashCode intermediate_trail_id;
2467 unsigned int is_predecessor = 0;
2468 uint64_t finger_id_value;
2470 /* Schedule another send_find_finger_trail_message task. After one round of
2471 * finger search, this time is exponentially backoff. */
2472 find_finger_trail_task_next_send_time.rel_value_us =
2473 find_finger_trail_task_next_send_time.rel_value_us +
2474 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2475 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2476 find_finger_trail_task =
2477 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2478 &send_find_finger_trail_message,
2481 /* No space in my routing table. (Source and destination peers also store entries
2482 * in their routing table). */
2483 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2486 target_friend = select_random_friend ();
2487 if (NULL == target_friend)
2490 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2491 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2494 /* Generate a unique trail id for trail we are trying to setup. */
2495 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2498 memset (&intermediate_trail_id,
2500 sizeof (struct GNUNET_HashCode));
2501 GDS_NEIGHBOURS_send_trail_setup (&my_identity,
2508 &intermediate_trail_id);
2513 * In case there are already maximum number of possible trails to reach to a
2514 * finger, then check if the new trail's length is lesser than any of the
2516 * If yes then replace that old trail by new trail.
2518 * Note: Here we are taking length as a parameter to choose the best possible
2519 * trail, but there could be other parameters also like:
2520 * 1. duration of existence of a trail - older the better.
2521 * 2. if the new trail is completely disjoint than the
2522 * other trails, then may be choosing it is better.
2524 * @param finger Finger
2525 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2526 * including the endpoints.
2527 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2528 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2531 select_and_replace_trail (struct FingerInfo *finger,
2532 const struct GNUNET_PeerIdentity *new_trail,
2533 unsigned int new_trail_length,
2534 const struct GNUNET_HashCode *new_trail_id)
2536 struct Trail *current_trail;
2537 unsigned int largest_trail_length;
2538 unsigned int largest_trail_index;
2539 struct Trail_Element *trail_element;
2540 const struct GNUNET_PeerIdentity *next_hop;
2543 largest_trail_length = new_trail_length;
2544 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2546 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2548 for (i = 0; i < finger->trails_count; i++)
2550 current_trail = &finger->trail_list[i];
2551 GNUNET_assert (GNUNET_YES == current_trail->is_present);
2552 if (current_trail->trail_length > largest_trail_length)
2554 largest_trail_length = current_trail->trail_length;
2555 largest_trail_index = i;
2559 /* New trail is not better than existing ones. Send trail teardown. */
2560 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2562 next_hop = GDS_ROUTING_get_next_hop (new_trail_id,
2563 GDS_ROUTING_SRC_TO_DEST);
2564 GDS_ROUTING_remove_trail (new_trail_id);
2565 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2566 GDS_ROUTING_SRC_TO_DEST,
2571 /* Send trail teardown message across the replaced trail. */
2572 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2573 next_hop = GDS_ROUTING_get_next_hop (&replace_trail->trail_id,
2574 GDS_ROUTING_SRC_TO_DEST);
2575 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (&replace_trail->trail_id));
2576 GDS_NEIGHBOURS_send_trail_teardown (&replace_trail->trail_id,
2577 GDS_ROUTING_SRC_TO_DEST,
2580 /* Free the trail. */
2581 while (NULL != (trail_element = replace_trail->trail_head))
2583 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2584 replace_trail->trail_tail,
2586 GNUNET_free_non_null (trail_element);
2589 /* Add new trial at that location. */
2590 replace_trail->is_present = GNUNET_YES;
2591 replace_trail->trail_length = new_trail_length;
2592 replace_trail->trail_id = *new_trail_id;
2594 for (i = 0; i < new_trail_length; i++)
2596 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2597 element->peer = new_trail[i];
2599 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2600 replace_trail->trail_tail,
2603 /* FIXME: URGENT Are we adding the trail back to the list. */
2608 * Check if the new trail to reach to finger is unique or do we already have
2609 * such a trail present for finger.
2610 * @param existing_finger Finger identity
2611 * @param new_trail New trail to reach @a existing_finger
2612 * @param trail_length Total number of peers in new_trail.
2613 * @return #GNUNET_YES if the new trail is unique
2614 * #GNUNET_NO if same trail is already present.
2617 is_new_trail_unique (struct FingerInfo *existing_finger,
2618 const struct GNUNET_PeerIdentity *new_trail,
2619 unsigned int trail_length)
2621 struct Trail *current_trail;
2622 struct Trail_Element *trail_element;
2626 GNUNET_assert (existing_finger->trails_count > 0);
2628 /* Iterate over list of trails. */
2629 for (i = 0; i < existing_finger->trails_count; i++)
2631 current_trail = &(existing_finger->trail_list[i]);
2632 if(GNUNET_NO == current_trail->is_present)
2635 /* New trail and existing trail length are not same. */
2636 if (current_trail->trail_length != trail_length)
2641 trail_element = current_trail->trail_head;
2642 for (j = 0; j < current_trail->trail_length; j++)
2644 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2645 &trail_element->peer))
2649 trail_element = trail_element->next;
2657 * FIXME; In case of multiple trails, we may have a case where a trail from in
2658 * between has been removed, then we should try to find a free slot , not simply
2659 * add a trail at then end of the list.
2660 * Add a new trail at a free slot in trail array of existing finger.
2661 * @param existing_finger Finger
2662 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2663 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2664 * @param new_finger_trail_id Unique identifier of the trail.
2667 add_new_trail (struct FingerInfo *existing_finger,
2668 const struct GNUNET_PeerIdentity *new_trail,
2669 unsigned int new_trail_length,
2670 const struct GNUNET_HashCode *new_trail_id)
2672 struct FriendInfo *friend;
2673 struct Trail *trail;
2677 if (GNUNET_NO == is_new_trail_unique (existing_finger,
2682 for (i = 0; i < existing_finger->trails_count; i++)
2684 if (GNUNET_NO == existing_finger->trail_list[i].is_present)
2691 if (-1 == free_slot)
2694 trail = &existing_finger->trail_list[free_slot];
2695 GNUNET_assert (GNUNET_NO == trail->is_present);
2696 trail->trail_id = *new_trail_id;
2697 trail->trail_length = new_trail_length;
2698 existing_finger->trails_count++;
2699 trail->is_present = GNUNET_YES;
2700 if (0 == new_trail_length)
2702 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2703 &existing_finger->finger_identity);
2707 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2710 GNUNET_assert (NULL != friend);
2711 friend->trails_count++;
2712 for (i = 0; i < new_trail_length; i++)
2714 struct Trail_Element *element;
2716 element = GNUNET_new (struct Trail_Element);
2717 element->peer = new_trail[i];
2718 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2723 existing_finger->trail_list[free_slot].trail_head = trail->trail_head;
2724 existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail;
2725 existing_finger->trail_list[free_slot].trail_length = new_trail_length;
2726 existing_finger->trail_list[free_slot].trail_id = *new_trail_id;
2727 existing_finger->trail_list[free_slot].is_present = GNUNET_YES;
2733 * FIXME; In case of multiple trails, we may have a case where a trail from in
2734 * between has been removed, then we should try to find a free slot , not simply
2735 * add a trail at then end of the list.
2736 * Add a new trail at a free slot in trail array of existing finger.
2737 * @param existing_finger Finger
2738 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2739 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2740 * @param new_finger_trail_id Unique identifier of the trail.
2743 add_new_trail (struct FingerInfo *existing_finger,
2744 const struct GNUNET_PeerIdentity *new_trail,
2745 unsigned int new_trail_length,
2746 const struct GNUNET_HashCode *new_trail_id)
2748 struct Trail *trail;
2749 struct FriendInfo *first_friend;
2753 if (GNUNET_NO == is_new_trail_unique (existing_finger,
2758 index = existing_finger->trails_count;
2759 trail = &existing_finger->trail_list[index];
2760 GNUNET_assert (GNUNET_NO == trail->is_present);
2761 trail->trail_id = *new_trail_id;
2762 trail->trail_length = new_trail_length;
2763 existing_finger->trails_count++;
2764 trail->is_present = GNUNET_YES;
2766 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2767 &existing_finger->finger_identity)));
2768 /* If finger is a friend then we never call this function. */
2769 GNUNET_assert (new_trail_length > 0);
2771 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2773 first_friend->trails_count++;
2775 for (i = 0; i < new_trail_length; i++)
2777 struct Trail_Element *element;
2779 element = GNUNET_new (struct Trail_Element);
2780 element->peer = new_trail[i];
2781 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2785 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2786 existing_finger->trail_list[index].trail_head = trail->trail_head;
2787 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2788 existing_finger->trail_list[index].trail_length = new_trail_length;
2789 existing_finger->trail_list[index].trail_id = *new_trail_id;
2790 existing_finger->trail_list[index].is_present = GNUNET_YES;
2795 * Get the next hop to send trail teardown message from routing table and
2796 * then delete the entry from routing table. Send trail teardown message for a
2797 * specific trail of a finger.
2798 * @param finger Finger whose trail is to be removed.
2799 * @param trail List of peers in trail from me to a finger, NOT including
2803 send_trail_teardown (struct FingerInfo *finger,
2804 struct Trail *trail)
2806 struct FriendInfo *friend;
2807 const struct GNUNET_PeerIdentity *next_hop;
2809 next_hop = GDS_ROUTING_get_next_hop (&trail->trail_id,
2810 GDS_ROUTING_SRC_TO_DEST);
2811 if (NULL == next_hop)
2813 // DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d",
2814 // GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length);
2817 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2820 GNUNET_assert(GNUNET_YES == trail->is_present);
2821 if (trail->trail_length > 0)
2823 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2824 &trail->trail_head->peer);
2828 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2829 &finger->finger_identity);
2834 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2836 GNUNET_h2s (&trail->trail_id),
2837 GNUNET_i2s(&my_identity),
2838 trail->trail_length);
2841 if ( (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop,
2843 (0 == trail->trail_length))
2845 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2847 GNUNET_h2s (&trail->trail_id),
2848 GNUNET_i2s (&my_identity),
2849 trail->trail_length);
2852 GNUNET_assert (GNUNET_YES ==
2853 GDS_ROUTING_remove_trail (&trail->trail_id));
2854 friend->trails_count--;
2855 GDS_NEIGHBOURS_send_trail_teardown (&trail->trail_id,
2856 GDS_ROUTING_SRC_TO_DEST,
2862 * Send trail teardown message across all the trails to reach to finger.
2863 * @param finger Finger whose all the trail should be freed.
2866 send_all_finger_trails_teardown (struct FingerInfo *finger)
2868 for (unsigned int i = 0; i < finger->trails_count; i++)
2870 struct Trail *trail;
2872 trail = &finger->trail_list[i];
2873 if (GNUNET_YES == trail->is_present)
2875 send_trail_teardown (finger, trail);
2876 trail->is_present = GNUNET_NO;
2883 * Free a specific trail
2884 * @param trail List of peers to be freed.
2887 free_trail (struct Trail *trail)
2889 struct Trail_Element *trail_element;
2891 while (NULL != (trail_element = trail->trail_head))
2893 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2896 GNUNET_free_non_null (trail_element);
2898 trail->trail_head = NULL;
2899 trail->trail_tail = NULL;
2904 * Free finger and its trail.
2906 * @param finger Finger to be freed.
2907 * @param finger_table_index Index at which finger is stored.
2910 free_finger (struct FingerInfo *finger,
2911 unsigned int finger_table_index)
2913 struct Trail *trail;
2915 for (unsigned int i = 0; i < finger->trails_count; i++)
2917 trail = &finger->trail_list[i];
2918 if (GNUNET_NO == trail->is_present)
2921 if (trail->trail_length > 0)
2923 trail->is_present = GNUNET_NO;
2926 finger->is_present = GNUNET_NO;
2927 memset (&finger_table[finger_table_index],
2929 sizeof (finger_table[finger_table_index]));
2934 * Add a new entry in finger table at finger_table_index.
2935 * In case I am my own finger, then we don't have a trail. In case of a friend,
2936 * we have a trail with unique id and '0' trail length.
2937 * In case a finger is a friend, then increment the trails count of the friend.
2939 * @param finger_identity Peer Identity of new finger
2940 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2941 * @param finger_trail_length Total number of peers in @a finger_trail.
2942 * @param trail_id Unique identifier of the trail.
2943 * @param finger_table_index Index in finger table.
2946 add_new_finger (const struct GNUNET_PeerIdentity *finger_identity,
2947 const struct GNUNET_PeerIdentity *finger_trail,
2948 unsigned int finger_trail_length,
2949 const struct GNUNET_HashCode *trail_id,
2950 unsigned int finger_table_index)
2952 struct FingerInfo *new_entry;
2953 struct FriendInfo *first_trail_hop;
2954 struct Trail *trail;
2957 new_entry = GNUNET_new (struct FingerInfo);
2958 new_entry->finger_identity = *finger_identity;
2959 new_entry->finger_table_index = finger_table_index;
2960 new_entry->is_present = GNUNET_YES;
2962 /* If the new entry is my own identity. */
2963 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2966 new_entry->trails_count = 0;
2967 finger_table[finger_table_index] = *new_entry;
2968 GNUNET_free (new_entry);
2972 /* Finger is a friend. */
2973 if (0 == finger_trail_length)
2975 new_entry->trail_list[0].trail_id = *trail_id;
2976 new_entry->trails_count = 1;
2977 new_entry->trail_list[0].is_present = GNUNET_YES;
2978 new_entry->trail_list[0].trail_length = 0;
2979 new_entry->trail_list[0].trail_head = NULL;
2980 new_entry->trail_list[0].trail_tail = NULL;
2981 finger_table[finger_table_index] = *new_entry;
2982 GNUNET_assert (NULL !=
2984 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2987 first_trail_hop->trails_count++;
2988 GNUNET_free (new_entry);
2992 GNUNET_assert (NULL !=
2994 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2995 &finger_trail[0])));
2996 new_entry->trails_count = 1;
2997 first_trail_hop->trails_count++;
2998 /* Copy the finger trail into trail. */
2999 trail = &new_entry->trail_list[0];
3000 for(i = 0; i < finger_trail_length; i++)
3002 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3004 element->next = NULL;
3005 element->prev = NULL;
3006 element->peer = finger_trail[i];
3007 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3012 /* Add trail to trail list. */
3013 trail->trail_length = finger_trail_length;
3014 trail->trail_id = *trail_id;
3015 trail->is_present = GNUNET_YES;
3016 finger_table[finger_table_index] = *new_entry;
3017 GNUNET_free (new_entry);
3022 * Periodic task to verify current successor. There can be multiple trails to reach
3023 * to successor, choose the shortest one and send verify successor message
3024 * across that trail.
3026 * @param cls closure for this task
3029 send_verify_successor_message (void *cls)
3031 struct FriendInfo *target_friend;
3032 struct Trail *trail;
3033 struct Trail_Element *element;
3034 unsigned int trail_length;
3036 struct FingerInfo *successor;
3038 successor = &finger_table[0];
3040 /* This task will be scheduled when the result for Verify Successor is received. */
3041 send_verify_successor_task = NULL;
3043 /* When verify successor is being called for first time *for current context*
3044 * cls will be NULL. If send_verify_successor_retry_task is not NO_TASK, we
3045 * must cancel the retry task scheduled for verify_successor of previous
3050 /* FIXME: Here we are scheduling a new verify successor task, as we
3051 got a new successor. But a send verify successor task may be in progress.
3052 1. We need to be sure that this is indeed a new successor. As this function
3053 is called even if we add a new trail to reach t old successor.
3054 2. Assuming the new successor is different, then verify successor message
3055 * to old successor may be following stages.
3056 * --> Waiting for verify successor result. Don't wait anymore. there is
3057 * no trail to reach from old successor to me, hence, routing
3059 * --> Waiting for notify confirmation. again don't wait for it. notify
3060 * confirmation will not succeded.
3062 if (send_verify_successor_retry_task != NULL)
3064 /* FIXME: Are we scheduling retry task as soon as we send verify message.
3065 If yes then here before making this task, first check if the message
3066 is for the same peer again. */
3067 struct VerifySuccessorContext *old_ctx =
3068 GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
3069 /* old_ctx must not be NULL, as the retry task had been scheduled */
3070 GNUNET_assert(NULL != old_ctx);
3071 GNUNET_free(old_ctx);
3072 /* FIXME: Why don't we reset the task to NO_TASK here? */
3075 struct VerifySuccessorContext *ctx;
3076 ctx = GNUNET_new (struct VerifySuccessorContext);
3078 ctx->num_retries_scheduled++;
3079 send_verify_successor_retry_task =
3080 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3081 &send_verify_successor_message,
3086 /* This is a retry attempt for verify_successor for a previous context */
3087 struct VerifySuccessorContext *ctx;
3090 ctx->num_retries_scheduled++;
3091 send_verify_successor_retry_task =
3092 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3093 &send_verify_successor_message,
3097 /* Among all the trails to reach to successor, select first one which is present.*/
3098 for (i = 0; i < successor->trails_count; i++)
3100 trail = &successor->trail_list[i];
3101 if (GNUNET_YES == trail->is_present)
3105 /* No valid trail found to reach to successor. */
3106 if (i == successor->trails_count)
3109 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3110 &successor->finger_identity));
3111 /* Trail stored at this index. */
3112 GNUNET_assert (GNUNET_YES == trail->is_present);
3113 if (NULL == GDS_ROUTING_get_next_hop (&trail->trail_id,
3114 GDS_ROUTING_SRC_TO_DEST))
3116 DEBUG (" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
3117 GNUNET_i2s (&my_identity),
3118 GNUNET_h2s (&trail->trail_id),
3123 trail_length = trail->trail_length;
3124 if (trail_length > 0)
3126 /* Copy the trail into peer list. */
3127 struct GNUNET_PeerIdentity peer_list[trail_length];
3129 element = trail->trail_head;
3130 for(i = 0; i < trail_length; i++)
3132 peer_list[i] = element->peer;
3133 element = element->next;
3135 GNUNET_assert (NULL != (target_friend =
3136 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3138 GDS_NEIGHBOURS_send_verify_successor_message (&my_identity,
3139 &successor->finger_identity,
3147 GNUNET_assert (NULL != (target_friend =
3148 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3149 &successor->finger_identity)));
3150 GDS_NEIGHBOURS_send_verify_successor_message (&my_identity,
3151 &successor->finger_identity,
3161 * FIXME: should this be a periodic task, incrementing the search finger index?
3162 * Update the current search finger index.
3163 * @a finger_identity
3164 * @a finger_table_index
3167 update_current_search_finger_index (unsigned int finger_table_index)
3169 struct FingerInfo *successor;
3171 /* FIXME correct this: only move current index periodically */
3172 if (finger_table_index != current_search_finger_index)
3175 successor = &finger_table[0];
3176 GNUNET_assert (GNUNET_YES == successor->is_present);
3178 /* We were looking for immediate successor. */
3179 if (0 == current_search_finger_index)
3181 current_search_finger_index = PREDECESSOR_FINGER_ID;
3182 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3183 &successor->finger_identity))
3185 if (NULL == send_verify_successor_task)
3187 send_verify_successor_task
3188 = GNUNET_SCHEDULER_add_now (&send_verify_successor_message,
3194 current_search_finger_index--;
3199 * Get the least significant bit set in val.
3202 * @return Position of first bit set, 65 in case of error.
3205 find_set_bit (uint64_t val)
3225 return 65; /* Some other bit was set to 1 as well. */
3232 * Calculate finger_table_index from initial 64 bit finger identity value that
3233 * we send in trail setup message.
3234 * @param ultimate_destination_finger_value Value that we calculated from our
3235 * identity and finger_table_index.
3236 * @param is_predecessor Is the entry for predecessor or not?
3237 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3238 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3241 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3242 unsigned int is_predecessor)
3246 unsigned int finger_table_index;
3248 GNUNET_memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3249 my_id64 = GNUNET_ntohll (my_id64);
3251 /* Is this a predecessor finger? */
3252 if (1 == is_predecessor)
3254 diff = my_id64 - ultimate_destination_finger_value;
3256 finger_table_index = PREDECESSOR_FINGER_ID;
3258 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3263 diff = ultimate_destination_finger_value - my_id64;
3264 finger_table_index = find_set_bit (diff);
3266 return finger_table_index;
3271 * Remove finger and its associated data structures from finger table.
3272 * @param existing_finger Finger to be removed which is in finger table.
3273 * @param finger_table_index Index in finger table where @a existing_finger
3277 remove_existing_finger (struct FingerInfo *existing_finger,
3278 unsigned int finger_table_index)
3280 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3282 /* If I am my own finger, then we have no trails. */
3283 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3286 existing_finger->is_present = GNUNET_NO;
3287 memset ((void *)&finger_table[finger_table_index], 0,
3288 sizeof (finger_table[finger_table_index]));
3292 /* For all other fingers, send trail teardown across all the trails to reach
3293 finger, and free the finger. */
3294 send_all_finger_trails_teardown (existing_finger);
3295 free_finger (existing_finger, finger_table_index);
3300 * Check if there is already an entry in finger_table at finger_table_index.
3301 * We get the finger_table_index from 64bit finger value we got from the network.
3302 * -- If yes, then select the closest finger.
3303 * -- If new and existing finger are same, then check if you can store more
3305 * -- If yes then add trail, else keep the best trails to reach to the
3307 * -- If the new finger is closest, remove the existing entry, send trail
3308 * teardown message across all the trails to reach the existing entry.
3309 * Add the new finger.
3310 * -- If new and existing finger are different, and existing finger is closest
3312 * -- Update current_search_finger_index.
3313 * @param finger_identity Peer Identity of new finger
3314 * @param finger_trail Trail to reach the new finger
3315 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3316 * @param is_predecessor Is this entry for predecessor in finger_table?
3317 * @param finger_value 64 bit value of finger identity that we got from network.
3318 * @param finger_trail_id Unique identifier of @finger_trail.
3321 finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
3322 const struct GNUNET_PeerIdentity *finger_trail,
3323 unsigned int finger_trail_length,
3324 unsigned int is_predecessor,
3325 uint64_t finger_value,
3326 const struct GNUNET_HashCode *finger_trail_id)
3328 struct FingerInfo *existing_finger;
3329 const struct GNUNET_PeerIdentity *closest_peer;
3330 struct FingerInfo *successor;
3331 unsigned int finger_table_index;
3333 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3334 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3336 /* Invalid finger_table_index. */
3337 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3339 GNUNET_break_op (0);
3343 /* Check if new entry is same as successor. */
3344 if ((0 != finger_table_index) &&
3345 (PREDECESSOR_FINGER_ID != finger_table_index))
3347 successor = &finger_table[0];
3348 if (GNUNET_NO == successor->is_present)
3350 GNUNET_break (0); //ASSERTION FAILS HERE. FIXME
3353 if (0 == GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3354 &successor->finger_identity))
3356 if (0 == fingers_round_count)
3358 find_finger_trail_task_next_send_time =
3359 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3362 fingers_round_count--;
3363 current_search_finger_index = 0;
3364 GNUNET_STATISTICS_update (GDS_stats,
3366 ("# FINGERS_COUNT"), (int64_t) total_fingers_found,
3368 total_fingers_found = 0;
3372 struct FingerInfo prev_finger;
3373 prev_finger = finger_table[finger_table_index - 1];
3374 if (0 == GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3375 &prev_finger.finger_identity))
3377 current_search_finger_index--;
3382 total_fingers_found++;
3383 existing_finger = &finger_table[finger_table_index];
3385 /* No entry present in finger_table for given finger map index. */
3386 if (GNUNET_NO == existing_finger->is_present)
3388 /* Shorten the trail if possible. */
3389 add_new_finger (finger_identity,
3391 finger_trail_length,
3393 finger_table_index);
3394 update_current_search_finger_index (finger_table_index);
3398 /* If existing entry and finger identity are not same. */
3399 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3402 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3407 /* If the new finger is the closest peer. */
3408 if (0 == GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3411 remove_existing_finger (existing_finger,
3412 finger_table_index);
3413 add_new_finger (finger_identity,
3415 finger_trail_length,
3417 finger_table_index);
3421 /* Existing finger is the closest one. We need to send trail teardown
3422 across the trail setup in routing table of all the peers. */
3423 if (0 != GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3426 if (finger_trail_length > 0)
3427 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3428 GDS_ROUTING_SRC_TO_DEST,
3431 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3432 GDS_ROUTING_SRC_TO_DEST,
3439 /* If both new and existing entry are same as my_identity, then do nothing. */
3440 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3446 /* If there is space to store more trails. */
3447 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3448 add_new_trail (existing_finger,
3450 finger_trail_length,
3453 select_and_replace_trail (existing_finger,
3455 finger_trail_length,
3458 update_current_search_finger_index (finger_table_index);
3464 * Verify validity of P2P put messages.
3466 * @param cls closure
3467 * @param put the message
3468 * @return #GNUNET_OK if the message is well-formed
3471 check_dht_p2p_put (void *cls,
3472 const struct PeerPutMessage *put)
3477 msize = ntohs (put->header.size);
3478 putlen = ntohl (put->put_path_length);
3480 sizeof (struct PeerPutMessage) +
3481 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3483 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3485 GNUNET_break_op (0);
3486 return GNUNET_SYSERR;
3493 * Core handler for P2P put messages.
3495 * @param cls closure
3496 * @param put the message
3499 handle_dht_p2p_put (void *cls,
3500 const struct PeerPutMessage *put)
3502 struct GNUNET_PeerIdentity *put_path;
3503 struct GNUNET_PeerIdentity current_best_known_dest;
3504 struct GNUNET_PeerIdentity best_known_dest;
3505 struct GNUNET_HashCode received_intermediate_trail_id;
3506 struct GNUNET_HashCode intermediate_trail_id;
3507 struct GNUNET_PeerIdentity next_hop;
3508 const struct GNUNET_PeerIdentity *next_routing_hop;
3509 enum GNUNET_DHT_RouteOption options;
3510 struct GNUNET_HashCode test_key;
3511 struct Closest_Peer successor;
3514 uint32_t putlen = ntohl (put->put_path_length);
3515 struct GNUNET_PeerIdentity pp[putlen + 1];
3517 size_t payload_size;
3520 msize = ntohs (put->header.size);
3521 GNUNET_STATISTICS_update (GDS_stats,
3522 gettext_noop ("# Bytes received from other peers"),
3526 current_best_known_dest = put->best_known_destination;
3527 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3528 payload = &put_path[putlen];
3529 options = ntohl (put->options);
3530 received_intermediate_trail_id = put->intermediate_trail_id;
3531 hop_count = ntohl(put->hop_count);
3532 payload_size = msize - (sizeof (struct PeerPutMessage) +
3533 putlen * sizeof (struct GNUNET_PeerIdentity));
3535 switch (GNUNET_BLOCK_get_key (GDS_block_context,
3536 ntohl (put->block_type),
3542 if (0 != memcmp (&test_key,
3544 sizeof (struct GNUNET_HashCode)))
3546 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3547 GNUNET_break_op (0);
3548 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3549 "PUT with key `%s' for block with key %s\n",
3551 GNUNET_h2s_full (&test_key));
3552 GNUNET_free (put_s);
3557 GNUNET_break_op (0);
3560 /* cannot verify, good luck */
3564 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3566 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3567 ntohl (put->block_type),
3568 GNUNET_BLOCK_EO_NONE,
3570 NULL, 0, /* bloom filer */
3571 NULL, 0, /* xquery */
3575 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3576 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3579 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3580 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3581 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3582 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3583 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3584 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3586 GNUNET_break_op (0);
3591 /* Check if you are already a part of put path. */
3593 for (i = 0; i < putlen; i++)
3595 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3603 /* Add yourself to the list. */
3604 //if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3609 putlen * sizeof (struct GNUNET_PeerIdentity));
3610 pp[putlen] = my_identity;
3617 GNUNET_memcpy (&key_value,
3620 key_value = GNUNET_ntohll (key_value);
3621 successor = find_local_best_known_next_hop (key_value,
3622 GDS_FINGER_TYPE_NON_PREDECESSOR);
3623 next_hop = successor.next_hop;
3624 intermediate_trail_id = successor.trail_id;
3625 best_known_dest = successor.best_known_destination;
3627 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest,
3630 next_routing_hop = GDS_ROUTING_get_next_hop (&received_intermediate_trail_id,
3631 GDS_ROUTING_SRC_TO_DEST);
3632 if (NULL != next_routing_hop)
3634 next_hop = *next_routing_hop;
3635 intermediate_trail_id = received_intermediate_trail_id;
3636 best_known_dest = current_best_known_dest;
3640 GDS_CLIENTS_process_put (options,
3641 ntohl (put->block_type),
3643 ntohl (put->desired_replication_level),
3646 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3651 /* I am the final destination */
3652 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3655 DEBUG ("\n PUT_REQUEST_SUCCESSFUL for key = %s",
3656 GNUNET_h2s(&put->key));
3657 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3661 ntohl (put->block_type),
3665 GDS_NEIGHBOURS_send_put (&put->key,
3666 ntohl (put->block_type),
3667 ntohl (put->options),
3668 ntohl (put->desired_replication_level),
3670 intermediate_trail_id,
3675 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3682 * Check integrity of @a get message.
3684 * @param cls closure
3685 * @param get the message
3686 * @return #GNUNET_OK if @a get is well-formed
3689 check_dht_p2p_get (void *cls,
3690 const struct PeerGetMessage *get)
3692 uint32_t get_length;
3695 msize = ntohs (get->header.size);
3696 get_length = ntohl (get->get_path_length);
3698 sizeof (struct PeerGetMessage) +
3699 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3701 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3703 GNUNET_break_op (0);
3704 return GNUNET_SYSERR;
3711 * FIXME: Check for loop in the request. If you already are part of get path,
3712 * then you need to reset the get path length.
3713 * Core handler for p2p get requests.
3715 * @param cls closure
3716 * @param get the message
3719 handle_dht_p2p_get (void *cls,
3720 const struct PeerGetMessage *get)
3722 const struct GNUNET_PeerIdentity *get_path;
3723 struct GNUNET_PeerIdentity best_known_dest;
3724 struct GNUNET_PeerIdentity current_best_known_dest;
3725 struct GNUNET_HashCode intermediate_trail_id;
3726 struct GNUNET_HashCode received_intermediate_trail_id;
3727 struct Closest_Peer successor;
3728 struct GNUNET_PeerIdentity next_hop;
3729 const struct GNUNET_PeerIdentity *next_routing_hop;
3730 uint32_t get_length;
3735 msize = ntohs (get->header.size);
3736 get_length = ntohl (get->get_path_length);
3737 current_best_known_dest = get->best_known_destination;
3738 received_intermediate_trail_id = get->intermediate_trail_id;
3739 get_path = (const struct GNUNET_PeerIdentity *) &get[1];
3740 hop_count = get->hop_count;
3742 GNUNET_STATISTICS_update (GDS_stats,
3743 gettext_noop ("# Bytes received from other peers"),
3746 GNUNET_memcpy (&key_value,
3749 key_value = GNUNET_ntohll (key_value);
3751 /* Check if you are already a part of get path. */
3752 for (unsigned int i = 0; i < get_length; i++)
3754 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3762 /* Add yourself in the get path. */
3763 struct GNUNET_PeerIdentity gp[get_length + 1];
3766 get_length * sizeof (struct GNUNET_PeerIdentity));
3767 gp[get_length] = my_identity;
3768 get_length = get_length + 1;
3769 GDS_CLIENTS_process_get (get->options,
3772 get->desired_replication_level,
3773 get->get_path_length,
3778 successor = find_local_best_known_next_hop (key_value,
3779 GDS_FINGER_TYPE_NON_PREDECESSOR);
3780 next_hop = successor.next_hop;
3781 best_known_dest = successor.best_known_destination;
3782 intermediate_trail_id = successor.trail_id;
3783 /* I am not the final destination. I am part of trail to reach final dest. */
3784 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3786 next_routing_hop = GDS_ROUTING_get_next_hop (&received_intermediate_trail_id,
3787 GDS_ROUTING_SRC_TO_DEST);
3788 if (NULL != next_routing_hop)
3790 next_hop = *next_routing_hop;
3791 best_known_dest = current_best_known_dest;
3792 intermediate_trail_id = received_intermediate_trail_id;
3796 /* I am the final destination. */
3797 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3800 if (1 == get_length)
3802 DEBUG ("\n GET_REQUEST DONE for key = %s",
3803 GNUNET_h2s(&get->key));
3804 GDS_DATACACHE_handle_get (&get->key,
3805 get->block_type, /* FIXME: endianess? */
3815 GDS_DATACACHE_handle_get (&get->key,
3816 get->block_type, /* FIXME: endianess? */
3822 &gp[get_length - 2]);
3827 GDS_NEIGHBOURS_send_get (&get->key,
3828 get->block_type, /* FIXME: endianess? */
3830 get->desired_replication_level,
3832 &intermediate_trail_id,
3842 * Check validity of @a get_result message.
3844 * @param cls closure
3845 * @param get_result the message
3846 * @return #GNUNET_OK if @a get_result is well-formed
3849 check_dht_p2p_get_result (void *cls,
3850 const struct PeerGetResultMessage *get_result)
3853 unsigned int getlen;
3854 unsigned int putlen;
3856 msize = ntohs (get_result->header.size);
3857 getlen = ntohl (get_result->get_path_length);
3858 putlen = ntohl (get_result->put_path_length);
3860 sizeof (struct PeerGetResultMessage) +
3861 getlen * sizeof (struct GNUNET_PeerIdentity) +
3862 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3864 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3866 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3868 GNUNET_break_op (0);
3869 return GNUNET_SYSERR;
3876 * Core handler for get result
3878 * @param cls closure
3879 * @param get_result the message
3882 handle_dht_p2p_get_result (void *cls,
3883 const struct PeerGetResultMessage *get_result)
3885 const struct GNUNET_PeerIdentity *get_path;
3886 const struct GNUNET_PeerIdentity *put_path;
3887 const void *payload;
3888 size_t payload_size;
3890 unsigned int getlen;
3891 unsigned int putlen;
3892 int current_path_index;
3894 msize = ntohs (get_result->header.size);
3895 getlen = ntohl (get_result->get_path_length);
3896 putlen = ntohl (get_result->put_path_length);
3897 DEBUG ("GET_RESULT FOR DATA_SIZE = %u\n",
3898 (unsigned int) msize);
3899 GNUNET_STATISTICS_update (GDS_stats,
3900 gettext_noop ("# Bytes received from other peers"),
3903 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3904 get_path = &put_path[putlen];
3905 payload = (const void *) &get_path[getlen];
3906 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3907 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3909 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3912 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
3923 current_path_index = search_my_index (get_path,
3925 if (-1 == current_path_index)
3927 DEBUG ("No entry found in get path.\n");
3931 if ((getlen + 1) == current_path_index)
3933 DEBUG("Present twice in get path. Not allowed. \n");
3937 GDS_NEIGHBOURS_send_get_result (&get_result->key,
3938 get_result->type, /* FIXME: endianess? */
3939 &get_path[current_path_index - 1],
3940 &get_result->querying_peer,
3945 GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
3952 * Find the next hop to pass trail setup message. First find the local best known
3953 * hop from your own identity, friends and finger. If you were part of trail,
3954 * then get the next hop from routing table. Compare next_hop from routing table
3955 * and local best known hop, and return the closest one to final_dest_finger_val
3956 * @param final_dest_finger_val 64 bit value of finger identity
3957 * @param intermediate_trail_id If you are part of trail to reach to some other
3958 * finger, then it is the trail id to reach to
3959 * that finger, else set to 0.
3960 * @param is_predecessor Are we looking for closest successor or predecessor.
3961 * @param source Source of trail setup message.
3962 * @param current_dest In case you are part of trail, then finger to which
3963 * we should forward the message. Else my own identity
3964 * @return Closest Peer for @a final_dest_finger_val
3966 static struct Closest_Peer
3967 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3968 const struct GNUNET_HashCode *intermediate_trail_id,
3969 unsigned int is_predecessor,
3970 const struct GNUNET_PeerIdentity *source,
3971 const struct GNUNET_PeerIdentity *current_dest)
3973 struct Closest_Peer peer;
3975 peer = find_local_best_known_next_hop (final_dest_finger_val,
3978 /* Am I just a part of a trail towards a finger (current_destination)? */
3979 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3981 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3984 const struct GNUNET_PeerIdentity *closest_peer;
3986 /* Select best successor among one found locally and current_destination
3987 * that we got from network.*/
3988 closest_peer = select_closest_peer (&peer.best_known_destination,
3990 final_dest_finger_val,
3993 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3994 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest,
3997 const struct GNUNET_PeerIdentity *next_hop;
3999 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4000 GDS_ROUTING_SRC_TO_DEST);
4001 /* next_hop NULL is a valid case. This intermediate trail id is set by
4002 some other finger, and while this trail setup is in progress, that other
4003 peer might have found a better trail ,and send trail teardown message
4004 across the network. In case we got the trail teardown message first,
4005 then next_hop will be NULL. A possible solution could be to keep track
4006 * of all removed trail id, and be sure that there is no other reason . */
4007 if(NULL != next_hop)
4009 peer.next_hop = *next_hop;
4010 peer.best_known_destination = *current_dest;
4011 peer.trail_id = *intermediate_trail_id;
4020 * Check format of a PeerTrailSetupMessage.
4022 * @param cls closure
4023 * @param trail_setup the message
4024 * @return #GNUNET_OK if @a trail_setup is well-formed
4027 check_dht_p2p_trail_setup (void *cls,
4028 const struct PeerTrailSetupMessage *trail_setup)
4032 msize = ntohs (trail_setup->header.size);
4033 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4034 sizeof (struct GNUNET_PeerIdentity) != 0)
4036 GNUNET_break_op (0);
4037 return GNUNET_SYSERR;
4044 * Core handle for PeerTrailSetupMessage.
4046 * @param cls closure
4047 * @param trail_setup the message
4050 handle_dht_p2p_trail_setup (void *cls,
4051 const struct PeerTrailSetupMessage *trail_setup)
4053 struct FriendInfo *friend = cls;
4054 const struct GNUNET_PeerIdentity *trail_peer_list;
4055 struct GNUNET_PeerIdentity current_dest;
4056 struct FriendInfo *target_friend;
4057 struct GNUNET_PeerIdentity source;
4058 struct GNUNET_HashCode intermediate_trail_id;
4059 struct GNUNET_HashCode trail_id;
4060 unsigned int is_predecessor;
4061 uint32_t trail_length;
4062 uint64_t final_dest_finger_val;
4066 msize = ntohs (trail_setup->header.size);
4067 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4068 sizeof (struct GNUNET_PeerIdentity);
4069 GNUNET_STATISTICS_update (GDS_stats,
4070 gettext_noop ("# Bytes received from other peers"),
4073 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_setup[1];
4074 current_dest = trail_setup->best_known_destination;
4075 trail_id = trail_setup->trail_id;
4076 final_dest_finger_val
4077 = GNUNET_ntohll (trail_setup->final_destination_finger_value);
4078 source = trail_setup->source_peer;
4079 is_predecessor = ntohl (trail_setup->is_predecessor);
4080 intermediate_trail_id = trail_setup->intermediate_trail_id;
4082 /* Did the friend insert its ID in the trail list? */
4083 if ( (trail_length > 0) &&
4084 (0 != memcmp (&trail_peer_list[trail_length-1],
4086 sizeof (struct GNUNET_PeerIdentity))) )
4088 GNUNET_break_op (0);
4092 /* If I was the source and got the message back, then set trail length to 0.*/
4093 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
4099 /* Check if you are present in the trail seen so far? */
4100 for (i = 0; i < trail_length; i++)
4102 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[i],
4105 /* We will add ourself later in code, if NOT destination. */
4111 /* Is my routing table full? */
4112 if (GNUNET_YES == GDS_ROUTING_threshold_reached ())
4115 = (trail_length > 0)
4116 ? GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4117 &trail_peer_list[trail_length - 1])
4118 : GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4120 if (NULL == target_friend)
4122 DEBUG ("\n friend not found");
4126 GDS_NEIGHBOURS_send_trail_rejection (&source,
4127 final_dest_finger_val,
4134 CONGESTION_TIMEOUT);
4138 /* Get the next hop to forward the trail setup request. */
4139 struct Closest_Peer next_peer
4140 = get_local_best_known_next_hop (final_dest_finger_val,
4141 &intermediate_trail_id,
4146 /* Am I the final destination? */
4147 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4150 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&source,
4153 finger_table_add (&my_identity,
4157 final_dest_finger_val,
4163 = (trail_length > 0)
4164 ? GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4165 &trail_peer_list[trail_length-1])
4166 : GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4168 if (NULL == target_friend)
4170 GNUNET_break_op (0);
4173 GDS_ROUTING_add (&trail_id,
4176 GDS_NEIGHBOURS_send_trail_setup_result (&source,
4182 final_dest_finger_val,
4186 /* I'm not the final destination. */
4187 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4188 &next_peer.next_hop);
4189 if (NULL == target_friend)
4191 DEBUG ("\n target friend not found for peer = %s",
4192 GNUNET_i2s(&next_peer.next_hop));
4196 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
4199 /* Add yourself to list of peers. */
4200 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4202 GNUNET_memcpy (peer_list,
4204 trail_length * sizeof (struct GNUNET_PeerIdentity));
4205 peer_list[trail_length] = my_identity;
4206 GDS_NEIGHBOURS_send_trail_setup (&source,
4207 final_dest_finger_val,
4208 &next_peer.best_known_destination,
4214 &next_peer.trail_id);
4217 GDS_NEIGHBOURS_send_trail_setup (&source,
4218 final_dest_finger_val,
4219 &next_peer.best_known_destination,
4225 &next_peer.trail_id);
4230 * Validate format of trail setup result messages.
4233 * @param trail_result the message
4234 * @return #GNUNET_OK if @a trail_result is well-formed
4237 check_dht_p2p_trail_setup_result (void *cls,
4238 const struct PeerTrailSetupResultMessage *trail_result)
4242 msize = ntohs (trail_result->header.size);
4243 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4244 sizeof (struct GNUNET_PeerIdentity) != 0)
4246 GNUNET_break_op (0);
4247 return GNUNET_SYSERR;
4254 * Core handle for p2p trail setup result messages.
4257 * @param trail_result the message
4260 handle_dht_p2p_trail_setup_result (void *cls,
4261 const struct PeerTrailSetupResultMessage *trail_result)
4263 struct FriendInfo *friend = cls;
4264 const struct GNUNET_PeerIdentity *trail_peer_list;
4265 struct GNUNET_PeerIdentity next_hop;
4266 struct FriendInfo *target_friend;
4267 struct GNUNET_PeerIdentity querying_peer;
4268 struct GNUNET_PeerIdentity finger_identity;
4269 uint32_t trail_length;
4270 uint64_t ultimate_destination_finger_value;
4271 uint32_t is_predecessor;
4272 struct GNUNET_HashCode trail_id;
4276 msize = ntohs (trail_result->header.size);
4277 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4278 sizeof (struct GNUNET_PeerIdentity);
4280 GNUNET_STATISTICS_update (GDS_stats,
4281 gettext_noop ("# Bytes received from other peers"),
4285 is_predecessor = ntohl (trail_result->is_predecessor);
4286 querying_peer = trail_result->querying_peer;
4287 finger_identity = trail_result->finger_identity;
4288 trail_id = trail_result->trail_id;
4289 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4290 ultimate_destination_finger_value
4291 = GNUNET_ntohll (trail_result->ultimate_destination_finger_value);
4293 /* Am I the one who initiated the query? */
4294 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer,
4297 /* Check that you got the message from the correct peer. */
4298 if (trail_length > 0)
4300 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4305 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4308 GDS_ROUTING_add (&trail_id,
4311 finger_table_add (&finger_identity,
4315 ultimate_destination_finger_value,
4320 /* Get my location in the trail. */
4321 my_index = search_my_index (trail_peer_list,
4325 DEBUG ("Not found in trail\n");
4330 if ((trail_length + 1) == my_index)
4332 DEBUG ("Found twice in trail.\n");
4337 //TODO; Refactor code here and above to check if sender peer is correct
4340 if (trail_length > 1)
4341 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4344 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4346 next_hop = trail_result->querying_peer;
4350 if (my_index == trail_length - 1)
4353 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4358 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4360 next_hop = trail_peer_list[my_index - 1];
4363 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4365 if (NULL == target_friend)
4367 GNUNET_break_op (0);
4370 GDS_ROUTING_add (&trail_id,
4373 GDS_NEIGHBOURS_send_trail_setup_result (&querying_peer,
4379 ultimate_destination_finger_value,
4387 * @param trail Trail to be inverted
4388 * @param trail_length Total number of peers in the trail.
4389 * @return Updated trail
4391 static struct GNUNET_PeerIdentity *
4392 invert_trail (const struct GNUNET_PeerIdentity *trail,
4393 unsigned int trail_length)
4397 struct GNUNET_PeerIdentity *inverted_trail;
4399 inverted_trail = GNUNET_new_array (trail_length,
4400 struct GNUNET_PeerIdentity);
4402 j = trail_length - 1;
4403 while (i < trail_length)
4405 inverted_trail[i] = trail[j];
4410 GNUNET_assert (NULL !=
4411 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4412 &inverted_trail[0]));
4413 return inverted_trail;
4418 * Return the shortest trail among all the trails to reach to finger from me.
4420 * @param finger Finger
4421 * @param shortest_trail_length[out] Trail length of shortest trail from me
4423 * @return Shortest trail.
4425 static struct GNUNET_PeerIdentity *
4426 get_shortest_trail (struct FingerInfo *finger,
4427 unsigned int *trail_length)
4429 struct Trail *trail;
4430 unsigned int flag = 0;
4431 unsigned int shortest_trail_index = 0;
4432 int shortest_trail_length = -1;
4433 struct Trail_Element *trail_element;
4434 struct GNUNET_PeerIdentity *trail_list;
4437 /* Get the shortest trail to reach to current successor. */
4438 for (i = 0; i < finger->trails_count; i++)
4440 trail = &finger->trail_list[i];
4444 shortest_trail_index = i;
4445 shortest_trail_length = trail->trail_length;
4450 if (shortest_trail_length > trail->trail_length)
4452 shortest_trail_index = i;
4453 shortest_trail_length = trail->trail_length;
4458 /* Copy the shortest trail and return. */
4459 trail = &finger->trail_list[shortest_trail_index];
4460 trail_element = trail->trail_head;
4462 trail_list = GNUNET_new_array (shortest_trail_length,
4463 struct GNUNET_PeerIdentity);
4465 for (i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4467 trail_list[i] = trail_element->peer;
4470 GNUNET_assert(shortest_trail_length != -1);
4472 *trail_length = shortest_trail_length;
4478 * Check if @a trail_1 and @a trail_2 have any common element. If yes then join
4479 * them at common element. @a trail_1 always preceeds @a trail_2 in joined trail.
4481 * @param trail_1 Trail from source to me, NOT including endpoints.
4482 * @param trail_1_len Total number of peers @a trail_1
4483 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4484 * @param trail_2_len Total number of peers @a trail_2
4485 * @param joined_trail_len Total number of peers in combined trail of @a trail_1
4487 * @return Joined trail.
4489 static struct GNUNET_PeerIdentity *
4490 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4491 unsigned int trail_1_len,
4492 const struct GNUNET_PeerIdentity *trail_2,
4493 unsigned int trail_2_len,
4494 unsigned int *joined_trail_len)
4496 struct GNUNET_PeerIdentity *joined_trail;
4501 for (i = 0; i < trail_1_len; i++)
4503 for (j = 0; j < trail_2_len; j++)
4505 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],
4509 *joined_trail_len = i + (trail_2_len - j);
4510 joined_trail = GNUNET_new_array (*joined_trail_len,
4511 struct GNUNET_PeerIdentity);
4514 /* Copy all the elements from 0 to i into joined_trail. */
4515 for(k = 0; k < ( i+1); k++)
4517 joined_trail[k] = trail_1[k];
4520 /* Increment j as entry stored is same as entry stored at i*/
4523 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4524 while(k <= (*joined_trail_len - 1))
4526 joined_trail[k] = trail_2[j];
4531 return joined_trail;
4535 /* Here you should join the trails. */
4536 *joined_trail_len = trail_1_len + trail_2_len + 1;
4537 joined_trail = GNUNET_new_array (*joined_trail_len,
4538 struct GNUNET_PeerIdentity);
4541 for(i = 0; i < trail_1_len;i++)
4543 joined_trail[i] = trail_1[i];
4546 joined_trail[i] = my_identity;
4549 for (j = 0; i < *joined_trail_len; i++,j++)
4551 joined_trail[i] = trail_2[j];
4554 return joined_trail;
4559 * Return the trail from source to my current predecessor. Check if source
4560 * is already part of the this trail, if yes then return the shorten trail.
4562 * @param current_trail Trail from source to me, NOT including the endpoints.
4563 * @param current_trail_length Number of peers in @a current_trail.
4564 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4565 * source to my predecessor, NOT including
4567 * @return Trail from source to my predecessor.
4569 static struct GNUNET_PeerIdentity *
4570 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4571 const struct GNUNET_PeerIdentity *trail_src_to_me,
4572 unsigned int trail_src_to_me_len,
4573 unsigned int *trail_src_to_curr_pred_length)
4575 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4576 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4577 unsigned int trail_me_to_curr_pred_length;
4578 struct FingerInfo *current_predecessor;
4583 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4585 /* Check if trail_src_to_me contains current_predecessor. */
4586 for (i = 0; i < trail_src_to_me_len; i++)
4588 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4589 ¤t_predecessor->finger_identity))
4593 *trail_src_to_curr_pred_length = i;
4598 trail_src_to_curr_pred = GNUNET_new_array (*trail_src_to_curr_pred_length,
4599 struct GNUNET_PeerIdentity);
4600 for (j = 0; j < i; j++)
4601 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4602 return trail_src_to_curr_pred;
4606 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4607 &trail_me_to_curr_pred_length);
4609 /* Check if trail contains the source_peer. */
4610 for (i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4612 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4613 &trail_me_to_curr_pred[i]))
4616 /* Source is NOT part of trail. */
4619 /* Source is the last element in the trail to reach to my pred.
4620 Source is direct friend of the pred. */
4621 if (trail_me_to_curr_pred_length == i)
4623 *trail_src_to_curr_pred_length = 0;
4624 GNUNET_free_non_null (trail_me_to_curr_pred);
4628 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4629 trail_src_to_curr_pred = GNUNET_new_array (*trail_src_to_curr_pred_length,
4630 struct GNUNET_PeerIdentity);
4633 for (j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4634 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4635 GNUNET_free_non_null (trail_me_to_curr_pred);
4636 return trail_src_to_curr_pred;
4639 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4640 trail_src_to_me_len,
4641 trail_me_to_curr_pred,
4642 trail_me_to_curr_pred_length,
4644 *trail_src_to_curr_pred_length = len;
4645 GNUNET_free_non_null(trail_me_to_curr_pred);
4646 return trail_src_to_curr_pred;
4651 * Add finger as your predecessor. To add, first generate a new trail id, invert
4652 * the trail to get the trail from me to finger, add an entry in your routing
4653 * table, send add trail message to peers which are part of trail from me to
4654 * finger and add finger in finger table.
4658 * @param trail_length
4661 update_predecessor (const struct GNUNET_PeerIdentity *finger,
4662 const struct GNUNET_PeerIdentity *trail,
4663 unsigned int trail_length)
4665 struct GNUNET_HashCode trail_to_new_predecessor_id;
4666 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4667 struct FriendInfo *target_friend;
4669 /* Generate trail id for trail from me to new predecessor = finger. */
4670 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4671 &trail_to_new_predecessor_id,
4672 sizeof (trail_to_new_predecessor_id));
4674 if (0 == trail_length)
4676 trail_to_new_predecessor = NULL;
4677 GDS_ROUTING_add (&trail_to_new_predecessor_id,
4680 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4682 if (NULL == target_friend)
4690 /* Invert the trail to get the trail from me to finger, NOT including the
4692 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4693 &trail[trail_length-1]));
4694 trail_to_new_predecessor = invert_trail (trail,
4697 /* Add an entry in your routing table. */
4698 GDS_ROUTING_add (&trail_to_new_predecessor_id,
4700 &trail_to_new_predecessor[0]);
4702 GNUNET_assert (NULL != (target_friend =
4703 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4704 &trail_to_new_predecessor[0])));
4707 /* Add entry in routing table of all peers that are part of trail from me
4708 to finger, including finger. */
4709 GDS_NEIGHBOURS_send_add_trail (&my_identity,
4711 &trail_to_new_predecessor_id,
4712 trail_to_new_predecessor,
4716 add_new_finger (finger,
4717 trail_to_new_predecessor,
4719 &trail_to_new_predecessor_id,
4720 PREDECESSOR_FINGER_ID);
4721 GNUNET_free_non_null (trail_to_new_predecessor);
4726 * Check if you already have a predecessor. If not then add finger as your
4727 * predecessor. If you have predecessor, then compare two peer identites.
4728 * If finger is correct predecessor, then remove the old entry, add finger in
4729 * finger table and send add_trail message to add the trail in the routing
4730 * table of all peers which are part of trail to reach from me to finger.
4731 * @param finger New peer which may be our predecessor.
4732 * @param trail List of peers to reach from @finger to me.
4733 * @param trail_length Total number of peer in @a trail.
4736 compare_and_update_predecessor (const struct GNUNET_PeerIdentity *finger,
4737 const struct GNUNET_PeerIdentity *trail,
4738 unsigned int trail_length)
4740 struct FingerInfo *current_predecessor;
4741 const struct GNUNET_PeerIdentity *closest_peer;
4742 uint64_t predecessor_value;
4743 unsigned int is_predecessor = 1;
4745 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4746 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (finger,
4749 /* No predecessor. Add finger as your predecessor. */
4750 if (GNUNET_NO == current_predecessor->is_present)
4752 update_predecessor (finger,
4758 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4764 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4765 closest_peer = select_closest_peer (finger,
4766 ¤t_predecessor->finger_identity,
4770 /* Finger is the closest predecessor. Remove the existing one and add the new
4772 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4775 remove_existing_finger (current_predecessor,
4776 PREDECESSOR_FINGER_ID);
4777 update_predecessor (finger,
4786 * Check format of a p2p verify successor messages.
4788 * @param cls closure
4789 * @param vsm the message
4790 * @return #GNUNET_OK if @a vsm is well-formed
4793 check_dht_p2p_verify_successor (void *cls,
4794 const struct PeerVerifySuccessorMessage *vsm)
4798 msize = ntohs (vsm->header.size);
4799 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4800 sizeof (struct GNUNET_PeerIdentity) != 0)
4802 GNUNET_break_op (0);
4803 return GNUNET_SYSERR;
4810 * Core handle for p2p verify successor messages.
4812 * @param cls closure
4813 * @param vsm the message
4816 handle_dht_p2p_verify_successor (void *cls,
4817 const struct PeerVerifySuccessorMessage *vsm)
4819 struct FriendInfo *friend = cls;
4820 struct GNUNET_HashCode trail_id;
4821 struct GNUNET_PeerIdentity successor;
4822 struct GNUNET_PeerIdentity source_peer;
4823 struct GNUNET_PeerIdentity *trail;
4824 const struct GNUNET_PeerIdentity *next_hop;
4825 struct FingerInfo current_predecessor;
4826 struct FriendInfo *target_friend;
4827 unsigned int trail_src_to_curr_pred_len = 0;
4828 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4829 unsigned int trail_length;
4832 msize = ntohs (vsm->header.size);
4833 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4834 sizeof (struct GNUNET_PeerIdentity);
4835 GNUNET_STATISTICS_update (GDS_stats,
4836 gettext_noop ("# Bytes received from other peers"),
4840 trail_id = vsm->trail_id;
4841 source_peer = vsm->source_peer;
4842 successor = vsm->successor;
4843 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4845 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4847 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor,
4850 next_hop = GDS_ROUTING_get_next_hop (&trail_id,
4851 GDS_ROUTING_SRC_TO_DEST);
4852 if (NULL == next_hop)
4855 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4857 if (NULL == target_friend)
4862 GDS_NEIGHBOURS_send_verify_successor_message (&source_peer,
4871 /* I am the destination of this message. */
4872 /* Check if the source_peer could be our predecessor and if yes then update
4874 compare_and_update_predecessor (&source_peer,
4877 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4879 /* Is source of this message NOT my predecessor. */
4880 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4883 trail_src_to_curr_pred
4884 = get_trail_src_to_curr_pred (source_peer,
4887 &trail_src_to_curr_pred_len);
4891 trail_src_to_curr_pred_len = trail_length;
4892 trail_src_to_curr_pred = GNUNET_new_array (trail_src_to_curr_pred_len,
4893 struct GNUNET_PeerIdentity);
4895 for (unsigned int i = 0; i < trail_src_to_curr_pred_len; i++)
4897 trail_src_to_curr_pred[i] = trail[i];
4901 GNUNET_assert (NULL !=
4903 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4905 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
4907 ¤t_predecessor.finger_identity,
4909 trail_src_to_curr_pred,
4910 trail_src_to_curr_pred_len,
4911 GDS_ROUTING_DEST_TO_SRC,
4913 GNUNET_free_non_null (trail_src_to_curr_pred);
4918 * If the trail from me to my probable successor contains a friend not
4919 * at index 0, then we can shorten the trail.
4921 * @param probable_successor Peer which is our probable successor
4922 * @param trail_me_to_probable_successor Peers in path from me to my probable
4923 * successor, NOT including the endpoints.
4924 * @param trail_me_to_probable_successor_len Total number of peers in
4925 * @a trail_me_to_probable_succesor.
4926 * @return Updated trail, if any friend found.
4927 * Else the trail_me_to_probable_successor.
4929 const struct GNUNET_PeerIdentity *
4930 check_trail_me_to_probable_succ (const struct GNUNET_PeerIdentity *probable_successor,
4931 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4932 unsigned int trail_me_to_probable_successor_len,
4933 unsigned int *trail_to_new_successor_length)
4937 struct GNUNET_PeerIdentity *trail_to_new_successor;
4939 /* Probable successor is a friend */
4940 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4941 probable_successor))
4943 trail_to_new_successor = NULL;
4944 *trail_to_new_successor_length = 0;
4945 return trail_to_new_successor;
4948 /* Is there any friend of yours in this trail. */
4949 if (trail_me_to_probable_successor_len > 1)
4951 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4953 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4954 &trail_me_to_probable_successor[i]))
4957 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4958 trail_to_new_successor = GNUNET_new_array (*trail_to_new_successor_length,
4959 struct GNUNET_PeerIdentity);
4960 for (j = 0; j < *trail_to_new_successor_length; i++,j++)
4962 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4965 return trail_to_new_successor;
4969 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4970 return trail_me_to_probable_successor;
4975 struct SendNotifyContext
4977 struct GNUNET_PeerIdentity source_peer;
4978 struct GNUNET_PeerIdentity successor;
4979 struct GNUNET_PeerIdentity *successor_trail;
4980 unsigned int successor_trail_length;
4981 struct GNUNET_HashCode succesor_trail_id;
4982 struct FriendInfo *target_friend;
4983 unsigned int num_retries_scheduled;
4988 send_notify_new_successor (void *cls);
4992 * Check if the peer which sent us verify successor result message is still ours
4993 * successor or not. If not, then compare existing successor and probable successor.
4994 * In case probable successor is the correct successor, remove the existing
4995 * successor. Add probable successor as new successor. Send notify new successor
4996 * message to new successor.
4997 * @param curr_succ Peer to which we sent the verify successor message. It may
4998 * or may not be our real current successor, as we may have few iterations of
4999 * find finger trail task.
5000 * @param probable_successor Peer which should be our successor accroding to @a
5002 * @param trail List of peers to reach from me to @a probable successor, NOT including
5004 * @param trail_length Total number of peers in @a trail.
5007 compare_and_update_successor (const struct GNUNET_PeerIdentity *curr_succ,
5008 const struct GNUNET_PeerIdentity *probable_successor,
5009 const struct GNUNET_PeerIdentity *trail,
5010 unsigned int trail_length)
5012 struct FingerInfo *current_successor;
5013 const struct GNUNET_PeerIdentity *closest_peer;
5014 struct GNUNET_HashCode trail_id;
5015 const struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
5016 struct FriendInfo *target_friend;
5017 unsigned int trail_me_to_probable_succ_len;
5018 unsigned int is_predecessor = 0;
5019 uint64_t successor_value;
5020 struct SendNotifyContext *notify_ctx;
5022 current_successor = &finger_table[0];
5023 successor_value = compute_finger_identity_value(0);
5025 /* If probable successor is same as current_successor, do nothing. */
5026 if(0 == GNUNET_CRYPTO_cmp_peer_identity (probable_successor,
5027 ¤t_successor->finger_identity))
5029 if ((NULL != GDS_stats))
5035 GNUNET_memcpy (&my_id, &my_identity, sizeof(uint64_t));
5036 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5037 GNUNET_memcpy (&succ,
5038 ¤t_successor->finger_identity,
5040 succ = GNUNET_ntohll(succ);
5041 GNUNET_asprintf (&key,
5044 GNUNET_free (my_id_str);
5046 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5049 if (send_verify_successor_task == NULL)
5050 send_verify_successor_task =
5051 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5052 &send_verify_successor_message,
5056 closest_peer = select_closest_peer (probable_successor,
5057 ¤t_successor->finger_identity,
5061 /* If the current_successor in the finger table is closest, then do nothing. */
5062 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
5063 ¤t_successor->finger_identity))
5065 //FIXME: Is this a good place to return the stats.
5066 if ((NULL != GDS_stats))
5072 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5073 GNUNET_memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5074 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5075 GNUNET_free (my_id_str);
5076 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5080 if(0 == successor_times)
5082 // successor_times = 3;
5083 verify_successor_next_send_time =
5084 GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time);
5090 if (send_verify_successor_task == NULL)
5091 send_verify_successor_task =
5092 GNUNET_SCHEDULER_add_delayed (verify_successor_next_send_time,
5093 &send_verify_successor_message,
5098 /* Probable successor is the closest peer.*/
5099 if(trail_length > 0)
5101 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5106 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5107 probable_successor));
5110 trail_me_to_probable_succ_len = 0;
5111 trail_me_to_probable_succ = check_trail_me_to_probable_succ (probable_successor,
5114 &trail_me_to_probable_succ_len);
5116 /* Remove the existing successor. */
5117 remove_existing_finger (current_successor, 0);
5118 /* Generate a new trail id to reach to your new successor. */
5119 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5123 if (trail_me_to_probable_succ_len > 0)
5125 GDS_ROUTING_add (&trail_id,
5127 &trail_me_to_probable_succ[0]);
5128 GNUNET_assert (NULL !=
5130 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5131 &trail_me_to_probable_succ[0])));
5135 GDS_ROUTING_add (&trail_id,
5137 probable_successor);
5138 GNUNET_assert (NULL !=
5140 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5141 probable_successor)));
5144 add_new_finger (probable_successor,
5145 trail_me_to_probable_succ,
5146 trail_me_to_probable_succ_len,
5150 notify_ctx = GNUNET_new (struct SendNotifyContext);
5152 notify_ctx->source_peer = my_identity;
5153 notify_ctx->successor = *probable_successor;
5154 notify_ctx->successor_trail = GNUNET_new_array (trail_me_to_probable_succ_len,
5155 struct GNUNET_PeerIdentity);
5156 GNUNET_memcpy (notify_ctx->successor_trail,
5157 trail_me_to_probable_succ,
5158 sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5159 notify_ctx->successor_trail_length = trail_me_to_probable_succ_len;
5160 notify_ctx->succesor_trail_id = trail_id;
5161 notify_ctx->target_friend = target_friend;
5162 notify_ctx->num_retries_scheduled = 0;
5164 // TODO: Check if we should verify before schedule if already scheduled.
5165 GNUNET_SCHEDULER_add_now (&send_notify_new_successor,
5171 send_notify_new_successor (void *cls)
5173 struct SendNotifyContext *ctx = cls;
5175 GDS_NEIGHBOURS_send_notify_new_successor (&ctx->source_peer,
5177 ctx->successor_trail,
5178 ctx->successor_trail_length,
5179 &ctx->succesor_trail_id,
5180 ctx->target_friend);
5182 if ( (0 == ctx->num_retries_scheduled) &&
5183 (send_notify_new_successor_retry_task != NULL) )
5185 // Result from previous notify successos hasn't arrived, so the retry task
5186 // hasn't been cancelled! Already a new notify successor must be called.
5187 // We will cancel the retry request.
5188 struct SendNotifyContext *old_notify_ctx;
5190 old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5191 GNUNET_free (old_notify_ctx->successor_trail);
5192 GNUNET_free (old_notify_ctx);
5193 send_notify_new_successor_retry_task = NULL;
5196 ctx->num_retries_scheduled++;
5197 send_notify_new_successor_retry_task
5198 = GNUNET_SCHEDULER_add_delayed (notify_successor_retry_time,
5199 &send_notify_new_successor,
5205 * Check integrity of verify successor result messages.
5207 * @param cls closure
5208 * @param vsrm the message
5209 * @return #GNUNET_OK if @a vrsm is well-formed
5212 check_dht_p2p_verify_successor_result (void *cls,
5213 const struct PeerVerifySuccessorResultMessage *vsrm)
5217 msize = ntohs (vsrm->header.size);
5218 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5219 sizeof (struct GNUNET_PeerIdentity) != 0)
5221 GNUNET_break_op (0);
5222 return GNUNET_SYSERR;
5229 * Core handle for p2p verify successor result messages.
5231 * @param cls closure
5232 * @param vsrm the message
5235 handle_dht_p2p_verify_successor_result (void *cls,
5236 const struct PeerVerifySuccessorResultMessage *vsrm)
5238 enum GDS_ROUTING_trail_direction trail_direction;
5239 struct GNUNET_PeerIdentity querying_peer;
5240 struct GNUNET_HashCode trail_id;
5241 const struct GNUNET_PeerIdentity *next_hop;
5242 struct FriendInfo *target_friend;
5243 struct GNUNET_PeerIdentity probable_successor;
5244 struct GNUNET_PeerIdentity current_successor;
5245 const struct GNUNET_PeerIdentity *trail;
5246 unsigned int trail_length;
5249 msize = ntohs (vsrm->header.size);
5250 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))
5251 / sizeof (struct GNUNET_PeerIdentity);
5253 GNUNET_STATISTICS_update (GDS_stats,
5254 gettext_noop ("# Bytes received from other peers"),
5258 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5259 querying_peer = vsrm->querying_peer;
5260 trail_direction = ntohl (vsrm->trail_direction);
5261 trail_id = vsrm->trail_id;
5262 probable_successor = vsrm->probable_successor;
5263 current_successor = vsrm->current_successor;
5265 /* Am I the querying_peer? */
5266 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer,
5269 /* Cancel Retry Task */
5270 if (NULL != send_verify_successor_retry_task)
5272 struct VerifySuccessorContext *ctx;
5274 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
5276 send_verify_successor_retry_task = NULL;
5278 compare_and_update_successor (¤t_successor,
5279 &probable_successor,
5285 /*If you are not the querying peer then pass on the message */
5286 if(NULL == (next_hop =
5287 GDS_ROUTING_get_next_hop (&trail_id,
5290 /* Here it may happen that source peer has found a new successor, and removed
5291 the trail, Hence no entry found in the routing table. Fail silently.*/
5292 DEBUG (" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
5293 GNUNET_i2s (&my_identity),
5294 GNUNET_h2s (&trail_id),
5299 if (NULL == (target_friend =
5300 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5305 GDS_NEIGHBOURS_send_verify_successor_result (&querying_peer,
5306 &vsrm->current_successor,
5307 &probable_successor,
5317 * Check integrity of p2p notify new successor messages.
5319 * @param cls closure
5320 * @param nsm the message
5321 * @return #GNUNET_OK if @a nsm is well-formed
5324 check_dht_p2p_notify_new_successor (void *cls,
5325 const struct PeerNotifyNewSuccessorMessage *nsm)
5329 msize = ntohs (nsm->header.size);
5330 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5331 sizeof (struct GNUNET_PeerIdentity) != 0)
5333 GNUNET_break_op (0);
5334 return GNUNET_SYSERR;
5341 * Core handle for p2p notify new successor messages.
5343 * @param cls closure
5344 * @param nsm the message
5347 handle_dht_p2p_notify_new_successor (void *cls,
5348 const struct PeerNotifyNewSuccessorMessage *nsm)
5350 struct FriendInfo *friend = cls;
5351 const struct GNUNET_PeerIdentity *trail;
5352 struct GNUNET_PeerIdentity source;
5353 struct GNUNET_PeerIdentity new_successor;
5354 struct GNUNET_HashCode trail_id;
5355 struct GNUNET_PeerIdentity next_hop;
5356 struct FriendInfo *target_friend;
5359 uint32_t trail_length;
5361 msize = ntohs (nsm->header.size);
5362 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5363 sizeof (struct GNUNET_PeerIdentity);
5364 GNUNET_STATISTICS_update (GDS_stats,
5365 gettext_noop ("# Bytes received from other peers"),
5368 trail = (const struct GNUNET_PeerIdentity *) &nsm[1];
5369 source = nsm->source_peer;
5370 new_successor = nsm->new_successor;
5371 trail_id = nsm->trail_id;
5373 /* I am the new_successor to source_peer. */
5374 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
5377 if (trail_length > 0)
5378 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail[trail_length - 1],
5381 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&source,
5384 compare_and_update_predecessor (&source,
5387 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5389 GNUNET_assert (NULL != target_friend);
5390 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (&trail_id,
5391 GDS_ROUTING_DEST_TO_SRC,
5396 GNUNET_assert(trail_length > 0);
5397 /* I am part of trail to reach to successor. */
5398 my_index = search_my_index (trail, trail_length);
5401 DEBUG ("No entry found in trail\n");
5402 GNUNET_break_op (0);
5405 if((trail_length + 1) == my_index)
5407 DEBUG ("Found twice in trail.\n");
5408 GNUNET_break_op (0);
5411 if ((trail_length-1) == my_index)
5412 next_hop = new_successor;
5414 next_hop = trail[my_index + 1];
5416 GDS_ROUTING_add (&trail_id,
5419 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5421 if (NULL == target_friend)
5426 GDS_NEIGHBOURS_send_notify_new_successor (&source,
5436 * Core handler for P2P notify successor message
5438 * @param cls closure
5439 * @param notify_confirmation the message
5442 handle_dht_p2p_notify_succ_confirmation (void *cls,
5443 const struct PeerNotifyConfirmationMessage *notify_confirmation)
5445 enum GDS_ROUTING_trail_direction trail_direction;
5446 struct GNUNET_HashCode trail_id;
5447 struct FriendInfo *target_friend;
5448 const struct GNUNET_PeerIdentity *next_hop;
5450 GNUNET_STATISTICS_update (GDS_stats,
5451 gettext_noop ("# Bytes received from other peers"),
5452 ntohs (notify_confirmation->header.size),
5454 trail_direction = ntohl (notify_confirmation->trail_direction);
5455 trail_id = notify_confirmation->trail_id;
5457 next_hop = GDS_ROUTING_get_next_hop (&trail_id,
5459 if (NULL == next_hop)
5461 /* The source of notify new successor, might have found even a better
5462 successor. In that case it send a trail teardown message, and hence,
5463 the next hop is NULL. */
5464 //Fixme: Add some print to confirm the above theory.
5468 /* I peer which sent the notify successor message to the successor. */
5469 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5473 * Schedule another round of verify sucessor with your current successor
5474 * which may or may not be source of this message. This message is used
5475 * only to ensure that we have a path setup to reach to our successor.
5478 // TODO: cancel schedule of notify_successor_retry_task
5479 if (send_notify_new_successor_retry_task != NULL)
5481 struct SendNotifyContext *notify_ctx;
5482 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5483 GNUNET_free (notify_ctx->successor_trail);
5484 GNUNET_free (notify_ctx);
5485 send_notify_new_successor_retry_task = NULL;
5487 if (send_verify_successor_task == NULL)
5489 verify_successor_next_send_time.rel_value_us =
5490 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5491 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5492 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5493 send_verify_successor_task
5494 = GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5495 &send_verify_successor_message,
5501 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5503 if (NULL == target_friend)
5505 DEBUG ("\n friend not found, line number = %d",
5509 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (&trail_id,
5510 GDS_ROUTING_DEST_TO_SRC,
5517 * Check integrity of P2P trail rejection message
5519 * @param cls closure
5520 * @param trail_rejection the message
5521 * @return #GNUNET_OK if @a trail_rejection is well-formed
5524 check_dht_p2p_trail_setup_rejection (void *cls,
5525 const struct PeerTrailRejectionMessage *trail_rejection)
5529 msize = ntohs (trail_rejection->header.size);
5530 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5531 sizeof (struct GNUNET_PeerIdentity) != 0)
5533 GNUNET_break_op (0);
5534 return GNUNET_SYSERR;
5541 * Core handler for P2P trail rejection message
5543 * @param cls closure
5544 * @param trail_rejection the message
5547 handle_dht_p2p_trail_setup_rejection (void *cls,
5548 const struct PeerTrailRejectionMessage *trail_rejection)
5550 struct FriendInfo *friend = cls;
5551 unsigned int trail_length;
5552 const struct GNUNET_PeerIdentity *trail_peer_list;
5553 struct FriendInfo *target_friend;
5554 struct GNUNET_TIME_Relative congestion_timeout;
5555 struct GNUNET_HashCode trail_id;
5556 struct GNUNET_PeerIdentity next_peer;
5557 struct GNUNET_PeerIdentity source;
5558 uint64_t ultimate_destination_finger_value;
5559 unsigned int is_predecessor;
5560 struct Closest_Peer successor;
5563 msize = ntohs (trail_rejection->header.size);
5564 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5565 sizeof (struct GNUNET_PeerIdentity);
5566 GNUNET_STATISTICS_update (GDS_stats,
5567 gettext_noop ("# Bytes received from other peers"),
5571 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_rejection[1];
5572 is_predecessor = ntohl (trail_rejection->is_predecessor);
5573 congestion_timeout = trail_rejection->congestion_time;
5574 source = trail_rejection->source_peer;
5575 trail_id = trail_rejection->trail_id;
5576 ultimate_destination_finger_value
5577 = GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5578 /* First set the congestion time of the friend that sent you this message. */
5579 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5581 if (NULL == target_friend)
5583 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5587 target_friend->congestion_timestamp
5588 = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5589 congestion_timeout);
5591 /* I am the source peer which wants to setup the trail. Do nothing.
5592 * send_find_finger_trail_task is scheduled periodically.*/
5593 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5596 /* If I am congested then pass this message to peer before me in trail. */
5597 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
5599 /* First remove yourself from the trail. */
5600 unsigned int new_trail_length = trail_length - 1;
5601 struct GNUNET_PeerIdentity trail[new_trail_length];
5603 GNUNET_memcpy (trail,
5605 new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5606 if (0 == trail_length)
5609 next_peer = trail[new_trail_length-1];
5612 = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5614 if (NULL == target_friend)
5616 DEBUG ("\nLINE = %d ,No friend found.",
5621 GDS_NEIGHBOURS_send_trail_rejection (&source,
5622 ultimate_destination_finger_value,
5629 CONGESTION_TIMEOUT);
5633 successor = find_local_best_known_next_hop (ultimate_destination_finger_value,
5636 /* Am I the final destination? */
5637 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5640 /*Here you are already part of trail. Copy the trail removing yourself. */
5641 unsigned int new_trail_length = trail_length - 1;
5642 struct GNUNET_PeerIdentity trail[new_trail_length];
5644 GNUNET_memcpy (trail,
5646 new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5648 if (0 == new_trail_length)
5652 next_peer = trail[new_trail_length-1];
5654 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5657 if (NULL == target_friend)
5659 DEBUG ("\nLINE = %d ,No friend found.",
5664 GDS_NEIGHBOURS_send_trail_setup_result (&source,
5670 ultimate_destination_finger_value,
5674 /* Here I was already part of trail. So no need to add. */
5675 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5676 &successor.next_hop);
5677 if (NULL == target_friend)
5679 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5683 GDS_NEIGHBOURS_send_trail_setup (&source,
5684 ultimate_destination_finger_value,
5685 &successor.best_known_destination,
5691 &successor.trail_id);
5696 * Core handler for trail teardown message.
5698 * @param cls closure
5699 * @param trail_teardown the message
5702 handle_dht_p2p_trail_teardown (void *cls,
5703 const struct PeerTrailTearDownMessage *trail_teardown)
5705 enum GDS_ROUTING_trail_direction trail_direction;
5706 struct GNUNET_HashCode trail_id;
5707 const struct GNUNET_PeerIdentity *next_hop;
5710 msize = ntohs (trail_teardown->header.size);
5711 GNUNET_STATISTICS_update (GDS_stats,
5712 gettext_noop ("# Bytes received from other peers"),
5715 trail_direction = ntohl (trail_teardown->trail_direction);
5716 trail_id = trail_teardown->trail_id;
5718 /* Check if peer is the real peer from which we should get this message.*/
5719 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5721 GNUNET_assert (NULL != (prev_hop =
5722 GDS_ROUTING_get_next_hop (trail_id, ! trail_direction)));
5723 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop,
5731 next_hop = GDS_ROUTING_get_next_hop (&trail_id,
5733 if (NULL == next_hop)
5735 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
5736 GNUNET_i2s (&my_identity),
5737 GNUNET_h2s (&trail_id),
5743 /* I am the next hop, which means I am the final destination. */
5744 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5746 GNUNET_assert (GNUNET_YES ==
5747 GDS_ROUTING_remove_trail (&trail_id));
5750 /* If not final destination, then send a trail teardown message to next hop.*/
5751 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5753 GNUNET_assert (GNUNET_YES ==
5754 GDS_ROUTING_remove_trail (&trail_id));
5755 GDS_NEIGHBOURS_send_trail_teardown (&trail_id,
5762 * Check validity of p2p add trail message.
5764 * @param cls closure
5765 * @param add_trail the message
5766 * @return #GNUNET_OK if @a add_trail is well-formed
5769 check_dht_p2p_add_trail (void *cls,
5770 const struct PeerAddTrailMessage *add_trail)
5774 msize = ntohs (add_trail->header.size);
5775 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5776 sizeof (struct GNUNET_PeerIdentity) != 0)
5778 GNUNET_break_op (0);
5779 return GNUNET_SYSERR;
5786 * Core handle for p2p add trail message.
5788 * @param cls closure
5789 * @param add_trail the message
5792 handle_dht_p2p_add_trail (void *cls,
5793 const struct PeerAddTrailMessage *add_trail)
5795 struct FriendInfo *friend = cls;
5796 const struct GNUNET_PeerIdentity *trail;
5797 struct GNUNET_HashCode trail_id;
5798 struct GNUNET_PeerIdentity destination_peer;
5799 struct GNUNET_PeerIdentity source_peer;
5800 struct GNUNET_PeerIdentity next_hop;
5801 unsigned int trail_length;
5802 unsigned int my_index;
5805 msize = ntohs (add_trail->header.size);
5806 /* In this message we pass the whole trail from source to destination as we
5807 * are adding that trail.*/
5808 //FIXME: failed when run with 1000 pears. check why.
5809 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5810 sizeof (struct GNUNET_PeerIdentity);
5811 GNUNET_STATISTICS_update (GDS_stats,
5812 gettext_noop ("# Bytes received from other peers"),
5816 trail = (const struct GNUNET_PeerIdentity *) &add_trail[1];
5817 destination_peer = add_trail->destination_peer;
5818 source_peer = add_trail->source_peer;
5819 trail_id = add_trail->trail_id;
5821 /* I am not the destination of the trail. */
5822 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
5825 struct FriendInfo *target_friend;
5827 /* Get my location in the trail. */
5828 my_index = search_my_index (trail, trail_length);
5831 GNUNET_break_op (0);
5834 if((trail_length + 1) == my_index)
5836 DEBUG ("Found twice in trail.\n");
5837 GNUNET_break_op (0);
5840 if ((trail_length - 1) == my_index)
5842 next_hop = destination_peer;
5846 next_hop = trail[my_index + 1];
5848 /* Add in your routing table. */
5849 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (&trail_id,
5852 //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5853 GNUNET_assert (NULL !=
5855 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5857 GDS_NEIGHBOURS_send_add_trail (&source_peer,
5865 /* I am the destination. Add an entry in routing table. */
5866 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (&trail_id,
5873 * Free the finger trail in which the first friend to reach to a finger is
5874 * disconnected_friend. Also remove entry from routing table for that particular
5876 * @param disconnected_friend PeerIdentity of friend which got disconnected
5877 * @param remove_finger Finger whose trail we need to check if it has
5878 * disconnected_friend as the first hop.
5879 * @return Total number of trails in which disconnected_friend was the first
5883 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5884 struct FingerInfo *finger)
5886 const struct GNUNET_PeerIdentity *next_hop;
5887 struct FriendInfo *remove_friend;
5888 struct Trail *current_trail;
5889 unsigned int matching_trails_count = 0;
5892 /* Iterate over all the trails of finger. */
5893 for (i = 0; i < finger->trails_count; i++)
5895 current_trail = &finger->trail_list[i];
5896 if (GNUNET_NO == current_trail->is_present)
5899 /* First friend to reach to finger is disconnected_peer. */
5900 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5901 disconnected_friend))
5904 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5905 disconnected_friend);
5906 GNUNET_assert (NULL != remove_friend);
5907 next_hop = GDS_ROUTING_get_next_hop (¤t_trail->trail_id,
5908 GDS_ROUTING_SRC_TO_DEST);
5910 /* Here it may happen that as all the peers got disconnected, the entry in
5911 routing table for that particular trail has been removed, because the
5912 previously disconnected peer was either a next hop or prev hop of that
5914 if (NULL != next_hop)
5916 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5918 GNUNET_assert (GNUNET_YES ==
5919 GDS_ROUTING_remove_trail (¤t_trail->trail_id));
5921 matching_trails_count++;
5922 free_trail (current_trail);
5923 current_trail->is_present = GNUNET_NO;
5926 return matching_trails_count;
5931 * Iterate over finger_table entries.
5932 * 0. Ignore finger which is my_identity or if no valid entry present at
5933 * that finger index.
5934 * 1. If disconnected_friend is a finger, then remove the routing entry from
5935 your own table. Free the trail.
5936 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5937 * 2.1 Remove all the trails and entry from routing table in which disconnected
5938 * friend is the first friend in the trail. If disconnected_friend is the
5939 * first friend in all the trails to reach finger, then remove the finger.
5940 * @param disconnected_friend Peer identity of friend which got disconnected.
5943 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5945 struct FingerInfo *current_finger;
5946 int removed_trails_count;
5949 /* Iterate over finger table entries. */
5950 for (i = 0; i < MAX_FINGERS; i++)
5952 current_finger = &finger_table[i];
5954 /* No finger stored at this trail index or I am the finger. */
5955 if ((GNUNET_NO == current_finger->is_present) ||
5956 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5960 /* Is disconnected_peer a finger? */
5961 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5962 ¤t_finger->finger_identity))
5964 remove_existing_finger (current_finger, i);
5967 /* If finger is a friend but not disconnected_friend, then continue. */
5968 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5969 ¤t_finger->finger_identity))
5972 /* Iterate over the list of trails to reach remove_finger. Check if
5973 * disconnected_friend is the first friend in any of the trail. */
5974 removed_trails_count = remove_matching_trails (disconnected_peer,
5976 current_finger->trails_count =
5977 current_finger->trails_count - removed_trails_count;
5978 if (0 == current_finger->trails_count)
5980 current_finger->is_present = GNUNET_NO;
5981 memset (&finger_table[i],
5983 sizeof (finger_table[i]));
5990 * Method called whenever a peer disconnects.
5992 * @param cls closure
5993 * @param peer peer identity this notification is about
5994 * @param internal_cls our `struct FriendInfo` for @a peer
5997 handle_core_disconnect (void *cls,
5998 const struct GNUNET_PeerIdentity *peer,
6001 struct FriendInfo *remove_friend = internal_cls;
6003 /* If disconnected to own identity, then return. */
6004 if (NULL == remove_friend)
6006 remove_matching_fingers (peer);
6007 GNUNET_assert (GNUNET_SYSERR !=
6008 GDS_ROUTING_remove_trail_by_peer (peer));
6009 GNUNET_assert (GNUNET_YES ==
6010 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
6013 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
6016 if (NULL != find_finger_trail_task)
6018 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6019 find_finger_trail_task = NULL;
6027 * Method called whenever a peer connects.
6029 * @param cls closure
6030 * @param peer_identity peer identity this notification is about
6031 * @param mq message queue for sending data to @a peer
6032 * @return our `struct FriendInfo` for this peer
6035 handle_core_connect (void *cls,
6036 const struct GNUNET_PeerIdentity *peer_identity,
6037 struct GNUNET_MQ_Handle *mq)
6039 struct FriendInfo *friend;
6041 /* Check for connect to self message */
6042 if (0 == memcmp (&my_identity,
6044 sizeof (struct GNUNET_PeerIdentity)))
6046 friend = GNUNET_new (struct FriendInfo);
6047 friend->id = peer_identity;
6049 GNUNET_assert (GNUNET_OK ==
6050 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
6053 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
6055 /* FIXME: now we are not making a distinction between fingers which are friends
6056 * also.But later, we should add a congestion timestamp on the friend, so that it is
6057 * selected after some time out. This is to ensure that both peers have added
6058 * each other as their friend. */
6059 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
6060 if (NULL == find_finger_trail_task)
6062 find_finger_trail_task
6063 = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message,
6071 * To be called on core init/fail.
6073 * @param cls service closure
6074 * @param identity the public identity of this peer
6077 core_init (void *cls,
6078 const struct GNUNET_PeerIdentity *identity)
6080 my_identity = *identity;
6085 * Initialize finger table entries.
6088 finger_table_init ()
6090 memset (&finger_table, 0, sizeof (finger_table));
6095 * Initialize neighbours subsystem.
6096 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
6099 GDS_NEIGHBOURS_init (void)
6101 struct GNUNET_MQ_MessageHandler core_handlers[] = {
6102 GNUNET_MQ_hd_var_size (dht_p2p_put,
6103 GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT,
6104 struct PeerPutMessage,
6106 GNUNET_MQ_hd_var_size (dht_p2p_get,
6107 GNUNET_MESSAGE_TYPE_XDHT_P2P_GET,
6108 struct PeerGetMessage,
6110 GNUNET_MQ_hd_var_size (dht_p2p_get_result,
6111 GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT,
6112 struct PeerGetResultMessage,
6114 GNUNET_MQ_hd_var_size (dht_p2p_trail_setup,
6115 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP,
6116 struct PeerTrailSetupMessage,
6118 GNUNET_MQ_hd_var_size (dht_p2p_trail_setup_result,
6119 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT,
6120 struct PeerTrailSetupResultMessage,
6122 GNUNET_MQ_hd_var_size (dht_p2p_verify_successor,
6123 GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR,
6124 struct PeerVerifySuccessorMessage,
6126 GNUNET_MQ_hd_var_size (dht_p2p_verify_successor_result,
6127 GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT,
6128 struct PeerVerifySuccessorResultMessage,
6130 GNUNET_MQ_hd_var_size (dht_p2p_notify_new_successor,
6131 GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR,
6132 struct PeerNotifyNewSuccessorMessage,
6134 GNUNET_MQ_hd_var_size (dht_p2p_trail_setup_rejection,
6135 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION,
6136 struct PeerTrailRejectionMessage,
6138 GNUNET_MQ_hd_fixed_size (dht_p2p_trail_teardown,
6139 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
6140 struct PeerTrailTearDownMessage,
6142 GNUNET_MQ_hd_var_size (dht_p2p_add_trail,
6143 GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL,
6144 struct PeerAddTrailMessage,
6146 GNUNET_MQ_hd_fixed_size (dht_p2p_notify_succ_confirmation,
6147 GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION,
6148 struct PeerNotifyConfirmationMessage,
6150 GNUNET_MQ_handler_end ()
6153 core_api = GNUNET_CORE_connect (GDS_cfg,
6156 &handle_core_connect,
6157 &handle_core_disconnect,
6159 if (NULL == core_api)
6160 return GNUNET_SYSERR;
6161 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256,
6163 finger_table_init ();
6164 successor_times = 10;
6165 fingers_round_count = 5;
6166 find_finger_trail_task_next_send_time.rel_value_us =
6167 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
6168 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6169 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
6171 verify_successor_next_send_time.rel_value_us =
6172 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
6173 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6174 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
6176 verify_successor_retry_time.rel_value_us =
6177 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6178 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6179 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6181 notify_successor_retry_time.rel_value_us =
6182 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6183 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6184 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6191 * Free the memory held up by trails of a finger.
6194 delete_finger_table_entries()
6196 for (unsigned int i = 0; i < MAX_FINGERS; i++)
6198 if (GNUNET_YES != finger_table[i].is_present)
6200 for (unsigned int j = 0; j < finger_table[i].trails_count; j++)
6201 free_trail(&finger_table[i].trail_list[j]);
6207 * Shutdown neighbours subsystem.
6210 GDS_NEIGHBOURS_done (void)
6212 if (NULL == core_api)
6215 GNUNET_CORE_disconnect (core_api);
6218 delete_finger_table_entries();
6219 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6220 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6221 friend_peermap = NULL;
6223 if (NULL != find_finger_trail_task)
6225 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6226 find_finger_trail_task = NULL;
6229 if (NULL != send_verify_successor_task)
6231 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6232 send_verify_successor_task = NULL;
6234 if (NULL != send_verify_successor_retry_task)
6236 struct VerifySuccessorContext *ctx;
6238 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
6240 send_verify_successor_retry_task = NULL;
6242 if (NULL != send_notify_new_successor_retry_task)
6244 struct SendNotifyContext *notify_ctx;
6246 notify_ctx = GNUNET_SCHEDULER_cancel (send_notify_new_successor_retry_task);
6247 GNUNET_free (notify_ctx->successor_trail);
6248 GNUNET_free (notify_ctx);
6249 send_notify_new_successor_retry_task = NULL;
6257 * @return my identity
6259 struct GNUNET_PeerIdentity *
6260 GDS_NEIGHBOURS_get_id (void)
6262 return &my_identity;
6265 /* end of gnunet-service-xdht_neighbours.c */