2 This file is part of GNUnet.
3 (C) 2009-2014 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file dht/gnunet-service-xdht_neighbours.c
23 * @brief GNUnet DHT service's finger and friend table management code
24 * @author Supriti Singh
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_ats_service.h"
34 #include "gnunet_core_service.h"
35 #include "gnunet_datacache_lib.h"
36 #include "gnunet_transport_service.h"
37 #include "gnunet_dht_service.h"
38 #include "gnunet_statistics_service.h"
39 #include "gnunet-service-xdht.h"
40 #include "gnunet-service-xdht_clients.h"
41 #include "gnunet-service-xdht_datacache.h"
42 #include "gnunet-service-xdht_neighbours.h"
43 #include "gnunet-service-xdht_routing.h"
49 * 1. In X-Vine paper, there is no policy defined for replicating the data to
50 * recover in case of peer failure. We can do it in Chord way. In R5N, the key
51 * is hashed and then data is stored according to the key value generated after
58 * We should have a message type like notify successor result. only when
59 * this message is being recvied by the new successor. we should schedule
60 * another round of verify successor.
63 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
66 * Maximum possible fingers (including predecessor) of a peer
68 #define MAX_FINGERS 65
71 * Maximum allowed number of pending messages per friend peer.
73 #define MAXIMUM_PENDING_PER_FRIEND 64
76 * How long to wait before sending another find finger trail request
78 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
81 * How long to wait before sending another verify successor message.
83 #define DHT_SEND_VERIFY_SUCCESSOR_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
86 * How long to wait before sending another verify successor message.
88 #define DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
91 * How long to wait before retrying notify successor.
93 #define DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
96 * How long at most to wait for transmission of a request to a friend ?
98 #define PENDING_MESSAGE_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
101 * Duration for which I may remain congested.
102 * Note: Its a static value. In future, a peer may do some analysis and calculate
103 * congestion_timeout based on 'some' parameters.
105 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
108 * In case we don't hear back from the current successor, then we can start
111 #define WAIT_NOTIFY_CONFIRMATION GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 200)
114 * Maximum number of trails allowed to go through a friend.
116 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
119 * Maximum number of trails stored per finger.
121 #define MAXIMUM_TRAILS_PER_FINGER 1
124 * Finger map index for predecessor entry in finger table.
126 #define PREDECESSOR_FINGER_ID 64
129 * FIXME: Its use only at 3 places check if you can remove it.
130 * To check if a finger is predecessor or not.
132 enum GDS_NEIGHBOURS_finger_type
134 GDS_FINGER_TYPE_PREDECESSOR = 1,
135 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
138 GNUNET_NETWORK_STRUCT_BEGIN
143 struct PeerPutMessage
146 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
148 struct GNUNET_MessageHeader header;
153 uint32_t options GNUNET_PACKED;
158 uint32_t block_type GNUNET_PACKED;
163 uint32_t hop_count GNUNET_PACKED;
166 * Replication level for this message
167 * In the current implementation, this value is not used.
169 uint32_t desired_replication_level GNUNET_PACKED;
172 * Length of the PUT path that follows (if tracked).
174 uint32_t put_path_length GNUNET_PACKED;
177 * Best known destination (could be my friend or finger) which should
178 * get this message next.
180 struct GNUNET_PeerIdentity best_known_destination;
183 * In case best_known_destination is a finger, then trail to reach
184 * to that finger. Else its default value is 0.
186 struct GNUNET_HashCode intermediate_trail_id;
189 * When does the content expire?
191 struct GNUNET_TIME_AbsoluteNBO expiration_time;
194 * The key to store the value under.
196 struct GNUNET_HashCode key GNUNET_PACKED;
198 /* put path (if tracked) */
207 struct PeerGetMessage
210 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
212 struct GNUNET_MessageHeader header;
217 uint32_t options GNUNET_PACKED;
220 * Desired content type.
222 uint32_t block_type GNUNET_PACKED;
227 uint32_t hop_count GNUNET_PACKED;
230 * Desired replication level for this request.
231 * In the current implementation, this value is not used.
233 uint32_t desired_replication_level GNUNET_PACKED;
236 * Total number of peers in get path.
238 unsigned int get_path_length;
241 * Best known destination (could be my friend or finger) which should
242 * get this message next.
244 struct GNUNET_PeerIdentity best_known_destination;
247 * In case best_known_destination is a finger, then trail to reach
248 * to that finger. Else its default value is 0.
250 struct GNUNET_HashCode intermediate_trail_id;
253 * The key we are looking for.
255 struct GNUNET_HashCode key;
258 /* struct GNUNET_PeerIdentity[]*/
264 struct PeerGetResultMessage
267 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
269 struct GNUNET_MessageHeader header;
272 * The type for the data.
274 uint32_t type GNUNET_PACKED;
277 * Number of peers recorded in the outgoing path from source to the
278 * stored location of this message.
280 uint32_t put_path_length GNUNET_PACKED;
283 * Length of the GET path that follows (if tracked).
285 uint32_t get_path_length GNUNET_PACKED;
288 * Peer which queried for get and should get the result.
290 struct GNUNET_PeerIdentity querying_peer;
293 * When does the content expire?
295 struct GNUNET_TIME_Absolute expiration_time;
298 * The key of the corresponding GET request.
300 struct GNUNET_HashCode key;
302 /* put path (if tracked) */
304 /* get path (if tracked) */
311 * P2P Trail setup message
313 struct PeerTrailSetupMessage
316 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
318 struct GNUNET_MessageHeader header;
321 * Is source_peer trying to setup the trail to a predecessor or any finger.
323 uint32_t is_predecessor;
326 * Peer closest to this value will be our finger.
328 uint64_t final_destination_finger_value;
331 * Source peer which wants to setup the trail to one of its finger.
333 struct GNUNET_PeerIdentity source_peer;
336 * Best known destination (could be my friend or finger) which should
337 * get this message next.
339 * FIXME: this could be removed if we include trail_source / trail_dest
340 * in the routing table. This way we save 32 bytes of bandwidth by using
341 * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID))
343 struct GNUNET_PeerIdentity best_known_destination;
346 * In case best_known_destination is a finger, then trail id of trail to
347 * reach to this finger.
349 struct GNUNET_HashCode intermediate_trail_id;
352 * Trail id for trail which we are trying to setup.
354 struct GNUNET_HashCode trail_id;
356 /* List of peers which are part of trail setup so far.
357 * Trail does NOT include source_peer and peer which will be closest to
358 * ultimate_destination_finger_value.
359 * struct GNUNET_PeerIdentity trail[]
364 * P2P Trail Setup Result message
366 struct PeerTrailSetupResultMessage
370 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
372 struct GNUNET_MessageHeader header;
375 * Finger to which we have found the path.
377 struct GNUNET_PeerIdentity finger_identity;
380 * Peer which started trail_setup to find trail to finger_identity
382 struct GNUNET_PeerIdentity querying_peer;
385 * Is the trail setup to querying_peer's predecessor or finger?
387 uint32_t is_predecessor;
390 * Value to which finger_identity is the closest peer.
392 uint64_t ulitmate_destination_finger_value;
395 * Identifier of the trail from querying peer to finger_identity, NOT
396 * including both endpoints.
398 struct GNUNET_HashCode trail_id;
400 /* List of peers which are part of the trail from querying peer to
401 * finger_identity, NOT including both endpoints.
402 * struct GNUNET_PeerIdentity trail[]
407 * P2P Verify Successor Message.
409 struct PeerVerifySuccessorMessage
412 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
414 struct GNUNET_MessageHeader header;
417 * Peer which wants to verify its successor.
419 struct GNUNET_PeerIdentity source_peer;
422 * Source Peer's current successor.
424 struct GNUNET_PeerIdentity successor;
427 * Identifier of trail to reach from source_peer to successor.
429 struct GNUNET_HashCode trail_id;
431 /* List of the peers which are part of trail to reach from source_peer
432 * to successor, NOT including them
433 * struct GNUNET_PeerIdentity trail[]
438 * P2P Verify Successor Result Message
440 struct PeerVerifySuccessorResultMessage
443 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
445 struct GNUNET_MessageHeader header;
448 * Peer which sent the request to verify its successor.
450 struct GNUNET_PeerIdentity querying_peer;
453 * Successor to which PeerVerifySuccessorMessage was sent.
455 struct GNUNET_PeerIdentity current_successor;
458 * Current Predecessor of source_successor. It can be same as querying peer
459 * or different. In case it is different then it can be querying_peer's
460 * probable successor.
462 struct GNUNET_PeerIdentity probable_successor;
465 * Trail identifier of trail from querying_peer to current_successor.
467 struct GNUNET_HashCode trail_id;
470 * Direction in which we are looking at the trail.
472 uint32_t trail_direction;
474 /* In case probable_successor != querying_peer, then trail to reach from
475 * querying_peer to probable_successor, NOT including end points.
476 * struct GNUNET_PeerIdentity trail[]
481 * P2P Notify New Successor Message.
483 struct PeerNotifyNewSuccessorMessage
486 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
488 struct GNUNET_MessageHeader header;
491 * Peer which wants to notify its new successor.
493 struct GNUNET_PeerIdentity source_peer;
496 * New successor of source_peer.
498 struct GNUNET_PeerIdentity new_successor;
501 * Unique identifier of the trail from source_peer to new_successor,
502 * NOT including the endpoints.
504 struct GNUNET_HashCode trail_id;
506 /* List of peers in trail from source_peer to new_successor,
507 * NOT including the endpoints.
508 * struct GNUNET_PeerIdentity trail[]
513 * P2P Notify Successor Confirmation message.
515 struct PeerNotifyConfirmationMessage
518 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
520 struct GNUNET_MessageHeader header;
523 * Unique identifier of the trail.
525 struct GNUNET_HashCode trail_id;
528 * Direction of trail.
530 uint32_t trail_direction;
535 * P2P Trail Tear Down message.
537 struct PeerTrailTearDownMessage
540 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
542 struct GNUNET_MessageHeader header;
545 * Unique identifier of the trail.
547 struct GNUNET_HashCode trail_id;
550 * Direction of trail.
552 uint32_t trail_direction;
557 * P2P Trail Rejection Message.
559 struct PeerTrailRejectionMessage
562 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
564 struct GNUNET_MessageHeader header;
567 * Peer which wants to set up the trail.
569 struct GNUNET_PeerIdentity source_peer;
572 * Peer which sent trail rejection message as it it congested.
574 struct GNUNET_PeerIdentity congested_peer;
577 * Peer identity closest to this value will be finger of
580 uint64_t ultimate_destination_finger_value;
583 * Is source_peer trying to setup the trail to its predecessor or finger.
585 uint32_t is_predecessor;
588 * Identifier for the trail that source peer is trying to setup.
590 struct GNUNET_HashCode trail_id;
593 * Relative time for which congested_peer will remain congested.
595 struct GNUNET_TIME_Relative congestion_time;
597 /* Trail_list from source_peer to peer which sent the message for trail setup
598 * to congested peer. This trail does NOT include source_peer.
599 struct GNUNET_PeerIdnetity trail[]*/
603 * P2P Add Trail Message.
605 struct PeerAddTrailMessage
608 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
610 struct GNUNET_MessageHeader header;
613 * Source of the routing trail.
615 struct GNUNET_PeerIdentity source_peer;
618 * Destination of the routing trail.
620 struct GNUNET_PeerIdentity destination_peer;
623 * Unique identifier of the trail from source_peer to destination_peer,
624 * NOT including the endpoints.
626 struct GNUNET_HashCode trail_id;
628 /* Trail from source peer to destination peer, NOT including them.
629 * struct GNUNET_PeerIdentity trail[]
633 GNUNET_NETWORK_STRUCT_END
636 * Linked list of messages to send to a particular other peer.
638 struct P2PPendingMessage
641 * Pointer to next item in the list
643 struct P2PPendingMessage *next;
646 * Pointer to previous item in the list
648 struct P2PPendingMessage *prev;
651 * Message importance level. FIXME: used? useful?
653 unsigned int importance;
656 * When does this message time out?
658 struct GNUNET_TIME_Absolute timeout;
661 * Actual message to be sent, allocated at the end of the struct:
662 * // msg = (cast) &pm[1];
663 * // memcpy (&pm[1], data, len);
665 const struct GNUNET_MessageHeader *msg;
670 * Entry in friend_peermap.
677 struct GNUNET_PeerIdentity id;
680 * Number of trails for which this friend is the first hop or if the friend
683 unsigned int trails_count;
686 * Count of outstanding messages for this friend.
688 unsigned int pending_count;
691 * In case not 0, then amount of time for which this friend is congested.
693 struct GNUNET_TIME_Absolute congestion_timestamp;
696 // TODO : Change name of head and tail to pending_messages_list_head and so.
698 * Head of pending messages to be sent to this friend.
700 struct P2PPendingMessage *head;
703 * Tail of pending messages to be sent to this friend.
705 struct P2PPendingMessage *tail;
708 * Core handle for sending messages to this friend.
710 struct GNUNET_CORE_TransmitHandle *th;
715 * An individual element of the trail to reach to a finger.
720 * Pointer to next item in the list
722 struct Trail_Element *next;
725 * Pointer to prev item in the list
727 struct Trail_Element *prev;
730 * An element in this trail.
732 struct GNUNET_PeerIdentity peer;
736 * Information about an individual trail.
743 struct Trail_Element *trail_head;
748 struct Trail_Element *trail_tail;
751 * Unique identifier of this trail.
753 struct GNUNET_HashCode trail_id;
756 * Length of trail pointed
758 unsigned int trail_length;
761 * Is there a valid trail entry.
763 unsigned int is_present;
767 * An entry in finger_table
774 struct GNUNET_PeerIdentity finger_identity;
777 * In case not 0, this amount is time to wait for notify successor message.
778 * Used ONLY for successor. NOT for any other finger.
780 struct GNUNET_TIME_Absolute wait_notify_confirmation;
783 * Is any finger stored at this finger index.
785 unsigned int is_present;
788 * Index in finger peer map
790 uint32_t finger_table_index;
793 * Number of trails setup so far for this finger.
794 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
796 uint32_t trails_count;
799 * Array of trails to reach to this finger.
801 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
806 * Stores information about the peer which is closest to destination_finger_value.
807 * 'closest' can be either successor or predecessor depending on is_predecessor
813 * Destination finger value.
815 uint64_t destination_finger_value;
818 * Is finger_value a predecessor or any other finger.
820 unsigned int is_predecessor;
823 * Trail id to reach to peer.
824 * In case peer is my identity or friend, it is set to 0.
826 struct GNUNET_HashCode trail_id;
829 * Next destination. In case of friend and my_identity , it is same as next_hop
830 * In case of finger it is finger identity.
832 struct GNUNET_PeerIdentity best_known_destination;
835 * In case best_known_destination is a finger, then first friend in the trail
836 * to reach to it. In other case, same as best_known_destination.
838 struct GNUNET_PeerIdentity next_hop;
841 * In case finger is the next hop, it contains a valid finger table index
842 * at which the finger is stored. Else, It contains 65, which is out of range
843 * of finger table index.
845 unsigned int finger_table_index;
849 * Context for send_verify_successor_task.
851 struct VerifySuccessorContext
854 * Number of times this has been scheduled.
856 unsigned int num_retries_scheduled;
860 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
861 * get our first friend.
863 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
866 * Task that sends verify successor message. This task is started when we get
867 * our successor for the first time.
869 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_task;
872 * Task that sends verify successor message. This task is started when we get
873 * our successor for the first time.
875 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_retry_task;
878 * Task that sends verify successor message. This task is started when we get
879 * our successor for the first time.
881 static GNUNET_SCHEDULER_TaskIdentifier send_notify_new_successor_retry_task;
884 * Identity of this peer.
886 static struct GNUNET_PeerIdentity my_identity;
889 * Peer map of all the friends of a peer
891 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
894 * Array of all the fingers.
896 static struct FingerInfo finger_table [MAX_FINGERS];
901 static struct GNUNET_CORE_Handle *core_api;
904 * Handle for the statistics service.
906 //extern struct GNUNET_STATISTICS_Handle *GDS_stats;
909 * The current finger index that we have want to find trail to. We start the
910 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
911 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
912 * we reset this index to 0.
914 static unsigned int current_search_finger_index;
917 * Time duration to schedule find finger trail task.
919 static struct GNUNET_TIME_Relative find_finger_trail_task_next_send_time;
922 * Time duration to schedule verify successor task.
924 static struct GNUNET_TIME_Relative verify_successor_next_send_time;
927 * Time duration to send verify successor again, if result was not received in time.
929 static struct GNUNET_TIME_Relative verify_successor_retry_time;
932 * Time duration to retry send_notify_successor.
934 static struct GNUNET_TIME_Relative notify_successor_retry_time;
937 * Are we waiting for confirmation from our new successor that it got the
940 //static unsigned int waiting_for_notify_confirmation;
942 /* Below variables are used only for testing, and statistics collection. */
944 * Should we store our topology predecessor and successor IDs into statistics?
946 unsigned int track_topology;
949 * Should I be a malicious peer and drop the PUT/GET packets?
950 * if 0 then NOT malicious.
952 unsigned int act_malicious;
955 * Count of fingers found. Ideally we should have O(logn) fingers for a
958 static unsigned int total_fingers_found;
961 * Number of times we found the same successor.
963 static unsigned int successor_times;
966 * Called when core is ready to send a message we asked for
967 * out to the destination.
969 * @param cls the 'struct FriendInfo' of the target friend
970 * @param size number of bytes available in buf
971 * @param buf where the callee should write the message
972 * @return number of bytes written to buf
975 core_transmit_notify (void *cls, size_t size, void *buf)
977 struct FriendInfo *peer = cls;
979 struct P2PPendingMessage *pending;
984 while ((NULL != (pending = peer->head)) &&
985 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
987 peer->pending_count--;
988 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
989 GNUNET_free (pending);
993 /* no messages pending */
999 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1000 GNUNET_CORE_PRIO_BEST_EFFORT,
1001 GNUNET_TIME_absolute_get_remaining
1002 (pending->timeout), &peer->id,
1003 ntohs (pending->msg->size),
1004 &core_transmit_notify, peer);
1005 GNUNET_break (NULL != peer->th);
1009 while ((NULL != (pending = peer->head)) &&
1010 (size - off >= (msize = ntohs (pending->msg->size))))
1012 GNUNET_STATISTICS_update (GDS_stats,
1014 ("# Bytes transmitted to other peers"), msize,
1016 memcpy (&cbuf[off], pending->msg, msize);
1018 peer->pending_count--;
1019 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1020 GNUNET_free (pending);
1022 if (peer->head != NULL)
1025 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1026 GNUNET_CORE_PRIO_BEST_EFFORT,
1027 GNUNET_TIME_absolute_get_remaining
1028 (pending->timeout), &peer->id, msize,
1029 &core_transmit_notify, peer);
1030 GNUNET_break (NULL != peer->th);
1037 * Transmit all messages in the friend's message queue.
1039 * @param peer message queue to process
1042 process_friend_queue (struct FriendInfo *peer)
1044 struct P2PPendingMessage *pending;
1046 if (NULL == (pending = peer->head))
1050 if (NULL != peer->th)
1056 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1057 pending->importance,
1058 GNUNET_TIME_absolute_get_remaining
1059 (pending->timeout), &peer->id,
1060 ntohs (pending->msg->size),
1061 &core_transmit_notify, peer);
1062 GNUNET_break (NULL != peer->th);
1066 #if ENABLE_MALICIOUS
1068 * Set the ENABLE_MALICIOUS value to malicious.
1072 GDS_NEIGHBOURS_act_malicious (unsigned int malicious)
1074 act_malicious = malicious;
1079 * Construct a trail setup message and forward it to target_friend
1080 * @param source_peer Peer which wants to setup the trail
1081 * @param ultimate_destination_finger_value Peer identity closest to this value
1082 * will be finger to @a source_peer
1083 * @param best_known_destination Best known destination (could be finger or friend)
1084 * which should get this message. In case it is
1085 * friend, then it is same as target_friend
1086 * @param target_friend Friend to which message is forwarded now.
1087 * @param trail_length Total number of peers in trail setup so far.
1088 * @param trail_peer_list Trail setup so far
1089 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1090 * @param trail_id Unique identifier for the trail we are trying to setup.
1091 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1092 * best_known_destination when its a finger. If not
1093 * used then set to 0.
1096 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1097 uint64_t ultimate_destination_finger_value,
1098 struct GNUNET_PeerIdentity best_known_destination,
1099 struct FriendInfo *target_friend,
1100 unsigned int trail_length,
1101 const struct GNUNET_PeerIdentity *trail_peer_list,
1102 unsigned int is_predecessor,
1103 struct GNUNET_HashCode trail_id,
1104 struct GNUNET_HashCode intermediate_trail_id)
1106 struct P2PPendingMessage *pending;
1107 struct PeerTrailSetupMessage *tsm;
1108 struct GNUNET_PeerIdentity *peer_list;
1111 msize = sizeof (struct PeerTrailSetupMessage) +
1112 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1114 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1120 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1122 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1125 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1126 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1127 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1128 pending->msg = &(tsm->header);
1129 tsm->header.size = htons (msize);
1130 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1131 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1132 tsm->source_peer = source_peer;
1133 tsm->best_known_destination = best_known_destination;
1134 tsm->is_predecessor = htonl (is_predecessor);
1135 tsm->trail_id = trail_id;
1136 tsm->intermediate_trail_id = intermediate_trail_id;
1138 if (trail_length > 0)
1140 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1141 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1144 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1145 target_friend->pending_count++;
1146 process_friend_queue (target_friend);
1151 * Construct a trail setup result message and forward it to target friend.
1152 * @param querying_peer Peer which sent the trail setup request and should get
1154 * @param Finger Peer to which the trail has been setup to.
1155 * @param target_friend Friend to which this message should be forwarded.
1156 * @param trail_length Numbers of peers in the trail.
1157 * @param trail_peer_list Peers which are part of the trail from
1158 * querying_peer to Finger, NOT including them.
1159 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1160 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1162 * @param trail_id Unique identifier of the trail.
1165 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1166 struct GNUNET_PeerIdentity finger,
1167 struct FriendInfo *target_friend,
1168 unsigned int trail_length,
1169 const struct GNUNET_PeerIdentity *trail_peer_list,
1170 unsigned int is_predecessor,
1171 uint64_t ultimate_destination_finger_value,
1172 struct GNUNET_HashCode trail_id)
1174 struct P2PPendingMessage *pending;
1175 struct PeerTrailSetupResultMessage *tsrm;
1176 struct GNUNET_PeerIdentity *peer_list;
1179 msize = sizeof (struct PeerTrailSetupResultMessage) +
1180 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1182 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1188 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1190 GNUNET_STATISTICS_update (GDS_stats,
1191 gettext_noop ("# P2P messages dropped due to full queue"),
1195 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1196 pending->importance = 0;
1197 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1198 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1199 pending->msg = &tsrm->header;
1200 tsrm->header.size = htons (msize);
1201 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1202 tsrm->querying_peer = querying_peer;
1203 tsrm->finger_identity = finger;
1204 tsrm->is_predecessor = htonl (is_predecessor);
1205 tsrm->trail_id = trail_id;
1206 tsrm->ulitmate_destination_finger_value =
1207 GNUNET_htonll (ultimate_destination_finger_value);
1208 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1209 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1211 /* Send the message to chosen friend. */
1212 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1213 target_friend->pending_count++;
1214 process_friend_queue (target_friend);
1218 * Send notify successor confirmation message.
1219 * @param trail_id Unique Identifier of the trail.
1220 * @param trail_direction Destination to Source.
1221 * @param target_friend Friend to get this message next.
1224 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (struct GNUNET_HashCode trail_id,
1225 unsigned int trail_direction,
1226 struct FriendInfo *target_friend)
1228 struct PeerNotifyConfirmationMessage *ncm;
1229 struct P2PPendingMessage *pending;
1232 msize = sizeof (struct PeerNotifyConfirmationMessage);
1233 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1239 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1241 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1245 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1246 pending->importance = 0; /* FIXME */
1247 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1248 ncm = (struct PeerNotifyConfirmationMessage *) &pending[1];
1249 pending->msg = &ncm->header;
1250 ncm->header.size = htons (msize);
1251 ncm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION);
1252 ncm->trail_id = trail_id;
1253 ncm->trail_direction = htonl (trail_direction);
1255 /* Send the message to chosen friend. */
1256 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1257 target_friend->pending_count++;
1258 process_friend_queue (target_friend);
1263 * Send trail rejection message to target friend
1264 * @param source_peer Peer which is trying to setup the trail.
1265 * @param ultimate_destination_finger_value Peer closest to this value will be
1266 * @a source_peer's finger
1267 * @param congested_peer Peer which sent this message as it is congested.
1268 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1269 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1270 * by congested_peer. This does NOT include @a source_peer
1271 * and congested_peer.
1272 * @param trail_length Total number of peers in trail_peer_list, NOT including
1273 * @a source_peer and @a congested_peer
1274 * @param trail_id Unique identifier of this trail.
1275 * @param congestion_timeout Duration given by congested peer as an estimate of
1276 * how long it may remain congested.
1279 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1280 uint64_t ultimate_destination_finger_value,
1281 struct GNUNET_PeerIdentity congested_peer,
1282 unsigned int is_predecessor,
1283 const struct GNUNET_PeerIdentity *trail_peer_list,
1284 unsigned int trail_length,
1285 struct GNUNET_HashCode trail_id,
1286 struct FriendInfo *target_friend,
1287 const struct GNUNET_TIME_Relative congestion_timeout)
1289 struct PeerTrailRejectionMessage *trm;
1290 struct P2PPendingMessage *pending;
1291 struct GNUNET_PeerIdentity *peer_list;
1294 msize = sizeof (struct PeerTrailRejectionMessage) +
1295 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1297 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1303 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1305 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1309 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1310 pending->importance = 0;
1311 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1312 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1313 pending->msg = &trm->header;
1314 trm->header.size = htons (msize);
1315 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1316 trm->source_peer = source_peer;
1317 trm->congested_peer = congested_peer;
1318 trm->congestion_time = congestion_timeout;
1319 trm->is_predecessor = htonl (is_predecessor);
1320 trm->trail_id = trail_id;
1321 trm->ultimate_destination_finger_value =
1322 GNUNET_htonll (ultimate_destination_finger_value);
1324 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1325 if (trail_length > 0)
1327 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1330 /* Send the message to chosen friend. */
1331 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1332 target_friend->pending_count++;
1333 process_friend_queue (target_friend);
1338 * Construct a verify successor message and forward it to target_friend.
1339 * @param source_peer Peer which wants to verify its successor.
1340 * @param successor Peer which is @a source_peer's current successor.
1341 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1342 * NOT including them.
1343 * @param trail List of peers which are part of trail to reach from @a source_peer
1344 * to @a successor, NOT including them.
1345 * @param trail_length Total number of peers in @a trail.
1346 * @param target_friend Next friend to get this message.
1349 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1350 struct GNUNET_PeerIdentity successor,
1351 struct GNUNET_HashCode trail_id,
1352 struct GNUNET_PeerIdentity *trail,
1353 unsigned int trail_length,
1354 struct FriendInfo *target_friend)
1356 struct PeerVerifySuccessorMessage *vsm;
1357 struct P2PPendingMessage *pending;
1358 struct GNUNET_PeerIdentity *peer_list;
1361 msize = sizeof (struct PeerVerifySuccessorMessage) +
1362 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1364 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1370 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1372 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1376 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1377 pending->importance = 0; /* FIXME */
1378 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1379 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1380 pending->msg = &vsm->header;
1381 vsm->header.size = htons (msize);
1382 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1383 vsm->source_peer = source_peer;
1384 vsm->successor = successor;
1385 vsm->trail_id = trail_id;
1386 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1387 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1389 /* Send the message to chosen friend. */
1390 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1391 target_friend->pending_count++;
1392 process_friend_queue (target_friend);
1397 * FIXME: In every function we pass target friend except for this one.
1398 * so, either change everything or this one. also, should se just store
1399 * the pointer to friend in routing table rather than gnunet_peeridentity.
1400 * if yes then we should keep friend info in.h andmake lot of changes.
1401 * Construct a trail teardown message and forward it to target friend.
1402 * @param trail_id Unique identifier of the trail.
1403 * @param trail_direction Direction of trail.
1404 * @param target_friend Friend to get this message.
1407 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1408 unsigned int trail_direction,
1409 struct GNUNET_PeerIdentity peer)
1411 struct PeerTrailTearDownMessage *ttdm;
1412 struct P2PPendingMessage *pending;
1413 struct FriendInfo *target_friend;
1416 msize = sizeof (struct PeerTrailTearDownMessage);
1418 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1424 /*FIXME:In what case friend can be null. ?*/
1425 if (NULL == (target_friend =
1426 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1429 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1431 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1435 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1436 pending->importance = 0; /* FIXME */
1437 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1438 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1439 pending->msg = &ttdm->header;
1440 ttdm->header.size = htons (msize);
1441 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1442 ttdm->trail_id = trail_id;
1443 ttdm->trail_direction = htonl (trail_direction);
1445 /* Send the message to chosen friend. */
1446 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1447 target_friend->pending_count++;
1448 process_friend_queue (target_friend);
1453 * Construct a verify successor result message and send it to target_friend
1454 * @param querying_peer Peer which sent the verify successor message.
1455 * @param source_successor Current_successor of @a querying_peer.
1456 * @param current_predecessor Current predecessor of @a successor. Could be same
1457 * or different from @a querying_peer.
1458 * @param trail_id Unique identifier of the trail from @a querying_peer to
1459 * @a successor, NOT including them.
1460 * @param trail List of peers which are part of trail from @a querying_peer to
1461 * @a successor, NOT including them.
1462 * @param trail_length Total number of peers in @a trail
1463 * @param trail_direction Direction in which we are sending the message. In this
1464 * case we are sending result from @a successor to @a querying_peer.
1465 * @param target_friend Next friend to get this message.
1468 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1469 struct GNUNET_PeerIdentity current_successor,
1470 struct GNUNET_PeerIdentity probable_successor,
1471 struct GNUNET_HashCode trail_id,
1472 const struct GNUNET_PeerIdentity *trail,
1473 unsigned int trail_length,
1474 enum GDS_ROUTING_trail_direction trail_direction,
1475 struct FriendInfo *target_friend)
1477 struct PeerVerifySuccessorResultMessage *vsmr;
1478 struct P2PPendingMessage *pending;
1479 struct GNUNET_PeerIdentity *peer_list;
1482 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1483 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1485 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1491 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1493 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1497 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1498 pending->importance = 0; /* FIXME */
1499 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1500 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1501 pending->msg = &vsmr->header;
1502 vsmr->header.size = htons (msize);
1503 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1504 vsmr->querying_peer = querying_peer;
1505 vsmr->current_successor = current_successor;
1506 vsmr->probable_successor = probable_successor;
1507 vsmr->trail_direction = htonl (trail_direction);
1508 vsmr->trail_id = trail_id;
1509 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1510 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1512 /* Send the message to chosen friend. */
1513 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1514 target_friend->pending_count++;
1515 process_friend_queue (target_friend);
1520 * Construct a notify new successor message and send it to target_friend
1521 * @param source_peer Peer which wants to notify to its new successor that it
1522 * could be its predecessor.
1523 * @param successor New successor of @a source_peer
1524 * @param successor_trail List of peers in Trail to reach from
1525 * @a source_peer to @a new_successor, NOT including
1527 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1528 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1529 * @param target_friend Next friend to get this message.
1532 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1533 struct GNUNET_PeerIdentity successor,
1534 const struct GNUNET_PeerIdentity *successor_trail,
1535 unsigned int successor_trail_length,
1536 struct GNUNET_HashCode succesor_trail_id,
1537 struct FriendInfo *target_friend)
1539 struct PeerNotifyNewSuccessorMessage *nsm;
1540 struct P2PPendingMessage *pending;
1541 struct GNUNET_PeerIdentity *peer_list;
1544 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1545 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1547 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1553 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1555 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1559 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1560 pending->importance = 0; /* FIXME */
1561 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1562 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1563 pending->msg = &nsm->header;
1564 nsm->header.size = htons (msize);
1565 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1566 nsm->new_successor = successor;
1567 nsm->source_peer = source_peer;
1568 nsm->trail_id = succesor_trail_id;
1569 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1570 memcpy (peer_list, successor_trail,
1571 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1573 /* Send the message to chosen friend. */
1574 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1575 target_friend->pending_count++;
1576 process_friend_queue (target_friend);
1581 * Construct an add_trail message and send it to target_friend
1582 * @param source_peer Source of the trail.
1583 * @param destination_peer Destination of the trail.
1584 * @param trail_id Unique identifier of the trail from
1585 * @a source_peer to @a destination_peer, NOT including the endpoints.
1586 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1587 * NOT including the endpoints.
1588 * @param trail_length Total number of peers in @a trail.
1589 * @param target_friend Next friend to get this message.
1592 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1593 struct GNUNET_PeerIdentity destination_peer,
1594 struct GNUNET_HashCode trail_id,
1595 const struct GNUNET_PeerIdentity *trail,
1596 unsigned int trail_length,
1597 struct FriendInfo *target_friend)
1599 struct PeerAddTrailMessage *adm;
1600 struct GNUNET_PeerIdentity *peer_list;
1601 struct P2PPendingMessage *pending;
1604 msize = sizeof (struct PeerAddTrailMessage) +
1605 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1607 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1613 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1615 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1619 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1620 pending->importance = 0; /* FIXME */
1621 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1622 adm = (struct PeerAddTrailMessage *) &pending[1];
1623 pending->msg = &adm->header;
1624 adm->header.size = htons (msize);
1625 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1626 adm->source_peer = source_peer;
1627 adm->destination_peer = destination_peer;
1628 adm->trail_id = trail_id;
1629 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1630 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1632 /* Send the message to chosen friend. */
1633 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1634 target_friend->pending_count++;
1635 process_friend_queue (target_friend);
1641 * Search my location in trail. In case I am present more than once in the
1642 * trail (can happen during trail setup), then return my lowest index.
1643 * @param trail List of peers
1644 * @return my_index if found
1645 * trail_length + 1 if an entry is present twice, It is an error.
1646 * -1 if no entry found.
1649 search_my_index (const struct GNUNET_PeerIdentity *trail,
1653 int index_seen = trail_length + 1;
1656 for (i = 0; i < trail_length; i++)
1658 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1661 if(index_seen == (trail_length + 1))
1665 DEBUG("Entry is present twice in trail. Its not allowed\n");
1679 * Check if the friend is congested or have reached maximum number of trails
1680 * it can be part of of.
1681 * @param friend Friend to be checked.
1682 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1683 * #GNUNET_YES if friend is either congested or have crossed threshold
1686 is_friend_congested (struct FriendInfo *friend)
1688 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1689 ((0 == GNUNET_TIME_absolute_get_remaining
1690 (friend->congestion_timestamp).rel_value_us)))
1698 * Select closest finger to value.
1699 * @param peer1 First peer
1700 * @param peer2 Second peer
1701 * @param value Value to be compare
1702 * @return Closest peer
1704 static struct GNUNET_PeerIdentity
1705 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1706 const struct GNUNET_PeerIdentity *peer2,
1709 uint64_t peer1_value;
1710 uint64_t peer2_value;
1712 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1713 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1714 peer1_value = GNUNET_ntohll (peer1_value);
1715 peer2_value = GNUNET_ntohll (peer2_value);
1717 if (peer1_value == value)
1722 if (peer2_value == value)
1727 if (value < peer1_value && peer1_value < peer2_value)
1731 else if (value < peer2_value && peer2_value < peer1_value)
1735 else if (peer1_value < value && value < peer2_value)
1739 else if (peer2_value < value && value < peer1_value)
1743 else if (peer1_value < peer2_value && peer2_value < value)
1747 else // if (peer2_value < peer1_value && peer1_value < value)
1755 * Select closest predecessor to value.
1756 * @param peer1 First peer
1757 * @param peer2 Second peer
1758 * @param value Value to be compare
1759 * @return Peer which precedes value in the network.
1761 static struct GNUNET_PeerIdentity
1762 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1763 const struct GNUNET_PeerIdentity *peer2,
1766 uint64_t peer1_value;
1767 uint64_t peer2_value;
1769 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1770 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1771 peer1_value = GNUNET_ntohll (peer1_value);
1772 peer2_value = GNUNET_ntohll (peer2_value);
1774 if (peer1_value == value)
1779 if (peer2_value == value)
1784 if (value < peer1_value && peer1_value < peer2_value)
1788 else if (value < peer2_value && peer2_value < peer1_value)
1792 else if (peer1_value < value && value < peer2_value)
1796 else if (peer2_value < value && value < peer1_value)
1800 else if (peer1_value < peer2_value && peer2_value < value)
1804 else // if (peer2_value < peer1_value && peer1_value < value)
1816 test_print_trail (struct GNUNET_PeerIdentity *trail,
1817 unsigned int trail_length)
1819 struct GNUNET_PeerIdentity print_peer;
1822 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1823 __FILE__, __func__,__LINE__,trail_length);
1824 for (i =0 ; i< trail_length; i++)
1826 print_peer = trail[i];
1827 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1828 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1835 * This is a test function to print all the entries of friend table.
1838 test_friend_peermap_print ()
1840 struct FriendInfo *friend;
1841 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1842 struct GNUNET_PeerIdentity print_peer;
1843 struct GNUNET_PeerIdentity key_ret;
1846 print_peer = my_identity;
1847 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1848 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1850 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1852 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1854 (const void **)&friend))
1856 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1857 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1858 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1866 * This is a test function, to print all the entries of finger table.
1869 test_finger_table_print()
1871 struct FingerInfo *finger;
1872 struct GNUNET_PeerIdentity print_peer;
1873 //struct Trail *trail;
1877 print_peer = my_identity;
1878 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1879 for (i = 0; i < MAX_FINGERS; i++)
1881 finger = &finger_table[i];
1883 if (GNUNET_NO == finger->is_present)
1886 print_peer = finger->finger_identity;
1887 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1888 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1891 for (j = 0; j < finger->trails_count; j++)
1893 trail = &finger->trail_list[j];
1894 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1895 struct Trail_Element *element;
1896 element = trail->trail_head;
1897 for (k = 0; k < trail->trail_length; k++)
1899 print_peer = element->peer;
1900 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1901 element = element->next;
1910 * Select the closest peer among two peers (which should not be same)
1911 * with respect to value and finger_table_index
1912 * NOTE: peer1 != peer2
1913 * @param peer1 First peer
1914 * @param peer2 Second peer
1915 * @param value Value relative to which we find the closest
1916 * @param is_predecessor Is value a predecessor or any other finger.
1917 * @return Closest peer among two peers.
1919 static struct GNUNET_PeerIdentity
1920 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1921 const struct GNUNET_PeerIdentity *peer2,
1923 unsigned int is_predecessor)
1925 /* This check is here to ensure that calling function never sends
1926 same peer value in peer1 and peer2. Remove it later. */
1927 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1928 if (1 == is_predecessor)
1929 return select_closest_predecessor (peer1, peer2, value);
1931 // TODO: Change name to something like select_closest_successor!!
1932 return select_closest_finger (peer1, peer2, value);
1937 * Iterate over the list of all the trails of a finger. In case the first
1938 * friend to reach the finger has reached trail threshold or is congested,
1939 * then don't select it. In case there multiple available good trails to reach
1940 * to Finger, choose the one with shortest trail length.
1941 * Note: We use length as parameter. But we can use any other suitable parameter
1943 * @param finger Finger Finger whose trail we have to select.
1944 * @return Trail Selected Trail.
1946 static struct Trail *
1947 select_finger_trail (struct FingerInfo *finger)
1949 struct FriendInfo *friend;
1950 struct Trail *current_finger_trail;
1951 struct Trail *best_trail = NULL;
1954 GNUNET_assert (finger->trails_count > 0);
1955 for (i = 0; i < finger->trails_count; i++)
1957 current_finger_trail = &finger->trail_list[i];
1959 /* No trail stored at this index. */
1960 if (GNUNET_NO == current_finger_trail->is_present)
1963 GNUNET_assert (NULL !=
1965 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1966 ¤t_finger_trail->trail_head->peer)));
1968 /* First friend to reach trail is not free. */
1969 if (GNUNET_YES == is_friend_congested (friend))
1972 if (NULL == best_trail ||
1973 best_trail->trail_length > current_finger_trail->trail_length)
1975 best_trail = current_finger_trail;
1984 * Compare FINGER entry with current successor. If finger's first friend of all
1985 * its trail is not congested and has not crossed trail threshold, then check
1986 * if finger peer identity is closer to final_destination_finger_value than
1987 * current_successor. If yes then update current_successor.
1988 * @param current_successor[in/out]
1992 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
1994 struct FingerInfo *finger;
1995 struct GNUNET_PeerIdentity closest_peer;
1996 struct Trail *finger_trail;
1999 /* Iterate over finger table. */
2000 for (i = 0; i < MAX_FINGERS; i++)
2002 finger = &finger_table[i];
2004 if (GNUNET_NO == finger->is_present)
2007 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2008 ¤t_closest_peer->best_known_destination))
2011 /* If I am my own finger, then ignore this finger. */
2012 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2016 /* If finger is a friend, we have already checked it in previous function. */
2017 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2018 &finger->finger_identity)))
2023 closest_peer = select_closest_peer (&finger->finger_identity,
2024 ¤t_closest_peer->best_known_destination,
2025 current_closest_peer->destination_finger_value,
2026 current_closest_peer->is_predecessor);
2028 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer))
2030 /* Choose one of the trail to reach to finger. */
2031 finger_trail = select_finger_trail (finger);
2033 /* In case no trail found, ignore this finger. */
2034 if (NULL == finger_trail)
2037 current_closest_peer->best_known_destination = closest_peer;
2038 current_closest_peer->next_hop = finger_trail->trail_head->peer;
2039 current_closest_peer->trail_id = finger_trail->trail_id;
2040 current_closest_peer->finger_table_index = i;
2048 * Compare friend entry with current successor.
2049 * If friend identity and current_successor is same, then do nothing.
2050 * If friend is not congested and has not crossed trail threshold, then check
2051 * if friend peer identity is closer to final_destination_finger_value than
2052 * current_successor. If yes then update current_successor.
2053 * @param cls closure
2054 * @param key current public key
2055 * @param value struct Closest_Peer
2056 * @return #GNUNET_YES if we should continue to iterate,
2057 * #GNUNET_NO if not.
2060 compare_friend_and_current_closest_peer (void *cls,
2061 const struct GNUNET_PeerIdentity *key,
2064 struct FriendInfo *friend = value;
2065 struct Closest_Peer *current_closest_peer = cls;
2066 struct GNUNET_PeerIdentity closest_peer;
2068 /* Friend is either congested or has crossed threshold. */
2069 if (GNUNET_YES == is_friend_congested (friend))
2072 /* If current_closest_peer and friend identity are same, then do nothing.*/
2073 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2074 ¤t_closest_peer->best_known_destination))
2080 closest_peer = select_closest_peer (&friend->id,
2081 ¤t_closest_peer->best_known_destination,
2082 current_closest_peer->destination_finger_value,
2083 current_closest_peer->is_predecessor);
2085 /* Is friend the closest successor? */
2086 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer))
2088 current_closest_peer->best_known_destination = friend->id;
2089 current_closest_peer->next_hop = friend->id;
2097 * Initialize current_successor to my_identity.
2098 * @param my_identity My peer identity
2099 * @return Updated closest_peer
2101 static struct Closest_Peer
2102 init_closest_peer (struct GNUNET_PeerIdentity my_identity,
2103 uint64_t destination_finger_value,
2104 unsigned int is_predecessor)
2106 struct Closest_Peer current_closest_peer;
2108 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2109 current_closest_peer.destination_finger_value = destination_finger_value;
2110 current_closest_peer.is_predecessor = is_predecessor;
2111 current_closest_peer.next_hop = my_identity;
2112 current_closest_peer.best_known_destination = my_identity;
2113 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
2114 return current_closest_peer;
2119 * Find locally best known peer, among your own identity, friend and finger list,
2120 * which is closest to given destination_finger_value.
2122 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2124 * @param destination_finger_value Peer closest to this value will be the next destination.
2125 * @param is_predecessor Are we looking for predecessor or finger?
2126 * @return Closest_Peer that contains all the relevant field to reach to
2127 * @a destination_finger_value
2129 static struct Closest_Peer
2130 find_local_best_known_next_hop (uint64_t destination_finger_value,
2131 unsigned int is_predecessor)
2133 struct Closest_Peer current_closest_peer;
2135 /* Initialize current_successor to my_identity. */
2136 current_closest_peer = init_closest_peer (my_identity,
2137 destination_finger_value,
2140 /* Compare each friend entry with current_successor and update current_successor
2141 * with friend if its closest. */
2144 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2145 &compare_friend_and_current_closest_peer,
2146 ¤t_closest_peer));
2148 /* Compare each finger entry with current_successor and update current_successor
2149 * with finger if its closest. */
2150 compare_finger_and_current_closest_peer (¤t_closest_peer);
2151 return current_closest_peer;
2155 * FIXME; Send put message across all the trail to reach to next hop to handle
2157 * Construct a Put message and send it to target_peer.
2158 * @param key Key for the content
2159 * @param block_type Type of the block
2160 * @param options Routing options
2161 * @param desired_replication_level Desired replication count
2162 * @param best_known_dest Peer to which this message should reach eventually,
2163 * as it is best known destination to me.
2164 * @param intermediate_trail_id Trail id in case
2165 * @param target_peer Peer to which this message will be forwarded.
2166 * @param hop_count Number of hops traversed so far.
2167 * @param put_path_length Total number of peers in @a put_path
2168 * @param put_path Number of peers traversed so far
2169 * @param expiration_time When does the content expire
2170 * @param data Content to store
2171 * @param data_size Size of content @a data in bytes
2174 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2175 enum GNUNET_BLOCK_Type block_type,
2176 enum GNUNET_DHT_RouteOption options,
2177 uint32_t desired_replication_level,
2178 struct GNUNET_PeerIdentity best_known_dest,
2179 struct GNUNET_HashCode intermediate_trail_id,
2180 struct GNUNET_PeerIdentity *target_peer,
2182 uint32_t put_path_length,
2183 struct GNUNET_PeerIdentity *put_path,
2184 struct GNUNET_TIME_Absolute expiration_time,
2185 const void *data, size_t data_size)
2187 struct PeerPutMessage *ppm;
2188 struct P2PPendingMessage *pending;
2189 struct FriendInfo *target_friend;
2190 struct GNUNET_PeerIdentity *pp;
2193 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2194 sizeof (struct PeerPutMessage);
2195 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2197 put_path_length = 0;
2198 msize = data_size + sizeof (struct PeerPutMessage);
2201 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2203 DEBUG("msize = %lu\n",msize);
2208 GNUNET_assert (NULL !=
2210 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2211 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2212 pending->timeout = expiration_time;
2213 ppm = (struct PeerPutMessage *) &pending[1];
2214 pending->msg = &ppm->header;
2215 ppm->header.size = htons (msize);
2216 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2217 ppm->options = htonl (options);
2218 ppm->block_type = htonl (block_type);
2219 ppm->hop_count = htonl (hop_count + 1);
2220 ppm->desired_replication_level = htonl (desired_replication_level);
2221 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2222 ppm->best_known_destination = best_known_dest;
2223 ppm->intermediate_trail_id = intermediate_trail_id;
2225 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2226 ppm->put_path_length = htonl (put_path_length);
2227 if(put_path_length > 0)
2229 memcpy (pp, put_path,
2230 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2232 memcpy (&pp[put_path_length], data, data_size);
2233 GNUNET_assert (NULL != target_friend);
2234 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2235 target_friend->pending_count++;
2236 process_friend_queue (target_friend);
2241 * Handle the put request from the client.
2242 * @param key Key for the content
2243 * @param block_type Type of the block
2244 * @param options Routing options
2245 * @param desired_replication_level Desired replication count
2246 * @param expiration_time When does the content expire
2247 * @param data Content to store
2248 * @param data_size Size of content @a data in bytes
2251 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
2252 enum GNUNET_BLOCK_Type block_type,
2253 enum GNUNET_DHT_RouteOption options,
2254 uint32_t desired_replication_level,
2255 struct GNUNET_TIME_Absolute expiration_time,
2256 const void *data, size_t data_size)
2258 struct GNUNET_PeerIdentity best_known_dest;
2259 struct GNUNET_HashCode intermediate_trail_id;
2260 struct GNUNET_PeerIdentity next_hop;
2262 struct Closest_Peer successor;
2264 memcpy (&key_value, key, sizeof (uint64_t));
2265 key_value = GNUNET_ntohll (key_value);
2266 successor = find_local_best_known_next_hop (key_value,
2267 GDS_FINGER_TYPE_NON_PREDECESSOR);
2268 best_known_dest = successor.best_known_destination;
2269 next_hop = successor.next_hop;
2270 intermediate_trail_id = successor.trail_id;
2272 DEBUG("PUT_REQUEST_RECEVIED KEY = %s \n",GNUNET_h2s(key));
2273 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2275 /* I am the destination. */
2276 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2277 block_type,data_size,data);
2278 GDS_CLIENTS_process_put (options, block_type, 0,
2279 ntohl (desired_replication_level),
2280 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time.
2281 key, data, data_size);
2285 /* In case we are sending the request to a finger, then send across all of its
2288 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2289 &successor.next_hop))
2291 struct FingerInfo *next_hop_finger;
2294 next_hop_finger = &finger_table[successor.finger_table_index];
2295 for (i = 0; i < next_hop_finger->trails_count; i++)
2297 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2299 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2301 next_hop_finger->trail_list[i].trail_id,
2302 &next_hop, hop_count, put_path_length, put_path,
2310 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2311 best_known_dest, intermediate_trail_id, &next_hop,
2312 0, 1, &my_identity, expiration_time,
2317 * FIXME; Send get message across all the trail to reach to next hop to handle
2319 * Construct a Get message and send it to target_peer.
2320 * @param key Key for the content
2321 * @param block_type Type of the block
2322 * @param options Routing options
2323 * @param desired_replication_level Desired replication count
2324 * @param best_known_dest Peer which should get this message. Same as target peer
2325 * if best_known_dest is a friend else its a finger.
2326 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2327 * in case it is a finger else set to 0.
2328 * @param target_peer Peer to which this message will be forwarded.
2329 * @param hop_count Number of hops traversed so far.
2330 * @param data Content to store
2331 * @param data_size Size of content @a data in bytes
2332 * @param get_path_length Total number of peers in @a get_path
2333 * @param get_path Number of peers traversed so far
2336 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2337 enum GNUNET_BLOCK_Type block_type,
2338 enum GNUNET_DHT_RouteOption options,
2339 uint32_t desired_replication_level,
2340 struct GNUNET_PeerIdentity best_known_dest,
2341 struct GNUNET_HashCode intermediate_trail_id,
2342 struct GNUNET_PeerIdentity *target_peer,
2344 uint32_t get_path_length,
2345 struct GNUNET_PeerIdentity *get_path)
2347 struct PeerGetMessage *pgm;
2348 struct P2PPendingMessage *pending;
2349 struct FriendInfo *target_friend;
2350 struct GNUNET_PeerIdentity *gp;
2353 msize = sizeof (struct PeerGetMessage) +
2354 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2356 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2361 GNUNET_assert (NULL !=
2363 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2365 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2366 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2367 pending->importance = 0; /* FIXME */
2368 pgm = (struct PeerGetMessage *) &pending[1];
2369 pending->msg = &pgm->header;
2370 pgm->header.size = htons (msize);
2371 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2372 pgm->get_path_length = htonl (get_path_length);
2373 pgm->best_known_destination = best_known_dest;
2375 pgm->intermediate_trail_id = intermediate_trail_id;
2376 pgm->hop_count = htonl (hop_count + 1);
2377 pgm->get_path_length = htonl (get_path_length);
2378 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2379 memcpy (gp, get_path,
2380 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2381 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2382 target_friend->pending_count++;
2383 process_friend_queue (target_friend);
2388 * Handle the get request from the client file. If I am destination do
2389 * datacache put and return. Else find the target friend and forward message
2391 * @param key Key for the content
2392 * @param block_type Type of the block
2393 * @param options Routing options
2394 * @param desired_replication_level Desired replication count
2397 GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key,
2398 enum GNUNET_BLOCK_Type block_type,
2399 enum GNUNET_DHT_RouteOption options,
2400 uint32_t desired_replication_level)
2402 struct Closest_Peer successor;
2403 struct GNUNET_PeerIdentity best_known_dest;
2404 struct GNUNET_HashCode intermediate_trail_id;
2407 memcpy (&key_value, key, sizeof (uint64_t));
2408 key_value = GNUNET_ntohll (key_value);
2410 successor = find_local_best_known_next_hop (key_value,
2411 GDS_FINGER_TYPE_NON_PREDECESSOR);
2413 best_known_dest = successor.best_known_destination;
2414 intermediate_trail_id = successor.trail_id;
2416 DEBUG("GET_REQUEST_RECEVIED KEY = %s \n",GNUNET_h2s(key));
2417 /* I am the destination. I have the data. */
2418 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2421 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2422 NULL, 0, 1, &my_identity, NULL,&my_identity);
2426 /* fixme; for multiple trails, we need to send back finger index and send trail
2427 across all the fingers. but in current implementation we don't have this case.
2428 compare finger and current_successor returns, */
2429 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2430 best_known_dest,intermediate_trail_id, &successor.next_hop,
2431 0, 1, &my_identity);
2436 * Send the get result to requesting client.
2437 * @param key Key of the requested data.
2438 * @param type Block type
2439 * @param target_peer Next peer to forward the message to.
2440 * @param source_peer Peer which has the data for the key.
2441 * @param put_path_length Number of peers in @a put_path
2442 * @param put_path Path taken to put the data at its stored location.
2443 * @param get_path_length Number of peers in @a get_path
2444 * @param get_path Path taken to reach to the location of the key.
2445 * @param expiration When will this result expire?
2446 * @param data Payload to store
2447 * @param data_size Size of the @a data
2450 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2451 enum GNUNET_BLOCK_Type type,
2452 const struct GNUNET_PeerIdentity *target_peer,
2453 const struct GNUNET_PeerIdentity *source_peer,
2454 unsigned int put_path_length,
2455 const struct GNUNET_PeerIdentity *put_path,
2456 unsigned int get_path_length,
2457 const struct GNUNET_PeerIdentity *get_path,
2458 struct GNUNET_TIME_Absolute expiration,
2459 const void *data, size_t data_size)
2461 struct PeerGetResultMessage *get_result;
2462 struct GNUNET_PeerIdentity *paths;
2463 struct P2PPendingMessage *pending;
2464 struct FriendInfo *target_friend;
2465 int current_path_index;
2468 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2470 sizeof (struct PeerGetResultMessage);
2472 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2474 put_path_length = 0;
2475 msize = msize - put_path_length;
2479 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2484 current_path_index = 0;
2485 if(get_path_length > 0)
2487 current_path_index = search_my_index(get_path, get_path_length);
2488 if (-1 == current_path_index)
2493 if ((get_path_length + 1) == current_path_index)
2495 DEBUG ("Peer found twice in get path. Not allowed \n");
2500 if (0 == current_path_index)
2502 DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",GNUNET_h2s(key),GNUNET_i2s(&my_identity));
2503 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2504 get_path, put_path_length,
2505 put_path, type, data_size, data);
2509 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2510 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2511 pending->importance = 0;
2512 get_result = (struct PeerGetResultMessage *)&pending[1];
2513 pending->msg = &get_result->header;
2514 get_result->header.size = htons (msize);
2515 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2516 get_result->key = *key;
2517 get_result->querying_peer = *source_peer;
2518 get_result->expiration_time = expiration;
2519 get_result->get_path_length = htonl (get_path_length);
2520 get_result->put_path_length = htonl (put_path_length);
2521 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2522 memcpy (paths, put_path,
2523 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2524 memcpy (&paths[put_path_length], get_path,
2525 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2526 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2528 GNUNET_assert (NULL !=
2530 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2531 &get_path[current_path_index - 1])));
2532 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2533 target_friend->pending_count++;
2534 process_friend_queue (target_friend);
2539 * Randomly choose one of your friends (which is not congested and have not crossed
2540 * trail threshold) from the friend_peermap
2541 * @return Friend Randomly chosen friend.
2542 * NULL in case friend peermap is empty, or all the friends are either
2543 * congested or have crossed trail threshold.
2545 static struct FriendInfo *
2546 select_random_friend ()
2548 unsigned int current_size;
2551 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2552 struct GNUNET_PeerIdentity key_ret;
2553 struct FriendInfo *friend;
2555 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2558 if (0 == current_size)
2561 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2562 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2564 /* Iterate till you don't reach to index. */
2565 for (j = 0; j < index ; j++)
2566 GNUNET_assert (GNUNET_YES ==
2567 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2571 /* Reset the index in friend peermap to 0 as we reached to the end. */
2572 if (j == current_size)
2575 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2576 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2580 /* Get the friend stored at the index, j*/
2581 GNUNET_assert (GNUNET_YES ==
2582 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2584 (const void **)&friend));
2586 /* This friend is not congested and has not crossed trail threshold. */
2587 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2588 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2594 } while (j != index);
2596 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2602 * Compute 64 bit value of finger_identity corresponding to a finger index using
2604 * For all fingers, n.finger[i] = n + pow (2,i),
2605 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2606 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2607 * @param finger_index Index corresponding to which we calculate 64 bit value.
2608 * @return 64 bit value.
2611 compute_finger_identity_value (unsigned int finger_index)
2615 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2616 my_id64 = GNUNET_ntohll (my_id64);
2618 /* Are we looking for immediate predecessor? */
2619 if (PREDECESSOR_FINGER_ID == finger_index)
2620 return (my_id64 - 1);
2623 uint64_t add = (uint64_t)1 << finger_index;
2624 return (my_id64 + add);
2630 * Choose a random friend. Calculate the next finger identity to search,from
2631 * current_search_finger_index. Start looking for the trail to reach to
2632 * finger identity through this random friend.
2634 * @param cls closure for this task
2635 * @param tc the context under which the task is running
2638 send_find_finger_trail_message (void *cls,
2639 const struct GNUNET_SCHEDULER_TaskContext *tc)
2641 struct FriendInfo *target_friend;
2642 struct GNUNET_HashCode trail_id;
2643 struct GNUNET_HashCode intermediate_trail_id;
2644 unsigned int is_predecessor = 0;
2645 uint64_t finger_id_value;
2647 /* Schedule another send_find_finger_trail_message task. After one round of
2648 * finger search, this time is exponentially backoff. */
2649 find_finger_trail_task_next_send_time.rel_value_us =
2650 find_finger_trail_task_next_send_time.rel_value_us +
2651 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2652 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2653 find_finger_trail_task =
2654 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2655 &send_find_finger_trail_message,
2658 /* No space in my routing table. (Source and destination peers also store entries
2659 * in their routing table). */
2660 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2663 target_friend = select_random_friend ();
2664 if (NULL == target_friend)
2669 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2670 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2673 /* Generate a unique trail id for trail we are trying to setup. */
2674 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2675 &trail_id, sizeof (trail_id));
2676 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2677 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2678 target_friend->id, target_friend, 0, NULL,
2679 is_predecessor, trail_id,
2680 intermediate_trail_id);
2685 * In case there are already maximum number of possible trails to reach to a
2686 * finger, then check if the new trail's length is lesser than any of the
2688 * If yes then replace that old trail by new trail.
2690 * Note: Here we are taking length as a parameter to choose the best possible
2691 * trail, but there could be other parameters also like:
2692 * 1. duration of existence of a trail - older the better.
2693 * 2. if the new trail is completely disjoint than the
2694 * other trails, then may be choosing it is better.
2696 * @param finger Finger
2697 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2698 * including the endpoints.
2699 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2700 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2703 select_and_replace_trail (struct FingerInfo *finger,
2704 const struct GNUNET_PeerIdentity *new_trail,
2705 unsigned int new_trail_length,
2706 struct GNUNET_HashCode new_trail_id)
2708 struct Trail *current_trail;
2709 unsigned int largest_trail_length;
2710 unsigned int largest_trail_index;
2711 struct Trail_Element *trail_element;
2712 struct GNUNET_PeerIdentity *next_hop;
2715 largest_trail_length = new_trail_length;
2716 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2718 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2720 for (i = 0; i < finger->trails_count; i++)
2722 current_trail = &finger->trail_list[i];
2723 GNUNET_assert (GNUNET_YES == current_trail->is_present);
2724 if (current_trail->trail_length > largest_trail_length)
2726 largest_trail_length = current_trail->trail_length;
2727 largest_trail_index = i;
2731 /* New trail is not better than existing ones. Send trail teardown. */
2732 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2734 next_hop = GDS_ROUTING_get_next_hop (new_trail_id, GDS_ROUTING_SRC_TO_DEST);
2735 GDS_ROUTING_remove_trail (new_trail_id);
2736 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2737 GDS_ROUTING_SRC_TO_DEST,
2742 /* Send trail teardown message across the replaced trail. */
2743 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2744 next_hop = GDS_ROUTING_get_next_hop (replace_trail->trail_id, GDS_ROUTING_SRC_TO_DEST);
2745 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2746 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2747 GDS_ROUTING_SRC_TO_DEST,
2750 /* Free the trail. */
2751 while (NULL != (trail_element = replace_trail->trail_head))
2753 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2754 replace_trail->trail_tail, trail_element);
2755 GNUNET_free_non_null (trail_element);
2758 /* Add new trial at that location. */
2759 replace_trail->is_present = GNUNET_YES;
2760 replace_trail->trail_length = new_trail_length;
2761 replace_trail->trail_id = new_trail_id;
2763 for (i = 0; i < new_trail_length; i++)
2765 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2766 element->peer = new_trail[i];
2768 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2769 replace_trail->trail_tail,
2772 /* FIXME: URGENT Are we adding the trail back to the list. */
2777 * Check if the new trail to reach to finger is unique or do we already have
2778 * such a trail present for finger.
2779 * @param existing_finger Finger identity
2780 * @param new_trail New trail to reach @a existing_finger
2781 * @param trail_length Total number of peers in new_trail.
2782 * @return #GNUNET_YES if the new trail is unique
2783 * #GNUNET_NO if same trail is already present.
2786 is_new_trail_unique (struct FingerInfo *existing_finger,
2787 const struct GNUNET_PeerIdentity *new_trail,
2788 unsigned int trail_length)
2790 struct Trail *current_trail;
2791 struct Trail_Element *trail_element;
2795 GNUNET_assert (existing_finger->trails_count > 0);
2797 /* Iterate over list of trails. */
2798 for (i = 0; i < existing_finger->trails_count; i++)
2800 current_trail = &(existing_finger->trail_list[i]);
2801 if(GNUNET_NO == current_trail->is_present)
2804 /* New trail and existing trail length are not same. */
2805 if (current_trail->trail_length != trail_length)
2810 trail_element = current_trail->trail_head;
2811 for (j = 0; j < current_trail->trail_length; j++)
2813 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2814 &trail_element->peer))
2818 trail_element = trail_element->next;
2825 * FIXME; In case of multiple trails, we may have a case where a trail from in
2826 * between has been removed, then we should try to find a free slot , not simply
2827 * add a trail at then end of the list.
2828 * Add a new trail at a free slot in trail array of existing finger.
2829 * @param existing_finger Finger
2830 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2831 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2832 * @param new_finger_trail_id Unique identifier of the trail.
2835 add_new_trail (struct FingerInfo *existing_finger,
2836 const struct GNUNET_PeerIdentity *new_trail,
2837 unsigned int new_trail_length,
2838 struct GNUNET_HashCode new_trail_id)
2840 struct FriendInfo *friend;
2841 struct Trail *trail;
2845 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2849 for (i = 0; i < existing_finger->trails_count; i++)
2851 if (GNUNET_NO == existing_finger->trail_list[i].is_present)
2858 if (-1 == free_slot)
2861 trail = &existing_finger->trail_list[free_slot];
2862 GNUNET_assert (GNUNET_NO == trail->is_present);
2863 trail->trail_id = new_trail_id;
2864 trail->trail_length = new_trail_length;
2865 existing_finger->trails_count++;
2866 trail->is_present = GNUNET_YES;
2867 if (0 == new_trail_length)
2869 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2870 &existing_finger->finger_identity);
2874 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2878 friend->trails_count++;
2879 for (i = 0; i < new_trail_length; i++)
2881 struct Trail_Element *element;
2883 element = GNUNET_new (struct Trail_Element);
2884 element->peer = new_trail[i];
2885 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2890 existing_finger->trail_list[free_slot].trail_head = trail->trail_head;
2891 existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail;
2892 existing_finger->trail_list[free_slot].trail_length = new_trail_length;
2893 existing_finger->trail_list[free_slot].trail_id = new_trail_id;
2894 existing_finger->trail_list[free_slot].is_present = GNUNET_YES;
2900 * FIXME; In case of multiple trails, we may have a case where a trail from in
2901 * between has been removed, then we should try to find a free slot , not simply
2902 * add a trail at then end of the list.
2903 * Add a new trail at a free slot in trail array of existing finger.
2904 * @param existing_finger Finger
2905 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2906 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2907 * @param new_finger_trail_id Unique identifier of the trail.
2910 add_new_trail (struct FingerInfo *existing_finger,
2911 const struct GNUNET_PeerIdentity *new_trail,
2912 unsigned int new_trail_length,
2913 struct GNUNET_HashCode new_trail_id)
2915 struct Trail *trail;
2916 struct FriendInfo *first_friend;
2920 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2924 index = existing_finger->trails_count;
2925 trail = &existing_finger->trail_list[index];
2926 GNUNET_assert (GNUNET_NO == trail->is_present);
2927 trail->trail_id = new_trail_id;
2928 trail->trail_length = new_trail_length;
2929 existing_finger->trails_count++;
2930 trail->is_present = GNUNET_YES;
2932 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2933 &existing_finger->finger_identity)));
2934 /* If finger is a friend then we never call this function. */
2935 GNUNET_assert (new_trail_length > 0);
2937 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2939 first_friend->trails_count++;
2941 for (i = 0; i < new_trail_length; i++)
2943 struct Trail_Element *element;
2945 element = GNUNET_new (struct Trail_Element);
2946 element->peer = new_trail[i];
2947 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2951 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2952 existing_finger->trail_list[index].trail_head = trail->trail_head;
2953 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2954 existing_finger->trail_list[index].trail_length = new_trail_length;
2955 existing_finger->trail_list[index].trail_id = new_trail_id;
2956 existing_finger->trail_list[index].is_present = GNUNET_YES;
2961 * Get the next hop to send trail teardown message from routing table and
2962 * then delete the entry from routing table. Send trail teardown message for a
2963 * specific trail of a finger.
2964 * @param finger Finger whose trail is to be removed.
2965 * @param trail List of peers in trail from me to a finger, NOT including
2969 send_trail_teardown (struct FingerInfo *finger,
2970 struct Trail *trail)
2972 struct FriendInfo *friend;
2973 struct GNUNET_PeerIdentity *next_hop;
2975 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2976 GDS_ROUTING_SRC_TO_DEST);
2977 if (NULL == next_hop)
2979 // DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d",
2980 // GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length);
2983 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2986 GNUNET_assert(GNUNET_YES == trail->is_present);
2987 if (trail->trail_length > 0)
2989 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2990 &trail->trail_head->peer);
2994 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2995 &finger->finger_identity);
3000 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
3001 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
3004 if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)
3005 && (0 == trail->trail_length))
3007 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
3008 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
3011 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
3012 friend->trails_count--;
3013 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
3014 GDS_ROUTING_SRC_TO_DEST,
3020 * Send trail teardown message across all the trails to reach to finger.
3021 * @param finger Finger whose all the trail should be freed.
3024 send_all_finger_trails_teardown (struct FingerInfo *finger)
3027 for (i = 0; i < finger->trails_count; i++)
3029 struct Trail *trail;
3030 trail = &finger->trail_list[i];
3031 if (GNUNET_YES == trail->is_present);
3033 send_trail_teardown (finger, trail);
3034 trail->is_present = GNUNET_NO;
3041 * Free a specific trail
3042 * @param trail List of peers to be freed.
3045 free_trail (struct Trail *trail)
3047 struct Trail_Element *trail_element;
3049 while (NULL != (trail_element = trail->trail_head))
3051 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
3054 GNUNET_free_non_null (trail_element);
3056 trail->trail_head = NULL;
3057 trail->trail_tail = NULL;
3062 * Free finger and its trail.
3063 * @param finger Finger to be freed.
3064 * @param finger_table_index Index at which finger is stored.
3067 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
3069 struct Trail *trail;
3071 for (i = 0; i < finger->trails_count; i++)
3073 trail = &finger->trail_list[i];
3074 if (GNUNET_NO == trail->is_present)
3077 if (trail->trail_length > 0)
3079 trail->is_present = GNUNET_NO;
3082 finger->is_present = GNUNET_NO;
3083 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
3088 * Add a new entry in finger table at finger_table_index.
3089 * In case I am my own finger, then we don't have a trail. In case of a friend,
3090 * we have a trail with unique id and '0' trail length.
3091 * In case a finger is a friend, then increment the trails count of the friend.
3092 * @param finger_identity Peer Identity of new finger
3093 * @param finger_trail Trail to reach from me to finger (excluding both end points).
3094 * @param finger_trail_length Total number of peers in @a finger_trail.
3095 * @param trail_id Unique identifier of the trail.
3096 * @param finger_table_index Index in finger table.
3099 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
3100 const struct GNUNET_PeerIdentity *finger_trail,
3101 unsigned int finger_trail_length,
3102 struct GNUNET_HashCode trail_id,
3103 unsigned int finger_table_index)
3105 struct FingerInfo *new_entry;
3106 struct FriendInfo *first_trail_hop;
3107 struct Trail *trail;
3110 new_entry = GNUNET_new (struct FingerInfo);
3111 new_entry->finger_identity = finger_identity;
3112 new_entry->finger_table_index = finger_table_index;
3113 new_entry->is_present = GNUNET_YES;
3115 /* If the new entry is my own identity. */
3116 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3119 new_entry->trails_count = 0;
3120 finger_table[finger_table_index] = *new_entry;
3121 GNUNET_free (new_entry);
3125 /* Finger is a friend. */
3126 if (0 == finger_trail_length)
3128 new_entry->trail_list[0].trail_id = trail_id;
3129 new_entry->trails_count = 1;
3130 new_entry->trail_list[0].is_present = GNUNET_YES;
3131 new_entry->trail_list[0].trail_length = 0;
3132 new_entry->trail_list[0].trail_head = NULL;
3133 new_entry->trail_list[0].trail_tail = NULL;
3134 finger_table[finger_table_index] = *new_entry;
3135 GNUNET_assert (NULL !=
3137 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3138 &finger_identity)));
3140 first_trail_hop->trails_count++;
3141 GNUNET_free (new_entry);
3145 GNUNET_assert (NULL !=
3147 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3148 &finger_trail[0])));
3149 new_entry->trails_count = 1;
3150 first_trail_hop->trails_count++;
3151 /* Copy the finger trail into trail. */
3152 trail = GNUNET_new (struct Trail);
3153 for(i = 0; i < finger_trail_length; i++)
3155 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3157 element->next = NULL;
3158 element->prev = NULL;
3159 element->peer = finger_trail[i];
3160 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3165 /* Add trail to trail list. */
3166 new_entry->trail_list[0].trail_head = trail->trail_head;
3167 new_entry->trail_list[0].trail_tail = trail->trail_tail;
3168 new_entry->trail_list[0].trail_length = finger_trail_length;
3169 new_entry->trail_list[0].trail_id = trail_id;
3170 new_entry->trail_list[0].is_present = GNUNET_YES;
3171 finger_table[finger_table_index] = *new_entry;
3172 GNUNET_free (new_entry);
3178 * Periodic task to verify current successor. There can be multiple trails to reach
3179 * to successor, choose the shortest one and send verify successor message
3180 * across that trail.
3181 * @param cls closure for this task
3182 * @param tc the context under which the task is running
3185 send_verify_successor_message (void *cls,
3186 const struct GNUNET_SCHEDULER_TaskContext *tc)
3188 struct FriendInfo *target_friend;
3189 struct GNUNET_HashCode trail_id;
3190 struct Trail *trail;
3191 struct Trail_Element *element;
3192 unsigned int trail_length;
3194 struct FingerInfo *successor;
3196 successor = &finger_table[0];
3198 /* This task will be scheduled when the result for Verify Successor is received. */
3199 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
3201 /* When verify successor is being called for first time *for current context*
3202 * cls will be NULL. If send_verify_successor_retry_task is not NO_TASK, we
3203 * must cancel the retry task scheduled for verify_successor of previous
3208 /* FIXME: Here we are scheduling a new verify successor task, as we
3209 got a new successor. But a send verify successor task may be in progress.
3210 1. We need to be sure that this is indeed a new successor. As this function
3211 is called even if we add a new trail to reach t old successor.
3212 2. Assuming the new successor is different, then verify successor message
3213 * to old successor may be following stages.
3214 * --> Waiting for verify successor result. Don't wait anymore. there is
3215 * no trail to reach from old successor to me, hence, routing
3217 * --> Waiting for notify confirmation. again don't wait for it. notify
3218 * confirmation will not succeded.
3220 if (send_verify_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
3222 /* FIXME: Are we scheduling retry task as soon as we send verify message.
3223 If yes then here before making this task, first check if the message
3224 is for the same peer again. */
3225 struct VerifySuccessorContext *old_ctx =
3226 GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
3227 /* old_ctx must not be NULL, as the retry task had been scheduled */
3228 GNUNET_assert(NULL != old_ctx);
3229 GNUNET_free(old_ctx);
3230 /* FIXME: Why don't we reset the task to NO_TASK here? */
3233 struct VerifySuccessorContext *ctx;
3234 ctx = GNUNET_new(struct VerifySuccessorContext);
3236 ctx->num_retries_scheduled++;
3237 send_verify_successor_retry_task =
3238 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3239 &send_verify_successor_message,
3244 /* This is a retry attempt for verify_successor for a previous context */
3245 struct VerifySuccessorContext *ctx;
3248 ctx->num_retries_scheduled++;
3249 send_verify_successor_retry_task =
3250 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3251 &send_verify_successor_message,
3255 /* Among all the trails to reach to successor, select first one which is present.*/
3256 for (i = 0; i < successor->trails_count; i++)
3258 trail = &successor->trail_list[i];
3259 if(GNUNET_YES == trail->is_present)
3263 /* No valid trail found to reach to successor. */
3264 if (i == successor->trails_count)
3267 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3268 &successor->finger_identity));
3269 /* Trail stored at this index. */
3270 GNUNET_assert (GNUNET_YES == trail->is_present);
3271 trail_id = trail->trail_id;
3272 if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST))
3274 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3275 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
3279 trail_length = trail->trail_length;
3280 if (trail_length > 0)
3282 /* Copy the trail into peer list. */
3283 struct GNUNET_PeerIdentity peer_list[trail_length];
3284 element = trail->trail_head;
3285 for(i = 0; i < trail_length; i++)
3287 peer_list[i] = element->peer;
3288 element = element->next;
3290 GNUNET_assert (NULL != (target_friend =
3291 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3293 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3294 successor->finger_identity,
3295 trail_id, peer_list, trail_length,
3300 GNUNET_assert (NULL != (target_friend =
3301 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3302 &successor->finger_identity)));
3303 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3304 successor->finger_identity,
3312 * FIXME: should this be a periodic task, incrementing the search finger index?
3313 * Update the current search finger index.
3314 * @a finger_identity
3315 * @a finger_table_index
3318 update_current_search_finger_index (unsigned int finger_table_index)
3320 struct FingerInfo *successor;
3322 /* FIXME correct this: only move current index periodically */
3323 if (finger_table_index != current_search_finger_index)
3326 successor = &finger_table[0];
3327 GNUNET_assert (GNUNET_YES == successor->is_present);
3329 /* We were looking for immediate successor. */
3330 if (0 == current_search_finger_index)
3332 current_search_finger_index = PREDECESSOR_FINGER_ID;
3333 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &successor->finger_identity))
3335 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3337 send_verify_successor_task =
3338 GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3344 current_search_finger_index = current_search_finger_index - 1;
3350 * Get the least significant bit set in val.
3353 * @return Position of first bit set, 65 in case of error.
3356 find_set_bit (uint64_t val)
3376 return 65; /* Some other bit was set to 1 as well. */
3383 * Calculate finger_table_index from initial 64 bit finger identity value that
3384 * we send in trail setup message.
3385 * @param ultimate_destination_finger_value Value that we calculated from our
3386 * identity and finger_table_index.
3387 * @param is_predecessor Is the entry for predecessor or not?
3388 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3389 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3392 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3393 unsigned int is_predecessor)
3397 unsigned int finger_table_index;
3399 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3400 my_id64 = GNUNET_ntohll (my_id64);
3402 /* Is this a predecessor finger? */
3403 if (1 == is_predecessor)
3405 diff = my_id64 - ultimate_destination_finger_value;
3407 finger_table_index = PREDECESSOR_FINGER_ID;
3409 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3414 diff = ultimate_destination_finger_value - my_id64;
3415 finger_table_index = find_set_bit (diff);
3417 return finger_table_index;
3422 * Remove finger and its associated data structures from finger table.
3423 * @param existing_finger Finger to be removed which is in finger table.
3424 * @param finger_table_index Index in finger table where @a existing_finger
3428 remove_existing_finger (struct FingerInfo *existing_finger,
3429 unsigned int finger_table_index)
3431 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3433 /* If I am my own finger, then we have no trails. */
3434 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3437 existing_finger->is_present = GNUNET_NO;
3438 memset ((void *)&finger_table[finger_table_index], 0,
3439 sizeof (finger_table[finger_table_index]));
3443 /* For all other fingers, send trail teardown across all the trails to reach
3444 finger, and free the finger. */
3445 send_all_finger_trails_teardown (existing_finger);
3446 free_finger (existing_finger, finger_table_index);
3452 * Check if there is already an entry in finger_table at finger_table_index.
3453 * We get the finger_table_index from 64bit finger value we got from the network.
3454 * -- If yes, then select the closest finger.
3455 * -- If new and existing finger are same, then check if you can store more
3457 * -- If yes then add trail, else keep the best trails to reach to the
3459 * -- If the new finger is closest, remove the existing entry, send trail
3460 * teardown message across all the trails to reach the existing entry.
3461 * Add the new finger.
3462 * -- If new and existing finger are different, and existing finger is closest
3464 * -- Update current_search_finger_index.
3465 * @param finger_identity Peer Identity of new finger
3466 * @param finger_trail Trail to reach the new finger
3467 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3468 * @param is_predecessor Is this entry for predecessor in finger_table?
3469 * @param finger_value 64 bit value of finger identity that we got from network.
3470 * @param finger_trail_id Unique identifier of @finger_trail.
3473 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3474 const struct GNUNET_PeerIdentity *finger_trail,
3475 unsigned int finger_trail_length,
3476 unsigned int is_predecessor,
3477 uint64_t finger_value,
3478 struct GNUNET_HashCode finger_trail_id)
3480 struct FingerInfo *existing_finger;
3481 struct GNUNET_PeerIdentity closest_peer;
3482 struct FingerInfo *successor;
3483 unsigned int finger_table_index;
3485 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3486 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3488 /* Invalid finger_table_index. */
3489 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3491 GNUNET_break_op (0);
3495 /* Check if new entry is same as successor. */
3496 if ((0 != finger_table_index) &&
3497 (PREDECESSOR_FINGER_ID != finger_table_index))
3499 successor = &finger_table[0];
3500 if (GNUNET_NO == successor->is_present)
3502 GNUNET_break (0); //ASSERTION FAILS HERE. FIXME
3505 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3506 &successor->finger_identity))
3508 // find_finger_trail_task_next_send_time =
3509 // GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3510 current_search_finger_index = 0;
3511 GNUNET_STATISTICS_update (GDS_stats,
3513 ("# FINGERS_COUNT"), (int64_t) total_fingers_found,
3515 total_fingers_found = 0;
3519 struct FingerInfo prev_finger;
3520 prev_finger = finger_table[finger_table_index - 1];
3521 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3522 &prev_finger.finger_identity))
3524 current_search_finger_index--;
3529 total_fingers_found++;
3530 existing_finger = &finger_table[finger_table_index];
3532 /* No entry present in finger_table for given finger map index. */
3533 if (GNUNET_NO == existing_finger->is_present)
3535 add_new_finger (finger_identity, finger_trail,
3536 finger_trail_length,
3537 finger_trail_id, finger_table_index);
3538 update_current_search_finger_index (finger_table_index);
3542 /* If existing entry and finger identity are not same. */
3543 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3546 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3551 /* If the new finger is the closest peer. */
3552 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer))
3554 remove_existing_finger (existing_finger, finger_table_index);
3555 add_new_finger (finger_identity, finger_trail, finger_trail_length,
3556 finger_trail_id, finger_table_index);
3557 // if ((0 == finger_table_index) && (1 == waiting_for_notify_confirmation))
3559 // /* SUPUS: We have removed our successor, but we are still waiting for a
3560 // * confirmation. As we have removed successor, then it does not make
3561 // sense to wait for the new successor. */
3562 // waiting_for_notify_confirmation = 0;
3567 /* Existing finger is the closest one. We need to send trail teardown
3568 across the trail setup in routing table of all the peers. */
3569 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3571 if (finger_trail_length > 0)
3572 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3573 GDS_ROUTING_SRC_TO_DEST,
3576 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3577 GDS_ROUTING_SRC_TO_DEST,
3584 /* If both new and existing entry are same as my_identity, then do nothing. */
3585 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3591 /* If there is space to store more trails. */
3592 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3593 add_new_trail (existing_finger, finger_trail,
3594 finger_trail_length, finger_trail_id);
3596 select_and_replace_trail (existing_finger, finger_trail,
3597 finger_trail_length, finger_trail_id);
3599 update_current_search_finger_index (finger_table_index);
3605 * FIXME: Check for loop in the request. If you already are part of put path,
3606 * then you need to reset the put path length.
3607 * Core handler for P2P put messages.
3608 * @param cls closure
3609 * @param peer sender of the request
3610 * @param message message
3611 * @return #GNUNET_OK to keep the connection open,
3612 * #GNUNET_SYSERR to close it (signal serious error)
3615 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3616 const struct GNUNET_MessageHeader *message)
3618 struct PeerPutMessage *put;
3619 struct GNUNET_PeerIdentity *put_path;
3620 struct GNUNET_PeerIdentity current_best_known_dest;
3621 struct GNUNET_PeerIdentity best_known_dest;
3622 struct GNUNET_HashCode received_intermediate_trail_id;
3623 struct GNUNET_HashCode intermediate_trail_id;
3624 struct GNUNET_PeerIdentity *next_hop;
3625 struct GNUNET_PeerIdentity *next_routing_hop;
3626 enum GNUNET_DHT_RouteOption options;
3627 struct GNUNET_HashCode test_key;
3632 size_t payload_size;
3635 #if ENABLE_MALICIOUS
3636 if(1 == act_malicious)
3638 DEBUG("I am malicious,dropping put request. \n");
3643 msize = ntohs (message->size);
3644 if (msize < sizeof (struct PeerPutMessage))
3646 GNUNET_break_op (0);
3650 put = (struct PeerPutMessage *) message;
3651 putlen = ntohl (put->put_path_length);
3653 sizeof (struct PeerPutMessage) +
3654 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3656 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3658 GNUNET_break_op (0);
3662 GNUNET_STATISTICS_update (GDS_stats,
3664 ("# Bytes received from other peers"), (int64_t) msize,
3667 current_best_known_dest = put->best_known_destination;
3668 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3669 payload = &put_path[putlen];
3670 options = ntohl (put->options);
3671 received_intermediate_trail_id = put->intermediate_trail_id;
3672 hop_count = ntohl(put->hop_count);
3673 payload_size = msize - (sizeof (struct PeerPutMessage) +
3674 putlen * sizeof (struct GNUNET_PeerIdentity));
3676 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3677 payload, payload_size, &test_key))
3680 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3682 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3683 GNUNET_break_op (0);
3684 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3685 "PUT with key `%s' for block with key %s\n",
3686 put_s, GNUNET_h2s_full (&test_key));
3687 GNUNET_free (put_s);
3692 GNUNET_break_op (0);
3695 /* cannot verify, good luck */
3699 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3701 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3702 ntohl (put->block_type),
3704 NULL, 0, /* bloom filer */
3705 NULL, 0, /* xquery */
3706 payload, payload_size))
3708 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3709 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3712 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3713 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3714 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3715 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3716 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3717 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3719 GNUNET_break_op (0);
3724 /* Check if you are already a part of put path. */
3726 for (i = 0; i < putlen; i++)
3728 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3735 /* Add yourself to the list. */
3736 struct GNUNET_PeerIdentity pp[putlen + 1];
3737 //if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3740 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3741 pp[putlen] = my_identity;
3747 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3748 struct Closest_Peer successor;
3749 key_value = GNUNET_ntohll (key_value);
3750 successor = find_local_best_known_next_hop (key_value,
3751 GDS_FINGER_TYPE_NON_PREDECESSOR);
3752 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3753 *next_hop = successor.next_hop;
3754 intermediate_trail_id = successor.trail_id;
3755 best_known_dest = successor.best_known_destination;
3757 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3759 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3760 GDS_ROUTING_SRC_TO_DEST);
3761 if (NULL != next_routing_hop)
3763 next_hop = next_routing_hop;
3764 intermediate_trail_id = received_intermediate_trail_id;
3765 best_known_dest = current_best_known_dest;
3769 GDS_CLIENTS_process_put (options,
3770 ntohl (put->block_type),
3772 ntohl (put->desired_replication_level),
3774 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3779 /* I am the final destination */
3780 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3782 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3783 &(put->key),putlen, pp, ntohl (put->block_type),
3784 payload_size, payload);
3788 GDS_NEIGHBOURS_send_put (&put->key,
3789 ntohl (put->block_type),ntohl (put->options),
3790 ntohl (put->desired_replication_level),
3791 best_known_dest, intermediate_trail_id, next_hop,
3792 hop_count, putlen, pp,
3793 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3794 payload, payload_size);
3801 * FIXME: Check for loop in the request. If you already are part of get path,
3802 * then you need to reset the get path length.
3803 * Core handler for p2p get requests.
3805 * @param cls closure
3806 * @param peer sender of the request
3807 * @param message message
3808 * @return #GNUNET_OK to keep the connection open,
3809 * #GNUNET_SYSERR to close it (signal serious error)
3812 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3813 const struct GNUNET_MessageHeader *message)
3815 const struct PeerGetMessage *get;
3816 const struct GNUNET_PeerIdentity *get_path;
3817 struct GNUNET_PeerIdentity best_known_dest;
3818 struct GNUNET_PeerIdentity current_best_known_dest;
3819 struct GNUNET_HashCode intermediate_trail_id;
3820 struct GNUNET_HashCode received_intermediate_trail_id;
3821 struct Closest_Peer successor;
3822 struct GNUNET_PeerIdentity *next_hop;
3823 struct GNUNET_PeerIdentity *next_routing_hop;
3824 uint32_t get_length;
3829 #if ENABLE_MALICIOUS
3830 if(1 == act_malicious)
3832 DEBUG("I am malicious,dropping get request. \n");
3837 msize = ntohs (message->size);
3838 if (msize < sizeof (struct PeerGetMessage))
3840 GNUNET_break_op (0);
3844 get = (const struct PeerGetMessage *)message;
3845 get_length = ntohl (get->get_path_length);
3846 current_best_known_dest = get->best_known_destination;
3847 received_intermediate_trail_id = get->intermediate_trail_id;
3848 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3849 hop_count = get->hop_count;
3853 sizeof (struct PeerGetMessage) +
3854 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3856 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3858 GNUNET_break_op (0);
3862 GNUNET_STATISTICS_update (GDS_stats,
3864 ("# Bytes received from other peers"), msize,
3867 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3868 key_value = GNUNET_ntohll (key_value);
3870 /* Check if you are already a part of get path. */
3872 for (i = 0; i < get_length; i++)
3874 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &get_path[i]))
3881 /* Add yourself in the get path. */
3882 struct GNUNET_PeerIdentity gp[get_length + 1];
3883 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3884 gp[get_length] = my_identity;
3885 get_length = get_length + 1;
3886 GDS_CLIENTS_process_get (get->options, get->block_type, hop_count,
3887 get->desired_replication_level, get->get_path_length,
3891 successor = find_local_best_known_next_hop (key_value,
3892 GDS_FINGER_TYPE_NON_PREDECESSOR);
3893 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3894 *next_hop = successor.next_hop;
3895 best_known_dest = successor.best_known_destination;
3896 intermediate_trail_id = successor.trail_id;
3897 /* I am not the final destination. I am part of trail to reach final dest. */
3898 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3900 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3901 GDS_ROUTING_SRC_TO_DEST);
3902 if (NULL != next_routing_hop)
3904 next_hop = next_routing_hop;
3905 best_known_dest = current_best_known_dest;
3906 intermediate_trail_id = received_intermediate_trail_id;
3911 /* I am the final destination. */
3912 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3914 if (1 == get_length)
3916 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0,
3917 NULL, 0, 1, &my_identity, NULL,&my_identity);
3921 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3922 get_length, gp, &gp[get_length - 2],
3928 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3929 get->desired_replication_level, best_known_dest,
3930 intermediate_trail_id, next_hop, hop_count,
3938 * Core handler for get result
3939 * @param cls closure
3940 * @param peer sender of the request
3941 * @param message message
3942 * @return #GNUNET_OK to keep the connection open,
3943 * #GNUNET_SYSERR to close it (signal serious error)
3946 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3947 const struct GNUNET_MessageHeader *message)
3949 const struct PeerGetResultMessage *get_result;
3950 const struct GNUNET_PeerIdentity *get_path;
3951 const struct GNUNET_PeerIdentity *put_path;
3952 const void *payload;
3953 size_t payload_size;
3955 unsigned int getlen;
3956 unsigned int putlen;
3957 int current_path_index;
3959 msize = ntohs (message->size);
3960 if (msize < sizeof (struct PeerGetResultMessage))
3962 GNUNET_break_op (0);
3966 get_result = (const struct PeerGetResultMessage *)message;
3967 getlen = ntohl (get_result->get_path_length);
3968 putlen = ntohl (get_result->put_path_length);
3971 sizeof (struct PeerGetResultMessage) +
3972 getlen * sizeof (struct GNUNET_PeerIdentity) +
3973 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3975 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3977 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3979 GNUNET_break_op (0);
3982 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3983 GNUNET_STATISTICS_update (GDS_stats,
3985 ("# Bytes received from other peers"), msize,
3988 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3989 get_path = &put_path[putlen];
3990 payload = (const void *) &get_path[getlen];
3991 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3992 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3994 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3996 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3997 getlen, get_path, putlen,
3998 put_path, get_result->type, payload_size, payload);
4003 current_path_index = search_my_index (get_path, getlen);
4004 if (-1 == current_path_index )
4006 DEBUG ("No entry found in get path.\n");
4008 return GNUNET_SYSERR;
4010 if((getlen + 1) == current_path_index)
4012 DEBUG("Present twice in get path. Not allowed. \n");
4014 return GNUNET_SYSERR;
4016 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
4017 &get_path[current_path_index - 1],
4018 &(get_result->querying_peer), putlen, put_path,
4019 getlen, get_path, get_result->expiration_time,
4020 payload, payload_size);
4023 return GNUNET_SYSERR;
4028 * Find the next hop to pass trail setup message. First find the local best known
4029 * hop from your own identity, friends and finger. If you were part of trail,
4030 * then get the next hop from routing table. Compare next_hop from routing table
4031 * and local best known hop, and return the closest one to final_dest_finger_val
4032 * @param final_dest_finger_val 64 bit value of finger identity
4033 * @param intermediate_trail_id If you are part of trail to reach to some other
4034 * finger, then it is the trail id to reach to
4035 * that finger, else set to 0.
4036 * @param is_predecessor Are we looking for closest successor or predecessor.
4037 * @param source Source of trail setup message.
4038 * @param current_dest In case you are part of trail, then finger to which
4039 * we should forward the message. Else my own identity
4040 * @return Closest Peer for @a final_dest_finger_val
4042 static struct Closest_Peer
4043 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
4044 struct GNUNET_HashCode intermediate_trail_id,
4045 unsigned int is_predecessor,
4046 struct GNUNET_PeerIdentity source,
4047 struct GNUNET_PeerIdentity *current_dest)
4049 struct Closest_Peer peer;
4051 peer = find_local_best_known_next_hop (final_dest_finger_val, is_predecessor);
4053 /* Am I just a part of a trail towards a finger (current_destination)? */
4054 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
4055 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
4058 struct GNUNET_PeerIdentity closest_peer;
4060 /* Select best successor among one found locally and current_destination
4061 * that we got from network.*/
4062 closest_peer = select_closest_peer (&peer.best_known_destination,
4064 final_dest_finger_val,
4067 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
4068 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
4070 struct GNUNET_PeerIdentity *next_hop;
4072 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4073 GDS_ROUTING_SRC_TO_DEST);
4074 /* next_hop NULL is a valid case. This intermediate trail id is set by
4075 some other finger, and while this trail setup is in progress, that other
4076 peer might have found a better trail ,and send trail teardown message
4077 across the network. In case we got the trail teardown message first,
4078 then next_hop will be NULL. A possible solution could be to keep track
4079 * of all removed trail id, and be sure that there is no other reason . */
4080 if(NULL != next_hop)
4082 peer.next_hop = *next_hop;
4083 peer.best_known_destination = *current_dest;
4084 peer.trail_id = intermediate_trail_id;
4093 * Core handle for PeerTrailSetupMessage.
4094 * @param cls closure
4095 * @param message message
4096 * @param peer peer identity this notification is about
4097 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4100 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
4101 const struct GNUNET_MessageHeader *message)
4103 const struct PeerTrailSetupMessage *trail_setup;
4104 const struct GNUNET_PeerIdentity *trail_peer_list;
4105 struct GNUNET_PeerIdentity current_dest;
4106 struct FriendInfo *target_friend;
4107 struct GNUNET_PeerIdentity source;
4108 struct GNUNET_HashCode intermediate_trail_id;
4109 struct GNUNET_HashCode trail_id;
4110 unsigned int is_predecessor;
4111 uint32_t trail_length;
4112 uint64_t final_dest_finger_val;
4116 msize = ntohs (message->size);
4117 if (msize < sizeof (struct PeerTrailSetupMessage))
4119 GNUNET_break_op (0);
4120 return GNUNET_SYSERR;
4123 trail_setup = (const struct PeerTrailSetupMessage *) message;
4124 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4125 sizeof (struct GNUNET_PeerIdentity) != 0)
4127 GNUNET_break_op (0);
4130 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4131 sizeof (struct GNUNET_PeerIdentity);
4133 GNUNET_STATISTICS_update (GDS_stats,
4135 ("# Bytes received from other peers"), msize,
4138 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4139 current_dest = trail_setup->best_known_destination;
4140 trail_id = trail_setup->trail_id;
4141 final_dest_finger_val =
4142 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4143 source = trail_setup->source_peer;
4144 is_predecessor = ntohl (trail_setup->is_predecessor);
4145 intermediate_trail_id = trail_setup->intermediate_trail_id;
4147 /* Did the friend insert its ID in the trail list? */
4148 if (trail_length > 0 &&
4149 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
4151 GNUNET_break_op (0);
4152 return GNUNET_SYSERR;
4155 /* If I was the source and got the message back, then set trail length to 0.*/
4156 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4161 /* Check if you are present in the trail seen so far? */
4162 for (i = 0; i < trail_length ; i++)
4164 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4166 /* We will add ourself later in code, if NOT destination. */
4172 /* Is my routing table full? */
4173 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4175 if (trail_length > 0)
4177 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4178 &trail_peer_list[trail_length - 1]);
4181 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4183 if(NULL == target_friend)
4185 DEBUG ("\n friend not found");
4189 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4190 my_identity, is_predecessor,
4191 trail_peer_list, trail_length,
4192 trail_id, target_friend,
4193 CONGESTION_TIMEOUT);
4197 /* Get the next hop to forward the trail setup request. */
4198 struct Closest_Peer next_peer =
4199 get_local_best_known_next_hop (final_dest_finger_val,
4200 intermediate_trail_id,
4205 /* Am I the final destination? */
4206 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4209 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4211 finger_table_add (my_identity, NULL, 0, is_predecessor,
4212 final_dest_finger_val, trail_id);
4216 if (trail_length > 0)
4218 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4219 &trail_peer_list[trail_length-1]);
4222 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4223 if (NULL == target_friend)
4225 GNUNET_break_op (0);
4226 return GNUNET_SYSERR;
4228 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4229 GDS_NEIGHBOURS_send_trail_setup_result (source,
4231 target_friend, trail_length,
4234 final_dest_finger_val,trail_id);
4236 else /* I'm not the final destination. */
4238 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4239 &next_peer.next_hop);
4240 if(NULL == target_friend)
4242 DEBUG ("\n target friend not found for peer = %s", GNUNET_i2s(&next_peer.next_hop));
4246 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4248 /* Add yourself to list of peers. */
4249 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4251 memcpy (peer_list, trail_peer_list,
4252 trail_length * sizeof (struct GNUNET_PeerIdentity));
4253 peer_list[trail_length] = my_identity;
4254 GDS_NEIGHBOURS_send_trail_setup (source,
4255 final_dest_finger_val,
4256 next_peer.best_known_destination,
4257 target_friend, trail_length + 1, peer_list,
4258 is_predecessor, trail_id,
4259 next_peer.trail_id);
4262 GDS_NEIGHBOURS_send_trail_setup (source,
4263 final_dest_finger_val,
4264 next_peer.best_known_destination,
4265 target_friend, 0, NULL,
4266 is_predecessor, trail_id,
4267 next_peer.trail_id);
4274 * Core handle for p2p trail setup result messages.
4276 * @param message message
4277 * @param peer sender of this message.
4278 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4281 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4282 const struct GNUNET_MessageHeader *message)
4284 const struct PeerTrailSetupResultMessage *trail_result;
4285 const struct GNUNET_PeerIdentity *trail_peer_list;
4286 struct GNUNET_PeerIdentity next_hop;
4287 struct FriendInfo *target_friend;
4288 struct GNUNET_PeerIdentity querying_peer;
4289 struct GNUNET_PeerIdentity finger_identity;
4290 uint32_t trail_length;
4291 uint64_t ulitmate_destination_finger_value;
4292 uint32_t is_predecessor;
4293 struct GNUNET_HashCode trail_id;
4297 msize = ntohs (message->size);
4298 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4300 GNUNET_break_op (0);
4304 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4305 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4306 sizeof (struct GNUNET_PeerIdentity) != 0)
4308 GNUNET_break_op (0);
4311 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4312 sizeof (struct GNUNET_PeerIdentity);
4314 GNUNET_STATISTICS_update (GDS_stats,
4316 ("# Bytes received from other peers"), msize,
4319 is_predecessor = ntohl (trail_result->is_predecessor);
4320 querying_peer = trail_result->querying_peer;
4321 finger_identity = trail_result->finger_identity;
4322 trail_id = trail_result->trail_id;
4323 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4324 ulitmate_destination_finger_value =
4325 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4327 /* Am I the one who initiated the query? */
4328 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4330 /* Check that you got the message from the correct peer. */
4331 if (trail_length > 0)
4333 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4338 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4341 GDS_ROUTING_add (trail_id, my_identity, *peer);
4342 finger_table_add (finger_identity, trail_peer_list, trail_length,
4343 is_predecessor, ulitmate_destination_finger_value, trail_id);
4347 /* Get my location in the trail. */
4348 my_index = search_my_index (trail_peer_list, trail_length);
4351 DEBUG ("Not found in trail\n");
4353 return GNUNET_SYSERR;
4356 if ((trail_length + 1) == my_index)
4358 DEBUG ("Found twice in trail.\n");
4360 return GNUNET_SYSERR;
4363 //TODO; Refactor code here and above to check if sender peer is correct
4366 if(trail_length > 1)
4367 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4370 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4372 next_hop = trail_result->querying_peer;
4376 if(my_index == trail_length - 1)
4379 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4384 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4386 next_hop = trail_peer_list[my_index - 1];
4389 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4390 if (NULL == target_friend)
4392 GNUNET_break_op (0);
4393 return GNUNET_SYSERR;
4395 GDS_ROUTING_add (trail_id, next_hop, *peer);
4396 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4397 target_friend, trail_length, trail_peer_list,
4399 ulitmate_destination_finger_value,
4407 * @param trail Trail to be inverted
4408 * @param trail_length Total number of peers in the trail.
4409 * @return Updated trail
4411 static struct GNUNET_PeerIdentity *
4412 invert_trail (const struct GNUNET_PeerIdentity *trail,
4413 unsigned int trail_length)
4417 struct GNUNET_PeerIdentity *inverted_trail;
4419 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4422 j = trail_length - 1;
4423 while (i < trail_length)
4425 inverted_trail[i] = trail[j];
4430 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4431 &inverted_trail[0]));
4432 return inverted_trail;
4437 * Return the shortest trail among all the trails to reach to finger from me.
4438 * @param finger Finger
4439 * @param shortest_trail_length[out] Trail length of shortest trail from me
4441 * @return Shortest trail.
4443 static struct GNUNET_PeerIdentity *
4444 get_shortest_trail (struct FingerInfo *finger,
4445 unsigned int *trail_length)
4447 struct Trail *trail;
4448 unsigned int flag = 0;
4449 unsigned int shortest_trail_index = 0;
4450 int shortest_trail_length = -1;
4451 struct Trail_Element *trail_element;
4452 struct GNUNET_PeerIdentity *trail_list;
4455 trail = GNUNET_new (struct Trail);
4457 /* Get the shortest trail to reach to current successor. */
4458 for (i = 0; i < finger->trails_count; i++)
4460 trail = &finger->trail_list[i];
4464 shortest_trail_index = i;
4465 shortest_trail_length = trail->trail_length;
4470 if (shortest_trail_length > trail->trail_length)
4472 shortest_trail_index = i;
4473 shortest_trail_length = trail->trail_length;
4478 /* Copy the shortest trail and return. */
4479 trail = &finger->trail_list[shortest_trail_index];
4480 trail_element = trail->trail_head;
4482 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4483 shortest_trail_length);
4485 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4487 trail_list[i] = trail_element->peer;
4490 GNUNET_assert(shortest_trail_length != -1);
4492 *trail_length = shortest_trail_length;
4498 * Check if trail_1 and trail_2 have any common element. If yes then join
4499 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4500 * @param trail_1 Trail from source to me, NOT including endpoints.
4501 * @param trail_1_len Total number of peers @a trail_1
4502 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4503 * @param trail_2_len Total number of peers @a trail_2
4504 * @param joined_trail_len Total number of peers in combined trail of trail_1
4506 * @return Joined trail.
4508 static struct GNUNET_PeerIdentity *
4509 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4510 unsigned int trail_1_len,
4511 struct GNUNET_PeerIdentity *trail_2,
4512 unsigned int trail_2_len,
4513 unsigned int *joined_trail_len)
4515 struct GNUNET_PeerIdentity *joined_trail;
4520 for (i = 0; i < trail_1_len; i++)
4522 for (j = 0; j < trail_2_len; j++)
4524 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4527 *joined_trail_len = i + (trail_2_len - j);
4528 joined_trail = GNUNET_malloc (*joined_trail_len *
4529 sizeof(struct GNUNET_PeerIdentity));
4532 /* Copy all the elements from 0 to i into joined_trail. */
4533 for(k = 0; k < ( i+1); k++)
4535 joined_trail[k] = trail_1[k];
4538 /* Increment j as entry stored is same as entry stored at i*/
4541 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4542 while(k <= (*joined_trail_len - 1))
4544 joined_trail[k] = trail_2[j];
4549 return joined_trail;
4553 /* Here you should join the trails. */
4554 *joined_trail_len = trail_1_len + trail_2_len + 1;
4555 joined_trail = GNUNET_malloc (*joined_trail_len *
4556 sizeof(struct GNUNET_PeerIdentity));
4559 for(i = 0; i < trail_1_len;i++)
4561 joined_trail[i] = trail_1[i];
4564 joined_trail[i] = my_identity;
4567 for (j = 0; i < *joined_trail_len; i++,j++)
4569 joined_trail[i] = trail_2[j];
4572 return joined_trail;
4577 * Return the trail from source to my current predecessor. Check if source
4578 * is already part of the this trail, if yes then return the shorten trail.
4579 * @param current_trail Trail from source to me, NOT including the endpoints.
4580 * @param current_trail_length Number of peers in @a current_trail.
4581 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4582 * source to my predecessor, NOT including
4584 * @return Trail from source to my predecessor.
4586 static struct GNUNET_PeerIdentity *
4587 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4588 const struct GNUNET_PeerIdentity *trail_src_to_me,
4589 unsigned int trail_src_to_me_len,
4590 unsigned int *trail_src_to_curr_pred_length)
4592 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4593 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4594 unsigned int trail_me_to_curr_pred_length;
4595 struct FingerInfo *current_predecessor;
4599 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4601 /* Check if trail_src_to_me contains current_predecessor. */
4602 for (i = 0; i < trail_src_to_me_len; i++)
4604 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4605 ¤t_predecessor->finger_identity))
4609 *trail_src_to_curr_pred_length = i;
4614 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4615 sizeof(struct GNUNET_PeerIdentity));
4616 for(j = 0; j < i;j++)
4617 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4618 return trail_src_to_curr_pred;
4622 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4623 &trail_me_to_curr_pred_length);
4625 /* Check if trail contains the source_peer. */
4626 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4628 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4629 &trail_me_to_curr_pred[i]))
4632 /* Source is NOT part of trail. */
4635 /* Source is the last element in the trail to reach to my pred.
4636 Source is direct friend of the pred. */
4637 if (trail_me_to_curr_pred_length == i)
4639 *trail_src_to_curr_pred_length = 0;
4643 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4644 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4645 *trail_src_to_curr_pred_length);
4647 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4649 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4651 GNUNET_free_non_null(trail_me_to_curr_pred);
4652 return trail_src_to_curr_pred;
4656 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4657 trail_src_to_me_len,
4658 trail_me_to_curr_pred,
4659 trail_me_to_curr_pred_length,
4661 *trail_src_to_curr_pred_length = len;
4662 GNUNET_free_non_null(trail_me_to_curr_pred);
4663 return trail_src_to_curr_pred;
4668 * Add finger as your predecessor. To add, first generate a new trail id, invert
4669 * the trail to get the trail from me to finger, add an entry in your routing
4670 * table, send add trail message to peers which are part of trail from me to
4671 * finger and add finger in finger table.
4674 * @param trail_length
4677 update_predecessor (struct GNUNET_PeerIdentity finger,
4678 struct GNUNET_PeerIdentity *trail,
4679 unsigned int trail_length)
4681 struct GNUNET_HashCode trail_to_new_predecessor_id;
4682 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4683 struct FriendInfo *target_friend;
4685 /* Generate trail id for trail from me to new predecessor = finger. */
4686 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4687 &trail_to_new_predecessor_id,
4688 sizeof (trail_to_new_predecessor_id));
4690 if (0 == trail_length)
4692 trail_to_new_predecessor = NULL;
4693 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4694 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger);
4695 if (NULL == target_friend)
4703 /* Invert the trail to get the trail from me to finger, NOT including the
4705 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4706 &trail[trail_length-1]));
4707 trail_to_new_predecessor = invert_trail (trail, trail_length);
4709 /* Add an entry in your routing table. */
4710 GDS_ROUTING_add (trail_to_new_predecessor_id,
4712 trail_to_new_predecessor[0]);
4714 GNUNET_assert (NULL != (target_friend =
4715 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4716 &trail_to_new_predecessor[0])));
4719 /* Add entry in routing table of all peers that are part of trail from me
4720 to finger, including finger. */
4721 GDS_NEIGHBOURS_send_add_trail (my_identity,
4723 trail_to_new_predecessor_id,
4724 trail_to_new_predecessor,
4728 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4729 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4730 GNUNET_free_non_null(trail_to_new_predecessor);
4735 * Check if you already have a predecessor. If not then add finger as your
4736 * predecessor. If you have predecessor, then compare two peer identites.
4737 * If finger is correct predecessor, then remove the old entry, add finger in
4738 * finger table and send add_trail message to add the trail in the routing
4739 * table of all peers which are part of trail to reach from me to finger.
4740 * @param finger New peer which may be our predecessor.
4741 * @param trail List of peers to reach from @finger to me.
4742 * @param trail_length Total number of peer in @a trail.
4745 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4746 struct GNUNET_PeerIdentity *trail,
4747 unsigned int trail_length)
4749 struct FingerInfo *current_predecessor;
4750 struct GNUNET_PeerIdentity closest_peer;
4751 uint64_t predecessor_value;
4752 unsigned int is_predecessor = 1;
4754 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4755 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4757 /* No predecessor. Add finger as your predecessor. */
4758 if (GNUNET_NO == current_predecessor->is_present)
4760 update_predecessor (finger, trail, trail_length);
4764 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4770 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4771 closest_peer = select_closest_peer (&finger,
4772 ¤t_predecessor->finger_identity,
4773 predecessor_value, is_predecessor);
4775 /* Finger is the closest predecessor. Remove the existing one and add the new
4777 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4779 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4780 update_predecessor (finger, trail, trail_length);
4788 * Core handle for p2p verify successor messages.
4789 * @param cls closure
4790 * @param message message
4791 * @param peer peer identity this notification is about
4792 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4795 handle_dht_p2p_verify_successor(void *cls,
4796 const struct GNUNET_PeerIdentity *peer,
4797 const struct GNUNET_MessageHeader *message)
4799 const struct PeerVerifySuccessorMessage *vsm;
4800 struct GNUNET_HashCode trail_id;
4801 struct GNUNET_PeerIdentity successor;
4802 struct GNUNET_PeerIdentity source_peer;
4803 struct GNUNET_PeerIdentity *trail;
4804 struct GNUNET_PeerIdentity *next_hop;
4805 struct FingerInfo current_predecessor;
4806 struct FriendInfo *target_friend;
4807 unsigned int trail_src_to_curr_pred_len = 0;
4808 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4809 unsigned int trail_length;
4812 msize = ntohs (message->size);
4814 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4816 GNUNET_break_op (0);
4820 vsm = (const struct PeerVerifySuccessorMessage *) message;
4821 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4822 sizeof (struct GNUNET_PeerIdentity);
4823 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4824 sizeof (struct GNUNET_PeerIdentity) != 0)
4826 GNUNET_break_op (0);
4830 GNUNET_STATISTICS_update (GDS_stats,
4832 ("# Bytes received from other peers"), msize,
4835 trail_id = vsm->trail_id;
4836 source_peer = vsm->source_peer;
4837 successor = vsm->successor;
4838 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4840 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4842 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4844 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4845 if (NULL == next_hop)
4850 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4852 if(NULL == target_friend)
4857 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4858 trail_id, trail, trail_length,
4863 /* I am the destination of this message. */
4865 /* Check if the source_peer could be our predecessor and if yes then update
4867 compare_and_update_predecessor (source_peer, trail, trail_length);
4868 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4870 /* Is source of this message NOT my predecessor. */
4871 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4874 trail_src_to_curr_pred =
4875 get_trail_src_to_curr_pred (source_peer,
4878 &trail_src_to_curr_pred_len);
4882 trail_src_to_curr_pred_len = trail_length;
4885 trail_src_to_curr_pred =
4886 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4887 *trail_src_to_curr_pred_len);
4888 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4890 trail_src_to_curr_pred[i] = trail[i];
4894 GNUNET_assert (NULL !=
4896 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4897 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4898 current_predecessor.finger_identity,
4899 trail_id, trail_src_to_curr_pred,
4900 trail_src_to_curr_pred_len,
4901 GDS_ROUTING_DEST_TO_SRC,
4903 GNUNET_free_non_null(trail_src_to_curr_pred);
4909 * If the trail from me to my probable successor contains a friend not
4910 * at index 0, then we can shorten the trail.
4911 * @param probable_successor Peer which is our probable successor
4912 * @param trail_me_to_probable_successor Peers in path from me to my probable
4913 * successor, NOT including the endpoints.
4914 * @param trail_me_to_probable_successor_len Total number of peers in
4915 * @a trail_me_to_probable_succesor.
4916 * @return Updated trail, if any friend found.
4917 * Else the trail_me_to_probable_successor.
4919 struct GNUNET_PeerIdentity *
4920 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4921 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4922 unsigned int trail_me_to_probable_successor_len,
4923 unsigned int *trail_to_new_successor_length)
4927 struct GNUNET_PeerIdentity *trail_to_new_successor;
4929 /* Probable successor is a friend */
4930 /* SUPUS: Here should I worry about friend,*/
4931 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4932 &probable_successor))
4934 trail_to_new_successor = NULL;
4935 *trail_to_new_successor_length = 0;
4936 return trail_to_new_successor;
4939 /* Is there any friend of yours in this trail. */
4940 if(trail_me_to_probable_successor_len > 1)
4942 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4944 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4945 &trail_me_to_probable_successor[i]))
4948 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4949 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4950 *trail_to_new_successor_length);
4953 for(j = 0; j < *trail_to_new_successor_length; i++,j++)
4955 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4958 return trail_to_new_successor;
4962 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4963 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4967 struct SendNotifyContext
4969 struct GNUNET_PeerIdentity source_peer;
4970 struct GNUNET_PeerIdentity successor;
4971 struct GNUNET_PeerIdentity *successor_trail;
4972 unsigned int successor_trail_length;
4973 struct GNUNET_HashCode succesor_trail_id;
4974 struct FriendInfo *target_friend;
4975 unsigned int num_retries_scheduled;
4979 send_notify_new_successor (void *cls,
4980 const struct GNUNET_SCHEDULER_TaskContext
4984 * Check if the peer which sent us verify successor result message is still ours
4985 * successor or not. If not, then compare existing successor and probable successor.
4986 * In case probable successor is the correct successor, remove the existing
4987 * successor. Add probable successor as new successor. Send notify new successor
4988 * message to new successor.
4989 * @param curr_succ Peer to which we sent the verify successor message. It may
4990 * or may not be our real current successor, as we may have few iterations of
4991 * find finger trail task.
4992 * @param probable_successor Peer which should be our successor accroding to @a
4994 * @param trail List of peers to reach from me to @a probable successor, NOT including
4996 * @param trail_length Total number of peers in @a trail.
4999 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
5000 struct GNUNET_PeerIdentity probable_successor,
5001 const struct GNUNET_PeerIdentity *trail,
5002 unsigned int trail_length)
5004 struct FingerInfo *current_successor;
5005 struct GNUNET_PeerIdentity closest_peer;
5006 struct GNUNET_HashCode trail_id;
5007 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
5008 struct FriendInfo *target_friend;
5009 unsigned int trail_me_to_probable_succ_len;
5010 unsigned int is_predecessor = 0;
5011 uint64_t successor_value;
5013 current_successor = &finger_table[0];
5014 successor_value = compute_finger_identity_value(0);
5016 /* If probable successor is same as current_successor, do nothing. */
5017 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
5018 ¤t_successor->finger_identity))
5020 if ((NULL != GDS_stats))
5026 memcpy (&my_id, &my_identity, sizeof(uint64_t));
5027 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5028 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5029 succ = GNUNET_ntohll(succ);
5030 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5031 GNUNET_free (my_id_str);
5033 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5036 if (send_verify_successor_task == GNUNET_SCHEDULER_NO_TASK)
5037 send_verify_successor_task =
5038 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5039 &send_verify_successor_message,
5043 closest_peer = select_closest_peer (&probable_successor,
5044 ¤t_successor->finger_identity,
5045 successor_value, is_predecessor);
5047 /* If the current_successor in the finger table is closest, then do nothing. */
5048 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
5049 ¤t_successor->finger_identity))
5051 //FIXME: Is this a good place to return the stats.
5052 if ((NULL != GDS_stats))
5058 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5059 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5060 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5061 GNUNET_free (my_id_str);
5062 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5066 if(0 == successor_times)
5068 // successor_times = 3;
5069 verify_successor_next_send_time =
5070 GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time);
5076 if (send_verify_successor_task == GNUNET_SCHEDULER_NO_TASK)
5077 send_verify_successor_task =
5078 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5079 &send_verify_successor_message,
5084 /* Probable successor is the closest peer.*/
5085 if(trail_length > 0)
5087 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5092 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5093 &probable_successor));
5096 trail_me_to_probable_succ_len = 0;
5097 trail_me_to_probable_succ =
5098 check_trail_me_to_probable_succ (probable_successor,
5099 trail, trail_length,
5100 &trail_me_to_probable_succ_len);
5102 /* Remove the existing successor. */
5103 remove_existing_finger (current_successor, 0);
5104 /* Generate a new trail id to reach to your new successor. */
5105 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5106 &trail_id, sizeof (trail_id));
5108 if (trail_me_to_probable_succ_len > 0)
5110 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
5111 GNUNET_assert (NULL !=
5113 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5114 &trail_me_to_probable_succ[0])));
5118 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5119 GNUNET_assert (NULL !=
5121 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5122 &probable_successor)));
5125 add_new_finger (probable_successor, trail_me_to_probable_succ,
5126 trail_me_to_probable_succ_len, trail_id, 0);
5128 struct SendNotifyContext *notify_ctx;
5130 notify_ctx = GNUNET_new(struct SendNotifyContext);
5132 notify_ctx->source_peer = my_identity;
5133 notify_ctx->successor = probable_successor;
5134 notify_ctx->successor_trail =
5135 GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5136 memcpy(notify_ctx->successor_trail, trail_me_to_probable_succ,
5137 sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5138 notify_ctx->successor_trail_length = trail_me_to_probable_succ_len;
5139 notify_ctx->succesor_trail_id = trail_id;
5140 notify_ctx->target_friend = target_friend;
5141 notify_ctx->num_retries_scheduled = 0;
5143 // TODO: Check if we should verify before schedule if already scheduled.
5144 GNUNET_SCHEDULER_add_now(&send_notify_new_successor, (void*)notify_ctx);
5152 send_notify_new_successor (void *cls,
5153 const struct GNUNET_SCHEDULER_TaskContext
5156 struct SendNotifyContext *ctx = (struct SendNotifyContext *) cls;
5158 GDS_NEIGHBOURS_send_notify_new_successor (ctx->source_peer,
5160 ctx->successor_trail,
5161 ctx->successor_trail_length,
5162 ctx->succesor_trail_id,
5163 ctx->target_friend);
5165 if (0 == ctx->num_retries_scheduled &&
5166 send_notify_new_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
5168 // Result from previous notify successos hasn't arrived, so the retry task
5169 // hasn't been cancelled! Already a new notify successor must be called.
5170 // We will cancel the retry request.
5171 struct SendNotifyContext *old_notify_ctx;
5172 old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5173 GNUNET_free (old_notify_ctx->successor_trail);
5174 GNUNET_free (old_notify_ctx);
5175 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
5178 ctx->num_retries_scheduled++;
5179 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_add_delayed(notify_successor_retry_time,
5180 &send_notify_new_successor,
5185 * Core handle for p2p verify successor result messages.
5186 * @param cls closure
5187 * @param message message
5188 * @param peer peer identity this notification is about
5189 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5192 handle_dht_p2p_verify_successor_result(void *cls,
5193 const struct GNUNET_PeerIdentity *peer,
5194 const struct GNUNET_MessageHeader *message)
5196 const struct PeerVerifySuccessorResultMessage *vsrm;
5197 enum GDS_ROUTING_trail_direction trail_direction;
5198 struct GNUNET_PeerIdentity querying_peer;
5199 struct GNUNET_HashCode trail_id;
5200 struct GNUNET_PeerIdentity *next_hop;
5201 struct FriendInfo *target_friend;
5202 struct GNUNET_PeerIdentity probable_successor;
5203 struct GNUNET_PeerIdentity current_successor;
5204 const struct GNUNET_PeerIdentity *trail;
5205 unsigned int trail_length;
5208 msize = ntohs (message->size);
5209 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5211 GNUNET_break_op (0);
5215 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5216 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5217 sizeof (struct GNUNET_PeerIdentity) != 0)
5219 GNUNET_break_op (0);
5222 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5223 sizeof (struct GNUNET_PeerIdentity);
5225 GNUNET_STATISTICS_update (GDS_stats,
5227 ("# Bytes received from other peers"), msize,
5230 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5231 querying_peer = vsrm->querying_peer;
5232 trail_direction = ntohl (vsrm->trail_direction);
5233 trail_id = vsrm->trail_id;
5234 probable_successor = vsrm->probable_successor;
5235 current_successor = vsrm->current_successor;
5237 /* I am the querying_peer. */
5238 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5240 /* Cancel Retry Task */
5241 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_retry_task)
5243 struct VerifySuccessorContext *ctx;
5244 ctx = GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
5246 send_verify_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
5248 compare_and_update_successor (current_successor,
5249 probable_successor, trail, trail_length);
5253 /*If you are not the querying peer then pass on the message */
5254 if(NULL == (next_hop =
5255 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
5257 /* Here it may happen that source peer has found a new successor, and removed
5258 the trail, Hence no entry found in the routing table. Fail silently.*/
5259 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5260 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5264 if (NULL == (target_friend =
5265 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5270 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5271 vsrm->current_successor,
5272 probable_successor, trail_id,
5275 trail_direction, target_friend);
5281 * Core handle for p2p notify new successor messages.
5282 * @param cls closure
5283 * @param message message
5284 * @param peer peer identity this notification is about
5285 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5288 handle_dht_p2p_notify_new_successor(void *cls,
5289 const struct GNUNET_PeerIdentity *peer,
5290 const struct GNUNET_MessageHeader *message)
5292 const struct PeerNotifyNewSuccessorMessage *nsm;
5293 struct GNUNET_PeerIdentity *trail;
5294 struct GNUNET_PeerIdentity source;
5295 struct GNUNET_PeerIdentity new_successor;
5296 struct GNUNET_HashCode trail_id;
5297 struct GNUNET_PeerIdentity next_hop;
5298 struct FriendInfo *target_friend;
5301 uint32_t trail_length;
5303 msize = ntohs (message->size);
5304 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5306 GNUNET_break_op (0);
5309 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5310 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5311 sizeof (struct GNUNET_PeerIdentity) != 0)
5313 GNUNET_break_op (0);
5316 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5317 sizeof (struct GNUNET_PeerIdentity);
5318 GNUNET_STATISTICS_update (GDS_stats,
5320 ("# Bytes received from other peers"), msize,
5323 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5324 source = nsm->source_peer;
5325 new_successor = nsm->new_successor;
5326 trail_id = nsm->trail_id;
5328 /* I am the new_successor to source_peer. */
5329 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5331 if(trail_length > 0)
5332 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5335 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5337 compare_and_update_predecessor (source, trail, trail_length);
5338 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5339 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5340 GDS_ROUTING_DEST_TO_SRC,
5345 GNUNET_assert(trail_length > 0);
5346 /* I am part of trail to reach to successor. */
5347 my_index = search_my_index (trail, trail_length);
5350 DEBUG ("No entry found in trail\n");
5351 GNUNET_break_op (0);
5352 return GNUNET_SYSERR;
5354 if((trail_length + 1) == my_index)
5356 DEBUG ("Found twice in trail.\n");
5357 GNUNET_break_op (0);
5358 return GNUNET_SYSERR;
5360 if ((trail_length-1) == my_index)
5361 next_hop = new_successor;
5363 next_hop = trail[my_index + 1];
5365 GDS_ROUTING_add(trail_id, *peer, next_hop);
5367 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
5368 if (NULL == target_friend)
5373 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5375 trail_id, target_friend);
5382 * Core handler for P2P notify successor message
5383 * @param cls closure
5384 * @param message message
5385 * @param peer peer identity this notification is about
5386 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5389 handle_dht_p2p_notify_succ_confirmation (void *cls,
5390 const struct GNUNET_PeerIdentity *peer,
5391 const struct GNUNET_MessageHeader *message)
5393 const struct PeerNotifyConfirmationMessage *notify_confirmation;
5394 enum GDS_ROUTING_trail_direction trail_direction;
5395 struct GNUNET_HashCode trail_id;
5396 struct FriendInfo *target_friend;
5397 struct GNUNET_PeerIdentity *next_hop;
5400 msize = ntohs (message->size);
5402 if (msize != sizeof (struct PeerNotifyConfirmationMessage))
5404 GNUNET_break_op (0);
5407 GNUNET_STATISTICS_update (GDS_stats,
5409 ("# Bytes received from other peers"), msize,
5412 notify_confirmation = (const struct PeerNotifyConfirmationMessage *) message;
5413 trail_direction = ntohl (notify_confirmation->trail_direction);
5414 trail_id = notify_confirmation->trail_id;
5416 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5417 if (NULL == next_hop)
5419 /* The source of notify new successor, might have found even a better
5420 successor. In that case it send a trail teardown message, and hence,
5421 the next hop is NULL. */
5422 //Fixme: Add some print to confirm the above theory.
5426 /* I peer which sent the notify successor message to the successor. */
5427 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5430 * Schedule another round of verify sucessor with your current successor
5431 * which may or may not be source of this message. This message is used
5432 * only to ensure that we have a path setup to reach to our successor.
5435 // TODO: cancel schedule of notify_successor_retry_task
5436 if (send_notify_new_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
5438 struct SendNotifyContext *notify_ctx;
5439 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5440 GNUNET_free (notify_ctx->successor_trail);
5441 GNUNET_free (notify_ctx);
5442 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
5444 if (send_verify_successor_task == GNUNET_SCHEDULER_NO_TASK)
5446 verify_successor_next_send_time.rel_value_us =
5447 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5448 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5449 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5450 send_verify_successor_task =
5451 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5452 &send_verify_successor_message,
5458 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
5459 if (NULL == target_friend)
5461 DEBUG ("\n friend not found, line number = %d",__LINE__);
5462 return GNUNET_SYSERR;
5464 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5465 GDS_ROUTING_DEST_TO_SRC,
5473 * Core handler for P2P trail rejection message
5474 * @param cls closure
5475 * @param message message
5476 * @param peer peer identity this notification is about
5477 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5480 handle_dht_p2p_trail_setup_rejection (void *cls,
5481 const struct GNUNET_PeerIdentity *peer,
5482 const struct GNUNET_MessageHeader *message)
5484 const struct PeerTrailRejectionMessage *trail_rejection;
5485 unsigned int trail_length;
5486 const struct GNUNET_PeerIdentity *trail_peer_list;
5487 struct FriendInfo *target_friend;
5488 struct GNUNET_TIME_Relative congestion_timeout;
5489 struct GNUNET_HashCode trail_id;
5490 struct GNUNET_PeerIdentity next_peer;
5491 struct GNUNET_PeerIdentity source;
5492 uint64_t ultimate_destination_finger_value;
5493 unsigned int is_predecessor;
5496 msize = ntohs (message->size);
5497 if (msize < sizeof (struct PeerTrailRejectionMessage))
5499 GNUNET_break_op (0);
5502 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5503 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5504 sizeof (struct GNUNET_PeerIdentity) != 0)
5506 GNUNET_break_op (0);
5509 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5510 sizeof (struct GNUNET_PeerIdentity);
5511 GNUNET_STATISTICS_update (GDS_stats,
5513 ("# Bytes received from other peers"), msize,
5516 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5517 is_predecessor = ntohl (trail_rejection->is_predecessor);
5518 congestion_timeout = trail_rejection->congestion_time;
5519 source = trail_rejection->source_peer;
5520 trail_id = trail_rejection->trail_id;
5521 ultimate_destination_finger_value =
5522 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5523 /* First set the congestion time of the friend that sent you this message. */
5524 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5525 if (NULL == target_friend)
5527 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5531 target_friend->congestion_timestamp =
5532 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5533 congestion_timeout);
5535 /* I am the source peer which wants to setup the trail. Do nothing.
5536 * send_find_finger_trail_task is scheduled periodically.*/
5537 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5540 /* If I am congested then pass this message to peer before me in trail. */
5541 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5543 /* First remove yourself from the trail. */
5544 unsigned int new_trail_length = trail_length - 1;
5545 struct GNUNET_PeerIdentity trail[new_trail_length];
5547 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5548 if (0 == trail_length)
5551 next_peer = trail[new_trail_length-1];
5554 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5555 if (NULL == target_friend)
5557 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5561 GDS_NEIGHBOURS_send_trail_rejection (source,
5562 ultimate_destination_finger_value,
5563 my_identity, is_predecessor,
5564 trail, new_trail_length, trail_id,
5565 target_friend, CONGESTION_TIMEOUT);
5569 struct Closest_Peer successor;
5570 successor = find_local_best_known_next_hop (ultimate_destination_finger_value, is_predecessor);
5572 /* Am I the final destination? */
5573 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5576 /*Here you are already part of trail. Copy the trail removing yourself. */
5577 unsigned int new_trail_length = trail_length - 1;
5578 struct GNUNET_PeerIdentity trail[new_trail_length];
5580 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5582 if (0 == new_trail_length)
5586 next_peer = trail[new_trail_length-1];
5589 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5591 if (NULL == target_friend)
5593 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5597 GDS_NEIGHBOURS_send_trail_setup_result (source,
5599 target_friend, new_trail_length,
5602 ultimate_destination_finger_value,
5607 /* Here I was already part of trail. So no need to add. */
5609 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5610 &successor.next_hop);
5611 if (NULL == target_friend)
5613 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5618 GDS_NEIGHBOURS_send_trail_setup (source,
5619 ultimate_destination_finger_value,
5620 successor.best_known_destination,
5621 target_friend, trail_length, trail_peer_list,
5622 is_predecessor, trail_id,
5623 successor.trail_id);
5630 * Core handler for trail teardown message.
5631 * @param cls closure
5632 * @param message message
5633 * @param peer sender of this messsage.
5634 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5637 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5638 const struct GNUNET_MessageHeader *message)
5640 const struct PeerTrailTearDownMessage *trail_teardown;
5641 enum GDS_ROUTING_trail_direction trail_direction;
5642 struct GNUNET_HashCode trail_id;
5643 struct GNUNET_PeerIdentity *next_hop;
5646 msize = ntohs (message->size);
5648 /* Here we pass only the trail id. */
5649 if (msize != sizeof (struct PeerTrailTearDownMessage))
5651 GNUNET_break_op (0);
5655 GNUNET_STATISTICS_update (GDS_stats,
5657 ("# Bytes received from other peers"), msize,
5660 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5661 trail_direction = ntohl (trail_teardown->trail_direction);
5662 trail_id = trail_teardown->trail_id;
5664 /* Check if peer is the real peer from which we should get this message.*/
5665 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5667 GNUNET_assert (NULL != (prev_hop =
5668 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5669 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5672 return GNUNET_SYSERR;
5676 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5677 if (NULL == next_hop)
5679 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5680 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5682 return GNUNET_SYSERR;
5685 /* I am the next hop, which means I am the final destination. */
5686 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5688 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5693 /* If not final destination, then send a trail teardown message to next hop.*/
5694 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5695 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5696 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5704 * Core handle for p2p add trail message.
5705 * @param cls closure
5706 * @param message message
5707 * @param peer peer identity this notification is about
5708 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5711 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5712 const struct GNUNET_MessageHeader *message)
5714 const struct PeerAddTrailMessage *add_trail;
5715 const struct GNUNET_PeerIdentity *trail;
5716 struct GNUNET_HashCode trail_id;
5717 struct GNUNET_PeerIdentity destination_peer;
5718 struct GNUNET_PeerIdentity source_peer;
5719 struct GNUNET_PeerIdentity next_hop;
5720 unsigned int trail_length;
5721 unsigned int my_index;
5724 msize = ntohs (message->size);
5725 /* In this message we pass the whole trail from source to destination as we
5726 * are adding that trail.*/
5727 //FIXME: failed when run with 1000 pears. check why.
5728 if (msize < sizeof (struct PeerAddTrailMessage))
5730 GNUNET_break_op (0);
5734 add_trail = (const struct PeerAddTrailMessage *) message;
5735 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5736 sizeof (struct GNUNET_PeerIdentity);
5737 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5738 sizeof (struct GNUNET_PeerIdentity) != 0)
5740 GNUNET_break_op (0);
5744 GNUNET_STATISTICS_update (GDS_stats,
5746 ("# Bytes received from other peers"), msize,
5749 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5750 destination_peer = add_trail->destination_peer;
5751 source_peer = add_trail->source_peer;
5752 trail_id = add_trail->trail_id;
5754 /* I am not the destination of the trail. */
5755 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5757 struct FriendInfo *target_friend;
5759 /* Get my location in the trail. */
5760 my_index = search_my_index (trail, trail_length);
5763 GNUNET_break_op (0);
5764 return GNUNET_SYSERR;
5766 if((trail_length + 1) == my_index)
5768 DEBUG ("Found twice in trail.\n");
5769 GNUNET_break_op (0);
5770 return GNUNET_SYSERR;
5772 if ((trail_length - 1) == my_index)
5774 next_hop = destination_peer;
5778 next_hop = trail[my_index + 1];
5780 /* Add in your routing table. */
5781 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5782 //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5783 GNUNET_assert (NULL !=
5785 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5786 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5787 trail, trail_length, target_friend);
5790 /* I am the destination. Add an entry in routing table. */
5791 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5797 * Free the finger trail in which the first friend to reach to a finger is
5798 * disconnected_friend. Also remove entry from routing table for that particular
5800 * @param disconnected_friend PeerIdentity of friend which got disconnected
5801 * @param remove_finger Finger whose trail we need to check if it has
5802 * disconnected_friend as the first hop.
5803 * @return Total number of trails in which disconnected_friend was the first
5807 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5808 struct FingerInfo *finger)
5810 struct GNUNET_PeerIdentity *next_hop;
5811 struct FriendInfo *remove_friend;
5812 struct Trail *current_trail;
5813 unsigned int matching_trails_count = 0;
5816 /* Iterate over all the trails of finger. */
5817 for (i = 0; i < finger->trails_count; i++)
5819 current_trail = &finger->trail_list[i];
5820 if (GNUNET_NO == current_trail->is_present)
5823 /* First friend to reach to finger is disconnected_peer. */
5824 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5825 disconnected_friend))
5828 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5829 disconnected_friend);
5830 GNUNET_assert (NULL != remove_friend);
5831 next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id,
5832 GDS_ROUTING_SRC_TO_DEST);
5834 /* Here it may happen that as all the peers got disconnected, the entry in
5835 routing table for that particular trail has been removed, because the
5836 previously disconnected peer was either a next hop or prev hop of that
5838 if (NULL != next_hop)
5840 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5842 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id));
5844 matching_trails_count++;
5845 free_trail (current_trail);
5846 current_trail->is_present = GNUNET_NO;
5849 return matching_trails_count;
5854 * Iterate over finger_table entries.
5855 * 0. Ignore finger which is my_identity or if no valid entry present at
5856 * that finger index.
5857 * 1. If disconnected_friend is a finger, then remove the routing entry from
5858 your own table. Free the trail.
5859 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5860 * 2.1 Remove all the trails and entry from routing table in which disconnected
5861 * friend is the first friend in the trail. If disconnected_friend is the
5862 * first friend in all the trails to reach finger, then remove the finger.
5863 * @param disconnected_friend Peer identity of friend which got disconnected.
5866 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5868 struct FingerInfo *current_finger;
5869 int removed_trails_count;
5872 /* Iterate over finger table entries. */
5873 for (i = 0; i < MAX_FINGERS; i++)
5875 current_finger = &finger_table[i];
5877 /* No finger stored at this trail index or I am the finger. */
5878 if ((GNUNET_NO == current_finger->is_present) ||
5879 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5883 /* Is disconnected_peer a finger? */
5884 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5885 ¤t_finger->finger_identity))
5887 remove_existing_finger (current_finger, i);
5890 /* If finger is a friend but not disconnected_friend, then continue. */
5891 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5892 ¤t_finger->finger_identity))
5895 /* Iterate over the list of trails to reach remove_finger. Check if
5896 * disconnected_friend is the first friend in any of the trail. */
5897 removed_trails_count = remove_matching_trails (disconnected_peer,
5899 current_finger->trails_count =
5900 current_finger->trails_count - removed_trails_count;
5901 if (0 == current_finger->trails_count)
5903 current_finger->is_present = GNUNET_NO;
5904 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5911 * Method called whenever a peer disconnects.
5913 * @param cls closure
5914 * @param peer peer identity this notification is about
5917 handle_core_disconnect (void *cls,
5918 const struct GNUNET_PeerIdentity *peer)
5920 struct FriendInfo *remove_friend;
5921 struct P2PPendingMessage *pos;
5922 unsigned int discarded;
5924 /* If disconnected to own identity, then return. */
5925 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5928 if(NULL == (remove_friend =
5929 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
5931 DEBUG("\n friend already disconnected.");
5935 remove_matching_fingers (peer);
5936 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5937 GNUNET_assert (GNUNET_YES ==
5938 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5942 /* Remove all the messages queued in pending list of this peer is discarded.*/
5943 if (remove_friend->th != NULL)
5945 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
5946 remove_friend->th = NULL;
5950 while (NULL != (pos = remove_friend->head))
5952 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
5957 GNUNET_STATISTICS_update (GDS_stats,
5959 ("# Queued messages discarded (peer disconnected)"),
5960 discarded, GNUNET_NO);
5961 //GNUNET_free (remove_friend);
5963 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5966 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5968 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5969 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5977 * Method called whenever a peer connects.
5979 * @param cls closure
5980 * @param peer_identity peer identity this notification is about
5983 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5985 struct FriendInfo *friend;
5987 /* Check for connect to self message */
5988 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5991 /* If peer already exists in our friend_peermap, then exit. */
5992 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5999 friend = GNUNET_new (struct FriendInfo);
6000 friend->id = *peer_identity;
6002 GNUNET_assert (GNUNET_OK ==
6003 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
6004 peer_identity, friend,
6005 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
6007 /* FIXME: now we are not making a distinction between fingers which are friends
6008 * also.But later, we should add a congestion timestamp on the friend, so that it is
6009 * selected after some time out. This is to ensure that both peers have added
6010 * each other as their friend. */
6011 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
6012 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
6014 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
6020 * To be called on core init/fail.
6022 * @param cls service closure
6023 * @param identity the public identity of this peer
6026 core_init (void *cls,
6027 const struct GNUNET_PeerIdentity *identity)
6029 my_identity = *identity;
6034 * Initialize finger table entries.
6037 finger_table_init ()
6039 memset (&finger_table, 0, sizeof (finger_table));
6044 * Initialize neighbours subsystem.
6045 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
6048 GDS_NEIGHBOURS_init (void)
6050 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
6051 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
6052 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
6053 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
6054 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
6055 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
6056 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
6057 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
6058 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
6059 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
6060 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
6061 sizeof (struct PeerTrailTearDownMessage)},
6062 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
6063 {&handle_dht_p2p_notify_succ_confirmation, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION,
6064 sizeof (struct PeerNotifyConfirmationMessage)},
6068 #if ENABLE_MALICIOUS
6073 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
6074 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
6075 GNUNET_NO, core_handlers);
6077 if (NULL == core_api)
6078 return GNUNET_SYSERR;
6080 //TODO: check size of this peer map?
6081 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
6082 finger_table_init ();
6083 successor_times = 10;
6084 find_finger_trail_task_next_send_time.rel_value_us =
6085 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
6086 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6087 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
6089 verify_successor_next_send_time.rel_value_us =
6090 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
6091 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6092 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
6094 verify_successor_retry_time.rel_value_us =
6095 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6096 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6097 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6099 notify_successor_retry_time.rel_value_us =
6100 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6101 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6102 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6110 * Free the memory held up by trails of a finger.
6113 delete_finger_table_entries()
6118 for(i = 0; i < MAX_FINGERS; i++)
6120 if(GNUNET_YES == finger_table[i].is_present)
6122 for(j = 0; j < finger_table[i].trails_count; j++)
6123 free_trail(&finger_table[i].trail_list[i]);
6130 * Shutdown neighbours subsystem.
6133 GDS_NEIGHBOURS_done (void)
6135 if (NULL == core_api)
6138 GNUNET_CORE_disconnect (core_api);
6141 delete_finger_table_entries();
6142 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6143 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6144 friend_peermap = NULL;
6146 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
6148 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6149 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
6152 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
6154 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6155 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
6158 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_retry_task)
6160 struct VerifySuccessorContext *ctx;
6161 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
6163 send_verify_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
6166 if (send_notify_new_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
6168 struct SendNotifyContext *notify_ctx;
6169 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
6170 GNUNET_free (notify_ctx->successor_trail);
6171 GNUNET_free (notify_ctx);
6172 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
6180 * @return my identity
6182 struct GNUNET_PeerIdentity
6183 GDS_NEIGHBOURS_get_my_id (void)
6188 /* end of gnunet-service-xdht_neighbours.c */