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 * FIXME: removed first_friend_trails_count, need to write a function
718 * to calculate each time we need it. Else, keep a pointer to first
719 * friend of in the trail.
720 * Information about an individual trail.
727 struct Trail_Element *trail_head;
732 struct Trail_Element *trail_tail;
735 * Unique identifier of this trail.
737 struct GNUNET_HashCode trail_id;
740 * Length of trail pointed
742 unsigned int trail_length;
745 * Is there a valid trail entry.
747 unsigned int is_present;
751 * An entry in finger_table
758 struct GNUNET_PeerIdentity finger_identity;
761 * Is any finger stored at this finger index.
763 unsigned int is_present;
766 * Index in finger peer map
768 uint32_t finger_table_index;
771 * Number of trails setup so far for this finger.
772 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
774 uint32_t trails_count;
777 * Array of trails to reach to this finger.
779 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
784 * Stores information about the peer which is closest to destination_finger_value.
785 * 'closest' can be either successor or predecessor depending on is_predecessor
791 * Destination finger value.
793 uint64_t destination_finger_value;
796 * Is finger_value a predecessor or any other finger.
798 unsigned int is_predecessor;
801 * Trail id to reach to peer.
802 * In case peer is my identity or friend, it is set to 0.
804 struct GNUNET_HashCode trail_id;
807 * Next destination. In case of friend and my_identity , it is same as next_hop
808 * In case of finger it is finger identity.
810 struct GNUNET_PeerIdentity best_known_destination;
813 * In case best_known_destination is a finger, then first friend in the trail
814 * to reach to it. In other case, same as best_known_destination.
816 struct GNUNET_PeerIdentity next_hop;
821 * Data structure to store the trail chosen to reach to finger.
823 struct Selected_Finger_Trail
826 * First friend in the trail to reach finger.
828 struct FriendInfo friend;
831 * Identifier of this trail.
833 struct GNUNET_HashCode trail_id;
836 * Total number of peers in this trail.
838 unsigned int trail_length;
842 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
843 * get our first friend.
845 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
848 * Task that sends verify successor message. This task is started when we get
849 * our successor for the first time.
851 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_task;
854 * Identity of this peer.
856 static struct GNUNET_PeerIdentity my_identity;
859 * Peer map of all the friends of a peer
861 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
864 * Array of all the fingers.
866 static struct FingerInfo finger_table [MAX_FINGERS];
871 static struct GNUNET_CORE_Handle *core_api;
874 * Handle for the statistics service.
876 extern struct GNUNET_STATISTICS_Handle *GDS_stats;
879 * The current finger index that we have want to find trail to. We start the
880 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
881 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
882 * we reset this index to 0.
884 static unsigned int current_search_finger_index;
887 * Should we store our topology predecessor and successor IDs into statistics?
889 unsigned int track_topology;
893 * Called when core is ready to send a message we asked for
894 * out to the destination.
896 * @param cls the 'struct FriendInfo' of the target friend
897 * @param size number of bytes available in buf
898 * @param buf where the callee should write the message
899 * @return number of bytes written to buf
902 core_transmit_notify (void *cls, size_t size, void *buf)
904 struct FriendInfo *peer = cls;
906 struct P2PPendingMessage *pending;
911 while ((NULL != (pending = peer->head)) &&
912 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
914 peer->pending_count--;
915 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
916 GNUNET_free (pending);
920 /* no messages pending */
926 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
927 GNUNET_CORE_PRIO_BEST_EFFORT,
928 GNUNET_TIME_absolute_get_remaining
929 (pending->timeout), &peer->id,
930 ntohs (pending->msg->size),
931 &core_transmit_notify, peer);
932 GNUNET_break (NULL != peer->th);
936 while ((NULL != (pending = peer->head)) &&
937 (size - off >= (msize = ntohs (pending->msg->size))))
939 /*GNUNET_STATISTICS_update (GDS_stats,
941 ("# Bytes transmitted to other peers"), msize,
943 memcpy (&cbuf[off], pending->msg, msize);
945 peer->pending_count--;
946 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
947 GNUNET_free (pending);
949 if (peer->head != NULL)
952 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
953 GNUNET_CORE_PRIO_BEST_EFFORT,
954 GNUNET_TIME_absolute_get_remaining
955 (pending->timeout), &peer->id, msize,
956 &core_transmit_notify, peer);
957 GNUNET_break (NULL != peer->th);
964 * Transmit all messages in the friend's message queue.
966 * @param peer message queue to process
969 process_friend_queue (struct FriendInfo *peer)
971 struct P2PPendingMessage *pending;
973 if (NULL == (pending = peer->head))
975 if (NULL != peer->th)
978 GNUNET_STATISTICS_update (GDS_stats,
980 ("# Bytes of bandwidth requested from core"),
981 ntohs (pending->msg->size), GNUNET_NO);
984 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
986 GNUNET_TIME_absolute_get_remaining
987 (pending->timeout), &peer->id,
988 ntohs (pending->msg->size),
989 &core_transmit_notify, peer);
990 GNUNET_break (NULL != peer->th);
995 * Construct a trail setup message and forward it to target_friend
996 * @param source_peer Peer which wants to setup the trail
997 * @param ultimate_destination_finger_value Peer identity closest to this value
998 * will be finger to @a source_peer
999 * @param best_known_destination Best known destination (could be finger or friend)
1000 * which should get this message. In case it is
1001 * friend, then it is same as target_friend
1002 * @param target_friend Friend to which message is forwarded now.
1003 * @param trail_length Total number of peers in trail setup so far.
1004 * @param trail_peer_list Trail setup so far
1005 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1006 * @param trail_id Unique identifier for the trail we are trying to setup.
1007 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1008 * best_known_destination when its a finger. If not
1009 * used then set to 0.
1012 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1013 uint64_t ultimate_destination_finger_value,
1014 struct GNUNET_PeerIdentity best_known_destination,
1015 struct FriendInfo *target_friend,
1016 unsigned int trail_length,
1017 const struct GNUNET_PeerIdentity *trail_peer_list,
1018 unsigned int is_predecessor,
1019 struct GNUNET_HashCode trail_id,
1020 struct GNUNET_HashCode intermediate_trail_id)
1022 struct P2PPendingMessage *pending;
1023 struct PeerTrailSetupMessage *tsm;
1024 struct GNUNET_PeerIdentity *peer_list;
1027 msize = sizeof (struct PeerTrailSetupMessage) +
1028 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1030 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1036 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1038 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1042 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1043 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1044 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1045 pending->msg = &tsm->header;
1046 tsm->header.size = htons (msize);
1047 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1048 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1049 tsm->source_peer = source_peer;
1050 tsm->best_known_destination = best_known_destination;
1051 tsm->is_predecessor = htonl (is_predecessor);
1052 tsm->trail_id = trail_id;
1053 tsm->intermediate_trail_id = intermediate_trail_id;
1055 if (trail_length > 0)
1057 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1058 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1061 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1062 target_friend->pending_count++;
1063 process_friend_queue (target_friend);
1068 * Construct a trail setup result message and forward it to target friend.
1069 * @param querying_peer Peer which sent the trail setup request and should get
1071 * @param Finger Peer to which the trail has been setup to.
1072 * @param target_friend Friend to which this message should be forwarded.
1073 * @param trail_length Numbers of peers in the trail.
1074 * @param trail_peer_list Peers which are part of the trail from
1075 * querying_peer to Finger, NOT including them.
1076 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1077 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1079 * @param trail_id Unique identifier of the trail.
1082 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1083 struct GNUNET_PeerIdentity finger,
1084 struct FriendInfo *target_friend,
1085 unsigned int trail_length,
1086 const struct GNUNET_PeerIdentity *trail_peer_list,
1087 unsigned int is_predecessor,
1088 uint64_t ultimate_destination_finger_value,
1089 struct GNUNET_HashCode trail_id)
1091 struct P2PPendingMessage *pending;
1092 struct PeerTrailSetupResultMessage *tsrm;
1093 struct GNUNET_PeerIdentity *peer_list;
1096 msize = sizeof (struct PeerTrailSetupResultMessage) +
1097 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1099 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1105 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1107 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1111 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1112 pending->importance = 0;
1113 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1114 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1115 pending->msg = &tsrm->header;
1116 tsrm->header.size = htons (msize);
1117 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1118 tsrm->querying_peer = querying_peer;
1119 tsrm->finger_identity = finger;
1120 tsrm->is_predecessor = htonl (is_predecessor);
1121 tsrm->trail_id = trail_id;
1122 tsrm->ulitmate_destination_finger_value =
1123 GNUNET_htonll (ultimate_destination_finger_value);
1124 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1126 if (trail_length > 0)
1128 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1130 /* Send the message to chosen friend. */
1131 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1132 target_friend->pending_count++;
1133 process_friend_queue (target_friend);
1138 * Send trail rejection message to target friend
1139 * @param source_peer Peer which is trying to setup the trail.
1140 * @param ultimate_destination_finger_value Peer closest to this value will be
1141 * @a source_peer's finger
1142 * @param congested_peer Peer which sent this message as it is congested.
1143 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1144 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1145 * by congested_peer. This does NOT include @a source_peer
1146 * and congested_peer.
1147 * @param trail_length Total number of peers in trail_peer_list, NOT including
1148 * @a source_peer and @a congested_peer
1149 * @param trail_id Unique identifier of this trail.
1150 * @param congestion_timeout Duration given by congested peer as an estimate of
1151 * how long it may remain congested.
1154 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1155 uint64_t ultimate_destination_finger_value,
1156 struct GNUNET_PeerIdentity congested_peer,
1157 unsigned int is_predecessor,
1158 const struct GNUNET_PeerIdentity *trail_peer_list,
1159 unsigned int trail_length,
1160 struct GNUNET_HashCode trail_id,
1161 struct FriendInfo *target_friend,
1162 const struct GNUNET_TIME_Relative congestion_timeout)
1164 struct PeerTrailRejectionMessage *trm;
1165 struct P2PPendingMessage *pending;
1166 struct GNUNET_PeerIdentity *peer_list;
1169 msize = sizeof (struct PeerTrailRejectionMessage) +
1170 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1172 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1178 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1180 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1184 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1185 pending->importance = 0;
1186 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1187 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1188 pending->msg = &trm->header;
1189 trm->header.size = htons (msize);
1190 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1191 trm->source_peer = source_peer;
1192 trm->congested_peer = congested_peer;
1193 trm->congestion_time = congestion_timeout;
1194 trm->is_predecessor = htonl (is_predecessor);
1195 trm->trail_id = trail_id;
1196 trm->ultimate_destination_finger_value =
1197 GNUNET_htonll (ultimate_destination_finger_value);
1199 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1200 if (trail_length > 0)
1202 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1205 /* Send the message to chosen friend. */
1206 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1207 target_friend->pending_count++;
1208 process_friend_queue (target_friend);
1213 * Construct a verify successor message and forward it to target_friend.
1214 * @param source_peer Peer which wants to verify its successor.
1215 * @param successor Peer which is @a source_peer's current successor.
1216 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1217 * NOT including them.
1218 * @param trail List of peers which are part of trail to reach from @a source_peer
1219 * to @a successor, NOT including them.
1220 * @param trail_length Total number of peers in @a trail.
1221 * @param target_friend Next friend to get this message.
1224 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1225 struct GNUNET_PeerIdentity successor,
1226 struct GNUNET_HashCode trail_id,
1227 struct GNUNET_PeerIdentity *trail,
1228 unsigned int trail_length,
1229 struct FriendInfo *target_friend)
1231 struct PeerVerifySuccessorMessage *vsm;
1232 struct P2PPendingMessage *pending;
1233 struct GNUNET_PeerIdentity *peer_list;
1236 msize = sizeof (struct PeerVerifySuccessorMessage) +
1237 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1238 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1244 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1246 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1250 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1251 pending->importance = 0; /* FIXME */
1252 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1253 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1254 pending->msg = &vsm->header;
1255 vsm->header.size = htons (msize);
1256 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1257 vsm->source_peer = source_peer;
1258 vsm->successor = successor;
1259 vsm->trail_id = trail_id;
1261 if (trail_length != 0)
1263 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1264 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1267 /* Send the message to chosen friend. */
1268 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1269 target_friend->pending_count++;
1270 process_friend_queue (target_friend);
1275 * FIXME: In every function we pass target friend except for this one.
1276 * so, either change everything or this one. also, should se just store
1277 * the pointer to friend in routing table rather than gnunet_peeridentity.
1278 * if yes then we should keep friend info in.h andmake lot of changes.
1279 * Construct a trail teardown message and forward it to target friend.
1280 * @param trail_id Unique identifier of the trail.
1281 * @param trail_direction Direction of trail.
1282 * @param target_friend Friend to get this message.
1285 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1286 unsigned int trail_direction,
1287 struct GNUNET_PeerIdentity peer)
1289 struct PeerTrailTearDownMessage *ttdm;
1290 struct P2PPendingMessage *pending;
1291 struct FriendInfo *target_friend;
1294 msize = sizeof (struct PeerTrailTearDownMessage);
1296 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1302 /*FIXME:In what case friend can be null. ?*/
1303 if (NULL == (target_friend =
1304 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1307 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1309 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1313 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1314 pending->importance = 0; /* FIXME */
1315 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1316 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1317 pending->msg = &ttdm->header;
1318 ttdm->header.size = htons (msize);
1319 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1320 ttdm->trail_id = trail_id;
1321 ttdm->trail_direction = htonl (trail_direction);
1323 /* Send the message to chosen friend. */
1324 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1325 target_friend->pending_count++;
1326 process_friend_queue (target_friend);
1331 * Construct a verify successor result message and send it to target_friend
1332 * @param querying_peer Peer which sent the verify successor message.
1333 * @param source_successor Current_successor of @a querying_peer.
1334 * @param current_predecessor Current predecessor of @a successor. Could be same
1335 * or different from @a querying_peer.
1336 * @param trail_id Unique identifier of the trail from @a querying_peer to
1337 * @a successor, NOT including them.
1338 * @param trail List of peers which are part of trail from @a querying_peer to
1339 * @a successor, NOT including them.
1340 * @param trail_length Total number of peers in @a trail
1341 * @param trail_direction Direction in which we are sending the message. In this
1342 * case we are sending result from @a successor to @a querying_peer.
1343 * @param target_friend Next friend to get this message.
1346 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1347 struct GNUNET_PeerIdentity current_successor,
1348 struct GNUNET_PeerIdentity probable_successor,
1349 struct GNUNET_HashCode trail_id,
1350 const struct GNUNET_PeerIdentity *trail,
1351 unsigned int trail_length,
1352 enum GDS_ROUTING_trail_direction trail_direction,
1353 struct FriendInfo *target_friend)
1355 struct PeerVerifySuccessorResultMessage *vsmr;
1356 struct P2PPendingMessage *pending;
1357 struct GNUNET_PeerIdentity *peer_list;
1360 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1361 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1363 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1369 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1371 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1375 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1376 pending->importance = 0; /* FIXME */
1377 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1378 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1379 pending->msg = &vsmr->header;
1380 vsmr->header.size = htons (msize);
1381 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1382 vsmr->querying_peer = querying_peer;
1383 vsmr->current_successor = current_successor;
1384 vsmr->probable_successor = probable_successor;
1385 vsmr->trail_direction = htonl (trail_direction);
1386 vsmr->trail_id = trail_id;
1388 if (trail_length > 0)
1390 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1391 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1394 /* Send the message to chosen friend. */
1395 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1396 target_friend->pending_count++;
1397 process_friend_queue (target_friend);
1402 * Construct a notify new successor message and send it to target_friend
1403 * @param source_peer Peer which wants to notify to its new successor that it
1404 * could be its predecessor.
1405 * @param successor New successor of @a source_peer
1406 * @param successor_trail List of peers in Trail to reach from
1407 * @a source_peer to @a new_successor, NOT including
1409 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1410 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1411 * @param target_friend Next friend to get this message.
1414 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1415 struct GNUNET_PeerIdentity successor,
1416 const struct GNUNET_PeerIdentity *successor_trail,
1417 unsigned int successor_trail_length,
1418 struct GNUNET_HashCode succesor_trail_id,
1419 struct FriendInfo *target_friend)
1421 struct PeerNotifyNewSuccessorMessage *nsm;
1422 struct P2PPendingMessage *pending;
1423 struct GNUNET_PeerIdentity *peer_list;
1426 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1427 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1429 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1435 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1437 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1441 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1442 pending->importance = 0; /* FIXME */
1443 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1444 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1445 pending->msg = &nsm->header;
1446 nsm->header.size = htons (msize);
1447 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1448 nsm->new_successor = successor;
1449 nsm->source_peer = source_peer;
1450 nsm->trail_id = succesor_trail_id;
1452 if (successor_trail_length > 0)
1454 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1455 memcpy (peer_list, successor_trail,
1456 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1459 /* Send the message to chosen friend. */
1460 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1461 target_friend->pending_count++;
1462 process_friend_queue (target_friend);
1467 * Construct an add_trail message and send it to target_friend
1468 * @param source_peer Source of the trail.
1469 * @param destination_peer Destination of the trail.
1470 * @param trail_id Unique identifier of the trail from
1471 * @a source_peer to @a destination_peer, NOT including the endpoints.
1472 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1473 * NOT including the endpoints.
1474 * @param trail_length Total number of peers in @a trail.
1475 * @param target_friend Next friend to get this message.
1478 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1479 struct GNUNET_PeerIdentity destination_peer,
1480 struct GNUNET_HashCode trail_id,
1481 const struct GNUNET_PeerIdentity *trail,
1482 unsigned int trail_length,
1483 struct FriendInfo *target_friend)
1485 struct PeerAddTrailMessage *adm;
1486 struct GNUNET_PeerIdentity *peer_list;
1487 struct P2PPendingMessage *pending;
1490 msize = sizeof (struct PeerAddTrailMessage) +
1491 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1493 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1499 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1501 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1505 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1506 pending->importance = 0; /* FIXME */
1507 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1508 adm = (struct PeerAddTrailMessage *) &pending[1];
1509 pending->msg = &adm->header;
1510 adm->header.size = htons (msize);
1511 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1512 adm->source_peer = source_peer;
1513 adm->destination_peer = destination_peer;
1514 adm->trail_id = trail_id;
1516 if (trail_length > 0)
1518 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1519 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1521 /* Send the message to chosen friend. */
1522 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1523 target_friend->pending_count++;
1524 process_friend_queue (target_friend);
1530 * Construct a trail compression message and send it to target_friend.
1531 * @param source_peer Source of the trail.
1532 * @param trail_id Unique identifier of trail.
1533 * @param first_friend First hop in compressed trail to reach from source to finger
1534 * @param target_friend Next friend to get this message.
1537 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1538 struct GNUNET_HashCode trail_id,
1539 struct GNUNET_PeerIdentity first_friend,
1540 struct FriendInfo *target_friend)
1542 struct P2PPendingMessage *pending;
1543 struct PeerTrailCompressionMessage *tcm;
1546 msize = sizeof (struct PeerTrailCompressionMessage);
1548 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1554 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1556 GNUNET_STATISTICS_update (GDS_stats,
1557 gettext_noop ("# P2P messages dropped due to full queue"),
1561 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1562 pending->importance = 0; /* FIXME */
1563 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1564 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1565 pending->msg = &tcm->header;
1566 tcm->header.size = htons (msize);
1567 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1568 tcm->source_peer = source_peer;
1569 tcm->new_first_friend = first_friend;
1570 tcm->trail_id = trail_id;
1572 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1573 target_friend->pending_count++;
1574 process_friend_queue (target_friend);
1580 * Search my location in trail. In case I am present more than once in the
1581 * trail (can happen during trail setup), then return my lowest index.
1582 * @param trail List of peers
1583 * @return my_index if found
1584 * -1 if no entry found.
1587 search_my_index (const struct GNUNET_PeerIdentity *trail,
1591 int lowest_index = -1;
1593 for (i = 0; i < trail_length; i++)
1595 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1600 return lowest_index;
1605 * Check if the friend is congested or have reached maximum number of trails
1606 * it can be part of of.
1607 * @param friend Friend to be checked.
1608 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1609 * #GNUNET_YES if friend is either congested or have crossed threshold
1612 is_friend_congested (struct FriendInfo *friend)
1614 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1615 ((0 == GNUNET_TIME_absolute_get_remaining
1616 (friend->congestion_timestamp).rel_value_us)))
1624 * FIXME; not handling the wrap around logic correctly.
1625 * Select closest finger to value.
1626 * @param peer1 First peer
1627 * @param peer2 Second peer
1628 * @param value Value to be compare
1629 * @return Closest peer
1631 static struct GNUNET_PeerIdentity *
1632 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1633 struct GNUNET_PeerIdentity *peer2,
1636 uint64_t peer1_value;
1637 uint64_t peer2_value;
1639 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1640 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1641 peer1_value = GNUNET_ntohll (peer1_value);
1642 peer2_value = GNUNET_ntohll (peer2_value);
1644 if (peer1_value == value)
1649 if (peer2_value == value)
1654 if (peer2_value < peer1_value)
1656 if ((peer2_value < value) && (value < peer1_value))
1660 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1661 ((0 < value) && (value < peer2_value)))
1667 if (peer1_value < peer2_value)
1669 if ((peer1_value < value) && (value < peer2_value))
1673 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1674 ((0 < value) && (value < peer1_value)))
1684 * Select closest predecessor to value.
1685 * @param peer1 First peer
1686 * @param peer2 Second peer
1687 * @param value Value to be compare
1688 * @return Peer which precedes value in the network.
1690 static struct GNUNET_PeerIdentity *
1691 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1692 struct GNUNET_PeerIdentity *peer2,
1695 uint64_t peer1_value;
1696 uint64_t peer2_value;
1698 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1699 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1700 peer1_value = GNUNET_ntohll (peer1_value);
1701 peer2_value = GNUNET_ntohll (peer2_value);
1703 if (peer1_value == value)
1706 if (peer2_value == value)
1709 if (peer1_value < peer2_value)
1711 if ((peer1_value < value) && (value < peer2_value))
1715 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1716 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1722 if (peer2_value < peer1_value)
1724 if ((peer2_value < value) && (value < peer1_value))
1728 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1729 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1739 * This is a test function to print all the entries of friend table.
1742 test_friend_peermap_print ()
1744 struct FriendInfo *friend;
1745 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1746 struct GNUNET_PeerIdentity print_peer;
1747 struct GNUNET_PeerIdentity key_ret;
1750 print_peer = my_identity;
1751 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1752 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1754 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1756 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1758 (const void **)&friend))
1760 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1761 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1762 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1768 * This is a test function, to print all the entries of finger table.
1771 test_finger_table_print()
1773 struct FingerInfo *finger;
1774 struct GNUNET_PeerIdentity print_peer;
1775 //struct Trail *trail;
1779 print_peer = my_identity;
1780 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1781 for (i = 0; i < MAX_FINGERS; i++)
1783 finger = &finger_table[i];
1785 if (GNUNET_NO == finger->is_present)
1788 print_peer = finger->finger_identity;
1789 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1790 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1793 for (j = 0; j < finger->trails_count; j++)
1795 trail = &finger->trail_list[j];
1796 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1797 struct Trail_Element *element;
1798 element = trail->trail_head;
1799 for (k = 0; k < trail->trail_length; k++)
1801 print_peer = element->peer;
1802 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1803 element = element->next;
1812 * Select the closest peer among two peers (which should not be same)
1813 * with respect to value and finger_table_index
1814 * NOTE: peer1 != peer2
1815 * @param peer1 First peer
1816 * @param peer2 Second peer
1817 * @param value Value relative to which we find the closest
1818 * @param is_predecessor Is value a predecessor or any other finger.
1819 * @return Closest peer among two peers.
1821 static struct GNUNET_PeerIdentity *
1822 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1823 struct GNUNET_PeerIdentity *peer2,
1825 unsigned int is_predecessor)
1827 struct GNUNET_PeerIdentity *closest_peer;
1829 if (1 == is_predecessor)
1831 closest_peer = select_closest_predecessor (peer1, peer2, value);
1836 closest_peer = select_closest_finger (peer1, peer2, value);
1838 return closest_peer;
1843 * Iterate over the list of all the trails of a finger. In case the first
1844 * friend to reach the finger has reached trail threshold or is congested,
1845 * then don't select it. In case there multiple available good trails to reach
1846 * to Finger, choose the one with shortest trail length.
1847 * Note: We use length as parameter. But we can use any other suitable parameter
1849 * @param finger Finger
1850 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1851 * and trail length. NULL in case none of the trails are free.
1853 static struct Selected_Finger_Trail *
1854 select_finger_trail (struct FingerInfo *finger)
1856 struct FriendInfo *friend;
1857 struct Trail *iterator;
1858 struct Selected_Finger_Trail *finger_trail;
1860 unsigned int flag = 0;
1863 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1864 GNUNET_assert (finger->trails_count > 0);
1866 for (i = 0; i < finger->trails_count; i++)
1868 iterator = &finger->trail_list[i];
1870 /* No trail stored at this index. */
1871 if (GNUNET_NO == iterator->is_present)
1874 GNUNET_assert (NULL !=
1876 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1877 &iterator->trail_head->peer)));
1879 /* First friend to reach trail is not free. */
1880 if (GNUNET_YES == is_friend_congested (friend))
1889 finger_trail->trail_length = iterator->trail_length;
1890 finger_trail->friend = *friend;
1891 finger_trail->trail_id = iterator->trail_id;
1893 else if (finger_trail->trail_length > iterator->trail_length)
1895 finger_trail->friend = *friend;
1896 finger_trail->trail_id = iterator->trail_id;
1897 finger_trail->trail_length = iterator->trail_length;
1901 /* All the first friend in all the trails to reach to finger are either
1902 congested or have crossed trail threshold. */
1903 if (j == finger->trails_count)
1906 return finger_trail;
1911 * Compare FINGER entry with current successor. If finger's first friend of all
1912 * its trail is not congested and has not crossed trail threshold, then check
1913 * if finger peer identity is closer to final_destination_finger_value than
1914 * current_successor. If yes then update current_successor.
1915 * @param current_successor[in/out]
1919 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1921 struct FingerInfo *finger;
1922 struct GNUNET_PeerIdentity *closest_peer;
1923 struct Selected_Finger_Trail *finger_trail;
1926 /* Iterate over finger table. */
1927 for (i = 0; i < MAX_FINGERS; i++)
1929 finger = &finger_table[i];
1931 if (GNUNET_NO == finger->is_present)
1934 /* If my identity is same as current closest peer then don't consider me*/
1936 GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1937 ¤t_closest_peer->best_known_destination))
1940 /* If I am my own finger, then ignore this finger. */
1941 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1945 /* If finger is a friend, then do nothing. As we have already checked
1946 * for each friend in compare_friend_and_current_successor(). */
1947 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1948 &finger->finger_identity)))
1953 /* Choose one of the trail to reach to finger. */
1954 finger_trail = select_finger_trail (finger);
1956 /* In case no trail found, ignore this finger. */
1957 if (NULL == finger_trail)
1960 closest_peer = select_closest_peer (&finger->finger_identity,
1961 ¤t_closest_peer->best_known_destination,
1962 current_closest_peer->destination_finger_value,
1963 current_closest_peer->is_predecessor);
1965 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1968 current_closest_peer->best_known_destination = finger->finger_identity;
1969 current_closest_peer->next_hop = finger_trail->friend.id;
1970 current_closest_peer->trail_id = finger_trail->trail_id;
1971 //GNUNET_free(finger_trail);//FIXME: where should we free the finger trail.
1979 * Compare friend entry with current successor.
1980 * If friend identity and current_successor is same, then do nothing.
1981 * If friend is not congested and has not crossed trail threshold, then check
1982 * if friend peer identity is closer to final_destination_finger_value than
1983 * current_successor. If yes then update current_successor.
1984 * @param cls closure
1985 * @param key current public key
1986 * @param value struct Closest_Peer
1987 * @return #GNUNET_YES if we should continue to iterate,
1988 * #GNUNET_NO if not.
1991 compare_friend_and_current_closest_peer (void *cls,
1992 const struct GNUNET_PeerIdentity *key,
1995 struct FriendInfo *friend = value;
1996 struct Closest_Peer *current_closest_peer = cls;
1997 struct GNUNET_PeerIdentity *closest_peer;
1999 /* Friend is either congested or has crossed threshold. */
2000 if (GNUNET_YES == is_friend_congested (friend))
2003 /* If current_closest_peer and friend identity are same, then do nothing.*/
2005 GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2006 ¤t_closest_peer->best_known_destination))
2009 closest_peer = select_closest_peer (&friend->id,
2010 ¤t_closest_peer->best_known_destination,
2011 current_closest_peer->destination_finger_value,
2012 current_closest_peer->is_predecessor);
2014 /* Is friend the closest successor? */
2015 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id, closest_peer))
2017 current_closest_peer->best_known_destination = friend->id;
2018 current_closest_peer->next_hop = friend->id;
2026 * Initialize current_successor to my_identity.
2027 * @param my_identity My peer identity
2028 * @return Updated closest_peer
2030 static struct Closest_Peer
2031 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2032 uint64_t destination_finger_value,
2033 unsigned int is_predecessor)
2035 struct Closest_Peer current_closest_peer;
2037 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2038 current_closest_peer.destination_finger_value = destination_finger_value;
2039 current_closest_peer.is_predecessor = is_predecessor;
2040 current_closest_peer.next_hop = my_identity;
2041 current_closest_peer.best_known_destination = my_identity;
2043 return current_closest_peer;
2048 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2049 * peer. It could be because of the logic we wrote here. Verify if its correct.
2050 * If not then return immediate_successor.
2052 * Find the successor for destination_finger_value among my_identity, my
2053 * friends and my fingers. Don't consider friends or fingers which are either
2054 * congested or have crossed the threshold.
2055 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2057 * @param destination_finger_value Peer closest to this value will be the next successor.
2058 * @param is_predecessor Are we looking for predecessor or finger?
2059 * @return Successor It is never NULL, in case none of friend or finger is closest,
2060 * then we return my_identity.
2062 static struct Closest_Peer
2063 find_successor (uint64_t destination_finger_value,
2064 unsigned int is_predecessor)
2066 struct Closest_Peer current_closest_peer;
2068 /* Initialize current_successor to my_identity. */
2069 current_closest_peer = init_current_successor (my_identity,
2070 destination_finger_value,
2073 /* Compare each friend entry with current_successor and update current_successor
2074 * with friend if its closest. */
2077 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2078 &compare_friend_and_current_closest_peer,
2079 ¤t_closest_peer));
2081 /* Compare each finger entry with current_successor and update current_successor
2082 * with finger if its closest. */
2083 compare_finger_and_current_successor (¤t_closest_peer);
2085 return current_closest_peer;
2090 * Construct a Put message and send it to target_peer.
2091 * @param key Key for the content
2092 * @param block_type Type of the block
2093 * @param options Routing options
2094 * @param desired_replication_level Desired replication count
2095 * @param best_known_dest Peer to which this message should reach eventually,
2096 * as it is best known destination to me.
2097 * @param intermediate_trail_id Trail id in case
2098 * @param target_peer Peer to which this message will be forwarded.
2099 * @param hop_count Number of hops traversed so far.
2100 * @param put_path_length Total number of peers in @a put_path
2101 * @param put_path Number of peers traversed so far
2102 * @param expiration_time When does the content expire
2103 * @param data Content to store
2104 * @param data_size Size of content @a data in bytes
2107 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2108 enum GNUNET_BLOCK_Type block_type,
2109 enum GNUNET_DHT_RouteOption options,
2110 uint32_t desired_replication_level,
2111 struct GNUNET_PeerIdentity best_known_dest,
2112 struct GNUNET_HashCode intermediate_trail_id,
2113 struct GNUNET_PeerIdentity *target_peer,
2115 uint32_t put_path_length,
2116 struct GNUNET_PeerIdentity *put_path,
2117 struct GNUNET_TIME_Absolute expiration_time,
2118 const void *data, size_t data_size)
2120 struct PeerPutMessage *ppm;
2121 struct P2PPendingMessage *pending;
2122 struct FriendInfo *target_friend;
2123 struct GNUNET_PeerIdentity *pp;
2124 struct GNUNET_PeerIdentity next_hop;
2128 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2129 sizeof (struct PeerPutMessage);
2131 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2133 put_path_length = 0;
2134 msize = data_size + sizeof (struct PeerPutMessage);
2137 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2143 /* This is the first call made from clients file. So, we should search for the
2145 if (NULL == target_peer)
2148 struct Closest_Peer successor;
2150 memcpy (&key_value, key, sizeof (uint64_t));
2151 key_value = GNUNET_ntohll (key_value);
2153 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2154 best_known_dest = successor.best_known_destination;
2155 next_hop = successor.next_hop;
2156 intermediate_trail_id = successor.trail_id;
2158 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2160 /* I am the destination but we have already done datacache_put in client file. */
2164 GNUNET_assert (NULL !=
2166 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2170 GNUNET_assert (NULL !=
2172 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2175 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2176 pending->timeout = expiration_time;
2177 ppm = (struct PeerPutMessage *) &pending[1];
2178 pending->msg = &ppm->header;
2179 ppm->header.size = htons (msize);
2180 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2181 ppm->options = htonl (options);
2182 ppm->block_type = htonl (block_type);
2183 ppm->hop_count = htonl (hop_count + 1);
2184 ppm->desired_replication_level = htonl (desired_replication_level);
2185 ppm->put_path_length = htonl (put_path_length);
2186 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2187 ppm->best_known_destination = best_known_dest;
2190 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2191 if (put_path_length != 0)
2193 memcpy (pp, put_path,
2194 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2196 memcpy (&pp[put_path_length], data, data_size);
2198 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2199 target_friend->pending_count++;
2200 process_friend_queue (target_friend);
2205 * Construct a Get message and send it to target_peer.
2206 * @param key Key for the content
2207 * @param block_type Type of the block
2208 * @param options Routing options
2209 * @param desired_replication_level Desired replication count
2210 * @param best_known_dest Peer which should get this message. Same as target peer
2211 * if best_known_dest is a friend else its a finger.
2212 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2213 * in case it is a finger else set to 0.
2214 * @param target_peer Peer to which this message will be forwarded.
2215 * @param hop_count Number of hops traversed so far.
2216 * @param data Content to store
2217 * @param data_size Size of content @a data in bytes
2218 * @param get_path_length Total number of peers in @a get_path
2219 * @param get_path Number of peers traversed so far
2222 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2223 enum GNUNET_BLOCK_Type block_type,
2224 enum GNUNET_DHT_RouteOption options,
2225 uint32_t desired_replication_level,
2226 struct GNUNET_PeerIdentity best_known_dest,
2227 struct GNUNET_HashCode intermediate_trail_id,
2228 struct GNUNET_PeerIdentity *target_peer,
2230 uint32_t get_path_length,
2231 struct GNUNET_PeerIdentity *get_path)
2233 struct PeerGetMessage *pgm;
2234 struct P2PPendingMessage *pending;
2235 struct FriendInfo *target_friend;
2236 struct GNUNET_PeerIdentity *gp;
2239 msize = sizeof (struct PeerGetMessage) +
2240 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2242 /* In this case we don't make get_path_length = 0, as we need get path to
2243 * return the message back to querying client. */
2244 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2250 /* This is the first time we got request from our own client file. */
2251 if (NULL == target_peer)
2254 struct Closest_Peer successor;
2256 memcpy (&key_value, key, sizeof (uint64_t));
2257 key_value = GNUNET_ntohll (key_value);
2258 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2260 best_known_dest = successor.best_known_destination;
2261 intermediate_trail_id = successor.trail_id;
2263 /* I am the destination. I have the data. */
2264 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2267 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2268 NULL, 0, 1, &my_identity, NULL,&my_identity);
2274 GNUNET_assert (NULL !=
2276 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2277 &successor.next_hop)));
2283 GNUNET_assert (NULL !=
2285 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); //FIXME: assertion fails.
2288 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2289 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2290 pending->importance = 0; /* FIXME */
2291 pgm = (struct PeerGetMessage *) &pending[1];
2292 pending->msg = &pgm->header;
2293 pgm->header.size = htons (msize);
2294 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2295 pgm->get_path_length = htonl (get_path_length);
2296 pgm->best_known_destination = best_known_dest;
2298 pgm->intermediate_trail_id = intermediate_trail_id;
2299 pgm->hop_count = htonl (hop_count + 1);
2300 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2302 if (get_path_length != 0)
2304 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2307 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2308 target_friend->pending_count++;
2309 process_friend_queue (target_friend);
2314 * Send the get result to requesting client.
2315 * @param key Key of the requested data.
2316 * @param type Block type
2317 * @param target_peer Next peer to forward the message to.
2318 * @param source_peer Peer which has the data for the key.
2319 * @param put_path_length Number of peers in @a put_path
2320 * @param put_path Path taken to put the data at its stored location.
2321 * @param get_path_length Number of peers in @a get_path
2322 * @param get_path Path taken to reach to the location of the key.
2323 * @param expiration When will this result expire?
2324 * @param data Payload to store
2325 * @param data_size Size of the @a data
2328 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2329 enum GNUNET_BLOCK_Type type,
2330 const struct GNUNET_PeerIdentity *target_peer,
2331 const struct GNUNET_PeerIdentity *source_peer,
2332 unsigned int put_path_length,
2333 const struct GNUNET_PeerIdentity *put_path,
2334 unsigned int get_path_length,
2335 const struct GNUNET_PeerIdentity *get_path,
2336 struct GNUNET_TIME_Absolute expiration,
2337 const void *data, size_t data_size)
2339 struct PeerGetResultMessage *get_result;
2340 struct GNUNET_PeerIdentity *paths;
2341 struct P2PPendingMessage *pending;
2342 struct FriendInfo *target_friend;
2343 int current_path_index;
2346 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2348 sizeof (struct PeerGetResultMessage);
2350 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2356 current_path_index = 0;
2357 if(get_path_length > 0)
2359 current_path_index = search_my_index(get_path, get_path_length);
2360 if (-1 == current_path_index)
2366 if (0 == current_path_index)
2368 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2369 get_path, put_path_length,
2370 put_path, type, data_size, data);
2374 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2375 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2376 pending->importance = 0;
2377 get_result = (struct PeerGetResultMessage *)&pending[1];
2378 pending->msg = &get_result->header;
2379 get_result->header.size = htons (msize);
2380 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2381 get_result->key = *key;
2382 get_result->querying_peer = *source_peer;
2383 get_result->expiration_time = expiration;
2384 get_result->get_path_length = htonl (get_path_length);
2385 get_result->put_path_length = htonl (put_path_length);
2386 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2387 memcpy (paths, put_path,
2388 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2389 memcpy (&paths[put_path_length], get_path,
2390 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2391 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2393 GNUNET_assert (NULL !=
2395 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2396 &get_path[current_path_index - 1])));
2397 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2398 target_friend->pending_count++;
2399 process_friend_queue (target_friend);
2404 * Randomly choose one of your friends (which is not congested and have not crossed
2405 * trail threshold) from the friend_peermap
2406 * @return Friend Randomly chosen friend.
2407 * NULL in case friend peermap is empty, or all the friends are either
2408 * congested or have crossed trail threshold.
2410 static struct FriendInfo *
2411 select_random_friend ()
2413 unsigned int current_size;
2416 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2417 struct GNUNET_PeerIdentity key_ret;
2418 struct FriendInfo *friend;
2420 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2423 if (0 == current_size)
2426 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2427 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2429 /* Iterate till you don't reach to index. */
2430 for (j = 0; j < index ; j++)
2431 GNUNET_assert (GNUNET_YES ==
2432 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2435 /* Reset the index in friend peermap to 0 as we reached to the end. */
2436 if (j == current_size)
2439 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2440 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2444 /* Get the friend stored at the index, j*/
2445 GNUNET_assert (GNUNET_YES ==
2446 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2448 (const void **)&friend));
2450 /* This friend is not congested and has not crossed trail threshold. */
2451 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2452 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2458 } while (j != index);
2460 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2466 * Compute 64 bit value of finger_identity corresponding to a finger index using
2468 * For all fingers, n.finger[i] = n + pow (2,i),
2469 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2470 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2471 * @param finger_index Index corresponding to which we calculate 64 bit value.
2472 * @return 64 bit value.
2475 compute_finger_identity_value (unsigned int finger_index)
2479 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2480 my_id64 = GNUNET_ntohll (my_id64);
2482 /* Are we looking for immediate predecessor? */
2483 if (PREDECESSOR_FINGER_ID == finger_index)
2484 return (my_id64 - 1);
2487 uint64_t add = (uint64_t)1 << finger_index;
2488 return (my_id64 + add);
2494 * Choose a random friend. Calculate the next finger identity to search,from
2495 * current_search_finger_index. Start looking for the trail to reach to
2496 * finger identity through this random friend.
2498 * @param cls closure for this task
2499 * @param tc the context under which the task is running
2502 send_find_finger_trail_message (void *cls,
2503 const struct GNUNET_SCHEDULER_TaskContext *tc)
2505 struct FriendInfo *target_friend;
2506 struct GNUNET_TIME_Relative next_send_time;
2507 struct GNUNET_HashCode trail_id;
2508 struct GNUNET_HashCode intermediate_trail_id;
2509 unsigned int is_predecessor;
2510 uint64_t finger_id_value;
2512 /* Schedule another send_find_finger_trail_message task. */
2513 next_send_time.rel_value_us =
2514 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
2515 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2516 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2517 find_finger_trail_task =
2518 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
2521 //FIXME: adding this check, so that once we found an entry for 0 and 64 then
2522 //don't schedule. Remove it afterwards.
2523 struct FingerInfo *succ;
2524 struct FingerInfo *pred;
2525 succ = &finger_table[0];
2526 pred = &finger_table[PREDECESSOR_FINGER_ID];
2528 if((GNUNET_YES == succ->is_present) &&
2529 (GNUNET_YES == pred->is_present))
2532 /* No space in my routing table. (Source and destination peers also store entries
2533 * in their routing table). */
2534 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2538 target_friend = select_random_friend ();
2539 if (NULL == target_friend)
2544 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2546 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2551 /* Generate a unique trail id for trail we are trying to setup. */
2552 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2553 &trail_id, sizeof (trail_id));
2554 memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2556 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2557 target_friend->id, target_friend, 0, NULL,
2558 is_predecessor, trail_id,
2559 intermediate_trail_id);
2564 * In case there are already maximum number of possible trails to reach to a
2565 * finger, then check if the new trail's length is lesser than any of the
2567 * If yes then replace that old trail by new trail.
2569 * Note: Here we are taking length as a parameter to choose the best possible
2570 * trail, but there could be other parameters also like:
2571 * 1. duration of existence of a trail - older the better.
2572 * 2. if the new trail is completely disjoint than the
2573 * other trails, then may be choosing it is better.
2575 * @param existing_finger
2576 * @param new_finger_trail
2577 * @param new_finger_trail_length
2578 * @param new_finger_trail_id
2581 select_and_replace_trail (struct FingerInfo *existing_finger,
2582 const struct GNUNET_PeerIdentity *new_trail,
2583 unsigned int new_trail_length,
2584 struct GNUNET_HashCode new_trail_id)
2586 struct Trail *trail_list_iterator;
2587 unsigned int largest_trail_length;
2588 unsigned int largest_trail_index;
2589 struct Trail_Element *trail_element;
2592 largest_trail_length = new_trail_length;
2593 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2595 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2597 for (i = 0; i < existing_finger->trails_count; i++)
2599 trail_list_iterator = &existing_finger->trail_list[i];
2600 if (trail_list_iterator->trail_length > largest_trail_length)
2602 largest_trail_length = trail_list_iterator->trail_length;
2603 largest_trail_index = i;
2607 /* New trail is not better than existing ones. Send trail teardown. */
2608 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2610 struct GNUNET_PeerIdentity next_hop;
2612 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2613 GDS_ROUTING_remove_trail (new_trail_id);
2614 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2615 GDS_ROUTING_SRC_TO_DEST,
2620 /* Send trail teardown message across the replaced trail. */
2621 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2622 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2623 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2624 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2625 GDS_ROUTING_SRC_TO_DEST,
2626 replace_trail->trail_head->peer);
2627 /* Free the trail. */
2628 while (NULL != (trail_element = replace_trail->trail_head))
2630 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2631 replace_trail->trail_tail, trail_element);
2632 GNUNET_free_non_null (trail_element);
2635 /* Add new trial at that location. */
2636 replace_trail->is_present = GNUNET_YES;
2637 replace_trail->trail_length = new_trail_length;
2638 replace_trail->trail_id = new_trail_id;
2639 //FIXME: Do we need to add pointers for head and tail.
2641 while (i < new_trail_length)
2643 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2644 element->peer = new_trail[i];
2646 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2647 replace_trail->trail_tail,
2654 * Check if the new trail to reach to finger is unique or do we already have
2655 * such a trail present for finger.
2656 * @param existing_finger Finger identity
2657 * @param new_trail New trail to reach @a existing_finger
2658 * @param trail_length Total number of peers in new_trail.
2659 * @return #GNUNET_YES if the new trail is unique
2660 * #GNUNET_NO if same trail is already present.
2663 is_new_trail_unique (struct FingerInfo *existing_finger,
2664 const struct GNUNET_PeerIdentity *new_trail,
2665 unsigned int trail_length)
2667 struct Trail *trail_list_iterator;
2668 struct Trail_Element *trail_element;
2671 int trail_unique = GNUNET_NO;
2673 GNUNET_assert (existing_finger->trails_count > 0);
2675 /* Iterate over list of trails. */
2676 for (i = 0; i < existing_finger->trails_count; i++)
2678 trail_list_iterator = &existing_finger->trail_list[i];
2679 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2681 /* New trail and existing trail length are not same. */
2682 if (trail_list_iterator->trail_length != trail_length)
2684 trail_unique = GNUNET_YES;
2688 trail_element = trail_list_iterator->trail_head;
2689 for (j = 0; j < trail_list_iterator->trail_length; j++)
2691 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2692 &trail_element->peer))
2694 trail_unique = GNUNET_YES;
2697 trail_element = trail_element->next;
2700 trail_unique = GNUNET_NO;
2703 return trail_unique;
2708 * Add a new trail to existing finger. This function is called only when finger
2709 * is not my own identity or a friend.
2710 * @param existing_finger Finger
2711 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2712 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2713 * @param new_finger_trail_id Unique identifier of the trail.
2716 add_new_trail (struct FingerInfo *existing_finger,
2717 const struct GNUNET_PeerIdentity *new_trail,
2718 unsigned int new_trail_length,
2719 struct GNUNET_HashCode new_trail_id)
2721 struct Trail *trail_list_iterator;
2722 struct FriendInfo *first_friend;
2725 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2731 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2732 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2733 trail_list_iterator->trail_id = new_trail_id;
2734 trail_list_iterator->trail_length = new_trail_length;
2735 existing_finger->trails_count++;
2736 trail_list_iterator->is_present = GNUNET_YES;
2738 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2739 &existing_finger->finger_identity)));
2740 /* If finger is a friend then we never call this function. */
2741 GNUNET_assert (new_trail_length > 0);
2743 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2745 first_friend->trails_count++;
2747 for (i = 0; i < new_trail_length; i++)
2749 struct Trail_Element *element;
2751 element = GNUNET_new (struct Trail_Element);
2752 element->peer = new_trail[i];
2753 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2754 trail_list_iterator->trail_tail,
2757 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2763 * FIXME Check if this function is called for opposite direction if yes then
2764 * take it as parameter.
2765 * Get the next hop to send trail teardown message from routing table and
2766 * then delete the entry from routing table. Send trail teardown message for a
2767 * specific trail of a finger.
2768 * @param finger Finger whose trail is to be removed.
2769 * @param trail List of peers in trail from me to a finger, NOT including
2773 send_trail_teardown (struct FingerInfo *finger,
2774 struct Trail *trail)
2776 struct FriendInfo *friend;
2777 struct GNUNET_PeerIdentity *next_hop;
2779 GNUNET_assert (NULL !=
2780 (next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2781 GDS_ROUTING_SRC_TO_DEST)));
2783 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2786 GNUNET_assert (trail->is_present == GNUNET_YES);
2788 /* Finger is not a friend. */
2789 if (trail->trail_length > 0)
2791 GNUNET_assert (NULL != (friend =
2792 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2793 &trail->trail_head->peer)));
2797 GNUNET_assert (NULL != (friend =
2798 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2799 &finger->finger_identity)));
2802 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2803 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2804 friend->trails_count--;
2805 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2806 GDS_ROUTING_SRC_TO_DEST,
2812 * Send trail teardown message across all the trails to reach to finger.
2813 * @param finger Finger whose all the trail should be freed.
2816 send_all_finger_trails_teardown (struct FingerInfo *finger)
2820 for (i = 0; i < finger->trails_count; i++)
2822 struct Trail *trail;
2824 trail = &finger->trail_list[i];
2825 GNUNET_assert (trail->is_present == GNUNET_YES);
2826 send_trail_teardown (finger, trail);
2827 trail->is_present = GNUNET_NO;
2833 * Free a specific trail
2834 * @param trail List of peers to be freed.
2837 free_trail (struct Trail *trail)
2839 struct Trail_Element *trail_element;
2841 while (NULL != (trail_element = trail->trail_head))
2843 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2846 GNUNET_free_non_null (trail_element);
2848 trail->trail_head = NULL;
2849 trail->trail_tail = NULL;
2854 * Free finger and its trail.
2855 * @param finger Finger to be freed.
2858 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2860 struct Trail *trail;
2863 /* Free all the trails to reach to finger */
2864 for (i = 0; i < finger->trails_count; i++)
2866 trail = &finger->trail_list[i];
2867 //FIXME: Check if there are any missing entry in this list because of
2868 // how we insert. If not then no need of this check.
2869 if (GNUNET_NO == trail->is_present)
2872 if (trail->trail_length > 0)
2876 trail->is_present = GNUNET_NO;
2879 finger->is_present = GNUNET_NO;
2880 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2885 * FIXME: ensure that you are not adding any trail to reach to a friend which
2886 * is a finger. Also decide on should you increment trails count of a friend
2887 * which is also a finger.
2888 * Add a new entry in finger table at finger_table_index.
2889 * In case finger identity is me or a friend, then don't add a trail. NOTE
2890 * trail length to reach to a finger can be 0 only if the finger is a friend
2892 * In case a finger is a friend, then increment the trails count of the friend.
2893 * @param finger_identity Peer Identity of new finger
2894 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2895 * @param finger_trail_length Total number of peers in @a finger_trail.
2896 * @param trail_id Unique identifier of the trail.
2897 * @param finger_table_index Index in finger table.
2900 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2901 const struct GNUNET_PeerIdentity *finger_trail,
2902 unsigned int finger_trail_length,
2903 struct GNUNET_HashCode trail_id,
2904 unsigned int finger_table_index)
2906 struct FingerInfo *new_entry;
2907 struct FriendInfo *first_trail_hop;
2908 struct Trail *trail;
2911 new_entry = GNUNET_new (struct FingerInfo);
2912 new_entry->finger_identity = finger_identity;
2913 new_entry->finger_table_index = finger_table_index;
2914 new_entry->is_present = GNUNET_YES;
2916 /* If the new entry is my own identity. */
2917 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2919 new_entry->trails_count = 0;
2920 finger_table[finger_table_index] = *new_entry;
2921 GNUNET_free (new_entry);
2925 /* If finger is a friend, then we don't actually have a trail.
2926 * Just a trail id */
2927 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2930 new_entry->trail_list[0].trail_id = trail_id;
2931 new_entry->trails_count = 1;
2932 new_entry->trail_list[0].is_present = GNUNET_YES;
2933 new_entry->trail_list[0].trail_length = 0;
2934 new_entry->trail_list[0].trail_head = NULL;
2935 new_entry->trail_list[0].trail_tail = NULL;
2936 finger_table[finger_table_index] = *new_entry;
2937 GNUNET_assert (NULL !=
2939 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2940 &finger_identity)));
2942 first_trail_hop->trails_count++;
2943 GNUNET_free (new_entry);
2947 /* finger trail length can be 0 only in case if finger is my identity or
2948 finger is friend. We should never reach here. */
2949 GNUNET_assert (finger_trail_length > 0);
2951 GNUNET_assert (NULL !=
2953 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2954 &finger_trail[0])));
2955 new_entry->trails_count = 1;
2956 first_trail_hop->trails_count++;
2958 /* Copy the finger trail into trail. */
2959 trail = GNUNET_new (struct Trail);
2960 while (i < finger_trail_length)
2962 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2964 element->next = NULL;
2965 element->prev = NULL;
2966 element->peer = finger_trail[i];
2967 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2973 /* Add trail to trail list. */
2974 new_entry->trail_list[0].trail_head = trail->trail_head;
2975 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2976 new_entry->trail_list[0].trail_length = finger_trail_length;
2977 new_entry->trail_list[0].trail_id = trail_id;
2978 new_entry->trail_list[0].is_present = GNUNET_YES;
2979 finger_table[finger_table_index] = *new_entry;
2980 //GNUNET_free (new_entry);
2981 //GNUNET_free (trail);
2987 * Scan the trail to check if there is any other friend in the trail other than
2988 * first hop. If yes then shortcut the trail, send trail compression message to
2989 * peers which are no longer part of trail and send back the updated trail
2990 * and trail_length to calling function.
2991 * @param finger_identity Finger whose trail we will scan.
2992 * @param finger_trail [in, out] Trail to reach from source to finger,
2993 * @param finger_trail_length Total number of peers in original finger_trail.
2994 * @param finger_trail_id Unique identifier of the finger trail.
2995 * @return updated trail length in case we shortcut the trail, else original
2998 static struct GNUNET_PeerIdentity *
2999 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
3000 const struct GNUNET_PeerIdentity *trail,
3001 unsigned int trail_length,
3002 struct GNUNET_HashCode trail_id,
3003 int *new_trail_length)
3005 struct FriendInfo *target_friend;
3006 struct GNUNET_PeerIdentity *new_trail;
3009 /* I am my own finger. */
3010 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3012 *new_trail_length = 0;
3016 if (0 == trail_length)
3018 *new_trail_length = 0;
3022 /* If finger identity is a friend. */
3023 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3025 *new_trail_length = 0;
3027 /* If there is trail to reach this finger/friend */
3028 if (trail_length > 0)
3030 /* Finger is your first friend. */
3031 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3032 GNUNET_assert (NULL !=
3034 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3038 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3039 trail_id, finger_identity,
3045 /* For other cases, when its neither a friend nor my own identity.*/
3046 for (i = trail_length - 1; i > 0; i--)
3048 /* If the element at this index in trail is a friend. */
3049 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3051 struct FriendInfo *target_friend;
3054 GNUNET_assert (NULL !=
3056 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3058 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3059 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3064 /* Copy the trail from index i to index (trail_length -1) into a new trail
3065 * and update new trail length */
3066 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3067 while (i < trail_length)
3069 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3073 *new_trail_length = j+1;
3074 GNUNET_assert((j+1) == (trail_length - 1)); //FIXME: remove it afterwards.
3079 /* If we did not compress the trail, return the original trail back.*/
3080 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3081 *new_trail_length = trail_length;
3082 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3088 * Periodic task to verify current successor. There can be multiple trails to reach
3089 * to successor, choose the shortest one and send verify successor message
3090 * across that trail.
3091 * @param cls closure for this task
3092 * @param tc the context under which the task is running
3095 send_verify_successor_message (void *cls,
3096 const struct GNUNET_SCHEDULER_TaskContext *tc)
3098 struct FingerInfo *current_successor;
3099 struct GNUNET_TIME_Relative next_send_time;
3100 struct GNUNET_PeerIdentity *trail;
3101 struct GNUNET_HashCode trail_id;
3102 unsigned int trail_length;
3104 /* Schedule another send_verify_successor_message. */
3105 next_send_time.rel_value_us =
3106 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
3107 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3108 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
3109 send_verify_successor_task =
3110 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3113 /* We should never be our own successor. */
3115 GNUNET_CRYTPO_cmp_peer_identity (&my_identity,
3116 ¤t_successor->finger_identity));
3119 trail = get_shortest_trail (successor, &trail_length, &trail_id);
3121 if(trail_length > 0)
3134 send_verify_successor_message (void *cls,
3135 const struct GNUNET_SCHEDULER_TaskContext *tc)
3137 struct FriendInfo *target_friend;
3138 struct GNUNET_HashCode trail_id;
3140 struct GNUNET_TIME_Relative next_send_time;
3141 struct Trail *trail;
3142 struct Trail_Element *element;
3143 unsigned int trail_length;
3145 struct FingerInfo *successor;
3147 /* Schedule another send_find_finger_trail_message task. */
3148 next_send_time.rel_value_us =
3149 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3150 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3151 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3152 send_verify_successor_task =
3153 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3156 successor = &finger_table[0];
3158 trail = &successor->trail_list[i];
3160 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3161 &successor->finger_identity))
3164 /* Trail stored at this index. */
3165 GNUNET_assert (GNUNET_YES == trail->is_present);
3167 trail_id = trail->trail_id;
3168 trail_length = trail->trail_length;
3170 if (trail_length > 0)
3172 /* Copy the trail into peer list. */
3173 struct GNUNET_PeerIdentity peer_list[trail_length];
3175 element = trail->trail_head;
3176 while (j < trail_length)
3178 peer_list[j] = element->peer;
3179 element = element->next;
3183 GNUNET_assert (NULL != (target_friend =
3184 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3186 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3187 successor->finger_identity,
3188 trail_id, peer_list, trail_length,
3194 GNUNET_assert (NULL != (target_friend =
3195 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3196 &successor->finger_identity)));
3197 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3198 successor->finger_identity,
3207 * Update the current search finger index.
3210 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3211 unsigned int finger_table_index)
3213 struct FingerInfo *successor;
3215 if (finger_table_index != current_search_finger_index)
3218 successor = &finger_table[0];
3219 GNUNET_assert (GNUNET_YES == successor->is_present);
3221 /* We were looking for immediate successor. */
3222 if (0 == current_search_finger_index)
3224 /* Start looking for immediate predecessor. */
3225 current_search_finger_index = PREDECESSOR_FINGER_ID;
3227 /* If I am not my own successor, then send a verify successor message. */
3228 //if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3230 //send_verify_successor_message (successor);
3233 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3235 if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task)
3236 send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3242 current_search_finger_index = current_search_finger_index - 1;
3248 * Get the first set bit in val.
3250 * @return Position of first bit set.
3253 find_set_bit(uint64_t val)
3270 * Calculate finger_table_index from initial 64 bit finger identity value that
3271 * we send in trail setup message.
3272 * @param ultimate_destination_finger_value Value that we calculated from our
3273 * identity and finger_table_index.
3274 * @param is_predecessor Is the entry for predecessor or not?
3275 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3276 * finger_table_index > PREDECESSOR_FINGER_ID ,
3277 * if no valid finger_table_index is found.
3280 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3281 unsigned int is_predecessor)
3285 unsigned int finger_table_index;
3287 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3288 my_id64 = GNUNET_ntohll (my_id64);
3290 /* Is this a predecessor finger? */
3291 if (1 == is_predecessor)
3293 diff = my_id64 - ultimate_destination_finger_value;
3295 finger_table_index = PREDECESSOR_FINGER_ID;
3297 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3302 diff = ultimate_destination_finger_value - my_id64;
3303 finger_table_index = find_set_bit(diff);
3306 return finger_table_index;
3311 * Remove finger and its associated data structures from finger table.
3312 * @param finger Finger to be removed.
3315 remove_existing_finger (struct FingerInfo *existing_finger,
3316 unsigned int finger_table_index)
3318 struct FingerInfo *finger;
3320 finger = &finger_table[finger_table_index];
3321 GNUNET_assert (GNUNET_YES == finger->is_present);
3323 /* If I am my own finger, then we have no trails. */
3324 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3327 finger->is_present = GNUNET_NO;
3328 memset ((void *)&finger_table[finger_table_index], 0,
3329 sizeof (finger_table[finger_table_index]));
3333 /* For all other fingers, send trail teardown across all the trails to reach
3334 finger, and free the finger. */
3335 send_all_finger_trails_teardown (finger);
3336 free_finger (finger, finger_table_index);
3342 * Check if there is already an entry in finger_table at finger_table_index.
3343 * We get the finger_table_index from 64bit finger value we got from the network.
3344 * -- If yes, then select the closest finger.
3345 * -- If new and existing finger are same, then check if you can store more
3347 * -- If yes then add trail, else keep the best trails to reach to the
3349 * -- If the new finger is closest, remove the existing entry, send trail
3350 * teardown message across all the trails to reach the existing entry.
3351 * Add the new finger.
3352 * -- If new and existing finger are different, and existing finger is closest
3354 * -- Update current_search_finger_index.
3355 * @param finger_identity Peer Identity of new finger
3356 * @param finger_trail Trail to reach the new finger
3357 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3358 * @param is_predecessor Is this entry for predecessor in finger_table?
3359 * @param finger_value 64 bit value of finger identity that we got from network.
3360 * @param finger_trail_id Unique identifier of @finger_trail.
3363 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3364 const struct GNUNET_PeerIdentity *finger_trail,
3365 unsigned int finger_trail_length,
3366 unsigned int is_predecessor,
3367 uint64_t finger_value,
3368 struct GNUNET_HashCode finger_trail_id)
3370 struct FingerInfo *existing_finger;
3371 struct GNUNET_PeerIdentity *closest_peer;
3372 struct FingerInfo *successor;
3373 int updated_finger_trail_length;
3374 unsigned int finger_table_index;
3376 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3377 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3379 /* Invalid finger_table_index. */
3380 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3382 GNUNET_break_op (0);
3386 /* New entry same as successor. */
3387 if ((0 != finger_table_index) &&
3388 (PREDECESSOR_FINGER_ID != finger_table_index))
3390 successor = &finger_table[0];
3391 GNUNET_assert (GNUNET_YES == successor->is_present);
3392 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3393 &successor->finger_identity))
3395 current_search_finger_index = 0;
3400 existing_finger = &finger_table[finger_table_index];
3402 /* No entry present in finger_table for given finger map index. */
3403 if (GNUNET_NO == existing_finger->is_present)
3405 struct GNUNET_PeerIdentity *updated_trail;
3407 /* Shorten the trail if possible. */
3408 updated_finger_trail_length = finger_trail_length;
3410 scan_and_compress_trail (finger_identity, finger_trail,
3411 finger_trail_length, finger_trail_id,
3412 &updated_finger_trail_length);
3414 add_new_finger (finger_identity, updated_trail,
3415 updated_finger_trail_length,
3416 finger_trail_id, finger_table_index);
3417 update_current_search_finger_index (finger_identity,
3418 finger_table_index);
3423 /* If existing entry and finger identity are not same. */
3424 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3427 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3432 /* If the new finger is the closest peer. */
3433 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3435 struct GNUNET_PeerIdentity *updated_trail;
3436 /* Shorten the trail if possible. */
3437 updated_finger_trail_length = finger_trail_length;
3439 scan_and_compress_trail (finger_identity, finger_trail,
3440 finger_trail_length, finger_trail_id,
3441 &updated_finger_trail_length);
3442 remove_existing_finger (existing_finger, finger_table_index);
3443 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3444 finger_trail_id, finger_table_index);
3449 /* Existing finger is the closest one. We need to send trail teardown
3450 across the trail setup in routing table of all the peers. */
3451 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3453 if (finger_trail_length > 0)
3454 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3455 GDS_ROUTING_SRC_TO_DEST,
3458 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3459 GDS_ROUTING_SRC_TO_DEST,
3463 /* Store the successor for path tracking */
3464 if (track_topology && (NULL != GDS_stats) && (0 == finger_table_index))
3470 my_id_str = GNUNET_strdup (GNUNET_i2s (&my_identity));
3471 succ_id_str = GNUNET_strdup (GNUNET_i2s
3472 (&existing_finger->finger_identity));
3473 GNUNET_asprintf (&key, "XDHT:0:%.4s:%.4s", my_id_str, succ_id_str);
3474 GNUNET_free (my_id_str);
3475 GNUNET_free (succ_id_str);
3476 GNUNET_STATISTICS_update (GDS_stats, "key", 1, 0);
3483 /* If both new and existing entry are same as my_identity, then do nothing. */
3484 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3489 /* If the existing finger is not a friend. */
3491 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3492 &existing_finger->finger_identity))
3494 struct GNUNET_PeerIdentity *updated_trail;
3496 /* Shorten the trail if possible. */
3497 updated_finger_trail_length = finger_trail_length;
3499 scan_and_compress_trail (finger_identity, finger_trail,
3500 finger_trail_length, finger_trail_id,
3501 &updated_finger_trail_length);
3502 /* If there is space to store more trails. */
3503 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3504 add_new_trail (existing_finger, updated_trail,
3505 updated_finger_trail_length, finger_trail_id);
3507 select_and_replace_trail (existing_finger, updated_trail,
3508 updated_finger_trail_length, finger_trail_id);
3512 update_current_search_finger_index (finger_identity, finger_table_index);
3517 * Core handler for P2P put messages.
3518 * @param cls closure
3519 * @param peer sender of the request
3520 * @param message message
3521 * @return #GNUNET_OK to keep the connection open,
3522 * #GNUNET_SYSERR to close it (signal serious error)
3525 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3526 const struct GNUNET_MessageHeader *message)
3528 struct PeerPutMessage *put;
3529 struct GNUNET_PeerIdentity *put_path;
3530 struct GNUNET_PeerIdentity best_known_dest;
3531 struct GNUNET_HashCode intermediate_trail_id;
3532 struct GNUNET_PeerIdentity *next_hop;
3533 enum GNUNET_DHT_RouteOption options;
3534 struct GNUNET_HashCode test_key;
3538 size_t payload_size;
3541 msize = ntohs (message->size);
3542 if (msize < sizeof (struct PeerPutMessage))
3544 GNUNET_break_op (0);
3548 put = (struct PeerPutMessage *) message;
3549 putlen = ntohl (put->put_path_length);
3552 sizeof (struct PeerPutMessage) +
3553 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3555 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3557 GNUNET_break_op (0);
3561 best_known_dest = put->best_known_destination;
3562 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3563 payload = &put_path[putlen];
3564 options = ntohl (put->options);
3565 intermediate_trail_id = put->intermediate_trail_id;
3567 payload_size = msize - (sizeof (struct PeerPutMessage) +
3568 putlen * sizeof (struct GNUNET_PeerIdentity));
3570 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3571 payload, payload_size, &test_key))
3574 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3576 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3577 GNUNET_break_op (0);
3578 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3579 "PUT with key `%s' for block with key %s\n",
3580 put_s, GNUNET_h2s_full (&test_key));
3581 GNUNET_free (put_s);
3586 GNUNET_break_op (0);
3589 /* cannot verify, good luck */
3593 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3595 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3596 ntohl (put->block_type),
3598 NULL, 0, /* bloom filer */
3599 NULL, 0, /* xquery */
3600 payload, payload_size))
3602 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3603 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3606 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3607 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3608 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3609 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3610 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3611 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3613 GNUNET_break_op (0);
3618 /* extend 'put path' by sender */
3619 struct GNUNET_PeerIdentity pp[putlen + 1];
3620 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3622 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3629 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3630 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3632 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3633 GDS_ROUTING_SRC_TO_DEST);
3634 if (NULL == next_hop)
3636 GNUNET_STATISTICS_update (GDS_stats,
3637 gettext_noop ("# Next hop to forward the packet not found "
3638 "trail setup request, packet dropped."),
3640 return GNUNET_SYSERR;
3645 struct Closest_Peer successor;
3646 key_value = GNUNET_ntohll (key_value);
3647 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3649 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3650 *next_hop = successor.next_hop;
3651 intermediate_trail_id = successor.trail_id;
3652 best_known_dest = successor.best_known_destination;
3655 GDS_CLIENTS_process_put (options,
3656 ntohl (put->block_type),
3657 ntohl (put->hop_count),
3658 ntohl (put->desired_replication_level),
3660 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3665 /* I am the final destination */
3666 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3668 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3669 &(put->key),putlen, pp, ntohl (put->block_type),
3670 payload_size, payload);
3674 GDS_NEIGHBOURS_send_put (&put->key,
3675 ntohl (put->block_type),ntohl (put->options),
3676 ntohl (put->desired_replication_level),
3677 best_known_dest, intermediate_trail_id, next_hop,
3678 ntohl (put->hop_count), putlen, pp,
3679 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3680 payload, payload_size);
3687 * Core handler for p2p get requests.
3689 * @param cls closure
3690 * @param peer sender of the request
3691 * @param message message
3692 * @return #GNUNET_OK to keep the connection open,
3693 * #GNUNET_SYSERR to close it (signal serious error)
3696 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3697 const struct GNUNET_MessageHeader *message)
3699 const struct PeerGetMessage *get;
3700 const struct GNUNET_PeerIdentity *get_path;
3701 struct GNUNET_PeerIdentity best_known_dest;
3702 struct GNUNET_HashCode intermediate_trail_id;
3703 struct GNUNET_PeerIdentity *next_hop;
3704 uint32_t get_length;
3708 msize = ntohs (message->size);
3709 if (msize < sizeof (struct PeerGetMessage))
3711 GNUNET_break_op (0);
3715 get = (const struct PeerGetMessage *)message;
3716 get_length = ntohl (get->get_path_length);
3717 best_known_dest = get->best_known_destination;
3718 intermediate_trail_id = get->intermediate_trail_id;
3719 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3722 sizeof (struct PeerGetMessage) +
3723 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3725 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3727 GNUNET_break_op (0);
3731 /* Add sender to get path */
3732 struct GNUNET_PeerIdentity gp[get_length + 1];
3734 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3735 gp[get_length] = *peer;
3736 get_length = get_length + 1;
3738 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3739 key_value = GNUNET_ntohll (key_value);
3741 /* I am not the final destination. I am part of trail to reach final dest. */
3742 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3744 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3745 GDS_ROUTING_SRC_TO_DEST);
3746 if (NULL == next_hop)
3748 GNUNET_STATISTICS_update (GDS_stats,
3749 gettext_noop ("# Next hop to forward the packet not found "
3750 "GET request, packet dropped."),
3752 return GNUNET_SYSERR;
3757 struct Closest_Peer successor;
3759 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3760 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3761 *next_hop = successor.next_hop;
3762 best_known_dest = successor.best_known_destination;
3763 intermediate_trail_id = successor.trail_id;
3766 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3767 get->desired_replication_level, get->get_path_length,
3769 /* I am the final destination. */
3770 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3772 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3774 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3775 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3776 get_length = get_length + 1;
3777 /* FIXME: here it may happen that we find our identity closest to key, but
3778 we don't have the data. then in that case, we should forward the packet
3779 to the next closest peer. */
3780 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3781 get_length, final_get_path,
3782 &final_get_path[get_length-2], &my_identity);
3786 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3787 get->desired_replication_level, best_known_dest,
3788 intermediate_trail_id, next_hop, 0,
3796 * Core handler for get result
3797 * @param cls closure
3798 * @param peer sender of the request
3799 * @param message message
3800 * @return #GNUNET_OK to keep the connection open,
3801 * #GNUNET_SYSERR to close it (signal serious error)
3804 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3805 const struct GNUNET_MessageHeader *message)
3807 const struct PeerGetResultMessage *get_result;
3808 const struct GNUNET_PeerIdentity *get_path;
3809 const struct GNUNET_PeerIdentity *put_path;
3810 const void *payload;
3811 size_t payload_size;
3813 unsigned int getlen;
3814 unsigned int putlen;
3815 int current_path_index;
3817 msize = ntohs (message->size);
3818 if (msize < sizeof (struct PeerGetResultMessage))
3820 GNUNET_break_op (0);
3824 get_result = (const struct PeerGetResultMessage *)message;
3825 getlen = ntohl (get_result->get_path_length);
3826 putlen = ntohl (get_result->put_path_length);
3829 sizeof (struct PeerGetResultMessage) +
3830 getlen * sizeof (struct GNUNET_PeerIdentity) +
3831 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3833 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3835 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3837 GNUNET_break_op (0);
3841 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3842 get_path = &put_path[putlen];
3843 payload = (const void *) &get_path[getlen];
3844 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3845 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3847 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3849 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3850 getlen, get_path, putlen,
3851 put_path, get_result->type, payload_size, payload);
3856 current_path_index = search_my_index (get_path, getlen);
3857 if (-1 == current_path_index )
3860 return GNUNET_SYSERR;
3862 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3863 &get_path[current_path_index - 1],
3864 &(get_result->querying_peer), putlen, put_path,
3865 getlen, get_path, get_result->expiration_time,
3866 payload, payload_size);
3869 return GNUNET_SYSERR;
3874 * Find the next hop to pass trail setup message. First find the local best known
3875 * hop from your own identity, friends and finger. If you were part of trail,
3876 * then get the next hop from routing table. Compare next_hop from routing table
3877 * and local best known hop, and return the closest one to final_dest_finger_val
3878 * @param final_dest_finger_val 64 bit value of finger identity
3879 * @param intermediate_trail_id If you are part of trail to reach to some other
3880 * finger, then it is the trail id to reach to
3881 * that finger, else set to 0.
3882 * @param is_predecessor Are we looking for closest successor or predecessor.
3883 * @param current_dest In case you are part of trail, then finger to which
3884 * we should forward the message. Else my own identity
3885 * @return Closest Peer for @a final_dest_finger_val
3887 static struct Closest_Peer
3888 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3889 struct GNUNET_HashCode intermediate_trail_id,
3890 unsigned int is_predecessor,
3891 struct GNUNET_PeerIdentity prev_hop,
3892 struct GNUNET_PeerIdentity source,
3893 struct GNUNET_PeerIdentity *current_dest)
3895 struct Closest_Peer peer;
3897 /* Find a local best known peer. */
3898 peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3900 /* Am I just a part of a trail towards a finger (current_destination)? */
3901 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest)))
3903 /* Select best successor among one found locally and current_destination
3904 * that we got from network.*/
3905 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3908 struct GNUNET_PeerIdentity *closest_peer;
3909 struct GNUNET_PeerIdentity *local_best_known_dest;
3910 local_best_known_dest = GNUNET_new(struct GNUNET_PeerIdentity);
3911 memcpy(local_best_known_dest, &peer.best_known_destination, sizeof(struct GNUNET_PeerIdentity));
3913 closest_peer = select_closest_peer (local_best_known_dest,
3915 final_dest_finger_val,
3918 GNUNET_free(local_best_known_dest);
3919 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3920 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3922 struct GNUNET_PeerIdentity *next_hop;
3923 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3924 GDS_ROUTING_SRC_TO_DEST);
3925 GNUNET_assert (NULL != next_hop);
3927 peer.next_hop = *next_hop;
3928 peer.best_known_destination = *current_dest;
3929 peer.trail_id = intermediate_trail_id;
3938 * Core handle for PeerTrailSetupMessage.
3939 * @param cls closure
3940 * @param message message
3941 * @param peer peer identity this notification is about
3942 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3945 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3946 const struct GNUNET_MessageHeader *message)
3948 const struct PeerTrailSetupMessage *trail_setup;
3949 const struct GNUNET_PeerIdentity *trail_peer_list;
3950 struct GNUNET_PeerIdentity current_dest;
3951 struct FriendInfo *target_friend;
3952 struct GNUNET_PeerIdentity source;
3953 uint64_t final_dest_finger_val;
3954 struct GNUNET_HashCode intermediate_trail_id;
3955 struct GNUNET_HashCode trail_id;
3956 unsigned int is_predecessor;
3957 uint32_t trail_length;
3960 msize = ntohs (message->size);
3961 if (msize < sizeof (struct PeerTrailSetupMessage))
3963 GNUNET_break_op (0);
3964 return GNUNET_SYSERR;
3967 trail_setup = (const struct PeerTrailSetupMessage *) message;
3968 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3969 sizeof (struct GNUNET_PeerIdentity);
3970 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3971 sizeof (struct GNUNET_PeerIdentity) != 0)
3973 GNUNET_break_op (0);
3977 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3978 current_dest = trail_setup->best_known_destination;
3979 trail_id = trail_setup->trail_id;
3980 final_dest_finger_val =
3981 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3982 source = trail_setup->source_peer;
3983 is_predecessor = ntohl (trail_setup->is_predecessor);
3984 intermediate_trail_id = trail_setup->intermediate_trail_id;
3986 /* If I was the source and got the message back, then set trail length to 0.*/
3987 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3992 /* Is my routing table full? */
3993 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3995 GNUNET_assert (NULL !=
3997 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
3998 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
3999 my_identity, is_predecessor,
4000 trail_peer_list, trail_length,
4001 trail_id, target_friend,
4002 CONGESTION_TIMEOUT);
4006 /* Get the next hop to forward the trail setup request. */
4007 struct Closest_Peer next_peer =
4008 get_local_best_known_next_hop (final_dest_finger_val,
4009 intermediate_trail_id,
4015 /* Am I the final destination? */
4016 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4020 /* If I was not the source of this message for which now I am destination */
4021 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4023 GDS_ROUTING_add (trail_id, *peer, my_identity);
4026 if(trail_length > 0)
4028 GNUNET_assert (NULL !=
4030 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4031 &trail_peer_list[trail_length-1])));
4035 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
4037 finger_table_add (my_identity, NULL, 0, is_predecessor,
4038 final_dest_finger_val, trail_id);
4041 GNUNET_assert (NULL !=
4043 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source)));
4046 GDS_NEIGHBOURS_send_trail_setup_result (source,
4048 target_friend, trail_length,
4051 final_dest_finger_val,trail_id);
4055 GNUNET_assert (NULL !=
4057 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4058 &next_peer.next_hop)));
4060 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4062 /* Add yourself to list of peers. */
4063 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4065 memcpy (peer_list, trail_peer_list,
4066 trail_length * sizeof (struct GNUNET_PeerIdentity));
4067 peer_list[trail_length] = my_identity;
4069 GDS_NEIGHBOURS_send_trail_setup (source,
4070 final_dest_finger_val,
4071 next_peer.best_known_destination,
4072 target_friend, trail_length + 1, peer_list,
4073 is_predecessor, trail_id,
4074 next_peer.trail_id);
4077 GDS_NEIGHBOURS_send_trail_setup (source,
4078 final_dest_finger_val,
4079 next_peer.best_known_destination,
4080 target_friend, 0, NULL,
4081 is_predecessor, trail_id,
4082 next_peer.trail_id);
4088 /* FIXME: here we are calculating my_index and comparing also in this function.
4089 And we are doing it again here in this function. Re factor the code. */
4091 * FIXME: Should we call this function everywhere in all the handle functions
4092 * where we have a trail to verify from or a trail id. something like
4093 * if prev hop is not same then drop the message.
4094 * Check if sender_peer and peer from which we should receive the message are
4095 * same or different.
4096 * @param trail_peer_list List of peers in trail
4097 * @param trail_length Total number of peers in @a trail_peer_list
4098 * @param sender_peer Peer from which we got the message.
4099 * @param finger_identity Finger to which trail is setup. It is not part of trail.
4100 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
4101 * message are different.
4102 * #GNUNET_NO if sender_peer and peer from which we should receive the
4103 * message are different.
4106 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
4107 unsigned int trail_length,
4108 const struct GNUNET_PeerIdentity *sender_peer,
4109 struct GNUNET_PeerIdentity finger_identity,
4110 struct GNUNET_PeerIdentity source_peer)
4114 /* I am the source peer. */
4115 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4118 /* Is the first element of the trail is sender_peer.*/
4119 if (trail_length > 0)
4121 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4127 /* Is finger the sender peer? */
4128 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4135 /* Get my current location in the trail. */
4136 my_index = search_my_index (trail_peer_list, trail_length);
4140 /* I am the last element in the trail. */
4141 if ((trail_length - 1) == my_index)
4143 /* Is finger the sender_peer? */
4144 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4150 /* Is peer after me in trail the sender peer? */
4151 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4152 &trail_peer_list[my_index + 1]))
4162 * FIXME: we should also add a case where we search if we are present in the trail
4164 * Core handle for p2p trail setup result messages.
4166 * @param message message
4167 * @param peer sender of this message.
4168 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4171 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4172 const struct GNUNET_MessageHeader *message)
4174 const struct PeerTrailSetupResultMessage *trail_result;
4175 const struct GNUNET_PeerIdentity *trail_peer_list;
4176 struct GNUNET_PeerIdentity next_hop;
4177 struct FriendInfo *target_friend;
4178 struct GNUNET_PeerIdentity querying_peer;
4179 struct GNUNET_PeerIdentity finger_identity;
4180 uint32_t trail_length;
4181 uint64_t ulitmate_destination_finger_value;
4182 uint32_t is_predecessor;
4183 struct GNUNET_HashCode trail_id;
4187 msize = ntohs (message->size);
4188 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4190 GNUNET_break_op (0);
4194 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4195 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4196 sizeof (struct GNUNET_PeerIdentity);
4197 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4198 sizeof (struct GNUNET_PeerIdentity) != 0)
4200 GNUNET_break_op (0);
4204 is_predecessor = ntohl (trail_result->is_predecessor);
4205 querying_peer = trail_result->querying_peer;
4206 finger_identity = trail_result->finger_identity;
4207 trail_id = trail_result->trail_id;
4208 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4209 ulitmate_destination_finger_value =
4210 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4212 /* FIXME: here we are calculating my_index and comparing also in this function.
4213 And we are doing it again here in this function. Re factor the code. */
4214 /* Ensure that sender peer is the peer from which we were expecting the message. */
4216 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
4218 peer, finger_identity, querying_peer))
4220 GNUNET_break_op (0);
4221 return GNUNET_SYSERR;
4225 /* Am I the one who initiated the query? */
4226 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4228 /* If I am not my own finger identity, then add routing table entry. */
4229 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4231 GDS_ROUTING_add (trail_id, my_identity, *peer);
4234 finger_table_add (finger_identity, trail_peer_list, trail_length,
4235 is_predecessor, ulitmate_destination_finger_value, trail_id);
4239 /* Get my location in the trail. */
4240 my_index = search_my_index (trail_peer_list, trail_length);
4244 return GNUNET_SYSERR;
4248 next_hop = trail_result->querying_peer;
4250 next_hop = trail_peer_list[my_index - 1];
4252 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4253 &(trail_result->finger_identity))))
4255 GDS_ROUTING_add (trail_id, next_hop, *peer);
4258 GNUNET_assert (NULL !=
4260 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4261 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4262 target_friend, trail_length, trail_peer_list,
4264 ulitmate_destination_finger_value,
4272 * @param trail Trail to be inverted
4273 * @param trail_length Total number of peers in the trail.
4274 * @return Updated trail
4276 static struct GNUNET_PeerIdentity *
4277 invert_trail (const struct GNUNET_PeerIdentity *trail,
4278 unsigned int trail_length)
4282 struct GNUNET_PeerIdentity *inverted_trail;
4284 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4287 j = trail_length - 1;
4288 while (i < trail_length)
4290 inverted_trail[i] = trail[j];
4295 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4296 &inverted_trail[0]));
4297 return inverted_trail;
4302 * Return the shortest trail among all the trails to reach to finger from me.
4303 * @param finger Finger
4304 * @param shortest_trail_length[out] Trail length of shortest trail from me
4306 * @return Shortest trail.
4308 static struct GNUNET_PeerIdentity *
4309 get_shortest_trail (struct FingerInfo *finger,
4310 unsigned int *trail_length)
4312 struct Trail *trail;
4313 unsigned int flag = 0;
4314 unsigned int shortest_trail_index = 0;
4315 int shortest_trail_length = -1;
4316 struct Trail_Element *trail_element;
4317 struct GNUNET_PeerIdentity *trail_list;
4320 trail = GNUNET_new (struct Trail);
4322 /* Get the shortest trail to reach to current successor. */
4323 for (i = 0; i < finger->trails_count; i++)
4325 trail = &finger->trail_list[i];
4329 shortest_trail_index = i;
4330 shortest_trail_length = trail->trail_length;
4335 if (shortest_trail_length > trail->trail_length)
4337 shortest_trail_index = i;
4338 shortest_trail_length = trail->trail_length;
4343 /* Copy the shortest trail and return. */
4344 trail = &finger->trail_list[shortest_trail_index];
4345 trail_element = trail->trail_head;
4346 trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4347 shortest_trail_length);
4349 for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4351 trail_list[i] = trail_element->peer;
4354 GNUNET_assert(shortest_trail_length != -1);
4356 *trail_length = shortest_trail_length;
4362 * Return the trail from source to my current predecessor. Check if source
4363 * is already part of the this trail, if yes then return the shorten trail.
4364 * @param current_trail Trail from source to me, NOT including the endpoints.
4365 * @param current_trail_length Number of peers in @a current_trail.
4366 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4367 * source to my predecessor, NOT including
4369 * @return Trail from source to my predecessor.
4371 static struct GNUNET_PeerIdentity *
4372 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4373 const struct GNUNET_PeerIdentity *trail_src_to_me,
4374 unsigned int trail_src_to_me_len,
4375 unsigned int *trail_src_to_curr_pred_length)
4377 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4378 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4379 unsigned int trail_me_to_curr_pred_length;
4380 struct FingerInfo *current_predecessor;
4384 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4385 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4386 &trail_me_to_curr_pred_length);
4388 /* Check if trail_me_to_curr_pred contains source. */
4389 if (trail_me_to_curr_pred_length > 0)
4391 for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4393 if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4394 &trail_me_to_curr_pred[i]))
4399 /* Source is the last element in the trail to reach to my pred.
4400 Source is direct friend of the pred. */
4401 if (trail_me_to_curr_pred_length == i)
4403 *trail_src_to_curr_pred_length = 0;
4407 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4408 trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4409 *trail_src_to_curr_pred_length);
4410 for(j = 0; i < *trail_src_to_curr_pred_length; i++,j++)
4412 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4414 return trail_src_to_curr_pred;
4418 /* Append trail from source to me to my current_predecessor. */
4419 *trail_src_to_curr_pred_length = trail_src_to_me_len +
4420 trail_me_to_curr_pred_length + 1;
4422 trail_src_to_curr_pred = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4423 *trail_src_to_curr_pred_length);
4425 for (i = 0; i < trail_src_to_me_len; i++)
4426 trail_src_to_curr_pred[i] = trail_src_to_me[i];
4428 trail_src_to_curr_pred[i] = my_identity;
4431 for (j = 0; i < *trail_src_to_curr_pred_length; i++,j++)
4432 trail_src_to_curr_pred[i] = trail_me_to_curr_pred[j];
4434 return trail_src_to_curr_pred;
4439 * Add finger as your predecessor. To add, first generate a new trail id, invert
4440 * the trail to get the trail from me to finger, add an entry in your routing
4441 * table, send add trail message to peers which are part of trail from me to
4442 * finger and add finger in finger table.
4445 * @param trail_length
4448 update_predecessor (struct GNUNET_PeerIdentity finger,
4449 struct GNUNET_PeerIdentity *trail,
4450 unsigned int trail_length)
4452 struct GNUNET_HashCode trail_to_new_predecessor_id;
4453 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4454 struct FriendInfo *target_friend;
4456 /* Generate trail id for trail from me to new predecessor = finger. */
4457 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4458 &trail_to_new_predecessor_id,
4459 sizeof (trail_to_new_predecessor_id));
4461 /* Finger is a friend. */
4462 if (trail_length == 0)
4464 trail_to_new_predecessor = NULL;
4465 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4466 GNUNET_assert (NULL != (target_friend =
4467 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4472 /* Invert the trail to get the trail from me to finger, NOT including the
4474 trail_to_new_predecessor = invert_trail (trail, trail_length);
4476 /* Add an entry in your routing table. */
4477 GDS_ROUTING_add (trail_to_new_predecessor_id,
4479 trail_to_new_predecessor[0]);
4481 GNUNET_assert (NULL != (target_friend =
4482 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4483 &trail_to_new_predecessor[0])));
4484 GNUNET_assert (NULL != (
4485 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4486 &trail[trail_length - 1])));
4489 /* Add entry in routing table of all peers that are part of trail from me
4490 to finger, including finger. */
4491 GDS_NEIGHBOURS_send_add_trail (my_identity,
4493 trail_to_new_predecessor_id,
4494 trail_to_new_predecessor,
4498 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4499 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4500 GNUNET_free_non_null (trail_to_new_predecessor);
4505 * Check if you already have a predecessor. If not then add finger as your
4506 * predecessor. If you have predecessor, then compare two peer identites.
4507 * If finger is correct predecessor, then remove the old entry, add finger in
4508 * finger table and send add_trail message to add the trail in the routing
4509 * table of all peers which are part of trail to reach from me to finger.
4510 * @param finger New peer which may be our predecessor.
4511 * @param trail List of peers to reach from @finger to me.
4512 * @param trail_length Total number of peer in @a trail.
4515 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4516 struct GNUNET_PeerIdentity *trail,
4517 unsigned int trail_length)
4519 struct FingerInfo *current_predecessor;
4520 struct GNUNET_PeerIdentity *closest_peer;
4521 uint64_t predecessor_value;
4522 unsigned int is_predecessor = 1;
4524 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4526 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4528 /* No predecessor. Add finger as your predecessor. */
4529 if (GNUNET_NO == current_predecessor->is_present)
4531 update_predecessor (finger, trail, trail_length);
4535 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4541 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4542 closest_peer = select_closest_peer (&finger,
4543 ¤t_predecessor->finger_identity,
4544 predecessor_value, is_predecessor);
4546 /* Finger is the closest predecessor. Remove the existing one and add the new
4548 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, &finger))
4550 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4551 update_predecessor (finger, trail, trail_length);
4559 * Core handle for p2p verify successor messages.
4560 * @param cls closure
4561 * @param message message
4562 * @param peer peer identity this notification is about
4563 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4566 handle_dht_p2p_verify_successor(void *cls,
4567 const struct GNUNET_PeerIdentity *peer,
4568 const struct GNUNET_MessageHeader *message)
4570 const struct PeerVerifySuccessorMessage *vsm;
4571 struct GNUNET_HashCode trail_id;
4572 struct GNUNET_PeerIdentity successor;
4573 struct GNUNET_PeerIdentity source_peer;
4574 struct GNUNET_PeerIdentity *trail;
4575 struct GNUNET_PeerIdentity *next_hop;
4576 struct FingerInfo *current_predecessor;
4577 struct FriendInfo *target_friend;
4578 unsigned int trail_src_to_curr_pred_len = 0;
4579 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4581 unsigned int trail_length;
4583 msize = ntohs (message->size);
4585 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4587 GNUNET_break_op (0);
4591 vsm = (const struct PeerVerifySuccessorMessage *) message;
4592 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4593 sizeof (struct GNUNET_PeerIdentity);
4594 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4595 sizeof (struct GNUNET_PeerIdentity) != 0)
4597 GNUNET_break_op (0);
4601 trail_id = vsm->trail_id;
4602 source_peer = vsm->source_peer;
4603 successor = vsm->successor;
4604 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4607 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4609 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4611 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4612 if (NULL == next_hop)
4615 return GNUNET_SYSERR;
4617 GNUNET_assert (NULL !=
4619 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4621 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4622 trail_id, trail, trail_length,
4627 /* I am the destination of this message. */
4629 /* Check if the source_peer could be our predecessor and if yes then update
4631 compare_and_update_predecessor (source_peer, trail, trail_length);
4632 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4634 /* Is source of this message NOT my predecessor. */
4635 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4638 trail_src_to_curr_pred = get_trail_src_to_curr_pred (source_peer,
4641 &trail_src_to_curr_pred_len);
4646 trail_src_to_curr_pred = GNUNET_new(struct GNUNET_PeerIdentity);
4647 trail_src_to_curr_pred = NULL;
4648 trail_src_to_curr_pred_len = 0;
4651 GNUNET_assert (NULL !=
4653 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4654 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4655 current_predecessor->finger_identity,
4656 trail_id, trail_src_to_curr_pred,
4657 trail_src_to_curr_pred_len,
4658 GDS_ROUTING_DEST_TO_SRC,
4666 * If the trail from me to my probable successor contains a friend not
4667 * at index 0, then we can shorten the trail.
4668 * @param probable_successor Peer which is our probable successor
4669 * @param trail_me_to_probable_successor Peers in path from me to my probable
4670 * successor, NOT including the endpoints.
4671 * @param trail_me_to_probable_successor_len Total number of peers in
4672 * @a trail_me_to_probable_succesor.
4673 * @return Updated trail, if any friend found.
4674 * Else the trail_me_to_probable_successor.
4676 struct GNUNET_PeerIdentity *
4677 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4678 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4679 unsigned int trail_me_to_probable_successor_len,
4680 unsigned int *trail_to_new_successor_length)
4684 struct GNUNET_PeerIdentity *trail_to_new_successor;
4686 /* Probable successor is a friend */
4687 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4688 &probable_successor))
4690 trail_to_new_successor = NULL;
4691 *trail_to_new_successor_length = 0;
4692 return trail_to_new_successor;
4695 /* Is there any friend of yours in this trail. */
4696 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4698 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4699 &trail_me_to_probable_successor[i]))
4703 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4704 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4705 *trail_to_new_successor_length);
4707 for(j = 0;i < trail_me_to_probable_successor_len;i++,j++)
4709 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4712 return trail_to_new_successor;
4716 trail_to_new_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4717 trail_me_to_probable_successor_len);
4719 for(i = 0; i < trail_me_to_probable_successor_len; i++)
4720 trail_to_new_successor[i] = trail_me_to_probable_successor[i];
4722 return trail_to_new_successor;
4729 * @param probable_successor
4731 * @param trail_length
4734 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4735 struct GNUNET_PeerIdentity probable_successor,
4736 const struct GNUNET_PeerIdentity *trail,
4737 unsigned int trail_length)
4739 struct FingerInfo *current_successor;
4740 struct GNUNET_PeerIdentity *closest_peer;
4741 struct GNUNET_HashCode trail_id;
4742 struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4743 struct FriendInfo *target_friend;
4744 unsigned int trail_me_to_probable_succ_len;
4745 unsigned int is_predecessor = GNUNET_NO;
4746 uint64_t successor_value;
4748 current_successor = &finger_table[0];
4749 successor_value = compute_finger_identity_value(0);
4751 /* Have we found some other successor, while waiting for verify successor result. */
4752 if(0 != GNUNET_CRYPTO_cmp_peer_identity(&curr_succ, ¤t_successor->finger_identity))
4754 /* We could have added this new successor, only if it was closer the old one. */
4755 closest_peer = select_closest_peer (&curr_succ,
4756 ¤t_successor->finger_identity,
4757 successor_value, is_predecessor);
4759 /* FIXME: it may fail in case we have done more number of iterations of
4760 find _finger_trail_task. */
4762 GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4763 ¤t_successor->finger_identity));
4767 closest_peer = select_closest_peer (&probable_successor,
4768 ¤t_successor->finger_identity,
4769 successor_value, is_predecessor);
4771 /* If the current_successor in the finger table is closest, then do nothing. */
4772 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4773 ¤t_successor->finger_identity))
4776 /* Probable successor is the closest peer.*/
4778 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4781 /* TODO: Check if the path to reach to probable successor contains a friend. */
4782 trail_me_to_probable_succ =
4783 check_trail_me_to_probable_succ (probable_successor,
4784 trail, trail_length,
4785 &trail_me_to_probable_succ_len);
4787 /* Remove the existing successor. */
4788 remove_existing_finger (current_successor, 0);
4790 /* Generate a new trail id to reach to your new successor. */
4791 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4792 &trail_id, sizeof (trail_id));
4794 if (trail_me_to_probable_succ_len > 0)
4796 GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4797 GNUNET_assert (NULL !=
4799 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4800 &trail_me_to_probable_succ[0])));
4804 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4805 GNUNET_assert (NULL !=
4807 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4808 &probable_successor)));
4811 add_new_finger (probable_successor, trail_me_to_probable_succ,
4812 trail_me_to_probable_succ_len, trail_id, 0);
4814 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4815 trail_me_to_probable_succ,
4816 trail_me_to_probable_succ_len,
4824 * Core handle for p2p verify successor result messages.
4825 * @param cls closure
4826 * @param message message
4827 * @param peer peer identity this notification is about
4828 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4831 handle_dht_p2p_verify_successor_result(void *cls,
4832 const struct GNUNET_PeerIdentity *peer,
4833 const struct GNUNET_MessageHeader *message)
4835 const struct PeerVerifySuccessorResultMessage *vsrm;
4836 enum GDS_ROUTING_trail_direction trail_direction;
4837 struct GNUNET_PeerIdentity querying_peer;
4838 struct GNUNET_HashCode trail_id;
4839 struct GNUNET_PeerIdentity *next_hop;
4840 struct FriendInfo *target_friend;
4841 struct GNUNET_PeerIdentity probable_successor;
4842 struct GNUNET_PeerIdentity current_successor;
4843 const struct GNUNET_PeerIdentity *trail;
4844 unsigned int trail_length;
4847 msize = ntohs (message->size);
4848 /* We send a trail to reach from old successor to new successor, if
4849 * old_successor != new_successor.*/
4850 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4852 GNUNET_break_op (0);
4856 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4857 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4858 sizeof (struct GNUNET_PeerIdentity);
4860 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4861 sizeof (struct GNUNET_PeerIdentity) != 0)
4863 GNUNET_break_op (0);
4867 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4868 querying_peer = vsrm->querying_peer;
4869 trail_direction = ntohl (vsrm->trail_direction);
4870 trail_id = vsrm->trail_id;
4871 probable_successor = vsrm->probable_successor;
4872 current_successor = vsrm->current_successor;
4875 /* I am the querying_peer. */
4876 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4878 compare_and_update_successor (current_successor,
4879 probable_successor, trail, trail_length);
4883 /*If you are not the querying peer then pass on the message */
4884 GNUNET_assert (NULL != (next_hop =
4885 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
4886 GNUNET_assert (NULL !=
4888 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4889 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4890 vsrm->current_successor,
4891 probable_successor, trail_id,
4894 trail_direction, target_friend);
4900 * Core handle for p2p notify new successor messages.
4901 * @param cls closure
4902 * @param message message
4903 * @param peer peer identity this notification is about
4904 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4907 handle_dht_p2p_notify_new_successor(void *cls,
4908 const struct GNUNET_PeerIdentity *peer,
4909 const struct GNUNET_MessageHeader *message)
4911 const struct PeerNotifyNewSuccessorMessage *nsm;
4912 struct GNUNET_PeerIdentity *trail;
4913 struct GNUNET_PeerIdentity source;
4914 struct GNUNET_PeerIdentity new_successor;
4915 struct GNUNET_HashCode trail_id;
4916 struct GNUNET_PeerIdentity next_hop;
4917 struct FriendInfo *target_friend;
4920 uint32_t trail_length;
4922 msize = ntohs (message->size);
4924 /* We have the trail to reach from source to new successor. */
4925 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
4927 GNUNET_break_op (0);
4931 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
4932 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
4933 sizeof (struct GNUNET_PeerIdentity);
4934 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
4935 sizeof (struct GNUNET_PeerIdentity) != 0)
4937 GNUNET_break_op (0);
4941 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
4942 source = nsm->source_peer;
4943 new_successor = nsm->new_successor;
4944 trail_id = nsm->trail_id;
4946 //FIXME: add a check to make sure peer is correct.
4948 /* I am the new_successor to source_peer. */
4949 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
4951 GDS_ROUTING_add (trail_id, *peer, my_identity);
4952 compare_and_update_predecessor (source, trail, trail_length);
4956 GNUNET_assert(trail_length > 0);
4957 /* I am part of trail to reach to successor. */
4958 my_index = search_my_index (trail, trail_length);
4961 GNUNET_break_op (0);
4962 return GNUNET_SYSERR;
4965 if ((trail_length-1) == my_index) //FIXMe: SHOULD IT BE TRAIL_LENGTH - 1.s
4966 next_hop = new_successor;
4968 next_hop = trail[my_index + 1];
4971 /* Add an entry in routing table for trail from source to its new successor. */
4972 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
4974 GNUNET_assert (NULL !=
4976 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4977 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
4979 trail_id, target_friend);
4986 * Core handler for P2P trail rejection message
4987 * @param cls closure
4988 * @param message message
4989 * @param peer peer identity this notification is about
4990 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4993 handle_dht_p2p_trail_setup_rejection (void *cls,
4994 const struct GNUNET_PeerIdentity *peer,
4995 const struct GNUNET_MessageHeader *message)
4997 const struct PeerTrailRejectionMessage *trail_rejection;
4998 unsigned int trail_length;
4999 const struct GNUNET_PeerIdentity *trail_peer_list;
5000 struct FriendInfo *target_friend;
5001 struct GNUNET_TIME_Relative congestion_timeout;
5002 struct GNUNET_HashCode trail_id;
5003 struct GNUNET_PeerIdentity next_peer;
5004 struct GNUNET_PeerIdentity source;
5005 struct GNUNET_PeerIdentity *next_hop;
5006 uint64_t ultimate_destination_finger_value;
5007 unsigned int is_predecessor;
5010 msize = ntohs (message->size);
5011 /* We are passing the trail setup so far. */
5012 if (msize < sizeof (struct PeerTrailRejectionMessage))
5014 GNUNET_break_op (0);
5018 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
5019 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5020 sizeof (struct GNUNET_PeerIdentity);
5021 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5022 sizeof (struct GNUNET_PeerIdentity) != 0)
5024 GNUNET_break_op (0);
5028 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5029 is_predecessor = ntohl (trail_rejection->is_predecessor);
5030 congestion_timeout = trail_rejection->congestion_time;
5031 source = trail_rejection->source_peer;
5032 trail_id = trail_rejection->trail_id;
5033 ultimate_destination_finger_value =
5034 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5036 /* First set the congestion time of the friend that sent you this message. */
5037 GNUNET_assert (NULL !=
5039 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5040 target_friend->congestion_timestamp =
5041 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5042 congestion_timeout);
5044 /* I am the source peer which wants to setup the trail. Do nothing.
5045 * send_find_finger_trail_task is scheduled periodically.*/
5046 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5049 /* If I am congested then pass this message to peer before me in trail. */
5050 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5052 struct GNUNET_PeerIdentity *new_trail;
5053 unsigned int new_trail_length;
5055 /* Remove yourself from the trail setup so far. */
5056 if (trail_length == 1)
5059 new_trail_length = 0;
5064 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5065 sizeof (struct GNUNET_PeerIdentity));
5067 /* Remove myself from the trail. */
5068 new_trail_length = trail_length -1;
5069 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5070 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5073 GNUNET_assert (NULL !=
5075 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5076 GDS_NEIGHBOURS_send_trail_rejection (source,
5077 ultimate_destination_finger_value,
5078 my_identity, is_predecessor,
5079 new_trail,new_trail_length,trail_id,
5080 target_friend, CONGESTION_TIMEOUT);
5081 GNUNET_free (new_trail);
5085 struct Closest_Peer successor;
5086 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5088 /* Am I the final destination? */
5089 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5092 if (0 == trail_length)
5095 next_peer = trail_peer_list[trail_length-1];
5097 GNUNET_assert (NULL !=
5099 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5101 GDS_NEIGHBOURS_send_trail_setup_result (source,
5103 target_friend, trail_length,
5106 ultimate_destination_finger_value,
5111 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5113 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5114 peer_list[trail_length] = my_identity;
5116 GNUNET_assert (NULL !=
5118 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5120 GDS_NEIGHBOURS_send_trail_setup (source,
5121 ultimate_destination_finger_value,
5122 successor.best_known_destination,
5123 target_friend, trail_length + 1, peer_list,
5124 is_predecessor, trail_id,
5125 successor.trail_id);
5132 * Core handle for p2p trail tear compression messages.
5133 * @param cls closure
5134 * @param message message
5135 * @param peer peer identity this notification is about
5136 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5139 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5140 const struct GNUNET_MessageHeader *message)
5142 const struct PeerTrailCompressionMessage *trail_compression;
5143 struct GNUNET_PeerIdentity *next_hop;
5144 struct FriendInfo *target_friend;
5145 struct GNUNET_HashCode trail_id;
5148 msize = ntohs (message->size);
5150 if (msize != sizeof (struct PeerTrailCompressionMessage))
5152 GNUNET_break_op (0);
5156 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5157 trail_id = trail_compression->trail_id;
5159 /* Am I the new first friend to reach to finger of this trail. */
5160 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5163 GNUNET_assert (NULL !=
5164 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5165 &trail_compression->source_peer)));
5167 /* Update your prev hop to source of this message. */
5168 GNUNET_assert (GNUNET_SYSERR !=
5169 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5170 trail_compression->source_peer)));
5174 /* Pass the message to next hop to finally reach to new_first_friend. */
5175 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5177 if (NULL == next_hop)
5183 GNUNET_assert (NULL !=
5185 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5187 GDS_ROUTING_remove_trail (trail_id);
5189 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5191 trail_compression->new_first_friend,
5198 * Core handler for trail teardown message.
5199 * @param cls closure
5200 * @param message message
5201 * @param peer sender of this messsage.
5202 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5205 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5206 const struct GNUNET_MessageHeader *message)
5208 const struct PeerTrailTearDownMessage *trail_teardown;
5209 enum GDS_ROUTING_trail_direction trail_direction;
5210 struct GNUNET_HashCode trail_id;
5211 struct GNUNET_PeerIdentity *next_hop;
5214 msize = ntohs (message->size);
5216 /* Here we pass only the trail id. */
5217 if (msize != sizeof (struct PeerTrailTearDownMessage))
5219 GNUNET_break_op (0);
5223 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5224 trail_direction = ntohl (trail_teardown->trail_direction);
5225 trail_id = trail_teardown->trail_id;
5227 /* Check if peer is the real peer from which we should get this message.*/
5228 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5229 /* FIXME: is using negation of trail direction correct. */
5231 GNUNET_assert (NULL != (prev_hop =
5232 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5233 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5236 return GNUNET_SYSERR;
5240 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5242 if (NULL == next_hop)
5245 return GNUNET_SYSERR;
5248 /* I am the next hop, which means I am the final destination. */
5249 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5251 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5256 /* If not final destination, then send a trail teardown message to next hop.*/
5257 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5258 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5259 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5267 * Core handle for p2p add trail message.
5268 * @param cls closure
5269 * @param message message
5270 * @param peer peer identity this notification is about
5271 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5274 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5275 const struct GNUNET_MessageHeader *message)
5277 const struct PeerAddTrailMessage *add_trail;
5278 const struct GNUNET_PeerIdentity *trail;
5279 struct GNUNET_HashCode trail_id;
5280 struct GNUNET_PeerIdentity destination_peer;
5281 struct GNUNET_PeerIdentity source_peer;
5282 struct GNUNET_PeerIdentity next_hop;
5283 unsigned int trail_length;
5284 unsigned int my_index;
5287 msize = ntohs (message->size);
5288 /* In this message we pass the whole trail from source to destination as we
5289 * are adding that trail.*/
5290 if (msize < sizeof (struct PeerAddTrailMessage))
5292 GNUNET_break_op (0);
5296 add_trail = (const struct PeerAddTrailMessage *) message;
5297 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5298 sizeof (struct GNUNET_PeerIdentity);
5299 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5300 sizeof (struct GNUNET_PeerIdentity) != 0)
5302 GNUNET_break_op (0);
5306 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5307 destination_peer = add_trail->destination_peer;
5308 source_peer = add_trail->source_peer;
5309 trail_id = add_trail->trail_id;
5311 //FIXME: add a check that sender peer is not malicious. Make it a generic
5312 // function so that it can be used in all other functions where we need the
5313 // same functionality.
5315 /* I am not the destination of the trail. */
5316 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5318 struct FriendInfo *target_friend;
5320 /* Get my location in the trail. */
5321 my_index = search_my_index (trail, trail_length);
5325 GNUNET_break_op (0);
5326 return GNUNET_SYSERR;
5330 if ((trail_length - 1) == my_index)
5333 next_hop = destination_peer;
5337 next_hop = trail[my_index + 1];
5339 /* FIXME: check that you always add trail entry even if your finger is
5341 /* Add in your routing table. */
5342 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5343 GNUNET_assert (NULL !=
5345 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5346 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5347 trail, trail_length, target_friend);
5350 /* FIXME: check that you always add trail entry even if your finger is
5352 /* I am the destination. Add an entry in routing table. */
5353 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5359 * Free the finger trail in which the first friend to reach to a finger is
5360 * disconnected_friend. Also remove entry from routing table for that particular
5362 * @param disconnected_friend PeerIdentity of friend which got disconnected
5363 * @param remove_finger Finger whose trail we need to check if it has
5364 * disconnected_friend as the first hop.
5365 * @return Total number of trails in which disconnected_friend was the first
5369 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5370 struct FingerInfo *remove_finger)
5372 unsigned int matching_trails_count;
5375 /* Number of trails with disconnected_friend as the first hop in the trail
5376 * to reach from me to remove_finger, NOT including endpoints. */
5377 matching_trails_count = 0;
5379 /* Iterate over all the trails of finger. */
5380 for (i = 0; i < remove_finger->trails_count; i++)
5382 struct Trail *trail;
5383 trail = &remove_finger->trail_list[i];
5385 /* This assertion is ensure that there are no gaps in the trail list.
5386 REMOVE IT AFTERWARDS. */
5387 GNUNET_assert (GNUNET_YES == trail->is_present);
5389 /* First friend to reach to finger is disconnected_peer. */
5390 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5391 disconnected_friend))
5393 struct GNUNET_PeerIdentity *next_hop;
5394 struct FriendInfo *remove_friend;
5396 GNUNET_assert (NULL !=
5398 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5399 disconnected_friend)));
5400 /* FIXME: removing no but check it. */
5401 //remove_friend->trails_count--;
5402 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5403 GDS_ROUTING_SRC_TO_DEST);
5405 /* Here it may happen that as all the peers got disconnected, the entry in
5406 routing table for that particular trail has been removed, because the
5407 previously disconnected peer was either a next hop or prev hop of that
5409 if (NULL == next_hop)
5412 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5414 matching_trails_count++;
5415 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5418 trail->is_present = GNUNET_NO;
5421 return matching_trails_count;
5426 * Iterate over finger_table entries.
5427 * 0. Ignore finger which is my_identity or if no valid entry present at
5428 * that finger index.
5429 * 1. If disconnected_friend is a finger, then remove the routing entry from
5430 your own table. Free the trail.
5431 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5432 * 2.1 Remove all the trails and entry from routing table in which disconnected
5433 * friend is the first friend in the trail. If disconnected_friend is the
5434 * first friend in all the trails to reach finger, then remove the finger.
5435 * @param disconnected_friend Peer identity of friend which got disconnected.
5438 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5440 struct FingerInfo *remove_finger;
5441 struct FriendInfo *remove_friend;
5442 int removed_trails_count;
5445 /* Iterate over finger table entries. */
5446 for (i = 0; i < MAX_FINGERS; i++)
5448 remove_finger = &finger_table[i];
5450 /* No finger stored at this trail index. */
5451 if (GNUNET_NO == remove_finger->is_present)
5454 /* I am my own finger, then ignore this finger. */
5455 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5459 /* Is disconnected_peer a finger? */
5460 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5461 &remove_finger->finger_identity))
5463 struct GNUNET_PeerIdentity *next_hop;
5464 struct GNUNET_HashCode trail_id;
5467 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5468 trail_id = remove_finger->trail_list[0].trail_id;
5472 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5474 /* FIXME: This assertion fails check why*/
5476 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5477 &remove_finger->finger_identity)));
5478 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5479 GNUNET_assert (NULL !=
5481 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5482 disconnected_peer)));
5485 remove_finger->trail_list[0].is_present = GNUNET_NO;
5486 //GNUNET_assert (0 != remove_friend->trails_count);
5487 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5488 remove_finger->is_present = GNUNET_NO;
5489 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5493 /* If finger is a friend but not disconnected_friend, then continue. */
5494 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5495 &remove_finger->finger_identity))
5498 /* Iterate over the list of trails to reach remove_finger. Check if
5499 * disconnected_friend is the first friend in any of the trail. */
5500 removed_trails_count = remove_matching_trails (disconnected_peer,
5502 remove_finger->trails_count =
5503 remove_finger->trails_count - removed_trails_count;
5504 /* All the finger trails had disconnected_friend as the first friend,
5505 * so free the finger. */
5506 if (remove_finger->trails_count == 0)
5508 remove_finger->is_present = GNUNET_NO;
5509 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5516 * Method called whenever a peer disconnects.
5518 * @param cls closure
5519 * @param peer peer identity this notification is about
5522 handle_core_disconnect (void *cls,
5523 const struct GNUNET_PeerIdentity *peer)
5525 struct FriendInfo *remove_friend;
5527 /* If disconnected to own identity, then return. */
5528 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5531 GNUNET_assert (NULL != (remove_friend =
5532 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5534 /* Remove fingers with peer as first friend or if peer is a finger. */
5535 remove_matching_fingers (peer);
5537 /* Remove any trail from routing table of which peer is a part of. This function
5538 * internally sends a trail teardown message in the direction of which
5539 * disconnected peer is not part of. */
5540 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5542 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5544 /* Remove peer from friend_peermap. */
5545 GNUNET_assert (GNUNET_YES ==
5546 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5550 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5553 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5555 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5556 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5565 * Method called whenever a peer connects.
5567 * @param cls closure
5568 * @param peer_identity peer identity this notification is about
5571 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5573 struct FriendInfo *friend;
5575 /* Check for connect to self message */
5576 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5579 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5581 /* If peer already exists in our friend_peermap, then exit. */
5582 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5589 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
5592 friend = GNUNET_new (struct FriendInfo);
5593 friend->id = *peer_identity;
5595 GNUNET_assert (GNUNET_OK ==
5596 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5597 peer_identity, friend,
5598 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5601 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5602 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5603 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5608 * To be called on core init/fail.
5610 * @param cls service closure
5611 * @param identity the public identity of this peer
5614 core_init (void *cls,
5615 const struct GNUNET_PeerIdentity *identity)
5617 my_identity = *identity;
5620 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5621 my_id64 = GNUNET_ntohll (my_id64);
5622 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5623 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5629 * Initialize finger table entries.
5632 finger_table_init ()
5637 for(i = 0; i < MAX_FINGERS; i++)
5639 finger_table[i].is_present = GNUNET_NO;
5640 for (j = 0; j < MAXIMUM_TRAILS_PER_FINGER; j++)
5641 finger_table[i].trail_list[j].is_present = GNUNET_NO;
5642 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5648 * Initialize neighbours subsystem.
5649 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5652 GDS_NEIGHBOURS_init (void)
5654 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5655 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5656 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5657 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5658 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5659 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5660 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5661 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5662 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5663 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5664 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5665 sizeof (struct PeerTrailCompressionMessage)},
5666 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5667 sizeof (struct PeerTrailTearDownMessage)},
5668 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5673 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5674 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5675 GNUNET_NO, core_handlers);
5676 if (NULL == core_api)
5677 return GNUNET_SYSERR;
5679 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5680 finger_table_init ();
5687 * Shutdown neighbours subsystem.
5690 GDS_NEIGHBOURS_done (void)
5692 if (NULL == core_api)
5695 GNUNET_CORE_disconnect (core_api);
5698 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5699 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5700 friend_peermap = NULL;
5702 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5705 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5706 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5709 if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5711 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5712 send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5720 * @return my identity
5722 struct GNUNET_PeerIdentity
5723 GDS_NEIGHBOURS_get_my_id (void)
5728 /* end of gnunet-service-xdht_neighbours.c */