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_MILLISECONDS, 500)
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, 60)
86 * How long at most to wait for transmission of a request to a friend ?
88 #define PENDING_MESSAGE_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
91 * Duration for which I may remain congested.
92 * Note: Its a static value. In future, a peer may do some analysis and calculate
93 * congestion_timeout based on 'some' parameters.
95 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
98 * Maximum number of trails allowed to go through a friend.
100 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
103 * Maximum number of trails stored per finger.
105 #define MAXIMUM_TRAILS_PER_FINGER 1
108 * Finger map index for predecessor entry in finger table.
110 #define PREDECESSOR_FINGER_ID 64
113 * Wrap around in peer identity circle.
115 #define PEER_IDENTITES_WRAP_AROUND pow(2, 64) - 1
118 * FIXME: Its use only at 3 places check if you can remove it.
119 * To check if a finger is predecessor or not.
121 enum GDS_NEIGHBOURS_finger_type
123 GDS_FINGER_TYPE_PREDECESSOR = 1,
124 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
127 GNUNET_NETWORK_STRUCT_BEGIN
132 struct PeerPutMessage
135 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
137 struct GNUNET_MessageHeader header;
142 uint32_t options GNUNET_PACKED;
147 uint32_t block_type GNUNET_PACKED;
152 uint32_t hop_count GNUNET_PACKED;
155 * Replication level for this message
156 * In the current implementation, this value is not used.
158 uint32_t desired_replication_level GNUNET_PACKED;
161 * Length of the PUT path that follows (if tracked).
163 uint32_t put_path_length GNUNET_PACKED;
166 * Best known destination (could be my friend or finger) which should
167 * get this message next.
169 struct GNUNET_PeerIdentity best_known_destination;
172 * In case best_known_destination is a finger, then trail to reach
173 * to that finger. Else its default value is 0.
175 struct GNUNET_HashCode intermediate_trail_id;
178 * When does the content expire?
180 struct GNUNET_TIME_AbsoluteNBO expiration_time;
183 * The key to store the value under.
185 struct GNUNET_HashCode key GNUNET_PACKED;
187 /* put path (if tracked) */
196 struct PeerGetMessage
199 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
201 struct GNUNET_MessageHeader header;
206 uint32_t options GNUNET_PACKED;
209 * Desired content type.
211 uint32_t block_type GNUNET_PACKED;
216 uint32_t hop_count GNUNET_PACKED;
219 * Desired replication level for this request.
220 * In the current implementation, this value is not used.
222 uint32_t desired_replication_level GNUNET_PACKED;
225 * Total number of peers in get path.
227 unsigned int get_path_length;
230 * Best known destination (could be my friend or finger) which should
231 * get this message next.
233 struct GNUNET_PeerIdentity best_known_destination;
236 * In case best_known_destination is a finger, then trail to reach
237 * to that finger. Else its default value is 0.
239 struct GNUNET_HashCode intermediate_trail_id;
242 * The key we are looking for.
244 struct GNUNET_HashCode key;
247 /* struct GNUNET_PeerIdentity[]*/
253 struct PeerGetResultMessage
256 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
258 struct GNUNET_MessageHeader header;
261 * The type for the data.
263 uint32_t type GNUNET_PACKED;
266 * Number of peers recorded in the outgoing path from source to the
267 * stored location of this message.
269 uint32_t put_path_length GNUNET_PACKED;
272 * Length of the GET path that follows (if tracked).
274 uint32_t get_path_length GNUNET_PACKED;
277 * Peer which queried for get and should get the result.
279 struct GNUNET_PeerIdentity querying_peer;
282 * When does the content expire?
284 struct GNUNET_TIME_Absolute expiration_time;
287 * The key of the corresponding GET request.
289 struct GNUNET_HashCode key;
291 /* put path (if tracked) */
293 /* get path (if tracked) */
300 * P2P Trail setup message
302 struct PeerTrailSetupMessage
305 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
307 struct GNUNET_MessageHeader header;
310 * Is source_peer trying to setup the trail to a predecessor or any finger.
312 uint32_t is_predecessor;
315 * Peer closest to this value will be our finger.
317 uint64_t final_destination_finger_value;
320 * Source peer which wants to setup the trail to one of its finger.
322 struct GNUNET_PeerIdentity source_peer;
325 * Best known destination (could be my friend or finger) which should
326 * get this message next.
328 * FIXME: this could be removed if we include trail_source / trail_dest
329 * in the routing table. This way we save 32 bytes of bandwidth by using
330 * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID))
332 struct GNUNET_PeerIdentity best_known_destination;
335 * In case best_known_destination is a finger, then trail id of trail to
336 * reach to this finger.
338 struct GNUNET_HashCode intermediate_trail_id;
341 * Trail id for trail which we are trying to setup.
343 struct GNUNET_HashCode trail_id;
345 /* List of peers which are part of trail setup so far.
346 * Trail does NOT include source_peer and peer which will be closest to
347 * ultimate_destination_finger_value.
348 * struct GNUNET_PeerIdentity trail[]
353 * P2P Trail Setup Result message
355 struct PeerTrailSetupResultMessage
359 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
361 struct GNUNET_MessageHeader header;
364 * Finger to which we have found the path.
366 struct GNUNET_PeerIdentity finger_identity;
369 * Peer which started trail_setup to find trail to finger_identity
371 struct GNUNET_PeerIdentity querying_peer;
374 * Is the trail setup to querying_peer's predecessor or finger?
376 uint32_t is_predecessor;
379 * Value to which finger_identity is the closest peer.
381 uint64_t ulitmate_destination_finger_value;
384 * Identifier of the trail from querying peer to finger_identity, NOT
385 * including both endpoints.
387 struct GNUNET_HashCode trail_id;
389 /* List of peers which are part of the trail from querying peer to
390 * finger_identity, NOT including both endpoints.
391 * struct GNUNET_PeerIdentity trail[]
396 * P2P Verify Successor Message.
398 struct PeerVerifySuccessorMessage
401 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
403 struct GNUNET_MessageHeader header;
406 * Peer which wants to verify its successor.
408 struct GNUNET_PeerIdentity source_peer;
411 * Source Peer's current successor.
413 struct GNUNET_PeerIdentity successor;
416 * Identifier of trail to reach from source_peer to successor.
418 struct GNUNET_HashCode trail_id;
420 /* List of the peers which are part of trail to reach from source_peer
421 * to successor, NOT including them
422 * struct GNUNET_PeerIdentity trail[]
427 * P2P Verify Successor Result Message
429 struct PeerVerifySuccessorResultMessage
432 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
434 struct GNUNET_MessageHeader header;
437 * Peer which sent the request to verify its successor.
439 struct GNUNET_PeerIdentity querying_peer;
442 * Successor to which PeerVerifySuccessorMessage was sent.
444 struct GNUNET_PeerIdentity current_successor;
447 * Current Predecessor of source_successor. It can be same as querying peer
448 * or different. In case it is different then it can be querying_peer's
449 * probable successor.
451 struct GNUNET_PeerIdentity probable_successor;
454 * Trail identifier of trail from querying_peer to current_successor.
456 struct GNUNET_HashCode trail_id;
459 * Direction in which we are looking at the trail.
461 uint32_t trail_direction;
463 /* In case probable_successor != querying_peer, then trail to reach from
464 * querying_peer to probable_successor, NOT including end points.
465 * struct GNUNET_PeerIdentity trail[]
470 * P2P Notify New Successor Message.
472 struct PeerNotifyNewSuccessorMessage
475 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
477 struct GNUNET_MessageHeader header;
480 * Peer which wants to notify its new successor.
482 struct GNUNET_PeerIdentity source_peer;
485 * New successor of source_peer.
487 struct GNUNET_PeerIdentity new_successor;
490 * Unique identifier of the trail from source_peer to new_successor,
491 * NOT including the endpoints.
493 struct GNUNET_HashCode trail_id;
495 /* List of peers in trail from source_peer to new_successor,
496 * NOT including the endpoints.
497 * struct GNUNET_PeerIdentity trail[]
503 * P2P Trail Tear Down message.
505 struct PeerTrailTearDownMessage
508 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
510 struct GNUNET_MessageHeader header;
513 * Unique identifier of the trail.
515 struct GNUNET_HashCode trail_id;
518 * Direction of trail.
520 uint32_t trail_direction;
525 * P2P Trail Rejection Message.
527 struct PeerTrailRejectionMessage
530 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
532 struct GNUNET_MessageHeader header;
535 * Peer which wants to set up the trail.
537 struct GNUNET_PeerIdentity source_peer;
540 * Peer which sent trail rejection message as it it congested.
542 struct GNUNET_PeerIdentity congested_peer;
545 * Peer identity closest to this value will be finger of
548 uint64_t ultimate_destination_finger_value;
551 * Is source_peer trying to setup the trail to its predecessor or finger.
553 uint32_t is_predecessor;
556 * Identifier for the trail that source peer is trying to setup.
558 struct GNUNET_HashCode trail_id;
561 * Relative time for which congested_peer will remain congested.
563 struct GNUNET_TIME_Relative congestion_time;
565 /* Trail_list from source_peer to peer which sent the message for trail setup
566 * to congested peer. This trail does NOT include source_peer.
567 struct GNUNET_PeerIdnetity trail[]*/
571 * P2P Add Trail Message.
573 struct PeerAddTrailMessage
576 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
578 struct GNUNET_MessageHeader header;
581 * Source of the routing trail.
583 struct GNUNET_PeerIdentity source_peer;
586 * Destination of the routing trail.
588 struct GNUNET_PeerIdentity destination_peer;
591 * Unique identifier of the trail from source_peer to destination_peer,
592 * NOT including the endpoints.
594 struct GNUNET_HashCode trail_id;
596 /* Trail from source peer to destination peer, NOT including them.
597 * struct GNUNET_PeerIdentity trail[]
601 GNUNET_NETWORK_STRUCT_END
604 * Linked list of messages to send to a particular other peer.
606 struct P2PPendingMessage
609 * Pointer to next item in the list
611 struct P2PPendingMessage *next;
614 * Pointer to previous item in the list
616 struct P2PPendingMessage *prev;
619 * Message importance level. FIXME: used? useful?
621 unsigned int importance;
624 * When does this message time out?
626 struct GNUNET_TIME_Absolute timeout;
629 * Actual message to be sent, allocated at the end of the struct:
630 * // msg = (cast) &pm[1];
631 * // memcpy (&pm[1], data, len);
633 const struct GNUNET_MessageHeader *msg;
638 * Entry in friend_peermap.
645 struct GNUNET_PeerIdentity id;
648 * Number of trails for which this friend is the first hop or if the friend
651 unsigned int trails_count;
654 * Count of outstanding messages for this friend.
656 unsigned int pending_count;
659 * In case not 0, then amount of time for which this friend is congested.
661 struct GNUNET_TIME_Absolute congestion_timestamp;
664 // TODO : Change name of head and tail to pending_messages_list_head and so.
666 * Head of pending messages to be sent to this friend.
668 struct P2PPendingMessage *head;
671 * Tail of pending messages to be sent to this friend.
673 struct P2PPendingMessage *tail;
676 * Core handle for sending messages to this friend.
678 struct GNUNET_CORE_TransmitHandle *th;
683 * An individual element of the trail to reach to a finger.
688 * Pointer to next item in the list
690 struct Trail_Element *next;
693 * Pointer to prev item in the list
695 struct Trail_Element *prev;
698 * An element in this trail.
700 struct GNUNET_PeerIdentity peer;
704 * Information about an individual trail.
711 struct Trail_Element *trail_head;
716 struct Trail_Element *trail_tail;
719 * Unique identifier of this trail.
721 struct GNUNET_HashCode trail_id;
724 * Length of trail pointed
726 unsigned int trail_length;
729 * Is there a valid trail entry.
731 unsigned int is_present;
735 * An entry in finger_table
742 struct GNUNET_PeerIdentity finger_identity;
745 * Is any finger stored at this finger index.
747 unsigned int is_present;
750 * Index in finger peer map
752 uint32_t finger_table_index;
755 * Number of trails setup so far for this finger.
756 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
758 uint32_t trails_count;
761 * Array of trails to reach to this finger.
763 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
768 * Stores information about the peer which is closest to destination_finger_value.
769 * 'closest' can be either successor or predecessor depending on is_predecessor
775 * Destination finger value.
777 uint64_t destination_finger_value;
780 * Is finger_value a predecessor or any other finger.
782 unsigned int is_predecessor;
785 * Trail id to reach to peer.
786 * In case peer is my identity or friend, it is set to 0.
788 struct GNUNET_HashCode trail_id;
791 * Next destination. In case of friend and my_identity , it is same as next_hop
792 * In case of finger it is finger identity.
794 struct GNUNET_PeerIdentity best_known_destination;
797 * In case best_known_destination is a finger, then first friend in the trail
798 * to reach to it. In other case, same as best_known_destination.
800 struct GNUNET_PeerIdentity next_hop;
803 * In case finger is the next hop, it contains a valid finger table index
804 * at which the finger is stored. Else, It contains 65, which is out of range
805 * of finger table index.
807 unsigned int finger_table_index;
812 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
813 * get our first friend.
815 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
818 * Task that sends verify successor message. This task is started when we get
819 * our successor for the first time.
821 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_task;
824 * Identity of this peer.
826 static struct GNUNET_PeerIdentity my_identity;
829 * Peer map of all the friends of a peer
831 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
834 * Array of all the fingers.
836 static struct FingerInfo finger_table [MAX_FINGERS];
841 static struct GNUNET_CORE_Handle *core_api;
844 * Handle for the statistics service.
846 //extern struct GNUNET_STATISTICS_Handle *GDS_stats;
849 * The current finger index that we have want to find trail to. We start the
850 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
851 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
852 * we reset this index to 0.
854 static unsigned int current_search_finger_index;
857 * Should we store our topology predecessor and successor IDs into statistics?
859 unsigned int track_topology;
862 * Should I be a malicious peer and drop the PUT/GET packets?
863 * if 0 then NOT malicious.
865 unsigned int act_malicious;
868 * Time duration to schedule find finger trail task.
870 static struct GNUNET_TIME_Relative find_finger_trail_task_next_send_time;
873 * Time duration to schedule verify successor task.
875 static struct GNUNET_TIME_Relative verify_successor_next_send_time;
878 * Called when core is ready to send a message we asked for
879 * out to the destination.
881 * @param cls the 'struct FriendInfo' of the target friend
882 * @param size number of bytes available in buf
883 * @param buf where the callee should write the message
884 * @return number of bytes written to buf
887 core_transmit_notify (void *cls, size_t size, void *buf)
889 struct FriendInfo *peer = cls;
891 struct P2PPendingMessage *pending;
896 while ((NULL != (pending = peer->head)) &&
897 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
899 peer->pending_count--;
900 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
901 GNUNET_free (pending);
905 /* no messages pending */
911 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
912 GNUNET_CORE_PRIO_BEST_EFFORT,
913 GNUNET_TIME_absolute_get_remaining
914 (pending->timeout), &peer->id,
915 ntohs (pending->msg->size),
916 &core_transmit_notify, peer);
917 GNUNET_break (NULL != peer->th);
921 while ((NULL != (pending = peer->head)) &&
922 (size - off >= (msize = ntohs (pending->msg->size))))
924 GNUNET_STATISTICS_update (GDS_stats,
926 ("# Bytes transmitted to other peers"), msize,
928 memcpy (&cbuf[off], pending->msg, msize);
930 peer->pending_count--;
931 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
932 GNUNET_free (pending);
934 if (peer->head != NULL)
937 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
938 GNUNET_CORE_PRIO_BEST_EFFORT,
939 GNUNET_TIME_absolute_get_remaining
940 (pending->timeout), &peer->id, msize,
941 &core_transmit_notify, peer);
942 GNUNET_break (NULL != peer->th);
949 * Transmit all messages in the friend's message queue.
951 * @param peer message queue to process
954 process_friend_queue (struct FriendInfo *peer)
956 struct P2PPendingMessage *pending;
958 if (NULL == (pending = peer->head))
962 if (NULL != peer->th)
968 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
970 GNUNET_TIME_absolute_get_remaining
971 (pending->timeout), &peer->id,
972 ntohs (pending->msg->size),
973 &core_transmit_notify, peer);
974 GNUNET_break (NULL != peer->th);
980 * Set the ENABLE_MALICIOUS value to malicious.
984 GDS_NEIGHBOURS_act_malicious (unsigned int malicious)
986 act_malicious = malicious;
991 * Construct a trail setup message and forward it to target_friend
992 * @param source_peer Peer which wants to setup the trail
993 * @param ultimate_destination_finger_value Peer identity closest to this value
994 * will be finger to @a source_peer
995 * @param best_known_destination Best known destination (could be finger or friend)
996 * which should get this message. In case it is
997 * friend, then it is same as target_friend
998 * @param target_friend Friend to which message is forwarded now.
999 * @param trail_length Total number of peers in trail setup so far.
1000 * @param trail_peer_list Trail setup so far
1001 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1002 * @param trail_id Unique identifier for the trail we are trying to setup.
1003 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1004 * best_known_destination when its a finger. If not
1005 * used then set to 0.
1008 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1009 uint64_t ultimate_destination_finger_value,
1010 struct GNUNET_PeerIdentity best_known_destination,
1011 struct FriendInfo *target_friend,
1012 unsigned int trail_length,
1013 const struct GNUNET_PeerIdentity *trail_peer_list,
1014 unsigned int is_predecessor,
1015 struct GNUNET_HashCode trail_id,
1016 struct GNUNET_HashCode intermediate_trail_id)
1018 struct P2PPendingMessage *pending;
1019 struct PeerTrailSetupMessage *tsm;
1020 struct GNUNET_PeerIdentity *peer_list;
1023 msize = sizeof (struct PeerTrailSetupMessage) +
1024 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1026 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1032 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1034 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1037 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1038 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1039 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1040 pending->msg = &(tsm->header);
1041 tsm->header.size = htons (msize);
1042 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1043 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1044 tsm->source_peer = source_peer;
1045 tsm->best_known_destination = best_known_destination;
1046 tsm->is_predecessor = htonl (is_predecessor);
1047 tsm->trail_id = trail_id;
1048 tsm->intermediate_trail_id = intermediate_trail_id;
1050 if (trail_length > 0)
1052 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1053 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1056 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1057 target_friend->pending_count++;
1058 process_friend_queue (target_friend);
1063 * Construct a trail setup result message and forward it to target friend.
1064 * @param querying_peer Peer which sent the trail setup request and should get
1066 * @param Finger Peer to which the trail has been setup to.
1067 * @param target_friend Friend to which this message should be forwarded.
1068 * @param trail_length Numbers of peers in the trail.
1069 * @param trail_peer_list Peers which are part of the trail from
1070 * querying_peer to Finger, NOT including them.
1071 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1072 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1074 * @param trail_id Unique identifier of the trail.
1077 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1078 struct GNUNET_PeerIdentity finger,
1079 struct FriendInfo *target_friend,
1080 unsigned int trail_length,
1081 const struct GNUNET_PeerIdentity *trail_peer_list,
1082 unsigned int is_predecessor,
1083 uint64_t ultimate_destination_finger_value,
1084 struct GNUNET_HashCode trail_id)
1086 struct P2PPendingMessage *pending;
1087 struct PeerTrailSetupResultMessage *tsrm;
1088 struct GNUNET_PeerIdentity *peer_list;
1091 msize = sizeof (struct PeerTrailSetupResultMessage) +
1092 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1094 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1100 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1102 GNUNET_STATISTICS_update (GDS_stats,
1103 gettext_noop ("# P2P messages dropped due to full queue"),
1107 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1108 pending->importance = 0;
1109 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1110 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1111 pending->msg = &tsrm->header;
1112 tsrm->header.size = htons (msize);
1113 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1114 tsrm->querying_peer = querying_peer;
1115 tsrm->finger_identity = finger;
1116 tsrm->is_predecessor = htonl (is_predecessor);
1117 tsrm->trail_id = trail_id;
1118 tsrm->ulitmate_destination_finger_value =
1119 GNUNET_htonll (ultimate_destination_finger_value);
1120 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1121 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1123 /* Send the message to chosen friend. */
1124 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1125 target_friend->pending_count++;
1126 process_friend_queue (target_friend);
1131 * Send trail rejection message to target friend
1132 * @param source_peer Peer which is trying to setup the trail.
1133 * @param ultimate_destination_finger_value Peer closest to this value will be
1134 * @a source_peer's finger
1135 * @param congested_peer Peer which sent this message as it is congested.
1136 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1137 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1138 * by congested_peer. This does NOT include @a source_peer
1139 * and congested_peer.
1140 * @param trail_length Total number of peers in trail_peer_list, NOT including
1141 * @a source_peer and @a congested_peer
1142 * @param trail_id Unique identifier of this trail.
1143 * @param congestion_timeout Duration given by congested peer as an estimate of
1144 * how long it may remain congested.
1147 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1148 uint64_t ultimate_destination_finger_value,
1149 struct GNUNET_PeerIdentity congested_peer,
1150 unsigned int is_predecessor,
1151 const struct GNUNET_PeerIdentity *trail_peer_list,
1152 unsigned int trail_length,
1153 struct GNUNET_HashCode trail_id,
1154 struct FriendInfo *target_friend,
1155 const struct GNUNET_TIME_Relative congestion_timeout)
1157 struct PeerTrailRejectionMessage *trm;
1158 struct P2PPendingMessage *pending;
1159 struct GNUNET_PeerIdentity *peer_list;
1162 msize = sizeof (struct PeerTrailRejectionMessage) +
1163 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1165 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1171 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1173 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1177 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1178 pending->importance = 0;
1179 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1180 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1181 pending->msg = &trm->header;
1182 trm->header.size = htons (msize);
1183 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1184 trm->source_peer = source_peer;
1185 trm->congested_peer = congested_peer;
1186 trm->congestion_time = congestion_timeout;
1187 trm->is_predecessor = htonl (is_predecessor);
1188 trm->trail_id = trail_id;
1189 trm->ultimate_destination_finger_value =
1190 GNUNET_htonll (ultimate_destination_finger_value);
1192 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1193 if (trail_length > 0)
1195 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1198 /* Send the message to chosen friend. */
1199 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1200 target_friend->pending_count++;
1201 process_friend_queue (target_friend);
1206 * Construct a verify successor message and forward it to target_friend.
1207 * @param source_peer Peer which wants to verify its successor.
1208 * @param successor Peer which is @a source_peer's current successor.
1209 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1210 * NOT including them.
1211 * @param trail List of peers which are part of trail to reach from @a source_peer
1212 * to @a successor, NOT including them.
1213 * @param trail_length Total number of peers in @a trail.
1214 * @param target_friend Next friend to get this message.
1217 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1218 struct GNUNET_PeerIdentity successor,
1219 struct GNUNET_HashCode trail_id,
1220 struct GNUNET_PeerIdentity *trail,
1221 unsigned int trail_length,
1222 struct FriendInfo *target_friend)
1224 struct PeerVerifySuccessorMessage *vsm;
1225 struct P2PPendingMessage *pending;
1226 struct GNUNET_PeerIdentity *peer_list;
1229 msize = sizeof (struct PeerVerifySuccessorMessage) +
1230 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1232 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1238 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1240 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1244 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1245 pending->importance = 0; /* FIXME */
1246 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1247 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1248 pending->msg = &vsm->header;
1249 vsm->header.size = htons (msize);
1250 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1251 vsm->source_peer = source_peer;
1252 vsm->successor = successor;
1253 vsm->trail_id = trail_id;
1254 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1255 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1257 /* Send the message to chosen friend. */
1258 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1259 target_friend->pending_count++;
1260 process_friend_queue (target_friend);
1265 * FIXME: In every function we pass target friend except for this one.
1266 * so, either change everything or this one. also, should se just store
1267 * the pointer to friend in routing table rather than gnunet_peeridentity.
1268 * if yes then we should keep friend info in.h andmake lot of changes.
1269 * Construct a trail teardown message and forward it to target friend.
1270 * @param trail_id Unique identifier of the trail.
1271 * @param trail_direction Direction of trail.
1272 * @param target_friend Friend to get this message.
1275 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1276 unsigned int trail_direction,
1277 struct GNUNET_PeerIdentity peer)
1279 struct PeerTrailTearDownMessage *ttdm;
1280 struct P2PPendingMessage *pending;
1281 struct FriendInfo *target_friend;
1284 msize = sizeof (struct PeerTrailTearDownMessage);
1286 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1292 /*FIXME:In what case friend can be null. ?*/
1293 if (NULL == (target_friend =
1294 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1297 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1299 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1303 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1304 pending->importance = 0; /* FIXME */
1305 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1306 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1307 pending->msg = &ttdm->header;
1308 ttdm->header.size = htons (msize);
1309 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1310 ttdm->trail_id = trail_id;
1311 ttdm->trail_direction = htonl (trail_direction);
1313 /* Send the message to chosen friend. */
1314 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1315 target_friend->pending_count++;
1316 process_friend_queue (target_friend);
1321 * Construct a verify successor result message and send it to target_friend
1322 * @param querying_peer Peer which sent the verify successor message.
1323 * @param source_successor Current_successor of @a querying_peer.
1324 * @param current_predecessor Current predecessor of @a successor. Could be same
1325 * or different from @a querying_peer.
1326 * @param trail_id Unique identifier of the trail from @a querying_peer to
1327 * @a successor, NOT including them.
1328 * @param trail List of peers which are part of trail from @a querying_peer to
1329 * @a successor, NOT including them.
1330 * @param trail_length Total number of peers in @a trail
1331 * @param trail_direction Direction in which we are sending the message. In this
1332 * case we are sending result from @a successor to @a querying_peer.
1333 * @param target_friend Next friend to get this message.
1336 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1337 struct GNUNET_PeerIdentity current_successor,
1338 struct GNUNET_PeerIdentity probable_successor,
1339 struct GNUNET_HashCode trail_id,
1340 const struct GNUNET_PeerIdentity *trail,
1341 unsigned int trail_length,
1342 enum GDS_ROUTING_trail_direction trail_direction,
1343 struct FriendInfo *target_friend)
1345 struct PeerVerifySuccessorResultMessage *vsmr;
1346 struct P2PPendingMessage *pending;
1347 struct GNUNET_PeerIdentity *peer_list;
1350 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1351 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1353 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1359 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1361 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1365 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1366 pending->importance = 0; /* FIXME */
1367 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1368 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1369 pending->msg = &vsmr->header;
1370 vsmr->header.size = htons (msize);
1371 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1372 vsmr->querying_peer = querying_peer;
1373 vsmr->current_successor = current_successor;
1374 vsmr->probable_successor = probable_successor;
1375 vsmr->trail_direction = htonl (trail_direction);
1376 vsmr->trail_id = trail_id;
1377 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1378 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1380 /* Send the message to chosen friend. */
1381 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1382 target_friend->pending_count++;
1383 process_friend_queue (target_friend);
1388 * Construct a notify new successor message and send it to target_friend
1389 * @param source_peer Peer which wants to notify to its new successor that it
1390 * could be its predecessor.
1391 * @param successor New successor of @a source_peer
1392 * @param successor_trail List of peers in Trail to reach from
1393 * @a source_peer to @a new_successor, NOT including
1395 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1396 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1397 * @param target_friend Next friend to get this message.
1400 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1401 struct GNUNET_PeerIdentity successor,
1402 const struct GNUNET_PeerIdentity *successor_trail,
1403 unsigned int successor_trail_length,
1404 struct GNUNET_HashCode succesor_trail_id,
1405 struct FriendInfo *target_friend)
1407 struct PeerNotifyNewSuccessorMessage *nsm;
1408 struct P2PPendingMessage *pending;
1409 struct GNUNET_PeerIdentity *peer_list;
1412 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1413 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1415 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1421 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1423 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1427 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1428 pending->importance = 0; /* FIXME */
1429 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1430 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1431 pending->msg = &nsm->header;
1432 nsm->header.size = htons (msize);
1433 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1434 nsm->new_successor = successor;
1435 nsm->source_peer = source_peer;
1436 nsm->trail_id = succesor_trail_id;
1437 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1438 memcpy (peer_list, successor_trail,
1439 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1441 /* Send the message to chosen friend. */
1442 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1443 target_friend->pending_count++;
1444 process_friend_queue (target_friend);
1449 * Construct an add_trail message and send it to target_friend
1450 * @param source_peer Source of the trail.
1451 * @param destination_peer Destination of the trail.
1452 * @param trail_id Unique identifier of the trail from
1453 * @a source_peer to @a destination_peer, NOT including the endpoints.
1454 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1455 * NOT including the endpoints.
1456 * @param trail_length Total number of peers in @a trail.
1457 * @param target_friend Next friend to get this message.
1460 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1461 struct GNUNET_PeerIdentity destination_peer,
1462 struct GNUNET_HashCode trail_id,
1463 const struct GNUNET_PeerIdentity *trail,
1464 unsigned int trail_length,
1465 struct FriendInfo *target_friend)
1467 struct PeerAddTrailMessage *adm;
1468 struct GNUNET_PeerIdentity *peer_list;
1469 struct P2PPendingMessage *pending;
1472 msize = sizeof (struct PeerAddTrailMessage) +
1473 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1475 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1481 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1483 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1487 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1488 pending->importance = 0; /* FIXME */
1489 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1490 adm = (struct PeerAddTrailMessage *) &pending[1];
1491 pending->msg = &adm->header;
1492 adm->header.size = htons (msize);
1493 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1494 adm->source_peer = source_peer;
1495 adm->destination_peer = destination_peer;
1496 adm->trail_id = trail_id;
1497 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1498 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1500 /* Send the message to chosen friend. */
1501 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1502 target_friend->pending_count++;
1503 process_friend_queue (target_friend);
1509 * Search my location in trail. In case I am present more than once in the
1510 * trail (can happen during trail setup), then return my lowest index.
1511 * @param trail List of peers
1512 * @return my_index if found
1513 * trail_length + 1 if an entry is present twice, It is an error.
1514 * -1 if no entry found.
1517 search_my_index (const struct GNUNET_PeerIdentity *trail,
1521 int index_seen = trail_length + 1;
1524 for (i = 0; i < trail_length; i++)
1526 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1529 if(index_seen == (trail_length + 1))
1533 DEBUG("Entry is present twice in trail. Its not allowed\n");
1547 * Check if the friend is congested or have reached maximum number of trails
1548 * it can be part of of.
1549 * @param friend Friend to be checked.
1550 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1551 * #GNUNET_YES if friend is either congested or have crossed threshold
1554 is_friend_congested (struct FriendInfo *friend)
1556 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1557 ((0 == GNUNET_TIME_absolute_get_remaining
1558 (friend->congestion_timestamp).rel_value_us)))
1566 * Select closest finger to value.
1567 * @param peer1 First peer
1568 * @param peer2 Second peer
1569 * @param value Value to be compare
1570 * @return Closest peer
1572 static struct GNUNET_PeerIdentity
1573 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1574 const struct GNUNET_PeerIdentity *peer2,
1577 uint64_t peer1_value;
1578 uint64_t peer2_value;
1580 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1581 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1582 peer1_value = GNUNET_ntohll (peer1_value);
1583 peer2_value = GNUNET_ntohll (peer2_value);
1585 // TODO: Can use a simpler (to understand) idea here!
1586 if (peer1_value == value)
1591 if (peer2_value == value)
1596 if (peer2_value < peer1_value)
1598 if ((peer2_value < value) && (value < peer1_value))
1602 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1603 ((0 < value) && (value < peer2_value)))
1609 //if (peer1_value < peer2_value)
1611 if ((peer1_value < value) && (value < peer2_value))
1615 //else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1616 // ((0 < value) && (value < peer1_value)))
1625 * Select closest predecessor to value.
1626 * @param peer1 First peer
1627 * @param peer2 Second peer
1628 * @param value Value to be compare
1629 * @return Peer which precedes value in the network.
1631 static struct GNUNET_PeerIdentity
1632 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1633 const struct GNUNET_PeerIdentity *peer2,
1636 uint64_t peer1_value;
1637 uint64_t peer2_value;
1639 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1640 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1641 peer1_value = GNUNET_ntohll (peer1_value);
1642 peer2_value = GNUNET_ntohll (peer2_value);
1644 if (peer1_value == value)
1647 if (peer2_value == value)
1650 if (peer1_value < peer2_value)
1652 if ((peer1_value < value) && (value < peer2_value))
1656 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1657 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1663 // if (peer2_value < peer1_value)
1665 if ((peer2_value < value) && (value < peer1_value))
1669 //else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1670 // ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1683 test_print_trail (struct GNUNET_PeerIdentity *trail,
1684 unsigned int trail_length)
1686 struct GNUNET_PeerIdentity print_peer;
1689 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1690 __FILE__, __func__,__LINE__,trail_length);
1691 for (i =0 ; i< trail_length; i++)
1693 print_peer = trail[i];
1694 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1695 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1702 * This is a test function to print all the entries of friend table.
1705 test_friend_peermap_print ()
1707 struct FriendInfo *friend;
1708 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1709 struct GNUNET_PeerIdentity print_peer;
1710 struct GNUNET_PeerIdentity key_ret;
1713 print_peer = my_identity;
1714 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1715 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1717 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1719 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1721 (const void **)&friend))
1723 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1724 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1725 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1733 * This is a test function, to print all the entries of finger table.
1736 test_finger_table_print()
1738 struct FingerInfo *finger;
1739 struct GNUNET_PeerIdentity print_peer;
1740 //struct Trail *trail;
1744 print_peer = my_identity;
1745 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1746 for (i = 0; i < MAX_FINGERS; i++)
1748 finger = &finger_table[i];
1750 if (GNUNET_NO == finger->is_present)
1753 print_peer = finger->finger_identity;
1754 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1755 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1758 for (j = 0; j < finger->trails_count; j++)
1760 trail = &finger->trail_list[j];
1761 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1762 struct Trail_Element *element;
1763 element = trail->trail_head;
1764 for (k = 0; k < trail->trail_length; k++)
1766 print_peer = element->peer;
1767 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1768 element = element->next;
1777 * Select the closest peer among two peers (which should not be same)
1778 * with respect to value and finger_table_index
1779 * NOTE: peer1 != peer2
1780 * @param peer1 First peer
1781 * @param peer2 Second peer
1782 * @param value Value relative to which we find the closest
1783 * @param is_predecessor Is value a predecessor or any other finger.
1784 * @return Closest peer among two peers.
1786 static struct GNUNET_PeerIdentity
1787 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1788 const struct GNUNET_PeerIdentity *peer2,
1790 unsigned int is_predecessor)
1792 /* This check is here to ensure that calling function never sends
1793 same peer value in peer1 and peer2. Remove it later. */
1794 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1795 if (1 == is_predecessor)
1796 return select_closest_predecessor (peer1, peer2, value);
1798 // TODO: Change name to something like select_closest_successor!!
1799 return select_closest_finger (peer1, peer2, value);
1804 * Iterate over the list of all the trails of a finger. In case the first
1805 * friend to reach the finger has reached trail threshold or is congested,
1806 * then don't select it. In case there multiple available good trails to reach
1807 * to Finger, choose the one with shortest trail length.
1808 * Note: We use length as parameter. But we can use any other suitable parameter
1810 * @param finger Finger
1813 static struct Trail *
1814 select_finger_trail (struct FingerInfo *finger)
1816 struct FriendInfo *friend;
1817 struct Trail *current_finger_trail;
1818 struct Trail *best_trail = NULL;
1821 GNUNET_assert (finger->trails_count > 0);
1823 for (i = 0; i < finger->trails_count; i++)
1825 current_finger_trail = &finger->trail_list[i];
1827 /* No trail stored at this index. */
1828 if (GNUNET_NO == current_finger_trail->is_present)
1831 /* SUPUS: I am not changing anything here. as i assume that in case we have
1832 a finger which is friend and we have trail length = 0, then it will
1833 be the first friend to which we send the request. As I have removed
1834 the condition in trail setup where we check for source is a friend. */
1835 GNUNET_assert (NULL !=
1837 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1838 ¤t_finger_trail->trail_head->peer)));
1840 /* First friend to reach trail is not free. */
1841 if (GNUNET_YES == is_friend_congested (friend))
1844 if (NULL == best_trail ||
1845 best_trail->trail_length > current_finger_trail->trail_length)
1847 best_trail = current_finger_trail;
1856 * Compare FINGER entry with current successor. If finger's first friend of all
1857 * its trail is not congested and has not crossed trail threshold, then check
1858 * if finger peer identity is closer to final_destination_finger_value than
1859 * current_successor. If yes then update current_successor.
1860 * @param current_successor[in/out]
1864 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
1866 struct FingerInfo *finger;
1867 struct GNUNET_PeerIdentity closest_peer;
1868 struct Trail *finger_trail;
1871 /* Iterate over finger table. */
1872 for (i = 0; i < MAX_FINGERS; i++)
1874 finger = &finger_table[i];
1876 if (GNUNET_NO == finger->is_present)
1879 /* SUPUS: As we have friend stored as finger also, it may happen that
1880 * friend corresponding to this finger has been chosen as the best
1881 * known destination, then just move to next element. */
1882 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1883 ¤t_closest_peer->best_known_destination))
1886 /* If I am my own finger, then ignore this finger. */
1887 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1891 /* If finger is a friend, then do nothing. As we have already checked
1892 * for each friend in compare_friend_and_current_successor().
1893 * SUPUS: Here we have all the friends in the friend table. So even if
1894 * that friend is a finger, we have checked it with trail length = 0.
1895 * So its okay. No need to change anything here. Note: finger may have
1896 * trail length > 0 but its okay. */
1897 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1898 &finger->finger_identity)))
1903 closest_peer = select_closest_peer (&finger->finger_identity,
1904 ¤t_closest_peer->best_known_destination,
1905 current_closest_peer->destination_finger_value,
1906 current_closest_peer->is_predecessor);
1908 /* SUPUS: Ideally if finger is a friend, but with trail length > 0, then
1909 also we have already handled the case in above condition. */
1910 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer))
1912 /* Choose one of the trail to reach to finger. */
1913 finger_trail = select_finger_trail (finger);
1915 /* In case no trail found, ignore this finger. */
1916 if (NULL == finger_trail)
1919 current_closest_peer->best_known_destination = closest_peer;
1920 current_closest_peer->next_hop = finger_trail->trail_head->peer;
1921 current_closest_peer->trail_id = finger_trail->trail_id;
1922 current_closest_peer->finger_table_index = i;
1930 * Compare friend entry with current successor.
1931 * If friend identity and current_successor is same, then do nothing.
1932 * If friend is not congested and has not crossed trail threshold, then check
1933 * if friend peer identity is closer to final_destination_finger_value than
1934 * current_successor. If yes then update current_successor.
1935 * @param cls closure
1936 * @param key current public key
1937 * @param value struct Closest_Peer
1938 * @return #GNUNET_YES if we should continue to iterate,
1939 * #GNUNET_NO if not.
1942 compare_friend_and_current_closest_peer (void *cls,
1943 const struct GNUNET_PeerIdentity *key,
1946 struct FriendInfo *friend = value;
1947 struct Closest_Peer *current_closest_peer = cls;
1948 struct GNUNET_PeerIdentity closest_peer;
1950 /* Friend is either congested or has crossed threshold. */
1951 if (GNUNET_YES == is_friend_congested (friend))
1954 /* If current_closest_peer and friend identity are same, then do nothing.*/
1955 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
1956 ¤t_closest_peer->best_known_destination))
1962 closest_peer = select_closest_peer (&friend->id,
1963 ¤t_closest_peer->best_known_destination,
1964 current_closest_peer->destination_finger_value,
1965 current_closest_peer->is_predecessor);
1967 /* Is friend the closest successor? */
1968 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer))
1970 current_closest_peer->best_known_destination = friend->id;
1971 current_closest_peer->next_hop = friend->id;
1979 * Initialize current_successor to my_identity.
1980 * @param my_identity My peer identity
1981 * @return Updated closest_peer
1983 static struct Closest_Peer
1984 init_current_successor (struct GNUNET_PeerIdentity my_identity,
1985 uint64_t destination_finger_value,
1986 unsigned int is_predecessor)
1988 struct Closest_Peer current_closest_peer;
1990 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
1991 current_closest_peer.destination_finger_value = destination_finger_value;
1992 current_closest_peer.is_predecessor = is_predecessor;
1993 current_closest_peer.next_hop = my_identity;
1994 current_closest_peer.best_known_destination = my_identity;
1995 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
1996 return current_closest_peer;
2001 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2002 * peer. It could be because of the logic we wrote here. Verify if its correct.
2003 * If not then return immediate_successor.
2005 * Find the successor for destination_finger_value among my_identity, my
2006 * friends and my fingers. Don't consider friends or fingers which are either
2007 * congested or have crossed the threshold.
2008 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2010 * @param destination_finger_value Peer closest to this value will be the next successor.
2011 * @param is_predecessor Are we looking for predecessor or finger?
2012 * @return Successor It is never NULL, in case none of friend or finger is closest,
2013 * then we return my_identity.
2015 static struct Closest_Peer
2016 find_successor (uint64_t destination_finger_value,
2017 unsigned int is_predecessor)
2019 struct Closest_Peer current_closest_peer;
2021 /* Initialize current_successor to my_identity. */
2022 current_closest_peer = init_current_successor (my_identity,
2023 destination_finger_value,
2026 /* Compare each friend entry with current_successor and update current_successor
2027 * with friend if its closest. */
2030 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2031 &compare_friend_and_current_closest_peer,
2032 ¤t_closest_peer));
2034 /* Compare each finger entry with current_successor and update current_successor
2035 * with finger if its closest. */
2036 compare_finger_and_current_closest_peer (¤t_closest_peer);
2037 return current_closest_peer;
2041 * FIXME; Send put message across all the trail to reach to next hop to handle
2043 * Construct a Put message and send it to target_peer.
2044 * @param key Key for the content
2045 * @param block_type Type of the block
2046 * @param options Routing options
2047 * @param desired_replication_level Desired replication count
2048 * @param best_known_dest Peer to which this message should reach eventually,
2049 * as it is best known destination to me.
2050 * @param intermediate_trail_id Trail id in case
2051 * @param target_peer Peer to which this message will be forwarded.
2052 * @param hop_count Number of hops traversed so far.
2053 * @param put_path_length Total number of peers in @a put_path
2054 * @param put_path Number of peers traversed so far
2055 * @param expiration_time When does the content expire
2056 * @param data Content to store
2057 * @param data_size Size of content @a data in bytes
2060 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2061 enum GNUNET_BLOCK_Type block_type,
2062 enum GNUNET_DHT_RouteOption options,
2063 uint32_t desired_replication_level,
2064 struct GNUNET_PeerIdentity best_known_dest,
2065 struct GNUNET_HashCode intermediate_trail_id,
2066 struct GNUNET_PeerIdentity *target_peer,
2068 uint32_t put_path_length,
2069 struct GNUNET_PeerIdentity *put_path,
2070 struct GNUNET_TIME_Absolute expiration_time,
2071 const void *data, size_t data_size)
2073 struct PeerPutMessage *ppm;
2074 struct P2PPendingMessage *pending;
2075 struct FriendInfo *target_friend;
2076 struct GNUNET_PeerIdentity *pp;
2079 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2080 sizeof (struct PeerPutMessage);
2081 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2083 put_path_length = 0;
2084 msize = data_size + sizeof (struct PeerPutMessage);
2087 /* Should it be GNUNET_SERVER_MAX_MESSAGE_SIZE? */
2088 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2090 DEBUG("msize = %lu\n",msize);
2095 GNUNET_assert (NULL !=
2097 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2098 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2099 pending->timeout = expiration_time;
2100 ppm = (struct PeerPutMessage *) &pending[1];
2101 pending->msg = &ppm->header;
2102 ppm->header.size = htons (msize);
2103 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2104 ppm->options = htonl (options);
2105 ppm->block_type = htonl (block_type);
2106 ppm->hop_count = htonl (hop_count + 1);
2107 ppm->desired_replication_level = htonl (desired_replication_level);
2108 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2109 ppm->best_known_destination = best_known_dest;
2110 ppm->intermediate_trail_id = intermediate_trail_id;
2112 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2113 ppm->put_path_length = htonl (put_path_length);
2114 if(put_path_length > 0)
2116 memcpy (pp, put_path,
2117 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2119 memcpy (&pp[put_path_length], data, data_size);
2120 GNUNET_assert (NULL != target_friend);
2121 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2122 target_friend->pending_count++;
2123 process_friend_queue (target_friend);
2128 * Handle the put request from the client.
2129 * @param key Key for the content
2130 * @param block_type Type of the block
2131 * @param options Routing options
2132 * @param desired_replication_level Desired replication count
2133 * @param expiration_time When does the content expire
2134 * @param data Content to store
2135 * @param data_size Size of content @a data in bytes
2138 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
2139 enum GNUNET_BLOCK_Type block_type,
2140 enum GNUNET_DHT_RouteOption options,
2141 uint32_t desired_replication_level,
2142 struct GNUNET_TIME_Absolute expiration_time,
2143 const void *data, size_t data_size)
2145 struct GNUNET_PeerIdentity best_known_dest;
2146 struct GNUNET_HashCode intermediate_trail_id;
2147 struct GNUNET_PeerIdentity next_hop;
2149 struct Closest_Peer successor;
2151 memcpy (&key_value, key, sizeof (uint64_t));
2152 key_value = GNUNET_ntohll (key_value);
2153 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2154 best_known_dest = successor.best_known_destination;
2155 next_hop = successor.next_hop;
2156 intermediate_trail_id = successor.trail_id;
2158 DEBUG("PUT_REQUEST_RECEVIED KEY = %s \n",GNUNET_h2s(key));
2159 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2161 /* I am the destination. */
2162 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2163 block_type,data_size,data);
2164 GDS_CLIENTS_process_put (options, block_type, 0,
2165 ntohl (desired_replication_level),
2166 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time.
2167 key, data, data_size);
2171 /* In case we are sending the request to a finger, then send across all of its
2174 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2175 &successor.next_hop))
2177 struct FingerInfo *next_hop_finger;
2180 next_hop_finger = &finger_table[successor.finger_table_index];
2181 for (i = 0; i < next_hop_finger->trails_count; i++)
2183 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2185 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2187 next_hop_finger->trail_list[i].trail_id,
2188 &next_hop, hop_count, put_path_length, put_path,
2196 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2197 best_known_dest, intermediate_trail_id, &next_hop,
2198 0, 1, &my_identity, expiration_time,
2203 * FIXME; Send get message across all the trail to reach to next hop to handle
2205 * Construct a Get message and send it to target_peer.
2206 * @param key Key for the content
2207 * @param block_type Type of the block
2208 * @param options Routing options
2209 * @param desired_replication_level Desired replication count
2210 * @param best_known_dest Peer which should get this message. Same as target peer
2211 * if best_known_dest is a friend else its a finger.
2212 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2213 * in case it is a finger else set to 0.
2214 * @param target_peer Peer to which this message will be forwarded.
2215 * @param hop_count Number of hops traversed so far.
2216 * @param data Content to store
2217 * @param data_size Size of content @a data in bytes
2218 * @param get_path_length Total number of peers in @a get_path
2219 * @param get_path Number of peers traversed so far
2222 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2223 enum GNUNET_BLOCK_Type block_type,
2224 enum GNUNET_DHT_RouteOption options,
2225 uint32_t desired_replication_level,
2226 struct GNUNET_PeerIdentity best_known_dest,
2227 struct GNUNET_HashCode intermediate_trail_id,
2228 struct GNUNET_PeerIdentity *target_peer,
2230 uint32_t get_path_length,
2231 struct GNUNET_PeerIdentity *get_path)
2233 struct PeerGetMessage *pgm;
2234 struct P2PPendingMessage *pending;
2235 struct FriendInfo *target_friend;
2236 struct GNUNET_PeerIdentity *gp;
2239 msize = sizeof (struct PeerGetMessage) +
2240 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2242 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2247 GNUNET_assert (NULL !=
2249 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2251 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2252 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2253 pending->importance = 0; /* FIXME */
2254 pgm = (struct PeerGetMessage *) &pending[1];
2255 pending->msg = &pgm->header;
2256 pgm->header.size = htons (msize);
2257 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2258 pgm->get_path_length = htonl (get_path_length);
2259 pgm->best_known_destination = best_known_dest;
2261 pgm->intermediate_trail_id = intermediate_trail_id;
2262 pgm->hop_count = htonl (hop_count + 1);
2263 pgm->get_path_length = htonl (get_path_length);
2264 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2265 memcpy (gp, get_path,
2266 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2267 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2268 target_friend->pending_count++;
2269 process_friend_queue (target_friend);
2274 * Handle the get request from the client file. If I am destination do
2275 * datacache put and return. Else find the target friend and forward message
2277 * @param key Key for the content
2278 * @param block_type Type of the block
2279 * @param options Routing options
2280 * @param desired_replication_level Desired replication count
2283 GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key,
2284 enum GNUNET_BLOCK_Type block_type,
2285 enum GNUNET_DHT_RouteOption options,
2286 uint32_t desired_replication_level)
2288 struct Closest_Peer successor;
2289 struct GNUNET_PeerIdentity best_known_dest;
2290 struct GNUNET_HashCode intermediate_trail_id;
2293 memcpy (&key_value, key, sizeof (uint64_t));
2294 key_value = GNUNET_ntohll (key_value);
2296 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2298 best_known_dest = successor.best_known_destination;
2299 intermediate_trail_id = successor.trail_id;
2301 DEBUG("GET_REQUEST_RECEVIED KEY = %s \n",GNUNET_h2s(key));
2302 /* I am the destination. I have the data. */
2303 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2306 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2307 NULL, 0, 1, &my_identity, NULL,&my_identity);
2311 /* fixme; for multiple trails, we need to send back finger index and send trail
2312 across all the fingers. but in current implementation we don't have this case.
2313 compare finger and current_successor returns, */
2314 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2315 best_known_dest,intermediate_trail_id, &successor.next_hop,
2316 0, 1, &my_identity);
2321 * Send the get result to requesting client.
2322 * @param key Key of the requested data.
2323 * @param type Block type
2324 * @param target_peer Next peer to forward the message to.
2325 * @param source_peer Peer which has the data for the key.
2326 * @param put_path_length Number of peers in @a put_path
2327 * @param put_path Path taken to put the data at its stored location.
2328 * @param get_path_length Number of peers in @a get_path
2329 * @param get_path Path taken to reach to the location of the key.
2330 * @param expiration When will this result expire?
2331 * @param data Payload to store
2332 * @param data_size Size of the @a data
2335 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2336 enum GNUNET_BLOCK_Type type,
2337 const struct GNUNET_PeerIdentity *target_peer,
2338 const struct GNUNET_PeerIdentity *source_peer,
2339 unsigned int put_path_length,
2340 const struct GNUNET_PeerIdentity *put_path,
2341 unsigned int get_path_length,
2342 const struct GNUNET_PeerIdentity *get_path,
2343 struct GNUNET_TIME_Absolute expiration,
2344 const void *data, size_t data_size)
2346 struct PeerGetResultMessage *get_result;
2347 struct GNUNET_PeerIdentity *paths;
2348 struct P2PPendingMessage *pending;
2349 struct FriendInfo *target_friend;
2350 int current_path_index;
2353 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2355 sizeof (struct PeerGetResultMessage);
2357 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2359 put_path_length = 0;
2360 msize = msize - put_path_length;
2364 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2369 current_path_index = 0;
2370 if(get_path_length > 0)
2372 current_path_index = search_my_index(get_path, get_path_length);
2373 if (-1 == current_path_index)
2378 if ((get_path_length + 1) == current_path_index)
2380 DEBUG ("Peer found twice in get path. Not allowed \n");
2385 if (0 == current_path_index)
2387 DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",GNUNET_h2s(key),GNUNET_i2s(&my_identity));
2388 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2389 get_path, put_path_length,
2390 put_path, type, data_size, data);
2394 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2395 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2396 pending->importance = 0;
2397 get_result = (struct PeerGetResultMessage *)&pending[1];
2398 pending->msg = &get_result->header;
2399 get_result->header.size = htons (msize);
2400 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2401 get_result->key = *key;
2402 get_result->querying_peer = *source_peer;
2403 get_result->expiration_time = expiration;
2404 get_result->get_path_length = htonl (get_path_length);
2405 get_result->put_path_length = htonl (put_path_length);
2406 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2407 memcpy (paths, put_path,
2408 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2409 memcpy (&paths[put_path_length], get_path,
2410 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2411 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2413 GNUNET_assert (NULL !=
2415 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2416 &get_path[current_path_index - 1])));
2417 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2418 target_friend->pending_count++;
2419 process_friend_queue (target_friend);
2424 * Randomly choose one of your friends (which is not congested and have not crossed
2425 * trail threshold) from the friend_peermap
2426 * @return Friend Randomly chosen friend.
2427 * NULL in case friend peermap is empty, or all the friends are either
2428 * congested or have crossed trail threshold.
2430 static struct FriendInfo *
2431 select_random_friend ()
2433 unsigned int current_size;
2436 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2437 struct GNUNET_PeerIdentity key_ret;
2438 struct FriendInfo *friend;
2440 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2443 if (0 == current_size)
2446 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2447 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2449 /* Iterate till you don't reach to index. */
2450 for (j = 0; j < index ; j++)
2451 GNUNET_assert (GNUNET_YES ==
2452 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2456 /* Reset the index in friend peermap to 0 as we reached to the end. */
2457 if (j == current_size)
2460 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2461 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2465 /* Get the friend stored at the index, j*/
2466 GNUNET_assert (GNUNET_YES ==
2467 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2469 (const void **)&friend));
2471 /* This friend is not congested and has not crossed trail threshold. */
2472 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2473 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2479 } while (j != index);
2481 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2487 * Compute 64 bit value of finger_identity corresponding to a finger index using
2489 * For all fingers, n.finger[i] = n + pow (2,i),
2490 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2491 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2492 * @param finger_index Index corresponding to which we calculate 64 bit value.
2493 * @return 64 bit value.
2496 compute_finger_identity_value (unsigned int finger_index)
2500 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2501 my_id64 = GNUNET_ntohll (my_id64);
2503 /* Are we looking for immediate predecessor? */
2504 if (PREDECESSOR_FINGER_ID == finger_index)
2505 return (my_id64 - 1);
2508 uint64_t add = (uint64_t)1 << finger_index;
2509 return (my_id64 + add);
2515 * Choose a random friend. Calculate the next finger identity to search,from
2516 * current_search_finger_index. Start looking for the trail to reach to
2517 * finger identity through this random friend.
2519 * @param cls closure for this task
2520 * @param tc the context under which the task is running
2523 send_find_finger_trail_message (void *cls,
2524 const struct GNUNET_SCHEDULER_TaskContext *tc)
2526 struct FriendInfo *target_friend;
2527 struct GNUNET_HashCode trail_id;
2528 struct GNUNET_HashCode intermediate_trail_id;
2529 unsigned int is_predecessor = 0;
2530 uint64_t finger_id_value;
2532 /* Schedule another send_find_finger_trail_message task. When we have seen
2533 * one round of fingers, then this time is exponentially backoff to reduce
2534 * traffic caused by this task. */
2535 find_finger_trail_task_next_send_time.rel_value_us =
2536 find_finger_trail_task_next_send_time.rel_value_us +
2537 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2538 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2539 find_finger_trail_task =
2540 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2541 &send_find_finger_trail_message,
2544 /* No space in my routing table. (Source and destination peers also store entries
2545 * in their routing table). */
2546 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2549 target_friend = select_random_friend ();
2550 if (NULL == target_friend)
2555 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2556 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2559 /* Generate a unique trail id for trail we are trying to setup. */
2560 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2561 &trail_id, sizeof (trail_id));
2562 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2563 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2564 target_friend->id, target_friend, 0, NULL,
2565 is_predecessor, trail_id,
2566 intermediate_trail_id);
2571 * In case there are already maximum number of possible trails to reach to a
2572 * finger, then check if the new trail's length is lesser than any of the
2574 * If yes then replace that old trail by new trail.
2576 * Note: Here we are taking length as a parameter to choose the best possible
2577 * trail, but there could be other parameters also like:
2578 * 1. duration of existence of a trail - older the better.
2579 * 2. if the new trail is completely disjoint than the
2580 * other trails, then may be choosing it is better.
2582 * @param finger Finger
2583 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2584 * including the endpoints.
2585 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2586 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2589 select_and_replace_trail (struct FingerInfo *finger,
2590 const struct GNUNET_PeerIdentity *new_trail,
2591 unsigned int new_trail_length,
2592 struct GNUNET_HashCode new_trail_id)
2594 struct Trail *trail;
2595 unsigned int largest_trail_length;
2596 unsigned int largest_trail_index;
2597 struct Trail_Element *trail_element;
2600 largest_trail_length = new_trail_length;
2601 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2603 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2605 for (i = 0; i < finger->trails_count; i++)
2607 trail = &finger->trail_list[i];
2608 if (trail->trail_length > largest_trail_length)
2610 largest_trail_length = trail->trail_length;
2611 largest_trail_index = i;
2615 /* New trail is not better than existing ones. Send trail teardown. */
2616 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2618 struct GNUNET_PeerIdentity next_hop;
2620 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2621 GDS_ROUTING_remove_trail (new_trail_id);
2622 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2623 GDS_ROUTING_SRC_TO_DEST,
2628 /* Send trail teardown message across the replaced trail. */
2629 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2631 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2632 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2633 GDS_ROUTING_SRC_TO_DEST,
2634 replace_trail->trail_head->peer);
2635 /* Free the trail. */
2636 while (NULL != (trail_element = replace_trail->trail_head))
2638 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2639 replace_trail->trail_tail, trail_element);
2640 GNUNET_free_non_null (trail_element);
2643 /* Add new trial at that location. */
2644 replace_trail->is_present = GNUNET_YES;
2645 replace_trail->trail_length = new_trail_length;
2646 replace_trail->trail_id = new_trail_id;
2648 for (i = 0; i < new_trail_length; i++)
2650 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2651 element->peer = new_trail[i];
2653 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2654 replace_trail->trail_tail,
2657 /* FIXME: URGENT Are we adding the trail back to the list. */
2662 * Check if the new trail to reach to finger is unique or do we already have
2663 * such a trail present for finger.
2664 * @param existing_finger Finger identity
2665 * @param new_trail New trail to reach @a existing_finger
2666 * @param trail_length Total number of peers in new_trail.
2667 * @return #GNUNET_YES if the new trail is unique
2668 * #GNUNET_NO if same trail is already present.
2671 is_new_trail_unique (struct FingerInfo *existing_finger,
2672 const struct GNUNET_PeerIdentity *new_trail,
2673 unsigned int trail_length)
2675 struct Trail *trail;
2676 struct Trail_Element *trail_element;
2680 GNUNET_assert (existing_finger->trails_count > 0);
2682 /* Iterate over list of trails. */
2683 for (i = 0; i < existing_finger->trails_count; i++)
2685 trail = &(existing_finger->trail_list[i]);
2686 GNUNET_assert (GNUNET_YES == trail->is_present);
2688 /* New trail and existing trail length are not same. */
2689 if (trail->trail_length != trail_length)
2694 trail_element = trail->trail_head;
2695 GNUNET_assert (trail_element != NULL);
2696 for (j = 0; j < trail->trail_length; j++)
2698 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2699 &trail_element->peer))
2703 trail_element = trail_element->next;
2711 * FIXME; In case of multiple trails, we may have a case where a trail from in
2712 * between has been removed, then we should try to find a free slot , not simply
2713 * add a trail at then end of the list.
2714 * Add a new trail to existing finger. This function is called only when finger
2715 * is not my own identity or a friend.
2716 * @param existing_finger Finger
2717 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2718 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2719 * @param new_finger_trail_id Unique identifier of the trail.
2722 add_new_trail (struct FingerInfo *existing_finger,
2723 const struct GNUNET_PeerIdentity *new_trail,
2724 unsigned int new_trail_length,
2725 struct GNUNET_HashCode new_trail_id)
2727 struct Trail *trail;
2728 struct FriendInfo *first_friend;
2732 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2738 index = existing_finger->trails_count;
2739 trail = &existing_finger->trail_list[index];
2740 GNUNET_assert (GNUNET_NO == trail->is_present);
2741 trail->trail_id = new_trail_id;
2742 trail->trail_length = new_trail_length;
2743 existing_finger->trails_count++;
2744 trail->is_present = GNUNET_YES;
2746 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2747 &existing_finger->finger_identity)));
2748 /* If finger is a friend then we never call this function. */
2749 GNUNET_assert (new_trail_length > 0);
2751 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2753 first_friend->trails_count++;
2755 for (i = 0; i < new_trail_length; i++)
2757 struct Trail_Element *element;
2759 element = GNUNET_new (struct Trail_Element);
2760 element->peer = new_trail[i];
2761 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2765 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2766 existing_finger->trail_list[index].trail_head = trail->trail_head;
2767 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2768 existing_finger->trail_list[index].trail_length = new_trail_length;
2769 existing_finger->trail_list[index].trail_id = new_trail_id;
2770 existing_finger->trail_list[index].is_present = GNUNET_YES;
2775 * FIXME Check if this function is called for opposite direction if yes then
2776 * take it as parameter.
2777 * Get the next hop to send trail teardown message from routing table and
2778 * then delete the entry from routing table. Send trail teardown message for a
2779 * specific trail of a finger.
2780 * @param finger Finger whose trail is to be removed.
2781 * @param trail List of peers in trail from me to a finger, NOT including
2785 send_trail_teardown (struct FingerInfo *finger,
2786 struct Trail *trail)
2788 struct FriendInfo *friend;
2789 struct GNUNET_PeerIdentity *next_hop;
2791 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2792 GDS_ROUTING_SRC_TO_DEST);
2794 if (NULL == next_hop)
2796 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
2797 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
2802 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2805 /*FIXME: here was an assertion that trail->is_present = GNUNET_YES. But it
2806 used to fail. We have removed assertion with a condition, just for now.
2807 Find out the reason why assertion failed. */
2808 if (trail->is_present == GNUNET_NO)
2810 DEBUG(" trail id %s of peer %s is not present to send a trail teardown message., line",
2811 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
2815 /* Finger is not a friend. */
2816 if (trail->trail_length > 0)
2818 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2819 &trail->trail_head->peer);
2823 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2824 &finger->finger_identity);
2829 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2830 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
2833 if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)
2834 && (0 == trail->trail_length))
2836 //FIXME HERE WE GOT NEXT HOP FRM ROUTING TABLE, AND TRAIL ENGTH - 0, IT ITS
2837 // THE CASE WEHERE WE SET IT TO 0.
2838 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2839 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
2842 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2843 friend->trails_count--;
2844 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2845 GDS_ROUTING_SRC_TO_DEST,
2851 * Send trail teardown message across all the trails to reach to finger.
2852 * @param finger Finger whose all the trail should be freed.
2855 send_all_finger_trails_teardown (struct FingerInfo *finger)
2858 for (i = 0; i < finger->trails_count; i++)
2860 struct Trail *trail;
2862 trail = &finger->trail_list[i];
2863 GNUNET_assert (trail->is_present == GNUNET_YES);
2864 send_trail_teardown (finger, trail);
2865 trail->is_present = GNUNET_NO;
2871 * Free a specific trail
2872 * @param trail List of peers to be freed.
2875 free_trail (struct Trail *trail)
2877 struct Trail_Element *trail_element;
2879 while (NULL != (trail_element = trail->trail_head))
2881 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2884 GNUNET_free_non_null (trail_element);
2886 trail->trail_head = NULL;
2887 trail->trail_tail = NULL;
2892 * Free finger and its trail.
2893 * @param finger Finger to be freed.
2894 * @param finger_table_index Index at which finger is stored.
2897 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2899 struct Trail *trail;
2901 for (i = 0; i < finger->trails_count; i++)
2903 trail = &finger->trail_list[i];
2904 if (GNUNET_NO == trail->is_present)
2907 if (trail->trail_length > 0)
2909 trail->is_present = GNUNET_NO;
2912 finger->is_present = GNUNET_NO;
2913 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2918 * Add a new entry in finger table at finger_table_index.
2919 * In case I am my own finger, then we don't have a trail. In case of a friend,
2920 * we have a trail with unique id and '0' trail length.
2921 * In case a finger is a friend, then increment the trails count of the friend.
2922 * @param finger_identity Peer Identity of new finger
2923 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2924 * @param finger_trail_length Total number of peers in @a finger_trail.
2925 * @param trail_id Unique identifier of the trail.
2926 * @param finger_table_index Index in finger table.
2929 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2930 const struct GNUNET_PeerIdentity *finger_trail,
2931 unsigned int finger_trail_length,
2932 struct GNUNET_HashCode trail_id,
2933 unsigned int finger_table_index)
2935 struct FingerInfo *new_entry;
2936 struct FriendInfo *first_trail_hop;
2937 struct Trail *trail;
2940 new_entry = GNUNET_new (struct FingerInfo);
2941 new_entry->finger_identity = finger_identity;
2942 new_entry->finger_table_index = finger_table_index;
2943 new_entry->is_present = GNUNET_YES;
2945 /* If the new entry is my own identity. */
2946 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2949 new_entry->trails_count = 0;
2950 finger_table[finger_table_index] = *new_entry;
2951 GNUNET_free (new_entry);
2955 /* If finger is a friend, then we don't actually have a trail.
2956 * Just a trail id */
2957 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2960 //FIXME: HERE WE SET TRAIL LENGTH TO 0, EVEN THOUGH IT HAS ENTRIES.
2961 new_entry->trail_list[0].trail_id = trail_id;
2962 new_entry->trails_count = 1;
2963 new_entry->trail_list[0].is_present = GNUNET_YES;
2964 new_entry->trail_list[0].trail_length = 0;
2965 new_entry->trail_list[0].trail_head = NULL;
2966 new_entry->trail_list[0].trail_tail = NULL;
2967 finger_table[finger_table_index] = *new_entry;
2968 GNUNET_assert (NULL !=
2970 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2971 &finger_identity)));
2973 first_trail_hop->trails_count++;
2974 GNUNET_free (new_entry);
2978 GNUNET_assert (NULL !=
2980 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2981 &finger_trail[0])));
2982 new_entry->trails_count = 1;
2983 first_trail_hop->trails_count++;
2984 GNUNET_assert (finger_trail_length != 0);
2985 /* Copy the finger trail into trail. */
2986 trail = GNUNET_new (struct Trail);
2987 for(i = 0; i < finger_trail_length; i++)
2989 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2991 element->next = NULL;
2992 element->prev = NULL;
2993 element->peer = finger_trail[i];
2994 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3000 /* Add trail to trail list. */
3001 new_entry->trail_list[0].trail_head = trail->trail_head;
3002 new_entry->trail_list[0].trail_tail = trail->trail_tail;
3003 new_entry->trail_list[0].trail_length = finger_trail_length;
3004 new_entry->trail_list[0].trail_id = trail_id;
3005 new_entry->trail_list[0].is_present = GNUNET_YES;
3006 finger_table[finger_table_index] = *new_entry;
3007 GNUNET_free (new_entry);
3013 * Periodic task to verify current successor. There can be multiple trails to reach
3014 * to successor, choose the shortest one and send verify successor message
3015 * across that trail.
3016 * @param cls closure for this task
3017 * @param tc the context under which the task is running
3020 send_verify_successor_message (void *cls,
3021 const struct GNUNET_SCHEDULER_TaskContext *tc)
3023 struct FriendInfo *target_friend;
3024 struct GNUNET_HashCode trail_id;
3026 struct Trail *trail;
3027 struct Trail_Element *element;
3028 unsigned int trail_length;
3030 struct FingerInfo *successor;
3032 /* Schedule another send_find_finger_trail_message task.
3033 verify_successor_next_send_time.rel_value_us =
3034 verify_successor_next_send_time.rel_value_us +
3035 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3036 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);*/
3037 send_verify_successor_task =
3038 GNUNET_SCHEDULER_add_delayed (verify_successor_next_send_time,
3039 &send_verify_successor_message,
3042 successor = &finger_table[0];
3043 for (i = 0; i < successor->trails_count; i++)
3045 trail = &successor->trail_list[i];
3046 if(GNUNET_YES == trail->is_present)
3050 /* No valid trail found to reach to successor. */
3051 if (i == successor->trails_count)
3054 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3055 &successor->finger_identity));
3057 /* Trail stored at this index. */
3058 GNUNET_assert (GNUNET_YES == trail->is_present);
3060 trail_id = trail->trail_id;
3061 if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST))
3063 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3064 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
3068 trail_length = trail->trail_length;
3070 if (trail_length > 0)
3072 /* Copy the trail into peer list. */
3073 struct GNUNET_PeerIdentity peer_list[trail_length];
3075 element = trail->trail_head;
3076 for(j = 0; j < trail_length; j++)
3078 peer_list[j] = element->peer;
3079 element = element->next;
3082 GNUNET_assert (NULL != (target_friend =
3083 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3085 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3086 successor->finger_identity,
3087 trail_id, peer_list, trail_length,
3093 GNUNET_assert (NULL != (target_friend =
3094 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3095 &successor->finger_identity)));
3096 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3097 successor->finger_identity,
3106 * FIXME: should this be a periodic task, incrementing the search finger index?
3107 * Update the current search finger index.
3109 * FIXME document parameters!
3112 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3113 unsigned int finger_table_index)
3115 struct FingerInfo *successor;
3117 /* FIXME correct this: only move current index periodically */
3118 if (finger_table_index != current_search_finger_index)
3121 successor = &finger_table[0];
3122 GNUNET_assert (GNUNET_YES == successor->is_present);
3124 /* We were looking for immediate successor. */
3125 if (0 == current_search_finger_index)
3127 /* Start looking for immediate predecessor. */
3128 current_search_finger_index = PREDECESSOR_FINGER_ID;
3130 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3132 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3134 send_verify_successor_task =
3135 GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3141 current_search_finger_index = current_search_finger_index - 1;
3147 * Get the least significant bit set in val.
3150 * @return Position of first bit set, 65 in case of error.
3153 find_set_bit (uint64_t val)
3173 return 65; /* Some other bit was set to 1 as well. */
3180 * Calculate finger_table_index from initial 64 bit finger identity value that
3181 * we send in trail setup message.
3182 * @param ultimate_destination_finger_value Value that we calculated from our
3183 * identity and finger_table_index.
3184 * @param is_predecessor Is the entry for predecessor or not?
3185 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3186 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3189 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3190 unsigned int is_predecessor)
3194 unsigned int finger_table_index;
3196 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3197 my_id64 = GNUNET_ntohll (my_id64);
3199 /* Is this a predecessor finger? */
3200 if (1 == is_predecessor)
3202 diff = my_id64 - ultimate_destination_finger_value;
3204 finger_table_index = PREDECESSOR_FINGER_ID;
3206 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3211 diff = ultimate_destination_finger_value - my_id64;
3212 finger_table_index = find_set_bit (diff);
3214 return finger_table_index;
3219 * Remove finger and its associated data structures from finger table.
3220 * @param existing_finger Finger to be removed which is in finger table.
3221 * @param finger_table_index Index in finger table where @a existing_finger
3225 remove_existing_finger (struct FingerInfo *existing_finger,
3226 unsigned int finger_table_index)
3228 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3230 /* If I am my own finger, then we have no trails. */
3231 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3234 existing_finger->is_present = GNUNET_NO;
3235 memset ((void *)&finger_table[finger_table_index], 0,
3236 sizeof (finger_table[finger_table_index]));
3240 /* For all other fingers, send trail teardown across all the trails to reach
3241 finger, and free the finger. */
3242 send_all_finger_trails_teardown (existing_finger);
3243 free_finger (existing_finger, finger_table_index);
3249 * Check if there is already an entry in finger_table at finger_table_index.
3250 * We get the finger_table_index from 64bit finger value we got from the network.
3251 * -- If yes, then select the closest finger.
3252 * -- If new and existing finger are same, then check if you can store more
3254 * -- If yes then add trail, else keep the best trails to reach to the
3256 * -- If the new finger is closest, remove the existing entry, send trail
3257 * teardown message across all the trails to reach the existing entry.
3258 * Add the new finger.
3259 * -- If new and existing finger are different, and existing finger is closest
3261 * -- Update current_search_finger_index.
3262 * @param finger_identity Peer Identity of new finger
3263 * @param finger_trail Trail to reach the new finger
3264 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3265 * @param is_predecessor Is this entry for predecessor in finger_table?
3266 * @param finger_value 64 bit value of finger identity that we got from network.
3267 * @param finger_trail_id Unique identifier of @finger_trail.
3270 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3271 const struct GNUNET_PeerIdentity *finger_trail,
3272 unsigned int finger_trail_length,
3273 unsigned int is_predecessor,
3274 uint64_t finger_value,
3275 struct GNUNET_HashCode finger_trail_id)
3277 struct FingerInfo *existing_finger;
3278 struct GNUNET_PeerIdentity closest_peer;
3279 struct FingerInfo *successor;
3280 unsigned int finger_table_index;
3282 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3283 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3285 /* Invalid finger_table_index. */
3286 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3288 GNUNET_break_op (0);
3292 /* New entry same as successor. */
3293 if ((0 != finger_table_index) &&
3294 (PREDECESSOR_FINGER_ID != finger_table_index))
3296 successor = &finger_table[0];
3297 if (GNUNET_NO == successor->is_present)
3302 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3303 &successor->finger_identity))
3305 find_finger_trail_task_next_send_time =
3306 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3307 current_search_finger_index = 0;
3311 struct FingerInfo prev_finger;
3312 prev_finger = finger_table[finger_table_index - 1];
3313 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3314 &prev_finger.finger_identity))
3316 current_search_finger_index--;
3321 existing_finger = &finger_table[finger_table_index];
3323 /* No entry present in finger_table for given finger map index. */
3324 if (GNUNET_NO == existing_finger->is_present)
3326 add_new_finger (finger_identity, finger_trail,
3327 finger_trail_length,
3328 finger_trail_id, finger_table_index);
3329 update_current_search_finger_index (finger_identity,
3330 finger_table_index);
3335 /* If existing entry and finger identity are not same. */
3336 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3339 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3344 /* If the new finger is the closest peer. */
3345 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer))
3347 remove_existing_finger (existing_finger, finger_table_index);
3348 add_new_finger (finger_identity, finger_trail, finger_trail_length,
3349 finger_trail_id, finger_table_index);
3353 /* Existing finger is the closest one. We need to send trail teardown
3354 across the trail setup in routing table of all the peers. */
3355 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3357 if (finger_trail_length > 0)
3358 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3359 GDS_ROUTING_SRC_TO_DEST,
3362 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3363 GDS_ROUTING_SRC_TO_DEST,
3370 /* If both new and existing entry are same as my_identity, then do nothing. */
3371 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3376 /* If the existing finger is not a friend. */
3378 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3379 &existing_finger->finger_identity))
3381 /* If there is space to store more trails. */
3382 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3383 add_new_trail (existing_finger, finger_trail,
3384 finger_trail_length, finger_trail_id);
3386 select_and_replace_trail (existing_finger, finger_trail,
3387 finger_trail_length, finger_trail_id);
3391 update_current_search_finger_index (finger_identity, finger_table_index);
3397 * FIXME: Check for loop in the request. If you already are part of put path,
3398 * then you need to reset the put path length.
3399 * Core handler for P2P put messages.
3400 * @param cls closure
3401 * @param peer sender of the request
3402 * @param message message
3403 * @return #GNUNET_OK to keep the connection open,
3404 * #GNUNET_SYSERR to close it (signal serious error)
3407 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3408 const struct GNUNET_MessageHeader *message)
3410 struct PeerPutMessage *put;
3411 struct GNUNET_PeerIdentity *put_path;
3412 struct GNUNET_PeerIdentity best_known_dest;
3413 struct GNUNET_HashCode intermediate_trail_id;
3414 struct GNUNET_PeerIdentity *next_hop;
3415 enum GNUNET_DHT_RouteOption options;
3416 struct GNUNET_HashCode test_key;
3421 size_t payload_size;
3424 #if ENABLE_MALICIOUS
3425 if(1 == act_malicious)
3427 DEBUG("I am malicious,dropping put request. \n");
3432 msize = ntohs (message->size);
3433 if (msize < sizeof (struct PeerPutMessage))
3435 GNUNET_break_op (0);
3439 put = (struct PeerPutMessage *) message;
3440 putlen = ntohl (put->put_path_length);
3442 sizeof (struct PeerPutMessage) +
3443 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3445 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3447 GNUNET_break_op (0);
3450 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
3451 GNUNET_STATISTICS_update (GDS_stats,
3453 ("# Bytes received from other peers"), (int64_t) msize,
3456 best_known_dest = put->best_known_destination;
3457 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3458 payload = &put_path[putlen];
3459 options = ntohl (put->options);
3460 intermediate_trail_id = put->intermediate_trail_id;
3461 hop_count = ntohl(put->hop_count);
3462 payload_size = msize - (sizeof (struct PeerPutMessage) +
3463 putlen * sizeof (struct GNUNET_PeerIdentity));
3465 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3466 payload, payload_size, &test_key))
3469 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3471 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3472 GNUNET_break_op (0);
3473 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3474 "PUT with key `%s' for block with key %s\n",
3475 put_s, GNUNET_h2s_full (&test_key));
3476 GNUNET_free (put_s);
3481 GNUNET_break_op (0);
3484 /* cannot verify, good luck */
3488 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3490 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3491 ntohl (put->block_type),
3493 NULL, 0, /* bloom filer */
3494 NULL, 0, /* xquery */
3495 payload, payload_size))
3497 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3498 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3501 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3502 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3503 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3504 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3505 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3506 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3508 GNUNET_break_op (0);
3513 /* Check if you are already a part of put path. */
3515 for (i = 0; i < putlen; i++)
3517 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3524 /* Add yourself to the list. */
3525 struct GNUNET_PeerIdentity pp[putlen + 1];
3526 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3528 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3529 pp[putlen] = my_identity;
3535 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3536 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3538 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3539 GDS_ROUTING_SRC_TO_DEST);
3540 if (NULL == next_hop)
3542 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3543 GNUNET_i2s(&my_identity), GNUNET_h2s(&intermediate_trail_id), __LINE__);
3544 GNUNET_STATISTICS_update (GDS_stats,
3545 gettext_noop ("# Next hop to forward the packet not found "
3546 "trail setup request, packet dropped."),
3549 GNUNET_break_op (0);
3550 //FIXME: Adding put here,only to ensure that process does not hang. but
3551 // should not be here. fix the logic.
3552 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3553 &(put->key),putlen, pp, ntohl (put->block_type),
3554 payload_size, payload);
3559 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3565 struct Closest_Peer successor;
3566 key_value = GNUNET_ntohll (key_value);
3567 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3568 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3569 *next_hop = successor.next_hop;
3570 intermediate_trail_id = successor.trail_id;
3571 best_known_dest = successor.best_known_destination;
3576 GDS_CLIENTS_process_put (options,
3577 ntohl (put->block_type),
3579 ntohl (put->desired_replication_level),
3581 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3586 /* I am the final destination */
3587 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3589 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3590 &(put->key),putlen, pp, ntohl (put->block_type),
3591 payload_size, payload);
3595 GDS_NEIGHBOURS_send_put (&put->key,
3596 ntohl (put->block_type),ntohl (put->options),
3597 ntohl (put->desired_replication_level),
3598 best_known_dest, intermediate_trail_id, next_hop,
3599 hop_count, putlen, pp,
3600 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3601 payload, payload_size);
3608 * FIXME: Check for loop in the request. If you already are part of get path,
3609 * then you need to reset the get path length.
3610 * Core handler for p2p get requests.
3612 * @param cls closure
3613 * @param peer sender of the request
3614 * @param message message
3615 * @return #GNUNET_OK to keep the connection open,
3616 * #GNUNET_SYSERR to close it (signal serious error)
3619 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3620 const struct GNUNET_MessageHeader *message)
3622 const struct PeerGetMessage *get;
3623 const struct GNUNET_PeerIdentity *get_path;
3624 struct GNUNET_PeerIdentity best_known_dest;
3625 struct GNUNET_HashCode intermediate_trail_id;
3626 struct GNUNET_PeerIdentity *next_hop;
3627 uint32_t get_length;
3632 #if ENABLE_MALICIOUS
3633 if(1 == act_malicious)
3635 DEBUG("I am malicious,dropping get request. \n");
3640 msize = ntohs (message->size);
3641 if (msize < sizeof (struct PeerGetMessage))
3643 GNUNET_break_op (0);
3647 get = (const struct PeerGetMessage *)message;
3648 get_length = ntohl (get->get_path_length);
3649 best_known_dest = get->best_known_destination;
3650 intermediate_trail_id = get->intermediate_trail_id;
3651 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3652 hop_count = get->hop_count;
3656 sizeof (struct PeerGetMessage) +
3657 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3659 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3661 GNUNET_break_op (0);
3665 GNUNET_STATISTICS_update (GDS_stats,
3667 ("# Bytes received from other peers"), msize,
3670 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3671 key_value = GNUNET_ntohll (key_value);
3673 /* Check if you are already a part of get path. */
3675 for (i = 0; i < get_length; i++)
3677 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &get_path[i]))
3684 /* Add yourself in the get path. */
3685 struct GNUNET_PeerIdentity gp[get_length + 1];
3686 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3687 gp[get_length] = my_identity;
3688 get_length = get_length + 1;
3689 GDS_CLIENTS_process_get (get->options, get->block_type, hop_count,
3690 get->desired_replication_level, get->get_path_length,
3693 /* I am not the final destination. I am part of trail to reach final dest. */
3694 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3696 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3697 GDS_ROUTING_SRC_TO_DEST);
3698 if (NULL == next_hop)
3700 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3701 GNUNET_i2s(&my_identity), GNUNET_h2s(&intermediate_trail_id), __LINE__);
3702 GNUNET_STATISTICS_update (GDS_stats,
3703 gettext_noop ("# Next hop to forward the packet not found "
3704 "GET request, packet dropped."),
3707 /* We are not able to proceed further*/
3708 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3709 get_length, gp, &gp[get_length - 2],
3716 struct Closest_Peer successor;
3718 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3719 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3720 *next_hop = successor.next_hop;
3721 best_known_dest = successor.best_known_destination;
3722 intermediate_trail_id = successor.trail_id;
3725 /* I am the final destination. */
3726 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3728 if (1 == get_length)
3730 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0,
3731 NULL, 0, 1, &my_identity, NULL,&my_identity);
3735 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3736 get_length, gp, &gp[get_length - 2],
3742 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3743 get->desired_replication_level, best_known_dest,
3744 intermediate_trail_id, next_hop, hop_count,
3752 * Core handler for get result
3753 * @param cls closure
3754 * @param peer sender of the request
3755 * @param message message
3756 * @return #GNUNET_OK to keep the connection open,
3757 * #GNUNET_SYSERR to close it (signal serious error)
3760 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3761 const struct GNUNET_MessageHeader *message)
3763 const struct PeerGetResultMessage *get_result;
3764 const struct GNUNET_PeerIdentity *get_path;
3765 const struct GNUNET_PeerIdentity *put_path;
3766 const void *payload;
3767 size_t payload_size;
3769 unsigned int getlen;
3770 unsigned int putlen;
3771 int current_path_index;
3773 msize = ntohs (message->size);
3774 if (msize < sizeof (struct PeerGetResultMessage))
3776 GNUNET_break_op (0);
3780 get_result = (const struct PeerGetResultMessage *)message;
3781 getlen = ntohl (get_result->get_path_length);
3782 putlen = ntohl (get_result->put_path_length);
3785 sizeof (struct PeerGetResultMessage) +
3786 getlen * sizeof (struct GNUNET_PeerIdentity) +
3787 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3789 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3791 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3793 GNUNET_break_op (0);
3796 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3797 GNUNET_STATISTICS_update (GDS_stats,
3799 ("# Bytes received from other peers"), msize,
3802 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3803 get_path = &put_path[putlen];
3804 payload = (const void *) &get_path[getlen];
3805 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3806 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3808 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3810 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3811 getlen, get_path, putlen,
3812 put_path, get_result->type, payload_size, payload);
3817 current_path_index = search_my_index (get_path, getlen);
3818 if (-1 == current_path_index )
3820 DEBUG ("No entry found in get path.\n");
3822 return GNUNET_SYSERR;
3824 if((getlen + 1) == current_path_index)
3826 DEBUG("Present twice in get path. Not allowed. \n");
3828 return GNUNET_SYSERR;
3830 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3831 &get_path[current_path_index - 1],
3832 &(get_result->querying_peer), putlen, put_path,
3833 getlen, get_path, get_result->expiration_time,
3834 payload, payload_size);
3837 return GNUNET_SYSERR;
3842 * Find the next hop to pass trail setup message. First find the local best known
3843 * hop from your own identity, friends and finger. If you were part of trail,
3844 * then get the next hop from routing table. Compare next_hop from routing table
3845 * and local best known hop, and return the closest one to final_dest_finger_val
3846 * @param final_dest_finger_val 64 bit value of finger identity
3847 * @param intermediate_trail_id If you are part of trail to reach to some other
3848 * finger, then it is the trail id to reach to
3849 * that finger, else set to 0.
3850 * @param is_predecessor Are we looking for closest successor or predecessor.
3851 * @param current_dest In case you are part of trail, then finger to which
3852 * we should forward the message. Else my own identity
3853 * @return Closest Peer for @a final_dest_finger_val
3855 static struct Closest_Peer
3856 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3857 struct GNUNET_HashCode intermediate_trail_id,
3858 unsigned int is_predecessor,
3859 struct GNUNET_PeerIdentity prev_hop,
3860 struct GNUNET_PeerIdentity source,
3861 struct GNUNET_PeerIdentity *current_dest)
3863 struct Closest_Peer peer;
3865 /* Find a local best known peer. */
3866 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3868 /* Am I just a part of a trail towards a finger (current_destination)? */
3869 /* Select best successor among one found locally and current_destination
3870 * that we got from network.*/
3871 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3872 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3875 struct GNUNET_PeerIdentity closest_peer;
3877 closest_peer = select_closest_peer (&peer.best_known_destination,
3879 final_dest_finger_val,
3882 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3883 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
3885 struct GNUNET_PeerIdentity *next_hop;
3887 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3888 GDS_ROUTING_SRC_TO_DEST);
3889 /* next_hop NULL is a valid case. This intermediate trail id is set by
3890 some other finger, and while this trail setup is in progress, that other
3891 peer might have found a better trail ,and send trail teardown message
3892 across the network. In case we got the trail teardown message first,
3893 then next_hop will be NULL. A possible solution could be to keep track
3894 * of all removed trail id, and be sure that there is no other reason . */
3895 if(NULL != next_hop)
3897 peer.next_hop = *next_hop;
3898 peer.best_known_destination = *current_dest;
3899 peer.trail_id = intermediate_trail_id;
3908 * Core handle for PeerTrailSetupMessage.
3909 * @param cls closure
3910 * @param message message
3911 * @param peer peer identity this notification is about
3912 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3915 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3916 const struct GNUNET_MessageHeader *message)
3918 const struct PeerTrailSetupMessage *trail_setup;
3919 const struct GNUNET_PeerIdentity *trail_peer_list;
3920 struct GNUNET_PeerIdentity current_dest;
3921 struct FriendInfo *target_friend;
3922 struct GNUNET_PeerIdentity source;
3923 uint64_t final_dest_finger_val;
3924 struct GNUNET_HashCode intermediate_trail_id;
3925 struct GNUNET_HashCode trail_id;
3926 unsigned int is_predecessor;
3927 uint32_t trail_length;
3931 msize = ntohs (message->size);
3932 if (msize < sizeof (struct PeerTrailSetupMessage))
3934 GNUNET_break_op (0);
3935 return GNUNET_SYSERR;
3938 trail_setup = (const struct PeerTrailSetupMessage *) message;
3939 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3940 sizeof (struct GNUNET_PeerIdentity) != 0)
3942 GNUNET_break_op (0);
3945 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3946 sizeof (struct GNUNET_PeerIdentity);
3948 GNUNET_STATISTICS_update (GDS_stats,
3950 ("# Bytes received from other peers"), msize,
3953 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3954 current_dest = trail_setup->best_known_destination;
3955 trail_id = trail_setup->trail_id;
3956 final_dest_finger_val =
3957 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3958 source = trail_setup->source_peer;
3959 is_predecessor = ntohl (trail_setup->is_predecessor);
3960 intermediate_trail_id = trail_setup->intermediate_trail_id;
3962 /* Did the friend insert its ID in the trail list? */
3963 if (trail_length > 0 &&
3964 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
3966 GNUNET_break_op (0);
3967 return GNUNET_SYSERR;
3970 /* If I was the source and got the message back, then set trail length to 0.*/
3971 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3976 /* SUPUS: remove the check that source is a friend, because again source
3977 may become aware about it later. and by that time lookup may fail. */
3979 /* Check if you are present in the trail seen so far? */
3980 for (i = 0; i < trail_length ; i++)
3982 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
3984 trail_length = i; /* Check that you add yourself again */
3989 /* Is my routing table full? */
3990 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3992 if (trail_length > 0)
3994 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3995 &trail_peer_list[trail_length - 1]);
3998 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4001 if(NULL == target_friend)
4003 DEBUG ("\n friend not found");
4008 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4009 my_identity, is_predecessor,
4010 trail_peer_list, trail_length,
4011 trail_id, target_friend,
4012 CONGESTION_TIMEOUT);
4016 /* Get the next hop to forward the trail setup request. */
4017 struct Closest_Peer next_peer =
4018 get_local_best_known_next_hop (final_dest_finger_val,
4019 intermediate_trail_id,
4025 /* Am I the final destination? */
4026 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4029 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4031 finger_table_add (my_identity, NULL, 0, is_predecessor,
4032 final_dest_finger_val, trail_id);
4036 if (trail_length > 0)
4038 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4039 &trail_peer_list[trail_length-1]);
4042 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4044 if (NULL == target_friend)
4046 GNUNET_break_op (0);
4047 return GNUNET_SYSERR;
4049 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4050 GDS_NEIGHBOURS_send_trail_setup_result (source,
4052 target_friend, trail_length,
4055 final_dest_finger_val,trail_id);
4057 else /* I'm not the final destination. */
4059 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4060 &next_peer.next_hop);
4061 if(NULL == target_friend)
4063 DEBUG ("\n target friend not found for peer = %s", GNUNET_i2s(&next_peer.next_hop));
4068 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4070 /* Add yourself to list of peers. */
4071 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4073 memcpy (peer_list, trail_peer_list,
4074 trail_length * sizeof (struct GNUNET_PeerIdentity));
4075 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,
4163 GDS_ROUTING_add (trail_id, my_identity, *peer);
4164 finger_table_add (finger_identity, trail_peer_list, trail_length,
4165 is_predecessor, ulitmate_destination_finger_value, trail_id);
4169 /* Get my location in the trail. */
4170 my_index = search_my_index (trail_peer_list, trail_length);
4173 DEBUG ("Not found in trail\n");
4175 return GNUNET_SYSERR;
4178 if ((trail_length + 1) == my_index)
4180 DEBUG ("Found twice in trail.\n");
4182 return GNUNET_SYSERR;
4185 //TODO; Refactor code here and above to check if sender peer is correct
4188 if(trail_length > 1)
4189 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4192 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4194 next_hop = trail_result->querying_peer;
4198 if(my_index == trail_length - 1)
4201 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4206 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4208 next_hop = trail_peer_list[my_index - 1];
4211 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4212 if (NULL == target_friend)
4214 GNUNET_break_op (0);
4215 return GNUNET_SYSERR;
4217 GDS_ROUTING_add (trail_id, next_hop, *peer);
4218 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4219 target_friend, trail_length, trail_peer_list,
4221 ulitmate_destination_finger_value,
4229 * @param trail Trail to be inverted
4230 * @param trail_length Total number of peers in the trail.
4231 * @return Updated trail
4233 static struct GNUNET_PeerIdentity *
4234 invert_trail (const struct GNUNET_PeerIdentity *trail,
4235 unsigned int trail_length)
4239 struct GNUNET_PeerIdentity *inverted_trail;
4241 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4244 j = trail_length - 1;
4245 while (i < trail_length)
4247 inverted_trail[i] = trail[j];
4252 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4253 &inverted_trail[0]));
4254 return inverted_trail;
4259 * Return the shortest trail among all the trails to reach to finger from me.
4260 * @param finger Finger
4261 * @param shortest_trail_length[out] Trail length of shortest trail from me
4263 * @return Shortest trail.
4265 static struct GNUNET_PeerIdentity *
4266 get_shortest_trail (struct FingerInfo *finger,
4267 unsigned int *trail_length)
4269 struct Trail *trail;
4270 unsigned int flag = 0;
4271 unsigned int shortest_trail_index = 0;
4272 int shortest_trail_length = -1;
4273 struct Trail_Element *trail_element;
4274 struct GNUNET_PeerIdentity *trail_list;
4277 trail = GNUNET_new (struct Trail);
4279 /* Get the shortest trail to reach to current successor. */
4280 for (i = 0; i < finger->trails_count; i++)
4282 trail = &finger->trail_list[i];
4286 shortest_trail_index = i;
4287 shortest_trail_length = trail->trail_length;
4292 if (shortest_trail_length > trail->trail_length)
4294 shortest_trail_index = i;
4295 shortest_trail_length = trail->trail_length;
4300 /* Copy the shortest trail and return. */
4301 trail = &finger->trail_list[shortest_trail_index];
4302 trail_element = trail->trail_head;
4304 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4305 shortest_trail_length);
4307 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4309 trail_list[i] = trail_element->peer;
4312 GNUNET_assert(shortest_trail_length != -1);
4314 *trail_length = shortest_trail_length;
4320 * Check if trail_1 and trail_2 have any common element. If yes then join
4321 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4322 * @param trail_1 Trail from source to me, NOT including endpoints.
4323 * @param trail_1_len Total number of peers @a trail_1
4324 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4325 * @param trail_2_len Total number of peers @a trail_2
4326 * @param joined_trail_len Total number of peers in combined trail of trail_1
4328 * @return Joined trail.
4330 static struct GNUNET_PeerIdentity *
4331 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4332 unsigned int trail_1_len,
4333 struct GNUNET_PeerIdentity *trail_2,
4334 unsigned int trail_2_len,
4335 unsigned int *joined_trail_len)
4337 struct GNUNET_PeerIdentity *joined_trail;
4342 for (i = 0; i < trail_1_len; i++)
4344 for (j = 0; j < trail_2_len; j++)
4346 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4349 *joined_trail_len = i + (trail_2_len - j);
4350 joined_trail = GNUNET_malloc (*joined_trail_len *
4351 sizeof(struct GNUNET_PeerIdentity));
4354 /* Copy all the elements from 0 to i into joined_trail. */
4355 for(k = 0; k < ( i+1); k++)
4357 joined_trail[k] = trail_1[k];
4360 /* Increment j as entry stored is same as entry stored at i*/
4363 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4364 while(k <= (*joined_trail_len - 1))
4366 joined_trail[k] = trail_2[j];
4371 return joined_trail;
4375 /* Here you should join the trails. */
4376 *joined_trail_len = trail_1_len + trail_2_len + 1;
4377 joined_trail = GNUNET_malloc (*joined_trail_len *
4378 sizeof(struct GNUNET_PeerIdentity));
4381 for(i = 0; i < trail_1_len;i++)
4383 joined_trail[i] = trail_1[i];
4386 joined_trail[i] = my_identity;
4389 for (j = 0; i < *joined_trail_len; i++,j++)
4391 joined_trail[i] = trail_2[j];
4394 return joined_trail;
4399 * Return the trail from source to my current predecessor. Check if source
4400 * is already part of the this trail, if yes then return the shorten trail.
4401 * @param current_trail Trail from source to me, NOT including the endpoints.
4402 * @param current_trail_length Number of peers in @a current_trail.
4403 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4404 * source to my predecessor, NOT including
4406 * @return Trail from source to my predecessor.
4408 static struct GNUNET_PeerIdentity *
4409 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4410 const struct GNUNET_PeerIdentity *trail_src_to_me,
4411 unsigned int trail_src_to_me_len,
4412 unsigned int *trail_src_to_curr_pred_length)
4414 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4415 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4416 unsigned int trail_me_to_curr_pred_length;
4417 struct FingerInfo *current_predecessor;
4421 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4423 /* Check if trail_src_to_me contains current_predecessor. */
4424 for (i = 0; i < trail_src_to_me_len; i++)
4426 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4427 ¤t_predecessor->finger_identity))
4431 *trail_src_to_curr_pred_length = i;
4436 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4437 sizeof(struct GNUNET_PeerIdentity));
4438 for(j = 0; j < i;j++)
4439 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4440 return trail_src_to_curr_pred;
4444 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4445 &trail_me_to_curr_pred_length);
4447 /* Check if trail contains the source_peer. */
4448 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4450 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4451 &trail_me_to_curr_pred[i]))
4454 /* Source is NOT part of trail. */
4457 /* Source is the last element in the trail to reach to my pred.
4458 Source is direct friend of the pred. */
4459 if (trail_me_to_curr_pred_length == i)
4461 *trail_src_to_curr_pred_length = 0;
4465 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4466 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4467 *trail_src_to_curr_pred_length);
4469 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4471 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4473 GNUNET_free_non_null(trail_me_to_curr_pred);
4474 return trail_src_to_curr_pred;
4478 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4479 trail_src_to_me_len,
4480 trail_me_to_curr_pred,
4481 trail_me_to_curr_pred_length,
4483 *trail_src_to_curr_pred_length = len;
4484 GNUNET_free_non_null(trail_me_to_curr_pred);
4485 return trail_src_to_curr_pred;
4490 * Add finger as your predecessor. To add, first generate a new trail id, invert
4491 * the trail to get the trail from me to finger, add an entry in your routing
4492 * table, send add trail message to peers which are part of trail from me to
4493 * finger and add finger in finger table.
4496 * @param trail_length
4499 update_predecessor (struct GNUNET_PeerIdentity finger,
4500 struct GNUNET_PeerIdentity *trail,
4501 unsigned int trail_length)
4503 struct GNUNET_HashCode trail_to_new_predecessor_id;
4504 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4505 struct FriendInfo *target_friend;
4507 /* Generate trail id for trail from me to new predecessor = finger. */
4508 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4509 &trail_to_new_predecessor_id,
4510 sizeof (trail_to_new_predecessor_id));
4512 /* Finger is a friend. */
4513 if (trail_length == 0)
4515 trail_to_new_predecessor = NULL;
4516 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4517 GNUNET_assert (NULL != (target_friend =
4518 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4523 /* Invert the trail to get the trail from me to finger, NOT including the
4525 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4526 &trail[trail_length-1]));
4528 trail_to_new_predecessor = invert_trail (trail, trail_length);
4530 /* Add an entry in your routing table. */
4531 GDS_ROUTING_add (trail_to_new_predecessor_id,
4533 trail_to_new_predecessor[0]);
4535 GNUNET_assert (NULL != (target_friend =
4536 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4537 &trail_to_new_predecessor[0])));
4538 GNUNET_assert (NULL != (
4539 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4540 &trail[trail_length - 1])));
4543 /* Add entry in routing table of all peers that are part of trail from me
4544 to finger, including finger. */
4545 GDS_NEIGHBOURS_send_add_trail (my_identity,
4547 trail_to_new_predecessor_id,
4548 trail_to_new_predecessor,
4552 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4553 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4554 GNUNET_free_non_null(trail_to_new_predecessor);
4559 * Check if you already have a predecessor. If not then add finger as your
4560 * predecessor. If you have predecessor, then compare two peer identites.
4561 * If finger is correct predecessor, then remove the old entry, add finger in
4562 * finger table and send add_trail message to add the trail in the routing
4563 * table of all peers which are part of trail to reach from me to finger.
4564 * @param finger New peer which may be our predecessor.
4565 * @param trail List of peers to reach from @finger to me.
4566 * @param trail_length Total number of peer in @a trail.
4569 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4570 struct GNUNET_PeerIdentity *trail,
4571 unsigned int trail_length)
4573 struct FingerInfo *current_predecessor;
4574 struct GNUNET_PeerIdentity closest_peer;
4575 uint64_t predecessor_value;
4576 unsigned int is_predecessor = 1;
4578 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4579 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4581 /* No predecessor. Add finger as your predecessor. */
4582 if (GNUNET_NO == current_predecessor->is_present)
4584 update_predecessor (finger, trail, trail_length);
4588 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4594 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4595 closest_peer = select_closest_peer (&finger,
4596 ¤t_predecessor->finger_identity,
4597 predecessor_value, is_predecessor);
4599 /* Finger is the closest predecessor. Remove the existing one and add the new
4601 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4603 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4604 update_predecessor (finger, trail, trail_length);
4612 * Core handle for p2p verify successor messages.
4613 * @param cls closure
4614 * @param message message
4615 * @param peer peer identity this notification is about
4616 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4619 handle_dht_p2p_verify_successor(void *cls,
4620 const struct GNUNET_PeerIdentity *peer,
4621 const struct GNUNET_MessageHeader *message)
4623 const struct PeerVerifySuccessorMessage *vsm;
4624 struct GNUNET_HashCode trail_id;
4625 struct GNUNET_PeerIdentity successor;
4626 struct GNUNET_PeerIdentity source_peer;
4627 struct GNUNET_PeerIdentity *trail;
4628 struct GNUNET_PeerIdentity *next_hop;
4629 struct FingerInfo current_predecessor;
4630 struct FriendInfo *target_friend;
4631 unsigned int trail_src_to_curr_pred_len = 0;
4632 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4633 unsigned int trail_length;
4636 msize = ntohs (message->size);
4638 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4640 GNUNET_break_op (0);
4644 vsm = (const struct PeerVerifySuccessorMessage *) message;
4645 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4646 sizeof (struct GNUNET_PeerIdentity);
4647 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4648 sizeof (struct GNUNET_PeerIdentity) != 0)
4650 GNUNET_break_op (0);
4654 GNUNET_STATISTICS_update (GDS_stats,
4656 ("# Bytes received from other peers"), msize,
4659 trail_id = vsm->trail_id;
4660 source_peer = vsm->source_peer;
4661 successor = vsm->successor;
4662 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4664 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4666 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4668 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4669 if (NULL == next_hop)
4671 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
4672 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
4673 GNUNET_break_op (0);
4677 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4679 if(NULL == target_friend)
4684 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4685 trail_id, trail, trail_length,
4690 /* I am the destination of this message. */
4692 /* Check if the source_peer could be our predecessor and if yes then update
4694 compare_and_update_predecessor (source_peer, trail, trail_length);
4695 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4697 /* Is source of this message NOT my predecessor. */
4698 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4701 trail_src_to_curr_pred =
4702 get_trail_src_to_curr_pred (source_peer,
4705 &trail_src_to_curr_pred_len);
4709 trail_src_to_curr_pred_len = trail_length;
4712 trail_src_to_curr_pred =
4713 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4714 *trail_src_to_curr_pred_len);
4715 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4717 trail_src_to_curr_pred[i] = trail[i];
4721 GNUNET_assert (NULL !=
4723 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4724 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4725 current_predecessor.finger_identity,
4726 trail_id, trail_src_to_curr_pred,
4727 trail_src_to_curr_pred_len,
4728 GDS_ROUTING_DEST_TO_SRC,
4730 GNUNET_free_non_null(trail_src_to_curr_pred);
4736 * If the trail from me to my probable successor contains a friend not
4737 * at index 0, then we can shorten the trail.
4738 * @param probable_successor Peer which is our probable successor
4739 * @param trail_me_to_probable_successor Peers in path from me to my probable
4740 * successor, NOT including the endpoints.
4741 * @param trail_me_to_probable_successor_len Total number of peers in
4742 * @a trail_me_to_probable_succesor.
4743 * @return Updated trail, if any friend found.
4744 * Else the trail_me_to_probable_successor.
4746 struct GNUNET_PeerIdentity *
4747 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4748 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4749 unsigned int trail_me_to_probable_successor_len,
4750 unsigned int *trail_to_new_successor_length)
4754 struct GNUNET_PeerIdentity *trail_to_new_successor;
4756 /* Probable successor is a friend */
4757 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4758 &probable_successor))
4760 trail_to_new_successor = NULL;
4761 *trail_to_new_successor_length = 0;
4762 return trail_to_new_successor;
4765 /* Is there any friend of yours in this trail. */
4766 if(trail_me_to_probable_successor_len > 1)
4768 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4770 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4771 &trail_me_to_probable_successor[i]))
4774 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4775 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4776 *trail_to_new_successor_length);
4779 for(j = 0;j < *trail_to_new_successor_length;i++,j++)
4781 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4784 return trail_to_new_successor;
4788 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4789 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4794 * Check if the peer which sent us verify successor result message is still ours
4795 * successor or not. If not, then compare existing successor and probable successor.
4796 * In case probable successor is the correct successor, remove the existing
4797 * successor. Add probable successor as new successor. Send notify new successor
4798 * message to new successor.
4799 * @param curr_succ Peer to which we sent the verify successor message. It may
4800 * or may not be our real current successor, as we may have few iterations of
4801 * find finger trail task.
4802 * @param probable_successor Peer which should be our successor accroding to @a
4804 * @param trail List of peers to reach from me to @a probable successor, NOT including
4806 * @param trail_length Total number of peers in @a trail.
4809 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4810 struct GNUNET_PeerIdentity probable_successor,
4811 const struct GNUNET_PeerIdentity *trail,
4812 unsigned int trail_length)
4814 struct FingerInfo *current_successor;
4815 struct GNUNET_PeerIdentity closest_peer;
4816 struct GNUNET_HashCode trail_id;
4817 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4818 struct FriendInfo *target_friend;
4819 unsigned int trail_me_to_probable_succ_len;
4820 unsigned int is_predecessor = 0;
4821 uint64_t successor_value;
4823 current_successor = &finger_table[0];
4824 successor_value = compute_finger_identity_value(0);
4826 /* If probable successor is same as current_successor, do nothing. */
4827 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
4828 ¤t_successor->finger_identity))
4831 closest_peer = select_closest_peer (&probable_successor,
4832 ¤t_successor->finger_identity,
4833 successor_value, is_predecessor);
4835 /* If the current_successor in the finger table is closest, then do nothing. */
4836 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
4837 ¤t_successor->finger_identity))
4839 if ((NULL != GDS_stats))
4845 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4846 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4847 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4848 GNUNET_free (my_id_str);
4849 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4855 /* Probable successor is the closest peer.*/
4856 if(trail_length > 0)
4858 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4863 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4864 &probable_successor));
4867 trail_me_to_probable_succ_len = 0;
4868 trail_me_to_probable_succ =
4869 check_trail_me_to_probable_succ (probable_successor,
4870 trail, trail_length,
4871 &trail_me_to_probable_succ_len);
4873 /* Remove the existing successor. */
4874 remove_existing_finger (current_successor, 0);
4875 /* Generate a new trail id to reach to your new successor. */
4876 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4877 &trail_id, sizeof (trail_id));
4879 if (trail_me_to_probable_succ_len > 0)
4881 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4882 GNUNET_assert (NULL !=
4884 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4885 &trail_me_to_probable_succ[0])));
4889 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4890 GNUNET_assert (NULL !=
4892 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4893 &probable_successor)));
4896 add_new_finger (probable_successor, trail_me_to_probable_succ,
4897 trail_me_to_probable_succ_len, trail_id, 0);
4899 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4900 trail_me_to_probable_succ,
4901 trail_me_to_probable_succ_len,
4909 * FIXME: Check for duplicate elements everywhere when you are making
4911 * Core handle for p2p verify successor result messages.
4912 * @param cls closure
4913 * @param message message
4914 * @param peer peer identity this notification is about
4915 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4918 handle_dht_p2p_verify_successor_result(void *cls,
4919 const struct GNUNET_PeerIdentity *peer,
4920 const struct GNUNET_MessageHeader *message)
4922 const struct PeerVerifySuccessorResultMessage *vsrm;
4923 enum GDS_ROUTING_trail_direction trail_direction;
4924 struct GNUNET_PeerIdentity querying_peer;
4925 struct GNUNET_HashCode trail_id;
4926 struct GNUNET_PeerIdentity *next_hop;
4927 struct FriendInfo *target_friend;
4928 struct GNUNET_PeerIdentity probable_successor;
4929 struct GNUNET_PeerIdentity current_successor;
4930 const struct GNUNET_PeerIdentity *trail;
4931 unsigned int trail_length;
4934 msize = ntohs (message->size);
4935 /* We send a trail to reach from old successor to new successor, if
4936 * old_successor != new_successor.*/
4937 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4939 GNUNET_break_op (0);
4943 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4944 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4945 sizeof (struct GNUNET_PeerIdentity);
4947 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4948 sizeof (struct GNUNET_PeerIdentity) != 0)
4950 GNUNET_break_op (0);
4954 GNUNET_STATISTICS_update (GDS_stats,
4956 ("# Bytes received from other peers"), msize,
4959 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4960 querying_peer = vsrm->querying_peer;
4961 trail_direction = ntohl (vsrm->trail_direction);
4962 trail_id = vsrm->trail_id;
4963 probable_successor = vsrm->probable_successor;
4964 current_successor = vsrm->current_successor;
4966 verify_successor_next_send_time =
4967 GNUNET_TIME_STD_BACKOFF(verify_successor_next_send_time);
4968 /* I am the querying_peer. */
4969 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4971 compare_and_update_successor (current_successor,
4972 probable_successor, trail, trail_length);
4976 /*If you are not the querying peer then pass on the message */
4977 if(NULL == (next_hop =
4978 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
4980 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
4981 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
4985 if (NULL == (target_friend =
4986 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
4991 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4992 vsrm->current_successor,
4993 probable_successor, trail_id,
4996 trail_direction, target_friend);
5002 * Core handle for p2p notify new successor messages.
5003 * @param cls closure
5004 * @param message message
5005 * @param peer peer identity this notification is about
5006 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5009 handle_dht_p2p_notify_new_successor(void *cls,
5010 const struct GNUNET_PeerIdentity *peer,
5011 const struct GNUNET_MessageHeader *message)
5013 const struct PeerNotifyNewSuccessorMessage *nsm;
5014 struct GNUNET_PeerIdentity *trail;
5015 struct GNUNET_PeerIdentity source;
5016 struct GNUNET_PeerIdentity new_successor;
5017 struct GNUNET_HashCode trail_id;
5018 struct GNUNET_PeerIdentity next_hop;
5019 struct FriendInfo *target_friend;
5022 uint32_t trail_length;
5024 msize = ntohs (message->size);
5026 /* We have the trail to reach from source to new successor. */
5027 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5029 GNUNET_break_op (0);
5033 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5034 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5035 sizeof (struct GNUNET_PeerIdentity);
5036 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5037 sizeof (struct GNUNET_PeerIdentity) != 0)
5039 GNUNET_break_op (0);
5043 GNUNET_STATISTICS_update (GDS_stats,
5045 ("# Bytes received from other peers"), msize,
5048 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5049 source = nsm->source_peer;
5050 new_successor = nsm->new_successor;
5051 trail_id = nsm->trail_id;
5053 /* I am the new_successor to source_peer. */
5054 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5056 if(trail_length > 0)
5057 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5060 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5062 compare_and_update_predecessor (source, trail, trail_length);
5066 GNUNET_assert(trail_length > 0);
5067 /* I am part of trail to reach to successor. */
5068 my_index = search_my_index (trail, trail_length);
5071 DEBUG ("No entry found in trail\n");
5072 GNUNET_break_op (0);
5073 return GNUNET_SYSERR;
5075 if((trail_length + 1) == my_index)
5077 DEBUG ("Found twice in trail.\n");
5078 GNUNET_break_op (0);
5079 return GNUNET_SYSERR;
5081 if ((trail_length-1) == my_index)
5082 next_hop = new_successor;
5084 next_hop = trail[my_index + 1];
5085 /* Add an entry in routing table for trail from source to its new successor. */
5086 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5087 GNUNET_assert (NULL !=
5089 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5090 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5092 trail_id, target_friend);
5099 * Core handler for P2P trail rejection message
5100 * @param cls closure
5101 * @param message message
5102 * @param peer peer identity this notification is about
5103 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5106 handle_dht_p2p_trail_setup_rejection (void *cls,
5107 const struct GNUNET_PeerIdentity *peer,
5108 const struct GNUNET_MessageHeader *message)
5110 const struct PeerTrailRejectionMessage *trail_rejection;
5111 unsigned int trail_length;
5112 const struct GNUNET_PeerIdentity *trail_peer_list;
5113 struct FriendInfo *target_friend;
5114 struct GNUNET_TIME_Relative congestion_timeout;
5115 struct GNUNET_HashCode trail_id;
5116 struct GNUNET_PeerIdentity next_peer;
5117 struct GNUNET_PeerIdentity source;
5118 uint64_t ultimate_destination_finger_value;
5119 unsigned int is_predecessor;
5122 msize = ntohs (message->size);
5123 if (msize < sizeof (struct PeerTrailRejectionMessage))
5125 GNUNET_break_op (0);
5128 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5129 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5130 sizeof (struct GNUNET_PeerIdentity) != 0)
5132 GNUNET_break_op (0);
5135 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5136 sizeof (struct GNUNET_PeerIdentity);
5137 GNUNET_STATISTICS_update (GDS_stats,
5139 ("# Bytes received from other peers"), msize,
5142 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5143 is_predecessor = ntohl (trail_rejection->is_predecessor);
5144 congestion_timeout = trail_rejection->congestion_time;
5145 source = trail_rejection->source_peer;
5146 trail_id = trail_rejection->trail_id;
5147 ultimate_destination_finger_value =
5148 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5149 /* First set the congestion time of the friend that sent you this message. */
5150 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5151 if (NULL == target_friend)
5153 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5157 target_friend->congestion_timestamp =
5158 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5159 congestion_timeout);
5161 /* I am the source peer which wants to setup the trail. Do nothing.
5162 * send_find_finger_trail_task is scheduled periodically.*/
5163 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5166 /* If I am congested then pass this message to peer before me in trail. */
5167 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5169 /* First remove yourself from the trail. */
5170 unsigned int new_trail_length = trail_length - 1;
5171 struct GNUNET_PeerIdentity trail[new_trail_length];
5173 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5174 if (0 == trail_length)
5177 next_peer = trail[new_trail_length-1];
5180 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5181 if (NULL == target_friend)
5183 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5187 GDS_NEIGHBOURS_send_trail_rejection (source,
5188 ultimate_destination_finger_value,
5189 my_identity, is_predecessor,
5190 trail, new_trail_length, trail_id,
5191 target_friend, CONGESTION_TIMEOUT);
5195 struct Closest_Peer successor;
5196 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5198 /* Am I the final destination? */
5199 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5202 /*Here you are already part of trail. Copy the trail removing yourself. */
5203 unsigned int new_trail_length = trail_length - 1;
5204 struct GNUNET_PeerIdentity trail[new_trail_length];
5206 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5208 if (0 == new_trail_length)
5212 next_peer = trail[new_trail_length-1];
5215 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5217 if (NULL == target_friend)
5219 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5223 GDS_NEIGHBOURS_send_trail_setup_result (source,
5225 target_friend, new_trail_length,
5228 ultimate_destination_finger_value,
5233 /* Here I was already part of trail. So no need to add. */
5235 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5236 &successor.next_hop);
5237 if (NULL == target_friend)
5239 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5244 GDS_NEIGHBOURS_send_trail_setup (source,
5245 ultimate_destination_finger_value,
5246 successor.best_known_destination,
5247 target_friend, trail_length, trail_peer_list,
5248 is_predecessor, trail_id,
5249 successor.trail_id);
5256 * Core handler for trail teardown message.
5257 * @param cls closure
5258 * @param message message
5259 * @param peer sender of this messsage.
5260 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5263 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5264 const struct GNUNET_MessageHeader *message)
5266 const struct PeerTrailTearDownMessage *trail_teardown;
5267 enum GDS_ROUTING_trail_direction trail_direction;
5268 struct GNUNET_HashCode trail_id;
5269 struct GNUNET_PeerIdentity *next_hop;
5272 msize = ntohs (message->size);
5274 /* Here we pass only the trail id. */
5275 if (msize != sizeof (struct PeerTrailTearDownMessage))
5277 GNUNET_break_op (0);
5281 GNUNET_STATISTICS_update (GDS_stats,
5283 ("# Bytes received from other peers"), msize,
5286 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5287 trail_direction = ntohl (trail_teardown->trail_direction);
5288 trail_id = trail_teardown->trail_id;
5290 /* Check if peer is the real peer from which we should get this message.*/
5291 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5293 GNUNET_assert (NULL != (prev_hop =
5294 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5295 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5298 return GNUNET_SYSERR;
5302 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5303 if (NULL == next_hop)
5305 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5306 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5308 return GNUNET_SYSERR;
5311 /* I am the next hop, which means I am the final destination. */
5312 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5314 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5319 /* If not final destination, then send a trail teardown message to next hop.*/
5320 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5321 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5322 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5330 * Core handle for p2p add trail message.
5331 * @param cls closure
5332 * @param message message
5333 * @param peer peer identity this notification is about
5334 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5337 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5338 const struct GNUNET_MessageHeader *message)
5340 const struct PeerAddTrailMessage *add_trail;
5341 const struct GNUNET_PeerIdentity *trail;
5342 struct GNUNET_HashCode trail_id;
5343 struct GNUNET_PeerIdentity destination_peer;
5344 struct GNUNET_PeerIdentity source_peer;
5345 struct GNUNET_PeerIdentity next_hop;
5346 unsigned int trail_length;
5347 unsigned int my_index;
5350 msize = ntohs (message->size);
5351 /* In this message we pass the whole trail from source to destination as we
5352 * are adding that trail.*/
5353 //FIXME: failed when run with 1000 pears. check why.
5354 if (msize < sizeof (struct PeerAddTrailMessage))
5356 GNUNET_break_op (0);
5360 add_trail = (const struct PeerAddTrailMessage *) message;
5361 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5362 sizeof (struct GNUNET_PeerIdentity);
5363 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5364 sizeof (struct GNUNET_PeerIdentity) != 0)
5366 GNUNET_break_op (0);
5370 GNUNET_STATISTICS_update (GDS_stats,
5372 ("# Bytes received from other peers"), msize,
5375 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5376 destination_peer = add_trail->destination_peer;
5377 source_peer = add_trail->source_peer;
5378 trail_id = add_trail->trail_id;
5380 //FIXME: add a check that sender peer is not malicious. Make it a generic
5381 // function so that it can be used in all other functions where we need the
5382 // same functionality.
5384 /* I am not the destination of the trail. */
5385 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5387 struct FriendInfo *target_friend;
5389 /* Get my location in the trail. */
5390 my_index = search_my_index (trail, trail_length);
5393 GNUNET_break_op (0);
5394 return GNUNET_SYSERR;
5396 if((trail_length + 1) == my_index)
5398 DEBUG ("Found twice in trail.\n");
5399 GNUNET_break_op (0);
5400 return GNUNET_SYSERR;
5402 if ((trail_length - 1) == my_index)
5404 next_hop = destination_peer;
5408 next_hop = trail[my_index + 1];
5410 /* Add in your routing table. */
5411 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5412 GNUNET_assert (NULL !=
5414 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5415 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5416 trail, trail_length, target_friend);
5419 /* I am the destination. Add an entry in routing table. */
5420 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5426 * Free the finger trail in which the first friend to reach to a finger is
5427 * disconnected_friend. Also remove entry from routing table for that particular
5429 * @param disconnected_friend PeerIdentity of friend which got disconnected
5430 * @param remove_finger Finger whose trail we need to check if it has
5431 * disconnected_friend as the first hop.
5432 * @return Total number of trails in which disconnected_friend was the first
5436 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5437 struct FingerInfo *finger)
5439 unsigned int matching_trails_count = 0;
5442 /* Iterate over all the trails of finger. */
5443 for (i = 0; i < finger->trails_count; i++)
5445 struct Trail *current_trail;
5446 current_trail = &finger->trail_list[i];
5447 //FIXME: This assertion fails if we have gap in trail list from o to trails count.
5448 GNUNET_assert (GNUNET_YES == current_trail->is_present);
5449 /* First friend to reach to finger is disconnected_peer. */
5450 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5451 disconnected_friend))
5453 struct GNUNET_PeerIdentity *next_hop;
5454 struct FriendInfo *remove_friend;
5456 GNUNET_assert (NULL !=
5458 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5459 disconnected_friend)));
5460 next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id,
5461 GDS_ROUTING_SRC_TO_DEST);
5463 /* Here it may happen that as all the peers got disconnected, the entry in
5464 routing table for that particular trail has been removed, because the
5465 previously disconnected peer was either a next hop or prev hop of that
5467 if (NULL != next_hop)
5469 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5471 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id));
5473 matching_trails_count++;
5474 free_trail (current_trail);
5475 current_trail->is_present = GNUNET_NO;
5478 return matching_trails_count;
5483 * Iterate over finger_table entries.
5484 * 0. Ignore finger which is my_identity or if no valid entry present at
5485 * that finger index.
5486 * 1. If disconnected_friend is a finger, then remove the routing entry from
5487 your own table. Free the trail.
5488 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5489 * 2.1 Remove all the trails and entry from routing table in which disconnected
5490 * friend is the first friend in the trail. If disconnected_friend is the
5491 * first friend in all the trails to reach finger, then remove the finger.
5492 * @param disconnected_friend Peer identity of friend which got disconnected.
5495 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5497 struct FingerInfo *current_finger;
5498 struct FriendInfo *remove_friend;
5499 int removed_trails_count;
5502 /* Iterate over finger table entries. */
5503 for (i = 0; i < MAX_FINGERS; i++)
5505 current_finger = &finger_table[i];
5507 /* No finger stored at this trail index. */
5508 if ((GNUNET_NO == current_finger->is_present) ||
5509 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5513 /* Is disconnected_peer a finger? */
5514 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5515 ¤t_finger->finger_identity))
5517 struct GNUNET_PeerIdentity *next_hop;
5518 struct GNUNET_HashCode trail_id;
5520 GNUNET_assert (0 == current_finger->trail_list[0].trail_length);
5521 GNUNET_assert (GNUNET_YES == (current_finger->trail_list[0].is_present));
5522 trail_id = current_finger->trail_list[0].trail_id;
5526 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5528 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5529 GNUNET_assert (NULL !=
5531 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5532 disconnected_peer)));
5534 current_finger->trail_list[0].is_present = GNUNET_NO;
5535 current_finger->is_present = GNUNET_NO;
5536 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5540 /* If finger is a friend but not disconnected_friend, then continue. */
5541 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5542 ¤t_finger->finger_identity))
5545 /* Iterate over the list of trails to reach remove_finger. Check if
5546 * disconnected_friend is the first friend in any of the trail. */
5547 removed_trails_count = remove_matching_trails (disconnected_peer,
5549 current_finger->trails_count =
5550 current_finger->trails_count - removed_trails_count;
5551 if (0 == current_finger->trails_count)
5553 current_finger->is_present = GNUNET_NO;
5554 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5561 * Method called whenever a peer disconnects.
5563 * @param cls closure
5564 * @param peer peer identity this notification is about
5567 handle_core_disconnect (void *cls,
5568 const struct GNUNET_PeerIdentity *peer)
5570 struct FriendInfo *remove_friend;
5571 struct P2PPendingMessage *pos;
5572 unsigned int discarded;
5574 /* If disconnected to own identity, then return. */
5575 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5578 if(NULL == (remove_friend =
5579 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
5581 DEBUG("\n friend already disconnected.");
5585 remove_matching_fingers (peer);
5586 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5587 GNUNET_assert (GNUNET_YES ==
5588 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5592 /* Remove all the messages queued in pending list of this peer is discarded.*/
5593 if (remove_friend->th != NULL)
5595 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
5596 remove_friend->th = NULL;
5600 while (NULL != (pos = remove_friend->head))
5602 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
5607 GNUNET_STATISTICS_update (GDS_stats,
5609 ("# Queued messages discarded (peer disconnected)"),
5610 discarded, GNUNET_NO);
5611 //GNUNET_free (remove_friend);
5613 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5616 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5618 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5619 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5627 * Method called whenever a peer connects.
5629 * @param cls closure
5630 * @param peer_identity peer identity this notification is about
5633 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5635 struct FriendInfo *friend;
5637 /* Check for connect to self message */
5638 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5641 /* If peer already exists in our friend_peermap, then exit. */
5642 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5649 friend = GNUNET_new (struct FriendInfo);
5650 friend->id = *peer_identity;
5651 GNUNET_assert (GNUNET_OK ==
5652 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5653 peer_identity, friend,
5654 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5656 /* SUPUS: We should add a congestion timestamp on the friend, so that it is
5657 selected after some time out. This is to ensure that both peers have added
5658 each other as their friend. */
5659 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5660 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5662 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5668 * To be called on core init/fail.
5670 * @param cls service closure
5671 * @param identity the public identity of this peer
5674 core_init (void *cls,
5675 const struct GNUNET_PeerIdentity *identity)
5677 my_identity = *identity;
5682 * Initialize finger table entries.
5685 finger_table_init ()
5687 memset (&finger_table, 0, sizeof (finger_table));
5692 * Initialize neighbours subsystem.
5693 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5696 GDS_NEIGHBOURS_init (void)
5698 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5699 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5700 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5701 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5702 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5703 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5704 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5705 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5706 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5707 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5708 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5709 sizeof (struct PeerTrailTearDownMessage)},
5710 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5714 #if ENABLE_MALICIOUS
5719 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5720 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5721 GNUNET_NO, core_handlers);
5723 if (NULL == core_api)
5724 return GNUNET_SYSERR;
5726 //TODO: check size of this peer map?
5727 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5728 finger_table_init ();
5730 find_finger_trail_task_next_send_time.rel_value_us =
5731 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5732 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5733 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5735 verify_successor_next_send_time.rel_value_us =
5736 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5737 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5738 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5744 * Free the memory held up by trails of a finger.
5747 delete_finger_table_entries()
5752 for(i = 0; i < MAX_FINGERS; i++)
5754 if(GNUNET_NO == finger_table[i].is_present)
5757 /* FREE ALL THE TRAILS. */
5758 /* SUPUS: Here in free trail, it will delete the entry
5759 if there is a trail with trail length != 0.OKAY */
5760 for(j = 0; j < finger_table[i].trails_count; j++)
5762 free_trail(&finger_table[i].trail_list[i]);
5769 * Shutdown neighbours subsystem.
5772 GDS_NEIGHBOURS_done (void)
5774 if (NULL == core_api)
5777 GNUNET_CORE_disconnect (core_api);
5780 delete_finger_table_entries();
5782 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5783 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5784 friend_peermap = NULL;
5786 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5789 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5790 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5793 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5795 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5796 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5804 * @return my identity
5806 struct GNUNET_PeerIdentity
5807 GDS_NEIGHBOURS_get_my_id (void)
5812 /* end of gnunet-service-xdht_neighbours.c */