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)))
1722 * This is a test function to print all the entries of friend table.
1725 test_friend_peermap_print ()
1727 struct FriendInfo *friend;
1728 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1729 struct GNUNET_PeerIdentity print_peer;
1730 struct GNUNET_PeerIdentity key_ret;
1733 print_peer = my_identity;
1734 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1735 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1737 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1739 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1741 (const void **)&friend))
1743 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1744 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1745 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1753 * This is a test function, to print all the entries of finger table.
1756 test_finger_table_print()
1758 struct FingerInfo *finger;
1759 struct GNUNET_PeerIdentity print_peer;
1760 //struct Trail *trail;
1764 print_peer = my_identity;
1765 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1766 for (i = 0; i < MAX_FINGERS; i++)
1768 finger = &finger_table[i];
1770 if (GNUNET_NO == finger->is_present)
1773 print_peer = finger->finger_identity;
1774 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1775 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1778 for (j = 0; j < finger->trails_count; j++)
1780 trail = &finger->trail_list[j];
1781 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1782 struct Trail_Element *element;
1783 element = trail->trail_head;
1784 for (k = 0; k < trail->trail_length; k++)
1786 print_peer = element->peer;
1787 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1788 element = element->next;
1797 * Select the closest peer among two peers (which should not be same)
1798 * with respect to value and finger_table_index
1799 * NOTE: peer1 != peer2
1800 * @param peer1 First peer
1801 * @param peer2 Second peer
1802 * @param value Value relative to which we find the closest
1803 * @param is_predecessor Is value a predecessor or any other finger.
1804 * @return Closest peer among two peers.
1806 const static struct GNUNET_PeerIdentity *
1807 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1808 const struct GNUNET_PeerIdentity *peer2,
1810 unsigned int is_predecessor)
1812 if (1 == is_predecessor)
1813 return select_closest_predecessor (peer1, peer2, value);
1815 return select_closest_finger (peer1, peer2, value);
1820 * Iterate over the list of all the trails of a finger. In case the first
1821 * friend to reach the finger has reached trail threshold or is congested,
1822 * then don't select it. In case there multiple available good trails to reach
1823 * to Finger, choose the one with shortest trail length.
1824 * Note: We use length as parameter. But we can use any other suitable parameter
1826 * @param finger Finger
1827 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1828 * and trail length. NULL in case none of the trails are free.
1830 static struct Selected_Finger_Trail *
1831 select_finger_trail (struct FingerInfo *finger)
1833 struct FriendInfo *friend;
1834 struct Trail *iterator;
1835 struct Selected_Finger_Trail *finger_trail;
1837 unsigned int flag = 0;
1840 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1841 GNUNET_assert (finger->trails_count > 0);
1843 for (i = 0; i < finger->trails_count; i++)
1845 iterator = &finger->trail_list[i];
1847 /* No trail stored at this index. */
1848 if (GNUNET_NO == iterator->is_present)
1851 GNUNET_assert (NULL !=
1853 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1854 &iterator->trail_head->peer)));
1856 /* First friend to reach trail is not free. */
1857 if (GNUNET_YES == is_friend_congested (friend))
1866 finger_trail->trail_length = iterator->trail_length;
1867 finger_trail->friend = *friend;
1868 finger_trail->trail_id = iterator->trail_id;
1870 else if (finger_trail->trail_length > iterator->trail_length)
1872 finger_trail->friend = *friend;
1873 finger_trail->trail_id = iterator->trail_id;
1874 finger_trail->trail_length = iterator->trail_length;
1878 /* All the first friend in all the trails to reach to finger are either
1879 congested or have crossed trail threshold. */
1880 if (j == finger->trails_count)
1883 return finger_trail;
1888 * Compare FINGER entry with current successor. If finger's first friend of all
1889 * its trail is not congested and has not crossed trail threshold, then check
1890 * if finger peer identity is closer to final_destination_finger_value than
1891 * current_successor. If yes then update current_successor.
1892 * @param current_successor[in/out]
1896 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1898 struct FingerInfo *finger;
1899 const struct GNUNET_PeerIdentity *closest_peer;
1900 struct Selected_Finger_Trail *finger_trail;
1903 /* Iterate over finger table. */
1904 for (i = 0; i < MAX_FINGERS; i++)
1906 finger = &finger_table[i];
1908 if (GNUNET_NO == finger->is_present)
1911 /* FIXME write correct comment here */
1912 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1913 ¤t_closest_peer->best_known_destination))
1916 /* If I am my own finger, then ignore this finger. */
1917 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1920 /* FIXME: I think a peer should not select itself as its own identity ever.
1921 But it does select. Find out why??*/
1927 /* If finger is a friend, then do nothing. As we have already checked
1928 * for each friend in compare_friend_and_current_successor(). */
1929 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1930 &finger->finger_identity)))
1935 closest_peer = select_closest_peer (&finger->finger_identity,
1936 ¤t_closest_peer->best_known_destination,
1937 current_closest_peer->destination_finger_value,
1938 current_closest_peer->is_predecessor);
1940 if (&finger->finger_identity == closest_peer)
1942 /* Choose one of the trail to reach to finger. */
1943 finger_trail = select_finger_trail (finger);
1945 /* In case no trail found, ignore this finger. */
1946 if (NULL == finger_trail)
1949 current_closest_peer->best_known_destination = finger->finger_identity;
1950 current_closest_peer->next_hop = finger_trail->friend.id;
1951 current_closest_peer->trail_id = finger_trail->trail_id;
1952 GNUNET_free(finger_trail);
1960 * Compare friend entry with current successor.
1961 * If friend identity and current_successor is same, then do nothing.
1962 * If friend is not congested and has not crossed trail threshold, then check
1963 * if friend peer identity is closer to final_destination_finger_value than
1964 * current_successor. If yes then update current_successor.
1965 * @param cls closure
1966 * @param key current public key
1967 * @param value struct Closest_Peer
1968 * @return #GNUNET_YES if we should continue to iterate,
1969 * #GNUNET_NO if not.
1972 compare_friend_and_current_closest_peer (void *cls,
1973 const struct GNUNET_PeerIdentity *key,
1976 struct FriendInfo *friend = value;
1977 struct Closest_Peer *current_closest_peer = cls;
1978 const struct GNUNET_PeerIdentity *closest_peer;
1980 /* Friend is either congested or has crossed threshold. */
1981 if (GNUNET_YES == is_friend_congested (friend))
1984 /* If current_closest_peer and friend identity are same, then do nothing.*/
1985 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
1986 ¤t_closest_peer->best_known_destination))
1992 closest_peer = select_closest_peer (&friend->id,
1993 ¤t_closest_peer->best_known_destination,
1994 current_closest_peer->destination_finger_value,
1995 current_closest_peer->is_predecessor);
1997 /* Is friend the closest successor? */
1998 if (&friend->id == closest_peer)
2000 current_closest_peer->best_known_destination = friend->id;
2001 current_closest_peer->next_hop = friend->id;
2009 * Initialize current_successor to my_identity.
2010 * @param my_identity My peer identity
2011 * @return Updated closest_peer
2013 static struct Closest_Peer
2014 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2015 uint64_t destination_finger_value,
2016 unsigned int is_predecessor)
2018 struct Closest_Peer current_closest_peer;
2020 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2021 current_closest_peer.destination_finger_value = destination_finger_value;
2022 current_closest_peer.is_predecessor = is_predecessor;
2023 current_closest_peer.next_hop = my_identity;
2024 current_closest_peer.best_known_destination = my_identity;
2026 return current_closest_peer;
2031 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2032 * peer. It could be because of the logic we wrote here. Verify if its correct.
2033 * If not then return immediate_successor.
2035 * Find the successor for destination_finger_value among my_identity, my
2036 * friends and my fingers. Don't consider friends or fingers which are either
2037 * congested or have crossed the threshold.
2038 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2040 * @param destination_finger_value Peer closest to this value will be the next successor.
2041 * @param is_predecessor Are we looking for predecessor or finger?
2042 * @return Successor It is never NULL, in case none of friend or finger is closest,
2043 * then we return my_identity.
2045 static struct Closest_Peer
2046 find_successor (uint64_t destination_finger_value,
2047 unsigned int is_predecessor)
2049 struct Closest_Peer current_closest_peer;
2051 /* Initialize current_successor to my_identity. */
2052 current_closest_peer = init_current_successor (my_identity,
2053 destination_finger_value,
2056 /* Compare each friend entry with current_successor and update current_successor
2057 * with friend if its closest. */
2060 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2061 &compare_friend_and_current_closest_peer,
2062 ¤t_closest_peer));
2064 /* Compare each finger entry with current_successor and update current_successor
2065 * with finger if its closest. */
2066 compare_finger_and_current_successor (¤t_closest_peer);
2068 return current_closest_peer;
2073 * Construct a Put message and send it to target_peer.
2074 * @param key Key for the content
2075 * @param block_type Type of the block
2076 * @param options Routing options
2077 * @param desired_replication_level Desired replication count
2078 * @param best_known_dest Peer to which this message should reach eventually,
2079 * as it is best known destination to me.
2080 * @param intermediate_trail_id Trail id in case
2081 * @param target_peer Peer to which this message will be forwarded.
2082 * @param hop_count Number of hops traversed so far.
2083 * @param put_path_length Total number of peers in @a put_path
2084 * @param put_path Number of peers traversed so far
2085 * @param expiration_time When does the content expire
2086 * @param data Content to store
2087 * @param data_size Size of content @a data in bytes
2090 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2091 enum GNUNET_BLOCK_Type block_type,
2092 enum GNUNET_DHT_RouteOption options,
2093 uint32_t desired_replication_level,
2094 struct GNUNET_PeerIdentity best_known_dest,
2095 struct GNUNET_HashCode intermediate_trail_id,
2096 struct GNUNET_PeerIdentity *target_peer,
2098 uint32_t put_path_length,
2099 struct GNUNET_PeerIdentity *put_path,
2100 struct GNUNET_TIME_Absolute expiration_time,
2101 const void *data, size_t data_size)
2103 struct PeerPutMessage *ppm;
2104 struct P2PPendingMessage *pending;
2105 struct FriendInfo *target_friend;
2106 struct GNUNET_PeerIdentity *pp;
2107 struct GNUNET_PeerIdentity next_hop;
2111 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2112 sizeof (struct PeerPutMessage);
2114 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2116 put_path_length = 0;
2117 msize = data_size + sizeof (struct PeerPutMessage);
2120 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2126 /* This is the first call made from clients file. So, we should search for the
2128 if (NULL == target_peer)
2131 struct Closest_Peer successor;
2133 memcpy (&key_value, key, sizeof (uint64_t));
2134 key_value = GNUNET_ntohll (key_value);
2136 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2137 best_known_dest = successor.best_known_destination;
2138 next_hop = successor.next_hop;
2139 intermediate_trail_id = successor.trail_id;
2141 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2143 /* I am the destination. */
2144 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2145 block_type,data_size,data);
2149 GNUNET_assert (NULL !=
2151 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2155 GNUNET_assert (NULL !=
2157 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2160 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2161 pending->timeout = expiration_time;
2162 ppm = (struct PeerPutMessage *) &pending[1];
2163 pending->msg = &ppm->header;
2164 ppm->header.size = htons (msize);
2165 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2166 ppm->options = htonl (options);
2167 ppm->block_type = htonl (block_type);
2168 ppm->hop_count = htonl (hop_count + 1);
2169 ppm->desired_replication_level = htonl (desired_replication_level);
2170 ppm->put_path_length = htonl (put_path_length);
2171 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2172 ppm->best_known_destination = best_known_dest;
2175 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2176 if (put_path_length != 0)
2178 memcpy (pp, put_path,
2179 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2181 memcpy (&pp[put_path_length], data, data_size);
2182 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2183 target_friend->pending_count++;
2184 process_friend_queue (target_friend);
2189 * Construct a Get message and send it to target_peer.
2190 * @param key Key for the content
2191 * @param block_type Type of the block
2192 * @param options Routing options
2193 * @param desired_replication_level Desired replication count
2194 * @param best_known_dest Peer which should get this message. Same as target peer
2195 * if best_known_dest is a friend else its a finger.
2196 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2197 * in case it is a finger else set to 0.
2198 * @param target_peer Peer to which this message will be forwarded.
2199 * @param hop_count Number of hops traversed so far.
2200 * @param data Content to store
2201 * @param data_size Size of content @a data in bytes
2202 * @param get_path_length Total number of peers in @a get_path
2203 * @param get_path Number of peers traversed so far
2206 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2207 enum GNUNET_BLOCK_Type block_type,
2208 enum GNUNET_DHT_RouteOption options,
2209 uint32_t desired_replication_level,
2210 struct GNUNET_PeerIdentity best_known_dest,
2211 struct GNUNET_HashCode intermediate_trail_id,
2212 struct GNUNET_PeerIdentity *target_peer,
2214 uint32_t get_path_length,
2215 struct GNUNET_PeerIdentity *get_path)
2217 struct PeerGetMessage *pgm;
2218 struct P2PPendingMessage *pending;
2219 struct FriendInfo *target_friend;
2220 struct GNUNET_PeerIdentity *gp;
2223 msize = sizeof (struct PeerGetMessage) +
2224 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2226 //GNUNET_SERVER_MAX_MESSAGE_SIZE
2227 /* FIXME:TODO:URGENTHere you can try to optimize it a bit. In case the get path contains you
2228 or your friend then shorten the path. */
2229 /* In this case we don't make get_path_length = 0, as we need get path to
2230 * return the message back to querying client. */
2231 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2237 /* This is the first time we got request from our own client file. */
2238 if (NULL == target_peer)
2241 struct Closest_Peer successor;
2243 memcpy (&key_value, key, sizeof (uint64_t));
2244 key_value = GNUNET_ntohll (key_value);
2245 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2247 best_known_dest = successor.best_known_destination;
2248 intermediate_trail_id = successor.trail_id;
2250 /* I am the destination. I have the data. */
2251 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2254 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2255 NULL, 0, 1, &my_identity, NULL,&my_identity);
2261 GNUNET_assert (NULL !=
2263 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2264 &successor.next_hop)));
2270 GNUNET_assert (NULL !=
2272 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); //FIXME: assertion fails.
2275 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2276 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2277 pending->importance = 0; /* FIXME */
2278 pgm = (struct PeerGetMessage *) &pending[1];
2279 pending->msg = &pgm->header;
2280 pgm->header.size = htons (msize);
2281 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2282 pgm->get_path_length = htonl (get_path_length);
2283 pgm->best_known_destination = best_known_dest;
2285 pgm->intermediate_trail_id = intermediate_trail_id;
2286 pgm->hop_count = htonl (hop_count + 1);
2287 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2289 if (get_path_length != 0)
2291 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2294 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2295 target_friend->pending_count++;
2296 process_friend_queue (target_friend);
2301 * Send the get result to requesting client.
2302 * @param key Key of the requested data.
2303 * @param type Block type
2304 * @param target_peer Next peer to forward the message to.
2305 * @param source_peer Peer which has the data for the key.
2306 * @param put_path_length Number of peers in @a put_path
2307 * @param put_path Path taken to put the data at its stored location.
2308 * @param get_path_length Number of peers in @a get_path
2309 * @param get_path Path taken to reach to the location of the key.
2310 * @param expiration When will this result expire?
2311 * @param data Payload to store
2312 * @param data_size Size of the @a data
2315 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2316 enum GNUNET_BLOCK_Type type,
2317 const struct GNUNET_PeerIdentity *target_peer,
2318 const struct GNUNET_PeerIdentity *source_peer,
2319 unsigned int put_path_length,
2320 const struct GNUNET_PeerIdentity *put_path,
2321 unsigned int get_path_length,
2322 const struct GNUNET_PeerIdentity *get_path,
2323 struct GNUNET_TIME_Absolute expiration,
2324 const void *data, size_t data_size)
2326 struct PeerGetResultMessage *get_result;
2327 struct GNUNET_PeerIdentity *paths;
2328 struct P2PPendingMessage *pending;
2329 struct FriendInfo *target_friend;
2330 int current_path_index;
2333 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2335 sizeof (struct PeerGetResultMessage);
2337 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2339 put_path_length = 0;
2340 msize = msize - put_path_length;
2344 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2350 current_path_index = 0;
2351 if(get_path_length > 0)
2353 current_path_index = search_my_index(get_path, get_path_length);
2354 if (-1 == current_path_index)
2360 if (0 == current_path_index)
2362 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2363 get_path, put_path_length,
2364 put_path, type, data_size, data);
2368 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2369 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2370 pending->importance = 0;
2371 get_result = (struct PeerGetResultMessage *)&pending[1];
2372 pending->msg = &get_result->header;
2373 get_result->header.size = htons (msize);
2374 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2375 get_result->key = *key;
2376 get_result->querying_peer = *source_peer;
2377 get_result->expiration_time = expiration;
2378 get_result->get_path_length = htonl (get_path_length);
2379 get_result->put_path_length = htonl (put_path_length);
2380 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2381 memcpy (paths, put_path,
2382 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2383 memcpy (&paths[put_path_length], get_path,
2384 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2385 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2387 GNUNET_assert (NULL !=
2389 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2390 &get_path[current_path_index - 1])));
2391 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2392 target_friend->pending_count++;
2393 process_friend_queue (target_friend);
2398 * Randomly choose one of your friends (which is not congested and have not crossed
2399 * trail threshold) from the friend_peermap
2400 * @return Friend Randomly chosen friend.
2401 * NULL in case friend peermap is empty, or all the friends are either
2402 * congested or have crossed trail threshold.
2404 static struct FriendInfo *
2405 select_random_friend ()
2407 unsigned int current_size;
2410 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2411 struct GNUNET_PeerIdentity key_ret;
2412 struct FriendInfo *friend;
2414 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2417 if (0 == current_size)
2420 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2421 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2423 /* Iterate till you don't reach to index. */
2424 for (j = 0; j < index ; j++)
2425 GNUNET_assert (GNUNET_YES ==
2426 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2429 /* Reset the index in friend peermap to 0 as we reached to the end. */
2430 if (j == current_size)
2433 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2434 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2438 /* Get the friend stored at the index, j*/
2439 GNUNET_assert (GNUNET_YES ==
2440 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2442 (const void **)&friend));
2444 /* This friend is not congested and has not crossed trail threshold. */
2445 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2446 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2452 } while (j != index);
2454 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2460 * Compute 64 bit value of finger_identity corresponding to a finger index using
2462 * For all fingers, n.finger[i] = n + pow (2,i),
2463 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2464 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2465 * @param finger_index Index corresponding to which we calculate 64 bit value.
2466 * @return 64 bit value.
2469 compute_finger_identity_value (unsigned int finger_index)
2473 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2474 my_id64 = GNUNET_ntohll (my_id64);
2476 /* Are we looking for immediate predecessor? */
2477 if (PREDECESSOR_FINGER_ID == finger_index)
2478 return (my_id64 - 1);
2481 uint64_t add = (uint64_t)1 << finger_index;
2482 return (my_id64 + add);
2486 static struct GNUNET_TIME_Relative next_send_time;
2489 * Choose a random friend. Calculate the next finger identity to search,from
2490 * current_search_finger_index. Start looking for the trail to reach to
2491 * finger identity through this random friend.
2493 * @param cls closure for this task
2494 * @param tc the context under which the task is running
2497 send_find_finger_trail_message (void *cls,
2498 const struct GNUNET_SCHEDULER_TaskContext *tc)
2500 struct FriendInfo *target_friend;
2501 //struct GNUNET_TIME_Relative next_send_time;
2502 struct GNUNET_HashCode trail_id;
2503 struct GNUNET_HashCode intermediate_trail_id;
2504 unsigned int is_predecessor;
2505 uint64_t finger_id_value;
2507 /* Schedule another send_find_finger_trail_message task. */
2508 find_finger_trail_task =
2509 GNUNET_SCHEDULER_add_delayed (next_send_time,
2510 &send_find_finger_trail_message,
2513 /* No space in my routing table. (Source and destination peers also store entries
2514 * in their routing table). */
2515 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2519 target_friend = select_random_friend ();
2520 if (NULL == target_friend)
2525 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2527 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2532 /* Generate a unique trail id for trail we are trying to setup. */
2533 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2534 &trail_id, sizeof (trail_id));
2535 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2537 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2538 target_friend->id, target_friend, 0, NULL,
2539 is_predecessor, trail_id,
2540 intermediate_trail_id);
2545 * In case there are already maximum number of possible trails to reach to a
2546 * finger, then check if the new trail's length is lesser than any of the
2548 * If yes then replace that old trail by new trail.
2550 * Note: Here we are taking length as a parameter to choose the best possible
2551 * trail, but there could be other parameters also like:
2552 * 1. duration of existence of a trail - older the better.
2553 * 2. if the new trail is completely disjoint than the
2554 * other trails, then may be choosing it is better.
2556 * @param existing_finger
2557 * @param new_finger_trail
2558 * @param new_finger_trail_length
2559 * @param new_finger_trail_id
2562 select_and_replace_trail (struct FingerInfo *existing_finger,
2563 const struct GNUNET_PeerIdentity *new_trail,
2564 unsigned int new_trail_length,
2565 struct GNUNET_HashCode new_trail_id)
2567 struct Trail *trail_list_iterator;
2568 unsigned int largest_trail_length;
2569 unsigned int largest_trail_index;
2570 struct Trail_Element *trail_element;
2573 largest_trail_length = new_trail_length;
2574 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2576 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2578 for (i = 0; i < existing_finger->trails_count; i++)
2580 trail_list_iterator = &existing_finger->trail_list[i];
2581 if (trail_list_iterator->trail_length > largest_trail_length)
2583 largest_trail_length = trail_list_iterator->trail_length;
2584 largest_trail_index = i;
2588 /* New trail is not better than existing ones. Send trail teardown. */
2589 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2591 struct GNUNET_PeerIdentity next_hop;
2593 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2594 GDS_ROUTING_remove_trail (new_trail_id);
2595 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2596 GDS_ROUTING_SRC_TO_DEST,
2601 /* Send trail teardown message across the replaced trail. */
2602 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2603 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2604 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2605 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2606 GDS_ROUTING_SRC_TO_DEST,
2607 replace_trail->trail_head->peer);
2608 /* Free the trail. */
2609 while (NULL != (trail_element = replace_trail->trail_head))
2611 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2612 replace_trail->trail_tail, trail_element);
2613 GNUNET_free_non_null (trail_element);
2616 /* Add new trial at that location. */
2617 replace_trail->is_present = GNUNET_YES;
2618 replace_trail->trail_length = new_trail_length;
2619 replace_trail->trail_id = new_trail_id;
2620 //FIXME: Do we need to add pointers for head and tail.
2622 while (i < new_trail_length)
2624 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2625 element->peer = new_trail[i];
2627 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2628 replace_trail->trail_tail,
2635 * Check if the new trail to reach to finger is unique or do we already have
2636 * such a trail present for finger.
2637 * @param existing_finger Finger identity
2638 * @param new_trail New trail to reach @a existing_finger
2639 * @param trail_length Total number of peers in new_trail.
2640 * @return #GNUNET_YES if the new trail is unique
2641 * #GNUNET_NO if same trail is already present.
2644 is_new_trail_unique (struct FingerInfo *existing_finger,
2645 const struct GNUNET_PeerIdentity *new_trail,
2646 unsigned int trail_length)
2648 struct Trail *trail_list_iterator;
2649 struct Trail_Element *trail_element;
2652 int trail_unique = GNUNET_NO;
2654 GNUNET_assert (existing_finger->trails_count > 0);
2656 /* Iterate over list of trails. */
2657 for (i = 0; i < existing_finger->trails_count; i++)
2659 trail_list_iterator = &existing_finger->trail_list[i];
2660 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2662 /* New trail and existing trail length are not same. */
2663 if (trail_list_iterator->trail_length != trail_length)
2665 trail_unique = GNUNET_YES;
2669 trail_element = trail_list_iterator->trail_head;
2670 for (j = 0; j < trail_list_iterator->trail_length; j++)
2672 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2673 &trail_element->peer))
2675 trail_unique = GNUNET_YES;
2678 trail_element = trail_element->next;
2681 trail_unique = GNUNET_NO;
2684 return trail_unique;
2689 * Add a new trail to existing finger. This function is called only when finger
2690 * is not my own identity or a friend.
2691 * @param existing_finger Finger
2692 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2693 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2694 * @param new_finger_trail_id Unique identifier of the trail.
2697 add_new_trail (struct FingerInfo *existing_finger,
2698 const struct GNUNET_PeerIdentity *new_trail,
2699 unsigned int new_trail_length,
2700 struct GNUNET_HashCode new_trail_id)
2702 struct Trail *trail_list_iterator;
2703 struct FriendInfo *first_friend;
2706 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2712 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2713 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2714 trail_list_iterator->trail_id = new_trail_id;
2715 trail_list_iterator->trail_length = new_trail_length;
2716 existing_finger->trails_count++;
2717 trail_list_iterator->is_present = GNUNET_YES;
2719 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2720 &existing_finger->finger_identity)));
2721 /* If finger is a friend then we never call this function. */
2722 GNUNET_assert (new_trail_length > 0);
2724 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2726 first_friend->trails_count++;
2728 for (i = 0; i < new_trail_length; i++)
2730 struct Trail_Element *element;
2732 element = GNUNET_new (struct Trail_Element);
2733 element->peer = new_trail[i];
2734 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2735 trail_list_iterator->trail_tail,
2738 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2744 * FIXME Check if this function is called for opposite direction if yes then
2745 * take it as parameter.
2746 * Get the next hop to send trail teardown message from routing table and
2747 * then delete the entry from routing table. Send trail teardown message for a
2748 * specific trail of a finger.
2749 * @param finger Finger whose trail is to be removed.
2750 * @param trail List of peers in trail from me to a finger, NOT including
2754 send_trail_teardown (struct FingerInfo *finger,
2755 struct Trail *trail)
2757 struct FriendInfo *friend;
2758 struct GNUNET_PeerIdentity *next_hop;
2760 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2761 GDS_ROUTING_SRC_TO_DEST);
2763 if (NULL == next_hop)
2768 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2771 GNUNET_assert (trail->is_present == GNUNET_YES);
2773 /* Finger is not a friend. */
2774 if (trail->trail_length > 0)
2776 GNUNET_assert (NULL != (friend =
2777 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2778 &trail->trail_head->peer)));
2782 GNUNET_assert (NULL != (friend =
2783 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2784 &finger->finger_identity)));
2787 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2788 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2789 friend->trails_count--;
2790 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2791 GDS_ROUTING_SRC_TO_DEST,
2797 * Send trail teardown message across all the trails to reach to finger.
2798 * @param finger Finger whose all the trail should be freed.
2801 send_all_finger_trails_teardown (struct FingerInfo *finger)
2805 for (i = 0; i < finger->trails_count; i++)
2807 struct Trail *trail;
2809 trail = &finger->trail_list[i];
2810 GNUNET_assert (trail->is_present == GNUNET_YES);
2811 send_trail_teardown (finger, trail);
2812 trail->is_present = GNUNET_NO;
2818 * Free a specific trail
2819 * @param trail List of peers to be freed.
2822 free_trail (struct Trail *trail)
2824 struct Trail_Element *trail_element;
2826 while (NULL != (trail_element = trail->trail_head))
2828 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2831 GNUNET_free_non_null (trail_element);
2833 trail->trail_head = NULL;
2834 trail->trail_tail = NULL;
2839 * Free finger and its trail.
2840 * @param finger Finger to be freed.
2843 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2845 struct Trail *trail;
2848 /* Free all the trails to reach to finger */
2849 for (i = 0; i < finger->trails_count; i++)
2851 trail = &finger->trail_list[i];
2852 //FIXME: Check if there are any missing entry in this list because of
2853 // how we insert. If not then no need of this check.
2854 if (GNUNET_NO == trail->is_present)
2857 if (trail->trail_length > 0)
2861 trail->is_present = GNUNET_NO;
2864 finger->is_present = GNUNET_NO;
2865 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2870 * Add a new entry in finger table at finger_table_index.
2871 * In case I am my own finger, then we don't have a trail. In case of a friend,
2872 * we have a trail with unique id and '0' trail length.
2873 * In case a finger is a friend, then increment the trails count of the friend.
2874 * @param finger_identity Peer Identity of new finger
2875 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2876 * @param finger_trail_length Total number of peers in @a finger_trail.
2877 * @param trail_id Unique identifier of the trail.
2878 * @param finger_table_index Index in finger table.
2881 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2882 const struct GNUNET_PeerIdentity *finger_trail,
2883 unsigned int finger_trail_length,
2884 struct GNUNET_HashCode trail_id,
2885 unsigned int finger_table_index)
2887 struct FingerInfo *new_entry;
2888 struct FriendInfo *first_trail_hop;
2889 struct Trail *trail;
2892 new_entry = GNUNET_new (struct FingerInfo);
2893 new_entry->finger_identity = finger_identity;
2894 new_entry->finger_table_index = finger_table_index;
2895 new_entry->is_present = GNUNET_YES;
2897 /* If the new entry is my own identity. */
2898 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2901 new_entry->trails_count = 0;
2902 finger_table[finger_table_index] = *new_entry;
2903 GNUNET_free (new_entry);
2907 /* If finger is a friend, then we don't actually have a trail.
2908 * Just a trail id */
2909 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2912 new_entry->trail_list[0].trail_id = trail_id;
2913 new_entry->trails_count = 1;
2914 new_entry->trail_list[0].is_present = GNUNET_YES;
2915 new_entry->trail_list[0].trail_length = 0;
2916 new_entry->trail_list[0].trail_head = NULL;
2917 new_entry->trail_list[0].trail_tail = NULL;
2918 finger_table[finger_table_index] = *new_entry;
2919 GNUNET_assert (NULL !=
2921 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2922 &finger_identity)));
2924 first_trail_hop->trails_count++;
2925 GNUNET_free (new_entry);
2929 GNUNET_assert (NULL !=
2931 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2932 &finger_trail[0])));
2933 new_entry->trails_count = 1;
2934 first_trail_hop->trails_count++;
2936 /* Copy the finger trail into trail. */
2937 trail = GNUNET_new (struct Trail);
2938 while (i < finger_trail_length)
2940 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2942 element->next = NULL;
2943 element->prev = NULL;
2944 element->peer = finger_trail[i];
2945 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2951 /* Add trail to trail list. */
2952 new_entry->trail_list[0].trail_head = trail->trail_head;
2953 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2954 new_entry->trail_list[0].trail_length = finger_trail_length;
2955 new_entry->trail_list[0].trail_id = trail_id;
2956 new_entry->trail_list[0].is_present = GNUNET_YES;
2957 finger_table[finger_table_index] = *new_entry;
2958 GNUNET_free (new_entry);
2964 * Scan the trail to check if there is any other friend in the trail other than
2965 * first hop. If yes then shortcut the trail, send trail compression message to
2966 * peers which are no longer part of trail and send back the updated trail
2967 * and trail_length to calling function.
2968 * @param finger_identity Finger whose trail we will scan.
2969 * @param finger_trail [in, out] Trail to reach from source to finger,
2970 * @param finger_trail_length Total number of peers in original finger_trail.
2971 * @param finger_trail_id Unique identifier of the finger trail.
2972 * @return updated trail length in case we shortcut the trail, else original
2975 static struct GNUNET_PeerIdentity *
2976 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2977 const struct GNUNET_PeerIdentity *trail,
2978 unsigned int trail_length,
2979 struct GNUNET_HashCode trail_id,
2980 int *new_trail_length)
2982 struct FriendInfo *target_friend;
2983 struct GNUNET_PeerIdentity *new_trail;
2986 /* I am my own finger. */
2987 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2989 *new_trail_length = 0;
2993 if (0 == trail_length)
2995 *new_trail_length = 0;
2999 /* If finger identity is a friend. */
3000 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3002 *new_trail_length = 0;
3004 /* If there is trail to reach this finger/friend */
3005 if (trail_length > 0)
3007 /* Finger is your first friend. */
3008 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3009 GNUNET_assert (NULL !=
3011 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3015 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3016 trail_id, finger_identity,
3022 /* For other cases, when its neither a friend nor my own identity.*/
3023 for (i = trail_length - 1; i > 0; i--)
3025 /* If the element at this index in trail is a friend. */
3026 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3028 struct FriendInfo *target_friend;
3031 GNUNET_assert (NULL !=
3033 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3035 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3036 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3041 /* Copy the trail from index i to index (trail_length -1) into a new trail
3042 * and update new trail length */
3043 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3044 while (i < trail_length)
3046 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3050 *new_trail_length = j+1;
3055 /* If we did not compress the trail, return the original trail back.*/
3056 *new_trail_length = trail_length;
3057 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3058 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3064 * Periodic task to verify current successor. There can be multiple trails to reach
3065 * to successor, choose the shortest one and send verify successor message
3066 * across that trail.
3067 * @param cls closure for this task
3068 * @param tc the context under which the task is running
3071 send_verify_successor_message (void *cls,
3072 const struct GNUNET_SCHEDULER_TaskContext *tc)
3074 struct FriendInfo *target_friend;
3075 struct GNUNET_HashCode trail_id;
3077 struct GNUNET_TIME_Relative next_send_time;
3078 struct Trail *trail;
3079 struct Trail_Element *element;
3080 unsigned int trail_length;
3082 struct FingerInfo *successor;
3084 /* Schedule another send_find_finger_trail_message task. */
3085 next_send_time.rel_value_us =
3086 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3087 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3088 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3089 send_verify_successor_task =
3090 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3093 successor = &finger_table[0];
3094 for (i = 0; i < successor->trails_count; i++)
3096 trail = &successor->trail_list[i];
3097 if(GNUNET_YES == trail->is_present)
3101 if (i == successor->trails_count)
3104 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3105 &successor->finger_identity));
3107 /* Trail stored at this index. */
3108 GNUNET_assert (GNUNET_YES == trail->is_present);
3110 /* Code for testing ONLY: Store the successor for path tracking */
3111 if (track_topology && (NULL != GDS_stats))
3117 my_id_str = GNUNET_strdup (GNUNET_i2s (&my_identity));
3118 succ_id_str = GNUNET_strdup (GNUNET_i2s
3119 (&successor->finger_identity));
3120 GNUNET_asprintf (&key, "XDHT:%s:%s", my_id_str, succ_id_str);
3121 GNUNET_free (my_id_str);
3122 GNUNET_free (succ_id_str);
3123 GNUNET_STATISTICS_update (GDS_stats, key, 1, 0);
3127 trail_id = trail->trail_id;
3128 trail_length = trail->trail_length;
3130 if (trail_length > 0)
3132 /* Copy the trail into peer list. */
3133 struct GNUNET_PeerIdentity peer_list[trail_length];
3135 element = trail->trail_head;
3136 while (j < trail_length)
3138 peer_list[j] = element->peer;
3139 element = element->next;
3143 GNUNET_assert (NULL != (target_friend =
3144 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3146 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3147 successor->finger_identity,
3148 trail_id, peer_list, trail_length,
3154 GNUNET_assert (NULL != (target_friend =
3155 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3156 &successor->finger_identity)));
3157 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3158 successor->finger_identity,
3167 * Update the current search finger index.
3169 * FIXME document parameters!
3172 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3173 unsigned int finger_table_index)
3175 struct FingerInfo *successor;
3177 /* FIXME correct this: only move current index periodically */
3178 if (finger_table_index != current_search_finger_index)
3181 successor = &finger_table[0];
3182 GNUNET_assert (GNUNET_YES == successor->is_present);
3184 /* We were looking for immediate successor. */
3185 if (0 == current_search_finger_index)
3187 /* Start looking for immediate predecessor. */
3188 current_search_finger_index = PREDECESSOR_FINGER_ID;
3190 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3192 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3193 send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3199 current_search_finger_index = current_search_finger_index - 1;
3205 * Get the least significant bit set in val.
3208 * @return Position of first bit set, 65 in case of error.
3211 find_set_bit (uint64_t val)
3231 return 65; /* Some other bit was set to 1 as well. */
3238 * Calculate finger_table_index from initial 64 bit finger identity value that
3239 * we send in trail setup message.
3240 * @param ultimate_destination_finger_value Value that we calculated from our
3241 * identity and finger_table_index.
3242 * @param is_predecessor Is the entry for predecessor or not?
3243 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3244 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3247 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3248 unsigned int is_predecessor)
3252 unsigned int finger_table_index;
3254 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3255 my_id64 = GNUNET_ntohll (my_id64);
3257 /* Is this a predecessor finger? */
3258 if (1 == is_predecessor)
3260 diff = my_id64 - ultimate_destination_finger_value;
3262 finger_table_index = PREDECESSOR_FINGER_ID;
3264 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3269 diff = ultimate_destination_finger_value - my_id64;
3270 finger_table_index = find_set_bit (diff);
3272 return finger_table_index;
3277 * Remove finger and its associated data structures from finger table.
3278 * @param finger Finger to be removed.
3281 remove_existing_finger (struct FingerInfo *existing_finger,
3282 unsigned int finger_table_index)
3284 struct FingerInfo *finger;
3286 finger = &finger_table[finger_table_index];
3287 GNUNET_assert (GNUNET_YES == finger->is_present);
3289 /* If I am my own finger, then we have no trails. */
3290 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3293 finger->is_present = GNUNET_NO;
3294 memset ((void *)&finger_table[finger_table_index], 0,
3295 sizeof (finger_table[finger_table_index]));
3299 /* For all other fingers, send trail teardown across all the trails to reach
3300 finger, and free the finger. */
3301 send_all_finger_trails_teardown (finger);
3302 free_finger (finger, finger_table_index);
3308 * Check if there is already an entry in finger_table at finger_table_index.
3309 * We get the finger_table_index from 64bit finger value we got from the network.
3310 * -- If yes, then select the closest finger.
3311 * -- If new and existing finger are same, then check if you can store more
3313 * -- If yes then add trail, else keep the best trails to reach to the
3315 * -- If the new finger is closest, remove the existing entry, send trail
3316 * teardown message across all the trails to reach the existing entry.
3317 * Add the new finger.
3318 * -- If new and existing finger are different, and existing finger is closest
3320 * -- Update current_search_finger_index.
3321 * @param finger_identity Peer Identity of new finger
3322 * @param finger_trail Trail to reach the new finger
3323 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3324 * @param is_predecessor Is this entry for predecessor in finger_table?
3325 * @param finger_value 64 bit value of finger identity that we got from network.
3326 * @param finger_trail_id Unique identifier of @finger_trail.
3329 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3330 const struct GNUNET_PeerIdentity *finger_trail,
3331 unsigned int finger_trail_length,
3332 unsigned int is_predecessor,
3333 uint64_t finger_value,
3334 struct GNUNET_HashCode finger_trail_id)
3336 struct FingerInfo *existing_finger;
3337 const struct GNUNET_PeerIdentity *closest_peer;
3338 struct FingerInfo *successor;
3339 int updated_finger_trail_length;
3340 unsigned int finger_table_index;
3342 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3343 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3345 /* Invalid finger_table_index. */
3346 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3348 GNUNET_break_op (0);
3352 /* New entry same as successor. */
3353 if ((0 != finger_table_index) &&
3354 (PREDECESSOR_FINGER_ID != finger_table_index))
3356 successor = &finger_table[0];
3357 if (GNUNET_NO == successor->is_present)
3359 GNUNET_break_op (0);
3362 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3363 &successor->finger_identity))
3365 current_search_finger_index = 0;
3366 /* We slow down the find_finger_trail_task as we have completed the circle. */
3367 next_send_time = GNUNET_TIME_STD_BACKOFF(next_send_time);
3372 struct FingerInfo prev_finger;
3373 prev_finger = finger_table[finger_table_index - 1];
3374 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3375 &prev_finger.finger_identity))
3377 current_search_finger_index--;
3382 existing_finger = &finger_table[finger_table_index];
3384 /* No entry present in finger_table for given finger map index. */
3385 if (GNUNET_NO == existing_finger->is_present)
3387 struct GNUNET_PeerIdentity *updated_trail;
3389 /* Shorten the trail if possible. */
3390 updated_finger_trail_length = finger_trail_length;
3391 updated_trail = scan_and_compress_trail (finger_identity, finger_trail,
3392 finger_trail_length,
3394 &updated_finger_trail_length);
3396 add_new_finger (finger_identity, updated_trail,
3397 updated_finger_trail_length,
3398 finger_trail_id, finger_table_index);
3399 GNUNET_free_non_null(updated_trail);
3400 update_current_search_finger_index (finger_identity,
3401 finger_table_index);
3406 /* If existing entry and finger identity are not same. */
3407 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3410 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3415 /* If the new finger is the closest peer. */
3416 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3418 struct GNUNET_PeerIdentity *updated_trail;
3419 /* Shorten the trail if possible. */
3420 updated_finger_trail_length = finger_trail_length;
3422 scan_and_compress_trail (finger_identity, finger_trail,
3423 finger_trail_length, finger_trail_id,
3424 &updated_finger_trail_length);
3425 remove_existing_finger (existing_finger, finger_table_index);
3426 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3427 finger_trail_id, finger_table_index);
3428 GNUNET_free_non_null((struct GNUNET_PeerIdentity *)updated_trail);
3432 /* Existing finger is the closest one. We need to send trail teardown
3433 across the trail setup in routing table of all the peers. */
3434 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3436 if (finger_trail_length > 0)
3437 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3438 GDS_ROUTING_SRC_TO_DEST,
3441 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3442 GDS_ROUTING_SRC_TO_DEST,
3449 /* If both new and existing entry are same as my_identity, then do nothing. */
3450 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3455 /* If the existing finger is not a friend. */
3457 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3458 &existing_finger->finger_identity))
3460 struct GNUNET_PeerIdentity *updated_trail;
3462 /* Shorten the trail if possible. */
3463 updated_finger_trail_length = finger_trail_length;
3465 scan_and_compress_trail (finger_identity, finger_trail,
3466 finger_trail_length, finger_trail_id,
3467 &updated_finger_trail_length);
3468 /* If there is space to store more trails. */
3469 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3470 add_new_trail (existing_finger, updated_trail,
3471 updated_finger_trail_length, finger_trail_id);
3473 select_and_replace_trail (existing_finger, updated_trail,
3474 updated_finger_trail_length, finger_trail_id);
3478 update_current_search_finger_index (finger_identity, finger_table_index);
3483 * Core handler for P2P put messages.
3484 * @param cls closure
3485 * @param peer sender of the request
3486 * @param message message
3487 * @return #GNUNET_OK to keep the connection open,
3488 * #GNUNET_SYSERR to close it (signal serious error)
3491 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3492 const struct GNUNET_MessageHeader *message)
3494 struct PeerPutMessage *put;
3495 struct GNUNET_PeerIdentity *put_path;
3496 struct GNUNET_PeerIdentity best_known_dest;
3497 struct GNUNET_HashCode intermediate_trail_id;
3498 struct GNUNET_PeerIdentity *next_hop;
3499 enum GNUNET_DHT_RouteOption options;
3500 struct GNUNET_HashCode test_key;
3504 size_t payload_size;
3507 msize = ntohs (message->size);
3508 if (msize < sizeof (struct PeerPutMessage))
3510 GNUNET_break_op (0);
3514 put = (struct PeerPutMessage *) message;
3515 putlen = ntohl (put->put_path_length);
3519 sizeof (struct PeerPutMessage) +
3520 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3522 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3524 GNUNET_break_op (0);
3528 GNUNET_STATISTICS_update (GDS_stats,
3530 ("# Bytes received from other peers"), (int64_t) msize,
3533 best_known_dest = put->best_known_destination;
3534 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3535 payload = &put_path[putlen];
3536 options = ntohl (put->options);
3537 intermediate_trail_id = put->intermediate_trail_id;
3539 payload_size = msize - (sizeof (struct PeerPutMessage) +
3540 putlen * sizeof (struct GNUNET_PeerIdentity));
3542 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3543 payload, payload_size, &test_key))
3546 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3548 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3549 GNUNET_break_op (0);
3550 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3551 "PUT with key `%s' for block with key %s\n",
3552 put_s, GNUNET_h2s_full (&test_key));
3553 GNUNET_free (put_s);
3558 GNUNET_break_op (0);
3561 /* cannot verify, good luck */
3565 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3567 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3568 ntohl (put->block_type),
3570 NULL, 0, /* bloom filer */
3571 NULL, 0, /* xquery */
3572 payload, payload_size))
3574 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3575 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3578 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3579 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3580 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3581 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3582 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3583 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3585 GNUNET_break_op (0);
3590 /* extend 'put path' by sender */
3591 struct GNUNET_PeerIdentity pp[putlen + 1];
3592 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3594 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3601 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3602 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3604 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3605 GDS_ROUTING_SRC_TO_DEST);
3606 if (NULL == next_hop)
3608 GNUNET_STATISTICS_update (GDS_stats,
3609 gettext_noop ("# Next hop to forward the packet not found "
3610 "trail setup request, packet dropped."),
3612 return GNUNET_SYSERR;
3617 struct Closest_Peer successor;
3618 key_value = GNUNET_ntohll (key_value);
3619 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3620 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3621 *next_hop = successor.next_hop;
3622 intermediate_trail_id = successor.trail_id;
3623 best_known_dest = successor.best_known_destination;
3626 GDS_CLIENTS_process_put (options,
3627 ntohl (put->block_type),
3628 ntohl (put->hop_count),
3629 ntohl (put->desired_replication_level),
3631 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3636 /* I am the final destination */
3637 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3639 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3640 &(put->key),putlen, pp, ntohl (put->block_type),
3641 payload_size, payload);
3645 GDS_NEIGHBOURS_send_put (&put->key,
3646 ntohl (put->block_type),ntohl (put->options),
3647 ntohl (put->desired_replication_level),
3648 best_known_dest, intermediate_trail_id, next_hop,
3649 ntohl (put->hop_count), putlen, pp,
3650 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3651 payload, payload_size);
3658 * Core handler for p2p get requests.
3660 * @param cls closure
3661 * @param peer sender of the request
3662 * @param message message
3663 * @return #GNUNET_OK to keep the connection open,
3664 * #GNUNET_SYSERR to close it (signal serious error)
3667 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3668 const struct GNUNET_MessageHeader *message)
3670 const struct PeerGetMessage *get;
3671 const struct GNUNET_PeerIdentity *get_path;
3672 struct GNUNET_PeerIdentity best_known_dest;
3673 struct GNUNET_HashCode intermediate_trail_id;
3674 struct GNUNET_PeerIdentity *next_hop;
3675 uint32_t get_length;
3679 msize = ntohs (message->size);
3680 if (msize < sizeof (struct PeerGetMessage))
3682 GNUNET_break_op (0);
3686 get = (const struct PeerGetMessage *)message;
3687 get_length = ntohl (get->get_path_length);
3688 best_known_dest = get->best_known_destination;
3689 intermediate_trail_id = get->intermediate_trail_id;
3690 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3693 sizeof (struct PeerGetMessage) +
3694 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3696 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3698 GNUNET_break_op (0);
3702 GNUNET_STATISTICS_update (GDS_stats,
3704 ("# Bytes received from other peers"), msize,
3707 /* Add sender to get path */
3708 struct GNUNET_PeerIdentity gp[get_length + 1];
3710 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3711 gp[get_length] = *peer;
3712 get_length = get_length + 1;
3714 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3715 key_value = GNUNET_ntohll (key_value);
3717 /* I am not the final destination. I am part of trail to reach final dest. */
3718 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3720 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3721 GDS_ROUTING_SRC_TO_DEST);
3722 if (NULL == next_hop)
3724 GNUNET_STATISTICS_update (GDS_stats,
3725 gettext_noop ("# Next hop to forward the packet not found "
3726 "GET request, packet dropped."),
3728 return GNUNET_SYSERR;
3733 struct Closest_Peer successor;
3735 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3736 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3737 *next_hop = successor.next_hop;
3738 best_known_dest = successor.best_known_destination;
3739 intermediate_trail_id = successor.trail_id;
3742 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3743 get->desired_replication_level, get->get_path_length,
3745 /* I am the final destination. */
3746 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3748 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3750 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3751 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3752 get_length = get_length + 1;
3754 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3755 get_length, final_get_path,
3756 &final_get_path[get_length-2], &my_identity);
3760 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3761 get->desired_replication_level, best_known_dest,
3762 intermediate_trail_id, next_hop, 0,
3770 * Core handler for get result
3771 * @param cls closure
3772 * @param peer sender of the request
3773 * @param message message
3774 * @return #GNUNET_OK to keep the connection open,
3775 * #GNUNET_SYSERR to close it (signal serious error)
3778 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3779 const struct GNUNET_MessageHeader *message)
3781 const struct PeerGetResultMessage *get_result;
3782 const struct GNUNET_PeerIdentity *get_path;
3783 const struct GNUNET_PeerIdentity *put_path;
3784 const void *payload;
3785 size_t payload_size;
3787 unsigned int getlen;
3788 unsigned int putlen;
3789 int current_path_index;
3791 msize = ntohs (message->size);
3792 if (msize < sizeof (struct PeerGetResultMessage))
3794 GNUNET_break_op (0);
3798 get_result = (const struct PeerGetResultMessage *)message;
3799 getlen = ntohl (get_result->get_path_length);
3800 putlen = ntohl (get_result->put_path_length);
3803 sizeof (struct PeerGetResultMessage) +
3804 getlen * sizeof (struct GNUNET_PeerIdentity) +
3805 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3807 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3809 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3811 GNUNET_break_op (0);
3815 GNUNET_STATISTICS_update (GDS_stats,
3817 ("# Bytes received from other peers"), msize,
3820 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3821 get_path = &put_path[putlen];
3822 payload = (const void *) &get_path[getlen];
3823 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3824 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3826 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3828 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3829 getlen, get_path, putlen,
3830 put_path, get_result->type, payload_size, payload);
3835 current_path_index = search_my_index (get_path, getlen);
3836 if (-1 == current_path_index )
3839 return GNUNET_SYSERR;
3841 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3842 &get_path[current_path_index - 1],
3843 &(get_result->querying_peer), putlen, put_path,
3844 getlen, get_path, get_result->expiration_time,
3845 payload, payload_size);
3848 return GNUNET_SYSERR;
3853 * Find the next hop to pass trail setup message. First find the local best known
3854 * hop from your own identity, friends and finger. If you were part of trail,
3855 * then get the next hop from routing table. Compare next_hop from routing table
3856 * and local best known hop, and return the closest one to final_dest_finger_val
3857 * @param final_dest_finger_val 64 bit value of finger identity
3858 * @param intermediate_trail_id If you are part of trail to reach to some other
3859 * finger, then it is the trail id to reach to
3860 * that finger, else set to 0.
3861 * @param is_predecessor Are we looking for closest successor or predecessor.
3862 * @param current_dest In case you are part of trail, then finger to which
3863 * we should forward the message. Else my own identity
3864 * @return Closest Peer for @a final_dest_finger_val
3866 static struct Closest_Peer
3867 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3868 struct GNUNET_HashCode intermediate_trail_id,
3869 unsigned int is_predecessor,
3870 struct GNUNET_PeerIdentity prev_hop,
3871 struct GNUNET_PeerIdentity source,
3872 struct GNUNET_PeerIdentity *current_dest)
3874 struct Closest_Peer peer;
3876 /* Find a local best known peer. */
3877 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3879 /* Am I just a part of a trail towards a finger (current_destination)? */
3880 /* Select best successor among one found locally and current_destination
3881 * that we got from network.*/
3882 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3883 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3886 const struct GNUNET_PeerIdentity *closest_peer;
3888 closest_peer = select_closest_peer (&peer.best_known_destination,
3890 final_dest_finger_val,
3893 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3894 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3896 struct GNUNET_PeerIdentity *next_hop;
3898 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3899 GDS_ROUTING_SRC_TO_DEST);
3900 /* It may happen that trail teardown message got delayed and hence,
3901 the previous hop sent the message over intermediate trail id.In that
3902 case next_hop could be NULL. */
3903 if(NULL != next_hop)
3905 peer.next_hop = *next_hop;
3906 peer.best_known_destination = *current_dest;
3907 peer.trail_id = intermediate_trail_id;
3915 * Core handle for PeerTrailSetupMessage.
3916 * @param cls closure
3917 * @param message message
3918 * @param peer peer identity this notification is about
3919 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3922 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3923 const struct GNUNET_MessageHeader *message)
3925 const struct PeerTrailSetupMessage *trail_setup;
3926 const struct GNUNET_PeerIdentity *trail_peer_list;
3927 struct GNUNET_PeerIdentity current_dest;
3928 struct FriendInfo *target_friend;
3929 struct GNUNET_PeerIdentity source;
3930 uint64_t final_dest_finger_val;
3931 struct GNUNET_HashCode intermediate_trail_id;
3932 struct GNUNET_HashCode trail_id;
3933 unsigned int is_predecessor;
3934 uint32_t trail_length;
3938 msize = ntohs (message->size);
3939 if (msize < sizeof (struct PeerTrailSetupMessage))
3941 GNUNET_break_op (0);
3942 return GNUNET_SYSERR;
3945 trail_setup = (const struct PeerTrailSetupMessage *) message;
3946 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3947 sizeof (struct GNUNET_PeerIdentity);
3948 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3949 sizeof (struct GNUNET_PeerIdentity) != 0)
3951 GNUNET_break_op (0);
3955 GNUNET_STATISTICS_update (GDS_stats,
3957 ("# Bytes received from other peers"), msize,
3960 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3961 current_dest = trail_setup->best_known_destination;
3962 trail_id = trail_setup->trail_id;
3963 final_dest_finger_val =
3964 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3965 source = trail_setup->source_peer;
3966 is_predecessor = ntohl (trail_setup->is_predecessor);
3967 intermediate_trail_id = trail_setup->intermediate_trail_id;
3969 /* Did the friend insert its ID in the trail list? */
3970 if (trail_length > 0 &&
3971 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (*peer)))
3973 GNUNET_break_op (0);
3974 return GNUNET_SYSERR;
3977 /* If I was the source and got the message back, then set trail length to 0.*/
3978 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3980 /* IF (!) the peers know the destinations of the trails in their routing
3983 * This shoud only happen after 1 hop, since the first message is sent
3984 * to random friend, and we can happen to be on the best trail to the dest.
3985 * If the first friend selects someone else, the request should never come
3990 // GNUNET_break_op (1 == trail_length);
3994 /* Check if you are present in the trail seen so far? */
3995 if(trail_length > 0)
3997 for (i = 0; i < trail_length ; i++)
3999 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4001 //Here if you already were present in the trail. then you
4002 // shoudl trail length to i + 1
4009 /* Is my routing table full? */
4010 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4012 GNUNET_assert (NULL !=
4014 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4015 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4016 my_identity, is_predecessor,
4017 trail_peer_list, trail_length,
4018 trail_id, target_friend,
4019 CONGESTION_TIMEOUT);
4023 /* Get the next hop to forward the trail setup request. */
4024 struct Closest_Peer next_peer =
4025 get_local_best_known_next_hop (final_dest_finger_val,
4026 intermediate_trail_id,
4032 /* Am I the final destination? */
4033 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4036 /* If I was not the source of this message for which now I am destination */
4037 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4039 GDS_ROUTING_add (trail_id, *peer, my_identity);
4042 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4044 finger_table_add (my_identity, NULL, 0, is_predecessor,
4045 final_dest_finger_val, trail_id);
4049 if (trail_length > 0)
4050 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4052 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4053 if (NULL == target_friend)
4055 GNUNET_break_op (0);
4056 return GNUNET_SYSERR;
4059 GDS_NEIGHBOURS_send_trail_setup_result (source,
4061 target_friend, trail_length,
4064 final_dest_finger_val,trail_id);
4066 else /* I'm not the final destination. */
4068 GNUNET_assert (NULL !=
4070 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4071 &next_peer.next_hop)));
4073 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4075 /* Add yourself to list of peers. */
4076 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4078 memcpy (peer_list, trail_peer_list,
4079 trail_length * sizeof (struct GNUNET_PeerIdentity));
4080 peer_list[trail_length] = my_identity;
4082 GDS_NEIGHBOURS_send_trail_setup (source,
4083 final_dest_finger_val,
4084 next_peer.best_known_destination,
4085 target_friend, trail_length + 1, peer_list,
4086 is_predecessor, trail_id,
4087 next_peer.trail_id);
4090 GDS_NEIGHBOURS_send_trail_setup (source,
4091 final_dest_finger_val,
4092 next_peer.best_known_destination,
4093 target_friend, 0, NULL,
4094 is_predecessor, trail_id,
4095 next_peer.trail_id);
4101 /* FIXME: here we are calculating my_index and comparing also in this function.
4102 And we are doing it again here in this function. Re factor the code. */
4104 * FIXME: Should we call this function everywhere in all the handle functions
4105 * where we have a trail to verify from or a trail id. something like
4106 * if prev hop is not same then drop the message.
4107 * Check if sender_peer and peer from which we should receive the message are
4108 * same or different.
4109 * @param trail_peer_list List of peers in trail
4110 * @param trail_length Total number of peers in @a trail_peer_list
4111 * @param sender_peer Peer from which we got the message.
4112 * @param finger_identity Finger to which trail is setup. It is not part of trail.
4113 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
4114 * message are different.
4115 * #GNUNET_NO if sender_peer and peer from which we should receive the
4116 * message are different.
4119 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
4120 unsigned int trail_length,
4121 const struct GNUNET_PeerIdentity *sender_peer,
4122 struct GNUNET_PeerIdentity finger_identity,
4123 struct GNUNET_PeerIdentity source_peer)
4127 /* I am the source peer. */
4128 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4131 /* Is the first element of the trail is sender_peer.*/
4132 if (trail_length > 0)
4134 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4140 /* Is finger the sender peer? */
4141 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4148 /* Get my current location in the trail. */
4149 my_index = search_my_index (trail_peer_list, trail_length);
4153 /* I am the last element in the trail. */
4154 if ((trail_length - 1) == my_index)
4156 /* Is finger the sender_peer? */
4157 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4163 /* Is peer after me in trail the sender peer? */
4164 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4165 &trail_peer_list[my_index + 1]))
4175 * FIXME: we should also add a case where we search if we are present in the trail
4177 * Core handle for p2p trail setup result messages.
4179 * @param message message
4180 * @param peer sender of this message.
4181 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4184 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4185 const struct GNUNET_MessageHeader *message)
4187 const struct PeerTrailSetupResultMessage *trail_result;
4188 const struct GNUNET_PeerIdentity *trail_peer_list;
4189 struct GNUNET_PeerIdentity next_hop;
4190 struct FriendInfo *target_friend;
4191 struct GNUNET_PeerIdentity querying_peer;
4192 struct GNUNET_PeerIdentity finger_identity;
4193 uint32_t trail_length;
4194 uint64_t ulitmate_destination_finger_value;
4195 uint32_t is_predecessor;
4196 struct GNUNET_HashCode trail_id;
4200 msize = ntohs (message->size);
4201 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4203 GNUNET_break_op (0);
4207 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4208 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4209 sizeof (struct GNUNET_PeerIdentity);
4210 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4211 sizeof (struct GNUNET_PeerIdentity) != 0)
4213 GNUNET_break_op (0);
4217 GNUNET_STATISTICS_update (GDS_stats,
4219 ("# Bytes received from other peers"), msize,
4222 is_predecessor = ntohl (trail_result->is_predecessor);
4223 querying_peer = trail_result->querying_peer;
4224 finger_identity = trail_result->finger_identity;
4225 trail_id = trail_result->trail_id;
4226 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4227 ulitmate_destination_finger_value =
4228 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4230 /* FIXME: here we are calculating my_index and comparing also in this function.
4231 And we are doing it again here in this function. Re factor the code. */
4232 /* Ensure that sender peer is the peer from which we were expecting the message. */
4234 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
4236 peer, finger_identity, querying_peer))
4238 GNUNET_break_op (0);
4239 return GNUNET_SYSERR;
4243 /*TODO:URGENT Check if I am already present in the trail. If yes then its an error,
4244 as in trail setup we ensure that it should never happen. */
4245 /* Am I the one who initiated the query? */
4246 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4248 /* If I am my own finger identity, error. */
4249 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4251 GNUNET_break_op (0);
4252 return GNUNET_SYSERR;
4254 GDS_ROUTING_add (trail_id, my_identity, *peer);
4255 finger_table_add (finger_identity, trail_peer_list, trail_length,
4256 is_predecessor, ulitmate_destination_finger_value, trail_id);
4260 /* Get my location in the trail. */
4261 my_index = search_my_index (trail_peer_list, trail_length);
4265 return GNUNET_SYSERR;
4269 next_hop = trail_result->querying_peer;
4271 next_hop = trail_peer_list[my_index - 1];
4273 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4274 if (NULL == target_friend)
4276 GNUNET_break_op (0);
4277 return GNUNET_SYSERR;
4280 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4281 &(trail_result->finger_identity))))
4283 GNUNET_break_op (0);
4284 return GNUNET_SYSERR;
4287 GDS_ROUTING_add (trail_id, next_hop, *peer);
4289 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4290 target_friend, trail_length, trail_peer_list,
4292 ulitmate_destination_finger_value,
4300 * @param trail Trail to be inverted
4301 * @param trail_length Total number of peers in the trail.
4302 * @return Updated trail
4304 static struct GNUNET_PeerIdentity *
4305 invert_trail (const struct GNUNET_PeerIdentity *trail,
4306 unsigned int trail_length)
4310 struct GNUNET_PeerIdentity *inverted_trail;
4312 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4315 j = trail_length - 1;
4316 while (i < trail_length)
4318 inverted_trail[i] = trail[j];
4323 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4324 &inverted_trail[0]));
4325 return inverted_trail;
4330 * Return the shortest trail among all the trails to reach to finger from me.
4331 * @param finger Finger
4332 * @param shortest_trail_length[out] Trail length of shortest trail from me
4334 * @return Shortest trail.
4336 static struct GNUNET_PeerIdentity *
4337 get_shortest_trail (struct FingerInfo *finger,
4338 unsigned int *trail_length)
4340 struct Trail *trail;
4341 unsigned int flag = 0;
4342 unsigned int shortest_trail_index = 0;
4343 int shortest_trail_length = -1;
4344 struct Trail_Element *trail_element;
4345 struct GNUNET_PeerIdentity *trail_list;
4348 trail = GNUNET_new (struct Trail);
4350 /* Get the shortest trail to reach to current successor. */
4351 for (i = 0; i < finger->trails_count; i++)
4353 trail = &finger->trail_list[i];
4357 shortest_trail_index = i;
4358 shortest_trail_length = trail->trail_length;
4363 if (shortest_trail_length > trail->trail_length)
4365 shortest_trail_index = i;
4366 shortest_trail_length = trail->trail_length;
4371 /* Copy the shortest trail and return. */
4372 trail = &finger->trail_list[shortest_trail_index];
4373 trail_element = trail->trail_head;
4375 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4376 shortest_trail_length);
4378 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4380 trail_list[i] = trail_element->peer;
4383 GNUNET_assert(shortest_trail_length != -1);
4385 *trail_length = shortest_trail_length;
4391 * Check if trail_1 and trail_2 have any common element. If yes then join
4392 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4393 * @param trail_1 Trail from source to me, NOT including endpoints.
4394 * @param trail_1_len Total number of peers @a trail_1
4395 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4396 * @param trail_2_len Total number of peers @a trail_2
4397 * @param joined_trail_len Total number of peers in combined trail of trail_1
4399 * @return Joined trail.
4401 static struct GNUNET_PeerIdentity *
4402 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4403 unsigned int trail_1_len,
4404 struct GNUNET_PeerIdentity *trail_2,
4405 unsigned int trail_2_len,
4406 unsigned int *joined_trail_len)
4408 struct GNUNET_PeerIdentity *joined_trail;
4413 for (i = 0; i < trail_1_len; i++)
4415 for (j = 0; j < trail_2_len; j++)
4417 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4420 *joined_trail_len = i + (trail_2_len - j) + 1;
4421 joined_trail = GNUNET_malloc (*joined_trail_len *
4422 sizeof(struct GNUNET_PeerIdentity));
4425 /* Copy all the elements from 0 to i into joined_trail. */
4426 for(k = 0; k < (i+1); k++)
4428 joined_trail[k] = trail_1[k];
4431 /* Increment j as entry stored is same as entry stored at i*/
4434 /* Copy all the elements from j+1 to trail_2_len-1 to joined trail.*/
4435 while((k < *joined_trail_len) && (j < trail_2_len));
4437 joined_trail[k] = trail_2[j];
4442 return joined_trail;
4446 /* Here you should join the trails. */
4447 *joined_trail_len = trail_1_len + trail_2_len + 1;
4448 joined_trail = GNUNET_malloc (*joined_trail_len *
4449 sizeof(struct GNUNET_PeerIdentity));
4451 while( i < trail_1_len)
4453 joined_trail[i] = trail_1[i];
4456 joined_trail[i] = my_identity;
4459 for (j = 0; i < *joined_trail_len; i++,j++)
4461 joined_trail[i] = trail_2[j];
4463 return joined_trail;
4468 * Return the trail from source to my current predecessor. Check if source
4469 * is already part of the this trail, if yes then return the shorten trail.
4470 * @param current_trail Trail from source to me, NOT including the endpoints.
4471 * @param current_trail_length Number of peers in @a current_trail.
4472 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4473 * source to my predecessor, NOT including
4475 * @return Trail from source to my predecessor.
4477 static struct GNUNET_PeerIdentity *
4478 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4479 const struct GNUNET_PeerIdentity *trail_src_to_me,
4480 unsigned int trail_src_to_me_len,
4481 unsigned int *trail_src_to_curr_pred_length)
4483 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4484 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4485 unsigned int trail_me_to_curr_pred_length;
4486 struct FingerInfo *current_predecessor;
4490 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4491 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4492 &trail_me_to_curr_pred_length);
4494 /* If there is only on element in the trail, and that element is source.*/
4495 if ((trail_me_to_curr_pred_length == 1) &&
4496 (0 == GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4497 &trail_me_to_curr_pred[0])))
4499 *trail_src_to_curr_pred_length = 0;
4500 GNUNET_free_non_null(trail_me_to_curr_pred);
4504 /* Check if trail_me_to_curr_pred contains source. */
4505 if (trail_me_to_curr_pred_length > 1)
4507 for(i = trail_me_to_curr_pred_length - 1; i > 0; i--)
4509 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4510 &trail_me_to_curr_pred[i]))
4513 /* Source is NOT part of trail. */
4516 /* Source is the last element in the trail to reach to my pred.
4517 Source is direct friend of the pred. */
4518 if (trail_me_to_curr_pred_length == i)
4520 *trail_src_to_curr_pred_length = 0;
4524 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4525 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4526 *trail_src_to_curr_pred_length);
4527 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4529 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4531 GNUNET_free_non_null(trail_me_to_curr_pred);
4532 return trail_src_to_curr_pred;
4534 /* Is first element source? Then exclude first element and copy rest of the
4536 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4537 &trail_me_to_curr_pred[0]))
4539 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - 1;
4540 trail_src_to_curr_pred = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)*
4541 *trail_src_to_curr_pred_length);
4543 for(j=0; j < *trail_src_to_curr_pred_length;j++)
4545 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[j+1];
4547 return trail_src_to_curr_pred;
4552 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4553 trail_src_to_me_len,
4554 trail_me_to_curr_pred,
4555 trail_me_to_curr_pred_length,
4557 *trail_src_to_curr_pred_length = len;
4558 GNUNET_free_non_null(trail_me_to_curr_pred);
4559 return trail_src_to_curr_pred;
4564 * Add finger as your predecessor. To add, first generate a new trail id, invert
4565 * the trail to get the trail from me to finger, add an entry in your routing
4566 * table, send add trail message to peers which are part of trail from me to
4567 * finger and add finger in finger table.
4570 * @param trail_length
4573 update_predecessor (struct GNUNET_PeerIdentity finger,
4574 struct GNUNET_PeerIdentity *trail,
4575 unsigned int trail_length)
4577 struct GNUNET_HashCode trail_to_new_predecessor_id;
4578 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4579 struct FriendInfo *target_friend;
4581 /* Generate trail id for trail from me to new predecessor = finger. */
4582 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4583 &trail_to_new_predecessor_id,
4584 sizeof (trail_to_new_predecessor_id));
4586 /* Finger is a friend. */
4587 if (trail_length == 0)
4589 trail_to_new_predecessor = NULL;
4590 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4591 GNUNET_assert (NULL != (target_friend =
4592 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4597 /* Invert the trail to get the trail from me to finger, NOT including the
4599 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4600 &trail[trail_length-1]));
4602 trail_to_new_predecessor = invert_trail (trail, trail_length);
4604 /* Add an entry in your routing table. */
4605 GDS_ROUTING_add (trail_to_new_predecessor_id,
4607 trail_to_new_predecessor[0]);
4609 GNUNET_assert (NULL != (target_friend =
4610 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4611 &trail_to_new_predecessor[0])));
4612 GNUNET_assert (NULL != (
4613 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4614 &trail[trail_length - 1])));
4617 /* Add entry in routing table of all peers that are part of trail from me
4618 to finger, including finger. */
4619 GDS_NEIGHBOURS_send_add_trail (my_identity,
4621 trail_to_new_predecessor_id,
4622 trail_to_new_predecessor,
4626 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4627 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4628 GNUNET_free_non_null(trail_to_new_predecessor);
4633 * Check if you already have a predecessor. If not then add finger as your
4634 * predecessor. If you have predecessor, then compare two peer identites.
4635 * If finger is correct predecessor, then remove the old entry, add finger in
4636 * finger table and send add_trail message to add the trail in the routing
4637 * table of all peers which are part of trail to reach from me to finger.
4638 * @param finger New peer which may be our predecessor.
4639 * @param trail List of peers to reach from @finger to me.
4640 * @param trail_length Total number of peer in @a trail.
4643 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4644 struct GNUNET_PeerIdentity *trail,
4645 unsigned int trail_length)
4647 struct FingerInfo *current_predecessor;
4648 const struct GNUNET_PeerIdentity *closest_peer;
4649 uint64_t predecessor_value;
4650 unsigned int is_predecessor = 1;
4652 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4654 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4656 /* No predecessor. Add finger as your predecessor. */
4657 if (GNUNET_NO == current_predecessor->is_present)
4659 update_predecessor (finger, trail, trail_length);
4663 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4669 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4670 closest_peer = select_closest_peer (&finger,
4671 ¤t_predecessor->finger_identity,
4672 predecessor_value, is_predecessor);
4674 /* Finger is the closest predecessor. Remove the existing one and add the new
4676 if (closest_peer == &finger)
4678 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4679 update_predecessor (finger, trail, trail_length);
4687 * Core handle for p2p verify successor messages.
4688 * @param cls closure
4689 * @param message message
4690 * @param peer peer identity this notification is about
4691 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4694 handle_dht_p2p_verify_successor(void *cls,
4695 const struct GNUNET_PeerIdentity *peer,
4696 const struct GNUNET_MessageHeader *message)
4698 const struct PeerVerifySuccessorMessage *vsm;
4699 struct GNUNET_HashCode trail_id;
4700 struct GNUNET_PeerIdentity successor;
4701 struct GNUNET_PeerIdentity source_peer;
4702 struct GNUNET_PeerIdentity *trail;
4703 struct GNUNET_PeerIdentity *next_hop;
4704 struct FingerInfo current_predecessor;
4705 struct FriendInfo *target_friend;
4706 unsigned int trail_src_to_curr_pred_len = 0;
4707 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4708 unsigned int trail_length;
4711 msize = ntohs (message->size);
4713 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4715 GNUNET_break_op (0);
4719 vsm = (const struct PeerVerifySuccessorMessage *) message;
4720 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4721 sizeof (struct GNUNET_PeerIdentity);
4722 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4723 sizeof (struct GNUNET_PeerIdentity) != 0)
4725 GNUNET_break_op (0);
4729 GNUNET_STATISTICS_update (GDS_stats,
4731 ("# Bytes received from other peers"), msize,
4734 trail_id = vsm->trail_id;
4735 source_peer = vsm->source_peer;
4736 successor = vsm->successor;
4737 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4740 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4742 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4744 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4745 if (NULL == next_hop)
4747 GNUNET_break_op (0);
4748 return GNUNET_SYSERR;
4751 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4753 if(NULL == target_friend)
4758 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4759 trail_id, trail, trail_length,
4764 /* I am the destination of this message. */
4766 /* Check if the source_peer could be our predecessor and if yes then update
4768 compare_and_update_predecessor (source_peer, trail, trail_length);
4769 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4770 unsigned int flag = 0;
4772 /* Is source of this message NOT my predecessor. */
4773 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4776 /* Check if trail contains current_predecessor. */
4778 for (i = 0; i < trail_length; i++)
4780 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail[i],
4781 ¤t_predecessor.finger_identity))
4785 trail_src_to_curr_pred_len = i;
4786 trail_src_to_curr_pred = GNUNET_malloc (trail_src_to_curr_pred_len *
4787 sizeof(struct GNUNET_PeerIdentity));
4792 trail_src_to_curr_pred[k] = trail[k];
4800 trail_src_to_curr_pred =
4801 get_trail_src_to_curr_pred (source_peer,
4804 &trail_src_to_curr_pred_len);
4809 trail_src_to_curr_pred_len = trail_length;
4812 trail_src_to_curr_pred =
4813 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4814 *trail_src_to_curr_pred_len);
4815 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4817 trail_src_to_curr_pred[i] = trail[i];
4821 GNUNET_assert (NULL !=
4823 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4824 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4825 current_predecessor.finger_identity,
4826 trail_id, trail_src_to_curr_pred,
4827 trail_src_to_curr_pred_len,
4828 GDS_ROUTING_DEST_TO_SRC,
4830 GNUNET_free_non_null(trail_src_to_curr_pred);
4836 * If the trail from me to my probable successor contains a friend not
4837 * at index 0, then we can shorten the trail.
4838 * @param probable_successor Peer which is our probable successor
4839 * @param trail_me_to_probable_successor Peers in path from me to my probable
4840 * successor, NOT including the endpoints.
4841 * @param trail_me_to_probable_successor_len Total number of peers in
4842 * @a trail_me_to_probable_succesor.
4843 * @return Updated trail, if any friend found.
4844 * Else the trail_me_to_probable_successor.
4846 struct GNUNET_PeerIdentity *
4847 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4848 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4849 unsigned int trail_me_to_probable_successor_len,
4850 unsigned int *trail_to_new_successor_length)
4854 struct GNUNET_PeerIdentity *trail_to_new_successor;
4856 /* Probable successor is a friend */
4857 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4858 &probable_successor))
4860 trail_to_new_successor = NULL;
4861 *trail_to_new_successor_length = 0;
4862 return trail_to_new_successor;
4865 /* Is there any friend of yours in this trail. */
4866 if(trail_me_to_probable_successor_len > 1)
4868 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4870 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4871 &trail_me_to_probable_successor[i]))
4875 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4876 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4877 *trail_to_new_successor_length);
4880 for(j = 0;j < *trail_to_new_successor_length;i++,j++)
4882 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4885 return trail_to_new_successor;
4889 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4890 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4892 trail_to_new_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4893 *trail_to_new_successor_length);
4895 for(i = 0; i < *trail_to_new_successor_length; i++)
4896 trail_to_new_successor[i] = trail_me_to_probable_successor[i];
4898 return trail_to_new_successor;
4904 * Check if the peer which sent us verify successor result message is still ours
4905 * successor or not. If not, then compare existing successor and probable successor.
4906 * In case probable successor is the correct successor, remove the existing
4907 * successor. Add probable successor as new successor. Send notify new successor
4908 * message to new successor.
4910 * @param probable_successor
4912 * @param trail_length
4915 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4916 struct GNUNET_PeerIdentity probable_successor,
4917 const struct GNUNET_PeerIdentity *trail,
4918 unsigned int trail_length)
4920 struct FingerInfo *current_successor;
4921 const struct GNUNET_PeerIdentity *closest_peer;
4922 struct GNUNET_HashCode trail_id;
4923 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4924 struct FriendInfo *target_friend;
4925 unsigned int trail_me_to_probable_succ_len;
4926 unsigned int is_predecessor = GNUNET_NO;
4927 uint64_t successor_value;
4929 current_successor = &finger_table[0];
4930 successor_value = compute_finger_identity_value(0);
4932 /* Have we found some other successor, while waiting for verify successor result
4934 * FIXME closest_peer is being overwritten just after the if
4937 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&curr_succ, ¤t_successor->finger_identity))
4939 /* We could have added this new successor, only if it was closer the old one. */
4940 closest_peer = select_closest_peer (&curr_succ,
4941 ¤t_successor->finger_identity,
4942 successor_value, is_predecessor);
4944 /* FIXME: it may fail in case we have done more number of iterations of
4945 find _finger_trail_task. */
4946 /*GNUNET_assert (0 ==
4947 GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4948 ¤t_successor->finger_identity));*/
4953 closest_peer = select_closest_peer (&probable_successor,
4954 ¤t_successor->finger_identity,
4955 successor_value, is_predecessor);
4957 /* If the current_successor in the finger table is closest, then do nothing. */
4958 if (closest_peer == ¤t_successor->finger_identity)
4961 /* Probable successor is the closest peer.*/
4962 if(trail_length > 0)
4964 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4969 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4970 &probable_successor));
4973 trail_me_to_probable_succ_len = 0;
4974 /* TODO: Check if the path to reach to probable successor contains a friend. */
4975 trail_me_to_probable_succ =
4976 check_trail_me_to_probable_succ (probable_successor,
4977 trail, trail_length,
4978 &trail_me_to_probable_succ_len);
4980 /* Remove the existing successor. */
4981 remove_existing_finger (current_successor, 0);
4983 /* TODO URGENT: Check if any peer is present more than once, if yes then shorten
4984 the trail. before sending it across the network. */
4985 /* Generate a new trail id to reach to your new successor. */
4986 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4987 &trail_id, sizeof (trail_id));
4989 if (trail_me_to_probable_succ_len > 0)
4991 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4992 GNUNET_assert (NULL !=
4994 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4995 &trail_me_to_probable_succ[0])));
4999 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5000 GNUNET_assert (NULL !=
5002 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5003 &probable_successor)));
5006 add_new_finger (probable_successor, trail_me_to_probable_succ,
5007 trail_me_to_probable_succ_len, trail_id, 0);
5009 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
5010 trail_me_to_probable_succ,
5011 trail_me_to_probable_succ_len,
5019 * FIXME: Check for duplicate elements everywhere when you are making
5021 * Core handle for p2p verify successor result messages.
5022 * @param cls closure
5023 * @param message message
5024 * @param peer peer identity this notification is about
5025 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5028 handle_dht_p2p_verify_successor_result(void *cls,
5029 const struct GNUNET_PeerIdentity *peer,
5030 const struct GNUNET_MessageHeader *message)
5032 const struct PeerVerifySuccessorResultMessage *vsrm;
5033 enum GDS_ROUTING_trail_direction trail_direction;
5034 struct GNUNET_PeerIdentity querying_peer;
5035 struct GNUNET_HashCode trail_id;
5036 struct GNUNET_PeerIdentity *next_hop;
5037 struct FriendInfo *target_friend;
5038 struct GNUNET_PeerIdentity probable_successor;
5039 struct GNUNET_PeerIdentity current_successor;
5040 const struct GNUNET_PeerIdentity *trail;
5041 unsigned int trail_length;
5044 msize = ntohs (message->size);
5045 /* We send a trail to reach from old successor to new successor, if
5046 * old_successor != new_successor.*/
5047 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5049 GNUNET_break_op (0);
5053 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5054 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5055 sizeof (struct GNUNET_PeerIdentity);
5057 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5058 sizeof (struct GNUNET_PeerIdentity) != 0)
5060 GNUNET_break_op (0);
5064 GNUNET_STATISTICS_update (GDS_stats,
5066 ("# Bytes received from other peers"), msize,
5069 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5070 querying_peer = vsrm->querying_peer;
5071 trail_direction = ntohl (vsrm->trail_direction);
5072 trail_id = vsrm->trail_id;
5073 probable_successor = vsrm->probable_successor;
5074 current_successor = vsrm->current_successor;
5077 /* I am the querying_peer. */
5078 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5080 compare_and_update_successor (current_successor,
5081 probable_successor, trail, trail_length);
5085 /*If you are not the querying peer then pass on the message */
5086 GNUNET_assert (NULL != (next_hop =
5087 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
5088 GNUNET_assert (NULL !=
5090 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5091 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5092 vsrm->current_successor,
5093 probable_successor, trail_id,
5096 trail_direction, target_friend);
5102 * Core handle for p2p notify new successor messages.
5103 * @param cls closure
5104 * @param message message
5105 * @param peer peer identity this notification is about
5106 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5109 handle_dht_p2p_notify_new_successor(void *cls,
5110 const struct GNUNET_PeerIdentity *peer,
5111 const struct GNUNET_MessageHeader *message)
5113 const struct PeerNotifyNewSuccessorMessage *nsm;
5114 struct GNUNET_PeerIdentity *trail;
5115 struct GNUNET_PeerIdentity source;
5116 struct GNUNET_PeerIdentity new_successor;
5117 struct GNUNET_HashCode trail_id;
5118 struct GNUNET_PeerIdentity next_hop;
5119 struct FriendInfo *target_friend;
5122 uint32_t trail_length;
5124 msize = ntohs (message->size);
5126 /* We have the trail to reach from source to new successor. */
5127 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5129 GNUNET_break_op (0);
5133 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5134 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5135 sizeof (struct GNUNET_PeerIdentity);
5136 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5137 sizeof (struct GNUNET_PeerIdentity) != 0)
5139 GNUNET_break_op (0);
5143 GNUNET_STATISTICS_update (GDS_stats,
5145 ("# Bytes received from other peers"), msize,
5148 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5149 source = nsm->source_peer;
5150 new_successor = nsm->new_successor;
5151 trail_id = nsm->trail_id;
5154 //FIXME: add a check to make sure peer is correct.
5156 /* I am the new_successor to source_peer. */
5157 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5159 if(trail_length > 0)
5160 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5163 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5165 compare_and_update_predecessor (source, trail, trail_length);
5169 GNUNET_assert(trail_length > 0);
5170 /* I am part of trail to reach to successor. */
5171 my_index = search_my_index (trail, trail_length);
5174 GNUNET_break_op (0);
5175 return GNUNET_SYSERR;
5178 if ((trail_length-1) == my_index)
5179 next_hop = new_successor;
5181 next_hop = trail[my_index + 1];
5184 /* Add an entry in routing table for trail from source to its new successor. */
5185 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5186 GNUNET_assert (NULL !=
5188 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5189 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5191 trail_id, target_friend);
5198 * Core handler for P2P trail rejection message
5199 * @param cls closure
5200 * @param message message
5201 * @param peer peer identity this notification is about
5202 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5205 handle_dht_p2p_trail_setup_rejection (void *cls,
5206 const struct GNUNET_PeerIdentity *peer,
5207 const struct GNUNET_MessageHeader *message)
5209 const struct PeerTrailRejectionMessage *trail_rejection;
5210 unsigned int trail_length;
5211 const struct GNUNET_PeerIdentity *trail_peer_list;
5212 struct FriendInfo *target_friend;
5213 struct GNUNET_TIME_Relative congestion_timeout;
5214 struct GNUNET_HashCode trail_id;
5215 struct GNUNET_PeerIdentity next_peer;
5216 struct GNUNET_PeerIdentity source;
5217 struct GNUNET_PeerIdentity *next_hop;
5218 uint64_t ultimate_destination_finger_value;
5219 unsigned int is_predecessor;
5222 msize = ntohs (message->size);
5223 /* We are passing the trail setup so far. */
5224 if (msize < sizeof (struct PeerTrailRejectionMessage))
5226 GNUNET_break_op (0);
5230 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5231 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5232 sizeof (struct GNUNET_PeerIdentity);
5233 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5234 sizeof (struct GNUNET_PeerIdentity) != 0)
5236 GNUNET_break_op (0);
5240 GNUNET_STATISTICS_update (GDS_stats,
5242 ("# Bytes received from other peers"), msize,
5245 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5246 is_predecessor = ntohl (trail_rejection->is_predecessor);
5247 congestion_timeout = trail_rejection->congestion_time;
5248 source = trail_rejection->source_peer;
5249 trail_id = trail_rejection->trail_id;
5250 ultimate_destination_finger_value =
5251 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5253 /* First set the congestion time of the friend that sent you this message. */
5254 GNUNET_assert (NULL !=
5256 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5257 target_friend->congestion_timestamp =
5258 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5259 congestion_timeout);
5261 /* I am the source peer which wants to setup the trail. Do nothing.
5262 * send_find_finger_trail_task is scheduled periodically.*/
5263 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5266 /* If I am congested then pass this message to peer before me in trail. */
5267 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5269 struct GNUNET_PeerIdentity *new_trail;
5270 unsigned int new_trail_length;
5272 /* Remove yourself from the trail setup so far. */
5273 if (trail_length == 1)
5276 new_trail_length = 0;
5281 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5282 sizeof (struct GNUNET_PeerIdentity));
5284 /* Remove myself from the trail. */
5285 new_trail_length = trail_length -1;
5286 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5287 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5290 GNUNET_assert (NULL !=
5292 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5293 GDS_NEIGHBOURS_send_trail_rejection (source,
5294 ultimate_destination_finger_value,
5295 my_identity, is_predecessor,
5296 new_trail,new_trail_length,trail_id,
5297 target_friend, CONGESTION_TIMEOUT);
5298 GNUNET_free (new_trail);
5302 struct Closest_Peer successor;
5303 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5305 /* Am I the final destination? */
5306 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5309 if (0 == trail_length)
5312 next_peer = trail_peer_list[trail_length-1];
5314 GNUNET_assert (NULL !=
5316 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5318 GDS_NEIGHBOURS_send_trail_setup_result (source,
5320 target_friend, trail_length,
5323 ultimate_destination_finger_value,
5328 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5330 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5331 peer_list[trail_length] = my_identity;
5333 GNUNET_assert (NULL !=
5335 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5337 GDS_NEIGHBOURS_send_trail_setup (source,
5338 ultimate_destination_finger_value,
5339 successor.best_known_destination,
5340 target_friend, trail_length + 1, peer_list,
5341 is_predecessor, trail_id,
5342 successor.trail_id);
5349 * Core handle for p2p trail tear compression messages.
5350 * @param cls closure
5351 * @param message message
5352 * @param peer peer identity this notification is about
5353 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5356 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5357 const struct GNUNET_MessageHeader *message)
5359 const struct PeerTrailCompressionMessage *trail_compression;
5360 struct GNUNET_PeerIdentity *next_hop;
5361 struct FriendInfo *target_friend;
5362 struct GNUNET_HashCode trail_id;
5365 msize = ntohs (message->size);
5367 if (msize != sizeof (struct PeerTrailCompressionMessage))
5369 GNUNET_break_op (0);
5373 GNUNET_STATISTICS_update (GDS_stats,
5375 ("# Bytes received from other peers"), msize,
5378 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5379 trail_id = trail_compression->trail_id;
5381 /* Am I the new first friend to reach to finger of this trail. */
5382 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5385 GNUNET_assert (NULL !=
5386 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5387 &trail_compression->source_peer)));
5389 /* Update your prev hop to source of this message. */
5390 GNUNET_assert (GNUNET_SYSERR !=
5391 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5392 trail_compression->source_peer)));
5396 /* Pass the message to next hop to finally reach to new_first_friend. */
5397 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5399 if (NULL == next_hop)
5405 GNUNET_assert (NULL !=
5407 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5409 GDS_ROUTING_remove_trail (trail_id);
5411 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5413 trail_compression->new_first_friend,
5420 * Core handler for trail teardown message.
5421 * @param cls closure
5422 * @param message message
5423 * @param peer sender of this messsage.
5424 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5427 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5428 const struct GNUNET_MessageHeader *message)
5430 const struct PeerTrailTearDownMessage *trail_teardown;
5431 enum GDS_ROUTING_trail_direction trail_direction;
5432 struct GNUNET_HashCode trail_id;
5433 struct GNUNET_PeerIdentity *next_hop;
5436 msize = ntohs (message->size);
5438 /* Here we pass only the trail id. */
5439 if (msize != sizeof (struct PeerTrailTearDownMessage))
5441 GNUNET_break_op (0);
5445 GNUNET_STATISTICS_update (GDS_stats,
5447 ("# Bytes received from other peers"), msize,
5450 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5451 trail_direction = ntohl (trail_teardown->trail_direction);
5452 trail_id = trail_teardown->trail_id;
5454 /* Check if peer is the real peer from which we should get this message.*/
5455 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5457 GNUNET_assert (NULL != (prev_hop =
5458 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5459 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5462 return GNUNET_SYSERR;
5466 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5468 if (NULL == next_hop)
5471 return GNUNET_SYSERR;
5474 /* I am the next hop, which means I am the final destination. */
5475 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5477 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5482 /* If not final destination, then send a trail teardown message to next hop.*/
5483 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5484 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5485 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5493 * Core handle for p2p add trail message.
5494 * @param cls closure
5495 * @param message message
5496 * @param peer peer identity this notification is about
5497 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5500 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5501 const struct GNUNET_MessageHeader *message)
5503 const struct PeerAddTrailMessage *add_trail;
5504 const struct GNUNET_PeerIdentity *trail;
5505 struct GNUNET_HashCode trail_id;
5506 struct GNUNET_PeerIdentity destination_peer;
5507 struct GNUNET_PeerIdentity source_peer;
5508 struct GNUNET_PeerIdentity next_hop;
5509 unsigned int trail_length;
5510 unsigned int my_index;
5513 msize = ntohs (message->size);
5514 /* In this message we pass the whole trail from source to destination as we
5515 * are adding that trail.*/
5516 //FIXME: failed when run with 1000 pears. check why.
5517 if (msize < sizeof (struct PeerAddTrailMessage))
5519 GNUNET_break_op (0);
5523 add_trail = (const struct PeerAddTrailMessage *) message;
5524 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5525 sizeof (struct GNUNET_PeerIdentity);
5526 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5527 sizeof (struct GNUNET_PeerIdentity) != 0)
5529 GNUNET_break_op (0);
5533 GNUNET_STATISTICS_update (GDS_stats,
5535 ("# Bytes received from other peers"), msize,
5538 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5539 destination_peer = add_trail->destination_peer;
5540 source_peer = add_trail->source_peer;
5541 trail_id = add_trail->trail_id;
5543 //FIXME: add a check that sender peer is not malicious. Make it a generic
5544 // function so that it can be used in all other functions where we need the
5545 // same functionality.
5547 /* I am not the destination of the trail. */
5548 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5550 struct FriendInfo *target_friend;
5552 /* Get my location in the trail. */
5553 my_index = search_my_index (trail, trail_length);
5556 GNUNET_break_op (0);
5557 return GNUNET_SYSERR;
5560 if ((trail_length - 1) == my_index)
5562 next_hop = destination_peer;
5566 next_hop = trail[my_index + 1];
5569 /* Add in your routing table. */
5570 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5571 GNUNET_assert (NULL !=
5573 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5574 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5575 trail, trail_length, target_friend);
5578 /* I am the destination. Add an entry in routing table. */
5579 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5585 * Free the finger trail in which the first friend to reach to a finger is
5586 * disconnected_friend. Also remove entry from routing table for that particular
5588 * @param disconnected_friend PeerIdentity of friend which got disconnected
5589 * @param remove_finger Finger whose trail we need to check if it has
5590 * disconnected_friend as the first hop.
5591 * @return Total number of trails in which disconnected_friend was the first
5595 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5596 struct FingerInfo *remove_finger)
5598 unsigned int matching_trails_count;
5601 /* Number of trails with disconnected_friend as the first hop in the trail
5602 * to reach from me to remove_finger, NOT including endpoints. */
5603 matching_trails_count = 0;
5605 /* Iterate over all the trails of finger. */
5606 for (i = 0; i < remove_finger->trails_count; i++)
5608 struct Trail *trail;
5609 trail = &remove_finger->trail_list[i];
5611 /* This assertion is ensure that there are no gaps in the trail list.
5612 REMOVE IT AFTERWARDS. */
5613 GNUNET_assert (GNUNET_YES == trail->is_present);
5615 /* First friend to reach to finger is disconnected_peer. */
5616 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5617 disconnected_friend))
5619 struct GNUNET_PeerIdentity *next_hop;
5620 struct FriendInfo *remove_friend;
5622 GNUNET_assert (NULL !=
5624 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5625 disconnected_friend)));
5626 /* FIXME: removing no but check it. */
5627 //remove_friend->trails_count--;
5628 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5629 GDS_ROUTING_SRC_TO_DEST);
5631 /* Here it may happen that as all the peers got disconnected, the entry in
5632 routing table for that particular trail has been removed, because the
5633 previously disconnected peer was either a next hop or prev hop of that
5635 if (NULL == next_hop)
5638 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5640 matching_trails_count++;
5641 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5644 trail->is_present = GNUNET_NO;
5647 return matching_trails_count;
5652 * Iterate over finger_table entries.
5653 * 0. Ignore finger which is my_identity or if no valid entry present at
5654 * that finger index.
5655 * 1. If disconnected_friend is a finger, then remove the routing entry from
5656 your own table. Free the trail.
5657 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5658 * 2.1 Remove all the trails and entry from routing table in which disconnected
5659 * friend is the first friend in the trail. If disconnected_friend is the
5660 * first friend in all the trails to reach finger, then remove the finger.
5661 * @param disconnected_friend Peer identity of friend which got disconnected.
5664 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5666 struct FingerInfo *remove_finger;
5667 struct FriendInfo *remove_friend;
5668 int removed_trails_count;
5671 /* Iterate over finger table entries. */
5672 for (i = 0; i < MAX_FINGERS; i++)
5674 remove_finger = &finger_table[i];
5676 /* No finger stored at this trail index. */
5677 if (GNUNET_NO == remove_finger->is_present)
5680 /* I am my own finger, then ignore this finger. */
5681 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5685 /* Is disconnected_peer a finger? */
5686 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5687 &remove_finger->finger_identity))
5689 struct GNUNET_PeerIdentity *next_hop;
5690 struct GNUNET_HashCode trail_id;
5693 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5694 trail_id = remove_finger->trail_list[0].trail_id;
5698 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5701 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5702 &remove_finger->finger_identity)));
5703 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5704 GNUNET_assert (NULL !=
5706 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5707 disconnected_peer)));
5710 remove_finger->trail_list[0].is_present = GNUNET_NO;
5711 //GNUNET_assert (0 != remove_friend->trails_count);
5712 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5713 remove_finger->is_present = GNUNET_NO;
5714 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5718 /* If finger is a friend but not disconnected_friend, then continue. */
5719 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5720 &remove_finger->finger_identity))
5723 /* Iterate over the list of trails to reach remove_finger. Check if
5724 * disconnected_friend is the first friend in any of the trail. */
5725 removed_trails_count = remove_matching_trails (disconnected_peer,
5727 remove_finger->trails_count =
5728 remove_finger->trails_count - removed_trails_count;
5729 /* All the finger trails had disconnected_friend as the first friend,
5730 * so free the finger. */
5731 if (remove_finger->trails_count == 0)
5733 remove_finger->is_present = GNUNET_NO;
5734 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5741 * Method called whenever a peer disconnects.
5743 * @param cls closure
5744 * @param peer peer identity this notification is about
5747 handle_core_disconnect (void *cls,
5748 const struct GNUNET_PeerIdentity *peer)
5750 struct FriendInfo *remove_friend;
5752 /* If disconnected to own identity, then return. */
5753 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5756 GNUNET_assert (NULL != (remove_friend =
5757 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5759 /* Remove fingers with peer as first friend or if peer is a finger. */
5760 remove_matching_fingers (peer);
5762 /* Remove any trail from routing table of which peer is a part of. This function
5763 * internally sends a trail teardown message in the direction of which
5764 * disconnected peer is not part of. */
5765 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5767 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5769 /* Remove peer from friend_peermap. */
5770 GNUNET_assert (GNUNET_YES ==
5771 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5775 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5778 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5780 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5781 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5790 * Method called whenever a peer connects.
5792 * @param cls closure
5793 * @param peer_identity peer identity this notification is about
5796 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5798 struct FriendInfo *friend;
5800 /* Check for connect to self message */
5801 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5804 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5806 /* If peer already exists in our friend_peermap, then exit. */
5807 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5814 friend = GNUNET_new (struct FriendInfo);
5815 friend->id = *peer_identity;
5817 GNUNET_assert (GNUNET_OK ==
5818 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5819 peer_identity, friend,
5820 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5823 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5824 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5826 next_send_time.rel_value_us =
5827 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5828 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5829 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5830 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5836 * To be called on core init/fail.
5838 * @param cls service closure
5839 * @param identity the public identity of this peer
5842 core_init (void *cls,
5843 const struct GNUNET_PeerIdentity *identity)
5845 my_identity = *identity;
5848 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5849 my_id64 = GNUNET_ntohll (my_id64);
5850 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5851 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5857 * Initialize finger table entries.
5860 finger_table_init ()
5862 memset (&finger_table, 0, sizeof (finger_table));
5867 * Initialize neighbours subsystem.
5868 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5871 GDS_NEIGHBOURS_init (void)
5873 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5874 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5875 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5876 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5877 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5878 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5879 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5880 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5881 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5882 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5883 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5884 sizeof (struct PeerTrailCompressionMessage)},
5885 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5886 sizeof (struct PeerTrailTearDownMessage)},
5887 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5892 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5893 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5894 GNUNET_NO, core_handlers);
5895 if (NULL == core_api)
5896 return GNUNET_SYSERR;
5898 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5899 finger_table_init ();
5906 * Shutdown neighbours subsystem.
5909 GDS_NEIGHBOURS_done (void)
5911 if (NULL == core_api)
5914 GNUNET_CORE_disconnect (core_api);
5917 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5918 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5919 friend_peermap = NULL;
5921 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5924 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5925 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5928 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5930 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5931 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5939 * @return my identity
5941 struct GNUNET_PeerIdentity
5942 GDS_NEIGHBOURS_get_my_id (void)
5947 /* end of gnunet-service-xdht_neighbours.c */