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;
1263 if (trail_length != 0)
1265 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1266 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1269 /* Send the message to chosen friend. */
1270 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1271 target_friend->pending_count++;
1272 process_friend_queue (target_friend);
1277 * FIXME: In every function we pass target friend except for this one.
1278 * so, either change everything or this one. also, should se just store
1279 * the pointer to friend in routing table rather than gnunet_peeridentity.
1280 * if yes then we should keep friend info in.h andmake lot of changes.
1281 * Construct a trail teardown message and forward it to target friend.
1282 * @param trail_id Unique identifier of the trail.
1283 * @param trail_direction Direction of trail.
1284 * @param target_friend Friend to get this message.
1287 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1288 unsigned int trail_direction,
1289 struct GNUNET_PeerIdentity peer)
1291 struct PeerTrailTearDownMessage *ttdm;
1292 struct P2PPendingMessage *pending;
1293 struct FriendInfo *target_friend;
1296 msize = sizeof (struct PeerTrailTearDownMessage);
1298 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1304 /*FIXME:In what case friend can be null. ?*/
1305 if (NULL == (target_friend =
1306 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1309 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1311 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1315 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1316 pending->importance = 0; /* FIXME */
1317 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1318 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1319 pending->msg = &ttdm->header;
1320 ttdm->header.size = htons (msize);
1321 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1322 ttdm->trail_id = trail_id;
1323 ttdm->trail_direction = htonl (trail_direction);
1325 /* Send the message to chosen friend. */
1326 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1327 target_friend->pending_count++;
1328 process_friend_queue (target_friend);
1333 * Construct a verify successor result message and send it to target_friend
1334 * @param querying_peer Peer which sent the verify successor message.
1335 * @param source_successor Current_successor of @a querying_peer.
1336 * @param current_predecessor Current predecessor of @a successor. Could be same
1337 * or different from @a querying_peer.
1338 * @param trail_id Unique identifier of the trail from @a querying_peer to
1339 * @a successor, NOT including them.
1340 * @param trail List of peers which are part of trail from @a querying_peer to
1341 * @a successor, NOT including them.
1342 * @param trail_length Total number of peers in @a trail
1343 * @param trail_direction Direction in which we are sending the message. In this
1344 * case we are sending result from @a successor to @a querying_peer.
1345 * @param target_friend Next friend to get this message.
1348 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1349 struct GNUNET_PeerIdentity current_successor,
1350 struct GNUNET_PeerIdentity probable_successor,
1351 struct GNUNET_HashCode trail_id,
1352 const struct GNUNET_PeerIdentity *trail,
1353 unsigned int trail_length,
1354 enum GDS_ROUTING_trail_direction trail_direction,
1355 struct FriendInfo *target_friend)
1357 struct PeerVerifySuccessorResultMessage *vsmr;
1358 struct P2PPendingMessage *pending;
1359 struct GNUNET_PeerIdentity *peer_list;
1362 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1363 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1365 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1371 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1373 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1377 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1378 pending->importance = 0; /* FIXME */
1379 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1380 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1381 pending->msg = &vsmr->header;
1382 vsmr->header.size = htons (msize);
1383 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1384 vsmr->querying_peer = querying_peer;
1385 vsmr->current_successor = current_successor;
1386 vsmr->probable_successor = probable_successor;
1387 vsmr->trail_direction = htonl (trail_direction);
1388 vsmr->trail_id = trail_id;
1390 if (trail_length > 0)
1392 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1393 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1396 /* Send the message to chosen friend. */
1397 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1398 target_friend->pending_count++;
1399 process_friend_queue (target_friend);
1404 * Construct a notify new successor message and send it to target_friend
1405 * @param source_peer Peer which wants to notify to its new successor that it
1406 * could be its predecessor.
1407 * @param successor New successor of @a source_peer
1408 * @param successor_trail List of peers in Trail to reach from
1409 * @a source_peer to @a new_successor, NOT including
1411 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1412 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1413 * @param target_friend Next friend to get this message.
1416 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1417 struct GNUNET_PeerIdentity successor,
1418 const struct GNUNET_PeerIdentity *successor_trail,
1419 unsigned int successor_trail_length,
1420 struct GNUNET_HashCode succesor_trail_id,
1421 struct FriendInfo *target_friend)
1423 struct PeerNotifyNewSuccessorMessage *nsm;
1424 struct P2PPendingMessage *pending;
1425 struct GNUNET_PeerIdentity *peer_list;
1428 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1429 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1431 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1437 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1439 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1443 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1444 pending->importance = 0; /* FIXME */
1445 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1446 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1447 pending->msg = &nsm->header;
1448 nsm->header.size = htons (msize);
1449 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1450 nsm->new_successor = successor;
1451 nsm->source_peer = source_peer;
1452 nsm->trail_id = succesor_trail_id;
1454 if (successor_trail_length > 0)
1456 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1457 memcpy (peer_list, successor_trail,
1458 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1461 /* Send the message to chosen friend. */
1462 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1463 target_friend->pending_count++;
1464 process_friend_queue (target_friend);
1469 * Construct an add_trail message and send it to target_friend
1470 * @param source_peer Source of the trail.
1471 * @param destination_peer Destination of the trail.
1472 * @param trail_id Unique identifier of the trail from
1473 * @a source_peer to @a destination_peer, NOT including the endpoints.
1474 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1475 * NOT including the endpoints.
1476 * @param trail_length Total number of peers in @a trail.
1477 * @param target_friend Next friend to get this message.
1480 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1481 struct GNUNET_PeerIdentity destination_peer,
1482 struct GNUNET_HashCode trail_id,
1483 const struct GNUNET_PeerIdentity *trail,
1484 unsigned int trail_length,
1485 struct FriendInfo *target_friend)
1487 struct PeerAddTrailMessage *adm;
1488 struct GNUNET_PeerIdentity *peer_list;
1489 struct P2PPendingMessage *pending;
1492 msize = sizeof (struct PeerAddTrailMessage) +
1493 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1495 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1501 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1503 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1507 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1508 pending->importance = 0; /* FIXME */
1509 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1510 adm = (struct PeerAddTrailMessage *) &pending[1];
1511 pending->msg = &adm->header;
1512 adm->header.size = htons (msize);
1513 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1514 adm->source_peer = source_peer;
1515 adm->destination_peer = destination_peer;
1516 adm->trail_id = trail_id;
1518 if (trail_length > 0)
1520 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1521 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1523 /* Send the message to chosen friend. */
1524 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1525 target_friend->pending_count++;
1526 process_friend_queue (target_friend);
1532 * Construct a trail compression message and send it to target_friend.
1533 * @param source_peer Source of the trail.
1534 * @param trail_id Unique identifier of trail.
1535 * @param first_friend First hop in compressed trail to reach from source to finger
1536 * @param target_friend Next friend to get this message.
1539 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1540 struct GNUNET_HashCode trail_id,
1541 struct GNUNET_PeerIdentity first_friend,
1542 struct FriendInfo *target_friend)
1544 struct P2PPendingMessage *pending;
1545 struct PeerTrailCompressionMessage *tcm;
1548 msize = sizeof (struct PeerTrailCompressionMessage);
1550 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1556 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1558 GNUNET_STATISTICS_update (GDS_stats,
1559 gettext_noop ("# P2P messages dropped due to full queue"),
1563 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1564 pending->importance = 0; /* FIXME */
1565 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1566 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1567 pending->msg = &tcm->header;
1568 tcm->header.size = htons (msize);
1569 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1570 tcm->source_peer = source_peer;
1571 tcm->new_first_friend = first_friend;
1572 tcm->trail_id = trail_id;
1574 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1575 target_friend->pending_count++;
1576 process_friend_queue (target_friend);
1582 * Search my location in trail. In case I am present more than once in the
1583 * trail (can happen during trail setup), then return my lowest index.
1584 * @param trail List of peers
1585 * @return my_index if found
1586 * -1 if no entry found.
1589 search_my_index (const struct GNUNET_PeerIdentity *trail,
1593 int lowest_index = -1;
1595 for (i = 0; i < trail_length; i++)
1597 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1602 return lowest_index;
1607 * Check if the friend is congested or have reached maximum number of trails
1608 * it can be part of of.
1609 * @param friend Friend to be checked.
1610 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1611 * #GNUNET_YES if friend is either congested or have crossed threshold
1614 is_friend_congested (struct FriendInfo *friend)
1616 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1617 ((0 == GNUNET_TIME_absolute_get_remaining
1618 (friend->congestion_timestamp).rel_value_us)))
1626 * Select closest finger to value.
1627 * @param peer1 First peer
1628 * @param peer2 Second peer
1629 * @param value Value to be compare
1630 * @return Closest peer
1632 const static struct GNUNET_PeerIdentity *
1633 select_closest_finger (const struct GNUNET_PeerIdentity *peer1,
1634 const struct GNUNET_PeerIdentity *peer2,
1637 uint64_t peer1_value;
1638 uint64_t peer2_value;
1640 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1641 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1642 peer1_value = GNUNET_ntohll (peer1_value);
1643 peer2_value = GNUNET_ntohll (peer2_value);
1645 if (peer1_value == value)
1650 if (peer2_value == value)
1655 if (peer2_value < peer1_value)
1657 if ((peer2_value < value) && (value < peer1_value))
1661 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1662 ((0 < value) && (value < peer2_value)))
1668 if (peer1_value < peer2_value)
1670 if ((peer1_value < value) && (value < peer2_value))
1674 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1675 ((0 < value) && (value < peer1_value)))
1685 * Select closest predecessor to value.
1686 * @param peer1 First peer
1687 * @param peer2 Second peer
1688 * @param value Value to be compare
1689 * @return Peer which precedes value in the network.
1691 const static struct GNUNET_PeerIdentity *
1692 select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1,
1693 const struct GNUNET_PeerIdentity *peer2,
1696 uint64_t peer1_value;
1697 uint64_t peer2_value;
1699 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1700 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1701 peer1_value = GNUNET_ntohll (peer1_value);
1702 peer2_value = GNUNET_ntohll (peer2_value);
1704 if (peer1_value == value)
1707 if (peer2_value == value)
1710 if (peer1_value < peer2_value)
1712 if ((peer1_value < value) && (value < peer2_value))
1716 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1717 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1723 if (peer2_value < peer1_value)
1725 if ((peer2_value < value) && (value < peer1_value))
1729 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1730 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1740 * This is a test function to print all the entries of friend table.
1743 test_friend_peermap_print ()
1745 struct FriendInfo *friend;
1746 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1747 struct GNUNET_PeerIdentity print_peer;
1748 struct GNUNET_PeerIdentity key_ret;
1751 print_peer = my_identity;
1752 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1753 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1755 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1757 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1759 (const void **)&friend))
1761 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1762 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1763 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1771 * This is a test function, to print all the entries of finger table.
1774 test_finger_table_print()
1776 struct FingerInfo *finger;
1777 struct GNUNET_PeerIdentity print_peer;
1778 //struct Trail *trail;
1782 print_peer = my_identity;
1783 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1784 for (i = 0; i < MAX_FINGERS; i++)
1786 finger = &finger_table[i];
1788 if (GNUNET_NO == finger->is_present)
1791 print_peer = finger->finger_identity;
1792 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1793 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1796 for (j = 0; j < finger->trails_count; j++)
1798 trail = &finger->trail_list[j];
1799 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1800 struct Trail_Element *element;
1801 element = trail->trail_head;
1802 for (k = 0; k < trail->trail_length; k++)
1804 print_peer = element->peer;
1805 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1806 element = element->next;
1815 * Select the closest peer among two peers (which should not be same)
1816 * with respect to value and finger_table_index
1817 * NOTE: peer1 != peer2
1818 * @param peer1 First peer
1819 * @param peer2 Second peer
1820 * @param value Value relative to which we find the closest
1821 * @param is_predecessor Is value a predecessor or any other finger.
1822 * @return Closest peer among two peers.
1824 const static struct GNUNET_PeerIdentity *
1825 select_closest_peer (const struct GNUNET_PeerIdentity *peer1,
1826 const struct GNUNET_PeerIdentity *peer2,
1828 unsigned int is_predecessor)
1830 if (1 == is_predecessor)
1831 return select_closest_predecessor (peer1, peer2, value);
1833 return select_closest_finger (peer1, peer2, value);
1838 * Iterate over the list of all the trails of a finger. In case the first
1839 * friend to reach the finger has reached trail threshold or is congested,
1840 * then don't select it. In case there multiple available good trails to reach
1841 * to Finger, choose the one with shortest trail length.
1842 * Note: We use length as parameter. But we can use any other suitable parameter
1844 * @param finger Finger
1845 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1846 * and trail length. NULL in case none of the trails are free.
1848 static struct Selected_Finger_Trail *
1849 select_finger_trail (struct FingerInfo *finger)
1851 struct FriendInfo *friend;
1852 struct Trail *iterator;
1853 struct Selected_Finger_Trail *finger_trail;
1855 unsigned int flag = 0;
1858 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1859 GNUNET_assert (finger->trails_count > 0);
1861 for (i = 0; i < finger->trails_count; i++)
1863 iterator = &finger->trail_list[i];
1865 /* No trail stored at this index. */
1866 if (GNUNET_NO == iterator->is_present)
1869 GNUNET_assert (NULL !=
1871 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1872 &iterator->trail_head->peer)));
1874 /* First friend to reach trail is not free. */
1875 if (GNUNET_YES == is_friend_congested (friend))
1884 finger_trail->trail_length = iterator->trail_length;
1885 finger_trail->friend = *friend;
1886 finger_trail->trail_id = iterator->trail_id;
1888 else if (finger_trail->trail_length > iterator->trail_length)
1890 finger_trail->friend = *friend;
1891 finger_trail->trail_id = iterator->trail_id;
1892 finger_trail->trail_length = iterator->trail_length;
1896 /* All the first friend in all the trails to reach to finger are either
1897 congested or have crossed trail threshold. */
1898 if (j == finger->trails_count)
1901 return finger_trail;
1906 * Compare FINGER entry with current successor. If finger's first friend of all
1907 * its trail is not congested and has not crossed trail threshold, then check
1908 * if finger peer identity is closer to final_destination_finger_value than
1909 * current_successor. If yes then update current_successor.
1910 * @param current_successor[in/out]
1914 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1916 struct FingerInfo *finger;
1917 const struct GNUNET_PeerIdentity *closest_peer;
1918 struct Selected_Finger_Trail *finger_trail;
1921 /* Iterate over finger table. */
1922 for (i = 0; i < MAX_FINGERS; i++)
1924 finger = &finger_table[i];
1926 if (GNUNET_NO == finger->is_present)
1929 /* FIXME write correct comment here */
1930 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1931 ¤t_closest_peer->best_known_destination))
1934 /* If I am my own finger, then ignore this finger. */
1935 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1938 /* FIXME: I think a peer should not select itself as its own identity ever.
1939 But it does select. Find out why??*/
1945 /* If finger is a friend, then do nothing. As we have already checked
1946 * for each friend in compare_friend_and_current_successor(). */
1947 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1948 &finger->finger_identity)))
1953 closest_peer = select_closest_peer (&finger->finger_identity,
1954 ¤t_closest_peer->best_known_destination,
1955 current_closest_peer->destination_finger_value,
1956 current_closest_peer->is_predecessor);
1958 if (&finger->finger_identity == closest_peer)
1960 /* Choose one of the trail to reach to finger. */
1961 finger_trail = select_finger_trail (finger);
1963 /* In case no trail found, ignore this finger. */
1964 if (NULL == finger_trail)
1967 current_closest_peer->best_known_destination = finger->finger_identity;
1968 current_closest_peer->next_hop = finger_trail->friend.id;
1969 current_closest_peer->trail_id = finger_trail->trail_id;
1970 //GNUNET_free(finger_trail);//FIXME: where should we free the finger trail.
1978 * Compare friend entry with current successor.
1979 * If friend identity and current_successor is same, then do nothing.
1980 * If friend is not congested and has not crossed trail threshold, then check
1981 * if friend peer identity is closer to final_destination_finger_value than
1982 * current_successor. If yes then update current_successor.
1983 * @param cls closure
1984 * @param key current public key
1985 * @param value struct Closest_Peer
1986 * @return #GNUNET_YES if we should continue to iterate,
1987 * #GNUNET_NO if not.
1990 compare_friend_and_current_closest_peer (void *cls,
1991 const struct GNUNET_PeerIdentity *key,
1994 struct FriendInfo *friend = value;
1995 struct Closest_Peer *current_closest_peer = cls;
1996 const struct GNUNET_PeerIdentity *closest_peer;
1998 /* Friend is either congested or has crossed threshold. */
1999 if (GNUNET_YES == is_friend_congested (friend))
2002 /* If current_closest_peer and friend identity are same, then do nothing.*/
2003 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2004 ¤t_closest_peer->best_known_destination))
2010 closest_peer = select_closest_peer (&friend->id,
2011 ¤t_closest_peer->best_known_destination,
2012 current_closest_peer->destination_finger_value,
2013 current_closest_peer->is_predecessor);
2015 /* Is friend the closest successor? */
2016 if (&friend->id == closest_peer)
2018 current_closest_peer->best_known_destination = friend->id;
2019 current_closest_peer->next_hop = friend->id;
2027 * Initialize current_successor to my_identity.
2028 * @param my_identity My peer identity
2029 * @return Updated closest_peer
2031 static struct Closest_Peer
2032 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2033 uint64_t destination_finger_value,
2034 unsigned int is_predecessor)
2036 struct Closest_Peer current_closest_peer;
2038 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2039 current_closest_peer.destination_finger_value = destination_finger_value;
2040 current_closest_peer.is_predecessor = is_predecessor;
2041 current_closest_peer.next_hop = my_identity;
2042 current_closest_peer.best_known_destination = my_identity;
2044 return current_closest_peer;
2049 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2050 * peer. It could be because of the logic we wrote here. Verify if its correct.
2051 * If not then return immediate_successor.
2053 * Find the successor for destination_finger_value among my_identity, my
2054 * friends and my fingers. Don't consider friends or fingers which are either
2055 * congested or have crossed the threshold.
2056 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2058 * @param destination_finger_value Peer closest to this value will be the next successor.
2059 * @param is_predecessor Are we looking for predecessor or finger?
2060 * @return Successor It is never NULL, in case none of friend or finger is closest,
2061 * then we return my_identity.
2063 static struct Closest_Peer
2064 find_successor (uint64_t destination_finger_value,
2065 unsigned int is_predecessor)
2067 struct Closest_Peer current_closest_peer;
2069 /* Initialize current_successor to my_identity. */
2070 current_closest_peer = init_current_successor (my_identity,
2071 destination_finger_value,
2074 /* Compare each friend entry with current_successor and update current_successor
2075 * with friend if its closest. */
2078 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2079 &compare_friend_and_current_closest_peer,
2080 ¤t_closest_peer));
2082 /* Compare each finger entry with current_successor and update current_successor
2083 * with finger if its closest. */
2084 compare_finger_and_current_successor (¤t_closest_peer);
2086 return current_closest_peer;
2091 * Construct a Put message and send it to target_peer.
2092 * @param key Key for the content
2093 * @param block_type Type of the block
2094 * @param options Routing options
2095 * @param desired_replication_level Desired replication count
2096 * @param best_known_dest Peer to which this message should reach eventually,
2097 * as it is best known destination to me.
2098 * @param intermediate_trail_id Trail id in case
2099 * @param target_peer Peer to which this message will be forwarded.
2100 * @param hop_count Number of hops traversed so far.
2101 * @param put_path_length Total number of peers in @a put_path
2102 * @param put_path Number of peers traversed so far
2103 * @param expiration_time When does the content expire
2104 * @param data Content to store
2105 * @param data_size Size of content @a data in bytes
2108 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2109 enum GNUNET_BLOCK_Type block_type,
2110 enum GNUNET_DHT_RouteOption options,
2111 uint32_t desired_replication_level,
2112 struct GNUNET_PeerIdentity best_known_dest,
2113 struct GNUNET_HashCode intermediate_trail_id,
2114 struct GNUNET_PeerIdentity *target_peer,
2116 uint32_t put_path_length,
2117 struct GNUNET_PeerIdentity *put_path,
2118 struct GNUNET_TIME_Absolute expiration_time,
2119 const void *data, size_t data_size)
2121 struct PeerPutMessage *ppm;
2122 struct P2PPendingMessage *pending;
2123 struct FriendInfo *target_friend;
2124 struct GNUNET_PeerIdentity *pp;
2125 struct GNUNET_PeerIdentity next_hop;
2129 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2130 sizeof (struct PeerPutMessage);
2132 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2134 put_path_length = 0;
2135 msize = data_size + sizeof (struct PeerPutMessage);
2138 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2144 /* This is the first call made from clients file. So, we should search for the
2146 if (NULL == target_peer)
2149 struct Closest_Peer successor;
2151 memcpy (&key_value, key, sizeof (uint64_t));
2152 key_value = GNUNET_ntohll (key_value);
2154 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2155 best_known_dest = successor.best_known_destination;
2156 next_hop = successor.next_hop;
2157 intermediate_trail_id = successor.trail_id;
2159 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2161 /* I am the destination. */
2162 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2163 block_type,data_size,data);
2167 GNUNET_assert (NULL !=
2169 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2173 GNUNET_assert (NULL !=
2175 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2178 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2179 pending->timeout = expiration_time;
2180 ppm = (struct PeerPutMessage *) &pending[1];
2181 pending->msg = &ppm->header;
2182 ppm->header.size = htons (msize);
2183 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2184 ppm->options = htonl (options);
2185 ppm->block_type = htonl (block_type);
2186 ppm->hop_count = htonl (hop_count + 1);
2187 ppm->desired_replication_level = htonl (desired_replication_level);
2188 ppm->put_path_length = htonl (put_path_length);
2189 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2190 ppm->best_known_destination = best_known_dest;
2193 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2194 if (put_path_length != 0)
2196 memcpy (pp, put_path,
2197 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2199 memcpy (&pp[put_path_length], data, data_size);
2200 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2201 target_friend->pending_count++;
2202 process_friend_queue (target_friend);
2207 * Construct a Get message and send it to target_peer.
2208 * @param key Key for the content
2209 * @param block_type Type of the block
2210 * @param options Routing options
2211 * @param desired_replication_level Desired replication count
2212 * @param best_known_dest Peer which should get this message. Same as target peer
2213 * if best_known_dest is a friend else its a finger.
2214 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2215 * in case it is a finger else set to 0.
2216 * @param target_peer Peer to which this message will be forwarded.
2217 * @param hop_count Number of hops traversed so far.
2218 * @param data Content to store
2219 * @param data_size Size of content @a data in bytes
2220 * @param get_path_length Total number of peers in @a get_path
2221 * @param get_path Number of peers traversed so far
2224 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2225 enum GNUNET_BLOCK_Type block_type,
2226 enum GNUNET_DHT_RouteOption options,
2227 uint32_t desired_replication_level,
2228 struct GNUNET_PeerIdentity best_known_dest,
2229 struct GNUNET_HashCode intermediate_trail_id,
2230 struct GNUNET_PeerIdentity *target_peer,
2232 uint32_t get_path_length,
2233 struct GNUNET_PeerIdentity *get_path)
2235 struct PeerGetMessage *pgm;
2236 struct P2PPendingMessage *pending;
2237 struct FriendInfo *target_friend;
2238 struct GNUNET_PeerIdentity *gp;
2241 msize = sizeof (struct PeerGetMessage) +
2242 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2244 /* In this case we don't make get_path_length = 0, as we need get path to
2245 * return the message back to querying client. */
2246 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2252 /* This is the first time we got request from our own client file. */
2253 if (NULL == target_peer)
2256 struct Closest_Peer successor;
2258 memcpy (&key_value, key, sizeof (uint64_t));
2259 key_value = GNUNET_ntohll (key_value);
2260 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2262 best_known_dest = successor.best_known_destination;
2263 intermediate_trail_id = successor.trail_id;
2265 /* I am the destination. I have the data. */
2266 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2269 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2270 NULL, 0, 1, &my_identity, NULL,&my_identity);
2276 GNUNET_assert (NULL !=
2278 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2279 &successor.next_hop)));
2285 GNUNET_assert (NULL !=
2287 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); //FIXME: assertion fails.
2290 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2291 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2292 pending->importance = 0; /* FIXME */
2293 pgm = (struct PeerGetMessage *) &pending[1];
2294 pending->msg = &pgm->header;
2295 pgm->header.size = htons (msize);
2296 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2297 pgm->get_path_length = htonl (get_path_length);
2298 pgm->best_known_destination = best_known_dest;
2300 pgm->intermediate_trail_id = intermediate_trail_id;
2301 pgm->hop_count = htonl (hop_count + 1);
2302 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2304 if (get_path_length != 0)
2306 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2309 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2310 target_friend->pending_count++;
2311 process_friend_queue (target_friend);
2316 * Send the get result to requesting client.
2317 * @param key Key of the requested data.
2318 * @param type Block type
2319 * @param target_peer Next peer to forward the message to.
2320 * @param source_peer Peer which has the data for the key.
2321 * @param put_path_length Number of peers in @a put_path
2322 * @param put_path Path taken to put the data at its stored location.
2323 * @param get_path_length Number of peers in @a get_path
2324 * @param get_path Path taken to reach to the location of the key.
2325 * @param expiration When will this result expire?
2326 * @param data Payload to store
2327 * @param data_size Size of the @a data
2330 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2331 enum GNUNET_BLOCK_Type type,
2332 const struct GNUNET_PeerIdentity *target_peer,
2333 const struct GNUNET_PeerIdentity *source_peer,
2334 unsigned int put_path_length,
2335 const struct GNUNET_PeerIdentity *put_path,
2336 unsigned int get_path_length,
2337 const struct GNUNET_PeerIdentity *get_path,
2338 struct GNUNET_TIME_Absolute expiration,
2339 const void *data, size_t data_size)
2341 struct PeerGetResultMessage *get_result;
2342 struct GNUNET_PeerIdentity *paths;
2343 struct P2PPendingMessage *pending;
2344 struct FriendInfo *target_friend;
2345 int current_path_index;
2348 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2350 sizeof (struct PeerGetResultMessage);
2352 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2358 current_path_index = 0;
2359 if(get_path_length > 0)
2361 current_path_index = search_my_index(get_path, get_path_length);
2362 if (-1 == current_path_index)
2368 if (0 == current_path_index)
2370 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2371 get_path, put_path_length,
2372 put_path, type, data_size, data);
2376 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2377 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2378 pending->importance = 0;
2379 get_result = (struct PeerGetResultMessage *)&pending[1];
2380 pending->msg = &get_result->header;
2381 get_result->header.size = htons (msize);
2382 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2383 get_result->key = *key;
2384 get_result->querying_peer = *source_peer;
2385 get_result->expiration_time = expiration;
2386 get_result->get_path_length = htonl (get_path_length);
2387 get_result->put_path_length = htonl (put_path_length);
2388 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2389 memcpy (paths, put_path,
2390 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2391 memcpy (&paths[put_path_length], get_path,
2392 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2393 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2395 GNUNET_assert (NULL !=
2397 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2398 &get_path[current_path_index - 1])));
2399 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2400 target_friend->pending_count++;
2401 process_friend_queue (target_friend);
2406 * Randomly choose one of your friends (which is not congested and have not crossed
2407 * trail threshold) from the friend_peermap
2408 * @return Friend Randomly chosen friend.
2409 * NULL in case friend peermap is empty, or all the friends are either
2410 * congested or have crossed trail threshold.
2412 static struct FriendInfo *
2413 select_random_friend ()
2415 unsigned int current_size;
2418 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2419 struct GNUNET_PeerIdentity key_ret;
2420 struct FriendInfo *friend;
2422 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2425 if (0 == current_size)
2428 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2429 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2431 /* Iterate till you don't reach to index. */
2432 for (j = 0; j < index ; j++)
2433 GNUNET_assert (GNUNET_YES ==
2434 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2437 /* Reset the index in friend peermap to 0 as we reached to the end. */
2438 if (j == current_size)
2441 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2442 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2446 /* Get the friend stored at the index, j*/
2447 GNUNET_assert (GNUNET_YES ==
2448 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2450 (const void **)&friend));
2452 /* This friend is not congested and has not crossed trail threshold. */
2453 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2454 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2460 } while (j != index);
2462 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2468 * Compute 64 bit value of finger_identity corresponding to a finger index using
2470 * For all fingers, n.finger[i] = n + pow (2,i),
2471 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2472 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2473 * @param finger_index Index corresponding to which we calculate 64 bit value.
2474 * @return 64 bit value.
2477 compute_finger_identity_value (unsigned int finger_index)
2481 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2482 my_id64 = GNUNET_ntohll (my_id64);
2484 /* Are we looking for immediate predecessor? */
2485 if (PREDECESSOR_FINGER_ID == finger_index)
2486 return (my_id64 - 1);
2489 uint64_t add = (uint64_t)1 << finger_index;
2490 return (my_id64 + add);
2496 * Choose a random friend. Calculate the next finger identity to search,from
2497 * current_search_finger_index. Start looking for the trail to reach to
2498 * finger identity through this random friend.
2500 * @param cls closure for this task
2501 * @param tc the context under which the task is running
2504 send_find_finger_trail_message (void *cls,
2505 const struct GNUNET_SCHEDULER_TaskContext *tc)
2507 struct FriendInfo *target_friend;
2508 struct GNUNET_TIME_Relative next_send_time;
2509 struct GNUNET_HashCode trail_id;
2510 struct GNUNET_HashCode intermediate_trail_id;
2511 unsigned int is_predecessor;
2512 uint64_t finger_id_value;
2514 /* Schedule another send_find_finger_trail_message task. */
2515 next_send_time.rel_value_us =
2516 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
2517 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2518 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2519 find_finger_trail_task =
2520 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
2523 /* No space in my routing table. (Source and destination peers also store entries
2524 * in their routing table). */
2525 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2529 target_friend = select_random_friend ();
2530 if (NULL == target_friend)
2535 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2537 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2542 /* Generate a unique trail id for trail we are trying to setup. */
2543 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2544 &trail_id, sizeof (trail_id));
2545 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2547 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2548 target_friend->id, target_friend, 0, NULL,
2549 is_predecessor, trail_id,
2550 intermediate_trail_id);
2555 * In case there are already maximum number of possible trails to reach to a
2556 * finger, then check if the new trail's length is lesser than any of the
2558 * If yes then replace that old trail by new trail.
2560 * Note: Here we are taking length as a parameter to choose the best possible
2561 * trail, but there could be other parameters also like:
2562 * 1. duration of existence of a trail - older the better.
2563 * 2. if the new trail is completely disjoint than the
2564 * other trails, then may be choosing it is better.
2566 * @param existing_finger
2567 * @param new_finger_trail
2568 * @param new_finger_trail_length
2569 * @param new_finger_trail_id
2572 select_and_replace_trail (struct FingerInfo *existing_finger,
2573 const struct GNUNET_PeerIdentity *new_trail,
2574 unsigned int new_trail_length,
2575 struct GNUNET_HashCode new_trail_id)
2577 struct Trail *trail_list_iterator;
2578 unsigned int largest_trail_length;
2579 unsigned int largest_trail_index;
2580 struct Trail_Element *trail_element;
2583 largest_trail_length = new_trail_length;
2584 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2586 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2588 for (i = 0; i < existing_finger->trails_count; i++)
2590 trail_list_iterator = &existing_finger->trail_list[i];
2591 if (trail_list_iterator->trail_length > largest_trail_length)
2593 largest_trail_length = trail_list_iterator->trail_length;
2594 largest_trail_index = i;
2598 /* New trail is not better than existing ones. Send trail teardown. */
2599 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2601 struct GNUNET_PeerIdentity next_hop;
2603 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2604 GDS_ROUTING_remove_trail (new_trail_id);
2605 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2606 GDS_ROUTING_SRC_TO_DEST,
2611 /* Send trail teardown message across the replaced trail. */
2612 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2613 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2614 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2615 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2616 GDS_ROUTING_SRC_TO_DEST,
2617 replace_trail->trail_head->peer);
2618 /* Free the trail. */
2619 while (NULL != (trail_element = replace_trail->trail_head))
2621 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2622 replace_trail->trail_tail, trail_element);
2623 GNUNET_free_non_null (trail_element);
2626 /* Add new trial at that location. */
2627 replace_trail->is_present = GNUNET_YES;
2628 replace_trail->trail_length = new_trail_length;
2629 replace_trail->trail_id = new_trail_id;
2630 //FIXME: Do we need to add pointers for head and tail.
2632 while (i < new_trail_length)
2634 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2635 element->peer = new_trail[i];
2637 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2638 replace_trail->trail_tail,
2645 * Check if the new trail to reach to finger is unique or do we already have
2646 * such a trail present for finger.
2647 * @param existing_finger Finger identity
2648 * @param new_trail New trail to reach @a existing_finger
2649 * @param trail_length Total number of peers in new_trail.
2650 * @return #GNUNET_YES if the new trail is unique
2651 * #GNUNET_NO if same trail is already present.
2654 is_new_trail_unique (struct FingerInfo *existing_finger,
2655 const struct GNUNET_PeerIdentity *new_trail,
2656 unsigned int trail_length)
2658 struct Trail *trail_list_iterator;
2659 struct Trail_Element *trail_element;
2662 int trail_unique = GNUNET_NO;
2664 GNUNET_assert (existing_finger->trails_count > 0);
2666 /* Iterate over list of trails. */
2667 for (i = 0; i < existing_finger->trails_count; i++)
2669 trail_list_iterator = &existing_finger->trail_list[i];
2670 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2672 /* New trail and existing trail length are not same. */
2673 if (trail_list_iterator->trail_length != trail_length)
2675 trail_unique = GNUNET_YES;
2679 trail_element = trail_list_iterator->trail_head;
2680 for (j = 0; j < trail_list_iterator->trail_length; j++)
2682 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2683 &trail_element->peer))
2685 trail_unique = GNUNET_YES;
2688 trail_element = trail_element->next;
2691 trail_unique = GNUNET_NO;
2694 return trail_unique;
2699 * Add a new trail to existing finger. This function is called only when finger
2700 * is not my own identity or a friend.
2701 * @param existing_finger Finger
2702 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2703 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2704 * @param new_finger_trail_id Unique identifier of the trail.
2707 add_new_trail (struct FingerInfo *existing_finger,
2708 const struct GNUNET_PeerIdentity *new_trail,
2709 unsigned int new_trail_length,
2710 struct GNUNET_HashCode new_trail_id)
2712 struct Trail *trail_list_iterator;
2713 struct FriendInfo *first_friend;
2716 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2722 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2723 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2724 trail_list_iterator->trail_id = new_trail_id;
2725 trail_list_iterator->trail_length = new_trail_length;
2726 existing_finger->trails_count++;
2727 trail_list_iterator->is_present = GNUNET_YES;
2729 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2730 &existing_finger->finger_identity)));
2731 /* If finger is a friend then we never call this function. */
2732 GNUNET_assert (new_trail_length > 0);
2734 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2736 first_friend->trails_count++;
2738 for (i = 0; i < new_trail_length; i++)
2740 struct Trail_Element *element;
2742 element = GNUNET_new (struct Trail_Element);
2743 element->peer = new_trail[i];
2744 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2745 trail_list_iterator->trail_tail,
2748 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2754 * FIXME Check if this function is called for opposite direction if yes then
2755 * take it as parameter.
2756 * Get the next hop to send trail teardown message from routing table and
2757 * then delete the entry from routing table. Send trail teardown message for a
2758 * specific trail of a finger.
2759 * @param finger Finger whose trail is to be removed.
2760 * @param trail List of peers in trail from me to a finger, NOT including
2764 send_trail_teardown (struct FingerInfo *finger,
2765 struct Trail *trail)
2767 struct FriendInfo *friend;
2768 struct GNUNET_PeerIdentity *next_hop;
2770 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2771 GDS_ROUTING_SRC_TO_DEST);
2773 if (NULL == next_hop)
2778 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2781 GNUNET_assert (trail->is_present == GNUNET_YES);
2783 /* Finger is not a friend. */
2784 if (trail->trail_length > 0)
2786 GNUNET_assert (NULL != (friend =
2787 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2788 &trail->trail_head->peer)));
2792 GNUNET_assert (NULL != (friend =
2793 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2794 &finger->finger_identity)));
2797 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2798 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2799 friend->trails_count--;
2800 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2801 GDS_ROUTING_SRC_TO_DEST,
2807 * Send trail teardown message across all the trails to reach to finger.
2808 * @param finger Finger whose all the trail should be freed.
2811 send_all_finger_trails_teardown (struct FingerInfo *finger)
2815 for (i = 0; i < finger->trails_count; i++)
2817 struct Trail *trail;
2819 trail = &finger->trail_list[i];
2820 GNUNET_assert (trail->is_present == GNUNET_YES);
2821 send_trail_teardown (finger, trail);
2822 trail->is_present = GNUNET_NO;
2828 * Free a specific trail
2829 * @param trail List of peers to be freed.
2832 free_trail (struct Trail *trail)
2834 struct Trail_Element *trail_element;
2836 while (NULL != (trail_element = trail->trail_head))
2838 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2841 GNUNET_free_non_null (trail_element);
2843 trail->trail_head = NULL;
2844 trail->trail_tail = NULL;
2849 * Free finger and its trail.
2850 * @param finger Finger to be freed.
2853 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2855 struct Trail *trail;
2858 /* Free all the trails to reach to finger */
2859 for (i = 0; i < finger->trails_count; i++)
2861 trail = &finger->trail_list[i];
2862 //FIXME: Check if there are any missing entry in this list because of
2863 // how we insert. If not then no need of this check.
2864 if (GNUNET_NO == trail->is_present)
2867 if (trail->trail_length > 0)
2871 trail->is_present = GNUNET_NO;
2874 finger->is_present = GNUNET_NO;
2875 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2880 * FIXME: ensure that you are not adding any trail to reach to a friend which
2881 * is a finger. Also decide on should you increment trails count of a friend
2882 * which is also a finger.
2883 * Add a new entry in finger table at finger_table_index.
2884 * In case finger identity is me or a friend, then don't add a trail. NOTE
2885 * trail length to reach to a finger can be 0 only if the finger is a friend
2887 * In case a finger is a friend, then increment the trails count of the friend.
2888 * @param finger_identity Peer Identity of new finger
2889 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2890 * @param finger_trail_length Total number of peers in @a finger_trail.
2891 * @param trail_id Unique identifier of the trail.
2892 * @param finger_table_index Index in finger table.
2895 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2896 const struct GNUNET_PeerIdentity *finger_trail,
2897 unsigned int finger_trail_length,
2898 struct GNUNET_HashCode trail_id,
2899 unsigned int finger_table_index)
2901 struct FingerInfo *new_entry;
2902 struct FriendInfo *first_trail_hop;
2903 struct Trail *trail;
2906 new_entry = GNUNET_new (struct FingerInfo);
2907 new_entry->finger_identity = finger_identity;
2908 new_entry->finger_table_index = finger_table_index;
2909 new_entry->is_present = GNUNET_YES;
2911 /* If the new entry is my own identity. */
2912 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2914 new_entry->trails_count = 0;
2915 finger_table[finger_table_index] = *new_entry;
2916 GNUNET_free (new_entry);
2920 /* If finger is a friend, then we don't actually have a trail.
2921 * Just a trail id */
2922 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2925 new_entry->trail_list[0].trail_id = trail_id;
2926 new_entry->trails_count = 1;
2927 new_entry->trail_list[0].is_present = GNUNET_YES;
2928 new_entry->trail_list[0].trail_length = 0;
2929 new_entry->trail_list[0].trail_head = NULL;
2930 new_entry->trail_list[0].trail_tail = NULL;
2931 finger_table[finger_table_index] = *new_entry;
2932 GNUNET_assert (NULL !=
2934 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2935 &finger_identity)));
2937 first_trail_hop->trails_count++;
2938 GNUNET_free (new_entry);
2942 /* finger trail length can be 0 only in case if finger is my identity or
2943 finger is friend. We should never reach here. */
2944 GNUNET_assert (finger_trail_length > 0);
2946 GNUNET_assert (NULL !=
2948 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2949 &finger_trail[0])));
2950 new_entry->trails_count = 1;
2951 first_trail_hop->trails_count++;
2953 /* Copy the finger trail into trail. */
2954 trail = GNUNET_new (struct Trail);
2955 while (i < finger_trail_length)
2957 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2959 element->next = NULL;
2960 element->prev = NULL;
2961 element->peer = finger_trail[i];
2962 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2968 /* Add trail to trail list. */
2969 new_entry->trail_list[0].trail_head = trail->trail_head;
2970 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2971 new_entry->trail_list[0].trail_length = finger_trail_length;
2972 new_entry->trail_list[0].trail_id = trail_id;
2973 new_entry->trail_list[0].is_present = GNUNET_YES;
2974 finger_table[finger_table_index] = *new_entry;
2975 //GNUNET_free (new_entry);
2976 //GNUNET_free (trail);
2982 * Scan the trail to check if there is any other friend in the trail other than
2983 * first hop. If yes then shortcut the trail, send trail compression message to
2984 * peers which are no longer part of trail and send back the updated trail
2985 * and trail_length to calling function.
2986 * @param finger_identity Finger whose trail we will scan.
2987 * @param finger_trail [in, out] Trail to reach from source to finger,
2988 * @param finger_trail_length Total number of peers in original finger_trail.
2989 * @param finger_trail_id Unique identifier of the finger trail.
2990 * @return updated trail length in case we shortcut the trail, else original
2993 static struct GNUNET_PeerIdentity *
2994 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2995 const struct GNUNET_PeerIdentity *trail,
2996 unsigned int trail_length,
2997 struct GNUNET_HashCode trail_id,
2998 int *new_trail_length)
3000 struct FriendInfo *target_friend;
3001 struct GNUNET_PeerIdentity *new_trail;
3004 /* I am my own finger. */
3005 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3007 *new_trail_length = 0;
3011 if (0 == trail_length)
3013 *new_trail_length = 0;
3017 /* If finger identity is a friend. */
3018 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3020 *new_trail_length = 0;
3022 /* If there is trail to reach this finger/friend */
3023 if (trail_length > 0)
3025 /* Finger is your first friend. */
3026 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3027 GNUNET_assert (NULL !=
3029 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3033 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3034 trail_id, finger_identity,
3040 /* For other cases, when its neither a friend nor my own identity.*/
3041 for (i = trail_length - 1; i > 0; i--)
3043 /* If the element at this index in trail is a friend. */
3044 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3046 struct FriendInfo *target_friend;
3049 GNUNET_assert (NULL !=
3051 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3053 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3054 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3059 /* Copy the trail from index i to index (trail_length -1) into a new trail
3060 * and update new trail length */
3061 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3062 while (i < trail_length)
3064 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3068 *new_trail_length = j+1;
3069 GNUNET_assert((j+1) == (trail_length - 1)); //FIXME: remove it afterwards.
3074 /* If we did not compress the trail, return the original trail back.*/
3075 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3076 *new_trail_length = trail_length;
3077 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3083 * Periodic task to verify current successor. There can be multiple trails to reach
3084 * to successor, choose the shortest one and send verify successor message
3085 * across that trail.
3086 * @param cls closure for this task
3087 * @param tc the context under which the task is running
3090 send_verify_successor_message (void *cls,
3091 const struct GNUNET_SCHEDULER_TaskContext *tc)
3093 struct FriendInfo *target_friend;
3094 struct GNUNET_HashCode trail_id;
3096 struct GNUNET_TIME_Relative next_send_time;
3097 struct Trail *trail;
3098 struct Trail_Element *element;
3099 unsigned int trail_length;
3101 struct FingerInfo *successor;
3103 /* Schedule another send_find_finger_trail_message task. */
3104 next_send_time.rel_value_us =
3105 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3106 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3107 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3108 send_verify_successor_task =
3109 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3112 successor = &finger_table[0];
3114 trail = &successor->trail_list[i];
3116 /* Store the successor for path tracking */
3117 if (track_topology && (NULL != GDS_stats))
3123 my_id_str = GNUNET_strdup (GNUNET_i2s (&my_identity));
3124 succ_id_str = GNUNET_strdup (GNUNET_i2s
3125 (&successor->finger_identity));
3126 GNUNET_asprintf (&key, "XDHT:0:%.4s:%.4s", my_id_str, succ_id_str);
3127 GNUNET_free (my_id_str);
3128 GNUNET_free (succ_id_str);
3129 GNUNET_STATISTICS_update (GDS_stats, "key", 1, 0);
3133 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3134 &successor->finger_identity));
3136 /* Trail stored at this index. */
3137 GNUNET_assert (GNUNET_YES == trail->is_present);
3139 trail_id = trail->trail_id;
3140 trail_length = trail->trail_length;
3142 if (trail_length > 0)
3144 /* Copy the trail into peer list. */
3145 struct GNUNET_PeerIdentity peer_list[trail_length];
3147 element = trail->trail_head;
3148 while (j < trail_length)
3150 peer_list[j] = element->peer;
3151 element = element->next;
3155 GNUNET_assert (NULL != (target_friend =
3156 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3158 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3159 successor->finger_identity,
3160 trail_id, peer_list, trail_length,
3166 GNUNET_assert (NULL != (target_friend =
3167 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3168 &successor->finger_identity)));
3169 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3170 successor->finger_identity,
3179 * Update the current search finger index.
3181 * FIXME document parameters!
3184 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3185 unsigned int finger_table_index)
3187 struct FingerInfo *successor;
3189 /* FIXME correct this: only move current index periodically */
3190 if (finger_table_index != current_search_finger_index)
3193 successor = &finger_table[0];
3194 GNUNET_assert (GNUNET_YES == successor->is_present);
3196 /* We were looking for immediate successor. */
3197 if (0 == current_search_finger_index)
3199 /* Start looking for immediate predecessor. */
3200 current_search_finger_index = PREDECESSOR_FINGER_ID;
3202 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3204 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3205 send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3211 current_search_finger_index = current_search_finger_index - 1;
3217 * Get the least significant bit set in val.
3220 * @return Position of first bit set, 65 in case of error.
3223 find_set_bit (uint64_t val)
3243 return 65; /* Some other bit was set to 1 as well. */
3250 * Calculate finger_table_index from initial 64 bit finger identity value that
3251 * we send in trail setup message.
3252 * @param ultimate_destination_finger_value Value that we calculated from our
3253 * identity and finger_table_index.
3254 * @param is_predecessor Is the entry for predecessor or not?
3255 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3256 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3259 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3260 unsigned int is_predecessor)
3264 unsigned int finger_table_index;
3266 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3267 my_id64 = GNUNET_ntohll (my_id64);
3269 /* Is this a predecessor finger? */
3270 if (1 == is_predecessor)
3272 diff = my_id64 - ultimate_destination_finger_value;
3274 finger_table_index = PREDECESSOR_FINGER_ID;
3276 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3281 diff = ultimate_destination_finger_value - my_id64;
3282 finger_table_index = find_set_bit (diff);
3284 return finger_table_index;
3289 * Remove finger and its associated data structures from finger table.
3290 * @param finger Finger to be removed.
3293 remove_existing_finger (struct FingerInfo *existing_finger,
3294 unsigned int finger_table_index)
3296 struct FingerInfo *finger;
3298 finger = &finger_table[finger_table_index];
3299 GNUNET_assert (GNUNET_YES == finger->is_present);
3301 /* If I am my own finger, then we have no trails. */
3302 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3305 finger->is_present = GNUNET_NO;
3306 memset ((void *)&finger_table[finger_table_index], 0,
3307 sizeof (finger_table[finger_table_index]));
3311 /* For all other fingers, send trail teardown across all the trails to reach
3312 finger, and free the finger. */
3313 send_all_finger_trails_teardown (finger);
3314 free_finger (finger, finger_table_index);
3320 * Check if there is already an entry in finger_table at finger_table_index.
3321 * We get the finger_table_index from 64bit finger value we got from the network.
3322 * -- If yes, then select the closest finger.
3323 * -- If new and existing finger are same, then check if you can store more
3325 * -- If yes then add trail, else keep the best trails to reach to the
3327 * -- If the new finger is closest, remove the existing entry, send trail
3328 * teardown message across all the trails to reach the existing entry.
3329 * Add the new finger.
3330 * -- If new and existing finger are different, and existing finger is closest
3332 * -- Update current_search_finger_index.
3333 * @param finger_identity Peer Identity of new finger
3334 * @param finger_trail Trail to reach the new finger
3335 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3336 * @param is_predecessor Is this entry for predecessor in finger_table?
3337 * @param finger_value 64 bit value of finger identity that we got from network.
3338 * @param finger_trail_id Unique identifier of @finger_trail.
3341 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3342 const struct GNUNET_PeerIdentity *finger_trail,
3343 unsigned int finger_trail_length,
3344 unsigned int is_predecessor,
3345 uint64_t finger_value,
3346 struct GNUNET_HashCode finger_trail_id)
3348 struct FingerInfo *existing_finger;
3349 const struct GNUNET_PeerIdentity *closest_peer;
3350 struct FingerInfo *successor;
3351 int updated_finger_trail_length;
3352 unsigned int finger_table_index;
3354 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3355 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3357 /* Invalid finger_table_index. */
3358 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3360 GNUNET_break_op (0);
3364 /* New entry same as successor. */
3365 if ((0 != finger_table_index) &&
3366 (PREDECESSOR_FINGER_ID != finger_table_index))
3368 successor = &finger_table[0];
3369 if (GNUNET_NO == successor->is_present)
3371 GNUNET_break_op (0);
3374 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3375 &successor->finger_identity))
3377 current_search_finger_index = 0;
3380 struct FingerInfo *prev_finger;
3381 prev_finger = &finger_table[finger_table_index - 1];
3382 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3383 &prev_finger->finger_identity))
3385 current_search_finger_index--;
3390 existing_finger = &finger_table[finger_table_index];
3392 /* No entry present in finger_table for given finger map index. */
3393 if (GNUNET_NO == existing_finger->is_present)
3395 struct GNUNET_PeerIdentity *updated_trail;
3397 /* Shorten the trail if possible. */
3398 updated_finger_trail_length = finger_trail_length;
3399 updated_trail = scan_and_compress_trail (finger_identity, finger_trail,
3400 finger_trail_length,
3402 &updated_finger_trail_length);
3404 add_new_finger (finger_identity, updated_trail,
3405 updated_finger_trail_length,
3406 finger_trail_id, finger_table_index);
3407 update_current_search_finger_index (finger_identity,
3408 finger_table_index);
3413 /* If existing entry and finger identity are not same. */
3414 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3417 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3422 /* If the new finger is the closest peer. */
3423 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3425 struct GNUNET_PeerIdentity *updated_trail;
3426 /* Shorten the trail if possible. */
3427 updated_finger_trail_length = finger_trail_length;
3429 scan_and_compress_trail (finger_identity, finger_trail,
3430 finger_trail_length, finger_trail_id,
3431 &updated_finger_trail_length);
3432 remove_existing_finger (existing_finger, finger_table_index);
3433 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3434 finger_trail_id, finger_table_index);
3439 /* Existing finger is the closest one. We need to send trail teardown
3440 across the trail setup in routing table of all the peers. */
3441 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3443 if (finger_trail_length > 0)
3444 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3445 GDS_ROUTING_SRC_TO_DEST,
3448 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3449 GDS_ROUTING_SRC_TO_DEST,
3456 /* If both new and existing entry are same as my_identity, then do nothing. */
3457 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3462 /* If the existing finger is not a friend. */
3464 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3465 &existing_finger->finger_identity))
3467 struct GNUNET_PeerIdentity *updated_trail;
3469 /* Shorten the trail if possible. */
3470 updated_finger_trail_length = finger_trail_length;
3472 scan_and_compress_trail (finger_identity, finger_trail,
3473 finger_trail_length, finger_trail_id,
3474 &updated_finger_trail_length);
3475 /* If there is space to store more trails. */
3476 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3477 add_new_trail (existing_finger, updated_trail,
3478 updated_finger_trail_length, finger_trail_id);
3480 select_and_replace_trail (existing_finger, updated_trail,
3481 updated_finger_trail_length, finger_trail_id);
3485 update_current_search_finger_index (finger_identity, finger_table_index);
3490 * Core handler for P2P put messages.
3491 * @param cls closure
3492 * @param peer sender of the request
3493 * @param message message
3494 * @return #GNUNET_OK to keep the connection open,
3495 * #GNUNET_SYSERR to close it (signal serious error)
3498 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3499 const struct GNUNET_MessageHeader *message)
3501 struct PeerPutMessage *put;
3502 struct GNUNET_PeerIdentity *put_path;
3503 struct GNUNET_PeerIdentity best_known_dest;
3504 struct GNUNET_HashCode intermediate_trail_id;
3505 struct GNUNET_PeerIdentity *next_hop;
3506 enum GNUNET_DHT_RouteOption options;
3507 struct GNUNET_HashCode test_key;
3511 size_t payload_size;
3514 msize = ntohs (message->size);
3515 if (msize < sizeof (struct PeerPutMessage))
3517 GNUNET_break_op (0);
3521 put = (struct PeerPutMessage *) message;
3522 putlen = ntohl (put->put_path_length);
3526 sizeof (struct PeerPutMessage) +
3527 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3529 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3531 GNUNET_break_op (0);
3535 best_known_dest = put->best_known_destination;
3536 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3537 payload = &put_path[putlen];
3538 options = ntohl (put->options);
3539 intermediate_trail_id = put->intermediate_trail_id;
3541 payload_size = msize - (sizeof (struct PeerPutMessage) +
3542 putlen * sizeof (struct GNUNET_PeerIdentity));
3544 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3545 payload, payload_size, &test_key))
3548 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3550 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3551 GNUNET_break_op (0);
3552 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3553 "PUT with key `%s' for block with key %s\n",
3554 put_s, GNUNET_h2s_full (&test_key));
3555 GNUNET_free (put_s);
3560 GNUNET_break_op (0);
3563 /* cannot verify, good luck */
3567 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3569 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3570 ntohl (put->block_type),
3572 NULL, 0, /* bloom filer */
3573 NULL, 0, /* xquery */
3574 payload, payload_size))
3576 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3577 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3580 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3581 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3582 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3583 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3584 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3585 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3587 GNUNET_break_op (0);
3592 /* extend 'put path' by sender */
3593 struct GNUNET_PeerIdentity pp[putlen + 1];
3594 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3596 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3603 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3604 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3606 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3607 GDS_ROUTING_SRC_TO_DEST);
3608 if (NULL == next_hop)
3610 GNUNET_STATISTICS_update (GDS_stats,
3611 gettext_noop ("# Next hop to forward the packet not found "
3612 "trail setup request, packet dropped."),
3614 return GNUNET_SYSERR;
3619 struct Closest_Peer successor;
3620 key_value = GNUNET_ntohll (key_value);
3621 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3623 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3624 *next_hop = successor.next_hop;
3625 intermediate_trail_id = successor.trail_id;
3626 best_known_dest = successor.best_known_destination;
3629 GDS_CLIENTS_process_put (options,
3630 ntohl (put->block_type),
3631 ntohl (put->hop_count),
3632 ntohl (put->desired_replication_level),
3634 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3639 /* I am the final destination */
3640 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3642 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3643 &(put->key),putlen, pp, ntohl (put->block_type),
3644 payload_size, payload);
3648 GDS_NEIGHBOURS_send_put (&put->key,
3649 ntohl (put->block_type),ntohl (put->options),
3650 ntohl (put->desired_replication_level),
3651 best_known_dest, intermediate_trail_id, next_hop,
3652 ntohl (put->hop_count), putlen, pp,
3653 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3654 payload, payload_size);
3661 * Core handler for p2p get requests.
3663 * @param cls closure
3664 * @param peer sender of the request
3665 * @param message message
3666 * @return #GNUNET_OK to keep the connection open,
3667 * #GNUNET_SYSERR to close it (signal serious error)
3670 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3671 const struct GNUNET_MessageHeader *message)
3673 const struct PeerGetMessage *get;
3674 const struct GNUNET_PeerIdentity *get_path;
3675 struct GNUNET_PeerIdentity best_known_dest;
3676 struct GNUNET_HashCode intermediate_trail_id;
3677 struct GNUNET_PeerIdentity *next_hop;
3678 uint32_t get_length;
3682 msize = ntohs (message->size);
3683 if (msize < sizeof (struct PeerGetMessage))
3685 GNUNET_break_op (0);
3689 get = (const struct PeerGetMessage *)message;
3690 get_length = ntohl (get->get_path_length);
3691 best_known_dest = get->best_known_destination;
3692 intermediate_trail_id = get->intermediate_trail_id;
3693 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3696 sizeof (struct PeerGetMessage) +
3697 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3699 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3701 GNUNET_break_op (0);
3705 /* Add sender to get path */
3706 struct GNUNET_PeerIdentity gp[get_length + 1];
3708 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3709 gp[get_length] = *peer;
3710 get_length = get_length + 1;
3712 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3713 key_value = GNUNET_ntohll (key_value);
3715 /* I am not the final destination. I am part of trail to reach final dest. */
3716 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3718 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3719 GDS_ROUTING_SRC_TO_DEST);
3720 if (NULL == next_hop)
3722 GNUNET_STATISTICS_update (GDS_stats,
3723 gettext_noop ("# Next hop to forward the packet not found "
3724 "GET request, packet dropped."),
3726 return GNUNET_SYSERR;
3731 struct Closest_Peer successor;
3733 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3734 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3735 *next_hop = successor.next_hop;
3736 best_known_dest = successor.best_known_destination;
3737 intermediate_trail_id = successor.trail_id;
3740 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3741 get->desired_replication_level, get->get_path_length,
3743 /* I am the final destination. */
3744 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3746 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3748 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3749 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3750 get_length = get_length + 1;
3752 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3753 get_length, final_get_path,
3754 &final_get_path[get_length-2], &my_identity);
3758 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3759 get->desired_replication_level, best_known_dest,
3760 intermediate_trail_id, next_hop, 0,
3768 * Core handler for get result
3769 * @param cls closure
3770 * @param peer sender of the request
3771 * @param message message
3772 * @return #GNUNET_OK to keep the connection open,
3773 * #GNUNET_SYSERR to close it (signal serious error)
3776 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3777 const struct GNUNET_MessageHeader *message)
3779 const struct PeerGetResultMessage *get_result;
3780 const struct GNUNET_PeerIdentity *get_path;
3781 const struct GNUNET_PeerIdentity *put_path;
3782 const void *payload;
3783 size_t payload_size;
3785 unsigned int getlen;
3786 unsigned int putlen;
3787 int current_path_index;
3789 msize = ntohs (message->size);
3790 if (msize < sizeof (struct PeerGetResultMessage))
3792 GNUNET_break_op (0);
3796 get_result = (const struct PeerGetResultMessage *)message;
3797 getlen = ntohl (get_result->get_path_length);
3798 putlen = ntohl (get_result->put_path_length);
3801 sizeof (struct PeerGetResultMessage) +
3802 getlen * sizeof (struct GNUNET_PeerIdentity) +
3803 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3805 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3807 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3809 GNUNET_break_op (0);
3813 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3814 get_path = &put_path[putlen];
3815 payload = (const void *) &get_path[getlen];
3816 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3817 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3819 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3821 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3822 getlen, get_path, putlen,
3823 put_path, get_result->type, payload_size, payload);
3828 current_path_index = search_my_index (get_path, getlen);
3829 if (-1 == current_path_index )
3832 return GNUNET_SYSERR;
3834 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3835 &get_path[current_path_index - 1],
3836 &(get_result->querying_peer), putlen, put_path,
3837 getlen, get_path, get_result->expiration_time,
3838 payload, payload_size);
3841 return GNUNET_SYSERR;
3846 * Find the next hop to pass trail setup message. First find the local best known
3847 * hop from your own identity, friends and finger. If you were part of trail,
3848 * then get the next hop from routing table. Compare next_hop from routing table
3849 * and local best known hop, and return the closest one to final_dest_finger_val
3850 * @param final_dest_finger_val 64 bit value of finger identity
3851 * @param intermediate_trail_id If you are part of trail to reach to some other
3852 * finger, then it is the trail id to reach to
3853 * that finger, else set to 0.
3854 * @param is_predecessor Are we looking for closest successor or predecessor.
3855 * @param current_dest In case you are part of trail, then finger to which
3856 * we should forward the message. Else my own identity
3857 * @return Closest Peer for @a final_dest_finger_val
3859 static struct Closest_Peer
3860 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3861 struct GNUNET_HashCode intermediate_trail_id,
3862 unsigned int is_predecessor,
3863 struct GNUNET_PeerIdentity prev_hop,
3864 struct GNUNET_PeerIdentity source,
3865 struct GNUNET_PeerIdentity *current_dest)
3867 struct Closest_Peer peer;
3869 /* Find a local best known peer. */
3870 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3872 /* Am I just a part of a trail towards a finger (current_destination)? */
3873 /* Select best successor among one found locally and current_destination
3874 * that we got from network.*/
3875 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) &&
3876 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3879 const struct GNUNET_PeerIdentity *closest_peer;
3881 closest_peer = select_closest_peer (&peer.best_known_destination,
3883 final_dest_finger_val,
3886 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3887 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3889 struct GNUNET_PeerIdentity *next_hop;
3891 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3892 GDS_ROUTING_SRC_TO_DEST);
3893 /* It may happen that trail teardown message got delayed and hence,
3894 the previous hop sent the message over intermediate trail id.In that
3895 case next_hop could be NULL. */
3896 if(NULL != next_hop)
3898 peer.next_hop = *next_hop;
3899 peer.best_known_destination = *current_dest;
3900 peer.trail_id = intermediate_trail_id;
3909 * Core handle for PeerTrailSetupMessage.
3910 * @param cls closure
3911 * @param message message
3912 * @param peer peer identity this notification is about
3913 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3916 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3917 const struct GNUNET_MessageHeader *message)
3919 const struct PeerTrailSetupMessage *trail_setup;
3920 const struct GNUNET_PeerIdentity *trail_peer_list;
3921 struct GNUNET_PeerIdentity current_dest;
3922 struct FriendInfo *target_friend;
3923 struct GNUNET_PeerIdentity source;
3924 uint64_t final_dest_finger_val;
3925 struct GNUNET_HashCode intermediate_trail_id;
3926 struct GNUNET_HashCode trail_id;
3927 unsigned int is_predecessor;
3928 uint32_t trail_length;
3931 msize = ntohs (message->size);
3932 if (msize < sizeof (struct PeerTrailSetupMessage))
3934 GNUNET_break_op (0);
3935 return GNUNET_SYSERR;
3938 trail_setup = (const struct PeerTrailSetupMessage *) message;
3939 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3940 sizeof (struct GNUNET_PeerIdentity);
3941 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3942 sizeof (struct GNUNET_PeerIdentity) != 0)
3944 GNUNET_break_op (0);
3948 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3949 current_dest = trail_setup->best_known_destination;
3950 trail_id = trail_setup->trail_id;
3951 final_dest_finger_val =
3952 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3953 source = trail_setup->source_peer;
3954 is_predecessor = ntohl (trail_setup->is_predecessor);
3955 intermediate_trail_id = trail_setup->intermediate_trail_id;
3957 /* If I was the source and got the message back, then set trail length to 0.*/
3958 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3960 /* IF (!) the peers know the destinations of the trails in their routing
3963 * This shoud only happen after 1 hop, since the first message is sent
3964 * to random friend, and we can happen to be on the best trail to the dest.
3965 * If the first friend selects someone else, the request should never come
3970 // GNUNET_break_op (1 == trail_length);
3974 /* Did the friend insert its ID in the trail list? */
3975 if (trail_length > 0 &&
3976 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (*peer)))
3978 GNUNET_break_op (0);
3979 return GNUNET_SYSERR;
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 /* Am I the one who initiated the query? */
4212 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4214 /* If I am my own finger identity, error. */
4215 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4217 GNUNET_break_op (0);
4218 return GNUNET_SYSERR;
4220 GDS_ROUTING_add (trail_id, my_identity, *peer);
4221 finger_table_add (finger_identity, trail_peer_list, trail_length,
4222 is_predecessor, ulitmate_destination_finger_value, trail_id);
4226 /* Get my location in the trail. */
4227 my_index = search_my_index (trail_peer_list, trail_length);
4231 return GNUNET_SYSERR;
4235 next_hop = trail_result->querying_peer;
4237 next_hop = trail_peer_list[my_index - 1];
4239 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4240 if (NULL == target_friend)
4242 GNUNET_break_op (0);
4243 return GNUNET_SYSERR;
4246 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4247 &(trail_result->finger_identity))))
4249 GNUNET_break_op (0);
4250 return GNUNET_SYSERR;
4253 GDS_ROUTING_add (trail_id, next_hop, *peer);
4255 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4256 target_friend, trail_length, trail_peer_list,
4258 ulitmate_destination_finger_value,
4266 * @param trail Trail to be inverted
4267 * @param trail_length Total number of peers in the trail.
4268 * @return Updated trail
4270 static struct GNUNET_PeerIdentity *
4271 invert_trail (const struct GNUNET_PeerIdentity *trail,
4272 unsigned int trail_length)
4276 struct GNUNET_PeerIdentity *inverted_trail;
4278 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4281 j = trail_length - 1;
4282 while (i < trail_length)
4284 inverted_trail[i] = trail[j];
4289 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4290 &inverted_trail[0]));
4291 return inverted_trail;
4296 * Return the shortest trail among all the trails to reach to finger from me.
4297 * @param finger Finger
4298 * @param shortest_trail_length[out] Trail length of shortest trail from me
4300 * @return Shortest trail.
4302 static struct GNUNET_PeerIdentity *
4303 get_shortest_trail (struct FingerInfo *finger,
4304 unsigned int *trail_length)
4306 struct Trail *trail;
4307 unsigned int flag = 0;
4308 unsigned int shortest_trail_index = 0;
4309 int shortest_trail_length = -1;
4310 struct Trail_Element *trail_element;
4311 struct GNUNET_PeerIdentity *trail_list;
4314 trail = GNUNET_new (struct Trail);
4316 /* Get the shortest trail to reach to current successor. */
4317 for (i = 0; i < finger->trails_count; i++)
4319 trail = &finger->trail_list[i];
4323 shortest_trail_index = i;
4324 shortest_trail_length = trail->trail_length;
4329 if (shortest_trail_length > trail->trail_length)
4331 shortest_trail_index = i;
4332 shortest_trail_length = trail->trail_length;
4337 /* Copy the shortest trail and return. */
4338 trail = &finger->trail_list[shortest_trail_index];
4339 trail_element = trail->trail_head;
4340 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4341 shortest_trail_length);
4343 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4345 trail_list[i] = trail_element->peer;
4348 GNUNET_assert(shortest_trail_length != -1);
4350 *trail_length = shortest_trail_length;
4356 * Return the trail from source to my current predecessor. Check if source
4357 * is already part of the this trail, if yes then return the shorten trail.
4358 * @param current_trail Trail from source to me, NOT including the endpoints.
4359 * @param current_trail_length Number of peers in @a current_trail.
4360 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4361 * source to my predecessor, NOT including
4363 * @return Trail from source to my predecessor.
4365 static struct GNUNET_PeerIdentity *
4366 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4367 const struct GNUNET_PeerIdentity *trail_src_to_me,
4368 unsigned int trail_src_to_me_len,
4369 unsigned int *trail_src_to_curr_pred_length)
4371 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4372 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4373 unsigned int trail_me_to_curr_pred_length;
4374 struct FingerInfo *current_predecessor;
4378 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4379 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4380 &trail_me_to_curr_pred_length);
4382 if ((trail_me_to_curr_pred_length == 1) &&
4383 (0 == GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4384 &trail_me_to_curr_pred[0])))
4386 *trail_src_to_curr_pred_length = 0;
4390 /* Check if trail_me_to_curr_pred contains source. */
4391 if (trail_me_to_curr_pred_length > 1)
4393 for(i = trail_me_to_curr_pred_length - 1; i > 0; i--)
4395 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4396 &trail_me_to_curr_pred[i]))
4401 /* Source is the last element in the trail to reach to my pred.
4402 Source is direct friend of the pred. */
4403 if (trail_me_to_curr_pred_length == i)
4405 *trail_src_to_curr_pred_length = 0;
4410 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4411 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4412 *trail_src_to_curr_pred_length);
4413 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4415 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4417 return trail_src_to_curr_pred;
4421 /* Append trail from source to me to my current_predecessor. */
4422 *trail_src_to_curr_pred_length = trail_src_to_me_len +
4423 trail_me_to_curr_pred_length + 1;
4425 trail_src_to_curr_pred = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4426 *trail_src_to_curr_pred_length);
4428 for (i = 0; i < trail_src_to_me_len; i++)
4429 trail_src_to_curr_pred[i] = trail_src_to_me[i];
4431 trail_src_to_curr_pred[i] = my_identity;
4434 for (j = 0; i < *trail_src_to_curr_pred_length; i++,j++)
4435 trail_src_to_curr_pred[i] = trail_me_to_curr_pred[j];
4437 return trail_src_to_curr_pred;
4442 * Add finger as your predecessor. To add, first generate a new trail id, invert
4443 * the trail to get the trail from me to finger, add an entry in your routing
4444 * table, send add trail message to peers which are part of trail from me to
4445 * finger and add finger in finger table.
4448 * @param trail_length
4451 update_predecessor (struct GNUNET_PeerIdentity finger,
4452 struct GNUNET_PeerIdentity *trail,
4453 unsigned int trail_length)
4455 struct GNUNET_HashCode trail_to_new_predecessor_id;
4456 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4457 struct FriendInfo *target_friend;
4459 /* Generate trail id for trail from me to new predecessor = finger. */
4460 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4461 &trail_to_new_predecessor_id,
4462 sizeof (trail_to_new_predecessor_id));
4464 /* Finger is a friend. */
4465 if (trail_length == 0)
4467 trail_to_new_predecessor = NULL;
4468 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4469 GNUNET_assert (NULL != (target_friend =
4470 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4475 /* Invert the trail to get the trail from me to finger, NOT including the
4477 trail_to_new_predecessor = invert_trail (trail, trail_length);
4479 /* Add an entry in your routing table. */
4480 GDS_ROUTING_add (trail_to_new_predecessor_id,
4482 trail_to_new_predecessor[0]);
4484 GNUNET_assert (NULL != (target_friend =
4485 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4486 &trail_to_new_predecessor[0])));
4487 GNUNET_assert (NULL != (
4488 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4489 &trail[trail_length - 1])));
4492 /* Add entry in routing table of all peers that are part of trail from me
4493 to finger, including finger. */
4494 GDS_NEIGHBOURS_send_add_trail (my_identity,
4496 trail_to_new_predecessor_id,
4497 trail_to_new_predecessor,
4501 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4502 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4503 GNUNET_free_non_null (trail_to_new_predecessor);
4508 * Check if you already have a predecessor. If not then add finger as your
4509 * predecessor. If you have predecessor, then compare two peer identites.
4510 * If finger is correct predecessor, then remove the old entry, add finger in
4511 * finger table and send add_trail message to add the trail in the routing
4512 * table of all peers which are part of trail to reach from me to finger.
4513 * @param finger New peer which may be our predecessor.
4514 * @param trail List of peers to reach from @finger to me.
4515 * @param trail_length Total number of peer in @a trail.
4518 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4519 struct GNUNET_PeerIdentity *trail,
4520 unsigned int trail_length)
4522 struct FingerInfo *current_predecessor;
4523 const struct GNUNET_PeerIdentity *closest_peer;
4524 uint64_t predecessor_value;
4525 unsigned int is_predecessor = 1;
4527 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4529 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4531 /* No predecessor. Add finger as your predecessor. */
4532 if (GNUNET_NO == current_predecessor->is_present)
4534 update_predecessor (finger, trail, trail_length);
4537 /* FIXME: Here we should first call find_successor and get a locally known
4538 predecessor. If locally known predecessor is closest then current or finger,
4539 add that as predecessor. */
4540 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4546 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4547 closest_peer = select_closest_peer (&finger,
4548 ¤t_predecessor->finger_identity,
4549 predecessor_value, is_predecessor);
4551 /* Finger is the closest predecessor. Remove the existing one and add the new
4553 if (closest_peer == &finger)
4555 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4556 update_predecessor (finger, trail, trail_length);
4564 * Core handle for p2p verify successor messages.
4565 * @param cls closure
4566 * @param message message
4567 * @param peer peer identity this notification is about
4568 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4571 handle_dht_p2p_verify_successor(void *cls,
4572 const struct GNUNET_PeerIdentity *peer,
4573 const struct GNUNET_MessageHeader *message)
4575 const struct PeerVerifySuccessorMessage *vsm;
4576 struct GNUNET_HashCode trail_id;
4577 struct GNUNET_PeerIdentity successor;
4578 struct GNUNET_PeerIdentity source_peer;
4579 struct GNUNET_PeerIdentity *trail;
4580 struct GNUNET_PeerIdentity *next_hop;
4581 struct FingerInfo *current_predecessor;
4582 struct FriendInfo *target_friend;
4583 unsigned int trail_src_to_curr_pred_len = 0;
4584 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4586 unsigned int trail_length;
4588 msize = ntohs (message->size);
4590 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4592 GNUNET_break_op (0);
4596 vsm = (const struct PeerVerifySuccessorMessage *) message;
4597 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4598 sizeof (struct GNUNET_PeerIdentity);
4599 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4600 sizeof (struct GNUNET_PeerIdentity) != 0)
4602 GNUNET_break_op (0);
4606 trail_id = vsm->trail_id;
4607 source_peer = vsm->source_peer;
4608 successor = vsm->successor;
4609 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4612 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4614 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4616 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4618 if (NULL == next_hop)
4620 GNUNET_break_op (0);
4621 return GNUNET_SYSERR;
4624 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4626 if(NULL == target_friend)
4631 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4632 trail_id, trail, trail_length,
4637 /* I am the destination of this message. */
4639 /* Check if the source_peer could be our predecessor and if yes then update
4641 compare_and_update_predecessor (source_peer, trail, trail_length);
4642 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4644 /* Is source of this message NOT my predecessor. */
4645 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4648 trail_src_to_curr_pred = get_trail_src_to_curr_pred (source_peer,
4651 &trail_src_to_curr_pred_len);
4655 trail_src_to_curr_pred_len = trail_length;
4657 trail_src_to_curr_pred = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)*trail_length);
4658 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4660 trail_src_to_curr_pred[i] = trail[i];
4665 GNUNET_assert (NULL !=
4667 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4668 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4669 current_predecessor->finger_identity,
4670 trail_id, trail_src_to_curr_pred,
4671 trail_src_to_curr_pred_len,
4672 GDS_ROUTING_DEST_TO_SRC,
4680 * If the trail from me to my probable successor contains a friend not
4681 * at index 0, then we can shorten the trail.
4682 * @param probable_successor Peer which is our probable successor
4683 * @param trail_me_to_probable_successor Peers in path from me to my probable
4684 * successor, NOT including the endpoints.
4685 * @param trail_me_to_probable_successor_len Total number of peers in
4686 * @a trail_me_to_probable_succesor.
4687 * @return Updated trail, if any friend found.
4688 * Else the trail_me_to_probable_successor.
4690 struct GNUNET_PeerIdentity *
4691 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4692 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4693 unsigned int trail_me_to_probable_successor_len,
4694 unsigned int *trail_to_new_successor_length)
4698 struct GNUNET_PeerIdentity *trail_to_new_successor;
4700 /* Probable successor is a friend */
4701 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4702 &probable_successor))
4704 trail_to_new_successor = NULL;
4705 *trail_to_new_successor_length = 0;
4706 return trail_to_new_successor;
4709 /* Is there any friend of yours in this trail. */
4710 if(trail_me_to_probable_successor_len > 1)
4712 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4714 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4715 &trail_me_to_probable_successor[i]))
4719 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4720 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4721 *trail_to_new_successor_length);
4723 for(j = 0;i < trail_me_to_probable_successor_len;i++,j++)
4725 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4727 return trail_to_new_successor;
4731 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4732 trail_to_new_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4733 *trail_to_new_successor_length);
4735 for(i = 0; i < *trail_to_new_successor_length; i++)
4736 trail_to_new_successor[i] = trail_me_to_probable_successor[i];
4738 return trail_to_new_successor;
4743 * Check if the peer which sent us verify successor result message is still ours
4744 * successor or not. If not, then compare existing successor and probable successor.
4745 * In case probable successor is the correct successor, remove the existing
4746 * successor. Add probable successor as new successor. Send notify new successor
4747 * message to new successor.
4749 * @param probable_successor
4751 * @param trail_length
4754 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4755 struct GNUNET_PeerIdentity probable_successor,
4756 const struct GNUNET_PeerIdentity *trail,
4757 unsigned int trail_length)
4759 struct FingerInfo *current_successor;
4760 const struct GNUNET_PeerIdentity *closest_peer;
4761 struct GNUNET_HashCode trail_id;
4762 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4763 struct FriendInfo *target_friend;
4764 unsigned int trail_me_to_probable_succ_len;
4765 unsigned int is_predecessor = GNUNET_NO;
4766 uint64_t successor_value;
4768 current_successor = &finger_table[0];
4769 successor_value = compute_finger_identity_value(0);
4771 /* Have we found some other successor, while waiting for verify successor result
4773 * FIXME closest_peer is being overwritten just after the if
4776 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&curr_succ, ¤t_successor->finger_identity))
4778 /* We could have added this new successor, only if it was closer the old one. */
4779 closest_peer = select_closest_peer (&curr_succ,
4780 ¤t_successor->finger_identity,
4781 successor_value, is_predecessor);
4783 /* FIXME: it may fail in case we have done more number of iterations of
4784 find _finger_trail_task. */
4785 /*GNUNET_assert (0 ==
4786 GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4787 ¤t_successor->finger_identity));*/
4792 closest_peer = select_closest_peer (&probable_successor,
4793 ¤t_successor->finger_identity,
4794 successor_value, is_predecessor);
4796 /* If the current_successor in the finger table is closest, then do nothing. */
4797 if (closest_peer == ¤t_successor->finger_identity)
4800 /* Probable successor is the closest peer.*/
4801 if(trail_length > 0)
4803 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4808 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4809 &probable_successor));
4812 trail_me_to_probable_succ_len = 0;
4813 /* TODO: Check if the path to reach to probable successor contains a friend. */
4814 trail_me_to_probable_succ =
4815 check_trail_me_to_probable_succ (probable_successor,
4816 trail, trail_length,
4817 &trail_me_to_probable_succ_len);
4819 /* Remove the existing successor. */
4820 remove_existing_finger (current_successor, 0);
4822 /* Generate a new trail id to reach to your new successor. */
4823 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4824 &trail_id, sizeof (trail_id));
4826 if (trail_me_to_probable_succ_len > 0)
4828 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4829 GNUNET_assert (NULL !=
4831 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4832 &trail_me_to_probable_succ[0])));
4836 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4837 GNUNET_assert (NULL !=
4839 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4840 &probable_successor)));
4843 add_new_finger (probable_successor, trail_me_to_probable_succ,
4844 trail_me_to_probable_succ_len, trail_id, 0);
4846 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4847 trail_me_to_probable_succ,
4848 trail_me_to_probable_succ_len,
4856 * FIXME: Check for duplicate elements everywhere when you are making
4858 * Core handle for p2p verify successor result messages.
4859 * @param cls closure
4860 * @param message message
4861 * @param peer peer identity this notification is about
4862 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4865 handle_dht_p2p_verify_successor_result(void *cls,
4866 const struct GNUNET_PeerIdentity *peer,
4867 const struct GNUNET_MessageHeader *message)
4869 const struct PeerVerifySuccessorResultMessage *vsrm;
4870 enum GDS_ROUTING_trail_direction trail_direction;
4871 struct GNUNET_PeerIdentity querying_peer;
4872 struct GNUNET_HashCode trail_id;
4873 struct GNUNET_PeerIdentity *next_hop;
4874 struct FriendInfo *target_friend;
4875 struct GNUNET_PeerIdentity probable_successor;
4876 struct GNUNET_PeerIdentity current_successor;
4877 const struct GNUNET_PeerIdentity *trail;
4878 unsigned int trail_length;
4881 msize = ntohs (message->size);
4882 /* We send a trail to reach from old successor to new successor, if
4883 * old_successor != new_successor.*/
4884 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4886 GNUNET_break_op (0);
4890 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4891 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4892 sizeof (struct GNUNET_PeerIdentity);
4894 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4895 sizeof (struct GNUNET_PeerIdentity) != 0)
4897 GNUNET_break_op (0);
4901 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4902 querying_peer = vsrm->querying_peer;
4903 trail_direction = ntohl (vsrm->trail_direction);
4904 trail_id = vsrm->trail_id;
4905 probable_successor = vsrm->probable_successor;
4906 current_successor = vsrm->current_successor;
4908 /* I am the querying_peer. */
4909 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4911 compare_and_update_successor (current_successor,
4912 probable_successor, trail, trail_length);
4916 /*If you are not the querying peer then pass on the message */
4917 GNUNET_assert (NULL != (next_hop =
4918 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
4919 GNUNET_assert (NULL !=
4921 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4922 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4923 vsrm->current_successor,
4924 probable_successor, trail_id,
4927 trail_direction, target_friend);
4933 * Core handle for p2p notify new successor messages.
4934 * @param cls closure
4935 * @param message message
4936 * @param peer peer identity this notification is about
4937 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4940 handle_dht_p2p_notify_new_successor(void *cls,
4941 const struct GNUNET_PeerIdentity *peer,
4942 const struct GNUNET_MessageHeader *message)
4944 const struct PeerNotifyNewSuccessorMessage *nsm;
4945 struct GNUNET_PeerIdentity *trail;
4946 struct GNUNET_PeerIdentity source;
4947 struct GNUNET_PeerIdentity new_successor;
4948 struct GNUNET_HashCode trail_id;
4949 struct GNUNET_PeerIdentity next_hop;
4950 struct FriendInfo *target_friend;
4953 uint32_t trail_length;
4955 msize = ntohs (message->size);
4957 /* We have the trail to reach from source to new successor. */
4958 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
4960 GNUNET_break_op (0);
4964 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
4965 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
4966 sizeof (struct GNUNET_PeerIdentity);
4967 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
4968 sizeof (struct GNUNET_PeerIdentity) != 0)
4970 GNUNET_break_op (0);
4974 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
4975 source = nsm->source_peer;
4976 new_successor = nsm->new_successor;
4977 trail_id = nsm->trail_id;
4979 //FIXME: add a check to make sure peer is correct.
4981 /* I am the new_successor to source_peer. */
4982 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
4984 GDS_ROUTING_add (trail_id, *peer, my_identity);
4985 compare_and_update_predecessor (source, trail, trail_length);
4989 GNUNET_assert(trail_length > 0);
4990 /* I am part of trail to reach to successor. */
4991 my_index = search_my_index (trail, trail_length);
4994 GNUNET_break_op (0);
4995 return GNUNET_SYSERR;
4998 if ((trail_length-1) == my_index)
4999 next_hop = new_successor;
5001 next_hop = trail[my_index + 1];
5004 /* Add an entry in routing table for trail from source to its new successor. */
5005 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
5007 GNUNET_assert (NULL !=
5009 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5010 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
5012 trail_id, target_friend);
5019 * Core handler for P2P trail rejection message
5020 * @param cls closure
5021 * @param message message
5022 * @param peer peer identity this notification is about
5023 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5026 handle_dht_p2p_trail_setup_rejection (void *cls,
5027 const struct GNUNET_PeerIdentity *peer,
5028 const struct GNUNET_MessageHeader *message)
5030 const struct PeerTrailRejectionMessage *trail_rejection;
5031 unsigned int trail_length;
5032 const struct GNUNET_PeerIdentity *trail_peer_list;
5033 struct FriendInfo *target_friend;
5034 struct GNUNET_TIME_Relative congestion_timeout;
5035 struct GNUNET_HashCode trail_id;
5036 struct GNUNET_PeerIdentity next_peer;
5037 struct GNUNET_PeerIdentity source;
5038 struct GNUNET_PeerIdentity *next_hop;
5039 uint64_t ultimate_destination_finger_value;
5040 unsigned int is_predecessor;
5043 msize = ntohs (message->size);
5044 /* We are passing the trail setup so far. */
5045 if (msize < sizeof (struct PeerTrailRejectionMessage))
5047 GNUNET_break_op (0);
5051 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5052 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5053 sizeof (struct GNUNET_PeerIdentity);
5054 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5055 sizeof (struct GNUNET_PeerIdentity) != 0)
5057 GNUNET_break_op (0);
5061 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5062 is_predecessor = ntohl (trail_rejection->is_predecessor);
5063 congestion_timeout = trail_rejection->congestion_time;
5064 source = trail_rejection->source_peer;
5065 trail_id = trail_rejection->trail_id;
5066 ultimate_destination_finger_value =
5067 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5069 /* First set the congestion time of the friend that sent you this message. */
5070 GNUNET_assert (NULL !=
5072 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5073 target_friend->congestion_timestamp =
5074 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5075 congestion_timeout);
5077 /* I am the source peer which wants to setup the trail. Do nothing.
5078 * send_find_finger_trail_task is scheduled periodically.*/
5079 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5082 /* If I am congested then pass this message to peer before me in trail. */
5083 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5085 struct GNUNET_PeerIdentity *new_trail;
5086 unsigned int new_trail_length;
5088 /* Remove yourself from the trail setup so far. */
5089 if (trail_length == 1)
5092 new_trail_length = 0;
5097 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5098 sizeof (struct GNUNET_PeerIdentity));
5100 /* Remove myself from the trail. */
5101 new_trail_length = trail_length -1;
5102 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5103 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5106 GNUNET_assert (NULL !=
5108 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5109 GDS_NEIGHBOURS_send_trail_rejection (source,
5110 ultimate_destination_finger_value,
5111 my_identity, is_predecessor,
5112 new_trail,new_trail_length,trail_id,
5113 target_friend, CONGESTION_TIMEOUT);
5114 GNUNET_free (new_trail);
5118 struct Closest_Peer successor;
5119 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5121 /* Am I the final destination? */
5122 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5125 if (0 == trail_length)
5128 next_peer = trail_peer_list[trail_length-1];
5130 GNUNET_assert (NULL !=
5132 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5134 GDS_NEIGHBOURS_send_trail_setup_result (source,
5136 target_friend, trail_length,
5139 ultimate_destination_finger_value,
5144 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5146 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5147 peer_list[trail_length] = my_identity;
5149 GNUNET_assert (NULL !=
5151 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5153 GDS_NEIGHBOURS_send_trail_setup (source,
5154 ultimate_destination_finger_value,
5155 successor.best_known_destination,
5156 target_friend, trail_length + 1, peer_list,
5157 is_predecessor, trail_id,
5158 successor.trail_id);
5165 * Core handle for p2p trail tear compression messages.
5166 * @param cls closure
5167 * @param message message
5168 * @param peer peer identity this notification is about
5169 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5172 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5173 const struct GNUNET_MessageHeader *message)
5175 const struct PeerTrailCompressionMessage *trail_compression;
5176 struct GNUNET_PeerIdentity *next_hop;
5177 struct FriendInfo *target_friend;
5178 struct GNUNET_HashCode trail_id;
5181 msize = ntohs (message->size);
5183 if (msize != sizeof (struct PeerTrailCompressionMessage))
5185 GNUNET_break_op (0);
5189 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5190 trail_id = trail_compression->trail_id;
5192 /* Am I the new first friend to reach to finger of this trail. */
5193 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5196 GNUNET_assert (NULL !=
5197 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5198 &trail_compression->source_peer)));
5200 /* Update your prev hop to source of this message. */
5201 GNUNET_assert (GNUNET_SYSERR !=
5202 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5203 trail_compression->source_peer)));
5207 /* Pass the message to next hop to finally reach to new_first_friend. */
5208 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5210 if (NULL == next_hop)
5216 GNUNET_assert (NULL !=
5218 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5220 GDS_ROUTING_remove_trail (trail_id);
5222 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5224 trail_compression->new_first_friend,
5231 * Core handler for trail teardown message.
5232 * @param cls closure
5233 * @param message message
5234 * @param peer sender of this messsage.
5235 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5238 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5239 const struct GNUNET_MessageHeader *message)
5241 const struct PeerTrailTearDownMessage *trail_teardown;
5242 enum GDS_ROUTING_trail_direction trail_direction;
5243 struct GNUNET_HashCode trail_id;
5244 struct GNUNET_PeerIdentity *next_hop;
5247 msize = ntohs (message->size);
5249 /* Here we pass only the trail id. */
5250 if (msize != sizeof (struct PeerTrailTearDownMessage))
5252 GNUNET_break_op (0);
5256 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5257 trail_direction = ntohl (trail_teardown->trail_direction);
5258 trail_id = trail_teardown->trail_id;
5260 /* Check if peer is the real peer from which we should get this message.*/
5261 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5263 GNUNET_assert (NULL != (prev_hop =
5264 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5265 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5268 return GNUNET_SYSERR;
5272 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5274 if (NULL == next_hop)
5277 return GNUNET_SYSERR;
5280 /* I am the next hop, which means I am the final destination. */
5281 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5283 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5288 /* If not final destination, then send a trail teardown message to next hop.*/
5289 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5290 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5291 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5299 * Core handle for p2p add trail message.
5300 * @param cls closure
5301 * @param message message
5302 * @param peer peer identity this notification is about
5303 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5306 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5307 const struct GNUNET_MessageHeader *message)
5309 const struct PeerAddTrailMessage *add_trail;
5310 const struct GNUNET_PeerIdentity *trail;
5311 struct GNUNET_HashCode trail_id;
5312 struct GNUNET_PeerIdentity destination_peer;
5313 struct GNUNET_PeerIdentity source_peer;
5314 struct GNUNET_PeerIdentity next_hop;
5315 unsigned int trail_length;
5316 unsigned int my_index;
5319 msize = ntohs (message->size);
5320 /* In this message we pass the whole trail from source to destination as we
5321 * are adding that trail.*/
5322 if (msize < sizeof (struct PeerAddTrailMessage))
5324 GNUNET_break_op (0);
5328 add_trail = (const struct PeerAddTrailMessage *) message;
5329 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5330 sizeof (struct GNUNET_PeerIdentity);
5331 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5332 sizeof (struct GNUNET_PeerIdentity) != 0)
5334 GNUNET_break_op (0);
5338 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5339 destination_peer = add_trail->destination_peer;
5340 source_peer = add_trail->source_peer;
5341 trail_id = add_trail->trail_id;
5343 //FIXME: add a check that sender peer is not malicious. Make it a generic
5344 // function so that it can be used in all other functions where we need the
5345 // same functionality.
5347 /* I am not the destination of the trail. */
5348 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5350 struct FriendInfo *target_friend;
5352 /* Get my location in the trail. */
5353 my_index = search_my_index (trail, trail_length);
5357 GNUNET_break_op (0);
5358 return GNUNET_SYSERR;
5362 if ((trail_length - 1) == my_index)
5364 next_hop = destination_peer;
5368 next_hop = trail[my_index + 1];
5371 /* Add in your routing table. */
5372 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5373 GNUNET_assert (NULL !=
5375 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5376 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5377 trail, trail_length, target_friend);
5380 /* I am the destination. Add an entry in routing table. */
5381 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5387 * Free the finger trail in which the first friend to reach to a finger is
5388 * disconnected_friend. Also remove entry from routing table for that particular
5390 * @param disconnected_friend PeerIdentity of friend which got disconnected
5391 * @param remove_finger Finger whose trail we need to check if it has
5392 * disconnected_friend as the first hop.
5393 * @return Total number of trails in which disconnected_friend was the first
5397 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5398 struct FingerInfo *remove_finger)
5400 unsigned int matching_trails_count;
5403 /* Number of trails with disconnected_friend as the first hop in the trail
5404 * to reach from me to remove_finger, NOT including endpoints. */
5405 matching_trails_count = 0;
5407 /* Iterate over all the trails of finger. */
5408 for (i = 0; i < remove_finger->trails_count; i++)
5410 struct Trail *trail;
5411 trail = &remove_finger->trail_list[i];
5413 /* This assertion is ensure that there are no gaps in the trail list.
5414 REMOVE IT AFTERWARDS. */
5415 GNUNET_assert (GNUNET_YES == trail->is_present);
5417 /* First friend to reach to finger is disconnected_peer. */
5418 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5419 disconnected_friend))
5421 struct GNUNET_PeerIdentity *next_hop;
5422 struct FriendInfo *remove_friend;
5424 GNUNET_assert (NULL !=
5426 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5427 disconnected_friend)));
5428 /* FIXME: removing no but check it. */
5429 //remove_friend->trails_count--;
5430 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5431 GDS_ROUTING_SRC_TO_DEST);
5433 /* Here it may happen that as all the peers got disconnected, the entry in
5434 routing table for that particular trail has been removed, because the
5435 previously disconnected peer was either a next hop or prev hop of that
5437 if (NULL == next_hop)
5440 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5442 matching_trails_count++;
5443 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5446 trail->is_present = GNUNET_NO;
5449 return matching_trails_count;
5454 * Iterate over finger_table entries.
5455 * 0. Ignore finger which is my_identity or if no valid entry present at
5456 * that finger index.
5457 * 1. If disconnected_friend is a finger, then remove the routing entry from
5458 your own table. Free the trail.
5459 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5460 * 2.1 Remove all the trails and entry from routing table in which disconnected
5461 * friend is the first friend in the trail. If disconnected_friend is the
5462 * first friend in all the trails to reach finger, then remove the finger.
5463 * @param disconnected_friend Peer identity of friend which got disconnected.
5466 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5468 struct FingerInfo *remove_finger;
5469 struct FriendInfo *remove_friend;
5470 int removed_trails_count;
5473 /* Iterate over finger table entries. */
5474 for (i = 0; i < MAX_FINGERS; i++)
5476 remove_finger = &finger_table[i];
5478 /* No finger stored at this trail index. */
5479 if (GNUNET_NO == remove_finger->is_present)
5482 /* I am my own finger, then ignore this finger. */
5483 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5487 /* Is disconnected_peer a finger? */
5488 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5489 &remove_finger->finger_identity))
5491 struct GNUNET_PeerIdentity *next_hop;
5492 struct GNUNET_HashCode trail_id;
5495 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5496 trail_id = remove_finger->trail_list[0].trail_id;
5500 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5503 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5504 &remove_finger->finger_identity)));
5505 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5506 GNUNET_assert (NULL !=
5508 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5509 disconnected_peer)));
5512 remove_finger->trail_list[0].is_present = GNUNET_NO;
5513 //GNUNET_assert (0 != remove_friend->trails_count);
5514 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5515 remove_finger->is_present = GNUNET_NO;
5516 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5520 /* If finger is a friend but not disconnected_friend, then continue. */
5521 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5522 &remove_finger->finger_identity))
5525 /* Iterate over the list of trails to reach remove_finger. Check if
5526 * disconnected_friend is the first friend in any of the trail. */
5527 removed_trails_count = remove_matching_trails (disconnected_peer,
5529 remove_finger->trails_count =
5530 remove_finger->trails_count - removed_trails_count;
5531 /* All the finger trails had disconnected_friend as the first friend,
5532 * so free the finger. */
5533 if (remove_finger->trails_count == 0)
5535 remove_finger->is_present = GNUNET_NO;
5536 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5543 * Method called whenever a peer disconnects.
5545 * @param cls closure
5546 * @param peer peer identity this notification is about
5549 handle_core_disconnect (void *cls,
5550 const struct GNUNET_PeerIdentity *peer)
5552 struct FriendInfo *remove_friend;
5554 /* If disconnected to own identity, then return. */
5555 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5558 GNUNET_assert (NULL != (remove_friend =
5559 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5561 /* Remove fingers with peer as first friend or if peer is a finger. */
5562 remove_matching_fingers (peer);
5564 /* Remove any trail from routing table of which peer is a part of. This function
5565 * internally sends a trail teardown message in the direction of which
5566 * disconnected peer is not part of. */
5567 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5569 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5571 /* Remove peer from friend_peermap. */
5572 GNUNET_assert (GNUNET_YES ==
5573 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5577 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5580 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5582 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5583 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5592 * Method called whenever a peer connects.
5594 * @param cls closure
5595 * @param peer_identity peer identity this notification is about
5598 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5600 struct FriendInfo *friend;
5602 /* Check for connect to self message */
5603 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5606 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5608 /* If peer already exists in our friend_peermap, then exit. */
5609 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5616 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
5619 friend = GNUNET_new (struct FriendInfo);
5620 friend->id = *peer_identity;
5622 GNUNET_assert (GNUNET_OK ==
5623 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5624 peer_identity, friend,
5625 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5628 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5629 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5630 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5635 * To be called on core init/fail.
5637 * @param cls service closure
5638 * @param identity the public identity of this peer
5641 core_init (void *cls,
5642 const struct GNUNET_PeerIdentity *identity)
5644 my_identity = *identity;
5647 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5648 my_id64 = GNUNET_ntohll (my_id64);
5649 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5650 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5656 * Initialize finger table entries.
5659 finger_table_init ()
5661 memset (&finger_table, 0, sizeof (finger_table));
5666 * Initialize neighbours subsystem.
5667 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5670 GDS_NEIGHBOURS_init (void)
5672 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5673 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5674 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5675 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5676 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5677 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5678 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5679 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5680 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5681 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5682 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5683 sizeof (struct PeerTrailCompressionMessage)},
5684 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5685 sizeof (struct PeerTrailTearDownMessage)},
5686 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5691 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5692 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5693 GNUNET_NO, core_handlers);
5694 if (NULL == core_api)
5695 return GNUNET_SYSERR;
5697 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5698 finger_table_init ();
5705 * Shutdown neighbours subsystem.
5708 GDS_NEIGHBOURS_done (void)
5710 if (NULL == core_api)
5713 GNUNET_CORE_disconnect (core_api);
5716 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5717 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5718 friend_peermap = NULL;
5720 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5723 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5724 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5727 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5729 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5730 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5738 * @return my identity
5740 struct GNUNET_PeerIdentity
5741 GDS_NEIGHBOURS_get_my_id (void)
5746 /* end of gnunet-service-xdht_neighbours.c */