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 * Called when core is ready to send a message we asked for
896 * out to the destination.
898 * @param cls the 'struct FriendInfo' of the target friend
899 * @param size number of bytes available in buf
900 * @param buf where the callee should write the message
901 * @return number of bytes written to buf
904 core_transmit_notify (void *cls, size_t size, void *buf)
906 struct FriendInfo *peer = cls;
908 struct P2PPendingMessage *pending;
913 while ((NULL != (pending = peer->head)) &&
914 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
916 peer->pending_count--;
917 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
918 GNUNET_free (pending);
922 /* no messages pending */
928 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
929 GNUNET_CORE_PRIO_BEST_EFFORT,
930 GNUNET_TIME_absolute_get_remaining
931 (pending->timeout), &peer->id,
932 ntohs (pending->msg->size),
933 &core_transmit_notify, peer);
934 GNUNET_break (NULL != peer->th);
938 while ((NULL != (pending = peer->head)) &&
939 (size - off >= (msize = ntohs (pending->msg->size))))
941 GNUNET_STATISTICS_update (GDS_stats,
943 ("# Bytes transmitted to other peers"), msize,
945 memcpy (&cbuf[off], pending->msg, msize);
947 peer->pending_count--;
948 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
949 GNUNET_free (pending);
951 if (peer->head != NULL)
954 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
955 GNUNET_CORE_PRIO_BEST_EFFORT,
956 GNUNET_TIME_absolute_get_remaining
957 (pending->timeout), &peer->id, msize,
958 &core_transmit_notify, peer);
959 GNUNET_break (NULL != peer->th);
966 * Transmit all messages in the friend's message queue.
968 * @param peer message queue to process
971 process_friend_queue (struct FriendInfo *peer)
973 struct P2PPendingMessage *pending;
975 if (NULL == (pending = peer->head))
979 if (NULL != peer->th)
985 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
987 GNUNET_TIME_absolute_get_remaining
988 (pending->timeout), &peer->id,
989 ntohs (pending->msg->size),
990 &core_transmit_notify, peer);
991 GNUNET_break (NULL != peer->th);
996 * Construct a trail setup message and forward it to target_friend
997 * @param source_peer Peer which wants to setup the trail
998 * @param ultimate_destination_finger_value Peer identity closest to this value
999 * will be finger to @a source_peer
1000 * @param best_known_destination Best known destination (could be finger or friend)
1001 * which should get this message. In case it is
1002 * friend, then it is same as target_friend
1003 * @param target_friend Friend to which message is forwarded now.
1004 * @param trail_length Total number of peers in trail setup so far.
1005 * @param trail_peer_list Trail setup so far
1006 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1007 * @param trail_id Unique identifier for the trail we are trying to setup.
1008 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1009 * best_known_destination when its a finger. If not
1010 * used then set to 0.
1013 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1014 uint64_t ultimate_destination_finger_value,
1015 struct GNUNET_PeerIdentity best_known_destination,
1016 struct FriendInfo *target_friend,
1017 unsigned int trail_length,
1018 const struct GNUNET_PeerIdentity *trail_peer_list,
1019 unsigned int is_predecessor,
1020 struct GNUNET_HashCode trail_id,
1021 struct GNUNET_HashCode intermediate_trail_id)
1023 struct P2PPendingMessage *pending;
1024 struct PeerTrailSetupMessage *tsm;
1025 struct GNUNET_PeerIdentity *peer_list;
1028 msize = sizeof (struct PeerTrailSetupMessage) +
1029 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1031 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1037 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1039 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1043 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1044 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1045 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1046 pending->msg = &tsm->header;
1047 tsm->header.size = htons (msize);
1048 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1049 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1050 tsm->source_peer = source_peer;
1051 tsm->best_known_destination = best_known_destination;
1052 tsm->is_predecessor = htonl (is_predecessor);
1053 tsm->trail_id = trail_id;
1054 tsm->intermediate_trail_id = intermediate_trail_id;
1056 if (trail_length > 0)
1058 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1059 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1062 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1063 target_friend->pending_count++;
1064 process_friend_queue (target_friend);
1069 * Construct a trail setup result message and forward it to target friend.
1070 * @param querying_peer Peer which sent the trail setup request and should get
1072 * @param Finger Peer to which the trail has been setup to.
1073 * @param target_friend Friend to which this message should be forwarded.
1074 * @param trail_length Numbers of peers in the trail.
1075 * @param trail_peer_list Peers which are part of the trail from
1076 * querying_peer to Finger, NOT including them.
1077 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1078 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1080 * @param trail_id Unique identifier of the trail.
1083 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1084 struct GNUNET_PeerIdentity finger,
1085 struct FriendInfo *target_friend,
1086 unsigned int trail_length,
1087 const struct GNUNET_PeerIdentity *trail_peer_list,
1088 unsigned int is_predecessor,
1089 uint64_t ultimate_destination_finger_value,
1090 struct GNUNET_HashCode trail_id)
1092 struct P2PPendingMessage *pending;
1093 struct PeerTrailSetupResultMessage *tsrm;
1094 struct GNUNET_PeerIdentity *peer_list;
1097 msize = sizeof (struct PeerTrailSetupResultMessage) +
1098 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1100 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1106 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1108 GNUNET_STATISTICS_update (GDS_stats,
1109 gettext_noop ("# P2P messages dropped due to full queue"),
1113 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1114 pending->importance = 0;
1115 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1116 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1117 pending->msg = &tsrm->header;
1118 tsrm->header.size = htons (msize);
1119 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1120 tsrm->querying_peer = querying_peer;
1121 tsrm->finger_identity = finger;
1122 tsrm->is_predecessor = htonl (is_predecessor);
1123 tsrm->trail_id = trail_id;
1124 tsrm->ulitmate_destination_finger_value =
1125 GNUNET_htonll (ultimate_destination_finger_value);
1126 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1128 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1130 /* Send the message to chosen friend. */
1131 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1132 target_friend->pending_count++;
1133 process_friend_queue (target_friend);
1138 * Send trail rejection message to target friend
1139 * @param source_peer Peer which is trying to setup the trail.
1140 * @param ultimate_destination_finger_value Peer closest to this value will be
1141 * @a source_peer's finger
1142 * @param congested_peer Peer which sent this message as it is congested.
1143 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1144 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1145 * by congested_peer. This does NOT include @a source_peer
1146 * and congested_peer.
1147 * @param trail_length Total number of peers in trail_peer_list, NOT including
1148 * @a source_peer and @a congested_peer
1149 * @param trail_id Unique identifier of this trail.
1150 * @param congestion_timeout Duration given by congested peer as an estimate of
1151 * how long it may remain congested.
1154 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1155 uint64_t ultimate_destination_finger_value,
1156 struct GNUNET_PeerIdentity congested_peer,
1157 unsigned int is_predecessor,
1158 const struct GNUNET_PeerIdentity *trail_peer_list,
1159 unsigned int trail_length,
1160 struct GNUNET_HashCode trail_id,
1161 struct FriendInfo *target_friend,
1162 const struct GNUNET_TIME_Relative congestion_timeout)
1164 struct PeerTrailRejectionMessage *trm;
1165 struct P2PPendingMessage *pending;
1166 struct GNUNET_PeerIdentity *peer_list;
1169 msize = sizeof (struct PeerTrailRejectionMessage) +
1170 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1172 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1178 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1180 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1184 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1185 pending->importance = 0;
1186 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1187 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1188 pending->msg = &trm->header;
1189 trm->header.size = htons (msize);
1190 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1191 trm->source_peer = source_peer;
1192 trm->congested_peer = congested_peer;
1193 trm->congestion_time = congestion_timeout;
1194 trm->is_predecessor = htonl (is_predecessor);
1195 trm->trail_id = trail_id;
1196 trm->ultimate_destination_finger_value =
1197 GNUNET_htonll (ultimate_destination_finger_value);
1199 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1200 if (trail_length > 0)
1202 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1205 /* Send the message to chosen friend. */
1206 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1207 target_friend->pending_count++;
1208 process_friend_queue (target_friend);
1213 * Construct a verify successor message and forward it to target_friend.
1214 * @param source_peer Peer which wants to verify its successor.
1215 * @param successor Peer which is @a source_peer's current successor.
1216 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1217 * NOT including them.
1218 * @param trail List of peers which are part of trail to reach from @a source_peer
1219 * to @a successor, NOT including them.
1220 * @param trail_length Total number of peers in @a trail.
1221 * @param target_friend Next friend to get this message.
1224 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1225 struct GNUNET_PeerIdentity successor,
1226 struct GNUNET_HashCode trail_id,
1227 struct GNUNET_PeerIdentity *trail,
1228 unsigned int trail_length,
1229 struct FriendInfo *target_friend)
1231 struct PeerVerifySuccessorMessage *vsm;
1232 struct P2PPendingMessage *pending;
1233 struct GNUNET_PeerIdentity *peer_list;
1236 msize = sizeof (struct PeerVerifySuccessorMessage) +
1237 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1238 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1244 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1246 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1250 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1251 pending->importance = 0; /* FIXME */
1252 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1253 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1254 pending->msg = &vsm->header;
1255 vsm->header.size = htons (msize);
1256 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1257 vsm->source_peer = source_peer;
1258 vsm->successor = successor;
1259 vsm->trail_id = trail_id;
1260 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1261 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1263 /* Send the message to chosen friend. */
1264 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1265 target_friend->pending_count++;
1266 process_friend_queue (target_friend);
1271 * FIXME: In every function we pass target friend except for this one.
1272 * so, either change everything or this one. also, should se just store
1273 * the pointer to friend in routing table rather than gnunet_peeridentity.
1274 * if yes then we should keep friend info in.h andmake lot of changes.
1275 * Construct a trail teardown message and forward it to target friend.
1276 * @param trail_id Unique identifier of the trail.
1277 * @param trail_direction Direction of trail.
1278 * @param target_friend Friend to get this message.
1281 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1282 unsigned int trail_direction,
1283 struct GNUNET_PeerIdentity peer)
1285 struct PeerTrailTearDownMessage *ttdm;
1286 struct P2PPendingMessage *pending;
1287 struct FriendInfo *target_friend;
1290 msize = sizeof (struct PeerTrailTearDownMessage);
1292 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1298 /*FIXME:In what case friend can be null. ?*/
1299 if (NULL == (target_friend =
1300 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1303 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1305 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1309 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1310 pending->importance = 0; /* FIXME */
1311 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1312 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1313 pending->msg = &ttdm->header;
1314 ttdm->header.size = htons (msize);
1315 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1316 ttdm->trail_id = trail_id;
1317 ttdm->trail_direction = htonl (trail_direction);
1319 /* Send the message to chosen friend. */
1320 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1321 target_friend->pending_count++;
1322 process_friend_queue (target_friend);
1327 * Construct a verify successor result message and send it to target_friend
1328 * @param querying_peer Peer which sent the verify successor message.
1329 * @param source_successor Current_successor of @a querying_peer.
1330 * @param current_predecessor Current predecessor of @a successor. Could be same
1331 * or different from @a querying_peer.
1332 * @param trail_id Unique identifier of the trail from @a querying_peer to
1333 * @a successor, NOT including them.
1334 * @param trail List of peers which are part of trail from @a querying_peer to
1335 * @a successor, NOT including them.
1336 * @param trail_length Total number of peers in @a trail
1337 * @param trail_direction Direction in which we are sending the message. In this
1338 * case we are sending result from @a successor to @a querying_peer.
1339 * @param target_friend Next friend to get this message.
1342 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1343 struct GNUNET_PeerIdentity current_successor,
1344 struct GNUNET_PeerIdentity probable_successor,
1345 struct GNUNET_HashCode trail_id,
1346 const struct GNUNET_PeerIdentity *trail,
1347 unsigned int trail_length,
1348 enum GDS_ROUTING_trail_direction trail_direction,
1349 struct FriendInfo *target_friend)
1351 struct PeerVerifySuccessorResultMessage *vsmr;
1352 struct P2PPendingMessage *pending;
1353 struct GNUNET_PeerIdentity *peer_list;
1356 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1357 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1359 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1365 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1367 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1371 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1372 pending->importance = 0; /* FIXME */
1373 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1374 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1375 pending->msg = &vsmr->header;
1376 vsmr->header.size = htons (msize);
1377 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1378 vsmr->querying_peer = querying_peer;
1379 vsmr->current_successor = current_successor;
1380 vsmr->probable_successor = probable_successor;
1381 vsmr->trail_direction = htonl (trail_direction);
1382 vsmr->trail_id = trail_id;
1383 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1384 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1386 /* Send the message to chosen friend. */
1387 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1388 target_friend->pending_count++;
1389 process_friend_queue (target_friend);
1394 * Construct a notify new successor message and send it to target_friend
1395 * @param source_peer Peer which wants to notify to its new successor that it
1396 * could be its predecessor.
1397 * @param successor New successor of @a source_peer
1398 * @param successor_trail List of peers in Trail to reach from
1399 * @a source_peer to @a new_successor, NOT including
1401 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1402 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1403 * @param target_friend Next friend to get this message.
1406 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1407 struct GNUNET_PeerIdentity successor,
1408 const struct GNUNET_PeerIdentity *successor_trail,
1409 unsigned int successor_trail_length,
1410 struct GNUNET_HashCode succesor_trail_id,
1411 struct FriendInfo *target_friend)
1413 struct PeerNotifyNewSuccessorMessage *nsm;
1414 struct P2PPendingMessage *pending;
1415 struct GNUNET_PeerIdentity *peer_list;
1418 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1419 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1421 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1427 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1429 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1433 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1434 pending->importance = 0; /* FIXME */
1435 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1436 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1437 pending->msg = &nsm->header;
1438 nsm->header.size = htons (msize);
1439 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1440 nsm->new_successor = successor;
1441 nsm->source_peer = source_peer;
1442 nsm->trail_id = succesor_trail_id;
1444 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1445 memcpy (peer_list, successor_trail,
1446 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1448 /* Send the message to chosen friend. */
1449 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1450 target_friend->pending_count++;
1451 process_friend_queue (target_friend);
1456 * Construct an add_trail message and send it to target_friend
1457 * @param source_peer Source of the trail.
1458 * @param destination_peer Destination of the trail.
1459 * @param trail_id Unique identifier of the trail from
1460 * @a source_peer to @a destination_peer, NOT including the endpoints.
1461 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1462 * NOT including the endpoints.
1463 * @param trail_length Total number of peers in @a trail.
1464 * @param target_friend Next friend to get this message.
1467 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1468 struct GNUNET_PeerIdentity destination_peer,
1469 struct GNUNET_HashCode trail_id,
1470 const struct GNUNET_PeerIdentity *trail,
1471 unsigned int trail_length,
1472 struct FriendInfo *target_friend)
1474 struct PeerAddTrailMessage *adm;
1475 struct GNUNET_PeerIdentity *peer_list;
1476 struct P2PPendingMessage *pending;
1479 msize = sizeof (struct PeerAddTrailMessage) +
1480 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1482 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1488 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1490 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1494 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1495 pending->importance = 0; /* FIXME */
1496 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1497 adm = (struct PeerAddTrailMessage *) &pending[1];
1498 pending->msg = &adm->header;
1499 adm->header.size = htons (msize);
1500 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1501 adm->source_peer = source_peer;
1502 adm->destination_peer = destination_peer;
1503 adm->trail_id = trail_id;
1504 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1505 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1507 /* Send the message to chosen friend. */
1508 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1509 target_friend->pending_count++;
1510 process_friend_queue (target_friend);
1516 * Construct a trail compression message and send it to target_friend.
1517 * @param source_peer Source of the trail.
1518 * @param trail_id Unique identifier of trail.
1519 * @param first_friend First hop in compressed trail to reach from source to finger
1520 * @param target_friend Next friend to get this message.
1523 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1524 struct GNUNET_HashCode trail_id,
1525 struct GNUNET_PeerIdentity first_friend,
1526 struct FriendInfo *target_friend)
1528 struct P2PPendingMessage *pending;
1529 struct PeerTrailCompressionMessage *tcm;
1532 msize = sizeof (struct PeerTrailCompressionMessage);
1534 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1540 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1542 GNUNET_STATISTICS_update (GDS_stats,
1543 gettext_noop ("# P2P messages dropped due to full queue"),
1547 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1548 pending->importance = 0; /* FIXME */
1549 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1550 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1551 pending->msg = &tcm->header;
1552 tcm->header.size = htons (msize);
1553 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1554 tcm->source_peer = source_peer;
1555 tcm->new_first_friend = first_friend;
1556 tcm->trail_id = trail_id;
1558 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1559 target_friend->pending_count++;
1560 process_friend_queue (target_friend);
1566 * Search my location in trail. In case I am present more than once in the
1567 * trail (can happen during trail setup), then return my lowest index.
1568 * @param trail List of peers
1569 * @return my_index if found
1570 * -1 if no entry found.
1573 search_my_index (const struct GNUNET_PeerIdentity *trail,
1578 for (i = 0; i < trail_length; i++)
1580 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1589 * Check if the friend is congested or have reached maximum number of trails
1590 * it can be part of of.
1591 * @param friend Friend to be checked.
1592 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1593 * #GNUNET_YES if friend is either congested or have crossed threshold
1596 is_friend_congested (struct FriendInfo *friend)
1598 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1599 ((0 == GNUNET_TIME_absolute_get_remaining
1600 (friend->congestion_timestamp).rel_value_us)))
1608 * Select closest finger to value.
1609 * @param peer1 First peer
1610 * @param peer2 Second peer
1611 * @param value Value to be compare
1612 * @return Closest peer
1614 const static struct GNUNET_PeerIdentity *
1615 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1616 const struct GNUNET_PeerIdentity *peer2,
1619 uint64_t peer1_value;
1620 uint64_t peer2_value;
1622 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1623 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1624 peer1_value = GNUNET_ntohll (peer1_value);
1625 peer2_value = GNUNET_ntohll (peer2_value);
1627 if (peer1_value == value)
1632 if (peer2_value == value)
1637 if (peer2_value < peer1_value)
1639 if ((peer2_value < value) && (value < peer1_value))
1643 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1644 ((0 < value) && (value < peer2_value)))
1650 if (peer1_value < peer2_value)
1652 if ((peer1_value < value) && (value < peer2_value))
1656 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1657 ((0 < value) && (value < peer1_value)))
1667 * Select closest predecessor to value.
1668 * @param peer1 First peer
1669 * @param peer2 Second peer
1670 * @param value Value to be compare
1671 * @return Peer which precedes value in the network.
1673 const static struct GNUNET_PeerIdentity *
1674 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1675 const struct GNUNET_PeerIdentity *peer2,
1678 uint64_t peer1_value;
1679 uint64_t peer2_value;
1681 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1682 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1683 peer1_value = GNUNET_ntohll (peer1_value);
1684 peer2_value = GNUNET_ntohll (peer2_value);
1686 if (peer1_value == value)
1689 if (peer2_value == value)
1692 if (peer1_value < peer2_value)
1694 if ((peer1_value < value) && (value < peer2_value))
1698 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1699 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1705 if (peer2_value < peer1_value)
1707 if ((peer2_value < value) && (value < peer1_value))
1711 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1712 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1726 test_print_trail (struct GNUNET_PeerIdentity *trail,
1727 unsigned int trail_length)
1729 struct GNUNET_PeerIdentity print_peer;
1732 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1733 __FILE__, __func__,__LINE__,trail_length);
1734 for (i =0 ; i< trail_length; i++)
1736 print_peer = trail[i];
1737 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1738 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1745 * This is a test function to print all the entries of friend table.
1748 test_friend_peermap_print ()
1750 struct FriendInfo *friend;
1751 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1752 struct GNUNET_PeerIdentity print_peer;
1753 struct GNUNET_PeerIdentity key_ret;
1756 print_peer = my_identity;
1757 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1758 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1760 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1762 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1764 (const void **)&friend))
1766 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1767 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1768 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1776 * This is a test function, to print all the entries of finger table.
1779 test_finger_table_print()
1781 struct FingerInfo *finger;
1782 struct GNUNET_PeerIdentity print_peer;
1783 //struct Trail *trail;
1787 print_peer = my_identity;
1788 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1789 for (i = 0; i < MAX_FINGERS; i++)
1791 finger = &finger_table[i];
1793 if (GNUNET_NO == finger->is_present)
1796 print_peer = finger->finger_identity;
1797 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1798 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1801 for (j = 0; j < finger->trails_count; j++)
1803 trail = &finger->trail_list[j];
1804 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1805 struct Trail_Element *element;
1806 element = trail->trail_head;
1807 for (k = 0; k < trail->trail_length; k++)
1809 print_peer = element->peer;
1810 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1811 element = element->next;
1820 * Select the closest peer among two peers (which should not be same)
1821 * with respect to value and finger_table_index
1822 * NOTE: peer1 != peer2
1823 * @param peer1 First peer
1824 * @param peer2 Second peer
1825 * @param value Value relative to which we find the closest
1826 * @param is_predecessor Is value a predecessor or any other finger.
1827 * @return Closest peer among two peers.
1829 const static struct GNUNET_PeerIdentity *
1830 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1831 const struct GNUNET_PeerIdentity *peer2,
1833 unsigned int is_predecessor)
1835 if (1 == is_predecessor)
1836 return select_closest_predecessor (peer1, peer2, value);
1838 return select_closest_finger (peer1, peer2, value);
1843 * Iterate over the list of all the trails of a finger. In case the first
1844 * friend to reach the finger has reached trail threshold or is congested,
1845 * then don't select it. In case there multiple available good trails to reach
1846 * to Finger, choose the one with shortest trail length.
1847 * Note: We use length as parameter. But we can use any other suitable parameter
1849 * @param finger Finger
1850 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1851 * and trail length. NULL in case none of the trails are free.
1853 static struct Selected_Finger_Trail *
1854 select_finger_trail (struct FingerInfo *finger)
1856 struct FriendInfo *friend;
1857 struct Trail *iterator;
1858 struct Selected_Finger_Trail *finger_trail;
1860 unsigned int flag = 0;
1863 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1864 GNUNET_assert (finger->trails_count > 0);
1866 for (i = 0; i < finger->trails_count; i++)
1868 iterator = &finger->trail_list[i];
1870 /* No trail stored at this index. */
1871 if (GNUNET_NO == iterator->is_present)
1874 GNUNET_assert (NULL !=
1876 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1877 &iterator->trail_head->peer)));
1879 /* First friend to reach trail is not free. */
1880 if (GNUNET_YES == is_friend_congested (friend))
1889 finger_trail->trail_length = iterator->trail_length;
1890 finger_trail->friend = *friend;
1891 finger_trail->trail_id = iterator->trail_id;
1893 else if (finger_trail->trail_length > iterator->trail_length)
1895 finger_trail->friend = *friend;
1896 finger_trail->trail_id = iterator->trail_id;
1897 finger_trail->trail_length = iterator->trail_length;
1901 /* All the first friend in all the trails to reach to finger are either
1902 congested or have crossed trail threshold. */
1903 if (j == finger->trails_count)
1906 return finger_trail;
1911 * Compare FINGER entry with current successor. If finger's first friend of all
1912 * its trail is not congested and has not crossed trail threshold, then check
1913 * if finger peer identity is closer to final_destination_finger_value than
1914 * current_successor. If yes then update current_successor.
1915 * @param current_successor[in/out]
1919 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1921 struct FingerInfo *finger;
1922 const struct GNUNET_PeerIdentity *closest_peer;
1923 struct Selected_Finger_Trail *finger_trail;
1926 /* Iterate over finger table. */
1927 for (i = 0; i < MAX_FINGERS; i++)
1929 finger = &finger_table[i];
1931 if (GNUNET_NO == finger->is_present)
1934 /* FIXME write correct comment here */
1935 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1936 ¤t_closest_peer->best_known_destination))
1939 /* If I am my own finger, then ignore this finger. */
1940 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1943 /* FIXME: I think a peer should not select itself as its own identity ever.
1944 But it does select. Find out why??*/
1950 /* If finger is a friend, then do nothing. As we have already checked
1951 * for each friend in compare_friend_and_current_successor(). */
1952 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1953 &finger->finger_identity)))
1958 closest_peer = select_closest_peer (&finger->finger_identity,
1959 ¤t_closest_peer->best_known_destination,
1960 current_closest_peer->destination_finger_value,
1961 current_closest_peer->is_predecessor);
1963 if (&finger->finger_identity == closest_peer)
1965 /* Choose one of the trail to reach to finger. */
1966 finger_trail = select_finger_trail (finger);
1968 /* In case no trail found, ignore this finger. */
1969 if (NULL == finger_trail)
1972 current_closest_peer->best_known_destination = finger->finger_identity;
1973 current_closest_peer->next_hop = finger_trail->friend.id;
1974 current_closest_peer->trail_id = finger_trail->trail_id;
1975 GNUNET_free(finger_trail);
1983 * Compare friend entry with current successor.
1984 * If friend identity and current_successor is same, then do nothing.
1985 * If friend is not congested and has not crossed trail threshold, then check
1986 * if friend peer identity is closer to final_destination_finger_value than
1987 * current_successor. If yes then update current_successor.
1988 * @param cls closure
1989 * @param key current public key
1990 * @param value struct Closest_Peer
1991 * @return #GNUNET_YES if we should continue to iterate,
1992 * #GNUNET_NO if not.
1995 compare_friend_and_current_closest_peer (void *cls,
1996 const struct GNUNET_PeerIdentity *key,
1999 struct FriendInfo *friend = value;
2000 struct Closest_Peer *current_closest_peer = cls;
2001 const struct GNUNET_PeerIdentity *closest_peer;
2003 /* Friend is either congested or has crossed threshold. */
2004 if (GNUNET_YES == is_friend_congested (friend))
2007 /* If current_closest_peer and friend identity are same, then do nothing.*/
2008 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2009 ¤t_closest_peer->best_known_destination))
2015 closest_peer = select_closest_peer (&friend->id,
2016 ¤t_closest_peer->best_known_destination,
2017 current_closest_peer->destination_finger_value,
2018 current_closest_peer->is_predecessor);
2020 /* Is friend the closest successor? */
2021 if (&friend->id == closest_peer)
2023 current_closest_peer->best_known_destination = friend->id;
2024 current_closest_peer->next_hop = friend->id;
2032 * Initialize current_successor to my_identity.
2033 * @param my_identity My peer identity
2034 * @return Updated closest_peer
2036 static struct Closest_Peer
2037 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2038 uint64_t destination_finger_value,
2039 unsigned int is_predecessor)
2041 struct Closest_Peer current_closest_peer;
2043 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2044 current_closest_peer.destination_finger_value = destination_finger_value;
2045 current_closest_peer.is_predecessor = is_predecessor;
2046 current_closest_peer.next_hop = my_identity;
2047 current_closest_peer.best_known_destination = my_identity;
2049 return current_closest_peer;
2054 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2055 * peer. It could be because of the logic we wrote here. Verify if its correct.
2056 * If not then return immediate_successor.
2058 * Find the successor for destination_finger_value among my_identity, my
2059 * friends and my fingers. Don't consider friends or fingers which are either
2060 * congested or have crossed the threshold.
2061 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2063 * @param destination_finger_value Peer closest to this value will be the next successor.
2064 * @param is_predecessor Are we looking for predecessor or finger?
2065 * @return Successor It is never NULL, in case none of friend or finger is closest,
2066 * then we return my_identity.
2068 static struct Closest_Peer
2069 find_successor (uint64_t destination_finger_value,
2070 unsigned int is_predecessor)
2072 struct Closest_Peer current_closest_peer;
2074 /* Initialize current_successor to my_identity. */
2075 current_closest_peer = init_current_successor (my_identity,
2076 destination_finger_value,
2079 /* Compare each friend entry with current_successor and update current_successor
2080 * with friend if its closest. */
2083 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2084 &compare_friend_and_current_closest_peer,
2085 ¤t_closest_peer));
2087 /* Compare each finger entry with current_successor and update current_successor
2088 * with finger if its closest. */
2089 compare_finger_and_current_successor (¤t_closest_peer);
2091 return current_closest_peer;
2096 * Construct a Put message and send it to target_peer.
2097 * @param key Key for the content
2098 * @param block_type Type of the block
2099 * @param options Routing options
2100 * @param desired_replication_level Desired replication count
2101 * @param best_known_dest Peer to which this message should reach eventually,
2102 * as it is best known destination to me.
2103 * @param intermediate_trail_id Trail id in case
2104 * @param target_peer Peer to which this message will be forwarded.
2105 * @param hop_count Number of hops traversed so far.
2106 * @param put_path_length Total number of peers in @a put_path
2107 * @param put_path Number of peers traversed so far
2108 * @param expiration_time When does the content expire
2109 * @param data Content to store
2110 * @param data_size Size of content @a data in bytes
2113 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2114 enum GNUNET_BLOCK_Type block_type,
2115 enum GNUNET_DHT_RouteOption options,
2116 uint32_t desired_replication_level,
2117 struct GNUNET_PeerIdentity best_known_dest,
2118 struct GNUNET_HashCode intermediate_trail_id,
2119 struct GNUNET_PeerIdentity *target_peer,
2121 uint32_t put_path_length,
2122 struct GNUNET_PeerIdentity *put_path,
2123 struct GNUNET_TIME_Absolute expiration_time,
2124 const void *data, size_t data_size)
2126 struct PeerPutMessage *ppm;
2127 struct P2PPendingMessage *pending;
2128 struct FriendInfo *target_friend;
2129 struct GNUNET_PeerIdentity *pp;
2130 struct GNUNET_PeerIdentity next_hop;
2134 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2135 sizeof (struct PeerPutMessage);
2137 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2139 put_path_length = 0;
2140 msize = data_size + sizeof (struct PeerPutMessage);
2143 /* Should it be GNUNET_SERVER_MAX_MESSAGE_SIZE? */
2144 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2146 DEBUG("msize = %lu\n",msize);
2151 /* This is the first call made from clients file. So, we should search for the
2153 if (NULL == target_peer)
2156 struct Closest_Peer successor;
2158 memcpy (&key_value, key, sizeof (uint64_t));
2159 key_value = GNUNET_ntohll (key_value);
2161 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2162 best_known_dest = successor.best_known_destination;
2163 next_hop = successor.next_hop;
2164 intermediate_trail_id = successor.trail_id;
2166 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2168 /* I am the destination. */
2169 DEBUG("PUT destination is me = %s,key =%s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2170 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2171 block_type,data_size,data);
2175 GNUNET_assert (NULL !=
2177 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2181 GNUNET_assert (NULL !=
2183 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2186 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2187 pending->timeout = expiration_time;
2188 ppm = (struct PeerPutMessage *) &pending[1];
2189 pending->msg = &ppm->header;
2190 ppm->header.size = htons (msize);
2191 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2192 ppm->options = htonl (options);
2193 ppm->block_type = htonl (block_type);
2194 ppm->hop_count = htonl (hop_count + 1);
2195 ppm->desired_replication_level = htonl (desired_replication_level);
2196 ppm->put_path_length = htonl (put_path_length);
2197 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2198 ppm->best_known_destination = best_known_dest;
2201 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2202 if (put_path_length != 0)
2204 memcpy (pp, put_path,
2205 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2207 memcpy (&pp[put_path_length], data, data_size);
2208 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2209 target_friend->pending_count++;
2210 process_friend_queue (target_friend);
2215 * Construct a Get message and send it to target_peer.
2216 * @param key Key for the content
2217 * @param block_type Type of the block
2218 * @param options Routing options
2219 * @param desired_replication_level Desired replication count
2220 * @param best_known_dest Peer which should get this message. Same as target peer
2221 * if best_known_dest is a friend else its a finger.
2222 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2223 * in case it is a finger else set to 0.
2224 * @param target_peer Peer to which this message will be forwarded.
2225 * @param hop_count Number of hops traversed so far.
2226 * @param data Content to store
2227 * @param data_size Size of content @a data in bytes
2228 * @param get_path_length Total number of peers in @a get_path
2229 * @param get_path Number of peers traversed so far
2232 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2233 enum GNUNET_BLOCK_Type block_type,
2234 enum GNUNET_DHT_RouteOption options,
2235 uint32_t desired_replication_level,
2236 struct GNUNET_PeerIdentity best_known_dest,
2237 struct GNUNET_HashCode intermediate_trail_id,
2238 struct GNUNET_PeerIdentity *target_peer,
2240 uint32_t get_path_length,
2241 struct GNUNET_PeerIdentity *get_path)
2243 struct PeerGetMessage *pgm;
2244 struct P2PPendingMessage *pending;
2245 struct FriendInfo *target_friend;
2246 struct GNUNET_PeerIdentity *gp;
2249 msize = sizeof (struct PeerGetMessage) +
2250 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2252 //GNUNET_SERVER_MAX_MESSAGE_SIZE
2253 /* FIXME:TODO:URGENTHere you can try to optimize it a bit. In case the get path contains you
2254 or your friend then shorten the path. */
2255 /* In this case we don't make get_path_length = 0, as we need get path to
2256 * return the message back to querying client. */
2257 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2263 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
2265 /* This is the first time we got request from our own client file. */
2266 if (NULL == target_peer)
2269 struct Closest_Peer successor;
2271 memcpy (&key_value, key, sizeof (uint64_t));
2272 key_value = GNUNET_ntohll (key_value);
2273 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2275 best_known_dest = successor.best_known_destination;
2276 intermediate_trail_id = successor.trail_id;
2278 /* I am the destination. I have the data. */
2279 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2282 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2283 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2284 NULL, 0, 1, &my_identity, NULL,&my_identity);
2290 GNUNET_assert (NULL !=
2292 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2293 &successor.next_hop)));
2299 GNUNET_assert (NULL !=
2301 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); //FIXME: assertion fails.
2304 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2305 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2306 pending->importance = 0; /* FIXME */
2307 pgm = (struct PeerGetMessage *) &pending[1];
2308 pending->msg = &pgm->header;
2309 pgm->header.size = htons (msize);
2310 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2311 pgm->get_path_length = htonl (get_path_length);
2312 pgm->best_known_destination = best_known_dest;
2314 pgm->intermediate_trail_id = intermediate_trail_id;
2315 pgm->hop_count = htonl (hop_count + 1);
2316 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2318 if (get_path_length != 0)
2320 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2323 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2324 target_friend->pending_count++;
2325 process_friend_queue (target_friend);
2330 * Send the get result to requesting client.
2331 * @param key Key of the requested data.
2332 * @param type Block type
2333 * @param target_peer Next peer to forward the message to.
2334 * @param source_peer Peer which has the data for the key.
2335 * @param put_path_length Number of peers in @a put_path
2336 * @param put_path Path taken to put the data at its stored location.
2337 * @param get_path_length Number of peers in @a get_path
2338 * @param get_path Path taken to reach to the location of the key.
2339 * @param expiration When will this result expire?
2340 * @param data Payload to store
2341 * @param data_size Size of the @a data
2344 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2345 enum GNUNET_BLOCK_Type type,
2346 const struct GNUNET_PeerIdentity *target_peer,
2347 const struct GNUNET_PeerIdentity *source_peer,
2348 unsigned int put_path_length,
2349 const struct GNUNET_PeerIdentity *put_path,
2350 unsigned int get_path_length,
2351 const struct GNUNET_PeerIdentity *get_path,
2352 struct GNUNET_TIME_Absolute expiration,
2353 const void *data, size_t data_size)
2355 struct PeerGetResultMessage *get_result;
2356 struct GNUNET_PeerIdentity *paths;
2357 struct P2PPendingMessage *pending;
2358 struct FriendInfo *target_friend;
2359 int current_path_index;
2362 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2364 sizeof (struct PeerGetResultMessage);
2366 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2368 put_path_length = 0;
2369 msize = msize - put_path_length;
2373 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2378 DEBUG("GET RESULT FOR DATA_SIZE = %lu\n",msize);
2379 current_path_index = 0;
2380 if(get_path_length > 0)
2382 current_path_index = search_my_index(get_path, get_path_length);
2383 if (-1 == current_path_index)
2389 if (0 == current_path_index)
2391 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2392 get_path, put_path_length,
2393 put_path, type, data_size, data);
2397 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2398 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2399 pending->importance = 0;
2400 get_result = (struct PeerGetResultMessage *)&pending[1];
2401 pending->msg = &get_result->header;
2402 get_result->header.size = htons (msize);
2403 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2404 get_result->key = *key;
2405 get_result->querying_peer = *source_peer;
2406 get_result->expiration_time = expiration;
2407 get_result->get_path_length = htonl (get_path_length);
2408 get_result->put_path_length = htonl (put_path_length);
2409 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2410 memcpy (paths, put_path,
2411 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2412 memcpy (&paths[put_path_length], get_path,
2413 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2414 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2416 GNUNET_assert (NULL !=
2418 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2419 &get_path[current_path_index - 1])));
2420 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2421 target_friend->pending_count++;
2422 process_friend_queue (target_friend);
2427 * Randomly choose one of your friends (which is not congested and have not crossed
2428 * trail threshold) from the friend_peermap
2429 * @return Friend Randomly chosen friend.
2430 * NULL in case friend peermap is empty, or all the friends are either
2431 * congested or have crossed trail threshold.
2433 static struct FriendInfo *
2434 select_random_friend ()
2436 unsigned int current_size;
2439 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2440 struct GNUNET_PeerIdentity key_ret;
2441 struct FriendInfo *friend;
2443 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2446 if (0 == current_size)
2449 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2450 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2452 /* Iterate till you don't reach to index. */
2453 for (j = 0; j < index ; j++)
2454 GNUNET_assert (GNUNET_YES ==
2455 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2458 /* Reset the index in friend peermap to 0 as we reached to the end. */
2459 if (j == current_size)
2462 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2463 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2467 /* Get the friend stored at the index, j*/
2468 GNUNET_assert (GNUNET_YES ==
2469 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2471 (const void **)&friend));
2473 /* This friend is not congested and has not crossed trail threshold. */
2474 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2475 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2481 } while (j != index);
2483 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2489 * Compute 64 bit value of finger_identity corresponding to a finger index using
2491 * For all fingers, n.finger[i] = n + pow (2,i),
2492 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2493 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2494 * @param finger_index Index corresponding to which we calculate 64 bit value.
2495 * @return 64 bit value.
2498 compute_finger_identity_value (unsigned int finger_index)
2502 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2503 my_id64 = GNUNET_ntohll (my_id64);
2505 /* Are we looking for immediate predecessor? */
2506 if (PREDECESSOR_FINGER_ID == finger_index)
2507 return (my_id64 - 1);
2510 uint64_t add = (uint64_t)1 << finger_index;
2511 return (my_id64 + add);
2515 static struct GNUNET_TIME_Relative next_send_time;
2518 * Choose a random friend. Calculate the next finger identity to search,from
2519 * current_search_finger_index. Start looking for the trail to reach to
2520 * finger identity through this random friend.
2522 * @param cls closure for this task
2523 * @param tc the context under which the task is running
2526 send_find_finger_trail_message (void *cls,
2527 const struct GNUNET_SCHEDULER_TaskContext *tc)
2529 struct FriendInfo *target_friend;
2530 //struct GNUNET_TIME_Relative next_send_time;
2531 struct GNUNET_HashCode trail_id;
2532 struct GNUNET_HashCode intermediate_trail_id;
2533 unsigned int is_predecessor;
2534 uint64_t finger_id_value;
2536 /* Schedule another send_find_finger_trail_message task. */
2537 find_finger_trail_task =
2538 GNUNET_SCHEDULER_add_delayed (next_send_time,
2539 &send_find_finger_trail_message,
2542 /* No space in my routing table. (Source and destination peers also store entries
2543 * in their routing table). */
2544 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2548 target_friend = select_random_friend ();
2549 if (NULL == target_friend)
2554 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2556 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2561 /* Generate a unique trail id for trail we are trying to setup. */
2562 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2563 &trail_id, sizeof (trail_id));
2564 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2566 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2567 target_friend->id, target_friend, 0, NULL,
2568 is_predecessor, trail_id,
2569 intermediate_trail_id);
2574 * In case there are already maximum number of possible trails to reach to a
2575 * finger, then check if the new trail's length is lesser than any of the
2577 * If yes then replace that old trail by new trail.
2579 * Note: Here we are taking length as a parameter to choose the best possible
2580 * trail, but there could be other parameters also like:
2581 * 1. duration of existence of a trail - older the better.
2582 * 2. if the new trail is completely disjoint than the
2583 * other trails, then may be choosing it is better.
2585 * @param existing_finger
2586 * @param new_finger_trail
2587 * @param new_finger_trail_length
2588 * @param new_finger_trail_id
2591 select_and_replace_trail (struct FingerInfo *existing_finger,
2592 const struct GNUNET_PeerIdentity *new_trail,
2593 unsigned int new_trail_length,
2594 struct GNUNET_HashCode new_trail_id)
2596 struct Trail *trail_list_iterator;
2597 unsigned int largest_trail_length;
2598 unsigned int largest_trail_index;
2599 struct Trail_Element *trail_element;
2602 largest_trail_length = new_trail_length;
2603 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2605 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2607 for (i = 0; i < existing_finger->trails_count; i++)
2609 trail_list_iterator = &existing_finger->trail_list[i];
2610 if (trail_list_iterator->trail_length > largest_trail_length)
2612 largest_trail_length = trail_list_iterator->trail_length;
2613 largest_trail_index = i;
2617 /* New trail is not better than existing ones. Send trail teardown. */
2618 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2620 struct GNUNET_PeerIdentity next_hop;
2622 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2623 GDS_ROUTING_remove_trail (new_trail_id);
2624 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2625 GDS_ROUTING_SRC_TO_DEST,
2630 /* Send trail teardown message across the replaced trail. */
2631 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2632 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2633 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2634 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2635 GDS_ROUTING_SRC_TO_DEST,
2636 replace_trail->trail_head->peer);
2637 /* Free the trail. */
2638 while (NULL != (trail_element = replace_trail->trail_head))
2640 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2641 replace_trail->trail_tail, trail_element);
2642 GNUNET_free_non_null (trail_element);
2645 /* Add new trial at that location. */
2646 replace_trail->is_present = GNUNET_YES;
2647 replace_trail->trail_length = new_trail_length;
2648 replace_trail->trail_id = new_trail_id;
2649 //FIXME: Do we need to add pointers for head and tail.
2651 while (i < new_trail_length)
2653 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2654 element->peer = new_trail[i];
2656 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2657 replace_trail->trail_tail,
2664 * Check if the new trail to reach to finger is unique or do we already have
2665 * such a trail present for finger.
2666 * @param existing_finger Finger identity
2667 * @param new_trail New trail to reach @a existing_finger
2668 * @param trail_length Total number of peers in new_trail.
2669 * @return #GNUNET_YES if the new trail is unique
2670 * #GNUNET_NO if same trail is already present.
2673 is_new_trail_unique (struct FingerInfo *existing_finger,
2674 const struct GNUNET_PeerIdentity *new_trail,
2675 unsigned int trail_length)
2677 struct Trail *trail_list_iterator;
2678 struct Trail_Element *trail_element;
2681 int trail_unique = GNUNET_NO;
2683 GNUNET_assert (existing_finger->trails_count > 0);
2685 /* Iterate over list of trails. */
2686 for (i = 0; i < existing_finger->trails_count; i++)
2688 trail_list_iterator = &existing_finger->trail_list[i];
2689 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2691 /* New trail and existing trail length are not same. */
2692 if (trail_list_iterator->trail_length != trail_length)
2694 trail_unique = GNUNET_YES;
2698 trail_element = trail_list_iterator->trail_head;
2699 for (j = 0; j < trail_list_iterator->trail_length; j++)
2701 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2702 &trail_element->peer))
2704 trail_unique = GNUNET_YES;
2707 trail_element = trail_element->next;
2710 trail_unique = GNUNET_NO;
2713 return trail_unique;
2718 * Add a new trail to existing finger. This function is called only when finger
2719 * is not my own identity or a friend.
2720 * @param existing_finger Finger
2721 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2722 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2723 * @param new_finger_trail_id Unique identifier of the trail.
2726 add_new_trail (struct FingerInfo *existing_finger,
2727 const struct GNUNET_PeerIdentity *new_trail,
2728 unsigned int new_trail_length,
2729 struct GNUNET_HashCode new_trail_id)
2731 struct Trail *trail_list_iterator;
2732 struct FriendInfo *first_friend;
2735 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2741 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2742 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2743 trail_list_iterator->trail_id = new_trail_id;
2744 trail_list_iterator->trail_length = new_trail_length;
2745 existing_finger->trails_count++;
2746 trail_list_iterator->is_present = GNUNET_YES;
2748 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2749 &existing_finger->finger_identity)));
2750 /* If finger is a friend then we never call this function. */
2751 GNUNET_assert (new_trail_length > 0);
2753 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2755 first_friend->trails_count++;
2757 for (i = 0; i < new_trail_length; i++)
2759 struct Trail_Element *element;
2761 element = GNUNET_new (struct Trail_Element);
2762 element->peer = new_trail[i];
2763 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2764 trail_list_iterator->trail_tail,
2767 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2773 * FIXME Check if this function is called for opposite direction if yes then
2774 * take it as parameter.
2775 * Get the next hop to send trail teardown message from routing table and
2776 * then delete the entry from routing table. Send trail teardown message for a
2777 * specific trail of a finger.
2778 * @param finger Finger whose trail is to be removed.
2779 * @param trail List of peers in trail from me to a finger, NOT including
2783 send_trail_teardown (struct FingerInfo *finger,
2784 struct Trail *trail)
2786 struct FriendInfo *friend;
2787 struct GNUNET_PeerIdentity *next_hop;
2789 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2790 GDS_ROUTING_SRC_TO_DEST);
2792 if (NULL == next_hop)
2797 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2800 GNUNET_assert (trail->is_present == GNUNET_YES);
2802 /* Finger is not a friend. */
2803 if (trail->trail_length > 0)
2805 GNUNET_assert (NULL != (friend =
2806 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2807 &trail->trail_head->peer)));
2811 GNUNET_assert (NULL != (friend =
2812 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2813 &finger->finger_identity)));
2816 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2817 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2818 friend->trails_count--;
2819 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2820 GDS_ROUTING_SRC_TO_DEST,
2826 * Send trail teardown message across all the trails to reach to finger.
2827 * @param finger Finger whose all the trail should be freed.
2830 send_all_finger_trails_teardown (struct FingerInfo *finger)
2834 for (i = 0; i < finger->trails_count; i++)
2836 struct Trail *trail;
2838 trail = &finger->trail_list[i];
2839 GNUNET_assert (trail->is_present == GNUNET_YES);
2840 send_trail_teardown (finger, trail);
2841 trail->is_present = GNUNET_NO;
2847 * Free a specific trail
2848 * @param trail List of peers to be freed.
2851 free_trail (struct Trail *trail)
2853 struct Trail_Element *trail_element;
2855 while (NULL != (trail_element = trail->trail_head))
2857 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2860 GNUNET_free_non_null (trail_element);
2862 trail->trail_head = NULL;
2863 trail->trail_tail = NULL;
2868 * Free finger and its trail.
2869 * @param finger Finger to be freed.
2872 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2874 struct Trail *trail;
2877 /* Free all the trails to reach to finger */
2878 for (i = 0; i < finger->trails_count; i++)
2880 trail = &finger->trail_list[i];
2881 //FIXME: Check if there are any missing entry in this list because of
2882 // how we insert. If not then no need of this check.
2883 if (GNUNET_NO == trail->is_present)
2886 if (trail->trail_length > 0)
2890 trail->is_present = GNUNET_NO;
2893 finger->is_present = GNUNET_NO;
2894 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2899 * Add a new entry in finger table at finger_table_index.
2900 * In case I am my own finger, then we don't have a trail. In case of a friend,
2901 * we have a trail with unique id and '0' trail length.
2902 * In case a finger is a friend, then increment the trails count of the friend.
2903 * @param finger_identity Peer Identity of new finger
2904 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2905 * @param finger_trail_length Total number of peers in @a finger_trail.
2906 * @param trail_id Unique identifier of the trail.
2907 * @param finger_table_index Index in finger table.
2910 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2911 const struct GNUNET_PeerIdentity *finger_trail,
2912 unsigned int finger_trail_length,
2913 struct GNUNET_HashCode trail_id,
2914 unsigned int finger_table_index)
2916 struct FingerInfo *new_entry;
2917 struct FriendInfo *first_trail_hop;
2918 struct Trail *trail;
2921 new_entry = GNUNET_new (struct FingerInfo);
2922 new_entry->finger_identity = finger_identity;
2923 new_entry->finger_table_index = finger_table_index;
2924 new_entry->is_present = GNUNET_YES;
2926 /* If the new entry is my own identity. */
2927 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2930 new_entry->trails_count = 0;
2931 finger_table[finger_table_index] = *new_entry;
2932 GNUNET_free (new_entry);
2936 /* If finger is a friend, then we don't actually have a trail.
2937 * Just a trail id */
2938 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2941 new_entry->trail_list[0].trail_id = trail_id;
2942 new_entry->trails_count = 1;
2943 new_entry->trail_list[0].is_present = GNUNET_YES;
2944 new_entry->trail_list[0].trail_length = 0;
2945 new_entry->trail_list[0].trail_head = NULL;
2946 new_entry->trail_list[0].trail_tail = NULL;
2947 finger_table[finger_table_index] = *new_entry;
2948 GNUNET_assert (NULL !=
2950 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2951 &finger_identity)));
2953 first_trail_hop->trails_count++;
2954 GNUNET_free (new_entry);
2958 GNUNET_assert (NULL !=
2960 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2961 &finger_trail[0])));
2962 new_entry->trails_count = 1;
2963 first_trail_hop->trails_count++;
2965 /* Copy the finger trail into trail. */
2966 trail = GNUNET_new (struct Trail);
2967 while (i < finger_trail_length)
2969 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2971 element->next = NULL;
2972 element->prev = NULL;
2973 element->peer = finger_trail[i];
2974 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2980 /* Add trail to trail list. */
2981 new_entry->trail_list[0].trail_head = trail->trail_head;
2982 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2983 new_entry->trail_list[0].trail_length = finger_trail_length;
2984 new_entry->trail_list[0].trail_id = trail_id;
2985 new_entry->trail_list[0].is_present = GNUNET_YES;
2986 finger_table[finger_table_index] = *new_entry;
2987 GNUNET_free (new_entry);
2993 * Scan the trail to check if there is any other friend in the trail other than
2994 * first hop. If yes then shortcut the trail, send trail compression message to
2995 * peers which are no longer part of trail and send back the updated trail
2996 * and trail_length to calling function.
2997 * @param finger_identity Finger whose trail we will scan.
2998 * @param finger_trail [in, out] Trail to reach from source to finger,
2999 * @param finger_trail_length Total number of peers in original finger_trail.
3000 * @param finger_trail_id Unique identifier of the finger trail.
3001 * @return updated trail length in case we shortcut the trail, else original
3004 static struct GNUNET_PeerIdentity *
3005 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
3006 const struct GNUNET_PeerIdentity *trail,
3007 unsigned int trail_length,
3008 struct GNUNET_HashCode trail_id,
3009 int *new_trail_length)
3011 struct FriendInfo *target_friend;
3012 struct GNUNET_PeerIdentity *new_trail;
3015 /* I am my own finger. */
3016 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3018 *new_trail_length = 0;
3022 if (0 == trail_length)
3024 *new_trail_length = 0;
3028 /* If finger identity is a friend. */
3029 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3031 *new_trail_length = 0;
3033 /* If there is trail to reach this finger/friend */
3034 if (trail_length > 0)
3036 /* Finger is your first friend. */
3037 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3038 GNUNET_assert (NULL !=
3040 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3044 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3045 trail_id, finger_identity,
3051 /* For other cases, when its neither a friend nor my own identity.*/
3052 for (i = trail_length - 1; i > 0; i--)
3054 /* If the element at this index in trail is a friend. */
3055 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3057 struct FriendInfo *target_friend;
3060 GNUNET_assert (NULL !=
3062 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3064 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3065 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3070 /* Copy the trail from index i to index (trail_length -1) into a new trail
3071 * and update new trail length */
3072 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3073 while (i < trail_length)
3075 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3079 *new_trail_length = j+1;
3084 /* If we did not compress the trail, return the original trail back.*/
3085 *new_trail_length = trail_length;
3086 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3087 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3093 * Periodic task to verify current successor. There can be multiple trails to reach
3094 * to successor, choose the shortest one and send verify successor message
3095 * across that trail.
3096 * @param cls closure for this task
3097 * @param tc the context under which the task is running
3100 send_verify_successor_message (void *cls,
3101 const struct GNUNET_SCHEDULER_TaskContext *tc)
3103 struct FriendInfo *target_friend;
3104 struct GNUNET_HashCode trail_id;
3106 struct GNUNET_TIME_Relative next_send_time;
3107 struct Trail *trail;
3108 struct Trail_Element *element;
3109 unsigned int trail_length;
3111 struct FingerInfo *successor;
3113 /* Schedule another send_find_finger_trail_message task. */
3114 next_send_time.rel_value_us =
3115 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3116 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3117 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3118 send_verify_successor_task =
3119 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3122 successor = &finger_table[0];
3123 for (i = 0; i < successor->trails_count; i++)
3125 trail = &successor->trail_list[i];
3126 if(GNUNET_YES == trail->is_present)
3130 if (i == successor->trails_count)
3133 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3134 &successor->finger_identity));
3136 /* Trail stored at this index. */
3137 GNUNET_assert (GNUNET_YES == trail->is_present);
3139 trail_id = trail->trail_id;
3140 trail_length = trail->trail_length;
3142 if (trail_length > 0)
3144 /* Copy the trail into peer list. */
3145 struct GNUNET_PeerIdentity peer_list[trail_length];
3147 element = trail->trail_head;
3148 while (j < trail_length)
3150 peer_list[j] = element->peer;
3151 element = element->next;
3155 GNUNET_assert (NULL != (target_friend =
3156 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3158 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3159 successor->finger_identity,
3160 trail_id, peer_list, trail_length,
3166 GNUNET_assert (NULL != (target_friend =
3167 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3168 &successor->finger_identity)));
3169 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3170 successor->finger_identity,
3179 * Update the current search finger index.
3181 * FIXME document parameters!
3184 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3185 unsigned int finger_table_index)
3187 struct FingerInfo *successor;
3189 /* FIXME correct this: only move current index periodically */
3190 if (finger_table_index != current_search_finger_index)
3193 successor = &finger_table[0];
3194 GNUNET_assert (GNUNET_YES == successor->is_present);
3196 /* We were looking for immediate successor. */
3197 if (0 == current_search_finger_index)
3199 /* Start looking for immediate predecessor. */
3200 current_search_finger_index = PREDECESSOR_FINGER_ID;
3202 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3204 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3205 send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3211 current_search_finger_index = current_search_finger_index - 1;
3217 * Get the least significant bit set in val.
3220 * @return Position of first bit set, 65 in case of error.
3223 find_set_bit (uint64_t val)
3243 return 65; /* Some other bit was set to 1 as well. */
3250 * Calculate finger_table_index from initial 64 bit finger identity value that
3251 * we send in trail setup message.
3252 * @param ultimate_destination_finger_value Value that we calculated from our
3253 * identity and finger_table_index.
3254 * @param is_predecessor Is the entry for predecessor or not?
3255 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3256 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3259 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3260 unsigned int is_predecessor)
3264 unsigned int finger_table_index;
3266 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3267 my_id64 = GNUNET_ntohll (my_id64);
3269 /* Is this a predecessor finger? */
3270 if (1 == is_predecessor)
3272 diff = my_id64 - ultimate_destination_finger_value;
3274 finger_table_index = PREDECESSOR_FINGER_ID;
3276 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3281 diff = ultimate_destination_finger_value - my_id64;
3282 finger_table_index = find_set_bit (diff);
3284 return finger_table_index;
3289 * Remove finger and its associated data structures from finger table.
3290 * @param finger Finger to be removed.
3293 remove_existing_finger (struct FingerInfo *existing_finger,
3294 unsigned int finger_table_index)
3296 struct FingerInfo *finger;
3298 finger = &finger_table[finger_table_index];
3299 GNUNET_assert (GNUNET_YES == finger->is_present);
3301 /* If I am my own finger, then we have no trails. */
3302 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3305 finger->is_present = GNUNET_NO;
3306 memset ((void *)&finger_table[finger_table_index], 0,
3307 sizeof (finger_table[finger_table_index]));
3311 /* For all other fingers, send trail teardown across all the trails to reach
3312 finger, and free the finger. */
3313 send_all_finger_trails_teardown (finger);
3314 free_finger (finger, finger_table_index);
3320 * Check if there is already an entry in finger_table at finger_table_index.
3321 * We get the finger_table_index from 64bit finger value we got from the network.
3322 * -- If yes, then select the closest finger.
3323 * -- If new and existing finger are same, then check if you can store more
3325 * -- If yes then add trail, else keep the best trails to reach to the
3327 * -- If the new finger is closest, remove the existing entry, send trail
3328 * teardown message across all the trails to reach the existing entry.
3329 * Add the new finger.
3330 * -- If new and existing finger are different, and existing finger is closest
3332 * -- Update current_search_finger_index.
3333 * @param finger_identity Peer Identity of new finger
3334 * @param finger_trail Trail to reach the new finger
3335 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3336 * @param is_predecessor Is this entry for predecessor in finger_table?
3337 * @param finger_value 64 bit value of finger identity that we got from network.
3338 * @param finger_trail_id Unique identifier of @finger_trail.
3341 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3342 const struct GNUNET_PeerIdentity *finger_trail,
3343 unsigned int finger_trail_length,
3344 unsigned int is_predecessor,
3345 uint64_t finger_value,
3346 struct GNUNET_HashCode finger_trail_id)
3348 struct FingerInfo *existing_finger;
3349 const struct GNUNET_PeerIdentity *closest_peer;
3350 struct FingerInfo *successor;
3351 int updated_finger_trail_length;
3352 unsigned int finger_table_index;
3354 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3355 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3357 /* Invalid finger_table_index. */
3358 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3360 GNUNET_break_op (0);
3364 /* New entry same as successor. */
3365 if ((0 != finger_table_index) &&
3366 (PREDECESSOR_FINGER_ID != finger_table_index))
3368 successor = &finger_table[0];
3369 if (GNUNET_NO == successor->is_present)
3371 GNUNET_break_op (0);
3374 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3375 &successor->finger_identity))
3377 current_search_finger_index = 0;
3378 /* We slow down the find_finger_trail_task as we have completed the circle. */
3379 next_send_time = GNUNET_TIME_STD_BACKOFF(next_send_time);
3384 struct FingerInfo prev_finger;
3385 prev_finger = finger_table[finger_table_index - 1];
3386 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3387 &prev_finger.finger_identity))
3389 current_search_finger_index--;
3394 existing_finger = &finger_table[finger_table_index];
3396 /* No entry present in finger_table for given finger map index. */
3397 if (GNUNET_NO == existing_finger->is_present)
3399 struct GNUNET_PeerIdentity *updated_trail;
3401 /* Shorten the trail if possible. */
3402 updated_finger_trail_length = finger_trail_length;
3403 updated_trail = scan_and_compress_trail (finger_identity, finger_trail,
3404 finger_trail_length,
3406 &updated_finger_trail_length);
3408 add_new_finger (finger_identity, updated_trail,
3409 updated_finger_trail_length,
3410 finger_trail_id, finger_table_index);
3411 GNUNET_free_non_null(updated_trail);
3412 update_current_search_finger_index (finger_identity,
3413 finger_table_index);
3418 /* If existing entry and finger identity are not same. */
3419 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3422 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3427 /* If the new finger is the closest peer. */
3428 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3430 struct GNUNET_PeerIdentity *updated_trail;
3431 /* Shorten the trail if possible. */
3432 updated_finger_trail_length = finger_trail_length;
3434 scan_and_compress_trail (finger_identity, finger_trail,
3435 finger_trail_length, finger_trail_id,
3436 &updated_finger_trail_length);
3437 remove_existing_finger (existing_finger, finger_table_index);
3438 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3439 finger_trail_id, finger_table_index);
3440 GNUNET_free_non_null((struct GNUNET_PeerIdentity *)updated_trail);
3444 /* Existing finger is the closest one. We need to send trail teardown
3445 across the trail setup in routing table of all the peers. */
3446 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3448 if (finger_trail_length > 0)
3449 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3450 GDS_ROUTING_SRC_TO_DEST,
3453 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3454 GDS_ROUTING_SRC_TO_DEST,
3461 /* If both new and existing entry are same as my_identity, then do nothing. */
3462 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3467 /* If the existing finger is not a friend. */
3469 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3470 &existing_finger->finger_identity))
3472 struct GNUNET_PeerIdentity *updated_trail;
3474 /* Shorten the trail if possible. */
3475 updated_finger_trail_length = finger_trail_length;
3477 scan_and_compress_trail (finger_identity, finger_trail,
3478 finger_trail_length, finger_trail_id,
3479 &updated_finger_trail_length);
3480 /* If there is space to store more trails. */
3481 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3482 add_new_trail (existing_finger, updated_trail,
3483 updated_finger_trail_length, finger_trail_id);
3485 select_and_replace_trail (existing_finger, updated_trail,
3486 updated_finger_trail_length, finger_trail_id);
3490 update_current_search_finger_index (finger_identity, finger_table_index);
3495 * Core handler for P2P put messages.
3496 * @param cls closure
3497 * @param peer sender of the request
3498 * @param message message
3499 * @return #GNUNET_OK to keep the connection open,
3500 * #GNUNET_SYSERR to close it (signal serious error)
3503 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3504 const struct GNUNET_MessageHeader *message)
3506 struct PeerPutMessage *put;
3507 struct GNUNET_PeerIdentity *put_path;
3508 struct GNUNET_PeerIdentity best_known_dest;
3509 struct GNUNET_HashCode intermediate_trail_id;
3510 struct GNUNET_PeerIdentity *next_hop;
3511 enum GNUNET_DHT_RouteOption options;
3512 struct GNUNET_HashCode test_key;
3516 size_t payload_size;
3519 msize = ntohs (message->size);
3520 if (msize < sizeof (struct PeerPutMessage))
3522 GNUNET_break_op (0);
3526 put = (struct PeerPutMessage *) message;
3527 putlen = ntohl (put->put_path_length);
3531 sizeof (struct PeerPutMessage) +
3532 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3534 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3536 GNUNET_break_op (0);
3539 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
3540 GNUNET_STATISTICS_update (GDS_stats,
3542 ("# Bytes received from other peers"), (int64_t) msize,
3545 best_known_dest = put->best_known_destination;
3546 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3547 payload = &put_path[putlen];
3548 options = ntohl (put->options);
3549 intermediate_trail_id = put->intermediate_trail_id;
3551 payload_size = msize - (sizeof (struct PeerPutMessage) +
3552 putlen * sizeof (struct GNUNET_PeerIdentity));
3554 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3555 payload, payload_size, &test_key))
3558 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3560 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3561 GNUNET_break_op (0);
3562 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3563 "PUT with key `%s' for block with key %s\n",
3564 put_s, GNUNET_h2s_full (&test_key));
3565 GNUNET_free (put_s);
3570 GNUNET_break_op (0);
3573 /* cannot verify, good luck */
3577 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3579 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3580 ntohl (put->block_type),
3582 NULL, 0, /* bloom filer */
3583 NULL, 0, /* xquery */
3584 payload, payload_size))
3586 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3587 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3590 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3591 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3592 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3593 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3594 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3595 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3597 GNUNET_break_op (0);
3602 /* extend 'put path' by sender */
3603 struct GNUNET_PeerIdentity pp[putlen + 1];
3604 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3606 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3613 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3614 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3616 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3617 GDS_ROUTING_SRC_TO_DEST);
3618 if (NULL == next_hop)
3620 GNUNET_STATISTICS_update (GDS_stats,
3621 gettext_noop ("# Next hop to forward the packet not found "
3622 "trail setup request, packet dropped."),
3624 return GNUNET_SYSERR;
3629 struct Closest_Peer successor;
3630 key_value = GNUNET_ntohll (key_value);
3631 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3632 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3633 *next_hop = successor.next_hop;
3634 intermediate_trail_id = successor.trail_id;
3635 best_known_dest = successor.best_known_destination;
3638 GDS_CLIENTS_process_put (options,
3639 ntohl (put->block_type),
3640 ntohl (put->hop_count),
3641 ntohl (put->desired_replication_level),
3643 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3648 /* I am the final destination */
3649 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3651 DEBUG("PUT destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(put->key)));
3652 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3653 &(put->key),putlen, pp, ntohl (put->block_type),
3654 payload_size, payload);
3658 GDS_NEIGHBOURS_send_put (&put->key,
3659 ntohl (put->block_type),ntohl (put->options),
3660 ntohl (put->desired_replication_level),
3661 best_known_dest, intermediate_trail_id, next_hop,
3662 ntohl (put->hop_count), putlen, pp,
3663 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3664 payload, payload_size);
3671 * Core handler for p2p get requests.
3673 * @param cls closure
3674 * @param peer sender of the request
3675 * @param message message
3676 * @return #GNUNET_OK to keep the connection open,
3677 * #GNUNET_SYSERR to close it (signal serious error)
3680 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3681 const struct GNUNET_MessageHeader *message)
3683 const struct PeerGetMessage *get;
3684 const struct GNUNET_PeerIdentity *get_path;
3685 struct GNUNET_PeerIdentity best_known_dest;
3686 struct GNUNET_HashCode intermediate_trail_id;
3687 struct GNUNET_PeerIdentity *next_hop;
3688 uint32_t get_length;
3692 msize = ntohs (message->size);
3693 if (msize < sizeof (struct PeerGetMessage))
3695 GNUNET_break_op (0);
3699 get = (const struct PeerGetMessage *)message;
3700 get_length = ntohl (get->get_path_length);
3701 best_known_dest = get->best_known_destination;
3702 intermediate_trail_id = get->intermediate_trail_id;
3703 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3706 sizeof (struct PeerGetMessage) +
3707 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3709 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3711 GNUNET_break_op (0);
3714 DEBUG("PUT FOR DATA_SIZE = %lu\n",msize);
3715 GNUNET_STATISTICS_update (GDS_stats,
3717 ("# Bytes received from other peers"), msize,
3720 /* Add sender to get path */
3721 struct GNUNET_PeerIdentity gp[get_length + 1];
3723 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3724 gp[get_length] = *peer;
3725 get_length = get_length + 1;
3727 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3728 key_value = GNUNET_ntohll (key_value);
3730 /* I am not the final destination. I am part of trail to reach final dest. */
3731 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3733 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3734 GDS_ROUTING_SRC_TO_DEST);
3735 if (NULL == next_hop)
3737 GNUNET_STATISTICS_update (GDS_stats,
3738 gettext_noop ("# Next hop to forward the packet not found "
3739 "GET request, packet dropped."),
3741 return GNUNET_SYSERR;
3746 struct Closest_Peer successor;
3748 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3749 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3750 *next_hop = successor.next_hop;
3751 best_known_dest = successor.best_known_destination;
3752 intermediate_trail_id = successor.trail_id;
3755 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3756 get->desired_replication_level, get->get_path_length,
3758 /* I am the final destination. */
3759 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3761 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(get->key)));
3762 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3764 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3765 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3766 get_length = get_length + 1;
3768 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3769 get_length, final_get_path,
3770 &final_get_path[get_length-2], &my_identity);
3774 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3775 get->desired_replication_level, best_known_dest,
3776 intermediate_trail_id, next_hop, 0,
3784 * Core handler for get result
3785 * @param cls closure
3786 * @param peer sender of the request
3787 * @param message message
3788 * @return #GNUNET_OK to keep the connection open,
3789 * #GNUNET_SYSERR to close it (signal serious error)
3792 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3793 const struct GNUNET_MessageHeader *message)
3795 const struct PeerGetResultMessage *get_result;
3796 const struct GNUNET_PeerIdentity *get_path;
3797 const struct GNUNET_PeerIdentity *put_path;
3798 const void *payload;
3799 size_t payload_size;
3801 unsigned int getlen;
3802 unsigned int putlen;
3803 int current_path_index;
3805 msize = ntohs (message->size);
3806 if (msize < sizeof (struct PeerGetResultMessage))
3808 GNUNET_break_op (0);
3812 get_result = (const struct PeerGetResultMessage *)message;
3813 getlen = ntohl (get_result->get_path_length);
3814 putlen = ntohl (get_result->put_path_length);
3817 sizeof (struct PeerGetResultMessage) +
3818 getlen * sizeof (struct GNUNET_PeerIdentity) +
3819 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3821 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3823 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3825 GNUNET_break_op (0);
3828 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3829 GNUNET_STATISTICS_update (GDS_stats,
3831 ("# Bytes received from other peers"), msize,
3834 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3835 get_path = &put_path[putlen];
3836 payload = (const void *) &get_path[getlen];
3837 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3838 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3840 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3842 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3843 getlen, get_path, putlen,
3844 put_path, get_result->type, payload_size, payload);
3849 current_path_index = search_my_index (get_path, getlen);
3850 if (-1 == current_path_index )
3853 return GNUNET_SYSERR;
3855 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3856 &get_path[current_path_index - 1],
3857 &(get_result->querying_peer), putlen, put_path,
3858 getlen, get_path, get_result->expiration_time,
3859 payload, payload_size);
3862 return GNUNET_SYSERR;
3867 * Find the next hop to pass trail setup message. First find the local best known
3868 * hop from your own identity, friends and finger. If you were part of trail,
3869 * then get the next hop from routing table. Compare next_hop from routing table
3870 * and local best known hop, and return the closest one to final_dest_finger_val
3871 * @param final_dest_finger_val 64 bit value of finger identity
3872 * @param intermediate_trail_id If you are part of trail to reach to some other
3873 * finger, then it is the trail id to reach to
3874 * that finger, else set to 0.
3875 * @param is_predecessor Are we looking for closest successor or predecessor.
3876 * @param current_dest In case you are part of trail, then finger to which
3877 * we should forward the message. Else my own identity
3878 * @return Closest Peer for @a final_dest_finger_val
3880 static struct Closest_Peer
3881 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3882 struct GNUNET_HashCode intermediate_trail_id,
3883 unsigned int is_predecessor,
3884 struct GNUNET_PeerIdentity prev_hop,
3885 struct GNUNET_PeerIdentity source,
3886 struct GNUNET_PeerIdentity *current_dest)
3888 struct Closest_Peer peer;
3890 /* Find a local best known peer. */
3891 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3893 /* Am I just a part of a trail towards a finger (current_destination)? */
3894 /* Select best successor among one found locally and current_destination
3895 * that we got from network.*/
3896 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3897 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3900 const struct GNUNET_PeerIdentity *closest_peer;
3902 closest_peer = select_closest_peer (&peer.best_known_destination,
3904 final_dest_finger_val,
3907 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3908 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3910 struct GNUNET_PeerIdentity *next_hop;
3912 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3913 GDS_ROUTING_SRC_TO_DEST);
3914 /* It may happen that trail teardown message got delayed and hence,
3915 the previous hop sent the message over intermediate trail id.In that
3916 case next_hop could be NULL. */
3917 if(NULL != next_hop)
3919 peer.next_hop = *next_hop;
3920 peer.best_known_destination = *current_dest;
3921 peer.trail_id = intermediate_trail_id;
3929 * Core handle for PeerTrailSetupMessage.
3930 * @param cls closure
3931 * @param message message
3932 * @param peer peer identity this notification is about
3933 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3936 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3937 const struct GNUNET_MessageHeader *message)
3939 const struct PeerTrailSetupMessage *trail_setup;
3940 const struct GNUNET_PeerIdentity *trail_peer_list;
3941 struct GNUNET_PeerIdentity current_dest;
3942 struct FriendInfo *target_friend;
3943 struct GNUNET_PeerIdentity source;
3944 uint64_t final_dest_finger_val;
3945 struct GNUNET_HashCode intermediate_trail_id;
3946 struct GNUNET_HashCode trail_id;
3947 unsigned int is_predecessor;
3948 uint32_t trail_length;
3952 msize = ntohs (message->size);
3953 if (msize < sizeof (struct PeerTrailSetupMessage))
3955 GNUNET_break_op (0);
3956 return GNUNET_SYSERR;
3959 trail_setup = (const struct PeerTrailSetupMessage *) message;
3960 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3961 sizeof (struct GNUNET_PeerIdentity);
3962 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3963 sizeof (struct GNUNET_PeerIdentity) != 0)
3965 GNUNET_break_op (0);
3969 GNUNET_STATISTICS_update (GDS_stats,
3971 ("# Bytes received from other peers"), msize,
3974 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3975 current_dest = trail_setup->best_known_destination;
3976 trail_id = trail_setup->trail_id;
3977 final_dest_finger_val =
3978 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3979 source = trail_setup->source_peer;
3980 is_predecessor = ntohl (trail_setup->is_predecessor);
3981 intermediate_trail_id = trail_setup->intermediate_trail_id;
3983 /* Did the friend insert its ID in the trail list? */
3984 if (trail_length > 0 &&
3985 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (*peer)))
3987 GNUNET_break_op (0);
3988 return GNUNET_SYSERR;
3991 /* If I was the source and got the message back, then set trail length to 0.*/
3992 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3994 /* IF (!) the peers know the destinations of the trails in their routing
3997 * This shoud only happen after 1 hop, since the first message is sent
3998 * to random friend, and we can happen to be on the best trail to the dest.
3999 * If the first friend selects someone else, the request should never come
4004 // GNUNET_break_op (1 == trail_length);
4008 /* Check if you are present in the trail seen so far? */
4009 for (i = 0; i < trail_length ; i++)
4011 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4013 //Here if you already were present in the trail. then you
4014 // should trail length to i + 1
4021 /* Is my routing table full? */
4022 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4024 GNUNET_assert (NULL !=
4026 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4027 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4028 my_identity, is_predecessor,
4029 trail_peer_list, trail_length,
4030 trail_id, target_friend,
4031 CONGESTION_TIMEOUT);
4035 /* Get the next hop to forward the trail setup request. */
4036 struct Closest_Peer next_peer =
4037 get_local_best_known_next_hop (final_dest_finger_val,
4038 intermediate_trail_id,
4044 /* Am I the final destination? */
4045 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4048 /* If I was not the source of this message for which now I am destination */
4049 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4051 GDS_ROUTING_add (trail_id, *peer, my_identity);
4054 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4056 finger_table_add (my_identity, NULL, 0, is_predecessor,
4057 final_dest_finger_val, trail_id);
4061 if (trail_length > 0)
4062 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4064 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4065 if (NULL == target_friend)
4067 GNUNET_break_op (0);
4068 return GNUNET_SYSERR;
4071 GDS_NEIGHBOURS_send_trail_setup_result (source,
4073 target_friend, trail_length,
4076 final_dest_finger_val,trail_id);
4078 else /* I'm not the final destination. */
4080 GNUNET_assert (NULL !=
4082 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4083 &next_peer.next_hop)));
4085 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4087 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &trail_peer_list[trail_length -1 ]))
4089 GDS_NEIGHBOURS_send_trail_setup (source,
4090 final_dest_finger_val,
4091 next_peer.best_known_destination,
4092 target_friend, trail_length, trail_peer_list,
4093 is_predecessor, trail_id,
4094 next_peer.trail_id);
4097 /* Add yourself to list of peers. */
4098 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4100 memcpy (peer_list, trail_peer_list,
4101 trail_length * sizeof (struct GNUNET_PeerIdentity));
4102 peer_list[trail_length] = my_identity;
4104 GDS_NEIGHBOURS_send_trail_setup (source,
4105 final_dest_finger_val,
4106 next_peer.best_known_destination,
4107 target_friend, trail_length + 1, peer_list,
4108 is_predecessor, trail_id,
4109 next_peer.trail_id);
4113 GDS_NEIGHBOURS_send_trail_setup (source,
4114 final_dest_finger_val,
4115 next_peer.best_known_destination,
4116 target_friend, 0, NULL,
4117 is_predecessor, trail_id,
4118 next_peer.trail_id);
4124 /* FIXME: here we are calculating my_index and comparing also in this function.
4125 And we are doing it again here in this function. Re factor the code. */
4127 * FIXME: Should we call this function everywhere in all the handle functions
4128 * where we have a trail to verify from or a trail id. something like
4129 * if prev hop is not same then drop the message.
4130 * Check if sender_peer and peer from which we should receive the message are
4131 * same or different.
4132 * @param trail_peer_list List of peers in trail
4133 * @param trail_length Total number of peers in @a trail_peer_list
4134 * @param sender_peer Peer from which we got the message.
4135 * @param finger_identity Finger to which trail is setup. It is not part of trail.
4136 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
4137 * message are different.
4138 * #GNUNET_NO if sender_peer and peer from which we should receive the
4139 * message are different.
4142 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
4143 unsigned int trail_length,
4144 const struct GNUNET_PeerIdentity *sender_peer,
4145 struct GNUNET_PeerIdentity finger_identity,
4146 struct GNUNET_PeerIdentity source_peer)
4150 /* I am the source peer. */
4151 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4154 /* Is the first element of the trail is sender_peer.*/
4155 if (trail_length > 0)
4157 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4163 /* Is finger the sender peer? */
4164 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4171 /* Get my current location in the trail. */
4172 my_index = search_my_index (trail_peer_list, trail_length);
4176 /* I am the last element in the trail. */
4177 if ((trail_length - 1) == my_index)
4179 /* Is finger the sender_peer? */
4180 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4186 /* Is peer after me in trail the sender peer? */
4187 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4188 &trail_peer_list[my_index + 1]))
4198 * FIXME: we should also add a case where we search if we are present in the trail
4200 * Core handle for p2p trail setup result messages.
4202 * @param message message
4203 * @param peer sender of this message.
4204 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4207 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4208 const struct GNUNET_MessageHeader *message)
4210 const struct PeerTrailSetupResultMessage *trail_result;
4211 const struct GNUNET_PeerIdentity *trail_peer_list;
4212 struct GNUNET_PeerIdentity next_hop;
4213 struct FriendInfo *target_friend;
4214 struct GNUNET_PeerIdentity querying_peer;
4215 struct GNUNET_PeerIdentity finger_identity;
4216 uint32_t trail_length;
4217 uint64_t ulitmate_destination_finger_value;
4218 uint32_t is_predecessor;
4219 struct GNUNET_HashCode trail_id;
4223 msize = ntohs (message->size);
4224 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4226 GNUNET_break_op (0);
4230 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4231 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4232 sizeof (struct GNUNET_PeerIdentity);
4233 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4234 sizeof (struct GNUNET_PeerIdentity) != 0)
4236 GNUNET_break_op (0);
4240 GNUNET_STATISTICS_update (GDS_stats,
4242 ("# Bytes received from other peers"), msize,
4245 is_predecessor = ntohl (trail_result->is_predecessor);
4246 querying_peer = trail_result->querying_peer;
4247 finger_identity = trail_result->finger_identity;
4248 trail_id = trail_result->trail_id;
4249 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4250 ulitmate_destination_finger_value =
4251 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4253 /* FIXME: here we are calculating my_index and comparing also in this function.
4254 And we are doing it again here in this function. Re factor the code. */
4255 /* Ensure that sender peer is the peer from which we were expecting the message. */
4257 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
4259 peer, finger_identity, querying_peer))
4261 GNUNET_break_op (0);
4262 return GNUNET_SYSERR;
4266 /*TODO:URGENT Check if I am already present in the trail. If yes then its an error,
4267 as in trail setup we ensure that it should never happen. */
4268 /* Am I the one who initiated the query? */
4269 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4271 /* If I am my own finger identity, error. */
4272 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4274 GNUNET_break_op (0);
4275 return GNUNET_SYSERR;
4277 GDS_ROUTING_add (trail_id, my_identity, *peer);
4278 finger_table_add (finger_identity, trail_peer_list, trail_length,
4279 is_predecessor, ulitmate_destination_finger_value, trail_id);
4283 /* Get my location in the trail. */
4284 my_index = search_my_index (trail_peer_list, trail_length);
4288 return GNUNET_SYSERR;
4292 next_hop = trail_result->querying_peer;
4294 next_hop = trail_peer_list[my_index - 1];
4296 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4297 if (NULL == target_friend)
4299 GNUNET_break_op (0);
4300 return GNUNET_SYSERR;
4303 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4304 &(trail_result->finger_identity))))
4306 GNUNET_break_op (0);
4307 return GNUNET_SYSERR;
4310 GDS_ROUTING_add (trail_id, next_hop, *peer);
4312 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4313 target_friend, trail_length, trail_peer_list,
4315 ulitmate_destination_finger_value,
4323 * @param trail Trail to be inverted
4324 * @param trail_length Total number of peers in the trail.
4325 * @return Updated trail
4327 static struct GNUNET_PeerIdentity *
4328 invert_trail (const struct GNUNET_PeerIdentity *trail,
4329 unsigned int trail_length)
4333 struct GNUNET_PeerIdentity *inverted_trail;
4335 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4338 j = trail_length - 1;
4339 while (i < trail_length)
4341 inverted_trail[i] = trail[j];
4346 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4347 &inverted_trail[0]));
4348 return inverted_trail;
4353 * Return the shortest trail among all the trails to reach to finger from me.
4354 * @param finger Finger
4355 * @param shortest_trail_length[out] Trail length of shortest trail from me
4357 * @return Shortest trail.
4359 static struct GNUNET_PeerIdentity *
4360 get_shortest_trail (struct FingerInfo *finger,
4361 unsigned int *trail_length)
4363 struct Trail *trail;
4364 unsigned int flag = 0;
4365 unsigned int shortest_trail_index = 0;
4366 int shortest_trail_length = -1;
4367 struct Trail_Element *trail_element;
4368 struct GNUNET_PeerIdentity *trail_list;
4371 trail = GNUNET_new (struct Trail);
4373 /* Get the shortest trail to reach to current successor. */
4374 for (i = 0; i < finger->trails_count; i++)
4376 trail = &finger->trail_list[i];
4380 shortest_trail_index = i;
4381 shortest_trail_length = trail->trail_length;
4386 if (shortest_trail_length > trail->trail_length)
4388 shortest_trail_index = i;
4389 shortest_trail_length = trail->trail_length;
4394 /* Copy the shortest trail and return. */
4395 trail = &finger->trail_list[shortest_trail_index];
4396 trail_element = trail->trail_head;
4398 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4399 shortest_trail_length);
4401 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4403 trail_list[i] = trail_element->peer;
4406 GNUNET_assert(shortest_trail_length != -1);
4408 *trail_length = shortest_trail_length;
4414 * Check if trail_1 and trail_2 have any common element. If yes then join
4415 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4416 * @param trail_1 Trail from source to me, NOT including endpoints.
4417 * @param trail_1_len Total number of peers @a trail_1
4418 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4419 * @param trail_2_len Total number of peers @a trail_2
4420 * @param joined_trail_len Total number of peers in combined trail of trail_1
4422 * @return Joined trail.
4424 static struct GNUNET_PeerIdentity *
4425 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4426 unsigned int trail_1_len,
4427 struct GNUNET_PeerIdentity *trail_2,
4428 unsigned int trail_2_len,
4429 unsigned int *joined_trail_len)
4431 struct GNUNET_PeerIdentity *joined_trail;
4436 for (i = 0; i < trail_1_len; i++)
4438 for (j = 0; j < trail_2_len; j++)
4440 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4443 *joined_trail_len = i + (trail_2_len - j);
4444 joined_trail = GNUNET_malloc (*joined_trail_len *
4445 sizeof(struct GNUNET_PeerIdentity));
4448 /* Copy all the elements from 0 to i into joined_trail. */
4449 for(k = 0; k < (i+1); k++)
4451 joined_trail[k] = trail_1[k];
4454 /* Increment j as entry stored is same as entry stored at i*/
4457 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4458 while((k < *joined_trail_len) && (j < trail_2_len));
4460 joined_trail[k] = trail_2[j];
4465 return joined_trail;
4469 /* Here you should join the trails. */
4470 *joined_trail_len = trail_1_len + trail_2_len + 1;
4471 joined_trail = GNUNET_malloc (*joined_trail_len *
4472 sizeof(struct GNUNET_PeerIdentity));
4475 for(i = 0; i < trail_1_len;i++)
4477 joined_trail[i] = trail_1[i];
4480 joined_trail[i] = my_identity;
4483 for (j = 0; i < *joined_trail_len; i++,j++)
4485 joined_trail[i] = trail_2[j];
4488 return joined_trail;
4493 * Return the trail from source to my current predecessor. Check if source
4494 * is already part of the this trail, if yes then return the shorten trail.
4495 * @param current_trail Trail from source to me, NOT including the endpoints.
4496 * @param current_trail_length Number of peers in @a current_trail.
4497 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4498 * source to my predecessor, NOT including
4500 * @return Trail from source to my predecessor.
4502 static struct GNUNET_PeerIdentity *
4503 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4504 const struct GNUNET_PeerIdentity *trail_src_to_me,
4505 unsigned int trail_src_to_me_len,
4506 unsigned int *trail_src_to_curr_pred_length)
4508 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4509 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4510 unsigned int trail_me_to_curr_pred_length;
4511 struct FingerInfo *current_predecessor;
4515 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4517 /* Check if trail_src_to_me contains current_predecessor. */
4518 for (i = 0; i < trail_src_to_me_len; i++)
4520 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4521 ¤t_predecessor->finger_identity))
4525 *trail_src_to_curr_pred_length = i;
4530 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4531 sizeof(struct GNUNET_PeerIdentity));
4532 for(j = 0; j < i;j++)
4533 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4534 return trail_src_to_curr_pred;
4538 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4539 &trail_me_to_curr_pred_length);
4541 /* Check if trail contains the source_peer. */
4542 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4544 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4545 &trail_me_to_curr_pred[i]))
4548 /* Source is NOT part of trail. */
4551 /* Source is the last element in the trail to reach to my pred.
4552 Source is direct friend of the pred. */
4553 if (trail_me_to_curr_pred_length == i)
4555 *trail_src_to_curr_pred_length = 0;
4559 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4560 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4561 *trail_src_to_curr_pred_length);
4563 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4565 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4567 GNUNET_free_non_null(trail_me_to_curr_pred);
4568 return trail_src_to_curr_pred;
4572 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4573 trail_src_to_me_len,
4574 trail_me_to_curr_pred,
4575 trail_me_to_curr_pred_length,
4577 *trail_src_to_curr_pred_length = len;
4578 GNUNET_free_non_null(trail_me_to_curr_pred);
4579 return trail_src_to_curr_pred;
4584 * Add finger as your predecessor. To add, first generate a new trail id, invert
4585 * the trail to get the trail from me to finger, add an entry in your routing
4586 * table, send add trail message to peers which are part of trail from me to
4587 * finger and add finger in finger table.
4590 * @param trail_length
4593 update_predecessor (struct GNUNET_PeerIdentity finger,
4594 struct GNUNET_PeerIdentity *trail,
4595 unsigned int trail_length)
4597 struct GNUNET_HashCode trail_to_new_predecessor_id;
4598 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4599 struct FriendInfo *target_friend;
4601 /* Generate trail id for trail from me to new predecessor = finger. */
4602 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4603 &trail_to_new_predecessor_id,
4604 sizeof (trail_to_new_predecessor_id));
4606 /* Finger is a friend. */
4607 if (trail_length == 0)
4609 trail_to_new_predecessor = NULL;
4610 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4611 GNUNET_assert (NULL != (target_friend =
4612 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4617 /* Invert the trail to get the trail from me to finger, NOT including the
4619 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4620 &trail[trail_length-1]));
4622 trail_to_new_predecessor = invert_trail (trail, trail_length);
4624 /* Add an entry in your routing table. */
4625 GDS_ROUTING_add (trail_to_new_predecessor_id,
4627 trail_to_new_predecessor[0]);
4629 GNUNET_assert (NULL != (target_friend =
4630 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4631 &trail_to_new_predecessor[0])));
4632 GNUNET_assert (NULL != (
4633 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4634 &trail[trail_length - 1])));
4637 /* Add entry in routing table of all peers that are part of trail from me
4638 to finger, including finger. */
4639 GDS_NEIGHBOURS_send_add_trail (my_identity,
4641 trail_to_new_predecessor_id,
4642 trail_to_new_predecessor,
4646 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4647 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4648 GNUNET_free_non_null(trail_to_new_predecessor);
4653 * Check if you already have a predecessor. If not then add finger as your
4654 * predecessor. If you have predecessor, then compare two peer identites.
4655 * If finger is correct predecessor, then remove the old entry, add finger in
4656 * finger table and send add_trail message to add the trail in the routing
4657 * table of all peers which are part of trail to reach from me to finger.
4658 * @param finger New peer which may be our predecessor.
4659 * @param trail List of peers to reach from @finger to me.
4660 * @param trail_length Total number of peer in @a trail.
4663 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4664 struct GNUNET_PeerIdentity *trail,
4665 unsigned int trail_length)
4667 struct FingerInfo *current_predecessor;
4668 const struct GNUNET_PeerIdentity *closest_peer;
4669 uint64_t predecessor_value;
4670 unsigned int is_predecessor = 1;
4672 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4674 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4676 /* No predecessor. Add finger as your predecessor. */
4677 if (GNUNET_NO == current_predecessor->is_present)
4679 update_predecessor (finger, trail, trail_length);
4683 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4689 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4690 closest_peer = select_closest_peer (&finger,
4691 ¤t_predecessor->finger_identity,
4692 predecessor_value, is_predecessor);
4694 /* Finger is the closest predecessor. Remove the existing one and add the new
4696 if (closest_peer == &finger)
4698 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4699 update_predecessor (finger, trail, trail_length);
4707 * Core handle for p2p verify successor messages.
4708 * @param cls closure
4709 * @param message message
4710 * @param peer peer identity this notification is about
4711 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4714 handle_dht_p2p_verify_successor(void *cls,
4715 const struct GNUNET_PeerIdentity *peer,
4716 const struct GNUNET_MessageHeader *message)
4718 const struct PeerVerifySuccessorMessage *vsm;
4719 struct GNUNET_HashCode trail_id;
4720 struct GNUNET_PeerIdentity successor;
4721 struct GNUNET_PeerIdentity source_peer;
4722 struct GNUNET_PeerIdentity *trail;
4723 struct GNUNET_PeerIdentity *next_hop;
4724 struct FingerInfo current_predecessor;
4725 struct FriendInfo *target_friend;
4726 unsigned int trail_src_to_curr_pred_len = 0;
4727 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4728 unsigned int trail_length;
4731 msize = ntohs (message->size);
4733 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4735 GNUNET_break_op (0);
4739 vsm = (const struct PeerVerifySuccessorMessage *) message;
4740 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4741 sizeof (struct GNUNET_PeerIdentity);
4742 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4743 sizeof (struct GNUNET_PeerIdentity) != 0)
4745 GNUNET_break_op (0);
4749 GNUNET_STATISTICS_update (GDS_stats,
4751 ("# Bytes received from other peers"), msize,
4754 trail_id = vsm->trail_id;
4755 source_peer = vsm->source_peer;
4756 successor = vsm->successor;
4757 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4760 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4762 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4764 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4765 if (NULL == next_hop)
4767 GNUNET_break_op (0);
4768 return GNUNET_SYSERR;
4771 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4773 if(NULL == target_friend)
4778 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4779 trail_id, trail, trail_length,
4784 /* I am the destination of this message. */
4786 /* Check if the source_peer could be our predecessor and if yes then update
4788 compare_and_update_predecessor (source_peer, trail, trail_length);
4789 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4791 /* Is source of this message NOT my predecessor. */
4792 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4795 trail_src_to_curr_pred =
4796 get_trail_src_to_curr_pred (source_peer,
4799 &trail_src_to_curr_pred_len);
4803 trail_src_to_curr_pred_len = trail_length;
4806 trail_src_to_curr_pred =
4807 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4808 *trail_src_to_curr_pred_len);
4809 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4811 trail_src_to_curr_pred[i] = trail[i];
4815 GNUNET_assert (NULL !=
4817 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4818 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4819 current_predecessor.finger_identity,
4820 trail_id, trail_src_to_curr_pred,
4821 trail_src_to_curr_pred_len,
4822 GDS_ROUTING_DEST_TO_SRC,
4824 GNUNET_free_non_null(trail_src_to_curr_pred);
4830 * If the trail from me to my probable successor contains a friend not
4831 * at index 0, then we can shorten the trail.
4832 * @param probable_successor Peer which is our probable successor
4833 * @param trail_me_to_probable_successor Peers in path from me to my probable
4834 * successor, NOT including the endpoints.
4835 * @param trail_me_to_probable_successor_len Total number of peers in
4836 * @a trail_me_to_probable_succesor.
4837 * @return Updated trail, if any friend found.
4838 * Else the trail_me_to_probable_successor.
4840 struct GNUNET_PeerIdentity *
4841 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4842 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4843 unsigned int trail_me_to_probable_successor_len,
4844 unsigned int *trail_to_new_successor_length)
4848 struct GNUNET_PeerIdentity *trail_to_new_successor;
4850 /* Probable successor is a friend */
4851 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4852 &probable_successor))
4854 trail_to_new_successor = NULL;
4855 *trail_to_new_successor_length = 0;
4856 return trail_to_new_successor;
4859 /* Is there any friend of yours in this trail. */
4860 if(trail_me_to_probable_successor_len > 1)
4862 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4864 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4865 &trail_me_to_probable_successor[i]))
4868 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4869 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4870 *trail_to_new_successor_length);
4873 for(j = 0;j < *trail_to_new_successor_length;i++,j++)
4875 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4878 return trail_to_new_successor;
4882 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4883 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4888 * Check if the peer which sent us verify successor result message is still ours
4889 * successor or not. If not, then compare existing successor and probable successor.
4890 * In case probable successor is the correct successor, remove the existing
4891 * successor. Add probable successor as new successor. Send notify new successor
4892 * message to new successor.
4894 * @param probable_successor
4896 * @param trail_length
4899 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4900 struct GNUNET_PeerIdentity probable_successor,
4901 const struct GNUNET_PeerIdentity *trail,
4902 unsigned int trail_length)
4904 struct FingerInfo *current_successor;
4905 const struct GNUNET_PeerIdentity *closest_peer;
4906 struct GNUNET_HashCode trail_id;
4907 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4908 struct FriendInfo *target_friend;
4909 unsigned int trail_me_to_probable_succ_len;
4910 unsigned int is_predecessor = GNUNET_NO;
4911 uint64_t successor_value;
4913 current_successor = &finger_table[0];
4914 successor_value = compute_finger_identity_value(0);
4916 closest_peer = select_closest_peer (&probable_successor,
4917 ¤t_successor->finger_identity,
4918 successor_value, is_predecessor);
4920 /* If the current_successor in the finger table is closest, then do nothing. */
4921 if (closest_peer == ¤t_successor->finger_identity)
4923 /* Code for testing ONLY: Store the successor for path tracking */
4925 if (track_topology && (NULL != GDS_stats))
4931 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4932 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4933 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4934 GNUNET_free (my_id_str);
4935 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4940 /* Probable successor is the closest peer.*/
4941 if(trail_length > 0)
4943 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4948 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4949 &probable_successor));
4952 trail_me_to_probable_succ_len = 0;
4953 trail_me_to_probable_succ =
4954 check_trail_me_to_probable_succ (probable_successor,
4955 trail, trail_length,
4956 &trail_me_to_probable_succ_len);
4958 /* Remove the existing successor. */
4959 remove_existing_finger (current_successor, 0);
4961 /* TODO URGENT: Check if any peer is present more than once, if yes then shorten
4962 the trail. before sending it across the network. */
4963 /* Generate a new trail id to reach to your new successor. */
4964 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4965 &trail_id, sizeof (trail_id));
4967 if (trail_me_to_probable_succ_len > 0)
4969 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4970 GNUNET_assert (NULL !=
4972 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4973 &trail_me_to_probable_succ[0])));
4977 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4978 GNUNET_assert (NULL !=
4980 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4981 &probable_successor)));
4984 add_new_finger (probable_successor, trail_me_to_probable_succ,
4985 trail_me_to_probable_succ_len, trail_id, 0);
4987 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4988 trail_me_to_probable_succ,
4989 trail_me_to_probable_succ_len,
4997 * FIXME: Check for duplicate elements everywhere when you are making
4999 * Core handle for p2p verify successor result messages.
5000 * @param cls closure
5001 * @param message message
5002 * @param peer peer identity this notification is about
5003 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5006 handle_dht_p2p_verify_successor_result(void *cls,
5007 const struct GNUNET_PeerIdentity *peer,
5008 const struct GNUNET_MessageHeader *message)
5010 const struct PeerVerifySuccessorResultMessage *vsrm;
5011 enum GDS_ROUTING_trail_direction trail_direction;
5012 struct GNUNET_PeerIdentity querying_peer;
5013 struct GNUNET_HashCode trail_id;
5014 struct GNUNET_PeerIdentity *next_hop;
5015 struct FriendInfo *target_friend;
5016 struct GNUNET_PeerIdentity probable_successor;
5017 struct GNUNET_PeerIdentity current_successor;
5018 const struct GNUNET_PeerIdentity *trail;
5019 unsigned int trail_length;
5022 msize = ntohs (message->size);
5023 /* We send a trail to reach from old successor to new successor, if
5024 * old_successor != new_successor.*/
5025 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5027 GNUNET_break_op (0);
5031 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5032 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5033 sizeof (struct GNUNET_PeerIdentity);
5035 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5036 sizeof (struct GNUNET_PeerIdentity) != 0)
5038 GNUNET_break_op (0);
5042 GNUNET_STATISTICS_update (GDS_stats,
5044 ("# Bytes received from other peers"), msize,
5047 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5048 querying_peer = vsrm->querying_peer;
5049 trail_direction = ntohl (vsrm->trail_direction);
5050 trail_id = vsrm->trail_id;
5051 probable_successor = vsrm->probable_successor;
5052 current_successor = vsrm->current_successor;
5055 /* I am the querying_peer. */
5056 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5058 compare_and_update_successor (current_successor,
5059 probable_successor, trail, trail_length);
5063 /*If you are not the querying peer then pass on the message */
5064 GNUNET_assert (NULL != (next_hop =
5065 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
5066 GNUNET_assert (NULL !=
5068 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5069 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5070 vsrm->current_successor,
5071 probable_successor, trail_id,
5074 trail_direction, target_friend);
5080 * Core handle for p2p notify new successor messages.
5081 * @param cls closure
5082 * @param message message
5083 * @param peer peer identity this notification is about
5084 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5087 handle_dht_p2p_notify_new_successor(void *cls,
5088 const struct GNUNET_PeerIdentity *peer,
5089 const struct GNUNET_MessageHeader *message)
5091 const struct PeerNotifyNewSuccessorMessage *nsm;
5092 struct GNUNET_PeerIdentity *trail;
5093 struct GNUNET_PeerIdentity source;
5094 struct GNUNET_PeerIdentity new_successor;
5095 struct GNUNET_HashCode trail_id;
5096 struct GNUNET_PeerIdentity next_hop;
5097 struct FriendInfo *target_friend;
5100 uint32_t trail_length;
5102 msize = ntohs (message->size);
5104 /* We have the trail to reach from source to new successor. */
5105 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5107 GNUNET_break_op (0);
5111 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5112 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5113 sizeof (struct GNUNET_PeerIdentity);
5114 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5115 sizeof (struct GNUNET_PeerIdentity) != 0)
5117 GNUNET_break_op (0);
5121 GNUNET_STATISTICS_update (GDS_stats,
5123 ("# Bytes received from other peers"), msize,
5126 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5127 source = nsm->source_peer;
5128 new_successor = nsm->new_successor;
5129 trail_id = nsm->trail_id;
5132 //FIXME: add a check to make sure peer is correct.
5134 /* I am the new_successor to source_peer. */
5135 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5137 if(trail_length > 0)
5138 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5141 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5143 compare_and_update_predecessor (source, trail, trail_length);
5147 GNUNET_assert(trail_length > 0);
5148 /* I am part of trail to reach to successor. */
5149 my_index = search_my_index (trail, trail_length);
5152 GNUNET_break_op (0);
5153 return GNUNET_SYSERR;
5156 if ((trail_length-1) == my_index)
5157 next_hop = new_successor;
5159 next_hop = trail[my_index + 1];
5162 /* Add an entry in routing table for trail from source to its new successor. */
5163 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5164 GNUNET_assert (NULL !=
5166 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5167 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5169 trail_id, target_friend);
5176 * Core handler for P2P trail rejection message
5177 * @param cls closure
5178 * @param message message
5179 * @param peer peer identity this notification is about
5180 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5183 handle_dht_p2p_trail_setup_rejection (void *cls,
5184 const struct GNUNET_PeerIdentity *peer,
5185 const struct GNUNET_MessageHeader *message)
5187 const struct PeerTrailRejectionMessage *trail_rejection;
5188 unsigned int trail_length;
5189 const struct GNUNET_PeerIdentity *trail_peer_list;
5190 struct FriendInfo *target_friend;
5191 struct GNUNET_TIME_Relative congestion_timeout;
5192 struct GNUNET_HashCode trail_id;
5193 struct GNUNET_PeerIdentity next_peer;
5194 struct GNUNET_PeerIdentity source;
5195 struct GNUNET_PeerIdentity *next_hop;
5196 uint64_t ultimate_destination_finger_value;
5197 unsigned int is_predecessor;
5200 msize = ntohs (message->size);
5201 /* We are passing the trail setup so far. */
5202 if (msize < sizeof (struct PeerTrailRejectionMessage))
5204 GNUNET_break_op (0);
5208 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5209 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5210 sizeof (struct GNUNET_PeerIdentity);
5211 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5212 sizeof (struct GNUNET_PeerIdentity) != 0)
5214 GNUNET_break_op (0);
5218 GNUNET_STATISTICS_update (GDS_stats,
5220 ("# Bytes received from other peers"), msize,
5223 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5224 is_predecessor = ntohl (trail_rejection->is_predecessor);
5225 congestion_timeout = trail_rejection->congestion_time;
5226 source = trail_rejection->source_peer;
5227 trail_id = trail_rejection->trail_id;
5228 ultimate_destination_finger_value =
5229 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5231 /* First set the congestion time of the friend that sent you this message. */
5232 GNUNET_assert (NULL !=
5234 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5235 target_friend->congestion_timestamp =
5236 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5237 congestion_timeout);
5239 /* I am the source peer which wants to setup the trail. Do nothing.
5240 * send_find_finger_trail_task is scheduled periodically.*/
5241 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5244 /* If I am congested then pass this message to peer before me in trail. */
5245 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5247 struct GNUNET_PeerIdentity *new_trail;
5248 unsigned int new_trail_length;
5250 /* Remove yourself from the trail setup so far. */
5251 if (trail_length == 1)
5254 new_trail_length = 0;
5259 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5260 sizeof (struct GNUNET_PeerIdentity));
5262 /* Remove myself from the trail. */
5263 new_trail_length = trail_length -1;
5264 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5265 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5268 GNUNET_assert (NULL !=
5270 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5271 GDS_NEIGHBOURS_send_trail_rejection (source,
5272 ultimate_destination_finger_value,
5273 my_identity, is_predecessor,
5274 new_trail,new_trail_length,trail_id,
5275 target_friend, CONGESTION_TIMEOUT);
5276 GNUNET_free (new_trail);
5280 struct Closest_Peer successor;
5281 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5283 /* Am I the final destination? */
5284 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5287 if (0 == trail_length)
5290 next_peer = trail_peer_list[trail_length-1];
5292 GNUNET_assert (NULL !=
5294 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5296 GDS_NEIGHBOURS_send_trail_setup_result (source,
5298 target_friend, trail_length,
5301 ultimate_destination_finger_value,
5306 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5308 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5309 peer_list[trail_length] = my_identity;
5311 GNUNET_assert (NULL !=
5313 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5315 GDS_NEIGHBOURS_send_trail_setup (source,
5316 ultimate_destination_finger_value,
5317 successor.best_known_destination,
5318 target_friend, trail_length + 1, peer_list,
5319 is_predecessor, trail_id,
5320 successor.trail_id);
5327 * Core handle for p2p trail tear compression messages.
5328 * @param cls closure
5329 * @param message message
5330 * @param peer peer identity this notification is about
5331 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5334 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5335 const struct GNUNET_MessageHeader *message)
5337 const struct PeerTrailCompressionMessage *trail_compression;
5338 struct GNUNET_PeerIdentity *next_hop;
5339 struct FriendInfo *target_friend;
5340 struct GNUNET_HashCode trail_id;
5343 msize = ntohs (message->size);
5345 if (msize != sizeof (struct PeerTrailCompressionMessage))
5347 GNUNET_break_op (0);
5351 GNUNET_STATISTICS_update (GDS_stats,
5353 ("# Bytes received from other peers"), msize,
5356 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5357 trail_id = trail_compression->trail_id;
5359 /* Am I the new first friend to reach to finger of this trail. */
5360 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5363 GNUNET_assert (NULL !=
5364 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5365 &trail_compression->source_peer)));
5367 /* Update your prev hop to source of this message. */
5368 GNUNET_assert (GNUNET_SYSERR !=
5369 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5370 trail_compression->source_peer)));
5374 /* Pass the message to next hop to finally reach to new_first_friend. */
5375 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5377 if (NULL == next_hop)
5383 GNUNET_assert (NULL !=
5385 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5387 GDS_ROUTING_remove_trail (trail_id);
5389 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5391 trail_compression->new_first_friend,
5398 * Core handler for trail teardown message.
5399 * @param cls closure
5400 * @param message message
5401 * @param peer sender of this messsage.
5402 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5405 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5406 const struct GNUNET_MessageHeader *message)
5408 const struct PeerTrailTearDownMessage *trail_teardown;
5409 enum GDS_ROUTING_trail_direction trail_direction;
5410 struct GNUNET_HashCode trail_id;
5411 struct GNUNET_PeerIdentity *next_hop;
5414 msize = ntohs (message->size);
5416 /* Here we pass only the trail id. */
5417 if (msize != sizeof (struct PeerTrailTearDownMessage))
5419 GNUNET_break_op (0);
5423 GNUNET_STATISTICS_update (GDS_stats,
5425 ("# Bytes received from other peers"), msize,
5428 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5429 trail_direction = ntohl (trail_teardown->trail_direction);
5430 trail_id = trail_teardown->trail_id;
5432 /* Check if peer is the real peer from which we should get this message.*/
5433 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5435 GNUNET_assert (NULL != (prev_hop =
5436 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5437 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5440 return GNUNET_SYSERR;
5444 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5446 if (NULL == next_hop)
5449 return GNUNET_SYSERR;
5452 /* I am the next hop, which means I am the final destination. */
5453 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5455 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5460 /* If not final destination, then send a trail teardown message to next hop.*/
5461 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5462 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5463 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5471 * Core handle for p2p add trail message.
5472 * @param cls closure
5473 * @param message message
5474 * @param peer peer identity this notification is about
5475 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5478 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5479 const struct GNUNET_MessageHeader *message)
5481 const struct PeerAddTrailMessage *add_trail;
5482 const struct GNUNET_PeerIdentity *trail;
5483 struct GNUNET_HashCode trail_id;
5484 struct GNUNET_PeerIdentity destination_peer;
5485 struct GNUNET_PeerIdentity source_peer;
5486 struct GNUNET_PeerIdentity next_hop;
5487 unsigned int trail_length;
5488 unsigned int my_index;
5491 msize = ntohs (message->size);
5492 /* In this message we pass the whole trail from source to destination as we
5493 * are adding that trail.*/
5494 //FIXME: failed when run with 1000 pears. check why.
5495 if (msize < sizeof (struct PeerAddTrailMessage))
5497 GNUNET_break_op (0);
5501 add_trail = (const struct PeerAddTrailMessage *) message;
5502 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5503 sizeof (struct GNUNET_PeerIdentity);
5504 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5505 sizeof (struct GNUNET_PeerIdentity) != 0)
5507 GNUNET_break_op (0);
5511 GNUNET_STATISTICS_update (GDS_stats,
5513 ("# Bytes received from other peers"), msize,
5516 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5517 destination_peer = add_trail->destination_peer;
5518 source_peer = add_trail->source_peer;
5519 trail_id = add_trail->trail_id;
5521 //FIXME: add a check that sender peer is not malicious. Make it a generic
5522 // function so that it can be used in all other functions where we need the
5523 // same functionality.
5525 /* I am not the destination of the trail. */
5526 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5528 struct FriendInfo *target_friend;
5530 /* Get my location in the trail. */
5531 my_index = search_my_index (trail, trail_length);
5534 GNUNET_break_op (0);
5535 return GNUNET_SYSERR;
5538 if ((trail_length - 1) == my_index)
5540 next_hop = destination_peer;
5544 next_hop = trail[my_index + 1];
5547 /* Add in your routing table. */
5548 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5549 GNUNET_assert (NULL !=
5551 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5552 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5553 trail, trail_length, target_friend);
5556 /* I am the destination. Add an entry in routing table. */
5557 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5563 * Free the finger trail in which the first friend to reach to a finger is
5564 * disconnected_friend. Also remove entry from routing table for that particular
5566 * @param disconnected_friend PeerIdentity of friend which got disconnected
5567 * @param remove_finger Finger whose trail we need to check if it has
5568 * disconnected_friend as the first hop.
5569 * @return Total number of trails in which disconnected_friend was the first
5573 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5574 struct FingerInfo *remove_finger)
5576 unsigned int matching_trails_count;
5579 /* Number of trails with disconnected_friend as the first hop in the trail
5580 * to reach from me to remove_finger, NOT including endpoints. */
5581 matching_trails_count = 0;
5583 /* Iterate over all the trails of finger. */
5584 for (i = 0; i < MAXIMUM_TRAILS_PER_FINGER; i++)
5586 struct Trail *trail;
5587 trail = &remove_finger->trail_list[i];
5589 /* This assertion is ensure that there are no gaps in the trail list.
5590 REMOVE IT AFTERWARDS. */
5591 GNUNET_assert (GNUNET_YES == trail->is_present);
5593 /* First friend to reach to finger is disconnected_peer. */
5594 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5595 disconnected_friend))
5597 struct GNUNET_PeerIdentity *next_hop;
5598 struct FriendInfo *remove_friend;
5600 GNUNET_assert (NULL !=
5602 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5603 disconnected_friend)));
5604 /* FIXME: removing no but check it. */
5605 //remove_friend->trails_count--;
5606 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5607 GDS_ROUTING_SRC_TO_DEST);
5609 /* Here it may happen that as all the peers got disconnected, the entry in
5610 routing table for that particular trail has been removed, because the
5611 previously disconnected peer was either a next hop or prev hop of that
5613 if (NULL == next_hop)
5616 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5618 matching_trails_count++;
5619 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5622 trail->is_present = GNUNET_NO;
5625 return matching_trails_count;
5630 * Iterate over finger_table entries.
5631 * 0. Ignore finger which is my_identity or if no valid entry present at
5632 * that finger index.
5633 * 1. If disconnected_friend is a finger, then remove the routing entry from
5634 your own table. Free the trail.
5635 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5636 * 2.1 Remove all the trails and entry from routing table in which disconnected
5637 * friend is the first friend in the trail. If disconnected_friend is the
5638 * first friend in all the trails to reach finger, then remove the finger.
5639 * @param disconnected_friend Peer identity of friend which got disconnected.
5642 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5644 struct FingerInfo *remove_finger;
5645 struct FriendInfo *remove_friend;
5646 int removed_trails_count;
5649 /* Iterate over finger table entries. */
5650 for (i = 0; i < MAX_FINGERS; i++)
5652 remove_finger = &finger_table[i];
5654 /* No finger stored at this trail index. */
5655 if (GNUNET_NO == remove_finger->is_present)
5658 /* I am my own finger, then ignore this finger. */
5659 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5663 /* Is disconnected_peer a finger? */
5664 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5665 &remove_finger->finger_identity))
5667 struct GNUNET_PeerIdentity *next_hop;
5668 struct GNUNET_HashCode trail_id;
5671 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5672 trail_id = remove_finger->trail_list[0].trail_id;
5676 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5679 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5680 &remove_finger->finger_identity)));
5681 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5682 GNUNET_assert (NULL !=
5684 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5685 disconnected_peer)));
5688 remove_finger->trail_list[0].is_present = GNUNET_NO;
5689 //GNUNET_assert (0 != remove_friend->trails_count);
5690 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5691 remove_finger->is_present = GNUNET_NO;
5692 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5696 /* If finger is a friend but not disconnected_friend, then continue. */
5697 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5698 &remove_finger->finger_identity))
5701 /* Iterate over the list of trails to reach remove_finger. Check if
5702 * disconnected_friend is the first friend in any of the trail. */
5703 removed_trails_count = remove_matching_trails (disconnected_peer,
5705 remove_finger->trails_count =
5706 remove_finger->trails_count - removed_trails_count;
5707 /* All the finger trails had disconnected_friend as the first friend,
5708 * so free the finger. */
5709 if (remove_finger->trails_count == 0)
5711 remove_finger->is_present = GNUNET_NO;
5712 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5719 * Method called whenever a peer disconnects.
5721 * @param cls closure
5722 * @param peer peer identity this notification is about
5725 handle_core_disconnect (void *cls,
5726 const struct GNUNET_PeerIdentity *peer)
5728 struct FriendInfo *remove_friend;
5730 /* If disconnected to own identity, then return. */
5731 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5734 GNUNET_assert (NULL != (remove_friend =
5735 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5737 /* Remove fingers with peer as first friend or if peer is a finger. */
5738 remove_matching_fingers (peer);
5740 /* Remove any trail from routing table of which peer is a part of. This function
5741 * internally sends a trail teardown message in the direction of which
5742 * disconnected peer is not part of. */
5743 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5745 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5747 /* Remove peer from friend_peermap. */
5748 GNUNET_assert (GNUNET_YES ==
5749 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5753 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5756 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5758 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5759 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5768 * Method called whenever a peer connects.
5770 * @param cls closure
5771 * @param peer_identity peer identity this notification is about
5774 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5776 struct FriendInfo *friend;
5778 /* Check for connect to self message */
5779 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5782 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5784 /* If peer already exists in our friend_peermap, then exit. */
5785 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5792 friend = GNUNET_new (struct FriendInfo);
5793 friend->id = *peer_identity;
5795 GNUNET_assert (GNUNET_OK ==
5796 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5797 peer_identity, friend,
5798 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5801 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5802 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5804 next_send_time.rel_value_us =
5805 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5806 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5807 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5808 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5814 * To be called on core init/fail.
5816 * @param cls service closure
5817 * @param identity the public identity of this peer
5820 core_init (void *cls,
5821 const struct GNUNET_PeerIdentity *identity)
5823 my_identity = *identity;
5826 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5827 my_id64 = GNUNET_ntohll (my_id64);
5828 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5829 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5835 * Initialize finger table entries.
5838 finger_table_init ()
5840 memset (&finger_table, 0, sizeof (finger_table));
5845 * Initialize neighbours subsystem.
5846 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5849 GDS_NEIGHBOURS_init (void)
5851 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5852 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5853 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5854 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5855 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5856 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5857 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5858 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5859 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5860 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5861 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5862 sizeof (struct PeerTrailCompressionMessage)},
5863 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5864 sizeof (struct PeerTrailTearDownMessage)},
5865 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5870 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5871 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5872 GNUNET_NO, core_handlers);
5873 if (NULL == core_api)
5874 return GNUNET_SYSERR;
5876 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5877 finger_table_init ();
5884 * Shutdown neighbours subsystem.
5887 GDS_NEIGHBOURS_done (void)
5889 if (NULL == core_api)
5892 GNUNET_CORE_disconnect (core_api);
5895 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5896 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5897 friend_peermap = NULL;
5899 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5902 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5903 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5906 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5908 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5909 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5917 * @return my identity
5919 struct GNUNET_PeerIdentity
5920 GDS_NEIGHBOURS_get_my_id (void)
5925 /* end of gnunet-service-xdht_neighbours.c */