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-xdht.h"
41 #include "gnunet-service-xdht_clients.h"
42 #include "gnunet-service-xdht_datacache.h"
43 #include "gnunet-service-xdht_neighbours.h"
44 #include "gnunet-service-xdht_routing.h"
49 * 1. In X-Vine paper, there is no policy defined for replicating the data to
50 * recover in case of peer failure. We can do it in Chord way. In R5N, the key
51 * is hashed and then data is stored according to the key value generated after
56 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
59 * Maximum possible fingers (including predecessor) of a peer
61 #define MAX_FINGERS 65
64 * Maximum allowed number of pending messages per friend peer.
66 #define MAXIMUM_PENDING_PER_FRIEND 64
69 * How long to wait before sending another find finger trail request
71 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
74 * How long to wait before sending another verify successor message.
76 #define DHT_SEND_VERIFY_SUCCESSOR_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
79 * How long to wait before sending another verify successor message.
81 #define DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
84 * How long to wait before retrying notify successor.
86 #define DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
89 * How long at most to wait for transmission of a request to a friend ?
91 #define PENDING_MESSAGE_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
94 * Duration for which I may remain congested.
95 * Note: Its a static value. In future, a peer may do some analysis and calculate
96 * congestion_timeout based on 'some' parameters.
98 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
101 * In case we don't hear back from the current successor, then we can start
104 #define WAIT_NOTIFY_CONFIRMATION GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 200)
107 * Maximum number of trails allowed to go through a friend.
109 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
112 * Maximum number of trails stored per finger.
114 #define MAXIMUM_TRAILS_PER_FINGER 4
117 * Finger map index for predecessor entry in finger table.
119 #define PREDECESSOR_FINGER_ID 64
122 * FIXME: Its use only at 3 places check if you can remove it.
123 * To check if a finger is predecessor or not.
125 enum GDS_NEIGHBOURS_finger_type
127 GDS_FINGER_TYPE_PREDECESSOR = 1,
128 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
131 GNUNET_NETWORK_STRUCT_BEGIN
136 struct PeerPutMessage
139 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
141 struct GNUNET_MessageHeader header;
146 uint32_t options GNUNET_PACKED;
151 uint32_t block_type GNUNET_PACKED;
156 uint32_t hop_count GNUNET_PACKED;
159 * Replication level for this message
160 * In the current implementation, this value is not used.
162 uint32_t desired_replication_level GNUNET_PACKED;
165 * Length of the PUT path that follows (if tracked).
167 uint32_t put_path_length GNUNET_PACKED;
170 * Best known destination (could be my friend or finger) which should
171 * get this message next.
173 struct GNUNET_PeerIdentity best_known_destination;
176 * In case best_known_destination is a finger, then trail to reach
177 * to that finger. Else its default value is 0.
179 struct GNUNET_HashCode intermediate_trail_id;
182 * When does the content expire?
184 struct GNUNET_TIME_AbsoluteNBO expiration_time;
187 * The key to store the value under.
189 struct GNUNET_HashCode key GNUNET_PACKED;
191 /* put path (if tracked) */
200 struct PeerGetMessage
203 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
205 struct GNUNET_MessageHeader header;
210 uint32_t options GNUNET_PACKED;
213 * Desired content type.
215 uint32_t block_type GNUNET_PACKED;
220 uint32_t hop_count GNUNET_PACKED;
223 * Desired replication level for this request.
224 * In the current implementation, this value is not used.
226 uint32_t desired_replication_level GNUNET_PACKED;
229 * Total number of peers in get path.
231 unsigned int get_path_length;
234 * Best known destination (could be my friend or finger) which should
235 * get this message next.
237 struct GNUNET_PeerIdentity best_known_destination;
240 * In case best_known_destination is a finger, then trail to reach
241 * to that finger. Else its default value is 0.
243 struct GNUNET_HashCode intermediate_trail_id;
246 * The key we are looking for.
248 struct GNUNET_HashCode key;
251 /* struct GNUNET_PeerIdentity[]*/
257 struct PeerGetResultMessage
260 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
262 struct GNUNET_MessageHeader header;
265 * The type for the data.
267 uint32_t type GNUNET_PACKED;
270 * Number of peers recorded in the outgoing path from source to the
271 * stored location of this message.
273 uint32_t put_path_length GNUNET_PACKED;
276 * Length of the GET path that follows (if tracked).
278 uint32_t get_path_length GNUNET_PACKED;
281 * Peer which queried for get and should get the result.
283 struct GNUNET_PeerIdentity querying_peer;
286 * When does the content expire?
288 struct GNUNET_TIME_AbsoluteNBO expiration_time;
291 * The key of the corresponding GET request.
293 struct GNUNET_HashCode key;
295 /* put path (if tracked) */
297 /* get path (if tracked) */
304 * P2P Trail setup message
306 struct PeerTrailSetupMessage
309 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
311 struct GNUNET_MessageHeader header;
314 * Is source_peer trying to setup the trail to a predecessor or any finger.
316 uint32_t is_predecessor;
319 * Peer closest to this value will be our finger.
321 uint64_t final_destination_finger_value;
324 * Source peer which wants to setup the trail to one of its finger.
326 struct GNUNET_PeerIdentity source_peer;
329 * Best known destination (could be my friend or finger) which should
330 * get this message next.
332 * FIXME: this could be removed if we include trail_source / trail_dest
333 * in the routing table. This way we save 32 bytes of bandwidth by using
334 * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID))
336 struct GNUNET_PeerIdentity best_known_destination;
339 * In case best_known_destination is a finger, then trail id of trail to
340 * reach to this finger.
342 struct GNUNET_HashCode intermediate_trail_id;
345 * Trail id for trail which we are trying to setup.
347 struct GNUNET_HashCode trail_id;
349 /* List of peers which are part of trail setup so far.
350 * Trail does NOT include source_peer and peer which will be closest to
351 * ultimate_destination_finger_value.
352 * struct GNUNET_PeerIdentity trail[]
357 * P2P Trail Setup Result message
359 struct PeerTrailSetupResultMessage
363 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
365 struct GNUNET_MessageHeader header;
368 * Finger to which we have found the path.
370 struct GNUNET_PeerIdentity finger_identity;
373 * Peer which started trail_setup to find trail to finger_identity
375 struct GNUNET_PeerIdentity querying_peer;
378 * Is the trail setup to querying_peer's predecessor or finger?
380 uint32_t is_predecessor;
383 * Value to which finger_identity is the closest peer.
385 uint64_t ultimate_destination_finger_value;
388 * Identifier of the trail from querying peer to finger_identity, NOT
389 * including both endpoints.
391 struct GNUNET_HashCode trail_id;
393 /* List of peers which are part of the trail from querying peer to
394 * finger_identity, NOT including both endpoints.
395 * struct GNUNET_PeerIdentity trail[]
400 * P2P Verify Successor Message.
402 struct PeerVerifySuccessorMessage
405 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
407 struct GNUNET_MessageHeader header;
410 * Peer which wants to verify its successor.
412 struct GNUNET_PeerIdentity source_peer;
415 * Source Peer's current successor.
417 struct GNUNET_PeerIdentity successor;
420 * Identifier of trail to reach from source_peer to successor.
422 struct GNUNET_HashCode trail_id;
424 /* List of the peers which are part of trail to reach from source_peer
425 * to successor, NOT including them
426 * struct GNUNET_PeerIdentity trail[]
431 * P2P Verify Successor Result Message
433 struct PeerVerifySuccessorResultMessage
436 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
438 struct GNUNET_MessageHeader header;
441 * Peer which sent the request to verify its successor.
443 struct GNUNET_PeerIdentity querying_peer;
446 * Successor to which PeerVerifySuccessorMessage was sent.
448 struct GNUNET_PeerIdentity current_successor;
451 * Current Predecessor of source_successor. It can be same as querying peer
452 * or different. In case it is different then it can be querying_peer's
453 * probable successor.
455 struct GNUNET_PeerIdentity probable_successor;
458 * Trail identifier of trail from querying_peer to current_successor.
460 struct GNUNET_HashCode trail_id;
463 * Direction in which we are looking at the trail.
465 uint32_t trail_direction;
467 /* In case probable_successor != querying_peer, then trail to reach from
468 * querying_peer to probable_successor, NOT including end points.
469 * struct GNUNET_PeerIdentity trail[]
474 * P2P Notify New Successor Message.
476 struct PeerNotifyNewSuccessorMessage
479 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
481 struct GNUNET_MessageHeader header;
484 * Peer which wants to notify its new successor.
486 struct GNUNET_PeerIdentity source_peer;
489 * New successor of source_peer.
491 struct GNUNET_PeerIdentity new_successor;
494 * Unique identifier of the trail from source_peer to new_successor,
495 * NOT including the endpoints.
497 struct GNUNET_HashCode trail_id;
499 /* List of peers in trail from source_peer to new_successor,
500 * NOT including the endpoints.
501 * struct GNUNET_PeerIdentity trail[]
506 * P2P Notify Successor Confirmation message.
508 struct PeerNotifyConfirmationMessage
511 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
513 struct GNUNET_MessageHeader header;
516 * Unique identifier of the trail.
518 struct GNUNET_HashCode trail_id;
521 * Direction of trail.
523 uint32_t trail_direction;
528 * P2P Trail Tear Down message.
530 struct PeerTrailTearDownMessage
533 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
535 struct GNUNET_MessageHeader header;
538 * Unique identifier of the trail.
540 struct GNUNET_HashCode trail_id;
543 * Direction of trail.
545 uint32_t trail_direction;
550 * P2P Trail Rejection Message.
552 struct PeerTrailRejectionMessage
555 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
557 struct GNUNET_MessageHeader header;
560 * Peer which wants to set up the trail.
562 struct GNUNET_PeerIdentity source_peer;
565 * Peer which sent trail rejection message as it it congested.
567 struct GNUNET_PeerIdentity congested_peer;
570 * Peer identity closest to this value will be finger of
573 uint64_t ultimate_destination_finger_value;
576 * Is source_peer trying to setup the trail to its predecessor or finger.
578 uint32_t is_predecessor;
581 * Identifier for the trail that source peer is trying to setup.
583 struct GNUNET_HashCode trail_id;
586 * Relative time for which congested_peer will remain congested.
588 struct GNUNET_TIME_Relative congestion_time;
590 /* Trail_list from source_peer to peer which sent the message for trail setup
591 * to congested peer. This trail does NOT include source_peer.
592 struct GNUNET_PeerIdnetity trail[]*/
596 * P2P Add Trail Message.
598 struct PeerAddTrailMessage
601 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
603 struct GNUNET_MessageHeader header;
606 * Source of the routing trail.
608 struct GNUNET_PeerIdentity source_peer;
611 * Destination of the routing trail.
613 struct GNUNET_PeerIdentity destination_peer;
616 * Unique identifier of the trail from source_peer to destination_peer,
617 * NOT including the endpoints.
619 struct GNUNET_HashCode trail_id;
621 /* Trail from source peer to destination peer, NOT including them.
622 * struct GNUNET_PeerIdentity trail[]
627 GNUNET_NETWORK_STRUCT_END
631 * Entry in friend_peermap.
638 const struct GNUNET_PeerIdentity *id;
641 * Number of trails for which this friend is the first hop or if the friend
644 unsigned int trails_count;
647 * In case not 0, then amount of time for which this friend is congested.
649 struct GNUNET_TIME_Absolute congestion_timestamp;
652 * Handle for sending messages to this friend.
654 struct GNUNET_MQ_Handle *mq;
659 * An individual element of the trail to reach to a finger.
664 * Pointer to next item in the list
666 struct Trail_Element *next;
669 * Pointer to prev item in the list
671 struct Trail_Element *prev;
674 * An element in this trail.
676 struct GNUNET_PeerIdentity peer;
680 * Information about an individual trail.
687 struct Trail_Element *trail_head;
692 struct Trail_Element *trail_tail;
695 * Unique identifier of this trail.
697 struct GNUNET_HashCode trail_id;
700 * Length of trail pointed
702 unsigned int trail_length;
705 * Is there a valid trail entry.
707 unsigned int is_present;
711 * An entry in finger_table
718 struct GNUNET_PeerIdentity finger_identity;
721 * In case not 0, this amount is time to wait for notify successor message.
722 * Used ONLY for successor. NOT for any other finger.
724 struct GNUNET_TIME_Absolute wait_notify_confirmation;
727 * Is any finger stored at this finger index.
729 unsigned int is_present;
732 * Index in finger peer map
734 uint32_t finger_table_index;
737 * Number of trails setup so far for this finger.
738 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
740 uint32_t trails_count;
743 * Array of trails to reach to this finger.
745 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
750 * Stores information about the peer which is closest to destination_finger_value.
751 * 'closest' can be either successor or predecessor depending on is_predecessor
757 * Destination finger value.
759 uint64_t destination_finger_value;
762 * Is finger_value a predecessor or any other finger.
764 unsigned int is_predecessor;
767 * Trail id to reach to peer.
768 * In case peer is my identity or friend, it is set to 0.
770 struct GNUNET_HashCode trail_id;
773 * Next destination. In case of friend and my_identity , it is same as next_hop
774 * In case of finger it is finger identity.
776 struct GNUNET_PeerIdentity best_known_destination;
779 * In case best_known_destination is a finger, then first friend in the trail
780 * to reach to it. In other case, same as best_known_destination.
782 struct GNUNET_PeerIdentity next_hop;
785 * In case finger is the next hop, it contains a valid finger table index
786 * at which the finger is stored. Else, It contains 65, which is out of range
787 * of finger table index.
789 unsigned int finger_table_index;
793 * Context for send_verify_successor_task.
795 struct VerifySuccessorContext
798 * Number of times this has been scheduled.
800 unsigned int num_retries_scheduled;
804 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
805 * get our first friend.
807 static struct GNUNET_SCHEDULER_Task *find_finger_trail_task;
810 * Task that sends verify successor message. This task is started when we get
811 * our successor for the first time.
813 static struct GNUNET_SCHEDULER_Task *send_verify_successor_task;
816 * Task that sends verify successor message. This task is started when we get
817 * our successor for the first time.
819 static struct GNUNET_SCHEDULER_Task *send_verify_successor_retry_task;
822 * Task that sends verify successor message. This task is started when we get
823 * our successor for the first time.
825 static struct GNUNET_SCHEDULER_Task *send_notify_new_successor_retry_task;
828 * Identity of this peer.
830 static struct GNUNET_PeerIdentity my_identity;
833 * Peer map of all the friends of a peer
835 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
838 * Array of all the fingers.
840 static struct FingerInfo finger_table [MAX_FINGERS];
845 static struct GNUNET_CORE_Handle *core_api;
848 * The current finger index that we have want to find trail to. We start the
849 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
850 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
851 * we reset this index to 0.
853 static unsigned int current_search_finger_index;
856 * Time duration to schedule find finger trail task.
858 static struct GNUNET_TIME_Relative find_finger_trail_task_next_send_time;
861 * Time duration to schedule verify successor task.
863 static struct GNUNET_TIME_Relative verify_successor_next_send_time;
866 * Time duration to send verify successor again, if result was not received in time.
868 static struct GNUNET_TIME_Relative verify_successor_retry_time;
871 * Time duration to retry send_notify_successor.
873 static struct GNUNET_TIME_Relative notify_successor_retry_time;
876 * Are we waiting for confirmation from our new successor that it got the
879 //static unsigned int waiting_for_notify_confirmation;
881 /* Below variables are used only for testing, and statistics collection. */
883 * Should we store our topology predecessor and successor IDs into statistics?
885 unsigned int track_topology;
888 * Count of fingers found. Ideally we should have O(logn) fingers for a
891 static unsigned int total_fingers_found;
894 * Number of times we found the same successor.
896 static unsigned int successor_times;
899 * Number of rounds for which we should search for finger.
901 static unsigned int fingers_round_count;
905 * Construct a trail setup message and forward it to @a target_friend
907 * @param source_peer Peer which wants to setup the trail
908 * @param ultimate_destination_finger_value Peer identity closest to this value
909 * will be finger to @a source_peer
910 * @param best_known_destination Best known destination (could be finger or friend)
911 * which should get this message. In case it is
912 * friend, then it is same as target_friend
913 * @param target_friend Friend to which message is forwarded now.
914 * @param trail_length Total number of peers in trail setup so far.
915 * @param trail_peer_list Trail setup so far
916 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
917 * @param trail_id Unique identifier for the trail we are trying to setup.
918 * @param intermediate_trail_id Trail id of intermediate trail to reach to
919 * best_known_destination when its a finger. If not
920 * used then set to 0.
923 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
924 uint64_t ultimate_destination_finger_value,
925 const struct GNUNET_PeerIdentity *best_known_destination,
926 const struct FriendInfo *target_friend,
927 unsigned int trail_length,
928 const struct GNUNET_PeerIdentity *trail_peer_list,
929 unsigned int is_predecessor,
930 const struct GNUNET_HashCode *trail_id,
931 const struct GNUNET_HashCode *intermediate_trail_id)
933 struct GNUNET_MQ_Envelope *env;
934 struct PeerTrailSetupMessage *tsm;
937 msize = trail_length * sizeof (struct GNUNET_PeerIdentity);
938 if (msize + sizeof (struct PeerTrailSetupMessage)
939 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
944 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
946 GNUNET_STATISTICS_update (GDS_stats,
947 gettext_noop ("# P2P messages dropped due to full queue"),
952 env = GNUNET_MQ_msg_extra (tsm,
954 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
955 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
956 tsm->source_peer = *source_peer;
957 tsm->best_known_destination = *best_known_destination;
958 tsm->is_predecessor = htonl (is_predecessor);
959 tsm->trail_id = *trail_id;
960 tsm->intermediate_trail_id = *intermediate_trail_id;
961 GNUNET_memcpy (&tsm[1],
964 GNUNET_MQ_send (target_friend->mq,
970 * Construct a trail setup result message and forward it to @a target_friend.
972 * @param querying_peer Peer which sent the trail setup request and should get
974 * @param Finger Peer to which the trail has been setup to.
975 * @param target_friend Friend to which this message should be forwarded.
976 * @param trail_length Numbers of peers in the trail.
977 * @param trail_peer_list Peers which are part of the trail from
978 * querying_peer to Finger, NOT including them.
979 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
980 * @param ultimate_destination_finger_value Value to which @a finger is the closest
982 * @param trail_id Unique identifier of the trail.
985 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *querying_peer,
986 const struct GNUNET_PeerIdentity *finger,
987 struct FriendInfo *target_friend,
988 unsigned int trail_length,
989 const struct GNUNET_PeerIdentity *trail_peer_list,
990 unsigned int is_predecessor,
991 uint64_t ultimate_destination_finger_value,
992 const struct GNUNET_HashCode *trail_id)
994 struct GNUNET_MQ_Envelope *env;
995 struct PeerTrailSetupResultMessage *tsrm;
998 msize = trail_length * sizeof (struct GNUNET_PeerIdentity);
999 if (msize + sizeof (struct PeerTrailSetupResultMessage)
1000 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1005 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1007 GNUNET_STATISTICS_update (GDS_stats,
1008 gettext_noop ("# P2P messages dropped due to full queue"),
1013 env = GNUNET_MQ_msg_extra (tsrm,
1015 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1016 tsrm->querying_peer = *querying_peer;
1017 tsrm->finger_identity = *finger;
1018 tsrm->is_predecessor = htonl (is_predecessor);
1019 tsrm->trail_id = *trail_id;
1020 tsrm->ultimate_destination_finger_value
1021 = GNUNET_htonll (ultimate_destination_finger_value);
1022 GNUNET_memcpy (&tsrm[1],
1025 GNUNET_MQ_send (target_friend->mq,
1031 * Send notify successor confirmation message.
1033 * @param trail_id Unique Identifier of the trail.
1034 * @param trail_direction Destination to Source.
1035 * @param target_friend Friend to get this message next.
1038 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (const struct GNUNET_HashCode *trail_id,
1039 unsigned int trail_direction,
1040 struct FriendInfo *target_friend)
1042 struct PeerNotifyConfirmationMessage *ncm;
1043 struct GNUNET_MQ_Envelope *env;
1045 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1047 GNUNET_STATISTICS_update (GDS_stats,
1048 gettext_noop ("# P2P messages dropped due to full queue"),
1053 env = GNUNET_MQ_msg (ncm,
1054 GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION);
1055 ncm->trail_id = *trail_id;
1056 ncm->trail_direction = htonl (trail_direction);
1057 GNUNET_MQ_send (target_friend->mq,
1063 * Send trail rejection message to @a target_friend
1065 * @param source_peer Peer which is trying to setup the trail.
1066 * @param ultimate_destination_finger_value Peer closest to this value will be
1067 * @a source_peer's finger
1068 * @param congested_peer Peer which sent this message as it is congested.
1069 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1070 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1071 * by congested_peer. This does NOT include @a source_peer
1072 * and congested_peer.
1073 * @param trail_length Total number of peers in trail_peer_list, NOT including
1074 * @a source_peer and @a congested_peer
1075 * @param trail_id Unique identifier of this trail.
1076 * @param congestion_timeout Duration given by congested peer as an estimate of
1077 * how long it may remain congested.
1080 GDS_NEIGHBOURS_send_trail_rejection (const struct GNUNET_PeerIdentity *source_peer,
1081 uint64_t ultimate_destination_finger_value,
1082 const struct GNUNET_PeerIdentity *congested_peer,
1083 unsigned int is_predecessor,
1084 const struct GNUNET_PeerIdentity *trail_peer_list,
1085 unsigned int trail_length,
1086 const struct GNUNET_HashCode *trail_id,
1087 struct FriendInfo *target_friend,
1088 const struct GNUNET_TIME_Relative congestion_timeout)
1090 struct PeerTrailRejectionMessage *trm;
1091 struct GNUNET_MQ_Envelope *env;
1094 msize = trail_length * sizeof (struct GNUNET_PeerIdentity);
1095 if (msize + sizeof (struct PeerTrailRejectionMessage)
1096 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1101 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1103 GNUNET_STATISTICS_update (GDS_stats,
1104 gettext_noop ("# P2P messages dropped due to full queue"),
1109 env = GNUNET_MQ_msg_extra (trm,
1111 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1112 trm->source_peer = *source_peer;
1113 trm->congested_peer = *congested_peer;
1114 trm->congestion_time = congestion_timeout;
1115 trm->is_predecessor = htonl (is_predecessor);
1116 trm->trail_id = *trail_id;
1117 trm->ultimate_destination_finger_value
1118 = GNUNET_htonll (ultimate_destination_finger_value);
1119 GNUNET_memcpy (&trm[1],
1122 GNUNET_MQ_send (target_friend->mq,
1128 * Construct a verify successor message and forward it to target_friend.
1129 * @param source_peer Peer which wants to verify its successor.
1130 * @param successor Peer which is @a source_peer's current successor.
1131 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1132 * NOT including them.
1133 * @param trail List of peers which are part of trail to reach from @a source_peer
1134 * to @a successor, NOT including them.
1135 * @param trail_length Total number of peers in @a trail.
1136 * @param target_friend Next friend to get this message.
1139 GDS_NEIGHBOURS_send_verify_successor_message (const struct GNUNET_PeerIdentity *source_peer,
1140 const struct GNUNET_PeerIdentity *successor,
1141 const struct GNUNET_HashCode *trail_id,
1142 struct GNUNET_PeerIdentity *trail,
1143 unsigned int trail_length,
1144 struct FriendInfo *target_friend)
1146 struct PeerVerifySuccessorMessage *vsm;
1147 struct GNUNET_MQ_Envelope *env;
1150 msize = trail_length * sizeof (struct GNUNET_PeerIdentity);
1151 if (msize + sizeof (*vsm) >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1156 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1158 GNUNET_STATISTICS_update (GDS_stats,
1159 gettext_noop ("# P2P messages dropped due to full queue"),
1164 env = GNUNET_MQ_msg_extra (vsm,
1166 GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1167 vsm->source_peer = *source_peer;
1168 vsm->successor = *successor;
1169 vsm->trail_id = *trail_id;
1170 GNUNET_memcpy (&vsm[1],
1173 GNUNET_MQ_send (target_friend->mq,
1179 * FIXME: In every function we pass target friend except for this one.
1180 * so, either change everything or this one. also, should we just store
1181 * the pointer to friend in routing table rather than gnunet_peeridentity.
1182 * if yes then we should keep friend info in.h andmake lot of changes.
1183 * Construct a trail teardown message and forward it to target friend.
1185 * @param trail_id Unique identifier of the trail.
1186 * @param trail_direction Direction of trail.
1187 * @param target_friend Friend to get this message.
1190 GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_HashCode *trail_id,
1191 unsigned int trail_direction,
1192 const struct GNUNET_PeerIdentity *peer)
1194 struct PeerTrailTearDownMessage *ttdm;
1195 struct GNUNET_MQ_Envelope *env;
1196 struct FriendInfo *target_friend;
1198 if (NULL == (target_friend =
1199 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1202 /* FIXME: In what case friend can be null. ?*/
1206 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1208 GNUNET_STATISTICS_update (GDS_stats,
1209 gettext_noop ("# P2P messages dropped due to full queue"),
1214 env = GNUNET_MQ_msg (ttdm,
1215 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1216 ttdm->trail_id = *trail_id;
1217 ttdm->trail_direction = htonl (trail_direction);
1218 GNUNET_MQ_send (target_friend->mq,
1224 * Construct a verify successor result message and send it to target_friend
1226 * @param querying_peer Peer which sent the verify successor message.
1227 * @param source_successor Current_successor of @a querying_peer.
1228 * @param current_predecessor Current predecessor of @a successor. Could be same
1229 * or different from @a querying_peer.
1230 * @param trail_id Unique identifier of the trail from @a querying_peer to
1231 * @a successor, NOT including them.
1232 * @param trail List of peers which are part of trail from @a querying_peer to
1233 * @a successor, NOT including them.
1234 * @param trail_length Total number of peers in @a trail
1235 * @param trail_direction Direction in which we are sending the message. In this
1236 * case we are sending result from @a successor to @a querying_peer.
1237 * @param target_friend Next friend to get this message.
1240 GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *querying_peer,
1241 const struct GNUNET_PeerIdentity *current_successor,
1242 const struct GNUNET_PeerIdentity *probable_successor,
1243 const struct GNUNET_HashCode *trail_id,
1244 const struct GNUNET_PeerIdentity *trail,
1245 unsigned int trail_length,
1246 enum GDS_ROUTING_trail_direction trail_direction,
1247 struct FriendInfo *target_friend)
1249 struct PeerVerifySuccessorResultMessage *vsmr;
1250 struct GNUNET_MQ_Envelope *env;
1253 msize = trail_length * sizeof(struct GNUNET_PeerIdentity);
1254 if (msize + sizeof (struct PeerVerifySuccessorResultMessage)
1255 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1260 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1262 GNUNET_STATISTICS_update (GDS_stats,
1263 gettext_noop ("# P2P messages dropped due to full queue"),
1268 env = GNUNET_MQ_msg_extra (vsmr,
1270 GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1271 vsmr->querying_peer = *querying_peer;
1272 vsmr->current_successor = *current_successor;
1273 vsmr->probable_successor = *probable_successor;
1274 vsmr->trail_direction = htonl (trail_direction);
1275 vsmr->trail_id = *trail_id;
1276 GNUNET_memcpy (&vsmr[1],
1279 GNUNET_MQ_send (target_friend->mq,
1285 * Construct a notify new successor message and send it to target_friend
1286 * @param source_peer Peer which wants to notify to its new successor that it
1287 * could be its predecessor.
1288 * @param successor New successor of @a source_peer
1289 * @param successor_trail List of peers in Trail to reach from
1290 * @a source_peer to @a new_successor, NOT including
1292 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1293 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1294 * @param target_friend Next friend to get this message.
1297 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1298 const struct GNUNET_PeerIdentity *successor,
1299 const struct GNUNET_PeerIdentity *successor_trail,
1300 unsigned int successor_trail_length,
1301 const struct GNUNET_HashCode *succesor_trail_id,
1302 struct FriendInfo *target_friend)
1304 struct PeerNotifyNewSuccessorMessage *nsm;
1305 struct GNUNET_MQ_Envelope *env;
1308 msize = successor_trail_length * sizeof(struct GNUNET_PeerIdentity);
1309 if (msize + sizeof (struct PeerNotifyNewSuccessorMessage)
1310 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1315 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1317 GNUNET_STATISTICS_update (GDS_stats,
1318 gettext_noop ("# P2P messages dropped due to full queue"),
1323 env = GNUNET_MQ_msg_extra (nsm,
1325 GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1326 nsm->new_successor = *successor;
1327 nsm->source_peer = *source_peer;
1328 nsm->trail_id = *succesor_trail_id;
1329 GNUNET_memcpy (&nsm[1],
1332 GNUNET_MQ_send (target_friend->mq,
1338 * Construct an add_trail message and send it to target_friend
1340 * @param source_peer Source of the trail.
1341 * @param destination_peer Destination of the trail.
1342 * @param trail_id Unique identifier of the trail from
1343 * @a source_peer to @a destination_peer, NOT including the endpoints.
1344 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1345 * NOT including the endpoints.
1346 * @param trail_length Total number of peers in @a trail.
1347 * @param target_friend Next friend to get this message.
1350 GDS_NEIGHBOURS_send_add_trail (const struct GNUNET_PeerIdentity *source_peer,
1351 const struct GNUNET_PeerIdentity *destination_peer,
1352 const struct GNUNET_HashCode *trail_id,
1353 const struct GNUNET_PeerIdentity *trail,
1354 unsigned int trail_length,
1355 struct FriendInfo *target_friend)
1357 struct PeerAddTrailMessage *adm;
1358 struct GNUNET_MQ_Envelope *env;
1361 msize = trail_length * sizeof(struct GNUNET_PeerIdentity);
1362 if (msize + sizeof (struct PeerAddTrailMessage)
1363 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1368 if (GNUNET_MQ_get_length (target_friend->mq) >= MAXIMUM_PENDING_PER_FRIEND)
1370 GNUNET_STATISTICS_update (GDS_stats,
1371 gettext_noop ("# P2P messages dropped due to full queue"),
1376 env = GNUNET_MQ_msg_extra (adm,
1378 GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1379 adm->source_peer = *source_peer;
1380 adm->destination_peer = *destination_peer;
1381 adm->trail_id = *trail_id;
1382 GNUNET_memcpy (&adm[1],
1385 GNUNET_MQ_send (target_friend->mq,
1391 * Search my location in trail. In case I am present more than once in the
1392 * trail (can happen during trail setup), then return my lowest index.
1394 * @param trail List of peers
1395 * @return my_index if found
1396 * trail_length + 1 if an entry is present twice, It is an error.
1397 * -1 if no entry found.
1400 search_my_index (const struct GNUNET_PeerIdentity *trail,
1404 int index_seen = trail_length + 1;
1407 for (i = 0; i < trail_length; i++)
1409 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1412 if(index_seen == (trail_length + 1))
1416 DEBUG("Entry is present twice in trail. Its not allowed\n");
1429 * Check if the friend is congested or have reached maximum number of trails
1430 * it can be part of of.
1431 * @param friend Friend to be checked.
1432 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1433 * #GNUNET_YES if friend is either congested or have crossed threshold
1436 is_friend_congested (struct FriendInfo *friend)
1438 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1439 ((0 == GNUNET_TIME_absolute_get_remaining
1440 (friend->congestion_timestamp).rel_value_us)))
1447 * Select closest finger to value.
1449 * @param peer1 First peer
1450 * @param peer2 Second peer
1451 * @param value Value to be compare
1452 * @return Closest peer
1454 static const struct GNUNET_PeerIdentity *
1455 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1456 const struct GNUNET_PeerIdentity *peer2,
1459 uint64_t peer1_value;
1460 uint64_t peer2_value;
1462 GNUNET_memcpy (&peer1_value, peer1, sizeof (uint64_t));
1463 GNUNET_memcpy (&peer2_value, peer2, sizeof (uint64_t));
1464 peer1_value = GNUNET_ntohll (peer1_value);
1465 peer2_value = GNUNET_ntohll (peer2_value);
1467 if (peer1_value == value)
1472 if (peer2_value == value)
1477 if (value < peer1_value && peer1_value < peer2_value)
1481 else if (value < peer2_value && peer2_value < peer1_value)
1485 else if (peer1_value < value && value < peer2_value)
1489 else if (peer2_value < value && value < peer1_value)
1493 else if (peer1_value < peer2_value && peer2_value < value)
1497 else // if (peer2_value < peer1_value && peer1_value < value)
1505 * Select closest predecessor to value.
1507 * @param peer1 First peer
1508 * @param peer2 Second peer
1509 * @param value Value to be compare
1510 * @return Peer which precedes value in the network.
1512 static const struct GNUNET_PeerIdentity *
1513 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1514 const struct GNUNET_PeerIdentity *peer2,
1517 uint64_t peer1_value;
1518 uint64_t peer2_value;
1520 GNUNET_memcpy (&peer1_value, peer1, sizeof (uint64_t));
1521 GNUNET_memcpy (&peer2_value, peer2, sizeof (uint64_t));
1522 peer1_value = GNUNET_ntohll (peer1_value);
1523 peer2_value = GNUNET_ntohll (peer2_value);
1525 if (peer1_value == value)
1530 if (peer2_value == value)
1535 if (value < peer1_value && peer1_value < peer2_value)
1539 else if (value < peer2_value && peer2_value < peer1_value)
1543 else if (peer1_value < value && value < peer2_value)
1547 else if (peer2_value < value && value < peer1_value)
1551 else if (peer1_value < peer2_value && peer2_value < value)
1555 else // if (peer2_value < peer1_value && peer1_value < value)
1567 test_print_trail (struct GNUNET_PeerIdentity *trail,
1568 unsigned int trail_length)
1570 struct GNUNET_PeerIdentity print_peer;
1573 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1574 __FILE__, __func__,__LINE__,trail_length);
1575 for (i =0 ; i< trail_length; i++)
1577 print_peer = trail[i];
1578 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1579 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1586 * This is a test function to print all the entries of friend table.
1589 test_friend_peermap_print ()
1591 struct FriendInfo *friend;
1592 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1593 struct GNUNET_PeerIdentity print_peer;
1594 struct GNUNET_PeerIdentity key_ret;
1597 print_peer = my_identity;
1598 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1599 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1601 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1603 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1605 (const void **)&friend))
1607 GNUNET_memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1608 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1609 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1617 * This is a test function, to print all the entries of finger table.
1620 test_finger_table_print()
1622 struct FingerInfo *finger;
1623 struct GNUNET_PeerIdentity print_peer;
1624 //struct Trail *trail;
1628 print_peer = my_identity;
1629 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1630 for (i = 0; i < MAX_FINGERS; i++)
1632 finger = &finger_table[i];
1634 if (GNUNET_NO == finger->is_present)
1637 print_peer = finger->finger_identity;
1638 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1639 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1642 for (j = 0; j < finger->trails_count; j++)
1644 trail = &finger->trail_list[j];
1645 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1646 struct Trail_Element *element;
1647 element = trail->trail_head;
1648 for (k = 0; k < trail->trail_length; k++)
1650 print_peer = element->peer;
1651 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1652 element = element->next;
1661 * Select the closest peer among two peers (which should not be same)
1662 * with respect to value and finger_table_index
1663 * NOTE: peer1 != peer2
1664 * @param peer1 First peer
1665 * @param peer2 Second peer
1666 * @param value Value relative to which we find the closest
1667 * @param is_predecessor Is value a predecessor or any other finger.
1668 * @return Closest peer among two peers.
1670 static const struct GNUNET_PeerIdentity *
1671 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1672 const struct GNUNET_PeerIdentity *peer2,
1674 unsigned int is_predecessor)
1676 /* This check is here to ensure that calling function never sends
1677 same peer value in peer1 and peer2. Remove it later. */
1678 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1679 if (1 == is_predecessor)
1680 return select_closest_predecessor (peer1, peer2, value);
1682 // TODO: Change name to something like select_closest_successor!!
1683 return select_closest_finger (peer1, peer2, value);
1688 * Iterate over the list of all the trails of a finger. In case the first
1689 * friend to reach the finger has reached trail threshold or is congested,
1690 * then don't select it. In case there multiple available good trails to reach
1691 * to Finger, choose the one with shortest trail length.
1692 * Note: We use length as parameter. But we can use any other suitable parameter
1694 * @param finger Finger Finger whose trail we have to select.
1695 * @return Trail Selected Trail.
1697 static struct Trail *
1698 select_finger_trail (struct FingerInfo *finger)
1700 struct FriendInfo *friend;
1701 struct Trail *current_finger_trail;
1702 struct Trail *best_trail = NULL;
1705 GNUNET_assert (finger->trails_count > 0);
1706 for (i = 0; i < finger->trails_count; i++)
1708 current_finger_trail = &finger->trail_list[i];
1710 /* No trail stored at this index. */
1711 if (GNUNET_NO == current_finger_trail->is_present)
1714 GNUNET_assert (NULL !=
1716 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1717 ¤t_finger_trail->trail_head->peer)));
1719 /* First friend to reach trail is not free. */
1720 if (GNUNET_YES == is_friend_congested (friend))
1723 if (NULL == best_trail ||
1724 best_trail->trail_length > current_finger_trail->trail_length)
1726 best_trail = current_finger_trail;
1735 * Compare FINGER entry with current successor. If finger's first friend of all
1736 * its trail is not congested and has not crossed trail threshold, then check
1737 * if finger peer identity is closer to final_destination_finger_value than
1738 * current_successor. If yes then update current_successor.
1739 * @param current_successor[in/out]
1743 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
1745 struct FingerInfo *finger;
1746 const struct GNUNET_PeerIdentity *closest_peer;
1747 struct Trail *finger_trail;
1750 /* Iterate over finger table. */
1751 for (i = 0; i < MAX_FINGERS; i++)
1753 finger = &finger_table[i];
1755 if (GNUNET_NO == finger->is_present)
1758 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1759 ¤t_closest_peer->best_known_destination))
1762 /* If I am my own finger, then ignore this finger. */
1763 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1767 /* If finger is a friend, we have already checked it in previous function. */
1768 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1769 &finger->finger_identity)))
1774 closest_peer = select_closest_peer (&finger->finger_identity,
1775 ¤t_closest_peer->best_known_destination,
1776 current_closest_peer->destination_finger_value,
1777 current_closest_peer->is_predecessor);
1779 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity,
1782 /* Choose one of the trail to reach to finger. */
1783 finger_trail = select_finger_trail (finger);
1785 /* In case no trail found, ignore this finger. */
1786 if (NULL == finger_trail)
1789 current_closest_peer->best_known_destination = *closest_peer;
1790 current_closest_peer->next_hop = finger_trail->trail_head->peer;
1791 current_closest_peer->trail_id = finger_trail->trail_id;
1792 current_closest_peer->finger_table_index = i;
1800 * Compare friend entry with current successor.
1801 * If friend identity and current_successor is same, then do nothing.
1802 * If friend is not congested and has not crossed trail threshold, then check
1803 * if friend peer identity is closer to final_destination_finger_value than
1804 * current_successor. If yes then update current_successor.
1806 * @param cls closure
1807 * @param key current public key
1808 * @param value struct Closest_Peer
1809 * @return #GNUNET_YES if we should continue to iterate,
1810 * #GNUNET_NO if not.
1813 compare_friend_and_current_closest_peer (void *cls,
1814 const struct GNUNET_PeerIdentity *key,
1817 struct FriendInfo *friend = value;
1818 struct Closest_Peer *current_closest_peer = cls;
1819 const struct GNUNET_PeerIdentity *closest_peer;
1821 /* Friend is either congested or has crossed threshold. */
1822 if (GNUNET_YES == is_friend_congested (friend))
1825 /* If current_closest_peer and friend identity are same, then do nothing.*/
1826 if (0 == GNUNET_CRYPTO_cmp_peer_identity (friend->id,
1827 ¤t_closest_peer->best_known_destination))
1833 closest_peer = select_closest_peer (friend->id,
1834 ¤t_closest_peer->best_known_destination,
1835 current_closest_peer->destination_finger_value,
1836 current_closest_peer->is_predecessor);
1838 /* Is friend the closest successor? */
1839 if (0 == GNUNET_CRYPTO_cmp_peer_identity (friend->id,
1842 current_closest_peer->best_known_destination = *friend->id;
1843 current_closest_peer->next_hop = *friend->id;
1850 * Initialize current_successor to my_identity.
1851 * @param my_identity My peer identity
1852 * @return Updated closest_peer
1854 static struct Closest_Peer
1855 init_closest_peer (struct GNUNET_PeerIdentity my_identity,
1856 uint64_t destination_finger_value,
1857 unsigned int is_predecessor)
1859 struct Closest_Peer current_closest_peer;
1861 memset (¤t_closest_peer.trail_id,
1863 sizeof(struct GNUNET_HashCode));
1864 current_closest_peer.destination_finger_value = destination_finger_value;
1865 current_closest_peer.is_predecessor = is_predecessor;
1866 current_closest_peer.next_hop = my_identity;
1867 current_closest_peer.best_known_destination = my_identity;
1868 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
1869 return current_closest_peer;
1874 * Find locally best known peer, among your own identity, friend and finger list,
1875 * which is closest to given destination_finger_value.
1877 * NOTE: In case a friend is also a finger, then it is always chosen as friend
1879 * @param destination_finger_value Peer closest to this value will be the next destination.
1880 * @param is_predecessor Are we looking for predecessor or finger?
1881 * @return Closest_Peer that contains all the relevant field to reach to
1882 * @a destination_finger_value
1884 static struct Closest_Peer
1885 find_local_best_known_next_hop (uint64_t destination_finger_value,
1886 unsigned int is_predecessor)
1888 struct Closest_Peer current_closest_peer;
1890 /* Initialize current_successor to my_identity. */
1891 current_closest_peer = init_closest_peer (my_identity,
1892 destination_finger_value,
1895 /* Compare each friend entry with current_successor and update current_successor
1896 * with friend if its closest. */
1899 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
1900 &compare_friend_and_current_closest_peer,
1901 ¤t_closest_peer));
1903 /* Compare each finger entry with current_successor and update current_successor
1904 * with finger if its closest. */
1905 compare_finger_and_current_closest_peer (¤t_closest_peer);
1906 return current_closest_peer;
1911 * Construct a Put message and send it to target_peer.
1912 * @param key Key for the content
1913 * @param block_type Type of the block
1914 * @param options Routing options
1915 * @param desired_replication_level Desired replication count
1916 * @param best_known_dest Peer to which this message should reach eventually,
1917 * as it is best known destination to me.
1918 * @param intermediate_trail_id Trail id in case
1919 * @param target_peer Peer to which this message will be forwarded.
1920 * @param hop_count Number of hops traversed so far.
1921 * @param put_path_length Total number of peers in @a put_path
1922 * @param put_path Number of peers traversed so far
1923 * @param expiration_time When does the content expire
1924 * @param data Content to store
1925 * @param data_size Size of content @a data in bytes
1928 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
1929 enum GNUNET_BLOCK_Type block_type,
1930 enum GNUNET_DHT_RouteOption options,
1931 uint32_t desired_replication_level,
1932 struct GNUNET_PeerIdentity best_known_dest,
1933 struct GNUNET_HashCode intermediate_trail_id,
1934 struct GNUNET_PeerIdentity *target_peer,
1936 uint32_t put_path_length,
1937 struct GNUNET_PeerIdentity *put_path,
1938 struct GNUNET_TIME_Absolute expiration_time,
1939 const void *data, size_t data_size)
1941 struct PeerPutMessage *ppm;
1942 struct GNUNET_MQ_Envelope *env;
1943 struct FriendInfo *target_friend;
1944 struct GNUNET_PeerIdentity *pp;
1947 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size;
1948 if (msize + sizeof (struct PeerPutMessage)
1949 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1951 put_path_length = 0;
1954 if (msize + sizeof (struct PeerPutMessage)
1955 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1961 GNUNET_assert (NULL !=
1963 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1965 env = GNUNET_MQ_msg_extra (ppm,
1967 GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
1968 ppm->options = htonl (options);
1969 ppm->block_type = htonl (block_type);
1970 ppm->hop_count = htonl (hop_count + 1);
1971 ppm->desired_replication_level = htonl (desired_replication_level);
1972 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1973 ppm->best_known_destination = best_known_dest;
1974 ppm->intermediate_trail_id = intermediate_trail_id;
1976 ppm->put_path_length = htonl (put_path_length);
1977 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
1980 put_path_length * sizeof (struct GNUNET_PeerIdentity));
1981 GNUNET_memcpy (&pp[put_path_length],
1984 GNUNET_MQ_send (target_friend->mq,
1990 * Handle the put request from the client.
1992 * @param key Key for the content
1993 * @param block_type Type of the block
1994 * @param options Routing options
1995 * @param desired_replication_level Desired replication count
1996 * @param expiration_time When does the content expire
1997 * @param data Content to store
1998 * @param data_size Size of content @a data in bytes
2001 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
2002 enum GNUNET_BLOCK_Type block_type,
2003 enum GNUNET_DHT_RouteOption options,
2004 uint32_t desired_replication_level,
2005 struct GNUNET_TIME_Absolute expiration_time,
2009 struct GNUNET_PeerIdentity best_known_dest;
2010 struct GNUNET_HashCode intermediate_trail_id;
2011 struct GNUNET_PeerIdentity next_hop;
2013 struct Closest_Peer successor;
2015 GNUNET_memcpy (&key_value,
2018 key_value = GNUNET_ntohll (key_value);
2019 successor = find_local_best_known_next_hop (key_value,
2020 GDS_FINGER_TYPE_NON_PREDECESSOR);
2021 best_known_dest = successor.best_known_destination;
2022 next_hop = successor.next_hop;
2023 intermediate_trail_id = successor.trail_id;
2025 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest,
2028 DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",
2030 /* I am the destination. */
2031 GDS_DATACACHE_handle_put (expiration_time,
2038 GDS_CLIENTS_process_put (options,
2041 ntohl (desired_replication_level),
2050 /* In case we are sending the request to a finger, then send across all of its
2052 GDS_NEIGHBOURS_send_put (key,
2055 desired_replication_level,
2057 intermediate_trail_id,
2069 * Construct a Get message and send it to target_peer.
2071 * @param key Key for the content
2072 * @param block_type Type of the block
2073 * @param options Routing options
2074 * @param desired_replication_level Desired replication count
2075 * @param best_known_dest Peer which should get this message. Same as target peer
2076 * if best_known_dest is a friend else its a finger.
2077 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2078 * in case it is a finger else set to 0.
2079 * @param target_peer Peer to which this message will be forwarded.
2080 * @param hop_count Number of hops traversed so far.
2081 * @param data Content to store
2082 * @param data_size Size of content @a data in bytes
2083 * @param get_path_length Total number of peers in @a get_path
2084 * @param get_path Number of peers traversed so far
2087 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2088 enum GNUNET_BLOCK_Type block_type,
2089 enum GNUNET_DHT_RouteOption options,
2090 uint32_t desired_replication_level,
2091 const struct GNUNET_PeerIdentity *best_known_dest,
2092 const struct GNUNET_HashCode *intermediate_trail_id,
2093 const struct GNUNET_PeerIdentity *target_peer,
2095 uint32_t get_path_length,
2096 const struct GNUNET_PeerIdentity *get_path)
2098 struct PeerGetMessage *pgm;
2099 struct GNUNET_MQ_Envelope *env;
2100 struct FriendInfo *target_friend;
2103 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity);
2104 if (msize + sizeof (struct PeerGetMessage)
2105 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2110 GNUNET_assert (NULL !=
2112 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2114 env = GNUNET_MQ_msg_extra (pgm,
2116 GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2117 pgm->get_path_length = htonl (get_path_length);
2118 pgm->best_known_destination = *best_known_dest;
2120 pgm->intermediate_trail_id = *intermediate_trail_id;
2121 pgm->hop_count = htonl (hop_count + 1);
2122 pgm->get_path_length = htonl (get_path_length);
2123 GNUNET_memcpy (&pgm[1],
2126 GNUNET_MQ_send (target_friend->mq,
2132 * Handle the get request from the client file. If I am destination do
2133 * datacache put and return. Else find the target friend and forward message
2136 * @param key Key for the content
2137 * @param block_type Type of the block
2138 * @param options Routing options
2139 * @param desired_replication_level Desired replication count
2142 GDS_NEIGHBOURS_handle_get (const struct GNUNET_HashCode *key,
2143 enum GNUNET_BLOCK_Type block_type,
2144 enum GNUNET_DHT_RouteOption options,
2145 uint32_t desired_replication_level)
2147 struct Closest_Peer successor;
2148 struct GNUNET_PeerIdentity best_known_dest;
2149 struct GNUNET_HashCode intermediate_trail_id;
2152 GNUNET_memcpy (&key_value,
2155 key_value = GNUNET_ntohll (key_value);
2156 successor = find_local_best_known_next_hop (key_value,
2157 GDS_FINGER_TYPE_NON_PREDECESSOR);
2158 best_known_dest = successor.best_known_destination;
2159 intermediate_trail_id = successor.trail_id;
2161 /* I am the destination. I have the data. */
2162 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2165 GDS_DATACACHE_handle_get (key,
2178 GDS_NEIGHBOURS_send_get (key,
2181 desired_replication_level,
2183 &intermediate_trail_id,
2184 &successor.next_hop,
2192 * Send the get result to requesting client.
2194 * @param key Key of the requested data.
2195 * @param type Block type
2196 * @param target_peer Next peer to forward the message to.
2197 * @param source_peer Peer which has the data for the key.
2198 * @param put_path_length Number of peers in @a put_path
2199 * @param put_path Path taken to put the data at its stored location.
2200 * @param get_path_length Number of peers in @a get_path
2201 * @param get_path Path taken to reach to the location of the key.
2202 * @param expiration When will this result expire?
2203 * @param data Payload to store
2204 * @param data_size Size of the @a data
2207 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2208 enum GNUNET_BLOCK_Type type,
2209 const struct GNUNET_PeerIdentity *target_peer,
2210 const struct GNUNET_PeerIdentity *source_peer,
2211 unsigned int put_path_length,
2212 const struct GNUNET_PeerIdentity *put_path,
2213 unsigned int get_path_length,
2214 const struct GNUNET_PeerIdentity *get_path,
2215 struct GNUNET_TIME_Absolute expiration,
2216 const void *data, size_t data_size)
2218 struct PeerGetResultMessage *get_result;
2219 struct GNUNET_PeerIdentity *paths;
2220 struct GNUNET_MQ_Envelope *env;
2221 struct FriendInfo *target_friend;
2222 int current_path_index;
2225 msize = (put_path_length + get_path_length) * sizeof (struct GNUNET_PeerIdentity) +
2227 if (msize + sizeof (struct PeerGetResultMessage)
2228 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2230 put_path_length = 0;
2233 if (msize + sizeof (struct PeerGetResultMessage)
2234 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2239 current_path_index = 0;
2240 if (get_path_length > 0)
2242 current_path_index = search_my_index (get_path,
2244 if (-1 == current_path_index)
2249 if ((get_path_length + 1) == current_path_index)
2251 DEBUG ("Peer found twice in get path. Not allowed \n");
2256 if (0 == current_path_index)
2258 DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",
2260 GNUNET_i2s(&my_identity));
2261 GDS_CLIENTS_handle_reply (expiration,
2272 env = GNUNET_MQ_msg_extra (get_result,
2274 GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2275 get_result->key = *key;
2276 get_result->querying_peer = *source_peer;
2277 get_result->expiration_time = GNUNET_TIME_absolute_hton (expiration);
2278 get_result->get_path_length = htonl (get_path_length);
2279 get_result->put_path_length = htonl (put_path_length);
2280 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2281 GNUNET_memcpy (paths,
2283 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2284 GNUNET_memcpy (&paths[put_path_length],
2286 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2287 GNUNET_memcpy (&paths[put_path_length + get_path_length],
2291 GNUNET_assert (NULL !=
2293 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2294 &get_path[current_path_index - 1])));
2295 GNUNET_MQ_send (target_friend->mq,
2301 * Randomly choose one of your friends (which is not congested and have not crossed
2302 * trail threshold) from the friend_peermap
2303 * @return Friend Randomly chosen friend.
2304 * NULL in case friend peermap is empty, or all the friends are either
2305 * congested or have crossed trail threshold.
2307 static struct FriendInfo *
2308 select_random_friend ()
2310 unsigned int current_size;
2313 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2314 struct GNUNET_PeerIdentity key_ret;
2315 struct FriendInfo *friend;
2317 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2320 if (0 == current_size)
2323 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2324 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2326 /* Iterate till you don't reach to index. */
2327 for (j = 0; j < index ; j++)
2328 GNUNET_assert (GNUNET_YES ==
2329 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2333 /* Reset the index in friend peermap to 0 as we reached to the end. */
2334 if (j == current_size)
2337 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2338 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2342 /* Get the friend stored at the index, j*/
2343 GNUNET_assert (GNUNET_YES ==
2344 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2346 (const void **)&friend));
2348 /* This friend is not congested and has not crossed trail threshold. */
2349 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2350 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2356 } while (j != index);
2358 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2364 * Compute 64 bit value of finger_identity corresponding to a finger index using
2366 * For all fingers, n.finger[i] = n + pow (2,i),
2367 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2368 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2370 * @param finger_index Index corresponding to which we calculate 64 bit value.
2371 * @return 64 bit value.
2374 compute_finger_identity_value (unsigned int finger_index)
2378 GNUNET_memcpy (&my_id64,
2381 my_id64 = GNUNET_ntohll (my_id64);
2383 /* Are we looking for immediate predecessor? */
2384 if (PREDECESSOR_FINGER_ID == finger_index)
2385 return (my_id64 - 1);
2386 uint64_t add = (uint64_t)1 << finger_index;
2387 return (my_id64 + add);
2392 * Choose a random friend. Calculate the next finger identity to search,from
2393 * current_search_finger_index. Start looking for the trail to reach to
2394 * finger identity through this random friend.
2396 * @param cls closure for this task
2399 send_find_finger_trail_message (void *cls)
2401 struct FriendInfo *target_friend;
2402 struct GNUNET_HashCode trail_id;
2403 struct GNUNET_HashCode intermediate_trail_id;
2404 unsigned int is_predecessor = 0;
2405 uint64_t finger_id_value;
2407 /* Schedule another send_find_finger_trail_message task. After one round of
2408 * finger search, this time is exponentially backoff. */
2409 find_finger_trail_task_next_send_time.rel_value_us =
2410 find_finger_trail_task_next_send_time.rel_value_us +
2411 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2412 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2413 find_finger_trail_task =
2414 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2415 &send_find_finger_trail_message,
2418 /* No space in my routing table. (Source and destination peers also store entries
2419 * in their routing table). */
2420 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2423 target_friend = select_random_friend ();
2424 if (NULL == target_friend)
2427 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2428 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2431 /* Generate a unique trail id for trail we are trying to setup. */
2432 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2435 memset (&intermediate_trail_id,
2437 sizeof (struct GNUNET_HashCode));
2438 GDS_NEIGHBOURS_send_trail_setup (&my_identity,
2445 &intermediate_trail_id);
2450 * In case there are already maximum number of possible trails to reach to a
2451 * finger, then check if the new trail's length is lesser than any of the
2453 * If yes then replace that old trail by new trail.
2455 * Note: Here we are taking length as a parameter to choose the best possible
2456 * trail, but there could be other parameters also like:
2457 * 1. duration of existence of a trail - older the better.
2458 * 2. if the new trail is completely disjoint than the
2459 * other trails, then may be choosing it is better.
2461 * @param finger Finger
2462 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2463 * including the endpoints.
2464 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2465 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2468 select_and_replace_trail (struct FingerInfo *finger,
2469 const struct GNUNET_PeerIdentity *new_trail,
2470 unsigned int new_trail_length,
2471 const struct GNUNET_HashCode *new_trail_id)
2473 struct Trail *current_trail;
2474 unsigned int largest_trail_length;
2475 unsigned int largest_trail_index;
2476 struct Trail_Element *trail_element;
2477 const struct GNUNET_PeerIdentity *next_hop;
2480 largest_trail_length = new_trail_length;
2481 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2483 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2485 for (i = 0; i < finger->trails_count; i++)
2487 current_trail = &finger->trail_list[i];
2488 GNUNET_assert (GNUNET_YES == current_trail->is_present);
2489 if (current_trail->trail_length > largest_trail_length)
2491 largest_trail_length = current_trail->trail_length;
2492 largest_trail_index = i;
2496 /* New trail is not better than existing ones. Send trail teardown. */
2497 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2499 next_hop = GDS_ROUTING_get_next_hop (new_trail_id,
2500 GDS_ROUTING_SRC_TO_DEST);
2501 GDS_ROUTING_remove_trail (new_trail_id);
2502 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2503 GDS_ROUTING_SRC_TO_DEST,
2508 /* Send trail teardown message across the replaced trail. */
2509 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2510 next_hop = GDS_ROUTING_get_next_hop (&replace_trail->trail_id,
2511 GDS_ROUTING_SRC_TO_DEST);
2512 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (&replace_trail->trail_id));
2513 GDS_NEIGHBOURS_send_trail_teardown (&replace_trail->trail_id,
2514 GDS_ROUTING_SRC_TO_DEST,
2517 /* Free the trail. */
2518 while (NULL != (trail_element = replace_trail->trail_head))
2520 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2521 replace_trail->trail_tail,
2523 GNUNET_free_non_null (trail_element);
2526 /* Add new trial at that location. */
2527 replace_trail->is_present = GNUNET_YES;
2528 replace_trail->trail_length = new_trail_length;
2529 replace_trail->trail_id = *new_trail_id;
2531 for (i = 0; i < new_trail_length; i++)
2533 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2534 element->peer = new_trail[i];
2536 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2537 replace_trail->trail_tail,
2540 /* FIXME: URGENT Are we adding the trail back to the list. */
2545 * Check if the new trail to reach to finger is unique or do we already have
2546 * such a trail present for finger.
2547 * @param existing_finger Finger identity
2548 * @param new_trail New trail to reach @a existing_finger
2549 * @param trail_length Total number of peers in new_trail.
2550 * @return #GNUNET_YES if the new trail is unique
2551 * #GNUNET_NO if same trail is already present.
2554 is_new_trail_unique (struct FingerInfo *existing_finger,
2555 const struct GNUNET_PeerIdentity *new_trail,
2556 unsigned int trail_length)
2558 struct Trail *current_trail;
2559 struct Trail_Element *trail_element;
2563 GNUNET_assert (existing_finger->trails_count > 0);
2565 /* Iterate over list of trails. */
2566 for (i = 0; i < existing_finger->trails_count; i++)
2568 current_trail = &(existing_finger->trail_list[i]);
2569 if(GNUNET_NO == current_trail->is_present)
2572 /* New trail and existing trail length are not same. */
2573 if (current_trail->trail_length != trail_length)
2578 trail_element = current_trail->trail_head;
2579 for (j = 0; j < current_trail->trail_length; j++)
2581 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2582 &trail_element->peer))
2586 trail_element = trail_element->next;
2594 * FIXME; In case of multiple trails, we may have a case where a trail from in
2595 * between has been removed, then we should try to find a free slot , not simply
2596 * add a trail at then end of the list.
2597 * Add a new trail at a free slot in trail array of existing finger.
2598 * @param existing_finger Finger
2599 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2600 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2601 * @param new_finger_trail_id Unique identifier of the trail.
2604 add_new_trail (struct FingerInfo *existing_finger,
2605 const struct GNUNET_PeerIdentity *new_trail,
2606 unsigned int new_trail_length,
2607 const struct GNUNET_HashCode *new_trail_id)
2609 struct FriendInfo *friend;
2610 struct Trail *trail;
2614 if (GNUNET_NO == is_new_trail_unique (existing_finger,
2619 for (i = 0; i < existing_finger->trails_count; i++)
2621 if (GNUNET_NO == existing_finger->trail_list[i].is_present)
2628 if (-1 == free_slot)
2631 trail = &existing_finger->trail_list[free_slot];
2632 GNUNET_assert (GNUNET_NO == trail->is_present);
2633 trail->trail_id = *new_trail_id;
2634 trail->trail_length = new_trail_length;
2635 existing_finger->trails_count++;
2636 trail->is_present = GNUNET_YES;
2637 if (0 == new_trail_length)
2639 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2640 &existing_finger->finger_identity);
2644 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2647 GNUNET_assert (NULL != friend);
2648 friend->trails_count++;
2649 for (i = 0; i < new_trail_length; i++)
2651 struct Trail_Element *element;
2653 element = GNUNET_new (struct Trail_Element);
2654 element->peer = new_trail[i];
2655 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2660 existing_finger->trail_list[free_slot].trail_head = trail->trail_head;
2661 existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail;
2662 existing_finger->trail_list[free_slot].trail_length = new_trail_length;
2663 existing_finger->trail_list[free_slot].trail_id = *new_trail_id;
2664 existing_finger->trail_list[free_slot].is_present = GNUNET_YES;
2670 * FIXME; In case of multiple trails, we may have a case where a trail from in
2671 * between has been removed, then we should try to find a free slot , not simply
2672 * add a trail at then end of the list.
2673 * Add a new trail at a free slot in trail array of existing finger.
2674 * @param existing_finger Finger
2675 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2676 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2677 * @param new_finger_trail_id Unique identifier of the trail.
2680 add_new_trail (struct FingerInfo *existing_finger,
2681 const struct GNUNET_PeerIdentity *new_trail,
2682 unsigned int new_trail_length,
2683 const struct GNUNET_HashCode *new_trail_id)
2685 struct Trail *trail;
2686 struct FriendInfo *first_friend;
2690 if (GNUNET_NO == is_new_trail_unique (existing_finger,
2695 index = existing_finger->trails_count;
2696 trail = &existing_finger->trail_list[index];
2697 GNUNET_assert (GNUNET_NO == trail->is_present);
2698 trail->trail_id = *new_trail_id;
2699 trail->trail_length = new_trail_length;
2700 existing_finger->trails_count++;
2701 trail->is_present = GNUNET_YES;
2703 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2704 &existing_finger->finger_identity)));
2705 /* If finger is a friend then we never call this function. */
2706 GNUNET_assert (new_trail_length > 0);
2708 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2710 first_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,
2722 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2723 existing_finger->trail_list[index].trail_head = trail->trail_head;
2724 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2725 existing_finger->trail_list[index].trail_length = new_trail_length;
2726 existing_finger->trail_list[index].trail_id = *new_trail_id;
2727 existing_finger->trail_list[index].is_present = GNUNET_YES;
2732 * Get the next hop to send trail teardown message from routing table and
2733 * then delete the entry from routing table. Send trail teardown message for a
2734 * specific trail of a finger.
2735 * @param finger Finger whose trail is to be removed.
2736 * @param trail List of peers in trail from me to a finger, NOT including
2740 send_trail_teardown (struct FingerInfo *finger,
2741 struct Trail *trail)
2743 struct FriendInfo *friend;
2744 const struct GNUNET_PeerIdentity *next_hop;
2746 next_hop = GDS_ROUTING_get_next_hop (&trail->trail_id,
2747 GDS_ROUTING_SRC_TO_DEST);
2748 if (NULL == next_hop)
2750 // DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d",
2751 // GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length);
2754 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2757 GNUNET_assert(GNUNET_YES == trail->is_present);
2758 if (trail->trail_length > 0)
2760 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2761 &trail->trail_head->peer);
2765 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2766 &finger->finger_identity);
2771 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2773 GNUNET_h2s (&trail->trail_id),
2774 GNUNET_i2s(&my_identity),
2775 trail->trail_length);
2778 if ( (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop,
2780 (0 == trail->trail_length))
2782 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2784 GNUNET_h2s (&trail->trail_id),
2785 GNUNET_i2s (&my_identity),
2786 trail->trail_length);
2789 GNUNET_assert (GNUNET_YES ==
2790 GDS_ROUTING_remove_trail (&trail->trail_id));
2791 friend->trails_count--;
2792 GDS_NEIGHBOURS_send_trail_teardown (&trail->trail_id,
2793 GDS_ROUTING_SRC_TO_DEST,
2799 * Send trail teardown message across all the trails to reach to finger.
2800 * @param finger Finger whose all the trail should be freed.
2803 send_all_finger_trails_teardown (struct FingerInfo *finger)
2805 for (unsigned int i = 0; i < finger->trails_count; i++)
2807 struct Trail *trail;
2809 trail = &finger->trail_list[i];
2810 if (GNUNET_YES == trail->is_present)
2812 send_trail_teardown (finger, trail);
2813 trail->is_present = GNUNET_NO;
2820 * Free a specific trail
2821 * @param trail List of peers to be freed.
2824 free_trail (struct Trail *trail)
2826 struct Trail_Element *trail_element;
2828 while (NULL != (trail_element = trail->trail_head))
2830 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2833 GNUNET_free_non_null (trail_element);
2835 trail->trail_head = NULL;
2836 trail->trail_tail = NULL;
2841 * Free finger and its trail.
2843 * @param finger Finger to be freed.
2844 * @param finger_table_index Index at which finger is stored.
2847 free_finger (struct FingerInfo *finger,
2848 unsigned int finger_table_index)
2850 struct Trail *trail;
2852 for (unsigned int i = 0; i < finger->trails_count; i++)
2854 trail = &finger->trail_list[i];
2855 if (GNUNET_NO == trail->is_present)
2858 if (trail->trail_length > 0)
2860 trail->is_present = GNUNET_NO;
2863 finger->is_present = GNUNET_NO;
2864 memset (&finger_table[finger_table_index],
2866 sizeof (finger_table[finger_table_index]));
2871 * Add a new entry in finger table at finger_table_index.
2872 * In case I am my own finger, then we don't have a trail. In case of a friend,
2873 * we have a trail with unique id and '0' trail length.
2874 * In case a finger is a friend, then increment the trails count of the friend.
2876 * @param finger_identity Peer Identity of new finger
2877 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2878 * @param finger_trail_length Total number of peers in @a finger_trail.
2879 * @param trail_id Unique identifier of the trail.
2880 * @param finger_table_index Index in finger table.
2883 add_new_finger (const struct GNUNET_PeerIdentity *finger_identity,
2884 const struct GNUNET_PeerIdentity *finger_trail,
2885 unsigned int finger_trail_length,
2886 const struct GNUNET_HashCode *trail_id,
2887 unsigned int finger_table_index)
2889 struct FingerInfo *new_entry;
2890 struct FriendInfo *first_trail_hop;
2891 struct Trail *trail;
2894 new_entry = GNUNET_new (struct FingerInfo);
2895 new_entry->finger_identity = *finger_identity;
2896 new_entry->finger_table_index = finger_table_index;
2897 new_entry->is_present = GNUNET_YES;
2899 /* If the new entry is my own identity. */
2900 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2903 new_entry->trails_count = 0;
2904 finger_table[finger_table_index] = *new_entry;
2905 GNUNET_free (new_entry);
2909 /* Finger is a friend. */
2910 if (0 == finger_trail_length)
2912 new_entry->trail_list[0].trail_id = *trail_id;
2913 new_entry->trails_count = 1;
2914 new_entry->trail_list[0].is_present = GNUNET_YES;
2915 new_entry->trail_list[0].trail_length = 0;
2916 new_entry->trail_list[0].trail_head = NULL;
2917 new_entry->trail_list[0].trail_tail = NULL;
2918 finger_table[finger_table_index] = *new_entry;
2919 GNUNET_assert (NULL !=
2921 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2924 first_trail_hop->trails_count++;
2925 GNUNET_free (new_entry);
2929 GNUNET_assert (NULL !=
2931 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2932 &finger_trail[0])));
2933 new_entry->trails_count = 1;
2934 first_trail_hop->trails_count++;
2935 /* Copy the finger trail into trail. */
2936 trail = &new_entry->trail_list[0];
2937 for(i = 0; i < finger_trail_length; i++)
2939 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2941 element->next = NULL;
2942 element->prev = NULL;
2943 element->peer = finger_trail[i];
2944 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2949 /* Add trail to trail list. */
2950 trail->trail_length = finger_trail_length;
2951 trail->trail_id = *trail_id;
2952 trail->is_present = GNUNET_YES;
2953 finger_table[finger_table_index] = *new_entry;
2954 GNUNET_free (new_entry);
2959 * Periodic task to verify current successor. There can be multiple trails to reach
2960 * to successor, choose the shortest one and send verify successor message
2961 * across that trail.
2963 * @param cls closure for this task
2966 send_verify_successor_message (void *cls)
2968 struct FriendInfo *target_friend;
2969 struct Trail *trail;
2970 struct Trail_Element *element;
2971 unsigned int trail_length;
2973 struct FingerInfo *successor;
2975 successor = &finger_table[0];
2977 /* This task will be scheduled when the result for Verify Successor is received. */
2978 send_verify_successor_task = NULL;
2980 /* When verify successor is being called for first time *for current context*
2981 * cls will be NULL. If send_verify_successor_retry_task is not NO_TASK, we
2982 * must cancel the retry task scheduled for verify_successor of previous
2987 /* FIXME: Here we are scheduling a new verify successor task, as we
2988 got a new successor. But a send verify successor task may be in progress.
2989 1. We need to be sure that this is indeed a new successor. As this function
2990 is called even if we add a new trail to reach t old successor.
2991 2. Assuming the new successor is different, then verify successor message
2992 * to old successor may be following stages.
2993 * --> Waiting for verify successor result. Don't wait anymore. there is
2994 * no trail to reach from old successor to me, hence, routing
2996 * --> Waiting for notify confirmation. again don't wait for it. notify
2997 * confirmation will not succeded.
2999 if (send_verify_successor_retry_task != NULL)
3001 /* FIXME: Are we scheduling retry task as soon as we send verify message.
3002 If yes then here before making this task, first check if the message
3003 is for the same peer again. */
3004 struct VerifySuccessorContext *old_ctx =
3005 GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
3006 /* old_ctx must not be NULL, as the retry task had been scheduled */
3007 GNUNET_assert(NULL != old_ctx);
3008 GNUNET_free(old_ctx);
3009 /* FIXME: Why don't we reset the task to NO_TASK here? */
3012 struct VerifySuccessorContext *ctx;
3013 ctx = GNUNET_new (struct VerifySuccessorContext);
3015 ctx->num_retries_scheduled++;
3016 send_verify_successor_retry_task =
3017 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3018 &send_verify_successor_message,
3023 /* This is a retry attempt for verify_successor for a previous context */
3024 struct VerifySuccessorContext *ctx;
3027 ctx->num_retries_scheduled++;
3028 send_verify_successor_retry_task =
3029 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3030 &send_verify_successor_message,
3034 /* Among all the trails to reach to successor, select first one which is present.*/
3035 for (i = 0; i < successor->trails_count; i++)
3037 trail = &successor->trail_list[i];
3038 if (GNUNET_YES == trail->is_present)
3042 /* No valid trail found to reach to successor. */
3043 if (i == successor->trails_count)
3046 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3047 &successor->finger_identity));
3048 /* Trail stored at this index. */
3049 GNUNET_assert (GNUNET_YES == trail->is_present);
3050 if (NULL == GDS_ROUTING_get_next_hop (&trail->trail_id,
3051 GDS_ROUTING_SRC_TO_DEST))
3053 DEBUG (" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
3054 GNUNET_i2s (&my_identity),
3055 GNUNET_h2s (&trail->trail_id),
3060 trail_length = trail->trail_length;
3061 if (trail_length > 0)
3063 /* Copy the trail into peer list. */
3064 struct GNUNET_PeerIdentity peer_list[trail_length];
3066 element = trail->trail_head;
3067 for(i = 0; i < trail_length; i++)
3069 peer_list[i] = element->peer;
3070 element = element->next;
3072 GNUNET_assert (NULL != (target_friend =
3073 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3075 GDS_NEIGHBOURS_send_verify_successor_message (&my_identity,
3076 &successor->finger_identity,
3084 GNUNET_assert (NULL != (target_friend =
3085 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3086 &successor->finger_identity)));
3087 GDS_NEIGHBOURS_send_verify_successor_message (&my_identity,
3088 &successor->finger_identity,
3098 * FIXME: should this be a periodic task, incrementing the search finger index?
3099 * Update the current search finger index.
3100 * @a finger_identity
3101 * @a finger_table_index
3104 update_current_search_finger_index (unsigned int finger_table_index)
3106 struct FingerInfo *successor;
3108 /* FIXME correct this: only move current index periodically */
3109 if (finger_table_index != current_search_finger_index)
3112 successor = &finger_table[0];
3113 GNUNET_assert (GNUNET_YES == successor->is_present);
3115 /* We were looking for immediate successor. */
3116 if (0 == current_search_finger_index)
3118 current_search_finger_index = PREDECESSOR_FINGER_ID;
3119 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3120 &successor->finger_identity))
3122 if (NULL == send_verify_successor_task)
3124 send_verify_successor_task
3125 = GNUNET_SCHEDULER_add_now (&send_verify_successor_message,
3131 current_search_finger_index--;
3136 * Get the least significant bit set in val.
3139 * @return Position of first bit set, 65 in case of error.
3142 find_set_bit (uint64_t val)
3162 return 65; /* Some other bit was set to 1 as well. */
3169 * Calculate finger_table_index from initial 64 bit finger identity value that
3170 * we send in trail setup message.
3171 * @param ultimate_destination_finger_value Value that we calculated from our
3172 * identity and finger_table_index.
3173 * @param is_predecessor Is the entry for predecessor or not?
3174 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3175 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3178 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3179 unsigned int is_predecessor)
3183 unsigned int finger_table_index;
3185 GNUNET_memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3186 my_id64 = GNUNET_ntohll (my_id64);
3188 /* Is this a predecessor finger? */
3189 if (1 == is_predecessor)
3191 diff = my_id64 - ultimate_destination_finger_value;
3193 finger_table_index = PREDECESSOR_FINGER_ID;
3195 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3200 diff = ultimate_destination_finger_value - my_id64;
3201 finger_table_index = find_set_bit (diff);
3203 return finger_table_index;
3208 * Remove finger and its associated data structures from finger table.
3209 * @param existing_finger Finger to be removed which is in finger table.
3210 * @param finger_table_index Index in finger table where @a existing_finger
3214 remove_existing_finger (struct FingerInfo *existing_finger,
3215 unsigned int finger_table_index)
3217 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3219 /* If I am my own finger, then we have no trails. */
3220 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3223 existing_finger->is_present = GNUNET_NO;
3224 memset ((void *)&finger_table[finger_table_index], 0,
3225 sizeof (finger_table[finger_table_index]));
3229 /* For all other fingers, send trail teardown across all the trails to reach
3230 finger, and free the finger. */
3231 send_all_finger_trails_teardown (existing_finger);
3232 free_finger (existing_finger, finger_table_index);
3237 * Check if there is already an entry in finger_table at finger_table_index.
3238 * We get the finger_table_index from 64bit finger value we got from the network.
3239 * -- If yes, then select the closest finger.
3240 * -- If new and existing finger are same, then check if you can store more
3242 * -- If yes then add trail, else keep the best trails to reach to the
3244 * -- If the new finger is closest, remove the existing entry, send trail
3245 * teardown message across all the trails to reach the existing entry.
3246 * Add the new finger.
3247 * -- If new and existing finger are different, and existing finger is closest
3249 * -- Update current_search_finger_index.
3250 * @param finger_identity Peer Identity of new finger
3251 * @param finger_trail Trail to reach the new finger
3252 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3253 * @param is_predecessor Is this entry for predecessor in finger_table?
3254 * @param finger_value 64 bit value of finger identity that we got from network.
3255 * @param finger_trail_id Unique identifier of @finger_trail.
3258 finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
3259 const struct GNUNET_PeerIdentity *finger_trail,
3260 unsigned int finger_trail_length,
3261 unsigned int is_predecessor,
3262 uint64_t finger_value,
3263 const struct GNUNET_HashCode *finger_trail_id)
3265 struct FingerInfo *existing_finger;
3266 const struct GNUNET_PeerIdentity *closest_peer;
3267 struct FingerInfo *successor;
3268 unsigned int finger_table_index;
3270 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3271 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3273 /* Invalid finger_table_index. */
3274 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3276 GNUNET_break_op (0);
3280 /* Check if new entry is same as successor. */
3281 if ((0 != finger_table_index) &&
3282 (PREDECESSOR_FINGER_ID != finger_table_index))
3284 successor = &finger_table[0];
3285 if (GNUNET_NO == successor->is_present)
3287 GNUNET_break (0); //ASSERTION FAILS HERE. FIXME
3290 if (0 == GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3291 &successor->finger_identity))
3293 if (0 == fingers_round_count)
3295 find_finger_trail_task_next_send_time =
3296 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3299 fingers_round_count--;
3300 current_search_finger_index = 0;
3301 GNUNET_STATISTICS_update (GDS_stats,
3303 ("# FINGERS_COUNT"), (int64_t) total_fingers_found,
3305 total_fingers_found = 0;
3309 struct FingerInfo prev_finger;
3310 prev_finger = finger_table[finger_table_index - 1];
3311 if (0 == GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3312 &prev_finger.finger_identity))
3314 current_search_finger_index--;
3319 total_fingers_found++;
3320 existing_finger = &finger_table[finger_table_index];
3322 /* No entry present in finger_table for given finger map index. */
3323 if (GNUNET_NO == existing_finger->is_present)
3325 /* Shorten the trail if possible. */
3326 add_new_finger (finger_identity,
3328 finger_trail_length,
3330 finger_table_index);
3331 update_current_search_finger_index (finger_table_index);
3335 /* If existing entry and finger identity are not same. */
3336 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3339 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3344 /* If the new finger is the closest peer. */
3345 if (0 == GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3348 remove_existing_finger (existing_finger,
3349 finger_table_index);
3350 add_new_finger (finger_identity,
3352 finger_trail_length,
3354 finger_table_index);
3358 /* Existing finger is the closest one. We need to send trail teardown
3359 across the trail setup in routing table of all the peers. */
3360 if (0 != GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3363 if (finger_trail_length > 0)
3364 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3365 GDS_ROUTING_SRC_TO_DEST,
3368 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3369 GDS_ROUTING_SRC_TO_DEST,
3376 /* If both new and existing entry are same as my_identity, then do nothing. */
3377 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3383 /* If there is space to store more trails. */
3384 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3385 add_new_trail (existing_finger,
3387 finger_trail_length,
3390 select_and_replace_trail (existing_finger,
3392 finger_trail_length,
3395 update_current_search_finger_index (finger_table_index);
3401 * Verify validity of P2P put messages.
3403 * @param cls closure
3404 * @param put the message
3405 * @return #GNUNET_OK if the message is well-formed
3408 check_dht_p2p_put (void *cls,
3409 const struct PeerPutMessage *put)
3414 msize = ntohs (put->header.size);
3415 putlen = ntohl (put->put_path_length);
3417 sizeof (struct PeerPutMessage) +
3418 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3420 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3422 GNUNET_break_op (0);
3423 return GNUNET_SYSERR;
3430 * Core handler for P2P put messages.
3432 * @param cls closure
3433 * @param put the message
3436 handle_dht_p2p_put (void *cls,
3437 const struct PeerPutMessage *put)
3439 struct GNUNET_PeerIdentity *put_path;
3440 struct GNUNET_PeerIdentity current_best_known_dest;
3441 struct GNUNET_PeerIdentity best_known_dest;
3442 struct GNUNET_HashCode received_intermediate_trail_id;
3443 struct GNUNET_HashCode intermediate_trail_id;
3444 struct GNUNET_PeerIdentity next_hop;
3445 const struct GNUNET_PeerIdentity *next_routing_hop;
3446 enum GNUNET_DHT_RouteOption options;
3447 struct GNUNET_HashCode test_key;
3448 struct Closest_Peer successor;
3451 uint32_t putlen = ntohl (put->put_path_length);
3452 struct GNUNET_PeerIdentity pp[putlen + 1];
3454 size_t payload_size;
3457 msize = ntohs (put->header.size);
3458 GNUNET_STATISTICS_update (GDS_stats,
3459 gettext_noop ("# Bytes received from other peers"),
3463 current_best_known_dest = put->best_known_destination;
3464 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3465 payload = &put_path[putlen];
3466 options = ntohl (put->options);
3467 received_intermediate_trail_id = put->intermediate_trail_id;
3468 hop_count = ntohl(put->hop_count);
3469 payload_size = msize - (sizeof (struct PeerPutMessage) +
3470 putlen * sizeof (struct GNUNET_PeerIdentity));
3472 switch (GNUNET_BLOCK_get_key (GDS_block_context,
3473 ntohl (put->block_type),
3479 if (0 != memcmp (&test_key,
3481 sizeof (struct GNUNET_HashCode)))
3483 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3484 GNUNET_break_op (0);
3485 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3486 "PUT with key `%s' for block with key %s\n",
3488 GNUNET_h2s_full (&test_key));
3489 GNUNET_free (put_s);
3494 GNUNET_break_op (0);
3497 /* cannot verify, good luck */
3501 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3503 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3504 ntohl (put->block_type),
3505 GNUNET_BLOCK_EO_NONE,
3507 NULL, 0, /* bloom filer */
3508 NULL, 0, /* xquery */
3512 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3513 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3516 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3517 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3518 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3519 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3520 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3521 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3523 GNUNET_break_op (0);
3528 /* Check if you are already a part of put path. */
3530 for (i = 0; i < putlen; i++)
3532 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3540 /* Add yourself to the list. */
3541 //if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3546 putlen * sizeof (struct GNUNET_PeerIdentity));
3547 pp[putlen] = my_identity;
3554 GNUNET_memcpy (&key_value,
3557 key_value = GNUNET_ntohll (key_value);
3558 successor = find_local_best_known_next_hop (key_value,
3559 GDS_FINGER_TYPE_NON_PREDECESSOR);
3560 next_hop = successor.next_hop;
3561 intermediate_trail_id = successor.trail_id;
3562 best_known_dest = successor.best_known_destination;
3564 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest,
3567 next_routing_hop = GDS_ROUTING_get_next_hop (&received_intermediate_trail_id,
3568 GDS_ROUTING_SRC_TO_DEST);
3569 if (NULL != next_routing_hop)
3571 next_hop = *next_routing_hop;
3572 intermediate_trail_id = received_intermediate_trail_id;
3573 best_known_dest = current_best_known_dest;
3577 GDS_CLIENTS_process_put (options,
3578 ntohl (put->block_type),
3580 ntohl (put->desired_replication_level),
3583 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3588 /* I am the final destination */
3589 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3592 DEBUG ("\n PUT_REQUEST_SUCCESSFUL for key = %s",
3593 GNUNET_h2s(&put->key));
3594 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3598 ntohl (put->block_type),
3602 GDS_NEIGHBOURS_send_put (&put->key,
3603 ntohl (put->block_type),
3604 ntohl (put->options),
3605 ntohl (put->desired_replication_level),
3607 intermediate_trail_id,
3612 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3619 * Check integrity of @a get message.
3621 * @param cls closure
3622 * @param get the message
3623 * @return #GNUNET_OK if @a get is well-formed
3626 check_dht_p2p_get (void *cls,
3627 const struct PeerGetMessage *get)
3629 uint32_t get_length;
3632 msize = ntohs (get->header.size);
3633 get_length = ntohl (get->get_path_length);
3635 sizeof (struct PeerGetMessage) +
3636 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3638 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3640 GNUNET_break_op (0);
3641 return GNUNET_SYSERR;
3648 * FIXME: Check for loop in the request. If you already are part of get path,
3649 * then you need to reset the get path length.
3650 * Core handler for p2p get requests.
3652 * @param cls closure
3653 * @param get the message
3656 handle_dht_p2p_get (void *cls,
3657 const struct PeerGetMessage *get)
3659 const struct GNUNET_PeerIdentity *get_path;
3660 struct GNUNET_PeerIdentity best_known_dest;
3661 struct GNUNET_PeerIdentity current_best_known_dest;
3662 struct GNUNET_HashCode intermediate_trail_id;
3663 struct GNUNET_HashCode received_intermediate_trail_id;
3664 struct Closest_Peer successor;
3665 struct GNUNET_PeerIdentity next_hop;
3666 const struct GNUNET_PeerIdentity *next_routing_hop;
3667 uint32_t get_length;
3672 msize = ntohs (get->header.size);
3673 get_length = ntohl (get->get_path_length);
3674 current_best_known_dest = get->best_known_destination;
3675 received_intermediate_trail_id = get->intermediate_trail_id;
3676 get_path = (const struct GNUNET_PeerIdentity *) &get[1];
3677 hop_count = get->hop_count;
3679 GNUNET_STATISTICS_update (GDS_stats,
3680 gettext_noop ("# Bytes received from other peers"),
3683 GNUNET_memcpy (&key_value,
3686 key_value = GNUNET_ntohll (key_value);
3688 /* Check if you are already a part of get path. */
3689 for (unsigned int i = 0; i < get_length; i++)
3691 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3699 /* Add yourself in the get path. */
3700 struct GNUNET_PeerIdentity gp[get_length + 1];
3703 get_length * sizeof (struct GNUNET_PeerIdentity));
3704 gp[get_length] = my_identity;
3705 get_length = get_length + 1;
3706 GDS_CLIENTS_process_get (get->options,
3709 get->desired_replication_level,
3710 get->get_path_length,
3715 successor = find_local_best_known_next_hop (key_value,
3716 GDS_FINGER_TYPE_NON_PREDECESSOR);
3717 next_hop = successor.next_hop;
3718 best_known_dest = successor.best_known_destination;
3719 intermediate_trail_id = successor.trail_id;
3720 /* I am not the final destination. I am part of trail to reach final dest. */
3721 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3723 next_routing_hop = GDS_ROUTING_get_next_hop (&received_intermediate_trail_id,
3724 GDS_ROUTING_SRC_TO_DEST);
3725 if (NULL != next_routing_hop)
3727 next_hop = *next_routing_hop;
3728 best_known_dest = current_best_known_dest;
3729 intermediate_trail_id = received_intermediate_trail_id;
3733 /* I am the final destination. */
3734 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3737 if (1 == get_length)
3739 DEBUG ("\n GET_REQUEST DONE for key = %s",
3740 GNUNET_h2s(&get->key));
3741 GDS_DATACACHE_handle_get (&get->key,
3742 get->block_type, /* FIXME: endianess? */
3754 GDS_DATACACHE_handle_get (&get->key,
3755 get->block_type, /* FIXME: endianess? */
3762 &gp[get_length - 2],
3768 GDS_NEIGHBOURS_send_get (&get->key,
3769 get->block_type, /* FIXME: endianess? */
3771 get->desired_replication_level,
3773 &intermediate_trail_id,
3783 * Check validity of @a get_result message.
3785 * @param cls closure
3786 * @param get_result the message
3787 * @return #GNUNET_OK if @a get_result is well-formed
3790 check_dht_p2p_get_result (void *cls,
3791 const struct PeerGetResultMessage *get_result)
3794 unsigned int getlen;
3795 unsigned int putlen;
3797 msize = ntohs (get_result->header.size);
3798 getlen = ntohl (get_result->get_path_length);
3799 putlen = ntohl (get_result->put_path_length);
3801 sizeof (struct PeerGetResultMessage) +
3802 getlen * sizeof (struct GNUNET_PeerIdentity) +
3803 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3805 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3807 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3809 GNUNET_break_op (0);
3810 return GNUNET_SYSERR;
3817 * Core handler for get result
3819 * @param cls closure
3820 * @param get_result the message
3823 handle_dht_p2p_get_result (void *cls,
3824 const struct PeerGetResultMessage *get_result)
3826 const struct GNUNET_PeerIdentity *get_path;
3827 const struct GNUNET_PeerIdentity *put_path;
3828 const void *payload;
3829 size_t payload_size;
3831 unsigned int getlen;
3832 unsigned int putlen;
3833 int current_path_index;
3835 msize = ntohs (get_result->header.size);
3836 getlen = ntohl (get_result->get_path_length);
3837 putlen = ntohl (get_result->put_path_length);
3838 DEBUG ("GET_RESULT FOR DATA_SIZE = %u\n",
3839 (unsigned int) msize);
3840 GNUNET_STATISTICS_update (GDS_stats,
3841 gettext_noop ("# Bytes received from other peers"),
3844 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3845 get_path = &put_path[putlen];
3846 payload = (const void *) &get_path[getlen];
3847 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3848 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3850 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3853 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
3864 current_path_index = search_my_index (get_path,
3866 if (-1 == current_path_index)
3868 DEBUG ("No entry found in get path.\n");
3872 if ((getlen + 1) == current_path_index)
3874 DEBUG("Present twice in get path. Not allowed. \n");
3878 GDS_NEIGHBOURS_send_get_result (&get_result->key,
3879 get_result->type, /* FIXME: endianess? */
3880 &get_path[current_path_index - 1],
3881 &get_result->querying_peer,
3886 GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
3893 * Find the next hop to pass trail setup message. First find the local best known
3894 * hop from your own identity, friends and finger. If you were part of trail,
3895 * then get the next hop from routing table. Compare next_hop from routing table
3896 * and local best known hop, and return the closest one to final_dest_finger_val
3897 * @param final_dest_finger_val 64 bit value of finger identity
3898 * @param intermediate_trail_id If you are part of trail to reach to some other
3899 * finger, then it is the trail id to reach to
3900 * that finger, else set to 0.
3901 * @param is_predecessor Are we looking for closest successor or predecessor.
3902 * @param source Source of trail setup message.
3903 * @param current_dest In case you are part of trail, then finger to which
3904 * we should forward the message. Else my own identity
3905 * @return Closest Peer for @a final_dest_finger_val
3907 static struct Closest_Peer
3908 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3909 const struct GNUNET_HashCode *intermediate_trail_id,
3910 unsigned int is_predecessor,
3911 const struct GNUNET_PeerIdentity *source,
3912 const struct GNUNET_PeerIdentity *current_dest)
3914 struct Closest_Peer peer;
3916 peer = find_local_best_known_next_hop (final_dest_finger_val,
3919 /* Am I just a part of a trail towards a finger (current_destination)? */
3920 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3922 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3925 const struct GNUNET_PeerIdentity *closest_peer;
3927 /* Select best successor among one found locally and current_destination
3928 * that we got from network.*/
3929 closest_peer = select_closest_peer (&peer.best_known_destination,
3931 final_dest_finger_val,
3934 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3935 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest,
3938 const struct GNUNET_PeerIdentity *next_hop;
3940 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3941 GDS_ROUTING_SRC_TO_DEST);
3942 /* next_hop NULL is a valid case. This intermediate trail id is set by
3943 some other finger, and while this trail setup is in progress, that other
3944 peer might have found a better trail ,and send trail teardown message
3945 across the network. In case we got the trail teardown message first,
3946 then next_hop will be NULL. A possible solution could be to keep track
3947 * of all removed trail id, and be sure that there is no other reason . */
3948 if(NULL != next_hop)
3950 peer.next_hop = *next_hop;
3951 peer.best_known_destination = *current_dest;
3952 peer.trail_id = *intermediate_trail_id;
3961 * Check format of a PeerTrailSetupMessage.
3963 * @param cls closure
3964 * @param trail_setup the message
3965 * @return #GNUNET_OK if @a trail_setup is well-formed
3968 check_dht_p2p_trail_setup (void *cls,
3969 const struct PeerTrailSetupMessage *trail_setup)
3973 msize = ntohs (trail_setup->header.size);
3974 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3975 sizeof (struct GNUNET_PeerIdentity) != 0)
3977 GNUNET_break_op (0);
3978 return GNUNET_SYSERR;
3985 * Core handle for PeerTrailSetupMessage.
3987 * @param cls closure
3988 * @param trail_setup the message
3991 handle_dht_p2p_trail_setup (void *cls,
3992 const struct PeerTrailSetupMessage *trail_setup)
3994 struct FriendInfo *friend = cls;
3995 const struct GNUNET_PeerIdentity *trail_peer_list;
3996 struct GNUNET_PeerIdentity current_dest;
3997 struct FriendInfo *target_friend;
3998 struct GNUNET_PeerIdentity source;
3999 struct GNUNET_HashCode intermediate_trail_id;
4000 struct GNUNET_HashCode trail_id;
4001 unsigned int is_predecessor;
4002 uint32_t trail_length;
4003 uint64_t final_dest_finger_val;
4007 msize = ntohs (trail_setup->header.size);
4008 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4009 sizeof (struct GNUNET_PeerIdentity);
4010 GNUNET_STATISTICS_update (GDS_stats,
4011 gettext_noop ("# Bytes received from other peers"),
4014 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_setup[1];
4015 current_dest = trail_setup->best_known_destination;
4016 trail_id = trail_setup->trail_id;
4017 final_dest_finger_val
4018 = GNUNET_ntohll (trail_setup->final_destination_finger_value);
4019 source = trail_setup->source_peer;
4020 is_predecessor = ntohl (trail_setup->is_predecessor);
4021 intermediate_trail_id = trail_setup->intermediate_trail_id;
4023 /* Did the friend insert its ID in the trail list? */
4024 if ( (trail_length > 0) &&
4025 (0 != memcmp (&trail_peer_list[trail_length-1],
4027 sizeof (struct GNUNET_PeerIdentity))) )
4029 GNUNET_break_op (0);
4033 /* If I was the source and got the message back, then set trail length to 0.*/
4034 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
4040 /* Check if you are present in the trail seen so far? */
4041 for (i = 0; i < trail_length; i++)
4043 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[i],
4046 /* We will add ourself later in code, if NOT destination. */
4052 /* Is my routing table full? */
4053 if (GNUNET_YES == GDS_ROUTING_threshold_reached ())
4056 = (trail_length > 0)
4057 ? GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4058 &trail_peer_list[trail_length - 1])
4059 : GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4061 if (NULL == target_friend)
4063 DEBUG ("\n friend not found");
4067 GDS_NEIGHBOURS_send_trail_rejection (&source,
4068 final_dest_finger_val,
4075 CONGESTION_TIMEOUT);
4079 /* Get the next hop to forward the trail setup request. */
4080 struct Closest_Peer next_peer
4081 = get_local_best_known_next_hop (final_dest_finger_val,
4082 &intermediate_trail_id,
4087 /* Am I the final destination? */
4088 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4091 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&source,
4094 finger_table_add (&my_identity,
4098 final_dest_finger_val,
4104 = (trail_length > 0)
4105 ? GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4106 &trail_peer_list[trail_length-1])
4107 : GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4109 if (NULL == target_friend)
4111 GNUNET_break_op (0);
4114 GDS_ROUTING_add (&trail_id,
4117 GDS_NEIGHBOURS_send_trail_setup_result (&source,
4123 final_dest_finger_val,
4127 /* I'm not the final destination. */
4128 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4129 &next_peer.next_hop);
4130 if (NULL == target_friend)
4132 DEBUG ("\n target friend not found for peer = %s",
4133 GNUNET_i2s(&next_peer.next_hop));
4137 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
4140 /* Add yourself to list of peers. */
4141 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4143 GNUNET_memcpy (peer_list,
4145 trail_length * sizeof (struct GNUNET_PeerIdentity));
4146 peer_list[trail_length] = my_identity;
4147 GDS_NEIGHBOURS_send_trail_setup (&source,
4148 final_dest_finger_val,
4149 &next_peer.best_known_destination,
4155 &next_peer.trail_id);
4158 GDS_NEIGHBOURS_send_trail_setup (&source,
4159 final_dest_finger_val,
4160 &next_peer.best_known_destination,
4166 &next_peer.trail_id);
4171 * Validate format of trail setup result messages.
4174 * @param trail_result the message
4175 * @return #GNUNET_OK if @a trail_result is well-formed
4178 check_dht_p2p_trail_setup_result (void *cls,
4179 const struct PeerTrailSetupResultMessage *trail_result)
4183 msize = ntohs (trail_result->header.size);
4184 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4185 sizeof (struct GNUNET_PeerIdentity) != 0)
4187 GNUNET_break_op (0);
4188 return GNUNET_SYSERR;
4195 * Core handle for p2p trail setup result messages.
4198 * @param trail_result the message
4201 handle_dht_p2p_trail_setup_result (void *cls,
4202 const struct PeerTrailSetupResultMessage *trail_result)
4204 struct FriendInfo *friend = cls;
4205 const struct GNUNET_PeerIdentity *trail_peer_list;
4206 struct GNUNET_PeerIdentity next_hop;
4207 struct FriendInfo *target_friend;
4208 struct GNUNET_PeerIdentity querying_peer;
4209 struct GNUNET_PeerIdentity finger_identity;
4210 uint32_t trail_length;
4211 uint64_t ultimate_destination_finger_value;
4212 uint32_t is_predecessor;
4213 struct GNUNET_HashCode trail_id;
4217 msize = ntohs (trail_result->header.size);
4218 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4219 sizeof (struct GNUNET_PeerIdentity);
4221 GNUNET_STATISTICS_update (GDS_stats,
4222 gettext_noop ("# Bytes received from other peers"),
4226 is_predecessor = ntohl (trail_result->is_predecessor);
4227 querying_peer = trail_result->querying_peer;
4228 finger_identity = trail_result->finger_identity;
4229 trail_id = trail_result->trail_id;
4230 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4231 ultimate_destination_finger_value
4232 = GNUNET_ntohll (trail_result->ultimate_destination_finger_value);
4234 /* Am I the one who initiated the query? */
4235 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer,
4238 /* Check that you got the message from the correct peer. */
4239 if (trail_length > 0)
4241 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4246 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4249 GDS_ROUTING_add (&trail_id,
4252 finger_table_add (&finger_identity,
4256 ultimate_destination_finger_value,
4261 /* Get my location in the trail. */
4262 my_index = search_my_index (trail_peer_list,
4266 DEBUG ("Not found in trail\n");
4271 if ((trail_length + 1) == my_index)
4273 DEBUG ("Found twice in trail.\n");
4278 //TODO; Refactor code here and above to check if sender peer is correct
4281 if (trail_length > 1)
4282 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4285 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4287 next_hop = trail_result->querying_peer;
4291 if (my_index == trail_length - 1)
4294 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4299 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4301 next_hop = trail_peer_list[my_index - 1];
4304 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4306 if (NULL == target_friend)
4308 GNUNET_break_op (0);
4311 GDS_ROUTING_add (&trail_id,
4314 GDS_NEIGHBOURS_send_trail_setup_result (&querying_peer,
4320 ultimate_destination_finger_value,
4328 * @param trail Trail to be inverted
4329 * @param trail_length Total number of peers in the trail.
4330 * @return Updated trail
4332 static struct GNUNET_PeerIdentity *
4333 invert_trail (const struct GNUNET_PeerIdentity *trail,
4334 unsigned int trail_length)
4338 struct GNUNET_PeerIdentity *inverted_trail;
4340 inverted_trail = GNUNET_new_array (trail_length,
4341 struct GNUNET_PeerIdentity);
4343 j = trail_length - 1;
4344 while (i < trail_length)
4346 inverted_trail[i] = trail[j];
4351 GNUNET_assert (NULL !=
4352 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4353 &inverted_trail[0]));
4354 return inverted_trail;
4359 * Return the shortest trail among all the trails to reach to finger from me.
4361 * @param finger Finger
4362 * @param shortest_trail_length[out] Trail length of shortest trail from me
4364 * @return Shortest trail.
4366 static struct GNUNET_PeerIdentity *
4367 get_shortest_trail (struct FingerInfo *finger,
4368 unsigned int *trail_length)
4370 struct Trail *trail;
4371 unsigned int flag = 0;
4372 unsigned int shortest_trail_index = 0;
4373 int shortest_trail_length = -1;
4374 struct Trail_Element *trail_element;
4375 struct GNUNET_PeerIdentity *trail_list;
4378 /* Get the shortest trail to reach to current successor. */
4379 for (i = 0; i < finger->trails_count; i++)
4381 trail = &finger->trail_list[i];
4385 shortest_trail_index = i;
4386 shortest_trail_length = trail->trail_length;
4391 if (shortest_trail_length > trail->trail_length)
4393 shortest_trail_index = i;
4394 shortest_trail_length = trail->trail_length;
4399 /* Copy the shortest trail and return. */
4400 trail = &finger->trail_list[shortest_trail_index];
4401 trail_element = trail->trail_head;
4403 trail_list = GNUNET_new_array (shortest_trail_length,
4404 struct GNUNET_PeerIdentity);
4406 for (i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4408 trail_list[i] = trail_element->peer;
4411 GNUNET_assert(shortest_trail_length != -1);
4413 *trail_length = shortest_trail_length;
4419 * Check if @a trail_1 and @a trail_2 have any common element. If yes then join
4420 * them at common element. @a trail_1 always preceeds @a trail_2 in joined trail.
4422 * @param trail_1 Trail from source to me, NOT including endpoints.
4423 * @param trail_1_len Total number of peers @a trail_1
4424 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4425 * @param trail_2_len Total number of peers @a trail_2
4426 * @param joined_trail_len Total number of peers in combined trail of @a trail_1
4428 * @return Joined trail.
4430 static struct GNUNET_PeerIdentity *
4431 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4432 unsigned int trail_1_len,
4433 const struct GNUNET_PeerIdentity *trail_2,
4434 unsigned int trail_2_len,
4435 unsigned int *joined_trail_len)
4437 struct GNUNET_PeerIdentity *joined_trail;
4442 for (i = 0; i < trail_1_len; i++)
4444 for (j = 0; j < trail_2_len; j++)
4446 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],
4450 *joined_trail_len = i + (trail_2_len - j);
4451 joined_trail = GNUNET_new_array (*joined_trail_len,
4452 struct GNUNET_PeerIdentity);
4455 /* Copy all the elements from 0 to i into joined_trail. */
4456 for(k = 0; k < ( i+1); k++)
4458 joined_trail[k] = trail_1[k];
4461 /* Increment j as entry stored is same as entry stored at i*/
4464 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4465 while(k <= (*joined_trail_len - 1))
4467 joined_trail[k] = trail_2[j];
4472 return joined_trail;
4476 /* Here you should join the trails. */
4477 *joined_trail_len = trail_1_len + trail_2_len + 1;
4478 joined_trail = GNUNET_new_array (*joined_trail_len,
4479 struct GNUNET_PeerIdentity);
4482 for(i = 0; i < trail_1_len;i++)
4484 joined_trail[i] = trail_1[i];
4487 joined_trail[i] = my_identity;
4490 for (j = 0; i < *joined_trail_len; i++,j++)
4492 joined_trail[i] = trail_2[j];
4495 return joined_trail;
4500 * Return the trail from source to my current predecessor. Check if source
4501 * is already part of the this trail, if yes then return the shorten trail.
4503 * @param current_trail Trail from source to me, NOT including the endpoints.
4504 * @param current_trail_length Number of peers in @a current_trail.
4505 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4506 * source to my predecessor, NOT including
4508 * @return Trail from source to my predecessor.
4510 static struct GNUNET_PeerIdentity *
4511 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4512 const struct GNUNET_PeerIdentity *trail_src_to_me,
4513 unsigned int trail_src_to_me_len,
4514 unsigned int *trail_src_to_curr_pred_length)
4516 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4517 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4518 unsigned int trail_me_to_curr_pred_length;
4519 struct FingerInfo *current_predecessor;
4524 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4526 /* Check if trail_src_to_me contains current_predecessor. */
4527 for (i = 0; i < trail_src_to_me_len; i++)
4529 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4530 ¤t_predecessor->finger_identity))
4534 *trail_src_to_curr_pred_length = i;
4539 trail_src_to_curr_pred = GNUNET_new_array (*trail_src_to_curr_pred_length,
4540 struct GNUNET_PeerIdentity);
4541 for (j = 0; j < i; j++)
4542 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4543 return trail_src_to_curr_pred;
4547 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4548 &trail_me_to_curr_pred_length);
4550 /* Check if trail contains the source_peer. */
4551 for (i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4553 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4554 &trail_me_to_curr_pred[i]))
4557 /* Source is NOT part of trail. */
4560 /* Source is the last element in the trail to reach to my pred.
4561 Source is direct friend of the pred. */
4562 if (trail_me_to_curr_pred_length == i)
4564 *trail_src_to_curr_pred_length = 0;
4565 GNUNET_free_non_null (trail_me_to_curr_pred);
4569 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4570 trail_src_to_curr_pred = GNUNET_new_array (*trail_src_to_curr_pred_length,
4571 struct GNUNET_PeerIdentity);
4574 for (j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4575 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4576 GNUNET_free_non_null (trail_me_to_curr_pred);
4577 return trail_src_to_curr_pred;
4580 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4581 trail_src_to_me_len,
4582 trail_me_to_curr_pred,
4583 trail_me_to_curr_pred_length,
4585 *trail_src_to_curr_pred_length = len;
4586 GNUNET_free_non_null(trail_me_to_curr_pred);
4587 return trail_src_to_curr_pred;
4592 * Add finger as your predecessor. To add, first generate a new trail id, invert
4593 * the trail to get the trail from me to finger, add an entry in your routing
4594 * table, send add trail message to peers which are part of trail from me to
4595 * finger and add finger in finger table.
4599 * @param trail_length
4602 update_predecessor (const struct GNUNET_PeerIdentity *finger,
4603 const struct GNUNET_PeerIdentity *trail,
4604 unsigned int trail_length)
4606 struct GNUNET_HashCode trail_to_new_predecessor_id;
4607 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4608 struct FriendInfo *target_friend;
4610 /* Generate trail id for trail from me to new predecessor = finger. */
4611 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4612 &trail_to_new_predecessor_id,
4613 sizeof (trail_to_new_predecessor_id));
4615 if (0 == trail_length)
4617 trail_to_new_predecessor = NULL;
4618 GDS_ROUTING_add (&trail_to_new_predecessor_id,
4621 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4623 if (NULL == target_friend)
4631 /* Invert the trail to get the trail from me to finger, NOT including the
4633 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4634 &trail[trail_length-1]));
4635 trail_to_new_predecessor = invert_trail (trail,
4638 /* Add an entry in your routing table. */
4639 GDS_ROUTING_add (&trail_to_new_predecessor_id,
4641 &trail_to_new_predecessor[0]);
4643 GNUNET_assert (NULL != (target_friend =
4644 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4645 &trail_to_new_predecessor[0])));
4648 /* Add entry in routing table of all peers that are part of trail from me
4649 to finger, including finger. */
4650 GDS_NEIGHBOURS_send_add_trail (&my_identity,
4652 &trail_to_new_predecessor_id,
4653 trail_to_new_predecessor,
4657 add_new_finger (finger,
4658 trail_to_new_predecessor,
4660 &trail_to_new_predecessor_id,
4661 PREDECESSOR_FINGER_ID);
4662 GNUNET_free_non_null (trail_to_new_predecessor);
4667 * Check if you already have a predecessor. If not then add finger as your
4668 * predecessor. If you have predecessor, then compare two peer identites.
4669 * If finger is correct predecessor, then remove the old entry, add finger in
4670 * finger table and send add_trail message to add the trail in the routing
4671 * table of all peers which are part of trail to reach from me to finger.
4672 * @param finger New peer which may be our predecessor.
4673 * @param trail List of peers to reach from @finger to me.
4674 * @param trail_length Total number of peer in @a trail.
4677 compare_and_update_predecessor (const struct GNUNET_PeerIdentity *finger,
4678 const struct GNUNET_PeerIdentity *trail,
4679 unsigned int trail_length)
4681 struct FingerInfo *current_predecessor;
4682 const struct GNUNET_PeerIdentity *closest_peer;
4683 uint64_t predecessor_value;
4684 unsigned int is_predecessor = 1;
4686 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4687 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (finger,
4690 /* No predecessor. Add finger as your predecessor. */
4691 if (GNUNET_NO == current_predecessor->is_present)
4693 update_predecessor (finger,
4699 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4705 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4706 closest_peer = select_closest_peer (finger,
4707 ¤t_predecessor->finger_identity,
4711 /* Finger is the closest predecessor. Remove the existing one and add the new
4713 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4716 remove_existing_finger (current_predecessor,
4717 PREDECESSOR_FINGER_ID);
4718 update_predecessor (finger,
4727 * Check format of a p2p verify successor messages.
4729 * @param cls closure
4730 * @param vsm the message
4731 * @return #GNUNET_OK if @a vsm is well-formed
4734 check_dht_p2p_verify_successor (void *cls,
4735 const struct PeerVerifySuccessorMessage *vsm)
4739 msize = ntohs (vsm->header.size);
4740 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4741 sizeof (struct GNUNET_PeerIdentity) != 0)
4743 GNUNET_break_op (0);
4744 return GNUNET_SYSERR;
4751 * Core handle for p2p verify successor messages.
4753 * @param cls closure
4754 * @param vsm the message
4757 handle_dht_p2p_verify_successor (void *cls,
4758 const struct PeerVerifySuccessorMessage *vsm)
4760 struct FriendInfo *friend = cls;
4761 struct GNUNET_HashCode trail_id;
4762 struct GNUNET_PeerIdentity successor;
4763 struct GNUNET_PeerIdentity source_peer;
4764 struct GNUNET_PeerIdentity *trail;
4765 const struct GNUNET_PeerIdentity *next_hop;
4766 struct FingerInfo current_predecessor;
4767 struct FriendInfo *target_friend;
4768 unsigned int trail_src_to_curr_pred_len = 0;
4769 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4770 unsigned int trail_length;
4773 msize = ntohs (vsm->header.size);
4774 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4775 sizeof (struct GNUNET_PeerIdentity);
4776 GNUNET_STATISTICS_update (GDS_stats,
4777 gettext_noop ("# Bytes received from other peers"),
4781 trail_id = vsm->trail_id;
4782 source_peer = vsm->source_peer;
4783 successor = vsm->successor;
4784 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4786 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4788 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor,
4791 next_hop = GDS_ROUTING_get_next_hop (&trail_id,
4792 GDS_ROUTING_SRC_TO_DEST);
4793 if (NULL == next_hop)
4796 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4798 if (NULL == target_friend)
4803 GDS_NEIGHBOURS_send_verify_successor_message (&source_peer,
4812 /* I am the destination of this message. */
4813 /* Check if the source_peer could be our predecessor and if yes then update
4815 compare_and_update_predecessor (&source_peer,
4818 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4820 /* Is source of this message NOT my predecessor. */
4821 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4824 trail_src_to_curr_pred
4825 = get_trail_src_to_curr_pred (source_peer,
4828 &trail_src_to_curr_pred_len);
4832 trail_src_to_curr_pred_len = trail_length;
4833 trail_src_to_curr_pred = GNUNET_new_array (trail_src_to_curr_pred_len,
4834 struct GNUNET_PeerIdentity);
4836 for (unsigned int i = 0; i < trail_src_to_curr_pred_len; i++)
4838 trail_src_to_curr_pred[i] = trail[i];
4842 GNUNET_assert (NULL !=
4844 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4846 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
4848 ¤t_predecessor.finger_identity,
4850 trail_src_to_curr_pred,
4851 trail_src_to_curr_pred_len,
4852 GDS_ROUTING_DEST_TO_SRC,
4854 GNUNET_free_non_null (trail_src_to_curr_pred);
4859 * If the trail from me to my probable successor contains a friend not
4860 * at index 0, then we can shorten the trail.
4862 * @param probable_successor Peer which is our probable successor
4863 * @param trail_me_to_probable_successor Peers in path from me to my probable
4864 * successor, NOT including the endpoints.
4865 * @param trail_me_to_probable_successor_len Total number of peers in
4866 * @a trail_me_to_probable_succesor.
4867 * @return Updated trail, if any friend found.
4868 * Else the trail_me_to_probable_successor.
4870 const struct GNUNET_PeerIdentity *
4871 check_trail_me_to_probable_succ (const struct GNUNET_PeerIdentity *probable_successor,
4872 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4873 unsigned int trail_me_to_probable_successor_len,
4874 unsigned int *trail_to_new_successor_length)
4878 struct GNUNET_PeerIdentity *trail_to_new_successor;
4880 /* Probable successor is a friend */
4881 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4882 probable_successor))
4884 trail_to_new_successor = NULL;
4885 *trail_to_new_successor_length = 0;
4886 return trail_to_new_successor;
4889 /* Is there any friend of yours in this trail. */
4890 if (trail_me_to_probable_successor_len > 1)
4892 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4894 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4895 &trail_me_to_probable_successor[i]))
4898 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4899 trail_to_new_successor = GNUNET_new_array (*trail_to_new_successor_length,
4900 struct GNUNET_PeerIdentity);
4901 for (j = 0; j < *trail_to_new_successor_length; i++,j++)
4903 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4906 return trail_to_new_successor;
4910 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4911 return trail_me_to_probable_successor;
4916 struct SendNotifyContext
4918 struct GNUNET_PeerIdentity source_peer;
4919 struct GNUNET_PeerIdentity successor;
4920 struct GNUNET_PeerIdentity *successor_trail;
4921 unsigned int successor_trail_length;
4922 struct GNUNET_HashCode succesor_trail_id;
4923 struct FriendInfo *target_friend;
4924 unsigned int num_retries_scheduled;
4929 send_notify_new_successor (void *cls);
4933 * Check if the peer which sent us verify successor result message is still ours
4934 * successor or not. If not, then compare existing successor and probable successor.
4935 * In case probable successor is the correct successor, remove the existing
4936 * successor. Add probable successor as new successor. Send notify new successor
4937 * message to new successor.
4938 * @param curr_succ Peer to which we sent the verify successor message. It may
4939 * or may not be our real current successor, as we may have few iterations of
4940 * find finger trail task.
4941 * @param probable_successor Peer which should be our successor accroding to @a
4943 * @param trail List of peers to reach from me to @a probable successor, NOT including
4945 * @param trail_length Total number of peers in @a trail.
4948 compare_and_update_successor (const struct GNUNET_PeerIdentity *curr_succ,
4949 const struct GNUNET_PeerIdentity *probable_successor,
4950 const struct GNUNET_PeerIdentity *trail,
4951 unsigned int trail_length)
4953 struct FingerInfo *current_successor;
4954 const struct GNUNET_PeerIdentity *closest_peer;
4955 struct GNUNET_HashCode trail_id;
4956 const struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4957 struct FriendInfo *target_friend;
4958 unsigned int trail_me_to_probable_succ_len;
4959 unsigned int is_predecessor = 0;
4960 uint64_t successor_value;
4961 struct SendNotifyContext *notify_ctx;
4963 current_successor = &finger_table[0];
4964 successor_value = compute_finger_identity_value(0);
4966 /* If probable successor is same as current_successor, do nothing. */
4967 if(0 == GNUNET_CRYPTO_cmp_peer_identity (probable_successor,
4968 ¤t_successor->finger_identity))
4970 if ((NULL != GDS_stats))
4976 GNUNET_memcpy (&my_id, &my_identity, sizeof(uint64_t));
4977 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4978 GNUNET_memcpy (&succ,
4979 ¤t_successor->finger_identity,
4981 succ = GNUNET_ntohll(succ);
4982 GNUNET_asprintf (&key,
4985 GNUNET_free (my_id_str);
4987 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4990 if (send_verify_successor_task == NULL)
4991 send_verify_successor_task =
4992 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
4993 &send_verify_successor_message,
4997 closest_peer = select_closest_peer (probable_successor,
4998 ¤t_successor->finger_identity,
5002 /* If the current_successor in the finger table is closest, then do nothing. */
5003 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
5004 ¤t_successor->finger_identity))
5006 //FIXME: Is this a good place to return the stats.
5007 if ((NULL != GDS_stats))
5013 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5014 GNUNET_memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5015 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5016 GNUNET_free (my_id_str);
5017 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5021 if(0 == successor_times)
5023 // successor_times = 3;
5024 verify_successor_next_send_time =
5025 GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time);
5031 if (send_verify_successor_task == NULL)
5032 send_verify_successor_task =
5033 GNUNET_SCHEDULER_add_delayed (verify_successor_next_send_time,
5034 &send_verify_successor_message,
5039 /* Probable successor is the closest peer.*/
5040 if(trail_length > 0)
5042 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5047 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5048 probable_successor));
5051 trail_me_to_probable_succ_len = 0;
5052 trail_me_to_probable_succ = check_trail_me_to_probable_succ (probable_successor,
5055 &trail_me_to_probable_succ_len);
5057 /* Remove the existing successor. */
5058 remove_existing_finger (current_successor, 0);
5059 /* Generate a new trail id to reach to your new successor. */
5060 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5064 if (trail_me_to_probable_succ_len > 0)
5066 GDS_ROUTING_add (&trail_id,
5068 &trail_me_to_probable_succ[0]);
5069 GNUNET_assert (NULL !=
5071 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5072 &trail_me_to_probable_succ[0])));
5076 GDS_ROUTING_add (&trail_id,
5078 probable_successor);
5079 GNUNET_assert (NULL !=
5081 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5082 probable_successor)));
5085 add_new_finger (probable_successor,
5086 trail_me_to_probable_succ,
5087 trail_me_to_probable_succ_len,
5091 notify_ctx = GNUNET_new (struct SendNotifyContext);
5093 notify_ctx->source_peer = my_identity;
5094 notify_ctx->successor = *probable_successor;
5095 notify_ctx->successor_trail = GNUNET_new_array (trail_me_to_probable_succ_len,
5096 struct GNUNET_PeerIdentity);
5097 GNUNET_memcpy (notify_ctx->successor_trail,
5098 trail_me_to_probable_succ,
5099 sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5100 notify_ctx->successor_trail_length = trail_me_to_probable_succ_len;
5101 notify_ctx->succesor_trail_id = trail_id;
5102 notify_ctx->target_friend = target_friend;
5103 notify_ctx->num_retries_scheduled = 0;
5105 // TODO: Check if we should verify before schedule if already scheduled.
5106 GNUNET_SCHEDULER_add_now (&send_notify_new_successor,
5112 send_notify_new_successor (void *cls)
5114 struct SendNotifyContext *ctx = cls;
5116 GDS_NEIGHBOURS_send_notify_new_successor (&ctx->source_peer,
5118 ctx->successor_trail,
5119 ctx->successor_trail_length,
5120 &ctx->succesor_trail_id,
5121 ctx->target_friend);
5123 if ( (0 == ctx->num_retries_scheduled) &&
5124 (send_notify_new_successor_retry_task != NULL) )
5126 // Result from previous notify successos hasn't arrived, so the retry task
5127 // hasn't been cancelled! Already a new notify successor must be called.
5128 // We will cancel the retry request.
5129 struct SendNotifyContext *old_notify_ctx;
5131 old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5132 GNUNET_free (old_notify_ctx->successor_trail);
5133 GNUNET_free (old_notify_ctx);
5134 send_notify_new_successor_retry_task = NULL;
5137 ctx->num_retries_scheduled++;
5138 send_notify_new_successor_retry_task
5139 = GNUNET_SCHEDULER_add_delayed (notify_successor_retry_time,
5140 &send_notify_new_successor,
5146 * Check integrity of verify successor result messages.
5148 * @param cls closure
5149 * @param vsrm the message
5150 * @return #GNUNET_OK if @a vrsm is well-formed
5153 check_dht_p2p_verify_successor_result (void *cls,
5154 const struct PeerVerifySuccessorResultMessage *vsrm)
5158 msize = ntohs (vsrm->header.size);
5159 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5160 sizeof (struct GNUNET_PeerIdentity) != 0)
5162 GNUNET_break_op (0);
5163 return GNUNET_SYSERR;
5170 * Core handle for p2p verify successor result messages.
5172 * @param cls closure
5173 * @param vsrm the message
5176 handle_dht_p2p_verify_successor_result (void *cls,
5177 const struct PeerVerifySuccessorResultMessage *vsrm)
5179 enum GDS_ROUTING_trail_direction trail_direction;
5180 struct GNUNET_PeerIdentity querying_peer;
5181 struct GNUNET_HashCode trail_id;
5182 const struct GNUNET_PeerIdentity *next_hop;
5183 struct FriendInfo *target_friend;
5184 struct GNUNET_PeerIdentity probable_successor;
5185 struct GNUNET_PeerIdentity current_successor;
5186 const struct GNUNET_PeerIdentity *trail;
5187 unsigned int trail_length;
5190 msize = ntohs (vsrm->header.size);
5191 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))
5192 / sizeof (struct GNUNET_PeerIdentity);
5194 GNUNET_STATISTICS_update (GDS_stats,
5195 gettext_noop ("# Bytes received from other peers"),
5199 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5200 querying_peer = vsrm->querying_peer;
5201 trail_direction = ntohl (vsrm->trail_direction);
5202 trail_id = vsrm->trail_id;
5203 probable_successor = vsrm->probable_successor;
5204 current_successor = vsrm->current_successor;
5206 /* Am I the querying_peer? */
5207 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer,
5210 /* Cancel Retry Task */
5211 if (NULL != send_verify_successor_retry_task)
5213 struct VerifySuccessorContext *ctx;
5215 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
5217 send_verify_successor_retry_task = NULL;
5219 compare_and_update_successor (¤t_successor,
5220 &probable_successor,
5226 /*If you are not the querying peer then pass on the message */
5227 if(NULL == (next_hop =
5228 GDS_ROUTING_get_next_hop (&trail_id,
5231 /* Here it may happen that source peer has found a new successor, and removed
5232 the trail, Hence no entry found in the routing table. Fail silently.*/
5233 DEBUG (" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
5234 GNUNET_i2s (&my_identity),
5235 GNUNET_h2s (&trail_id),
5240 if (NULL == (target_friend =
5241 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5246 GDS_NEIGHBOURS_send_verify_successor_result (&querying_peer,
5247 &vsrm->current_successor,
5248 &probable_successor,
5258 * Check integrity of p2p notify new successor messages.
5260 * @param cls closure
5261 * @param nsm the message
5262 * @return #GNUNET_OK if @a nsm is well-formed
5265 check_dht_p2p_notify_new_successor (void *cls,
5266 const struct PeerNotifyNewSuccessorMessage *nsm)
5270 msize = ntohs (nsm->header.size);
5271 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5272 sizeof (struct GNUNET_PeerIdentity) != 0)
5274 GNUNET_break_op (0);
5275 return GNUNET_SYSERR;
5282 * Core handle for p2p notify new successor messages.
5284 * @param cls closure
5285 * @param nsm the message
5288 handle_dht_p2p_notify_new_successor (void *cls,
5289 const struct PeerNotifyNewSuccessorMessage *nsm)
5291 struct FriendInfo *friend = cls;
5292 const struct GNUNET_PeerIdentity *trail;
5293 struct GNUNET_PeerIdentity source;
5294 struct GNUNET_PeerIdentity new_successor;
5295 struct GNUNET_HashCode trail_id;
5296 struct GNUNET_PeerIdentity next_hop;
5297 struct FriendInfo *target_friend;
5300 uint32_t trail_length;
5302 msize = ntohs (nsm->header.size);
5303 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5304 sizeof (struct GNUNET_PeerIdentity);
5305 GNUNET_STATISTICS_update (GDS_stats,
5306 gettext_noop ("# Bytes received from other peers"),
5309 trail = (const struct GNUNET_PeerIdentity *) &nsm[1];
5310 source = nsm->source_peer;
5311 new_successor = nsm->new_successor;
5312 trail_id = nsm->trail_id;
5314 /* I am the new_successor to source_peer. */
5315 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
5318 if (trail_length > 0)
5319 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail[trail_length - 1],
5322 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&source,
5325 compare_and_update_predecessor (&source,
5328 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5330 GNUNET_assert (NULL != target_friend);
5331 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (&trail_id,
5332 GDS_ROUTING_DEST_TO_SRC,
5337 GNUNET_assert(trail_length > 0);
5338 /* I am part of trail to reach to successor. */
5339 my_index = search_my_index (trail, trail_length);
5342 DEBUG ("No entry found in trail\n");
5343 GNUNET_break_op (0);
5346 if((trail_length + 1) == my_index)
5348 DEBUG ("Found twice in trail.\n");
5349 GNUNET_break_op (0);
5352 if ((trail_length-1) == my_index)
5353 next_hop = new_successor;
5355 next_hop = trail[my_index + 1];
5357 GDS_ROUTING_add (&trail_id,
5360 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5362 if (NULL == target_friend)
5367 GDS_NEIGHBOURS_send_notify_new_successor (&source,
5377 * Core handler for P2P notify successor message
5379 * @param cls closure
5380 * @param notify_confirmation the message
5383 handle_dht_p2p_notify_succ_confirmation (void *cls,
5384 const struct PeerNotifyConfirmationMessage *notify_confirmation)
5386 enum GDS_ROUTING_trail_direction trail_direction;
5387 struct GNUNET_HashCode trail_id;
5388 struct FriendInfo *target_friend;
5389 const struct GNUNET_PeerIdentity *next_hop;
5391 GNUNET_STATISTICS_update (GDS_stats,
5392 gettext_noop ("# Bytes received from other peers"),
5393 ntohs (notify_confirmation->header.size),
5395 trail_direction = ntohl (notify_confirmation->trail_direction);
5396 trail_id = notify_confirmation->trail_id;
5398 next_hop = GDS_ROUTING_get_next_hop (&trail_id,
5400 if (NULL == next_hop)
5402 /* The source of notify new successor, might have found even a better
5403 successor. In that case it send a trail teardown message, and hence,
5404 the next hop is NULL. */
5405 //Fixme: Add some print to confirm the above theory.
5409 /* I peer which sent the notify successor message to the successor. */
5410 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5414 * Schedule another round of verify sucessor with your current successor
5415 * which may or may not be source of this message. This message is used
5416 * only to ensure that we have a path setup to reach to our successor.
5419 // TODO: cancel schedule of notify_successor_retry_task
5420 if (send_notify_new_successor_retry_task != NULL)
5422 struct SendNotifyContext *notify_ctx;
5423 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5424 GNUNET_free (notify_ctx->successor_trail);
5425 GNUNET_free (notify_ctx);
5426 send_notify_new_successor_retry_task = NULL;
5428 if (send_verify_successor_task == NULL)
5430 verify_successor_next_send_time.rel_value_us =
5431 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5432 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5433 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5434 send_verify_successor_task
5435 = GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5436 &send_verify_successor_message,
5442 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5444 if (NULL == target_friend)
5446 DEBUG ("\n friend not found, line number = %d",
5450 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (&trail_id,
5451 GDS_ROUTING_DEST_TO_SRC,
5458 * Check integrity of P2P trail rejection message
5460 * @param cls closure
5461 * @param trail_rejection the message
5462 * @return #GNUNET_OK if @a trail_rejection is well-formed
5465 check_dht_p2p_trail_setup_rejection (void *cls,
5466 const struct PeerTrailRejectionMessage *trail_rejection)
5470 msize = ntohs (trail_rejection->header.size);
5471 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5472 sizeof (struct GNUNET_PeerIdentity) != 0)
5474 GNUNET_break_op (0);
5475 return GNUNET_SYSERR;
5482 * Core handler for P2P trail rejection message
5484 * @param cls closure
5485 * @param trail_rejection the message
5488 handle_dht_p2p_trail_setup_rejection (void *cls,
5489 const struct PeerTrailRejectionMessage *trail_rejection)
5491 struct FriendInfo *friend = cls;
5492 unsigned int trail_length;
5493 const struct GNUNET_PeerIdentity *trail_peer_list;
5494 struct FriendInfo *target_friend;
5495 struct GNUNET_TIME_Relative congestion_timeout;
5496 struct GNUNET_HashCode trail_id;
5497 struct GNUNET_PeerIdentity next_peer;
5498 struct GNUNET_PeerIdentity source;
5499 uint64_t ultimate_destination_finger_value;
5500 unsigned int is_predecessor;
5501 struct Closest_Peer successor;
5504 msize = ntohs (trail_rejection->header.size);
5505 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5506 sizeof (struct GNUNET_PeerIdentity);
5507 GNUNET_STATISTICS_update (GDS_stats,
5508 gettext_noop ("# Bytes received from other peers"),
5512 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_rejection[1];
5513 is_predecessor = ntohl (trail_rejection->is_predecessor);
5514 congestion_timeout = trail_rejection->congestion_time;
5515 source = trail_rejection->source_peer;
5516 trail_id = trail_rejection->trail_id;
5517 ultimate_destination_finger_value
5518 = GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5519 /* First set the congestion time of the friend that sent you this message. */
5520 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5522 if (NULL == target_friend)
5524 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5528 target_friend->congestion_timestamp
5529 = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5530 congestion_timeout);
5532 /* I am the source peer which wants to setup the trail. Do nothing.
5533 * send_find_finger_trail_task is scheduled periodically.*/
5534 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5537 /* If I am congested then pass this message to peer before me in trail. */
5538 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
5540 /* First remove yourself from the trail. */
5541 unsigned int new_trail_length = trail_length - 1;
5542 struct GNUNET_PeerIdentity trail[new_trail_length];
5544 GNUNET_memcpy (trail,
5546 new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5547 if (0 == trail_length)
5550 next_peer = trail[new_trail_length-1];
5553 = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5555 if (NULL == target_friend)
5557 DEBUG ("\nLINE = %d ,No friend found.",
5562 GDS_NEIGHBOURS_send_trail_rejection (&source,
5563 ultimate_destination_finger_value,
5570 CONGESTION_TIMEOUT);
5574 successor = find_local_best_known_next_hop (ultimate_destination_finger_value,
5577 /* Am I the final destination? */
5578 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5581 /*Here you are already part of trail. Copy the trail removing yourself. */
5582 unsigned int new_trail_length = trail_length - 1;
5583 struct GNUNET_PeerIdentity trail[new_trail_length];
5585 GNUNET_memcpy (trail,
5587 new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5589 if (0 == new_trail_length)
5593 next_peer = trail[new_trail_length-1];
5595 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5598 if (NULL == target_friend)
5600 DEBUG ("\nLINE = %d ,No friend found.",
5605 GDS_NEIGHBOURS_send_trail_setup_result (&source,
5611 ultimate_destination_finger_value,
5615 /* Here I was already part of trail. So no need to add. */
5616 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5617 &successor.next_hop);
5618 if (NULL == target_friend)
5620 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5624 GDS_NEIGHBOURS_send_trail_setup (&source,
5625 ultimate_destination_finger_value,
5626 &successor.best_known_destination,
5632 &successor.trail_id);
5637 * Core handler for trail teardown message.
5639 * @param cls closure
5640 * @param trail_teardown the message
5643 handle_dht_p2p_trail_teardown (void *cls,
5644 const struct PeerTrailTearDownMessage *trail_teardown)
5646 enum GDS_ROUTING_trail_direction trail_direction;
5647 struct GNUNET_HashCode trail_id;
5648 const struct GNUNET_PeerIdentity *next_hop;
5651 msize = ntohs (trail_teardown->header.size);
5652 GNUNET_STATISTICS_update (GDS_stats,
5653 gettext_noop ("# Bytes received from other peers"),
5656 trail_direction = ntohl (trail_teardown->trail_direction);
5657 trail_id = trail_teardown->trail_id;
5659 /* Check if peer is the real peer from which we should get this message.*/
5660 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5662 GNUNET_assert (NULL != (prev_hop =
5663 GDS_ROUTING_get_next_hop (trail_id, ! trail_direction)));
5664 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop,
5672 next_hop = GDS_ROUTING_get_next_hop (&trail_id,
5674 if (NULL == next_hop)
5676 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
5677 GNUNET_i2s (&my_identity),
5678 GNUNET_h2s (&trail_id),
5684 /* I am the next hop, which means I am the final destination. */
5685 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5687 GNUNET_assert (GNUNET_YES ==
5688 GDS_ROUTING_remove_trail (&trail_id));
5691 /* If not final destination, then send a trail teardown message to next hop.*/
5692 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5694 GNUNET_assert (GNUNET_YES ==
5695 GDS_ROUTING_remove_trail (&trail_id));
5696 GDS_NEIGHBOURS_send_trail_teardown (&trail_id,
5703 * Check validity of p2p add trail message.
5705 * @param cls closure
5706 * @param add_trail the message
5707 * @return #GNUNET_OK if @a add_trail is well-formed
5710 check_dht_p2p_add_trail (void *cls,
5711 const struct PeerAddTrailMessage *add_trail)
5715 msize = ntohs (add_trail->header.size);
5716 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5717 sizeof (struct GNUNET_PeerIdentity) != 0)
5719 GNUNET_break_op (0);
5720 return GNUNET_SYSERR;
5727 * Core handle for p2p add trail message.
5729 * @param cls closure
5730 * @param add_trail the message
5733 handle_dht_p2p_add_trail (void *cls,
5734 const struct PeerAddTrailMessage *add_trail)
5736 struct FriendInfo *friend = cls;
5737 const struct GNUNET_PeerIdentity *trail;
5738 struct GNUNET_HashCode trail_id;
5739 struct GNUNET_PeerIdentity destination_peer;
5740 struct GNUNET_PeerIdentity source_peer;
5741 struct GNUNET_PeerIdentity next_hop;
5742 unsigned int trail_length;
5743 unsigned int my_index;
5746 msize = ntohs (add_trail->header.size);
5747 /* In this message we pass the whole trail from source to destination as we
5748 * are adding that trail.*/
5749 //FIXME: failed when run with 1000 pears. check why.
5750 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5751 sizeof (struct GNUNET_PeerIdentity);
5752 GNUNET_STATISTICS_update (GDS_stats,
5753 gettext_noop ("# Bytes received from other peers"),
5757 trail = (const struct GNUNET_PeerIdentity *) &add_trail[1];
5758 destination_peer = add_trail->destination_peer;
5759 source_peer = add_trail->source_peer;
5760 trail_id = add_trail->trail_id;
5762 /* I am not the destination of the trail. */
5763 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
5766 struct FriendInfo *target_friend;
5768 /* Get my location in the trail. */
5769 my_index = search_my_index (trail, trail_length);
5772 GNUNET_break_op (0);
5775 if((trail_length + 1) == my_index)
5777 DEBUG ("Found twice in trail.\n");
5778 GNUNET_break_op (0);
5781 if ((trail_length - 1) == my_index)
5783 next_hop = destination_peer;
5787 next_hop = trail[my_index + 1];
5789 /* Add in your routing table. */
5790 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (&trail_id,
5793 //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5794 GNUNET_assert (NULL !=
5796 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5798 GDS_NEIGHBOURS_send_add_trail (&source_peer,
5806 /* I am the destination. Add an entry in routing table. */
5807 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (&trail_id,
5814 * Free the finger trail in which the first friend to reach to a finger is
5815 * disconnected_friend. Also remove entry from routing table for that particular
5817 * @param disconnected_friend PeerIdentity of friend which got disconnected
5818 * @param remove_finger Finger whose trail we need to check if it has
5819 * disconnected_friend as the first hop.
5820 * @return Total number of trails in which disconnected_friend was the first
5824 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5825 struct FingerInfo *finger)
5827 const struct GNUNET_PeerIdentity *next_hop;
5828 struct FriendInfo *remove_friend;
5829 struct Trail *current_trail;
5830 unsigned int matching_trails_count = 0;
5833 /* Iterate over all the trails of finger. */
5834 for (i = 0; i < finger->trails_count; i++)
5836 current_trail = &finger->trail_list[i];
5837 if (GNUNET_NO == current_trail->is_present)
5840 /* First friend to reach to finger is disconnected_peer. */
5841 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5842 disconnected_friend))
5845 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5846 disconnected_friend);
5847 GNUNET_assert (NULL != remove_friend);
5848 next_hop = GDS_ROUTING_get_next_hop (¤t_trail->trail_id,
5849 GDS_ROUTING_SRC_TO_DEST);
5851 /* Here it may happen that as all the peers got disconnected, the entry in
5852 routing table for that particular trail has been removed, because the
5853 previously disconnected peer was either a next hop or prev hop of that
5855 if (NULL != next_hop)
5857 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5859 GNUNET_assert (GNUNET_YES ==
5860 GDS_ROUTING_remove_trail (¤t_trail->trail_id));
5862 matching_trails_count++;
5863 free_trail (current_trail);
5864 current_trail->is_present = GNUNET_NO;
5867 return matching_trails_count;
5872 * Iterate over finger_table entries.
5873 * 0. Ignore finger which is my_identity or if no valid entry present at
5874 * that finger index.
5875 * 1. If disconnected_friend is a finger, then remove the routing entry from
5876 your own table. Free the trail.
5877 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5878 * 2.1 Remove all the trails and entry from routing table in which disconnected
5879 * friend is the first friend in the trail. If disconnected_friend is the
5880 * first friend in all the trails to reach finger, then remove the finger.
5881 * @param disconnected_friend Peer identity of friend which got disconnected.
5884 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5886 struct FingerInfo *current_finger;
5887 int removed_trails_count;
5890 /* Iterate over finger table entries. */
5891 for (i = 0; i < MAX_FINGERS; i++)
5893 current_finger = &finger_table[i];
5895 /* No finger stored at this trail index or I am the finger. */
5896 if ((GNUNET_NO == current_finger->is_present) ||
5897 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5901 /* Is disconnected_peer a finger? */
5902 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5903 ¤t_finger->finger_identity))
5905 remove_existing_finger (current_finger, i);
5908 /* If finger is a friend but not disconnected_friend, then continue. */
5909 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5910 ¤t_finger->finger_identity))
5913 /* Iterate over the list of trails to reach remove_finger. Check if
5914 * disconnected_friend is the first friend in any of the trail. */
5915 removed_trails_count = remove_matching_trails (disconnected_peer,
5917 current_finger->trails_count =
5918 current_finger->trails_count - removed_trails_count;
5919 if (0 == current_finger->trails_count)
5921 current_finger->is_present = GNUNET_NO;
5922 memset (&finger_table[i],
5924 sizeof (finger_table[i]));
5931 * Method called whenever a peer disconnects.
5933 * @param cls closure
5934 * @param peer peer identity this notification is about
5935 * @param internal_cls our `struct FriendInfo` for @a peer
5938 handle_core_disconnect (void *cls,
5939 const struct GNUNET_PeerIdentity *peer,
5942 struct FriendInfo *remove_friend = internal_cls;
5944 /* If disconnected to own identity, then return. */
5945 if (NULL == remove_friend)
5947 remove_matching_fingers (peer);
5948 GNUNET_assert (GNUNET_SYSERR !=
5949 GDS_ROUTING_remove_trail_by_peer (peer));
5950 GNUNET_assert (GNUNET_YES ==
5951 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5954 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5957 if (NULL != find_finger_trail_task)
5959 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5960 find_finger_trail_task = NULL;
5968 * Method called whenever a peer connects.
5970 * @param cls closure
5971 * @param peer_identity peer identity this notification is about
5972 * @param mq message queue for sending data to @a peer
5973 * @return our `struct FriendInfo` for this peer
5976 handle_core_connect (void *cls,
5977 const struct GNUNET_PeerIdentity *peer_identity,
5978 struct GNUNET_MQ_Handle *mq)
5980 struct FriendInfo *friend;
5982 /* Check for connect to self message */
5983 if (0 == memcmp (&my_identity,
5985 sizeof (struct GNUNET_PeerIdentity)))
5987 friend = GNUNET_new (struct FriendInfo);
5988 friend->id = peer_identity;
5990 GNUNET_assert (GNUNET_OK ==
5991 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5994 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5996 /* FIXME: now we are not making a distinction between fingers which are friends
5997 * also.But later, we should add a congestion timestamp on the friend, so that it is
5998 * selected after some time out. This is to ensure that both peers have added
5999 * each other as their friend. */
6000 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
6001 if (NULL == find_finger_trail_task)
6003 find_finger_trail_task
6004 = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message,
6012 * To be called on core init/fail.
6014 * @param cls service closure
6015 * @param identity the public identity of this peer
6018 core_init (void *cls,
6019 const struct GNUNET_PeerIdentity *identity)
6021 my_identity = *identity;
6026 * Initialize finger table entries.
6029 finger_table_init ()
6031 memset (&finger_table, 0, sizeof (finger_table));
6036 * Initialize neighbours subsystem.
6037 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
6040 GDS_NEIGHBOURS_init (void)
6042 struct GNUNET_MQ_MessageHandler core_handlers[] = {
6043 GNUNET_MQ_hd_var_size (dht_p2p_put,
6044 GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT,
6045 struct PeerPutMessage,
6047 GNUNET_MQ_hd_var_size (dht_p2p_get,
6048 GNUNET_MESSAGE_TYPE_XDHT_P2P_GET,
6049 struct PeerGetMessage,
6051 GNUNET_MQ_hd_var_size (dht_p2p_get_result,
6052 GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT,
6053 struct PeerGetResultMessage,
6055 GNUNET_MQ_hd_var_size (dht_p2p_trail_setup,
6056 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP,
6057 struct PeerTrailSetupMessage,
6059 GNUNET_MQ_hd_var_size (dht_p2p_trail_setup_result,
6060 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT,
6061 struct PeerTrailSetupResultMessag,
6063 GNUNET_MQ_hd_var_size (dht_p2p_verify_successor,
6064 GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR,
6065 struct PeerVerifySuccessorMessage,
6067 GNUNET_MQ_hd_var_size (dht_p2p_verify_successor_result,
6068 GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT,
6069 struct PeerVerifySuccessorResultMessage,
6071 GNUNET_MQ_hd_var_size (dht_p2p_notify_new_successor,
6072 GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR,
6073 struct PeerNotifyNewSuccessorMessage,
6075 GNUNET_MQ_hd_var_size (dht_p2p_trail_setup_rejection,
6076 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION,
6077 struct PeerTrailRejectionMessage,
6079 GNUNET_MQ_hd_fixed_size (dht_p2p_trail_teardown,
6080 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
6081 struct PeerTrailTearDownMessage,
6083 GNUNET_MQ_hd_var_size (dht_p2p_add_trail,
6084 GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL,
6085 struct PeerAddTrailMessage,
6087 GNUNET_MQ_hd_fixed_size (dht_p2p_notify_succ_confirmation,
6088 GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION,
6089 struct PeerNotifyConfirmationMessage,
6091 GNUNET_MQ_handler_end ()
6094 core_api = GNUNET_CORE_connecT (GDS_cfg,
6097 &handle_core_connect,
6098 &handle_core_disconnect,
6100 if (NULL == core_api)
6101 return GNUNET_SYSERR;
6102 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256,
6104 finger_table_init ();
6105 successor_times = 10;
6106 fingers_round_count = 5;
6107 find_finger_trail_task_next_send_time.rel_value_us =
6108 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
6109 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6110 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
6112 verify_successor_next_send_time.rel_value_us =
6113 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
6114 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6115 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
6117 verify_successor_retry_time.rel_value_us =
6118 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6119 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6120 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6122 notify_successor_retry_time.rel_value_us =
6123 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6124 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6125 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6132 * Free the memory held up by trails of a finger.
6135 delete_finger_table_entries()
6137 for (unsigned int i = 0; i < MAX_FINGERS; i++)
6139 if (GNUNET_YES != finger_table[i].is_present)
6141 for (unsigned int j = 0; j < finger_table[i].trails_count; j++)
6142 free_trail(&finger_table[i].trail_list[j]);
6148 * Shutdown neighbours subsystem.
6151 GDS_NEIGHBOURS_done (void)
6153 if (NULL == core_api)
6156 GNUNET_CORE_disconnecT (core_api);
6159 delete_finger_table_entries();
6160 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6161 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6162 friend_peermap = NULL;
6164 if (NULL != find_finger_trail_task)
6166 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6167 find_finger_trail_task = NULL;
6170 if (NULL != send_verify_successor_task)
6172 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6173 send_verify_successor_task = NULL;
6175 if (NULL != send_verify_successor_retry_task)
6177 struct VerifySuccessorContext *ctx;
6179 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
6181 send_verify_successor_retry_task = NULL;
6183 if (NULL != send_notify_new_successor_retry_task)
6185 struct SendNotifyContext *notify_ctx;
6187 notify_ctx = GNUNET_SCHEDULER_cancel (send_notify_new_successor_retry_task);
6188 GNUNET_free (notify_ctx->successor_trail);
6189 GNUNET_free (notify_ctx);
6190 send_notify_new_successor_retry_task = NULL;
6198 * @return my identity
6200 struct GNUNET_PeerIdentity
6201 GDS_NEIGHBOURS_get_my_id (void)
6206 /* end of gnunet-service-xdht_neighbours.c */