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 * Number of rounds for which we should search for finger.
968 static unsigned int fingers_round_count;
970 * Called when core is ready to send a message we asked for
971 * out to the destination.
973 * @param cls the 'struct FriendInfo' of the target friend
974 * @param size number of bytes available in buf
975 * @param buf where the callee should write the message
976 * @return number of bytes written to buf
979 core_transmit_notify (void *cls, size_t size, void *buf)
981 struct FriendInfo *peer = cls;
983 struct P2PPendingMessage *pending;
988 while ((NULL != (pending = peer->head)) &&
989 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
991 peer->pending_count--;
992 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
993 GNUNET_free (pending);
997 /* no messages pending */
1003 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1004 GNUNET_CORE_PRIO_BEST_EFFORT,
1005 GNUNET_TIME_absolute_get_remaining
1006 (pending->timeout), &peer->id,
1007 ntohs (pending->msg->size),
1008 &core_transmit_notify, peer);
1009 GNUNET_break (NULL != peer->th);
1013 while ((NULL != (pending = peer->head)) &&
1014 (size - off >= (msize = ntohs (pending->msg->size))))
1016 GNUNET_STATISTICS_update (GDS_stats,
1018 ("# Bytes transmitted to other peers"), msize,
1020 memcpy (&cbuf[off], pending->msg, msize);
1022 peer->pending_count--;
1023 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1024 GNUNET_free (pending);
1026 if (peer->head != NULL)
1029 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1030 GNUNET_CORE_PRIO_BEST_EFFORT,
1031 GNUNET_TIME_absolute_get_remaining
1032 (pending->timeout), &peer->id, msize,
1033 &core_transmit_notify, peer);
1034 GNUNET_break (NULL != peer->th);
1041 * Transmit all messages in the friend's message queue.
1043 * @param peer message queue to process
1046 process_friend_queue (struct FriendInfo *peer)
1048 struct P2PPendingMessage *pending;
1050 if (NULL == (pending = peer->head))
1054 if (NULL != peer->th)
1060 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1061 pending->importance,
1062 GNUNET_TIME_absolute_get_remaining
1063 (pending->timeout), &peer->id,
1064 ntohs (pending->msg->size),
1065 &core_transmit_notify, peer);
1066 GNUNET_break (NULL != peer->th);
1070 #if ENABLE_MALICIOUS
1072 * Set the ENABLE_MALICIOUS value to malicious.
1076 GDS_NEIGHBOURS_act_malicious (unsigned int malicious)
1078 act_malicious = malicious;
1083 * Construct a trail setup message and forward it to target_friend
1084 * @param source_peer Peer which wants to setup the trail
1085 * @param ultimate_destination_finger_value Peer identity closest to this value
1086 * will be finger to @a source_peer
1087 * @param best_known_destination Best known destination (could be finger or friend)
1088 * which should get this message. In case it is
1089 * friend, then it is same as target_friend
1090 * @param target_friend Friend to which message is forwarded now.
1091 * @param trail_length Total number of peers in trail setup so far.
1092 * @param trail_peer_list Trail setup so far
1093 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1094 * @param trail_id Unique identifier for the trail we are trying to setup.
1095 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1096 * best_known_destination when its a finger. If not
1097 * used then set to 0.
1100 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1101 uint64_t ultimate_destination_finger_value,
1102 struct GNUNET_PeerIdentity best_known_destination,
1103 struct FriendInfo *target_friend,
1104 unsigned int trail_length,
1105 const struct GNUNET_PeerIdentity *trail_peer_list,
1106 unsigned int is_predecessor,
1107 struct GNUNET_HashCode trail_id,
1108 struct GNUNET_HashCode intermediate_trail_id)
1110 struct P2PPendingMessage *pending;
1111 struct PeerTrailSetupMessage *tsm;
1112 struct GNUNET_PeerIdentity *peer_list;
1115 msize = sizeof (struct PeerTrailSetupMessage) +
1116 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1118 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1124 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1126 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1129 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1130 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1131 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1132 pending->msg = &(tsm->header);
1133 tsm->header.size = htons (msize);
1134 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1135 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1136 tsm->source_peer = source_peer;
1137 tsm->best_known_destination = best_known_destination;
1138 tsm->is_predecessor = htonl (is_predecessor);
1139 tsm->trail_id = trail_id;
1140 tsm->intermediate_trail_id = intermediate_trail_id;
1142 if (trail_length > 0)
1144 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1145 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1148 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1149 target_friend->pending_count++;
1150 process_friend_queue (target_friend);
1155 * Construct a trail setup result message and forward it to target friend.
1156 * @param querying_peer Peer which sent the trail setup request and should get
1158 * @param Finger Peer to which the trail has been setup to.
1159 * @param target_friend Friend to which this message should be forwarded.
1160 * @param trail_length Numbers of peers in the trail.
1161 * @param trail_peer_list Peers which are part of the trail from
1162 * querying_peer to Finger, NOT including them.
1163 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1164 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1166 * @param trail_id Unique identifier of the trail.
1169 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1170 struct GNUNET_PeerIdentity finger,
1171 struct FriendInfo *target_friend,
1172 unsigned int trail_length,
1173 const struct GNUNET_PeerIdentity *trail_peer_list,
1174 unsigned int is_predecessor,
1175 uint64_t ultimate_destination_finger_value,
1176 struct GNUNET_HashCode trail_id)
1178 struct P2PPendingMessage *pending;
1179 struct PeerTrailSetupResultMessage *tsrm;
1180 struct GNUNET_PeerIdentity *peer_list;
1183 msize = sizeof (struct PeerTrailSetupResultMessage) +
1184 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1186 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1192 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1194 GNUNET_STATISTICS_update (GDS_stats,
1195 gettext_noop ("# P2P messages dropped due to full queue"),
1199 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1200 pending->importance = 0;
1201 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1202 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1203 pending->msg = &tsrm->header;
1204 tsrm->header.size = htons (msize);
1205 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1206 tsrm->querying_peer = querying_peer;
1207 tsrm->finger_identity = finger;
1208 tsrm->is_predecessor = htonl (is_predecessor);
1209 tsrm->trail_id = trail_id;
1210 tsrm->ulitmate_destination_finger_value =
1211 GNUNET_htonll (ultimate_destination_finger_value);
1212 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1213 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1215 /* Send the message to chosen friend. */
1216 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1217 target_friend->pending_count++;
1218 process_friend_queue (target_friend);
1222 * Send notify successor confirmation message.
1223 * @param trail_id Unique Identifier of the trail.
1224 * @param trail_direction Destination to Source.
1225 * @param target_friend Friend to get this message next.
1228 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (struct GNUNET_HashCode trail_id,
1229 unsigned int trail_direction,
1230 struct FriendInfo *target_friend)
1232 struct PeerNotifyConfirmationMessage *ncm;
1233 struct P2PPendingMessage *pending;
1236 msize = sizeof (struct PeerNotifyConfirmationMessage);
1237 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1243 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1245 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1249 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1250 pending->importance = 0; /* FIXME */
1251 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1252 ncm = (struct PeerNotifyConfirmationMessage *) &pending[1];
1253 pending->msg = &ncm->header;
1254 ncm->header.size = htons (msize);
1255 ncm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION);
1256 ncm->trail_id = trail_id;
1257 ncm->trail_direction = htonl (trail_direction);
1259 /* Send the message to chosen friend. */
1260 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1261 target_friend->pending_count++;
1262 process_friend_queue (target_friend);
1267 * Send trail rejection message to target friend
1268 * @param source_peer Peer which is trying to setup the trail.
1269 * @param ultimate_destination_finger_value Peer closest to this value will be
1270 * @a source_peer's finger
1271 * @param congested_peer Peer which sent this message as it is congested.
1272 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1273 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1274 * by congested_peer. This does NOT include @a source_peer
1275 * and congested_peer.
1276 * @param trail_length Total number of peers in trail_peer_list, NOT including
1277 * @a source_peer and @a congested_peer
1278 * @param trail_id Unique identifier of this trail.
1279 * @param congestion_timeout Duration given by congested peer as an estimate of
1280 * how long it may remain congested.
1283 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1284 uint64_t ultimate_destination_finger_value,
1285 struct GNUNET_PeerIdentity congested_peer,
1286 unsigned int is_predecessor,
1287 const struct GNUNET_PeerIdentity *trail_peer_list,
1288 unsigned int trail_length,
1289 struct GNUNET_HashCode trail_id,
1290 struct FriendInfo *target_friend,
1291 const struct GNUNET_TIME_Relative congestion_timeout)
1293 struct PeerTrailRejectionMessage *trm;
1294 struct P2PPendingMessage *pending;
1295 struct GNUNET_PeerIdentity *peer_list;
1298 msize = sizeof (struct PeerTrailRejectionMessage) +
1299 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1301 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1307 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1309 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1313 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1314 pending->importance = 0;
1315 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1316 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1317 pending->msg = &trm->header;
1318 trm->header.size = htons (msize);
1319 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1320 trm->source_peer = source_peer;
1321 trm->congested_peer = congested_peer;
1322 trm->congestion_time = congestion_timeout;
1323 trm->is_predecessor = htonl (is_predecessor);
1324 trm->trail_id = trail_id;
1325 trm->ultimate_destination_finger_value =
1326 GNUNET_htonll (ultimate_destination_finger_value);
1328 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1329 if (trail_length > 0)
1331 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1334 /* Send the message to chosen friend. */
1335 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1336 target_friend->pending_count++;
1337 process_friend_queue (target_friend);
1342 * Construct a verify successor message and forward it to target_friend.
1343 * @param source_peer Peer which wants to verify its successor.
1344 * @param successor Peer which is @a source_peer's current successor.
1345 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1346 * NOT including them.
1347 * @param trail List of peers which are part of trail to reach from @a source_peer
1348 * to @a successor, NOT including them.
1349 * @param trail_length Total number of peers in @a trail.
1350 * @param target_friend Next friend to get this message.
1353 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1354 struct GNUNET_PeerIdentity successor,
1355 struct GNUNET_HashCode trail_id,
1356 struct GNUNET_PeerIdentity *trail,
1357 unsigned int trail_length,
1358 struct FriendInfo *target_friend)
1360 struct PeerVerifySuccessorMessage *vsm;
1361 struct P2PPendingMessage *pending;
1362 struct GNUNET_PeerIdentity *peer_list;
1365 msize = sizeof (struct PeerVerifySuccessorMessage) +
1366 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1368 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1374 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1376 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1380 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1381 pending->importance = 0; /* FIXME */
1382 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1383 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1384 pending->msg = &vsm->header;
1385 vsm->header.size = htons (msize);
1386 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1387 vsm->source_peer = source_peer;
1388 vsm->successor = successor;
1389 vsm->trail_id = trail_id;
1390 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1391 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1393 /* Send the message to chosen friend. */
1394 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1395 target_friend->pending_count++;
1396 process_friend_queue (target_friend);
1401 * FIXME: In every function we pass target friend except for this one.
1402 * so, either change everything or this one. also, should se just store
1403 * the pointer to friend in routing table rather than gnunet_peeridentity.
1404 * if yes then we should keep friend info in.h andmake lot of changes.
1405 * Construct a trail teardown message and forward it to target friend.
1406 * @param trail_id Unique identifier of the trail.
1407 * @param trail_direction Direction of trail.
1408 * @param target_friend Friend to get this message.
1411 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1412 unsigned int trail_direction,
1413 struct GNUNET_PeerIdentity peer)
1415 struct PeerTrailTearDownMessage *ttdm;
1416 struct P2PPendingMessage *pending;
1417 struct FriendInfo *target_friend;
1420 msize = sizeof (struct PeerTrailTearDownMessage);
1422 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1428 /*FIXME:In what case friend can be null. ?*/
1429 if (NULL == (target_friend =
1430 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1433 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1435 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1439 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1440 pending->importance = 0; /* FIXME */
1441 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1442 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1443 pending->msg = &ttdm->header;
1444 ttdm->header.size = htons (msize);
1445 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1446 ttdm->trail_id = trail_id;
1447 ttdm->trail_direction = htonl (trail_direction);
1449 /* Send the message to chosen friend. */
1450 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1451 target_friend->pending_count++;
1452 process_friend_queue (target_friend);
1457 * Construct a verify successor result message and send it to target_friend
1458 * @param querying_peer Peer which sent the verify successor message.
1459 * @param source_successor Current_successor of @a querying_peer.
1460 * @param current_predecessor Current predecessor of @a successor. Could be same
1461 * or different from @a querying_peer.
1462 * @param trail_id Unique identifier of the trail from @a querying_peer to
1463 * @a successor, NOT including them.
1464 * @param trail List of peers which are part of trail from @a querying_peer to
1465 * @a successor, NOT including them.
1466 * @param trail_length Total number of peers in @a trail
1467 * @param trail_direction Direction in which we are sending the message. In this
1468 * case we are sending result from @a successor to @a querying_peer.
1469 * @param target_friend Next friend to get this message.
1472 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1473 struct GNUNET_PeerIdentity current_successor,
1474 struct GNUNET_PeerIdentity probable_successor,
1475 struct GNUNET_HashCode trail_id,
1476 const struct GNUNET_PeerIdentity *trail,
1477 unsigned int trail_length,
1478 enum GDS_ROUTING_trail_direction trail_direction,
1479 struct FriendInfo *target_friend)
1481 struct PeerVerifySuccessorResultMessage *vsmr;
1482 struct P2PPendingMessage *pending;
1483 struct GNUNET_PeerIdentity *peer_list;
1486 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1487 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1489 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1495 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1497 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1501 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1502 pending->importance = 0; /* FIXME */
1503 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1504 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1505 pending->msg = &vsmr->header;
1506 vsmr->header.size = htons (msize);
1507 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1508 vsmr->querying_peer = querying_peer;
1509 vsmr->current_successor = current_successor;
1510 vsmr->probable_successor = probable_successor;
1511 vsmr->trail_direction = htonl (trail_direction);
1512 vsmr->trail_id = trail_id;
1513 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1514 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1516 /* Send the message to chosen friend. */
1517 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1518 target_friend->pending_count++;
1519 process_friend_queue (target_friend);
1524 * Construct a notify new successor message and send it to target_friend
1525 * @param source_peer Peer which wants to notify to its new successor that it
1526 * could be its predecessor.
1527 * @param successor New successor of @a source_peer
1528 * @param successor_trail List of peers in Trail to reach from
1529 * @a source_peer to @a new_successor, NOT including
1531 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1532 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1533 * @param target_friend Next friend to get this message.
1536 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1537 struct GNUNET_PeerIdentity successor,
1538 const struct GNUNET_PeerIdentity *successor_trail,
1539 unsigned int successor_trail_length,
1540 struct GNUNET_HashCode succesor_trail_id,
1541 struct FriendInfo *target_friend)
1543 struct PeerNotifyNewSuccessorMessage *nsm;
1544 struct P2PPendingMessage *pending;
1545 struct GNUNET_PeerIdentity *peer_list;
1548 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1549 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1551 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1557 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1559 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1563 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1564 pending->importance = 0; /* FIXME */
1565 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1566 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1567 pending->msg = &nsm->header;
1568 nsm->header.size = htons (msize);
1569 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1570 nsm->new_successor = successor;
1571 nsm->source_peer = source_peer;
1572 nsm->trail_id = succesor_trail_id;
1573 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1574 memcpy (peer_list, successor_trail,
1575 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1577 /* Send the message to chosen friend. */
1578 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1579 target_friend->pending_count++;
1580 process_friend_queue (target_friend);
1585 * Construct an add_trail message and send it to target_friend
1586 * @param source_peer Source of the trail.
1587 * @param destination_peer Destination of the trail.
1588 * @param trail_id Unique identifier of the trail from
1589 * @a source_peer to @a destination_peer, NOT including the endpoints.
1590 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1591 * NOT including the endpoints.
1592 * @param trail_length Total number of peers in @a trail.
1593 * @param target_friend Next friend to get this message.
1596 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1597 struct GNUNET_PeerIdentity destination_peer,
1598 struct GNUNET_HashCode trail_id,
1599 const struct GNUNET_PeerIdentity *trail,
1600 unsigned int trail_length,
1601 struct FriendInfo *target_friend)
1603 struct PeerAddTrailMessage *adm;
1604 struct GNUNET_PeerIdentity *peer_list;
1605 struct P2PPendingMessage *pending;
1608 msize = sizeof (struct PeerAddTrailMessage) +
1609 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1611 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1617 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1619 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1623 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1624 pending->importance = 0; /* FIXME */
1625 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1626 adm = (struct PeerAddTrailMessage *) &pending[1];
1627 pending->msg = &adm->header;
1628 adm->header.size = htons (msize);
1629 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1630 adm->source_peer = source_peer;
1631 adm->destination_peer = destination_peer;
1632 adm->trail_id = trail_id;
1633 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1634 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1636 /* Send the message to chosen friend. */
1637 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1638 target_friend->pending_count++;
1639 process_friend_queue (target_friend);
1645 * Search my location in trail. In case I am present more than once in the
1646 * trail (can happen during trail setup), then return my lowest index.
1647 * @param trail List of peers
1648 * @return my_index if found
1649 * trail_length + 1 if an entry is present twice, It is an error.
1650 * -1 if no entry found.
1653 search_my_index (const struct GNUNET_PeerIdentity *trail,
1657 int index_seen = trail_length + 1;
1660 for (i = 0; i < trail_length; i++)
1662 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1665 if(index_seen == (trail_length + 1))
1669 DEBUG("Entry is present twice in trail. Its not allowed\n");
1683 * Check if the friend is congested or have reached maximum number of trails
1684 * it can be part of of.
1685 * @param friend Friend to be checked.
1686 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1687 * #GNUNET_YES if friend is either congested or have crossed threshold
1690 is_friend_congested (struct FriendInfo *friend)
1692 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1693 ((0 == GNUNET_TIME_absolute_get_remaining
1694 (friend->congestion_timestamp).rel_value_us)))
1702 * Select closest finger to value.
1703 * @param peer1 First peer
1704 * @param peer2 Second peer
1705 * @param value Value to be compare
1706 * @return Closest peer
1708 static struct GNUNET_PeerIdentity
1709 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1710 const struct GNUNET_PeerIdentity *peer2,
1713 uint64_t peer1_value;
1714 uint64_t peer2_value;
1716 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1717 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1718 peer1_value = GNUNET_ntohll (peer1_value);
1719 peer2_value = GNUNET_ntohll (peer2_value);
1721 if (peer1_value == value)
1726 if (peer2_value == value)
1731 if (value < peer1_value && peer1_value < peer2_value)
1735 else if (value < peer2_value && peer2_value < peer1_value)
1739 else if (peer1_value < value && value < peer2_value)
1743 else if (peer2_value < value && value < peer1_value)
1747 else if (peer1_value < peer2_value && peer2_value < value)
1751 else // if (peer2_value < peer1_value && peer1_value < value)
1759 * Select closest predecessor to value.
1760 * @param peer1 First peer
1761 * @param peer2 Second peer
1762 * @param value Value to be compare
1763 * @return Peer which precedes value in the network.
1765 static struct GNUNET_PeerIdentity
1766 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1767 const struct GNUNET_PeerIdentity *peer2,
1770 uint64_t peer1_value;
1771 uint64_t peer2_value;
1773 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1774 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1775 peer1_value = GNUNET_ntohll (peer1_value);
1776 peer2_value = GNUNET_ntohll (peer2_value);
1778 if (peer1_value == value)
1783 if (peer2_value == value)
1788 if (value < peer1_value && peer1_value < peer2_value)
1792 else if (value < peer2_value && peer2_value < peer1_value)
1796 else if (peer1_value < value && value < peer2_value)
1800 else if (peer2_value < value && value < peer1_value)
1804 else if (peer1_value < peer2_value && peer2_value < value)
1808 else // if (peer2_value < peer1_value && peer1_value < value)
1820 test_print_trail (struct GNUNET_PeerIdentity *trail,
1821 unsigned int trail_length)
1823 struct GNUNET_PeerIdentity print_peer;
1826 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1827 __FILE__, __func__,__LINE__,trail_length);
1828 for (i =0 ; i< trail_length; i++)
1830 print_peer = trail[i];
1831 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1832 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1839 * This is a test function to print all the entries of friend table.
1842 test_friend_peermap_print ()
1844 struct FriendInfo *friend;
1845 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1846 struct GNUNET_PeerIdentity print_peer;
1847 struct GNUNET_PeerIdentity key_ret;
1850 print_peer = my_identity;
1851 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1852 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1854 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1856 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1858 (const void **)&friend))
1860 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1861 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1862 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1870 * This is a test function, to print all the entries of finger table.
1873 test_finger_table_print()
1875 struct FingerInfo *finger;
1876 struct GNUNET_PeerIdentity print_peer;
1877 //struct Trail *trail;
1881 print_peer = my_identity;
1882 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1883 for (i = 0; i < MAX_FINGERS; i++)
1885 finger = &finger_table[i];
1887 if (GNUNET_NO == finger->is_present)
1890 print_peer = finger->finger_identity;
1891 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1892 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1895 for (j = 0; j < finger->trails_count; j++)
1897 trail = &finger->trail_list[j];
1898 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1899 struct Trail_Element *element;
1900 element = trail->trail_head;
1901 for (k = 0; k < trail->trail_length; k++)
1903 print_peer = element->peer;
1904 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1905 element = element->next;
1914 * Select the closest peer among two peers (which should not be same)
1915 * with respect to value and finger_table_index
1916 * NOTE: peer1 != peer2
1917 * @param peer1 First peer
1918 * @param peer2 Second peer
1919 * @param value Value relative to which we find the closest
1920 * @param is_predecessor Is value a predecessor or any other finger.
1921 * @return Closest peer among two peers.
1923 static struct GNUNET_PeerIdentity
1924 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1925 const struct GNUNET_PeerIdentity *peer2,
1927 unsigned int is_predecessor)
1929 /* This check is here to ensure that calling function never sends
1930 same peer value in peer1 and peer2. Remove it later. */
1931 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1932 if (1 == is_predecessor)
1933 return select_closest_predecessor (peer1, peer2, value);
1935 // TODO: Change name to something like select_closest_successor!!
1936 return select_closest_finger (peer1, peer2, value);
1941 * Iterate over the list of all the trails of a finger. In case the first
1942 * friend to reach the finger has reached trail threshold or is congested,
1943 * then don't select it. In case there multiple available good trails to reach
1944 * to Finger, choose the one with shortest trail length.
1945 * Note: We use length as parameter. But we can use any other suitable parameter
1947 * @param finger Finger Finger whose trail we have to select.
1948 * @return Trail Selected Trail.
1950 static struct Trail *
1951 select_finger_trail (struct FingerInfo *finger)
1953 struct FriendInfo *friend;
1954 struct Trail *current_finger_trail;
1955 struct Trail *best_trail = NULL;
1958 GNUNET_assert (finger->trails_count > 0);
1959 for (i = 0; i < finger->trails_count; i++)
1961 current_finger_trail = &finger->trail_list[i];
1963 /* No trail stored at this index. */
1964 if (GNUNET_NO == current_finger_trail->is_present)
1967 GNUNET_assert (NULL !=
1969 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1970 ¤t_finger_trail->trail_head->peer)));
1972 /* First friend to reach trail is not free. */
1973 if (GNUNET_YES == is_friend_congested (friend))
1976 if (NULL == best_trail ||
1977 best_trail->trail_length > current_finger_trail->trail_length)
1979 best_trail = current_finger_trail;
1988 * Compare FINGER entry with current successor. If finger's first friend of all
1989 * its trail is not congested and has not crossed trail threshold, then check
1990 * if finger peer identity is closer to final_destination_finger_value than
1991 * current_successor. If yes then update current_successor.
1992 * @param current_successor[in/out]
1996 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
1998 struct FingerInfo *finger;
1999 struct GNUNET_PeerIdentity closest_peer;
2000 struct Trail *finger_trail;
2003 /* Iterate over finger table. */
2004 for (i = 0; i < MAX_FINGERS; i++)
2006 finger = &finger_table[i];
2008 if (GNUNET_NO == finger->is_present)
2011 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2012 ¤t_closest_peer->best_known_destination))
2015 /* If I am my own finger, then ignore this finger. */
2016 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2020 /* If finger is a friend, we have already checked it in previous function. */
2021 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2022 &finger->finger_identity)))
2027 closest_peer = select_closest_peer (&finger->finger_identity,
2028 ¤t_closest_peer->best_known_destination,
2029 current_closest_peer->destination_finger_value,
2030 current_closest_peer->is_predecessor);
2032 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer))
2034 /* Choose one of the trail to reach to finger. */
2035 finger_trail = select_finger_trail (finger);
2037 /* In case no trail found, ignore this finger. */
2038 if (NULL == finger_trail)
2041 current_closest_peer->best_known_destination = closest_peer;
2042 current_closest_peer->next_hop = finger_trail->trail_head->peer;
2043 current_closest_peer->trail_id = finger_trail->trail_id;
2044 current_closest_peer->finger_table_index = i;
2052 * Compare friend entry with current successor.
2053 * If friend identity and current_successor is same, then do nothing.
2054 * If friend is not congested and has not crossed trail threshold, then check
2055 * if friend peer identity is closer to final_destination_finger_value than
2056 * current_successor. If yes then update current_successor.
2057 * @param cls closure
2058 * @param key current public key
2059 * @param value struct Closest_Peer
2060 * @return #GNUNET_YES if we should continue to iterate,
2061 * #GNUNET_NO if not.
2064 compare_friend_and_current_closest_peer (void *cls,
2065 const struct GNUNET_PeerIdentity *key,
2068 struct FriendInfo *friend = value;
2069 struct Closest_Peer *current_closest_peer = cls;
2070 struct GNUNET_PeerIdentity closest_peer;
2072 /* Friend is either congested or has crossed threshold. */
2073 if (GNUNET_YES == is_friend_congested (friend))
2076 /* If current_closest_peer and friend identity are same, then do nothing.*/
2077 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2078 ¤t_closest_peer->best_known_destination))
2084 closest_peer = select_closest_peer (&friend->id,
2085 ¤t_closest_peer->best_known_destination,
2086 current_closest_peer->destination_finger_value,
2087 current_closest_peer->is_predecessor);
2089 /* Is friend the closest successor? */
2090 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer))
2092 current_closest_peer->best_known_destination = friend->id;
2093 current_closest_peer->next_hop = friend->id;
2101 * Initialize current_successor to my_identity.
2102 * @param my_identity My peer identity
2103 * @return Updated closest_peer
2105 static struct Closest_Peer
2106 init_closest_peer (struct GNUNET_PeerIdentity my_identity,
2107 uint64_t destination_finger_value,
2108 unsigned int is_predecessor)
2110 struct Closest_Peer current_closest_peer;
2112 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2113 current_closest_peer.destination_finger_value = destination_finger_value;
2114 current_closest_peer.is_predecessor = is_predecessor;
2115 current_closest_peer.next_hop = my_identity;
2116 current_closest_peer.best_known_destination = my_identity;
2117 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
2118 return current_closest_peer;
2123 * Find locally best known peer, among your own identity, friend and finger list,
2124 * which is closest to given destination_finger_value.
2126 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2128 * @param destination_finger_value Peer closest to this value will be the next destination.
2129 * @param is_predecessor Are we looking for predecessor or finger?
2130 * @return Closest_Peer that contains all the relevant field to reach to
2131 * @a destination_finger_value
2133 static struct Closest_Peer
2134 find_local_best_known_next_hop (uint64_t destination_finger_value,
2135 unsigned int is_predecessor)
2137 struct Closest_Peer current_closest_peer;
2139 /* Initialize current_successor to my_identity. */
2140 current_closest_peer = init_closest_peer (my_identity,
2141 destination_finger_value,
2144 /* Compare each friend entry with current_successor and update current_successor
2145 * with friend if its closest. */
2148 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2149 &compare_friend_and_current_closest_peer,
2150 ¤t_closest_peer));
2152 /* Compare each finger entry with current_successor and update current_successor
2153 * with finger if its closest. */
2154 compare_finger_and_current_closest_peer (¤t_closest_peer);
2155 return current_closest_peer;
2159 * FIXME; Send put message across all the trail to reach to next hop to handle
2161 * Construct a Put message and send it to target_peer.
2162 * @param key Key for the content
2163 * @param block_type Type of the block
2164 * @param options Routing options
2165 * @param desired_replication_level Desired replication count
2166 * @param best_known_dest Peer to which this message should reach eventually,
2167 * as it is best known destination to me.
2168 * @param intermediate_trail_id Trail id in case
2169 * @param target_peer Peer to which this message will be forwarded.
2170 * @param hop_count Number of hops traversed so far.
2171 * @param put_path_length Total number of peers in @a put_path
2172 * @param put_path Number of peers traversed so far
2173 * @param expiration_time When does the content expire
2174 * @param data Content to store
2175 * @param data_size Size of content @a data in bytes
2178 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2179 enum GNUNET_BLOCK_Type block_type,
2180 enum GNUNET_DHT_RouteOption options,
2181 uint32_t desired_replication_level,
2182 struct GNUNET_PeerIdentity best_known_dest,
2183 struct GNUNET_HashCode intermediate_trail_id,
2184 struct GNUNET_PeerIdentity *target_peer,
2186 uint32_t put_path_length,
2187 struct GNUNET_PeerIdentity *put_path,
2188 struct GNUNET_TIME_Absolute expiration_time,
2189 const void *data, size_t data_size)
2191 struct PeerPutMessage *ppm;
2192 struct P2PPendingMessage *pending;
2193 struct FriendInfo *target_friend;
2194 struct GNUNET_PeerIdentity *pp;
2197 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2198 sizeof (struct PeerPutMessage);
2199 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2201 put_path_length = 0;
2202 msize = data_size + sizeof (struct PeerPutMessage);
2205 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2207 DEBUG("msize = %lu\n",msize);
2212 GNUNET_assert (NULL !=
2214 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2215 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2216 pending->timeout = expiration_time;
2217 ppm = (struct PeerPutMessage *) &pending[1];
2218 pending->msg = &ppm->header;
2219 ppm->header.size = htons (msize);
2220 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2221 ppm->options = htonl (options);
2222 ppm->block_type = htonl (block_type);
2223 ppm->hop_count = htonl (hop_count + 1);
2224 ppm->desired_replication_level = htonl (desired_replication_level);
2225 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2226 ppm->best_known_destination = best_known_dest;
2227 ppm->intermediate_trail_id = intermediate_trail_id;
2229 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2230 ppm->put_path_length = htonl (put_path_length);
2231 if(put_path_length > 0)
2233 memcpy (pp, put_path,
2234 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2236 memcpy (&pp[put_path_length], data, data_size);
2237 GNUNET_assert (NULL != target_friend);
2238 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2239 target_friend->pending_count++;
2240 process_friend_queue (target_friend);
2245 * Handle the put request from the client.
2246 * @param key Key for the content
2247 * @param block_type Type of the block
2248 * @param options Routing options
2249 * @param desired_replication_level Desired replication count
2250 * @param expiration_time When does the content expire
2251 * @param data Content to store
2252 * @param data_size Size of content @a data in bytes
2255 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
2256 enum GNUNET_BLOCK_Type block_type,
2257 enum GNUNET_DHT_RouteOption options,
2258 uint32_t desired_replication_level,
2259 struct GNUNET_TIME_Absolute expiration_time,
2260 const void *data, size_t data_size)
2262 struct GNUNET_PeerIdentity best_known_dest;
2263 struct GNUNET_HashCode intermediate_trail_id;
2264 struct GNUNET_PeerIdentity next_hop;
2266 struct Closest_Peer successor;
2268 memcpy (&key_value, key, sizeof (uint64_t));
2269 key_value = GNUNET_ntohll (key_value);
2270 successor = find_local_best_known_next_hop (key_value,
2271 GDS_FINGER_TYPE_NON_PREDECESSOR);
2272 best_known_dest = successor.best_known_destination;
2273 next_hop = successor.next_hop;
2274 intermediate_trail_id = successor.trail_id;
2276 DEBUG("PUT_REQUEST_RECEVIED KEY = %s \n",GNUNET_h2s(key));
2277 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2279 /* I am the destination. */
2280 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2281 block_type,data_size,data);
2282 GDS_CLIENTS_process_put (options, block_type, 0,
2283 ntohl (desired_replication_level),
2284 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time.
2285 key, data, data_size);
2289 /* In case we are sending the request to a finger, then send across all of its
2292 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2293 &successor.next_hop))
2295 struct FingerInfo *next_hop_finger;
2298 next_hop_finger = &finger_table[successor.finger_table_index];
2299 for (i = 0; i < next_hop_finger->trails_count; i++)
2301 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2303 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2305 next_hop_finger->trail_list[i].trail_id,
2306 &next_hop, hop_count, put_path_length, put_path,
2314 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2315 best_known_dest, intermediate_trail_id, &next_hop,
2316 0, 1, &my_identity, expiration_time,
2321 * FIXME; Send get message across all the trail to reach to next hop to handle
2323 * Construct a Get message and send it to target_peer.
2324 * @param key Key for the content
2325 * @param block_type Type of the block
2326 * @param options Routing options
2327 * @param desired_replication_level Desired replication count
2328 * @param best_known_dest Peer which should get this message. Same as target peer
2329 * if best_known_dest is a friend else its a finger.
2330 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2331 * in case it is a finger else set to 0.
2332 * @param target_peer Peer to which this message will be forwarded.
2333 * @param hop_count Number of hops traversed so far.
2334 * @param data Content to store
2335 * @param data_size Size of content @a data in bytes
2336 * @param get_path_length Total number of peers in @a get_path
2337 * @param get_path Number of peers traversed so far
2340 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2341 enum GNUNET_BLOCK_Type block_type,
2342 enum GNUNET_DHT_RouteOption options,
2343 uint32_t desired_replication_level,
2344 struct GNUNET_PeerIdentity best_known_dest,
2345 struct GNUNET_HashCode intermediate_trail_id,
2346 struct GNUNET_PeerIdentity *target_peer,
2348 uint32_t get_path_length,
2349 struct GNUNET_PeerIdentity *get_path)
2351 struct PeerGetMessage *pgm;
2352 struct P2PPendingMessage *pending;
2353 struct FriendInfo *target_friend;
2354 struct GNUNET_PeerIdentity *gp;
2357 msize = sizeof (struct PeerGetMessage) +
2358 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2360 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2365 GNUNET_assert (NULL !=
2367 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2369 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2370 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2371 pending->importance = 0; /* FIXME */
2372 pgm = (struct PeerGetMessage *) &pending[1];
2373 pending->msg = &pgm->header;
2374 pgm->header.size = htons (msize);
2375 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2376 pgm->get_path_length = htonl (get_path_length);
2377 pgm->best_known_destination = best_known_dest;
2379 pgm->intermediate_trail_id = intermediate_trail_id;
2380 pgm->hop_count = htonl (hop_count + 1);
2381 pgm->get_path_length = htonl (get_path_length);
2382 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2383 memcpy (gp, get_path,
2384 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2385 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2386 target_friend->pending_count++;
2387 process_friend_queue (target_friend);
2392 * Handle the get request from the client file. If I am destination do
2393 * datacache put and return. Else find the target friend and forward message
2395 * @param key Key for the content
2396 * @param block_type Type of the block
2397 * @param options Routing options
2398 * @param desired_replication_level Desired replication count
2401 GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key,
2402 enum GNUNET_BLOCK_Type block_type,
2403 enum GNUNET_DHT_RouteOption options,
2404 uint32_t desired_replication_level)
2406 struct Closest_Peer successor;
2407 struct GNUNET_PeerIdentity best_known_dest;
2408 struct GNUNET_HashCode intermediate_trail_id;
2411 memcpy (&key_value, key, sizeof (uint64_t));
2412 key_value = GNUNET_ntohll (key_value);
2414 successor = find_local_best_known_next_hop (key_value,
2415 GDS_FINGER_TYPE_NON_PREDECESSOR);
2417 best_known_dest = successor.best_known_destination;
2418 intermediate_trail_id = successor.trail_id;
2420 DEBUG("GET_REQUEST_RECEVIED KEY = %s \n",GNUNET_h2s(key));
2421 /* I am the destination. I have the data. */
2422 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2425 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2426 NULL, 0, 1, &my_identity, NULL,&my_identity);
2430 /* fixme; for multiple trails, we need to send back finger index and send trail
2431 across all the fingers. but in current implementation we don't have this case.
2432 compare finger and current_successor returns, */
2433 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2434 best_known_dest,intermediate_trail_id, &successor.next_hop,
2435 0, 1, &my_identity);
2440 * Send the get result to requesting client.
2441 * @param key Key of the requested data.
2442 * @param type Block type
2443 * @param target_peer Next peer to forward the message to.
2444 * @param source_peer Peer which has the data for the key.
2445 * @param put_path_length Number of peers in @a put_path
2446 * @param put_path Path taken to put the data at its stored location.
2447 * @param get_path_length Number of peers in @a get_path
2448 * @param get_path Path taken to reach to the location of the key.
2449 * @param expiration When will this result expire?
2450 * @param data Payload to store
2451 * @param data_size Size of the @a data
2454 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2455 enum GNUNET_BLOCK_Type type,
2456 const struct GNUNET_PeerIdentity *target_peer,
2457 const struct GNUNET_PeerIdentity *source_peer,
2458 unsigned int put_path_length,
2459 const struct GNUNET_PeerIdentity *put_path,
2460 unsigned int get_path_length,
2461 const struct GNUNET_PeerIdentity *get_path,
2462 struct GNUNET_TIME_Absolute expiration,
2463 const void *data, size_t data_size)
2465 struct PeerGetResultMessage *get_result;
2466 struct GNUNET_PeerIdentity *paths;
2467 struct P2PPendingMessage *pending;
2468 struct FriendInfo *target_friend;
2469 int current_path_index;
2472 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2474 sizeof (struct PeerGetResultMessage);
2476 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2478 put_path_length = 0;
2479 msize = msize - put_path_length;
2483 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2488 current_path_index = 0;
2489 if(get_path_length > 0)
2491 current_path_index = search_my_index(get_path, get_path_length);
2492 if (-1 == current_path_index)
2497 if ((get_path_length + 1) == current_path_index)
2499 DEBUG ("Peer found twice in get path. Not allowed \n");
2504 if (0 == current_path_index)
2506 DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",GNUNET_h2s(key),GNUNET_i2s(&my_identity));
2507 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2508 get_path, put_path_length,
2509 put_path, type, data_size, data);
2513 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2514 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2515 pending->importance = 0;
2516 get_result = (struct PeerGetResultMessage *)&pending[1];
2517 pending->msg = &get_result->header;
2518 get_result->header.size = htons (msize);
2519 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2520 get_result->key = *key;
2521 get_result->querying_peer = *source_peer;
2522 get_result->expiration_time = expiration;
2523 get_result->get_path_length = htonl (get_path_length);
2524 get_result->put_path_length = htonl (put_path_length);
2525 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2526 memcpy (paths, put_path,
2527 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2528 memcpy (&paths[put_path_length], get_path,
2529 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2530 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2532 GNUNET_assert (NULL !=
2534 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2535 &get_path[current_path_index - 1])));
2536 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2537 target_friend->pending_count++;
2538 process_friend_queue (target_friend);
2543 * Randomly choose one of your friends (which is not congested and have not crossed
2544 * trail threshold) from the friend_peermap
2545 * @return Friend Randomly chosen friend.
2546 * NULL in case friend peermap is empty, or all the friends are either
2547 * congested or have crossed trail threshold.
2549 static struct FriendInfo *
2550 select_random_friend ()
2552 unsigned int current_size;
2555 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2556 struct GNUNET_PeerIdentity key_ret;
2557 struct FriendInfo *friend;
2559 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2562 if (0 == current_size)
2565 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2566 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2568 /* Iterate till you don't reach to index. */
2569 for (j = 0; j < index ; j++)
2570 GNUNET_assert (GNUNET_YES ==
2571 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2575 /* Reset the index in friend peermap to 0 as we reached to the end. */
2576 if (j == current_size)
2579 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2580 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2584 /* Get the friend stored at the index, j*/
2585 GNUNET_assert (GNUNET_YES ==
2586 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2588 (const void **)&friend));
2590 /* This friend is not congested and has not crossed trail threshold. */
2591 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2592 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2598 } while (j != index);
2600 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2606 * Compute 64 bit value of finger_identity corresponding to a finger index using
2608 * For all fingers, n.finger[i] = n + pow (2,i),
2609 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2610 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2611 * @param finger_index Index corresponding to which we calculate 64 bit value.
2612 * @return 64 bit value.
2615 compute_finger_identity_value (unsigned int finger_index)
2619 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2620 my_id64 = GNUNET_ntohll (my_id64);
2622 /* Are we looking for immediate predecessor? */
2623 if (PREDECESSOR_FINGER_ID == finger_index)
2624 return (my_id64 - 1);
2627 uint64_t add = (uint64_t)1 << finger_index;
2628 return (my_id64 + add);
2634 * Choose a random friend. Calculate the next finger identity to search,from
2635 * current_search_finger_index. Start looking for the trail to reach to
2636 * finger identity through this random friend.
2638 * @param cls closure for this task
2639 * @param tc the context under which the task is running
2642 send_find_finger_trail_message (void *cls,
2643 const struct GNUNET_SCHEDULER_TaskContext *tc)
2645 struct FriendInfo *target_friend;
2646 struct GNUNET_HashCode trail_id;
2647 struct GNUNET_HashCode intermediate_trail_id;
2648 unsigned int is_predecessor = 0;
2649 uint64_t finger_id_value;
2651 /* Schedule another send_find_finger_trail_message task. After one round of
2652 * finger search, this time is exponentially backoff. */
2653 find_finger_trail_task_next_send_time.rel_value_us =
2654 find_finger_trail_task_next_send_time.rel_value_us +
2655 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2656 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2657 find_finger_trail_task =
2658 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2659 &send_find_finger_trail_message,
2662 /* No space in my routing table. (Source and destination peers also store entries
2663 * in their routing table). */
2664 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2667 target_friend = select_random_friend ();
2668 if (NULL == target_friend)
2673 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2674 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2677 /* Generate a unique trail id for trail we are trying to setup. */
2678 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2679 &trail_id, sizeof (trail_id));
2680 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2681 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2682 target_friend->id, target_friend, 0, NULL,
2683 is_predecessor, trail_id,
2684 intermediate_trail_id);
2689 * In case there are already maximum number of possible trails to reach to a
2690 * finger, then check if the new trail's length is lesser than any of the
2692 * If yes then replace that old trail by new trail.
2694 * Note: Here we are taking length as a parameter to choose the best possible
2695 * trail, but there could be other parameters also like:
2696 * 1. duration of existence of a trail - older the better.
2697 * 2. if the new trail is completely disjoint than the
2698 * other trails, then may be choosing it is better.
2700 * @param finger Finger
2701 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2702 * including the endpoints.
2703 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2704 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2707 select_and_replace_trail (struct FingerInfo *finger,
2708 const struct GNUNET_PeerIdentity *new_trail,
2709 unsigned int new_trail_length,
2710 struct GNUNET_HashCode new_trail_id)
2712 struct Trail *current_trail;
2713 unsigned int largest_trail_length;
2714 unsigned int largest_trail_index;
2715 struct Trail_Element *trail_element;
2716 struct GNUNET_PeerIdentity *next_hop;
2719 largest_trail_length = new_trail_length;
2720 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2722 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2724 for (i = 0; i < finger->trails_count; i++)
2726 current_trail = &finger->trail_list[i];
2727 GNUNET_assert (GNUNET_YES == current_trail->is_present);
2728 if (current_trail->trail_length > largest_trail_length)
2730 largest_trail_length = current_trail->trail_length;
2731 largest_trail_index = i;
2735 /* New trail is not better than existing ones. Send trail teardown. */
2736 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2738 next_hop = GDS_ROUTING_get_next_hop (new_trail_id, GDS_ROUTING_SRC_TO_DEST);
2739 GDS_ROUTING_remove_trail (new_trail_id);
2740 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2741 GDS_ROUTING_SRC_TO_DEST,
2746 /* Send trail teardown message across the replaced trail. */
2747 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2748 next_hop = GDS_ROUTING_get_next_hop (replace_trail->trail_id, GDS_ROUTING_SRC_TO_DEST);
2749 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2750 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2751 GDS_ROUTING_SRC_TO_DEST,
2754 /* Free the trail. */
2755 while (NULL != (trail_element = replace_trail->trail_head))
2757 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2758 replace_trail->trail_tail, trail_element);
2759 GNUNET_free_non_null (trail_element);
2762 /* Add new trial at that location. */
2763 replace_trail->is_present = GNUNET_YES;
2764 replace_trail->trail_length = new_trail_length;
2765 replace_trail->trail_id = new_trail_id;
2767 for (i = 0; i < new_trail_length; i++)
2769 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2770 element->peer = new_trail[i];
2772 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2773 replace_trail->trail_tail,
2776 /* FIXME: URGENT Are we adding the trail back to the list. */
2781 * Check if the new trail to reach to finger is unique or do we already have
2782 * such a trail present for finger.
2783 * @param existing_finger Finger identity
2784 * @param new_trail New trail to reach @a existing_finger
2785 * @param trail_length Total number of peers in new_trail.
2786 * @return #GNUNET_YES if the new trail is unique
2787 * #GNUNET_NO if same trail is already present.
2790 is_new_trail_unique (struct FingerInfo *existing_finger,
2791 const struct GNUNET_PeerIdentity *new_trail,
2792 unsigned int trail_length)
2794 struct Trail *current_trail;
2795 struct Trail_Element *trail_element;
2799 GNUNET_assert (existing_finger->trails_count > 0);
2801 /* Iterate over list of trails. */
2802 for (i = 0; i < existing_finger->trails_count; i++)
2804 current_trail = &(existing_finger->trail_list[i]);
2805 if(GNUNET_NO == current_trail->is_present)
2808 /* New trail and existing trail length are not same. */
2809 if (current_trail->trail_length != trail_length)
2814 trail_element = current_trail->trail_head;
2815 for (j = 0; j < current_trail->trail_length; j++)
2817 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2818 &trail_element->peer))
2822 trail_element = trail_element->next;
2829 * FIXME; In case of multiple trails, we may have a case where a trail from in
2830 * between has been removed, then we should try to find a free slot , not simply
2831 * add a trail at then end of the list.
2832 * Add a new trail at a free slot in trail array of existing finger.
2833 * @param existing_finger Finger
2834 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2835 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2836 * @param new_finger_trail_id Unique identifier of the trail.
2839 add_new_trail (struct FingerInfo *existing_finger,
2840 const struct GNUNET_PeerIdentity *new_trail,
2841 unsigned int new_trail_length,
2842 struct GNUNET_HashCode new_trail_id)
2844 struct FriendInfo *friend;
2845 struct Trail *trail;
2849 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2853 for (i = 0; i < existing_finger->trails_count; i++)
2855 if (GNUNET_NO == existing_finger->trail_list[i].is_present)
2862 if (-1 == free_slot)
2865 trail = &existing_finger->trail_list[free_slot];
2866 GNUNET_assert (GNUNET_NO == trail->is_present);
2867 trail->trail_id = new_trail_id;
2868 trail->trail_length = new_trail_length;
2869 existing_finger->trails_count++;
2870 trail->is_present = GNUNET_YES;
2871 if (0 == new_trail_length)
2873 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2874 &existing_finger->finger_identity);
2878 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2882 friend->trails_count++;
2883 for (i = 0; i < new_trail_length; i++)
2885 struct Trail_Element *element;
2887 element = GNUNET_new (struct Trail_Element);
2888 element->peer = new_trail[i];
2889 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2894 existing_finger->trail_list[free_slot].trail_head = trail->trail_head;
2895 existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail;
2896 existing_finger->trail_list[free_slot].trail_length = new_trail_length;
2897 existing_finger->trail_list[free_slot].trail_id = new_trail_id;
2898 existing_finger->trail_list[free_slot].is_present = GNUNET_YES;
2904 * FIXME; In case of multiple trails, we may have a case where a trail from in
2905 * between has been removed, then we should try to find a free slot , not simply
2906 * add a trail at then end of the list.
2907 * Add a new trail at a free slot in trail array of existing finger.
2908 * @param existing_finger Finger
2909 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2910 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2911 * @param new_finger_trail_id Unique identifier of the trail.
2914 add_new_trail (struct FingerInfo *existing_finger,
2915 const struct GNUNET_PeerIdentity *new_trail,
2916 unsigned int new_trail_length,
2917 struct GNUNET_HashCode new_trail_id)
2919 struct Trail *trail;
2920 struct FriendInfo *first_friend;
2924 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2928 index = existing_finger->trails_count;
2929 trail = &existing_finger->trail_list[index];
2930 GNUNET_assert (GNUNET_NO == trail->is_present);
2931 trail->trail_id = new_trail_id;
2932 trail->trail_length = new_trail_length;
2933 existing_finger->trails_count++;
2934 trail->is_present = GNUNET_YES;
2936 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2937 &existing_finger->finger_identity)));
2938 /* If finger is a friend then we never call this function. */
2939 GNUNET_assert (new_trail_length > 0);
2941 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2943 first_friend->trails_count++;
2945 for (i = 0; i < new_trail_length; i++)
2947 struct Trail_Element *element;
2949 element = GNUNET_new (struct Trail_Element);
2950 element->peer = new_trail[i];
2951 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2955 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2956 existing_finger->trail_list[index].trail_head = trail->trail_head;
2957 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2958 existing_finger->trail_list[index].trail_length = new_trail_length;
2959 existing_finger->trail_list[index].trail_id = new_trail_id;
2960 existing_finger->trail_list[index].is_present = GNUNET_YES;
2965 * Get the next hop to send trail teardown message from routing table and
2966 * then delete the entry from routing table. Send trail teardown message for a
2967 * specific trail of a finger.
2968 * @param finger Finger whose trail is to be removed.
2969 * @param trail List of peers in trail from me to a finger, NOT including
2973 send_trail_teardown (struct FingerInfo *finger,
2974 struct Trail *trail)
2976 struct FriendInfo *friend;
2977 struct GNUNET_PeerIdentity *next_hop;
2979 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2980 GDS_ROUTING_SRC_TO_DEST);
2981 if (NULL == next_hop)
2983 // DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d",
2984 // GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length);
2987 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2990 GNUNET_assert(GNUNET_YES == trail->is_present);
2991 if (trail->trail_length > 0)
2993 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2994 &trail->trail_head->peer);
2998 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2999 &finger->finger_identity);
3004 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
3005 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
3008 if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)
3009 && (0 == trail->trail_length))
3011 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
3012 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
3015 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
3016 friend->trails_count--;
3017 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
3018 GDS_ROUTING_SRC_TO_DEST,
3024 * Send trail teardown message across all the trails to reach to finger.
3025 * @param finger Finger whose all the trail should be freed.
3028 send_all_finger_trails_teardown (struct FingerInfo *finger)
3031 for (i = 0; i < finger->trails_count; i++)
3033 struct Trail *trail;
3034 trail = &finger->trail_list[i];
3035 if (GNUNET_YES == trail->is_present);
3037 send_trail_teardown (finger, trail);
3038 trail->is_present = GNUNET_NO;
3045 * Free a specific trail
3046 * @param trail List of peers to be freed.
3049 free_trail (struct Trail *trail)
3051 struct Trail_Element *trail_element;
3053 while (NULL != (trail_element = trail->trail_head))
3055 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
3058 GNUNET_free_non_null (trail_element);
3060 trail->trail_head = NULL;
3061 trail->trail_tail = NULL;
3066 * Free finger and its trail.
3067 * @param finger Finger to be freed.
3068 * @param finger_table_index Index at which finger is stored.
3071 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
3073 struct Trail *trail;
3075 for (i = 0; i < finger->trails_count; i++)
3077 trail = &finger->trail_list[i];
3078 if (GNUNET_NO == trail->is_present)
3081 if (trail->trail_length > 0)
3083 trail->is_present = GNUNET_NO;
3086 finger->is_present = GNUNET_NO;
3087 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
3092 * Add a new entry in finger table at finger_table_index.
3093 * In case I am my own finger, then we don't have a trail. In case of a friend,
3094 * we have a trail with unique id and '0' trail length.
3095 * In case a finger is a friend, then increment the trails count of the friend.
3096 * @param finger_identity Peer Identity of new finger
3097 * @param finger_trail Trail to reach from me to finger (excluding both end points).
3098 * @param finger_trail_length Total number of peers in @a finger_trail.
3099 * @param trail_id Unique identifier of the trail.
3100 * @param finger_table_index Index in finger table.
3103 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
3104 const struct GNUNET_PeerIdentity *finger_trail,
3105 unsigned int finger_trail_length,
3106 struct GNUNET_HashCode trail_id,
3107 unsigned int finger_table_index)
3109 struct FingerInfo *new_entry;
3110 struct FriendInfo *first_trail_hop;
3111 struct Trail *trail;
3114 new_entry = GNUNET_new (struct FingerInfo);
3115 new_entry->finger_identity = finger_identity;
3116 new_entry->finger_table_index = finger_table_index;
3117 new_entry->is_present = GNUNET_YES;
3119 /* If the new entry is my own identity. */
3120 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3123 new_entry->trails_count = 0;
3124 finger_table[finger_table_index] = *new_entry;
3125 GNUNET_free (new_entry);
3129 /* Finger is a friend. */
3130 if (0 == finger_trail_length)
3132 new_entry->trail_list[0].trail_id = trail_id;
3133 new_entry->trails_count = 1;
3134 new_entry->trail_list[0].is_present = GNUNET_YES;
3135 new_entry->trail_list[0].trail_length = 0;
3136 new_entry->trail_list[0].trail_head = NULL;
3137 new_entry->trail_list[0].trail_tail = NULL;
3138 finger_table[finger_table_index] = *new_entry;
3139 GNUNET_assert (NULL !=
3141 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3142 &finger_identity)));
3144 first_trail_hop->trails_count++;
3145 GNUNET_free (new_entry);
3149 GNUNET_assert (NULL !=
3151 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3152 &finger_trail[0])));
3153 new_entry->trails_count = 1;
3154 first_trail_hop->trails_count++;
3155 /* Copy the finger trail into trail. */
3156 trail = GNUNET_new (struct Trail);
3157 for(i = 0; i < finger_trail_length; i++)
3159 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3161 element->next = NULL;
3162 element->prev = NULL;
3163 element->peer = finger_trail[i];
3164 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3169 /* Add trail to trail list. */
3170 new_entry->trail_list[0].trail_head = trail->trail_head;
3171 new_entry->trail_list[0].trail_tail = trail->trail_tail;
3172 new_entry->trail_list[0].trail_length = finger_trail_length;
3173 new_entry->trail_list[0].trail_id = trail_id;
3174 new_entry->trail_list[0].is_present = GNUNET_YES;
3175 finger_table[finger_table_index] = *new_entry;
3176 GNUNET_free (new_entry);
3182 * Periodic task to verify current successor. There can be multiple trails to reach
3183 * to successor, choose the shortest one and send verify successor message
3184 * across that trail.
3185 * @param cls closure for this task
3186 * @param tc the context under which the task is running
3189 send_verify_successor_message (void *cls,
3190 const struct GNUNET_SCHEDULER_TaskContext *tc)
3192 struct FriendInfo *target_friend;
3193 struct GNUNET_HashCode trail_id;
3194 struct Trail *trail;
3195 struct Trail_Element *element;
3196 unsigned int trail_length;
3198 struct FingerInfo *successor;
3200 successor = &finger_table[0];
3202 /* This task will be scheduled when the result for Verify Successor is received. */
3203 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
3205 /* When verify successor is being called for first time *for current context*
3206 * cls will be NULL. If send_verify_successor_retry_task is not NO_TASK, we
3207 * must cancel the retry task scheduled for verify_successor of previous
3212 /* FIXME: Here we are scheduling a new verify successor task, as we
3213 got a new successor. But a send verify successor task may be in progress.
3214 1. We need to be sure that this is indeed a new successor. As this function
3215 is called even if we add a new trail to reach t old successor.
3216 2. Assuming the new successor is different, then verify successor message
3217 * to old successor may be following stages.
3218 * --> Waiting for verify successor result. Don't wait anymore. there is
3219 * no trail to reach from old successor to me, hence, routing
3221 * --> Waiting for notify confirmation. again don't wait for it. notify
3222 * confirmation will not succeded.
3224 if (send_verify_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
3226 /* FIXME: Are we scheduling retry task as soon as we send verify message.
3227 If yes then here before making this task, first check if the message
3228 is for the same peer again. */
3229 struct VerifySuccessorContext *old_ctx =
3230 GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
3231 /* old_ctx must not be NULL, as the retry task had been scheduled */
3232 GNUNET_assert(NULL != old_ctx);
3233 GNUNET_free(old_ctx);
3234 /* FIXME: Why don't we reset the task to NO_TASK here? */
3237 struct VerifySuccessorContext *ctx;
3238 ctx = GNUNET_new(struct VerifySuccessorContext);
3240 ctx->num_retries_scheduled++;
3241 send_verify_successor_retry_task =
3242 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3243 &send_verify_successor_message,
3248 /* This is a retry attempt for verify_successor for a previous context */
3249 struct VerifySuccessorContext *ctx;
3252 ctx->num_retries_scheduled++;
3253 send_verify_successor_retry_task =
3254 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3255 &send_verify_successor_message,
3259 /* Among all the trails to reach to successor, select first one which is present.*/
3260 for (i = 0; i < successor->trails_count; i++)
3262 trail = &successor->trail_list[i];
3263 if(GNUNET_YES == trail->is_present)
3267 /* No valid trail found to reach to successor. */
3268 if (i == successor->trails_count)
3271 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3272 &successor->finger_identity));
3273 /* Trail stored at this index. */
3274 GNUNET_assert (GNUNET_YES == trail->is_present);
3275 trail_id = trail->trail_id;
3276 if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST))
3278 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3279 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
3283 trail_length = trail->trail_length;
3284 if (trail_length > 0)
3286 /* Copy the trail into peer list. */
3287 struct GNUNET_PeerIdentity peer_list[trail_length];
3288 element = trail->trail_head;
3289 for(i = 0; i < trail_length; i++)
3291 peer_list[i] = element->peer;
3292 element = element->next;
3294 GNUNET_assert (NULL != (target_friend =
3295 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3297 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3298 successor->finger_identity,
3299 trail_id, peer_list, trail_length,
3304 GNUNET_assert (NULL != (target_friend =
3305 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3306 &successor->finger_identity)));
3307 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3308 successor->finger_identity,
3316 * FIXME: should this be a periodic task, incrementing the search finger index?
3317 * Update the current search finger index.
3318 * @a finger_identity
3319 * @a finger_table_index
3322 update_current_search_finger_index (unsigned int finger_table_index)
3324 struct FingerInfo *successor;
3326 /* FIXME correct this: only move current index periodically */
3327 if (finger_table_index != current_search_finger_index)
3330 successor = &finger_table[0];
3331 GNUNET_assert (GNUNET_YES == successor->is_present);
3333 /* We were looking for immediate successor. */
3334 if (0 == current_search_finger_index)
3336 current_search_finger_index = PREDECESSOR_FINGER_ID;
3337 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &successor->finger_identity))
3339 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3341 send_verify_successor_task =
3342 GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3348 current_search_finger_index = current_search_finger_index - 1;
3354 * Get the least significant bit set in val.
3357 * @return Position of first bit set, 65 in case of error.
3360 find_set_bit (uint64_t val)
3380 return 65; /* Some other bit was set to 1 as well. */
3387 * Calculate finger_table_index from initial 64 bit finger identity value that
3388 * we send in trail setup message.
3389 * @param ultimate_destination_finger_value Value that we calculated from our
3390 * identity and finger_table_index.
3391 * @param is_predecessor Is the entry for predecessor or not?
3392 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3393 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3396 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3397 unsigned int is_predecessor)
3401 unsigned int finger_table_index;
3403 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3404 my_id64 = GNUNET_ntohll (my_id64);
3406 /* Is this a predecessor finger? */
3407 if (1 == is_predecessor)
3409 diff = my_id64 - ultimate_destination_finger_value;
3411 finger_table_index = PREDECESSOR_FINGER_ID;
3413 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3418 diff = ultimate_destination_finger_value - my_id64;
3419 finger_table_index = find_set_bit (diff);
3421 return finger_table_index;
3426 * Remove finger and its associated data structures from finger table.
3427 * @param existing_finger Finger to be removed which is in finger table.
3428 * @param finger_table_index Index in finger table where @a existing_finger
3432 remove_existing_finger (struct FingerInfo *existing_finger,
3433 unsigned int finger_table_index)
3435 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3437 /* If I am my own finger, then we have no trails. */
3438 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3441 existing_finger->is_present = GNUNET_NO;
3442 memset ((void *)&finger_table[finger_table_index], 0,
3443 sizeof (finger_table[finger_table_index]));
3447 /* For all other fingers, send trail teardown across all the trails to reach
3448 finger, and free the finger. */
3449 send_all_finger_trails_teardown (existing_finger);
3450 free_finger (existing_finger, finger_table_index);
3456 * Check if there is already an entry in finger_table at finger_table_index.
3457 * We get the finger_table_index from 64bit finger value we got from the network.
3458 * -- If yes, then select the closest finger.
3459 * -- If new and existing finger are same, then check if you can store more
3461 * -- If yes then add trail, else keep the best trails to reach to the
3463 * -- If the new finger is closest, remove the existing entry, send trail
3464 * teardown message across all the trails to reach the existing entry.
3465 * Add the new finger.
3466 * -- If new and existing finger are different, and existing finger is closest
3468 * -- Update current_search_finger_index.
3469 * @param finger_identity Peer Identity of new finger
3470 * @param finger_trail Trail to reach the new finger
3471 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3472 * @param is_predecessor Is this entry for predecessor in finger_table?
3473 * @param finger_value 64 bit value of finger identity that we got from network.
3474 * @param finger_trail_id Unique identifier of @finger_trail.
3477 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3478 const struct GNUNET_PeerIdentity *finger_trail,
3479 unsigned int finger_trail_length,
3480 unsigned int is_predecessor,
3481 uint64_t finger_value,
3482 struct GNUNET_HashCode finger_trail_id)
3484 struct FingerInfo *existing_finger;
3485 struct GNUNET_PeerIdentity closest_peer;
3486 struct FingerInfo *successor;
3487 unsigned int finger_table_index;
3489 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3490 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3492 /* Invalid finger_table_index. */
3493 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3495 GNUNET_break_op (0);
3499 /* Check if new entry is same as successor. */
3500 if ((0 != finger_table_index) &&
3501 (PREDECESSOR_FINGER_ID != finger_table_index))
3503 successor = &finger_table[0];
3504 if (GNUNET_NO == successor->is_present)
3506 GNUNET_break (0); //ASSERTION FAILS HERE. FIXME
3509 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3510 &successor->finger_identity))
3512 // find_finger_trail_task_next_send_time =
3513 // GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3514 if (0 == fingers_round_count)
3516 find_finger_trail_task_next_send_time =
3517 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3520 fingers_round_count--;
3521 current_search_finger_index = 0;
3522 GNUNET_STATISTICS_update (GDS_stats,
3524 ("# FINGERS_COUNT"), (int64_t) total_fingers_found,
3526 total_fingers_found = 0;
3530 struct FingerInfo prev_finger;
3531 prev_finger = finger_table[finger_table_index - 1];
3532 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3533 &prev_finger.finger_identity))
3535 current_search_finger_index--;
3540 total_fingers_found++;
3541 existing_finger = &finger_table[finger_table_index];
3543 /* No entry present in finger_table for given finger map index. */
3544 if (GNUNET_NO == existing_finger->is_present)
3546 add_new_finger (finger_identity, finger_trail,
3547 finger_trail_length,
3548 finger_trail_id, finger_table_index);
3549 update_current_search_finger_index (finger_table_index);
3553 /* If existing entry and finger identity are not same. */
3554 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3557 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3562 /* If the new finger is the closest peer. */
3563 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer))
3565 remove_existing_finger (existing_finger, finger_table_index);
3566 add_new_finger (finger_identity, finger_trail, finger_trail_length,
3567 finger_trail_id, finger_table_index);
3568 // if ((0 == finger_table_index) && (1 == waiting_for_notify_confirmation))
3570 // /* SUPUS: We have removed our successor, but we are still waiting for a
3571 // * confirmation. As we have removed successor, then it does not make
3572 // sense to wait for the new successor. */
3573 // waiting_for_notify_confirmation = 0;
3578 /* Existing finger is the closest one. We need to send trail teardown
3579 across the trail setup in routing table of all the peers. */
3580 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3582 if (finger_trail_length > 0)
3583 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3584 GDS_ROUTING_SRC_TO_DEST,
3587 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3588 GDS_ROUTING_SRC_TO_DEST,
3595 /* If both new and existing entry are same as my_identity, then do nothing. */
3596 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3602 /* If there is space to store more trails. */
3603 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3604 add_new_trail (existing_finger, finger_trail,
3605 finger_trail_length, finger_trail_id);
3607 select_and_replace_trail (existing_finger, finger_trail,
3608 finger_trail_length, finger_trail_id);
3610 update_current_search_finger_index (finger_table_index);
3616 * FIXME: Check for loop in the request. If you already are part of put path,
3617 * then you need to reset the put path length.
3618 * Core handler for P2P put messages.
3619 * @param cls closure
3620 * @param peer sender of the request
3621 * @param message message
3622 * @return #GNUNET_OK to keep the connection open,
3623 * #GNUNET_SYSERR to close it (signal serious error)
3626 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3627 const struct GNUNET_MessageHeader *message)
3629 struct PeerPutMessage *put;
3630 struct GNUNET_PeerIdentity *put_path;
3631 struct GNUNET_PeerIdentity current_best_known_dest;
3632 struct GNUNET_PeerIdentity best_known_dest;
3633 struct GNUNET_HashCode received_intermediate_trail_id;
3634 struct GNUNET_HashCode intermediate_trail_id;
3635 struct GNUNET_PeerIdentity *next_hop;
3636 struct GNUNET_PeerIdentity *next_routing_hop;
3637 enum GNUNET_DHT_RouteOption options;
3638 struct GNUNET_HashCode test_key;
3643 size_t payload_size;
3646 #if ENABLE_MALICIOUS
3647 if(1 == act_malicious)
3649 DEBUG("I am malicious,dropping put request. \n");
3654 msize = ntohs (message->size);
3655 if (msize < sizeof (struct PeerPutMessage))
3657 GNUNET_break_op (0);
3661 put = (struct PeerPutMessage *) message;
3662 putlen = ntohl (put->put_path_length);
3664 sizeof (struct PeerPutMessage) +
3665 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3667 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3669 GNUNET_break_op (0);
3673 GNUNET_STATISTICS_update (GDS_stats,
3675 ("# Bytes received from other peers"), (int64_t) msize,
3678 current_best_known_dest = put->best_known_destination;
3679 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3680 payload = &put_path[putlen];
3681 options = ntohl (put->options);
3682 received_intermediate_trail_id = put->intermediate_trail_id;
3683 hop_count = ntohl(put->hop_count);
3684 payload_size = msize - (sizeof (struct PeerPutMessage) +
3685 putlen * sizeof (struct GNUNET_PeerIdentity));
3687 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3688 payload, payload_size, &test_key))
3691 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3693 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3694 GNUNET_break_op (0);
3695 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3696 "PUT with key `%s' for block with key %s\n",
3697 put_s, GNUNET_h2s_full (&test_key));
3698 GNUNET_free (put_s);
3703 GNUNET_break_op (0);
3706 /* cannot verify, good luck */
3710 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3712 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3713 ntohl (put->block_type),
3715 NULL, 0, /* bloom filer */
3716 NULL, 0, /* xquery */
3717 payload, payload_size))
3719 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3720 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3723 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3724 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3725 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3726 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3727 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3728 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3730 GNUNET_break_op (0);
3735 /* Check if you are already a part of put path. */
3737 for (i = 0; i < putlen; i++)
3739 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3746 /* Add yourself to the list. */
3747 struct GNUNET_PeerIdentity pp[putlen + 1];
3748 //if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3751 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3752 pp[putlen] = my_identity;
3758 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3759 struct Closest_Peer successor;
3760 key_value = GNUNET_ntohll (key_value);
3761 successor = find_local_best_known_next_hop (key_value,
3762 GDS_FINGER_TYPE_NON_PREDECESSOR);
3763 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3764 *next_hop = successor.next_hop;
3765 intermediate_trail_id = successor.trail_id;
3766 best_known_dest = successor.best_known_destination;
3768 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3770 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3771 GDS_ROUTING_SRC_TO_DEST);
3772 if (NULL != next_routing_hop)
3774 next_hop = next_routing_hop;
3775 intermediate_trail_id = received_intermediate_trail_id;
3776 best_known_dest = current_best_known_dest;
3780 GDS_CLIENTS_process_put (options,
3781 ntohl (put->block_type),
3783 ntohl (put->desired_replication_level),
3785 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3790 /* I am the final destination */
3791 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3793 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3794 &(put->key),putlen, pp, ntohl (put->block_type),
3795 payload_size, payload);
3799 GDS_NEIGHBOURS_send_put (&put->key,
3800 ntohl (put->block_type),ntohl (put->options),
3801 ntohl (put->desired_replication_level),
3802 best_known_dest, intermediate_trail_id, next_hop,
3803 hop_count, putlen, pp,
3804 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3805 payload, payload_size);
3812 * FIXME: Check for loop in the request. If you already are part of get path,
3813 * then you need to reset the get path length.
3814 * Core handler for p2p get requests.
3816 * @param cls closure
3817 * @param peer sender of the request
3818 * @param message message
3819 * @return #GNUNET_OK to keep the connection open,
3820 * #GNUNET_SYSERR to close it (signal serious error)
3823 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3824 const struct GNUNET_MessageHeader *message)
3826 const struct PeerGetMessage *get;
3827 const struct GNUNET_PeerIdentity *get_path;
3828 struct GNUNET_PeerIdentity best_known_dest;
3829 struct GNUNET_PeerIdentity current_best_known_dest;
3830 struct GNUNET_HashCode intermediate_trail_id;
3831 struct GNUNET_HashCode received_intermediate_trail_id;
3832 struct Closest_Peer successor;
3833 struct GNUNET_PeerIdentity *next_hop;
3834 struct GNUNET_PeerIdentity *next_routing_hop;
3835 uint32_t get_length;
3840 #if ENABLE_MALICIOUS
3841 if(1 == act_malicious)
3843 DEBUG("I am malicious,dropping get request. \n");
3848 msize = ntohs (message->size);
3849 if (msize < sizeof (struct PeerGetMessage))
3851 GNUNET_break_op (0);
3855 get = (const struct PeerGetMessage *)message;
3856 get_length = ntohl (get->get_path_length);
3857 current_best_known_dest = get->best_known_destination;
3858 received_intermediate_trail_id = get->intermediate_trail_id;
3859 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3860 hop_count = get->hop_count;
3864 sizeof (struct PeerGetMessage) +
3865 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3867 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3869 GNUNET_break_op (0);
3873 GNUNET_STATISTICS_update (GDS_stats,
3875 ("# Bytes received from other peers"), msize,
3878 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3879 key_value = GNUNET_ntohll (key_value);
3881 /* Check if you are already a part of get path. */
3883 for (i = 0; i < get_length; i++)
3885 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &get_path[i]))
3892 /* Add yourself in the get path. */
3893 struct GNUNET_PeerIdentity gp[get_length + 1];
3894 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3895 gp[get_length] = my_identity;
3896 get_length = get_length + 1;
3897 GDS_CLIENTS_process_get (get->options, get->block_type, hop_count,
3898 get->desired_replication_level, get->get_path_length,
3902 successor = find_local_best_known_next_hop (key_value,
3903 GDS_FINGER_TYPE_NON_PREDECESSOR);
3904 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3905 *next_hop = successor.next_hop;
3906 best_known_dest = successor.best_known_destination;
3907 intermediate_trail_id = successor.trail_id;
3908 /* I am not the final destination. I am part of trail to reach final dest. */
3909 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3911 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3912 GDS_ROUTING_SRC_TO_DEST);
3913 if (NULL != next_routing_hop)
3915 next_hop = next_routing_hop;
3916 best_known_dest = current_best_known_dest;
3917 intermediate_trail_id = received_intermediate_trail_id;
3922 /* I am the final destination. */
3923 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3925 if (1 == get_length)
3927 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0,
3928 NULL, 0, 1, &my_identity, NULL,&my_identity);
3932 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3933 get_length, gp, &gp[get_length - 2],
3939 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3940 get->desired_replication_level, best_known_dest,
3941 intermediate_trail_id, next_hop, hop_count,
3949 * Core handler for get result
3950 * @param cls closure
3951 * @param peer sender of the request
3952 * @param message message
3953 * @return #GNUNET_OK to keep the connection open,
3954 * #GNUNET_SYSERR to close it (signal serious error)
3957 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3958 const struct GNUNET_MessageHeader *message)
3960 const struct PeerGetResultMessage *get_result;
3961 const struct GNUNET_PeerIdentity *get_path;
3962 const struct GNUNET_PeerIdentity *put_path;
3963 const void *payload;
3964 size_t payload_size;
3966 unsigned int getlen;
3967 unsigned int putlen;
3968 int current_path_index;
3970 msize = ntohs (message->size);
3971 if (msize < sizeof (struct PeerGetResultMessage))
3973 GNUNET_break_op (0);
3977 get_result = (const struct PeerGetResultMessage *)message;
3978 getlen = ntohl (get_result->get_path_length);
3979 putlen = ntohl (get_result->put_path_length);
3982 sizeof (struct PeerGetResultMessage) +
3983 getlen * sizeof (struct GNUNET_PeerIdentity) +
3984 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3986 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3988 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3990 GNUNET_break_op (0);
3993 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
3994 GNUNET_STATISTICS_update (GDS_stats,
3996 ("# Bytes received from other peers"), msize,
3999 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
4000 get_path = &put_path[putlen];
4001 payload = (const void *) &get_path[getlen];
4002 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
4003 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
4005 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
4007 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
4008 getlen, get_path, putlen,
4009 put_path, get_result->type, payload_size, payload);
4014 current_path_index = search_my_index (get_path, getlen);
4015 if (-1 == current_path_index )
4017 DEBUG ("No entry found in get path.\n");
4019 return GNUNET_SYSERR;
4021 if((getlen + 1) == current_path_index)
4023 DEBUG("Present twice in get path. Not allowed. \n");
4025 return GNUNET_SYSERR;
4027 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
4028 &get_path[current_path_index - 1],
4029 &(get_result->querying_peer), putlen, put_path,
4030 getlen, get_path, get_result->expiration_time,
4031 payload, payload_size);
4034 return GNUNET_SYSERR;
4039 * Find the next hop to pass trail setup message. First find the local best known
4040 * hop from your own identity, friends and finger. If you were part of trail,
4041 * then get the next hop from routing table. Compare next_hop from routing table
4042 * and local best known hop, and return the closest one to final_dest_finger_val
4043 * @param final_dest_finger_val 64 bit value of finger identity
4044 * @param intermediate_trail_id If you are part of trail to reach to some other
4045 * finger, then it is the trail id to reach to
4046 * that finger, else set to 0.
4047 * @param is_predecessor Are we looking for closest successor or predecessor.
4048 * @param source Source of trail setup message.
4049 * @param current_dest In case you are part of trail, then finger to which
4050 * we should forward the message. Else my own identity
4051 * @return Closest Peer for @a final_dest_finger_val
4053 static struct Closest_Peer
4054 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
4055 struct GNUNET_HashCode intermediate_trail_id,
4056 unsigned int is_predecessor,
4057 struct GNUNET_PeerIdentity source,
4058 struct GNUNET_PeerIdentity *current_dest)
4060 struct Closest_Peer peer;
4062 peer = find_local_best_known_next_hop (final_dest_finger_val, is_predecessor);
4064 /* Am I just a part of a trail towards a finger (current_destination)? */
4065 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
4066 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
4069 struct GNUNET_PeerIdentity closest_peer;
4071 /* Select best successor among one found locally and current_destination
4072 * that we got from network.*/
4073 closest_peer = select_closest_peer (&peer.best_known_destination,
4075 final_dest_finger_val,
4078 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
4079 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
4081 struct GNUNET_PeerIdentity *next_hop;
4083 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4084 GDS_ROUTING_SRC_TO_DEST);
4085 /* next_hop NULL is a valid case. This intermediate trail id is set by
4086 some other finger, and while this trail setup is in progress, that other
4087 peer might have found a better trail ,and send trail teardown message
4088 across the network. In case we got the trail teardown message first,
4089 then next_hop will be NULL. A possible solution could be to keep track
4090 * of all removed trail id, and be sure that there is no other reason . */
4091 if(NULL != next_hop)
4093 peer.next_hop = *next_hop;
4094 peer.best_known_destination = *current_dest;
4095 peer.trail_id = intermediate_trail_id;
4104 * Core handle for PeerTrailSetupMessage.
4105 * @param cls closure
4106 * @param message message
4107 * @param peer peer identity this notification is about
4108 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4111 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
4112 const struct GNUNET_MessageHeader *message)
4114 const struct PeerTrailSetupMessage *trail_setup;
4115 const struct GNUNET_PeerIdentity *trail_peer_list;
4116 struct GNUNET_PeerIdentity current_dest;
4117 struct FriendInfo *target_friend;
4118 struct GNUNET_PeerIdentity source;
4119 struct GNUNET_HashCode intermediate_trail_id;
4120 struct GNUNET_HashCode trail_id;
4121 unsigned int is_predecessor;
4122 uint32_t trail_length;
4123 uint64_t final_dest_finger_val;
4127 msize = ntohs (message->size);
4128 if (msize < sizeof (struct PeerTrailSetupMessage))
4130 GNUNET_break_op (0);
4131 return GNUNET_SYSERR;
4134 trail_setup = (const struct PeerTrailSetupMessage *) message;
4135 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4136 sizeof (struct GNUNET_PeerIdentity) != 0)
4138 GNUNET_break_op (0);
4141 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4142 sizeof (struct GNUNET_PeerIdentity);
4144 GNUNET_STATISTICS_update (GDS_stats,
4146 ("# Bytes received from other peers"), msize,
4149 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4150 current_dest = trail_setup->best_known_destination;
4151 trail_id = trail_setup->trail_id;
4152 final_dest_finger_val =
4153 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4154 source = trail_setup->source_peer;
4155 is_predecessor = ntohl (trail_setup->is_predecessor);
4156 intermediate_trail_id = trail_setup->intermediate_trail_id;
4158 /* Did the friend insert its ID in the trail list? */
4159 if (trail_length > 0 &&
4160 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
4162 GNUNET_break_op (0);
4163 return GNUNET_SYSERR;
4166 /* If I was the source and got the message back, then set trail length to 0.*/
4167 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4172 /* Check if you are present in the trail seen so far? */
4173 for (i = 0; i < trail_length ; i++)
4175 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4177 /* We will add ourself later in code, if NOT destination. */
4183 /* Is my routing table full? */
4184 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4186 if (trail_length > 0)
4188 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4189 &trail_peer_list[trail_length - 1]);
4192 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4194 if(NULL == target_friend)
4196 DEBUG ("\n friend not found");
4200 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4201 my_identity, is_predecessor,
4202 trail_peer_list, trail_length,
4203 trail_id, target_friend,
4204 CONGESTION_TIMEOUT);
4208 /* Get the next hop to forward the trail setup request. */
4209 struct Closest_Peer next_peer =
4210 get_local_best_known_next_hop (final_dest_finger_val,
4211 intermediate_trail_id,
4216 /* Am I the final destination? */
4217 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4220 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4222 finger_table_add (my_identity, NULL, 0, is_predecessor,
4223 final_dest_finger_val, trail_id);
4227 if (trail_length > 0)
4229 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4230 &trail_peer_list[trail_length-1]);
4233 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4234 if (NULL == target_friend)
4236 GNUNET_break_op (0);
4237 return GNUNET_SYSERR;
4239 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4240 GDS_NEIGHBOURS_send_trail_setup_result (source,
4242 target_friend, trail_length,
4245 final_dest_finger_val,trail_id);
4247 else /* I'm not the final destination. */
4249 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4250 &next_peer.next_hop);
4251 if(NULL == target_friend)
4253 DEBUG ("\n target friend not found for peer = %s", GNUNET_i2s(&next_peer.next_hop));
4257 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4259 /* Add yourself to list of peers. */
4260 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4262 memcpy (peer_list, trail_peer_list,
4263 trail_length * sizeof (struct GNUNET_PeerIdentity));
4264 peer_list[trail_length] = my_identity;
4265 GDS_NEIGHBOURS_send_trail_setup (source,
4266 final_dest_finger_val,
4267 next_peer.best_known_destination,
4268 target_friend, trail_length + 1, peer_list,
4269 is_predecessor, trail_id,
4270 next_peer.trail_id);
4273 GDS_NEIGHBOURS_send_trail_setup (source,
4274 final_dest_finger_val,
4275 next_peer.best_known_destination,
4276 target_friend, 0, NULL,
4277 is_predecessor, trail_id,
4278 next_peer.trail_id);
4285 * Core handle for p2p trail setup result messages.
4287 * @param message message
4288 * @param peer sender of this message.
4289 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4292 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4293 const struct GNUNET_MessageHeader *message)
4295 const struct PeerTrailSetupResultMessage *trail_result;
4296 const struct GNUNET_PeerIdentity *trail_peer_list;
4297 struct GNUNET_PeerIdentity next_hop;
4298 struct FriendInfo *target_friend;
4299 struct GNUNET_PeerIdentity querying_peer;
4300 struct GNUNET_PeerIdentity finger_identity;
4301 uint32_t trail_length;
4302 uint64_t ulitmate_destination_finger_value;
4303 uint32_t is_predecessor;
4304 struct GNUNET_HashCode trail_id;
4308 msize = ntohs (message->size);
4309 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4311 GNUNET_break_op (0);
4315 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4316 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4317 sizeof (struct GNUNET_PeerIdentity) != 0)
4319 GNUNET_break_op (0);
4322 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4323 sizeof (struct GNUNET_PeerIdentity);
4325 GNUNET_STATISTICS_update (GDS_stats,
4327 ("# Bytes received from other peers"), msize,
4330 is_predecessor = ntohl (trail_result->is_predecessor);
4331 querying_peer = trail_result->querying_peer;
4332 finger_identity = trail_result->finger_identity;
4333 trail_id = trail_result->trail_id;
4334 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4335 ulitmate_destination_finger_value =
4336 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4338 /* Am I the one who initiated the query? */
4339 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4341 /* Check that you got the message from the correct peer. */
4342 if (trail_length > 0)
4344 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4349 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4352 GDS_ROUTING_add (trail_id, my_identity, *peer);
4353 finger_table_add (finger_identity, trail_peer_list, trail_length,
4354 is_predecessor, ulitmate_destination_finger_value, trail_id);
4358 /* Get my location in the trail. */
4359 my_index = search_my_index (trail_peer_list, trail_length);
4362 DEBUG ("Not found in trail\n");
4364 return GNUNET_SYSERR;
4367 if ((trail_length + 1) == my_index)
4369 DEBUG ("Found twice in trail.\n");
4371 return GNUNET_SYSERR;
4374 //TODO; Refactor code here and above to check if sender peer is correct
4377 if(trail_length > 1)
4378 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4381 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4383 next_hop = trail_result->querying_peer;
4387 if(my_index == trail_length - 1)
4390 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4395 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4397 next_hop = trail_peer_list[my_index - 1];
4400 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4401 if (NULL == target_friend)
4403 GNUNET_break_op (0);
4404 return GNUNET_SYSERR;
4406 GDS_ROUTING_add (trail_id, next_hop, *peer);
4407 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4408 target_friend, trail_length, trail_peer_list,
4410 ulitmate_destination_finger_value,
4418 * @param trail Trail to be inverted
4419 * @param trail_length Total number of peers in the trail.
4420 * @return Updated trail
4422 static struct GNUNET_PeerIdentity *
4423 invert_trail (const struct GNUNET_PeerIdentity *trail,
4424 unsigned int trail_length)
4428 struct GNUNET_PeerIdentity *inverted_trail;
4430 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4433 j = trail_length - 1;
4434 while (i < trail_length)
4436 inverted_trail[i] = trail[j];
4441 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4442 &inverted_trail[0]));
4443 return inverted_trail;
4448 * Return the shortest trail among all the trails to reach to finger from me.
4449 * @param finger Finger
4450 * @param shortest_trail_length[out] Trail length of shortest trail from me
4452 * @return Shortest trail.
4454 static struct GNUNET_PeerIdentity *
4455 get_shortest_trail (struct FingerInfo *finger,
4456 unsigned int *trail_length)
4458 struct Trail *trail;
4459 unsigned int flag = 0;
4460 unsigned int shortest_trail_index = 0;
4461 int shortest_trail_length = -1;
4462 struct Trail_Element *trail_element;
4463 struct GNUNET_PeerIdentity *trail_list;
4466 trail = GNUNET_new (struct Trail);
4468 /* Get the shortest trail to reach to current successor. */
4469 for (i = 0; i < finger->trails_count; i++)
4471 trail = &finger->trail_list[i];
4475 shortest_trail_index = i;
4476 shortest_trail_length = trail->trail_length;
4481 if (shortest_trail_length > trail->trail_length)
4483 shortest_trail_index = i;
4484 shortest_trail_length = trail->trail_length;
4489 /* Copy the shortest trail and return. */
4490 trail = &finger->trail_list[shortest_trail_index];
4491 trail_element = trail->trail_head;
4493 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4494 shortest_trail_length);
4496 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4498 trail_list[i] = trail_element->peer;
4501 GNUNET_assert(shortest_trail_length != -1);
4503 *trail_length = shortest_trail_length;
4509 * Check if trail_1 and trail_2 have any common element. If yes then join
4510 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4511 * @param trail_1 Trail from source to me, NOT including endpoints.
4512 * @param trail_1_len Total number of peers @a trail_1
4513 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4514 * @param trail_2_len Total number of peers @a trail_2
4515 * @param joined_trail_len Total number of peers in combined trail of trail_1
4517 * @return Joined trail.
4519 static struct GNUNET_PeerIdentity *
4520 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4521 unsigned int trail_1_len,
4522 struct GNUNET_PeerIdentity *trail_2,
4523 unsigned int trail_2_len,
4524 unsigned int *joined_trail_len)
4526 struct GNUNET_PeerIdentity *joined_trail;
4531 for (i = 0; i < trail_1_len; i++)
4533 for (j = 0; j < trail_2_len; j++)
4535 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4538 *joined_trail_len = i + (trail_2_len - j);
4539 joined_trail = GNUNET_malloc (*joined_trail_len *
4540 sizeof(struct GNUNET_PeerIdentity));
4543 /* Copy all the elements from 0 to i into joined_trail. */
4544 for(k = 0; k < ( i+1); k++)
4546 joined_trail[k] = trail_1[k];
4549 /* Increment j as entry stored is same as entry stored at i*/
4552 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4553 while(k <= (*joined_trail_len - 1))
4555 joined_trail[k] = trail_2[j];
4560 return joined_trail;
4564 /* Here you should join the trails. */
4565 *joined_trail_len = trail_1_len + trail_2_len + 1;
4566 joined_trail = GNUNET_malloc (*joined_trail_len *
4567 sizeof(struct GNUNET_PeerIdentity));
4570 for(i = 0; i < trail_1_len;i++)
4572 joined_trail[i] = trail_1[i];
4575 joined_trail[i] = my_identity;
4578 for (j = 0; i < *joined_trail_len; i++,j++)
4580 joined_trail[i] = trail_2[j];
4583 return joined_trail;
4588 * Return the trail from source to my current predecessor. Check if source
4589 * is already part of the this trail, if yes then return the shorten trail.
4590 * @param current_trail Trail from source to me, NOT including the endpoints.
4591 * @param current_trail_length Number of peers in @a current_trail.
4592 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4593 * source to my predecessor, NOT including
4595 * @return Trail from source to my predecessor.
4597 static struct GNUNET_PeerIdentity *
4598 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4599 const struct GNUNET_PeerIdentity *trail_src_to_me,
4600 unsigned int trail_src_to_me_len,
4601 unsigned int *trail_src_to_curr_pred_length)
4603 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4604 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4605 unsigned int trail_me_to_curr_pred_length;
4606 struct FingerInfo *current_predecessor;
4610 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4612 /* Check if trail_src_to_me contains current_predecessor. */
4613 for (i = 0; i < trail_src_to_me_len; i++)
4615 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4616 ¤t_predecessor->finger_identity))
4620 *trail_src_to_curr_pred_length = i;
4625 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4626 sizeof(struct GNUNET_PeerIdentity));
4627 for(j = 0; j < i;j++)
4628 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4629 return trail_src_to_curr_pred;
4633 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4634 &trail_me_to_curr_pred_length);
4636 /* Check if trail contains the source_peer. */
4637 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4639 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4640 &trail_me_to_curr_pred[i]))
4643 /* Source is NOT part of trail. */
4646 /* Source is the last element in the trail to reach to my pred.
4647 Source is direct friend of the pred. */
4648 if (trail_me_to_curr_pred_length == i)
4650 *trail_src_to_curr_pred_length = 0;
4654 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4655 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4656 *trail_src_to_curr_pred_length);
4658 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4660 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4662 GNUNET_free_non_null(trail_me_to_curr_pred);
4663 return trail_src_to_curr_pred;
4667 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4668 trail_src_to_me_len,
4669 trail_me_to_curr_pred,
4670 trail_me_to_curr_pred_length,
4672 *trail_src_to_curr_pred_length = len;
4673 GNUNET_free_non_null(trail_me_to_curr_pred);
4674 return trail_src_to_curr_pred;
4679 * Add finger as your predecessor. To add, first generate a new trail id, invert
4680 * the trail to get the trail from me to finger, add an entry in your routing
4681 * table, send add trail message to peers which are part of trail from me to
4682 * finger and add finger in finger table.
4685 * @param trail_length
4688 update_predecessor (struct GNUNET_PeerIdentity finger,
4689 struct GNUNET_PeerIdentity *trail,
4690 unsigned int trail_length)
4692 struct GNUNET_HashCode trail_to_new_predecessor_id;
4693 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4694 struct FriendInfo *target_friend;
4696 /* Generate trail id for trail from me to new predecessor = finger. */
4697 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4698 &trail_to_new_predecessor_id,
4699 sizeof (trail_to_new_predecessor_id));
4701 if (0 == trail_length)
4703 trail_to_new_predecessor = NULL;
4704 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4705 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger);
4706 if (NULL == target_friend)
4714 /* Invert the trail to get the trail from me to finger, NOT including the
4716 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4717 &trail[trail_length-1]));
4718 trail_to_new_predecessor = invert_trail (trail, trail_length);
4720 /* Add an entry in your routing table. */
4721 GDS_ROUTING_add (trail_to_new_predecessor_id,
4723 trail_to_new_predecessor[0]);
4725 GNUNET_assert (NULL != (target_friend =
4726 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4727 &trail_to_new_predecessor[0])));
4730 /* Add entry in routing table of all peers that are part of trail from me
4731 to finger, including finger. */
4732 GDS_NEIGHBOURS_send_add_trail (my_identity,
4734 trail_to_new_predecessor_id,
4735 trail_to_new_predecessor,
4739 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4740 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4741 GNUNET_free_non_null(trail_to_new_predecessor);
4746 * Check if you already have a predecessor. If not then add finger as your
4747 * predecessor. If you have predecessor, then compare two peer identites.
4748 * If finger is correct predecessor, then remove the old entry, add finger in
4749 * finger table and send add_trail message to add the trail in the routing
4750 * table of all peers which are part of trail to reach from me to finger.
4751 * @param finger New peer which may be our predecessor.
4752 * @param trail List of peers to reach from @finger to me.
4753 * @param trail_length Total number of peer in @a trail.
4756 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4757 struct GNUNET_PeerIdentity *trail,
4758 unsigned int trail_length)
4760 struct FingerInfo *current_predecessor;
4761 struct GNUNET_PeerIdentity closest_peer;
4762 uint64_t predecessor_value;
4763 unsigned int is_predecessor = 1;
4765 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4766 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4768 /* No predecessor. Add finger as your predecessor. */
4769 if (GNUNET_NO == current_predecessor->is_present)
4771 update_predecessor (finger, trail, trail_length);
4775 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4781 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4782 closest_peer = select_closest_peer (&finger,
4783 ¤t_predecessor->finger_identity,
4784 predecessor_value, is_predecessor);
4786 /* Finger is the closest predecessor. Remove the existing one and add the new
4788 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4790 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4791 update_predecessor (finger, trail, trail_length);
4799 * Core handle for p2p verify successor messages.
4800 * @param cls closure
4801 * @param message message
4802 * @param peer peer identity this notification is about
4803 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4806 handle_dht_p2p_verify_successor(void *cls,
4807 const struct GNUNET_PeerIdentity *peer,
4808 const struct GNUNET_MessageHeader *message)
4810 const struct PeerVerifySuccessorMessage *vsm;
4811 struct GNUNET_HashCode trail_id;
4812 struct GNUNET_PeerIdentity successor;
4813 struct GNUNET_PeerIdentity source_peer;
4814 struct GNUNET_PeerIdentity *trail;
4815 struct GNUNET_PeerIdentity *next_hop;
4816 struct FingerInfo current_predecessor;
4817 struct FriendInfo *target_friend;
4818 unsigned int trail_src_to_curr_pred_len = 0;
4819 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4820 unsigned int trail_length;
4823 msize = ntohs (message->size);
4825 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4827 GNUNET_break_op (0);
4831 vsm = (const struct PeerVerifySuccessorMessage *) message;
4832 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4833 sizeof (struct GNUNET_PeerIdentity);
4834 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4835 sizeof (struct GNUNET_PeerIdentity) != 0)
4837 GNUNET_break_op (0);
4841 GNUNET_STATISTICS_update (GDS_stats,
4843 ("# Bytes received from other peers"), msize,
4846 trail_id = vsm->trail_id;
4847 source_peer = vsm->source_peer;
4848 successor = vsm->successor;
4849 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4851 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4853 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4855 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4856 if (NULL == next_hop)
4861 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4863 if(NULL == target_friend)
4868 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4869 trail_id, trail, trail_length,
4874 /* I am the destination of this message. */
4876 /* Check if the source_peer could be our predecessor and if yes then update
4878 compare_and_update_predecessor (source_peer, trail, trail_length);
4879 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4881 /* Is source of this message NOT my predecessor. */
4882 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4885 trail_src_to_curr_pred =
4886 get_trail_src_to_curr_pred (source_peer,
4889 &trail_src_to_curr_pred_len);
4893 trail_src_to_curr_pred_len = trail_length;
4896 trail_src_to_curr_pred =
4897 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4898 *trail_src_to_curr_pred_len);
4899 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4901 trail_src_to_curr_pred[i] = trail[i];
4905 GNUNET_assert (NULL !=
4907 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4908 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4909 current_predecessor.finger_identity,
4910 trail_id, trail_src_to_curr_pred,
4911 trail_src_to_curr_pred_len,
4912 GDS_ROUTING_DEST_TO_SRC,
4914 GNUNET_free_non_null(trail_src_to_curr_pred);
4920 * If the trail from me to my probable successor contains a friend not
4921 * at index 0, then we can shorten the trail.
4922 * @param probable_successor Peer which is our probable successor
4923 * @param trail_me_to_probable_successor Peers in path from me to my probable
4924 * successor, NOT including the endpoints.
4925 * @param trail_me_to_probable_successor_len Total number of peers in
4926 * @a trail_me_to_probable_succesor.
4927 * @return Updated trail, if any friend found.
4928 * Else the trail_me_to_probable_successor.
4930 struct GNUNET_PeerIdentity *
4931 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4932 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4933 unsigned int trail_me_to_probable_successor_len,
4934 unsigned int *trail_to_new_successor_length)
4938 struct GNUNET_PeerIdentity *trail_to_new_successor;
4940 /* Probable successor is a friend */
4941 /* SUPUS: Here should I worry about friend,*/
4942 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4943 &probable_successor))
4945 trail_to_new_successor = NULL;
4946 *trail_to_new_successor_length = 0;
4947 return trail_to_new_successor;
4950 /* Is there any friend of yours in this trail. */
4951 if(trail_me_to_probable_successor_len > 1)
4953 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4955 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4956 &trail_me_to_probable_successor[i]))
4959 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4960 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4961 *trail_to_new_successor_length);
4964 for(j = 0; j < *trail_to_new_successor_length; i++,j++)
4966 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4969 return trail_to_new_successor;
4973 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4974 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4978 struct SendNotifyContext
4980 struct GNUNET_PeerIdentity source_peer;
4981 struct GNUNET_PeerIdentity successor;
4982 struct GNUNET_PeerIdentity *successor_trail;
4983 unsigned int successor_trail_length;
4984 struct GNUNET_HashCode succesor_trail_id;
4985 struct FriendInfo *target_friend;
4986 unsigned int num_retries_scheduled;
4990 send_notify_new_successor (void *cls,
4991 const struct GNUNET_SCHEDULER_TaskContext
4995 * Check if the peer which sent us verify successor result message is still ours
4996 * successor or not. If not, then compare existing successor and probable successor.
4997 * In case probable successor is the correct successor, remove the existing
4998 * successor. Add probable successor as new successor. Send notify new successor
4999 * message to new successor.
5000 * @param curr_succ Peer to which we sent the verify successor message. It may
5001 * or may not be our real current successor, as we may have few iterations of
5002 * find finger trail task.
5003 * @param probable_successor Peer which should be our successor accroding to @a
5005 * @param trail List of peers to reach from me to @a probable successor, NOT including
5007 * @param trail_length Total number of peers in @a trail.
5010 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
5011 struct GNUNET_PeerIdentity probable_successor,
5012 const struct GNUNET_PeerIdentity *trail,
5013 unsigned int trail_length)
5015 struct FingerInfo *current_successor;
5016 struct GNUNET_PeerIdentity closest_peer;
5017 struct GNUNET_HashCode trail_id;
5018 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
5019 struct FriendInfo *target_friend;
5020 unsigned int trail_me_to_probable_succ_len;
5021 unsigned int is_predecessor = 0;
5022 uint64_t successor_value;
5024 current_successor = &finger_table[0];
5025 successor_value = compute_finger_identity_value(0);
5027 /* If probable successor is same as current_successor, do nothing. */
5028 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
5029 ¤t_successor->finger_identity))
5031 if ((NULL != GDS_stats))
5037 memcpy (&my_id, &my_identity, sizeof(uint64_t));
5038 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5039 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5040 succ = GNUNET_ntohll(succ);
5041 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5042 GNUNET_free (my_id_str);
5044 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5047 if (send_verify_successor_task == GNUNET_SCHEDULER_NO_TASK)
5048 send_verify_successor_task =
5049 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5050 &send_verify_successor_message,
5054 closest_peer = select_closest_peer (&probable_successor,
5055 ¤t_successor->finger_identity,
5056 successor_value, is_predecessor);
5058 /* If the current_successor in the finger table is closest, then do nothing. */
5059 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
5060 ¤t_successor->finger_identity))
5062 //FIXME: Is this a good place to return the stats.
5063 if ((NULL != GDS_stats))
5069 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5070 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5071 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5072 GNUNET_free (my_id_str);
5073 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5077 if(0 == successor_times)
5079 // successor_times = 3;
5080 verify_successor_next_send_time =
5081 GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time);
5087 if (send_verify_successor_task == GNUNET_SCHEDULER_NO_TASK)
5088 send_verify_successor_task =
5089 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5090 &send_verify_successor_message,
5095 /* Probable successor is the closest peer.*/
5096 if(trail_length > 0)
5098 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5103 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5104 &probable_successor));
5107 trail_me_to_probable_succ_len = 0;
5108 trail_me_to_probable_succ =
5109 check_trail_me_to_probable_succ (probable_successor,
5110 trail, trail_length,
5111 &trail_me_to_probable_succ_len);
5113 /* Remove the existing successor. */
5114 remove_existing_finger (current_successor, 0);
5115 /* Generate a new trail id to reach to your new successor. */
5116 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5117 &trail_id, sizeof (trail_id));
5119 if (trail_me_to_probable_succ_len > 0)
5121 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
5122 GNUNET_assert (NULL !=
5124 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5125 &trail_me_to_probable_succ[0])));
5129 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5130 GNUNET_assert (NULL !=
5132 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5133 &probable_successor)));
5136 add_new_finger (probable_successor, trail_me_to_probable_succ,
5137 trail_me_to_probable_succ_len, trail_id, 0);
5139 struct SendNotifyContext *notify_ctx;
5141 notify_ctx = GNUNET_new(struct SendNotifyContext);
5143 notify_ctx->source_peer = my_identity;
5144 notify_ctx->successor = probable_successor;
5145 notify_ctx->successor_trail =
5146 GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5147 memcpy(notify_ctx->successor_trail, trail_me_to_probable_succ,
5148 sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5149 notify_ctx->successor_trail_length = trail_me_to_probable_succ_len;
5150 notify_ctx->succesor_trail_id = trail_id;
5151 notify_ctx->target_friend = target_friend;
5152 notify_ctx->num_retries_scheduled = 0;
5154 // TODO: Check if we should verify before schedule if already scheduled.
5155 GNUNET_SCHEDULER_add_now(&send_notify_new_successor, (void*)notify_ctx);
5163 send_notify_new_successor (void *cls,
5164 const struct GNUNET_SCHEDULER_TaskContext
5167 struct SendNotifyContext *ctx = (struct SendNotifyContext *) cls;
5169 GDS_NEIGHBOURS_send_notify_new_successor (ctx->source_peer,
5171 ctx->successor_trail,
5172 ctx->successor_trail_length,
5173 ctx->succesor_trail_id,
5174 ctx->target_friend);
5176 if (0 == ctx->num_retries_scheduled &&
5177 send_notify_new_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
5179 // Result from previous notify successos hasn't arrived, so the retry task
5180 // hasn't been cancelled! Already a new notify successor must be called.
5181 // We will cancel the retry request.
5182 struct SendNotifyContext *old_notify_ctx;
5183 old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5184 GNUNET_free (old_notify_ctx->successor_trail);
5185 GNUNET_free (old_notify_ctx);
5186 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
5189 ctx->num_retries_scheduled++;
5190 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_add_delayed(notify_successor_retry_time,
5191 &send_notify_new_successor,
5196 * Core handle for p2p verify successor result messages.
5197 * @param cls closure
5198 * @param message message
5199 * @param peer peer identity this notification is about
5200 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5203 handle_dht_p2p_verify_successor_result(void *cls,
5204 const struct GNUNET_PeerIdentity *peer,
5205 const struct GNUNET_MessageHeader *message)
5207 const struct PeerVerifySuccessorResultMessage *vsrm;
5208 enum GDS_ROUTING_trail_direction trail_direction;
5209 struct GNUNET_PeerIdentity querying_peer;
5210 struct GNUNET_HashCode trail_id;
5211 struct GNUNET_PeerIdentity *next_hop;
5212 struct FriendInfo *target_friend;
5213 struct GNUNET_PeerIdentity probable_successor;
5214 struct GNUNET_PeerIdentity current_successor;
5215 const struct GNUNET_PeerIdentity *trail;
5216 unsigned int trail_length;
5219 msize = ntohs (message->size);
5220 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5222 GNUNET_break_op (0);
5226 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5227 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5228 sizeof (struct GNUNET_PeerIdentity) != 0)
5230 GNUNET_break_op (0);
5233 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5234 sizeof (struct GNUNET_PeerIdentity);
5236 GNUNET_STATISTICS_update (GDS_stats,
5238 ("# Bytes received from other peers"), msize,
5241 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5242 querying_peer = vsrm->querying_peer;
5243 trail_direction = ntohl (vsrm->trail_direction);
5244 trail_id = vsrm->trail_id;
5245 probable_successor = vsrm->probable_successor;
5246 current_successor = vsrm->current_successor;
5248 /* I am the querying_peer. */
5249 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5251 /* Cancel Retry Task */
5252 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_retry_task)
5254 struct VerifySuccessorContext *ctx;
5255 ctx = GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
5257 send_verify_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
5259 compare_and_update_successor (current_successor,
5260 probable_successor, trail, trail_length);
5264 /*If you are not the querying peer then pass on the message */
5265 if(NULL == (next_hop =
5266 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
5268 /* Here it may happen that source peer has found a new successor, and removed
5269 the trail, Hence no entry found in the routing table. Fail silently.*/
5270 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5271 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5275 if (NULL == (target_friend =
5276 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5281 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5282 vsrm->current_successor,
5283 probable_successor, trail_id,
5286 trail_direction, target_friend);
5292 * Core handle for p2p notify new successor messages.
5293 * @param cls closure
5294 * @param message message
5295 * @param peer peer identity this notification is about
5296 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5299 handle_dht_p2p_notify_new_successor(void *cls,
5300 const struct GNUNET_PeerIdentity *peer,
5301 const struct GNUNET_MessageHeader *message)
5303 const struct PeerNotifyNewSuccessorMessage *nsm;
5304 struct GNUNET_PeerIdentity *trail;
5305 struct GNUNET_PeerIdentity source;
5306 struct GNUNET_PeerIdentity new_successor;
5307 struct GNUNET_HashCode trail_id;
5308 struct GNUNET_PeerIdentity next_hop;
5309 struct FriendInfo *target_friend;
5312 uint32_t trail_length;
5314 msize = ntohs (message->size);
5315 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5317 GNUNET_break_op (0);
5320 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5321 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5322 sizeof (struct GNUNET_PeerIdentity) != 0)
5324 GNUNET_break_op (0);
5327 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5328 sizeof (struct GNUNET_PeerIdentity);
5329 GNUNET_STATISTICS_update (GDS_stats,
5331 ("# Bytes received from other peers"), msize,
5334 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5335 source = nsm->source_peer;
5336 new_successor = nsm->new_successor;
5337 trail_id = nsm->trail_id;
5339 /* I am the new_successor to source_peer. */
5340 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5342 if(trail_length > 0)
5343 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5346 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5348 compare_and_update_predecessor (source, trail, trail_length);
5349 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5350 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5351 GDS_ROUTING_DEST_TO_SRC,
5356 GNUNET_assert(trail_length > 0);
5357 /* I am part of trail to reach to successor. */
5358 my_index = search_my_index (trail, trail_length);
5361 DEBUG ("No entry found in trail\n");
5362 GNUNET_break_op (0);
5363 return GNUNET_SYSERR;
5365 if((trail_length + 1) == my_index)
5367 DEBUG ("Found twice in trail.\n");
5368 GNUNET_break_op (0);
5369 return GNUNET_SYSERR;
5371 if ((trail_length-1) == my_index)
5372 next_hop = new_successor;
5374 next_hop = trail[my_index + 1];
5376 GDS_ROUTING_add(trail_id, *peer, next_hop);
5378 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
5379 if (NULL == target_friend)
5384 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5386 trail_id, target_friend);
5393 * Core handler for P2P notify successor message
5394 * @param cls closure
5395 * @param message message
5396 * @param peer peer identity this notification is about
5397 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5400 handle_dht_p2p_notify_succ_confirmation (void *cls,
5401 const struct GNUNET_PeerIdentity *peer,
5402 const struct GNUNET_MessageHeader *message)
5404 const struct PeerNotifyConfirmationMessage *notify_confirmation;
5405 enum GDS_ROUTING_trail_direction trail_direction;
5406 struct GNUNET_HashCode trail_id;
5407 struct FriendInfo *target_friend;
5408 struct GNUNET_PeerIdentity *next_hop;
5411 msize = ntohs (message->size);
5413 if (msize != sizeof (struct PeerNotifyConfirmationMessage))
5415 GNUNET_break_op (0);
5418 GNUNET_STATISTICS_update (GDS_stats,
5420 ("# Bytes received from other peers"), msize,
5423 notify_confirmation = (const struct PeerNotifyConfirmationMessage *) message;
5424 trail_direction = ntohl (notify_confirmation->trail_direction);
5425 trail_id = notify_confirmation->trail_id;
5427 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5428 if (NULL == next_hop)
5430 /* The source of notify new successor, might have found even a better
5431 successor. In that case it send a trail teardown message, and hence,
5432 the next hop is NULL. */
5433 //Fixme: Add some print to confirm the above theory.
5437 /* I peer which sent the notify successor message to the successor. */
5438 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5441 * Schedule another round of verify sucessor with your current successor
5442 * which may or may not be source of this message. This message is used
5443 * only to ensure that we have a path setup to reach to our successor.
5446 // TODO: cancel schedule of notify_successor_retry_task
5447 if (send_notify_new_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
5449 struct SendNotifyContext *notify_ctx;
5450 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5451 GNUNET_free (notify_ctx->successor_trail);
5452 GNUNET_free (notify_ctx);
5453 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
5455 if (send_verify_successor_task == GNUNET_SCHEDULER_NO_TASK)
5457 verify_successor_next_send_time.rel_value_us =
5458 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5459 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5460 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5461 send_verify_successor_task =
5462 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5463 &send_verify_successor_message,
5469 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
5470 if (NULL == target_friend)
5472 DEBUG ("\n friend not found, line number = %d",__LINE__);
5473 return GNUNET_SYSERR;
5475 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5476 GDS_ROUTING_DEST_TO_SRC,
5484 * Core handler for P2P trail rejection message
5485 * @param cls closure
5486 * @param message message
5487 * @param peer peer identity this notification is about
5488 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5491 handle_dht_p2p_trail_setup_rejection (void *cls,
5492 const struct GNUNET_PeerIdentity *peer,
5493 const struct GNUNET_MessageHeader *message)
5495 const struct PeerTrailRejectionMessage *trail_rejection;
5496 unsigned int trail_length;
5497 const struct GNUNET_PeerIdentity *trail_peer_list;
5498 struct FriendInfo *target_friend;
5499 struct GNUNET_TIME_Relative congestion_timeout;
5500 struct GNUNET_HashCode trail_id;
5501 struct GNUNET_PeerIdentity next_peer;
5502 struct GNUNET_PeerIdentity source;
5503 uint64_t ultimate_destination_finger_value;
5504 unsigned int is_predecessor;
5507 msize = ntohs (message->size);
5508 if (msize < sizeof (struct PeerTrailRejectionMessage))
5510 GNUNET_break_op (0);
5513 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5514 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5515 sizeof (struct GNUNET_PeerIdentity) != 0)
5517 GNUNET_break_op (0);
5520 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5521 sizeof (struct GNUNET_PeerIdentity);
5522 GNUNET_STATISTICS_update (GDS_stats,
5524 ("# Bytes received from other peers"), msize,
5527 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5528 is_predecessor = ntohl (trail_rejection->is_predecessor);
5529 congestion_timeout = trail_rejection->congestion_time;
5530 source = trail_rejection->source_peer;
5531 trail_id = trail_rejection->trail_id;
5532 ultimate_destination_finger_value =
5533 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5534 /* First set the congestion time of the friend that sent you this message. */
5535 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5536 if (NULL == target_friend)
5538 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5542 target_friend->congestion_timestamp =
5543 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5544 congestion_timeout);
5546 /* I am the source peer which wants to setup the trail. Do nothing.
5547 * send_find_finger_trail_task is scheduled periodically.*/
5548 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5551 /* If I am congested then pass this message to peer before me in trail. */
5552 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5554 /* First remove yourself from the trail. */
5555 unsigned int new_trail_length = trail_length - 1;
5556 struct GNUNET_PeerIdentity trail[new_trail_length];
5558 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5559 if (0 == trail_length)
5562 next_peer = trail[new_trail_length-1];
5565 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5566 if (NULL == target_friend)
5568 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5572 GDS_NEIGHBOURS_send_trail_rejection (source,
5573 ultimate_destination_finger_value,
5574 my_identity, is_predecessor,
5575 trail, new_trail_length, trail_id,
5576 target_friend, CONGESTION_TIMEOUT);
5580 struct Closest_Peer successor;
5581 successor = find_local_best_known_next_hop (ultimate_destination_finger_value, is_predecessor);
5583 /* Am I the final destination? */
5584 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5587 /*Here you are already part of trail. Copy the trail removing yourself. */
5588 unsigned int new_trail_length = trail_length - 1;
5589 struct GNUNET_PeerIdentity trail[new_trail_length];
5591 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5593 if (0 == new_trail_length)
5597 next_peer = trail[new_trail_length-1];
5600 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5602 if (NULL == target_friend)
5604 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5608 GDS_NEIGHBOURS_send_trail_setup_result (source,
5610 target_friend, new_trail_length,
5613 ultimate_destination_finger_value,
5618 /* Here I was already part of trail. So no need to add. */
5620 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5621 &successor.next_hop);
5622 if (NULL == target_friend)
5624 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5629 GDS_NEIGHBOURS_send_trail_setup (source,
5630 ultimate_destination_finger_value,
5631 successor.best_known_destination,
5632 target_friend, trail_length, trail_peer_list,
5633 is_predecessor, trail_id,
5634 successor.trail_id);
5641 * Core handler for trail teardown message.
5642 * @param cls closure
5643 * @param message message
5644 * @param peer sender of this messsage.
5645 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5648 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5649 const struct GNUNET_MessageHeader *message)
5651 const struct PeerTrailTearDownMessage *trail_teardown;
5652 enum GDS_ROUTING_trail_direction trail_direction;
5653 struct GNUNET_HashCode trail_id;
5654 struct GNUNET_PeerIdentity *next_hop;
5657 msize = ntohs (message->size);
5659 /* Here we pass only the trail id. */
5660 if (msize != sizeof (struct PeerTrailTearDownMessage))
5662 GNUNET_break_op (0);
5666 GNUNET_STATISTICS_update (GDS_stats,
5668 ("# Bytes received from other peers"), msize,
5671 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5672 trail_direction = ntohl (trail_teardown->trail_direction);
5673 trail_id = trail_teardown->trail_id;
5675 /* Check if peer is the real peer from which we should get this message.*/
5676 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5678 GNUNET_assert (NULL != (prev_hop =
5679 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5680 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5683 return GNUNET_SYSERR;
5687 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5688 if (NULL == next_hop)
5690 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5691 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5693 return GNUNET_SYSERR;
5696 /* I am the next hop, which means I am the final destination. */
5697 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5699 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5704 /* If not final destination, then send a trail teardown message to next hop.*/
5705 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5706 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5707 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5715 * Core handle for p2p add trail message.
5716 * @param cls closure
5717 * @param message message
5718 * @param peer peer identity this notification is about
5719 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5722 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5723 const struct GNUNET_MessageHeader *message)
5725 const struct PeerAddTrailMessage *add_trail;
5726 const struct GNUNET_PeerIdentity *trail;
5727 struct GNUNET_HashCode trail_id;
5728 struct GNUNET_PeerIdentity destination_peer;
5729 struct GNUNET_PeerIdentity source_peer;
5730 struct GNUNET_PeerIdentity next_hop;
5731 unsigned int trail_length;
5732 unsigned int my_index;
5735 msize = ntohs (message->size);
5736 /* In this message we pass the whole trail from source to destination as we
5737 * are adding that trail.*/
5738 //FIXME: failed when run with 1000 pears. check why.
5739 if (msize < sizeof (struct PeerAddTrailMessage))
5741 GNUNET_break_op (0);
5745 add_trail = (const struct PeerAddTrailMessage *) message;
5746 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5747 sizeof (struct GNUNET_PeerIdentity);
5748 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5749 sizeof (struct GNUNET_PeerIdentity) != 0)
5751 GNUNET_break_op (0);
5755 GNUNET_STATISTICS_update (GDS_stats,
5757 ("# Bytes received from other peers"), msize,
5760 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5761 destination_peer = add_trail->destination_peer;
5762 source_peer = add_trail->source_peer;
5763 trail_id = add_trail->trail_id;
5765 /* I am not the destination of the trail. */
5766 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5768 struct FriendInfo *target_friend;
5770 /* Get my location in the trail. */
5771 my_index = search_my_index (trail, trail_length);
5774 GNUNET_break_op (0);
5775 return GNUNET_SYSERR;
5777 if((trail_length + 1) == my_index)
5779 DEBUG ("Found twice in trail.\n");
5780 GNUNET_break_op (0);
5781 return GNUNET_SYSERR;
5783 if ((trail_length - 1) == my_index)
5785 next_hop = destination_peer;
5789 next_hop = trail[my_index + 1];
5791 /* Add in your routing table. */
5792 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5793 //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5794 GNUNET_assert (NULL !=
5796 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5797 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5798 trail, trail_length, target_friend);
5801 /* I am the destination. Add an entry in routing table. */
5802 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5808 * Free the finger trail in which the first friend to reach to a finger is
5809 * disconnected_friend. Also remove entry from routing table for that particular
5811 * @param disconnected_friend PeerIdentity of friend which got disconnected
5812 * @param remove_finger Finger whose trail we need to check if it has
5813 * disconnected_friend as the first hop.
5814 * @return Total number of trails in which disconnected_friend was the first
5818 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5819 struct FingerInfo *finger)
5821 struct GNUNET_PeerIdentity *next_hop;
5822 struct FriendInfo *remove_friend;
5823 struct Trail *current_trail;
5824 unsigned int matching_trails_count = 0;
5827 /* Iterate over all the trails of finger. */
5828 for (i = 0; i < finger->trails_count; i++)
5830 current_trail = &finger->trail_list[i];
5831 if (GNUNET_NO == current_trail->is_present)
5834 /* First friend to reach to finger is disconnected_peer. */
5835 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5836 disconnected_friend))
5839 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5840 disconnected_friend);
5841 GNUNET_assert (NULL != remove_friend);
5842 next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id,
5843 GDS_ROUTING_SRC_TO_DEST);
5845 /* Here it may happen that as all the peers got disconnected, the entry in
5846 routing table for that particular trail has been removed, because the
5847 previously disconnected peer was either a next hop or prev hop of that
5849 if (NULL != next_hop)
5851 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5853 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id));
5855 matching_trails_count++;
5856 free_trail (current_trail);
5857 current_trail->is_present = GNUNET_NO;
5860 return matching_trails_count;
5865 * Iterate over finger_table entries.
5866 * 0. Ignore finger which is my_identity or if no valid entry present at
5867 * that finger index.
5868 * 1. If disconnected_friend is a finger, then remove the routing entry from
5869 your own table. Free the trail.
5870 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5871 * 2.1 Remove all the trails and entry from routing table in which disconnected
5872 * friend is the first friend in the trail. If disconnected_friend is the
5873 * first friend in all the trails to reach finger, then remove the finger.
5874 * @param disconnected_friend Peer identity of friend which got disconnected.
5877 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5879 struct FingerInfo *current_finger;
5880 int removed_trails_count;
5883 /* Iterate over finger table entries. */
5884 for (i = 0; i < MAX_FINGERS; i++)
5886 current_finger = &finger_table[i];
5888 /* No finger stored at this trail index or I am the finger. */
5889 if ((GNUNET_NO == current_finger->is_present) ||
5890 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5894 /* Is disconnected_peer a finger? */
5895 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5896 ¤t_finger->finger_identity))
5898 remove_existing_finger (current_finger, i);
5901 /* If finger is a friend but not disconnected_friend, then continue. */
5902 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5903 ¤t_finger->finger_identity))
5906 /* Iterate over the list of trails to reach remove_finger. Check if
5907 * disconnected_friend is the first friend in any of the trail. */
5908 removed_trails_count = remove_matching_trails (disconnected_peer,
5910 current_finger->trails_count =
5911 current_finger->trails_count - removed_trails_count;
5912 if (0 == current_finger->trails_count)
5914 current_finger->is_present = GNUNET_NO;
5915 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5922 * Method called whenever a peer disconnects.
5924 * @param cls closure
5925 * @param peer peer identity this notification is about
5928 handle_core_disconnect (void *cls,
5929 const struct GNUNET_PeerIdentity *peer)
5931 struct FriendInfo *remove_friend;
5932 struct P2PPendingMessage *pos;
5933 unsigned int discarded;
5935 /* If disconnected to own identity, then return. */
5936 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5939 if(NULL == (remove_friend =
5940 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
5942 DEBUG("\n friend already disconnected.");
5946 remove_matching_fingers (peer);
5947 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5948 GNUNET_assert (GNUNET_YES ==
5949 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5953 /* Remove all the messages queued in pending list of this peer is discarded.*/
5954 if (remove_friend->th != NULL)
5956 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
5957 remove_friend->th = NULL;
5961 while (NULL != (pos = remove_friend->head))
5963 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
5968 GNUNET_STATISTICS_update (GDS_stats,
5970 ("# Queued messages discarded (peer disconnected)"),
5971 discarded, GNUNET_NO);
5972 //GNUNET_free (remove_friend);
5974 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5977 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5979 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5980 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5988 * Method called whenever a peer connects.
5990 * @param cls closure
5991 * @param peer_identity peer identity this notification is about
5994 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5996 struct FriendInfo *friend;
5998 /* Check for connect to self message */
5999 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
6002 /* If peer already exists in our friend_peermap, then exit. */
6003 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
6010 friend = GNUNET_new (struct FriendInfo);
6011 friend->id = *peer_identity;
6013 GNUNET_assert (GNUNET_OK ==
6014 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
6015 peer_identity, friend,
6016 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
6018 /* FIXME: now we are not making a distinction between fingers which are friends
6019 * also.But later, we should add a congestion timestamp on the friend, so that it is
6020 * selected after some time out. This is to ensure that both peers have added
6021 * each other as their friend. */
6022 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
6023 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
6025 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
6031 * To be called on core init/fail.
6033 * @param cls service closure
6034 * @param identity the public identity of this peer
6037 core_init (void *cls,
6038 const struct GNUNET_PeerIdentity *identity)
6040 my_identity = *identity;
6045 * Initialize finger table entries.
6048 finger_table_init ()
6050 memset (&finger_table, 0, sizeof (finger_table));
6055 * Initialize neighbours subsystem.
6056 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
6059 GDS_NEIGHBOURS_init (void)
6061 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
6062 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
6063 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
6064 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
6065 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
6066 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
6067 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
6068 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
6069 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
6070 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
6071 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
6072 sizeof (struct PeerTrailTearDownMessage)},
6073 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
6074 {&handle_dht_p2p_notify_succ_confirmation, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION,
6075 sizeof (struct PeerNotifyConfirmationMessage)},
6079 #if ENABLE_MALICIOUS
6084 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
6085 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
6086 GNUNET_NO, core_handlers);
6088 if (NULL == core_api)
6089 return GNUNET_SYSERR;
6091 //TODO: check size of this peer map?
6092 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
6093 finger_table_init ();
6094 successor_times = 10;
6095 fingers_round_count = 5;
6096 find_finger_trail_task_next_send_time.rel_value_us =
6097 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
6098 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6099 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
6101 verify_successor_next_send_time.rel_value_us =
6102 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
6103 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6104 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
6106 verify_successor_retry_time.rel_value_us =
6107 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6108 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6109 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6111 notify_successor_retry_time.rel_value_us =
6112 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6113 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6114 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6122 * Free the memory held up by trails of a finger.
6125 delete_finger_table_entries()
6130 for(i = 0; i < MAX_FINGERS; i++)
6132 if(GNUNET_YES == finger_table[i].is_present)
6134 for(j = 0; j < finger_table[i].trails_count; j++)
6135 free_trail(&finger_table[i].trail_list[i]);
6142 * Shutdown neighbours subsystem.
6145 GDS_NEIGHBOURS_done (void)
6147 if (NULL == core_api)
6150 GNUNET_CORE_disconnect (core_api);
6153 delete_finger_table_entries();
6154 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6155 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6156 friend_peermap = NULL;
6158 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
6160 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6161 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
6164 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
6166 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6167 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
6170 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_retry_task)
6172 struct VerifySuccessorContext *ctx;
6173 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
6175 send_verify_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
6178 if (send_notify_new_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
6180 struct SendNotifyContext *notify_ctx;
6181 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
6182 GNUNET_free (notify_ctx->successor_trail);
6183 GNUNET_free (notify_ctx);
6184 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
6192 * @return my identity
6194 struct GNUNET_PeerIdentity
6195 GDS_NEIGHBOURS_get_my_id (void)
6200 /* end of gnunet-service-xdht_neighbours.c */