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);
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];
1149 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1151 /* Send the message to chosen friend. */
1152 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1153 target_friend->pending_count++;
1154 process_friend_queue (target_friend);
1159 * Send trail rejection message to target friend
1160 * @param source_peer Peer which is trying to setup the trail.
1161 * @param ultimate_destination_finger_value Peer closest to this value will be
1162 * @a source_peer's finger
1163 * @param congested_peer Peer which sent this message as it is congested.
1164 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1165 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1166 * by congested_peer. This does NOT include @a source_peer
1167 * and congested_peer.
1168 * @param trail_length Total number of peers in trail_peer_list, NOT including
1169 * @a source_peer and @a congested_peer
1170 * @param trail_id Unique identifier of this trail.
1171 * @param congestion_timeout Duration given by congested peer as an estimate of
1172 * how long it may remain congested.
1175 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1176 uint64_t ultimate_destination_finger_value,
1177 struct GNUNET_PeerIdentity congested_peer,
1178 unsigned int is_predecessor,
1179 const struct GNUNET_PeerIdentity *trail_peer_list,
1180 unsigned int trail_length,
1181 struct GNUNET_HashCode trail_id,
1182 struct FriendInfo *target_friend,
1183 const struct GNUNET_TIME_Relative congestion_timeout)
1185 struct PeerTrailRejectionMessage *trm;
1186 struct P2PPendingMessage *pending;
1187 struct GNUNET_PeerIdentity *peer_list;
1190 msize = sizeof (struct PeerTrailRejectionMessage) +
1191 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1193 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1199 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1201 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1205 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1206 pending->importance = 0;
1207 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1208 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1209 pending->msg = &trm->header;
1210 trm->header.size = htons (msize);
1211 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1212 trm->source_peer = source_peer;
1213 trm->congested_peer = congested_peer;
1214 trm->congestion_time = congestion_timeout;
1215 trm->is_predecessor = htonl (is_predecessor);
1216 trm->trail_id = trail_id;
1217 trm->ultimate_destination_finger_value =
1218 GNUNET_htonll (ultimate_destination_finger_value);
1220 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1221 if (trail_length > 0)
1223 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1226 /* Send the message to chosen friend. */
1227 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1228 target_friend->pending_count++;
1229 process_friend_queue (target_friend);
1234 * Construct a verify successor message and forward it to target_friend.
1235 * @param source_peer Peer which wants to verify its successor.
1236 * @param successor Peer which is @a source_peer's current successor.
1237 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1238 * NOT including them.
1239 * @param trail List of peers which are part of trail to reach from @a source_peer
1240 * to @a successor, NOT including them.
1241 * @param trail_length Total number of peers in @a trail.
1242 * @param target_friend Next friend to get this message.
1245 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1246 struct GNUNET_PeerIdentity successor,
1247 struct GNUNET_HashCode trail_id,
1248 struct GNUNET_PeerIdentity *trail,
1249 unsigned int trail_length,
1250 struct FriendInfo *target_friend)
1252 struct PeerVerifySuccessorMessage *vsm;
1253 struct P2PPendingMessage *pending;
1254 struct GNUNET_PeerIdentity *peer_list;
1257 msize = sizeof (struct PeerVerifySuccessorMessage) +
1258 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1259 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1265 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1267 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1271 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1272 pending->importance = 0; /* FIXME */
1273 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1274 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1275 pending->msg = &vsm->header;
1276 vsm->header.size = htons (msize);
1277 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1278 vsm->source_peer = source_peer;
1279 vsm->successor = successor;
1280 vsm->trail_id = trail_id;
1281 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1282 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1284 /* Send the message to chosen friend. */
1285 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1286 target_friend->pending_count++;
1287 process_friend_queue (target_friend);
1292 * FIXME: In every function we pass target friend except for this one.
1293 * so, either change everything or this one. also, should se just store
1294 * the pointer to friend in routing table rather than gnunet_peeridentity.
1295 * if yes then we should keep friend info in.h andmake lot of changes.
1296 * Construct a trail teardown message and forward it to target friend.
1297 * @param trail_id Unique identifier of the trail.
1298 * @param trail_direction Direction of trail.
1299 * @param target_friend Friend to get this message.
1302 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1303 unsigned int trail_direction,
1304 struct GNUNET_PeerIdentity peer)
1306 struct PeerTrailTearDownMessage *ttdm;
1307 struct P2PPendingMessage *pending;
1308 struct FriendInfo *target_friend;
1311 msize = sizeof (struct PeerTrailTearDownMessage);
1313 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1319 /*FIXME:In what case friend can be null. ?*/
1320 if (NULL == (target_friend =
1321 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1324 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1326 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1330 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1331 pending->importance = 0; /* FIXME */
1332 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1333 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1334 pending->msg = &ttdm->header;
1335 ttdm->header.size = htons (msize);
1336 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1337 ttdm->trail_id = trail_id;
1338 ttdm->trail_direction = htonl (trail_direction);
1340 /* Send the message to chosen friend. */
1341 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1342 target_friend->pending_count++;
1343 process_friend_queue (target_friend);
1348 * Construct a verify successor result message and send it to target_friend
1349 * @param querying_peer Peer which sent the verify successor message.
1350 * @param source_successor Current_successor of @a querying_peer.
1351 * @param current_predecessor Current predecessor of @a successor. Could be same
1352 * or different from @a querying_peer.
1353 * @param trail_id Unique identifier of the trail from @a querying_peer to
1354 * @a successor, NOT including them.
1355 * @param trail List of peers which are part of trail from @a querying_peer to
1356 * @a successor, NOT including them.
1357 * @param trail_length Total number of peers in @a trail
1358 * @param trail_direction Direction in which we are sending the message. In this
1359 * case we are sending result from @a successor to @a querying_peer.
1360 * @param target_friend Next friend to get this message.
1363 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1364 struct GNUNET_PeerIdentity current_successor,
1365 struct GNUNET_PeerIdentity probable_successor,
1366 struct GNUNET_HashCode trail_id,
1367 const struct GNUNET_PeerIdentity *trail,
1368 unsigned int trail_length,
1369 enum GDS_ROUTING_trail_direction trail_direction,
1370 struct FriendInfo *target_friend)
1372 struct PeerVerifySuccessorResultMessage *vsmr;
1373 struct P2PPendingMessage *pending;
1374 struct GNUNET_PeerIdentity *peer_list;
1377 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1378 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1380 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1386 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1388 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1392 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1393 pending->importance = 0; /* FIXME */
1394 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1395 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1396 pending->msg = &vsmr->header;
1397 vsmr->header.size = htons (msize);
1398 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1399 vsmr->querying_peer = querying_peer;
1400 vsmr->current_successor = current_successor;
1401 vsmr->probable_successor = probable_successor;
1402 vsmr->trail_direction = htonl (trail_direction);
1403 vsmr->trail_id = trail_id;
1404 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1405 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1407 /* Send the message to chosen friend. */
1408 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1409 target_friend->pending_count++;
1410 process_friend_queue (target_friend);
1415 * Construct a notify new successor message and send it to target_friend
1416 * @param source_peer Peer which wants to notify to its new successor that it
1417 * could be its predecessor.
1418 * @param successor New successor of @a source_peer
1419 * @param successor_trail List of peers in Trail to reach from
1420 * @a source_peer to @a new_successor, NOT including
1422 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1423 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1424 * @param target_friend Next friend to get this message.
1427 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1428 struct GNUNET_PeerIdentity successor,
1429 const struct GNUNET_PeerIdentity *successor_trail,
1430 unsigned int successor_trail_length,
1431 struct GNUNET_HashCode succesor_trail_id,
1432 struct FriendInfo *target_friend)
1434 struct PeerNotifyNewSuccessorMessage *nsm;
1435 struct P2PPendingMessage *pending;
1436 struct GNUNET_PeerIdentity *peer_list;
1439 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1440 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1442 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1448 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1450 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1454 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1455 pending->importance = 0; /* FIXME */
1456 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1457 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1458 pending->msg = &nsm->header;
1459 nsm->header.size = htons (msize);
1460 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1461 nsm->new_successor = successor;
1462 nsm->source_peer = source_peer;
1463 nsm->trail_id = succesor_trail_id;
1465 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1466 memcpy (peer_list, successor_trail,
1467 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1469 /* Send the message to chosen friend. */
1470 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1471 target_friend->pending_count++;
1472 process_friend_queue (target_friend);
1477 * Construct an add_trail message and send it to target_friend
1478 * @param source_peer Source of the trail.
1479 * @param destination_peer Destination of the trail.
1480 * @param trail_id Unique identifier of the trail from
1481 * @a source_peer to @a destination_peer, NOT including the endpoints.
1482 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1483 * NOT including the endpoints.
1484 * @param trail_length Total number of peers in @a trail.
1485 * @param target_friend Next friend to get this message.
1488 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1489 struct GNUNET_PeerIdentity destination_peer,
1490 struct GNUNET_HashCode trail_id,
1491 const struct GNUNET_PeerIdentity *trail,
1492 unsigned int trail_length,
1493 struct FriendInfo *target_friend)
1495 struct PeerAddTrailMessage *adm;
1496 struct GNUNET_PeerIdentity *peer_list;
1497 struct P2PPendingMessage *pending;
1500 msize = sizeof (struct PeerAddTrailMessage) +
1501 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1503 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1509 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1511 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1515 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1516 pending->importance = 0; /* FIXME */
1517 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1518 adm = (struct PeerAddTrailMessage *) &pending[1];
1519 pending->msg = &adm->header;
1520 adm->header.size = htons (msize);
1521 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1522 adm->source_peer = source_peer;
1523 adm->destination_peer = destination_peer;
1524 adm->trail_id = trail_id;
1525 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1526 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1528 /* Send the message to chosen friend. */
1529 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1530 target_friend->pending_count++;
1531 process_friend_queue (target_friend);
1537 * Construct a trail compression message and send it to target_friend.
1538 * @param source_peer Source of the trail.
1539 * @param trail_id Unique identifier of trail.
1540 * @param first_friend First hop in compressed trail to reach from source to finger
1541 * @param target_friend Next friend to get this message.
1544 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1545 struct GNUNET_HashCode trail_id,
1546 struct GNUNET_PeerIdentity first_friend,
1547 struct FriendInfo *target_friend)
1549 struct P2PPendingMessage *pending;
1550 struct PeerTrailCompressionMessage *tcm;
1553 msize = sizeof (struct PeerTrailCompressionMessage);
1555 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1561 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1563 GNUNET_STATISTICS_update (GDS_stats,
1564 gettext_noop ("# P2P messages dropped due to full queue"),
1568 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1569 pending->importance = 0; /* FIXME */
1570 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1571 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1572 pending->msg = &tcm->header;
1573 tcm->header.size = htons (msize);
1574 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1575 tcm->source_peer = source_peer;
1576 tcm->new_first_friend = first_friend;
1577 tcm->trail_id = trail_id;
1579 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1580 target_friend->pending_count++;
1581 process_friend_queue (target_friend);
1587 * Search my location in trail. In case I am present more than once in the
1588 * trail (can happen during trail setup), then return my lowest index.
1589 * @param trail List of peers
1590 * @return my_index if found
1591 * trail_length + 1 if an entry is present twice, It is an error.
1592 * -1 if no entry found.
1595 search_my_index (const struct GNUNET_PeerIdentity *trail,
1599 int index_seen = trail_length + 1;
1602 for (i = 0; i < trail_length; i++)
1604 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1607 if(index_seen == (trail_length + 1))
1611 DEBUG("Entry is present twice in trail. Its not allowed\n");
1625 * Check if the friend is congested or have reached maximum number of trails
1626 * it can be part of of.
1627 * @param friend Friend to be checked.
1628 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1629 * #GNUNET_YES if friend is either congested or have crossed threshold
1632 is_friend_congested (struct FriendInfo *friend)
1634 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1635 ((0 == GNUNET_TIME_absolute_get_remaining
1636 (friend->congestion_timestamp).rel_value_us)))
1644 * Select closest finger to value.
1645 * @param peer1 First peer
1646 * @param peer2 Second peer
1647 * @param value Value to be compare
1648 * @return Closest peer
1650 const static struct GNUNET_PeerIdentity *
1651 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1652 const struct GNUNET_PeerIdentity *peer2,
1655 uint64_t peer1_value;
1656 uint64_t peer2_value;
1658 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1659 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1660 peer1_value = GNUNET_ntohll (peer1_value);
1661 peer2_value = GNUNET_ntohll (peer2_value);
1663 // TODO: Can use a simpler (to understand) idea here!
1665 if (peer1_value == value)
1670 if (peer2_value == value)
1675 if (peer2_value < peer1_value)
1677 if ((peer2_value < value) && (value < peer1_value))
1681 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1682 ((0 < value) && (value < peer2_value)))
1688 if (peer1_value < peer2_value)
1690 if ((peer1_value < value) && (value < peer2_value))
1694 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1695 ((0 < value) && (value < peer1_value)))
1705 * Select closest predecessor to value.
1706 * @param peer1 First peer
1707 * @param peer2 Second peer
1708 * @param value Value to be compare
1709 * @return Peer which precedes value in the network.
1711 const static struct GNUNET_PeerIdentity *
1712 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1713 const struct GNUNET_PeerIdentity *peer2,
1716 uint64_t peer1_value;
1717 uint64_t peer2_value;
1719 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1720 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1721 peer1_value = GNUNET_ntohll (peer1_value);
1722 peer2_value = GNUNET_ntohll (peer2_value);
1724 if (peer1_value == value)
1727 if (peer2_value == value)
1730 if (peer1_value < peer2_value)
1732 if ((peer1_value < value) && (value < peer2_value))
1736 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1737 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1743 if (peer2_value < peer1_value)
1745 if ((peer2_value < value) && (value < peer1_value))
1749 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1750 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1764 test_print_trail (struct GNUNET_PeerIdentity *trail,
1765 unsigned int trail_length)
1767 struct GNUNET_PeerIdentity print_peer;
1770 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1771 __FILE__, __func__,__LINE__,trail_length);
1772 for (i =0 ; i< trail_length; i++)
1774 print_peer = trail[i];
1775 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1776 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1783 * This is a test function to print all the entries of friend table.
1786 test_friend_peermap_print ()
1788 struct FriendInfo *friend;
1789 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1790 struct GNUNET_PeerIdentity print_peer;
1791 struct GNUNET_PeerIdentity key_ret;
1794 print_peer = my_identity;
1795 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1796 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1798 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1800 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1802 (const void **)&friend))
1804 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1805 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1806 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1814 * This is a test function, to print all the entries of finger table.
1817 test_finger_table_print()
1819 struct FingerInfo *finger;
1820 struct GNUNET_PeerIdentity print_peer;
1821 //struct Trail *trail;
1825 print_peer = my_identity;
1826 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1827 for (i = 0; i < MAX_FINGERS; i++)
1829 finger = &finger_table[i];
1831 if (GNUNET_NO == finger->is_present)
1834 print_peer = finger->finger_identity;
1835 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1836 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1839 for (j = 0; j < finger->trails_count; j++)
1841 trail = &finger->trail_list[j];
1842 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1843 struct Trail_Element *element;
1844 element = trail->trail_head;
1845 for (k = 0; k < trail->trail_length; k++)
1847 print_peer = element->peer;
1848 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1849 element = element->next;
1858 * Select the closest peer among two peers (which should not be same)
1859 * with respect to value and finger_table_index
1860 * NOTE: peer1 != peer2
1861 * @param peer1 First peer
1862 * @param peer2 Second peer
1863 * @param value Value relative to which we find the closest
1864 * @param is_predecessor Is value a predecessor or any other finger.
1865 * @return Closest peer among two peers.
1868 // TODO: URGENT! Change return type to value instead of pointer
1869 const static struct GNUNET_PeerIdentity *
1870 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1871 const struct GNUNET_PeerIdentity *peer2,
1873 unsigned int is_predecessor)
1875 /* This check is here to ensure that calling function never sends
1876 same peer value in peer1 and peer2. Remove it later. */
1877 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1878 if (1 == is_predecessor)
1879 return select_closest_predecessor (peer1, peer2, value);
1881 // TODO: Change name to something like select_closest_successor!!
1882 return select_closest_finger (peer1, peer2, value);
1887 * Iterate over the list of all the trails of a finger. In case the first
1888 * friend to reach the finger has reached trail threshold or is congested,
1889 * then don't select it. In case there multiple available good trails to reach
1890 * to Finger, choose the one with shortest trail length.
1891 * Note: We use length as parameter. But we can use any other suitable parameter
1893 * @param finger Finger
1894 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1895 * and trail length. NULL in case none of the trails are free.
1897 static struct Trail *
1898 select_finger_trail (struct FingerInfo *finger)
1900 struct FriendInfo *friend;
1901 struct Trail *current_finger_trail;
1902 struct Trail *best_trail = NULL;
1905 GNUNET_assert (finger->trails_count > 0);
1907 for (i = 0; i < finger->trails_count; i++)
1909 current_finger_trail = &finger->trail_list[i];
1911 /* No trail stored at this index. */
1912 if (GNUNET_NO == current_finger_trail->is_present)
1915 GNUNET_assert (NULL !=
1917 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1918 ¤t_finger_trail->trail_head->peer)));
1920 /* First friend to reach trail is not free. */
1921 if (GNUNET_YES == is_friend_congested (friend))
1924 if (NULL == best_trail ||
1925 best_trail->trail_length > current_finger_trail->trail_length)
1927 best_trail = current_finger_trail;
1935 static struct Selected_Finger_Trail *
1936 select_finger_trail (struct FingerInfo *finger)
1938 struct FriendInfo *friend;
1939 struct Trail *current_finger_trail;
1940 struct Selected_Finger_Trail *finger_trail;
1942 unsigned int flag = 0;
1945 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1946 GNUNET_assert (finger->trails_count > 0);
1948 for (i = 0; i < finger->trails_count; i++)
1950 current_finger_trail = &finger->trail_list[i];
1952 /* No trail stored at this index. */
1953 if (GNUNET_NO == current_finger_trail->is_present)
1956 GNUNET_assert (NULL !=
1958 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1959 ¤t_finger_trail->trail_head->peer)));
1961 /* First friend to reach trail is not free. */
1962 if (GNUNET_YES == is_friend_congested (friend))
1971 finger_trail->trail_length = current_finger_trail->trail_length;
1972 finger_trail->friend = *friend;
1973 finger_trail->trail_id = current_finger_trail->trail_id;
1975 else if (finger_trail->trail_length > current_finger_trail->trail_length)
1977 finger_trail->friend = *friend;
1978 finger_trail->trail_id = current_finger_trail->trail_id;
1979 finger_trail->trail_length = current_finger_trail->trail_length;
1983 /* All the first friend in all the trails to reach to finger are either
1984 congested or have crossed trail threshold. */
1985 if (j == finger->trails_count)
1988 return finger_trail;
1994 * Compare FINGER entry with current successor. If finger's first friend of all
1995 * its trail is not congested and has not crossed trail threshold, then check
1996 * if finger peer identity is closer to final_destination_finger_value than
1997 * current_successor. If yes then update current_successor.
1998 * @param current_successor[in/out]
2002 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
2004 struct FingerInfo *finger;
2005 const struct GNUNET_PeerIdentity *closest_peer;
2006 struct Trail *finger_trail;
2009 // TODO: Instead of iterating over all fingers, calculate the finger index
2010 // using "value" of my id and current closest peer id.
2012 /* Iterate over finger table. */
2013 for (i = 0; i < MAX_FINGERS; i++)
2015 finger = &finger_table[i];
2017 if (GNUNET_NO == finger->is_present)
2020 /* FIXME write correct comment here */
2021 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2022 ¤t_closest_peer->best_known_destination))
2025 /* If I am my own finger, then ignore this finger. */
2026 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2029 /* FIXME: I think a peer should not select itself as its own identity ever.
2030 But it does select. Find out why??*/
2036 /* If finger is a friend, then do nothing. As we have already checked
2037 * for each friend in compare_friend_and_current_successor(). */
2038 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2039 &finger->finger_identity)))
2044 closest_peer = select_closest_peer (&finger->finger_identity,
2045 ¤t_closest_peer->best_known_destination,
2046 current_closest_peer->destination_finger_value,
2047 current_closest_peer->is_predecessor);
2049 if (&finger->finger_identity == closest_peer)
2051 /* Choose one of the trail to reach to finger. */
2052 finger_trail = select_finger_trail (finger);
2054 /* In case no trail found, ignore this finger. */
2055 if (NULL == finger_trail)
2058 current_closest_peer->best_known_destination = *closest_peer;
2059 current_closest_peer->next_hop = finger_trail->trail_head->peer;
2060 current_closest_peer->trail_id = finger_trail->trail_id;
2068 * Compare friend entry with current successor.
2069 * If friend identity and current_successor is same, then do nothing.
2070 * If friend is not congested and has not crossed trail threshold, then check
2071 * if friend peer identity is closer to final_destination_finger_value than
2072 * current_successor. If yes then update current_successor.
2073 * @param cls closure
2074 * @param key current public key
2075 * @param value struct Closest_Peer
2076 * @return #GNUNET_YES if we should continue to iterate,
2077 * #GNUNET_NO if not.
2080 compare_friend_and_current_closest_peer (void *cls,
2081 const struct GNUNET_PeerIdentity *key,
2084 struct FriendInfo *friend = value;
2085 struct Closest_Peer *current_closest_peer = cls;
2086 const struct GNUNET_PeerIdentity *closest_peer;
2088 /* Friend is either congested or has crossed threshold. */
2089 if (GNUNET_YES == is_friend_congested (friend))
2092 /* If current_closest_peer and friend identity are same, then do nothing.*/
2093 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2094 ¤t_closest_peer->best_known_destination))
2100 closest_peer = select_closest_peer (&friend->id,
2101 ¤t_closest_peer->best_known_destination,
2102 current_closest_peer->destination_finger_value,
2103 current_closest_peer->is_predecessor);
2105 /* Is friend the closest successor? */
2106 if (&friend->id == closest_peer)
2108 current_closest_peer->best_known_destination = friend->id;
2109 current_closest_peer->next_hop = friend->id;
2117 * Initialize current_successor to my_identity.
2118 * @param my_identity My peer identity
2119 * @return Updated closest_peer
2121 static struct Closest_Peer
2122 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2123 uint64_t destination_finger_value,
2124 unsigned int is_predecessor)
2126 struct Closest_Peer current_closest_peer;
2128 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2129 current_closest_peer.destination_finger_value = destination_finger_value;
2130 current_closest_peer.is_predecessor = is_predecessor;
2131 current_closest_peer.next_hop = my_identity;
2132 current_closest_peer.best_known_destination = my_identity;
2134 return current_closest_peer;
2139 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2140 * peer. It could be because of the logic we wrote here. Verify if its correct.
2141 * If not then return immediate_successor.
2143 * Find the successor for destination_finger_value among my_identity, my
2144 * friends and my fingers. Don't consider friends or fingers which are either
2145 * congested or have crossed the threshold.
2146 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2148 * @param destination_finger_value Peer closest to this value will be the next successor.
2149 * @param is_predecessor Are we looking for predecessor or finger?
2150 * @return Successor It is never NULL, in case none of friend or finger is closest,
2151 * then we return my_identity.
2153 static struct Closest_Peer
2154 find_successor (uint64_t destination_finger_value,
2155 unsigned int is_predecessor)
2157 struct Closest_Peer current_closest_peer;
2159 /* Initialize current_successor to my_identity. */
2160 current_closest_peer = init_current_successor (my_identity,
2161 destination_finger_value,
2164 /* Compare each friend entry with current_successor and update current_successor
2165 * with friend if its closest. */
2168 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2169 &compare_friend_and_current_closest_peer,
2170 ¤t_closest_peer));
2172 /* Compare each finger entry with current_successor and update current_successor
2173 * with finger if its closest. */
2174 // TODO: Change function name to "compare_finger_and_current_closest_peer"
2175 compare_finger_and_current_successor (¤t_closest_peer);
2177 return current_closest_peer;
2182 * FIXME; Send put message across all the trail to reach to next hop to handle
2184 * Construct a Put message and send it to target_peer.
2185 * @param key Key for the content
2186 * @param block_type Type of the block
2187 * @param options Routing options
2188 * @param desired_replication_level Desired replication count
2189 * @param best_known_dest Peer to which this message should reach eventually,
2190 * as it is best known destination to me.
2191 * @param intermediate_trail_id Trail id in case
2192 * @param target_peer Peer to which this message will be forwarded.
2193 * @param hop_count Number of hops traversed so far.
2194 * @param put_path_length Total number of peers in @a put_path
2195 * @param put_path Number of peers traversed so far
2196 * @param expiration_time When does the content expire
2197 * @param data Content to store
2198 * @param data_size Size of content @a data in bytes
2201 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2202 enum GNUNET_BLOCK_Type block_type,
2203 enum GNUNET_DHT_RouteOption options,
2204 uint32_t desired_replication_level,
2205 struct GNUNET_PeerIdentity best_known_dest,
2206 struct GNUNET_HashCode intermediate_trail_id,
2207 struct GNUNET_PeerIdentity *target_peer,
2209 uint32_t put_path_length,
2210 struct GNUNET_PeerIdentity *put_path,
2211 struct GNUNET_TIME_Absolute expiration_time,
2212 const void *data, size_t data_size)
2214 struct PeerPutMessage *ppm;
2215 struct P2PPendingMessage *pending;
2216 struct FriendInfo *target_friend;
2217 struct GNUNET_PeerIdentity *pp;
2218 struct GNUNET_PeerIdentity next_hop;
2222 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2223 sizeof (struct PeerPutMessage);
2225 #if ENABLE_MALICIOUS
2226 /*Call is made to this function from
2228 2. Every peer to construct a pending message and send it to next peer.
2229 In case of 2nd, this case should have been handled in handle_dht_p2p_put/get
2230 No need to check here. First peer can never be malicious. IDEALLY we DONOT
2231 need the condition here. REMOVE IT AFTERWARDS once verified.*/
2232 if(1 == act_malicious)
2237 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2239 put_path_length = 0;
2240 msize = data_size + sizeof (struct PeerPutMessage);
2243 /* Should it be GNUNET_SERVER_MAX_MESSAGE_SIZE? */
2244 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2246 DEBUG("msize = %lu\n",msize);
2251 /* This is the first call made from clients file. So, we should search for the
2253 if (NULL == target_peer)
2256 struct Closest_Peer successor;
2258 memcpy (&key_value, key, sizeof (uint64_t));
2259 key_value = GNUNET_ntohll (key_value);
2261 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2262 best_known_dest = successor.best_known_destination;
2263 next_hop = successor.next_hop;
2264 intermediate_trail_id = successor.trail_id;
2266 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2268 /* I am the destination. */
2269 DEBUG("PUT destination is me = %s,key =%s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2270 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2271 block_type,data_size,data);
2275 GNUNET_assert (NULL !=
2277 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2281 GNUNET_assert (NULL !=
2283 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2286 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2287 pending->timeout = expiration_time;
2288 ppm = (struct PeerPutMessage *) &pending[1];
2289 pending->msg = &ppm->header;
2290 ppm->header.size = htons (msize);
2291 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2292 ppm->options = htonl (options);
2293 ppm->block_type = htonl (block_type);
2294 ppm->hop_count = htonl (hop_count + 1);
2295 ppm->desired_replication_level = htonl (desired_replication_level);
2296 ppm->put_path_length = htonl (put_path_length);
2297 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2298 ppm->best_known_destination = best_known_dest;
2301 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2302 if (put_path_length != 0)
2304 memcpy (pp, put_path,
2305 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2307 memcpy (&pp[put_path_length], data, data_size);
2308 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2309 target_friend->pending_count++;
2310 process_friend_queue (target_friend);
2315 * FIXME; Send get message across all the trail to reach to next hop to handle
2317 * Construct a Get message and send it to target_peer.
2318 * @param key Key for the content
2319 * @param block_type Type of the block
2320 * @param options Routing options
2321 * @param desired_replication_level Desired replication count
2322 * @param best_known_dest Peer which should get this message. Same as target peer
2323 * if best_known_dest is a friend else its a finger.
2324 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2325 * in case it is a finger else set to 0.
2326 * @param target_peer Peer to which this message will be forwarded.
2327 * @param hop_count Number of hops traversed so far.
2328 * @param data Content to store
2329 * @param data_size Size of content @a data in bytes
2330 * @param get_path_length Total number of peers in @a get_path
2331 * @param get_path Number of peers traversed so far
2334 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2335 enum GNUNET_BLOCK_Type block_type,
2336 enum GNUNET_DHT_RouteOption options,
2337 uint32_t desired_replication_level,
2338 struct GNUNET_PeerIdentity best_known_dest,
2339 struct GNUNET_HashCode intermediate_trail_id,
2340 struct GNUNET_PeerIdentity *target_peer,
2342 uint32_t get_path_length,
2343 struct GNUNET_PeerIdentity *get_path)
2345 struct PeerGetMessage *pgm;
2346 struct P2PPendingMessage *pending;
2347 struct FriendInfo *target_friend;
2348 struct GNUNET_PeerIdentity *gp;
2351 msize = sizeof (struct PeerGetMessage) +
2352 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2354 #if ENABLE_MALICIOUS
2355 if(1 == act_malicious)
2360 //GNUNET_SERVER_MAX_MESSAGE_SIZE
2361 /* FIXME:TODO:URGENTHere you can try to optimize it a bit. In case the get path contains you
2362 or your friend then shorten the path. */
2363 /* In this case we don't make get_path_length = 0, as we need get path to
2364 * return the message back to querying client. */
2365 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2371 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
2373 /* This is the first time we got request from our own client file. */
2374 if (NULL == target_peer)
2377 struct Closest_Peer successor;
2379 memcpy (&key_value, key, sizeof (uint64_t));
2380 key_value = GNUNET_ntohll (key_value);
2381 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2383 best_known_dest = successor.best_known_destination;
2384 intermediate_trail_id = successor.trail_id;
2386 /* I am the destination. I have the data. */
2387 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2390 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2391 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2392 NULL, 0, 1, &my_identity, NULL,&my_identity);
2398 GNUNET_assert (NULL !=
2400 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2401 &successor.next_hop)));
2407 GNUNET_assert (NULL !=
2409 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2412 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2413 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2414 pending->importance = 0; /* FIXME */
2415 pgm = (struct PeerGetMessage *) &pending[1];
2416 pending->msg = &pgm->header;
2417 pgm->header.size = htons (msize);
2418 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2419 pgm->get_path_length = htonl (get_path_length);
2420 pgm->best_known_destination = best_known_dest;
2422 pgm->intermediate_trail_id = intermediate_trail_id;
2423 pgm->hop_count = htonl (hop_count + 1);
2424 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2426 if (get_path_length != 0)
2428 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2431 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2432 target_friend->pending_count++;
2433 process_friend_queue (target_friend);
2438 * Send the get result to requesting client.
2439 * @param key Key of the requested data.
2440 * @param type Block type
2441 * @param target_peer Next peer to forward the message to.
2442 * @param source_peer Peer which has the data for the key.
2443 * @param put_path_length Number of peers in @a put_path
2444 * @param put_path Path taken to put the data at its stored location.
2445 * @param get_path_length Number of peers in @a get_path
2446 * @param get_path Path taken to reach to the location of the key.
2447 * @param expiration When will this result expire?
2448 * @param data Payload to store
2449 * @param data_size Size of the @a data
2452 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2453 enum GNUNET_BLOCK_Type type,
2454 const struct GNUNET_PeerIdentity *target_peer,
2455 const struct GNUNET_PeerIdentity *source_peer,
2456 unsigned int put_path_length,
2457 const struct GNUNET_PeerIdentity *put_path,
2458 unsigned int get_path_length,
2459 const struct GNUNET_PeerIdentity *get_path,
2460 struct GNUNET_TIME_Absolute expiration,
2461 const void *data, size_t data_size)
2463 struct PeerGetResultMessage *get_result;
2464 struct GNUNET_PeerIdentity *paths;
2465 struct P2PPendingMessage *pending;
2466 struct FriendInfo *target_friend;
2467 int current_path_index;
2470 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2472 sizeof (struct PeerGetResultMessage);
2474 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2476 put_path_length = 0;
2477 msize = msize - put_path_length;
2481 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2486 DEBUG("GET RESULT FOR DATA_SIZE = %lu\n",msize);
2487 current_path_index = 0;
2488 if(get_path_length > 0)
2490 current_path_index = search_my_index(get_path, get_path_length);
2491 if (-1 == current_path_index)
2496 if ((get_path_length + 1) == current_path_index)
2498 DEBUG ("Peer found twice in get path. Not allowed \n");
2503 if (0 == current_path_index)
2505 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2506 get_path, put_path_length,
2507 put_path, type, data_size, data);
2511 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2512 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2513 pending->importance = 0;
2514 get_result = (struct PeerGetResultMessage *)&pending[1];
2515 pending->msg = &get_result->header;
2516 get_result->header.size = htons (msize);
2517 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2518 get_result->key = *key;
2519 get_result->querying_peer = *source_peer;
2520 get_result->expiration_time = expiration;
2521 get_result->get_path_length = htonl (get_path_length);
2522 get_result->put_path_length = htonl (put_path_length);
2523 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2524 memcpy (paths, put_path,
2525 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2526 memcpy (&paths[put_path_length], get_path,
2527 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2528 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2530 GNUNET_assert (NULL !=
2532 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2533 &get_path[current_path_index - 1])));
2534 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2535 target_friend->pending_count++;
2536 process_friend_queue (target_friend);
2541 * Randomly choose one of your friends (which is not congested and have not crossed
2542 * trail threshold) from the friend_peermap
2543 * @return Friend Randomly chosen friend.
2544 * NULL in case friend peermap is empty, or all the friends are either
2545 * congested or have crossed trail threshold.
2547 static struct FriendInfo *
2548 select_random_friend ()
2550 unsigned int current_size;
2553 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2554 struct GNUNET_PeerIdentity key_ret;
2555 struct FriendInfo *friend;
2557 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2560 if (0 == current_size)
2563 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2564 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2566 /* Iterate till you don't reach to index. */
2567 for (j = 0; j < index ; j++)
2568 GNUNET_assert (GNUNET_YES ==
2569 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2573 /* Reset the index in friend peermap to 0 as we reached to the end. */
2574 if (j == current_size)
2577 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2578 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2582 /* Get the friend stored at the index, j*/
2583 GNUNET_assert (GNUNET_YES ==
2584 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2586 (const void **)&friend));
2588 /* This friend is not congested and has not crossed trail threshold. */
2589 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2590 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2596 } while (j != index);
2598 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2604 * Compute 64 bit value of finger_identity corresponding to a finger index using
2606 * For all fingers, n.finger[i] = n + pow (2,i),
2607 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2608 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2609 * @param finger_index Index corresponding to which we calculate 64 bit value.
2610 * @return 64 bit value.
2613 compute_finger_identity_value (unsigned int finger_index)
2617 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2618 // TODO: Check how and if to use ntohll
2619 my_id64 = GNUNET_ntohll (my_id64);
2621 /* Are we looking for immediate predecessor? */
2622 if (PREDECESSOR_FINGER_ID == finger_index)
2623 return (my_id64 - 1);
2626 uint64_t add = (uint64_t)1 << finger_index;
2627 return (my_id64 + add);
2631 //TODO move at top, write comment.
2632 static struct GNUNET_TIME_Relative next_send_time;
2636 * Choose a random friend. Calculate the next finger identity to search,from
2637 * current_search_finger_index. Start looking for the trail to reach to
2638 * finger identity through this random friend.
2640 * @param cls closure for this task
2641 * @param tc the context under which the task is running
2644 send_find_finger_trail_message (void *cls,
2645 const struct GNUNET_SCHEDULER_TaskContext *tc)
2647 struct FriendInfo *target_friend;
2648 struct GNUNET_HashCode trail_id;
2649 struct GNUNET_HashCode intermediate_trail_id;
2650 unsigned int is_predecessor;
2651 uint64_t finger_id_value;
2653 /* Schedule another send_find_finger_trail_message task. */
2654 find_finger_trail_task =
2655 GNUNET_SCHEDULER_add_delayed (next_send_time,
2656 &send_find_finger_trail_message,
2659 /* No space in my routing table. (Source and destination peers also store entries
2660 * in their routing table). */
2661 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2665 target_friend = select_random_friend ();
2666 if (NULL == target_friend)
2671 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2673 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2678 /* Generate a unique trail id for trail we are trying to setup. */
2679 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2680 &trail_id, sizeof (trail_id));
2681 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2683 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2684 target_friend->id, target_friend, 0, NULL,
2685 is_predecessor, trail_id,
2686 intermediate_trail_id);
2691 * In case there are already maximum number of possible trails to reach to a
2692 * finger, then check if the new trail's length is lesser than any of the
2694 * If yes then replace that old trail by new trail.
2696 * Note: Here we are taking length as a parameter to choose the best possible
2697 * trail, but there could be other parameters also like:
2698 * 1. duration of existence of a trail - older the better.
2699 * 2. if the new trail is completely disjoint than the
2700 * other trails, then may be choosing it is better.
2702 * @param existing_finger
2703 * @param new_finger_trail
2704 * @param new_finger_trail_length
2705 * @param new_finger_trail_id
2708 select_and_replace_trail (struct FingerInfo *existing_finger,
2709 const struct GNUNET_PeerIdentity *new_trail,
2710 unsigned int new_trail_length,
2711 struct GNUNET_HashCode new_trail_id)
2713 struct Trail *trail_list_iterator;
2714 unsigned int largest_trail_length;
2715 unsigned int largest_trail_index;
2716 struct Trail_Element *trail_element;
2719 largest_trail_length = new_trail_length;
2720 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2722 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2724 for (i = 0; i < existing_finger->trails_count; i++)
2726 trail_list_iterator = &existing_finger->trail_list[i];
2727 if (trail_list_iterator->trail_length > largest_trail_length)
2729 largest_trail_length = trail_list_iterator->trail_length;
2730 largest_trail_index = i;
2734 /* New trail is not better than existing ones. Send trail teardown. */
2735 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2737 struct GNUNET_PeerIdentity next_hop;
2739 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2740 GDS_ROUTING_remove_trail (new_trail_id);
2741 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2742 GDS_ROUTING_SRC_TO_DEST,
2747 /* Send trail teardown message across the replaced trail. */
2748 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2749 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2750 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2751 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2752 GDS_ROUTING_SRC_TO_DEST,
2753 replace_trail->trail_head->peer);
2754 /* Free the trail. */
2755 while (NULL != (trail_element = replace_trail->trail_head))
2757 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2758 replace_trail->trail_tail, trail_element);
2759 GNUNET_free_non_null (trail_element);
2762 /* Add new trial at that location. */
2763 replace_trail->is_present = GNUNET_YES;
2764 replace_trail->trail_length = new_trail_length;
2765 replace_trail->trail_id = new_trail_id;
2766 //FIXME: Do we need to add pointers for head and tail.
2768 while (i < new_trail_length)
2770 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2771 element->peer = new_trail[i];
2773 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2774 replace_trail->trail_tail,
2781 * Check if the new trail to reach to finger is unique or do we already have
2782 * such a trail present for finger.
2783 * @param existing_finger Finger identity
2784 * @param new_trail New trail to reach @a existing_finger
2785 * @param trail_length Total number of peers in new_trail.
2786 * @return #GNUNET_YES if the new trail is unique
2787 * #GNUNET_NO if same trail is already present.
2790 is_new_trail_unique (struct FingerInfo *existing_finger,
2791 const struct GNUNET_PeerIdentity *new_trail,
2792 unsigned int trail_length)
2794 struct Trail *trail_list_iterator;
2795 struct Trail_Element *trail_element;
2798 int trail_unique = GNUNET_NO;
2800 GNUNET_assert (existing_finger->trails_count > 0);
2802 /* Iterate over list of trails. */
2803 for (i = 0; i < existing_finger->trails_count; i++)
2805 trail_list_iterator = &(existing_finger->trail_list[i]);
2806 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2808 /* New trail and existing trail length are not same. */
2809 if (trail_list_iterator->trail_length != trail_length)
2811 trail_unique = GNUNET_YES;
2815 trail_element = trail_list_iterator->trail_head;
2816 GNUNET_assert (trail_element != NULL);
2817 for (j = 0; j < trail_list_iterator->trail_length; j++)
2819 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2820 &trail_element->peer))
2822 trail_unique = GNUNET_YES;
2825 trail_element = trail_element->next;
2829 return trail_unique;
2834 * Add a new trail to existing finger. This function is called only when finger
2835 * is not my own identity or a friend.
2836 * @param existing_finger Finger
2837 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2838 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2839 * @param new_finger_trail_id Unique identifier of the trail.
2842 add_new_trail (struct FingerInfo *existing_finger,
2843 const struct GNUNET_PeerIdentity *new_trail,
2844 unsigned int new_trail_length,
2845 struct GNUNET_HashCode new_trail_id)
2847 struct Trail *trail_list_iterator;
2848 struct FriendInfo *first_friend;
2851 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2857 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2858 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2859 trail_list_iterator->trail_id = new_trail_id;
2860 trail_list_iterator->trail_length = new_trail_length;
2861 existing_finger->trails_count++;
2862 trail_list_iterator->is_present = GNUNET_YES;
2864 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2865 &existing_finger->finger_identity)));
2866 /* If finger is a friend then we never call this function. */
2867 GNUNET_assert (new_trail_length > 0);
2869 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2871 first_friend->trails_count++;
2873 for (i = 0; i < new_trail_length; i++)
2875 struct Trail_Element *element;
2877 element = GNUNET_new (struct Trail_Element);
2878 element->peer = new_trail[i];
2879 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2880 trail_list_iterator->trail_tail,
2883 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2889 * FIXME Check if this function is called for opposite direction if yes then
2890 * take it as parameter.
2891 * Get the next hop to send trail teardown message from routing table and
2892 * then delete the entry from routing table. Send trail teardown message for a
2893 * specific trail of a finger.
2894 * @param finger Finger whose trail is to be removed.
2895 * @param trail List of peers in trail from me to a finger, NOT including
2899 send_trail_teardown (struct FingerInfo *finger,
2900 struct Trail *trail)
2902 struct FriendInfo *friend;
2903 struct GNUNET_PeerIdentity *next_hop;
2905 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2906 GDS_ROUTING_SRC_TO_DEST);
2908 if (NULL == next_hop)
2913 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2916 GNUNET_assert (trail->is_present == GNUNET_YES);
2918 /* Finger is not a friend. */
2919 if (trail->trail_length > 0)
2921 GNUNET_assert (NULL != (friend =
2922 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2923 &trail->trail_head->peer)));
2927 GNUNET_assert (NULL != (friend =
2928 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2929 &finger->finger_identity)));
2932 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2933 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2934 friend->trails_count--;
2935 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2936 GDS_ROUTING_SRC_TO_DEST,
2942 * Send trail teardown message across all the trails to reach to finger.
2943 * @param finger Finger whose all the trail should be freed.
2946 send_all_finger_trails_teardown (struct FingerInfo *finger)
2950 for (i = 0; i < finger->trails_count; i++)
2952 struct Trail *trail;
2954 trail = &finger->trail_list[i];
2955 GNUNET_assert (trail->is_present == GNUNET_YES);
2956 send_trail_teardown (finger, trail);
2957 trail->is_present = GNUNET_NO;
2963 * Free a specific trail
2964 * @param trail List of peers to be freed.
2967 free_trail (struct Trail *trail)
2969 struct Trail_Element *trail_element;
2971 while (NULL != (trail_element = trail->trail_head))
2973 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2976 GNUNET_free_non_null (trail_element);
2978 trail->trail_head = NULL;
2979 trail->trail_tail = NULL;
2984 * Free finger and its trail.
2985 * @param finger Finger to be freed.
2988 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2990 struct Trail *trail;
2993 /* Free all the trails to reach to finger */
2994 for (i = 0; i < finger->trails_count; i++)
2996 trail = &finger->trail_list[i];
2997 //FIXME: Check if there are any missing entry in this list because of
2998 // how we insert. If not then no need of this check.
2999 if (GNUNET_NO == trail->is_present)
3002 if (trail->trail_length > 0)
3006 trail->is_present = GNUNET_NO;
3009 finger->is_present = GNUNET_NO;
3010 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
3015 * Add a new entry in finger table at finger_table_index.
3016 * In case I am my own finger, then we don't have a trail. In case of a friend,
3017 * we have a trail with unique id and '0' trail length.
3018 * In case a finger is a friend, then increment the trails count of the friend.
3019 * @param finger_identity Peer Identity of new finger
3020 * @param finger_trail Trail to reach from me to finger (excluding both end points).
3021 * @param finger_trail_length Total number of peers in @a finger_trail.
3022 * @param trail_id Unique identifier of the trail.
3023 * @param finger_table_index Index in finger table.
3026 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
3027 const struct GNUNET_PeerIdentity *finger_trail,
3028 unsigned int finger_trail_length,
3029 struct GNUNET_HashCode trail_id,
3030 unsigned int finger_table_index)
3032 struct FingerInfo *new_entry;
3033 struct FriendInfo *first_trail_hop;
3034 struct Trail *trail;
3037 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3038 GNUNET_assert (NULL != GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST));
3039 new_entry = GNUNET_new (struct FingerInfo);
3040 new_entry->finger_identity = finger_identity;
3041 new_entry->finger_table_index = finger_table_index;
3042 new_entry->is_present = GNUNET_YES;
3044 /* If the new entry is my own identity. */
3045 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3048 new_entry->trails_count = 0;
3049 finger_table[finger_table_index] = *new_entry;
3050 GNUNET_free (new_entry);
3054 /* If finger is a friend, then we don't actually have a trail.
3055 * Just a trail id */
3056 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3059 new_entry->trail_list[0].trail_id = trail_id;
3060 new_entry->trails_count = 1;
3061 new_entry->trail_list[0].is_present = GNUNET_YES;
3062 new_entry->trail_list[0].trail_length = 0;
3063 new_entry->trail_list[0].trail_head = NULL;
3064 new_entry->trail_list[0].trail_tail = NULL;
3065 finger_table[finger_table_index] = *new_entry;
3066 GNUNET_assert (NULL !=
3068 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3069 &finger_identity)));
3071 first_trail_hop->trails_count++;
3072 GNUNET_free (new_entry);
3076 GNUNET_assert (NULL !=
3078 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3079 &finger_trail[0])));
3080 new_entry->trails_count = 1;
3081 first_trail_hop->trails_count++;
3083 /* Copy the finger trail into trail. */
3084 trail = GNUNET_new (struct Trail);
3085 while (i < finger_trail_length)
3087 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3089 element->next = NULL;
3090 element->prev = NULL;
3091 element->peer = finger_trail[i];
3092 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3098 /* Add trail to trail list. */
3099 new_entry->trail_list[0].trail_head = trail->trail_head;
3100 new_entry->trail_list[0].trail_tail = trail->trail_tail;
3101 new_entry->trail_list[0].trail_length = finger_trail_length;
3102 new_entry->trail_list[0].trail_id = trail_id;
3103 new_entry->trail_list[0].is_present = GNUNET_YES;
3104 finger_table[finger_table_index] = *new_entry;
3105 GNUNET_free (new_entry);
3111 * Scan the trail to check if there is any other friend in the trail other than
3112 * first hop. If yes then shortcut the trail, send trail compression message to
3113 * peers which are no longer part of trail and send back the updated trail
3114 * and trail_length to calling function.
3115 * @param finger_identity Finger whose trail we will scan.
3116 * @param finger_trail [in, out] Trail to reach from source to finger,
3117 * @param finger_trail_length Total number of peers in original finger_trail.
3118 * @param finger_trail_id Unique identifier of the finger trail.
3119 * @return updated trail length in case we shortcut the trail, else original
3122 static struct GNUNET_PeerIdentity *
3123 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
3124 const struct GNUNET_PeerIdentity *trail,
3125 unsigned int trail_length,
3126 struct GNUNET_HashCode trail_id,
3127 int *new_trail_length)
3129 struct FriendInfo *target_friend;
3130 struct GNUNET_PeerIdentity *new_trail;
3133 /* I am my own finger. */
3134 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3136 *new_trail_length = 0;
3140 if (0 == trail_length)
3142 *new_trail_length = 0;
3146 /* If finger identity is a friend. */
3147 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3149 *new_trail_length = 0;
3151 /* If there is trail to reach this finger/friend */
3152 if (trail_length > 0)
3154 /* Finger is your first friend. */
3155 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3156 GNUNET_assert (NULL !=
3158 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3162 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3163 trail_id, finger_identity,
3169 /* For other cases, when its neither a friend nor my own identity.*/
3170 for (i = trail_length - 1; i > 0; i--)
3172 /* If the element at this index in trail is a friend. */
3173 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3175 struct FriendInfo *target_friend;
3178 GNUNET_assert (NULL !=
3180 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3182 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3183 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3188 /* Copy the trail from index i to index (trail_length -1) into a new trail
3189 * and update new trail length */
3190 *new_trail_length = trail_length - i;
3191 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (*new_trail_length));
3192 while (i < trail_length)
3194 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3202 /* If we did not compress the trail, return the original trail back.*/
3203 *new_trail_length = trail_length;
3204 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3205 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3211 * Periodic task to verify current successor. There can be multiple trails to reach
3212 * to successor, choose the shortest one and send verify successor message
3213 * across that trail.
3214 * @param cls closure for this task
3215 * @param tc the context under which the task is running
3218 send_verify_successor_message (void *cls,
3219 const struct GNUNET_SCHEDULER_TaskContext *tc)
3221 struct FriendInfo *target_friend;
3222 struct GNUNET_HashCode trail_id;
3224 struct GNUNET_TIME_Relative next_send_time;
3225 struct Trail *trail;
3226 struct Trail_Element *element;
3227 unsigned int trail_length;
3229 struct FingerInfo *successor;
3231 /* Schedule another send_find_finger_trail_message task. */
3232 next_send_time.rel_value_us =
3233 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3234 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3235 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3236 send_verify_successor_task =
3237 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3240 successor = &finger_table[0];
3241 for (i = 0; i < successor->trails_count; i++)
3243 trail = &successor->trail_list[i];
3244 if(GNUNET_YES == trail->is_present)
3248 if (i == successor->trails_count)
3251 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3252 &successor->finger_identity));
3254 /* Trail stored at this index. */
3255 GNUNET_assert (GNUNET_YES == trail->is_present);
3257 trail_id = trail->trail_id;
3259 GNUNET_assert (NULL != GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST));
3260 trail_length = trail->trail_length;
3262 if (trail_length > 0)
3264 /* Copy the trail into peer list. */
3265 struct GNUNET_PeerIdentity peer_list[trail_length];
3267 element = trail->trail_head;
3268 while (j < trail_length)
3270 peer_list[j] = element->peer;
3271 element = element->next;
3275 GNUNET_assert (NULL != (target_friend =
3276 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3278 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3279 successor->finger_identity,
3280 trail_id, peer_list, trail_length,
3286 GNUNET_assert (NULL != (target_friend =
3287 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3288 &successor->finger_identity)));
3289 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3290 successor->finger_identity,
3299 * FIXME: should this be a periodic task, incrementing the search finger index?
3300 * Update the current search finger index.
3302 * FIXME document parameters!
3305 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3306 unsigned int finger_table_index)
3308 struct FingerInfo *successor;
3310 /* FIXME correct this: only move current index periodically */
3311 if (finger_table_index != current_search_finger_index)
3314 successor = &finger_table[0];
3315 GNUNET_assert (GNUNET_YES == successor->is_present);
3317 /* We were looking for immediate successor. */
3318 if (0 == current_search_finger_index)
3320 /* Start looking for immediate predecessor. */
3321 current_search_finger_index = PREDECESSOR_FINGER_ID;
3323 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3325 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3326 send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3332 current_search_finger_index = current_search_finger_index - 1;
3338 * Get the least significant bit set in val.
3341 * @return Position of first bit set, 65 in case of error.
3344 find_set_bit (uint64_t val)
3364 return 65; /* Some other bit was set to 1 as well. */
3371 * Calculate finger_table_index from initial 64 bit finger identity value that
3372 * we send in trail setup message.
3373 * @param ultimate_destination_finger_value Value that we calculated from our
3374 * identity and finger_table_index.
3375 * @param is_predecessor Is the entry for predecessor or not?
3376 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3377 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3380 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3381 unsigned int is_predecessor)
3385 unsigned int finger_table_index;
3387 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3388 my_id64 = GNUNET_ntohll (my_id64);
3390 /* Is this a predecessor finger? */
3391 if (1 == is_predecessor)
3393 diff = my_id64 - ultimate_destination_finger_value;
3395 finger_table_index = PREDECESSOR_FINGER_ID;
3397 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3402 diff = ultimate_destination_finger_value - my_id64;
3403 finger_table_index = find_set_bit (diff);
3405 return finger_table_index;
3410 * Remove finger and its associated data structures from finger table.
3411 * @param finger Finger to be removed.
3414 remove_existing_finger (struct FingerInfo *existing_finger,
3415 unsigned int finger_table_index)
3417 struct FingerInfo *finger;
3419 finger = &finger_table[finger_table_index];
3420 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3421 &existing_finger->finger_identity));
3422 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3425 GNUNET_assert (GNUNET_YES == finger->is_present);
3427 /* If I am my own finger, then we have no trails. */
3428 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3431 finger->is_present = GNUNET_NO;
3432 memset ((void *)&finger_table[finger_table_index], 0,
3433 sizeof (finger_table[finger_table_index]));
3437 /* For all other fingers, send trail teardown across all the trails to reach
3438 finger, and free the finger. */
3439 send_all_finger_trails_teardown (finger);
3440 free_finger (finger, finger_table_index);
3446 * Check if there is already an entry in finger_table at finger_table_index.
3447 * We get the finger_table_index from 64bit finger value we got from the network.
3448 * -- If yes, then select the closest finger.
3449 * -- If new and existing finger are same, then check if you can store more
3451 * -- If yes then add trail, else keep the best trails to reach to the
3453 * -- If the new finger is closest, remove the existing entry, send trail
3454 * teardown message across all the trails to reach the existing entry.
3455 * Add the new finger.
3456 * -- If new and existing finger are different, and existing finger is closest
3458 * -- Update current_search_finger_index.
3459 * @param finger_identity Peer Identity of new finger
3460 * @param finger_trail Trail to reach the new finger
3461 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3462 * @param is_predecessor Is this entry for predecessor in finger_table?
3463 * @param finger_value 64 bit value of finger identity that we got from network.
3464 * @param finger_trail_id Unique identifier of @finger_trail.
3467 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3468 const struct GNUNET_PeerIdentity *finger_trail,
3469 unsigned int finger_trail_length,
3470 unsigned int is_predecessor,
3471 uint64_t finger_value,
3472 struct GNUNET_HashCode finger_trail_id)
3474 struct FingerInfo *existing_finger;
3475 const struct GNUNET_PeerIdentity *closest_peer;
3476 struct FingerInfo *successor;
3477 int updated_finger_trail_length;
3478 unsigned int finger_table_index;
3480 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3481 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3483 /* Invalid finger_table_index. */
3484 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3486 GNUNET_break_op (0);
3490 /* New entry same as successor. */
3491 if ((0 != finger_table_index) &&
3492 (PREDECESSOR_FINGER_ID != finger_table_index))
3494 successor = &finger_table[0];
3495 if (GNUNET_NO == successor->is_present)
3497 GNUNET_break_op (0);
3500 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3501 &successor->finger_identity))
3503 current_search_finger_index = 0;
3504 /* We slow down the find_finger_trail_task as we have completed the circle. */
3505 next_send_time = GNUNET_TIME_STD_BACKOFF(next_send_time);
3510 struct FingerInfo prev_finger;
3511 prev_finger = finger_table[finger_table_index - 1];
3512 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3513 &prev_finger.finger_identity))
3515 current_search_finger_index--;
3520 existing_finger = &finger_table[finger_table_index];
3522 /* No entry present in finger_table for given finger map index. */
3523 if (GNUNET_NO == existing_finger->is_present)
3525 struct GNUNET_PeerIdentity *updated_trail;
3527 /* Shorten the trail if possible. */
3528 updated_finger_trail_length = finger_trail_length;
3529 updated_trail = scan_and_compress_trail (finger_identity, finger_trail,
3530 finger_trail_length,
3532 &updated_finger_trail_length);
3533 add_new_finger (finger_identity, updated_trail,
3534 updated_finger_trail_length,
3535 finger_trail_id, finger_table_index);
3536 GNUNET_free_non_null(updated_trail);
3537 update_current_search_finger_index (finger_identity,
3538 finger_table_index);
3543 /* If existing entry and finger identity are not same. */
3544 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3547 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3552 /* If the new finger is the closest peer. */
3553 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3555 struct GNUNET_PeerIdentity *updated_trail;
3556 /* Shorten the trail if possible. */
3557 updated_finger_trail_length = finger_trail_length;
3559 scan_and_compress_trail (finger_identity, finger_trail,
3560 finger_trail_length, finger_trail_id,
3561 &updated_finger_trail_length);
3562 remove_existing_finger (existing_finger, finger_table_index);
3563 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3564 finger_trail_id, finger_table_index);
3565 GNUNET_free_non_null((struct GNUNET_PeerIdentity *)updated_trail);
3569 /* Existing finger is the closest one. We need to send trail teardown
3570 across the trail setup in routing table of all the peers. */
3571 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3573 if (finger_trail_length > 0)
3574 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3575 GDS_ROUTING_SRC_TO_DEST,
3578 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3579 GDS_ROUTING_SRC_TO_DEST,
3586 /* If both new and existing entry are same as my_identity, then do nothing. */
3587 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3592 /* If the existing finger is not a friend. */
3594 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3595 &existing_finger->finger_identity))
3597 struct GNUNET_PeerIdentity *updated_trail;
3599 /* Shorten the trail if possible. */
3600 updated_finger_trail_length = finger_trail_length;
3602 scan_and_compress_trail (finger_identity, finger_trail,
3603 finger_trail_length, finger_trail_id,
3604 &updated_finger_trail_length);
3605 /* If there is space to store more trails. */
3606 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3607 add_new_trail (existing_finger, updated_trail,
3608 updated_finger_trail_length, finger_trail_id);
3610 select_and_replace_trail (existing_finger, updated_trail,
3611 updated_finger_trail_length, finger_trail_id);
3615 update_current_search_finger_index (finger_identity, finger_table_index);
3621 * FIXME: Check for loop in the request. If you already are part of put path,
3622 * then you need to reset the put path length.
3623 * Core handler for P2P put messages.
3624 * @param cls closure
3625 * @param peer sender of the request
3626 * @param message message
3627 * @return #GNUNET_OK to keep the connection open,
3628 * #GNUNET_SYSERR to close it (signal serious error)
3631 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3632 const struct GNUNET_MessageHeader *message)
3634 struct PeerPutMessage *put;
3635 struct GNUNET_PeerIdentity *put_path;
3636 struct GNUNET_PeerIdentity best_known_dest;
3637 struct GNUNET_HashCode intermediate_trail_id;
3638 struct GNUNET_PeerIdentity *next_hop;
3639 enum GNUNET_DHT_RouteOption options;
3640 struct GNUNET_HashCode test_key;
3644 size_t payload_size;
3647 #if ENABLE_MALICIOUS
3648 if(1 == act_malicious)
3650 DEBUG("I am malicious,dropping put request. \n");
3655 msize = ntohs (message->size);
3656 if (msize < sizeof (struct PeerPutMessage))
3658 GNUNET_break_op (0);
3662 put = (struct PeerPutMessage *) message;
3663 putlen = ntohl (put->put_path_length);
3667 sizeof (struct PeerPutMessage) +
3668 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3670 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3672 GNUNET_break_op (0);
3675 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
3676 GNUNET_STATISTICS_update (GDS_stats,
3678 ("# Bytes received from other peers"), (int64_t) msize,
3681 best_known_dest = put->best_known_destination;
3682 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3683 payload = &put_path[putlen];
3684 options = ntohl (put->options);
3685 intermediate_trail_id = put->intermediate_trail_id;
3687 payload_size = msize - (sizeof (struct PeerPutMessage) +
3688 putlen * sizeof (struct GNUNET_PeerIdentity));
3690 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3691 payload, payload_size, &test_key))
3694 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3696 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3697 GNUNET_break_op (0);
3698 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3699 "PUT with key `%s' for block with key %s\n",
3700 put_s, GNUNET_h2s_full (&test_key));
3701 GNUNET_free (put_s);
3706 GNUNET_break_op (0);
3709 /* cannot verify, good luck */
3713 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3715 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3716 ntohl (put->block_type),
3718 NULL, 0, /* bloom filer */
3719 NULL, 0, /* xquery */
3720 payload, payload_size))
3722 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3723 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3726 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3727 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3728 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3729 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3730 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3731 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3733 GNUNET_break_op (0);
3739 /* Check if you are present in the trail already. */
3741 for (i = 0; i < putlen; i++)
3743 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3750 //FIXME: always add yourself to the peer list not the sender.
3751 /* extend 'put path' by sender */
3752 struct GNUNET_PeerIdentity pp[putlen + 1];
3753 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3755 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3762 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3763 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3765 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3766 GDS_ROUTING_SRC_TO_DEST);
3767 if (NULL == next_hop)
3769 GNUNET_STATISTICS_update (GDS_stats,
3770 gettext_noop ("# Next hop to forward the packet not found "
3771 "trail setup request, packet dropped."),
3773 return GNUNET_SYSERR;
3778 struct Closest_Peer successor;
3779 key_value = GNUNET_ntohll (key_value);
3780 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3781 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3782 *next_hop = successor.next_hop;
3783 intermediate_trail_id = successor.trail_id;
3784 best_known_dest = successor.best_known_destination;
3787 GDS_CLIENTS_process_put (options,
3788 ntohl (put->block_type),
3789 ntohl (put->hop_count),
3790 ntohl (put->desired_replication_level),
3792 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3797 /* I am the final destination */
3798 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3800 DEBUG("PUT destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(put->key)));
3801 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3802 &(put->key),putlen, pp, ntohl (put->block_type),
3803 payload_size, payload);
3807 GDS_NEIGHBOURS_send_put (&put->key,
3808 ntohl (put->block_type),ntohl (put->options),
3809 ntohl (put->desired_replication_level),
3810 best_known_dest, intermediate_trail_id, next_hop,
3811 ntohl (put->hop_count), putlen, pp,
3812 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3813 payload, payload_size);
3820 * FIXME: Check for loop in the request. If you already are part of get path,
3821 * then you need to reset the get path length.
3822 * Core handler for p2p get requests.
3824 * @param cls closure
3825 * @param peer sender of the request
3826 * @param message message
3827 * @return #GNUNET_OK to keep the connection open,
3828 * #GNUNET_SYSERR to close it (signal serious error)
3831 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3832 const struct GNUNET_MessageHeader *message)
3834 const struct PeerGetMessage *get;
3835 const struct GNUNET_PeerIdentity *get_path;
3836 struct GNUNET_PeerIdentity best_known_dest;
3837 struct GNUNET_HashCode intermediate_trail_id;
3838 struct GNUNET_PeerIdentity *next_hop;
3839 uint32_t get_length;
3843 #if ENABLE_MALICIOUS
3844 if(1 == act_malicious)
3846 DEBUG("I am malicious,dropping get request. \n");
3851 msize = ntohs (message->size);
3852 if (msize < sizeof (struct PeerGetMessage))
3854 GNUNET_break_op (0);
3858 get = (const struct PeerGetMessage *)message;
3859 get_length = ntohl (get->get_path_length);
3860 best_known_dest = get->best_known_destination;
3861 intermediate_trail_id = get->intermediate_trail_id;
3862 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3865 sizeof (struct PeerGetMessage) +
3866 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3868 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3870 GNUNET_break_op (0);
3873 DEBUG("PUT FOR DATA_SIZE = %lu\n",msize);
3874 GNUNET_STATISTICS_update (GDS_stats,
3876 ("# Bytes received from other peers"), msize,
3879 /* Add sender to get path */
3880 struct GNUNET_PeerIdentity gp[get_length + 1];
3882 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3883 gp[get_length] = *peer;
3884 get_length = get_length + 1;
3886 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3887 key_value = GNUNET_ntohll (key_value);
3889 /* I am not the final destination. I am part of trail to reach final dest. */
3890 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3892 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3893 GDS_ROUTING_SRC_TO_DEST);
3894 if (NULL == next_hop)
3896 GNUNET_STATISTICS_update (GDS_stats,
3897 gettext_noop ("# Next hop to forward the packet not found "
3898 "GET request, packet dropped."),
3900 return GNUNET_SYSERR;
3905 struct Closest_Peer successor;
3907 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3908 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3909 *next_hop = successor.next_hop;
3910 best_known_dest = successor.best_known_destination;
3911 intermediate_trail_id = successor.trail_id;
3914 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3915 get->desired_replication_level, get->get_path_length,
3917 /* I am the final destination. */
3918 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3920 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(get->key)));
3921 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3923 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3924 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3925 get_length = get_length + 1;
3927 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3928 get_length, final_get_path,
3929 &final_get_path[get_length-2], &my_identity);
3933 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3934 get->desired_replication_level, best_known_dest,
3935 intermediate_trail_id, next_hop, 0,
3943 * Core handler for get result
3944 * @param cls closure
3945 * @param peer sender of the request
3946 * @param message message
3947 * @return #GNUNET_OK to keep the connection open,
3948 * #GNUNET_SYSERR to close it (signal serious error)
3951 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3952 const struct GNUNET_MessageHeader *message)
3954 const struct PeerGetResultMessage *get_result;
3955 const struct GNUNET_PeerIdentity *get_path;
3956 const struct GNUNET_PeerIdentity *put_path;
3957 const void *payload;
3958 size_t payload_size;
3960 unsigned int getlen;
3961 unsigned int putlen;
3962 int current_path_index;
3964 msize = ntohs (message->size);
3965 if (msize < sizeof (struct PeerGetResultMessage))
3967 GNUNET_break_op (0);
3971 get_result = (const struct PeerGetResultMessage *)message;
3972 getlen = ntohl (get_result->get_path_length);
3973 putlen = ntohl (get_result->put_path_length);
3976 sizeof (struct PeerGetResultMessage) +
3977 getlen * sizeof (struct GNUNET_PeerIdentity) +
3978 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3980 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3982 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3984 GNUNET_break_op (0);
3987 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3988 GNUNET_STATISTICS_update (GDS_stats,
3990 ("# Bytes received from other peers"), msize,
3993 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3994 get_path = &put_path[putlen];
3995 payload = (const void *) &get_path[getlen];
3996 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3997 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3999 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
4001 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
4002 getlen, get_path, putlen,
4003 put_path, get_result->type, payload_size, payload);
4008 current_path_index = search_my_index (get_path, getlen);
4009 if (-1 == current_path_index )
4011 DEBUG ("No entry found in get path.\n");
4013 return GNUNET_SYSERR;
4015 if((getlen + 1) == current_path_index)
4017 DEBUG("Present twice in get path. Not allowed. \n");
4019 return GNUNET_SYSERR;
4021 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
4022 &get_path[current_path_index - 1],
4023 &(get_result->querying_peer), putlen, put_path,
4024 getlen, get_path, get_result->expiration_time,
4025 payload, payload_size);
4028 return GNUNET_SYSERR;
4033 * Find the next hop to pass trail setup message. First find the local best known
4034 * hop from your own identity, friends and finger. If you were part of trail,
4035 * then get the next hop from routing table. Compare next_hop from routing table
4036 * and local best known hop, and return the closest one to final_dest_finger_val
4037 * @param final_dest_finger_val 64 bit value of finger identity
4038 * @param intermediate_trail_id If you are part of trail to reach to some other
4039 * finger, then it is the trail id to reach to
4040 * that finger, else set to 0.
4041 * @param is_predecessor Are we looking for closest successor or predecessor.
4042 * @param current_dest In case you are part of trail, then finger to which
4043 * we should forward the message. Else my own identity
4044 * @return Closest Peer for @a final_dest_finger_val
4046 static struct Closest_Peer
4047 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
4048 struct GNUNET_HashCode intermediate_trail_id,
4049 unsigned int is_predecessor,
4050 struct GNUNET_PeerIdentity prev_hop,
4051 struct GNUNET_PeerIdentity source,
4052 struct GNUNET_PeerIdentity *current_dest)
4054 struct Closest_Peer peer;
4056 /* Find a local best known peer. */
4057 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
4059 /* Am I just a part of a trail towards a finger (current_destination)? */
4060 /* Select best successor among one found locally and current_destination
4061 * that we got from network.*/
4062 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
4063 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
4066 const struct GNUNET_PeerIdentity *closest_peer;
4068 closest_peer = select_closest_peer (&peer.best_known_destination,
4070 final_dest_finger_val,
4073 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
4074 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
4076 struct GNUNET_PeerIdentity *next_hop;
4078 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4079 GDS_ROUTING_SRC_TO_DEST);
4080 /* It may happen that trail teardown message got delayed and hence,
4081 the previous hop sent the message over intermediate trail id.In that
4082 case next_hop could be NULL. */
4083 if(NULL != next_hop)
4085 peer.next_hop = *next_hop;
4086 peer.best_known_destination = *current_dest;
4087 peer.trail_id = intermediate_trail_id;
4096 * Core handle for PeerTrailSetupMessage.
4097 * @param cls closure
4098 * @param message message
4099 * @param peer peer identity this notification is about
4100 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4103 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
4104 const struct GNUNET_MessageHeader *message)
4106 const struct PeerTrailSetupMessage *trail_setup;
4107 const struct GNUNET_PeerIdentity *trail_peer_list;
4108 struct GNUNET_PeerIdentity current_dest;
4109 struct FriendInfo *target_friend;
4110 struct GNUNET_PeerIdentity source;
4111 uint64_t final_dest_finger_val;
4112 struct GNUNET_HashCode intermediate_trail_id;
4113 struct GNUNET_HashCode trail_id;
4114 unsigned int is_predecessor;
4115 uint32_t trail_length;
4119 msize = ntohs (message->size);
4120 if (msize < sizeof (struct PeerTrailSetupMessage))
4122 GNUNET_break_op (0);
4123 return GNUNET_SYSERR;
4126 trail_setup = (const struct PeerTrailSetupMessage *) message;
4127 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4128 sizeof (struct GNUNET_PeerIdentity) != 0)
4130 GNUNET_break_op (0);
4133 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4134 sizeof (struct GNUNET_PeerIdentity);
4137 GNUNET_STATISTICS_update (GDS_stats,
4139 ("# Bytes received from other peers"), msize,
4142 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4143 current_dest = trail_setup->best_known_destination;
4144 trail_id = trail_setup->trail_id;
4145 final_dest_finger_val =
4146 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4147 source = trail_setup->source_peer;
4148 is_predecessor = ntohl (trail_setup->is_predecessor);
4149 intermediate_trail_id = trail_setup->intermediate_trail_id;
4151 /* Did the friend insert its ID in the trail list? */
4152 if (trail_length > 0 &&
4153 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
4155 GNUNET_break_op (0);
4156 return GNUNET_SYSERR;
4159 /* If I was the source and got the message back, then set trail length to 0.*/
4160 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4165 /* Check if you are present in the trail seen so far? */
4166 for (i = 0; i < trail_length ; i++)
4168 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4170 trail_length = i; /* Check that you add yourself again */
4175 /* Is my routing table full? */
4176 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4178 GNUNET_assert (NULL !=
4180 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4181 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4182 my_identity, is_predecessor,
4183 trail_peer_list, trail_length,
4184 trail_id, target_friend,
4185 CONGESTION_TIMEOUT);
4189 /* Get the next hop to forward the trail setup request. */
4190 struct Closest_Peer next_peer =
4191 get_local_best_known_next_hop (final_dest_finger_val,
4192 intermediate_trail_id,
4198 /* Am I the final destination? */
4199 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4202 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4204 finger_table_add (my_identity, NULL, 0, is_predecessor,
4205 final_dest_finger_val, trail_id);
4209 GDS_ROUTING_add (trail_id, *peer, my_identity);
4210 if (trail_length > 0)
4212 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4213 &trail_peer_list[trail_length-1]);
4216 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4218 if (NULL == target_friend)
4220 GNUNET_break_op (0);
4221 return GNUNET_SYSERR;
4224 GDS_NEIGHBOURS_send_trail_setup_result (source,
4226 target_friend, trail_length,
4229 final_dest_finger_val,trail_id);
4231 else /* I'm not the final destination. */
4233 GNUNET_assert (NULL !=
4235 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4236 &next_peer.next_hop)));
4238 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4240 /* Add yourself to list of peers. */
4241 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4243 memcpy (peer_list, trail_peer_list,
4244 trail_length * sizeof (struct GNUNET_PeerIdentity));
4245 peer_list[trail_length] = my_identity;
4247 GDS_NEIGHBOURS_send_trail_setup (source,
4248 final_dest_finger_val,
4249 next_peer.best_known_destination,
4250 target_friend, trail_length + 1, peer_list,
4251 is_predecessor, trail_id,
4252 next_peer.trail_id);
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 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4299 sizeof (struct GNUNET_PeerIdentity);
4300 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4301 sizeof (struct GNUNET_PeerIdentity) != 0)
4303 GNUNET_break_op (0);
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 /* If I am my own finger identity, error. */
4336 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4338 GNUNET_break_op (0);
4339 return GNUNET_SYSERR;
4342 GDS_ROUTING_add (trail_id, my_identity, *peer);
4343 finger_table_add (finger_identity, trail_peer_list, trail_length,
4344 is_predecessor, ulitmate_destination_finger_value, trail_id);
4348 /* Get my location in the trail. */
4349 my_index = search_my_index (trail_peer_list, trail_length);
4352 DEBUG ("Not found in trail\n");
4354 return GNUNET_SYSERR;
4357 if ((trail_length + 1) == my_index)
4359 DEBUG ("Found twice in trail.\n");
4361 return GNUNET_SYSERR;
4366 if(trail_length > 1)
4367 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4370 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4372 next_hop = trail_result->querying_peer;
4376 if(my_index == trail_length - 1)
4379 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4384 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4386 next_hop = trail_peer_list[my_index - 1];
4389 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4390 if (NULL == target_friend)
4392 GNUNET_break_op (0);
4393 return GNUNET_SYSERR;
4395 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4396 &(trail_result->finger_identity))))
4398 GNUNET_break_op (0);
4399 return GNUNET_SYSERR;
4401 GDS_ROUTING_add (trail_id, next_hop, *peer);
4402 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4403 target_friend, trail_length, trail_peer_list,
4405 ulitmate_destination_finger_value,
4413 * @param trail Trail to be inverted
4414 * @param trail_length Total number of peers in the trail.
4415 * @return Updated trail
4417 static struct GNUNET_PeerIdentity *
4418 invert_trail (const struct GNUNET_PeerIdentity *trail,
4419 unsigned int trail_length)
4423 struct GNUNET_PeerIdentity *inverted_trail;
4425 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4428 j = trail_length - 1;
4429 while (i < trail_length)
4431 inverted_trail[i] = trail[j];
4436 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4437 &inverted_trail[0]));
4438 return inverted_trail;
4443 * Return the shortest trail among all the trails to reach to finger from me.
4444 * @param finger Finger
4445 * @param shortest_trail_length[out] Trail length of shortest trail from me
4447 * @return Shortest trail.
4449 static struct GNUNET_PeerIdentity *
4450 get_shortest_trail (struct FingerInfo *finger,
4451 unsigned int *trail_length)
4453 struct Trail *trail;
4454 unsigned int flag = 0;
4455 unsigned int shortest_trail_index = 0;
4456 int shortest_trail_length = -1;
4457 struct Trail_Element *trail_element;
4458 struct GNUNET_PeerIdentity *trail_list;
4461 trail = GNUNET_new (struct Trail);
4463 /* Get the shortest trail to reach to current successor. */
4464 for (i = 0; i < finger->trails_count; i++)
4466 trail = &finger->trail_list[i];
4470 shortest_trail_index = i;
4471 shortest_trail_length = trail->trail_length;
4476 if (shortest_trail_length > trail->trail_length)
4478 shortest_trail_index = i;
4479 shortest_trail_length = trail->trail_length;
4484 /* Copy the shortest trail and return. */
4485 trail = &finger->trail_list[shortest_trail_index];
4486 trail_element = trail->trail_head;
4488 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4489 shortest_trail_length);
4491 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4493 trail_list[i] = trail_element->peer;
4496 GNUNET_assert(shortest_trail_length != -1);
4498 *trail_length = shortest_trail_length;
4504 * Check if trail_1 and trail_2 have any common element. If yes then join
4505 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4506 * @param trail_1 Trail from source to me, NOT including endpoints.
4507 * @param trail_1_len Total number of peers @a trail_1
4508 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4509 * @param trail_2_len Total number of peers @a trail_2
4510 * @param joined_trail_len Total number of peers in combined trail of trail_1
4512 * @return Joined trail.
4514 static struct GNUNET_PeerIdentity *
4515 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4516 unsigned int trail_1_len,
4517 struct GNUNET_PeerIdentity *trail_2,
4518 unsigned int trail_2_len,
4519 unsigned int *joined_trail_len)
4521 struct GNUNET_PeerIdentity *joined_trail;
4526 for (i = 0; i < trail_1_len; i++)
4528 for (j = 0; j < trail_2_len; j++)
4530 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4533 *joined_trail_len = i + (trail_2_len - j);
4534 joined_trail = GNUNET_malloc (*joined_trail_len *
4535 sizeof(struct GNUNET_PeerIdentity));
4538 /* Copy all the elements from 0 to i into joined_trail. */
4539 for(k = 0; k < ( i+1); k++)
4541 joined_trail[k] = trail_1[k];
4544 /* Increment j as entry stored is same as entry stored at i*/
4547 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4548 while(k <= (*joined_trail_len - 1))
4550 joined_trail[k] = trail_2[j];
4555 return joined_trail;
4559 /* Here you should join the trails. */
4560 *joined_trail_len = trail_1_len + trail_2_len + 1;
4561 joined_trail = GNUNET_malloc (*joined_trail_len *
4562 sizeof(struct GNUNET_PeerIdentity));
4565 for(i = 0; i < trail_1_len;i++)
4567 joined_trail[i] = trail_1[i];
4570 joined_trail[i] = my_identity;
4573 for (j = 0; i < *joined_trail_len; i++,j++)
4575 joined_trail[i] = trail_2[j];
4578 return joined_trail;
4583 * Return the trail from source to my current predecessor. Check if source
4584 * is already part of the this trail, if yes then return the shorten trail.
4585 * @param current_trail Trail from source to me, NOT including the endpoints.
4586 * @param current_trail_length Number of peers in @a current_trail.
4587 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4588 * source to my predecessor, NOT including
4590 * @return Trail from source to my predecessor.
4592 static struct GNUNET_PeerIdentity *
4593 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4594 const struct GNUNET_PeerIdentity *trail_src_to_me,
4595 unsigned int trail_src_to_me_len,
4596 unsigned int *trail_src_to_curr_pred_length)
4598 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4599 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4600 unsigned int trail_me_to_curr_pred_length;
4601 struct FingerInfo *current_predecessor;
4605 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4607 /* Check if trail_src_to_me contains current_predecessor. */
4608 for (i = 0; i < trail_src_to_me_len; i++)
4610 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4611 ¤t_predecessor->finger_identity))
4615 *trail_src_to_curr_pred_length = i;
4620 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4621 sizeof(struct GNUNET_PeerIdentity));
4622 for(j = 0; j < i;j++)
4623 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4624 return trail_src_to_curr_pred;
4628 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4629 &trail_me_to_curr_pred_length);
4631 /* Check if trail contains the source_peer. */
4632 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4634 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4635 &trail_me_to_curr_pred[i]))
4638 /* Source is NOT part of trail. */
4641 /* Source is the last element in the trail to reach to my pred.
4642 Source is direct friend of the pred. */
4643 if (trail_me_to_curr_pred_length == i)
4645 *trail_src_to_curr_pred_length = 0;
4649 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4650 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4651 *trail_src_to_curr_pred_length);
4653 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4655 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4657 GNUNET_free_non_null(trail_me_to_curr_pred);
4658 return trail_src_to_curr_pred;
4662 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4663 trail_src_to_me_len,
4664 trail_me_to_curr_pred,
4665 trail_me_to_curr_pred_length,
4667 *trail_src_to_curr_pred_length = len;
4668 GNUNET_free_non_null(trail_me_to_curr_pred);
4669 return trail_src_to_curr_pred;
4674 * Add finger as your predecessor. To add, first generate a new trail id, invert
4675 * the trail to get the trail from me to finger, add an entry in your routing
4676 * table, send add trail message to peers which are part of trail from me to
4677 * finger and add finger in finger table.
4680 * @param trail_length
4683 update_predecessor (struct GNUNET_PeerIdentity finger,
4684 struct GNUNET_PeerIdentity *trail,
4685 unsigned int trail_length)
4687 struct GNUNET_HashCode trail_to_new_predecessor_id;
4688 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4689 struct FriendInfo *target_friend;
4691 /* Generate trail id for trail from me to new predecessor = finger. */
4692 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4693 &trail_to_new_predecessor_id,
4694 sizeof (trail_to_new_predecessor_id));
4696 /* Finger is a friend. */
4697 if (trail_length == 0)
4699 trail_to_new_predecessor = NULL;
4700 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4701 GNUNET_assert (NULL != (target_friend =
4702 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4707 /* Invert the trail to get the trail from me to finger, NOT including the
4709 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4710 &trail[trail_length-1]));
4712 trail_to_new_predecessor = invert_trail (trail, trail_length);
4714 /* Add an entry in your routing table. */
4715 GDS_ROUTING_add (trail_to_new_predecessor_id,
4717 trail_to_new_predecessor[0]);
4719 GNUNET_assert (NULL != (target_friend =
4720 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4721 &trail_to_new_predecessor[0])));
4722 GNUNET_assert (NULL != (
4723 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4724 &trail[trail_length - 1])));
4727 /* Add entry in routing table of all peers that are part of trail from me
4728 to finger, including finger. */
4729 GDS_NEIGHBOURS_send_add_trail (my_identity,
4731 trail_to_new_predecessor_id,
4732 trail_to_new_predecessor,
4736 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4737 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4738 GNUNET_free_non_null(trail_to_new_predecessor);
4743 * Check if you already have a predecessor. If not then add finger as your
4744 * predecessor. If you have predecessor, then compare two peer identites.
4745 * If finger is correct predecessor, then remove the old entry, add finger in
4746 * finger table and send add_trail message to add the trail in the routing
4747 * table of all peers which are part of trail to reach from me to finger.
4748 * @param finger New peer which may be our predecessor.
4749 * @param trail List of peers to reach from @finger to me.
4750 * @param trail_length Total number of peer in @a trail.
4753 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4754 struct GNUNET_PeerIdentity *trail,
4755 unsigned int trail_length)
4757 struct FingerInfo *current_predecessor;
4758 const struct GNUNET_PeerIdentity *closest_peer;
4759 uint64_t predecessor_value;
4760 unsigned int is_predecessor = 1;
4762 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4764 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4766 /* No predecessor. Add finger as your predecessor. */
4767 if (GNUNET_NO == current_predecessor->is_present)
4769 update_predecessor (finger, trail, trail_length);
4773 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4779 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4780 closest_peer = select_closest_peer (&finger,
4781 ¤t_predecessor->finger_identity,
4782 predecessor_value, is_predecessor);
4784 /* Finger is the closest predecessor. Remove the existing one and add the new
4786 if (closest_peer == &finger)
4788 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4789 update_predecessor (finger, trail, trail_length);
4797 * Core handle for p2p verify successor messages.
4798 * @param cls closure
4799 * @param message message
4800 * @param peer peer identity this notification is about
4801 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4804 handle_dht_p2p_verify_successor(void *cls,
4805 const struct GNUNET_PeerIdentity *peer,
4806 const struct GNUNET_MessageHeader *message)
4808 const struct PeerVerifySuccessorMessage *vsm;
4809 struct GNUNET_HashCode trail_id;
4810 struct GNUNET_PeerIdentity successor;
4811 struct GNUNET_PeerIdentity source_peer;
4812 struct GNUNET_PeerIdentity *trail;
4813 struct GNUNET_PeerIdentity *next_hop;
4814 struct FingerInfo current_predecessor;
4815 struct FriendInfo *target_friend;
4816 unsigned int trail_src_to_curr_pred_len = 0;
4817 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4818 unsigned int trail_length;
4821 msize = ntohs (message->size);
4823 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4825 GNUNET_break_op (0);
4829 vsm = (const struct PeerVerifySuccessorMessage *) message;
4830 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4831 sizeof (struct GNUNET_PeerIdentity);
4832 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4833 sizeof (struct GNUNET_PeerIdentity) != 0)
4835 GNUNET_break_op (0);
4839 GNUNET_STATISTICS_update (GDS_stats,
4841 ("# Bytes received from other peers"), msize,
4844 trail_id = vsm->trail_id;
4845 source_peer = vsm->source_peer;
4846 successor = vsm->successor;
4847 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4850 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4852 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4854 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4855 if (NULL == next_hop)
4857 // GNUNET_break_op (0);
4858 // return GNUNET_SYSERR;
4859 //FIXME: Here it may happen that trail has not yet been added
4860 //in notify successor.
4864 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4866 if(NULL == target_friend)
4871 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4872 trail_id, trail, trail_length,
4877 /* I am the destination of this message. */
4879 /* Check if the source_peer could be our predecessor and if yes then update
4881 compare_and_update_predecessor (source_peer, trail, trail_length);
4882 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4884 /* Is source of this message NOT my predecessor. */
4885 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4888 trail_src_to_curr_pred =
4889 get_trail_src_to_curr_pred (source_peer,
4892 &trail_src_to_curr_pred_len);
4896 trail_src_to_curr_pred_len = trail_length;
4899 trail_src_to_curr_pred =
4900 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4901 *trail_src_to_curr_pred_len);
4902 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4904 trail_src_to_curr_pred[i] = trail[i];
4908 GNUNET_assert (NULL !=
4910 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4911 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4912 current_predecessor.finger_identity,
4913 trail_id, trail_src_to_curr_pred,
4914 trail_src_to_curr_pred_len,
4915 GDS_ROUTING_DEST_TO_SRC,
4917 GNUNET_free_non_null(trail_src_to_curr_pred);
4923 * If the trail from me to my probable successor contains a friend not
4924 * at index 0, then we can shorten the trail.
4925 * @param probable_successor Peer which is our probable successor
4926 * @param trail_me_to_probable_successor Peers in path from me to my probable
4927 * successor, NOT including the endpoints.
4928 * @param trail_me_to_probable_successor_len Total number of peers in
4929 * @a trail_me_to_probable_succesor.
4930 * @return Updated trail, if any friend found.
4931 * Else the trail_me_to_probable_successor.
4933 struct GNUNET_PeerIdentity *
4934 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4935 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4936 unsigned int trail_me_to_probable_successor_len,
4937 unsigned int *trail_to_new_successor_length)
4941 struct GNUNET_PeerIdentity *trail_to_new_successor;
4943 /* Probable successor is a friend */
4944 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4945 &probable_successor))
4947 trail_to_new_successor = NULL;
4948 *trail_to_new_successor_length = 0;
4949 return trail_to_new_successor;
4952 /* Is there any friend of yours in this trail. */
4953 if(trail_me_to_probable_successor_len > 1)
4955 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4957 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4958 &trail_me_to_probable_successor[i]))
4961 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4962 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4963 *trail_to_new_successor_length);
4966 for(j = 0;j < *trail_to_new_successor_length;i++,j++)
4968 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4971 return trail_to_new_successor;
4975 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4976 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4981 * Check if the peer which sent us verify successor result message is still ours
4982 * successor or not. If not, then compare existing successor and probable successor.
4983 * In case probable successor is the correct successor, remove the existing
4984 * successor. Add probable successor as new successor. Send notify new successor
4985 * message to new successor.
4986 * @param curr_succ Peer to which we sent the verify successor message. It may
4987 * or may not be our real current successor, as we may have few iterations of
4988 * find finger trail task.
4989 * @param probable_successor Peer which should be our successor accroding to @a
4991 * @param trail List of peers to reach from me to @a probable successor, NOT including
4993 * @param trail_length Total number of peers in @a trail.
4996 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4997 struct GNUNET_PeerIdentity probable_successor,
4998 const struct GNUNET_PeerIdentity *trail,
4999 unsigned int trail_length)
5001 struct FingerInfo *current_successor;
5002 const struct GNUNET_PeerIdentity *closest_peer;
5003 struct GNUNET_HashCode trail_id;
5004 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
5005 struct FriendInfo *target_friend;
5006 unsigned int trail_me_to_probable_succ_len;
5007 unsigned int is_predecessor = GNUNET_NO;
5008 uint64_t successor_value;
5010 current_successor = &finger_table[0];
5011 successor_value = compute_finger_identity_value(0);
5013 /* If probable successor is same as current_successor, do nothing. */
5014 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
5015 ¤t_successor->finger_identity))
5018 closest_peer = select_closest_peer (&probable_successor,
5019 ¤t_successor->finger_identity,
5020 successor_value, is_predecessor);
5022 /* If the current_successor in the finger table is closest, then do nothing. */
5023 if (closest_peer == ¤t_successor->finger_identity)
5025 /* Code for testing ONLY: Store the successor for path tracking */
5026 // track_topology = 1;
5027 if ((NULL != GDS_stats))
5033 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5034 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5035 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5036 GNUNET_free (my_id_str);
5037 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5043 /* Probable successor is the closest peer.*/
5044 if(trail_length > 0)
5046 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5051 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5052 &probable_successor));
5055 trail_me_to_probable_succ_len = 0;
5056 trail_me_to_probable_succ =
5057 check_trail_me_to_probable_succ (probable_successor,
5058 trail, trail_length,
5059 &trail_me_to_probable_succ_len);
5061 /* Remove the existing successor. */
5062 remove_existing_finger (current_successor, 0);
5064 /* TODO URGENT: Check if any peer is present more than once, if yes then shorten
5065 the trail. before sending it across the network. */
5066 /* Generate a new trail id to reach to your new successor. */
5067 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5068 &trail_id, sizeof (trail_id));
5070 if (trail_me_to_probable_succ_len > 0)
5072 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
5073 GNUNET_assert (NULL !=
5075 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5076 &trail_me_to_probable_succ[0])));
5080 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5081 GNUNET_assert (NULL !=
5083 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5084 &probable_successor)));
5087 add_new_finger (probable_successor, trail_me_to_probable_succ,
5088 trail_me_to_probable_succ_len, trail_id, 0);
5090 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
5091 trail_me_to_probable_succ,
5092 trail_me_to_probable_succ_len,
5100 * FIXME: Check for duplicate elements everywhere when you are making
5102 * Core handle for p2p verify successor result messages.
5103 * @param cls closure
5104 * @param message message
5105 * @param peer peer identity this notification is about
5106 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5109 handle_dht_p2p_verify_successor_result(void *cls,
5110 const struct GNUNET_PeerIdentity *peer,
5111 const struct GNUNET_MessageHeader *message)
5113 const struct PeerVerifySuccessorResultMessage *vsrm;
5114 enum GDS_ROUTING_trail_direction trail_direction;
5115 struct GNUNET_PeerIdentity querying_peer;
5116 struct GNUNET_HashCode trail_id;
5117 struct GNUNET_PeerIdentity *next_hop;
5118 struct FriendInfo *target_friend;
5119 struct GNUNET_PeerIdentity probable_successor;
5120 struct GNUNET_PeerIdentity current_successor;
5121 const struct GNUNET_PeerIdentity *trail;
5122 unsigned int trail_length;
5125 msize = ntohs (message->size);
5126 /* We send a trail to reach from old successor to new successor, if
5127 * old_successor != new_successor.*/
5128 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5130 GNUNET_break_op (0);
5134 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5135 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5136 sizeof (struct GNUNET_PeerIdentity);
5138 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5139 sizeof (struct GNUNET_PeerIdentity) != 0)
5141 GNUNET_break_op (0);
5145 GNUNET_STATISTICS_update (GDS_stats,
5147 ("# Bytes received from other peers"), msize,
5150 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5151 querying_peer = vsrm->querying_peer;
5152 trail_direction = ntohl (vsrm->trail_direction);
5153 trail_id = vsrm->trail_id;
5154 probable_successor = vsrm->probable_successor;
5155 current_successor = vsrm->current_successor;
5158 /* I am the querying_peer. */
5159 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5161 compare_and_update_successor (current_successor,
5162 probable_successor, trail, trail_length);
5166 /*If you are not the querying peer then pass on the message */
5167 if(NULL == (next_hop =
5168 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
5173 if (NULL == (target_friend =
5174 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5179 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5180 vsrm->current_successor,
5181 probable_successor, trail_id,
5184 trail_direction, target_friend);
5190 * Core handle for p2p notify new successor messages.
5191 * @param cls closure
5192 * @param message message
5193 * @param peer peer identity this notification is about
5194 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5197 handle_dht_p2p_notify_new_successor(void *cls,
5198 const struct GNUNET_PeerIdentity *peer,
5199 const struct GNUNET_MessageHeader *message)
5201 const struct PeerNotifyNewSuccessorMessage *nsm;
5202 struct GNUNET_PeerIdentity *trail;
5203 struct GNUNET_PeerIdentity source;
5204 struct GNUNET_PeerIdentity new_successor;
5205 struct GNUNET_HashCode trail_id;
5206 struct GNUNET_PeerIdentity next_hop;
5207 struct FriendInfo *target_friend;
5210 uint32_t trail_length;
5212 msize = ntohs (message->size);
5214 /* We have the trail to reach from source to new successor. */
5215 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5217 GNUNET_break_op (0);
5221 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5222 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5223 sizeof (struct GNUNET_PeerIdentity);
5224 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5225 sizeof (struct GNUNET_PeerIdentity) != 0)
5227 GNUNET_break_op (0);
5231 GNUNET_STATISTICS_update (GDS_stats,
5233 ("# Bytes received from other peers"), msize,
5236 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5237 source = nsm->source_peer;
5238 new_successor = nsm->new_successor;
5239 trail_id = nsm->trail_id;
5242 //FIXME: add a check to make sure peer is correct.
5244 /* I am the new_successor to source_peer. */
5245 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5247 if(trail_length > 0)
5248 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5251 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5253 compare_and_update_predecessor (source, trail, trail_length);
5257 GNUNET_assert(trail_length > 0);
5258 /* I am part of trail to reach to successor. */
5259 my_index = search_my_index (trail, trail_length);
5262 DEBUG ("No entry found in trail\n");
5263 GNUNET_break_op (0);
5264 return GNUNET_SYSERR;
5266 if((trail_length + 1) == my_index)
5268 DEBUG ("Found twice in trail.\n");
5269 GNUNET_break_op (0);
5270 return GNUNET_SYSERR;
5272 if ((trail_length-1) == my_index)
5273 next_hop = new_successor;
5275 next_hop = trail[my_index + 1];
5278 /* Add an entry in routing table for trail from source to its new successor. */
5279 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5280 GNUNET_assert (NULL !=
5282 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5283 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5285 trail_id, target_friend);
5292 * Core handler for P2P trail rejection message
5293 * @param cls closure
5294 * @param message message
5295 * @param peer peer identity this notification is about
5296 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5299 handle_dht_p2p_trail_setup_rejection (void *cls,
5300 const struct GNUNET_PeerIdentity *peer,
5301 const struct GNUNET_MessageHeader *message)
5303 const struct PeerTrailRejectionMessage *trail_rejection;
5304 unsigned int trail_length;
5305 const struct GNUNET_PeerIdentity *trail_peer_list;
5306 struct FriendInfo *target_friend;
5307 struct GNUNET_TIME_Relative congestion_timeout;
5308 struct GNUNET_HashCode trail_id;
5309 struct GNUNET_PeerIdentity next_peer;
5310 struct GNUNET_PeerIdentity source;
5311 struct GNUNET_PeerIdentity *next_hop;
5312 uint64_t ultimate_destination_finger_value;
5313 unsigned int is_predecessor;
5316 msize = ntohs (message->size);
5317 /* We are passing the trail setup so far. */
5318 if (msize < sizeof (struct PeerTrailRejectionMessage))
5320 GNUNET_break_op (0);
5324 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5325 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5326 sizeof (struct GNUNET_PeerIdentity);
5327 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5328 sizeof (struct GNUNET_PeerIdentity) != 0)
5330 GNUNET_break_op (0);
5334 GNUNET_STATISTICS_update (GDS_stats,
5336 ("# Bytes received from other peers"), msize,
5339 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5340 is_predecessor = ntohl (trail_rejection->is_predecessor);
5341 congestion_timeout = trail_rejection->congestion_time;
5342 source = trail_rejection->source_peer;
5343 trail_id = trail_rejection->trail_id;
5344 ultimate_destination_finger_value =
5345 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5347 /* First set the congestion time of the friend that sent you this message. */
5348 GNUNET_assert (NULL !=
5350 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5351 target_friend->congestion_timestamp =
5352 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5353 congestion_timeout);
5355 /* I am the source peer which wants to setup the trail. Do nothing.
5356 * send_find_finger_trail_task is scheduled periodically.*/
5357 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5360 /* If I am congested then pass this message to peer before me in trail. */
5361 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5363 struct GNUNET_PeerIdentity *new_trail;
5364 unsigned int new_trail_length;
5366 /* Remove yourself from the trail setup so far. */
5367 if (trail_length == 1)
5370 new_trail_length = 0;
5375 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5376 sizeof (struct GNUNET_PeerIdentity));
5378 /* Remove myself from the trail. */
5379 new_trail_length = trail_length -1;
5380 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5381 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5384 GNUNET_assert (NULL !=
5386 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5387 GDS_NEIGHBOURS_send_trail_rejection (source,
5388 ultimate_destination_finger_value,
5389 my_identity, is_predecessor,
5390 new_trail,new_trail_length,trail_id,
5391 target_friend, CONGESTION_TIMEOUT);
5392 GNUNET_free (new_trail);
5396 struct Closest_Peer successor;
5397 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5399 /* Am I the final destination? */
5400 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5403 if (0 == trail_length)
5406 next_peer = trail_peer_list[trail_length-1];
5408 GNUNET_assert (NULL !=
5410 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5412 GDS_NEIGHBOURS_send_trail_setup_result (source,
5414 target_friend, trail_length,
5417 ultimate_destination_finger_value,
5422 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5424 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5425 peer_list[trail_length] = my_identity;
5427 GNUNET_assert (NULL !=
5429 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5431 GDS_NEIGHBOURS_send_trail_setup (source,
5432 ultimate_destination_finger_value,
5433 successor.best_known_destination,
5434 target_friend, trail_length + 1, peer_list,
5435 is_predecessor, trail_id,
5436 successor.trail_id);
5443 * Core handle for p2p trail tear compression messages.
5444 * @param cls closure
5445 * @param message message
5446 * @param peer peer identity this notification is about
5447 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5450 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5451 const struct GNUNET_MessageHeader *message)
5453 const struct PeerTrailCompressionMessage *trail_compression;
5454 struct GNUNET_PeerIdentity *next_hop;
5455 struct FriendInfo *target_friend;
5456 struct GNUNET_HashCode trail_id;
5459 msize = ntohs (message->size);
5461 if (msize != sizeof (struct PeerTrailCompressionMessage))
5463 GNUNET_break_op (0);
5467 GNUNET_STATISTICS_update (GDS_stats,
5469 ("# Bytes received from other peers"), msize,
5472 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5473 trail_id = trail_compression->trail_id;
5475 /* Am I the new first friend to reach to finger of this trail. */
5476 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5480 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5481 &trail_compression->source_peer)))
5487 /* Update your prev hop to source of this message. */
5489 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5490 trail_compression->source_peer)))
5498 /* Pass the message to next hop to finally reach to new_first_friend. */
5499 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5501 if (NULL == next_hop)
5507 if( NULL == (target_friend =
5508 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5514 GDS_ROUTING_remove_trail (trail_id);
5516 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5518 trail_compression->new_first_friend,
5525 * Core handler for trail teardown message.
5526 * @param cls closure
5527 * @param message message
5528 * @param peer sender of this messsage.
5529 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5532 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5533 const struct GNUNET_MessageHeader *message)
5535 const struct PeerTrailTearDownMessage *trail_teardown;
5536 enum GDS_ROUTING_trail_direction trail_direction;
5537 struct GNUNET_HashCode trail_id;
5538 struct GNUNET_PeerIdentity *next_hop;
5541 msize = ntohs (message->size);
5543 /* Here we pass only the trail id. */
5544 if (msize != sizeof (struct PeerTrailTearDownMessage))
5546 GNUNET_break_op (0);
5550 GNUNET_STATISTICS_update (GDS_stats,
5552 ("# Bytes received from other peers"), msize,
5555 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5556 trail_direction = ntohl (trail_teardown->trail_direction);
5557 trail_id = trail_teardown->trail_id;
5559 /* Check if peer is the real peer from which we should get this message.*/
5560 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5562 GNUNET_assert (NULL != (prev_hop =
5563 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5564 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5567 return GNUNET_SYSERR;
5571 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5573 if (NULL == next_hop)
5576 return GNUNET_SYSERR;
5579 /* I am the next hop, which means I am the final destination. */
5580 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5582 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5587 /* If not final destination, then send a trail teardown message to next hop.*/
5588 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5589 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5590 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5598 * Core handle for p2p add trail message.
5599 * @param cls closure
5600 * @param message message
5601 * @param peer peer identity this notification is about
5602 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5605 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5606 const struct GNUNET_MessageHeader *message)
5608 const struct PeerAddTrailMessage *add_trail;
5609 const struct GNUNET_PeerIdentity *trail;
5610 struct GNUNET_HashCode trail_id;
5611 struct GNUNET_PeerIdentity destination_peer;
5612 struct GNUNET_PeerIdentity source_peer;
5613 struct GNUNET_PeerIdentity next_hop;
5614 unsigned int trail_length;
5615 unsigned int my_index;
5618 msize = ntohs (message->size);
5619 /* In this message we pass the whole trail from source to destination as we
5620 * are adding that trail.*/
5621 //FIXME: failed when run with 1000 pears. check why.
5622 if (msize < sizeof (struct PeerAddTrailMessage))
5624 GNUNET_break_op (0);
5628 add_trail = (const struct PeerAddTrailMessage *) message;
5629 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5630 sizeof (struct GNUNET_PeerIdentity);
5631 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5632 sizeof (struct GNUNET_PeerIdentity) != 0)
5634 GNUNET_break_op (0);
5638 GNUNET_STATISTICS_update (GDS_stats,
5640 ("# Bytes received from other peers"), msize,
5643 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5644 destination_peer = add_trail->destination_peer;
5645 source_peer = add_trail->source_peer;
5646 trail_id = add_trail->trail_id;
5648 //FIXME: add a check that sender peer is not malicious. Make it a generic
5649 // function so that it can be used in all other functions where we need the
5650 // same functionality.
5652 /* I am not the destination of the trail. */
5653 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5655 struct FriendInfo *target_friend;
5657 /* Get my location in the trail. */
5658 my_index = search_my_index (trail, trail_length);
5661 GNUNET_break_op (0);
5662 return GNUNET_SYSERR;
5664 if((trail_length + 1) == my_index)
5666 DEBUG ("Found twice in trail.\n");
5667 GNUNET_break_op (0);
5668 return GNUNET_SYSERR;
5670 if ((trail_length - 1) == my_index)
5672 next_hop = destination_peer;
5676 next_hop = trail[my_index + 1];
5679 /* Add in your routing table. */
5680 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5681 GNUNET_assert (NULL !=
5683 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5684 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5685 trail, trail_length, target_friend);
5688 /* I am the destination. Add an entry in routing table. */
5689 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5695 * Free the finger trail in which the first friend to reach to a finger is
5696 * disconnected_friend. Also remove entry from routing table for that particular
5698 * @param disconnected_friend PeerIdentity of friend which got disconnected
5699 * @param remove_finger Finger whose trail we need to check if it has
5700 * disconnected_friend as the first hop.
5701 * @return Total number of trails in which disconnected_friend was the first
5705 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5706 struct FingerInfo *remove_finger)
5708 unsigned int matching_trails_count;
5711 /* Number of trails with disconnected_friend as the first hop in the trail
5712 * to reach from me to remove_finger, NOT including endpoints. */
5713 matching_trails_count = 0;
5715 /* Iterate over all the trails of finger. */
5716 for (i = 0; i < remove_finger->trails_count; i++)
5718 struct Trail *trail;
5719 trail = &remove_finger->trail_list[i];
5721 /* This assertion is ensure that there are no gaps in the trail list.
5722 REMOVE IT AFTERWARDS. */
5723 GNUNET_assert (GNUNET_YES == trail->is_present);
5725 /* First friend to reach to finger is disconnected_peer. */
5726 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5727 disconnected_friend))
5729 struct GNUNET_PeerIdentity *next_hop;
5730 struct FriendInfo *remove_friend;
5732 GNUNET_assert (NULL !=
5734 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5735 disconnected_friend)));
5736 /* FIXME: removing no but check it. */
5737 //remove_friend->trails_count--;
5738 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5739 GDS_ROUTING_SRC_TO_DEST);
5741 /* Here it may happen that as all the peers got disconnected, the entry in
5742 routing table for that particular trail has been removed, because the
5743 previously disconnected peer was either a next hop or prev hop of that
5745 if (NULL == next_hop)
5748 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5750 matching_trails_count++;
5751 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5754 trail->is_present = GNUNET_NO;
5757 return matching_trails_count;
5762 * Iterate over finger_table entries.
5763 * 0. Ignore finger which is my_identity or if no valid entry present at
5764 * that finger index.
5765 * 1. If disconnected_friend is a finger, then remove the routing entry from
5766 your own table. Free the trail.
5767 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5768 * 2.1 Remove all the trails and entry from routing table in which disconnected
5769 * friend is the first friend in the trail. If disconnected_friend is the
5770 * first friend in all the trails to reach finger, then remove the finger.
5771 * @param disconnected_friend Peer identity of friend which got disconnected.
5774 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5776 struct FingerInfo *remove_finger;
5777 struct FriendInfo *remove_friend;
5778 int removed_trails_count;
5781 /* Iterate over finger table entries. */
5782 for (i = 0; i < MAX_FINGERS; i++)
5784 remove_finger = &finger_table[i];
5786 /* No finger stored at this trail index. */
5787 if (GNUNET_NO == remove_finger->is_present)
5790 /* I am my own finger, then ignore this finger. */
5791 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5795 /* Is disconnected_peer a finger? */
5796 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5797 &remove_finger->finger_identity))
5799 struct GNUNET_PeerIdentity *next_hop;
5800 struct GNUNET_HashCode trail_id;
5801 /* FIXME: Just for check, remove it afterwards. Here finger is a friend.
5802 hence trail length should be 0.*/
5803 GNUNET_assert (0 == remove_finger->trail_list[0].trail_length);
5804 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5805 trail_id = remove_finger->trail_list[0].trail_id;
5809 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5812 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5813 &remove_finger->finger_identity)));
5814 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5815 GNUNET_assert (NULL !=
5817 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5818 disconnected_peer)));
5821 remove_finger->trail_list[0].is_present = GNUNET_NO;
5822 //GNUNET_assert (0 != remove_friend->trails_count);
5823 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5824 remove_finger->is_present = GNUNET_NO;
5825 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5829 /* If finger is a friend but not disconnected_friend, then continue. */
5830 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5831 &remove_finger->finger_identity))
5834 /* Iterate over the list of trails to reach remove_finger. Check if
5835 * disconnected_friend is the first friend in any of the trail. */
5836 removed_trails_count = remove_matching_trails (disconnected_peer,
5838 remove_finger->trails_count =
5839 remove_finger->trails_count - removed_trails_count;
5840 /* All the finger trails had disconnected_friend as the first friend,
5841 * so free the finger. */
5842 if (remove_finger->trails_count == 0)
5844 remove_finger->is_present = GNUNET_NO;
5845 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5852 * Method called whenever a peer disconnects.
5854 * @param cls closure
5855 * @param peer peer identity this notification is about
5858 handle_core_disconnect (void *cls,
5859 const struct GNUNET_PeerIdentity *peer)
5861 struct FriendInfo *remove_friend;
5862 struct P2PPendingMessage *pos;
5863 unsigned int discarded;
5865 /* If disconnected to own identity, then return. */
5866 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5869 if(NULL == (remove_friend =
5870 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
5872 DEBUG("\n friend already disconnected.");
5875 /* Remove fingers with peer as first friend or if peer is a finger. */
5876 remove_matching_fingers (peer);
5878 /* Remove any trail from routing table of which peer is a part of. This function
5879 * internally sends a trail teardown message in the direction of which
5880 * disconnected peer is not part of. */
5881 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5883 /* Remove peer from friend_peermap. */
5884 GNUNET_assert (GNUNET_YES ==
5885 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5889 /* Remove all the messages queued in pending list of this peer is discarded.*/
5890 if (remove_friend->th != NULL)
5892 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
5893 remove_friend->th = NULL;
5897 while (NULL != (pos = remove_friend->head))
5899 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
5904 GNUNET_STATISTICS_update (GDS_stats,
5906 ("# Queued messages discarded (peer disconnected)"),
5907 discarded, GNUNET_NO);
5908 GNUNET_free (remove_friend);
5910 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5913 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5915 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5916 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5924 * Method called whenever a peer connects.
5926 * @param cls closure
5927 * @param peer_identity peer identity this notification is about
5930 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5932 struct FriendInfo *friend;
5934 /* Check for connect to self message */
5935 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5938 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5940 /* If peer already exists in our friend_peermap, then exit. */
5941 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5948 friend = GNUNET_new (struct FriendInfo);
5949 friend->id = *peer_identity;
5951 GNUNET_assert (GNUNET_OK ==
5952 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5953 peer_identity, friend,
5954 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5956 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5957 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5959 next_send_time.rel_value_us =
5960 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5961 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5962 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5963 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5969 * To be called on core init/fail.
5971 * @param cls service closure
5972 * @param identity the public identity of this peer
5975 core_init (void *cls,
5976 const struct GNUNET_PeerIdentity *identity)
5978 my_identity = *identity;
5981 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5982 my_id64 = GNUNET_ntohll (my_id64);
5983 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5984 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5990 * Initialize finger table entries.
5993 finger_table_init ()
5995 memset (&finger_table, 0, sizeof (finger_table));
6000 * Initialize neighbours subsystem.
6001 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
6004 GDS_NEIGHBOURS_init (void)
6006 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
6007 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
6008 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
6009 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
6010 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
6011 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
6012 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
6013 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
6014 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
6015 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
6016 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
6017 sizeof (struct PeerTrailCompressionMessage)},
6018 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
6019 sizeof (struct PeerTrailTearDownMessage)},
6020 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
6024 #if ENABLE_MALICIOUS
6029 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
6030 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
6031 GNUNET_NO, core_handlers);
6033 if (NULL == core_api)
6034 return GNUNET_SYSERR;
6036 //TODO: check size of this peer map?
6037 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
6038 finger_table_init ();
6044 * Free the memory held up by trails of a finger.
6047 delete_finger_table_entries()
6052 for(i = 0; i < MAX_FINGERS; i++)
6054 if(GNUNET_NO == finger_table[i].is_present)
6057 for(j = 0; j < finger_table[i].trails_count; j++)
6059 free_trail(&finger_table[i].trail_list[i]);
6065 * Shutdown neighbours subsystem.
6068 GDS_NEIGHBOURS_done (void)
6070 if (NULL == core_api)
6073 GNUNET_CORE_disconnect (core_api);
6076 delete_finger_table_entries();
6078 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6079 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6080 friend_peermap = NULL;
6082 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
6085 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6086 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
6089 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
6091 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6092 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
6100 * @return my identity
6102 struct GNUNET_PeerIdentity
6103 GDS_NEIGHBOURS_get_my_id (void)
6108 /* end of gnunet-service-xdht_neighbours.c */