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_MILLISECONDS, 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;
805 * Data structure to store the trail chosen to reach to finger.
807 struct Selected_Finger_Trail
810 * First friend in the trail to reach finger.
812 struct FriendInfo friend;
815 * Identifier of this trail.
817 struct GNUNET_HashCode trail_id;
820 * Total number of peers in this trail.
822 unsigned int trail_length;
826 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
827 * get our first friend.
829 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
832 * Task that sends verify successor message. This task is started when we get
833 * our successor for the first time.
835 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_task;
838 * Identity of this peer.
840 static struct GNUNET_PeerIdentity my_identity;
843 * Peer map of all the friends of a peer
845 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
848 * Array of all the fingers.
850 static struct FingerInfo finger_table [MAX_FINGERS];
855 static struct GNUNET_CORE_Handle *core_api;
858 * Handle for the statistics service.
860 //extern struct GNUNET_STATISTICS_Handle *GDS_stats;
863 * The current finger index that we have want to find trail to. We start the
864 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
865 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
866 * we reset this index to 0.
868 static unsigned int current_search_finger_index;
871 * Should we store our topology predecessor and successor IDs into statistics?
873 unsigned int track_topology;
876 * Should I be a malicious peer and drop the PUT/GET packets?
877 * if 0 then NOT malicious.
879 unsigned int act_malicious;
882 * Time duration to schedule find finger trail task.
884 static struct GNUNET_TIME_Relative find_finger_trail_task_next_send_time;
887 * Time duration to schedule verify successor task.
889 static struct GNUNET_TIME_Relative verify_successor_next_send_time;
892 * Called when core is ready to send a message we asked for
893 * out to the destination.
895 * @param cls the 'struct FriendInfo' of the target friend
896 * @param size number of bytes available in buf
897 * @param buf where the callee should write the message
898 * @return number of bytes written to buf
901 core_transmit_notify (void *cls, size_t size, void *buf)
903 struct FriendInfo *peer = cls;
905 struct P2PPendingMessage *pending;
910 while ((NULL != (pending = peer->head)) &&
911 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
913 peer->pending_count--;
914 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
915 GNUNET_free (pending);
919 /* no messages pending */
925 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
926 GNUNET_CORE_PRIO_BEST_EFFORT,
927 GNUNET_TIME_absolute_get_remaining
928 (pending->timeout), &peer->id,
929 ntohs (pending->msg->size),
930 &core_transmit_notify, peer);
931 GNUNET_break (NULL != peer->th);
935 while ((NULL != (pending = peer->head)) &&
936 (size - off >= (msize = ntohs (pending->msg->size))))
938 GNUNET_STATISTICS_update (GDS_stats,
940 ("# Bytes transmitted to other peers"), msize,
942 memcpy (&cbuf[off], pending->msg, msize);
944 peer->pending_count--;
945 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
946 GNUNET_free (pending);
948 if (peer->head != NULL)
951 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
952 GNUNET_CORE_PRIO_BEST_EFFORT,
953 GNUNET_TIME_absolute_get_remaining
954 (pending->timeout), &peer->id, msize,
955 &core_transmit_notify, peer);
956 GNUNET_break (NULL != peer->th);
963 * Transmit all messages in the friend's message queue.
965 * @param peer message queue to process
968 process_friend_queue (struct FriendInfo *peer)
970 struct P2PPendingMessage *pending;
972 if (NULL == (pending = peer->head))
976 if (NULL != peer->th)
982 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
984 GNUNET_TIME_absolute_get_remaining
985 (pending->timeout), &peer->id,
986 ntohs (pending->msg->size),
987 &core_transmit_notify, peer);
988 GNUNET_break (NULL != peer->th);
994 * Set the ENABLE_MALICIOUS value to malicious.
998 GDS_NEIGHBOURS_act_malicious (unsigned int malicious)
1000 act_malicious = malicious;
1005 * Construct a trail setup message and forward it to target_friend
1006 * @param source_peer Peer which wants to setup the trail
1007 * @param ultimate_destination_finger_value Peer identity closest to this value
1008 * will be finger to @a source_peer
1009 * @param best_known_destination Best known destination (could be finger or friend)
1010 * which should get this message. In case it is
1011 * friend, then it is same as target_friend
1012 * @param target_friend Friend to which message is forwarded now.
1013 * @param trail_length Total number of peers in trail setup so far.
1014 * @param trail_peer_list Trail setup so far
1015 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1016 * @param trail_id Unique identifier for the trail we are trying to setup.
1017 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1018 * best_known_destination when its a finger. If not
1019 * used then set to 0.
1022 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1023 uint64_t ultimate_destination_finger_value,
1024 struct GNUNET_PeerIdentity best_known_destination,
1025 struct FriendInfo *target_friend,
1026 unsigned int trail_length,
1027 const struct GNUNET_PeerIdentity *trail_peer_list,
1028 unsigned int is_predecessor,
1029 struct GNUNET_HashCode trail_id,
1030 struct GNUNET_HashCode intermediate_trail_id)
1032 struct P2PPendingMessage *pending;
1033 struct PeerTrailSetupMessage *tsm;
1034 struct GNUNET_PeerIdentity *peer_list;
1037 msize = sizeof (struct PeerTrailSetupMessage) +
1038 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1040 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1046 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1048 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1052 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1053 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1054 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1055 pending->msg = &(tsm->header);
1056 tsm->header.size = htons (msize);
1057 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1058 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1059 tsm->source_peer = source_peer;
1060 tsm->best_known_destination = best_known_destination;
1061 tsm->is_predecessor = htonl (is_predecessor);
1062 tsm->trail_id = trail_id;
1063 tsm->intermediate_trail_id = intermediate_trail_id;
1065 if (trail_length > 0)
1067 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1068 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1071 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1072 target_friend->pending_count++;
1073 process_friend_queue (target_friend);
1078 * Construct a trail setup result message and forward it to target friend.
1079 * @param querying_peer Peer which sent the trail setup request and should get
1081 * @param Finger Peer to which the trail has been setup to.
1082 * @param target_friend Friend to which this message should be forwarded.
1083 * @param trail_length Numbers of peers in the trail.
1084 * @param trail_peer_list Peers which are part of the trail from
1085 * querying_peer to Finger, NOT including them.
1086 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1087 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1089 * @param trail_id Unique identifier of the trail.
1092 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1093 struct GNUNET_PeerIdentity finger,
1094 struct FriendInfo *target_friend,
1095 unsigned int trail_length,
1096 const struct GNUNET_PeerIdentity *trail_peer_list,
1097 unsigned int is_predecessor,
1098 uint64_t ultimate_destination_finger_value,
1099 struct GNUNET_HashCode trail_id)
1101 struct P2PPendingMessage *pending;
1102 struct PeerTrailSetupResultMessage *tsrm;
1103 struct GNUNET_PeerIdentity *peer_list;
1106 msize = sizeof (struct PeerTrailSetupResultMessage) +
1107 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1109 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1115 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1117 GNUNET_STATISTICS_update (GDS_stats,
1118 gettext_noop ("# P2P messages dropped due to full queue"),
1122 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1123 pending->importance = 0;
1124 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1125 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1126 pending->msg = &tsrm->header;
1127 tsrm->header.size = htons (msize);
1128 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1129 tsrm->querying_peer = querying_peer;
1130 tsrm->finger_identity = finger;
1131 tsrm->is_predecessor = htonl (is_predecessor);
1132 tsrm->trail_id = trail_id;
1133 tsrm->ulitmate_destination_finger_value =
1134 GNUNET_htonll (ultimate_destination_finger_value);
1135 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1136 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1138 /* Send the message to chosen friend. */
1139 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1140 target_friend->pending_count++;
1141 process_friend_queue (target_friend);
1146 * Send trail rejection message to target friend
1147 * @param source_peer Peer which is trying to setup the trail.
1148 * @param ultimate_destination_finger_value Peer closest to this value will be
1149 * @a source_peer's finger
1150 * @param congested_peer Peer which sent this message as it is congested.
1151 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1152 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1153 * by congested_peer. This does NOT include @a source_peer
1154 * and congested_peer.
1155 * @param trail_length Total number of peers in trail_peer_list, NOT including
1156 * @a source_peer and @a congested_peer
1157 * @param trail_id Unique identifier of this trail.
1158 * @param congestion_timeout Duration given by congested peer as an estimate of
1159 * how long it may remain congested.
1162 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1163 uint64_t ultimate_destination_finger_value,
1164 struct GNUNET_PeerIdentity congested_peer,
1165 unsigned int is_predecessor,
1166 const struct GNUNET_PeerIdentity *trail_peer_list,
1167 unsigned int trail_length,
1168 struct GNUNET_HashCode trail_id,
1169 struct FriendInfo *target_friend,
1170 const struct GNUNET_TIME_Relative congestion_timeout)
1172 struct PeerTrailRejectionMessage *trm;
1173 struct P2PPendingMessage *pending;
1174 struct GNUNET_PeerIdentity *peer_list;
1177 msize = sizeof (struct PeerTrailRejectionMessage) +
1178 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1180 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1186 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1188 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1192 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1193 pending->importance = 0;
1194 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1195 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1196 pending->msg = &trm->header;
1197 trm->header.size = htons (msize);
1198 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1199 trm->source_peer = source_peer;
1200 trm->congested_peer = congested_peer;
1201 trm->congestion_time = congestion_timeout;
1202 trm->is_predecessor = htonl (is_predecessor);
1203 trm->trail_id = trail_id;
1204 trm->ultimate_destination_finger_value =
1205 GNUNET_htonll (ultimate_destination_finger_value);
1207 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1208 if (trail_length > 0)
1210 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1213 /* Send the message to chosen friend. */
1214 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1215 target_friend->pending_count++;
1216 process_friend_queue (target_friend);
1221 * Construct a verify successor message and forward it to target_friend.
1222 * @param source_peer Peer which wants to verify its successor.
1223 * @param successor Peer which is @a source_peer's current successor.
1224 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1225 * NOT including them.
1226 * @param trail List of peers which are part of trail to reach from @a source_peer
1227 * to @a successor, NOT including them.
1228 * @param trail_length Total number of peers in @a trail.
1229 * @param target_friend Next friend to get this message.
1232 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1233 struct GNUNET_PeerIdentity successor,
1234 struct GNUNET_HashCode trail_id,
1235 struct GNUNET_PeerIdentity *trail,
1236 unsigned int trail_length,
1237 struct FriendInfo *target_friend)
1239 struct PeerVerifySuccessorMessage *vsm;
1240 struct P2PPendingMessage *pending;
1241 struct GNUNET_PeerIdentity *peer_list;
1244 msize = sizeof (struct PeerVerifySuccessorMessage) +
1245 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1246 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1252 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1254 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1258 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1259 pending->importance = 0; /* FIXME */
1260 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1261 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1262 pending->msg = &vsm->header;
1263 vsm->header.size = htons (msize);
1264 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1265 vsm->source_peer = source_peer;
1266 vsm->successor = successor;
1267 vsm->trail_id = trail_id;
1268 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1269 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1271 /* Send the message to chosen friend. */
1272 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1273 target_friend->pending_count++;
1274 process_friend_queue (target_friend);
1279 * FIXME: In every function we pass target friend except for this one.
1280 * so, either change everything or this one. also, should se just store
1281 * the pointer to friend in routing table rather than gnunet_peeridentity.
1282 * if yes then we should keep friend info in.h andmake lot of changes.
1283 * Construct a trail teardown message and forward it to target friend.
1284 * @param trail_id Unique identifier of the trail.
1285 * @param trail_direction Direction of trail.
1286 * @param target_friend Friend to get this message.
1289 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1290 unsigned int trail_direction,
1291 struct GNUNET_PeerIdentity peer)
1293 struct PeerTrailTearDownMessage *ttdm;
1294 struct P2PPendingMessage *pending;
1295 struct FriendInfo *target_friend;
1298 msize = sizeof (struct PeerTrailTearDownMessage);
1300 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1306 /*FIXME:In what case friend can be null. ?*/
1307 if (NULL == (target_friend =
1308 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1311 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1313 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1317 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1318 pending->importance = 0; /* FIXME */
1319 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1320 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1321 pending->msg = &ttdm->header;
1322 ttdm->header.size = htons (msize);
1323 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1324 ttdm->trail_id = trail_id;
1325 ttdm->trail_direction = htonl (trail_direction);
1327 /* Send the message to chosen friend. */
1328 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1329 target_friend->pending_count++;
1330 process_friend_queue (target_friend);
1335 * Construct a verify successor result message and send it to target_friend
1336 * @param querying_peer Peer which sent the verify successor message.
1337 * @param source_successor Current_successor of @a querying_peer.
1338 * @param current_predecessor Current predecessor of @a successor. Could be same
1339 * or different from @a querying_peer.
1340 * @param trail_id Unique identifier of the trail from @a querying_peer to
1341 * @a successor, NOT including them.
1342 * @param trail List of peers which are part of trail from @a querying_peer to
1343 * @a successor, NOT including them.
1344 * @param trail_length Total number of peers in @a trail
1345 * @param trail_direction Direction in which we are sending the message. In this
1346 * case we are sending result from @a successor to @a querying_peer.
1347 * @param target_friend Next friend to get this message.
1350 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1351 struct GNUNET_PeerIdentity current_successor,
1352 struct GNUNET_PeerIdentity probable_successor,
1353 struct GNUNET_HashCode trail_id,
1354 const struct GNUNET_PeerIdentity *trail,
1355 unsigned int trail_length,
1356 enum GDS_ROUTING_trail_direction trail_direction,
1357 struct FriendInfo *target_friend)
1359 struct PeerVerifySuccessorResultMessage *vsmr;
1360 struct P2PPendingMessage *pending;
1361 struct GNUNET_PeerIdentity *peer_list;
1364 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1365 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1367 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1373 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1375 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1379 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1380 pending->importance = 0; /* FIXME */
1381 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1382 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1383 pending->msg = &vsmr->header;
1384 vsmr->header.size = htons (msize);
1385 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1386 vsmr->querying_peer = querying_peer;
1387 vsmr->current_successor = current_successor;
1388 vsmr->probable_successor = probable_successor;
1389 vsmr->trail_direction = htonl (trail_direction);
1390 vsmr->trail_id = trail_id;
1391 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1392 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1394 /* Send the message to chosen friend. */
1395 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1396 target_friend->pending_count++;
1397 process_friend_queue (target_friend);
1402 * Construct a notify new successor message and send it to target_friend
1403 * @param source_peer Peer which wants to notify to its new successor that it
1404 * could be its predecessor.
1405 * @param successor New successor of @a source_peer
1406 * @param successor_trail List of peers in Trail to reach from
1407 * @a source_peer to @a new_successor, NOT including
1409 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1410 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1411 * @param target_friend Next friend to get this message.
1414 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1415 struct GNUNET_PeerIdentity successor,
1416 const struct GNUNET_PeerIdentity *successor_trail,
1417 unsigned int successor_trail_length,
1418 struct GNUNET_HashCode succesor_trail_id,
1419 struct FriendInfo *target_friend)
1421 struct PeerNotifyNewSuccessorMessage *nsm;
1422 struct P2PPendingMessage *pending;
1423 struct GNUNET_PeerIdentity *peer_list;
1426 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1427 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1429 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1435 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1437 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1441 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1442 pending->importance = 0; /* FIXME */
1443 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1444 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1445 pending->msg = &nsm->header;
1446 nsm->header.size = htons (msize);
1447 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1448 nsm->new_successor = successor;
1449 nsm->source_peer = source_peer;
1450 nsm->trail_id = succesor_trail_id;
1452 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1453 memcpy (peer_list, successor_trail,
1454 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1456 /* Send the message to chosen friend. */
1457 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1458 target_friend->pending_count++;
1459 process_friend_queue (target_friend);
1464 * Construct an add_trail message and send it to target_friend
1465 * @param source_peer Source of the trail.
1466 * @param destination_peer Destination of the trail.
1467 * @param trail_id Unique identifier of the trail from
1468 * @a source_peer to @a destination_peer, NOT including the endpoints.
1469 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1470 * NOT including the endpoints.
1471 * @param trail_length Total number of peers in @a trail.
1472 * @param target_friend Next friend to get this message.
1475 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1476 struct GNUNET_PeerIdentity destination_peer,
1477 struct GNUNET_HashCode trail_id,
1478 const struct GNUNET_PeerIdentity *trail,
1479 unsigned int trail_length,
1480 struct FriendInfo *target_friend)
1482 struct PeerAddTrailMessage *adm;
1483 struct GNUNET_PeerIdentity *peer_list;
1484 struct P2PPendingMessage *pending;
1487 msize = sizeof (struct PeerAddTrailMessage) +
1488 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1490 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1496 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1498 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1502 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1503 pending->importance = 0; /* FIXME */
1504 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1505 adm = (struct PeerAddTrailMessage *) &pending[1];
1506 pending->msg = &adm->header;
1507 adm->header.size = htons (msize);
1508 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1509 adm->source_peer = source_peer;
1510 adm->destination_peer = destination_peer;
1511 adm->trail_id = trail_id;
1512 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1513 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1515 /* Send the message to chosen friend. */
1516 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1517 target_friend->pending_count++;
1518 process_friend_queue (target_friend);
1524 * Search my location in trail. In case I am present more than once in the
1525 * trail (can happen during trail setup), then return my lowest index.
1526 * @param trail List of peers
1527 * @return my_index if found
1528 * trail_length + 1 if an entry is present twice, It is an error.
1529 * -1 if no entry found.
1532 search_my_index (const struct GNUNET_PeerIdentity *trail,
1536 int index_seen = trail_length + 1;
1539 for (i = 0; i < trail_length; i++)
1541 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1544 if(index_seen == (trail_length + 1))
1548 DEBUG("Entry is present twice in trail. Its not allowed\n");
1562 * Check if the friend is congested or have reached maximum number of trails
1563 * it can be part of of.
1564 * @param friend Friend to be checked.
1565 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1566 * #GNUNET_YES if friend is either congested or have crossed threshold
1569 is_friend_congested (struct FriendInfo *friend)
1571 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1572 ((0 == GNUNET_TIME_absolute_get_remaining
1573 (friend->congestion_timestamp).rel_value_us)))
1581 * Select closest finger to value.
1582 * @param peer1 First peer
1583 * @param peer2 Second peer
1584 * @param value Value to be compare
1585 * @return Closest peer
1587 static struct GNUNET_PeerIdentity
1588 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1589 const struct GNUNET_PeerIdentity *peer2,
1592 uint64_t peer1_value;
1593 uint64_t peer2_value;
1595 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1596 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1597 peer1_value = GNUNET_ntohll (peer1_value);
1598 peer2_value = GNUNET_ntohll (peer2_value);
1600 // TODO: Can use a simpler (to understand) idea here!
1601 if (peer1_value == value)
1606 if (peer2_value == value)
1611 if (peer2_value < peer1_value)
1613 if ((peer2_value < value) && (value < peer1_value))
1617 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1618 ((0 < value) && (value < peer2_value)))
1624 //if (peer1_value < peer2_value)
1626 if ((peer1_value < value) && (value < peer2_value))
1630 //else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1631 // ((0 < value) && (value < peer1_value)))
1640 * Select closest predecessor to value.
1641 * @param peer1 First peer
1642 * @param peer2 Second peer
1643 * @param value Value to be compare
1644 * @return Peer which precedes value in the network.
1646 static struct GNUNET_PeerIdentity
1647 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1648 const struct GNUNET_PeerIdentity *peer2,
1651 uint64_t peer1_value;
1652 uint64_t peer2_value;
1654 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1655 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1656 peer1_value = GNUNET_ntohll (peer1_value);
1657 peer2_value = GNUNET_ntohll (peer2_value);
1659 if (peer1_value == value)
1662 if (peer2_value == value)
1665 if (peer1_value < peer2_value)
1667 if ((peer1_value < value) && (value < peer2_value))
1671 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1672 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1678 // if (peer2_value < peer1_value)
1680 if ((peer2_value < value) && (value < peer1_value))
1684 //else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1685 // ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1698 test_print_trail (struct GNUNET_PeerIdentity *trail,
1699 unsigned int trail_length)
1701 struct GNUNET_PeerIdentity print_peer;
1704 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1705 __FILE__, __func__,__LINE__,trail_length);
1706 for (i =0 ; i< trail_length; i++)
1708 print_peer = trail[i];
1709 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1710 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1717 * This is a test function to print all the entries of friend table.
1720 test_friend_peermap_print ()
1722 struct FriendInfo *friend;
1723 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1724 struct GNUNET_PeerIdentity print_peer;
1725 struct GNUNET_PeerIdentity key_ret;
1728 print_peer = my_identity;
1729 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1730 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1732 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1734 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1736 (const void **)&friend))
1738 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1739 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1740 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1748 * This is a test function, to print all the entries of finger table.
1751 test_finger_table_print()
1753 struct FingerInfo *finger;
1754 struct GNUNET_PeerIdentity print_peer;
1755 //struct Trail *trail;
1759 print_peer = my_identity;
1760 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1761 for (i = 0; i < MAX_FINGERS; i++)
1763 finger = &finger_table[i];
1765 if (GNUNET_NO == finger->is_present)
1768 print_peer = finger->finger_identity;
1769 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1770 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1773 for (j = 0; j < finger->trails_count; j++)
1775 trail = &finger->trail_list[j];
1776 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1777 struct Trail_Element *element;
1778 element = trail->trail_head;
1779 for (k = 0; k < trail->trail_length; k++)
1781 print_peer = element->peer;
1782 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1783 element = element->next;
1792 * Select the closest peer among two peers (which should not be same)
1793 * with respect to value and finger_table_index
1794 * NOTE: peer1 != peer2
1795 * @param peer1 First peer
1796 * @param peer2 Second peer
1797 * @param value Value relative to which we find the closest
1798 * @param is_predecessor Is value a predecessor or any other finger.
1799 * @return Closest peer among two peers.
1801 static struct GNUNET_PeerIdentity
1802 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1803 const struct GNUNET_PeerIdentity *peer2,
1805 unsigned int is_predecessor)
1807 /* This check is here to ensure that calling function never sends
1808 same peer value in peer1 and peer2. Remove it later. */
1809 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1810 if (1 == is_predecessor)
1811 return select_closest_predecessor (peer1, peer2, value);
1813 // TODO: Change name to something like select_closest_successor!!
1814 return select_closest_finger (peer1, peer2, value);
1819 * Iterate over the list of all the trails of a finger. In case the first
1820 * friend to reach the finger has reached trail threshold or is congested,
1821 * then don't select it. In case there multiple available good trails to reach
1822 * to Finger, choose the one with shortest trail length.
1823 * Note: We use length as parameter. But we can use any other suitable parameter
1825 * @param finger Finger
1826 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1827 * and trail length. NULL in case none of the trails are free.
1829 static struct Trail *
1830 select_finger_trail (struct FingerInfo *finger)
1832 struct FriendInfo *friend;
1833 struct Trail *current_finger_trail;
1834 struct Trail *best_trail = NULL;
1837 GNUNET_assert (finger->trails_count > 0);
1839 for (i = 0; i < finger->trails_count; i++)
1841 current_finger_trail = &finger->trail_list[i];
1843 /* No trail stored at this index. */
1844 if (GNUNET_NO == current_finger_trail->is_present)
1847 GNUNET_assert (NULL !=
1849 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1850 ¤t_finger_trail->trail_head->peer)));
1852 /* First friend to reach trail is not free. */
1853 if (GNUNET_YES == is_friend_congested (friend))
1856 if (NULL == best_trail ||
1857 best_trail->trail_length > current_finger_trail->trail_length)
1859 best_trail = current_finger_trail;
1867 static struct Selected_Finger_Trail *
1868 select_finger_trail (struct FingerInfo *finger)
1870 struct FriendInfo *friend;
1871 struct Trail *current_finger_trail;
1872 struct Selected_Finger_Trail *finger_trail;
1874 unsigned int flag = 0;
1877 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1878 GNUNET_assert (finger->trails_count > 0);
1880 for (i = 0; i < finger->trails_count; i++)
1882 current_finger_trail = &finger->trail_list[i];
1884 /* No trail stored at this index. */
1885 if (GNUNET_NO == current_finger_trail->is_present)
1888 GNUNET_assert (NULL !=
1890 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1891 ¤t_finger_trail->trail_head->peer)));
1893 /* First friend to reach trail is not free. */
1894 if (GNUNET_YES == is_friend_congested (friend))
1903 finger_trail->trail_length = current_finger_trail->trail_length;
1904 finger_trail->friend = *friend;
1905 finger_trail->trail_id = current_finger_trail->trail_id;
1907 else if (finger_trail->trail_length > current_finger_trail->trail_length)
1909 finger_trail->friend = *friend;
1910 finger_trail->trail_id = current_finger_trail->trail_id;
1911 finger_trail->trail_length = current_finger_trail->trail_length;
1915 /* All the first friend in all the trails to reach to finger are either
1916 congested or have crossed trail threshold. */
1917 if (j == finger->trails_count)
1920 return finger_trail;
1926 * Compare FINGER entry with current successor. If finger's first friend of all
1927 * its trail is not congested and has not crossed trail threshold, then check
1928 * if finger peer identity is closer to final_destination_finger_value than
1929 * current_successor. If yes then update current_successor.
1930 * @param current_successor[in/out]
1934 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
1936 struct FingerInfo *finger;
1937 struct GNUNET_PeerIdentity closest_peer;
1938 struct Trail *finger_trail;
1941 /* Iterate over finger table. */
1942 for (i = 0; i < MAX_FINGERS; i++)
1944 finger = &finger_table[i];
1946 if (GNUNET_NO == finger->is_present)
1949 /* FIXME write correct comment here */
1950 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1951 ¤t_closest_peer->best_known_destination))
1954 /* If I am my own finger, then ignore this finger. */
1955 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1958 /* FIXME: I think a peer should not select itself as its own identity ever.
1959 But it does select. Find out why??*/
1965 /* If finger is a friend, then do nothing. As we have already checked
1966 * for each friend in compare_friend_and_current_successor(). */
1967 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1968 &finger->finger_identity)))
1973 closest_peer = select_closest_peer (&finger->finger_identity,
1974 ¤t_closest_peer->best_known_destination,
1975 current_closest_peer->destination_finger_value,
1976 current_closest_peer->is_predecessor);
1978 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer))
1980 /* Choose one of the trail to reach to finger. */
1981 finger_trail = select_finger_trail (finger);
1983 /* In case no trail found, ignore this finger. */
1984 if (NULL == finger_trail)
1987 current_closest_peer->best_known_destination = closest_peer;
1988 current_closest_peer->next_hop = finger_trail->trail_head->peer;
1989 current_closest_peer->trail_id = finger_trail->trail_id;
1997 * Compare friend entry with current successor.
1998 * If friend identity and current_successor is same, then do nothing.
1999 * If friend is not congested and has not crossed trail threshold, then check
2000 * if friend peer identity is closer to final_destination_finger_value than
2001 * current_successor. If yes then update current_successor.
2002 * @param cls closure
2003 * @param key current public key
2004 * @param value struct Closest_Peer
2005 * @return #GNUNET_YES if we should continue to iterate,
2006 * #GNUNET_NO if not.
2009 compare_friend_and_current_closest_peer (void *cls,
2010 const struct GNUNET_PeerIdentity *key,
2013 struct FriendInfo *friend = value;
2014 struct Closest_Peer *current_closest_peer = cls;
2015 struct GNUNET_PeerIdentity closest_peer;
2017 /* Friend is either congested or has crossed threshold. */
2018 if (GNUNET_YES == is_friend_congested (friend))
2021 /* If current_closest_peer and friend identity are same, then do nothing.*/
2022 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2023 ¤t_closest_peer->best_known_destination))
2029 closest_peer = select_closest_peer (&friend->id,
2030 ¤t_closest_peer->best_known_destination,
2031 current_closest_peer->destination_finger_value,
2032 current_closest_peer->is_predecessor);
2034 /* Is friend the closest successor? */
2035 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer))
2037 current_closest_peer->best_known_destination = friend->id;
2038 current_closest_peer->next_hop = friend->id;
2046 * Initialize current_successor to my_identity.
2047 * @param my_identity My peer identity
2048 * @return Updated closest_peer
2050 static struct Closest_Peer
2051 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2052 uint64_t destination_finger_value,
2053 unsigned int is_predecessor)
2055 struct Closest_Peer current_closest_peer;
2057 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2058 current_closest_peer.destination_finger_value = destination_finger_value;
2059 current_closest_peer.is_predecessor = is_predecessor;
2060 current_closest_peer.next_hop = my_identity;
2061 current_closest_peer.best_known_destination = my_identity;
2063 return current_closest_peer;
2068 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2069 * peer. It could be because of the logic we wrote here. Verify if its correct.
2070 * If not then return immediate_successor.
2072 * Find the successor for destination_finger_value among my_identity, my
2073 * friends and my fingers. Don't consider friends or fingers which are either
2074 * congested or have crossed the threshold.
2075 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2077 * @param destination_finger_value Peer closest to this value will be the next successor.
2078 * @param is_predecessor Are we looking for predecessor or finger?
2079 * @return Successor It is never NULL, in case none of friend or finger is closest,
2080 * then we return my_identity.
2082 static struct Closest_Peer
2083 find_successor (uint64_t destination_finger_value,
2084 unsigned int is_predecessor)
2086 struct Closest_Peer current_closest_peer;
2088 /* Initialize current_successor to my_identity. */
2089 current_closest_peer = init_current_successor (my_identity,
2090 destination_finger_value,
2093 /* Compare each friend entry with current_successor and update current_successor
2094 * with friend if its closest. */
2097 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2098 &compare_friend_and_current_closest_peer,
2099 ¤t_closest_peer));
2101 /* Compare each finger entry with current_successor and update current_successor
2102 * with finger if its closest. */
2103 compare_finger_and_current_closest_peer (¤t_closest_peer);
2105 return current_closest_peer;
2110 * FIXME; Send put message across all the trail to reach to next hop to handle
2112 * Construct a Put message and send it to target_peer.
2113 * @param key Key for the content
2114 * @param block_type Type of the block
2115 * @param options Routing options
2116 * @param desired_replication_level Desired replication count
2117 * @param best_known_dest Peer to which this message should reach eventually,
2118 * as it is best known destination to me.
2119 * @param intermediate_trail_id Trail id in case
2120 * @param target_peer Peer to which this message will be forwarded.
2121 * @param hop_count Number of hops traversed so far.
2122 * @param put_path_length Total number of peers in @a put_path
2123 * @param put_path Number of peers traversed so far
2124 * @param expiration_time When does the content expire
2125 * @param data Content to store
2126 * @param data_size Size of content @a data in bytes
2129 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2130 enum GNUNET_BLOCK_Type block_type,
2131 enum GNUNET_DHT_RouteOption options,
2132 uint32_t desired_replication_level,
2133 struct GNUNET_PeerIdentity best_known_dest,
2134 struct GNUNET_HashCode intermediate_trail_id,
2135 struct GNUNET_PeerIdentity *target_peer,
2137 uint32_t put_path_length,
2138 struct GNUNET_PeerIdentity *put_path,
2139 struct GNUNET_TIME_Absolute expiration_time,
2140 const void *data, size_t data_size)
2142 struct PeerPutMessage *ppm;
2143 struct P2PPendingMessage *pending;
2144 struct FriendInfo *target_friend;
2145 struct GNUNET_PeerIdentity *pp;
2146 struct GNUNET_PeerIdentity next_hop;
2150 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2151 sizeof (struct PeerPutMessage);
2153 #if ENABLE_MALICIOUS
2154 /*Call is made to this function from
2156 2. Every peer to construct a pending message and send it to next peer.
2157 In case of 2nd, this case should have been handled in handle_dht_p2p_put/get
2158 No need to check here. First peer can never be malicious. IDEALLY we DONOT
2159 need the condition here. REMOVE IT AFTERWARDS once verified.*/
2160 if(1 == act_malicious)
2165 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2167 put_path_length = 0;
2168 msize = data_size + sizeof (struct PeerPutMessage);
2171 /* Should it be GNUNET_SERVER_MAX_MESSAGE_SIZE? */
2172 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2174 DEBUG("msize = %lu\n",msize);
2179 /* This is the first call made from clients file. So, we should search for the
2181 if (NULL == target_peer)
2184 struct Closest_Peer successor;
2186 memcpy (&key_value, key, sizeof (uint64_t));
2187 key_value = GNUNET_ntohll (key_value);
2189 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2190 best_known_dest = successor.best_known_destination;
2191 next_hop = successor.next_hop;
2192 intermediate_trail_id = successor.trail_id;
2194 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2196 /* I am the destination. */
2197 DEBUG("PUT destination is me = %s,key =%s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2198 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2199 block_type,data_size,data);
2203 GNUNET_assert (NULL !=
2205 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2209 GNUNET_assert (NULL !=
2211 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2214 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2215 pending->timeout = expiration_time;
2216 ppm = (struct PeerPutMessage *) &pending[1];
2217 pending->msg = &ppm->header;
2218 ppm->header.size = htons (msize);
2219 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2220 ppm->options = htonl (options);
2221 ppm->block_type = htonl (block_type);
2222 ppm->hop_count = htonl (hop_count + 1);
2223 ppm->desired_replication_level = htonl (desired_replication_level);
2224 ppm->put_path_length = htonl (put_path_length);
2225 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2226 ppm->best_known_destination = best_known_dest;
2229 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2230 if (put_path_length != 0)
2232 memcpy (pp, put_path,
2233 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2235 memcpy (&pp[put_path_length], data, data_size);
2236 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2237 target_friend->pending_count++;
2238 process_friend_queue (target_friend);
2243 * FIXME; Send get message across all the trail to reach to next hop to handle
2245 * Construct a Get message and send it to target_peer.
2246 * @param key Key for the content
2247 * @param block_type Type of the block
2248 * @param options Routing options
2249 * @param desired_replication_level Desired replication count
2250 * @param best_known_dest Peer which should get this message. Same as target peer
2251 * if best_known_dest is a friend else its a finger.
2252 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2253 * in case it is a finger else set to 0.
2254 * @param target_peer Peer to which this message will be forwarded.
2255 * @param hop_count Number of hops traversed so far.
2256 * @param data Content to store
2257 * @param data_size Size of content @a data in bytes
2258 * @param get_path_length Total number of peers in @a get_path
2259 * @param get_path Number of peers traversed so far
2262 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2263 enum GNUNET_BLOCK_Type block_type,
2264 enum GNUNET_DHT_RouteOption options,
2265 uint32_t desired_replication_level,
2266 struct GNUNET_PeerIdentity best_known_dest,
2267 struct GNUNET_HashCode intermediate_trail_id,
2268 struct GNUNET_PeerIdentity *target_peer,
2270 uint32_t get_path_length,
2271 struct GNUNET_PeerIdentity *get_path)
2273 struct PeerGetMessage *pgm;
2274 struct P2PPendingMessage *pending;
2275 struct FriendInfo *target_friend;
2276 struct GNUNET_PeerIdentity *gp;
2279 msize = sizeof (struct PeerGetMessage) +
2280 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2282 #if ENABLE_MALICIOUS
2283 if(1 == act_malicious)
2288 //GNUNET_SERVER_MAX_MESSAGE_SIZE
2289 /* FIXME:TODO:URGENTHere you can try to optimize it a bit. In case the get path contains you
2290 or your friend then shorten the path. */
2291 /* In this case we don't make get_path_length = 0, as we need get path to
2292 * return the message back to querying client. */
2293 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2299 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
2301 /* This is the first time we got request from our own client file. */
2302 if (NULL == target_peer)
2305 struct Closest_Peer successor;
2307 memcpy (&key_value, key, sizeof (uint64_t));
2308 key_value = GNUNET_ntohll (key_value);
2309 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2311 best_known_dest = successor.best_known_destination;
2312 intermediate_trail_id = successor.trail_id;
2314 /* I am the destination. I have the data. */
2315 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2318 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2319 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2320 NULL, 0, 1, &my_identity, NULL,&my_identity);
2326 GNUNET_assert (NULL !=
2328 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2329 &successor.next_hop)));
2335 GNUNET_assert (NULL !=
2337 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2340 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2341 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2342 pending->importance = 0; /* FIXME */
2343 pgm = (struct PeerGetMessage *) &pending[1];
2344 pending->msg = &pgm->header;
2345 pgm->header.size = htons (msize);
2346 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2347 pgm->get_path_length = htonl (get_path_length);
2348 pgm->best_known_destination = best_known_dest;
2350 pgm->intermediate_trail_id = intermediate_trail_id;
2351 pgm->hop_count = htonl (hop_count + 1);
2352 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2354 if (get_path_length != 0)
2356 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2359 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2360 target_friend->pending_count++;
2361 process_friend_queue (target_friend);
2366 * Send the get result to requesting client.
2367 * @param key Key of the requested data.
2368 * @param type Block type
2369 * @param target_peer Next peer to forward the message to.
2370 * @param source_peer Peer which has the data for the key.
2371 * @param put_path_length Number of peers in @a put_path
2372 * @param put_path Path taken to put the data at its stored location.
2373 * @param get_path_length Number of peers in @a get_path
2374 * @param get_path Path taken to reach to the location of the key.
2375 * @param expiration When will this result expire?
2376 * @param data Payload to store
2377 * @param data_size Size of the @a data
2380 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2381 enum GNUNET_BLOCK_Type type,
2382 const struct GNUNET_PeerIdentity *target_peer,
2383 const struct GNUNET_PeerIdentity *source_peer,
2384 unsigned int put_path_length,
2385 const struct GNUNET_PeerIdentity *put_path,
2386 unsigned int get_path_length,
2387 const struct GNUNET_PeerIdentity *get_path,
2388 struct GNUNET_TIME_Absolute expiration,
2389 const void *data, size_t data_size)
2391 struct PeerGetResultMessage *get_result;
2392 struct GNUNET_PeerIdentity *paths;
2393 struct P2PPendingMessage *pending;
2394 struct FriendInfo *target_friend;
2395 int current_path_index;
2398 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2400 sizeof (struct PeerGetResultMessage);
2402 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2404 put_path_length = 0;
2405 msize = msize - put_path_length;
2409 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2414 DEBUG("GET RESULT FOR DATA_SIZE = %lu\n",msize);
2415 current_path_index = 0;
2416 if(get_path_length > 0)
2418 current_path_index = search_my_index(get_path, get_path_length);
2419 if (-1 == current_path_index)
2424 if ((get_path_length + 1) == current_path_index)
2426 DEBUG ("Peer found twice in get path. Not allowed \n");
2431 if (0 == current_path_index)
2433 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2434 get_path, put_path_length,
2435 put_path, type, data_size, data);
2439 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2440 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2441 pending->importance = 0;
2442 get_result = (struct PeerGetResultMessage *)&pending[1];
2443 pending->msg = &get_result->header;
2444 get_result->header.size = htons (msize);
2445 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2446 get_result->key = *key;
2447 get_result->querying_peer = *source_peer;
2448 get_result->expiration_time = expiration;
2449 get_result->get_path_length = htonl (get_path_length);
2450 get_result->put_path_length = htonl (put_path_length);
2451 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2452 memcpy (paths, put_path,
2453 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2454 memcpy (&paths[put_path_length], get_path,
2455 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2456 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2458 GNUNET_assert (NULL !=
2460 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2461 &get_path[current_path_index - 1])));
2462 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2463 target_friend->pending_count++;
2464 process_friend_queue (target_friend);
2469 * Randomly choose one of your friends (which is not congested and have not crossed
2470 * trail threshold) from the friend_peermap
2471 * @return Friend Randomly chosen friend.
2472 * NULL in case friend peermap is empty, or all the friends are either
2473 * congested or have crossed trail threshold.
2475 static struct FriendInfo *
2476 select_random_friend ()
2478 unsigned int current_size;
2481 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2482 struct GNUNET_PeerIdentity key_ret;
2483 struct FriendInfo *friend;
2485 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2488 if (0 == current_size)
2491 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2492 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2494 /* Iterate till you don't reach to index. */
2495 for (j = 0; j < index ; j++)
2496 GNUNET_assert (GNUNET_YES ==
2497 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2501 /* Reset the index in friend peermap to 0 as we reached to the end. */
2502 if (j == current_size)
2505 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2506 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2510 /* Get the friend stored at the index, j*/
2511 GNUNET_assert (GNUNET_YES ==
2512 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2514 (const void **)&friend));
2516 /* This friend is not congested and has not crossed trail threshold. */
2517 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2518 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2524 } while (j != index);
2526 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2532 * Compute 64 bit value of finger_identity corresponding to a finger index using
2534 * For all fingers, n.finger[i] = n + pow (2,i),
2535 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2536 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2537 * @param finger_index Index corresponding to which we calculate 64 bit value.
2538 * @return 64 bit value.
2541 compute_finger_identity_value (unsigned int finger_index)
2545 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2546 my_id64 = GNUNET_ntohll (my_id64);
2548 /* Are we looking for immediate predecessor? */
2549 if (PREDECESSOR_FINGER_ID == finger_index)
2550 return (my_id64 - 1);
2553 uint64_t add = (uint64_t)1 << finger_index;
2554 return (my_id64 + add);
2560 * Choose a random friend. Calculate the next finger identity to search,from
2561 * current_search_finger_index. Start looking for the trail to reach to
2562 * finger identity through this random friend.
2564 * @param cls closure for this task
2565 * @param tc the context under which the task is running
2568 send_find_finger_trail_message (void *cls,
2569 const struct GNUNET_SCHEDULER_TaskContext *tc)
2571 struct FriendInfo *target_friend;
2572 struct GNUNET_HashCode trail_id;
2573 struct GNUNET_HashCode intermediate_trail_id;
2574 unsigned int is_predecessor;
2575 uint64_t finger_id_value;
2577 /* Schedule another send_find_finger_trail_message task. */
2578 find_finger_trail_task_next_send_time =
2579 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
2580 find_finger_trail_task =
2581 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2582 &send_find_finger_trail_message,
2585 /* No space in my routing table. (Source and destination peers also store entries
2586 * in their routing table). */
2587 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2591 target_friend = select_random_friend ();
2592 if (NULL == target_friend)
2597 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2599 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2604 /* Generate a unique trail id for trail we are trying to setup. */
2605 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2606 &trail_id, sizeof (trail_id));
2607 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2609 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2610 target_friend->id, target_friend, 0, NULL,
2611 is_predecessor, trail_id,
2612 intermediate_trail_id);
2617 * In case there are already maximum number of possible trails to reach to a
2618 * finger, then check if the new trail's length is lesser than any of the
2620 * If yes then replace that old trail by new trail.
2622 * Note: Here we are taking length as a parameter to choose the best possible
2623 * trail, but there could be other parameters also like:
2624 * 1. duration of existence of a trail - older the better.
2625 * 2. if the new trail is completely disjoint than the
2626 * other trails, then may be choosing it is better.
2628 * @param finger Finger
2629 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2630 * including the endpoints.
2631 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2632 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2635 select_and_replace_trail (struct FingerInfo *finger,
2636 const struct GNUNET_PeerIdentity *new_trail,
2637 unsigned int new_trail_length,
2638 struct GNUNET_HashCode new_trail_id)
2640 struct Trail *trail;
2641 unsigned int largest_trail_length;
2642 unsigned int largest_trail_index;
2643 struct Trail_Element *trail_element;
2646 largest_trail_length = new_trail_length;
2647 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2649 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2651 for (i = 0; i < finger->trails_count; i++)
2653 trail = &finger->trail_list[i];
2654 if (trail->trail_length > largest_trail_length)
2656 largest_trail_length = trail->trail_length;
2657 largest_trail_index = i;
2661 /* New trail is not better than existing ones. Send trail teardown. */
2662 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2664 struct GNUNET_PeerIdentity next_hop;
2666 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2667 GDS_ROUTING_remove_trail (new_trail_id);
2668 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2669 GDS_ROUTING_SRC_TO_DEST,
2674 /* Send trail teardown message across the replaced trail. */
2675 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2677 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2678 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2679 GDS_ROUTING_SRC_TO_DEST,
2680 replace_trail->trail_head->peer);
2681 /* Free the trail. */
2682 while (NULL != (trail_element = replace_trail->trail_head))
2684 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2685 replace_trail->trail_tail, trail_element);
2686 GNUNET_free_non_null (trail_element);
2689 /* Add new trial at that location. */
2690 replace_trail->is_present = GNUNET_YES;
2691 replace_trail->trail_length = new_trail_length;
2692 replace_trail->trail_id = new_trail_id;
2694 for (i = 0; i < new_trail_length; i++)
2696 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2697 element->peer = new_trail[i];
2699 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2700 replace_trail->trail_tail,
2703 /* FIXME: Are we adding the trail back to the list. */
2708 * Check if the new trail to reach to finger is unique or do we already have
2709 * such a trail present for finger.
2710 * @param existing_finger Finger identity
2711 * @param new_trail New trail to reach @a existing_finger
2712 * @param trail_length Total number of peers in new_trail.
2713 * @return #GNUNET_YES if the new trail is unique
2714 * #GNUNET_NO if same trail is already present.
2717 is_new_trail_unique (struct FingerInfo *existing_finger,
2718 const struct GNUNET_PeerIdentity *new_trail,
2719 unsigned int trail_length)
2721 struct Trail *trail;
2722 struct Trail_Element *trail_element;
2726 GNUNET_assert (existing_finger->trails_count > 0);
2728 /* Iterate over list of trails. */
2729 for (i = 0; i < existing_finger->trails_count; i++)
2731 trail = &(existing_finger->trail_list[i]);
2732 GNUNET_assert (GNUNET_YES == trail->is_present);
2734 /* New trail and existing trail length are not same. */
2735 if (trail->trail_length != trail_length)
2740 trail_element = trail->trail_head;
2741 GNUNET_assert (trail_element != NULL);
2742 for (j = 0; j < trail->trail_length; j++)
2744 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2745 &trail_element->peer))
2749 trail_element = trail_element->next;
2757 * FIXME; In case of multiple trails, we may have a case where a trail from in
2758 * between has been removed, then we should try to find a free slot , not simply
2759 * add a trail at then end of the list.
2760 * Add a new trail to existing finger. This function is called only when finger
2761 * is not my own identity or a friend.
2762 * @param existing_finger Finger
2763 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2764 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2765 * @param new_finger_trail_id Unique identifier of the trail.
2768 add_new_trail (struct FingerInfo *existing_finger,
2769 const struct GNUNET_PeerIdentity *new_trail,
2770 unsigned int new_trail_length,
2771 struct GNUNET_HashCode new_trail_id)
2773 struct Trail *trail;
2774 struct FriendInfo *first_friend;
2778 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2784 index = existing_finger->trails_count;
2785 trail = &existing_finger->trail_list[index];
2786 GNUNET_assert (GNUNET_NO == trail->is_present);
2787 trail->trail_id = new_trail_id;
2788 trail->trail_length = new_trail_length;
2789 existing_finger->trails_count++;
2790 trail->is_present = GNUNET_YES;
2792 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2793 &existing_finger->finger_identity)));
2794 /* If finger is a friend then we never call this function. */
2795 GNUNET_assert (new_trail_length > 0);
2797 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2799 first_friend->trails_count++;
2801 for (i = 0; i < new_trail_length; i++)
2803 struct Trail_Element *element;
2805 element = GNUNET_new (struct Trail_Element);
2806 element->peer = new_trail[i];
2807 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2811 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2812 existing_finger->trail_list[index].trail_head = trail->trail_head;
2813 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2814 existing_finger->trail_list[index].trail_length = new_trail_length;
2815 existing_finger->trail_list[index].trail_id = new_trail_id;
2816 existing_finger->trail_list[index].is_present = GNUNET_YES;
2821 * FIXME Check if this function is called for opposite direction if yes then
2822 * take it as parameter.
2823 * Get the next hop to send trail teardown message from routing table and
2824 * then delete the entry from routing table. Send trail teardown message for a
2825 * specific trail of a finger.
2826 * @param finger Finger whose trail is to be removed.
2827 * @param trail List of peers in trail from me to a finger, NOT including
2831 send_trail_teardown (struct FingerInfo *finger,
2832 struct Trail *trail)
2834 struct FriendInfo *friend;
2835 struct GNUNET_PeerIdentity *next_hop;
2837 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2838 GDS_ROUTING_SRC_TO_DEST);
2840 if (NULL == next_hop)
2842 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
2843 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
2848 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2851 /*FIXME: here was an assertion that trail->is_present = GNUNET_YES. But it
2852 used to fail. We have removed assertion with a condition, just for now.
2853 Find out the reason why assertion failed. */
2854 if (trail->is_present == GNUNET_NO)
2856 DEBUG(" trail id %s of peer %s is not present to send a trail teardown message., line",
2857 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
2861 /* Finger is not a friend. */
2862 if (trail->trail_length > 0)
2864 GNUNET_assert (NULL != (friend =
2865 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2866 &trail->trail_head->peer)));
2870 GNUNET_assert (NULL != (friend =
2871 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2872 &finger->finger_identity)));
2875 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id));
2876 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2877 friend->trails_count--;
2878 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2879 GDS_ROUTING_SRC_TO_DEST,
2885 * Send trail teardown message across all the trails to reach to finger.
2886 * @param finger Finger whose all the trail should be freed.
2889 send_all_finger_trails_teardown (struct FingerInfo *finger)
2892 for (i = 0; i < finger->trails_count; i++)
2894 struct Trail *trail;
2896 trail = &finger->trail_list[i];
2897 GNUNET_assert (trail->is_present == GNUNET_YES);
2898 send_trail_teardown (finger, trail);
2899 trail->is_present = GNUNET_NO;
2905 * Free a specific trail
2906 * @param trail List of peers to be freed.
2909 free_trail (struct Trail *trail)
2911 struct Trail_Element *trail_element;
2913 while (NULL != (trail_element = trail->trail_head))
2915 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2918 GNUNET_free_non_null (trail_element);
2920 trail->trail_head = NULL;
2921 trail->trail_tail = NULL;
2926 * Free finger and its trail.
2927 * @param finger Finger to be freed.
2928 * @param finger_table_index Index at which finger is stored.
2931 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2933 struct Trail *trail;
2935 for (i = 0; i < finger->trails_count; i++)
2937 trail = &finger->trail_list[i];
2938 if (GNUNET_NO == trail->is_present)
2941 if (trail->trail_length > 0)
2943 trail->is_present = GNUNET_NO;
2946 finger->is_present = GNUNET_NO;
2947 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2952 * Add a new entry in finger table at finger_table_index.
2953 * In case I am my own finger, then we don't have a trail. In case of a friend,
2954 * we have a trail with unique id and '0' trail length.
2955 * In case a finger is a friend, then increment the trails count of the friend.
2956 * @param finger_identity Peer Identity of new finger
2957 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2958 * @param finger_trail_length Total number of peers in @a finger_trail.
2959 * @param trail_id Unique identifier of the trail.
2960 * @param finger_table_index Index in finger table.
2963 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2964 const struct GNUNET_PeerIdentity *finger_trail,
2965 unsigned int finger_trail_length,
2966 struct GNUNET_HashCode trail_id,
2967 unsigned int finger_table_index)
2969 struct FingerInfo *new_entry;
2970 struct FriendInfo *first_trail_hop;
2971 struct Trail *trail;
2974 new_entry = GNUNET_new (struct FingerInfo);
2975 new_entry->finger_identity = finger_identity;
2976 new_entry->finger_table_index = finger_table_index;
2977 new_entry->is_present = GNUNET_YES;
2979 /* If the new entry is my own identity. */
2980 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2983 new_entry->trails_count = 0;
2984 finger_table[finger_table_index] = *new_entry;
2985 GNUNET_free (new_entry);
2989 /* If finger is a friend, then we don't actually have a trail.
2990 * Just a trail id */
2991 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2994 new_entry->trail_list[0].trail_id = trail_id;
2995 new_entry->trails_count = 1;
2996 new_entry->trail_list[0].is_present = GNUNET_YES;
2997 new_entry->trail_list[0].trail_length = 0;
2998 new_entry->trail_list[0].trail_head = NULL;
2999 new_entry->trail_list[0].trail_tail = NULL;
3000 finger_table[finger_table_index] = *new_entry;
3001 GNUNET_assert (NULL !=
3003 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3004 &finger_identity)));
3006 first_trail_hop->trails_count++;
3007 GNUNET_free (new_entry);
3011 GNUNET_assert (NULL !=
3013 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3014 &finger_trail[0])));
3015 new_entry->trails_count = 1;
3016 first_trail_hop->trails_count++;
3018 /* Copy the finger trail into trail. */
3019 trail = GNUNET_new (struct Trail);
3020 for(i = 0; i < finger_trail_length; i++)
3022 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3024 element->next = NULL;
3025 element->prev = NULL;
3026 element->peer = finger_trail[i];
3027 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3033 /* Add trail to trail list. */
3034 new_entry->trail_list[0].trail_head = trail->trail_head;
3035 new_entry->trail_list[0].trail_tail = trail->trail_tail;
3036 new_entry->trail_list[0].trail_length = finger_trail_length;
3037 new_entry->trail_list[0].trail_id = trail_id;
3038 new_entry->trail_list[0].is_present = GNUNET_YES;
3039 finger_table[finger_table_index] = *new_entry;
3040 GNUNET_free (new_entry);
3046 * Periodic task to verify current successor. There can be multiple trails to reach
3047 * to successor, choose the shortest one and send verify successor message
3048 * across that trail.
3049 * @param cls closure for this task
3050 * @param tc the context under which the task is running
3053 send_verify_successor_message (void *cls,
3054 const struct GNUNET_SCHEDULER_TaskContext *tc)
3056 struct FriendInfo *target_friend;
3057 struct GNUNET_HashCode trail_id;
3059 struct Trail *trail;
3060 struct Trail_Element *element;
3061 unsigned int trail_length;
3063 struct FingerInfo *successor;
3065 verify_successor_next_send_time =
3066 GNUNET_TIME_STD_BACKOFF(verify_successor_next_send_time);
3067 /* Schedule another send_find_finger_trail_message task. */
3068 verify_successor_next_send_time.rel_value_us =
3069 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
3070 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3071 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
3072 send_verify_successor_task =
3073 GNUNET_SCHEDULER_add_delayed (verify_successor_next_send_time,
3074 &send_verify_successor_message,
3077 successor = &finger_table[0];
3078 for (i = 0; i < successor->trails_count; i++)
3080 trail = &successor->trail_list[i];
3081 if(GNUNET_YES == trail->is_present)
3085 /* No valid trail found to reach to successor. */
3086 if (i == successor->trails_count)
3089 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3090 &successor->finger_identity));
3092 /* Trail stored at this index. */
3093 GNUNET_assert (GNUNET_YES == trail->is_present);
3095 trail_id = trail->trail_id;
3096 if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST))
3098 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3099 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
3103 trail_length = trail->trail_length;
3105 if (trail_length > 0)
3107 /* Copy the trail into peer list. */
3108 struct GNUNET_PeerIdentity peer_list[trail_length];
3110 element = trail->trail_head;
3111 while (j < trail_length)
3113 peer_list[j] = element->peer;
3114 element = element->next;
3118 GNUNET_assert (NULL != (target_friend =
3119 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3121 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3122 successor->finger_identity,
3123 trail_id, peer_list, trail_length,
3129 GNUNET_assert (NULL != (target_friend =
3130 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3131 &successor->finger_identity)));
3132 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3133 successor->finger_identity,
3142 * FIXME: should this be a periodic task, incrementing the search finger index?
3143 * Update the current search finger index.
3145 * FIXME document parameters!
3148 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3149 unsigned int finger_table_index)
3151 struct FingerInfo *successor;
3153 /* FIXME correct this: only move current index periodically */
3154 if (finger_table_index != current_search_finger_index)
3157 successor = &finger_table[0];
3158 GNUNET_assert (GNUNET_YES == successor->is_present);
3160 /* We were looking for immediate successor. */
3161 if (0 == current_search_finger_index)
3163 /* Start looking for immediate predecessor. */
3164 current_search_finger_index = PREDECESSOR_FINGER_ID;
3166 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3168 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3170 DEBUG (" schedule");
3171 send_verify_successor_task =
3172 GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3178 current_search_finger_index = current_search_finger_index - 1;
3184 * Get the least significant bit set in val.
3187 * @return Position of first bit set, 65 in case of error.
3190 find_set_bit (uint64_t val)
3210 return 65; /* Some other bit was set to 1 as well. */
3217 * Calculate finger_table_index from initial 64 bit finger identity value that
3218 * we send in trail setup message.
3219 * @param ultimate_destination_finger_value Value that we calculated from our
3220 * identity and finger_table_index.
3221 * @param is_predecessor Is the entry for predecessor or not?
3222 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3223 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3226 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3227 unsigned int is_predecessor)
3231 unsigned int finger_table_index;
3233 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3234 my_id64 = GNUNET_ntohll (my_id64);
3236 /* Is this a predecessor finger? */
3237 if (1 == is_predecessor)
3239 diff = my_id64 - ultimate_destination_finger_value;
3241 finger_table_index = PREDECESSOR_FINGER_ID;
3243 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3248 diff = ultimate_destination_finger_value - my_id64;
3249 finger_table_index = find_set_bit (diff);
3251 return finger_table_index;
3256 * Remove finger and its associated data structures from finger table.
3257 * @param existing_finger Finger to be removed which is in finger table.
3258 * @param finger_table_index Index in finger table where @a existing_finger
3262 remove_existing_finger (struct FingerInfo *existing_finger,
3263 unsigned int finger_table_index)
3265 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3267 /* If I am my own finger, then we have no trails. */
3268 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3271 existing_finger->is_present = GNUNET_NO;
3272 memset ((void *)&finger_table[finger_table_index], 0,
3273 sizeof (finger_table[finger_table_index]));
3277 /* For all other fingers, send trail teardown across all the trails to reach
3278 finger, and free the finger. */
3279 send_all_finger_trails_teardown (existing_finger);
3280 free_finger (existing_finger, finger_table_index);
3286 * Check if there is already an entry in finger_table at finger_table_index.
3287 * We get the finger_table_index from 64bit finger value we got from the network.
3288 * -- If yes, then select the closest finger.
3289 * -- If new and existing finger are same, then check if you can store more
3291 * -- If yes then add trail, else keep the best trails to reach to the
3293 * -- If the new finger is closest, remove the existing entry, send trail
3294 * teardown message across all the trails to reach the existing entry.
3295 * Add the new finger.
3296 * -- If new and existing finger are different, and existing finger is closest
3298 * -- Update current_search_finger_index.
3299 * @param finger_identity Peer Identity of new finger
3300 * @param finger_trail Trail to reach the new finger
3301 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3302 * @param is_predecessor Is this entry for predecessor in finger_table?
3303 * @param finger_value 64 bit value of finger identity that we got from network.
3304 * @param finger_trail_id Unique identifier of @finger_trail.
3307 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3308 const struct GNUNET_PeerIdentity *finger_trail,
3309 unsigned int finger_trail_length,
3310 unsigned int is_predecessor,
3311 uint64_t finger_value,
3312 struct GNUNET_HashCode finger_trail_id)
3314 struct FingerInfo *existing_finger;
3315 struct GNUNET_PeerIdentity closest_peer;
3316 struct FingerInfo *successor;
3317 unsigned int finger_table_index;
3319 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3320 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3322 /* Invalid finger_table_index. */
3323 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3325 GNUNET_break_op (0);
3329 /* New entry same as successor. */
3330 if ((0 != finger_table_index) &&
3331 (PREDECESSOR_FINGER_ID != finger_table_index))
3333 successor = &finger_table[0];
3334 if (GNUNET_NO == successor->is_present)
3339 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3340 &successor->finger_identity))
3342 current_search_finger_index = 0;
3346 struct FingerInfo prev_finger;
3347 prev_finger = finger_table[finger_table_index - 1];
3348 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3349 &prev_finger.finger_identity))
3351 current_search_finger_index--;
3356 existing_finger = &finger_table[finger_table_index];
3358 /* No entry present in finger_table for given finger map index. */
3359 if (GNUNET_NO == existing_finger->is_present)
3361 add_new_finger (finger_identity, finger_trail,
3362 finger_trail_length,
3363 finger_trail_id, finger_table_index);
3364 update_current_search_finger_index (finger_identity,
3365 finger_table_index);
3370 /* If existing entry and finger identity are not same. */
3371 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3374 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3379 /* If the new finger is the closest peer. */
3380 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer))
3382 remove_existing_finger (existing_finger, finger_table_index);
3383 add_new_finger (finger_identity, finger_trail, finger_trail_length,
3384 finger_trail_id, finger_table_index);
3388 /* Existing finger is the closest one. We need to send trail teardown
3389 across the trail setup in routing table of all the peers. */
3390 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3392 if (finger_trail_length > 0)
3393 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3394 GDS_ROUTING_SRC_TO_DEST,
3397 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3398 GDS_ROUTING_SRC_TO_DEST,
3405 /* If both new and existing entry are same as my_identity, then do nothing. */
3406 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3411 /* If the existing finger is not a friend. */
3413 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3414 &existing_finger->finger_identity))
3416 /* If there is space to store more trails. */
3417 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3418 add_new_trail (existing_finger, finger_trail,
3419 finger_trail_length, finger_trail_id);
3421 select_and_replace_trail (existing_finger, finger_trail,
3422 finger_trail_length, finger_trail_id);
3426 update_current_search_finger_index (finger_identity, finger_table_index);
3432 * FIXME: Check for loop in the request. If you already are part of put path,
3433 * then you need to reset the put path length.
3434 * Core handler for P2P put messages.
3435 * @param cls closure
3436 * @param peer sender of the request
3437 * @param message message
3438 * @return #GNUNET_OK to keep the connection open,
3439 * #GNUNET_SYSERR to close it (signal serious error)
3442 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3443 const struct GNUNET_MessageHeader *message)
3445 struct PeerPutMessage *put;
3446 struct GNUNET_PeerIdentity *put_path;
3447 struct GNUNET_PeerIdentity best_known_dest;
3448 struct GNUNET_HashCode intermediate_trail_id;
3449 struct GNUNET_PeerIdentity *next_hop;
3450 enum GNUNET_DHT_RouteOption options;
3451 struct GNUNET_HashCode test_key;
3455 size_t payload_size;
3458 #if ENABLE_MALICIOUS
3459 if(1 == act_malicious)
3461 DEBUG("I am malicious,dropping put request. \n");
3466 msize = ntohs (message->size);
3467 if (msize < sizeof (struct PeerPutMessage))
3469 GNUNET_break_op (0);
3473 put = (struct PeerPutMessage *) message;
3474 putlen = ntohl (put->put_path_length);
3478 sizeof (struct PeerPutMessage) +
3479 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3481 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3483 GNUNET_break_op (0);
3486 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
3487 GNUNET_STATISTICS_update (GDS_stats,
3489 ("# Bytes received from other peers"), (int64_t) msize,
3492 best_known_dest = put->best_known_destination;
3493 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3494 payload = &put_path[putlen];
3495 options = ntohl (put->options);
3496 intermediate_trail_id = put->intermediate_trail_id;
3498 payload_size = msize - (sizeof (struct PeerPutMessage) +
3499 putlen * sizeof (struct GNUNET_PeerIdentity));
3501 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3502 payload, payload_size, &test_key))
3505 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3507 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3508 GNUNET_break_op (0);
3509 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3510 "PUT with key `%s' for block with key %s\n",
3511 put_s, GNUNET_h2s_full (&test_key));
3512 GNUNET_free (put_s);
3517 GNUNET_break_op (0);
3520 /* cannot verify, good luck */
3524 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3526 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3527 ntohl (put->block_type),
3529 NULL, 0, /* bloom filer */
3530 NULL, 0, /* xquery */
3531 payload, payload_size))
3533 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3534 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3537 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3538 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3539 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3540 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3541 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3542 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3544 GNUNET_break_op (0);
3550 /* Check if you are present in the trail already. */
3552 for (i = 0; i < putlen; i++)
3554 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3561 //FIXME: always add yourself to the peer list not the sender.
3562 /* extend 'put path' by sender */
3563 struct GNUNET_PeerIdentity pp[putlen + 1];
3564 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3566 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3573 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3574 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3576 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3577 GDS_ROUTING_SRC_TO_DEST);
3578 if (NULL == next_hop)
3580 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3581 GNUNET_i2s(&my_identity), GNUNET_h2s(&intermediate_trail_id), __LINE__);
3582 GNUNET_STATISTICS_update (GDS_stats,
3583 gettext_noop ("# Next hop to forward the packet not found "
3584 "trail setup request, packet dropped."),
3586 GNUNET_break_op (0);
3592 struct Closest_Peer successor;
3593 key_value = GNUNET_ntohll (key_value);
3594 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3595 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3596 *next_hop = successor.next_hop;
3597 intermediate_trail_id = successor.trail_id;
3598 best_known_dest = successor.best_known_destination;
3601 GDS_CLIENTS_process_put (options,
3602 ntohl (put->block_type),
3603 ntohl (put->hop_count),
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 DEBUG("PUT destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(put->key)));
3615 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3616 &(put->key),putlen, pp, ntohl (put->block_type),
3617 payload_size, payload);
3621 GDS_NEIGHBOURS_send_put (&put->key,
3622 ntohl (put->block_type),ntohl (put->options),
3623 ntohl (put->desired_replication_level),
3624 best_known_dest, intermediate_trail_id, next_hop,
3625 ntohl (put->hop_count), putlen, pp,
3626 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3627 payload, payload_size);
3634 * FIXME: Check for loop in the request. If you already are part of get path,
3635 * then you need to reset the get path length.
3636 * Core handler for p2p get requests.
3638 * @param cls closure
3639 * @param peer sender of the request
3640 * @param message message
3641 * @return #GNUNET_OK to keep the connection open,
3642 * #GNUNET_SYSERR to close it (signal serious error)
3645 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3646 const struct GNUNET_MessageHeader *message)
3648 const struct PeerGetMessage *get;
3649 const struct GNUNET_PeerIdentity *get_path;
3650 struct GNUNET_PeerIdentity best_known_dest;
3651 struct GNUNET_HashCode intermediate_trail_id;
3652 struct GNUNET_PeerIdentity *next_hop;
3653 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];
3679 sizeof (struct PeerGetMessage) +
3680 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3682 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3684 GNUNET_break_op (0);
3687 DEBUG("PUT FOR DATA_SIZE = %lu\n",msize);
3688 GNUNET_STATISTICS_update (GDS_stats,
3690 ("# Bytes received from other peers"), msize,
3693 /* Add sender to get path */
3694 struct GNUNET_PeerIdentity gp[get_length + 1];
3696 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3697 gp[get_length] = *peer;
3698 get_length = get_length + 1;
3700 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3701 key_value = GNUNET_ntohll (key_value);
3703 /* I am not the final destination. I am part of trail to reach final dest. */
3704 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3706 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3707 GDS_ROUTING_SRC_TO_DEST);
3708 if (NULL == next_hop)
3710 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3711 GNUNET_i2s(&my_identity), GNUNET_h2s(&intermediate_trail_id), __LINE__);
3712 GNUNET_STATISTICS_update (GDS_stats,
3713 gettext_noop ("# Next hop to forward the packet not found "
3714 "GET request, packet dropped."),
3722 struct Closest_Peer successor;
3724 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3725 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3726 *next_hop = successor.next_hop;
3727 best_known_dest = successor.best_known_destination;
3728 intermediate_trail_id = successor.trail_id;
3731 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3732 get->desired_replication_level, get->get_path_length,
3734 /* I am the final destination. */
3735 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3737 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(get->key)));
3738 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3740 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3741 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3742 get_length = get_length + 1;
3744 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3745 get_length, final_get_path,
3746 &final_get_path[get_length-2], &my_identity);
3750 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3751 get->desired_replication_level, best_known_dest,
3752 intermediate_trail_id, next_hop, 0,
3760 * Core handler for get result
3761 * @param cls closure
3762 * @param peer sender of the request
3763 * @param message message
3764 * @return #GNUNET_OK to keep the connection open,
3765 * #GNUNET_SYSERR to close it (signal serious error)
3768 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3769 const struct GNUNET_MessageHeader *message)
3771 const struct PeerGetResultMessage *get_result;
3772 const struct GNUNET_PeerIdentity *get_path;
3773 const struct GNUNET_PeerIdentity *put_path;
3774 const void *payload;
3775 size_t payload_size;
3777 unsigned int getlen;
3778 unsigned int putlen;
3779 int current_path_index;
3781 msize = ntohs (message->size);
3782 if (msize < sizeof (struct PeerGetResultMessage))
3784 GNUNET_break_op (0);
3788 get_result = (const struct PeerGetResultMessage *)message;
3789 getlen = ntohl (get_result->get_path_length);
3790 putlen = ntohl (get_result->put_path_length);
3793 sizeof (struct PeerGetResultMessage) +
3794 getlen * sizeof (struct GNUNET_PeerIdentity) +
3795 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3797 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3799 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3801 GNUNET_break_op (0);
3804 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3805 GNUNET_STATISTICS_update (GDS_stats,
3807 ("# Bytes received from other peers"), msize,
3810 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3811 get_path = &put_path[putlen];
3812 payload = (const void *) &get_path[getlen];
3813 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3814 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3816 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3818 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3819 getlen, get_path, putlen,
3820 put_path, get_result->type, payload_size, payload);
3825 current_path_index = search_my_index (get_path, getlen);
3826 if (-1 == current_path_index )
3828 DEBUG ("No entry found in get path.\n");
3830 return GNUNET_SYSERR;
3832 if((getlen + 1) == current_path_index)
3834 DEBUG("Present twice in get path. Not allowed. \n");
3836 return GNUNET_SYSERR;
3838 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3839 &get_path[current_path_index - 1],
3840 &(get_result->querying_peer), putlen, put_path,
3841 getlen, get_path, get_result->expiration_time,
3842 payload, payload_size);
3845 return GNUNET_SYSERR;
3850 * Find the next hop to pass trail setup message. First find the local best known
3851 * hop from your own identity, friends and finger. If you were part of trail,
3852 * then get the next hop from routing table. Compare next_hop from routing table
3853 * and local best known hop, and return the closest one to final_dest_finger_val
3854 * @param final_dest_finger_val 64 bit value of finger identity
3855 * @param intermediate_trail_id If you are part of trail to reach to some other
3856 * finger, then it is the trail id to reach to
3857 * that finger, else set to 0.
3858 * @param is_predecessor Are we looking for closest successor or predecessor.
3859 * @param current_dest In case you are part of trail, then finger to which
3860 * we should forward the message. Else my own identity
3861 * @return Closest Peer for @a final_dest_finger_val
3863 static struct Closest_Peer
3864 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3865 struct GNUNET_HashCode intermediate_trail_id,
3866 unsigned int is_predecessor,
3867 struct GNUNET_PeerIdentity prev_hop,
3868 struct GNUNET_PeerIdentity source,
3869 struct GNUNET_PeerIdentity *current_dest)
3871 struct Closest_Peer peer;
3873 /* Find a local best known peer. */
3874 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3876 /* Am I just a part of a trail towards a finger (current_destination)? */
3877 /* Select best successor among one found locally and current_destination
3878 * that we got from network.*/
3879 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3880 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3883 struct GNUNET_PeerIdentity closest_peer;
3885 closest_peer = select_closest_peer (&peer.best_known_destination,
3887 final_dest_finger_val,
3890 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3891 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
3893 struct GNUNET_PeerIdentity *next_hop;
3895 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3896 GDS_ROUTING_SRC_TO_DEST);
3897 /* It may happen that trail teardown message got delayed and hence,
3898 the previous hop sent the message over intermediate trail id.In that
3899 case next_hop could be NULL. */
3900 if(NULL != next_hop)
3902 peer.next_hop = *next_hop;
3903 peer.best_known_destination = *current_dest;
3904 peer.trail_id = intermediate_trail_id;
3913 * Core handle for PeerTrailSetupMessage.
3914 * @param cls closure
3915 * @param message message
3916 * @param peer peer identity this notification is about
3917 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3920 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3921 const struct GNUNET_MessageHeader *message)
3923 const struct PeerTrailSetupMessage *trail_setup;
3924 const struct GNUNET_PeerIdentity *trail_peer_list;
3925 struct GNUNET_PeerIdentity current_dest;
3926 struct FriendInfo *target_friend;
3927 struct GNUNET_PeerIdentity source;
3928 uint64_t final_dest_finger_val;
3929 struct GNUNET_HashCode intermediate_trail_id;
3930 struct GNUNET_HashCode trail_id;
3931 unsigned int is_predecessor;
3932 uint32_t trail_length;
3936 msize = ntohs (message->size);
3937 if (msize < sizeof (struct PeerTrailSetupMessage))
3939 GNUNET_break_op (0);
3940 return GNUNET_SYSERR;
3943 trail_setup = (const struct PeerTrailSetupMessage *) message;
3944 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3945 sizeof (struct GNUNET_PeerIdentity) != 0)
3947 GNUNET_break_op (0);
3950 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3951 sizeof (struct GNUNET_PeerIdentity);
3953 GNUNET_STATISTICS_update (GDS_stats,
3955 ("# Bytes received from other peers"), msize,
3958 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3959 current_dest = trail_setup->best_known_destination;
3960 trail_id = trail_setup->trail_id;
3961 final_dest_finger_val =
3962 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3963 source = trail_setup->source_peer;
3964 is_predecessor = ntohl (trail_setup->is_predecessor);
3965 intermediate_trail_id = trail_setup->intermediate_trail_id;
3967 /* Did the friend insert its ID in the trail list? */
3968 if (trail_length > 0 &&
3969 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
3971 GNUNET_break_op (0);
3972 return GNUNET_SYSERR;
3975 /* If I was the source and got the message back, then set trail length to 0.*/
3976 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3981 /* Check if you are friend of source. */
3982 if (trail_length > 1)
3984 if(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source))
3986 /* If I am a friend, then I can be the first contact, so make
3987 trail length 0. We are going to add ourself later in the code.*/
3993 /* Check if you are present in the trail seen so far? */
3994 for (i = 0; i < trail_length ; i++)
3996 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
3998 trail_length = i; /* Check that you add yourself again */
4004 /* Is my routing table full? */
4005 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4007 GNUNET_assert (NULL !=
4009 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4010 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4011 my_identity, is_predecessor,
4012 trail_peer_list, trail_length,
4013 trail_id, target_friend,
4014 CONGESTION_TIMEOUT);
4018 /* Get the next hop to forward the trail setup request. */
4019 struct Closest_Peer next_peer =
4020 get_local_best_known_next_hop (final_dest_finger_val,
4021 intermediate_trail_id,
4027 /* Am I the final destination? */
4028 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4031 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4033 finger_table_add (my_identity, NULL, 0, is_predecessor,
4034 final_dest_finger_val, trail_id);
4038 if (trail_length > 0)
4040 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4041 &trail_peer_list[trail_length-1]);
4044 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4046 if (NULL == target_friend)
4048 GNUNET_break_op (0);
4049 return GNUNET_SYSERR;
4052 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4053 GDS_NEIGHBOURS_send_trail_setup_result (source,
4055 target_friend, trail_length,
4058 final_dest_finger_val,trail_id);
4060 else /* I'm not the final destination. */
4062 GNUNET_assert (NULL !=
4064 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4065 &next_peer.next_hop)));
4067 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4069 /* Add yourself to list of peers. */
4070 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4072 memcpy (peer_list, trail_peer_list,
4073 trail_length * sizeof (struct GNUNET_PeerIdentity));
4074 peer_list[trail_length] = my_identity;
4076 GDS_NEIGHBOURS_send_trail_setup (source,
4077 final_dest_finger_val,
4078 next_peer.best_known_destination,
4079 target_friend, trail_length + 1, peer_list,
4080 is_predecessor, trail_id,
4081 next_peer.trail_id);
4084 GDS_NEIGHBOURS_send_trail_setup (source,
4085 final_dest_finger_val,
4086 next_peer.best_known_destination,
4087 target_friend, 0, NULL,
4088 is_predecessor, trail_id,
4089 next_peer.trail_id);
4096 * Core handle for p2p trail setup result messages.
4098 * @param message message
4099 * @param peer sender of this message.
4100 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4103 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4104 const struct GNUNET_MessageHeader *message)
4106 const struct PeerTrailSetupResultMessage *trail_result;
4107 const struct GNUNET_PeerIdentity *trail_peer_list;
4108 struct GNUNET_PeerIdentity next_hop;
4109 struct FriendInfo *target_friend;
4110 struct GNUNET_PeerIdentity querying_peer;
4111 struct GNUNET_PeerIdentity finger_identity;
4112 uint32_t trail_length;
4113 uint64_t ulitmate_destination_finger_value;
4114 uint32_t is_predecessor;
4115 struct GNUNET_HashCode trail_id;
4119 msize = ntohs (message->size);
4120 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4122 GNUNET_break_op (0);
4126 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4127 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4128 sizeof (struct GNUNET_PeerIdentity) != 0)
4130 GNUNET_break_op (0);
4133 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4134 sizeof (struct GNUNET_PeerIdentity);
4136 GNUNET_STATISTICS_update (GDS_stats,
4138 ("# Bytes received from other peers"), msize,
4141 is_predecessor = ntohl (trail_result->is_predecessor);
4142 querying_peer = trail_result->querying_peer;
4143 finger_identity = trail_result->finger_identity;
4144 trail_id = trail_result->trail_id;
4145 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4146 ulitmate_destination_finger_value =
4147 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4149 /* Am I the one who initiated the query? */
4150 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4152 /* Check that you got the message from the correct peer. */
4153 if (trail_length > 0)
4155 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4160 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4164 GDS_ROUTING_add (trail_id, my_identity, *peer);
4165 finger_table_add (finger_identity, trail_peer_list, trail_length,
4166 is_predecessor, ulitmate_destination_finger_value, trail_id);
4170 /* Get my location in the trail. */
4171 my_index = search_my_index (trail_peer_list, trail_length);
4174 DEBUG ("Not found in trail\n");
4176 return GNUNET_SYSERR;
4179 if ((trail_length + 1) == my_index)
4181 DEBUG ("Found twice in trail.\n");
4183 return GNUNET_SYSERR;
4186 //TODO; Refactor code here and above to check if sender peer is correct
4189 if(trail_length > 1)
4190 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4193 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4195 next_hop = trail_result->querying_peer;
4199 if(my_index == trail_length - 1)
4202 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4207 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4209 next_hop = trail_peer_list[my_index - 1];
4212 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4213 if (NULL == target_friend)
4215 GNUNET_break_op (0);
4216 return GNUNET_SYSERR;
4219 GDS_ROUTING_add (trail_id, next_hop, *peer);
4220 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4221 target_friend, trail_length, trail_peer_list,
4223 ulitmate_destination_finger_value,
4231 * @param trail Trail to be inverted
4232 * @param trail_length Total number of peers in the trail.
4233 * @return Updated trail
4235 static struct GNUNET_PeerIdentity *
4236 invert_trail (const struct GNUNET_PeerIdentity *trail,
4237 unsigned int trail_length)
4241 struct GNUNET_PeerIdentity *inverted_trail;
4243 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4246 j = trail_length - 1;
4247 while (i < trail_length)
4249 inverted_trail[i] = trail[j];
4254 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4255 &inverted_trail[0]));
4256 return inverted_trail;
4261 * Return the shortest trail among all the trails to reach to finger from me.
4262 * @param finger Finger
4263 * @param shortest_trail_length[out] Trail length of shortest trail from me
4265 * @return Shortest trail.
4267 static struct GNUNET_PeerIdentity *
4268 get_shortest_trail (struct FingerInfo *finger,
4269 unsigned int *trail_length)
4271 struct Trail *trail;
4272 unsigned int flag = 0;
4273 unsigned int shortest_trail_index = 0;
4274 int shortest_trail_length = -1;
4275 struct Trail_Element *trail_element;
4276 struct GNUNET_PeerIdentity *trail_list;
4279 trail = GNUNET_new (struct Trail);
4281 /* Get the shortest trail to reach to current successor. */
4282 for (i = 0; i < finger->trails_count; i++)
4284 trail = &finger->trail_list[i];
4288 shortest_trail_index = i;
4289 shortest_trail_length = trail->trail_length;
4294 if (shortest_trail_length > trail->trail_length)
4296 shortest_trail_index = i;
4297 shortest_trail_length = trail->trail_length;
4302 /* Copy the shortest trail and return. */
4303 trail = &finger->trail_list[shortest_trail_index];
4304 trail_element = trail->trail_head;
4306 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4307 shortest_trail_length);
4309 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4311 trail_list[i] = trail_element->peer;
4314 GNUNET_assert(shortest_trail_length != -1);
4316 *trail_length = shortest_trail_length;
4322 * Check if trail_1 and trail_2 have any common element. If yes then join
4323 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4324 * @param trail_1 Trail from source to me, NOT including endpoints.
4325 * @param trail_1_len Total number of peers @a trail_1
4326 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4327 * @param trail_2_len Total number of peers @a trail_2
4328 * @param joined_trail_len Total number of peers in combined trail of trail_1
4330 * @return Joined trail.
4332 static struct GNUNET_PeerIdentity *
4333 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4334 unsigned int trail_1_len,
4335 struct GNUNET_PeerIdentity *trail_2,
4336 unsigned int trail_2_len,
4337 unsigned int *joined_trail_len)
4339 struct GNUNET_PeerIdentity *joined_trail;
4344 for (i = 0; i < trail_1_len; i++)
4346 for (j = 0; j < trail_2_len; j++)
4348 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4351 *joined_trail_len = i + (trail_2_len - j);
4352 joined_trail = GNUNET_malloc (*joined_trail_len *
4353 sizeof(struct GNUNET_PeerIdentity));
4356 /* Copy all the elements from 0 to i into joined_trail. */
4357 for(k = 0; k < ( i+1); k++)
4359 joined_trail[k] = trail_1[k];
4362 /* Increment j as entry stored is same as entry stored at i*/
4365 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4366 while(k <= (*joined_trail_len - 1))
4368 joined_trail[k] = trail_2[j];
4373 return joined_trail;
4377 /* Here you should join the trails. */
4378 *joined_trail_len = trail_1_len + trail_2_len + 1;
4379 joined_trail = GNUNET_malloc (*joined_trail_len *
4380 sizeof(struct GNUNET_PeerIdentity));
4383 for(i = 0; i < trail_1_len;i++)
4385 joined_trail[i] = trail_1[i];
4388 joined_trail[i] = my_identity;
4391 for (j = 0; i < *joined_trail_len; i++,j++)
4393 joined_trail[i] = trail_2[j];
4396 return joined_trail;
4401 * Return the trail from source to my current predecessor. Check if source
4402 * is already part of the this trail, if yes then return the shorten trail.
4403 * @param current_trail Trail from source to me, NOT including the endpoints.
4404 * @param current_trail_length Number of peers in @a current_trail.
4405 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4406 * source to my predecessor, NOT including
4408 * @return Trail from source to my predecessor.
4410 static struct GNUNET_PeerIdentity *
4411 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4412 const struct GNUNET_PeerIdentity *trail_src_to_me,
4413 unsigned int trail_src_to_me_len,
4414 unsigned int *trail_src_to_curr_pred_length)
4416 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4417 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4418 unsigned int trail_me_to_curr_pred_length;
4419 struct FingerInfo *current_predecessor;
4423 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4425 /* Check if trail_src_to_me contains current_predecessor. */
4426 for (i = 0; i < trail_src_to_me_len; i++)
4428 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4429 ¤t_predecessor->finger_identity))
4433 *trail_src_to_curr_pred_length = i;
4438 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4439 sizeof(struct GNUNET_PeerIdentity));
4440 for(j = 0; j < i;j++)
4441 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4442 return trail_src_to_curr_pred;
4446 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4447 &trail_me_to_curr_pred_length);
4449 /* Check if trail contains the source_peer. */
4450 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4452 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4453 &trail_me_to_curr_pred[i]))
4456 /* Source is NOT part of trail. */
4459 /* Source is the last element in the trail to reach to my pred.
4460 Source is direct friend of the pred. */
4461 if (trail_me_to_curr_pred_length == i)
4463 *trail_src_to_curr_pred_length = 0;
4467 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4468 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4469 *trail_src_to_curr_pred_length);
4471 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4473 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4475 GNUNET_free_non_null(trail_me_to_curr_pred);
4476 return trail_src_to_curr_pred;
4480 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4481 trail_src_to_me_len,
4482 trail_me_to_curr_pred,
4483 trail_me_to_curr_pred_length,
4485 *trail_src_to_curr_pred_length = len;
4486 GNUNET_free_non_null(trail_me_to_curr_pred);
4487 return trail_src_to_curr_pred;
4492 * Add finger as your predecessor. To add, first generate a new trail id, invert
4493 * the trail to get the trail from me to finger, add an entry in your routing
4494 * table, send add trail message to peers which are part of trail from me to
4495 * finger and add finger in finger table.
4498 * @param trail_length
4501 update_predecessor (struct GNUNET_PeerIdentity finger,
4502 struct GNUNET_PeerIdentity *trail,
4503 unsigned int trail_length)
4505 struct GNUNET_HashCode trail_to_new_predecessor_id;
4506 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4507 struct FriendInfo *target_friend;
4509 /* Generate trail id for trail from me to new predecessor = finger. */
4510 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4511 &trail_to_new_predecessor_id,
4512 sizeof (trail_to_new_predecessor_id));
4514 /* Finger is a friend. */
4515 if (trail_length == 0)
4517 trail_to_new_predecessor = NULL;
4518 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4519 GNUNET_assert (NULL != (target_friend =
4520 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4525 /* Invert the trail to get the trail from me to finger, NOT including the
4527 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4528 &trail[trail_length-1]));
4530 trail_to_new_predecessor = invert_trail (trail, trail_length);
4532 /* Add an entry in your routing table. */
4533 GDS_ROUTING_add (trail_to_new_predecessor_id,
4535 trail_to_new_predecessor[0]);
4537 GNUNET_assert (NULL != (target_friend =
4538 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4539 &trail_to_new_predecessor[0])));
4540 GNUNET_assert (NULL != (
4541 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4542 &trail[trail_length - 1])));
4545 /* Add entry in routing table of all peers that are part of trail from me
4546 to finger, including finger. */
4547 GDS_NEIGHBOURS_send_add_trail (my_identity,
4549 trail_to_new_predecessor_id,
4550 trail_to_new_predecessor,
4554 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4555 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4556 GNUNET_free_non_null(trail_to_new_predecessor);
4561 * Check if you already have a predecessor. If not then add finger as your
4562 * predecessor. If you have predecessor, then compare two peer identites.
4563 * If finger is correct predecessor, then remove the old entry, add finger in
4564 * finger table and send add_trail message to add the trail in the routing
4565 * table of all peers which are part of trail to reach from me to finger.
4566 * @param finger New peer which may be our predecessor.
4567 * @param trail List of peers to reach from @finger to me.
4568 * @param trail_length Total number of peer in @a trail.
4571 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4572 struct GNUNET_PeerIdentity *trail,
4573 unsigned int trail_length)
4575 struct FingerInfo *current_predecessor;
4576 struct GNUNET_PeerIdentity closest_peer;
4577 uint64_t predecessor_value;
4578 unsigned int is_predecessor = 1;
4580 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4582 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4584 /* No predecessor. Add finger as your predecessor. */
4585 if (GNUNET_NO == current_predecessor->is_present)
4587 update_predecessor (finger, trail, trail_length);
4591 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4597 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4598 closest_peer = select_closest_peer (&finger,
4599 ¤t_predecessor->finger_identity,
4600 predecessor_value, is_predecessor);
4602 /* Finger is the closest predecessor. Remove the existing one and add the new
4604 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4606 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4607 update_predecessor (finger, trail, trail_length);
4615 * Core handle for p2p verify successor messages.
4616 * @param cls closure
4617 * @param message message
4618 * @param peer peer identity this notification is about
4619 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4622 handle_dht_p2p_verify_successor(void *cls,
4623 const struct GNUNET_PeerIdentity *peer,
4624 const struct GNUNET_MessageHeader *message)
4626 const struct PeerVerifySuccessorMessage *vsm;
4627 struct GNUNET_HashCode trail_id;
4628 struct GNUNET_PeerIdentity successor;
4629 struct GNUNET_PeerIdentity source_peer;
4630 struct GNUNET_PeerIdentity *trail;
4631 struct GNUNET_PeerIdentity *next_hop;
4632 struct FingerInfo current_predecessor;
4633 struct FriendInfo *target_friend;
4634 unsigned int trail_src_to_curr_pred_len = 0;
4635 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4636 unsigned int trail_length;
4639 msize = ntohs (message->size);
4641 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4643 GNUNET_break_op (0);
4647 vsm = (const struct PeerVerifySuccessorMessage *) message;
4648 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4649 sizeof (struct GNUNET_PeerIdentity);
4650 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4651 sizeof (struct GNUNET_PeerIdentity) != 0)
4653 GNUNET_break_op (0);
4657 GNUNET_STATISTICS_update (GDS_stats,
4659 ("# Bytes received from other peers"), msize,
4662 trail_id = vsm->trail_id;
4663 source_peer = vsm->source_peer;
4664 successor = vsm->successor;
4665 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4668 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4670 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4672 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4673 if (NULL == next_hop)
4675 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
4676 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
4677 GNUNET_break_op (0);
4681 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4683 if(NULL == target_friend)
4688 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4689 trail_id, trail, trail_length,
4694 /* I am the destination of this message. */
4696 /* Check if the source_peer could be our predecessor and if yes then update
4698 compare_and_update_predecessor (source_peer, trail, trail_length);
4699 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4701 /* Is source of this message NOT my predecessor. */
4702 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4705 trail_src_to_curr_pred =
4706 get_trail_src_to_curr_pred (source_peer,
4709 &trail_src_to_curr_pred_len);
4713 trail_src_to_curr_pred_len = trail_length;
4716 trail_src_to_curr_pred =
4717 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4718 *trail_src_to_curr_pred_len);
4719 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4721 trail_src_to_curr_pred[i] = trail[i];
4725 GNUNET_assert (NULL !=
4727 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4728 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4729 current_predecessor.finger_identity,
4730 trail_id, trail_src_to_curr_pred,
4731 trail_src_to_curr_pred_len,
4732 GDS_ROUTING_DEST_TO_SRC,
4734 GNUNET_free_non_null(trail_src_to_curr_pred);
4740 * If the trail from me to my probable successor contains a friend not
4741 * at index 0, then we can shorten the trail.
4742 * @param probable_successor Peer which is our probable successor
4743 * @param trail_me_to_probable_successor Peers in path from me to my probable
4744 * successor, NOT including the endpoints.
4745 * @param trail_me_to_probable_successor_len Total number of peers in
4746 * @a trail_me_to_probable_succesor.
4747 * @return Updated trail, if any friend found.
4748 * Else the trail_me_to_probable_successor.
4750 struct GNUNET_PeerIdentity *
4751 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4752 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4753 unsigned int trail_me_to_probable_successor_len,
4754 unsigned int *trail_to_new_successor_length)
4758 struct GNUNET_PeerIdentity *trail_to_new_successor;
4760 /* Probable successor is a friend */
4761 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4762 &probable_successor))
4764 trail_to_new_successor = NULL;
4765 *trail_to_new_successor_length = 0;
4766 return trail_to_new_successor;
4769 /* Is there any friend of yours in this trail. */
4770 if(trail_me_to_probable_successor_len > 1)
4772 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4774 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4775 &trail_me_to_probable_successor[i]))
4778 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4779 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4780 *trail_to_new_successor_length);
4783 for(j = 0;j < *trail_to_new_successor_length;i++,j++)
4785 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4788 return trail_to_new_successor;
4792 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4793 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4798 * Check if the peer which sent us verify successor result message is still ours
4799 * successor or not. If not, then compare existing successor and probable successor.
4800 * In case probable successor is the correct successor, remove the existing
4801 * successor. Add probable successor as new successor. Send notify new successor
4802 * message to new successor.
4803 * @param curr_succ Peer to which we sent the verify successor message. It may
4804 * or may not be our real current successor, as we may have few iterations of
4805 * find finger trail task.
4806 * @param probable_successor Peer which should be our successor accroding to @a
4808 * @param trail List of peers to reach from me to @a probable successor, NOT including
4810 * @param trail_length Total number of peers in @a trail.
4813 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4814 struct GNUNET_PeerIdentity probable_successor,
4815 const struct GNUNET_PeerIdentity *trail,
4816 unsigned int trail_length)
4818 struct FingerInfo *current_successor;
4819 struct GNUNET_PeerIdentity closest_peer;
4820 struct GNUNET_HashCode trail_id;
4821 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4822 struct FriendInfo *target_friend;
4823 unsigned int trail_me_to_probable_succ_len;
4824 unsigned int is_predecessor = GNUNET_NO;
4825 uint64_t successor_value;
4827 current_successor = &finger_table[0];
4828 successor_value = compute_finger_identity_value(0);
4830 /* If probable successor is same as current_successor, do nothing. */
4831 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
4832 ¤t_successor->finger_identity))
4835 closest_peer = select_closest_peer (&probable_successor,
4836 ¤t_successor->finger_identity,
4837 successor_value, is_predecessor);
4839 /* If the current_successor in the finger table is closest, then do nothing. */
4840 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
4841 ¤t_successor->finger_identity))
4843 /* Code for testing ONLY: Store the successor for path tracking */
4844 // track_topology = 1;
4845 if ((NULL != GDS_stats))
4851 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4852 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4853 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4854 GNUNET_free (my_id_str);
4855 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4861 /* Probable successor is the closest peer.*/
4862 if(trail_length > 0)
4864 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4869 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4870 &probable_successor));
4873 trail_me_to_probable_succ_len = 0;
4874 trail_me_to_probable_succ =
4875 check_trail_me_to_probable_succ (probable_successor,
4876 trail, trail_length,
4877 &trail_me_to_probable_succ_len);
4879 /* Remove the existing successor. */
4880 remove_existing_finger (current_successor, 0);
4882 /* TODO URGENT: Check if any peer is present more than once, if yes then shorten
4883 the trail. before sending it across the network. */
4884 /* Generate a new trail id to reach to your new successor. */
4885 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4886 &trail_id, sizeof (trail_id));
4888 if (trail_me_to_probable_succ_len > 0)
4890 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4891 GNUNET_assert (NULL !=
4893 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4894 &trail_me_to_probable_succ[0])));
4898 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4899 GNUNET_assert (NULL !=
4901 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4902 &probable_successor)));
4905 add_new_finger (probable_successor, trail_me_to_probable_succ,
4906 trail_me_to_probable_succ_len, trail_id, 0);
4908 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4909 trail_me_to_probable_succ,
4910 trail_me_to_probable_succ_len,
4918 * FIXME: Check for duplicate elements everywhere when you are making
4920 * Core handle for p2p verify successor result messages.
4921 * @param cls closure
4922 * @param message message
4923 * @param peer peer identity this notification is about
4924 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4927 handle_dht_p2p_verify_successor_result(void *cls,
4928 const struct GNUNET_PeerIdentity *peer,
4929 const struct GNUNET_MessageHeader *message)
4931 const struct PeerVerifySuccessorResultMessage *vsrm;
4932 enum GDS_ROUTING_trail_direction trail_direction;
4933 struct GNUNET_PeerIdentity querying_peer;
4934 struct GNUNET_HashCode trail_id;
4935 struct GNUNET_PeerIdentity *next_hop;
4936 struct FriendInfo *target_friend;
4937 struct GNUNET_PeerIdentity probable_successor;
4938 struct GNUNET_PeerIdentity current_successor;
4939 const struct GNUNET_PeerIdentity *trail;
4940 unsigned int trail_length;
4943 msize = ntohs (message->size);
4944 /* We send a trail to reach from old successor to new successor, if
4945 * old_successor != new_successor.*/
4946 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4948 GNUNET_break_op (0);
4952 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4953 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4954 sizeof (struct GNUNET_PeerIdentity);
4956 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4957 sizeof (struct GNUNET_PeerIdentity) != 0)
4959 GNUNET_break_op (0);
4963 GNUNET_STATISTICS_update (GDS_stats,
4965 ("# Bytes received from other peers"), msize,
4968 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4969 querying_peer = vsrm->querying_peer;
4970 trail_direction = ntohl (vsrm->trail_direction);
4971 trail_id = vsrm->trail_id;
4972 probable_successor = vsrm->probable_successor;
4973 current_successor = vsrm->current_successor;
4976 /* I am the querying_peer. */
4977 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4979 compare_and_update_successor (current_successor,
4980 probable_successor, trail, trail_length);
4984 /*If you are not the querying peer then pass on the message */
4985 if(NULL == (next_hop =
4986 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
4988 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
4989 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
4993 if (NULL == (target_friend =
4994 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
4999 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5000 vsrm->current_successor,
5001 probable_successor, trail_id,
5004 trail_direction, target_friend);
5010 * Core handle for p2p notify new successor messages.
5011 * @param cls closure
5012 * @param message message
5013 * @param peer peer identity this notification is about
5014 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5017 handle_dht_p2p_notify_new_successor(void *cls,
5018 const struct GNUNET_PeerIdentity *peer,
5019 const struct GNUNET_MessageHeader *message)
5021 const struct PeerNotifyNewSuccessorMessage *nsm;
5022 struct GNUNET_PeerIdentity *trail;
5023 struct GNUNET_PeerIdentity source;
5024 struct GNUNET_PeerIdentity new_successor;
5025 struct GNUNET_HashCode trail_id;
5026 struct GNUNET_PeerIdentity next_hop;
5027 struct FriendInfo *target_friend;
5030 uint32_t trail_length;
5032 msize = ntohs (message->size);
5034 /* We have the trail to reach from source to new successor. */
5035 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5037 GNUNET_break_op (0);
5041 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5042 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5043 sizeof (struct GNUNET_PeerIdentity);
5044 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5045 sizeof (struct GNUNET_PeerIdentity) != 0)
5047 GNUNET_break_op (0);
5051 GNUNET_STATISTICS_update (GDS_stats,
5053 ("# Bytes received from other peers"), msize,
5056 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5057 source = nsm->source_peer;
5058 new_successor = nsm->new_successor;
5059 trail_id = nsm->trail_id;
5062 //FIXME: add a check to make sure peer is correct.
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];
5098 /* Add an entry in routing table for trail from source to its new successor. */
5099 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5100 GNUNET_assert (NULL !=
5102 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5103 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5105 trail_id, target_friend);
5112 * Core handler for P2P trail rejection message
5113 * @param cls closure
5114 * @param message message
5115 * @param peer peer identity this notification is about
5116 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5119 handle_dht_p2p_trail_setup_rejection (void *cls,
5120 const struct GNUNET_PeerIdentity *peer,
5121 const struct GNUNET_MessageHeader *message)
5123 const struct PeerTrailRejectionMessage *trail_rejection;
5124 unsigned int trail_length;
5125 const struct GNUNET_PeerIdentity *trail_peer_list;
5126 struct FriendInfo *target_friend;
5127 struct GNUNET_TIME_Relative congestion_timeout;
5128 struct GNUNET_HashCode trail_id;
5129 struct GNUNET_PeerIdentity next_peer;
5130 struct GNUNET_PeerIdentity source;
5131 struct GNUNET_PeerIdentity *next_hop;
5132 uint64_t ultimate_destination_finger_value;
5133 unsigned int is_predecessor;
5136 msize = ntohs (message->size);
5137 /* We are passing the trail setup so far. */
5138 if (msize < sizeof (struct PeerTrailRejectionMessage))
5140 GNUNET_break_op (0);
5144 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5145 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5146 sizeof (struct GNUNET_PeerIdentity);
5147 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5148 sizeof (struct GNUNET_PeerIdentity) != 0)
5150 GNUNET_break_op (0);
5154 GNUNET_STATISTICS_update (GDS_stats,
5156 ("# Bytes received from other peers"), msize,
5159 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5160 is_predecessor = ntohl (trail_rejection->is_predecessor);
5161 congestion_timeout = trail_rejection->congestion_time;
5162 source = trail_rejection->source_peer;
5163 trail_id = trail_rejection->trail_id;
5164 ultimate_destination_finger_value =
5165 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5167 /* First set the congestion time of the friend that sent you this message. */
5168 GNUNET_assert (NULL !=
5170 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5171 target_friend->congestion_timestamp =
5172 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5173 congestion_timeout);
5175 /* I am the source peer which wants to setup the trail. Do nothing.
5176 * send_find_finger_trail_task is scheduled periodically.*/
5177 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5180 /* If I am congested then pass this message to peer before me in trail. */
5181 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5183 struct GNUNET_PeerIdentity *new_trail;
5184 unsigned int new_trail_length;
5186 /* Remove yourself from the trail setup so far. */
5187 if (trail_length == 1)
5190 new_trail_length = 0;
5195 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5196 sizeof (struct GNUNET_PeerIdentity));
5198 /* Remove myself from the trail. */
5199 new_trail_length = trail_length -1;
5200 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5201 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5204 GNUNET_assert (NULL !=
5206 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5207 GDS_NEIGHBOURS_send_trail_rejection (source,
5208 ultimate_destination_finger_value,
5209 my_identity, is_predecessor,
5210 new_trail,new_trail_length,trail_id,
5211 target_friend, CONGESTION_TIMEOUT);
5212 GNUNET_free (new_trail);
5216 struct Closest_Peer successor;
5217 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5219 /* Am I the final destination? */
5220 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5223 if (0 == trail_length)
5226 next_peer = trail_peer_list[trail_length-1];
5228 GNUNET_assert (NULL !=
5230 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5232 GDS_NEIGHBOURS_send_trail_setup_result (source,
5234 target_friend, trail_length,
5237 ultimate_destination_finger_value,
5242 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5244 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5245 peer_list[trail_length] = my_identity;
5247 GNUNET_assert (NULL !=
5249 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5251 GDS_NEIGHBOURS_send_trail_setup (source,
5252 ultimate_destination_finger_value,
5253 successor.best_known_destination,
5254 target_friend, trail_length + 1, peer_list,
5255 is_predecessor, trail_id,
5256 successor.trail_id);
5263 * Core handler for trail teardown message.
5264 * @param cls closure
5265 * @param message message
5266 * @param peer sender of this messsage.
5267 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5270 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5271 const struct GNUNET_MessageHeader *message)
5273 const struct PeerTrailTearDownMessage *trail_teardown;
5274 enum GDS_ROUTING_trail_direction trail_direction;
5275 struct GNUNET_HashCode trail_id;
5276 struct GNUNET_PeerIdentity *next_hop;
5279 msize = ntohs (message->size);
5281 /* Here we pass only the trail id. */
5282 if (msize != sizeof (struct PeerTrailTearDownMessage))
5284 GNUNET_break_op (0);
5288 GNUNET_STATISTICS_update (GDS_stats,
5290 ("# Bytes received from other peers"), msize,
5293 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5294 trail_direction = ntohl (trail_teardown->trail_direction);
5295 trail_id = trail_teardown->trail_id;
5297 /* Check if peer is the real peer from which we should get this message.*/
5298 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5300 GNUNET_assert (NULL != (prev_hop =
5301 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5302 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5305 return GNUNET_SYSERR;
5309 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5310 if (NULL == next_hop)
5312 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5313 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5315 return GNUNET_SYSERR;
5318 /* I am the next hop, which means I am the final destination. */
5319 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5321 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5326 /* If not final destination, then send a trail teardown message to next hop.*/
5327 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5328 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5329 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5337 * Core handle for p2p add trail message.
5338 * @param cls closure
5339 * @param message message
5340 * @param peer peer identity this notification is about
5341 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5344 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5345 const struct GNUNET_MessageHeader *message)
5347 const struct PeerAddTrailMessage *add_trail;
5348 const struct GNUNET_PeerIdentity *trail;
5349 struct GNUNET_HashCode trail_id;
5350 struct GNUNET_PeerIdentity destination_peer;
5351 struct GNUNET_PeerIdentity source_peer;
5352 struct GNUNET_PeerIdentity next_hop;
5353 unsigned int trail_length;
5354 unsigned int my_index;
5357 msize = ntohs (message->size);
5358 /* In this message we pass the whole trail from source to destination as we
5359 * are adding that trail.*/
5360 //FIXME: failed when run with 1000 pears. check why.
5361 if (msize < sizeof (struct PeerAddTrailMessage))
5363 GNUNET_break_op (0);
5367 add_trail = (const struct PeerAddTrailMessage *) message;
5368 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5369 sizeof (struct GNUNET_PeerIdentity);
5370 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5371 sizeof (struct GNUNET_PeerIdentity) != 0)
5373 GNUNET_break_op (0);
5377 GNUNET_STATISTICS_update (GDS_stats,
5379 ("# Bytes received from other peers"), msize,
5382 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5383 destination_peer = add_trail->destination_peer;
5384 source_peer = add_trail->source_peer;
5385 trail_id = add_trail->trail_id;
5387 //FIXME: add a check that sender peer is not malicious. Make it a generic
5388 // function so that it can be used in all other functions where we need the
5389 // same functionality.
5391 /* I am not the destination of the trail. */
5392 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5394 struct FriendInfo *target_friend;
5396 /* Get my location in the trail. */
5397 my_index = search_my_index (trail, trail_length);
5400 GNUNET_break_op (0);
5401 return GNUNET_SYSERR;
5403 if((trail_length + 1) == my_index)
5405 DEBUG ("Found twice in trail.\n");
5406 GNUNET_break_op (0);
5407 return GNUNET_SYSERR;
5409 if ((trail_length - 1) == my_index)
5411 next_hop = destination_peer;
5415 next_hop = trail[my_index + 1];
5418 /* Add in your routing table. */
5419 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5420 GNUNET_assert (NULL !=
5422 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5423 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5424 trail, trail_length, target_friend);
5427 /* I am the destination. Add an entry in routing table. */
5428 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5434 * Free the finger trail in which the first friend to reach to a finger is
5435 * disconnected_friend. Also remove entry from routing table for that particular
5437 * @param disconnected_friend PeerIdentity of friend which got disconnected
5438 * @param remove_finger Finger whose trail we need to check if it has
5439 * disconnected_friend as the first hop.
5440 * @return Total number of trails in which disconnected_friend was the first
5444 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5445 struct FingerInfo *remove_finger)
5447 unsigned int matching_trails_count;
5450 /* Number of trails with disconnected_friend as the first hop in the trail
5451 * to reach from me to remove_finger, NOT including endpoints. */
5452 matching_trails_count = 0;
5454 /* Iterate over all the trails of finger. */
5455 for (i = 0; i < remove_finger->trails_count; i++)
5457 struct Trail *trail;
5458 trail = &remove_finger->trail_list[i];
5460 /* This assertion is ensure that there are no gaps in the trail list.
5461 REMOVE IT AFTERWARDS. */
5462 GNUNET_assert (GNUNET_YES == trail->is_present);
5464 /* First friend to reach to finger is disconnected_peer. */
5465 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5466 disconnected_friend))
5468 struct GNUNET_PeerIdentity *next_hop;
5469 struct FriendInfo *remove_friend;
5471 GNUNET_assert (NULL !=
5473 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5474 disconnected_friend)));
5475 /* FIXME: removing no but check it. */
5476 //remove_friend->trails_count--;
5477 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5478 GDS_ROUTING_SRC_TO_DEST);
5480 /* Here it may happen that as all the peers got disconnected, the entry in
5481 routing table for that particular trail has been removed, because the
5482 previously disconnected peer was either a next hop or prev hop of that
5484 if (NULL == next_hop)
5486 //TODO UNDERSTAND why do you continue here?
5489 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5491 matching_trails_count++;
5492 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5495 trail->is_present = GNUNET_NO;
5498 return matching_trails_count;
5503 * Iterate over finger_table entries.
5504 * 0. Ignore finger which is my_identity or if no valid entry present at
5505 * that finger index.
5506 * 1. If disconnected_friend is a finger, then remove the routing entry from
5507 your own table. Free the trail.
5508 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5509 * 2.1 Remove all the trails and entry from routing table in which disconnected
5510 * friend is the first friend in the trail. If disconnected_friend is the
5511 * first friend in all the trails to reach finger, then remove the finger.
5512 * @param disconnected_friend Peer identity of friend which got disconnected.
5515 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5517 struct FingerInfo *remove_finger;
5518 struct FriendInfo *remove_friend;
5519 int removed_trails_count;
5522 /* Iterate over finger table entries. */
5523 for (i = 0; i < MAX_FINGERS; i++)
5525 remove_finger = &finger_table[i];
5527 /* No finger stored at this trail index. */
5528 if (GNUNET_NO == remove_finger->is_present)
5531 /* I am my own finger, then ignore this finger. */
5532 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5536 /* Is disconnected_peer a finger? */
5537 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5538 &remove_finger->finger_identity))
5540 struct GNUNET_PeerIdentity *next_hop;
5541 struct GNUNET_HashCode trail_id;
5542 /* FIXME: Just for check, remove it afterwards. Here finger is a friend.
5543 hence trail length should be 0*/
5544 GNUNET_assert (0 == remove_finger->trail_list[0].trail_length);
5545 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5546 trail_id = remove_finger->trail_list[0].trail_id;
5550 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5553 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5554 &remove_finger->finger_identity)));
5555 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5556 GNUNET_assert (NULL !=
5558 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5559 disconnected_peer)));
5561 //TODO should we handle the else case.
5564 remove_finger->trail_list[0].is_present = GNUNET_NO;
5565 //GNUNET_assert (0 != remove_friend->trails_count);
5566 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5567 remove_finger->is_present = GNUNET_NO;
5568 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5572 /* If finger is a friend but not disconnected_friend, then continue. */
5573 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5574 &remove_finger->finger_identity))
5577 /* Iterate over the list of trails to reach remove_finger. Check if
5578 * disconnected_friend is the first friend in any of the trail. */
5579 removed_trails_count = remove_matching_trails (disconnected_peer,
5581 remove_finger->trails_count =
5582 remove_finger->trails_count - removed_trails_count;
5583 /* All the finger trails had disconnected_friend as the first friend,
5584 * so free the finger. */
5585 if (remove_finger->trails_count == 0)
5587 remove_finger->is_present = GNUNET_NO;
5588 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5595 * Method called whenever a peer disconnects.
5597 * @param cls closure
5598 * @param peer peer identity this notification is about
5601 handle_core_disconnect (void *cls,
5602 const struct GNUNET_PeerIdentity *peer)
5604 struct FriendInfo *remove_friend;
5605 struct P2PPendingMessage *pos;
5606 unsigned int discarded;
5608 /* If disconnected to own identity, then return. */
5609 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5612 if(NULL == (remove_friend =
5613 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
5615 DEBUG("\n friend already disconnected.");
5618 /* Remove fingers with peer as first friend or if peer is a finger. */
5619 remove_matching_fingers (peer);
5621 /* Remove any trail from routing table of which peer is a part of. This function
5622 * internally sends a trail teardown message in the direction of which
5623 * disconnected peer is not part of. */
5624 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5626 /* Remove peer from friend_peermap. */
5627 GNUNET_assert (GNUNET_YES ==
5628 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5632 /* Remove all the messages queued in pending list of this peer is discarded.*/
5633 if (remove_friend->th != NULL)
5635 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
5636 remove_friend->th = NULL;
5640 while (NULL != (pos = remove_friend->head))
5642 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
5647 GNUNET_STATISTICS_update (GDS_stats,
5649 ("# Queued messages discarded (peer disconnected)"),
5650 discarded, GNUNET_NO);
5651 GNUNET_free (remove_friend);
5653 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5656 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5658 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5659 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5667 * Method called whenever a peer connects.
5669 * @param cls closure
5670 * @param peer_identity peer identity this notification is about
5673 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5675 struct FriendInfo *friend;
5677 /* Check for connect to self message */
5678 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5681 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5683 /* If peer already exists in our friend_peermap, then exit. */
5684 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5691 friend = GNUNET_new (struct FriendInfo);
5692 friend->id = *peer_identity;
5694 GNUNET_assert (GNUNET_OK ==
5695 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5696 peer_identity, friend,
5697 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5699 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5700 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5702 DEBUG ("sCHEDULING FINGER TASK");
5703 find_finger_trail_task_next_send_time.rel_value_us =
5704 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5705 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5706 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5707 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5713 * To be called on core init/fail.
5715 * @param cls service closure
5716 * @param identity the public identity of this peer
5719 core_init (void *cls,
5720 const struct GNUNET_PeerIdentity *identity)
5722 my_identity = *identity;
5725 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5726 my_id64 = GNUNET_ntohll (my_id64);
5727 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5728 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5734 * Initialize finger table entries.
5737 finger_table_init ()
5739 memset (&finger_table, 0, sizeof (finger_table));
5744 * Initialize neighbours subsystem.
5745 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5748 GDS_NEIGHBOURS_init (void)
5750 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5751 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5752 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5753 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5754 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5755 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5756 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5757 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5758 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5759 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5760 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5761 sizeof (struct PeerTrailTearDownMessage)},
5762 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5766 #if ENABLE_MALICIOUS
5771 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5772 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5773 GNUNET_NO, core_handlers);
5775 if (NULL == core_api)
5776 return GNUNET_SYSERR;
5778 //TODO: check size of this peer map?
5779 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5780 finger_table_init ();
5786 * Free the memory held up by trails of a finger.
5789 delete_finger_table_entries()
5794 for(i = 0; i < MAX_FINGERS; i++)
5796 if(GNUNET_NO == finger_table[i].is_present)
5799 for(j = 0; j < finger_table[i].trails_count; j++)
5801 free_trail(&finger_table[i].trail_list[i]);
5807 * Shutdown neighbours subsystem.
5810 GDS_NEIGHBOURS_done (void)
5812 if (NULL == core_api)
5815 GNUNET_CORE_disconnect (core_api);
5818 delete_finger_table_entries();
5820 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5821 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5822 friend_peermap = NULL;
5824 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5827 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5828 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5831 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5833 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5834 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5842 * @return my identity
5844 struct GNUNET_PeerIdentity
5845 GDS_NEIGHBOURS_get_my_id (void)
5850 /* end of gnunet-service-xdht_neighbours.c */