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
57 * Maximum possible fingers (including predecessor) of a peer
59 #define MAX_FINGERS 65
62 * Maximum allowed number of pending messages per friend peer.
64 #define MAXIMUM_PENDING_PER_FRIEND 64
67 * How long to wait before sending another find finger trail request
69 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
72 * How long to wait before sending another verify successor message.
74 #define DHT_SEND_VERIFY_SUCCESSOR_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 1)
77 * How long at most to wait for transmission of a request to a friend ?
79 #define GET_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
82 * Duration for which I may remain congested.
83 * Note: Its a static value. In future, a peer may do some analysis and calculate
84 * congestion_timeout based on 'some' parameters.
86 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
89 * Maximum number of trails allowed to go through a friend.
91 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
94 * Maximum number of trails stored per finger.
96 #define MAXIMUM_TRAILS_PER_FINGER 1
99 * Finger map index for predecessor entry in finger table.
101 #define PREDECESSOR_FINGER_ID 64
104 * Wrap around in peer identity circle.
106 #define PEER_IDENTITES_WRAP_AROUND pow(2, 64) - 1
109 * FIXME: Its use only at 3 places check if you can remove it.
110 * To check if a finger is predecessor or not.
112 enum GDS_NEIGHBOURS_finger_type
114 GDS_FINGER_TYPE_PREDECESSOR = 1,
115 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
118 GNUNET_NETWORK_STRUCT_BEGIN
123 struct PeerPutMessage
126 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
128 struct GNUNET_MessageHeader header;
133 uint32_t options GNUNET_PACKED;
138 uint32_t block_type GNUNET_PACKED;
143 uint32_t hop_count GNUNET_PACKED;
146 * Replication level for this message
147 * In the current implementation, this value is not used.
149 uint32_t desired_replication_level GNUNET_PACKED;
152 * Length of the PUT path that follows (if tracked).
154 uint32_t put_path_length GNUNET_PACKED;
157 * Best known destination (could be my friend or finger) which should
158 * get this message next.
160 struct GNUNET_PeerIdentity best_known_destination;
163 * In case best_known_destination is a finger, then trail to reach
164 * to that finger. Else its default value is 0.
166 struct GNUNET_HashCode intermediate_trail_id;
169 * When does the content expire?
171 struct GNUNET_TIME_AbsoluteNBO expiration_time;
174 * The key to store the value under.
176 struct GNUNET_HashCode key GNUNET_PACKED;
178 /* put path (if tracked) */
187 struct PeerGetMessage
190 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
192 struct GNUNET_MessageHeader header;
197 uint32_t options GNUNET_PACKED;
200 * Desired content type.
202 uint32_t block_type GNUNET_PACKED;
207 uint32_t hop_count GNUNET_PACKED;
210 * Desired replication level for this request.
211 * In the current implementation, this value is not used.
213 uint32_t desired_replication_level GNUNET_PACKED;
216 * Total number of peers in get path.
218 unsigned int get_path_length;
221 * Best known destination (could be my friend or finger) which should
222 * get this message next.
224 struct GNUNET_PeerIdentity best_known_destination;
227 * In case best_known_destination is a finger, then trail to reach
228 * to that finger. Else its default value is 0.
230 struct GNUNET_HashCode intermediate_trail_id;
233 * The key we are looking for.
235 struct GNUNET_HashCode key;
238 /* struct GNUNET_PeerIdentity[]*/
244 struct PeerGetResultMessage
247 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
249 struct GNUNET_MessageHeader header;
252 * The type for the data.
254 uint32_t type GNUNET_PACKED;
257 * Number of peers recorded in the outgoing path from source to the
258 * stored location of this message.
260 uint32_t put_path_length GNUNET_PACKED;
263 * Length of the GET path that follows (if tracked).
265 uint32_t get_path_length GNUNET_PACKED;
268 * Peer which queried for get and should get the result.
270 struct GNUNET_PeerIdentity querying_peer;
273 * When does the content expire?
275 struct GNUNET_TIME_Absolute expiration_time;
278 * The key of the corresponding GET request.
280 struct GNUNET_HashCode key;
282 /* put path (if tracked) */
284 /* get path (if tracked) */
291 * P2P Trail setup message
293 struct PeerTrailSetupMessage
296 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
298 struct GNUNET_MessageHeader header;
301 * Is source_peer trying to setup the trail to a predecessor or any finger.
303 uint32_t is_predecessor;
306 * Peer closest to this value will be our finger.
308 uint64_t final_destination_finger_value;
311 * Source peer which wants to setup the trail to one of its finger.
313 struct GNUNET_PeerIdentity source_peer;
316 * Best known destination (could be my friend or finger) which should
317 * get this message next.
319 * FIXME: this could be removed if we include trail_source / trail_dest
320 * in the routing table. This way we save 32 bytes of bandwidth by using
321 * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID))
323 struct GNUNET_PeerIdentity best_known_destination;
326 * In case best_known_destination is a finger, then trail id of trail to
327 * reach to this finger.
329 struct GNUNET_HashCode intermediate_trail_id;
332 * Trail id for trail which we are trying to setup.
334 struct GNUNET_HashCode trail_id;
336 /* List of peers which are part of trail setup so far.
337 * Trail does NOT include source_peer and peer which will be closest to
338 * ultimate_destination_finger_value.
339 * struct GNUNET_PeerIdentity trail[]
344 * P2P Trail Setup Result message
346 struct PeerTrailSetupResultMessage
350 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
352 struct GNUNET_MessageHeader header;
355 * Finger to which we have found the path.
357 struct GNUNET_PeerIdentity finger_identity;
360 * Peer which started trail_setup to find trail to finger_identity
362 struct GNUNET_PeerIdentity querying_peer;
365 * Is the trail setup to querying_peer's predecessor or finger?
367 uint32_t is_predecessor;
370 * Value to which finger_identity is the closest peer.
372 uint64_t ulitmate_destination_finger_value;
375 * Identifier of the trail from querying peer to finger_identity, NOT
376 * including both endpoints.
378 struct GNUNET_HashCode trail_id;
380 /* List of peers which are part of the trail from querying peer to
381 * finger_identity, NOT including both endpoints.
382 * struct GNUNET_PeerIdentity trail[]
387 * P2P Verify Successor Message.
389 struct PeerVerifySuccessorMessage
392 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
394 struct GNUNET_MessageHeader header;
397 * Peer which wants to verify its successor.
399 struct GNUNET_PeerIdentity source_peer;
402 * Source Peer's current successor.
404 struct GNUNET_PeerIdentity successor;
407 * Identifier of trail to reach from source_peer to successor.
409 struct GNUNET_HashCode trail_id;
411 /* List of the peers which are part of trail to reach from source_peer
412 * to successor, NOT including them
413 * struct GNUNET_PeerIdentity trail[]
418 * P2P Verify Successor Result Message
420 struct PeerVerifySuccessorResultMessage
423 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
425 struct GNUNET_MessageHeader header;
428 * Peer which sent the request to verify its successor.
430 struct GNUNET_PeerIdentity querying_peer;
433 * Successor to which PeerVerifySuccessorMessage was sent.
435 struct GNUNET_PeerIdentity current_successor;
438 * Current Predecessor of source_successor. It can be same as querying peer
439 * or different. In case it is different then it can be querying_peer's
440 * probable successor.
442 struct GNUNET_PeerIdentity probable_successor;
445 * Trail identifier of trail from querying_peer to current_successor.
447 struct GNUNET_HashCode trail_id;
450 * Direction in which we are looking at the trail.
452 uint32_t trail_direction;
454 /* In case probable_successor != querying_peer, then trail to reach from
455 * querying_peer to probable_successor, NOT including end points.
456 * struct GNUNET_PeerIdentity trail[]
461 * P2P Notify New Successor Message.
463 struct PeerNotifyNewSuccessorMessage
466 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
468 struct GNUNET_MessageHeader header;
471 * Peer which wants to notify its new successor.
473 struct GNUNET_PeerIdentity source_peer;
476 * New successor of source_peer.
478 struct GNUNET_PeerIdentity new_successor;
481 * Unique identifier of the trail from source_peer to new_successor,
482 * NOT including the endpoints.
484 struct GNUNET_HashCode trail_id;
486 /* List of peers in trail from source_peer to new_successor,
487 * NOT including the endpoints.
488 * struct GNUNET_PeerIdentity trail[]
493 * P2P Trail Compression Message.
495 struct PeerTrailCompressionMessage
498 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION
500 struct GNUNET_MessageHeader header;
503 * Source peer of this trail.
505 struct GNUNET_PeerIdentity source_peer;
508 * Trail from source_peer to destination_peer compressed such that
509 * new_first_friend is the first hop in the trail from source to
512 struct GNUNET_PeerIdentity new_first_friend;
515 * Unique identifier of trail.
517 struct GNUNET_HashCode trail_id;
522 * P2P Trail Tear Down message.
524 struct PeerTrailTearDownMessage
527 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
529 struct GNUNET_MessageHeader header;
532 * Unique identifier of the trail.
534 struct GNUNET_HashCode trail_id;
537 * Direction of trail.
539 uint32_t trail_direction;
544 * P2P Trail Rejection Message.
546 struct PeerTrailRejectionMessage
549 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
551 struct GNUNET_MessageHeader header;
554 * Peer which wants to set up the trail.
556 struct GNUNET_PeerIdentity source_peer;
559 * Peer which sent trail rejection message as it it congested.
561 struct GNUNET_PeerIdentity congested_peer;
564 * Peer identity closest to this value will be finger of
567 uint64_t ultimate_destination_finger_value;
570 * Is source_peer trying to setup the trail to its predecessor or finger.
572 uint32_t is_predecessor;
575 * Identifier for the trail that source peer is trying to setup.
577 struct GNUNET_HashCode trail_id;
580 * Relative time for which congested_peer will remain congested.
582 struct GNUNET_TIME_Relative congestion_time;
584 /* Trail_list from source_peer to peer which sent the message for trail setup
585 * to congested peer. This trail does NOT include source_peer.
586 struct GNUNET_PeerIdnetity trail[]*/
590 * P2P Add Trail Message.
592 struct PeerAddTrailMessage
595 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
597 struct GNUNET_MessageHeader header;
600 * Source of the routing trail.
602 struct GNUNET_PeerIdentity source_peer;
605 * Destination of the routing trail.
607 struct GNUNET_PeerIdentity destination_peer;
610 * Unique identifier of the trail from source_peer to destination_peer,
611 * NOT including the endpoints.
613 struct GNUNET_HashCode trail_id;
615 /* Trail from source peer to destination peer, NOT including them.
616 * struct GNUNET_PeerIdentity trail[]
620 GNUNET_NETWORK_STRUCT_END
623 * Linked list of messages to send to a particular other peer.
625 struct P2PPendingMessage
628 * Pointer to next item in the list
630 struct P2PPendingMessage *next;
633 * Pointer to previous item in the list
635 struct P2PPendingMessage *prev;
638 * Message importance level. FIXME: used? useful?
640 unsigned int importance;
643 * When does this message time out?
645 struct GNUNET_TIME_Absolute timeout;
648 * Actual message to be sent, allocated at the end of the struct:
649 * // msg = (cast) &pm[1];
650 * // memcpy (&pm[1], data, len);
652 const struct GNUNET_MessageHeader *msg;
657 * Entry in friend_peermap.
664 struct GNUNET_PeerIdentity id;
667 * Number of trails for which this friend is the first hop or if the friend
670 unsigned int trails_count;
673 * Count of outstanding messages for this friend.
675 unsigned int pending_count;
678 * In case not 0, then amount of time for which this friend is congested.
680 struct GNUNET_TIME_Absolute congestion_timestamp;
683 * Head of pending messages to be sent to this friend.
685 struct P2PPendingMessage *head;
688 * Tail of pending messages to be sent to this friend.
690 struct P2PPendingMessage *tail;
693 * Core handle for sending messages to this friend.
695 struct GNUNET_CORE_TransmitHandle *th;
700 * An individual element of the trail to reach to a finger.
705 * Pointer to next item in the list
707 struct Trail_Element *next;
710 * Pointer to prev item in the list
712 struct Trail_Element *prev;
715 * An element in this trail.
717 struct GNUNET_PeerIdentity peer;
721 * Information about an individual trail.
728 struct Trail_Element *trail_head;
733 struct Trail_Element *trail_tail;
736 * Unique identifier of this trail.
738 struct GNUNET_HashCode trail_id;
741 * Length of trail pointed
743 unsigned int trail_length;
746 * Is there a valid trail entry.
748 unsigned int is_present;
752 * An entry in finger_table
759 struct GNUNET_PeerIdentity finger_identity;
762 * Is any finger stored at this finger index.
764 unsigned int is_present;
767 * Index in finger peer map
769 uint32_t finger_table_index;
772 * Number of trails setup so far for this finger.
773 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
775 uint32_t trails_count;
778 * Array of trails to reach to this finger.
780 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
785 * Stores information about the peer which is closest to destination_finger_value.
786 * 'closest' can be either successor or predecessor depending on is_predecessor
792 * Destination finger value.
794 uint64_t destination_finger_value;
797 * Is finger_value a predecessor or any other finger.
799 unsigned int is_predecessor;
802 * Trail id to reach to peer.
803 * In case peer is my identity or friend, it is set to 0.
805 struct GNUNET_HashCode trail_id;
808 * Next destination. In case of friend and my_identity , it is same as next_hop
809 * In case of finger it is finger identity.
811 struct GNUNET_PeerIdentity best_known_destination;
814 * In case best_known_destination is a finger, then first friend in the trail
815 * to reach to it. In other case, same as best_known_destination.
817 struct GNUNET_PeerIdentity next_hop;
822 * Data structure to store the trail chosen to reach to finger.
824 struct Selected_Finger_Trail
827 * First friend in the trail to reach finger.
829 struct FriendInfo friend;
832 * Identifier of this trail.
834 struct GNUNET_HashCode trail_id;
837 * Total number of peers in this trail.
839 unsigned int trail_length;
843 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
844 * get our first friend.
846 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
849 * Task that sends verify successor message. This task is started when we get
850 * our successor for the first time.
852 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_task;
855 * Identity of this peer.
857 static struct GNUNET_PeerIdentity my_identity;
860 * Peer map of all the friends of a peer
862 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
865 * Array of all the fingers.
867 static struct FingerInfo finger_table [MAX_FINGERS];
872 static struct GNUNET_CORE_Handle *core_api;
875 * Handle for the statistics service.
877 extern struct GNUNET_STATISTICS_Handle *GDS_stats;
880 * The current finger index that we have want to find trail to. We start the
881 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
882 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
883 * we reset this index to 0.
885 static unsigned int current_search_finger_index;
888 * Should we store our topology predecessor and successor IDs into statistics?
890 unsigned int track_topology;
893 * Called when core is ready to send a message we asked for
894 * out to the destination.
896 * @param cls the 'struct FriendInfo' of the target friend
897 * @param size number of bytes available in buf
898 * @param buf where the callee should write the message
899 * @return number of bytes written to buf
902 core_transmit_notify (void *cls, size_t size, void *buf)
904 struct FriendInfo *peer = cls;
906 struct P2PPendingMessage *pending;
911 while ((NULL != (pending = peer->head)) &&
912 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
914 peer->pending_count--;
915 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
916 GNUNET_free (pending);
920 /* no messages pending */
926 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
927 GNUNET_CORE_PRIO_BEST_EFFORT,
928 GNUNET_TIME_absolute_get_remaining
929 (pending->timeout), &peer->id,
930 ntohs (pending->msg->size),
931 &core_transmit_notify, peer);
932 GNUNET_break (NULL != peer->th);
936 while ((NULL != (pending = peer->head)) &&
937 (size - off >= (msize = ntohs (pending->msg->size))))
939 /*GNUNET_STATISTICS_update (GDS_stats,
941 ("# Bytes transmitted to other peers"), msize,
943 memcpy (&cbuf[off], pending->msg, msize);
945 peer->pending_count--;
946 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
947 GNUNET_free (pending);
949 if (peer->head != NULL)
952 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
953 GNUNET_CORE_PRIO_BEST_EFFORT,
954 GNUNET_TIME_absolute_get_remaining
955 (pending->timeout), &peer->id, msize,
956 &core_transmit_notify, peer);
957 GNUNET_break (NULL != peer->th);
964 * Transmit all messages in the friend's message queue.
966 * @param peer message queue to process
969 process_friend_queue (struct FriendInfo *peer)
971 struct P2PPendingMessage *pending;
973 if (NULL == (pending = peer->head))
977 if (NULL != peer->th)
981 GNUNET_STATISTICS_update (GDS_stats,
983 ("# Bytes of bandwidth requested from core"),
984 ntohs (pending->msg->size), GNUNET_NO);
987 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
989 GNUNET_TIME_absolute_get_remaining
990 (pending->timeout), &peer->id,
991 ntohs (pending->msg->size),
992 &core_transmit_notify, peer);
993 GNUNET_break (NULL != peer->th);
998 * Construct a trail setup message and forward it to target_friend
999 * @param source_peer Peer which wants to setup the trail
1000 * @param ultimate_destination_finger_value Peer identity closest to this value
1001 * will be finger to @a source_peer
1002 * @param best_known_destination Best known destination (could be finger or friend)
1003 * which should get this message. In case it is
1004 * friend, then it is same as target_friend
1005 * @param target_friend Friend to which message is forwarded now.
1006 * @param trail_length Total number of peers in trail setup so far.
1007 * @param trail_peer_list Trail setup so far
1008 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1009 * @param trail_id Unique identifier for the trail we are trying to setup.
1010 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1011 * best_known_destination when its a finger. If not
1012 * used then set to 0.
1015 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1016 uint64_t ultimate_destination_finger_value,
1017 struct GNUNET_PeerIdentity best_known_destination,
1018 struct FriendInfo *target_friend,
1019 unsigned int trail_length,
1020 const struct GNUNET_PeerIdentity *trail_peer_list,
1021 unsigned int is_predecessor,
1022 struct GNUNET_HashCode trail_id,
1023 struct GNUNET_HashCode intermediate_trail_id)
1025 struct P2PPendingMessage *pending;
1026 struct PeerTrailSetupMessage *tsm;
1027 struct GNUNET_PeerIdentity *peer_list;
1030 msize = sizeof (struct PeerTrailSetupMessage) +
1031 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1033 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1039 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1041 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1045 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1046 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1047 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1048 pending->msg = &tsm->header;
1049 tsm->header.size = htons (msize);
1050 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1051 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1052 tsm->source_peer = source_peer;
1053 tsm->best_known_destination = best_known_destination;
1054 tsm->is_predecessor = htonl (is_predecessor);
1055 tsm->trail_id = trail_id;
1056 tsm->intermediate_trail_id = intermediate_trail_id;
1058 if (trail_length > 0)
1060 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1061 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1064 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1065 target_friend->pending_count++;
1066 process_friend_queue (target_friend);
1071 * Construct a trail setup result message and forward it to target friend.
1072 * @param querying_peer Peer which sent the trail setup request and should get
1074 * @param Finger Peer to which the trail has been setup to.
1075 * @param target_friend Friend to which this message should be forwarded.
1076 * @param trail_length Numbers of peers in the trail.
1077 * @param trail_peer_list Peers which are part of the trail from
1078 * querying_peer to Finger, NOT including them.
1079 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1080 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1082 * @param trail_id Unique identifier of the trail.
1085 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1086 struct GNUNET_PeerIdentity finger,
1087 struct FriendInfo *target_friend,
1088 unsigned int trail_length,
1089 const struct GNUNET_PeerIdentity *trail_peer_list,
1090 unsigned int is_predecessor,
1091 uint64_t ultimate_destination_finger_value,
1092 struct GNUNET_HashCode trail_id)
1094 struct P2PPendingMessage *pending;
1095 struct PeerTrailSetupResultMessage *tsrm;
1096 struct GNUNET_PeerIdentity *peer_list;
1099 msize = sizeof (struct PeerTrailSetupResultMessage) +
1100 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1102 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1108 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1110 GNUNET_STATISTICS_update (GDS_stats,
1111 gettext_noop ("# P2P messages dropped due to full queue"),
1115 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1116 pending->importance = 0;
1117 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1118 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1119 pending->msg = &tsrm->header;
1120 tsrm->header.size = htons (msize);
1121 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1122 tsrm->querying_peer = querying_peer;
1123 tsrm->finger_identity = finger;
1124 tsrm->is_predecessor = htonl (is_predecessor);
1125 tsrm->trail_id = trail_id;
1126 tsrm->ulitmate_destination_finger_value =
1127 GNUNET_htonll (ultimate_destination_finger_value);
1128 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1130 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1132 /* Send the message to chosen friend. */
1133 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1134 target_friend->pending_count++;
1135 process_friend_queue (target_friend);
1140 * Send trail rejection message to target friend
1141 * @param source_peer Peer which is trying to setup the trail.
1142 * @param ultimate_destination_finger_value Peer closest to this value will be
1143 * @a source_peer's finger
1144 * @param congested_peer Peer which sent this message as it is congested.
1145 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1146 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1147 * by congested_peer. This does NOT include @a source_peer
1148 * and congested_peer.
1149 * @param trail_length Total number of peers in trail_peer_list, NOT including
1150 * @a source_peer and @a congested_peer
1151 * @param trail_id Unique identifier of this trail.
1152 * @param congestion_timeout Duration given by congested peer as an estimate of
1153 * how long it may remain congested.
1156 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1157 uint64_t ultimate_destination_finger_value,
1158 struct GNUNET_PeerIdentity congested_peer,
1159 unsigned int is_predecessor,
1160 const struct GNUNET_PeerIdentity *trail_peer_list,
1161 unsigned int trail_length,
1162 struct GNUNET_HashCode trail_id,
1163 struct FriendInfo *target_friend,
1164 const struct GNUNET_TIME_Relative congestion_timeout)
1166 struct PeerTrailRejectionMessage *trm;
1167 struct P2PPendingMessage *pending;
1168 struct GNUNET_PeerIdentity *peer_list;
1171 msize = sizeof (struct PeerTrailRejectionMessage) +
1172 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1174 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1180 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1182 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1186 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1187 pending->importance = 0;
1188 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1189 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1190 pending->msg = &trm->header;
1191 trm->header.size = htons (msize);
1192 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1193 trm->source_peer = source_peer;
1194 trm->congested_peer = congested_peer;
1195 trm->congestion_time = congestion_timeout;
1196 trm->is_predecessor = htonl (is_predecessor);
1197 trm->trail_id = trail_id;
1198 trm->ultimate_destination_finger_value =
1199 GNUNET_htonll (ultimate_destination_finger_value);
1201 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1202 if (trail_length > 0)
1204 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1207 /* Send the message to chosen friend. */
1208 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1209 target_friend->pending_count++;
1210 process_friend_queue (target_friend);
1215 * Construct a verify successor message and forward it to target_friend.
1216 * @param source_peer Peer which wants to verify its successor.
1217 * @param successor Peer which is @a source_peer's current successor.
1218 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1219 * NOT including them.
1220 * @param trail List of peers which are part of trail to reach from @a source_peer
1221 * to @a successor, NOT including them.
1222 * @param trail_length Total number of peers in @a trail.
1223 * @param target_friend Next friend to get this message.
1226 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1227 struct GNUNET_PeerIdentity successor,
1228 struct GNUNET_HashCode trail_id,
1229 struct GNUNET_PeerIdentity *trail,
1230 unsigned int trail_length,
1231 struct FriendInfo *target_friend)
1233 struct PeerVerifySuccessorMessage *vsm;
1234 struct P2PPendingMessage *pending;
1235 struct GNUNET_PeerIdentity *peer_list;
1238 msize = sizeof (struct PeerVerifySuccessorMessage) +
1239 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1240 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1246 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1248 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1252 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1253 pending->importance = 0; /* FIXME */
1254 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1255 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1256 pending->msg = &vsm->header;
1257 vsm->header.size = htons (msize);
1258 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1259 vsm->source_peer = source_peer;
1260 vsm->successor = successor;
1261 vsm->trail_id = trail_id;
1262 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1263 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1265 /* Send the message to chosen friend. */
1266 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1267 target_friend->pending_count++;
1268 process_friend_queue (target_friend);
1273 * FIXME: In every function we pass target friend except for this one.
1274 * so, either change everything or this one. also, should se just store
1275 * the pointer to friend in routing table rather than gnunet_peeridentity.
1276 * if yes then we should keep friend info in.h andmake lot of changes.
1277 * Construct a trail teardown message and forward it to target friend.
1278 * @param trail_id Unique identifier of the trail.
1279 * @param trail_direction Direction of trail.
1280 * @param target_friend Friend to get this message.
1283 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1284 unsigned int trail_direction,
1285 struct GNUNET_PeerIdentity peer)
1287 struct PeerTrailTearDownMessage *ttdm;
1288 struct P2PPendingMessage *pending;
1289 struct FriendInfo *target_friend;
1292 msize = sizeof (struct PeerTrailTearDownMessage);
1294 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1300 /*FIXME:In what case friend can be null. ?*/
1301 if (NULL == (target_friend =
1302 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1305 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1307 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1311 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1312 pending->importance = 0; /* FIXME */
1313 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1314 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1315 pending->msg = &ttdm->header;
1316 ttdm->header.size = htons (msize);
1317 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1318 ttdm->trail_id = trail_id;
1319 ttdm->trail_direction = htonl (trail_direction);
1321 /* Send the message to chosen friend. */
1322 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1323 target_friend->pending_count++;
1324 process_friend_queue (target_friend);
1329 * Construct a verify successor result message and send it to target_friend
1330 * @param querying_peer Peer which sent the verify successor message.
1331 * @param source_successor Current_successor of @a querying_peer.
1332 * @param current_predecessor Current predecessor of @a successor. Could be same
1333 * or different from @a querying_peer.
1334 * @param trail_id Unique identifier of the trail from @a querying_peer to
1335 * @a successor, NOT including them.
1336 * @param trail List of peers which are part of trail from @a querying_peer to
1337 * @a successor, NOT including them.
1338 * @param trail_length Total number of peers in @a trail
1339 * @param trail_direction Direction in which we are sending the message. In this
1340 * case we are sending result from @a successor to @a querying_peer.
1341 * @param target_friend Next friend to get this message.
1344 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1345 struct GNUNET_PeerIdentity current_successor,
1346 struct GNUNET_PeerIdentity probable_successor,
1347 struct GNUNET_HashCode trail_id,
1348 const struct GNUNET_PeerIdentity *trail,
1349 unsigned int trail_length,
1350 enum GDS_ROUTING_trail_direction trail_direction,
1351 struct FriendInfo *target_friend)
1353 struct PeerVerifySuccessorResultMessage *vsmr;
1354 struct P2PPendingMessage *pending;
1355 struct GNUNET_PeerIdentity *peer_list;
1358 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1359 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1361 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1367 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1369 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1373 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1374 pending->importance = 0; /* FIXME */
1375 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1376 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1377 pending->msg = &vsmr->header;
1378 vsmr->header.size = htons (msize);
1379 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1380 vsmr->querying_peer = querying_peer;
1381 vsmr->current_successor = current_successor;
1382 vsmr->probable_successor = probable_successor;
1383 vsmr->trail_direction = htonl (trail_direction);
1384 vsmr->trail_id = trail_id;
1385 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[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 * Construct a notify new successor message and send it to target_friend
1397 * @param source_peer Peer which wants to notify to its new successor that it
1398 * could be its predecessor.
1399 * @param successor New successor of @a source_peer
1400 * @param successor_trail List of peers in Trail to reach from
1401 * @a source_peer to @a new_successor, NOT including
1403 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1404 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1405 * @param target_friend Next friend to get this message.
1408 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1409 struct GNUNET_PeerIdentity successor,
1410 const struct GNUNET_PeerIdentity *successor_trail,
1411 unsigned int successor_trail_length,
1412 struct GNUNET_HashCode succesor_trail_id,
1413 struct FriendInfo *target_friend)
1415 struct PeerNotifyNewSuccessorMessage *nsm;
1416 struct P2PPendingMessage *pending;
1417 struct GNUNET_PeerIdentity *peer_list;
1420 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1421 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1423 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1429 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1431 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1435 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1436 pending->importance = 0; /* FIXME */
1437 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1438 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1439 pending->msg = &nsm->header;
1440 nsm->header.size = htons (msize);
1441 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1442 nsm->new_successor = successor;
1443 nsm->source_peer = source_peer;
1444 nsm->trail_id = succesor_trail_id;
1446 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1447 memcpy (peer_list, successor_trail,
1448 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1450 /* Send the message to chosen friend. */
1451 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1452 target_friend->pending_count++;
1453 process_friend_queue (target_friend);
1458 * Construct an add_trail message and send it to target_friend
1459 * @param source_peer Source of the trail.
1460 * @param destination_peer Destination of the trail.
1461 * @param trail_id Unique identifier of the trail from
1462 * @a source_peer to @a destination_peer, NOT including the endpoints.
1463 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1464 * NOT including the endpoints.
1465 * @param trail_length Total number of peers in @a trail.
1466 * @param target_friend Next friend to get this message.
1469 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1470 struct GNUNET_PeerIdentity destination_peer,
1471 struct GNUNET_HashCode trail_id,
1472 const struct GNUNET_PeerIdentity *trail,
1473 unsigned int trail_length,
1474 struct FriendInfo *target_friend)
1476 struct PeerAddTrailMessage *adm;
1477 struct GNUNET_PeerIdentity *peer_list;
1478 struct P2PPendingMessage *pending;
1481 msize = sizeof (struct PeerAddTrailMessage) +
1482 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1484 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1490 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1492 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1496 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1497 pending->importance = 0; /* FIXME */
1498 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1499 adm = (struct PeerAddTrailMessage *) &pending[1];
1500 pending->msg = &adm->header;
1501 adm->header.size = htons (msize);
1502 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1503 adm->source_peer = source_peer;
1504 adm->destination_peer = destination_peer;
1505 adm->trail_id = trail_id;
1506 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1507 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1509 /* Send the message to chosen friend. */
1510 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1511 target_friend->pending_count++;
1512 process_friend_queue (target_friend);
1518 * Construct a trail compression message and send it to target_friend.
1519 * @param source_peer Source of the trail.
1520 * @param trail_id Unique identifier of trail.
1521 * @param first_friend First hop in compressed trail to reach from source to finger
1522 * @param target_friend Next friend to get this message.
1525 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1526 struct GNUNET_HashCode trail_id,
1527 struct GNUNET_PeerIdentity first_friend,
1528 struct FriendInfo *target_friend)
1530 struct P2PPendingMessage *pending;
1531 struct PeerTrailCompressionMessage *tcm;
1534 msize = sizeof (struct PeerTrailCompressionMessage);
1536 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1542 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1544 GNUNET_STATISTICS_update (GDS_stats,
1545 gettext_noop ("# P2P messages dropped due to full queue"),
1549 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1550 pending->importance = 0; /* FIXME */
1551 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1552 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1553 pending->msg = &tcm->header;
1554 tcm->header.size = htons (msize);
1555 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1556 tcm->source_peer = source_peer;
1557 tcm->new_first_friend = first_friend;
1558 tcm->trail_id = trail_id;
1560 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1561 target_friend->pending_count++;
1562 process_friend_queue (target_friend);
1568 * Search my location in trail. In case I am present more than once in the
1569 * trail (can happen during trail setup), then return my lowest index.
1570 * @param trail List of peers
1571 * @return my_index if found
1572 * -1 if no entry found.
1575 search_my_index (const struct GNUNET_PeerIdentity *trail,
1580 for (i = 0; i < trail_length; i++)
1582 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1591 * Check if the friend is congested or have reached maximum number of trails
1592 * it can be part of of.
1593 * @param friend Friend to be checked.
1594 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1595 * #GNUNET_YES if friend is either congested or have crossed threshold
1598 is_friend_congested (struct FriendInfo *friend)
1600 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1601 ((0 == GNUNET_TIME_absolute_get_remaining
1602 (friend->congestion_timestamp).rel_value_us)))
1610 * Select closest finger to value.
1611 * @param peer1 First peer
1612 * @param peer2 Second peer
1613 * @param value Value to be compare
1614 * @return Closest peer
1616 const static struct GNUNET_PeerIdentity *
1617 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1618 const struct GNUNET_PeerIdentity *peer2,
1621 uint64_t peer1_value;
1622 uint64_t peer2_value;
1624 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1625 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1626 peer1_value = GNUNET_ntohll (peer1_value);
1627 peer2_value = GNUNET_ntohll (peer2_value);
1629 if (peer1_value == value)
1634 if (peer2_value == value)
1639 if (peer2_value < peer1_value)
1641 if ((peer2_value < value) && (value < peer1_value))
1645 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1646 ((0 < value) && (value < peer2_value)))
1652 if (peer1_value < peer2_value)
1654 if ((peer1_value < value) && (value < peer2_value))
1658 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1659 ((0 < value) && (value < peer1_value)))
1669 * Select closest predecessor to value.
1670 * @param peer1 First peer
1671 * @param peer2 Second peer
1672 * @param value Value to be compare
1673 * @return Peer which precedes value in the network.
1675 const static struct GNUNET_PeerIdentity *
1676 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1677 const struct GNUNET_PeerIdentity *peer2,
1680 uint64_t peer1_value;
1681 uint64_t peer2_value;
1683 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1684 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1685 peer1_value = GNUNET_ntohll (peer1_value);
1686 peer2_value = GNUNET_ntohll (peer2_value);
1688 if (peer1_value == value)
1691 if (peer2_value == value)
1694 if (peer1_value < peer2_value)
1696 if ((peer1_value < value) && (value < peer2_value))
1700 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1701 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1707 if (peer2_value < peer1_value)
1709 if ((peer2_value < value) && (value < peer1_value))
1713 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1714 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1724 * This is a test function to print all the entries of friend table.
1727 test_friend_peermap_print ()
1729 struct FriendInfo *friend;
1730 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1731 struct GNUNET_PeerIdentity print_peer;
1732 struct GNUNET_PeerIdentity key_ret;
1735 print_peer = my_identity;
1736 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1737 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1739 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1741 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1743 (const void **)&friend))
1745 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1746 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1747 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1755 * This is a test function, to print all the entries of finger table.
1758 test_finger_table_print()
1760 struct FingerInfo *finger;
1761 struct GNUNET_PeerIdentity print_peer;
1762 //struct Trail *trail;
1766 print_peer = my_identity;
1767 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1768 for (i = 0; i < MAX_FINGERS; i++)
1770 finger = &finger_table[i];
1772 if (GNUNET_NO == finger->is_present)
1775 print_peer = finger->finger_identity;
1776 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1777 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1780 for (j = 0; j < finger->trails_count; j++)
1782 trail = &finger->trail_list[j];
1783 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1784 struct Trail_Element *element;
1785 element = trail->trail_head;
1786 for (k = 0; k < trail->trail_length; k++)
1788 print_peer = element->peer;
1789 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1790 element = element->next;
1799 * Select the closest peer among two peers (which should not be same)
1800 * with respect to value and finger_table_index
1801 * NOTE: peer1 != peer2
1802 * @param peer1 First peer
1803 * @param peer2 Second peer
1804 * @param value Value relative to which we find the closest
1805 * @param is_predecessor Is value a predecessor or any other finger.
1806 * @return Closest peer among two peers.
1808 const static struct GNUNET_PeerIdentity *
1809 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1810 const struct GNUNET_PeerIdentity *peer2,
1812 unsigned int is_predecessor)
1814 if (1 == is_predecessor)
1815 return select_closest_predecessor (peer1, peer2, value);
1817 return select_closest_finger (peer1, peer2, value);
1822 * Iterate over the list of all the trails of a finger. In case the first
1823 * friend to reach the finger has reached trail threshold or is congested,
1824 * then don't select it. In case there multiple available good trails to reach
1825 * to Finger, choose the one with shortest trail length.
1826 * Note: We use length as parameter. But we can use any other suitable parameter
1828 * @param finger Finger
1829 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1830 * and trail length. NULL in case none of the trails are free.
1832 static struct Selected_Finger_Trail *
1833 select_finger_trail (struct FingerInfo *finger)
1835 struct FriendInfo *friend;
1836 struct Trail *iterator;
1837 struct Selected_Finger_Trail *finger_trail;
1839 unsigned int flag = 0;
1842 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1843 GNUNET_assert (finger->trails_count > 0);
1845 for (i = 0; i < finger->trails_count; i++)
1847 iterator = &finger->trail_list[i];
1849 /* No trail stored at this index. */
1850 if (GNUNET_NO == iterator->is_present)
1853 GNUNET_assert (NULL !=
1855 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1856 &iterator->trail_head->peer)));
1858 /* First friend to reach trail is not free. */
1859 if (GNUNET_YES == is_friend_congested (friend))
1868 finger_trail->trail_length = iterator->trail_length;
1869 finger_trail->friend = *friend;
1870 finger_trail->trail_id = iterator->trail_id;
1872 else if (finger_trail->trail_length > iterator->trail_length)
1874 finger_trail->friend = *friend;
1875 finger_trail->trail_id = iterator->trail_id;
1876 finger_trail->trail_length = iterator->trail_length;
1880 /* All the first friend in all the trails to reach to finger are either
1881 congested or have crossed trail threshold. */
1882 if (j == finger->trails_count)
1885 return finger_trail;
1890 * Compare FINGER entry with current successor. If finger's first friend of all
1891 * its trail is not congested and has not crossed trail threshold, then check
1892 * if finger peer identity is closer to final_destination_finger_value than
1893 * current_successor. If yes then update current_successor.
1894 * @param current_successor[in/out]
1898 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1900 struct FingerInfo *finger;
1901 const struct GNUNET_PeerIdentity *closest_peer;
1902 struct Selected_Finger_Trail *finger_trail;
1905 /* Iterate over finger table. */
1906 for (i = 0; i < MAX_FINGERS; i++)
1908 finger = &finger_table[i];
1910 if (GNUNET_NO == finger->is_present)
1913 /* FIXME write correct comment here */
1914 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1915 ¤t_closest_peer->best_known_destination))
1918 /* If I am my own finger, then ignore this finger. */
1919 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1922 /* FIXME: I think a peer should not select itself as its own identity ever.
1923 But it does select. Find out why??*/
1929 /* If finger is a friend, then do nothing. As we have already checked
1930 * for each friend in compare_friend_and_current_successor(). */
1931 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1932 &finger->finger_identity)))
1937 closest_peer = select_closest_peer (&finger->finger_identity,
1938 ¤t_closest_peer->best_known_destination,
1939 current_closest_peer->destination_finger_value,
1940 current_closest_peer->is_predecessor);
1942 if (&finger->finger_identity == closest_peer)
1944 /* Choose one of the trail to reach to finger. */
1945 finger_trail = select_finger_trail (finger);
1947 /* In case no trail found, ignore this finger. */
1948 if (NULL == finger_trail)
1951 current_closest_peer->best_known_destination = finger->finger_identity;
1952 current_closest_peer->next_hop = finger_trail->friend.id;
1953 current_closest_peer->trail_id = finger_trail->trail_id;
1954 GNUNET_free(finger_trail);
1962 * Compare friend entry with current successor.
1963 * If friend identity and current_successor is same, then do nothing.
1964 * If friend is not congested and has not crossed trail threshold, then check
1965 * if friend peer identity is closer to final_destination_finger_value than
1966 * current_successor. If yes then update current_successor.
1967 * @param cls closure
1968 * @param key current public key
1969 * @param value struct Closest_Peer
1970 * @return #GNUNET_YES if we should continue to iterate,
1971 * #GNUNET_NO if not.
1974 compare_friend_and_current_closest_peer (void *cls,
1975 const struct GNUNET_PeerIdentity *key,
1978 struct FriendInfo *friend = value;
1979 struct Closest_Peer *current_closest_peer = cls;
1980 const struct GNUNET_PeerIdentity *closest_peer;
1982 /* Friend is either congested or has crossed threshold. */
1983 if (GNUNET_YES == is_friend_congested (friend))
1986 /* If current_closest_peer and friend identity are same, then do nothing.*/
1987 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
1988 ¤t_closest_peer->best_known_destination))
1994 closest_peer = select_closest_peer (&friend->id,
1995 ¤t_closest_peer->best_known_destination,
1996 current_closest_peer->destination_finger_value,
1997 current_closest_peer->is_predecessor);
1999 /* Is friend the closest successor? */
2000 if (&friend->id == closest_peer)
2002 current_closest_peer->best_known_destination = friend->id;
2003 current_closest_peer->next_hop = friend->id;
2011 * Initialize current_successor to my_identity.
2012 * @param my_identity My peer identity
2013 * @return Updated closest_peer
2015 static struct Closest_Peer
2016 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2017 uint64_t destination_finger_value,
2018 unsigned int is_predecessor)
2020 struct Closest_Peer current_closest_peer;
2022 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2023 current_closest_peer.destination_finger_value = destination_finger_value;
2024 current_closest_peer.is_predecessor = is_predecessor;
2025 current_closest_peer.next_hop = my_identity;
2026 current_closest_peer.best_known_destination = my_identity;
2028 return current_closest_peer;
2033 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2034 * peer. It could be because of the logic we wrote here. Verify if its correct.
2035 * If not then return immediate_successor.
2037 * Find the successor for destination_finger_value among my_identity, my
2038 * friends and my fingers. Don't consider friends or fingers which are either
2039 * congested or have crossed the threshold.
2040 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2042 * @param destination_finger_value Peer closest to this value will be the next successor.
2043 * @param is_predecessor Are we looking for predecessor or finger?
2044 * @return Successor It is never NULL, in case none of friend or finger is closest,
2045 * then we return my_identity.
2047 static struct Closest_Peer
2048 find_successor (uint64_t destination_finger_value,
2049 unsigned int is_predecessor)
2051 struct Closest_Peer current_closest_peer;
2053 /* Initialize current_successor to my_identity. */
2054 current_closest_peer = init_current_successor (my_identity,
2055 destination_finger_value,
2058 /* Compare each friend entry with current_successor and update current_successor
2059 * with friend if its closest. */
2062 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2063 &compare_friend_and_current_closest_peer,
2064 ¤t_closest_peer));
2066 /* Compare each finger entry with current_successor and update current_successor
2067 * with finger if its closest. */
2068 compare_finger_and_current_successor (¤t_closest_peer);
2070 return current_closest_peer;
2075 * Construct a Put message and send it to target_peer.
2076 * @param key Key for the content
2077 * @param block_type Type of the block
2078 * @param options Routing options
2079 * @param desired_replication_level Desired replication count
2080 * @param best_known_dest Peer to which this message should reach eventually,
2081 * as it is best known destination to me.
2082 * @param intermediate_trail_id Trail id in case
2083 * @param target_peer Peer to which this message will be forwarded.
2084 * @param hop_count Number of hops traversed so far.
2085 * @param put_path_length Total number of peers in @a put_path
2086 * @param put_path Number of peers traversed so far
2087 * @param expiration_time When does the content expire
2088 * @param data Content to store
2089 * @param data_size Size of content @a data in bytes
2092 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2093 enum GNUNET_BLOCK_Type block_type,
2094 enum GNUNET_DHT_RouteOption options,
2095 uint32_t desired_replication_level,
2096 struct GNUNET_PeerIdentity best_known_dest,
2097 struct GNUNET_HashCode intermediate_trail_id,
2098 struct GNUNET_PeerIdentity *target_peer,
2100 uint32_t put_path_length,
2101 struct GNUNET_PeerIdentity *put_path,
2102 struct GNUNET_TIME_Absolute expiration_time,
2103 const void *data, size_t data_size)
2105 struct PeerPutMessage *ppm;
2106 struct P2PPendingMessage *pending;
2107 struct FriendInfo *target_friend;
2108 struct GNUNET_PeerIdentity *pp;
2109 struct GNUNET_PeerIdentity next_hop;
2113 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2114 sizeof (struct PeerPutMessage);
2116 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2118 put_path_length = 0;
2119 msize = data_size + sizeof (struct PeerPutMessage);
2122 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2128 /* This is the first call made from clients file. So, we should search for the
2130 if (NULL == target_peer)
2133 struct Closest_Peer successor;
2135 memcpy (&key_value, key, sizeof (uint64_t));
2136 key_value = GNUNET_ntohll (key_value);
2138 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2139 best_known_dest = successor.best_known_destination;
2140 next_hop = successor.next_hop;
2141 intermediate_trail_id = successor.trail_id;
2143 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2145 /* I am the destination. */
2146 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2147 block_type,data_size,data);
2151 GNUNET_assert (NULL !=
2153 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2157 GNUNET_assert (NULL !=
2159 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2162 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2163 pending->timeout = expiration_time;
2164 ppm = (struct PeerPutMessage *) &pending[1];
2165 pending->msg = &ppm->header;
2166 ppm->header.size = htons (msize);
2167 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2168 ppm->options = htonl (options);
2169 ppm->block_type = htonl (block_type);
2170 ppm->hop_count = htonl (hop_count + 1);
2171 ppm->desired_replication_level = htonl (desired_replication_level);
2172 ppm->put_path_length = htonl (put_path_length);
2173 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2174 ppm->best_known_destination = best_known_dest;
2177 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2178 if (put_path_length != 0)
2180 memcpy (pp, put_path,
2181 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2183 memcpy (&pp[put_path_length], data, data_size);
2184 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2185 target_friend->pending_count++;
2186 process_friend_queue (target_friend);
2191 * Construct a Get message and send it to target_peer.
2192 * @param key Key for the content
2193 * @param block_type Type of the block
2194 * @param options Routing options
2195 * @param desired_replication_level Desired replication count
2196 * @param best_known_dest Peer which should get this message. Same as target peer
2197 * if best_known_dest is a friend else its a finger.
2198 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2199 * in case it is a finger else set to 0.
2200 * @param target_peer Peer to which this message will be forwarded.
2201 * @param hop_count Number of hops traversed so far.
2202 * @param data Content to store
2203 * @param data_size Size of content @a data in bytes
2204 * @param get_path_length Total number of peers in @a get_path
2205 * @param get_path Number of peers traversed so far
2208 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2209 enum GNUNET_BLOCK_Type block_type,
2210 enum GNUNET_DHT_RouteOption options,
2211 uint32_t desired_replication_level,
2212 struct GNUNET_PeerIdentity best_known_dest,
2213 struct GNUNET_HashCode intermediate_trail_id,
2214 struct GNUNET_PeerIdentity *target_peer,
2216 uint32_t get_path_length,
2217 struct GNUNET_PeerIdentity *get_path)
2219 struct PeerGetMessage *pgm;
2220 struct P2PPendingMessage *pending;
2221 struct FriendInfo *target_friend;
2222 struct GNUNET_PeerIdentity *gp;
2225 msize = sizeof (struct PeerGetMessage) +
2226 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2228 /* In this case we don't make get_path_length = 0, as we need get path to
2229 * return the message back to querying client. */
2230 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2236 /* This is the first time we got request from our own client file. */
2237 if (NULL == target_peer)
2240 struct Closest_Peer successor;
2242 memcpy (&key_value, key, sizeof (uint64_t));
2243 key_value = GNUNET_ntohll (key_value);
2244 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2246 best_known_dest = successor.best_known_destination;
2247 intermediate_trail_id = successor.trail_id;
2249 /* I am the destination. I have the data. */
2250 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2253 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2254 NULL, 0, 1, &my_identity, NULL,&my_identity);
2260 GNUNET_assert (NULL !=
2262 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2263 &successor.next_hop)));
2269 GNUNET_assert (NULL !=
2271 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); //FIXME: assertion fails.
2274 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2275 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2276 pending->importance = 0; /* FIXME */
2277 pgm = (struct PeerGetMessage *) &pending[1];
2278 pending->msg = &pgm->header;
2279 pgm->header.size = htons (msize);
2280 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2281 pgm->get_path_length = htonl (get_path_length);
2282 pgm->best_known_destination = best_known_dest;
2284 pgm->intermediate_trail_id = intermediate_trail_id;
2285 pgm->hop_count = htonl (hop_count + 1);
2286 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2288 if (get_path_length != 0)
2290 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2293 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2294 target_friend->pending_count++;
2295 process_friend_queue (target_friend);
2300 * Send the get result to requesting client.
2301 * @param key Key of the requested data.
2302 * @param type Block type
2303 * @param target_peer Next peer to forward the message to.
2304 * @param source_peer Peer which has the data for the key.
2305 * @param put_path_length Number of peers in @a put_path
2306 * @param put_path Path taken to put the data at its stored location.
2307 * @param get_path_length Number of peers in @a get_path
2308 * @param get_path Path taken to reach to the location of the key.
2309 * @param expiration When will this result expire?
2310 * @param data Payload to store
2311 * @param data_size Size of the @a data
2314 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2315 enum GNUNET_BLOCK_Type type,
2316 const struct GNUNET_PeerIdentity *target_peer,
2317 const struct GNUNET_PeerIdentity *source_peer,
2318 unsigned int put_path_length,
2319 const struct GNUNET_PeerIdentity *put_path,
2320 unsigned int get_path_length,
2321 const struct GNUNET_PeerIdentity *get_path,
2322 struct GNUNET_TIME_Absolute expiration,
2323 const void *data, size_t data_size)
2325 struct PeerGetResultMessage *get_result;
2326 struct GNUNET_PeerIdentity *paths;
2327 struct P2PPendingMessage *pending;
2328 struct FriendInfo *target_friend;
2329 int current_path_index;
2332 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2334 sizeof (struct PeerGetResultMessage);
2336 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2342 current_path_index = 0;
2343 if(get_path_length > 0)
2345 current_path_index = search_my_index(get_path, get_path_length);
2346 if (-1 == current_path_index)
2352 if (0 == current_path_index)
2354 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2355 get_path, put_path_length,
2356 put_path, type, data_size, data);
2360 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2361 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2362 pending->importance = 0;
2363 get_result = (struct PeerGetResultMessage *)&pending[1];
2364 pending->msg = &get_result->header;
2365 get_result->header.size = htons (msize);
2366 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2367 get_result->key = *key;
2368 get_result->querying_peer = *source_peer;
2369 get_result->expiration_time = expiration;
2370 get_result->get_path_length = htonl (get_path_length);
2371 get_result->put_path_length = htonl (put_path_length);
2372 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2373 memcpy (paths, put_path,
2374 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2375 memcpy (&paths[put_path_length], get_path,
2376 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2377 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2379 GNUNET_assert (NULL !=
2381 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2382 &get_path[current_path_index - 1])));
2383 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2384 target_friend->pending_count++;
2385 process_friend_queue (target_friend);
2390 * Randomly choose one of your friends (which is not congested and have not crossed
2391 * trail threshold) from the friend_peermap
2392 * @return Friend Randomly chosen friend.
2393 * NULL in case friend peermap is empty, or all the friends are either
2394 * congested or have crossed trail threshold.
2396 static struct FriendInfo *
2397 select_random_friend ()
2399 unsigned int current_size;
2402 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2403 struct GNUNET_PeerIdentity key_ret;
2404 struct FriendInfo *friend;
2406 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2409 if (0 == current_size)
2412 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2413 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2415 /* Iterate till you don't reach to index. */
2416 for (j = 0; j < index ; j++)
2417 GNUNET_assert (GNUNET_YES ==
2418 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2421 /* Reset the index in friend peermap to 0 as we reached to the end. */
2422 if (j == current_size)
2425 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2426 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2430 /* Get the friend stored at the index, j*/
2431 GNUNET_assert (GNUNET_YES ==
2432 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2434 (const void **)&friend));
2436 /* This friend is not congested and has not crossed trail threshold. */
2437 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2438 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2444 } while (j != index);
2446 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2452 * Compute 64 bit value of finger_identity corresponding to a finger index using
2454 * For all fingers, n.finger[i] = n + pow (2,i),
2455 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2456 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2457 * @param finger_index Index corresponding to which we calculate 64 bit value.
2458 * @return 64 bit value.
2461 compute_finger_identity_value (unsigned int finger_index)
2465 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2466 my_id64 = GNUNET_ntohll (my_id64);
2468 /* Are we looking for immediate predecessor? */
2469 if (PREDECESSOR_FINGER_ID == finger_index)
2470 return (my_id64 - 1);
2473 uint64_t add = (uint64_t)1 << finger_index;
2474 return (my_id64 + add);
2478 static struct GNUNET_TIME_Relative next_send_time;
2481 * Choose a random friend. Calculate the next finger identity to search,from
2482 * current_search_finger_index. Start looking for the trail to reach to
2483 * finger identity through this random friend.
2485 * @param cls closure for this task
2486 * @param tc the context under which the task is running
2489 send_find_finger_trail_message (void *cls,
2490 const struct GNUNET_SCHEDULER_TaskContext *tc)
2492 struct FriendInfo *target_friend;
2493 //struct GNUNET_TIME_Relative next_send_time;
2494 struct GNUNET_HashCode trail_id;
2495 struct GNUNET_HashCode intermediate_trail_id;
2496 unsigned int is_predecessor;
2497 uint64_t finger_id_value;
2499 /* Schedule another send_find_finger_trail_message task. */
2500 find_finger_trail_task =
2501 GNUNET_SCHEDULER_add_delayed (next_send_time,
2502 &send_find_finger_trail_message,
2505 /* No space in my routing table. (Source and destination peers also store entries
2506 * in their routing table). */
2507 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2511 target_friend = select_random_friend ();
2512 if (NULL == target_friend)
2517 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2519 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2524 /* Generate a unique trail id for trail we are trying to setup. */
2525 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2526 &trail_id, sizeof (trail_id));
2527 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2529 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2530 target_friend->id, target_friend, 0, NULL,
2531 is_predecessor, trail_id,
2532 intermediate_trail_id);
2537 * In case there are already maximum number of possible trails to reach to a
2538 * finger, then check if the new trail's length is lesser than any of the
2540 * If yes then replace that old trail by new trail.
2542 * Note: Here we are taking length as a parameter to choose the best possible
2543 * trail, but there could be other parameters also like:
2544 * 1. duration of existence of a trail - older the better.
2545 * 2. if the new trail is completely disjoint than the
2546 * other trails, then may be choosing it is better.
2548 * @param existing_finger
2549 * @param new_finger_trail
2550 * @param new_finger_trail_length
2551 * @param new_finger_trail_id
2554 select_and_replace_trail (struct FingerInfo *existing_finger,
2555 const struct GNUNET_PeerIdentity *new_trail,
2556 unsigned int new_trail_length,
2557 struct GNUNET_HashCode new_trail_id)
2559 struct Trail *trail_list_iterator;
2560 unsigned int largest_trail_length;
2561 unsigned int largest_trail_index;
2562 struct Trail_Element *trail_element;
2565 largest_trail_length = new_trail_length;
2566 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2568 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2570 for (i = 0; i < existing_finger->trails_count; i++)
2572 trail_list_iterator = &existing_finger->trail_list[i];
2573 if (trail_list_iterator->trail_length > largest_trail_length)
2575 largest_trail_length = trail_list_iterator->trail_length;
2576 largest_trail_index = i;
2580 /* New trail is not better than existing ones. Send trail teardown. */
2581 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2583 struct GNUNET_PeerIdentity next_hop;
2585 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2586 GDS_ROUTING_remove_trail (new_trail_id);
2587 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2588 GDS_ROUTING_SRC_TO_DEST,
2593 /* Send trail teardown message across the replaced trail. */
2594 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2595 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2596 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2597 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2598 GDS_ROUTING_SRC_TO_DEST,
2599 replace_trail->trail_head->peer);
2600 /* Free the trail. */
2601 while (NULL != (trail_element = replace_trail->trail_head))
2603 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2604 replace_trail->trail_tail, trail_element);
2605 GNUNET_free_non_null (trail_element);
2608 /* Add new trial at that location. */
2609 replace_trail->is_present = GNUNET_YES;
2610 replace_trail->trail_length = new_trail_length;
2611 replace_trail->trail_id = new_trail_id;
2612 //FIXME: Do we need to add pointers for head and tail.
2614 while (i < new_trail_length)
2616 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2617 element->peer = new_trail[i];
2619 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2620 replace_trail->trail_tail,
2627 * Check if the new trail to reach to finger is unique or do we already have
2628 * such a trail present for finger.
2629 * @param existing_finger Finger identity
2630 * @param new_trail New trail to reach @a existing_finger
2631 * @param trail_length Total number of peers in new_trail.
2632 * @return #GNUNET_YES if the new trail is unique
2633 * #GNUNET_NO if same trail is already present.
2636 is_new_trail_unique (struct FingerInfo *existing_finger,
2637 const struct GNUNET_PeerIdentity *new_trail,
2638 unsigned int trail_length)
2640 struct Trail *trail_list_iterator;
2641 struct Trail_Element *trail_element;
2644 int trail_unique = GNUNET_NO;
2646 GNUNET_assert (existing_finger->trails_count > 0);
2648 /* Iterate over list of trails. */
2649 for (i = 0; i < existing_finger->trails_count; i++)
2651 trail_list_iterator = &existing_finger->trail_list[i];
2652 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2654 /* New trail and existing trail length are not same. */
2655 if (trail_list_iterator->trail_length != trail_length)
2657 trail_unique = GNUNET_YES;
2661 trail_element = trail_list_iterator->trail_head;
2662 for (j = 0; j < trail_list_iterator->trail_length; j++)
2664 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2665 &trail_element->peer))
2667 trail_unique = GNUNET_YES;
2670 trail_element = trail_element->next;
2673 trail_unique = GNUNET_NO;
2676 return trail_unique;
2681 * Add a new trail to existing finger. This function is called only when finger
2682 * is not my own identity or a friend.
2683 * @param existing_finger Finger
2684 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2685 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2686 * @param new_finger_trail_id Unique identifier of the trail.
2689 add_new_trail (struct FingerInfo *existing_finger,
2690 const struct GNUNET_PeerIdentity *new_trail,
2691 unsigned int new_trail_length,
2692 struct GNUNET_HashCode new_trail_id)
2694 struct Trail *trail_list_iterator;
2695 struct FriendInfo *first_friend;
2698 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2704 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2705 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2706 trail_list_iterator->trail_id = new_trail_id;
2707 trail_list_iterator->trail_length = new_trail_length;
2708 existing_finger->trails_count++;
2709 trail_list_iterator->is_present = GNUNET_YES;
2711 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2712 &existing_finger->finger_identity)));
2713 /* If finger is a friend then we never call this function. */
2714 GNUNET_assert (new_trail_length > 0);
2716 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2718 first_friend->trails_count++;
2720 for (i = 0; i < new_trail_length; i++)
2722 struct Trail_Element *element;
2724 element = GNUNET_new (struct Trail_Element);
2725 element->peer = new_trail[i];
2726 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2727 trail_list_iterator->trail_tail,
2730 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2736 * FIXME Check if this function is called for opposite direction if yes then
2737 * take it as parameter.
2738 * Get the next hop to send trail teardown message from routing table and
2739 * then delete the entry from routing table. Send trail teardown message for a
2740 * specific trail of a finger.
2741 * @param finger Finger whose trail is to be removed.
2742 * @param trail List of peers in trail from me to a finger, NOT including
2746 send_trail_teardown (struct FingerInfo *finger,
2747 struct Trail *trail)
2749 struct FriendInfo *friend;
2750 struct GNUNET_PeerIdentity *next_hop;
2752 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2753 GDS_ROUTING_SRC_TO_DEST);
2755 if (NULL == next_hop)
2760 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2763 GNUNET_assert (trail->is_present == GNUNET_YES);
2765 /* Finger is not a friend. */
2766 if (trail->trail_length > 0)
2768 GNUNET_assert (NULL != (friend =
2769 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2770 &trail->trail_head->peer)));
2774 GNUNET_assert (NULL != (friend =
2775 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2776 &finger->finger_identity)));
2779 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2780 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2781 friend->trails_count--;
2782 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2783 GDS_ROUTING_SRC_TO_DEST,
2789 * Send trail teardown message across all the trails to reach to finger.
2790 * @param finger Finger whose all the trail should be freed.
2793 send_all_finger_trails_teardown (struct FingerInfo *finger)
2797 for (i = 0; i < finger->trails_count; i++)
2799 struct Trail *trail;
2801 trail = &finger->trail_list[i];
2802 GNUNET_assert (trail->is_present == GNUNET_YES);
2803 send_trail_teardown (finger, trail);
2804 trail->is_present = GNUNET_NO;
2810 * Free a specific trail
2811 * @param trail List of peers to be freed.
2814 free_trail (struct Trail *trail)
2816 struct Trail_Element *trail_element;
2818 while (NULL != (trail_element = trail->trail_head))
2820 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2823 GNUNET_free_non_null (trail_element);
2825 trail->trail_head = NULL;
2826 trail->trail_tail = NULL;
2831 * Free finger and its trail.
2832 * @param finger Finger to be freed.
2835 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2837 struct Trail *trail;
2840 /* Free all the trails to reach to finger */
2841 for (i = 0; i < finger->trails_count; i++)
2843 trail = &finger->trail_list[i];
2844 //FIXME: Check if there are any missing entry in this list because of
2845 // how we insert. If not then no need of this check.
2846 if (GNUNET_NO == trail->is_present)
2849 if (trail->trail_length > 0)
2853 trail->is_present = GNUNET_NO;
2856 finger->is_present = GNUNET_NO;
2857 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2862 * Add a new entry in finger table at finger_table_index.
2863 * In case I am my own finger, then we don't have a trail. In case of a friend,
2864 * we have a trail with unique id and '0' trail length.
2865 * In case a finger is a friend, then increment the trails count of the friend.
2866 * @param finger_identity Peer Identity of new finger
2867 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2868 * @param finger_trail_length Total number of peers in @a finger_trail.
2869 * @param trail_id Unique identifier of the trail.
2870 * @param finger_table_index Index in finger table.
2873 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2874 const struct GNUNET_PeerIdentity *finger_trail,
2875 unsigned int finger_trail_length,
2876 struct GNUNET_HashCode trail_id,
2877 unsigned int finger_table_index)
2879 struct FingerInfo *new_entry;
2880 struct FriendInfo *first_trail_hop;
2881 struct Trail *trail;
2884 new_entry = GNUNET_new (struct FingerInfo);
2885 new_entry->finger_identity = finger_identity;
2886 new_entry->finger_table_index = finger_table_index;
2887 new_entry->is_present = GNUNET_YES;
2889 /* If the new entry is my own identity. */
2890 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2893 new_entry->trails_count = 0;
2894 finger_table[finger_table_index] = *new_entry;
2895 GNUNET_free (new_entry);
2899 /* If finger is a friend, then we don't actually have a trail.
2900 * Just a trail id */
2901 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2904 new_entry->trail_list[0].trail_id = trail_id;
2905 new_entry->trails_count = 1;
2906 new_entry->trail_list[0].is_present = GNUNET_YES;
2907 new_entry->trail_list[0].trail_length = 0;
2908 new_entry->trail_list[0].trail_head = NULL;
2909 new_entry->trail_list[0].trail_tail = NULL;
2910 finger_table[finger_table_index] = *new_entry;
2911 GNUNET_assert (NULL !=
2913 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2914 &finger_identity)));
2916 first_trail_hop->trails_count++;
2917 GNUNET_free (new_entry);
2921 GNUNET_assert (NULL !=
2923 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2924 &finger_trail[0])));
2925 new_entry->trails_count = 1;
2926 first_trail_hop->trails_count++;
2928 /* Copy the finger trail into trail. */
2929 trail = GNUNET_new (struct Trail);
2930 while (i < finger_trail_length)
2932 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2934 element->next = NULL;
2935 element->prev = NULL;
2936 element->peer = finger_trail[i];
2937 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2943 /* Add trail to trail list. */
2944 new_entry->trail_list[0].trail_head = trail->trail_head;
2945 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2946 new_entry->trail_list[0].trail_length = finger_trail_length;
2947 new_entry->trail_list[0].trail_id = trail_id;
2948 new_entry->trail_list[0].is_present = GNUNET_YES;
2949 finger_table[finger_table_index] = *new_entry;
2950 GNUNET_free (new_entry);
2956 * Scan the trail to check if there is any other friend in the trail other than
2957 * first hop. If yes then shortcut the trail, send trail compression message to
2958 * peers which are no longer part of trail and send back the updated trail
2959 * and trail_length to calling function.
2960 * @param finger_identity Finger whose trail we will scan.
2961 * @param finger_trail [in, out] Trail to reach from source to finger,
2962 * @param finger_trail_length Total number of peers in original finger_trail.
2963 * @param finger_trail_id Unique identifier of the finger trail.
2964 * @return updated trail length in case we shortcut the trail, else original
2967 static struct GNUNET_PeerIdentity *
2968 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2969 const struct GNUNET_PeerIdentity *trail,
2970 unsigned int trail_length,
2971 struct GNUNET_HashCode trail_id,
2972 int *new_trail_length)
2974 struct FriendInfo *target_friend;
2975 struct GNUNET_PeerIdentity *new_trail;
2978 /* I am my own finger. */
2979 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2981 *new_trail_length = 0;
2985 if (0 == trail_length)
2987 *new_trail_length = 0;
2991 /* If finger identity is a friend. */
2992 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
2994 *new_trail_length = 0;
2996 /* If there is trail to reach this finger/friend */
2997 if (trail_length > 0)
2999 /* Finger is your first friend. */
3000 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3001 GNUNET_assert (NULL !=
3003 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3007 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3008 trail_id, finger_identity,
3014 /* For other cases, when its neither a friend nor my own identity.*/
3015 for (i = trail_length - 1; i > 0; i--)
3017 /* If the element at this index in trail is a friend. */
3018 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3020 struct FriendInfo *target_friend;
3023 GNUNET_assert (NULL !=
3025 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3027 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3028 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3033 /* Copy the trail from index i to index (trail_length -1) into a new trail
3034 * and update new trail length */
3035 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3036 while (i < trail_length)
3038 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3042 *new_trail_length = j+1;
3047 /* If we did not compress the trail, return the original trail back.*/
3048 *new_trail_length = trail_length;
3049 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3050 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3055 /* Store the successor for path tracking */
3056 if (track_topology && (NULL != GDS_stats))
3062 my_id_str = GNUNET_strdup (GNUNET_i2s (&my_identity));
3063 succ_id_str = GNUNET_strdup (GNUNET_i2s
3064 (&successor->finger_identity));
3065 GNUNET_asprintf (&key, "XDHT:0:%.4s:%.4s", my_id_str, succ_id_str);
3066 GNUNET_free (my_id_str);
3067 GNUNET_free (succ_id_str);
3068 GNUNET_STATISTICS_update (GDS_stats, "key", 1, 0);
3074 * Periodic task to verify current successor. There can be multiple trails to reach
3075 * to successor, choose the shortest one and send verify successor message
3076 * across that trail.
3077 * @param cls closure for this task
3078 * @param tc the context under which the task is running
3081 send_verify_successor_message (void *cls,
3082 const struct GNUNET_SCHEDULER_TaskContext *tc)
3084 struct FriendInfo *target_friend;
3085 struct GNUNET_HashCode trail_id;
3087 struct GNUNET_TIME_Relative next_send_time;
3088 struct Trail *trail;
3089 struct Trail_Element *element;
3090 unsigned int trail_length;
3092 struct FingerInfo *successor;
3094 /* Schedule another send_find_finger_trail_message task. */
3095 next_send_time.rel_value_us =
3096 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3097 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3098 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3099 send_verify_successor_task =
3100 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3103 successor = &finger_table[0];
3104 for (i = 0; i < successor->trails_count; i++)
3106 trail = &successor->trail_list[i];
3107 if(GNUNET_YES == trail->is_present)
3111 if (i == successor->trails_count)
3114 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3115 &successor->finger_identity));
3117 /* Trail stored at this index. */
3118 GNUNET_assert (GNUNET_YES == trail->is_present);
3120 trail_id = trail->trail_id;
3121 trail_length = trail->trail_length;
3123 if (trail_length > 0)
3125 /* Copy the trail into peer list. */
3126 struct GNUNET_PeerIdentity peer_list[trail_length];
3128 element = trail->trail_head;
3129 while (j < trail_length)
3131 peer_list[j] = element->peer;
3132 element = element->next;
3136 GNUNET_assert (NULL != (target_friend =
3137 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3139 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3140 successor->finger_identity,
3141 trail_id, peer_list, trail_length,
3147 GNUNET_assert (NULL != (target_friend =
3148 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3149 &successor->finger_identity)));
3150 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3151 successor->finger_identity,
3160 * Update the current search finger index.
3162 * FIXME document parameters!
3165 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3166 unsigned int finger_table_index)
3168 struct FingerInfo *successor;
3170 /* FIXME correct this: only move current index periodically */
3171 if (finger_table_index != current_search_finger_index)
3174 successor = &finger_table[0];
3175 GNUNET_assert (GNUNET_YES == successor->is_present);
3177 /* We were looking for immediate successor. */
3178 if (0 == current_search_finger_index)
3180 /* Start looking for immediate predecessor. */
3181 current_search_finger_index = PREDECESSOR_FINGER_ID;
3183 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3185 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3186 send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3192 current_search_finger_index = current_search_finger_index - 1;
3198 * Get the least significant bit set in val.
3201 * @return Position of first bit set, 65 in case of error.
3204 find_set_bit (uint64_t val)
3224 return 65; /* Some other bit was set to 1 as well. */
3231 * Calculate finger_table_index from initial 64 bit finger identity value that
3232 * we send in trail setup message.
3233 * @param ultimate_destination_finger_value Value that we calculated from our
3234 * identity and finger_table_index.
3235 * @param is_predecessor Is the entry for predecessor or not?
3236 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3237 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3240 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3241 unsigned int is_predecessor)
3245 unsigned int finger_table_index;
3247 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3248 my_id64 = GNUNET_ntohll (my_id64);
3250 /* Is this a predecessor finger? */
3251 if (1 == is_predecessor)
3253 diff = my_id64 - ultimate_destination_finger_value;
3255 finger_table_index = PREDECESSOR_FINGER_ID;
3257 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3262 diff = ultimate_destination_finger_value - my_id64;
3263 finger_table_index = find_set_bit (diff);
3265 return finger_table_index;
3270 * Remove finger and its associated data structures from finger table.
3271 * @param finger Finger to be removed.
3274 remove_existing_finger (struct FingerInfo *existing_finger,
3275 unsigned int finger_table_index)
3277 struct FingerInfo *finger;
3279 finger = &finger_table[finger_table_index];
3280 GNUNET_assert (GNUNET_YES == finger->is_present);
3282 /* If I am my own finger, then we have no trails. */
3283 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3286 finger->is_present = GNUNET_NO;
3287 memset ((void *)&finger_table[finger_table_index], 0,
3288 sizeof (finger_table[finger_table_index]));
3292 /* For all other fingers, send trail teardown across all the trails to reach
3293 finger, and free the finger. */
3294 send_all_finger_trails_teardown (finger);
3295 free_finger (finger, finger_table_index);
3301 * Check if there is already an entry in finger_table at finger_table_index.
3302 * We get the finger_table_index from 64bit finger value we got from the network.
3303 * -- If yes, then select the closest finger.
3304 * -- If new and existing finger are same, then check if you can store more
3306 * -- If yes then add trail, else keep the best trails to reach to the
3308 * -- If the new finger is closest, remove the existing entry, send trail
3309 * teardown message across all the trails to reach the existing entry.
3310 * Add the new finger.
3311 * -- If new and existing finger are different, and existing finger is closest
3313 * -- Update current_search_finger_index.
3314 * @param finger_identity Peer Identity of new finger
3315 * @param finger_trail Trail to reach the new finger
3316 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3317 * @param is_predecessor Is this entry for predecessor in finger_table?
3318 * @param finger_value 64 bit value of finger identity that we got from network.
3319 * @param finger_trail_id Unique identifier of @finger_trail.
3322 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3323 const struct GNUNET_PeerIdentity *finger_trail,
3324 unsigned int finger_trail_length,
3325 unsigned int is_predecessor,
3326 uint64_t finger_value,
3327 struct GNUNET_HashCode finger_trail_id)
3329 struct FingerInfo *existing_finger;
3330 const struct GNUNET_PeerIdentity *closest_peer;
3331 struct FingerInfo *successor;
3332 int updated_finger_trail_length;
3333 unsigned int finger_table_index;
3335 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3336 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3338 /* Invalid finger_table_index. */
3339 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3341 GNUNET_break_op (0);
3345 /* New entry same as successor. */
3346 if ((0 != finger_table_index) &&
3347 (PREDECESSOR_FINGER_ID != finger_table_index))
3349 successor = &finger_table[0];
3350 if (GNUNET_NO == successor->is_present)
3352 GNUNET_break_op (0);
3355 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3356 &successor->finger_identity))
3358 current_search_finger_index = 0;
3359 /* We slow down the find_finger_trail_task as we have completed the circle. */
3360 next_send_time = GNUNET_TIME_STD_BACKOFF(next_send_time);
3365 struct FingerInfo prev_finger;
3366 prev_finger = finger_table[finger_table_index - 1];
3367 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3368 &prev_finger.finger_identity))
3370 current_search_finger_index--;
3375 existing_finger = &finger_table[finger_table_index];
3377 /* No entry present in finger_table for given finger map index. */
3378 if (GNUNET_NO == existing_finger->is_present)
3380 struct GNUNET_PeerIdentity *updated_trail;
3382 /* Shorten the trail if possible. */
3383 updated_finger_trail_length = finger_trail_length;
3384 updated_trail = scan_and_compress_trail (finger_identity, finger_trail,
3385 finger_trail_length,
3387 &updated_finger_trail_length);
3389 add_new_finger (finger_identity, updated_trail,
3390 updated_finger_trail_length,
3391 finger_trail_id, finger_table_index);
3392 GNUNET_free_non_null(updated_trail);
3393 update_current_search_finger_index (finger_identity,
3394 finger_table_index);
3399 /* If existing entry and finger identity are not same. */
3400 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3403 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3408 /* If the new finger is the closest peer. */
3409 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3411 struct GNUNET_PeerIdentity *updated_trail;
3412 /* Shorten the trail if possible. */
3413 updated_finger_trail_length = finger_trail_length;
3415 scan_and_compress_trail (finger_identity, finger_trail,
3416 finger_trail_length, finger_trail_id,
3417 &updated_finger_trail_length);
3418 remove_existing_finger (existing_finger, finger_table_index);
3419 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3420 finger_trail_id, finger_table_index);
3421 GNUNET_free_non_null((struct GNUNET_PeerIdentity *)updated_trail);
3425 /* Existing finger is the closest one. We need to send trail teardown
3426 across the trail setup in routing table of all the peers. */
3427 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3429 if (finger_trail_length > 0)
3430 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3431 GDS_ROUTING_SRC_TO_DEST,
3434 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3435 GDS_ROUTING_SRC_TO_DEST,
3442 /* If both new and existing entry are same as my_identity, then do nothing. */
3443 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3448 /* If the existing finger is not a friend. */
3450 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3451 &existing_finger->finger_identity))
3453 struct GNUNET_PeerIdentity *updated_trail;
3455 /* Shorten the trail if possible. */
3456 updated_finger_trail_length = finger_trail_length;
3458 scan_and_compress_trail (finger_identity, finger_trail,
3459 finger_trail_length, finger_trail_id,
3460 &updated_finger_trail_length);
3461 /* If there is space to store more trails. */
3462 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3463 add_new_trail (existing_finger, updated_trail,
3464 updated_finger_trail_length, finger_trail_id);
3466 select_and_replace_trail (existing_finger, updated_trail,
3467 updated_finger_trail_length, finger_trail_id);
3471 update_current_search_finger_index (finger_identity, finger_table_index);
3476 * Core handler for P2P put messages.
3477 * @param cls closure
3478 * @param peer sender of the request
3479 * @param message message
3480 * @return #GNUNET_OK to keep the connection open,
3481 * #GNUNET_SYSERR to close it (signal serious error)
3484 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3485 const struct GNUNET_MessageHeader *message)
3487 struct PeerPutMessage *put;
3488 struct GNUNET_PeerIdentity *put_path;
3489 struct GNUNET_PeerIdentity best_known_dest;
3490 struct GNUNET_HashCode intermediate_trail_id;
3491 struct GNUNET_PeerIdentity *next_hop;
3492 enum GNUNET_DHT_RouteOption options;
3493 struct GNUNET_HashCode test_key;
3497 size_t payload_size;
3500 msize = ntohs (message->size);
3501 if (msize < sizeof (struct PeerPutMessage))
3503 GNUNET_break_op (0);
3507 put = (struct PeerPutMessage *) message;
3508 putlen = ntohl (put->put_path_length);
3512 sizeof (struct PeerPutMessage) +
3513 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3515 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3517 GNUNET_break_op (0);
3521 best_known_dest = put->best_known_destination;
3522 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3523 payload = &put_path[putlen];
3524 options = ntohl (put->options);
3525 intermediate_trail_id = put->intermediate_trail_id;
3527 payload_size = msize - (sizeof (struct PeerPutMessage) +
3528 putlen * sizeof (struct GNUNET_PeerIdentity));
3530 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3531 payload, payload_size, &test_key))
3534 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3536 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3537 GNUNET_break_op (0);
3538 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3539 "PUT with key `%s' for block with key %s\n",
3540 put_s, GNUNET_h2s_full (&test_key));
3541 GNUNET_free (put_s);
3546 GNUNET_break_op (0);
3549 /* cannot verify, good luck */
3553 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3555 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3556 ntohl (put->block_type),
3558 NULL, 0, /* bloom filer */
3559 NULL, 0, /* xquery */
3560 payload, payload_size))
3562 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3563 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3566 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3567 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3568 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3569 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3570 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3571 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3573 GNUNET_break_op (0);
3578 /* extend 'put path' by sender */
3579 struct GNUNET_PeerIdentity pp[putlen + 1];
3580 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3582 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3589 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3590 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3592 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3593 GDS_ROUTING_SRC_TO_DEST);
3594 if (NULL == next_hop)
3596 GNUNET_STATISTICS_update (GDS_stats,
3597 gettext_noop ("# Next hop to forward the packet not found "
3598 "trail setup request, packet dropped."),
3600 return GNUNET_SYSERR;
3605 struct Closest_Peer successor;
3606 key_value = GNUNET_ntohll (key_value);
3607 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3608 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3609 *next_hop = successor.next_hop;
3610 intermediate_trail_id = successor.trail_id;
3611 best_known_dest = successor.best_known_destination;
3614 GDS_CLIENTS_process_put (options,
3615 ntohl (put->block_type),
3616 ntohl (put->hop_count),
3617 ntohl (put->desired_replication_level),
3619 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3624 /* I am the final destination */
3625 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3627 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3628 &(put->key),putlen, pp, ntohl (put->block_type),
3629 payload_size, payload);
3633 GDS_NEIGHBOURS_send_put (&put->key,
3634 ntohl (put->block_type),ntohl (put->options),
3635 ntohl (put->desired_replication_level),
3636 best_known_dest, intermediate_trail_id, next_hop,
3637 ntohl (put->hop_count), putlen, pp,
3638 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3639 payload, payload_size);
3646 * Core handler for p2p get requests.
3648 * @param cls closure
3649 * @param peer sender of the request
3650 * @param message message
3651 * @return #GNUNET_OK to keep the connection open,
3652 * #GNUNET_SYSERR to close it (signal serious error)
3655 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3656 const struct GNUNET_MessageHeader *message)
3658 const struct PeerGetMessage *get;
3659 const struct GNUNET_PeerIdentity *get_path;
3660 struct GNUNET_PeerIdentity best_known_dest;
3661 struct GNUNET_HashCode intermediate_trail_id;
3662 struct GNUNET_PeerIdentity *next_hop;
3663 uint32_t get_length;
3667 msize = ntohs (message->size);
3668 if (msize < sizeof (struct PeerGetMessage))
3670 GNUNET_break_op (0);
3674 get = (const struct PeerGetMessage *)message;
3675 get_length = ntohl (get->get_path_length);
3676 best_known_dest = get->best_known_destination;
3677 intermediate_trail_id = get->intermediate_trail_id;
3678 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3681 sizeof (struct PeerGetMessage) +
3682 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3684 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3686 GNUNET_break_op (0);
3690 /* Add sender to get path */
3691 struct GNUNET_PeerIdentity gp[get_length + 1];
3693 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3694 gp[get_length] = *peer;
3695 get_length = get_length + 1;
3697 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3698 key_value = GNUNET_ntohll (key_value);
3700 /* I am not the final destination. I am part of trail to reach final dest. */
3701 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3703 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3704 GDS_ROUTING_SRC_TO_DEST);
3705 if (NULL == next_hop)
3707 GNUNET_STATISTICS_update (GDS_stats,
3708 gettext_noop ("# Next hop to forward the packet not found "
3709 "GET request, packet dropped."),
3711 return GNUNET_SYSERR;
3716 struct Closest_Peer successor;
3718 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3719 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3720 *next_hop = successor.next_hop;
3721 best_known_dest = successor.best_known_destination;
3722 intermediate_trail_id = successor.trail_id;
3725 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3726 get->desired_replication_level, get->get_path_length,
3728 /* I am the final destination. */
3729 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3731 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3733 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3734 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3735 get_length = get_length + 1;
3737 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3738 get_length, final_get_path,
3739 &final_get_path[get_length-2], &my_identity);
3743 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3744 get->desired_replication_level, best_known_dest,
3745 intermediate_trail_id, next_hop, 0,
3753 * Core handler for get result
3754 * @param cls closure
3755 * @param peer sender of the request
3756 * @param message message
3757 * @return #GNUNET_OK to keep the connection open,
3758 * #GNUNET_SYSERR to close it (signal serious error)
3761 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3762 const struct GNUNET_MessageHeader *message)
3764 const struct PeerGetResultMessage *get_result;
3765 const struct GNUNET_PeerIdentity *get_path;
3766 const struct GNUNET_PeerIdentity *put_path;
3767 const void *payload;
3768 size_t payload_size;
3770 unsigned int getlen;
3771 unsigned int putlen;
3772 int current_path_index;
3774 msize = ntohs (message->size);
3775 if (msize < sizeof (struct PeerGetResultMessage))
3777 GNUNET_break_op (0);
3781 get_result = (const struct PeerGetResultMessage *)message;
3782 getlen = ntohl (get_result->get_path_length);
3783 putlen = ntohl (get_result->put_path_length);
3786 sizeof (struct PeerGetResultMessage) +
3787 getlen * sizeof (struct GNUNET_PeerIdentity) +
3788 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3790 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3792 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3794 GNUNET_break_op (0);
3798 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3799 get_path = &put_path[putlen];
3800 payload = (const void *) &get_path[getlen];
3801 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3802 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3804 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3806 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3807 getlen, get_path, putlen,
3808 put_path, get_result->type, payload_size, payload);
3813 current_path_index = search_my_index (get_path, getlen);
3814 if (-1 == current_path_index )
3817 return GNUNET_SYSERR;
3819 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3820 &get_path[current_path_index - 1],
3821 &(get_result->querying_peer), putlen, put_path,
3822 getlen, get_path, get_result->expiration_time,
3823 payload, payload_size);
3826 return GNUNET_SYSERR;
3831 * Find the next hop to pass trail setup message. First find the local best known
3832 * hop from your own identity, friends and finger. If you were part of trail,
3833 * then get the next hop from routing table. Compare next_hop from routing table
3834 * and local best known hop, and return the closest one to final_dest_finger_val
3835 * @param final_dest_finger_val 64 bit value of finger identity
3836 * @param intermediate_trail_id If you are part of trail to reach to some other
3837 * finger, then it is the trail id to reach to
3838 * that finger, else set to 0.
3839 * @param is_predecessor Are we looking for closest successor or predecessor.
3840 * @param current_dest In case you are part of trail, then finger to which
3841 * we should forward the message. Else my own identity
3842 * @return Closest Peer for @a final_dest_finger_val
3844 static struct Closest_Peer
3845 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3846 struct GNUNET_HashCode intermediate_trail_id,
3847 unsigned int is_predecessor,
3848 struct GNUNET_PeerIdentity prev_hop,
3849 struct GNUNET_PeerIdentity source,
3850 struct GNUNET_PeerIdentity *current_dest)
3852 struct Closest_Peer peer;
3854 /* Find a local best known peer. */
3855 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3857 /* Am I just a part of a trail towards a finger (current_destination)? */
3858 /* Select best successor among one found locally and current_destination
3859 * that we got from network.*/
3860 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3861 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3864 const struct GNUNET_PeerIdentity *closest_peer;
3866 closest_peer = select_closest_peer (&peer.best_known_destination,
3868 final_dest_finger_val,
3871 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3872 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3874 struct GNUNET_PeerIdentity *next_hop;
3876 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3877 GDS_ROUTING_SRC_TO_DEST);
3878 /* It may happen that trail teardown message got delayed and hence,
3879 the previous hop sent the message over intermediate trail id.In that
3880 case next_hop could be NULL. */
3881 if(NULL != next_hop)
3883 peer.next_hop = *next_hop;
3884 peer.best_known_destination = *current_dest;
3885 peer.trail_id = intermediate_trail_id;
3893 * Core handle for PeerTrailSetupMessage.
3894 * @param cls closure
3895 * @param message message
3896 * @param peer peer identity this notification is about
3897 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3900 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3901 const struct GNUNET_MessageHeader *message)
3903 const struct PeerTrailSetupMessage *trail_setup;
3904 const struct GNUNET_PeerIdentity *trail_peer_list;
3905 struct GNUNET_PeerIdentity current_dest;
3906 struct FriendInfo *target_friend;
3907 struct GNUNET_PeerIdentity source;
3908 uint64_t final_dest_finger_val;
3909 struct GNUNET_HashCode intermediate_trail_id;
3910 struct GNUNET_HashCode trail_id;
3911 unsigned int is_predecessor;
3912 uint32_t trail_length;
3916 msize = ntohs (message->size);
3917 if (msize < sizeof (struct PeerTrailSetupMessage))
3919 GNUNET_break_op (0);
3920 return GNUNET_SYSERR;
3923 trail_setup = (const struct PeerTrailSetupMessage *) message;
3924 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3925 sizeof (struct GNUNET_PeerIdentity);
3926 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3927 sizeof (struct GNUNET_PeerIdentity) != 0)
3929 GNUNET_break_op (0);
3933 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3934 current_dest = trail_setup->best_known_destination;
3935 trail_id = trail_setup->trail_id;
3936 final_dest_finger_val =
3937 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3938 source = trail_setup->source_peer;
3939 is_predecessor = ntohl (trail_setup->is_predecessor);
3940 intermediate_trail_id = trail_setup->intermediate_trail_id;
3942 /* Did the friend insert its ID in the trail list? */
3943 if (trail_length > 0 &&
3944 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (*peer)))
3946 GNUNET_break_op (0);
3947 return GNUNET_SYSERR;
3950 /* If I was the source and got the message back, then set trail length to 0.*/
3951 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3953 /* IF (!) the peers know the destinations of the trails in their routing
3956 * This shoud only happen after 1 hop, since the first message is sent
3957 * to random friend, and we can happen to be on the best trail to the dest.
3958 * If the first friend selects someone else, the request should never come
3963 // GNUNET_break_op (1 == trail_length);
3967 /* Check if you are present in the trail seen so far? */
3968 if(trail_length > 0)
3970 for (i = 0; i < trail_length ; i++)
3972 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity))
3974 //Here if you already were present in the trail. then you
3975 // shoudl trail length to i + 1
3982 /* Is my routing table full? */
3983 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3985 GNUNET_assert (NULL !=
3987 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
3988 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
3989 my_identity, is_predecessor,
3990 trail_peer_list, trail_length,
3991 trail_id, target_friend,
3992 CONGESTION_TIMEOUT);
3996 /* Get the next hop to forward the trail setup request. */
3997 struct Closest_Peer next_peer =
3998 get_local_best_known_next_hop (final_dest_finger_val,
3999 intermediate_trail_id,
4005 /* Am I the final destination? */
4006 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4009 /* If I was not the source of this message for which now I am destination */
4010 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4012 GDS_ROUTING_add (trail_id, *peer, my_identity);
4015 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4017 finger_table_add (my_identity, NULL, 0, is_predecessor,
4018 final_dest_finger_val, trail_id);
4022 if (trail_length > 0)
4023 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4025 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source);
4026 if (NULL == target_friend)
4028 GNUNET_break_op (0);
4029 return GNUNET_SYSERR;
4032 GDS_NEIGHBOURS_send_trail_setup_result (source,
4034 target_friend, trail_length,
4037 final_dest_finger_val,trail_id);
4039 else /* I'm not the final destination. */
4041 GNUNET_assert (NULL !=
4043 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4044 &next_peer.next_hop)));
4046 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4048 /* Add yourself to list of peers. */
4049 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4051 memcpy (peer_list, trail_peer_list,
4052 trail_length * sizeof (struct GNUNET_PeerIdentity));
4053 peer_list[trail_length] = my_identity;
4055 GDS_NEIGHBOURS_send_trail_setup (source,
4056 final_dest_finger_val,
4057 next_peer.best_known_destination,
4058 target_friend, trail_length + 1, peer_list,
4059 is_predecessor, trail_id,
4060 next_peer.trail_id);
4063 GDS_NEIGHBOURS_send_trail_setup (source,
4064 final_dest_finger_val,
4065 next_peer.best_known_destination,
4066 target_friend, 0, NULL,
4067 is_predecessor, trail_id,
4068 next_peer.trail_id);
4074 /* FIXME: here we are calculating my_index and comparing also in this function.
4075 And we are doing it again here in this function. Re factor the code. */
4077 * FIXME: Should we call this function everywhere in all the handle functions
4078 * where we have a trail to verify from or a trail id. something like
4079 * if prev hop is not same then drop the message.
4080 * Check if sender_peer and peer from which we should receive the message are
4081 * same or different.
4082 * @param trail_peer_list List of peers in trail
4083 * @param trail_length Total number of peers in @a trail_peer_list
4084 * @param sender_peer Peer from which we got the message.
4085 * @param finger_identity Finger to which trail is setup. It is not part of trail.
4086 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
4087 * message are different.
4088 * #GNUNET_NO if sender_peer and peer from which we should receive the
4089 * message are different.
4092 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
4093 unsigned int trail_length,
4094 const struct GNUNET_PeerIdentity *sender_peer,
4095 struct GNUNET_PeerIdentity finger_identity,
4096 struct GNUNET_PeerIdentity source_peer)
4100 /* I am the source peer. */
4101 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4104 /* Is the first element of the trail is sender_peer.*/
4105 if (trail_length > 0)
4107 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4113 /* Is finger the sender peer? */
4114 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4121 /* Get my current location in the trail. */
4122 my_index = search_my_index (trail_peer_list, trail_length);
4126 /* I am the last element in the trail. */
4127 if ((trail_length - 1) == my_index)
4129 /* Is finger the sender_peer? */
4130 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4136 /* Is peer after me in trail the sender peer? */
4137 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4138 &trail_peer_list[my_index + 1]))
4148 * FIXME: we should also add a case where we search if we are present in the trail
4150 * Core handle for p2p trail setup result messages.
4152 * @param message message
4153 * @param peer sender of this message.
4154 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4157 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4158 const struct GNUNET_MessageHeader *message)
4160 const struct PeerTrailSetupResultMessage *trail_result;
4161 const struct GNUNET_PeerIdentity *trail_peer_list;
4162 struct GNUNET_PeerIdentity next_hop;
4163 struct FriendInfo *target_friend;
4164 struct GNUNET_PeerIdentity querying_peer;
4165 struct GNUNET_PeerIdentity finger_identity;
4166 uint32_t trail_length;
4167 uint64_t ulitmate_destination_finger_value;
4168 uint32_t is_predecessor;
4169 struct GNUNET_HashCode trail_id;
4173 msize = ntohs (message->size);
4174 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4176 GNUNET_break_op (0);
4180 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4181 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4182 sizeof (struct GNUNET_PeerIdentity);
4183 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4184 sizeof (struct GNUNET_PeerIdentity) != 0)
4186 GNUNET_break_op (0);
4190 is_predecessor = ntohl (trail_result->is_predecessor);
4191 querying_peer = trail_result->querying_peer;
4192 finger_identity = trail_result->finger_identity;
4193 trail_id = trail_result->trail_id;
4194 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4195 ulitmate_destination_finger_value =
4196 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4198 /* FIXME: here we are calculating my_index and comparing also in this function.
4199 And we are doing it again here in this function. Re factor the code. */
4200 /* Ensure that sender peer is the peer from which we were expecting the message. */
4202 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
4204 peer, finger_identity, querying_peer))
4206 GNUNET_break_op (0);
4207 return GNUNET_SYSERR;
4211 /*TODO:URGENT Check if I am already present in the trail. If yes then its an error,
4212 as in trail setup we ensure that it should never happen. */
4213 /* Am I the one who initiated the query? */
4214 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4216 /* If I am my own finger identity, error. */
4217 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4219 GNUNET_break_op (0);
4220 return GNUNET_SYSERR;
4222 GDS_ROUTING_add (trail_id, my_identity, *peer);
4223 finger_table_add (finger_identity, trail_peer_list, trail_length,
4224 is_predecessor, ulitmate_destination_finger_value, trail_id);
4228 /* Get my location in the trail. */
4229 my_index = search_my_index (trail_peer_list, trail_length);
4233 return GNUNET_SYSERR;
4237 next_hop = trail_result->querying_peer;
4239 next_hop = trail_peer_list[my_index - 1];
4241 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4242 if (NULL == target_friend)
4244 GNUNET_break_op (0);
4245 return GNUNET_SYSERR;
4248 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4249 &(trail_result->finger_identity))))
4251 GNUNET_break_op (0);
4252 return GNUNET_SYSERR;
4255 GDS_ROUTING_add (trail_id, next_hop, *peer);
4257 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4258 target_friend, trail_length, trail_peer_list,
4260 ulitmate_destination_finger_value,
4268 * @param trail Trail to be inverted
4269 * @param trail_length Total number of peers in the trail.
4270 * @return Updated trail
4272 static struct GNUNET_PeerIdentity *
4273 invert_trail (const struct GNUNET_PeerIdentity *trail,
4274 unsigned int trail_length)
4278 struct GNUNET_PeerIdentity *inverted_trail;
4280 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4283 j = trail_length - 1;
4284 while (i < trail_length)
4286 inverted_trail[i] = trail[j];
4291 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4292 &inverted_trail[0]));
4293 return inverted_trail;
4298 * Return the shortest trail among all the trails to reach to finger from me.
4299 * @param finger Finger
4300 * @param shortest_trail_length[out] Trail length of shortest trail from me
4302 * @return Shortest trail.
4304 static struct GNUNET_PeerIdentity *
4305 get_shortest_trail (struct FingerInfo *finger,
4306 unsigned int *trail_length)
4308 struct Trail *trail;
4309 unsigned int flag = 0;
4310 unsigned int shortest_trail_index = 0;
4311 int shortest_trail_length = -1;
4312 struct Trail_Element *trail_element;
4313 struct GNUNET_PeerIdentity *trail_list;
4316 trail = GNUNET_new (struct Trail);
4318 /* Get the shortest trail to reach to current successor. */
4319 for (i = 0; i < finger->trails_count; i++)
4321 trail = &finger->trail_list[i];
4325 shortest_trail_index = i;
4326 shortest_trail_length = trail->trail_length;
4331 if (shortest_trail_length > trail->trail_length)
4333 shortest_trail_index = i;
4334 shortest_trail_length = trail->trail_length;
4339 /* Copy the shortest trail and return. */
4340 trail = &finger->trail_list[shortest_trail_index];
4341 trail_element = trail->trail_head;
4343 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4344 shortest_trail_length);
4346 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4348 trail_list[i] = trail_element->peer;
4351 GNUNET_assert(shortest_trail_length != -1);
4353 *trail_length = shortest_trail_length;
4359 * Check if trail_1 and trail_2 have any common element. If yes then join
4360 * them at common element. trail_1 always preceeds trail_2 in joined trail.
4361 * @param trail_1 Trail from source to me, NOT including endpoints.
4362 * @param trail_1_len Total number of peers @a trail_1
4363 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4364 * @param trail_2_len Total number of peers @a trail_2
4365 * @param joined_trail_len Total number of peers in combined trail of trail_1
4367 * @return Joined trail.
4369 static struct GNUNET_PeerIdentity *
4370 check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4371 unsigned int trail_1_len,
4372 struct GNUNET_PeerIdentity *trail_2,
4373 unsigned int trail_2_len,
4374 unsigned int *joined_trail_len)
4376 struct GNUNET_PeerIdentity *joined_trail;
4381 for (i = 0; i < trail_1_len; i++)
4383 for (j = 0; j < trail_2_len; j++)
4385 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j]))
4388 *joined_trail_len = i + (trail_2_len - j) + 1;
4389 joined_trail = GNUNET_malloc (*joined_trail_len *
4390 sizeof(struct GNUNET_PeerIdentity));
4393 /* Copy all the elements from 0 to i into joined_trail. */
4394 for(k = 0; k < (i+1); k++)
4396 joined_trail[k] = trail_1[k];
4399 /* Increment j as entry stored is same as entry stored at i*/
4402 /* Copy all the elements from j+1 to trail_2_len-1 to joined trail.*/
4403 while((k < *joined_trail_len) && (j < trail_2_len));
4405 joined_trail[k] = trail_2[j];
4410 return joined_trail;
4414 /* Here you should join the trails. */
4415 *joined_trail_len = trail_1_len + trail_2_len + 1;
4416 joined_trail = GNUNET_malloc (*joined_trail_len *
4417 sizeof(struct GNUNET_PeerIdentity));
4419 while( i < trail_1_len)
4421 joined_trail[i] = trail_1[i];
4424 joined_trail[i] = my_identity;
4427 for (j = 0; i < *joined_trail_len; i++,j++)
4429 joined_trail[i] = trail_2[j];
4431 return joined_trail;
4436 * Return the trail from source to my current predecessor. Check if source
4437 * is already part of the this trail, if yes then return the shorten trail.
4438 * @param current_trail Trail from source to me, NOT including the endpoints.
4439 * @param current_trail_length Number of peers in @a current_trail.
4440 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4441 * source to my predecessor, NOT including
4443 * @return Trail from source to my predecessor.
4445 static struct GNUNET_PeerIdentity *
4446 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4447 const struct GNUNET_PeerIdentity *trail_src_to_me,
4448 unsigned int trail_src_to_me_len,
4449 unsigned int *trail_src_to_curr_pred_length)
4451 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4452 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4453 unsigned int trail_me_to_curr_pred_length;
4454 struct FingerInfo *current_predecessor;
4458 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4459 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4460 &trail_me_to_curr_pred_length);
4462 /* If there is only on element in the trail, and that element is source.*/
4463 if ((trail_me_to_curr_pred_length == 1) &&
4464 (0 == GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4465 &trail_me_to_curr_pred[0])))
4467 *trail_src_to_curr_pred_length = 0;
4468 GNUNET_free_non_null(trail_me_to_curr_pred);
4472 /* Check if trail_me_to_curr_pred contains source. */
4473 if (trail_me_to_curr_pred_length > 1)
4475 for(i = trail_me_to_curr_pred_length - 1; i > 0; i--)
4477 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4478 &trail_me_to_curr_pred[i]))
4481 /* Source is NOT part of trail. */
4484 /* Source is the last element in the trail to reach to my pred.
4485 Source is direct friend of the pred. */
4486 if (trail_me_to_curr_pred_length == i)
4488 *trail_src_to_curr_pred_length = 0;
4492 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4493 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4494 *trail_src_to_curr_pred_length);
4495 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4497 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4499 GNUNET_free_non_null(trail_me_to_curr_pred);
4500 return trail_src_to_curr_pred;
4502 /* Is first element source? Then exclude first element and copy rest of the
4504 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4505 &trail_me_to_curr_pred[0]))
4507 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - 1;
4508 trail_src_to_curr_pred = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)*
4509 *trail_src_to_curr_pred_length);
4511 for(j=0; j < *trail_src_to_curr_pred_length;j++)
4513 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[j+1];
4515 return trail_src_to_curr_pred;
4520 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4521 trail_src_to_me_len,
4522 trail_me_to_curr_pred,
4523 trail_me_to_curr_pred_length,
4525 *trail_src_to_curr_pred_length = len;
4526 GNUNET_free_non_null(trail_me_to_curr_pred);
4527 return trail_src_to_curr_pred;
4532 * Add finger as your predecessor. To add, first generate a new trail id, invert
4533 * the trail to get the trail from me to finger, add an entry in your routing
4534 * table, send add trail message to peers which are part of trail from me to
4535 * finger and add finger in finger table.
4538 * @param trail_length
4541 update_predecessor (struct GNUNET_PeerIdentity finger,
4542 struct GNUNET_PeerIdentity *trail,
4543 unsigned int trail_length)
4545 struct GNUNET_HashCode trail_to_new_predecessor_id;
4546 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4547 struct FriendInfo *target_friend;
4549 /* Generate trail id for trail from me to new predecessor = finger. */
4550 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4551 &trail_to_new_predecessor_id,
4552 sizeof (trail_to_new_predecessor_id));
4554 /* Finger is a friend. */
4555 if (trail_length == 0)
4557 trail_to_new_predecessor = NULL;
4558 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4559 GNUNET_assert (NULL != (target_friend =
4560 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4565 /* Invert the trail to get the trail from me to finger, NOT including the
4567 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4568 &trail[trail_length-1]));
4570 trail_to_new_predecessor = invert_trail (trail, trail_length);
4572 /* Add an entry in your routing table. */
4573 GDS_ROUTING_add (trail_to_new_predecessor_id,
4575 trail_to_new_predecessor[0]);
4577 GNUNET_assert (NULL != (target_friend =
4578 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4579 &trail_to_new_predecessor[0])));
4580 GNUNET_assert (NULL != (
4581 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4582 &trail[trail_length - 1])));
4585 /* Add entry in routing table of all peers that are part of trail from me
4586 to finger, including finger. */
4587 GDS_NEIGHBOURS_send_add_trail (my_identity,
4589 trail_to_new_predecessor_id,
4590 trail_to_new_predecessor,
4594 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4595 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4596 GNUNET_free_non_null(trail_to_new_predecessor);
4601 * Check if you already have a predecessor. If not then add finger as your
4602 * predecessor. If you have predecessor, then compare two peer identites.
4603 * If finger is correct predecessor, then remove the old entry, add finger in
4604 * finger table and send add_trail message to add the trail in the routing
4605 * table of all peers which are part of trail to reach from me to finger.
4606 * @param finger New peer which may be our predecessor.
4607 * @param trail List of peers to reach from @finger to me.
4608 * @param trail_length Total number of peer in @a trail.
4611 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4612 struct GNUNET_PeerIdentity *trail,
4613 unsigned int trail_length)
4615 struct FingerInfo *current_predecessor;
4616 const struct GNUNET_PeerIdentity *closest_peer;
4617 uint64_t predecessor_value;
4618 unsigned int is_predecessor = 1;
4620 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4622 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4624 /* No predecessor. Add finger as your predecessor. */
4625 if (GNUNET_NO == current_predecessor->is_present)
4627 update_predecessor (finger, trail, trail_length);
4631 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4637 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4638 closest_peer = select_closest_peer (&finger,
4639 ¤t_predecessor->finger_identity,
4640 predecessor_value, is_predecessor);
4642 /* Finger is the closest predecessor. Remove the existing one and add the new
4644 if (closest_peer == &finger)
4646 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4647 update_predecessor (finger, trail, trail_length);
4655 * Core handle for p2p verify successor messages.
4656 * @param cls closure
4657 * @param message message
4658 * @param peer peer identity this notification is about
4659 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4662 handle_dht_p2p_verify_successor(void *cls,
4663 const struct GNUNET_PeerIdentity *peer,
4664 const struct GNUNET_MessageHeader *message)
4666 const struct PeerVerifySuccessorMessage *vsm;
4667 struct GNUNET_HashCode trail_id;
4668 struct GNUNET_PeerIdentity successor;
4669 struct GNUNET_PeerIdentity source_peer;
4670 struct GNUNET_PeerIdentity *trail;
4671 struct GNUNET_PeerIdentity *next_hop;
4672 struct FingerInfo current_predecessor;
4673 struct FriendInfo *target_friend;
4674 unsigned int trail_src_to_curr_pred_len = 0;
4675 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4676 unsigned int trail_length;
4679 msize = ntohs (message->size);
4681 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4683 GNUNET_break_op (0);
4687 vsm = (const struct PeerVerifySuccessorMessage *) message;
4688 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4689 sizeof (struct GNUNET_PeerIdentity);
4690 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4691 sizeof (struct GNUNET_PeerIdentity) != 0)
4693 GNUNET_break_op (0);
4697 trail_id = vsm->trail_id;
4698 source_peer = vsm->source_peer;
4699 successor = vsm->successor;
4700 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4703 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4705 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4707 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4708 if (NULL == next_hop)
4710 GNUNET_break_op (0);
4711 return GNUNET_SYSERR;
4714 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4716 if(NULL == target_friend)
4721 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4722 trail_id, trail, trail_length,
4727 /* I am the destination of this message. */
4729 /* Check if the source_peer could be our predecessor and if yes then update
4731 compare_and_update_predecessor (source_peer, trail, trail_length);
4732 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4733 unsigned int flag = 0;
4735 /* Is source of this message NOT my predecessor. */
4736 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity,
4739 /* Check if trail contains current_predecessor. */
4741 for (i = 0; i < trail_length; i++)
4743 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&trail[i],
4744 ¤t_predecessor.finger_identity))
4748 trail_src_to_curr_pred_len = i;
4749 trail_src_to_curr_pred = GNUNET_malloc (trail_src_to_curr_pred_len *
4750 sizeof(struct GNUNET_PeerIdentity));
4755 trail_src_to_curr_pred[k] = trail[k];
4763 trail_src_to_curr_pred =
4764 get_trail_src_to_curr_pred (source_peer,
4767 &trail_src_to_curr_pred_len);
4772 trail_src_to_curr_pred_len = trail_length;
4775 trail_src_to_curr_pred =
4776 GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)
4777 *trail_src_to_curr_pred_len);
4778 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4780 trail_src_to_curr_pred[i] = trail[i];
4784 GNUNET_assert (NULL !=
4786 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4787 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4788 current_predecessor.finger_identity,
4789 trail_id, trail_src_to_curr_pred,
4790 trail_src_to_curr_pred_len,
4791 GDS_ROUTING_DEST_TO_SRC,
4793 GNUNET_free_non_null(trail_src_to_curr_pred);
4799 * If the trail from me to my probable successor contains a friend not
4800 * at index 0, then we can shorten the trail.
4801 * @param probable_successor Peer which is our probable successor
4802 * @param trail_me_to_probable_successor Peers in path from me to my probable
4803 * successor, NOT including the endpoints.
4804 * @param trail_me_to_probable_successor_len Total number of peers in
4805 * @a trail_me_to_probable_succesor.
4806 * @return Updated trail, if any friend found.
4807 * Else the trail_me_to_probable_successor.
4809 struct GNUNET_PeerIdentity *
4810 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4811 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4812 unsigned int trail_me_to_probable_successor_len,
4813 unsigned int *trail_to_new_successor_length)
4817 struct GNUNET_PeerIdentity *trail_to_new_successor;
4819 /* Probable successor is a friend */
4820 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4821 &probable_successor))
4823 trail_to_new_successor = NULL;
4824 *trail_to_new_successor_length = 0;
4825 return trail_to_new_successor;
4828 /* Is there any friend of yours in this trail. */
4829 if(trail_me_to_probable_successor_len > 1)
4831 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4833 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4834 &trail_me_to_probable_successor[i]))
4838 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4839 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4840 *trail_to_new_successor_length);
4843 for(j = 0;j < *trail_to_new_successor_length;i++,j++)
4845 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4848 return trail_to_new_successor;
4852 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4853 return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor;
4855 trail_to_new_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4856 *trail_to_new_successor_length);
4858 for(i = 0; i < *trail_to_new_successor_length; i++)
4859 trail_to_new_successor[i] = trail_me_to_probable_successor[i];
4861 return trail_to_new_successor;
4867 * Check if the peer which sent us verify successor result message is still ours
4868 * successor or not. If not, then compare existing successor and probable successor.
4869 * In case probable successor is the correct successor, remove the existing
4870 * successor. Add probable successor as new successor. Send notify new successor
4871 * message to new successor.
4873 * @param probable_successor
4875 * @param trail_length
4878 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4879 struct GNUNET_PeerIdentity probable_successor,
4880 const struct GNUNET_PeerIdentity *trail,
4881 unsigned int trail_length)
4883 struct FingerInfo *current_successor;
4884 const struct GNUNET_PeerIdentity *closest_peer;
4885 struct GNUNET_HashCode trail_id;
4886 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4887 struct FriendInfo *target_friend;
4888 unsigned int trail_me_to_probable_succ_len;
4889 unsigned int is_predecessor = GNUNET_NO;
4890 uint64_t successor_value;
4892 current_successor = &finger_table[0];
4893 successor_value = compute_finger_identity_value(0);
4895 /* Have we found some other successor, while waiting for verify successor result
4897 * FIXME closest_peer is being overwritten just after the if
4900 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&curr_succ, ¤t_successor->finger_identity))
4902 /* We could have added this new successor, only if it was closer the old one. */
4903 closest_peer = select_closest_peer (&curr_succ,
4904 ¤t_successor->finger_identity,
4905 successor_value, is_predecessor);
4907 /* FIXME: it may fail in case we have done more number of iterations of
4908 find _finger_trail_task. */
4909 /*GNUNET_assert (0 ==
4910 GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4911 ¤t_successor->finger_identity));*/
4916 closest_peer = select_closest_peer (&probable_successor,
4917 ¤t_successor->finger_identity,
4918 successor_value, is_predecessor);
4920 /* If the current_successor in the finger table is closest, then do nothing. */
4921 if (closest_peer == ¤t_successor->finger_identity)
4924 /* Probable successor is the closest peer.*/
4925 if(trail_length > 0)
4927 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4932 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4933 &probable_successor));
4936 trail_me_to_probable_succ_len = 0;
4937 /* TODO: Check if the path to reach to probable successor contains a friend. */
4938 trail_me_to_probable_succ =
4939 check_trail_me_to_probable_succ (probable_successor,
4940 trail, trail_length,
4941 &trail_me_to_probable_succ_len);
4943 /* Remove the existing successor. */
4944 remove_existing_finger (current_successor, 0);
4946 /* TODO URGENT: Check if any peer is present more than once, if yes then shorten
4947 the trail. before sending it across the network. */
4948 /* Generate a new trail id to reach to your new successor. */
4949 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4950 &trail_id, sizeof (trail_id));
4952 if (trail_me_to_probable_succ_len > 0)
4954 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4955 GNUNET_assert (NULL !=
4957 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4958 &trail_me_to_probable_succ[0])));
4962 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4963 GNUNET_assert (NULL !=
4965 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4966 &probable_successor)));
4969 add_new_finger (probable_successor, trail_me_to_probable_succ,
4970 trail_me_to_probable_succ_len, trail_id, 0);
4972 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4973 trail_me_to_probable_succ,
4974 trail_me_to_probable_succ_len,
4982 * FIXME: Check for duplicate elements everywhere when you are making
4984 * Core handle for p2p verify successor result messages.
4985 * @param cls closure
4986 * @param message message
4987 * @param peer peer identity this notification is about
4988 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4991 handle_dht_p2p_verify_successor_result(void *cls,
4992 const struct GNUNET_PeerIdentity *peer,
4993 const struct GNUNET_MessageHeader *message)
4995 const struct PeerVerifySuccessorResultMessage *vsrm;
4996 enum GDS_ROUTING_trail_direction trail_direction;
4997 struct GNUNET_PeerIdentity querying_peer;
4998 struct GNUNET_HashCode trail_id;
4999 struct GNUNET_PeerIdentity *next_hop;
5000 struct FriendInfo *target_friend;
5001 struct GNUNET_PeerIdentity probable_successor;
5002 struct GNUNET_PeerIdentity current_successor;
5003 const struct GNUNET_PeerIdentity *trail;
5004 unsigned int trail_length;
5007 msize = ntohs (message->size);
5008 /* We send a trail to reach from old successor to new successor, if
5009 * old_successor != new_successor.*/
5010 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
5012 GNUNET_break_op (0);
5016 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
5017 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
5018 sizeof (struct GNUNET_PeerIdentity);
5020 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5021 sizeof (struct GNUNET_PeerIdentity) != 0)
5023 GNUNET_break_op (0);
5027 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5028 querying_peer = vsrm->querying_peer;
5029 trail_direction = ntohl (vsrm->trail_direction);
5030 trail_id = vsrm->trail_id;
5031 probable_successor = vsrm->probable_successor;
5032 current_successor = vsrm->current_successor;
5035 /* I am the querying_peer. */
5036 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
5038 compare_and_update_successor (current_successor,
5039 probable_successor, trail, trail_length);
5043 /*If you are not the querying peer then pass on the message */
5044 GNUNET_assert (NULL != (next_hop =
5045 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
5046 GNUNET_assert (NULL !=
5048 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5049 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
5050 vsrm->current_successor,
5051 probable_successor, trail_id,
5054 trail_direction, target_friend);
5060 * Core handle for p2p notify new successor messages.
5061 * @param cls closure
5062 * @param message message
5063 * @param peer peer identity this notification is about
5064 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5067 handle_dht_p2p_notify_new_successor(void *cls,
5068 const struct GNUNET_PeerIdentity *peer,
5069 const struct GNUNET_MessageHeader *message)
5071 const struct PeerNotifyNewSuccessorMessage *nsm;
5072 struct GNUNET_PeerIdentity *trail;
5073 struct GNUNET_PeerIdentity source;
5074 struct GNUNET_PeerIdentity new_successor;
5075 struct GNUNET_HashCode trail_id;
5076 struct GNUNET_PeerIdentity next_hop;
5077 struct FriendInfo *target_friend;
5080 uint32_t trail_length;
5082 msize = ntohs (message->size);
5084 /* We have the trail to reach from source to new successor. */
5085 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
5087 GNUNET_break_op (0);
5091 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
5092 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5093 sizeof (struct GNUNET_PeerIdentity);
5094 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5095 sizeof (struct GNUNET_PeerIdentity) != 0)
5097 GNUNET_break_op (0);
5101 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
5102 source = nsm->source_peer;
5103 new_successor = nsm->new_successor;
5104 trail_id = nsm->trail_id;
5107 //FIXME: add a check to make sure peer is correct.
5109 /* I am the new_successor to source_peer. */
5110 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
5112 if(trail_length > 0)
5113 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1],
5116 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer));
5118 compare_and_update_predecessor (source, trail, trail_length);
5122 GNUNET_assert(trail_length > 0);
5123 /* I am part of trail to reach to successor. */
5124 my_index = search_my_index (trail, trail_length);
5127 GNUNET_break_op (0);
5128 return GNUNET_SYSERR;
5131 if ((trail_length-1) == my_index)
5132 next_hop = new_successor;
5134 next_hop = trail[my_index + 1];
5137 /* Add an entry in routing table for trail from source to its new successor. */
5138 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5139 GNUNET_assert (NULL !=
5141 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5142 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5144 trail_id, target_friend);
5151 * Core handler for P2P trail rejection message
5152 * @param cls closure
5153 * @param message message
5154 * @param peer peer identity this notification is about
5155 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5158 handle_dht_p2p_trail_setup_rejection (void *cls,
5159 const struct GNUNET_PeerIdentity *peer,
5160 const struct GNUNET_MessageHeader *message)
5162 const struct PeerTrailRejectionMessage *trail_rejection;
5163 unsigned int trail_length;
5164 const struct GNUNET_PeerIdentity *trail_peer_list;
5165 struct FriendInfo *target_friend;
5166 struct GNUNET_TIME_Relative congestion_timeout;
5167 struct GNUNET_HashCode trail_id;
5168 struct GNUNET_PeerIdentity next_peer;
5169 struct GNUNET_PeerIdentity source;
5170 struct GNUNET_PeerIdentity *next_hop;
5171 uint64_t ultimate_destination_finger_value;
5172 unsigned int is_predecessor;
5175 msize = ntohs (message->size);
5176 /* We are passing the trail setup so far. */
5177 if (msize < sizeof (struct PeerTrailRejectionMessage))
5179 GNUNET_break_op (0);
5183 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5184 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5185 sizeof (struct GNUNET_PeerIdentity);
5186 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5187 sizeof (struct GNUNET_PeerIdentity) != 0)
5189 GNUNET_break_op (0);
5193 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5194 is_predecessor = ntohl (trail_rejection->is_predecessor);
5195 congestion_timeout = trail_rejection->congestion_time;
5196 source = trail_rejection->source_peer;
5197 trail_id = trail_rejection->trail_id;
5198 ultimate_destination_finger_value =
5199 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5201 /* First set the congestion time of the friend that sent you this message. */
5202 GNUNET_assert (NULL !=
5204 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5205 target_friend->congestion_timestamp =
5206 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5207 congestion_timeout);
5209 /* I am the source peer which wants to setup the trail. Do nothing.
5210 * send_find_finger_trail_task is scheduled periodically.*/
5211 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5214 /* If I am congested then pass this message to peer before me in trail. */
5215 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5217 struct GNUNET_PeerIdentity *new_trail;
5218 unsigned int new_trail_length;
5220 /* Remove yourself from the trail setup so far. */
5221 if (trail_length == 1)
5224 new_trail_length = 0;
5229 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5230 sizeof (struct GNUNET_PeerIdentity));
5232 /* Remove myself from the trail. */
5233 new_trail_length = trail_length -1;
5234 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5235 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5238 GNUNET_assert (NULL !=
5240 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5241 GDS_NEIGHBOURS_send_trail_rejection (source,
5242 ultimate_destination_finger_value,
5243 my_identity, is_predecessor,
5244 new_trail,new_trail_length,trail_id,
5245 target_friend, CONGESTION_TIMEOUT);
5246 GNUNET_free (new_trail);
5250 struct Closest_Peer successor;
5251 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5253 /* Am I the final destination? */
5254 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5257 if (0 == trail_length)
5260 next_peer = trail_peer_list[trail_length-1];
5262 GNUNET_assert (NULL !=
5264 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5266 GDS_NEIGHBOURS_send_trail_setup_result (source,
5268 target_friend, trail_length,
5271 ultimate_destination_finger_value,
5276 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5278 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5279 peer_list[trail_length] = my_identity;
5281 GNUNET_assert (NULL !=
5283 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5285 GDS_NEIGHBOURS_send_trail_setup (source,
5286 ultimate_destination_finger_value,
5287 successor.best_known_destination,
5288 target_friend, trail_length + 1, peer_list,
5289 is_predecessor, trail_id,
5290 successor.trail_id);
5297 * Core handle for p2p trail tear compression messages.
5298 * @param cls closure
5299 * @param message message
5300 * @param peer peer identity this notification is about
5301 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5304 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5305 const struct GNUNET_MessageHeader *message)
5307 const struct PeerTrailCompressionMessage *trail_compression;
5308 struct GNUNET_PeerIdentity *next_hop;
5309 struct FriendInfo *target_friend;
5310 struct GNUNET_HashCode trail_id;
5313 msize = ntohs (message->size);
5315 if (msize != sizeof (struct PeerTrailCompressionMessage))
5317 GNUNET_break_op (0);
5321 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5322 trail_id = trail_compression->trail_id;
5324 /* Am I the new first friend to reach to finger of this trail. */
5325 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5328 GNUNET_assert (NULL !=
5329 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5330 &trail_compression->source_peer)));
5332 /* Update your prev hop to source of this message. */
5333 GNUNET_assert (GNUNET_SYSERR !=
5334 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5335 trail_compression->source_peer)));
5339 /* Pass the message to next hop to finally reach to new_first_friend. */
5340 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5342 if (NULL == next_hop)
5348 GNUNET_assert (NULL !=
5350 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5352 GDS_ROUTING_remove_trail (trail_id);
5354 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5356 trail_compression->new_first_friend,
5363 * Core handler for trail teardown message.
5364 * @param cls closure
5365 * @param message message
5366 * @param peer sender of this messsage.
5367 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5370 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5371 const struct GNUNET_MessageHeader *message)
5373 const struct PeerTrailTearDownMessage *trail_teardown;
5374 enum GDS_ROUTING_trail_direction trail_direction;
5375 struct GNUNET_HashCode trail_id;
5376 struct GNUNET_PeerIdentity *next_hop;
5379 msize = ntohs (message->size);
5381 /* Here we pass only the trail id. */
5382 if (msize != sizeof (struct PeerTrailTearDownMessage))
5384 GNUNET_break_op (0);
5388 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5389 trail_direction = ntohl (trail_teardown->trail_direction);
5390 trail_id = trail_teardown->trail_id;
5392 /* Check if peer is the real peer from which we should get this message.*/
5393 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5395 GNUNET_assert (NULL != (prev_hop =
5396 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5397 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5400 return GNUNET_SYSERR;
5404 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5406 if (NULL == next_hop)
5409 return GNUNET_SYSERR;
5412 /* I am the next hop, which means I am the final destination. */
5413 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5415 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5420 /* If not final destination, then send a trail teardown message to next hop.*/
5421 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5422 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5423 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5431 * Core handle for p2p add trail message.
5432 * @param cls closure
5433 * @param message message
5434 * @param peer peer identity this notification is about
5435 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5438 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5439 const struct GNUNET_MessageHeader *message)
5441 const struct PeerAddTrailMessage *add_trail;
5442 const struct GNUNET_PeerIdentity *trail;
5443 struct GNUNET_HashCode trail_id;
5444 struct GNUNET_PeerIdentity destination_peer;
5445 struct GNUNET_PeerIdentity source_peer;
5446 struct GNUNET_PeerIdentity next_hop;
5447 unsigned int trail_length;
5448 unsigned int my_index;
5451 msize = ntohs (message->size);
5452 /* In this message we pass the whole trail from source to destination as we
5453 * are adding that trail.*/
5454 //FIXME: failed when run with 1000 pears. check why.
5455 if (msize < sizeof (struct PeerAddTrailMessage))
5457 GNUNET_break_op (0);
5461 add_trail = (const struct PeerAddTrailMessage *) message;
5462 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5463 sizeof (struct GNUNET_PeerIdentity);
5464 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5465 sizeof (struct GNUNET_PeerIdentity) != 0)
5467 GNUNET_break_op (0);
5471 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5472 destination_peer = add_trail->destination_peer;
5473 source_peer = add_trail->source_peer;
5474 trail_id = add_trail->trail_id;
5476 //FIXME: add a check that sender peer is not malicious. Make it a generic
5477 // function so that it can be used in all other functions where we need the
5478 // same functionality.
5480 /* I am not the destination of the trail. */
5481 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5483 struct FriendInfo *target_friend;
5485 /* Get my location in the trail. */
5486 my_index = search_my_index (trail, trail_length);
5489 GNUNET_break_op (0);
5490 return GNUNET_SYSERR;
5493 if ((trail_length - 1) == my_index)
5495 next_hop = destination_peer;
5499 next_hop = trail[my_index + 1];
5502 /* Add in your routing table. */
5503 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5504 GNUNET_assert (NULL !=
5506 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5507 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5508 trail, trail_length, target_friend);
5511 /* I am the destination. Add an entry in routing table. */
5512 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5518 * Free the finger trail in which the first friend to reach to a finger is
5519 * disconnected_friend. Also remove entry from routing table for that particular
5521 * @param disconnected_friend PeerIdentity of friend which got disconnected
5522 * @param remove_finger Finger whose trail we need to check if it has
5523 * disconnected_friend as the first hop.
5524 * @return Total number of trails in which disconnected_friend was the first
5528 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5529 struct FingerInfo *remove_finger)
5531 unsigned int matching_trails_count;
5534 /* Number of trails with disconnected_friend as the first hop in the trail
5535 * to reach from me to remove_finger, NOT including endpoints. */
5536 matching_trails_count = 0;
5538 /* Iterate over all the trails of finger. */
5539 for (i = 0; i < remove_finger->trails_count; i++)
5541 struct Trail *trail;
5542 trail = &remove_finger->trail_list[i];
5544 /* This assertion is ensure that there are no gaps in the trail list.
5545 REMOVE IT AFTERWARDS. */
5546 GNUNET_assert (GNUNET_YES == trail->is_present);
5548 /* First friend to reach to finger is disconnected_peer. */
5549 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5550 disconnected_friend))
5552 struct GNUNET_PeerIdentity *next_hop;
5553 struct FriendInfo *remove_friend;
5555 GNUNET_assert (NULL !=
5557 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5558 disconnected_friend)));
5559 /* FIXME: removing no but check it. */
5560 //remove_friend->trails_count--;
5561 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5562 GDS_ROUTING_SRC_TO_DEST);
5564 /* Here it may happen that as all the peers got disconnected, the entry in
5565 routing table for that particular trail has been removed, because the
5566 previously disconnected peer was either a next hop or prev hop of that
5568 if (NULL == next_hop)
5571 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5573 matching_trails_count++;
5574 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5577 trail->is_present = GNUNET_NO;
5580 return matching_trails_count;
5585 * Iterate over finger_table entries.
5586 * 0. Ignore finger which is my_identity or if no valid entry present at
5587 * that finger index.
5588 * 1. If disconnected_friend is a finger, then remove the routing entry from
5589 your own table. Free the trail.
5590 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5591 * 2.1 Remove all the trails and entry from routing table in which disconnected
5592 * friend is the first friend in the trail. If disconnected_friend is the
5593 * first friend in all the trails to reach finger, then remove the finger.
5594 * @param disconnected_friend Peer identity of friend which got disconnected.
5597 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5599 struct FingerInfo *remove_finger;
5600 struct FriendInfo *remove_friend;
5601 int removed_trails_count;
5604 /* Iterate over finger table entries. */
5605 for (i = 0; i < MAX_FINGERS; i++)
5607 remove_finger = &finger_table[i];
5609 /* No finger stored at this trail index. */
5610 if (GNUNET_NO == remove_finger->is_present)
5613 /* I am my own finger, then ignore this finger. */
5614 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5618 /* Is disconnected_peer a finger? */
5619 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5620 &remove_finger->finger_identity))
5622 struct GNUNET_PeerIdentity *next_hop;
5623 struct GNUNET_HashCode trail_id;
5626 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5627 trail_id = remove_finger->trail_list[0].trail_id;
5631 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5634 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5635 &remove_finger->finger_identity)));
5636 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5637 GNUNET_assert (NULL !=
5639 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5640 disconnected_peer)));
5643 remove_finger->trail_list[0].is_present = GNUNET_NO;
5644 //GNUNET_assert (0 != remove_friend->trails_count);
5645 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5646 remove_finger->is_present = GNUNET_NO;
5647 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5651 /* If finger is a friend but not disconnected_friend, then continue. */
5652 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5653 &remove_finger->finger_identity))
5656 /* Iterate over the list of trails to reach remove_finger. Check if
5657 * disconnected_friend is the first friend in any of the trail. */
5658 removed_trails_count = remove_matching_trails (disconnected_peer,
5660 remove_finger->trails_count =
5661 remove_finger->trails_count - removed_trails_count;
5662 /* All the finger trails had disconnected_friend as the first friend,
5663 * so free the finger. */
5664 if (remove_finger->trails_count == 0)
5666 remove_finger->is_present = GNUNET_NO;
5667 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5674 * Method called whenever a peer disconnects.
5676 * @param cls closure
5677 * @param peer peer identity this notification is about
5680 handle_core_disconnect (void *cls,
5681 const struct GNUNET_PeerIdentity *peer)
5683 struct FriendInfo *remove_friend;
5685 /* If disconnected to own identity, then return. */
5686 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5689 GNUNET_assert (NULL != (remove_friend =
5690 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5692 /* Remove fingers with peer as first friend or if peer is a finger. */
5693 remove_matching_fingers (peer);
5695 /* Remove any trail from routing table of which peer is a part of. This function
5696 * internally sends a trail teardown message in the direction of which
5697 * disconnected peer is not part of. */
5698 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5700 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5702 /* Remove peer from friend_peermap. */
5703 GNUNET_assert (GNUNET_YES ==
5704 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5708 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5711 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5713 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5714 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5723 * Method called whenever a peer connects.
5725 * @param cls closure
5726 * @param peer_identity peer identity this notification is about
5729 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5731 struct FriendInfo *friend;
5733 /* Check for connect to self message */
5734 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5737 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5739 /* If peer already exists in our friend_peermap, then exit. */
5740 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5747 friend = GNUNET_new (struct FriendInfo);
5748 friend->id = *peer_identity;
5750 GNUNET_assert (GNUNET_OK ==
5751 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5752 peer_identity, friend,
5753 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5756 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5757 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5759 next_send_time.rel_value_us =
5760 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
5761 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5762 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
5763 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5769 * To be called on core init/fail.
5771 * @param cls service closure
5772 * @param identity the public identity of this peer
5775 core_init (void *cls,
5776 const struct GNUNET_PeerIdentity *identity)
5778 my_identity = *identity;
5781 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5782 my_id64 = GNUNET_ntohll (my_id64);
5783 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5784 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5790 * Initialize finger table entries.
5793 finger_table_init ()
5795 memset (&finger_table, 0, sizeof (finger_table));
5800 * Initialize neighbours subsystem.
5801 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5804 GDS_NEIGHBOURS_init (void)
5806 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5807 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5808 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5809 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5810 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5811 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5812 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5813 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5814 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5815 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5816 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5817 sizeof (struct PeerTrailCompressionMessage)},
5818 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5819 sizeof (struct PeerTrailTearDownMessage)},
5820 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5825 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5826 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5827 GNUNET_NO, core_handlers);
5828 if (NULL == core_api)
5829 return GNUNET_SYSERR;
5831 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5832 finger_table_init ();
5839 * Shutdown neighbours subsystem.
5842 GDS_NEIGHBOURS_done (void)
5844 if (NULL == core_api)
5847 GNUNET_CORE_disconnect (core_api);
5850 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5851 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5852 friend_peermap = NULL;
5854 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5857 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5858 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5861 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5863 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5864 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5872 * @return my identity
5874 struct GNUNET_PeerIdentity
5875 GDS_NEIGHBOURS_get_my_id (void)
5880 /* end of gnunet-service-xdht_neighbours.c */