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, 50)
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, 5)
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 GNUNET_assert (NULL !=
1833 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1834 ¤t_finger_trail->trail_head->peer)));
1836 /* First friend to reach trail is not free. */
1837 if (GNUNET_YES == is_friend_congested (friend))
1840 if (NULL == best_trail ||
1841 best_trail->trail_length > current_finger_trail->trail_length)
1843 best_trail = current_finger_trail;
1852 * Compare FINGER entry with current successor. If finger's first friend of all
1853 * its trail is not congested and has not crossed trail threshold, then check
1854 * if finger peer identity is closer to final_destination_finger_value than
1855 * current_successor. If yes then update current_successor.
1856 * @param current_successor[in/out]
1860 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
1862 struct FingerInfo *finger;
1863 struct GNUNET_PeerIdentity closest_peer;
1864 struct Trail *finger_trail;
1867 /* Iterate over finger table. */
1868 for (i = 0; i < MAX_FINGERS; i++)
1870 finger = &finger_table[i];
1872 if (GNUNET_NO == finger->is_present)
1875 /* FIXME write correct comment here */
1876 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1877 ¤t_closest_peer->best_known_destination))
1880 /* If I am my own finger, then ignore this finger. */
1881 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1884 /* FIXME: I think a peer should not select itself as its own identity ever.
1885 But it does select. Find out why??*/
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 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1894 &finger->finger_identity)))
1899 closest_peer = select_closest_peer (&finger->finger_identity,
1900 ¤t_closest_peer->best_known_destination,
1901 current_closest_peer->destination_finger_value,
1902 current_closest_peer->is_predecessor);
1904 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer))
1906 /* Choose one of the trail to reach to finger. */
1907 finger_trail = select_finger_trail (finger);
1909 /* In case no trail found, ignore this finger. */
1910 if (NULL == finger_trail)
1913 current_closest_peer->best_known_destination = closest_peer;
1914 current_closest_peer->next_hop = finger_trail->trail_head->peer;
1915 current_closest_peer->trail_id = finger_trail->trail_id;
1916 current_closest_peer->finger_table_index = i;
1924 * Compare friend entry with current successor.
1925 * If friend identity and current_successor is same, then do nothing.
1926 * If friend is not congested and has not crossed trail threshold, then check
1927 * if friend peer identity is closer to final_destination_finger_value than
1928 * current_successor. If yes then update current_successor.
1929 * @param cls closure
1930 * @param key current public key
1931 * @param value struct Closest_Peer
1932 * @return #GNUNET_YES if we should continue to iterate,
1933 * #GNUNET_NO if not.
1936 compare_friend_and_current_closest_peer (void *cls,
1937 const struct GNUNET_PeerIdentity *key,
1940 struct FriendInfo *friend = value;
1941 struct Closest_Peer *current_closest_peer = cls;
1942 struct GNUNET_PeerIdentity closest_peer;
1944 /* Friend is either congested or has crossed threshold. */
1945 if (GNUNET_YES == is_friend_congested (friend))
1948 /* If current_closest_peer and friend identity are same, then do nothing.*/
1949 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
1950 ¤t_closest_peer->best_known_destination))
1956 closest_peer = select_closest_peer (&friend->id,
1957 ¤t_closest_peer->best_known_destination,
1958 current_closest_peer->destination_finger_value,
1959 current_closest_peer->is_predecessor);
1961 /* Is friend the closest successor? */
1962 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer))
1964 current_closest_peer->best_known_destination = friend->id;
1965 current_closest_peer->next_hop = friend->id;
1973 * Initialize current_successor to my_identity.
1974 * @param my_identity My peer identity
1975 * @return Updated closest_peer
1977 static struct Closest_Peer
1978 init_current_successor (struct GNUNET_PeerIdentity my_identity,
1979 uint64_t destination_finger_value,
1980 unsigned int is_predecessor)
1982 struct Closest_Peer current_closest_peer;
1984 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
1985 current_closest_peer.destination_finger_value = destination_finger_value;
1986 current_closest_peer.is_predecessor = is_predecessor;
1987 current_closest_peer.next_hop = my_identity;
1988 current_closest_peer.best_known_destination = my_identity;
1989 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
1990 return current_closest_peer;
1995 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
1996 * peer. It could be because of the logic we wrote here. Verify if its correct.
1997 * If not then return immediate_successor.
1999 * Find the successor for destination_finger_value among my_identity, my
2000 * friends and my fingers. Don't consider friends or fingers which are either
2001 * congested or have crossed the threshold.
2002 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2004 * @param destination_finger_value Peer closest to this value will be the next successor.
2005 * @param is_predecessor Are we looking for predecessor or finger?
2006 * @return Successor It is never NULL, in case none of friend or finger is closest,
2007 * then we return my_identity.
2009 static struct Closest_Peer
2010 find_successor (uint64_t destination_finger_value,
2011 unsigned int is_predecessor)
2013 struct Closest_Peer current_closest_peer;
2015 /* Initialize current_successor to my_identity. */
2016 current_closest_peer = init_current_successor (my_identity,
2017 destination_finger_value,
2020 /* Compare each friend entry with current_successor and update current_successor
2021 * with friend if its closest. */
2024 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2025 &compare_friend_and_current_closest_peer,
2026 ¤t_closest_peer));
2028 /* Compare each finger entry with current_successor and update current_successor
2029 * with finger if its closest. */
2030 compare_finger_and_current_closest_peer (¤t_closest_peer);
2031 return current_closest_peer;
2035 * FIXME; Send put message across all the trail to reach to next hop to handle
2037 * Construct a Put message and send it to target_peer.
2038 * @param key Key for the content
2039 * @param block_type Type of the block
2040 * @param options Routing options
2041 * @param desired_replication_level Desired replication count
2042 * @param best_known_dest Peer to which this message should reach eventually,
2043 * as it is best known destination to me.
2044 * @param intermediate_trail_id Trail id in case
2045 * @param target_peer Peer to which this message will be forwarded.
2046 * @param hop_count Number of hops traversed so far.
2047 * @param put_path_length Total number of peers in @a put_path
2048 * @param put_path Number of peers traversed so far
2049 * @param expiration_time When does the content expire
2050 * @param data Content to store
2051 * @param data_size Size of content @a data in bytes
2054 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2055 enum GNUNET_BLOCK_Type block_type,
2056 enum GNUNET_DHT_RouteOption options,
2057 uint32_t desired_replication_level,
2058 struct GNUNET_PeerIdentity best_known_dest,
2059 struct GNUNET_HashCode intermediate_trail_id,
2060 struct GNUNET_PeerIdentity *target_peer,
2062 uint32_t put_path_length,
2063 struct GNUNET_PeerIdentity *put_path,
2064 struct GNUNET_TIME_Absolute expiration_time,
2065 const void *data, size_t data_size)
2067 struct PeerPutMessage *ppm;
2068 struct P2PPendingMessage *pending;
2069 struct FriendInfo *target_friend;
2070 struct GNUNET_PeerIdentity *pp;
2073 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2074 sizeof (struct PeerPutMessage);
2075 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2077 put_path_length = 0;
2078 msize = data_size + sizeof (struct PeerPutMessage);
2081 /* Should it be GNUNET_SERVER_MAX_MESSAGE_SIZE? */
2082 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2084 DEBUG("msize = %lu\n",msize);
2089 GNUNET_assert (NULL !=
2091 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2092 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2093 pending->timeout = expiration_time;
2094 ppm = (struct PeerPutMessage *) &pending[1];
2095 pending->msg = &ppm->header;
2096 ppm->header.size = htons (msize);
2097 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2098 ppm->options = htonl (options);
2099 ppm->block_type = htonl (block_type);
2100 ppm->hop_count = htonl (hop_count + 1);
2101 ppm->desired_replication_level = htonl (desired_replication_level);
2102 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2103 ppm->best_known_destination = best_known_dest;
2104 ppm->intermediate_trail_id = intermediate_trail_id;
2106 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2107 ppm->put_path_length = htonl (put_path_length);
2108 if(put_path_length > 0)
2110 memcpy (pp, put_path,
2111 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2113 memcpy (&pp[put_path_length], data, data_size);
2114 GNUNET_assert (NULL != target_friend);
2115 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2116 target_friend->pending_count++;
2117 process_friend_queue (target_friend);
2122 * Handle the put request from the client.
2123 * @param key Key for the content
2124 * @param block_type Type of the block
2125 * @param options Routing options
2126 * @param desired_replication_level Desired replication count
2127 * @param expiration_time When does the content expire
2128 * @param data Content to store
2129 * @param data_size Size of content @a data in bytes
2132 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
2133 enum GNUNET_BLOCK_Type block_type,
2134 enum GNUNET_DHT_RouteOption options,
2135 uint32_t desired_replication_level,
2136 struct GNUNET_TIME_Absolute expiration_time,
2137 const void *data, size_t data_size)
2139 struct GNUNET_PeerIdentity best_known_dest;
2140 struct GNUNET_HashCode intermediate_trail_id;
2141 struct GNUNET_PeerIdentity next_hop;
2143 struct Closest_Peer successor;
2145 memcpy (&key_value, key, sizeof (uint64_t));
2146 key_value = GNUNET_ntohll (key_value);
2147 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2148 best_known_dest = successor.best_known_destination;
2149 next_hop = successor.next_hop;
2150 intermediate_trail_id = successor.trail_id;
2152 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2154 /* I am the destination. */
2155 DEBUG("PUT destination is me = %s,key =%s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2156 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2157 block_type,data_size,data);
2158 GDS_CLIENTS_process_put (options, block_type, 0,
2159 ntohl (desired_replication_level),
2160 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time.
2161 key, data, data_size);
2165 /* In case we are sending the request to a finger, then send across all of its
2168 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2169 &successor.next_hop))
2171 struct FingerInfo *next_hop_finger;
2174 next_hop_finger = &finger_table[successor.finger_table_index];
2175 for (i = 0; i < next_hop_finger->trails_count; i++)
2177 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2179 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2181 next_hop_finger->trail_list[i].trail_id,
2182 &next_hop, hop_count, put_path_length, put_path,
2190 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2191 best_known_dest, intermediate_trail_id, &next_hop,
2192 0, 1, &my_identity, expiration_time,
2197 * FIXME; Send get message across all the trail to reach to next hop to handle
2199 * Construct a Get message and send it to target_peer.
2200 * @param key Key for the content
2201 * @param block_type Type of the block
2202 * @param options Routing options
2203 * @param desired_replication_level Desired replication count
2204 * @param best_known_dest Peer which should get this message. Same as target peer
2205 * if best_known_dest is a friend else its a finger.
2206 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2207 * in case it is a finger else set to 0.
2208 * @param target_peer Peer to which this message will be forwarded.
2209 * @param hop_count Number of hops traversed so far.
2210 * @param data Content to store
2211 * @param data_size Size of content @a data in bytes
2212 * @param get_path_length Total number of peers in @a get_path
2213 * @param get_path Number of peers traversed so far
2216 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2217 enum GNUNET_BLOCK_Type block_type,
2218 enum GNUNET_DHT_RouteOption options,
2219 uint32_t desired_replication_level,
2220 struct GNUNET_PeerIdentity best_known_dest,
2221 struct GNUNET_HashCode intermediate_trail_id,
2222 struct GNUNET_PeerIdentity *target_peer,
2224 uint32_t get_path_length,
2225 struct GNUNET_PeerIdentity *get_path)
2227 struct PeerGetMessage *pgm;
2228 struct P2PPendingMessage *pending;
2229 struct FriendInfo *target_friend;
2230 struct GNUNET_PeerIdentity *gp;
2233 msize = sizeof (struct PeerGetMessage) +
2234 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2236 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2241 GNUNET_assert (NULL !=
2243 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2245 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2246 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2247 pending->importance = 0; /* FIXME */
2248 pgm = (struct PeerGetMessage *) &pending[1];
2249 pending->msg = &pgm->header;
2250 pgm->header.size = htons (msize);
2251 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2252 pgm->get_path_length = htonl (get_path_length);
2253 pgm->best_known_destination = best_known_dest;
2255 pgm->intermediate_trail_id = intermediate_trail_id;
2256 pgm->hop_count = htonl (hop_count + 1);
2257 pgm->get_path_length = htonl (get_path_length);
2258 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2259 memcpy (gp, get_path,
2260 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2261 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2262 target_friend->pending_count++;
2263 process_friend_queue (target_friend);
2268 * Handle the get request from the client file. If I am destination do
2269 * datacache put and return. Else find the target friend and forward message
2271 * @param key Key for the content
2272 * @param block_type Type of the block
2273 * @param options Routing options
2274 * @param desired_replication_level Desired replication count
2277 GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key,
2278 enum GNUNET_BLOCK_Type block_type,
2279 enum GNUNET_DHT_RouteOption options,
2280 uint32_t desired_replication_level)
2282 struct Closest_Peer successor;
2283 struct GNUNET_PeerIdentity best_known_dest;
2284 struct GNUNET_HashCode intermediate_trail_id;
2287 memcpy (&key_value, key, sizeof (uint64_t));
2288 key_value = GNUNET_ntohll (key_value);
2290 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2292 best_known_dest = successor.best_known_destination;
2293 intermediate_trail_id = successor.trail_id;
2295 /* I am the destination. I have the data. */
2296 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2299 DEBUG("GET destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(key));
2300 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2301 NULL, 0, 1, &my_identity, NULL,&my_identity);
2305 /* fixme; for multiple trails, we need to send back finger index and send trail
2306 across all the fingers. but in current implementation we don't have this case.
2307 compare finger and current_successor returns, */
2308 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2309 best_known_dest,intermediate_trail_id, &successor.next_hop,
2310 0, 1, &my_identity);
2315 * Send the get result to requesting client.
2316 * @param key Key of the requested data.
2317 * @param type Block type
2318 * @param target_peer Next peer to forward the message to.
2319 * @param source_peer Peer which has the data for the key.
2320 * @param put_path_length Number of peers in @a put_path
2321 * @param put_path Path taken to put the data at its stored location.
2322 * @param get_path_length Number of peers in @a get_path
2323 * @param get_path Path taken to reach to the location of the key.
2324 * @param expiration When will this result expire?
2325 * @param data Payload to store
2326 * @param data_size Size of the @a data
2329 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2330 enum GNUNET_BLOCK_Type type,
2331 const struct GNUNET_PeerIdentity *target_peer,
2332 const struct GNUNET_PeerIdentity *source_peer,
2333 unsigned int put_path_length,
2334 const struct GNUNET_PeerIdentity *put_path,
2335 unsigned int get_path_length,
2336 const struct GNUNET_PeerIdentity *get_path,
2337 struct GNUNET_TIME_Absolute expiration,
2338 const void *data, size_t data_size)
2340 struct PeerGetResultMessage *get_result;
2341 struct GNUNET_PeerIdentity *paths;
2342 struct P2PPendingMessage *pending;
2343 struct FriendInfo *target_friend;
2344 int current_path_index;
2347 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2349 sizeof (struct PeerGetResultMessage);
2351 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2353 put_path_length = 0;
2354 msize = msize - put_path_length;
2358 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2363 DEBUG("GET RESULT FOR DATA_SIZE = %lu\n",msize);
2364 current_path_index = 0;
2365 if(get_path_length > 0)
2367 current_path_index = search_my_index(get_path, get_path_length);
2368 if (-1 == current_path_index)
2373 if ((get_path_length + 1) == current_path_index)
2375 DEBUG ("Peer found twice in get path. Not allowed \n");
2380 if (0 == current_path_index)
2382 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2383 get_path, put_path_length,
2384 put_path, type, data_size, data);
2388 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2389 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2390 pending->importance = 0;
2391 get_result = (struct PeerGetResultMessage *)&pending[1];
2392 pending->msg = &get_result->header;
2393 get_result->header.size = htons (msize);
2394 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2395 get_result->key = *key;
2396 get_result->querying_peer = *source_peer;
2397 get_result->expiration_time = expiration;
2398 get_result->get_path_length = htonl (get_path_length);
2399 get_result->put_path_length = htonl (put_path_length);
2400 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2401 memcpy (paths, put_path,
2402 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2403 memcpy (&paths[put_path_length], get_path,
2404 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2405 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2407 GNUNET_assert (NULL !=
2409 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2410 &get_path[current_path_index - 1])));
2411 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2412 target_friend->pending_count++;
2413 process_friend_queue (target_friend);
2418 * Randomly choose one of your friends (which is not congested and have not crossed
2419 * trail threshold) from the friend_peermap
2420 * @return Friend Randomly chosen friend.
2421 * NULL in case friend peermap is empty, or all the friends are either
2422 * congested or have crossed trail threshold.
2424 static struct FriendInfo *
2425 select_random_friend ()
2427 unsigned int current_size;
2430 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2431 struct GNUNET_PeerIdentity key_ret;
2432 struct FriendInfo *friend;
2434 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2437 if (0 == current_size)
2440 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2441 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2443 /* Iterate till you don't reach to index. */
2444 for (j = 0; j < index ; j++)
2445 GNUNET_assert (GNUNET_YES ==
2446 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2450 /* Reset the index in friend peermap to 0 as we reached to the end. */
2451 if (j == current_size)
2454 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2455 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2459 /* Get the friend stored at the index, j*/
2460 GNUNET_assert (GNUNET_YES ==
2461 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2463 (const void **)&friend));
2465 /* This friend is not congested and has not crossed trail threshold. */
2466 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2467 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2473 } while (j != index);
2475 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2481 * Compute 64 bit value of finger_identity corresponding to a finger index using
2483 * For all fingers, n.finger[i] = n + pow (2,i),
2484 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2485 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2486 * @param finger_index Index corresponding to which we calculate 64 bit value.
2487 * @return 64 bit value.
2490 compute_finger_identity_value (unsigned int finger_index)
2494 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2495 my_id64 = GNUNET_ntohll (my_id64);
2497 /* Are we looking for immediate predecessor? */
2498 if (PREDECESSOR_FINGER_ID == finger_index)
2499 return (my_id64 - 1);
2502 uint64_t add = (uint64_t)1 << finger_index;
2503 return (my_id64 + add);
2509 * Choose a random friend. Calculate the next finger identity to search,from
2510 * current_search_finger_index. Start looking for the trail to reach to
2511 * finger identity through this random friend.
2513 * @param cls closure for this task
2514 * @param tc the context under which the task is running
2517 send_find_finger_trail_message (void *cls,
2518 const struct GNUNET_SCHEDULER_TaskContext *tc)
2520 struct FriendInfo *target_friend;
2521 struct GNUNET_HashCode trail_id;
2522 struct GNUNET_HashCode intermediate_trail_id;
2523 unsigned int is_predecessor;
2524 uint64_t finger_id_value;
2526 /* Schedule another send_find_finger_trail_message task. */
2527 find_finger_trail_task_next_send_time.rel_value_us =
2528 find_finger_trail_task_next_send_time.rel_value_us +
2529 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2530 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2531 find_finger_trail_task =
2532 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2533 &send_find_finger_trail_message,
2536 /* No space in my routing table. (Source and destination peers also store entries
2537 * in their routing table). */
2538 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2541 target_friend = select_random_friend ();
2542 if (NULL == target_friend)
2547 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2549 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2554 /* Generate a unique trail id for trail we are trying to setup. */
2555 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2556 &trail_id, sizeof (trail_id));
2557 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2558 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2559 target_friend->id, target_friend, 0, NULL,
2560 is_predecessor, trail_id,
2561 intermediate_trail_id);
2566 * In case there are already maximum number of possible trails to reach to a
2567 * finger, then check if the new trail's length is lesser than any of the
2569 * If yes then replace that old trail by new trail.
2571 * Note: Here we are taking length as a parameter to choose the best possible
2572 * trail, but there could be other parameters also like:
2573 * 1. duration of existence of a trail - older the better.
2574 * 2. if the new trail is completely disjoint than the
2575 * other trails, then may be choosing it is better.
2577 * @param finger Finger
2578 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2579 * including the endpoints.
2580 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2581 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2584 select_and_replace_trail (struct FingerInfo *finger,
2585 const struct GNUNET_PeerIdentity *new_trail,
2586 unsigned int new_trail_length,
2587 struct GNUNET_HashCode new_trail_id)
2589 struct Trail *trail;
2590 unsigned int largest_trail_length;
2591 unsigned int largest_trail_index;
2592 struct Trail_Element *trail_element;
2595 largest_trail_length = new_trail_length;
2596 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2598 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2600 for (i = 0; i < finger->trails_count; i++)
2602 trail = &finger->trail_list[i];
2603 if (trail->trail_length > largest_trail_length)
2605 largest_trail_length = trail->trail_length;
2606 largest_trail_index = i;
2610 /* New trail is not better than existing ones. Send trail teardown. */
2611 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2613 struct GNUNET_PeerIdentity next_hop;
2615 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2616 GDS_ROUTING_remove_trail (new_trail_id);
2617 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2618 GDS_ROUTING_SRC_TO_DEST,
2623 /* Send trail teardown message across the replaced trail. */
2624 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2626 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2627 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2628 GDS_ROUTING_SRC_TO_DEST,
2629 replace_trail->trail_head->peer);
2630 /* Free the trail. */
2631 while (NULL != (trail_element = replace_trail->trail_head))
2633 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2634 replace_trail->trail_tail, trail_element);
2635 GNUNET_free_non_null (trail_element);
2638 /* Add new trial at that location. */
2639 replace_trail->is_present = GNUNET_YES;
2640 replace_trail->trail_length = new_trail_length;
2641 replace_trail->trail_id = new_trail_id;
2643 for (i = 0; i < new_trail_length; i++)
2645 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2646 element->peer = new_trail[i];
2648 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2649 replace_trail->trail_tail,
2652 /* FIXME: URGENT Are we adding the trail back to the list. */
2657 * Check if the new trail to reach to finger is unique or do we already have
2658 * such a trail present for finger.
2659 * @param existing_finger Finger identity
2660 * @param new_trail New trail to reach @a existing_finger
2661 * @param trail_length Total number of peers in new_trail.
2662 * @return #GNUNET_YES if the new trail is unique
2663 * #GNUNET_NO if same trail is already present.
2666 is_new_trail_unique (struct FingerInfo *existing_finger,
2667 const struct GNUNET_PeerIdentity *new_trail,
2668 unsigned int trail_length)
2670 struct Trail *trail;
2671 struct Trail_Element *trail_element;
2675 GNUNET_assert (existing_finger->trails_count > 0);
2677 /* Iterate over list of trails. */
2678 for (i = 0; i < existing_finger->trails_count; i++)
2680 trail = &(existing_finger->trail_list[i]);
2681 GNUNET_assert (GNUNET_YES == trail->is_present);
2683 /* New trail and existing trail length are not same. */
2684 if (trail->trail_length != trail_length)
2689 trail_element = trail->trail_head;
2690 GNUNET_assert (trail_element != NULL);
2691 for (j = 0; j < trail->trail_length; j++)
2693 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2694 &trail_element->peer))
2698 trail_element = trail_element->next;
2706 * FIXME; In case of multiple trails, we may have a case where a trail from in
2707 * between has been removed, then we should try to find a free slot , not simply
2708 * add a trail at then end of the list.
2709 * Add a new trail to existing finger. This function is called only when finger
2710 * is not my own identity or a friend.
2711 * @param existing_finger Finger
2712 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2713 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2714 * @param new_finger_trail_id Unique identifier of the trail.
2717 add_new_trail (struct FingerInfo *existing_finger,
2718 const struct GNUNET_PeerIdentity *new_trail,
2719 unsigned int new_trail_length,
2720 struct GNUNET_HashCode new_trail_id)
2722 struct Trail *trail;
2723 struct FriendInfo *first_friend;
2727 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2733 index = existing_finger->trails_count;
2734 trail = &existing_finger->trail_list[index];
2735 GNUNET_assert (GNUNET_NO == trail->is_present);
2736 trail->trail_id = new_trail_id;
2737 trail->trail_length = new_trail_length;
2738 existing_finger->trails_count++;
2739 trail->is_present = GNUNET_YES;
2741 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2742 &existing_finger->finger_identity)));
2743 /* If finger is a friend then we never call this function. */
2744 GNUNET_assert (new_trail_length > 0);
2746 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2748 first_friend->trails_count++;
2750 for (i = 0; i < new_trail_length; i++)
2752 struct Trail_Element *element;
2754 element = GNUNET_new (struct Trail_Element);
2755 element->peer = new_trail[i];
2756 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2760 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2761 existing_finger->trail_list[index].trail_head = trail->trail_head;
2762 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2763 existing_finger->trail_list[index].trail_length = new_trail_length;
2764 existing_finger->trail_list[index].trail_id = new_trail_id;
2765 existing_finger->trail_list[index].is_present = GNUNET_YES;
2770 * FIXME Check if this function is called for opposite direction if yes then
2771 * take it as parameter.
2772 * Get the next hop to send trail teardown message from routing table and
2773 * then delete the entry from routing table. Send trail teardown message for a
2774 * specific trail of a finger.
2775 * @param finger Finger whose trail is to be removed.
2776 * @param trail List of peers in trail from me to a finger, NOT including
2780 send_trail_teardown (struct FingerInfo *finger,
2781 struct Trail *trail)
2783 struct FriendInfo *friend;
2784 struct GNUNET_PeerIdentity *next_hop;
2786 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2787 GDS_ROUTING_SRC_TO_DEST);
2789 if (NULL == next_hop)
2791 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
2792 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
2797 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2800 /*FIXME: here was an assertion that trail->is_present = GNUNET_YES. But it
2801 used to fail. We have removed assertion with a condition, just for now.
2802 Find out the reason why assertion failed. */
2803 if (trail->is_present == GNUNET_NO)
2805 DEBUG(" trail id %s of peer %s is not present to send a trail teardown message., line",
2806 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
2810 /* Finger is not a friend. */
2811 if (trail->trail_length > 0)
2813 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2814 &trail->trail_head->peer);
2818 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2819 &finger->finger_identity);
2824 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2825 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
2828 if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)
2829 && (0 == trail->trail_length))
2831 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2832 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
2835 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2836 friend->trails_count--;
2837 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2838 GDS_ROUTING_SRC_TO_DEST,
2844 * Send trail teardown message across all the trails to reach to finger.
2845 * @param finger Finger whose all the trail should be freed.
2848 send_all_finger_trails_teardown (struct FingerInfo *finger)
2851 for (i = 0; i < finger->trails_count; i++)
2853 struct Trail *trail;
2855 trail = &finger->trail_list[i];
2856 GNUNET_assert (trail->is_present == GNUNET_YES);
2857 send_trail_teardown (finger, trail);
2858 trail->is_present = GNUNET_NO;
2864 * Free a specific trail
2865 * @param trail List of peers to be freed.
2868 free_trail (struct Trail *trail)
2870 struct Trail_Element *trail_element;
2872 while (NULL != (trail_element = trail->trail_head))
2874 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2877 GNUNET_free_non_null (trail_element);
2879 trail->trail_head = NULL;
2880 trail->trail_tail = NULL;
2885 * Free finger and its trail.
2886 * @param finger Finger to be freed.
2887 * @param finger_table_index Index at which finger is stored.
2890 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2892 struct Trail *trail;
2894 for (i = 0; i < finger->trails_count; i++)
2896 trail = &finger->trail_list[i];
2897 if (GNUNET_NO == trail->is_present)
2900 if (trail->trail_length > 0)
2902 trail->is_present = GNUNET_NO;
2905 finger->is_present = GNUNET_NO;
2906 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2911 * Add a new entry in finger table at finger_table_index.
2912 * In case I am my own finger, then we don't have a trail. In case of a friend,
2913 * we have a trail with unique id and '0' trail length.
2914 * In case a finger is a friend, then increment the trails count of the friend.
2915 * @param finger_identity Peer Identity of new finger
2916 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2917 * @param finger_trail_length Total number of peers in @a finger_trail.
2918 * @param trail_id Unique identifier of the trail.
2919 * @param finger_table_index Index in finger table.
2922 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2923 const struct GNUNET_PeerIdentity *finger_trail,
2924 unsigned int finger_trail_length,
2925 struct GNUNET_HashCode trail_id,
2926 unsigned int finger_table_index)
2928 struct FingerInfo *new_entry;
2929 struct FriendInfo *first_trail_hop;
2930 struct Trail *trail;
2933 new_entry = GNUNET_new (struct FingerInfo);
2934 new_entry->finger_identity = finger_identity;
2935 new_entry->finger_table_index = finger_table_index;
2936 new_entry->is_present = GNUNET_YES;
2938 /* If the new entry is my own identity. */
2939 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2942 new_entry->trails_count = 0;
2943 finger_table[finger_table_index] = *new_entry;
2944 GNUNET_free (new_entry);
2948 /* If finger is a friend, then we don't actually have a trail.
2949 * Just a trail id */
2950 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2953 GNUNET_assert (finger_trail_length == 0);
2954 new_entry->trail_list[0].trail_id = trail_id;
2955 new_entry->trails_count = 1;
2956 new_entry->trail_list[0].is_present = GNUNET_YES;
2957 new_entry->trail_list[0].trail_length = 0;
2958 new_entry->trail_list[0].trail_head = NULL;
2959 new_entry->trail_list[0].trail_tail = NULL;
2960 finger_table[finger_table_index] = *new_entry;
2961 GNUNET_assert (NULL !=
2963 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2964 &finger_identity)));
2966 first_trail_hop->trails_count++;
2967 GNUNET_free (new_entry);
2971 GNUNET_assert (NULL !=
2973 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2974 &finger_trail[0])));
2975 new_entry->trails_count = 1;
2976 first_trail_hop->trails_count++;
2977 GNUNET_assert (finger_trail_length != 0);
2978 /* Copy the finger trail into trail. */
2979 trail = GNUNET_new (struct Trail);
2980 for(i = 0; i < finger_trail_length; i++)
2982 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2984 element->next = NULL;
2985 element->prev = NULL;
2986 element->peer = finger_trail[i];
2987 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2993 /* Add trail to trail list. */
2994 new_entry->trail_list[0].trail_head = trail->trail_head;
2995 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2996 new_entry->trail_list[0].trail_length = finger_trail_length;
2997 new_entry->trail_list[0].trail_id = trail_id;
2998 new_entry->trail_list[0].is_present = GNUNET_YES;
2999 finger_table[finger_table_index] = *new_entry;
3000 GNUNET_free (new_entry);
3006 * Periodic task to verify current successor. There can be multiple trails to reach
3007 * to successor, choose the shortest one and send verify successor message
3008 * across that trail.
3009 * @param cls closure for this task
3010 * @param tc the context under which the task is running
3013 send_verify_successor_message (void *cls,
3014 const struct GNUNET_SCHEDULER_TaskContext *tc)
3016 struct FriendInfo *target_friend;
3017 struct GNUNET_HashCode trail_id;
3019 struct Trail *trail;
3020 struct Trail_Element *element;
3021 unsigned int trail_length;
3023 struct FingerInfo *successor;
3025 /* Schedule another send_find_finger_trail_message task.
3026 verify_successor_next_send_time.rel_value_us =
3027 verify_successor_next_send_time.rel_value_us +
3028 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3029 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);*/
3030 send_verify_successor_task =
3031 GNUNET_SCHEDULER_add_delayed (verify_successor_next_send_time,
3032 &send_verify_successor_message,
3035 successor = &finger_table[0];
3036 for (i = 0; i < successor->trails_count; i++)
3038 trail = &successor->trail_list[i];
3039 if(GNUNET_YES == trail->is_present)
3043 /* No valid trail found to reach to successor. */
3044 if (i == successor->trails_count)
3047 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3048 &successor->finger_identity));
3050 /* Trail stored at this index. */
3051 GNUNET_assert (GNUNET_YES == trail->is_present);
3053 trail_id = trail->trail_id;
3054 if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST))
3056 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3057 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
3061 trail_length = trail->trail_length;
3063 if (trail_length > 0)
3065 /* Copy the trail into peer list. */
3066 struct GNUNET_PeerIdentity peer_list[trail_length];
3068 element = trail->trail_head;
3069 for(j = 0; j < trail_length; j++)
3071 peer_list[j] = element->peer;
3072 element = element->next;
3075 GNUNET_assert (NULL != (target_friend =
3076 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3078 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3079 successor->finger_identity,
3080 trail_id, peer_list, trail_length,
3086 GNUNET_assert (NULL != (target_friend =
3087 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3088 &successor->finger_identity)));
3089 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3090 successor->finger_identity,
3099 * FIXME: should this be a periodic task, incrementing the search finger index?
3100 * Update the current search finger index.
3102 * FIXME document parameters!
3105 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3106 unsigned int finger_table_index)
3108 struct FingerInfo *successor;
3110 /* FIXME correct this: only move current index periodically */
3111 if (finger_table_index != current_search_finger_index)
3114 successor = &finger_table[0];
3115 GNUNET_assert (GNUNET_YES == successor->is_present);
3117 /* We were looking for immediate successor. */
3118 if (0 == current_search_finger_index)
3120 /* Start looking for immediate predecessor. */
3121 current_search_finger_index = PREDECESSOR_FINGER_ID;
3123 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3125 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3127 send_verify_successor_task =
3128 GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3134 current_search_finger_index = current_search_finger_index - 1;
3140 * Get the least significant bit set in val.
3143 * @return Position of first bit set, 65 in case of error.
3146 find_set_bit (uint64_t val)
3166 return 65; /* Some other bit was set to 1 as well. */
3173 * Calculate finger_table_index from initial 64 bit finger identity value that
3174 * we send in trail setup message.
3175 * @param ultimate_destination_finger_value Value that we calculated from our
3176 * identity and finger_table_index.
3177 * @param is_predecessor Is the entry for predecessor or not?
3178 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3179 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3182 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3183 unsigned int is_predecessor)
3187 unsigned int finger_table_index;
3189 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3190 my_id64 = GNUNET_ntohll (my_id64);
3192 /* Is this a predecessor finger? */
3193 if (1 == is_predecessor)
3195 diff = my_id64 - ultimate_destination_finger_value;
3197 finger_table_index = PREDECESSOR_FINGER_ID;
3199 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3204 diff = ultimate_destination_finger_value - my_id64;
3205 finger_table_index = find_set_bit (diff);
3207 return finger_table_index;
3212 * Remove finger and its associated data structures from finger table.
3213 * @param existing_finger Finger to be removed which is in finger table.
3214 * @param finger_table_index Index in finger table where @a existing_finger
3218 remove_existing_finger (struct FingerInfo *existing_finger,
3219 unsigned int finger_table_index)
3221 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3223 /* If I am my own finger, then we have no trails. */
3224 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3227 existing_finger->is_present = GNUNET_NO;
3228 memset ((void *)&finger_table[finger_table_index], 0,
3229 sizeof (finger_table[finger_table_index]));
3233 /* For all other fingers, send trail teardown across all the trails to reach
3234 finger, and free the finger. */
3235 send_all_finger_trails_teardown (existing_finger);
3236 free_finger (existing_finger, finger_table_index);
3242 * Check if there is already an entry in finger_table at finger_table_index.
3243 * We get the finger_table_index from 64bit finger value we got from the network.
3244 * -- If yes, then select the closest finger.
3245 * -- If new and existing finger are same, then check if you can store more
3247 * -- If yes then add trail, else keep the best trails to reach to the
3249 * -- If the new finger is closest, remove the existing entry, send trail
3250 * teardown message across all the trails to reach the existing entry.
3251 * Add the new finger.
3252 * -- If new and existing finger are different, and existing finger is closest
3254 * -- Update current_search_finger_index.
3255 * @param finger_identity Peer Identity of new finger
3256 * @param finger_trail Trail to reach the new finger
3257 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3258 * @param is_predecessor Is this entry for predecessor in finger_table?
3259 * @param finger_value 64 bit value of finger identity that we got from network.
3260 * @param finger_trail_id Unique identifier of @finger_trail.
3263 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3264 const struct GNUNET_PeerIdentity *finger_trail,
3265 unsigned int finger_trail_length,
3266 unsigned int is_predecessor,
3267 uint64_t finger_value,
3268 struct GNUNET_HashCode finger_trail_id)
3270 struct FingerInfo *existing_finger;
3271 struct GNUNET_PeerIdentity closest_peer;
3272 struct FingerInfo *successor;
3273 unsigned int finger_table_index;
3275 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3276 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3278 /* Invalid finger_table_index. */
3279 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3281 GNUNET_break_op (0);
3285 /* New entry same as successor. */
3286 if ((0 != finger_table_index) &&
3287 (PREDECESSOR_FINGER_ID != finger_table_index))
3289 successor = &finger_table[0];
3290 if (GNUNET_NO == successor->is_present)
3295 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3296 &successor->finger_identity))
3298 find_finger_trail_task_next_send_time =
3299 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3300 current_search_finger_index = 0;
3304 struct FingerInfo prev_finger;
3305 prev_finger = finger_table[finger_table_index - 1];
3306 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3307 &prev_finger.finger_identity))
3309 current_search_finger_index--;
3314 existing_finger = &finger_table[finger_table_index];
3316 /* No entry present in finger_table for given finger map index. */
3317 if (GNUNET_NO == existing_finger->is_present)
3319 add_new_finger (finger_identity, finger_trail,
3320 finger_trail_length,
3321 finger_trail_id, finger_table_index);
3322 update_current_search_finger_index (finger_identity,
3323 finger_table_index);
3328 /* If existing entry and finger identity are not same. */
3329 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3332 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3337 /* If the new finger is the closest peer. */
3338 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer))
3340 remove_existing_finger (existing_finger, finger_table_index);
3341 add_new_finger (finger_identity, finger_trail, finger_trail_length,
3342 finger_trail_id, finger_table_index);
3346 /* Existing finger is the closest one. We need to send trail teardown
3347 across the trail setup in routing table of all the peers. */
3348 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3350 if (finger_trail_length > 0)
3351 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3352 GDS_ROUTING_SRC_TO_DEST,
3355 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3356 GDS_ROUTING_SRC_TO_DEST,
3363 /* If both new and existing entry are same as my_identity, then do nothing. */
3364 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3369 /* If the existing finger is not a friend. */
3371 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3372 &existing_finger->finger_identity))
3374 /* If there is space to store more trails. */
3375 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3376 add_new_trail (existing_finger, finger_trail,
3377 finger_trail_length, finger_trail_id);
3379 select_and_replace_trail (existing_finger, finger_trail,
3380 finger_trail_length, finger_trail_id);
3384 update_current_search_finger_index (finger_identity, finger_table_index);
3390 * FIXME: Check for loop in the request. If you already are part of put path,
3391 * then you need to reset the put path length.
3392 * Core handler for P2P put messages.
3393 * @param cls closure
3394 * @param peer sender of the request
3395 * @param message message
3396 * @return #GNUNET_OK to keep the connection open,
3397 * #GNUNET_SYSERR to close it (signal serious error)
3400 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3401 const struct GNUNET_MessageHeader *message)
3403 struct PeerPutMessage *put;
3404 struct GNUNET_PeerIdentity *put_path;
3405 struct GNUNET_PeerIdentity best_known_dest;
3406 struct GNUNET_HashCode intermediate_trail_id;
3407 struct GNUNET_PeerIdentity *next_hop;
3408 enum GNUNET_DHT_RouteOption options;
3409 struct GNUNET_HashCode test_key;
3413 size_t payload_size;
3416 #if ENABLE_MALICIOUS
3417 if(1 == act_malicious)
3419 DEBUG("I am malicious,dropping put request. \n");
3424 msize = ntohs (message->size);
3425 if (msize < sizeof (struct PeerPutMessage))
3427 GNUNET_break_op (0);
3431 put = (struct PeerPutMessage *) message;
3432 putlen = ntohl (put->put_path_length);
3434 sizeof (struct PeerPutMessage) +
3435 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3437 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3439 GNUNET_break_op (0);
3442 DEBUG("GET FOR DATA_SIZE = %lu\n",msize);
3443 GNUNET_STATISTICS_update (GDS_stats,
3445 ("# Bytes received from other peers"), (int64_t) msize,
3448 best_known_dest = put->best_known_destination;
3449 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3450 payload = &put_path[putlen];
3451 options = ntohl (put->options);
3452 intermediate_trail_id = put->intermediate_trail_id;
3453 payload_size = msize - (sizeof (struct PeerPutMessage) +
3454 putlen * sizeof (struct GNUNET_PeerIdentity));
3456 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3457 payload, payload_size, &test_key))
3460 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3462 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3463 GNUNET_break_op (0);
3464 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3465 "PUT with key `%s' for block with key %s\n",
3466 put_s, GNUNET_h2s_full (&test_key));
3467 GNUNET_free (put_s);
3472 GNUNET_break_op (0);
3475 /* cannot verify, good luck */
3479 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3481 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3482 ntohl (put->block_type),
3484 NULL, 0, /* bloom filer */
3485 NULL, 0, /* xquery */
3486 payload, payload_size))
3488 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3489 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3492 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3493 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3494 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3495 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3496 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3497 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3499 GNUNET_break_op (0);
3504 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3505 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3507 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3508 GDS_ROUTING_SRC_TO_DEST);
3509 if (NULL == next_hop)
3511 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3512 GNUNET_i2s(&my_identity), GNUNET_h2s(&intermediate_trail_id), __LINE__);
3513 GNUNET_STATISTICS_update (GDS_stats,
3514 gettext_noop ("# Next hop to forward the packet not found "
3515 "trail setup request, packet dropped."),
3517 GNUNET_break_op (0);
3523 struct Closest_Peer successor;
3524 key_value = GNUNET_ntohll (key_value);
3525 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3526 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3527 *next_hop = successor.next_hop;
3528 intermediate_trail_id = successor.trail_id;
3529 best_known_dest = successor.best_known_destination;
3532 /* Check if you are already a part of put path. */
3534 for (i = 0; i < putlen; i++)
3536 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3543 /* Add yourself to the list. */
3544 struct GNUNET_PeerIdentity pp[putlen + 1];
3545 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3547 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3548 pp[putlen] = my_identity;
3554 GDS_CLIENTS_process_put (options,
3555 ntohl (put->block_type),
3556 ntohl (put->hop_count),
3557 ntohl (put->desired_replication_level),
3559 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3564 /* I am the final destination */
3565 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3567 DEBUG("PUT destination is me = %s,KEY = %s\n",GNUNET_i2s(&my_identity),GNUNET_h2s(&(put->key)));
3568 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3569 &(put->key),putlen, pp, ntohl (put->block_type),
3570 payload_size, payload);
3574 GDS_NEIGHBOURS_send_put (&put->key,
3575 ntohl (put->block_type),ntohl (put->options),
3576 ntohl (put->desired_replication_level),
3577 best_known_dest, intermediate_trail_id, next_hop,
3578 ntohl (put->hop_count), putlen, pp,
3579 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3580 payload, payload_size);
3587 * FIXME: Check for loop in the request. If you already are part of get path,
3588 * then you need to reset the get path length.
3589 * Core handler for p2p get requests.
3591 * @param cls closure
3592 * @param peer sender of the request
3593 * @param message message
3594 * @return #GNUNET_OK to keep the connection open,
3595 * #GNUNET_SYSERR to close it (signal serious error)
3598 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3599 const struct GNUNET_MessageHeader *message)
3601 const struct PeerGetMessage *get;
3602 const struct GNUNET_PeerIdentity *get_path;
3603 struct GNUNET_PeerIdentity best_known_dest;
3604 struct GNUNET_HashCode intermediate_trail_id;
3605 struct GNUNET_PeerIdentity *next_hop;
3606 uint32_t get_length;
3610 #if ENABLE_MALICIOUS
3611 if(1 == act_malicious)
3613 DEBUG("I am malicious,dropping get request. \n");
3618 msize = ntohs (message->size);
3619 if (msize < sizeof (struct PeerGetMessage))
3621 GNUNET_break_op (0);
3625 get = (const struct PeerGetMessage *)message;
3626 get_length = ntohl (get->get_path_length);
3627 best_known_dest = get->best_known_destination;
3628 intermediate_trail_id = get->intermediate_trail_id;
3629 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3632 sizeof (struct PeerGetMessage) +
3633 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3635 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3637 GNUNET_break_op (0);
3640 DEBUG("PUT FOR DATA_SIZE = %lu\n",msize);
3641 GNUNET_STATISTICS_update (GDS_stats,
3643 ("# Bytes received from other peers"), msize,
3646 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3647 key_value = GNUNET_ntohll (key_value);
3649 /* I am not the final destination. I am part of trail to reach final dest. */
3650 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3652 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3653 GDS_ROUTING_SRC_TO_DEST);
3654 if (NULL == next_hop)
3656 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3657 GNUNET_i2s(&my_identity), GNUNET_h2s(&intermediate_trail_id), __LINE__);
3658 GNUNET_STATISTICS_update (GDS_stats,
3659 gettext_noop ("# Next hop to forward the packet not found "
3660 "GET request, packet dropped."),
3668 struct Closest_Peer successor;
3670 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3671 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3672 *next_hop = successor.next_hop;
3673 best_known_dest = successor.best_known_destination;
3674 intermediate_trail_id = successor.trail_id;
3677 /* Check if you are already a part of get path. */
3679 for (i = 0; i < get_length; i++)
3681 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &get_path[i]))
3688 /* Add yourself in the get path. */
3689 struct GNUNET_PeerIdentity gp[get_length + 1];
3690 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3691 gp[get_length] = my_identity;
3692 get_length = get_length + 1;
3693 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3694 get->desired_replication_level, get->get_path_length,
3697 /* I am the final destination. */
3698 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3700 DEBUG("GET destination is me = %s,KEY = %s,get_length = %d\n",
3701 GNUNET_i2s(&my_identity),GNUNET_h2s(&(get->key)),get_length);
3702 if (1 == get_length)
3704 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0,
3705 NULL, 0, 1, &my_identity, NULL,&my_identity);
3709 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3710 get_length, gp, &gp[get_length - 2],
3716 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3717 get->desired_replication_level, best_known_dest,
3718 intermediate_trail_id, next_hop, 0,
3726 * Core handler for get result
3727 * @param cls closure
3728 * @param peer sender of the request
3729 * @param message message
3730 * @return #GNUNET_OK to keep the connection open,
3731 * #GNUNET_SYSERR to close it (signal serious error)
3734 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3735 const struct GNUNET_MessageHeader *message)
3737 const struct PeerGetResultMessage *get_result;
3738 const struct GNUNET_PeerIdentity *get_path;
3739 const struct GNUNET_PeerIdentity *put_path;
3740 const void *payload;
3741 size_t payload_size;
3743 unsigned int getlen;
3744 unsigned int putlen;
3745 int current_path_index;
3747 msize = ntohs (message->size);
3748 if (msize < sizeof (struct PeerGetResultMessage))
3750 GNUNET_break_op (0);
3754 get_result = (const struct PeerGetResultMessage *)message;
3755 getlen = ntohl (get_result->get_path_length);
3756 putlen = ntohl (get_result->put_path_length);
3759 sizeof (struct PeerGetResultMessage) +
3760 getlen * sizeof (struct GNUNET_PeerIdentity) +
3761 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3763 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3765 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3767 GNUNET_break_op (0);
3770 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3771 GNUNET_STATISTICS_update (GDS_stats,
3773 ("# Bytes received from other peers"), msize,
3776 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3777 get_path = &put_path[putlen];
3778 payload = (const void *) &get_path[getlen];
3779 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3780 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3782 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3784 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3785 getlen, get_path, putlen,
3786 put_path, get_result->type, payload_size, payload);
3791 current_path_index = search_my_index (get_path, getlen);
3792 if (-1 == current_path_index )
3794 DEBUG ("No entry found in get path.\n");
3796 return GNUNET_SYSERR;
3798 if((getlen + 1) == current_path_index)
3800 DEBUG("Present twice in get path. Not allowed. \n");
3802 return GNUNET_SYSERR;
3804 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3805 &get_path[current_path_index - 1],
3806 &(get_result->querying_peer), putlen, put_path,
3807 getlen, get_path, get_result->expiration_time,
3808 payload, payload_size);
3811 return GNUNET_SYSERR;
3816 * Find the next hop to pass trail setup message. First find the local best known
3817 * hop from your own identity, friends and finger. If you were part of trail,
3818 * then get the next hop from routing table. Compare next_hop from routing table
3819 * and local best known hop, and return the closest one to final_dest_finger_val
3820 * @param final_dest_finger_val 64 bit value of finger identity
3821 * @param intermediate_trail_id If you are part of trail to reach to some other
3822 * finger, then it is the trail id to reach to
3823 * that finger, else set to 0.
3824 * @param is_predecessor Are we looking for closest successor or predecessor.
3825 * @param current_dest In case you are part of trail, then finger to which
3826 * we should forward the message. Else my own identity
3827 * @return Closest Peer for @a final_dest_finger_val
3829 static struct Closest_Peer
3830 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3831 struct GNUNET_HashCode intermediate_trail_id,
3832 unsigned int is_predecessor,
3833 struct GNUNET_PeerIdentity prev_hop,
3834 struct GNUNET_PeerIdentity source,
3835 struct GNUNET_PeerIdentity *current_dest)
3837 struct Closest_Peer peer;
3839 /* Find a local best known peer. */
3840 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3842 /* Am I just a part of a trail towards a finger (current_destination)? */
3843 /* Select best successor among one found locally and current_destination
3844 * that we got from network.*/
3845 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3846 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3849 struct GNUNET_PeerIdentity closest_peer;
3851 closest_peer = select_closest_peer (&peer.best_known_destination,
3853 final_dest_finger_val,
3856 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3857 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
3859 struct GNUNET_PeerIdentity *next_hop;
3861 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3862 GDS_ROUTING_SRC_TO_DEST);
3863 /* It may happen that trail teardown message got delayed and hence,
3864 the previous hop sent the message over intermediate trail id.In that
3865 case next_hop could be NULL. */
3866 if(NULL != next_hop)
3868 peer.next_hop = *next_hop;
3869 peer.best_known_destination = *current_dest;
3870 peer.trail_id = intermediate_trail_id;
3879 * Core handle for PeerTrailSetupMessage.
3880 * @param cls closure
3881 * @param message message
3882 * @param peer peer identity this notification is about
3883 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3886 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3887 const struct GNUNET_MessageHeader *message)
3889 const struct PeerTrailSetupMessage *trail_setup;
3890 const struct GNUNET_PeerIdentity *trail_peer_list;
3891 struct GNUNET_PeerIdentity current_dest;
3892 struct FriendInfo *target_friend;
3893 struct GNUNET_PeerIdentity source;
3894 uint64_t final_dest_finger_val;
3895 struct GNUNET_HashCode intermediate_trail_id;
3896 struct GNUNET_HashCode trail_id;
3897 unsigned int is_predecessor;
3898 uint32_t trail_length;
3902 msize = ntohs (message->size);
3903 if (msize < sizeof (struct PeerTrailSetupMessage))
3905 GNUNET_break_op (0);
3906 return GNUNET_SYSERR;
3909 trail_setup = (const struct PeerTrailSetupMessage *) message;
3910 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3911 sizeof (struct GNUNET_PeerIdentity) != 0)
3913 GNUNET_break_op (0);
3916 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3917 sizeof (struct GNUNET_PeerIdentity);
3919 GNUNET_STATISTICS_update (GDS_stats,
3921 ("# Bytes received from other peers"), msize,
3924 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3925 current_dest = trail_setup->best_known_destination;
3926 trail_id = trail_setup->trail_id;
3927 final_dest_finger_val =
3928 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3929 source = trail_setup->source_peer;
3930 is_predecessor = ntohl (trail_setup->is_predecessor);
3931 intermediate_trail_id = trail_setup->intermediate_trail_id;
3933 /* Did the friend insert its ID in the trail list? */
3934 if (trail_length > 0 &&
3935 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
3937 GNUNET_break_op (0);
3938 return GNUNET_SYSERR;
3941 /* If I was the source and got the message back, then set trail length to 0.*/
3942 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3947 /* Check if you are friend of source. */
3948 if (trail_length >= 1)
3950 if(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source))
3952 /* If I am a friend, then I can be the first contact, so make
3953 trail length 0. We are going to add ourself later in the code.*/
3958 /* Check if you are present in the trail seen so far? */
3959 for (i = 0; i < trail_length ; i++)
3961 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
3963 trail_length = i; /* Check that you add yourself again */
3968 /* Is my routing table full? */
3969 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3971 GNUNET_assert (NULL !=
3973 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
3974 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
3975 my_identity, is_predecessor,
3976 trail_peer_list, trail_length,
3977 trail_id, target_friend,
3978 CONGESTION_TIMEOUT);
3982 /* Get the next hop to forward the trail setup request. */
3983 struct Closest_Peer next_peer =
3984 get_local_best_known_next_hop (final_dest_finger_val,
3985 intermediate_trail_id,
3991 /* Am I the final destination? */
3992 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
3995 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
3997 finger_table_add (my_identity, NULL, 0, is_predecessor,
3998 final_dest_finger_val, trail_id);
4002 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4008 if (trail_length > 0)
4010 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4011 &trail_peer_list[trail_length-1]);
4014 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4016 if (NULL == target_friend)
4018 GNUNET_break_op (0);
4019 return GNUNET_SYSERR;
4021 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4022 GDS_NEIGHBOURS_send_trail_setup_result (source,
4024 target_friend, trail_length,
4027 final_dest_finger_val,trail_id);
4029 else /* I'm not the final destination. */
4031 GNUNET_assert (NULL !=
4033 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4034 &next_peer.next_hop)));
4036 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4038 /* Add yourself to list of peers. */
4039 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4041 memcpy (peer_list, trail_peer_list,
4042 trail_length * sizeof (struct GNUNET_PeerIdentity));
4043 peer_list[trail_length] = my_identity;
4044 GDS_NEIGHBOURS_send_trail_setup (source,
4045 final_dest_finger_val,
4046 next_peer.best_known_destination,
4047 target_friend, trail_length + 1, peer_list,
4048 is_predecessor, trail_id,
4049 next_peer.trail_id);
4052 GDS_NEIGHBOURS_send_trail_setup (source,
4053 final_dest_finger_val,
4054 next_peer.best_known_destination,
4055 target_friend, 0, NULL,
4056 is_predecessor, trail_id,
4057 next_peer.trail_id);
4064 * Core handle for p2p trail setup result messages.
4066 * @param message message
4067 * @param peer sender of this message.
4068 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4071 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4072 const struct GNUNET_MessageHeader *message)
4074 const struct PeerTrailSetupResultMessage *trail_result;
4075 const struct GNUNET_PeerIdentity *trail_peer_list;
4076 struct GNUNET_PeerIdentity next_hop;
4077 struct FriendInfo *target_friend;
4078 struct GNUNET_PeerIdentity querying_peer;
4079 struct GNUNET_PeerIdentity finger_identity;
4080 uint32_t trail_length;
4081 uint64_t ulitmate_destination_finger_value;
4082 uint32_t is_predecessor;
4083 struct GNUNET_HashCode trail_id;
4087 msize = ntohs (message->size);
4088 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4090 GNUNET_break_op (0);
4094 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4095 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4096 sizeof (struct GNUNET_PeerIdentity) != 0)
4098 GNUNET_break_op (0);
4101 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4102 sizeof (struct GNUNET_PeerIdentity);
4104 GNUNET_STATISTICS_update (GDS_stats,
4106 ("# Bytes received from other peers"), msize,
4109 is_predecessor = ntohl (trail_result->is_predecessor);
4110 querying_peer = trail_result->querying_peer;
4111 finger_identity = trail_result->finger_identity;
4112 trail_id = trail_result->trail_id;
4113 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4114 ulitmate_destination_finger_value =
4115 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4117 /* Am I the one who initiated the query? */
4118 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4120 /* Check that you got the message from the correct peer. */
4121 if (trail_length > 0)
4123 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4128 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4131 GDS_ROUTING_add (trail_id, my_identity, *peer);
4132 finger_table_add (finger_identity, trail_peer_list, trail_length,
4133 is_predecessor, ulitmate_destination_finger_value, trail_id);
4137 /* Get my location in the trail. */
4138 my_index = search_my_index (trail_peer_list, trail_length);
4141 DEBUG ("Not found in trail\n");
4143 return GNUNET_SYSERR;
4146 if ((trail_length + 1) == my_index)
4148 DEBUG ("Found twice in trail.\n");
4150 return GNUNET_SYSERR;
4153 //TODO; Refactor code here and above to check if sender peer is correct
4156 if(trail_length > 1)
4157 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4160 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4162 next_hop = trail_result->querying_peer;
4166 if(my_index == trail_length - 1)
4169 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4174 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4176 next_hop = trail_peer_list[my_index - 1];
4179 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4180 if (NULL == target_friend)
4182 GNUNET_break_op (0);
4183 return GNUNET_SYSERR;
4185 GDS_ROUTING_add (trail_id, next_hop, *peer);
4186 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4187 target_friend, trail_length, trail_peer_list,
4189 ulitmate_destination_finger_value,
4197 * @param trail Trail to be inverted
4198 * @param trail_length Total number of peers in the trail.
4199 * @return Updated trail
4201 static struct GNUNET_PeerIdentity *
4202 invert_trail (const struct GNUNET_PeerIdentity *trail,
4203 unsigned int trail_length)
4207 struct GNUNET_PeerIdentity *inverted_trail;
4209 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4212 j = trail_length - 1;
4213 while (i < trail_length)
4215 inverted_trail[i] = trail[j];
4220 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4221 &inverted_trail[0]));
4222 return inverted_trail;
4227 * Return the shortest trail among all the trails to reach to finger from me.
4228 * @param finger Finger
4229 * @param shortest_trail_length[out] Trail length of shortest trail from me
4231 * @return Shortest trail.
4233 static struct GNUNET_PeerIdentity *
4234 get_shortest_trail (struct FingerInfo *finger,
4235 unsigned int *trail_length)
4237 struct Trail *trail;
4238 unsigned int flag = 0;
4239 unsigned int shortest_trail_index = 0;
4240 int shortest_trail_length = -1;
4241 struct Trail_Element *trail_element;
4242 struct GNUNET_PeerIdentity *trail_list;
4245 trail = GNUNET_new (struct Trail);
4247 /* Get the shortest trail to reach to current successor. */
4248 for (i = 0; i < finger->trails_count; i++)
4250 trail = &finger->trail_list[i];
4254 shortest_trail_index = i;
4255 shortest_trail_length = trail->trail_length;
4260 if (shortest_trail_length > trail->trail_length)
4262 shortest_trail_index = i;
4263 shortest_trail_length = trail->trail_length;
4268 /* Copy the shortest trail and return. */
4269 trail = &finger->trail_list[shortest_trail_index];
4270 trail_element = trail->trail_head;
4272 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4273 shortest_trail_length);
4275 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4277 trail_list[i] = trail_element->peer;
4280 GNUNET_assert(shortest_trail_length != -1);
4282 *trail_length = shortest_trail_length;
4288 * Check if trail_1 and trail_2 have any common element. If yes then join
4289 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4290 * @param trail_1 Trail from source to me, NOT including endpoints.
4291 * @param trail_1_len Total number of peers @a trail_1
4292 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4293 * @param trail_2_len Total number of peers @a trail_2
4294 * @param joined_trail_len Total number of peers in combined trail of trail_1
4296 * @return Joined trail.
4298 static struct GNUNET_PeerIdentity *
4299 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4300 unsigned int trail_1_len,
4301 struct GNUNET_PeerIdentity *trail_2,
4302 unsigned int trail_2_len,
4303 unsigned int *joined_trail_len)
4305 struct GNUNET_PeerIdentity *joined_trail;
4310 for (i = 0; i < trail_1_len; i++)
4312 for (j = 0; j < trail_2_len; j++)
4314 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4317 *joined_trail_len = i + (trail_2_len - j);
4318 joined_trail = GNUNET_malloc (*joined_trail_len *
4319 sizeof(struct GNUNET_PeerIdentity));
4322 /* Copy all the elements from 0 to i into joined_trail. */
4323 for(k = 0; k < ( i+1); k++)
4325 joined_trail[k] = trail_1[k];
4328 /* Increment j as entry stored is same as entry stored at i*/
4331 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4332 while(k <= (*joined_trail_len - 1))
4334 joined_trail[k] = trail_2[j];
4339 return joined_trail;
4343 /* Here you should join the trails. */
4344 *joined_trail_len = trail_1_len + trail_2_len + 1;
4345 joined_trail = GNUNET_malloc (*joined_trail_len *
4346 sizeof(struct GNUNET_PeerIdentity));
4349 for(i = 0; i < trail_1_len;i++)
4351 joined_trail[i] = trail_1[i];
4354 joined_trail[i] = my_identity;
4357 for (j = 0; i < *joined_trail_len; i++,j++)
4359 joined_trail[i] = trail_2[j];
4362 return joined_trail;
4367 * Return the trail from source to my current predecessor. Check if source
4368 * is already part of the this trail, if yes then return the shorten trail.
4369 * @param current_trail Trail from source to me, NOT including the endpoints.
4370 * @param current_trail_length Number of peers in @a current_trail.
4371 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4372 * source to my predecessor, NOT including
4374 * @return Trail from source to my predecessor.
4376 static struct GNUNET_PeerIdentity *
4377 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4378 const struct GNUNET_PeerIdentity *trail_src_to_me,
4379 unsigned int trail_src_to_me_len,
4380 unsigned int *trail_src_to_curr_pred_length)
4382 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4383 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4384 unsigned int trail_me_to_curr_pred_length;
4385 struct FingerInfo *current_predecessor;
4389 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4391 /* Check if trail_src_to_me contains current_predecessor. */
4392 for (i = 0; i < trail_src_to_me_len; i++)
4394 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4395 ¤t_predecessor->finger_identity))
4399 *trail_src_to_curr_pred_length = i;
4404 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4405 sizeof(struct GNUNET_PeerIdentity));
4406 for(j = 0; j < i;j++)
4407 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4408 return trail_src_to_curr_pred;
4412 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4413 &trail_me_to_curr_pred_length);
4415 /* Check if trail contains the source_peer. */
4416 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4418 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4419 &trail_me_to_curr_pred[i]))
4422 /* Source is NOT part of trail. */
4425 /* Source is the last element in the trail to reach to my pred.
4426 Source is direct friend of the pred. */
4427 if (trail_me_to_curr_pred_length == i)
4429 *trail_src_to_curr_pred_length = 0;
4433 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4434 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4435 *trail_src_to_curr_pred_length);
4437 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4439 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4441 GNUNET_free_non_null(trail_me_to_curr_pred);
4442 return trail_src_to_curr_pred;
4446 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4447 trail_src_to_me_len,
4448 trail_me_to_curr_pred,
4449 trail_me_to_curr_pred_length,
4451 *trail_src_to_curr_pred_length = len;
4452 GNUNET_free_non_null(trail_me_to_curr_pred);
4453 return trail_src_to_curr_pred;
4458 * Add finger as your predecessor. To add, first generate a new trail id, invert
4459 * the trail to get the trail from me to finger, add an entry in your routing
4460 * table, send add trail message to peers which are part of trail from me to
4461 * finger and add finger in finger table.
4464 * @param trail_length
4467 update_predecessor (struct GNUNET_PeerIdentity finger,
4468 struct GNUNET_PeerIdentity *trail,
4469 unsigned int trail_length)
4471 struct GNUNET_HashCode trail_to_new_predecessor_id;
4472 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4473 struct FriendInfo *target_friend;
4475 /* Generate trail id for trail from me to new predecessor = finger. */
4476 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4477 &trail_to_new_predecessor_id,
4478 sizeof (trail_to_new_predecessor_id));
4480 /* Finger is a friend. */
4481 if (trail_length == 0)
4483 trail_to_new_predecessor = NULL;
4484 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4485 GNUNET_assert (NULL != (target_friend =
4486 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4491 /* Invert the trail to get the trail from me to finger, NOT including the
4493 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4494 &trail[trail_length-1]));
4496 trail_to_new_predecessor = invert_trail (trail, trail_length);
4498 /* Add an entry in your routing table. */
4499 GDS_ROUTING_add (trail_to_new_predecessor_id,
4501 trail_to_new_predecessor[0]);
4503 GNUNET_assert (NULL != (target_friend =
4504 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4505 &trail_to_new_predecessor[0])));
4506 GNUNET_assert (NULL != (
4507 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4508 &trail[trail_length - 1])));
4511 /* Add entry in routing table of all peers that are part of trail from me
4512 to finger, including finger. */
4513 GDS_NEIGHBOURS_send_add_trail (my_identity,
4515 trail_to_new_predecessor_id,
4516 trail_to_new_predecessor,
4520 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4521 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4522 GNUNET_free_non_null(trail_to_new_predecessor);
4527 * Check if you already have a predecessor. If not then add finger as your
4528 * predecessor. If you have predecessor, then compare two peer identites.
4529 * If finger is correct predecessor, then remove the old entry, add finger in
4530 * finger table and send add_trail message to add the trail in the routing
4531 * table of all peers which are part of trail to reach from me to finger.
4532 * @param finger New peer which may be our predecessor.
4533 * @param trail List of peers to reach from @finger to me.
4534 * @param trail_length Total number of peer in @a trail.
4537 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4538 struct GNUNET_PeerIdentity *trail,
4539 unsigned int trail_length)
4541 struct FingerInfo *current_predecessor;
4542 struct GNUNET_PeerIdentity closest_peer;
4543 uint64_t predecessor_value;
4544 unsigned int is_predecessor = 1;
4546 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4547 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4549 /* No predecessor. Add finger as your predecessor. */
4550 if (GNUNET_NO == current_predecessor->is_present)
4552 update_predecessor (finger, trail, trail_length);
4556 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4562 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4563 closest_peer = select_closest_peer (&finger,
4564 ¤t_predecessor->finger_identity,
4565 predecessor_value, is_predecessor);
4567 /* Finger is the closest predecessor. Remove the existing one and add the new
4569 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4571 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4572 update_predecessor (finger, trail, trail_length);
4580 * Core handle for p2p verify successor messages.
4581 * @param cls closure
4582 * @param message message
4583 * @param peer peer identity this notification is about
4584 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4587 handle_dht_p2p_verify_successor(void *cls,
4588 const struct GNUNET_PeerIdentity *peer,
4589 const struct GNUNET_MessageHeader *message)
4591 const struct PeerVerifySuccessorMessage *vsm;
4592 struct GNUNET_HashCode trail_id;
4593 struct GNUNET_PeerIdentity successor;
4594 struct GNUNET_PeerIdentity source_peer;
4595 struct GNUNET_PeerIdentity *trail;
4596 struct GNUNET_PeerIdentity *next_hop;
4597 struct FingerInfo current_predecessor;
4598 struct FriendInfo *target_friend;
4599 unsigned int trail_src_to_curr_pred_len = 0;
4600 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4601 unsigned int trail_length;
4604 msize = ntohs (message->size);
4606 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4608 GNUNET_break_op (0);
4612 vsm = (const struct PeerVerifySuccessorMessage *) message;
4613 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4614 sizeof (struct GNUNET_PeerIdentity);
4615 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4616 sizeof (struct GNUNET_PeerIdentity) != 0)
4618 GNUNET_break_op (0);
4622 GNUNET_STATISTICS_update (GDS_stats,
4624 ("# Bytes received from other peers"), msize,
4627 trail_id = vsm->trail_id;
4628 source_peer = vsm->source_peer;
4629 successor = vsm->successor;
4630 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4632 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4634 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4636 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4637 if (NULL == next_hop)
4639 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
4640 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
4641 GNUNET_break_op (0);
4645 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4647 if(NULL == target_friend)
4652 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4653 trail_id, trail, trail_length,
4658 /* I am the destination of this message. */
4660 /* Check if the source_peer could be our predecessor and if yes then update
4662 compare_and_update_predecessor (source_peer, trail, trail_length);
4663 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4665 /* Is source of this message NOT my predecessor. */
4666 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4669 trail_src_to_curr_pred =
4670 get_trail_src_to_curr_pred (source_peer,
4673 &trail_src_to_curr_pred_len);
4677 trail_src_to_curr_pred_len = trail_length;
4680 trail_src_to_curr_pred =
4681 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4682 *trail_src_to_curr_pred_len);
4683 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4685 trail_src_to_curr_pred[i] = trail[i];
4689 GNUNET_assert (NULL !=
4691 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4692 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4693 current_predecessor.finger_identity,
4694 trail_id, trail_src_to_curr_pred,
4695 trail_src_to_curr_pred_len,
4696 GDS_ROUTING_DEST_TO_SRC,
4698 GNUNET_free_non_null(trail_src_to_curr_pred);
4704 * If the trail from me to my probable successor contains a friend not
4705 * at index 0, then we can shorten the trail.
4706 * @param probable_successor Peer which is our probable successor
4707 * @param trail_me_to_probable_successor Peers in path from me to my probable
4708 * successor, NOT including the endpoints.
4709 * @param trail_me_to_probable_successor_len Total number of peers in
4710 * @a trail_me_to_probable_succesor.
4711 * @return Updated trail, if any friend found.
4712 * Else the trail_me_to_probable_successor.
4714 struct GNUNET_PeerIdentity *
4715 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4716 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4717 unsigned int trail_me_to_probable_successor_len,
4718 unsigned int *trail_to_new_successor_length)
4722 struct GNUNET_PeerIdentity *trail_to_new_successor;
4724 /* Probable successor is a friend */
4725 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4726 &probable_successor))
4728 trail_to_new_successor = NULL;
4729 *trail_to_new_successor_length = 0;
4730 return trail_to_new_successor;
4733 /* Is there any friend of yours in this trail. */
4734 if(trail_me_to_probable_successor_len > 1)
4736 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4738 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4739 &trail_me_to_probable_successor[i]))
4742 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4743 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4744 *trail_to_new_successor_length);
4747 for(j = 0;j < *trail_to_new_successor_length;i++,j++)
4749 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4752 return trail_to_new_successor;
4756 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4757 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4762 * Check if the peer which sent us verify successor result message is still ours
4763 * successor or not. If not, then compare existing successor and probable successor.
4764 * In case probable successor is the correct successor, remove the existing
4765 * successor. Add probable successor as new successor. Send notify new successor
4766 * message to new successor.
4767 * @param curr_succ Peer to which we sent the verify successor message. It may
4768 * or may not be our real current successor, as we may have few iterations of
4769 * find finger trail task.
4770 * @param probable_successor Peer which should be our successor accroding to @a
4772 * @param trail List of peers to reach from me to @a probable successor, NOT including
4774 * @param trail_length Total number of peers in @a trail.
4777 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4778 struct GNUNET_PeerIdentity probable_successor,
4779 const struct GNUNET_PeerIdentity *trail,
4780 unsigned int trail_length)
4782 struct FingerInfo *current_successor;
4783 struct GNUNET_PeerIdentity closest_peer;
4784 struct GNUNET_HashCode trail_id;
4785 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4786 struct FriendInfo *target_friend;
4787 unsigned int trail_me_to_probable_succ_len;
4788 unsigned int is_predecessor = 0;
4789 uint64_t successor_value;
4791 current_successor = &finger_table[0];
4792 successor_value = compute_finger_identity_value(0);
4794 /* If probable successor is same as current_successor, do nothing. */
4795 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
4796 ¤t_successor->finger_identity))
4799 closest_peer = select_closest_peer (&probable_successor,
4800 ¤t_successor->finger_identity,
4801 successor_value, is_predecessor);
4803 /* If the current_successor in the finger table is closest, then do nothing. */
4804 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
4805 ¤t_successor->finger_identity))
4807 if ((NULL != GDS_stats))
4813 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
4814 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
4815 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
4816 GNUNET_free (my_id_str);
4817 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
4823 /* Probable successor is the closest peer.*/
4824 if(trail_length > 0)
4826 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4831 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4832 &probable_successor));
4835 trail_me_to_probable_succ_len = 0;
4836 trail_me_to_probable_succ =
4837 check_trail_me_to_probable_succ (probable_successor,
4838 trail, trail_length,
4839 &trail_me_to_probable_succ_len);
4841 /* Remove the existing successor. */
4842 remove_existing_finger (current_successor, 0);
4843 /* Generate a new trail id to reach to your new successor. */
4844 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4845 &trail_id, sizeof (trail_id));
4847 if (trail_me_to_probable_succ_len > 0)
4849 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4850 GNUNET_assert (NULL !=
4852 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4853 &trail_me_to_probable_succ[0])));
4857 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4858 GNUNET_assert (NULL !=
4860 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4861 &probable_successor)));
4864 add_new_finger (probable_successor, trail_me_to_probable_succ,
4865 trail_me_to_probable_succ_len, trail_id, 0);
4867 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4868 trail_me_to_probable_succ,
4869 trail_me_to_probable_succ_len,
4877 * FIXME: Check for duplicate elements everywhere when you are making
4879 * Core handle for p2p verify successor result messages.
4880 * @param cls closure
4881 * @param message message
4882 * @param peer peer identity this notification is about
4883 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4886 handle_dht_p2p_verify_successor_result(void *cls,
4887 const struct GNUNET_PeerIdentity *peer,
4888 const struct GNUNET_MessageHeader *message)
4890 const struct PeerVerifySuccessorResultMessage *vsrm;
4891 enum GDS_ROUTING_trail_direction trail_direction;
4892 struct GNUNET_PeerIdentity querying_peer;
4893 struct GNUNET_HashCode trail_id;
4894 struct GNUNET_PeerIdentity *next_hop;
4895 struct FriendInfo *target_friend;
4896 struct GNUNET_PeerIdentity probable_successor;
4897 struct GNUNET_PeerIdentity current_successor;
4898 const struct GNUNET_PeerIdentity *trail;
4899 unsigned int trail_length;
4902 msize = ntohs (message->size);
4903 /* We send a trail to reach from old successor to new successor, if
4904 * old_successor != new_successor.*/
4905 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4907 GNUNET_break_op (0);
4911 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4912 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4913 sizeof (struct GNUNET_PeerIdentity);
4915 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4916 sizeof (struct GNUNET_PeerIdentity) != 0)
4918 GNUNET_break_op (0);
4922 GNUNET_STATISTICS_update (GDS_stats,
4924 ("# Bytes received from other peers"), msize,
4927 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4928 querying_peer = vsrm->querying_peer;
4929 trail_direction = ntohl (vsrm->trail_direction);
4930 trail_id = vsrm->trail_id;
4931 probable_successor = vsrm->probable_successor;
4932 current_successor = vsrm->current_successor;
4934 verify_successor_next_send_time =
4935 GNUNET_TIME_STD_BACKOFF(verify_successor_next_send_time);
4936 /* I am the querying_peer. */
4937 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4939 compare_and_update_successor (current_successor,
4940 probable_successor, trail, trail_length);
4944 /*If you are not the querying peer then pass on the message */
4945 if(NULL == (next_hop =
4946 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
4948 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
4949 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
4953 if (NULL == (target_friend =
4954 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
4959 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4960 vsrm->current_successor,
4961 probable_successor, trail_id,
4964 trail_direction, target_friend);
4970 * Core handle for p2p notify new successor messages.
4971 * @param cls closure
4972 * @param message message
4973 * @param peer peer identity this notification is about
4974 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4977 handle_dht_p2p_notify_new_successor(void *cls,
4978 const struct GNUNET_PeerIdentity *peer,
4979 const struct GNUNET_MessageHeader *message)
4981 const struct PeerNotifyNewSuccessorMessage *nsm;
4982 struct GNUNET_PeerIdentity *trail;
4983 struct GNUNET_PeerIdentity source;
4984 struct GNUNET_PeerIdentity new_successor;
4985 struct GNUNET_HashCode trail_id;
4986 struct GNUNET_PeerIdentity next_hop;
4987 struct FriendInfo *target_friend;
4990 uint32_t trail_length;
4992 msize = ntohs (message->size);
4994 /* We have the trail to reach from source to new successor. */
4995 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
4997 GNUNET_break_op (0);
5001 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5002 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5003 sizeof (struct GNUNET_PeerIdentity);
5004 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5005 sizeof (struct GNUNET_PeerIdentity) != 0)
5007 GNUNET_break_op (0);
5011 GNUNET_STATISTICS_update (GDS_stats,
5013 ("# Bytes received from other peers"), msize,
5016 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5017 source = nsm->source_peer;
5018 new_successor = nsm->new_successor;
5019 trail_id = nsm->trail_id;
5021 /* I am the new_successor to source_peer. */
5022 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5024 if(trail_length > 0)
5025 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5028 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5030 compare_and_update_predecessor (source, trail, trail_length);
5034 GNUNET_assert(trail_length > 0);
5035 /* I am part of trail to reach to successor. */
5036 my_index = search_my_index (trail, trail_length);
5039 DEBUG ("No entry found in trail\n");
5040 GNUNET_break_op (0);
5041 return GNUNET_SYSERR;
5043 if((trail_length + 1) == my_index)
5045 DEBUG ("Found twice in trail.\n");
5046 GNUNET_break_op (0);
5047 return GNUNET_SYSERR;
5049 if ((trail_length-1) == my_index)
5050 next_hop = new_successor;
5052 next_hop = trail[my_index + 1];
5053 /* Add an entry in routing table for trail from source to its new successor. */
5054 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5055 GNUNET_assert (NULL !=
5057 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5058 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5060 trail_id, target_friend);
5067 * Core handler for P2P trail rejection message
5068 * @param cls closure
5069 * @param message message
5070 * @param peer peer identity this notification is about
5071 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5074 handle_dht_p2p_trail_setup_rejection (void *cls,
5075 const struct GNUNET_PeerIdentity *peer,
5076 const struct GNUNET_MessageHeader *message)
5078 const struct PeerTrailRejectionMessage *trail_rejection;
5079 unsigned int trail_length;
5080 const struct GNUNET_PeerIdentity *trail_peer_list;
5081 struct FriendInfo *target_friend;
5082 struct GNUNET_TIME_Relative congestion_timeout;
5083 struct GNUNET_HashCode trail_id;
5084 struct GNUNET_PeerIdentity next_peer;
5085 struct GNUNET_PeerIdentity source;
5086 struct GNUNET_PeerIdentity *next_hop;
5087 uint64_t ultimate_destination_finger_value;
5088 unsigned int is_predecessor;
5091 msize = ntohs (message->size);
5092 /* We are passing the trail setup so far. */
5093 if (msize < sizeof (struct PeerTrailRejectionMessage))
5095 GNUNET_break_op (0);
5099 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5100 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5101 sizeof (struct GNUNET_PeerIdentity);
5102 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5103 sizeof (struct GNUNET_PeerIdentity) != 0)
5105 GNUNET_break_op (0);
5109 GNUNET_STATISTICS_update (GDS_stats,
5111 ("# Bytes received from other peers"), msize,
5114 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5115 is_predecessor = ntohl (trail_rejection->is_predecessor);
5116 congestion_timeout = trail_rejection->congestion_time;
5117 source = trail_rejection->source_peer;
5118 trail_id = trail_rejection->trail_id;
5119 ultimate_destination_finger_value =
5120 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5122 /* First set the congestion time of the friend that sent you this message. */
5123 GNUNET_assert (NULL !=
5125 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5126 target_friend->congestion_timestamp =
5127 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5128 congestion_timeout);
5130 /* I am the source peer which wants to setup the trail. Do nothing.
5131 * send_find_finger_trail_task is scheduled periodically.*/
5132 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5135 /* If I am congested then pass this message to peer before me in trail. */
5136 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5138 struct GNUNET_PeerIdentity *new_trail;
5139 unsigned int new_trail_length;
5141 /* Remove yourself from the trail setup so far. */
5142 if (trail_length == 1)
5145 new_trail_length = 0;
5150 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5151 sizeof (struct GNUNET_PeerIdentity));
5153 /* Remove myself from the trail. */
5154 new_trail_length = trail_length -1;
5155 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5156 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5159 GNUNET_assert (NULL !=
5161 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5162 GDS_NEIGHBOURS_send_trail_rejection (source,
5163 ultimate_destination_finger_value,
5164 my_identity, is_predecessor,
5165 new_trail,new_trail_length,trail_id,
5166 target_friend, CONGESTION_TIMEOUT);
5167 GNUNET_free (new_trail);
5171 struct Closest_Peer successor;
5172 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5174 /* Am I the final destination? */
5175 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5178 if (0 == trail_length)
5181 next_peer = trail_peer_list[trail_length-1];
5183 GNUNET_assert (NULL !=
5185 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5187 GDS_NEIGHBOURS_send_trail_setup_result (source,
5189 target_friend, trail_length,
5192 ultimate_destination_finger_value,
5197 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5199 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5200 peer_list[trail_length] = my_identity;
5202 GNUNET_assert (NULL !=
5204 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5205 GDS_NEIGHBOURS_send_trail_setup (source,
5206 ultimate_destination_finger_value,
5207 successor.best_known_destination,
5208 target_friend, trail_length + 1, peer_list,
5209 is_predecessor, trail_id,
5210 successor.trail_id);
5217 * Core handler for trail teardown message.
5218 * @param cls closure
5219 * @param message message
5220 * @param peer sender of this messsage.
5221 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5224 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5225 const struct GNUNET_MessageHeader *message)
5227 const struct PeerTrailTearDownMessage *trail_teardown;
5228 enum GDS_ROUTING_trail_direction trail_direction;
5229 struct GNUNET_HashCode trail_id;
5230 struct GNUNET_PeerIdentity *next_hop;
5233 msize = ntohs (message->size);
5235 /* Here we pass only the trail id. */
5236 if (msize != sizeof (struct PeerTrailTearDownMessage))
5238 GNUNET_break_op (0);
5242 GNUNET_STATISTICS_update (GDS_stats,
5244 ("# Bytes received from other peers"), msize,
5247 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5248 trail_direction = ntohl (trail_teardown->trail_direction);
5249 trail_id = trail_teardown->trail_id;
5251 /* Check if peer is the real peer from which we should get this message.*/
5252 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5254 GNUNET_assert (NULL != (prev_hop =
5255 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5256 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5259 return GNUNET_SYSERR;
5263 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5264 if (NULL == next_hop)
5266 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5267 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5269 return GNUNET_SYSERR;
5272 /* I am the next hop, which means I am the final destination. */
5273 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5275 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5280 /* If not final destination, then send a trail teardown message to next hop.*/
5281 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5282 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5283 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5291 * Core handle for p2p add trail message.
5292 * @param cls closure
5293 * @param message message
5294 * @param peer peer identity this notification is about
5295 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5298 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5299 const struct GNUNET_MessageHeader *message)
5301 const struct PeerAddTrailMessage *add_trail;
5302 const struct GNUNET_PeerIdentity *trail;
5303 struct GNUNET_HashCode trail_id;
5304 struct GNUNET_PeerIdentity destination_peer;
5305 struct GNUNET_PeerIdentity source_peer;
5306 struct GNUNET_PeerIdentity next_hop;
5307 unsigned int trail_length;
5308 unsigned int my_index;
5311 msize = ntohs (message->size);
5312 /* In this message we pass the whole trail from source to destination as we
5313 * are adding that trail.*/
5314 //FIXME: failed when run with 1000 pears. check why.
5315 if (msize < sizeof (struct PeerAddTrailMessage))
5317 GNUNET_break_op (0);
5321 add_trail = (const struct PeerAddTrailMessage *) message;
5322 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5323 sizeof (struct GNUNET_PeerIdentity);
5324 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5325 sizeof (struct GNUNET_PeerIdentity) != 0)
5327 GNUNET_break_op (0);
5331 GNUNET_STATISTICS_update (GDS_stats,
5333 ("# Bytes received from other peers"), msize,
5336 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5337 destination_peer = add_trail->destination_peer;
5338 source_peer = add_trail->source_peer;
5339 trail_id = add_trail->trail_id;
5341 //FIXME: add a check that sender peer is not malicious. Make it a generic
5342 // function so that it can be used in all other functions where we need the
5343 // same functionality.
5345 /* I am not the destination of the trail. */
5346 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5348 struct FriendInfo *target_friend;
5350 /* Get my location in the trail. */
5351 my_index = search_my_index (trail, trail_length);
5354 GNUNET_break_op (0);
5355 return GNUNET_SYSERR;
5357 if((trail_length + 1) == my_index)
5359 DEBUG ("Found twice in trail.\n");
5360 GNUNET_break_op (0);
5361 return GNUNET_SYSERR;
5363 if ((trail_length - 1) == my_index)
5365 next_hop = destination_peer;
5369 next_hop = trail[my_index + 1];
5371 /* Add in your routing table. */
5372 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5373 GNUNET_assert (NULL !=
5375 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5376 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5377 trail, trail_length, target_friend);
5380 /* I am the destination. Add an entry in routing table. */
5381 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5387 * Free the finger trail in which the first friend to reach to a finger is
5388 * disconnected_friend. Also remove entry from routing table for that particular
5390 * @param disconnected_friend PeerIdentity of friend which got disconnected
5391 * @param remove_finger Finger whose trail we need to check if it has
5392 * disconnected_friend as the first hop.
5393 * @return Total number of trails in which disconnected_friend was the first
5397 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5398 struct FingerInfo *finger)
5400 unsigned int matching_trails_count = 0;
5403 /* Iterate over all the trails of finger. */
5404 for (i = 0; i < finger->trails_count; i++)
5406 struct Trail *current_trail;
5407 current_trail = &finger->trail_list[i];
5408 //FIXME: This assertion fails if we have gap in trail list from o to trails count.
5409 GNUNET_assert (GNUNET_YES == current_trail->is_present);
5410 /* First friend to reach to finger is disconnected_peer. */
5411 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5412 disconnected_friend))
5414 struct GNUNET_PeerIdentity *next_hop;
5415 struct FriendInfo *remove_friend;
5417 GNUNET_assert (NULL !=
5419 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5420 disconnected_friend)));
5421 next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id,
5422 GDS_ROUTING_SRC_TO_DEST);
5424 /* Here it may happen that as all the peers got disconnected, the entry in
5425 routing table for that particular trail has been removed, because the
5426 previously disconnected peer was either a next hop or prev hop of that
5428 if (NULL != next_hop)
5430 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5432 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id));
5434 matching_trails_count++;
5435 free_trail (current_trail);
5436 current_trail->is_present = GNUNET_NO;
5439 return matching_trails_count;
5445 * Iterate over finger_table entries.
5446 * 0. Ignore finger which is my_identity or if no valid entry present at
5447 * that finger index.
5448 * 1. If disconnected_friend is a finger, then remove the routing entry from
5449 your own table. Free the trail.
5450 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5451 * 2.1 Remove all the trails and entry from routing table in which disconnected
5452 * friend is the first friend in the trail. If disconnected_friend is the
5453 * first friend in all the trails to reach finger, then remove the finger.
5454 * @param disconnected_friend Peer identity of friend which got disconnected.
5457 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5459 struct FingerInfo *current_finger;
5460 struct FriendInfo *remove_friend;
5461 int removed_trails_count;
5464 /* Iterate over finger table entries. */
5465 for (i = 0; i < MAX_FINGERS; i++)
5467 current_finger = &finger_table[i];
5469 /* No finger stored at this trail index. */
5470 if ((GNUNET_NO == current_finger->is_present) ||
5471 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5475 /* Is disconnected_peer a finger? */
5476 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5477 ¤t_finger->finger_identity))
5479 struct GNUNET_PeerIdentity *next_hop;
5480 struct GNUNET_HashCode trail_id;
5482 GNUNET_assert (0 == current_finger->trail_list[0].trail_length);
5483 GNUNET_assert (GNUNET_YES == (current_finger->trail_list[0].is_present));
5484 trail_id = current_finger->trail_list[0].trail_id;
5488 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5491 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5492 ¤t_finger->finger_identity)));
5493 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5494 GNUNET_assert (NULL !=
5496 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5497 disconnected_peer)));
5499 current_finger->trail_list[0].is_present = GNUNET_NO;
5500 current_finger->is_present = GNUNET_NO;
5501 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5505 /* If finger is a friend but not disconnected_friend, then continue. */
5506 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5507 ¤t_finger->finger_identity))
5510 /* Iterate over the list of trails to reach remove_finger. Check if
5511 * disconnected_friend is the first friend in any of the trail. */
5512 removed_trails_count = remove_matching_trails (disconnected_peer,
5514 current_finger->trails_count =
5515 current_finger->trails_count - removed_trails_count;
5516 if (0 == current_finger->trails_count)
5518 current_finger->is_present = GNUNET_NO;
5519 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5526 * Method called whenever a peer disconnects.
5528 * @param cls closure
5529 * @param peer peer identity this notification is about
5532 handle_core_disconnect (void *cls,
5533 const struct GNUNET_PeerIdentity *peer)
5535 struct FriendInfo *remove_friend;
5536 struct P2PPendingMessage *pos;
5537 unsigned int discarded;
5539 /* If disconnected to own identity, then return. */
5540 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5543 if(NULL == (remove_friend =
5544 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
5546 DEBUG("\n friend already disconnected.");
5550 remove_matching_fingers (peer);
5551 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5552 GNUNET_assert (GNUNET_YES ==
5553 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5557 /* Remove all the messages queued in pending list of this peer is discarded.*/
5558 if (remove_friend->th != NULL)
5560 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
5561 remove_friend->th = NULL;
5565 while (NULL != (pos = remove_friend->head))
5567 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
5572 GNUNET_STATISTICS_update (GDS_stats,
5574 ("# Queued messages discarded (peer disconnected)"),
5575 discarded, GNUNET_NO);
5576 //GNUNET_free (remove_friend);
5578 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5581 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5583 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5584 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5592 * Method called whenever a peer connects.
5594 * @param cls closure
5595 * @param peer_identity peer identity this notification is about
5598 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5600 struct FriendInfo *friend;
5602 /* Check for connect to self message */
5603 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5606 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5608 /* If peer already exists in our friend_peermap, then exit. */
5609 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5616 friend = GNUNET_new (struct FriendInfo);
5617 friend->id = *peer_identity;
5618 friend->congestion_timestamp = GNUNET_TIME_relative_to_absolute(GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MILLISECONDS, 50));
5619 GNUNET_assert (GNUNET_OK ==
5620 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5621 peer_identity, friend,
5622 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5624 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5625 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5627 // find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5628 find_finger_trail_task = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MILLISECONDS, 60),
5629 &send_find_finger_trail_message, NULL);
5635 * To be called on core init/fail.
5637 * @param cls service closure
5638 * @param identity the public identity of this peer
5641 core_init (void *cls,
5642 const struct GNUNET_PeerIdentity *identity)
5644 my_identity = *identity;
5647 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5648 my_id64 = GNUNET_ntohll (my_id64);
5649 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5650 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5656 * Initialize finger table entries.
5659 finger_table_init ()
5661 memset (&finger_table, 0, sizeof (finger_table));
5666 * Initialize neighbours subsystem.
5667 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5670 GDS_NEIGHBOURS_init (void)
5672 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5673 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5674 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5675 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5676 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5677 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5678 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5679 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5680 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5681 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5682 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5683 sizeof (struct PeerTrailTearDownMessage)},
5684 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5688 #if ENABLE_MALICIOUS
5693 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5694 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5695 GNUNET_NO, core_handlers);
5697 if (NULL == core_api)
5698 return GNUNET_SYSERR;
5700 //TODO: check size of this peer map?
5701 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5702 finger_table_init ();
5704 find_finger_trail_task_next_send_time.rel_value_us =
5705 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5706 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5707 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5709 verify_successor_next_send_time.rel_value_us =
5710 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5711 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5712 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5718 * Free the memory held up by trails of a finger.
5721 delete_finger_table_entries()
5726 for(i = 0; i < MAX_FINGERS; i++)
5728 if(GNUNET_NO == finger_table[i].is_present)
5731 for(j = 0; j < finger_table[i].trails_count; j++)
5733 free_trail(&finger_table[i].trail_list[i]);
5739 * Shutdown neighbours subsystem.
5742 GDS_NEIGHBOURS_done (void)
5744 if (NULL == core_api)
5747 GNUNET_CORE_disconnect (core_api);
5750 delete_finger_table_entries();
5752 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5753 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5754 friend_peermap = NULL;
5756 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5759 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5760 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5763 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5765 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5766 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5774 * @return my identity
5776 struct GNUNET_PeerIdentity
5777 GDS_NEIGHBOURS_get_my_id (void)
5782 /* end of gnunet-service-xdht_neighbours.c */