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
56 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
59 * Maximum possible fingers (including predecessor) of a peer
61 #define MAX_FINGERS 65
64 * Maximum allowed number of pending messages per friend peer.
66 #define MAXIMUM_PENDING_PER_FRIEND 64
69 * How long to wait before sending another find finger trail request
71 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
74 * How long to wait before sending another verify successor message.
76 #define DHT_SEND_VERIFY_SUCCESSOR_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
79 * How long to wait before sending another verify successor message.
81 #define DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
84 * How long to wait before retrying notify successor.
86 #define DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
89 * How long at most to wait for transmission of a request to a friend ?
91 #define PENDING_MESSAGE_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
94 * Duration for which I may remain congested.
95 * Note: Its a static value. In future, a peer may do some analysis and calculate
96 * congestion_timeout based on 'some' parameters.
98 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
101 * In case we don't hear back from the current successor, then we can start
104 #define WAIT_NOTIFY_CONFIRMATION GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 200)
107 * Maximum number of trails allowed to go through a friend.
109 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
112 * Maximum number of trails stored per finger.
114 #define MAXIMUM_TRAILS_PER_FINGER 4
117 * Finger map index for predecessor entry in finger table.
119 #define PREDECESSOR_FINGER_ID 64
122 * FIXME: Its use only at 3 places check if you can remove it.
123 * To check if a finger is predecessor or not.
125 enum GDS_NEIGHBOURS_finger_type
127 GDS_FINGER_TYPE_PREDECESSOR = 1,
128 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
131 GNUNET_NETWORK_STRUCT_BEGIN
136 struct PeerPutMessage
139 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
141 struct GNUNET_MessageHeader header;
146 uint32_t options GNUNET_PACKED;
151 uint32_t block_type GNUNET_PACKED;
156 uint32_t hop_count GNUNET_PACKED;
159 * Replication level for this message
160 * In the current implementation, this value is not used.
162 uint32_t desired_replication_level GNUNET_PACKED;
165 * Length of the PUT path that follows (if tracked).
167 uint32_t put_path_length GNUNET_PACKED;
170 * Best known destination (could be my friend or finger) which should
171 * get this message next.
173 struct GNUNET_PeerIdentity best_known_destination;
176 * In case best_known_destination is a finger, then trail to reach
177 * to that finger. Else its default value is 0.
179 struct GNUNET_HashCode intermediate_trail_id;
182 * When does the content expire?
184 struct GNUNET_TIME_AbsoluteNBO expiration_time;
187 * The key to store the value under.
189 struct GNUNET_HashCode key GNUNET_PACKED;
191 /* put path (if tracked) */
200 struct PeerGetMessage
203 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
205 struct GNUNET_MessageHeader header;
210 uint32_t options GNUNET_PACKED;
213 * Desired content type.
215 uint32_t block_type GNUNET_PACKED;
220 uint32_t hop_count GNUNET_PACKED;
223 * Desired replication level for this request.
224 * In the current implementation, this value is not used.
226 uint32_t desired_replication_level GNUNET_PACKED;
229 * Total number of peers in get path.
231 unsigned int get_path_length;
234 * Best known destination (could be my friend or finger) which should
235 * get this message next.
237 struct GNUNET_PeerIdentity best_known_destination;
240 * In case best_known_destination is a finger, then trail to reach
241 * to that finger. Else its default value is 0.
243 struct GNUNET_HashCode intermediate_trail_id;
246 * The key we are looking for.
248 struct GNUNET_HashCode key;
251 /* struct GNUNET_PeerIdentity[]*/
257 struct PeerGetResultMessage
260 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
262 struct GNUNET_MessageHeader header;
265 * The type for the data.
267 uint32_t type GNUNET_PACKED;
270 * Number of peers recorded in the outgoing path from source to the
271 * stored location of this message.
273 uint32_t put_path_length GNUNET_PACKED;
276 * Length of the GET path that follows (if tracked).
278 uint32_t get_path_length GNUNET_PACKED;
281 * Peer which queried for get and should get the result.
283 struct GNUNET_PeerIdentity querying_peer;
286 * When does the content expire?
288 struct GNUNET_TIME_Absolute expiration_time;
291 * The key of the corresponding GET request.
293 struct GNUNET_HashCode key;
295 /* put path (if tracked) */
297 /* get path (if tracked) */
304 * P2P Trail setup message
306 struct PeerTrailSetupMessage
309 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
311 struct GNUNET_MessageHeader header;
314 * Is source_peer trying to setup the trail to a predecessor or any finger.
316 uint32_t is_predecessor;
319 * Peer closest to this value will be our finger.
321 uint64_t final_destination_finger_value;
324 * Source peer which wants to setup the trail to one of its finger.
326 struct GNUNET_PeerIdentity source_peer;
329 * Best known destination (could be my friend or finger) which should
330 * get this message next.
332 * FIXME: this could be removed if we include trail_source / trail_dest
333 * in the routing table. This way we save 32 bytes of bandwidth by using
334 * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID))
336 struct GNUNET_PeerIdentity best_known_destination;
339 * In case best_known_destination is a finger, then trail id of trail to
340 * reach to this finger.
342 struct GNUNET_HashCode intermediate_trail_id;
345 * Trail id for trail which we are trying to setup.
347 struct GNUNET_HashCode trail_id;
349 /* List of peers which are part of trail setup so far.
350 * Trail does NOT include source_peer and peer which will be closest to
351 * ultimate_destination_finger_value.
352 * struct GNUNET_PeerIdentity trail[]
357 * P2P Trail Setup Result message
359 struct PeerTrailSetupResultMessage
363 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
365 struct GNUNET_MessageHeader header;
368 * Finger to which we have found the path.
370 struct GNUNET_PeerIdentity finger_identity;
373 * Peer which started trail_setup to find trail to finger_identity
375 struct GNUNET_PeerIdentity querying_peer;
378 * Is the trail setup to querying_peer's predecessor or finger?
380 uint32_t is_predecessor;
383 * Value to which finger_identity is the closest peer.
385 uint64_t ulitmate_destination_finger_value;
388 * Identifier of the trail from querying peer to finger_identity, NOT
389 * including both endpoints.
391 struct GNUNET_HashCode trail_id;
393 /* List of peers which are part of the trail from querying peer to
394 * finger_identity, NOT including both endpoints.
395 * struct GNUNET_PeerIdentity trail[]
400 * P2P Verify Successor Message.
402 struct PeerVerifySuccessorMessage
405 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
407 struct GNUNET_MessageHeader header;
410 * Peer which wants to verify its successor.
412 struct GNUNET_PeerIdentity source_peer;
415 * Source Peer's current successor.
417 struct GNUNET_PeerIdentity successor;
420 * Identifier of trail to reach from source_peer to successor.
422 struct GNUNET_HashCode trail_id;
424 /* List of the peers which are part of trail to reach from source_peer
425 * to successor, NOT including them
426 * struct GNUNET_PeerIdentity trail[]
431 * P2P Verify Successor Result Message
433 struct PeerVerifySuccessorResultMessage
436 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
438 struct GNUNET_MessageHeader header;
441 * Peer which sent the request to verify its successor.
443 struct GNUNET_PeerIdentity querying_peer;
446 * Successor to which PeerVerifySuccessorMessage was sent.
448 struct GNUNET_PeerIdentity current_successor;
451 * Current Predecessor of source_successor. It can be same as querying peer
452 * or different. In case it is different then it can be querying_peer's
453 * probable successor.
455 struct GNUNET_PeerIdentity probable_successor;
458 * Trail identifier of trail from querying_peer to current_successor.
460 struct GNUNET_HashCode trail_id;
463 * Direction in which we are looking at the trail.
465 uint32_t trail_direction;
467 /* In case probable_successor != querying_peer, then trail to reach from
468 * querying_peer to probable_successor, NOT including end points.
469 * struct GNUNET_PeerIdentity trail[]
474 * P2P Notify New Successor Message.
476 struct PeerNotifyNewSuccessorMessage
479 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
481 struct GNUNET_MessageHeader header;
484 * Peer which wants to notify its new successor.
486 struct GNUNET_PeerIdentity source_peer;
489 * New successor of source_peer.
491 struct GNUNET_PeerIdentity new_successor;
494 * Unique identifier of the trail from source_peer to new_successor,
495 * NOT including the endpoints.
497 struct GNUNET_HashCode trail_id;
499 /* List of peers in trail from source_peer to new_successor,
500 * NOT including the endpoints.
501 * struct GNUNET_PeerIdentity trail[]
506 * P2P Notify Successor Confirmation message.
508 struct PeerNotifyConfirmationMessage
511 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
513 struct GNUNET_MessageHeader header;
516 * Unique identifier of the trail.
518 struct GNUNET_HashCode trail_id;
521 * Direction of trail.
523 uint32_t trail_direction;
528 * P2P Trail Tear Down message.
530 struct PeerTrailTearDownMessage
533 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
535 struct GNUNET_MessageHeader header;
538 * Unique identifier of the trail.
540 struct GNUNET_HashCode trail_id;
543 * Direction of trail.
545 uint32_t trail_direction;
550 * P2P Trail Rejection Message.
552 struct PeerTrailRejectionMessage
555 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
557 struct GNUNET_MessageHeader header;
560 * Peer which wants to set up the trail.
562 struct GNUNET_PeerIdentity source_peer;
565 * Peer which sent trail rejection message as it it congested.
567 struct GNUNET_PeerIdentity congested_peer;
570 * Peer identity closest to this value will be finger of
573 uint64_t ultimate_destination_finger_value;
576 * Is source_peer trying to setup the trail to its predecessor or finger.
578 uint32_t is_predecessor;
581 * Identifier for the trail that source peer is trying to setup.
583 struct GNUNET_HashCode trail_id;
586 * Relative time for which congested_peer will remain congested.
588 struct GNUNET_TIME_Relative congestion_time;
590 /* Trail_list from source_peer to peer which sent the message for trail setup
591 * to congested peer. This trail does NOT include source_peer.
592 struct GNUNET_PeerIdnetity trail[]*/
596 * P2P Add Trail Message.
598 struct PeerAddTrailMessage
601 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
603 struct GNUNET_MessageHeader header;
606 * Source of the routing trail.
608 struct GNUNET_PeerIdentity source_peer;
611 * Destination of the routing trail.
613 struct GNUNET_PeerIdentity destination_peer;
616 * Unique identifier of the trail from source_peer to destination_peer,
617 * NOT including the endpoints.
619 struct GNUNET_HashCode trail_id;
621 /* Trail from source peer to destination peer, NOT including them.
622 * struct GNUNET_PeerIdentity trail[]
627 GNUNET_NETWORK_STRUCT_END
630 * Linked list of messages to send to a particular other peer.
632 struct P2PPendingMessage
635 * Pointer to next item in the list
637 struct P2PPendingMessage *next;
640 * Pointer to previous item in the list
642 struct P2PPendingMessage *prev;
645 * Message importance level. FIXME: used? useful?
647 unsigned int importance;
650 * When does this message time out?
652 struct GNUNET_TIME_Absolute timeout;
655 * Actual message to be sent, allocated at the end of the struct:
656 * // msg = (cast) &pm[1];
657 * // memcpy (&pm[1], data, len);
659 const struct GNUNET_MessageHeader *msg;
664 * Entry in friend_peermap.
671 struct GNUNET_PeerIdentity id;
674 * Number of trails for which this friend is the first hop or if the friend
677 unsigned int trails_count;
680 * Count of outstanding messages for this friend.
682 unsigned int pending_count;
685 * In case not 0, then amount of time for which this friend is congested.
687 struct GNUNET_TIME_Absolute congestion_timestamp;
690 // TODO : Change name of head and tail to pending_messages_list_head and so.
692 * Head of pending messages to be sent to this friend.
694 struct P2PPendingMessage *head;
697 * Tail of pending messages to be sent to this friend.
699 struct P2PPendingMessage *tail;
702 * Core handle for sending messages to this friend.
704 struct GNUNET_CORE_TransmitHandle *th;
709 * An individual element of the trail to reach to a finger.
714 * Pointer to next item in the list
716 struct Trail_Element *next;
719 * Pointer to prev item in the list
721 struct Trail_Element *prev;
724 * An element in this trail.
726 struct GNUNET_PeerIdentity peer;
730 * Information about an individual trail.
737 struct Trail_Element *trail_head;
742 struct Trail_Element *trail_tail;
745 * Unique identifier of this trail.
747 struct GNUNET_HashCode trail_id;
750 * Length of trail pointed
752 unsigned int trail_length;
755 * Is there a valid trail entry.
757 unsigned int is_present;
761 * An entry in finger_table
768 struct GNUNET_PeerIdentity finger_identity;
771 * In case not 0, this amount is time to wait for notify successor message.
772 * Used ONLY for successor. NOT for any other finger.
774 struct GNUNET_TIME_Absolute wait_notify_confirmation;
777 * Is any finger stored at this finger index.
779 unsigned int is_present;
782 * Index in finger peer map
784 uint32_t finger_table_index;
787 * Number of trails setup so far for this finger.
788 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
790 uint32_t trails_count;
793 * Array of trails to reach to this finger.
795 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
800 * Stores information about the peer which is closest to destination_finger_value.
801 * 'closest' can be either successor or predecessor depending on is_predecessor
807 * Destination finger value.
809 uint64_t destination_finger_value;
812 * Is finger_value a predecessor or any other finger.
814 unsigned int is_predecessor;
817 * Trail id to reach to peer.
818 * In case peer is my identity or friend, it is set to 0.
820 struct GNUNET_HashCode trail_id;
823 * Next destination. In case of friend and my_identity , it is same as next_hop
824 * In case of finger it is finger identity.
826 struct GNUNET_PeerIdentity best_known_destination;
829 * In case best_known_destination is a finger, then first friend in the trail
830 * to reach to it. In other case, same as best_known_destination.
832 struct GNUNET_PeerIdentity next_hop;
835 * In case finger is the next hop, it contains a valid finger table index
836 * at which the finger is stored. Else, It contains 65, which is out of range
837 * of finger table index.
839 unsigned int finger_table_index;
843 * Context for send_verify_successor_task.
845 struct VerifySuccessorContext
848 * Number of times this has been scheduled.
850 unsigned int num_retries_scheduled;
854 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
855 * get our first friend.
857 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
860 * Task that sends verify successor message. This task is started when we get
861 * our successor for the first time.
863 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_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_retry_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_notify_new_successor_retry_task;
878 * Identity of this peer.
880 static struct GNUNET_PeerIdentity my_identity;
883 * Peer map of all the friends of a peer
885 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
888 * Array of all the fingers.
890 static struct FingerInfo finger_table [MAX_FINGERS];
895 static struct GNUNET_CORE_Handle *core_api;
898 * Handle for the statistics service.
900 //extern struct GNUNET_STATISTICS_Handle *GDS_stats;
903 * The current finger index that we have want to find trail to. We start the
904 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
905 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
906 * we reset this index to 0.
908 static unsigned int current_search_finger_index;
911 * Time duration to schedule find finger trail task.
913 static struct GNUNET_TIME_Relative find_finger_trail_task_next_send_time;
916 * Time duration to schedule verify successor task.
918 static struct GNUNET_TIME_Relative verify_successor_next_send_time;
921 * Time duration to send verify successor again, if result was not received in time.
923 static struct GNUNET_TIME_Relative verify_successor_retry_time;
926 * Time duration to retry send_notify_successor.
928 static struct GNUNET_TIME_Relative notify_successor_retry_time;
931 * Are we waiting for confirmation from our new successor that it got the
934 //static unsigned int waiting_for_notify_confirmation;
936 /* Below variables are used only for testing, and statistics collection. */
938 * Should we store our topology predecessor and successor IDs into statistics?
940 unsigned int track_topology;
943 * Should I be a malicious peer and drop the PUT/GET packets?
944 * if 0 then NOT malicious.
946 unsigned int act_malicious;
949 * Count of fingers found. Ideally we should have O(logn) fingers for a
952 static unsigned int total_fingers_found;
955 * Number of times we found the same successor.
957 static unsigned int successor_times;
960 * Number of rounds for which we should search for finger.
962 static unsigned int fingers_round_count;
964 * Called when core is ready to send a message we asked for
965 * out to the destination.
967 * @param cls the 'struct FriendInfo' of the target friend
968 * @param size number of bytes available in buf
969 * @param buf where the callee should write the message
970 * @return number of bytes written to buf
973 core_transmit_notify (void *cls, size_t size, void *buf)
975 struct FriendInfo *peer = cls;
977 struct P2PPendingMessage *pending;
982 while ((NULL != (pending = peer->head)) &&
983 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
985 peer->pending_count--;
986 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
987 GNUNET_free (pending);
991 /* no messages pending */
997 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
998 GNUNET_CORE_PRIO_BEST_EFFORT,
999 GNUNET_TIME_absolute_get_remaining
1000 (pending->timeout), &peer->id,
1001 ntohs (pending->msg->size),
1002 &core_transmit_notify, peer);
1003 GNUNET_break (NULL != peer->th);
1007 while ((NULL != (pending = peer->head)) &&
1008 (size - off >= (msize = ntohs (pending->msg->size))))
1010 GNUNET_STATISTICS_update (GDS_stats,
1012 ("# Bytes transmitted to other peers"), msize,
1014 memcpy (&cbuf[off], pending->msg, msize);
1016 peer->pending_count--;
1017 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1018 GNUNET_free (pending);
1020 if (peer->head != NULL)
1023 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1024 GNUNET_CORE_PRIO_BEST_EFFORT,
1025 GNUNET_TIME_absolute_get_remaining
1026 (pending->timeout), &peer->id, msize,
1027 &core_transmit_notify, peer);
1028 GNUNET_break (NULL != peer->th);
1035 * Transmit all messages in the friend's message queue.
1037 * @param peer message queue to process
1040 process_friend_queue (struct FriendInfo *peer)
1042 struct P2PPendingMessage *pending;
1044 if (NULL == (pending = peer->head))
1048 if (NULL != peer->th)
1054 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1055 pending->importance,
1056 GNUNET_TIME_absolute_get_remaining
1057 (pending->timeout), &peer->id,
1058 ntohs (pending->msg->size),
1059 &core_transmit_notify, peer);
1060 GNUNET_break (NULL != peer->th);
1064 #if ENABLE_MALICIOUS
1066 * Set the ENABLE_MALICIOUS value to malicious.
1070 GDS_NEIGHBOURS_act_malicious (unsigned int malicious)
1072 act_malicious = malicious;
1078 * Construct a trail setup message and forward it to target_friend
1079 * @param source_peer Peer which wants to setup the trail
1080 * @param ultimate_destination_finger_value Peer identity closest to this value
1081 * will be finger to @a source_peer
1082 * @param best_known_destination Best known destination (could be finger or friend)
1083 * which should get this message. In case it is
1084 * friend, then it is same as target_friend
1085 * @param target_friend Friend to which message is forwarded now.
1086 * @param trail_length Total number of peers in trail setup so far.
1087 * @param trail_peer_list Trail setup so far
1088 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1089 * @param trail_id Unique identifier for the trail we are trying to setup.
1090 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1091 * best_known_destination when its a finger. If not
1092 * used then set to 0.
1095 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1096 uint64_t ultimate_destination_finger_value,
1097 struct GNUNET_PeerIdentity best_known_destination,
1098 struct FriendInfo *target_friend,
1099 unsigned int trail_length,
1100 const struct GNUNET_PeerIdentity *trail_peer_list,
1101 unsigned int is_predecessor,
1102 struct GNUNET_HashCode trail_id,
1103 struct GNUNET_HashCode intermediate_trail_id)
1105 struct P2PPendingMessage *pending;
1106 struct PeerTrailSetupMessage *tsm;
1107 struct GNUNET_PeerIdentity *peer_list;
1110 msize = sizeof (struct PeerTrailSetupMessage) +
1111 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1113 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1119 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1121 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1124 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1125 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1126 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1127 pending->msg = &(tsm->header);
1128 tsm->header.size = htons (msize);
1129 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1130 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1131 tsm->source_peer = source_peer;
1132 tsm->best_known_destination = best_known_destination;
1133 tsm->is_predecessor = htonl (is_predecessor);
1134 tsm->trail_id = trail_id;
1135 tsm->intermediate_trail_id = intermediate_trail_id;
1137 if (trail_length > 0)
1139 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1140 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1143 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1144 target_friend->pending_count++;
1145 process_friend_queue (target_friend);
1150 * Construct a trail setup result message and forward it to target friend.
1151 * @param querying_peer Peer which sent the trail setup request and should get
1153 * @param Finger Peer to which the trail has been setup to.
1154 * @param target_friend Friend to which this message should be forwarded.
1155 * @param trail_length Numbers of peers in the trail.
1156 * @param trail_peer_list Peers which are part of the trail from
1157 * querying_peer to Finger, NOT including them.
1158 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1159 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1161 * @param trail_id Unique identifier of the trail.
1164 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1165 struct GNUNET_PeerIdentity finger,
1166 struct FriendInfo *target_friend,
1167 unsigned int trail_length,
1168 const struct GNUNET_PeerIdentity *trail_peer_list,
1169 unsigned int is_predecessor,
1170 uint64_t ultimate_destination_finger_value,
1171 struct GNUNET_HashCode trail_id)
1173 struct P2PPendingMessage *pending;
1174 struct PeerTrailSetupResultMessage *tsrm;
1175 struct GNUNET_PeerIdentity *peer_list;
1178 msize = sizeof (struct PeerTrailSetupResultMessage) +
1179 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1181 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1187 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1189 GNUNET_STATISTICS_update (GDS_stats,
1190 gettext_noop ("# P2P messages dropped due to full queue"),
1194 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1195 pending->importance = 0;
1196 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1197 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1198 pending->msg = &tsrm->header;
1199 tsrm->header.size = htons (msize);
1200 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1201 tsrm->querying_peer = querying_peer;
1202 tsrm->finger_identity = finger;
1203 tsrm->is_predecessor = htonl (is_predecessor);
1204 tsrm->trail_id = trail_id;
1205 tsrm->ulitmate_destination_finger_value =
1206 GNUNET_htonll (ultimate_destination_finger_value);
1207 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1208 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1210 /* Send the message to chosen friend. */
1211 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1212 target_friend->pending_count++;
1213 process_friend_queue (target_friend);
1217 * Send notify successor confirmation message.
1218 * @param trail_id Unique Identifier of the trail.
1219 * @param trail_direction Destination to Source.
1220 * @param target_friend Friend to get this message next.
1223 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (struct GNUNET_HashCode trail_id,
1224 unsigned int trail_direction,
1225 struct FriendInfo *target_friend)
1227 struct PeerNotifyConfirmationMessage *ncm;
1228 struct P2PPendingMessage *pending;
1231 msize = sizeof (struct PeerNotifyConfirmationMessage);
1232 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1238 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1240 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1244 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1245 pending->importance = 0; /* FIXME */
1246 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1247 ncm = (struct PeerNotifyConfirmationMessage *) &pending[1];
1248 pending->msg = &ncm->header;
1249 ncm->header.size = htons (msize);
1250 ncm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION);
1251 ncm->trail_id = trail_id;
1252 ncm->trail_direction = htonl (trail_direction);
1254 /* Send the message to chosen friend. */
1255 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1256 target_friend->pending_count++;
1257 process_friend_queue (target_friend);
1262 * Send trail rejection message to target friend
1263 * @param source_peer Peer which is trying to setup the trail.
1264 * @param ultimate_destination_finger_value Peer closest to this value will be
1265 * @a source_peer's finger
1266 * @param congested_peer Peer which sent this message as it is congested.
1267 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1268 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1269 * by congested_peer. This does NOT include @a source_peer
1270 * and congested_peer.
1271 * @param trail_length Total number of peers in trail_peer_list, NOT including
1272 * @a source_peer and @a congested_peer
1273 * @param trail_id Unique identifier of this trail.
1274 * @param congestion_timeout Duration given by congested peer as an estimate of
1275 * how long it may remain congested.
1278 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1279 uint64_t ultimate_destination_finger_value,
1280 struct GNUNET_PeerIdentity congested_peer,
1281 unsigned int is_predecessor,
1282 const struct GNUNET_PeerIdentity *trail_peer_list,
1283 unsigned int trail_length,
1284 struct GNUNET_HashCode trail_id,
1285 struct FriendInfo *target_friend,
1286 const struct GNUNET_TIME_Relative congestion_timeout)
1288 struct PeerTrailRejectionMessage *trm;
1289 struct P2PPendingMessage *pending;
1290 struct GNUNET_PeerIdentity *peer_list;
1293 msize = sizeof (struct PeerTrailRejectionMessage) +
1294 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1296 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1302 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1304 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1308 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1309 pending->importance = 0;
1310 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1311 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1312 pending->msg = &trm->header;
1313 trm->header.size = htons (msize);
1314 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1315 trm->source_peer = source_peer;
1316 trm->congested_peer = congested_peer;
1317 trm->congestion_time = congestion_timeout;
1318 trm->is_predecessor = htonl (is_predecessor);
1319 trm->trail_id = trail_id;
1320 trm->ultimate_destination_finger_value =
1321 GNUNET_htonll (ultimate_destination_finger_value);
1323 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1324 if (trail_length > 0)
1326 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1329 /* Send the message to chosen friend. */
1330 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1331 target_friend->pending_count++;
1332 process_friend_queue (target_friend);
1337 * Construct a verify successor message and forward it to target_friend.
1338 * @param source_peer Peer which wants to verify its successor.
1339 * @param successor Peer which is @a source_peer's current successor.
1340 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1341 * NOT including them.
1342 * @param trail List of peers which are part of trail to reach from @a source_peer
1343 * to @a successor, NOT including them.
1344 * @param trail_length Total number of peers in @a trail.
1345 * @param target_friend Next friend to get this message.
1348 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1349 struct GNUNET_PeerIdentity successor,
1350 struct GNUNET_HashCode trail_id,
1351 struct GNUNET_PeerIdentity *trail,
1352 unsigned int trail_length,
1353 struct FriendInfo *target_friend)
1355 struct PeerVerifySuccessorMessage *vsm;
1356 struct P2PPendingMessage *pending;
1357 struct GNUNET_PeerIdentity *peer_list;
1360 msize = sizeof (struct PeerVerifySuccessorMessage) +
1361 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1363 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1369 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1371 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1375 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1376 pending->importance = 0; /* FIXME */
1377 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1378 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1379 pending->msg = &vsm->header;
1380 vsm->header.size = htons (msize);
1381 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1382 vsm->source_peer = source_peer;
1383 vsm->successor = successor;
1384 vsm->trail_id = trail_id;
1385 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1386 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1388 /* Send the message to chosen friend. */
1389 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1390 target_friend->pending_count++;
1391 process_friend_queue (target_friend);
1396 * FIXME: In every function we pass target friend except for this one.
1397 * so, either change everything or this one. also, should se just store
1398 * the pointer to friend in routing table rather than gnunet_peeridentity.
1399 * if yes then we should keep friend info in.h andmake lot of changes.
1400 * Construct a trail teardown message and forward it to target friend.
1402 * @param trail_id Unique identifier of the trail.
1403 * @param trail_direction Direction of trail.
1404 * @param target_friend Friend to get this message.
1407 GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_HashCode *trail_id,
1408 unsigned int trail_direction,
1409 const struct GNUNET_PeerIdentity *peer)
1411 struct PeerTrailTearDownMessage *ttdm;
1412 struct P2PPendingMessage *pending;
1413 struct FriendInfo *target_friend;
1416 msize = sizeof (struct PeerTrailTearDownMessage);
1417 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1423 if (NULL == (target_friend =
1424 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
1426 /* FIXME: In what case friend can be null. ?*/
1431 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1433 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1437 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1438 pending->importance = 0; /* FIXME */
1439 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1440 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1441 pending->msg = &ttdm->header;
1442 ttdm->header.size = htons (msize);
1443 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1444 ttdm->trail_id = *trail_id;
1445 ttdm->trail_direction = htonl (trail_direction);
1447 /* Send the message to chosen friend. */
1448 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1449 target_friend->pending_count++;
1450 process_friend_queue (target_friend);
1455 * Construct a verify successor result message and send it to target_friend
1456 * @param querying_peer Peer which sent the verify successor message.
1457 * @param source_successor Current_successor of @a querying_peer.
1458 * @param current_predecessor Current predecessor of @a successor. Could be same
1459 * or different from @a querying_peer.
1460 * @param trail_id Unique identifier of the trail from @a querying_peer to
1461 * @a successor, NOT including them.
1462 * @param trail List of peers which are part of trail from @a querying_peer to
1463 * @a successor, NOT including them.
1464 * @param trail_length Total number of peers in @a trail
1465 * @param trail_direction Direction in which we are sending the message. In this
1466 * case we are sending result from @a successor to @a querying_peer.
1467 * @param target_friend Next friend to get this message.
1470 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1471 struct GNUNET_PeerIdentity current_successor,
1472 struct GNUNET_PeerIdentity probable_successor,
1473 struct GNUNET_HashCode trail_id,
1474 const struct GNUNET_PeerIdentity *trail,
1475 unsigned int trail_length,
1476 enum GDS_ROUTING_trail_direction trail_direction,
1477 struct FriendInfo *target_friend)
1479 struct PeerVerifySuccessorResultMessage *vsmr;
1480 struct P2PPendingMessage *pending;
1481 struct GNUNET_PeerIdentity *peer_list;
1484 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1485 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1487 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1493 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1495 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1499 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1500 pending->importance = 0; /* FIXME */
1501 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1502 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1503 pending->msg = &vsmr->header;
1504 vsmr->header.size = htons (msize);
1505 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1506 vsmr->querying_peer = querying_peer;
1507 vsmr->current_successor = current_successor;
1508 vsmr->probable_successor = probable_successor;
1509 vsmr->trail_direction = htonl (trail_direction);
1510 vsmr->trail_id = trail_id;
1511 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1512 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1514 /* Send the message to chosen friend. */
1515 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1516 target_friend->pending_count++;
1517 process_friend_queue (target_friend);
1522 * Construct a notify new successor message and send it to target_friend
1523 * @param source_peer Peer which wants to notify to its new successor that it
1524 * could be its predecessor.
1525 * @param successor New successor of @a source_peer
1526 * @param successor_trail List of peers in Trail to reach from
1527 * @a source_peer to @a new_successor, NOT including
1529 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1530 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1531 * @param target_friend Next friend to get this message.
1534 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1535 struct GNUNET_PeerIdentity successor,
1536 const struct GNUNET_PeerIdentity *successor_trail,
1537 unsigned int successor_trail_length,
1538 struct GNUNET_HashCode succesor_trail_id,
1539 struct FriendInfo *target_friend)
1541 struct PeerNotifyNewSuccessorMessage *nsm;
1542 struct P2PPendingMessage *pending;
1543 struct GNUNET_PeerIdentity *peer_list;
1546 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1547 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1549 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1555 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1557 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1561 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1562 pending->importance = 0; /* FIXME */
1563 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1564 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1565 pending->msg = &nsm->header;
1566 nsm->header.size = htons (msize);
1567 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1568 nsm->new_successor = successor;
1569 nsm->source_peer = source_peer;
1570 nsm->trail_id = succesor_trail_id;
1571 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1572 memcpy (peer_list, successor_trail,
1573 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1575 /* Send the message to chosen friend. */
1576 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1577 target_friend->pending_count++;
1578 process_friend_queue (target_friend);
1583 * Construct an add_trail message and send it to target_friend
1584 * @param source_peer Source of the trail.
1585 * @param destination_peer Destination of the trail.
1586 * @param trail_id Unique identifier of the trail from
1587 * @a source_peer to @a destination_peer, NOT including the endpoints.
1588 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1589 * NOT including the endpoints.
1590 * @param trail_length Total number of peers in @a trail.
1591 * @param target_friend Next friend to get this message.
1594 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1595 struct GNUNET_PeerIdentity destination_peer,
1596 struct GNUNET_HashCode trail_id,
1597 const struct GNUNET_PeerIdentity *trail,
1598 unsigned int trail_length,
1599 struct FriendInfo *target_friend)
1601 struct PeerAddTrailMessage *adm;
1602 struct GNUNET_PeerIdentity *peer_list;
1603 struct P2PPendingMessage *pending;
1606 msize = sizeof (struct PeerAddTrailMessage) +
1607 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1609 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1615 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1617 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1621 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1622 pending->importance = 0; /* FIXME */
1623 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
1624 adm = (struct PeerAddTrailMessage *) &pending[1];
1625 pending->msg = &adm->header;
1626 adm->header.size = htons (msize);
1627 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1628 adm->source_peer = source_peer;
1629 adm->destination_peer = destination_peer;
1630 adm->trail_id = trail_id;
1631 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1632 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1634 /* Send the message to chosen friend. */
1635 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1636 target_friend->pending_count++;
1637 process_friend_queue (target_friend);
1643 * Search my location in trail. In case I am present more than once in the
1644 * trail (can happen during trail setup), then return my lowest index.
1645 * @param trail List of peers
1646 * @return my_index if found
1647 * trail_length + 1 if an entry is present twice, It is an error.
1648 * -1 if no entry found.
1651 search_my_index (const struct GNUNET_PeerIdentity *trail,
1655 int index_seen = trail_length + 1;
1658 for (i = 0; i < trail_length; i++)
1660 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1663 if(index_seen == (trail_length + 1))
1667 DEBUG("Entry is present twice in trail. Its not allowed\n");
1681 * Check if the friend is congested or have reached maximum number of trails
1682 * it can be part of of.
1683 * @param friend Friend to be checked.
1684 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1685 * #GNUNET_YES if friend is either congested or have crossed threshold
1688 is_friend_congested (struct FriendInfo *friend)
1690 if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1691 ((0 == GNUNET_TIME_absolute_get_remaining
1692 (friend->congestion_timestamp).rel_value_us)))
1700 * Select closest finger to value.
1701 * @param peer1 First peer
1702 * @param peer2 Second peer
1703 * @param value Value to be compare
1704 * @return Closest peer
1706 static struct GNUNET_PeerIdentity
1707 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1708 const struct GNUNET_PeerIdentity *peer2,
1711 uint64_t peer1_value;
1712 uint64_t peer2_value;
1714 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1715 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1716 peer1_value = GNUNET_ntohll (peer1_value);
1717 peer2_value = GNUNET_ntohll (peer2_value);
1719 if (peer1_value == value)
1724 if (peer2_value == value)
1729 if (value < peer1_value && peer1_value < peer2_value)
1733 else if (value < peer2_value && peer2_value < peer1_value)
1737 else if (peer1_value < value && value < peer2_value)
1741 else if (peer2_value < value && value < peer1_value)
1745 else if (peer1_value < peer2_value && peer2_value < value)
1749 else // if (peer2_value < peer1_value && peer1_value < value)
1757 * Select closest predecessor to value.
1758 * @param peer1 First peer
1759 * @param peer2 Second peer
1760 * @param value Value to be compare
1761 * @return Peer which precedes value in the network.
1763 static struct GNUNET_PeerIdentity
1764 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1765 const struct GNUNET_PeerIdentity *peer2,
1768 uint64_t peer1_value;
1769 uint64_t peer2_value;
1771 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1772 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1773 peer1_value = GNUNET_ntohll (peer1_value);
1774 peer2_value = GNUNET_ntohll (peer2_value);
1776 if (peer1_value == value)
1781 if (peer2_value == value)
1786 if (value < peer1_value && peer1_value < peer2_value)
1790 else if (value < peer2_value && peer2_value < peer1_value)
1794 else if (peer1_value < value && value < peer2_value)
1798 else if (peer2_value < value && value < peer1_value)
1802 else if (peer1_value < peer2_value && peer2_value < value)
1806 else // if (peer2_value < peer1_value && peer1_value < value)
1818 test_print_trail (struct GNUNET_PeerIdentity *trail,
1819 unsigned int trail_length)
1821 struct GNUNET_PeerIdentity print_peer;
1824 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"),
1825 __FILE__, __func__,__LINE__,trail_length);
1826 for (i =0 ; i< trail_length; i++)
1828 print_peer = trail[i];
1829 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"),
1830 __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer));
1837 * This is a test function to print all the entries of friend table.
1840 test_friend_peermap_print ()
1842 struct FriendInfo *friend;
1843 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1844 struct GNUNET_PeerIdentity print_peer;
1845 struct GNUNET_PeerIdentity key_ret;
1848 print_peer = my_identity;
1849 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1850 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1852 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1854 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1856 (const void **)&friend))
1858 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1859 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1860 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1868 * This is a test function, to print all the entries of finger table.
1871 test_finger_table_print()
1873 struct FingerInfo *finger;
1874 struct GNUNET_PeerIdentity print_peer;
1875 //struct Trail *trail;
1879 print_peer = my_identity;
1880 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1881 for (i = 0; i < MAX_FINGERS; i++)
1883 finger = &finger_table[i];
1885 if (GNUNET_NO == finger->is_present)
1888 print_peer = finger->finger_identity;
1889 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1890 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1893 for (j = 0; j < finger->trails_count; j++)
1895 trail = &finger->trail_list[j];
1896 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1897 struct Trail_Element *element;
1898 element = trail->trail_head;
1899 for (k = 0; k < trail->trail_length; k++)
1901 print_peer = element->peer;
1902 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1903 element = element->next;
1912 * Select the closest peer among two peers (which should not be same)
1913 * with respect to value and finger_table_index
1914 * NOTE: peer1 != peer2
1915 * @param peer1 First peer
1916 * @param peer2 Second peer
1917 * @param value Value relative to which we find the closest
1918 * @param is_predecessor Is value a predecessor or any other finger.
1919 * @return Closest peer among two peers.
1921 static struct GNUNET_PeerIdentity
1922 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1923 const struct GNUNET_PeerIdentity *peer2,
1925 unsigned int is_predecessor)
1927 /* This check is here to ensure that calling function never sends
1928 same peer value in peer1 and peer2. Remove it later. */
1929 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2));
1930 if (1 == is_predecessor)
1931 return select_closest_predecessor (peer1, peer2, value);
1933 // TODO: Change name to something like select_closest_successor!!
1934 return select_closest_finger (peer1, peer2, value);
1939 * Iterate over the list of all the trails of a finger. In case the first
1940 * friend to reach the finger has reached trail threshold or is congested,
1941 * then don't select it. In case there multiple available good trails to reach
1942 * to Finger, choose the one with shortest trail length.
1943 * Note: We use length as parameter. But we can use any other suitable parameter
1945 * @param finger Finger Finger whose trail we have to select.
1946 * @return Trail Selected Trail.
1948 static struct Trail *
1949 select_finger_trail (struct FingerInfo *finger)
1951 struct FriendInfo *friend;
1952 struct Trail *current_finger_trail;
1953 struct Trail *best_trail = NULL;
1956 GNUNET_assert (finger->trails_count > 0);
1957 for (i = 0; i < finger->trails_count; i++)
1959 current_finger_trail = &finger->trail_list[i];
1961 /* No trail stored at this index. */
1962 if (GNUNET_NO == current_finger_trail->is_present)
1965 GNUNET_assert (NULL !=
1967 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1968 ¤t_finger_trail->trail_head->peer)));
1970 /* First friend to reach trail is not free. */
1971 if (GNUNET_YES == is_friend_congested (friend))
1974 if (NULL == best_trail ||
1975 best_trail->trail_length > current_finger_trail->trail_length)
1977 best_trail = current_finger_trail;
1986 * Compare FINGER entry with current successor. If finger's first friend of all
1987 * its trail is not congested and has not crossed trail threshold, then check
1988 * if finger peer identity is closer to final_destination_finger_value than
1989 * current_successor. If yes then update current_successor.
1990 * @param current_successor[in/out]
1994 compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer)
1996 struct FingerInfo *finger;
1997 struct GNUNET_PeerIdentity closest_peer;
1998 struct Trail *finger_trail;
2001 /* Iterate over finger table. */
2002 for (i = 0; i < MAX_FINGERS; i++)
2004 finger = &finger_table[i];
2006 if (GNUNET_NO == finger->is_present)
2009 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2010 ¤t_closest_peer->best_known_destination))
2013 /* If I am my own finger, then ignore this finger. */
2014 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2018 /* If finger is a friend, we have already checked it in previous function. */
2019 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2020 &finger->finger_identity)))
2025 closest_peer = select_closest_peer (&finger->finger_identity,
2026 ¤t_closest_peer->best_known_destination,
2027 current_closest_peer->destination_finger_value,
2028 current_closest_peer->is_predecessor);
2030 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer))
2032 /* Choose one of the trail to reach to finger. */
2033 finger_trail = select_finger_trail (finger);
2035 /* In case no trail found, ignore this finger. */
2036 if (NULL == finger_trail)
2039 current_closest_peer->best_known_destination = closest_peer;
2040 current_closest_peer->next_hop = finger_trail->trail_head->peer;
2041 current_closest_peer->trail_id = finger_trail->trail_id;
2042 current_closest_peer->finger_table_index = i;
2050 * Compare friend entry with current successor.
2051 * If friend identity and current_successor is same, then do nothing.
2052 * If friend is not congested and has not crossed trail threshold, then check
2053 * if friend peer identity is closer to final_destination_finger_value than
2054 * current_successor. If yes then update current_successor.
2055 * @param cls closure
2056 * @param key current public key
2057 * @param value struct Closest_Peer
2058 * @return #GNUNET_YES if we should continue to iterate,
2059 * #GNUNET_NO if not.
2062 compare_friend_and_current_closest_peer (void *cls,
2063 const struct GNUNET_PeerIdentity *key,
2066 struct FriendInfo *friend = value;
2067 struct Closest_Peer *current_closest_peer = cls;
2068 struct GNUNET_PeerIdentity closest_peer;
2070 /* Friend is either congested or has crossed threshold. */
2071 if (GNUNET_YES == is_friend_congested (friend))
2074 /* If current_closest_peer and friend identity are same, then do nothing.*/
2075 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2076 ¤t_closest_peer->best_known_destination))
2082 closest_peer = select_closest_peer (&friend->id,
2083 ¤t_closest_peer->best_known_destination,
2084 current_closest_peer->destination_finger_value,
2085 current_closest_peer->is_predecessor);
2087 /* Is friend the closest successor? */
2088 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer))
2090 current_closest_peer->best_known_destination = friend->id;
2091 current_closest_peer->next_hop = friend->id;
2099 * Initialize current_successor to my_identity.
2100 * @param my_identity My peer identity
2101 * @return Updated closest_peer
2103 static struct Closest_Peer
2104 init_closest_peer (struct GNUNET_PeerIdentity my_identity,
2105 uint64_t destination_finger_value,
2106 unsigned int is_predecessor)
2108 struct Closest_Peer current_closest_peer;
2110 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2111 current_closest_peer.destination_finger_value = destination_finger_value;
2112 current_closest_peer.is_predecessor = is_predecessor;
2113 current_closest_peer.next_hop = my_identity;
2114 current_closest_peer.best_known_destination = my_identity;
2115 current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index.
2116 return current_closest_peer;
2121 * Find locally best known peer, among your own identity, friend and finger list,
2122 * which is closest to given destination_finger_value.
2124 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2126 * @param destination_finger_value Peer closest to this value will be the next destination.
2127 * @param is_predecessor Are we looking for predecessor or finger?
2128 * @return Closest_Peer that contains all the relevant field to reach to
2129 * @a destination_finger_value
2131 static struct Closest_Peer
2132 find_local_best_known_next_hop (uint64_t destination_finger_value,
2133 unsigned int is_predecessor)
2135 struct Closest_Peer current_closest_peer;
2137 /* Initialize current_successor to my_identity. */
2138 current_closest_peer = init_closest_peer (my_identity,
2139 destination_finger_value,
2142 /* Compare each friend entry with current_successor and update current_successor
2143 * with friend if its closest. */
2146 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2147 &compare_friend_and_current_closest_peer,
2148 ¤t_closest_peer));
2150 /* Compare each finger entry with current_successor and update current_successor
2151 * with finger if its closest. */
2152 compare_finger_and_current_closest_peer (¤t_closest_peer);
2153 return current_closest_peer;
2158 * Construct a Put message and send it to target_peer.
2159 * @param key Key for the content
2160 * @param block_type Type of the block
2161 * @param options Routing options
2162 * @param desired_replication_level Desired replication count
2163 * @param best_known_dest Peer to which this message should reach eventually,
2164 * as it is best known destination to me.
2165 * @param intermediate_trail_id Trail id in case
2166 * @param target_peer Peer to which this message will be forwarded.
2167 * @param hop_count Number of hops traversed so far.
2168 * @param put_path_length Total number of peers in @a put_path
2169 * @param put_path Number of peers traversed so far
2170 * @param expiration_time When does the content expire
2171 * @param data Content to store
2172 * @param data_size Size of content @a data in bytes
2175 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2176 enum GNUNET_BLOCK_Type block_type,
2177 enum GNUNET_DHT_RouteOption options,
2178 uint32_t desired_replication_level,
2179 struct GNUNET_PeerIdentity best_known_dest,
2180 struct GNUNET_HashCode intermediate_trail_id,
2181 struct GNUNET_PeerIdentity *target_peer,
2183 uint32_t put_path_length,
2184 struct GNUNET_PeerIdentity *put_path,
2185 struct GNUNET_TIME_Absolute expiration_time,
2186 const void *data, size_t data_size)
2188 struct PeerPutMessage *ppm;
2189 struct P2PPendingMessage *pending;
2190 struct FriendInfo *target_friend;
2191 struct GNUNET_PeerIdentity *pp;
2194 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2195 sizeof (struct PeerPutMessage);
2196 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2198 put_path_length = 0;
2199 msize = data_size + sizeof (struct PeerPutMessage);
2202 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2204 DEBUG("msize = %lu\n",msize);
2209 GNUNET_assert (NULL !=
2211 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2212 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2213 pending->timeout = expiration_time;
2214 ppm = (struct PeerPutMessage *) &pending[1];
2215 pending->msg = &ppm->header;
2216 ppm->header.size = htons (msize);
2217 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2218 ppm->options = htonl (options);
2219 ppm->block_type = htonl (block_type);
2220 ppm->hop_count = htonl (hop_count + 1);
2221 ppm->desired_replication_level = htonl (desired_replication_level);
2222 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2223 ppm->best_known_destination = best_known_dest;
2224 ppm->intermediate_trail_id = intermediate_trail_id;
2226 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2227 ppm->put_path_length = htonl (put_path_length);
2228 if(put_path_length > 0)
2230 memcpy (pp, put_path,
2231 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2233 memcpy (&pp[put_path_length], data, data_size);
2234 GNUNET_assert (NULL != target_friend);
2235 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2236 target_friend->pending_count++;
2237 process_friend_queue (target_friend);
2242 * Handle the put request from the client.
2243 * @param key Key for the content
2244 * @param block_type Type of the block
2245 * @param options Routing options
2246 * @param desired_replication_level Desired replication count
2247 * @param expiration_time When does the content expire
2248 * @param data Content to store
2249 * @param data_size Size of content @a data in bytes
2252 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
2253 enum GNUNET_BLOCK_Type block_type,
2254 enum GNUNET_DHT_RouteOption options,
2255 uint32_t desired_replication_level,
2256 struct GNUNET_TIME_Absolute expiration_time,
2257 const void *data, size_t data_size)
2259 struct GNUNET_PeerIdentity best_known_dest;
2260 struct GNUNET_HashCode intermediate_trail_id;
2261 struct GNUNET_PeerIdentity next_hop;
2263 struct Closest_Peer successor;
2265 memcpy (&key_value, key, sizeof (uint64_t));
2266 key_value = GNUNET_ntohll (key_value);
2267 successor = find_local_best_known_next_hop (key_value,
2268 GDS_FINGER_TYPE_NON_PREDECESSOR);
2269 best_known_dest = successor.best_known_destination;
2270 next_hop = successor.next_hop;
2271 intermediate_trail_id = successor.trail_id;
2273 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2275 DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",GNUNET_h2s(key));
2276 /* I am the destination. */
2277 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2278 block_type,data_size,data);
2279 GDS_CLIENTS_process_put (options, block_type, 0,
2280 ntohl (desired_replication_level),
2281 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time.
2282 key, data, data_size);
2285 /* In case we are sending the request to a finger, then send across all of its
2287 #if ENABLE_MALICIOUS
2288 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2289 &successor.next_hop))
2291 struct FingerInfo *next_hop_finger;
2294 next_hop_finger = &finger_table[successor.finger_table_index];
2295 for (i = 0; i < next_hop_finger->trails_count; i++)
2297 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2299 if(0 == next_hop_finger->trail_list[i].trail_length)
2301 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2302 best_known_dest, intermediate_trail_id, &next_hop,
2303 0, 1, &my_identity, expiration_time,
2307 next_hop = next_hop_finger->trail_list[i].trail_head->peer;
2308 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2310 next_hop_finger->trail_list[i].trail_id,
2311 &next_hop, 0, 1, &my_identity,
2319 GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level,
2320 best_known_dest, intermediate_trail_id, &next_hop,
2321 0, 1, &my_identity, expiration_time,
2326 * Construct a Get message and send it to target_peer.
2327 * @param key Key for the content
2328 * @param block_type Type of the block
2329 * @param options Routing options
2330 * @param desired_replication_level Desired replication count
2331 * @param best_known_dest Peer which should get this message. Same as target peer
2332 * if best_known_dest is a friend else its a finger.
2333 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2334 * in case it is a finger else set to 0.
2335 * @param target_peer Peer to which this message will be forwarded.
2336 * @param hop_count Number of hops traversed so far.
2337 * @param data Content to store
2338 * @param data_size Size of content @a data in bytes
2339 * @param get_path_length Total number of peers in @a get_path
2340 * @param get_path Number of peers traversed so far
2343 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2344 enum GNUNET_BLOCK_Type block_type,
2345 enum GNUNET_DHT_RouteOption options,
2346 uint32_t desired_replication_level,
2347 struct GNUNET_PeerIdentity best_known_dest,
2348 struct GNUNET_HashCode intermediate_trail_id,
2349 struct GNUNET_PeerIdentity *target_peer,
2351 uint32_t get_path_length,
2352 struct GNUNET_PeerIdentity *get_path)
2354 struct PeerGetMessage *pgm;
2355 struct P2PPendingMessage *pending;
2356 struct FriendInfo *target_friend;
2357 struct GNUNET_PeerIdentity *gp;
2360 msize = sizeof (struct PeerGetMessage) +
2361 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2363 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2368 GNUNET_assert (NULL !=
2370 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2372 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2373 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2374 pending->importance = 0; /* FIXME */
2375 pgm = (struct PeerGetMessage *) &pending[1];
2376 pending->msg = &pgm->header;
2377 pgm->header.size = htons (msize);
2378 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2379 pgm->get_path_length = htonl (get_path_length);
2380 pgm->best_known_destination = best_known_dest;
2382 pgm->intermediate_trail_id = intermediate_trail_id;
2383 pgm->hop_count = htonl (hop_count + 1);
2384 pgm->get_path_length = htonl (get_path_length);
2385 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2386 memcpy (gp, get_path,
2387 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2388 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2389 target_friend->pending_count++;
2390 process_friend_queue (target_friend);
2395 * Handle the get request from the client file. If I am destination do
2396 * datacache put and return. Else find the target friend and forward message
2398 * @param key Key for the content
2399 * @param block_type Type of the block
2400 * @param options Routing options
2401 * @param desired_replication_level Desired replication count
2404 GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key,
2405 enum GNUNET_BLOCK_Type block_type,
2406 enum GNUNET_DHT_RouteOption options,
2407 uint32_t desired_replication_level)
2409 struct Closest_Peer successor;
2410 struct GNUNET_PeerIdentity best_known_dest;
2411 struct GNUNET_HashCode intermediate_trail_id;
2414 memcpy (&key_value, key, sizeof (uint64_t));
2415 key_value = GNUNET_ntohll (key_value);
2417 successor = find_local_best_known_next_hop (key_value,
2418 GDS_FINGER_TYPE_NON_PREDECESSOR);
2420 best_known_dest = successor.best_known_destination;
2421 intermediate_trail_id = successor.trail_id;
2423 /* I am the destination. I have the data. */
2424 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2427 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2428 NULL, 0, 1, &my_identity, NULL,&my_identity);
2432 #if ENABLE_MALICIOUS
2433 struct GNUNET_PeerIdentity next_hop;
2434 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
2435 &successor.next_hop))
2437 struct FingerInfo *next_hop_finger;
2440 next_hop_finger = &finger_table[successor.finger_table_index];
2441 for (i = 0; i < next_hop_finger->trails_count; i++)
2443 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
2445 if(0 == next_hop_finger->trail_list[i].trail_length)
2447 GDS_NEIGHBOURS_send_get (key, block_type, options,
2448 desired_replication_level,
2449 best_known_dest,intermediate_trail_id,
2450 &successor.next_hop,
2451 0, 1, &my_identity);
2454 next_hop = next_hop_finger->trail_list[i].trail_head->peer;
2455 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2457 next_hop_finger->trail_list[i].trail_id,
2458 &next_hop, 0, 1, &my_identity);
2464 GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level,
2465 best_known_dest,intermediate_trail_id, &successor.next_hop,
2466 0, 1, &my_identity);
2471 * Send the get result to requesting client.
2472 * @param key Key of the requested data.
2473 * @param type Block type
2474 * @param target_peer Next peer to forward the message to.
2475 * @param source_peer Peer which has the data for the key.
2476 * @param put_path_length Number of peers in @a put_path
2477 * @param put_path Path taken to put the data at its stored location.
2478 * @param get_path_length Number of peers in @a get_path
2479 * @param get_path Path taken to reach to the location of the key.
2480 * @param expiration When will this result expire?
2481 * @param data Payload to store
2482 * @param data_size Size of the @a data
2485 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2486 enum GNUNET_BLOCK_Type type,
2487 const struct GNUNET_PeerIdentity *target_peer,
2488 const struct GNUNET_PeerIdentity *source_peer,
2489 unsigned int put_path_length,
2490 const struct GNUNET_PeerIdentity *put_path,
2491 unsigned int get_path_length,
2492 const struct GNUNET_PeerIdentity *get_path,
2493 struct GNUNET_TIME_Absolute expiration,
2494 const void *data, size_t data_size)
2496 struct PeerGetResultMessage *get_result;
2497 struct GNUNET_PeerIdentity *paths;
2498 struct P2PPendingMessage *pending;
2499 struct FriendInfo *target_friend;
2500 int current_path_index;
2503 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2505 sizeof (struct PeerGetResultMessage);
2507 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2509 put_path_length = 0;
2510 msize = msize - put_path_length;
2514 if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
2519 current_path_index = 0;
2520 if(get_path_length > 0)
2522 current_path_index = search_my_index(get_path, get_path_length);
2523 if (-1 == current_path_index)
2528 if ((get_path_length + 1) == current_path_index)
2530 DEBUG ("Peer found twice in get path. Not allowed \n");
2535 if (0 == current_path_index)
2537 DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",GNUNET_h2s(key),GNUNET_i2s(&my_identity));
2538 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2539 get_path, put_path_length,
2540 put_path, type, data_size, data);
2544 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2545 pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT);
2546 pending->importance = 0;
2547 get_result = (struct PeerGetResultMessage *)&pending[1];
2548 pending->msg = &get_result->header;
2549 get_result->header.size = htons (msize);
2550 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2551 get_result->key = *key;
2552 get_result->querying_peer = *source_peer;
2553 get_result->expiration_time = expiration;
2554 get_result->get_path_length = htonl (get_path_length);
2555 get_result->put_path_length = htonl (put_path_length);
2556 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2557 memcpy (paths, put_path,
2558 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2559 memcpy (&paths[put_path_length], get_path,
2560 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2561 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2563 GNUNET_assert (NULL !=
2565 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2566 &get_path[current_path_index - 1])));
2567 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2568 target_friend->pending_count++;
2569 process_friend_queue (target_friend);
2574 * Randomly choose one of your friends (which is not congested and have not crossed
2575 * trail threshold) from the friend_peermap
2576 * @return Friend Randomly chosen friend.
2577 * NULL in case friend peermap is empty, or all the friends are either
2578 * congested or have crossed trail threshold.
2580 static struct FriendInfo *
2581 select_random_friend ()
2583 unsigned int current_size;
2586 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2587 struct GNUNET_PeerIdentity key_ret;
2588 struct FriendInfo *friend;
2590 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2593 if (0 == current_size)
2596 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2597 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2599 /* Iterate till you don't reach to index. */
2600 for (j = 0; j < index ; j++)
2601 GNUNET_assert (GNUNET_YES ==
2602 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2606 /* Reset the index in friend peermap to 0 as we reached to the end. */
2607 if (j == current_size)
2610 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2611 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2615 /* Get the friend stored at the index, j*/
2616 GNUNET_assert (GNUNET_YES ==
2617 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2619 (const void **)&friend));
2621 /* This friend is not congested and has not crossed trail threshold. */
2622 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2623 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2629 } while (j != index);
2631 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2637 * Compute 64 bit value of finger_identity corresponding to a finger index using
2639 * For all fingers, n.finger[i] = n + pow (2,i),
2640 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2641 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2642 * @param finger_index Index corresponding to which we calculate 64 bit value.
2643 * @return 64 bit value.
2646 compute_finger_identity_value (unsigned int finger_index)
2650 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2651 my_id64 = GNUNET_ntohll (my_id64);
2653 /* Are we looking for immediate predecessor? */
2654 if (PREDECESSOR_FINGER_ID == finger_index)
2655 return (my_id64 - 1);
2658 uint64_t add = (uint64_t)1 << finger_index;
2659 return (my_id64 + add);
2665 * Choose a random friend. Calculate the next finger identity to search,from
2666 * current_search_finger_index. Start looking for the trail to reach to
2667 * finger identity through this random friend.
2669 * @param cls closure for this task
2670 * @param tc the context under which the task is running
2673 send_find_finger_trail_message (void *cls,
2674 const struct GNUNET_SCHEDULER_TaskContext *tc)
2676 struct FriendInfo *target_friend;
2677 struct GNUNET_HashCode trail_id;
2678 struct GNUNET_HashCode intermediate_trail_id;
2679 unsigned int is_predecessor = 0;
2680 uint64_t finger_id_value;
2682 /* Schedule another send_find_finger_trail_message task. After one round of
2683 * finger search, this time is exponentially backoff. */
2684 find_finger_trail_task_next_send_time.rel_value_us =
2685 find_finger_trail_task_next_send_time.rel_value_us +
2686 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2687 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2688 find_finger_trail_task =
2689 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2690 &send_find_finger_trail_message,
2693 /* No space in my routing table. (Source and destination peers also store entries
2694 * in their routing table). */
2695 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2698 target_friend = select_random_friend ();
2699 if (NULL == target_friend)
2704 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2705 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2708 /* Generate a unique trail id for trail we are trying to setup. */
2709 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2710 &trail_id, sizeof (trail_id));
2711 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2712 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2713 target_friend->id, target_friend, 0, NULL,
2714 is_predecessor, trail_id,
2715 intermediate_trail_id);
2720 * In case there are already maximum number of possible trails to reach to a
2721 * finger, then check if the new trail's length is lesser than any of the
2723 * If yes then replace that old trail by new trail.
2725 * Note: Here we are taking length as a parameter to choose the best possible
2726 * trail, but there could be other parameters also like:
2727 * 1. duration of existence of a trail - older the better.
2728 * 2. if the new trail is completely disjoint than the
2729 * other trails, then may be choosing it is better.
2731 * @param finger Finger
2732 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2733 * including the endpoints.
2734 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2735 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2738 select_and_replace_trail (struct FingerInfo *finger,
2739 const struct GNUNET_PeerIdentity *new_trail,
2740 unsigned int new_trail_length,
2741 struct GNUNET_HashCode new_trail_id)
2743 struct Trail *current_trail;
2744 unsigned int largest_trail_length;
2745 unsigned int largest_trail_index;
2746 struct Trail_Element *trail_element;
2747 struct GNUNET_PeerIdentity *next_hop;
2750 largest_trail_length = new_trail_length;
2751 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2753 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2755 for (i = 0; i < finger->trails_count; i++)
2757 current_trail = &finger->trail_list[i];
2758 GNUNET_assert (GNUNET_YES == current_trail->is_present);
2759 if (current_trail->trail_length > largest_trail_length)
2761 largest_trail_length = current_trail->trail_length;
2762 largest_trail_index = i;
2766 /* New trail is not better than existing ones. Send trail teardown. */
2767 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2769 next_hop = GDS_ROUTING_get_next_hop (new_trail_id, GDS_ROUTING_SRC_TO_DEST);
2770 GDS_ROUTING_remove_trail (new_trail_id);
2771 GDS_NEIGHBOURS_send_trail_teardown (&new_trail_id,
2772 GDS_ROUTING_SRC_TO_DEST,
2777 /* Send trail teardown message across the replaced trail. */
2778 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2779 next_hop = GDS_ROUTING_get_next_hop (replace_trail->trail_id, GDS_ROUTING_SRC_TO_DEST);
2780 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2781 GDS_NEIGHBOURS_send_trail_teardown (&replace_trail->trail_id,
2782 GDS_ROUTING_SRC_TO_DEST,
2785 /* Free the trail. */
2786 while (NULL != (trail_element = replace_trail->trail_head))
2788 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2789 replace_trail->trail_tail, trail_element);
2790 GNUNET_free_non_null (trail_element);
2793 /* Add new trial at that location. */
2794 replace_trail->is_present = GNUNET_YES;
2795 replace_trail->trail_length = new_trail_length;
2796 replace_trail->trail_id = new_trail_id;
2798 for (i = 0; i < new_trail_length; i++)
2800 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2801 element->peer = new_trail[i];
2803 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2804 replace_trail->trail_tail,
2807 /* FIXME: URGENT Are we adding the trail back to the list. */
2812 * Check if the new trail to reach to finger is unique or do we already have
2813 * such a trail present for finger.
2814 * @param existing_finger Finger identity
2815 * @param new_trail New trail to reach @a existing_finger
2816 * @param trail_length Total number of peers in new_trail.
2817 * @return #GNUNET_YES if the new trail is unique
2818 * #GNUNET_NO if same trail is already present.
2821 is_new_trail_unique (struct FingerInfo *existing_finger,
2822 const struct GNUNET_PeerIdentity *new_trail,
2823 unsigned int trail_length)
2825 struct Trail *current_trail;
2826 struct Trail_Element *trail_element;
2830 GNUNET_assert (existing_finger->trails_count > 0);
2832 /* Iterate over list of trails. */
2833 for (i = 0; i < existing_finger->trails_count; i++)
2835 current_trail = &(existing_finger->trail_list[i]);
2836 if(GNUNET_NO == current_trail->is_present)
2839 /* New trail and existing trail length are not same. */
2840 if (current_trail->trail_length != trail_length)
2845 trail_element = current_trail->trail_head;
2846 for (j = 0; j < current_trail->trail_length; j++)
2848 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2849 &trail_element->peer))
2853 trail_element = trail_element->next;
2860 * FIXME; In case of multiple trails, we may have a case where a trail from in
2861 * between has been removed, then we should try to find a free slot , not simply
2862 * add a trail at then end of the list.
2863 * Add a new trail at a free slot in trail array of existing finger.
2864 * @param existing_finger Finger
2865 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2866 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2867 * @param new_finger_trail_id Unique identifier of the trail.
2870 add_new_trail (struct FingerInfo *existing_finger,
2871 const struct GNUNET_PeerIdentity *new_trail,
2872 unsigned int new_trail_length,
2873 struct GNUNET_HashCode new_trail_id)
2875 struct FriendInfo *friend;
2876 struct Trail *trail;
2880 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2884 for (i = 0; i < existing_finger->trails_count; i++)
2886 if (GNUNET_NO == existing_finger->trail_list[i].is_present)
2893 if (-1 == free_slot)
2896 trail = &existing_finger->trail_list[free_slot];
2897 GNUNET_assert (GNUNET_NO == trail->is_present);
2898 trail->trail_id = new_trail_id;
2899 trail->trail_length = new_trail_length;
2900 existing_finger->trails_count++;
2901 trail->is_present = GNUNET_YES;
2902 if (0 == new_trail_length)
2904 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2905 &existing_finger->finger_identity);
2909 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2913 friend->trails_count++;
2914 for (i = 0; i < new_trail_length; i++)
2916 struct Trail_Element *element;
2918 element = GNUNET_new (struct Trail_Element);
2919 element->peer = new_trail[i];
2920 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2925 existing_finger->trail_list[free_slot].trail_head = trail->trail_head;
2926 existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail;
2927 existing_finger->trail_list[free_slot].trail_length = new_trail_length;
2928 existing_finger->trail_list[free_slot].trail_id = new_trail_id;
2929 existing_finger->trail_list[free_slot].is_present = GNUNET_YES;
2935 * FIXME; In case of multiple trails, we may have a case where a trail from in
2936 * between has been removed, then we should try to find a free slot , not simply
2937 * add a trail at then end of the list.
2938 * Add a new trail at a free slot in trail array of existing finger.
2939 * @param existing_finger Finger
2940 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2941 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2942 * @param new_finger_trail_id Unique identifier of the trail.
2945 add_new_trail (struct FingerInfo *existing_finger,
2946 const struct GNUNET_PeerIdentity *new_trail,
2947 unsigned int new_trail_length,
2948 struct GNUNET_HashCode new_trail_id)
2950 struct Trail *trail;
2951 struct FriendInfo *first_friend;
2955 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2959 index = existing_finger->trails_count;
2960 trail = &existing_finger->trail_list[index];
2961 GNUNET_assert (GNUNET_NO == trail->is_present);
2962 trail->trail_id = new_trail_id;
2963 trail->trail_length = new_trail_length;
2964 existing_finger->trails_count++;
2965 trail->is_present = GNUNET_YES;
2967 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2968 &existing_finger->finger_identity)));
2969 /* If finger is a friend then we never call this function. */
2970 GNUNET_assert (new_trail_length > 0);
2972 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2974 first_friend->trails_count++;
2976 for (i = 0; i < new_trail_length; i++)
2978 struct Trail_Element *element;
2980 element = GNUNET_new (struct Trail_Element);
2981 element->peer = new_trail[i];
2982 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2986 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2987 existing_finger->trail_list[index].trail_head = trail->trail_head;
2988 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2989 existing_finger->trail_list[index].trail_length = new_trail_length;
2990 existing_finger->trail_list[index].trail_id = new_trail_id;
2991 existing_finger->trail_list[index].is_present = GNUNET_YES;
2996 * Get the next hop to send trail teardown message from routing table and
2997 * then delete the entry from routing table. Send trail teardown message for a
2998 * specific trail of a finger.
2999 * @param finger Finger whose trail is to be removed.
3000 * @param trail List of peers in trail from me to a finger, NOT including
3004 send_trail_teardown (struct FingerInfo *finger,
3005 struct Trail *trail)
3007 struct FriendInfo *friend;
3008 struct GNUNET_PeerIdentity *next_hop;
3010 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
3011 GDS_ROUTING_SRC_TO_DEST);
3012 if (NULL == next_hop)
3014 // DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d",
3015 // GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length);
3018 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3021 GNUNET_assert(GNUNET_YES == trail->is_present);
3022 if (trail->trail_length > 0)
3024 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3025 &trail->trail_head->peer);
3029 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3030 &finger->finger_identity);
3035 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
3036 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
3039 if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)
3040 && (0 == trail->trail_length))
3042 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
3043 __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length);
3046 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
3047 friend->trails_count--;
3048 GDS_NEIGHBOURS_send_trail_teardown (&trail->trail_id,
3049 GDS_ROUTING_SRC_TO_DEST,
3055 * Send trail teardown message across all the trails to reach to finger.
3056 * @param finger Finger whose all the trail should be freed.
3059 send_all_finger_trails_teardown (struct FingerInfo *finger)
3063 for (i = 0; i < finger->trails_count; i++)
3065 struct Trail *trail;
3067 trail = &finger->trail_list[i];
3068 if (GNUNET_YES == trail->is_present)
3070 send_trail_teardown (finger, trail);
3071 trail->is_present = GNUNET_NO;
3078 * Free a specific trail
3079 * @param trail List of peers to be freed.
3082 free_trail (struct Trail *trail)
3084 struct Trail_Element *trail_element;
3086 while (NULL != (trail_element = trail->trail_head))
3088 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
3091 GNUNET_free_non_null (trail_element);
3093 trail->trail_head = NULL;
3094 trail->trail_tail = NULL;
3099 * Free finger and its trail.
3100 * @param finger Finger to be freed.
3101 * @param finger_table_index Index at which finger is stored.
3104 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
3106 struct Trail *trail;
3108 for (i = 0; i < finger->trails_count; i++)
3110 trail = &finger->trail_list[i];
3111 if (GNUNET_NO == trail->is_present)
3114 if (trail->trail_length > 0)
3116 trail->is_present = GNUNET_NO;
3119 finger->is_present = GNUNET_NO;
3120 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
3125 * Add a new entry in finger table at finger_table_index.
3126 * In case I am my own finger, then we don't have a trail. In case of a friend,
3127 * we have a trail with unique id and '0' trail length.
3128 * In case a finger is a friend, then increment the trails count of the friend.
3129 * @param finger_identity Peer Identity of new finger
3130 * @param finger_trail Trail to reach from me to finger (excluding both end points).
3131 * @param finger_trail_length Total number of peers in @a finger_trail.
3132 * @param trail_id Unique identifier of the trail.
3133 * @param finger_table_index Index in finger table.
3136 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
3137 const struct GNUNET_PeerIdentity *finger_trail,
3138 unsigned int finger_trail_length,
3139 struct GNUNET_HashCode trail_id,
3140 unsigned int finger_table_index)
3142 struct FingerInfo *new_entry;
3143 struct FriendInfo *first_trail_hop;
3144 struct Trail *trail;
3147 new_entry = GNUNET_new (struct FingerInfo);
3148 new_entry->finger_identity = finger_identity;
3149 new_entry->finger_table_index = finger_table_index;
3150 new_entry->is_present = GNUNET_YES;
3152 /* If the new entry is my own identity. */
3153 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3156 new_entry->trails_count = 0;
3157 finger_table[finger_table_index] = *new_entry;
3158 GNUNET_free (new_entry);
3162 /* Finger is a friend. */
3163 if (0 == finger_trail_length)
3165 new_entry->trail_list[0].trail_id = trail_id;
3166 new_entry->trails_count = 1;
3167 new_entry->trail_list[0].is_present = GNUNET_YES;
3168 new_entry->trail_list[0].trail_length = 0;
3169 new_entry->trail_list[0].trail_head = NULL;
3170 new_entry->trail_list[0].trail_tail = NULL;
3171 finger_table[finger_table_index] = *new_entry;
3172 GNUNET_assert (NULL !=
3174 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3175 &finger_identity)));
3177 first_trail_hop->trails_count++;
3178 GNUNET_free (new_entry);
3182 GNUNET_assert (NULL !=
3184 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3185 &finger_trail[0])));
3186 new_entry->trails_count = 1;
3187 first_trail_hop->trails_count++;
3188 /* Copy the finger trail into trail. */
3189 trail = &new_entry->trail_list[0];
3190 for(i = 0; i < finger_trail_length; i++)
3192 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3194 element->next = NULL;
3195 element->prev = NULL;
3196 element->peer = finger_trail[i];
3197 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3202 /* Add trail to trail list. */
3203 trail->trail_length = finger_trail_length;
3204 trail->trail_id = trail_id;
3205 trail->is_present = GNUNET_YES;
3206 finger_table[finger_table_index] = *new_entry;
3207 GNUNET_free (new_entry);
3212 * Periodic task to verify current successor. There can be multiple trails to reach
3213 * to successor, choose the shortest one and send verify successor message
3214 * across that trail.
3215 * @param cls closure for this task
3216 * @param tc the context under which the task is running
3219 send_verify_successor_message (void *cls,
3220 const struct GNUNET_SCHEDULER_TaskContext *tc)
3222 struct FriendInfo *target_friend;
3223 struct GNUNET_HashCode trail_id;
3224 struct Trail *trail;
3225 struct Trail_Element *element;
3226 unsigned int trail_length;
3228 struct FingerInfo *successor;
3230 successor = &finger_table[0];
3232 /* This task will be scheduled when the result for Verify Successor is received. */
3233 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
3235 /* When verify successor is being called for first time *for current context*
3236 * cls will be NULL. If send_verify_successor_retry_task is not NO_TASK, we
3237 * must cancel the retry task scheduled for verify_successor of previous
3242 /* FIXME: Here we are scheduling a new verify successor task, as we
3243 got a new successor. But a send verify successor task may be in progress.
3244 1. We need to be sure that this is indeed a new successor. As this function
3245 is called even if we add a new trail to reach t old successor.
3246 2. Assuming the new successor is different, then verify successor message
3247 * to old successor may be following stages.
3248 * --> Waiting for verify successor result. Don't wait anymore. there is
3249 * no trail to reach from old successor to me, hence, routing
3251 * --> Waiting for notify confirmation. again don't wait for it. notify
3252 * confirmation will not succeded.
3254 if (send_verify_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
3256 /* FIXME: Are we scheduling retry task as soon as we send verify message.
3257 If yes then here before making this task, first check if the message
3258 is for the same peer again. */
3259 struct VerifySuccessorContext *old_ctx =
3260 GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
3261 /* old_ctx must not be NULL, as the retry task had been scheduled */
3262 GNUNET_assert(NULL != old_ctx);
3263 GNUNET_free(old_ctx);
3264 /* FIXME: Why don't we reset the task to NO_TASK here? */
3267 struct VerifySuccessorContext *ctx;
3268 ctx = GNUNET_new(struct VerifySuccessorContext);
3270 ctx->num_retries_scheduled++;
3271 send_verify_successor_retry_task =
3272 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3273 &send_verify_successor_message,
3278 /* This is a retry attempt for verify_successor for a previous context */
3279 struct VerifySuccessorContext *ctx;
3282 ctx->num_retries_scheduled++;
3283 send_verify_successor_retry_task =
3284 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3285 &send_verify_successor_message,
3289 /* Among all the trails to reach to successor, select first one which is present.*/
3290 for (i = 0; i < successor->trails_count; i++)
3292 trail = &successor->trail_list[i];
3293 if(GNUNET_YES == trail->is_present)
3297 /* No valid trail found to reach to successor. */
3298 if (i == successor->trails_count)
3301 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3302 &successor->finger_identity));
3303 /* Trail stored at this index. */
3304 GNUNET_assert (GNUNET_YES == trail->is_present);
3305 trail_id = trail->trail_id;
3306 if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST))
3308 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
3309 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__);
3313 trail_length = trail->trail_length;
3314 if (trail_length > 0)
3316 /* Copy the trail into peer list. */
3317 struct GNUNET_PeerIdentity peer_list[trail_length];
3318 element = trail->trail_head;
3319 for(i = 0; i < trail_length; i++)
3321 peer_list[i] = element->peer;
3322 element = element->next;
3324 GNUNET_assert (NULL != (target_friend =
3325 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3327 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3328 successor->finger_identity,
3329 trail_id, peer_list, trail_length,
3334 GNUNET_assert (NULL != (target_friend =
3335 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3336 &successor->finger_identity)));
3337 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3338 successor->finger_identity,
3346 * FIXME: should this be a periodic task, incrementing the search finger index?
3347 * Update the current search finger index.
3348 * @a finger_identity
3349 * @a finger_table_index
3352 update_current_search_finger_index (unsigned int finger_table_index)
3354 struct FingerInfo *successor;
3356 /* FIXME correct this: only move current index periodically */
3357 if (finger_table_index != current_search_finger_index)
3360 successor = &finger_table[0];
3361 GNUNET_assert (GNUNET_YES == successor->is_present);
3363 /* We were looking for immediate successor. */
3364 if (0 == current_search_finger_index)
3366 current_search_finger_index = PREDECESSOR_FINGER_ID;
3367 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &successor->finger_identity))
3369 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3371 send_verify_successor_task =
3372 GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3378 current_search_finger_index = current_search_finger_index - 1;
3384 * Get the least significant bit set in val.
3387 * @return Position of first bit set, 65 in case of error.
3390 find_set_bit (uint64_t val)
3410 return 65; /* Some other bit was set to 1 as well. */
3417 * Calculate finger_table_index from initial 64 bit finger identity value that
3418 * we send in trail setup message.
3419 * @param ultimate_destination_finger_value Value that we calculated from our
3420 * identity and finger_table_index.
3421 * @param is_predecessor Is the entry for predecessor or not?
3422 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3423 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3426 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3427 unsigned int is_predecessor)
3431 unsigned int finger_table_index;
3433 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3434 my_id64 = GNUNET_ntohll (my_id64);
3436 /* Is this a predecessor finger? */
3437 if (1 == is_predecessor)
3439 diff = my_id64 - ultimate_destination_finger_value;
3441 finger_table_index = PREDECESSOR_FINGER_ID;
3443 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3448 diff = ultimate_destination_finger_value - my_id64;
3449 finger_table_index = find_set_bit (diff);
3451 return finger_table_index;
3456 * Remove finger and its associated data structures from finger table.
3457 * @param existing_finger Finger to be removed which is in finger table.
3458 * @param finger_table_index Index in finger table where @a existing_finger
3462 remove_existing_finger (struct FingerInfo *existing_finger,
3463 unsigned int finger_table_index)
3465 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3467 /* If I am my own finger, then we have no trails. */
3468 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3471 existing_finger->is_present = GNUNET_NO;
3472 memset ((void *)&finger_table[finger_table_index], 0,
3473 sizeof (finger_table[finger_table_index]));
3477 /* For all other fingers, send trail teardown across all the trails to reach
3478 finger, and free the finger. */
3479 send_all_finger_trails_teardown (existing_finger);
3480 free_finger (existing_finger, finger_table_index);
3485 * Check if there is already an entry in finger_table at finger_table_index.
3486 * We get the finger_table_index from 64bit finger value we got from the network.
3487 * -- If yes, then select the closest finger.
3488 * -- If new and existing finger are same, then check if you can store more
3490 * -- If yes then add trail, else keep the best trails to reach to the
3492 * -- If the new finger is closest, remove the existing entry, send trail
3493 * teardown message across all the trails to reach the existing entry.
3494 * Add the new finger.
3495 * -- If new and existing finger are different, and existing finger is closest
3497 * -- Update current_search_finger_index.
3498 * @param finger_identity Peer Identity of new finger
3499 * @param finger_trail Trail to reach the new finger
3500 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3501 * @param is_predecessor Is this entry for predecessor in finger_table?
3502 * @param finger_value 64 bit value of finger identity that we got from network.
3503 * @param finger_trail_id Unique identifier of @finger_trail.
3506 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3507 const struct GNUNET_PeerIdentity *finger_trail,
3508 unsigned int finger_trail_length,
3509 unsigned int is_predecessor,
3510 uint64_t finger_value,
3511 struct GNUNET_HashCode finger_trail_id)
3513 struct FingerInfo *existing_finger;
3514 struct GNUNET_PeerIdentity closest_peer;
3515 struct FingerInfo *successor;
3516 unsigned int finger_table_index;
3518 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3519 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3521 /* Invalid finger_table_index. */
3522 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3524 GNUNET_break_op (0);
3528 /* Check if new entry is same as successor. */
3529 if ((0 != finger_table_index) &&
3530 (PREDECESSOR_FINGER_ID != finger_table_index))
3532 successor = &finger_table[0];
3533 if (GNUNET_NO == successor->is_present)
3535 GNUNET_break (0); //ASSERTION FAILS HERE. FIXME
3538 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3539 &successor->finger_identity))
3541 if (0 == fingers_round_count)
3543 find_finger_trail_task_next_send_time =
3544 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3547 fingers_round_count--;
3548 current_search_finger_index = 0;
3549 GNUNET_STATISTICS_update (GDS_stats,
3551 ("# FINGERS_COUNT"), (int64_t) total_fingers_found,
3553 total_fingers_found = 0;
3557 struct FingerInfo prev_finger;
3558 prev_finger = finger_table[finger_table_index - 1];
3559 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3560 &prev_finger.finger_identity))
3562 current_search_finger_index--;
3567 total_fingers_found++;
3568 existing_finger = &finger_table[finger_table_index];
3570 /* No entry present in finger_table for given finger map index. */
3571 if (GNUNET_NO == existing_finger->is_present)
3573 /* Shorten the trail if possible. */
3574 add_new_finger (finger_identity, finger_trail,
3575 finger_trail_length,
3576 finger_trail_id, finger_table_index);
3577 update_current_search_finger_index (finger_table_index);
3581 /* If existing entry and finger identity are not same. */
3582 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3585 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3590 /* If the new finger is the closest peer. */
3591 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer))
3593 remove_existing_finger (existing_finger, finger_table_index);
3594 add_new_finger (finger_identity, finger_trail, finger_trail_length,
3595 finger_trail_id, finger_table_index);
3599 /* Existing finger is the closest one. We need to send trail teardown
3600 across the trail setup in routing table of all the peers. */
3601 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3603 if (finger_trail_length > 0)
3604 GDS_NEIGHBOURS_send_trail_teardown (&finger_trail_id,
3605 GDS_ROUTING_SRC_TO_DEST,
3608 GDS_NEIGHBOURS_send_trail_teardown (&finger_trail_id,
3609 GDS_ROUTING_SRC_TO_DEST,
3616 /* If both new and existing entry are same as my_identity, then do nothing. */
3617 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3623 /* If there is space to store more trails. */
3624 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3625 add_new_trail (existing_finger, finger_trail,
3626 finger_trail_length, finger_trail_id);
3628 select_and_replace_trail (existing_finger, finger_trail,
3629 finger_trail_length, finger_trail_id);
3631 update_current_search_finger_index (finger_table_index);
3637 * Core handler for P2P put messages.
3638 * @param cls closure
3639 * @param peer sender of the request
3640 * @param message message
3641 * @return #GNUNET_OK to keep the connection open,
3642 * #GNUNET_SYSERR to close it (signal serious error)
3645 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3646 const struct GNUNET_MessageHeader *message)
3648 struct PeerPutMessage *put;
3649 struct GNUNET_PeerIdentity *put_path;
3650 struct GNUNET_PeerIdentity current_best_known_dest;
3651 struct GNUNET_PeerIdentity best_known_dest;
3652 struct GNUNET_HashCode received_intermediate_trail_id;
3653 struct GNUNET_HashCode intermediate_trail_id;
3654 struct GNUNET_PeerIdentity *next_hop;
3655 struct GNUNET_PeerIdentity *next_routing_hop;
3656 enum GNUNET_DHT_RouteOption options;
3657 struct GNUNET_HashCode test_key;
3662 size_t payload_size;
3665 msize = ntohs (message->size);
3666 if (msize < sizeof (struct PeerPutMessage))
3668 GNUNET_break_op (0);
3672 put = (struct PeerPutMessage *) message;
3673 putlen = ntohl (put->put_path_length);
3675 sizeof (struct PeerPutMessage) +
3676 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3678 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3680 GNUNET_break_op (0);
3683 #if ENABLE_MALICIOUS
3684 if(1 == act_malicious)
3686 DEBUG("\n I AM MALICIOUS PUT_REQUEST_DROPPED for key = %ss",GNUNET_h2s(&put->key));
3690 GNUNET_STATISTICS_update (GDS_stats,
3692 ("# Bytes received from other peers"), (int64_t) msize,
3695 current_best_known_dest = put->best_known_destination;
3696 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3697 payload = &put_path[putlen];
3698 options = ntohl (put->options);
3699 received_intermediate_trail_id = put->intermediate_trail_id;
3700 hop_count = ntohl(put->hop_count);
3701 payload_size = msize - (sizeof (struct PeerPutMessage) +
3702 putlen * sizeof (struct GNUNET_PeerIdentity));
3704 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3705 payload, payload_size, &test_key))
3708 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3710 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3711 GNUNET_break_op (0);
3712 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3713 "PUT with key `%s' for block with key %s\n",
3714 put_s, GNUNET_h2s_full (&test_key));
3715 GNUNET_free (put_s);
3720 GNUNET_break_op (0);
3723 /* cannot verify, good luck */
3727 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3729 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3730 ntohl (put->block_type),
3732 NULL, 0, /* bloom filer */
3733 NULL, 0, /* xquery */
3734 payload, payload_size))
3736 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3737 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3740 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3741 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3742 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3743 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3744 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3745 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3747 GNUNET_break_op (0);
3752 /* Check if you are already a part of put path. */
3754 for (i = 0; i < putlen; i++)
3756 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i]))
3763 /* Add yourself to the list. */
3764 struct GNUNET_PeerIdentity pp[putlen + 1];
3765 //if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3768 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3769 pp[putlen] = my_identity;
3775 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3776 struct Closest_Peer successor;
3777 key_value = GNUNET_ntohll (key_value);
3778 successor = find_local_best_known_next_hop (key_value,
3779 GDS_FINGER_TYPE_NON_PREDECESSOR);
3780 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3781 *next_hop = successor.next_hop;
3782 intermediate_trail_id = successor.trail_id;
3783 best_known_dest = successor.best_known_destination;
3785 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3787 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3788 GDS_ROUTING_SRC_TO_DEST);
3789 if (NULL != next_routing_hop)
3791 next_hop = next_routing_hop;
3792 intermediate_trail_id = received_intermediate_trail_id;
3793 best_known_dest = current_best_known_dest;
3797 GDS_CLIENTS_process_put (options,
3798 ntohl (put->block_type),
3800 ntohl (put->desired_replication_level),
3802 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3807 /* I am the final destination */
3808 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3810 DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",GNUNET_h2s(&put->key));
3811 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3812 &(put->key),putlen, pp, ntohl (put->block_type),
3813 payload_size, payload);
3817 #if ENABLE_MALICIOUS
3818 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
3819 &successor.next_hop))
3821 struct FingerInfo *next_hop_finger;
3824 next_hop_finger = &finger_table[successor.finger_table_index];
3825 for (i = 0; i < next_hop_finger->trails_count; i++)
3827 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
3829 if(0 == next_hop_finger->trail_list[i].trail_length)
3831 GDS_NEIGHBOURS_send_put (&put->key,
3832 ntohl (put->block_type),ntohl (put->options),
3833 ntohl (put->desired_replication_level),
3834 best_known_dest, intermediate_trail_id, next_hop,
3835 hop_count, putlen, pp,
3836 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3837 payload, payload_size);
3840 next_hop = &next_hop_finger->trail_list[i].trail_head->peer;
3841 GDS_NEIGHBOURS_send_put (&put->key,
3842 ntohl (put->block_type),ntohl (put->options),
3843 ntohl (put->desired_replication_level),
3845 next_hop_finger->trail_list[i].trail_id,
3846 next_hop, hop_count, putlen, pp,
3847 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3848 payload, payload_size);
3854 GDS_NEIGHBOURS_send_put (&put->key,
3855 ntohl (put->block_type),ntohl (put->options),
3856 ntohl (put->desired_replication_level),
3857 best_known_dest, intermediate_trail_id, next_hop,
3858 hop_count, putlen, pp,
3859 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3860 payload, payload_size);
3867 * FIXME: Check for loop in the request. If you already are part of get path,
3868 * then you need to reset the get path length.
3869 * Core handler for p2p get requests.
3871 * @param cls closure
3872 * @param peer sender of the request
3873 * @param message message
3874 * @return #GNUNET_OK to keep the connection open,
3875 * #GNUNET_SYSERR to close it (signal serious error)
3878 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3879 const struct GNUNET_MessageHeader *message)
3881 const struct PeerGetMessage *get;
3882 const struct GNUNET_PeerIdentity *get_path;
3883 struct GNUNET_PeerIdentity best_known_dest;
3884 struct GNUNET_PeerIdentity current_best_known_dest;
3885 struct GNUNET_HashCode intermediate_trail_id;
3886 struct GNUNET_HashCode received_intermediate_trail_id;
3887 struct Closest_Peer successor;
3888 struct GNUNET_PeerIdentity *next_hop;
3889 struct GNUNET_PeerIdentity *next_routing_hop;
3890 uint32_t get_length;
3895 msize = ntohs (message->size);
3896 if (msize < sizeof (struct PeerGetMessage))
3898 GNUNET_break_op (0);
3902 get = (const struct PeerGetMessage *)message;
3903 get_length = ntohl (get->get_path_length);
3905 sizeof (struct PeerGetMessage) +
3906 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3908 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3910 GNUNET_break_op (0);
3914 #if ENABLE_MALICIOUS
3915 if(1 == act_malicious)
3917 DEBUG("I am malicious,GET_REQUEST_DROPPED for key = %s. \n",GNUNET_h2s(&get->key));
3921 current_best_known_dest = get->best_known_destination;
3922 received_intermediate_trail_id = get->intermediate_trail_id;
3923 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3924 hop_count = get->hop_count;
3928 GNUNET_STATISTICS_update (GDS_stats,
3930 ("# Bytes received from other peers"), msize,
3933 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3934 key_value = GNUNET_ntohll (key_value);
3936 /* Check if you are already a part of get path. */
3938 for (i = 0; i < get_length; i++)
3940 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &get_path[i]))
3947 /* Add yourself in the get path. */
3948 struct GNUNET_PeerIdentity gp[get_length + 1];
3949 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3950 gp[get_length] = my_identity;
3951 get_length = get_length + 1;
3952 GDS_CLIENTS_process_get (get->options, get->block_type, hop_count,
3953 get->desired_replication_level, get->get_path_length,
3957 successor = find_local_best_known_next_hop (key_value,
3958 GDS_FINGER_TYPE_NON_PREDECESSOR);
3959 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3960 *next_hop = successor.next_hop;
3961 best_known_dest = successor.best_known_destination;
3962 intermediate_trail_id = successor.trail_id;
3963 /* I am not the final destination. I am part of trail to reach final dest. */
3964 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity)))
3966 next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id,
3967 GDS_ROUTING_SRC_TO_DEST);
3968 if (NULL != next_routing_hop)
3970 next_hop = next_routing_hop;
3971 best_known_dest = current_best_known_dest;
3972 intermediate_trail_id = received_intermediate_trail_id;
3976 /* I am the final destination. */
3977 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3979 if (1 == get_length)
3981 DEBUG("\n GET_REQUEST DONE for key = %s",GNUNET_h2s(&get->key));
3982 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0,
3983 NULL, 0, 1, &my_identity, NULL,&my_identity);
3987 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3988 get_length, gp, &gp[get_length - 2],
3995 #if ENABLE_MALICIOUS
3996 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
3997 &successor.next_hop))
3999 struct FingerInfo *next_hop_finger;
4002 next_hop_finger = &finger_table[successor.finger_table_index];
4003 for (i = 0; i < next_hop_finger->trails_count; i++)
4005 if(0 == next_hop_finger->trail_list[i].trail_length)
4007 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
4008 get->desired_replication_level, best_known_dest,
4009 intermediate_trail_id, next_hop, hop_count,
4013 if (GNUNET_YES == next_hop_finger->trail_list[i].is_present)
4015 next_hop = &next_hop_finger->trail_list[i].trail_head->peer;
4016 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
4017 get->desired_replication_level, best_known_dest,
4018 next_hop_finger->trail_list[i].trail_id,
4019 next_hop, hop_count,
4026 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
4027 get->desired_replication_level, best_known_dest,
4028 intermediate_trail_id, next_hop, hop_count,
4036 * Core handler for get result
4037 * @param cls closure
4038 * @param peer sender of the request
4039 * @param message message
4040 * @return #GNUNET_OK to keep the connection open,
4041 * #GNUNET_SYSERR to close it (signal serious error)
4044 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
4045 const struct GNUNET_MessageHeader *message)
4047 const struct PeerGetResultMessage *get_result;
4048 const struct GNUNET_PeerIdentity *get_path;
4049 const struct GNUNET_PeerIdentity *put_path;
4050 const void *payload;
4051 size_t payload_size;
4053 unsigned int getlen;
4054 unsigned int putlen;
4055 int current_path_index;
4057 msize = ntohs (message->size);
4058 if (msize < sizeof (struct PeerGetResultMessage))
4060 GNUNET_break_op (0);
4064 get_result = (const struct PeerGetResultMessage *)message;
4065 getlen = ntohl (get_result->get_path_length);
4066 putlen = ntohl (get_result->put_path_length);
4069 sizeof (struct PeerGetResultMessage) +
4070 getlen * sizeof (struct GNUNET_PeerIdentity) +
4071 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
4073 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
4075 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
4077 GNUNET_break_op (0);
4080 DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize);
4081 GNUNET_STATISTICS_update (GDS_stats,
4083 ("# Bytes received from other peers"), msize,
4086 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
4087 get_path = &put_path[putlen];
4088 payload = (const void *) &get_path[getlen];
4089 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
4090 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
4092 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
4094 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
4095 getlen, get_path, putlen,
4096 put_path, get_result->type, payload_size, payload);
4101 current_path_index = search_my_index (get_path, getlen);
4102 if (-1 == current_path_index )
4104 DEBUG ("No entry found in get path.\n");
4106 return GNUNET_SYSERR;
4108 if((getlen + 1) == current_path_index)
4110 DEBUG("Present twice in get path. Not allowed. \n");
4112 return GNUNET_SYSERR;
4114 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
4115 &get_path[current_path_index - 1],
4116 &(get_result->querying_peer), putlen, put_path,
4117 getlen, get_path, get_result->expiration_time,
4118 payload, payload_size);
4121 return GNUNET_SYSERR;
4126 * Find the next hop to pass trail setup message. First find the local best known
4127 * hop from your own identity, friends and finger. If you were part of trail,
4128 * then get the next hop from routing table. Compare next_hop from routing table
4129 * and local best known hop, and return the closest one to final_dest_finger_val
4130 * @param final_dest_finger_val 64 bit value of finger identity
4131 * @param intermediate_trail_id If you are part of trail to reach to some other
4132 * finger, then it is the trail id to reach to
4133 * that finger, else set to 0.
4134 * @param is_predecessor Are we looking for closest successor or predecessor.
4135 * @param source Source of trail setup message.
4136 * @param current_dest In case you are part of trail, then finger to which
4137 * we should forward the message. Else my own identity
4138 * @return Closest Peer for @a final_dest_finger_val
4140 static struct Closest_Peer
4141 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
4142 struct GNUNET_HashCode intermediate_trail_id,
4143 unsigned int is_predecessor,
4144 struct GNUNET_PeerIdentity source,
4145 struct GNUNET_PeerIdentity *current_dest)
4147 struct Closest_Peer peer;
4149 peer = find_local_best_known_next_hop (final_dest_finger_val, is_predecessor);
4151 /* Am I just a part of a trail towards a finger (current_destination)? */
4152 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
4153 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
4156 struct GNUNET_PeerIdentity closest_peer;
4158 /* Select best successor among one found locally and current_destination
4159 * that we got from network.*/
4160 closest_peer = select_closest_peer (&peer.best_known_destination,
4162 final_dest_finger_val,
4165 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
4166 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer))
4168 struct GNUNET_PeerIdentity *next_hop;
4170 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
4171 GDS_ROUTING_SRC_TO_DEST);
4172 /* next_hop NULL is a valid case. This intermediate trail id is set by
4173 some other finger, and while this trail setup is in progress, that other
4174 peer might have found a better trail ,and send trail teardown message
4175 across the network. In case we got the trail teardown message first,
4176 then next_hop will be NULL. A possible solution could be to keep track
4177 * of all removed trail id, and be sure that there is no other reason . */
4178 if(NULL != next_hop)
4180 peer.next_hop = *next_hop;
4181 peer.best_known_destination = *current_dest;
4182 peer.trail_id = intermediate_trail_id;
4191 * Core handle for PeerTrailSetupMessage.
4192 * @param cls closure
4193 * @param message message
4194 * @param peer peer identity this notification is about
4195 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4198 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
4199 const struct GNUNET_MessageHeader *message)
4201 const struct PeerTrailSetupMessage *trail_setup;
4202 const struct GNUNET_PeerIdentity *trail_peer_list;
4203 struct GNUNET_PeerIdentity current_dest;
4204 struct FriendInfo *target_friend;
4205 struct GNUNET_PeerIdentity source;
4206 struct GNUNET_HashCode intermediate_trail_id;
4207 struct GNUNET_HashCode trail_id;
4208 unsigned int is_predecessor;
4209 uint32_t trail_length;
4210 uint64_t final_dest_finger_val;
4214 msize = ntohs (message->size);
4215 if (msize < sizeof (struct PeerTrailSetupMessage))
4217 GNUNET_break_op (0);
4218 return GNUNET_SYSERR;
4221 trail_setup = (const struct PeerTrailSetupMessage *) message;
4222 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4223 sizeof (struct GNUNET_PeerIdentity) != 0)
4225 GNUNET_break_op (0);
4228 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4229 sizeof (struct GNUNET_PeerIdentity);
4231 GNUNET_STATISTICS_update (GDS_stats,
4233 ("# Bytes received from other peers"), msize,
4236 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
4237 current_dest = trail_setup->best_known_destination;
4238 trail_id = trail_setup->trail_id;
4239 final_dest_finger_val =
4240 GNUNET_ntohll (trail_setup->final_destination_finger_value);
4241 source = trail_setup->source_peer;
4242 is_predecessor = ntohl (trail_setup->is_predecessor);
4243 intermediate_trail_id = trail_setup->intermediate_trail_id;
4245 /* Did the friend insert its ID in the trail list? */
4246 if (trail_length > 0 &&
4247 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity)))
4249 GNUNET_break_op (0);
4250 return GNUNET_SYSERR;
4253 /* If I was the source and got the message back, then set trail length to 0.*/
4254 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4259 /* Check if you are present in the trail seen so far? */
4260 for (i = 0; i < trail_length ; i++)
4262 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
4264 /* We will add ourself later in code, if NOT destination. */
4270 /* Is my routing table full? */
4271 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
4273 if (trail_length > 0)
4275 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4276 &trail_peer_list[trail_length - 1]);
4279 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4281 if(NULL == target_friend)
4283 DEBUG ("\n friend not found");
4287 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
4288 my_identity, is_predecessor,
4289 trail_peer_list, trail_length,
4290 trail_id, target_friend,
4291 CONGESTION_TIMEOUT);
4295 /* Get the next hop to forward the trail setup request. */
4296 struct Closest_Peer next_peer =
4297 get_local_best_known_next_hop (final_dest_finger_val,
4298 intermediate_trail_id,
4303 /* Am I the final destination? */
4304 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4307 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4309 finger_table_add (my_identity, NULL, 0, is_predecessor,
4310 final_dest_finger_val, trail_id);
4314 if (trail_length > 0)
4316 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4317 &trail_peer_list[trail_length-1]);
4320 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4321 if (NULL == target_friend)
4323 GNUNET_break_op (0);
4324 return GNUNET_SYSERR;
4326 GDS_ROUTING_add (trail_id, target_friend->id, my_identity);
4327 GDS_NEIGHBOURS_send_trail_setup_result (source,
4329 target_friend, trail_length,
4332 final_dest_finger_val,trail_id);
4334 else /* I'm not the final destination. */
4336 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4337 &next_peer.next_hop);
4338 if(NULL == target_friend)
4340 DEBUG ("\n target friend not found for peer = %s", GNUNET_i2s(&next_peer.next_hop));
4344 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4346 /* Add yourself to list of peers. */
4347 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4349 memcpy (peer_list, trail_peer_list,
4350 trail_length * sizeof (struct GNUNET_PeerIdentity));
4351 peer_list[trail_length] = my_identity;
4352 GDS_NEIGHBOURS_send_trail_setup (source,
4353 final_dest_finger_val,
4354 next_peer.best_known_destination,
4355 target_friend, trail_length + 1, peer_list,
4356 is_predecessor, trail_id,
4357 next_peer.trail_id);
4360 GDS_NEIGHBOURS_send_trail_setup (source,
4361 final_dest_finger_val,
4362 next_peer.best_known_destination,
4363 target_friend, 0, NULL,
4364 is_predecessor, trail_id,
4365 next_peer.trail_id);
4372 * Core handle for p2p trail setup result messages.
4374 * @param message message
4375 * @param peer sender of this message.
4376 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4379 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4380 const struct GNUNET_MessageHeader *message)
4382 const struct PeerTrailSetupResultMessage *trail_result;
4383 const struct GNUNET_PeerIdentity *trail_peer_list;
4384 struct GNUNET_PeerIdentity next_hop;
4385 struct FriendInfo *target_friend;
4386 struct GNUNET_PeerIdentity querying_peer;
4387 struct GNUNET_PeerIdentity finger_identity;
4388 uint32_t trail_length;
4389 uint64_t ulitmate_destination_finger_value;
4390 uint32_t is_predecessor;
4391 struct GNUNET_HashCode trail_id;
4395 msize = ntohs (message->size);
4396 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4398 GNUNET_break_op (0);
4402 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4403 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4404 sizeof (struct GNUNET_PeerIdentity) != 0)
4406 GNUNET_break_op (0);
4409 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4410 sizeof (struct GNUNET_PeerIdentity);
4412 GNUNET_STATISTICS_update (GDS_stats,
4414 ("# Bytes received from other peers"), msize,
4417 is_predecessor = ntohl (trail_result->is_predecessor);
4418 querying_peer = trail_result->querying_peer;
4419 finger_identity = trail_result->finger_identity;
4420 trail_id = trail_result->trail_id;
4421 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4422 ulitmate_destination_finger_value =
4423 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4425 /* Am I the one who initiated the query? */
4426 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4428 /* Check that you got the message from the correct peer. */
4429 if (trail_length > 0)
4431 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4436 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4439 GDS_ROUTING_add (trail_id, my_identity, *peer);
4440 finger_table_add (finger_identity, trail_peer_list, trail_length,
4441 is_predecessor, ulitmate_destination_finger_value, trail_id);
4445 /* Get my location in the trail. */
4446 my_index = search_my_index (trail_peer_list, trail_length);
4449 DEBUG ("Not found in trail\n");
4451 return GNUNET_SYSERR;
4454 if ((trail_length + 1) == my_index)
4456 DEBUG ("Found twice in trail.\n");
4458 return GNUNET_SYSERR;
4461 //TODO; Refactor code here and above to check if sender peer is correct
4464 if(trail_length > 1)
4465 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4468 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4470 next_hop = trail_result->querying_peer;
4474 if(my_index == trail_length - 1)
4477 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4482 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4484 next_hop = trail_peer_list[my_index - 1];
4487 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4488 if (NULL == target_friend)
4490 GNUNET_break_op (0);
4491 return GNUNET_SYSERR;
4493 GDS_ROUTING_add (trail_id, next_hop, *peer);
4494 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4495 target_friend, trail_length, trail_peer_list,
4497 ulitmate_destination_finger_value,
4505 * @param trail Trail to be inverted
4506 * @param trail_length Total number of peers in the trail.
4507 * @return Updated trail
4509 static struct GNUNET_PeerIdentity *
4510 invert_trail (const struct GNUNET_PeerIdentity *trail,
4511 unsigned int trail_length)
4515 struct GNUNET_PeerIdentity *inverted_trail;
4517 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4520 j = trail_length - 1;
4521 while (i < trail_length)
4523 inverted_trail[i] = trail[j];
4528 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4529 &inverted_trail[0]));
4530 return inverted_trail;
4535 * Return the shortest trail among all the trails to reach to finger from me.
4536 * @param finger Finger
4537 * @param shortest_trail_length[out] Trail length of shortest trail from me
4539 * @return Shortest trail.
4541 static struct GNUNET_PeerIdentity *
4542 get_shortest_trail (struct FingerInfo *finger,
4543 unsigned int *trail_length)
4545 struct Trail *trail;
4546 unsigned int flag = 0;
4547 unsigned int shortest_trail_index = 0;
4548 int shortest_trail_length = -1;
4549 struct Trail_Element *trail_element;
4550 struct GNUNET_PeerIdentity *trail_list;
4553 trail = GNUNET_new (struct Trail);
4555 /* Get the shortest trail to reach to current successor. */
4556 for (i = 0; i < finger->trails_count; i++)
4558 trail = &finger->trail_list[i];
4562 shortest_trail_index = i;
4563 shortest_trail_length = trail->trail_length;
4568 if (shortest_trail_length > trail->trail_length)
4570 shortest_trail_index = i;
4571 shortest_trail_length = trail->trail_length;
4576 /* Copy the shortest trail and return. */
4577 trail = &finger->trail_list[shortest_trail_index];
4578 trail_element = trail->trail_head;
4580 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4581 shortest_trail_length);
4583 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4585 trail_list[i] = trail_element->peer;
4588 GNUNET_assert(shortest_trail_length != -1);
4590 *trail_length = shortest_trail_length;
4596 * Check if trail_1 and trail_2 have any common element. If yes then join
4597 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4598 * @param trail_1 Trail from source to me, NOT including endpoints.
4599 * @param trail_1_len Total number of peers @a trail_1
4600 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4601 * @param trail_2_len Total number of peers @a trail_2
4602 * @param joined_trail_len Total number of peers in combined trail of trail_1
4604 * @return Joined trail.
4606 static struct GNUNET_PeerIdentity *
4607 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4608 unsigned int trail_1_len,
4609 struct GNUNET_PeerIdentity *trail_2,
4610 unsigned int trail_2_len,
4611 unsigned int *joined_trail_len)
4613 struct GNUNET_PeerIdentity *joined_trail;
4618 for (i = 0; i < trail_1_len; i++)
4620 for (j = 0; j < trail_2_len; j++)
4622 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4625 *joined_trail_len = i + (trail_2_len - j);
4626 joined_trail = GNUNET_malloc (*joined_trail_len *
4627 sizeof(struct GNUNET_PeerIdentity));
4630 /* Copy all the elements from 0 to i into joined_trail. */
4631 for(k = 0; k < ( i+1); k++)
4633 joined_trail[k] = trail_1[k];
4636 /* Increment j as entry stored is same as entry stored at i*/
4639 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4640 while(k <= (*joined_trail_len - 1))
4642 joined_trail[k] = trail_2[j];
4647 return joined_trail;
4651 /* Here you should join the trails. */
4652 *joined_trail_len = trail_1_len + trail_2_len + 1;
4653 joined_trail = GNUNET_malloc (*joined_trail_len *
4654 sizeof(struct GNUNET_PeerIdentity));
4657 for(i = 0; i < trail_1_len;i++)
4659 joined_trail[i] = trail_1[i];
4662 joined_trail[i] = my_identity;
4665 for (j = 0; i < *joined_trail_len; i++,j++)
4667 joined_trail[i] = trail_2[j];
4670 return joined_trail;
4675 * Return the trail from source to my current predecessor. Check if source
4676 * is already part of the this trail, if yes then return the shorten trail.
4677 * @param current_trail Trail from source to me, NOT including the endpoints.
4678 * @param current_trail_length Number of peers in @a current_trail.
4679 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4680 * source to my predecessor, NOT including
4682 * @return Trail from source to my predecessor.
4684 static struct GNUNET_PeerIdentity *
4685 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4686 const struct GNUNET_PeerIdentity *trail_src_to_me,
4687 unsigned int trail_src_to_me_len,
4688 unsigned int *trail_src_to_curr_pred_length)
4690 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4691 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4692 unsigned int trail_me_to_curr_pred_length;
4693 struct FingerInfo *current_predecessor;
4697 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4699 /* Check if trail_src_to_me contains current_predecessor. */
4700 for (i = 0; i < trail_src_to_me_len; i++)
4702 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4703 ¤t_predecessor->finger_identity))
4707 *trail_src_to_curr_pred_length = i;
4712 trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length *
4713 sizeof(struct GNUNET_PeerIdentity));
4714 for(j = 0; j < i;j++)
4715 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4716 return trail_src_to_curr_pred;
4720 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4721 &trail_me_to_curr_pred_length);
4723 /* Check if trail contains the source_peer. */
4724 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4726 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4727 &trail_me_to_curr_pred[i]))
4730 /* Source is NOT part of trail. */
4733 /* Source is the last element in the trail to reach to my pred.
4734 Source is direct friend of the pred. */
4735 if (trail_me_to_curr_pred_length == i)
4737 *trail_src_to_curr_pred_length = 0;
4741 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4742 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4743 *trail_src_to_curr_pred_length);
4745 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4747 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4749 GNUNET_free_non_null(trail_me_to_curr_pred);
4750 return trail_src_to_curr_pred;
4754 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4755 trail_src_to_me_len,
4756 trail_me_to_curr_pred,
4757 trail_me_to_curr_pred_length,
4759 *trail_src_to_curr_pred_length = len;
4760 GNUNET_free_non_null(trail_me_to_curr_pred);
4761 return trail_src_to_curr_pred;
4766 * Add finger as your predecessor. To add, first generate a new trail id, invert
4767 * the trail to get the trail from me to finger, add an entry in your routing
4768 * table, send add trail message to peers which are part of trail from me to
4769 * finger and add finger in finger table.
4772 * @param trail_length
4775 update_predecessor (struct GNUNET_PeerIdentity finger,
4776 struct GNUNET_PeerIdentity *trail,
4777 unsigned int trail_length)
4779 struct GNUNET_HashCode trail_to_new_predecessor_id;
4780 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4781 struct FriendInfo *target_friend;
4783 /* Generate trail id for trail from me to new predecessor = finger. */
4784 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4785 &trail_to_new_predecessor_id,
4786 sizeof (trail_to_new_predecessor_id));
4788 if (0 == trail_length)
4790 trail_to_new_predecessor = NULL;
4791 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4792 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger);
4793 if (NULL == target_friend)
4801 /* Invert the trail to get the trail from me to finger, NOT including the
4803 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4804 &trail[trail_length-1]));
4805 trail_to_new_predecessor = invert_trail (trail, trail_length);
4807 /* Add an entry in your routing table. */
4808 GDS_ROUTING_add (trail_to_new_predecessor_id,
4810 trail_to_new_predecessor[0]);
4812 GNUNET_assert (NULL != (target_friend =
4813 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4814 &trail_to_new_predecessor[0])));
4817 /* Add entry in routing table of all peers that are part of trail from me
4818 to finger, including finger. */
4819 GDS_NEIGHBOURS_send_add_trail (my_identity,
4821 trail_to_new_predecessor_id,
4822 trail_to_new_predecessor,
4826 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4827 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4828 GNUNET_free_non_null(trail_to_new_predecessor);
4833 * Check if you already have a predecessor. If not then add finger as your
4834 * predecessor. If you have predecessor, then compare two peer identites.
4835 * If finger is correct predecessor, then remove the old entry, add finger in
4836 * finger table and send add_trail message to add the trail in the routing
4837 * table of all peers which are part of trail to reach from me to finger.
4838 * @param finger New peer which may be our predecessor.
4839 * @param trail List of peers to reach from @finger to me.
4840 * @param trail_length Total number of peer in @a trail.
4843 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4844 struct GNUNET_PeerIdentity *trail,
4845 unsigned int trail_length)
4847 struct FingerInfo *current_predecessor;
4848 struct GNUNET_PeerIdentity closest_peer;
4849 uint64_t predecessor_value;
4850 unsigned int is_predecessor = 1;
4852 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4853 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4855 /* No predecessor. Add finger as your predecessor. */
4856 if (GNUNET_NO == current_predecessor->is_present)
4858 update_predecessor (finger, trail, trail_length);
4862 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4868 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4869 closest_peer = select_closest_peer (&finger,
4870 ¤t_predecessor->finger_identity,
4871 predecessor_value, is_predecessor);
4873 /* Finger is the closest predecessor. Remove the existing one and add the new
4875 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger))
4877 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4878 update_predecessor (finger, trail, trail_length);
4886 * Core handle for p2p verify successor messages.
4887 * @param cls closure
4888 * @param message message
4889 * @param peer peer identity this notification is about
4890 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4893 handle_dht_p2p_verify_successor(void *cls,
4894 const struct GNUNET_PeerIdentity *peer,
4895 const struct GNUNET_MessageHeader *message)
4897 const struct PeerVerifySuccessorMessage *vsm;
4898 struct GNUNET_HashCode trail_id;
4899 struct GNUNET_PeerIdentity successor;
4900 struct GNUNET_PeerIdentity source_peer;
4901 struct GNUNET_PeerIdentity *trail;
4902 struct GNUNET_PeerIdentity *next_hop;
4903 struct FingerInfo current_predecessor;
4904 struct FriendInfo *target_friend;
4905 unsigned int trail_src_to_curr_pred_len = 0;
4906 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4907 unsigned int trail_length;
4910 msize = ntohs (message->size);
4912 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4914 GNUNET_break_op (0);
4918 vsm = (const struct PeerVerifySuccessorMessage *) message;
4919 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4920 sizeof (struct GNUNET_PeerIdentity);
4921 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4922 sizeof (struct GNUNET_PeerIdentity) != 0)
4924 GNUNET_break_op (0);
4928 GNUNET_STATISTICS_update (GDS_stats,
4930 ("# Bytes received from other peers"), msize,
4933 trail_id = vsm->trail_id;
4934 source_peer = vsm->source_peer;
4935 successor = vsm->successor;
4936 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4938 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4940 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4942 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4943 if (NULL == next_hop)
4948 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4950 if(NULL == target_friend)
4955 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4956 trail_id, trail, trail_length,
4961 /* I am the destination of this message. */
4963 /* Check if the source_peer could be our predecessor and if yes then update
4965 compare_and_update_predecessor (source_peer, trail, trail_length);
4966 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4968 /* Is source of this message NOT my predecessor. */
4969 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4972 trail_src_to_curr_pred =
4973 get_trail_src_to_curr_pred (source_peer,
4976 &trail_src_to_curr_pred_len);
4980 trail_src_to_curr_pred_len = trail_length;
4983 trail_src_to_curr_pred =
4984 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4985 *trail_src_to_curr_pred_len);
4986 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4988 trail_src_to_curr_pred[i] = trail[i];
4992 GNUNET_assert (NULL !=
4994 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4995 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4996 current_predecessor.finger_identity,
4997 trail_id, trail_src_to_curr_pred,
4998 trail_src_to_curr_pred_len,
4999 GDS_ROUTING_DEST_TO_SRC,
5001 GNUNET_free_non_null(trail_src_to_curr_pred);
5007 * If the trail from me to my probable successor contains a friend not
5008 * at index 0, then we can shorten the trail.
5009 * @param probable_successor Peer which is our probable successor
5010 * @param trail_me_to_probable_successor Peers in path from me to my probable
5011 * successor, NOT including the endpoints.
5012 * @param trail_me_to_probable_successor_len Total number of peers in
5013 * @a trail_me_to_probable_succesor.
5014 * @return Updated trail, if any friend found.
5015 * Else the trail_me_to_probable_successor.
5017 struct GNUNET_PeerIdentity *
5018 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
5019 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
5020 unsigned int trail_me_to_probable_successor_len,
5021 unsigned int *trail_to_new_successor_length)
5025 struct GNUNET_PeerIdentity *trail_to_new_successor;
5027 /* Probable successor is a friend */
5028 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5029 &probable_successor))
5031 trail_to_new_successor = NULL;
5032 *trail_to_new_successor_length = 0;
5033 return trail_to_new_successor;
5036 /* Is there any friend of yours in this trail. */
5037 if(trail_me_to_probable_successor_len > 1)
5039 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
5041 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5042 &trail_me_to_probable_successor[i]))
5045 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
5046 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
5047 *trail_to_new_successor_length);
5050 for(j = 0; j < *trail_to_new_successor_length; i++,j++)
5052 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
5055 return trail_to_new_successor;
5059 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
5060 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
5064 struct SendNotifyContext
5066 struct GNUNET_PeerIdentity source_peer;
5067 struct GNUNET_PeerIdentity successor;
5068 struct GNUNET_PeerIdentity *successor_trail;
5069 unsigned int successor_trail_length;
5070 struct GNUNET_HashCode succesor_trail_id;
5071 struct FriendInfo *target_friend;
5072 unsigned int num_retries_scheduled;
5076 send_notify_new_successor (void *cls,
5077 const struct GNUNET_SCHEDULER_TaskContext
5081 * Check if the peer which sent us verify successor result message is still ours
5082 * successor or not. If not, then compare existing successor and probable successor.
5083 * In case probable successor is the correct successor, remove the existing
5084 * successor. Add probable successor as new successor. Send notify new successor
5085 * message to new successor.
5086 * @param curr_succ Peer to which we sent the verify successor message. It may
5087 * or may not be our real current successor, as we may have few iterations of
5088 * find finger trail task.
5089 * @param probable_successor Peer which should be our successor accroding to @a
5091 * @param trail List of peers to reach from me to @a probable successor, NOT including
5093 * @param trail_length Total number of peers in @a trail.
5096 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
5097 struct GNUNET_PeerIdentity probable_successor,
5098 const struct GNUNET_PeerIdentity *trail,
5099 unsigned int trail_length)
5101 struct FingerInfo *current_successor;
5102 struct GNUNET_PeerIdentity closest_peer;
5103 struct GNUNET_HashCode trail_id;
5104 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
5105 struct FriendInfo *target_friend;
5106 unsigned int trail_me_to_probable_succ_len;
5107 unsigned int is_predecessor = 0;
5108 uint64_t successor_value;
5110 current_successor = &finger_table[0];
5111 successor_value = compute_finger_identity_value(0);
5113 /* If probable successor is same as current_successor, do nothing. */
5114 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor,
5115 ¤t_successor->finger_identity))
5117 if ((NULL != GDS_stats))
5123 memcpy (&my_id, &my_identity, sizeof(uint64_t));
5124 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5125 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5126 succ = GNUNET_ntohll(succ);
5127 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5128 GNUNET_free (my_id_str);
5130 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5133 if (send_verify_successor_task == GNUNET_SCHEDULER_NO_TASK)
5134 send_verify_successor_task =
5135 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5136 &send_verify_successor_message,
5140 closest_peer = select_closest_peer (&probable_successor,
5141 ¤t_successor->finger_identity,
5142 successor_value, is_predecessor);
5144 /* If the current_successor in the finger table is closest, then do nothing. */
5145 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer ,
5146 ¤t_successor->finger_identity))
5148 //FIXME: Is this a good place to return the stats.
5149 if ((NULL != GDS_stats))
5155 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5156 memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t));
5157 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5158 GNUNET_free (my_id_str);
5159 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5163 if(0 == successor_times)
5165 // successor_times = 3;
5166 verify_successor_next_send_time =
5167 GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time);
5173 if (send_verify_successor_task == GNUNET_SCHEDULER_NO_TASK)
5174 send_verify_successor_task =
5175 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5176 &send_verify_successor_message,
5181 /* Probable successor is the closest peer.*/
5182 if(trail_length > 0)
5184 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5189 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
5190 &probable_successor));
5193 trail_me_to_probable_succ_len = 0;
5194 trail_me_to_probable_succ =
5195 check_trail_me_to_probable_succ (probable_successor,
5196 trail, trail_length,
5197 &trail_me_to_probable_succ_len);
5199 /* Remove the existing successor. */
5200 remove_existing_finger (current_successor, 0);
5201 /* Generate a new trail id to reach to your new successor. */
5202 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5203 &trail_id, sizeof (trail_id));
5205 if (trail_me_to_probable_succ_len > 0)
5207 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
5208 GNUNET_assert (NULL !=
5210 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5211 &trail_me_to_probable_succ[0])));
5215 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
5216 GNUNET_assert (NULL !=
5218 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5219 &probable_successor)));
5222 add_new_finger (probable_successor, trail_me_to_probable_succ,
5223 trail_me_to_probable_succ_len, trail_id, 0);
5225 struct SendNotifyContext *notify_ctx;
5227 notify_ctx = GNUNET_new(struct SendNotifyContext);
5229 notify_ctx->source_peer = my_identity;
5230 notify_ctx->successor = probable_successor;
5231 notify_ctx->successor_trail =
5232 GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5233 memcpy(notify_ctx->successor_trail, trail_me_to_probable_succ,
5234 sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5235 notify_ctx->successor_trail_length = trail_me_to_probable_succ_len;
5236 notify_ctx->succesor_trail_id = trail_id;
5237 notify_ctx->target_friend = target_friend;
5238 notify_ctx->num_retries_scheduled = 0;
5240 // TODO: Check if we should verify before schedule if already scheduled.
5241 GNUNET_SCHEDULER_add_now(&send_notify_new_successor, (void*)notify_ctx);
5249 send_notify_new_successor (void *cls,
5250 const struct GNUNET_SCHEDULER_TaskContext
5253 struct SendNotifyContext *ctx = (struct SendNotifyContext *) cls;
5255 GDS_NEIGHBOURS_send_notify_new_successor (ctx->source_peer,
5257 ctx->successor_trail,
5258 ctx->successor_trail_length,
5259 ctx->succesor_trail_id,
5260 ctx->target_friend);
5262 if (0 == ctx->num_retries_scheduled &&
5263 send_notify_new_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
5265 // Result from previous notify successos hasn't arrived, so the retry task
5266 // hasn't been cancelled! Already a new notify successor must be called.
5267 // We will cancel the retry request.
5268 struct SendNotifyContext *old_notify_ctx;
5269 old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5270 GNUNET_free (old_notify_ctx->successor_trail);
5271 GNUNET_free (old_notify_ctx);
5272 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
5275 ctx->num_retries_scheduled++;
5276 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_add_delayed(notify_successor_retry_time,
5277 &send_notify_new_successor,
5282 * Core handle for p2p verify successor result messages.
5283 * @param cls closure
5284 * @param message message
5285 * @param peer peer identity this notification is about
5286 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5289 handle_dht_p2p_verify_successor_result(void *cls,
5290 const struct GNUNET_PeerIdentity *peer,
5291 const struct GNUNET_MessageHeader *message)
5293 const struct PeerVerifySuccessorResultMessage *vsrm;
5294 enum GDS_ROUTING_trail_direction trail_direction;
5295 struct GNUNET_PeerIdentity querying_peer;
5296 struct GNUNET_HashCode trail_id;
5297 struct GNUNET_PeerIdentity *next_hop;
5298 struct FriendInfo *target_friend;
5299 struct GNUNET_PeerIdentity probable_successor;
5300 struct GNUNET_PeerIdentity current_successor;
5301 const struct GNUNET_PeerIdentity *trail;
5302 unsigned int trail_length;
5305 msize = ntohs (message->size);
5306 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5308 GNUNET_break_op (0);
5312 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5313 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5314 sizeof (struct GNUNET_PeerIdentity) != 0)
5316 GNUNET_break_op (0);
5319 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5320 sizeof (struct GNUNET_PeerIdentity);
5322 GNUNET_STATISTICS_update (GDS_stats,
5324 ("# Bytes received from other peers"), msize,
5327 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5328 querying_peer = vsrm->querying_peer;
5329 trail_direction = ntohl (vsrm->trail_direction);
5330 trail_id = vsrm->trail_id;
5331 probable_successor = vsrm->probable_successor;
5332 current_successor = vsrm->current_successor;
5334 /* I am the querying_peer. */
5335 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5337 /* Cancel Retry Task */
5338 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_retry_task)
5340 struct VerifySuccessorContext *ctx;
5341 ctx = GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
5343 send_verify_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
5345 compare_and_update_successor (current_successor,
5346 probable_successor, trail, trail_length);
5350 /*If you are not the querying peer then pass on the message */
5351 if(NULL == (next_hop =
5352 GDS_ROUTING_get_next_hop (trail_id, trail_direction)))
5354 /* Here it may happen that source peer has found a new successor, and removed
5355 the trail, Hence no entry found in the routing table. Fail silently.*/
5356 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5357 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5361 if (NULL == (target_friend =
5362 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5367 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5368 vsrm->current_successor,
5369 probable_successor, trail_id,
5372 trail_direction, target_friend);
5378 * Core handle for p2p notify new successor messages.
5379 * @param cls closure
5380 * @param message message
5381 * @param peer peer identity this notification is about
5382 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5385 handle_dht_p2p_notify_new_successor(void *cls,
5386 const struct GNUNET_PeerIdentity *peer,
5387 const struct GNUNET_MessageHeader *message)
5389 const struct PeerNotifyNewSuccessorMessage *nsm;
5390 struct GNUNET_PeerIdentity *trail;
5391 struct GNUNET_PeerIdentity source;
5392 struct GNUNET_PeerIdentity new_successor;
5393 struct GNUNET_HashCode trail_id;
5394 struct GNUNET_PeerIdentity next_hop;
5395 struct FriendInfo *target_friend;
5398 uint32_t trail_length;
5400 msize = ntohs (message->size);
5401 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5403 GNUNET_break_op (0);
5406 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5407 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5408 sizeof (struct GNUNET_PeerIdentity) != 0)
5410 GNUNET_break_op (0);
5413 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5414 sizeof (struct GNUNET_PeerIdentity);
5415 GNUNET_STATISTICS_update (GDS_stats,
5417 ("# Bytes received from other peers"), msize,
5420 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5421 source = nsm->source_peer;
5422 new_successor = nsm->new_successor;
5423 trail_id = nsm->trail_id;
5425 /* I am the new_successor to source_peer. */
5426 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5428 if(trail_length > 0)
5429 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5432 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5434 compare_and_update_predecessor (source, trail, trail_length);
5435 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5436 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5437 GDS_ROUTING_DEST_TO_SRC,
5442 GNUNET_assert(trail_length > 0);
5443 /* I am part of trail to reach to successor. */
5444 my_index = search_my_index (trail, trail_length);
5447 DEBUG ("No entry found in trail\n");
5448 GNUNET_break_op (0);
5449 return GNUNET_SYSERR;
5451 if((trail_length + 1) == my_index)
5453 DEBUG ("Found twice in trail.\n");
5454 GNUNET_break_op (0);
5455 return GNUNET_SYSERR;
5457 if ((trail_length-1) == my_index)
5458 next_hop = new_successor;
5460 next_hop = trail[my_index + 1];
5462 GDS_ROUTING_add(trail_id, *peer, next_hop);
5464 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
5465 if (NULL == target_friend)
5470 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5472 trail_id, target_friend);
5479 * Core handler for P2P notify successor message
5480 * @param cls closure
5481 * @param message message
5482 * @param peer peer identity this notification is about
5483 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5486 handle_dht_p2p_notify_succ_confirmation (void *cls,
5487 const struct GNUNET_PeerIdentity *peer,
5488 const struct GNUNET_MessageHeader *message)
5490 const struct PeerNotifyConfirmationMessage *notify_confirmation;
5491 enum GDS_ROUTING_trail_direction trail_direction;
5492 struct GNUNET_HashCode trail_id;
5493 struct FriendInfo *target_friend;
5494 struct GNUNET_PeerIdentity *next_hop;
5497 msize = ntohs (message->size);
5499 if (msize != sizeof (struct PeerNotifyConfirmationMessage))
5501 GNUNET_break_op (0);
5504 GNUNET_STATISTICS_update (GDS_stats,
5506 ("# Bytes received from other peers"), msize,
5509 notify_confirmation = (const struct PeerNotifyConfirmationMessage *) message;
5510 trail_direction = ntohl (notify_confirmation->trail_direction);
5511 trail_id = notify_confirmation->trail_id;
5513 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5514 if (NULL == next_hop)
5516 /* The source of notify new successor, might have found even a better
5517 successor. In that case it send a trail teardown message, and hence,
5518 the next hop is NULL. */
5519 //Fixme: Add some print to confirm the above theory.
5523 /* I peer which sent the notify successor message to the successor. */
5524 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5527 * Schedule another round of verify sucessor with your current successor
5528 * which may or may not be source of this message. This message is used
5529 * only to ensure that we have a path setup to reach to our successor.
5532 // TODO: cancel schedule of notify_successor_retry_task
5533 if (send_notify_new_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
5535 struct SendNotifyContext *notify_ctx;
5536 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5537 GNUNET_free (notify_ctx->successor_trail);
5538 GNUNET_free (notify_ctx);
5539 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
5541 if (send_verify_successor_task == GNUNET_SCHEDULER_NO_TASK)
5543 verify_successor_next_send_time.rel_value_us =
5544 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5545 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5546 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5547 send_verify_successor_task =
5548 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5549 &send_verify_successor_message,
5555 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
5556 if (NULL == target_friend)
5558 DEBUG ("\n friend not found, line number = %d",__LINE__);
5559 return GNUNET_SYSERR;
5561 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id,
5562 GDS_ROUTING_DEST_TO_SRC,
5570 * Core handler for P2P trail rejection message
5571 * @param cls closure
5572 * @param message message
5573 * @param peer peer identity this notification is about
5574 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5577 handle_dht_p2p_trail_setup_rejection (void *cls,
5578 const struct GNUNET_PeerIdentity *peer,
5579 const struct GNUNET_MessageHeader *message)
5581 const struct PeerTrailRejectionMessage *trail_rejection;
5582 unsigned int trail_length;
5583 const struct GNUNET_PeerIdentity *trail_peer_list;
5584 struct FriendInfo *target_friend;
5585 struct GNUNET_TIME_Relative congestion_timeout;
5586 struct GNUNET_HashCode trail_id;
5587 struct GNUNET_PeerIdentity next_peer;
5588 struct GNUNET_PeerIdentity source;
5589 uint64_t ultimate_destination_finger_value;
5590 unsigned int is_predecessor;
5593 msize = ntohs (message->size);
5594 if (msize < sizeof (struct PeerTrailRejectionMessage))
5596 GNUNET_break_op (0);
5599 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5600 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5601 sizeof (struct GNUNET_PeerIdentity) != 0)
5603 GNUNET_break_op (0);
5606 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5607 sizeof (struct GNUNET_PeerIdentity);
5608 GNUNET_STATISTICS_update (GDS_stats,
5610 ("# Bytes received from other peers"), msize,
5613 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5614 is_predecessor = ntohl (trail_rejection->is_predecessor);
5615 congestion_timeout = trail_rejection->congestion_time;
5616 source = trail_rejection->source_peer;
5617 trail_id = trail_rejection->trail_id;
5618 ultimate_destination_finger_value =
5619 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5620 /* First set the congestion time of the friend that sent you this message. */
5621 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
5622 if (NULL == target_friend)
5624 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5628 target_friend->congestion_timestamp =
5629 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5630 congestion_timeout);
5632 /* I am the source peer which wants to setup the trail. Do nothing.
5633 * send_find_finger_trail_task is scheduled periodically.*/
5634 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5637 /* If I am congested then pass this message to peer before me in trail. */
5638 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5640 /* First remove yourself from the trail. */
5641 unsigned int new_trail_length = trail_length - 1;
5642 struct GNUNET_PeerIdentity trail[new_trail_length];
5644 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5645 if (0 == trail_length)
5648 next_peer = trail[new_trail_length-1];
5651 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5652 if (NULL == target_friend)
5654 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5658 GDS_NEIGHBOURS_send_trail_rejection (source,
5659 ultimate_destination_finger_value,
5660 my_identity, is_predecessor,
5661 trail, new_trail_length, trail_id,
5662 target_friend, CONGESTION_TIMEOUT);
5666 struct Closest_Peer successor;
5667 successor = find_local_best_known_next_hop (ultimate_destination_finger_value, is_predecessor);
5669 /* Am I the final destination? */
5670 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5673 /*Here you are already part of trail. Copy the trail removing yourself. */
5674 unsigned int new_trail_length = trail_length - 1;
5675 struct GNUNET_PeerIdentity trail[new_trail_length];
5677 memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5679 if (0 == new_trail_length)
5683 next_peer = trail[new_trail_length-1];
5686 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
5688 if (NULL == target_friend)
5690 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5694 GDS_NEIGHBOURS_send_trail_setup_result (source,
5696 target_friend, new_trail_length,
5699 ultimate_destination_finger_value,
5704 /* Here I was already part of trail. So no need to add. */
5706 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5707 &successor.next_hop);
5708 if (NULL == target_friend)
5710 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5715 GDS_NEIGHBOURS_send_trail_setup (source,
5716 ultimate_destination_finger_value,
5717 successor.best_known_destination,
5718 target_friend, trail_length, trail_peer_list,
5719 is_predecessor, trail_id,
5720 successor.trail_id);
5727 * Core handler for trail teardown message.
5728 * @param cls closure
5729 * @param message message
5730 * @param peer sender of this messsage.
5731 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5734 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5735 const struct GNUNET_MessageHeader *message)
5737 const struct PeerTrailTearDownMessage *trail_teardown;
5738 enum GDS_ROUTING_trail_direction trail_direction;
5739 struct GNUNET_HashCode trail_id;
5740 struct GNUNET_PeerIdentity *next_hop;
5743 msize = ntohs (message->size);
5745 /* Here we pass only the trail id. */
5746 if (msize != sizeof (struct PeerTrailTearDownMessage))
5748 GNUNET_break_op (0);
5752 GNUNET_STATISTICS_update (GDS_stats,
5754 ("# Bytes received from other peers"), msize,
5757 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5758 trail_direction = ntohl (trail_teardown->trail_direction);
5759 trail_id = trail_teardown->trail_id;
5761 /* Check if peer is the real peer from which we should get this message.*/
5762 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5764 GNUNET_assert (NULL != (prev_hop =
5765 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5766 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5769 return GNUNET_SYSERR;
5773 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5774 if (NULL == next_hop)
5776 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line",
5777 GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__);
5779 return GNUNET_SYSERR;
5782 /* I am the next hop, which means I am the final destination. */
5783 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5785 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5790 /* If not final destination, then send a trail teardown message to next hop.*/
5791 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5792 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5793 GDS_NEIGHBOURS_send_trail_teardown (&trail_id, trail_direction, next_hop);
5801 * Core handle for p2p add trail message.
5802 * @param cls closure
5803 * @param message message
5804 * @param peer peer identity this notification is about
5805 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5808 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5809 const struct GNUNET_MessageHeader *message)
5811 const struct PeerAddTrailMessage *add_trail;
5812 const struct GNUNET_PeerIdentity *trail;
5813 struct GNUNET_HashCode trail_id;
5814 struct GNUNET_PeerIdentity destination_peer;
5815 struct GNUNET_PeerIdentity source_peer;
5816 struct GNUNET_PeerIdentity next_hop;
5817 unsigned int trail_length;
5818 unsigned int my_index;
5821 msize = ntohs (message->size);
5822 /* In this message we pass the whole trail from source to destination as we
5823 * are adding that trail.*/
5824 //FIXME: failed when run with 1000 pears. check why.
5825 if (msize < sizeof (struct PeerAddTrailMessage))
5827 GNUNET_break_op (0);
5831 add_trail = (const struct PeerAddTrailMessage *) message;
5832 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5833 sizeof (struct GNUNET_PeerIdentity);
5834 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5835 sizeof (struct GNUNET_PeerIdentity) != 0)
5837 GNUNET_break_op (0);
5841 GNUNET_STATISTICS_update (GDS_stats,
5843 ("# Bytes received from other peers"), msize,
5846 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5847 destination_peer = add_trail->destination_peer;
5848 source_peer = add_trail->source_peer;
5849 trail_id = add_trail->trail_id;
5851 /* I am not the destination of the trail. */
5852 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5854 struct FriendInfo *target_friend;
5856 /* Get my location in the trail. */
5857 my_index = search_my_index (trail, trail_length);
5860 GNUNET_break_op (0);
5861 return GNUNET_SYSERR;
5863 if((trail_length + 1) == my_index)
5865 DEBUG ("Found twice in trail.\n");
5866 GNUNET_break_op (0);
5867 return GNUNET_SYSERR;
5869 if ((trail_length - 1) == my_index)
5871 next_hop = destination_peer;
5875 next_hop = trail[my_index + 1];
5877 /* Add in your routing table. */
5878 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5879 //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5880 GNUNET_assert (NULL !=
5882 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5883 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5884 trail, trail_length, target_friend);
5887 /* I am the destination. Add an entry in routing table. */
5888 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5894 * Free the finger trail in which the first friend to reach to a finger is
5895 * disconnected_friend. Also remove entry from routing table for that particular
5897 * @param disconnected_friend PeerIdentity of friend which got disconnected
5898 * @param remove_finger Finger whose trail we need to check if it has
5899 * disconnected_friend as the first hop.
5900 * @return Total number of trails in which disconnected_friend was the first
5904 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5905 struct FingerInfo *finger)
5907 struct GNUNET_PeerIdentity *next_hop;
5908 struct FriendInfo *remove_friend;
5909 struct Trail *current_trail;
5910 unsigned int matching_trails_count = 0;
5913 /* Iterate over all the trails of finger. */
5914 for (i = 0; i < finger->trails_count; i++)
5916 current_trail = &finger->trail_list[i];
5917 if (GNUNET_NO == current_trail->is_present)
5920 /* First friend to reach to finger is disconnected_peer. */
5921 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer,
5922 disconnected_friend))
5925 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5926 disconnected_friend);
5927 GNUNET_assert (NULL != remove_friend);
5928 next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id,
5929 GDS_ROUTING_SRC_TO_DEST);
5931 /* Here it may happen that as all the peers got disconnected, the entry in
5932 routing table for that particular trail has been removed, because the
5933 previously disconnected peer was either a next hop or prev hop of that
5935 if (NULL != next_hop)
5937 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5939 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id));
5941 matching_trails_count++;
5942 free_trail (current_trail);
5943 current_trail->is_present = GNUNET_NO;
5946 return matching_trails_count;
5951 * Iterate over finger_table entries.
5952 * 0. Ignore finger which is my_identity or if no valid entry present at
5953 * that finger index.
5954 * 1. If disconnected_friend is a finger, then remove the routing entry from
5955 your own table. Free the trail.
5956 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5957 * 2.1 Remove all the trails and entry from routing table in which disconnected
5958 * friend is the first friend in the trail. If disconnected_friend is the
5959 * first friend in all the trails to reach finger, then remove the finger.
5960 * @param disconnected_friend Peer identity of friend which got disconnected.
5963 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5965 struct FingerInfo *current_finger;
5966 int removed_trails_count;
5969 /* Iterate over finger table entries. */
5970 for (i = 0; i < MAX_FINGERS; i++)
5972 current_finger = &finger_table[i];
5974 /* No finger stored at this trail index or I am the finger. */
5975 if ((GNUNET_NO == current_finger->is_present) ||
5976 (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity,
5980 /* Is disconnected_peer a finger? */
5981 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5982 ¤t_finger->finger_identity))
5984 remove_existing_finger (current_finger, i);
5987 /* If finger is a friend but not disconnected_friend, then continue. */
5988 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5989 ¤t_finger->finger_identity))
5992 /* Iterate over the list of trails to reach remove_finger. Check if
5993 * disconnected_friend is the first friend in any of the trail. */
5994 removed_trails_count = remove_matching_trails (disconnected_peer,
5996 current_finger->trails_count =
5997 current_finger->trails_count - removed_trails_count;
5998 if (0 == current_finger->trails_count)
6000 current_finger->is_present = GNUNET_NO;
6001 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
6008 * Method called whenever a peer disconnects.
6010 * @param cls closure
6011 * @param peer peer identity this notification is about
6014 handle_core_disconnect (void *cls,
6015 const struct GNUNET_PeerIdentity *peer)
6017 struct FriendInfo *remove_friend;
6018 struct P2PPendingMessage *pos;
6019 unsigned int discarded;
6021 /* If disconnected to own identity, then return. */
6022 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
6025 if(NULL == (remove_friend =
6026 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)))
6028 DEBUG("\n friend already disconnected.");
6032 remove_matching_fingers (peer);
6033 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
6034 GNUNET_assert (GNUNET_YES ==
6035 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
6039 /* Remove all the messages queued in pending list of this peer is discarded.*/
6040 if (remove_friend->th != NULL)
6042 GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th);
6043 remove_friend->th = NULL;
6047 while (NULL != (pos = remove_friend->head))
6049 GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos);
6054 GNUNET_STATISTICS_update (GDS_stats,
6056 ("# Queued messages discarded (peer disconnected)"),
6057 discarded, GNUNET_NO);
6058 //GNUNET_free (remove_friend);
6060 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
6063 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
6065 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6066 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
6074 * Method called whenever a peer connects.
6076 * @param cls closure
6077 * @param peer_identity peer identity this notification is about
6080 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
6082 struct FriendInfo *friend;
6084 /* Check for connect to self message */
6085 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
6088 /* If peer already exists in our friend_peermap, then exit. */
6089 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
6096 friend = GNUNET_new (struct FriendInfo);
6097 friend->id = *peer_identity;
6099 GNUNET_assert (GNUNET_OK ==
6100 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
6101 peer_identity, friend,
6102 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
6104 /* FIXME: now we are not making a distinction between fingers which are friends
6105 * also.But later, we should add a congestion timestamp on the friend, so that it is
6106 * selected after some time out. This is to ensure that both peers have added
6107 * each other as their friend. */
6108 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
6109 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
6111 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
6117 * To be called on core init/fail.
6119 * @param cls service closure
6120 * @param identity the public identity of this peer
6123 core_init (void *cls,
6124 const struct GNUNET_PeerIdentity *identity)
6126 my_identity = *identity;
6131 * Initialize finger table entries.
6134 finger_table_init ()
6136 memset (&finger_table, 0, sizeof (finger_table));
6141 * Initialize neighbours subsystem.
6142 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
6145 GDS_NEIGHBOURS_init (void)
6147 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
6148 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
6149 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
6150 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
6151 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
6152 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
6153 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
6154 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
6155 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
6156 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
6157 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
6158 sizeof (struct PeerTrailTearDownMessage)},
6159 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
6160 {&handle_dht_p2p_notify_succ_confirmation, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION,
6161 sizeof (struct PeerNotifyConfirmationMessage)},
6165 #if ENABLE_MALICIOUS
6170 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
6171 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
6172 GNUNET_NO, core_handlers);
6174 if (NULL == core_api)
6175 return GNUNET_SYSERR;
6177 //TODO: check size of this peer map?
6178 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
6179 finger_table_init ();
6180 successor_times = 10;
6181 fingers_round_count = 5;
6182 find_finger_trail_task_next_send_time.rel_value_us =
6183 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
6184 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6185 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
6187 verify_successor_next_send_time.rel_value_us =
6188 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
6189 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6190 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
6192 verify_successor_retry_time.rel_value_us =
6193 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6194 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6195 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6197 notify_successor_retry_time.rel_value_us =
6198 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6199 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6200 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6208 * Free the memory held up by trails of a finger.
6211 delete_finger_table_entries()
6216 for(i = 0; i < MAX_FINGERS; i++)
6218 if(GNUNET_YES == finger_table[i].is_present)
6220 for(j = 0; j < finger_table[i].trails_count; j++)
6221 free_trail(&finger_table[i].trail_list[j]);
6228 * Shutdown neighbours subsystem.
6231 GDS_NEIGHBOURS_done (void)
6233 if (NULL == core_api)
6236 GNUNET_CORE_disconnect (core_api);
6239 delete_finger_table_entries();
6240 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6241 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6242 friend_peermap = NULL;
6244 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
6246 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6247 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
6250 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
6252 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6253 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
6256 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_retry_task)
6258 struct VerifySuccessorContext *ctx;
6259 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
6261 send_verify_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
6264 if (send_notify_new_successor_retry_task != GNUNET_SCHEDULER_NO_TASK)
6266 struct SendNotifyContext *notify_ctx;
6267 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
6268 GNUNET_free (notify_ctx->successor_trail);
6269 GNUNET_free (notify_ctx);
6270 send_notify_new_successor_retry_task = GNUNET_SCHEDULER_NO_TASK;
6278 * @return my identity
6280 struct GNUNET_PeerIdentity
6281 GDS_NEIGHBOURS_get_my_id (void)
6286 /* end of gnunet-service-xdht_neighbours.c */