2 This file is part of GNUnet.
3 (C) 2009-2014 Christian Grothoff (and other contributing authors)
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., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, 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"
49 * 1. In X-Vine paper, there is no policy defined for replicating the data to
50 * recover in case of peer failure. We can do it in Chord way. In R5N, the key
51 * is hashed and then data is stored according to the key value generated after
56 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
59 * Maximum possible fingers (including predecessor) of a peer
61 #define MAX_FINGERS 65
64 * Maximum allowed number of pending messages per friend peer.
66 #define MAXIMUM_PENDING_PER_FRIEND 64
69 * How long to wait before sending another find finger trail request
71 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
74 * How long to wait before sending another verify successor message.
76 #define DHT_SEND_VERIFY_SUCCESSOR_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
79 * How long to wait before sending another verify successor message.
81 #define DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
84 * How long to wait before retrying notify successor.
86 #define DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
89 * How long at most to wait for transmission of a request to a friend ?
91 #define PENDING_MESSAGE_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
94 * Duration for which I may remain congested.
95 * Note: Its a static value. In future, a peer may do some analysis and calculate
96 * congestion_timeout based on 'some' parameters.
98 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
101 * In case we don't hear back from the current successor, then we can start
104 #define WAIT_NOTIFY_CONFIRMATION GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 200)
107 * Maximum number of trails allowed to go through a friend.
109 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
112 * Maximum number of trails stored per finger.
114 #define MAXIMUM_TRAILS_PER_FINGER 4
117 * Finger map index for predecessor entry in finger table.
119 #define PREDECESSOR_FINGER_ID 64
122 * FIXME: Its use only at 3 places check if you can remove it.
123 * To check if a finger is predecessor or not.
125 enum GDS_NEIGHBOURS_finger_type
127 GDS_FINGER_TYPE_PREDECESSOR = 1,
128 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
131 GNUNET_NETWORK_STRUCT_BEGIN
136 struct PeerPutMessage
139 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
141 struct GNUNET_MessageHeader header;
146 uint32_t options GNUNET_PACKED;
151 uint32_t block_type GNUNET_PACKED;
156 uint32_t hop_count GNUNET_PACKED;
159 * Replication level for this message
160 * In the current implementation, this value is not used.
162 uint32_t desired_replication_level GNUNET_PACKED;
165 * Length of the PUT path that follows (if tracked).
167 uint32_t put_path_length GNUNET_PACKED;
170 * Best known destination (could be my friend or finger) which should
171 * get this message next.
173 struct GNUNET_PeerIdentity best_known_destination;
176 * In case best_known_destination is a finger, then trail to reach
177 * to that finger. Else its default value is 0.
179 struct GNUNET_HashCode intermediate_trail_id;
182 * When does the content expire?
184 struct GNUNET_TIME_AbsoluteNBO expiration_time;
187 * The key to store the value under.
189 struct GNUNET_HashCode key GNUNET_PACKED;
191 /* put path (if tracked) */
200 struct PeerGetMessage
203 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
205 struct GNUNET_MessageHeader header;
210 uint32_t options GNUNET_PACKED;
213 * Desired content type.
215 uint32_t block_type GNUNET_PACKED;
220 uint32_t hop_count GNUNET_PACKED;
223 * Desired replication level for this request.
224 * In the current implementation, this value is not used.
226 uint32_t desired_replication_level GNUNET_PACKED;
229 * Total number of peers in get path.
231 unsigned int get_path_length;
234 * Best known destination (could be my friend or finger) which should
235 * get this message next.
237 struct GNUNET_PeerIdentity best_known_destination;
240 * In case best_known_destination is a finger, then trail to reach
241 * to that finger. Else its default value is 0.
243 struct GNUNET_HashCode intermediate_trail_id;
246 * The key we are looking for.
248 struct GNUNET_HashCode key;
251 /* struct GNUNET_PeerIdentity[]*/
257 struct PeerGetResultMessage
260 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
262 struct GNUNET_MessageHeader header;
265 * The type for the data.
267 uint32_t type GNUNET_PACKED;
270 * Number of peers recorded in the outgoing path from source to the
271 * stored location of this message.
273 uint32_t put_path_length GNUNET_PACKED;
276 * Length of the GET path that follows (if tracked).
278 uint32_t get_path_length GNUNET_PACKED;
281 * Peer which queried for get and should get the result.
283 struct GNUNET_PeerIdentity querying_peer;
286 * When does the content expire?
288 struct GNUNET_TIME_Absolute expiration_time;
291 * The key of the corresponding GET request.
293 struct GNUNET_HashCode key;
295 /* put path (if tracked) */
297 /* get path (if tracked) */
304 * P2P Trail setup message
306 struct PeerTrailSetupMessage
309 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
311 struct GNUNET_MessageHeader header;
314 * Is source_peer trying to setup the trail to a predecessor or any finger.
316 uint32_t is_predecessor;
319 * Peer closest to this value will be our finger.
321 uint64_t final_destination_finger_value;
324 * Source peer which wants to setup the trail to one of its finger.
326 struct GNUNET_PeerIdentity source_peer;
329 * Best known destination (could be my friend or finger) which should
330 * get this message next.
332 * FIXME: this could be removed if we include trail_source / trail_dest
333 * in the routing table. This way we save 32 bytes of bandwidth by using
334 * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID))
336 struct GNUNET_PeerIdentity best_known_destination;
339 * In case best_known_destination is a finger, then trail id of trail to
340 * reach to this finger.
342 struct GNUNET_HashCode intermediate_trail_id;
345 * Trail id for trail which we are trying to setup.
347 struct GNUNET_HashCode trail_id;
349 /* List of peers which are part of trail setup so far.
350 * Trail does NOT include source_peer and peer which will be closest to
351 * ultimate_destination_finger_value.
352 * struct GNUNET_PeerIdentity trail[]
357 * P2P Trail Setup Result message
359 struct PeerTrailSetupResultMessage
363 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
365 struct GNUNET_MessageHeader header;
368 * Finger to which we have found the path.
370 struct GNUNET_PeerIdentity finger_identity;
373 * Peer which started trail_setup to find trail to finger_identity
375 struct GNUNET_PeerIdentity querying_peer;
378 * Is the trail setup to querying_peer's predecessor or finger?
380 uint32_t is_predecessor;
383 * Value to which finger_identity is the closest peer.
385 uint64_t ulitmate_destination_finger_value;
388 * Identifier of the trail from querying peer to finger_identity, NOT
389 * including both endpoints.
391 struct GNUNET_HashCode trail_id;
393 /* List of peers which are part of the trail from querying peer to
394 * finger_identity, NOT including both endpoints.
395 * struct GNUNET_PeerIdentity trail[]
400 * P2P Verify Successor Message.
402 struct PeerVerifySuccessorMessage
405 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
407 struct GNUNET_MessageHeader header;
410 * Peer which wants to verify its successor.
412 struct GNUNET_PeerIdentity source_peer;
415 * Source Peer's current successor.
417 struct GNUNET_PeerIdentity successor;
420 * Identifier of trail to reach from source_peer to successor.
422 struct GNUNET_HashCode trail_id;
424 /* List of the peers which are part of trail to reach from source_peer
425 * to successor, NOT including them
426 * struct GNUNET_PeerIdentity trail[]
431 * P2P Verify Successor Result Message
433 struct PeerVerifySuccessorResultMessage
436 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
438 struct GNUNET_MessageHeader header;
441 * Peer which sent the request to verify its successor.
443 struct GNUNET_PeerIdentity querying_peer;
446 * Successor to which PeerVerifySuccessorMessage was sent.
448 struct GNUNET_PeerIdentity current_successor;
451 * Current Predecessor of source_successor. It can be same as querying peer
452 * or different. In case it is different then it can be querying_peer's
453 * probable successor.
455 struct GNUNET_PeerIdentity probable_successor;
458 * Trail identifier of trail from querying_peer to current_successor.
460 struct GNUNET_HashCode trail_id;
463 * Direction in which we are looking at the trail.
465 uint32_t trail_direction;
467 /* In case probable_successor != querying_peer, then trail to reach from
468 * querying_peer to probable_successor, NOT including end points.
469 * struct GNUNET_PeerIdentity trail[]
474 * P2P Notify New Successor Message.
476 struct PeerNotifyNewSuccessorMessage
479 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
481 struct GNUNET_MessageHeader header;
484 * Peer which wants to notify its new successor.
486 struct GNUNET_PeerIdentity source_peer;
489 * New successor of source_peer.
491 struct GNUNET_PeerIdentity new_successor;
494 * Unique identifier of the trail from source_peer to new_successor,
495 * NOT including the endpoints.
497 struct GNUNET_HashCode trail_id;
499 /* List of peers in trail from source_peer to new_successor,
500 * NOT including the endpoints.
501 * struct GNUNET_PeerIdentity trail[]
506 * P2P Notify Successor Confirmation message.
508 struct PeerNotifyConfirmationMessage
511 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
513 struct GNUNET_MessageHeader header;
516 * Unique identifier of the trail.
518 struct GNUNET_HashCode trail_id;
521 * Direction of trail.
523 uint32_t trail_direction;
528 * P2P Trail Tear Down message.
530 struct PeerTrailTearDownMessage
533 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
535 struct GNUNET_MessageHeader header;
538 * Unique identifier of the trail.
540 struct GNUNET_HashCode trail_id;
543 * Direction of trail.
545 uint32_t trail_direction;
550 * P2P Trail Rejection Message.
552 struct PeerTrailRejectionMessage
555 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
557 struct GNUNET_MessageHeader header;
560 * Peer which wants to set up the trail.
562 struct GNUNET_PeerIdentity source_peer;
565 * Peer which sent trail rejection message as it it congested.
567 struct GNUNET_PeerIdentity congested_peer;
570 * Peer identity closest to this value will be finger of
573 uint64_t ultimate_destination_finger_value;
576 * Is source_peer trying to setup the trail to its predecessor or finger.
578 uint32_t is_predecessor;
581 * Identifier for the trail that source peer is trying to setup.
583 struct GNUNET_HashCode trail_id;
586 * Relative time for which congested_peer will remain congested.
588 struct GNUNET_TIME_Relative congestion_time;
590 /* Trail_list from source_peer to peer which sent the message for trail setup
591 * to congested peer. This trail does NOT include source_peer.
592 struct GNUNET_PeerIdnetity trail[]*/
596 * P2P Add Trail Message.
598 struct PeerAddTrailMessage
601 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
603 struct GNUNET_MessageHeader header;
606 * Source of the routing trail.
608 struct GNUNET_PeerIdentity source_peer;
611 * Destination of the routing trail.
613 struct GNUNET_PeerIdentity destination_peer;
616 * Unique identifier of the trail from source_peer to destination_peer,
617 * NOT including the endpoints.
619 struct GNUNET_HashCode trail_id;
621 /* Trail from source peer to destination peer, NOT including them.
622 * struct GNUNET_PeerIdentity trail[]
627 GNUNET_NETWORK_STRUCT_END
630 * Linked list of messages to send to a particular other peer.
632 struct P2PPendingMessage
635 * Pointer to next item in the list
637 struct P2PPendingMessage *next;
640 * Pointer to previous item in the list
642 struct P2PPendingMessage *prev;
645 * Message importance level. FIXME: used? useful?
647 unsigned int importance;
650 * When does this message time out?
652 struct GNUNET_TIME_Absolute timeout;
655 * Actual message to be sent, allocated at the end of the struct:
656 * // msg = (cast) &pm[1];
657 * // memcpy (&pm[1], data, len);
659 const struct GNUNET_MessageHeader *msg;
664 * Entry in friend_peermap.
671 struct GNUNET_PeerIdentity id;
674 * Number of trails for which this friend is the first hop or if the friend
677 unsigned int trails_count;
680 * Count of outstanding messages for this friend.
682 unsigned int pending_count;
685 * In case not 0, then amount of time for which this friend is congested.
687 struct GNUNET_TIME_Absolute congestion_timestamp;
690 // TODO : Change name of head and tail to pending_messages_list_head and so.
692 * Head of pending messages to be sent to this friend.
694 struct P2PPendingMessage *head;
697 * Tail of pending messages to be sent to this friend.
699 struct P2PPendingMessage *tail;
702 * Core handle for sending messages to this friend.
704 struct GNUNET_CORE_TransmitHandle *th;
709 * An individual element of the trail to reach to a finger.
714 * Pointer to next item in the list
716 struct Trail_Element *next;
719 * Pointer to prev item in the list
721 struct Trail_Element *prev;
724 * An element in this trail.
726 struct GNUNET_PeerIdentity peer;
730 * Information about an individual trail.
737 struct Trail_Element *trail_head;
742 struct Trail_Element *trail_tail;
745 * Unique identifier of this trail.
747 struct GNUNET_HashCode trail_id;
750 * Length of trail pointed
752 unsigned int trail_length;
755 * Is there a valid trail entry.
757 unsigned int is_present;
761 * An entry in finger_table
768 struct GNUNET_PeerIdentity finger_identity;
771 * In case not 0, this amount is time to wait for notify successor message.
772 * Used ONLY for successor. NOT for any other finger.
774 struct GNUNET_TIME_Absolute wait_notify_confirmation;
777 * Is any finger stored at this finger index.
779 unsigned int is_present;
782 * Index in finger peer map
784 uint32_t finger_table_index;
787 * Number of trails setup so far for this finger.
788 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
790 uint32_t trails_count;
793 * Array of trails to reach to this finger.
795 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
800 * Stores information about the peer which is closest to destination_finger_value.
801 * 'closest' can be either successor or predecessor depending on is_predecessor
807 * Destination finger value.
809 uint64_t destination_finger_value;
812 * Is finger_value a predecessor or any other finger.
814 unsigned int is_predecessor;
817 * Trail id to reach to peer.
818 * In case peer is my identity or friend, it is set to 0.
820 struct GNUNET_HashCode trail_id;
823 * Next destination. In case of friend and my_identity , it is same as next_hop
824 * In case of finger it is finger identity.
826 struct GNUNET_PeerIdentity best_known_destination;
829 * In case best_known_destination is a finger, then first friend in the trail
830 * to reach to it. In other case, same as best_known_destination.
832 struct GNUNET_PeerIdentity next_hop;
835 * In case finger is the next hop, it contains a valid finger table index
836 * at which the finger is stored. Else, It contains 65, which is out of range
837 * of finger table index.
839 unsigned int finger_table_index;
843 * Context for send_verify_successor_task.
845 struct VerifySuccessorContext
848 * Number of times this has been scheduled.
850 unsigned int num_retries_scheduled;
854 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
855 * get our first friend.
857 static struct GNUNET_SCHEDULER_Task * find_finger_trail_task;
860 * Task that sends verify successor message. This task is started when we get
861 * our successor for the first time.
863 static struct GNUNET_SCHEDULER_Task * send_verify_successor_task;
866 * Task that sends verify successor message. This task is started when we get
867 * our successor for the first time.
869 static struct GNUNET_SCHEDULER_Task * send_verify_successor_retry_task;
872 * Task that sends verify successor message. This task is started when we get
873 * our successor for the first time.
875 static struct GNUNET_SCHEDULER_Task * send_notify_new_successor_retry_task;
878 * Identity of this peer.
880 static struct GNUNET_PeerIdentity my_identity;
883 * Peer map of all the friends of a peer
885 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
888 * Array of all the fingers.
890 static struct FingerInfo finger_table [MAX_FINGERS];
895 static struct GNUNET_CORE_Handle *core_api;
898 * Handle for the statistics service.
900 //extern struct GNUNET_STATISTICS_Handle *GDS_stats;
903 * The current finger index that we have want to find trail to. We start the
904 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
905 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
906 * we reset this index to 0.
908 static unsigned int current_search_finger_index;
911 * Time duration to schedule find finger trail task.
913 static struct GNUNET_TIME_Relative find_finger_trail_task_next_send_time;
916 * Time duration to schedule verify successor task.
918 static struct GNUNET_TIME_Relative verify_successor_next_send_time;
921 * Time duration to send verify successor again, if result was not received in time.
923 static struct GNUNET_TIME_Relative verify_successor_retry_time;
926 * Time duration to retry send_notify_successor.
928 static struct GNUNET_TIME_Relative notify_successor_retry_time;
931 * Are we waiting for confirmation from our new successor that it got the
934 //static unsigned int waiting_for_notify_confirmation;
936 /* Below variables are used only for testing, and statistics collection. */
938 * Should we store our topology predecessor and successor IDs into statistics?
940 unsigned int track_topology;
943 * Should I be a malicious peer and drop the PUT/GET packets?
944 * if 0 then NOT malicious.
946 unsigned int act_malicious;
949 * Count of fingers found. Ideally we should have O(logn) fingers for a
952 static unsigned int total_fingers_found;
955 * Number of times we found the same successor.
957 static unsigned int successor_times;
960 * Number of rounds for which we should search for finger.
962 static unsigned int fingers_round_count;
964 * Called when core is ready to send a message we asked for
965 * out to the destination.
967 * @param cls the 'struct FriendInfo' of the target friend
968 * @param size number of bytes available in buf
969 * @param buf where the callee should write the message
970 * @return number of bytes written to buf
973 core_transmit_notify (void *cls, size_t size, void *buf)
975 struct FriendInfo *peer = cls;
977 struct P2PPendingMessage *pending;
982 while ( (NULL != (pending = peer->head)) &&
983 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us) )
985 GNUNET_STATISTICS_update (GDS_stats,
987 ("# Messages dropped (CORE timeout)"),
990 peer->pending_count--;
991 GNUNET_CONTAINER_DLL_remove (peer->head,
994 GNUNET_free (pending);
998 /* no messages pending */
1004 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1005 GNUNET_CORE_PRIO_BEST_EFFORT,
1006 GNUNET_TIME_absolute_get_remaining
1007 (pending->timeout), &peer->id,
1008 ntohs (pending->msg->size),
1009 &core_transmit_notify, peer);
1010 GNUNET_break (NULL != peer->th);
1014 while ((NULL != (pending = peer->head)) &&
1015 (size - off >= (msize = ntohs (pending->msg->size))))
1017 GNUNET_STATISTICS_update (GDS_stats,
1019 ("# Bytes transmitted to other peers"),
1022 memcpy (&cbuf[off], pending->msg, msize);
1024 peer->pending_count--;
1025 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1026 GNUNET_free (pending);
1028 if (peer->head != NULL)
1031 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1032 GNUNET_CORE_PRIO_BEST_EFFORT,
1033 GNUNET_TIME_absolute_get_remaining
1034 (pending->timeout), &peer->id, msize,
1035 &core_transmit_notify, peer);
1036 GNUNET_break (NULL != peer->th);
1043 * Transmit all messages in the friend's message queue.
1045 * @param peer message queue to process
1048 process_friend_queue (struct FriendInfo *peer)
1050 struct P2PPendingMessage *pending;
1052 if (NULL == (pending = peer->head))
1056 if (NULL != peer->th)
1062 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1063 pending->importance,
1064 GNUNET_TIME_absolute_get_remaining
1065 (pending->timeout), &peer->id,
1066 ntohs (pending->msg->size),
1067 &core_transmit_notify, peer);
1068 GNUNET_break (NULL != peer->th);
1072 #if ENABLE_MALICIOUS
1074 * Set the ENABLE_MALICIOUS value to malicious.
1078 GDS_NEIGHBOURS_act_malicious (unsigned int malicious)
1080 act_malicious = malicious;
1086 * Construct a trail setup message and forward it to target_friend
1087 * @param source_peer Peer which wants to setup the trail
1088 * @param ultimate_destination_finger_value Peer identity closest to this value
1089 * will be finger to @a source_peer
1090 * @param best_known_destination Best known destination (could be finger or friend)
1091 * which should get this message. In case it is
1092 * friend, then it is same as target_friend
1093 * @param target_friend Friend to which message is forwarded now.
1094 * @param trail_length Total number of peers in trail setup so far.
1095 * @param trail_peer_list Trail setup so far
1096 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1097 * @param trail_id Unique identifier for the trail we are trying to setup.
1098 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1099 * best_known_destination when its a finger. If not
1100 * used then set to 0.
1103 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1104 uint64_t ultimate_destination_finger_value,
1105 struct GNUNET_PeerIdentity best_known_destination,
1106 struct FriendInfo *target_friend,
1107 unsigned int trail_length,
1108 const struct GNUNET_PeerIdentity *trail_peer_list,
1109 unsigned int is_predecessor,
1110 struct GNUNET_HashCode trail_id,
1111 struct GNUNET_HashCode intermediate_trail_id)
1113 struct P2PPendingMessage *pending;
1114 struct PeerTrailSetupMessage *tsm;
1115 struct GNUNET_PeerIdentity *peer_list;
1118 msize = sizeof (struct PeerTrailSetupMessage) +
1119 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1121 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1127 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1129 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1132 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1133 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1134 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1135 pending->msg = &(tsm->header);
1136 tsm->header.size = htons (msize);
1137 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1138 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1139 tsm->source_peer = source_peer;
1140 tsm->best_known_destination = best_known_destination;
1141 tsm->is_predecessor = htonl (is_predecessor);
1142 tsm->trail_id = trail_id;
1143 tsm->intermediate_trail_id = intermediate_trail_id;
1145 if (trail_length > 0)
1147 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1148 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1151 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1152 target_friend->pending_count++;
1153 process_friend_queue (target_friend);
1158 * Construct a trail setup result message and forward it to target friend.
1159 * @param querying_peer Peer which sent the trail setup request and should get
1161 * @param Finger Peer to which the trail has been setup to.
1162 * @param target_friend Friend to which this message should be forwarded.
1163 * @param trail_length Numbers of peers in the trail.
1164 * @param trail_peer_list Peers which are part of the trail from
1165 * querying_peer to Finger, NOT including them.
1166 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1167 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1169 * @param trail_id Unique identifier of the trail.
1172 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1173 struct GNUNET_PeerIdentity finger,
1174 struct FriendInfo *target_friend,
1175 unsigned int trail_length,
1176 const struct GNUNET_PeerIdentity *trail_peer_list,
1177 unsigned int is_predecessor,
1178 uint64_t ultimate_destination_finger_value,
1179 struct GNUNET_HashCode trail_id)
1181 struct P2PPendingMessage *pending;
1182 struct PeerTrailSetupResultMessage *tsrm;
1183 struct GNUNET_PeerIdentity *peer_list;
1186 msize = sizeof (struct PeerTrailSetupResultMessage) +
1187 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1189 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1195 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1197 GNUNET_STATISTICS_update (GDS_stats,
1198 gettext_noop ("# P2P messages dropped due to full queue"),
1202 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1203 pending->importance = 0;
1204 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1205 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1206 pending->msg = &tsrm->header;
1207 tsrm->header.size = htons (msize);
1208 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1209 tsrm->querying_peer = querying_peer;
1210 tsrm->finger_identity = finger;
1211 tsrm->is_predecessor = htonl (is_predecessor);
1212 tsrm->trail_id = trail_id;
1213 tsrm->ulitmate_destination_finger_value =
1214 GNUNET_htonll (ultimate_destination_finger_value);
1215 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1216 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1218 /* Send the message to chosen friend. */
1219 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1220 target_friend->pending_count++;
1221 process_friend_queue (target_friend);
1225 * Send notify successor confirmation message.
1226 * @param trail_id Unique Identifier of the trail.
1227 * @param trail_direction Destination to Source.
1228 * @param target_friend Friend to get this message next.
1231 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (struct GNUNET_HashCode trail_id,
1232 unsigned int trail_direction,
1233 struct FriendInfo *target_friend)
1235 struct PeerNotifyConfirmationMessage *ncm;
1236 struct P2PPendingMessage *pending;
1239 msize = sizeof (struct PeerNotifyConfirmationMessage);
1240 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1246 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1248 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1252 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1253 pending->importance = 0; /* FIXME */
1254 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1255 ncm = (struct PeerNotifyConfirmationMessage *) &pending[1];
1256 pending->msg = &ncm->header;
1257 ncm->header.size = htons (msize);
1258 ncm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION);
1259 ncm->trail_id = trail_id;
1260 ncm->trail_direction = htonl (trail_direction);
1262 /* Send the message to chosen friend. */
1263 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1264 target_friend->pending_count++;
1265 process_friend_queue (target_friend);
1270 * Send trail rejection message to target friend
1271 * @param source_peer Peer which is trying to setup the trail.
1272 * @param ultimate_destination_finger_value Peer closest to this value will be
1273 * @a source_peer's finger
1274 * @param congested_peer Peer which sent this message as it is congested.
1275 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1276 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1277 * by congested_peer. This does NOT include @a source_peer
1278 * and congested_peer.
1279 * @param trail_length Total number of peers in trail_peer_list, NOT including
1280 * @a source_peer and @a congested_peer
1281 * @param trail_id Unique identifier of this trail.
1282 * @param congestion_timeout Duration given by congested peer as an estimate of
1283 * how long it may remain congested.
1286 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1287 uint64_t ultimate_destination_finger_value,
1288 struct GNUNET_PeerIdentity congested_peer,
1289 unsigned int is_predecessor,
1290 const struct GNUNET_PeerIdentity *trail_peer_list,
1291 unsigned int trail_length,
1292 struct GNUNET_HashCode trail_id,
1293 struct FriendInfo *target_friend,
1294 const struct GNUNET_TIME_Relative congestion_timeout)
1296 struct PeerTrailRejectionMessage *trm;
1297 struct P2PPendingMessage *pending;
1298 struct GNUNET_PeerIdentity *peer_list;
1301 msize = sizeof (struct PeerTrailRejectionMessage) +
1302 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1304 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1310 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1312 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1316 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1317 pending->importance = 0;
1318 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1319 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1320 pending->msg = &trm->header;
1321 trm->header.size = htons (msize);
1322 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1323 trm->source_peer = source_peer;
1324 trm->congested_peer = congested_peer;
1325 trm->congestion_time = congestion_timeout;
1326 trm->is_predecessor = htonl (is_predecessor);
1327 trm->trail_id = trail_id;
1328 trm->ultimate_destination_finger_value =
1329 GNUNET_htonll (ultimate_destination_finger_value);
1331 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1332 if (trail_length > 0)
1334 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1337 /* Send the message to chosen friend. */
1338 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1339 target_friend->pending_count++;
1340 process_friend_queue (target_friend);
1345 * Construct a verify successor message and forward it to target_friend.
1346 * @param source_peer Peer which wants to verify its successor.
1347 * @param successor Peer which is @a source_peer's current successor.
1348 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1349 * NOT including them.
1350 * @param trail List of peers which are part of trail to reach from @a source_peer
1351 * to @a successor, NOT including them.
1352 * @param trail_length Total number of peers in @a trail.
1353 * @param target_friend Next friend to get this message.
1356 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1357 struct GNUNET_PeerIdentity successor,
1358 struct GNUNET_HashCode trail_id,
1359 struct GNUNET_PeerIdentity *trail,
1360 unsigned int trail_length,
1361 struct FriendInfo *target_friend)
1363 struct PeerVerifySuccessorMessage *vsm;
1364 struct P2PPendingMessage *pending;
1365 struct GNUNET_PeerIdentity *peer_list;
1368 msize = sizeof (struct PeerVerifySuccessorMessage) +
1369 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1371 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1377 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1379 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1383 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1384 pending->importance = 0; /* FIXME */
1385 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1386 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1387 pending->msg = &vsm->header;
1388 vsm->header.size = htons (msize);
1389 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1390 vsm->source_peer = source_peer;
1391 vsm->successor = successor;
1392 vsm->trail_id = trail_id;
1393 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1394 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1396 /* Send the message to chosen friend. */
1397 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1398 target_friend->pending_count++;
1399 process_friend_queue (target_friend);
1404 * FIXME: In every function we pass target friend except for this one.
1405 * so, either change everything or this one. also, should se just store
1406 * the pointer to friend in routing table rather than gnunet_peeridentity.
1407 * if yes then we should keep friend info in.h andmake lot of changes.
1408 * Construct a trail teardown message and forward it to target friend.
1410 * @param trail_id Unique identifier of the trail.
1411 * @param trail_direction Direction of trail.
1412 * @param target_friend Friend to get this message.
1415 GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_HashCode *trail_id,
1416 unsigned int trail_direction,
1417 const struct GNUNET_PeerIdentity *peer)
1419 struct PeerTrailTearDownMessage *ttdm;
1420 struct P2PPendingMessage *pending;
1421 struct FriendInfo *target_friend;
1424 msize = sizeof (struct PeerTrailTearDownMessage);
1425 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1431 if (NULL == (target_friend =
1432 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
1434 /* FIXME: In what case friend can be null. ?*/
1439 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1441 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1445 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1446 pending->importance = 0; /* FIXME */
1447 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1448 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1449 pending->msg = &ttdm->header;
1450 ttdm->header.size = htons (msize);
1451 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1452 ttdm->trail_id = *trail_id;
1453 ttdm->trail_direction = htonl (trail_direction);
1455 /* Send the message to chosen friend. */
1456 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1457 target_friend->pending_count++;
1458 process_friend_queue (target_friend);
1463 * Construct a verify successor result message and send it to target_friend
1464 * @param querying_peer Peer which sent the verify successor message.
1465 * @param source_successor Current_successor of @a querying_peer.
1466 * @param current_predecessor Current predecessor of @a successor. Could be same
1467 * or different from @a querying_peer.
1468 * @param trail_id Unique identifier of the trail from @a querying_peer to
1469 * @a successor, NOT including them.
1470 * @param trail List of peers which are part of trail from @a querying_peer to
1471 * @a successor, NOT including them.
1472 * @param trail_length Total number of peers in @a trail
1473 * @param trail_direction Direction in which we are sending the message. In this
1474 * case we are sending result from @a successor to @a querying_peer.
1475 * @param target_friend Next friend to get this message.
1478 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1479 struct GNUNET_PeerIdentity current_successor,
1480 struct GNUNET_PeerIdentity probable_successor,
1481 struct GNUNET_HashCode trail_id,
1482 const struct GNUNET_PeerIdentity *trail,
1483 unsigned int trail_length,
1484 enum GDS_ROUTING_trail_direction trail_direction,
1485 struct FriendInfo *target_friend)
1487 struct PeerVerifySuccessorResultMessage *vsmr;
1488 struct P2PPendingMessage *pending;
1489 struct GNUNET_PeerIdentity *peer_list;
1492 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1493 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1495 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1501 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1503 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1507 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1508 pending->importance = 0; /* FIXME */
1509 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1510 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1511 pending->msg = &vsmr->header;
1512 vsmr->header.size = htons (msize);
1513 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1514 vsmr->querying_peer = querying_peer;
1515 vsmr->current_successor = current_successor;
1516 vsmr->probable_successor = probable_successor;
1517 vsmr->trail_direction = htonl (trail_direction);
1518 vsmr->trail_id = trail_id;
1519 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1520 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1522 /* Send the message to chosen friend. */
1523 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1524 target_friend->pending_count++;
1525 process_friend_queue (target_friend);
1530 * Construct a notify new successor message and send it to target_friend
1531 * @param source_peer Peer which wants to notify to its new successor that it
1532 * could be its predecessor.
1533 * @param successor New successor of @a source_peer
1534 * @param successor_trail List of peers in Trail to reach from
1535 * @a source_peer to @a new_successor, NOT including
1537 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1538 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1539 * @param target_friend Next friend to get this message.
1542 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1543 struct GNUNET_PeerIdentity successor,
1544 const struct GNUNET_PeerIdentity *successor_trail,
1545 unsigned int successor_trail_length,
1546 struct GNUNET_HashCode succesor_trail_id,
1547 struct FriendInfo *target_friend)
1549 struct PeerNotifyNewSuccessorMessage *nsm;
1550 struct P2PPendingMessage *pending;
1551 struct GNUNET_PeerIdentity *peer_list;
1554 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1555 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1557 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1563 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1565 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1569 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1570 pending->importance = 0; /* FIXME */
1571 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1572 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1573 pending->msg = &nsm->header;
1574 nsm->header.size = htons (msize);
1575 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1576 nsm->new_successor = successor;
1577 nsm->source_peer = source_peer;
1578 nsm->trail_id = succesor_trail_id;
1579 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1580 memcpy (peer_list, successor_trail,
1581 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1583 /* Send the message to chosen friend. */
1584 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1585 target_friend->pending_count++;
1586 process_friend_queue (target_friend);
1591 * Construct an add_trail message and send it to target_friend
1592 * @param source_peer Source of the trail.
1593 * @param destination_peer Destination of the trail.
1594 * @param trail_id Unique identifier of the trail from
1595 * @a source_peer to @a destination_peer, NOT including the endpoints.
1596 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1597 * NOT including the endpoints.
1598 * @param trail_length Total number of peers in @a trail.
1599 * @param target_friend Next friend to get this message.
1602 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1603 struct GNUNET_PeerIdentity destination_peer,
1604 struct GNUNET_HashCode trail_id,
1605 const struct GNUNET_PeerIdentity *trail,
1606 unsigned int trail_length,
1607 struct FriendInfo *target_friend)
1609 struct PeerAddTrailMessage *adm;
1610 struct GNUNET_PeerIdentity *peer_list;
1611 struct P2PPendingMessage *pending;
1614 msize = sizeof (struct PeerAddTrailMessage) +
1615 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1617 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1623 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1625 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1629 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1630 pending->importance = 0; /* FIXME */
1631 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1632 adm = (struct PeerAddTrailMessage *) &pending[1];
1633 pending->msg = &adm->header;
1634 adm->header.size = htons (msize);
1635 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1636 adm->source_peer = source_peer;
1637 adm->destination_peer = destination_peer;
1638 adm->trail_id = trail_id;
1639 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1640 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1642 /* Send the message to chosen friend. */
1643 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1644 target_friend->pending_count++;
1645 process_friend_queue (target_friend);
1651 * Search my location in trail. In case I am present more than once in the
1652 * trail (can happen during trail setup), then return my lowest index.
1653 * @param trail List of peers
1654 * @return my_index if found
1655 * trail_length + 1 if an entry is present twice, It is an error.
1656 * -1 if no entry found.
1659 search_my_index (const struct GNUNET_PeerIdentity *trail,
1663 int index_seen = trail_length + 1;
1666 for (i = 0; i < trail_length; i++)
1668 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1671 if(index_seen == (trail_length + 1))
1675 DEBUG("Entry is present twice in trail. Its not allowed\n");
1689 * Check if the friend is congested or have reached maximum number of trails
1690 * it can be part of of.
1691 * @param friend Friend to be checked.
1692 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1693 * #GNUNET_YES if friend is either congested or have crossed threshold
1696 is_friend_congested (struct FriendInfo *friend)
1698 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1699 ((0 == GNUNET_TIME_absolute_get_remaining
1700 (friend->congestion_timestamp).rel_value_us)))
1708 * Select closest finger to value.
1709 * @param peer1 First peer
1710 * @param peer2 Second peer
1711 * @param value Value to be compare
1712 * @return Closest peer
1714 static struct GNUNET_PeerIdentity
1715 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1716 const struct GNUNET_PeerIdentity *peer2,
1719 uint64_t peer1_value;
1720 uint64_t peer2_value;
1722 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1723 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1724 peer1_value = GNUNET_ntohll (peer1_value);
1725 peer2_value = GNUNET_ntohll (peer2_value);
1727 if (peer1_value == value)
1732 if (peer2_value == value)
1737 if (value < peer1_value && peer1_value < peer2_value)
1741 else if (value < peer2_value && peer2_value < peer1_value)
1745 else if (peer1_value < value && value < peer2_value)
1749 else if (peer2_value < value && value < peer1_value)
1753 else if (peer1_value < peer2_value && peer2_value < value)
1757 else // if (peer2_value < peer1_value && peer1_value < value)
1765 * Select closest predecessor to value.
1766 * @param peer1 First peer
1767 * @param peer2 Second peer
1768 * @param value Value to be compare
1769 * @return Peer which precedes value in the network.
1771 static struct GNUNET_PeerIdentity
1772 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1773 const struct GNUNET_PeerIdentity *peer2,
1776 uint64_t peer1_value;
1777 uint64_t peer2_value;
1779 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1780 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1781 peer1_value = GNUNET_ntohll (peer1_value);
1782 peer2_value = GNUNET_ntohll (peer2_value);
1784 if (peer1_value == value)
1789 if (peer2_value == value)
1794 if (value < peer1_value && peer1_value < peer2_value)
1798 else if (value < peer2_value && peer2_value < peer1_value)
1802 else if (peer1_value < value && value < peer2_value)
1806 else if (peer2_value < value && value < peer1_value)
1810 else if (peer1_value < peer2_value && peer2_value < value)
1814 else // if (peer2_value < peer1_value && peer1_value < value)
1826 test_print_trail (struct GNUNET_PeerIdentity *trail,
1827 unsigned int trail_length)
1829 struct GNUNET_PeerIdentity print_peer;
1832 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1833 __FILE__, __func__,__LINE__,trail_length);
1834 for (i =0 ; i< trail_length; i++)
1836 print_peer = trail[i];
1837 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1838 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1845 * This is a test function to print all the entries of friend table.
1848 test_friend_peermap_print ()
1850 struct FriendInfo *friend;
1851 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1852 struct GNUNET_PeerIdentity print_peer;
1853 struct GNUNET_PeerIdentity key_ret;
1856 print_peer = my_identity;
1857 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1858 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1860 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1862 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1864 (const void **)&friend))
1866 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1867 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1868 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1876 * This is a test function, to print all the entries of finger table.
1879 test_finger_table_print()
1881 struct FingerInfo *finger;
1882 struct GNUNET_PeerIdentity print_peer;
1883 //struct Trail *trail;
1887 print_peer = my_identity;
1888 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1889 for (i = 0; i < MAX_FINGERS; i++)
1891 finger = &finger_table[i];
1893 if (GNUNET_NO == finger->is_present)
1896 print_peer = finger->finger_identity;
1897 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1898 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1901 for (j = 0; j < finger->trails_count; j++)
1903 trail = &finger->trail_list[j];
1904 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1905 struct Trail_Element *element;
1906 element = trail->trail_head;
1907 for (k = 0; k < trail->trail_length; k++)
1909 print_peer = element->peer;
1910 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1911 element = element->next;
1920 * Select the closest peer among two peers (which should not be same)
1921 * with respect to value and finger_table_index
1922 * NOTE: peer1 != peer2
1923 * @param peer1 First peer
1924 * @param peer2 Second peer
1925 * @param value Value relative to which we find the closest
1926 * @param is_predecessor Is value a predecessor or any other finger.
1927 * @return Closest peer among two peers.
1929 static struct GNUNET_PeerIdentity
1930 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1931 const struct GNUNET_PeerIdentity *peer2,
1933 unsigned int is_predecessor)
1935 /* This check is here to ensure that calling function never sends
1936 same peer value in peer1 and peer2. Remove it later. */
1937 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1938 if (1 == is_predecessor)
1939 return select_closest_predecessor (peer1, peer2, value);
1941 // TODO: Change name to something like select_closest_successor!!
1942 return select_closest_finger (peer1, peer2, value);
1947 * Iterate over the list of all the trails of a finger. In case the first
1948 * friend to reach the finger has reached trail threshold or is congested,
1949 * then don't select it. In case there multiple available good trails to reach
1950 * to Finger, choose the one with shortest trail length.
1951 * Note: We use length as parameter. But we can use any other suitable parameter
1953 * @param finger Finger Finger whose trail we have to select.
1954 * @return Trail Selected Trail.
1956 static struct Trail *
1957 select_finger_trail (struct FingerInfo *finger)
1959 struct FriendInfo *friend;
1960 struct Trail *current_finger_trail;
1961 struct Trail *best_trail = NULL;
1964 GNUNET_assert (finger->trails_count > 0);
1965 for (i = 0; i < finger->trails_count; i++)
1967 current_finger_trail = &finger->trail_list[i];
1969 /* No trail stored at this index. */
1970 if (GNUNET_NO == current_finger_trail->is_present)
1973 GNUNET_assert (NULL !=
1975 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1976 ¤t_finger_trail->trail_head->peer)));
1978 /* First friend to reach trail is not free. */
1979 if (GNUNET_YES == is_friend_congested (friend))
1982 if (NULL == best_trail ||
1983 best_trail->trail_length > current_finger_trail->trail_length)
1985 best_trail = current_finger_trail;
1994 * Compare FINGER entry with current successor. If finger's first friend of all
1995 * its trail is not congested and has not crossed trail threshold, then check
1996 * if finger peer identity is closer to final_destination_finger_value than
1997 * current_successor. If yes then update current_successor.
1998 * @param current_successor[in/out]
2002 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
2004 struct FingerInfo *finger;
2005 struct GNUNET_PeerIdentity closest_peer;
2006 struct Trail *finger_trail;
2009 /* Iterate over finger table. */
2010 for (i = 0; i < MAX_FINGERS; i++)
2012 finger = &finger_table[i];
2014 if (GNUNET_NO == finger->is_present)
2017 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2018 ¤t_closest_peer->best_known_destination))
2021 /* If I am my own finger, then ignore this finger. */
2022 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2026 /* If finger is a friend, we have already checked it in previous function. */
2027 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2028 &finger->finger_identity)))
2033 closest_peer = select_closest_peer (&finger->finger_identity,
2034 ¤t_closest_peer->best_known_destination,
2035 current_closest_peer->destination_finger_value,
2036 current_closest_peer->is_predecessor);
2038 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer))
2040 /* Choose one of the trail to reach to finger. */
2041 finger_trail = select_finger_trail (finger);
2043 /* In case no trail found, ignore this finger. */
2044 if (NULL == finger_trail)
2047 current_closest_peer->best_known_destination = closest_peer;
2048 current_closest_peer->next_hop = finger_trail->trail_head->peer;
2049 current_closest_peer->trail_id = finger_trail->trail_id;
2050 current_closest_peer->finger_table_index = i;
2058 * Compare friend entry with current successor.
2059 * If friend identity and current_successor is same, then do nothing.
2060 * If friend is not congested and has not crossed trail threshold, then check
2061 * if friend peer identity is closer to final_destination_finger_value than
2062 * current_successor. If yes then update current_successor.
2063 * @param cls closure
2064 * @param key current public key
2065 * @param value struct Closest_Peer
2066 * @return #GNUNET_YES if we should continue to iterate,
2067 * #GNUNET_NO if not.
2070 compare_friend_and_current_closest_peer (void *cls,
2071 const struct GNUNET_PeerIdentity *key,
2074 struct FriendInfo *friend = value;
2075 struct Closest_Peer *current_closest_peer = cls;
2076 struct GNUNET_PeerIdentity closest_peer;
2078 /* Friend is either congested or has crossed threshold. */
2079 if (GNUNET_YES == is_friend_congested (friend))
2082 /* If current_closest_peer and friend identity are same, then do nothing.*/
2083 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2084 ¤t_closest_peer->best_known_destination))
2090 closest_peer = select_closest_peer (&friend->id,
2091 ¤t_closest_peer->best_known_destination,
2092 current_closest_peer->destination_finger_value,
2093 current_closest_peer->is_predecessor);
2095 /* Is friend the closest successor? */
2096 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer))
2098 current_closest_peer->best_known_destination = friend->id;
2099 current_closest_peer->next_hop = friend->id;
2107 * Initialize current_successor to my_identity.
2108 * @param my_identity My peer identity
2109 * @return Updated closest_peer
2111 static struct Closest_Peer
2112 init_closest_peer (struct GNUNET_PeerIdentity my_identity,
2113 uint64_t destination_finger_value,
2114 unsigned int is_predecessor)
2116 struct Closest_Peer current_closest_peer;
2118 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2119 current_closest_peer.destination_finger_value = destination_finger_value;
2120 current_closest_peer.is_predecessor = is_predecessor;
2121 current_closest_peer.next_hop = my_identity;
2122 current_closest_peer.best_known_destination = my_identity;
2123 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
2124 return current_closest_peer;
2129 * Find locally best known peer, among your own identity, friend and finger list,
2130 * which is closest to given destination_finger_value.
2132 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2134 * @param destination_finger_value Peer closest to this value will be the next destination.
2135 * @param is_predecessor Are we looking for predecessor or finger?
2136 * @return Closest_Peer that contains all the relevant field to reach to
2137 * @a destination_finger_value
2139 static struct Closest_Peer
2140 find_local_best_known_next_hop (uint64_t destination_finger_value,
2141 unsigned int is_predecessor)
2143 struct Closest_Peer current_closest_peer;
2145 /* Initialize current_successor to my_identity. */
2146 current_closest_peer = init_closest_peer (my_identity,
2147 destination_finger_value,
2150 /* Compare each friend entry with current_successor and update current_successor
2151 * with friend if its closest. */
2154 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2155 &compare_friend_and_current_closest_peer,
2156 ¤t_closest_peer));
2158 /* Compare each finger entry with current_successor and update current_successor
2159 * with finger if its closest. */
2160 compare_finger_and_current_closest_peer (¤t_closest_peer);
2161 return current_closest_peer;
2166 * Construct a Put message and send it to target_peer.
2167 * @param key Key for the content
2168 * @param block_type Type of the block
2169 * @param options Routing options
2170 * @param desired_replication_level Desired replication count
2171 * @param best_known_dest Peer to which this message should reach eventually,
2172 * as it is best known destination to me.
2173 * @param intermediate_trail_id Trail id in case
2174 * @param target_peer Peer to which this message will be forwarded.
2175 * @param hop_count Number of hops traversed so far.
2176 * @param put_path_length Total number of peers in @a put_path
2177 * @param put_path Number of peers traversed so far
2178 * @param expiration_time When does the content expire
2179 * @param data Content to store
2180 * @param data_size Size of content @a data in bytes
2183 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2184 enum GNUNET_BLOCK_Type block_type,
2185 enum GNUNET_DHT_RouteOption options,
2186 uint32_t desired_replication_level,
2187 struct GNUNET_PeerIdentity best_known_dest,
2188 struct GNUNET_HashCode intermediate_trail_id,
2189 struct GNUNET_PeerIdentity *target_peer,
2191 uint32_t put_path_length,
2192 struct GNUNET_PeerIdentity *put_path,
2193 struct GNUNET_TIME_Absolute expiration_time,
2194 const void *data, size_t data_size)
2196 struct PeerPutMessage *ppm;
2197 struct P2PPendingMessage *pending;
2198 struct FriendInfo *target_friend;
2199 struct GNUNET_PeerIdentity *pp;
2202 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2203 sizeof (struct PeerPutMessage);
2204 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2206 put_path_length = 0;
2207 msize = data_size + sizeof (struct PeerPutMessage);
2210 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2212 DEBUG("msize = %lu\n",msize);
2217 GNUNET_assert (NULL !=
2219 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2220 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2221 pending->timeout = expiration_time;
2222 ppm = (struct PeerPutMessage *) &pending[1];
2223 pending->msg = &ppm->header;
2224 ppm->header.size = htons (msize);
2225 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2226 ppm->options = htonl (options);
2227 ppm->block_type = htonl (block_type);
2228 ppm->hop_count = htonl (hop_count + 1);
2229 ppm->desired_replication_level = htonl (desired_replication_level);
2230 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2231 ppm->best_known_destination = best_known_dest;
2232 ppm->intermediate_trail_id = intermediate_trail_id;
2234 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2235 ppm->put_path_length = htonl (put_path_length);
2236 if(put_path_length > 0)
2238 memcpy (pp, put_path,
2239 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2241 memcpy (&pp[put_path_length], data, data_size);
2242 GNUNET_assert (NULL != target_friend);
2243 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2244 target_friend->pending_count++;
2245 process_friend_queue (target_friend);
2250 * Handle the put request from the client.
2251 * @param key Key for the content
2252 * @param block_type Type of the block
2253 * @param options Routing options
2254 * @param desired_replication_level Desired replication count
2255 * @param expiration_time When does the content expire
2256 * @param data Content to store
2257 * @param data_size Size of content @a data in bytes
2260 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
2261 enum GNUNET_BLOCK_Type block_type,
2262 enum GNUNET_DHT_RouteOption options,
2263 uint32_t desired_replication_level,
2264 struct GNUNET_TIME_Absolute expiration_time,
2265 const void *data, size_t data_size)
2267 struct GNUNET_PeerIdentity best_known_dest;
2268 struct GNUNET_HashCode intermediate_trail_id;
2269 struct GNUNET_PeerIdentity next_hop;
2271 struct Closest_Peer successor;
2273 memcpy (&key_value, key, sizeof (uint64_t));
2274 key_value = GNUNET_ntohll (key_value);
2275 successor = find_local_best_known_next_hop (key_value,
2276 GDS_FINGER_TYPE_NON_PREDECESSOR);
2277 best_known_dest = successor.best_known_destination;
2278 next_hop = successor.next_hop;
2279 intermediate_trail_id = successor.trail_id;
2281 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2283 DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",GNUNET_h2s(key));
2284 /* I am the destination. */
2285 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2286 block_type,data_size,data);
2287 GDS_CLIENTS_process_put (options, block_type, 0,
2288 ntohl (desired_replication_level),
2289 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time.
2290 key, data, data_size);
2293 /* In case we are sending the request to a finger, then send across all of its
2295 #if ENABLE_MALICIOUS
2296 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2297 &successor.next_hop))
2299 struct FingerInfo *next_hop_finger;
2302 next_hop_finger = &finger_table[successor.finger_table_index];
2303 for (i = 0; i < next_hop_finger->trails_count; i++)
2305 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2307 if(0 == next_hop_finger->trail_list[i].trail_length)
2309 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2310 best_known_dest, intermediate_trail_id, &next_hop,
2311 0, 1, &my_identity, expiration_time,
2315 next_hop = next_hop_finger->trail_list[i].trail_head->peer;
2316 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2318 next_hop_finger->trail_list[i].trail_id,
2319 &next_hop, 0, 1, &my_identity,
2327 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2328 best_known_dest, intermediate_trail_id, &next_hop,
2329 0, 1, &my_identity, expiration_time,
2334 * Construct a Get message and send it to target_peer.
2335 * @param key Key for the content
2336 * @param block_type Type of the block
2337 * @param options Routing options
2338 * @param desired_replication_level Desired replication count
2339 * @param best_known_dest Peer which should get this message. Same as target peer
2340 * if best_known_dest is a friend else its a finger.
2341 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2342 * in case it is a finger else set to 0.
2343 * @param target_peer Peer to which this message will be forwarded.
2344 * @param hop_count Number of hops traversed so far.
2345 * @param data Content to store
2346 * @param data_size Size of content @a data in bytes
2347 * @param get_path_length Total number of peers in @a get_path
2348 * @param get_path Number of peers traversed so far
2351 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2352 enum GNUNET_BLOCK_Type block_type,
2353 enum GNUNET_DHT_RouteOption options,
2354 uint32_t desired_replication_level,
2355 struct GNUNET_PeerIdentity best_known_dest,
2356 struct GNUNET_HashCode intermediate_trail_id,
2357 struct GNUNET_PeerIdentity *target_peer,
2359 uint32_t get_path_length,
2360 struct GNUNET_PeerIdentity *get_path)
2362 struct PeerGetMessage *pgm;
2363 struct P2PPendingMessage *pending;
2364 struct FriendInfo *target_friend;
2365 struct GNUNET_PeerIdentity *gp;
2368 msize = sizeof (struct PeerGetMessage) +
2369 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2371 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2376 GNUNET_assert (NULL !=
2378 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2380 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2381 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2382 pending->importance = 0; /* FIXME */
2383 pgm = (struct PeerGetMessage *) &pending[1];
2384 pending->msg = &pgm->header;
2385 pgm->header.size = htons (msize);
2386 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2387 pgm->get_path_length = htonl (get_path_length);
2388 pgm->best_known_destination = best_known_dest;
2390 pgm->intermediate_trail_id = intermediate_trail_id;
2391 pgm->hop_count = htonl (hop_count + 1);
2392 pgm->get_path_length = htonl (get_path_length);
2393 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2394 memcpy (gp, get_path,
2395 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2396 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2397 target_friend->pending_count++;
2398 process_friend_queue (target_friend);
2403 * Handle the get request from the client file. If I am destination do
2404 * datacache put and return. Else find the target friend and forward message
2406 * @param key Key for the content
2407 * @param block_type Type of the block
2408 * @param options Routing options
2409 * @param desired_replication_level Desired replication count
2412 GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key,
2413 enum GNUNET_BLOCK_Type block_type,
2414 enum GNUNET_DHT_RouteOption options,
2415 uint32_t desired_replication_level)
2417 struct Closest_Peer successor;
2418 struct GNUNET_PeerIdentity best_known_dest;
2419 struct GNUNET_HashCode intermediate_trail_id;
2422 memcpy (&key_value, key, sizeof (uint64_t));
2423 key_value = GNUNET_ntohll (key_value);
2425 successor = find_local_best_known_next_hop (key_value,
2426 GDS_FINGER_TYPE_NON_PREDECESSOR);
2428 best_known_dest = successor.best_known_destination;
2429 intermediate_trail_id = successor.trail_id;
2431 /* I am the destination. I have the data. */
2432 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2435 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2436 NULL, 0, 1, &my_identity, NULL,&my_identity);
2440 #if ENABLE_MALICIOUS
2441 struct GNUNET_PeerIdentity next_hop;
2442 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2443 &successor.next_hop))
2445 struct FingerInfo *next_hop_finger;
2448 next_hop_finger = &finger_table[successor.finger_table_index];
2449 for (i = 0; i < next_hop_finger->trails_count; i++)
2451 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2453 if(0 == next_hop_finger->trail_list[i].trail_length)
2455 GDS_NEIGHBOURS_send_get (key, block_type, options,
2456 desired_replication_level,
2457 best_known_dest,intermediate_trail_id,
2458 &successor.next_hop,
2459 0, 1, &my_identity);
2462 next_hop = next_hop_finger->trail_list[i].trail_head->peer;
2463 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2465 next_hop_finger->trail_list[i].trail_id,
2466 &next_hop, 0, 1, &my_identity);
2472 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2473 best_known_dest,intermediate_trail_id, &successor.next_hop,
2474 0, 1, &my_identity);
2479 * Send the get result to requesting client.
2481 * @param key Key of the requested data.
2482 * @param type Block type
2483 * @param target_peer Next peer to forward the message to.
2484 * @param source_peer Peer which has the data for the key.
2485 * @param put_path_length Number of peers in @a put_path
2486 * @param put_path Path taken to put the data at its stored location.
2487 * @param get_path_length Number of peers in @a get_path
2488 * @param get_path Path taken to reach to the location of the key.
2489 * @param expiration When will this result expire?
2490 * @param data Payload to store
2491 * @param data_size Size of the @a data
2494 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2495 enum GNUNET_BLOCK_Type type,
2496 const struct GNUNET_PeerIdentity *target_peer,
2497 const struct GNUNET_PeerIdentity *source_peer,
2498 unsigned int put_path_length,
2499 const struct GNUNET_PeerIdentity *put_path,
2500 unsigned int get_path_length,
2501 const struct GNUNET_PeerIdentity *get_path,
2502 struct GNUNET_TIME_Absolute expiration,
2503 const void *data, size_t data_size)
2505 struct PeerGetResultMessage *get_result;
2506 struct GNUNET_PeerIdentity *paths;
2507 struct P2PPendingMessage *pending;
2508 struct FriendInfo *target_friend;
2509 int current_path_index;
2512 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2514 sizeof (struct PeerGetResultMessage);
2516 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2518 put_path_length = 0;
2519 msize = msize - put_path_length * sizeof (struct GNUNET_PeerIdentity);
2522 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2527 current_path_index = 0;
2528 if(get_path_length > 0)
2530 current_path_index = search_my_index(get_path, get_path_length);
2531 if (-1 == current_path_index)
2536 if ((get_path_length + 1) == current_path_index)
2538 DEBUG ("Peer found twice in get path. Not allowed \n");
2543 if (0 == current_path_index)
2545 DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",GNUNET_h2s(key),GNUNET_i2s(&my_identity));
2546 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2547 get_path, put_path_length,
2548 put_path, type, data_size, data);
2552 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2553 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2554 pending->importance = 0;
2555 get_result = (struct PeerGetResultMessage *)&pending[1];
2556 pending->msg = &get_result->header;
2557 get_result->header.size = htons (msize);
2558 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2559 get_result->key = *key;
2560 get_result->querying_peer = *source_peer;
2561 get_result->expiration_time = expiration;
2562 get_result->get_path_length = htonl (get_path_length);
2563 get_result->put_path_length = htonl (put_path_length);
2564 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2565 memcpy (paths, put_path,
2566 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2567 memcpy (&paths[put_path_length], get_path,
2568 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2569 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2571 GNUNET_assert (NULL !=
2573 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2574 &get_path[current_path_index - 1])));
2575 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2576 target_friend->pending_count++;
2577 process_friend_queue (target_friend);
2582 * Randomly choose one of your friends (which is not congested and have not crossed
2583 * trail threshold) from the friend_peermap
2584 * @return Friend Randomly chosen friend.
2585 * NULL in case friend peermap is empty, or all the friends are either
2586 * congested or have crossed trail threshold.
2588 static struct FriendInfo *
2589 select_random_friend ()
2591 unsigned int current_size;
2594 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2595 struct GNUNET_PeerIdentity key_ret;
2596 struct FriendInfo *friend;
2598 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2601 if (0 == current_size)
2604 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2605 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2607 /* Iterate till you don't reach to index. */
2608 for (j = 0; j < index ; j++)
2609 GNUNET_assert (GNUNET_YES ==
2610 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2614 /* Reset the index in friend peermap to 0 as we reached to the end. */
2615 if (j == current_size)
2618 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2619 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2623 /* Get the friend stored at the index, j*/
2624 GNUNET_assert (GNUNET_YES ==
2625 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2627 (const void **)&friend));
2629 /* This friend is not congested and has not crossed trail threshold. */
2630 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2631 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2637 } while (j != index);
2639 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2645 * Compute 64 bit value of finger_identity corresponding to a finger index using
2647 * For all fingers, n.finger[i] = n + pow (2,i),
2648 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2649 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2650 * @param finger_index Index corresponding to which we calculate 64 bit value.
2651 * @return 64 bit value.
2654 compute_finger_identity_value (unsigned int finger_index)
2658 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2659 my_id64 = GNUNET_ntohll (my_id64);
2661 /* Are we looking for immediate predecessor? */
2662 if (PREDECESSOR_FINGER_ID == finger_index)
2663 return (my_id64 - 1);
2666 uint64_t add = (uint64_t)1 << finger_index;
2667 return (my_id64 + add);
2673 * Choose a random friend. Calculate the next finger identity to search,from
2674 * current_search_finger_index. Start looking for the trail to reach to
2675 * finger identity through this random friend.
2677 * @param cls closure for this task
2678 * @param tc the context under which the task is running
2681 send_find_finger_trail_message (void *cls,
2682 const struct GNUNET_SCHEDULER_TaskContext *tc)
2684 struct FriendInfo *target_friend;
2685 struct GNUNET_HashCode trail_id;
2686 struct GNUNET_HashCode intermediate_trail_id;
2687 unsigned int is_predecessor = 0;
2688 uint64_t finger_id_value;
2690 /* Schedule another send_find_finger_trail_message task. After one round of
2691 * finger search, this time is exponentially backoff. */
2692 find_finger_trail_task_next_send_time.rel_value_us =
2693 find_finger_trail_task_next_send_time.rel_value_us +
2694 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2695 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2696 find_finger_trail_task =
2697 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2698 &send_find_finger_trail_message,
2701 /* No space in my routing table. (Source and destination peers also store entries
2702 * in their routing table). */
2703 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2706 target_friend = select_random_friend ();
2707 if (NULL == target_friend)
2712 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2713 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2716 /* Generate a unique trail id for trail we are trying to setup. */
2717 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2718 &trail_id, sizeof (trail_id));
2719 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2720 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2721 target_friend->id, target_friend, 0, NULL,
2722 is_predecessor, trail_id,
2723 intermediate_trail_id);
2728 * In case there are already maximum number of possible trails to reach to a
2729 * finger, then check if the new trail's length is lesser than any of the
2731 * If yes then replace that old trail by new trail.
2733 * Note: Here we are taking length as a parameter to choose the best possible
2734 * trail, but there could be other parameters also like:
2735 * 1. duration of existence of a trail - older the better.
2736 * 2. if the new trail is completely disjoint than the
2737 * other trails, then may be choosing it is better.
2739 * @param finger Finger
2740 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2741 * including the endpoints.
2742 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2743 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2746 select_and_replace_trail (struct FingerInfo *finger,
2747 const struct GNUNET_PeerIdentity *new_trail,
2748 unsigned int new_trail_length,
2749 struct GNUNET_HashCode new_trail_id)
2751 struct Trail *current_trail;
2752 unsigned int largest_trail_length;
2753 unsigned int largest_trail_index;
2754 struct Trail_Element *trail_element;
2755 struct GNUNET_PeerIdentity *next_hop;
2758 largest_trail_length = new_trail_length;
2759 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2761 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2763 for (i = 0; i < finger->trails_count; i++)
2765 current_trail = &finger->trail_list[i];
2766 GNUNET_assert (GNUNET_YES == current_trail->is_present);
2767 if (current_trail->trail_length > largest_trail_length)
2769 largest_trail_length = current_trail->trail_length;
2770 largest_trail_index = i;
2774 /* New trail is not better than existing ones. Send trail teardown. */
2775 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2777 next_hop = GDS_ROUTING_get_next_hop (new_trail_id, GDS_ROUTING_SRC_TO_DEST);
2778 GDS_ROUTING_remove_trail (new_trail_id);
2779 GDS_NEIGHBOURS_send_trail_teardown (&new_trail_id,
2780 GDS_ROUTING_SRC_TO_DEST,
2785 /* Send trail teardown message across the replaced trail. */
2786 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2787 next_hop = GDS_ROUTING_get_next_hop (replace_trail->trail_id, GDS_ROUTING_SRC_TO_DEST);
2788 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2789 GDS_NEIGHBOURS_send_trail_teardown (&replace_trail->trail_id,
2790 GDS_ROUTING_SRC_TO_DEST,
2793 /* Free the trail. */
2794 while (NULL != (trail_element = replace_trail->trail_head))
2796 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2797 replace_trail->trail_tail, trail_element);
2798 GNUNET_free_non_null (trail_element);
2801 /* Add new trial at that location. */
2802 replace_trail->is_present = GNUNET_YES;
2803 replace_trail->trail_length = new_trail_length;
2804 replace_trail->trail_id = new_trail_id;
2806 for (i = 0; i < new_trail_length; i++)
2808 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2809 element->peer = new_trail[i];
2811 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2812 replace_trail->trail_tail,
2815 /* FIXME: URGENT Are we adding the trail back to the list. */
2820 * Check if the new trail to reach to finger is unique or do we already have
2821 * such a trail present for finger.
2822 * @param existing_finger Finger identity
2823 * @param new_trail New trail to reach @a existing_finger
2824 * @param trail_length Total number of peers in new_trail.
2825 * @return #GNUNET_YES if the new trail is unique
2826 * #GNUNET_NO if same trail is already present.
2829 is_new_trail_unique (struct FingerInfo *existing_finger,
2830 const struct GNUNET_PeerIdentity *new_trail,
2831 unsigned int trail_length)
2833 struct Trail *current_trail;
2834 struct Trail_Element *trail_element;
2838 GNUNET_assert (existing_finger->trails_count > 0);
2840 /* Iterate over list of trails. */
2841 for (i = 0; i < existing_finger->trails_count; i++)
2843 current_trail = &(existing_finger->trail_list[i]);
2844 if(GNUNET_NO == current_trail->is_present)
2847 /* New trail and existing trail length are not same. */
2848 if (current_trail->trail_length != trail_length)
2853 trail_element = current_trail->trail_head;
2854 for (j = 0; j < current_trail->trail_length; j++)
2856 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2857 &trail_element->peer))
2861 trail_element = trail_element->next;
2868 * FIXME; In case of multiple trails, we may have a case where a trail from in
2869 * between has been removed, then we should try to find a free slot , not simply
2870 * add a trail at then end of the list.
2871 * Add a new trail at a free slot in trail array of existing finger.
2872 * @param existing_finger Finger
2873 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2874 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2875 * @param new_finger_trail_id Unique identifier of the trail.
2878 add_new_trail (struct FingerInfo *existing_finger,
2879 const struct GNUNET_PeerIdentity *new_trail,
2880 unsigned int new_trail_length,
2881 struct GNUNET_HashCode new_trail_id)
2883 struct FriendInfo *friend;
2884 struct Trail *trail;
2888 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2892 for (i = 0; i < existing_finger->trails_count; i++)
2894 if (GNUNET_NO == existing_finger->trail_list[i].is_present)
2901 if (-1 == free_slot)
2904 trail = &existing_finger->trail_list[free_slot];
2905 GNUNET_assert (GNUNET_NO == trail->is_present);
2906 trail->trail_id = new_trail_id;
2907 trail->trail_length = new_trail_length;
2908 existing_finger->trails_count++;
2909 trail->is_present = GNUNET_YES;
2910 if (0 == new_trail_length)
2912 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2913 &existing_finger->finger_identity);
2917 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2920 GNUNET_assert (NULL != friend);
2921 friend->trails_count++;
2922 for (i = 0; i < new_trail_length; i++)
2924 struct Trail_Element *element;
2926 element = GNUNET_new (struct Trail_Element);
2927 element->peer = new_trail[i];
2928 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2933 existing_finger->trail_list[free_slot].trail_head = trail->trail_head;
2934 existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail;
2935 existing_finger->trail_list[free_slot].trail_length = new_trail_length;
2936 existing_finger->trail_list[free_slot].trail_id = new_trail_id;
2937 existing_finger->trail_list[free_slot].is_present = GNUNET_YES;
2943 * FIXME; In case of multiple trails, we may have a case where a trail from in
2944 * between has been removed, then we should try to find a free slot , not simply
2945 * add a trail at then end of the list.
2946 * Add a new trail at a free slot in trail array of existing finger.
2947 * @param existing_finger Finger
2948 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2949 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2950 * @param new_finger_trail_id Unique identifier of the trail.
2953 add_new_trail (struct FingerInfo *existing_finger,
2954 const struct GNUNET_PeerIdentity *new_trail,
2955 unsigned int new_trail_length,
2956 struct GNUNET_HashCode new_trail_id)
2958 struct Trail *trail;
2959 struct FriendInfo *first_friend;
2963 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2967 index = existing_finger->trails_count;
2968 trail = &existing_finger->trail_list[index];
2969 GNUNET_assert (GNUNET_NO == trail->is_present);
2970 trail->trail_id = new_trail_id;
2971 trail->trail_length = new_trail_length;
2972 existing_finger->trails_count++;
2973 trail->is_present = GNUNET_YES;
2975 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2976 &existing_finger->finger_identity)));
2977 /* If finger is a friend then we never call this function. */
2978 GNUNET_assert (new_trail_length > 0);
2980 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2982 first_friend->trails_count++;
2984 for (i = 0; i < new_trail_length; i++)
2986 struct Trail_Element *element;
2988 element = GNUNET_new (struct Trail_Element);
2989 element->peer = new_trail[i];
2990 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2994 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2995 existing_finger->trail_list[index].trail_head = trail->trail_head;
2996 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2997 existing_finger->trail_list[index].trail_length = new_trail_length;
2998 existing_finger->trail_list[index].trail_id = new_trail_id;
2999 existing_finger->trail_list[index].is_present = GNUNET_YES;
3004 * Get the next hop to send trail teardown message from routing table and
3005 * then delete the entry from routing table. Send trail teardown message for a
3006 * specific trail of a finger.
3007 * @param finger Finger whose trail is to be removed.
3008 * @param trail List of peers in trail from me to a finger, NOT including
3012 send_trail_teardown (struct FingerInfo *finger,
3013 struct Trail *trail)
3015 struct FriendInfo *friend;
3016 struct GNUNET_PeerIdentity *next_hop;
3018 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
3019 GDS_ROUTING_SRC_TO_DEST);
3020 if (NULL == next_hop)
3022 // DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d",
3023 // GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length);
3026 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3029 GNUNET_assert(GNUNET_YES == trail->is_present);
3030 if (trail->trail_length > 0)
3032 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3033 &trail->trail_head->peer);
3037 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3038 &finger->finger_identity);
3043 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
3044 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
3047 if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)
3048 && (0 == trail->trail_length))
3050 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
3051 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
3054 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
3055 friend->trails_count--;
3056 GDS_NEIGHBOURS_send_trail_teardown (&trail->trail_id,
3057 GDS_ROUTING_SRC_TO_DEST,
3063 * Send trail teardown message across all the trails to reach to finger.
3064 * @param finger Finger whose all the trail should be freed.
3067 send_all_finger_trails_teardown (struct FingerInfo *finger)
3071 for (i = 0; i < finger->trails_count; i++)
3073 struct Trail *trail;
3075 trail = &finger->trail_list[i];
3076 if (GNUNET_YES == trail->is_present)
3078 send_trail_teardown (finger, trail);
3079 trail->is_present = GNUNET_NO;
3086 * Free a specific trail
3087 * @param trail List of peers to be freed.
3090 free_trail (struct Trail *trail)
3092 struct Trail_Element *trail_element;
3094 while (NULL != (trail_element = trail->trail_head))
3096 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
3099 GNUNET_free_non_null (trail_element);
3101 trail->trail_head = NULL;
3102 trail->trail_tail = NULL;
3107 * Free finger and its trail.
3108 * @param finger Finger to be freed.
3109 * @param finger_table_index Index at which finger is stored.
3112 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
3114 struct Trail *trail;
3116 for (i = 0; i < finger->trails_count; i++)
3118 trail = &finger->trail_list[i];
3119 if (GNUNET_NO == trail->is_present)
3122 if (trail->trail_length > 0)
3124 trail->is_present = GNUNET_NO;
3127 finger->is_present = GNUNET_NO;
3128 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
3133 * Add a new entry in finger table at finger_table_index.
3134 * In case I am my own finger, then we don't have a trail. In case of a friend,
3135 * we have a trail with unique id and '0' trail length.
3136 * In case a finger is a friend, then increment the trails count of the friend.
3137 * @param finger_identity Peer Identity of new finger
3138 * @param finger_trail Trail to reach from me to finger (excluding both end points).
3139 * @param finger_trail_length Total number of peers in @a finger_trail.
3140 * @param trail_id Unique identifier of the trail.
3141 * @param finger_table_index Index in finger table.
3144 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
3145 const struct GNUNET_PeerIdentity *finger_trail,
3146 unsigned int finger_trail_length,
3147 struct GNUNET_HashCode trail_id,
3148 unsigned int finger_table_index)
3150 struct FingerInfo *new_entry;
3151 struct FriendInfo *first_trail_hop;
3152 struct Trail *trail;
3155 new_entry = GNUNET_new (struct FingerInfo);
3156 new_entry->finger_identity = finger_identity;
3157 new_entry->finger_table_index = finger_table_index;
3158 new_entry->is_present = GNUNET_YES;
3160 /* If the new entry is my own identity. */
3161 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3164 new_entry->trails_count = 0;
3165 finger_table[finger_table_index] = *new_entry;
3166 GNUNET_free (new_entry);
3170 /* Finger is a friend. */
3171 if (0 == finger_trail_length)
3173 new_entry->trail_list[0].trail_id = trail_id;
3174 new_entry->trails_count = 1;
3175 new_entry->trail_list[0].is_present = GNUNET_YES;
3176 new_entry->trail_list[0].trail_length = 0;
3177 new_entry->trail_list[0].trail_head = NULL;
3178 new_entry->trail_list[0].trail_tail = NULL;
3179 finger_table[finger_table_index] = *new_entry;
3180 GNUNET_assert (NULL !=
3182 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3183 &finger_identity)));
3185 first_trail_hop->trails_count++;
3186 GNUNET_free (new_entry);
3190 GNUNET_assert (NULL !=
3192 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3193 &finger_trail[0])));
3194 new_entry->trails_count = 1;
3195 first_trail_hop->trails_count++;
3196 /* Copy the finger trail into trail. */
3197 trail = &new_entry->trail_list[0];
3198 for(i = 0; i < finger_trail_length; i++)
3200 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3202 element->next = NULL;
3203 element->prev = NULL;
3204 element->peer = finger_trail[i];
3205 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3210 /* Add trail to trail list. */
3211 trail->trail_length = finger_trail_length;
3212 trail->trail_id = trail_id;
3213 trail->is_present = GNUNET_YES;
3214 finger_table[finger_table_index] = *new_entry;
3215 GNUNET_free (new_entry);
3220 * Periodic task to verify current successor. There can be multiple trails to reach
3221 * to successor, choose the shortest one and send verify successor message
3222 * across that trail.
3223 * @param cls closure for this task
3224 * @param tc the context under which the task is running
3227 send_verify_successor_message (void *cls,
3228 const struct GNUNET_SCHEDULER_TaskContext *tc)
3230 struct FriendInfo *target_friend;
3231 struct GNUNET_HashCode trail_id;
3232 struct Trail *trail;
3233 struct Trail_Element *element;
3234 unsigned int trail_length;
3236 struct FingerInfo *successor;
3238 successor = &finger_table[0];
3240 /* This task will be scheduled when the result for Verify Successor is received. */
3241 send_verify_successor_task = NULL;
3243 /* When verify successor is being called for first time *for current context*
3244 * cls will be NULL. If send_verify_successor_retry_task is not NO_TASK, we
3245 * must cancel the retry task scheduled for verify_successor of previous
3250 /* FIXME: Here we are scheduling a new verify successor task, as we
3251 got a new successor. But a send verify successor task may be in progress.
3252 1. We need to be sure that this is indeed a new successor. As this function
3253 is called even if we add a new trail to reach t old successor.
3254 2. Assuming the new successor is different, then verify successor message
3255 * to old successor may be following stages.
3256 * --> Waiting for verify successor result. Don't wait anymore. there is
3257 * no trail to reach from old successor to me, hence, routing
3259 * --> Waiting for notify confirmation. again don't wait for it. notify
3260 * confirmation will not succeded.
3262 if (send_verify_successor_retry_task != NULL)
3264 /* FIXME: Are we scheduling retry task as soon as we send verify message.
3265 If yes then here before making this task, first check if the message
3266 is for the same peer again. */
3267 struct VerifySuccessorContext *old_ctx =
3268 GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
3269 /* old_ctx must not be NULL, as the retry task had been scheduled */
3270 GNUNET_assert(NULL != old_ctx);
3271 GNUNET_free(old_ctx);
3272 /* FIXME: Why don't we reset the task to NO_TASK here? */
3275 struct VerifySuccessorContext *ctx;
3276 ctx = GNUNET_new(struct VerifySuccessorContext);
3278 ctx->num_retries_scheduled++;
3279 send_verify_successor_retry_task =
3280 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3281 &send_verify_successor_message,
3286 /* This is a retry attempt for verify_successor for a previous context */
3287 struct VerifySuccessorContext *ctx;
3290 ctx->num_retries_scheduled++;
3291 send_verify_successor_retry_task =
3292 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3293 &send_verify_successor_message,
3297 /* Among all the trails to reach to successor, select first one which is present.*/
3298 for (i = 0; i < successor->trails_count; i++)
3300 trail = &successor->trail_list[i];
3301 if(GNUNET_YES == trail->is_present)
3305 /* No valid trail found to reach to successor. */
3306 if (i == successor->trails_count)
3309 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3310 &successor->finger_identity));
3311 /* Trail stored at this index. */
3312 GNUNET_assert (GNUNET_YES == trail->is_present);
3313 trail_id = trail->trail_id;
3314 if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST))
3316 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3317 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
3321 trail_length = trail->trail_length;
3322 if (trail_length > 0)
3324 /* Copy the trail into peer list. */
3325 struct GNUNET_PeerIdentity peer_list[trail_length];
3326 element = trail->trail_head;
3327 for(i = 0; i < trail_length; i++)
3329 peer_list[i] = element->peer;
3330 element = element->next;
3332 GNUNET_assert (NULL != (target_friend =
3333 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3335 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3336 successor->finger_identity,
3337 trail_id, peer_list, trail_length,
3342 GNUNET_assert (NULL != (target_friend =
3343 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3344 &successor->finger_identity)));
3345 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3346 successor->finger_identity,
3354 * FIXME: should this be a periodic task, incrementing the search finger index?
3355 * Update the current search finger index.
3356 * @a finger_identity
3357 * @a finger_table_index
3360 update_current_search_finger_index (unsigned int finger_table_index)
3362 struct FingerInfo *successor;
3364 /* FIXME correct this: only move current index periodically */
3365 if (finger_table_index != current_search_finger_index)
3368 successor = &finger_table[0];
3369 GNUNET_assert (GNUNET_YES == successor->is_present);
3371 /* We were looking for immediate successor. */
3372 if (0 == current_search_finger_index)
3374 current_search_finger_index = PREDECESSOR_FINGER_ID;
3375 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &successor->finger_identity))
3377 if (NULL == send_verify_successor_task)
3379 send_verify_successor_task =
3380 GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3386 current_search_finger_index = current_search_finger_index - 1;
3392 * Get the least significant bit set in val.
3395 * @return Position of first bit set, 65 in case of error.
3398 find_set_bit (uint64_t val)
3418 return 65; /* Some other bit was set to 1 as well. */
3425 * Calculate finger_table_index from initial 64 bit finger identity value that
3426 * we send in trail setup message.
3427 * @param ultimate_destination_finger_value Value that we calculated from our
3428 * identity and finger_table_index.
3429 * @param is_predecessor Is the entry for predecessor or not?
3430 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3431 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3434 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3435 unsigned int is_predecessor)
3439 unsigned int finger_table_index;
3441 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3442 my_id64 = GNUNET_ntohll (my_id64);
3444 /* Is this a predecessor finger? */
3445 if (1 == is_predecessor)
3447 diff = my_id64 - ultimate_destination_finger_value;
3449 finger_table_index = PREDECESSOR_FINGER_ID;
3451 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3456 diff = ultimate_destination_finger_value - my_id64;
3457 finger_table_index = find_set_bit (diff);
3459 return finger_table_index;
3464 * Remove finger and its associated data structures from finger table.
3465 * @param existing_finger Finger to be removed which is in finger table.
3466 * @param finger_table_index Index in finger table where @a existing_finger
3470 remove_existing_finger (struct FingerInfo *existing_finger,
3471 unsigned int finger_table_index)
3473 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3475 /* If I am my own finger, then we have no trails. */
3476 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3479 existing_finger->is_present = GNUNET_NO;
3480 memset ((void *)&finger_table[finger_table_index], 0,
3481 sizeof (finger_table[finger_table_index]));
3485 /* For all other fingers, send trail teardown across all the trails to reach
3486 finger, and free the finger. */
3487 send_all_finger_trails_teardown (existing_finger);
3488 free_finger (existing_finger, finger_table_index);
3493 * Check if there is already an entry in finger_table at finger_table_index.
3494 * We get the finger_table_index from 64bit finger value we got from the network.
3495 * -- If yes, then select the closest finger.
3496 * -- If new and existing finger are same, then check if you can store more
3498 * -- If yes then add trail, else keep the best trails to reach to the
3500 * -- If the new finger is closest, remove the existing entry, send trail
3501 * teardown message across all the trails to reach the existing entry.
3502 * Add the new finger.
3503 * -- If new and existing finger are different, and existing finger is closest
3505 * -- Update current_search_finger_index.
3506 * @param finger_identity Peer Identity of new finger
3507 * @param finger_trail Trail to reach the new finger
3508 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3509 * @param is_predecessor Is this entry for predecessor in finger_table?
3510 * @param finger_value 64 bit value of finger identity that we got from network.
3511 * @param finger_trail_id Unique identifier of @finger_trail.
3514 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3515 const struct GNUNET_PeerIdentity *finger_trail,
3516 unsigned int finger_trail_length,
3517 unsigned int is_predecessor,
3518 uint64_t finger_value,
3519 struct GNUNET_HashCode finger_trail_id)
3521 struct FingerInfo *existing_finger;
3522 struct GNUNET_PeerIdentity closest_peer;
3523 struct FingerInfo *successor;
3524 unsigned int finger_table_index;
3526 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3527 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3529 /* Invalid finger_table_index. */
3530 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3532 GNUNET_break_op (0);
3536 /* Check if new entry is same as successor. */
3537 if ((0 != finger_table_index) &&
3538 (PREDECESSOR_FINGER_ID != finger_table_index))
3540 successor = &finger_table[0];
3541 if (GNUNET_NO == successor->is_present)
3543 GNUNET_break (0); //ASSERTION FAILS HERE. FIXME
3546 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3547 &successor->finger_identity))
3549 if (0 == fingers_round_count)
3551 find_finger_trail_task_next_send_time =
3552 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3555 fingers_round_count--;
3556 current_search_finger_index = 0;
3557 GNUNET_STATISTICS_update (GDS_stats,
3559 ("# FINGERS_COUNT"), (int64_t) total_fingers_found,
3561 total_fingers_found = 0;
3565 struct FingerInfo prev_finger;
3566 prev_finger = finger_table[finger_table_index - 1];
3567 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3568 &prev_finger.finger_identity))
3570 current_search_finger_index--;
3575 total_fingers_found++;
3576 existing_finger = &finger_table[finger_table_index];
3578 /* No entry present in finger_table for given finger map index. */
3579 if (GNUNET_NO == existing_finger->is_present)
3581 /* Shorten the trail if possible. */
3582 add_new_finger (finger_identity, finger_trail,
3583 finger_trail_length,
3584 finger_trail_id, finger_table_index);
3585 update_current_search_finger_index (finger_table_index);
3589 /* If existing entry and finger identity are not same. */
3590 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3593 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3598 /* If the new finger is the closest peer. */
3599 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer))
3601 remove_existing_finger (existing_finger, finger_table_index);
3602 add_new_finger (finger_identity, finger_trail, finger_trail_length,
3603 finger_trail_id, finger_table_index);
3607 /* Existing finger is the closest one. We need to send trail teardown
3608 across the trail setup in routing table of all the peers. */
3609 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3611 if (finger_trail_length > 0)
3612 GDS_NEIGHBOURS_send_trail_teardown (&finger_trail_id,
3613 GDS_ROUTING_SRC_TO_DEST,
3616 GDS_NEIGHBOURS_send_trail_teardown (&finger_trail_id,
3617 GDS_ROUTING_SRC_TO_DEST,
3624 /* If both new and existing entry are same as my_identity, then do nothing. */
3625 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3631 /* If there is space to store more trails. */
3632 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3633 add_new_trail (existing_finger, finger_trail,
3634 finger_trail_length, finger_trail_id);
3636 select_and_replace_trail (existing_finger, finger_trail,
3637 finger_trail_length, finger_trail_id);
3639 update_current_search_finger_index (finger_table_index);
3645 * Core handler for P2P put messages.
3646 * @param cls closure
3647 * @param peer sender of the request
3648 * @param message message
3649 * @return #GNUNET_OK to keep the connection open,
3650 * #GNUNET_SYSERR to close it (signal serious error)
3653 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3654 const struct GNUNET_MessageHeader *message)
3656 struct PeerPutMessage *put;
3657 struct GNUNET_PeerIdentity *put_path;
3658 struct GNUNET_PeerIdentity current_best_known_dest;
3659 struct GNUNET_PeerIdentity best_known_dest;
3660 struct GNUNET_HashCode received_intermediate_trail_id;
3661 struct GNUNET_HashCode intermediate_trail_id;
3662 struct GNUNET_PeerIdentity next_hop;
3663 struct GNUNET_PeerIdentity *next_routing_hop;
3664 enum GNUNET_DHT_RouteOption options;
3665 struct GNUNET_HashCode test_key;
3670 size_t payload_size;
3673 msize = ntohs (message->size);
3674 if (msize < sizeof (struct PeerPutMessage))
3676 GNUNET_break_op (0);
3680 put = (struct PeerPutMessage *) message;
3681 putlen = ntohl (put->put_path_length);
3683 sizeof (struct PeerPutMessage) +
3684 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3686 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3688 GNUNET_break_op (0);
3691 #if ENABLE_MALICIOUS
3692 if(1 == act_malicious)
3694 DEBUG("\n I AM MALICIOUS PUT_REQUEST_DROPPED for key = %ss",GNUNET_h2s(&put->key));
3698 GNUNET_STATISTICS_update (GDS_stats,
3700 ("# Bytes received from other peers"), (int64_t) msize,
3703 current_best_known_dest = put->best_known_destination;
3704 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3705 payload = &put_path[putlen];
3706 options = ntohl (put->options);
3707 received_intermediate_trail_id = put->intermediate_trail_id;
3708 hop_count = ntohl(put->hop_count);
3709 payload_size = msize - (sizeof (struct PeerPutMessage) +
3710 putlen * sizeof (struct GNUNET_PeerIdentity));
3712 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3713 payload, payload_size, &test_key))
3716 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3718 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3719 GNUNET_break_op (0);
3720 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3721 "PUT with key `%s' for block with key %s\n",
3722 put_s, GNUNET_h2s_full (&test_key));
3723 GNUNET_free (put_s);
3728 GNUNET_break_op (0);
3731 /* cannot verify, good luck */
3735 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3737 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3738 ntohl (put->block_type),
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 (get_result->expiration_time, &(get_result->key),
4101 getlen, get_path, putlen,
4102 put_path, get_result->type, payload_size, payload);
4107 current_path_index = search_my_index (get_path, getlen);
4108 if (-1 == current_path_index )
4110 DEBUG ("No entry found in get path.\n");
4112 return GNUNET_SYSERR;
4114 if((getlen + 1) == current_path_index)
4116 DEBUG("Present twice in get path. Not allowed. \n");
4118 return GNUNET_SYSERR;
4120 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
4121 &get_path[current_path_index - 1],
4122 &(get_result->querying_peer), putlen, put_path,
4123 getlen, get_path, get_result->expiration_time,
4124 payload, payload_size);
4127 return GNUNET_SYSERR;
4132 * Find the next hop to pass trail setup message. First find the local best known
4133 * hop from your own identity, friends and finger. If you were part of trail,
4134 * then get the next hop from routing table. Compare next_hop from routing table
4135 * and local best known hop, and return the closest one to final_dest_finger_val
4136 * @param final_dest_finger_val 64 bit value of finger identity
4137 * @param intermediate_trail_id If you are part of trail to reach to some other
4138 * finger, then it is the trail id to reach to
4139 * that finger, else set to 0.
4140 * @param is_predecessor Are we looking for closest successor or predecessor.
4141 * @param source Source of trail setup message.
4142 * @param current_dest In case you are part of trail, then finger to which
4143 * we should forward the message. Else my own identity
4144 * @return Closest Peer for @a final_dest_finger_val
4146 static struct Closest_Peer
4147 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
4148 struct GNUNET_HashCode intermediate_trail_id,
4149 unsigned int is_predecessor,
4150 struct GNUNET_PeerIdentity source,
4151 struct GNUNET_PeerIdentity *current_dest)
4153 struct Closest_Peer peer;
4155 peer = find_local_best_known_next_hop (final_dest_finger_val, is_predecessor);
4157 /* Am I just a part of a trail towards a finger (current_destination)? */
4158 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
4159 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
4162 struct GNUNET_PeerIdentity closest_peer;
4164 /* Select best successor among one found locally and current_destination
4165 * that we got from network.*/
4166 closest_peer = select_closest_peer (&peer.best_known_destination,
4168 final_dest_finger_val,
4171 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
4172 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
4174 struct GNUNET_PeerIdentity *next_hop;
4176 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4177 GDS_ROUTING_SRC_TO_DEST);
4178 /* next_hop NULL is a valid case. This intermediate trail id is set by
4179 some other finger, and while this trail setup is in progress, that other
4180 peer might have found a better trail ,and send trail teardown message
4181 across the network. In case we got the trail teardown message first,
4182 then next_hop will be NULL. A possible solution could be to keep track
4183 * of all removed trail id, and be sure that there is no other reason . */
4184 if(NULL != next_hop)
4186 peer.next_hop = *next_hop;
4187 peer.best_known_destination = *current_dest;
4188 peer.trail_id = intermediate_trail_id;
4197 * Core handle for PeerTrailSetupMessage.
4198 * @param cls closure
4199 * @param message message
4200 * @param peer peer identity this notification is about
4201 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4204 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
4205 const struct GNUNET_MessageHeader *message)
4207 const struct PeerTrailSetupMessage *trail_setup;
4208 const struct GNUNET_PeerIdentity *trail_peer_list;
4209 struct GNUNET_PeerIdentity current_dest;
4210 struct FriendInfo *target_friend;
4211 struct GNUNET_PeerIdentity source;
4212 struct GNUNET_HashCode intermediate_trail_id;
4213 struct GNUNET_HashCode trail_id;
4214 unsigned int is_predecessor;
4215 uint32_t trail_length;
4216 uint64_t final_dest_finger_val;
4220 msize = ntohs (message->size);
4221 if (msize < sizeof (struct PeerTrailSetupMessage))
4223 GNUNET_break_op (0);
4224 return GNUNET_SYSERR;
4227 trail_setup = (const struct PeerTrailSetupMessage *) message;
4228 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4229 sizeof (struct GNUNET_PeerIdentity) != 0)
4231 GNUNET_break_op (0);
4234 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4235 sizeof (struct GNUNET_PeerIdentity);
4237 GNUNET_STATISTICS_update (GDS_stats,
4239 ("# Bytes received from other peers"), msize,
4242 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4243 current_dest = trail_setup->best_known_destination;
4244 trail_id = trail_setup->trail_id;
4245 final_dest_finger_val =
4246 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4247 source = trail_setup->source_peer;
4248 is_predecessor = ntohl (trail_setup->is_predecessor);
4249 intermediate_trail_id = trail_setup->intermediate_trail_id;
4251 /* Did the friend insert its ID in the trail list? */
4252 if (trail_length > 0 &&
4253 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
4255 GNUNET_break_op (0);
4256 return GNUNET_SYSERR;
4259 /* If I was the source and got the message back, then set trail length to 0.*/
4260 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4265 /* Check if you are present in the trail seen so far? */
4266 for (i = 0; i < trail_length ; i++)
4268 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4270 /* We will add ourself later in code, if NOT destination. */
4276 /* Is my routing table full? */
4277 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4279 if (trail_length > 0)
4281 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4282 &trail_peer_list[trail_length - 1]);
4285 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4287 if(NULL == target_friend)
4289 DEBUG ("\n friend not found");
4293 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4294 my_identity, is_predecessor,
4295 trail_peer_list, trail_length,
4296 trail_id, target_friend,
4297 CONGESTION_TIMEOUT);
4301 /* Get the next hop to forward the trail setup request. */
4302 struct Closest_Peer next_peer =
4303 get_local_best_known_next_hop (final_dest_finger_val,
4304 intermediate_trail_id,
4309 /* Am I the final destination? */
4310 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4313 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4315 finger_table_add (my_identity, NULL, 0, is_predecessor,
4316 final_dest_finger_val, trail_id);
4320 if (trail_length > 0)
4322 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4323 &trail_peer_list[trail_length-1]);
4326 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4327 if (NULL == target_friend)
4329 GNUNET_break_op (0);
4330 return GNUNET_SYSERR;
4332 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4333 GDS_NEIGHBOURS_send_trail_setup_result (source,
4335 target_friend, trail_length,
4338 final_dest_finger_val,trail_id);
4340 else /* I'm not the final destination. */
4342 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4343 &next_peer.next_hop);
4344 if(NULL == target_friend)
4346 DEBUG ("\n target friend not found for peer = %s", GNUNET_i2s(&next_peer.next_hop));
4350 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4352 /* Add yourself to list of peers. */
4353 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4355 memcpy (peer_list, trail_peer_list,
4356 trail_length * sizeof (struct GNUNET_PeerIdentity));
4357 peer_list[trail_length] = my_identity;
4358 GDS_NEIGHBOURS_send_trail_setup (source,
4359 final_dest_finger_val,
4360 next_peer.best_known_destination,
4361 target_friend, trail_length + 1, peer_list,
4362 is_predecessor, trail_id,
4363 next_peer.trail_id);
4366 GDS_NEIGHBOURS_send_trail_setup (source,
4367 final_dest_finger_val,
4368 next_peer.best_known_destination,
4369 target_friend, 0, NULL,
4370 is_predecessor, trail_id,
4371 next_peer.trail_id);
4378 * Core handle for p2p trail setup result messages.
4380 * @param message message
4381 * @param peer sender of this message.
4382 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4385 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4386 const struct GNUNET_MessageHeader *message)
4388 const struct PeerTrailSetupResultMessage *trail_result;
4389 const struct GNUNET_PeerIdentity *trail_peer_list;
4390 struct GNUNET_PeerIdentity next_hop;
4391 struct FriendInfo *target_friend;
4392 struct GNUNET_PeerIdentity querying_peer;
4393 struct GNUNET_PeerIdentity finger_identity;
4394 uint32_t trail_length;
4395 uint64_t ulitmate_destination_finger_value;
4396 uint32_t is_predecessor;
4397 struct GNUNET_HashCode trail_id;
4401 msize = ntohs (message->size);
4402 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4404 GNUNET_break_op (0);
4408 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4409 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4410 sizeof (struct GNUNET_PeerIdentity) != 0)
4412 GNUNET_break_op (0);
4415 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4416 sizeof (struct GNUNET_PeerIdentity);
4418 GNUNET_STATISTICS_update (GDS_stats,
4420 ("# Bytes received from other peers"), msize,
4423 is_predecessor = ntohl (trail_result->is_predecessor);
4424 querying_peer = trail_result->querying_peer;
4425 finger_identity = trail_result->finger_identity;
4426 trail_id = trail_result->trail_id;
4427 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4428 ulitmate_destination_finger_value =
4429 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4431 /* Am I the one who initiated the query? */
4432 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4434 /* Check that you got the message from the correct peer. */
4435 if (trail_length > 0)
4437 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4442 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4445 GDS_ROUTING_add (trail_id, my_identity, *peer);
4446 finger_table_add (finger_identity, trail_peer_list, trail_length,
4447 is_predecessor, ulitmate_destination_finger_value, trail_id);
4451 /* Get my location in the trail. */
4452 my_index = search_my_index (trail_peer_list, trail_length);
4455 DEBUG ("Not found in trail\n");
4457 return GNUNET_SYSERR;
4460 if ((trail_length + 1) == my_index)
4462 DEBUG ("Found twice in trail.\n");
4464 return GNUNET_SYSERR;
4467 //TODO; Refactor code here and above to check if sender peer is correct
4470 if(trail_length > 1)
4471 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4474 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4476 next_hop = trail_result->querying_peer;
4480 if(my_index == trail_length - 1)
4483 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4488 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4490 next_hop = trail_peer_list[my_index - 1];
4493 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4494 if (NULL == target_friend)
4496 GNUNET_break_op (0);
4497 return GNUNET_SYSERR;
4499 GDS_ROUTING_add (trail_id, next_hop, *peer);
4500 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4501 target_friend, trail_length, trail_peer_list,
4503 ulitmate_destination_finger_value,
4511 * @param trail Trail to be inverted
4512 * @param trail_length Total number of peers in the trail.
4513 * @return Updated trail
4515 static struct GNUNET_PeerIdentity *
4516 invert_trail (const struct GNUNET_PeerIdentity *trail,
4517 unsigned int trail_length)
4521 struct GNUNET_PeerIdentity *inverted_trail;
4523 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4526 j = trail_length - 1;
4527 while (i < trail_length)
4529 inverted_trail[i] = trail[j];
4534 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4535 &inverted_trail[0]));
4536 return inverted_trail;
4541 * Return the shortest trail among all the trails to reach to finger from me.
4542 * @param finger Finger
4543 * @param shortest_trail_length[out] Trail length of shortest trail from me
4545 * @return Shortest trail.
4547 static struct GNUNET_PeerIdentity *
4548 get_shortest_trail (struct FingerInfo *finger,
4549 unsigned int *trail_length)
4551 struct Trail *trail;
4552 unsigned int flag = 0;
4553 unsigned int shortest_trail_index = 0;
4554 int shortest_trail_length = -1;
4555 struct Trail_Element *trail_element;
4556 struct GNUNET_PeerIdentity *trail_list;
4559 /* Get the shortest trail to reach to current successor. */
4560 for (i = 0; i < finger->trails_count; i++)
4562 trail = &finger->trail_list[i];
4566 shortest_trail_index = i;
4567 shortest_trail_length = trail->trail_length;
4572 if (shortest_trail_length > trail->trail_length)
4574 shortest_trail_index = i;
4575 shortest_trail_length = trail->trail_length;
4580 /* Copy the shortest trail and return. */
4581 trail = &finger->trail_list[shortest_trail_index];
4582 trail_element = trail->trail_head;
4584 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4585 shortest_trail_length);
4587 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4589 trail_list[i] = trail_element->peer;
4592 GNUNET_assert(shortest_trail_length != -1);
4594 *trail_length = shortest_trail_length;
4600 * Check if trail_1 and trail_2 have any common element. If yes then join
4601 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4602 * @param trail_1 Trail from source to me, NOT including endpoints.
4603 * @param trail_1_len Total number of peers @a trail_1
4604 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4605 * @param trail_2_len Total number of peers @a trail_2
4606 * @param joined_trail_len Total number of peers in combined trail of trail_1
4608 * @return Joined trail.
4610 static struct GNUNET_PeerIdentity *
4611 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4612 unsigned int trail_1_len,
4613 struct GNUNET_PeerIdentity *trail_2,
4614 unsigned int trail_2_len,
4615 unsigned int *joined_trail_len)
4617 struct GNUNET_PeerIdentity *joined_trail;
4622 for (i = 0; i < trail_1_len; i++)
4624 for (j = 0; j < trail_2_len; j++)
4626 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4629 *joined_trail_len = i + (trail_2_len - j);
4630 joined_trail = GNUNET_malloc (*joined_trail_len *
4631 sizeof(struct GNUNET_PeerIdentity));
4634 /* Copy all the elements from 0 to i into joined_trail. */
4635 for(k = 0; k < ( i+1); k++)
4637 joined_trail[k] = trail_1[k];
4640 /* Increment j as entry stored is same as entry stored at i*/
4643 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4644 while(k <= (*joined_trail_len - 1))
4646 joined_trail[k] = trail_2[j];
4651 return joined_trail;
4655 /* Here you should join the trails. */
4656 *joined_trail_len = trail_1_len + trail_2_len + 1;
4657 joined_trail = GNUNET_malloc (*joined_trail_len *
4658 sizeof(struct GNUNET_PeerIdentity));
4661 for(i = 0; i < trail_1_len;i++)
4663 joined_trail[i] = trail_1[i];
4666 joined_trail[i] = my_identity;
4669 for (j = 0; i < *joined_trail_len; i++,j++)
4671 joined_trail[i] = trail_2[j];
4674 return joined_trail;
4679 * Return the trail from source to my current predecessor. Check if source
4680 * is already part of the this trail, if yes then return the shorten trail.
4681 * @param current_trail Trail from source to me, NOT including the endpoints.
4682 * @param current_trail_length Number of peers in @a current_trail.
4683 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4684 * source to my predecessor, NOT including
4686 * @return Trail from source to my predecessor.
4688 static struct GNUNET_PeerIdentity *
4689 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4690 const struct GNUNET_PeerIdentity *trail_src_to_me,
4691 unsigned int trail_src_to_me_len,
4692 unsigned int *trail_src_to_curr_pred_length)
4694 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4695 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4696 unsigned int trail_me_to_curr_pred_length;
4697 struct FingerInfo *current_predecessor;
4702 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4704 /* Check if trail_src_to_me contains current_predecessor. */
4705 for (i = 0; i < trail_src_to_me_len; i++)
4707 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4708 ¤t_predecessor->finger_identity))
4712 *trail_src_to_curr_pred_length = i;
4717 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4718 sizeof(struct GNUNET_PeerIdentity));
4719 for (j = 0; j < i; j++)
4720 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4721 return trail_src_to_curr_pred;
4725 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4726 &trail_me_to_curr_pred_length);
4728 /* Check if trail contains the source_peer. */
4729 for (i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4731 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4732 &trail_me_to_curr_pred[i]))
4735 /* Source is NOT part of trail. */
4738 /* Source is the last element in the trail to reach to my pred.
4739 Source is direct friend of the pred. */
4740 if (trail_me_to_curr_pred_length == i)
4742 *trail_src_to_curr_pred_length = 0;
4743 GNUNET_free_non_null (trail_me_to_curr_pred);
4747 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4748 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4749 *trail_src_to_curr_pred_length);
4751 for (j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4752 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4753 GNUNET_free_non_null (trail_me_to_curr_pred);
4754 return trail_src_to_curr_pred;
4757 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4758 trail_src_to_me_len,
4759 trail_me_to_curr_pred,
4760 trail_me_to_curr_pred_length,
4762 *trail_src_to_curr_pred_length = len;
4763 GNUNET_free_non_null(trail_me_to_curr_pred);
4764 return trail_src_to_curr_pred;
4769 * Add finger as your predecessor. To add, first generate a new trail id, invert
4770 * the trail to get the trail from me to finger, add an entry in your routing
4771 * table, send add trail message to peers which are part of trail from me to
4772 * finger and add finger in finger table.
4775 * @param trail_length
4778 update_predecessor (struct GNUNET_PeerIdentity finger,
4779 struct GNUNET_PeerIdentity *trail,
4780 unsigned int trail_length)
4782 struct GNUNET_HashCode trail_to_new_predecessor_id;
4783 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4784 struct FriendInfo *target_friend;
4786 /* Generate trail id for trail from me to new predecessor = finger. */
4787 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4788 &trail_to_new_predecessor_id,
4789 sizeof (trail_to_new_predecessor_id));
4791 if (0 == trail_length)
4793 trail_to_new_predecessor = NULL;
4794 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4795 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger);
4796 if (NULL == target_friend)
4804 /* Invert the trail to get the trail from me to finger, NOT including the
4806 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4807 &trail[trail_length-1]));
4808 trail_to_new_predecessor = invert_trail (trail, trail_length);
4810 /* Add an entry in your routing table. */
4811 GDS_ROUTING_add (trail_to_new_predecessor_id,
4813 trail_to_new_predecessor[0]);
4815 GNUNET_assert (NULL != (target_friend =
4816 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4817 &trail_to_new_predecessor[0])));
4820 /* Add entry in routing table of all peers that are part of trail from me
4821 to finger, including finger. */
4822 GDS_NEIGHBOURS_send_add_trail (my_identity,
4824 trail_to_new_predecessor_id,
4825 trail_to_new_predecessor,
4829 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4830 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4831 GNUNET_free_non_null(trail_to_new_predecessor);
4836 * Check if you already have a predecessor. If not then add finger as your
4837 * predecessor. If you have predecessor, then compare two peer identites.
4838 * If finger is correct predecessor, then remove the old entry, add finger in
4839 * finger table and send add_trail message to add the trail in the routing
4840 * table of all peers which are part of trail to reach from me to finger.
4841 * @param finger New peer which may be our predecessor.
4842 * @param trail List of peers to reach from @finger to me.
4843 * @param trail_length Total number of peer in @a trail.
4846 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4847 struct GNUNET_PeerIdentity *trail,
4848 unsigned int trail_length)
4850 struct FingerInfo *current_predecessor;
4851 struct GNUNET_PeerIdentity closest_peer;
4852 uint64_t predecessor_value;
4853 unsigned int is_predecessor = 1;
4855 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4856 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4858 /* No predecessor. Add finger as your predecessor. */
4859 if (GNUNET_NO == current_predecessor->is_present)
4861 update_predecessor (finger, trail, trail_length);
4865 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4871 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4872 closest_peer = select_closest_peer (&finger,
4873 ¤t_predecessor->finger_identity,
4874 predecessor_value, is_predecessor);
4876 /* Finger is the closest predecessor. Remove the existing one and add the new
4878 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4880 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4881 update_predecessor (finger, trail, trail_length);
4889 * Core handle for p2p verify successor messages.
4890 * @param cls closure
4891 * @param message message
4892 * @param peer peer identity this notification is about
4893 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4896 handle_dht_p2p_verify_successor(void *cls,
4897 const struct GNUNET_PeerIdentity *peer,
4898 const struct GNUNET_MessageHeader *message)
4900 const struct PeerVerifySuccessorMessage *vsm;
4901 struct GNUNET_HashCode trail_id;
4902 struct GNUNET_PeerIdentity successor;
4903 struct GNUNET_PeerIdentity source_peer;
4904 struct GNUNET_PeerIdentity *trail;
4905 struct GNUNET_PeerIdentity *next_hop;
4906 struct FingerInfo current_predecessor;
4907 struct FriendInfo *target_friend;
4908 unsigned int trail_src_to_curr_pred_len = 0;
4909 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4910 unsigned int trail_length;
4913 msize = ntohs (message->size);
4915 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4917 GNUNET_break_op (0);
4921 vsm = (const struct PeerVerifySuccessorMessage *) message;
4922 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4923 sizeof (struct GNUNET_PeerIdentity);
4924 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4925 sizeof (struct GNUNET_PeerIdentity) != 0)
4927 GNUNET_break_op (0);
4931 GNUNET_STATISTICS_update (GDS_stats,
4933 ("# Bytes received from other peers"), msize,
4936 trail_id = vsm->trail_id;
4937 source_peer = vsm->source_peer;
4938 successor = vsm->successor;
4939 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4941 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4943 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4945 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4946 if (NULL == next_hop)
4951 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4953 if(NULL == target_friend)
4958 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4959 trail_id, trail, trail_length,
4964 /* I am the destination of this message. */
4966 /* Check if the source_peer could be our predecessor and if yes then update
4968 compare_and_update_predecessor (source_peer, trail, trail_length);
4969 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4971 /* Is source of this message NOT my predecessor. */
4972 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4975 trail_src_to_curr_pred =
4976 get_trail_src_to_curr_pred (source_peer,
4979 &trail_src_to_curr_pred_len);
4983 trail_src_to_curr_pred_len = trail_length;
4986 trail_src_to_curr_pred =
4987 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4988 *trail_src_to_curr_pred_len);
4989 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4991 trail_src_to_curr_pred[i] = trail[i];
4995 GNUNET_assert (NULL !=
4997 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4998 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4999 current_predecessor.finger_identity,
5000 trail_id, trail_src_to_curr_pred,
5001 trail_src_to_curr_pred_len,
5002 GDS_ROUTING_DEST_TO_SRC,
5004 GNUNET_free_non_null(trail_src_to_curr_pred);
5010 * If the trail from me to my probable successor contains a friend not
5011 * at index 0, then we can shorten the trail.
5012 * @param probable_successor Peer which is our probable successor
5013 * @param trail_me_to_probable_successor Peers in path from me to my probable
5014 * successor, NOT including the endpoints.
5015 * @param trail_me_to_probable_successor_len Total number of peers in
5016 * @a trail_me_to_probable_succesor.
5017 * @return Updated trail, if any friend found.
5018 * Else the trail_me_to_probable_successor.
5020 struct GNUNET_PeerIdentity *
5021 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
5022 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
5023 unsigned int trail_me_to_probable_successor_len,
5024 unsigned int *trail_to_new_successor_length)
5028 struct GNUNET_PeerIdentity *trail_to_new_successor;
5030 /* Probable successor is a friend */
5031 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5032 &probable_successor))
5034 trail_to_new_successor = NULL;
5035 *trail_to_new_successor_length = 0;
5036 return trail_to_new_successor;
5039 /* Is there any friend of yours in this trail. */
5040 if(trail_me_to_probable_successor_len > 1)
5042 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
5044 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5045 &trail_me_to_probable_successor[i]))
5048 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
5049 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
5050 *trail_to_new_successor_length);
5053 for(j = 0; j < *trail_to_new_successor_length; i++,j++)
5055 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
5058 return trail_to_new_successor;
5062 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
5063 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
5067 struct SendNotifyContext
5069 struct GNUNET_PeerIdentity source_peer;
5070 struct GNUNET_PeerIdentity successor;
5071 struct GNUNET_PeerIdentity *successor_trail;
5072 unsigned int successor_trail_length;
5073 struct GNUNET_HashCode succesor_trail_id;
5074 struct FriendInfo *target_friend;
5075 unsigned int num_retries_scheduled;
5079 send_notify_new_successor (void *cls,
5080 const struct GNUNET_SCHEDULER_TaskContext
5084 * Check if the peer which sent us verify successor result message is still ours
5085 * successor or not. If not, then compare existing successor and probable successor.
5086 * In case probable successor is the correct successor, remove the existing
5087 * successor. Add probable successor as new successor. Send notify new successor
5088 * message to new successor.
5089 * @param curr_succ Peer to which we sent the verify successor message. It may
5090 * or may not be our real current successor, as we may have few iterations of
5091 * find finger trail task.
5092 * @param probable_successor Peer which should be our successor accroding to @a
5094 * @param trail List of peers to reach from me to @a probable successor, NOT including
5096 * @param trail_length Total number of peers in @a trail.
5099 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
5100 struct GNUNET_PeerIdentity probable_successor,
5101 const struct GNUNET_PeerIdentity *trail,
5102 unsigned int trail_length)
5104 struct FingerInfo *current_successor;
5105 struct GNUNET_PeerIdentity closest_peer;
5106 struct GNUNET_HashCode trail_id;
5107 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
5108 struct FriendInfo *target_friend;
5109 unsigned int trail_me_to_probable_succ_len;
5110 unsigned int is_predecessor = 0;
5111 uint64_t successor_value;
5113 current_successor = &finger_table[0];
5114 successor_value = compute_finger_identity_value(0);
5116 /* If probable successor is same as current_successor, do nothing. */
5117 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
5118 ¤t_successor->finger_identity))
5120 if ((NULL != GDS_stats))
5126 memcpy (&my_id, &my_identity, sizeof(uint64_t));
5127 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5128 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5129 succ = GNUNET_ntohll(succ);
5130 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5131 GNUNET_free (my_id_str);
5133 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5136 if (send_verify_successor_task == NULL)
5137 send_verify_successor_task =
5138 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5139 &send_verify_successor_message,
5143 closest_peer = select_closest_peer (&probable_successor,
5144 ¤t_successor->finger_identity,
5145 successor_value, is_predecessor);
5147 /* If the current_successor in the finger table is closest, then do nothing. */
5148 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
5149 ¤t_successor->finger_identity))
5151 //FIXME: Is this a good place to return the stats.
5152 if ((NULL != GDS_stats))
5158 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5159 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5160 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5161 GNUNET_free (my_id_str);
5162 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5166 if(0 == successor_times)
5168 // successor_times = 3;
5169 verify_successor_next_send_time =
5170 GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time);
5176 if (send_verify_successor_task == NULL)
5177 send_verify_successor_task =
5178 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5179 &send_verify_successor_message,
5184 /* Probable successor is the closest peer.*/
5185 if(trail_length > 0)
5187 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5192 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5193 &probable_successor));
5196 trail_me_to_probable_succ_len = 0;
5197 trail_me_to_probable_succ =
5198 check_trail_me_to_probable_succ (probable_successor,
5199 trail, trail_length,
5200 &trail_me_to_probable_succ_len);
5202 /* Remove the existing successor. */
5203 remove_existing_finger (current_successor, 0);
5204 /* Generate a new trail id to reach to your new successor. */
5205 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5206 &trail_id, sizeof (trail_id));
5208 if (trail_me_to_probable_succ_len > 0)
5210 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
5211 GNUNET_assert (NULL !=
5213 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5214 &trail_me_to_probable_succ[0])));
5218 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5219 GNUNET_assert (NULL !=
5221 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5222 &probable_successor)));
5225 add_new_finger (probable_successor, trail_me_to_probable_succ,
5226 trail_me_to_probable_succ_len, trail_id, 0);
5228 struct SendNotifyContext *notify_ctx;
5230 notify_ctx = GNUNET_new(struct SendNotifyContext);
5232 notify_ctx->source_peer = my_identity;
5233 notify_ctx->successor = probable_successor;
5234 notify_ctx->successor_trail =
5235 GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5236 memcpy(notify_ctx->successor_trail, trail_me_to_probable_succ,
5237 sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5238 notify_ctx->successor_trail_length = trail_me_to_probable_succ_len;
5239 notify_ctx->succesor_trail_id = trail_id;
5240 notify_ctx->target_friend = target_friend;
5241 notify_ctx->num_retries_scheduled = 0;
5242 GNUNET_free_non_null (trail_me_to_probable_succ);
5244 // TODO: Check if we should verify before schedule if already scheduled.
5245 GNUNET_SCHEDULER_add_now(&send_notify_new_successor, (void*)notify_ctx);
5251 send_notify_new_successor (void *cls,
5252 const struct GNUNET_SCHEDULER_TaskContext
5255 struct SendNotifyContext *ctx = (struct SendNotifyContext *) cls;
5257 GDS_NEIGHBOURS_send_notify_new_successor (ctx->source_peer,
5259 ctx->successor_trail,
5260 ctx->successor_trail_length,
5261 ctx->succesor_trail_id,
5262 ctx->target_friend);
5264 if (0 == ctx->num_retries_scheduled &&
5265 send_notify_new_successor_retry_task != NULL)
5267 // Result from previous notify successos hasn't arrived, so the retry task
5268 // hasn't been cancelled! Already a new notify successor must be called.
5269 // We will cancel the retry request.
5270 struct SendNotifyContext *old_notify_ctx;
5271 old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5272 GNUNET_free (old_notify_ctx->successor_trail);
5273 GNUNET_free (old_notify_ctx);
5274 send_notify_new_successor_retry_task = NULL;
5277 ctx->num_retries_scheduled++;
5278 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_add_delayed(notify_successor_retry_time,
5279 &send_notify_new_successor,
5284 * Core handle for p2p verify successor result messages.
5285 * @param cls closure
5286 * @param message message
5287 * @param peer peer identity this notification is about
5288 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5291 handle_dht_p2p_verify_successor_result(void *cls,
5292 const struct GNUNET_PeerIdentity *peer,
5293 const struct GNUNET_MessageHeader *message)
5295 const struct PeerVerifySuccessorResultMessage *vsrm;
5296 enum GDS_ROUTING_trail_direction trail_direction;
5297 struct GNUNET_PeerIdentity querying_peer;
5298 struct GNUNET_HashCode trail_id;
5299 struct GNUNET_PeerIdentity *next_hop;
5300 struct FriendInfo *target_friend;
5301 struct GNUNET_PeerIdentity probable_successor;
5302 struct GNUNET_PeerIdentity current_successor;
5303 const struct GNUNET_PeerIdentity *trail;
5304 unsigned int trail_length;
5307 msize = ntohs (message->size);
5308 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5310 GNUNET_break_op (0);
5314 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5315 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5316 sizeof (struct GNUNET_PeerIdentity) != 0)
5318 GNUNET_break_op (0);
5321 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5322 sizeof (struct GNUNET_PeerIdentity);
5324 GNUNET_STATISTICS_update (GDS_stats,
5326 ("# Bytes received from other peers"), msize,
5329 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5330 querying_peer = vsrm->querying_peer;
5331 trail_direction = ntohl (vsrm->trail_direction);
5332 trail_id = vsrm->trail_id;
5333 probable_successor = vsrm->probable_successor;
5334 current_successor = vsrm->current_successor;
5336 /* I am the querying_peer. */
5337 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5339 /* Cancel Retry Task */
5340 if (NULL != send_verify_successor_retry_task)
5342 struct VerifySuccessorContext *ctx;
5343 ctx = GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
5345 send_verify_successor_retry_task = NULL;
5347 compare_and_update_successor (current_successor,
5348 probable_successor, trail, trail_length);
5352 /*If you are not the querying peer then pass on the message */
5353 if(NULL == (next_hop =
5354 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
5356 /* Here it may happen that source peer has found a new successor, and removed
5357 the trail, Hence no entry found in the routing table. Fail silently.*/
5358 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5359 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5363 if (NULL == (target_friend =
5364 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5369 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5370 vsrm->current_successor,
5371 probable_successor, trail_id,
5374 trail_direction, target_friend);
5380 * Core handle for p2p notify new successor messages.
5381 * @param cls closure
5382 * @param message message
5383 * @param peer peer identity this notification is about
5384 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5387 handle_dht_p2p_notify_new_successor(void *cls,
5388 const struct GNUNET_PeerIdentity *peer,
5389 const struct GNUNET_MessageHeader *message)
5391 const struct PeerNotifyNewSuccessorMessage *nsm;
5392 struct GNUNET_PeerIdentity *trail;
5393 struct GNUNET_PeerIdentity source;
5394 struct GNUNET_PeerIdentity new_successor;
5395 struct GNUNET_HashCode trail_id;
5396 struct GNUNET_PeerIdentity next_hop;
5397 struct FriendInfo *target_friend;
5400 uint32_t trail_length;
5402 msize = ntohs (message->size);
5403 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5405 GNUNET_break_op (0);
5408 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5409 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5410 sizeof (struct GNUNET_PeerIdentity) != 0)
5412 GNUNET_break_op (0);
5415 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5416 sizeof (struct GNUNET_PeerIdentity);
5417 GNUNET_STATISTICS_update (GDS_stats,
5419 ("# Bytes received from other peers"), msize,
5422 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5423 source = nsm->source_peer;
5424 new_successor = nsm->new_successor;
5425 trail_id = nsm->trail_id;
5427 /* I am the new_successor to source_peer. */
5428 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5430 if(trail_length > 0)
5431 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5434 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5436 compare_and_update_predecessor (source, trail, trail_length);
5437 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5438 GNUNET_assert (NULL != target_friend);
5439 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5440 GDS_ROUTING_DEST_TO_SRC,
5445 GNUNET_assert(trail_length > 0);
5446 /* I am part of trail to reach to successor. */
5447 my_index = search_my_index (trail, trail_length);
5450 DEBUG ("No entry found in trail\n");
5451 GNUNET_break_op (0);
5452 return GNUNET_SYSERR;
5454 if((trail_length + 1) == my_index)
5456 DEBUG ("Found twice in trail.\n");
5457 GNUNET_break_op (0);
5458 return GNUNET_SYSERR;
5460 if ((trail_length-1) == my_index)
5461 next_hop = new_successor;
5463 next_hop = trail[my_index + 1];
5465 GDS_ROUTING_add(trail_id, *peer, next_hop);
5467 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
5468 if (NULL == target_friend)
5473 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5475 trail_id, target_friend);
5482 * Core handler for P2P notify successor message
5483 * @param cls closure
5484 * @param message message
5485 * @param peer peer identity this notification is about
5486 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5489 handle_dht_p2p_notify_succ_confirmation (void *cls,
5490 const struct GNUNET_PeerIdentity *peer,
5491 const struct GNUNET_MessageHeader *message)
5493 const struct PeerNotifyConfirmationMessage *notify_confirmation;
5494 enum GDS_ROUTING_trail_direction trail_direction;
5495 struct GNUNET_HashCode trail_id;
5496 struct FriendInfo *target_friend;
5497 struct GNUNET_PeerIdentity *next_hop;
5500 msize = ntohs (message->size);
5502 if (msize != sizeof (struct PeerNotifyConfirmationMessage))
5504 GNUNET_break_op (0);
5507 GNUNET_STATISTICS_update (GDS_stats,
5509 ("# Bytes received from other peers"), msize,
5512 notify_confirmation = (const struct PeerNotifyConfirmationMessage *) message;
5513 trail_direction = ntohl (notify_confirmation->trail_direction);
5514 trail_id = notify_confirmation->trail_id;
5516 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5517 if (NULL == next_hop)
5519 /* The source of notify new successor, might have found even a better
5520 successor. In that case it send a trail teardown message, and hence,
5521 the next hop is NULL. */
5522 //Fixme: Add some print to confirm the above theory.
5526 /* I peer which sent the notify successor message to the successor. */
5527 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5530 * Schedule another round of verify sucessor with your current successor
5531 * which may or may not be source of this message. This message is used
5532 * only to ensure that we have a path setup to reach to our successor.
5535 // TODO: cancel schedule of notify_successor_retry_task
5536 if (send_notify_new_successor_retry_task != NULL)
5538 struct SendNotifyContext *notify_ctx;
5539 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5540 GNUNET_free (notify_ctx->successor_trail);
5541 GNUNET_free (notify_ctx);
5542 send_notify_new_successor_retry_task = NULL;
5544 if (send_verify_successor_task == NULL)
5546 verify_successor_next_send_time.rel_value_us =
5547 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5548 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5549 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5550 send_verify_successor_task =
5551 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5552 &send_verify_successor_message,
5558 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
5559 if (NULL == target_friend)
5561 DEBUG ("\n friend not found, line number = %d",__LINE__);
5562 return GNUNET_SYSERR;
5564 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5565 GDS_ROUTING_DEST_TO_SRC,
5573 * Core handler for P2P trail rejection message
5574 * @param cls closure
5575 * @param message message
5576 * @param peer peer identity this notification is about
5577 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5580 handle_dht_p2p_trail_setup_rejection (void *cls,
5581 const struct GNUNET_PeerIdentity *peer,
5582 const struct GNUNET_MessageHeader *message)
5584 const struct PeerTrailRejectionMessage *trail_rejection;
5585 unsigned int trail_length;
5586 const struct GNUNET_PeerIdentity *trail_peer_list;
5587 struct FriendInfo *target_friend;
5588 struct GNUNET_TIME_Relative congestion_timeout;
5589 struct GNUNET_HashCode trail_id;
5590 struct GNUNET_PeerIdentity next_peer;
5591 struct GNUNET_PeerIdentity source;
5592 uint64_t ultimate_destination_finger_value;
5593 unsigned int is_predecessor;
5596 msize = ntohs (message->size);
5597 if (msize < sizeof (struct PeerTrailRejectionMessage))
5599 GNUNET_break_op (0);
5602 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5603 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5604 sizeof (struct GNUNET_PeerIdentity) != 0)
5606 GNUNET_break_op (0);
5609 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5610 sizeof (struct GNUNET_PeerIdentity);
5611 GNUNET_STATISTICS_update (GDS_stats,
5613 ("# Bytes received from other peers"), msize,
5616 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5617 is_predecessor = ntohl (trail_rejection->is_predecessor);
5618 congestion_timeout = trail_rejection->congestion_time;
5619 source = trail_rejection->source_peer;
5620 trail_id = trail_rejection->trail_id;
5621 ultimate_destination_finger_value =
5622 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5623 /* First set the congestion time of the friend that sent you this message. */
5624 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5625 if (NULL == target_friend)
5627 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5631 target_friend->congestion_timestamp =
5632 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5633 congestion_timeout);
5635 /* I am the source peer which wants to setup the trail. Do nothing.
5636 * send_find_finger_trail_task is scheduled periodically.*/
5637 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5640 /* If I am congested then pass this message to peer before me in trail. */
5641 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5643 /* First remove yourself from the trail. */
5644 unsigned int new_trail_length = trail_length - 1;
5645 struct GNUNET_PeerIdentity trail[new_trail_length];
5647 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5648 if (0 == trail_length)
5651 next_peer = trail[new_trail_length-1];
5654 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5655 if (NULL == target_friend)
5657 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5661 GDS_NEIGHBOURS_send_trail_rejection (source,
5662 ultimate_destination_finger_value,
5663 my_identity, is_predecessor,
5664 trail, new_trail_length, trail_id,
5665 target_friend, CONGESTION_TIMEOUT);
5669 struct Closest_Peer successor;
5670 successor = find_local_best_known_next_hop (ultimate_destination_finger_value, is_predecessor);
5672 /* Am I the final destination? */
5673 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5676 /*Here you are already part of trail. Copy the trail removing yourself. */
5677 unsigned int new_trail_length = trail_length - 1;
5678 struct GNUNET_PeerIdentity trail[new_trail_length];
5680 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5682 if (0 == new_trail_length)
5686 next_peer = trail[new_trail_length-1];
5689 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5691 if (NULL == target_friend)
5693 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5697 GDS_NEIGHBOURS_send_trail_setup_result (source,
5699 target_friend, new_trail_length,
5702 ultimate_destination_finger_value,
5707 /* Here I was already part of trail. So no need to add. */
5709 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5710 &successor.next_hop);
5711 if (NULL == target_friend)
5713 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5718 GDS_NEIGHBOURS_send_trail_setup (source,
5719 ultimate_destination_finger_value,
5720 successor.best_known_destination,
5721 target_friend, trail_length, trail_peer_list,
5722 is_predecessor, trail_id,
5723 successor.trail_id);
5730 * Core handler for trail teardown message.
5731 * @param cls closure
5732 * @param message message
5733 * @param peer sender of this messsage.
5734 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5737 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5738 const struct GNUNET_MessageHeader *message)
5740 const struct PeerTrailTearDownMessage *trail_teardown;
5741 enum GDS_ROUTING_trail_direction trail_direction;
5742 struct GNUNET_HashCode trail_id;
5743 struct GNUNET_PeerIdentity *next_hop;
5746 msize = ntohs (message->size);
5748 /* Here we pass only the trail id. */
5749 if (msize != sizeof (struct PeerTrailTearDownMessage))
5751 GNUNET_break_op (0);
5755 GNUNET_STATISTICS_update (GDS_stats,
5757 ("# Bytes received from other peers"), msize,
5760 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5761 trail_direction = ntohl (trail_teardown->trail_direction);
5762 trail_id = trail_teardown->trail_id;
5764 /* Check if peer is the real peer from which we should get this message.*/
5765 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5767 GNUNET_assert (NULL != (prev_hop =
5768 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5769 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5772 return GNUNET_SYSERR;
5776 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5777 if (NULL == next_hop)
5779 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5780 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5782 return GNUNET_SYSERR;
5785 /* I am the next hop, which means I am the final destination. */
5786 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5788 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5793 /* If not final destination, then send a trail teardown message to next hop.*/
5794 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5795 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5796 GDS_NEIGHBOURS_send_trail_teardown (&trail_id, trail_direction, next_hop);
5804 * Core handle for p2p add trail message.
5805 * @param cls closure
5806 * @param message message
5807 * @param peer peer identity this notification is about
5808 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5811 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5812 const struct GNUNET_MessageHeader *message)
5814 const struct PeerAddTrailMessage *add_trail;
5815 const struct GNUNET_PeerIdentity *trail;
5816 struct GNUNET_HashCode trail_id;
5817 struct GNUNET_PeerIdentity destination_peer;
5818 struct GNUNET_PeerIdentity source_peer;
5819 struct GNUNET_PeerIdentity next_hop;
5820 unsigned int trail_length;
5821 unsigned int my_index;
5824 msize = ntohs (message->size);
5825 /* In this message we pass the whole trail from source to destination as we
5826 * are adding that trail.*/
5827 //FIXME: failed when run with 1000 pears. check why.
5828 if (msize < sizeof (struct PeerAddTrailMessage))
5830 GNUNET_break_op (0);
5834 add_trail = (const struct PeerAddTrailMessage *) message;
5835 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5836 sizeof (struct GNUNET_PeerIdentity);
5837 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5838 sizeof (struct GNUNET_PeerIdentity) != 0)
5840 GNUNET_break_op (0);
5844 GNUNET_STATISTICS_update (GDS_stats,
5846 ("# Bytes received from other peers"), msize,
5849 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5850 destination_peer = add_trail->destination_peer;
5851 source_peer = add_trail->source_peer;
5852 trail_id = add_trail->trail_id;
5854 /* I am not the destination of the trail. */
5855 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5857 struct FriendInfo *target_friend;
5859 /* Get my location in the trail. */
5860 my_index = search_my_index (trail, trail_length);
5863 GNUNET_break_op (0);
5864 return GNUNET_SYSERR;
5866 if((trail_length + 1) == my_index)
5868 DEBUG ("Found twice in trail.\n");
5869 GNUNET_break_op (0);
5870 return GNUNET_SYSERR;
5872 if ((trail_length - 1) == my_index)
5874 next_hop = destination_peer;
5878 next_hop = trail[my_index + 1];
5880 /* Add in your routing table. */
5881 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5882 //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5883 GNUNET_assert (NULL !=
5885 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5886 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5887 trail, trail_length, target_friend);
5890 /* I am the destination. Add an entry in routing table. */
5891 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5897 * Free the finger trail in which the first friend to reach to a finger is
5898 * disconnected_friend. Also remove entry from routing table for that particular
5900 * @param disconnected_friend PeerIdentity of friend which got disconnected
5901 * @param remove_finger Finger whose trail we need to check if it has
5902 * disconnected_friend as the first hop.
5903 * @return Total number of trails in which disconnected_friend was the first
5907 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5908 struct FingerInfo *finger)
5910 struct GNUNET_PeerIdentity *next_hop;
5911 struct FriendInfo *remove_friend;
5912 struct Trail *current_trail;
5913 unsigned int matching_trails_count = 0;
5916 /* Iterate over all the trails of finger. */
5917 for (i = 0; i < finger->trails_count; i++)
5919 current_trail = &finger->trail_list[i];
5920 if (GNUNET_NO == current_trail->is_present)
5923 /* First friend to reach to finger is disconnected_peer. */
5924 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5925 disconnected_friend))
5928 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5929 disconnected_friend);
5930 GNUNET_assert (NULL != remove_friend);
5931 next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id,
5932 GDS_ROUTING_SRC_TO_DEST);
5934 /* Here it may happen that as all the peers got disconnected, the entry in
5935 routing table for that particular trail has been removed, because the
5936 previously disconnected peer was either a next hop or prev hop of that
5938 if (NULL != next_hop)
5940 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5942 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id));
5944 matching_trails_count++;
5945 free_trail (current_trail);
5946 current_trail->is_present = GNUNET_NO;
5949 return matching_trails_count;
5954 * Iterate over finger_table entries.
5955 * 0. Ignore finger which is my_identity or if no valid entry present at
5956 * that finger index.
5957 * 1. If disconnected_friend is a finger, then remove the routing entry from
5958 your own table. Free the trail.
5959 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5960 * 2.1 Remove all the trails and entry from routing table in which disconnected
5961 * friend is the first friend in the trail. If disconnected_friend is the
5962 * first friend in all the trails to reach finger, then remove the finger.
5963 * @param disconnected_friend Peer identity of friend which got disconnected.
5966 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5968 struct FingerInfo *current_finger;
5969 int removed_trails_count;
5972 /* Iterate over finger table entries. */
5973 for (i = 0; i < MAX_FINGERS; i++)
5975 current_finger = &finger_table[i];
5977 /* No finger stored at this trail index or I am the finger. */
5978 if ((GNUNET_NO == current_finger->is_present) ||
5979 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5983 /* Is disconnected_peer a finger? */
5984 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5985 ¤t_finger->finger_identity))
5987 remove_existing_finger (current_finger, i);
5990 /* If finger is a friend but not disconnected_friend, then continue. */
5991 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5992 ¤t_finger->finger_identity))
5995 /* Iterate over the list of trails to reach remove_finger. Check if
5996 * disconnected_friend is the first friend in any of the trail. */
5997 removed_trails_count = remove_matching_trails (disconnected_peer,
5999 current_finger->trails_count =
6000 current_finger->trails_count - removed_trails_count;
6001 if (0 == current_finger->trails_count)
6003 current_finger->is_present = GNUNET_NO;
6004 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
6011 * Method called whenever a peer disconnects.
6013 * @param cls closure
6014 * @param peer peer identity this notification is about
6017 handle_core_disconnect (void *cls,
6018 const struct GNUNET_PeerIdentity *peer)
6020 struct FriendInfo *remove_friend;
6021 struct P2PPendingMessage *pos;
6022 unsigned int discarded;
6024 /* If disconnected to own identity, then return. */
6025 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
6028 if(NULL == (remove_friend =
6029 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
6031 DEBUG("\n friend already disconnected.");
6035 remove_matching_fingers (peer);
6036 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
6037 GNUNET_assert (GNUNET_YES ==
6038 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
6042 /* Remove all the messages queued in pending list of this peer is discarded.*/
6043 if (remove_friend->th != NULL)
6045 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
6046 remove_friend->th = NULL;
6050 while (NULL != (pos = remove_friend->head))
6052 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
6057 GNUNET_STATISTICS_update (GDS_stats,
6059 ("# Queued messages discarded (peer disconnected)"),
6060 discarded, GNUNET_NO);
6061 //GNUNET_free (remove_friend);
6063 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
6066 if (NULL != find_finger_trail_task)
6068 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6069 find_finger_trail_task = NULL;
6077 * Method called whenever a peer connects.
6079 * @param cls closure
6080 * @param peer_identity peer identity this notification is about
6083 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
6085 struct FriendInfo *friend;
6087 /* Check for connect to self message */
6088 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
6091 /* If peer already exists in our friend_peermap, then exit. */
6092 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
6099 friend = GNUNET_new (struct FriendInfo);
6100 friend->id = *peer_identity;
6102 GNUNET_assert (GNUNET_OK ==
6103 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
6104 peer_identity, friend,
6105 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
6107 /* FIXME: now we are not making a distinction between fingers which are friends
6108 * also.But later, we should add a congestion timestamp on the friend, so that it is
6109 * selected after some time out. This is to ensure that both peers have added
6110 * each other as their friend. */
6111 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
6112 if (NULL == find_finger_trail_task)
6114 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
6120 * To be called on core init/fail.
6122 * @param cls service closure
6123 * @param identity the public identity of this peer
6126 core_init (void *cls,
6127 const struct GNUNET_PeerIdentity *identity)
6129 my_identity = *identity;
6134 * Initialize finger table entries.
6137 finger_table_init ()
6139 memset (&finger_table, 0, sizeof (finger_table));
6144 * Initialize neighbours subsystem.
6145 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
6148 GDS_NEIGHBOURS_init (void)
6150 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
6151 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
6152 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
6153 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
6154 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
6155 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
6156 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
6157 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
6158 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
6159 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
6160 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
6161 sizeof (struct PeerTrailTearDownMessage)},
6162 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
6163 {&handle_dht_p2p_notify_succ_confirmation, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION,
6164 sizeof (struct PeerNotifyConfirmationMessage)},
6168 #if ENABLE_MALICIOUS
6173 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
6174 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
6175 GNUNET_NO, core_handlers);
6177 if (NULL == core_api)
6178 return GNUNET_SYSERR;
6180 //TODO: check size of this peer map?
6181 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
6182 finger_table_init ();
6183 successor_times = 10;
6184 fingers_round_count = 5;
6185 find_finger_trail_task_next_send_time.rel_value_us =
6186 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
6187 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6188 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
6190 verify_successor_next_send_time.rel_value_us =
6191 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
6192 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6193 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
6195 verify_successor_retry_time.rel_value_us =
6196 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6197 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6198 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6200 notify_successor_retry_time.rel_value_us =
6201 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6202 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6203 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6211 * Free the memory held up by trails of a finger.
6214 delete_finger_table_entries()
6219 for(i = 0; i < MAX_FINGERS; i++)
6221 if(GNUNET_YES == finger_table[i].is_present)
6223 for(j = 0; j < finger_table[i].trails_count; j++)
6224 free_trail(&finger_table[i].trail_list[j]);
6231 * Shutdown neighbours subsystem.
6234 GDS_NEIGHBOURS_done (void)
6236 if (NULL == core_api)
6239 GNUNET_CORE_disconnect (core_api);
6242 delete_finger_table_entries();
6243 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6244 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6245 friend_peermap = NULL;
6247 if (NULL != find_finger_trail_task)
6249 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6250 find_finger_trail_task = NULL;
6253 if (NULL != send_verify_successor_task)
6255 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6256 send_verify_successor_task = NULL;
6259 if (NULL != send_verify_successor_retry_task)
6261 struct VerifySuccessorContext *ctx;
6262 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
6264 send_verify_successor_retry_task = NULL;
6267 if (send_notify_new_successor_retry_task != NULL)
6269 struct SendNotifyContext *notify_ctx;
6270 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
6271 GNUNET_free (notify_ctx->successor_trail);
6272 GNUNET_free (notify_ctx);
6273 send_notify_new_successor_retry_task = NULL;
6281 * @return my identity
6283 struct GNUNET_PeerIdentity
6284 GDS_NEIGHBOURS_get_my_id (void)
6289 /* end of gnunet-service-xdht_neighbours.c */