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 * Head of pending messages to be sent to this friend.
687 struct P2PPendingMessage *head;
690 * Tail of pending messages to be sent to this friend.
692 struct P2PPendingMessage *tail;
695 * Core handle for sending messages to this friend.
697 struct GNUNET_CORE_TransmitHandle *th;
702 * An individual element of the trail to reach to a finger.
707 * Pointer to next item in the list
709 struct Trail_Element *next;
712 * Pointer to prev item in the list
714 struct Trail_Element *prev;
717 * An element in this trail.
719 struct GNUNET_PeerIdentity peer;
723 * Information about an individual trail.
730 struct Trail_Element *trail_head;
735 struct Trail_Element *trail_tail;
738 * Unique identifier of this trail.
740 struct GNUNET_HashCode trail_id;
743 * Length of trail pointed
745 unsigned int trail_length;
748 * Is there a valid trail entry.
750 unsigned int is_present;
754 * An entry in finger_table
761 struct GNUNET_PeerIdentity finger_identity;
764 * Is any finger stored at this finger index.
766 unsigned int is_present;
769 * Index in finger peer map
771 uint32_t finger_table_index;
774 * Number of trails setup so far for this finger.
775 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
777 uint32_t trails_count;
780 * Array of trails to reach to this finger.
782 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
787 * Stores information about the peer which is closest to destination_finger_value.
788 * 'closest' can be either successor or predecessor depending on is_predecessor
794 * Destination finger value.
796 uint64_t destination_finger_value;
799 * Is finger_value a predecessor or any other finger.
801 unsigned int is_predecessor;
804 * Trail id to reach to peer.
805 * In case peer is my identity or friend, it is set to 0.
807 struct GNUNET_HashCode trail_id;
810 * Next destination. In case of friend and my_identity , it is same as next_hop
811 * In case of finger it is finger identity.
813 struct GNUNET_PeerIdentity best_known_destination;
816 * In case best_known_destination is a finger, then first friend in the trail
817 * to reach to it. In other case, same as best_known_destination.
819 struct GNUNET_PeerIdentity next_hop;
824 * Data structure to store the trail chosen to reach to finger.
826 struct Selected_Finger_Trail
829 * First friend in the trail to reach finger.
831 struct FriendInfo friend;
834 * Identifier of this trail.
836 struct GNUNET_HashCode trail_id;
839 * Total number of peers in this trail.
841 unsigned int trail_length;
845 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
846 * get our first friend.
848 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
851 * Task that sends verify successor message. This task is started when we get
852 * our successor for the first time.
854 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_task;
857 * Identity of this peer.
859 static struct GNUNET_PeerIdentity my_identity;
862 * Peer map of all the friends of a peer
864 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
867 * Array of all the fingers.
869 static struct FingerInfo finger_table [MAX_FINGERS];
874 static struct GNUNET_CORE_Handle *core_api;
877 * Handle for the statistics service.
879 //extern struct GNUNET_STATISTICS_Handle *GDS_stats;
882 * The current finger index that we have want to find trail to. We start the
883 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
884 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
885 * we reset this index to 0.
887 static unsigned int current_search_finger_index;
890 * Should we store our topology predecessor and successor IDs into statistics?
892 unsigned int track_topology;
895 * Should I be a malicious peer and drop the PUT/GET packets?
896 * if 0 then NOT malicious.
898 unsigned int act_malicious;
901 * Called when core is ready to send a message we asked for
902 * out to the destination.
904 * @param cls the 'struct FriendInfo' of the target friend
905 * @param size number of bytes available in buf
906 * @param buf where the callee should write the message
907 * @return number of bytes written to buf
910 core_transmit_notify (void *cls, size_t size, void *buf)
912 struct FriendInfo *peer = cls;
914 struct P2PPendingMessage *pending;
919 while ((NULL != (pending = peer->head)) &&
920 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
922 peer->pending_count--;
923 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
924 GNUNET_free (pending);
928 /* no messages pending */
934 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
935 GNUNET_CORE_PRIO_BEST_EFFORT,
936 GNUNET_TIME_absolute_get_remaining
937 (pending->timeout), &peer->id,
938 ntohs (pending->msg->size),
939 &core_transmit_notify, peer);
940 GNUNET_break (NULL != peer->th);
944 while ((NULL != (pending = peer->head)) &&
945 (size - off >= (msize = ntohs (pending->msg->size))))
947 GNUNET_STATISTICS_update (GDS_stats,
949 ("# Bytes transmitted to other peers"), msize,
951 memcpy (&cbuf[off], pending->msg, msize);
953 peer->pending_count--;
954 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
955 GNUNET_free (pending);
957 if (peer->head != NULL)
960 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
961 GNUNET_CORE_PRIO_BEST_EFFORT,
962 GNUNET_TIME_absolute_get_remaining
963 (pending->timeout), &peer->id, msize,
964 &core_transmit_notify, peer);
965 GNUNET_break (NULL != peer->th);
972 * Transmit all messages in the friend's message queue.
974 * @param peer message queue to process
977 process_friend_queue (struct FriendInfo *peer)
979 struct P2PPendingMessage *pending;
981 if (NULL == (pending = peer->head))
985 if (NULL != peer->th)
991 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
993 GNUNET_TIME_absolute_get_remaining
994 (pending->timeout), &peer->id,
995 ntohs (pending->msg->size),
996 &core_transmit_notify, peer);
997 GNUNET_break (NULL != peer->th);
1001 #if ENABLE_MALICIOUS
1003 * Set the ENABLE_MALICIOUS value to malicious.
1007 GDS_NEIGHBOURS_act_malicious (unsigned int malicious)
1009 act_malicious = malicious;
1014 * Construct a trail setup message and forward it to target_friend
1015 * @param source_peer Peer which wants to setup the trail
1016 * @param ultimate_destination_finger_value Peer identity closest to this value
1017 * will be finger to @a source_peer
1018 * @param best_known_destination Best known destination (could be finger or friend)
1019 * which should get this message. In case it is
1020 * friend, then it is same as target_friend
1021 * @param target_friend Friend to which message is forwarded now.
1022 * @param trail_length Total number of peers in trail setup so far.
1023 * @param trail_peer_list Trail setup so far
1024 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1025 * @param trail_id Unique identifier for the trail we are trying to setup.
1026 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1027 * best_known_destination when its a finger. If not
1028 * used then set to 0.
1031 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1032 uint64_t ultimate_destination_finger_value,
1033 struct GNUNET_PeerIdentity best_known_destination,
1034 struct FriendInfo *target_friend,
1035 unsigned int trail_length,
1036 const struct GNUNET_PeerIdentity *trail_peer_list,
1037 unsigned int is_predecessor,
1038 struct GNUNET_HashCode trail_id,
1039 struct GNUNET_HashCode intermediate_trail_id)
1041 struct P2PPendingMessage *pending;
1042 struct PeerTrailSetupMessage *tsm;
1043 struct GNUNET_PeerIdentity *peer_list;
1046 msize = sizeof (struct PeerTrailSetupMessage) +
1047 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1049 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1055 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1057 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1061 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1062 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1063 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1064 pending->msg = &tsm->header;
1065 tsm->header.size = htons (msize);
1066 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1067 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1068 tsm->source_peer = source_peer;
1069 tsm->best_known_destination = best_known_destination;
1070 tsm->is_predecessor = htonl (is_predecessor);
1071 tsm->trail_id = trail_id;
1072 tsm->intermediate_trail_id = intermediate_trail_id;
1074 if (trail_length > 0)
1076 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1077 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1080 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1081 target_friend->pending_count++;
1082 process_friend_queue (target_friend);
1087 * Construct a trail setup result message and forward it to target friend.
1088 * @param querying_peer Peer which sent the trail setup request and should get
1090 * @param Finger Peer to which the trail has been setup to.
1091 * @param target_friend Friend to which this message should be forwarded.
1092 * @param trail_length Numbers of peers in the trail.
1093 * @param trail_peer_list Peers which are part of the trail from
1094 * querying_peer to Finger, NOT including them.
1095 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1096 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1098 * @param trail_id Unique identifier of the trail.
1101 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1102 struct GNUNET_PeerIdentity finger,
1103 struct FriendInfo *target_friend,
1104 unsigned int trail_length,
1105 const struct GNUNET_PeerIdentity *trail_peer_list,
1106 unsigned int is_predecessor,
1107 uint64_t ultimate_destination_finger_value,
1108 struct GNUNET_HashCode trail_id)
1110 struct P2PPendingMessage *pending;
1111 struct PeerTrailSetupResultMessage *tsrm;
1112 struct GNUNET_PeerIdentity *peer_list;
1115 msize = sizeof (struct PeerTrailSetupResultMessage) +
1116 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1118 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1124 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1126 GNUNET_STATISTICS_update (GDS_stats,
1127 gettext_noop ("# P2P messages dropped due to full queue"),
1131 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1132 pending->importance = 0;
1133 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1134 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1135 pending->msg = &tsrm->header;
1136 tsrm->header.size = htons (msize);
1137 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1138 tsrm->querying_peer = querying_peer;
1139 tsrm->finger_identity = finger;
1140 tsrm->is_predecessor = htonl (is_predecessor);
1141 tsrm->trail_id = trail_id;
1142 tsrm->ulitmate_destination_finger_value =
1143 GNUNET_htonll (ultimate_destination_finger_value);
1144 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1146 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1148 /* Send the message to chosen friend. */
1149 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1150 target_friend->pending_count++;
1151 process_friend_queue (target_friend);
1156 * Send trail rejection message to target friend
1157 * @param source_peer Peer which is trying to setup the trail.
1158 * @param ultimate_destination_finger_value Peer closest to this value will be
1159 * @a source_peer's finger
1160 * @param congested_peer Peer which sent this message as it is congested.
1161 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1162 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1163 * by congested_peer. This does NOT include @a source_peer
1164 * and congested_peer.
1165 * @param trail_length Total number of peers in trail_peer_list, NOT including
1166 * @a source_peer and @a congested_peer
1167 * @param trail_id Unique identifier of this trail.
1168 * @param congestion_timeout Duration given by congested peer as an estimate of
1169 * how long it may remain congested.
1172 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1173 uint64_t ultimate_destination_finger_value,
1174 struct GNUNET_PeerIdentity congested_peer,
1175 unsigned int is_predecessor,
1176 const struct GNUNET_PeerIdentity *trail_peer_list,
1177 unsigned int trail_length,
1178 struct GNUNET_HashCode trail_id,
1179 struct FriendInfo *target_friend,
1180 const struct GNUNET_TIME_Relative congestion_timeout)
1182 struct PeerTrailRejectionMessage *trm;
1183 struct P2PPendingMessage *pending;
1184 struct GNUNET_PeerIdentity *peer_list;
1187 msize = sizeof (struct PeerTrailRejectionMessage) +
1188 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1190 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1196 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1198 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1202 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1203 pending->importance = 0;
1204 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1205 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1206 pending->msg = &trm->header;
1207 trm->header.size = htons (msize);
1208 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1209 trm->source_peer = source_peer;
1210 trm->congested_peer = congested_peer;
1211 trm->congestion_time = congestion_timeout;
1212 trm->is_predecessor = htonl (is_predecessor);
1213 trm->trail_id = trail_id;
1214 trm->ultimate_destination_finger_value =
1215 GNUNET_htonll (ultimate_destination_finger_value);
1217 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1218 if (trail_length > 0)
1220 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1223 /* Send the message to chosen friend. */
1224 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1225 target_friend->pending_count++;
1226 process_friend_queue (target_friend);
1231 * Construct a verify successor message and forward it to target_friend.
1232 * @param source_peer Peer which wants to verify its successor.
1233 * @param successor Peer which is @a source_peer's current successor.
1234 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1235 * NOT including them.
1236 * @param trail List of peers which are part of trail to reach from @a source_peer
1237 * to @a successor, NOT including them.
1238 * @param trail_length Total number of peers in @a trail.
1239 * @param target_friend Next friend to get this message.
1242 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1243 struct GNUNET_PeerIdentity successor,
1244 struct GNUNET_HashCode trail_id,
1245 struct GNUNET_PeerIdentity *trail,
1246 unsigned int trail_length,
1247 struct FriendInfo *target_friend)
1249 struct PeerVerifySuccessorMessage *vsm;
1250 struct P2PPendingMessage *pending;
1251 struct GNUNET_PeerIdentity *peer_list;
1254 msize = sizeof (struct PeerVerifySuccessorMessage) +
1255 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1256 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1262 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1264 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1268 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1269 pending->importance = 0; /* FIXME */
1270 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1271 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1272 pending->msg = &vsm->header;
1273 vsm->header.size = htons (msize);
1274 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1275 vsm->source_peer = source_peer;
1276 vsm->successor = successor;
1277 vsm->trail_id = trail_id;
1278 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1279 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1281 /* Send the message to chosen friend. */
1282 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1283 target_friend->pending_count++;
1284 process_friend_queue (target_friend);
1289 * FIXME: In every function we pass target friend except for this one.
1290 * so, either change everything or this one. also, should se just store
1291 * the pointer to friend in routing table rather than gnunet_peeridentity.
1292 * if yes then we should keep friend info in.h andmake lot of changes.
1293 * Construct a trail teardown message and forward it to target friend.
1294 * @param trail_id Unique identifier of the trail.
1295 * @param trail_direction Direction of trail.
1296 * @param target_friend Friend to get this message.
1299 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1300 unsigned int trail_direction,
1301 struct GNUNET_PeerIdentity peer)
1303 struct PeerTrailTearDownMessage *ttdm;
1304 struct P2PPendingMessage *pending;
1305 struct FriendInfo *target_friend;
1308 msize = sizeof (struct PeerTrailTearDownMessage);
1310 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1316 /*FIXME:In what case friend can be null. ?*/
1317 if (NULL == (target_friend =
1318 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1321 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1323 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1327 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1328 pending->importance = 0; /* FIXME */
1329 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1330 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1331 pending->msg = &ttdm->header;
1332 ttdm->header.size = htons (msize);
1333 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1334 ttdm->trail_id = trail_id;
1335 ttdm->trail_direction = htonl (trail_direction);
1337 /* Send the message to chosen friend. */
1338 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1339 target_friend->pending_count++;
1340 process_friend_queue (target_friend);
1345 * Construct a verify successor result message and send it to target_friend
1346 * @param querying_peer Peer which sent the verify successor message.
1347 * @param source_successor Current_successor of @a querying_peer.
1348 * @param current_predecessor Current predecessor of @a successor. Could be same
1349 * or different from @a querying_peer.
1350 * @param trail_id Unique identifier of the trail from @a querying_peer to
1351 * @a successor, NOT including them.
1352 * @param trail List of peers which are part of trail from @a querying_peer to
1353 * @a successor, NOT including them.
1354 * @param trail_length Total number of peers in @a trail
1355 * @param trail_direction Direction in which we are sending the message. In this
1356 * case we are sending result from @a successor to @a querying_peer.
1357 * @param target_friend Next friend to get this message.
1360 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1361 struct GNUNET_PeerIdentity current_successor,
1362 struct GNUNET_PeerIdentity probable_successor,
1363 struct GNUNET_HashCode trail_id,
1364 const struct GNUNET_PeerIdentity *trail,
1365 unsigned int trail_length,
1366 enum GDS_ROUTING_trail_direction trail_direction,
1367 struct FriendInfo *target_friend)
1369 struct PeerVerifySuccessorResultMessage *vsmr;
1370 struct P2PPendingMessage *pending;
1371 struct GNUNET_PeerIdentity *peer_list;
1374 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1375 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1377 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1383 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1385 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1389 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1390 pending->importance = 0; /* FIXME */
1391 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1392 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1393 pending->msg = &vsmr->header;
1394 vsmr->header.size = htons (msize);
1395 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1396 vsmr->querying_peer = querying_peer;
1397 vsmr->current_successor = current_successor;
1398 vsmr->probable_successor = probable_successor;
1399 vsmr->trail_direction = htonl (trail_direction);
1400 vsmr->trail_id = trail_id;
1401 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1402 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1404 /* Send the message to chosen friend. */
1405 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1406 target_friend->pending_count++;
1407 process_friend_queue (target_friend);
1412 * Construct a notify new successor message and send it to target_friend
1413 * @param source_peer Peer which wants to notify to its new successor that it
1414 * could be its predecessor.
1415 * @param successor New successor of @a source_peer
1416 * @param successor_trail List of peers in Trail to reach from
1417 * @a source_peer to @a new_successor, NOT including
1419 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1420 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1421 * @param target_friend Next friend to get this message.
1424 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1425 struct GNUNET_PeerIdentity successor,
1426 const struct GNUNET_PeerIdentity *successor_trail,
1427 unsigned int successor_trail_length,
1428 struct GNUNET_HashCode succesor_trail_id,
1429 struct FriendInfo *target_friend)
1431 struct PeerNotifyNewSuccessorMessage *nsm;
1432 struct P2PPendingMessage *pending;
1433 struct GNUNET_PeerIdentity *peer_list;
1436 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1437 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1439 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1445 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1447 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1451 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1452 pending->importance = 0; /* FIXME */
1453 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1454 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1455 pending->msg = &nsm->header;
1456 nsm->header.size = htons (msize);
1457 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1458 nsm->new_successor = successor;
1459 nsm->source_peer = source_peer;
1460 nsm->trail_id = succesor_trail_id;
1462 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1463 memcpy (peer_list, successor_trail,
1464 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1466 /* Send the message to chosen friend. */
1467 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1468 target_friend->pending_count++;
1469 process_friend_queue (target_friend);
1474 * Construct an add_trail message and send it to target_friend
1475 * @param source_peer Source of the trail.
1476 * @param destination_peer Destination of the trail.
1477 * @param trail_id Unique identifier of the trail from
1478 * @a source_peer to @a destination_peer, NOT including the endpoints.
1479 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1480 * NOT including the endpoints.
1481 * @param trail_length Total number of peers in @a trail.
1482 * @param target_friend Next friend to get this message.
1485 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1486 struct GNUNET_PeerIdentity destination_peer,
1487 struct GNUNET_HashCode trail_id,
1488 const struct GNUNET_PeerIdentity *trail,
1489 unsigned int trail_length,
1490 struct FriendInfo *target_friend)
1492 struct PeerAddTrailMessage *adm;
1493 struct GNUNET_PeerIdentity *peer_list;
1494 struct P2PPendingMessage *pending;
1497 msize = sizeof (struct PeerAddTrailMessage) +
1498 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1500 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1506 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1508 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1512 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1513 pending->importance = 0; /* FIXME */
1514 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1515 adm = (struct PeerAddTrailMessage *) &pending[1];
1516 pending->msg = &adm->header;
1517 adm->header.size = htons (msize);
1518 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1519 adm->source_peer = source_peer;
1520 adm->destination_peer = destination_peer;
1521 adm->trail_id = trail_id;
1522 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1523 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1525 /* Send the message to chosen friend. */
1526 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1527 target_friend->pending_count++;
1528 process_friend_queue (target_friend);
1534 * Construct a trail compression message and send it to target_friend.
1535 * @param source_peer Source of the trail.
1536 * @param trail_id Unique identifier of trail.
1537 * @param first_friend First hop in compressed trail to reach from source to finger
1538 * @param target_friend Next friend to get this message.
1541 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1542 struct GNUNET_HashCode trail_id,
1543 struct GNUNET_PeerIdentity first_friend,
1544 struct FriendInfo *target_friend)
1546 struct P2PPendingMessage *pending;
1547 struct PeerTrailCompressionMessage *tcm;
1550 msize = sizeof (struct PeerTrailCompressionMessage);
1552 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1558 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1560 GNUNET_STATISTICS_update (GDS_stats,
1561 gettext_noop ("# P2P messages dropped due to full queue"),
1565 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1566 pending->importance = 0; /* FIXME */
1567 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1568 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1569 pending->msg = &tcm->header;
1570 tcm->header.size = htons (msize);
1571 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1572 tcm->source_peer = source_peer;
1573 tcm->new_first_friend = first_friend;
1574 tcm->trail_id = trail_id;
1576 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1577 target_friend->pending_count++;
1578 process_friend_queue (target_friend);
1584 * Search my location in trail. In case I am present more than once in the
1585 * trail (can happen during trail setup), then return my lowest index.
1586 * @param trail List of peers
1587 * @return my_index if found
1588 * -1 if no entry found.
1591 search_my_index (const struct GNUNET_PeerIdentity *trail,
1596 for (i = 0; i < trail_length; i++)
1598 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1607 * Check if the friend is congested or have reached maximum number of trails
1608 * it can be part of of.
1609 * @param friend Friend to be checked.
1610 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1611 * #GNUNET_YES if friend is either congested or have crossed threshold
1614 is_friend_congested (struct FriendInfo *friend)
1616 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1617 ((0 == GNUNET_TIME_absolute_get_remaining
1618 (friend->congestion_timestamp).rel_value_us)))
1626 * Select closest finger to value.
1627 * @param peer1 First peer
1628 * @param peer2 Second peer
1629 * @param value Value to be compare
1630 * @return Closest peer
1632 const static struct GNUNET_PeerIdentity *
1633 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1634 const struct GNUNET_PeerIdentity *peer2,
1637 uint64_t peer1_value;
1638 uint64_t peer2_value;
1640 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1641 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1642 peer1_value = GNUNET_ntohll (peer1_value);
1643 peer2_value = GNUNET_ntohll (peer2_value);
1645 if (peer1_value == value)
1650 if (peer2_value == value)
1655 if (peer2_value < peer1_value)
1657 if ((peer2_value < value) && (value < peer1_value))
1661 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1662 ((0 < value) && (value < peer2_value)))
1668 if (peer1_value < peer2_value)
1670 if ((peer1_value < value) && (value < peer2_value))
1674 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1675 ((0 < value) && (value < peer1_value)))
1685 * Select closest predecessor to value.
1686 * @param peer1 First peer
1687 * @param peer2 Second peer
1688 * @param value Value to be compare
1689 * @return Peer which precedes value in the network.
1691 const static struct GNUNET_PeerIdentity *
1692 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1693 const struct GNUNET_PeerIdentity *peer2,
1696 uint64_t peer1_value;
1697 uint64_t peer2_value;
1699 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1700 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1701 peer1_value = GNUNET_ntohll (peer1_value);
1702 peer2_value = GNUNET_ntohll (peer2_value);
1704 if (peer1_value == value)
1707 if (peer2_value == value)
1710 if (peer1_value < peer2_value)
1712 if ((peer1_value < value) && (value < peer2_value))
1716 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1717 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1723 if (peer2_value < peer1_value)
1725 if ((peer2_value < value) && (value < peer1_value))
1729 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1730 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1744 test_print_trail (struct GNUNET_PeerIdentity *trail,
1745 unsigned int trail_length)
1747 struct GNUNET_PeerIdentity print_peer;
1750 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1751 __FILE__, __func__,__LINE__,trail_length);
1752 for (i =0 ; i< trail_length; i++)
1754 print_peer = trail[i];
1755 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1756 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1763 * This is a test function to print all the entries of friend table.
1766 test_friend_peermap_print ()
1768 struct FriendInfo *friend;
1769 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1770 struct GNUNET_PeerIdentity print_peer;
1771 struct GNUNET_PeerIdentity key_ret;
1774 print_peer = my_identity;
1775 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1776 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1778 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1780 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1782 (const void **)&friend))
1784 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1785 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1786 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1794 * This is a test function, to print all the entries of finger table.
1797 test_finger_table_print()
1799 struct FingerInfo *finger;
1800 struct GNUNET_PeerIdentity print_peer;
1801 //struct Trail *trail;
1805 print_peer = my_identity;
1806 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1807 for (i = 0; i < MAX_FINGERS; i++)
1809 finger = &finger_table[i];
1811 if (GNUNET_NO == finger->is_present)
1814 print_peer = finger->finger_identity;
1815 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1816 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1819 for (j = 0; j < finger->trails_count; j++)
1821 trail = &finger->trail_list[j];
1822 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1823 struct Trail_Element *element;
1824 element = trail->trail_head;
1825 for (k = 0; k < trail->trail_length; k++)
1827 print_peer = element->peer;
1828 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1829 element = element->next;
1838 * Select the closest peer among two peers (which should not be same)
1839 * with respect to value and finger_table_index
1840 * NOTE: peer1 != peer2
1841 * @param peer1 First peer
1842 * @param peer2 Second peer
1843 * @param value Value relative to which we find the closest
1844 * @param is_predecessor Is value a predecessor or any other finger.
1845 * @return Closest peer among two peers.
1847 const static struct GNUNET_PeerIdentity *
1848 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1849 const struct GNUNET_PeerIdentity *peer2,
1851 unsigned int is_predecessor)
1853 if (1 == is_predecessor)
1854 return select_closest_predecessor (peer1, peer2, value);
1856 return select_closest_finger (peer1, peer2, value);
1861 * Iterate over the list of all the trails of a finger. In case the first
1862 * friend to reach the finger has reached trail threshold or is congested,
1863 * then don't select it. In case there multiple available good trails to reach
1864 * to Finger, choose the one with shortest trail length.
1865 * Note: We use length as parameter. But we can use any other suitable parameter
1867 * @param finger Finger
1868 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1869 * and trail length. NULL in case none of the trails are free.
1871 static struct Selected_Finger_Trail *
1872 select_finger_trail (struct FingerInfo *finger)
1874 struct FriendInfo *friend;
1875 struct Trail *iterator;
1876 struct Selected_Finger_Trail *finger_trail;
1878 unsigned int flag = 0;
1881 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1882 GNUNET_assert (finger->trails_count > 0);
1884 for (i = 0; i < finger->trails_count; i++)
1886 iterator = &finger->trail_list[i];
1888 /* No trail stored at this index. */
1889 if (GNUNET_NO == iterator->is_present)
1892 GNUNET_assert (NULL !=
1894 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1895 &iterator->trail_head->peer)));
1897 /* First friend to reach trail is not free. */
1898 if (GNUNET_YES == is_friend_congested (friend))
1907 finger_trail->trail_length = iterator->trail_length;
1908 finger_trail->friend = *friend;
1909 finger_trail->trail_id = iterator->trail_id;
1911 else if (finger_trail->trail_length > iterator->trail_length)
1913 finger_trail->friend = *friend;
1914 finger_trail->trail_id = iterator->trail_id;
1915 finger_trail->trail_length = iterator->trail_length;
1919 /* All the first friend in all the trails to reach to finger are either
1920 congested or have crossed trail threshold. */
1921 if (j == finger->trails_count)
1924 return finger_trail;
1929 * Compare FINGER entry with current successor. If finger's first friend of all
1930 * its trail is not congested and has not crossed trail threshold, then check
1931 * if finger peer identity is closer to final_destination_finger_value than
1932 * current_successor. If yes then update current_successor.
1933 * @param current_successor[in/out]
1937 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1939 struct FingerInfo *finger;
1940 const struct GNUNET_PeerIdentity *closest_peer;
1941 struct Selected_Finger_Trail *finger_trail;
1944 /* Iterate over finger table. */
1945 for (i = 0; i < MAX_FINGERS; i++)
1947 finger = &finger_table[i];
1949 if (GNUNET_NO == finger->is_present)
1952 /* FIXME write correct comment here */
1953 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1954 ¤t_closest_peer->best_known_destination))
1957 /* If I am my own finger, then ignore this finger. */
1958 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1961 /* FIXME: I think a peer should not select itself as its own identity ever.
1962 But it does select. Find out why??*/
1968 /* If finger is a friend, then do nothing. As we have already checked
1969 * for each friend in compare_friend_and_current_successor(). */
1970 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1971 &finger->finger_identity)))
1976 closest_peer = select_closest_peer (&finger->finger_identity,
1977 ¤t_closest_peer->best_known_destination,
1978 current_closest_peer->destination_finger_value,
1979 current_closest_peer->is_predecessor);
1981 if (&finger->finger_identity == closest_peer)
1983 /* Choose one of the trail to reach to finger. */
1984 finger_trail = select_finger_trail (finger);
1986 /* In case no trail found, ignore this finger. */
1987 if (NULL == finger_trail)
1990 current_closest_peer->best_known_destination = finger->finger_identity;
1991 current_closest_peer->next_hop = finger_trail->friend.id;
1992 current_closest_peer->trail_id = finger_trail->trail_id;
1993 GNUNET_free(finger_trail);
2001 * Compare friend entry with current successor.
2002 * If friend identity and current_successor is same, then do nothing.
2003 * If friend is not congested and has not crossed trail threshold, then check
2004 * if friend peer identity is closer to final_destination_finger_value than
2005 * current_successor. If yes then update current_successor.
2006 * @param cls closure
2007 * @param key current public key
2008 * @param value struct Closest_Peer
2009 * @return #GNUNET_YES if we should continue to iterate,
2010 * #GNUNET_NO if not.
2013 compare_friend_and_current_closest_peer (void *cls,
2014 const struct GNUNET_PeerIdentity *key,
2017 struct FriendInfo *friend = value;
2018 struct Closest_Peer *current_closest_peer = cls;
2019 const struct GNUNET_PeerIdentity *closest_peer;
2021 /* Friend is either congested or has crossed threshold. */
2022 if (GNUNET_YES == is_friend_congested (friend))
2025 /* If current_closest_peer and friend identity are same, then do nothing.*/
2026 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2027 ¤t_closest_peer->best_known_destination))
2033 closest_peer = select_closest_peer (&friend->id,
2034 ¤t_closest_peer->best_known_destination,
2035 current_closest_peer->destination_finger_value,
2036 current_closest_peer->is_predecessor);
2038 /* Is friend the closest successor? */
2039 if (&friend->id == closest_peer)
2041 current_closest_peer->best_known_destination = friend->id;
2042 current_closest_peer->next_hop = friend->id;
2050 * Initialize current_successor to my_identity.
2051 * @param my_identity My peer identity
2052 * @return Updated closest_peer
2054 static struct Closest_Peer
2055 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2056 uint64_t destination_finger_value,
2057 unsigned int is_predecessor)
2059 struct Closest_Peer current_closest_peer;
2061 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2062 current_closest_peer.destination_finger_value = destination_finger_value;
2063 current_closest_peer.is_predecessor = is_predecessor;
2064 current_closest_peer.next_hop = my_identity;
2065 current_closest_peer.best_known_destination = my_identity;
2067 return current_closest_peer;
2072 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2073 * peer. It could be because of the logic we wrote here. Verify if its correct.
2074 * If not then return immediate_successor.
2076 * Find the successor for destination_finger_value among my_identity, my
2077 * friends and my fingers. Don't consider friends or fingers which are either
2078 * congested or have crossed the threshold.
2079 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2081 * @param destination_finger_value Peer closest to this value will be the next successor.
2082 * @param is_predecessor Are we looking for predecessor or finger?
2083 * @return Successor It is never NULL, in case none of friend or finger is closest,
2084 * then we return my_identity.
2086 static struct Closest_Peer
2087 find_successor (uint64_t destination_finger_value,
2088 unsigned int is_predecessor)
2090 struct Closest_Peer current_closest_peer;
2092 /* Initialize current_successor to my_identity. */
2093 current_closest_peer = init_current_successor (my_identity,
2094 destination_finger_value,
2097 /* Compare each friend entry with current_successor and update current_successor
2098 * with friend if its closest. */
2101 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2102 &compare_friend_and_current_closest_peer,
2103 ¤t_closest_peer));
2105 /* Compare each finger entry with current_successor and update current_successor
2106 * with finger if its closest. */
2107 compare_finger_and_current_successor (¤t_closest_peer);
2109 return current_closest_peer;
2114 * FIXME; Send put message across all the trail to reach to next hop to handle
2116 * Construct a Put message and send it to target_peer.
2117 * @param key Key for the content
2118 * @param block_type Type of the block
2119 * @param options Routing options
2120 * @param desired_replication_level Desired replication count
2121 * @param best_known_dest Peer to which this message should reach eventually,
2122 * as it is best known destination to me.
2123 * @param intermediate_trail_id Trail id in case
2124 * @param target_peer Peer to which this message will be forwarded.
2125 * @param hop_count Number of hops traversed so far.
2126 * @param put_path_length Total number of peers in @a put_path
2127 * @param put_path Number of peers traversed so far
2128 * @param expiration_time When does the content expire
2129 * @param data Content to store
2130 * @param data_size Size of content @a data in bytes
2133 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2134 enum GNUNET_BLOCK_Type block_type,
2135 enum GNUNET_DHT_RouteOption options,
2136 uint32_t desired_replication_level,
2137 struct GNUNET_PeerIdentity best_known_dest,
2138 struct GNUNET_HashCode intermediate_trail_id,
2139 struct GNUNET_PeerIdentity *target_peer,
2141 uint32_t put_path_length,
2142 struct GNUNET_PeerIdentity *put_path,
2143 struct GNUNET_TIME_Absolute expiration_time,
2144 const void *data, size_t data_size)
2146 struct PeerPutMessage *ppm;
2147 struct P2PPendingMessage *pending;
2148 struct FriendInfo *target_friend;
2149 struct GNUNET_PeerIdentity *pp;
2150 struct GNUNET_PeerIdentity next_hop;
2154 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2155 sizeof (struct PeerPutMessage);
2157 #if ENABLE_MALICIOUS
2158 /*Call is made to this function from
2160 2. Every peer to construct a pending message and send it to next peer.
2161 In case of 2nd, this case should have been handled in handle_dht_p2p_put/get
2162 No need to check here. First peer can never be malicious. IDEALLY we DONOT
2163 need the condition here. REMOVE IT AFTERWARDS once verified.*/
2164 if(1 == act_malicious)
2169 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2171 put_path_length = 0;
2172 msize = data_size + sizeof (struct PeerPutMessage);
2175 /* Should it be GNUNET_SERVER_MAX_MESSAGE_SIZE? */
2176 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2178 DEBUG("msize = %lu\n",msize);
2183 /* This is the first call made from clients file. So, we should search for the
2185 if (NULL == target_peer)
2188 struct Closest_Peer successor;
2190 memcpy (&key_value, key, sizeof (uint64_t));
2191 key_value = GNUNET_ntohll (key_value);
2193 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2194 best_known_dest = successor.best_known_destination;
2195 next_hop = successor.next_hop;
2196 intermediate_trail_id = successor.trail_id;
2198 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2200 /* I am the destination. */
2201 DEBUG("PUT destination is me = %s,key =%s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2202 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2203 block_type,data_size,data);
2207 GNUNET_assert (NULL !=
2209 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2213 GNUNET_assert (NULL !=
2215 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2218 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2219 pending->timeout = expiration_time;
2220 ppm = (struct PeerPutMessage *) &pending[1];
2221 pending->msg = &ppm->header;
2222 ppm->header.size = htons (msize);
2223 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2224 ppm->options = htonl (options);
2225 ppm->block_type = htonl (block_type);
2226 ppm->hop_count = htonl (hop_count + 1);
2227 ppm->desired_replication_level = htonl (desired_replication_level);
2228 ppm->put_path_length = htonl (put_path_length);
2229 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2230 ppm->best_known_destination = best_known_dest;
2233 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2234 if (put_path_length != 0)
2236 memcpy (pp, put_path,
2237 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2239 memcpy (&pp[put_path_length], data, data_size);
2240 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2241 target_friend->pending_count++;
2242 process_friend_queue (target_friend);
2247 * FIXME; Send get message across all the trail to reach to next hop to handle
2249 * Construct a Get message and send it to target_peer.
2250 * @param key Key for the content
2251 * @param block_type Type of the block
2252 * @param options Routing options
2253 * @param desired_replication_level Desired replication count
2254 * @param best_known_dest Peer which should get this message. Same as target peer
2255 * if best_known_dest is a friend else its a finger.
2256 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2257 * in case it is a finger else set to 0.
2258 * @param target_peer Peer to which this message will be forwarded.
2259 * @param hop_count Number of hops traversed so far.
2260 * @param data Content to store
2261 * @param data_size Size of content @a data in bytes
2262 * @param get_path_length Total number of peers in @a get_path
2263 * @param get_path Number of peers traversed so far
2266 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2267 enum GNUNET_BLOCK_Type block_type,
2268 enum GNUNET_DHT_RouteOption options,
2269 uint32_t desired_replication_level,
2270 struct GNUNET_PeerIdentity best_known_dest,
2271 struct GNUNET_HashCode intermediate_trail_id,
2272 struct GNUNET_PeerIdentity *target_peer,
2274 uint32_t get_path_length,
2275 struct GNUNET_PeerIdentity *get_path)
2277 struct PeerGetMessage *pgm;
2278 struct P2PPendingMessage *pending;
2279 struct FriendInfo *target_friend;
2280 struct GNUNET_PeerIdentity *gp;
2283 msize = sizeof (struct PeerGetMessage) +
2284 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2286 #if ENABLE_MALICIOUS
2287 if(1 == act_malicious)
2292 //GNUNET_SERVER_MAX_MESSAGE_SIZE
2293 /* FIXME:TODO:URGENTHere you can try to optimize it a bit. In case the get path contains you
2294 or your friend then shorten the path. */
2295 /* In this case we don't make get_path_length = 0, as we need get path to
2296 * return the message back to querying client. */
2297 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2303 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
2305 /* This is the first time we got request from our own client file. */
2306 if (NULL == target_peer)
2309 struct Closest_Peer successor;
2311 memcpy (&key_value, key, sizeof (uint64_t));
2312 key_value = GNUNET_ntohll (key_value);
2313 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2315 best_known_dest = successor.best_known_destination;
2316 intermediate_trail_id = successor.trail_id;
2318 /* I am the destination. I have the data. */
2319 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2322 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2323 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2324 NULL, 0, 1, &my_identity, NULL,&my_identity);
2330 GNUNET_assert (NULL !=
2332 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2333 &successor.next_hop)));
2339 GNUNET_assert (NULL !=
2341 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2344 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2345 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2346 pending->importance = 0; /* FIXME */
2347 pgm = (struct PeerGetMessage *) &pending[1];
2348 pending->msg = &pgm->header;
2349 pgm->header.size = htons (msize);
2350 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2351 pgm->get_path_length = htonl (get_path_length);
2352 pgm->best_known_destination = best_known_dest;
2354 pgm->intermediate_trail_id = intermediate_trail_id;
2355 pgm->hop_count = htonl (hop_count + 1);
2356 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2358 if (get_path_length != 0)
2360 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2363 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2364 target_friend->pending_count++;
2365 process_friend_queue (target_friend);
2370 * Send the get result to requesting client.
2371 * @param key Key of the requested data.
2372 * @param type Block type
2373 * @param target_peer Next peer to forward the message to.
2374 * @param source_peer Peer which has the data for the key.
2375 * @param put_path_length Number of peers in @a put_path
2376 * @param put_path Path taken to put the data at its stored location.
2377 * @param get_path_length Number of peers in @a get_path
2378 * @param get_path Path taken to reach to the location of the key.
2379 * @param expiration When will this result expire?
2380 * @param data Payload to store
2381 * @param data_size Size of the @a data
2384 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2385 enum GNUNET_BLOCK_Type type,
2386 const struct GNUNET_PeerIdentity *target_peer,
2387 const struct GNUNET_PeerIdentity *source_peer,
2388 unsigned int put_path_length,
2389 const struct GNUNET_PeerIdentity *put_path,
2390 unsigned int get_path_length,
2391 const struct GNUNET_PeerIdentity *get_path,
2392 struct GNUNET_TIME_Absolute expiration,
2393 const void *data, size_t data_size)
2395 struct PeerGetResultMessage *get_result;
2396 struct GNUNET_PeerIdentity *paths;
2397 struct P2PPendingMessage *pending;
2398 struct FriendInfo *target_friend;
2399 int current_path_index;
2402 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2404 sizeof (struct PeerGetResultMessage);
2406 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2408 put_path_length = 0;
2409 msize = msize - put_path_length;
2413 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2418 DEBUG("GET RESULT FOR DATA_SIZE = %lu\n",msize);
2419 current_path_index = 0;
2420 if(get_path_length > 0)
2422 current_path_index = search_my_index(get_path, get_path_length);
2423 if (-1 == current_path_index)
2429 if (0 == current_path_index)
2431 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2432 get_path, put_path_length,
2433 put_path, type, data_size, data);
2437 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2438 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2439 pending->importance = 0;
2440 get_result = (struct PeerGetResultMessage *)&pending[1];
2441 pending->msg = &get_result->header;
2442 get_result->header.size = htons (msize);
2443 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2444 get_result->key = *key;
2445 get_result->querying_peer = *source_peer;
2446 get_result->expiration_time = expiration;
2447 get_result->get_path_length = htonl (get_path_length);
2448 get_result->put_path_length = htonl (put_path_length);
2449 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2450 memcpy (paths, put_path,
2451 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2452 memcpy (&paths[put_path_length], get_path,
2453 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2454 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2456 GNUNET_assert (NULL !=
2458 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2459 &get_path[current_path_index - 1])));
2460 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2461 target_friend->pending_count++;
2462 process_friend_queue (target_friend);
2467 * Randomly choose one of your friends (which is not congested and have not crossed
2468 * trail threshold) from the friend_peermap
2469 * @return Friend Randomly chosen friend.
2470 * NULL in case friend peermap is empty, or all the friends are either
2471 * congested or have crossed trail threshold.
2473 static struct FriendInfo *
2474 select_random_friend ()
2476 unsigned int current_size;
2479 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2480 struct GNUNET_PeerIdentity key_ret;
2481 struct FriendInfo *friend;
2483 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2486 if (0 == current_size)
2489 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2490 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2492 /* Iterate till you don't reach to index. */
2493 for (j = 0; j < index ; j++)
2494 GNUNET_assert (GNUNET_YES ==
2495 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2498 /* Reset the index in friend peermap to 0 as we reached to the end. */
2499 if (j == current_size)
2502 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2503 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2507 /* Get the friend stored at the index, j*/
2508 GNUNET_assert (GNUNET_YES ==
2509 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2511 (const void **)&friend));
2513 /* This friend is not congested and has not crossed trail threshold. */
2514 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2515 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2521 } while (j != index);
2523 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2529 * Compute 64 bit value of finger_identity corresponding to a finger index using
2531 * For all fingers, n.finger[i] = n + pow (2,i),
2532 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2533 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2534 * @param finger_index Index corresponding to which we calculate 64 bit value.
2535 * @return 64 bit value.
2538 compute_finger_identity_value (unsigned int finger_index)
2542 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2543 my_id64 = GNUNET_ntohll (my_id64);
2545 /* Are we looking for immediate predecessor? */
2546 if (PREDECESSOR_FINGER_ID == finger_index)
2547 return (my_id64 - 1);
2550 uint64_t add = (uint64_t)1 << finger_index;
2551 return (my_id64 + add);
2555 static struct GNUNET_TIME_Relative next_send_time;
2558 * Choose a random friend. Calculate the next finger identity to search,from
2559 * current_search_finger_index. Start looking for the trail to reach to
2560 * finger identity through this random friend.
2562 * @param cls closure for this task
2563 * @param tc the context under which the task is running
2566 send_find_finger_trail_message (void *cls,
2567 const struct GNUNET_SCHEDULER_TaskContext *tc)
2569 struct FriendInfo *target_friend;
2570 //struct GNUNET_TIME_Relative next_send_time;
2571 struct GNUNET_HashCode trail_id;
2572 struct GNUNET_HashCode intermediate_trail_id;
2573 unsigned int is_predecessor;
2574 uint64_t finger_id_value;
2576 /* Schedule another send_find_finger_trail_message task. */
2577 find_finger_trail_task =
2578 GNUNET_SCHEDULER_add_delayed (next_send_time,
2579 &send_find_finger_trail_message,
2582 /* No space in my routing table. (Source and destination peers also store entries
2583 * in their routing table). */
2584 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2588 target_friend = select_random_friend ();
2589 if (NULL == target_friend)
2594 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2596 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2601 /* Generate a unique trail id for trail we are trying to setup. */
2602 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2603 &trail_id, sizeof (trail_id));
2604 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2606 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2607 target_friend->id, target_friend, 0, NULL,
2608 is_predecessor, trail_id,
2609 intermediate_trail_id);
2614 * In case there are already maximum number of possible trails to reach to a
2615 * finger, then check if the new trail's length is lesser than any of the
2617 * If yes then replace that old trail by new trail.
2619 * Note: Here we are taking length as a parameter to choose the best possible
2620 * trail, but there could be other parameters also like:
2621 * 1. duration of existence of a trail - older the better.
2622 * 2. if the new trail is completely disjoint than the
2623 * other trails, then may be choosing it is better.
2625 * @param existing_finger
2626 * @param new_finger_trail
2627 * @param new_finger_trail_length
2628 * @param new_finger_trail_id
2631 select_and_replace_trail (struct FingerInfo *existing_finger,
2632 const struct GNUNET_PeerIdentity *new_trail,
2633 unsigned int new_trail_length,
2634 struct GNUNET_HashCode new_trail_id)
2636 struct Trail *trail_list_iterator;
2637 unsigned int largest_trail_length;
2638 unsigned int largest_trail_index;
2639 struct Trail_Element *trail_element;
2642 largest_trail_length = new_trail_length;
2643 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2645 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2647 for (i = 0; i < existing_finger->trails_count; i++)
2649 trail_list_iterator = &existing_finger->trail_list[i];
2650 if (trail_list_iterator->trail_length > largest_trail_length)
2652 largest_trail_length = trail_list_iterator->trail_length;
2653 largest_trail_index = i;
2657 /* New trail is not better than existing ones. Send trail teardown. */
2658 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2660 struct GNUNET_PeerIdentity next_hop;
2662 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2663 GDS_ROUTING_remove_trail (new_trail_id);
2664 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2665 GDS_ROUTING_SRC_TO_DEST,
2670 /* Send trail teardown message across the replaced trail. */
2671 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2672 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2673 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2674 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2675 GDS_ROUTING_SRC_TO_DEST,
2676 replace_trail->trail_head->peer);
2677 /* Free the trail. */
2678 while (NULL != (trail_element = replace_trail->trail_head))
2680 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2681 replace_trail->trail_tail, trail_element);
2682 GNUNET_free_non_null (trail_element);
2685 /* Add new trial at that location. */
2686 replace_trail->is_present = GNUNET_YES;
2687 replace_trail->trail_length = new_trail_length;
2688 replace_trail->trail_id = new_trail_id;
2689 //FIXME: Do we need to add pointers for head and tail.
2691 while (i < new_trail_length)
2693 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2694 element->peer = new_trail[i];
2696 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2697 replace_trail->trail_tail,
2704 * Check if the new trail to reach to finger is unique or do we already have
2705 * such a trail present for finger.
2706 * @param existing_finger Finger identity
2707 * @param new_trail New trail to reach @a existing_finger
2708 * @param trail_length Total number of peers in new_trail.
2709 * @return #GNUNET_YES if the new trail is unique
2710 * #GNUNET_NO if same trail is already present.
2713 is_new_trail_unique (struct FingerInfo *existing_finger,
2714 const struct GNUNET_PeerIdentity *new_trail,
2715 unsigned int trail_length)
2717 struct Trail *trail_list_iterator;
2718 struct Trail_Element *trail_element;
2721 int trail_unique = GNUNET_NO;
2723 GNUNET_assert (existing_finger->trails_count > 0);
2725 /* Iterate over list of trails. */
2726 for (i = 0; i < existing_finger->trails_count; i++)
2728 trail_list_iterator = &existing_finger->trail_list[i];
2729 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2731 /* New trail and existing trail length are not same. */
2732 if (trail_list_iterator->trail_length != trail_length)
2734 trail_unique = GNUNET_YES;
2738 trail_element = trail_list_iterator->trail_head;
2739 for (j = 0; j < trail_list_iterator->trail_length; j++)
2741 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2742 &trail_element->peer))
2744 trail_unique = GNUNET_YES;
2747 trail_element = trail_element->next;
2750 trail_unique = GNUNET_NO;
2753 return trail_unique;
2758 * Add a new trail to existing finger. This function is called only when finger
2759 * is not my own identity or a friend.
2760 * @param existing_finger Finger
2761 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2762 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2763 * @param new_finger_trail_id Unique identifier of the trail.
2766 add_new_trail (struct FingerInfo *existing_finger,
2767 const struct GNUNET_PeerIdentity *new_trail,
2768 unsigned int new_trail_length,
2769 struct GNUNET_HashCode new_trail_id)
2771 struct Trail *trail_list_iterator;
2772 struct FriendInfo *first_friend;
2775 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2781 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2782 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2783 trail_list_iterator->trail_id = new_trail_id;
2784 trail_list_iterator->trail_length = new_trail_length;
2785 existing_finger->trails_count++;
2786 trail_list_iterator->is_present = GNUNET_YES;
2788 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2789 &existing_finger->finger_identity)));
2790 /* If finger is a friend then we never call this function. */
2791 GNUNET_assert (new_trail_length > 0);
2793 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2795 first_friend->trails_count++;
2797 for (i = 0; i < new_trail_length; i++)
2799 struct Trail_Element *element;
2801 element = GNUNET_new (struct Trail_Element);
2802 element->peer = new_trail[i];
2803 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2804 trail_list_iterator->trail_tail,
2807 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2813 * FIXME Check if this function is called for opposite direction if yes then
2814 * take it as parameter.
2815 * Get the next hop to send trail teardown message from routing table and
2816 * then delete the entry from routing table. Send trail teardown message for a
2817 * specific trail of a finger.
2818 * @param finger Finger whose trail is to be removed.
2819 * @param trail List of peers in trail from me to a finger, NOT including
2823 send_trail_teardown (struct FingerInfo *finger,
2824 struct Trail *trail)
2826 struct FriendInfo *friend;
2827 struct GNUNET_PeerIdentity *next_hop;
2829 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2830 GDS_ROUTING_SRC_TO_DEST);
2832 if (NULL == next_hop)
2837 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2840 GNUNET_assert (trail->is_present == GNUNET_YES);
2842 /* Finger is not a friend. */
2843 if (trail->trail_length > 0)
2845 GNUNET_assert (NULL != (friend =
2846 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2847 &trail->trail_head->peer)));
2851 GNUNET_assert (NULL != (friend =
2852 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2853 &finger->finger_identity)));
2856 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2857 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2858 friend->trails_count--;
2859 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2860 GDS_ROUTING_SRC_TO_DEST,
2866 * Send trail teardown message across all the trails to reach to finger.
2867 * @param finger Finger whose all the trail should be freed.
2870 send_all_finger_trails_teardown (struct FingerInfo *finger)
2874 for (i = 0; i < finger->trails_count; i++)
2876 struct Trail *trail;
2878 trail = &finger->trail_list[i];
2879 GNUNET_assert (trail->is_present == GNUNET_YES);
2880 send_trail_teardown (finger, trail);
2881 trail->is_present = GNUNET_NO;
2887 * Free a specific trail
2888 * @param trail List of peers to be freed.
2891 free_trail (struct Trail *trail)
2893 struct Trail_Element *trail_element;
2895 while (NULL != (trail_element = trail->trail_head))
2897 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2900 GNUNET_free_non_null (trail_element);
2902 trail->trail_head = NULL;
2903 trail->trail_tail = NULL;
2908 * Free finger and its trail.
2909 * @param finger Finger to be freed.
2912 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2914 struct Trail *trail;
2917 /* Free all the trails to reach to finger */
2918 for (i = 0; i < finger->trails_count; i++)
2920 trail = &finger->trail_list[i];
2921 //FIXME: Check if there are any missing entry in this list because of
2922 // how we insert. If not then no need of this check.
2923 if (GNUNET_NO == trail->is_present)
2926 if (trail->trail_length > 0)
2930 trail->is_present = GNUNET_NO;
2933 finger->is_present = GNUNET_NO;
2934 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2939 * Add a new entry in finger table at finger_table_index.
2940 * In case I am my own finger, then we don't have a trail. In case of a friend,
2941 * we have a trail with unique id and '0' trail length.
2942 * In case a finger is a friend, then increment the trails count of the friend.
2943 * @param finger_identity Peer Identity of new finger
2944 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2945 * @param finger_trail_length Total number of peers in @a finger_trail.
2946 * @param trail_id Unique identifier of the trail.
2947 * @param finger_table_index Index in finger table.
2950 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2951 const struct GNUNET_PeerIdentity *finger_trail,
2952 unsigned int finger_trail_length,
2953 struct GNUNET_HashCode trail_id,
2954 unsigned int finger_table_index)
2956 struct FingerInfo *new_entry;
2957 struct FriendInfo *first_trail_hop;
2958 struct Trail *trail;
2961 new_entry = GNUNET_new (struct FingerInfo);
2962 new_entry->finger_identity = finger_identity;
2963 new_entry->finger_table_index = finger_table_index;
2964 new_entry->is_present = GNUNET_YES;
2966 /* If the new entry is my own identity. */
2967 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2970 new_entry->trails_count = 0;
2971 finger_table[finger_table_index] = *new_entry;
2972 GNUNET_free (new_entry);
2976 /* If finger is a friend, then we don't actually have a trail.
2977 * Just a trail id */
2978 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2981 new_entry->trail_list[0].trail_id = trail_id;
2982 new_entry->trails_count = 1;
2983 new_entry->trail_list[0].is_present = GNUNET_YES;
2984 new_entry->trail_list[0].trail_length = 0;
2985 new_entry->trail_list[0].trail_head = NULL;
2986 new_entry->trail_list[0].trail_tail = NULL;
2987 finger_table[finger_table_index] = *new_entry;
2988 GNUNET_assert (NULL !=
2990 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2991 &finger_identity)));
2993 first_trail_hop->trails_count++;
2994 GNUNET_free (new_entry);
2998 GNUNET_assert (NULL !=
3000 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3001 &finger_trail[0])));
3002 new_entry->trails_count = 1;
3003 first_trail_hop->trails_count++;
3005 /* Copy the finger trail into trail. */
3006 trail = GNUNET_new (struct Trail);
3007 while (i < finger_trail_length)
3009 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3011 element->next = NULL;
3012 element->prev = NULL;
3013 element->peer = finger_trail[i];
3014 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3020 /* Add trail to trail list. */
3021 new_entry->trail_list[0].trail_head = trail->trail_head;
3022 new_entry->trail_list[0].trail_tail = trail->trail_tail;
3023 new_entry->trail_list[0].trail_length = finger_trail_length;
3024 new_entry->trail_list[0].trail_id = trail_id;
3025 new_entry->trail_list[0].is_present = GNUNET_YES;
3026 finger_table[finger_table_index] = *new_entry;
3027 GNUNET_free (new_entry);
3033 * Scan the trail to check if there is any other friend in the trail other than
3034 * first hop. If yes then shortcut the trail, send trail compression message to
3035 * peers which are no longer part of trail and send back the updated trail
3036 * and trail_length to calling function.
3037 * @param finger_identity Finger whose trail we will scan.
3038 * @param finger_trail [in, out] Trail to reach from source to finger,
3039 * @param finger_trail_length Total number of peers in original finger_trail.
3040 * @param finger_trail_id Unique identifier of the finger trail.
3041 * @return updated trail length in case we shortcut the trail, else original
3044 static struct GNUNET_PeerIdentity *
3045 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
3046 const struct GNUNET_PeerIdentity *trail,
3047 unsigned int trail_length,
3048 struct GNUNET_HashCode trail_id,
3049 int *new_trail_length)
3051 struct FriendInfo *target_friend;
3052 struct GNUNET_PeerIdentity *new_trail;
3055 /* I am my own finger. */
3056 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3058 *new_trail_length = 0;
3062 if (0 == trail_length)
3064 *new_trail_length = 0;
3068 /* If finger identity is a friend. */
3069 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3071 *new_trail_length = 0;
3073 /* If there is trail to reach this finger/friend */
3074 if (trail_length > 0)
3076 /* Finger is your first friend. */
3077 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3078 GNUNET_assert (NULL !=
3080 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3084 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3085 trail_id, finger_identity,
3091 /* For other cases, when its neither a friend nor my own identity.*/
3092 for (i = trail_length - 1; i > 0; i--)
3094 /* If the element at this index in trail is a friend. */
3095 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3097 struct FriendInfo *target_friend;
3100 GNUNET_assert (NULL !=
3102 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3104 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3105 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3110 /* Copy the trail from index i to index (trail_length -1) into a new trail
3111 * and update new trail length */
3112 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3113 while (i < trail_length)
3115 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3119 *new_trail_length = j+1;
3124 /* If we did not compress the trail, return the original trail back.*/
3125 *new_trail_length = trail_length;
3126 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3127 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3133 * Periodic task to verify current successor. There can be multiple trails to reach
3134 * to successor, choose the shortest one and send verify successor message
3135 * across that trail.
3136 * @param cls closure for this task
3137 * @param tc the context under which the task is running
3140 send_verify_successor_message (void *cls,
3141 const struct GNUNET_SCHEDULER_TaskContext *tc)
3143 struct FriendInfo *target_friend;
3144 struct GNUNET_HashCode trail_id;
3146 struct GNUNET_TIME_Relative next_send_time;
3147 struct Trail *trail;
3148 struct Trail_Element *element;
3149 unsigned int trail_length;
3151 struct FingerInfo *successor;
3153 /* Schedule another send_find_finger_trail_message task. */
3154 next_send_time.rel_value_us =
3155 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3156 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3157 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3158 send_verify_successor_task =
3159 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3162 successor = &finger_table[0];
3163 for (i = 0; i < successor->trails_count; i++)
3165 trail = &successor->trail_list[i];
3166 if(GNUNET_YES == trail->is_present)
3170 if (i == successor->trails_count)
3173 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3174 &successor->finger_identity));
3176 /* Trail stored at this index. */
3177 GNUNET_assert (GNUNET_YES == trail->is_present);
3179 trail_id = trail->trail_id;
3180 trail_length = trail->trail_length;
3182 if (trail_length > 0)
3184 /* Copy the trail into peer list. */
3185 struct GNUNET_PeerIdentity peer_list[trail_length];
3187 element = trail->trail_head;
3188 while (j < trail_length)
3190 peer_list[j] = element->peer;
3191 element = element->next;
3195 GNUNET_assert (NULL != (target_friend =
3196 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3198 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3199 successor->finger_identity,
3200 trail_id, peer_list, trail_length,
3206 GNUNET_assert (NULL != (target_friend =
3207 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3208 &successor->finger_identity)));
3209 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3210 successor->finger_identity,
3219 * Update the current search finger index.
3221 * FIXME document parameters!
3224 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3225 unsigned int finger_table_index)
3227 struct FingerInfo *successor;
3229 /* FIXME correct this: only move current index periodically */
3230 if (finger_table_index != current_search_finger_index)
3233 successor = &finger_table[0];
3234 GNUNET_assert (GNUNET_YES == successor->is_present);
3236 /* We were looking for immediate successor. */
3237 if (0 == current_search_finger_index)
3239 /* Start looking for immediate predecessor. */
3240 current_search_finger_index = PREDECESSOR_FINGER_ID;
3242 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3244 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3245 send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3251 current_search_finger_index = current_search_finger_index - 1;
3257 * Get the least significant bit set in val.
3260 * @return Position of first bit set, 65 in case of error.
3263 find_set_bit (uint64_t val)
3283 return 65; /* Some other bit was set to 1 as well. */
3290 * Calculate finger_table_index from initial 64 bit finger identity value that
3291 * we send in trail setup message.
3292 * @param ultimate_destination_finger_value Value that we calculated from our
3293 * identity and finger_table_index.
3294 * @param is_predecessor Is the entry for predecessor or not?
3295 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3296 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3299 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3300 unsigned int is_predecessor)
3304 unsigned int finger_table_index;
3306 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3307 my_id64 = GNUNET_ntohll (my_id64);
3309 /* Is this a predecessor finger? */
3310 if (1 == is_predecessor)
3312 diff = my_id64 - ultimate_destination_finger_value;
3314 finger_table_index = PREDECESSOR_FINGER_ID;
3316 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3321 diff = ultimate_destination_finger_value - my_id64;
3322 finger_table_index = find_set_bit (diff);
3324 return finger_table_index;
3329 * Remove finger and its associated data structures from finger table.
3330 * @param finger Finger to be removed.
3333 remove_existing_finger (struct FingerInfo *existing_finger,
3334 unsigned int finger_table_index)
3336 struct FingerInfo *finger;
3338 finger = &finger_table[finger_table_index];
3339 GNUNET_assert (GNUNET_YES == finger->is_present);
3341 /* If I am my own finger, then we have no trails. */
3342 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3345 finger->is_present = GNUNET_NO;
3346 memset ((void *)&finger_table[finger_table_index], 0,
3347 sizeof (finger_table[finger_table_index]));
3351 /* For all other fingers, send trail teardown across all the trails to reach
3352 finger, and free the finger. */
3353 send_all_finger_trails_teardown (finger);
3354 free_finger (finger, finger_table_index);
3360 * Check if there is already an entry in finger_table at finger_table_index.
3361 * We get the finger_table_index from 64bit finger value we got from the network.
3362 * -- If yes, then select the closest finger.
3363 * -- If new and existing finger are same, then check if you can store more
3365 * -- If yes then add trail, else keep the best trails to reach to the
3367 * -- If the new finger is closest, remove the existing entry, send trail
3368 * teardown message across all the trails to reach the existing entry.
3369 * Add the new finger.
3370 * -- If new and existing finger are different, and existing finger is closest
3372 * -- Update current_search_finger_index.
3373 * @param finger_identity Peer Identity of new finger
3374 * @param finger_trail Trail to reach the new finger
3375 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3376 * @param is_predecessor Is this entry for predecessor in finger_table?
3377 * @param finger_value 64 bit value of finger identity that we got from network.
3378 * @param finger_trail_id Unique identifier of @finger_trail.
3381 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3382 const struct GNUNET_PeerIdentity *finger_trail,
3383 unsigned int finger_trail_length,
3384 unsigned int is_predecessor,
3385 uint64_t finger_value,
3386 struct GNUNET_HashCode finger_trail_id)
3388 struct FingerInfo *existing_finger;
3389 const struct GNUNET_PeerIdentity *closest_peer;
3390 struct FingerInfo *successor;
3391 int updated_finger_trail_length;
3392 unsigned int finger_table_index;
3394 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3395 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3397 /* Invalid finger_table_index. */
3398 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3400 GNUNET_break_op (0);
3404 /* New entry same as successor. */
3405 if ((0 != finger_table_index) &&
3406 (PREDECESSOR_FINGER_ID != finger_table_index))
3408 successor = &finger_table[0];
3409 if (GNUNET_NO == successor->is_present)
3411 GNUNET_break_op (0);
3414 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3415 &successor->finger_identity))
3417 current_search_finger_index = 0;
3418 /* We slow down the find_finger_trail_task as we have completed the circle. */
3419 next_send_time = GNUNET_TIME_STD_BACKOFF(next_send_time);
3424 struct FingerInfo prev_finger;
3425 prev_finger = finger_table[finger_table_index - 1];
3426 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3427 &prev_finger.finger_identity))
3429 current_search_finger_index--;
3434 existing_finger = &finger_table[finger_table_index];
3436 /* No entry present in finger_table for given finger map index. */
3437 if (GNUNET_NO == existing_finger->is_present)
3439 struct GNUNET_PeerIdentity *updated_trail;
3441 /* Shorten the trail if possible. */
3442 updated_finger_trail_length = finger_trail_length;
3443 updated_trail = scan_and_compress_trail (finger_identity, finger_trail,
3444 finger_trail_length,
3446 &updated_finger_trail_length);
3447 add_new_finger (finger_identity, updated_trail,
3448 updated_finger_trail_length,
3449 finger_trail_id, finger_table_index);
3450 GNUNET_free_non_null(updated_trail);
3451 update_current_search_finger_index (finger_identity,
3452 finger_table_index);
3457 /* If existing entry and finger identity are not same. */
3458 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3461 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3466 /* If the new finger is the closest peer. */
3467 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3469 struct GNUNET_PeerIdentity *updated_trail;
3470 /* Shorten the trail if possible. */
3471 updated_finger_trail_length = finger_trail_length;
3473 scan_and_compress_trail (finger_identity, finger_trail,
3474 finger_trail_length, finger_trail_id,
3475 &updated_finger_trail_length);
3476 remove_existing_finger (existing_finger, finger_table_index);
3477 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3478 finger_trail_id, finger_table_index);
3479 GNUNET_free_non_null((struct GNUNET_PeerIdentity *)updated_trail);
3483 /* Existing finger is the closest one. We need to send trail teardown
3484 across the trail setup in routing table of all the peers. */
3485 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3487 if (finger_trail_length > 0)
3488 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3489 GDS_ROUTING_SRC_TO_DEST,
3492 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3493 GDS_ROUTING_SRC_TO_DEST,
3500 /* If both new and existing entry are same as my_identity, then do nothing. */
3501 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3506 /* If the existing finger is not a friend. */
3508 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3509 &existing_finger->finger_identity))
3511 struct GNUNET_PeerIdentity *updated_trail;
3513 /* Shorten the trail if possible. */
3514 updated_finger_trail_length = finger_trail_length;
3516 scan_and_compress_trail (finger_identity, finger_trail,
3517 finger_trail_length, finger_trail_id,
3518 &updated_finger_trail_length);
3519 /* If there is space to store more trails. */
3520 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3521 add_new_trail (existing_finger, updated_trail,
3522 updated_finger_trail_length, finger_trail_id);
3524 select_and_replace_trail (existing_finger, updated_trail,
3525 updated_finger_trail_length, finger_trail_id);
3529 update_current_search_finger_index (finger_identity, finger_table_index);
3535 * FIXME: Check for loop in the request. If you already are part of put path,
3536 * then you need to reset the put path length.
3537 * Core handler for P2P put messages.
3538 * @param cls closure
3539 * @param peer sender of the request
3540 * @param message message
3541 * @return #GNUNET_OK to keep the connection open,
3542 * #GNUNET_SYSERR to close it (signal serious error)
3545 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3546 const struct GNUNET_MessageHeader *message)
3548 struct PeerPutMessage *put;
3549 struct GNUNET_PeerIdentity *put_path;
3550 struct GNUNET_PeerIdentity best_known_dest;
3551 struct GNUNET_HashCode intermediate_trail_id;
3552 struct GNUNET_PeerIdentity *next_hop;
3553 enum GNUNET_DHT_RouteOption options;
3554 struct GNUNET_HashCode test_key;
3558 size_t payload_size;
3561 #if ENABLE_MALICIOUS
3562 if(1 == act_malicious)
3564 DEBUG("I am malicious,dropping put request. \n");
3569 msize = ntohs (message->size);
3570 if (msize < sizeof (struct PeerPutMessage))
3572 GNUNET_break_op (0);
3576 put = (struct PeerPutMessage *) message;
3577 putlen = ntohl (put->put_path_length);
3581 sizeof (struct PeerPutMessage) +
3582 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3584 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3586 GNUNET_break_op (0);
3589 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
3590 GNUNET_STATISTICS_update (GDS_stats,
3592 ("# Bytes received from other peers"), (int64_t) msize,
3595 best_known_dest = put->best_known_destination;
3596 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3597 payload = &put_path[putlen];
3598 options = ntohl (put->options);
3599 intermediate_trail_id = put->intermediate_trail_id;
3601 payload_size = msize - (sizeof (struct PeerPutMessage) +
3602 putlen * sizeof (struct GNUNET_PeerIdentity));
3604 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3605 payload, payload_size, &test_key))
3608 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3610 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3611 GNUNET_break_op (0);
3612 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3613 "PUT with key `%s' for block with key %s\n",
3614 put_s, GNUNET_h2s_full (&test_key));
3615 GNUNET_free (put_s);
3620 GNUNET_break_op (0);
3623 /* cannot verify, good luck */
3627 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3629 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3630 ntohl (put->block_type),
3632 NULL, 0, /* bloom filer */
3633 NULL, 0, /* xquery */
3634 payload, payload_size))
3636 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3637 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3640 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3641 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3642 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3643 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3644 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3645 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3647 GNUNET_break_op (0);
3652 /* extend 'put path' by sender */
3653 struct GNUNET_PeerIdentity pp[putlen + 1];
3654 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3656 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3663 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3664 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3666 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3667 GDS_ROUTING_SRC_TO_DEST);
3668 if (NULL == next_hop)
3670 GNUNET_STATISTICS_update (GDS_stats,
3671 gettext_noop ("# Next hop to forward the packet not found "
3672 "trail setup request, packet dropped."),
3674 return GNUNET_SYSERR;
3679 struct Closest_Peer successor;
3680 key_value = GNUNET_ntohll (key_value);
3681 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3682 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3683 *next_hop = successor.next_hop;
3684 intermediate_trail_id = successor.trail_id;
3685 best_known_dest = successor.best_known_destination;
3688 GDS_CLIENTS_process_put (options,
3689 ntohl (put->block_type),
3690 ntohl (put->hop_count),
3691 ntohl (put->desired_replication_level),
3693 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3698 /* I am the final destination */
3699 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3701 DEBUG("PUT destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(put->key)));
3702 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3703 &(put->key),putlen, pp, ntohl (put->block_type),
3704 payload_size, payload);
3708 GDS_NEIGHBOURS_send_put (&put->key,
3709 ntohl (put->block_type),ntohl (put->options),
3710 ntohl (put->desired_replication_level),
3711 best_known_dest, intermediate_trail_id, next_hop,
3712 ntohl (put->hop_count), putlen, pp,
3713 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3714 payload, payload_size);
3721 * FIXME: Check for loop in the request. If you already are part of get path,
3722 * then you need to reset the get path length.
3723 * Core handler for p2p get requests.
3725 * @param cls closure
3726 * @param peer sender of the request
3727 * @param message message
3728 * @return #GNUNET_OK to keep the connection open,
3729 * #GNUNET_SYSERR to close it (signal serious error)
3732 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3733 const struct GNUNET_MessageHeader *message)
3735 const struct PeerGetMessage *get;
3736 const struct GNUNET_PeerIdentity *get_path;
3737 struct GNUNET_PeerIdentity best_known_dest;
3738 struct GNUNET_HashCode intermediate_trail_id;
3739 struct GNUNET_PeerIdentity *next_hop;
3740 uint32_t get_length;
3744 #if ENABLE_MALICIOUS
3745 if(1 == act_malicious)
3747 DEBUG("I am malicious,dropping get request. \n");
3752 msize = ntohs (message->size);
3753 if (msize < sizeof (struct PeerGetMessage))
3755 GNUNET_break_op (0);
3759 get = (const struct PeerGetMessage *)message;
3760 get_length = ntohl (get->get_path_length);
3761 best_known_dest = get->best_known_destination;
3762 intermediate_trail_id = get->intermediate_trail_id;
3763 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3766 sizeof (struct PeerGetMessage) +
3767 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3769 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3771 GNUNET_break_op (0);
3774 DEBUG("PUT FOR DATA_SIZE = %lu\n",msize);
3775 GNUNET_STATISTICS_update (GDS_stats,
3777 ("# Bytes received from other peers"), msize,
3780 /* Add sender to get path */
3781 struct GNUNET_PeerIdentity gp[get_length + 1];
3783 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3784 gp[get_length] = *peer;
3785 get_length = get_length + 1;
3787 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3788 key_value = GNUNET_ntohll (key_value);
3790 /* I am not the final destination. I am part of trail to reach final dest. */
3791 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3793 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3794 GDS_ROUTING_SRC_TO_DEST);
3795 if (NULL == next_hop)
3797 GNUNET_STATISTICS_update (GDS_stats,
3798 gettext_noop ("# Next hop to forward the packet not found "
3799 "GET request, packet dropped."),
3801 return GNUNET_SYSERR;
3806 struct Closest_Peer successor;
3808 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3809 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3810 *next_hop = successor.next_hop;
3811 best_known_dest = successor.best_known_destination;
3812 intermediate_trail_id = successor.trail_id;
3815 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3816 get->desired_replication_level, get->get_path_length,
3818 /* I am the final destination. */
3819 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3821 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(get->key)));
3822 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3824 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3825 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3826 get_length = get_length + 1;
3828 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3829 get_length, final_get_path,
3830 &final_get_path[get_length-2], &my_identity);
3834 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3835 get->desired_replication_level, best_known_dest,
3836 intermediate_trail_id, next_hop, 0,
3844 * Core handler for get result
3845 * @param cls closure
3846 * @param peer sender of the request
3847 * @param message message
3848 * @return #GNUNET_OK to keep the connection open,
3849 * #GNUNET_SYSERR to close it (signal serious error)
3852 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3853 const struct GNUNET_MessageHeader *message)
3855 const struct PeerGetResultMessage *get_result;
3856 const struct GNUNET_PeerIdentity *get_path;
3857 const struct GNUNET_PeerIdentity *put_path;
3858 const void *payload;
3859 size_t payload_size;
3861 unsigned int getlen;
3862 unsigned int putlen;
3863 int current_path_index;
3865 msize = ntohs (message->size);
3866 if (msize < sizeof (struct PeerGetResultMessage))
3868 GNUNET_break_op (0);
3872 get_result = (const struct PeerGetResultMessage *)message;
3873 getlen = ntohl (get_result->get_path_length);
3874 putlen = ntohl (get_result->put_path_length);
3877 sizeof (struct PeerGetResultMessage) +
3878 getlen * sizeof (struct GNUNET_PeerIdentity) +
3879 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3881 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3883 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3885 GNUNET_break_op (0);
3888 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3889 GNUNET_STATISTICS_update (GDS_stats,
3891 ("# Bytes received from other peers"), msize,
3894 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3895 get_path = &put_path[putlen];
3896 payload = (const void *) &get_path[getlen];
3897 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3898 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3900 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3902 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3903 getlen, get_path, putlen,
3904 put_path, get_result->type, payload_size, payload);
3909 current_path_index = search_my_index (get_path, getlen);
3910 if (-1 == current_path_index )
3913 return GNUNET_SYSERR;
3915 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3916 &get_path[current_path_index - 1],
3917 &(get_result->querying_peer), putlen, put_path,
3918 getlen, get_path, get_result->expiration_time,
3919 payload, payload_size);
3922 return GNUNET_SYSERR;
3927 * Find the next hop to pass trail setup message. First find the local best known
3928 * hop from your own identity, friends and finger. If you were part of trail,
3929 * then get the next hop from routing table. Compare next_hop from routing table
3930 * and local best known hop, and return the closest one to final_dest_finger_val
3931 * @param final_dest_finger_val 64 bit value of finger identity
3932 * @param intermediate_trail_id If you are part of trail to reach to some other
3933 * finger, then it is the trail id to reach to
3934 * that finger, else set to 0.
3935 * @param is_predecessor Are we looking for closest successor or predecessor.
3936 * @param current_dest In case you are part of trail, then finger to which
3937 * we should forward the message. Else my own identity
3938 * @return Closest Peer for @a final_dest_finger_val
3940 static struct Closest_Peer
3941 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3942 struct GNUNET_HashCode intermediate_trail_id,
3943 unsigned int is_predecessor,
3944 struct GNUNET_PeerIdentity prev_hop,
3945 struct GNUNET_PeerIdentity source,
3946 struct GNUNET_PeerIdentity *current_dest)
3948 struct Closest_Peer peer;
3950 /* Find a local best known peer. */
3951 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3953 /* Am I just a part of a trail towards a finger (current_destination)? */
3954 /* Select best successor among one found locally and current_destination
3955 * that we got from network.*/
3956 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3957 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3960 const struct GNUNET_PeerIdentity *closest_peer;
3962 closest_peer = select_closest_peer (&peer.best_known_destination,
3964 final_dest_finger_val,
3967 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3968 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3970 struct GNUNET_PeerIdentity *next_hop;
3972 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3973 GDS_ROUTING_SRC_TO_DEST);
3974 /* It may happen that trail teardown message got delayed and hence,
3975 the previous hop sent the message over intermediate trail id.In that
3976 case next_hop could be NULL. */
3977 if(NULL != next_hop)
3979 peer.next_hop = *next_hop;
3980 peer.best_known_destination = *current_dest;
3981 peer.trail_id = intermediate_trail_id;
3989 * Core handle for PeerTrailSetupMessage.
3990 * @param cls closure
3991 * @param message message
3992 * @param peer peer identity this notification is about
3993 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3996 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3997 const struct GNUNET_MessageHeader *message)
3999 const struct PeerTrailSetupMessage *trail_setup;
4000 const struct GNUNET_PeerIdentity *trail_peer_list;
4001 struct GNUNET_PeerIdentity current_dest;
4002 struct FriendInfo *target_friend;
4003 struct GNUNET_PeerIdentity source;
4004 uint64_t final_dest_finger_val;
4005 struct GNUNET_HashCode intermediate_trail_id;
4006 struct GNUNET_HashCode trail_id;
4007 unsigned int is_predecessor;
4008 uint32_t trail_length;
4012 msize = ntohs (message->size);
4013 if (msize < sizeof (struct PeerTrailSetupMessage))
4015 GNUNET_break_op (0);
4016 return GNUNET_SYSERR;
4019 trail_setup = (const struct PeerTrailSetupMessage *) message;
4020 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4021 sizeof (struct GNUNET_PeerIdentity);
4022 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4023 sizeof (struct GNUNET_PeerIdentity) != 0)
4025 GNUNET_break_op (0);
4029 GNUNET_STATISTICS_update (GDS_stats,
4031 ("# Bytes received from other peers"), msize,
4034 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4035 current_dest = trail_setup->best_known_destination;
4036 trail_id = trail_setup->trail_id;
4037 final_dest_finger_val =
4038 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4039 source = trail_setup->source_peer;
4040 is_predecessor = ntohl (trail_setup->is_predecessor);
4041 intermediate_trail_id = trail_setup->intermediate_trail_id;
4043 /* Did the friend insert its ID in the trail list? */
4044 if (trail_length > 0 &&
4045 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (*peer)))
4047 GNUNET_break_op (0);
4048 return GNUNET_SYSERR;
4051 /* If I was the source and got the message back, then set trail length to 0.*/
4052 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4054 /* IF (!) the peers know the destinations of the trails in their routing
4057 * This shoud only happen after 1 hop, since the first message is sent
4058 * to random friend, and we can happen to be on the best trail to the dest.
4059 * If the first friend selects someone else, the request should never come
4064 // GNUNET_break_op (1 == trail_length);
4068 /* Check if you are present in the trail seen so far? */
4069 for (i = 0; i < trail_length ; i++)
4071 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4079 /* Is my routing table full? */
4080 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4082 GNUNET_assert (NULL !=
4084 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4085 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4086 my_identity, is_predecessor,
4087 trail_peer_list, trail_length,
4088 trail_id, target_friend,
4089 CONGESTION_TIMEOUT);
4093 /* Get the next hop to forward the trail setup request. */
4094 struct Closest_Peer next_peer =
4095 get_local_best_known_next_hop (final_dest_finger_val,
4096 intermediate_trail_id,
4102 /* Am I the final destination? */
4103 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4106 /* If I was not the source of this message for which now I am destination */
4107 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4109 GDS_ROUTING_add (trail_id, *peer, my_identity);
4112 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4114 finger_table_add (my_identity, NULL, 0, is_predecessor,
4115 final_dest_finger_val, trail_id);
4119 if (trail_length > 0)
4120 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail_peer_list[trail_length-1]);
4122 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4123 if (NULL == target_friend)
4125 GNUNET_break_op (0);
4126 return GNUNET_SYSERR;
4129 GDS_NEIGHBOURS_send_trail_setup_result (source,
4131 target_friend, trail_length,
4134 final_dest_finger_val,trail_id);
4136 else /* I'm not the final destination. */
4138 GNUNET_assert (NULL !=
4140 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4141 &next_peer.next_hop)));
4143 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4145 /* Add yourself to list of peers. */
4146 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4148 memcpy (peer_list, trail_peer_list,
4149 trail_length * sizeof (struct GNUNET_PeerIdentity));
4150 peer_list[trail_length] = my_identity;
4152 GDS_NEIGHBOURS_send_trail_setup (source,
4153 final_dest_finger_val,
4154 next_peer.best_known_destination,
4155 target_friend, trail_length + 1, peer_list,
4156 is_predecessor, trail_id,
4157 next_peer.trail_id);
4160 GDS_NEIGHBOURS_send_trail_setup (source,
4161 final_dest_finger_val,
4162 next_peer.best_known_destination,
4163 target_friend, 0, NULL,
4164 is_predecessor, trail_id,
4165 next_peer.trail_id);
4171 /* FIXME: here we are calculating my_index and comparing also in this function.
4172 And we are doing it again here in this function. Re factor the code. */
4174 * FIXME: Should we call this function everywhere in all the handle functions
4175 * where we have a trail to verify from or a trail id. something like
4176 * if prev hop is not same then drop the message.
4177 * Check if sender_peer and peer from which we should receive the message are
4178 * same or different.
4179 * @param trail_peer_list List of peers in trail
4180 * @param trail_length Total number of peers in @a trail_peer_list
4181 * @param sender_peer Peer from which we got the message.
4182 * @param finger_identity Finger to which trail is setup. It is not part of trail.
4183 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
4184 * message are different.
4185 * #GNUNET_NO if sender_peer and peer from which we should receive the
4186 * message are different.
4189 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
4190 unsigned int trail_length,
4191 const struct GNUNET_PeerIdentity *sender_peer,
4192 struct GNUNET_PeerIdentity finger_identity,
4193 struct GNUNET_PeerIdentity source_peer)
4197 /* I am the source peer. */
4198 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4201 /* Is the first element of the trail is sender_peer.*/
4202 if (trail_length > 0)
4204 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4210 /* Is finger the sender peer? */
4211 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4218 /* Get my current location in the trail. */
4219 my_index = search_my_index (trail_peer_list, trail_length);
4223 /* I am the last element in the trail. */
4224 if ((trail_length - 1) == my_index)
4226 /* Is finger the sender_peer? */
4227 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4233 /* Is peer after me in trail the sender peer? */
4234 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4235 &trail_peer_list[my_index + 1]))
4245 * FIXME: we should also add a case where we search if we are present in the trail
4247 * Core handle for p2p trail setup result messages.
4249 * @param message message
4250 * @param peer sender of this message.
4251 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4254 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4255 const struct GNUNET_MessageHeader *message)
4257 const struct PeerTrailSetupResultMessage *trail_result;
4258 const struct GNUNET_PeerIdentity *trail_peer_list;
4259 struct GNUNET_PeerIdentity next_hop;
4260 struct FriendInfo *target_friend;
4261 struct GNUNET_PeerIdentity querying_peer;
4262 struct GNUNET_PeerIdentity finger_identity;
4263 uint32_t trail_length;
4264 uint64_t ulitmate_destination_finger_value;
4265 uint32_t is_predecessor;
4266 struct GNUNET_HashCode trail_id;
4270 msize = ntohs (message->size);
4271 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4273 GNUNET_break_op (0);
4277 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4278 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4279 sizeof (struct GNUNET_PeerIdentity);
4280 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4281 sizeof (struct GNUNET_PeerIdentity) != 0)
4283 GNUNET_break_op (0);
4287 GNUNET_STATISTICS_update (GDS_stats,
4289 ("# Bytes received from other peers"), msize,
4292 is_predecessor = ntohl (trail_result->is_predecessor);
4293 querying_peer = trail_result->querying_peer;
4294 finger_identity = trail_result->finger_identity;
4295 trail_id = trail_result->trail_id;
4296 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4297 ulitmate_destination_finger_value =
4298 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4300 /* Ensure that sender peer is the peer from which we were expecting the message. */
4302 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
4304 peer, finger_identity, querying_peer))
4306 GNUNET_break_op (0);
4307 return GNUNET_SYSERR;
4311 /*TODO:URGENT Check if I am already present in the trail. If yes then its an error,
4312 as in trail setup we ensure that it should never happen. */
4313 /* Am I the one who initiated the query? */
4314 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4316 /* If I am my own finger identity, error. */
4317 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4319 GNUNET_break_op (0);
4320 return GNUNET_SYSERR;
4322 GDS_ROUTING_add (trail_id, my_identity, *peer);
4323 finger_table_add (finger_identity, trail_peer_list, trail_length,
4324 is_predecessor, ulitmate_destination_finger_value, trail_id);
4328 /* Get my location in the trail. */
4329 my_index = search_my_index (trail_peer_list, trail_length);
4333 return GNUNET_SYSERR;
4337 next_hop = trail_result->querying_peer;
4339 next_hop = trail_peer_list[my_index - 1];
4341 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4342 if (NULL == target_friend)
4344 GNUNET_break_op (0);
4345 return GNUNET_SYSERR;
4348 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4349 &(trail_result->finger_identity))))
4351 GNUNET_break_op (0);
4352 return GNUNET_SYSERR;
4355 GDS_ROUTING_add (trail_id, next_hop, *peer);
4357 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4358 target_friend, trail_length, trail_peer_list,
4360 ulitmate_destination_finger_value,
4368 * @param trail Trail to be inverted
4369 * @param trail_length Total number of peers in the trail.
4370 * @return Updated trail
4372 static struct GNUNET_PeerIdentity *
4373 invert_trail (const struct GNUNET_PeerIdentity *trail,
4374 unsigned int trail_length)
4378 struct GNUNET_PeerIdentity *inverted_trail;
4380 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4383 j = trail_length - 1;
4384 while (i < trail_length)
4386 inverted_trail[i] = trail[j];
4391 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4392 &inverted_trail[0]));
4393 return inverted_trail;
4398 * Return the shortest trail among all the trails to reach to finger from me.
4399 * @param finger Finger
4400 * @param shortest_trail_length[out] Trail length of shortest trail from me
4402 * @return Shortest trail.
4404 static struct GNUNET_PeerIdentity *
4405 get_shortest_trail (struct FingerInfo *finger,
4406 unsigned int *trail_length)
4408 struct Trail *trail;
4409 unsigned int flag = 0;
4410 unsigned int shortest_trail_index = 0;
4411 int shortest_trail_length = -1;
4412 struct Trail_Element *trail_element;
4413 struct GNUNET_PeerIdentity *trail_list;
4416 trail = GNUNET_new (struct Trail);
4418 /* Get the shortest trail to reach to current successor. */
4419 for (i = 0; i < finger->trails_count; i++)
4421 trail = &finger->trail_list[i];
4425 shortest_trail_index = i;
4426 shortest_trail_length = trail->trail_length;
4431 if (shortest_trail_length > trail->trail_length)
4433 shortest_trail_index = i;
4434 shortest_trail_length = trail->trail_length;
4439 /* Copy the shortest trail and return. */
4440 trail = &finger->trail_list[shortest_trail_index];
4441 trail_element = trail->trail_head;
4443 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4444 shortest_trail_length);
4446 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4448 trail_list[i] = trail_element->peer;
4451 GNUNET_assert(shortest_trail_length != -1);
4453 *trail_length = shortest_trail_length;
4459 * Check if trail_1 and trail_2 have any common element. If yes then join
4460 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4461 * @param trail_1 Trail from source to me, NOT including endpoints.
4462 * @param trail_1_len Total number of peers @a trail_1
4463 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4464 * @param trail_2_len Total number of peers @a trail_2
4465 * @param joined_trail_len Total number of peers in combined trail of trail_1
4467 * @return Joined trail.
4469 static struct GNUNET_PeerIdentity *
4470 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4471 unsigned int trail_1_len,
4472 struct GNUNET_PeerIdentity *trail_2,
4473 unsigned int trail_2_len,
4474 unsigned int *joined_trail_len)
4476 struct GNUNET_PeerIdentity *joined_trail;
4481 for (i = 0; i < trail_1_len; i++)
4483 for (j = 0; j < trail_2_len; j++)
4485 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4488 *joined_trail_len = i + (trail_2_len - j);
4489 joined_trail = GNUNET_malloc (*joined_trail_len *
4490 sizeof(struct GNUNET_PeerIdentity));
4493 /* Copy all the elements from 0 to i into joined_trail. */
4494 for(k = 0; k < ( i+1); k++)
4496 joined_trail[k] = trail_1[k];
4499 /* Increment j as entry stored is same as entry stored at i*/
4502 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4503 while(k <= (*joined_trail_len - 1))
4505 joined_trail[k] = trail_2[j];
4510 return joined_trail;
4514 /* Here you should join the trails. */
4515 *joined_trail_len = trail_1_len + trail_2_len + 1;
4516 joined_trail = GNUNET_malloc (*joined_trail_len *
4517 sizeof(struct GNUNET_PeerIdentity));
4520 for(i = 0; i < trail_1_len;i++)
4522 joined_trail[i] = trail_1[i];
4525 joined_trail[i] = my_identity;
4528 for (j = 0; i < *joined_trail_len; i++,j++)
4530 joined_trail[i] = trail_2[j];
4533 return joined_trail;
4538 * Return the trail from source to my current predecessor. Check if source
4539 * is already part of the this trail, if yes then return the shorten trail.
4540 * @param current_trail Trail from source to me, NOT including the endpoints.
4541 * @param current_trail_length Number of peers in @a current_trail.
4542 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4543 * source to my predecessor, NOT including
4545 * @return Trail from source to my predecessor.
4547 static struct GNUNET_PeerIdentity *
4548 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4549 const struct GNUNET_PeerIdentity *trail_src_to_me,
4550 unsigned int trail_src_to_me_len,
4551 unsigned int *trail_src_to_curr_pred_length)
4553 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4554 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4555 unsigned int trail_me_to_curr_pred_length;
4556 struct FingerInfo *current_predecessor;
4560 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4562 /* Check if trail_src_to_me contains current_predecessor. */
4563 for (i = 0; i < trail_src_to_me_len; i++)
4565 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4566 ¤t_predecessor->finger_identity))
4570 *trail_src_to_curr_pred_length = i;
4575 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4576 sizeof(struct GNUNET_PeerIdentity));
4577 for(j = 0; j < i;j++)
4578 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4579 return trail_src_to_curr_pred;
4583 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4584 &trail_me_to_curr_pred_length);
4586 /* Check if trail contains the source_peer. */
4587 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4589 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4590 &trail_me_to_curr_pred[i]))
4593 /* Source is NOT part of trail. */
4596 /* Source is the last element in the trail to reach to my pred.
4597 Source is direct friend of the pred. */
4598 if (trail_me_to_curr_pred_length == i)
4600 *trail_src_to_curr_pred_length = 0;
4604 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4605 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4606 *trail_src_to_curr_pred_length);
4608 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4610 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4612 GNUNET_free_non_null(trail_me_to_curr_pred);
4613 return trail_src_to_curr_pred;
4617 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4618 trail_src_to_me_len,
4619 trail_me_to_curr_pred,
4620 trail_me_to_curr_pred_length,
4622 *trail_src_to_curr_pred_length = len;
4623 GNUNET_free_non_null(trail_me_to_curr_pred);
4624 return trail_src_to_curr_pred;
4629 * Add finger as your predecessor. To add, first generate a new trail id, invert
4630 * the trail to get the trail from me to finger, add an entry in your routing
4631 * table, send add trail message to peers which are part of trail from me to
4632 * finger and add finger in finger table.
4635 * @param trail_length
4638 update_predecessor (struct GNUNET_PeerIdentity finger,
4639 struct GNUNET_PeerIdentity *trail,
4640 unsigned int trail_length)
4642 struct GNUNET_HashCode trail_to_new_predecessor_id;
4643 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4644 struct FriendInfo *target_friend;
4646 /* Generate trail id for trail from me to new predecessor = finger. */
4647 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4648 &trail_to_new_predecessor_id,
4649 sizeof (trail_to_new_predecessor_id));
4651 /* Finger is a friend. */
4652 if (trail_length == 0)
4654 trail_to_new_predecessor = NULL;
4655 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4656 GNUNET_assert (NULL != (target_friend =
4657 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4662 /* Invert the trail to get the trail from me to finger, NOT including the
4664 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4665 &trail[trail_length-1]));
4667 trail_to_new_predecessor = invert_trail (trail, trail_length);
4669 /* Add an entry in your routing table. */
4670 GDS_ROUTING_add (trail_to_new_predecessor_id,
4672 trail_to_new_predecessor[0]);
4674 GNUNET_assert (NULL != (target_friend =
4675 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4676 &trail_to_new_predecessor[0])));
4677 GNUNET_assert (NULL != (
4678 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4679 &trail[trail_length - 1])));
4682 /* Add entry in routing table of all peers that are part of trail from me
4683 to finger, including finger. */
4684 GDS_NEIGHBOURS_send_add_trail (my_identity,
4686 trail_to_new_predecessor_id,
4687 trail_to_new_predecessor,
4691 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4692 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4693 GNUNET_free_non_null(trail_to_new_predecessor);
4698 * Check if you already have a predecessor. If not then add finger as your
4699 * predecessor. If you have predecessor, then compare two peer identites.
4700 * If finger is correct predecessor, then remove the old entry, add finger in
4701 * finger table and send add_trail message to add the trail in the routing
4702 * table of all peers which are part of trail to reach from me to finger.
4703 * @param finger New peer which may be our predecessor.
4704 * @param trail List of peers to reach from @finger to me.
4705 * @param trail_length Total number of peer in @a trail.
4708 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4709 struct GNUNET_PeerIdentity *trail,
4710 unsigned int trail_length)
4712 struct FingerInfo *current_predecessor;
4713 const struct GNUNET_PeerIdentity *closest_peer;
4714 uint64_t predecessor_value;
4715 unsigned int is_predecessor = 1;
4717 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4719 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4721 /* No predecessor. Add finger as your predecessor. */
4722 if (GNUNET_NO == current_predecessor->is_present)
4724 update_predecessor (finger, trail, trail_length);
4728 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4734 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4735 closest_peer = select_closest_peer (&finger,
4736 ¤t_predecessor->finger_identity,
4737 predecessor_value, is_predecessor);
4739 /* Finger is the closest predecessor. Remove the existing one and add the new
4741 if (closest_peer == &finger)
4743 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4744 update_predecessor (finger, trail, trail_length);
4752 * Core handle for p2p verify successor messages.
4753 * @param cls closure
4754 * @param message message
4755 * @param peer peer identity this notification is about
4756 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4759 handle_dht_p2p_verify_successor(void *cls,
4760 const struct GNUNET_PeerIdentity *peer,
4761 const struct GNUNET_MessageHeader *message)
4763 const struct PeerVerifySuccessorMessage *vsm;
4764 struct GNUNET_HashCode trail_id;
4765 struct GNUNET_PeerIdentity successor;
4766 struct GNUNET_PeerIdentity source_peer;
4767 struct GNUNET_PeerIdentity *trail;
4768 struct GNUNET_PeerIdentity *next_hop;
4769 struct FingerInfo current_predecessor;
4770 struct FriendInfo *target_friend;
4771 unsigned int trail_src_to_curr_pred_len = 0;
4772 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4773 unsigned int trail_length;
4776 msize = ntohs (message->size);
4778 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4780 GNUNET_break_op (0);
4784 vsm = (const struct PeerVerifySuccessorMessage *) message;
4785 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4786 sizeof (struct GNUNET_PeerIdentity);
4787 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4788 sizeof (struct GNUNET_PeerIdentity) != 0)
4790 GNUNET_break_op (0);
4794 GNUNET_STATISTICS_update (GDS_stats,
4796 ("# Bytes received from other peers"), msize,
4799 trail_id = vsm->trail_id;
4800 source_peer = vsm->source_peer;
4801 successor = vsm->successor;
4802 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4805 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4807 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4809 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4810 if (NULL == next_hop)
4812 // GNUNET_break_op (0);
4813 // return GNUNET_SYSERR;
4814 //FIXME: Here it may happen that trail has not yet been added
4815 //in notify successor.
4819 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4821 if(NULL == target_friend)
4826 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4827 trail_id, trail, trail_length,
4832 /* I am the destination of this message. */
4834 /* Check if the source_peer could be our predecessor and if yes then update
4836 compare_and_update_predecessor (source_peer, trail, trail_length);
4837 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4839 /* Is source of this message NOT my predecessor. */
4840 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4843 trail_src_to_curr_pred =
4844 get_trail_src_to_curr_pred (source_peer,
4847 &trail_src_to_curr_pred_len);
4851 trail_src_to_curr_pred_len = trail_length;
4854 trail_src_to_curr_pred =
4855 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4856 *trail_src_to_curr_pred_len);
4857 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4859 trail_src_to_curr_pred[i] = trail[i];
4863 GNUNET_assert (NULL !=
4865 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4866 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4867 current_predecessor.finger_identity,
4868 trail_id, trail_src_to_curr_pred,
4869 trail_src_to_curr_pred_len,
4870 GDS_ROUTING_DEST_TO_SRC,
4872 GNUNET_free_non_null(trail_src_to_curr_pred);
4878 * If the trail from me to my probable successor contains a friend not
4879 * at index 0, then we can shorten the trail.
4880 * @param probable_successor Peer which is our probable successor
4881 * @param trail_me_to_probable_successor Peers in path from me to my probable
4882 * successor, NOT including the endpoints.
4883 * @param trail_me_to_probable_successor_len Total number of peers in
4884 * @a trail_me_to_probable_succesor.
4885 * @return Updated trail, if any friend found.
4886 * Else the trail_me_to_probable_successor.
4888 struct GNUNET_PeerIdentity *
4889 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4890 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4891 unsigned int trail_me_to_probable_successor_len,
4892 unsigned int *trail_to_new_successor_length)
4896 struct GNUNET_PeerIdentity *trail_to_new_successor;
4898 /* Probable successor is a friend */
4899 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4900 &probable_successor))
4902 trail_to_new_successor = NULL;
4903 *trail_to_new_successor_length = 0;
4904 return trail_to_new_successor;
4907 /* Is there any friend of yours in this trail. */
4908 if(trail_me_to_probable_successor_len > 1)
4910 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4912 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4913 &trail_me_to_probable_successor[i]))
4916 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4917 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4918 *trail_to_new_successor_length);
4921 for(j = 0;j < *trail_to_new_successor_length;i++,j++)
4923 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4926 return trail_to_new_successor;
4930 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4931 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4936 * Check if the peer which sent us verify successor result message is still ours
4937 * successor or not. If not, then compare existing successor and probable successor.
4938 * In case probable successor is the correct successor, remove the existing
4939 * successor. Add probable successor as new successor. Send notify new successor
4940 * message to new successor.
4942 * @param probable_successor
4944 * @param trail_length
4947 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4948 struct GNUNET_PeerIdentity probable_successor,
4949 const struct GNUNET_PeerIdentity *trail,
4950 unsigned int trail_length)
4952 struct FingerInfo *current_successor;
4953 const struct GNUNET_PeerIdentity *closest_peer;
4954 struct GNUNET_HashCode trail_id;
4955 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4956 struct FriendInfo *target_friend;
4957 unsigned int trail_me_to_probable_succ_len;
4958 unsigned int is_predecessor = GNUNET_NO;
4959 uint64_t successor_value;
4961 current_successor = &finger_table[0];
4962 successor_value = compute_finger_identity_value(0);
4964 closest_peer = select_closest_peer (&probable_successor,
4965 ¤t_successor->finger_identity,
4966 successor_value, is_predecessor);
4968 /* If the current_successor in the finger table is closest, then do nothing. */
4969 if (closest_peer == ¤t_successor->finger_identity)
4971 /* Code for testing ONLY: Store the successor for path tracking */
4972 // track_topology = 1;
4973 if ((NULL != GDS_stats))
4979 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4980 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4981 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4982 GNUNET_free (my_id_str);
4983 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4988 /* Probable successor is the closest peer.*/
4989 if(trail_length > 0)
4991 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4996 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4997 &probable_successor));
5000 trail_me_to_probable_succ_len = 0;
5001 trail_me_to_probable_succ =
5002 check_trail_me_to_probable_succ (probable_successor,
5003 trail, trail_length,
5004 &trail_me_to_probable_succ_len);
5006 /* Remove the existing successor. */
5007 remove_existing_finger (current_successor, 0);
5009 /* TODO URGENT: Check if any peer is present more than once, if yes then shorten
5010 the trail. before sending it across the network. */
5011 /* Generate a new trail id to reach to your new successor. */
5012 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5013 &trail_id, sizeof (trail_id));
5015 if (trail_me_to_probable_succ_len > 0)
5017 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
5018 GNUNET_assert (NULL !=
5020 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5021 &trail_me_to_probable_succ[0])));
5025 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5026 GNUNET_assert (NULL !=
5028 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5029 &probable_successor)));
5032 add_new_finger (probable_successor, trail_me_to_probable_succ,
5033 trail_me_to_probable_succ_len, trail_id, 0);
5035 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
5036 trail_me_to_probable_succ,
5037 trail_me_to_probable_succ_len,
5045 * FIXME: Check for duplicate elements everywhere when you are making
5047 * Core handle for p2p verify successor result messages.
5048 * @param cls closure
5049 * @param message message
5050 * @param peer peer identity this notification is about
5051 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5054 handle_dht_p2p_verify_successor_result(void *cls,
5055 const struct GNUNET_PeerIdentity *peer,
5056 const struct GNUNET_MessageHeader *message)
5058 const struct PeerVerifySuccessorResultMessage *vsrm;
5059 enum GDS_ROUTING_trail_direction trail_direction;
5060 struct GNUNET_PeerIdentity querying_peer;
5061 struct GNUNET_HashCode trail_id;
5062 struct GNUNET_PeerIdentity *next_hop;
5063 struct FriendInfo *target_friend;
5064 struct GNUNET_PeerIdentity probable_successor;
5065 struct GNUNET_PeerIdentity current_successor;
5066 const struct GNUNET_PeerIdentity *trail;
5067 unsigned int trail_length;
5070 msize = ntohs (message->size);
5071 /* We send a trail to reach from old successor to new successor, if
5072 * old_successor != new_successor.*/
5073 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5075 GNUNET_break_op (0);
5079 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5080 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5081 sizeof (struct GNUNET_PeerIdentity);
5083 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5084 sizeof (struct GNUNET_PeerIdentity) != 0)
5086 GNUNET_break_op (0);
5090 GNUNET_STATISTICS_update (GDS_stats,
5092 ("# Bytes received from other peers"), msize,
5095 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5096 querying_peer = vsrm->querying_peer;
5097 trail_direction = ntohl (vsrm->trail_direction);
5098 trail_id = vsrm->trail_id;
5099 probable_successor = vsrm->probable_successor;
5100 current_successor = vsrm->current_successor;
5103 /* I am the querying_peer. */
5104 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5106 compare_and_update_successor (current_successor,
5107 probable_successor, trail, trail_length);
5111 /*If you are not the querying peer then pass on the message */
5112 GNUNET_assert (NULL != (next_hop =
5113 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
5114 GNUNET_assert (NULL !=
5116 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5117 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5118 vsrm->current_successor,
5119 probable_successor, trail_id,
5122 trail_direction, target_friend);
5128 * Core handle for p2p notify new successor messages.
5129 * @param cls closure
5130 * @param message message
5131 * @param peer peer identity this notification is about
5132 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5135 handle_dht_p2p_notify_new_successor(void *cls,
5136 const struct GNUNET_PeerIdentity *peer,
5137 const struct GNUNET_MessageHeader *message)
5139 const struct PeerNotifyNewSuccessorMessage *nsm;
5140 struct GNUNET_PeerIdentity *trail;
5141 struct GNUNET_PeerIdentity source;
5142 struct GNUNET_PeerIdentity new_successor;
5143 struct GNUNET_HashCode trail_id;
5144 struct GNUNET_PeerIdentity next_hop;
5145 struct FriendInfo *target_friend;
5148 uint32_t trail_length;
5150 msize = ntohs (message->size);
5152 /* We have the trail to reach from source to new successor. */
5153 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5155 GNUNET_break_op (0);
5159 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5160 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5161 sizeof (struct GNUNET_PeerIdentity);
5162 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5163 sizeof (struct GNUNET_PeerIdentity) != 0)
5165 GNUNET_break_op (0);
5169 GNUNET_STATISTICS_update (GDS_stats,
5171 ("# Bytes received from other peers"), msize,
5174 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5175 source = nsm->source_peer;
5176 new_successor = nsm->new_successor;
5177 trail_id = nsm->trail_id;
5180 //FIXME: add a check to make sure peer is correct.
5182 /* I am the new_successor to source_peer. */
5183 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5185 if(trail_length > 0)
5186 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5189 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5191 compare_and_update_predecessor (source, trail, trail_length);
5195 GNUNET_assert(trail_length > 0);
5196 /* I am part of trail to reach to successor. */
5197 my_index = search_my_index (trail, trail_length);
5200 GNUNET_break_op (0);
5201 return GNUNET_SYSERR;
5204 if ((trail_length-1) == my_index)
5205 next_hop = new_successor;
5207 next_hop = trail[my_index + 1];
5210 /* Add an entry in routing table for trail from source to its new successor. */
5211 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5212 GNUNET_assert (NULL !=
5214 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5215 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5217 trail_id, target_friend);
5224 * Core handler for P2P trail rejection message
5225 * @param cls closure
5226 * @param message message
5227 * @param peer peer identity this notification is about
5228 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5231 handle_dht_p2p_trail_setup_rejection (void *cls,
5232 const struct GNUNET_PeerIdentity *peer,
5233 const struct GNUNET_MessageHeader *message)
5235 const struct PeerTrailRejectionMessage *trail_rejection;
5236 unsigned int trail_length;
5237 const struct GNUNET_PeerIdentity *trail_peer_list;
5238 struct FriendInfo *target_friend;
5239 struct GNUNET_TIME_Relative congestion_timeout;
5240 struct GNUNET_HashCode trail_id;
5241 struct GNUNET_PeerIdentity next_peer;
5242 struct GNUNET_PeerIdentity source;
5243 struct GNUNET_PeerIdentity *next_hop;
5244 uint64_t ultimate_destination_finger_value;
5245 unsigned int is_predecessor;
5248 msize = ntohs (message->size);
5249 /* We are passing the trail setup so far. */
5250 if (msize < sizeof (struct PeerTrailRejectionMessage))
5252 GNUNET_break_op (0);
5256 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5257 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5258 sizeof (struct GNUNET_PeerIdentity);
5259 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5260 sizeof (struct GNUNET_PeerIdentity) != 0)
5262 GNUNET_break_op (0);
5266 GNUNET_STATISTICS_update (GDS_stats,
5268 ("# Bytes received from other peers"), msize,
5271 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5272 is_predecessor = ntohl (trail_rejection->is_predecessor);
5273 congestion_timeout = trail_rejection->congestion_time;
5274 source = trail_rejection->source_peer;
5275 trail_id = trail_rejection->trail_id;
5276 ultimate_destination_finger_value =
5277 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5279 /* First set the congestion time of the friend that sent you this message. */
5280 GNUNET_assert (NULL !=
5282 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5283 target_friend->congestion_timestamp =
5284 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5285 congestion_timeout);
5287 /* I am the source peer which wants to setup the trail. Do nothing.
5288 * send_find_finger_trail_task is scheduled periodically.*/
5289 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5292 /* If I am congested then pass this message to peer before me in trail. */
5293 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5295 struct GNUNET_PeerIdentity *new_trail;
5296 unsigned int new_trail_length;
5298 /* Remove yourself from the trail setup so far. */
5299 if (trail_length == 1)
5302 new_trail_length = 0;
5307 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5308 sizeof (struct GNUNET_PeerIdentity));
5310 /* Remove myself from the trail. */
5311 new_trail_length = trail_length -1;
5312 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5313 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5316 GNUNET_assert (NULL !=
5318 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5319 GDS_NEIGHBOURS_send_trail_rejection (source,
5320 ultimate_destination_finger_value,
5321 my_identity, is_predecessor,
5322 new_trail,new_trail_length,trail_id,
5323 target_friend, CONGESTION_TIMEOUT);
5324 GNUNET_free (new_trail);
5328 struct Closest_Peer successor;
5329 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5331 /* Am I the final destination? */
5332 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5335 if (0 == trail_length)
5338 next_peer = trail_peer_list[trail_length-1];
5340 GNUNET_assert (NULL !=
5342 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5344 GDS_NEIGHBOURS_send_trail_setup_result (source,
5346 target_friend, trail_length,
5349 ultimate_destination_finger_value,
5354 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5356 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5357 peer_list[trail_length] = my_identity;
5359 GNUNET_assert (NULL !=
5361 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5363 GDS_NEIGHBOURS_send_trail_setup (source,
5364 ultimate_destination_finger_value,
5365 successor.best_known_destination,
5366 target_friend, trail_length + 1, peer_list,
5367 is_predecessor, trail_id,
5368 successor.trail_id);
5375 * Core handle for p2p trail tear compression messages.
5376 * @param cls closure
5377 * @param message message
5378 * @param peer peer identity this notification is about
5379 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5382 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5383 const struct GNUNET_MessageHeader *message)
5385 const struct PeerTrailCompressionMessage *trail_compression;
5386 struct GNUNET_PeerIdentity *next_hop;
5387 struct FriendInfo *target_friend;
5388 struct GNUNET_HashCode trail_id;
5391 msize = ntohs (message->size);
5393 if (msize != sizeof (struct PeerTrailCompressionMessage))
5395 GNUNET_break_op (0);
5399 GNUNET_STATISTICS_update (GDS_stats,
5401 ("# Bytes received from other peers"), msize,
5404 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5405 trail_id = trail_compression->trail_id;
5407 /* Am I the new first friend to reach to finger of this trail. */
5408 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5411 GNUNET_assert (NULL !=
5412 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5413 &trail_compression->source_peer)));
5415 /* Update your prev hop to source of this message. */
5416 GNUNET_assert (GNUNET_SYSERR !=
5417 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5418 trail_compression->source_peer)));
5422 /* Pass the message to next hop to finally reach to new_first_friend. */
5423 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5425 if (NULL == next_hop)
5431 GNUNET_assert (NULL !=
5433 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5435 GDS_ROUTING_remove_trail (trail_id);
5437 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5439 trail_compression->new_first_friend,
5446 * Core handler for trail teardown message.
5447 * @param cls closure
5448 * @param message message
5449 * @param peer sender of this messsage.
5450 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5453 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5454 const struct GNUNET_MessageHeader *message)
5456 const struct PeerTrailTearDownMessage *trail_teardown;
5457 enum GDS_ROUTING_trail_direction trail_direction;
5458 struct GNUNET_HashCode trail_id;
5459 struct GNUNET_PeerIdentity *next_hop;
5462 msize = ntohs (message->size);
5464 /* Here we pass only the trail id. */
5465 if (msize != sizeof (struct PeerTrailTearDownMessage))
5467 GNUNET_break_op (0);
5471 GNUNET_STATISTICS_update (GDS_stats,
5473 ("# Bytes received from other peers"), msize,
5476 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5477 trail_direction = ntohl (trail_teardown->trail_direction);
5478 trail_id = trail_teardown->trail_id;
5480 /* Check if peer is the real peer from which we should get this message.*/
5481 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5483 GNUNET_assert (NULL != (prev_hop =
5484 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5485 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5488 return GNUNET_SYSERR;
5492 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5494 if (NULL == next_hop)
5497 return GNUNET_SYSERR;
5500 /* I am the next hop, which means I am the final destination. */
5501 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5503 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5508 /* If not final destination, then send a trail teardown message to next hop.*/
5509 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5510 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5511 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5519 * Core handle for p2p add trail message.
5520 * @param cls closure
5521 * @param message message
5522 * @param peer peer identity this notification is about
5523 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5526 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5527 const struct GNUNET_MessageHeader *message)
5529 const struct PeerAddTrailMessage *add_trail;
5530 const struct GNUNET_PeerIdentity *trail;
5531 struct GNUNET_HashCode trail_id;
5532 struct GNUNET_PeerIdentity destination_peer;
5533 struct GNUNET_PeerIdentity source_peer;
5534 struct GNUNET_PeerIdentity next_hop;
5535 unsigned int trail_length;
5536 unsigned int my_index;
5539 msize = ntohs (message->size);
5540 /* In this message we pass the whole trail from source to destination as we
5541 * are adding that trail.*/
5542 //FIXME: failed when run with 1000 pears. check why.
5543 if (msize < sizeof (struct PeerAddTrailMessage))
5545 GNUNET_break_op (0);
5549 add_trail = (const struct PeerAddTrailMessage *) message;
5550 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5551 sizeof (struct GNUNET_PeerIdentity);
5552 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5553 sizeof (struct GNUNET_PeerIdentity) != 0)
5555 GNUNET_break_op (0);
5559 GNUNET_STATISTICS_update (GDS_stats,
5561 ("# Bytes received from other peers"), msize,
5564 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5565 destination_peer = add_trail->destination_peer;
5566 source_peer = add_trail->source_peer;
5567 trail_id = add_trail->trail_id;
5569 //FIXME: add a check that sender peer is not malicious. Make it a generic
5570 // function so that it can be used in all other functions where we need the
5571 // same functionality.
5573 /* I am not the destination of the trail. */
5574 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5576 struct FriendInfo *target_friend;
5578 /* Get my location in the trail. */
5579 my_index = search_my_index (trail, trail_length);
5582 GNUNET_break_op (0);
5583 return GNUNET_SYSERR;
5586 if ((trail_length - 1) == my_index)
5588 next_hop = destination_peer;
5592 next_hop = trail[my_index + 1];
5595 /* Add in your routing table. */
5596 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5597 GNUNET_assert (NULL !=
5599 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5600 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5601 trail, trail_length, target_friend);
5604 /* I am the destination. Add an entry in routing table. */
5605 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5611 * Free the finger trail in which the first friend to reach to a finger is
5612 * disconnected_friend. Also remove entry from routing table for that particular
5614 * @param disconnected_friend PeerIdentity of friend which got disconnected
5615 * @param remove_finger Finger whose trail we need to check if it has
5616 * disconnected_friend as the first hop.
5617 * @return Total number of trails in which disconnected_friend was the first
5621 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5622 struct FingerInfo *remove_finger)
5624 unsigned int matching_trails_count;
5627 /* Number of trails with disconnected_friend as the first hop in the trail
5628 * to reach from me to remove_finger, NOT including endpoints. */
5629 matching_trails_count = 0;
5631 /* Iterate over all the trails of finger. */
5632 for (i = 0; i < remove_finger->trails_count; i++)
5634 struct Trail *trail;
5635 trail = &remove_finger->trail_list[i];
5637 /* This assertion is ensure that there are no gaps in the trail list.
5638 REMOVE IT AFTERWARDS. */
5639 GNUNET_assert (GNUNET_YES == trail->is_present);
5641 /* First friend to reach to finger is disconnected_peer. */
5642 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5643 disconnected_friend))
5645 struct GNUNET_PeerIdentity *next_hop;
5646 struct FriendInfo *remove_friend;
5648 GNUNET_assert (NULL !=
5650 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5651 disconnected_friend)));
5652 /* FIXME: removing no but check it. */
5653 //remove_friend->trails_count--;
5654 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5655 GDS_ROUTING_SRC_TO_DEST);
5657 /* Here it may happen that as all the peers got disconnected, the entry in
5658 routing table for that particular trail has been removed, because the
5659 previously disconnected peer was either a next hop or prev hop of that
5661 if (NULL == next_hop)
5664 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5666 matching_trails_count++;
5667 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5670 trail->is_present = GNUNET_NO;
5673 return matching_trails_count;
5678 * Iterate over finger_table entries.
5679 * 0. Ignore finger which is my_identity or if no valid entry present at
5680 * that finger index.
5681 * 1. If disconnected_friend is a finger, then remove the routing entry from
5682 your own table. Free the trail.
5683 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5684 * 2.1 Remove all the trails and entry from routing table in which disconnected
5685 * friend is the first friend in the trail. If disconnected_friend is the
5686 * first friend in all the trails to reach finger, then remove the finger.
5687 * @param disconnected_friend Peer identity of friend which got disconnected.
5690 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5692 struct FingerInfo *remove_finger;
5693 struct FriendInfo *remove_friend;
5694 int removed_trails_count;
5697 /* Iterate over finger table entries. */
5698 for (i = 0; i < MAX_FINGERS; i++)
5700 remove_finger = &finger_table[i];
5702 /* No finger stored at this trail index. */
5703 if (GNUNET_NO == remove_finger->is_present)
5706 /* I am my own finger, then ignore this finger. */
5707 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5711 /* Is disconnected_peer a finger? */
5712 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5713 &remove_finger->finger_identity))
5715 struct GNUNET_PeerIdentity *next_hop;
5716 struct GNUNET_HashCode trail_id;
5719 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5720 trail_id = remove_finger->trail_list[0].trail_id;
5724 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5727 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5728 &remove_finger->finger_identity)));
5729 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5730 GNUNET_assert (NULL !=
5732 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5733 disconnected_peer)));
5736 remove_finger->trail_list[0].is_present = GNUNET_NO;
5737 //GNUNET_assert (0 != remove_friend->trails_count);
5738 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5739 remove_finger->is_present = GNUNET_NO;
5740 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5744 /* If finger is a friend but not disconnected_friend, then continue. */
5745 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5746 &remove_finger->finger_identity))
5749 /* Iterate over the list of trails to reach remove_finger. Check if
5750 * disconnected_friend is the first friend in any of the trail. */
5751 removed_trails_count = remove_matching_trails (disconnected_peer,
5753 remove_finger->trails_count =
5754 remove_finger->trails_count - removed_trails_count;
5755 /* All the finger trails had disconnected_friend as the first friend,
5756 * so free the finger. */
5757 if (remove_finger->trails_count == 0)
5759 remove_finger->is_present = GNUNET_NO;
5760 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5767 * Method called whenever a peer disconnects.
5769 * @param cls closure
5770 * @param peer peer identity this notification is about
5773 handle_core_disconnect (void *cls,
5774 const struct GNUNET_PeerIdentity *peer)
5776 struct FriendInfo *remove_friend;
5778 /* If disconnected to own identity, then return. */
5779 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5782 GNUNET_assert (NULL != (remove_friend =
5783 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5785 /* Remove fingers with peer as first friend or if peer is a finger. */
5786 remove_matching_fingers (peer);
5788 /* Remove any trail from routing table of which peer is a part of. This function
5789 * internally sends a trail teardown message in the direction of which
5790 * disconnected peer is not part of. */
5791 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5793 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5795 /* Remove peer from friend_peermap. */
5796 GNUNET_assert (GNUNET_YES ==
5797 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5801 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5804 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5806 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5807 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5816 * Method called whenever a peer connects.
5818 * @param cls closure
5819 * @param peer_identity peer identity this notification is about
5822 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5824 struct FriendInfo *friend;
5826 /* Check for connect to self message */
5827 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5830 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5832 /* If peer already exists in our friend_peermap, then exit. */
5833 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5840 friend = GNUNET_new (struct FriendInfo);
5841 friend->id = *peer_identity;
5843 GNUNET_assert (GNUNET_OK ==
5844 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5845 peer_identity, friend,
5846 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5848 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5849 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5851 next_send_time.rel_value_us =
5852 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5853 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5854 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5855 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5861 * To be called on core init/fail.
5863 * @param cls service closure
5864 * @param identity the public identity of this peer
5867 core_init (void *cls,
5868 const struct GNUNET_PeerIdentity *identity)
5870 my_identity = *identity;
5873 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5874 my_id64 = GNUNET_ntohll (my_id64);
5875 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5876 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5882 * Initialize finger table entries.
5885 finger_table_init ()
5887 memset (&finger_table, 0, sizeof (finger_table));
5892 * Initialize neighbours subsystem.
5893 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5896 GDS_NEIGHBOURS_init (void)
5898 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5899 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5900 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5901 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5902 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5903 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5904 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5905 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5906 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5907 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5908 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5909 sizeof (struct PeerTrailCompressionMessage)},
5910 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5911 sizeof (struct PeerTrailTearDownMessage)},
5912 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5916 #if ENABLE_MALICIOUS
5921 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5922 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5923 GNUNET_NO, core_handlers);
5925 if (NULL == core_api)
5926 return GNUNET_SYSERR;
5928 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5929 finger_table_init ();
5935 * Free the memory held up by trails of a finger.
5938 delete_finger_table_entries()
5943 for(i = 0; i < MAX_FINGERS; i++)
5945 if(GNUNET_NO == finger_table[i].is_present)
5948 for(j = 0; j < finger_table[i].trails_count; j++)
5950 free_trail(&finger_table[i].trail_list[i]);
5956 * Shutdown neighbours subsystem.
5959 GDS_NEIGHBOURS_done (void)
5961 if (NULL == core_api)
5964 GNUNET_CORE_disconnect (core_api);
5967 delete_finger_table_entries();
5969 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5970 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5971 friend_peermap = NULL;
5973 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5976 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5977 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5980 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5982 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5983 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5991 * @return my identity
5993 struct GNUNET_PeerIdentity
5994 GDS_NEIGHBOURS_get_my_id (void)
5999 /* end of gnunet-service-xdht_neighbours.c */