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?
56 * 4. make sure you are adding trail for end point of trail everywhere.
57 * 5. Should we increment the trail count of a friend which is a finger.
59 * 8. Check everywhere if the peer from which you got the message is correct or
61 * 9. if finger is a friend then don't add any entry in routing table of the
65 * Should we add an entry in our routing table if I am the immediate friend
66 * and finger also. Yes add it at the moment later we can remove it if it does
67 * not look correct. In notify new successor we add a new trail irrespective
68 * that the trail is destination or not.
72 * Maximum possible fingers (including predecessor) of a peer
74 #define MAX_FINGERS 65
77 * Maximum allowed number of pending messages per friend peer.
79 #define MAXIMUM_PENDING_PER_FRIEND 64
82 * How long to wait before sending another find finger trail request
84 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
87 * How long at most to wait for transmission of a request to a friend ?
89 #define GET_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
92 * Duration for which I may remain congested.
93 * Note: Its a static value. In future, a peer may do some analysis and calculate
94 * congestion_timeout based on 'some' parameters.
96 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
99 * Maximum number of trails allowed to go through a friend.
101 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
104 * Maximum number of trails stored per finger.
106 #define MAXIMUM_TRAILS_PER_FINGER 2
109 * Finger map index for predecessor entry in finger table.
111 #define PREDECESSOR_FINGER_ID 64
114 * Wrap around in peer identity circle.
115 * FIXME: not used anywhere, should be used in
116 * find_successor() while comparing two peers.
118 #define PEER_IDENTITES_WRAP_AROUND pow(2, 64) - 1
121 * To check if a finger is predecessor or not.
123 enum GDS_NEIGHBOURS_finger_type
125 GDS_FINGER_TYPE_PREDECESSOR = 0,
126 GDS_FINGER_TYPE_NON_PREDECESSOR = 1
129 GNUNET_NETWORK_STRUCT_BEGIN
134 struct PeerPutMessage
137 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
139 struct GNUNET_MessageHeader header;
144 uint32_t options GNUNET_PACKED;
149 uint32_t block_type GNUNET_PACKED;
154 uint32_t hop_count GNUNET_PACKED;
157 * Replication level for this message
158 * In the current implementation, this value is not used.
160 uint32_t desired_replication_level GNUNET_PACKED;
163 * Length of the PUT path that follows (if tracked).
165 uint32_t put_path_length GNUNET_PACKED;
168 * Best known destination (could be my friend or finger) which should
169 * get this message next.
171 struct GNUNET_PeerIdentity best_known_destination;
174 * In case best_known_destination is a finger, then trail to reach
175 * to that finger. Else its default value is 0.
177 struct GNUNET_HashCode intermediate_trail_id;
180 * When does the content expire?
182 struct GNUNET_TIME_AbsoluteNBO expiration_time;
185 * The key to store the value under.
187 struct GNUNET_HashCode key GNUNET_PACKED;
189 /* put path (if tracked) */
198 struct PeerGetMessage
201 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
203 struct GNUNET_MessageHeader header;
208 uint32_t options GNUNET_PACKED;
211 * Desired content type.
213 uint32_t block_type GNUNET_PACKED;
218 uint32_t hop_count GNUNET_PACKED;
221 * Desired replication level for this request.
222 * In the current implementation, this value is not used.
224 uint32_t desired_replication_level GNUNET_PACKED;
227 * Total number of peers in get path.
229 unsigned int get_path_length;
232 * Best known destination (could be my friend or finger) which should
233 * get this message next.
235 struct GNUNET_PeerIdentity best_known_destination;
238 * In case best_known_destination is a finger, then trail to reach
239 * to that finger. Else its default value is 0.
241 struct GNUNET_HashCode intermediate_trail_id;
244 * The key we are looking for.
246 struct GNUNET_HashCode key;
255 struct PeerGetResultMessage
258 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
260 struct GNUNET_MessageHeader header;
263 * The type for the data.
265 uint32_t type GNUNET_PACKED;
268 * Number of peers recorded in the outgoing path from source to the
269 * stored location of this message.
271 uint32_t put_path_length GNUNET_PACKED;
274 * Length of the GET path that follows (if tracked).
276 uint32_t get_path_length GNUNET_PACKED;
279 * Peer which queried for get and should get the result.
281 struct GNUNET_PeerIdentity querying_peer;
284 * When does the content expire?
286 struct GNUNET_TIME_Absolute expiration_time;
289 * The key of the corresponding GET request.
291 struct GNUNET_HashCode key;
293 /* put path (if tracked) */
295 /* get path (if tracked) */
302 * P2P Trail setup message
304 struct PeerTrailSetupMessage
307 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
309 struct GNUNET_MessageHeader header;
312 * Is source_peer trying to setup the trail to a predecessor or any finger.
314 uint32_t is_predecessor;
317 * Peer closest to this value will be our finger.
319 uint64_t final_destination_finger_value;
322 * Source peer which wants to setup the trail to one of its finger.
324 struct GNUNET_PeerIdentity source_peer;
327 * Best known destination (could be my friend or finger) which should
328 * get this message next.
330 struct GNUNET_PeerIdentity best_known_destination;
333 * In case best_known_destination is a finger, then trail id of trail to
334 * reach to this finger.
336 struct GNUNET_HashCode intermediate_trail_id;
339 * Trail id for trail which we are trying to setup.
341 struct GNUNET_HashCode trail_id;
343 /* List of peers which are part of trail setup so far.
344 * Trail does NOT include source_peer and peer which will be closest to
345 * ultimate_destination_finger_value.
346 * struct GNUNET_PeerIdentity trail[]
351 * P2P Trail Setup Result message
353 struct PeerTrailSetupResultMessage
357 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
359 struct GNUNET_MessageHeader header;
362 * Finger to which we have found the path.
364 struct GNUNET_PeerIdentity finger_identity;
367 * Peer which started trail_setup to find trail to finger_identity
369 struct GNUNET_PeerIdentity querying_peer;
372 * Is the trail setup to querying_peer's predecessor or finger?
374 uint32_t is_predecessor;
377 * Value to which finger_identity is the closest peer.
379 uint64_t ulitmate_destination_finger_value;
382 * Identifier of the trail from querying peer to finger_identity, NOT
383 * including both endpoints.
385 struct GNUNET_HashCode trail_id;
387 /* List of peers which are part of the trail from querying peer to
388 * finger_identity, NOT including both endpoints.
389 * struct GNUNET_PeerIdentity trail[]
394 * P2P Verify Successor Message.
396 struct PeerVerifySuccessorMessage
399 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
401 struct GNUNET_MessageHeader header;
404 * Peer which wants to verify its successor.
406 struct GNUNET_PeerIdentity source_peer;
409 * Source Peer's current successor.
411 struct GNUNET_PeerIdentity successor;
414 * Identifier of trail to reach from source_peer to successor.
416 struct GNUNET_HashCode trail_id;
418 /* List of the peers which are part of trail to reach from source_peer
419 * to successor, NOT including them
420 * struct GNUNET_PeerIdentity trail[]
425 * P2P Verify Successor Result Message
427 struct PeerVerifySuccessorResultMessage
430 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
432 struct GNUNET_MessageHeader header;
435 * Peer which sent the request to verify its successor.
437 struct GNUNET_PeerIdentity querying_peer;
440 * Successor to which PeerVerifySuccessorMessage was sent.
442 struct GNUNET_PeerIdentity current_successor;
445 * Current Predecessor of source_successor. It can be same as querying peer
446 * or different. In case it is different then it can be querying_peer's
447 * probable successor.
449 struct GNUNET_PeerIdentity probable_successor;
452 * Trail identifier of trail from querying_peer to current_successor.
454 struct GNUNET_HashCode trail_id;
457 * Direction in which we are looking at the trail.
459 uint32_t trail_direction;
461 /* In case probable_successor != querying_peer, then trail to reach from
462 * querying_peer to probable_successor, NOT including end points.
463 * struct GNUNET_PeerIdentity trail[]
468 * P2P Notify New Successor Message.
470 struct PeerNotifyNewSuccessorMessage
473 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
475 struct GNUNET_MessageHeader header;
478 * Peer which wants to notify its new successor.
480 struct GNUNET_PeerIdentity source_peer;
483 * New successor of source_peer.
485 struct GNUNET_PeerIdentity new_successor;
488 * Unique identifier of the trail from source_peer to new_successor,
489 * NOT including the endpoints.
491 struct GNUNET_HashCode trail_id;
493 /* List of peers in trail from source_peer to new_successor,
494 * NOT including the endpoints.
495 * struct GNUNET_PeerIdentity trail[]
500 * P2P Trail Compression Message.
502 struct PeerTrailCompressionMessage
505 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION
507 struct GNUNET_MessageHeader header;
510 * Source peer of this trail.
512 struct GNUNET_PeerIdentity source_peer;
515 * Trail from source_peer to destination_peer compressed such that
516 * new_first_friend is the first hop in the trail from source to
519 struct GNUNET_PeerIdentity new_first_friend;
522 * Unique identifier of trail.
524 struct GNUNET_HashCode trail_id;
529 * P2P Trail Tear Down message.
531 struct PeerTrailTearDownMessage
534 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
536 struct GNUNET_MessageHeader header;
539 * Unique identifier of the trail.
541 struct GNUNET_HashCode trail_id;
544 * Direction of trail.
546 uint32_t trail_direction;
551 * P2P Trail Rejection Message.
553 struct PeerTrailRejectionMessage
556 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_REJECTION
558 struct GNUNET_MessageHeader header;
561 * Peer which wants to set up the trail.
563 struct GNUNET_PeerIdentity source_peer;
566 * Peer which sent trail rejection message as it it congested.
568 struct GNUNET_PeerIdentity congested_peer;
571 * Peer identity closest to this value will be finger of
574 uint64_t ultimate_destination_finger_value;
577 * Is source_peer trying to setup the trail to its predecessor or finger.
579 uint32_t is_predecessor;
582 * Identifier for the trail that source peer is trying to setup.
584 struct GNUNET_HashCode trail_id;
587 * Relative time for which congested_peer will remain congested.
589 struct GNUNET_TIME_Relative congestion_time;
591 /* Trail_list from source_peer to peer which sent the message for trail setup
592 * to congested peer. This trail does NOT include source_peer.
593 struct GNUNET_PeerIdnetity trail[]*/
597 * P2P Add Trail Message.
599 struct PeerAddTrailMessage
602 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL
604 struct GNUNET_MessageHeader header;
607 * Source of the routing trail.
609 struct GNUNET_PeerIdentity source_peer;
612 * Destination of the routing trail.
614 struct GNUNET_PeerIdentity destination_peer;
617 * Unique identifier of the trail from source_peer to destination_peer,
618 * NOT including the endpoints.
620 struct GNUNET_HashCode trail_id;
622 /* Trail from source peer to destination peer, NOT including them.
623 * struct GNUNET_PeerIdentity trail[]
627 GNUNET_NETWORK_STRUCT_END
630 * Linked list of messages to send to a particular other peer.
632 struct P2PPendingMessage
635 * Pointer to next item in the list
637 struct P2PPendingMessage *next;
640 * Pointer to previous item in the list
642 struct P2PPendingMessage *prev;
645 * Message importance level. FIXME: used? useful?
647 unsigned int importance;
650 * When does this message time out?
652 struct GNUNET_TIME_Absolute timeout;
655 * Actual message to be sent, allocated at the end of the struct:
656 * // msg = (cast) &pm[1];
657 * // memcpy (&pm[1], data, len);
659 const struct GNUNET_MessageHeader *msg;
664 * Entry in friend_peermap.
671 struct GNUNET_PeerIdentity id;
674 * Number of trails for which this friend is the first hop or if the friend
677 unsigned int trails_count;
680 * Count of outstanding messages for this friend.
682 unsigned int pending_count;
685 * In case not 0, then amount of time for which this friend is congested.
687 struct GNUNET_TIME_Absolute congestion_timestamp;
690 * Head of pending messages to be sent to this friend.
692 struct P2PPendingMessage *head;
695 * Tail of pending messages to be sent to this friend.
697 struct P2PPendingMessage *tail;
700 * Core handle for sending messages to this friend.
702 struct GNUNET_CORE_TransmitHandle *th;
707 * An individual element of the trail to reach to a finger.
712 * Pointer to next item in the list
714 struct Trail_Element *next;
717 * Pointer to prev item in the list
719 struct Trail_Element *prev;
722 * An element in this trail.
724 struct GNUNET_PeerIdentity peer;
728 * FIXME: removed first_friend_trails_count, need to write a function
729 * to calculate each time we need it. Else, keep a pointer to first
730 * friend of in the trail.
731 * Information about an individual trail.
738 struct Trail_Element *trail_head;
743 struct Trail_Element *trail_tail;
746 * Unique identifier of this trail.
748 struct GNUNET_HashCode trail_id;
751 * Length of trail pointed
753 unsigned int trail_length;
757 * An entry in finger_table
764 struct GNUNET_PeerIdentity finger_identity;
767 * Is any finger stored at this finger index.
769 unsigned int is_present;
772 * Index in finger peer map
774 uint32_t finger_table_index;
777 * Number of trails setup so far for this finger.
778 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
780 uint32_t trails_count;
783 * Array of trails to reach to this finger.
785 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
790 * Data structure to keep track of closest peer seen so far in find_successor()
795 * Destination finger vaule.
797 uint64_t destination_finger_value;
800 * Is finger value predecessor or any other finge
802 unsigned int is_predecessor;
805 * Trail id to reach to peer.
807 struct GNUNET_HashCode trail_id;
810 * FIXME: see the usage of this field and write comment.
812 struct GNUNET_PeerIdentity next_hop;
815 * Next destination. In case of friend and my_identity , it is same as next_hop
816 * In case of finger it is finger identity.
818 struct GNUNET_PeerIdentity best_known_destination;
822 * FIXME: now I have removed the first_friend_trail_count,
823 * Need to update the code to find the count.
824 * Data structure to store the trail chosen to reach to finger.
826 struct Selected_Finger_Trail
829 * First friend in the trail to reach finger.
831 struct FriendInfo friend;
834 * Identifier of this trail.
836 struct GNUNET_HashCode trail_id;
839 * Total number of peers in this trail.
841 unsigned int trail_length;
845 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
846 * get our first friend.
848 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
851 * Identity of this peer.
853 static struct GNUNET_PeerIdentity my_identity;
856 * Peer map of all the friends of a peer
858 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
861 * Array of all the fingers.
863 static struct FingerInfo finger_table [MAX_FINGERS];
868 static struct GNUNET_CORE_Handle *core_api;
871 * The current finger index that we have want to find trail to. We start the
872 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
873 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
874 * we reset this index to 0.
876 static unsigned int current_search_finger_index;
880 * Called when core is ready to send a message we asked for
881 * out to the destination.
883 * @param cls the 'struct FriendInfo' of the target friend
884 * @param size number of bytes available in buf
885 * @param buf where the callee should write the message
886 * @return number of bytes written to buf
889 core_transmit_notify (void *cls, size_t size, void *buf)
891 struct FriendInfo *peer = cls;
893 struct P2PPendingMessage *pending;
898 while ((NULL != (pending = peer->head)) &&
899 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
901 peer->pending_count--;
902 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
903 GNUNET_free (pending);
907 /* no messages pending */
913 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
914 GNUNET_CORE_PRIO_BEST_EFFORT,
915 GNUNET_TIME_absolute_get_remaining
916 (pending->timeout), &peer->id,
917 ntohs (pending->msg->size),
918 &core_transmit_notify, peer);
919 GNUNET_break (NULL != peer->th);
923 while ((NULL != (pending = peer->head)) &&
924 (size - off >= (msize = ntohs (pending->msg->size))))
926 GNUNET_STATISTICS_update (GDS_stats,
928 ("# Bytes transmitted to other peers"), msize,
930 memcpy (&cbuf[off], pending->msg, msize);
932 peer->pending_count--;
933 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
934 GNUNET_free (pending);
936 if (peer->head != NULL)
939 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
940 GNUNET_CORE_PRIO_BEST_EFFORT,
941 GNUNET_TIME_absolute_get_remaining
942 (pending->timeout), &peer->id, msize,
943 &core_transmit_notify, peer);
944 GNUNET_break (NULL != peer->th);
952 * Transmit all messages in the friend's message queue.
954 * @param peer message queue to process
957 process_friend_queue (struct FriendInfo *peer)
959 struct P2PPendingMessage *pending;
961 if (NULL == (pending = peer->head))
963 if (NULL != peer->th)
966 GNUNET_STATISTICS_update (GDS_stats,
968 ("# Bytes of bandwidth requested from core"),
969 ntohs (pending->msg->size), GNUNET_NO);
972 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
974 GNUNET_TIME_absolute_get_remaining
975 (pending->timeout), &peer->id,
976 ntohs (pending->msg->size),
977 &core_transmit_notify, peer);
978 GNUNET_break (NULL != peer->th);
983 * Return friend corresponding to peer.
988 GDS_NEIGHBOURS_get_friend (struct GNUNET_PeerIdentity peer)
990 struct FriendInfo *friend;
991 GNUNET_assert (NULL != (friend =
992 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
998 * Construct a trail setup message and forward it to target_friend
999 * @param source_peer Peer which wants to setup the trail
1000 * @param ultimate_destination_finger_value Peer identity closest to this value
1001 * will be finger to @a source_peer
1002 * @param best_known_destination Best known destination (could be finger or friend)
1003 * which should get this message.
1004 * @param target_friend Friend to which message is forwarded now.
1005 * @param trail_length Total number of peers in trail setup so far.
1006 * @param trail_peer_list Trail setup so far
1007 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1008 * @param trail_id Unique identifier for the trail we are trying to setup.
1009 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1010 * best_known_destination when its a finger. If not
1011 * used then set to 0.
1014 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1015 uint64_t ultimate_destination_finger_value,
1016 struct GNUNET_PeerIdentity best_known_destination,
1017 struct FriendInfo *target_friend,
1018 unsigned int trail_length,
1019 const struct GNUNET_PeerIdentity *trail_peer_list,
1020 unsigned int is_predecessor,
1021 struct GNUNET_HashCode trail_id,
1022 struct GNUNET_HashCode *intermediate_trail_id)
1024 struct P2PPendingMessage *pending;
1025 struct PeerTrailSetupMessage *tsm;
1026 struct GNUNET_PeerIdentity *peer_list;
1029 msize = sizeof (struct PeerTrailSetupMessage) +
1030 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1032 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1038 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1040 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1044 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1045 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1046 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1047 pending->msg = &tsm->header;
1048 tsm->header.size = htons (msize);
1049 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
1050 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1051 tsm->source_peer = source_peer;
1052 tsm->best_known_destination = best_known_destination;
1053 tsm->is_predecessor = htonl (is_predecessor);
1054 tsm->trail_id = trail_id;
1056 if (NULL == intermediate_trail_id)
1057 memset (&tsm->intermediate_trail_id, 0, sizeof (tsm->intermediate_trail_id));
1059 tsm->intermediate_trail_id = *intermediate_trail_id;
1061 if (trail_length > 0)
1063 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1064 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1067 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1068 target_friend->pending_count++;
1069 process_friend_queue (target_friend);
1074 * Construct a trail setup result message and forward it to target friend.
1075 * @param querying_peer Peer which sent the trail setup request and should get
1077 * @param Finger Peer to which the trail has been setup to.
1078 * @param target_friend Friend to which this message should be forwarded.
1079 * @param trail_length Numbers of peers in the trail.
1080 * @param trail_peer_list Peers which are part of the trail from q
1081 * querying_peer to Finger, NOT including them.
1082 * @param is_predecessor Is @a Finger predecessor to @a querying_peer
1083 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1085 * @param trail_id Unique identifier of the trail.
1088 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1089 struct GNUNET_PeerIdentity finger,
1090 struct FriendInfo *target_friend,
1091 unsigned int trail_length,
1092 const struct GNUNET_PeerIdentity *trail_peer_list,
1093 unsigned int is_predecessor,
1094 uint64_t ultimate_destination_finger_value,
1095 struct GNUNET_HashCode trail_id)
1097 struct P2PPendingMessage *pending;
1098 struct PeerTrailSetupResultMessage *tsrm;
1099 struct GNUNET_PeerIdentity *peer_list;
1102 msize = sizeof (struct PeerTrailSetupResultMessage) +
1103 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1105 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1111 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1113 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1117 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1118 pending->importance = 0;
1119 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1120 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1121 pending->msg = &tsrm->header;
1122 tsrm->header.size = htons (msize);
1123 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
1124 tsrm->querying_peer = querying_peer;
1125 tsrm->finger_identity = finger;
1126 tsrm->is_predecessor = htonl (is_predecessor);
1127 tsrm->trail_id = trail_id;
1128 tsrm->ulitmate_destination_finger_value =
1129 GNUNET_htonll (ultimate_destination_finger_value);
1130 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1131 if (trail_length > 0)
1133 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1135 /* Send the message to chosen friend. */
1136 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1137 target_friend->pending_count++;
1138 process_friend_queue (target_friend);
1143 * Send trail rejection message to target friend
1144 * @param source_peer Peer which is trying to setup the trail.
1145 * @param ultimate_destination_finger_value Peer closest to this value will be
1146 * @a source_peer's finger
1147 * @param congested_peer Peer which sent this message as it is congested.
1148 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1149 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1150 * by congested_peer. This does not include @a source_peer
1151 * @param trail_length Total number of peers in trail_peer_list, not including
1153 * @param trail_id Unique identifier of this trail.
1154 * @param congestion_timeout Duration given by congested peer as an estimate of
1155 * how long it may remain congested.
1158 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1159 uint64_t ultimate_destination_finger_value,
1160 struct GNUNET_PeerIdentity congested_peer,
1161 unsigned int is_predecessor,
1162 const struct GNUNET_PeerIdentity *trail_peer_list,
1163 unsigned int trail_length,
1164 struct GNUNET_HashCode trail_id,
1165 struct FriendInfo *target_friend,
1166 const struct GNUNET_TIME_Relative congestion_timeout)
1168 struct PeerTrailRejectionMessage *trm;
1169 struct P2PPendingMessage *pending;
1170 struct GNUNET_PeerIdentity *peer_list;
1173 msize = sizeof (struct PeerTrailRejectionMessage) +
1174 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1176 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1182 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1184 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1188 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1189 pending->importance = 0;
1190 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1191 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1192 pending->msg = &trm->header;
1193 trm->header.size = htons (msize);
1194 trm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_REJECTION);
1195 trm->source_peer = source_peer;
1196 trm->congested_peer = congested_peer;
1197 trm->congestion_time = congestion_timeout;
1198 trm->is_predecessor = htonl (is_predecessor);
1199 trm->trail_id = trail_id;
1200 trm->ultimate_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1202 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1203 if (trail_length > 0)
1205 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1208 /* Send the message to chosen friend. */
1209 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1210 target_friend->pending_count++;
1211 process_friend_queue (target_friend);
1216 * Construct a verify successor message and forward it to target_friend.
1217 * @param source_peer Peer which wants to verify its successor.
1218 * @param successor Peer which is @a source_peer's current successor.
1219 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1220 * NOT including them.
1221 * @param trail List of peers which are part of trail to reach from @a source_peer
1222 * to @a successor, NOT including them.
1223 * @param trail_length Total number of peers in @a trail.
1224 * @param target_friend Next friend to get this message.
1227 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1228 struct GNUNET_PeerIdentity successor,
1229 const struct GNUNET_HashCode *trail_id,
1230 struct GNUNET_PeerIdentity *trail,
1231 unsigned int trail_length,
1232 struct FriendInfo *target_friend)
1234 struct PeerVerifySuccessorMessage *vsm;
1235 struct P2PPendingMessage *pending;
1236 struct GNUNET_PeerIdentity *peer_list;
1239 msize = sizeof (struct PeerVerifySuccessorMessage);
1240 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1246 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1248 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1252 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1253 pending->importance = 0; /* FIXME */
1254 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1255 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1256 pending->msg = &vsm->header;
1257 vsm->header.size = htons (msize);
1258 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1259 vsm->source_peer = source_peer;
1260 vsm->successor = successor;
1261 if (NULL == trail_id)
1262 memset (&vsm->trail_id, 0, sizeof (vsm->trail_id));
1264 vsm->trail_id = *trail_id;
1266 if (trail_length > 0)
1268 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1269 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1272 /* Send the message to chosen friend. */
1273 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1274 target_friend->pending_count++;
1275 process_friend_queue (target_friend);
1280 * FIXME: In every function we pass target friend except for this one.
1281 * so, either change everything or this one. also, should se just store
1282 * the pointer to friend in routing table rather than gnunet_peeridentity.
1283 * if yes then we should keep friend info in.h andmake lot of changes.
1284 * Construct a trail teardown message and forward it to target friend.
1285 * @param trail_id Unique identifier of the trail.
1286 * @param trail_direction Direction of trail.
1287 * @param target_friend Friend to get this message.
1290 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1291 unsigned int trail_direction,
1292 struct GNUNET_PeerIdentity *peer)
1294 struct PeerTrailTearDownMessage *ttdm;
1295 struct P2PPendingMessage *pending;
1296 struct FriendInfo *target_friend;
1299 msize = sizeof (struct PeerTrailTearDownMessage);
1301 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1307 GNUNET_assert (NULL != (target_friend =
1308 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
1310 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1312 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1316 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1317 pending->importance = 0; /* FIXME */
1318 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1319 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1320 pending->msg = &ttdm->header;
1321 ttdm->header.size = htons (msize);
1322 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1323 ttdm->trail_id = trail_id;
1324 ttdm->trail_direction = htonl (trail_direction);
1326 /* Send the message to chosen friend. */
1328 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1329 target_friend->pending_count++;
1330 process_friend_queue (target_friend);
1335 * Construct a verify successor result message and send it to target_friend
1336 * @param querying_peer Peer which sent the verify successor message.
1337 * @param source_successor Current_successor of @a querying_peer.
1338 * @param current_predecessor Current predecessor of @a successor. Could be same
1339 * or different from @a querying_peer.
1340 * @param trail_id Unique identifier of the trail from @a querying_peer to
1341 * @a successor, NOT including them.
1342 * @param trail List of peers which are part of trail from @a querying_peer to
1343 * @a successor, NOT including them.
1344 * @param trail_length Total number of peers in @a trail
1345 * @param trail_direction Direction in which we are sending the message. In this
1346 * case we are sending result from @a successor to @a querying_peer.
1347 * @param target_friend Next friend to get this message.
1350 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1351 struct GNUNET_PeerIdentity current_successor,
1352 struct GNUNET_PeerIdentity probable_successor,
1353 struct GNUNET_HashCode trail_id,
1354 const struct GNUNET_PeerIdentity *trail,
1355 unsigned int trail_length,
1356 enum GDS_ROUTING_trail_direction trail_direction,
1357 struct FriendInfo *target_friend)
1359 struct PeerVerifySuccessorResultMessage *vsmr;
1360 struct P2PPendingMessage *pending;
1361 struct GNUNET_PeerIdentity *peer_list;
1364 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1365 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1367 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1373 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1375 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1379 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1380 pending->importance = 0; /* FIXME */
1381 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1382 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1383 pending->msg = &vsmr->header;
1384 vsmr->header.size = htons (msize);
1385 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1386 vsmr->querying_peer = querying_peer;
1387 vsmr->current_successor = current_successor;
1388 vsmr->probable_successor = probable_successor;
1389 vsmr->trail_direction = htonl (trail_direction);
1390 vsmr->trail_id = trail_id;
1392 if (trail_length > 0)
1394 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1395 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1398 /* Send the message to chosen friend. */
1399 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1400 target_friend->pending_count++;
1401 process_friend_queue (target_friend);
1406 * Construct a notify new successor message and send it to target_friend
1407 * @param source_peer Peer which wants to notify to its new successor that it
1408 * could be its predecessor.
1409 * @param successor New successor of @a source_peer
1410 * @param successor_trail List of peers in Trail to reach from
1411 * @a source_peer to @a new_successor, NOT including
1413 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1414 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1415 * @param target_friend Next friend to get this message.
1418 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1419 struct GNUNET_PeerIdentity successor,
1420 const struct GNUNET_PeerIdentity *successor_trail,
1421 unsigned int successor_trail_length,
1422 struct GNUNET_HashCode succesor_trail_id,
1423 struct FriendInfo *target_friend)
1425 struct PeerNotifyNewSuccessorMessage *nsm;
1426 struct P2PPendingMessage *pending;
1427 struct GNUNET_PeerIdentity *peer_list;
1430 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1431 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1433 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1439 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1441 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1445 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1446 pending->importance = 0; /* FIXME */
1447 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1448 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1449 pending->msg = &nsm->header;
1450 nsm->header.size = htons (msize);
1451 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1452 nsm->new_successor = successor;
1453 nsm->source_peer = source_peer;
1454 nsm->trail_id = succesor_trail_id;
1456 if (successor_trail_length > 0)
1458 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1459 memcpy (peer_list, successor_trail,
1460 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1463 /* Send the message to chosen friend. */
1464 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1465 target_friend->pending_count++;
1466 process_friend_queue (target_friend);
1471 * Construct an add_trail message and send it to target_friend
1472 * @param source_peer Source of the trail.
1473 * @param destination_peer Destination of the trail.
1474 * @param trail_id Unique identifier of the trail from
1475 * @a source_peer to @a destination_peer, NOT including the endpoints.
1476 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1477 * NOT including the endpoints.
1478 * @param trail_length Total number of peers in @a trail.
1479 * @param target_friend Next friend to get this message.
1482 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1483 struct GNUNET_PeerIdentity destination_peer,
1484 struct GNUNET_HashCode trail_id,
1485 const struct GNUNET_PeerIdentity *trail,
1486 unsigned int trail_length,
1487 struct FriendInfo *target_friend)
1489 struct PeerAddTrailMessage *adm;
1490 struct GNUNET_PeerIdentity *peer_list;
1491 struct P2PPendingMessage *pending;
1494 msize = sizeof (struct PeerAddTrailMessage) +
1495 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1497 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1503 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1505 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1509 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1510 pending->importance = 0; /* FIXME */
1511 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1512 adm = (struct PeerAddTrailMessage *) &pending[1];
1513 pending->msg = &adm->header;
1514 adm->header.size = htons (msize);
1515 adm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL);
1516 adm->source_peer = source_peer;
1517 adm->destination_peer = destination_peer;
1518 adm->trail_id = trail_id;
1520 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1521 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1523 /* Send the message to chosen friend. */
1524 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1525 target_friend->pending_count++;
1526 process_friend_queue (target_friend);
1532 * Construct a trail compression message and send it to target_friend.
1533 * @param source_peer Source of the trail.
1534 * @param trail_id Unique identifier of trail.
1535 * @param first_friend First hop in compressed trail to reach from source to finger
1536 * @param target_friend Next friend to get this message.
1539 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1540 struct GNUNET_HashCode trail_id,
1541 struct GNUNET_PeerIdentity first_friend,
1542 struct FriendInfo *target_friend)
1544 struct P2PPendingMessage *pending;
1545 struct PeerTrailCompressionMessage *tcm;
1548 msize = sizeof (struct PeerTrailCompressionMessage);
1550 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1556 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1558 GNUNET_STATISTICS_update (GDS_stats,
1559 gettext_noop ("# P2P messages dropped due to full queue"),
1563 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1564 pending->importance = 0; /* FIXME */
1565 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1566 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1567 pending->msg = &tcm->header;
1568 tcm->header.size = htons (msize);
1569 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION);
1570 tcm->source_peer = source_peer;
1571 tcm->new_first_friend = first_friend;
1572 tcm->trail_id = trail_id;
1574 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1575 target_friend->pending_count++;
1576 process_friend_queue (target_friend);
1582 * Search my location in trail.
1583 * @param trail List of peers
1584 * @return my_index if found
1585 * -1 if no entry found.
1588 search_my_index (const struct GNUNET_PeerIdentity *trail,
1593 for (i = 0; i < trail_length; i++)
1595 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1603 * Check if the friend is congested or have reached maximum number of trails
1604 * it can be part of of.
1605 * @param friend Friend to be chechked.
1606 * @return #GNUNET_YES if friend is not congested or have not crossed threshold.
1607 * #GNUNET_NO if friend is either congested or have crossed threshold
1610 is_friend_congested (struct FriendInfo *friend)
1612 if ((friend->trails_count == TRAILS_THROUGH_FRIEND_THRESHOLD)||
1613 ((0 != GNUNET_TIME_absolute_get_remaining
1614 (friend->congestion_timestamp).rel_value_us)))
1622 * FIXME: here we should also check if iterator is null or not. It can be NULL
1623 * only if we insert randomly at locations. But as we are using trails_count
1624 * as the parameter, it should not happen.
1625 * Iterate over the list of all the trails of a finger. In case the first
1626 * friend to reach the finger has reached trail threshold or is congested,
1627 * then don't select it. In case there multiple available good trails to reach
1628 * to Finger, choose the one with shortest trail length.
1629 * Note: We use length as parameter. But we can use any other suitable parameter
1631 * @param finger Finger
1632 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1633 * and trail length. NULL in case none of the trails are free.
1635 static struct Selected_Finger_Trail *
1636 select_finger_trail (struct FingerInfo *finger)
1638 struct FriendInfo *friend;
1639 struct Trail *iterator;
1640 struct Selected_Finger_Trail *finger_trail;
1643 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1645 for (i = 0; i < finger->trails_count; i++)
1647 iterator = &finger->trail_list[i];
1648 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1649 &iterator->trail_head->peer);
1650 if (GNUNET_YES == is_friend_congested (friend))
1653 /* Check if the trail length of this trail is least seen so far. If yes then
1654 set finger_trail to this trail.*/
1655 if (finger_trail->trail_length > iterator->trail_length)
1657 finger_trail->friend = *friend;
1658 finger_trail->trail_id = iterator->trail_id;
1659 finger_trail->trail_length = iterator->trail_length;
1663 /* No trail found. */
1664 if (i == finger->trails_count)
1665 finger_trail = NULL;
1667 return finger_trail;
1672 * FIXME; not handling the wrap around logic correctly.
1673 * Select closest finger to value.
1674 * @param peer1 First peer
1675 * @param peer2 Second peer
1676 * @param value Value to be compare
1677 * @return Closest peer
1679 static struct GNUNET_PeerIdentity *
1680 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1681 struct GNUNET_PeerIdentity *peer2,
1684 uint64_t peer1_value;
1685 uint64_t peer2_value;
1687 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1688 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1690 if (peer1_value == value)
1695 if (peer2_value == value)
1700 if (peer2_value < peer1_value)
1702 if ((peer2_value < value) && (value < peer1_value))
1706 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1707 ((0 < value) && (value < peer2_value)))
1713 if (peer1_value < peer2_value)
1715 if ((peer1_value < value) && (value < peer2_value))
1719 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1720 ((0 < value) && (value < peer1_value)))
1730 * FIMXE: COMPLETE THE LOGIC.
1737 * 0 <= key < 5, so my_id 0 is the predecessor.
1738 * peer1 != peer2 ever.
1739 * Select closest predecessor to value.
1740 * @param peer1 First peer
1741 * @param peer2 Second peer
1742 * @param value Value to be compare
1743 * @return Closest peer
1745 static struct GNUNET_PeerIdentity *
1746 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1747 struct GNUNET_PeerIdentity *peer2,
1750 uint64_t peer1_value;
1751 uint64_t peer2_value;
1753 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1754 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1756 if (peer1_value == value)
1759 if (peer2_value == value)
1762 if (peer1_value < peer2_value)
1764 if ((peer1_value < value) && (value < peer2_value))
1766 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1767 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1771 if (peer2_value < peer1_value)
1773 if ((peer2_value < value) && (value < peer1_value))
1775 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1776 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1783 /* FIXME: select closest peer w.r.t. value. [finger->friend_id, current_successor->id)
1784 and [current_successor->id, finger->friend_id). Check in which range value lies.
1785 Also, check for wrap around. But this will give you the immediate predecessor
1786 For example. if we have 0,1,6 and I am 0 and one of my finger is 6. Then
1787 for 1, we will have ranges like [0,6) and [6,0) 1 lies in range from [0,6)
1788 but successor is 6 not 0 as 6 is > than 1. If you are the closest one,
1790 in current_successor. Want to write a generic code so that it is used in
1791 * finger_table_add also while choosing the closest one among new and existing
1800 * 0 <= key < 5, so key should go to 5.
1804 * Select the closest peer among two peers (which should not be same)
1805 * with respect to value and finger_table_index
1806 * @param peer1 First peer
1807 * @param peer2 Second peer
1808 * @param value Value relative to which we find the closest
1809 * @param finger_table_index Index in finger map. If equal to PREDECESSOR_FINGER_ID,
1810 * then we use different logic than other
1811 * finger_table_index
1812 * @return Closest peer among two peers.
1814 static struct GNUNET_PeerIdentity *
1815 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1816 struct GNUNET_PeerIdentity *peer2,
1818 unsigned int finger_table_index)
1820 struct GNUNET_PeerIdentity *closest_peer;
1821 /* FIXME: select closest peer w.r.t. value. [friend_id, current_successor->id)
1822 and [current_successor->id, friend_id). Check in which range value lies.
1823 Also, check for wrap around. Set the value of current_successor accordingly.*/
1824 if (PREDECESSOR_FINGER_ID == finger_table_index)
1825 closest_peer = select_closest_predecessor (peer1, peer2, value);
1827 closest_peer = select_closest_finger (peer1, peer2, value);
1829 return closest_peer;
1834 * FIXME: better names and more refactoring.
1835 * Compare FINGER entry with current successor. If finger's first friend of all
1836 * its trail is not congested and has not crossed trail threshold, then check
1837 * if finger peer identity is closer to final_destination_finger_value than
1838 * current_successor. If yes then update current_successor.
1839 * @param current_successor[in/out]
1842 static struct Closest_Peer *
1843 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1845 struct FingerInfo *finger;
1846 struct FriendInfo *friend;
1847 struct Selected_Finger_Trail *finger_trail;
1848 struct GNUNET_PeerIdentity *closest_peer;
1851 for (i = 0; i < MAX_FINGERS; i++)
1853 finger = &finger_table[i];
1855 if (GNUNET_NO == finger->is_present)
1858 /* If my identity is same as current closest peer then don't consider me*/
1859 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1860 ¤t_closest_peer->best_known_destination))
1863 /* If I am my own finger, then ignore this finger. */
1864 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1868 /* If finger is friend. */
1869 if (NULL != (friend = GNUNET_CONTAINER_multipeermap_get
1870 (friend_peermap, &finger->finger_identity)))
1872 if (GNUNET_YES == is_friend_congested (friend))
1875 /* If not congested then compare it with current_successor. */
1876 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1877 ¤t_closest_peer->best_known_destination))
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->finger_identity;
1893 /* Choose one of the trail to reach to finger. */
1894 finger_trail = select_finger_trail (finger);
1896 /* In case no trail found, ignore this finger. */
1897 if (NULL == finger_trail)
1900 closest_peer = select_closest_peer (&finger->finger_identity,
1901 ¤t_closest_peer->best_known_destination,
1902 current_closest_peer->destination_finger_value,
1903 current_closest_peer->is_predecessor);
1904 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1907 current_closest_peer->best_known_destination = finger->finger_identity;
1908 current_closest_peer->next_hop = finger_trail->friend.id;
1909 current_closest_peer->trail_id = finger_trail->trail_id;
1913 return current_closest_peer;
1918 * Compare friend entry with current successor. If friend is not congested and
1919 * has not crossed trail threshold, then check if friend peer identity is
1920 * closer to final_destination_finger_value than current_successor. If yes
1921 * then update current_successor.
1922 * @param cls closure
1923 * @param key current public key
1924 * @param value struct Closest_Peer
1925 * @return #GNUNET_YES if we should continue to iterate,
1926 * #GNUNET_NO if not.
1929 compare_friend_and_current_closest_peer (void *cls,
1930 const struct GNUNET_PeerIdentity *key,
1933 struct FriendInfo *friend = value;
1934 struct Closest_Peer *current_closest_peer = cls;
1935 struct GNUNET_PeerIdentity *closest_peer;
1937 if (GNUNET_YES == is_friend_congested (friend))
1941 GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
1942 ¤t_closest_peer->best_known_destination))
1945 closest_peer = select_closest_peer (&friend->id,
1946 ¤t_closest_peer->best_known_destination,
1947 current_closest_peer->destination_finger_value,
1948 current_closest_peer->is_predecessor);
1950 /* If friend is the closest successor. */
1951 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id, closest_peer))
1953 current_closest_peer->best_known_destination = friend->id;
1954 current_closest_peer->next_hop = friend->id;
1961 * Initialize current_successor to my_identity.
1962 * @param my_identity My peer identity
1963 * @return current_successor
1965 static struct Closest_Peer *
1966 init_current_successor (struct GNUNET_PeerIdentity my_identity,
1967 uint64_t destination_finger_value,
1968 unsigned int is_predecessor)
1970 struct Closest_Peer *current_closest_peer;
1972 current_closest_peer = GNUNET_new (struct Closest_Peer);
1973 memset (¤t_closest_peer->trail_id, 0, sizeof (current_closest_peer->trail_id));
1974 current_closest_peer->destination_finger_value = destination_finger_value;
1975 current_closest_peer->is_predecessor = is_predecessor;
1976 current_closest_peer->next_hop = my_identity;
1977 current_closest_peer->best_known_destination = my_identity;
1979 return current_closest_peer;
1984 * FIXME: first check if the finger == closest_peer then don't do anything.
1985 * Find the successor for destination_finger_value among my_identity, all my
1986 * friend and all my fingers. Don't consider friends or fingers
1987 * which are congested or have crossed the threshold.
1988 * @param destination_finger_value Peer closest to this value will be the next successor.
1989 * @param local_best_known_destination [out] Updated to my_identity if I am the
1990 * final destination. Updated to friend
1991 * identity in case a friend is successor,
1992 * updated to first friend to reach to finger
1993 * in case finger is the destination.
1994 * @param new_intermediate_trail_id [out] In case a finger is the
1995 * @a local_best_known_destination,
1996 * then it is the trail to reach it. Else
1998 * @param is_predecessor Are we looking for predecessor or finger?
1999 * @return Next hop to reach to local_best_known_destination. In case my_identity
2000 * or a friend is a local_best_known_destination, then
2001 * next_hop = local_best_known_destination. Else
2002 * next_hop is the first friend to reach to finger (local_best_known_destination)
2004 static struct GNUNET_PeerIdentity *
2005 find_successor (uint64_t destination_finger_value,
2006 struct GNUNET_PeerIdentity *local_best_known_destination,
2007 struct GNUNET_HashCode *new_intermediate_trail_id,
2008 unsigned int is_predecessor)
2010 struct Closest_Peer *current_closest_peer;
2011 struct GNUNET_PeerIdentity *next_hop;
2013 /* Initialize current_successor to my_identity. */
2014 current_closest_peer = init_current_successor (my_identity,
2015 destination_finger_value,
2018 /* Compare each friend entry with current_successor and update current_successor
2019 * with friend if its closest. */
2020 GNUNET_assert (GNUNET_SYSERR !=
2021 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2022 &compare_friend_and_current_closest_peer,
2023 current_closest_peer));
2025 /* Compare each finger entry with current_successor and update current_successor
2026 * with finger if its closest. */
2027 compare_finger_and_current_successor (current_closest_peer);
2029 *local_best_known_destination = current_closest_peer->best_known_destination;
2030 new_intermediate_trail_id = ¤t_closest_peer->trail_id;
2031 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
2032 *next_hop = current_closest_peer->next_hop;
2039 * Construct a Put message and send it to target_peer.
2040 * @param key Key for the content
2041 * @param block_type Type of the block
2042 * @param options Routing options
2043 * @param desired_replication_level Desired replication count
2044 * @param best_known_dest Peer to which this message should reach eventually,
2045 * as it is best known destination to me.
2046 * @param intermediate_trail_id Trail id in case
2047 * @param target_peer Peer to which this message will be forwarded.
2048 * @param hop_count Number of hops traversed so far.
2049 * @param put_path_length Total number of peers in @a put_path
2050 * @param put_path Number of peers traversed so far
2051 * @param expiration_time When does the content expire
2052 * @param data Content to store
2053 * @param data_size Size of content @a data in bytes
2056 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2057 enum GNUNET_BLOCK_Type block_type,
2058 enum GNUNET_DHT_RouteOption options,
2059 uint32_t desired_replication_level,
2060 struct GNUNET_PeerIdentity *best_known_dest,
2061 struct GNUNET_HashCode *intermediate_trail_id,
2062 struct GNUNET_PeerIdentity *target_peer,
2064 uint32_t put_path_length,
2065 struct GNUNET_PeerIdentity *put_path,
2066 struct GNUNET_TIME_Absolute expiration_time,
2067 const void *data, size_t data_size)
2069 struct PeerPutMessage *ppm;
2070 struct P2PPendingMessage *pending;
2071 struct FriendInfo *target_friend;
2072 struct GNUNET_PeerIdentity *pp;
2075 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2076 sizeof (struct PeerPutMessage);
2078 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2080 put_path_length = 0;
2081 msize = data_size + sizeof (struct PeerPutMessage);
2084 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2090 /* This is the first call made from clients file. So, we should search for the
2092 if (NULL == target_peer)
2095 struct GNUNET_PeerIdentity *next_hop;
2097 memcpy (&key_value, key, sizeof (uint64_t));
2098 next_hop = find_successor (key_value, best_known_dest,
2099 intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
2100 if (0 == GNUNET_CRYPTO_cmp_peer_identity(next_hop, &my_identity))
2102 /* I am the destination but we have already done datacache_put in client file. */
2106 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2109 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2110 pending->timeout = expiration_time;
2111 ppm = (struct PeerPutMessage *) &pending[1];
2112 pending->msg = &ppm->header;
2113 ppm->header.size = htons (msize);
2114 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
2115 ppm->options = htonl (options);
2116 ppm->block_type = htonl (block_type);
2117 ppm->hop_count = htonl (hop_count + 1);
2118 ppm->desired_replication_level = htonl (desired_replication_level);
2119 ppm->put_path_length = htonl (put_path_length);
2120 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2121 ppm->best_known_destination = *best_known_dest;
2123 if (NULL == intermediate_trail_id)
2124 memset (&ppm->intermediate_trail_id, 0, sizeof (ppm->intermediate_trail_id));
2126 ppm->intermediate_trail_id = *intermediate_trail_id;
2127 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2128 if (put_path_length != 0)
2130 memcpy (pp, put_path,
2131 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2133 memcpy (&pp[put_path_length], data, data_size);
2134 if (NULL == target_friend)
2135 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer);
2136 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2137 target_friend->pending_count++;
2138 process_friend_queue (target_friend);
2144 * Construct a Get message and send it to target_peer.
2145 * @param key Key for the content
2146 * @param block_type Type of the block
2147 * @param options Routing options
2148 * @param desired_replication_level Desired replication count
2149 * @param best_known_dest
2150 * @param intermediate_trail_id
2151 * @param target_peer Peer to which this message will be forwarded.
2152 * @param hop_count Number of hops traversed so far.
2153 * @param data Content to store
2154 * @param data_size Size of content @a data in bytes
2155 * @param get_path_length Total number of peers in @a get_path
2156 * @param get_path Number of peers traversed so far
2159 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2160 enum GNUNET_BLOCK_Type block_type,
2161 enum GNUNET_DHT_RouteOption options,
2162 uint32_t desired_replication_level,
2163 struct GNUNET_PeerIdentity *best_known_dest,
2164 struct GNUNET_HashCode *intermediate_trail_id,
2165 struct GNUNET_PeerIdentity *target_peer,
2167 uint32_t get_path_length,
2168 struct GNUNET_PeerIdentity *get_path)
2170 struct PeerGetMessage *pgm;
2171 struct P2PPendingMessage *pending;
2172 struct FriendInfo *target_friend;
2173 struct GNUNET_PeerIdentity *gp;
2176 msize = sizeof (struct PeerGetMessage) +
2177 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2179 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2185 if (NULL == target_peer)
2187 struct GNUNET_PeerIdentity *next_hop;
2190 memcpy (&key_value, key, sizeof (uint64_t));
2191 // FIXME: endianess of key_value!?
2192 /* FIXME: Here you should use enum GDS_NEIGHBOURS_FINGER_TYPE in place of 0. */
2193 next_hop = find_successor (key_value, best_known_dest,
2194 intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
2196 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity,next_hop))
2198 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2199 NULL, 0, 1, &my_identity, NULL,&my_identity);
2204 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2208 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2209 pending->importance = 0; /* FIXME */
2210 pgm = (struct PeerGetMessage *) &pending[1];
2211 pending->msg = &pgm->header;
2212 pgm->header.size = htons (msize);
2213 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2214 pgm->get_path_length = htonl (get_path_length);
2216 pgm->best_known_destination = *best_known_dest;
2217 pgm->intermediate_trail_id = *intermediate_trail_id;
2218 pgm->hop_count = htonl (hop_count + 1);
2222 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2223 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2225 if (NULL == target_friend)
2226 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer);
2227 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2228 target_friend->pending_count++;
2229 process_friend_queue (target_friend);
2234 * Send the get result to requesting client.
2235 * @param key Key of the requested data.
2236 * @param type Block type
2237 * @param target_peer Next peer to forward the message to.
2238 * @param source_peer Peer which has the data for the key.
2239 * @param put_path_length Number of peers in @a put_path
2240 * @param put_path Path taken to put the data at its stored location.
2241 * @param get_path_length Number of peers in @a get_path
2242 * @param get_path Path taken to reach to the location of the key.
2243 * @param expiration When will this result expire?
2244 * @param data Payload to store
2245 * @param data_size Size of the @a data
2248 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2249 enum GNUNET_BLOCK_Type type,
2250 struct GNUNET_PeerIdentity *target_peer,
2251 struct GNUNET_PeerIdentity *source_peer,
2252 unsigned int put_path_length,
2253 const struct GNUNET_PeerIdentity *put_path,
2254 unsigned int get_path_length,
2255 struct GNUNET_PeerIdentity *get_path,
2256 struct GNUNET_TIME_Absolute expiration,
2257 const void *data, size_t data_size)
2259 struct PeerGetResultMessage *get_result;
2260 struct GNUNET_PeerIdentity *get_result_path;
2261 struct GNUNET_PeerIdentity *pp;
2262 struct P2PPendingMessage *pending;
2263 struct FriendInfo *target_friend;
2264 int current_path_index;
2267 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2268 sizeof (struct PeerPutMessage);
2270 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2276 if(get_path_length > 0)
2278 current_path_index = search_my_index(get_path, get_path_length);
2279 if (GNUNET_SYSERR == current_path_index)
2285 if (0 == current_path_index)
2287 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2288 get_path, put_path_length,
2289 put_path, type, data_size, data);
2293 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2294 pending->importance = 0;
2295 get_result = (struct PeerGetResultMessage *)&pending[1];
2296 pending->msg = &get_result->header;
2297 get_result->header.size = htons (msize);
2298 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2299 get_result->key = *key;
2300 /* FIXME: check if you are passing the correct querying_peer as described in
2301 the get_result documentation. */
2302 memcpy (&(get_result->querying_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2303 get_result->expiration_time = expiration;
2306 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2307 memcpy (get_result_path, get_path,
2308 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2309 memcpy (&get_result_path[get_path_length], data, data_size);
2311 /* FIXME: Is this correct? */
2312 if (put_path_length != 0)
2314 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2315 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2318 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2319 &get_result_path[current_path_index - 1]);
2320 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2321 target_friend->pending_count++;
2322 process_friend_queue (target_friend);
2327 * Randomly choose one of your friends (which is not congested and have not crossed
2328 * trail threshold) from the friends_peer map
2329 * @return Friend Randomly chosen friend.
2330 * NULL in case friend peermap is empty, or all the friends are either
2331 * congested or have crossed trail threshold.
2333 static struct FriendInfo *
2334 select_random_friend ()
2336 unsigned int current_size;
2339 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2340 struct GNUNET_PeerIdentity key_ret;
2341 struct FriendInfo *friend;
2343 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2344 if (0 == current_size)
2347 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2348 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2350 for (j = 0; j < index ; j++)
2351 GNUNET_assert (GNUNET_YES ==
2352 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2355 if (j == current_size)
2358 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2359 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2362 GNUNET_assert (GNUNET_YES ==
2363 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2365 (const void **)&friend));
2367 /* This friend is not congested and has not crossed trail threshold. */
2368 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2369 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2375 } while (j != index);
2377 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2383 * Compute 64 bit value of finger_identity corresponding to a finger index using
2386 * n.finger[i] = n + pow (2,i),
2388 * n.finger[i] = n - 1, where
2391 * n.finger[i] = 64 bit finger value
2392 * @param finger_index Index corresponding to which we calculate 64 bit value.
2393 * @return 64 bit value.
2396 compute_finger_identity_value (unsigned int finger_index)
2400 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2401 my_id64 = GNUNET_ntohll (my_id64);
2403 /* Are we looking for immediate predecessor? */
2404 if (PREDECESSOR_FINGER_ID == finger_index)
2405 return (my_id64 -1);
2407 return (my_id64 + (unsigned long) pow (2, finger_index));
2412 * Choose a random friend. Start looking for the trail to reach to
2413 * finger identity corresponding to current_search_finger_index through
2414 * this random friend.
2416 * @param cls closure for this task
2417 * @param tc the context under which the task is running
2420 send_find_finger_trail_message (void *cls,
2421 const struct GNUNET_SCHEDULER_TaskContext *tc)
2423 struct FriendInfo *target_friend;
2424 struct GNUNET_TIME_Relative next_send_time;
2425 struct GNUNET_HashCode trail_id;
2426 unsigned int is_predecessor;
2427 uint64_t finger_id_value;
2429 /* Schedule another send_find_finger_trail_message task. */
2430 next_send_time.rel_value_us =
2431 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
2432 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2433 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2434 find_finger_trail_task =
2435 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
2438 /* My own routing table is all full. I can not store any more trails for which
2440 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2443 target_friend = select_random_friend ();
2444 if (NULL == target_friend)
2449 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2450 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2455 /* Generate a unique trail id for trail we are trying to setup. */
2456 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2457 &trail_id, sizeof (trail_id));
2458 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2459 target_friend->id, target_friend, 0, NULL,
2460 is_predecessor, trail_id, NULL);
2465 * In case there are already maximum number of possible trails to reach to a
2466 * finger, then check if the new trail's length is lesser than any of the
2468 * If yes then replace that old trail by new trail.
2470 * Note: Here we are taking length as a parameter to choose the best possible
2471 * trail, but there could be other parameters also like:
2472 * 1. duration of existence of a trail - older the better.
2473 * 2. if the new trail is completely disjoint than the
2474 * other trails, then may be choosing it is better.
2476 * @param existing_finger
2477 * @param new_finger_trail
2478 * @param new_finger_trail_length
2479 * @param new_finger_trail_id
2482 select_and_replace_trail (struct FingerInfo *existing_finger,
2483 const struct GNUNET_PeerIdentity *new_trail,
2484 unsigned int new_trail_length,
2485 struct GNUNET_HashCode new_trail_id)
2487 struct Trail *trail_list_iterator;
2488 unsigned int largest_trail_length;
2489 unsigned int largest_trail_index;
2490 struct Trail_Element *trail_element;
2493 largest_trail_length = new_trail_length;
2494 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2496 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2498 for (i = 0; i < existing_finger->trails_count; i++)
2500 trail_list_iterator = &existing_finger->trail_list[i];
2501 if (trail_list_iterator->trail_length > largest_trail_length)
2503 largest_trail_length = trail_list_iterator->trail_length;
2504 largest_trail_index = i;
2508 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2510 // tear down new trail: it's not better than the existing ones
2514 /* Send trail teardown message across the replaced trail. */
2515 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2517 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2518 GDS_ROUTING_SRC_TO_DEST,
2519 &replace_trail->trail_head->peer);
2520 /* Free the trail. */
2521 while (NULL != (trail_element = replace_trail->trail_head))
2523 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2524 replace_trail->trail_tail, trail_element);
2525 GNUNET_free_non_null (trail_element);
2528 /* Add new trial at that location. */
2530 while (i < new_trail_length)
2532 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2533 element->peer = new_trail[i];
2535 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2536 replace_trail->trail_tail,
2543 * Check if the new trail to reach to finger is unique or do we already have
2544 * such a trail present for finger.
2545 * @param existing_finger Finger identity
2546 * @param new_trail New trail to reach @a existing_finger
2547 * @param trail_length Total number of peers in new_trail.
2548 * @return #GNUNET_YES if the new trail is unique
2549 * #GNUNET_NO if same trail is already present.
2552 is_new_trail_unique (struct FingerInfo *existing_finger,
2553 const struct GNUNET_PeerIdentity *new_trail,
2554 unsigned int trail_length)
2556 struct Trail *trail_list_iterator;
2557 struct Trail_Element *trail_element;
2560 int trail_unique = GNUNET_NO;
2562 for (i = 0; i < existing_finger->trails_count; i++)
2564 trail_list_iterator = &existing_finger->trail_list[i];
2565 if (trail_list_iterator->trail_length != trail_length)
2567 trail_element = trail_list_iterator->trail_head;
2568 for (j = 0; j < trail_list_iterator->trail_length; j++)
2570 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2571 &trail_element->peer))
2573 trail_unique = GNUNET_YES;
2578 return trail_unique;
2583 * Add a new trail to existing finger.
2584 * @param existing_finger
2585 * @param new_finger_trail
2586 * @param new_finger_trail_length
2587 * @param new_finger_trail_id
2590 add_new_trail (struct FingerInfo *existing_finger,
2591 const struct GNUNET_PeerIdentity *new_trail,
2592 unsigned int new_trail_length,
2593 struct GNUNET_HashCode new_trail_id)
2595 struct Trail *trail_list_iterator;
2596 struct FriendInfo *first_friend;
2599 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2605 // FIXME checking trail_head is NOT a valid way to verify an open slot
2606 for (i = 0; existing_finger->trail_list[i].trail_head != NULL; i++)
2607 GNUNET_assert (i < MAXIMUM_TRAILS_PER_FINGER);
2609 trail_list_iterator = &existing_finger->trail_list[i];
2611 if (new_trail_length > 0)
2612 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2615 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2616 &(existing_finger->finger_identity));
2617 first_friend->trails_count++;
2618 /* FIXME; we removed this field but read fixme. */
2619 //trail_list_iterator->first_friend_trail_count = first_friend->trails_count;
2620 trail_list_iterator->trail_length = new_trail_length;
2622 for (i = 0; i < new_trail_length; i++)
2624 struct Trail_Element *element;
2625 element = GNUNET_new (struct Trail_Element);
2627 element->peer = new_trail[i];
2628 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2629 trail_list_iterator->trail_tail,
2632 existing_finger->trails_count++;
2637 * Send trail teardown message for a specific trail of a finger.
2638 * @param finger Finger whose trail is to be removed.
2639 * @param trail List of peers in trail from me to a finger, NOT including
2643 send_trail_teardown (struct FingerInfo *finger,
2644 struct Trail *trail)
2646 /* FIXME: Now source also stores a trail entry in its routing table. before
2647 sending the trail teardown, you should get next_hop from routing table.
2648 If it is NULL, it means that path is broken, then remove the trail.
2649 return a value to calling function so that if all trails are removed,
2650 then remove finger. */
2651 /* We should decerement the friend trail count here. */
2652 struct FriendInfo *friend;
2654 GNUNET_assert (NULL != (friend =
2655 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2656 &trail->trail_head->peer)));
2658 friend->trails_count--;
2659 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2660 GDS_ROUTING_SRC_TO_DEST,
2661 &trail->trail_head->peer);
2666 * Send trail teardown message across all the trails to reach to finger.
2667 * @param finger Finger whose all the trail should be freed.
2670 send_all_finger_trails_teardown (struct FingerInfo *finger)
2672 struct Trail *trail;
2675 for (i = 0; i < finger->trails_count; i++)
2677 trail = &finger->trail_list[i];
2678 if (trail->trail_length > 0)
2680 /* decerement the friend trails count. */
2681 send_trail_teardown (finger, trail);
2688 * Free a specific trail
2689 * @param trail List of peers to be freed.
2692 free_trail (struct Trail *trail)
2694 struct Trail_Element *trail_element;
2696 while (NULL != (trail_element = trail->trail_head))
2698 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2701 GNUNET_free_non_null (trail_element);
2707 * Free finger and its trail.
2708 * @param finger Finger to be freed.
2711 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2713 struct Trail *trail;
2716 for (i = 0; i < finger->trails_count; i++)
2718 trail = &finger->trail_list[i];
2719 if (trail->trail_length > 0)
2723 finger->is_present = GNUNET_NO;
2724 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2729 * Add a new entry in finger table at finger_table_index.
2730 * In case finger identity is me or a friend, then don't add a trail.
2731 * In case a finger is a friend, then increment the trails count of the friend.
2732 * @param finger_identity Peer Identity of new finger
2733 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2734 * @param finger_trail_length Total number of peers in @a finger_trail.
2735 * @param trail_id Unique identifier of the trail.
2736 * @param finger_table_index Index in finger table.
2739 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2740 const struct GNUNET_PeerIdentity *finger_trail,
2741 unsigned int finger_trail_length,
2742 struct GNUNET_HashCode trail_id,
2743 unsigned int finger_table_index)
2745 struct FingerInfo *new_entry;
2746 struct FriendInfo *first_trail_hop;
2747 struct Trail *trail;
2750 new_entry = GNUNET_new (struct FingerInfo);
2751 new_entry->finger_identity = finger_identity;
2752 new_entry->finger_table_index = finger_table_index;
2753 new_entry->is_present = GNUNET_YES;
2755 /* Finger is not my identity. */
2756 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2758 if (finger_trail_length == 0)
2760 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2762 first_trail_hop->trails_count++;
2763 finger_table[finger_table_index] = *new_entry;
2767 /* PRINT TRAIL remove*/
2769 GNUNET_assert(NULL !=
2771 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2772 &finger_trail[0])));
2773 new_entry->trails_count = 1;
2774 first_trail_hop->trails_count++;
2776 /* Copy the finger trail into trail. */
2777 trail = GNUNET_new (struct Trail);
2778 while (i < finger_trail_length)
2780 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2782 element->next = NULL;
2783 element->prev = NULL;
2784 element->peer = finger_trail[i];
2785 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2790 /* Add trail to trail list. */
2791 new_entry->trail_list[0].trail_head = trail->trail_head;
2792 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2793 new_entry->trail_list[0].trail_length = finger_trail_length;
2794 new_entry->trail_list[0].trail_id = trail_id;
2797 finger_table[finger_table_index] = *new_entry;
2803 * Scan the trail to check if there is any other friend in the trail other than
2804 * first hop. If yes then shortcut the trail, send trail compression message to
2805 * peers which are no longer part of trail and send back the updated trail
2806 * and trail_length to calling function.
2807 * @param finger_identity Finger whose trail we will scan.
2808 * @param finger_trail [in, out] Trail to reach from source to finger,
2809 * @param finger_trail_length Total number of peers in original finger_trail.
2810 * @param finger_trail_id Unique identifier of the finger trail.
2811 * @return updated trail length in case we shortcut the trail, else original
2814 static struct GNUNET_PeerIdentity *
2815 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2816 const struct GNUNET_PeerIdentity *trail,
2817 unsigned int trail_length,
2818 struct GNUNET_HashCode trail_id,
2819 int *new_trail_length)
2821 struct FriendInfo *target_friend;
2822 struct GNUNET_PeerIdentity *new_trail;
2825 /* If I am my own finger identity, then we set trail_length = 0.
2826 Note: Here we don't send trail compression message, as no peer in its
2827 trail added an entry in its routing table.*/
2828 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2830 *new_trail_length = 0;
2834 /* If finger identity is a friend. */
2835 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
2837 *new_trail_length = 0;
2839 /* If there is trail to reach this finger/friend */
2840 if (trail_length > 0)
2842 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2844 /* FIXME: In case its finger == friend, then may be we send a trail
2845 teardown message as it does not make any sense to have any routing e
2846 entry in your own routing table.*/
2847 GDS_NEIGHBOURS_send_trail_compression (my_identity,
2848 trail_id, finger_identity,
2854 /* For other cases, when its neither a friend nor my own identity.*/
2855 for (i = trail_length - 1; i > 0; i--)
2857 /* If the element at this index in trail is a friend. */
2858 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
2860 struct FriendInfo *target_friend;
2863 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2865 GDS_NEIGHBOURS_send_trail_compression (my_identity,
2870 /* Copy the trail from index i to index (trail_length -1) into a new trail
2871 * and update new trail length */
2872 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * i);
2873 while (i < trail_length)
2875 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
2879 *new_trail_length = j+1;
2884 /* If we found no other friend except the first hop, return the original
2887 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
2888 *new_trail_length = trail_length;
2889 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
2895 * FIXME: Ensure that we add trail in succession in the trail list.
2896 * There are no free spots within the trail list.
2897 * Send verify successor message to your successor on all trails to reach
2899 * @param successor My current successor
2902 send_verify_successor_message (struct FingerInfo *successor)
2904 struct Trail *trail_list_iterator;
2905 struct GNUNET_HashCode *trail_id;
2906 struct GNUNET_PeerIdentity next_hop;
2907 struct FriendInfo *target_friend;
2908 struct GNUNET_PeerIdentity *trail;
2909 unsigned int trail_length;
2913 /* If successor is a friend. */
2914 if (successor->trails_count == 0)
2916 struct FriendInfo *target_friend;
2917 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2918 &successor->finger_identity);
2919 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
2920 successor->finger_identity,
2925 trail_id = GNUNET_new (struct GNUNET_HashCode);
2927 for (i = 0; i < successor->trails_count; i++)
2929 trail_list_iterator = &successor->trail_list[i];
2930 GNUNET_assert (NULL != trail_list_iterator->trail_head);
2932 if (trail_list_iterator->trail_length > 0)
2934 struct Trail_Element *element;
2936 trail_length = trail_list_iterator->trail_length;
2937 trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
2939 element = trail_list_iterator->trail_head;
2940 for (j = 0; j < trail_length; j++, element = element->next)
2941 trail[j] = element->peer;
2942 next_hop = trail_list_iterator->trail_head->peer;
2948 next_hop = successor->finger_identity;
2950 *trail_id = trail_list_iterator->trail_id;
2951 GNUNET_assert (NULL != (target_friend =
2952 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2954 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
2955 successor->finger_identity,
2956 trail_id, trail, trail_length,
2963 * FIXME" clear abstraction of current search finger index and finger map index.
2964 * it never goes to 63. I don't know why
2965 * Update the current search finger index.
2968 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
2969 unsigned int finger_table_index)
2971 struct FingerInfo *successor;
2973 if (finger_table_index != current_search_finger_index)
2976 successor = &finger_table[0];
2977 if (GNUNET_NO == successor->is_present)
2980 /* We were looking for immediate successor. */
2981 if (0 == current_search_finger_index)
2983 /* Start looking for immediate predecessor. */
2984 current_search_finger_index = PREDECESSOR_FINGER_ID;
2986 /* If I am not my own successor, then send a verify successor message. */
2987 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2989 send_verify_successor_message (successor);
2994 current_search_finger_index = current_search_finger_index - 1;
3000 * Calculate finger_table_index from initial 64 bit finger identity value that
3001 * we send in trail setup message.
3002 * @param ultimate_destination_finger_value Value that we calculated from our
3003 * identity and finger_table_index.
3004 * @param is_predecessor Is the entry for predecessor or not?
3005 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3006 * -1, if no valid finger_table_index is found.
3009 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3010 unsigned int is_predecessor)
3014 unsigned int finger_table_index;
3016 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3017 my_id64 = GNUNET_ntohll (my_id64);
3019 /* Is this a predecessor finger? */
3020 if (1 == is_predecessor)
3022 diff = my_id64 - ultimate_destination_finger_value;
3024 finger_table_index = PREDECESSOR_FINGER_ID;
3026 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3031 diff = ultimate_destination_finger_value - my_id64;
3032 finger_table_index = (log10 (diff))/(log10 (2));
3035 return finger_table_index;
3040 * Remove finger and its associated data structures from finger table.
3041 * @param finger Finger to be removed.
3044 remove_existing_finger (struct FingerInfo *existing_finger, unsigned int finger_table_index)
3046 struct FriendInfo *friend;
3047 struct FingerInfo *finger;
3049 finger = &finger_table[finger_table_index];
3050 GNUNET_assert (GNUNET_YES == finger->is_present);
3052 /* If I am my own finger, then we have no trails. */
3053 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3056 finger->is_present = GNUNET_NO;
3057 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
3061 /* If finger is a friend, then decrement the trail count and free the finger. */
3062 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3063 &finger->finger_identity);
3066 friend->trails_count--;
3067 finger->is_present = GNUNET_NO;
3068 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
3072 /* For all other fingers, send trail teardown across all the trails to reach
3073 finger, and free the finger. */
3074 send_all_finger_trails_teardown (finger);
3075 free_finger (finger, finger_table_index);
3081 * This is a test function to print all the entries of friend table.
3084 test_friend_peermap_print ()
3086 struct FriendInfo *friend;
3087 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
3088 struct GNUNET_PeerIdentity print_peer;
3089 struct GNUNET_PeerIdentity key_ret;
3092 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
3094 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
3096 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
3098 (const void **)&friend))
3100 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
3101 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
3102 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
3109 * This is a test function, to print all the entries of finger table.
3112 test_finger_table_print()
3114 struct FingerInfo *finger;
3115 struct GNUNET_PeerIdentity print_peer;
3116 struct Trail *trail;
3121 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE"));
3122 for (i = 0; i < MAX_FINGERS; i++)
3124 finger = &finger_table[i];
3126 if (GNUNET_NO == finger->is_present)
3129 print_peer = finger->finger_identity;
3130 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
3131 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
3134 for (j = 0; j < finger->trails_count; j++)
3136 trail = &finger->trail_list[j];
3137 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
3138 struct Trail_Element *element;
3139 element = trail->trail_head;
3140 for (k = 0; k < trail->trail_length; k++)
3142 print_peer = element->peer;
3143 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
3144 element = element->next;
3152 * Check if there is already an entry in finger_table at finger_table_index.
3153 * We get the finger_table_index from 64bit finger value we got from the network.
3154 * -- If yes, then select the closest finger.
3155 * -- If new and existing finger are same, then check if you can store more
3157 * -- If yes then add trail, else keep the best trails to reach to the
3159 * -- If the new finger is closest, remove the existing entry, send trail
3160 * teardown message across all the trails to reach the existing entry.
3162 * -- If new and existing finger are different, and existing finger is same
3164 * -- Update current_search_finger_index.
3165 * @param finger_identity Peer Identity of new finger
3166 * @param finger_trail Trail to reach the new finger
3167 * @param finger_length Total number of peers in @a new_finger_trail.
3168 * @param is_predecessor Is this entry for predecessor in finger_table?
3169 * @param finger_value 64 bit value of finger identity that we got from network.
3170 * @param finger_trail_id Unique identifier of @finger_trail.
3173 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3174 const struct GNUNET_PeerIdentity *finger_trail,
3175 unsigned int finger_trail_length,
3176 unsigned int is_predecessor,
3177 uint64_t finger_value,
3178 struct GNUNET_HashCode finger_trail_id)
3180 struct FingerInfo *existing_finger;
3181 struct GNUNET_PeerIdentity *closest_peer;
3182 struct GNUNET_PeerIdentity *updated_trail;
3183 struct FingerInfo *successor;
3184 int updated_finger_trail_length;
3185 unsigned int finger_table_index;
3187 //test_friend_peermap_print();
3188 //test_finger_table_print();
3190 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3191 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3193 /* Invalid finger_table_index. */
3194 if ((finger_table_index > PREDECESSOR_FINGER_ID) || (finger_table_index < 0))
3196 GNUNET_break_op (0);
3199 updated_finger_trail_length = finger_trail_length;
3201 scan_and_compress_trail (finger_identity, finger_trail,
3202 finger_trail_length, finger_trail_id,
3203 &updated_finger_trail_length);
3205 /* If the new entry is same as successor then don't add it in finger table,
3206 reset the current search finger index and exit. */
3207 if ((0 != finger_table_index) && (PREDECESSOR_FINGER_ID != finger_table_index))
3209 successor = &finger_table[0];
3210 GNUNET_assert (GNUNET_YES == successor->is_present);
3211 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3212 &successor->finger_identity))
3214 current_search_finger_index = 0;
3219 existing_finger = &finger_table[finger_table_index];
3221 /* No entry present in finger_table for given finger map index. */
3222 if (GNUNET_NO == existing_finger->is_present)
3224 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3225 finger_trail_id, finger_table_index);
3226 update_current_search_finger_index (finger_identity, finger_table_index);
3230 /* If existing entry and finger identity are not same. */
3231 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3234 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3236 finger_value, finger_table_index);
3238 /* If the new finger is the closest peer. */
3239 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3241 remove_existing_finger (existing_finger, finger_table_index);
3242 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3243 finger_trail_id, finger_table_index);
3248 /* If both new and existing entry are same as my_identity, then do nothing. */
3249 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3253 /* If the existing finger is not a friend. */
3255 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3256 &existing_finger->finger_identity))
3258 /* If there is space to store more trails. */
3259 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3260 add_new_trail (existing_finger, updated_trail,
3261 finger_trail_length, finger_trail_id);
3263 select_and_replace_trail (existing_finger, updated_trail,
3264 finger_trail_length, finger_trail_id);
3267 update_current_search_finger_index (finger_identity, finger_table_index);
3273 * Core handler for P2P put messages.
3274 * @param cls closure
3275 * @param peer sender of the request
3276 * @param message message
3277 * @return #GNUNET_OK to keep the connection open,
3278 * #GNUNET_SYSERR to close it (signal serious error)
3281 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3282 const struct GNUNET_MessageHeader *message)
3284 struct PeerPutMessage *put;
3285 struct GNUNET_PeerIdentity *put_path;
3286 struct GNUNET_HashCode test_key;
3287 enum GNUNET_DHT_RouteOption options;
3288 struct GNUNET_PeerIdentity best_known_dest;
3289 struct GNUNET_HashCode intermediate_trail_id;
3290 struct GNUNET_PeerIdentity *next_hop;
3294 size_t payload_size;
3297 msize = ntohs (message->size);
3298 if (msize < sizeof (struct PeerPutMessage))
3300 GNUNET_break_op (0);
3304 put = (struct PeerPutMessage *) message;
3305 putlen = ntohl (put->put_path_length);
3308 sizeof (struct PeerPutMessage) +
3309 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3311 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3313 GNUNET_break_op (0);
3317 best_known_dest = put->best_known_destination;
3318 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3319 payload = &put_path[putlen];
3320 options = ntohl (put->options);
3321 intermediate_trail_id = put->intermediate_trail_id;
3323 payload_size = msize - (sizeof (struct PeerPutMessage) +
3324 putlen * sizeof (struct GNUNET_PeerIdentity));
3326 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3327 payload, payload_size, &test_key))
3330 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3332 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3333 GNUNET_break_op (0);
3334 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3335 "PUT with key `%s' for block with key %s\n",
3336 put_s, GNUNET_h2s_full (&test_key));
3337 GNUNET_free (put_s);
3342 GNUNET_break_op (0);
3345 /* cannot verify, good luck */
3349 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3351 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3352 ntohl (put->block_type),
3354 NULL, 0, /* bloom filer */
3355 NULL, 0, /* xquery */
3356 payload, payload_size))
3358 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3359 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3362 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3363 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3364 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3365 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3366 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3367 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3369 GNUNET_break_op (0);
3374 /* extend 'put path' by sender */
3375 struct GNUNET_PeerIdentity pp[putlen + 1];
3376 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3378 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3385 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3386 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3388 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3389 GDS_ROUTING_SRC_TO_DEST);
3393 /*FIXME: Here you should use enum GDS_NEIGHBOURS_FINGER_TYPE in place of 0. */
3394 next_hop = find_successor (key_value, &best_known_dest,
3395 &intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
3398 if (NULL == next_hop)
3400 GNUNET_STATISTICS_update (GDS_stats,
3401 gettext_noop ("# Next hop to forward the packet not found "
3402 "trail setup request, packet dropped."),
3404 return GNUNET_SYSERR;
3407 GDS_CLIENTS_process_put (options,
3408 ntohl (put->block_type),
3409 ntohl (put->hop_count),
3410 ntohl (put->desired_replication_level),
3412 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3417 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop)) /* I am the final destination */
3419 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3420 &(put->key),putlen, pp, ntohl (put->block_type),
3421 payload_size, payload);
3426 GDS_NEIGHBOURS_send_put (&put->key,
3427 ntohl (put->block_type),ntohl (put->options),
3428 ntohl (put->desired_replication_level),
3429 &best_known_dest, &intermediate_trail_id, next_hop,
3430 ntohl (put->hop_count), putlen, pp,
3431 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3432 payload, payload_size);
3436 return GNUNET_SYSERR;
3441 * Core handler for p2p get requests.
3443 * @param cls closure
3444 * @param peer sender of the request
3445 * @param message message
3446 * @return #GNUNET_OK to keep the connection open,
3447 * #GNUNET_SYSERR to close it (signal serious error)
3450 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3451 const struct GNUNET_MessageHeader *message)
3453 struct PeerGetMessage *get;
3454 struct GNUNET_PeerIdentity *get_path;
3455 struct GNUNET_PeerIdentity best_known_dest;
3456 struct GNUNET_HashCode intermediate_trail_id;
3457 struct GNUNET_PeerIdentity *next_hop;
3458 uint32_t get_length;
3462 msize = ntohs (message->size);
3463 if (msize < sizeof (struct PeerGetMessage))
3465 GNUNET_break_op (0);
3469 get = (struct PeerGetMessage *)message;
3470 get_length = ntohl (get->get_path_length);
3471 best_known_dest = get->best_known_destination;
3472 intermediate_trail_id = get->intermediate_trail_id;
3473 get_path = (struct GNUNET_PeerIdentity *)&get[1];
3476 sizeof (struct PeerGetMessage) +
3477 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3479 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3481 GNUNET_break_op (0);
3485 /* Add sender to get path */
3486 struct GNUNET_PeerIdentity gp[get_length + 1];
3487 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3488 gp[get_length + 1] = *peer;
3489 get_length = get_length + 1;
3491 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3492 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3494 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3495 GDS_ROUTING_SRC_TO_DEST);
3499 /*FIXME: Here you should use enum GDS_NEIGHBOURS_FINGER_TYPE in place of 0. */
3500 next_hop = find_successor (key_value, &best_known_dest,
3501 &intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
3504 if (NULL == next_hop)
3506 GNUNET_STATISTICS_update (GDS_stats,
3507 gettext_noop ("# Next hop to forward the packet not found "
3508 "trail setup request, packet dropped."),
3510 return GNUNET_SYSERR;
3512 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop))
3514 /* I am the destination.*/
3515 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3516 struct GNUNET_PeerIdentity next_hop;
3518 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3519 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3520 get_length = get_length + 1;
3521 memcpy (&next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
3522 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3523 get_length, final_get_path,&next_hop, &my_identity);
3529 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3530 get->desired_replication_level, &best_known_dest,
3531 &intermediate_trail_id, next_hop, 0,
3534 return GNUNET_SYSERR;
3539 * Core handler for get result
3540 * @param cls closure
3541 * @param peer sender of the request
3542 * @param message message
3543 * @return #GNUNET_OK to keep the connection open,
3544 * #GNUNET_SYSERR to close it (signal serious error)
3547 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3548 const struct GNUNET_MessageHeader *message)
3550 struct PeerGetResultMessage *get_result;
3551 struct GNUNET_PeerIdentity *get_path;
3552 struct GNUNET_PeerIdentity *put_path;
3554 size_t payload_size;
3556 unsigned int getlen;
3557 unsigned int putlen;
3558 int current_path_index;
3560 msize = ntohs (message->size);
3561 if (msize < sizeof (struct PeerGetResultMessage))
3563 GNUNET_break_op (0);
3567 get_result = (struct PeerGetResultMessage *)message;
3568 getlen = ntohl (get_result->get_path_length);
3569 putlen = ntohl (get_result->put_path_length);
3572 sizeof (struct PeerGetResultMessage) +
3573 getlen * sizeof (struct GNUNET_PeerIdentity) +
3574 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3576 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3578 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3580 GNUNET_break_op (0);
3585 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
3586 payload = &get_path[getlen];
3587 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3588 getlen * sizeof (struct GNUNET_PeerIdentity));
3591 put_path = &get_path[1];
3595 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3597 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3598 getlen, get_path, putlen,
3599 put_path, get_result->type, payload_size, payload);
3604 current_path_index = search_my_index (get_path, getlen);
3605 if (GNUNET_SYSERR == current_path_index )
3608 return GNUNET_SYSERR;
3610 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3611 &get_path[current_path_index - 1],
3612 &(get_result->querying_peer), putlen, put_path,
3613 getlen, get_path, get_result->expiration_time,
3614 payload, payload_size);
3617 return GNUNET_SYSERR;
3622 * Get the best known next destination (local_dest) among your fingers, friends
3623 * and my identity. If @a current_dest is some other peer and not me, then
3624 * compare curent_dest and local_dest.
3625 * @param final_dest_finger_value Peer closest to this value will be
3626 * @a local_best_known_dest
3627 * @param local_best_known_dest[out] Updated to peer identity which is closest to
3628 * @a final_dest_finger_value.
3629 * @param new_intermediate_trail_id In case @a local_best_known_dest is a finger,
3630 * then the trail id to reach to the finger
3631 * @param is_predecessor Is source peer trying to setup trail to its predecessor
3633 * @param current_dest Peer which should get this message ultimately according
3634 * to the peer which sent me this message. It could be me
3635 * or some other peer. In case it is not me, then I am a part
3636 * of trail to reach to that peer.
3639 static struct GNUNET_PeerIdentity *
3640 get_local_best_known_next_hop (uint64_t final_dest_finger_value,
3641 struct GNUNET_PeerIdentity *local_best_known_dest,
3642 struct GNUNET_HashCode *new_intermediate_trail_id,
3643 struct GNUNET_HashCode intermediate_trail_id,
3644 unsigned int is_predecessor,
3645 struct GNUNET_PeerIdentity *current_dest)
3647 struct GNUNET_PeerIdentity *next_hop_to_local_best_known_dest;
3649 /* Choose a local best known hop among your fingers, friends and you. */
3650 next_hop_to_local_best_known_dest = find_successor (final_dest_finger_value,
3651 local_best_known_dest,
3652 new_intermediate_trail_id,
3655 /* Are we just a part of a trail towards a finger (current_destination)? */
3656 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest)))
3658 struct GNUNET_PeerIdentity *closest_peer;
3660 /* Select best successor among one found locally and current_destination
3661 * that we got from network.*/
3662 closest_peer = select_closest_peer (local_best_known_dest,
3664 final_dest_finger_value,
3667 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3668 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3670 next_hop_to_local_best_known_dest =
3671 GDS_ROUTING_get_next_hop (intermediate_trail_id,
3672 GDS_ROUTING_SRC_TO_DEST);
3673 /* FIXME: Here we found next_hop NULL from routing table, but we still
3674 * have a next_hop from find_successor should we not break and choose that
3676 if (NULL == next_hop_to_local_best_known_dest)
3678 GNUNET_break_op (0);
3682 local_best_known_dest = current_dest;
3683 *new_intermediate_trail_id = intermediate_trail_id;
3687 GNUNET_assert (NULL != next_hop_to_local_best_known_dest);
3688 return next_hop_to_local_best_known_dest;
3692 /* Core handle for PeerTrailSetupMessage.
3693 * @param cls closure
3694 * @param message message
3695 * @param peer peer identity this notification is about
3696 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3699 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3700 const struct GNUNET_MessageHeader *message)
3702 const struct PeerTrailSetupMessage *trail_setup;
3703 const struct GNUNET_PeerIdentity *trail_peer_list;
3704 struct GNUNET_PeerIdentity *local_best_known_dest;
3705 struct GNUNET_PeerIdentity current_dest;
3706 struct GNUNET_PeerIdentity *next_hop_towards_local_best_known_dest;
3707 struct GNUNET_PeerIdentity next_peer;
3708 struct FriendInfo *target_friend;
3709 struct GNUNET_PeerIdentity source;
3710 uint64_t final_dest_finger_val;
3711 struct GNUNET_HashCode new_intermediate_trail_id;
3712 struct GNUNET_HashCode intermediate_trail_id;
3713 struct GNUNET_HashCode trail_id;
3714 unsigned int is_predecessor;
3715 uint32_t trail_length;
3718 msize = ntohs (message->size);
3719 if (msize < sizeof (struct PeerTrailSetupMessage))
3721 GNUNET_break_op (0);
3725 trail_setup = (const struct PeerTrailSetupMessage *) message;
3726 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3727 sizeof (struct GNUNET_PeerIdentity);
3728 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3729 sizeof (struct GNUNET_PeerIdentity) != 0)
3731 GNUNET_break_op (0);
3735 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3736 current_dest = trail_setup->best_known_destination;
3737 trail_id = trail_setup->trail_id;
3738 final_dest_finger_val =
3739 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3740 source = trail_setup->source_peer;
3741 is_predecessor = ntohl (trail_setup->is_predecessor);
3742 intermediate_trail_id = trail_setup->intermediate_trail_id;
3744 /* Is my routing table full? */
3745 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3747 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3748 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
3749 my_identity, is_predecessor,
3750 trail_peer_list, trail_length,
3751 trail_id, target_friend,
3752 CONGESTION_TIMEOUT);
3756 local_best_known_dest = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3758 /* Get the next hop to forward the trail setup request. */
3759 next_hop_towards_local_best_known_dest =
3760 get_local_best_known_next_hop (final_dest_finger_val,
3761 local_best_known_dest,
3762 &new_intermediate_trail_id,
3763 intermediate_trail_id,
3767 /* Am I the final destination? */
3768 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (local_best_known_dest,
3771 /* If I was not the source of this message for which now I am destination */
3772 if ((0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity)) ||
3775 GDS_ROUTING_add (trail_id, *peer, my_identity);
3777 if (0 == trail_length)
3778 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
3780 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3782 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3783 GDS_NEIGHBOURS_send_trail_setup_result (source,
3785 target_friend, trail_length,
3787 final_dest_finger_val,
3788 is_predecessor, trail_id);
3792 /* Add yourself to list of peers. */
3793 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3795 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3796 peer_list[trail_length] = my_identity;
3798 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3799 next_hop_towards_local_best_known_dest);
3800 GDS_NEIGHBOURS_send_trail_setup (source,
3801 final_dest_finger_val,
3802 *local_best_known_dest,
3803 target_friend, trail_length + 1, peer_list,
3804 is_predecessor, trail_id,
3805 &new_intermediate_trail_id);
3811 /* FIXME: here we are calculating my_index and comparing also in this function.
3812 And we are doing it again here in this function. Re factor the code. */
3814 * FIXME: Should we call this function everywhere in all the handle functions
3815 * where we have a trail to verify from or a trail id. something like
3816 * if prev hop is not same then drop the message.
3817 * Check if sender_peer and peer from which we should receive the message are
3818 * same or different.
3819 * @param trail_peer_list List of peers in trail
3820 * @param trail_length Total number of peers in @a trail_peer_list
3821 * @param sender_peer Peer from which we got the message.
3822 * @param finger_identity Finger to which trail is setup. It is not part of trail.
3823 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
3824 * message are different.
3825 * #GNUNET_NO if sender_peer and peer from which we should receive the
3826 * message are different.
3829 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
3830 unsigned int trail_length,
3831 const struct GNUNET_PeerIdentity *sender_peer,
3832 struct GNUNET_PeerIdentity finger_identity,
3833 struct GNUNET_PeerIdentity source_peer)
3837 /* I am the source peer. */
3838 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3841 /* Is the first element of the trail is sender_peer.*/
3842 if (trail_length > 0)
3844 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
3850 /* Is finger the sender peer? */
3851 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
3858 /* Get my current location in the trail. */
3859 my_index = search_my_index (trail_peer_list, trail_length);
3863 /* I am the last element in the trail. */
3864 if ((trail_length - 1) == my_index)
3866 /* Is finger the sender_peer? */
3867 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
3873 /* Is peer after me in trail the sender peer? */
3874 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
3875 &trail_peer_list[my_index + 1]))
3884 * FIXME: we should also add a case where we search if we are present in the trail
3886 * Core handle for p2p trail setup result messages.
3888 * @param message message
3889 * @param peer sender of this message.
3890 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3893 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3894 const struct GNUNET_MessageHeader *message)
3896 const struct PeerTrailSetupResultMessage *trail_result;
3897 const struct GNUNET_PeerIdentity *trail_peer_list;
3898 struct GNUNET_PeerIdentity next_hop;
3899 struct FriendInfo *target_friend;
3900 struct GNUNET_PeerIdentity querying_peer;
3901 struct GNUNET_PeerIdentity finger_identity;
3902 uint32_t trail_length;
3903 uint64_t ulitmate_destination_finger_value;
3904 uint32_t is_predecessor;
3905 struct GNUNET_HashCode trail_id;
3909 msize = ntohs (message->size);
3910 if (msize < sizeof (struct PeerTrailSetupResultMessage))
3912 GNUNET_break_op (0);
3916 trail_result = (const struct PeerTrailSetupResultMessage *) message;
3917 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
3918 sizeof (struct GNUNET_PeerIdentity);
3919 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
3920 sizeof (struct GNUNET_PeerIdentity) != 0)
3922 GNUNET_break_op (0);
3926 is_predecessor = htonl (trail_result->is_predecessor);
3927 querying_peer = trail_result->querying_peer;
3928 finger_identity = trail_result->finger_identity;
3929 trail_id = trail_result->trail_id;
3930 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
3931 ulitmate_destination_finger_value =
3932 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
3934 /* FIXME: here we are calculating my_index and comparing also in this function.
3935 And we are doing it again here in this function. Re factor the code. */
3936 /* Ensure that sender peer is the peer from which we were expecting the message. */
3937 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
3939 peer, finger_identity, querying_peer))
3941 GNUNET_break_op (0);
3942 return GNUNET_SYSERR;
3945 /* Am I the one who initiated the query? */
3946 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer,
3949 /* If I am not my own finger identity, then add routing table entry. */
3950 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3952 GDS_ROUTING_add (trail_id, my_identity, *peer);
3955 finger_table_add (finger_identity, trail_peer_list,
3956 trail_length, ulitmate_destination_finger_value,
3957 is_predecessor, trail_id);
3961 /* Get my location in the trail. */
3962 my_index = search_my_index(trail_peer_list, trail_length);
3966 return GNUNET_SYSERR;
3970 next_hop = trail_result->querying_peer;
3972 next_hop = trail_peer_list[my_index - 1];
3974 /* If the querying_peer is its own finger, then don't add an entry in routing
3975 * table as querying peer will discard the trail. */
3976 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
3977 &(trail_result->finger_identity))))
3979 GDS_ROUTING_add (trail_id, next_hop, *peer);
3982 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3983 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
3984 target_friend, trail_length, trail_peer_list,
3986 ulitmate_destination_finger_value,
3994 * @param trail Trail to be inverted
3995 * @param trail_length Total number of peers in the trail.
3996 * @return Updated trail
3998 static struct GNUNET_PeerIdentity *
3999 invert_trail (const struct GNUNET_PeerIdentity *trail,
4000 unsigned int trail_length)
4004 struct GNUNET_PeerIdentity *inverted_trail;
4006 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4009 j = trail_length - 1;
4010 while (i < trail_length)
4012 inverted_trail[i] = trail[j];
4016 return inverted_trail;
4021 * Return the shortest trail to reach from me to my_predecessor.
4022 * @param my_predecessor my current predecessor.
4023 * @param current_trail Trail from source to me.
4024 * @param current_trail_length Total number of peers in @a current_trail
4025 * @param trail_length [out] Total number of peers in selected trail.
4026 * @return Updated trail from source peer to my_predecessor.
4028 static struct GNUNET_PeerIdentity *
4029 trail_source_to_my_predecessor (const struct GNUNET_PeerIdentity *current_trail,
4030 unsigned int current_trail_length,
4031 unsigned int *trail_length)
4033 struct GNUNET_PeerIdentity *trail_me_to_predecessor;
4034 struct Trail *trail;
4035 struct Trail_Element *trail_element;
4036 struct FingerInfo *my_predecessor;
4038 unsigned int shortest_trail_length = 0;
4039 unsigned int trail_index = 0;
4041 my_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4043 GNUNET_assert (GNUNET_YES == my_predecessor->is_present);
4045 //if my_predecessor is a friend then don't send back any trail. as
4046 // there is no trail.
4049 /* Choose the shortest path from me to my predecessor. */
4050 for (i = 0; i < my_predecessor->trails_count; i++)
4052 trail = &my_predecessor->trail_list[i];
4053 if (trail->trail_length > shortest_trail_length)
4055 shortest_trail_length = trail->trail_length;
4059 *trail_length = shortest_trail_length;
4060 trail_me_to_predecessor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
4063 /* Copy the selected trail and send this trail to calling function. */
4065 trail = &my_predecessor->trail_list[trail_index];
4066 trail_element = trail->trail_head;
4067 while ( i < shortest_trail_length)
4069 trail_me_to_predecessor[i] = trail_element->peer;
4071 trail_element = trail_element->next;
4074 return trail_me_to_predecessor;
4079 * FIXME In case predecessor is a friend then do we add it in routing table.
4080 * if not then check the logic of trail teardown in case we compress the trail
4081 * such that friend is finger. then do we remove the entry from end points or
4082 * not. Ideally we should remove the entries from end point.
4083 * Add finger as your predecessor. To add, first generate a new trail id, invert
4084 * the trail to get the trail from me to finger, add an entry in your routing
4085 * table, send add trail message to peers which are part of trail from me to
4086 * finger and add finger in finger table.
4089 * @param trail_length
4092 update_predecessor (struct GNUNET_PeerIdentity finger,
4093 struct GNUNET_PeerIdentity *trail,
4094 unsigned int trail_length)
4096 struct GNUNET_HashCode trail_to_new_predecessor_id;
4097 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4098 struct FriendInfo *target_friend;
4100 /* Generate trail id for trail from me to new predecessor = finger. */
4101 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4102 &trail_to_new_predecessor_id,
4103 sizeof (trail_to_new_predecessor_id));
4105 /* Invert the trail from finger to me to get the trail from me to finger. */
4106 if (trail_length == 0)
4107 trail_to_new_predecessor = NULL;
4109 if (trail_length > 0)
4111 trail_to_new_predecessor = invert_trail (trail, trail_length);
4112 /* Add an entry in your routing table. */
4113 GDS_ROUTING_add (trail_to_new_predecessor_id,
4114 trail_to_new_predecessor[trail_length - 1],
4118 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4119 &trail_to_new_predecessor[trail_length - 1]);
4121 // Before sending the trail may be you need to compress it. And in case
4122 // it was a friend how did we got the trail. ??
4124 /* Add entry in routing table of all peers that are part of trail from me
4127 GDS_NEIGHBOURS_send_add_trail (my_identity,
4129 trail_to_new_predecessor_id,
4130 trail_to_new_predecessor,
4135 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4136 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4140 /* 3. In case you are successor, then
4141 * 3.1 check if you have a predecessor
4142 * 3.2 if no predecessor, then add the source of this message as your
4143 * predecessor. To add, first you should generate a new trail id,
4144 * invert the trail, send add trail message across new trail, add
4145 * an entry in finger table. Now, destination also have routing
4146 * table entry so add in your routing table also.
4147 * 3.3 If its closer than existing one, then do everything in step 1 and
4148 * free existing finger.
4149 * 3.3 If its same as the old one, then do nothing.
4150 * 3.4 if its not same as old one, and between source and old one, old one
4151 * is the correct predecessor, then construct a trail from source
4152 * to your old successor. scan the trail to remove duplicate entries.
4153 * 4. send verify successor result, with trail id of trail from source to
4154 * me. And also send the new trail from source to reach to its probable
4157 * 1. this function is called from both verify and notify.
4158 * 2. so write in a way that it is used in both.
4161 * Check if you have a predecessor.
4162 * 1. if no predecessor, then add finger as your predecessor. To add, first
4163 * generate a new trail id, invert the trail to get the trail from me to finger,
4164 * add an entry in your routing table, send add trail message to peers which
4165 * are part of trail from me to finger and add finger in finger table.
4166 * 2. If there is a predecessor, then compare existing one and finger.
4167 * 2.1 If finger is correct predecessor, then remove current_predecessor. And
4168 * do everything in step 1 to add finger into finger table.
4169 * 2.2 If current_predecessor is correct predecessor, the construct a trail from
4170 * finger to current_predecessor.
4173 * @param trail_length
4177 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4178 struct GNUNET_PeerIdentity *trail,
4179 unsigned int trail_length)
4181 struct FingerInfo *current_predecessor;
4182 struct GNUNET_PeerIdentity *closest_peer;
4183 uint64_t predecessor_value;
4185 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4187 /* No predecessor. Add finger as your predecessor. */
4188 if (GNUNET_NO == current_predecessor->is_present)
4190 update_predecessor (finger, trail, trail_length);
4194 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4195 closest_peer = select_closest_peer (&finger,
4196 ¤t_predecessor->finger_identity,
4197 predecessor_value, PREDECESSOR_FINGER_ID);
4199 /* Finger is the closest predecessor. Remove the existing one and add the new
4201 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, &finger))
4203 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4204 update_predecessor (finger, trail, trail_length);
4212 * FIXME: if i have no predecessor and I get a new predecessor but the first
4213 * friend to reach to that hop is congested then?
4214 * 1. check if you are the successor or not.
4215 * 2. if not then get the next hop from routing table, and pass the message,
4216 * 3. In case you are successor, then
4217 * 3.1 check if you have a predecessor
4218 * 3.2 if no predecessor, then add the source of this message as your
4219 * predecessor. To add, first you should generate a new trail id,
4220 * invert the trail, send add trail message across new trail, add
4221 * an entry in finger table. Now, destination also have routing
4222 * table entry so add in your routing table also.
4223 * 3.3 If its closer than existing one, then do everything in step 1 and
4224 * free existing finger.
4225 * 3.3 If its same as the old one, then do nothing.
4226 * 3.4 if its not same as old one, and between source and old one, old one
4227 * is the correct predecessor, then choose the shortest path to reach
4228 * from you to your predecessor. Pass this trail to source of this message.
4229 * It is the responsibility of source peer to scan the trail to reach to
4230 * its new probable successor.
4231 * 4. send verify successor result, with trail id of trail from source to
4232 * me. And also send the trail from me to reach to my predecessor, if
4233 * my_predecessor != source.
4235 * Core handle for p2p verify successor messages.
4236 * @param cls closure
4237 * @param message message
4238 * @param peer peer identity this notification is about
4239 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4242 handle_dht_p2p_verify_successor(void *cls,
4243 const struct GNUNET_PeerIdentity *peer,
4244 const struct GNUNET_MessageHeader *message)
4246 const struct PeerVerifySuccessorMessage *vsm;
4247 const struct GNUNET_HashCode *trail_id;
4248 struct GNUNET_PeerIdentity successor;
4249 struct GNUNET_PeerIdentity source_peer;
4250 struct GNUNET_PeerIdentity *trail;
4251 struct GNUNET_PeerIdentity *next_hop;
4252 struct GNUNET_PeerIdentity *trail_to_predecessor;
4253 struct FingerInfo *current_predecessor;
4254 struct FriendInfo *target_friend;
4255 unsigned int trail_to_predecessor_length;
4257 unsigned int trail_length;
4259 msize = ntohs (message->size);
4261 /* Here we pass trail to reach from source to successor, and in case successor
4262 * does not have any predecessor, then we will add source as my predecessor.
4263 * So we pass the trail along with trail id. */
4264 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4266 GNUNET_break_op (0);
4270 vsm = (const struct PeerVerifySuccessorMessage *) message;
4271 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4272 sizeof (struct GNUNET_PeerIdentity);
4273 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4274 sizeof (struct GNUNET_PeerIdentity) != 0)
4276 GNUNET_break_op (0);
4281 trail_id = GNUNET_new (struct GNUNET_HashCode);
4282 trail_id = &vsm->trail_id;
4283 source_peer = vsm->source_peer;
4284 successor = vsm->successor;
4285 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4287 //GDS_ROUTING_test_print(); //FIXME REMOVE AFTERWARDS.
4288 //FIXME: we can have a check if peer is correct peer which should have
4289 // sent this message. use same function is_sender_peer_correct
4290 // but specify direction so that the function can be used in other functions
4293 /* I am not the successor of source_peer. Pass the message to next_hop on
4295 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4297 next_hop = GDS_ROUTING_get_next_hop (*trail_id, GDS_ROUTING_SRC_TO_DEST);
4298 if (NULL == next_hop)
4301 return GNUNET_SYSERR;
4303 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4305 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4306 trail_id, trail, trail_length,
4311 /* I am the destination of this message. */
4313 /* Check if there is a predecessor or not. */
4314 compare_and_update_predecessor (source_peer, trail, trail_length);
4316 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4317 /* Is source of this message my predecessor. */
4318 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4321 trail_to_predecessor = NULL;
4322 trail_to_predecessor_length = 0;
4326 if (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4327 ¤t_predecessor->finger_identity)))
4329 /* Only if current predecessor is not a friend, we have a trail to reach
4330 to it. Only in that case we pass the trail. */
4331 trail_to_predecessor =
4332 trail_source_to_my_predecessor (trail, trail_length,
4333 &trail_to_predecessor_length);
4337 trail_to_predecessor = NULL;
4338 trail_to_predecessor_length = 0;
4342 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4343 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4344 current_predecessor->finger_identity,
4345 *trail_id, trail_to_predecessor,
4346 trail_to_predecessor_length,
4347 GDS_ROUTING_DEST_TO_SRC,
4354 * Construct the trail from me to probable successor that goes through current
4355 * successor. Scan this trail to check if you can shortcut the trail somehow.
4356 * In case we can shortcut the trail, don't send trail compression as we don't
4357 * have any entry in routing table.
4358 * @param current_successor
4359 * @param probable_successor
4360 * @param trail_from_curr_to_probable_successor
4361 * @param trail_from_curr_to_probable_successor_length
4362 * @param trail_to_new_successor_length
4365 static struct GNUNET_PeerIdentity *
4366 get_trail_to_new_successor (struct FingerInfo *current_successor,
4367 struct GNUNET_PeerIdentity probable_successor,
4368 const struct GNUNET_PeerIdentity *trail,
4369 unsigned int trail_length,
4370 unsigned int *trail_to_new_successor_length)
4372 struct GNUNET_PeerIdentity *trail_to_new_successor;
4374 /* If the probable successor is a friend, then we don't need to have a trail
4376 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4377 &probable_successor))
4379 trail_to_new_successor = NULL;
4380 *trail_to_new_successor_length = 0;
4381 return trail_to_new_successor;
4385 * FIXME: can we some how use the select_finger_trail here??
4386 * complete this logic.
4387 * 1. Choose the shortest trail to reach to current successor.
4388 * 2. append the trail with the current trail
4389 * 3. scan the trail for duplicate elements
4390 * 4. scan the trail for friend
4391 * 5. get the shortest trail.
4392 * 6. send back the trail.
4399 * Compare probable successor and current successor.
4400 * If the probable successor is the correct successor, then construct the trail
4401 * from me to probable successor that goes through current successor. Scan this
4402 * trail to check if you can shortcut the trail somehow. In case we can short
4403 * cut the trail, don't send trail compression as we don't have any entry in
4405 * Once you have scanned trail, then add an entry in finger table.
4406 * Add an entry in routing table (Only if new successor is NOT a friend).
4407 * @param probable_successor Peer which could be our successor
4408 * @param trail_from_curr_to_probable_successor Trail from current successor
4409 * to probable successor, NOT
4411 * @param trail_from_curr_to_probable_successor_length Total number of peers
4412 * in @a trail_from_curr_to_probable_successor
4415 compare_and_update_successor (struct GNUNET_PeerIdentity probable_successor,
4416 const struct GNUNET_PeerIdentity *trail_from_curr_to_probable_successor,
4417 unsigned int trail_from_curr_to_probable_successor_length)
4419 struct GNUNET_PeerIdentity *closest_peer;
4420 struct GNUNET_PeerIdentity *trail_to_new_successor;
4421 struct GNUNET_HashCode trail_id;
4422 unsigned int trail_to_new_successor_length;
4423 uint64_t successor_value;
4424 struct FingerInfo *current_successor;
4425 struct FriendInfo *target_friend;
4427 current_successor = &finger_table[0];
4428 GNUNET_assert (GNUNET_YES == current_successor->is_present);
4430 /* Compute the 64 bit value of successor identity. We need this as we need to
4431 * find the closest peer w.r.t this value.*/
4432 successor_value = compute_finger_identity_value (0);
4433 closest_peer = select_closest_peer (¤t_successor->finger_identity,
4434 &probable_successor,
4435 successor_value, GNUNET_NO);
4437 /* If the current_successor is the closest one, then exit. */
4438 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4439 ¤t_successor->finger_identity))
4442 /* probable successor is the closest_peer. */
4444 /* Get the trail to reach to your new successor. */
4445 trail_to_new_successor = get_trail_to_new_successor (current_successor,
4447 trail_from_curr_to_probable_successor,
4448 trail_from_curr_to_probable_successor_length,
4449 &trail_to_new_successor_length);
4450 /* Remove the existing successor. */
4451 remove_existing_finger (current_successor, 0);
4453 /* Generate a new trail id to reach to your new successor. */
4454 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4455 &trail_id, sizeof (trail_id));
4456 add_new_finger (probable_successor, trail_to_new_successor,
4457 trail_to_new_successor_length, trail_id, 0);
4459 /* If probable successor is not a friend, then add an entry in your own
4461 if (trail_to_new_successor_length > 0)
4463 GDS_ROUTING_add (trail_id, my_identity, trail_to_new_successor[0]);
4464 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4465 &trail_to_new_successor[0]);
4469 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4470 &probable_successor);
4473 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4474 trail_from_curr_to_probable_successor,
4475 trail_from_curr_to_probable_successor_length,
4483 * 1. If you are not the querying peer then pass on the message,
4484 * 2. If you are querying peer, then
4485 * 2.1 is new successor same as old one
4486 * 2.1.1 if yes then do noting
4487 * 2.1.2 if no then you need to notify the new one about your existence,
4488 * 2.1.2,1 also you need to remove the older successor, remove entry
4489 * from finger table, send trail teardown message across all the trail
4490 * of older successor. Call notify new successor with new trail id
4491 * and new trail to reach it.
4492 * Core handle for p2p verify successor result messages.
4493 * @param cls closure
4494 * @param message message
4495 * @param peer peer identity this notification is about
4496 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4499 handle_dht_p2p_verify_successor_result(void *cls,
4500 const struct GNUNET_PeerIdentity *peer,
4501 const struct GNUNET_MessageHeader *message)
4503 const struct PeerVerifySuccessorResultMessage *vsrm;
4504 enum GDS_ROUTING_trail_direction trail_direction;
4505 struct GNUNET_PeerIdentity querying_peer;
4506 struct GNUNET_HashCode trail_id;
4507 struct GNUNET_PeerIdentity *next_hop;
4508 struct FriendInfo *target_friend;
4509 struct GNUNET_PeerIdentity probable_successor;
4510 const struct GNUNET_PeerIdentity *trail;
4511 unsigned int trail_length;
4514 msize = ntohs (message->size);
4515 /* We send a trail to reach from old successor to new successor, if
4516 * old_successor != new_successor.*/
4517 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4519 GNUNET_break_op (0);
4523 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4524 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4525 sizeof (struct GNUNET_PeerIdentity);
4527 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4528 sizeof (struct GNUNET_PeerIdentity) != 0)
4530 GNUNET_break_op (0);
4534 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4535 querying_peer = vsrm->querying_peer;
4536 trail_direction = ntohl (vsrm->trail_direction);
4537 trail_id = vsrm->trail_id;
4538 probable_successor = vsrm->probable_successor;
4540 //FIXME: add a check to ensure that peer from which you got the message is
4542 /* I am the querying_peer. */
4543 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4545 compare_and_update_successor (probable_successor, trail, trail_length);
4549 /*If you are not the querying peer then pass on the message */
4550 GNUNET_assert (NULL != (next_hop =
4551 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
4552 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4553 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4554 vsrm->current_successor,
4555 probable_successor, trail_id,
4558 trail_direction, target_friend);
4564 * Add entry in your routing table if source of the message is not a friend.
4565 * Irrespective if destination peer accepts source peer as predecessor or not,
4566 * we need to add an entry. So, that in next round to verify successor, source
4567 * is able to reach to its successor.
4568 * Check if you are the new successor of this message
4569 * 1. If yes the call function compare_and_update_successor(). This function
4570 * checks if source is real predecessor or not and take action accordingly.
4571 * 2. If not then find the next hop to find the message from the trail that
4572 * you got from the message and pass on the message.
4573 * Core handle for p2p notify new successor messages.
4574 * @param cls closure
4575 * @param message message
4576 * @param peer peer identity this notification is about
4577 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4580 handle_dht_p2p_notify_new_successor(void *cls,
4581 const struct GNUNET_PeerIdentity *peer,
4582 const struct GNUNET_MessageHeader *message)
4584 const struct PeerNotifyNewSuccessorMessage *nsm;
4585 struct GNUNET_PeerIdentity *trail;
4586 struct GNUNET_PeerIdentity source;
4587 struct GNUNET_PeerIdentity new_successor;
4588 struct GNUNET_HashCode trail_id;
4589 struct GNUNET_PeerIdentity next_hop;
4590 struct FriendInfo *target_friend;
4593 uint32_t trail_length;
4595 msize = ntohs (message->size);
4596 /* We have the trail to reach from source to new successor. */
4597 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
4599 GNUNET_break_op (0);
4603 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
4604 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
4605 sizeof (struct GNUNET_PeerIdentity);
4606 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4607 sizeof (struct GNUNET_PeerIdentity) != 0)
4609 GNUNET_break_op (0);
4613 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
4614 source = nsm->source_peer;
4615 new_successor = nsm->new_successor;
4616 trail_id = nsm->trail_id;
4618 //FIXME: add a check to make sure peer is correct.
4620 /* I am the new_successor to source_peer. */
4621 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
4623 /* Add an entry in routing table only if new predecessor is not a friend. */
4624 if (NULL == GNUNET_CONTAINER_multipeermap_get(friend_peermap, &source))
4626 GDS_ROUTING_add (trail_id, *peer, my_identity);
4628 compare_and_update_predecessor (source, trail, trail_length);
4632 /* I am part of trail to reach to successor. */
4633 my_index = search_my_index (trail, trail_length);
4636 GNUNET_break_op (0);
4637 return GNUNET_SYSERR;
4639 if (trail_length == my_index)
4640 next_hop = new_successor;
4642 next_hop = trail[my_index + 1];
4644 /* Add an entry in routing table for trail from source to its new successor. */
4645 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
4646 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4647 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
4649 trail_id, target_friend);
4656 * 1. Set the congestion timeout for the friend which is congested and sent
4658 * 2. Check if you were the source of this message
4659 * 2.1 If yes then exit. find_finger_trail_task is scheduled periodically.
4660 * So, we will eventually send a new request to setup trail to finger.
4661 * 2. Check if you can handle more trails through you. (Routing table space)
4662 * 2.1 If not then you are congested. Set your congestion time and pass this
4663 * message to peer before you in the trail setup so far.
4664 * 2.2 If yes, the call find_successor(). It will give you the next hop to
4665 * pass this message.
4666 * 2.2.1 If you are the final destination, then send back the trail setup
4668 * 2.2.2 If you are not the final dest, then send trail setup message to
4670 * Core handler for P2P trail rejection message
4671 * @param cls closure
4672 * @param message message
4673 * @param peer peer identity this notification is about
4674 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4677 handle_dht_p2p_trail_setup_rejection (void *cls,
4678 const struct GNUNET_PeerIdentity *peer,
4679 const struct GNUNET_MessageHeader *message)
4681 const struct PeerTrailRejectionMessage *trail_rejection;
4682 unsigned int trail_length;
4683 const struct GNUNET_PeerIdentity *trail_peer_list;
4684 struct FriendInfo *target_friend;
4685 struct GNUNET_TIME_Relative congestion_timeout;
4686 struct GNUNET_HashCode trail_id;
4687 struct GNUNET_PeerIdentity next_destination;
4688 struct GNUNET_HashCode new_intermediate_trail_id;
4689 struct GNUNET_PeerIdentity next_peer;
4690 struct GNUNET_PeerIdentity source;
4691 struct GNUNET_PeerIdentity *next_hop;
4692 uint64_t ultimate_destination_finger_value;
4693 unsigned int is_predecessor;
4696 msize = ntohs (message->size);
4697 /* We are passing the trail setup so far. */
4698 if (msize < sizeof (struct PeerTrailRejectionMessage))
4700 GNUNET_break_op (0);
4704 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
4705 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
4706 sizeof (struct GNUNET_PeerIdentity);
4707 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4708 sizeof (struct GNUNET_PeerIdentity) != 0)
4710 GNUNET_break_op (0);
4714 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
4715 is_predecessor = ntohl (trail_rejection->is_predecessor);
4716 congestion_timeout = trail_rejection->congestion_time;
4717 source = trail_rejection->source_peer;
4718 trail_id = trail_rejection->trail_id;
4719 ultimate_destination_finger_value =
4720 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
4722 /* First set the congestion time of the friend that sent you this message. */
4723 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4724 target_friend->congestion_timestamp =
4725 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
4726 congestion_timeout);
4728 /* I am the source peer which wants to setup the trail. Do nothing.
4729 * send_find_finger_trail_task is scheduled periodically.*/
4730 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
4733 /* If I am congested then pass this message to peer before me in trail. */
4734 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
4736 struct GNUNET_PeerIdentity *new_trail;
4737 unsigned int new_trail_length;
4739 /* Remove yourself from the trail setup so far. */
4740 if (trail_length == 1)
4743 new_trail_length = 0;
4748 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
4749 sizeof (struct GNUNET_PeerIdentity));
4751 /* Remove myself from the trail. */
4752 new_trail_length = trail_length -1;
4753 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4754 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4757 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4758 GDS_NEIGHBOURS_send_trail_rejection (source,
4759 ultimate_destination_finger_value,
4760 my_identity, is_predecessor,
4761 new_trail,new_trail_length,trail_id,
4762 target_friend, CONGESTION_TIMEOUT);
4766 /* Look for next_hop to pass the trail setup message */
4767 next_hop = find_successor (ultimate_destination_finger_value,
4769 &new_intermediate_trail_id,
4772 /* Am I the final destination? */
4773 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))
4775 /* Add an entry in routing table only
4776 * 1. If I am not the original source which sent the request for trail setup
4777 * 2. If trail length > 0.
4778 * NOTE: In case trail length > 0 and source is my friend, then also I add
4779 * an entry in routing table,as we will send a trail compression message
4782 if ((0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity)) ||
4784 GNUNET_assert (GNUNET_YES == GDS_ROUTING_add (trail_id, *peer, my_identity));
4786 if (0 == trail_length)
4789 next_peer = trail_peer_list[trail_length-1];
4791 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
4792 GDS_NEIGHBOURS_send_trail_setup_result (source,
4794 target_friend, trail_length,
4797 ultimate_destination_finger_value,
4802 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4804 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
4805 peer_list[trail_length] = my_identity;
4807 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4808 GDS_NEIGHBOURS_send_trail_setup (source,
4809 ultimate_destination_finger_value,
4811 target_friend, trail_length + 1, peer_list,
4812 is_predecessor, trail_id,
4813 &new_intermediate_trail_id);
4820 * If you are the new first friend, then update prev hop to source of this message
4821 * else get the next hop and pass this message forward to ultimately reach
4823 * Core handle for p2p trail tear compression messages.
4824 * @param cls closure
4825 * @param message message
4826 * @param peer peer identity this notification is about
4827 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4830 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
4831 const struct GNUNET_MessageHeader *message)
4833 const struct PeerTrailCompressionMessage *trail_compression;
4834 struct GNUNET_PeerIdentity *next_hop;
4835 struct FriendInfo *target_friend;
4836 struct GNUNET_HashCode trail_id;
4839 msize = ntohs (message->size);
4840 /* Here we pass only the trail id. */
4841 if (msize != sizeof (struct PeerTrailCompressionMessage))
4843 GNUNET_break_op (0);
4847 trail_compression = (const struct PeerTrailCompressionMessage *) message;
4848 trail_id = trail_compression->trail_id;
4849 //FIXME: again check if peer is the correct peer. same logic as
4850 //trail teardown make a generic function.
4852 /* Am I the new first friend to reach to finger of this trail. */
4853 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->new_first_friend),
4856 /* Update your prev hop to source of this message. */
4857 GDS_ROUTING_update_trail_prev_hop (trail_id,
4858 trail_compression->source_peer);
4862 /* Pass the message to next hop to finally reach to new_first_friend. */
4863 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4864 if (NULL == next_hop)
4870 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
4871 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4872 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
4874 trail_compression->new_first_friend,
4881 * Remove entry from your own routing table and pass the message to next
4882 * peer in the trail.
4883 * Core handler for trail teardown message.
4884 * @param cls closure
4885 * @param message message
4886 * @param peer sender of this messsage.
4887 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4890 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
4891 const struct GNUNET_MessageHeader *message)
4893 const struct PeerTrailTearDownMessage *trail_teardown;
4894 enum GDS_ROUTING_trail_direction trail_direction;
4895 struct GNUNET_HashCode trail_id;
4896 struct GNUNET_PeerIdentity *prev_hop;
4897 struct GNUNET_PeerIdentity *next_hop;
4899 msize = ntohs (message->size);
4900 /* Here we pass only the trail id. */
4901 if (msize != sizeof (struct PeerTrailTearDownMessage))
4903 GNUNET_break_op (0);
4907 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
4908 trail_direction = ntohl (trail_teardown->trail_direction);
4909 trail_id = trail_teardown->trail_id;
4911 /* Check if peer is the real peer from which we should get this message.*/
4912 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
4913 /* FIXME: is using negation of trail direction correct. */
4914 prev_hop = GDS_ROUTING_get_next_hop (trail_id, !trail_direction);
4915 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
4918 return GNUNET_SYSERR;
4920 GNUNET_free_non_null (prev_hop);
4922 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
4923 if (NULL == next_hop)
4926 return GNUNET_SYSERR;
4929 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
4931 /* If next_hop is my_identity, it means I am the final destination. */
4932 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
4935 /* If not final destination, then send a trail teardown message to next hop.*/
4936 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, next_hop);
4942 * Add an entry in your routing table. If you are destination of this message
4943 * then next_hop in routing table should be your own identity. If you are NOT
4944 * destination, then get the next hop and forward message to it.
4945 * Core handle for p2p add trail message.
4946 * @param cls closure
4947 * @param message message
4948 * @param peer peer identity this notification is about
4949 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4952 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
4953 const struct GNUNET_MessageHeader *message)
4955 const struct PeerAddTrailMessage *add_trail;
4956 const struct GNUNET_PeerIdentity *trail;
4957 struct GNUNET_HashCode trail_id;
4958 struct GNUNET_PeerIdentity destination_peer;
4959 struct GNUNET_PeerIdentity source_peer;
4960 struct GNUNET_PeerIdentity next_hop;
4961 unsigned int trail_length;
4962 unsigned int my_index;
4965 msize = ntohs (message->size);
4966 /* In this message we pass the whole trail from source to destination as we
4967 * are adding that trail.*/
4968 if (msize < sizeof (struct PeerAddTrailMessage))
4970 GNUNET_break_op (0);
4974 add_trail = (const struct PeerAddTrailMessage *) message;
4975 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
4976 sizeof (struct GNUNET_PeerIdentity);
4977 if ((msize - sizeof (struct PeerAddTrailMessage)) %
4978 sizeof (struct GNUNET_PeerIdentity) != 0)
4980 GNUNET_break_op (0);
4984 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
4985 destination_peer = add_trail->destination_peer;
4986 source_peer = add_trail->source_peer;
4987 trail_id = add_trail->trail_id;
4989 //FIXME: add a check that sender peer is not malicious. Make it a generic
4990 // function so that it can be used in all other functions where we need the
4991 // same functionality.
4993 /* I am not the destination of the trail. */
4994 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
4996 struct FriendInfo *target_friend;
4998 /* Get my location in the trail. */
4999 my_index = search_my_index (trail, trail_length);
5000 if (GNUNET_SYSERR == my_index)
5002 GNUNET_break_op (0);
5003 return GNUNET_SYSERR;
5007 next_hop = source_peer;
5009 next_hop = trail[trail_length - 1];
5011 /* Add in your routing table. */
5012 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5013 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
5014 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5015 trail, trail_length, target_friend);
5019 /* I am the destination. Add an entry in routing table. */
5020 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5026 * Send trail teardown and free the trail of the finger for which the first
5027 * friend to reach to a finger is disconnected_friend
5028 * @param disconnected_friend PeerIdentity of friend which got disconnected
5029 * @param remove_finger Finger whose trail we need to check if it has
5030 * disconnected_friend as the first hop.
5031 * @return Total number of trails in which disconnected_friend was the first
5035 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5036 struct FingerInfo *remove_finger)
5038 unsigned int matching_trails_count;
5039 struct Trail *trail;
5042 /* Number of trails with disconnected_friend as the first hop in the trail
5043 * to reach from me to remove_finger, NOT including endpoints. */
5044 matching_trails_count = 0;
5046 /* Iterate over all the trails of finger. */
5047 for (i = 0; i < remove_finger->trails_count; i++)
5049 trail = &remove_finger->trail_list[i];
5051 /* First friend to reach to finger is disconnected_peer. */
5052 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5053 disconnected_friend))
5055 matching_trails_count++;
5056 send_trail_teardown (remove_finger, trail);
5057 if (trail->trail_length > 0)
5061 return matching_trails_count;
5066 * Iterate over finger_table entries.
5067 * 0. Ignore finger which is my_identity.
5068 * 1. If disconnected_friend is a finger, then free that entry. Don't send trail
5069 * teardown message, as there is no trail to reach to a finger which is a friend.
5070 * 2. Check if disconnected_friend peer is the first friend in the trail to reach to a finger.
5071 * 2.1 Send trail teardown message across all the trails in which disconnected
5072 * peer is the first friend in the trail. If disconnected_friend peer is the
5073 * first friend in all the trails to reach finger, then remove the finger.
5074 * @param disconnected_friend Peer identity of friend which got disconnected.
5077 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_friend)
5079 struct FingerInfo *remove_finger;
5080 int removed_trails_count;
5083 /* Iterate over finger table entries. */
5084 for (i = 0; i < MAX_FINGERS; i++)
5086 remove_finger = &finger_table[i];
5088 /* No finger stored at this trail index. */
5089 if (GNUNET_NO == remove_finger->is_present)
5092 /* I am my own finger, then ignore this finger. */
5093 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5097 /* Is finger same as disconnected friend? */
5098 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5099 &remove_finger->finger_identity))
5101 /* No trail to reach this finger as it is a friend, don't send
5102 * trail_teardown message. */
5103 remove_finger->is_present = GNUNET_NO;
5104 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5108 /* Iterate over the list of trails to reach remove_finger. Check if
5109 * disconnected_friend is the first friend in any of the trail. */
5110 removed_trails_count = remove_matching_trails (disconnected_friend,
5113 /* All the finger trails has disconnected_friend as the first friend,
5114 * so free the finger. */
5115 if (removed_trails_count == remove_finger->trails_count)
5117 remove_finger->is_present = GNUNET_NO;
5118 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5125 * Method called whenever a peer disconnects.
5127 * @param cls closure
5128 * @param peer peer identity this notification is about
5131 handle_core_disconnect (void *cls,
5132 const struct GNUNET_PeerIdentity *peer)
5134 struct FriendInfo *remove_friend;
5136 /* If disconnected to own identity, then return. */
5137 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5140 GNUNET_assert (NULL != (remove_friend =
5141 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5143 /* Remove fingers with peer as first friend or if peer is a finger. */
5144 remove_matching_fingers (peer);
5146 /* Remove any trail from routing table of which peer is a part of. */
5147 GDS_ROUTING_remove_trail_by_peer (peer);
5149 /* Remove peer from friend_peermap. */
5150 GNUNET_assert (GNUNET_YES ==
5151 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5154 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5157 /* If there are no more friends in friend_peermap, then don't schedule
5158 * find_finger_trail_task. */
5159 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5161 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5162 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5171 * Method called whenever a peer connects.
5173 * @param cls closure
5174 * @param peer_identity peer identity this notification is about
5177 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5179 struct FriendInfo *friend;
5181 /* Check for connect to self message */
5182 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5185 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5187 /* If peer already exists in our friend_peermap, then exit. */
5188 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5195 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
5198 friend = GNUNET_new (struct FriendInfo);
5199 friend->id = *peer_identity;
5201 GNUNET_assert (GNUNET_OK ==
5202 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5203 peer_identity, friend,
5204 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5207 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5208 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5209 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5214 * To be called on core init/fail.
5216 * @param cls service closure
5217 * @param identity the public identity of this peer
5220 core_init (void *cls,
5221 const struct GNUNET_PeerIdentity *identity)
5223 my_identity = *identity;
5224 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5225 "my_indentity = %s\n",GNUNET_i2s(&my_identity));
5227 FPRINTF (stderr,_("\nSUPU %s, %s, %d, my_identity = %s"),
5228 __FILE__, __func__,__LINE__, GNUNET_i2s (&my_identity));
5234 * Initialize finger table entries.
5237 finger_table_init ()
5241 for(i = 0; i < MAX_FINGERS; i++)
5243 finger_table[i].is_present = GNUNET_NO;
5244 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5250 * Initialize neighbours subsystem.
5251 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5254 GDS_NEIGHBOURS_init (void)
5256 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5257 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
5258 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
5259 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
5260 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
5261 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
5262 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
5263 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5264 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5265 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_REJECTION, 0},
5266 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION,
5267 sizeof (struct PeerTrailCompressionMessage)},
5268 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN,
5269 sizeof (struct PeerTrailTearDownMessage)},
5270 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL, 0},
5275 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5276 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5277 GNUNET_NO, core_handlers);
5278 if (NULL == core_api)
5279 return GNUNET_SYSERR;
5281 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5282 finger_table_init ();
5289 * Shutdown neighbours subsystem.
5292 GDS_NEIGHBOURS_done (void)
5294 if (NULL == core_api)
5297 GNUNET_CORE_disconnect (core_api);
5300 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5301 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5302 friend_peermap = NULL;
5304 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5307 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5308 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5316 * @return my identity
5318 struct GNUNET_PeerIdentity
5319 GDS_NEIGHBOURS_get_my_id (void)