2 This file is part of GNUnet.
3 Copyright (C) 2009-2014 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
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_ats_service.h"
34 #include "gnunet_core_service.h"
35 #include "gnunet_datacache_lib.h"
36 #include "gnunet_transport_service.h"
37 #include "gnunet_dht_service.h"
38 #include "gnunet_statistics_service.h"
39 #include "gnunet-service-xdht.h"
40 #include "gnunet-service-xdht_clients.h"
41 #include "gnunet-service-xdht_datacache.h"
42 #include "gnunet-service-xdht_neighbours.h"
43 #include "gnunet-service-xdht_routing.h"
48 * 1. In X-Vine paper, there is no policy defined for replicating the data to
49 * recover in case of peer failure. We can do it in Chord way. In R5N, the key
50 * is hashed and then data is stored according to the key value generated after
55 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
58 * Maximum possible fingers (including predecessor) of a peer
60 #define MAX_FINGERS 65
63 * Maximum allowed number of pending messages per friend peer.
65 #define MAXIMUM_PENDING_PER_FRIEND 64
68 * How long to wait before sending another find finger trail request
70 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
73 * How long to wait before sending another verify successor message.
75 #define DHT_SEND_VERIFY_SUCCESSOR_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
78 * How long to wait before sending another verify successor message.
80 #define DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
83 * How long to wait before retrying notify successor.
85 #define DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
88 * How long at most to wait for transmission of a request to a friend ?
90 #define PENDING_MESSAGE_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
93 * Duration for which I may remain congested.
94 * Note: Its a static value. In future, a peer may do some analysis and calculate
95 * congestion_timeout based on 'some' parameters.
97 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
100 * In case we don't hear back from the current successor, then we can start
103 #define WAIT_NOTIFY_CONFIRMATION GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 200)
106 * Maximum number of trails allowed to go through a friend.
108 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
111 * Maximum number of trails stored per finger.
113 #define MAXIMUM_TRAILS_PER_FINGER 4
116 * Finger map index for predecessor entry in finger table.
118 #define PREDECESSOR_FINGER_ID 64
121 * FIXME: Its use only at 3 places check if you can remove it.
122 * To check if a finger is predecessor or not.
124 enum GDS_NEIGHBOURS_finger_type
126 GDS_FINGER_TYPE_PREDECESSOR = 1,
127 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
130 GNUNET_NETWORK_STRUCT_BEGIN
135 struct PeerPutMessage
138 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
140 struct GNUNET_MessageHeader header;
145 uint32_t options GNUNET_PACKED;
150 uint32_t block_type GNUNET_PACKED;
155 uint32_t hop_count GNUNET_PACKED;
158 * Replication level for this message
159 * In the current implementation, this value is not used.
161 uint32_t desired_replication_level GNUNET_PACKED;
164 * Length of the PUT path that follows (if tracked).
166 uint32_t put_path_length GNUNET_PACKED;
169 * Best known destination (could be my friend or finger) which should
170 * get this message next.
172 struct GNUNET_PeerIdentity best_known_destination;
175 * In case best_known_destination is a finger, then trail to reach
176 * to that finger. Else its default value is 0.
178 struct GNUNET_HashCode intermediate_trail_id;
181 * When does the content expire?
183 struct GNUNET_TIME_AbsoluteNBO expiration_time;
186 * The key to store the value under.
188 struct GNUNET_HashCode key GNUNET_PACKED;
190 /* put path (if tracked) */
199 struct PeerGetMessage
202 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
204 struct GNUNET_MessageHeader header;
209 uint32_t options GNUNET_PACKED;
212 * Desired content type.
214 uint32_t block_type GNUNET_PACKED;
219 uint32_t hop_count GNUNET_PACKED;
222 * Desired replication level for this request.
223 * In the current implementation, this value is not used.
225 uint32_t desired_replication_level GNUNET_PACKED;
228 * Total number of peers in get path.
230 unsigned int get_path_length;
233 * Best known destination (could be my friend or finger) which should
234 * get this message next.
236 struct GNUNET_PeerIdentity best_known_destination;
239 * In case best_known_destination is a finger, then trail to reach
240 * to that finger. Else its default value is 0.
242 struct GNUNET_HashCode intermediate_trail_id;
245 * The key we are looking for.
247 struct GNUNET_HashCode key;
250 /* struct GNUNET_PeerIdentity[]*/
256 struct PeerGetResultMessage
259 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
261 struct GNUNET_MessageHeader header;
264 * The type for the data.
266 uint32_t type GNUNET_PACKED;
269 * Number of peers recorded in the outgoing path from source to the
270 * stored location of this message.
272 uint32_t put_path_length GNUNET_PACKED;
275 * Length of the GET path that follows (if tracked).
277 uint32_t get_path_length GNUNET_PACKED;
280 * Peer which queried for get and should get the result.
282 struct GNUNET_PeerIdentity querying_peer;
285 * When does the content expire?
287 struct GNUNET_TIME_AbsoluteNBO expiration_time;
290 * The key of the corresponding GET request.
292 struct GNUNET_HashCode key;
294 /* put path (if tracked) */
296 /* get path (if tracked) */
303 * P2P Trail setup message
305 struct PeerTrailSetupMessage
308 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
310 struct GNUNET_MessageHeader header;
313 * Is source_peer trying to setup the trail to a predecessor or any finger.
315 uint32_t is_predecessor;
318 * Peer closest to this value will be our finger.
320 uint64_t final_destination_finger_value;
323 * Source peer which wants to setup the trail to one of its finger.
325 struct GNUNET_PeerIdentity source_peer;
328 * Best known destination (could be my friend or finger) which should
329 * get this message next.
331 * FIXME: this could be removed if we include trail_source / trail_dest
332 * in the routing table. This way we save 32 bytes of bandwidth by using
333 * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID))
335 struct GNUNET_PeerIdentity best_known_destination;
338 * In case best_known_destination is a finger, then trail id of trail to
339 * reach to this finger.
341 struct GNUNET_HashCode intermediate_trail_id;
344 * Trail id for trail which we are trying to setup.
346 struct GNUNET_HashCode trail_id;
348 /* List of peers which are part of trail setup so far.
349 * Trail does NOT include source_peer and peer which will be closest to
350 * ultimate_destination_finger_value.
351 * struct GNUNET_PeerIdentity trail[]
356 * P2P Trail Setup Result message
358 struct PeerTrailSetupResultMessage
362 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
364 struct GNUNET_MessageHeader header;
367 * Finger to which we have found the path.
369 struct GNUNET_PeerIdentity finger_identity;
372 * Peer which started trail_setup to find trail to finger_identity
374 struct GNUNET_PeerIdentity querying_peer;
377 * Is the trail setup to querying_peer's predecessor or finger?
379 uint32_t is_predecessor;
382 * Value to which finger_identity is the closest peer.
384 uint64_t ulitmate_destination_finger_value;
387 * Identifier of the trail from querying peer to finger_identity, NOT
388 * including both endpoints.
390 struct GNUNET_HashCode trail_id;
392 /* List of peers which are part of the trail from querying peer to
393 * finger_identity, NOT including both endpoints.
394 * struct GNUNET_PeerIdentity trail[]
399 * P2P Verify Successor Message.
401 struct PeerVerifySuccessorMessage
404 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
406 struct GNUNET_MessageHeader header;
409 * Peer which wants to verify its successor.
411 struct GNUNET_PeerIdentity source_peer;
414 * Source Peer's current successor.
416 struct GNUNET_PeerIdentity successor;
419 * Identifier of trail to reach from source_peer to successor.
421 struct GNUNET_HashCode trail_id;
423 /* List of the peers which are part of trail to reach from source_peer
424 * to successor, NOT including them
425 * struct GNUNET_PeerIdentity trail[]
430 * P2P Verify Successor Result Message
432 struct PeerVerifySuccessorResultMessage
435 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
437 struct GNUNET_MessageHeader header;
440 * Peer which sent the request to verify its successor.
442 struct GNUNET_PeerIdentity querying_peer;
445 * Successor to which PeerVerifySuccessorMessage was sent.
447 struct GNUNET_PeerIdentity current_successor;
450 * Current Predecessor of source_successor. It can be same as querying peer
451 * or different. In case it is different then it can be querying_peer's
452 * probable successor.
454 struct GNUNET_PeerIdentity probable_successor;
457 * Trail identifier of trail from querying_peer to current_successor.
459 struct GNUNET_HashCode trail_id;
462 * Direction in which we are looking at the trail.
464 uint32_t trail_direction;
466 /* In case probable_successor != querying_peer, then trail to reach from
467 * querying_peer to probable_successor, NOT including end points.
468 * struct GNUNET_PeerIdentity trail[]
473 * P2P Notify New Successor Message.
475 struct PeerNotifyNewSuccessorMessage
478 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
480 struct GNUNET_MessageHeader header;
483 * Peer which wants to notify its new successor.
485 struct GNUNET_PeerIdentity source_peer;
488 * New successor of source_peer.
490 struct GNUNET_PeerIdentity new_successor;
493 * Unique identifier of the trail from source_peer to new_successor,
494 * NOT including the endpoints.
496 struct GNUNET_HashCode trail_id;
498 /* List of peers in trail from source_peer to new_successor,
499 * NOT including the endpoints.
500 * struct GNUNET_PeerIdentity trail[]
505 * P2P Notify Successor Confirmation message.
507 struct PeerNotifyConfirmationMessage
510 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
512 struct GNUNET_MessageHeader header;
515 * Unique identifier of the trail.
517 struct GNUNET_HashCode trail_id;
520 * Direction of trail.
522 uint32_t trail_direction;
527 * P2P Trail Tear Down message.
529 struct PeerTrailTearDownMessage
532 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
534 struct GNUNET_MessageHeader header;
537 * Unique identifier of the trail.
539 struct GNUNET_HashCode trail_id;
542 * Direction of trail.
544 uint32_t trail_direction;
549 * P2P Trail Rejection Message.
551 struct PeerTrailRejectionMessage
554 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
556 struct GNUNET_MessageHeader header;
559 * Peer which wants to set up the trail.
561 struct GNUNET_PeerIdentity source_peer;
564 * Peer which sent trail rejection message as it it congested.
566 struct GNUNET_PeerIdentity congested_peer;
569 * Peer identity closest to this value will be finger of
572 uint64_t ultimate_destination_finger_value;
575 * Is source_peer trying to setup the trail to its predecessor or finger.
577 uint32_t is_predecessor;
580 * Identifier for the trail that source peer is trying to setup.
582 struct GNUNET_HashCode trail_id;
585 * Relative time for which congested_peer will remain congested.
587 struct GNUNET_TIME_Relative congestion_time;
589 /* Trail_list from source_peer to peer which sent the message for trail setup
590 * to congested peer. This trail does NOT include source_peer.
591 struct GNUNET_PeerIdnetity trail[]*/
595 * P2P Add Trail Message.
597 struct PeerAddTrailMessage
600 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
602 struct GNUNET_MessageHeader header;
605 * Source of the routing trail.
607 struct GNUNET_PeerIdentity source_peer;
610 * Destination of the routing trail.
612 struct GNUNET_PeerIdentity destination_peer;
615 * Unique identifier of the trail from source_peer to destination_peer,
616 * NOT including the endpoints.
618 struct GNUNET_HashCode trail_id;
620 /* Trail from source peer to destination peer, NOT including them.
621 * struct GNUNET_PeerIdentity trail[]
626 GNUNET_NETWORK_STRUCT_END
629 * Linked list of messages to send to a particular other peer.
631 struct P2PPendingMessage
634 * Pointer to next item in the list
636 struct P2PPendingMessage *next;
639 * Pointer to previous item in the list
641 struct P2PPendingMessage *prev;
644 * Message importance level. FIXME: used? useful?
646 unsigned int importance;
649 * When does this message time out?
651 struct GNUNET_TIME_Absolute timeout;
654 * Actual message to be sent, allocated at the end of the struct:
655 * // msg = (cast) &pm[1];
656 * // memcpy (&pm[1], data, len);
658 const struct GNUNET_MessageHeader *msg;
663 * Entry in friend_peermap.
670 struct GNUNET_PeerIdentity id;
673 * Number of trails for which this friend is the first hop or if the friend
676 unsigned int trails_count;
679 * Count of outstanding messages for this friend.
681 unsigned int pending_count;
684 * In case not 0, then amount of time for which this friend is congested.
686 struct GNUNET_TIME_Absolute congestion_timestamp;
689 // TODO : Change name of head and tail to pending_messages_list_head and so.
691 * Head of pending messages to be sent to this friend.
693 struct P2PPendingMessage *head;
696 * Tail of pending messages to be sent to this friend.
698 struct P2PPendingMessage *tail;
701 * Core handle for sending messages to this friend.
703 struct GNUNET_CORE_TransmitHandle *th;
708 * An individual element of the trail to reach to a finger.
713 * Pointer to next item in the list
715 struct Trail_Element *next;
718 * Pointer to prev item in the list
720 struct Trail_Element *prev;
723 * An element in this trail.
725 struct GNUNET_PeerIdentity peer;
729 * Information about an individual trail.
736 struct Trail_Element *trail_head;
741 struct Trail_Element *trail_tail;
744 * Unique identifier of this trail.
746 struct GNUNET_HashCode trail_id;
749 * Length of trail pointed
751 unsigned int trail_length;
754 * Is there a valid trail entry.
756 unsigned int is_present;
760 * An entry in finger_table
767 struct GNUNET_PeerIdentity finger_identity;
770 * In case not 0, this amount is time to wait for notify successor message.
771 * Used ONLY for successor. NOT for any other finger.
773 struct GNUNET_TIME_Absolute wait_notify_confirmation;
776 * Is any finger stored at this finger index.
778 unsigned int is_present;
781 * Index in finger peer map
783 uint32_t finger_table_index;
786 * Number of trails setup so far for this finger.
787 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
789 uint32_t trails_count;
792 * Array of trails to reach to this finger.
794 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
799 * Stores information about the peer which is closest to destination_finger_value.
800 * 'closest' can be either successor or predecessor depending on is_predecessor
806 * Destination finger value.
808 uint64_t destination_finger_value;
811 * Is finger_value a predecessor or any other finger.
813 unsigned int is_predecessor;
816 * Trail id to reach to peer.
817 * In case peer is my identity or friend, it is set to 0.
819 struct GNUNET_HashCode trail_id;
822 * Next destination. In case of friend and my_identity , it is same as next_hop
823 * In case of finger it is finger identity.
825 struct GNUNET_PeerIdentity best_known_destination;
828 * In case best_known_destination is a finger, then first friend in the trail
829 * to reach to it. In other case, same as best_known_destination.
831 struct GNUNET_PeerIdentity next_hop;
834 * In case finger is the next hop, it contains a valid finger table index
835 * at which the finger is stored. Else, It contains 65, which is out of range
836 * of finger table index.
838 unsigned int finger_table_index;
842 * Context for send_verify_successor_task.
844 struct VerifySuccessorContext
847 * Number of times this has been scheduled.
849 unsigned int num_retries_scheduled;
853 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
854 * get our first friend.
856 static struct GNUNET_SCHEDULER_Task * find_finger_trail_task;
859 * Task that sends verify successor message. This task is started when we get
860 * our successor for the first time.
862 static struct GNUNET_SCHEDULER_Task * send_verify_successor_task;
865 * Task that sends verify successor message. This task is started when we get
866 * our successor for the first time.
868 static struct GNUNET_SCHEDULER_Task * send_verify_successor_retry_task;
871 * Task that sends verify successor message. This task is started when we get
872 * our successor for the first time.
874 static struct GNUNET_SCHEDULER_Task * send_notify_new_successor_retry_task;
877 * Identity of this peer.
879 static struct GNUNET_PeerIdentity my_identity;
882 * Peer map of all the friends of a peer
884 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
887 * Array of all the fingers.
889 static struct FingerInfo finger_table [MAX_FINGERS];
894 static struct GNUNET_CORE_Handle *core_api;
897 * Handle for the statistics service.
899 //extern struct GNUNET_STATISTICS_Handle *GDS_stats;
902 * The current finger index that we have want to find trail to. We start the
903 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
904 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
905 * we reset this index to 0.
907 static unsigned int current_search_finger_index;
910 * Time duration to schedule find finger trail task.
912 static struct GNUNET_TIME_Relative find_finger_trail_task_next_send_time;
915 * Time duration to schedule verify successor task.
917 static struct GNUNET_TIME_Relative verify_successor_next_send_time;
920 * Time duration to send verify successor again, if result was not received in time.
922 static struct GNUNET_TIME_Relative verify_successor_retry_time;
925 * Time duration to retry send_notify_successor.
927 static struct GNUNET_TIME_Relative notify_successor_retry_time;
930 * Are we waiting for confirmation from our new successor that it got the
933 //static unsigned int waiting_for_notify_confirmation;
935 /* Below variables are used only for testing, and statistics collection. */
937 * Should we store our topology predecessor and successor IDs into statistics?
939 unsigned int track_topology;
942 * Count of fingers found. Ideally we should have O(logn) fingers for a
945 static unsigned int total_fingers_found;
948 * Number of times we found the same successor.
950 static unsigned int successor_times;
953 * Number of rounds for which we should search for finger.
955 static unsigned int fingers_round_count;
957 * Called when core is ready to send a message we asked for
958 * out to the destination.
960 * @param cls the 'struct FriendInfo' of the target friend
961 * @param size number of bytes available in buf
962 * @param buf where the callee should write the message
963 * @return number of bytes written to buf
966 core_transmit_notify (void *cls, size_t size, void *buf)
968 struct FriendInfo *peer = cls;
970 struct P2PPendingMessage *pending;
975 while ( (NULL != (pending = peer->head)) &&
976 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us) )
978 GNUNET_STATISTICS_update (GDS_stats,
980 ("# Messages dropped (CORE timeout)"),
983 peer->pending_count--;
984 GNUNET_CONTAINER_DLL_remove (peer->head,
987 GNUNET_free (pending);
991 /* no messages pending */
997 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
998 GNUNET_CORE_PRIO_BEST_EFFORT,
999 GNUNET_TIME_absolute_get_remaining
1000 (pending->timeout), &peer->id,
1001 ntohs (pending->msg->size),
1002 &core_transmit_notify, peer);
1003 GNUNET_break (NULL != peer->th);
1007 while ((NULL != (pending = peer->head)) &&
1008 (size - off >= (msize = ntohs (pending->msg->size))))
1010 GNUNET_STATISTICS_update (GDS_stats,
1012 ("# Bytes transmitted to other peers"),
1015 memcpy (&cbuf[off], pending->msg, msize);
1017 peer->pending_count--;
1018 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1019 GNUNET_free (pending);
1021 if (peer->head != NULL)
1024 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1025 GNUNET_CORE_PRIO_BEST_EFFORT,
1026 GNUNET_TIME_absolute_get_remaining
1027 (pending->timeout), &peer->id, msize,
1028 &core_transmit_notify, peer);
1029 GNUNET_break (NULL != peer->th);
1036 * Transmit all messages in the friend's message queue.
1038 * @param peer message queue to process
1041 process_friend_queue (struct FriendInfo *peer)
1043 struct P2PPendingMessage *pending;
1045 if (NULL == (pending = peer->head))
1049 if (NULL != peer->th)
1055 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1056 pending->importance,
1057 GNUNET_TIME_absolute_get_remaining
1058 (pending->timeout), &peer->id,
1059 ntohs (pending->msg->size),
1060 &core_transmit_notify, peer);
1061 GNUNET_break (NULL != peer->th);
1066 * Construct a trail setup message and forward it to target_friend
1067 * @param source_peer Peer which wants to setup the trail
1068 * @param ultimate_destination_finger_value Peer identity closest to this value
1069 * will be finger to @a source_peer
1070 * @param best_known_destination Best known destination (could be finger or friend)
1071 * which should get this message. In case it is
1072 * friend, then it is same as target_friend
1073 * @param target_friend Friend to which message is forwarded now.
1074 * @param trail_length Total number of peers in trail setup so far.
1075 * @param trail_peer_list Trail setup so far
1076 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1077 * @param trail_id Unique identifier for the trail we are trying to setup.
1078 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1079 * best_known_destination when its a finger. If not
1080 * used then set to 0.
1083 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1084 uint64_t ultimate_destination_finger_value,
1085 struct GNUNET_PeerIdentity best_known_destination,
1086 struct FriendInfo *target_friend,
1087 unsigned int trail_length,
1088 const struct GNUNET_PeerIdentity *trail_peer_list,
1089 unsigned int is_predecessor,
1090 struct GNUNET_HashCode trail_id,
1091 struct GNUNET_HashCode intermediate_trail_id)
1093 struct P2PPendingMessage *pending;
1094 struct PeerTrailSetupMessage *tsm;
1095 struct GNUNET_PeerIdentity *peer_list;
1098 msize = sizeof (struct PeerTrailSetupMessage) +
1099 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1101 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1107 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1109 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1112 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1113 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1114 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1115 pending->msg = &(tsm->header);
1116 tsm->header.size = htons (msize);
1117 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1118 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1119 tsm->source_peer = source_peer;
1120 tsm->best_known_destination = best_known_destination;
1121 tsm->is_predecessor = htonl (is_predecessor);
1122 tsm->trail_id = trail_id;
1123 tsm->intermediate_trail_id = intermediate_trail_id;
1125 if (trail_length > 0)
1127 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1128 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1131 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1132 target_friend->pending_count++;
1133 process_friend_queue (target_friend);
1138 * Construct a trail setup result message and forward it to target friend.
1139 * @param querying_peer Peer which sent the trail setup request and should get
1141 * @param Finger Peer to which the trail has been setup to.
1142 * @param target_friend Friend to which this message should be forwarded.
1143 * @param trail_length Numbers of peers in the trail.
1144 * @param trail_peer_list Peers which are part of the trail from
1145 * querying_peer to Finger, NOT including them.
1146 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1147 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1149 * @param trail_id Unique identifier of the trail.
1152 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1153 struct GNUNET_PeerIdentity finger,
1154 struct FriendInfo *target_friend,
1155 unsigned int trail_length,
1156 const struct GNUNET_PeerIdentity *trail_peer_list,
1157 unsigned int is_predecessor,
1158 uint64_t ultimate_destination_finger_value,
1159 struct GNUNET_HashCode trail_id)
1161 struct P2PPendingMessage *pending;
1162 struct PeerTrailSetupResultMessage *tsrm;
1163 struct GNUNET_PeerIdentity *peer_list;
1166 msize = sizeof (struct PeerTrailSetupResultMessage) +
1167 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1169 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1175 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1177 GNUNET_STATISTICS_update (GDS_stats,
1178 gettext_noop ("# P2P messages dropped due to full queue"),
1182 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1183 pending->importance = 0;
1184 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1185 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1186 pending->msg = &tsrm->header;
1187 tsrm->header.size = htons (msize);
1188 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1189 tsrm->querying_peer = querying_peer;
1190 tsrm->finger_identity = finger;
1191 tsrm->is_predecessor = htonl (is_predecessor);
1192 tsrm->trail_id = trail_id;
1193 tsrm->ulitmate_destination_finger_value =
1194 GNUNET_htonll (ultimate_destination_finger_value);
1195 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1196 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1198 /* Send the message to chosen friend. */
1199 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1200 target_friend->pending_count++;
1201 process_friend_queue (target_friend);
1205 * Send notify successor confirmation message.
1206 * @param trail_id Unique Identifier of the trail.
1207 * @param trail_direction Destination to Source.
1208 * @param target_friend Friend to get this message next.
1211 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (struct GNUNET_HashCode trail_id,
1212 unsigned int trail_direction,
1213 struct FriendInfo *target_friend)
1215 struct PeerNotifyConfirmationMessage *ncm;
1216 struct P2PPendingMessage *pending;
1219 msize = sizeof (struct PeerNotifyConfirmationMessage);
1220 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1226 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1228 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1232 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1233 pending->importance = 0; /* FIXME */
1234 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1235 ncm = (struct PeerNotifyConfirmationMessage *) &pending[1];
1236 pending->msg = &ncm->header;
1237 ncm->header.size = htons (msize);
1238 ncm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION);
1239 ncm->trail_id = trail_id;
1240 ncm->trail_direction = htonl (trail_direction);
1242 /* Send the message to chosen friend. */
1243 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1244 target_friend->pending_count++;
1245 process_friend_queue (target_friend);
1250 * Send trail rejection message to target friend
1251 * @param source_peer Peer which is trying to setup the trail.
1252 * @param ultimate_destination_finger_value Peer closest to this value will be
1253 * @a source_peer's finger
1254 * @param congested_peer Peer which sent this message as it is congested.
1255 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1256 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1257 * by congested_peer. This does NOT include @a source_peer
1258 * and congested_peer.
1259 * @param trail_length Total number of peers in trail_peer_list, NOT including
1260 * @a source_peer and @a congested_peer
1261 * @param trail_id Unique identifier of this trail.
1262 * @param congestion_timeout Duration given by congested peer as an estimate of
1263 * how long it may remain congested.
1266 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1267 uint64_t ultimate_destination_finger_value,
1268 struct GNUNET_PeerIdentity congested_peer,
1269 unsigned int is_predecessor,
1270 const struct GNUNET_PeerIdentity *trail_peer_list,
1271 unsigned int trail_length,
1272 struct GNUNET_HashCode trail_id,
1273 struct FriendInfo *target_friend,
1274 const struct GNUNET_TIME_Relative congestion_timeout)
1276 struct PeerTrailRejectionMessage *trm;
1277 struct P2PPendingMessage *pending;
1278 struct GNUNET_PeerIdentity *peer_list;
1281 msize = sizeof (struct PeerTrailRejectionMessage) +
1282 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1284 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1290 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1292 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1296 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1297 pending->importance = 0;
1298 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1299 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1300 pending->msg = &trm->header;
1301 trm->header.size = htons (msize);
1302 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1303 trm->source_peer = source_peer;
1304 trm->congested_peer = congested_peer;
1305 trm->congestion_time = congestion_timeout;
1306 trm->is_predecessor = htonl (is_predecessor);
1307 trm->trail_id = trail_id;
1308 trm->ultimate_destination_finger_value =
1309 GNUNET_htonll (ultimate_destination_finger_value);
1311 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1312 if (trail_length > 0)
1314 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1317 /* Send the message to chosen friend. */
1318 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1319 target_friend->pending_count++;
1320 process_friend_queue (target_friend);
1325 * Construct a verify successor message and forward it to target_friend.
1326 * @param source_peer Peer which wants to verify its successor.
1327 * @param successor Peer which is @a source_peer's current successor.
1328 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1329 * NOT including them.
1330 * @param trail List of peers which are part of trail to reach from @a source_peer
1331 * to @a successor, NOT including them.
1332 * @param trail_length Total number of peers in @a trail.
1333 * @param target_friend Next friend to get this message.
1336 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1337 struct GNUNET_PeerIdentity successor,
1338 struct GNUNET_HashCode trail_id,
1339 struct GNUNET_PeerIdentity *trail,
1340 unsigned int trail_length,
1341 struct FriendInfo *target_friend)
1343 struct PeerVerifySuccessorMessage *vsm;
1344 struct P2PPendingMessage *pending;
1345 struct GNUNET_PeerIdentity *peer_list;
1348 msize = sizeof (struct PeerVerifySuccessorMessage) +
1349 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1351 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1357 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1359 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1363 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1364 pending->importance = 0; /* FIXME */
1365 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1366 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1367 pending->msg = &vsm->header;
1368 vsm->header.size = htons (msize);
1369 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1370 vsm->source_peer = source_peer;
1371 vsm->successor = successor;
1372 vsm->trail_id = trail_id;
1373 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1374 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1376 /* Send the message to chosen friend. */
1377 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1378 target_friend->pending_count++;
1379 process_friend_queue (target_friend);
1384 * FIXME: In every function we pass target friend except for this one.
1385 * so, either change everything or this one. also, should se just store
1386 * the pointer to friend in routing table rather than gnunet_peeridentity.
1387 * if yes then we should keep friend info in.h andmake lot of changes.
1388 * Construct a trail teardown message and forward it to target friend.
1390 * @param trail_id Unique identifier of the trail.
1391 * @param trail_direction Direction of trail.
1392 * @param target_friend Friend to get this message.
1395 GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_HashCode *trail_id,
1396 unsigned int trail_direction,
1397 const struct GNUNET_PeerIdentity *peer)
1399 struct PeerTrailTearDownMessage *ttdm;
1400 struct P2PPendingMessage *pending;
1401 struct FriendInfo *target_friend;
1404 msize = sizeof (struct PeerTrailTearDownMessage);
1405 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1411 if (NULL == (target_friend =
1412 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
1414 /* FIXME: In what case friend can be null. ?*/
1419 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1421 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1425 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1426 pending->importance = 0; /* FIXME */
1427 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1428 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1429 pending->msg = &ttdm->header;
1430 ttdm->header.size = htons (msize);
1431 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1432 ttdm->trail_id = *trail_id;
1433 ttdm->trail_direction = htonl (trail_direction);
1435 /* Send the message to chosen friend. */
1436 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1437 target_friend->pending_count++;
1438 process_friend_queue (target_friend);
1443 * Construct a verify successor result message and send it to target_friend
1444 * @param querying_peer Peer which sent the verify successor message.
1445 * @param source_successor Current_successor of @a querying_peer.
1446 * @param current_predecessor Current predecessor of @a successor. Could be same
1447 * or different from @a querying_peer.
1448 * @param trail_id Unique identifier of the trail from @a querying_peer to
1449 * @a successor, NOT including them.
1450 * @param trail List of peers which are part of trail from @a querying_peer to
1451 * @a successor, NOT including them.
1452 * @param trail_length Total number of peers in @a trail
1453 * @param trail_direction Direction in which we are sending the message. In this
1454 * case we are sending result from @a successor to @a querying_peer.
1455 * @param target_friend Next friend to get this message.
1458 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1459 struct GNUNET_PeerIdentity current_successor,
1460 struct GNUNET_PeerIdentity probable_successor,
1461 struct GNUNET_HashCode trail_id,
1462 const struct GNUNET_PeerIdentity *trail,
1463 unsigned int trail_length,
1464 enum GDS_ROUTING_trail_direction trail_direction,
1465 struct FriendInfo *target_friend)
1467 struct PeerVerifySuccessorResultMessage *vsmr;
1468 struct P2PPendingMessage *pending;
1469 struct GNUNET_PeerIdentity *peer_list;
1472 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1473 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1475 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1481 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1483 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1487 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1488 pending->importance = 0; /* FIXME */
1489 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1490 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1491 pending->msg = &vsmr->header;
1492 vsmr->header.size = htons (msize);
1493 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1494 vsmr->querying_peer = querying_peer;
1495 vsmr->current_successor = current_successor;
1496 vsmr->probable_successor = probable_successor;
1497 vsmr->trail_direction = htonl (trail_direction);
1498 vsmr->trail_id = trail_id;
1499 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1500 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1502 /* Send the message to chosen friend. */
1503 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1504 target_friend->pending_count++;
1505 process_friend_queue (target_friend);
1510 * Construct a notify new successor message and send it to target_friend
1511 * @param source_peer Peer which wants to notify to its new successor that it
1512 * could be its predecessor.
1513 * @param successor New successor of @a source_peer
1514 * @param successor_trail List of peers in Trail to reach from
1515 * @a source_peer to @a new_successor, NOT including
1517 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1518 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1519 * @param target_friend Next friend to get this message.
1522 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1523 struct GNUNET_PeerIdentity successor,
1524 const struct GNUNET_PeerIdentity *successor_trail,
1525 unsigned int successor_trail_length,
1526 struct GNUNET_HashCode succesor_trail_id,
1527 struct FriendInfo *target_friend)
1529 struct PeerNotifyNewSuccessorMessage *nsm;
1530 struct P2PPendingMessage *pending;
1531 struct GNUNET_PeerIdentity *peer_list;
1534 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1535 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1537 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1543 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1545 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1549 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1550 pending->importance = 0; /* FIXME */
1551 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1552 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1553 pending->msg = &nsm->header;
1554 nsm->header.size = htons (msize);
1555 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1556 nsm->new_successor = successor;
1557 nsm->source_peer = source_peer;
1558 nsm->trail_id = succesor_trail_id;
1559 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1560 memcpy (peer_list, successor_trail,
1561 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1563 /* Send the message to chosen friend. */
1564 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1565 target_friend->pending_count++;
1566 process_friend_queue (target_friend);
1571 * Construct an add_trail message and send it to target_friend
1572 * @param source_peer Source of the trail.
1573 * @param destination_peer Destination of the trail.
1574 * @param trail_id Unique identifier of the trail from
1575 * @a source_peer to @a destination_peer, NOT including the endpoints.
1576 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1577 * NOT including the endpoints.
1578 * @param trail_length Total number of peers in @a trail.
1579 * @param target_friend Next friend to get this message.
1582 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1583 struct GNUNET_PeerIdentity destination_peer,
1584 struct GNUNET_HashCode trail_id,
1585 const struct GNUNET_PeerIdentity *trail,
1586 unsigned int trail_length,
1587 struct FriendInfo *target_friend)
1589 struct PeerAddTrailMessage *adm;
1590 struct GNUNET_PeerIdentity *peer_list;
1591 struct P2PPendingMessage *pending;
1594 msize = sizeof (struct PeerAddTrailMessage) +
1595 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1597 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1603 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1605 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1609 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1610 pending->importance = 0; /* FIXME */
1611 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1612 adm = (struct PeerAddTrailMessage *) &pending[1];
1613 pending->msg = &adm->header;
1614 adm->header.size = htons (msize);
1615 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1616 adm->source_peer = source_peer;
1617 adm->destination_peer = destination_peer;
1618 adm->trail_id = trail_id;
1619 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1620 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1622 /* Send the message to chosen friend. */
1623 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1624 target_friend->pending_count++;
1625 process_friend_queue (target_friend);
1631 * Search my location in trail. In case I am present more than once in the
1632 * trail (can happen during trail setup), then return my lowest index.
1633 * @param trail List of peers
1634 * @return my_index if found
1635 * trail_length + 1 if an entry is present twice, It is an error.
1636 * -1 if no entry found.
1639 search_my_index (const struct GNUNET_PeerIdentity *trail,
1643 int index_seen = trail_length + 1;
1646 for (i = 0; i < trail_length; i++)
1648 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1651 if(index_seen == (trail_length + 1))
1655 DEBUG("Entry is present twice in trail. Its not allowed\n");
1669 * Check if the friend is congested or have reached maximum number of trails
1670 * it can be part of of.
1671 * @param friend Friend to be checked.
1672 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1673 * #GNUNET_YES if friend is either congested or have crossed threshold
1676 is_friend_congested (struct FriendInfo *friend)
1678 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1679 ((0 == GNUNET_TIME_absolute_get_remaining
1680 (friend->congestion_timestamp).rel_value_us)))
1688 * Select closest finger to value.
1689 * @param peer1 First peer
1690 * @param peer2 Second peer
1691 * @param value Value to be compare
1692 * @return Closest peer
1694 static struct GNUNET_PeerIdentity
1695 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1696 const struct GNUNET_PeerIdentity *peer2,
1699 uint64_t peer1_value;
1700 uint64_t peer2_value;
1702 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1703 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1704 peer1_value = GNUNET_ntohll (peer1_value);
1705 peer2_value = GNUNET_ntohll (peer2_value);
1707 if (peer1_value == value)
1712 if (peer2_value == value)
1717 if (value < peer1_value && peer1_value < peer2_value)
1721 else if (value < peer2_value && peer2_value < peer1_value)
1725 else if (peer1_value < value && value < peer2_value)
1729 else if (peer2_value < value && value < peer1_value)
1733 else if (peer1_value < peer2_value && peer2_value < value)
1737 else // if (peer2_value < peer1_value && peer1_value < value)
1745 * Select closest predecessor to value.
1746 * @param peer1 First peer
1747 * @param peer2 Second peer
1748 * @param value Value to be compare
1749 * @return Peer which precedes value in the network.
1751 static struct GNUNET_PeerIdentity
1752 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1753 const struct GNUNET_PeerIdentity *peer2,
1756 uint64_t peer1_value;
1757 uint64_t peer2_value;
1759 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1760 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1761 peer1_value = GNUNET_ntohll (peer1_value);
1762 peer2_value = GNUNET_ntohll (peer2_value);
1764 if (peer1_value == value)
1769 if (peer2_value == value)
1774 if (value < peer1_value && peer1_value < peer2_value)
1778 else if (value < peer2_value && peer2_value < peer1_value)
1782 else if (peer1_value < value && value < peer2_value)
1786 else if (peer2_value < value && value < peer1_value)
1790 else if (peer1_value < peer2_value && peer2_value < value)
1794 else // if (peer2_value < peer1_value && peer1_value < value)
1806 test_print_trail (struct GNUNET_PeerIdentity *trail,
1807 unsigned int trail_length)
1809 struct GNUNET_PeerIdentity print_peer;
1812 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1813 __FILE__, __func__,__LINE__,trail_length);
1814 for (i =0 ; i< trail_length; i++)
1816 print_peer = trail[i];
1817 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1818 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1825 * This is a test function to print all the entries of friend table.
1828 test_friend_peermap_print ()
1830 struct FriendInfo *friend;
1831 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1832 struct GNUNET_PeerIdentity print_peer;
1833 struct GNUNET_PeerIdentity key_ret;
1836 print_peer = my_identity;
1837 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1838 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1840 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1842 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1844 (const void **)&friend))
1846 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1847 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1848 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1856 * This is a test function, to print all the entries of finger table.
1859 test_finger_table_print()
1861 struct FingerInfo *finger;
1862 struct GNUNET_PeerIdentity print_peer;
1863 //struct Trail *trail;
1867 print_peer = my_identity;
1868 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1869 for (i = 0; i < MAX_FINGERS; i++)
1871 finger = &finger_table[i];
1873 if (GNUNET_NO == finger->is_present)
1876 print_peer = finger->finger_identity;
1877 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1878 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1881 for (j = 0; j < finger->trails_count; j++)
1883 trail = &finger->trail_list[j];
1884 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1885 struct Trail_Element *element;
1886 element = trail->trail_head;
1887 for (k = 0; k < trail->trail_length; k++)
1889 print_peer = element->peer;
1890 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1891 element = element->next;
1900 * Select the closest peer among two peers (which should not be same)
1901 * with respect to value and finger_table_index
1902 * NOTE: peer1 != peer2
1903 * @param peer1 First peer
1904 * @param peer2 Second peer
1905 * @param value Value relative to which we find the closest
1906 * @param is_predecessor Is value a predecessor or any other finger.
1907 * @return Closest peer among two peers.
1909 static struct GNUNET_PeerIdentity
1910 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1911 const struct GNUNET_PeerIdentity *peer2,
1913 unsigned int is_predecessor)
1915 /* This check is here to ensure that calling function never sends
1916 same peer value in peer1 and peer2. Remove it later. */
1917 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1918 if (1 == is_predecessor)
1919 return select_closest_predecessor (peer1, peer2, value);
1921 // TODO: Change name to something like select_closest_successor!!
1922 return select_closest_finger (peer1, peer2, value);
1927 * Iterate over the list of all the trails of a finger. In case the first
1928 * friend to reach the finger has reached trail threshold or is congested,
1929 * then don't select it. In case there multiple available good trails to reach
1930 * to Finger, choose the one with shortest trail length.
1931 * Note: We use length as parameter. But we can use any other suitable parameter
1933 * @param finger Finger Finger whose trail we have to select.
1934 * @return Trail Selected Trail.
1936 static struct Trail *
1937 select_finger_trail (struct FingerInfo *finger)
1939 struct FriendInfo *friend;
1940 struct Trail *current_finger_trail;
1941 struct Trail *best_trail = NULL;
1944 GNUNET_assert (finger->trails_count > 0);
1945 for (i = 0; i < finger->trails_count; i++)
1947 current_finger_trail = &finger->trail_list[i];
1949 /* No trail stored at this index. */
1950 if (GNUNET_NO == current_finger_trail->is_present)
1953 GNUNET_assert (NULL !=
1955 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1956 ¤t_finger_trail->trail_head->peer)));
1958 /* First friend to reach trail is not free. */
1959 if (GNUNET_YES == is_friend_congested (friend))
1962 if (NULL == best_trail ||
1963 best_trail->trail_length > current_finger_trail->trail_length)
1965 best_trail = current_finger_trail;
1974 * Compare FINGER entry with current successor. If finger's first friend of all
1975 * its trail is not congested and has not crossed trail threshold, then check
1976 * if finger peer identity is closer to final_destination_finger_value than
1977 * current_successor. If yes then update current_successor.
1978 * @param current_successor[in/out]
1982 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
1984 struct FingerInfo *finger;
1985 struct GNUNET_PeerIdentity closest_peer;
1986 struct Trail *finger_trail;
1989 /* Iterate over finger table. */
1990 for (i = 0; i < MAX_FINGERS; i++)
1992 finger = &finger_table[i];
1994 if (GNUNET_NO == finger->is_present)
1997 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1998 ¤t_closest_peer->best_known_destination))
2001 /* If I am my own finger, then ignore this finger. */
2002 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2006 /* If finger is a friend, we have already checked it in previous function. */
2007 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2008 &finger->finger_identity)))
2013 closest_peer = select_closest_peer (&finger->finger_identity,
2014 ¤t_closest_peer->best_known_destination,
2015 current_closest_peer->destination_finger_value,
2016 current_closest_peer->is_predecessor);
2018 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer))
2020 /* Choose one of the trail to reach to finger. */
2021 finger_trail = select_finger_trail (finger);
2023 /* In case no trail found, ignore this finger. */
2024 if (NULL == finger_trail)
2027 current_closest_peer->best_known_destination = closest_peer;
2028 current_closest_peer->next_hop = finger_trail->trail_head->peer;
2029 current_closest_peer->trail_id = finger_trail->trail_id;
2030 current_closest_peer->finger_table_index = i;
2038 * Compare friend entry with current successor.
2039 * If friend identity and current_successor is same, then do nothing.
2040 * If friend is not congested and has not crossed trail threshold, then check
2041 * if friend peer identity is closer to final_destination_finger_value than
2042 * current_successor. If yes then update current_successor.
2043 * @param cls closure
2044 * @param key current public key
2045 * @param value struct Closest_Peer
2046 * @return #GNUNET_YES if we should continue to iterate,
2047 * #GNUNET_NO if not.
2050 compare_friend_and_current_closest_peer (void *cls,
2051 const struct GNUNET_PeerIdentity *key,
2054 struct FriendInfo *friend = value;
2055 struct Closest_Peer *current_closest_peer = cls;
2056 struct GNUNET_PeerIdentity closest_peer;
2058 /* Friend is either congested or has crossed threshold. */
2059 if (GNUNET_YES == is_friend_congested (friend))
2062 /* If current_closest_peer and friend identity are same, then do nothing.*/
2063 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2064 ¤t_closest_peer->best_known_destination))
2070 closest_peer = select_closest_peer (&friend->id,
2071 ¤t_closest_peer->best_known_destination,
2072 current_closest_peer->destination_finger_value,
2073 current_closest_peer->is_predecessor);
2075 /* Is friend the closest successor? */
2076 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer))
2078 current_closest_peer->best_known_destination = friend->id;
2079 current_closest_peer->next_hop = friend->id;
2087 * Initialize current_successor to my_identity.
2088 * @param my_identity My peer identity
2089 * @return Updated closest_peer
2091 static struct Closest_Peer
2092 init_closest_peer (struct GNUNET_PeerIdentity my_identity,
2093 uint64_t destination_finger_value,
2094 unsigned int is_predecessor)
2096 struct Closest_Peer current_closest_peer;
2098 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2099 current_closest_peer.destination_finger_value = destination_finger_value;
2100 current_closest_peer.is_predecessor = is_predecessor;
2101 current_closest_peer.next_hop = my_identity;
2102 current_closest_peer.best_known_destination = my_identity;
2103 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
2104 return current_closest_peer;
2109 * Find locally best known peer, among your own identity, friend and finger list,
2110 * which is closest to given destination_finger_value.
2112 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2114 * @param destination_finger_value Peer closest to this value will be the next destination.
2115 * @param is_predecessor Are we looking for predecessor or finger?
2116 * @return Closest_Peer that contains all the relevant field to reach to
2117 * @a destination_finger_value
2119 static struct Closest_Peer
2120 find_local_best_known_next_hop (uint64_t destination_finger_value,
2121 unsigned int is_predecessor)
2123 struct Closest_Peer current_closest_peer;
2125 /* Initialize current_successor to my_identity. */
2126 current_closest_peer = init_closest_peer (my_identity,
2127 destination_finger_value,
2130 /* Compare each friend entry with current_successor and update current_successor
2131 * with friend if its closest. */
2134 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2135 &compare_friend_and_current_closest_peer,
2136 ¤t_closest_peer));
2138 /* Compare each finger entry with current_successor and update current_successor
2139 * with finger if its closest. */
2140 compare_finger_and_current_closest_peer (¤t_closest_peer);
2141 return current_closest_peer;
2146 * Construct a Put message and send it to target_peer.
2147 * @param key Key for the content
2148 * @param block_type Type of the block
2149 * @param options Routing options
2150 * @param desired_replication_level Desired replication count
2151 * @param best_known_dest Peer to which this message should reach eventually,
2152 * as it is best known destination to me.
2153 * @param intermediate_trail_id Trail id in case
2154 * @param target_peer Peer to which this message will be forwarded.
2155 * @param hop_count Number of hops traversed so far.
2156 * @param put_path_length Total number of peers in @a put_path
2157 * @param put_path Number of peers traversed so far
2158 * @param expiration_time When does the content expire
2159 * @param data Content to store
2160 * @param data_size Size of content @a data in bytes
2163 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2164 enum GNUNET_BLOCK_Type block_type,
2165 enum GNUNET_DHT_RouteOption options,
2166 uint32_t desired_replication_level,
2167 struct GNUNET_PeerIdentity best_known_dest,
2168 struct GNUNET_HashCode intermediate_trail_id,
2169 struct GNUNET_PeerIdentity *target_peer,
2171 uint32_t put_path_length,
2172 struct GNUNET_PeerIdentity *put_path,
2173 struct GNUNET_TIME_Absolute expiration_time,
2174 const void *data, size_t data_size)
2176 struct PeerPutMessage *ppm;
2177 struct P2PPendingMessage *pending;
2178 struct FriendInfo *target_friend;
2179 struct GNUNET_PeerIdentity *pp;
2182 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2183 sizeof (struct PeerPutMessage);
2184 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2186 put_path_length = 0;
2187 msize = data_size + sizeof (struct PeerPutMessage);
2190 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2192 DEBUG("msize = %lu\n",msize);
2197 GNUNET_assert (NULL !=
2199 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2200 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2201 pending->timeout = expiration_time;
2202 ppm = (struct PeerPutMessage *) &pending[1];
2203 pending->msg = &ppm->header;
2204 ppm->header.size = htons (msize);
2205 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2206 ppm->options = htonl (options);
2207 ppm->block_type = htonl (block_type);
2208 ppm->hop_count = htonl (hop_count + 1);
2209 ppm->desired_replication_level = htonl (desired_replication_level);
2210 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2211 ppm->best_known_destination = best_known_dest;
2212 ppm->intermediate_trail_id = intermediate_trail_id;
2214 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2215 ppm->put_path_length = htonl (put_path_length);
2216 if(put_path_length > 0)
2218 memcpy (pp, put_path,
2219 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2221 memcpy (&pp[put_path_length], data, data_size);
2222 GNUNET_assert (NULL != target_friend);
2223 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2224 target_friend->pending_count++;
2225 process_friend_queue (target_friend);
2230 * Handle the put request from the client.
2231 * @param key Key for the content
2232 * @param block_type Type of the block
2233 * @param options Routing options
2234 * @param desired_replication_level Desired replication count
2235 * @param expiration_time When does the content expire
2236 * @param data Content to store
2237 * @param data_size Size of content @a data in bytes
2240 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
2241 enum GNUNET_BLOCK_Type block_type,
2242 enum GNUNET_DHT_RouteOption options,
2243 uint32_t desired_replication_level,
2244 struct GNUNET_TIME_Absolute expiration_time,
2245 const void *data, size_t data_size)
2247 struct GNUNET_PeerIdentity best_known_dest;
2248 struct GNUNET_HashCode intermediate_trail_id;
2249 struct GNUNET_PeerIdentity next_hop;
2251 struct Closest_Peer successor;
2253 memcpy (&key_value, key, sizeof (uint64_t));
2254 key_value = GNUNET_ntohll (key_value);
2255 successor = find_local_best_known_next_hop (key_value,
2256 GDS_FINGER_TYPE_NON_PREDECESSOR);
2257 best_known_dest = successor.best_known_destination;
2258 next_hop = successor.next_hop;
2259 intermediate_trail_id = successor.trail_id;
2261 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2263 DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",GNUNET_h2s(key));
2264 /* I am the destination. */
2265 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2266 block_type,data_size,data);
2267 GDS_CLIENTS_process_put (options, block_type, 0,
2268 ntohl (desired_replication_level),
2269 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time.
2270 key, data, data_size);
2273 /* In case we are sending the request to a finger, then send across all of its
2275 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2276 best_known_dest, intermediate_trail_id, &next_hop,
2277 0, 1, &my_identity, expiration_time,
2282 * Construct a Get message and send it to target_peer.
2283 * @param key Key for the content
2284 * @param block_type Type of the block
2285 * @param options Routing options
2286 * @param desired_replication_level Desired replication count
2287 * @param best_known_dest Peer which should get this message. Same as target peer
2288 * if best_known_dest is a friend else its a finger.
2289 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2290 * in case it is a finger else set to 0.
2291 * @param target_peer Peer to which this message will be forwarded.
2292 * @param hop_count Number of hops traversed so far.
2293 * @param data Content to store
2294 * @param data_size Size of content @a data in bytes
2295 * @param get_path_length Total number of peers in @a get_path
2296 * @param get_path Number of peers traversed so far
2299 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2300 enum GNUNET_BLOCK_Type block_type,
2301 enum GNUNET_DHT_RouteOption options,
2302 uint32_t desired_replication_level,
2303 struct GNUNET_PeerIdentity best_known_dest,
2304 struct GNUNET_HashCode intermediate_trail_id,
2305 struct GNUNET_PeerIdentity *target_peer,
2307 uint32_t get_path_length,
2308 struct GNUNET_PeerIdentity *get_path)
2310 struct PeerGetMessage *pgm;
2311 struct P2PPendingMessage *pending;
2312 struct FriendInfo *target_friend;
2313 struct GNUNET_PeerIdentity *gp;
2316 msize = sizeof (struct PeerGetMessage) +
2317 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2319 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2324 GNUNET_assert (NULL !=
2326 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2328 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2329 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2330 pending->importance = 0; /* FIXME */
2331 pgm = (struct PeerGetMessage *) &pending[1];
2332 pending->msg = &pgm->header;
2333 pgm->header.size = htons (msize);
2334 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2335 pgm->get_path_length = htonl (get_path_length);
2336 pgm->best_known_destination = best_known_dest;
2338 pgm->intermediate_trail_id = intermediate_trail_id;
2339 pgm->hop_count = htonl (hop_count + 1);
2340 pgm->get_path_length = htonl (get_path_length);
2341 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2342 memcpy (gp, get_path,
2343 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2344 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2345 target_friend->pending_count++;
2346 process_friend_queue (target_friend);
2351 * Handle the get request from the client file. If I am destination do
2352 * datacache put and return. Else find the target friend and forward message
2354 * @param key Key for the content
2355 * @param block_type Type of the block
2356 * @param options Routing options
2357 * @param desired_replication_level Desired replication count
2360 GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key,
2361 enum GNUNET_BLOCK_Type block_type,
2362 enum GNUNET_DHT_RouteOption options,
2363 uint32_t desired_replication_level)
2365 struct Closest_Peer successor;
2366 struct GNUNET_PeerIdentity best_known_dest;
2367 struct GNUNET_HashCode intermediate_trail_id;
2370 memcpy (&key_value, key, sizeof (uint64_t));
2371 key_value = GNUNET_ntohll (key_value);
2373 successor = find_local_best_known_next_hop (key_value,
2374 GDS_FINGER_TYPE_NON_PREDECESSOR);
2376 best_known_dest = successor.best_known_destination;
2377 intermediate_trail_id = successor.trail_id;
2379 /* I am the destination. I have the data. */
2380 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2383 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2384 NULL, 0, 1, &my_identity, NULL,&my_identity);
2388 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2389 best_known_dest,intermediate_trail_id, &successor.next_hop,
2390 0, 1, &my_identity);
2395 * Send the get result to requesting client.
2397 * @param key Key of the requested data.
2398 * @param type Block type
2399 * @param target_peer Next peer to forward the message to.
2400 * @param source_peer Peer which has the data for the key.
2401 * @param put_path_length Number of peers in @a put_path
2402 * @param put_path Path taken to put the data at its stored location.
2403 * @param get_path_length Number of peers in @a get_path
2404 * @param get_path Path taken to reach to the location of the key.
2405 * @param expiration When will this result expire?
2406 * @param data Payload to store
2407 * @param data_size Size of the @a data
2410 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2411 enum GNUNET_BLOCK_Type type,
2412 const struct GNUNET_PeerIdentity *target_peer,
2413 const struct GNUNET_PeerIdentity *source_peer,
2414 unsigned int put_path_length,
2415 const struct GNUNET_PeerIdentity *put_path,
2416 unsigned int get_path_length,
2417 const struct GNUNET_PeerIdentity *get_path,
2418 struct GNUNET_TIME_Absolute expiration,
2419 const void *data, size_t data_size)
2421 struct PeerGetResultMessage *get_result;
2422 struct GNUNET_PeerIdentity *paths;
2423 struct P2PPendingMessage *pending;
2424 struct FriendInfo *target_friend;
2425 int current_path_index;
2428 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2430 sizeof (struct PeerGetResultMessage);
2432 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2434 put_path_length = 0;
2435 msize = msize - put_path_length * sizeof (struct GNUNET_PeerIdentity);
2438 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2443 current_path_index = 0;
2444 if(get_path_length > 0)
2446 current_path_index = search_my_index(get_path, get_path_length);
2447 if (-1 == current_path_index)
2452 if ((get_path_length + 1) == current_path_index)
2454 DEBUG ("Peer found twice in get path. Not allowed \n");
2459 if (0 == current_path_index)
2461 DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",GNUNET_h2s(key),GNUNET_i2s(&my_identity));
2462 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2463 get_path, put_path_length,
2464 put_path, type, data_size, data);
2468 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2469 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2470 pending->importance = 0;
2471 get_result = (struct PeerGetResultMessage *)&pending[1];
2472 pending->msg = &get_result->header;
2473 get_result->header.size = htons (msize);
2474 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2475 get_result->key = *key;
2476 get_result->querying_peer = *source_peer;
2477 get_result->expiration_time = GNUNET_TIME_absolute_hton (expiration);
2478 get_result->get_path_length = htonl (get_path_length);
2479 get_result->put_path_length = htonl (put_path_length);
2480 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2481 memcpy (paths, put_path,
2482 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2483 memcpy (&paths[put_path_length], get_path,
2484 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2485 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2487 GNUNET_assert (NULL !=
2489 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2490 &get_path[current_path_index - 1])));
2491 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2492 target_friend->pending_count++;
2493 process_friend_queue (target_friend);
2498 * Randomly choose one of your friends (which is not congested and have not crossed
2499 * trail threshold) from the friend_peermap
2500 * @return Friend Randomly chosen friend.
2501 * NULL in case friend peermap is empty, or all the friends are either
2502 * congested or have crossed trail threshold.
2504 static struct FriendInfo *
2505 select_random_friend ()
2507 unsigned int current_size;
2510 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2511 struct GNUNET_PeerIdentity key_ret;
2512 struct FriendInfo *friend;
2514 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2517 if (0 == current_size)
2520 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2521 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2523 /* Iterate till you don't reach to index. */
2524 for (j = 0; j < index ; j++)
2525 GNUNET_assert (GNUNET_YES ==
2526 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2530 /* Reset the index in friend peermap to 0 as we reached to the end. */
2531 if (j == current_size)
2534 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2535 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2539 /* Get the friend stored at the index, j*/
2540 GNUNET_assert (GNUNET_YES ==
2541 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2543 (const void **)&friend));
2545 /* This friend is not congested and has not crossed trail threshold. */
2546 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2547 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2553 } while (j != index);
2555 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2561 * Compute 64 bit value of finger_identity corresponding to a finger index using
2563 * For all fingers, n.finger[i] = n + pow (2,i),
2564 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2565 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2566 * @param finger_index Index corresponding to which we calculate 64 bit value.
2567 * @return 64 bit value.
2570 compute_finger_identity_value (unsigned int finger_index)
2574 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2575 my_id64 = GNUNET_ntohll (my_id64);
2577 /* Are we looking for immediate predecessor? */
2578 if (PREDECESSOR_FINGER_ID == finger_index)
2579 return (my_id64 - 1);
2582 uint64_t add = (uint64_t)1 << finger_index;
2583 return (my_id64 + add);
2589 * Choose a random friend. Calculate the next finger identity to search,from
2590 * current_search_finger_index. Start looking for the trail to reach to
2591 * finger identity through this random friend.
2593 * @param cls closure for this task
2596 send_find_finger_trail_message (void *cls)
2598 struct FriendInfo *target_friend;
2599 struct GNUNET_HashCode trail_id;
2600 struct GNUNET_HashCode intermediate_trail_id;
2601 unsigned int is_predecessor = 0;
2602 uint64_t finger_id_value;
2604 /* Schedule another send_find_finger_trail_message task. After one round of
2605 * finger search, this time is exponentially backoff. */
2606 find_finger_trail_task_next_send_time.rel_value_us =
2607 find_finger_trail_task_next_send_time.rel_value_us +
2608 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2609 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2610 find_finger_trail_task =
2611 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2612 &send_find_finger_trail_message,
2615 /* No space in my routing table. (Source and destination peers also store entries
2616 * in their routing table). */
2617 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2620 target_friend = select_random_friend ();
2621 if (NULL == target_friend)
2626 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2627 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2630 /* Generate a unique trail id for trail we are trying to setup. */
2631 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2632 &trail_id, sizeof (trail_id));
2633 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2634 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2635 target_friend->id, target_friend, 0, NULL,
2636 is_predecessor, trail_id,
2637 intermediate_trail_id);
2642 * In case there are already maximum number of possible trails to reach to a
2643 * finger, then check if the new trail's length is lesser than any of the
2645 * If yes then replace that old trail by new trail.
2647 * Note: Here we are taking length as a parameter to choose the best possible
2648 * trail, but there could be other parameters also like:
2649 * 1. duration of existence of a trail - older the better.
2650 * 2. if the new trail is completely disjoint than the
2651 * other trails, then may be choosing it is better.
2653 * @param finger Finger
2654 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2655 * including the endpoints.
2656 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2657 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2660 select_and_replace_trail (struct FingerInfo *finger,
2661 const struct GNUNET_PeerIdentity *new_trail,
2662 unsigned int new_trail_length,
2663 struct GNUNET_HashCode new_trail_id)
2665 struct Trail *current_trail;
2666 unsigned int largest_trail_length;
2667 unsigned int largest_trail_index;
2668 struct Trail_Element *trail_element;
2669 struct GNUNET_PeerIdentity *next_hop;
2672 largest_trail_length = new_trail_length;
2673 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2675 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2677 for (i = 0; i < finger->trails_count; i++)
2679 current_trail = &finger->trail_list[i];
2680 GNUNET_assert (GNUNET_YES == current_trail->is_present);
2681 if (current_trail->trail_length > largest_trail_length)
2683 largest_trail_length = current_trail->trail_length;
2684 largest_trail_index = i;
2688 /* New trail is not better than existing ones. Send trail teardown. */
2689 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2691 next_hop = GDS_ROUTING_get_next_hop (new_trail_id, GDS_ROUTING_SRC_TO_DEST);
2692 GDS_ROUTING_remove_trail (new_trail_id);
2693 GDS_NEIGHBOURS_send_trail_teardown (&new_trail_id,
2694 GDS_ROUTING_SRC_TO_DEST,
2699 /* Send trail teardown message across the replaced trail. */
2700 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2701 next_hop = GDS_ROUTING_get_next_hop (replace_trail->trail_id, GDS_ROUTING_SRC_TO_DEST);
2702 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2703 GDS_NEIGHBOURS_send_trail_teardown (&replace_trail->trail_id,
2704 GDS_ROUTING_SRC_TO_DEST,
2707 /* Free the trail. */
2708 while (NULL != (trail_element = replace_trail->trail_head))
2710 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2711 replace_trail->trail_tail, trail_element);
2712 GNUNET_free_non_null (trail_element);
2715 /* Add new trial at that location. */
2716 replace_trail->is_present = GNUNET_YES;
2717 replace_trail->trail_length = new_trail_length;
2718 replace_trail->trail_id = new_trail_id;
2720 for (i = 0; i < new_trail_length; i++)
2722 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2723 element->peer = new_trail[i];
2725 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2726 replace_trail->trail_tail,
2729 /* FIXME: URGENT Are we adding the trail back to the list. */
2734 * Check if the new trail to reach to finger is unique or do we already have
2735 * such a trail present for finger.
2736 * @param existing_finger Finger identity
2737 * @param new_trail New trail to reach @a existing_finger
2738 * @param trail_length Total number of peers in new_trail.
2739 * @return #GNUNET_YES if the new trail is unique
2740 * #GNUNET_NO if same trail is already present.
2743 is_new_trail_unique (struct FingerInfo *existing_finger,
2744 const struct GNUNET_PeerIdentity *new_trail,
2745 unsigned int trail_length)
2747 struct Trail *current_trail;
2748 struct Trail_Element *trail_element;
2752 GNUNET_assert (existing_finger->trails_count > 0);
2754 /* Iterate over list of trails. */
2755 for (i = 0; i < existing_finger->trails_count; i++)
2757 current_trail = &(existing_finger->trail_list[i]);
2758 if(GNUNET_NO == current_trail->is_present)
2761 /* New trail and existing trail length are not same. */
2762 if (current_trail->trail_length != trail_length)
2767 trail_element = current_trail->trail_head;
2768 for (j = 0; j < current_trail->trail_length; j++)
2770 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2771 &trail_element->peer))
2775 trail_element = trail_element->next;
2782 * FIXME; In case of multiple trails, we may have a case where a trail from in
2783 * between has been removed, then we should try to find a free slot , not simply
2784 * add a trail at then end of the list.
2785 * Add a new trail at a free slot in trail array of existing finger.
2786 * @param existing_finger Finger
2787 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2788 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2789 * @param new_finger_trail_id Unique identifier of the trail.
2792 add_new_trail (struct FingerInfo *existing_finger,
2793 const struct GNUNET_PeerIdentity *new_trail,
2794 unsigned int new_trail_length,
2795 struct GNUNET_HashCode new_trail_id)
2797 struct FriendInfo *friend;
2798 struct Trail *trail;
2802 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2806 for (i = 0; i < existing_finger->trails_count; i++)
2808 if (GNUNET_NO == existing_finger->trail_list[i].is_present)
2815 if (-1 == free_slot)
2818 trail = &existing_finger->trail_list[free_slot];
2819 GNUNET_assert (GNUNET_NO == trail->is_present);
2820 trail->trail_id = new_trail_id;
2821 trail->trail_length = new_trail_length;
2822 existing_finger->trails_count++;
2823 trail->is_present = GNUNET_YES;
2824 if (0 == new_trail_length)
2826 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2827 &existing_finger->finger_identity);
2831 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2834 GNUNET_assert (NULL != friend);
2835 friend->trails_count++;
2836 for (i = 0; i < new_trail_length; i++)
2838 struct Trail_Element *element;
2840 element = GNUNET_new (struct Trail_Element);
2841 element->peer = new_trail[i];
2842 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2847 existing_finger->trail_list[free_slot].trail_head = trail->trail_head;
2848 existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail;
2849 existing_finger->trail_list[free_slot].trail_length = new_trail_length;
2850 existing_finger->trail_list[free_slot].trail_id = new_trail_id;
2851 existing_finger->trail_list[free_slot].is_present = GNUNET_YES;
2857 * FIXME; In case of multiple trails, we may have a case where a trail from in
2858 * between has been removed, then we should try to find a free slot , not simply
2859 * add a trail at then end of the list.
2860 * Add a new trail at a free slot in trail array of existing finger.
2861 * @param existing_finger Finger
2862 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2863 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2864 * @param new_finger_trail_id Unique identifier of the trail.
2867 add_new_trail (struct FingerInfo *existing_finger,
2868 const struct GNUNET_PeerIdentity *new_trail,
2869 unsigned int new_trail_length,
2870 struct GNUNET_HashCode new_trail_id)
2872 struct Trail *trail;
2873 struct FriendInfo *first_friend;
2877 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2881 index = existing_finger->trails_count;
2882 trail = &existing_finger->trail_list[index];
2883 GNUNET_assert (GNUNET_NO == trail->is_present);
2884 trail->trail_id = new_trail_id;
2885 trail->trail_length = new_trail_length;
2886 existing_finger->trails_count++;
2887 trail->is_present = GNUNET_YES;
2889 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2890 &existing_finger->finger_identity)));
2891 /* If finger is a friend then we never call this function. */
2892 GNUNET_assert (new_trail_length > 0);
2894 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2896 first_friend->trails_count++;
2898 for (i = 0; i < new_trail_length; i++)
2900 struct Trail_Element *element;
2902 element = GNUNET_new (struct Trail_Element);
2903 element->peer = new_trail[i];
2904 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2908 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2909 existing_finger->trail_list[index].trail_head = trail->trail_head;
2910 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2911 existing_finger->trail_list[index].trail_length = new_trail_length;
2912 existing_finger->trail_list[index].trail_id = new_trail_id;
2913 existing_finger->trail_list[index].is_present = GNUNET_YES;
2918 * Get the next hop to send trail teardown message from routing table and
2919 * then delete the entry from routing table. Send trail teardown message for a
2920 * specific trail of a finger.
2921 * @param finger Finger whose trail is to be removed.
2922 * @param trail List of peers in trail from me to a finger, NOT including
2926 send_trail_teardown (struct FingerInfo *finger,
2927 struct Trail *trail)
2929 struct FriendInfo *friend;
2930 struct GNUNET_PeerIdentity *next_hop;
2932 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2933 GDS_ROUTING_SRC_TO_DEST);
2934 if (NULL == next_hop)
2936 // DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d",
2937 // GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length);
2940 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2943 GNUNET_assert(GNUNET_YES == trail->is_present);
2944 if (trail->trail_length > 0)
2946 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2947 &trail->trail_head->peer);
2951 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2952 &finger->finger_identity);
2957 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2958 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
2961 if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)
2962 && (0 == trail->trail_length))
2964 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2965 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
2968 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2969 friend->trails_count--;
2970 GDS_NEIGHBOURS_send_trail_teardown (&trail->trail_id,
2971 GDS_ROUTING_SRC_TO_DEST,
2977 * Send trail teardown message across all the trails to reach to finger.
2978 * @param finger Finger whose all the trail should be freed.
2981 send_all_finger_trails_teardown (struct FingerInfo *finger)
2985 for (i = 0; i < finger->trails_count; i++)
2987 struct Trail *trail;
2989 trail = &finger->trail_list[i];
2990 if (GNUNET_YES == trail->is_present)
2992 send_trail_teardown (finger, trail);
2993 trail->is_present = GNUNET_NO;
3000 * Free a specific trail
3001 * @param trail List of peers to be freed.
3004 free_trail (struct Trail *trail)
3006 struct Trail_Element *trail_element;
3008 while (NULL != (trail_element = trail->trail_head))
3010 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
3013 GNUNET_free_non_null (trail_element);
3015 trail->trail_head = NULL;
3016 trail->trail_tail = NULL;
3021 * Free finger and its trail.
3022 * @param finger Finger to be freed.
3023 * @param finger_table_index Index at which finger is stored.
3026 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
3028 struct Trail *trail;
3030 for (i = 0; i < finger->trails_count; i++)
3032 trail = &finger->trail_list[i];
3033 if (GNUNET_NO == trail->is_present)
3036 if (trail->trail_length > 0)
3038 trail->is_present = GNUNET_NO;
3041 finger->is_present = GNUNET_NO;
3042 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
3047 * Add a new entry in finger table at finger_table_index.
3048 * In case I am my own finger, then we don't have a trail. In case of a friend,
3049 * we have a trail with unique id and '0' trail length.
3050 * In case a finger is a friend, then increment the trails count of the friend.
3051 * @param finger_identity Peer Identity of new finger
3052 * @param finger_trail Trail to reach from me to finger (excluding both end points).
3053 * @param finger_trail_length Total number of peers in @a finger_trail.
3054 * @param trail_id Unique identifier of the trail.
3055 * @param finger_table_index Index in finger table.
3058 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
3059 const struct GNUNET_PeerIdentity *finger_trail,
3060 unsigned int finger_trail_length,
3061 struct GNUNET_HashCode trail_id,
3062 unsigned int finger_table_index)
3064 struct FingerInfo *new_entry;
3065 struct FriendInfo *first_trail_hop;
3066 struct Trail *trail;
3069 new_entry = GNUNET_new (struct FingerInfo);
3070 new_entry->finger_identity = finger_identity;
3071 new_entry->finger_table_index = finger_table_index;
3072 new_entry->is_present = GNUNET_YES;
3074 /* If the new entry is my own identity. */
3075 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3078 new_entry->trails_count = 0;
3079 finger_table[finger_table_index] = *new_entry;
3080 GNUNET_free (new_entry);
3084 /* Finger is a friend. */
3085 if (0 == finger_trail_length)
3087 new_entry->trail_list[0].trail_id = trail_id;
3088 new_entry->trails_count = 1;
3089 new_entry->trail_list[0].is_present = GNUNET_YES;
3090 new_entry->trail_list[0].trail_length = 0;
3091 new_entry->trail_list[0].trail_head = NULL;
3092 new_entry->trail_list[0].trail_tail = NULL;
3093 finger_table[finger_table_index] = *new_entry;
3094 GNUNET_assert (NULL !=
3096 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3097 &finger_identity)));
3099 first_trail_hop->trails_count++;
3100 GNUNET_free (new_entry);
3104 GNUNET_assert (NULL !=
3106 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3107 &finger_trail[0])));
3108 new_entry->trails_count = 1;
3109 first_trail_hop->trails_count++;
3110 /* Copy the finger trail into trail. */
3111 trail = &new_entry->trail_list[0];
3112 for(i = 0; i < finger_trail_length; i++)
3114 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3116 element->next = NULL;
3117 element->prev = NULL;
3118 element->peer = finger_trail[i];
3119 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3124 /* Add trail to trail list. */
3125 trail->trail_length = finger_trail_length;
3126 trail->trail_id = trail_id;
3127 trail->is_present = GNUNET_YES;
3128 finger_table[finger_table_index] = *new_entry;
3129 GNUNET_free (new_entry);
3134 * Periodic task to verify current successor. There can be multiple trails to reach
3135 * to successor, choose the shortest one and send verify successor message
3136 * across that trail.
3138 * @param cls closure for this task
3141 send_verify_successor_message (void *cls)
3143 struct FriendInfo *target_friend;
3144 struct GNUNET_HashCode trail_id;
3145 struct Trail *trail;
3146 struct Trail_Element *element;
3147 unsigned int trail_length;
3149 struct FingerInfo *successor;
3151 successor = &finger_table[0];
3153 /* This task will be scheduled when the result for Verify Successor is received. */
3154 send_verify_successor_task = NULL;
3156 /* When verify successor is being called for first time *for current context*
3157 * cls will be NULL. If send_verify_successor_retry_task is not NO_TASK, we
3158 * must cancel the retry task scheduled for verify_successor of previous
3163 /* FIXME: Here we are scheduling a new verify successor task, as we
3164 got a new successor. But a send verify successor task may be in progress.
3165 1. We need to be sure that this is indeed a new successor. As this function
3166 is called even if we add a new trail to reach t old successor.
3167 2. Assuming the new successor is different, then verify successor message
3168 * to old successor may be following stages.
3169 * --> Waiting for verify successor result. Don't wait anymore. there is
3170 * no trail to reach from old successor to me, hence, routing
3172 * --> Waiting for notify confirmation. again don't wait for it. notify
3173 * confirmation will not succeded.
3175 if (send_verify_successor_retry_task != NULL)
3177 /* FIXME: Are we scheduling retry task as soon as we send verify message.
3178 If yes then here before making this task, first check if the message
3179 is for the same peer again. */
3180 struct VerifySuccessorContext *old_ctx =
3181 GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
3182 /* old_ctx must not be NULL, as the retry task had been scheduled */
3183 GNUNET_assert(NULL != old_ctx);
3184 GNUNET_free(old_ctx);
3185 /* FIXME: Why don't we reset the task to NO_TASK here? */
3188 struct VerifySuccessorContext *ctx;
3189 ctx = GNUNET_new(struct VerifySuccessorContext);
3191 ctx->num_retries_scheduled++;
3192 send_verify_successor_retry_task =
3193 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3194 &send_verify_successor_message,
3199 /* This is a retry attempt for verify_successor for a previous context */
3200 struct VerifySuccessorContext *ctx;
3203 ctx->num_retries_scheduled++;
3204 send_verify_successor_retry_task =
3205 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3206 &send_verify_successor_message,
3210 /* Among all the trails to reach to successor, select first one which is present.*/
3211 for (i = 0; i < successor->trails_count; i++)
3213 trail = &successor->trail_list[i];
3214 if(GNUNET_YES == trail->is_present)
3218 /* No valid trail found to reach to successor. */
3219 if (i == successor->trails_count)
3222 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3223 &successor->finger_identity));
3224 /* Trail stored at this index. */
3225 GNUNET_assert (GNUNET_YES == trail->is_present);
3226 trail_id = trail->trail_id;
3227 if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST))
3229 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
3230 GNUNET_i2s (&my_identity),
3231 GNUNET_h2s (&trail->trail_id),
3236 trail_length = trail->trail_length;
3237 if (trail_length > 0)
3239 /* Copy the trail into peer list. */
3240 struct GNUNET_PeerIdentity peer_list[trail_length];
3241 element = trail->trail_head;
3242 for(i = 0; i < trail_length; i++)
3244 peer_list[i] = element->peer;
3245 element = element->next;
3247 GNUNET_assert (NULL != (target_friend =
3248 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3250 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3251 successor->finger_identity,
3252 trail_id, peer_list, trail_length,
3257 GNUNET_assert (NULL != (target_friend =
3258 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3259 &successor->finger_identity)));
3260 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3261 successor->finger_identity,
3269 * FIXME: should this be a periodic task, incrementing the search finger index?
3270 * Update the current search finger index.
3271 * @a finger_identity
3272 * @a finger_table_index
3275 update_current_search_finger_index (unsigned int finger_table_index)
3277 struct FingerInfo *successor;
3279 /* FIXME correct this: only move current index periodically */
3280 if (finger_table_index != current_search_finger_index)
3283 successor = &finger_table[0];
3284 GNUNET_assert (GNUNET_YES == successor->is_present);
3286 /* We were looking for immediate successor. */
3287 if (0 == current_search_finger_index)
3289 current_search_finger_index = PREDECESSOR_FINGER_ID;
3290 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &successor->finger_identity))
3292 if (NULL == send_verify_successor_task)
3294 send_verify_successor_task =
3295 GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3301 current_search_finger_index = current_search_finger_index - 1;
3307 * Get the least significant bit set in val.
3310 * @return Position of first bit set, 65 in case of error.
3313 find_set_bit (uint64_t val)
3333 return 65; /* Some other bit was set to 1 as well. */
3340 * Calculate finger_table_index from initial 64 bit finger identity value that
3341 * we send in trail setup message.
3342 * @param ultimate_destination_finger_value Value that we calculated from our
3343 * identity and finger_table_index.
3344 * @param is_predecessor Is the entry for predecessor or not?
3345 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3346 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3349 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3350 unsigned int is_predecessor)
3354 unsigned int finger_table_index;
3356 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3357 my_id64 = GNUNET_ntohll (my_id64);
3359 /* Is this a predecessor finger? */
3360 if (1 == is_predecessor)
3362 diff = my_id64 - ultimate_destination_finger_value;
3364 finger_table_index = PREDECESSOR_FINGER_ID;
3366 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3371 diff = ultimate_destination_finger_value - my_id64;
3372 finger_table_index = find_set_bit (diff);
3374 return finger_table_index;
3379 * Remove finger and its associated data structures from finger table.
3380 * @param existing_finger Finger to be removed which is in finger table.
3381 * @param finger_table_index Index in finger table where @a existing_finger
3385 remove_existing_finger (struct FingerInfo *existing_finger,
3386 unsigned int finger_table_index)
3388 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3390 /* If I am my own finger, then we have no trails. */
3391 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3394 existing_finger->is_present = GNUNET_NO;
3395 memset ((void *)&finger_table[finger_table_index], 0,
3396 sizeof (finger_table[finger_table_index]));
3400 /* For all other fingers, send trail teardown across all the trails to reach
3401 finger, and free the finger. */
3402 send_all_finger_trails_teardown (existing_finger);
3403 free_finger (existing_finger, finger_table_index);
3408 * Check if there is already an entry in finger_table at finger_table_index.
3409 * We get the finger_table_index from 64bit finger value we got from the network.
3410 * -- If yes, then select the closest finger.
3411 * -- If new and existing finger are same, then check if you can store more
3413 * -- If yes then add trail, else keep the best trails to reach to the
3415 * -- If the new finger is closest, remove the existing entry, send trail
3416 * teardown message across all the trails to reach the existing entry.
3417 * Add the new finger.
3418 * -- If new and existing finger are different, and existing finger is closest
3420 * -- Update current_search_finger_index.
3421 * @param finger_identity Peer Identity of new finger
3422 * @param finger_trail Trail to reach the new finger
3423 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3424 * @param is_predecessor Is this entry for predecessor in finger_table?
3425 * @param finger_value 64 bit value of finger identity that we got from network.
3426 * @param finger_trail_id Unique identifier of @finger_trail.
3429 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3430 const struct GNUNET_PeerIdentity *finger_trail,
3431 unsigned int finger_trail_length,
3432 unsigned int is_predecessor,
3433 uint64_t finger_value,
3434 struct GNUNET_HashCode finger_trail_id)
3436 struct FingerInfo *existing_finger;
3437 struct GNUNET_PeerIdentity closest_peer;
3438 struct FingerInfo *successor;
3439 unsigned int finger_table_index;
3441 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3442 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3444 /* Invalid finger_table_index. */
3445 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3447 GNUNET_break_op (0);
3451 /* Check if new entry is same as successor. */
3452 if ((0 != finger_table_index) &&
3453 (PREDECESSOR_FINGER_ID != finger_table_index))
3455 successor = &finger_table[0];
3456 if (GNUNET_NO == successor->is_present)
3458 GNUNET_break (0); //ASSERTION FAILS HERE. FIXME
3461 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3462 &successor->finger_identity))
3464 if (0 == fingers_round_count)
3466 find_finger_trail_task_next_send_time =
3467 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3470 fingers_round_count--;
3471 current_search_finger_index = 0;
3472 GNUNET_STATISTICS_update (GDS_stats,
3474 ("# FINGERS_COUNT"), (int64_t) total_fingers_found,
3476 total_fingers_found = 0;
3480 struct FingerInfo prev_finger;
3481 prev_finger = finger_table[finger_table_index - 1];
3482 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3483 &prev_finger.finger_identity))
3485 current_search_finger_index--;
3490 total_fingers_found++;
3491 existing_finger = &finger_table[finger_table_index];
3493 /* No entry present in finger_table for given finger map index. */
3494 if (GNUNET_NO == existing_finger->is_present)
3496 /* Shorten the trail if possible. */
3497 add_new_finger (finger_identity, finger_trail,
3498 finger_trail_length,
3499 finger_trail_id, finger_table_index);
3500 update_current_search_finger_index (finger_table_index);
3504 /* If existing entry and finger identity are not same. */
3505 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3508 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3513 /* If the new finger is the closest peer. */
3514 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer))
3516 remove_existing_finger (existing_finger, finger_table_index);
3517 add_new_finger (finger_identity, finger_trail, finger_trail_length,
3518 finger_trail_id, finger_table_index);
3522 /* Existing finger is the closest one. We need to send trail teardown
3523 across the trail setup in routing table of all the peers. */
3524 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3526 if (finger_trail_length > 0)
3527 GDS_NEIGHBOURS_send_trail_teardown (&finger_trail_id,
3528 GDS_ROUTING_SRC_TO_DEST,
3531 GDS_NEIGHBOURS_send_trail_teardown (&finger_trail_id,
3532 GDS_ROUTING_SRC_TO_DEST,
3539 /* If both new and existing entry are same as my_identity, then do nothing. */
3540 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3546 /* If there is space to store more trails. */
3547 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3548 add_new_trail (existing_finger, finger_trail,
3549 finger_trail_length, finger_trail_id);
3551 select_and_replace_trail (existing_finger, finger_trail,
3552 finger_trail_length, finger_trail_id);
3554 update_current_search_finger_index (finger_table_index);
3560 * Core handler for P2P put messages.
3561 * @param cls closure
3562 * @param peer sender of the request
3563 * @param message message
3564 * @return #GNUNET_OK to keep the connection open,
3565 * #GNUNET_SYSERR to close it (signal serious error)
3568 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3569 const struct GNUNET_MessageHeader *message)
3571 struct PeerPutMessage *put;
3572 struct GNUNET_PeerIdentity *put_path;
3573 struct GNUNET_PeerIdentity current_best_known_dest;
3574 struct GNUNET_PeerIdentity best_known_dest;
3575 struct GNUNET_HashCode received_intermediate_trail_id;
3576 struct GNUNET_HashCode intermediate_trail_id;
3577 struct GNUNET_PeerIdentity next_hop;
3578 struct GNUNET_PeerIdentity *next_routing_hop;
3579 enum GNUNET_DHT_RouteOption options;
3580 struct GNUNET_HashCode test_key;
3585 size_t payload_size;
3588 msize = ntohs (message->size);
3589 if (msize < sizeof (struct PeerPutMessage))
3591 GNUNET_break_op (0);
3595 put = (struct PeerPutMessage *) message;
3596 putlen = ntohl (put->put_path_length);
3598 sizeof (struct PeerPutMessage) +
3599 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3601 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3603 GNUNET_break_op (0);
3606 GNUNET_STATISTICS_update (GDS_stats,
3608 ("# Bytes received from other peers"), (int64_t) msize,
3611 current_best_known_dest = put->best_known_destination;
3612 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3613 payload = &put_path[putlen];
3614 options = ntohl (put->options);
3615 received_intermediate_trail_id = put->intermediate_trail_id;
3616 hop_count = ntohl(put->hop_count);
3617 payload_size = msize - (sizeof (struct PeerPutMessage) +
3618 putlen * sizeof (struct GNUNET_PeerIdentity));
3620 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3621 payload, payload_size, &test_key))
3624 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3626 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3627 GNUNET_break_op (0);
3628 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3629 "PUT with key `%s' for block with key %s\n",
3630 put_s, GNUNET_h2s_full (&test_key));
3631 GNUNET_free (put_s);
3636 GNUNET_break_op (0);
3639 /* cannot verify, good luck */
3643 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3645 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3646 ntohl (put->block_type),
3647 GNUNET_BLOCK_EO_NONE,
3649 NULL, 0, /* bloom filer */
3650 NULL, 0, /* xquery */
3651 payload, payload_size))
3653 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3654 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3657 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3658 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3659 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3660 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3661 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3662 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3664 GNUNET_break_op (0);
3669 /* Check if you are already a part of put path. */
3671 for (i = 0; i < putlen; i++)
3673 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3680 /* Add yourself to the list. */
3681 struct GNUNET_PeerIdentity pp[putlen + 1];
3682 //if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3685 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3686 pp[putlen] = my_identity;
3692 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3693 struct Closest_Peer successor;
3694 key_value = GNUNET_ntohll (key_value);
3695 successor = find_local_best_known_next_hop (key_value,
3696 GDS_FINGER_TYPE_NON_PREDECESSOR);
3697 next_hop = successor.next_hop;
3698 intermediate_trail_id = successor.trail_id;
3699 best_known_dest = successor.best_known_destination;
3701 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3703 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3704 GDS_ROUTING_SRC_TO_DEST);
3705 if (NULL != next_routing_hop)
3707 next_hop = *next_routing_hop;
3708 intermediate_trail_id = received_intermediate_trail_id;
3709 best_known_dest = current_best_known_dest;
3713 GDS_CLIENTS_process_put (options,
3714 ntohl (put->block_type),
3716 ntohl (put->desired_replication_level),
3718 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3723 /* I am the final destination */
3724 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3726 DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",GNUNET_h2s(&put->key));
3727 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3728 &(put->key),putlen, pp, ntohl (put->block_type),
3729 payload_size, payload);
3731 GDS_NEIGHBOURS_send_put (&put->key,
3732 ntohl (put->block_type),ntohl (put->options),
3733 ntohl (put->desired_replication_level),
3734 best_known_dest, intermediate_trail_id, &next_hop,
3735 hop_count, putlen, pp,
3736 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3737 payload, payload_size);
3744 * FIXME: Check for loop in the request. If you already are part of get path,
3745 * then you need to reset the get path length.
3746 * Core handler for p2p get requests.
3748 * @param cls closure
3749 * @param peer sender of the request
3750 * @param message message
3751 * @return #GNUNET_OK to keep the connection open,
3752 * #GNUNET_SYSERR to close it (signal serious error)
3755 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3756 const struct GNUNET_MessageHeader *message)
3758 const struct PeerGetMessage *get;
3759 const struct GNUNET_PeerIdentity *get_path;
3760 struct GNUNET_PeerIdentity best_known_dest;
3761 struct GNUNET_PeerIdentity current_best_known_dest;
3762 struct GNUNET_HashCode intermediate_trail_id;
3763 struct GNUNET_HashCode received_intermediate_trail_id;
3764 struct Closest_Peer successor;
3765 struct GNUNET_PeerIdentity next_hop;
3766 struct GNUNET_PeerIdentity *next_routing_hop;
3767 uint32_t get_length;
3772 msize = ntohs (message->size);
3773 if (msize < sizeof (struct PeerGetMessage))
3775 GNUNET_break_op (0);
3779 get = (const struct PeerGetMessage *)message;
3780 get_length = ntohl (get->get_path_length);
3782 sizeof (struct PeerGetMessage) +
3783 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3785 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3787 GNUNET_break_op (0);
3791 current_best_known_dest = get->best_known_destination;
3792 received_intermediate_trail_id = get->intermediate_trail_id;
3793 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3794 hop_count = get->hop_count;
3798 GNUNET_STATISTICS_update (GDS_stats,
3800 ("# Bytes received from other peers"), msize,
3803 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3804 key_value = GNUNET_ntohll (key_value);
3806 /* Check if you are already a part of get path. */
3808 for (i = 0; i < get_length; i++)
3810 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &get_path[i]))
3817 /* Add yourself in the get path. */
3818 struct GNUNET_PeerIdentity gp[get_length + 1];
3819 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3820 gp[get_length] = my_identity;
3821 get_length = get_length + 1;
3822 GDS_CLIENTS_process_get (get->options, get->block_type, hop_count,
3823 get->desired_replication_level, get->get_path_length,
3827 successor = find_local_best_known_next_hop (key_value,
3828 GDS_FINGER_TYPE_NON_PREDECESSOR);
3829 next_hop = successor.next_hop;
3830 best_known_dest = successor.best_known_destination;
3831 intermediate_trail_id = successor.trail_id;
3832 /* I am not the final destination. I am part of trail to reach final dest. */
3833 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3835 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3836 GDS_ROUTING_SRC_TO_DEST);
3837 if (NULL != next_routing_hop)
3839 next_hop = *next_routing_hop;
3840 best_known_dest = current_best_known_dest;
3841 intermediate_trail_id = received_intermediate_trail_id;
3845 /* I am the final destination. */
3846 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3848 if (1 == get_length)
3850 DEBUG("\n GET_REQUEST DONE for key = %s",GNUNET_h2s(&get->key));
3851 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0,
3852 NULL, 0, 1, &my_identity, NULL,&my_identity);
3856 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3857 get_length, gp, &gp[get_length - 2],
3864 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3865 get->desired_replication_level, best_known_dest,
3866 intermediate_trail_id, &next_hop, hop_count,
3874 * Core handler for get result
3875 * @param cls closure
3876 * @param peer sender of the request
3877 * @param message message
3878 * @return #GNUNET_OK to keep the connection open,
3879 * #GNUNET_SYSERR to close it (signal serious error)
3882 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3883 const struct GNUNET_MessageHeader *message)
3885 const struct PeerGetResultMessage *get_result;
3886 const struct GNUNET_PeerIdentity *get_path;
3887 const struct GNUNET_PeerIdentity *put_path;
3888 const void *payload;
3889 size_t payload_size;
3891 unsigned int getlen;
3892 unsigned int putlen;
3893 int current_path_index;
3895 msize = ntohs (message->size);
3896 if (msize < sizeof (struct PeerGetResultMessage))
3898 GNUNET_break_op (0);
3902 get_result = (const struct PeerGetResultMessage *)message;
3903 getlen = ntohl (get_result->get_path_length);
3904 putlen = ntohl (get_result->put_path_length);
3907 sizeof (struct PeerGetResultMessage) +
3908 getlen * sizeof (struct GNUNET_PeerIdentity) +
3909 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3911 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3913 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3915 GNUNET_break_op (0);
3918 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3919 GNUNET_STATISTICS_update (GDS_stats,
3921 ("# Bytes received from other peers"), msize,
3924 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3925 get_path = &put_path[putlen];
3926 payload = (const void *) &get_path[getlen];
3927 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3928 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3930 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3932 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
3934 getlen, get_path, putlen,
3935 put_path, get_result->type, payload_size, payload);
3940 current_path_index = search_my_index (get_path, getlen);
3941 if (-1 == current_path_index )
3943 DEBUG ("No entry found in get path.\n");
3945 return GNUNET_SYSERR;
3947 if((getlen + 1) == current_path_index)
3949 DEBUG("Present twice in get path. Not allowed. \n");
3951 return GNUNET_SYSERR;
3953 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3954 &get_path[current_path_index - 1],
3955 &(get_result->querying_peer), putlen, put_path,
3957 GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
3958 payload, payload_size);
3961 return GNUNET_SYSERR;
3966 * Find the next hop to pass trail setup message. First find the local best known
3967 * hop from your own identity, friends and finger. If you were part of trail,
3968 * then get the next hop from routing table. Compare next_hop from routing table
3969 * and local best known hop, and return the closest one to final_dest_finger_val
3970 * @param final_dest_finger_val 64 bit value of finger identity
3971 * @param intermediate_trail_id If you are part of trail to reach to some other
3972 * finger, then it is the trail id to reach to
3973 * that finger, else set to 0.
3974 * @param is_predecessor Are we looking for closest successor or predecessor.
3975 * @param source Source of trail setup message.
3976 * @param current_dest In case you are part of trail, then finger to which
3977 * we should forward the message. Else my own identity
3978 * @return Closest Peer for @a final_dest_finger_val
3980 static struct Closest_Peer
3981 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3982 struct GNUNET_HashCode intermediate_trail_id,
3983 unsigned int is_predecessor,
3984 struct GNUNET_PeerIdentity source,
3985 struct GNUNET_PeerIdentity *current_dest)
3987 struct Closest_Peer peer;
3989 peer = find_local_best_known_next_hop (final_dest_finger_val, is_predecessor);
3991 /* Am I just a part of a trail towards a finger (current_destination)? */
3992 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3993 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3996 struct GNUNET_PeerIdentity closest_peer;
3998 /* Select best successor among one found locally and current_destination
3999 * that we got from network.*/
4000 closest_peer = select_closest_peer (&peer.best_known_destination,
4002 final_dest_finger_val,
4005 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
4006 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
4008 struct GNUNET_PeerIdentity *next_hop;
4010 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4011 GDS_ROUTING_SRC_TO_DEST);
4012 /* next_hop NULL is a valid case. This intermediate trail id is set by
4013 some other finger, and while this trail setup is in progress, that other
4014 peer might have found a better trail ,and send trail teardown message
4015 across the network. In case we got the trail teardown message first,
4016 then next_hop will be NULL. A possible solution could be to keep track
4017 * of all removed trail id, and be sure that there is no other reason . */
4018 if(NULL != next_hop)
4020 peer.next_hop = *next_hop;
4021 peer.best_known_destination = *current_dest;
4022 peer.trail_id = intermediate_trail_id;
4031 * Core handle for PeerTrailSetupMessage.
4032 * @param cls closure
4033 * @param message message
4034 * @param peer peer identity this notification is about
4035 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4038 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
4039 const struct GNUNET_MessageHeader *message)
4041 const struct PeerTrailSetupMessage *trail_setup;
4042 const struct GNUNET_PeerIdentity *trail_peer_list;
4043 struct GNUNET_PeerIdentity current_dest;
4044 struct FriendInfo *target_friend;
4045 struct GNUNET_PeerIdentity source;
4046 struct GNUNET_HashCode intermediate_trail_id;
4047 struct GNUNET_HashCode trail_id;
4048 unsigned int is_predecessor;
4049 uint32_t trail_length;
4050 uint64_t final_dest_finger_val;
4054 msize = ntohs (message->size);
4055 if (msize < sizeof (struct PeerTrailSetupMessage))
4057 GNUNET_break_op (0);
4058 return GNUNET_SYSERR;
4061 trail_setup = (const struct PeerTrailSetupMessage *) message;
4062 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4063 sizeof (struct GNUNET_PeerIdentity) != 0)
4065 GNUNET_break_op (0);
4068 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4069 sizeof (struct GNUNET_PeerIdentity);
4071 GNUNET_STATISTICS_update (GDS_stats,
4073 ("# Bytes received from other peers"), msize,
4076 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4077 current_dest = trail_setup->best_known_destination;
4078 trail_id = trail_setup->trail_id;
4079 final_dest_finger_val =
4080 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4081 source = trail_setup->source_peer;
4082 is_predecessor = ntohl (trail_setup->is_predecessor);
4083 intermediate_trail_id = trail_setup->intermediate_trail_id;
4085 /* Did the friend insert its ID in the trail list? */
4086 if (trail_length > 0 &&
4087 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
4089 GNUNET_break_op (0);
4090 return GNUNET_SYSERR;
4093 /* If I was the source and got the message back, then set trail length to 0.*/
4094 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4099 /* Check if you are present in the trail seen so far? */
4100 for (i = 0; i < trail_length ; i++)
4102 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4104 /* We will add ourself later in code, if NOT destination. */
4110 /* Is my routing table full? */
4111 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4113 if (trail_length > 0)
4115 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4116 &trail_peer_list[trail_length - 1]);
4119 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4121 if(NULL == target_friend)
4123 DEBUG ("\n friend not found");
4127 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4128 my_identity, is_predecessor,
4129 trail_peer_list, trail_length,
4130 trail_id, target_friend,
4131 CONGESTION_TIMEOUT);
4135 /* Get the next hop to forward the trail setup request. */
4136 struct Closest_Peer next_peer =
4137 get_local_best_known_next_hop (final_dest_finger_val,
4138 intermediate_trail_id,
4143 /* Am I the final destination? */
4144 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4147 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4149 finger_table_add (my_identity, NULL, 0, is_predecessor,
4150 final_dest_finger_val, trail_id);
4154 if (trail_length > 0)
4156 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4157 &trail_peer_list[trail_length-1]);
4160 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4161 if (NULL == target_friend)
4163 GNUNET_break_op (0);
4164 return GNUNET_SYSERR;
4166 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4167 GDS_NEIGHBOURS_send_trail_setup_result (source,
4169 target_friend, trail_length,
4172 final_dest_finger_val,trail_id);
4174 else /* I'm not the final destination. */
4176 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4177 &next_peer.next_hop);
4178 if(NULL == target_friend)
4180 DEBUG ("\n target friend not found for peer = %s", GNUNET_i2s(&next_peer.next_hop));
4184 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4186 /* Add yourself to list of peers. */
4187 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4189 memcpy (peer_list, trail_peer_list,
4190 trail_length * sizeof (struct GNUNET_PeerIdentity));
4191 peer_list[trail_length] = my_identity;
4192 GDS_NEIGHBOURS_send_trail_setup (source,
4193 final_dest_finger_val,
4194 next_peer.best_known_destination,
4195 target_friend, trail_length + 1, peer_list,
4196 is_predecessor, trail_id,
4197 next_peer.trail_id);
4200 GDS_NEIGHBOURS_send_trail_setup (source,
4201 final_dest_finger_val,
4202 next_peer.best_known_destination,
4203 target_friend, 0, NULL,
4204 is_predecessor, trail_id,
4205 next_peer.trail_id);
4212 * Core handle for p2p trail setup result messages.
4214 * @param message message
4215 * @param peer sender of this message.
4216 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4219 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4220 const struct GNUNET_MessageHeader *message)
4222 const struct PeerTrailSetupResultMessage *trail_result;
4223 const struct GNUNET_PeerIdentity *trail_peer_list;
4224 struct GNUNET_PeerIdentity next_hop;
4225 struct FriendInfo *target_friend;
4226 struct GNUNET_PeerIdentity querying_peer;
4227 struct GNUNET_PeerIdentity finger_identity;
4228 uint32_t trail_length;
4229 uint64_t ulitmate_destination_finger_value;
4230 uint32_t is_predecessor;
4231 struct GNUNET_HashCode trail_id;
4235 msize = ntohs (message->size);
4236 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4238 GNUNET_break_op (0);
4242 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4243 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4244 sizeof (struct GNUNET_PeerIdentity) != 0)
4246 GNUNET_break_op (0);
4249 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4250 sizeof (struct GNUNET_PeerIdentity);
4252 GNUNET_STATISTICS_update (GDS_stats,
4254 ("# Bytes received from other peers"), msize,
4257 is_predecessor = ntohl (trail_result->is_predecessor);
4258 querying_peer = trail_result->querying_peer;
4259 finger_identity = trail_result->finger_identity;
4260 trail_id = trail_result->trail_id;
4261 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4262 ulitmate_destination_finger_value =
4263 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4265 /* Am I the one who initiated the query? */
4266 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4268 /* Check that you got the message from the correct peer. */
4269 if (trail_length > 0)
4271 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4276 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4279 GDS_ROUTING_add (trail_id, my_identity, *peer);
4280 finger_table_add (finger_identity, trail_peer_list, trail_length,
4281 is_predecessor, ulitmate_destination_finger_value, trail_id);
4285 /* Get my location in the trail. */
4286 my_index = search_my_index (trail_peer_list, trail_length);
4289 DEBUG ("Not found in trail\n");
4291 return GNUNET_SYSERR;
4294 if ((trail_length + 1) == my_index)
4296 DEBUG ("Found twice in trail.\n");
4298 return GNUNET_SYSERR;
4301 //TODO; Refactor code here and above to check if sender peer is correct
4304 if(trail_length > 1)
4305 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4308 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4310 next_hop = trail_result->querying_peer;
4314 if(my_index == trail_length - 1)
4317 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4322 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4324 next_hop = trail_peer_list[my_index - 1];
4327 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4328 if (NULL == target_friend)
4330 GNUNET_break_op (0);
4331 return GNUNET_SYSERR;
4333 GDS_ROUTING_add (trail_id, next_hop, *peer);
4334 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4335 target_friend, trail_length, trail_peer_list,
4337 ulitmate_destination_finger_value,
4345 * @param trail Trail to be inverted
4346 * @param trail_length Total number of peers in the trail.
4347 * @return Updated trail
4349 static struct GNUNET_PeerIdentity *
4350 invert_trail (const struct GNUNET_PeerIdentity *trail,
4351 unsigned int trail_length)
4355 struct GNUNET_PeerIdentity *inverted_trail;
4357 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4360 j = trail_length - 1;
4361 while (i < trail_length)
4363 inverted_trail[i] = trail[j];
4368 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4369 &inverted_trail[0]));
4370 return inverted_trail;
4375 * Return the shortest trail among all the trails to reach to finger from me.
4376 * @param finger Finger
4377 * @param shortest_trail_length[out] Trail length of shortest trail from me
4379 * @return Shortest trail.
4381 static struct GNUNET_PeerIdentity *
4382 get_shortest_trail (struct FingerInfo *finger,
4383 unsigned int *trail_length)
4385 struct Trail *trail;
4386 unsigned int flag = 0;
4387 unsigned int shortest_trail_index = 0;
4388 int shortest_trail_length = -1;
4389 struct Trail_Element *trail_element;
4390 struct GNUNET_PeerIdentity *trail_list;
4393 /* Get the shortest trail to reach to current successor. */
4394 for (i = 0; i < finger->trails_count; i++)
4396 trail = &finger->trail_list[i];
4400 shortest_trail_index = i;
4401 shortest_trail_length = trail->trail_length;
4406 if (shortest_trail_length > trail->trail_length)
4408 shortest_trail_index = i;
4409 shortest_trail_length = trail->trail_length;
4414 /* Copy the shortest trail and return. */
4415 trail = &finger->trail_list[shortest_trail_index];
4416 trail_element = trail->trail_head;
4418 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4419 shortest_trail_length);
4421 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4423 trail_list[i] = trail_element->peer;
4426 GNUNET_assert(shortest_trail_length != -1);
4428 *trail_length = shortest_trail_length;
4434 * Check if trail_1 and trail_2 have any common element. If yes then join
4435 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4436 * @param trail_1 Trail from source to me, NOT including endpoints.
4437 * @param trail_1_len Total number of peers @a trail_1
4438 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4439 * @param trail_2_len Total number of peers @a trail_2
4440 * @param joined_trail_len Total number of peers in combined trail of trail_1
4442 * @return Joined trail.
4444 static struct GNUNET_PeerIdentity *
4445 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4446 unsigned int trail_1_len,
4447 struct GNUNET_PeerIdentity *trail_2,
4448 unsigned int trail_2_len,
4449 unsigned int *joined_trail_len)
4451 struct GNUNET_PeerIdentity *joined_trail;
4456 for (i = 0; i < trail_1_len; i++)
4458 for (j = 0; j < trail_2_len; j++)
4460 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4463 *joined_trail_len = i + (trail_2_len - j);
4464 joined_trail = GNUNET_malloc (*joined_trail_len *
4465 sizeof(struct GNUNET_PeerIdentity));
4468 /* Copy all the elements from 0 to i into joined_trail. */
4469 for(k = 0; k < ( i+1); k++)
4471 joined_trail[k] = trail_1[k];
4474 /* Increment j as entry stored is same as entry stored at i*/
4477 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4478 while(k <= (*joined_trail_len - 1))
4480 joined_trail[k] = trail_2[j];
4485 return joined_trail;
4489 /* Here you should join the trails. */
4490 *joined_trail_len = trail_1_len + trail_2_len + 1;
4491 joined_trail = GNUNET_malloc (*joined_trail_len *
4492 sizeof(struct GNUNET_PeerIdentity));
4495 for(i = 0; i < trail_1_len;i++)
4497 joined_trail[i] = trail_1[i];
4500 joined_trail[i] = my_identity;
4503 for (j = 0; i < *joined_trail_len; i++,j++)
4505 joined_trail[i] = trail_2[j];
4508 return joined_trail;
4513 * Return the trail from source to my current predecessor. Check if source
4514 * is already part of the this trail, if yes then return the shorten trail.
4515 * @param current_trail Trail from source to me, NOT including the endpoints.
4516 * @param current_trail_length Number of peers in @a current_trail.
4517 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4518 * source to my predecessor, NOT including
4520 * @return Trail from source to my predecessor.
4522 static struct GNUNET_PeerIdentity *
4523 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4524 const struct GNUNET_PeerIdentity *trail_src_to_me,
4525 unsigned int trail_src_to_me_len,
4526 unsigned int *trail_src_to_curr_pred_length)
4528 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4529 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4530 unsigned int trail_me_to_curr_pred_length;
4531 struct FingerInfo *current_predecessor;
4536 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4538 /* Check if trail_src_to_me contains current_predecessor. */
4539 for (i = 0; i < trail_src_to_me_len; i++)
4541 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4542 ¤t_predecessor->finger_identity))
4546 *trail_src_to_curr_pred_length = i;
4551 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4552 sizeof(struct GNUNET_PeerIdentity));
4553 for (j = 0; j < i; j++)
4554 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4555 return trail_src_to_curr_pred;
4559 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4560 &trail_me_to_curr_pred_length);
4562 /* Check if trail contains the source_peer. */
4563 for (i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4565 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4566 &trail_me_to_curr_pred[i]))
4569 /* Source is NOT part of trail. */
4572 /* Source is the last element in the trail to reach to my pred.
4573 Source is direct friend of the pred. */
4574 if (trail_me_to_curr_pred_length == i)
4576 *trail_src_to_curr_pred_length = 0;
4577 GNUNET_free_non_null (trail_me_to_curr_pred);
4581 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4582 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4583 *trail_src_to_curr_pred_length);
4585 for (j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4586 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4587 GNUNET_free_non_null (trail_me_to_curr_pred);
4588 return trail_src_to_curr_pred;
4591 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4592 trail_src_to_me_len,
4593 trail_me_to_curr_pred,
4594 trail_me_to_curr_pred_length,
4596 *trail_src_to_curr_pred_length = len;
4597 GNUNET_free_non_null(trail_me_to_curr_pred);
4598 return trail_src_to_curr_pred;
4603 * Add finger as your predecessor. To add, first generate a new trail id, invert
4604 * the trail to get the trail from me to finger, add an entry in your routing
4605 * table, send add trail message to peers which are part of trail from me to
4606 * finger and add finger in finger table.
4609 * @param trail_length
4612 update_predecessor (struct GNUNET_PeerIdentity finger,
4613 struct GNUNET_PeerIdentity *trail,
4614 unsigned int trail_length)
4616 struct GNUNET_HashCode trail_to_new_predecessor_id;
4617 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4618 struct FriendInfo *target_friend;
4620 /* Generate trail id for trail from me to new predecessor = finger. */
4621 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4622 &trail_to_new_predecessor_id,
4623 sizeof (trail_to_new_predecessor_id));
4625 if (0 == trail_length)
4627 trail_to_new_predecessor = NULL;
4628 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4629 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger);
4630 if (NULL == target_friend)
4638 /* Invert the trail to get the trail from me to finger, NOT including the
4640 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4641 &trail[trail_length-1]));
4642 trail_to_new_predecessor = invert_trail (trail, trail_length);
4644 /* Add an entry in your routing table. */
4645 GDS_ROUTING_add (trail_to_new_predecessor_id,
4647 trail_to_new_predecessor[0]);
4649 GNUNET_assert (NULL != (target_friend =
4650 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4651 &trail_to_new_predecessor[0])));
4654 /* Add entry in routing table of all peers that are part of trail from me
4655 to finger, including finger. */
4656 GDS_NEIGHBOURS_send_add_trail (my_identity,
4658 trail_to_new_predecessor_id,
4659 trail_to_new_predecessor,
4663 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4664 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4665 GNUNET_free_non_null(trail_to_new_predecessor);
4670 * Check if you already have a predecessor. If not then add finger as your
4671 * predecessor. If you have predecessor, then compare two peer identites.
4672 * If finger is correct predecessor, then remove the old entry, add finger in
4673 * finger table and send add_trail message to add the trail in the routing
4674 * table of all peers which are part of trail to reach from me to finger.
4675 * @param finger New peer which may be our predecessor.
4676 * @param trail List of peers to reach from @finger to me.
4677 * @param trail_length Total number of peer in @a trail.
4680 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4681 struct GNUNET_PeerIdentity *trail,
4682 unsigned int trail_length)
4684 struct FingerInfo *current_predecessor;
4685 struct GNUNET_PeerIdentity closest_peer;
4686 uint64_t predecessor_value;
4687 unsigned int is_predecessor = 1;
4689 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4690 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4692 /* No predecessor. Add finger as your predecessor. */
4693 if (GNUNET_NO == current_predecessor->is_present)
4695 update_predecessor (finger, trail, trail_length);
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,
4708 predecessor_value, is_predecessor);
4710 /* Finger is the closest predecessor. Remove the existing one and add the new
4712 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4714 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4715 update_predecessor (finger, trail, trail_length);
4723 * Core handle for p2p verify successor messages.
4724 * @param cls closure
4725 * @param message message
4726 * @param peer peer identity this notification is about
4727 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4730 handle_dht_p2p_verify_successor(void *cls,
4731 const struct GNUNET_PeerIdentity *peer,
4732 const struct GNUNET_MessageHeader *message)
4734 const struct PeerVerifySuccessorMessage *vsm;
4735 struct GNUNET_HashCode trail_id;
4736 struct GNUNET_PeerIdentity successor;
4737 struct GNUNET_PeerIdentity source_peer;
4738 struct GNUNET_PeerIdentity *trail;
4739 struct GNUNET_PeerIdentity *next_hop;
4740 struct FingerInfo current_predecessor;
4741 struct FriendInfo *target_friend;
4742 unsigned int trail_src_to_curr_pred_len = 0;
4743 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4744 unsigned int trail_length;
4747 msize = ntohs (message->size);
4749 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4751 GNUNET_break_op (0);
4755 vsm = (const struct PeerVerifySuccessorMessage *) message;
4756 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4757 sizeof (struct GNUNET_PeerIdentity);
4758 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4759 sizeof (struct GNUNET_PeerIdentity) != 0)
4761 GNUNET_break_op (0);
4765 GNUNET_STATISTICS_update (GDS_stats,
4767 ("# Bytes received from other peers"), msize,
4770 trail_id = vsm->trail_id;
4771 source_peer = vsm->source_peer;
4772 successor = vsm->successor;
4773 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4775 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4777 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4779 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4780 if (NULL == next_hop)
4785 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4787 if(NULL == target_friend)
4792 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4793 trail_id, trail, trail_length,
4798 /* I am the destination of this message. */
4800 /* Check if the source_peer could be our predecessor and if yes then update
4802 compare_and_update_predecessor (source_peer, trail, trail_length);
4803 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4805 /* Is source of this message NOT my predecessor. */
4806 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4809 trail_src_to_curr_pred =
4810 get_trail_src_to_curr_pred (source_peer,
4813 &trail_src_to_curr_pred_len);
4817 trail_src_to_curr_pred_len = trail_length;
4820 trail_src_to_curr_pred =
4821 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4822 *trail_src_to_curr_pred_len);
4823 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4825 trail_src_to_curr_pred[i] = trail[i];
4829 GNUNET_assert (NULL !=
4831 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4832 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4833 current_predecessor.finger_identity,
4834 trail_id, trail_src_to_curr_pred,
4835 trail_src_to_curr_pred_len,
4836 GDS_ROUTING_DEST_TO_SRC,
4838 GNUNET_free_non_null(trail_src_to_curr_pred);
4844 * If the trail from me to my probable successor contains a friend not
4845 * at index 0, then we can shorten the trail.
4846 * @param probable_successor Peer which is our probable successor
4847 * @param trail_me_to_probable_successor Peers in path from me to my probable
4848 * successor, NOT including the endpoints.
4849 * @param trail_me_to_probable_successor_len Total number of peers in
4850 * @a trail_me_to_probable_succesor.
4851 * @return Updated trail, if any friend found.
4852 * Else the trail_me_to_probable_successor.
4854 struct GNUNET_PeerIdentity *
4855 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4856 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4857 unsigned int trail_me_to_probable_successor_len,
4858 unsigned int *trail_to_new_successor_length)
4862 struct GNUNET_PeerIdentity *trail_to_new_successor;
4864 /* Probable successor is a friend */
4865 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4866 &probable_successor))
4868 trail_to_new_successor = NULL;
4869 *trail_to_new_successor_length = 0;
4870 return trail_to_new_successor;
4873 /* Is there any friend of yours in this trail. */
4874 if(trail_me_to_probable_successor_len > 1)
4876 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4878 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4879 &trail_me_to_probable_successor[i]))
4882 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4883 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4884 *trail_to_new_successor_length);
4887 for(j = 0; j < *trail_to_new_successor_length; i++,j++)
4889 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4892 return trail_to_new_successor;
4896 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4897 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4901 struct SendNotifyContext
4903 struct GNUNET_PeerIdentity source_peer;
4904 struct GNUNET_PeerIdentity successor;
4905 struct GNUNET_PeerIdentity *successor_trail;
4906 unsigned int successor_trail_length;
4907 struct GNUNET_HashCode succesor_trail_id;
4908 struct FriendInfo *target_friend;
4909 unsigned int num_retries_scheduled;
4914 send_notify_new_successor (void *cls);
4918 * Check if the peer which sent us verify successor result message is still ours
4919 * successor or not. If not, then compare existing successor and probable successor.
4920 * In case probable successor is the correct successor, remove the existing
4921 * successor. Add probable successor as new successor. Send notify new successor
4922 * message to new successor.
4923 * @param curr_succ Peer to which we sent the verify successor message. It may
4924 * or may not be our real current successor, as we may have few iterations of
4925 * find finger trail task.
4926 * @param probable_successor Peer which should be our successor accroding to @a
4928 * @param trail List of peers to reach from me to @a probable successor, NOT including
4930 * @param trail_length Total number of peers in @a trail.
4933 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4934 struct GNUNET_PeerIdentity probable_successor,
4935 const struct GNUNET_PeerIdentity *trail,
4936 unsigned int trail_length)
4938 struct FingerInfo *current_successor;
4939 struct GNUNET_PeerIdentity closest_peer;
4940 struct GNUNET_HashCode trail_id;
4941 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4942 struct FriendInfo *target_friend;
4943 unsigned int trail_me_to_probable_succ_len;
4944 unsigned int is_predecessor = 0;
4945 uint64_t successor_value;
4947 current_successor = &finger_table[0];
4948 successor_value = compute_finger_identity_value(0);
4950 /* If probable successor is same as current_successor, do nothing. */
4951 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
4952 ¤t_successor->finger_identity))
4954 if ((NULL != GDS_stats))
4960 memcpy (&my_id, &my_identity, sizeof(uint64_t));
4961 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4962 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4963 succ = GNUNET_ntohll(succ);
4964 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4965 GNUNET_free (my_id_str);
4967 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4970 if (send_verify_successor_task == NULL)
4971 send_verify_successor_task =
4972 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
4973 &send_verify_successor_message,
4977 closest_peer = select_closest_peer (&probable_successor,
4978 ¤t_successor->finger_identity,
4979 successor_value, is_predecessor);
4981 /* If the current_successor in the finger table is closest, then do nothing. */
4982 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
4983 ¤t_successor->finger_identity))
4985 //FIXME: Is this a good place to return the stats.
4986 if ((NULL != GDS_stats))
4992 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4993 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4994 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4995 GNUNET_free (my_id_str);
4996 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5000 if(0 == successor_times)
5002 // successor_times = 3;
5003 verify_successor_next_send_time =
5004 GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time);
5010 if (send_verify_successor_task == NULL)
5011 send_verify_successor_task =
5012 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5013 &send_verify_successor_message,
5018 /* Probable successor is the closest peer.*/
5019 if(trail_length > 0)
5021 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5026 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5027 &probable_successor));
5030 trail_me_to_probable_succ_len = 0;
5031 trail_me_to_probable_succ =
5032 check_trail_me_to_probable_succ (probable_successor,
5033 trail, trail_length,
5034 &trail_me_to_probable_succ_len);
5036 /* Remove the existing successor. */
5037 remove_existing_finger (current_successor, 0);
5038 /* Generate a new trail id to reach to your new successor. */
5039 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5040 &trail_id, sizeof (trail_id));
5042 if (trail_me_to_probable_succ_len > 0)
5044 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
5045 GNUNET_assert (NULL !=
5047 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5048 &trail_me_to_probable_succ[0])));
5052 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5053 GNUNET_assert (NULL !=
5055 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5056 &probable_successor)));
5059 add_new_finger (probable_successor, trail_me_to_probable_succ,
5060 trail_me_to_probable_succ_len, trail_id, 0);
5062 struct SendNotifyContext *notify_ctx;
5064 notify_ctx = GNUNET_new(struct SendNotifyContext);
5066 notify_ctx->source_peer = my_identity;
5067 notify_ctx->successor = probable_successor;
5068 notify_ctx->successor_trail =
5069 GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5070 memcpy(notify_ctx->successor_trail, trail_me_to_probable_succ,
5071 sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5072 notify_ctx->successor_trail_length = trail_me_to_probable_succ_len;
5073 notify_ctx->succesor_trail_id = trail_id;
5074 notify_ctx->target_friend = target_friend;
5075 notify_ctx->num_retries_scheduled = 0;
5076 GNUNET_free_non_null (trail_me_to_probable_succ);
5078 // TODO: Check if we should verify before schedule if already scheduled.
5079 GNUNET_SCHEDULER_add_now(&send_notify_new_successor, (void*)notify_ctx);
5085 send_notify_new_successor (void *cls)
5087 struct SendNotifyContext *ctx = cls;
5089 GDS_NEIGHBOURS_send_notify_new_successor (ctx->source_peer,
5091 ctx->successor_trail,
5092 ctx->successor_trail_length,
5093 ctx->succesor_trail_id,
5094 ctx->target_friend);
5096 if (0 == ctx->num_retries_scheduled &&
5097 send_notify_new_successor_retry_task != NULL)
5099 // Result from previous notify successos hasn't arrived, so the retry task
5100 // hasn't been cancelled! Already a new notify successor must be called.
5101 // We will cancel the retry request.
5102 struct SendNotifyContext *old_notify_ctx;
5103 old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5104 GNUNET_free (old_notify_ctx->successor_trail);
5105 GNUNET_free (old_notify_ctx);
5106 send_notify_new_successor_retry_task = NULL;
5109 ctx->num_retries_scheduled++;
5110 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_add_delayed(notify_successor_retry_time,
5111 &send_notify_new_successor,
5116 * Core handle for p2p verify successor result messages.
5117 * @param cls closure
5118 * @param message message
5119 * @param peer peer identity this notification is about
5120 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5123 handle_dht_p2p_verify_successor_result(void *cls,
5124 const struct GNUNET_PeerIdentity *peer,
5125 const struct GNUNET_MessageHeader *message)
5127 const struct PeerVerifySuccessorResultMessage *vsrm;
5128 enum GDS_ROUTING_trail_direction trail_direction;
5129 struct GNUNET_PeerIdentity querying_peer;
5130 struct GNUNET_HashCode trail_id;
5131 struct GNUNET_PeerIdentity *next_hop;
5132 struct FriendInfo *target_friend;
5133 struct GNUNET_PeerIdentity probable_successor;
5134 struct GNUNET_PeerIdentity current_successor;
5135 const struct GNUNET_PeerIdentity *trail;
5136 unsigned int trail_length;
5139 msize = ntohs (message->size);
5140 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5142 GNUNET_break_op (0);
5146 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5147 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5148 sizeof (struct GNUNET_PeerIdentity) != 0)
5150 GNUNET_break_op (0);
5153 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5154 sizeof (struct GNUNET_PeerIdentity);
5156 GNUNET_STATISTICS_update (GDS_stats,
5158 ("# Bytes received from other peers"), msize,
5161 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5162 querying_peer = vsrm->querying_peer;
5163 trail_direction = ntohl (vsrm->trail_direction);
5164 trail_id = vsrm->trail_id;
5165 probable_successor = vsrm->probable_successor;
5166 current_successor = vsrm->current_successor;
5168 /* I am the querying_peer. */
5169 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5171 /* Cancel Retry Task */
5172 if (NULL != send_verify_successor_retry_task)
5174 struct VerifySuccessorContext *ctx;
5175 ctx = GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
5177 send_verify_successor_retry_task = NULL;
5179 compare_and_update_successor (current_successor,
5180 probable_successor, trail, trail_length);
5184 /*If you are not the querying peer then pass on the message */
5185 if(NULL == (next_hop =
5186 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
5188 /* Here it may happen that source peer has found a new successor, and removed
5189 the trail, Hence no entry found in the routing table. Fail silently.*/
5190 DEBUG (" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
5191 GNUNET_i2s (&my_identity),
5192 GNUNET_h2s (&trail_id),
5197 if (NULL == (target_friend =
5198 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5203 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5204 vsrm->current_successor,
5205 probable_successor, trail_id,
5208 trail_direction, target_friend);
5214 * Core handle for p2p notify new successor messages.
5215 * @param cls closure
5216 * @param message message
5217 * @param peer peer identity this notification is about
5218 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5221 handle_dht_p2p_notify_new_successor(void *cls,
5222 const struct GNUNET_PeerIdentity *peer,
5223 const struct GNUNET_MessageHeader *message)
5225 const struct PeerNotifyNewSuccessorMessage *nsm;
5226 struct GNUNET_PeerIdentity *trail;
5227 struct GNUNET_PeerIdentity source;
5228 struct GNUNET_PeerIdentity new_successor;
5229 struct GNUNET_HashCode trail_id;
5230 struct GNUNET_PeerIdentity next_hop;
5231 struct FriendInfo *target_friend;
5234 uint32_t trail_length;
5236 msize = ntohs (message->size);
5237 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5239 GNUNET_break_op (0);
5242 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5243 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5244 sizeof (struct GNUNET_PeerIdentity) != 0)
5246 GNUNET_break_op (0);
5249 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5250 sizeof (struct GNUNET_PeerIdentity);
5251 GNUNET_STATISTICS_update (GDS_stats,
5253 ("# Bytes received from other peers"), msize,
5256 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5257 source = nsm->source_peer;
5258 new_successor = nsm->new_successor;
5259 trail_id = nsm->trail_id;
5261 /* I am the new_successor to source_peer. */
5262 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5264 if(trail_length > 0)
5265 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5268 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5270 compare_and_update_predecessor (source, trail, trail_length);
5271 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5272 GNUNET_assert (NULL != target_friend);
5273 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5274 GDS_ROUTING_DEST_TO_SRC,
5279 GNUNET_assert(trail_length > 0);
5280 /* I am part of trail to reach to successor. */
5281 my_index = search_my_index (trail, trail_length);
5284 DEBUG ("No entry found in trail\n");
5285 GNUNET_break_op (0);
5286 return GNUNET_SYSERR;
5288 if((trail_length + 1) == my_index)
5290 DEBUG ("Found twice in trail.\n");
5291 GNUNET_break_op (0);
5292 return GNUNET_SYSERR;
5294 if ((trail_length-1) == my_index)
5295 next_hop = new_successor;
5297 next_hop = trail[my_index + 1];
5299 GDS_ROUTING_add(trail_id, *peer, next_hop);
5301 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
5302 if (NULL == target_friend)
5307 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5309 trail_id, target_friend);
5316 * Core handler for P2P notify successor message
5317 * @param cls closure
5318 * @param message message
5319 * @param peer peer identity this notification is about
5320 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5323 handle_dht_p2p_notify_succ_confirmation (void *cls,
5324 const struct GNUNET_PeerIdentity *peer,
5325 const struct GNUNET_MessageHeader *message)
5327 const struct PeerNotifyConfirmationMessage *notify_confirmation;
5328 enum GDS_ROUTING_trail_direction trail_direction;
5329 struct GNUNET_HashCode trail_id;
5330 struct FriendInfo *target_friend;
5331 struct GNUNET_PeerIdentity *next_hop;
5334 msize = ntohs (message->size);
5336 if (msize != sizeof (struct PeerNotifyConfirmationMessage))
5338 GNUNET_break_op (0);
5341 GNUNET_STATISTICS_update (GDS_stats,
5343 ("# Bytes received from other peers"), msize,
5346 notify_confirmation = (const struct PeerNotifyConfirmationMessage *) message;
5347 trail_direction = ntohl (notify_confirmation->trail_direction);
5348 trail_id = notify_confirmation->trail_id;
5350 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5351 if (NULL == next_hop)
5353 /* The source of notify new successor, might have found even a better
5354 successor. In that case it send a trail teardown message, and hence,
5355 the next hop is NULL. */
5356 //Fixme: Add some print to confirm the above theory.
5360 /* I peer which sent the notify successor message to the successor. */
5361 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5364 * Schedule another round of verify sucessor with your current successor
5365 * which may or may not be source of this message. This message is used
5366 * only to ensure that we have a path setup to reach to our successor.
5369 // TODO: cancel schedule of notify_successor_retry_task
5370 if (send_notify_new_successor_retry_task != NULL)
5372 struct SendNotifyContext *notify_ctx;
5373 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5374 GNUNET_free (notify_ctx->successor_trail);
5375 GNUNET_free (notify_ctx);
5376 send_notify_new_successor_retry_task = NULL;
5378 if (send_verify_successor_task == NULL)
5380 verify_successor_next_send_time.rel_value_us =
5381 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5382 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5383 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5384 send_verify_successor_task =
5385 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5386 &send_verify_successor_message,
5392 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
5393 if (NULL == target_friend)
5395 DEBUG ("\n friend not found, line number = %d",__LINE__);
5396 return GNUNET_SYSERR;
5398 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5399 GDS_ROUTING_DEST_TO_SRC,
5407 * Core handler for P2P trail rejection message
5408 * @param cls closure
5409 * @param message message
5410 * @param peer peer identity this notification is about
5411 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5414 handle_dht_p2p_trail_setup_rejection (void *cls,
5415 const struct GNUNET_PeerIdentity *peer,
5416 const struct GNUNET_MessageHeader *message)
5418 const struct PeerTrailRejectionMessage *trail_rejection;
5419 unsigned int trail_length;
5420 const struct GNUNET_PeerIdentity *trail_peer_list;
5421 struct FriendInfo *target_friend;
5422 struct GNUNET_TIME_Relative congestion_timeout;
5423 struct GNUNET_HashCode trail_id;
5424 struct GNUNET_PeerIdentity next_peer;
5425 struct GNUNET_PeerIdentity source;
5426 uint64_t ultimate_destination_finger_value;
5427 unsigned int is_predecessor;
5430 msize = ntohs (message->size);
5431 if (msize < sizeof (struct PeerTrailRejectionMessage))
5433 GNUNET_break_op (0);
5436 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5437 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5438 sizeof (struct GNUNET_PeerIdentity) != 0)
5440 GNUNET_break_op (0);
5443 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5444 sizeof (struct GNUNET_PeerIdentity);
5445 GNUNET_STATISTICS_update (GDS_stats,
5447 ("# Bytes received from other peers"), msize,
5450 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5451 is_predecessor = ntohl (trail_rejection->is_predecessor);
5452 congestion_timeout = trail_rejection->congestion_time;
5453 source = trail_rejection->source_peer;
5454 trail_id = trail_rejection->trail_id;
5455 ultimate_destination_finger_value =
5456 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5457 /* First set the congestion time of the friend that sent you this message. */
5458 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5459 if (NULL == target_friend)
5461 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5465 target_friend->congestion_timestamp =
5466 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5467 congestion_timeout);
5469 /* I am the source peer which wants to setup the trail. Do nothing.
5470 * send_find_finger_trail_task is scheduled periodically.*/
5471 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5474 /* If I am congested then pass this message to peer before me in trail. */
5475 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5477 /* First remove yourself from the trail. */
5478 unsigned int new_trail_length = trail_length - 1;
5479 struct GNUNET_PeerIdentity trail[new_trail_length];
5481 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5482 if (0 == trail_length)
5485 next_peer = trail[new_trail_length-1];
5488 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5489 if (NULL == target_friend)
5491 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5495 GDS_NEIGHBOURS_send_trail_rejection (source,
5496 ultimate_destination_finger_value,
5497 my_identity, is_predecessor,
5498 trail, new_trail_length, trail_id,
5499 target_friend, CONGESTION_TIMEOUT);
5503 struct Closest_Peer successor;
5504 successor = find_local_best_known_next_hop (ultimate_destination_finger_value, is_predecessor);
5506 /* Am I the final destination? */
5507 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5510 /*Here you are already part of trail. Copy the trail removing yourself. */
5511 unsigned int new_trail_length = trail_length - 1;
5512 struct GNUNET_PeerIdentity trail[new_trail_length];
5514 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5516 if (0 == new_trail_length)
5520 next_peer = trail[new_trail_length-1];
5523 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5525 if (NULL == target_friend)
5527 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5531 GDS_NEIGHBOURS_send_trail_setup_result (source,
5533 target_friend, new_trail_length,
5536 ultimate_destination_finger_value,
5541 /* Here I was already part of trail. So no need to add. */
5543 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5544 &successor.next_hop);
5545 if (NULL == target_friend)
5547 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5552 GDS_NEIGHBOURS_send_trail_setup (source,
5553 ultimate_destination_finger_value,
5554 successor.best_known_destination,
5555 target_friend, trail_length, trail_peer_list,
5556 is_predecessor, trail_id,
5557 successor.trail_id);
5564 * Core handler for trail teardown message.
5565 * @param cls closure
5566 * @param message message
5567 * @param peer sender of this messsage.
5568 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5571 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5572 const struct GNUNET_MessageHeader *message)
5574 const struct PeerTrailTearDownMessage *trail_teardown;
5575 enum GDS_ROUTING_trail_direction trail_direction;
5576 struct GNUNET_HashCode trail_id;
5577 struct GNUNET_PeerIdentity *next_hop;
5580 msize = ntohs (message->size);
5582 /* Here we pass only the trail id. */
5583 if (msize != sizeof (struct PeerTrailTearDownMessage))
5585 GNUNET_break_op (0);
5589 GNUNET_STATISTICS_update (GDS_stats,
5591 ("# Bytes received from other peers"), msize,
5594 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5595 trail_direction = ntohl (trail_teardown->trail_direction);
5596 trail_id = trail_teardown->trail_id;
5598 /* Check if peer is the real peer from which we should get this message.*/
5599 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5601 GNUNET_assert (NULL != (prev_hop =
5602 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5603 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5606 return GNUNET_SYSERR;
5610 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5611 if (NULL == next_hop)
5613 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
5614 GNUNET_i2s (&my_identity),
5615 GNUNET_h2s(&trail_id),
5618 return GNUNET_SYSERR;
5621 /* I am the next hop, which means I am the final destination. */
5622 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5624 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5629 /* If not final destination, then send a trail teardown message to next hop.*/
5630 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5631 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5632 GDS_NEIGHBOURS_send_trail_teardown (&trail_id, trail_direction, next_hop);
5640 * Core handle for p2p add trail message.
5641 * @param cls closure
5642 * @param message message
5643 * @param peer peer identity this notification is about
5644 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5647 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5648 const struct GNUNET_MessageHeader *message)
5650 const struct PeerAddTrailMessage *add_trail;
5651 const struct GNUNET_PeerIdentity *trail;
5652 struct GNUNET_HashCode trail_id;
5653 struct GNUNET_PeerIdentity destination_peer;
5654 struct GNUNET_PeerIdentity source_peer;
5655 struct GNUNET_PeerIdentity next_hop;
5656 unsigned int trail_length;
5657 unsigned int my_index;
5660 msize = ntohs (message->size);
5661 /* In this message we pass the whole trail from source to destination as we
5662 * are adding that trail.*/
5663 //FIXME: failed when run with 1000 pears. check why.
5664 if (msize < sizeof (struct PeerAddTrailMessage))
5666 GNUNET_break_op (0);
5670 add_trail = (const struct PeerAddTrailMessage *) message;
5671 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5672 sizeof (struct GNUNET_PeerIdentity);
5673 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5674 sizeof (struct GNUNET_PeerIdentity) != 0)
5676 GNUNET_break_op (0);
5680 GNUNET_STATISTICS_update (GDS_stats,
5682 ("# Bytes received from other peers"), msize,
5685 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5686 destination_peer = add_trail->destination_peer;
5687 source_peer = add_trail->source_peer;
5688 trail_id = add_trail->trail_id;
5690 /* I am not the destination of the trail. */
5691 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5693 struct FriendInfo *target_friend;
5695 /* Get my location in the trail. */
5696 my_index = search_my_index (trail, trail_length);
5699 GNUNET_break_op (0);
5700 return GNUNET_SYSERR;
5702 if((trail_length + 1) == my_index)
5704 DEBUG ("Found twice in trail.\n");
5705 GNUNET_break_op (0);
5706 return GNUNET_SYSERR;
5708 if ((trail_length - 1) == my_index)
5710 next_hop = destination_peer;
5714 next_hop = trail[my_index + 1];
5716 /* Add in your routing table. */
5717 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5718 //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5719 GNUNET_assert (NULL !=
5721 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5722 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5723 trail, trail_length, target_friend);
5726 /* I am the destination. Add an entry in routing table. */
5727 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5733 * Free the finger trail in which the first friend to reach to a finger is
5734 * disconnected_friend. Also remove entry from routing table for that particular
5736 * @param disconnected_friend PeerIdentity of friend which got disconnected
5737 * @param remove_finger Finger whose trail we need to check if it has
5738 * disconnected_friend as the first hop.
5739 * @return Total number of trails in which disconnected_friend was the first
5743 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5744 struct FingerInfo *finger)
5746 struct GNUNET_PeerIdentity *next_hop;
5747 struct FriendInfo *remove_friend;
5748 struct Trail *current_trail;
5749 unsigned int matching_trails_count = 0;
5752 /* Iterate over all the trails of finger. */
5753 for (i = 0; i < finger->trails_count; i++)
5755 current_trail = &finger->trail_list[i];
5756 if (GNUNET_NO == current_trail->is_present)
5759 /* First friend to reach to finger is disconnected_peer. */
5760 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5761 disconnected_friend))
5764 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5765 disconnected_friend);
5766 GNUNET_assert (NULL != remove_friend);
5767 next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id,
5768 GDS_ROUTING_SRC_TO_DEST);
5770 /* Here it may happen that as all the peers got disconnected, the entry in
5771 routing table for that particular trail has been removed, because the
5772 previously disconnected peer was either a next hop or prev hop of that
5774 if (NULL != next_hop)
5776 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5778 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id));
5780 matching_trails_count++;
5781 free_trail (current_trail);
5782 current_trail->is_present = GNUNET_NO;
5785 return matching_trails_count;
5790 * Iterate over finger_table entries.
5791 * 0. Ignore finger which is my_identity or if no valid entry present at
5792 * that finger index.
5793 * 1. If disconnected_friend is a finger, then remove the routing entry from
5794 your own table. Free the trail.
5795 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5796 * 2.1 Remove all the trails and entry from routing table in which disconnected
5797 * friend is the first friend in the trail. If disconnected_friend is the
5798 * first friend in all the trails to reach finger, then remove the finger.
5799 * @param disconnected_friend Peer identity of friend which got disconnected.
5802 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5804 struct FingerInfo *current_finger;
5805 int removed_trails_count;
5808 /* Iterate over finger table entries. */
5809 for (i = 0; i < MAX_FINGERS; i++)
5811 current_finger = &finger_table[i];
5813 /* No finger stored at this trail index or I am the finger. */
5814 if ((GNUNET_NO == current_finger->is_present) ||
5815 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5819 /* Is disconnected_peer a finger? */
5820 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5821 ¤t_finger->finger_identity))
5823 remove_existing_finger (current_finger, i);
5826 /* If finger is a friend but not disconnected_friend, then continue. */
5827 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5828 ¤t_finger->finger_identity))
5831 /* Iterate over the list of trails to reach remove_finger. Check if
5832 * disconnected_friend is the first friend in any of the trail. */
5833 removed_trails_count = remove_matching_trails (disconnected_peer,
5835 current_finger->trails_count =
5836 current_finger->trails_count - removed_trails_count;
5837 if (0 == current_finger->trails_count)
5839 current_finger->is_present = GNUNET_NO;
5840 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5847 * Method called whenever a peer disconnects.
5849 * @param cls closure
5850 * @param peer peer identity this notification is about
5853 handle_core_disconnect (void *cls,
5854 const struct GNUNET_PeerIdentity *peer)
5856 struct FriendInfo *remove_friend;
5857 struct P2PPendingMessage *pos;
5858 unsigned int discarded;
5860 /* If disconnected to own identity, then return. */
5861 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5864 if(NULL == (remove_friend =
5865 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
5867 DEBUG("\n friend already disconnected.");
5871 remove_matching_fingers (peer);
5872 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5873 GNUNET_assert (GNUNET_YES ==
5874 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5878 /* Remove all the messages queued in pending list of this peer is discarded.*/
5879 if (remove_friend->th != NULL)
5881 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
5882 remove_friend->th = NULL;
5886 while (NULL != (pos = remove_friend->head))
5888 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
5893 GNUNET_STATISTICS_update (GDS_stats,
5895 ("# Queued messages discarded (peer disconnected)"),
5896 discarded, GNUNET_NO);
5897 //GNUNET_free (remove_friend);
5899 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5902 if (NULL != find_finger_trail_task)
5904 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5905 find_finger_trail_task = NULL;
5913 * Method called whenever a peer connects.
5915 * @param cls closure
5916 * @param peer_identity peer identity this notification is about
5919 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5921 struct FriendInfo *friend;
5923 /* Check for connect to self message */
5924 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5927 /* If peer already exists in our friend_peermap, then exit. */
5928 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5935 friend = GNUNET_new (struct FriendInfo);
5936 friend->id = *peer_identity;
5938 GNUNET_assert (GNUNET_OK ==
5939 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5940 peer_identity, friend,
5941 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5943 /* FIXME: now we are not making a distinction between fingers which are friends
5944 * also.But later, we should add a congestion timestamp on the friend, so that it is
5945 * selected after some time out. This is to ensure that both peers have added
5946 * each other as their friend. */
5947 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5948 if (NULL == find_finger_trail_task)
5950 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5956 * To be called on core init/fail.
5958 * @param cls service closure
5959 * @param identity the public identity of this peer
5962 core_init (void *cls,
5963 const struct GNUNET_PeerIdentity *identity)
5965 my_identity = *identity;
5970 * Initialize finger table entries.
5973 finger_table_init ()
5975 memset (&finger_table, 0, sizeof (finger_table));
5980 * Initialize neighbours subsystem.
5981 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5984 GDS_NEIGHBOURS_init (void)
5986 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5987 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5988 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5989 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5990 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5991 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5992 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5993 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5994 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5995 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5996 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5997 sizeof (struct PeerTrailTearDownMessage)},
5998 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5999 {&handle_dht_p2p_notify_succ_confirmation, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION,
6000 sizeof (struct PeerNotifyConfirmationMessage)},
6005 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
6006 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
6007 GNUNET_NO, core_handlers);
6009 if (NULL == core_api)
6010 return GNUNET_SYSERR;
6012 //TODO: check size of this peer map?
6013 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
6014 finger_table_init ();
6015 successor_times = 10;
6016 fingers_round_count = 5;
6017 find_finger_trail_task_next_send_time.rel_value_us =
6018 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
6019 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6020 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
6022 verify_successor_next_send_time.rel_value_us =
6023 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
6024 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6025 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
6027 verify_successor_retry_time.rel_value_us =
6028 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6029 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6030 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6032 notify_successor_retry_time.rel_value_us =
6033 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6034 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6035 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6043 * Free the memory held up by trails of a finger.
6046 delete_finger_table_entries()
6051 for(i = 0; i < MAX_FINGERS; i++)
6053 if(GNUNET_YES == finger_table[i].is_present)
6055 for(j = 0; j < finger_table[i].trails_count; j++)
6056 free_trail(&finger_table[i].trail_list[j]);
6063 * Shutdown neighbours subsystem.
6066 GDS_NEIGHBOURS_done (void)
6068 if (NULL == core_api)
6071 GNUNET_CORE_disconnect (core_api);
6074 delete_finger_table_entries();
6075 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6076 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6077 friend_peermap = NULL;
6079 if (NULL != find_finger_trail_task)
6081 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6082 find_finger_trail_task = NULL;
6085 if (NULL != send_verify_successor_task)
6087 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6088 send_verify_successor_task = NULL;
6091 if (NULL != send_verify_successor_retry_task)
6093 struct VerifySuccessorContext *ctx;
6094 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
6096 send_verify_successor_retry_task = NULL;
6099 if (send_notify_new_successor_retry_task != NULL)
6101 struct SendNotifyContext *notify_ctx;
6102 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
6103 GNUNET_free (notify_ctx->successor_trail);
6104 GNUNET_free (notify_ctx);
6105 send_notify_new_successor_retry_task = NULL;
6113 * @return my identity
6115 struct GNUNET_PeerIdentity
6116 GDS_NEIGHBOURS_get_my_id (void)
6121 /* end of gnunet-service-xdht_neighbours.c */