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 * Should I be a malicious peer and drop the PUT/GET packets?
943 * if 0 then NOT malicious.
945 unsigned int act_malicious;
948 * Count of fingers found. Ideally we should have O(logn) fingers for a
951 static unsigned int total_fingers_found;
954 * Number of times we found the same successor.
956 static unsigned int successor_times;
959 * Number of rounds for which we should search for finger.
961 static unsigned int fingers_round_count;
963 * Called when core is ready to send a message we asked for
964 * out to the destination.
966 * @param cls the 'struct FriendInfo' of the target friend
967 * @param size number of bytes available in buf
968 * @param buf where the callee should write the message
969 * @return number of bytes written to buf
972 core_transmit_notify (void *cls, size_t size, void *buf)
974 struct FriendInfo *peer = cls;
976 struct P2PPendingMessage *pending;
981 while ( (NULL != (pending = peer->head)) &&
982 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us) )
984 GNUNET_STATISTICS_update (GDS_stats,
986 ("# Messages dropped (CORE timeout)"),
989 peer->pending_count--;
990 GNUNET_CONTAINER_DLL_remove (peer->head,
993 GNUNET_free (pending);
997 /* no messages pending */
1003 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1004 GNUNET_CORE_PRIO_BEST_EFFORT,
1005 GNUNET_TIME_absolute_get_remaining
1006 (pending->timeout), &peer->id,
1007 ntohs (pending->msg->size),
1008 &core_transmit_notify, peer);
1009 GNUNET_break (NULL != peer->th);
1013 while ((NULL != (pending = peer->head)) &&
1014 (size - off >= (msize = ntohs (pending->msg->size))))
1016 GNUNET_STATISTICS_update (GDS_stats,
1018 ("# Bytes transmitted to other peers"),
1021 memcpy (&cbuf[off], pending->msg, msize);
1023 peer->pending_count--;
1024 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1025 GNUNET_free (pending);
1027 if (peer->head != NULL)
1030 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1031 GNUNET_CORE_PRIO_BEST_EFFORT,
1032 GNUNET_TIME_absolute_get_remaining
1033 (pending->timeout), &peer->id, msize,
1034 &core_transmit_notify, peer);
1035 GNUNET_break (NULL != peer->th);
1042 * Transmit all messages in the friend's message queue.
1044 * @param peer message queue to process
1047 process_friend_queue (struct FriendInfo *peer)
1049 struct P2PPendingMessage *pending;
1051 if (NULL == (pending = peer->head))
1055 if (NULL != peer->th)
1061 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1062 pending->importance,
1063 GNUNET_TIME_absolute_get_remaining
1064 (pending->timeout), &peer->id,
1065 ntohs (pending->msg->size),
1066 &core_transmit_notify, peer);
1067 GNUNET_break (NULL != peer->th);
1071 #if ENABLE_MALICIOUS
1073 * Set the ENABLE_MALICIOUS value to malicious.
1077 GDS_NEIGHBOURS_act_malicious (unsigned int malicious)
1079 act_malicious = malicious;
1085 * Construct a trail setup message and forward it to target_friend
1086 * @param source_peer Peer which wants to setup the trail
1087 * @param ultimate_destination_finger_value Peer identity closest to this value
1088 * will be finger to @a source_peer
1089 * @param best_known_destination Best known destination (could be finger or friend)
1090 * which should get this message. In case it is
1091 * friend, then it is same as target_friend
1092 * @param target_friend Friend to which message is forwarded now.
1093 * @param trail_length Total number of peers in trail setup so far.
1094 * @param trail_peer_list Trail setup so far
1095 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1096 * @param trail_id Unique identifier for the trail we are trying to setup.
1097 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1098 * best_known_destination when its a finger. If not
1099 * used then set to 0.
1102 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1103 uint64_t ultimate_destination_finger_value,
1104 struct GNUNET_PeerIdentity best_known_destination,
1105 struct FriendInfo *target_friend,
1106 unsigned int trail_length,
1107 const struct GNUNET_PeerIdentity *trail_peer_list,
1108 unsigned int is_predecessor,
1109 struct GNUNET_HashCode trail_id,
1110 struct GNUNET_HashCode intermediate_trail_id)
1112 struct P2PPendingMessage *pending;
1113 struct PeerTrailSetupMessage *tsm;
1114 struct GNUNET_PeerIdentity *peer_list;
1117 msize = sizeof (struct PeerTrailSetupMessage) +
1118 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1120 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1126 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1128 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1131 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1132 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1133 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1134 pending->msg = &(tsm->header);
1135 tsm->header.size = htons (msize);
1136 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1137 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1138 tsm->source_peer = source_peer;
1139 tsm->best_known_destination = best_known_destination;
1140 tsm->is_predecessor = htonl (is_predecessor);
1141 tsm->trail_id = trail_id;
1142 tsm->intermediate_trail_id = intermediate_trail_id;
1144 if (trail_length > 0)
1146 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1147 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1150 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1151 target_friend->pending_count++;
1152 process_friend_queue (target_friend);
1157 * Construct a trail setup result message and forward it to target friend.
1158 * @param querying_peer Peer which sent the trail setup request and should get
1160 * @param Finger Peer to which the trail has been setup to.
1161 * @param target_friend Friend to which this message should be forwarded.
1162 * @param trail_length Numbers of peers in the trail.
1163 * @param trail_peer_list Peers which are part of the trail from
1164 * querying_peer to Finger, NOT including them.
1165 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1166 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1168 * @param trail_id Unique identifier of the trail.
1171 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1172 struct GNUNET_PeerIdentity finger,
1173 struct FriendInfo *target_friend,
1174 unsigned int trail_length,
1175 const struct GNUNET_PeerIdentity *trail_peer_list,
1176 unsigned int is_predecessor,
1177 uint64_t ultimate_destination_finger_value,
1178 struct GNUNET_HashCode trail_id)
1180 struct P2PPendingMessage *pending;
1181 struct PeerTrailSetupResultMessage *tsrm;
1182 struct GNUNET_PeerIdentity *peer_list;
1185 msize = sizeof (struct PeerTrailSetupResultMessage) +
1186 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1188 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1194 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1196 GNUNET_STATISTICS_update (GDS_stats,
1197 gettext_noop ("# P2P messages dropped due to full queue"),
1201 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1202 pending->importance = 0;
1203 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1204 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1205 pending->msg = &tsrm->header;
1206 tsrm->header.size = htons (msize);
1207 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1208 tsrm->querying_peer = querying_peer;
1209 tsrm->finger_identity = finger;
1210 tsrm->is_predecessor = htonl (is_predecessor);
1211 tsrm->trail_id = trail_id;
1212 tsrm->ulitmate_destination_finger_value =
1213 GNUNET_htonll (ultimate_destination_finger_value);
1214 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1215 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1217 /* Send the message to chosen friend. */
1218 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1219 target_friend->pending_count++;
1220 process_friend_queue (target_friend);
1224 * Send notify successor confirmation message.
1225 * @param trail_id Unique Identifier of the trail.
1226 * @param trail_direction Destination to Source.
1227 * @param target_friend Friend to get this message next.
1230 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (struct GNUNET_HashCode trail_id,
1231 unsigned int trail_direction,
1232 struct FriendInfo *target_friend)
1234 struct PeerNotifyConfirmationMessage *ncm;
1235 struct P2PPendingMessage *pending;
1238 msize = sizeof (struct PeerNotifyConfirmationMessage);
1239 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1245 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1247 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1251 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1252 pending->importance = 0; /* FIXME */
1253 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1254 ncm = (struct PeerNotifyConfirmationMessage *) &pending[1];
1255 pending->msg = &ncm->header;
1256 ncm->header.size = htons (msize);
1257 ncm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION);
1258 ncm->trail_id = trail_id;
1259 ncm->trail_direction = htonl (trail_direction);
1261 /* Send the message to chosen friend. */
1262 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1263 target_friend->pending_count++;
1264 process_friend_queue (target_friend);
1269 * Send trail rejection message to target friend
1270 * @param source_peer Peer which is trying to setup the trail.
1271 * @param ultimate_destination_finger_value Peer closest to this value will be
1272 * @a source_peer's finger
1273 * @param congested_peer Peer which sent this message as it is congested.
1274 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1275 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1276 * by congested_peer. This does NOT include @a source_peer
1277 * and congested_peer.
1278 * @param trail_length Total number of peers in trail_peer_list, NOT including
1279 * @a source_peer and @a congested_peer
1280 * @param trail_id Unique identifier of this trail.
1281 * @param congestion_timeout Duration given by congested peer as an estimate of
1282 * how long it may remain congested.
1285 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1286 uint64_t ultimate_destination_finger_value,
1287 struct GNUNET_PeerIdentity congested_peer,
1288 unsigned int is_predecessor,
1289 const struct GNUNET_PeerIdentity *trail_peer_list,
1290 unsigned int trail_length,
1291 struct GNUNET_HashCode trail_id,
1292 struct FriendInfo *target_friend,
1293 const struct GNUNET_TIME_Relative congestion_timeout)
1295 struct PeerTrailRejectionMessage *trm;
1296 struct P2PPendingMessage *pending;
1297 struct GNUNET_PeerIdentity *peer_list;
1300 msize = sizeof (struct PeerTrailRejectionMessage) +
1301 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1303 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1309 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1311 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1315 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1316 pending->importance = 0;
1317 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1318 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1319 pending->msg = &trm->header;
1320 trm->header.size = htons (msize);
1321 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1322 trm->source_peer = source_peer;
1323 trm->congested_peer = congested_peer;
1324 trm->congestion_time = congestion_timeout;
1325 trm->is_predecessor = htonl (is_predecessor);
1326 trm->trail_id = trail_id;
1327 trm->ultimate_destination_finger_value =
1328 GNUNET_htonll (ultimate_destination_finger_value);
1330 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1331 if (trail_length > 0)
1333 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1336 /* Send the message to chosen friend. */
1337 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1338 target_friend->pending_count++;
1339 process_friend_queue (target_friend);
1344 * Construct a verify successor message and forward it to target_friend.
1345 * @param source_peer Peer which wants to verify its successor.
1346 * @param successor Peer which is @a source_peer's current successor.
1347 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1348 * NOT including them.
1349 * @param trail List of peers which are part of trail to reach from @a source_peer
1350 * to @a successor, NOT including them.
1351 * @param trail_length Total number of peers in @a trail.
1352 * @param target_friend Next friend to get this message.
1355 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1356 struct GNUNET_PeerIdentity successor,
1357 struct GNUNET_HashCode trail_id,
1358 struct GNUNET_PeerIdentity *trail,
1359 unsigned int trail_length,
1360 struct FriendInfo *target_friend)
1362 struct PeerVerifySuccessorMessage *vsm;
1363 struct P2PPendingMessage *pending;
1364 struct GNUNET_PeerIdentity *peer_list;
1367 msize = sizeof (struct PeerVerifySuccessorMessage) +
1368 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1370 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1376 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1378 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1382 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1383 pending->importance = 0; /* FIXME */
1384 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1385 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1386 pending->msg = &vsm->header;
1387 vsm->header.size = htons (msize);
1388 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1389 vsm->source_peer = source_peer;
1390 vsm->successor = successor;
1391 vsm->trail_id = trail_id;
1392 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1393 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1395 /* Send the message to chosen friend. */
1396 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1397 target_friend->pending_count++;
1398 process_friend_queue (target_friend);
1403 * FIXME: In every function we pass target friend except for this one.
1404 * so, either change everything or this one. also, should se just store
1405 * the pointer to friend in routing table rather than gnunet_peeridentity.
1406 * if yes then we should keep friend info in.h andmake lot of changes.
1407 * Construct a trail teardown message and forward it to target friend.
1409 * @param trail_id Unique identifier of the trail.
1410 * @param trail_direction Direction of trail.
1411 * @param target_friend Friend to get this message.
1414 GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_HashCode *trail_id,
1415 unsigned int trail_direction,
1416 const struct GNUNET_PeerIdentity *peer)
1418 struct PeerTrailTearDownMessage *ttdm;
1419 struct P2PPendingMessage *pending;
1420 struct FriendInfo *target_friend;
1423 msize = sizeof (struct PeerTrailTearDownMessage);
1424 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1430 if (NULL == (target_friend =
1431 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
1433 /* FIXME: In what case friend can be null. ?*/
1438 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1440 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1444 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1445 pending->importance = 0; /* FIXME */
1446 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1447 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1448 pending->msg = &ttdm->header;
1449 ttdm->header.size = htons (msize);
1450 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1451 ttdm->trail_id = *trail_id;
1452 ttdm->trail_direction = htonl (trail_direction);
1454 /* Send the message to chosen friend. */
1455 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1456 target_friend->pending_count++;
1457 process_friend_queue (target_friend);
1462 * Construct a verify successor result message and send it to target_friend
1463 * @param querying_peer Peer which sent the verify successor message.
1464 * @param source_successor Current_successor of @a querying_peer.
1465 * @param current_predecessor Current predecessor of @a successor. Could be same
1466 * or different from @a querying_peer.
1467 * @param trail_id Unique identifier of the trail from @a querying_peer to
1468 * @a successor, NOT including them.
1469 * @param trail List of peers which are part of trail from @a querying_peer to
1470 * @a successor, NOT including them.
1471 * @param trail_length Total number of peers in @a trail
1472 * @param trail_direction Direction in which we are sending the message. In this
1473 * case we are sending result from @a successor to @a querying_peer.
1474 * @param target_friend Next friend to get this message.
1477 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1478 struct GNUNET_PeerIdentity current_successor,
1479 struct GNUNET_PeerIdentity probable_successor,
1480 struct GNUNET_HashCode trail_id,
1481 const struct GNUNET_PeerIdentity *trail,
1482 unsigned int trail_length,
1483 enum GDS_ROUTING_trail_direction trail_direction,
1484 struct FriendInfo *target_friend)
1486 struct PeerVerifySuccessorResultMessage *vsmr;
1487 struct P2PPendingMessage *pending;
1488 struct GNUNET_PeerIdentity *peer_list;
1491 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1492 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1494 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1500 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1502 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1506 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1507 pending->importance = 0; /* FIXME */
1508 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1509 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1510 pending->msg = &vsmr->header;
1511 vsmr->header.size = htons (msize);
1512 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1513 vsmr->querying_peer = querying_peer;
1514 vsmr->current_successor = current_successor;
1515 vsmr->probable_successor = probable_successor;
1516 vsmr->trail_direction = htonl (trail_direction);
1517 vsmr->trail_id = trail_id;
1518 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1519 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1521 /* Send the message to chosen friend. */
1522 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1523 target_friend->pending_count++;
1524 process_friend_queue (target_friend);
1529 * Construct a notify new successor message and send it to target_friend
1530 * @param source_peer Peer which wants to notify to its new successor that it
1531 * could be its predecessor.
1532 * @param successor New successor of @a source_peer
1533 * @param successor_trail List of peers in Trail to reach from
1534 * @a source_peer to @a new_successor, NOT including
1536 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1537 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1538 * @param target_friend Next friend to get this message.
1541 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1542 struct GNUNET_PeerIdentity successor,
1543 const struct GNUNET_PeerIdentity *successor_trail,
1544 unsigned int successor_trail_length,
1545 struct GNUNET_HashCode succesor_trail_id,
1546 struct FriendInfo *target_friend)
1548 struct PeerNotifyNewSuccessorMessage *nsm;
1549 struct P2PPendingMessage *pending;
1550 struct GNUNET_PeerIdentity *peer_list;
1553 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1554 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1556 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1562 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1564 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1568 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1569 pending->importance = 0; /* FIXME */
1570 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1571 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1572 pending->msg = &nsm->header;
1573 nsm->header.size = htons (msize);
1574 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1575 nsm->new_successor = successor;
1576 nsm->source_peer = source_peer;
1577 nsm->trail_id = succesor_trail_id;
1578 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1579 memcpy (peer_list, successor_trail,
1580 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1582 /* Send the message to chosen friend. */
1583 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1584 target_friend->pending_count++;
1585 process_friend_queue (target_friend);
1590 * Construct an add_trail message and send it to target_friend
1591 * @param source_peer Source of the trail.
1592 * @param destination_peer Destination of the trail.
1593 * @param trail_id Unique identifier of the trail from
1594 * @a source_peer to @a destination_peer, NOT including the endpoints.
1595 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1596 * NOT including the endpoints.
1597 * @param trail_length Total number of peers in @a trail.
1598 * @param target_friend Next friend to get this message.
1601 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1602 struct GNUNET_PeerIdentity destination_peer,
1603 struct GNUNET_HashCode trail_id,
1604 const struct GNUNET_PeerIdentity *trail,
1605 unsigned int trail_length,
1606 struct FriendInfo *target_friend)
1608 struct PeerAddTrailMessage *adm;
1609 struct GNUNET_PeerIdentity *peer_list;
1610 struct P2PPendingMessage *pending;
1613 msize = sizeof (struct PeerAddTrailMessage) +
1614 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1616 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1622 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1624 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1628 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1629 pending->importance = 0; /* FIXME */
1630 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1631 adm = (struct PeerAddTrailMessage *) &pending[1];
1632 pending->msg = &adm->header;
1633 adm->header.size = htons (msize);
1634 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1635 adm->source_peer = source_peer;
1636 adm->destination_peer = destination_peer;
1637 adm->trail_id = trail_id;
1638 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1639 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1641 /* Send the message to chosen friend. */
1642 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1643 target_friend->pending_count++;
1644 process_friend_queue (target_friend);
1650 * Search my location in trail. In case I am present more than once in the
1651 * trail (can happen during trail setup), then return my lowest index.
1652 * @param trail List of peers
1653 * @return my_index if found
1654 * trail_length + 1 if an entry is present twice, It is an error.
1655 * -1 if no entry found.
1658 search_my_index (const struct GNUNET_PeerIdentity *trail,
1662 int index_seen = trail_length + 1;
1665 for (i = 0; i < trail_length; i++)
1667 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1670 if(index_seen == (trail_length + 1))
1674 DEBUG("Entry is present twice in trail. Its not allowed\n");
1688 * Check if the friend is congested or have reached maximum number of trails
1689 * it can be part of of.
1690 * @param friend Friend to be checked.
1691 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1692 * #GNUNET_YES if friend is either congested or have crossed threshold
1695 is_friend_congested (struct FriendInfo *friend)
1697 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1698 ((0 == GNUNET_TIME_absolute_get_remaining
1699 (friend->congestion_timestamp).rel_value_us)))
1707 * Select closest finger to value.
1708 * @param peer1 First peer
1709 * @param peer2 Second peer
1710 * @param value Value to be compare
1711 * @return Closest peer
1713 static struct GNUNET_PeerIdentity
1714 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1715 const struct GNUNET_PeerIdentity *peer2,
1718 uint64_t peer1_value;
1719 uint64_t peer2_value;
1721 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1722 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1723 peer1_value = GNUNET_ntohll (peer1_value);
1724 peer2_value = GNUNET_ntohll (peer2_value);
1726 if (peer1_value == value)
1731 if (peer2_value == value)
1736 if (value < peer1_value && peer1_value < peer2_value)
1740 else if (value < peer2_value && peer2_value < peer1_value)
1744 else if (peer1_value < value && value < peer2_value)
1748 else if (peer2_value < value && value < peer1_value)
1752 else if (peer1_value < peer2_value && peer2_value < value)
1756 else // if (peer2_value < peer1_value && peer1_value < value)
1764 * Select closest predecessor to value.
1765 * @param peer1 First peer
1766 * @param peer2 Second peer
1767 * @param value Value to be compare
1768 * @return Peer which precedes value in the network.
1770 static struct GNUNET_PeerIdentity
1771 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1772 const struct GNUNET_PeerIdentity *peer2,
1775 uint64_t peer1_value;
1776 uint64_t peer2_value;
1778 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1779 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1780 peer1_value = GNUNET_ntohll (peer1_value);
1781 peer2_value = GNUNET_ntohll (peer2_value);
1783 if (peer1_value == value)
1788 if (peer2_value == value)
1793 if (value < peer1_value && peer1_value < peer2_value)
1797 else if (value < peer2_value && peer2_value < peer1_value)
1801 else if (peer1_value < value && value < peer2_value)
1805 else if (peer2_value < value && value < peer1_value)
1809 else if (peer1_value < peer2_value && peer2_value < value)
1813 else // if (peer2_value < peer1_value && peer1_value < value)
1825 test_print_trail (struct GNUNET_PeerIdentity *trail,
1826 unsigned int trail_length)
1828 struct GNUNET_PeerIdentity print_peer;
1831 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1832 __FILE__, __func__,__LINE__,trail_length);
1833 for (i =0 ; i< trail_length; i++)
1835 print_peer = trail[i];
1836 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1837 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1844 * This is a test function to print all the entries of friend table.
1847 test_friend_peermap_print ()
1849 struct FriendInfo *friend;
1850 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1851 struct GNUNET_PeerIdentity print_peer;
1852 struct GNUNET_PeerIdentity key_ret;
1855 print_peer = my_identity;
1856 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1857 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1859 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1861 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1863 (const void **)&friend))
1865 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1866 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1867 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1875 * This is a test function, to print all the entries of finger table.
1878 test_finger_table_print()
1880 struct FingerInfo *finger;
1881 struct GNUNET_PeerIdentity print_peer;
1882 //struct Trail *trail;
1886 print_peer = my_identity;
1887 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1888 for (i = 0; i < MAX_FINGERS; i++)
1890 finger = &finger_table[i];
1892 if (GNUNET_NO == finger->is_present)
1895 print_peer = finger->finger_identity;
1896 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1897 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1900 for (j = 0; j < finger->trails_count; j++)
1902 trail = &finger->trail_list[j];
1903 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1904 struct Trail_Element *element;
1905 element = trail->trail_head;
1906 for (k = 0; k < trail->trail_length; k++)
1908 print_peer = element->peer;
1909 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1910 element = element->next;
1919 * Select the closest peer among two peers (which should not be same)
1920 * with respect to value and finger_table_index
1921 * NOTE: peer1 != peer2
1922 * @param peer1 First peer
1923 * @param peer2 Second peer
1924 * @param value Value relative to which we find the closest
1925 * @param is_predecessor Is value a predecessor or any other finger.
1926 * @return Closest peer among two peers.
1928 static struct GNUNET_PeerIdentity
1929 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1930 const struct GNUNET_PeerIdentity *peer2,
1932 unsigned int is_predecessor)
1934 /* This check is here to ensure that calling function never sends
1935 same peer value in peer1 and peer2. Remove it later. */
1936 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1937 if (1 == is_predecessor)
1938 return select_closest_predecessor (peer1, peer2, value);
1940 // TODO: Change name to something like select_closest_successor!!
1941 return select_closest_finger (peer1, peer2, value);
1946 * Iterate over the list of all the trails of a finger. In case the first
1947 * friend to reach the finger has reached trail threshold or is congested,
1948 * then don't select it. In case there multiple available good trails to reach
1949 * to Finger, choose the one with shortest trail length.
1950 * Note: We use length as parameter. But we can use any other suitable parameter
1952 * @param finger Finger Finger whose trail we have to select.
1953 * @return Trail Selected Trail.
1955 static struct Trail *
1956 select_finger_trail (struct FingerInfo *finger)
1958 struct FriendInfo *friend;
1959 struct Trail *current_finger_trail;
1960 struct Trail *best_trail = NULL;
1963 GNUNET_assert (finger->trails_count > 0);
1964 for (i = 0; i < finger->trails_count; i++)
1966 current_finger_trail = &finger->trail_list[i];
1968 /* No trail stored at this index. */
1969 if (GNUNET_NO == current_finger_trail->is_present)
1972 GNUNET_assert (NULL !=
1974 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1975 ¤t_finger_trail->trail_head->peer)));
1977 /* First friend to reach trail is not free. */
1978 if (GNUNET_YES == is_friend_congested (friend))
1981 if (NULL == best_trail ||
1982 best_trail->trail_length > current_finger_trail->trail_length)
1984 best_trail = current_finger_trail;
1993 * Compare FINGER entry with current successor. If finger's first friend of all
1994 * its trail is not congested and has not crossed trail threshold, then check
1995 * if finger peer identity is closer to final_destination_finger_value than
1996 * current_successor. If yes then update current_successor.
1997 * @param current_successor[in/out]
2001 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
2003 struct FingerInfo *finger;
2004 struct GNUNET_PeerIdentity closest_peer;
2005 struct Trail *finger_trail;
2008 /* Iterate over finger table. */
2009 for (i = 0; i < MAX_FINGERS; i++)
2011 finger = &finger_table[i];
2013 if (GNUNET_NO == finger->is_present)
2016 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2017 ¤t_closest_peer->best_known_destination))
2020 /* If I am my own finger, then ignore this finger. */
2021 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2025 /* If finger is a friend, we have already checked it in previous function. */
2026 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2027 &finger->finger_identity)))
2032 closest_peer = select_closest_peer (&finger->finger_identity,
2033 ¤t_closest_peer->best_known_destination,
2034 current_closest_peer->destination_finger_value,
2035 current_closest_peer->is_predecessor);
2037 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer))
2039 /* Choose one of the trail to reach to finger. */
2040 finger_trail = select_finger_trail (finger);
2042 /* In case no trail found, ignore this finger. */
2043 if (NULL == finger_trail)
2046 current_closest_peer->best_known_destination = closest_peer;
2047 current_closest_peer->next_hop = finger_trail->trail_head->peer;
2048 current_closest_peer->trail_id = finger_trail->trail_id;
2049 current_closest_peer->finger_table_index = i;
2057 * Compare friend entry with current successor.
2058 * If friend identity and current_successor is same, then do nothing.
2059 * If friend is not congested and has not crossed trail threshold, then check
2060 * if friend peer identity is closer to final_destination_finger_value than
2061 * current_successor. If yes then update current_successor.
2062 * @param cls closure
2063 * @param key current public key
2064 * @param value struct Closest_Peer
2065 * @return #GNUNET_YES if we should continue to iterate,
2066 * #GNUNET_NO if not.
2069 compare_friend_and_current_closest_peer (void *cls,
2070 const struct GNUNET_PeerIdentity *key,
2073 struct FriendInfo *friend = value;
2074 struct Closest_Peer *current_closest_peer = cls;
2075 struct GNUNET_PeerIdentity closest_peer;
2077 /* Friend is either congested or has crossed threshold. */
2078 if (GNUNET_YES == is_friend_congested (friend))
2081 /* If current_closest_peer and friend identity are same, then do nothing.*/
2082 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2083 ¤t_closest_peer->best_known_destination))
2089 closest_peer = select_closest_peer (&friend->id,
2090 ¤t_closest_peer->best_known_destination,
2091 current_closest_peer->destination_finger_value,
2092 current_closest_peer->is_predecessor);
2094 /* Is friend the closest successor? */
2095 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer))
2097 current_closest_peer->best_known_destination = friend->id;
2098 current_closest_peer->next_hop = friend->id;
2106 * Initialize current_successor to my_identity.
2107 * @param my_identity My peer identity
2108 * @return Updated closest_peer
2110 static struct Closest_Peer
2111 init_closest_peer (struct GNUNET_PeerIdentity my_identity,
2112 uint64_t destination_finger_value,
2113 unsigned int is_predecessor)
2115 struct Closest_Peer current_closest_peer;
2117 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2118 current_closest_peer.destination_finger_value = destination_finger_value;
2119 current_closest_peer.is_predecessor = is_predecessor;
2120 current_closest_peer.next_hop = my_identity;
2121 current_closest_peer.best_known_destination = my_identity;
2122 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
2123 return current_closest_peer;
2128 * Find locally best known peer, among your own identity, friend and finger list,
2129 * which is closest to given destination_finger_value.
2131 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2133 * @param destination_finger_value Peer closest to this value will be the next destination.
2134 * @param is_predecessor Are we looking for predecessor or finger?
2135 * @return Closest_Peer that contains all the relevant field to reach to
2136 * @a destination_finger_value
2138 static struct Closest_Peer
2139 find_local_best_known_next_hop (uint64_t destination_finger_value,
2140 unsigned int is_predecessor)
2142 struct Closest_Peer current_closest_peer;
2144 /* Initialize current_successor to my_identity. */
2145 current_closest_peer = init_closest_peer (my_identity,
2146 destination_finger_value,
2149 /* Compare each friend entry with current_successor and update current_successor
2150 * with friend if its closest. */
2153 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2154 &compare_friend_and_current_closest_peer,
2155 ¤t_closest_peer));
2157 /* Compare each finger entry with current_successor and update current_successor
2158 * with finger if its closest. */
2159 compare_finger_and_current_closest_peer (¤t_closest_peer);
2160 return current_closest_peer;
2165 * Construct a Put message and send it to target_peer.
2166 * @param key Key for the content
2167 * @param block_type Type of the block
2168 * @param options Routing options
2169 * @param desired_replication_level Desired replication count
2170 * @param best_known_dest Peer to which this message should reach eventually,
2171 * as it is best known destination to me.
2172 * @param intermediate_trail_id Trail id in case
2173 * @param target_peer Peer to which this message will be forwarded.
2174 * @param hop_count Number of hops traversed so far.
2175 * @param put_path_length Total number of peers in @a put_path
2176 * @param put_path Number of peers traversed so far
2177 * @param expiration_time When does the content expire
2178 * @param data Content to store
2179 * @param data_size Size of content @a data in bytes
2182 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2183 enum GNUNET_BLOCK_Type block_type,
2184 enum GNUNET_DHT_RouteOption options,
2185 uint32_t desired_replication_level,
2186 struct GNUNET_PeerIdentity best_known_dest,
2187 struct GNUNET_HashCode intermediate_trail_id,
2188 struct GNUNET_PeerIdentity *target_peer,
2190 uint32_t put_path_length,
2191 struct GNUNET_PeerIdentity *put_path,
2192 struct GNUNET_TIME_Absolute expiration_time,
2193 const void *data, size_t data_size)
2195 struct PeerPutMessage *ppm;
2196 struct P2PPendingMessage *pending;
2197 struct FriendInfo *target_friend;
2198 struct GNUNET_PeerIdentity *pp;
2201 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2202 sizeof (struct PeerPutMessage);
2203 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2205 put_path_length = 0;
2206 msize = data_size + sizeof (struct PeerPutMessage);
2209 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2211 DEBUG("msize = %lu\n",msize);
2216 GNUNET_assert (NULL !=
2218 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2219 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2220 pending->timeout = expiration_time;
2221 ppm = (struct PeerPutMessage *) &pending[1];
2222 pending->msg = &ppm->header;
2223 ppm->header.size = htons (msize);
2224 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2225 ppm->options = htonl (options);
2226 ppm->block_type = htonl (block_type);
2227 ppm->hop_count = htonl (hop_count + 1);
2228 ppm->desired_replication_level = htonl (desired_replication_level);
2229 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2230 ppm->best_known_destination = best_known_dest;
2231 ppm->intermediate_trail_id = intermediate_trail_id;
2233 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2234 ppm->put_path_length = htonl (put_path_length);
2235 if(put_path_length > 0)
2237 memcpy (pp, put_path,
2238 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2240 memcpy (&pp[put_path_length], data, data_size);
2241 GNUNET_assert (NULL != target_friend);
2242 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2243 target_friend->pending_count++;
2244 process_friend_queue (target_friend);
2249 * Handle the put request from the client.
2250 * @param key Key for the content
2251 * @param block_type Type of the block
2252 * @param options Routing options
2253 * @param desired_replication_level Desired replication count
2254 * @param expiration_time When does the content expire
2255 * @param data Content to store
2256 * @param data_size Size of content @a data in bytes
2259 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
2260 enum GNUNET_BLOCK_Type block_type,
2261 enum GNUNET_DHT_RouteOption options,
2262 uint32_t desired_replication_level,
2263 struct GNUNET_TIME_Absolute expiration_time,
2264 const void *data, size_t data_size)
2266 struct GNUNET_PeerIdentity best_known_dest;
2267 struct GNUNET_HashCode intermediate_trail_id;
2268 struct GNUNET_PeerIdentity next_hop;
2270 struct Closest_Peer successor;
2272 memcpy (&key_value, key, sizeof (uint64_t));
2273 key_value = GNUNET_ntohll (key_value);
2274 successor = find_local_best_known_next_hop (key_value,
2275 GDS_FINGER_TYPE_NON_PREDECESSOR);
2276 best_known_dest = successor.best_known_destination;
2277 next_hop = successor.next_hop;
2278 intermediate_trail_id = successor.trail_id;
2280 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2282 DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",GNUNET_h2s(key));
2283 /* I am the destination. */
2284 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2285 block_type,data_size,data);
2286 GDS_CLIENTS_process_put (options, block_type, 0,
2287 ntohl (desired_replication_level),
2288 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time.
2289 key, data, data_size);
2292 /* In case we are sending the request to a finger, then send across all of its
2294 #if ENABLE_MALICIOUS
2295 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2296 &successor.next_hop))
2298 struct FingerInfo *next_hop_finger;
2301 next_hop_finger = &finger_table[successor.finger_table_index];
2302 for (i = 0; i < next_hop_finger->trails_count; i++)
2304 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2306 if(0 == next_hop_finger->trail_list[i].trail_length)
2308 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2309 best_known_dest, intermediate_trail_id, &next_hop,
2310 0, 1, &my_identity, expiration_time,
2314 next_hop = next_hop_finger->trail_list[i].trail_head->peer;
2315 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2317 next_hop_finger->trail_list[i].trail_id,
2318 &next_hop, 0, 1, &my_identity,
2326 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2327 best_known_dest, intermediate_trail_id, &next_hop,
2328 0, 1, &my_identity, expiration_time,
2333 * Construct a Get message and send it to target_peer.
2334 * @param key Key for the content
2335 * @param block_type Type of the block
2336 * @param options Routing options
2337 * @param desired_replication_level Desired replication count
2338 * @param best_known_dest Peer which should get this message. Same as target peer
2339 * if best_known_dest is a friend else its a finger.
2340 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2341 * in case it is a finger else set to 0.
2342 * @param target_peer Peer to which this message will be forwarded.
2343 * @param hop_count Number of hops traversed so far.
2344 * @param data Content to store
2345 * @param data_size Size of content @a data in bytes
2346 * @param get_path_length Total number of peers in @a get_path
2347 * @param get_path Number of peers traversed so far
2350 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2351 enum GNUNET_BLOCK_Type block_type,
2352 enum GNUNET_DHT_RouteOption options,
2353 uint32_t desired_replication_level,
2354 struct GNUNET_PeerIdentity best_known_dest,
2355 struct GNUNET_HashCode intermediate_trail_id,
2356 struct GNUNET_PeerIdentity *target_peer,
2358 uint32_t get_path_length,
2359 struct GNUNET_PeerIdentity *get_path)
2361 struct PeerGetMessage *pgm;
2362 struct P2PPendingMessage *pending;
2363 struct FriendInfo *target_friend;
2364 struct GNUNET_PeerIdentity *gp;
2367 msize = sizeof (struct PeerGetMessage) +
2368 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2370 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2375 GNUNET_assert (NULL !=
2377 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2379 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2380 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2381 pending->importance = 0; /* FIXME */
2382 pgm = (struct PeerGetMessage *) &pending[1];
2383 pending->msg = &pgm->header;
2384 pgm->header.size = htons (msize);
2385 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2386 pgm->get_path_length = htonl (get_path_length);
2387 pgm->best_known_destination = best_known_dest;
2389 pgm->intermediate_trail_id = intermediate_trail_id;
2390 pgm->hop_count = htonl (hop_count + 1);
2391 pgm->get_path_length = htonl (get_path_length);
2392 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2393 memcpy (gp, get_path,
2394 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2395 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2396 target_friend->pending_count++;
2397 process_friend_queue (target_friend);
2402 * Handle the get request from the client file. If I am destination do
2403 * datacache put and return. Else find the target friend and forward message
2405 * @param key Key for the content
2406 * @param block_type Type of the block
2407 * @param options Routing options
2408 * @param desired_replication_level Desired replication count
2411 GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key,
2412 enum GNUNET_BLOCK_Type block_type,
2413 enum GNUNET_DHT_RouteOption options,
2414 uint32_t desired_replication_level)
2416 struct Closest_Peer successor;
2417 struct GNUNET_PeerIdentity best_known_dest;
2418 struct GNUNET_HashCode intermediate_trail_id;
2421 memcpy (&key_value, key, sizeof (uint64_t));
2422 key_value = GNUNET_ntohll (key_value);
2424 successor = find_local_best_known_next_hop (key_value,
2425 GDS_FINGER_TYPE_NON_PREDECESSOR);
2427 best_known_dest = successor.best_known_destination;
2428 intermediate_trail_id = successor.trail_id;
2430 /* I am the destination. I have the data. */
2431 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2434 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2435 NULL, 0, 1, &my_identity, NULL,&my_identity);
2439 #if ENABLE_MALICIOUS
2440 struct GNUNET_PeerIdentity next_hop;
2441 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2442 &successor.next_hop))
2444 struct FingerInfo *next_hop_finger;
2447 next_hop_finger = &finger_table[successor.finger_table_index];
2448 for (i = 0; i < next_hop_finger->trails_count; i++)
2450 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2452 if(0 == next_hop_finger->trail_list[i].trail_length)
2454 GDS_NEIGHBOURS_send_get (key, block_type, options,
2455 desired_replication_level,
2456 best_known_dest,intermediate_trail_id,
2457 &successor.next_hop,
2458 0, 1, &my_identity);
2461 next_hop = next_hop_finger->trail_list[i].trail_head->peer;
2462 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2464 next_hop_finger->trail_list[i].trail_id,
2465 &next_hop, 0, 1, &my_identity);
2471 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2472 best_known_dest,intermediate_trail_id, &successor.next_hop,
2473 0, 1, &my_identity);
2478 * Send the get result to requesting client.
2480 * @param key Key of the requested data.
2481 * @param type Block type
2482 * @param target_peer Next peer to forward the message to.
2483 * @param source_peer Peer which has the data for the key.
2484 * @param put_path_length Number of peers in @a put_path
2485 * @param put_path Path taken to put the data at its stored location.
2486 * @param get_path_length Number of peers in @a get_path
2487 * @param get_path Path taken to reach to the location of the key.
2488 * @param expiration When will this result expire?
2489 * @param data Payload to store
2490 * @param data_size Size of the @a data
2493 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2494 enum GNUNET_BLOCK_Type type,
2495 const struct GNUNET_PeerIdentity *target_peer,
2496 const struct GNUNET_PeerIdentity *source_peer,
2497 unsigned int put_path_length,
2498 const struct GNUNET_PeerIdentity *put_path,
2499 unsigned int get_path_length,
2500 const struct GNUNET_PeerIdentity *get_path,
2501 struct GNUNET_TIME_Absolute expiration,
2502 const void *data, size_t data_size)
2504 struct PeerGetResultMessage *get_result;
2505 struct GNUNET_PeerIdentity *paths;
2506 struct P2PPendingMessage *pending;
2507 struct FriendInfo *target_friend;
2508 int current_path_index;
2511 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2513 sizeof (struct PeerGetResultMessage);
2515 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2517 put_path_length = 0;
2518 msize = msize - put_path_length * sizeof (struct GNUNET_PeerIdentity);
2521 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2526 current_path_index = 0;
2527 if(get_path_length > 0)
2529 current_path_index = search_my_index(get_path, get_path_length);
2530 if (-1 == current_path_index)
2535 if ((get_path_length + 1) == current_path_index)
2537 DEBUG ("Peer found twice in get path. Not allowed \n");
2542 if (0 == current_path_index)
2544 DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",GNUNET_h2s(key),GNUNET_i2s(&my_identity));
2545 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2546 get_path, put_path_length,
2547 put_path, type, data_size, data);
2551 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2552 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2553 pending->importance = 0;
2554 get_result = (struct PeerGetResultMessage *)&pending[1];
2555 pending->msg = &get_result->header;
2556 get_result->header.size = htons (msize);
2557 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2558 get_result->key = *key;
2559 get_result->querying_peer = *source_peer;
2560 get_result->expiration_time = GNUNET_TIME_absolute_hton (expiration);
2561 get_result->get_path_length = htonl (get_path_length);
2562 get_result->put_path_length = htonl (put_path_length);
2563 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2564 memcpy (paths, put_path,
2565 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2566 memcpy (&paths[put_path_length], get_path,
2567 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2568 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2570 GNUNET_assert (NULL !=
2572 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2573 &get_path[current_path_index - 1])));
2574 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2575 target_friend->pending_count++;
2576 process_friend_queue (target_friend);
2581 * Randomly choose one of your friends (which is not congested and have not crossed
2582 * trail threshold) from the friend_peermap
2583 * @return Friend Randomly chosen friend.
2584 * NULL in case friend peermap is empty, or all the friends are either
2585 * congested or have crossed trail threshold.
2587 static struct FriendInfo *
2588 select_random_friend ()
2590 unsigned int current_size;
2593 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2594 struct GNUNET_PeerIdentity key_ret;
2595 struct FriendInfo *friend;
2597 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2600 if (0 == current_size)
2603 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2604 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2606 /* Iterate till you don't reach to index. */
2607 for (j = 0; j < index ; j++)
2608 GNUNET_assert (GNUNET_YES ==
2609 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2613 /* Reset the index in friend peermap to 0 as we reached to the end. */
2614 if (j == current_size)
2617 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2618 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2622 /* Get the friend stored at the index, j*/
2623 GNUNET_assert (GNUNET_YES ==
2624 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2626 (const void **)&friend));
2628 /* This friend is not congested and has not crossed trail threshold. */
2629 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2630 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2636 } while (j != index);
2638 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2644 * Compute 64 bit value of finger_identity corresponding to a finger index using
2646 * For all fingers, n.finger[i] = n + pow (2,i),
2647 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2648 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2649 * @param finger_index Index corresponding to which we calculate 64 bit value.
2650 * @return 64 bit value.
2653 compute_finger_identity_value (unsigned int finger_index)
2657 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2658 my_id64 = GNUNET_ntohll (my_id64);
2660 /* Are we looking for immediate predecessor? */
2661 if (PREDECESSOR_FINGER_ID == finger_index)
2662 return (my_id64 - 1);
2665 uint64_t add = (uint64_t)1 << finger_index;
2666 return (my_id64 + add);
2672 * Choose a random friend. Calculate the next finger identity to search,from
2673 * current_search_finger_index. Start looking for the trail to reach to
2674 * finger identity through this random friend.
2676 * @param cls closure for this task
2677 * @param tc the context under which the task is running
2680 send_find_finger_trail_message (void *cls,
2681 const struct GNUNET_SCHEDULER_TaskContext *tc)
2683 struct FriendInfo *target_friend;
2684 struct GNUNET_HashCode trail_id;
2685 struct GNUNET_HashCode intermediate_trail_id;
2686 unsigned int is_predecessor = 0;
2687 uint64_t finger_id_value;
2689 /* Schedule another send_find_finger_trail_message task. After one round of
2690 * finger search, this time is exponentially backoff. */
2691 find_finger_trail_task_next_send_time.rel_value_us =
2692 find_finger_trail_task_next_send_time.rel_value_us +
2693 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2694 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2695 find_finger_trail_task =
2696 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2697 &send_find_finger_trail_message,
2700 /* No space in my routing table. (Source and destination peers also store entries
2701 * in their routing table). */
2702 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2705 target_friend = select_random_friend ();
2706 if (NULL == target_friend)
2711 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2712 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2715 /* Generate a unique trail id for trail we are trying to setup. */
2716 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2717 &trail_id, sizeof (trail_id));
2718 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2719 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2720 target_friend->id, target_friend, 0, NULL,
2721 is_predecessor, trail_id,
2722 intermediate_trail_id);
2727 * In case there are already maximum number of possible trails to reach to a
2728 * finger, then check if the new trail's length is lesser than any of the
2730 * If yes then replace that old trail by new trail.
2732 * Note: Here we are taking length as a parameter to choose the best possible
2733 * trail, but there could be other parameters also like:
2734 * 1. duration of existence of a trail - older the better.
2735 * 2. if the new trail is completely disjoint than the
2736 * other trails, then may be choosing it is better.
2738 * @param finger Finger
2739 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2740 * including the endpoints.
2741 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2742 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2745 select_and_replace_trail (struct FingerInfo *finger,
2746 const struct GNUNET_PeerIdentity *new_trail,
2747 unsigned int new_trail_length,
2748 struct GNUNET_HashCode new_trail_id)
2750 struct Trail *current_trail;
2751 unsigned int largest_trail_length;
2752 unsigned int largest_trail_index;
2753 struct Trail_Element *trail_element;
2754 struct GNUNET_PeerIdentity *next_hop;
2757 largest_trail_length = new_trail_length;
2758 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2760 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2762 for (i = 0; i < finger->trails_count; i++)
2764 current_trail = &finger->trail_list[i];
2765 GNUNET_assert (GNUNET_YES == current_trail->is_present);
2766 if (current_trail->trail_length > largest_trail_length)
2768 largest_trail_length = current_trail->trail_length;
2769 largest_trail_index = i;
2773 /* New trail is not better than existing ones. Send trail teardown. */
2774 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2776 next_hop = GDS_ROUTING_get_next_hop (new_trail_id, GDS_ROUTING_SRC_TO_DEST);
2777 GDS_ROUTING_remove_trail (new_trail_id);
2778 GDS_NEIGHBOURS_send_trail_teardown (&new_trail_id,
2779 GDS_ROUTING_SRC_TO_DEST,
2784 /* Send trail teardown message across the replaced trail. */
2785 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2786 next_hop = GDS_ROUTING_get_next_hop (replace_trail->trail_id, GDS_ROUTING_SRC_TO_DEST);
2787 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2788 GDS_NEIGHBOURS_send_trail_teardown (&replace_trail->trail_id,
2789 GDS_ROUTING_SRC_TO_DEST,
2792 /* Free the trail. */
2793 while (NULL != (trail_element = replace_trail->trail_head))
2795 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2796 replace_trail->trail_tail, trail_element);
2797 GNUNET_free_non_null (trail_element);
2800 /* Add new trial at that location. */
2801 replace_trail->is_present = GNUNET_YES;
2802 replace_trail->trail_length = new_trail_length;
2803 replace_trail->trail_id = new_trail_id;
2805 for (i = 0; i < new_trail_length; i++)
2807 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2808 element->peer = new_trail[i];
2810 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2811 replace_trail->trail_tail,
2814 /* FIXME: URGENT Are we adding the trail back to the list. */
2819 * Check if the new trail to reach to finger is unique or do we already have
2820 * such a trail present for finger.
2821 * @param existing_finger Finger identity
2822 * @param new_trail New trail to reach @a existing_finger
2823 * @param trail_length Total number of peers in new_trail.
2824 * @return #GNUNET_YES if the new trail is unique
2825 * #GNUNET_NO if same trail is already present.
2828 is_new_trail_unique (struct FingerInfo *existing_finger,
2829 const struct GNUNET_PeerIdentity *new_trail,
2830 unsigned int trail_length)
2832 struct Trail *current_trail;
2833 struct Trail_Element *trail_element;
2837 GNUNET_assert (existing_finger->trails_count > 0);
2839 /* Iterate over list of trails. */
2840 for (i = 0; i < existing_finger->trails_count; i++)
2842 current_trail = &(existing_finger->trail_list[i]);
2843 if(GNUNET_NO == current_trail->is_present)
2846 /* New trail and existing trail length are not same. */
2847 if (current_trail->trail_length != trail_length)
2852 trail_element = current_trail->trail_head;
2853 for (j = 0; j < current_trail->trail_length; j++)
2855 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2856 &trail_element->peer))
2860 trail_element = trail_element->next;
2867 * FIXME; In case of multiple trails, we may have a case where a trail from in
2868 * between has been removed, then we should try to find a free slot , not simply
2869 * add a trail at then end of the list.
2870 * Add a new trail at a free slot in trail array of existing finger.
2871 * @param existing_finger Finger
2872 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2873 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2874 * @param new_finger_trail_id Unique identifier of the trail.
2877 add_new_trail (struct FingerInfo *existing_finger,
2878 const struct GNUNET_PeerIdentity *new_trail,
2879 unsigned int new_trail_length,
2880 struct GNUNET_HashCode new_trail_id)
2882 struct FriendInfo *friend;
2883 struct Trail *trail;
2887 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2891 for (i = 0; i < existing_finger->trails_count; i++)
2893 if (GNUNET_NO == existing_finger->trail_list[i].is_present)
2900 if (-1 == free_slot)
2903 trail = &existing_finger->trail_list[free_slot];
2904 GNUNET_assert (GNUNET_NO == trail->is_present);
2905 trail->trail_id = new_trail_id;
2906 trail->trail_length = new_trail_length;
2907 existing_finger->trails_count++;
2908 trail->is_present = GNUNET_YES;
2909 if (0 == new_trail_length)
2911 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2912 &existing_finger->finger_identity);
2916 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2919 GNUNET_assert (NULL != friend);
2920 friend->trails_count++;
2921 for (i = 0; i < new_trail_length; i++)
2923 struct Trail_Element *element;
2925 element = GNUNET_new (struct Trail_Element);
2926 element->peer = new_trail[i];
2927 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2932 existing_finger->trail_list[free_slot].trail_head = trail->trail_head;
2933 existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail;
2934 existing_finger->trail_list[free_slot].trail_length = new_trail_length;
2935 existing_finger->trail_list[free_slot].trail_id = new_trail_id;
2936 existing_finger->trail_list[free_slot].is_present = GNUNET_YES;
2942 * FIXME; In case of multiple trails, we may have a case where a trail from in
2943 * between has been removed, then we should try to find a free slot , not simply
2944 * add a trail at then end of the list.
2945 * Add a new trail at a free slot in trail array of existing finger.
2946 * @param existing_finger Finger
2947 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2948 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2949 * @param new_finger_trail_id Unique identifier of the trail.
2952 add_new_trail (struct FingerInfo *existing_finger,
2953 const struct GNUNET_PeerIdentity *new_trail,
2954 unsigned int new_trail_length,
2955 struct GNUNET_HashCode new_trail_id)
2957 struct Trail *trail;
2958 struct FriendInfo *first_friend;
2962 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2966 index = existing_finger->trails_count;
2967 trail = &existing_finger->trail_list[index];
2968 GNUNET_assert (GNUNET_NO == trail->is_present);
2969 trail->trail_id = new_trail_id;
2970 trail->trail_length = new_trail_length;
2971 existing_finger->trails_count++;
2972 trail->is_present = GNUNET_YES;
2974 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2975 &existing_finger->finger_identity)));
2976 /* If finger is a friend then we never call this function. */
2977 GNUNET_assert (new_trail_length > 0);
2979 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2981 first_friend->trails_count++;
2983 for (i = 0; i < new_trail_length; i++)
2985 struct Trail_Element *element;
2987 element = GNUNET_new (struct Trail_Element);
2988 element->peer = new_trail[i];
2989 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2993 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2994 existing_finger->trail_list[index].trail_head = trail->trail_head;
2995 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2996 existing_finger->trail_list[index].trail_length = new_trail_length;
2997 existing_finger->trail_list[index].trail_id = new_trail_id;
2998 existing_finger->trail_list[index].is_present = GNUNET_YES;
3003 * Get the next hop to send trail teardown message from routing table and
3004 * then delete the entry from routing table. Send trail teardown message for a
3005 * specific trail of a finger.
3006 * @param finger Finger whose trail is to be removed.
3007 * @param trail List of peers in trail from me to a finger, NOT including
3011 send_trail_teardown (struct FingerInfo *finger,
3012 struct Trail *trail)
3014 struct FriendInfo *friend;
3015 struct GNUNET_PeerIdentity *next_hop;
3017 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
3018 GDS_ROUTING_SRC_TO_DEST);
3019 if (NULL == next_hop)
3021 // DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d",
3022 // GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length);
3025 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3028 GNUNET_assert(GNUNET_YES == trail->is_present);
3029 if (trail->trail_length > 0)
3031 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3032 &trail->trail_head->peer);
3036 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3037 &finger->finger_identity);
3042 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
3043 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
3046 if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)
3047 && (0 == trail->trail_length))
3049 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
3050 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
3053 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
3054 friend->trails_count--;
3055 GDS_NEIGHBOURS_send_trail_teardown (&trail->trail_id,
3056 GDS_ROUTING_SRC_TO_DEST,
3062 * Send trail teardown message across all the trails to reach to finger.
3063 * @param finger Finger whose all the trail should be freed.
3066 send_all_finger_trails_teardown (struct FingerInfo *finger)
3070 for (i = 0; i < finger->trails_count; i++)
3072 struct Trail *trail;
3074 trail = &finger->trail_list[i];
3075 if (GNUNET_YES == trail->is_present)
3077 send_trail_teardown (finger, trail);
3078 trail->is_present = GNUNET_NO;
3085 * Free a specific trail
3086 * @param trail List of peers to be freed.
3089 free_trail (struct Trail *trail)
3091 struct Trail_Element *trail_element;
3093 while (NULL != (trail_element = trail->trail_head))
3095 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
3098 GNUNET_free_non_null (trail_element);
3100 trail->trail_head = NULL;
3101 trail->trail_tail = NULL;
3106 * Free finger and its trail.
3107 * @param finger Finger to be freed.
3108 * @param finger_table_index Index at which finger is stored.
3111 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
3113 struct Trail *trail;
3115 for (i = 0; i < finger->trails_count; i++)
3117 trail = &finger->trail_list[i];
3118 if (GNUNET_NO == trail->is_present)
3121 if (trail->trail_length > 0)
3123 trail->is_present = GNUNET_NO;
3126 finger->is_present = GNUNET_NO;
3127 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
3132 * Add a new entry in finger table at finger_table_index.
3133 * In case I am my own finger, then we don't have a trail. In case of a friend,
3134 * we have a trail with unique id and '0' trail length.
3135 * In case a finger is a friend, then increment the trails count of the friend.
3136 * @param finger_identity Peer Identity of new finger
3137 * @param finger_trail Trail to reach from me to finger (excluding both end points).
3138 * @param finger_trail_length Total number of peers in @a finger_trail.
3139 * @param trail_id Unique identifier of the trail.
3140 * @param finger_table_index Index in finger table.
3143 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
3144 const struct GNUNET_PeerIdentity *finger_trail,
3145 unsigned int finger_trail_length,
3146 struct GNUNET_HashCode trail_id,
3147 unsigned int finger_table_index)
3149 struct FingerInfo *new_entry;
3150 struct FriendInfo *first_trail_hop;
3151 struct Trail *trail;
3154 new_entry = GNUNET_new (struct FingerInfo);
3155 new_entry->finger_identity = finger_identity;
3156 new_entry->finger_table_index = finger_table_index;
3157 new_entry->is_present = GNUNET_YES;
3159 /* If the new entry is my own identity. */
3160 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3163 new_entry->trails_count = 0;
3164 finger_table[finger_table_index] = *new_entry;
3165 GNUNET_free (new_entry);
3169 /* Finger is a friend. */
3170 if (0 == finger_trail_length)
3172 new_entry->trail_list[0].trail_id = trail_id;
3173 new_entry->trails_count = 1;
3174 new_entry->trail_list[0].is_present = GNUNET_YES;
3175 new_entry->trail_list[0].trail_length = 0;
3176 new_entry->trail_list[0].trail_head = NULL;
3177 new_entry->trail_list[0].trail_tail = NULL;
3178 finger_table[finger_table_index] = *new_entry;
3179 GNUNET_assert (NULL !=
3181 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3182 &finger_identity)));
3184 first_trail_hop->trails_count++;
3185 GNUNET_free (new_entry);
3189 GNUNET_assert (NULL !=
3191 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3192 &finger_trail[0])));
3193 new_entry->trails_count = 1;
3194 first_trail_hop->trails_count++;
3195 /* Copy the finger trail into trail. */
3196 trail = &new_entry->trail_list[0];
3197 for(i = 0; i < finger_trail_length; i++)
3199 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3201 element->next = NULL;
3202 element->prev = NULL;
3203 element->peer = finger_trail[i];
3204 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3209 /* Add trail to trail list. */
3210 trail->trail_length = finger_trail_length;
3211 trail->trail_id = trail_id;
3212 trail->is_present = GNUNET_YES;
3213 finger_table[finger_table_index] = *new_entry;
3214 GNUNET_free (new_entry);
3219 * Periodic task to verify current successor. There can be multiple trails to reach
3220 * to successor, choose the shortest one and send verify successor message
3221 * across that trail.
3222 * @param cls closure for this task
3223 * @param tc the context under which the task is running
3226 send_verify_successor_message (void *cls,
3227 const struct GNUNET_SCHEDULER_TaskContext *tc)
3229 struct FriendInfo *target_friend;
3230 struct GNUNET_HashCode trail_id;
3231 struct Trail *trail;
3232 struct Trail_Element *element;
3233 unsigned int trail_length;
3235 struct FingerInfo *successor;
3237 successor = &finger_table[0];
3239 /* This task will be scheduled when the result for Verify Successor is received. */
3240 send_verify_successor_task = NULL;
3242 /* When verify successor is being called for first time *for current context*
3243 * cls will be NULL. If send_verify_successor_retry_task is not NO_TASK, we
3244 * must cancel the retry task scheduled for verify_successor of previous
3249 /* FIXME: Here we are scheduling a new verify successor task, as we
3250 got a new successor. But a send verify successor task may be in progress.
3251 1. We need to be sure that this is indeed a new successor. As this function
3252 is called even if we add a new trail to reach t old successor.
3253 2. Assuming the new successor is different, then verify successor message
3254 * to old successor may be following stages.
3255 * --> Waiting for verify successor result. Don't wait anymore. there is
3256 * no trail to reach from old successor to me, hence, routing
3258 * --> Waiting for notify confirmation. again don't wait for it. notify
3259 * confirmation will not succeded.
3261 if (send_verify_successor_retry_task != NULL)
3263 /* FIXME: Are we scheduling retry task as soon as we send verify message.
3264 If yes then here before making this task, first check if the message
3265 is for the same peer again. */
3266 struct VerifySuccessorContext *old_ctx =
3267 GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
3268 /* old_ctx must not be NULL, as the retry task had been scheduled */
3269 GNUNET_assert(NULL != old_ctx);
3270 GNUNET_free(old_ctx);
3271 /* FIXME: Why don't we reset the task to NO_TASK here? */
3274 struct VerifySuccessorContext *ctx;
3275 ctx = GNUNET_new(struct VerifySuccessorContext);
3277 ctx->num_retries_scheduled++;
3278 send_verify_successor_retry_task =
3279 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3280 &send_verify_successor_message,
3285 /* This is a retry attempt for verify_successor for a previous context */
3286 struct VerifySuccessorContext *ctx;
3289 ctx->num_retries_scheduled++;
3290 send_verify_successor_retry_task =
3291 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3292 &send_verify_successor_message,
3296 /* Among all the trails to reach to successor, select first one which is present.*/
3297 for (i = 0; i < successor->trails_count; i++)
3299 trail = &successor->trail_list[i];
3300 if(GNUNET_YES == trail->is_present)
3304 /* No valid trail found to reach to successor. */
3305 if (i == successor->trails_count)
3308 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3309 &successor->finger_identity));
3310 /* Trail stored at this index. */
3311 GNUNET_assert (GNUNET_YES == trail->is_present);
3312 trail_id = trail->trail_id;
3313 if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST))
3315 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3316 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
3320 trail_length = trail->trail_length;
3321 if (trail_length > 0)
3323 /* Copy the trail into peer list. */
3324 struct GNUNET_PeerIdentity peer_list[trail_length];
3325 element = trail->trail_head;
3326 for(i = 0; i < trail_length; i++)
3328 peer_list[i] = element->peer;
3329 element = element->next;
3331 GNUNET_assert (NULL != (target_friend =
3332 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3334 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3335 successor->finger_identity,
3336 trail_id, peer_list, trail_length,
3341 GNUNET_assert (NULL != (target_friend =
3342 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3343 &successor->finger_identity)));
3344 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3345 successor->finger_identity,
3353 * FIXME: should this be a periodic task, incrementing the search finger index?
3354 * Update the current search finger index.
3355 * @a finger_identity
3356 * @a finger_table_index
3359 update_current_search_finger_index (unsigned int finger_table_index)
3361 struct FingerInfo *successor;
3363 /* FIXME correct this: only move current index periodically */
3364 if (finger_table_index != current_search_finger_index)
3367 successor = &finger_table[0];
3368 GNUNET_assert (GNUNET_YES == successor->is_present);
3370 /* We were looking for immediate successor. */
3371 if (0 == current_search_finger_index)
3373 current_search_finger_index = PREDECESSOR_FINGER_ID;
3374 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &successor->finger_identity))
3376 if (NULL == send_verify_successor_task)
3378 send_verify_successor_task =
3379 GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3385 current_search_finger_index = current_search_finger_index - 1;
3391 * Get the least significant bit set in val.
3394 * @return Position of first bit set, 65 in case of error.
3397 find_set_bit (uint64_t val)
3417 return 65; /* Some other bit was set to 1 as well. */
3424 * Calculate finger_table_index from initial 64 bit finger identity value that
3425 * we send in trail setup message.
3426 * @param ultimate_destination_finger_value Value that we calculated from our
3427 * identity and finger_table_index.
3428 * @param is_predecessor Is the entry for predecessor or not?
3429 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3430 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3433 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3434 unsigned int is_predecessor)
3438 unsigned int finger_table_index;
3440 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3441 my_id64 = GNUNET_ntohll (my_id64);
3443 /* Is this a predecessor finger? */
3444 if (1 == is_predecessor)
3446 diff = my_id64 - ultimate_destination_finger_value;
3448 finger_table_index = PREDECESSOR_FINGER_ID;
3450 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3455 diff = ultimate_destination_finger_value - my_id64;
3456 finger_table_index = find_set_bit (diff);
3458 return finger_table_index;
3463 * Remove finger and its associated data structures from finger table.
3464 * @param existing_finger Finger to be removed which is in finger table.
3465 * @param finger_table_index Index in finger table where @a existing_finger
3469 remove_existing_finger (struct FingerInfo *existing_finger,
3470 unsigned int finger_table_index)
3472 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3474 /* If I am my own finger, then we have no trails. */
3475 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3478 existing_finger->is_present = GNUNET_NO;
3479 memset ((void *)&finger_table[finger_table_index], 0,
3480 sizeof (finger_table[finger_table_index]));
3484 /* For all other fingers, send trail teardown across all the trails to reach
3485 finger, and free the finger. */
3486 send_all_finger_trails_teardown (existing_finger);
3487 free_finger (existing_finger, finger_table_index);
3492 * Check if there is already an entry in finger_table at finger_table_index.
3493 * We get the finger_table_index from 64bit finger value we got from the network.
3494 * -- If yes, then select the closest finger.
3495 * -- If new and existing finger are same, then check if you can store more
3497 * -- If yes then add trail, else keep the best trails to reach to the
3499 * -- If the new finger is closest, remove the existing entry, send trail
3500 * teardown message across all the trails to reach the existing entry.
3501 * Add the new finger.
3502 * -- If new and existing finger are different, and existing finger is closest
3504 * -- Update current_search_finger_index.
3505 * @param finger_identity Peer Identity of new finger
3506 * @param finger_trail Trail to reach the new finger
3507 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3508 * @param is_predecessor Is this entry for predecessor in finger_table?
3509 * @param finger_value 64 bit value of finger identity that we got from network.
3510 * @param finger_trail_id Unique identifier of @finger_trail.
3513 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3514 const struct GNUNET_PeerIdentity *finger_trail,
3515 unsigned int finger_trail_length,
3516 unsigned int is_predecessor,
3517 uint64_t finger_value,
3518 struct GNUNET_HashCode finger_trail_id)
3520 struct FingerInfo *existing_finger;
3521 struct GNUNET_PeerIdentity closest_peer;
3522 struct FingerInfo *successor;
3523 unsigned int finger_table_index;
3525 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3526 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3528 /* Invalid finger_table_index. */
3529 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3531 GNUNET_break_op (0);
3535 /* Check if new entry is same as successor. */
3536 if ((0 != finger_table_index) &&
3537 (PREDECESSOR_FINGER_ID != finger_table_index))
3539 successor = &finger_table[0];
3540 if (GNUNET_NO == successor->is_present)
3542 GNUNET_break (0); //ASSERTION FAILS HERE. FIXME
3545 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3546 &successor->finger_identity))
3548 if (0 == fingers_round_count)
3550 find_finger_trail_task_next_send_time =
3551 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3554 fingers_round_count--;
3555 current_search_finger_index = 0;
3556 GNUNET_STATISTICS_update (GDS_stats,
3558 ("# FINGERS_COUNT"), (int64_t) total_fingers_found,
3560 total_fingers_found = 0;
3564 struct FingerInfo prev_finger;
3565 prev_finger = finger_table[finger_table_index - 1];
3566 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3567 &prev_finger.finger_identity))
3569 current_search_finger_index--;
3574 total_fingers_found++;
3575 existing_finger = &finger_table[finger_table_index];
3577 /* No entry present in finger_table for given finger map index. */
3578 if (GNUNET_NO == existing_finger->is_present)
3580 /* Shorten the trail if possible. */
3581 add_new_finger (finger_identity, finger_trail,
3582 finger_trail_length,
3583 finger_trail_id, finger_table_index);
3584 update_current_search_finger_index (finger_table_index);
3588 /* If existing entry and finger identity are not same. */
3589 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3592 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3597 /* If the new finger is the closest peer. */
3598 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer))
3600 remove_existing_finger (existing_finger, finger_table_index);
3601 add_new_finger (finger_identity, finger_trail, finger_trail_length,
3602 finger_trail_id, finger_table_index);
3606 /* Existing finger is the closest one. We need to send trail teardown
3607 across the trail setup in routing table of all the peers. */
3608 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3610 if (finger_trail_length > 0)
3611 GDS_NEIGHBOURS_send_trail_teardown (&finger_trail_id,
3612 GDS_ROUTING_SRC_TO_DEST,
3615 GDS_NEIGHBOURS_send_trail_teardown (&finger_trail_id,
3616 GDS_ROUTING_SRC_TO_DEST,
3623 /* If both new and existing entry are same as my_identity, then do nothing. */
3624 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3630 /* If there is space to store more trails. */
3631 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3632 add_new_trail (existing_finger, finger_trail,
3633 finger_trail_length, finger_trail_id);
3635 select_and_replace_trail (existing_finger, finger_trail,
3636 finger_trail_length, finger_trail_id);
3638 update_current_search_finger_index (finger_table_index);
3644 * Core handler for P2P put messages.
3645 * @param cls closure
3646 * @param peer sender of the request
3647 * @param message message
3648 * @return #GNUNET_OK to keep the connection open,
3649 * #GNUNET_SYSERR to close it (signal serious error)
3652 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3653 const struct GNUNET_MessageHeader *message)
3655 struct PeerPutMessage *put;
3656 struct GNUNET_PeerIdentity *put_path;
3657 struct GNUNET_PeerIdentity current_best_known_dest;
3658 struct GNUNET_PeerIdentity best_known_dest;
3659 struct GNUNET_HashCode received_intermediate_trail_id;
3660 struct GNUNET_HashCode intermediate_trail_id;
3661 struct GNUNET_PeerIdentity next_hop;
3662 struct GNUNET_PeerIdentity *next_routing_hop;
3663 enum GNUNET_DHT_RouteOption options;
3664 struct GNUNET_HashCode test_key;
3669 size_t payload_size;
3672 msize = ntohs (message->size);
3673 if (msize < sizeof (struct PeerPutMessage))
3675 GNUNET_break_op (0);
3679 put = (struct PeerPutMessage *) message;
3680 putlen = ntohl (put->put_path_length);
3682 sizeof (struct PeerPutMessage) +
3683 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3685 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3687 GNUNET_break_op (0);
3690 #if ENABLE_MALICIOUS
3691 if(1 == act_malicious)
3693 DEBUG("\n I AM MALICIOUS PUT_REQUEST_DROPPED for key = %ss",GNUNET_h2s(&put->key));
3697 GNUNET_STATISTICS_update (GDS_stats,
3699 ("# Bytes received from other peers"), (int64_t) msize,
3702 current_best_known_dest = put->best_known_destination;
3703 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3704 payload = &put_path[putlen];
3705 options = ntohl (put->options);
3706 received_intermediate_trail_id = put->intermediate_trail_id;
3707 hop_count = ntohl(put->hop_count);
3708 payload_size = msize - (sizeof (struct PeerPutMessage) +
3709 putlen * sizeof (struct GNUNET_PeerIdentity));
3711 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3712 payload, payload_size, &test_key))
3715 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3717 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3718 GNUNET_break_op (0);
3719 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3720 "PUT with key `%s' for block with key %s\n",
3721 put_s, GNUNET_h2s_full (&test_key));
3722 GNUNET_free (put_s);
3727 GNUNET_break_op (0);
3730 /* cannot verify, good luck */
3734 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3736 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3737 ntohl (put->block_type),
3738 GNUNET_BLOCK_EO_NONE,
3740 NULL, 0, /* bloom filer */
3741 NULL, 0, /* xquery */
3742 payload, payload_size))
3744 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3745 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3748 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3749 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3750 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3751 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3752 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3753 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3755 GNUNET_break_op (0);
3760 /* Check if you are already a part of put path. */
3762 for (i = 0; i < putlen; i++)
3764 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3771 /* Add yourself to the list. */
3772 struct GNUNET_PeerIdentity pp[putlen + 1];
3773 //if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3776 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3777 pp[putlen] = my_identity;
3783 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3784 struct Closest_Peer successor;
3785 key_value = GNUNET_ntohll (key_value);
3786 successor = find_local_best_known_next_hop (key_value,
3787 GDS_FINGER_TYPE_NON_PREDECESSOR);
3788 next_hop = successor.next_hop;
3789 intermediate_trail_id = successor.trail_id;
3790 best_known_dest = successor.best_known_destination;
3792 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3794 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3795 GDS_ROUTING_SRC_TO_DEST);
3796 if (NULL != next_routing_hop)
3798 next_hop = *next_routing_hop;
3799 intermediate_trail_id = received_intermediate_trail_id;
3800 best_known_dest = current_best_known_dest;
3804 GDS_CLIENTS_process_put (options,
3805 ntohl (put->block_type),
3807 ntohl (put->desired_replication_level),
3809 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3814 /* I am the final destination */
3815 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3817 DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",GNUNET_h2s(&put->key));
3818 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3819 &(put->key),putlen, pp, ntohl (put->block_type),
3820 payload_size, payload);
3824 #if ENABLE_MALICIOUS
3825 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
3826 &successor.next_hop))
3828 struct FingerInfo *next_hop_finger;
3831 next_hop_finger = &finger_table[successor.finger_table_index];
3832 for (i = 0; i < next_hop_finger->trails_count; i++)
3834 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
3836 if(0 == next_hop_finger->trail_list[i].trail_length)
3838 GDS_NEIGHBOURS_send_put (&put->key,
3839 ntohl (put->block_type),ntohl (put->options),
3840 ntohl (put->desired_replication_level),
3841 best_known_dest, intermediate_trail_id, &next_hop,
3842 hop_count, putlen, pp,
3843 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3844 payload, payload_size);
3847 next_hop = next_hop_finger->trail_list[i].trail_head->peer;
3848 GDS_NEIGHBOURS_send_put (&put->key,
3849 ntohl (put->block_type),ntohl (put->options),
3850 ntohl (put->desired_replication_level),
3852 next_hop_finger->trail_list[i].trail_id,
3853 &next_hop, hop_count, putlen, pp,
3854 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3855 payload, payload_size);
3861 GDS_NEIGHBOURS_send_put (&put->key,
3862 ntohl (put->block_type),ntohl (put->options),
3863 ntohl (put->desired_replication_level),
3864 best_known_dest, intermediate_trail_id, &next_hop,
3865 hop_count, putlen, pp,
3866 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3867 payload, payload_size);
3874 * FIXME: Check for loop in the request. If you already are part of get path,
3875 * then you need to reset the get path length.
3876 * Core handler for p2p get requests.
3878 * @param cls closure
3879 * @param peer sender of the request
3880 * @param message message
3881 * @return #GNUNET_OK to keep the connection open,
3882 * #GNUNET_SYSERR to close it (signal serious error)
3885 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3886 const struct GNUNET_MessageHeader *message)
3888 const struct PeerGetMessage *get;
3889 const struct GNUNET_PeerIdentity *get_path;
3890 struct GNUNET_PeerIdentity best_known_dest;
3891 struct GNUNET_PeerIdentity current_best_known_dest;
3892 struct GNUNET_HashCode intermediate_trail_id;
3893 struct GNUNET_HashCode received_intermediate_trail_id;
3894 struct Closest_Peer successor;
3895 struct GNUNET_PeerIdentity next_hop;
3896 struct GNUNET_PeerIdentity *next_routing_hop;
3897 uint32_t get_length;
3902 msize = ntohs (message->size);
3903 if (msize < sizeof (struct PeerGetMessage))
3905 GNUNET_break_op (0);
3909 get = (const struct PeerGetMessage *)message;
3910 get_length = ntohl (get->get_path_length);
3912 sizeof (struct PeerGetMessage) +
3913 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3915 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3917 GNUNET_break_op (0);
3921 #if ENABLE_MALICIOUS
3922 if(1 == act_malicious)
3924 DEBUG("I am malicious,GET_REQUEST_DROPPED for key = %s. \n",GNUNET_h2s(&get->key));
3928 current_best_known_dest = get->best_known_destination;
3929 received_intermediate_trail_id = get->intermediate_trail_id;
3930 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3931 hop_count = get->hop_count;
3935 GNUNET_STATISTICS_update (GDS_stats,
3937 ("# Bytes received from other peers"), msize,
3940 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3941 key_value = GNUNET_ntohll (key_value);
3943 /* Check if you are already a part of get path. */
3945 for (i = 0; i < get_length; i++)
3947 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &get_path[i]))
3954 /* Add yourself in the get path. */
3955 struct GNUNET_PeerIdentity gp[get_length + 1];
3956 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3957 gp[get_length] = my_identity;
3958 get_length = get_length + 1;
3959 GDS_CLIENTS_process_get (get->options, get->block_type, hop_count,
3960 get->desired_replication_level, get->get_path_length,
3964 successor = find_local_best_known_next_hop (key_value,
3965 GDS_FINGER_TYPE_NON_PREDECESSOR);
3966 next_hop = successor.next_hop;
3967 best_known_dest = successor.best_known_destination;
3968 intermediate_trail_id = successor.trail_id;
3969 /* I am not the final destination. I am part of trail to reach final dest. */
3970 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3972 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3973 GDS_ROUTING_SRC_TO_DEST);
3974 if (NULL != next_routing_hop)
3976 next_hop = *next_routing_hop;
3977 best_known_dest = current_best_known_dest;
3978 intermediate_trail_id = received_intermediate_trail_id;
3982 /* I am the final destination. */
3983 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3985 if (1 == get_length)
3987 DEBUG("\n GET_REQUEST DONE for key = %s",GNUNET_h2s(&get->key));
3988 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0,
3989 NULL, 0, 1, &my_identity, NULL,&my_identity);
3993 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3994 get_length, gp, &gp[get_length - 2],
4001 #if ENABLE_MALICIOUS
4002 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
4003 &successor.next_hop))
4005 struct FingerInfo *next_hop_finger;
4008 next_hop_finger = &finger_table[successor.finger_table_index];
4009 for (i = 0; i < next_hop_finger->trails_count; i++)
4011 if(0 == next_hop_finger->trail_list[i].trail_length)
4013 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
4014 get->desired_replication_level, best_known_dest,
4015 intermediate_trail_id, &next_hop, hop_count,
4019 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
4021 next_hop = next_hop_finger->trail_list[i].trail_head->peer;
4022 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
4023 get->desired_replication_level, best_known_dest,
4024 next_hop_finger->trail_list[i].trail_id,
4025 &next_hop, hop_count,
4032 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
4033 get->desired_replication_level, best_known_dest,
4034 intermediate_trail_id, &next_hop, hop_count,
4042 * Core handler for get result
4043 * @param cls closure
4044 * @param peer sender of the request
4045 * @param message message
4046 * @return #GNUNET_OK to keep the connection open,
4047 * #GNUNET_SYSERR to close it (signal serious error)
4050 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
4051 const struct GNUNET_MessageHeader *message)
4053 const struct PeerGetResultMessage *get_result;
4054 const struct GNUNET_PeerIdentity *get_path;
4055 const struct GNUNET_PeerIdentity *put_path;
4056 const void *payload;
4057 size_t payload_size;
4059 unsigned int getlen;
4060 unsigned int putlen;
4061 int current_path_index;
4063 msize = ntohs (message->size);
4064 if (msize < sizeof (struct PeerGetResultMessage))
4066 GNUNET_break_op (0);
4070 get_result = (const struct PeerGetResultMessage *)message;
4071 getlen = ntohl (get_result->get_path_length);
4072 putlen = ntohl (get_result->put_path_length);
4075 sizeof (struct PeerGetResultMessage) +
4076 getlen * sizeof (struct GNUNET_PeerIdentity) +
4077 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
4079 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
4081 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
4083 GNUNET_break_op (0);
4086 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
4087 GNUNET_STATISTICS_update (GDS_stats,
4089 ("# Bytes received from other peers"), msize,
4092 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
4093 get_path = &put_path[putlen];
4094 payload = (const void *) &get_path[getlen];
4095 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
4096 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
4098 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
4100 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
4102 getlen, get_path, putlen,
4103 put_path, get_result->type, payload_size, payload);
4108 current_path_index = search_my_index (get_path, getlen);
4109 if (-1 == current_path_index )
4111 DEBUG ("No entry found in get path.\n");
4113 return GNUNET_SYSERR;
4115 if((getlen + 1) == current_path_index)
4117 DEBUG("Present twice in get path. Not allowed. \n");
4119 return GNUNET_SYSERR;
4121 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
4122 &get_path[current_path_index - 1],
4123 &(get_result->querying_peer), putlen, put_path,
4125 GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
4126 payload, payload_size);
4129 return GNUNET_SYSERR;
4134 * Find the next hop to pass trail setup message. First find the local best known
4135 * hop from your own identity, friends and finger. If you were part of trail,
4136 * then get the next hop from routing table. Compare next_hop from routing table
4137 * and local best known hop, and return the closest one to final_dest_finger_val
4138 * @param final_dest_finger_val 64 bit value of finger identity
4139 * @param intermediate_trail_id If you are part of trail to reach to some other
4140 * finger, then it is the trail id to reach to
4141 * that finger, else set to 0.
4142 * @param is_predecessor Are we looking for closest successor or predecessor.
4143 * @param source Source of trail setup message.
4144 * @param current_dest In case you are part of trail, then finger to which
4145 * we should forward the message. Else my own identity
4146 * @return Closest Peer for @a final_dest_finger_val
4148 static struct Closest_Peer
4149 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
4150 struct GNUNET_HashCode intermediate_trail_id,
4151 unsigned int is_predecessor,
4152 struct GNUNET_PeerIdentity source,
4153 struct GNUNET_PeerIdentity *current_dest)
4155 struct Closest_Peer peer;
4157 peer = find_local_best_known_next_hop (final_dest_finger_val, is_predecessor);
4159 /* Am I just a part of a trail towards a finger (current_destination)? */
4160 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
4161 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
4164 struct GNUNET_PeerIdentity closest_peer;
4166 /* Select best successor among one found locally and current_destination
4167 * that we got from network.*/
4168 closest_peer = select_closest_peer (&peer.best_known_destination,
4170 final_dest_finger_val,
4173 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
4174 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
4176 struct GNUNET_PeerIdentity *next_hop;
4178 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4179 GDS_ROUTING_SRC_TO_DEST);
4180 /* next_hop NULL is a valid case. This intermediate trail id is set by
4181 some other finger, and while this trail setup is in progress, that other
4182 peer might have found a better trail ,and send trail teardown message
4183 across the network. In case we got the trail teardown message first,
4184 then next_hop will be NULL. A possible solution could be to keep track
4185 * of all removed trail id, and be sure that there is no other reason . */
4186 if(NULL != next_hop)
4188 peer.next_hop = *next_hop;
4189 peer.best_known_destination = *current_dest;
4190 peer.trail_id = intermediate_trail_id;
4199 * Core handle for PeerTrailSetupMessage.
4200 * @param cls closure
4201 * @param message message
4202 * @param peer peer identity this notification is about
4203 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4206 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
4207 const struct GNUNET_MessageHeader *message)
4209 const struct PeerTrailSetupMessage *trail_setup;
4210 const struct GNUNET_PeerIdentity *trail_peer_list;
4211 struct GNUNET_PeerIdentity current_dest;
4212 struct FriendInfo *target_friend;
4213 struct GNUNET_PeerIdentity source;
4214 struct GNUNET_HashCode intermediate_trail_id;
4215 struct GNUNET_HashCode trail_id;
4216 unsigned int is_predecessor;
4217 uint32_t trail_length;
4218 uint64_t final_dest_finger_val;
4222 msize = ntohs (message->size);
4223 if (msize < sizeof (struct PeerTrailSetupMessage))
4225 GNUNET_break_op (0);
4226 return GNUNET_SYSERR;
4229 trail_setup = (const struct PeerTrailSetupMessage *) message;
4230 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4231 sizeof (struct GNUNET_PeerIdentity) != 0)
4233 GNUNET_break_op (0);
4236 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4237 sizeof (struct GNUNET_PeerIdentity);
4239 GNUNET_STATISTICS_update (GDS_stats,
4241 ("# Bytes received from other peers"), msize,
4244 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4245 current_dest = trail_setup->best_known_destination;
4246 trail_id = trail_setup->trail_id;
4247 final_dest_finger_val =
4248 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4249 source = trail_setup->source_peer;
4250 is_predecessor = ntohl (trail_setup->is_predecessor);
4251 intermediate_trail_id = trail_setup->intermediate_trail_id;
4253 /* Did the friend insert its ID in the trail list? */
4254 if (trail_length > 0 &&
4255 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
4257 GNUNET_break_op (0);
4258 return GNUNET_SYSERR;
4261 /* If I was the source and got the message back, then set trail length to 0.*/
4262 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4267 /* Check if you are present in the trail seen so far? */
4268 for (i = 0; i < trail_length ; i++)
4270 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4272 /* We will add ourself later in code, if NOT destination. */
4278 /* Is my routing table full? */
4279 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4281 if (trail_length > 0)
4283 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4284 &trail_peer_list[trail_length - 1]);
4287 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4289 if(NULL == target_friend)
4291 DEBUG ("\n friend not found");
4295 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4296 my_identity, is_predecessor,
4297 trail_peer_list, trail_length,
4298 trail_id, target_friend,
4299 CONGESTION_TIMEOUT);
4303 /* Get the next hop to forward the trail setup request. */
4304 struct Closest_Peer next_peer =
4305 get_local_best_known_next_hop (final_dest_finger_val,
4306 intermediate_trail_id,
4311 /* Am I the final destination? */
4312 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4315 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4317 finger_table_add (my_identity, NULL, 0, is_predecessor,
4318 final_dest_finger_val, trail_id);
4322 if (trail_length > 0)
4324 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4325 &trail_peer_list[trail_length-1]);
4328 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4329 if (NULL == target_friend)
4331 GNUNET_break_op (0);
4332 return GNUNET_SYSERR;
4334 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4335 GDS_NEIGHBOURS_send_trail_setup_result (source,
4337 target_friend, trail_length,
4340 final_dest_finger_val,trail_id);
4342 else /* I'm not the final destination. */
4344 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4345 &next_peer.next_hop);
4346 if(NULL == target_friend)
4348 DEBUG ("\n target friend not found for peer = %s", GNUNET_i2s(&next_peer.next_hop));
4352 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4354 /* Add yourself to list of peers. */
4355 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4357 memcpy (peer_list, trail_peer_list,
4358 trail_length * sizeof (struct GNUNET_PeerIdentity));
4359 peer_list[trail_length] = my_identity;
4360 GDS_NEIGHBOURS_send_trail_setup (source,
4361 final_dest_finger_val,
4362 next_peer.best_known_destination,
4363 target_friend, trail_length + 1, peer_list,
4364 is_predecessor, trail_id,
4365 next_peer.trail_id);
4368 GDS_NEIGHBOURS_send_trail_setup (source,
4369 final_dest_finger_val,
4370 next_peer.best_known_destination,
4371 target_friend, 0, NULL,
4372 is_predecessor, trail_id,
4373 next_peer.trail_id);
4380 * Core handle for p2p trail setup result messages.
4382 * @param message message
4383 * @param peer sender of this message.
4384 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4387 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4388 const struct GNUNET_MessageHeader *message)
4390 const struct PeerTrailSetupResultMessage *trail_result;
4391 const struct GNUNET_PeerIdentity *trail_peer_list;
4392 struct GNUNET_PeerIdentity next_hop;
4393 struct FriendInfo *target_friend;
4394 struct GNUNET_PeerIdentity querying_peer;
4395 struct GNUNET_PeerIdentity finger_identity;
4396 uint32_t trail_length;
4397 uint64_t ulitmate_destination_finger_value;
4398 uint32_t is_predecessor;
4399 struct GNUNET_HashCode trail_id;
4403 msize = ntohs (message->size);
4404 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4406 GNUNET_break_op (0);
4410 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4411 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4412 sizeof (struct GNUNET_PeerIdentity) != 0)
4414 GNUNET_break_op (0);
4417 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4418 sizeof (struct GNUNET_PeerIdentity);
4420 GNUNET_STATISTICS_update (GDS_stats,
4422 ("# Bytes received from other peers"), msize,
4425 is_predecessor = ntohl (trail_result->is_predecessor);
4426 querying_peer = trail_result->querying_peer;
4427 finger_identity = trail_result->finger_identity;
4428 trail_id = trail_result->trail_id;
4429 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4430 ulitmate_destination_finger_value =
4431 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4433 /* Am I the one who initiated the query? */
4434 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4436 /* Check that you got the message from the correct peer. */
4437 if (trail_length > 0)
4439 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4444 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4447 GDS_ROUTING_add (trail_id, my_identity, *peer);
4448 finger_table_add (finger_identity, trail_peer_list, trail_length,
4449 is_predecessor, ulitmate_destination_finger_value, trail_id);
4453 /* Get my location in the trail. */
4454 my_index = search_my_index (trail_peer_list, trail_length);
4457 DEBUG ("Not found in trail\n");
4459 return GNUNET_SYSERR;
4462 if ((trail_length + 1) == my_index)
4464 DEBUG ("Found twice in trail.\n");
4466 return GNUNET_SYSERR;
4469 //TODO; Refactor code here and above to check if sender peer is correct
4472 if(trail_length > 1)
4473 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4476 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4478 next_hop = trail_result->querying_peer;
4482 if(my_index == trail_length - 1)
4485 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4490 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4492 next_hop = trail_peer_list[my_index - 1];
4495 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4496 if (NULL == target_friend)
4498 GNUNET_break_op (0);
4499 return GNUNET_SYSERR;
4501 GDS_ROUTING_add (trail_id, next_hop, *peer);
4502 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4503 target_friend, trail_length, trail_peer_list,
4505 ulitmate_destination_finger_value,
4513 * @param trail Trail to be inverted
4514 * @param trail_length Total number of peers in the trail.
4515 * @return Updated trail
4517 static struct GNUNET_PeerIdentity *
4518 invert_trail (const struct GNUNET_PeerIdentity *trail,
4519 unsigned int trail_length)
4523 struct GNUNET_PeerIdentity *inverted_trail;
4525 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4528 j = trail_length - 1;
4529 while (i < trail_length)
4531 inverted_trail[i] = trail[j];
4536 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4537 &inverted_trail[0]));
4538 return inverted_trail;
4543 * Return the shortest trail among all the trails to reach to finger from me.
4544 * @param finger Finger
4545 * @param shortest_trail_length[out] Trail length of shortest trail from me
4547 * @return Shortest trail.
4549 static struct GNUNET_PeerIdentity *
4550 get_shortest_trail (struct FingerInfo *finger,
4551 unsigned int *trail_length)
4553 struct Trail *trail;
4554 unsigned int flag = 0;
4555 unsigned int shortest_trail_index = 0;
4556 int shortest_trail_length = -1;
4557 struct Trail_Element *trail_element;
4558 struct GNUNET_PeerIdentity *trail_list;
4561 /* Get the shortest trail to reach to current successor. */
4562 for (i = 0; i < finger->trails_count; i++)
4564 trail = &finger->trail_list[i];
4568 shortest_trail_index = i;
4569 shortest_trail_length = trail->trail_length;
4574 if (shortest_trail_length > trail->trail_length)
4576 shortest_trail_index = i;
4577 shortest_trail_length = trail->trail_length;
4582 /* Copy the shortest trail and return. */
4583 trail = &finger->trail_list[shortest_trail_index];
4584 trail_element = trail->trail_head;
4586 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4587 shortest_trail_length);
4589 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4591 trail_list[i] = trail_element->peer;
4594 GNUNET_assert(shortest_trail_length != -1);
4596 *trail_length = shortest_trail_length;
4602 * Check if trail_1 and trail_2 have any common element. If yes then join
4603 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4604 * @param trail_1 Trail from source to me, NOT including endpoints.
4605 * @param trail_1_len Total number of peers @a trail_1
4606 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4607 * @param trail_2_len Total number of peers @a trail_2
4608 * @param joined_trail_len Total number of peers in combined trail of trail_1
4610 * @return Joined trail.
4612 static struct GNUNET_PeerIdentity *
4613 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4614 unsigned int trail_1_len,
4615 struct GNUNET_PeerIdentity *trail_2,
4616 unsigned int trail_2_len,
4617 unsigned int *joined_trail_len)
4619 struct GNUNET_PeerIdentity *joined_trail;
4624 for (i = 0; i < trail_1_len; i++)
4626 for (j = 0; j < trail_2_len; j++)
4628 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4631 *joined_trail_len = i + (trail_2_len - j);
4632 joined_trail = GNUNET_malloc (*joined_trail_len *
4633 sizeof(struct GNUNET_PeerIdentity));
4636 /* Copy all the elements from 0 to i into joined_trail. */
4637 for(k = 0; k < ( i+1); k++)
4639 joined_trail[k] = trail_1[k];
4642 /* Increment j as entry stored is same as entry stored at i*/
4645 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4646 while(k <= (*joined_trail_len - 1))
4648 joined_trail[k] = trail_2[j];
4653 return joined_trail;
4657 /* Here you should join the trails. */
4658 *joined_trail_len = trail_1_len + trail_2_len + 1;
4659 joined_trail = GNUNET_malloc (*joined_trail_len *
4660 sizeof(struct GNUNET_PeerIdentity));
4663 for(i = 0; i < trail_1_len;i++)
4665 joined_trail[i] = trail_1[i];
4668 joined_trail[i] = my_identity;
4671 for (j = 0; i < *joined_trail_len; i++,j++)
4673 joined_trail[i] = trail_2[j];
4676 return joined_trail;
4681 * Return the trail from source to my current predecessor. Check if source
4682 * is already part of the this trail, if yes then return the shorten trail.
4683 * @param current_trail Trail from source to me, NOT including the endpoints.
4684 * @param current_trail_length Number of peers in @a current_trail.
4685 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4686 * source to my predecessor, NOT including
4688 * @return Trail from source to my predecessor.
4690 static struct GNUNET_PeerIdentity *
4691 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4692 const struct GNUNET_PeerIdentity *trail_src_to_me,
4693 unsigned int trail_src_to_me_len,
4694 unsigned int *trail_src_to_curr_pred_length)
4696 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4697 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4698 unsigned int trail_me_to_curr_pred_length;
4699 struct FingerInfo *current_predecessor;
4704 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4706 /* Check if trail_src_to_me contains current_predecessor. */
4707 for (i = 0; i < trail_src_to_me_len; i++)
4709 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4710 ¤t_predecessor->finger_identity))
4714 *trail_src_to_curr_pred_length = i;
4719 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4720 sizeof(struct GNUNET_PeerIdentity));
4721 for (j = 0; j < i; j++)
4722 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4723 return trail_src_to_curr_pred;
4727 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4728 &trail_me_to_curr_pred_length);
4730 /* Check if trail contains the source_peer. */
4731 for (i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4733 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4734 &trail_me_to_curr_pred[i]))
4737 /* Source is NOT part of trail. */
4740 /* Source is the last element in the trail to reach to my pred.
4741 Source is direct friend of the pred. */
4742 if (trail_me_to_curr_pred_length == i)
4744 *trail_src_to_curr_pred_length = 0;
4745 GNUNET_free_non_null (trail_me_to_curr_pred);
4749 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4750 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4751 *trail_src_to_curr_pred_length);
4753 for (j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4754 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4755 GNUNET_free_non_null (trail_me_to_curr_pred);
4756 return trail_src_to_curr_pred;
4759 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4760 trail_src_to_me_len,
4761 trail_me_to_curr_pred,
4762 trail_me_to_curr_pred_length,
4764 *trail_src_to_curr_pred_length = len;
4765 GNUNET_free_non_null(trail_me_to_curr_pred);
4766 return trail_src_to_curr_pred;
4771 * Add finger as your predecessor. To add, first generate a new trail id, invert
4772 * the trail to get the trail from me to finger, add an entry in your routing
4773 * table, send add trail message to peers which are part of trail from me to
4774 * finger and add finger in finger table.
4777 * @param trail_length
4780 update_predecessor (struct GNUNET_PeerIdentity finger,
4781 struct GNUNET_PeerIdentity *trail,
4782 unsigned int trail_length)
4784 struct GNUNET_HashCode trail_to_new_predecessor_id;
4785 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4786 struct FriendInfo *target_friend;
4788 /* Generate trail id for trail from me to new predecessor = finger. */
4789 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4790 &trail_to_new_predecessor_id,
4791 sizeof (trail_to_new_predecessor_id));
4793 if (0 == trail_length)
4795 trail_to_new_predecessor = NULL;
4796 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4797 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger);
4798 if (NULL == target_friend)
4806 /* Invert the trail to get the trail from me to finger, NOT including the
4808 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4809 &trail[trail_length-1]));
4810 trail_to_new_predecessor = invert_trail (trail, trail_length);
4812 /* Add an entry in your routing table. */
4813 GDS_ROUTING_add (trail_to_new_predecessor_id,
4815 trail_to_new_predecessor[0]);
4817 GNUNET_assert (NULL != (target_friend =
4818 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4819 &trail_to_new_predecessor[0])));
4822 /* Add entry in routing table of all peers that are part of trail from me
4823 to finger, including finger. */
4824 GDS_NEIGHBOURS_send_add_trail (my_identity,
4826 trail_to_new_predecessor_id,
4827 trail_to_new_predecessor,
4831 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4832 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4833 GNUNET_free_non_null(trail_to_new_predecessor);
4838 * Check if you already have a predecessor. If not then add finger as your
4839 * predecessor. If you have predecessor, then compare two peer identites.
4840 * If finger is correct predecessor, then remove the old entry, add finger in
4841 * finger table and send add_trail message to add the trail in the routing
4842 * table of all peers which are part of trail to reach from me to finger.
4843 * @param finger New peer which may be our predecessor.
4844 * @param trail List of peers to reach from @finger to me.
4845 * @param trail_length Total number of peer in @a trail.
4848 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4849 struct GNUNET_PeerIdentity *trail,
4850 unsigned int trail_length)
4852 struct FingerInfo *current_predecessor;
4853 struct GNUNET_PeerIdentity closest_peer;
4854 uint64_t predecessor_value;
4855 unsigned int is_predecessor = 1;
4857 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4858 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4860 /* No predecessor. Add finger as your predecessor. */
4861 if (GNUNET_NO == current_predecessor->is_present)
4863 update_predecessor (finger, trail, trail_length);
4867 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4873 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4874 closest_peer = select_closest_peer (&finger,
4875 ¤t_predecessor->finger_identity,
4876 predecessor_value, is_predecessor);
4878 /* Finger is the closest predecessor. Remove the existing one and add the new
4880 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4882 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4883 update_predecessor (finger, trail, trail_length);
4891 * Core handle for p2p verify successor messages.
4892 * @param cls closure
4893 * @param message message
4894 * @param peer peer identity this notification is about
4895 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4898 handle_dht_p2p_verify_successor(void *cls,
4899 const struct GNUNET_PeerIdentity *peer,
4900 const struct GNUNET_MessageHeader *message)
4902 const struct PeerVerifySuccessorMessage *vsm;
4903 struct GNUNET_HashCode trail_id;
4904 struct GNUNET_PeerIdentity successor;
4905 struct GNUNET_PeerIdentity source_peer;
4906 struct GNUNET_PeerIdentity *trail;
4907 struct GNUNET_PeerIdentity *next_hop;
4908 struct FingerInfo current_predecessor;
4909 struct FriendInfo *target_friend;
4910 unsigned int trail_src_to_curr_pred_len = 0;
4911 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4912 unsigned int trail_length;
4915 msize = ntohs (message->size);
4917 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4919 GNUNET_break_op (0);
4923 vsm = (const struct PeerVerifySuccessorMessage *) message;
4924 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4925 sizeof (struct GNUNET_PeerIdentity);
4926 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4927 sizeof (struct GNUNET_PeerIdentity) != 0)
4929 GNUNET_break_op (0);
4933 GNUNET_STATISTICS_update (GDS_stats,
4935 ("# Bytes received from other peers"), msize,
4938 trail_id = vsm->trail_id;
4939 source_peer = vsm->source_peer;
4940 successor = vsm->successor;
4941 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4943 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4945 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4947 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4948 if (NULL == next_hop)
4953 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4955 if(NULL == target_friend)
4960 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4961 trail_id, trail, trail_length,
4966 /* I am the destination of this message. */
4968 /* Check if the source_peer could be our predecessor and if yes then update
4970 compare_and_update_predecessor (source_peer, trail, trail_length);
4971 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4973 /* Is source of this message NOT my predecessor. */
4974 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4977 trail_src_to_curr_pred =
4978 get_trail_src_to_curr_pred (source_peer,
4981 &trail_src_to_curr_pred_len);
4985 trail_src_to_curr_pred_len = trail_length;
4988 trail_src_to_curr_pred =
4989 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4990 *trail_src_to_curr_pred_len);
4991 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4993 trail_src_to_curr_pred[i] = trail[i];
4997 GNUNET_assert (NULL !=
4999 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5000 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
5001 current_predecessor.finger_identity,
5002 trail_id, trail_src_to_curr_pred,
5003 trail_src_to_curr_pred_len,
5004 GDS_ROUTING_DEST_TO_SRC,
5006 GNUNET_free_non_null(trail_src_to_curr_pred);
5012 * If the trail from me to my probable successor contains a friend not
5013 * at index 0, then we can shorten the trail.
5014 * @param probable_successor Peer which is our probable successor
5015 * @param trail_me_to_probable_successor Peers in path from me to my probable
5016 * successor, NOT including the endpoints.
5017 * @param trail_me_to_probable_successor_len Total number of peers in
5018 * @a trail_me_to_probable_succesor.
5019 * @return Updated trail, if any friend found.
5020 * Else the trail_me_to_probable_successor.
5022 struct GNUNET_PeerIdentity *
5023 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
5024 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
5025 unsigned int trail_me_to_probable_successor_len,
5026 unsigned int *trail_to_new_successor_length)
5030 struct GNUNET_PeerIdentity *trail_to_new_successor;
5032 /* Probable successor is a friend */
5033 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5034 &probable_successor))
5036 trail_to_new_successor = NULL;
5037 *trail_to_new_successor_length = 0;
5038 return trail_to_new_successor;
5041 /* Is there any friend of yours in this trail. */
5042 if(trail_me_to_probable_successor_len > 1)
5044 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
5046 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5047 &trail_me_to_probable_successor[i]))
5050 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
5051 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
5052 *trail_to_new_successor_length);
5055 for(j = 0; j < *trail_to_new_successor_length; i++,j++)
5057 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
5060 return trail_to_new_successor;
5064 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
5065 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
5069 struct SendNotifyContext
5071 struct GNUNET_PeerIdentity source_peer;
5072 struct GNUNET_PeerIdentity successor;
5073 struct GNUNET_PeerIdentity *successor_trail;
5074 unsigned int successor_trail_length;
5075 struct GNUNET_HashCode succesor_trail_id;
5076 struct FriendInfo *target_friend;
5077 unsigned int num_retries_scheduled;
5081 send_notify_new_successor (void *cls,
5082 const struct GNUNET_SCHEDULER_TaskContext
5086 * Check if the peer which sent us verify successor result message is still ours
5087 * successor or not. If not, then compare existing successor and probable successor.
5088 * In case probable successor is the correct successor, remove the existing
5089 * successor. Add probable successor as new successor. Send notify new successor
5090 * message to new successor.
5091 * @param curr_succ Peer to which we sent the verify successor message. It may
5092 * or may not be our real current successor, as we may have few iterations of
5093 * find finger trail task.
5094 * @param probable_successor Peer which should be our successor accroding to @a
5096 * @param trail List of peers to reach from me to @a probable successor, NOT including
5098 * @param trail_length Total number of peers in @a trail.
5101 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
5102 struct GNUNET_PeerIdentity probable_successor,
5103 const struct GNUNET_PeerIdentity *trail,
5104 unsigned int trail_length)
5106 struct FingerInfo *current_successor;
5107 struct GNUNET_PeerIdentity closest_peer;
5108 struct GNUNET_HashCode trail_id;
5109 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
5110 struct FriendInfo *target_friend;
5111 unsigned int trail_me_to_probable_succ_len;
5112 unsigned int is_predecessor = 0;
5113 uint64_t successor_value;
5115 current_successor = &finger_table[0];
5116 successor_value = compute_finger_identity_value(0);
5118 /* If probable successor is same as current_successor, do nothing. */
5119 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
5120 ¤t_successor->finger_identity))
5122 if ((NULL != GDS_stats))
5128 memcpy (&my_id, &my_identity, sizeof(uint64_t));
5129 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5130 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5131 succ = GNUNET_ntohll(succ);
5132 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5133 GNUNET_free (my_id_str);
5135 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5138 if (send_verify_successor_task == NULL)
5139 send_verify_successor_task =
5140 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5141 &send_verify_successor_message,
5145 closest_peer = select_closest_peer (&probable_successor,
5146 ¤t_successor->finger_identity,
5147 successor_value, is_predecessor);
5149 /* If the current_successor in the finger table is closest, then do nothing. */
5150 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
5151 ¤t_successor->finger_identity))
5153 //FIXME: Is this a good place to return the stats.
5154 if ((NULL != GDS_stats))
5160 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5161 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5162 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5163 GNUNET_free (my_id_str);
5164 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5168 if(0 == successor_times)
5170 // successor_times = 3;
5171 verify_successor_next_send_time =
5172 GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time);
5178 if (send_verify_successor_task == NULL)
5179 send_verify_successor_task =
5180 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5181 &send_verify_successor_message,
5186 /* Probable successor is the closest peer.*/
5187 if(trail_length > 0)
5189 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5194 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5195 &probable_successor));
5198 trail_me_to_probable_succ_len = 0;
5199 trail_me_to_probable_succ =
5200 check_trail_me_to_probable_succ (probable_successor,
5201 trail, trail_length,
5202 &trail_me_to_probable_succ_len);
5204 /* Remove the existing successor. */
5205 remove_existing_finger (current_successor, 0);
5206 /* Generate a new trail id to reach to your new successor. */
5207 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5208 &trail_id, sizeof (trail_id));
5210 if (trail_me_to_probable_succ_len > 0)
5212 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
5213 GNUNET_assert (NULL !=
5215 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5216 &trail_me_to_probable_succ[0])));
5220 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5221 GNUNET_assert (NULL !=
5223 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5224 &probable_successor)));
5227 add_new_finger (probable_successor, trail_me_to_probable_succ,
5228 trail_me_to_probable_succ_len, trail_id, 0);
5230 struct SendNotifyContext *notify_ctx;
5232 notify_ctx = GNUNET_new(struct SendNotifyContext);
5234 notify_ctx->source_peer = my_identity;
5235 notify_ctx->successor = probable_successor;
5236 notify_ctx->successor_trail =
5237 GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5238 memcpy(notify_ctx->successor_trail, trail_me_to_probable_succ,
5239 sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5240 notify_ctx->successor_trail_length = trail_me_to_probable_succ_len;
5241 notify_ctx->succesor_trail_id = trail_id;
5242 notify_ctx->target_friend = target_friend;
5243 notify_ctx->num_retries_scheduled = 0;
5244 GNUNET_free_non_null (trail_me_to_probable_succ);
5246 // TODO: Check if we should verify before schedule if already scheduled.
5247 GNUNET_SCHEDULER_add_now(&send_notify_new_successor, (void*)notify_ctx);
5253 send_notify_new_successor (void *cls,
5254 const struct GNUNET_SCHEDULER_TaskContext
5257 struct SendNotifyContext *ctx = (struct SendNotifyContext *) cls;
5259 GDS_NEIGHBOURS_send_notify_new_successor (ctx->source_peer,
5261 ctx->successor_trail,
5262 ctx->successor_trail_length,
5263 ctx->succesor_trail_id,
5264 ctx->target_friend);
5266 if (0 == ctx->num_retries_scheduled &&
5267 send_notify_new_successor_retry_task != NULL)
5269 // Result from previous notify successos hasn't arrived, so the retry task
5270 // hasn't been cancelled! Already a new notify successor must be called.
5271 // We will cancel the retry request.
5272 struct SendNotifyContext *old_notify_ctx;
5273 old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5274 GNUNET_free (old_notify_ctx->successor_trail);
5275 GNUNET_free (old_notify_ctx);
5276 send_notify_new_successor_retry_task = NULL;
5279 ctx->num_retries_scheduled++;
5280 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_add_delayed(notify_successor_retry_time,
5281 &send_notify_new_successor,
5286 * Core handle for p2p verify successor result messages.
5287 * @param cls closure
5288 * @param message message
5289 * @param peer peer identity this notification is about
5290 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5293 handle_dht_p2p_verify_successor_result(void *cls,
5294 const struct GNUNET_PeerIdentity *peer,
5295 const struct GNUNET_MessageHeader *message)
5297 const struct PeerVerifySuccessorResultMessage *vsrm;
5298 enum GDS_ROUTING_trail_direction trail_direction;
5299 struct GNUNET_PeerIdentity querying_peer;
5300 struct GNUNET_HashCode trail_id;
5301 struct GNUNET_PeerIdentity *next_hop;
5302 struct FriendInfo *target_friend;
5303 struct GNUNET_PeerIdentity probable_successor;
5304 struct GNUNET_PeerIdentity current_successor;
5305 const struct GNUNET_PeerIdentity *trail;
5306 unsigned int trail_length;
5309 msize = ntohs (message->size);
5310 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5312 GNUNET_break_op (0);
5316 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5317 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5318 sizeof (struct GNUNET_PeerIdentity) != 0)
5320 GNUNET_break_op (0);
5323 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5324 sizeof (struct GNUNET_PeerIdentity);
5326 GNUNET_STATISTICS_update (GDS_stats,
5328 ("# Bytes received from other peers"), msize,
5331 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5332 querying_peer = vsrm->querying_peer;
5333 trail_direction = ntohl (vsrm->trail_direction);
5334 trail_id = vsrm->trail_id;
5335 probable_successor = vsrm->probable_successor;
5336 current_successor = vsrm->current_successor;
5338 /* I am the querying_peer. */
5339 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5341 /* Cancel Retry Task */
5342 if (NULL != send_verify_successor_retry_task)
5344 struct VerifySuccessorContext *ctx;
5345 ctx = GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
5347 send_verify_successor_retry_task = NULL;
5349 compare_and_update_successor (current_successor,
5350 probable_successor, trail, trail_length);
5354 /*If you are not the querying peer then pass on the message */
5355 if(NULL == (next_hop =
5356 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
5358 /* Here it may happen that source peer has found a new successor, and removed
5359 the trail, Hence no entry found in the routing table. Fail silently.*/
5360 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5361 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5365 if (NULL == (target_friend =
5366 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5371 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5372 vsrm->current_successor,
5373 probable_successor, trail_id,
5376 trail_direction, target_friend);
5382 * Core handle for p2p notify new successor messages.
5383 * @param cls closure
5384 * @param message message
5385 * @param peer peer identity this notification is about
5386 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5389 handle_dht_p2p_notify_new_successor(void *cls,
5390 const struct GNUNET_PeerIdentity *peer,
5391 const struct GNUNET_MessageHeader *message)
5393 const struct PeerNotifyNewSuccessorMessage *nsm;
5394 struct GNUNET_PeerIdentity *trail;
5395 struct GNUNET_PeerIdentity source;
5396 struct GNUNET_PeerIdentity new_successor;
5397 struct GNUNET_HashCode trail_id;
5398 struct GNUNET_PeerIdentity next_hop;
5399 struct FriendInfo *target_friend;
5402 uint32_t trail_length;
5404 msize = ntohs (message->size);
5405 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5407 GNUNET_break_op (0);
5410 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5411 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5412 sizeof (struct GNUNET_PeerIdentity) != 0)
5414 GNUNET_break_op (0);
5417 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5418 sizeof (struct GNUNET_PeerIdentity);
5419 GNUNET_STATISTICS_update (GDS_stats,
5421 ("# Bytes received from other peers"), msize,
5424 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5425 source = nsm->source_peer;
5426 new_successor = nsm->new_successor;
5427 trail_id = nsm->trail_id;
5429 /* I am the new_successor to source_peer. */
5430 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5432 if(trail_length > 0)
5433 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5436 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5438 compare_and_update_predecessor (source, trail, trail_length);
5439 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5440 GNUNET_assert (NULL != target_friend);
5441 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5442 GDS_ROUTING_DEST_TO_SRC,
5447 GNUNET_assert(trail_length > 0);
5448 /* I am part of trail to reach to successor. */
5449 my_index = search_my_index (trail, trail_length);
5452 DEBUG ("No entry found in trail\n");
5453 GNUNET_break_op (0);
5454 return GNUNET_SYSERR;
5456 if((trail_length + 1) == my_index)
5458 DEBUG ("Found twice in trail.\n");
5459 GNUNET_break_op (0);
5460 return GNUNET_SYSERR;
5462 if ((trail_length-1) == my_index)
5463 next_hop = new_successor;
5465 next_hop = trail[my_index + 1];
5467 GDS_ROUTING_add(trail_id, *peer, next_hop);
5469 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
5470 if (NULL == target_friend)
5475 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5477 trail_id, target_friend);
5484 * Core handler for P2P notify successor message
5485 * @param cls closure
5486 * @param message message
5487 * @param peer peer identity this notification is about
5488 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5491 handle_dht_p2p_notify_succ_confirmation (void *cls,
5492 const struct GNUNET_PeerIdentity *peer,
5493 const struct GNUNET_MessageHeader *message)
5495 const struct PeerNotifyConfirmationMessage *notify_confirmation;
5496 enum GDS_ROUTING_trail_direction trail_direction;
5497 struct GNUNET_HashCode trail_id;
5498 struct FriendInfo *target_friend;
5499 struct GNUNET_PeerIdentity *next_hop;
5502 msize = ntohs (message->size);
5504 if (msize != sizeof (struct PeerNotifyConfirmationMessage))
5506 GNUNET_break_op (0);
5509 GNUNET_STATISTICS_update (GDS_stats,
5511 ("# Bytes received from other peers"), msize,
5514 notify_confirmation = (const struct PeerNotifyConfirmationMessage *) message;
5515 trail_direction = ntohl (notify_confirmation->trail_direction);
5516 trail_id = notify_confirmation->trail_id;
5518 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5519 if (NULL == next_hop)
5521 /* The source of notify new successor, might have found even a better
5522 successor. In that case it send a trail teardown message, and hence,
5523 the next hop is NULL. */
5524 //Fixme: Add some print to confirm the above theory.
5528 /* I peer which sent the notify successor message to the successor. */
5529 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5532 * Schedule another round of verify sucessor with your current successor
5533 * which may or may not be source of this message. This message is used
5534 * only to ensure that we have a path setup to reach to our successor.
5537 // TODO: cancel schedule of notify_successor_retry_task
5538 if (send_notify_new_successor_retry_task != NULL)
5540 struct SendNotifyContext *notify_ctx;
5541 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5542 GNUNET_free (notify_ctx->successor_trail);
5543 GNUNET_free (notify_ctx);
5544 send_notify_new_successor_retry_task = NULL;
5546 if (send_verify_successor_task == NULL)
5548 verify_successor_next_send_time.rel_value_us =
5549 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5550 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5551 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5552 send_verify_successor_task =
5553 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5554 &send_verify_successor_message,
5560 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
5561 if (NULL == target_friend)
5563 DEBUG ("\n friend not found, line number = %d",__LINE__);
5564 return GNUNET_SYSERR;
5566 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5567 GDS_ROUTING_DEST_TO_SRC,
5575 * Core handler for P2P trail rejection message
5576 * @param cls closure
5577 * @param message message
5578 * @param peer peer identity this notification is about
5579 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5582 handle_dht_p2p_trail_setup_rejection (void *cls,
5583 const struct GNUNET_PeerIdentity *peer,
5584 const struct GNUNET_MessageHeader *message)
5586 const struct PeerTrailRejectionMessage *trail_rejection;
5587 unsigned int trail_length;
5588 const struct GNUNET_PeerIdentity *trail_peer_list;
5589 struct FriendInfo *target_friend;
5590 struct GNUNET_TIME_Relative congestion_timeout;
5591 struct GNUNET_HashCode trail_id;
5592 struct GNUNET_PeerIdentity next_peer;
5593 struct GNUNET_PeerIdentity source;
5594 uint64_t ultimate_destination_finger_value;
5595 unsigned int is_predecessor;
5598 msize = ntohs (message->size);
5599 if (msize < sizeof (struct PeerTrailRejectionMessage))
5601 GNUNET_break_op (0);
5604 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5605 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5606 sizeof (struct GNUNET_PeerIdentity) != 0)
5608 GNUNET_break_op (0);
5611 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5612 sizeof (struct GNUNET_PeerIdentity);
5613 GNUNET_STATISTICS_update (GDS_stats,
5615 ("# Bytes received from other peers"), msize,
5618 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5619 is_predecessor = ntohl (trail_rejection->is_predecessor);
5620 congestion_timeout = trail_rejection->congestion_time;
5621 source = trail_rejection->source_peer;
5622 trail_id = trail_rejection->trail_id;
5623 ultimate_destination_finger_value =
5624 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5625 /* First set the congestion time of the friend that sent you this message. */
5626 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5627 if (NULL == target_friend)
5629 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5633 target_friend->congestion_timestamp =
5634 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5635 congestion_timeout);
5637 /* I am the source peer which wants to setup the trail. Do nothing.
5638 * send_find_finger_trail_task is scheduled periodically.*/
5639 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5642 /* If I am congested then pass this message to peer before me in trail. */
5643 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5645 /* First remove yourself from the trail. */
5646 unsigned int new_trail_length = trail_length - 1;
5647 struct GNUNET_PeerIdentity trail[new_trail_length];
5649 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5650 if (0 == trail_length)
5653 next_peer = trail[new_trail_length-1];
5656 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5657 if (NULL == target_friend)
5659 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5663 GDS_NEIGHBOURS_send_trail_rejection (source,
5664 ultimate_destination_finger_value,
5665 my_identity, is_predecessor,
5666 trail, new_trail_length, trail_id,
5667 target_friend, CONGESTION_TIMEOUT);
5671 struct Closest_Peer successor;
5672 successor = find_local_best_known_next_hop (ultimate_destination_finger_value, is_predecessor);
5674 /* Am I the final destination? */
5675 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5678 /*Here you are already part of trail. Copy the trail removing yourself. */
5679 unsigned int new_trail_length = trail_length - 1;
5680 struct GNUNET_PeerIdentity trail[new_trail_length];
5682 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5684 if (0 == new_trail_length)
5688 next_peer = trail[new_trail_length-1];
5691 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5693 if (NULL == target_friend)
5695 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5699 GDS_NEIGHBOURS_send_trail_setup_result (source,
5701 target_friend, new_trail_length,
5704 ultimate_destination_finger_value,
5709 /* Here I was already part of trail. So no need to add. */
5711 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5712 &successor.next_hop);
5713 if (NULL == target_friend)
5715 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5720 GDS_NEIGHBOURS_send_trail_setup (source,
5721 ultimate_destination_finger_value,
5722 successor.best_known_destination,
5723 target_friend, trail_length, trail_peer_list,
5724 is_predecessor, trail_id,
5725 successor.trail_id);
5732 * Core handler for trail teardown message.
5733 * @param cls closure
5734 * @param message message
5735 * @param peer sender of this messsage.
5736 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5739 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5740 const struct GNUNET_MessageHeader *message)
5742 const struct PeerTrailTearDownMessage *trail_teardown;
5743 enum GDS_ROUTING_trail_direction trail_direction;
5744 struct GNUNET_HashCode trail_id;
5745 struct GNUNET_PeerIdentity *next_hop;
5748 msize = ntohs (message->size);
5750 /* Here we pass only the trail id. */
5751 if (msize != sizeof (struct PeerTrailTearDownMessage))
5753 GNUNET_break_op (0);
5757 GNUNET_STATISTICS_update (GDS_stats,
5759 ("# Bytes received from other peers"), msize,
5762 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5763 trail_direction = ntohl (trail_teardown->trail_direction);
5764 trail_id = trail_teardown->trail_id;
5766 /* Check if peer is the real peer from which we should get this message.*/
5767 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5769 GNUNET_assert (NULL != (prev_hop =
5770 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5771 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5774 return GNUNET_SYSERR;
5778 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5779 if (NULL == next_hop)
5781 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5782 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5784 return GNUNET_SYSERR;
5787 /* I am the next hop, which means I am the final destination. */
5788 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5790 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5795 /* If not final destination, then send a trail teardown message to next hop.*/
5796 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5797 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5798 GDS_NEIGHBOURS_send_trail_teardown (&trail_id, trail_direction, next_hop);
5806 * Core handle for p2p add trail message.
5807 * @param cls closure
5808 * @param message message
5809 * @param peer peer identity this notification is about
5810 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5813 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5814 const struct GNUNET_MessageHeader *message)
5816 const struct PeerAddTrailMessage *add_trail;
5817 const struct GNUNET_PeerIdentity *trail;
5818 struct GNUNET_HashCode trail_id;
5819 struct GNUNET_PeerIdentity destination_peer;
5820 struct GNUNET_PeerIdentity source_peer;
5821 struct GNUNET_PeerIdentity next_hop;
5822 unsigned int trail_length;
5823 unsigned int my_index;
5826 msize = ntohs (message->size);
5827 /* In this message we pass the whole trail from source to destination as we
5828 * are adding that trail.*/
5829 //FIXME: failed when run with 1000 pears. check why.
5830 if (msize < sizeof (struct PeerAddTrailMessage))
5832 GNUNET_break_op (0);
5836 add_trail = (const struct PeerAddTrailMessage *) message;
5837 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5838 sizeof (struct GNUNET_PeerIdentity);
5839 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5840 sizeof (struct GNUNET_PeerIdentity) != 0)
5842 GNUNET_break_op (0);
5846 GNUNET_STATISTICS_update (GDS_stats,
5848 ("# Bytes received from other peers"), msize,
5851 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5852 destination_peer = add_trail->destination_peer;
5853 source_peer = add_trail->source_peer;
5854 trail_id = add_trail->trail_id;
5856 /* I am not the destination of the trail. */
5857 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5859 struct FriendInfo *target_friend;
5861 /* Get my location in the trail. */
5862 my_index = search_my_index (trail, trail_length);
5865 GNUNET_break_op (0);
5866 return GNUNET_SYSERR;
5868 if((trail_length + 1) == my_index)
5870 DEBUG ("Found twice in trail.\n");
5871 GNUNET_break_op (0);
5872 return GNUNET_SYSERR;
5874 if ((trail_length - 1) == my_index)
5876 next_hop = destination_peer;
5880 next_hop = trail[my_index + 1];
5882 /* Add in your routing table. */
5883 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5884 //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5885 GNUNET_assert (NULL !=
5887 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5888 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5889 trail, trail_length, target_friend);
5892 /* I am the destination. Add an entry in routing table. */
5893 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5899 * Free the finger trail in which the first friend to reach to a finger is
5900 * disconnected_friend. Also remove entry from routing table for that particular
5902 * @param disconnected_friend PeerIdentity of friend which got disconnected
5903 * @param remove_finger Finger whose trail we need to check if it has
5904 * disconnected_friend as the first hop.
5905 * @return Total number of trails in which disconnected_friend was the first
5909 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5910 struct FingerInfo *finger)
5912 struct GNUNET_PeerIdentity *next_hop;
5913 struct FriendInfo *remove_friend;
5914 struct Trail *current_trail;
5915 unsigned int matching_trails_count = 0;
5918 /* Iterate over all the trails of finger. */
5919 for (i = 0; i < finger->trails_count; i++)
5921 current_trail = &finger->trail_list[i];
5922 if (GNUNET_NO == current_trail->is_present)
5925 /* First friend to reach to finger is disconnected_peer. */
5926 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5927 disconnected_friend))
5930 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5931 disconnected_friend);
5932 GNUNET_assert (NULL != remove_friend);
5933 next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id,
5934 GDS_ROUTING_SRC_TO_DEST);
5936 /* Here it may happen that as all the peers got disconnected, the entry in
5937 routing table for that particular trail has been removed, because the
5938 previously disconnected peer was either a next hop or prev hop of that
5940 if (NULL != next_hop)
5942 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5944 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id));
5946 matching_trails_count++;
5947 free_trail (current_trail);
5948 current_trail->is_present = GNUNET_NO;
5951 return matching_trails_count;
5956 * Iterate over finger_table entries.
5957 * 0. Ignore finger which is my_identity or if no valid entry present at
5958 * that finger index.
5959 * 1. If disconnected_friend is a finger, then remove the routing entry from
5960 your own table. Free the trail.
5961 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5962 * 2.1 Remove all the trails and entry from routing table in which disconnected
5963 * friend is the first friend in the trail. If disconnected_friend is the
5964 * first friend in all the trails to reach finger, then remove the finger.
5965 * @param disconnected_friend Peer identity of friend which got disconnected.
5968 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5970 struct FingerInfo *current_finger;
5971 int removed_trails_count;
5974 /* Iterate over finger table entries. */
5975 for (i = 0; i < MAX_FINGERS; i++)
5977 current_finger = &finger_table[i];
5979 /* No finger stored at this trail index or I am the finger. */
5980 if ((GNUNET_NO == current_finger->is_present) ||
5981 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5985 /* Is disconnected_peer a finger? */
5986 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5987 ¤t_finger->finger_identity))
5989 remove_existing_finger (current_finger, i);
5992 /* If finger is a friend but not disconnected_friend, then continue. */
5993 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5994 ¤t_finger->finger_identity))
5997 /* Iterate over the list of trails to reach remove_finger. Check if
5998 * disconnected_friend is the first friend in any of the trail. */
5999 removed_trails_count = remove_matching_trails (disconnected_peer,
6001 current_finger->trails_count =
6002 current_finger->trails_count - removed_trails_count;
6003 if (0 == current_finger->trails_count)
6005 current_finger->is_present = GNUNET_NO;
6006 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
6013 * Method called whenever a peer disconnects.
6015 * @param cls closure
6016 * @param peer peer identity this notification is about
6019 handle_core_disconnect (void *cls,
6020 const struct GNUNET_PeerIdentity *peer)
6022 struct FriendInfo *remove_friend;
6023 struct P2PPendingMessage *pos;
6024 unsigned int discarded;
6026 /* If disconnected to own identity, then return. */
6027 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
6030 if(NULL == (remove_friend =
6031 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
6033 DEBUG("\n friend already disconnected.");
6037 remove_matching_fingers (peer);
6038 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
6039 GNUNET_assert (GNUNET_YES ==
6040 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
6044 /* Remove all the messages queued in pending list of this peer is discarded.*/
6045 if (remove_friend->th != NULL)
6047 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
6048 remove_friend->th = NULL;
6052 while (NULL != (pos = remove_friend->head))
6054 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
6059 GNUNET_STATISTICS_update (GDS_stats,
6061 ("# Queued messages discarded (peer disconnected)"),
6062 discarded, GNUNET_NO);
6063 //GNUNET_free (remove_friend);
6065 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
6068 if (NULL != find_finger_trail_task)
6070 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6071 find_finger_trail_task = NULL;
6079 * Method called whenever a peer connects.
6081 * @param cls closure
6082 * @param peer_identity peer identity this notification is about
6085 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
6087 struct FriendInfo *friend;
6089 /* Check for connect to self message */
6090 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
6093 /* If peer already exists in our friend_peermap, then exit. */
6094 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
6101 friend = GNUNET_new (struct FriendInfo);
6102 friend->id = *peer_identity;
6104 GNUNET_assert (GNUNET_OK ==
6105 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
6106 peer_identity, friend,
6107 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
6109 /* FIXME: now we are not making a distinction between fingers which are friends
6110 * also.But later, we should add a congestion timestamp on the friend, so that it is
6111 * selected after some time out. This is to ensure that both peers have added
6112 * each other as their friend. */
6113 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
6114 if (NULL == find_finger_trail_task)
6116 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
6122 * To be called on core init/fail.
6124 * @param cls service closure
6125 * @param identity the public identity of this peer
6128 core_init (void *cls,
6129 const struct GNUNET_PeerIdentity *identity)
6131 my_identity = *identity;
6136 * Initialize finger table entries.
6139 finger_table_init ()
6141 memset (&finger_table, 0, sizeof (finger_table));
6146 * Initialize neighbours subsystem.
6147 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
6150 GDS_NEIGHBOURS_init (void)
6152 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
6153 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
6154 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
6155 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
6156 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
6157 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
6158 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
6159 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
6160 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
6161 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
6162 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
6163 sizeof (struct PeerTrailTearDownMessage)},
6164 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
6165 {&handle_dht_p2p_notify_succ_confirmation, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION,
6166 sizeof (struct PeerNotifyConfirmationMessage)},
6170 #if ENABLE_MALICIOUS
6175 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
6176 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
6177 GNUNET_NO, core_handlers);
6179 if (NULL == core_api)
6180 return GNUNET_SYSERR;
6182 //TODO: check size of this peer map?
6183 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
6184 finger_table_init ();
6185 successor_times = 10;
6186 fingers_round_count = 5;
6187 find_finger_trail_task_next_send_time.rel_value_us =
6188 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
6189 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6190 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
6192 verify_successor_next_send_time.rel_value_us =
6193 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
6194 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6195 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
6197 verify_successor_retry_time.rel_value_us =
6198 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6199 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6200 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6202 notify_successor_retry_time.rel_value_us =
6203 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6204 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6205 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6213 * Free the memory held up by trails of a finger.
6216 delete_finger_table_entries()
6221 for(i = 0; i < MAX_FINGERS; i++)
6223 if(GNUNET_YES == finger_table[i].is_present)
6225 for(j = 0; j < finger_table[i].trails_count; j++)
6226 free_trail(&finger_table[i].trail_list[j]);
6233 * Shutdown neighbours subsystem.
6236 GDS_NEIGHBOURS_done (void)
6238 if (NULL == core_api)
6241 GNUNET_CORE_disconnect (core_api);
6244 delete_finger_table_entries();
6245 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6246 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6247 friend_peermap = NULL;
6249 if (NULL != find_finger_trail_task)
6251 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6252 find_finger_trail_task = NULL;
6255 if (NULL != send_verify_successor_task)
6257 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6258 send_verify_successor_task = NULL;
6261 if (NULL != send_verify_successor_retry_task)
6263 struct VerifySuccessorContext *ctx;
6264 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
6266 send_verify_successor_retry_task = NULL;
6269 if (send_notify_new_successor_retry_task != NULL)
6271 struct SendNotifyContext *notify_ctx;
6272 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
6273 GNUNET_free (notify_ctx->successor_trail);
6274 GNUNET_free (notify_ctx);
6275 send_notify_new_successor_retry_task = NULL;
6283 * @return my identity
6285 struct GNUNET_PeerIdentity
6286 GDS_NEIGHBOURS_get_my_id (void)
6291 /* end of gnunet-service-xdht_neighbours.c */