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
53 * 2. Now souce and destination of a trail also stores the trail entries for
54 * which they are end point. Make these changes in case of gds_routing_add()
55 * 3. Should we append xvine in message which are of xvine dht?
59 * Maximum possible fingers (including predecessor) of a peer
61 #define MAX_FINGERS 65
64 * Maximum allowed number of pending messages per friend peer.
66 #define MAXIMUM_PENDING_PER_FRIEND 64
69 * How long to wait before sending another find finger trail request
71 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
74 * How long at most to wait for transmission of a request to a friend ?
76 #define GET_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
79 * Duration for which I may remain congested.
80 * Note: Its a static value. In future, a peer may do some analysis and calculate
81 * congestion_timeout based on 'some' parameters.
83 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
86 * Maximum number of trails allowed to go through a friend.
88 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
91 * Maximum number of trails stored per finger.
93 #define MAXIMUM_TRAILS_PER_FINGER 2
96 * Finger map index for predecessor entry in finger table.
98 #define PREDECESSOR_FINGER_ID 64
101 * Wrap around in peer identity circle.
102 * FIXME: not used anywhere, should be used in
103 * find_successor() while comparing two peers.
105 #define PEER_IDENTITES_WRAP_AROUND pow(2, 64) - 1
108 * To check if a finger is predecessor or not.
110 enum GDS_NEIGHBOURS_finger_type
112 GDS_FINGER_TYPE_PREDECESSOR = 0,
113 GDS_FINGER_TYPE_NON_PREDECESSOR = 1
116 GNUNET_NETWORK_STRUCT_BEGIN
121 struct PeerPutMessage
124 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
126 struct GNUNET_MessageHeader header;
131 uint32_t options GNUNET_PACKED;
136 uint32_t block_type GNUNET_PACKED;
141 uint32_t hop_count GNUNET_PACKED;
144 * Replication level for this message
145 * In the current implementation, this value is not used.
147 uint32_t desired_replication_level GNUNET_PACKED;
150 * Length of the PUT path that follows (if tracked).
152 uint32_t put_path_length GNUNET_PACKED;
155 * Best known destination (could be my friend or finger) which should
156 * get this message next.
158 struct GNUNET_PeerIdentity best_known_destination;
161 * In case best_known_destination is a finger, then trail to reach
162 * to that finger. Else its default value is 0.
164 struct GNUNET_HashCode intermediate_trail_id;
167 * When does the content expire?
169 struct GNUNET_TIME_AbsoluteNBO expiration_time;
172 * The key to store the value under.
174 struct GNUNET_HashCode key GNUNET_PACKED;
176 /* put path (if tracked) */
185 struct PeerGetMessage
188 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
190 struct GNUNET_MessageHeader header;
195 uint32_t options GNUNET_PACKED;
198 * Desired content type.
200 uint32_t block_type GNUNET_PACKED;
205 uint32_t hop_count GNUNET_PACKED;
208 * Desired replication level for this request.
209 * In the current implementation, this value is not used.
211 uint32_t desired_replication_level GNUNET_PACKED;
214 * Total number of peers in get path.
216 unsigned int get_path_length;
219 * Best known destination (could be my friend or finger) which should
220 * get this message next.
222 struct GNUNET_PeerIdentity best_known_destination;
225 * In case best_known_destination is a finger, then trail to reach
226 * to that finger. Else its default value is 0.
228 struct GNUNET_HashCode intermediate_trail_id;
231 * The key we are looking for.
233 struct GNUNET_HashCode key;
242 struct PeerGetResultMessage
245 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
247 struct GNUNET_MessageHeader header;
250 * The type for the data.
252 uint32_t type GNUNET_PACKED;
255 * Number of peers recorded in the outgoing path from source to the
256 * stored location of this message.
258 uint32_t put_path_length GNUNET_PACKED;
261 * Length of the GET path that follows (if tracked).
263 uint32_t get_path_length GNUNET_PACKED;
266 * Peer which queried for get and should get the result.
268 struct GNUNET_PeerIdentity querying_peer;
271 * When does the content expire?
273 struct GNUNET_TIME_Absolute expiration_time;
276 * The key of the corresponding GET request.
278 struct GNUNET_HashCode key;
280 /* put path (if tracked) */
282 /* get path (if tracked) */
289 * P2P Trail setup message
291 struct PeerTrailSetupMessage
294 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
296 struct GNUNET_MessageHeader header;
299 * Is source_peer trying to setup the trail to a predecessor or any finger.
301 uint32_t is_predecessor;
304 * Peer closest to this value will be our finger.
306 uint64_t final_destination_finger_value;
309 * Source peer which wants to setup the trail to one of its finger.
311 struct GNUNET_PeerIdentity source_peer;
314 * Best known destination (could be my friend or finger) which should
315 * get this message next.
317 struct GNUNET_PeerIdentity best_known_destination;
320 * In case best_known_destination is a finger, then trail id of trail to
321 * reach to this finger.
323 struct GNUNET_HashCode intermediate_trail_id;
326 * Trail id for trail which we are trying to setup.
328 struct GNUNET_HashCode trail_id;
330 /* List of peers which are part of trail setup so far.
331 * Trail does NOT include source_peer and peer which will be closest to
332 * ultimate_destination_finger_value.
333 * struct GNUNET_PeerIdentity trail[]
338 * P2P Trail Setup Result message
340 struct PeerTrailSetupResultMessage
344 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
346 struct GNUNET_MessageHeader header;
349 * Finger to which we have found the path.
351 struct GNUNET_PeerIdentity finger_identity;
354 * Peer which started trail_setup to find trail to finger_identity
356 struct GNUNET_PeerIdentity querying_peer;
359 * Is the trail setup to querying_peer's predecessor or finger?
361 uint32_t is_predecessor;
364 * Value to which finger_identity is the closest peer.
366 uint64_t ulitmate_destination_finger_value;
369 * Identifier of the trail from querying peer to finger_identity, NOT
370 * including both endpoints.
372 struct GNUNET_HashCode trail_id;
374 /* List of peers which are part of the trail from querying peer to
375 * finger_identity, NOT including both endpoints.
376 * struct GNUNET_PeerIdentity trail[]
381 * P2P Verify Successor Message.
383 struct PeerVerifySuccessorMessage
386 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
388 struct GNUNET_MessageHeader header;
391 * Peer which wants to verify its successor.
393 struct GNUNET_PeerIdentity source_peer;
396 * Source Peer's current successor.
398 struct GNUNET_PeerIdentity successor;
401 * Identifier of trail to reach from source_peer to successor.
403 struct GNUNET_HashCode trail_id;
405 /* List of the peers which are part of trail to reach from source_peer
406 * to successor, NOT including them
407 * struct GNUNET_PeerIdentity trail[]
412 * FIXME: In case you append the trail it may contain the same peer twice.
413 * So, when you call search_my_index it can return error. Solution is while
414 * appending the entry first check for duplicate entries or may be don't
415 * send the current_predecessor at all.
416 * P2P Verify Successor Result Message
418 struct PeerVerifySuccessorResultMessage
421 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
423 struct GNUNET_MessageHeader header;
426 * Peer which sent the request to verify its successor.
428 struct GNUNET_PeerIdentity querying_peer;
431 * Successor to which PeerVerifySuccessorMessage was sent.
433 struct GNUNET_PeerIdentity source_successor;
436 * Current Predecessor of source_successor. It can be same as querying peer
439 struct GNUNET_PeerIdentity current_predecessor;
442 * Trail identifier of trail from querying_peer to source_successor.
444 struct GNUNET_HashCode trail_id;
447 * Direction in which we are looking at the trail.
449 uint32_t trail_direction;
451 /* In case current_predecessor != querying_peer, then trail to reach from
452 * querying_peer to current_predecessor, NOT including end points.
453 * struct GNUNET_PeerIdentity trail[]
458 * P2P Notify New Successor Message.
460 struct PeerNotifyNewSuccessorMessage
463 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
465 struct GNUNET_MessageHeader header;
468 * Peer which wants to notify its new successor.
470 struct GNUNET_PeerIdentity source_peer;
473 * New successor of source_peer.
475 struct GNUNET_PeerIdentity new_successor;
478 * Unique identifier of the trail from source_peer to new_successor,
479 * NOT including the endpoints.
481 struct GNUNET_HashCode trail_id;
483 /* List of peers in trail from source_peer to new_successor,
484 * NOT including the endpoints.
485 * struct GNUNET_PeerIdentity trail[]
490 * P2P Trail Compression Message.
492 struct PeerTrailCompressionMessage
495 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION
497 struct GNUNET_MessageHeader header;
500 * Source peer of this trail.
502 struct GNUNET_PeerIdentity source_peer;
505 * Trail from source_peer to destination_peer compressed such that
506 * new_first_friend is the first hop in the trail from source to
509 struct GNUNET_PeerIdentity new_first_friend;
512 * Unique identifier of trail.
514 struct GNUNET_HashCode trail_id;
519 * P2P Trail Tear Down message.
521 struct PeerTrailTearDownMessage
524 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
526 struct GNUNET_MessageHeader header;
529 * Unique identifier of the trail.
531 struct GNUNET_HashCode TRAIL_ID;
534 * Direction of trail.
536 uint32_t trail_direction;
541 * P2P Trail Rejection Message.
543 struct PeerTrailRejectionMessage
546 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
548 struct GNUNET_MessageHeader header;
551 * Peer which wants to set up the trail.
553 struct GNUNET_PeerIdentity source_peer;
556 * Peer which sent trail rejection message as it it congested.
558 struct GNUNET_PeerIdentity congested_peer;
561 * Peer identity closest to this value will be finger of
564 uint64_t ultimate_destination_finger_value;
567 * Is source_peer trying to setup the trail to its predecessor or finger.
569 uint32_t is_predecessor;
572 * Identifier for the trail that source peer is trying to setup.
574 struct GNUNET_HashCode trail_id;
577 * Relative time for which congested_peer will remain congested.
579 struct GNUNET_TIME_Relative congestion_time;
581 /* Trail_list from source_peer to peer which sent the message for trail setup
582 * to congested peer. This trail does NOT include source_peer.
583 struct GNUNET_PeerIdnetity trail[]*/
587 * P2P Add Trail Message.
589 struct PeerAddTrailMessage
592 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL
594 struct GNUNET_MessageHeader header;
597 * Source of the routing trail.
599 struct GNUNET_PeerIdentity source_peer;
602 * Destination of the routing trail.
604 struct GNUNET_PeerIdentity destination_peer;
607 * Unique identifier of the trail from source_peer to destination_peer,
608 * NOT including the endpoints.
610 struct GNUNET_HashCode trail_id;
612 /* Trail from source peer to destination peer, NOT including them.
613 * struct GNUNET_PeerIdentity trail[]
617 GNUNET_NETWORK_STRUCT_END
620 * Linked list of messages to send to a particular other peer.
622 struct P2PPendingMessage
625 * Pointer to next item in the list
627 struct P2PPendingMessage *next;
630 * Pointer to previous item in the list
632 struct P2PPendingMessage *prev;
635 * Message importance level. FIXME: used? useful?
637 unsigned int importance;
640 * When does this message time out?
642 struct GNUNET_TIME_Absolute timeout;
645 * Actual message to be sent, allocated at the end of the struct:
646 * // msg = (cast) &pm[1];
647 * // memcpy (&pm[1], data, len);
649 const struct GNUNET_MessageHeader *msg;
654 * Entry in friend_peermap.
661 struct GNUNET_PeerIdentity id;
664 * Number of trails for which this friend is the first hop or if the friend
667 unsigned int trails_count;
670 * Count of outstanding messages for this friend.
672 unsigned int pending_count;
675 * In case not 0, then amount of time for which this friend is congested.
677 struct GNUNET_TIME_Absolute congestion_timestamp;
680 * Head of pending messages to be sent to this friend.
682 struct P2PPendingMessage *head;
685 * Tail of pending messages to be sent to this friend.
687 struct P2PPendingMessage *tail;
690 * Core handle for sending messages to this friend.
692 struct GNUNET_CORE_TransmitHandle *th;
697 * An individual element of the trail to reach to a finger.
702 * Pointer to next item in the list
704 struct Trail_Element *next;
707 * Pointer to prev item in the list
709 struct Trail_Element *prev;
712 * An element in this trail.
714 struct GNUNET_PeerIdentity peer;
718 * FIXME: removed first_friend_trails_count, need to write a function
719 * to calculate each time we need it. Else, keep a pointer to first
720 * friend of in the trail.
721 * Information about an individual trail.
728 struct Trail_Element *trail_head;
733 struct Trail_Element *trail_tail;
736 * Unique identifier of this trail.
738 struct GNUNET_HashCode trail_id;
741 * Length of trail pointed
743 unsigned int trail_length;
747 * An entry in finger_table
754 struct GNUNET_PeerIdentity finger_identity;
758 * Is there any valid entry for this finger.
760 unsigned int is_present;
763 * Index in finger peer map
765 uint32_t finger_map_index;
768 * Number of trails setup so far for this finger.
769 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
771 uint32_t trails_count;
774 * Array of trails to reach to this finger.
776 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
781 * Data structure to keep track of closest peer seen so far in find_successor()
786 * Destination finger vaule.
788 uint64_t destination_finger_value;
791 * Is finger value predecessor or any other finge
793 unsigned int is_predecessor;
796 * Trail id to reach to peer.
798 struct GNUNET_HashCode trail_id;
801 * FIXME: see the usage of this field and write comment.
803 struct GNUNET_PeerIdentity next_hop;
806 * Next destination. In case of friend and my_identity , it is same as next_hop
807 * In case of finger it is finger identity.
809 struct GNUNET_PeerIdentity best_known_destination;
813 * FIXME: now I have removed the first_friend_trail_count,
814 * Need to update the code to find the count.
815 * Data structure to store the trail chosen to reach to finger.
817 struct Selected_Finger_Trail
820 * First friend in the trail to reach finger.
822 struct FriendInfo friend;
825 * Identifier of this trail.
827 struct GNUNET_HashCode trail_id;
830 * Total number of peers in this trail.
832 unsigned int trail_length;
836 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
837 * get our first friend.
839 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
842 * Identity of this peer.
844 static struct GNUNET_PeerIdentity my_identity;
847 * Peer map of all the friends of a peer
849 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
852 * Array of all the fingers.
854 static struct FingerInfo finger_table [MAX_FINGERS];
859 static struct GNUNET_CORE_Handle *core_api;
862 * The current finger index that we have want to find trail to. We start the
863 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
864 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
865 * we reset this index to 0.
867 static unsigned int current_search_finger_index;
871 * Called when core is ready to send a message we asked for
872 * out to the destination.
874 * @param cls the 'struct FriendInfo' of the target friend
875 * @param size number of bytes available in buf
876 * @param buf where the callee should write the message
877 * @return number of bytes written to buf
880 core_transmit_notify (void *cls, size_t size, void *buf)
882 struct FriendInfo *peer = cls;
884 struct P2PPendingMessage *pending;
889 while ((NULL != (pending = peer->head)) &&
890 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
892 peer->pending_count--;
893 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
894 GNUNET_free (pending);
898 /* no messages pending */
904 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
905 GNUNET_CORE_PRIO_BEST_EFFORT,
906 GNUNET_TIME_absolute_get_remaining
907 (pending->timeout), &peer->id,
908 ntohs (pending->msg->size),
909 &core_transmit_notify, peer);
910 GNUNET_break (NULL != peer->th);
914 while ((NULL != (pending = peer->head)) &&
915 (size - off >= (msize = ntohs (pending->msg->size))))
917 GNUNET_STATISTICS_update (GDS_stats,
919 ("# Bytes transmitted to other peers"), msize,
921 memcpy (&cbuf[off], pending->msg, msize);
923 peer->pending_count--;
924 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
925 GNUNET_free (pending);
927 if (peer->head != NULL)
930 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
931 GNUNET_CORE_PRIO_BEST_EFFORT,
932 GNUNET_TIME_absolute_get_remaining
933 (pending->timeout), &peer->id, msize,
934 &core_transmit_notify, peer);
935 GNUNET_break (NULL != peer->th);
943 * Transmit all messages in the friend's message queue.
945 * @param peer message queue to process
948 process_friend_queue (struct FriendInfo *peer)
950 struct P2PPendingMessage *pending;
952 if (NULL == (pending = peer->head))
954 if (NULL != peer->th)
957 GNUNET_STATISTICS_update (GDS_stats,
959 ("# Bytes of bandwidth requested from core"),
960 ntohs (pending->msg->size), GNUNET_NO);
963 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
965 GNUNET_TIME_absolute_get_remaining
966 (pending->timeout), &peer->id,
967 ntohs (pending->msg->size),
968 &core_transmit_notify, peer);
969 GNUNET_break (NULL != peer->th);
974 * Return friend corresponding to peer.
979 GDS_NEIGHBOURS_get_friend (struct GNUNET_PeerIdentity peer)
981 struct FriendInfo *friend;
982 GNUNET_assert (NULL != (friend =
983 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
989 * Construct a trail setup message and forward it to target_friend
990 * @param source_peer Peer which wants to setup the trail
991 * @param ultimate_destination_finger_value Peer identity closest to this value
992 * will be finger to @a source_peer
993 * @param best_known_destination Best known destination (could be finger or friend)
994 * which should get this message.
995 * @param target_friend Friend to which message is forwarded now.
996 * @param trail_length Total number of peers in trail setup so far.
997 * @param trail_peer_list Trail setup so far
998 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
999 * @param trail_id Unique identifier for the trail we are trying to setup.
1000 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1001 * best_known_destination when its a finger. If not
1002 * used then set to 0.
1005 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1006 uint64_t ultimate_destination_finger_value,
1007 struct GNUNET_PeerIdentity best_known_destination,
1008 struct FriendInfo *target_friend,
1009 unsigned int trail_length,
1010 const struct GNUNET_PeerIdentity *trail_peer_list,
1011 unsigned int is_predecessor,
1012 struct GNUNET_HashCode trail_id,
1013 struct GNUNET_HashCode *intermediate_trail_id)
1015 struct P2PPendingMessage *pending;
1016 struct PeerTrailSetupMessage *tsm;
1017 struct GNUNET_PeerIdentity *peer_list;
1020 msize = sizeof (struct PeerTrailSetupMessage) +
1021 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1023 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1029 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1031 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1035 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1036 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1037 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1038 pending->msg = &tsm->header;
1039 tsm->header.size = htons (msize);
1040 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
1041 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1042 tsm->source_peer = source_peer;
1043 tsm->best_known_destination = best_known_destination;
1044 tsm->is_predecessor = htonl (is_predecessor);
1045 tsm->trail_id = trail_id;
1047 if (NULL == intermediate_trail_id)
1048 memset (&tsm->intermediate_trail_id, 0, sizeof (tsm->intermediate_trail_id));
1050 tsm->intermediate_trail_id = *intermediate_trail_id;
1052 if (trail_length > 0)
1054 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1055 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1058 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1059 target_friend->pending_count++;
1060 process_friend_queue (target_friend);
1065 * Construct a trail setup result message and forward it to target friend.
1066 * @param querying_peer Peer which sent the trail setup request and should get
1068 * @param Finger Peer to which the trail has been setup to.
1069 * @param target_friend Friend to which this message should be forwarded.
1070 * @param trail_length Numbers of peers in the trail.
1071 * @param trail_peer_list Peers which are part of the trail from q
1072 * querying_peer to Finger, NOT including them.
1073 * @param is_predecessor Is @a Finger predecessor to @a querying_peer
1074 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1076 * @param trail_id Unique identifier of the trail.
1079 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1080 struct GNUNET_PeerIdentity finger,
1081 struct FriendInfo *target_friend,
1082 unsigned int trail_length,
1083 const struct GNUNET_PeerIdentity *trail_peer_list,
1084 unsigned int is_predecessor,
1085 uint64_t ultimate_destination_finger_value,
1086 struct GNUNET_HashCode trail_id)
1088 struct P2PPendingMessage *pending;
1089 struct PeerTrailSetupResultMessage *tsrm;
1090 struct GNUNET_PeerIdentity *peer_list;
1093 msize = sizeof (struct PeerTrailSetupResultMessage) +
1094 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1096 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1102 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1104 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1108 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1109 pending->importance = 0;
1110 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1111 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1112 pending->msg = &tsrm->header;
1113 tsrm->header.size = htons (msize);
1114 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
1115 tsrm->querying_peer = querying_peer;
1116 tsrm->finger_identity = finger;
1117 tsrm->is_predecessor = htonl (is_predecessor);
1118 tsrm->trail_id = trail_id;
1119 tsrm->ulitmate_destination_finger_value =
1120 GNUNET_htonll (ultimate_destination_finger_value);
1121 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1122 if (trail_length > 0)
1124 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1126 /* Send the message to chosen friend. */
1127 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1128 target_friend->pending_count++;
1129 process_friend_queue (target_friend);
1134 * Send trail rejection message to next_hop
1135 * @param source_peer Peer which is trying to setup the trail.
1136 * @param ultimate_destination_finger_value Peer closest to this value will be
1137 * @a source_peer's finger
1138 * @param congested_peer Peer which sent this message as it is congested.
1139 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1140 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1141 * by congested_peer. This does not include @a source_peer
1142 * @param trail_length Total number of peers in trail_peer_list, not including
1144 * @param trail_id Unique identifier of this trail.
1145 * @param congestion_timeout Duration given by congested peer as an estimate of
1146 * how long it may remain congested.
1149 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1150 uint64_t ultimate_destination_finger_value,
1151 struct GNUNET_PeerIdentity congested_peer,
1152 unsigned int is_predecessor,
1153 const struct GNUNET_PeerIdentity *trail_peer_list,
1154 unsigned int trail_length,
1155 struct GNUNET_HashCode trail_id,
1156 struct FriendInfo *target_friend,
1157 const struct GNUNET_TIME_Relative congestion_timeout)
1159 struct PeerTrailRejectionMessage *trm;
1160 struct P2PPendingMessage *pending;
1161 struct GNUNET_PeerIdentity *peer_list;
1164 msize = sizeof (struct PeerTrailRejectionMessage) +
1165 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1167 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1173 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1175 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1179 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1180 pending->importance = 0;
1181 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1182 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1183 pending->msg = &trm->header;
1184 trm->header.size = htons (msize);
1185 trm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION);
1186 trm->source_peer = source_peer;
1187 trm->congested_peer = congested_peer;
1188 trm->congestion_time = congestion_timeout;
1189 trm->is_predecessor = htonl (is_predecessor);
1190 trm->trail_id = trail_id;
1191 trm->ultimate_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1193 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1194 if (trail_length > 0)
1196 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1199 /* Send the message to chosen friend. */
1200 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1201 target_friend->pending_count++;
1202 process_friend_queue (target_friend);
1207 * Construct a verify successor message and forward it to target_friend.
1208 * @param source_peer Peer which wants to verify its successor.
1209 * @param successor Peer which is @a source_peer's current successor.
1210 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1211 * NOT including them.
1212 * @param trail List of peers which are part of trail to reach from @a source_peer
1213 * to @a successor, NOT including them.
1214 * @param trail_length Total number of peers in @a trail.
1215 * @param target_friend Next friend to get this message.
1218 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1219 struct GNUNET_PeerIdentity successor,
1220 const struct GNUNET_HashCode trail_id,
1221 struct GNUNET_PeerIdentity *trail,
1222 unsigned int trail_length,
1223 struct FriendInfo *target_friend)
1225 struct PeerVerifySuccessorMessage *vsm;
1226 struct P2PPendingMessage *pending;
1227 struct GNUNET_PeerIdentity *peer_list;
1230 msize = sizeof (struct PeerVerifySuccessorMessage);
1231 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1237 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1239 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1243 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1244 pending->importance = 0; /* FIXME */
1245 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1246 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1247 pending->msg = &vsm->header;
1248 vsm->header.size = htons (msize);
1249 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1250 vsm->source_peer = source_peer;
1251 vsm->successor = successor;
1252 vsm->trail_id = trail_id;
1254 if (trail_length > 0)
1256 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1257 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1260 /* Send the message to chosen friend. */
1261 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1262 target_friend->pending_count++;
1263 process_friend_queue (target_friend);
1268 * FIXME: In every function we pass target friend except for this one.
1269 * so, either change everything or this one. also, should se just store
1270 * the pointer to friend in routing table rather than gnunet_peeridentity.
1271 * if yes then we should keep friend info in.h andmake lot of changes.
1272 * Construct a trail teardown message and forward it to target friend.
1273 * @param trail_id Unique identifier of the trail.
1274 * @param trail_direction Direction of trail.
1275 * @param target_friend Friend to get this message.
1278 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1279 unsigned int trail_direction,
1280 struct GNUNET_PeerIdentity *peer)
1282 struct PeerTrailTearDownMessage *ttdm;
1283 struct P2PPendingMessage *pending;
1284 struct FriendInfo *target_friend;
1287 msize = sizeof (struct PeerTrailTearDownMessage);
1289 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1295 GNUNET_assert (NULL != (target_friend =
1296 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
1298 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1300 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1304 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1305 pending->importance = 0; /* FIXME */
1306 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1307 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1308 pending->msg = &ttdm->header;
1309 ttdm->header.size = htons (msize);
1310 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1311 ttdm->TRAIL_ID = trail_id;
1312 ttdm->trail_direction = htonl (trail_direction);
1314 /* Send the message to chosen friend. */
1316 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1317 target_friend->pending_count++;
1318 process_friend_queue (target_friend);
1323 * Construct a verify successor result message and send it to target_friend
1324 * @param querying_peer Peer which sent the verify successor message.
1325 * @param source_successor Current_successor of @a querying_peer.
1326 * @param current_predecessor Current predecessor of @a successor. Could be same
1327 * or different from @a querying_peer.
1328 * @param trail_id Unique identifier of the trail from @a querying_peer to
1329 * @a successor, NOT including them.
1330 * @param trail List of peers which are part of trail from @a querying_peer to
1331 * @a successor, NOT including them.
1332 * @param trail_length Total number of peers in @a trail
1333 * @param trail_direction Direction in which we are sending the message. In this
1334 * case we are sending result from @a successor to @a querying_peer.
1335 * @param target_friend Next friend to get this message.
1338 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1339 struct GNUNET_PeerIdentity source_successor,
1340 struct GNUNET_PeerIdentity current_predecessor,
1341 struct GNUNET_HashCode trail_id,
1342 const struct GNUNET_PeerIdentity *trail,
1343 unsigned int trail_length,
1344 enum GDS_ROUTING_trail_direction trail_direction,
1345 struct FriendInfo *target_friend)
1347 struct PeerVerifySuccessorResultMessage *vsmr;
1348 struct P2PPendingMessage *pending;
1349 struct GNUNET_PeerIdentity *peer_list;
1352 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1353 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1355 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1361 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1363 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1367 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1368 pending->importance = 0; /* FIXME */
1369 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1370 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1371 pending->msg = &vsmr->header;
1372 vsmr->header.size = htons (msize);
1373 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1374 vsmr->querying_peer = querying_peer;
1375 vsmr->source_successor = source_successor;
1376 vsmr->current_predecessor = current_predecessor;
1377 vsmr->trail_direction = htonl (trail_direction);
1378 vsmr->trail_id = trail_id;
1380 if (trail_length > 0)
1382 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1383 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1386 /* Send the message to chosen friend. */
1387 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1388 target_friend->pending_count++;
1389 process_friend_queue (target_friend);
1394 * Construct a notify new successor message and send it to target_friend
1395 * @param source_peer Peer which wants to notify to its new successor that it
1396 * could be its predecessor.
1397 * @param successor New successor of @a source_peer
1398 * @param successor_trail List of peers in Trail to reach from
1399 * @a source_peer to @a new_successor, NOT including
1401 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1402 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1403 * @param target_friend Next friend to get this message.
1406 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1407 struct GNUNET_PeerIdentity successor,
1408 struct GNUNET_PeerIdentity *successor_trail,
1409 unsigned int successor_trail_length,
1410 struct GNUNET_HashCode succesor_trail_id,
1411 struct FriendInfo *target_friend)
1413 struct PeerNotifyNewSuccessorMessage *nsm;
1414 struct P2PPendingMessage *pending;
1415 struct GNUNET_PeerIdentity *peer_list;
1418 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1419 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1421 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1427 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1429 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1433 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1434 pending->importance = 0; /* FIXME */
1435 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1436 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1437 pending->msg = &nsm->header;
1438 nsm->header.size = htons (msize);
1439 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1440 nsm->new_successor = successor;
1441 nsm->source_peer = source_peer;
1442 nsm->trail_id = succesor_trail_id;
1444 if (successor_trail_length > 0)
1446 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1447 memcpy (peer_list, successor_trail,
1448 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1451 /* Send the message to chosen friend. */
1452 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1453 target_friend->pending_count++;
1454 process_friend_queue (target_friend);
1459 * Construct an add_trail message and send it to target_friend
1460 * @param source_peer Source of the trail.
1461 * @param destination_peer Destination of the trail.
1462 * @param trail_id Unique identifier of the trail from
1463 * @a source_peer to @a destination_peer, NOT including the endpoints.
1464 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1465 * NOT including the endpoints.
1466 * @param trail_length Total number of peers in @a trail.
1467 * @param target_friend Next friend to get this message.
1470 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1471 struct GNUNET_PeerIdentity destination_peer,
1472 struct GNUNET_HashCode trail_id,
1473 struct GNUNET_PeerIdentity *trail,
1474 unsigned int trail_length,
1475 struct FriendInfo *target_friend)
1477 struct PeerAddTrailMessage *adm;
1478 struct GNUNET_PeerIdentity *peer_list;
1479 struct P2PPendingMessage *pending;
1482 msize = sizeof (struct PeerAddTrailMessage) +
1483 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1485 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1491 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1493 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1497 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1498 pending->importance = 0; /* FIXME */
1499 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1500 adm = (struct PeerAddTrailMessage *) &pending[1];
1501 pending->msg = &adm->header;
1502 adm->header.size = htons (msize);
1503 adm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL);
1504 adm->source_peer = source_peer;
1505 adm->destination_peer = destination_peer;
1506 adm->trail_id = trail_id;
1508 if (trail_length > 0)
1510 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1511 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1514 /* Send the message to chosen friend. */
1515 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1516 target_friend->pending_count++;
1517 process_friend_queue (target_friend);
1523 * Construct a trail compression message and send it to target_friend.
1524 * @param source_peer Source of the trail.
1525 * @param trail_id Unique identifier of trail.
1526 * @param first_friend First hop in compressed trail to reach from source to finger
1527 * @param target_friend Next friend to get this message.
1530 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1531 struct GNUNET_HashCode trail_id,
1532 struct GNUNET_PeerIdentity first_friend,
1533 struct FriendInfo *target_friend)
1535 struct P2PPendingMessage *pending;
1536 struct PeerTrailCompressionMessage *tcm;
1539 msize = sizeof (struct PeerTrailCompressionMessage);
1541 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1547 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1549 GNUNET_STATISTICS_update (GDS_stats,
1550 gettext_noop ("# P2P messages dropped due to full queue"),
1554 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1555 pending->importance = 0; /* FIXME */
1556 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1557 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1558 pending->msg = &tcm->header;
1559 tcm->header.size = htons (msize);
1560 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION);
1561 tcm->source_peer = source_peer;
1562 tcm->new_first_friend = first_friend;
1563 tcm->trail_id = trail_id;
1565 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1566 target_friend->pending_count++;
1567 process_friend_queue (target_friend);
1573 * Search my location in trail.
1574 * @param trail List of peers
1575 * @return my_index if found
1576 * -1 if no entry found.
1579 search_my_index (const struct GNUNET_PeerIdentity *trail,
1584 for (i = 0; i < trail_length; i++)
1586 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1594 * Check if the friend is congested or have reached maximum number of trails
1595 * it can be part of of.
1596 * @param friend Friend to be chechked.
1597 * @return #GNUNET_YES if friend is not congested or have not crossed threshold.
1598 * #GNUNET_NO if friend is either congested or have crossed threshold
1601 is_friend_congested (struct FriendInfo *friend)
1603 if ((friend->trails_count == TRAILS_THROUGH_FRIEND_THRESHOLD)||
1604 ((0 != GNUNET_TIME_absolute_get_remaining
1605 (friend->congestion_timestamp).rel_value_us)))
1613 * FIXME: here we should also check if iterator is null or not. It can be NULL
1614 * only if we insert randomly at locations. But as we are using trails_count
1615 * as the parameter, it should not happen.
1616 * Iterate over the list of all the trails of a finger. In case the first
1617 * friend to reach the finger has reached trail threshold or is congested,
1618 * then don't select it. In case there multiple available good trails to reach
1619 * to Finger, choose the one with shortest trail length.
1620 * Note: We use length as parameter. But we can use any other suitable parameter
1622 * @param finger Finger
1623 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1624 * and trail length. NULL in case none of the trails are free.
1626 static struct Selected_Finger_Trail *
1627 select_finger_trail (struct FingerInfo *finger)
1629 struct FriendInfo *friend;
1630 struct Trail *iterator;
1631 struct Selected_Finger_Trail *finger_trail;
1634 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1636 for (i = 0; i < finger->trails_count; i++)
1638 iterator = &finger->trail_list[i];
1639 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1640 &iterator->trail_head->peer);
1641 if (GNUNET_YES == is_friend_congested (friend))
1644 /* Check if the trail length of this trail is least seen so far. If yes then
1645 set finger_trail to this trail.*/
1646 if (finger_trail->trail_length > iterator->trail_length)
1648 finger_trail->friend = *friend;
1649 finger_trail->trail_id = iterator->trail_id;
1650 finger_trail->trail_length = iterator->trail_length;
1654 /* No trail found. */
1655 if (i == finger->trails_count)
1656 finger_trail = NULL;
1658 return finger_trail;
1663 * FIXME; not handling the wrap around logic correctly.
1664 * Select closest finger to value.
1665 * @param peer1 First peer
1666 * @param peer2 Second peer
1667 * @param value Value to be compare
1668 * @return Closest peer
1670 static struct GNUNET_PeerIdentity *
1671 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1672 struct GNUNET_PeerIdentity *peer2,
1675 uint64_t peer1_value;
1676 uint64_t peer2_value;
1678 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1679 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1681 if (peer1_value == value)
1686 if (peer2_value == value)
1691 if (peer1_value < peer2_value)
1693 if ((peer1_value < value) && (value < peer2_value))
1697 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1698 ((PEER_IDENTITES_WRAP_AROUND < value) && (value < peer1_value)))
1704 if (peer2_value < peer1_value)
1706 if ((peer2_value < value) && (value < peer1_value))
1710 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1711 ((PEER_IDENTITES_WRAP_AROUND < value) && (value < peer2_value)))
1721 * FIMXE: COMPLETE THE LOGIC.
1728 * 0 <= key < 5, so my_id 0 is the predecessor.
1729 * peer1 != peer2 ever.
1730 * Select closest predecessor to value.
1731 * @param peer1 First peer
1732 * @param peer2 Second peer
1733 * @param value Value to be compare
1734 * @return Closest peer
1736 static struct GNUNET_PeerIdentity *
1737 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1738 struct GNUNET_PeerIdentity *peer2,
1741 uint64_t peer1_value;
1742 uint64_t peer2_value;
1744 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1745 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1747 if (peer1_value == value)
1750 if (peer2_value == value)
1753 if (peer1_value < peer2_value)
1755 if ((peer1_value < value) && (value < peer2_value))
1757 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1758 ((PEER_IDENTITES_WRAP_AROUND < value) && (value < peer1_value)))
1762 if (peer2_value < peer1_value)
1764 if ((peer2_value < value) && (value < peer1_value))
1766 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1767 ((PEER_IDENTITES_WRAP_AROUND < value) && (value < peer2_value)))
1774 /* FIXME: select closest peer w.r.t. value. [finger->friend_id, current_successor->id)
1775 and [current_successor->id, finger->friend_id). Check in which range value lies.
1776 Also, check for wrap around. But this will give you the immediate predecessor
1777 For example. if we have 0,1,6 and I am 0 and one of my finger is 6. Then
1778 for 1, we will have ranges like [0,6) and [6,0) 1 lies in range from [0,6)
1779 but successor is 6 not 0 as 6 is > than 1. If you are the closest one,
1781 in current_successor. Want to write a generic code so that it is used in
1782 * finger_table_add also while choosing the closest one among new and existing
1791 * 0 <= key < 5, so key should go to 5.
1795 * Select the closest peer among two peers (which should not be same)
1796 * with respect to value and finger_map_index
1797 * @param peer1 First peer
1798 * @param peer2 Second peer
1799 * @param value Value relative to which we find the closest
1800 * @param finger_map_index Index in finger map. If equal to PREDECESSOR_FINGER_ID,
1801 * then we use different logic than other
1803 * @return Closest peer among two peers.
1805 static struct GNUNET_PeerIdentity *
1806 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1807 struct GNUNET_PeerIdentity *peer2,
1809 unsigned int finger_map_index)
1811 struct GNUNET_PeerIdentity *closest_peer;
1812 /* FIXME: select closest peer w.r.t. value. [friend_id, current_successor->id)
1813 and [current_successor->id, friend_id). Check in which range value lies.
1814 Also, check for wrap around. Set the value of current_successor accordingly.*/
1816 if (PREDECESSOR_FINGER_ID == finger_map_index)
1817 closest_peer = select_closest_predecessor (peer1, peer2, value);
1819 closest_peer = select_closest_finger (peer1, peer2, value);
1821 return closest_peer;
1826 * FIXME: better names and more refactoring.
1827 * Compare FINGER entry with current successor. If finger's first friend of all
1828 * its trail is not congested and has not crossed trail threshold, then check
1829 * if finger peer identity is closer to final_destination_finger_value than
1830 * current_successor. If yes then update current_successor.
1831 * @param current_successor[in/out]
1834 static struct Closest_Peer *
1835 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1837 struct FingerInfo *finger;
1838 struct FriendInfo *friend;
1839 struct Selected_Finger_Trail *finger_trail;
1840 struct GNUNET_PeerIdentity *closest_peer;
1843 for (i = 0; i < MAX_FINGERS; i++)
1845 finger = &finger_table[i];
1847 /* If I am my own finger, then ignore this finger. */
1848 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1852 /* If finger is friend. */
1853 if (NULL != (friend = GNUNET_CONTAINER_multipeermap_get
1854 (friend_peermap, &finger->finger_identity)))
1856 if (GNUNET_YES == is_friend_congested (friend))
1859 /* If not congested then compare it with current_successor. */
1860 closest_peer = select_closest_peer (&finger->finger_identity,
1861 ¤t_closest_peer->best_known_destination,
1862 current_closest_peer->destination_finger_value,
1863 current_closest_peer->is_predecessor);
1864 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1867 current_closest_peer->best_known_destination = finger->finger_identity;
1868 current_closest_peer->next_hop = finger->finger_identity;
1873 /* Choose one of the trail to reach to finger. */
1874 finger_trail = select_finger_trail (finger);
1876 /* In case no trail found, ignore this finger. */
1877 if (NULL == finger_trail)
1880 closest_peer = select_closest_peer (&finger->finger_identity,
1881 ¤t_closest_peer->best_known_destination,
1882 current_closest_peer->destination_finger_value,
1883 current_closest_peer->is_predecessor);
1884 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1887 current_closest_peer->best_known_destination = finger->finger_identity;
1888 current_closest_peer->next_hop = finger_trail->friend.id;
1889 current_closest_peer->trail_id = finger_trail->trail_id;
1893 return current_closest_peer;
1898 * Compare friend entry with current successor. If friend is not congested and
1899 * has not crossed trail threshold, then check if friend peer identity is
1900 * closer to final_destination_finger_value than current_successor. If yes
1901 * then update current_successor.
1902 * @param cls closure
1903 * @param key current public key
1904 * @param value struct Closest_Peer
1905 * @return #GNUNET_YES if we should continue to iterate,
1906 * #GNUNET_NO if not.
1909 compare_friend_and_current_closest_peer (void *cls,
1910 const struct GNUNET_PeerIdentity *key,
1913 struct FriendInfo *friend = value;
1914 struct Closest_Peer *current_closest_peer = cls;
1915 struct GNUNET_PeerIdentity *closest_peer;
1917 if (GNUNET_YES == is_friend_congested (friend))
1920 closest_peer = select_closest_peer (&friend->id,
1921 ¤t_closest_peer->best_known_destination,
1922 current_closest_peer->destination_finger_value,
1923 current_closest_peer->is_predecessor);
1925 /* If friend is the closest successor. */
1926 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id, closest_peer))
1928 current_closest_peer->best_known_destination = friend->id;
1929 current_closest_peer->next_hop = friend->id;
1936 * Initialize current_successor to my_identity.
1937 * @param my_identity My peer identity
1938 * @return current_successor
1940 static struct Closest_Peer *
1941 init_current_successor (struct GNUNET_PeerIdentity my_identity,
1942 uint64_t destination_finger_value,
1943 unsigned int is_predecessor)
1945 struct Closest_Peer *current_closest_peer;
1947 current_closest_peer = GNUNET_new (struct Closest_Peer);
1948 memset (¤t_closest_peer->trail_id, 0, sizeof (current_closest_peer->trail_id));
1949 current_closest_peer->destination_finger_value = destination_finger_value;
1950 current_closest_peer->is_predecessor = is_predecessor;
1951 current_closest_peer->next_hop = my_identity;
1952 current_closest_peer->best_known_destination = my_identity;
1954 return current_closest_peer;
1959 * Find the successor for destination_finger_value among my_identity, all my
1960 * friend and all my fingers. Don't consider friends or fingers
1961 * which are congested or have crossed the threshold.
1962 * @param destination_finger_value Peer closest to this value will be the next successor.
1963 * @param local_best_known_destination [out] Updated to my_identity if I am the
1964 * final destination. Updated to friend
1965 * identity in case a friend is successor,
1966 * updated to first friend to reach to finger
1967 * in case finger is the destination.
1968 * @param new_intermediate_trail_id [out] In case a finger is the
1969 * @a local_best_known_destination,
1970 * then it is the trail to reach it. Else
1972 * @param is_predecessor Are we looking for predecessor or finger?
1973 * @return Next hop to reach to local_best_known_destination. In case my_identity
1974 * or a friend is a local_best_known_destination, then
1975 * next_hop = local_best_known_destination. Else
1976 * next_hop is the first friend to reach to finger (local_best_known_destination)
1978 static struct GNUNET_PeerIdentity *
1979 find_successor (uint64_t destination_finger_value,
1980 struct GNUNET_PeerIdentity *local_best_known_destination,
1981 struct GNUNET_HashCode *new_intermediate_trail_id,
1982 unsigned int is_predecessor)
1984 struct Closest_Peer *current_closest_peer;
1985 struct GNUNET_PeerIdentity *next_hop;
1987 /* Initialize current_successor to my_identity. */
1988 current_closest_peer = init_current_successor (my_identity,
1989 destination_finger_value,
1992 /* Compare each friend entry with current_successor and update current_successor
1993 * with friend if its closest. */
1994 GNUNET_assert (GNUNET_SYSERR !=
1995 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
1996 &compare_friend_and_current_closest_peer,
1997 current_closest_peer));
1999 /* Compare each finger entry with current_successor and update current_successor
2000 * with finger if its closest. */
2001 compare_finger_and_current_successor (current_closest_peer);
2003 *local_best_known_destination = current_closest_peer->best_known_destination;
2004 new_intermediate_trail_id = ¤t_closest_peer->trail_id;
2005 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
2006 *next_hop = current_closest_peer->next_hop;
2013 * Construct a Put message and send it to target_peer.
2014 * @param key Key for the content
2015 * @param block_type Type of the block
2016 * @param options Routing options
2017 * @param desired_replication_level Desired replication count
2018 * @param best_known_dest Peer to which this message should reach eventually,
2019 * as it is best known destination to me.
2020 * @param intermediate_trail_id Trail id in case
2021 * @param target_peer Peer to which this message will be forwarded.
2022 * @param hop_count Number of hops traversed so far.
2023 * @param put_path_length Total number of peers in @a put_path
2024 * @param put_path Number of peers traversed so far
2025 * @param expiration_time When does the content expire
2026 * @param data Content to store
2027 * @param data_size Size of content @a data in bytes
2030 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2031 enum GNUNET_BLOCK_Type block_type,
2032 enum GNUNET_DHT_RouteOption options,
2033 uint32_t desired_replication_level,
2034 struct GNUNET_PeerIdentity *best_known_dest,
2035 struct GNUNET_HashCode *intermediate_trail_id,
2036 struct GNUNET_PeerIdentity *target_peer,
2038 uint32_t put_path_length,
2039 struct GNUNET_PeerIdentity *put_path,
2040 struct GNUNET_TIME_Absolute expiration_time,
2041 const void *data, size_t data_size)
2043 struct PeerPutMessage *ppm;
2044 struct P2PPendingMessage *pending;
2045 struct FriendInfo *target_friend;
2046 struct GNUNET_PeerIdentity *pp;
2049 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2050 sizeof (struct PeerPutMessage);
2052 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2054 put_path_length = 0;
2055 msize = data_size + sizeof (struct PeerPutMessage);
2058 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2064 /* This is the first call made from clients file. So, we should search for the
2066 if (NULL == target_peer)
2069 struct GNUNET_PeerIdentity *next_hop;
2071 memcpy (&key_value, key, sizeof (uint64_t));
2072 next_hop = find_successor (key_value, best_known_dest,
2073 intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
2074 if (0 == GNUNET_CRYPTO_cmp_peer_identity(next_hop, &my_identity))
2076 /* I am the destination but we have already done datacache_put in client file. */
2080 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2083 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2084 pending->timeout = expiration_time;
2085 ppm = (struct PeerPutMessage *) &pending[1];
2086 pending->msg = &ppm->header;
2087 ppm->header.size = htons (msize);
2088 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
2089 ppm->options = htonl (options);
2090 ppm->block_type = htonl (block_type);
2091 ppm->hop_count = htonl (hop_count + 1);
2092 ppm->desired_replication_level = htonl (desired_replication_level);
2093 ppm->put_path_length = htonl (put_path_length);
2094 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2095 ppm->best_known_destination = *best_known_dest;
2097 if (NULL == intermediate_trail_id)
2098 memset (&ppm->intermediate_trail_id, 0, sizeof (ppm->intermediate_trail_id));
2100 ppm->intermediate_trail_id = *intermediate_trail_id;
2101 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2102 if (put_path_length != 0)
2104 memcpy (pp, put_path,
2105 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2107 memcpy (&pp[put_path_length], data, data_size);
2108 if (NULL == target_friend)
2109 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer);
2110 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2111 target_friend->pending_count++;
2112 process_friend_queue (target_friend);
2118 * Construct a Get message and send it to target_peer.
2119 * @param key Key for the content
2120 * @param block_type Type of the block
2121 * @param options Routing options
2122 * @param desired_replication_level Desired replication count
2123 * @param best_known_dest
2124 * @param intermediate_trail_id
2125 * @param target_peer Peer to which this message will be forwarded.
2126 * @param hop_count Number of hops traversed so far.
2127 * @param data Content to store
2128 * @param data_size Size of content @a data in bytes
2129 * @param get_path_length Total number of peers in @a get_path
2130 * @param get_path Number of peers traversed so far
2133 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2134 enum GNUNET_BLOCK_Type block_type,
2135 enum GNUNET_DHT_RouteOption options,
2136 uint32_t desired_replication_level,
2137 struct GNUNET_PeerIdentity *best_known_dest,
2138 struct GNUNET_HashCode *intermediate_trail_id,
2139 struct GNUNET_PeerIdentity *target_peer,
2141 uint32_t get_path_length,
2142 struct GNUNET_PeerIdentity *get_path)
2144 struct PeerGetMessage *pgm;
2145 struct P2PPendingMessage *pending;
2146 struct FriendInfo *target_friend;
2147 struct GNUNET_PeerIdentity *gp;
2150 msize = sizeof (struct PeerGetMessage) +
2151 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2153 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2159 if (NULL == target_peer)
2161 struct GNUNET_PeerIdentity *next_hop;
2164 memcpy (&key_value, key, sizeof (uint64_t));
2165 // FIXME: endianess of key_value!?
2166 /* FIXME: Here you should use enum GDS_NEIGHBOURS_FINGER_TYPE in place of 0. */
2167 next_hop = find_successor (key_value, best_known_dest,
2168 intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
2170 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity,next_hop))
2172 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2173 NULL, 0, 1, &my_identity, NULL,&my_identity);
2178 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2182 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2183 pending->importance = 0; /* FIXME */
2184 pgm = (struct PeerGetMessage *) &pending[1];
2185 pending->msg = &pgm->header;
2186 pgm->header.size = htons (msize);
2187 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2188 pgm->get_path_length = htonl (get_path_length);
2190 pgm->best_known_destination = *best_known_dest;
2191 pgm->intermediate_trail_id = *intermediate_trail_id;
2192 pgm->hop_count = htonl (hop_count + 1);
2196 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2197 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2199 if (NULL == target_friend)
2200 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer);
2201 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2202 target_friend->pending_count++;
2203 process_friend_queue (target_friend);
2208 * Send the get result to requesting client.
2209 * @param key Key of the requested data.
2210 * @param type Block type
2211 * @param target_peer Next peer to forward the message to.
2212 * @param source_peer Peer which has the data for the key.
2213 * @param put_path_length Number of peers in @a put_path
2214 * @param put_path Path taken to put the data at its stored location.
2215 * @param get_path_length Number of peers in @a get_path
2216 * @param get_path Path taken to reach to the location of the key.
2217 * @param expiration When will this result expire?
2218 * @param data Payload to store
2219 * @param data_size Size of the @a data
2222 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2223 enum GNUNET_BLOCK_Type type,
2224 struct GNUNET_PeerIdentity *target_peer,
2225 struct GNUNET_PeerIdentity *source_peer,
2226 unsigned int put_path_length,
2227 const struct GNUNET_PeerIdentity *put_path,
2228 unsigned int get_path_length,
2229 struct GNUNET_PeerIdentity *get_path,
2230 struct GNUNET_TIME_Absolute expiration,
2231 const void *data, size_t data_size)
2233 struct PeerGetResultMessage *get_result;
2234 struct GNUNET_PeerIdentity *get_result_path;
2235 struct GNUNET_PeerIdentity *pp;
2236 struct P2PPendingMessage *pending;
2237 struct FriendInfo *target_friend;
2238 int current_path_index;
2241 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2242 sizeof (struct PeerPutMessage);
2244 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2250 if(get_path_length > 0)
2252 current_path_index = search_my_index(get_path, get_path_length);
2253 if (GNUNET_SYSERR == current_path_index)
2259 if (0 == current_path_index)
2261 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2262 get_path, put_path_length,
2263 put_path, type, data_size, data);
2267 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2268 pending->importance = 0;
2269 get_result = (struct PeerGetResultMessage *)&pending[1];
2270 pending->msg = &get_result->header;
2271 get_result->header.size = htons (msize);
2272 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2273 get_result->key = *key;
2274 /* FIXME: check if you are passing the correct querying_peer as described in
2275 the get_result documentation. */
2276 memcpy (&(get_result->querying_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2277 get_result->expiration_time = expiration;
2280 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2281 memcpy (get_result_path, get_path,
2282 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2283 memcpy (&get_result_path[get_path_length], data, data_size);
2285 /* FIXME: Is this correct? */
2286 if (put_path_length != 0)
2288 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2289 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2292 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2293 &get_result_path[current_path_index - 1]);
2294 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2295 target_friend->pending_count++;
2296 process_friend_queue (target_friend);
2301 * Randomly choose one of your friends (which is not congested and have not crossed
2302 * trail threshold) from the friends_peer map
2303 * @return Friend Randomly chosen friend.
2304 * NULL in case friend peermap is empty, or all the friends are either
2305 * congested or have crossed trail threshold.
2307 static struct FriendInfo *
2308 select_random_friend ()
2310 unsigned int current_size;
2313 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2314 struct GNUNET_PeerIdentity key_ret;
2315 struct FriendInfo *friend;
2317 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2318 if (0 == current_size)
2321 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2322 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2324 for (j = 0; j < index ; j++)
2325 GNUNET_assert (GNUNET_YES ==
2326 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2329 if (j == current_size)
2332 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2333 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2336 GNUNET_assert (GNUNET_YES ==
2337 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2339 (const void **)&friend));
2342 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2343 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2349 } while (j != index);
2351 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2357 * Compute 64 bit value of finger_identity to which we want to setup
2358 * the trail using chord formula.
2359 * @return finger_identity
2362 compute_finger_identity_value (unsigned int finger_index)
2366 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2367 my_id64 = GNUNET_ntohll (my_id64);
2369 /* Are we looking for immediate predecessor? */
2370 if (PREDECESSOR_FINGER_ID == finger_index)
2371 return (my_id64 -1);
2373 return (my_id64 + (unsigned long) pow (2, finger_index));
2378 * Choose a random friend and start looking for the trail to reach to
2379 * finger identity through this random friend.
2381 * @param cls closure for this task
2382 * @param tc the context under which the task is running
2385 send_find_finger_trail_message (void *cls,
2386 const struct GNUNET_SCHEDULER_TaskContext *tc)
2388 struct FriendInfo *target_friend;
2389 struct GNUNET_TIME_Relative next_send_time;
2390 struct GNUNET_HashCode trail_id;
2391 unsigned int is_predecessor;
2392 uint64_t finger_id_value;
2394 next_send_time.rel_value_us =
2395 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
2396 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2397 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2398 find_finger_trail_task =
2399 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
2402 target_friend = select_random_friend ();
2403 if (NULL == target_friend)
2408 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2409 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2414 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2415 &trail_id, sizeof (trail_id));
2417 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2418 target_friend->id, target_friend, 0, NULL,
2419 is_predecessor, trail_id, NULL);
2424 * In case there are already maximum number of possible trails to reach to a
2425 * finger, then check if the new trail's length is lesser than any of the
2427 * If yes then replace that old trail by new trail.
2429 * Note: Here we are taking length as a parameter to choose the best possible
2430 * trail, but there could be other parameters also like:
2431 * 1. duration of existence of a trail - older the better.
2432 * 2. if the new trail is completely disjoint than the
2433 * other trails, then may be choosing it is better.
2435 * @param existing_finger
2436 * @param new_finger_trail
2437 * @param new_finger_trail_length
2438 * @param new_finger_trail_id
2441 select_and_replace_trail (struct FingerInfo *existing_finger,
2442 const struct GNUNET_PeerIdentity *new_trail,
2443 unsigned int new_trail_length,
2444 struct GNUNET_HashCode new_trail_id)
2446 struct Trail *trail_list_iterator;
2447 unsigned int largest_trail_length;
2448 unsigned int largest_trail_index;
2449 struct Trail_Element *trail_element;
2452 largest_trail_length = new_trail_length;
2453 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2455 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2457 for (i = 0; i < existing_finger->trails_count; i++)
2459 trail_list_iterator = &existing_finger->trail_list[i];
2460 if (trail_list_iterator->trail_length > largest_trail_length)
2462 largest_trail_length = trail_list_iterator->trail_length;
2463 largest_trail_index = i;
2467 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2469 // tear down new trail: it's not better than the existing ones
2473 /* Send trail teardown message across the replaced trail. */
2474 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2476 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2477 GDS_ROUTING_SRC_TO_DEST,
2478 &replace_trail->trail_head->peer);
2479 /* Free the trail. */
2480 while (NULL != (trail_element = replace_trail->trail_head))
2482 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2483 replace_trail->trail_tail, trail_element);
2484 GNUNET_free (trail_element);
2487 /* Add new trial at that location. */
2489 while (i < new_trail_length)
2491 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2492 element->peer = new_trail[i];
2494 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2495 replace_trail->trail_tail,
2502 * Check if the new trail to reach to finger is unique or do we already have
2503 * such a trail present for finger.
2504 * @param existing_finger Finger identity
2505 * @param new_trail New trail to reach @a existing_finger
2506 * @param trail_length Total number of peers in new_trail.
2507 * @return #GNUNET_YES if the new trail is unique
2508 * #GNUNET_NO if same trail is already present.
2511 is_new_trail_unique (struct FingerInfo *existing_finger,
2512 const struct GNUNET_PeerIdentity *new_trail,
2513 unsigned int trail_length)
2515 struct Trail *trail_list_iterator;
2516 struct Trail_Element *trail_element;
2519 int trail_unique = GNUNET_NO;
2521 for (i = 0; i < existing_finger->trails_count; i++)
2523 trail_list_iterator = &existing_finger->trail_list[i];
2524 if (trail_list_iterator->trail_length != trail_length)
2526 trail_element = trail_list_iterator->trail_head;
2527 for (j = 0; j < trail_list_iterator->trail_length; j++)
2529 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2530 &trail_element->peer))
2532 trail_unique = GNUNET_YES;
2537 return trail_unique;
2542 * Add a new trail to existing finger.
2543 * @param existing_finger
2544 * @param new_finger_trail
2545 * @param new_finger_trail_length
2546 * @param new_finger_trail_id
2549 add_new_trail (struct FingerInfo *existing_finger,
2550 const struct GNUNET_PeerIdentity *new_trail,
2551 unsigned int new_trail_length,
2552 struct GNUNET_HashCode new_trail_id)
2554 struct Trail *trail_list_iterator;
2555 struct FriendInfo *first_friend;
2558 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2564 // FIXME checking trail_head is NOT a valid way to verify an open slot
2565 for (i = 0; existing_finger->trail_list[i].trail_head != NULL; i++)
2566 GNUNET_assert (i < MAXIMUM_TRAILS_PER_FINGER);
2568 trail_list_iterator = &existing_finger->trail_list[i];
2570 if (new_trail_length > 0)
2571 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2574 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2575 &(existing_finger->finger_identity));
2576 first_friend->trails_count++;
2577 /* FIXME; we removed this field but read fixme. */
2578 //trail_list_iterator->first_friend_trail_count = first_friend->trails_count;
2579 trail_list_iterator->trail_length = new_trail_length;
2581 for (i = 0; i < new_trail_length; i++)
2583 struct Trail_Element *element;
2584 element = GNUNET_new (struct Trail_Element);
2586 element->peer = new_trail[i];
2587 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2588 trail_list_iterator->trail_tail,
2591 existing_finger->trails_count++;
2596 * Send trail teardown message for a specific trail of a finger.
2597 * @param finger Finger whose trail is to be removed.
2598 * @param trail List of peers in trail from me to a finger, NOT including
2602 send_trail_teardown (struct FingerInfo *finger,
2603 struct Trail *trail)
2605 /* FIXME: Now source also stores a trail entry in its routing table. before
2606 sending the trail teardown, you should get next_hop from routing table.
2607 If it is NULL, it means that path is broken, then remove the trail.
2608 return a value to calling function so that if all trails are removed,
2609 then remove finger. */
2610 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2611 GDS_ROUTING_SRC_TO_DEST,
2612 &trail->trail_head->peer);
2617 * Send trail teardown message across all the trails to reach to finger.
2618 * @param finger Finger whose all the trail should be freed.
2621 send_all_finger_trails_teardown (struct FingerInfo *finger)
2623 struct Trail *trail_list_iterator;
2626 /* FIXME: here we should check if we really need this check or not.
2627 because the calling function should have checked this already. Verify*/
2628 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity, &my_identity)
2629 || (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2630 &finger->finger_identity)))
2633 for (i = 0; i < finger->trails_count; i++)
2635 trail_list_iterator = &finger->trail_list[i];
2636 send_trail_teardown (finger, trail_list_iterator);
2642 * Decrement the trail count of the first friend to reach the finger
2643 * In case finger is the friend, then decrement its trail count.
2647 decrement_friend_trail_count (struct FingerInfo *finger)
2649 struct Trail *trail_list_iterator;
2650 struct FriendInfo *target_friend;
2653 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2657 for (i = 0; i < finger->trails_count; i++)
2659 trail_list_iterator = &finger->trail_list[i];
2660 if (trail_list_iterator->trail_length > 0)
2662 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2663 &trail_list_iterator->trail_head->peer);
2666 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2667 &finger->finger_identity);
2669 // check target_friend for NULL
2670 /* FIXME: we have removed first_friend_trail_count field. */
2671 target_friend->trails_count--;
2672 //trail_list_iterator->first_friend_trail_count--;
2679 * Free a specific trail
2680 * @param trail List of peers to be freed.
2683 free_trail (struct Trail *trail)
2685 struct Trail_Element *trail_element;
2687 while (NULL != (trail_element = trail->trail_head))
2689 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2692 GNUNET_free (trail_element);
2698 * Free finger and its trail.
2699 * @param finger Finger to be freed.
2702 free_finger (struct FingerInfo *finger)
2704 struct Trail *trail_list_iterator;
2708 for (i = 0; i < finger->trails_count; i++)
2710 trail_list_iterator = &finger->trail_list[i];
2711 free_trail (trail_list_iterator);
2713 GNUNET_free (finger);
2718 * Add a new entry in finger hashmap at finger_map_index
2719 * @param finger_identity Peer Identity of new finger
2720 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2721 * @param finger_trail_length Total number of peers in @a finger_trail.
2722 * @param trail_id Unique identifier of the trail.
2723 * @param finger_map_index Index in finger hashmap.
2724 * @return #GNUNET_OK if new entry is added
2725 * #GNUNET_NO -- FIXME: need to check what value does hahsmap put
2726 * returns on failure.
2729 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2730 const struct GNUNET_PeerIdentity *finger_trail,
2731 unsigned int finger_trail_length,
2732 struct GNUNET_HashCode trail_id,
2733 unsigned int finger_map_index)
2735 struct FingerInfo *new_entry;
2736 struct FriendInfo *first_trail_hop;
2737 struct Trail *first_trail;
2740 new_entry = GNUNET_new (struct FingerInfo);
2741 new_entry->finger_identity = finger_identity;
2742 new_entry->finger_map_index = finger_map_index;
2743 new_entry->trails_count = 1;
2744 new_entry->is_present = GNUNET_YES;
2746 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2748 if (finger_trail_length > 0)
2750 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2755 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2759 first_trail_hop->trails_count++;
2760 first_trail = &new_entry->trail_list[0];
2761 /* FIXME: We have removed this field. */
2762 //first_trail->first_friend_trail_count = first_trail_hop->trails_count;
2764 while (i < finger_trail_length)
2766 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2768 element->next = NULL;
2769 element->prev = NULL;
2770 element->peer = finger_trail[i];
2771 GNUNET_CONTAINER_DLL_insert_tail (first_trail->trail_head,
2772 first_trail->trail_tail,
2778 finger_table[finger_map_index] = *new_entry;
2784 * Scan the trail to check if there is any other friend in the trail other than
2785 * first hop. If yes then shortcut the trail, send trail compression message to
2786 * peers which are no longer part of trail and send back the updated trail
2787 * and trail_length to calling function.
2788 * @param finger_identity Finger whose trail we will scan.
2789 * @param finger_trail [in, out] Trail to reach from source to finger,
2790 * @param finger_trail_length Total number of peers in original finger_trail.
2791 * @param finger_trail_id Unique identifier of the finger trail.
2792 * @return updated trail length in case we shortcut the trail, else original
2795 static struct GNUNET_PeerIdentity *
2796 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2797 const struct GNUNET_PeerIdentity *trail,
2798 unsigned int trail_length,
2799 struct GNUNET_HashCode trail_id,
2800 int *new_trail_length)
2802 struct FriendInfo *target_friend;
2803 struct GNUNET_PeerIdentity *new_trail;
2806 new_trail = GNUNET_new (struct GNUNET_PeerIdentity);
2807 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2809 *new_trail_length = 0;
2813 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
2815 if (trail_length > 0)
2817 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2819 GDS_NEIGHBOURS_send_trail_compression (my_identity,
2820 trail_id, finger_identity,
2822 *new_trail_length = 0;
2827 for (i = trail_length - 1; i > 0; i--)
2829 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
2831 struct FriendInfo *target_friend;
2834 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2836 GDS_NEIGHBOURS_send_trail_compression (my_identity,
2841 /* Copy the trail from index i to index trail_length -1 and change
2842 trail length and return */
2843 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * i);
2844 while (i < trail_length)
2846 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
2850 *new_trail_length = j+1;
2855 *new_trail_length = trail_length;
2856 memcpy (new_trail, new_trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
2862 * FIXME: Ensure that we add trail in succession in the trail list.
2863 * There are no free spots within the trail list.
2864 * Send verify successor message to your successor on all trails to reach
2866 * @param successor My current successor
2869 send_verify_successor_message (struct FingerInfo *successor)
2871 struct Trail *trail_list_iterator;
2872 struct GNUNET_HashCode trail_id;
2873 struct GNUNET_PeerIdentity next_hop;
2874 struct FriendInfo *target_friend;
2875 struct GNUNET_PeerIdentity *trail;
2876 unsigned int trail_length;
2880 for (i = 0; i < successor->trails_count; i++)
2882 trail_list_iterator = &successor->trail_list[i];
2883 GNUNET_assert (NULL != trail_list_iterator->trail_head);
2885 if (trail_list_iterator->trail_length > 0)
2887 struct Trail_Element *element;
2889 trail_length = trail_list_iterator->trail_length;
2890 trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
2892 element = trail_list_iterator->trail_head;
2893 for (j = 0; j < trail_length; j++, element = element->next)
2894 trail[j] = element->peer;
2895 next_hop = trail_list_iterator->trail_head->peer;
2901 next_hop = successor->finger_identity;
2903 trail_id = trail_list_iterator->trail_id;
2904 GNUNET_assert (NULL != (target_friend =
2905 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2907 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
2908 successor->finger_identity,
2909 trail_id, trail, trail_length,
2911 GNUNET_free_non_null (trail);
2917 * FIXME: Is it safe to assume that current_search_finger_index == finger_map_index?
2918 * Update the current search finger index.
2921 update_current_search_finger_index (struct GNUNET_PeerIdentity new_finger_identity)
2923 struct FingerInfo *successor;
2925 successor = &finger_table[0];
2927 if (0 == current_search_finger_index)
2929 current_search_finger_index = PREDECESSOR_FINGER_ID;
2931 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_finger_identity))
2933 send_verify_successor_message (successor);
2936 else if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity,
2937 &(successor->finger_identity)))
2939 current_search_finger_index = 0;
2942 current_search_finger_index = current_search_finger_index - 1;
2946 * FIXME: Is it sage to assume that finger_map_index == current_search_finger_index
2947 * Calculate finger_map_index from initial value that we send in trail setup
2949 * @param ultimate_destination_finger_value Value that we calculated from our
2950 * identity and finger_map_index.
2951 * @param is_predecessor Is the entry for predecessor or not.
2952 * @return finger_map_index which is a value between 0 <= finger_map_index <= 64
2953 * -1, if no valid finger_map_index is found.
2956 get_finger_map_index (uint64_t ultimate_destination_finger_value,
2957 unsigned int is_predecessor)
2960 int finger_map_index;
2962 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2963 my_id64 = GNUNET_ntohll (my_id64);
2965 if (1 == is_predecessor)
2967 if(1 == (my_id64 - ultimate_destination_finger_value))
2968 finger_map_index = PREDECESSOR_FINGER_ID;
2972 if (1 == (ultimate_destination_finger_value - my_id64))
2974 finger_map_index = 0;
2978 finger_map_index = log (ultimate_destination_finger_value - my_id64);
2982 if (finger_map_index > PREDECESSOR_FINGER_ID)
2983 finger_map_index = -1;
2985 return finger_map_index;
2994 remove_existing_finger (struct FingerInfo *finger)
2997 GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2998 &finger->finger_identity));
3000 send_all_finger_trails_teardown (finger);
3001 decrement_friend_trail_count (finger);
3003 free_finger (finger);
3008 * Check if there is already an entry in finger peermap for given finger map index.
3009 * If yes, then select the closest finger. If new and existing finger are same,
3010 * the check if you can store more trails. If yes then add trail, else keep the best
3011 * trails to reach to the finger. If the new finger is closest, add it.
3012 * Then, update current_search_finger_index.
3013 * @param new_finger_identity Peer Identity of new finger
3014 * @param new_finger_trail Trail to reach the new finger
3015 * @param new_finger_length Total number of peers in @a new_finger_trail.
3016 * @param is_predecessor Is this entry for predecessor in finger_peermap.
3017 * @param new_finger_trail_id Unique identifier of @new_finger_trail.
3018 * @return #GNUNET_YES if the new entry is added
3019 * #GNUNET_NO if new entry is not added, either it was discarded or
3020 * it was same as existing finger at finger map index.
3023 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3024 const struct GNUNET_PeerIdentity *finger_trail,
3025 unsigned int finger_trail_length,
3026 unsigned int is_predecessor,
3027 uint64_t finger_value,
3028 struct GNUNET_HashCode finger_trail_id)
3030 struct FingerInfo *existing_finger;
3031 struct GNUNET_PeerIdentity *closest_peer;
3032 int updated_finger_trail_length;
3033 struct GNUNET_PeerIdentity *updated_trail;
3034 unsigned int finger_map_index;
3035 unsigned int new_entry_added;
3037 new_entry_added = GNUNET_NO;
3039 finger_map_index = get_finger_map_index (finger_value,
3042 if (-1 == finger_map_index)
3044 GNUNET_break_op (0);
3045 return GNUNET_SYSERR;
3047 updated_finger_trail_length = finger_trail_length;
3049 scan_and_compress_trail (finger_identity, finger_trail,
3050 finger_trail_length, finger_trail_id,
3051 &updated_finger_trail_length);
3053 existing_finger = &finger_table[finger_map_index];
3055 /* No entry present in finger hashmap for given finger map index. */
3056 if (GNUNET_NO == existing_finger->is_present)
3058 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3059 finger_trail_id, finger_map_index);
3060 update_current_search_finger_index (finger_identity);
3064 /* If existing entry and finger identity are not same. */
3065 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3068 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3070 finger_value, finger_map_index);
3072 /* If the new finger is the closest peer. */
3073 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3075 remove_existing_finger (existing_finger);
3076 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3077 finger_trail_id, finger_map_index);
3078 new_entry_added = GNUNET_YES;
3083 /* If both new and existing entry are same as my_identity, then do nothing. */
3084 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3090 /* If the existing finger is not a friend. */
3092 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3093 &(existing_finger->finger_identity)))
3095 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3096 add_new_trail (existing_finger, updated_trail,
3097 finger_trail_length, finger_trail_id);
3099 select_and_replace_trail (existing_finger, updated_trail,
3100 finger_trail_length, finger_trail_id);
3102 new_entry_added = GNUNET_NO;
3105 update_current_search_finger_index (finger_identity);
3106 return new_entry_added;
3111 * Core handler for P2P put messages.
3112 * @param cls closure
3113 * @param peer sender of the request
3114 * @param message message
3115 * @return #GNUNET_OK to keep the connection open,
3116 * #GNUNET_SYSERR to close it (signal serious error)
3119 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3120 const struct GNUNET_MessageHeader *message)
3122 struct PeerPutMessage *put;
3123 struct GNUNET_PeerIdentity *put_path;
3124 struct GNUNET_HashCode test_key;
3125 enum GNUNET_DHT_RouteOption options;
3126 struct GNUNET_PeerIdentity best_known_dest;
3127 struct GNUNET_HashCode intermediate_trail_id;
3128 struct GNUNET_PeerIdentity *next_hop;
3132 size_t payload_size;
3135 msize = ntohs (message->size);
3136 if (msize < sizeof (struct PeerPutMessage))
3138 GNUNET_break_op (0);
3142 put = (struct PeerPutMessage *) message;
3143 putlen = ntohl (put->put_path_length);
3146 sizeof (struct PeerPutMessage) +
3147 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3149 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3151 GNUNET_break_op (0);
3155 best_known_dest = put->best_known_destination;
3156 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3157 payload = &put_path[putlen];
3158 options = ntohl (put->options);
3159 intermediate_trail_id = put->intermediate_trail_id;
3161 payload_size = msize - (sizeof (struct PeerPutMessage) +
3162 putlen * sizeof (struct GNUNET_PeerIdentity));
3164 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3165 payload, payload_size, &test_key))
3168 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3170 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3171 GNUNET_break_op (0);
3172 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3173 "PUT with key `%s' for block with key %s\n",
3174 put_s, GNUNET_h2s_full (&test_key));
3175 GNUNET_free (put_s);
3180 GNUNET_break_op (0);
3183 /* cannot verify, good luck */
3187 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3189 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3190 ntohl (put->block_type),
3192 NULL, 0, /* bloom filer */
3193 NULL, 0, /* xquery */
3194 payload, payload_size))
3196 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3197 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3200 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3201 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3202 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3203 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3204 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3205 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3207 GNUNET_break_op (0);
3212 /* extend 'put path' by sender */
3213 struct GNUNET_PeerIdentity pp[putlen + 1];
3214 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3216 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3223 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3224 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3226 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3227 GDS_ROUTING_SRC_TO_DEST);
3231 /*FIXME: Here you should use enum GDS_NEIGHBOURS_FINGER_TYPE in place of 0. */
3232 next_hop = find_successor (key_value, &best_known_dest,
3233 &intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
3236 if (NULL == next_hop)
3238 GNUNET_STATISTICS_update (GDS_stats,
3239 gettext_noop ("# Next hop to forward the packet not found "
3240 "trail setup request, packet dropped."),
3242 return GNUNET_SYSERR;
3245 GDS_CLIENTS_process_put (options,
3246 ntohl (put->block_type),
3247 ntohl (put->hop_count),
3248 ntohl (put->desired_replication_level),
3250 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3255 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop)) /* I am the final destination */
3257 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3258 &(put->key),putlen, pp, ntohl (put->block_type),
3259 payload_size, payload);
3264 GDS_NEIGHBOURS_send_put (&put->key,
3265 ntohl (put->block_type),ntohl (put->options),
3266 ntohl (put->desired_replication_level),
3267 &best_known_dest, &intermediate_trail_id, next_hop,
3268 ntohl (put->hop_count), putlen, pp,
3269 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3270 payload, payload_size);
3274 return GNUNET_SYSERR;
3279 * Core handler for p2p get requests.
3281 * @param cls closure
3282 * @param peer sender of the request
3283 * @param message message
3284 * @return #GNUNET_OK to keep the connection open,
3285 * #GNUNET_SYSERR to close it (signal serious error)
3288 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3289 const struct GNUNET_MessageHeader *message)
3291 struct PeerGetMessage *get;
3292 struct GNUNET_PeerIdentity *get_path;
3293 struct GNUNET_PeerIdentity best_known_dest;
3294 struct GNUNET_HashCode intermediate_trail_id;
3295 struct GNUNET_PeerIdentity *next_hop;
3296 uint32_t get_length;
3300 msize = ntohs (message->size);
3301 if (msize < sizeof (struct PeerGetMessage))
3303 GNUNET_break_op (0);
3307 get = (struct PeerGetMessage *)message;
3308 get_length = ntohl (get->get_path_length);
3309 best_known_dest = get->best_known_destination;
3310 intermediate_trail_id = get->intermediate_trail_id;
3311 get_path = (struct GNUNET_PeerIdentity *)&get[1];
3314 sizeof (struct PeerGetMessage) +
3315 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3317 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3319 GNUNET_break_op (0);
3323 /* Add sender to get path */
3324 struct GNUNET_PeerIdentity gp[get_length + 1];
3325 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3326 gp[get_length + 1] = *peer;
3327 get_length = get_length + 1;
3329 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3330 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3332 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3333 GDS_ROUTING_SRC_TO_DEST);
3337 /*FIXME: Here you should use enum GDS_NEIGHBOURS_FINGER_TYPE in place of 0. */
3338 next_hop = find_successor (key_value, &best_known_dest,
3339 &intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
3342 if (NULL == next_hop)
3344 GNUNET_STATISTICS_update (GDS_stats,
3345 gettext_noop ("# Next hop to forward the packet not found "
3346 "trail setup request, packet dropped."),
3348 return GNUNET_SYSERR;
3350 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop))
3352 /* I am the destination.*/
3353 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3354 struct GNUNET_PeerIdentity next_hop;
3356 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3357 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3358 get_length = get_length + 1;
3359 memcpy (&next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
3360 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3361 get_length, final_get_path,&next_hop, &my_identity);
3367 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3368 get->desired_replication_level, &best_known_dest,
3369 &intermediate_trail_id, next_hop, 0,
3372 return GNUNET_SYSERR;
3377 * Core handler for get result
3378 * @param cls closure
3379 * @param peer sender of the request
3380 * @param message message
3381 * @return #GNUNET_OK to keep the connection open,
3382 * #GNUNET_SYSERR to close it (signal serious error)
3385 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3386 const struct GNUNET_MessageHeader *message)
3388 struct PeerGetResultMessage *get_result;
3389 struct GNUNET_PeerIdentity *get_path;
3390 struct GNUNET_PeerIdentity *put_path;
3392 size_t payload_size;
3394 unsigned int getlen;
3395 unsigned int putlen;
3396 int current_path_index;
3398 msize = ntohs (message->size);
3399 if (msize < sizeof (struct PeerGetResultMessage))
3401 GNUNET_break_op (0);
3405 get_result = (struct PeerGetResultMessage *)message;
3406 getlen = ntohl (get_result->get_path_length);
3407 putlen = ntohl (get_result->put_path_length);
3410 sizeof (struct PeerGetResultMessage) +
3411 getlen * sizeof (struct GNUNET_PeerIdentity) +
3412 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3414 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3416 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3418 GNUNET_break_op (0);
3423 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
3424 payload = &get_path[getlen];
3425 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3426 getlen * sizeof (struct GNUNET_PeerIdentity));
3429 put_path = &get_path[1];
3433 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3435 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3436 getlen, get_path, putlen,
3437 put_path, get_result->type, payload_size, payload);
3442 current_path_index = search_my_index (get_path, getlen);
3443 if (GNUNET_SYSERR == current_path_index )
3446 return GNUNET_SYSERR;
3448 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3449 &get_path[current_path_index - 1],
3450 &(get_result->querying_peer), putlen, put_path,
3451 getlen, get_path, get_result->expiration_time,
3452 payload, payload_size);
3455 return GNUNET_SYSERR;
3460 * Get the best known next destination (local_dest) among your fingers, friends
3461 * and my identity. If @a current_dest is some other peer and not me, then
3462 * compare curent_dest and local_dest.
3463 * @param final_dest_finger_value Peer closest to this value will be
3464 * @a local_best_known_dest
3465 * @param local_best_known_dest[out] Updated to peer identity which is closest to
3466 * @a final_dest_finger_value.
3467 * @param new_intermediate_trail_id In case @a local_best_known_dest is a finger,
3468 * then the trail id to reach to the finger
3469 * @param is_predecessor Is source peer trying to setup trail to its predecessor
3471 * @param current_dest Peer which should get this message ultimately according
3472 * to the peer which sent me this message. It could be me
3473 * or some other peer. In case it is not me, then I am a part
3474 * of trail to reach to that peer.
3477 static struct GNUNET_PeerIdentity *
3478 get_local_best_known_next_hop (uint64_t final_dest_finger_value,
3479 struct GNUNET_PeerIdentity *local_best_known_dest,
3480 struct GNUNET_HashCode *new_intermediate_trail_id,
3481 struct GNUNET_HashCode intermediate_trail_id,
3482 unsigned int is_predecessor,
3483 struct GNUNET_PeerIdentity *current_dest)
3485 struct GNUNET_PeerIdentity *next_hop_to_local_best_known_dest;
3487 /* Choose a local best known hop among your fingers, friends and you. */
3488 next_hop_to_local_best_known_dest = find_successor (final_dest_finger_value,
3489 local_best_known_dest,
3490 new_intermediate_trail_id,
3493 /* Are we just a part of a trail towards a finger (current_destination)? */
3494 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest)))
3496 struct GNUNET_PeerIdentity *closest_peer;
3498 /* Select best successor among one found locally and current_destination
3499 * that we got from network.*/
3500 closest_peer = select_closest_peer (local_best_known_dest,
3502 final_dest_finger_value,
3505 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3506 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3508 next_hop_to_local_best_known_dest =
3509 GDS_ROUTING_get_next_hop (intermediate_trail_id,
3510 GDS_ROUTING_SRC_TO_DEST);
3511 /* FIXME: Here we found next_hop NULL from routing table, but we still
3512 * have a next_hop from find_successor should we not break and choose that
3514 if (NULL == next_hop_to_local_best_known_dest)
3516 GNUNET_break_op (0);
3520 local_best_known_dest = current_dest;
3521 *new_intermediate_trail_id = intermediate_trail_id;
3525 GNUNET_assert (NULL != next_hop_to_local_best_known_dest);
3526 return next_hop_to_local_best_known_dest;
3530 /* Core handle for PeerTrailSetupMessage.
3531 * @param cls closure
3532 * @param message message
3533 * @param peer peer identity this notification is about
3534 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3537 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3538 const struct GNUNET_MessageHeader *message)
3540 const struct PeerTrailSetupMessage *trail_setup;
3541 const struct GNUNET_PeerIdentity *trail_peer_list;
3542 struct GNUNET_PeerIdentity *local_best_known_dest;
3543 struct GNUNET_PeerIdentity current_dest;
3544 struct GNUNET_PeerIdentity *next_hop_towards_local_best_known_dest;
3545 struct GNUNET_PeerIdentity next_peer;
3546 struct FriendInfo *target_friend;
3547 struct GNUNET_PeerIdentity source;
3548 uint64_t final_dest_finger_val;
3549 struct GNUNET_HashCode new_intermediate_trail_id;
3550 struct GNUNET_HashCode intermediate_trail_id;
3551 struct GNUNET_HashCode trail_id;
3552 unsigned int is_predecessor;
3553 uint32_t trail_length;
3556 msize = ntohs (message->size);
3557 if (msize < sizeof (struct PeerTrailSetupMessage))
3559 GNUNET_break_op (0);
3563 trail_setup = (const struct PeerTrailSetupMessage *) message;
3564 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3565 sizeof (struct GNUNET_PeerIdentity);
3566 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3567 sizeof (struct GNUNET_PeerIdentity) != 0)
3569 GNUNET_break_op (0);
3573 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3574 current_dest = trail_setup->best_known_destination;
3575 trail_id = trail_setup->trail_id;
3576 final_dest_finger_val =
3577 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3578 source = trail_setup->source_peer;
3579 is_predecessor = ntohl (trail_setup->is_predecessor);
3580 intermediate_trail_id = trail_setup->intermediate_trail_id;
3582 /* Is my routing table full? */
3583 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3585 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3586 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
3587 my_identity, is_predecessor,
3588 trail_peer_list, trail_length,
3589 trail_id, target_friend,
3590 CONGESTION_TIMEOUT);
3594 local_best_known_dest = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3595 /* Get the next hop to forward the trail setup request. */
3596 next_hop_towards_local_best_known_dest =
3597 get_local_best_known_next_hop (final_dest_finger_val,
3598 local_best_known_dest,
3599 &new_intermediate_trail_id,
3600 intermediate_trail_id,
3604 /* Am I the final destination? */
3605 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (local_best_known_dest,
3608 if (0 == trail_length)
3609 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
3611 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3613 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3614 GDS_NEIGHBOURS_send_trail_setup_result (source,
3616 target_friend, trail_length,
3618 final_dest_finger_val,
3619 is_predecessor, trail_id);
3623 /* Add yourself to list of peers. */
3624 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3626 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3627 peer_list[trail_length] = my_identity;
3629 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3630 next_hop_towards_local_best_known_dest);
3631 GDS_NEIGHBOURS_send_trail_setup (source,
3632 final_dest_finger_val,
3633 *local_best_known_dest,
3634 target_friend, trail_length + 1, peer_list,
3635 is_predecessor, trail_id,
3636 &new_intermediate_trail_id);
3642 /* FIXME: here we are calculating my_index and comparing also in this function.
3643 And we are doing it again here in this function. Re factor the code. */
3645 * Check if sender_peer and peer from which we should receive the message are
3646 * same or different.
3647 * @param trail_peer_list List of peers in trail
3648 * @param trail_length Total number of peers in @a trail_peer_list
3649 * @param sender_peer Peer from which we got the message.
3650 * @param finger_identity Finger to which trail is setup. It is not part of trail.
3651 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
3652 * message are different.
3653 * #GNUNET_NO if sender_peer and peer from which we should receive the
3654 * message are different.
3657 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
3658 unsigned int trail_length,
3659 const struct GNUNET_PeerIdentity *sender_peer,
3660 struct GNUNET_PeerIdentity finger_identity,
3661 struct GNUNET_PeerIdentity source_peer)
3665 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3668 if (trail_length > 0)
3670 // source, then trail_length > 0, trail_peer_list[0] != peer
3671 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
3677 // source, trail_length == 0, finger != peer
3678 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
3685 my_index = search_my_index (trail_peer_list, trail_length);
3689 // my_index == trail_length -1, finger != peer
3690 if ((trail_length - 1) == my_index)
3692 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
3698 // FIXME: if trail_peer_list[my_index + 1] != peer
3699 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
3700 &trail_peer_list[my_index + 1]))
3709 * FIXME: we have a new field is next_hop desintation or prev_hop source.
3710 * think how to add it. I am not adding any entry in destination or source
3711 * peer routing table as in case of handle core disconnect when we remove
3712 * an entry from routing table then we send a trail teardown message and
3713 * I am not aware about source or dest. So. we can't send dest as end point.
3714 * Core handle for p2p trail setup result messages.
3716 * @param message message
3717 * @param peer sender of this message.
3718 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3721 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3722 const struct GNUNET_MessageHeader *message)
3724 const struct PeerTrailSetupResultMessage *trail_result;
3725 const struct GNUNET_PeerIdentity *trail_peer_list;
3726 struct GNUNET_PeerIdentity next_hop;
3727 struct FriendInfo *target_friend;
3728 struct GNUNET_PeerIdentity querying_peer;
3729 struct GNUNET_PeerIdentity finger_identity;
3730 uint32_t trail_length;
3731 uint64_t ulitmate_destination_finger_value;
3732 uint32_t is_predecessor;
3733 struct GNUNET_HashCode trail_id;
3737 msize = ntohs (message->size);
3738 if (msize < sizeof (struct PeerTrailSetupResultMessage))
3740 GNUNET_break_op (0);
3744 trail_result = (const struct PeerTrailSetupResultMessage *) message;
3745 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
3746 sizeof (struct GNUNET_PeerIdentity);
3747 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
3748 sizeof (struct GNUNET_PeerIdentity) != 0)
3750 GNUNET_break_op (0);
3754 is_predecessor = htonl (trail_result->is_predecessor);
3755 querying_peer = trail_result->querying_peer;
3756 finger_identity = trail_result->finger_identity;
3757 trail_id = trail_result->trail_id;
3758 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
3759 ulitmate_destination_finger_value =
3760 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
3762 /* FIXME: here we are calculating my_index and comparing also in this function.
3763 And we are doing it again here in this function. Re factor the code. */
3764 /* Ensure that sender peer is the peer from which we were expecting the message. */
3765 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
3767 peer, finger_identity, querying_peer))
3769 GNUNET_break_op (0);
3770 return GNUNET_SYSERR;
3773 /* Am I the one who initiated the query? */
3774 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer,
3777 finger_table_add (finger_identity, trail_peer_list,
3778 trail_length, ulitmate_destination_finger_value,
3779 is_predecessor, trail_id);
3783 my_index = search_my_index(trail_peer_list, trail_length);
3787 return GNUNET_SYSERR;
3791 next_hop = trail_result->querying_peer;
3793 next_hop = trail_peer_list[my_index - 1];
3795 /* If the querying_peer is its own finger, then don't add an entry in routing
3796 * table as querying peer will discard the trail.
3798 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
3799 &(trail_result->finger_identity))))
3801 GDS_ROUTING_add (trail_id, next_hop, *peer);
3804 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3805 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
3806 target_friend, trail_length, trail_peer_list,
3808 ulitmate_destination_finger_value,
3816 * @param trail Trail to be inverted
3817 * @param trail_length Total number of peers in the trail.
3818 * @return Updated trail
3820 static struct GNUNET_PeerIdentity *
3821 invert_trail (const struct GNUNET_PeerIdentity *trail,
3822 unsigned int trail_length)
3826 struct GNUNET_PeerIdentity *inverted_trail;
3828 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
3831 j = trail_length - 1;
3832 while (i < trail_length)
3834 inverted_trail[i] = trail[j];
3838 return inverted_trail;
3844 * my_current_predecessor != source_peer. get the trail to reach to
3845 * my_current_predecessor and append it to the trail from source to me.
3846 * It can contain duplicate elements. Need to get the correct one.
3847 * In case the source peer of verify successor message is not my successor,
3848 * then construct a trail from source peer to my current predecessor.
3849 * @param my_predecessor my current predecessor.
3850 * @param current_trail Trail from source to me.
3851 * @param current_trail_length Total number of peers in @a current_trail
3852 * @param new_trail_length [out] Total number of peers in updated trail.
3853 * @return Updated trail from source peer to my_predecessor.
3855 static struct GNUNET_PeerIdentity *
3856 trail_source_to_my_predecessor (const struct GNUNET_PeerIdentity *current_trail,
3857 unsigned int current_trail_length,
3858 unsigned int *new_trail_length)
3860 struct GNUNET_PeerIdentity *new_trail;
3861 struct Trail *trail_list_iterator;
3862 struct Trail_Element *trail_iterator;
3863 struct FingerInfo *my_predecessor;
3866 unsigned int shortest_trail_length = 0;
3867 unsigned int trail_index = 0;
3869 my_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
3871 for (i = 0; i < my_predecessor->trails_count; i++)
3873 trail_list_iterator = &my_predecessor->trail_list[i];
3874 if (trail_list_iterator->trail_length > shortest_trail_length)
3876 shortest_trail_length = trail_list_iterator->trail_length;
3880 *new_trail_length = current_trail_length + shortest_trail_length + 1;
3881 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
3883 memcpy (new_trail, current_trail,
3884 current_trail_length * sizeof (struct GNUNET_PeerIdentity));
3885 new_trail[current_trail_length + 1] = my_identity;
3888 j = current_trail_length + 1;
3889 trail_list_iterator = &my_predecessor->trail_list[trail_index];
3890 trail_iterator = trail_list_iterator->trail_head;
3891 while ( i < shortest_trail_length)
3893 new_trail[j] = trail_iterator->peer;
3896 trail_iterator = trail_iterator->next;
3899 *new_trail_length = j;
3905 * Add finger as your predecessor. To add, first generate a new trail id, invert
3906 * the trail to get the trail from me to finger, add an entry in your routing
3907 * table, send add trail message to peers which are part of trail from me to
3908 * finger and add finger in finger table.
3911 * @param trail_length
3914 update_predecessor (struct GNUNET_PeerIdentity *finger,
3915 struct GNUNET_PeerIdentity *trail,
3916 unsigned int trail_length)
3918 struct GNUNET_HashCode *trail_to_new_predecessor_id;
3919 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
3920 struct FriendInfo *target_friend;
3922 /* Generate trail id for trail from me to new predecessor = finger. */
3923 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
3924 &trail_to_new_predecessor_id,
3925 sizeof (trail_to_new_predecessor_id));
3927 /* Invert the trail from finger to me to get the trail from me to finger. */
3928 trail_to_new_predecessor = invert_trail (trail, trail_length);
3929 if (trail_length > 0)
3931 /* Add an entry in your routing table. */
3932 GDS_ROUTING_add (*trail_to_new_predecessor_id,
3933 trail_to_new_predecessor[trail_length - 1],
3937 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3938 &trail_to_new_predecessor[trail_length - 1]);
3940 /* Add entry in routing table of all peers that are part of trail from me
3942 GDS_NEIGHBOURS_send_add_trail (my_identity,
3944 *trail_to_new_predecessor_id,
3945 trail_to_new_predecessor,
3949 add_new_finger (*finger, trail_to_new_predecessor, trail_length,
3950 *trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
3954 /* 3. In case you are successor, then
3955 * 3.1 check if you have a predecessor
3956 * 3.2 if no predecessor, then add the source of this message as your
3957 * predecessor. To add, first you should generate a new trail id,
3958 * invert the trail, send add trail message across new trail, add
3959 * an entry in finger table. Now, destination also have routing
3960 * table entry so add in your routing table also.
3961 * 3.3 If its closer than existing one, then do everything in step 1 and
3962 * free existing finger.
3963 * 3.3 If its same as the old one, then do nothing.
3964 * 3.4 if its not same as old one, and between source and old one, old one
3965 * is the correct predecessor, then construct a trail from source
3966 * to your old successor. scan the trail to remove duplicate entries.
3967 * 4. send verify successor result, with trail id of trail from source to
3968 * me. And also send the new trail from source to reach to its probable
3971 * 1. this function is called from both verify and notify.
3972 * 2. so write in a way that it is used in both.
3975 * Check if you have a predecessor.
3976 * 1. if no predecessor, then add finger as your predecessor. To add, first
3977 * generate a new trail id, invert the trail to get the trail from me to finger,
3978 * add an entry in your routing table, send add trail message to peers which
3979 * are part of trail from me to finger and add finger in finger table.
3980 * 2. If there is a predecessor, then compare existing one and finger.
3981 * 2.1 If finger is correct predecessor, then remove current_predecessor. And
3982 * do everything in step 1 to add finger into finger table.
3983 * 2.2 If current_predecessor is correct predecessor, the construct a trail from
3984 * finger to current_predecessor.
3987 * @param trail_length
3991 compare_and_update_predecessor (struct GNUNET_PeerIdentity *finger,
3992 struct GNUNET_PeerIdentity *trail,
3993 unsigned int trail_length)
3995 struct FingerInfo *current_predecessor;
3996 struct GNUNET_PeerIdentity *closest_peer;
3997 uint64_t predecessor_value;
3999 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4001 /* No predecessor. Add finger as your predecessor. */
4002 if (NULL == current_predecessor) /*FIXME: is it correct value to check if there is no predecessor. */
4004 update_predecessor (finger, trail, trail_length);
4008 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4009 closest_peer = select_closest_peer (finger,
4010 ¤t_predecessor->finger_identity,
4011 predecessor_value, PREDECESSOR_FINGER_ID);
4013 /* Finger is the closest predecessor. Remove the existing one and add the new
4015 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, finger))
4017 remove_existing_finger (current_predecessor);
4018 update_predecessor (finger, trail, trail_length);
4024 /* Core handle for p2p verify successor messages.
4025 * @param cls closure
4026 * @param message message
4027 * @param peer peer identity this notification is about
4028 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4031 handle_dht_p2p_verify_successor(void *cls,
4032 const struct GNUNET_PeerIdentity *peer,
4033 const struct GNUNET_MessageHeader *message)
4036 * 1. check if you are the successor or not.
4037 * 2. if not then get the next hop from routing table, and pass the message,
4038 * 3. In case you are successor, then
4039 * 3.1 check if you have a predecessor
4040 * 3.2 if no predecessor, then add the source of this message as your
4041 * predecessor. To add, first you should generate a new trail id,
4042 * invert the trail, send add trail message across new trail, add
4043 * an entry in finger table. Now, destination also have routing
4044 * table entry so add in your routing table also.
4045 * 3.3 If its closer than existing one, then do everything in step 1 and
4046 * free existing finger.
4047 * 3.3 If its same as the old one, then do nothing.
4048 * 3.4 if its not same as old one, and between source and old one, old one
4049 * is the correct predecessor, then construct a trail from source
4050 * to your old successor. scan the trail to remove duplicate entries.
4051 * 4. send verify successor result, with trail id of trail from source to
4052 * me. And also send the new trail from source to reach to its probable
4055 const struct PeerVerifySuccessorMessage *vsm;
4056 struct GNUNET_HashCode trail_id;
4057 struct GNUNET_PeerIdentity successor;
4058 struct GNUNET_PeerIdentity source_peer;
4059 struct GNUNET_PeerIdentity *trail;
4060 struct GNUNET_PeerIdentity *next_hop;
4061 struct GNUNET_PeerIdentity *new_trail;
4062 struct FingerInfo *current_predecessor;
4063 struct FriendInfo *target_friend;
4064 unsigned int new_trail_length;
4066 unsigned int trail_length;
4068 msize = ntohs (message->size);
4069 if (msize != sizeof (struct PeerVerifySuccessorMessage))
4071 GNUNET_break_op (0);
4075 vsm = (const struct PeerVerifySuccessorMessage *) message;
4076 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4077 sizeof (struct GNUNET_PeerIdentity);
4078 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4079 sizeof (struct GNUNET_PeerIdentity) != 0)
4081 GNUNET_break_op (0);
4085 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4086 source_peer = vsm->source_peer;
4087 successor = vsm->successor;
4088 trail_id = vsm->trail_id;
4090 /* I am not the successor of source_peer. Pass the message to next_hop on
4092 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4094 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4095 if (NULL == next_hop)
4098 return GNUNET_SYSERR;
4100 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4101 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4102 trail_id, trail, trail_length,
4107 /* I am the successor of this message. */
4109 compare_and_update_predecessor (&source_peer, trail, trail_length);
4111 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4112 /* Is source of this message my predecessor. */
4113 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4117 new_trail_length = 0;
4121 /* Get the path from source to my predecessor. This predecessor can be
4122 source's successor. */
4124 new_trail = trail_source_to_my_predecessor (trail, trail_length,
4128 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4129 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4130 current_predecessor->finger_identity,
4131 trail_id, new_trail,
4133 GDS_ROUTING_DEST_TO_SRC,
4139 /* Core handle for p2p verify successor result messages.
4140 * @param cls closure
4141 * @param message message
4142 * @param peer peer identity this notification is about
4143 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4146 handle_dht_p2p_verify_successor_result(void *cls,
4147 const struct GNUNET_PeerIdentity *peer,
4148 const struct GNUNET_MessageHeader *message)
4151 * 1. If you are not the querying peer then pass on the message,
4152 * 2, If you are querying peer, then
4153 * 2,1 is new successor same as old one
4154 * 2,1,1 if yes then do noting
4155 * 2,1,2 if no then you need to notify the new one about your existence,
4156 * 2.1.2,1 also you need to remove the older predecessor, remove entry
4157 * from finger table, send trail teardown message,
4158 * call notify new successor with new trail id and new trail to reach it.
4160 const struct PeerVerifySuccessorResultMessage *vsrm;
4161 enum GDS_ROUTING_trail_direction trail_direction;
4162 struct GNUNET_PeerIdentity querying_peer;
4163 struct GNUNET_HashCode trail_id;
4164 struct GNUNET_PeerIdentity *next_hop;
4165 struct FriendInfo *target_friend;
4166 struct GNUNET_PeerIdentity current_predecessor;
4167 struct GNUNET_PeerIdentity *trail;
4168 unsigned int trail_length;
4171 msize = ntohs (message->size);
4172 if (msize != sizeof (struct PeerVerifySuccessorResultMessage))
4174 GNUNET_break_op (0);
4178 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
4179 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4180 sizeof (struct GNUNET_PeerIdentity);
4181 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4182 sizeof (struct GNUNET_PeerIdentity) != 0)
4184 GNUNET_break_op (0);
4188 trail = (struct GNUNET_PeerIdentity *) &vsrm[1];
4189 querying_peer = vsrm->querying_peer;
4190 trail_direction = ntohl (vsrm->trail_direction);
4191 trail_id = vsrm->trail_id;
4192 current_predecessor = vsrm->current_predecessor;
4194 /* I am the querying_peer. */
4195 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4197 //Fixme: you check if successor is same of different. if differentthen
4198 // send notify new successor. in that function we will add in trail. scan
4199 // and compress the trail too.
4202 /*If you are not the querying peer then pass on the message */
4203 GNUNET_assert (NULL != (next_hop =
4204 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
4205 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4206 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4207 vsrm->source_successor,
4208 current_predecessor, trail_id,
4211 trail_direction, target_friend);
4217 * Core handle for p2p notify new successor messages.
4218 * @param cls closure
4219 * @param message message
4220 * @param peer peer identity this notification is about
4221 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4224 handle_dht_p2p_notify_new_successor(void *cls,
4225 const struct GNUNET_PeerIdentity *peer,
4226 const struct GNUNET_MessageHeader *message)
4228 const struct PeerNotifyNewSuccessorMessage *nsm;
4229 struct GNUNET_PeerIdentity *trail;
4230 struct GNUNET_PeerIdentity source;
4231 struct GNUNET_PeerIdentity new_successor;
4232 struct GNUNET_HashCode trail_id;
4233 struct GNUNET_PeerIdentity next_hop;
4234 struct FriendInfo *target_friend;
4237 uint32_t trail_length;
4239 msize = ntohs (message->size);
4240 if (msize != sizeof (struct PeerNotifyNewSuccessorMessage))
4242 GNUNET_break_op (0);
4246 nsm = (struct PeerNotifyNewSuccessorMessage *) message;
4247 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
4248 sizeof (struct GNUNET_PeerIdentity);
4249 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4250 sizeof (struct GNUNET_PeerIdentity) != 0)
4252 GNUNET_break_op (0);
4256 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
4257 source = nsm->source_peer;
4258 new_successor = nsm->new_successor;
4259 trail_id = nsm->trail_id;
4263 /* I am the new_successor to source_peer. */
4264 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
4266 /* Add an entry in routing table. */
4267 GDS_ROUTING_add (trail_id, *peer, my_identity);
4268 compare_and_update_predecessor (&source, trail, trail_length);
4272 /* I am part of trail to reach to successor. */
4273 my_index = search_my_index (trail, trail_length);
4276 GNUNET_break_op (0);
4277 return GNUNET_SYSERR;
4279 if (trail_length == my_index)
4280 next_hop = new_successor;
4282 next_hop = trail[my_index + 1];
4284 /* Add an entry in routing table for trail from source to its new successor. */
4285 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
4286 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4287 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
4289 trail_id, target_friend);
4296 * FIXME: Here you should keep the trail id with you.
4297 * Core handler for P2P trail rejection message
4298 * @param cls closure
4299 * @param message message
4300 * @param peer peer identity this notification is about
4301 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4304 handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
4305 const struct GNUNET_MessageHeader *message)
4307 struct PeerTrailRejectionMessage *trail_rejection;
4308 unsigned int trail_length;
4309 struct GNUNET_PeerIdentity *trail_peer_list;
4310 struct FriendInfo *target_friend;
4311 struct GNUNET_TIME_Relative congestion_timeout;
4312 struct GNUNET_HashCode trail_id;
4313 struct GNUNET_PeerIdentity next_destination;
4314 struct GNUNET_HashCode new_intermediate_trail_id;
4315 struct GNUNET_PeerIdentity next_peer;
4316 struct GNUNET_PeerIdentity source;
4317 struct GNUNET_PeerIdentity *next_hop;
4318 uint64_t ultimate_destination_finger_value;
4319 unsigned int is_predecessor;
4322 msize = ntohs (message->size);
4323 if (msize != sizeof (struct PeerTrailRejectionMessage))
4325 GNUNET_break_op (0);
4329 trail_rejection = (struct PeerTrailRejectionMessage *) message;
4330 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
4331 sizeof (struct GNUNET_PeerIdentity);
4332 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4333 sizeof (struct GNUNET_PeerIdentity) != 0)
4335 GNUNET_break_op (0);
4339 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
4340 is_predecessor = ntohl (trail_rejection->is_predecessor);
4341 congestion_timeout = trail_rejection->congestion_time;
4342 source = trail_rejection->source_peer;
4343 trail_id = trail_rejection->trail_id;
4344 ultimate_destination_finger_value =
4345 trail_rejection->ultimate_destination_finger_value;
4347 /* First set the congestion time of the friend that sent you this message. */
4348 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4349 target_friend->congestion_timestamp = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
4350 congestion_timeout);
4352 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
4357 /* If I am congested then pass this message to peer before me in trail. */
4358 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
4360 struct GNUNET_PeerIdentity *new_trail;
4361 unsigned int new_trail_length;
4363 if (trail_length == 1)
4366 new_trail_length = 0;
4371 next_hop = &trail_peer_list[trail_length - 2];
4372 /* Remove myself from the trail. */
4373 new_trail_length = trail_length -1;
4374 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4375 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4378 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4379 GDS_NEIGHBOURS_send_trail_rejection (source,
4380 ultimate_destination_finger_value,
4381 my_identity, is_predecessor,
4382 new_trail,new_trail_length,trail_id,
4383 target_friend, CONGESTION_TIMEOUT);
4387 /* Look for next_hop to pass the trail setup message */
4388 next_hop = find_successor (ultimate_destination_finger_value,
4390 &new_intermediate_trail_id,
4393 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
4395 if (0 == trail_length)
4398 next_peer = trail_peer_list[trail_length-1];
4400 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
4401 GDS_NEIGHBOURS_send_trail_setup_result (source,
4403 target_friend, trail_length,
4406 ultimate_destination_finger_value,
4411 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4413 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
4414 peer_list[trail_length] = my_identity;
4416 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4417 GDS_NEIGHBOURS_send_trail_setup (source,
4418 ultimate_destination_finger_value,
4420 target_friend, trail_length + 1, peer_list,
4421 is_predecessor, trail_id,
4422 &new_intermediate_trail_id);
4429 * Core handle for p2p trail tear down messages.
4430 * @param cls closure
4431 * @param message message
4432 * @param peer peer identity this notification is about
4433 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4436 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
4437 const struct GNUNET_MessageHeader *message)
4439 const struct PeerTrailCompressionMessage *trail_compression;
4440 struct GNUNET_PeerIdentity *next_hop;
4441 struct FriendInfo *target_friend;
4442 struct GNUNET_HashCode trail_id;
4445 msize = ntohs (message->size);
4446 if (msize != sizeof (struct PeerTrailCompressionMessage))
4448 GNUNET_break_op (0);
4452 trail_compression = (const struct PeerTrailCompressionMessage *) message;
4453 trail_id = trail_compression->trail_id;
4455 /* Am I the new first friend to reach to finger of this trail. */
4456 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->new_first_friend),
4459 GDS_ROUTING_update_trail_prev_hop (trail_id,
4460 trail_compression->source_peer);
4464 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4465 if (NULL == next_hop)
4471 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
4472 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4473 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
4475 trail_compression->new_first_friend,
4482 * Core handler for trail teardown message.
4483 * @param cls closure
4484 * @param message message
4485 * @param peer sender of this messsage.
4486 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4489 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
4490 const struct GNUNET_MessageHeader *message)
4492 const struct PeerTrailTearDownMessage *trail_teardown;
4493 enum GDS_ROUTING_trail_direction trail_direction;
4494 struct GNUNET_HashCode trail_id;
4495 struct GNUNET_PeerIdentity *next_hop;
4498 msize = ntohs (message->size);
4499 if (msize != sizeof (struct PeerTrailTearDownMessage))
4501 GNUNET_break_op (0);
4505 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
4506 trail_direction = ntohl (trail_teardown->trail_direction);
4507 trail_id = trail_teardown->TRAIL_ID;
4510 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
4511 if (NULL == next_hop)
4514 return GNUNET_SYSERR;
4517 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
4519 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
4522 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, next_hop);
4528 * Fixme: this function is called only in case in notify new successor, the new
4529 * successor wants to add the source of the peer as its predecessor. Identify
4530 * if there is any other use case where it is required and if yes then adapt the
4532 * Core handle for p2p add trail message.
4533 * @param cls closure
4534 * @param message message
4535 * @param peer peer identity this notification is about
4536 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4539 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
4540 const struct GNUNET_MessageHeader *message)
4542 struct PeerAddTrailMessage *add_trail;
4543 struct GNUNET_PeerIdentity *trail;
4544 struct GNUNET_HashCode trail_id;
4545 struct GNUNET_PeerIdentity destination_peer;
4546 struct GNUNET_PeerIdentity source_peer;
4547 struct GNUNET_PeerIdentity next_hop;
4548 unsigned int trail_length;
4549 unsigned int my_index;
4552 msize = ntohs (message->size);
4553 if (msize != sizeof (struct PeerAddTrailMessage))
4555 GNUNET_break_op (0);
4559 add_trail = (struct PeerAddTrailMessage *) message;
4560 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
4561 sizeof (struct GNUNET_PeerIdentity);
4562 if ((msize - sizeof (struct PeerAddTrailMessage)) %
4563 sizeof (struct GNUNET_PeerIdentity) != 0)
4565 GNUNET_break_op (0);
4569 if ((msize < sizeof (struct PeerAddTrailMessage) +
4570 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
4572 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
4574 GNUNET_break_op (0);
4578 trail = (struct GNUNET_PeerIdentity *)&add_trail[1];
4579 destination_peer = add_trail->destination_peer;
4580 source_peer = add_trail->source_peer;
4581 trail_id = add_trail->trail_id;
4583 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
4586 struct FriendInfo *target_friend;
4588 my_index = search_my_index (trail, trail_length);
4589 if (GNUNET_SYSERR == my_index)
4591 GNUNET_break_op (0);
4592 return GNUNET_SYSERR;
4596 next_hop = source_peer;
4598 next_hop = trail[trail_length - 1];
4600 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
4601 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4602 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
4603 trail, trail_length, target_friend);
4610 * Send trail teardown and free the trail of the finger for which the first
4611 * friend to reach to a finger is disconnected_peer
4612 * @param disconnected_peer
4613 * @param remove_finger
4616 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_peer,
4617 struct FingerInfo *remove_finger)
4620 unsigned int matching_trails_count;
4621 struct Trail *trail;
4623 matching_trails_count = 0;
4624 for (i = 0; i < remove_finger->trails_count; i++)
4626 trail = &remove_finger->trail_list[i];
4628 /* First friend to reach to finger is disconnected_peer. */
4629 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
4632 matching_trails_count++;
4633 send_trail_teardown (remove_finger, trail);
4637 return matching_trails_count;
4642 * Iterate over finger_table entries. Check if disconnected_peer is a finger. If
4643 * yes then free that entry.
4644 * Check if disconnected peer is the first friend in the trail to reach to a finger.
4645 * If disconnected peer is the first friend in not all of the trails to reach
4646 * a finger then send only trail teardown message for those trails and don't
4647 * free the finger entry.
4648 * If disconnected peer is the first friend in all of the trails to reach a finger,
4649 * then send trail teardown message and free finger.
4650 * @param disconnected_peer Peer which got disconnected.
4653 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
4655 struct FingerInfo *remove_finger;
4657 int matching_trails_count;
4659 for (i = 0; i < MAX_FINGERS; i++)
4661 remove_finger = &finger_table[i];
4663 if (GNUNET_NO == remove_finger->is_present)
4666 /* I am my own finger, then ignore this finger. */
4667 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer, &my_identity))
4670 /* Is disconnected peer my finger? */
4671 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
4672 &remove_finger->finger_identity))
4674 memset ((void *)&finger_table[i], 0, sizeof (struct FingerInfo));
4675 /* We don't call send_find_finger_trail, as we have no trail to reach to
4677 GNUNET_free (remove_finger);
4682 /* Iterate over the list of trails to reach to remove_finger.*/
4683 matching_trails_count = remove_matching_trails (disconnected_peer, remove_finger);
4685 /* All the trails of the finger has disconnected peer as the first friend,
4686 so free the finger. */
4687 /* FIXME; Here we assume that only in case of a finger which is a friend or
4688 my_identity only then trails count is 0. and we will not reach here in
4689 those cases. So, we can free the finger. Verify that we don't increment
4690 the trail count in case of finger == friend or my_ienity. */
4691 remove_finger->trails_count =
4692 remove_finger->trails_count - matching_trails_count;
4693 if (0 == remove_finger->trails_count)
4695 GNUNET_free (remove_finger);
4702 * Method called whenever a peer disconnects.
4704 * @param cls closure
4705 * @param peer peer identity this notification is about
4708 handle_core_disconnect (void *cls,
4709 const struct GNUNET_PeerIdentity *peer)
4711 struct FriendInfo *remove_friend;
4713 /* If disconnected to own identity, then return. */
4714 if (0 == memcmp (&my_identity, peer,
4715 sizeof (struct GNUNET_PeerIdentity)))
4718 GNUNET_assert (NULL != (remove_friend =
4719 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4721 /* Remove fingers with peer as first friend or if peer is a finger. */
4722 remove_matching_fingers (peer);
4724 /* Remove any trail of which peer is a part of. */
4725 GDS_ROUTING_remove_trail_by_peer (peer);
4727 GNUNET_assert (GNUNET_YES ==
4728 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
4732 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
4735 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4737 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4738 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4746 * Method called whenever a peer connects.
4748 * @param cls closure
4749 * @param peer_identity peer identity this notification is about
4752 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
4754 struct FriendInfo *friend;
4756 /* Check for connect to self message */
4757 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
4760 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
4762 /* If peer already exists in our friend_peermap, then exit. */
4763 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
4769 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
4772 friend = GNUNET_new (struct FriendInfo);
4773 friend->id = *peer_identity;
4775 GNUNET_assert (GNUNET_OK ==
4776 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
4777 peer_identity, friend,
4778 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
4780 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
4781 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
4782 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
4787 * To be called on core init/fail.
4789 * @param cls service closure
4790 * @param identity the public identity of this peer
4793 core_init (void *cls,
4794 const struct GNUNET_PeerIdentity *identity)
4796 my_identity = *identity;
4801 * Initialize finger table.
4804 finger_table_init ()
4808 for(i = 0; i < MAX_FINGERS; i++)
4809 finger_table[i].is_present = GNUNET_NO;
4814 * Initialize neighbours subsystem.
4815 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4818 GDS_NEIGHBOURS_init (void)
4820 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
4821 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
4822 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
4823 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
4824 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
4825 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
4826 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
4827 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
4828 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
4829 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
4830 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION,
4831 sizeof (struct PeerTrailCompressionMessage)},
4832 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN,
4833 sizeof (struct PeerTrailTearDownMessage)},
4834 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL, 0},
4839 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
4840 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
4841 GNUNET_NO, core_handlers);
4842 if (NULL == core_api)
4843 return GNUNET_SYSERR;
4845 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
4846 finger_table_init ();
4853 * Shutdown neighbours subsystem.
4856 GDS_NEIGHBOURS_done (void)
4858 if (NULL == core_api)
4861 GNUNET_CORE_disconnect (core_api);
4864 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
4865 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
4866 friend_peermap = NULL;
4868 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4871 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4872 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4880 * @return my identity
4882 struct GNUNET_PeerIdentity
4883 GDS_NEIGHBOURS_get_my_id (void)