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 * trail_length + 1 if an entry is present twice, It is an error.
1589 * -1 if no entry found.
1592 search_my_index (const struct GNUNET_PeerIdentity *trail,
1596 int index_seen = trail_length + 1;
1599 for (i = 0; i < trail_length; i++)
1601 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1604 if(index_seen == (trail_length + 1))
1608 DEBUG("Entry is present twice in trail. Its not allowed\n");
1622 * Check if the friend is congested or have reached maximum number of trails
1623 * it can be part of of.
1624 * @param friend Friend to be checked.
1625 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1626 * #GNUNET_YES if friend is either congested or have crossed threshold
1629 is_friend_congested (struct FriendInfo *friend)
1631 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1632 ((0 == GNUNET_TIME_absolute_get_remaining
1633 (friend->congestion_timestamp).rel_value_us)))
1641 * Select closest finger to value.
1642 * @param peer1 First peer
1643 * @param peer2 Second peer
1644 * @param value Value to be compare
1645 * @return Closest peer
1647 const static struct GNUNET_PeerIdentity *
1648 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1649 const struct GNUNET_PeerIdentity *peer2,
1652 uint64_t peer1_value;
1653 uint64_t peer2_value;
1655 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1656 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1657 peer1_value = GNUNET_ntohll (peer1_value);
1658 peer2_value = GNUNET_ntohll (peer2_value);
1660 if (peer1_value == value)
1665 if (peer2_value == value)
1670 if (peer2_value < peer1_value)
1672 if ((peer2_value < value) && (value < peer1_value))
1676 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1677 ((0 < value) && (value < peer2_value)))
1683 if (peer1_value < peer2_value)
1685 if ((peer1_value < value) && (value < peer2_value))
1689 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1690 ((0 < value) && (value < peer1_value)))
1700 * Select closest predecessor to value.
1701 * @param peer1 First peer
1702 * @param peer2 Second peer
1703 * @param value Value to be compare
1704 * @return Peer which precedes value in the network.
1706 const static struct GNUNET_PeerIdentity *
1707 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1708 const struct GNUNET_PeerIdentity *peer2,
1711 uint64_t peer1_value;
1712 uint64_t peer2_value;
1714 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1715 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1716 peer1_value = GNUNET_ntohll (peer1_value);
1717 peer2_value = GNUNET_ntohll (peer2_value);
1719 if (peer1_value == value)
1722 if (peer2_value == value)
1725 if (peer1_value < peer2_value)
1727 if ((peer1_value < value) && (value < peer2_value))
1731 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1732 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1738 if (peer2_value < peer1_value)
1740 if ((peer2_value < value) && (value < peer1_value))
1744 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1745 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1759 test_print_trail (struct GNUNET_PeerIdentity *trail,
1760 unsigned int trail_length)
1762 struct GNUNET_PeerIdentity print_peer;
1765 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1766 __FILE__, __func__,__LINE__,trail_length);
1767 for (i =0 ; i< trail_length; i++)
1769 print_peer = trail[i];
1770 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1771 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1778 * This is a test function to print all the entries of friend table.
1781 test_friend_peermap_print ()
1783 struct FriendInfo *friend;
1784 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1785 struct GNUNET_PeerIdentity print_peer;
1786 struct GNUNET_PeerIdentity key_ret;
1789 print_peer = my_identity;
1790 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1791 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1793 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1795 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1797 (const void **)&friend))
1799 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1800 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1801 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1809 * This is a test function, to print all the entries of finger table.
1812 test_finger_table_print()
1814 struct FingerInfo *finger;
1815 struct GNUNET_PeerIdentity print_peer;
1816 //struct Trail *trail;
1820 print_peer = my_identity;
1821 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1822 for (i = 0; i < MAX_FINGERS; i++)
1824 finger = &finger_table[i];
1826 if (GNUNET_NO == finger->is_present)
1829 print_peer = finger->finger_identity;
1830 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1831 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1834 for (j = 0; j < finger->trails_count; j++)
1836 trail = &finger->trail_list[j];
1837 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1838 struct Trail_Element *element;
1839 element = trail->trail_head;
1840 for (k = 0; k < trail->trail_length; k++)
1842 print_peer = element->peer;
1843 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1844 element = element->next;
1853 * Select the closest peer among two peers (which should not be same)
1854 * with respect to value and finger_table_index
1855 * NOTE: peer1 != peer2
1856 * @param peer1 First peer
1857 * @param peer2 Second peer
1858 * @param value Value relative to which we find the closest
1859 * @param is_predecessor Is value a predecessor or any other finger.
1860 * @return Closest peer among two peers.
1862 const static struct GNUNET_PeerIdentity *
1863 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1864 const struct GNUNET_PeerIdentity *peer2,
1866 unsigned int is_predecessor)
1868 if (1 == is_predecessor)
1869 return select_closest_predecessor (peer1, peer2, value);
1871 return select_closest_finger (peer1, peer2, value);
1876 * Iterate over the list of all the trails of a finger. In case the first
1877 * friend to reach the finger has reached trail threshold or is congested,
1878 * then don't select it. In case there multiple available good trails to reach
1879 * to Finger, choose the one with shortest trail length.
1880 * Note: We use length as parameter. But we can use any other suitable parameter
1882 * @param finger Finger
1883 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1884 * and trail length. NULL in case none of the trails are free.
1886 static struct Selected_Finger_Trail *
1887 select_finger_trail (struct FingerInfo *finger)
1889 struct FriendInfo *friend;
1890 struct Trail *iterator;
1891 struct Selected_Finger_Trail *finger_trail;
1893 unsigned int flag = 0;
1896 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1897 GNUNET_assert (finger->trails_count > 0);
1899 for (i = 0; i < finger->trails_count; i++)
1901 iterator = &finger->trail_list[i];
1903 /* No trail stored at this index. */
1904 if (GNUNET_NO == iterator->is_present)
1907 GNUNET_assert (NULL !=
1909 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1910 &iterator->trail_head->peer)));
1912 /* First friend to reach trail is not free. */
1913 if (GNUNET_YES == is_friend_congested (friend))
1922 finger_trail->trail_length = iterator->trail_length;
1923 finger_trail->friend = *friend;
1924 finger_trail->trail_id = iterator->trail_id;
1926 else if (finger_trail->trail_length > iterator->trail_length)
1928 finger_trail->friend = *friend;
1929 finger_trail->trail_id = iterator->trail_id;
1930 finger_trail->trail_length = iterator->trail_length;
1934 /* All the first friend in all the trails to reach to finger are either
1935 congested or have crossed trail threshold. */
1936 if (j == finger->trails_count)
1939 return finger_trail;
1944 * Compare FINGER entry with current successor. If finger's first friend of all
1945 * its trail is not congested and has not crossed trail threshold, then check
1946 * if finger peer identity is closer to final_destination_finger_value than
1947 * current_successor. If yes then update current_successor.
1948 * @param current_successor[in/out]
1952 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1954 struct FingerInfo *finger;
1955 const struct GNUNET_PeerIdentity *closest_peer;
1956 struct Selected_Finger_Trail *finger_trail;
1959 /* Iterate over finger table. */
1960 for (i = 0; i < MAX_FINGERS; i++)
1962 finger = &finger_table[i];
1964 if (GNUNET_NO == finger->is_present)
1967 /* FIXME write correct comment here */
1968 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1969 ¤t_closest_peer->best_known_destination))
1972 /* If I am my own finger, then ignore this finger. */
1973 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1976 /* FIXME: I think a peer should not select itself as its own identity ever.
1977 But it does select. Find out why??*/
1983 /* If finger is a friend, then do nothing. As we have already checked
1984 * for each friend in compare_friend_and_current_successor(). */
1985 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1986 &finger->finger_identity)))
1991 closest_peer = select_closest_peer (&finger->finger_identity,
1992 ¤t_closest_peer->best_known_destination,
1993 current_closest_peer->destination_finger_value,
1994 current_closest_peer->is_predecessor);
1996 if (&finger->finger_identity == closest_peer)
1998 /* Choose one of the trail to reach to finger. */
1999 finger_trail = select_finger_trail (finger);
2001 /* In case no trail found, ignore this finger. */
2002 if (NULL == finger_trail)
2005 current_closest_peer->best_known_destination = finger->finger_identity;
2006 current_closest_peer->next_hop = finger_trail->friend.id;
2007 current_closest_peer->trail_id = finger_trail->trail_id;
2008 GNUNET_free(finger_trail);
2016 * Compare friend entry with current successor.
2017 * If friend identity and current_successor is same, then do nothing.
2018 * If friend is not congested and has not crossed trail threshold, then check
2019 * if friend peer identity is closer to final_destination_finger_value than
2020 * current_successor. If yes then update current_successor.
2021 * @param cls closure
2022 * @param key current public key
2023 * @param value struct Closest_Peer
2024 * @return #GNUNET_YES if we should continue to iterate,
2025 * #GNUNET_NO if not.
2028 compare_friend_and_current_closest_peer (void *cls,
2029 const struct GNUNET_PeerIdentity *key,
2032 struct FriendInfo *friend = value;
2033 struct Closest_Peer *current_closest_peer = cls;
2034 const struct GNUNET_PeerIdentity *closest_peer;
2036 /* Friend is either congested or has crossed threshold. */
2037 if (GNUNET_YES == is_friend_congested (friend))
2040 /* If current_closest_peer and friend identity are same, then do nothing.*/
2041 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2042 ¤t_closest_peer->best_known_destination))
2048 closest_peer = select_closest_peer (&friend->id,
2049 ¤t_closest_peer->best_known_destination,
2050 current_closest_peer->destination_finger_value,
2051 current_closest_peer->is_predecessor);
2053 /* Is friend the closest successor? */
2054 if (&friend->id == closest_peer)
2056 current_closest_peer->best_known_destination = friend->id;
2057 current_closest_peer->next_hop = friend->id;
2065 * Initialize current_successor to my_identity.
2066 * @param my_identity My peer identity
2067 * @return Updated closest_peer
2069 static struct Closest_Peer
2070 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2071 uint64_t destination_finger_value,
2072 unsigned int is_predecessor)
2074 struct Closest_Peer current_closest_peer;
2076 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2077 current_closest_peer.destination_finger_value = destination_finger_value;
2078 current_closest_peer.is_predecessor = is_predecessor;
2079 current_closest_peer.next_hop = my_identity;
2080 current_closest_peer.best_known_destination = my_identity;
2082 return current_closest_peer;
2087 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2088 * peer. It could be because of the logic we wrote here. Verify if its correct.
2089 * If not then return immediate_successor.
2091 * Find the successor for destination_finger_value among my_identity, my
2092 * friends and my fingers. Don't consider friends or fingers which are either
2093 * congested or have crossed the threshold.
2094 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2096 * @param destination_finger_value Peer closest to this value will be the next successor.
2097 * @param is_predecessor Are we looking for predecessor or finger?
2098 * @return Successor It is never NULL, in case none of friend or finger is closest,
2099 * then we return my_identity.
2101 static struct Closest_Peer
2102 find_successor (uint64_t destination_finger_value,
2103 unsigned int is_predecessor)
2105 struct Closest_Peer current_closest_peer;
2107 /* Initialize current_successor to my_identity. */
2108 current_closest_peer = init_current_successor (my_identity,
2109 destination_finger_value,
2112 /* Compare each friend entry with current_successor and update current_successor
2113 * with friend if its closest. */
2116 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2117 &compare_friend_and_current_closest_peer,
2118 ¤t_closest_peer));
2120 /* Compare each finger entry with current_successor and update current_successor
2121 * with finger if its closest. */
2122 compare_finger_and_current_successor (¤t_closest_peer);
2124 return current_closest_peer;
2129 * FIXME; Send put message across all the trail to reach to next hop to handle
2131 * Construct a Put message and send it to target_peer.
2132 * @param key Key for the content
2133 * @param block_type Type of the block
2134 * @param options Routing options
2135 * @param desired_replication_level Desired replication count
2136 * @param best_known_dest Peer to which this message should reach eventually,
2137 * as it is best known destination to me.
2138 * @param intermediate_trail_id Trail id in case
2139 * @param target_peer Peer to which this message will be forwarded.
2140 * @param hop_count Number of hops traversed so far.
2141 * @param put_path_length Total number of peers in @a put_path
2142 * @param put_path Number of peers traversed so far
2143 * @param expiration_time When does the content expire
2144 * @param data Content to store
2145 * @param data_size Size of content @a data in bytes
2148 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2149 enum GNUNET_BLOCK_Type block_type,
2150 enum GNUNET_DHT_RouteOption options,
2151 uint32_t desired_replication_level,
2152 struct GNUNET_PeerIdentity best_known_dest,
2153 struct GNUNET_HashCode intermediate_trail_id,
2154 struct GNUNET_PeerIdentity *target_peer,
2156 uint32_t put_path_length,
2157 struct GNUNET_PeerIdentity *put_path,
2158 struct GNUNET_TIME_Absolute expiration_time,
2159 const void *data, size_t data_size)
2161 struct PeerPutMessage *ppm;
2162 struct P2PPendingMessage *pending;
2163 struct FriendInfo *target_friend;
2164 struct GNUNET_PeerIdentity *pp;
2165 struct GNUNET_PeerIdentity next_hop;
2169 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2170 sizeof (struct PeerPutMessage);
2172 #if ENABLE_MALICIOUS
2173 /*Call is made to this function from
2175 2. Every peer to construct a pending message and send it to next peer.
2176 In case of 2nd, this case should have been handled in handle_dht_p2p_put/get
2177 No need to check here. First peer can never be malicious. IDEALLY we DONOT
2178 need the condition here. REMOVE IT AFTERWARDS once verified.*/
2179 if(1 == act_malicious)
2184 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2186 put_path_length = 0;
2187 msize = data_size + sizeof (struct PeerPutMessage);
2190 /* Should it be GNUNET_SERVER_MAX_MESSAGE_SIZE? */
2191 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2193 DEBUG("msize = %lu\n",msize);
2198 /* This is the first call made from clients file. So, we should search for the
2200 if (NULL == target_peer)
2203 struct Closest_Peer successor;
2205 memcpy (&key_value, key, sizeof (uint64_t));
2206 key_value = GNUNET_ntohll (key_value);
2208 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2209 best_known_dest = successor.best_known_destination;
2210 next_hop = successor.next_hop;
2211 intermediate_trail_id = successor.trail_id;
2213 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2215 /* I am the destination. */
2216 DEBUG("PUT destination is me = %s,key =%s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2217 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2218 block_type,data_size,data);
2222 GNUNET_assert (NULL !=
2224 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2228 GNUNET_assert (NULL !=
2230 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2233 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2234 pending->timeout = expiration_time;
2235 ppm = (struct PeerPutMessage *) &pending[1];
2236 pending->msg = &ppm->header;
2237 ppm->header.size = htons (msize);
2238 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2239 ppm->options = htonl (options);
2240 ppm->block_type = htonl (block_type);
2241 ppm->hop_count = htonl (hop_count + 1);
2242 ppm->desired_replication_level = htonl (desired_replication_level);
2243 ppm->put_path_length = htonl (put_path_length);
2244 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2245 ppm->best_known_destination = best_known_dest;
2248 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2249 if (put_path_length != 0)
2251 memcpy (pp, put_path,
2252 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2254 memcpy (&pp[put_path_length], data, data_size);
2255 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2256 target_friend->pending_count++;
2257 process_friend_queue (target_friend);
2262 * FIXME; Send get message across all the trail to reach to next hop to handle
2264 * Construct a Get message and send it to target_peer.
2265 * @param key Key for the content
2266 * @param block_type Type of the block
2267 * @param options Routing options
2268 * @param desired_replication_level Desired replication count
2269 * @param best_known_dest Peer which should get this message. Same as target peer
2270 * if best_known_dest is a friend else its a finger.
2271 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2272 * in case it is a finger else set to 0.
2273 * @param target_peer Peer to which this message will be forwarded.
2274 * @param hop_count Number of hops traversed so far.
2275 * @param data Content to store
2276 * @param data_size Size of content @a data in bytes
2277 * @param get_path_length Total number of peers in @a get_path
2278 * @param get_path Number of peers traversed so far
2281 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2282 enum GNUNET_BLOCK_Type block_type,
2283 enum GNUNET_DHT_RouteOption options,
2284 uint32_t desired_replication_level,
2285 struct GNUNET_PeerIdentity best_known_dest,
2286 struct GNUNET_HashCode intermediate_trail_id,
2287 struct GNUNET_PeerIdentity *target_peer,
2289 uint32_t get_path_length,
2290 struct GNUNET_PeerIdentity *get_path)
2292 struct PeerGetMessage *pgm;
2293 struct P2PPendingMessage *pending;
2294 struct FriendInfo *target_friend;
2295 struct GNUNET_PeerIdentity *gp;
2298 msize = sizeof (struct PeerGetMessage) +
2299 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2301 #if ENABLE_MALICIOUS
2302 if(1 == act_malicious)
2307 //GNUNET_SERVER_MAX_MESSAGE_SIZE
2308 /* FIXME:TODO:URGENTHere you can try to optimize it a bit. In case the get path contains you
2309 or your friend then shorten the path. */
2310 /* In this case we don't make get_path_length = 0, as we need get path to
2311 * return the message back to querying client. */
2312 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2318 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
2320 /* This is the first time we got request from our own client file. */
2321 if (NULL == target_peer)
2324 struct Closest_Peer successor;
2326 memcpy (&key_value, key, sizeof (uint64_t));
2327 key_value = GNUNET_ntohll (key_value);
2328 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2330 best_known_dest = successor.best_known_destination;
2331 intermediate_trail_id = successor.trail_id;
2333 /* I am the destination. I have the data. */
2334 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2337 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2338 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2339 NULL, 0, 1, &my_identity, NULL,&my_identity);
2345 GNUNET_assert (NULL !=
2347 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2348 &successor.next_hop)));
2354 GNUNET_assert (NULL !=
2356 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2359 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2360 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2361 pending->importance = 0; /* FIXME */
2362 pgm = (struct PeerGetMessage *) &pending[1];
2363 pending->msg = &pgm->header;
2364 pgm->header.size = htons (msize);
2365 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2366 pgm->get_path_length = htonl (get_path_length);
2367 pgm->best_known_destination = best_known_dest;
2369 pgm->intermediate_trail_id = intermediate_trail_id;
2370 pgm->hop_count = htonl (hop_count + 1);
2371 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2373 if (get_path_length != 0)
2375 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2378 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2379 target_friend->pending_count++;
2380 process_friend_queue (target_friend);
2385 * Send the get result to requesting client.
2386 * @param key Key of the requested data.
2387 * @param type Block type
2388 * @param target_peer Next peer to forward the message to.
2389 * @param source_peer Peer which has the data for the key.
2390 * @param put_path_length Number of peers in @a put_path
2391 * @param put_path Path taken to put the data at its stored location.
2392 * @param get_path_length Number of peers in @a get_path
2393 * @param get_path Path taken to reach to the location of the key.
2394 * @param expiration When will this result expire?
2395 * @param data Payload to store
2396 * @param data_size Size of the @a data
2399 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2400 enum GNUNET_BLOCK_Type type,
2401 const struct GNUNET_PeerIdentity *target_peer,
2402 const struct GNUNET_PeerIdentity *source_peer,
2403 unsigned int put_path_length,
2404 const struct GNUNET_PeerIdentity *put_path,
2405 unsigned int get_path_length,
2406 const struct GNUNET_PeerIdentity *get_path,
2407 struct GNUNET_TIME_Absolute expiration,
2408 const void *data, size_t data_size)
2410 struct PeerGetResultMessage *get_result;
2411 struct GNUNET_PeerIdentity *paths;
2412 struct P2PPendingMessage *pending;
2413 struct FriendInfo *target_friend;
2414 int current_path_index;
2417 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2419 sizeof (struct PeerGetResultMessage);
2421 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2423 put_path_length = 0;
2424 msize = msize - put_path_length;
2428 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2433 DEBUG("GET RESULT FOR DATA_SIZE = %lu\n",msize);
2434 current_path_index = 0;
2435 if(get_path_length > 0)
2437 current_path_index = search_my_index(get_path, get_path_length);
2438 if (-1 == current_path_index)
2443 if ((get_path_length + 1) == current_path_index)
2445 DEBUG ("Peer found twice in get path. Not allowed \n");
2450 if (0 == current_path_index)
2452 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2453 get_path, put_path_length,
2454 put_path, type, data_size, data);
2458 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2459 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2460 pending->importance = 0;
2461 get_result = (struct PeerGetResultMessage *)&pending[1];
2462 pending->msg = &get_result->header;
2463 get_result->header.size = htons (msize);
2464 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2465 get_result->key = *key;
2466 get_result->querying_peer = *source_peer;
2467 get_result->expiration_time = expiration;
2468 get_result->get_path_length = htonl (get_path_length);
2469 get_result->put_path_length = htonl (put_path_length);
2470 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2471 memcpy (paths, put_path,
2472 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2473 memcpy (&paths[put_path_length], get_path,
2474 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2475 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2477 GNUNET_assert (NULL !=
2479 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2480 &get_path[current_path_index - 1])));
2481 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2482 target_friend->pending_count++;
2483 process_friend_queue (target_friend);
2488 * Randomly choose one of your friends (which is not congested and have not crossed
2489 * trail threshold) from the friend_peermap
2490 * @return Friend Randomly chosen friend.
2491 * NULL in case friend peermap is empty, or all the friends are either
2492 * congested or have crossed trail threshold.
2494 static struct FriendInfo *
2495 select_random_friend ()
2497 unsigned int current_size;
2500 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2501 struct GNUNET_PeerIdentity key_ret;
2502 struct FriendInfo *friend;
2504 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2507 if (0 == current_size)
2510 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2511 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2513 /* Iterate till you don't reach to index. */
2514 for (j = 0; j < index ; j++)
2515 GNUNET_assert (GNUNET_YES ==
2516 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2519 /* Reset the index in friend peermap to 0 as we reached to the end. */
2520 if (j == current_size)
2523 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2524 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2528 /* Get the friend stored at the index, j*/
2529 GNUNET_assert (GNUNET_YES ==
2530 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2532 (const void **)&friend));
2534 /* This friend is not congested and has not crossed trail threshold. */
2535 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2536 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2542 } while (j != index);
2544 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2550 * Compute 64 bit value of finger_identity corresponding to a finger index using
2552 * For all fingers, n.finger[i] = n + pow (2,i),
2553 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2554 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2555 * @param finger_index Index corresponding to which we calculate 64 bit value.
2556 * @return 64 bit value.
2559 compute_finger_identity_value (unsigned int finger_index)
2563 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2564 my_id64 = GNUNET_ntohll (my_id64);
2566 /* Are we looking for immediate predecessor? */
2567 if (PREDECESSOR_FINGER_ID == finger_index)
2568 return (my_id64 - 1);
2571 uint64_t add = (uint64_t)1 << finger_index;
2572 return (my_id64 + add);
2576 static struct GNUNET_TIME_Relative next_send_time;
2579 * Choose a random friend. Calculate the next finger identity to search,from
2580 * current_search_finger_index. Start looking for the trail to reach to
2581 * finger identity through this random friend.
2583 * @param cls closure for this task
2584 * @param tc the context under which the task is running
2587 send_find_finger_trail_message (void *cls,
2588 const struct GNUNET_SCHEDULER_TaskContext *tc)
2590 struct FriendInfo *target_friend;
2591 //struct GNUNET_TIME_Relative next_send_time;
2592 struct GNUNET_HashCode trail_id;
2593 struct GNUNET_HashCode intermediate_trail_id;
2594 unsigned int is_predecessor;
2595 uint64_t finger_id_value;
2597 /* Schedule another send_find_finger_trail_message task. */
2598 find_finger_trail_task =
2599 GNUNET_SCHEDULER_add_delayed (next_send_time,
2600 &send_find_finger_trail_message,
2603 /* No space in my routing table. (Source and destination peers also store entries
2604 * in their routing table). */
2605 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2609 target_friend = select_random_friend ();
2610 if (NULL == target_friend)
2615 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2617 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2622 /* Generate a unique trail id for trail we are trying to setup. */
2623 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2624 &trail_id, sizeof (trail_id));
2625 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2627 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2628 target_friend->id, target_friend, 0, NULL,
2629 is_predecessor, trail_id,
2630 intermediate_trail_id);
2635 * In case there are already maximum number of possible trails to reach to a
2636 * finger, then check if the new trail's length is lesser than any of the
2638 * If yes then replace that old trail by new trail.
2640 * Note: Here we are taking length as a parameter to choose the best possible
2641 * trail, but there could be other parameters also like:
2642 * 1. duration of existence of a trail - older the better.
2643 * 2. if the new trail is completely disjoint than the
2644 * other trails, then may be choosing it is better.
2646 * @param existing_finger
2647 * @param new_finger_trail
2648 * @param new_finger_trail_length
2649 * @param new_finger_trail_id
2652 select_and_replace_trail (struct FingerInfo *existing_finger,
2653 const struct GNUNET_PeerIdentity *new_trail,
2654 unsigned int new_trail_length,
2655 struct GNUNET_HashCode new_trail_id)
2657 struct Trail *trail_list_iterator;
2658 unsigned int largest_trail_length;
2659 unsigned int largest_trail_index;
2660 struct Trail_Element *trail_element;
2663 largest_trail_length = new_trail_length;
2664 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2666 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2668 for (i = 0; i < existing_finger->trails_count; i++)
2670 trail_list_iterator = &existing_finger->trail_list[i];
2671 if (trail_list_iterator->trail_length > largest_trail_length)
2673 largest_trail_length = trail_list_iterator->trail_length;
2674 largest_trail_index = i;
2678 /* New trail is not better than existing ones. Send trail teardown. */
2679 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2681 struct GNUNET_PeerIdentity next_hop;
2683 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2684 GDS_ROUTING_remove_trail (new_trail_id);
2685 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2686 GDS_ROUTING_SRC_TO_DEST,
2691 /* Send trail teardown message across the replaced trail. */
2692 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2693 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2694 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2695 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2696 GDS_ROUTING_SRC_TO_DEST,
2697 replace_trail->trail_head->peer);
2698 /* Free the trail. */
2699 while (NULL != (trail_element = replace_trail->trail_head))
2701 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2702 replace_trail->trail_tail, trail_element);
2703 GNUNET_free_non_null (trail_element);
2706 /* Add new trial at that location. */
2707 replace_trail->is_present = GNUNET_YES;
2708 replace_trail->trail_length = new_trail_length;
2709 replace_trail->trail_id = new_trail_id;
2710 //FIXME: Do we need to add pointers for head and tail.
2712 while (i < new_trail_length)
2714 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2715 element->peer = new_trail[i];
2717 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2718 replace_trail->trail_tail,
2725 * Check if the new trail to reach to finger is unique or do we already have
2726 * such a trail present for finger.
2727 * @param existing_finger Finger identity
2728 * @param new_trail New trail to reach @a existing_finger
2729 * @param trail_length Total number of peers in new_trail.
2730 * @return #GNUNET_YES if the new trail is unique
2731 * #GNUNET_NO if same trail is already present.
2734 is_new_trail_unique (struct FingerInfo *existing_finger,
2735 const struct GNUNET_PeerIdentity *new_trail,
2736 unsigned int trail_length)
2738 struct Trail *trail_list_iterator;
2739 struct Trail_Element *trail_element;
2742 int trail_unique = GNUNET_NO;
2744 GNUNET_assert (existing_finger->trails_count > 0);
2746 /* Iterate over list of trails. */
2747 for (i = 0; i < existing_finger->trails_count; i++)
2749 trail_list_iterator = &existing_finger->trail_list[i];
2750 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2752 /* New trail and existing trail length are not same. */
2753 if (trail_list_iterator->trail_length != trail_length)
2755 trail_unique = GNUNET_YES;
2759 trail_element = trail_list_iterator->trail_head;
2760 for (j = 0; j < trail_list_iterator->trail_length; j++)
2762 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2763 &trail_element->peer))
2765 trail_unique = GNUNET_YES;
2768 trail_element = trail_element->next;
2771 trail_unique = GNUNET_NO;
2774 return trail_unique;
2779 * Add a new trail to existing finger. This function is called only when finger
2780 * is not my own identity or a friend.
2781 * @param existing_finger Finger
2782 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2783 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2784 * @param new_finger_trail_id Unique identifier of the trail.
2787 add_new_trail (struct FingerInfo *existing_finger,
2788 const struct GNUNET_PeerIdentity *new_trail,
2789 unsigned int new_trail_length,
2790 struct GNUNET_HashCode new_trail_id)
2792 struct Trail *trail_list_iterator;
2793 struct FriendInfo *first_friend;
2796 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2802 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2803 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2804 trail_list_iterator->trail_id = new_trail_id;
2805 trail_list_iterator->trail_length = new_trail_length;
2806 existing_finger->trails_count++;
2807 trail_list_iterator->is_present = GNUNET_YES;
2809 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2810 &existing_finger->finger_identity)));
2811 /* If finger is a friend then we never call this function. */
2812 GNUNET_assert (new_trail_length > 0);
2814 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2816 first_friend->trails_count++;
2818 for (i = 0; i < new_trail_length; i++)
2820 struct Trail_Element *element;
2822 element = GNUNET_new (struct Trail_Element);
2823 element->peer = new_trail[i];
2824 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2825 trail_list_iterator->trail_tail,
2828 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2834 * FIXME Check if this function is called for opposite direction if yes then
2835 * take it as parameter.
2836 * Get the next hop to send trail teardown message from routing table and
2837 * then delete the entry from routing table. Send trail teardown message for a
2838 * specific trail of a finger.
2839 * @param finger Finger whose trail is to be removed.
2840 * @param trail List of peers in trail from me to a finger, NOT including
2844 send_trail_teardown (struct FingerInfo *finger,
2845 struct Trail *trail)
2847 struct FriendInfo *friend;
2848 struct GNUNET_PeerIdentity *next_hop;
2850 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2851 GDS_ROUTING_SRC_TO_DEST);
2853 if (NULL == next_hop)
2858 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2861 GNUNET_assert (trail->is_present == GNUNET_YES);
2863 /* Finger is not a friend. */
2864 if (trail->trail_length > 0)
2866 GNUNET_assert (NULL != (friend =
2867 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2868 &trail->trail_head->peer)));
2872 GNUNET_assert (NULL != (friend =
2873 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2874 &finger->finger_identity)));
2877 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2878 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2879 friend->trails_count--;
2880 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2881 GDS_ROUTING_SRC_TO_DEST,
2887 * Send trail teardown message across all the trails to reach to finger.
2888 * @param finger Finger whose all the trail should be freed.
2891 send_all_finger_trails_teardown (struct FingerInfo *finger)
2895 for (i = 0; i < finger->trails_count; i++)
2897 struct Trail *trail;
2899 trail = &finger->trail_list[i];
2900 GNUNET_assert (trail->is_present == GNUNET_YES);
2901 send_trail_teardown (finger, trail);
2902 trail->is_present = GNUNET_NO;
2908 * Free a specific trail
2909 * @param trail List of peers to be freed.
2912 free_trail (struct Trail *trail)
2914 struct Trail_Element *trail_element;
2916 while (NULL != (trail_element = trail->trail_head))
2918 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2921 GNUNET_free_non_null (trail_element);
2923 trail->trail_head = NULL;
2924 trail->trail_tail = NULL;
2929 * Free finger and its trail.
2930 * @param finger Finger to be freed.
2933 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2935 struct Trail *trail;
2938 /* Free all the trails to reach to finger */
2939 for (i = 0; i < finger->trails_count; i++)
2941 trail = &finger->trail_list[i];
2942 //FIXME: Check if there are any missing entry in this list because of
2943 // how we insert. If not then no need of this check.
2944 if (GNUNET_NO == trail->is_present)
2947 if (trail->trail_length > 0)
2951 trail->is_present = GNUNET_NO;
2954 finger->is_present = GNUNET_NO;
2955 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2960 * Add a new entry in finger table at finger_table_index.
2961 * In case I am my own finger, then we don't have a trail. In case of a friend,
2962 * we have a trail with unique id and '0' trail length.
2963 * In case a finger is a friend, then increment the trails count of the friend.
2964 * @param finger_identity Peer Identity of new finger
2965 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2966 * @param finger_trail_length Total number of peers in @a finger_trail.
2967 * @param trail_id Unique identifier of the trail.
2968 * @param finger_table_index Index in finger table.
2971 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2972 const struct GNUNET_PeerIdentity *finger_trail,
2973 unsigned int finger_trail_length,
2974 struct GNUNET_HashCode trail_id,
2975 unsigned int finger_table_index)
2977 struct FingerInfo *new_entry;
2978 struct FriendInfo *first_trail_hop;
2979 struct Trail *trail;
2982 new_entry = GNUNET_new (struct FingerInfo);
2983 new_entry->finger_identity = finger_identity;
2984 new_entry->finger_table_index = finger_table_index;
2985 new_entry->is_present = GNUNET_YES;
2987 /* If the new entry is my own identity. */
2988 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2991 new_entry->trails_count = 0;
2992 finger_table[finger_table_index] = *new_entry;
2993 GNUNET_free (new_entry);
2997 /* If finger is a friend, then we don't actually have a trail.
2998 * Just a trail id */
2999 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3002 new_entry->trail_list[0].trail_id = trail_id;
3003 new_entry->trails_count = 1;
3004 new_entry->trail_list[0].is_present = GNUNET_YES;
3005 new_entry->trail_list[0].trail_length = 0;
3006 new_entry->trail_list[0].trail_head = NULL;
3007 new_entry->trail_list[0].trail_tail = NULL;
3008 finger_table[finger_table_index] = *new_entry;
3009 GNUNET_assert (NULL !=
3011 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3012 &finger_identity)));
3014 first_trail_hop->trails_count++;
3015 GNUNET_free (new_entry);
3019 GNUNET_assert (NULL !=
3021 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3022 &finger_trail[0])));
3023 new_entry->trails_count = 1;
3024 first_trail_hop->trails_count++;
3026 /* Copy the finger trail into trail. */
3027 trail = GNUNET_new (struct Trail);
3028 while (i < finger_trail_length)
3030 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3032 element->next = NULL;
3033 element->prev = NULL;
3034 element->peer = finger_trail[i];
3035 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3041 /* Add trail to trail list. */
3042 new_entry->trail_list[0].trail_head = trail->trail_head;
3043 new_entry->trail_list[0].trail_tail = trail->trail_tail;
3044 new_entry->trail_list[0].trail_length = finger_trail_length;
3045 new_entry->trail_list[0].trail_id = trail_id;
3046 new_entry->trail_list[0].is_present = GNUNET_YES;
3047 finger_table[finger_table_index] = *new_entry;
3048 GNUNET_free (new_entry);
3054 * Scan the trail to check if there is any other friend in the trail other than
3055 * first hop. If yes then shortcut the trail, send trail compression message to
3056 * peers which are no longer part of trail and send back the updated trail
3057 * and trail_length to calling function.
3058 * @param finger_identity Finger whose trail we will scan.
3059 * @param finger_trail [in, out] Trail to reach from source to finger,
3060 * @param finger_trail_length Total number of peers in original finger_trail.
3061 * @param finger_trail_id Unique identifier of the finger trail.
3062 * @return updated trail length in case we shortcut the trail, else original
3065 static struct GNUNET_PeerIdentity *
3066 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
3067 const struct GNUNET_PeerIdentity *trail,
3068 unsigned int trail_length,
3069 struct GNUNET_HashCode trail_id,
3070 int *new_trail_length)
3072 struct FriendInfo *target_friend;
3073 struct GNUNET_PeerIdentity *new_trail;
3076 /* I am my own finger. */
3077 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3079 *new_trail_length = 0;
3083 if (0 == trail_length)
3085 *new_trail_length = 0;
3089 /* If finger identity is a friend. */
3090 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3092 *new_trail_length = 0;
3094 /* If there is trail to reach this finger/friend */
3095 if (trail_length > 0)
3097 /* Finger is your first friend. */
3098 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3099 GNUNET_assert (NULL !=
3101 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3105 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3106 trail_id, finger_identity,
3112 /* For other cases, when its neither a friend nor my own identity.*/
3113 for (i = trail_length - 1; i > 0; i--)
3115 /* If the element at this index in trail is a friend. */
3116 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3118 struct FriendInfo *target_friend;
3121 GNUNET_assert (NULL !=
3123 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3125 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3126 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3131 /* Copy the trail from index i to index (trail_length -1) into a new trail
3132 * and update new trail length */
3133 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3134 while (i < trail_length)
3136 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3140 *new_trail_length = j+1;
3145 /* If we did not compress the trail, return the original trail back.*/
3146 *new_trail_length = trail_length;
3147 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3148 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3154 * Periodic task to verify current successor. There can be multiple trails to reach
3155 * to successor, choose the shortest one and send verify successor message
3156 * across that trail.
3157 * @param cls closure for this task
3158 * @param tc the context under which the task is running
3161 send_verify_successor_message (void *cls,
3162 const struct GNUNET_SCHEDULER_TaskContext *tc)
3164 struct FriendInfo *target_friend;
3165 struct GNUNET_HashCode trail_id;
3167 struct GNUNET_TIME_Relative next_send_time;
3168 struct Trail *trail;
3169 struct Trail_Element *element;
3170 unsigned int trail_length;
3172 struct FingerInfo *successor;
3174 /* Schedule another send_find_finger_trail_message task. */
3175 next_send_time.rel_value_us =
3176 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3177 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3178 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3179 send_verify_successor_task =
3180 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3183 successor = &finger_table[0];
3184 for (i = 0; i < successor->trails_count; i++)
3186 trail = &successor->trail_list[i];
3187 if(GNUNET_YES == trail->is_present)
3191 if (i == successor->trails_count)
3194 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3195 &successor->finger_identity));
3197 /* Trail stored at this index. */
3198 GNUNET_assert (GNUNET_YES == trail->is_present);
3200 trail_id = trail->trail_id;
3201 trail_length = trail->trail_length;
3203 if (trail_length > 0)
3205 /* Copy the trail into peer list. */
3206 struct GNUNET_PeerIdentity peer_list[trail_length];
3208 element = trail->trail_head;
3209 while (j < trail_length)
3211 peer_list[j] = element->peer;
3212 element = element->next;
3216 GNUNET_assert (NULL != (target_friend =
3217 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3219 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3220 successor->finger_identity,
3221 trail_id, peer_list, trail_length,
3227 GNUNET_assert (NULL != (target_friend =
3228 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3229 &successor->finger_identity)));
3230 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3231 successor->finger_identity,
3240 * Update the current search finger index.
3242 * FIXME document parameters!
3245 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3246 unsigned int finger_table_index)
3248 struct FingerInfo *successor;
3250 /* FIXME correct this: only move current index periodically */
3251 if (finger_table_index != current_search_finger_index)
3254 successor = &finger_table[0];
3255 GNUNET_assert (GNUNET_YES == successor->is_present);
3257 /* We were looking for immediate successor. */
3258 if (0 == current_search_finger_index)
3260 /* Start looking for immediate predecessor. */
3261 current_search_finger_index = PREDECESSOR_FINGER_ID;
3263 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3265 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3266 send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3272 current_search_finger_index = current_search_finger_index - 1;
3278 * Get the least significant bit set in val.
3281 * @return Position of first bit set, 65 in case of error.
3284 find_set_bit (uint64_t val)
3304 return 65; /* Some other bit was set to 1 as well. */
3311 * Calculate finger_table_index from initial 64 bit finger identity value that
3312 * we send in trail setup message.
3313 * @param ultimate_destination_finger_value Value that we calculated from our
3314 * identity and finger_table_index.
3315 * @param is_predecessor Is the entry for predecessor or not?
3316 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3317 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3320 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3321 unsigned int is_predecessor)
3325 unsigned int finger_table_index;
3327 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3328 my_id64 = GNUNET_ntohll (my_id64);
3330 /* Is this a predecessor finger? */
3331 if (1 == is_predecessor)
3333 diff = my_id64 - ultimate_destination_finger_value;
3335 finger_table_index = PREDECESSOR_FINGER_ID;
3337 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3342 diff = ultimate_destination_finger_value - my_id64;
3343 finger_table_index = find_set_bit (diff);
3345 return finger_table_index;
3350 * Remove finger and its associated data structures from finger table.
3351 * @param finger Finger to be removed.
3354 remove_existing_finger (struct FingerInfo *existing_finger,
3355 unsigned int finger_table_index)
3357 struct FingerInfo *finger;
3359 finger = &finger_table[finger_table_index];
3360 GNUNET_assert (GNUNET_YES == finger->is_present);
3362 /* If I am my own finger, then we have no trails. */
3363 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3366 finger->is_present = GNUNET_NO;
3367 memset ((void *)&finger_table[finger_table_index], 0,
3368 sizeof (finger_table[finger_table_index]));
3372 /* For all other fingers, send trail teardown across all the trails to reach
3373 finger, and free the finger. */
3374 send_all_finger_trails_teardown (finger);
3375 free_finger (finger, finger_table_index);
3381 * Check if there is already an entry in finger_table at finger_table_index.
3382 * We get the finger_table_index from 64bit finger value we got from the network.
3383 * -- If yes, then select the closest finger.
3384 * -- If new and existing finger are same, then check if you can store more
3386 * -- If yes then add trail, else keep the best trails to reach to the
3388 * -- If the new finger is closest, remove the existing entry, send trail
3389 * teardown message across all the trails to reach the existing entry.
3390 * Add the new finger.
3391 * -- If new and existing finger are different, and existing finger is closest
3393 * -- Update current_search_finger_index.
3394 * @param finger_identity Peer Identity of new finger
3395 * @param finger_trail Trail to reach the new finger
3396 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3397 * @param is_predecessor Is this entry for predecessor in finger_table?
3398 * @param finger_value 64 bit value of finger identity that we got from network.
3399 * @param finger_trail_id Unique identifier of @finger_trail.
3402 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3403 const struct GNUNET_PeerIdentity *finger_trail,
3404 unsigned int finger_trail_length,
3405 unsigned int is_predecessor,
3406 uint64_t finger_value,
3407 struct GNUNET_HashCode finger_trail_id)
3409 struct FingerInfo *existing_finger;
3410 const struct GNUNET_PeerIdentity *closest_peer;
3411 struct FingerInfo *successor;
3412 int updated_finger_trail_length;
3413 unsigned int finger_table_index;
3415 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3416 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3418 /* Invalid finger_table_index. */
3419 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3421 GNUNET_break_op (0);
3425 /* New entry same as successor. */
3426 if ((0 != finger_table_index) &&
3427 (PREDECESSOR_FINGER_ID != finger_table_index))
3429 successor = &finger_table[0];
3430 if (GNUNET_NO == successor->is_present)
3432 GNUNET_break_op (0);
3435 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3436 &successor->finger_identity))
3438 current_search_finger_index = 0;
3439 /* We slow down the find_finger_trail_task as we have completed the circle. */
3440 next_send_time = GNUNET_TIME_STD_BACKOFF(next_send_time);
3445 struct FingerInfo prev_finger;
3446 prev_finger = finger_table[finger_table_index - 1];
3447 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3448 &prev_finger.finger_identity))
3450 current_search_finger_index--;
3455 existing_finger = &finger_table[finger_table_index];
3457 /* No entry present in finger_table for given finger map index. */
3458 if (GNUNET_NO == existing_finger->is_present)
3460 struct GNUNET_PeerIdentity *updated_trail;
3462 /* Shorten the trail if possible. */
3463 updated_finger_trail_length = finger_trail_length;
3464 updated_trail = scan_and_compress_trail (finger_identity, finger_trail,
3465 finger_trail_length,
3467 &updated_finger_trail_length);
3468 add_new_finger (finger_identity, updated_trail,
3469 updated_finger_trail_length,
3470 finger_trail_id, finger_table_index);
3471 GNUNET_free_non_null(updated_trail);
3472 update_current_search_finger_index (finger_identity,
3473 finger_table_index);
3478 /* If existing entry and finger identity are not same. */
3479 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3482 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3487 /* If the new finger is the closest peer. */
3488 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3490 struct GNUNET_PeerIdentity *updated_trail;
3491 /* Shorten the trail if possible. */
3492 updated_finger_trail_length = finger_trail_length;
3494 scan_and_compress_trail (finger_identity, finger_trail,
3495 finger_trail_length, finger_trail_id,
3496 &updated_finger_trail_length);
3497 remove_existing_finger (existing_finger, finger_table_index);
3498 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3499 finger_trail_id, finger_table_index);
3500 GNUNET_free_non_null((struct GNUNET_PeerIdentity *)updated_trail);
3504 /* Existing finger is the closest one. We need to send trail teardown
3505 across the trail setup in routing table of all the peers. */
3506 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3508 if (finger_trail_length > 0)
3509 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3510 GDS_ROUTING_SRC_TO_DEST,
3513 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3514 GDS_ROUTING_SRC_TO_DEST,
3521 /* If both new and existing entry are same as my_identity, then do nothing. */
3522 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3527 /* If the existing finger is not a friend. */
3529 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3530 &existing_finger->finger_identity))
3532 struct GNUNET_PeerIdentity *updated_trail;
3534 /* Shorten the trail if possible. */
3535 updated_finger_trail_length = finger_trail_length;
3537 scan_and_compress_trail (finger_identity, finger_trail,
3538 finger_trail_length, finger_trail_id,
3539 &updated_finger_trail_length);
3540 /* If there is space to store more trails. */
3541 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3542 add_new_trail (existing_finger, updated_trail,
3543 updated_finger_trail_length, finger_trail_id);
3545 select_and_replace_trail (existing_finger, updated_trail,
3546 updated_finger_trail_length, finger_trail_id);
3550 update_current_search_finger_index (finger_identity, finger_table_index);
3556 * FIXME: Check for loop in the request. If you already are part of put path,
3557 * then you need to reset the put path length.
3558 * Core handler for P2P put messages.
3559 * @param cls closure
3560 * @param peer sender of the request
3561 * @param message message
3562 * @return #GNUNET_OK to keep the connection open,
3563 * #GNUNET_SYSERR to close it (signal serious error)
3566 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3567 const struct GNUNET_MessageHeader *message)
3569 struct PeerPutMessage *put;
3570 struct GNUNET_PeerIdentity *put_path;
3571 struct GNUNET_PeerIdentity best_known_dest;
3572 struct GNUNET_HashCode intermediate_trail_id;
3573 struct GNUNET_PeerIdentity *next_hop;
3574 enum GNUNET_DHT_RouteOption options;
3575 struct GNUNET_HashCode test_key;
3579 size_t payload_size;
3582 #if ENABLE_MALICIOUS
3583 if(1 == act_malicious)
3585 DEBUG("I am malicious,dropping put request. \n");
3590 msize = ntohs (message->size);
3591 if (msize < sizeof (struct PeerPutMessage))
3593 GNUNET_break_op (0);
3597 put = (struct PeerPutMessage *) message;
3598 putlen = ntohl (put->put_path_length);
3602 sizeof (struct PeerPutMessage) +
3603 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3605 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3607 GNUNET_break_op (0);
3610 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
3611 GNUNET_STATISTICS_update (GDS_stats,
3613 ("# Bytes received from other peers"), (int64_t) msize,
3616 best_known_dest = put->best_known_destination;
3617 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3618 payload = &put_path[putlen];
3619 options = ntohl (put->options);
3620 intermediate_trail_id = put->intermediate_trail_id;
3622 payload_size = msize - (sizeof (struct PeerPutMessage) +
3623 putlen * sizeof (struct GNUNET_PeerIdentity));
3625 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3626 payload, payload_size, &test_key))
3629 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3631 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3632 GNUNET_break_op (0);
3633 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3634 "PUT with key `%s' for block with key %s\n",
3635 put_s, GNUNET_h2s_full (&test_key));
3636 GNUNET_free (put_s);
3641 GNUNET_break_op (0);
3644 /* cannot verify, good luck */
3648 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3650 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3651 ntohl (put->block_type),
3653 NULL, 0, /* bloom filer */
3654 NULL, 0, /* xquery */
3655 payload, payload_size))
3657 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3658 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3661 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3662 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3663 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3664 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3665 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3666 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3668 GNUNET_break_op (0);
3673 /* extend 'put path' by sender */
3674 struct GNUNET_PeerIdentity pp[putlen + 1];
3675 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3677 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3684 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3685 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3687 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3688 GDS_ROUTING_SRC_TO_DEST);
3689 if (NULL == next_hop)
3691 GNUNET_STATISTICS_update (GDS_stats,
3692 gettext_noop ("# Next hop to forward the packet not found "
3693 "trail setup request, packet dropped."),
3695 return GNUNET_SYSERR;
3700 struct Closest_Peer successor;
3701 key_value = GNUNET_ntohll (key_value);
3702 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3703 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3704 *next_hop = successor.next_hop;
3705 intermediate_trail_id = successor.trail_id;
3706 best_known_dest = successor.best_known_destination;
3709 GDS_CLIENTS_process_put (options,
3710 ntohl (put->block_type),
3711 ntohl (put->hop_count),
3712 ntohl (put->desired_replication_level),
3714 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3719 /* I am the final destination */
3720 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3722 DEBUG("PUT destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(put->key)));
3723 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3724 &(put->key),putlen, pp, ntohl (put->block_type),
3725 payload_size, payload);
3729 GDS_NEIGHBOURS_send_put (&put->key,
3730 ntohl (put->block_type),ntohl (put->options),
3731 ntohl (put->desired_replication_level),
3732 best_known_dest, intermediate_trail_id, next_hop,
3733 ntohl (put->hop_count), putlen, pp,
3734 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3735 payload, payload_size);
3742 * FIXME: Check for loop in the request. If you already are part of get path,
3743 * then you need to reset the get path length.
3744 * Core handler for p2p get requests.
3746 * @param cls closure
3747 * @param peer sender of the request
3748 * @param message message
3749 * @return #GNUNET_OK to keep the connection open,
3750 * #GNUNET_SYSERR to close it (signal serious error)
3753 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3754 const struct GNUNET_MessageHeader *message)
3756 const struct PeerGetMessage *get;
3757 const struct GNUNET_PeerIdentity *get_path;
3758 struct GNUNET_PeerIdentity best_known_dest;
3759 struct GNUNET_HashCode intermediate_trail_id;
3760 struct GNUNET_PeerIdentity *next_hop;
3761 uint32_t get_length;
3765 #if ENABLE_MALICIOUS
3766 if(1 == act_malicious)
3768 DEBUG("I am malicious,dropping get request. \n");
3773 msize = ntohs (message->size);
3774 if (msize < sizeof (struct PeerGetMessage))
3776 GNUNET_break_op (0);
3780 get = (const struct PeerGetMessage *)message;
3781 get_length = ntohl (get->get_path_length);
3782 best_known_dest = get->best_known_destination;
3783 intermediate_trail_id = get->intermediate_trail_id;
3784 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3787 sizeof (struct PeerGetMessage) +
3788 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3790 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3792 GNUNET_break_op (0);
3795 DEBUG("PUT FOR DATA_SIZE = %lu\n",msize);
3796 GNUNET_STATISTICS_update (GDS_stats,
3798 ("# Bytes received from other peers"), msize,
3801 /* Add sender to get path */
3802 struct GNUNET_PeerIdentity gp[get_length + 1];
3804 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3805 gp[get_length] = *peer;
3806 get_length = get_length + 1;
3808 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3809 key_value = GNUNET_ntohll (key_value);
3811 /* I am not the final destination. I am part of trail to reach final dest. */
3812 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3814 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3815 GDS_ROUTING_SRC_TO_DEST);
3816 if (NULL == next_hop)
3818 GNUNET_STATISTICS_update (GDS_stats,
3819 gettext_noop ("# Next hop to forward the packet not found "
3820 "GET request, packet dropped."),
3822 return GNUNET_SYSERR;
3827 struct Closest_Peer successor;
3829 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3830 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3831 *next_hop = successor.next_hop;
3832 best_known_dest = successor.best_known_destination;
3833 intermediate_trail_id = successor.trail_id;
3836 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3837 get->desired_replication_level, get->get_path_length,
3839 /* I am the final destination. */
3840 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3842 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(get->key)));
3843 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3845 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3846 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3847 get_length = get_length + 1;
3849 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3850 get_length, final_get_path,
3851 &final_get_path[get_length-2], &my_identity);
3855 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3856 get->desired_replication_level, best_known_dest,
3857 intermediate_trail_id, next_hop, 0,
3865 * Core handler for get result
3866 * @param cls closure
3867 * @param peer sender of the request
3868 * @param message message
3869 * @return #GNUNET_OK to keep the connection open,
3870 * #GNUNET_SYSERR to close it (signal serious error)
3873 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3874 const struct GNUNET_MessageHeader *message)
3876 const struct PeerGetResultMessage *get_result;
3877 const struct GNUNET_PeerIdentity *get_path;
3878 const struct GNUNET_PeerIdentity *put_path;
3879 const void *payload;
3880 size_t payload_size;
3882 unsigned int getlen;
3883 unsigned int putlen;
3884 int current_path_index;
3886 msize = ntohs (message->size);
3887 if (msize < sizeof (struct PeerGetResultMessage))
3889 GNUNET_break_op (0);
3893 get_result = (const struct PeerGetResultMessage *)message;
3894 getlen = ntohl (get_result->get_path_length);
3895 putlen = ntohl (get_result->put_path_length);
3898 sizeof (struct PeerGetResultMessage) +
3899 getlen * sizeof (struct GNUNET_PeerIdentity) +
3900 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3902 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3904 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3906 GNUNET_break_op (0);
3909 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3910 GNUNET_STATISTICS_update (GDS_stats,
3912 ("# Bytes received from other peers"), msize,
3915 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3916 get_path = &put_path[putlen];
3917 payload = (const void *) &get_path[getlen];
3918 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3919 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3921 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3923 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3924 getlen, get_path, putlen,
3925 put_path, get_result->type, payload_size, payload);
3930 current_path_index = search_my_index (get_path, getlen);
3931 if (-1 == current_path_index )
3933 DEBUG ("No entry found in get path.\n");
3935 return GNUNET_SYSERR;
3937 if((getlen + 1) == current_path_index)
3939 DEBUG("Present twice in get path. Not allowed. \n");
3941 return GNUNET_SYSERR;
3943 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3944 &get_path[current_path_index - 1],
3945 &(get_result->querying_peer), putlen, put_path,
3946 getlen, get_path, get_result->expiration_time,
3947 payload, payload_size);
3950 return GNUNET_SYSERR;
3955 * Find the next hop to pass trail setup message. First find the local best known
3956 * hop from your own identity, friends and finger. If you were part of trail,
3957 * then get the next hop from routing table. Compare next_hop from routing table
3958 * and local best known hop, and return the closest one to final_dest_finger_val
3959 * @param final_dest_finger_val 64 bit value of finger identity
3960 * @param intermediate_trail_id If you are part of trail to reach to some other
3961 * finger, then it is the trail id to reach to
3962 * that finger, else set to 0.
3963 * @param is_predecessor Are we looking for closest successor or predecessor.
3964 * @param current_dest In case you are part of trail, then finger to which
3965 * we should forward the message. Else my own identity
3966 * @return Closest Peer for @a final_dest_finger_val
3968 static struct Closest_Peer
3969 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3970 struct GNUNET_HashCode intermediate_trail_id,
3971 unsigned int is_predecessor,
3972 struct GNUNET_PeerIdentity prev_hop,
3973 struct GNUNET_PeerIdentity source,
3974 struct GNUNET_PeerIdentity *current_dest)
3976 struct Closest_Peer peer;
3978 /* Find a local best known peer. */
3979 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3981 /* Am I just a part of a trail towards a finger (current_destination)? */
3982 /* Select best successor among one found locally and current_destination
3983 * that we got from network.*/
3984 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3985 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3988 const struct GNUNET_PeerIdentity *closest_peer;
3990 closest_peer = select_closest_peer (&peer.best_known_destination,
3992 final_dest_finger_val,
3995 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3996 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3998 struct GNUNET_PeerIdentity *next_hop;
4000 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4001 GDS_ROUTING_SRC_TO_DEST);
4002 /* It may happen that trail teardown message got delayed and hence,
4003 the previous hop sent the message over intermediate trail id.In that
4004 case next_hop could be NULL. */
4005 if(NULL != next_hop)
4007 peer.next_hop = *next_hop;
4008 peer.best_known_destination = *current_dest;
4009 peer.trail_id = intermediate_trail_id;
4018 * Core handle for PeerTrailSetupMessage.
4019 * @param cls closure
4020 * @param message message
4021 * @param peer peer identity this notification is about
4022 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4025 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
4026 const struct GNUNET_MessageHeader *message)
4028 const struct PeerTrailSetupMessage *trail_setup;
4029 const struct GNUNET_PeerIdentity *trail_peer_list;
4030 struct GNUNET_PeerIdentity current_dest;
4031 struct FriendInfo *target_friend;
4032 struct GNUNET_PeerIdentity source;
4033 uint64_t final_dest_finger_val;
4034 struct GNUNET_HashCode intermediate_trail_id;
4035 struct GNUNET_HashCode trail_id;
4036 unsigned int is_predecessor;
4037 uint32_t trail_length;
4041 msize = ntohs (message->size);
4042 if (msize < sizeof (struct PeerTrailSetupMessage))
4044 GNUNET_break_op (0);
4045 return GNUNET_SYSERR;
4048 trail_setup = (const struct PeerTrailSetupMessage *) message;
4049 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4050 sizeof (struct GNUNET_PeerIdentity);
4051 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4052 sizeof (struct GNUNET_PeerIdentity) != 0)
4054 GNUNET_break_op (0);
4058 GNUNET_STATISTICS_update (GDS_stats,
4060 ("# Bytes received from other peers"), msize,
4063 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4064 current_dest = trail_setup->best_known_destination;
4065 trail_id = trail_setup->trail_id;
4066 final_dest_finger_val =
4067 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4068 source = trail_setup->source_peer;
4069 is_predecessor = ntohl (trail_setup->is_predecessor);
4070 intermediate_trail_id = trail_setup->intermediate_trail_id;
4072 /* Did the friend insert its ID in the trail list? */
4073 if (trail_length > 0 &&
4074 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (*peer)))
4076 GNUNET_break_op (0);
4077 return GNUNET_SYSERR;
4080 /* If I was the source and got the message back, then set trail length to 0.*/
4081 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4086 /* Check if you are present in the trail seen so far? */
4087 for (i = 0; i < trail_length ; i++)
4089 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4091 trail_length = i; /* Check that you add yourself again */
4096 /* Is my routing table full? */
4097 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4099 GNUNET_assert (NULL !=
4101 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4102 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4103 my_identity, is_predecessor,
4104 trail_peer_list, trail_length,
4105 trail_id, target_friend,
4106 CONGESTION_TIMEOUT);
4110 /* Get the next hop to forward the trail setup request. */
4111 struct Closest_Peer next_peer =
4112 get_local_best_known_next_hop (final_dest_finger_val,
4113 intermediate_trail_id,
4119 /* Am I the final destination? */
4120 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4123 /* If I was not the source of this message for which now I am destination */
4124 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4126 GDS_ROUTING_add (trail_id, *peer, my_identity);
4129 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4131 finger_table_add (my_identity, NULL, 0, is_predecessor,
4132 final_dest_finger_val, trail_id);
4136 if (trail_length > 0)
4138 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4139 &trail_peer_list[trail_length-1]);
4142 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4144 if (NULL == target_friend)
4146 GNUNET_break_op (0);
4147 return GNUNET_SYSERR;
4150 GDS_NEIGHBOURS_send_trail_setup_result (source,
4152 target_friend, trail_length,
4155 final_dest_finger_val,trail_id);
4157 else /* I'm not the final destination. */
4159 GNUNET_assert (NULL !=
4161 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4162 &next_peer.next_hop)));
4164 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4166 /* Add yourself to list of peers. */
4167 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4169 memcpy (peer_list, trail_peer_list,
4170 trail_length * sizeof (struct GNUNET_PeerIdentity));
4171 peer_list[trail_length] = my_identity;
4173 GDS_NEIGHBOURS_send_trail_setup (source,
4174 final_dest_finger_val,
4175 next_peer.best_known_destination,
4176 target_friend, trail_length + 1, peer_list,
4177 is_predecessor, trail_id,
4178 next_peer.trail_id);
4181 GDS_NEIGHBOURS_send_trail_setup (source,
4182 final_dest_finger_val,
4183 next_peer.best_known_destination,
4184 target_friend, 0, NULL,
4185 is_predecessor, trail_id,
4186 next_peer.trail_id);
4193 * Core handle for p2p trail setup result messages.
4195 * @param message message
4196 * @param peer sender of this message.
4197 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4200 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4201 const struct GNUNET_MessageHeader *message)
4203 const struct PeerTrailSetupResultMessage *trail_result;
4204 const struct GNUNET_PeerIdentity *trail_peer_list;
4205 struct GNUNET_PeerIdentity next_hop;
4206 struct FriendInfo *target_friend;
4207 struct GNUNET_PeerIdentity querying_peer;
4208 struct GNUNET_PeerIdentity finger_identity;
4209 uint32_t trail_length;
4210 uint64_t ulitmate_destination_finger_value;
4211 uint32_t is_predecessor;
4212 struct GNUNET_HashCode trail_id;
4216 msize = ntohs (message->size);
4217 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4219 GNUNET_break_op (0);
4223 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4224 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4225 sizeof (struct GNUNET_PeerIdentity);
4226 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4227 sizeof (struct GNUNET_PeerIdentity) != 0)
4229 GNUNET_break_op (0);
4233 GNUNET_STATISTICS_update (GDS_stats,
4235 ("# Bytes received from other peers"), msize,
4238 is_predecessor = ntohl (trail_result->is_predecessor);
4239 querying_peer = trail_result->querying_peer;
4240 finger_identity = trail_result->finger_identity;
4241 trail_id = trail_result->trail_id;
4242 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4243 ulitmate_destination_finger_value =
4244 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4246 /* Am I the one who initiated the query? */
4247 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4249 /* Check that you got the message from the correct peer. */
4250 if (trail_length > 0)
4252 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4257 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4261 /* If I am my own finger identity, error. */
4262 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4264 GNUNET_break_op (0);
4265 return GNUNET_SYSERR;
4268 GDS_ROUTING_add (trail_id, my_identity, *peer);
4269 finger_table_add (finger_identity, trail_peer_list, trail_length,
4270 is_predecessor, ulitmate_destination_finger_value, trail_id);
4274 /* Get my location in the trail. */
4275 my_index = search_my_index (trail_peer_list, trail_length);
4278 DEBUG ("Not found in trail\n");
4280 return GNUNET_SYSERR;
4283 if ((trail_length + 1) == my_index)
4285 DEBUG ("Found twice in trail.\n");
4287 return GNUNET_SYSERR;
4292 if(trail_length > 1)
4293 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4296 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4298 next_hop = trail_result->querying_peer;
4302 if(my_index == trail_length - 1)
4305 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4310 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4312 next_hop = trail_peer_list[my_index - 1];
4315 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4316 if (NULL == target_friend)
4318 GNUNET_break_op (0);
4319 return GNUNET_SYSERR;
4321 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4322 &(trail_result->finger_identity))))
4324 GNUNET_break_op (0);
4325 return GNUNET_SYSERR;
4327 GDS_ROUTING_add (trail_id, next_hop, *peer);
4328 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4329 target_friend, trail_length, trail_peer_list,
4331 ulitmate_destination_finger_value,
4339 * @param trail Trail to be inverted
4340 * @param trail_length Total number of peers in the trail.
4341 * @return Updated trail
4343 static struct GNUNET_PeerIdentity *
4344 invert_trail (const struct GNUNET_PeerIdentity *trail,
4345 unsigned int trail_length)
4349 struct GNUNET_PeerIdentity *inverted_trail;
4351 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4354 j = trail_length - 1;
4355 while (i < trail_length)
4357 inverted_trail[i] = trail[j];
4362 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4363 &inverted_trail[0]));
4364 return inverted_trail;
4369 * Return the shortest trail among all the trails to reach to finger from me.
4370 * @param finger Finger
4371 * @param shortest_trail_length[out] Trail length of shortest trail from me
4373 * @return Shortest trail.
4375 static struct GNUNET_PeerIdentity *
4376 get_shortest_trail (struct FingerInfo *finger,
4377 unsigned int *trail_length)
4379 struct Trail *trail;
4380 unsigned int flag = 0;
4381 unsigned int shortest_trail_index = 0;
4382 int shortest_trail_length = -1;
4383 struct Trail_Element *trail_element;
4384 struct GNUNET_PeerIdentity *trail_list;
4387 trail = GNUNET_new (struct Trail);
4389 /* Get the shortest trail to reach to current successor. */
4390 for (i = 0; i < finger->trails_count; i++)
4392 trail = &finger->trail_list[i];
4396 shortest_trail_index = i;
4397 shortest_trail_length = trail->trail_length;
4402 if (shortest_trail_length > trail->trail_length)
4404 shortest_trail_index = i;
4405 shortest_trail_length = trail->trail_length;
4410 /* Copy the shortest trail and return. */
4411 trail = &finger->trail_list[shortest_trail_index];
4412 trail_element = trail->trail_head;
4414 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4415 shortest_trail_length);
4417 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4419 trail_list[i] = trail_element->peer;
4422 GNUNET_assert(shortest_trail_length != -1);
4424 *trail_length = shortest_trail_length;
4430 * Check if trail_1 and trail_2 have any common element. If yes then join
4431 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4432 * @param trail_1 Trail from source to me, NOT including endpoints.
4433 * @param trail_1_len Total number of peers @a trail_1
4434 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4435 * @param trail_2_len Total number of peers @a trail_2
4436 * @param joined_trail_len Total number of peers in combined trail of trail_1
4438 * @return Joined trail.
4440 static struct GNUNET_PeerIdentity *
4441 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4442 unsigned int trail_1_len,
4443 struct GNUNET_PeerIdentity *trail_2,
4444 unsigned int trail_2_len,
4445 unsigned int *joined_trail_len)
4447 struct GNUNET_PeerIdentity *joined_trail;
4452 for (i = 0; i < trail_1_len; i++)
4454 for (j = 0; j < trail_2_len; j++)
4456 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4459 *joined_trail_len = i + (trail_2_len - j);
4460 joined_trail = GNUNET_malloc (*joined_trail_len *
4461 sizeof(struct GNUNET_PeerIdentity));
4464 /* Copy all the elements from 0 to i into joined_trail. */
4465 for(k = 0; k < ( i+1); k++)
4467 joined_trail[k] = trail_1[k];
4470 /* Increment j as entry stored is same as entry stored at i*/
4473 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4474 while(k <= (*joined_trail_len - 1))
4476 joined_trail[k] = trail_2[j];
4481 return joined_trail;
4485 /* Here you should join the trails. */
4486 *joined_trail_len = trail_1_len + trail_2_len + 1;
4487 joined_trail = GNUNET_malloc (*joined_trail_len *
4488 sizeof(struct GNUNET_PeerIdentity));
4491 for(i = 0; i < trail_1_len;i++)
4493 joined_trail[i] = trail_1[i];
4496 joined_trail[i] = my_identity;
4499 for (j = 0; i < *joined_trail_len; i++,j++)
4501 joined_trail[i] = trail_2[j];
4504 return joined_trail;
4509 * Return the trail from source to my current predecessor. Check if source
4510 * is already part of the this trail, if yes then return the shorten trail.
4511 * @param current_trail Trail from source to me, NOT including the endpoints.
4512 * @param current_trail_length Number of peers in @a current_trail.
4513 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4514 * source to my predecessor, NOT including
4516 * @return Trail from source to my predecessor.
4518 static struct GNUNET_PeerIdentity *
4519 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4520 const struct GNUNET_PeerIdentity *trail_src_to_me,
4521 unsigned int trail_src_to_me_len,
4522 unsigned int *trail_src_to_curr_pred_length)
4524 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4525 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4526 unsigned int trail_me_to_curr_pred_length;
4527 struct FingerInfo *current_predecessor;
4531 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4533 /* Check if trail_src_to_me contains current_predecessor. */
4534 for (i = 0; i < trail_src_to_me_len; i++)
4536 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4537 ¤t_predecessor->finger_identity))
4541 *trail_src_to_curr_pred_length = i;
4546 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4547 sizeof(struct GNUNET_PeerIdentity));
4548 for(j = 0; j < i;j++)
4549 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4550 return trail_src_to_curr_pred;
4554 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4555 &trail_me_to_curr_pred_length);
4557 /* Check if trail contains the source_peer. */
4558 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4560 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4561 &trail_me_to_curr_pred[i]))
4564 /* Source is NOT part of trail. */
4567 /* Source is the last element in the trail to reach to my pred.
4568 Source is direct friend of the pred. */
4569 if (trail_me_to_curr_pred_length == i)
4571 *trail_src_to_curr_pred_length = 0;
4575 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4576 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4577 *trail_src_to_curr_pred_length);
4579 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4581 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4583 GNUNET_free_non_null(trail_me_to_curr_pred);
4584 return trail_src_to_curr_pred;
4588 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4589 trail_src_to_me_len,
4590 trail_me_to_curr_pred,
4591 trail_me_to_curr_pred_length,
4593 *trail_src_to_curr_pred_length = len;
4594 GNUNET_free_non_null(trail_me_to_curr_pred);
4595 return trail_src_to_curr_pred;
4600 * Add finger as your predecessor. To add, first generate a new trail id, invert
4601 * the trail to get the trail from me to finger, add an entry in your routing
4602 * table, send add trail message to peers which are part of trail from me to
4603 * finger and add finger in finger table.
4606 * @param trail_length
4609 update_predecessor (struct GNUNET_PeerIdentity finger,
4610 struct GNUNET_PeerIdentity *trail,
4611 unsigned int trail_length)
4613 struct GNUNET_HashCode trail_to_new_predecessor_id;
4614 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4615 struct FriendInfo *target_friend;
4617 /* Generate trail id for trail from me to new predecessor = finger. */
4618 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4619 &trail_to_new_predecessor_id,
4620 sizeof (trail_to_new_predecessor_id));
4622 /* Finger is a friend. */
4623 if (trail_length == 0)
4625 trail_to_new_predecessor = NULL;
4626 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4627 GNUNET_assert (NULL != (target_friend =
4628 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4633 /* Invert the trail to get the trail from me to finger, NOT including the
4635 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4636 &trail[trail_length-1]));
4638 trail_to_new_predecessor = invert_trail (trail, trail_length);
4640 /* Add an entry in your routing table. */
4641 GDS_ROUTING_add (trail_to_new_predecessor_id,
4643 trail_to_new_predecessor[0]);
4645 GNUNET_assert (NULL != (target_friend =
4646 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4647 &trail_to_new_predecessor[0])));
4648 GNUNET_assert (NULL != (
4649 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4650 &trail[trail_length - 1])));
4653 /* Add entry in routing table of all peers that are part of trail from me
4654 to finger, including finger. */
4655 GDS_NEIGHBOURS_send_add_trail (my_identity,
4657 trail_to_new_predecessor_id,
4658 trail_to_new_predecessor,
4662 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4663 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4664 GNUNET_free_non_null(trail_to_new_predecessor);
4669 * Check if you already have a predecessor. If not then add finger as your
4670 * predecessor. If you have predecessor, then compare two peer identites.
4671 * If finger is correct predecessor, then remove the old entry, add finger in
4672 * finger table and send add_trail message to add the trail in the routing
4673 * table of all peers which are part of trail to reach from me to finger.
4674 * @param finger New peer which may be our predecessor.
4675 * @param trail List of peers to reach from @finger to me.
4676 * @param trail_length Total number of peer in @a trail.
4679 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4680 struct GNUNET_PeerIdentity *trail,
4681 unsigned int trail_length)
4683 struct FingerInfo *current_predecessor;
4684 const struct GNUNET_PeerIdentity *closest_peer;
4685 uint64_t predecessor_value;
4686 unsigned int is_predecessor = 1;
4688 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4690 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4692 /* No predecessor. Add finger as your predecessor. */
4693 if (GNUNET_NO == current_predecessor->is_present)
4695 update_predecessor (finger, trail, trail_length);
4699 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4705 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4706 closest_peer = select_closest_peer (&finger,
4707 ¤t_predecessor->finger_identity,
4708 predecessor_value, is_predecessor);
4710 /* Finger is the closest predecessor. Remove the existing one and add the new
4712 if (closest_peer == &finger)
4714 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4715 update_predecessor (finger, trail, trail_length);
4723 * Core handle for p2p verify successor messages.
4724 * @param cls closure
4725 * @param message message
4726 * @param peer peer identity this notification is about
4727 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4730 handle_dht_p2p_verify_successor(void *cls,
4731 const struct GNUNET_PeerIdentity *peer,
4732 const struct GNUNET_MessageHeader *message)
4734 const struct PeerVerifySuccessorMessage *vsm;
4735 struct GNUNET_HashCode trail_id;
4736 struct GNUNET_PeerIdentity successor;
4737 struct GNUNET_PeerIdentity source_peer;
4738 struct GNUNET_PeerIdentity *trail;
4739 struct GNUNET_PeerIdentity *next_hop;
4740 struct FingerInfo current_predecessor;
4741 struct FriendInfo *target_friend;
4742 unsigned int trail_src_to_curr_pred_len = 0;
4743 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4744 unsigned int trail_length;
4747 msize = ntohs (message->size);
4749 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4751 GNUNET_break_op (0);
4755 vsm = (const struct PeerVerifySuccessorMessage *) message;
4756 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4757 sizeof (struct GNUNET_PeerIdentity);
4758 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4759 sizeof (struct GNUNET_PeerIdentity) != 0)
4761 GNUNET_break_op (0);
4765 GNUNET_STATISTICS_update (GDS_stats,
4767 ("# Bytes received from other peers"), msize,
4770 trail_id = vsm->trail_id;
4771 source_peer = vsm->source_peer;
4772 successor = vsm->successor;
4773 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4776 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4778 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4780 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4781 if (NULL == next_hop)
4783 // GNUNET_break_op (0);
4784 // return GNUNET_SYSERR;
4785 //FIXME: Here it may happen that trail has not yet been added
4786 //in notify successor.
4790 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4792 if(NULL == target_friend)
4797 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4798 trail_id, trail, trail_length,
4803 /* I am the destination of this message. */
4805 /* Check if the source_peer could be our predecessor and if yes then update
4807 compare_and_update_predecessor (source_peer, trail, trail_length);
4808 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4810 /* Is source of this message NOT my predecessor. */
4811 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4814 trail_src_to_curr_pred =
4815 get_trail_src_to_curr_pred (source_peer,
4818 &trail_src_to_curr_pred_len);
4822 trail_src_to_curr_pred_len = trail_length;
4825 trail_src_to_curr_pred =
4826 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4827 *trail_src_to_curr_pred_len);
4828 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4830 trail_src_to_curr_pred[i] = trail[i];
4834 GNUNET_assert (NULL !=
4836 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4837 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4838 current_predecessor.finger_identity,
4839 trail_id, trail_src_to_curr_pred,
4840 trail_src_to_curr_pred_len,
4841 GDS_ROUTING_DEST_TO_SRC,
4843 GNUNET_free_non_null(trail_src_to_curr_pred);
4849 * If the trail from me to my probable successor contains a friend not
4850 * at index 0, then we can shorten the trail.
4851 * @param probable_successor Peer which is our probable successor
4852 * @param trail_me_to_probable_successor Peers in path from me to my probable
4853 * successor, NOT including the endpoints.
4854 * @param trail_me_to_probable_successor_len Total number of peers in
4855 * @a trail_me_to_probable_succesor.
4856 * @return Updated trail, if any friend found.
4857 * Else the trail_me_to_probable_successor.
4859 struct GNUNET_PeerIdentity *
4860 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4861 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4862 unsigned int trail_me_to_probable_successor_len,
4863 unsigned int *trail_to_new_successor_length)
4867 struct GNUNET_PeerIdentity *trail_to_new_successor;
4869 /* Probable successor is a friend */
4870 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4871 &probable_successor))
4873 trail_to_new_successor = NULL;
4874 *trail_to_new_successor_length = 0;
4875 return trail_to_new_successor;
4878 /* Is there any friend of yours in this trail. */
4879 if(trail_me_to_probable_successor_len > 1)
4881 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4883 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4884 &trail_me_to_probable_successor[i]))
4887 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4888 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4889 *trail_to_new_successor_length);
4892 for(j = 0;j < *trail_to_new_successor_length;i++,j++)
4894 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4897 return trail_to_new_successor;
4901 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4902 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4907 * Check if the peer which sent us verify successor result message is still ours
4908 * successor or not. If not, then compare existing successor and probable successor.
4909 * In case probable successor is the correct successor, remove the existing
4910 * successor. Add probable successor as new successor. Send notify new successor
4911 * message to new successor.
4913 * @param probable_successor
4915 * @param trail_length
4918 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4919 struct GNUNET_PeerIdentity probable_successor,
4920 const struct GNUNET_PeerIdentity *trail,
4921 unsigned int trail_length)
4923 struct FingerInfo *current_successor;
4924 const struct GNUNET_PeerIdentity *closest_peer;
4925 struct GNUNET_HashCode trail_id;
4926 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4927 struct FriendInfo *target_friend;
4928 unsigned int trail_me_to_probable_succ_len;
4929 unsigned int is_predecessor = GNUNET_NO;
4930 uint64_t successor_value;
4932 current_successor = &finger_table[0];
4933 successor_value = compute_finger_identity_value(0);
4935 closest_peer = select_closest_peer (&probable_successor,
4936 ¤t_successor->finger_identity,
4937 successor_value, is_predecessor);
4939 /* If the current_successor in the finger table is closest, then do nothing. */
4940 if (closest_peer == ¤t_successor->finger_identity)
4942 /* Code for testing ONLY: Store the successor for path tracking */
4943 // track_topology = 1;
4944 if ((NULL != GDS_stats))
4950 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4951 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4952 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4953 GNUNET_free (my_id_str);
4954 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4959 /* Probable successor is the closest peer.*/
4960 if(trail_length > 0)
4962 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4967 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4968 &probable_successor));
4971 trail_me_to_probable_succ_len = 0;
4972 trail_me_to_probable_succ =
4973 check_trail_me_to_probable_succ (probable_successor,
4974 trail, trail_length,
4975 &trail_me_to_probable_succ_len);
4977 /* Remove the existing successor. */
4978 remove_existing_finger (current_successor, 0);
4980 /* TODO URGENT: Check if any peer is present more than once, if yes then shorten
4981 the trail. before sending it across the network. */
4982 /* Generate a new trail id to reach to your new successor. */
4983 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4984 &trail_id, sizeof (trail_id));
4986 if (trail_me_to_probable_succ_len > 0)
4988 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4989 GNUNET_assert (NULL !=
4991 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4992 &trail_me_to_probable_succ[0])));
4996 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4997 GNUNET_assert (NULL !=
4999 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5000 &probable_successor)));
5003 add_new_finger (probable_successor, trail_me_to_probable_succ,
5004 trail_me_to_probable_succ_len, trail_id, 0);
5006 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
5007 trail_me_to_probable_succ,
5008 trail_me_to_probable_succ_len,
5016 * FIXME: Check for duplicate elements everywhere when you are making
5018 * Core handle for p2p verify successor result messages.
5019 * @param cls closure
5020 * @param message message
5021 * @param peer peer identity this notification is about
5022 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5025 handle_dht_p2p_verify_successor_result(void *cls,
5026 const struct GNUNET_PeerIdentity *peer,
5027 const struct GNUNET_MessageHeader *message)
5029 const struct PeerVerifySuccessorResultMessage *vsrm;
5030 enum GDS_ROUTING_trail_direction trail_direction;
5031 struct GNUNET_PeerIdentity querying_peer;
5032 struct GNUNET_HashCode trail_id;
5033 struct GNUNET_PeerIdentity *next_hop;
5034 struct FriendInfo *target_friend;
5035 struct GNUNET_PeerIdentity probable_successor;
5036 struct GNUNET_PeerIdentity current_successor;
5037 const struct GNUNET_PeerIdentity *trail;
5038 unsigned int trail_length;
5041 msize = ntohs (message->size);
5042 /* We send a trail to reach from old successor to new successor, if
5043 * old_successor != new_successor.*/
5044 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5046 GNUNET_break_op (0);
5050 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5051 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5052 sizeof (struct GNUNET_PeerIdentity);
5054 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5055 sizeof (struct GNUNET_PeerIdentity) != 0)
5057 GNUNET_break_op (0);
5061 GNUNET_STATISTICS_update (GDS_stats,
5063 ("# Bytes received from other peers"), msize,
5066 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5067 querying_peer = vsrm->querying_peer;
5068 trail_direction = ntohl (vsrm->trail_direction);
5069 trail_id = vsrm->trail_id;
5070 probable_successor = vsrm->probable_successor;
5071 current_successor = vsrm->current_successor;
5074 /* I am the querying_peer. */
5075 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5077 compare_and_update_successor (current_successor,
5078 probable_successor, trail, trail_length);
5082 /*If you are not the querying peer then pass on the message */
5083 GNUNET_assert (NULL != (next_hop =
5084 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
5085 GNUNET_assert (NULL !=
5087 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5088 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5089 vsrm->current_successor,
5090 probable_successor, trail_id,
5093 trail_direction, target_friend);
5099 * Core handle for p2p notify new successor messages.
5100 * @param cls closure
5101 * @param message message
5102 * @param peer peer identity this notification is about
5103 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5106 handle_dht_p2p_notify_new_successor(void *cls,
5107 const struct GNUNET_PeerIdentity *peer,
5108 const struct GNUNET_MessageHeader *message)
5110 const struct PeerNotifyNewSuccessorMessage *nsm;
5111 struct GNUNET_PeerIdentity *trail;
5112 struct GNUNET_PeerIdentity source;
5113 struct GNUNET_PeerIdentity new_successor;
5114 struct GNUNET_HashCode trail_id;
5115 struct GNUNET_PeerIdentity next_hop;
5116 struct FriendInfo *target_friend;
5119 uint32_t trail_length;
5121 msize = ntohs (message->size);
5123 /* We have the trail to reach from source to new successor. */
5124 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5126 GNUNET_break_op (0);
5130 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5131 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5132 sizeof (struct GNUNET_PeerIdentity);
5133 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5134 sizeof (struct GNUNET_PeerIdentity) != 0)
5136 GNUNET_break_op (0);
5140 GNUNET_STATISTICS_update (GDS_stats,
5142 ("# Bytes received from other peers"), msize,
5145 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5146 source = nsm->source_peer;
5147 new_successor = nsm->new_successor;
5148 trail_id = nsm->trail_id;
5151 //FIXME: add a check to make sure peer is correct.
5153 /* I am the new_successor to source_peer. */
5154 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5156 if(trail_length > 0)
5157 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5160 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5162 compare_and_update_predecessor (source, trail, trail_length);
5166 GNUNET_assert(trail_length > 0);
5167 /* I am part of trail to reach to successor. */
5168 my_index = search_my_index (trail, trail_length);
5171 DEBUG ("No entry found in trail\n");
5172 GNUNET_break_op (0);
5173 return GNUNET_SYSERR;
5175 if((trail_length + 1) == my_index)
5177 DEBUG ("Found twice in trail.\n");
5178 GNUNET_break_op (0);
5179 return GNUNET_SYSERR;
5181 if ((trail_length-1) == my_index)
5182 next_hop = new_successor;
5184 next_hop = trail[my_index + 1];
5187 /* Add an entry in routing table for trail from source to its new successor. */
5188 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5189 GNUNET_assert (NULL !=
5191 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5192 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5194 trail_id, target_friend);
5201 * Core handler for P2P trail rejection message
5202 * @param cls closure
5203 * @param message message
5204 * @param peer peer identity this notification is about
5205 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5208 handle_dht_p2p_trail_setup_rejection (void *cls,
5209 const struct GNUNET_PeerIdentity *peer,
5210 const struct GNUNET_MessageHeader *message)
5212 const struct PeerTrailRejectionMessage *trail_rejection;
5213 unsigned int trail_length;
5214 const struct GNUNET_PeerIdentity *trail_peer_list;
5215 struct FriendInfo *target_friend;
5216 struct GNUNET_TIME_Relative congestion_timeout;
5217 struct GNUNET_HashCode trail_id;
5218 struct GNUNET_PeerIdentity next_peer;
5219 struct GNUNET_PeerIdentity source;
5220 struct GNUNET_PeerIdentity *next_hop;
5221 uint64_t ultimate_destination_finger_value;
5222 unsigned int is_predecessor;
5225 msize = ntohs (message->size);
5226 /* We are passing the trail setup so far. */
5227 if (msize < sizeof (struct PeerTrailRejectionMessage))
5229 GNUNET_break_op (0);
5233 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5234 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5235 sizeof (struct GNUNET_PeerIdentity);
5236 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5237 sizeof (struct GNUNET_PeerIdentity) != 0)
5239 GNUNET_break_op (0);
5243 GNUNET_STATISTICS_update (GDS_stats,
5245 ("# Bytes received from other peers"), msize,
5248 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5249 is_predecessor = ntohl (trail_rejection->is_predecessor);
5250 congestion_timeout = trail_rejection->congestion_time;
5251 source = trail_rejection->source_peer;
5252 trail_id = trail_rejection->trail_id;
5253 ultimate_destination_finger_value =
5254 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5256 /* First set the congestion time of the friend that sent you this message. */
5257 GNUNET_assert (NULL !=
5259 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5260 target_friend->congestion_timestamp =
5261 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5262 congestion_timeout);
5264 /* I am the source peer which wants to setup the trail. Do nothing.
5265 * send_find_finger_trail_task is scheduled periodically.*/
5266 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5269 /* If I am congested then pass this message to peer before me in trail. */
5270 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5272 struct GNUNET_PeerIdentity *new_trail;
5273 unsigned int new_trail_length;
5275 /* Remove yourself from the trail setup so far. */
5276 if (trail_length == 1)
5279 new_trail_length = 0;
5284 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5285 sizeof (struct GNUNET_PeerIdentity));
5287 /* Remove myself from the trail. */
5288 new_trail_length = trail_length -1;
5289 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5290 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5293 GNUNET_assert (NULL !=
5295 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5296 GDS_NEIGHBOURS_send_trail_rejection (source,
5297 ultimate_destination_finger_value,
5298 my_identity, is_predecessor,
5299 new_trail,new_trail_length,trail_id,
5300 target_friend, CONGESTION_TIMEOUT);
5301 GNUNET_free (new_trail);
5305 struct Closest_Peer successor;
5306 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5308 /* Am I the final destination? */
5309 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5312 if (0 == trail_length)
5315 next_peer = trail_peer_list[trail_length-1];
5317 GNUNET_assert (NULL !=
5319 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5321 GDS_NEIGHBOURS_send_trail_setup_result (source,
5323 target_friend, trail_length,
5326 ultimate_destination_finger_value,
5331 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5333 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5334 peer_list[trail_length] = my_identity;
5336 GNUNET_assert (NULL !=
5338 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5340 GDS_NEIGHBOURS_send_trail_setup (source,
5341 ultimate_destination_finger_value,
5342 successor.best_known_destination,
5343 target_friend, trail_length + 1, peer_list,
5344 is_predecessor, trail_id,
5345 successor.trail_id);
5352 * Core handle for p2p trail tear compression messages.
5353 * @param cls closure
5354 * @param message message
5355 * @param peer peer identity this notification is about
5356 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5359 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5360 const struct GNUNET_MessageHeader *message)
5362 const struct PeerTrailCompressionMessage *trail_compression;
5363 struct GNUNET_PeerIdentity *next_hop;
5364 struct FriendInfo *target_friend;
5365 struct GNUNET_HashCode trail_id;
5368 msize = ntohs (message->size);
5370 if (msize != sizeof (struct PeerTrailCompressionMessage))
5372 GNUNET_break_op (0);
5376 GNUNET_STATISTICS_update (GDS_stats,
5378 ("# Bytes received from other peers"), msize,
5381 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5382 trail_id = trail_compression->trail_id;
5384 /* Am I the new first friend to reach to finger of this trail. */
5385 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5388 GNUNET_assert (NULL !=
5389 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5390 &trail_compression->source_peer)));
5392 /* Update your prev hop to source of this message. */
5393 GNUNET_assert (GNUNET_SYSERR !=
5394 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5395 trail_compression->source_peer)));
5399 /* Pass the message to next hop to finally reach to new_first_friend. */
5400 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5402 if (NULL == next_hop)
5408 GNUNET_assert (NULL !=
5410 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5412 GDS_ROUTING_remove_trail (trail_id);
5414 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5416 trail_compression->new_first_friend,
5423 * Core handler for trail teardown message.
5424 * @param cls closure
5425 * @param message message
5426 * @param peer sender of this messsage.
5427 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5430 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5431 const struct GNUNET_MessageHeader *message)
5433 const struct PeerTrailTearDownMessage *trail_teardown;
5434 enum GDS_ROUTING_trail_direction trail_direction;
5435 struct GNUNET_HashCode trail_id;
5436 struct GNUNET_PeerIdentity *next_hop;
5439 msize = ntohs (message->size);
5441 /* Here we pass only the trail id. */
5442 if (msize != sizeof (struct PeerTrailTearDownMessage))
5444 GNUNET_break_op (0);
5448 GNUNET_STATISTICS_update (GDS_stats,
5450 ("# Bytes received from other peers"), msize,
5453 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5454 trail_direction = ntohl (trail_teardown->trail_direction);
5455 trail_id = trail_teardown->trail_id;
5457 /* Check if peer is the real peer from which we should get this message.*/
5458 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5460 GNUNET_assert (NULL != (prev_hop =
5461 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5462 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5465 return GNUNET_SYSERR;
5469 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5471 if (NULL == next_hop)
5474 return GNUNET_SYSERR;
5477 /* I am the next hop, which means I am the final destination. */
5478 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5480 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5485 /* If not final destination, then send a trail teardown message to next hop.*/
5486 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5487 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5488 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5496 * Core handle for p2p add trail message.
5497 * @param cls closure
5498 * @param message message
5499 * @param peer peer identity this notification is about
5500 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5503 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5504 const struct GNUNET_MessageHeader *message)
5506 const struct PeerAddTrailMessage *add_trail;
5507 const struct GNUNET_PeerIdentity *trail;
5508 struct GNUNET_HashCode trail_id;
5509 struct GNUNET_PeerIdentity destination_peer;
5510 struct GNUNET_PeerIdentity source_peer;
5511 struct GNUNET_PeerIdentity next_hop;
5512 unsigned int trail_length;
5513 unsigned int my_index;
5516 msize = ntohs (message->size);
5517 /* In this message we pass the whole trail from source to destination as we
5518 * are adding that trail.*/
5519 //FIXME: failed when run with 1000 pears. check why.
5520 if (msize < sizeof (struct PeerAddTrailMessage))
5522 GNUNET_break_op (0);
5526 add_trail = (const struct PeerAddTrailMessage *) message;
5527 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5528 sizeof (struct GNUNET_PeerIdentity);
5529 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5530 sizeof (struct GNUNET_PeerIdentity) != 0)
5532 GNUNET_break_op (0);
5536 GNUNET_STATISTICS_update (GDS_stats,
5538 ("# Bytes received from other peers"), msize,
5541 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5542 destination_peer = add_trail->destination_peer;
5543 source_peer = add_trail->source_peer;
5544 trail_id = add_trail->trail_id;
5546 //FIXME: add a check that sender peer is not malicious. Make it a generic
5547 // function so that it can be used in all other functions where we need the
5548 // same functionality.
5550 /* I am not the destination of the trail. */
5551 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5553 struct FriendInfo *target_friend;
5555 /* Get my location in the trail. */
5556 my_index = search_my_index (trail, trail_length);
5559 GNUNET_break_op (0);
5560 return GNUNET_SYSERR;
5562 if((trail_length + 1) == my_index)
5564 DEBUG ("Found twice in trail.\n");
5565 GNUNET_break_op (0);
5566 return GNUNET_SYSERR;
5568 if ((trail_length - 1) == my_index)
5570 next_hop = destination_peer;
5574 next_hop = trail[my_index + 1];
5577 /* Add in your routing table. */
5578 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5579 GNUNET_assert (NULL !=
5581 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5582 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5583 trail, trail_length, target_friend);
5586 /* I am the destination. Add an entry in routing table. */
5587 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5593 * Free the finger trail in which the first friend to reach to a finger is
5594 * disconnected_friend. Also remove entry from routing table for that particular
5596 * @param disconnected_friend PeerIdentity of friend which got disconnected
5597 * @param remove_finger Finger whose trail we need to check if it has
5598 * disconnected_friend as the first hop.
5599 * @return Total number of trails in which disconnected_friend was the first
5603 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5604 struct FingerInfo *remove_finger)
5606 unsigned int matching_trails_count;
5609 /* Number of trails with disconnected_friend as the first hop in the trail
5610 * to reach from me to remove_finger, NOT including endpoints. */
5611 matching_trails_count = 0;
5613 /* Iterate over all the trails of finger. */
5614 for (i = 0; i < remove_finger->trails_count; i++)
5616 struct Trail *trail;
5617 trail = &remove_finger->trail_list[i];
5619 /* This assertion is ensure that there are no gaps in the trail list.
5620 REMOVE IT AFTERWARDS. */
5621 GNUNET_assert (GNUNET_YES == trail->is_present);
5623 /* First friend to reach to finger is disconnected_peer. */
5624 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5625 disconnected_friend))
5627 struct GNUNET_PeerIdentity *next_hop;
5628 struct FriendInfo *remove_friend;
5630 GNUNET_assert (NULL !=
5632 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5633 disconnected_friend)));
5634 /* FIXME: removing no but check it. */
5635 //remove_friend->trails_count--;
5636 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5637 GDS_ROUTING_SRC_TO_DEST);
5639 /* Here it may happen that as all the peers got disconnected, the entry in
5640 routing table for that particular trail has been removed, because the
5641 previously disconnected peer was either a next hop or prev hop of that
5643 if (NULL == next_hop)
5646 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5648 matching_trails_count++;
5649 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5652 trail->is_present = GNUNET_NO;
5655 return matching_trails_count;
5660 * Iterate over finger_table entries.
5661 * 0. Ignore finger which is my_identity or if no valid entry present at
5662 * that finger index.
5663 * 1. If disconnected_friend is a finger, then remove the routing entry from
5664 your own table. Free the trail.
5665 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5666 * 2.1 Remove all the trails and entry from routing table in which disconnected
5667 * friend is the first friend in the trail. If disconnected_friend is the
5668 * first friend in all the trails to reach finger, then remove the finger.
5669 * @param disconnected_friend Peer identity of friend which got disconnected.
5672 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5674 struct FingerInfo *remove_finger;
5675 struct FriendInfo *remove_friend;
5676 int removed_trails_count;
5679 /* Iterate over finger table entries. */
5680 for (i = 0; i < MAX_FINGERS; i++)
5682 remove_finger = &finger_table[i];
5684 /* No finger stored at this trail index. */
5685 if (GNUNET_NO == remove_finger->is_present)
5688 /* I am my own finger, then ignore this finger. */
5689 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5693 /* Is disconnected_peer a finger? */
5694 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5695 &remove_finger->finger_identity))
5697 struct GNUNET_PeerIdentity *next_hop;
5698 struct GNUNET_HashCode trail_id;
5701 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5702 trail_id = remove_finger->trail_list[0].trail_id;
5706 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5709 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5710 &remove_finger->finger_identity)));
5711 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5712 GNUNET_assert (NULL !=
5714 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5715 disconnected_peer)));
5718 remove_finger->trail_list[0].is_present = GNUNET_NO;
5719 //GNUNET_assert (0 != remove_friend->trails_count);
5720 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5721 remove_finger->is_present = GNUNET_NO;
5722 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5726 /* If finger is a friend but not disconnected_friend, then continue. */
5727 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5728 &remove_finger->finger_identity))
5731 /* Iterate over the list of trails to reach remove_finger. Check if
5732 * disconnected_friend is the first friend in any of the trail. */
5733 removed_trails_count = remove_matching_trails (disconnected_peer,
5735 remove_finger->trails_count =
5736 remove_finger->trails_count - removed_trails_count;
5737 /* All the finger trails had disconnected_friend as the first friend,
5738 * so free the finger. */
5739 if (remove_finger->trails_count == 0)
5741 remove_finger->is_present = GNUNET_NO;
5742 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5749 * Method called whenever a peer disconnects.
5751 * @param cls closure
5752 * @param peer peer identity this notification is about
5755 handle_core_disconnect (void *cls,
5756 const struct GNUNET_PeerIdentity *peer)
5758 struct FriendInfo *remove_friend;
5760 /* If disconnected to own identity, then return. */
5761 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5764 GNUNET_assert (NULL != (remove_friend =
5765 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5767 /* Remove fingers with peer as first friend or if peer is a finger. */
5768 remove_matching_fingers (peer);
5770 /* Remove any trail from routing table of which peer is a part of. This function
5771 * internally sends a trail teardown message in the direction of which
5772 * disconnected peer is not part of. */
5773 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5775 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5777 /* Remove peer from friend_peermap. */
5778 GNUNET_assert (GNUNET_YES ==
5779 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5783 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5786 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5788 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5789 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5798 * Method called whenever a peer connects.
5800 * @param cls closure
5801 * @param peer_identity peer identity this notification is about
5804 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5806 struct FriendInfo *friend;
5808 /* Check for connect to self message */
5809 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5812 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5814 /* If peer already exists in our friend_peermap, then exit. */
5815 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5822 friend = GNUNET_new (struct FriendInfo);
5823 friend->id = *peer_identity;
5825 GNUNET_assert (GNUNET_OK ==
5826 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5827 peer_identity, friend,
5828 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5830 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5831 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5833 next_send_time.rel_value_us =
5834 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5835 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5836 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5837 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5843 * To be called on core init/fail.
5845 * @param cls service closure
5846 * @param identity the public identity of this peer
5849 core_init (void *cls,
5850 const struct GNUNET_PeerIdentity *identity)
5852 my_identity = *identity;
5855 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5856 my_id64 = GNUNET_ntohll (my_id64);
5857 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5858 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5864 * Initialize finger table entries.
5867 finger_table_init ()
5869 memset (&finger_table, 0, sizeof (finger_table));
5874 * Initialize neighbours subsystem.
5875 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5878 GDS_NEIGHBOURS_init (void)
5880 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5881 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5882 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5883 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5884 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5885 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5886 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5887 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5888 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5889 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5890 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5891 sizeof (struct PeerTrailCompressionMessage)},
5892 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5893 sizeof (struct PeerTrailTearDownMessage)},
5894 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5898 #if ENABLE_MALICIOUS
5903 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5904 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5905 GNUNET_NO, core_handlers);
5907 if (NULL == core_api)
5908 return GNUNET_SYSERR;
5910 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5911 finger_table_init ();
5917 * Free the memory held up by trails of a finger.
5920 delete_finger_table_entries()
5925 for(i = 0; i < MAX_FINGERS; i++)
5927 if(GNUNET_NO == finger_table[i].is_present)
5930 for(j = 0; j < finger_table[i].trails_count; j++)
5932 free_trail(&finger_table[i].trail_list[i]);
5938 * Shutdown neighbours subsystem.
5941 GDS_NEIGHBOURS_done (void)
5943 if (NULL == core_api)
5946 GNUNET_CORE_disconnect (core_api);
5949 delete_finger_table_entries();
5951 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5952 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5953 friend_peermap = NULL;
5955 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5958 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5959 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5962 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5964 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5965 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5973 * @return my identity
5975 struct GNUNET_PeerIdentity
5976 GDS_NEIGHBOURS_get_my_id (void)
5981 /* end of gnunet-service-xdht_neighbours.c */