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);
3743 * FIXME: Check for loop in the request. If you already are part of get path,
3744 * then you need to reset the get path length.
3745 * Core handler for p2p get requests.
3747 * @param cls closure
3748 * @param peer sender of the request
3749 * @param message message
3750 * @return #GNUNET_OK to keep the connection open,
3751 * #GNUNET_SYSERR to close it (signal serious error)
3754 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3755 const struct GNUNET_MessageHeader *message)
3757 const struct PeerGetMessage *get;
3758 const struct GNUNET_PeerIdentity *get_path;
3759 struct GNUNET_PeerIdentity best_known_dest;
3760 struct GNUNET_PeerIdentity current_best_known_dest;
3761 struct GNUNET_HashCode intermediate_trail_id;
3762 struct GNUNET_HashCode received_intermediate_trail_id;
3763 struct Closest_Peer successor;
3764 struct GNUNET_PeerIdentity next_hop;
3765 struct GNUNET_PeerIdentity *next_routing_hop;
3766 uint32_t get_length;
3771 msize = ntohs (message->size);
3772 if (msize < sizeof (struct PeerGetMessage))
3774 GNUNET_break_op (0);
3778 get = (const struct PeerGetMessage *)message;
3779 get_length = ntohl (get->get_path_length);
3781 sizeof (struct PeerGetMessage) +
3782 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3784 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3786 GNUNET_break_op (0);
3790 current_best_known_dest = get->best_known_destination;
3791 received_intermediate_trail_id = get->intermediate_trail_id;
3792 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3793 hop_count = get->hop_count;
3797 GNUNET_STATISTICS_update (GDS_stats,
3799 ("# Bytes received from other peers"), msize,
3802 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3803 key_value = GNUNET_ntohll (key_value);
3805 /* Check if you are already a part of get path. */
3807 for (i = 0; i < get_length; i++)
3809 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &get_path[i]))
3816 /* Add yourself in the get path. */
3817 struct GNUNET_PeerIdentity gp[get_length + 1];
3818 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3819 gp[get_length] = my_identity;
3820 get_length = get_length + 1;
3821 GDS_CLIENTS_process_get (get->options, get->block_type, hop_count,
3822 get->desired_replication_level, get->get_path_length,
3826 successor = find_local_best_known_next_hop (key_value,
3827 GDS_FINGER_TYPE_NON_PREDECESSOR);
3828 next_hop = successor.next_hop;
3829 best_known_dest = successor.best_known_destination;
3830 intermediate_trail_id = successor.trail_id;
3831 /* I am not the final destination. I am part of trail to reach final dest. */
3832 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3834 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3835 GDS_ROUTING_SRC_TO_DEST);
3836 if (NULL != next_routing_hop)
3838 next_hop = *next_routing_hop;
3839 best_known_dest = current_best_known_dest;
3840 intermediate_trail_id = received_intermediate_trail_id;
3844 /* I am the final destination. */
3845 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3847 if (1 == get_length)
3849 DEBUG("\n GET_REQUEST DONE for key = %s",GNUNET_h2s(&get->key));
3850 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0,
3851 NULL, 0, 1, &my_identity, NULL,&my_identity);
3855 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3856 get_length, gp, &gp[get_length - 2],
3863 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3864 get->desired_replication_level, best_known_dest,
3865 intermediate_trail_id, &next_hop, hop_count,
3873 * Core handler for get result
3874 * @param cls closure
3875 * @param peer sender of the request
3876 * @param message message
3877 * @return #GNUNET_OK to keep the connection open,
3878 * #GNUNET_SYSERR to close it (signal serious error)
3881 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3882 const struct GNUNET_MessageHeader *message)
3884 const struct PeerGetResultMessage *get_result;
3885 const struct GNUNET_PeerIdentity *get_path;
3886 const struct GNUNET_PeerIdentity *put_path;
3887 const void *payload;
3888 size_t payload_size;
3890 unsigned int getlen;
3891 unsigned int putlen;
3892 int current_path_index;
3894 msize = ntohs (message->size);
3895 if (msize < sizeof (struct PeerGetResultMessage))
3897 GNUNET_break_op (0);
3901 get_result = (const struct PeerGetResultMessage *)message;
3902 getlen = ntohl (get_result->get_path_length);
3903 putlen = ntohl (get_result->put_path_length);
3906 sizeof (struct PeerGetResultMessage) +
3907 getlen * sizeof (struct GNUNET_PeerIdentity) +
3908 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3910 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3912 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3914 GNUNET_break_op (0);
3917 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3918 GNUNET_STATISTICS_update (GDS_stats,
3920 ("# Bytes received from other peers"), msize,
3923 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3924 get_path = &put_path[putlen];
3925 payload = (const void *) &get_path[getlen];
3926 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3927 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3929 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3931 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
3933 getlen, get_path, putlen,
3934 put_path, get_result->type, payload_size, payload);
3939 current_path_index = search_my_index (get_path, getlen);
3940 if (-1 == current_path_index )
3942 DEBUG ("No entry found in get path.\n");
3944 return GNUNET_SYSERR;
3946 if((getlen + 1) == current_path_index)
3948 DEBUG("Present twice in get path. Not allowed. \n");
3950 return GNUNET_SYSERR;
3952 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3953 &get_path[current_path_index - 1],
3954 &(get_result->querying_peer), putlen, put_path,
3956 GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
3957 payload, payload_size);
3960 return GNUNET_SYSERR;
3965 * Find the next hop to pass trail setup message. First find the local best known
3966 * hop from your own identity, friends and finger. If you were part of trail,
3967 * then get the next hop from routing table. Compare next_hop from routing table
3968 * and local best known hop, and return the closest one to final_dest_finger_val
3969 * @param final_dest_finger_val 64 bit value of finger identity
3970 * @param intermediate_trail_id If you are part of trail to reach to some other
3971 * finger, then it is the trail id to reach to
3972 * that finger, else set to 0.
3973 * @param is_predecessor Are we looking for closest successor or predecessor.
3974 * @param source Source of trail setup message.
3975 * @param current_dest In case you are part of trail, then finger to which
3976 * we should forward the message. Else my own identity
3977 * @return Closest Peer for @a final_dest_finger_val
3979 static struct Closest_Peer
3980 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3981 struct GNUNET_HashCode intermediate_trail_id,
3982 unsigned int is_predecessor,
3983 struct GNUNET_PeerIdentity source,
3984 struct GNUNET_PeerIdentity *current_dest)
3986 struct Closest_Peer peer;
3988 peer = find_local_best_known_next_hop (final_dest_finger_val, is_predecessor);
3990 /* Am I just a part of a trail towards a finger (current_destination)? */
3991 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3992 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3995 struct GNUNET_PeerIdentity closest_peer;
3997 /* Select best successor among one found locally and current_destination
3998 * that we got from network.*/
3999 closest_peer = select_closest_peer (&peer.best_known_destination,
4001 final_dest_finger_val,
4004 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
4005 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
4007 struct GNUNET_PeerIdentity *next_hop;
4009 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4010 GDS_ROUTING_SRC_TO_DEST);
4011 /* next_hop NULL is a valid case. This intermediate trail id is set by
4012 some other finger, and while this trail setup is in progress, that other
4013 peer might have found a better trail ,and send trail teardown message
4014 across the network. In case we got the trail teardown message first,
4015 then next_hop will be NULL. A possible solution could be to keep track
4016 * of all removed trail id, and be sure that there is no other reason . */
4017 if(NULL != next_hop)
4019 peer.next_hop = *next_hop;
4020 peer.best_known_destination = *current_dest;
4021 peer.trail_id = intermediate_trail_id;
4030 * Core handle for PeerTrailSetupMessage.
4031 * @param cls closure
4032 * @param message message
4033 * @param peer peer identity this notification is about
4034 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4037 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
4038 const struct GNUNET_MessageHeader *message)
4040 const struct PeerTrailSetupMessage *trail_setup;
4041 const struct GNUNET_PeerIdentity *trail_peer_list;
4042 struct GNUNET_PeerIdentity current_dest;
4043 struct FriendInfo *target_friend;
4044 struct GNUNET_PeerIdentity source;
4045 struct GNUNET_HashCode intermediate_trail_id;
4046 struct GNUNET_HashCode trail_id;
4047 unsigned int is_predecessor;
4048 uint32_t trail_length;
4049 uint64_t final_dest_finger_val;
4053 msize = ntohs (message->size);
4054 if (msize < sizeof (struct PeerTrailSetupMessage))
4056 GNUNET_break_op (0);
4057 return GNUNET_SYSERR;
4060 trail_setup = (const struct PeerTrailSetupMessage *) message;
4061 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4062 sizeof (struct GNUNET_PeerIdentity) != 0)
4064 GNUNET_break_op (0);
4067 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4068 sizeof (struct GNUNET_PeerIdentity);
4070 GNUNET_STATISTICS_update (GDS_stats,
4072 ("# Bytes received from other peers"), msize,
4075 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4076 current_dest = trail_setup->best_known_destination;
4077 trail_id = trail_setup->trail_id;
4078 final_dest_finger_val =
4079 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4080 source = trail_setup->source_peer;
4081 is_predecessor = ntohl (trail_setup->is_predecessor);
4082 intermediate_trail_id = trail_setup->intermediate_trail_id;
4084 /* Did the friend insert its ID in the trail list? */
4085 if (trail_length > 0 &&
4086 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
4088 GNUNET_break_op (0);
4089 return GNUNET_SYSERR;
4092 /* If I was the source and got the message back, then set trail length to 0.*/
4093 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4098 /* Check if you are present in the trail seen so far? */
4099 for (i = 0; i < trail_length ; i++)
4101 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4103 /* We will add ourself later in code, if NOT destination. */
4109 /* Is my routing table full? */
4110 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4112 if (trail_length > 0)
4114 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4115 &trail_peer_list[trail_length - 1]);
4118 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4120 if(NULL == target_friend)
4122 DEBUG ("\n friend not found");
4126 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4127 my_identity, is_predecessor,
4128 trail_peer_list, trail_length,
4129 trail_id, target_friend,
4130 CONGESTION_TIMEOUT);
4134 /* Get the next hop to forward the trail setup request. */
4135 struct Closest_Peer next_peer =
4136 get_local_best_known_next_hop (final_dest_finger_val,
4137 intermediate_trail_id,
4142 /* Am I the final destination? */
4143 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4146 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4148 finger_table_add (my_identity, NULL, 0, is_predecessor,
4149 final_dest_finger_val, trail_id);
4153 if (trail_length > 0)
4155 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4156 &trail_peer_list[trail_length-1]);
4159 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4160 if (NULL == target_friend)
4162 GNUNET_break_op (0);
4163 return GNUNET_SYSERR;
4165 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4166 GDS_NEIGHBOURS_send_trail_setup_result (source,
4168 target_friend, trail_length,
4171 final_dest_finger_val,trail_id);
4173 else /* I'm not the final destination. */
4175 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4176 &next_peer.next_hop);
4177 if(NULL == target_friend)
4179 DEBUG ("\n target friend not found for peer = %s", GNUNET_i2s(&next_peer.next_hop));
4183 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4185 /* Add yourself to list of peers. */
4186 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4188 memcpy (peer_list, trail_peer_list,
4189 trail_length * sizeof (struct GNUNET_PeerIdentity));
4190 peer_list[trail_length] = my_identity;
4191 GDS_NEIGHBOURS_send_trail_setup (source,
4192 final_dest_finger_val,
4193 next_peer.best_known_destination,
4194 target_friend, trail_length + 1, peer_list,
4195 is_predecessor, trail_id,
4196 next_peer.trail_id);
4199 GDS_NEIGHBOURS_send_trail_setup (source,
4200 final_dest_finger_val,
4201 next_peer.best_known_destination,
4202 target_friend, 0, NULL,
4203 is_predecessor, trail_id,
4204 next_peer.trail_id);
4211 * Core handle for p2p trail setup result messages.
4213 * @param message message
4214 * @param peer sender of this message.
4215 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4218 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4219 const struct GNUNET_MessageHeader *message)
4221 const struct PeerTrailSetupResultMessage *trail_result;
4222 const struct GNUNET_PeerIdentity *trail_peer_list;
4223 struct GNUNET_PeerIdentity next_hop;
4224 struct FriendInfo *target_friend;
4225 struct GNUNET_PeerIdentity querying_peer;
4226 struct GNUNET_PeerIdentity finger_identity;
4227 uint32_t trail_length;
4228 uint64_t ulitmate_destination_finger_value;
4229 uint32_t is_predecessor;
4230 struct GNUNET_HashCode trail_id;
4234 msize = ntohs (message->size);
4235 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4237 GNUNET_break_op (0);
4241 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4242 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4243 sizeof (struct GNUNET_PeerIdentity) != 0)
4245 GNUNET_break_op (0);
4248 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4249 sizeof (struct GNUNET_PeerIdentity);
4251 GNUNET_STATISTICS_update (GDS_stats,
4253 ("# Bytes received from other peers"), msize,
4256 is_predecessor = ntohl (trail_result->is_predecessor);
4257 querying_peer = trail_result->querying_peer;
4258 finger_identity = trail_result->finger_identity;
4259 trail_id = trail_result->trail_id;
4260 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4261 ulitmate_destination_finger_value =
4262 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4264 /* Am I the one who initiated the query? */
4265 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4267 /* Check that you got the message from the correct peer. */
4268 if (trail_length > 0)
4270 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4275 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4278 GDS_ROUTING_add (trail_id, my_identity, *peer);
4279 finger_table_add (finger_identity, trail_peer_list, trail_length,
4280 is_predecessor, ulitmate_destination_finger_value, trail_id);
4284 /* Get my location in the trail. */
4285 my_index = search_my_index (trail_peer_list, trail_length);
4288 DEBUG ("Not found in trail\n");
4290 return GNUNET_SYSERR;
4293 if ((trail_length + 1) == my_index)
4295 DEBUG ("Found twice in trail.\n");
4297 return GNUNET_SYSERR;
4300 //TODO; Refactor code here and above to check if sender peer is correct
4303 if(trail_length > 1)
4304 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4307 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4309 next_hop = trail_result->querying_peer;
4313 if(my_index == trail_length - 1)
4316 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4321 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4323 next_hop = trail_peer_list[my_index - 1];
4326 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4327 if (NULL == target_friend)
4329 GNUNET_break_op (0);
4330 return GNUNET_SYSERR;
4332 GDS_ROUTING_add (trail_id, next_hop, *peer);
4333 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4334 target_friend, trail_length, trail_peer_list,
4336 ulitmate_destination_finger_value,
4344 * @param trail Trail to be inverted
4345 * @param trail_length Total number of peers in the trail.
4346 * @return Updated trail
4348 static struct GNUNET_PeerIdentity *
4349 invert_trail (const struct GNUNET_PeerIdentity *trail,
4350 unsigned int trail_length)
4354 struct GNUNET_PeerIdentity *inverted_trail;
4356 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4359 j = trail_length - 1;
4360 while (i < trail_length)
4362 inverted_trail[i] = trail[j];
4367 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4368 &inverted_trail[0]));
4369 return inverted_trail;
4374 * Return the shortest trail among all the trails to reach to finger from me.
4375 * @param finger Finger
4376 * @param shortest_trail_length[out] Trail length of shortest trail from me
4378 * @return Shortest trail.
4380 static struct GNUNET_PeerIdentity *
4381 get_shortest_trail (struct FingerInfo *finger,
4382 unsigned int *trail_length)
4384 struct Trail *trail;
4385 unsigned int flag = 0;
4386 unsigned int shortest_trail_index = 0;
4387 int shortest_trail_length = -1;
4388 struct Trail_Element *trail_element;
4389 struct GNUNET_PeerIdentity *trail_list;
4392 /* Get the shortest trail to reach to current successor. */
4393 for (i = 0; i < finger->trails_count; i++)
4395 trail = &finger->trail_list[i];
4399 shortest_trail_index = i;
4400 shortest_trail_length = trail->trail_length;
4405 if (shortest_trail_length > trail->trail_length)
4407 shortest_trail_index = i;
4408 shortest_trail_length = trail->trail_length;
4413 /* Copy the shortest trail and return. */
4414 trail = &finger->trail_list[shortest_trail_index];
4415 trail_element = trail->trail_head;
4417 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4418 shortest_trail_length);
4420 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4422 trail_list[i] = trail_element->peer;
4425 GNUNET_assert(shortest_trail_length != -1);
4427 *trail_length = shortest_trail_length;
4433 * Check if trail_1 and trail_2 have any common element. If yes then join
4434 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4435 * @param trail_1 Trail from source to me, NOT including endpoints.
4436 * @param trail_1_len Total number of peers @a trail_1
4437 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4438 * @param trail_2_len Total number of peers @a trail_2
4439 * @param joined_trail_len Total number of peers in combined trail of trail_1
4441 * @return Joined trail.
4443 static struct GNUNET_PeerIdentity *
4444 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4445 unsigned int trail_1_len,
4446 struct GNUNET_PeerIdentity *trail_2,
4447 unsigned int trail_2_len,
4448 unsigned int *joined_trail_len)
4450 struct GNUNET_PeerIdentity *joined_trail;
4455 for (i = 0; i < trail_1_len; i++)
4457 for (j = 0; j < trail_2_len; j++)
4459 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4462 *joined_trail_len = i + (trail_2_len - j);
4463 joined_trail = GNUNET_malloc (*joined_trail_len *
4464 sizeof(struct GNUNET_PeerIdentity));
4467 /* Copy all the elements from 0 to i into joined_trail. */
4468 for(k = 0; k < ( i+1); k++)
4470 joined_trail[k] = trail_1[k];
4473 /* Increment j as entry stored is same as entry stored at i*/
4476 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4477 while(k <= (*joined_trail_len - 1))
4479 joined_trail[k] = trail_2[j];
4484 return joined_trail;
4488 /* Here you should join the trails. */
4489 *joined_trail_len = trail_1_len + trail_2_len + 1;
4490 joined_trail = GNUNET_malloc (*joined_trail_len *
4491 sizeof(struct GNUNET_PeerIdentity));
4494 for(i = 0; i < trail_1_len;i++)
4496 joined_trail[i] = trail_1[i];
4499 joined_trail[i] = my_identity;
4502 for (j = 0; i < *joined_trail_len; i++,j++)
4504 joined_trail[i] = trail_2[j];
4507 return joined_trail;
4512 * Return the trail from source to my current predecessor. Check if source
4513 * is already part of the this trail, if yes then return the shorten trail.
4514 * @param current_trail Trail from source to me, NOT including the endpoints.
4515 * @param current_trail_length Number of peers in @a current_trail.
4516 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4517 * source to my predecessor, NOT including
4519 * @return Trail from source to my predecessor.
4521 static struct GNUNET_PeerIdentity *
4522 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4523 const struct GNUNET_PeerIdentity *trail_src_to_me,
4524 unsigned int trail_src_to_me_len,
4525 unsigned int *trail_src_to_curr_pred_length)
4527 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4528 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4529 unsigned int trail_me_to_curr_pred_length;
4530 struct FingerInfo *current_predecessor;
4535 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4537 /* Check if trail_src_to_me contains current_predecessor. */
4538 for (i = 0; i < trail_src_to_me_len; i++)
4540 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4541 ¤t_predecessor->finger_identity))
4545 *trail_src_to_curr_pred_length = i;
4550 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4551 sizeof(struct GNUNET_PeerIdentity));
4552 for (j = 0; j < i; j++)
4553 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4554 return trail_src_to_curr_pred;
4558 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4559 &trail_me_to_curr_pred_length);
4561 /* Check if trail contains the source_peer. */
4562 for (i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4564 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4565 &trail_me_to_curr_pred[i]))
4568 /* Source is NOT part of trail. */
4571 /* Source is the last element in the trail to reach to my pred.
4572 Source is direct friend of the pred. */
4573 if (trail_me_to_curr_pred_length == i)
4575 *trail_src_to_curr_pred_length = 0;
4576 GNUNET_free_non_null (trail_me_to_curr_pred);
4580 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4581 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4582 *trail_src_to_curr_pred_length);
4584 for (j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4585 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4586 GNUNET_free_non_null (trail_me_to_curr_pred);
4587 return trail_src_to_curr_pred;
4590 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4591 trail_src_to_me_len,
4592 trail_me_to_curr_pred,
4593 trail_me_to_curr_pred_length,
4595 *trail_src_to_curr_pred_length = len;
4596 GNUNET_free_non_null(trail_me_to_curr_pred);
4597 return trail_src_to_curr_pred;
4602 * Add finger as your predecessor. To add, first generate a new trail id, invert
4603 * the trail to get the trail from me to finger, add an entry in your routing
4604 * table, send add trail message to peers which are part of trail from me to
4605 * finger and add finger in finger table.
4608 * @param trail_length
4611 update_predecessor (struct GNUNET_PeerIdentity finger,
4612 struct GNUNET_PeerIdentity *trail,
4613 unsigned int trail_length)
4615 struct GNUNET_HashCode trail_to_new_predecessor_id;
4616 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4617 struct FriendInfo *target_friend;
4619 /* Generate trail id for trail from me to new predecessor = finger. */
4620 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4621 &trail_to_new_predecessor_id,
4622 sizeof (trail_to_new_predecessor_id));
4624 if (0 == trail_length)
4626 trail_to_new_predecessor = NULL;
4627 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4628 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger);
4629 if (NULL == target_friend)
4637 /* Invert the trail to get the trail from me to finger, NOT including the
4639 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4640 &trail[trail_length-1]));
4641 trail_to_new_predecessor = invert_trail (trail, trail_length);
4643 /* Add an entry in your routing table. */
4644 GDS_ROUTING_add (trail_to_new_predecessor_id,
4646 trail_to_new_predecessor[0]);
4648 GNUNET_assert (NULL != (target_friend =
4649 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4650 &trail_to_new_predecessor[0])));
4653 /* Add entry in routing table of all peers that are part of trail from me
4654 to finger, including finger. */
4655 GDS_NEIGHBOURS_send_add_trail (my_identity,
4657 trail_to_new_predecessor_id,
4658 trail_to_new_predecessor,
4662 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4663 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4664 GNUNET_free_non_null(trail_to_new_predecessor);
4669 * Check if you already have a predecessor. If not then add finger as your
4670 * predecessor. If you have predecessor, then compare two peer identites.
4671 * If finger is correct predecessor, then remove the old entry, add finger in
4672 * finger table and send add_trail message to add the trail in the routing
4673 * table of all peers which are part of trail to reach from me to finger.
4674 * @param finger New peer which may be our predecessor.
4675 * @param trail List of peers to reach from @finger to me.
4676 * @param trail_length Total number of peer in @a trail.
4679 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4680 struct GNUNET_PeerIdentity *trail,
4681 unsigned int trail_length)
4683 struct FingerInfo *current_predecessor;
4684 struct GNUNET_PeerIdentity closest_peer;
4685 uint64_t predecessor_value;
4686 unsigned int is_predecessor = 1;
4688 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4689 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4691 /* No predecessor. Add finger as your predecessor. */
4692 if (GNUNET_NO == current_predecessor->is_present)
4694 update_predecessor (finger, trail, trail_length);
4698 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4704 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4705 closest_peer = select_closest_peer (&finger,
4706 ¤t_predecessor->finger_identity,
4707 predecessor_value, is_predecessor);
4709 /* Finger is the closest predecessor. Remove the existing one and add the new
4711 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4713 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4714 update_predecessor (finger, trail, trail_length);
4722 * Core handle for p2p verify successor messages.
4723 * @param cls closure
4724 * @param message message
4725 * @param peer peer identity this notification is about
4726 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4729 handle_dht_p2p_verify_successor(void *cls,
4730 const struct GNUNET_PeerIdentity *peer,
4731 const struct GNUNET_MessageHeader *message)
4733 const struct PeerVerifySuccessorMessage *vsm;
4734 struct GNUNET_HashCode trail_id;
4735 struct GNUNET_PeerIdentity successor;
4736 struct GNUNET_PeerIdentity source_peer;
4737 struct GNUNET_PeerIdentity *trail;
4738 struct GNUNET_PeerIdentity *next_hop;
4739 struct FingerInfo current_predecessor;
4740 struct FriendInfo *target_friend;
4741 unsigned int trail_src_to_curr_pred_len = 0;
4742 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4743 unsigned int trail_length;
4746 msize = ntohs (message->size);
4748 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4750 GNUNET_break_op (0);
4754 vsm = (const struct PeerVerifySuccessorMessage *) message;
4755 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4756 sizeof (struct GNUNET_PeerIdentity);
4757 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4758 sizeof (struct GNUNET_PeerIdentity) != 0)
4760 GNUNET_break_op (0);
4764 GNUNET_STATISTICS_update (GDS_stats,
4766 ("# Bytes received from other peers"), msize,
4769 trail_id = vsm->trail_id;
4770 source_peer = vsm->source_peer;
4771 successor = vsm->successor;
4772 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4774 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4776 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4778 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4779 if (NULL == next_hop)
4784 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4786 if(NULL == target_friend)
4791 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4792 trail_id, trail, trail_length,
4797 /* I am the destination of this message. */
4799 /* Check if the source_peer could be our predecessor and if yes then update
4801 compare_and_update_predecessor (source_peer, trail, trail_length);
4802 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4804 /* Is source of this message NOT my predecessor. */
4805 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4808 trail_src_to_curr_pred =
4809 get_trail_src_to_curr_pred (source_peer,
4812 &trail_src_to_curr_pred_len);
4816 trail_src_to_curr_pred_len = trail_length;
4819 trail_src_to_curr_pred =
4820 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4821 *trail_src_to_curr_pred_len);
4822 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4824 trail_src_to_curr_pred[i] = trail[i];
4828 GNUNET_assert (NULL !=
4830 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4831 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4832 current_predecessor.finger_identity,
4833 trail_id, trail_src_to_curr_pred,
4834 trail_src_to_curr_pred_len,
4835 GDS_ROUTING_DEST_TO_SRC,
4837 GNUNET_free_non_null(trail_src_to_curr_pred);
4843 * If the trail from me to my probable successor contains a friend not
4844 * at index 0, then we can shorten the trail.
4845 * @param probable_successor Peer which is our probable successor
4846 * @param trail_me_to_probable_successor Peers in path from me to my probable
4847 * successor, NOT including the endpoints.
4848 * @param trail_me_to_probable_successor_len Total number of peers in
4849 * @a trail_me_to_probable_succesor.
4850 * @return Updated trail, if any friend found.
4851 * Else the trail_me_to_probable_successor.
4853 struct GNUNET_PeerIdentity *
4854 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4855 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4856 unsigned int trail_me_to_probable_successor_len,
4857 unsigned int *trail_to_new_successor_length)
4861 struct GNUNET_PeerIdentity *trail_to_new_successor;
4863 /* Probable successor is a friend */
4864 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4865 &probable_successor))
4867 trail_to_new_successor = NULL;
4868 *trail_to_new_successor_length = 0;
4869 return trail_to_new_successor;
4872 /* Is there any friend of yours in this trail. */
4873 if(trail_me_to_probable_successor_len > 1)
4875 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4877 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4878 &trail_me_to_probable_successor[i]))
4881 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4882 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4883 *trail_to_new_successor_length);
4886 for(j = 0; j < *trail_to_new_successor_length; i++,j++)
4888 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4891 return trail_to_new_successor;
4895 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4896 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4900 struct SendNotifyContext
4902 struct GNUNET_PeerIdentity source_peer;
4903 struct GNUNET_PeerIdentity successor;
4904 struct GNUNET_PeerIdentity *successor_trail;
4905 unsigned int successor_trail_length;
4906 struct GNUNET_HashCode succesor_trail_id;
4907 struct FriendInfo *target_friend;
4908 unsigned int num_retries_scheduled;
4913 send_notify_new_successor (void *cls);
4917 * Check if the peer which sent us verify successor result message is still ours
4918 * successor or not. If not, then compare existing successor and probable successor.
4919 * In case probable successor is the correct successor, remove the existing
4920 * successor. Add probable successor as new successor. Send notify new successor
4921 * message to new successor.
4922 * @param curr_succ Peer to which we sent the verify successor message. It may
4923 * or may not be our real current successor, as we may have few iterations of
4924 * find finger trail task.
4925 * @param probable_successor Peer which should be our successor accroding to @a
4927 * @param trail List of peers to reach from me to @a probable successor, NOT including
4929 * @param trail_length Total number of peers in @a trail.
4932 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4933 struct GNUNET_PeerIdentity probable_successor,
4934 const struct GNUNET_PeerIdentity *trail,
4935 unsigned int trail_length)
4937 struct FingerInfo *current_successor;
4938 struct GNUNET_PeerIdentity closest_peer;
4939 struct GNUNET_HashCode trail_id;
4940 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4941 struct FriendInfo *target_friend;
4942 unsigned int trail_me_to_probable_succ_len;
4943 unsigned int is_predecessor = 0;
4944 uint64_t successor_value;
4946 current_successor = &finger_table[0];
4947 successor_value = compute_finger_identity_value(0);
4949 /* If probable successor is same as current_successor, do nothing. */
4950 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
4951 ¤t_successor->finger_identity))
4953 if ((NULL != GDS_stats))
4959 memcpy (&my_id, &my_identity, sizeof(uint64_t));
4960 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4961 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4962 succ = GNUNET_ntohll(succ);
4963 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4964 GNUNET_free (my_id_str);
4966 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4969 if (send_verify_successor_task == NULL)
4970 send_verify_successor_task =
4971 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
4972 &send_verify_successor_message,
4976 closest_peer = select_closest_peer (&probable_successor,
4977 ¤t_successor->finger_identity,
4978 successor_value, is_predecessor);
4980 /* If the current_successor in the finger table is closest, then do nothing. */
4981 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
4982 ¤t_successor->finger_identity))
4984 //FIXME: Is this a good place to return the stats.
4985 if ((NULL != GDS_stats))
4991 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4992 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4993 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4994 GNUNET_free (my_id_str);
4995 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4999 if(0 == successor_times)
5001 // successor_times = 3;
5002 verify_successor_next_send_time =
5003 GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time);
5009 if (send_verify_successor_task == NULL)
5010 send_verify_successor_task =
5011 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5012 &send_verify_successor_message,
5017 /* Probable successor is the closest peer.*/
5018 if(trail_length > 0)
5020 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5025 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5026 &probable_successor));
5029 trail_me_to_probable_succ_len = 0;
5030 trail_me_to_probable_succ =
5031 check_trail_me_to_probable_succ (probable_successor,
5032 trail, trail_length,
5033 &trail_me_to_probable_succ_len);
5035 /* Remove the existing successor. */
5036 remove_existing_finger (current_successor, 0);
5037 /* Generate a new trail id to reach to your new successor. */
5038 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5039 &trail_id, sizeof (trail_id));
5041 if (trail_me_to_probable_succ_len > 0)
5043 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
5044 GNUNET_assert (NULL !=
5046 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5047 &trail_me_to_probable_succ[0])));
5051 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5052 GNUNET_assert (NULL !=
5054 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5055 &probable_successor)));
5058 add_new_finger (probable_successor, trail_me_to_probable_succ,
5059 trail_me_to_probable_succ_len, trail_id, 0);
5061 struct SendNotifyContext *notify_ctx;
5063 notify_ctx = GNUNET_new(struct SendNotifyContext);
5065 notify_ctx->source_peer = my_identity;
5066 notify_ctx->successor = probable_successor;
5067 notify_ctx->successor_trail =
5068 GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5069 memcpy(notify_ctx->successor_trail, trail_me_to_probable_succ,
5070 sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5071 notify_ctx->successor_trail_length = trail_me_to_probable_succ_len;
5072 notify_ctx->succesor_trail_id = trail_id;
5073 notify_ctx->target_friend = target_friend;
5074 notify_ctx->num_retries_scheduled = 0;
5075 GNUNET_free_non_null (trail_me_to_probable_succ);
5077 // TODO: Check if we should verify before schedule if already scheduled.
5078 GNUNET_SCHEDULER_add_now(&send_notify_new_successor, (void*)notify_ctx);
5084 send_notify_new_successor (void *cls)
5086 struct SendNotifyContext *ctx = cls;
5088 GDS_NEIGHBOURS_send_notify_new_successor (ctx->source_peer,
5090 ctx->successor_trail,
5091 ctx->successor_trail_length,
5092 ctx->succesor_trail_id,
5093 ctx->target_friend);
5095 if (0 == ctx->num_retries_scheduled &&
5096 send_notify_new_successor_retry_task != NULL)
5098 // Result from previous notify successos hasn't arrived, so the retry task
5099 // hasn't been cancelled! Already a new notify successor must be called.
5100 // We will cancel the retry request.
5101 struct SendNotifyContext *old_notify_ctx;
5102 old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5103 GNUNET_free (old_notify_ctx->successor_trail);
5104 GNUNET_free (old_notify_ctx);
5105 send_notify_new_successor_retry_task = NULL;
5108 ctx->num_retries_scheduled++;
5109 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_add_delayed(notify_successor_retry_time,
5110 &send_notify_new_successor,
5115 * Core handle for p2p verify successor result messages.
5116 * @param cls closure
5117 * @param message message
5118 * @param peer peer identity this notification is about
5119 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5122 handle_dht_p2p_verify_successor_result(void *cls,
5123 const struct GNUNET_PeerIdentity *peer,
5124 const struct GNUNET_MessageHeader *message)
5126 const struct PeerVerifySuccessorResultMessage *vsrm;
5127 enum GDS_ROUTING_trail_direction trail_direction;
5128 struct GNUNET_PeerIdentity querying_peer;
5129 struct GNUNET_HashCode trail_id;
5130 struct GNUNET_PeerIdentity *next_hop;
5131 struct FriendInfo *target_friend;
5132 struct GNUNET_PeerIdentity probable_successor;
5133 struct GNUNET_PeerIdentity current_successor;
5134 const struct GNUNET_PeerIdentity *trail;
5135 unsigned int trail_length;
5138 msize = ntohs (message->size);
5139 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5141 GNUNET_break_op (0);
5145 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5146 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5147 sizeof (struct GNUNET_PeerIdentity) != 0)
5149 GNUNET_break_op (0);
5152 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5153 sizeof (struct GNUNET_PeerIdentity);
5155 GNUNET_STATISTICS_update (GDS_stats,
5157 ("# Bytes received from other peers"), msize,
5160 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5161 querying_peer = vsrm->querying_peer;
5162 trail_direction = ntohl (vsrm->trail_direction);
5163 trail_id = vsrm->trail_id;
5164 probable_successor = vsrm->probable_successor;
5165 current_successor = vsrm->current_successor;
5167 /* I am the querying_peer. */
5168 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5170 /* Cancel Retry Task */
5171 if (NULL != send_verify_successor_retry_task)
5173 struct VerifySuccessorContext *ctx;
5174 ctx = GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
5176 send_verify_successor_retry_task = NULL;
5178 compare_and_update_successor (current_successor,
5179 probable_successor, trail, trail_length);
5183 /*If you are not the querying peer then pass on the message */
5184 if(NULL == (next_hop =
5185 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
5187 /* Here it may happen that source peer has found a new successor, and removed
5188 the trail, Hence no entry found in the routing table. Fail silently.*/
5189 DEBUG (" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
5190 GNUNET_i2s (&my_identity),
5191 GNUNET_h2s (&trail_id),
5196 if (NULL == (target_friend =
5197 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5202 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5203 vsrm->current_successor,
5204 probable_successor, trail_id,
5207 trail_direction, target_friend);
5213 * Core handle for p2p notify new successor messages.
5214 * @param cls closure
5215 * @param message message
5216 * @param peer peer identity this notification is about
5217 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5220 handle_dht_p2p_notify_new_successor(void *cls,
5221 const struct GNUNET_PeerIdentity *peer,
5222 const struct GNUNET_MessageHeader *message)
5224 const struct PeerNotifyNewSuccessorMessage *nsm;
5225 struct GNUNET_PeerIdentity *trail;
5226 struct GNUNET_PeerIdentity source;
5227 struct GNUNET_PeerIdentity new_successor;
5228 struct GNUNET_HashCode trail_id;
5229 struct GNUNET_PeerIdentity next_hop;
5230 struct FriendInfo *target_friend;
5233 uint32_t trail_length;
5235 msize = ntohs (message->size);
5236 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5238 GNUNET_break_op (0);
5241 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5242 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5243 sizeof (struct GNUNET_PeerIdentity) != 0)
5245 GNUNET_break_op (0);
5248 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5249 sizeof (struct GNUNET_PeerIdentity);
5250 GNUNET_STATISTICS_update (GDS_stats,
5252 ("# Bytes received from other peers"), msize,
5255 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5256 source = nsm->source_peer;
5257 new_successor = nsm->new_successor;
5258 trail_id = nsm->trail_id;
5260 /* I am the new_successor to source_peer. */
5261 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5263 if(trail_length > 0)
5264 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5267 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5269 compare_and_update_predecessor (source, trail, trail_length);
5270 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5271 GNUNET_assert (NULL != target_friend);
5272 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5273 GDS_ROUTING_DEST_TO_SRC,
5278 GNUNET_assert(trail_length > 0);
5279 /* I am part of trail to reach to successor. */
5280 my_index = search_my_index (trail, trail_length);
5283 DEBUG ("No entry found in trail\n");
5284 GNUNET_break_op (0);
5285 return GNUNET_SYSERR;
5287 if((trail_length + 1) == my_index)
5289 DEBUG ("Found twice in trail.\n");
5290 GNUNET_break_op (0);
5291 return GNUNET_SYSERR;
5293 if ((trail_length-1) == my_index)
5294 next_hop = new_successor;
5296 next_hop = trail[my_index + 1];
5298 GDS_ROUTING_add(trail_id, *peer, next_hop);
5300 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
5301 if (NULL == target_friend)
5306 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5308 trail_id, target_friend);
5315 * Core handler for P2P notify successor message
5316 * @param cls closure
5317 * @param message message
5318 * @param peer peer identity this notification is about
5319 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5322 handle_dht_p2p_notify_succ_confirmation (void *cls,
5323 const struct GNUNET_PeerIdentity *peer,
5324 const struct GNUNET_MessageHeader *message)
5326 const struct PeerNotifyConfirmationMessage *notify_confirmation;
5327 enum GDS_ROUTING_trail_direction trail_direction;
5328 struct GNUNET_HashCode trail_id;
5329 struct FriendInfo *target_friend;
5330 struct GNUNET_PeerIdentity *next_hop;
5333 msize = ntohs (message->size);
5335 if (msize != sizeof (struct PeerNotifyConfirmationMessage))
5337 GNUNET_break_op (0);
5340 GNUNET_STATISTICS_update (GDS_stats,
5342 ("# Bytes received from other peers"), msize,
5345 notify_confirmation = (const struct PeerNotifyConfirmationMessage *) message;
5346 trail_direction = ntohl (notify_confirmation->trail_direction);
5347 trail_id = notify_confirmation->trail_id;
5349 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5350 if (NULL == next_hop)
5352 /* The source of notify new successor, might have found even a better
5353 successor. In that case it send a trail teardown message, and hence,
5354 the next hop is NULL. */
5355 //Fixme: Add some print to confirm the above theory.
5359 /* I peer which sent the notify successor message to the successor. */
5360 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5363 * Schedule another round of verify sucessor with your current successor
5364 * which may or may not be source of this message. This message is used
5365 * only to ensure that we have a path setup to reach to our successor.
5368 // TODO: cancel schedule of notify_successor_retry_task
5369 if (send_notify_new_successor_retry_task != NULL)
5371 struct SendNotifyContext *notify_ctx;
5372 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5373 GNUNET_free (notify_ctx->successor_trail);
5374 GNUNET_free (notify_ctx);
5375 send_notify_new_successor_retry_task = NULL;
5377 if (send_verify_successor_task == NULL)
5379 verify_successor_next_send_time.rel_value_us =
5380 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5381 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5382 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5383 send_verify_successor_task =
5384 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5385 &send_verify_successor_message,
5391 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
5392 if (NULL == target_friend)
5394 DEBUG ("\n friend not found, line number = %d",__LINE__);
5395 return GNUNET_SYSERR;
5397 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5398 GDS_ROUTING_DEST_TO_SRC,
5406 * Core handler for P2P trail rejection message
5407 * @param cls closure
5408 * @param message message
5409 * @param peer peer identity this notification is about
5410 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5413 handle_dht_p2p_trail_setup_rejection (void *cls,
5414 const struct GNUNET_PeerIdentity *peer,
5415 const struct GNUNET_MessageHeader *message)
5417 const struct PeerTrailRejectionMessage *trail_rejection;
5418 unsigned int trail_length;
5419 const struct GNUNET_PeerIdentity *trail_peer_list;
5420 struct FriendInfo *target_friend;
5421 struct GNUNET_TIME_Relative congestion_timeout;
5422 struct GNUNET_HashCode trail_id;
5423 struct GNUNET_PeerIdentity next_peer;
5424 struct GNUNET_PeerIdentity source;
5425 uint64_t ultimate_destination_finger_value;
5426 unsigned int is_predecessor;
5429 msize = ntohs (message->size);
5430 if (msize < sizeof (struct PeerTrailRejectionMessage))
5432 GNUNET_break_op (0);
5435 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5436 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5437 sizeof (struct GNUNET_PeerIdentity) != 0)
5439 GNUNET_break_op (0);
5442 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5443 sizeof (struct GNUNET_PeerIdentity);
5444 GNUNET_STATISTICS_update (GDS_stats,
5446 ("# Bytes received from other peers"), msize,
5449 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5450 is_predecessor = ntohl (trail_rejection->is_predecessor);
5451 congestion_timeout = trail_rejection->congestion_time;
5452 source = trail_rejection->source_peer;
5453 trail_id = trail_rejection->trail_id;
5454 ultimate_destination_finger_value =
5455 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5456 /* First set the congestion time of the friend that sent you this message. */
5457 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5458 if (NULL == target_friend)
5460 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5464 target_friend->congestion_timestamp =
5465 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5466 congestion_timeout);
5468 /* I am the source peer which wants to setup the trail. Do nothing.
5469 * send_find_finger_trail_task is scheduled periodically.*/
5470 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5473 /* If I am congested then pass this message to peer before me in trail. */
5474 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5476 /* First remove yourself from the trail. */
5477 unsigned int new_trail_length = trail_length - 1;
5478 struct GNUNET_PeerIdentity trail[new_trail_length];
5480 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5481 if (0 == trail_length)
5484 next_peer = trail[new_trail_length-1];
5487 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5488 if (NULL == target_friend)
5490 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5494 GDS_NEIGHBOURS_send_trail_rejection (source,
5495 ultimate_destination_finger_value,
5496 my_identity, is_predecessor,
5497 trail, new_trail_length, trail_id,
5498 target_friend, CONGESTION_TIMEOUT);
5502 struct Closest_Peer successor;
5503 successor = find_local_best_known_next_hop (ultimate_destination_finger_value, is_predecessor);
5505 /* Am I the final destination? */
5506 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5509 /*Here you are already part of trail. Copy the trail removing yourself. */
5510 unsigned int new_trail_length = trail_length - 1;
5511 struct GNUNET_PeerIdentity trail[new_trail_length];
5513 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5515 if (0 == new_trail_length)
5519 next_peer = trail[new_trail_length-1];
5522 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5524 if (NULL == target_friend)
5526 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5530 GDS_NEIGHBOURS_send_trail_setup_result (source,
5532 target_friend, new_trail_length,
5535 ultimate_destination_finger_value,
5540 /* Here I was already part of trail. So no need to add. */
5542 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5543 &successor.next_hop);
5544 if (NULL == target_friend)
5546 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5551 GDS_NEIGHBOURS_send_trail_setup (source,
5552 ultimate_destination_finger_value,
5553 successor.best_known_destination,
5554 target_friend, trail_length, trail_peer_list,
5555 is_predecessor, trail_id,
5556 successor.trail_id);
5563 * Core handler for trail teardown message.
5564 * @param cls closure
5565 * @param message message
5566 * @param peer sender of this messsage.
5567 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5570 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5571 const struct GNUNET_MessageHeader *message)
5573 const struct PeerTrailTearDownMessage *trail_teardown;
5574 enum GDS_ROUTING_trail_direction trail_direction;
5575 struct GNUNET_HashCode trail_id;
5576 struct GNUNET_PeerIdentity *next_hop;
5579 msize = ntohs (message->size);
5581 /* Here we pass only the trail id. */
5582 if (msize != sizeof (struct PeerTrailTearDownMessage))
5584 GNUNET_break_op (0);
5588 GNUNET_STATISTICS_update (GDS_stats,
5590 ("# Bytes received from other peers"), msize,
5593 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5594 trail_direction = ntohl (trail_teardown->trail_direction);
5595 trail_id = trail_teardown->trail_id;
5597 /* Check if peer is the real peer from which we should get this message.*/
5598 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5600 GNUNET_assert (NULL != (prev_hop =
5601 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5602 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5605 return GNUNET_SYSERR;
5609 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5610 if (NULL == next_hop)
5612 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
5613 GNUNET_i2s (&my_identity),
5614 GNUNET_h2s(&trail_id),
5617 return GNUNET_SYSERR;
5620 /* I am the next hop, which means I am the final destination. */
5621 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5623 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5628 /* If not final destination, then send a trail teardown message to next hop.*/
5629 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5630 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5631 GDS_NEIGHBOURS_send_trail_teardown (&trail_id, trail_direction, next_hop);
5639 * Core handle for p2p add trail message.
5640 * @param cls closure
5641 * @param message message
5642 * @param peer peer identity this notification is about
5643 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5646 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5647 const struct GNUNET_MessageHeader *message)
5649 const struct PeerAddTrailMessage *add_trail;
5650 const struct GNUNET_PeerIdentity *trail;
5651 struct GNUNET_HashCode trail_id;
5652 struct GNUNET_PeerIdentity destination_peer;
5653 struct GNUNET_PeerIdentity source_peer;
5654 struct GNUNET_PeerIdentity next_hop;
5655 unsigned int trail_length;
5656 unsigned int my_index;
5659 msize = ntohs (message->size);
5660 /* In this message we pass the whole trail from source to destination as we
5661 * are adding that trail.*/
5662 //FIXME: failed when run with 1000 pears. check why.
5663 if (msize < sizeof (struct PeerAddTrailMessage))
5665 GNUNET_break_op (0);
5669 add_trail = (const struct PeerAddTrailMessage *) message;
5670 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5671 sizeof (struct GNUNET_PeerIdentity);
5672 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5673 sizeof (struct GNUNET_PeerIdentity) != 0)
5675 GNUNET_break_op (0);
5679 GNUNET_STATISTICS_update (GDS_stats,
5681 ("# Bytes received from other peers"), msize,
5684 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5685 destination_peer = add_trail->destination_peer;
5686 source_peer = add_trail->source_peer;
5687 trail_id = add_trail->trail_id;
5689 /* I am not the destination of the trail. */
5690 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5692 struct FriendInfo *target_friend;
5694 /* Get my location in the trail. */
5695 my_index = search_my_index (trail, trail_length);
5698 GNUNET_break_op (0);
5699 return GNUNET_SYSERR;
5701 if((trail_length + 1) == my_index)
5703 DEBUG ("Found twice in trail.\n");
5704 GNUNET_break_op (0);
5705 return GNUNET_SYSERR;
5707 if ((trail_length - 1) == my_index)
5709 next_hop = destination_peer;
5713 next_hop = trail[my_index + 1];
5715 /* Add in your routing table. */
5716 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5717 //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5718 GNUNET_assert (NULL !=
5720 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5721 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5722 trail, trail_length, target_friend);
5725 /* I am the destination. Add an entry in routing table. */
5726 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5732 * Free the finger trail in which the first friend to reach to a finger is
5733 * disconnected_friend. Also remove entry from routing table for that particular
5735 * @param disconnected_friend PeerIdentity of friend which got disconnected
5736 * @param remove_finger Finger whose trail we need to check if it has
5737 * disconnected_friend as the first hop.
5738 * @return Total number of trails in which disconnected_friend was the first
5742 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5743 struct FingerInfo *finger)
5745 struct GNUNET_PeerIdentity *next_hop;
5746 struct FriendInfo *remove_friend;
5747 struct Trail *current_trail;
5748 unsigned int matching_trails_count = 0;
5751 /* Iterate over all the trails of finger. */
5752 for (i = 0; i < finger->trails_count; i++)
5754 current_trail = &finger->trail_list[i];
5755 if (GNUNET_NO == current_trail->is_present)
5758 /* First friend to reach to finger is disconnected_peer. */
5759 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5760 disconnected_friend))
5763 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5764 disconnected_friend);
5765 GNUNET_assert (NULL != remove_friend);
5766 next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id,
5767 GDS_ROUTING_SRC_TO_DEST);
5769 /* Here it may happen that as all the peers got disconnected, the entry in
5770 routing table for that particular trail has been removed, because the
5771 previously disconnected peer was either a next hop or prev hop of that
5773 if (NULL != next_hop)
5775 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5777 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id));
5779 matching_trails_count++;
5780 free_trail (current_trail);
5781 current_trail->is_present = GNUNET_NO;
5784 return matching_trails_count;
5789 * Iterate over finger_table entries.
5790 * 0. Ignore finger which is my_identity or if no valid entry present at
5791 * that finger index.
5792 * 1. If disconnected_friend is a finger, then remove the routing entry from
5793 your own table. Free the trail.
5794 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5795 * 2.1 Remove all the trails and entry from routing table in which disconnected
5796 * friend is the first friend in the trail. If disconnected_friend is the
5797 * first friend in all the trails to reach finger, then remove the finger.
5798 * @param disconnected_friend Peer identity of friend which got disconnected.
5801 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5803 struct FingerInfo *current_finger;
5804 int removed_trails_count;
5807 /* Iterate over finger table entries. */
5808 for (i = 0; i < MAX_FINGERS; i++)
5810 current_finger = &finger_table[i];
5812 /* No finger stored at this trail index or I am the finger. */
5813 if ((GNUNET_NO == current_finger->is_present) ||
5814 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5818 /* Is disconnected_peer a finger? */
5819 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5820 ¤t_finger->finger_identity))
5822 remove_existing_finger (current_finger, i);
5825 /* If finger is a friend but not disconnected_friend, then continue. */
5826 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5827 ¤t_finger->finger_identity))
5830 /* Iterate over the list of trails to reach remove_finger. Check if
5831 * disconnected_friend is the first friend in any of the trail. */
5832 removed_trails_count = remove_matching_trails (disconnected_peer,
5834 current_finger->trails_count =
5835 current_finger->trails_count - removed_trails_count;
5836 if (0 == current_finger->trails_count)
5838 current_finger->is_present = GNUNET_NO;
5839 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5846 * Method called whenever a peer disconnects.
5848 * @param cls closure
5849 * @param peer peer identity this notification is about
5852 handle_core_disconnect (void *cls,
5853 const struct GNUNET_PeerIdentity *peer)
5855 struct FriendInfo *remove_friend;
5856 struct P2PPendingMessage *pos;
5857 unsigned int discarded;
5859 /* If disconnected to own identity, then return. */
5860 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5863 if(NULL == (remove_friend =
5864 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
5866 DEBUG("\n friend already disconnected.");
5870 remove_matching_fingers (peer);
5871 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5872 GNUNET_assert (GNUNET_YES ==
5873 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5877 /* Remove all the messages queued in pending list of this peer is discarded.*/
5878 if (remove_friend->th != NULL)
5880 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
5881 remove_friend->th = NULL;
5885 while (NULL != (pos = remove_friend->head))
5887 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
5892 GNUNET_STATISTICS_update (GDS_stats,
5894 ("# Queued messages discarded (peer disconnected)"),
5895 discarded, GNUNET_NO);
5896 //GNUNET_free (remove_friend);
5898 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5901 if (NULL != find_finger_trail_task)
5903 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5904 find_finger_trail_task = NULL;
5912 * Method called whenever a peer connects.
5914 * @param cls closure
5915 * @param peer_identity peer identity this notification is about
5918 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5920 struct FriendInfo *friend;
5922 /* Check for connect to self message */
5923 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5926 /* If peer already exists in our friend_peermap, then exit. */
5927 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5934 friend = GNUNET_new (struct FriendInfo);
5935 friend->id = *peer_identity;
5937 GNUNET_assert (GNUNET_OK ==
5938 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5939 peer_identity, friend,
5940 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5942 /* FIXME: now we are not making a distinction between fingers which are friends
5943 * also.But later, we should add a congestion timestamp on the friend, so that it is
5944 * selected after some time out. This is to ensure that both peers have added
5945 * each other as their friend. */
5946 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5947 if (NULL == find_finger_trail_task)
5949 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5955 * To be called on core init/fail.
5957 * @param cls service closure
5958 * @param identity the public identity of this peer
5961 core_init (void *cls,
5962 const struct GNUNET_PeerIdentity *identity)
5964 my_identity = *identity;
5969 * Initialize finger table entries.
5972 finger_table_init ()
5974 memset (&finger_table, 0, sizeof (finger_table));
5979 * Initialize neighbours subsystem.
5980 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5983 GDS_NEIGHBOURS_init (void)
5985 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5986 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5987 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5988 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5989 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5990 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5991 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5992 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5993 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5994 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5995 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5996 sizeof (struct PeerTrailTearDownMessage)},
5997 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5998 {&handle_dht_p2p_notify_succ_confirmation, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION,
5999 sizeof (struct PeerNotifyConfirmationMessage)},
6004 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
6005 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
6006 GNUNET_NO, core_handlers);
6008 if (NULL == core_api)
6009 return GNUNET_SYSERR;
6011 //TODO: check size of this peer map?
6012 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
6013 finger_table_init ();
6014 successor_times = 10;
6015 fingers_round_count = 5;
6016 find_finger_trail_task_next_send_time.rel_value_us =
6017 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
6018 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6019 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
6021 verify_successor_next_send_time.rel_value_us =
6022 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
6023 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6024 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
6026 verify_successor_retry_time.rel_value_us =
6027 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6028 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6029 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6031 notify_successor_retry_time.rel_value_us =
6032 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6033 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6034 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6042 * Free the memory held up by trails of a finger.
6045 delete_finger_table_entries()
6050 for(i = 0; i < MAX_FINGERS; i++)
6052 if(GNUNET_YES == finger_table[i].is_present)
6054 for(j = 0; j < finger_table[i].trails_count; j++)
6055 free_trail(&finger_table[i].trail_list[j]);
6062 * Shutdown neighbours subsystem.
6065 GDS_NEIGHBOURS_done (void)
6067 if (NULL == core_api)
6070 GNUNET_CORE_disconnect (core_api);
6073 delete_finger_table_entries();
6074 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6075 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6076 friend_peermap = NULL;
6078 if (NULL != find_finger_trail_task)
6080 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6081 find_finger_trail_task = NULL;
6084 if (NULL != send_verify_successor_task)
6086 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6087 send_verify_successor_task = NULL;
6090 if (NULL != send_verify_successor_retry_task)
6092 struct VerifySuccessorContext *ctx;
6093 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
6095 send_verify_successor_retry_task = NULL;
6098 if (send_notify_new_successor_retry_task != NULL)
6100 struct SendNotifyContext *notify_ctx;
6101 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
6102 GNUNET_free (notify_ctx->successor_trail);
6103 GNUNET_free (notify_ctx);
6104 send_notify_new_successor_retry_task = NULL;
6112 * @return my identity
6114 struct GNUNET_PeerIdentity
6115 GDS_NEIGHBOURS_get_my_id (void)
6120 /* end of gnunet-service-xdht_neighbours.c */