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_MILLISECONDS, 1)
79 * How long at most to wait for transmission of a request to a friend ?
81 #define GET_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
84 * Duration for which I may remain congested.
85 * Note: Its a static value. In future, a peer may do some analysis and calculate
86 * congestion_timeout based on 'some' parameters.
88 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
91 * Maximum number of trails allowed to go through a friend.
93 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
96 * Maximum number of trails stored per finger.
98 #define MAXIMUM_TRAILS_PER_FINGER 1
101 * Finger map index for predecessor entry in finger table.
103 #define PREDECESSOR_FINGER_ID 64
106 * Wrap around in peer identity circle.
108 #define PEER_IDENTITES_WRAP_AROUND pow(2, 64) - 1
111 * FIXME: Its use only at 3 places check if you can remove it.
112 * To check if a finger is predecessor or not.
114 enum GDS_NEIGHBOURS_finger_type
116 GDS_FINGER_TYPE_PREDECESSOR = 1,
117 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
120 GNUNET_NETWORK_STRUCT_BEGIN
125 struct PeerPutMessage
128 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
130 struct GNUNET_MessageHeader header;
135 uint32_t options GNUNET_PACKED;
140 uint32_t block_type GNUNET_PACKED;
145 uint32_t hop_count GNUNET_PACKED;
148 * Replication level for this message
149 * In the current implementation, this value is not used.
151 uint32_t desired_replication_level GNUNET_PACKED;
154 * Length of the PUT path that follows (if tracked).
156 uint32_t put_path_length GNUNET_PACKED;
159 * Best known destination (could be my friend or finger) which should
160 * get this message next.
162 struct GNUNET_PeerIdentity best_known_destination;
165 * In case best_known_destination is a finger, then trail to reach
166 * to that finger. Else its default value is 0.
168 struct GNUNET_HashCode intermediate_trail_id;
171 * When does the content expire?
173 struct GNUNET_TIME_AbsoluteNBO expiration_time;
176 * The key to store the value under.
178 struct GNUNET_HashCode key GNUNET_PACKED;
180 /* put path (if tracked) */
189 struct PeerGetMessage
192 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
194 struct GNUNET_MessageHeader header;
199 uint32_t options GNUNET_PACKED;
202 * Desired content type.
204 uint32_t block_type GNUNET_PACKED;
209 uint32_t hop_count GNUNET_PACKED;
212 * Desired replication level for this request.
213 * In the current implementation, this value is not used.
215 uint32_t desired_replication_level GNUNET_PACKED;
218 * Total number of peers in get path.
220 unsigned int get_path_length;
223 * Best known destination (could be my friend or finger) which should
224 * get this message next.
226 struct GNUNET_PeerIdentity best_known_destination;
229 * In case best_known_destination is a finger, then trail to reach
230 * to that finger. Else its default value is 0.
232 struct GNUNET_HashCode intermediate_trail_id;
235 * The key we are looking for.
237 struct GNUNET_HashCode key;
240 /* struct GNUNET_PeerIdentity[]*/
246 struct PeerGetResultMessage
249 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
251 struct GNUNET_MessageHeader header;
254 * The type for the data.
256 uint32_t type GNUNET_PACKED;
259 * Number of peers recorded in the outgoing path from source to the
260 * stored location of this message.
262 uint32_t put_path_length GNUNET_PACKED;
265 * Length of the GET path that follows (if tracked).
267 uint32_t get_path_length GNUNET_PACKED;
270 * Peer which queried for get and should get the result.
272 struct GNUNET_PeerIdentity querying_peer;
275 * When does the content expire?
277 struct GNUNET_TIME_Absolute expiration_time;
280 * The key of the corresponding GET request.
282 struct GNUNET_HashCode key;
284 /* put path (if tracked) */
286 /* get path (if tracked) */
293 * P2P Trail setup message
295 struct PeerTrailSetupMessage
298 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
300 struct GNUNET_MessageHeader header;
303 * Is source_peer trying to setup the trail to a predecessor or any finger.
305 uint32_t is_predecessor;
308 * Peer closest to this value will be our finger.
310 uint64_t final_destination_finger_value;
313 * Source peer which wants to setup the trail to one of its finger.
315 struct GNUNET_PeerIdentity source_peer;
318 * Best known destination (could be my friend or finger) which should
319 * get this message next.
321 * FIXME: this could be removed if we include trail_source / trail_dest
322 * in the routing table. This way we save 32 bytes of bandwidth by using
323 * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID))
325 struct GNUNET_PeerIdentity best_known_destination;
328 * In case best_known_destination is a finger, then trail id of trail to
329 * reach to this finger.
331 struct GNUNET_HashCode intermediate_trail_id;
334 * Trail id for trail which we are trying to setup.
336 struct GNUNET_HashCode trail_id;
338 /* List of peers which are part of trail setup so far.
339 * Trail does NOT include source_peer and peer which will be closest to
340 * ultimate_destination_finger_value.
341 * struct GNUNET_PeerIdentity trail[]
346 * P2P Trail Setup Result message
348 struct PeerTrailSetupResultMessage
352 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
354 struct GNUNET_MessageHeader header;
357 * Finger to which we have found the path.
359 struct GNUNET_PeerIdentity finger_identity;
362 * Peer which started trail_setup to find trail to finger_identity
364 struct GNUNET_PeerIdentity querying_peer;
367 * Is the trail setup to querying_peer's predecessor or finger?
369 uint32_t is_predecessor;
372 * Value to which finger_identity is the closest peer.
374 uint64_t ulitmate_destination_finger_value;
377 * Identifier of the trail from querying peer to finger_identity, NOT
378 * including both endpoints.
380 struct GNUNET_HashCode trail_id;
382 /* List of peers which are part of the trail from querying peer to
383 * finger_identity, NOT including both endpoints.
384 * struct GNUNET_PeerIdentity trail[]
389 * P2P Verify Successor Message.
391 struct PeerVerifySuccessorMessage
394 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
396 struct GNUNET_MessageHeader header;
399 * Peer which wants to verify its successor.
401 struct GNUNET_PeerIdentity source_peer;
404 * Source Peer's current successor.
406 struct GNUNET_PeerIdentity successor;
409 * Identifier of trail to reach from source_peer to successor.
411 struct GNUNET_HashCode trail_id;
413 /* List of the peers which are part of trail to reach from source_peer
414 * to successor, NOT including them
415 * struct GNUNET_PeerIdentity trail[]
420 * P2P Verify Successor Result Message
422 struct PeerVerifySuccessorResultMessage
425 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
427 struct GNUNET_MessageHeader header;
430 * Peer which sent the request to verify its successor.
432 struct GNUNET_PeerIdentity querying_peer;
435 * Successor to which PeerVerifySuccessorMessage was sent.
437 struct GNUNET_PeerIdentity current_successor;
440 * Current Predecessor of source_successor. It can be same as querying peer
441 * or different. In case it is different then it can be querying_peer's
442 * probable successor.
444 struct GNUNET_PeerIdentity probable_successor;
447 * Trail identifier of trail from querying_peer to current_successor.
449 struct GNUNET_HashCode trail_id;
452 * Direction in which we are looking at the trail.
454 uint32_t trail_direction;
456 /* In case probable_successor != querying_peer, then trail to reach from
457 * querying_peer to probable_successor, NOT including end points.
458 * struct GNUNET_PeerIdentity trail[]
463 * P2P Notify New Successor Message.
465 struct PeerNotifyNewSuccessorMessage
468 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
470 struct GNUNET_MessageHeader header;
473 * Peer which wants to notify its new successor.
475 struct GNUNET_PeerIdentity source_peer;
478 * New successor of source_peer.
480 struct GNUNET_PeerIdentity new_successor;
483 * Unique identifier of the trail from source_peer to new_successor,
484 * NOT including the endpoints.
486 struct GNUNET_HashCode trail_id;
488 /* List of peers in trail from source_peer to new_successor,
489 * NOT including the endpoints.
490 * struct GNUNET_PeerIdentity trail[]
495 * P2P Trail Compression Message.
497 struct PeerTrailCompressionMessage
500 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION
502 struct GNUNET_MessageHeader header;
505 * Source peer of this trail.
507 struct GNUNET_PeerIdentity source_peer;
510 * Trail from source_peer to destination_peer compressed such that
511 * new_first_friend is the first hop in the trail from source to
514 struct GNUNET_PeerIdentity new_first_friend;
517 * Unique identifier of trail.
519 struct GNUNET_HashCode trail_id;
524 * P2P Trail Tear Down message.
526 struct PeerTrailTearDownMessage
529 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
531 struct GNUNET_MessageHeader header;
534 * Unique identifier of the trail.
536 struct GNUNET_HashCode trail_id;
539 * Direction of trail.
541 uint32_t trail_direction;
546 * P2P Trail Rejection Message.
548 struct PeerTrailRejectionMessage
551 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
553 struct GNUNET_MessageHeader header;
556 * Peer which wants to set up the trail.
558 struct GNUNET_PeerIdentity source_peer;
561 * Peer which sent trail rejection message as it it congested.
563 struct GNUNET_PeerIdentity congested_peer;
566 * Peer identity closest to this value will be finger of
569 uint64_t ultimate_destination_finger_value;
572 * Is source_peer trying to setup the trail to its predecessor or finger.
574 uint32_t is_predecessor;
577 * Identifier for the trail that source peer is trying to setup.
579 struct GNUNET_HashCode trail_id;
582 * Relative time for which congested_peer will remain congested.
584 struct GNUNET_TIME_Relative congestion_time;
586 /* Trail_list from source_peer to peer which sent the message for trail setup
587 * to congested peer. This trail does NOT include source_peer.
588 struct GNUNET_PeerIdnetity trail[]*/
592 * P2P Add Trail Message.
594 struct PeerAddTrailMessage
597 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
599 struct GNUNET_MessageHeader header;
602 * Source of the routing trail.
604 struct GNUNET_PeerIdentity source_peer;
607 * Destination of the routing trail.
609 struct GNUNET_PeerIdentity destination_peer;
612 * Unique identifier of the trail from source_peer to destination_peer,
613 * NOT including the endpoints.
615 struct GNUNET_HashCode trail_id;
617 /* Trail from source peer to destination peer, NOT including them.
618 * struct GNUNET_PeerIdentity trail[]
622 GNUNET_NETWORK_STRUCT_END
625 * Linked list of messages to send to a particular other peer.
627 struct P2PPendingMessage
630 * Pointer to next item in the list
632 struct P2PPendingMessage *next;
635 * Pointer to previous item in the list
637 struct P2PPendingMessage *prev;
640 * Message importance level. FIXME: used? useful?
642 unsigned int importance;
645 * When does this message time out?
647 struct GNUNET_TIME_Absolute timeout;
650 * Actual message to be sent, allocated at the end of the struct:
651 * // msg = (cast) &pm[1];
652 * // memcpy (&pm[1], data, len);
654 const struct GNUNET_MessageHeader *msg;
659 * Entry in friend_peermap.
666 struct GNUNET_PeerIdentity id;
669 * Number of trails for which this friend is the first hop or if the friend
672 unsigned int trails_count;
675 * Count of outstanding messages for this friend.
677 unsigned int pending_count;
680 * In case not 0, then amount of time for which this friend is congested.
682 struct GNUNET_TIME_Absolute congestion_timestamp;
685 // TODO : Change name of head and tail to pending_messages_list_head and so.
687 * Head of pending messages to be sent to this friend.
689 struct P2PPendingMessage *head;
692 * Tail of pending messages to be sent to this friend.
694 struct P2PPendingMessage *tail;
697 * Core handle for sending messages to this friend.
699 struct GNUNET_CORE_TransmitHandle *th;
704 * An individual element of the trail to reach to a finger.
709 * Pointer to next item in the list
711 struct Trail_Element *next;
714 * Pointer to prev item in the list
716 struct Trail_Element *prev;
719 * An element in this trail.
721 struct GNUNET_PeerIdentity peer;
725 * Information about an individual trail.
732 struct Trail_Element *trail_head;
737 struct Trail_Element *trail_tail;
740 * Unique identifier of this trail.
742 struct GNUNET_HashCode trail_id;
745 * Length of trail pointed
747 unsigned int trail_length;
750 * Is there a valid trail entry.
752 unsigned int is_present;
756 * An entry in finger_table
763 struct GNUNET_PeerIdentity finger_identity;
766 * Is any finger stored at this finger index.
768 unsigned int is_present;
771 * Index in finger peer map
773 uint32_t finger_table_index;
776 * Number of trails setup so far for this finger.
777 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
779 uint32_t trails_count;
782 * Array of trails to reach to this finger.
784 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
789 * Stores information about the peer which is closest to destination_finger_value.
790 * 'closest' can be either successor or predecessor depending on is_predecessor
796 * Destination finger value.
798 uint64_t destination_finger_value;
801 * Is finger_value a predecessor or any other finger.
803 unsigned int is_predecessor;
806 * Trail id to reach to peer.
807 * In case peer is my identity or friend, it is set to 0.
809 struct GNUNET_HashCode trail_id;
812 * Next destination. In case of friend and my_identity , it is same as next_hop
813 * In case of finger it is finger identity.
815 struct GNUNET_PeerIdentity best_known_destination;
818 * In case best_known_destination is a finger, then first friend in the trail
819 * to reach to it. In other case, same as best_known_destination.
821 struct GNUNET_PeerIdentity next_hop;
826 * Data structure to store the trail chosen to reach to finger.
828 struct Selected_Finger_Trail
831 * First friend in the trail to reach finger.
833 struct FriendInfo friend;
836 * Identifier of this trail.
838 struct GNUNET_HashCode trail_id;
841 * Total number of peers in this trail.
843 unsigned int trail_length;
847 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
848 * get our first friend.
850 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
853 * Task that sends verify successor message. This task is started when we get
854 * our successor for the first time.
856 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_task;
859 * Identity of this peer.
861 static struct GNUNET_PeerIdentity my_identity;
864 * Peer map of all the friends of a peer
866 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
869 * Array of all the fingers.
871 static struct FingerInfo finger_table [MAX_FINGERS];
876 static struct GNUNET_CORE_Handle *core_api;
879 * Handle for the statistics service.
881 //extern struct GNUNET_STATISTICS_Handle *GDS_stats;
884 * The current finger index that we have want to find trail to. We start the
885 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
886 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
887 * we reset this index to 0.
889 static unsigned int current_search_finger_index;
892 * Should we store our topology predecessor and successor IDs into statistics?
894 unsigned int track_topology;
897 * Should I be a malicious peer and drop the PUT/GET packets?
898 * if 0 then NOT malicious.
900 unsigned int act_malicious;
903 * Called when core is ready to send a message we asked for
904 * out to the destination.
906 * @param cls the 'struct FriendInfo' of the target friend
907 * @param size number of bytes available in buf
908 * @param buf where the callee should write the message
909 * @return number of bytes written to buf
912 core_transmit_notify (void *cls, size_t size, void *buf)
914 struct FriendInfo *peer = cls;
916 struct P2PPendingMessage *pending;
921 while ((NULL != (pending = peer->head)) &&
922 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
924 peer->pending_count--;
925 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
926 GNUNET_free (pending);
930 /* no messages pending */
936 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
937 GNUNET_CORE_PRIO_BEST_EFFORT,
938 GNUNET_TIME_absolute_get_remaining
939 (pending->timeout), &peer->id,
940 ntohs (pending->msg->size),
941 &core_transmit_notify, peer);
942 GNUNET_break (NULL != peer->th);
946 while ((NULL != (pending = peer->head)) &&
947 (size - off >= (msize = ntohs (pending->msg->size))))
949 GNUNET_STATISTICS_update (GDS_stats,
951 ("# Bytes transmitted to other peers"), msize,
953 memcpy (&cbuf[off], pending->msg, msize);
955 peer->pending_count--;
956 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
957 GNUNET_free (pending);
959 if (peer->head != NULL)
962 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
963 GNUNET_CORE_PRIO_BEST_EFFORT,
964 GNUNET_TIME_absolute_get_remaining
965 (pending->timeout), &peer->id, msize,
966 &core_transmit_notify, peer);
967 GNUNET_break (NULL != peer->th);
974 * Transmit all messages in the friend's message queue.
976 * @param peer message queue to process
979 process_friend_queue (struct FriendInfo *peer)
981 struct P2PPendingMessage *pending;
983 if (NULL == (pending = peer->head))
987 if (NULL != peer->th)
993 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
995 GNUNET_TIME_absolute_get_remaining
996 (pending->timeout), &peer->id,
997 ntohs (pending->msg->size),
998 &core_transmit_notify, peer);
999 GNUNET_break (NULL != peer->th);
1003 #if ENABLE_MALICIOUS
1005 * Set the ENABLE_MALICIOUS value to malicious.
1009 GDS_NEIGHBOURS_act_malicious (unsigned int malicious)
1011 act_malicious = malicious;
1016 * Construct a trail setup message and forward it to target_friend
1017 * @param source_peer Peer which wants to setup the trail
1018 * @param ultimate_destination_finger_value Peer identity closest to this value
1019 * will be finger to @a source_peer
1020 * @param best_known_destination Best known destination (could be finger or friend)
1021 * which should get this message. In case it is
1022 * friend, then it is same as target_friend
1023 * @param target_friend Friend to which message is forwarded now.
1024 * @param trail_length Total number of peers in trail setup so far.
1025 * @param trail_peer_list Trail setup so far
1026 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1027 * @param trail_id Unique identifier for the trail we are trying to setup.
1028 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1029 * best_known_destination when its a finger. If not
1030 * used then set to 0.
1033 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1034 uint64_t ultimate_destination_finger_value,
1035 struct GNUNET_PeerIdentity best_known_destination,
1036 struct FriendInfo *target_friend,
1037 unsigned int trail_length,
1038 const struct GNUNET_PeerIdentity *trail_peer_list,
1039 unsigned int is_predecessor,
1040 struct GNUNET_HashCode trail_id,
1041 struct GNUNET_HashCode intermediate_trail_id)
1043 struct P2PPendingMessage *pending;
1044 struct PeerTrailSetupMessage *tsm;
1045 struct GNUNET_PeerIdentity *peer_list;
1048 msize = sizeof (struct PeerTrailSetupMessage) +
1049 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1051 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1057 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1059 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1063 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1064 // TODO: Create a new macro for timeout value of pending messages
1065 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1066 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1067 pending->msg = &(tsm->header);
1068 tsm->header.size = htons (msize);
1069 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1070 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1071 tsm->source_peer = source_peer;
1072 tsm->best_known_destination = best_known_destination;
1073 tsm->is_predecessor = htonl (is_predecessor);
1074 tsm->trail_id = trail_id;
1075 tsm->intermediate_trail_id = intermediate_trail_id;
1077 if (trail_length > 0)
1079 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1080 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1083 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1084 target_friend->pending_count++;
1085 process_friend_queue (target_friend);
1090 * Construct a trail setup result message and forward it to target friend.
1091 * @param querying_peer Peer which sent the trail setup request and should get
1093 * @param Finger Peer to which the trail has been setup to.
1094 * @param target_friend Friend to which this message should be forwarded.
1095 * @param trail_length Numbers of peers in the trail.
1096 * @param trail_peer_list Peers which are part of the trail from
1097 * querying_peer to Finger, NOT including them.
1098 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1099 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1101 * @param trail_id Unique identifier of the trail.
1104 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1105 struct GNUNET_PeerIdentity finger,
1106 struct FriendInfo *target_friend,
1107 unsigned int trail_length,
1108 const struct GNUNET_PeerIdentity *trail_peer_list,
1109 unsigned int is_predecessor,
1110 uint64_t ultimate_destination_finger_value,
1111 struct GNUNET_HashCode trail_id)
1113 struct P2PPendingMessage *pending;
1114 struct PeerTrailSetupResultMessage *tsrm;
1115 struct GNUNET_PeerIdentity *peer_list;
1118 msize = sizeof (struct PeerTrailSetupResultMessage) +
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,
1130 gettext_noop ("# P2P messages dropped due to full queue"),
1134 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1135 pending->importance = 0;
1136 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT); //TODO: Change it
1137 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1138 pending->msg = &tsrm->header;
1139 tsrm->header.size = htons (msize);
1140 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1141 tsrm->querying_peer = querying_peer;
1142 tsrm->finger_identity = finger;
1143 tsrm->is_predecessor = htonl (is_predecessor);
1144 tsrm->trail_id = trail_id;
1145 tsrm->ulitmate_destination_finger_value =
1146 GNUNET_htonll (ultimate_destination_finger_value);
1147 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1148 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1150 /* Send the message to chosen friend. */
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 * Send trail rejection message to target friend
1159 * @param source_peer Peer which is trying to setup the trail.
1160 * @param ultimate_destination_finger_value Peer closest to this value will be
1161 * @a source_peer's finger
1162 * @param congested_peer Peer which sent this message as it is congested.
1163 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1164 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1165 * by congested_peer. This does NOT include @a source_peer
1166 * and congested_peer.
1167 * @param trail_length Total number of peers in trail_peer_list, NOT including
1168 * @a source_peer and @a congested_peer
1169 * @param trail_id Unique identifier of this trail.
1170 * @param congestion_timeout Duration given by congested peer as an estimate of
1171 * how long it may remain congested.
1174 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1175 uint64_t ultimate_destination_finger_value,
1176 struct GNUNET_PeerIdentity congested_peer,
1177 unsigned int is_predecessor,
1178 const struct GNUNET_PeerIdentity *trail_peer_list,
1179 unsigned int trail_length,
1180 struct GNUNET_HashCode trail_id,
1181 struct FriendInfo *target_friend,
1182 const struct GNUNET_TIME_Relative congestion_timeout)
1184 struct PeerTrailRejectionMessage *trm;
1185 struct P2PPendingMessage *pending;
1186 struct GNUNET_PeerIdentity *peer_list;
1189 msize = sizeof (struct PeerTrailRejectionMessage) +
1190 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1192 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1198 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1200 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1204 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1205 pending->importance = 0;
1206 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1207 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1208 pending->msg = &trm->header;
1209 trm->header.size = htons (msize);
1210 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1211 trm->source_peer = source_peer;
1212 trm->congested_peer = congested_peer;
1213 trm->congestion_time = congestion_timeout;
1214 trm->is_predecessor = htonl (is_predecessor);
1215 trm->trail_id = trail_id;
1216 trm->ultimate_destination_finger_value =
1217 GNUNET_htonll (ultimate_destination_finger_value);
1219 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1220 if (trail_length > 0)
1222 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1225 /* Send the message to chosen friend. */
1226 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1227 target_friend->pending_count++;
1228 process_friend_queue (target_friend);
1233 * Construct a verify successor message and forward it to target_friend.
1234 * @param source_peer Peer which wants to verify its successor.
1235 * @param successor Peer which is @a source_peer's current successor.
1236 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1237 * NOT including them.
1238 * @param trail List of peers which are part of trail to reach from @a source_peer
1239 * to @a successor, NOT including them.
1240 * @param trail_length Total number of peers in @a trail.
1241 * @param target_friend Next friend to get this message.
1244 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1245 struct GNUNET_PeerIdentity successor,
1246 struct GNUNET_HashCode trail_id,
1247 struct GNUNET_PeerIdentity *trail,
1248 unsigned int trail_length,
1249 struct FriendInfo *target_friend)
1251 struct PeerVerifySuccessorMessage *vsm;
1252 struct P2PPendingMessage *pending;
1253 struct GNUNET_PeerIdentity *peer_list;
1256 msize = sizeof (struct PeerVerifySuccessorMessage) +
1257 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1258 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1264 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1266 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1270 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1271 pending->importance = 0; /* FIXME */
1272 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1273 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1274 pending->msg = &vsm->header;
1275 vsm->header.size = htons (msize);
1276 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1277 vsm->source_peer = source_peer;
1278 vsm->successor = successor;
1279 vsm->trail_id = trail_id;
1280 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1281 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1283 /* Send the message to chosen friend. */
1284 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1285 target_friend->pending_count++;
1286 process_friend_queue (target_friend);
1291 * FIXME: In every function we pass target friend except for this one.
1292 * so, either change everything or this one. also, should se just store
1293 * the pointer to friend in routing table rather than gnunet_peeridentity.
1294 * if yes then we should keep friend info in.h andmake lot of changes.
1295 * Construct a trail teardown message and forward it to target friend.
1296 * @param trail_id Unique identifier of the trail.
1297 * @param trail_direction Direction of trail.
1298 * @param target_friend Friend to get this message.
1301 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1302 unsigned int trail_direction,
1303 struct GNUNET_PeerIdentity peer)
1305 struct PeerTrailTearDownMessage *ttdm;
1306 struct P2PPendingMessage *pending;
1307 struct FriendInfo *target_friend;
1310 msize = sizeof (struct PeerTrailTearDownMessage);
1312 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1318 /*FIXME:In what case friend can be null. ?*/
1319 if (NULL == (target_friend =
1320 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1323 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1325 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1329 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1330 pending->importance = 0; /* FIXME */
1331 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1332 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1333 pending->msg = &ttdm->header;
1334 ttdm->header.size = htons (msize);
1335 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1336 ttdm->trail_id = trail_id;
1337 ttdm->trail_direction = htonl (trail_direction);
1339 /* Send the message to chosen friend. */
1340 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1341 target_friend->pending_count++;
1342 process_friend_queue (target_friend);
1347 * Construct a verify successor result message and send it to target_friend
1348 * @param querying_peer Peer which sent the verify successor message.
1349 * @param source_successor Current_successor of @a querying_peer.
1350 * @param current_predecessor Current predecessor of @a successor. Could be same
1351 * or different from @a querying_peer.
1352 * @param trail_id Unique identifier of the trail from @a querying_peer to
1353 * @a successor, NOT including them.
1354 * @param trail List of peers which are part of trail from @a querying_peer to
1355 * @a successor, NOT including them.
1356 * @param trail_length Total number of peers in @a trail
1357 * @param trail_direction Direction in which we are sending the message. In this
1358 * case we are sending result from @a successor to @a querying_peer.
1359 * @param target_friend Next friend to get this message.
1362 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1363 struct GNUNET_PeerIdentity current_successor,
1364 struct GNUNET_PeerIdentity probable_successor,
1365 struct GNUNET_HashCode trail_id,
1366 const struct GNUNET_PeerIdentity *trail,
1367 unsigned int trail_length,
1368 enum GDS_ROUTING_trail_direction trail_direction,
1369 struct FriendInfo *target_friend)
1371 struct PeerVerifySuccessorResultMessage *vsmr;
1372 struct P2PPendingMessage *pending;
1373 struct GNUNET_PeerIdentity *peer_list;
1376 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1377 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1379 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1385 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1387 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1391 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1392 pending->importance = 0; /* FIXME */
1393 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1394 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1395 pending->msg = &vsmr->header;
1396 vsmr->header.size = htons (msize);
1397 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1398 vsmr->querying_peer = querying_peer;
1399 vsmr->current_successor = current_successor;
1400 vsmr->probable_successor = probable_successor;
1401 vsmr->trail_direction = htonl (trail_direction);
1402 vsmr->trail_id = trail_id;
1403 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1404 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1406 /* Send the message to chosen friend. */
1407 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1408 target_friend->pending_count++;
1409 process_friend_queue (target_friend);
1414 * Construct a notify new successor message and send it to target_friend
1415 * @param source_peer Peer which wants to notify to its new successor that it
1416 * could be its predecessor.
1417 * @param successor New successor of @a source_peer
1418 * @param successor_trail List of peers in Trail to reach from
1419 * @a source_peer to @a new_successor, NOT including
1421 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1422 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1423 * @param target_friend Next friend to get this message.
1426 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1427 struct GNUNET_PeerIdentity successor,
1428 const struct GNUNET_PeerIdentity *successor_trail,
1429 unsigned int successor_trail_length,
1430 struct GNUNET_HashCode succesor_trail_id,
1431 struct FriendInfo *target_friend)
1433 struct PeerNotifyNewSuccessorMessage *nsm;
1434 struct P2PPendingMessage *pending;
1435 struct GNUNET_PeerIdentity *peer_list;
1438 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1439 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1441 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1447 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1449 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1453 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1454 pending->importance = 0; /* FIXME */
1455 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1456 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1457 pending->msg = &nsm->header;
1458 nsm->header.size = htons (msize);
1459 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1460 nsm->new_successor = successor;
1461 nsm->source_peer = source_peer;
1462 nsm->trail_id = succesor_trail_id;
1464 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1465 memcpy (peer_list, successor_trail,
1466 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1468 /* Send the message to chosen friend. */
1469 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1470 target_friend->pending_count++;
1471 process_friend_queue (target_friend);
1476 * Construct an add_trail message and send it to target_friend
1477 * @param source_peer Source of the trail.
1478 * @param destination_peer Destination of the trail.
1479 * @param trail_id Unique identifier of the trail from
1480 * @a source_peer to @a destination_peer, NOT including the endpoints.
1481 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1482 * NOT including the endpoints.
1483 * @param trail_length Total number of peers in @a trail.
1484 * @param target_friend Next friend to get this message.
1487 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1488 struct GNUNET_PeerIdentity destination_peer,
1489 struct GNUNET_HashCode trail_id,
1490 const struct GNUNET_PeerIdentity *trail,
1491 unsigned int trail_length,
1492 struct FriendInfo *target_friend)
1494 struct PeerAddTrailMessage *adm;
1495 struct GNUNET_PeerIdentity *peer_list;
1496 struct P2PPendingMessage *pending;
1499 msize = sizeof (struct PeerAddTrailMessage) +
1500 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1502 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1508 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1510 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1514 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1515 pending->importance = 0; /* FIXME */
1516 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1517 adm = (struct PeerAddTrailMessage *) &pending[1];
1518 pending->msg = &adm->header;
1519 adm->header.size = htons (msize);
1520 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1521 adm->source_peer = source_peer;
1522 adm->destination_peer = destination_peer;
1523 adm->trail_id = trail_id;
1524 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1525 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1527 /* Send the message to chosen friend. */
1528 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1529 target_friend->pending_count++;
1530 process_friend_queue (target_friend);
1536 * Construct a trail compression message and send it to target_friend.
1537 * @param source_peer Source of the trail.
1538 * @param trail_id Unique identifier of trail.
1539 * @param first_friend First hop in compressed trail to reach from source to finger
1540 * @param target_friend Next friend to get this message.
1543 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1544 struct GNUNET_HashCode trail_id,
1545 struct GNUNET_PeerIdentity first_friend,
1546 struct FriendInfo *target_friend)
1548 struct P2PPendingMessage *pending;
1549 struct PeerTrailCompressionMessage *tcm;
1552 msize = sizeof (struct PeerTrailCompressionMessage);
1554 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1560 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1562 GNUNET_STATISTICS_update (GDS_stats,
1563 gettext_noop ("# P2P messages dropped due to full queue"),
1567 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1568 pending->importance = 0; /* FIXME */
1569 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1570 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1571 pending->msg = &tcm->header;
1572 tcm->header.size = htons (msize);
1573 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1574 tcm->source_peer = source_peer;
1575 tcm->new_first_friend = first_friend;
1576 tcm->trail_id = trail_id;
1578 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1579 target_friend->pending_count++;
1580 process_friend_queue (target_friend);
1586 * Search my location in trail. In case I am present more than once in the
1587 * trail (can happen during trail setup), then return my lowest index.
1588 * @param trail List of peers
1589 * @return my_index if found
1590 * trail_length + 1 if an entry is present twice, It is an error.
1591 * -1 if no entry found.
1594 search_my_index (const struct GNUNET_PeerIdentity *trail,
1598 int index_seen = trail_length + 1;
1601 for (i = 0; i < trail_length; i++)
1603 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1606 if(index_seen == (trail_length + 1))
1610 DEBUG("Entry is present twice in trail. Its not allowed\n");
1624 * Check if the friend is congested or have reached maximum number of trails
1625 * it can be part of of.
1626 * @param friend Friend to be checked.
1627 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1628 * #GNUNET_YES if friend is either congested or have crossed threshold
1631 is_friend_congested (struct FriendInfo *friend)
1633 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1634 ((0 == GNUNET_TIME_absolute_get_remaining
1635 (friend->congestion_timestamp).rel_value_us)))
1643 * Select closest finger to value.
1644 * @param peer1 First peer
1645 * @param peer2 Second peer
1646 * @param value Value to be compare
1647 * @return Closest peer
1649 const static struct GNUNET_PeerIdentity *
1650 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1651 const struct GNUNET_PeerIdentity *peer2,
1654 uint64_t peer1_value;
1655 uint64_t peer2_value;
1657 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1658 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1659 peer1_value = GNUNET_ntohll (peer1_value);
1660 peer2_value = GNUNET_ntohll (peer2_value);
1662 // TODO: Can use a simpler (to understand) idea here!
1664 if (peer1_value == value)
1669 if (peer2_value == value)
1674 if (peer2_value < peer1_value)
1676 if ((peer2_value < value) && (value < peer1_value))
1680 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1681 ((0 < value) && (value < peer2_value)))
1687 if (peer1_value < peer2_value)
1689 if ((peer1_value < value) && (value < peer2_value))
1693 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1694 ((0 < value) && (value < peer1_value)))
1704 * Select closest predecessor to value.
1705 * @param peer1 First peer
1706 * @param peer2 Second peer
1707 * @param value Value to be compare
1708 * @return Peer which precedes value in the network.
1710 const static struct GNUNET_PeerIdentity *
1711 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1712 const struct GNUNET_PeerIdentity *peer2,
1715 uint64_t peer1_value;
1716 uint64_t peer2_value;
1718 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1719 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1720 peer1_value = GNUNET_ntohll (peer1_value);
1721 peer2_value = GNUNET_ntohll (peer2_value);
1723 if (peer1_value == value)
1726 if (peer2_value == value)
1729 if (peer1_value < peer2_value)
1731 if ((peer1_value < value) && (value < peer2_value))
1735 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1736 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1742 if (peer2_value < peer1_value)
1744 if ((peer2_value < value) && (value < peer1_value))
1748 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1749 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1763 test_print_trail (struct GNUNET_PeerIdentity *trail,
1764 unsigned int trail_length)
1766 struct GNUNET_PeerIdentity print_peer;
1769 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1770 __FILE__, __func__,__LINE__,trail_length);
1771 for (i =0 ; i< trail_length; i++)
1773 print_peer = trail[i];
1774 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1775 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1782 * This is a test function to print all the entries of friend table.
1785 test_friend_peermap_print ()
1787 struct FriendInfo *friend;
1788 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1789 struct GNUNET_PeerIdentity print_peer;
1790 struct GNUNET_PeerIdentity key_ret;
1793 print_peer = my_identity;
1794 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1795 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1797 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1799 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1801 (const void **)&friend))
1803 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1804 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1805 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1813 * This is a test function, to print all the entries of finger table.
1816 test_finger_table_print()
1818 struct FingerInfo *finger;
1819 struct GNUNET_PeerIdentity print_peer;
1820 //struct Trail *trail;
1824 print_peer = my_identity;
1825 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1826 for (i = 0; i < MAX_FINGERS; i++)
1828 finger = &finger_table[i];
1830 if (GNUNET_NO == finger->is_present)
1833 print_peer = finger->finger_identity;
1834 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1835 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1838 for (j = 0; j < finger->trails_count; j++)
1840 trail = &finger->trail_list[j];
1841 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1842 struct Trail_Element *element;
1843 element = trail->trail_head;
1844 for (k = 0; k < trail->trail_length; k++)
1846 print_peer = element->peer;
1847 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1848 element = element->next;
1857 * Select the closest peer among two peers (which should not be same)
1858 * with respect to value and finger_table_index
1859 * NOTE: peer1 != peer2
1860 * @param peer1 First peer
1861 * @param peer2 Second peer
1862 * @param value Value relative to which we find the closest
1863 * @param is_predecessor Is value a predecessor or any other finger.
1864 * @return Closest peer among two peers.
1867 // TODO: URGENT! Change return type to value instead of pointer
1868 const static struct GNUNET_PeerIdentity *
1869 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1870 const struct GNUNET_PeerIdentity *peer2,
1872 unsigned int is_predecessor)
1874 /* This check is here to ensure that calling function never sends
1875 same peer value in peer1 and peer2. Remove it later. */
1876 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1877 if (1 == is_predecessor)
1878 return select_closest_predecessor (peer1, peer2, value);
1880 // TODO: Change name to something like select_closest_successor!!
1881 return select_closest_finger (peer1, peer2, value);
1886 * Iterate over the list of all the trails of a finger. In case the first
1887 * friend to reach the finger has reached trail threshold or is congested,
1888 * then don't select it. In case there multiple available good trails to reach
1889 * to Finger, choose the one with shortest trail length.
1890 * Note: We use length as parameter. But we can use any other suitable parameter
1892 * @param finger Finger
1893 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1894 * and trail length. NULL in case none of the trails are free.
1896 static struct Trail *
1897 select_finger_trail (struct FingerInfo *finger)
1899 struct FriendInfo *friend;
1900 struct Trail *current_finger_trail;
1901 struct Trail *best_trail = NULL;
1904 GNUNET_assert (finger->trails_count > 0);
1906 for (i = 0; i < finger->trails_count; i++)
1908 current_finger_trail = &finger->trail_list[i];
1910 /* No trail stored at this index. */
1911 if (GNUNET_NO == current_finger_trail->is_present)
1914 GNUNET_assert (NULL !=
1916 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1917 ¤t_finger_trail->trail_head->peer)));
1919 /* First friend to reach trail is not free. */
1920 if (GNUNET_YES == is_friend_congested (friend))
1923 if (NULL == best_trail ||
1924 best_trail->trail_length > current_finger_trail->trail_length)
1926 best_trail = current_finger_trail;
1934 static struct Selected_Finger_Trail *
1935 select_finger_trail (struct FingerInfo *finger)
1937 struct FriendInfo *friend;
1938 struct Trail *current_finger_trail;
1939 struct Selected_Finger_Trail *finger_trail;
1941 unsigned int flag = 0;
1944 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1945 GNUNET_assert (finger->trails_count > 0);
1947 for (i = 0; i < finger->trails_count; i++)
1949 current_finger_trail = &finger->trail_list[i];
1951 /* No trail stored at this index. */
1952 if (GNUNET_NO == current_finger_trail->is_present)
1955 GNUNET_assert (NULL !=
1957 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1958 ¤t_finger_trail->trail_head->peer)));
1960 /* First friend to reach trail is not free. */
1961 if (GNUNET_YES == is_friend_congested (friend))
1970 finger_trail->trail_length = current_finger_trail->trail_length;
1971 finger_trail->friend = *friend;
1972 finger_trail->trail_id = current_finger_trail->trail_id;
1974 else if (finger_trail->trail_length > current_finger_trail->trail_length)
1976 finger_trail->friend = *friend;
1977 finger_trail->trail_id = current_finger_trail->trail_id;
1978 finger_trail->trail_length = current_finger_trail->trail_length;
1982 /* All the first friend in all the trails to reach to finger are either
1983 congested or have crossed trail threshold. */
1984 if (j == finger->trails_count)
1987 return finger_trail;
1993 * Compare FINGER entry with current successor. If finger's first friend of all
1994 * its trail is not congested and has not crossed trail threshold, then check
1995 * if finger peer identity is closer to final_destination_finger_value than
1996 * current_successor. If yes then update current_successor.
1997 * @param current_successor[in/out]
2001 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
2003 struct FingerInfo *finger;
2004 const struct GNUNET_PeerIdentity *closest_peer;
2005 struct Trail *finger_trail;
2008 // TODO: Instead of iterating over all fingers, calculate the finger index
2009 // using "value" of my id and current closest peer id.
2011 /* Iterate over finger table. */
2012 for (i = 0; i < MAX_FINGERS; i++)
2014 finger = &finger_table[i];
2016 if (GNUNET_NO == finger->is_present)
2019 /* FIXME write correct comment here */
2020 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2021 ¤t_closest_peer->best_known_destination))
2024 /* If I am my own finger, then ignore this finger. */
2025 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2028 /* FIXME: I think a peer should not select itself as its own identity ever.
2029 But it does select. Find out why??*/
2035 /* If finger is a friend, then do nothing. As we have already checked
2036 * for each friend in compare_friend_and_current_successor(). */
2037 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2038 &finger->finger_identity)))
2043 closest_peer = select_closest_peer (&finger->finger_identity,
2044 ¤t_closest_peer->best_known_destination,
2045 current_closest_peer->destination_finger_value,
2046 current_closest_peer->is_predecessor);
2048 if (&finger->finger_identity == closest_peer)
2050 /* Choose one of the trail to reach to finger. */
2051 finger_trail = select_finger_trail (finger);
2053 /* In case no trail found, ignore this finger. */
2054 if (NULL == finger_trail)
2057 current_closest_peer->best_known_destination = *closest_peer;
2058 current_closest_peer->next_hop = finger_trail->trail_head->peer;
2059 current_closest_peer->trail_id = finger_trail->trail_id;
2067 * Compare friend entry with current successor.
2068 * If friend identity and current_successor is same, then do nothing.
2069 * If friend is not congested and has not crossed trail threshold, then check
2070 * if friend peer identity is closer to final_destination_finger_value than
2071 * current_successor. If yes then update current_successor.
2072 * @param cls closure
2073 * @param key current public key
2074 * @param value struct Closest_Peer
2075 * @return #GNUNET_YES if we should continue to iterate,
2076 * #GNUNET_NO if not.
2079 compare_friend_and_current_closest_peer (void *cls,
2080 const struct GNUNET_PeerIdentity *key,
2083 struct FriendInfo *friend = value;
2084 struct Closest_Peer *current_closest_peer = cls;
2085 const struct GNUNET_PeerIdentity *closest_peer;
2087 /* Friend is either congested or has crossed threshold. */
2088 if (GNUNET_YES == is_friend_congested (friend))
2091 /* If current_closest_peer and friend identity are same, then do nothing.*/
2092 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2093 ¤t_closest_peer->best_known_destination))
2099 closest_peer = select_closest_peer (&friend->id,
2100 ¤t_closest_peer->best_known_destination,
2101 current_closest_peer->destination_finger_value,
2102 current_closest_peer->is_predecessor);
2104 /* Is friend the closest successor? */
2105 if (&friend->id == closest_peer)
2107 current_closest_peer->best_known_destination = friend->id;
2108 current_closest_peer->next_hop = friend->id;
2116 * Initialize current_successor to my_identity.
2117 * @param my_identity My peer identity
2118 * @return Updated closest_peer
2120 static struct Closest_Peer
2121 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2122 uint64_t destination_finger_value,
2123 unsigned int is_predecessor)
2125 struct Closest_Peer current_closest_peer;
2127 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2128 current_closest_peer.destination_finger_value = destination_finger_value;
2129 current_closest_peer.is_predecessor = is_predecessor;
2130 current_closest_peer.next_hop = my_identity;
2131 current_closest_peer.best_known_destination = my_identity;
2133 return current_closest_peer;
2138 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2139 * peer. It could be because of the logic we wrote here. Verify if its correct.
2140 * If not then return immediate_successor.
2142 * Find the successor for destination_finger_value among my_identity, my
2143 * friends and my fingers. Don't consider friends or fingers which are either
2144 * congested or have crossed the threshold.
2145 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2147 * @param destination_finger_value Peer closest to this value will be the next successor.
2148 * @param is_predecessor Are we looking for predecessor or finger?
2149 * @return Successor It is never NULL, in case none of friend or finger is closest,
2150 * then we return my_identity.
2152 static struct Closest_Peer
2153 find_successor (uint64_t destination_finger_value,
2154 unsigned int is_predecessor)
2156 struct Closest_Peer current_closest_peer;
2158 /* Initialize current_successor to my_identity. */
2159 current_closest_peer = init_current_successor (my_identity,
2160 destination_finger_value,
2163 /* Compare each friend entry with current_successor and update current_successor
2164 * with friend if its closest. */
2167 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2168 &compare_friend_and_current_closest_peer,
2169 ¤t_closest_peer));
2171 /* Compare each finger entry with current_successor and update current_successor
2172 * with finger if its closest. */
2173 // TODO: Change function name to "compare_finger_and_current_closest_peer"
2174 compare_finger_and_current_successor (¤t_closest_peer);
2176 return current_closest_peer;
2181 * FIXME; Send put message across all the trail to reach to next hop to handle
2183 * Construct a Put message and send it to target_peer.
2184 * @param key Key for the content
2185 * @param block_type Type of the block
2186 * @param options Routing options
2187 * @param desired_replication_level Desired replication count
2188 * @param best_known_dest Peer to which this message should reach eventually,
2189 * as it is best known destination to me.
2190 * @param intermediate_trail_id Trail id in case
2191 * @param target_peer Peer to which this message will be forwarded.
2192 * @param hop_count Number of hops traversed so far.
2193 * @param put_path_length Total number of peers in @a put_path
2194 * @param put_path Number of peers traversed so far
2195 * @param expiration_time When does the content expire
2196 * @param data Content to store
2197 * @param data_size Size of content @a data in bytes
2200 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2201 enum GNUNET_BLOCK_Type block_type,
2202 enum GNUNET_DHT_RouteOption options,
2203 uint32_t desired_replication_level,
2204 struct GNUNET_PeerIdentity best_known_dest,
2205 struct GNUNET_HashCode intermediate_trail_id,
2206 struct GNUNET_PeerIdentity *target_peer,
2208 uint32_t put_path_length,
2209 struct GNUNET_PeerIdentity *put_path,
2210 struct GNUNET_TIME_Absolute expiration_time,
2211 const void *data, size_t data_size)
2213 struct PeerPutMessage *ppm;
2214 struct P2PPendingMessage *pending;
2215 struct FriendInfo *target_friend;
2216 struct GNUNET_PeerIdentity *pp;
2217 struct GNUNET_PeerIdentity next_hop;
2221 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2222 sizeof (struct PeerPutMessage);
2224 #if ENABLE_MALICIOUS
2225 /*Call is made to this function from
2227 2. Every peer to construct a pending message and send it to next peer.
2228 In case of 2nd, this case should have been handled in handle_dht_p2p_put/get
2229 No need to check here. First peer can never be malicious. IDEALLY we DONOT
2230 need the condition here. REMOVE IT AFTERWARDS once verified.*/
2231 if(1 == act_malicious)
2236 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2238 put_path_length = 0;
2239 msize = data_size + sizeof (struct PeerPutMessage);
2242 /* Should it be GNUNET_SERVER_MAX_MESSAGE_SIZE? */
2243 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2245 DEBUG("msize = %lu\n",msize);
2250 /* This is the first call made from clients file. So, we should search for the
2252 if (NULL == target_peer)
2255 struct Closest_Peer successor;
2257 memcpy (&key_value, key, sizeof (uint64_t));
2258 key_value = GNUNET_ntohll (key_value);
2260 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2261 best_known_dest = successor.best_known_destination;
2262 next_hop = successor.next_hop;
2263 intermediate_trail_id = successor.trail_id;
2265 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2267 /* I am the destination. */
2268 DEBUG("PUT destination is me = %s,key =%s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2269 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2270 block_type,data_size,data);
2274 GNUNET_assert (NULL !=
2276 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2280 GNUNET_assert (NULL !=
2282 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2285 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2286 pending->timeout = expiration_time;
2287 ppm = (struct PeerPutMessage *) &pending[1];
2288 pending->msg = &ppm->header;
2289 ppm->header.size = htons (msize);
2290 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2291 ppm->options = htonl (options);
2292 ppm->block_type = htonl (block_type);
2293 ppm->hop_count = htonl (hop_count + 1);
2294 ppm->desired_replication_level = htonl (desired_replication_level);
2295 ppm->put_path_length = htonl (put_path_length);
2296 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2297 ppm->best_known_destination = best_known_dest;
2300 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2301 if (put_path_length != 0)
2303 memcpy (pp, put_path,
2304 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2306 memcpy (&pp[put_path_length], data, data_size);
2307 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2308 target_friend->pending_count++;
2309 process_friend_queue (target_friend);
2314 * FIXME; Send get message across all the trail to reach to next hop to handle
2316 * Construct a Get message and send it to target_peer.
2317 * @param key Key for the content
2318 * @param block_type Type of the block
2319 * @param options Routing options
2320 * @param desired_replication_level Desired replication count
2321 * @param best_known_dest Peer which should get this message. Same as target peer
2322 * if best_known_dest is a friend else its a finger.
2323 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2324 * in case it is a finger else set to 0.
2325 * @param target_peer Peer to which this message will be forwarded.
2326 * @param hop_count Number of hops traversed so far.
2327 * @param data Content to store
2328 * @param data_size Size of content @a data in bytes
2329 * @param get_path_length Total number of peers in @a get_path
2330 * @param get_path Number of peers traversed so far
2333 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2334 enum GNUNET_BLOCK_Type block_type,
2335 enum GNUNET_DHT_RouteOption options,
2336 uint32_t desired_replication_level,
2337 struct GNUNET_PeerIdentity best_known_dest,
2338 struct GNUNET_HashCode intermediate_trail_id,
2339 struct GNUNET_PeerIdentity *target_peer,
2341 uint32_t get_path_length,
2342 struct GNUNET_PeerIdentity *get_path)
2344 struct PeerGetMessage *pgm;
2345 struct P2PPendingMessage *pending;
2346 struct FriendInfo *target_friend;
2347 struct GNUNET_PeerIdentity *gp;
2350 msize = sizeof (struct PeerGetMessage) +
2351 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2353 #if ENABLE_MALICIOUS
2354 if(1 == act_malicious)
2359 //GNUNET_SERVER_MAX_MESSAGE_SIZE
2360 /* FIXME:TODO:URGENTHere you can try to optimize it a bit. In case the get path contains you
2361 or your friend then shorten the path. */
2362 /* In this case we don't make get_path_length = 0, as we need get path to
2363 * return the message back to querying client. */
2364 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2370 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
2372 /* This is the first time we got request from our own client file. */
2373 if (NULL == target_peer)
2376 struct Closest_Peer successor;
2378 memcpy (&key_value, key, sizeof (uint64_t));
2379 key_value = GNUNET_ntohll (key_value);
2380 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2382 best_known_dest = successor.best_known_destination;
2383 intermediate_trail_id = successor.trail_id;
2385 /* I am the destination. I have the data. */
2386 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2389 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2390 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2391 NULL, 0, 1, &my_identity, NULL,&my_identity);
2397 GNUNET_assert (NULL !=
2399 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2400 &successor.next_hop)));
2406 GNUNET_assert (NULL !=
2408 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2411 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2412 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2413 pending->importance = 0; /* FIXME */
2414 pgm = (struct PeerGetMessage *) &pending[1];
2415 pending->msg = &pgm->header;
2416 pgm->header.size = htons (msize);
2417 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2418 pgm->get_path_length = htonl (get_path_length);
2419 pgm->best_known_destination = best_known_dest;
2421 pgm->intermediate_trail_id = intermediate_trail_id;
2422 pgm->hop_count = htonl (hop_count + 1);
2423 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2425 if (get_path_length != 0)
2427 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2430 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2431 target_friend->pending_count++;
2432 process_friend_queue (target_friend);
2437 * Send the get result to requesting client.
2438 * @param key Key of the requested data.
2439 * @param type Block type
2440 * @param target_peer Next peer to forward the message to.
2441 * @param source_peer Peer which has the data for the key.
2442 * @param put_path_length Number of peers in @a put_path
2443 * @param put_path Path taken to put the data at its stored location.
2444 * @param get_path_length Number of peers in @a get_path
2445 * @param get_path Path taken to reach to the location of the key.
2446 * @param expiration When will this result expire?
2447 * @param data Payload to store
2448 * @param data_size Size of the @a data
2451 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2452 enum GNUNET_BLOCK_Type type,
2453 const struct GNUNET_PeerIdentity *target_peer,
2454 const struct GNUNET_PeerIdentity *source_peer,
2455 unsigned int put_path_length,
2456 const struct GNUNET_PeerIdentity *put_path,
2457 unsigned int get_path_length,
2458 const struct GNUNET_PeerIdentity *get_path,
2459 struct GNUNET_TIME_Absolute expiration,
2460 const void *data, size_t data_size)
2462 struct PeerGetResultMessage *get_result;
2463 struct GNUNET_PeerIdentity *paths;
2464 struct P2PPendingMessage *pending;
2465 struct FriendInfo *target_friend;
2466 int current_path_index;
2469 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2471 sizeof (struct PeerGetResultMessage);
2473 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2475 put_path_length = 0;
2476 msize = msize - put_path_length;
2480 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2485 DEBUG("GET RESULT FOR DATA_SIZE = %lu\n",msize);
2486 current_path_index = 0;
2487 if(get_path_length > 0)
2489 current_path_index = search_my_index(get_path, get_path_length);
2490 if (-1 == current_path_index)
2495 if ((get_path_length + 1) == current_path_index)
2497 DEBUG ("Peer found twice in get path. Not allowed \n");
2502 if (0 == current_path_index)
2504 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2505 get_path, put_path_length,
2506 put_path, type, data_size, data);
2510 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2511 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2512 pending->importance = 0;
2513 get_result = (struct PeerGetResultMessage *)&pending[1];
2514 pending->msg = &get_result->header;
2515 get_result->header.size = htons (msize);
2516 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2517 get_result->key = *key;
2518 get_result->querying_peer = *source_peer;
2519 get_result->expiration_time = expiration;
2520 get_result->get_path_length = htonl (get_path_length);
2521 get_result->put_path_length = htonl (put_path_length);
2522 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2523 memcpy (paths, put_path,
2524 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2525 memcpy (&paths[put_path_length], get_path,
2526 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2527 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2529 GNUNET_assert (NULL !=
2531 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2532 &get_path[current_path_index - 1])));
2533 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2534 target_friend->pending_count++;
2535 process_friend_queue (target_friend);
2540 * Randomly choose one of your friends (which is not congested and have not crossed
2541 * trail threshold) from the friend_peermap
2542 * @return Friend Randomly chosen friend.
2543 * NULL in case friend peermap is empty, or all the friends are either
2544 * congested or have crossed trail threshold.
2546 static struct FriendInfo *
2547 select_random_friend ()
2549 unsigned int current_size;
2552 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2553 struct GNUNET_PeerIdentity key_ret;
2554 struct FriendInfo *friend;
2556 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2559 if (0 == current_size)
2562 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2563 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2565 /* Iterate till you don't reach to index. */
2566 for (j = 0; j < index ; j++)
2567 GNUNET_assert (GNUNET_YES ==
2568 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2572 /* Reset the index in friend peermap to 0 as we reached to the end. */
2573 if (j == current_size)
2576 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2577 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2581 /* Get the friend stored at the index, j*/
2582 GNUNET_assert (GNUNET_YES ==
2583 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2585 (const void **)&friend));
2587 /* This friend is not congested and has not crossed trail threshold. */
2588 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2589 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2595 } while (j != index);
2597 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2603 * Compute 64 bit value of finger_identity corresponding to a finger index using
2605 * For all fingers, n.finger[i] = n + pow (2,i),
2606 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2607 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2608 * @param finger_index Index corresponding to which we calculate 64 bit value.
2609 * @return 64 bit value.
2612 compute_finger_identity_value (unsigned int finger_index)
2616 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2617 // TODO: Check how and if to use ntohll
2618 my_id64 = GNUNET_ntohll (my_id64);
2620 /* Are we looking for immediate predecessor? */
2621 if (PREDECESSOR_FINGER_ID == finger_index)
2622 return (my_id64 - 1);
2625 uint64_t add = (uint64_t)1 << finger_index;
2626 return (my_id64 + add);
2630 //TODO move at top, write comment.
2631 static struct GNUNET_TIME_Relative next_send_time;
2635 * Choose a random friend. Calculate the next finger identity to search,from
2636 * current_search_finger_index. Start looking for the trail to reach to
2637 * finger identity through this random friend.
2639 * @param cls closure for this task
2640 * @param tc the context under which the task is running
2643 send_find_finger_trail_message (void *cls,
2644 const struct GNUNET_SCHEDULER_TaskContext *tc)
2646 struct FriendInfo *target_friend;
2647 struct GNUNET_HashCode trail_id;
2648 struct GNUNET_HashCode intermediate_trail_id;
2649 unsigned int is_predecessor;
2650 uint64_t finger_id_value;
2652 /* Schedule another send_find_finger_trail_message task. */
2653 find_finger_trail_task =
2654 GNUNET_SCHEDULER_add_delayed (next_send_time,
2655 &send_find_finger_trail_message,
2658 /* No space in my routing table. (Source and destination peers also store entries
2659 * in their routing table). */
2660 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2664 target_friend = select_random_friend ();
2665 if (NULL == target_friend)
2670 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2672 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2677 /* Generate a unique trail id for trail we are trying to setup. */
2678 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2679 &trail_id, sizeof (trail_id));
2680 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2682 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2683 target_friend->id, target_friend, 0, NULL,
2684 is_predecessor, trail_id,
2685 intermediate_trail_id);
2690 * In case there are already maximum number of possible trails to reach to a
2691 * finger, then check if the new trail's length is lesser than any of the
2693 * If yes then replace that old trail by new trail.
2695 * Note: Here we are taking length as a parameter to choose the best possible
2696 * trail, but there could be other parameters also like:
2697 * 1. duration of existence of a trail - older the better.
2698 * 2. if the new trail is completely disjoint than the
2699 * other trails, then may be choosing it is better.
2701 * @param existing_finger
2702 * @param new_finger_trail
2703 * @param new_finger_trail_length
2704 * @param new_finger_trail_id
2707 select_and_replace_trail (struct FingerInfo *existing_finger,
2708 const struct GNUNET_PeerIdentity *new_trail,
2709 unsigned int new_trail_length,
2710 struct GNUNET_HashCode new_trail_id)
2712 struct Trail *trail_list_iterator;
2713 unsigned int largest_trail_length;
2714 unsigned int largest_trail_index;
2715 struct Trail_Element *trail_element;
2718 largest_trail_length = new_trail_length;
2719 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2721 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2723 for (i = 0; i < existing_finger->trails_count; i++)
2725 trail_list_iterator = &existing_finger->trail_list[i];
2726 if (trail_list_iterator->trail_length > largest_trail_length)
2728 largest_trail_length = trail_list_iterator->trail_length;
2729 largest_trail_index = i;
2733 /* New trail is not better than existing ones. Send trail teardown. */
2734 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2736 struct GNUNET_PeerIdentity next_hop;
2738 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2739 GDS_ROUTING_remove_trail (new_trail_id);
2740 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2741 GDS_ROUTING_SRC_TO_DEST,
2746 /* Send trail teardown message across the replaced trail. */
2747 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2748 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2749 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2750 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2751 GDS_ROUTING_SRC_TO_DEST,
2752 replace_trail->trail_head->peer);
2753 /* Free the trail. */
2754 while (NULL != (trail_element = replace_trail->trail_head))
2756 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2757 replace_trail->trail_tail, trail_element);
2758 GNUNET_free_non_null (trail_element);
2761 /* Add new trial at that location. */
2762 replace_trail->is_present = GNUNET_YES;
2763 replace_trail->trail_length = new_trail_length;
2764 replace_trail->trail_id = new_trail_id;
2765 //FIXME: Do we need to add pointers for head and tail.
2767 while (i < new_trail_length)
2769 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2770 element->peer = new_trail[i];
2772 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2773 replace_trail->trail_tail,
2780 * Check if the new trail to reach to finger is unique or do we already have
2781 * such a trail present for finger.
2782 * @param existing_finger Finger identity
2783 * @param new_trail New trail to reach @a existing_finger
2784 * @param trail_length Total number of peers in new_trail.
2785 * @return #GNUNET_YES if the new trail is unique
2786 * #GNUNET_NO if same trail is already present.
2789 is_new_trail_unique (struct FingerInfo *existing_finger,
2790 const struct GNUNET_PeerIdentity *new_trail,
2791 unsigned int trail_length)
2793 struct Trail *trail_list_iterator;
2794 struct Trail_Element *trail_element;
2797 int trail_unique = GNUNET_NO;
2799 GNUNET_assert (existing_finger->trails_count > 0);
2801 /* Iterate over list of trails. */
2802 for (i = 0; i < existing_finger->trails_count; i++)
2804 trail_list_iterator = &(existing_finger->trail_list[i]);
2805 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2807 /* New trail and existing trail length are not same. */
2808 if (trail_list_iterator->trail_length != trail_length)
2810 trail_unique = GNUNET_YES;
2814 trail_element = trail_list_iterator->trail_head;
2815 GNUNET_assert (trail_element != NULL);
2816 for (j = 0; j < trail_list_iterator->trail_length; j++)
2818 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2819 &trail_element->peer))
2821 trail_unique = GNUNET_YES;
2824 trail_element = trail_element->next;
2828 return trail_unique;
2833 * Add a new trail to existing finger. This function is called only when finger
2834 * is not my own identity or a friend.
2835 * @param existing_finger Finger
2836 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2837 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2838 * @param new_finger_trail_id Unique identifier of the trail.
2841 add_new_trail (struct FingerInfo *existing_finger,
2842 const struct GNUNET_PeerIdentity *new_trail,
2843 unsigned int new_trail_length,
2844 struct GNUNET_HashCode new_trail_id)
2846 struct Trail *trail_list_iterator;
2847 struct FriendInfo *first_friend;
2850 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2856 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2857 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2858 trail_list_iterator->trail_id = new_trail_id;
2859 trail_list_iterator->trail_length = new_trail_length;
2860 existing_finger->trails_count++;
2861 trail_list_iterator->is_present = GNUNET_YES;
2863 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2864 &existing_finger->finger_identity)));
2865 /* If finger is a friend then we never call this function. */
2866 GNUNET_assert (new_trail_length > 0);
2868 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2870 first_friend->trails_count++;
2872 for (i = 0; i < new_trail_length; i++)
2874 struct Trail_Element *element;
2876 element = GNUNET_new (struct Trail_Element);
2877 element->peer = new_trail[i];
2878 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2879 trail_list_iterator->trail_tail,
2882 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2888 * FIXME Check if this function is called for opposite direction if yes then
2889 * take it as parameter.
2890 * Get the next hop to send trail teardown message from routing table and
2891 * then delete the entry from routing table. Send trail teardown message for a
2892 * specific trail of a finger.
2893 * @param finger Finger whose trail is to be removed.
2894 * @param trail List of peers in trail from me to a finger, NOT including
2898 send_trail_teardown (struct FingerInfo *finger,
2899 struct Trail *trail)
2901 struct FriendInfo *friend;
2902 struct GNUNET_PeerIdentity *next_hop;
2904 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2905 GDS_ROUTING_SRC_TO_DEST);
2907 if (NULL == next_hop)
2912 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2915 GNUNET_assert (trail->is_present == GNUNET_YES);
2917 /* Finger is not a friend. */
2918 if (trail->trail_length > 0)
2920 GNUNET_assert (NULL != (friend =
2921 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2922 &trail->trail_head->peer)));
2926 GNUNET_assert (NULL != (friend =
2927 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2928 &finger->finger_identity)));
2931 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2932 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2933 friend->trails_count--;
2934 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2935 GDS_ROUTING_SRC_TO_DEST,
2941 * Send trail teardown message across all the trails to reach to finger.
2942 * @param finger Finger whose all the trail should be freed.
2945 send_all_finger_trails_teardown (struct FingerInfo *finger)
2949 for (i = 0; i < finger->trails_count; i++)
2951 struct Trail *trail;
2953 trail = &finger->trail_list[i];
2954 GNUNET_assert (trail->is_present == GNUNET_YES);
2955 send_trail_teardown (finger, trail);
2956 trail->is_present = GNUNET_NO;
2962 * Free a specific trail
2963 * @param trail List of peers to be freed.
2966 free_trail (struct Trail *trail)
2968 struct Trail_Element *trail_element;
2970 while (NULL != (trail_element = trail->trail_head))
2972 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2975 GNUNET_free_non_null (trail_element);
2977 trail->trail_head = NULL;
2978 trail->trail_tail = NULL;
2983 * Free finger and its trail.
2984 * @param finger Finger to be freed.
2987 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2989 struct Trail *trail;
2992 /* Free all the trails to reach to finger */
2993 for (i = 0; i < finger->trails_count; i++)
2995 trail = &finger->trail_list[i];
2996 //FIXME: Check if there are any missing entry in this list because of
2997 // how we insert. If not then no need of this check.
2998 if (GNUNET_NO == trail->is_present)
3001 if (trail->trail_length > 0)
3005 trail->is_present = GNUNET_NO;
3008 finger->is_present = GNUNET_NO;
3009 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
3014 * Add a new entry in finger table at finger_table_index.
3015 * In case I am my own finger, then we don't have a trail. In case of a friend,
3016 * we have a trail with unique id and '0' trail length.
3017 * In case a finger is a friend, then increment the trails count of the friend.
3018 * @param finger_identity Peer Identity of new finger
3019 * @param finger_trail Trail to reach from me to finger (excluding both end points).
3020 * @param finger_trail_length Total number of peers in @a finger_trail.
3021 * @param trail_id Unique identifier of the trail.
3022 * @param finger_table_index Index in finger table.
3025 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
3026 const struct GNUNET_PeerIdentity *finger_trail,
3027 unsigned int finger_trail_length,
3028 struct GNUNET_HashCode trail_id,
3029 unsigned int finger_table_index)
3031 struct FingerInfo *new_entry;
3032 struct FriendInfo *first_trail_hop;
3033 struct Trail *trail;
3036 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3037 GNUNET_assert (NULL != GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST));
3038 new_entry = GNUNET_new (struct FingerInfo);
3039 new_entry->finger_identity = finger_identity;
3040 new_entry->finger_table_index = finger_table_index;
3041 new_entry->is_present = GNUNET_YES;
3043 /* If the new entry is my own identity. */
3044 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3047 new_entry->trails_count = 0;
3048 finger_table[finger_table_index] = *new_entry;
3049 GNUNET_free (new_entry);
3053 /* If finger is a friend, then we don't actually have a trail.
3054 * Just a trail id */
3055 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3058 new_entry->trail_list[0].trail_id = trail_id;
3059 new_entry->trails_count = 1;
3060 new_entry->trail_list[0].is_present = GNUNET_YES;
3061 new_entry->trail_list[0].trail_length = 0;
3062 new_entry->trail_list[0].trail_head = NULL;
3063 new_entry->trail_list[0].trail_tail = NULL;
3064 finger_table[finger_table_index] = *new_entry;
3065 GNUNET_assert (NULL !=
3067 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3068 &finger_identity)));
3070 first_trail_hop->trails_count++;
3071 GNUNET_free (new_entry);
3075 GNUNET_assert (NULL !=
3077 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3078 &finger_trail[0])));
3079 new_entry->trails_count = 1;
3080 first_trail_hop->trails_count++;
3082 /* Copy the finger trail into trail. */
3083 trail = GNUNET_new (struct Trail);
3084 while (i < finger_trail_length)
3086 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3088 element->next = NULL;
3089 element->prev = NULL;
3090 element->peer = finger_trail[i];
3091 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3097 /* Add trail to trail list. */
3098 new_entry->trail_list[0].trail_head = trail->trail_head;
3099 new_entry->trail_list[0].trail_tail = trail->trail_tail;
3100 new_entry->trail_list[0].trail_length = finger_trail_length;
3101 new_entry->trail_list[0].trail_id = trail_id;
3102 new_entry->trail_list[0].is_present = GNUNET_YES;
3103 finger_table[finger_table_index] = *new_entry;
3104 GNUNET_free (new_entry);
3110 * Scan the trail to check if there is any other friend in the trail other than
3111 * first hop. If yes then shortcut the trail, send trail compression message to
3112 * peers which are no longer part of trail and send back the updated trail
3113 * and trail_length to calling function.
3114 * @param finger_identity Finger whose trail we will scan.
3115 * @param finger_trail [in, out] Trail to reach from source to finger,
3116 * @param finger_trail_length Total number of peers in original finger_trail.
3117 * @param finger_trail_id Unique identifier of the finger trail.
3118 * @return updated trail length in case we shortcut the trail, else original
3121 static struct GNUNET_PeerIdentity *
3122 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
3123 const struct GNUNET_PeerIdentity *trail,
3124 unsigned int trail_length,
3125 struct GNUNET_HashCode trail_id,
3126 int *new_trail_length)
3128 struct FriendInfo *target_friend;
3129 struct GNUNET_PeerIdentity *new_trail;
3132 /* I am my own finger. */
3133 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3135 *new_trail_length = 0;
3139 if (0 == trail_length)
3141 *new_trail_length = 0;
3145 /* If finger identity is a friend. */
3146 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3148 *new_trail_length = 0;
3150 /* If there is trail to reach this finger/friend */
3151 if (trail_length > 0)
3153 /* Finger is your first friend. */
3154 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3155 GNUNET_assert (NULL !=
3157 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3161 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3162 trail_id, finger_identity,
3168 /* For other cases, when its neither a friend nor my own identity.*/
3169 for (i = trail_length - 1; i > 0; i--)
3171 /* If the element at this index in trail is a friend. */
3172 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3174 struct FriendInfo *target_friend;
3177 GNUNET_assert (NULL !=
3179 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3181 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3182 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3187 /* Copy the trail from index i to index (trail_length -1) into a new trail
3188 * and update new trail length */
3189 *new_trail_length = trail_length - i;
3190 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (*new_trail_length));
3191 while (i < trail_length)
3193 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3201 /* If we did not compress the trail, return the original trail back.*/
3202 *new_trail_length = trail_length;
3203 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3204 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3210 * Periodic task to verify current successor. There can be multiple trails to reach
3211 * to successor, choose the shortest one and send verify successor message
3212 * across that trail.
3213 * @param cls closure for this task
3214 * @param tc the context under which the task is running
3217 send_verify_successor_message (void *cls,
3218 const struct GNUNET_SCHEDULER_TaskContext *tc)
3220 struct FriendInfo *target_friend;
3221 struct GNUNET_HashCode trail_id;
3223 struct GNUNET_TIME_Relative next_send_time;
3224 struct Trail *trail;
3225 struct Trail_Element *element;
3226 unsigned int trail_length;
3228 struct FingerInfo *successor;
3230 /* Schedule another send_find_finger_trail_message task. */
3231 next_send_time.rel_value_us =
3232 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3233 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3234 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3235 send_verify_successor_task =
3236 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3239 successor = &finger_table[0];
3240 for (i = 0; i < successor->trails_count; i++)
3242 trail = &successor->trail_list[i];
3243 if(GNUNET_YES == trail->is_present)
3247 if (i == successor->trails_count)
3250 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3251 &successor->finger_identity));
3253 /* Trail stored at this index. */
3254 GNUNET_assert (GNUNET_YES == trail->is_present);
3256 trail_id = trail->trail_id;
3258 GNUNET_assert (NULL != GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST));
3259 trail_length = trail->trail_length;
3261 if (trail_length > 0)
3263 /* Copy the trail into peer list. */
3264 struct GNUNET_PeerIdentity peer_list[trail_length];
3266 element = trail->trail_head;
3267 while (j < trail_length)
3269 peer_list[j] = element->peer;
3270 element = element->next;
3274 GNUNET_assert (NULL != (target_friend =
3275 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3277 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3278 successor->finger_identity,
3279 trail_id, peer_list, trail_length,
3285 GNUNET_assert (NULL != (target_friend =
3286 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3287 &successor->finger_identity)));
3288 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3289 successor->finger_identity,
3298 * FIXME: should this be a periodic task, incrementing the search finger index?
3299 * Update the current search finger index.
3301 * FIXME document parameters!
3304 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3305 unsigned int finger_table_index)
3307 struct FingerInfo *successor;
3309 /* FIXME correct this: only move current index periodically */
3310 if (finger_table_index != current_search_finger_index)
3313 successor = &finger_table[0];
3314 GNUNET_assert (GNUNET_YES == successor->is_present);
3316 /* We were looking for immediate successor. */
3317 if (0 == current_search_finger_index)
3319 /* Start looking for immediate predecessor. */
3320 current_search_finger_index = PREDECESSOR_FINGER_ID;
3322 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3324 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3325 send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3331 current_search_finger_index = current_search_finger_index - 1;
3337 * Get the least significant bit set in val.
3340 * @return Position of first bit set, 65 in case of error.
3343 find_set_bit (uint64_t val)
3363 return 65; /* Some other bit was set to 1 as well. */
3370 * Calculate finger_table_index from initial 64 bit finger identity value that
3371 * we send in trail setup message.
3372 * @param ultimate_destination_finger_value Value that we calculated from our
3373 * identity and finger_table_index.
3374 * @param is_predecessor Is the entry for predecessor or not?
3375 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3376 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3379 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3380 unsigned int is_predecessor)
3384 unsigned int finger_table_index;
3386 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3387 my_id64 = GNUNET_ntohll (my_id64);
3389 /* Is this a predecessor finger? */
3390 if (1 == is_predecessor)
3392 diff = my_id64 - ultimate_destination_finger_value;
3394 finger_table_index = PREDECESSOR_FINGER_ID;
3396 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3401 diff = ultimate_destination_finger_value - my_id64;
3402 finger_table_index = find_set_bit (diff);
3404 return finger_table_index;
3409 * Remove finger and its associated data structures from finger table.
3410 * @param finger Finger to be removed.
3413 remove_existing_finger (struct FingerInfo *existing_finger,
3414 unsigned int finger_table_index)
3416 struct FingerInfo *finger;
3418 finger = &finger_table[finger_table_index];
3419 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3420 &existing_finger->finger_identity));
3421 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3424 GNUNET_assert (GNUNET_YES == finger->is_present);
3426 /* If I am my own finger, then we have no trails. */
3427 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3430 finger->is_present = GNUNET_NO;
3431 memset ((void *)&finger_table[finger_table_index], 0,
3432 sizeof (finger_table[finger_table_index]));
3436 /* For all other fingers, send trail teardown across all the trails to reach
3437 finger, and free the finger. */
3438 send_all_finger_trails_teardown (finger);
3439 free_finger (finger, finger_table_index);
3445 * Check if there is already an entry in finger_table at finger_table_index.
3446 * We get the finger_table_index from 64bit finger value we got from the network.
3447 * -- If yes, then select the closest finger.
3448 * -- If new and existing finger are same, then check if you can store more
3450 * -- If yes then add trail, else keep the best trails to reach to the
3452 * -- If the new finger is closest, remove the existing entry, send trail
3453 * teardown message across all the trails to reach the existing entry.
3454 * Add the new finger.
3455 * -- If new and existing finger are different, and existing finger is closest
3457 * -- Update current_search_finger_index.
3458 * @param finger_identity Peer Identity of new finger
3459 * @param finger_trail Trail to reach the new finger
3460 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3461 * @param is_predecessor Is this entry for predecessor in finger_table?
3462 * @param finger_value 64 bit value of finger identity that we got from network.
3463 * @param finger_trail_id Unique identifier of @finger_trail.
3466 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3467 const struct GNUNET_PeerIdentity *finger_trail,
3468 unsigned int finger_trail_length,
3469 unsigned int is_predecessor,
3470 uint64_t finger_value,
3471 struct GNUNET_HashCode finger_trail_id)
3473 struct FingerInfo *existing_finger;
3474 const struct GNUNET_PeerIdentity *closest_peer;
3475 struct FingerInfo *successor;
3476 int updated_finger_trail_length;
3477 unsigned int finger_table_index;
3479 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3480 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3482 /* Invalid finger_table_index. */
3483 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3485 GNUNET_break_op (0);
3489 /* New entry same as successor. */
3490 if ((0 != finger_table_index) &&
3491 (PREDECESSOR_FINGER_ID != finger_table_index))
3493 successor = &finger_table[0];
3494 if (GNUNET_NO == successor->is_present)
3496 GNUNET_break_op (0);
3499 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3500 &successor->finger_identity))
3502 current_search_finger_index = 0;
3503 /* We slow down the find_finger_trail_task as we have completed the circle. */
3504 next_send_time = GNUNET_TIME_STD_BACKOFF(next_send_time);
3509 struct FingerInfo prev_finger;
3510 prev_finger = finger_table[finger_table_index - 1];
3511 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3512 &prev_finger.finger_identity))
3514 current_search_finger_index--;
3519 existing_finger = &finger_table[finger_table_index];
3521 /* No entry present in finger_table for given finger map index. */
3522 if (GNUNET_NO == existing_finger->is_present)
3524 struct GNUNET_PeerIdentity *updated_trail;
3526 /* Shorten the trail if possible. */
3527 updated_finger_trail_length = finger_trail_length;
3528 updated_trail = scan_and_compress_trail (finger_identity, finger_trail,
3529 finger_trail_length,
3531 &updated_finger_trail_length);
3532 add_new_finger (finger_identity, updated_trail,
3533 updated_finger_trail_length,
3534 finger_trail_id, finger_table_index);
3535 GNUNET_free_non_null(updated_trail);
3536 update_current_search_finger_index (finger_identity,
3537 finger_table_index);
3542 /* If existing entry and finger identity are not same. */
3543 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3546 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3551 /* If the new finger is the closest peer. */
3552 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3554 struct GNUNET_PeerIdentity *updated_trail;
3555 /* Shorten the trail if possible. */
3556 updated_finger_trail_length = finger_trail_length;
3558 scan_and_compress_trail (finger_identity, finger_trail,
3559 finger_trail_length, finger_trail_id,
3560 &updated_finger_trail_length);
3561 remove_existing_finger (existing_finger, finger_table_index);
3562 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3563 finger_trail_id, finger_table_index);
3564 GNUNET_free_non_null((struct GNUNET_PeerIdentity *)updated_trail);
3568 /* Existing finger is the closest one. We need to send trail teardown
3569 across the trail setup in routing table of all the peers. */
3570 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3572 if (finger_trail_length > 0)
3573 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3574 GDS_ROUTING_SRC_TO_DEST,
3577 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3578 GDS_ROUTING_SRC_TO_DEST,
3585 /* If both new and existing entry are same as my_identity, then do nothing. */
3586 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3591 /* If the existing finger is not a friend. */
3593 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3594 &existing_finger->finger_identity))
3596 struct GNUNET_PeerIdentity *updated_trail;
3598 /* Shorten the trail if possible. */
3599 updated_finger_trail_length = finger_trail_length;
3601 scan_and_compress_trail (finger_identity, finger_trail,
3602 finger_trail_length, finger_trail_id,
3603 &updated_finger_trail_length);
3604 /* If there is space to store more trails. */
3605 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3606 add_new_trail (existing_finger, updated_trail,
3607 updated_finger_trail_length, finger_trail_id);
3609 select_and_replace_trail (existing_finger, updated_trail,
3610 updated_finger_trail_length, finger_trail_id);
3614 update_current_search_finger_index (finger_identity, finger_table_index);
3620 * FIXME: Check for loop in the request. If you already are part of put path,
3621 * then you need to reset the put path length.
3622 * Core handler for P2P put messages.
3623 * @param cls closure
3624 * @param peer sender of the request
3625 * @param message message
3626 * @return #GNUNET_OK to keep the connection open,
3627 * #GNUNET_SYSERR to close it (signal serious error)
3630 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3631 const struct GNUNET_MessageHeader *message)
3633 struct PeerPutMessage *put;
3634 struct GNUNET_PeerIdentity *put_path;
3635 struct GNUNET_PeerIdentity best_known_dest;
3636 struct GNUNET_HashCode intermediate_trail_id;
3637 struct GNUNET_PeerIdentity *next_hop;
3638 enum GNUNET_DHT_RouteOption options;
3639 struct GNUNET_HashCode test_key;
3643 size_t payload_size;
3646 #if ENABLE_MALICIOUS
3647 if(1 == act_malicious)
3649 DEBUG("I am malicious,dropping put request. \n");
3654 msize = ntohs (message->size);
3655 if (msize < sizeof (struct PeerPutMessage))
3657 GNUNET_break_op (0);
3661 put = (struct PeerPutMessage *) message;
3662 putlen = ntohl (put->put_path_length);
3666 sizeof (struct PeerPutMessage) +
3667 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3669 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3671 GNUNET_break_op (0);
3674 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
3675 GNUNET_STATISTICS_update (GDS_stats,
3677 ("# Bytes received from other peers"), (int64_t) msize,
3680 best_known_dest = put->best_known_destination;
3681 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3682 payload = &put_path[putlen];
3683 options = ntohl (put->options);
3684 intermediate_trail_id = put->intermediate_trail_id;
3686 payload_size = msize - (sizeof (struct PeerPutMessage) +
3687 putlen * sizeof (struct GNUNET_PeerIdentity));
3689 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3690 payload, payload_size, &test_key))
3693 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3695 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3696 GNUNET_break_op (0);
3697 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3698 "PUT with key `%s' for block with key %s\n",
3699 put_s, GNUNET_h2s_full (&test_key));
3700 GNUNET_free (put_s);
3705 GNUNET_break_op (0);
3708 /* cannot verify, good luck */
3712 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3714 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3715 ntohl (put->block_type),
3717 NULL, 0, /* bloom filer */
3718 NULL, 0, /* xquery */
3719 payload, payload_size))
3721 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3722 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3725 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3726 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3727 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3728 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3729 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3730 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3732 GNUNET_break_op (0);
3738 /* Check if you are present in the trail already. */
3740 for (i = 0; i < putlen; i++)
3742 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3749 //FIXME: always add yourself to the peer list not the sender.
3750 /* extend 'put path' by sender */
3751 struct GNUNET_PeerIdentity pp[putlen + 1];
3752 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3754 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3761 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3762 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3764 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3765 GDS_ROUTING_SRC_TO_DEST);
3766 if (NULL == next_hop)
3768 GNUNET_STATISTICS_update (GDS_stats,
3769 gettext_noop ("# Next hop to forward the packet not found "
3770 "trail setup request, packet dropped."),
3772 return GNUNET_SYSERR;
3777 struct Closest_Peer successor;
3778 key_value = GNUNET_ntohll (key_value);
3779 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3780 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3781 *next_hop = successor.next_hop;
3782 intermediate_trail_id = successor.trail_id;
3783 best_known_dest = successor.best_known_destination;
3786 GDS_CLIENTS_process_put (options,
3787 ntohl (put->block_type),
3788 ntohl (put->hop_count),
3789 ntohl (put->desired_replication_level),
3791 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3796 /* I am the final destination */
3797 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3799 DEBUG("PUT destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(put->key)));
3800 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3801 &(put->key),putlen, pp, ntohl (put->block_type),
3802 payload_size, payload);
3806 GDS_NEIGHBOURS_send_put (&put->key,
3807 ntohl (put->block_type),ntohl (put->options),
3808 ntohl (put->desired_replication_level),
3809 best_known_dest, intermediate_trail_id, next_hop,
3810 ntohl (put->hop_count), putlen, pp,
3811 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3812 payload, payload_size);
3819 * FIXME: Check for loop in the request. If you already are part of get path,
3820 * then you need to reset the get path length.
3821 * Core handler for p2p get requests.
3823 * @param cls closure
3824 * @param peer sender of the request
3825 * @param message message
3826 * @return #GNUNET_OK to keep the connection open,
3827 * #GNUNET_SYSERR to close it (signal serious error)
3830 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3831 const struct GNUNET_MessageHeader *message)
3833 const struct PeerGetMessage *get;
3834 const struct GNUNET_PeerIdentity *get_path;
3835 struct GNUNET_PeerIdentity best_known_dest;
3836 struct GNUNET_HashCode intermediate_trail_id;
3837 struct GNUNET_PeerIdentity *next_hop;
3838 uint32_t get_length;
3842 #if ENABLE_MALICIOUS
3843 if(1 == act_malicious)
3845 DEBUG("I am malicious,dropping get request. \n");
3850 msize = ntohs (message->size);
3851 if (msize < sizeof (struct PeerGetMessage))
3853 GNUNET_break_op (0);
3857 get = (const struct PeerGetMessage *)message;
3858 get_length = ntohl (get->get_path_length);
3859 best_known_dest = get->best_known_destination;
3860 intermediate_trail_id = get->intermediate_trail_id;
3861 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3864 sizeof (struct PeerGetMessage) +
3865 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3867 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3869 GNUNET_break_op (0);
3872 DEBUG("PUT FOR DATA_SIZE = %lu\n",msize);
3873 GNUNET_STATISTICS_update (GDS_stats,
3875 ("# Bytes received from other peers"), msize,
3878 /* Add sender to get path */
3879 struct GNUNET_PeerIdentity gp[get_length + 1];
3881 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3882 gp[get_length] = *peer;
3883 get_length = get_length + 1;
3885 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3886 key_value = GNUNET_ntohll (key_value);
3888 /* I am not the final destination. I am part of trail to reach final dest. */
3889 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3891 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3892 GDS_ROUTING_SRC_TO_DEST);
3893 if (NULL == next_hop)
3895 GNUNET_STATISTICS_update (GDS_stats,
3896 gettext_noop ("# Next hop to forward the packet not found "
3897 "GET request, packet dropped."),
3899 return GNUNET_SYSERR;
3904 struct Closest_Peer successor;
3906 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3907 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3908 *next_hop = successor.next_hop;
3909 best_known_dest = successor.best_known_destination;
3910 intermediate_trail_id = successor.trail_id;
3913 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3914 get->desired_replication_level, get->get_path_length,
3916 /* I am the final destination. */
3917 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3919 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(get->key)));
3920 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3922 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3923 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3924 get_length = get_length + 1;
3926 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3927 get_length, final_get_path,
3928 &final_get_path[get_length-2], &my_identity);
3932 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3933 get->desired_replication_level, best_known_dest,
3934 intermediate_trail_id, next_hop, 0,
3942 * Core handler for get result
3943 * @param cls closure
3944 * @param peer sender of the request
3945 * @param message message
3946 * @return #GNUNET_OK to keep the connection open,
3947 * #GNUNET_SYSERR to close it (signal serious error)
3950 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3951 const struct GNUNET_MessageHeader *message)
3953 const struct PeerGetResultMessage *get_result;
3954 const struct GNUNET_PeerIdentity *get_path;
3955 const struct GNUNET_PeerIdentity *put_path;
3956 const void *payload;
3957 size_t payload_size;
3959 unsigned int getlen;
3960 unsigned int putlen;
3961 int current_path_index;
3963 msize = ntohs (message->size);
3964 if (msize < sizeof (struct PeerGetResultMessage))
3966 GNUNET_break_op (0);
3970 get_result = (const struct PeerGetResultMessage *)message;
3971 getlen = ntohl (get_result->get_path_length);
3972 putlen = ntohl (get_result->put_path_length);
3975 sizeof (struct PeerGetResultMessage) +
3976 getlen * sizeof (struct GNUNET_PeerIdentity) +
3977 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3979 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3981 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3983 GNUNET_break_op (0);
3986 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3987 GNUNET_STATISTICS_update (GDS_stats,
3989 ("# Bytes received from other peers"), msize,
3992 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3993 get_path = &put_path[putlen];
3994 payload = (const void *) &get_path[getlen];
3995 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3996 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3998 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
4000 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
4001 getlen, get_path, putlen,
4002 put_path, get_result->type, payload_size, payload);
4007 current_path_index = search_my_index (get_path, getlen);
4008 if (-1 == current_path_index )
4010 DEBUG ("No entry found in get path.\n");
4012 return GNUNET_SYSERR;
4014 if((getlen + 1) == current_path_index)
4016 DEBUG("Present twice in get path. Not allowed. \n");
4018 return GNUNET_SYSERR;
4020 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
4021 &get_path[current_path_index - 1],
4022 &(get_result->querying_peer), putlen, put_path,
4023 getlen, get_path, get_result->expiration_time,
4024 payload, payload_size);
4027 return GNUNET_SYSERR;
4032 * Find the next hop to pass trail setup message. First find the local best known
4033 * hop from your own identity, friends and finger. If you were part of trail,
4034 * then get the next hop from routing table. Compare next_hop from routing table
4035 * and local best known hop, and return the closest one to final_dest_finger_val
4036 * @param final_dest_finger_val 64 bit value of finger identity
4037 * @param intermediate_trail_id If you are part of trail to reach to some other
4038 * finger, then it is the trail id to reach to
4039 * that finger, else set to 0.
4040 * @param is_predecessor Are we looking for closest successor or predecessor.
4041 * @param current_dest In case you are part of trail, then finger to which
4042 * we should forward the message. Else my own identity
4043 * @return Closest Peer for @a final_dest_finger_val
4045 static struct Closest_Peer
4046 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
4047 struct GNUNET_HashCode intermediate_trail_id,
4048 unsigned int is_predecessor,
4049 struct GNUNET_PeerIdentity prev_hop,
4050 struct GNUNET_PeerIdentity source,
4051 struct GNUNET_PeerIdentity *current_dest)
4053 struct Closest_Peer peer;
4055 /* Find a local best known peer. */
4056 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
4058 /* Am I just a part of a trail towards a finger (current_destination)? */
4059 /* Select best successor among one found locally and current_destination
4060 * that we got from network.*/
4061 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
4062 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
4065 const struct GNUNET_PeerIdentity *closest_peer;
4067 closest_peer = select_closest_peer (&peer.best_known_destination,
4069 final_dest_finger_val,
4072 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
4073 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
4075 struct GNUNET_PeerIdentity *next_hop;
4077 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4078 GDS_ROUTING_SRC_TO_DEST);
4079 /* It may happen that trail teardown message got delayed and hence,
4080 the previous hop sent the message over intermediate trail id.In that
4081 case next_hop could be NULL. */
4082 if(NULL != next_hop)
4084 peer.next_hop = *next_hop;
4085 peer.best_known_destination = *current_dest;
4086 peer.trail_id = intermediate_trail_id;
4095 * Core handle for PeerTrailSetupMessage.
4096 * @param cls closure
4097 * @param message message
4098 * @param peer peer identity this notification is about
4099 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4102 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
4103 const struct GNUNET_MessageHeader *message)
4105 const struct PeerTrailSetupMessage *trail_setup;
4106 const struct GNUNET_PeerIdentity *trail_peer_list;
4107 struct GNUNET_PeerIdentity current_dest;
4108 struct FriendInfo *target_friend;
4109 struct GNUNET_PeerIdentity source;
4110 uint64_t final_dest_finger_val;
4111 struct GNUNET_HashCode intermediate_trail_id;
4112 struct GNUNET_HashCode trail_id;
4113 unsigned int is_predecessor;
4114 uint32_t trail_length;
4118 msize = ntohs (message->size);
4119 if (msize < sizeof (struct PeerTrailSetupMessage))
4121 GNUNET_break_op (0);
4122 return GNUNET_SYSERR;
4125 trail_setup = (const struct PeerTrailSetupMessage *) message;
4126 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4127 sizeof (struct GNUNET_PeerIdentity) != 0)
4129 GNUNET_break_op (0);
4132 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4133 sizeof (struct GNUNET_PeerIdentity);
4135 GNUNET_STATISTICS_update (GDS_stats,
4137 ("# Bytes received from other peers"), msize,
4140 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4141 current_dest = trail_setup->best_known_destination;
4142 trail_id = trail_setup->trail_id;
4143 final_dest_finger_val =
4144 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4145 source = trail_setup->source_peer;
4146 is_predecessor = ntohl (trail_setup->is_predecessor);
4147 intermediate_trail_id = trail_setup->intermediate_trail_id;
4149 /* Did the friend insert its ID in the trail list? */
4150 if (trail_length > 0 &&
4151 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
4153 GNUNET_break_op (0);
4154 return GNUNET_SYSERR;
4157 /* If I was the source and got the message back, then set trail length to 0.*/
4158 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4163 /* Check if you are present in the trail seen so far? */
4164 for (i = 0; i < trail_length ; i++)
4166 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4168 trail_length = i; /* Check that you add yourself again */
4173 /* Is my routing table full? */
4174 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4176 GNUNET_assert (NULL !=
4178 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4179 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4180 my_identity, is_predecessor,
4181 trail_peer_list, trail_length,
4182 trail_id, target_friend,
4183 CONGESTION_TIMEOUT);
4187 /* Get the next hop to forward the trail setup request. */
4188 struct Closest_Peer next_peer =
4189 get_local_best_known_next_hop (final_dest_finger_val,
4190 intermediate_trail_id,
4196 /* Am I the final destination? */
4197 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4200 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4202 finger_table_add (my_identity, NULL, 0, is_predecessor,
4203 final_dest_finger_val, trail_id);
4207 if (trail_length > 0)
4209 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4210 &trail_peer_list[trail_length-1]);
4213 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4215 if (NULL == target_friend)
4217 GNUNET_break_op (0);
4218 return GNUNET_SYSERR;
4221 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4222 GDS_NEIGHBOURS_send_trail_setup_result (source,
4224 target_friend, trail_length,
4227 final_dest_finger_val,trail_id);
4230 else /* I'm not the final destination. */
4232 GNUNET_assert (NULL !=
4234 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4235 &next_peer.next_hop)));
4237 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4239 /* Add yourself to list of peers. */
4240 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4242 memcpy (peer_list, trail_peer_list,
4243 trail_length * sizeof (struct GNUNET_PeerIdentity));
4244 peer_list[trail_length] = my_identity;
4246 GDS_NEIGHBOURS_send_trail_setup (source,
4247 final_dest_finger_val,
4248 next_peer.best_known_destination,
4249 target_friend, trail_length + 1, peer_list,
4250 is_predecessor, trail_id,
4251 next_peer.trail_id);
4252 GNUNET_free_non_null (peer_list);
4255 GDS_NEIGHBOURS_send_trail_setup (source,
4256 final_dest_finger_val,
4257 next_peer.best_known_destination,
4258 target_friend, 0, NULL,
4259 is_predecessor, trail_id,
4260 next_peer.trail_id);
4267 * Core handle for p2p trail setup result messages.
4269 * @param message message
4270 * @param peer sender of this message.
4271 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4274 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4275 const struct GNUNET_MessageHeader *message)
4277 const struct PeerTrailSetupResultMessage *trail_result;
4278 const struct GNUNET_PeerIdentity *trail_peer_list;
4279 struct GNUNET_PeerIdentity next_hop;
4280 struct FriendInfo *target_friend;
4281 struct GNUNET_PeerIdentity querying_peer;
4282 struct GNUNET_PeerIdentity finger_identity;
4283 uint32_t trail_length;
4284 uint64_t ulitmate_destination_finger_value;
4285 uint32_t is_predecessor;
4286 struct GNUNET_HashCode trail_id;
4290 msize = ntohs (message->size);
4291 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4293 GNUNET_break_op (0);
4297 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4298 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4299 sizeof (struct GNUNET_PeerIdentity) != 0)
4301 GNUNET_break_op (0);
4304 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4305 sizeof (struct GNUNET_PeerIdentity);
4307 GNUNET_STATISTICS_update (GDS_stats,
4309 ("# Bytes received from other peers"), msize,
4312 is_predecessor = ntohl (trail_result->is_predecessor);
4313 querying_peer = trail_result->querying_peer;
4314 finger_identity = trail_result->finger_identity;
4315 trail_id = trail_result->trail_id;
4316 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4317 ulitmate_destination_finger_value =
4318 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4320 /* Am I the one who initiated the query? */
4321 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4323 /* Check that you got the message from the correct peer. */
4324 if (trail_length > 0)
4326 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4331 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4335 GDS_ROUTING_add (trail_id, my_identity, *peer);
4336 finger_table_add (finger_identity, trail_peer_list, trail_length,
4337 is_predecessor, ulitmate_destination_finger_value, trail_id);
4341 /* Get my location in the trail. */
4342 my_index = search_my_index (trail_peer_list, trail_length);
4345 DEBUG ("Not found in trail\n");
4347 return GNUNET_SYSERR;
4350 if ((trail_length + 1) == my_index)
4352 DEBUG ("Found twice in trail.\n");
4354 return GNUNET_SYSERR;
4357 //TODO; Refactor code here and above to check if sender peer is correct
4360 if(trail_length > 1)
4361 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4364 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4366 next_hop = trail_result->querying_peer;
4370 if(my_index == trail_length - 1)
4373 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4378 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4380 next_hop = trail_peer_list[my_index - 1];
4383 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4384 if (NULL == target_friend)
4386 GNUNET_break_op (0);
4387 return GNUNET_SYSERR;
4390 GDS_ROUTING_add (trail_id, next_hop, *peer);
4391 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4392 target_friend, trail_length, trail_peer_list,
4394 ulitmate_destination_finger_value,
4402 * @param trail Trail to be inverted
4403 * @param trail_length Total number of peers in the trail.
4404 * @return Updated trail
4406 static struct GNUNET_PeerIdentity *
4407 invert_trail (const struct GNUNET_PeerIdentity *trail,
4408 unsigned int trail_length)
4412 struct GNUNET_PeerIdentity *inverted_trail;
4414 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4417 j = trail_length - 1;
4418 while (i < trail_length)
4420 inverted_trail[i] = trail[j];
4425 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4426 &inverted_trail[0]));
4427 return inverted_trail;
4432 * Return the shortest trail among all the trails to reach to finger from me.
4433 * @param finger Finger
4434 * @param shortest_trail_length[out] Trail length of shortest trail from me
4436 * @return Shortest trail.
4438 static struct GNUNET_PeerIdentity *
4439 get_shortest_trail (struct FingerInfo *finger,
4440 unsigned int *trail_length)
4442 struct Trail *trail;
4443 unsigned int flag = 0;
4444 unsigned int shortest_trail_index = 0;
4445 int shortest_trail_length = -1;
4446 struct Trail_Element *trail_element;
4447 struct GNUNET_PeerIdentity *trail_list;
4450 trail = GNUNET_new (struct Trail);
4452 /* Get the shortest trail to reach to current successor. */
4453 for (i = 0; i < finger->trails_count; i++)
4455 trail = &finger->trail_list[i];
4459 shortest_trail_index = i;
4460 shortest_trail_length = trail->trail_length;
4465 if (shortest_trail_length > trail->trail_length)
4467 shortest_trail_index = i;
4468 shortest_trail_length = trail->trail_length;
4473 /* Copy the shortest trail and return. */
4474 trail = &finger->trail_list[shortest_trail_index];
4475 trail_element = trail->trail_head;
4477 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4478 shortest_trail_length);
4480 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4482 trail_list[i] = trail_element->peer;
4485 GNUNET_assert(shortest_trail_length != -1);
4487 *trail_length = shortest_trail_length;
4493 * Check if trail_1 and trail_2 have any common element. If yes then join
4494 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4495 * @param trail_1 Trail from source to me, NOT including endpoints.
4496 * @param trail_1_len Total number of peers @a trail_1
4497 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4498 * @param trail_2_len Total number of peers @a trail_2
4499 * @param joined_trail_len Total number of peers in combined trail of trail_1
4501 * @return Joined trail.
4503 static struct GNUNET_PeerIdentity *
4504 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4505 unsigned int trail_1_len,
4506 struct GNUNET_PeerIdentity *trail_2,
4507 unsigned int trail_2_len,
4508 unsigned int *joined_trail_len)
4510 struct GNUNET_PeerIdentity *joined_trail;
4515 for (i = 0; i < trail_1_len; i++)
4517 for (j = 0; j < trail_2_len; j++)
4519 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4522 *joined_trail_len = i + (trail_2_len - j);
4523 joined_trail = GNUNET_malloc (*joined_trail_len *
4524 sizeof(struct GNUNET_PeerIdentity));
4527 /* Copy all the elements from 0 to i into joined_trail. */
4528 for(k = 0; k < ( i+1); k++)
4530 joined_trail[k] = trail_1[k];
4533 /* Increment j as entry stored is same as entry stored at i*/
4536 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4537 while(k <= (*joined_trail_len - 1))
4539 joined_trail[k] = trail_2[j];
4544 return joined_trail;
4548 /* Here you should join the trails. */
4549 *joined_trail_len = trail_1_len + trail_2_len + 1;
4550 joined_trail = GNUNET_malloc (*joined_trail_len *
4551 sizeof(struct GNUNET_PeerIdentity));
4554 for(i = 0; i < trail_1_len;i++)
4556 joined_trail[i] = trail_1[i];
4559 joined_trail[i] = my_identity;
4562 for (j = 0; i < *joined_trail_len; i++,j++)
4564 joined_trail[i] = trail_2[j];
4567 return joined_trail;
4572 * Return the trail from source to my current predecessor. Check if source
4573 * is already part of the this trail, if yes then return the shorten trail.
4574 * @param current_trail Trail from source to me, NOT including the endpoints.
4575 * @param current_trail_length Number of peers in @a current_trail.
4576 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4577 * source to my predecessor, NOT including
4579 * @return Trail from source to my predecessor.
4581 static struct GNUNET_PeerIdentity *
4582 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4583 const struct GNUNET_PeerIdentity *trail_src_to_me,
4584 unsigned int trail_src_to_me_len,
4585 unsigned int *trail_src_to_curr_pred_length)
4587 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4588 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4589 unsigned int trail_me_to_curr_pred_length;
4590 struct FingerInfo *current_predecessor;
4594 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4596 /* Check if trail_src_to_me contains current_predecessor. */
4597 for (i = 0; i < trail_src_to_me_len; i++)
4599 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4600 ¤t_predecessor->finger_identity))
4604 *trail_src_to_curr_pred_length = i;
4609 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4610 sizeof(struct GNUNET_PeerIdentity));
4611 for(j = 0; j < i;j++)
4612 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4613 return trail_src_to_curr_pred;
4617 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4618 &trail_me_to_curr_pred_length);
4620 /* Check if trail contains the source_peer. */
4621 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4623 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4624 &trail_me_to_curr_pred[i]))
4627 /* Source is NOT part of trail. */
4630 /* Source is the last element in the trail to reach to my pred.
4631 Source is direct friend of the pred. */
4632 if (trail_me_to_curr_pred_length == i)
4634 *trail_src_to_curr_pred_length = 0;
4638 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4639 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4640 *trail_src_to_curr_pred_length);
4642 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4644 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4646 GNUNET_free_non_null(trail_me_to_curr_pred);
4647 return trail_src_to_curr_pred;
4651 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4652 trail_src_to_me_len,
4653 trail_me_to_curr_pred,
4654 trail_me_to_curr_pred_length,
4656 *trail_src_to_curr_pred_length = len;
4657 GNUNET_free_non_null(trail_me_to_curr_pred);
4658 return trail_src_to_curr_pred;
4663 * Add finger as your predecessor. To add, first generate a new trail id, invert
4664 * the trail to get the trail from me to finger, add an entry in your routing
4665 * table, send add trail message to peers which are part of trail from me to
4666 * finger and add finger in finger table.
4669 * @param trail_length
4672 update_predecessor (struct GNUNET_PeerIdentity finger,
4673 struct GNUNET_PeerIdentity *trail,
4674 unsigned int trail_length)
4676 struct GNUNET_HashCode trail_to_new_predecessor_id;
4677 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4678 struct FriendInfo *target_friend;
4680 /* Generate trail id for trail from me to new predecessor = finger. */
4681 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4682 &trail_to_new_predecessor_id,
4683 sizeof (trail_to_new_predecessor_id));
4685 /* Finger is a friend. */
4686 if (trail_length == 0)
4688 trail_to_new_predecessor = NULL;
4689 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4690 GNUNET_assert (NULL != (target_friend =
4691 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4696 /* Invert the trail to get the trail from me to finger, NOT including the
4698 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4699 &trail[trail_length-1]));
4701 trail_to_new_predecessor = invert_trail (trail, trail_length);
4703 /* Add an entry in your routing table. */
4704 GDS_ROUTING_add (trail_to_new_predecessor_id,
4706 trail_to_new_predecessor[0]);
4708 GNUNET_assert (NULL != (target_friend =
4709 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4710 &trail_to_new_predecessor[0])));
4711 GNUNET_assert (NULL != (
4712 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4713 &trail[trail_length - 1])));
4716 /* Add entry in routing table of all peers that are part of trail from me
4717 to finger, including finger. */
4718 GDS_NEIGHBOURS_send_add_trail (my_identity,
4720 trail_to_new_predecessor_id,
4721 trail_to_new_predecessor,
4725 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4726 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4727 GNUNET_free_non_null(trail_to_new_predecessor);
4732 * Check if you already have a predecessor. If not then add finger as your
4733 * predecessor. If you have predecessor, then compare two peer identites.
4734 * If finger is correct predecessor, then remove the old entry, add finger in
4735 * finger table and send add_trail message to add the trail in the routing
4736 * table of all peers which are part of trail to reach from me to finger.
4737 * @param finger New peer which may be our predecessor.
4738 * @param trail List of peers to reach from @finger to me.
4739 * @param trail_length Total number of peer in @a trail.
4742 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4743 struct GNUNET_PeerIdentity *trail,
4744 unsigned int trail_length)
4746 struct FingerInfo *current_predecessor;
4747 const struct GNUNET_PeerIdentity *closest_peer;
4748 uint64_t predecessor_value;
4749 unsigned int is_predecessor = 1;
4751 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4753 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4755 /* No predecessor. Add finger as your predecessor. */
4756 if (GNUNET_NO == current_predecessor->is_present)
4758 update_predecessor (finger, trail, trail_length);
4762 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4768 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4769 closest_peer = select_closest_peer (&finger,
4770 ¤t_predecessor->finger_identity,
4771 predecessor_value, is_predecessor);
4773 /* Finger is the closest predecessor. Remove the existing one and add the new
4775 if (closest_peer == &finger)
4777 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4778 update_predecessor (finger, trail, trail_length);
4786 * Core handle for p2p verify successor messages.
4787 * @param cls closure
4788 * @param message message
4789 * @param peer peer identity this notification is about
4790 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4793 handle_dht_p2p_verify_successor(void *cls,
4794 const struct GNUNET_PeerIdentity *peer,
4795 const struct GNUNET_MessageHeader *message)
4797 const struct PeerVerifySuccessorMessage *vsm;
4798 struct GNUNET_HashCode trail_id;
4799 struct GNUNET_PeerIdentity successor;
4800 struct GNUNET_PeerIdentity source_peer;
4801 struct GNUNET_PeerIdentity *trail;
4802 struct GNUNET_PeerIdentity *next_hop;
4803 struct FingerInfo current_predecessor;
4804 struct FriendInfo *target_friend;
4805 unsigned int trail_src_to_curr_pred_len = 0;
4806 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4807 unsigned int trail_length;
4810 msize = ntohs (message->size);
4812 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4814 GNUNET_break_op (0);
4818 vsm = (const struct PeerVerifySuccessorMessage *) message;
4819 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4820 sizeof (struct GNUNET_PeerIdentity);
4821 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4822 sizeof (struct GNUNET_PeerIdentity) != 0)
4824 GNUNET_break_op (0);
4828 GNUNET_STATISTICS_update (GDS_stats,
4830 ("# Bytes received from other peers"), msize,
4833 trail_id = vsm->trail_id;
4834 source_peer = vsm->source_peer;
4835 successor = vsm->successor;
4836 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4839 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4841 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4843 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4844 if (NULL == next_hop)
4846 // GNUNET_break_op (0);
4847 // return GNUNET_SYSERR;
4848 //FIXME: Here it may happen that trail has not yet been added
4849 //in notify successor.
4853 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4855 if(NULL == target_friend)
4860 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4861 trail_id, trail, trail_length,
4866 /* I am the destination of this message. */
4868 /* Check if the source_peer could be our predecessor and if yes then update
4870 compare_and_update_predecessor (source_peer, trail, trail_length);
4871 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4873 /* Is source of this message NOT my predecessor. */
4874 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4877 trail_src_to_curr_pred =
4878 get_trail_src_to_curr_pred (source_peer,
4881 &trail_src_to_curr_pred_len);
4885 trail_src_to_curr_pred_len = trail_length;
4888 trail_src_to_curr_pred =
4889 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4890 *trail_src_to_curr_pred_len);
4891 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4893 trail_src_to_curr_pred[i] = trail[i];
4897 GNUNET_assert (NULL !=
4899 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4900 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4901 current_predecessor.finger_identity,
4902 trail_id, trail_src_to_curr_pred,
4903 trail_src_to_curr_pred_len,
4904 GDS_ROUTING_DEST_TO_SRC,
4906 GNUNET_free_non_null(trail_src_to_curr_pred);
4912 * If the trail from me to my probable successor contains a friend not
4913 * at index 0, then we can shorten the trail.
4914 * @param probable_successor Peer which is our probable successor
4915 * @param trail_me_to_probable_successor Peers in path from me to my probable
4916 * successor, NOT including the endpoints.
4917 * @param trail_me_to_probable_successor_len Total number of peers in
4918 * @a trail_me_to_probable_succesor.
4919 * @return Updated trail, if any friend found.
4920 * Else the trail_me_to_probable_successor.
4922 struct GNUNET_PeerIdentity *
4923 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4924 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4925 unsigned int trail_me_to_probable_successor_len,
4926 unsigned int *trail_to_new_successor_length)
4930 struct GNUNET_PeerIdentity *trail_to_new_successor;
4932 /* Probable successor is a friend */
4933 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4934 &probable_successor))
4936 trail_to_new_successor = NULL;
4937 *trail_to_new_successor_length = 0;
4938 return trail_to_new_successor;
4941 /* Is there any friend of yours in this trail. */
4942 if(trail_me_to_probable_successor_len > 1)
4944 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4946 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4947 &trail_me_to_probable_successor[i]))
4950 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4951 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4952 *trail_to_new_successor_length);
4955 for(j = 0;j < *trail_to_new_successor_length;i++,j++)
4957 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4960 return trail_to_new_successor;
4964 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4965 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4970 * Check if the peer which sent us verify successor result message is still ours
4971 * successor or not. If not, then compare existing successor and probable successor.
4972 * In case probable successor is the correct successor, remove the existing
4973 * successor. Add probable successor as new successor. Send notify new successor
4974 * message to new successor.
4975 * @param curr_succ Peer to which we sent the verify successor message. It may
4976 * or may not be our real current successor, as we may have few iterations of
4977 * find finger trail task.
4978 * @param probable_successor Peer which should be our successor accroding to @a
4980 * @param trail List of peers to reach from me to @a probable successor, NOT including
4982 * @param trail_length Total number of peers in @a trail.
4985 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4986 struct GNUNET_PeerIdentity probable_successor,
4987 const struct GNUNET_PeerIdentity *trail,
4988 unsigned int trail_length)
4990 struct FingerInfo *current_successor;
4991 const struct GNUNET_PeerIdentity *closest_peer;
4992 struct GNUNET_HashCode trail_id;
4993 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4994 struct FriendInfo *target_friend;
4995 unsigned int trail_me_to_probable_succ_len;
4996 unsigned int is_predecessor = GNUNET_NO;
4997 uint64_t successor_value;
4999 current_successor = &finger_table[0];
5000 successor_value = compute_finger_identity_value(0);
5002 /* If probable successor is same as current_successor, do nothing. */
5003 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
5004 ¤t_successor->finger_identity))
5007 closest_peer = select_closest_peer (&probable_successor,
5008 ¤t_successor->finger_identity,
5009 successor_value, is_predecessor);
5011 /* If the current_successor in the finger table is closest, then do nothing. */
5012 if (closest_peer == ¤t_successor->finger_identity)
5014 /* Code for testing ONLY: Store the successor for path tracking */
5015 // track_topology = 1;
5016 if ((NULL != GDS_stats))
5022 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5023 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5024 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5025 GNUNET_free (my_id_str);
5026 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5032 /* Probable successor is the closest peer.*/
5033 if(trail_length > 0)
5035 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5040 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5041 &probable_successor));
5044 trail_me_to_probable_succ_len = 0;
5045 trail_me_to_probable_succ =
5046 check_trail_me_to_probable_succ (probable_successor,
5047 trail, trail_length,
5048 &trail_me_to_probable_succ_len);
5050 /* Remove the existing successor. */
5051 remove_existing_finger (current_successor, 0);
5053 /* TODO URGENT: Check if any peer is present more than once, if yes then shorten
5054 the trail. before sending it across the network. */
5055 /* Generate a new trail id to reach to your new successor. */
5056 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5057 &trail_id, sizeof (trail_id));
5059 if (trail_me_to_probable_succ_len > 0)
5061 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
5062 GNUNET_assert (NULL !=
5064 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5065 &trail_me_to_probable_succ[0])));
5069 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5070 GNUNET_assert (NULL !=
5072 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5073 &probable_successor)));
5076 add_new_finger (probable_successor, trail_me_to_probable_succ,
5077 trail_me_to_probable_succ_len, trail_id, 0);
5079 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
5080 trail_me_to_probable_succ,
5081 trail_me_to_probable_succ_len,
5089 * FIXME: Check for duplicate elements everywhere when you are making
5091 * Core handle for p2p verify successor result messages.
5092 * @param cls closure
5093 * @param message message
5094 * @param peer peer identity this notification is about
5095 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5098 handle_dht_p2p_verify_successor_result(void *cls,
5099 const struct GNUNET_PeerIdentity *peer,
5100 const struct GNUNET_MessageHeader *message)
5102 const struct PeerVerifySuccessorResultMessage *vsrm;
5103 enum GDS_ROUTING_trail_direction trail_direction;
5104 struct GNUNET_PeerIdentity querying_peer;
5105 struct GNUNET_HashCode trail_id;
5106 struct GNUNET_PeerIdentity *next_hop;
5107 struct FriendInfo *target_friend;
5108 struct GNUNET_PeerIdentity probable_successor;
5109 struct GNUNET_PeerIdentity current_successor;
5110 const struct GNUNET_PeerIdentity *trail;
5111 unsigned int trail_length;
5114 msize = ntohs (message->size);
5115 /* We send a trail to reach from old successor to new successor, if
5116 * old_successor != new_successor.*/
5117 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5119 GNUNET_break_op (0);
5123 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5124 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5125 sizeof (struct GNUNET_PeerIdentity);
5127 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5128 sizeof (struct GNUNET_PeerIdentity) != 0)
5130 GNUNET_break_op (0);
5134 GNUNET_STATISTICS_update (GDS_stats,
5136 ("# Bytes received from other peers"), msize,
5139 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5140 querying_peer = vsrm->querying_peer;
5141 trail_direction = ntohl (vsrm->trail_direction);
5142 trail_id = vsrm->trail_id;
5143 probable_successor = vsrm->probable_successor;
5144 current_successor = vsrm->current_successor;
5147 /* I am the querying_peer. */
5148 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5150 compare_and_update_successor (current_successor,
5151 probable_successor, trail, trail_length);
5155 /*If you are not the querying peer then pass on the message */
5156 if(NULL == (next_hop =
5157 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
5162 if (NULL == (target_friend =
5163 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5168 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5169 vsrm->current_successor,
5170 probable_successor, trail_id,
5173 trail_direction, target_friend);
5179 * Core handle for p2p notify new successor messages.
5180 * @param cls closure
5181 * @param message message
5182 * @param peer peer identity this notification is about
5183 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5186 handle_dht_p2p_notify_new_successor(void *cls,
5187 const struct GNUNET_PeerIdentity *peer,
5188 const struct GNUNET_MessageHeader *message)
5190 const struct PeerNotifyNewSuccessorMessage *nsm;
5191 struct GNUNET_PeerIdentity *trail;
5192 struct GNUNET_PeerIdentity source;
5193 struct GNUNET_PeerIdentity new_successor;
5194 struct GNUNET_HashCode trail_id;
5195 struct GNUNET_PeerIdentity next_hop;
5196 struct FriendInfo *target_friend;
5199 uint32_t trail_length;
5201 msize = ntohs (message->size);
5203 /* We have the trail to reach from source to new successor. */
5204 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5206 GNUNET_break_op (0);
5210 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5211 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5212 sizeof (struct GNUNET_PeerIdentity);
5213 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5214 sizeof (struct GNUNET_PeerIdentity) != 0)
5216 GNUNET_break_op (0);
5220 GNUNET_STATISTICS_update (GDS_stats,
5222 ("# Bytes received from other peers"), msize,
5225 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5226 source = nsm->source_peer;
5227 new_successor = nsm->new_successor;
5228 trail_id = nsm->trail_id;
5231 //FIXME: add a check to make sure peer is correct.
5233 /* I am the new_successor to source_peer. */
5234 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5236 if(trail_length > 0)
5237 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5240 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5242 compare_and_update_predecessor (source, trail, trail_length);
5246 GNUNET_assert(trail_length > 0);
5247 /* I am part of trail to reach to successor. */
5248 my_index = search_my_index (trail, trail_length);
5251 DEBUG ("No entry found in trail\n");
5252 GNUNET_break_op (0);
5253 return GNUNET_SYSERR;
5255 if((trail_length + 1) == my_index)
5257 DEBUG ("Found twice in trail.\n");
5258 GNUNET_break_op (0);
5259 return GNUNET_SYSERR;
5261 if ((trail_length-1) == my_index)
5262 next_hop = new_successor;
5264 next_hop = trail[my_index + 1];
5267 /* Add an entry in routing table for trail from source to its new successor. */
5268 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5269 GNUNET_assert (NULL !=
5271 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5272 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5274 trail_id, target_friend);
5281 * Core handler for P2P trail rejection message
5282 * @param cls closure
5283 * @param message message
5284 * @param peer peer identity this notification is about
5285 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5288 handle_dht_p2p_trail_setup_rejection (void *cls,
5289 const struct GNUNET_PeerIdentity *peer,
5290 const struct GNUNET_MessageHeader *message)
5292 const struct PeerTrailRejectionMessage *trail_rejection;
5293 unsigned int trail_length;
5294 const struct GNUNET_PeerIdentity *trail_peer_list;
5295 struct FriendInfo *target_friend;
5296 struct GNUNET_TIME_Relative congestion_timeout;
5297 struct GNUNET_HashCode trail_id;
5298 struct GNUNET_PeerIdentity next_peer;
5299 struct GNUNET_PeerIdentity source;
5300 struct GNUNET_PeerIdentity *next_hop;
5301 uint64_t ultimate_destination_finger_value;
5302 unsigned int is_predecessor;
5305 msize = ntohs (message->size);
5306 /* We are passing the trail setup so far. */
5307 if (msize < sizeof (struct PeerTrailRejectionMessage))
5309 GNUNET_break_op (0);
5313 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5314 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5315 sizeof (struct GNUNET_PeerIdentity);
5316 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5317 sizeof (struct GNUNET_PeerIdentity) != 0)
5319 GNUNET_break_op (0);
5323 GNUNET_STATISTICS_update (GDS_stats,
5325 ("# Bytes received from other peers"), msize,
5328 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5329 is_predecessor = ntohl (trail_rejection->is_predecessor);
5330 congestion_timeout = trail_rejection->congestion_time;
5331 source = trail_rejection->source_peer;
5332 trail_id = trail_rejection->trail_id;
5333 ultimate_destination_finger_value =
5334 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5336 /* First set the congestion time of the friend that sent you this message. */
5337 GNUNET_assert (NULL !=
5339 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5340 target_friend->congestion_timestamp =
5341 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5342 congestion_timeout);
5344 /* I am the source peer which wants to setup the trail. Do nothing.
5345 * send_find_finger_trail_task is scheduled periodically.*/
5346 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5349 /* If I am congested then pass this message to peer before me in trail. */
5350 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5352 struct GNUNET_PeerIdentity *new_trail;
5353 unsigned int new_trail_length;
5355 /* Remove yourself from the trail setup so far. */
5356 if (trail_length == 1)
5359 new_trail_length = 0;
5364 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5365 sizeof (struct GNUNET_PeerIdentity));
5367 /* Remove myself from the trail. */
5368 new_trail_length = trail_length -1;
5369 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5370 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5373 GNUNET_assert (NULL !=
5375 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5376 GDS_NEIGHBOURS_send_trail_rejection (source,
5377 ultimate_destination_finger_value,
5378 my_identity, is_predecessor,
5379 new_trail,new_trail_length,trail_id,
5380 target_friend, CONGESTION_TIMEOUT);
5381 GNUNET_free (new_trail);
5385 struct Closest_Peer successor;
5386 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5388 /* Am I the final destination? */
5389 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5392 if (0 == trail_length)
5395 next_peer = trail_peer_list[trail_length-1];
5397 GNUNET_assert (NULL !=
5399 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5401 GDS_NEIGHBOURS_send_trail_setup_result (source,
5403 target_friend, trail_length,
5406 ultimate_destination_finger_value,
5411 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5413 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5414 peer_list[trail_length] = my_identity;
5416 GNUNET_assert (NULL !=
5418 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5420 GDS_NEIGHBOURS_send_trail_setup (source,
5421 ultimate_destination_finger_value,
5422 successor.best_known_destination,
5423 target_friend, trail_length + 1, peer_list,
5424 is_predecessor, trail_id,
5425 successor.trail_id);
5432 * Core handle for p2p trail tear compression messages.
5433 * @param cls closure
5434 * @param message message
5435 * @param peer peer identity this notification is about
5436 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5439 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5440 const struct GNUNET_MessageHeader *message)
5442 const struct PeerTrailCompressionMessage *trail_compression;
5443 struct GNUNET_PeerIdentity *next_hop;
5444 struct FriendInfo *target_friend;
5445 struct GNUNET_HashCode trail_id;
5448 msize = ntohs (message->size);
5450 if (msize != sizeof (struct PeerTrailCompressionMessage))
5452 GNUNET_break_op (0);
5456 GNUNET_STATISTICS_update (GDS_stats,
5458 ("# Bytes received from other peers"), msize,
5461 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5462 trail_id = trail_compression->trail_id;
5464 /* Am I the new first friend to reach to finger of this trail. */
5465 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5469 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5470 &trail_compression->source_peer)))
5476 /* Update your prev hop to source of this message. */
5478 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5479 trail_compression->source_peer)))
5487 /* Pass the message to next hop to finally reach to new_first_friend. */
5488 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5490 if (NULL == next_hop)
5496 if( NULL == (target_friend =
5497 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5503 GDS_ROUTING_remove_trail (trail_id);
5505 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5507 trail_compression->new_first_friend,
5514 * Core handler for trail teardown message.
5515 * @param cls closure
5516 * @param message message
5517 * @param peer sender of this messsage.
5518 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5521 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5522 const struct GNUNET_MessageHeader *message)
5524 const struct PeerTrailTearDownMessage *trail_teardown;
5525 enum GDS_ROUTING_trail_direction trail_direction;
5526 struct GNUNET_HashCode trail_id;
5527 struct GNUNET_PeerIdentity *next_hop;
5530 msize = ntohs (message->size);
5532 /* Here we pass only the trail id. */
5533 if (msize != sizeof (struct PeerTrailTearDownMessage))
5535 GNUNET_break_op (0);
5539 GNUNET_STATISTICS_update (GDS_stats,
5541 ("# Bytes received from other peers"), msize,
5544 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5545 trail_direction = ntohl (trail_teardown->trail_direction);
5546 trail_id = trail_teardown->trail_id;
5548 /* Check if peer is the real peer from which we should get this message.*/
5549 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5551 GNUNET_assert (NULL != (prev_hop =
5552 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5553 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5556 return GNUNET_SYSERR;
5560 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5562 if (NULL == next_hop)
5565 return GNUNET_SYSERR;
5568 /* I am the next hop, which means I am the final destination. */
5569 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5571 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5576 /* If not final destination, then send a trail teardown message to next hop.*/
5577 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5578 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5579 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5587 * Core handle for p2p add trail message.
5588 * @param cls closure
5589 * @param message message
5590 * @param peer peer identity this notification is about
5591 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5594 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5595 const struct GNUNET_MessageHeader *message)
5597 const struct PeerAddTrailMessage *add_trail;
5598 const struct GNUNET_PeerIdentity *trail;
5599 struct GNUNET_HashCode trail_id;
5600 struct GNUNET_PeerIdentity destination_peer;
5601 struct GNUNET_PeerIdentity source_peer;
5602 struct GNUNET_PeerIdentity next_hop;
5603 unsigned int trail_length;
5604 unsigned int my_index;
5607 msize = ntohs (message->size);
5608 /* In this message we pass the whole trail from source to destination as we
5609 * are adding that trail.*/
5610 //FIXME: failed when run with 1000 pears. check why.
5611 if (msize < sizeof (struct PeerAddTrailMessage))
5613 GNUNET_break_op (0);
5617 add_trail = (const struct PeerAddTrailMessage *) message;
5618 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5619 sizeof (struct GNUNET_PeerIdentity);
5620 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5621 sizeof (struct GNUNET_PeerIdentity) != 0)
5623 GNUNET_break_op (0);
5627 GNUNET_STATISTICS_update (GDS_stats,
5629 ("# Bytes received from other peers"), msize,
5632 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5633 destination_peer = add_trail->destination_peer;
5634 source_peer = add_trail->source_peer;
5635 trail_id = add_trail->trail_id;
5637 //FIXME: add a check that sender peer is not malicious. Make it a generic
5638 // function so that it can be used in all other functions where we need the
5639 // same functionality.
5641 /* I am not the destination of the trail. */
5642 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5644 struct FriendInfo *target_friend;
5646 /* Get my location in the trail. */
5647 my_index = search_my_index (trail, trail_length);
5650 GNUNET_break_op (0);
5651 return GNUNET_SYSERR;
5653 if((trail_length + 1) == my_index)
5655 DEBUG ("Found twice in trail.\n");
5656 GNUNET_break_op (0);
5657 return GNUNET_SYSERR;
5659 if ((trail_length - 1) == my_index)
5661 next_hop = destination_peer;
5665 next_hop = trail[my_index + 1];
5668 /* Add in your routing table. */
5669 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5670 GNUNET_assert (NULL !=
5672 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5673 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5674 trail, trail_length, target_friend);
5677 /* I am the destination. Add an entry in routing table. */
5678 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5684 * Free the finger trail in which the first friend to reach to a finger is
5685 * disconnected_friend. Also remove entry from routing table for that particular
5687 * @param disconnected_friend PeerIdentity of friend which got disconnected
5688 * @param remove_finger Finger whose trail we need to check if it has
5689 * disconnected_friend as the first hop.
5690 * @return Total number of trails in which disconnected_friend was the first
5694 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5695 struct FingerInfo *remove_finger)
5697 unsigned int matching_trails_count;
5700 /* Number of trails with disconnected_friend as the first hop in the trail
5701 * to reach from me to remove_finger, NOT including endpoints. */
5702 matching_trails_count = 0;
5704 /* Iterate over all the trails of finger. */
5705 for (i = 0; i < remove_finger->trails_count; i++)
5707 struct Trail *trail;
5708 trail = &remove_finger->trail_list[i];
5710 /* This assertion is ensure that there are no gaps in the trail list.
5711 REMOVE IT AFTERWARDS. */
5712 GNUNET_assert (GNUNET_YES == trail->is_present);
5714 /* First friend to reach to finger is disconnected_peer. */
5715 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5716 disconnected_friend))
5718 struct GNUNET_PeerIdentity *next_hop;
5719 struct FriendInfo *remove_friend;
5721 GNUNET_assert (NULL !=
5723 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5724 disconnected_friend)));
5725 /* FIXME: removing no but check it. */
5726 //remove_friend->trails_count--;
5727 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5728 GDS_ROUTING_SRC_TO_DEST);
5730 /* Here it may happen that as all the peers got disconnected, the entry in
5731 routing table for that particular trail has been removed, because the
5732 previously disconnected peer was either a next hop or prev hop of that
5734 if (NULL == next_hop)
5737 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5739 matching_trails_count++;
5740 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5743 trail->is_present = GNUNET_NO;
5746 return matching_trails_count;
5751 * Iterate over finger_table entries.
5752 * 0. Ignore finger which is my_identity or if no valid entry present at
5753 * that finger index.
5754 * 1. If disconnected_friend is a finger, then remove the routing entry from
5755 your own table. Free the trail.
5756 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5757 * 2.1 Remove all the trails and entry from routing table in which disconnected
5758 * friend is the first friend in the trail. If disconnected_friend is the
5759 * first friend in all the trails to reach finger, then remove the finger.
5760 * @param disconnected_friend Peer identity of friend which got disconnected.
5763 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5765 struct FingerInfo *remove_finger;
5766 struct FriendInfo *remove_friend;
5767 int removed_trails_count;
5770 /* Iterate over finger table entries. */
5771 for (i = 0; i < MAX_FINGERS; i++)
5773 remove_finger = &finger_table[i];
5775 /* No finger stored at this trail index. */
5776 if (GNUNET_NO == remove_finger->is_present)
5779 /* I am my own finger, then ignore this finger. */
5780 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5784 /* Is disconnected_peer a finger? */
5785 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5786 &remove_finger->finger_identity))
5788 struct GNUNET_PeerIdentity *next_hop;
5789 struct GNUNET_HashCode trail_id;
5790 /* FIXME: Just for check, remove it afterwards. Here finger is a friend.
5791 hence trail length should be 0*/
5792 GNUNET_assert (0 == remove_finger->trail_list[0].trail_length);
5793 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5794 trail_id = remove_finger->trail_list[0].trail_id;
5798 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5801 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5802 &remove_finger->finger_identity)));
5803 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5804 GNUNET_assert (NULL !=
5806 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5807 disconnected_peer)));
5810 remove_finger->trail_list[0].is_present = GNUNET_NO;
5811 //GNUNET_assert (0 != remove_friend->trails_count);
5812 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5813 remove_finger->is_present = GNUNET_NO;
5814 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5818 /* If finger is a friend but not disconnected_friend, then continue. */
5819 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5820 &remove_finger->finger_identity))
5823 /* Iterate over the list of trails to reach remove_finger. Check if
5824 * disconnected_friend is the first friend in any of the trail. */
5825 removed_trails_count = remove_matching_trails (disconnected_peer,
5827 remove_finger->trails_count =
5828 remove_finger->trails_count - removed_trails_count;
5829 /* All the finger trails had disconnected_friend as the first friend,
5830 * so free the finger. */
5831 if (remove_finger->trails_count == 0)
5833 remove_finger->is_present = GNUNET_NO;
5834 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5841 * Method called whenever a peer disconnects.
5843 * @param cls closure
5844 * @param peer peer identity this notification is about
5847 handle_core_disconnect (void *cls,
5848 const struct GNUNET_PeerIdentity *peer)
5850 struct FriendInfo *remove_friend;
5851 struct P2PPendingMessage *pos;
5852 unsigned int discarded;
5854 /* If disconnected to own identity, then return. */
5855 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5858 if(NULL == (remove_friend =
5859 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
5861 DEBUG("\n friend already disconnected.");
5864 /* Remove fingers with peer as first friend or if peer is a finger. */
5865 remove_matching_fingers (peer);
5867 /* Remove any trail from routing table of which peer is a part of. This function
5868 * internally sends a trail teardown message in the direction of which
5869 * disconnected peer is not part of. */
5870 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5872 /* Remove peer from friend_peermap. */
5873 GNUNET_assert (GNUNET_YES ==
5874 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5878 /* Remove all the messages queued in pending list of this peer is discarded.*/
5879 if (remove_friend->th != NULL)
5881 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
5882 remove_friend->th = NULL;
5886 while (NULL != (pos = remove_friend->head))
5888 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
5893 GNUNET_STATISTICS_update (GDS_stats,
5895 ("# Queued messages discarded (peer disconnected)"),
5896 discarded, GNUNET_NO);
5897 GNUNET_free (remove_friend);
5899 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5902 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5904 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5905 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5913 * Method called whenever a peer connects.
5915 * @param cls closure
5916 * @param peer_identity peer identity this notification is about
5919 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5921 struct FriendInfo *friend;
5923 /* Check for connect to self message */
5924 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5927 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5929 /* If peer already exists in our friend_peermap, then exit. */
5930 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5937 friend = GNUNET_new (struct FriendInfo);
5938 friend->id = *peer_identity;
5940 GNUNET_assert (GNUNET_OK ==
5941 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5942 peer_identity, friend,
5943 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5945 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5946 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5948 next_send_time.rel_value_us =
5949 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5950 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5951 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5952 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5958 * To be called on core init/fail.
5960 * @param cls service closure
5961 * @param identity the public identity of this peer
5964 core_init (void *cls,
5965 const struct GNUNET_PeerIdentity *identity)
5967 my_identity = *identity;
5970 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5971 my_id64 = GNUNET_ntohll (my_id64);
5972 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5973 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5979 * Initialize finger table entries.
5982 finger_table_init ()
5984 memset (&finger_table, 0, sizeof (finger_table));
5989 * Initialize neighbours subsystem.
5990 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5993 GDS_NEIGHBOURS_init (void)
5995 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5996 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5997 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5998 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5999 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
6000 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
6001 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
6002 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
6003 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
6004 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
6005 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
6006 sizeof (struct PeerTrailCompressionMessage)},
6007 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
6008 sizeof (struct PeerTrailTearDownMessage)},
6009 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
6013 #if ENABLE_MALICIOUS
6018 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
6019 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
6020 GNUNET_NO, core_handlers);
6022 if (NULL == core_api)
6023 return GNUNET_SYSERR;
6025 //TODO: check size of this peer map?
6026 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
6027 finger_table_init ();
6033 * Free the memory held up by trails of a finger.
6036 delete_finger_table_entries()
6041 for(i = 0; i < MAX_FINGERS; i++)
6043 if(GNUNET_NO == finger_table[i].is_present)
6046 for(j = 0; j < finger_table[i].trails_count; j++)
6048 free_trail(&finger_table[i].trail_list[i]);
6054 * Shutdown neighbours subsystem.
6057 GDS_NEIGHBOURS_done (void)
6059 if (NULL == core_api)
6062 GNUNET_CORE_disconnect (core_api);
6065 delete_finger_table_entries();
6067 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6068 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6069 friend_peermap = NULL;
6071 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
6074 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6075 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
6078 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
6080 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6081 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
6089 * @return my identity
6091 struct GNUNET_PeerIdentity
6092 GDS_NEIGHBOURS_get_my_id (void)
6097 /* end of gnunet-service-xdht_neighbours.c */