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
58 * We should have a message type like notify successor result. only when
59 * this message is being recvied by the new successor. we should schedule
60 * another round of verify successor.
63 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
66 * Maximum possible fingers (including predecessor) of a peer
68 #define MAX_FINGERS 65
71 * Maximum allowed number of pending messages per friend peer.
73 #define MAXIMUM_PENDING_PER_FRIEND 64
76 * How long to wait before sending another find finger trail request
78 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
81 * How long to wait before sending another verify successor message.
83 #define DHT_SEND_VERIFY_SUCCESSOR_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 1)
86 * How long at most to wait for transmission of a request to a friend ?
88 #define PENDING_MESSAGE_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
91 * Duration for which I may remain congested.
92 * Note: Its a static value. In future, a peer may do some analysis and calculate
93 * congestion_timeout based on 'some' parameters.
95 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
98 * Maximum number of trails allowed to go through a friend.
100 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
103 * Maximum number of trails stored per finger.
105 #define MAXIMUM_TRAILS_PER_FINGER 1
108 * Finger map index for predecessor entry in finger table.
110 #define PREDECESSOR_FINGER_ID 64
113 * Wrap around in peer identity circle.
115 #define PEER_IDENTITES_WRAP_AROUND pow(2, 64) - 1
118 * FIXME: Its use only at 3 places check if you can remove it.
119 * To check if a finger is predecessor or not.
121 enum GDS_NEIGHBOURS_finger_type
123 GDS_FINGER_TYPE_PREDECESSOR = 1,
124 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
127 GNUNET_NETWORK_STRUCT_BEGIN
132 struct PeerPutMessage
135 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
137 struct GNUNET_MessageHeader header;
142 uint32_t options GNUNET_PACKED;
147 uint32_t block_type GNUNET_PACKED;
152 uint32_t hop_count GNUNET_PACKED;
155 * Replication level for this message
156 * In the current implementation, this value is not used.
158 uint32_t desired_replication_level GNUNET_PACKED;
161 * Length of the PUT path that follows (if tracked).
163 uint32_t put_path_length GNUNET_PACKED;
166 * Best known destination (could be my friend or finger) which should
167 * get this message next.
169 struct GNUNET_PeerIdentity best_known_destination;
172 * In case best_known_destination is a finger, then trail to reach
173 * to that finger. Else its default value is 0.
175 struct GNUNET_HashCode intermediate_trail_id;
178 * When does the content expire?
180 struct GNUNET_TIME_AbsoluteNBO expiration_time;
183 * The key to store the value under.
185 struct GNUNET_HashCode key GNUNET_PACKED;
187 /* put path (if tracked) */
196 struct PeerGetMessage
199 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
201 struct GNUNET_MessageHeader header;
206 uint32_t options GNUNET_PACKED;
209 * Desired content type.
211 uint32_t block_type GNUNET_PACKED;
216 uint32_t hop_count GNUNET_PACKED;
219 * Desired replication level for this request.
220 * In the current implementation, this value is not used.
222 uint32_t desired_replication_level GNUNET_PACKED;
225 * Total number of peers in get path.
227 unsigned int get_path_length;
230 * Best known destination (could be my friend or finger) which should
231 * get this message next.
233 struct GNUNET_PeerIdentity best_known_destination;
236 * In case best_known_destination is a finger, then trail to reach
237 * to that finger. Else its default value is 0.
239 struct GNUNET_HashCode intermediate_trail_id;
242 * The key we are looking for.
244 struct GNUNET_HashCode key;
247 /* struct GNUNET_PeerIdentity[]*/
253 struct PeerGetResultMessage
256 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
258 struct GNUNET_MessageHeader header;
261 * The type for the data.
263 uint32_t type GNUNET_PACKED;
266 * Number of peers recorded in the outgoing path from source to the
267 * stored location of this message.
269 uint32_t put_path_length GNUNET_PACKED;
272 * Length of the GET path that follows (if tracked).
274 uint32_t get_path_length GNUNET_PACKED;
277 * Peer which queried for get and should get the result.
279 struct GNUNET_PeerIdentity querying_peer;
282 * When does the content expire?
284 struct GNUNET_TIME_Absolute expiration_time;
287 * The key of the corresponding GET request.
289 struct GNUNET_HashCode key;
291 /* put path (if tracked) */
293 /* get path (if tracked) */
300 * P2P Trail setup message
302 struct PeerTrailSetupMessage
305 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
307 struct GNUNET_MessageHeader header;
310 * Is source_peer trying to setup the trail to a predecessor or any finger.
312 uint32_t is_predecessor;
315 * Peer closest to this value will be our finger.
317 uint64_t final_destination_finger_value;
320 * Source peer which wants to setup the trail to one of its finger.
322 struct GNUNET_PeerIdentity source_peer;
325 * Best known destination (could be my friend or finger) which should
326 * get this message next.
328 * FIXME: this could be removed if we include trail_source / trail_dest
329 * in the routing table. This way we save 32 bytes of bandwidth by using
330 * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID))
332 struct GNUNET_PeerIdentity best_known_destination;
335 * In case best_known_destination is a finger, then trail id of trail to
336 * reach to this finger.
338 struct GNUNET_HashCode intermediate_trail_id;
341 * Trail id for trail which we are trying to setup.
343 struct GNUNET_HashCode trail_id;
345 /* List of peers which are part of trail setup so far.
346 * Trail does NOT include source_peer and peer which will be closest to
347 * ultimate_destination_finger_value.
348 * struct GNUNET_PeerIdentity trail[]
353 * P2P Trail Setup Result message
355 struct PeerTrailSetupResultMessage
359 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
361 struct GNUNET_MessageHeader header;
364 * Finger to which we have found the path.
366 struct GNUNET_PeerIdentity finger_identity;
369 * Peer which started trail_setup to find trail to finger_identity
371 struct GNUNET_PeerIdentity querying_peer;
374 * Is the trail setup to querying_peer's predecessor or finger?
376 uint32_t is_predecessor;
379 * Value to which finger_identity is the closest peer.
381 uint64_t ulitmate_destination_finger_value;
384 * Identifier of the trail from querying peer to finger_identity, NOT
385 * including both endpoints.
387 struct GNUNET_HashCode trail_id;
389 /* List of peers which are part of the trail from querying peer to
390 * finger_identity, NOT including both endpoints.
391 * struct GNUNET_PeerIdentity trail[]
396 * P2P Verify Successor Message.
398 struct PeerVerifySuccessorMessage
401 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
403 struct GNUNET_MessageHeader header;
406 * Peer which wants to verify its successor.
408 struct GNUNET_PeerIdentity source_peer;
411 * Source Peer's current successor.
413 struct GNUNET_PeerIdentity successor;
416 * Identifier of trail to reach from source_peer to successor.
418 struct GNUNET_HashCode trail_id;
420 /* List of the peers which are part of trail to reach from source_peer
421 * to successor, NOT including them
422 * struct GNUNET_PeerIdentity trail[]
427 * P2P Verify Successor Result Message
429 struct PeerVerifySuccessorResultMessage
432 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
434 struct GNUNET_MessageHeader header;
437 * Peer which sent the request to verify its successor.
439 struct GNUNET_PeerIdentity querying_peer;
442 * Successor to which PeerVerifySuccessorMessage was sent.
444 struct GNUNET_PeerIdentity current_successor;
447 * Current Predecessor of source_successor. It can be same as querying peer
448 * or different. In case it is different then it can be querying_peer's
449 * probable successor.
451 struct GNUNET_PeerIdentity probable_successor;
454 * Trail identifier of trail from querying_peer to current_successor.
456 struct GNUNET_HashCode trail_id;
459 * Direction in which we are looking at the trail.
461 uint32_t trail_direction;
463 /* In case probable_successor != querying_peer, then trail to reach from
464 * querying_peer to probable_successor, NOT including end points.
465 * struct GNUNET_PeerIdentity trail[]
470 * P2P Notify New Successor Message.
472 struct PeerNotifyNewSuccessorMessage
475 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
477 struct GNUNET_MessageHeader header;
480 * Peer which wants to notify its new successor.
482 struct GNUNET_PeerIdentity source_peer;
485 * New successor of source_peer.
487 struct GNUNET_PeerIdentity new_successor;
490 * Unique identifier of the trail from source_peer to new_successor,
491 * NOT including the endpoints.
493 struct GNUNET_HashCode trail_id;
495 /* List of peers in trail from source_peer to new_successor,
496 * NOT including the endpoints.
497 * struct GNUNET_PeerIdentity trail[]
503 * P2P Trail Tear Down message.
505 struct PeerTrailTearDownMessage
508 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
510 struct GNUNET_MessageHeader header;
513 * Unique identifier of the trail.
515 struct GNUNET_HashCode trail_id;
518 * Direction of trail.
520 uint32_t trail_direction;
525 * P2P Trail Rejection Message.
527 struct PeerTrailRejectionMessage
530 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
532 struct GNUNET_MessageHeader header;
535 * Peer which wants to set up the trail.
537 struct GNUNET_PeerIdentity source_peer;
540 * Peer which sent trail rejection message as it it congested.
542 struct GNUNET_PeerIdentity congested_peer;
545 * Peer identity closest to this value will be finger of
548 uint64_t ultimate_destination_finger_value;
551 * Is source_peer trying to setup the trail to its predecessor or finger.
553 uint32_t is_predecessor;
556 * Identifier for the trail that source peer is trying to setup.
558 struct GNUNET_HashCode trail_id;
561 * Relative time for which congested_peer will remain congested.
563 struct GNUNET_TIME_Relative congestion_time;
565 /* Trail_list from source_peer to peer which sent the message for trail setup
566 * to congested peer. This trail does NOT include source_peer.
567 struct GNUNET_PeerIdnetity trail[]*/
571 * P2P Add Trail Message.
573 struct PeerAddTrailMessage
576 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
578 struct GNUNET_MessageHeader header;
581 * Source of the routing trail.
583 struct GNUNET_PeerIdentity source_peer;
586 * Destination of the routing trail.
588 struct GNUNET_PeerIdentity destination_peer;
591 * Unique identifier of the trail from source_peer to destination_peer,
592 * NOT including the endpoints.
594 struct GNUNET_HashCode trail_id;
596 /* Trail from source peer to destination peer, NOT including them.
597 * struct GNUNET_PeerIdentity trail[]
601 GNUNET_NETWORK_STRUCT_END
604 * Linked list of messages to send to a particular other peer.
606 struct P2PPendingMessage
609 * Pointer to next item in the list
611 struct P2PPendingMessage *next;
614 * Pointer to previous item in the list
616 struct P2PPendingMessage *prev;
619 * Message importance level. FIXME: used? useful?
621 unsigned int importance;
624 * When does this message time out?
626 struct GNUNET_TIME_Absolute timeout;
629 * Actual message to be sent, allocated at the end of the struct:
630 * // msg = (cast) &pm[1];
631 * // memcpy (&pm[1], data, len);
633 const struct GNUNET_MessageHeader *msg;
638 * Entry in friend_peermap.
645 struct GNUNET_PeerIdentity id;
648 * Number of trails for which this friend is the first hop or if the friend
651 unsigned int trails_count;
654 * Count of outstanding messages for this friend.
656 unsigned int pending_count;
659 * In case not 0, then amount of time for which this friend is congested.
661 struct GNUNET_TIME_Absolute congestion_timestamp;
664 // TODO : Change name of head and tail to pending_messages_list_head and so.
666 * Head of pending messages to be sent to this friend.
668 struct P2PPendingMessage *head;
671 * Tail of pending messages to be sent to this friend.
673 struct P2PPendingMessage *tail;
676 * Core handle for sending messages to this friend.
678 struct GNUNET_CORE_TransmitHandle *th;
683 * An individual element of the trail to reach to a finger.
688 * Pointer to next item in the list
690 struct Trail_Element *next;
693 * Pointer to prev item in the list
695 struct Trail_Element *prev;
698 * An element in this trail.
700 struct GNUNET_PeerIdentity peer;
704 * Information about an individual trail.
711 struct Trail_Element *trail_head;
716 struct Trail_Element *trail_tail;
719 * Unique identifier of this trail.
721 struct GNUNET_HashCode trail_id;
724 * Length of trail pointed
726 unsigned int trail_length;
729 * Is there a valid trail entry.
731 unsigned int is_present;
735 * An entry in finger_table
742 struct GNUNET_PeerIdentity finger_identity;
745 * Is any finger stored at this finger index.
747 unsigned int is_present;
750 * Index in finger peer map
752 uint32_t finger_table_index;
755 * Number of trails setup so far for this finger.
756 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
758 uint32_t trails_count;
761 * Array of trails to reach to this finger.
763 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
768 * Stores information about the peer which is closest to destination_finger_value.
769 * 'closest' can be either successor or predecessor depending on is_predecessor
775 * Destination finger value.
777 uint64_t destination_finger_value;
780 * Is finger_value a predecessor or any other finger.
782 unsigned int is_predecessor;
785 * Trail id to reach to peer.
786 * In case peer is my identity or friend, it is set to 0.
788 struct GNUNET_HashCode trail_id;
791 * Next destination. In case of friend and my_identity , it is same as next_hop
792 * In case of finger it is finger identity.
794 struct GNUNET_PeerIdentity best_known_destination;
797 * In case best_known_destination is a finger, then first friend in the trail
798 * to reach to it. In other case, same as best_known_destination.
800 struct GNUNET_PeerIdentity next_hop;
803 * In case finger is the next hop, it contains a valid finger table index
804 * at which the finger is stored. Else, It contains 65, which is out of range
805 * of finger table index.
807 unsigned int finger_table_index;
812 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
813 * get our first friend.
815 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
818 * Task that sends verify successor message. This task is started when we get
819 * our successor for the first time.
821 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_task;
824 * Identity of this peer.
826 static struct GNUNET_PeerIdentity my_identity;
829 * Peer map of all the friends of a peer
831 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
834 * Array of all the fingers.
836 static struct FingerInfo finger_table [MAX_FINGERS];
841 static struct GNUNET_CORE_Handle *core_api;
844 * Handle for the statistics service.
846 //extern struct GNUNET_STATISTICS_Handle *GDS_stats;
849 * The current finger index that we have want to find trail to. We start the
850 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
851 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
852 * we reset this index to 0.
854 static unsigned int current_search_finger_index;
857 * Time duration to schedule find finger trail task.
859 static struct GNUNET_TIME_Relative find_finger_trail_task_next_send_time;
862 * Time duration to schedule verify successor task.
864 static struct GNUNET_TIME_Relative verify_successor_next_send_time;
866 /* Below variables are used only for testing, and statistics collection. */
868 * Should we store our topology predecessor and successor IDs into statistics?
870 unsigned int track_topology;
873 * Should I be a malicious peer and drop the PUT/GET packets?
874 * if 0 then NOT malicious.
876 unsigned int act_malicious;
879 * Count of fingers found. Ideally we should have O(logn) fingers for a
882 static unsigned int total_fingers_found;
886 * Called when core is ready to send a message we asked for
887 * out to the destination.
889 * @param cls the 'struct FriendInfo' of the target friend
890 * @param size number of bytes available in buf
891 * @param buf where the callee should write the message
892 * @return number of bytes written to buf
895 core_transmit_notify (void *cls, size_t size, void *buf)
897 struct FriendInfo *peer = cls;
899 struct P2PPendingMessage *pending;
904 while ((NULL != (pending = peer->head)) &&
905 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
907 peer->pending_count--;
908 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
909 GNUNET_free (pending);
913 /* no messages pending */
919 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
920 GNUNET_CORE_PRIO_BEST_EFFORT,
921 GNUNET_TIME_absolute_get_remaining
922 (pending->timeout), &peer->id,
923 ntohs (pending->msg->size),
924 &core_transmit_notify, peer);
925 GNUNET_break (NULL != peer->th);
929 while ((NULL != (pending = peer->head)) &&
930 (size - off >= (msize = ntohs (pending->msg->size))))
932 GNUNET_STATISTICS_update (GDS_stats,
934 ("# Bytes transmitted to other peers"), msize,
936 memcpy (&cbuf[off], pending->msg, msize);
938 peer->pending_count--;
939 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
940 GNUNET_free (pending);
942 if (peer->head != NULL)
945 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
946 GNUNET_CORE_PRIO_BEST_EFFORT,
947 GNUNET_TIME_absolute_get_remaining
948 (pending->timeout), &peer->id, msize,
949 &core_transmit_notify, peer);
950 GNUNET_break (NULL != peer->th);
957 * Transmit all messages in the friend's message queue.
959 * @param peer message queue to process
962 process_friend_queue (struct FriendInfo *peer)
964 struct P2PPendingMessage *pending;
966 if (NULL == (pending = peer->head))
970 if (NULL != peer->th)
976 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
978 GNUNET_TIME_absolute_get_remaining
979 (pending->timeout), &peer->id,
980 ntohs (pending->msg->size),
981 &core_transmit_notify, peer);
982 GNUNET_break (NULL != peer->th);
988 * Set the ENABLE_MALICIOUS value to malicious.
992 GDS_NEIGHBOURS_act_malicious (unsigned int malicious)
994 act_malicious = malicious;
999 * Construct a trail setup message and forward it to target_friend
1000 * @param source_peer Peer which wants to setup the trail
1001 * @param ultimate_destination_finger_value Peer identity closest to this value
1002 * will be finger to @a source_peer
1003 * @param best_known_destination Best known destination (could be finger or friend)
1004 * which should get this message. In case it is
1005 * friend, then it is same as target_friend
1006 * @param target_friend Friend to which message is forwarded now.
1007 * @param trail_length Total number of peers in trail setup so far.
1008 * @param trail_peer_list Trail setup so far
1009 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1010 * @param trail_id Unique identifier for the trail we are trying to setup.
1011 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1012 * best_known_destination when its a finger. If not
1013 * used then set to 0.
1016 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1017 uint64_t ultimate_destination_finger_value,
1018 struct GNUNET_PeerIdentity best_known_destination,
1019 struct FriendInfo *target_friend,
1020 unsigned int trail_length,
1021 const struct GNUNET_PeerIdentity *trail_peer_list,
1022 unsigned int is_predecessor,
1023 struct GNUNET_HashCode trail_id,
1024 struct GNUNET_HashCode intermediate_trail_id)
1026 struct P2PPendingMessage *pending;
1027 struct PeerTrailSetupMessage *tsm;
1028 struct GNUNET_PeerIdentity *peer_list;
1031 msize = sizeof (struct PeerTrailSetupMessage) +
1032 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1034 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1040 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1042 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1045 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1046 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1047 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1048 pending->msg = &(tsm->header);
1049 tsm->header.size = htons (msize);
1050 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1051 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1052 tsm->source_peer = source_peer;
1053 tsm->best_known_destination = best_known_destination;
1054 tsm->is_predecessor = htonl (is_predecessor);
1055 tsm->trail_id = trail_id;
1056 tsm->intermediate_trail_id = intermediate_trail_id;
1058 if (trail_length > 0)
1060 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1061 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1064 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1065 target_friend->pending_count++;
1066 process_friend_queue (target_friend);
1071 * Construct a trail setup result message and forward it to target friend.
1072 * @param querying_peer Peer which sent the trail setup request and should get
1074 * @param Finger Peer to which the trail has been setup to.
1075 * @param target_friend Friend to which this message should be forwarded.
1076 * @param trail_length Numbers of peers in the trail.
1077 * @param trail_peer_list Peers which are part of the trail from
1078 * querying_peer to Finger, NOT including them.
1079 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1080 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1082 * @param trail_id Unique identifier of the trail.
1085 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1086 struct GNUNET_PeerIdentity finger,
1087 struct FriendInfo *target_friend,
1088 unsigned int trail_length,
1089 const struct GNUNET_PeerIdentity *trail_peer_list,
1090 unsigned int is_predecessor,
1091 uint64_t ultimate_destination_finger_value,
1092 struct GNUNET_HashCode trail_id)
1094 struct P2PPendingMessage *pending;
1095 struct PeerTrailSetupResultMessage *tsrm;
1096 struct GNUNET_PeerIdentity *peer_list;
1099 msize = sizeof (struct PeerTrailSetupResultMessage) +
1100 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1102 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1108 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1110 GNUNET_STATISTICS_update (GDS_stats,
1111 gettext_noop ("# P2P messages dropped due to full queue"),
1115 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1116 pending->importance = 0;
1117 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1118 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1119 pending->msg = &tsrm->header;
1120 tsrm->header.size = htons (msize);
1121 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1122 tsrm->querying_peer = querying_peer;
1123 tsrm->finger_identity = finger;
1124 tsrm->is_predecessor = htonl (is_predecessor);
1125 tsrm->trail_id = trail_id;
1126 tsrm->ulitmate_destination_finger_value =
1127 GNUNET_htonll (ultimate_destination_finger_value);
1128 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1129 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1131 /* Send the message to chosen friend. */
1132 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1133 target_friend->pending_count++;
1134 process_friend_queue (target_friend);
1139 * Send trail rejection message to target friend
1140 * @param source_peer Peer which is trying to setup the trail.
1141 * @param ultimate_destination_finger_value Peer closest to this value will be
1142 * @a source_peer's finger
1143 * @param congested_peer Peer which sent this message as it is congested.
1144 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1145 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1146 * by congested_peer. This does NOT include @a source_peer
1147 * and congested_peer.
1148 * @param trail_length Total number of peers in trail_peer_list, NOT including
1149 * @a source_peer and @a congested_peer
1150 * @param trail_id Unique identifier of this trail.
1151 * @param congestion_timeout Duration given by congested peer as an estimate of
1152 * how long it may remain congested.
1155 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1156 uint64_t ultimate_destination_finger_value,
1157 struct GNUNET_PeerIdentity congested_peer,
1158 unsigned int is_predecessor,
1159 const struct GNUNET_PeerIdentity *trail_peer_list,
1160 unsigned int trail_length,
1161 struct GNUNET_HashCode trail_id,
1162 struct FriendInfo *target_friend,
1163 const struct GNUNET_TIME_Relative congestion_timeout)
1165 struct PeerTrailRejectionMessage *trm;
1166 struct P2PPendingMessage *pending;
1167 struct GNUNET_PeerIdentity *peer_list;
1170 msize = sizeof (struct PeerTrailRejectionMessage) +
1171 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1173 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1179 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1181 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1185 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1186 pending->importance = 0;
1187 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1188 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1189 pending->msg = &trm->header;
1190 trm->header.size = htons (msize);
1191 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1192 trm->source_peer = source_peer;
1193 trm->congested_peer = congested_peer;
1194 trm->congestion_time = congestion_timeout;
1195 trm->is_predecessor = htonl (is_predecessor);
1196 trm->trail_id = trail_id;
1197 trm->ultimate_destination_finger_value =
1198 GNUNET_htonll (ultimate_destination_finger_value);
1200 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1201 if (trail_length > 0)
1203 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1206 /* Send the message to chosen friend. */
1207 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1208 target_friend->pending_count++;
1209 process_friend_queue (target_friend);
1214 * Construct a verify successor message and forward it to target_friend.
1215 * @param source_peer Peer which wants to verify its successor.
1216 * @param successor Peer which is @a source_peer's current successor.
1217 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1218 * NOT including them.
1219 * @param trail List of peers which are part of trail to reach from @a source_peer
1220 * to @a successor, NOT including them.
1221 * @param trail_length Total number of peers in @a trail.
1222 * @param target_friend Next friend to get this message.
1225 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1226 struct GNUNET_PeerIdentity successor,
1227 struct GNUNET_HashCode trail_id,
1228 struct GNUNET_PeerIdentity *trail,
1229 unsigned int trail_length,
1230 struct FriendInfo *target_friend)
1232 struct PeerVerifySuccessorMessage *vsm;
1233 struct P2PPendingMessage *pending;
1234 struct GNUNET_PeerIdentity *peer_list;
1237 msize = sizeof (struct PeerVerifySuccessorMessage) +
1238 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1240 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1246 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1248 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1252 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1253 pending->importance = 0; /* FIXME */
1254 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1255 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1256 pending->msg = &vsm->header;
1257 vsm->header.size = htons (msize);
1258 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1259 vsm->source_peer = source_peer;
1260 vsm->successor = successor;
1261 vsm->trail_id = trail_id;
1262 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1263 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1265 /* Send the message to chosen friend. */
1266 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1267 target_friend->pending_count++;
1268 process_friend_queue (target_friend);
1273 * FIXME: In every function we pass target friend except for this one.
1274 * so, either change everything or this one. also, should se just store
1275 * the pointer to friend in routing table rather than gnunet_peeridentity.
1276 * if yes then we should keep friend info in.h andmake lot of changes.
1277 * Construct a trail teardown message and forward it to target friend.
1278 * @param trail_id Unique identifier of the trail.
1279 * @param trail_direction Direction of trail.
1280 * @param target_friend Friend to get this message.
1283 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1284 unsigned int trail_direction,
1285 struct GNUNET_PeerIdentity peer)
1287 struct PeerTrailTearDownMessage *ttdm;
1288 struct P2PPendingMessage *pending;
1289 struct FriendInfo *target_friend;
1292 msize = sizeof (struct PeerTrailTearDownMessage);
1294 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1300 /*FIXME:In what case friend can be null. ?*/
1301 if (NULL == (target_friend =
1302 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1305 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1307 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1311 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1312 pending->importance = 0; /* FIXME */
1313 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1314 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1315 pending->msg = &ttdm->header;
1316 ttdm->header.size = htons (msize);
1317 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1318 ttdm->trail_id = trail_id;
1319 ttdm->trail_direction = htonl (trail_direction);
1321 /* Send the message to chosen friend. */
1322 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1323 target_friend->pending_count++;
1324 process_friend_queue (target_friend);
1329 * Construct a verify successor result message and send it to target_friend
1330 * @param querying_peer Peer which sent the verify successor message.
1331 * @param source_successor Current_successor of @a querying_peer.
1332 * @param current_predecessor Current predecessor of @a successor. Could be same
1333 * or different from @a querying_peer.
1334 * @param trail_id Unique identifier of the trail from @a querying_peer to
1335 * @a successor, NOT including them.
1336 * @param trail List of peers which are part of trail from @a querying_peer to
1337 * @a successor, NOT including them.
1338 * @param trail_length Total number of peers in @a trail
1339 * @param trail_direction Direction in which we are sending the message. In this
1340 * case we are sending result from @a successor to @a querying_peer.
1341 * @param target_friend Next friend to get this message.
1344 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1345 struct GNUNET_PeerIdentity current_successor,
1346 struct GNUNET_PeerIdentity probable_successor,
1347 struct GNUNET_HashCode trail_id,
1348 const struct GNUNET_PeerIdentity *trail,
1349 unsigned int trail_length,
1350 enum GDS_ROUTING_trail_direction trail_direction,
1351 struct FriendInfo *target_friend)
1353 struct PeerVerifySuccessorResultMessage *vsmr;
1354 struct P2PPendingMessage *pending;
1355 struct GNUNET_PeerIdentity *peer_list;
1358 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1359 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1361 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1367 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1369 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1373 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1374 pending->importance = 0; /* FIXME */
1375 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1376 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1377 pending->msg = &vsmr->header;
1378 vsmr->header.size = htons (msize);
1379 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1380 vsmr->querying_peer = querying_peer;
1381 vsmr->current_successor = current_successor;
1382 vsmr->probable_successor = probable_successor;
1383 vsmr->trail_direction = htonl (trail_direction);
1384 vsmr->trail_id = trail_id;
1385 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1386 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1388 /* Send the message to chosen friend. */
1389 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1390 target_friend->pending_count++;
1391 process_friend_queue (target_friend);
1396 * Construct a notify new successor message and send it to target_friend
1397 * @param source_peer Peer which wants to notify to its new successor that it
1398 * could be its predecessor.
1399 * @param successor New successor of @a source_peer
1400 * @param successor_trail List of peers in Trail to reach from
1401 * @a source_peer to @a new_successor, NOT including
1403 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1404 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1405 * @param target_friend Next friend to get this message.
1408 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1409 struct GNUNET_PeerIdentity successor,
1410 const struct GNUNET_PeerIdentity *successor_trail,
1411 unsigned int successor_trail_length,
1412 struct GNUNET_HashCode succesor_trail_id,
1413 struct FriendInfo *target_friend)
1415 struct PeerNotifyNewSuccessorMessage *nsm;
1416 struct P2PPendingMessage *pending;
1417 struct GNUNET_PeerIdentity *peer_list;
1420 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1421 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1423 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1429 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1431 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1435 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1436 pending->importance = 0; /* FIXME */
1437 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1438 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1439 pending->msg = &nsm->header;
1440 nsm->header.size = htons (msize);
1441 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1442 nsm->new_successor = successor;
1443 nsm->source_peer = source_peer;
1444 nsm->trail_id = succesor_trail_id;
1445 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1446 memcpy (peer_list, successor_trail,
1447 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1449 /* Send the message to chosen friend. */
1450 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1451 target_friend->pending_count++;
1452 process_friend_queue (target_friend);
1457 * Construct an add_trail message and send it to target_friend
1458 * @param source_peer Source of the trail.
1459 * @param destination_peer Destination of the trail.
1460 * @param trail_id Unique identifier of the trail from
1461 * @a source_peer to @a destination_peer, NOT including the endpoints.
1462 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1463 * NOT including the endpoints.
1464 * @param trail_length Total number of peers in @a trail.
1465 * @param target_friend Next friend to get this message.
1468 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1469 struct GNUNET_PeerIdentity destination_peer,
1470 struct GNUNET_HashCode trail_id,
1471 const struct GNUNET_PeerIdentity *trail,
1472 unsigned int trail_length,
1473 struct FriendInfo *target_friend)
1475 struct PeerAddTrailMessage *adm;
1476 struct GNUNET_PeerIdentity *peer_list;
1477 struct P2PPendingMessage *pending;
1480 msize = sizeof (struct PeerAddTrailMessage) +
1481 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1483 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1489 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1491 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1495 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1496 pending->importance = 0; /* FIXME */
1497 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1498 adm = (struct PeerAddTrailMessage *) &pending[1];
1499 pending->msg = &adm->header;
1500 adm->header.size = htons (msize);
1501 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1502 adm->source_peer = source_peer;
1503 adm->destination_peer = destination_peer;
1504 adm->trail_id = trail_id;
1505 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1506 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1508 /* Send the message to chosen friend. */
1509 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1510 target_friend->pending_count++;
1511 process_friend_queue (target_friend);
1517 * Search my location in trail. In case I am present more than once in the
1518 * trail (can happen during trail setup), then return my lowest index.
1519 * @param trail List of peers
1520 * @return my_index if found
1521 * trail_length + 1 if an entry is present twice, It is an error.
1522 * -1 if no entry found.
1525 search_my_index (const struct GNUNET_PeerIdentity *trail,
1529 int index_seen = trail_length + 1;
1532 for (i = 0; i < trail_length; i++)
1534 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1537 if(index_seen == (trail_length + 1))
1541 DEBUG("Entry is present twice in trail. Its not allowed\n");
1555 * Check if the friend is congested or have reached maximum number of trails
1556 * it can be part of of.
1557 * @param friend Friend to be checked.
1558 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1559 * #GNUNET_YES if friend is either congested or have crossed threshold
1562 is_friend_congested (struct FriendInfo *friend)
1564 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1565 ((0 == GNUNET_TIME_absolute_get_remaining
1566 (friend->congestion_timestamp).rel_value_us)))
1574 * Select closest finger to value.
1575 * @param peer1 First peer
1576 * @param peer2 Second peer
1577 * @param value Value to be compare
1578 * @return Closest peer
1580 static struct GNUNET_PeerIdentity
1581 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1582 const struct GNUNET_PeerIdentity *peer2,
1585 uint64_t peer1_value;
1586 uint64_t peer2_value;
1588 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1589 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1590 peer1_value = GNUNET_ntohll (peer1_value);
1591 peer2_value = GNUNET_ntohll (peer2_value);
1593 // TODO: Can use a simpler (to understand) idea here!
1594 if (peer1_value == value)
1599 if (peer2_value == value)
1604 if (peer2_value < peer1_value)
1606 if ((peer2_value < value) && (value < peer1_value))
1610 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1611 ((0 < value) && (value < peer2_value)))
1617 //if (peer1_value < peer2_value)
1619 if ((peer1_value < value) && (value < peer2_value))
1623 //else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1624 // ((0 < value) && (value < peer1_value)))
1633 * Select closest predecessor to value.
1634 * @param peer1 First peer
1635 * @param peer2 Second peer
1636 * @param value Value to be compare
1637 * @return Peer which precedes value in the network.
1639 static struct GNUNET_PeerIdentity
1640 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1641 const struct GNUNET_PeerIdentity *peer2,
1644 uint64_t peer1_value;
1645 uint64_t peer2_value;
1647 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1648 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1649 peer1_value = GNUNET_ntohll (peer1_value);
1650 peer2_value = GNUNET_ntohll (peer2_value);
1652 if (peer1_value == value)
1655 if (peer2_value == value)
1658 if (peer1_value < peer2_value)
1660 if ((peer1_value < value) && (value < peer2_value))
1664 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1665 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1671 // if (peer2_value < peer1_value)
1673 if ((peer2_value < value) && (value < peer1_value))
1677 //else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1678 // ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1691 test_print_trail (struct GNUNET_PeerIdentity *trail,
1692 unsigned int trail_length)
1694 struct GNUNET_PeerIdentity print_peer;
1697 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1698 __FILE__, __func__,__LINE__,trail_length);
1699 for (i =0 ; i< trail_length; i++)
1701 print_peer = trail[i];
1702 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1703 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1710 * This is a test function to print all the entries of friend table.
1713 test_friend_peermap_print ()
1715 struct FriendInfo *friend;
1716 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1717 struct GNUNET_PeerIdentity print_peer;
1718 struct GNUNET_PeerIdentity key_ret;
1721 print_peer = my_identity;
1722 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1723 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1725 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1727 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1729 (const void **)&friend))
1731 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1732 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1733 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1741 * This is a test function, to print all the entries of finger table.
1744 test_finger_table_print()
1746 struct FingerInfo *finger;
1747 struct GNUNET_PeerIdentity print_peer;
1748 //struct Trail *trail;
1752 print_peer = my_identity;
1753 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1754 for (i = 0; i < MAX_FINGERS; i++)
1756 finger = &finger_table[i];
1758 if (GNUNET_NO == finger->is_present)
1761 print_peer = finger->finger_identity;
1762 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1763 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1766 for (j = 0; j < finger->trails_count; j++)
1768 trail = &finger->trail_list[j];
1769 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1770 struct Trail_Element *element;
1771 element = trail->trail_head;
1772 for (k = 0; k < trail->trail_length; k++)
1774 print_peer = element->peer;
1775 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1776 element = element->next;
1785 * Select the closest peer among two peers (which should not be same)
1786 * with respect to value and finger_table_index
1787 * NOTE: peer1 != peer2
1788 * @param peer1 First peer
1789 * @param peer2 Second peer
1790 * @param value Value relative to which we find the closest
1791 * @param is_predecessor Is value a predecessor or any other finger.
1792 * @return Closest peer among two peers.
1794 static struct GNUNET_PeerIdentity
1795 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1796 const struct GNUNET_PeerIdentity *peer2,
1798 unsigned int is_predecessor)
1800 /* This check is here to ensure that calling function never sends
1801 same peer value in peer1 and peer2. Remove it later. */
1802 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1803 if (1 == is_predecessor)
1804 return select_closest_predecessor (peer1, peer2, value);
1806 // TODO: Change name to something like select_closest_successor!!
1807 return select_closest_finger (peer1, peer2, value);
1812 * Iterate over the list of all the trails of a finger. In case the first
1813 * friend to reach the finger has reached trail threshold or is congested,
1814 * then don't select it. In case there multiple available good trails to reach
1815 * to Finger, choose the one with shortest trail length.
1816 * Note: We use length as parameter. But we can use any other suitable parameter
1818 * @param finger Finger Finger whose trail we have to select.
1819 * @return Trail Selected Trail.
1821 static struct Trail *
1822 select_finger_trail (struct FingerInfo *finger)
1824 struct FriendInfo *friend;
1825 struct Trail *current_finger_trail;
1826 struct Trail *best_trail = NULL;
1829 GNUNET_assert (finger->trails_count > 0);
1830 for (i = 0; i < finger->trails_count; i++)
1832 current_finger_trail = &finger->trail_list[i];
1834 /* No trail stored at this index. */
1835 if (GNUNET_NO == current_finger_trail->is_present)
1838 GNUNET_assert (NULL !=
1840 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1841 ¤t_finger_trail->trail_head->peer)));
1843 /* First friend to reach trail is not free. */
1844 if (GNUNET_YES == is_friend_congested (friend))
1847 if (NULL == best_trail ||
1848 best_trail->trail_length > current_finger_trail->trail_length)
1850 best_trail = current_finger_trail;
1859 * Compare FINGER entry with current successor. If finger's first friend of all
1860 * its trail is not congested and has not crossed trail threshold, then check
1861 * if finger peer identity is closer to final_destination_finger_value than
1862 * current_successor. If yes then update current_successor.
1863 * @param current_successor[in/out]
1867 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
1869 struct FingerInfo *finger;
1870 struct GNUNET_PeerIdentity closest_peer;
1871 struct Trail *finger_trail;
1874 /* Iterate over finger table. */
1875 for (i = 0; i < MAX_FINGERS; i++)
1877 finger = &finger_table[i];
1879 if (GNUNET_NO == finger->is_present)
1882 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1883 ¤t_closest_peer->best_known_destination))
1886 /* If I am my own finger, then ignore this finger. */
1887 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1891 /* If finger is a friend, we have already checked it in previous function. */
1892 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1893 &finger->finger_identity)))
1898 closest_peer = select_closest_peer (&finger->finger_identity,
1899 ¤t_closest_peer->best_known_destination,
1900 current_closest_peer->destination_finger_value,
1901 current_closest_peer->is_predecessor);
1903 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer))
1905 /* Choose one of the trail to reach to finger. */
1906 finger_trail = select_finger_trail (finger);
1908 /* In case no trail found, ignore this finger. */
1909 if (NULL == finger_trail)
1912 current_closest_peer->best_known_destination = closest_peer;
1913 current_closest_peer->next_hop = finger_trail->trail_head->peer;
1914 current_closest_peer->trail_id = finger_trail->trail_id;
1915 current_closest_peer->finger_table_index = i;
1923 * Compare friend entry with current successor.
1924 * If friend identity and current_successor is same, then do nothing.
1925 * If friend is not congested and has not crossed trail threshold, then check
1926 * if friend peer identity is closer to final_destination_finger_value than
1927 * current_successor. If yes then update current_successor.
1928 * @param cls closure
1929 * @param key current public key
1930 * @param value struct Closest_Peer
1931 * @return #GNUNET_YES if we should continue to iterate,
1932 * #GNUNET_NO if not.
1935 compare_friend_and_current_closest_peer (void *cls,
1936 const struct GNUNET_PeerIdentity *key,
1939 struct FriendInfo *friend = value;
1940 struct Closest_Peer *current_closest_peer = cls;
1941 struct GNUNET_PeerIdentity closest_peer;
1943 /* Friend is either congested or has crossed threshold. */
1944 if (GNUNET_YES == is_friend_congested (friend))
1947 /* If current_closest_peer and friend identity are same, then do nothing.*/
1948 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
1949 ¤t_closest_peer->best_known_destination))
1955 closest_peer = select_closest_peer (&friend->id,
1956 ¤t_closest_peer->best_known_destination,
1957 current_closest_peer->destination_finger_value,
1958 current_closest_peer->is_predecessor);
1960 /* Is friend the closest successor? */
1961 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer))
1963 current_closest_peer->best_known_destination = friend->id;
1964 current_closest_peer->next_hop = friend->id;
1972 * Initialize current_successor to my_identity.
1973 * @param my_identity My peer identity
1974 * @return Updated closest_peer
1976 static struct Closest_Peer
1977 init_current_successor (struct GNUNET_PeerIdentity my_identity,
1978 uint64_t destination_finger_value,
1979 unsigned int is_predecessor)
1981 struct Closest_Peer current_closest_peer;
1983 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
1984 current_closest_peer.destination_finger_value = destination_finger_value;
1985 current_closest_peer.is_predecessor = is_predecessor;
1986 current_closest_peer.next_hop = my_identity;
1987 current_closest_peer.best_known_destination = my_identity;
1988 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
1989 return current_closest_peer;
1994 * Find locally best known peer, among your own identity, friend and finger list,
1995 * which is closest to given destination_finger_value.
1997 * NOTE: In case a friend is also a finger, then it is always chosen as friend
1999 * @param destination_finger_value Peer closest to this value will be the next destination.
2000 * @param is_predecessor Are we looking for predecessor or finger?
2001 * @return Closest_Peer that contains all the relevant field to reach to
2002 * @a destination_finger_value
2004 static struct Closest_Peer
2005 find_local_best_known_next_hop (uint64_t destination_finger_value,
2006 unsigned int is_predecessor)
2008 struct Closest_Peer current_closest_peer;
2010 /* Initialize current_successor to my_identity. */
2011 current_closest_peer = init_current_successor (my_identity,
2012 destination_finger_value,
2015 /* Compare each friend entry with current_successor and update current_successor
2016 * with friend if its closest. */
2019 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2020 &compare_friend_and_current_closest_peer,
2021 ¤t_closest_peer));
2023 /* Compare each finger entry with current_successor and update current_successor
2024 * with finger if its closest. */
2025 compare_finger_and_current_closest_peer (¤t_closest_peer);
2026 return current_closest_peer;
2030 * FIXME; Send put message across all the trail to reach to next hop to handle
2032 * Construct a Put message and send it to target_peer.
2033 * @param key Key for the content
2034 * @param block_type Type of the block
2035 * @param options Routing options
2036 * @param desired_replication_level Desired replication count
2037 * @param best_known_dest Peer to which this message should reach eventually,
2038 * as it is best known destination to me.
2039 * @param intermediate_trail_id Trail id in case
2040 * @param target_peer Peer to which this message will be forwarded.
2041 * @param hop_count Number of hops traversed so far.
2042 * @param put_path_length Total number of peers in @a put_path
2043 * @param put_path Number of peers traversed so far
2044 * @param expiration_time When does the content expire
2045 * @param data Content to store
2046 * @param data_size Size of content @a data in bytes
2049 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2050 enum GNUNET_BLOCK_Type block_type,
2051 enum GNUNET_DHT_RouteOption options,
2052 uint32_t desired_replication_level,
2053 struct GNUNET_PeerIdentity best_known_dest,
2054 struct GNUNET_HashCode intermediate_trail_id,
2055 struct GNUNET_PeerIdentity *target_peer,
2057 uint32_t put_path_length,
2058 struct GNUNET_PeerIdentity *put_path,
2059 struct GNUNET_TIME_Absolute expiration_time,
2060 const void *data, size_t data_size)
2062 struct PeerPutMessage *ppm;
2063 struct P2PPendingMessage *pending;
2064 struct FriendInfo *target_friend;
2065 struct GNUNET_PeerIdentity *pp;
2068 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2069 sizeof (struct PeerPutMessage);
2070 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2072 put_path_length = 0;
2073 msize = data_size + sizeof (struct PeerPutMessage);
2076 /* Should it be GNUNET_SERVER_MAX_MESSAGE_SIZE? */
2077 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2079 DEBUG("msize = %lu\n",msize);
2084 GNUNET_assert (NULL !=
2086 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2087 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2088 pending->timeout = expiration_time;
2089 ppm = (struct PeerPutMessage *) &pending[1];
2090 pending->msg = &ppm->header;
2091 ppm->header.size = htons (msize);
2092 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2093 ppm->options = htonl (options);
2094 ppm->block_type = htonl (block_type);
2095 ppm->hop_count = htonl (hop_count + 1);
2096 ppm->desired_replication_level = htonl (desired_replication_level);
2097 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2098 ppm->best_known_destination = best_known_dest;
2099 ppm->intermediate_trail_id = intermediate_trail_id;
2101 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2102 ppm->put_path_length = htonl (put_path_length);
2103 if(put_path_length > 0)
2105 memcpy (pp, put_path,
2106 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2108 memcpy (&pp[put_path_length], data, data_size);
2109 GNUNET_assert (NULL != target_friend);
2110 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2111 target_friend->pending_count++;
2112 process_friend_queue (target_friend);
2117 * Handle the put request from the client.
2118 * @param key Key for the content
2119 * @param block_type Type of the block
2120 * @param options Routing options
2121 * @param desired_replication_level Desired replication count
2122 * @param expiration_time When does the content expire
2123 * @param data Content to store
2124 * @param data_size Size of content @a data in bytes
2127 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
2128 enum GNUNET_BLOCK_Type block_type,
2129 enum GNUNET_DHT_RouteOption options,
2130 uint32_t desired_replication_level,
2131 struct GNUNET_TIME_Absolute expiration_time,
2132 const void *data, size_t data_size)
2134 struct GNUNET_PeerIdentity best_known_dest;
2135 struct GNUNET_HashCode intermediate_trail_id;
2136 struct GNUNET_PeerIdentity next_hop;
2138 struct Closest_Peer successor;
2140 memcpy (&key_value, key, sizeof (uint64_t));
2141 key_value = GNUNET_ntohll (key_value);
2142 successor = find_local_best_known_next_hop (key_value,
2143 GDS_FINGER_TYPE_NON_PREDECESSOR);
2144 best_known_dest = successor.best_known_destination;
2145 next_hop = successor.next_hop;
2146 intermediate_trail_id = successor.trail_id;
2148 DEBUG("PUT_REQUEST_RECEVIED KEY = %s \n",GNUNET_h2s(key));
2149 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2151 /* I am the destination. */
2152 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2153 block_type,data_size,data);
2154 GDS_CLIENTS_process_put (options, block_type, 0,
2155 ntohl (desired_replication_level),
2156 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time.
2157 key, data, data_size);
2161 /* In case we are sending the request to a finger, then send across all of its
2164 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2165 &successor.next_hop))
2167 struct FingerInfo *next_hop_finger;
2170 next_hop_finger = &finger_table[successor.finger_table_index];
2171 for (i = 0; i < next_hop_finger->trails_count; i++)
2173 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2175 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2177 next_hop_finger->trail_list[i].trail_id,
2178 &next_hop, hop_count, put_path_length, put_path,
2186 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2187 best_known_dest, intermediate_trail_id, &next_hop,
2188 0, 1, &my_identity, expiration_time,
2193 * FIXME; Send get message across all the trail to reach to next hop to handle
2195 * Construct a Get message and send it to target_peer.
2196 * @param key Key for the content
2197 * @param block_type Type of the block
2198 * @param options Routing options
2199 * @param desired_replication_level Desired replication count
2200 * @param best_known_dest Peer which should get this message. Same as target peer
2201 * if best_known_dest is a friend else its a finger.
2202 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2203 * in case it is a finger else set to 0.
2204 * @param target_peer Peer to which this message will be forwarded.
2205 * @param hop_count Number of hops traversed so far.
2206 * @param data Content to store
2207 * @param data_size Size of content @a data in bytes
2208 * @param get_path_length Total number of peers in @a get_path
2209 * @param get_path Number of peers traversed so far
2212 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2213 enum GNUNET_BLOCK_Type block_type,
2214 enum GNUNET_DHT_RouteOption options,
2215 uint32_t desired_replication_level,
2216 struct GNUNET_PeerIdentity best_known_dest,
2217 struct GNUNET_HashCode intermediate_trail_id,
2218 struct GNUNET_PeerIdentity *target_peer,
2220 uint32_t get_path_length,
2221 struct GNUNET_PeerIdentity *get_path)
2223 struct PeerGetMessage *pgm;
2224 struct P2PPendingMessage *pending;
2225 struct FriendInfo *target_friend;
2226 struct GNUNET_PeerIdentity *gp;
2229 msize = sizeof (struct PeerGetMessage) +
2230 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2232 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2237 GNUNET_assert (NULL !=
2239 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2241 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2242 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2243 pending->importance = 0; /* FIXME */
2244 pgm = (struct PeerGetMessage *) &pending[1];
2245 pending->msg = &pgm->header;
2246 pgm->header.size = htons (msize);
2247 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2248 pgm->get_path_length = htonl (get_path_length);
2249 pgm->best_known_destination = best_known_dest;
2251 pgm->intermediate_trail_id = intermediate_trail_id;
2252 pgm->hop_count = htonl (hop_count + 1);
2253 pgm->get_path_length = htonl (get_path_length);
2254 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2255 memcpy (gp, get_path,
2256 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2257 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2258 target_friend->pending_count++;
2259 process_friend_queue (target_friend);
2264 * Handle the get request from the client file. If I am destination do
2265 * datacache put and return. Else find the target friend and forward message
2267 * @param key Key for the content
2268 * @param block_type Type of the block
2269 * @param options Routing options
2270 * @param desired_replication_level Desired replication count
2273 GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key,
2274 enum GNUNET_BLOCK_Type block_type,
2275 enum GNUNET_DHT_RouteOption options,
2276 uint32_t desired_replication_level)
2278 struct Closest_Peer successor;
2279 struct GNUNET_PeerIdentity best_known_dest;
2280 struct GNUNET_HashCode intermediate_trail_id;
2283 memcpy (&key_value, key, sizeof (uint64_t));
2284 key_value = GNUNET_ntohll (key_value);
2286 successor = find_local_best_known_next_hop (key_value,
2287 GDS_FINGER_TYPE_NON_PREDECESSOR);
2289 best_known_dest = successor.best_known_destination;
2290 intermediate_trail_id = successor.trail_id;
2292 DEBUG("GET_REQUEST_RECEVIED KEY = %s \n",GNUNET_h2s(key));
2293 /* I am the destination. I have the data. */
2294 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2297 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2298 NULL, 0, 1, &my_identity, NULL,&my_identity);
2302 /* fixme; for multiple trails, we need to send back finger index and send trail
2303 across all the fingers. but in current implementation we don't have this case.
2304 compare finger and current_successor returns, */
2305 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2306 best_known_dest,intermediate_trail_id, &successor.next_hop,
2307 0, 1, &my_identity);
2312 * Send the get result to requesting client.
2313 * @param key Key of the requested data.
2314 * @param type Block type
2315 * @param target_peer Next peer to forward the message to.
2316 * @param source_peer Peer which has the data for the key.
2317 * @param put_path_length Number of peers in @a put_path
2318 * @param put_path Path taken to put the data at its stored location.
2319 * @param get_path_length Number of peers in @a get_path
2320 * @param get_path Path taken to reach to the location of the key.
2321 * @param expiration When will this result expire?
2322 * @param data Payload to store
2323 * @param data_size Size of the @a data
2326 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2327 enum GNUNET_BLOCK_Type type,
2328 const struct GNUNET_PeerIdentity *target_peer,
2329 const struct GNUNET_PeerIdentity *source_peer,
2330 unsigned int put_path_length,
2331 const struct GNUNET_PeerIdentity *put_path,
2332 unsigned int get_path_length,
2333 const struct GNUNET_PeerIdentity *get_path,
2334 struct GNUNET_TIME_Absolute expiration,
2335 const void *data, size_t data_size)
2337 struct PeerGetResultMessage *get_result;
2338 struct GNUNET_PeerIdentity *paths;
2339 struct P2PPendingMessage *pending;
2340 struct FriendInfo *target_friend;
2341 int current_path_index;
2344 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2346 sizeof (struct PeerGetResultMessage);
2348 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2350 put_path_length = 0;
2351 msize = msize - put_path_length;
2355 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2360 current_path_index = 0;
2361 if(get_path_length > 0)
2363 current_path_index = search_my_index(get_path, get_path_length);
2364 if (-1 == current_path_index)
2369 if ((get_path_length + 1) == current_path_index)
2371 DEBUG ("Peer found twice in get path. Not allowed \n");
2376 if (0 == current_path_index)
2378 DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",GNUNET_h2s(key),GNUNET_i2s(&my_identity));
2379 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2380 get_path, put_path_length,
2381 put_path, type, data_size, data);
2385 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2386 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2387 pending->importance = 0;
2388 get_result = (struct PeerGetResultMessage *)&pending[1];
2389 pending->msg = &get_result->header;
2390 get_result->header.size = htons (msize);
2391 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2392 get_result->key = *key;
2393 get_result->querying_peer = *source_peer;
2394 get_result->expiration_time = expiration;
2395 get_result->get_path_length = htonl (get_path_length);
2396 get_result->put_path_length = htonl (put_path_length);
2397 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2398 memcpy (paths, put_path,
2399 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2400 memcpy (&paths[put_path_length], get_path,
2401 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2402 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2404 GNUNET_assert (NULL !=
2406 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2407 &get_path[current_path_index - 1])));
2408 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2409 target_friend->pending_count++;
2410 process_friend_queue (target_friend);
2415 * Randomly choose one of your friends (which is not congested and have not crossed
2416 * trail threshold) from the friend_peermap
2417 * @return Friend Randomly chosen friend.
2418 * NULL in case friend peermap is empty, or all the friends are either
2419 * congested or have crossed trail threshold.
2421 static struct FriendInfo *
2422 select_random_friend ()
2424 unsigned int current_size;
2427 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2428 struct GNUNET_PeerIdentity key_ret;
2429 struct FriendInfo *friend;
2431 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2434 if (0 == current_size)
2437 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2438 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2440 /* Iterate till you don't reach to index. */
2441 for (j = 0; j < index ; j++)
2442 GNUNET_assert (GNUNET_YES ==
2443 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2447 /* Reset the index in friend peermap to 0 as we reached to the end. */
2448 if (j == current_size)
2451 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2452 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2456 /* Get the friend stored at the index, j*/
2457 GNUNET_assert (GNUNET_YES ==
2458 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2460 (const void **)&friend));
2462 /* This friend is not congested and has not crossed trail threshold. */
2463 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2464 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2470 } while (j != index);
2472 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2478 * Compute 64 bit value of finger_identity corresponding to a finger index using
2480 * For all fingers, n.finger[i] = n + pow (2,i),
2481 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2482 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2483 * @param finger_index Index corresponding to which we calculate 64 bit value.
2484 * @return 64 bit value.
2487 compute_finger_identity_value (unsigned int finger_index)
2491 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2492 my_id64 = GNUNET_ntohll (my_id64);
2494 /* Are we looking for immediate predecessor? */
2495 if (PREDECESSOR_FINGER_ID == finger_index)
2496 return (my_id64 - 1);
2499 uint64_t add = (uint64_t)1 << finger_index;
2500 return (my_id64 + add);
2506 * Choose a random friend. Calculate the next finger identity to search,from
2507 * current_search_finger_index. Start looking for the trail to reach to
2508 * finger identity through this random friend.
2510 * @param cls closure for this task
2511 * @param tc the context under which the task is running
2514 send_find_finger_trail_message (void *cls,
2515 const struct GNUNET_SCHEDULER_TaskContext *tc)
2517 struct FriendInfo *target_friend;
2518 struct GNUNET_HashCode trail_id;
2519 struct GNUNET_HashCode intermediate_trail_id;
2520 unsigned int is_predecessor = 0;
2521 uint64_t finger_id_value;
2523 /* Schedule another send_find_finger_trail_message task. After one round of
2524 * finger search, this time is exponentially backoff. */
2525 find_finger_trail_task_next_send_time.rel_value_us =
2526 find_finger_trail_task_next_send_time.rel_value_us +
2527 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2528 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2529 find_finger_trail_task =
2530 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2531 &send_find_finger_trail_message,
2534 /* No space in my routing table. (Source and destination peers also store entries
2535 * in their routing table). */
2536 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2539 target_friend = select_random_friend ();
2540 if (NULL == target_friend)
2545 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2546 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2549 /* Generate a unique trail id for trail we are trying to setup. */
2550 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2551 &trail_id, sizeof (trail_id));
2552 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2553 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2554 target_friend->id, target_friend, 0, NULL,
2555 is_predecessor, trail_id,
2556 intermediate_trail_id);
2561 * In case there are already maximum number of possible trails to reach to a
2562 * finger, then check if the new trail's length is lesser than any of the
2564 * If yes then replace that old trail by new trail.
2566 * Note: Here we are taking length as a parameter to choose the best possible
2567 * trail, but there could be other parameters also like:
2568 * 1. duration of existence of a trail - older the better.
2569 * 2. if the new trail is completely disjoint than the
2570 * other trails, then may be choosing it is better.
2572 * @param finger Finger
2573 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2574 * including the endpoints.
2575 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2576 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2579 select_and_replace_trail (struct FingerInfo *finger,
2580 const struct GNUNET_PeerIdentity *new_trail,
2581 unsigned int new_trail_length,
2582 struct GNUNET_HashCode new_trail_id)
2584 struct Trail *current_trail;
2585 unsigned int largest_trail_length;
2586 unsigned int largest_trail_index;
2587 struct Trail_Element *trail_element;
2588 struct GNUNET_PeerIdentity *next_hop;
2591 largest_trail_length = new_trail_length;
2592 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2594 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2596 for (i = 0; i < finger->trails_count; i++)
2598 current_trail = &finger->trail_list[i];
2599 GNUNET_assert (GNUNET_YES == current_trail->is_present);
2600 if (current_trail->trail_length > largest_trail_length)
2602 largest_trail_length = current_trail->trail_length;
2603 largest_trail_index = i;
2607 /* New trail is not better than existing ones. Send trail teardown. */
2608 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2610 next_hop = GDS_ROUTING_get_next_hop (new_trail_id, GDS_ROUTING_SRC_TO_DEST);
2611 GDS_ROUTING_remove_trail (new_trail_id);
2612 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2613 GDS_ROUTING_SRC_TO_DEST,
2618 /* Send trail teardown message across the replaced trail. */
2619 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2620 next_hop = GDS_ROUTING_get_next_hop (replace_trail->trail_id, GDS_ROUTING_SRC_TO_DEST);
2621 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2622 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2623 GDS_ROUTING_SRC_TO_DEST,
2626 /* Free the trail. */
2627 while (NULL != (trail_element = replace_trail->trail_head))
2629 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2630 replace_trail->trail_tail, trail_element);
2631 GNUNET_free_non_null (trail_element);
2634 /* Add new trial at that location. */
2635 replace_trail->is_present = GNUNET_YES;
2636 replace_trail->trail_length = new_trail_length;
2637 replace_trail->trail_id = new_trail_id;
2639 for (i = 0; i < new_trail_length; i++)
2641 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2642 element->peer = new_trail[i];
2644 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2645 replace_trail->trail_tail,
2648 /* FIXME: URGENT Are we adding the trail back to the list. */
2653 * Check if the new trail to reach to finger is unique or do we already have
2654 * such a trail present for finger.
2655 * @param existing_finger Finger identity
2656 * @param new_trail New trail to reach @a existing_finger
2657 * @param trail_length Total number of peers in new_trail.
2658 * @return #GNUNET_YES if the new trail is unique
2659 * #GNUNET_NO if same trail is already present.
2662 is_new_trail_unique (struct FingerInfo *existing_finger,
2663 const struct GNUNET_PeerIdentity *new_trail,
2664 unsigned int trail_length)
2666 struct Trail *current_trail;
2667 struct Trail_Element *trail_element;
2671 GNUNET_assert (existing_finger->trails_count > 0);
2673 /* Iterate over list of trails. */
2674 for (i = 0; i < existing_finger->trails_count; i++)
2676 current_trail = &(existing_finger->trail_list[i]);
2677 if(GNUNET_NO == current_trail->is_present)
2680 /* New trail and existing trail length are not same. */
2681 if (current_trail->trail_length != trail_length)
2686 trail_element = current_trail->trail_head;
2687 for (j = 0; j < current_trail->trail_length; j++)
2689 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2690 &trail_element->peer))
2694 trail_element = trail_element->next;
2701 * FIXME; In case of multiple trails, we may have a case where a trail from in
2702 * between has been removed, then we should try to find a free slot , not simply
2703 * add a trail at then end of the list.
2704 * Add a new trail at a free slot in trail array of existing finger.
2705 * @param existing_finger Finger
2706 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2707 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2708 * @param new_finger_trail_id Unique identifier of the trail.
2711 add_new_trail (struct FingerInfo *existing_finger,
2712 const struct GNUNET_PeerIdentity *new_trail,
2713 unsigned int new_trail_length,
2714 struct GNUNET_HashCode new_trail_id)
2716 struct FriendInfo *friend;
2717 struct Trail *trail;
2721 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2725 for (i = 0; i < existing_finger->trails_count; i++)
2727 if (GNUNET_NO == existing_finger->trail_list[i].is_present)
2734 if (-1 == free_slot)
2737 trail = &existing_finger->trail_list[free_slot];
2738 GNUNET_assert (GNUNET_NO == trail->is_present);
2739 trail->trail_id = new_trail_id;
2740 trail->trail_length = new_trail_length;
2741 existing_finger->trails_count++;
2742 trail->is_present = GNUNET_YES;
2743 if (0 == new_trail_length)
2745 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2746 &existing_finger->finger_identity);
2750 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2754 friend->trails_count++;
2755 for (i = 0; i < new_trail_length; i++)
2757 struct Trail_Element *element;
2759 element = GNUNET_new (struct Trail_Element);
2760 element->peer = new_trail[i];
2761 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2766 existing_finger->trail_list[free_slot].trail_head = trail->trail_head;
2767 existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail;
2768 existing_finger->trail_list[free_slot].trail_length = new_trail_length;
2769 existing_finger->trail_list[free_slot].trail_id = new_trail_id;
2770 existing_finger->trail_list[free_slot].is_present = GNUNET_YES;
2776 * FIXME; In case of multiple trails, we may have a case where a trail from in
2777 * between has been removed, then we should try to find a free slot , not simply
2778 * add a trail at then end of the list.
2779 * Add a new trail at a free slot in trail array of existing finger.
2780 * @param existing_finger Finger
2781 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2782 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2783 * @param new_finger_trail_id Unique identifier of the trail.
2786 add_new_trail (struct FingerInfo *existing_finger,
2787 const struct GNUNET_PeerIdentity *new_trail,
2788 unsigned int new_trail_length,
2789 struct GNUNET_HashCode new_trail_id)
2791 struct Trail *trail;
2792 struct FriendInfo *first_friend;
2796 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2800 index = existing_finger->trails_count;
2801 trail = &existing_finger->trail_list[index];
2802 GNUNET_assert (GNUNET_NO == trail->is_present);
2803 trail->trail_id = new_trail_id;
2804 trail->trail_length = new_trail_length;
2805 existing_finger->trails_count++;
2806 trail->is_present = GNUNET_YES;
2808 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2809 &existing_finger->finger_identity)));
2810 /* If finger is a friend then we never call this function. */
2811 GNUNET_assert (new_trail_length > 0);
2813 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2815 first_friend->trails_count++;
2817 for (i = 0; i < new_trail_length; i++)
2819 struct Trail_Element *element;
2821 element = GNUNET_new (struct Trail_Element);
2822 element->peer = new_trail[i];
2823 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2827 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2828 existing_finger->trail_list[index].trail_head = trail->trail_head;
2829 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2830 existing_finger->trail_list[index].trail_length = new_trail_length;
2831 existing_finger->trail_list[index].trail_id = new_trail_id;
2832 existing_finger->trail_list[index].is_present = GNUNET_YES;
2837 * Get the next hop to send trail teardown message from routing table and
2838 * then delete the entry from routing table. Send trail teardown message for a
2839 * specific trail of a finger.
2840 * @param finger Finger whose trail is to be removed.
2841 * @param trail List of peers in trail from me to a finger, NOT including
2845 send_trail_teardown (struct FingerInfo *finger,
2846 struct Trail *trail)
2848 struct FriendInfo *friend;
2849 struct GNUNET_PeerIdentity *next_hop;
2851 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2852 GDS_ROUTING_SRC_TO_DEST);
2853 if (NULL == next_hop)
2855 // DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d",
2856 // GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length);
2859 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2862 GNUNET_assert(GNUNET_YES == trail->is_present);
2863 if (trail->trail_length > 0)
2865 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2866 &trail->trail_head->peer);
2870 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2871 &finger->finger_identity);
2876 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2877 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
2880 if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)
2881 && (0 == trail->trail_length))
2883 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2884 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
2887 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2888 friend->trails_count--;
2889 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2890 GDS_ROUTING_SRC_TO_DEST,
2896 * Send trail teardown message across all the trails to reach to finger.
2897 * @param finger Finger whose all the trail should be freed.
2900 send_all_finger_trails_teardown (struct FingerInfo *finger)
2903 for (i = 0; i < finger->trails_count; i++)
2905 struct Trail *trail;
2906 trail = &finger->trail_list[i];
2907 if (GNUNET_YES == trail->is_present);
2909 send_trail_teardown (finger, trail);
2910 trail->is_present = GNUNET_NO;
2917 * Free a specific trail
2918 * @param trail List of peers to be freed.
2921 free_trail (struct Trail *trail)
2923 struct Trail_Element *trail_element;
2925 while (NULL != (trail_element = trail->trail_head))
2927 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2930 GNUNET_free_non_null (trail_element);
2932 trail->trail_head = NULL;
2933 trail->trail_tail = NULL;
2938 * Free finger and its trail.
2939 * @param finger Finger to be freed.
2940 * @param finger_table_index Index at which finger is stored.
2943 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2945 struct Trail *trail;
2947 for (i = 0; i < finger->trails_count; i++)
2949 trail = &finger->trail_list[i];
2950 if (GNUNET_NO == trail->is_present)
2953 if (trail->trail_length > 0)
2955 trail->is_present = GNUNET_NO;
2958 finger->is_present = GNUNET_NO;
2959 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2964 * Add a new entry in finger table at finger_table_index.
2965 * In case I am my own finger, then we don't have a trail. In case of a friend,
2966 * we have a trail with unique id and '0' trail length.
2967 * In case a finger is a friend, then increment the trails count of the friend.
2968 * @param finger_identity Peer Identity of new finger
2969 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2970 * @param finger_trail_length Total number of peers in @a finger_trail.
2971 * @param trail_id Unique identifier of the trail.
2972 * @param finger_table_index Index in finger table.
2975 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2976 const struct GNUNET_PeerIdentity *finger_trail,
2977 unsigned int finger_trail_length,
2978 struct GNUNET_HashCode trail_id,
2979 unsigned int finger_table_index)
2981 struct FingerInfo *new_entry;
2982 struct FriendInfo *first_trail_hop;
2983 struct Trail *trail;
2986 new_entry = GNUNET_new (struct FingerInfo);
2987 new_entry->finger_identity = finger_identity;
2988 new_entry->finger_table_index = finger_table_index;
2989 new_entry->is_present = GNUNET_YES;
2991 /* If the new entry is my own identity. */
2992 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2995 new_entry->trails_count = 0;
2996 finger_table[finger_table_index] = *new_entry;
2997 GNUNET_free (new_entry);
3001 /* Finger is a friend. */
3002 if (0 == finger_trail_length)
3004 new_entry->trail_list[0].trail_id = trail_id;
3005 new_entry->trails_count = 1;
3006 new_entry->trail_list[0].is_present = GNUNET_YES;
3007 new_entry->trail_list[0].trail_length = 0;
3008 new_entry->trail_list[0].trail_head = NULL;
3009 new_entry->trail_list[0].trail_tail = NULL;
3010 finger_table[finger_table_index] = *new_entry;
3011 GNUNET_assert (NULL !=
3013 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3014 &finger_identity)));
3016 first_trail_hop->trails_count++;
3017 GNUNET_free (new_entry);
3021 GNUNET_assert (NULL !=
3023 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3024 &finger_trail[0])));
3025 new_entry->trails_count = 1;
3026 first_trail_hop->trails_count++;
3027 /* Copy the finger trail into trail. */
3028 trail = GNUNET_new (struct Trail);
3029 for(i = 0; i < finger_trail_length; i++)
3031 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3033 element->next = NULL;
3034 element->prev = NULL;
3035 element->peer = finger_trail[i];
3036 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3041 /* Add trail to trail list. */
3042 new_entry->trail_list[0].trail_head = trail->trail_head;
3043 new_entry->trail_list[0].trail_tail = trail->trail_tail;
3044 new_entry->trail_list[0].trail_length = finger_trail_length;
3045 new_entry->trail_list[0].trail_id = trail_id;
3046 new_entry->trail_list[0].is_present = GNUNET_YES;
3047 finger_table[finger_table_index] = *new_entry;
3048 GNUNET_free (new_entry);
3054 * Periodic task to verify current successor. There can be multiple trails to reach
3055 * to successor, choose the shortest one and send verify successor message
3056 * across that trail.
3057 * @param cls closure for this task
3058 * @param tc the context under which the task is running
3061 send_verify_successor_message (void *cls,
3062 const struct GNUNET_SCHEDULER_TaskContext *tc)
3064 struct FriendInfo *target_friend;
3065 struct GNUNET_HashCode trail_id;
3066 struct Trail *trail;
3067 struct Trail_Element *element;
3068 unsigned int trail_length;
3070 struct FingerInfo *successor;
3072 /* After one round of verify successor, we do back off. */
3073 send_verify_successor_task =
3074 GNUNET_SCHEDULER_add_delayed (verify_successor_next_send_time,
3075 &send_verify_successor_message,
3077 successor = &finger_table[0];
3078 /* Among all the trails to reach to successor, select first one which is present.*/
3079 for (i = 0; i < successor->trails_count; i++)
3081 trail = &successor->trail_list[i];
3082 if(GNUNET_YES == trail->is_present)
3086 /* No valid trail found to reach to successor. */
3087 if (i == successor->trails_count)
3090 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3091 &successor->finger_identity));
3092 /* Trail stored at this index. */
3093 GNUNET_assert (GNUNET_YES == trail->is_present);
3094 trail_id = trail->trail_id;
3095 if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST))
3097 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3098 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
3102 trail_length = trail->trail_length;
3103 if (trail_length > 0)
3105 /* Copy the trail into peer list. */
3106 struct GNUNET_PeerIdentity peer_list[trail_length];
3107 element = trail->trail_head;
3108 for(i = 0; i < trail_length; i++)
3110 peer_list[i] = element->peer;
3111 element = element->next;
3113 GNUNET_assert (NULL != (target_friend =
3114 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3116 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3117 successor->finger_identity,
3118 trail_id, peer_list, trail_length,
3123 GNUNET_assert (NULL != (target_friend =
3124 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3125 &successor->finger_identity)));
3126 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3127 successor->finger_identity,
3135 * FIXME: should this be a periodic task, incrementing the search finger index?
3136 * Update the current search finger index.
3137 * @a finger_identity
3138 * @a finger_table_index
3141 update_current_search_finger_index (unsigned int finger_table_index)
3143 struct FingerInfo *successor;
3145 /* FIXME correct this: only move current index periodically */
3146 if (finger_table_index != current_search_finger_index)
3149 successor = &finger_table[0];
3150 GNUNET_assert (GNUNET_YES == successor->is_present);
3152 /* We were looking for immediate successor. */
3153 if (0 == current_search_finger_index)
3155 current_search_finger_index = PREDECESSOR_FINGER_ID;
3156 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &successor->finger_identity))
3158 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3160 send_verify_successor_task =
3161 GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3167 current_search_finger_index = current_search_finger_index - 1;
3173 * Get the least significant bit set in val.
3176 * @return Position of first bit set, 65 in case of error.
3179 find_set_bit (uint64_t val)
3199 return 65; /* Some other bit was set to 1 as well. */
3206 * Calculate finger_table_index from initial 64 bit finger identity value that
3207 * we send in trail setup message.
3208 * @param ultimate_destination_finger_value Value that we calculated from our
3209 * identity and finger_table_index.
3210 * @param is_predecessor Is the entry for predecessor or not?
3211 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3212 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3215 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3216 unsigned int is_predecessor)
3220 unsigned int finger_table_index;
3222 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3223 my_id64 = GNUNET_ntohll (my_id64);
3225 /* Is this a predecessor finger? */
3226 if (1 == is_predecessor)
3228 diff = my_id64 - ultimate_destination_finger_value;
3230 finger_table_index = PREDECESSOR_FINGER_ID;
3232 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3237 diff = ultimate_destination_finger_value - my_id64;
3238 finger_table_index = find_set_bit (diff);
3240 return finger_table_index;
3245 * Remove finger and its associated data structures from finger table.
3246 * @param existing_finger Finger to be removed which is in finger table.
3247 * @param finger_table_index Index in finger table where @a existing_finger
3251 remove_existing_finger (struct FingerInfo *existing_finger,
3252 unsigned int finger_table_index)
3254 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3256 /* If I am my own finger, then we have no trails. */
3257 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3260 existing_finger->is_present = GNUNET_NO;
3261 memset ((void *)&finger_table[finger_table_index], 0,
3262 sizeof (finger_table[finger_table_index]));
3266 /* For all other fingers, send trail teardown across all the trails to reach
3267 finger, and free the finger. */
3268 send_all_finger_trails_teardown (existing_finger);
3269 free_finger (existing_finger, finger_table_index);
3275 * Check if there is already an entry in finger_table at finger_table_index.
3276 * We get the finger_table_index from 64bit finger value we got from the network.
3277 * -- If yes, then select the closest finger.
3278 * -- If new and existing finger are same, then check if you can store more
3280 * -- If yes then add trail, else keep the best trails to reach to the
3282 * -- If the new finger is closest, remove the existing entry, send trail
3283 * teardown message across all the trails to reach the existing entry.
3284 * Add the new finger.
3285 * -- If new and existing finger are different, and existing finger is closest
3287 * -- Update current_search_finger_index.
3288 * @param finger_identity Peer Identity of new finger
3289 * @param finger_trail Trail to reach the new finger
3290 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3291 * @param is_predecessor Is this entry for predecessor in finger_table?
3292 * @param finger_value 64 bit value of finger identity that we got from network.
3293 * @param finger_trail_id Unique identifier of @finger_trail.
3296 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3297 const struct GNUNET_PeerIdentity *finger_trail,
3298 unsigned int finger_trail_length,
3299 unsigned int is_predecessor,
3300 uint64_t finger_value,
3301 struct GNUNET_HashCode finger_trail_id)
3303 struct FingerInfo *existing_finger;
3304 struct GNUNET_PeerIdentity closest_peer;
3305 struct FingerInfo *successor;
3306 unsigned int finger_table_index;
3308 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3309 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3311 /* Invalid finger_table_index. */
3312 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3314 GNUNET_break_op (0);
3318 /* Check if new entry is same as successor. */
3319 if ((0 != finger_table_index) &&
3320 (PREDECESSOR_FINGER_ID != finger_table_index))
3322 successor = &finger_table[0];
3323 if (GNUNET_NO == successor->is_present)
3328 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3329 &successor->finger_identity))
3331 // find_finger_trail_task_next_send_time =
3332 // GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3333 current_search_finger_index = 0;
3334 GNUNET_STATISTICS_update (GDS_stats,
3336 ("# FINGERS_COUNT"), (int64_t) total_fingers_found,
3338 total_fingers_found = 0;
3342 struct FingerInfo prev_finger;
3343 prev_finger = finger_table[finger_table_index - 1];
3344 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3345 &prev_finger.finger_identity))
3347 current_search_finger_index--;
3352 total_fingers_found++;
3353 existing_finger = &finger_table[finger_table_index];
3355 /* No entry present in finger_table for given finger map index. */
3356 if (GNUNET_NO == existing_finger->is_present)
3358 add_new_finger (finger_identity, finger_trail,
3359 finger_trail_length,
3360 finger_trail_id, finger_table_index);
3361 update_current_search_finger_index (finger_table_index);
3365 /* If existing entry and finger identity are not same. */
3366 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3369 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3374 /* If the new finger is the closest peer. */
3375 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer))
3377 remove_existing_finger (existing_finger, finger_table_index);
3378 add_new_finger (finger_identity, finger_trail, finger_trail_length,
3379 finger_trail_id, finger_table_index);
3383 /* Existing finger is the closest one. We need to send trail teardown
3384 across the trail setup in routing table of all the peers. */
3385 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3387 if (finger_trail_length > 0)
3388 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3389 GDS_ROUTING_SRC_TO_DEST,
3392 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3393 GDS_ROUTING_SRC_TO_DEST,
3400 /* If both new and existing entry are same as my_identity, then do nothing. */
3401 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3407 /* If there is space to store more trails. */
3408 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3409 add_new_trail (existing_finger, finger_trail,
3410 finger_trail_length, finger_trail_id);
3412 select_and_replace_trail (existing_finger, finger_trail,
3413 finger_trail_length, finger_trail_id);
3415 update_current_search_finger_index (finger_table_index);
3421 * FIXME: Check for loop in the request. If you already are part of put path,
3422 * then you need to reset the put path length.
3423 * Core handler for P2P put messages.
3424 * @param cls closure
3425 * @param peer sender of the request
3426 * @param message message
3427 * @return #GNUNET_OK to keep the connection open,
3428 * #GNUNET_SYSERR to close it (signal serious error)
3431 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3432 const struct GNUNET_MessageHeader *message)
3434 struct PeerPutMessage *put;
3435 struct GNUNET_PeerIdentity *put_path;
3436 struct GNUNET_PeerIdentity best_known_dest;
3437 struct GNUNET_HashCode intermediate_trail_id;
3438 struct GNUNET_PeerIdentity *next_hop;
3439 enum GNUNET_DHT_RouteOption options;
3440 struct GNUNET_HashCode test_key;
3445 size_t payload_size;
3448 #if ENABLE_MALICIOUS
3449 if(1 == act_malicious)
3451 DEBUG("I am malicious,dropping put request. \n");
3456 msize = ntohs (message->size);
3457 if (msize < sizeof (struct PeerPutMessage))
3459 GNUNET_break_op (0);
3463 put = (struct PeerPutMessage *) message;
3464 putlen = ntohl (put->put_path_length);
3466 sizeof (struct PeerPutMessage) +
3467 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3469 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3471 GNUNET_break_op (0);
3475 GNUNET_STATISTICS_update (GDS_stats,
3477 ("# Bytes received from other peers"), (int64_t) msize,
3480 best_known_dest = put->best_known_destination;
3481 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3482 payload = &put_path[putlen];
3483 options = ntohl (put->options);
3484 intermediate_trail_id = put->intermediate_trail_id;
3485 hop_count = ntohl(put->hop_count);
3486 payload_size = msize - (sizeof (struct PeerPutMessage) +
3487 putlen * sizeof (struct GNUNET_PeerIdentity));
3489 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3490 payload, payload_size, &test_key))
3493 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3495 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3496 GNUNET_break_op (0);
3497 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3498 "PUT with key `%s' for block with key %s\n",
3499 put_s, GNUNET_h2s_full (&test_key));
3500 GNUNET_free (put_s);
3505 GNUNET_break_op (0);
3508 /* cannot verify, good luck */
3512 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3514 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3515 ntohl (put->block_type),
3517 NULL, 0, /* bloom filer */
3518 NULL, 0, /* xquery */
3519 payload, payload_size))
3521 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3522 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3525 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3526 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3527 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3528 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3529 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3530 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3532 GNUNET_break_op (0);
3537 /* Check if you are already a part of put path. */
3539 for (i = 0; i < putlen; i++)
3541 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3548 /* Add yourself to the list. */
3549 struct GNUNET_PeerIdentity pp[putlen + 1];
3550 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3552 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3553 pp[putlen] = my_identity;
3559 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3560 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3562 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3563 GDS_ROUTING_SRC_TO_DEST);
3564 if (NULL == next_hop)
3566 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3567 GNUNET_i2s(&my_identity), GNUNET_h2s(&intermediate_trail_id), __LINE__);
3568 GNUNET_STATISTICS_update (GDS_stats,
3569 gettext_noop ("# Next hop to forward the packet not found "
3570 "trail setup request, packet dropped."),
3573 GNUNET_break_op (0);
3574 //FIXME: Adding put here,only to ensure that process does not hang. but
3575 // should not be here. fix the logic.
3576 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3577 &(put->key),putlen, pp, ntohl (put->block_type),
3578 payload_size, payload);
3583 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3589 struct Closest_Peer successor;
3590 key_value = GNUNET_ntohll (key_value);
3591 successor = find_local_best_known_next_hop (key_value,
3592 GDS_FINGER_TYPE_NON_PREDECESSOR);
3593 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3594 *next_hop = successor.next_hop;
3595 intermediate_trail_id = successor.trail_id;
3596 best_known_dest = successor.best_known_destination;
3601 GDS_CLIENTS_process_put (options,
3602 ntohl (put->block_type),
3604 ntohl (put->desired_replication_level),
3606 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3611 /* I am the final destination */
3612 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3614 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3615 &(put->key),putlen, pp, ntohl (put->block_type),
3616 payload_size, payload);
3620 GDS_NEIGHBOURS_send_put (&put->key,
3621 ntohl (put->block_type),ntohl (put->options),
3622 ntohl (put->desired_replication_level),
3623 best_known_dest, intermediate_trail_id, next_hop,
3624 hop_count, putlen, pp,
3625 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3626 payload, payload_size);
3633 * FIXME: Check for loop in the request. If you already are part of get path,
3634 * then you need to reset the get path length.
3635 * Core handler for p2p get requests.
3637 * @param cls closure
3638 * @param peer sender of the request
3639 * @param message message
3640 * @return #GNUNET_OK to keep the connection open,
3641 * #GNUNET_SYSERR to close it (signal serious error)
3644 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3645 const struct GNUNET_MessageHeader *message)
3647 const struct PeerGetMessage *get;
3648 const struct GNUNET_PeerIdentity *get_path;
3649 struct GNUNET_PeerIdentity best_known_dest;
3650 struct GNUNET_HashCode intermediate_trail_id;
3651 struct GNUNET_PeerIdentity *next_hop;
3652 uint32_t get_length;
3657 #if ENABLE_MALICIOUS
3658 if(1 == act_malicious)
3660 DEBUG("I am malicious,dropping get request. \n");
3665 msize = ntohs (message->size);
3666 if (msize < sizeof (struct PeerGetMessage))
3668 GNUNET_break_op (0);
3672 get = (const struct PeerGetMessage *)message;
3673 get_length = ntohl (get->get_path_length);
3674 best_known_dest = get->best_known_destination;
3675 intermediate_trail_id = get->intermediate_trail_id;
3676 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3677 hop_count = get->hop_count;
3681 sizeof (struct PeerGetMessage) +
3682 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3684 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3686 GNUNET_break_op (0);
3690 GNUNET_STATISTICS_update (GDS_stats,
3692 ("# Bytes received from other peers"), msize,
3695 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3696 key_value = GNUNET_ntohll (key_value);
3698 /* Check if you are already a part of get path. */
3700 for (i = 0; i < get_length; i++)
3702 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &get_path[i]))
3709 /* Add yourself in the get path. */
3710 struct GNUNET_PeerIdentity gp[get_length + 1];
3711 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3712 gp[get_length] = my_identity;
3713 get_length = get_length + 1;
3714 GDS_CLIENTS_process_get (get->options, get->block_type, hop_count,
3715 get->desired_replication_level, get->get_path_length,
3718 /* I am not the final destination. I am part of trail to reach final dest. */
3719 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3721 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3722 GDS_ROUTING_SRC_TO_DEST);
3723 if (NULL == next_hop)
3725 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3726 GNUNET_i2s(&my_identity), GNUNET_h2s(&intermediate_trail_id), __LINE__);
3727 GNUNET_STATISTICS_update (GDS_stats,
3728 gettext_noop ("# Next hop to forward the packet not found "
3729 "GET request, packet dropped."),
3732 /* We are not able to proceed further*/
3733 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3734 get_length, gp, &gp[get_length - 2],
3741 struct Closest_Peer successor;
3743 successor = find_local_best_known_next_hop (key_value,
3744 GDS_FINGER_TYPE_NON_PREDECESSOR);
3745 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3746 *next_hop = successor.next_hop;
3747 best_known_dest = successor.best_known_destination;
3748 intermediate_trail_id = successor.trail_id;
3751 /* I am the final destination. */
3752 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3754 if (1 == get_length)
3756 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0,
3757 NULL, 0, 1, &my_identity, NULL,&my_identity);
3761 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3762 get_length, gp, &gp[get_length - 2],
3768 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3769 get->desired_replication_level, best_known_dest,
3770 intermediate_trail_id, next_hop, hop_count,
3778 * Core handler for get result
3779 * @param cls closure
3780 * @param peer sender of the request
3781 * @param message message
3782 * @return #GNUNET_OK to keep the connection open,
3783 * #GNUNET_SYSERR to close it (signal serious error)
3786 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3787 const struct GNUNET_MessageHeader *message)
3789 const struct PeerGetResultMessage *get_result;
3790 const struct GNUNET_PeerIdentity *get_path;
3791 const struct GNUNET_PeerIdentity *put_path;
3792 const void *payload;
3793 size_t payload_size;
3795 unsigned int getlen;
3796 unsigned int putlen;
3797 int current_path_index;
3799 msize = ntohs (message->size);
3800 if (msize < sizeof (struct PeerGetResultMessage))
3802 GNUNET_break_op (0);
3806 get_result = (const struct PeerGetResultMessage *)message;
3807 getlen = ntohl (get_result->get_path_length);
3808 putlen = ntohl (get_result->put_path_length);
3811 sizeof (struct PeerGetResultMessage) +
3812 getlen * sizeof (struct GNUNET_PeerIdentity) +
3813 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3815 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3817 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3819 GNUNET_break_op (0);
3822 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3823 GNUNET_STATISTICS_update (GDS_stats,
3825 ("# Bytes received from other peers"), msize,
3828 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3829 get_path = &put_path[putlen];
3830 payload = (const void *) &get_path[getlen];
3831 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3832 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3834 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3836 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3837 getlen, get_path, putlen,
3838 put_path, get_result->type, payload_size, payload);
3843 current_path_index = search_my_index (get_path, getlen);
3844 if (-1 == current_path_index )
3846 DEBUG ("No entry found in get path.\n");
3848 return GNUNET_SYSERR;
3850 if((getlen + 1) == current_path_index)
3852 DEBUG("Present twice in get path. Not allowed. \n");
3854 return GNUNET_SYSERR;
3856 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3857 &get_path[current_path_index - 1],
3858 &(get_result->querying_peer), putlen, put_path,
3859 getlen, get_path, get_result->expiration_time,
3860 payload, payload_size);
3863 return GNUNET_SYSERR;
3868 * Find the next hop to pass trail setup message. First find the local best known
3869 * hop from your own identity, friends and finger. If you were part of trail,
3870 * then get the next hop from routing table. Compare next_hop from routing table
3871 * and local best known hop, and return the closest one to final_dest_finger_val
3872 * @param final_dest_finger_val 64 bit value of finger identity
3873 * @param intermediate_trail_id If you are part of trail to reach to some other
3874 * finger, then it is the trail id to reach to
3875 * that finger, else set to 0.
3876 * @param is_predecessor Are we looking for closest successor or predecessor.
3877 * @param source Source of trail setup message.
3878 * @param current_dest In case you are part of trail, then finger to which
3879 * we should forward the message. Else my own identity
3880 * @return Closest Peer for @a final_dest_finger_val
3882 static struct Closest_Peer
3883 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3884 struct GNUNET_HashCode intermediate_trail_id,
3885 unsigned int is_predecessor,
3886 struct GNUNET_PeerIdentity source,
3887 struct GNUNET_PeerIdentity *current_dest)
3889 struct Closest_Peer peer;
3891 peer = find_local_best_known_next_hop (final_dest_finger_val, is_predecessor);
3893 /* Am I just a part of a trail towards a finger (current_destination)? */
3894 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3895 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3898 struct GNUNET_PeerIdentity closest_peer;
3900 /* Select best successor among one found locally and current_destination
3901 * that we got from network.*/
3902 closest_peer = select_closest_peer (&peer.best_known_destination,
3904 final_dest_finger_val,
3907 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3908 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
3910 struct GNUNET_PeerIdentity *next_hop;
3912 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3913 GDS_ROUTING_SRC_TO_DEST);
3914 /* next_hop NULL is a valid case. This intermediate trail id is set by
3915 some other finger, and while this trail setup is in progress, that other
3916 peer might have found a better trail ,and send trail teardown message
3917 across the network. In case we got the trail teardown message first,
3918 then next_hop will be NULL. A possible solution could be to keep track
3919 * of all removed trail id, and be sure that there is no other reason . */
3920 if(NULL != next_hop)
3922 peer.next_hop = *next_hop;
3923 peer.best_known_destination = *current_dest;
3924 peer.trail_id = intermediate_trail_id;
3933 * Core handle for PeerTrailSetupMessage.
3934 * @param cls closure
3935 * @param message message
3936 * @param peer peer identity this notification is about
3937 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3940 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3941 const struct GNUNET_MessageHeader *message)
3943 const struct PeerTrailSetupMessage *trail_setup;
3944 const struct GNUNET_PeerIdentity *trail_peer_list;
3945 struct GNUNET_PeerIdentity current_dest;
3946 struct FriendInfo *target_friend;
3947 struct GNUNET_PeerIdentity source;
3948 struct GNUNET_HashCode intermediate_trail_id;
3949 struct GNUNET_HashCode trail_id;
3950 unsigned int is_predecessor;
3951 uint32_t trail_length;
3952 uint64_t final_dest_finger_val;
3956 msize = ntohs (message->size);
3957 if (msize < sizeof (struct PeerTrailSetupMessage))
3959 GNUNET_break_op (0);
3960 return GNUNET_SYSERR;
3963 trail_setup = (const struct PeerTrailSetupMessage *) message;
3964 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3965 sizeof (struct GNUNET_PeerIdentity) != 0)
3967 GNUNET_break_op (0);
3970 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3971 sizeof (struct GNUNET_PeerIdentity);
3973 GNUNET_STATISTICS_update (GDS_stats,
3975 ("# Bytes received from other peers"), msize,
3978 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3979 current_dest = trail_setup->best_known_destination;
3980 trail_id = trail_setup->trail_id;
3981 final_dest_finger_val =
3982 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3983 source = trail_setup->source_peer;
3984 is_predecessor = ntohl (trail_setup->is_predecessor);
3985 intermediate_trail_id = trail_setup->intermediate_trail_id;
3987 /* Did the friend insert its ID in the trail list? */
3988 if (trail_length > 0 &&
3989 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
3991 GNUNET_break_op (0);
3992 return GNUNET_SYSERR;
3995 /* If I was the source and got the message back, then set trail length to 0.*/
3996 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4001 /* Check if you are present in the trail seen so far? */
4002 for (i = 0; i < trail_length ; i++)
4004 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4006 /* We will add ourself later in code, if NOT destination. */
4012 /* Is my routing table full? */
4013 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4015 if (trail_length > 0)
4017 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4018 &trail_peer_list[trail_length - 1]);
4021 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4023 if(NULL == target_friend)
4025 DEBUG ("\n friend not found");
4029 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4030 my_identity, is_predecessor,
4031 trail_peer_list, trail_length,
4032 trail_id, target_friend,
4033 CONGESTION_TIMEOUT);
4037 /* Get the next hop to forward the trail setup request. */
4038 struct Closest_Peer next_peer =
4039 get_local_best_known_next_hop (final_dest_finger_val,
4040 intermediate_trail_id,
4045 /* Am I the final destination? */
4046 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4049 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4051 finger_table_add (my_identity, NULL, 0, is_predecessor,
4052 final_dest_finger_val, trail_id);
4056 if (trail_length > 0)
4058 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4059 &trail_peer_list[trail_length-1]);
4062 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4063 if (NULL == target_friend)
4065 GNUNET_break_op (0);
4066 return GNUNET_SYSERR;
4068 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4069 GDS_NEIGHBOURS_send_trail_setup_result (source,
4071 target_friend, trail_length,
4074 final_dest_finger_val,trail_id);
4076 else /* I'm not the final destination. */
4078 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4079 &next_peer.next_hop);
4080 if(NULL == target_friend)
4082 DEBUG ("\n target friend not found for peer = %s", GNUNET_i2s(&next_peer.next_hop));
4086 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4088 /* Add yourself to list of peers. */
4089 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4091 memcpy (peer_list, trail_peer_list,
4092 trail_length * sizeof (struct GNUNET_PeerIdentity));
4093 peer_list[trail_length] = my_identity;
4094 GDS_NEIGHBOURS_send_trail_setup (source,
4095 final_dest_finger_val,
4096 next_peer.best_known_destination,
4097 target_friend, trail_length + 1, peer_list,
4098 is_predecessor, trail_id,
4099 next_peer.trail_id);
4102 GDS_NEIGHBOURS_send_trail_setup (source,
4103 final_dest_finger_val,
4104 next_peer.best_known_destination,
4105 target_friend, 0, NULL,
4106 is_predecessor, trail_id,
4107 next_peer.trail_id);
4114 * Core handle for p2p trail setup result messages.
4116 * @param message message
4117 * @param peer sender of this message.
4118 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4121 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4122 const struct GNUNET_MessageHeader *message)
4124 const struct PeerTrailSetupResultMessage *trail_result;
4125 const struct GNUNET_PeerIdentity *trail_peer_list;
4126 struct GNUNET_PeerIdentity next_hop;
4127 struct FriendInfo *target_friend;
4128 struct GNUNET_PeerIdentity querying_peer;
4129 struct GNUNET_PeerIdentity finger_identity;
4130 uint32_t trail_length;
4131 uint64_t ulitmate_destination_finger_value;
4132 uint32_t is_predecessor;
4133 struct GNUNET_HashCode trail_id;
4137 msize = ntohs (message->size);
4138 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4140 GNUNET_break_op (0);
4144 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4145 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4146 sizeof (struct GNUNET_PeerIdentity) != 0)
4148 GNUNET_break_op (0);
4151 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4152 sizeof (struct GNUNET_PeerIdentity);
4154 GNUNET_STATISTICS_update (GDS_stats,
4156 ("# Bytes received from other peers"), msize,
4159 is_predecessor = ntohl (trail_result->is_predecessor);
4160 querying_peer = trail_result->querying_peer;
4161 finger_identity = trail_result->finger_identity;
4162 trail_id = trail_result->trail_id;
4163 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4164 ulitmate_destination_finger_value =
4165 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4167 /* Am I the one who initiated the query? */
4168 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4170 /* Check that you got the message from the correct peer. */
4171 if (trail_length > 0)
4173 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4178 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4181 GDS_ROUTING_add (trail_id, my_identity, *peer);
4182 finger_table_add (finger_identity, trail_peer_list, trail_length,
4183 is_predecessor, ulitmate_destination_finger_value, trail_id);
4187 /* Get my location in the trail. */
4188 my_index = search_my_index (trail_peer_list, trail_length);
4191 DEBUG ("Not found in trail\n");
4193 return GNUNET_SYSERR;
4196 if ((trail_length + 1) == my_index)
4198 DEBUG ("Found twice in trail.\n");
4200 return GNUNET_SYSERR;
4203 //TODO; Refactor code here and above to check if sender peer is correct
4206 if(trail_length > 1)
4207 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4210 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4212 next_hop = trail_result->querying_peer;
4216 if(my_index == trail_length - 1)
4219 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4224 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4226 next_hop = trail_peer_list[my_index - 1];
4229 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4230 if (NULL == target_friend)
4232 GNUNET_break_op (0);
4233 return GNUNET_SYSERR;
4235 GDS_ROUTING_add (trail_id, next_hop, *peer);
4236 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4237 target_friend, trail_length, trail_peer_list,
4239 ulitmate_destination_finger_value,
4247 * @param trail Trail to be inverted
4248 * @param trail_length Total number of peers in the trail.
4249 * @return Updated trail
4251 static struct GNUNET_PeerIdentity *
4252 invert_trail (const struct GNUNET_PeerIdentity *trail,
4253 unsigned int trail_length)
4257 struct GNUNET_PeerIdentity *inverted_trail;
4259 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4262 j = trail_length - 1;
4263 while (i < trail_length)
4265 inverted_trail[i] = trail[j];
4270 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4271 &inverted_trail[0]));
4272 return inverted_trail;
4277 * Return the shortest trail among all the trails to reach to finger from me.
4278 * @param finger Finger
4279 * @param shortest_trail_length[out] Trail length of shortest trail from me
4281 * @return Shortest trail.
4283 static struct GNUNET_PeerIdentity *
4284 get_shortest_trail (struct FingerInfo *finger,
4285 unsigned int *trail_length)
4287 struct Trail *trail;
4288 unsigned int flag = 0;
4289 unsigned int shortest_trail_index = 0;
4290 int shortest_trail_length = -1;
4291 struct Trail_Element *trail_element;
4292 struct GNUNET_PeerIdentity *trail_list;
4295 trail = GNUNET_new (struct Trail);
4297 /* Get the shortest trail to reach to current successor. */
4298 for (i = 0; i < finger->trails_count; i++)
4300 trail = &finger->trail_list[i];
4304 shortest_trail_index = i;
4305 shortest_trail_length = trail->trail_length;
4310 if (shortest_trail_length > trail->trail_length)
4312 shortest_trail_index = i;
4313 shortest_trail_length = trail->trail_length;
4318 /* Copy the shortest trail and return. */
4319 trail = &finger->trail_list[shortest_trail_index];
4320 trail_element = trail->trail_head;
4322 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4323 shortest_trail_length);
4325 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4327 trail_list[i] = trail_element->peer;
4330 GNUNET_assert(shortest_trail_length != -1);
4332 *trail_length = shortest_trail_length;
4338 * Check if trail_1 and trail_2 have any common element. If yes then join
4339 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4340 * @param trail_1 Trail from source to me, NOT including endpoints.
4341 * @param trail_1_len Total number of peers @a trail_1
4342 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4343 * @param trail_2_len Total number of peers @a trail_2
4344 * @param joined_trail_len Total number of peers in combined trail of trail_1
4346 * @return Joined trail.
4348 static struct GNUNET_PeerIdentity *
4349 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4350 unsigned int trail_1_len,
4351 struct GNUNET_PeerIdentity *trail_2,
4352 unsigned int trail_2_len,
4353 unsigned int *joined_trail_len)
4355 struct GNUNET_PeerIdentity *joined_trail;
4360 for (i = 0; i < trail_1_len; i++)
4362 for (j = 0; j < trail_2_len; j++)
4364 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4367 *joined_trail_len = i + (trail_2_len - j);
4368 joined_trail = GNUNET_malloc (*joined_trail_len *
4369 sizeof(struct GNUNET_PeerIdentity));
4372 /* Copy all the elements from 0 to i into joined_trail. */
4373 for(k = 0; k < ( i+1); k++)
4375 joined_trail[k] = trail_1[k];
4378 /* Increment j as entry stored is same as entry stored at i*/
4381 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4382 while(k <= (*joined_trail_len - 1))
4384 joined_trail[k] = trail_2[j];
4389 return joined_trail;
4393 /* Here you should join the trails. */
4394 *joined_trail_len = trail_1_len + trail_2_len + 1;
4395 joined_trail = GNUNET_malloc (*joined_trail_len *
4396 sizeof(struct GNUNET_PeerIdentity));
4399 for(i = 0; i < trail_1_len;i++)
4401 joined_trail[i] = trail_1[i];
4404 joined_trail[i] = my_identity;
4407 for (j = 0; i < *joined_trail_len; i++,j++)
4409 joined_trail[i] = trail_2[j];
4412 return joined_trail;
4417 * Return the trail from source to my current predecessor. Check if source
4418 * is already part of the this trail, if yes then return the shorten trail.
4419 * @param current_trail Trail from source to me, NOT including the endpoints.
4420 * @param current_trail_length Number of peers in @a current_trail.
4421 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4422 * source to my predecessor, NOT including
4424 * @return Trail from source to my predecessor.
4426 static struct GNUNET_PeerIdentity *
4427 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4428 const struct GNUNET_PeerIdentity *trail_src_to_me,
4429 unsigned int trail_src_to_me_len,
4430 unsigned int *trail_src_to_curr_pred_length)
4432 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4433 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4434 unsigned int trail_me_to_curr_pred_length;
4435 struct FingerInfo *current_predecessor;
4439 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4441 /* Check if trail_src_to_me contains current_predecessor. */
4442 for (i = 0; i < trail_src_to_me_len; i++)
4444 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4445 ¤t_predecessor->finger_identity))
4449 *trail_src_to_curr_pred_length = i;
4454 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4455 sizeof(struct GNUNET_PeerIdentity));
4456 for(j = 0; j < i;j++)
4457 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4458 return trail_src_to_curr_pred;
4462 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4463 &trail_me_to_curr_pred_length);
4465 /* Check if trail contains the source_peer. */
4466 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4468 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4469 &trail_me_to_curr_pred[i]))
4472 /* Source is NOT part of trail. */
4475 /* Source is the last element in the trail to reach to my pred.
4476 Source is direct friend of the pred. */
4477 if (trail_me_to_curr_pred_length == i)
4479 *trail_src_to_curr_pred_length = 0;
4483 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4484 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4485 *trail_src_to_curr_pred_length);
4487 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4489 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4491 GNUNET_free_non_null(trail_me_to_curr_pred);
4492 return trail_src_to_curr_pred;
4496 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4497 trail_src_to_me_len,
4498 trail_me_to_curr_pred,
4499 trail_me_to_curr_pred_length,
4501 *trail_src_to_curr_pred_length = len;
4502 GNUNET_free_non_null(trail_me_to_curr_pred);
4503 return trail_src_to_curr_pred;
4508 * Add finger as your predecessor. To add, first generate a new trail id, invert
4509 * the trail to get the trail from me to finger, add an entry in your routing
4510 * table, send add trail message to peers which are part of trail from me to
4511 * finger and add finger in finger table.
4514 * @param trail_length
4517 update_predecessor (struct GNUNET_PeerIdentity finger,
4518 struct GNUNET_PeerIdentity *trail,
4519 unsigned int trail_length)
4521 struct GNUNET_HashCode trail_to_new_predecessor_id;
4522 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4523 struct FriendInfo *target_friend;
4525 /* Generate trail id for trail from me to new predecessor = finger. */
4526 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4527 &trail_to_new_predecessor_id,
4528 sizeof (trail_to_new_predecessor_id));
4530 if (0 == trail_length)
4532 trail_to_new_predecessor = NULL;
4533 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4534 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger);
4535 if (NULL == target_friend)
4543 /* Invert the trail to get the trail from me to finger, NOT including the
4545 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4546 &trail[trail_length-1]));
4547 trail_to_new_predecessor = invert_trail (trail, trail_length);
4549 /* Add an entry in your routing table. */
4550 GDS_ROUTING_add (trail_to_new_predecessor_id,
4552 trail_to_new_predecessor[0]);
4554 GNUNET_assert (NULL != (target_friend =
4555 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4556 &trail_to_new_predecessor[0])));
4559 /* Add entry in routing table of all peers that are part of trail from me
4560 to finger, including finger. */
4561 GDS_NEIGHBOURS_send_add_trail (my_identity,
4563 trail_to_new_predecessor_id,
4564 trail_to_new_predecessor,
4568 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4569 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4570 GNUNET_free_non_null(trail_to_new_predecessor);
4575 * Check if you already have a predecessor. If not then add finger as your
4576 * predecessor. If you have predecessor, then compare two peer identites.
4577 * If finger is correct predecessor, then remove the old entry, add finger in
4578 * finger table and send add_trail message to add the trail in the routing
4579 * table of all peers which are part of trail to reach from me to finger.
4580 * @param finger New peer which may be our predecessor.
4581 * @param trail List of peers to reach from @finger to me.
4582 * @param trail_length Total number of peer in @a trail.
4585 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4586 struct GNUNET_PeerIdentity *trail,
4587 unsigned int trail_length)
4589 struct FingerInfo *current_predecessor;
4590 struct GNUNET_PeerIdentity closest_peer;
4591 uint64_t predecessor_value;
4592 unsigned int is_predecessor = 1;
4594 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4595 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4597 /* No predecessor. Add finger as your predecessor. */
4598 if (GNUNET_NO == current_predecessor->is_present)
4600 update_predecessor (finger, trail, trail_length);
4604 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4610 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4611 closest_peer = select_closest_peer (&finger,
4612 ¤t_predecessor->finger_identity,
4613 predecessor_value, is_predecessor);
4615 /* Finger is the closest predecessor. Remove the existing one and add the new
4617 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4619 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4620 update_predecessor (finger, trail, trail_length);
4628 * Core handle for p2p verify successor messages.
4629 * @param cls closure
4630 * @param message message
4631 * @param peer peer identity this notification is about
4632 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4635 handle_dht_p2p_verify_successor(void *cls,
4636 const struct GNUNET_PeerIdentity *peer,
4637 const struct GNUNET_MessageHeader *message)
4639 const struct PeerVerifySuccessorMessage *vsm;
4640 struct GNUNET_HashCode trail_id;
4641 struct GNUNET_PeerIdentity successor;
4642 struct GNUNET_PeerIdentity source_peer;
4643 struct GNUNET_PeerIdentity *trail;
4644 struct GNUNET_PeerIdentity *next_hop;
4645 struct FingerInfo current_predecessor;
4646 struct FriendInfo *target_friend;
4647 unsigned int trail_src_to_curr_pred_len = 0;
4648 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4649 unsigned int trail_length;
4652 msize = ntohs (message->size);
4654 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4656 GNUNET_break_op (0);
4660 vsm = (const struct PeerVerifySuccessorMessage *) message;
4661 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4662 sizeof (struct GNUNET_PeerIdentity);
4663 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4664 sizeof (struct GNUNET_PeerIdentity) != 0)
4666 GNUNET_break_op (0);
4670 GNUNET_STATISTICS_update (GDS_stats,
4672 ("# Bytes received from other peers"), msize,
4675 trail_id = vsm->trail_id;
4676 source_peer = vsm->source_peer;
4677 successor = vsm->successor;
4678 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4680 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4682 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4684 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4685 if (NULL == next_hop)
4687 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
4688 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
4689 GNUNET_break_op (0);
4693 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4695 if(NULL == target_friend)
4700 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4701 trail_id, trail, trail_length,
4706 /* I am the destination of this message. */
4708 /* Check if the source_peer could be our predecessor and if yes then update
4710 compare_and_update_predecessor (source_peer, trail, trail_length);
4711 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4713 /* Is source of this message NOT my predecessor. */
4714 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4717 trail_src_to_curr_pred =
4718 get_trail_src_to_curr_pred (source_peer,
4721 &trail_src_to_curr_pred_len);
4725 trail_src_to_curr_pred_len = trail_length;
4728 trail_src_to_curr_pred =
4729 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4730 *trail_src_to_curr_pred_len);
4731 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4733 trail_src_to_curr_pred[i] = trail[i];
4737 GNUNET_assert (NULL !=
4739 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4740 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4741 current_predecessor.finger_identity,
4742 trail_id, trail_src_to_curr_pred,
4743 trail_src_to_curr_pred_len,
4744 GDS_ROUTING_DEST_TO_SRC,
4746 GNUNET_free_non_null(trail_src_to_curr_pred);
4752 * If the trail from me to my probable successor contains a friend not
4753 * at index 0, then we can shorten the trail.
4754 * @param probable_successor Peer which is our probable successor
4755 * @param trail_me_to_probable_successor Peers in path from me to my probable
4756 * successor, NOT including the endpoints.
4757 * @param trail_me_to_probable_successor_len Total number of peers in
4758 * @a trail_me_to_probable_succesor.
4759 * @return Updated trail, if any friend found.
4760 * Else the trail_me_to_probable_successor.
4762 struct GNUNET_PeerIdentity *
4763 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4764 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4765 unsigned int trail_me_to_probable_successor_len,
4766 unsigned int *trail_to_new_successor_length)
4770 struct GNUNET_PeerIdentity *trail_to_new_successor;
4772 /* Probable successor is a friend */
4773 /* SUPUS: Here should I worry about friend,*/
4774 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4775 &probable_successor))
4777 trail_to_new_successor = NULL;
4778 *trail_to_new_successor_length = 0;
4779 return trail_to_new_successor;
4782 /* Is there any friend of yours in this trail. */
4783 if(trail_me_to_probable_successor_len > 1)
4785 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4787 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4788 &trail_me_to_probable_successor[i]))
4791 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4792 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4793 *trail_to_new_successor_length);
4796 for(j = 0; j < *trail_to_new_successor_length; i++,j++)
4798 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4801 return trail_to_new_successor;
4805 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4806 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4811 * Check if the peer which sent us verify successor result message is still ours
4812 * successor or not. If not, then compare existing successor and probable successor.
4813 * In case probable successor is the correct successor, remove the existing
4814 * successor. Add probable successor as new successor. Send notify new successor
4815 * message to new successor.
4816 * @param curr_succ Peer to which we sent the verify successor message. It may
4817 * or may not be our real current successor, as we may have few iterations of
4818 * find finger trail task.
4819 * @param probable_successor Peer which should be our successor accroding to @a
4821 * @param trail List of peers to reach from me to @a probable successor, NOT including
4823 * @param trail_length Total number of peers in @a trail.
4826 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4827 struct GNUNET_PeerIdentity probable_successor,
4828 const struct GNUNET_PeerIdentity *trail,
4829 unsigned int trail_length)
4831 struct FingerInfo *current_successor;
4832 struct GNUNET_PeerIdentity closest_peer;
4833 struct GNUNET_HashCode trail_id;
4834 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4835 struct FriendInfo *target_friend;
4836 unsigned int trail_me_to_probable_succ_len;
4837 unsigned int is_predecessor = 0;
4838 uint64_t successor_value;
4840 current_successor = &finger_table[0];
4841 successor_value = compute_finger_identity_value(0);
4843 /* If probable successor is same as current_successor, do nothing. */
4844 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
4845 ¤t_successor->finger_identity))
4848 closest_peer = select_closest_peer (&probable_successor,
4849 ¤t_successor->finger_identity,
4850 successor_value, is_predecessor);
4852 /* If the current_successor in the finger table is closest, then do nothing. */
4853 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
4854 ¤t_successor->finger_identity))
4856 //FIXME: Is this a good place to return the stats.
4857 if ((NULL != GDS_stats))
4863 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4864 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4865 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4866 GNUNET_free (my_id_str);
4867 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4873 /* Probable successor is the closest peer.*/
4874 if(trail_length > 0)
4876 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4881 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4882 &probable_successor));
4885 trail_me_to_probable_succ_len = 0;
4886 trail_me_to_probable_succ =
4887 check_trail_me_to_probable_succ (probable_successor,
4888 trail, trail_length,
4889 &trail_me_to_probable_succ_len);
4891 /* Remove the existing successor. */
4892 remove_existing_finger (current_successor, 0);
4893 /* Generate a new trail id to reach to your new successor. */
4894 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4895 &trail_id, sizeof (trail_id));
4897 if (trail_me_to_probable_succ_len > 0)
4899 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4900 GNUNET_assert (NULL !=
4902 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4903 &trail_me_to_probable_succ[0])));
4907 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4908 GNUNET_assert (NULL !=
4910 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4911 &probable_successor)));
4914 add_new_finger (probable_successor, trail_me_to_probable_succ,
4915 trail_me_to_probable_succ_len, trail_id, 0);
4917 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4918 trail_me_to_probable_succ,
4919 trail_me_to_probable_succ_len,
4927 * Core handle for p2p verify successor result messages.
4928 * @param cls closure
4929 * @param message message
4930 * @param peer peer identity this notification is about
4931 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4934 handle_dht_p2p_verify_successor_result(void *cls,
4935 const struct GNUNET_PeerIdentity *peer,
4936 const struct GNUNET_MessageHeader *message)
4938 const struct PeerVerifySuccessorResultMessage *vsrm;
4939 enum GDS_ROUTING_trail_direction trail_direction;
4940 struct GNUNET_PeerIdentity querying_peer;
4941 struct GNUNET_HashCode trail_id;
4942 struct GNUNET_PeerIdentity *next_hop;
4943 struct FriendInfo *target_friend;
4944 struct GNUNET_PeerIdentity probable_successor;
4945 struct GNUNET_PeerIdentity current_successor;
4946 const struct GNUNET_PeerIdentity *trail;
4947 unsigned int trail_length;
4950 msize = ntohs (message->size);
4951 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4953 GNUNET_break_op (0);
4957 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4958 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4959 sizeof (struct GNUNET_PeerIdentity) != 0)
4961 GNUNET_break_op (0);
4964 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4965 sizeof (struct GNUNET_PeerIdentity);
4967 GNUNET_STATISTICS_update (GDS_stats,
4969 ("# Bytes received from other peers"), msize,
4972 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4973 querying_peer = vsrm->querying_peer;
4974 trail_direction = ntohl (vsrm->trail_direction);
4975 trail_id = vsrm->trail_id;
4976 probable_successor = vsrm->probable_successor;
4977 current_successor = vsrm->current_successor;
4979 /* I am the querying_peer. */
4980 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4982 /* As we completed one round of verify successor, we can do backoff. */
4983 // verify_successor_next_send_time =
4984 // GNUNET_TIME_STD_BACKOFF(verify_successor_next_send_time);
4985 compare_and_update_successor (current_successor,
4986 probable_successor, trail, trail_length);
4990 /*If you are not the querying peer then pass on the message */
4991 if(NULL == (next_hop =
4992 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
4994 //FIXME: Urgent in what case this is possible?
4995 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
4996 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5000 if (NULL == (target_friend =
5001 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5006 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5007 vsrm->current_successor,
5008 probable_successor, trail_id,
5011 trail_direction, target_friend);
5017 * Core handle for p2p notify new successor messages.
5018 * @param cls closure
5019 * @param message message
5020 * @param peer peer identity this notification is about
5021 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5024 handle_dht_p2p_notify_new_successor(void *cls,
5025 const struct GNUNET_PeerIdentity *peer,
5026 const struct GNUNET_MessageHeader *message)
5028 const struct PeerNotifyNewSuccessorMessage *nsm;
5029 struct GNUNET_PeerIdentity *trail;
5030 struct GNUNET_PeerIdentity source;
5031 struct GNUNET_PeerIdentity new_successor;
5032 struct GNUNET_HashCode trail_id;
5033 struct GNUNET_PeerIdentity next_hop;
5034 struct FriendInfo *target_friend;
5037 uint32_t trail_length;
5039 msize = ntohs (message->size);
5040 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5042 GNUNET_break_op (0);
5045 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5046 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5047 sizeof (struct GNUNET_PeerIdentity) != 0)
5049 GNUNET_break_op (0);
5052 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5053 sizeof (struct GNUNET_PeerIdentity);
5054 GNUNET_STATISTICS_update (GDS_stats,
5056 ("# Bytes received from other peers"), msize,
5059 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5060 source = nsm->source_peer;
5061 new_successor = nsm->new_successor;
5062 trail_id = nsm->trail_id;
5064 /* I am the new_successor to source_peer. */
5065 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5067 if(trail_length > 0)
5068 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5071 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5073 compare_and_update_predecessor (source, trail, trail_length);
5077 GNUNET_assert(trail_length > 0);
5078 /* I am part of trail to reach to successor. */
5079 my_index = search_my_index (trail, trail_length);
5082 DEBUG ("No entry found in trail\n");
5083 GNUNET_break_op (0);
5084 return GNUNET_SYSERR;
5086 if((trail_length + 1) == my_index)
5088 DEBUG ("Found twice in trail.\n");
5089 GNUNET_break_op (0);
5090 return GNUNET_SYSERR;
5092 if ((trail_length-1) == my_index)
5093 next_hop = new_successor;
5095 next_hop = trail[my_index + 1];
5096 /* Add an entry in routing table for trail from source to its new successor. */
5097 if (GNUNET_SYSERR == GDS_ROUTING_add (trail_id, *peer, next_hop))
5103 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
5104 if (NULL == target_friend)
5109 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5111 trail_id, target_friend);
5118 * Core handler for P2P trail rejection message
5119 * @param cls closure
5120 * @param message message
5121 * @param peer peer identity this notification is about
5122 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5125 handle_dht_p2p_trail_setup_rejection (void *cls,
5126 const struct GNUNET_PeerIdentity *peer,
5127 const struct GNUNET_MessageHeader *message)
5129 const struct PeerTrailRejectionMessage *trail_rejection;
5130 unsigned int trail_length;
5131 const struct GNUNET_PeerIdentity *trail_peer_list;
5132 struct FriendInfo *target_friend;
5133 struct GNUNET_TIME_Relative congestion_timeout;
5134 struct GNUNET_HashCode trail_id;
5135 struct GNUNET_PeerIdentity next_peer;
5136 struct GNUNET_PeerIdentity source;
5137 uint64_t ultimate_destination_finger_value;
5138 unsigned int is_predecessor;
5141 msize = ntohs (message->size);
5142 if (msize < sizeof (struct PeerTrailRejectionMessage))
5144 GNUNET_break_op (0);
5147 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5148 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5149 sizeof (struct GNUNET_PeerIdentity) != 0)
5151 GNUNET_break_op (0);
5154 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5155 sizeof (struct GNUNET_PeerIdentity);
5156 GNUNET_STATISTICS_update (GDS_stats,
5158 ("# Bytes received from other peers"), msize,
5161 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5162 is_predecessor = ntohl (trail_rejection->is_predecessor);
5163 congestion_timeout = trail_rejection->congestion_time;
5164 source = trail_rejection->source_peer;
5165 trail_id = trail_rejection->trail_id;
5166 ultimate_destination_finger_value =
5167 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5168 /* First set the congestion time of the friend that sent you this message. */
5169 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5170 if (NULL == target_friend)
5172 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5176 target_friend->congestion_timestamp =
5177 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5178 congestion_timeout);
5180 /* I am the source peer which wants to setup the trail. Do nothing.
5181 * send_find_finger_trail_task is scheduled periodically.*/
5182 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5185 /* If I am congested then pass this message to peer before me in trail. */
5186 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5188 /* First remove yourself from the trail. */
5189 unsigned int new_trail_length = trail_length - 1;
5190 struct GNUNET_PeerIdentity trail[new_trail_length];
5192 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5193 if (0 == trail_length)
5196 next_peer = trail[new_trail_length-1];
5199 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5200 if (NULL == target_friend)
5202 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5206 GDS_NEIGHBOURS_send_trail_rejection (source,
5207 ultimate_destination_finger_value,
5208 my_identity, is_predecessor,
5209 trail, new_trail_length, trail_id,
5210 target_friend, CONGESTION_TIMEOUT);
5214 struct Closest_Peer successor;
5215 successor = find_local_best_known_next_hop (ultimate_destination_finger_value, is_predecessor);
5217 /* Am I the final destination? */
5218 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5221 /*Here you are already part of trail. Copy the trail removing yourself. */
5222 unsigned int new_trail_length = trail_length - 1;
5223 struct GNUNET_PeerIdentity trail[new_trail_length];
5225 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5227 if (0 == new_trail_length)
5231 next_peer = trail[new_trail_length-1];
5234 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5236 if (NULL == target_friend)
5238 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5242 GDS_NEIGHBOURS_send_trail_setup_result (source,
5244 target_friend, new_trail_length,
5247 ultimate_destination_finger_value,
5252 /* Here I was already part of trail. So no need to add. */
5254 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5255 &successor.next_hop);
5256 if (NULL == target_friend)
5258 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5263 GDS_NEIGHBOURS_send_trail_setup (source,
5264 ultimate_destination_finger_value,
5265 successor.best_known_destination,
5266 target_friend, trail_length, trail_peer_list,
5267 is_predecessor, trail_id,
5268 successor.trail_id);
5275 * Core handler for trail teardown message.
5276 * @param cls closure
5277 * @param message message
5278 * @param peer sender of this messsage.
5279 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5282 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5283 const struct GNUNET_MessageHeader *message)
5285 const struct PeerTrailTearDownMessage *trail_teardown;
5286 enum GDS_ROUTING_trail_direction trail_direction;
5287 struct GNUNET_HashCode trail_id;
5288 struct GNUNET_PeerIdentity *next_hop;
5291 msize = ntohs (message->size);
5293 /* Here we pass only the trail id. */
5294 if (msize != sizeof (struct PeerTrailTearDownMessage))
5296 GNUNET_break_op (0);
5300 GNUNET_STATISTICS_update (GDS_stats,
5302 ("# Bytes received from other peers"), msize,
5305 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5306 trail_direction = ntohl (trail_teardown->trail_direction);
5307 trail_id = trail_teardown->trail_id;
5309 /* Check if peer is the real peer from which we should get this message.*/
5310 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5312 GNUNET_assert (NULL != (prev_hop =
5313 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5314 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5317 return GNUNET_SYSERR;
5321 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5322 if (NULL == next_hop)
5324 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5325 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5327 return GNUNET_SYSERR;
5330 /* I am the next hop, which means I am the final destination. */
5331 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5333 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5338 /* If not final destination, then send a trail teardown message to next hop.*/
5339 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5340 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5341 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5349 * Core handle for p2p add trail message.
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_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5357 const struct GNUNET_MessageHeader *message)
5359 const struct PeerAddTrailMessage *add_trail;
5360 const struct GNUNET_PeerIdentity *trail;
5361 struct GNUNET_HashCode trail_id;
5362 struct GNUNET_PeerIdentity destination_peer;
5363 struct GNUNET_PeerIdentity source_peer;
5364 struct GNUNET_PeerIdentity next_hop;
5365 unsigned int trail_length;
5366 unsigned int my_index;
5369 msize = ntohs (message->size);
5370 /* In this message we pass the whole trail from source to destination as we
5371 * are adding that trail.*/
5372 //FIXME: failed when run with 1000 pears. check why.
5373 if (msize < sizeof (struct PeerAddTrailMessage))
5375 GNUNET_break_op (0);
5379 add_trail = (const struct PeerAddTrailMessage *) message;
5380 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5381 sizeof (struct GNUNET_PeerIdentity);
5382 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5383 sizeof (struct GNUNET_PeerIdentity) != 0)
5385 GNUNET_break_op (0);
5389 GNUNET_STATISTICS_update (GDS_stats,
5391 ("# Bytes received from other peers"), msize,
5394 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5395 destination_peer = add_trail->destination_peer;
5396 source_peer = add_trail->source_peer;
5397 trail_id = add_trail->trail_id;
5399 //FIXME: add a check that sender peer is not malicious. Make it a generic
5400 // function so that it can be used in all other functions where we need the
5401 // same functionality.
5403 /* I am not the destination of the trail. */
5404 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5406 struct FriendInfo *target_friend;
5408 /* Get my location in the trail. */
5409 my_index = search_my_index (trail, trail_length);
5412 GNUNET_break_op (0);
5413 return GNUNET_SYSERR;
5415 if((trail_length + 1) == my_index)
5417 DEBUG ("Found twice in trail.\n");
5418 GNUNET_break_op (0);
5419 return GNUNET_SYSERR;
5421 if ((trail_length - 1) == my_index)
5423 next_hop = destination_peer;
5427 next_hop = trail[my_index + 1];
5429 /* Add in your routing table. */
5430 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5431 GNUNET_assert (NULL !=
5433 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5434 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5435 trail, trail_length, target_friend);
5438 /* I am the destination. Add an entry in routing table. */
5439 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5445 * Free the finger trail in which the first friend to reach to a finger is
5446 * disconnected_friend. Also remove entry from routing table for that particular
5448 * @param disconnected_friend PeerIdentity of friend which got disconnected
5449 * @param remove_finger Finger whose trail we need to check if it has
5450 * disconnected_friend as the first hop.
5451 * @return Total number of trails in which disconnected_friend was the first
5455 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5456 struct FingerInfo *finger)
5458 struct GNUNET_PeerIdentity *next_hop;
5459 struct FriendInfo *remove_friend;
5460 struct Trail *current_trail;
5461 unsigned int matching_trails_count = 0;
5464 /* Iterate over all the trails of finger. */
5465 for (i = 0; i < finger->trails_count; i++)
5467 current_trail = &finger->trail_list[i];
5468 if (GNUNET_NO == current_trail->is_present)
5471 /* First friend to reach to finger is disconnected_peer. */
5472 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5473 disconnected_friend))
5476 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5477 disconnected_friend);
5478 GNUNET_assert (NULL != remove_friend);
5479 next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id,
5480 GDS_ROUTING_SRC_TO_DEST);
5482 /* Here it may happen that as all the peers got disconnected, the entry in
5483 routing table for that particular trail has been removed, because the
5484 previously disconnected peer was either a next hop or prev hop of that
5486 if (NULL != next_hop)
5488 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5490 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id));
5492 matching_trails_count++;
5493 free_trail (current_trail);
5494 current_trail->is_present = GNUNET_NO;
5497 return matching_trails_count;
5502 * Iterate over finger_table entries.
5503 * 0. Ignore finger which is my_identity or if no valid entry present at
5504 * that finger index.
5505 * 1. If disconnected_friend is a finger, then remove the routing entry from
5506 your own table. Free the trail.
5507 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5508 * 2.1 Remove all the trails and entry from routing table in which disconnected
5509 * friend is the first friend in the trail. If disconnected_friend is the
5510 * first friend in all the trails to reach finger, then remove the finger.
5511 * @param disconnected_friend Peer identity of friend which got disconnected.
5514 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5516 struct FingerInfo *current_finger;
5517 int removed_trails_count;
5520 /* Iterate over finger table entries. */
5521 for (i = 0; i < MAX_FINGERS; i++)
5523 current_finger = &finger_table[i];
5525 /* No finger stored at this trail index or I am the finger. */
5526 if ((GNUNET_NO == current_finger->is_present) ||
5527 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5531 /* Is disconnected_peer a finger? */
5532 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5533 ¤t_finger->finger_identity))
5535 remove_existing_finger (current_finger, i);
5538 /* If finger is a friend but not disconnected_friend, then continue. */
5539 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5540 ¤t_finger->finger_identity))
5543 /* Iterate over the list of trails to reach remove_finger. Check if
5544 * disconnected_friend is the first friend in any of the trail. */
5545 removed_trails_count = remove_matching_trails (disconnected_peer,
5547 current_finger->trails_count =
5548 current_finger->trails_count - removed_trails_count;
5549 if (0 == current_finger->trails_count)
5551 current_finger->is_present = GNUNET_NO;
5552 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5559 * Method called whenever a peer disconnects.
5561 * @param cls closure
5562 * @param peer peer identity this notification is about
5565 handle_core_disconnect (void *cls,
5566 const struct GNUNET_PeerIdentity *peer)
5568 struct FriendInfo *remove_friend;
5569 struct P2PPendingMessage *pos;
5570 unsigned int discarded;
5572 /* If disconnected to own identity, then return. */
5573 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5576 if(NULL == (remove_friend =
5577 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
5579 DEBUG("\n friend already disconnected.");
5583 remove_matching_fingers (peer);
5584 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5585 GNUNET_assert (GNUNET_YES ==
5586 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5590 /* Remove all the messages queued in pending list of this peer is discarded.*/
5591 if (remove_friend->th != NULL)
5593 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
5594 remove_friend->th = NULL;
5598 while (NULL != (pos = remove_friend->head))
5600 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
5605 GNUNET_STATISTICS_update (GDS_stats,
5607 ("# Queued messages discarded (peer disconnected)"),
5608 discarded, GNUNET_NO);
5609 //GNUNET_free (remove_friend);
5611 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5614 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5616 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5617 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5625 * Method called whenever a peer connects.
5627 * @param cls closure
5628 * @param peer_identity peer identity this notification is about
5631 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5633 struct FriendInfo *friend;
5635 /* Check for connect to self message */
5636 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5639 /* If peer already exists in our friend_peermap, then exit. */
5640 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5647 friend = GNUNET_new (struct FriendInfo);
5648 friend->id = *peer_identity;
5650 GNUNET_assert (GNUNET_OK ==
5651 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5652 peer_identity, friend,
5653 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5655 /* FIXME: now we are not making a distinction between fingers which are friends
5656 * also.But later, we should add a congestion timestamp on the friend, so that it is
5657 * selected after some time out. This is to ensure that both peers have added
5658 * each other as their friend. */
5659 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5660 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5662 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5668 * To be called on core init/fail.
5670 * @param cls service closure
5671 * @param identity the public identity of this peer
5674 core_init (void *cls,
5675 const struct GNUNET_PeerIdentity *identity)
5677 my_identity = *identity;
5682 * Initialize finger table entries.
5685 finger_table_init ()
5687 memset (&finger_table, 0, sizeof (finger_table));
5692 * Initialize neighbours subsystem.
5693 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5696 GDS_NEIGHBOURS_init (void)
5698 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5699 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5700 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5701 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5702 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5703 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5704 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5705 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5706 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5707 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5708 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5709 sizeof (struct PeerTrailTearDownMessage)},
5710 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5714 #if ENABLE_MALICIOUS
5719 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5720 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5721 GNUNET_NO, core_handlers);
5723 if (NULL == core_api)
5724 return GNUNET_SYSERR;
5726 //TODO: check size of this peer map?
5727 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5728 finger_table_init ();
5730 find_finger_trail_task_next_send_time.rel_value_us =
5731 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5732 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5733 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5735 verify_successor_next_send_time.rel_value_us =
5736 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5737 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5738 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5745 * Free the memory held up by trails of a finger.
5748 delete_finger_table_entries()
5753 for(i = 0; i < MAX_FINGERS; i++)
5755 if(GNUNET_YES == finger_table[i].is_present)
5757 for(j = 0; j < finger_table[i].trails_count; j++)
5758 free_trail(&finger_table[i].trail_list[i]);
5765 * Shutdown neighbours subsystem.
5768 GDS_NEIGHBOURS_done (void)
5770 if (NULL == core_api)
5773 GNUNET_CORE_disconnect (core_api);
5776 delete_finger_table_entries();
5777 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5778 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5779 friend_peermap = NULL;
5781 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5784 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5785 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5788 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5790 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5791 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5799 * @return my identity
5801 struct GNUNET_PeerIdentity
5802 GDS_NEIGHBOURS_get_my_id (void)
5807 /* end of gnunet-service-xdht_neighbours.c */