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_SECONDS, 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 struct GNUNET_PeerIdentity best_known_destination;
322 * In case best_known_destination is a finger, then trail id of trail to
323 * reach to this finger.
325 struct GNUNET_HashCode intermediate_trail_id;
328 * Trail id for trail which we are trying to setup.
330 struct GNUNET_HashCode trail_id;
332 /* List of peers which are part of trail setup so far.
333 * Trail does NOT include source_peer and peer which will be closest to
334 * ultimate_destination_finger_value.
335 * struct GNUNET_PeerIdentity trail[]
340 * P2P Trail Setup Result message
342 struct PeerTrailSetupResultMessage
346 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
348 struct GNUNET_MessageHeader header;
351 * Finger to which we have found the path.
353 struct GNUNET_PeerIdentity finger_identity;
356 * Peer which started trail_setup to find trail to finger_identity
358 struct GNUNET_PeerIdentity querying_peer;
361 * Is the trail setup to querying_peer's predecessor or finger?
363 uint32_t is_predecessor;
366 * Value to which finger_identity is the closest peer.
368 uint64_t ulitmate_destination_finger_value;
371 * Identifier of the trail from querying peer to finger_identity, NOT
372 * including both endpoints.
374 struct GNUNET_HashCode trail_id;
376 /* List of peers which are part of the trail from querying peer to
377 * finger_identity, NOT including both endpoints.
378 * struct GNUNET_PeerIdentity trail[]
383 * P2P Verify Successor Message.
385 struct PeerVerifySuccessorMessage
388 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
390 struct GNUNET_MessageHeader header;
393 * Peer which wants to verify its successor.
395 struct GNUNET_PeerIdentity source_peer;
398 * Source Peer's current successor.
400 struct GNUNET_PeerIdentity successor;
403 * Identifier of trail to reach from source_peer to successor.
405 struct GNUNET_HashCode trail_id;
407 /* List of the peers which are part of trail to reach from source_peer
408 * to successor, NOT including them
409 * struct GNUNET_PeerIdentity trail[]
414 * P2P Verify Successor Result Message
416 struct PeerVerifySuccessorResultMessage
419 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
421 struct GNUNET_MessageHeader header;
424 * Peer which sent the request to verify its successor.
426 struct GNUNET_PeerIdentity querying_peer;
429 * Successor to which PeerVerifySuccessorMessage was sent.
431 struct GNUNET_PeerIdentity current_successor;
434 * Current Predecessor of source_successor. It can be same as querying peer
435 * or different. In case it is different then it can be querying_peer's
436 * probable successor.
438 struct GNUNET_PeerIdentity probable_successor;
441 * Trail identifier of trail from querying_peer to current_successor.
443 struct GNUNET_HashCode trail_id;
446 * Direction in which we are looking at the trail.
448 uint32_t trail_direction;
450 /* In case probable_successor != querying_peer, then trail to reach from
451 * querying_peer to probable_successor, NOT including end points.
452 * struct GNUNET_PeerIdentity trail[]
457 * P2P Notify New Successor Message.
459 struct PeerNotifyNewSuccessorMessage
462 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
464 struct GNUNET_MessageHeader header;
467 * Peer which wants to notify its new successor.
469 struct GNUNET_PeerIdentity source_peer;
472 * New successor of source_peer.
474 struct GNUNET_PeerIdentity new_successor;
477 * Unique identifier of the trail from source_peer to new_successor,
478 * NOT including the endpoints.
480 struct GNUNET_HashCode trail_id;
482 /* List of peers in trail from source_peer to new_successor,
483 * NOT including the endpoints.
484 * struct GNUNET_PeerIdentity trail[]
489 * P2P Trail Compression Message.
491 struct PeerTrailCompressionMessage
494 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION
496 struct GNUNET_MessageHeader header;
499 * Source peer of this trail.
501 struct GNUNET_PeerIdentity source_peer;
504 * Trail from source_peer to destination_peer compressed such that
505 * new_first_friend is the first hop in the trail from source to
508 struct GNUNET_PeerIdentity new_first_friend;
511 * Unique identifier of trail.
513 struct GNUNET_HashCode trail_id;
518 * P2P Trail Tear Down message.
520 struct PeerTrailTearDownMessage
523 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
525 struct GNUNET_MessageHeader header;
528 * Unique identifier of the trail.
530 struct GNUNET_HashCode trail_id;
533 * Direction of trail.
535 uint32_t trail_direction;
540 * P2P Trail Rejection Message.
542 struct PeerTrailRejectionMessage
545 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
547 struct GNUNET_MessageHeader header;
550 * Peer which wants to set up the trail.
552 struct GNUNET_PeerIdentity source_peer;
555 * Peer which sent trail rejection message as it it congested.
557 struct GNUNET_PeerIdentity congested_peer;
560 * Peer identity closest to this value will be finger of
563 uint64_t ultimate_destination_finger_value;
566 * Is source_peer trying to setup the trail to its predecessor or finger.
568 uint32_t is_predecessor;
571 * Identifier for the trail that source peer is trying to setup.
573 struct GNUNET_HashCode trail_id;
576 * Relative time for which congested_peer will remain congested.
578 struct GNUNET_TIME_Relative congestion_time;
580 /* Trail_list from source_peer to peer which sent the message for trail setup
581 * to congested peer. This trail does NOT include source_peer.
582 struct GNUNET_PeerIdnetity trail[]*/
586 * P2P Add Trail Message.
588 struct PeerAddTrailMessage
591 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
593 struct GNUNET_MessageHeader header;
596 * Source of the routing trail.
598 struct GNUNET_PeerIdentity source_peer;
601 * Destination of the routing trail.
603 struct GNUNET_PeerIdentity destination_peer;
606 * Unique identifier of the trail from source_peer to destination_peer,
607 * NOT including the endpoints.
609 struct GNUNET_HashCode trail_id;
611 /* Trail from source peer to destination peer, NOT including them.
612 * struct GNUNET_PeerIdentity trail[]
616 GNUNET_NETWORK_STRUCT_END
619 * Linked list of messages to send to a particular other peer.
621 struct P2PPendingMessage
624 * Pointer to next item in the list
626 struct P2PPendingMessage *next;
629 * Pointer to previous item in the list
631 struct P2PPendingMessage *prev;
634 * Message importance level. FIXME: used? useful?
636 unsigned int importance;
639 * When does this message time out?
641 struct GNUNET_TIME_Absolute timeout;
644 * Actual message to be sent, allocated at the end of the struct:
645 * // msg = (cast) &pm[1];
646 * // memcpy (&pm[1], data, len);
648 const struct GNUNET_MessageHeader *msg;
653 * Entry in friend_peermap.
660 struct GNUNET_PeerIdentity id;
663 * Number of trails for which this friend is the first hop or if the friend
666 unsigned int trails_count;
669 * Count of outstanding messages for this friend.
671 unsigned int pending_count;
674 * In case not 0, then amount of time for which this friend is congested.
676 struct GNUNET_TIME_Absolute congestion_timestamp;
679 * Head of pending messages to be sent to this friend.
681 struct P2PPendingMessage *head;
684 * Tail of pending messages to be sent to this friend.
686 struct P2PPendingMessage *tail;
689 * Core handle for sending messages to this friend.
691 struct GNUNET_CORE_TransmitHandle *th;
696 * An individual element of the trail to reach to a finger.
701 * Pointer to next item in the list
703 struct Trail_Element *next;
706 * Pointer to prev item in the list
708 struct Trail_Element *prev;
711 * An element in this trail.
713 struct GNUNET_PeerIdentity peer;
717 * Information about an individual trail.
724 struct Trail_Element *trail_head;
729 struct Trail_Element *trail_tail;
732 * Unique identifier of this trail.
734 struct GNUNET_HashCode trail_id;
737 * Length of trail pointed
739 unsigned int trail_length;
742 * Is there a valid trail entry.
744 unsigned int is_present;
748 * An entry in finger_table
755 struct GNUNET_PeerIdentity finger_identity;
758 * Is any finger stored at this finger index.
760 unsigned int is_present;
763 * Index in finger peer map
765 uint32_t finger_table_index;
768 * Number of trails setup so far for this finger.
769 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
771 uint32_t trails_count;
774 * Array of trails to reach to this finger.
776 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
781 * Stores information about the peer which is closest to destination_finger_value.
782 * 'closest' can be either successor or predecessor depending on is_predecessor
788 * Destination finger value.
790 uint64_t destination_finger_value;
793 * Is finger_value a predecessor or any other finger.
795 unsigned int is_predecessor;
798 * Trail id to reach to peer.
799 * In case peer is my identity or friend, it is set to 0.
801 struct GNUNET_HashCode trail_id;
804 * Next destination. In case of friend and my_identity , it is same as next_hop
805 * In case of finger it is finger identity.
807 struct GNUNET_PeerIdentity best_known_destination;
810 * In case best_known_destination is a finger, then first friend in the trail
811 * to reach to it. In other case, same as best_known_destination.
813 struct GNUNET_PeerIdentity next_hop;
818 * Data structure to store the trail chosen to reach to finger.
820 struct Selected_Finger_Trail
823 * First friend in the trail to reach finger.
825 struct FriendInfo friend;
828 * Identifier of this trail.
830 struct GNUNET_HashCode trail_id;
833 * Total number of peers in this trail.
835 unsigned int trail_length;
839 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
840 * get our first friend.
842 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
845 * Task that sends verify successor message. This task is started when we get
846 * our successor for the first time.
848 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_task;
851 * Identity of this peer.
853 static struct GNUNET_PeerIdentity my_identity;
856 * Peer map of all the friends of a peer
858 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
861 * Array of all the fingers.
863 static struct FingerInfo finger_table [MAX_FINGERS];
868 static struct GNUNET_CORE_Handle *core_api;
871 * Handle for the statistics service.
873 extern struct GNUNET_STATISTICS_Handle *GDS_stats;
876 * The current finger index that we have want to find trail to. We start the
877 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
878 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
879 * we reset this index to 0.
881 static unsigned int current_search_finger_index;
884 * Should we store our topology predecessor and successor IDs into statistics?
886 unsigned int track_topology;
889 * Called when core is ready to send a message we asked for
890 * out to the destination.
892 * @param cls the 'struct FriendInfo' of the target friend
893 * @param size number of bytes available in buf
894 * @param buf where the callee should write the message
895 * @return number of bytes written to buf
898 core_transmit_notify (void *cls, size_t size, void *buf)
900 struct FriendInfo *peer = cls;
902 struct P2PPendingMessage *pending;
907 while ((NULL != (pending = peer->head)) &&
908 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
910 peer->pending_count--;
911 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
912 GNUNET_free (pending);
916 /* no messages pending */
922 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
923 GNUNET_CORE_PRIO_BEST_EFFORT,
924 GNUNET_TIME_absolute_get_remaining
925 (pending->timeout), &peer->id,
926 ntohs (pending->msg->size),
927 &core_transmit_notify, peer);
928 GNUNET_break (NULL != peer->th);
932 while ((NULL != (pending = peer->head)) &&
933 (size - off >= (msize = ntohs (pending->msg->size))))
935 /*GNUNET_STATISTICS_update (GDS_stats,
937 ("# Bytes transmitted to other peers"), msize,
939 memcpy (&cbuf[off], pending->msg, msize);
941 peer->pending_count--;
942 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
943 GNUNET_free (pending);
945 if (peer->head != NULL)
948 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
949 GNUNET_CORE_PRIO_BEST_EFFORT,
950 GNUNET_TIME_absolute_get_remaining
951 (pending->timeout), &peer->id, msize,
952 &core_transmit_notify, peer);
953 GNUNET_break (NULL != peer->th);
960 * Transmit all messages in the friend's message queue.
962 * @param peer message queue to process
965 process_friend_queue (struct FriendInfo *peer)
967 struct P2PPendingMessage *pending;
969 if (NULL == (pending = peer->head))
971 if (NULL != peer->th)
974 GNUNET_STATISTICS_update (GDS_stats,
976 ("# Bytes of bandwidth requested from core"),
977 ntohs (pending->msg->size), GNUNET_NO);
980 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
982 GNUNET_TIME_absolute_get_remaining
983 (pending->timeout), &peer->id,
984 ntohs (pending->msg->size),
985 &core_transmit_notify, peer);
986 GNUNET_break (NULL != peer->th);
991 * Construct a trail setup message and forward it to target_friend
992 * @param source_peer Peer which wants to setup the trail
993 * @param ultimate_destination_finger_value Peer identity closest to this value
994 * will be finger to @a source_peer
995 * @param best_known_destination Best known destination (could be finger or friend)
996 * which should get this message. In case it is
997 * friend, then it is same as target_friend
998 * @param target_friend Friend to which message is forwarded now.
999 * @param trail_length Total number of peers in trail setup so far.
1000 * @param trail_peer_list Trail setup so far
1001 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1002 * @param trail_id Unique identifier for the trail we are trying to setup.
1003 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1004 * best_known_destination when its a finger. If not
1005 * used then set to 0.
1008 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1009 uint64_t ultimate_destination_finger_value,
1010 struct GNUNET_PeerIdentity best_known_destination,
1011 struct FriendInfo *target_friend,
1012 unsigned int trail_length,
1013 const struct GNUNET_PeerIdentity *trail_peer_list,
1014 unsigned int is_predecessor,
1015 struct GNUNET_HashCode trail_id,
1016 struct GNUNET_HashCode intermediate_trail_id)
1018 struct P2PPendingMessage *pending;
1019 struct PeerTrailSetupMessage *tsm;
1020 struct GNUNET_PeerIdentity *peer_list;
1023 msize = sizeof (struct PeerTrailSetupMessage) +
1024 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1026 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1032 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1034 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1038 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1039 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1040 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1041 pending->msg = &tsm->header;
1042 tsm->header.size = htons (msize);
1043 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1044 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1045 tsm->source_peer = source_peer;
1046 tsm->best_known_destination = best_known_destination;
1047 tsm->is_predecessor = htonl (is_predecessor);
1048 tsm->trail_id = trail_id;
1049 tsm->intermediate_trail_id = intermediate_trail_id;
1051 if (trail_length > 0)
1053 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1054 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1057 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1058 target_friend->pending_count++;
1059 process_friend_queue (target_friend);
1064 * Construct a trail setup result message and forward it to target friend.
1065 * @param querying_peer Peer which sent the trail setup request and should get
1067 * @param Finger Peer to which the trail has been setup to.
1068 * @param target_friend Friend to which this message should be forwarded.
1069 * @param trail_length Numbers of peers in the trail.
1070 * @param trail_peer_list Peers which are part of the trail from
1071 * querying_peer to Finger, NOT including them.
1072 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1073 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1075 * @param trail_id Unique identifier of the trail.
1078 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1079 struct GNUNET_PeerIdentity finger,
1080 struct FriendInfo *target_friend,
1081 unsigned int trail_length,
1082 const struct GNUNET_PeerIdentity *trail_peer_list,
1083 unsigned int is_predecessor,
1084 uint64_t ultimate_destination_finger_value,
1085 struct GNUNET_HashCode trail_id)
1087 struct P2PPendingMessage *pending;
1088 struct PeerTrailSetupResultMessage *tsrm;
1089 struct GNUNET_PeerIdentity *peer_list;
1092 msize = sizeof (struct PeerTrailSetupResultMessage) +
1093 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1095 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1101 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1103 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1107 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1108 pending->importance = 0;
1109 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1110 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1111 pending->msg = &tsrm->header;
1112 tsrm->header.size = htons (msize);
1113 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1114 tsrm->querying_peer = querying_peer;
1115 tsrm->finger_identity = finger;
1116 tsrm->is_predecessor = htonl (is_predecessor);
1117 tsrm->trail_id = trail_id;
1118 tsrm->ulitmate_destination_finger_value =
1119 GNUNET_htonll (ultimate_destination_finger_value);
1120 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1122 if (trail_length > 0)
1124 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1126 /* Send the message to chosen friend. */
1127 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1128 target_friend->pending_count++;
1129 process_friend_queue (target_friend);
1134 * Send trail rejection message to target friend
1135 * @param source_peer Peer which is trying to setup the trail.
1136 * @param ultimate_destination_finger_value Peer closest to this value will be
1137 * @a source_peer's finger
1138 * @param congested_peer Peer which sent this message as it is congested.
1139 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1140 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1141 * by congested_peer. This does NOT include @a source_peer
1142 * and congested_peer.
1143 * @param trail_length Total number of peers in trail_peer_list, NOT including
1144 * @a source_peer and @a congested_peer
1145 * @param trail_id Unique identifier of this trail.
1146 * @param congestion_timeout Duration given by congested peer as an estimate of
1147 * how long it may remain congested.
1150 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1151 uint64_t ultimate_destination_finger_value,
1152 struct GNUNET_PeerIdentity congested_peer,
1153 unsigned int is_predecessor,
1154 const struct GNUNET_PeerIdentity *trail_peer_list,
1155 unsigned int trail_length,
1156 struct GNUNET_HashCode trail_id,
1157 struct FriendInfo *target_friend,
1158 const struct GNUNET_TIME_Relative congestion_timeout)
1160 struct PeerTrailRejectionMessage *trm;
1161 struct P2PPendingMessage *pending;
1162 struct GNUNET_PeerIdentity *peer_list;
1165 msize = sizeof (struct PeerTrailRejectionMessage) +
1166 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1168 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1174 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1176 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1180 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1181 pending->importance = 0;
1182 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1183 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1184 pending->msg = &trm->header;
1185 trm->header.size = htons (msize);
1186 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1187 trm->source_peer = source_peer;
1188 trm->congested_peer = congested_peer;
1189 trm->congestion_time = congestion_timeout;
1190 trm->is_predecessor = htonl (is_predecessor);
1191 trm->trail_id = trail_id;
1192 trm->ultimate_destination_finger_value =
1193 GNUNET_htonll (ultimate_destination_finger_value);
1195 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1196 if (trail_length > 0)
1198 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1201 /* Send the message to chosen friend. */
1202 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1203 target_friend->pending_count++;
1204 process_friend_queue (target_friend);
1209 * Construct a verify successor message and forward it to target_friend.
1210 * @param source_peer Peer which wants to verify its successor.
1211 * @param successor Peer which is @a source_peer's current successor.
1212 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1213 * NOT including them.
1214 * @param trail List of peers which are part of trail to reach from @a source_peer
1215 * to @a successor, NOT including them.
1216 * @param trail_length Total number of peers in @a trail.
1217 * @param target_friend Next friend to get this message.
1220 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1221 struct GNUNET_PeerIdentity successor,
1222 struct GNUNET_HashCode trail_id,
1223 struct GNUNET_PeerIdentity *trail,
1224 unsigned int trail_length,
1225 struct FriendInfo *target_friend)
1227 struct PeerVerifySuccessorMessage *vsm;
1228 struct P2PPendingMessage *pending;
1229 struct GNUNET_PeerIdentity *peer_list;
1232 msize = sizeof (struct PeerVerifySuccessorMessage) +
1233 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1234 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1240 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1242 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1246 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1247 pending->importance = 0; /* FIXME */
1248 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1249 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1250 pending->msg = &vsm->header;
1251 vsm->header.size = htons (msize);
1252 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1253 vsm->source_peer = source_peer;
1254 vsm->successor = successor;
1255 vsm->trail_id = trail_id;
1257 if (trail_length != 0)
1259 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1260 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1263 /* Send the message to chosen friend. */
1264 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1265 target_friend->pending_count++;
1266 process_friend_queue (target_friend);
1271 * FIXME: In every function we pass target friend except for this one.
1272 * so, either change everything or this one. also, should se just store
1273 * the pointer to friend in routing table rather than gnunet_peeridentity.
1274 * if yes then we should keep friend info in.h andmake lot of changes.
1275 * Construct a trail teardown message and forward it to target friend.
1276 * @param trail_id Unique identifier of the trail.
1277 * @param trail_direction Direction of trail.
1278 * @param target_friend Friend to get this message.
1281 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1282 unsigned int trail_direction,
1283 struct GNUNET_PeerIdentity peer)
1285 struct PeerTrailTearDownMessage *ttdm;
1286 struct P2PPendingMessage *pending;
1287 struct FriendInfo *target_friend;
1290 msize = sizeof (struct PeerTrailTearDownMessage);
1292 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1298 /*FIXME:In what case friend can be null. ?*/
1299 if (NULL == (target_friend =
1300 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1303 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1305 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1309 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1310 pending->importance = 0; /* FIXME */
1311 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1312 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1313 pending->msg = &ttdm->header;
1314 ttdm->header.size = htons (msize);
1315 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1316 ttdm->trail_id = trail_id;
1317 ttdm->trail_direction = htonl (trail_direction);
1319 /* Send the message to chosen friend. */
1320 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1321 target_friend->pending_count++;
1322 process_friend_queue (target_friend);
1327 * Construct a verify successor result message and send it to target_friend
1328 * @param querying_peer Peer which sent the verify successor message.
1329 * @param source_successor Current_successor of @a querying_peer.
1330 * @param current_predecessor Current predecessor of @a successor. Could be same
1331 * or different from @a querying_peer.
1332 * @param trail_id Unique identifier of the trail from @a querying_peer to
1333 * @a successor, NOT including them.
1334 * @param trail List of peers which are part of trail from @a querying_peer to
1335 * @a successor, NOT including them.
1336 * @param trail_length Total number of peers in @a trail
1337 * @param trail_direction Direction in which we are sending the message. In this
1338 * case we are sending result from @a successor to @a querying_peer.
1339 * @param target_friend Next friend to get this message.
1342 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1343 struct GNUNET_PeerIdentity current_successor,
1344 struct GNUNET_PeerIdentity probable_successor,
1345 struct GNUNET_HashCode trail_id,
1346 const struct GNUNET_PeerIdentity *trail,
1347 unsigned int trail_length,
1348 enum GDS_ROUTING_trail_direction trail_direction,
1349 struct FriendInfo *target_friend)
1351 struct PeerVerifySuccessorResultMessage *vsmr;
1352 struct P2PPendingMessage *pending;
1353 struct GNUNET_PeerIdentity *peer_list;
1356 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1357 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1359 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1365 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1367 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1371 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1372 pending->importance = 0; /* FIXME */
1373 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1374 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1375 pending->msg = &vsmr->header;
1376 vsmr->header.size = htons (msize);
1377 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1378 vsmr->querying_peer = querying_peer;
1379 vsmr->current_successor = current_successor;
1380 vsmr->probable_successor = probable_successor;
1381 vsmr->trail_direction = htonl (trail_direction);
1382 vsmr->trail_id = trail_id;
1384 if (trail_length > 0)
1386 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1387 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1390 /* Send the message to chosen friend. */
1391 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1392 target_friend->pending_count++;
1393 process_friend_queue (target_friend);
1398 * Construct a notify new successor message and send it to target_friend
1399 * @param source_peer Peer which wants to notify to its new successor that it
1400 * could be its predecessor.
1401 * @param successor New successor of @a source_peer
1402 * @param successor_trail List of peers in Trail to reach from
1403 * @a source_peer to @a new_successor, NOT including
1405 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1406 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1407 * @param target_friend Next friend to get this message.
1410 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1411 struct GNUNET_PeerIdentity successor,
1412 const struct GNUNET_PeerIdentity *successor_trail,
1413 unsigned int successor_trail_length,
1414 struct GNUNET_HashCode succesor_trail_id,
1415 struct FriendInfo *target_friend)
1417 struct PeerNotifyNewSuccessorMessage *nsm;
1418 struct P2PPendingMessage *pending;
1419 struct GNUNET_PeerIdentity *peer_list;
1422 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1423 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1425 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1431 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1433 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1437 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1438 pending->importance = 0; /* FIXME */
1439 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1440 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1441 pending->msg = &nsm->header;
1442 nsm->header.size = htons (msize);
1443 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1444 nsm->new_successor = successor;
1445 nsm->source_peer = source_peer;
1446 nsm->trail_id = succesor_trail_id;
1448 if (successor_trail_length > 0)
1450 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1451 memcpy (peer_list, successor_trail,
1452 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1455 /* Send the message to chosen friend. */
1456 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1457 target_friend->pending_count++;
1458 process_friend_queue (target_friend);
1463 * Construct an add_trail message and send it to target_friend
1464 * @param source_peer Source of the trail.
1465 * @param destination_peer Destination of the trail.
1466 * @param trail_id Unique identifier of the trail from
1467 * @a source_peer to @a destination_peer, NOT including the endpoints.
1468 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1469 * NOT including the endpoints.
1470 * @param trail_length Total number of peers in @a trail.
1471 * @param target_friend Next friend to get this message.
1474 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1475 struct GNUNET_PeerIdentity destination_peer,
1476 struct GNUNET_HashCode trail_id,
1477 const struct GNUNET_PeerIdentity *trail,
1478 unsigned int trail_length,
1479 struct FriendInfo *target_friend)
1481 struct PeerAddTrailMessage *adm;
1482 struct GNUNET_PeerIdentity *peer_list;
1483 struct P2PPendingMessage *pending;
1486 msize = sizeof (struct PeerAddTrailMessage) +
1487 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1489 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1495 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1497 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1501 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1502 pending->importance = 0; /* FIXME */
1503 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1504 adm = (struct PeerAddTrailMessage *) &pending[1];
1505 pending->msg = &adm->header;
1506 adm->header.size = htons (msize);
1507 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1508 adm->source_peer = source_peer;
1509 adm->destination_peer = destination_peer;
1510 adm->trail_id = trail_id;
1512 if (trail_length > 0)
1514 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1515 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1517 /* Send the message to chosen friend. */
1518 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1519 target_friend->pending_count++;
1520 process_friend_queue (target_friend);
1526 * Construct a trail compression message and send it to target_friend.
1527 * @param source_peer Source of the trail.
1528 * @param trail_id Unique identifier of trail.
1529 * @param first_friend First hop in compressed trail to reach from source to finger
1530 * @param target_friend Next friend to get this message.
1533 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1534 struct GNUNET_HashCode trail_id,
1535 struct GNUNET_PeerIdentity first_friend,
1536 struct FriendInfo *target_friend)
1538 struct P2PPendingMessage *pending;
1539 struct PeerTrailCompressionMessage *tcm;
1542 msize = sizeof (struct PeerTrailCompressionMessage);
1544 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1550 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1552 GNUNET_STATISTICS_update (GDS_stats,
1553 gettext_noop ("# P2P messages dropped due to full queue"),
1557 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1558 pending->importance = 0; /* FIXME */
1559 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1560 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1561 pending->msg = &tcm->header;
1562 tcm->header.size = htons (msize);
1563 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1564 tcm->source_peer = source_peer;
1565 tcm->new_first_friend = first_friend;
1566 tcm->trail_id = trail_id;
1568 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1569 target_friend->pending_count++;
1570 process_friend_queue (target_friend);
1576 * Search my location in trail. In case I am present more than once in the
1577 * trail (can happen during trail setup), then return my lowest index.
1578 * @param trail List of peers
1579 * @return my_index if found
1580 * -1 if no entry found.
1583 search_my_index (const struct GNUNET_PeerIdentity *trail,
1587 int lowest_index = -1;
1589 for (i = 0; i < trail_length; i++)
1591 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1596 return lowest_index;
1601 * Check if the friend is congested or have reached maximum number of trails
1602 * it can be part of of.
1603 * @param friend Friend to be checked.
1604 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1605 * #GNUNET_YES if friend is either congested or have crossed threshold
1608 is_friend_congested (struct FriendInfo *friend)
1610 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1611 ((0 == GNUNET_TIME_absolute_get_remaining
1612 (friend->congestion_timestamp).rel_value_us)))
1620 * FIXME; not handling the wrap around logic correctly.
1621 * Select closest finger to value.
1622 * @param peer1 First peer
1623 * @param peer2 Second peer
1624 * @param value Value to be compare
1625 * @return Closest peer
1627 static struct GNUNET_PeerIdentity *
1628 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1629 struct GNUNET_PeerIdentity *peer2,
1632 uint64_t peer1_value;
1633 uint64_t peer2_value;
1635 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1636 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1637 peer1_value = GNUNET_ntohll (peer1_value);
1638 peer2_value = GNUNET_ntohll (peer2_value);
1640 if (peer1_value == value)
1645 if (peer2_value == value)
1650 if (peer2_value < peer1_value)
1652 if ((peer2_value < value) && (value < peer1_value))
1656 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1657 ((0 < value) && (value < peer2_value)))
1663 if (peer1_value < peer2_value)
1665 if ((peer1_value < value) && (value < peer2_value))
1669 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1670 ((0 < value) && (value < peer1_value)))
1680 * Select closest predecessor to value.
1681 * @param peer1 First peer
1682 * @param peer2 Second peer
1683 * @param value Value to be compare
1684 * @return Peer which precedes value in the network.
1686 static struct GNUNET_PeerIdentity *
1687 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1688 struct GNUNET_PeerIdentity *peer2,
1691 uint64_t peer1_value;
1692 uint64_t peer2_value;
1694 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1695 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1696 peer1_value = GNUNET_ntohll (peer1_value);
1697 peer2_value = GNUNET_ntohll (peer2_value);
1699 if (peer1_value == value)
1702 if (peer2_value == value)
1705 if (peer1_value < peer2_value)
1707 if ((peer1_value < value) && (value < peer2_value))
1711 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1712 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1718 if (peer2_value < peer1_value)
1720 if ((peer2_value < value) && (value < peer1_value))
1724 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1725 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1735 * This is a test function to print all the entries of friend table.
1738 test_friend_peermap_print ()
1740 struct FriendInfo *friend;
1741 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1742 struct GNUNET_PeerIdentity print_peer;
1743 struct GNUNET_PeerIdentity key_ret;
1746 print_peer = my_identity;
1747 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1748 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1750 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1752 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1754 (const void **)&friend))
1756 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1757 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1758 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1764 * This is a test function, to print all the entries of finger table.
1767 test_finger_table_print()
1769 struct FingerInfo *finger;
1770 struct GNUNET_PeerIdentity print_peer;
1771 //struct Trail *trail;
1775 print_peer = my_identity;
1776 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1777 for (i = 0; i < MAX_FINGERS; i++)
1779 finger = &finger_table[i];
1781 if (GNUNET_NO == finger->is_present)
1784 print_peer = finger->finger_identity;
1785 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1786 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1789 for (j = 0; j < finger->trails_count; j++)
1791 trail = &finger->trail_list[j];
1792 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1793 struct Trail_Element *element;
1794 element = trail->trail_head;
1795 for (k = 0; k < trail->trail_length; k++)
1797 print_peer = element->peer;
1798 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1799 element = element->next;
1808 * Select the closest peer among two peers (which should not be same)
1809 * with respect to value and finger_table_index
1810 * NOTE: peer1 != peer2
1811 * @param peer1 First peer
1812 * @param peer2 Second peer
1813 * @param value Value relative to which we find the closest
1814 * @param is_predecessor Is value a predecessor or any other finger.
1815 * @return Closest peer among two peers.
1817 static struct GNUNET_PeerIdentity *
1818 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1819 struct GNUNET_PeerIdentity *peer2,
1821 unsigned int is_predecessor)
1823 struct GNUNET_PeerIdentity *closest_peer;
1825 if (1 == is_predecessor)
1827 closest_peer = select_closest_predecessor (peer1, peer2, value);
1832 closest_peer = select_closest_finger (peer1, peer2, value);
1834 return closest_peer;
1839 * Iterate over the list of all the trails of a finger. In case the first
1840 * friend to reach the finger has reached trail threshold or is congested,
1841 * then don't select it. In case there multiple available good trails to reach
1842 * to Finger, choose the one with shortest trail length.
1843 * Note: We use length as parameter. But we can use any other suitable parameter
1845 * @param finger Finger
1846 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1847 * and trail length. NULL in case none of the trails are free.
1849 static struct Selected_Finger_Trail *
1850 select_finger_trail (struct FingerInfo *finger)
1852 struct FriendInfo *friend;
1853 struct Trail *iterator;
1854 struct Selected_Finger_Trail *finger_trail;
1856 unsigned int flag = 0;
1859 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1860 GNUNET_assert (finger->trails_count > 0);
1862 for (i = 0; i < finger->trails_count; i++)
1864 iterator = &finger->trail_list[i];
1866 /* No trail stored at this index. */
1867 if (GNUNET_NO == iterator->is_present)
1870 GNUNET_assert (NULL !=
1872 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1873 &iterator->trail_head->peer)));
1875 /* First friend to reach trail is not free. */
1876 if (GNUNET_YES == is_friend_congested (friend))
1885 finger_trail->trail_length = iterator->trail_length;
1886 finger_trail->friend = *friend;
1887 finger_trail->trail_id = iterator->trail_id;
1889 else if (finger_trail->trail_length > iterator->trail_length)
1891 finger_trail->friend = *friend;
1892 finger_trail->trail_id = iterator->trail_id;
1893 finger_trail->trail_length = iterator->trail_length;
1897 /* All the first friend in all the trails to reach to finger are either
1898 congested or have crossed trail threshold. */
1899 if (j == finger->trails_count)
1902 return finger_trail;
1907 * Compare FINGER entry with current successor. If finger's first friend of all
1908 * its trail is not congested and has not crossed trail threshold, then check
1909 * if finger peer identity is closer to final_destination_finger_value than
1910 * current_successor. If yes then update current_successor.
1911 * @param current_successor[in/out]
1915 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1917 struct FingerInfo *finger;
1918 struct GNUNET_PeerIdentity *closest_peer;
1919 struct Selected_Finger_Trail *finger_trail;
1922 /* Iterate over finger table. */
1923 for (i = 0; i < MAX_FINGERS; i++)
1925 finger = &finger_table[i];
1927 if (GNUNET_NO == finger->is_present)
1930 /* If my identity is same as current closest peer then don't consider me*/
1932 GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1933 ¤t_closest_peer->best_known_destination))
1936 /* If I am my own finger, then ignore this finger. */
1937 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1941 /* If finger is a friend, then do nothing. As we have already checked
1942 * for each friend in compare_friend_and_current_successor(). */
1943 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1944 &finger->finger_identity)))
1949 /* Choose one of the trail to reach to finger. */
1950 finger_trail = select_finger_trail (finger);
1952 /* In case no trail found, ignore this finger. */
1953 if (NULL == finger_trail)
1956 closest_peer = select_closest_peer (&finger->finger_identity,
1957 ¤t_closest_peer->best_known_destination,
1958 current_closest_peer->destination_finger_value,
1959 current_closest_peer->is_predecessor);
1961 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1964 current_closest_peer->best_known_destination = finger->finger_identity;
1965 current_closest_peer->next_hop = finger_trail->friend.id;
1966 current_closest_peer->trail_id = finger_trail->trail_id;
1967 //GNUNET_free(finger_trail);//FIXME: where should we free the finger trail.
1975 * Compare friend entry with current successor.
1976 * If friend identity and current_successor is same, then do nothing.
1977 * If friend is not congested and has not crossed trail threshold, then check
1978 * if friend peer identity is closer to final_destination_finger_value than
1979 * current_successor. If yes then update current_successor.
1980 * @param cls closure
1981 * @param key current public key
1982 * @param value struct Closest_Peer
1983 * @return #GNUNET_YES if we should continue to iterate,
1984 * #GNUNET_NO if not.
1987 compare_friend_and_current_closest_peer (void *cls,
1988 const struct GNUNET_PeerIdentity *key,
1991 struct FriendInfo *friend = value;
1992 struct Closest_Peer *current_closest_peer = cls;
1993 struct GNUNET_PeerIdentity *closest_peer;
1995 /* Friend is either congested or has crossed threshold. */
1996 if (GNUNET_YES == is_friend_congested (friend))
1999 /* If current_closest_peer and friend identity are same, then do nothing.*/
2001 GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2002 ¤t_closest_peer->best_known_destination))
2005 closest_peer = select_closest_peer (&friend->id,
2006 ¤t_closest_peer->best_known_destination,
2007 current_closest_peer->destination_finger_value,
2008 current_closest_peer->is_predecessor);
2010 /* Is friend the closest successor? */
2011 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id, closest_peer))
2013 current_closest_peer->best_known_destination = friend->id;
2014 current_closest_peer->next_hop = friend->id;
2022 * Initialize current_successor to my_identity.
2023 * @param my_identity My peer identity
2024 * @return Updated closest_peer
2026 static struct Closest_Peer
2027 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2028 uint64_t destination_finger_value,
2029 unsigned int is_predecessor)
2031 struct Closest_Peer current_closest_peer;
2033 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2034 current_closest_peer.destination_finger_value = destination_finger_value;
2035 current_closest_peer.is_predecessor = is_predecessor;
2036 current_closest_peer.next_hop = my_identity;
2037 current_closest_peer.best_known_destination = my_identity;
2039 return current_closest_peer;
2044 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2045 * peer. It could be because of the logic we wrote here. Verify if its correct.
2046 * If not then return immediate_successor.
2048 * Find the successor for destination_finger_value among my_identity, my
2049 * friends and my fingers. Don't consider friends or fingers which are either
2050 * congested or have crossed the threshold.
2051 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2053 * @param destination_finger_value Peer closest to this value will be the next successor.
2054 * @param is_predecessor Are we looking for predecessor or finger?
2055 * @return Successor It is never NULL, in case none of friend or finger is closest,
2056 * then we return my_identity.
2058 static struct Closest_Peer
2059 find_successor (uint64_t destination_finger_value,
2060 unsigned int is_predecessor)
2062 struct Closest_Peer current_closest_peer;
2064 /* Initialize current_successor to my_identity. */
2065 current_closest_peer = init_current_successor (my_identity,
2066 destination_finger_value,
2069 /* Compare each friend entry with current_successor and update current_successor
2070 * with friend if its closest. */
2073 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2074 &compare_friend_and_current_closest_peer,
2075 ¤t_closest_peer));
2077 /* Compare each finger entry with current_successor and update current_successor
2078 * with finger if its closest. */
2079 compare_finger_and_current_successor (¤t_closest_peer);
2081 return current_closest_peer;
2086 * Construct a Put message and send it to target_peer.
2087 * @param key Key for the content
2088 * @param block_type Type of the block
2089 * @param options Routing options
2090 * @param desired_replication_level Desired replication count
2091 * @param best_known_dest Peer to which this message should reach eventually,
2092 * as it is best known destination to me.
2093 * @param intermediate_trail_id Trail id in case
2094 * @param target_peer Peer to which this message will be forwarded.
2095 * @param hop_count Number of hops traversed so far.
2096 * @param put_path_length Total number of peers in @a put_path
2097 * @param put_path Number of peers traversed so far
2098 * @param expiration_time When does the content expire
2099 * @param data Content to store
2100 * @param data_size Size of content @a data in bytes
2103 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2104 enum GNUNET_BLOCK_Type block_type,
2105 enum GNUNET_DHT_RouteOption options,
2106 uint32_t desired_replication_level,
2107 struct GNUNET_PeerIdentity best_known_dest,
2108 struct GNUNET_HashCode intermediate_trail_id,
2109 struct GNUNET_PeerIdentity *target_peer,
2111 uint32_t put_path_length,
2112 struct GNUNET_PeerIdentity *put_path,
2113 struct GNUNET_TIME_Absolute expiration_time,
2114 const void *data, size_t data_size)
2116 struct PeerPutMessage *ppm;
2117 struct P2PPendingMessage *pending;
2118 struct FriendInfo *target_friend;
2119 struct GNUNET_PeerIdentity *pp;
2120 struct GNUNET_PeerIdentity next_hop;
2124 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2125 sizeof (struct PeerPutMessage);
2127 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2129 put_path_length = 0;
2130 msize = data_size + sizeof (struct PeerPutMessage);
2133 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2139 /* This is the first call made from clients file. So, we should search for the
2141 if (NULL == target_peer)
2144 struct Closest_Peer successor;
2146 memcpy (&key_value, key, sizeof (uint64_t));
2147 key_value = GNUNET_ntohll (key_value);
2149 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2150 best_known_dest = successor.best_known_destination;
2151 next_hop = successor.next_hop;
2152 intermediate_trail_id = successor.trail_id;
2154 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2156 /* I am the destination. */
2157 GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL,
2158 ntohl (block_type),data_size,data);
2162 GNUNET_assert (NULL !=
2164 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2168 GNUNET_assert (NULL !=
2170 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2173 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2174 pending->timeout = expiration_time;
2175 ppm = (struct PeerPutMessage *) &pending[1];
2176 pending->msg = &ppm->header;
2177 ppm->header.size = htons (msize);
2178 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2179 ppm->options = htonl (options);
2180 ppm->block_type = htonl (block_type);
2181 ppm->hop_count = htonl (hop_count + 1);
2182 ppm->desired_replication_level = htonl (desired_replication_level);
2183 ppm->put_path_length = htonl (put_path_length);
2184 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2185 ppm->best_known_destination = best_known_dest;
2188 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2189 if (put_path_length != 0)
2191 memcpy (pp, put_path,
2192 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2194 memcpy (&pp[put_path_length], data, data_size);
2196 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2197 target_friend->pending_count++;
2198 process_friend_queue (target_friend);
2203 * Construct a Get message and send it to target_peer.
2204 * @param key Key for the content
2205 * @param block_type Type of the block
2206 * @param options Routing options
2207 * @param desired_replication_level Desired replication count
2208 * @param best_known_dest Peer which should get this message. Same as target peer
2209 * if best_known_dest is a friend else its a finger.
2210 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2211 * in case it is a finger else set to 0.
2212 * @param target_peer Peer to which this message will be forwarded.
2213 * @param hop_count Number of hops traversed so far.
2214 * @param data Content to store
2215 * @param data_size Size of content @a data in bytes
2216 * @param get_path_length Total number of peers in @a get_path
2217 * @param get_path Number of peers traversed so far
2220 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2221 enum GNUNET_BLOCK_Type block_type,
2222 enum GNUNET_DHT_RouteOption options,
2223 uint32_t desired_replication_level,
2224 struct GNUNET_PeerIdentity best_known_dest,
2225 struct GNUNET_HashCode intermediate_trail_id,
2226 struct GNUNET_PeerIdentity *target_peer,
2228 uint32_t get_path_length,
2229 struct GNUNET_PeerIdentity *get_path)
2231 struct PeerGetMessage *pgm;
2232 struct P2PPendingMessage *pending;
2233 struct FriendInfo *target_friend;
2234 struct GNUNET_PeerIdentity *gp;
2237 msize = sizeof (struct PeerGetMessage) +
2238 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2240 /* In this case we don't make get_path_length = 0, as we need get path to
2241 * return the message back to querying client. */
2242 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2248 /* This is the first time we got request from our own client file. */
2249 if (NULL == target_peer)
2252 struct Closest_Peer successor;
2254 memcpy (&key_value, key, sizeof (uint64_t));
2255 key_value = GNUNET_ntohll (key_value);
2256 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2258 best_known_dest = successor.best_known_destination;
2259 intermediate_trail_id = successor.trail_id;
2261 /* I am the destination. I have the data. */
2262 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2265 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2266 NULL, 0, 1, &my_identity, NULL,&my_identity);
2272 GNUNET_assert (NULL !=
2274 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2275 &successor.next_hop)));
2281 GNUNET_assert (NULL !=
2283 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); //FIXME: assertion fails.
2286 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2287 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2288 pending->importance = 0; /* FIXME */
2289 pgm = (struct PeerGetMessage *) &pending[1];
2290 pending->msg = &pgm->header;
2291 pgm->header.size = htons (msize);
2292 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2293 pgm->get_path_length = htonl (get_path_length);
2294 pgm->best_known_destination = best_known_dest;
2296 pgm->intermediate_trail_id = intermediate_trail_id;
2297 pgm->hop_count = htonl (hop_count + 1);
2298 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2300 if (get_path_length != 0)
2302 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2305 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2306 target_friend->pending_count++;
2307 process_friend_queue (target_friend);
2312 * Send the get result to requesting client.
2313 * @param key Key of the requested data.
2314 * @param type Block type
2315 * @param target_peer Next peer to forward the message to.
2316 * @param source_peer Peer which has the data for the key.
2317 * @param put_path_length Number of peers in @a put_path
2318 * @param put_path Path taken to put the data at its stored location.
2319 * @param get_path_length Number of peers in @a get_path
2320 * @param get_path Path taken to reach to the location of the key.
2321 * @param expiration When will this result expire?
2322 * @param data Payload to store
2323 * @param data_size Size of the @a data
2326 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2327 enum GNUNET_BLOCK_Type type,
2328 const struct GNUNET_PeerIdentity *target_peer,
2329 const struct GNUNET_PeerIdentity *source_peer,
2330 unsigned int put_path_length,
2331 const struct GNUNET_PeerIdentity *put_path,
2332 unsigned int get_path_length,
2333 const struct GNUNET_PeerIdentity *get_path,
2334 struct GNUNET_TIME_Absolute expiration,
2335 const void *data, size_t data_size)
2337 struct PeerGetResultMessage *get_result;
2338 struct GNUNET_PeerIdentity *paths;
2339 struct P2PPendingMessage *pending;
2340 struct FriendInfo *target_friend;
2341 int current_path_index;
2344 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2346 sizeof (struct PeerGetResultMessage);
2348 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2354 current_path_index = 0;
2355 if(get_path_length > 0)
2357 current_path_index = search_my_index(get_path, get_path_length);
2358 if (-1 == current_path_index)
2364 if (0 == current_path_index)
2366 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2367 get_path, put_path_length,
2368 put_path, type, data_size, data);
2372 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2373 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2374 pending->importance = 0;
2375 get_result = (struct PeerGetResultMessage *)&pending[1];
2376 pending->msg = &get_result->header;
2377 get_result->header.size = htons (msize);
2378 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2379 get_result->key = *key;
2380 get_result->querying_peer = *source_peer;
2381 get_result->expiration_time = expiration;
2382 get_result->get_path_length = htonl (get_path_length);
2383 get_result->put_path_length = htonl (put_path_length);
2384 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2385 memcpy (paths, put_path,
2386 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2387 memcpy (&paths[put_path_length], get_path,
2388 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2389 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2391 GNUNET_assert (NULL !=
2393 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2394 &get_path[current_path_index - 1])));
2395 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2396 target_friend->pending_count++;
2397 process_friend_queue (target_friend);
2402 * Randomly choose one of your friends (which is not congested and have not crossed
2403 * trail threshold) from the friend_peermap
2404 * @return Friend Randomly chosen friend.
2405 * NULL in case friend peermap is empty, or all the friends are either
2406 * congested or have crossed trail threshold.
2408 static struct FriendInfo *
2409 select_random_friend ()
2411 unsigned int current_size;
2414 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2415 struct GNUNET_PeerIdentity key_ret;
2416 struct FriendInfo *friend;
2418 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2421 if (0 == current_size)
2424 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2425 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2427 /* Iterate till you don't reach to index. */
2428 for (j = 0; j < index ; j++)
2429 GNUNET_assert (GNUNET_YES ==
2430 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2433 /* Reset the index in friend peermap to 0 as we reached to the end. */
2434 if (j == current_size)
2437 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2438 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2442 /* Get the friend stored at the index, j*/
2443 GNUNET_assert (GNUNET_YES ==
2444 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2446 (const void **)&friend));
2448 /* This friend is not congested and has not crossed trail threshold. */
2449 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2450 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2456 } while (j != index);
2458 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2464 * Compute 64 bit value of finger_identity corresponding to a finger index using
2466 * For all fingers, n.finger[i] = n + pow (2,i),
2467 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2468 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2469 * @param finger_index Index corresponding to which we calculate 64 bit value.
2470 * @return 64 bit value.
2473 compute_finger_identity_value (unsigned int finger_index)
2477 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2478 my_id64 = GNUNET_ntohll (my_id64);
2480 /* Are we looking for immediate predecessor? */
2481 if (PREDECESSOR_FINGER_ID == finger_index)
2482 return (my_id64 - 1);
2485 uint64_t add = (uint64_t)1 << finger_index;
2486 return (my_id64 + add);
2492 * Choose a random friend. Calculate the next finger identity to search,from
2493 * current_search_finger_index. Start looking for the trail to reach to
2494 * finger identity through this random friend.
2496 * @param cls closure for this task
2497 * @param tc the context under which the task is running
2500 send_find_finger_trail_message (void *cls,
2501 const struct GNUNET_SCHEDULER_TaskContext *tc)
2503 struct FriendInfo *target_friend;
2504 struct GNUNET_TIME_Relative next_send_time;
2505 struct GNUNET_HashCode trail_id;
2506 struct GNUNET_HashCode intermediate_trail_id;
2507 unsigned int is_predecessor;
2508 uint64_t finger_id_value;
2510 /* Schedule another send_find_finger_trail_message task. */
2511 next_send_time.rel_value_us =
2512 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
2513 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2514 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2515 find_finger_trail_task =
2516 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
2519 /* No space in my routing table. (Source and destination peers also store entries
2520 * in their routing table). */
2521 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2525 target_friend = select_random_friend ();
2526 if (NULL == target_friend)
2531 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2533 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2538 /* Generate a unique trail id for trail we are trying to setup. */
2539 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2540 &trail_id, sizeof (trail_id));
2541 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2543 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2544 target_friend->id, target_friend, 0, NULL,
2545 is_predecessor, trail_id,
2546 intermediate_trail_id);
2551 * In case there are already maximum number of possible trails to reach to a
2552 * finger, then check if the new trail's length is lesser than any of the
2554 * If yes then replace that old trail by new trail.
2556 * Note: Here we are taking length as a parameter to choose the best possible
2557 * trail, but there could be other parameters also like:
2558 * 1. duration of existence of a trail - older the better.
2559 * 2. if the new trail is completely disjoint than the
2560 * other trails, then may be choosing it is better.
2562 * @param existing_finger
2563 * @param new_finger_trail
2564 * @param new_finger_trail_length
2565 * @param new_finger_trail_id
2568 select_and_replace_trail (struct FingerInfo *existing_finger,
2569 const struct GNUNET_PeerIdentity *new_trail,
2570 unsigned int new_trail_length,
2571 struct GNUNET_HashCode new_trail_id)
2573 struct Trail *trail_list_iterator;
2574 unsigned int largest_trail_length;
2575 unsigned int largest_trail_index;
2576 struct Trail_Element *trail_element;
2579 largest_trail_length = new_trail_length;
2580 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2582 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2584 for (i = 0; i < existing_finger->trails_count; i++)
2586 trail_list_iterator = &existing_finger->trail_list[i];
2587 if (trail_list_iterator->trail_length > largest_trail_length)
2589 largest_trail_length = trail_list_iterator->trail_length;
2590 largest_trail_index = i;
2594 /* New trail is not better than existing ones. Send trail teardown. */
2595 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2597 struct GNUNET_PeerIdentity next_hop;
2599 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2600 GDS_ROUTING_remove_trail (new_trail_id);
2601 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2602 GDS_ROUTING_SRC_TO_DEST,
2607 /* Send trail teardown message across the replaced trail. */
2608 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2609 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2610 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2611 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2612 GDS_ROUTING_SRC_TO_DEST,
2613 replace_trail->trail_head->peer);
2614 /* Free the trail. */
2615 while (NULL != (trail_element = replace_trail->trail_head))
2617 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2618 replace_trail->trail_tail, trail_element);
2619 GNUNET_free_non_null (trail_element);
2622 /* Add new trial at that location. */
2623 replace_trail->is_present = GNUNET_YES;
2624 replace_trail->trail_length = new_trail_length;
2625 replace_trail->trail_id = new_trail_id;
2626 //FIXME: Do we need to add pointers for head and tail.
2628 while (i < new_trail_length)
2630 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2631 element->peer = new_trail[i];
2633 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2634 replace_trail->trail_tail,
2641 * Check if the new trail to reach to finger is unique or do we already have
2642 * such a trail present for finger.
2643 * @param existing_finger Finger identity
2644 * @param new_trail New trail to reach @a existing_finger
2645 * @param trail_length Total number of peers in new_trail.
2646 * @return #GNUNET_YES if the new trail is unique
2647 * #GNUNET_NO if same trail is already present.
2650 is_new_trail_unique (struct FingerInfo *existing_finger,
2651 const struct GNUNET_PeerIdentity *new_trail,
2652 unsigned int trail_length)
2654 struct Trail *trail_list_iterator;
2655 struct Trail_Element *trail_element;
2658 int trail_unique = GNUNET_NO;
2660 GNUNET_assert (existing_finger->trails_count > 0);
2662 /* Iterate over list of trails. */
2663 for (i = 0; i < existing_finger->trails_count; i++)
2665 trail_list_iterator = &existing_finger->trail_list[i];
2666 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2668 /* New trail and existing trail length are not same. */
2669 if (trail_list_iterator->trail_length != trail_length)
2671 trail_unique = GNUNET_YES;
2675 trail_element = trail_list_iterator->trail_head;
2676 for (j = 0; j < trail_list_iterator->trail_length; j++)
2678 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2679 &trail_element->peer))
2681 trail_unique = GNUNET_YES;
2684 trail_element = trail_element->next;
2687 trail_unique = GNUNET_NO;
2690 return trail_unique;
2695 * Add a new trail to existing finger. This function is called only when finger
2696 * is not my own identity or a friend.
2697 * @param existing_finger Finger
2698 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2699 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2700 * @param new_finger_trail_id Unique identifier of the trail.
2703 add_new_trail (struct FingerInfo *existing_finger,
2704 const struct GNUNET_PeerIdentity *new_trail,
2705 unsigned int new_trail_length,
2706 struct GNUNET_HashCode new_trail_id)
2708 struct Trail *trail_list_iterator;
2709 struct FriendInfo *first_friend;
2712 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2718 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2719 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2720 trail_list_iterator->trail_id = new_trail_id;
2721 trail_list_iterator->trail_length = new_trail_length;
2722 existing_finger->trails_count++;
2723 trail_list_iterator->is_present = GNUNET_YES;
2725 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2726 &existing_finger->finger_identity)));
2727 /* If finger is a friend then we never call this function. */
2728 GNUNET_assert (new_trail_length > 0);
2730 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2732 first_friend->trails_count++;
2734 for (i = 0; i < new_trail_length; i++)
2736 struct Trail_Element *element;
2738 element = GNUNET_new (struct Trail_Element);
2739 element->peer = new_trail[i];
2740 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2741 trail_list_iterator->trail_tail,
2744 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2750 * FIXME Check if this function is called for opposite direction if yes then
2751 * take it as parameter.
2752 * Get the next hop to send trail teardown message from routing table and
2753 * then delete the entry from routing table. Send trail teardown message for a
2754 * specific trail of a finger.
2755 * @param finger Finger whose trail is to be removed.
2756 * @param trail List of peers in trail from me to a finger, NOT including
2760 send_trail_teardown (struct FingerInfo *finger,
2761 struct Trail *trail)
2763 struct FriendInfo *friend;
2764 struct GNUNET_PeerIdentity *next_hop;
2766 GNUNET_assert (NULL !=
2767 (next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2768 GDS_ROUTING_SRC_TO_DEST)));
2770 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2773 GNUNET_assert (trail->is_present == GNUNET_YES);
2775 /* Finger is not a friend. */
2776 if (trail->trail_length > 0)
2778 GNUNET_assert (NULL != (friend =
2779 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2780 &trail->trail_head->peer)));
2784 GNUNET_assert (NULL != (friend =
2785 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2786 &finger->finger_identity)));
2789 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2790 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2791 friend->trails_count--;
2792 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2793 GDS_ROUTING_SRC_TO_DEST,
2799 * Send trail teardown message across all the trails to reach to finger.
2800 * @param finger Finger whose all the trail should be freed.
2803 send_all_finger_trails_teardown (struct FingerInfo *finger)
2807 for (i = 0; i < finger->trails_count; i++)
2809 struct Trail *trail;
2811 trail = &finger->trail_list[i];
2812 GNUNET_assert (trail->is_present == GNUNET_YES);
2813 send_trail_teardown (finger, trail);
2814 trail->is_present = GNUNET_NO;
2820 * Free a specific trail
2821 * @param trail List of peers to be freed.
2824 free_trail (struct Trail *trail)
2826 struct Trail_Element *trail_element;
2828 while (NULL != (trail_element = trail->trail_head))
2830 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2833 GNUNET_free_non_null (trail_element);
2835 trail->trail_head = NULL;
2836 trail->trail_tail = NULL;
2841 * Free finger and its trail.
2842 * @param finger Finger to be freed.
2845 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2847 struct Trail *trail;
2850 /* Free all the trails to reach to finger */
2851 for (i = 0; i < finger->trails_count; i++)
2853 trail = &finger->trail_list[i];
2854 //FIXME: Check if there are any missing entry in this list because of
2855 // how we insert. If not then no need of this check.
2856 if (GNUNET_NO == trail->is_present)
2859 if (trail->trail_length > 0)
2863 trail->is_present = GNUNET_NO;
2866 finger->is_present = GNUNET_NO;
2867 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2872 * FIXME: ensure that you are not adding any trail to reach to a friend which
2873 * is a finger. Also decide on should you increment trails count of a friend
2874 * which is also a finger.
2875 * Add a new entry in finger table at finger_table_index.
2876 * In case finger identity is me or a friend, then don't add a trail. NOTE
2877 * trail length to reach to a finger can be 0 only if the finger is a friend
2879 * In case a finger is a friend, then increment the trails count of the friend.
2880 * @param finger_identity Peer Identity of new finger
2881 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2882 * @param finger_trail_length Total number of peers in @a finger_trail.
2883 * @param trail_id Unique identifier of the trail.
2884 * @param finger_table_index Index in finger table.
2887 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2888 const struct GNUNET_PeerIdentity *finger_trail,
2889 unsigned int finger_trail_length,
2890 struct GNUNET_HashCode trail_id,
2891 unsigned int finger_table_index)
2893 struct FingerInfo *new_entry;
2894 struct FriendInfo *first_trail_hop;
2895 struct Trail *trail;
2898 new_entry = GNUNET_new (struct FingerInfo);
2899 new_entry->finger_identity = finger_identity;
2900 new_entry->finger_table_index = finger_table_index;
2901 new_entry->is_present = GNUNET_YES;
2903 /* If the new entry is my own identity. */
2904 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2906 new_entry->trails_count = 0;
2907 finger_table[finger_table_index] = *new_entry;
2908 GNUNET_free (new_entry);
2912 /* If finger is a friend, then we don't actually have a trail.
2913 * Just a trail id */
2914 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2917 new_entry->trail_list[0].trail_id = trail_id;
2918 new_entry->trails_count = 1;
2919 new_entry->trail_list[0].is_present = GNUNET_YES;
2920 new_entry->trail_list[0].trail_length = 0;
2921 new_entry->trail_list[0].trail_head = NULL;
2922 new_entry->trail_list[0].trail_tail = NULL;
2923 finger_table[finger_table_index] = *new_entry;
2924 GNUNET_assert (NULL !=
2926 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2927 &finger_identity)));
2929 first_trail_hop->trails_count++;
2930 GNUNET_free (new_entry);
2934 /* finger trail length can be 0 only in case if finger is my identity or
2935 finger is friend. We should never reach here. */
2936 GNUNET_assert (finger_trail_length > 0);
2938 GNUNET_assert (NULL !=
2940 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2941 &finger_trail[0])));
2942 new_entry->trails_count = 1;
2943 first_trail_hop->trails_count++;
2945 /* Copy the finger trail into trail. */
2946 trail = GNUNET_new (struct Trail);
2947 while (i < finger_trail_length)
2949 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2951 element->next = NULL;
2952 element->prev = NULL;
2953 element->peer = finger_trail[i];
2954 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2960 /* Add trail to trail list. */
2961 new_entry->trail_list[0].trail_head = trail->trail_head;
2962 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2963 new_entry->trail_list[0].trail_length = finger_trail_length;
2964 new_entry->trail_list[0].trail_id = trail_id;
2965 new_entry->trail_list[0].is_present = GNUNET_YES;
2966 finger_table[finger_table_index] = *new_entry;
2967 //GNUNET_free (new_entry);
2968 //GNUNET_free (trail);
2974 * Scan the trail to check if there is any other friend in the trail other than
2975 * first hop. If yes then shortcut the trail, send trail compression message to
2976 * peers which are no longer part of trail and send back the updated trail
2977 * and trail_length to calling function.
2978 * @param finger_identity Finger whose trail we will scan.
2979 * @param finger_trail [in, out] Trail to reach from source to finger,
2980 * @param finger_trail_length Total number of peers in original finger_trail.
2981 * @param finger_trail_id Unique identifier of the finger trail.
2982 * @return updated trail length in case we shortcut the trail, else original
2985 static struct GNUNET_PeerIdentity *
2986 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2987 const struct GNUNET_PeerIdentity *trail,
2988 unsigned int trail_length,
2989 struct GNUNET_HashCode trail_id,
2990 int *new_trail_length)
2992 struct FriendInfo *target_friend;
2993 struct GNUNET_PeerIdentity *new_trail;
2996 /* I am my own finger. */
2997 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2999 *new_trail_length = 0;
3003 if (0 == trail_length)
3005 *new_trail_length = 0;
3009 /* If finger identity is a friend. */
3010 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3012 *new_trail_length = 0;
3014 /* If there is trail to reach this finger/friend */
3015 if (trail_length > 0)
3017 /* Finger is your first friend. */
3018 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3019 GNUNET_assert (NULL !=
3021 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3025 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3026 trail_id, finger_identity,
3032 /* For other cases, when its neither a friend nor my own identity.*/
3033 for (i = trail_length - 1; i > 0; i--)
3035 /* If the element at this index in trail is a friend. */
3036 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3038 struct FriendInfo *target_friend;
3041 GNUNET_assert (NULL !=
3043 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3045 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3046 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3051 /* Copy the trail from index i to index (trail_length -1) into a new trail
3052 * and update new trail length */
3053 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3054 while (i < trail_length)
3056 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3060 *new_trail_length = j+1;
3061 GNUNET_assert((j+1) == (trail_length - 1)); //FIXME: remove it afterwards.
3066 /* If we did not compress the trail, return the original trail back.*/
3067 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3068 *new_trail_length = trail_length;
3069 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3075 * Periodic task to verify current successor. There can be multiple trails to reach
3076 * to successor, choose the shortest one and send verify successor message
3077 * across that trail.
3078 * @param cls closure for this task
3079 * @param tc the context under which the task is running
3082 send_verify_successor_message (void *cls,
3083 const struct GNUNET_SCHEDULER_TaskContext *tc)
3085 struct FriendInfo *target_friend;
3086 struct GNUNET_HashCode trail_id;
3088 struct GNUNET_TIME_Relative next_send_time;
3089 struct Trail *trail;
3090 struct Trail_Element *element;
3091 unsigned int trail_length;
3093 struct FingerInfo *successor;
3095 /* Schedule another send_find_finger_trail_message task. */
3096 next_send_time.rel_value_us =
3097 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3098 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3099 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3100 send_verify_successor_task =
3101 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3104 successor = &finger_table[0];
3106 trail = &successor->trail_list[i];
3108 /* Store the successor for path tracking */
3109 if (track_topology && (NULL != GDS_stats))
3115 my_id_str = GNUNET_strdup (GNUNET_i2s (&my_identity));
3116 succ_id_str = GNUNET_strdup (GNUNET_i2s
3117 (&successor->finger_identity));
3118 GNUNET_asprintf (&key, "XDHT:0:%.4s:%.4s", my_id_str, succ_id_str);
3119 GNUNET_free (my_id_str);
3120 GNUNET_free (succ_id_str);
3121 GNUNET_STATISTICS_update (GDS_stats, "key", 1, 0);
3125 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3126 &successor->finger_identity));
3128 /* Trail stored at this index. */
3129 GNUNET_assert (GNUNET_YES == trail->is_present);
3131 trail_id = trail->trail_id;
3132 trail_length = trail->trail_length;
3134 if (trail_length > 0)
3136 /* Copy the trail into peer list. */
3137 struct GNUNET_PeerIdentity peer_list[trail_length];
3139 element = trail->trail_head;
3140 while (j < trail_length)
3142 peer_list[j] = element->peer;
3143 element = element->next;
3147 GNUNET_assert (NULL != (target_friend =
3148 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3150 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3151 successor->finger_identity,
3152 trail_id, peer_list, trail_length,
3158 GNUNET_assert (NULL != (target_friend =
3159 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3160 &successor->finger_identity)));
3161 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3162 successor->finger_identity,
3171 * Update the current search finger index.
3174 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3175 unsigned int finger_table_index)
3177 struct FingerInfo *successor;
3179 if (finger_table_index != current_search_finger_index)
3182 successor = &finger_table[0];
3183 GNUNET_assert (GNUNET_YES == successor->is_present);
3185 /* We were looking for immediate successor. */
3186 if (0 == current_search_finger_index)
3188 /* Start looking for immediate predecessor. */
3189 current_search_finger_index = PREDECESSOR_FINGER_ID;
3191 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3193 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3194 send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3200 current_search_finger_index = current_search_finger_index - 1;
3206 * Get the first set bit in val.
3208 * @return Position of first bit set.
3211 find_set_bit(uint64_t val)
3228 * Calculate finger_table_index from initial 64 bit finger identity value that
3229 * we send in trail setup message.
3230 * @param ultimate_destination_finger_value Value that we calculated from our
3231 * identity and finger_table_index.
3232 * @param is_predecessor Is the entry for predecessor or not?
3233 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3234 * finger_table_index > PREDECESSOR_FINGER_ID ,
3235 * if no valid finger_table_index is found.
3238 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3239 unsigned int is_predecessor)
3243 unsigned int finger_table_index;
3245 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3246 my_id64 = GNUNET_ntohll (my_id64);
3248 /* Is this a predecessor finger? */
3249 if (1 == is_predecessor)
3251 diff = my_id64 - ultimate_destination_finger_value;
3253 finger_table_index = PREDECESSOR_FINGER_ID;
3255 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3260 diff = ultimate_destination_finger_value - my_id64;
3261 finger_table_index = find_set_bit(diff);
3264 return finger_table_index;
3269 * Remove finger and its associated data structures from finger table.
3270 * @param finger Finger to be removed.
3273 remove_existing_finger (struct FingerInfo *existing_finger,
3274 unsigned int finger_table_index)
3276 struct FingerInfo *finger;
3278 finger = &finger_table[finger_table_index];
3279 GNUNET_assert (GNUNET_YES == finger->is_present);
3281 /* If I am my own finger, then we have no trails. */
3282 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3285 finger->is_present = GNUNET_NO;
3286 memset ((void *)&finger_table[finger_table_index], 0,
3287 sizeof (finger_table[finger_table_index]));
3291 /* For all other fingers, send trail teardown across all the trails to reach
3292 finger, and free the finger. */
3293 send_all_finger_trails_teardown (finger);
3294 free_finger (finger, finger_table_index);
3300 * Check if there is already an entry in finger_table at finger_table_index.
3301 * We get the finger_table_index from 64bit finger value we got from the network.
3302 * -- If yes, then select the closest finger.
3303 * -- If new and existing finger are same, then check if you can store more
3305 * -- If yes then add trail, else keep the best trails to reach to the
3307 * -- If the new finger is closest, remove the existing entry, send trail
3308 * teardown message across all the trails to reach the existing entry.
3309 * Add the new finger.
3310 * -- If new and existing finger are different, and existing finger is closest
3312 * -- Update current_search_finger_index.
3313 * @param finger_identity Peer Identity of new finger
3314 * @param finger_trail Trail to reach the new finger
3315 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3316 * @param is_predecessor Is this entry for predecessor in finger_table?
3317 * @param finger_value 64 bit value of finger identity that we got from network.
3318 * @param finger_trail_id Unique identifier of @finger_trail.
3321 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3322 const struct GNUNET_PeerIdentity *finger_trail,
3323 unsigned int finger_trail_length,
3324 unsigned int is_predecessor,
3325 uint64_t finger_value,
3326 struct GNUNET_HashCode finger_trail_id)
3328 struct FingerInfo *existing_finger;
3329 struct GNUNET_PeerIdentity *closest_peer;
3330 struct FingerInfo *successor;
3331 int updated_finger_trail_length;
3332 unsigned int finger_table_index;
3334 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3335 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3337 /* Invalid finger_table_index. */
3338 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3340 GNUNET_break_op (0);
3344 /* New entry same as successor. */
3345 if ((0 != finger_table_index) &&
3346 (PREDECESSOR_FINGER_ID != finger_table_index))
3348 successor = &finger_table[0];
3349 GNUNET_assert (GNUNET_YES == successor->is_present);
3350 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3351 &successor->finger_identity))
3353 current_search_finger_index = 0;
3358 existing_finger = &finger_table[finger_table_index];
3360 /* No entry present in finger_table for given finger map index. */
3361 if (GNUNET_NO == existing_finger->is_present)
3363 struct GNUNET_PeerIdentity *updated_trail;
3365 /* Shorten the trail if possible. */
3366 updated_finger_trail_length = finger_trail_length;
3368 scan_and_compress_trail (finger_identity, finger_trail,
3369 finger_trail_length, finger_trail_id,
3370 &updated_finger_trail_length);
3372 add_new_finger (finger_identity, updated_trail,
3373 updated_finger_trail_length,
3374 finger_trail_id, finger_table_index);
3375 update_current_search_finger_index (finger_identity,
3376 finger_table_index);
3381 /* If existing entry and finger identity are not same. */
3382 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3385 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3390 /* If the new finger is the closest peer. */
3391 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3393 struct GNUNET_PeerIdentity *updated_trail;
3394 /* Shorten the trail if possible. */
3395 updated_finger_trail_length = finger_trail_length;
3397 scan_and_compress_trail (finger_identity, finger_trail,
3398 finger_trail_length, finger_trail_id,
3399 &updated_finger_trail_length);
3400 remove_existing_finger (existing_finger, finger_table_index);
3401 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3402 finger_trail_id, finger_table_index);
3407 /* Existing finger is the closest one. We need to send trail teardown
3408 across the trail setup in routing table of all the peers. */
3409 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3411 if (finger_trail_length > 0)
3412 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3413 GDS_ROUTING_SRC_TO_DEST,
3416 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3417 GDS_ROUTING_SRC_TO_DEST,
3424 /* If both new and existing entry are same as my_identity, then do nothing. */
3425 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3430 /* If the existing finger is not a friend. */
3432 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3433 &existing_finger->finger_identity))
3435 struct GNUNET_PeerIdentity *updated_trail;
3437 /* Shorten the trail if possible. */
3438 updated_finger_trail_length = finger_trail_length;
3440 scan_and_compress_trail (finger_identity, finger_trail,
3441 finger_trail_length, finger_trail_id,
3442 &updated_finger_trail_length);
3443 /* If there is space to store more trails. */
3444 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3445 add_new_trail (existing_finger, updated_trail,
3446 updated_finger_trail_length, finger_trail_id);
3448 select_and_replace_trail (existing_finger, updated_trail,
3449 updated_finger_trail_length, finger_trail_id);
3453 update_current_search_finger_index (finger_identity, finger_table_index);
3458 * Core handler for P2P put messages.
3459 * @param cls closure
3460 * @param peer sender of the request
3461 * @param message message
3462 * @return #GNUNET_OK to keep the connection open,
3463 * #GNUNET_SYSERR to close it (signal serious error)
3466 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3467 const struct GNUNET_MessageHeader *message)
3469 struct PeerPutMessage *put;
3470 struct GNUNET_PeerIdentity *put_path;
3471 struct GNUNET_PeerIdentity best_known_dest;
3472 struct GNUNET_HashCode intermediate_trail_id;
3473 struct GNUNET_PeerIdentity *next_hop;
3474 enum GNUNET_DHT_RouteOption options;
3475 struct GNUNET_HashCode test_key;
3479 size_t payload_size;
3482 msize = ntohs (message->size);
3483 if (msize < sizeof (struct PeerPutMessage))
3485 GNUNET_break_op (0);
3489 put = (struct PeerPutMessage *) message;
3490 putlen = ntohl (put->put_path_length);
3494 sizeof (struct PeerPutMessage) +
3495 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3497 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3499 GNUNET_break_op (0);
3503 best_known_dest = put->best_known_destination;
3504 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3505 payload = &put_path[putlen];
3506 options = ntohl (put->options);
3507 intermediate_trail_id = put->intermediate_trail_id;
3509 payload_size = msize - (sizeof (struct PeerPutMessage) +
3510 putlen * sizeof (struct GNUNET_PeerIdentity));
3512 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3513 payload, payload_size, &test_key))
3516 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3518 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3519 GNUNET_break_op (0);
3520 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3521 "PUT with key `%s' for block with key %s\n",
3522 put_s, GNUNET_h2s_full (&test_key));
3523 GNUNET_free (put_s);
3528 GNUNET_break_op (0);
3531 /* cannot verify, good luck */
3535 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3537 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3538 ntohl (put->block_type),
3540 NULL, 0, /* bloom filer */
3541 NULL, 0, /* xquery */
3542 payload, payload_size))
3544 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3545 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3548 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3549 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3550 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3551 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3552 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3553 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3555 GNUNET_break_op (0);
3560 /* extend 'put path' by sender */
3561 struct GNUNET_PeerIdentity pp[putlen + 1];
3562 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3564 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3571 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3572 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3574 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3575 GDS_ROUTING_SRC_TO_DEST);
3576 if (NULL == next_hop)
3578 GNUNET_STATISTICS_update (GDS_stats,
3579 gettext_noop ("# Next hop to forward the packet not found "
3580 "trail setup request, packet dropped."),
3582 return GNUNET_SYSERR;
3587 struct Closest_Peer successor;
3588 key_value = GNUNET_ntohll (key_value);
3589 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3591 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3592 *next_hop = successor.next_hop;
3593 intermediate_trail_id = successor.trail_id;
3594 best_known_dest = successor.best_known_destination;
3597 GDS_CLIENTS_process_put (options,
3598 ntohl (put->block_type),
3599 ntohl (put->hop_count),
3600 ntohl (put->desired_replication_level),
3602 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3607 /* I am the final destination */
3608 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3610 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3611 &(put->key),putlen, pp, ntohl (put->block_type),
3612 payload_size, payload);
3616 GDS_NEIGHBOURS_send_put (&put->key,
3617 ntohl (put->block_type),ntohl (put->options),
3618 ntohl (put->desired_replication_level),
3619 best_known_dest, intermediate_trail_id, next_hop,
3620 ntohl (put->hop_count), putlen, pp,
3621 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3622 payload, payload_size);
3629 * Core handler for p2p get requests.
3631 * @param cls closure
3632 * @param peer sender of the request
3633 * @param message message
3634 * @return #GNUNET_OK to keep the connection open,
3635 * #GNUNET_SYSERR to close it (signal serious error)
3638 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3639 const struct GNUNET_MessageHeader *message)
3641 const struct PeerGetMessage *get;
3642 const struct GNUNET_PeerIdentity *get_path;
3643 struct GNUNET_PeerIdentity best_known_dest;
3644 struct GNUNET_HashCode intermediate_trail_id;
3645 struct GNUNET_PeerIdentity *next_hop;
3646 uint32_t get_length;
3650 msize = ntohs (message->size);
3651 if (msize < sizeof (struct PeerGetMessage))
3653 GNUNET_break_op (0);
3657 get = (const struct PeerGetMessage *)message;
3658 get_length = ntohl (get->get_path_length);
3659 best_known_dest = get->best_known_destination;
3660 intermediate_trail_id = get->intermediate_trail_id;
3661 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3664 sizeof (struct PeerGetMessage) +
3665 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3667 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3669 GNUNET_break_op (0);
3673 /* Add sender to get path */
3674 struct GNUNET_PeerIdentity gp[get_length + 1];
3676 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3677 gp[get_length] = *peer;
3678 get_length = get_length + 1;
3680 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3681 key_value = GNUNET_ntohll (key_value);
3683 /* I am not the final destination. I am part of trail to reach final dest. */
3684 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3686 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3687 GDS_ROUTING_SRC_TO_DEST);
3688 if (NULL == next_hop)
3690 GNUNET_STATISTICS_update (GDS_stats,
3691 gettext_noop ("# Next hop to forward the packet not found "
3692 "GET request, packet dropped."),
3694 return GNUNET_SYSERR;
3699 struct Closest_Peer successor;
3701 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3702 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3703 *next_hop = successor.next_hop;
3704 best_known_dest = successor.best_known_destination;
3705 intermediate_trail_id = successor.trail_id;
3708 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3709 get->desired_replication_level, get->get_path_length,
3711 /* I am the final destination. */
3712 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3714 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3716 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3717 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3718 get_length = get_length + 1;
3720 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3721 get_length, final_get_path,
3722 &final_get_path[get_length-2], &my_identity);
3726 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3727 get->desired_replication_level, best_known_dest,
3728 intermediate_trail_id, next_hop, 0,
3736 * Core handler for get result
3737 * @param cls closure
3738 * @param peer sender of the request
3739 * @param message message
3740 * @return #GNUNET_OK to keep the connection open,
3741 * #GNUNET_SYSERR to close it (signal serious error)
3744 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3745 const struct GNUNET_MessageHeader *message)
3747 const struct PeerGetResultMessage *get_result;
3748 const struct GNUNET_PeerIdentity *get_path;
3749 const struct GNUNET_PeerIdentity *put_path;
3750 const void *payload;
3751 size_t payload_size;
3753 unsigned int getlen;
3754 unsigned int putlen;
3755 int current_path_index;
3757 msize = ntohs (message->size);
3758 if (msize < sizeof (struct PeerGetResultMessage))
3760 GNUNET_break_op (0);
3764 get_result = (const struct PeerGetResultMessage *)message;
3765 getlen = ntohl (get_result->get_path_length);
3766 putlen = ntohl (get_result->put_path_length);
3769 sizeof (struct PeerGetResultMessage) +
3770 getlen * sizeof (struct GNUNET_PeerIdentity) +
3771 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3773 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3775 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3777 GNUNET_break_op (0);
3781 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3782 get_path = &put_path[putlen];
3783 payload = (const void *) &get_path[getlen];
3784 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3785 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3787 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3789 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3790 getlen, get_path, putlen,
3791 put_path, get_result->type, payload_size, payload);
3796 current_path_index = search_my_index (get_path, getlen);
3797 if (-1 == current_path_index )
3800 return GNUNET_SYSERR;
3802 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3803 &get_path[current_path_index - 1],
3804 &(get_result->querying_peer), putlen, put_path,
3805 getlen, get_path, get_result->expiration_time,
3806 payload, payload_size);
3809 return GNUNET_SYSERR;
3814 * Find the next hop to pass trail setup message. First find the local best known
3815 * hop from your own identity, friends and finger. If you were part of trail,
3816 * then get the next hop from routing table. Compare next_hop from routing table
3817 * and local best known hop, and return the closest one to final_dest_finger_val
3818 * @param final_dest_finger_val 64 bit value of finger identity
3819 * @param intermediate_trail_id If you are part of trail to reach to some other
3820 * finger, then it is the trail id to reach to
3821 * that finger, else set to 0.
3822 * @param is_predecessor Are we looking for closest successor or predecessor.
3823 * @param current_dest In case you are part of trail, then finger to which
3824 * we should forward the message. Else my own identity
3825 * @return Closest Peer for @a final_dest_finger_val
3827 static struct Closest_Peer
3828 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3829 struct GNUNET_HashCode intermediate_trail_id,
3830 unsigned int is_predecessor,
3831 struct GNUNET_PeerIdentity prev_hop,
3832 struct GNUNET_PeerIdentity source,
3833 struct GNUNET_PeerIdentity *current_dest)
3835 struct Closest_Peer peer;
3837 /* Find a local best known peer. */
3838 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3840 /* Am I just a part of a trail towards a finger (current_destination)? */
3841 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest)))
3843 /* Select best successor among one found locally and current_destination
3844 * that we got from network.*/
3845 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3848 struct GNUNET_PeerIdentity *closest_peer;
3849 struct GNUNET_PeerIdentity *local_best_known_dest;
3850 local_best_known_dest = GNUNET_new(struct GNUNET_PeerIdentity);
3851 memcpy(local_best_known_dest, &peer.best_known_destination, sizeof(struct GNUNET_PeerIdentity));
3853 closest_peer = select_closest_peer (local_best_known_dest,
3855 final_dest_finger_val,
3858 GNUNET_free(local_best_known_dest);
3859 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3860 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3862 struct GNUNET_PeerIdentity *next_hop;
3863 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3864 GDS_ROUTING_SRC_TO_DEST);
3865 GNUNET_assert (NULL != next_hop);
3867 peer.next_hop = *next_hop;
3868 peer.best_known_destination = *current_dest;
3869 peer.trail_id = intermediate_trail_id;
3878 * Core handle for PeerTrailSetupMessage.
3879 * @param cls closure
3880 * @param message message
3881 * @param peer peer identity this notification is about
3882 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3885 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3886 const struct GNUNET_MessageHeader *message)
3888 const struct PeerTrailSetupMessage *trail_setup;
3889 const struct GNUNET_PeerIdentity *trail_peer_list;
3890 struct GNUNET_PeerIdentity current_dest;
3891 struct FriendInfo *target_friend;
3892 struct GNUNET_PeerIdentity source;
3893 uint64_t final_dest_finger_val;
3894 struct GNUNET_HashCode intermediate_trail_id;
3895 struct GNUNET_HashCode trail_id;
3896 unsigned int is_predecessor;
3897 uint32_t trail_length;
3900 msize = ntohs (message->size);
3901 if (msize < sizeof (struct PeerTrailSetupMessage))
3903 GNUNET_break_op (0);
3904 return GNUNET_SYSERR;
3907 trail_setup = (const struct PeerTrailSetupMessage *) message;
3908 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3909 sizeof (struct GNUNET_PeerIdentity);
3910 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3911 sizeof (struct GNUNET_PeerIdentity) != 0)
3913 GNUNET_break_op (0);
3917 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3918 current_dest = trail_setup->best_known_destination;
3919 trail_id = trail_setup->trail_id;
3920 final_dest_finger_val =
3921 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3922 source = trail_setup->source_peer;
3923 is_predecessor = ntohl (trail_setup->is_predecessor);
3924 intermediate_trail_id = trail_setup->intermediate_trail_id;
3926 /* If I was the source and got the message back, then set trail length to 0.*/
3927 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3932 /* Is my routing table full? */
3933 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3935 GNUNET_assert (NULL !=
3937 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
3938 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
3939 my_identity, is_predecessor,
3940 trail_peer_list, trail_length,
3941 trail_id, target_friend,
3942 CONGESTION_TIMEOUT);
3946 /* Get the next hop to forward the trail setup request. */
3947 struct Closest_Peer next_peer =
3948 get_local_best_known_next_hop (final_dest_finger_val,
3949 intermediate_trail_id,
3955 /* Am I the final destination? */
3956 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
3960 /* If I was not the source of this message for which now I am destination */
3961 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
3963 GDS_ROUTING_add (trail_id, *peer, my_identity);
3966 if(trail_length > 0)
3968 GNUNET_assert (NULL !=
3970 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3971 &trail_peer_list[trail_length-1])));
3975 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
3977 finger_table_add (my_identity, NULL, 0, is_predecessor,
3978 final_dest_finger_val, trail_id);
3981 GNUNET_assert (NULL !=
3983 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source)));
3986 GDS_NEIGHBOURS_send_trail_setup_result (source,
3988 target_friend, trail_length,
3991 final_dest_finger_val,trail_id);
3995 GNUNET_assert (NULL !=
3997 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3998 &next_peer.next_hop)));
4000 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4002 /* Add yourself to list of peers. */
4003 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4005 memcpy (peer_list, trail_peer_list,
4006 trail_length * sizeof (struct GNUNET_PeerIdentity));
4007 peer_list[trail_length] = my_identity;
4009 GDS_NEIGHBOURS_send_trail_setup (source,
4010 final_dest_finger_val,
4011 next_peer.best_known_destination,
4012 target_friend, trail_length + 1, peer_list,
4013 is_predecessor, trail_id,
4014 next_peer.trail_id);
4017 GDS_NEIGHBOURS_send_trail_setup (source,
4018 final_dest_finger_val,
4019 next_peer.best_known_destination,
4020 target_friend, 0, NULL,
4021 is_predecessor, trail_id,
4022 next_peer.trail_id);
4028 /* FIXME: here we are calculating my_index and comparing also in this function.
4029 And we are doing it again here in this function. Re factor the code. */
4031 * FIXME: Should we call this function everywhere in all the handle functions
4032 * where we have a trail to verify from or a trail id. something like
4033 * if prev hop is not same then drop the message.
4034 * Check if sender_peer and peer from which we should receive the message are
4035 * same or different.
4036 * @param trail_peer_list List of peers in trail
4037 * @param trail_length Total number of peers in @a trail_peer_list
4038 * @param sender_peer Peer from which we got the message.
4039 * @param finger_identity Finger to which trail is setup. It is not part of trail.
4040 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
4041 * message are different.
4042 * #GNUNET_NO if sender_peer and peer from which we should receive the
4043 * message are different.
4046 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
4047 unsigned int trail_length,
4048 const struct GNUNET_PeerIdentity *sender_peer,
4049 struct GNUNET_PeerIdentity finger_identity,
4050 struct GNUNET_PeerIdentity source_peer)
4054 /* I am the source peer. */
4055 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4058 /* Is the first element of the trail is sender_peer.*/
4059 if (trail_length > 0)
4061 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4067 /* Is finger the sender peer? */
4068 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4075 /* Get my current location in the trail. */
4076 my_index = search_my_index (trail_peer_list, trail_length);
4080 /* I am the last element in the trail. */
4081 if ((trail_length - 1) == my_index)
4083 /* Is finger the sender_peer? */
4084 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4090 /* Is peer after me in trail the sender peer? */
4091 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4092 &trail_peer_list[my_index + 1]))
4102 * FIXME: we should also add a case where we search if we are present in the trail
4104 * Core handle for p2p trail setup result messages.
4106 * @param message message
4107 * @param peer sender of this message.
4108 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4111 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4112 const struct GNUNET_MessageHeader *message)
4114 const struct PeerTrailSetupResultMessage *trail_result;
4115 const struct GNUNET_PeerIdentity *trail_peer_list;
4116 struct GNUNET_PeerIdentity next_hop;
4117 struct FriendInfo *target_friend;
4118 struct GNUNET_PeerIdentity querying_peer;
4119 struct GNUNET_PeerIdentity finger_identity;
4120 uint32_t trail_length;
4121 uint64_t ulitmate_destination_finger_value;
4122 uint32_t is_predecessor;
4123 struct GNUNET_HashCode trail_id;
4127 msize = ntohs (message->size);
4128 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4130 GNUNET_break_op (0);
4134 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4135 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4136 sizeof (struct GNUNET_PeerIdentity);
4137 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4138 sizeof (struct GNUNET_PeerIdentity) != 0)
4140 GNUNET_break_op (0);
4144 is_predecessor = ntohl (trail_result->is_predecessor);
4145 querying_peer = trail_result->querying_peer;
4146 finger_identity = trail_result->finger_identity;
4147 trail_id = trail_result->trail_id;
4148 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4149 ulitmate_destination_finger_value =
4150 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4152 /* FIXME: here we are calculating my_index and comparing also in this function.
4153 And we are doing it again here in this function. Re factor the code. */
4154 /* Ensure that sender peer is the peer from which we were expecting the message. */
4156 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
4158 peer, finger_identity, querying_peer))
4160 GNUNET_break_op (0);
4161 return GNUNET_SYSERR;
4165 /* Am I the one who initiated the query? */
4166 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4168 /* If I am not my own finger identity, then add routing table entry. */
4169 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4171 GDS_ROUTING_add (trail_id, my_identity, *peer);
4174 finger_table_add (finger_identity, trail_peer_list, trail_length,
4175 is_predecessor, ulitmate_destination_finger_value, trail_id);
4179 /* Get my location in the trail. */
4180 my_index = search_my_index (trail_peer_list, trail_length);
4184 return GNUNET_SYSERR;
4188 next_hop = trail_result->querying_peer;
4190 next_hop = trail_peer_list[my_index - 1];
4192 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4193 &(trail_result->finger_identity))))
4195 GDS_ROUTING_add (trail_id, next_hop, *peer);
4198 GNUNET_assert (NULL !=
4200 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4201 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4202 target_friend, trail_length, trail_peer_list,
4204 ulitmate_destination_finger_value,
4212 * @param trail Trail to be inverted
4213 * @param trail_length Total number of peers in the trail.
4214 * @return Updated trail
4216 static struct GNUNET_PeerIdentity *
4217 invert_trail (const struct GNUNET_PeerIdentity *trail,
4218 unsigned int trail_length)
4222 struct GNUNET_PeerIdentity *inverted_trail;
4224 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4227 j = trail_length - 1;
4228 while (i < trail_length)
4230 inverted_trail[i] = trail[j];
4235 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4236 &inverted_trail[0]));
4237 return inverted_trail;
4242 * Return the shortest trail among all the trails to reach to finger from me.
4243 * @param finger Finger
4244 * @param shortest_trail_length[out] Trail length of shortest trail from me
4246 * @return Shortest trail.
4248 static struct GNUNET_PeerIdentity *
4249 get_shortest_trail (struct FingerInfo *finger,
4250 unsigned int *trail_length)
4252 struct Trail *trail;
4253 unsigned int flag = 0;
4254 unsigned int shortest_trail_index = 0;
4255 int shortest_trail_length = -1;
4256 struct Trail_Element *trail_element;
4257 struct GNUNET_PeerIdentity *trail_list;
4260 trail = GNUNET_new (struct Trail);
4262 /* Get the shortest trail to reach to current successor. */
4263 for (i = 0; i < finger->trails_count; i++)
4265 trail = &finger->trail_list[i];
4269 shortest_trail_index = i;
4270 shortest_trail_length = trail->trail_length;
4275 if (shortest_trail_length > trail->trail_length)
4277 shortest_trail_index = i;
4278 shortest_trail_length = trail->trail_length;
4283 /* Copy the shortest trail and return. */
4284 trail = &finger->trail_list[shortest_trail_index];
4285 trail_element = trail->trail_head;
4286 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4287 shortest_trail_length);
4289 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4291 trail_list[i] = trail_element->peer;
4294 GNUNET_assert(shortest_trail_length != -1);
4296 *trail_length = shortest_trail_length;
4302 * Return the trail from source to my current predecessor. Check if source
4303 * is already part of the this trail, if yes then return the shorten trail.
4304 * @param current_trail Trail from source to me, NOT including the endpoints.
4305 * @param current_trail_length Number of peers in @a current_trail.
4306 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4307 * source to my predecessor, NOT including
4309 * @return Trail from source to my predecessor.
4311 static struct GNUNET_PeerIdentity *
4312 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4313 const struct GNUNET_PeerIdentity *trail_src_to_me,
4314 unsigned int trail_src_to_me_len,
4315 unsigned int *trail_src_to_curr_pred_length)
4317 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4318 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4319 unsigned int trail_me_to_curr_pred_length;
4320 struct FingerInfo *current_predecessor;
4324 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4325 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4326 &trail_me_to_curr_pred_length);
4328 /* Check if trail_me_to_curr_pred contains source. */
4329 if (trail_me_to_curr_pred_length > 0)
4331 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4333 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4334 &trail_me_to_curr_pred[i]))
4339 /* Source is the last element in the trail to reach to my pred.
4340 Source is direct friend of the pred. */
4341 if (trail_me_to_curr_pred_length == i)
4343 *trail_src_to_curr_pred_length = 0;
4347 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4348 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4349 *trail_src_to_curr_pred_length);
4350 for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4352 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4355 return trail_src_to_curr_pred;
4359 /* Append trail from source to me to my current_predecessor. */
4360 *trail_src_to_curr_pred_length = trail_src_to_me_len +
4361 trail_me_to_curr_pred_length + 1;
4363 trail_src_to_curr_pred = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4364 *trail_src_to_curr_pred_length);
4366 for (i = 0; i < trail_src_to_me_len; i++)
4367 trail_src_to_curr_pred[i] = trail_src_to_me[i];
4369 trail_src_to_curr_pred[i] = my_identity;
4372 for (j = 0; i < *trail_src_to_curr_pred_length; i++,j++)
4373 trail_src_to_curr_pred[i] = trail_me_to_curr_pred[j];
4375 return trail_src_to_curr_pred;
4380 * Add finger as your predecessor. To add, first generate a new trail id, invert
4381 * the trail to get the trail from me to finger, add an entry in your routing
4382 * table, send add trail message to peers which are part of trail from me to
4383 * finger and add finger in finger table.
4386 * @param trail_length
4389 update_predecessor (struct GNUNET_PeerIdentity finger,
4390 struct GNUNET_PeerIdentity *trail,
4391 unsigned int trail_length)
4393 struct GNUNET_HashCode trail_to_new_predecessor_id;
4394 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4395 struct FriendInfo *target_friend;
4397 /* Generate trail id for trail from me to new predecessor = finger. */
4398 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4399 &trail_to_new_predecessor_id,
4400 sizeof (trail_to_new_predecessor_id));
4402 /* Finger is a friend. */
4403 if (trail_length == 0)
4405 trail_to_new_predecessor = NULL;
4406 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4407 GNUNET_assert (NULL != (target_friend =
4408 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4413 /* Invert the trail to get the trail from me to finger, NOT including the
4415 trail_to_new_predecessor = invert_trail (trail, trail_length);
4417 /* Add an entry in your routing table. */
4418 GDS_ROUTING_add (trail_to_new_predecessor_id,
4420 trail_to_new_predecessor[0]);
4422 GNUNET_assert (NULL != (target_friend =
4423 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4424 &trail_to_new_predecessor[0])));
4425 GNUNET_assert (NULL != (
4426 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4427 &trail[trail_length - 1])));
4430 /* Add entry in routing table of all peers that are part of trail from me
4431 to finger, including finger. */
4432 GDS_NEIGHBOURS_send_add_trail (my_identity,
4434 trail_to_new_predecessor_id,
4435 trail_to_new_predecessor,
4439 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4440 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4441 GNUNET_free_non_null (trail_to_new_predecessor);
4446 * Check if you already have a predecessor. If not then add finger as your
4447 * predecessor. If you have predecessor, then compare two peer identites.
4448 * If finger is correct predecessor, then remove the old entry, add finger in
4449 * finger table and send add_trail message to add the trail in the routing
4450 * table of all peers which are part of trail to reach from me to finger.
4451 * @param finger New peer which may be our predecessor.
4452 * @param trail List of peers to reach from @finger to me.
4453 * @param trail_length Total number of peer in @a trail.
4456 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4457 struct GNUNET_PeerIdentity *trail,
4458 unsigned int trail_length)
4460 struct FingerInfo *current_predecessor;
4461 struct GNUNET_PeerIdentity *closest_peer;
4462 uint64_t predecessor_value;
4463 unsigned int is_predecessor = 1;
4465 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4467 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4469 /* No predecessor. Add finger as your predecessor. */
4470 if (GNUNET_NO == current_predecessor->is_present)
4472 update_predecessor (finger, trail, trail_length);
4475 /* FIXME: Here we should first call find_successor and get a locally known
4476 predecessor. If locally known predecessor is closest then current or finger,
4477 add that as predecessor. */
4478 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4484 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4485 closest_peer = select_closest_peer (&finger,
4486 ¤t_predecessor->finger_identity,
4487 predecessor_value, is_predecessor);
4489 /* Finger is the closest predecessor. Remove the existing one and add the new
4491 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, &finger))
4493 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4494 update_predecessor (finger, trail, trail_length);
4502 * Core handle for p2p verify successor messages.
4503 * @param cls closure
4504 * @param message message
4505 * @param peer peer identity this notification is about
4506 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4509 handle_dht_p2p_verify_successor(void *cls,
4510 const struct GNUNET_PeerIdentity *peer,
4511 const struct GNUNET_MessageHeader *message)
4513 const struct PeerVerifySuccessorMessage *vsm;
4514 struct GNUNET_HashCode trail_id;
4515 struct GNUNET_PeerIdentity successor;
4516 struct GNUNET_PeerIdentity source_peer;
4517 struct GNUNET_PeerIdentity *trail;
4518 struct GNUNET_PeerIdentity *next_hop;
4519 struct FingerInfo *current_predecessor;
4520 struct FriendInfo *target_friend;
4521 unsigned int trail_src_to_curr_pred_len = 0;
4522 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4524 unsigned int trail_length;
4526 msize = ntohs (message->size);
4528 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4530 GNUNET_break_op (0);
4534 vsm = (const struct PeerVerifySuccessorMessage *) message;
4535 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4536 sizeof (struct GNUNET_PeerIdentity);
4537 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4538 sizeof (struct GNUNET_PeerIdentity) != 0)
4540 GNUNET_break_op (0);
4544 trail_id = vsm->trail_id;
4545 source_peer = vsm->source_peer;
4546 successor = vsm->successor;
4547 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4550 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4552 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4554 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4555 if (NULL == next_hop)
4558 return GNUNET_SYSERR;
4560 GNUNET_assert (NULL !=
4562 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4564 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4565 trail_id, trail, trail_length,
4570 /* I am the destination of this message. */
4572 /* Check if the source_peer could be our predecessor and if yes then update
4574 compare_and_update_predecessor (source_peer, trail, trail_length);
4575 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4577 /* Is source of this message NOT my predecessor. */
4578 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4581 trail_src_to_curr_pred = get_trail_src_to_curr_pred (source_peer,
4584 &trail_src_to_curr_pred_len);
4588 trail_src_to_curr_pred_len = trail_length;
4590 trail_src_to_curr_pred = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)*trail_length);
4591 for(i = 0; i < trail_src_to_curr_pred_len; i++)
4593 trail_src_to_curr_pred[i] = trail[i];
4598 GNUNET_assert (NULL !=
4600 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4601 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4602 current_predecessor->finger_identity,
4603 trail_id, trail_src_to_curr_pred,
4604 trail_src_to_curr_pred_len,
4605 GDS_ROUTING_DEST_TO_SRC,
4613 * If the trail from me to my probable successor contains a friend not
4614 * at index 0, then we can shorten the trail.
4615 * @param probable_successor Peer which is our probable successor
4616 * @param trail_me_to_probable_successor Peers in path from me to my probable
4617 * successor, NOT including the endpoints.
4618 * @param trail_me_to_probable_successor_len Total number of peers in
4619 * @a trail_me_to_probable_succesor.
4620 * @return Updated trail, if any friend found.
4621 * Else the trail_me_to_probable_successor.
4623 struct GNUNET_PeerIdentity *
4624 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4625 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4626 unsigned int trail_me_to_probable_successor_len,
4627 unsigned int *trail_to_new_successor_length)
4631 struct GNUNET_PeerIdentity *trail_to_new_successor;
4633 /* Probable successor is a friend */
4634 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4635 &probable_successor))
4637 trail_to_new_successor = NULL;
4638 *trail_to_new_successor_length = 0;
4639 return trail_to_new_successor;
4642 /* Is there any friend of yours in this trail. */
4643 if(trail_me_to_probable_successor_len > 1)
4645 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4647 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4648 &trail_me_to_probable_successor[i]))
4652 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4653 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4654 *trail_to_new_successor_length);
4656 for(j = 0;i < trail_me_to_probable_successor_len;i++,j++)
4658 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4660 return trail_to_new_successor;
4664 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4665 trail_to_new_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4666 *trail_to_new_successor_length);
4668 for(i = 0; i < *trail_to_new_successor_length; i++)
4669 trail_to_new_successor[i] = trail_me_to_probable_successor[i];
4671 return trail_to_new_successor;
4676 * Check if the peer which sent us verify successor result message is still ours
4677 * successor or not. If not, then compare existing successor and probable successor.
4678 * In case probable successor is the correct successor, remove the existing
4679 * successor. Add probable successor as new successor. Send notify new successor
4680 * message to new successor.
4682 * @param probable_successor
4684 * @param trail_length
4687 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4688 struct GNUNET_PeerIdentity probable_successor,
4689 const struct GNUNET_PeerIdentity *trail,
4690 unsigned int trail_length)
4692 struct FingerInfo *current_successor;
4693 struct GNUNET_PeerIdentity *closest_peer;
4694 struct GNUNET_HashCode trail_id;
4695 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4696 struct FriendInfo *target_friend;
4697 unsigned int trail_me_to_probable_succ_len;
4698 unsigned int is_predecessor = GNUNET_NO;
4699 uint64_t successor_value;
4701 current_successor = &finger_table[0];
4702 successor_value = compute_finger_identity_value(0);
4704 /* Have we found some other successor, while waiting for verify successor result. */
4705 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&curr_succ, ¤t_successor->finger_identity))
4707 /* We could have added this new successor, only if it was closer the old one. */
4708 closest_peer = select_closest_peer (&curr_succ,
4709 ¤t_successor->finger_identity,
4710 successor_value, is_predecessor);
4712 /* FIXME: it may fail in case we have done more number of iterations of
4713 find _finger_trail_task. */
4714 /*GNUNET_assert (0 ==
4715 GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4716 ¤t_successor->finger_identity));*/
4720 closest_peer = select_closest_peer (&probable_successor,
4721 ¤t_successor->finger_identity,
4722 successor_value, is_predecessor);
4724 /* If the current_successor in the finger table is closest, then do nothing. */
4725 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4726 ¤t_successor->finger_identity))
4729 /* Probable successor is the closest peer.*/
4730 if(trail_length > 0)
4731 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4734 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4735 &probable_successor));
4737 trail_me_to_probable_succ_len = 0;
4738 /* TODO: Check if the path to reach to probable successor contains a friend. */
4739 trail_me_to_probable_succ =
4740 check_trail_me_to_probable_succ (probable_successor,
4741 trail, trail_length,
4742 &trail_me_to_probable_succ_len);
4744 /* Remove the existing successor. */
4745 remove_existing_finger (current_successor, 0);
4747 /* Generate a new trail id to reach to your new successor. */
4748 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4749 &trail_id, sizeof (trail_id));
4751 if (trail_me_to_probable_succ_len > 0)
4753 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4754 GNUNET_assert (NULL !=
4756 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4757 &trail_me_to_probable_succ[0])));
4761 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4762 GNUNET_assert (NULL !=
4764 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4765 &probable_successor)));
4768 add_new_finger (probable_successor, trail_me_to_probable_succ,
4769 trail_me_to_probable_succ_len, trail_id, 0);
4771 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4772 trail_me_to_probable_succ,
4773 trail_me_to_probable_succ_len,
4781 * Core handle for p2p verify successor result messages.
4782 * @param cls closure
4783 * @param message message
4784 * @param peer peer identity this notification is about
4785 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4788 handle_dht_p2p_verify_successor_result(void *cls,
4789 const struct GNUNET_PeerIdentity *peer,
4790 const struct GNUNET_MessageHeader *message)
4792 const struct PeerVerifySuccessorResultMessage *vsrm;
4793 enum GDS_ROUTING_trail_direction trail_direction;
4794 struct GNUNET_PeerIdentity querying_peer;
4795 struct GNUNET_HashCode trail_id;
4796 struct GNUNET_PeerIdentity *next_hop;
4797 struct FriendInfo *target_friend;
4798 struct GNUNET_PeerIdentity probable_successor;
4799 struct GNUNET_PeerIdentity current_successor;
4800 const struct GNUNET_PeerIdentity *trail;
4801 unsigned int trail_length;
4804 msize = ntohs (message->size);
4805 /* We send a trail to reach from old successor to new successor, if
4806 * old_successor != new_successor.*/
4807 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4809 GNUNET_break_op (0);
4813 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4814 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4815 sizeof (struct GNUNET_PeerIdentity);
4817 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4818 sizeof (struct GNUNET_PeerIdentity) != 0)
4820 GNUNET_break_op (0);
4824 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4825 querying_peer = vsrm->querying_peer;
4826 trail_direction = ntohl (vsrm->trail_direction);
4827 trail_id = vsrm->trail_id;
4828 probable_successor = vsrm->probable_successor;
4829 current_successor = vsrm->current_successor;
4831 /* I am the querying_peer. */
4832 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4834 compare_and_update_successor (current_successor,
4835 probable_successor, trail, trail_length);
4839 /*If you are not the querying peer then pass on the message */
4840 GNUNET_assert (NULL != (next_hop =
4841 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
4842 GNUNET_assert (NULL !=
4844 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4845 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4846 vsrm->current_successor,
4847 probable_successor, trail_id,
4850 trail_direction, target_friend);
4856 * Core handle for p2p notify new successor messages.
4857 * @param cls closure
4858 * @param message message
4859 * @param peer peer identity this notification is about
4860 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4863 handle_dht_p2p_notify_new_successor(void *cls,
4864 const struct GNUNET_PeerIdentity *peer,
4865 const struct GNUNET_MessageHeader *message)
4867 const struct PeerNotifyNewSuccessorMessage *nsm;
4868 struct GNUNET_PeerIdentity *trail;
4869 struct GNUNET_PeerIdentity source;
4870 struct GNUNET_PeerIdentity new_successor;
4871 struct GNUNET_HashCode trail_id;
4872 struct GNUNET_PeerIdentity next_hop;
4873 struct FriendInfo *target_friend;
4876 uint32_t trail_length;
4878 msize = ntohs (message->size);
4880 /* We have the trail to reach from source to new successor. */
4881 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
4883 GNUNET_break_op (0);
4887 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
4888 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
4889 sizeof (struct GNUNET_PeerIdentity);
4890 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
4891 sizeof (struct GNUNET_PeerIdentity) != 0)
4893 GNUNET_break_op (0);
4897 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
4898 source = nsm->source_peer;
4899 new_successor = nsm->new_successor;
4900 trail_id = nsm->trail_id;
4902 //FIXME: add a check to make sure peer is correct.
4904 /* I am the new_successor to source_peer. */
4905 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
4907 GDS_ROUTING_add (trail_id, *peer, my_identity);
4908 compare_and_update_predecessor (source, trail, trail_length);
4912 GNUNET_assert(trail_length > 0);
4913 /* I am part of trail to reach to successor. */
4914 my_index = search_my_index (trail, trail_length);
4917 GNUNET_break_op (0);
4918 return GNUNET_SYSERR;
4921 if ((trail_length-1) == my_index)
4922 next_hop = new_successor;
4924 next_hop = trail[my_index + 1];
4927 /* Add an entry in routing table for trail from source to its new successor. */
4928 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
4930 GNUNET_assert (NULL !=
4932 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4933 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
4935 trail_id, target_friend);
4942 * Core handler for P2P trail rejection message
4943 * @param cls closure
4944 * @param message message
4945 * @param peer peer identity this notification is about
4946 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4949 handle_dht_p2p_trail_setup_rejection (void *cls,
4950 const struct GNUNET_PeerIdentity *peer,
4951 const struct GNUNET_MessageHeader *message)
4953 const struct PeerTrailRejectionMessage *trail_rejection;
4954 unsigned int trail_length;
4955 const struct GNUNET_PeerIdentity *trail_peer_list;
4956 struct FriendInfo *target_friend;
4957 struct GNUNET_TIME_Relative congestion_timeout;
4958 struct GNUNET_HashCode trail_id;
4959 struct GNUNET_PeerIdentity next_peer;
4960 struct GNUNET_PeerIdentity source;
4961 struct GNUNET_PeerIdentity *next_hop;
4962 uint64_t ultimate_destination_finger_value;
4963 unsigned int is_predecessor;
4966 msize = ntohs (message->size);
4967 /* We are passing the trail setup so far. */
4968 if (msize < sizeof (struct PeerTrailRejectionMessage))
4970 GNUNET_break_op (0);
4974 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
4975 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
4976 sizeof (struct GNUNET_PeerIdentity);
4977 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4978 sizeof (struct GNUNET_PeerIdentity) != 0)
4980 GNUNET_break_op (0);
4984 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
4985 is_predecessor = ntohl (trail_rejection->is_predecessor);
4986 congestion_timeout = trail_rejection->congestion_time;
4987 source = trail_rejection->source_peer;
4988 trail_id = trail_rejection->trail_id;
4989 ultimate_destination_finger_value =
4990 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
4992 /* First set the congestion time of the friend that sent you this message. */
4993 GNUNET_assert (NULL !=
4995 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4996 target_friend->congestion_timestamp =
4997 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
4998 congestion_timeout);
5000 /* I am the source peer which wants to setup the trail. Do nothing.
5001 * send_find_finger_trail_task is scheduled periodically.*/
5002 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5005 /* If I am congested then pass this message to peer before me in trail. */
5006 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5008 struct GNUNET_PeerIdentity *new_trail;
5009 unsigned int new_trail_length;
5011 /* Remove yourself from the trail setup so far. */
5012 if (trail_length == 1)
5015 new_trail_length = 0;
5020 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5021 sizeof (struct GNUNET_PeerIdentity));
5023 /* Remove myself from the trail. */
5024 new_trail_length = trail_length -1;
5025 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5026 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5029 GNUNET_assert (NULL !=
5031 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5032 GDS_NEIGHBOURS_send_trail_rejection (source,
5033 ultimate_destination_finger_value,
5034 my_identity, is_predecessor,
5035 new_trail,new_trail_length,trail_id,
5036 target_friend, CONGESTION_TIMEOUT);
5037 GNUNET_free (new_trail);
5041 struct Closest_Peer successor;
5042 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5044 /* Am I the final destination? */
5045 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5048 if (0 == trail_length)
5051 next_peer = trail_peer_list[trail_length-1];
5053 GNUNET_assert (NULL !=
5055 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5057 GDS_NEIGHBOURS_send_trail_setup_result (source,
5059 target_friend, trail_length,
5062 ultimate_destination_finger_value,
5067 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5069 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5070 peer_list[trail_length] = my_identity;
5072 GNUNET_assert (NULL !=
5074 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5076 GDS_NEIGHBOURS_send_trail_setup (source,
5077 ultimate_destination_finger_value,
5078 successor.best_known_destination,
5079 target_friend, trail_length + 1, peer_list,
5080 is_predecessor, trail_id,
5081 successor.trail_id);
5088 * Core handle for p2p trail tear compression messages.
5089 * @param cls closure
5090 * @param message message
5091 * @param peer peer identity this notification is about
5092 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5095 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5096 const struct GNUNET_MessageHeader *message)
5098 const struct PeerTrailCompressionMessage *trail_compression;
5099 struct GNUNET_PeerIdentity *next_hop;
5100 struct FriendInfo *target_friend;
5101 struct GNUNET_HashCode trail_id;
5104 msize = ntohs (message->size);
5106 if (msize != sizeof (struct PeerTrailCompressionMessage))
5108 GNUNET_break_op (0);
5112 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5113 trail_id = trail_compression->trail_id;
5115 /* Am I the new first friend to reach to finger of this trail. */
5116 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5119 GNUNET_assert (NULL !=
5120 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5121 &trail_compression->source_peer)));
5123 /* Update your prev hop to source of this message. */
5124 GNUNET_assert (GNUNET_SYSERR !=
5125 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5126 trail_compression->source_peer)));
5130 /* Pass the message to next hop to finally reach to new_first_friend. */
5131 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5133 if (NULL == next_hop)
5139 GNUNET_assert (NULL !=
5141 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5143 GDS_ROUTING_remove_trail (trail_id);
5145 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5147 trail_compression->new_first_friend,
5154 * Core handler for trail teardown message.
5155 * @param cls closure
5156 * @param message message
5157 * @param peer sender of this messsage.
5158 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5161 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5162 const struct GNUNET_MessageHeader *message)
5164 const struct PeerTrailTearDownMessage *trail_teardown;
5165 enum GDS_ROUTING_trail_direction trail_direction;
5166 struct GNUNET_HashCode trail_id;
5167 struct GNUNET_PeerIdentity *next_hop;
5170 msize = ntohs (message->size);
5172 /* Here we pass only the trail id. */
5173 if (msize != sizeof (struct PeerTrailTearDownMessage))
5175 GNUNET_break_op (0);
5179 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5180 trail_direction = ntohl (trail_teardown->trail_direction);
5181 trail_id = trail_teardown->trail_id;
5183 /* Check if peer is the real peer from which we should get this message.*/
5184 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5186 GNUNET_assert (NULL != (prev_hop =
5187 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5188 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5191 return GNUNET_SYSERR;
5195 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5197 if (NULL == next_hop)
5200 return GNUNET_SYSERR;
5203 /* I am the next hop, which means I am the final destination. */
5204 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5206 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5211 /* If not final destination, then send a trail teardown message to next hop.*/
5212 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5213 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5214 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5222 * Core handle for p2p add trail message.
5223 * @param cls closure
5224 * @param message message
5225 * @param peer peer identity this notification is about
5226 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5229 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5230 const struct GNUNET_MessageHeader *message)
5232 const struct PeerAddTrailMessage *add_trail;
5233 const struct GNUNET_PeerIdentity *trail;
5234 struct GNUNET_HashCode trail_id;
5235 struct GNUNET_PeerIdentity destination_peer;
5236 struct GNUNET_PeerIdentity source_peer;
5237 struct GNUNET_PeerIdentity next_hop;
5238 unsigned int trail_length;
5239 unsigned int my_index;
5242 msize = ntohs (message->size);
5243 /* In this message we pass the whole trail from source to destination as we
5244 * are adding that trail.*/
5245 if (msize < sizeof (struct PeerAddTrailMessage))
5247 GNUNET_break_op (0);
5251 add_trail = (const struct PeerAddTrailMessage *) message;
5252 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5253 sizeof (struct GNUNET_PeerIdentity);
5254 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5255 sizeof (struct GNUNET_PeerIdentity) != 0)
5257 GNUNET_break_op (0);
5261 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5262 destination_peer = add_trail->destination_peer;
5263 source_peer = add_trail->source_peer;
5264 trail_id = add_trail->trail_id;
5266 //FIXME: add a check that sender peer is not malicious. Make it a generic
5267 // function so that it can be used in all other functions where we need the
5268 // same functionality.
5270 /* I am not the destination of the trail. */
5271 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5273 struct FriendInfo *target_friend;
5275 /* Get my location in the trail. */
5276 my_index = search_my_index (trail, trail_length);
5280 GNUNET_break_op (0);
5281 return GNUNET_SYSERR;
5285 if ((trail_length - 1) == my_index)
5287 next_hop = destination_peer;
5291 next_hop = trail[my_index + 1];
5294 /* Add in your routing table. */
5295 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5296 GNUNET_assert (NULL !=
5298 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5299 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5300 trail, trail_length, target_friend);
5303 /* I am the destination. Add an entry in routing table. */
5304 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5310 * Free the finger trail in which the first friend to reach to a finger is
5311 * disconnected_friend. Also remove entry from routing table for that particular
5313 * @param disconnected_friend PeerIdentity of friend which got disconnected
5314 * @param remove_finger Finger whose trail we need to check if it has
5315 * disconnected_friend as the first hop.
5316 * @return Total number of trails in which disconnected_friend was the first
5320 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5321 struct FingerInfo *remove_finger)
5323 unsigned int matching_trails_count;
5326 /* Number of trails with disconnected_friend as the first hop in the trail
5327 * to reach from me to remove_finger, NOT including endpoints. */
5328 matching_trails_count = 0;
5330 /* Iterate over all the trails of finger. */
5331 for (i = 0; i < remove_finger->trails_count; i++)
5333 struct Trail *trail;
5334 trail = &remove_finger->trail_list[i];
5336 /* This assertion is ensure that there are no gaps in the trail list.
5337 REMOVE IT AFTERWARDS. */
5338 GNUNET_assert (GNUNET_YES == trail->is_present);
5340 /* First friend to reach to finger is disconnected_peer. */
5341 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5342 disconnected_friend))
5344 struct GNUNET_PeerIdentity *next_hop;
5345 struct FriendInfo *remove_friend;
5347 GNUNET_assert (NULL !=
5349 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5350 disconnected_friend)));
5351 /* FIXME: removing no but check it. */
5352 //remove_friend->trails_count--;
5353 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5354 GDS_ROUTING_SRC_TO_DEST);
5356 /* Here it may happen that as all the peers got disconnected, the entry in
5357 routing table for that particular trail has been removed, because the
5358 previously disconnected peer was either a next hop or prev hop of that
5360 if (NULL == next_hop)
5363 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5365 matching_trails_count++;
5366 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5369 trail->is_present = GNUNET_NO;
5372 return matching_trails_count;
5377 * Iterate over finger_table entries.
5378 * 0. Ignore finger which is my_identity or if no valid entry present at
5379 * that finger index.
5380 * 1. If disconnected_friend is a finger, then remove the routing entry from
5381 your own table. Free the trail.
5382 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5383 * 2.1 Remove all the trails and entry from routing table in which disconnected
5384 * friend is the first friend in the trail. If disconnected_friend is the
5385 * first friend in all the trails to reach finger, then remove the finger.
5386 * @param disconnected_friend Peer identity of friend which got disconnected.
5389 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5391 struct FingerInfo *remove_finger;
5392 struct FriendInfo *remove_friend;
5393 int removed_trails_count;
5396 /* Iterate over finger table entries. */
5397 for (i = 0; i < MAX_FINGERS; i++)
5399 remove_finger = &finger_table[i];
5401 /* No finger stored at this trail index. */
5402 if (GNUNET_NO == remove_finger->is_present)
5405 /* I am my own finger, then ignore this finger. */
5406 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5410 /* Is disconnected_peer a finger? */
5411 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5412 &remove_finger->finger_identity))
5414 struct GNUNET_PeerIdentity *next_hop;
5415 struct GNUNET_HashCode trail_id;
5418 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5419 trail_id = remove_finger->trail_list[0].trail_id;
5423 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5426 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5427 &remove_finger->finger_identity)));
5428 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5429 GNUNET_assert (NULL !=
5431 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5432 disconnected_peer)));
5435 remove_finger->trail_list[0].is_present = GNUNET_NO;
5436 //GNUNET_assert (0 != remove_friend->trails_count);
5437 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5438 remove_finger->is_present = GNUNET_NO;
5439 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5443 /* If finger is a friend but not disconnected_friend, then continue. */
5444 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5445 &remove_finger->finger_identity))
5448 /* Iterate over the list of trails to reach remove_finger. Check if
5449 * disconnected_friend is the first friend in any of the trail. */
5450 removed_trails_count = remove_matching_trails (disconnected_peer,
5452 remove_finger->trails_count =
5453 remove_finger->trails_count - removed_trails_count;
5454 /* All the finger trails had disconnected_friend as the first friend,
5455 * so free the finger. */
5456 if (remove_finger->trails_count == 0)
5458 remove_finger->is_present = GNUNET_NO;
5459 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5466 * Method called whenever a peer disconnects.
5468 * @param cls closure
5469 * @param peer peer identity this notification is about
5472 handle_core_disconnect (void *cls,
5473 const struct GNUNET_PeerIdentity *peer)
5475 struct FriendInfo *remove_friend;
5477 /* If disconnected to own identity, then return. */
5478 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5481 GNUNET_assert (NULL != (remove_friend =
5482 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5484 /* Remove fingers with peer as first friend or if peer is a finger. */
5485 remove_matching_fingers (peer);
5487 /* Remove any trail from routing table of which peer is a part of. This function
5488 * internally sends a trail teardown message in the direction of which
5489 * disconnected peer is not part of. */
5490 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5492 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5494 /* Remove peer from friend_peermap. */
5495 GNUNET_assert (GNUNET_YES ==
5496 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5500 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5503 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5505 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5506 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5515 * Method called whenever a peer connects.
5517 * @param cls closure
5518 * @param peer_identity peer identity this notification is about
5521 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5523 struct FriendInfo *friend;
5525 /* Check for connect to self message */
5526 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5529 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5531 /* If peer already exists in our friend_peermap, then exit. */
5532 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5539 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
5542 friend = GNUNET_new (struct FriendInfo);
5543 friend->id = *peer_identity;
5545 GNUNET_assert (GNUNET_OK ==
5546 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5547 peer_identity, friend,
5548 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5551 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5552 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5553 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5558 * To be called on core init/fail.
5560 * @param cls service closure
5561 * @param identity the public identity of this peer
5564 core_init (void *cls,
5565 const struct GNUNET_PeerIdentity *identity)
5567 my_identity = *identity;
5570 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5571 my_id64 = GNUNET_ntohll (my_id64);
5572 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5573 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5579 * Initialize finger table entries.
5582 finger_table_init ()
5587 for(i = 0; i < MAX_FINGERS; i++)
5589 finger_table[i].is_present = GNUNET_NO;
5590 for (j = 0; j < MAXIMUM_TRAILS_PER_FINGER; j++)
5591 finger_table[i].trail_list[j].is_present = GNUNET_NO;
5592 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5598 * Initialize neighbours subsystem.
5599 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5602 GDS_NEIGHBOURS_init (void)
5604 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5605 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5606 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5607 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5608 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5609 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5610 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5611 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5612 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5613 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5614 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5615 sizeof (struct PeerTrailCompressionMessage)},
5616 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5617 sizeof (struct PeerTrailTearDownMessage)},
5618 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5623 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5624 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5625 GNUNET_NO, core_handlers);
5626 if (NULL == core_api)
5627 return GNUNET_SYSERR;
5629 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5630 finger_table_init ();
5637 * Shutdown neighbours subsystem.
5640 GDS_NEIGHBOURS_done (void)
5642 if (NULL == core_api)
5645 GNUNET_CORE_disconnect (core_api);
5648 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5649 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5650 friend_peermap = NULL;
5652 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5655 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5656 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5659 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5661 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5662 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5670 * @return my identity
5672 struct GNUNET_PeerIdentity
5673 GDS_NEIGHBOURS_get_my_id (void)
5678 /* end of gnunet-service-xdht_neighbours.c */