2 This file is part of GNUnet.
3 (C) 2009-2014 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file dht/gnunet-service-xdht_neighbours.c
23 * @brief GNUnet DHT service's finger and friend table management code
24 * @author Supriti Singh
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_ats_service.h"
34 #include "gnunet_core_service.h"
35 #include "gnunet_datacache_lib.h"
36 #include "gnunet_transport_service.h"
37 #include "gnunet_dht_service.h"
38 #include "gnunet_statistics_service.h"
39 #include "gnunet-service-xdht.h"
40 #include "gnunet-service-xdht_clients.h"
41 #include "gnunet-service-xdht_datacache.h"
42 #include "gnunet-service-xdht_neighbours.h"
43 #include "gnunet-service-xdht_routing.h"
49 * 1. In X-Vine paper, there is no policy defined for replicating the data to
50 * recover in case of peer failure. We can do it in Chord way. In R5N, the key
51 * is hashed and then data is stored according to the key value generated after
57 * Maximum possible fingers (including predecessor) of a peer
59 #define MAX_FINGERS 65
62 * Maximum allowed number of pending messages per friend peer.
64 #define MAXIMUM_PENDING_PER_FRIEND 64
67 * How long to wait before sending another find finger trail request
69 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
72 * How long at most to wait for transmission of a request to a friend ?
74 #define GET_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
77 * Duration for which I may remain congested.
78 * Note: Its a static value. In future, a peer may do some analysis and calculate
79 * congestion_timeout based on 'some' parameters.
81 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
84 * Maximum number of trails allowed to go through a friend.
86 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
89 * Maximum number of trails stored per finger.
91 #define MAXIMUM_TRAILS_PER_FINGER 1
94 * Finger map index for predecessor entry in finger table.
96 #define PREDECESSOR_FINGER_ID 64
99 * Wrap around in peer identity circle.
101 #define PEER_IDENTITES_WRAP_AROUND pow(2, 64) - 1
104 * FIXME: Its use only at 3 places check if you can remove it.
105 * To check if a finger is predecessor or not.
107 enum GDS_NEIGHBOURS_finger_type
109 GDS_FINGER_TYPE_PREDECESSOR = 1,
110 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
113 GNUNET_NETWORK_STRUCT_BEGIN
118 struct PeerPutMessage
121 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
123 struct GNUNET_MessageHeader header;
128 uint32_t options GNUNET_PACKED;
133 uint32_t block_type GNUNET_PACKED;
138 uint32_t hop_count GNUNET_PACKED;
141 * Replication level for this message
142 * In the current implementation, this value is not used.
144 uint32_t desired_replication_level GNUNET_PACKED;
147 * Length of the PUT path that follows (if tracked).
149 uint32_t put_path_length GNUNET_PACKED;
152 * Best known destination (could be my friend or finger) which should
153 * get this message next.
155 struct GNUNET_PeerIdentity best_known_destination;
158 * In case best_known_destination is a finger, then trail to reach
159 * to that finger. Else its default value is 0.
161 struct GNUNET_HashCode intermediate_trail_id;
164 * When does the content expire?
166 struct GNUNET_TIME_AbsoluteNBO expiration_time;
169 * The key to store the value under.
171 struct GNUNET_HashCode key GNUNET_PACKED;
173 /* put path (if tracked) */
182 struct PeerGetMessage
185 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
187 struct GNUNET_MessageHeader header;
192 uint32_t options GNUNET_PACKED;
195 * Desired content type.
197 uint32_t block_type GNUNET_PACKED;
202 uint32_t hop_count GNUNET_PACKED;
205 * Desired replication level for this request.
206 * In the current implementation, this value is not used.
208 uint32_t desired_replication_level GNUNET_PACKED;
211 * Total number of peers in get path.
213 unsigned int get_path_length;
216 * Best known destination (could be my friend or finger) which should
217 * get this message next.
219 struct GNUNET_PeerIdentity best_known_destination;
222 * In case best_known_destination is a finger, then trail to reach
223 * to that finger. Else its default value is 0.
225 struct GNUNET_HashCode intermediate_trail_id;
228 * The key we are looking for.
230 struct GNUNET_HashCode key;
233 /* struct GNUNET_PeerIdentity[]*/
239 struct PeerGetResultMessage
242 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
244 struct GNUNET_MessageHeader header;
247 * The type for the data.
249 uint32_t type GNUNET_PACKED;
252 * Number of peers recorded in the outgoing path from source to the
253 * stored location of this message.
255 uint32_t put_path_length GNUNET_PACKED;
258 * Length of the GET path that follows (if tracked).
260 uint32_t get_path_length GNUNET_PACKED;
263 * Peer which queried for get and should get the result.
265 struct GNUNET_PeerIdentity querying_peer;
268 * When does the content expire?
270 struct GNUNET_TIME_Absolute expiration_time;
273 * The key of the corresponding GET request.
275 struct GNUNET_HashCode key;
277 /* put path (if tracked) */
279 /* get path (if tracked) */
286 * P2P Trail setup message
288 struct PeerTrailSetupMessage
291 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
293 struct GNUNET_MessageHeader header;
296 * Is source_peer trying to setup the trail to a predecessor or any finger.
298 uint32_t is_predecessor;
301 * Peer closest to this value will be our finger.
303 uint64_t final_destination_finger_value;
306 * Source peer which wants to setup the trail to one of its finger.
308 struct GNUNET_PeerIdentity source_peer;
311 * Best known destination (could be my friend or finger) which should
312 * get this message next.
314 struct GNUNET_PeerIdentity best_known_destination;
317 * In case best_known_destination is a finger, then trail id of trail to
318 * reach to this finger.
320 struct GNUNET_HashCode intermediate_trail_id;
323 * Trail id for trail which we are trying to setup.
325 struct GNUNET_HashCode trail_id;
327 /* List of peers which are part of trail setup so far.
328 * Trail does NOT include source_peer and peer which will be closest to
329 * ultimate_destination_finger_value.
330 * struct GNUNET_PeerIdentity trail[]
335 * P2P Trail Setup Result message
337 struct PeerTrailSetupResultMessage
341 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
343 struct GNUNET_MessageHeader header;
346 * Finger to which we have found the path.
348 struct GNUNET_PeerIdentity finger_identity;
351 * Peer which started trail_setup to find trail to finger_identity
353 struct GNUNET_PeerIdentity querying_peer;
356 * Is the trail setup to querying_peer's predecessor or finger?
358 uint32_t is_predecessor;
361 * Value to which finger_identity is the closest peer.
363 uint64_t ulitmate_destination_finger_value;
366 * Identifier of the trail from querying peer to finger_identity, NOT
367 * including both endpoints.
369 struct GNUNET_HashCode trail_id;
371 /* List of peers which are part of the trail from querying peer to
372 * finger_identity, NOT including both endpoints.
373 * struct GNUNET_PeerIdentity trail[]
378 * P2P Verify Successor Message.
380 struct PeerVerifySuccessorMessage
383 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
385 struct GNUNET_MessageHeader header;
388 * Peer which wants to verify its successor.
390 struct GNUNET_PeerIdentity source_peer;
393 * Source Peer's current successor.
395 struct GNUNET_PeerIdentity successor;
398 * Identifier of trail to reach from source_peer to successor.
400 struct GNUNET_HashCode trail_id;
402 /* List of the peers which are part of trail to reach from source_peer
403 * to successor, NOT including them
404 * struct GNUNET_PeerIdentity trail[]
409 * P2P Verify Successor Result Message
411 struct PeerVerifySuccessorResultMessage
414 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
416 struct GNUNET_MessageHeader header;
419 * Peer which sent the request to verify its successor.
421 struct GNUNET_PeerIdentity querying_peer;
424 * Successor to which PeerVerifySuccessorMessage was sent.
426 struct GNUNET_PeerIdentity current_successor;
429 * Current Predecessor of source_successor. It can be same as querying peer
430 * or different. In case it is different then it can be querying_peer's
431 * probable successor.
433 struct GNUNET_PeerIdentity probable_successor;
436 * Trail identifier of trail from querying_peer to current_successor.
438 struct GNUNET_HashCode trail_id;
441 * Direction in which we are looking at the trail.
443 uint32_t trail_direction;
445 /* In case probable_successor != querying_peer, then trail to reach from
446 * querying_peer to probable_successor, NOT including end points.
447 * struct GNUNET_PeerIdentity trail[]
452 * P2P Notify New Successor Message.
454 struct PeerNotifyNewSuccessorMessage
457 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
459 struct GNUNET_MessageHeader header;
462 * Peer which wants to notify its new successor.
464 struct GNUNET_PeerIdentity source_peer;
467 * New successor of source_peer.
469 struct GNUNET_PeerIdentity new_successor;
472 * Unique identifier of the trail from source_peer to new_successor,
473 * NOT including the endpoints.
475 struct GNUNET_HashCode trail_id;
477 /* List of peers in trail from source_peer to new_successor,
478 * NOT including the endpoints.
479 * struct GNUNET_PeerIdentity trail[]
484 * P2P Trail Compression Message.
486 struct PeerTrailCompressionMessage
489 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION
491 struct GNUNET_MessageHeader header;
494 * Source peer of this trail.
496 struct GNUNET_PeerIdentity source_peer;
499 * Trail from source_peer to destination_peer compressed such that
500 * new_first_friend is the first hop in the trail from source to
503 struct GNUNET_PeerIdentity new_first_friend;
506 * Unique identifier of trail.
508 struct GNUNET_HashCode trail_id;
513 * P2P Trail Tear Down message.
515 struct PeerTrailTearDownMessage
518 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
520 struct GNUNET_MessageHeader header;
523 * Unique identifier of the trail.
525 struct GNUNET_HashCode trail_id;
528 * Direction of trail.
530 uint32_t trail_direction;
535 * P2P Trail Rejection Message.
537 struct PeerTrailRejectionMessage
540 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
542 struct GNUNET_MessageHeader header;
545 * Peer which wants to set up the trail.
547 struct GNUNET_PeerIdentity source_peer;
550 * Peer which sent trail rejection message as it it congested.
552 struct GNUNET_PeerIdentity congested_peer;
555 * Peer identity closest to this value will be finger of
558 uint64_t ultimate_destination_finger_value;
561 * Is source_peer trying to setup the trail to its predecessor or finger.
563 uint32_t is_predecessor;
566 * Identifier for the trail that source peer is trying to setup.
568 struct GNUNET_HashCode trail_id;
571 * Relative time for which congested_peer will remain congested.
573 struct GNUNET_TIME_Relative congestion_time;
575 /* Trail_list from source_peer to peer which sent the message for trail setup
576 * to congested peer. This trail does NOT include source_peer.
577 struct GNUNET_PeerIdnetity trail[]*/
581 * P2P Add Trail Message.
583 struct PeerAddTrailMessage
586 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
588 struct GNUNET_MessageHeader header;
591 * Source of the routing trail.
593 struct GNUNET_PeerIdentity source_peer;
596 * Destination of the routing trail.
598 struct GNUNET_PeerIdentity destination_peer;
601 * Unique identifier of the trail from source_peer to destination_peer,
602 * NOT including the endpoints.
604 struct GNUNET_HashCode trail_id;
606 /* Trail from source peer to destination peer, NOT including them.
607 * struct GNUNET_PeerIdentity trail[]
611 GNUNET_NETWORK_STRUCT_END
614 * Linked list of messages to send to a particular other peer.
616 struct P2PPendingMessage
619 * Pointer to next item in the list
621 struct P2PPendingMessage *next;
624 * Pointer to previous item in the list
626 struct P2PPendingMessage *prev;
629 * Message importance level. FIXME: used? useful?
631 unsigned int importance;
634 * When does this message time out?
636 struct GNUNET_TIME_Absolute timeout;
639 * Actual message to be sent, allocated at the end of the struct:
640 * // msg = (cast) &pm[1];
641 * // memcpy (&pm[1], data, len);
643 const struct GNUNET_MessageHeader *msg;
648 * Entry in friend_peermap.
655 struct GNUNET_PeerIdentity id;
658 * Number of trails for which this friend is the first hop or if the friend
661 unsigned int trails_count;
664 * Count of outstanding messages for this friend.
666 unsigned int pending_count;
669 * In case not 0, then amount of time for which this friend is congested.
671 struct GNUNET_TIME_Absolute congestion_timestamp;
674 * Head of pending messages to be sent to this friend.
676 struct P2PPendingMessage *head;
679 * Tail of pending messages to be sent to this friend.
681 struct P2PPendingMessage *tail;
684 * Core handle for sending messages to this friend.
686 struct GNUNET_CORE_TransmitHandle *th;
691 * An individual element of the trail to reach to a finger.
696 * Pointer to next item in the list
698 struct Trail_Element *next;
701 * Pointer to prev item in the list
703 struct Trail_Element *prev;
706 * An element in this trail.
708 struct GNUNET_PeerIdentity peer;
712 * FIXME: removed first_friend_trails_count, need to write a function
713 * to calculate each time we need it. Else, keep a pointer to first
714 * friend of in the trail.
715 * Information about an individual trail.
722 struct Trail_Element *trail_head;
727 struct Trail_Element *trail_tail;
730 * Unique identifier of this trail.
732 struct GNUNET_HashCode trail_id;
735 * Length of trail pointed
737 unsigned int trail_length;
740 * Is there a valid trail entry.
742 unsigned int is_present;
746 * An entry in finger_table
753 struct GNUNET_PeerIdentity finger_identity;
756 * Is any finger stored at this finger index.
758 unsigned int is_present;
761 * Index in finger peer map
763 uint32_t finger_table_index;
766 * Number of trails setup so far for this finger.
767 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
769 uint32_t trails_count;
772 * Array of trails to reach to this finger.
774 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
779 * Data structure to keep track of closest peer seen so far in find_successor()
784 * Destination finger value.
786 uint64_t destination_finger_value;
789 * Is finger_value a predecessor or any other finger.
791 unsigned int is_predecessor;
794 * Trail id to reach to peer.
795 * In case peer is my identity or friend, it is set to NULL.
797 struct GNUNET_HashCode trail_id;
800 * Next destination. In case of friend and my_identity , it is same as next_hop
801 * In case of finger it is finger identity.
803 struct GNUNET_PeerIdentity best_known_destination;
806 * In case best_known_destination is a finger, then first friend in the trail
807 * to reach to it. In other case, same as best_known_destination.
809 struct GNUNET_PeerIdentity next_hop;
814 * Data structure to store the trail chosen to reach to finger.
816 struct Selected_Finger_Trail
819 * First friend in the trail to reach finger.
821 struct FriendInfo friend;
824 * Identifier of this trail.
826 struct GNUNET_HashCode trail_id;
829 * Total number of peers in this trail.
831 unsigned int trail_length;
835 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
836 * get our first friend.
838 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
841 * Identity of this peer.
843 static struct GNUNET_PeerIdentity my_identity;
846 * Peer map of all the friends of a peer
848 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
851 * Array of all the fingers.
853 static struct FingerInfo finger_table [MAX_FINGERS];
858 static struct GNUNET_CORE_Handle *core_api;
861 * The current finger index that we have want to find trail to. We start the
862 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
863 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
864 * we reset this index to 0.
866 static unsigned int current_search_finger_index;
870 * Called when core is ready to send a message we asked for
871 * out to the destination.
873 * @param cls the 'struct FriendInfo' of the target friend
874 * @param size number of bytes available in buf
875 * @param buf where the callee should write the message
876 * @return number of bytes written to buf
879 core_transmit_notify (void *cls, size_t size, void *buf)
881 struct FriendInfo *peer = cls;
883 struct P2PPendingMessage *pending;
888 while ((NULL != (pending = peer->head)) &&
889 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
891 peer->pending_count--;
892 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
893 GNUNET_free (pending);
897 /* no messages pending */
903 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
904 GNUNET_CORE_PRIO_BEST_EFFORT,
905 GNUNET_TIME_absolute_get_remaining
906 (pending->timeout), &peer->id,
907 ntohs (pending->msg->size),
908 &core_transmit_notify, peer);
909 GNUNET_break (NULL != peer->th);
913 while ((NULL != (pending = peer->head)) &&
914 (size - off >= (msize = ntohs (pending->msg->size))))
916 /*GNUNET_STATISTICS_update (GDS_stats,
918 ("# Bytes transmitted to other peers"), msize,
920 memcpy (&cbuf[off], pending->msg, msize);
922 peer->pending_count--;
923 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
924 GNUNET_free (pending);
926 if (peer->head != NULL)
929 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
930 GNUNET_CORE_PRIO_BEST_EFFORT,
931 GNUNET_TIME_absolute_get_remaining
932 (pending->timeout), &peer->id, msize,
933 &core_transmit_notify, peer);
934 GNUNET_break (NULL != peer->th);
941 * Transmit all messages in the friend's message queue.
943 * @param peer message queue to process
946 process_friend_queue (struct FriendInfo *peer)
948 struct P2PPendingMessage *pending;
950 if (NULL == (pending = peer->head))
952 if (NULL != peer->th)
955 GNUNET_STATISTICS_update (GDS_stats,
957 ("# Bytes of bandwidth requested from core"),
958 ntohs (pending->msg->size), GNUNET_NO);
961 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
963 GNUNET_TIME_absolute_get_remaining
964 (pending->timeout), &peer->id,
965 ntohs (pending->msg->size),
966 &core_transmit_notify, peer);
967 GNUNET_break (NULL != peer->th);
971 * Construct a trail setup message and forward it to target_friend
972 * @param source_peer Peer which wants to setup the trail
973 * @param ultimate_destination_finger_value Peer identity closest to this value
974 * will be finger to @a source_peer
975 * @param best_known_destination Best known destination (could be finger or friend)
976 * which should get this message. In case it is
977 * friend, then it is same as target_friend
978 * @param target_friend Friend to which message is forwarded now.
979 * @param trail_length Total number of peers in trail setup so far.
980 * @param trail_peer_list Trail setup so far
981 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
982 * @param trail_id Unique identifier for the trail we are trying to setup.
983 * @param intermediate_trail_id Trail id of intermediate trail to reach to
984 * best_known_destination when its a finger. If not
985 * used then set to 0.
988 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
989 uint64_t ultimate_destination_finger_value,
990 struct GNUNET_PeerIdentity best_known_destination,
991 struct FriendInfo *target_friend,
992 unsigned int trail_length,
993 const struct GNUNET_PeerIdentity *trail_peer_list,
994 unsigned int is_predecessor,
995 struct GNUNET_HashCode trail_id,
996 struct GNUNET_HashCode intermediate_trail_id)
998 struct P2PPendingMessage *pending;
999 struct PeerTrailSetupMessage *tsm;
1000 struct GNUNET_PeerIdentity *peer_list;
1003 msize = sizeof (struct PeerTrailSetupMessage) +
1004 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1006 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1012 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1014 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1018 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1019 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1020 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1021 pending->msg = &tsm->header;
1022 tsm->header.size = htons (msize);
1023 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1024 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1025 tsm->source_peer = source_peer;
1026 tsm->best_known_destination = best_known_destination;
1027 tsm->is_predecessor = htonl (is_predecessor);
1028 tsm->trail_id = trail_id;
1029 tsm->intermediate_trail_id = intermediate_trail_id;
1031 if (trail_length > 0)
1033 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1034 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1037 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1038 target_friend->pending_count++;
1039 process_friend_queue (target_friend);
1044 * Construct a trail setup result message and forward it to target friend.
1045 * @param querying_peer Peer which sent the trail setup request and should get
1047 * @param Finger Peer to which the trail has been setup to.
1048 * @param target_friend Friend to which this message should be forwarded.
1049 * @param trail_length Numbers of peers in the trail.
1050 * @param trail_peer_list Peers which are part of the trail from
1051 * querying_peer to Finger, NOT including them.
1052 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1053 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1055 * @param trail_id Unique identifier of the trail.
1058 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1059 struct GNUNET_PeerIdentity finger,
1060 struct FriendInfo *target_friend,
1061 unsigned int trail_length,
1062 const struct GNUNET_PeerIdentity *trail_peer_list,
1063 unsigned int is_predecessor,
1064 uint64_t ultimate_destination_finger_value,
1065 struct GNUNET_HashCode trail_id)
1067 struct P2PPendingMessage *pending;
1068 struct PeerTrailSetupResultMessage *tsrm;
1069 struct GNUNET_PeerIdentity *peer_list;
1072 msize = sizeof (struct PeerTrailSetupResultMessage) +
1073 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1075 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1081 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1083 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1087 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1088 pending->importance = 0;
1089 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1090 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1091 pending->msg = &tsrm->header;
1092 tsrm->header.size = htons (msize);
1093 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1094 tsrm->querying_peer = querying_peer;
1095 tsrm->finger_identity = finger;
1096 tsrm->is_predecessor = htonl (is_predecessor);
1097 tsrm->trail_id = trail_id;
1098 tsrm->ulitmate_destination_finger_value =
1099 GNUNET_htonll (ultimate_destination_finger_value);
1100 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1101 if (trail_length > 0)
1103 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1105 /* Send the message to chosen friend. */
1106 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1107 target_friend->pending_count++;
1108 process_friend_queue (target_friend);
1113 * Send trail rejection message to target friend
1114 * @param source_peer Peer which is trying to setup the trail.
1115 * @param ultimate_destination_finger_value Peer closest to this value will be
1116 * @a source_peer's finger
1117 * @param congested_peer Peer which sent this message as it is congested.
1118 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1119 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1120 * by congested_peer. This does NOT include @a source_peer
1121 * and congested_peer.
1122 * @param trail_length Total number of peers in trail_peer_list, NOT including
1123 * @a source_peer and @a congested_peer
1124 * @param trail_id Unique identifier of this trail.
1125 * @param congestion_timeout Duration given by congested peer as an estimate of
1126 * how long it may remain congested.
1129 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1130 uint64_t ultimate_destination_finger_value,
1131 struct GNUNET_PeerIdentity congested_peer,
1132 unsigned int is_predecessor,
1133 const struct GNUNET_PeerIdentity *trail_peer_list,
1134 unsigned int trail_length,
1135 struct GNUNET_HashCode trail_id,
1136 struct FriendInfo *target_friend,
1137 const struct GNUNET_TIME_Relative congestion_timeout)
1139 struct PeerTrailRejectionMessage *trm;
1140 struct P2PPendingMessage *pending;
1141 struct GNUNET_PeerIdentity *peer_list;
1144 msize = sizeof (struct PeerTrailRejectionMessage) +
1145 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1147 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1153 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1155 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1159 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1160 pending->importance = 0;
1161 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1162 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1163 pending->msg = &trm->header;
1164 trm->header.size = htons (msize);
1165 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1166 trm->source_peer = source_peer;
1167 trm->congested_peer = congested_peer;
1168 trm->congestion_time = congestion_timeout;
1169 trm->is_predecessor = htonl (is_predecessor);
1170 trm->trail_id = trail_id;
1171 trm->ultimate_destination_finger_value =
1172 GNUNET_htonll (ultimate_destination_finger_value);
1174 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1175 if (trail_length > 0)
1177 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1180 /* Send the message to chosen friend. */
1181 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1182 target_friend->pending_count++;
1183 process_friend_queue (target_friend);
1188 * Construct a verify successor message and forward it to target_friend.
1189 * @param source_peer Peer which wants to verify its successor.
1190 * @param successor Peer which is @a source_peer's current successor.
1191 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1192 * NOT including them.
1193 * @param trail List of peers which are part of trail to reach from @a source_peer
1194 * to @a successor, NOT including them.
1195 * @param trail_length Total number of peers in @a trail.
1196 * @param target_friend Next friend to get this message.
1199 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1200 struct GNUNET_PeerIdentity successor,
1201 struct GNUNET_HashCode trail_id,
1202 struct GNUNET_PeerIdentity *trail,
1203 unsigned int trail_length,
1204 struct FriendInfo *target_friend)
1206 struct PeerVerifySuccessorMessage *vsm;
1207 struct P2PPendingMessage *pending;
1208 struct GNUNET_PeerIdentity *peer_list;
1211 msize = sizeof (struct PeerVerifySuccessorMessage) +
1212 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1213 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1219 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1221 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1225 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1226 pending->importance = 0; /* FIXME */
1227 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1228 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1229 pending->msg = &vsm->header;
1230 vsm->header.size = htons (msize);
1231 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1232 vsm->source_peer = source_peer;
1233 vsm->successor = successor;
1234 vsm->trail_id = trail_id;
1236 if (trail_length != 0)
1238 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1239 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1242 /* Send the message to chosen friend. */
1243 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1244 target_friend->pending_count++;
1245 process_friend_queue (target_friend);
1250 * FIXME: In every function we pass target friend except for this one.
1251 * so, either change everything or this one. also, should se just store
1252 * the pointer to friend in routing table rather than gnunet_peeridentity.
1253 * if yes then we should keep friend info in.h andmake lot of changes.
1254 * Construct a trail teardown message and forward it to target friend.
1255 * @param trail_id Unique identifier of the trail.
1256 * @param trail_direction Direction of trail.
1257 * @param target_friend Friend to get this message.
1260 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1261 unsigned int trail_direction,
1262 struct GNUNET_PeerIdentity peer)
1264 struct PeerTrailTearDownMessage *ttdm;
1265 struct P2PPendingMessage *pending;
1266 struct FriendInfo *target_friend;
1269 msize = sizeof (struct PeerTrailTearDownMessage);
1271 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1277 /*FIXME:In what case friend can be null. ?*/
1278 if (NULL == (target_friend =
1279 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1282 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1284 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1288 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1289 pending->importance = 0; /* FIXME */
1290 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1291 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1292 pending->msg = &ttdm->header;
1293 ttdm->header.size = htons (msize);
1294 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1295 ttdm->trail_id = trail_id;
1296 ttdm->trail_direction = htonl (trail_direction);
1298 /* Send the message to chosen friend. */
1299 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1300 target_friend->pending_count++;
1301 process_friend_queue (target_friend);
1306 * Construct a verify successor result message and send it to target_friend
1307 * @param querying_peer Peer which sent the verify successor message.
1308 * @param source_successor Current_successor of @a querying_peer.
1309 * @param current_predecessor Current predecessor of @a successor. Could be same
1310 * or different from @a querying_peer.
1311 * @param trail_id Unique identifier of the trail from @a querying_peer to
1312 * @a successor, NOT including them.
1313 * @param trail List of peers which are part of trail from @a querying_peer to
1314 * @a successor, NOT including them.
1315 * @param trail_length Total number of peers in @a trail
1316 * @param trail_direction Direction in which we are sending the message. In this
1317 * case we are sending result from @a successor to @a querying_peer.
1318 * @param target_friend Next friend to get this message.
1321 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1322 struct GNUNET_PeerIdentity current_successor,
1323 struct GNUNET_PeerIdentity probable_successor,
1324 struct GNUNET_HashCode trail_id,
1325 const struct GNUNET_PeerIdentity *trail,
1326 unsigned int trail_length,
1327 enum GDS_ROUTING_trail_direction trail_direction,
1328 struct FriendInfo *target_friend)
1330 struct PeerVerifySuccessorResultMessage *vsmr;
1331 struct P2PPendingMessage *pending;
1332 struct GNUNET_PeerIdentity *peer_list;
1335 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1336 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1338 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1344 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1346 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1350 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1351 pending->importance = 0; /* FIXME */
1352 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1353 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1354 pending->msg = &vsmr->header;
1355 vsmr->header.size = htons (msize);
1356 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1357 vsmr->querying_peer = querying_peer;
1358 vsmr->current_successor = current_successor;
1359 vsmr->probable_successor = probable_successor;
1360 vsmr->trail_direction = htonl (trail_direction);
1361 vsmr->trail_id = trail_id;
1363 if (trail_length > 0)
1365 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1366 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1369 /* Send the message to chosen friend. */
1370 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1371 target_friend->pending_count++;
1372 process_friend_queue (target_friend);
1377 * Construct a notify new successor message and send it to target_friend
1378 * @param source_peer Peer which wants to notify to its new successor that it
1379 * could be its predecessor.
1380 * @param successor New successor of @a source_peer
1381 * @param successor_trail List of peers in Trail to reach from
1382 * @a source_peer to @a new_successor, NOT including
1384 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1385 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1386 * @param target_friend Next friend to get this message.
1389 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1390 struct GNUNET_PeerIdentity successor,
1391 const struct GNUNET_PeerIdentity *successor_trail,
1392 unsigned int successor_trail_length,
1393 struct GNUNET_HashCode succesor_trail_id,
1394 struct FriendInfo *target_friend)
1396 struct PeerNotifyNewSuccessorMessage *nsm;
1397 struct P2PPendingMessage *pending;
1398 struct GNUNET_PeerIdentity *peer_list;
1401 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1402 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1404 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1410 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1412 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1416 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1417 pending->importance = 0; /* FIXME */
1418 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1419 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1420 pending->msg = &nsm->header;
1421 nsm->header.size = htons (msize);
1422 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1423 nsm->new_successor = successor;
1424 nsm->source_peer = source_peer;
1425 nsm->trail_id = succesor_trail_id;
1427 if (successor_trail_length > 0)
1429 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1430 memcpy (peer_list, successor_trail,
1431 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1434 /* Send the message to chosen friend. */
1435 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1436 target_friend->pending_count++;
1437 process_friend_queue (target_friend);
1442 * Construct an add_trail message and send it to target_friend
1443 * @param source_peer Source of the trail.
1444 * @param destination_peer Destination of the trail.
1445 * @param trail_id Unique identifier of the trail from
1446 * @a source_peer to @a destination_peer, NOT including the endpoints.
1447 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1448 * NOT including the endpoints.
1449 * @param trail_length Total number of peers in @a trail.
1450 * @param target_friend Next friend to get this message.
1453 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1454 struct GNUNET_PeerIdentity destination_peer,
1455 struct GNUNET_HashCode trail_id,
1456 const struct GNUNET_PeerIdentity *trail,
1457 unsigned int trail_length,
1458 struct FriendInfo *target_friend)
1460 struct PeerAddTrailMessage *adm;
1461 struct GNUNET_PeerIdentity *peer_list;
1462 struct P2PPendingMessage *pending;
1465 msize = sizeof (struct PeerAddTrailMessage) +
1466 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1468 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1474 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1476 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1480 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1481 pending->importance = 0; /* FIXME */
1482 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1483 adm = (struct PeerAddTrailMessage *) &pending[1];
1484 pending->msg = &adm->header;
1485 adm->header.size = htons (msize);
1486 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1487 adm->source_peer = source_peer;
1488 adm->destination_peer = destination_peer;
1489 adm->trail_id = trail_id;
1491 if (trail_length > 0)
1493 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1494 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1496 /* Send the message to chosen friend. */
1497 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1498 target_friend->pending_count++;
1499 process_friend_queue (target_friend);
1505 * Construct a trail compression message and send it to target_friend.
1506 * @param source_peer Source of the trail.
1507 * @param trail_id Unique identifier of trail.
1508 * @param first_friend First hop in compressed trail to reach from source to finger
1509 * @param target_friend Next friend to get this message.
1512 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1513 struct GNUNET_HashCode trail_id,
1514 struct GNUNET_PeerIdentity first_friend,
1515 struct FriendInfo *target_friend)
1517 struct P2PPendingMessage *pending;
1518 struct PeerTrailCompressionMessage *tcm;
1521 msize = sizeof (struct PeerTrailCompressionMessage);
1523 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1529 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1531 GNUNET_STATISTICS_update (GDS_stats,
1532 gettext_noop ("# P2P messages dropped due to full queue"),
1536 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1537 pending->importance = 0; /* FIXME */
1538 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1539 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1540 pending->msg = &tcm->header;
1541 tcm->header.size = htons (msize);
1542 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1543 tcm->source_peer = source_peer;
1544 tcm->new_first_friend = first_friend;
1545 tcm->trail_id = trail_id;
1547 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1548 target_friend->pending_count++;
1549 process_friend_queue (target_friend);
1555 * Search my location in trail. In case I am present more than once in the
1556 * trail (can happen during trail setup), then return my lowest index.
1557 * @param trail List of peers
1558 * @return my_index if found
1559 * -1 if no entry found.
1562 search_my_index (const struct GNUNET_PeerIdentity *trail,
1566 int lowest_index = -1;
1568 for (i = 0; i < trail_length; i++)
1570 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1574 return lowest_index;
1579 * Check if the friend is congested or have reached maximum number of trails
1580 * it can be part of of.
1581 * @param friend Friend to be checked.
1582 * @return #GNUNET_YES if friend is not congested or have not crossed threshold.
1583 * #GNUNET_NO if friend is either congested or have crossed threshold
1586 is_friend_congested (struct FriendInfo *friend)
1588 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1589 ((0 == GNUNET_TIME_absolute_get_remaining
1590 (friend->congestion_timestamp).rel_value_us)))
1598 * FIXME; not handling the wrap around logic correctly.
1599 * Select closest finger to value.
1600 * @param peer1 First peer
1601 * @param peer2 Second peer
1602 * @param value Value to be compare
1603 * @return Closest peer
1605 static struct GNUNET_PeerIdentity *
1606 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1607 struct GNUNET_PeerIdentity *peer2,
1610 uint64_t peer1_value;
1611 uint64_t peer2_value;
1613 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1614 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1615 peer1_value = GNUNET_ntohll (peer1_value);
1616 peer2_value = GNUNET_ntohll (peer2_value);
1618 if (peer1_value == value)
1623 if (peer2_value == value)
1628 if (peer2_value < peer1_value)
1630 if ((peer2_value < value) && (value < peer1_value))
1634 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1635 ((0 < value) && (value < peer2_value)))
1641 if (peer1_value < peer2_value)
1643 if ((peer1_value < value) && (value < peer2_value))
1647 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1648 ((0 < value) && (value < peer1_value)))
1658 * Select closest predecessor to value.
1659 * @param peer1 First peer
1660 * @param peer2 Second peer
1661 * @param value Value to be compare
1662 * @return Peer which precedes value in the network.
1664 static struct GNUNET_PeerIdentity *
1665 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1666 struct GNUNET_PeerIdentity *peer2,
1669 uint64_t peer1_value;
1670 uint64_t peer2_value;
1672 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1673 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1674 peer1_value = GNUNET_ntohll (peer1_value);
1675 peer2_value = GNUNET_ntohll (peer2_value);
1677 if (peer1_value == value)
1680 if (peer2_value == value)
1683 if (peer1_value < peer2_value)
1685 if ((peer1_value < value) && (value < peer2_value))
1687 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1688 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1692 if (peer2_value < peer1_value)
1694 if ((peer2_value < value) && (value < peer1_value))
1696 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1697 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1705 * This is a test function to print all the entries of friend table.
1708 test_friend_peermap_print ()
1710 struct FriendInfo *friend;
1711 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1712 struct GNUNET_PeerIdentity print_peer;
1713 struct GNUNET_PeerIdentity key_ret;
1715 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP"));
1716 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1718 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1720 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1722 (const void **)&friend))
1724 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1725 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1726 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1733 * This is a test function, to print all the entries of finger table.
1736 test_finger_table_print()
1738 struct FingerInfo *finger;
1739 struct GNUNET_PeerIdentity print_peer;
1740 //struct Trail *trail;
1745 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE"));
1746 for (i = 0; i < MAX_FINGERS; i++)
1748 finger = &finger_table[i];
1750 if (GNUNET_NO == finger->is_present)
1753 print_peer = finger->finger_identity;
1754 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1755 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1758 for (j = 0; j < finger->trails_count; j++)
1760 trail = &finger->trail_list[j];
1761 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1762 struct Trail_Element *element;
1763 element = trail->trail_head;
1764 for (k = 0; k < trail->trail_length; k++)
1766 print_peer = element->peer;
1767 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1768 element = element->next;
1777 * Select the closest peer among two peers (which should not be same)
1778 * with respect to value and finger_table_index
1779 * NOTE: peer1 != peer2
1780 * @param peer1 First peer
1781 * @param peer2 Second peer
1782 * @param value Value relative to which we find the closest
1783 * @param is_predecessor Is value a predecessor or any other finger.
1784 * @return Closest peer among two peers.
1786 static struct GNUNET_PeerIdentity *
1787 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1788 struct GNUNET_PeerIdentity *peer2,
1790 unsigned int is_predecessor)
1792 struct GNUNET_PeerIdentity *closest_peer;
1794 if (1 == is_predecessor)
1796 closest_peer = select_closest_predecessor (peer1, peer2, value);
1800 closest_peer = select_closest_finger (peer1, peer2, value);
1802 return closest_peer;
1807 * Iterate over the list of all the trails of a finger. In case the first
1808 * friend to reach the finger has reached trail threshold or is congested,
1809 * then don't select it. In case there multiple available good trails to reach
1810 * to Finger, choose the one with shortest trail length.
1811 * Note: We use length as parameter. But we can use any other suitable parameter
1813 * @param finger Finger
1814 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1815 * and trail length. NULL in case none of the trails are free.
1817 static struct Selected_Finger_Trail *
1818 select_finger_trail (struct FingerInfo *finger)
1820 struct FriendInfo *friend;
1821 struct Trail *iterator;
1822 struct Selected_Finger_Trail *finger_trail;
1824 unsigned int flag = 0;
1827 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1829 /* It can never happen that we have a finger (which is not a friend or my identity),
1830 and we don't have a trail to reach to it. */
1831 GNUNET_assert (finger->trails_count > 0);
1833 for (i = 0; i < finger->trails_count; i++)
1835 iterator = &finger->trail_list[i];
1837 /* No trail stored at this index. */
1838 if (GNUNET_NO == iterator->is_present)
1843 GNUNET_assert (NULL !=
1845 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1846 &iterator->trail_head->peer)));
1848 /* First friend to reach trail is not free. */
1849 if (GNUNET_YES == is_friend_congested (friend))
1854 /* This is the first time we enter the loop. Set finger trail length to
1855 * trail length of this trail. */
1859 finger_trail->trail_length = iterator->trail_length;
1860 finger_trail->friend = *friend;
1861 finger_trail->trail_id = iterator->trail_id;
1862 //memcmp (finger_trail->trail_id, &iterator->trail_id, sizeof (struct GNUNET_HashCode));
1864 else if (finger_trail->trail_length > iterator->trail_length)
1866 /* Check if the trail length of this trail is least seen so far. If yes then
1867 set finger_trail to this trail.*/
1868 finger_trail->friend = *friend;
1869 finger_trail->trail_id = iterator->trail_id;
1870 //memcmp (finger_trail->trail_id, &iterator->trail_id, sizeof (struct GNUNET_HashCode));
1871 finger_trail->trail_length = iterator->trail_length;
1875 /* All the first friend in all the trails to reach to finger are either
1876 congested or have crossed trail threshold. */
1877 if (j == finger->trails_count)
1880 return finger_trail;
1885 * Compare FINGER entry with current successor. If finger's first friend of all
1886 * its trail is not congested and has not crossed trail threshold, then check
1887 * if finger peer identity is closer to final_destination_finger_value than
1888 * current_successor. If yes then update current_successor.
1889 * @param current_successor[in/out]
1893 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1895 struct FingerInfo *finger;
1896 struct GNUNET_PeerIdentity *closest_peer;
1897 struct Selected_Finger_Trail *finger_trail;
1900 /* Iterate over finger table. */
1901 for (i = 0; i < MAX_FINGERS; i++)
1903 finger = &finger_table[i];
1905 /* No valid entry at this index, go to next element.*/
1906 if (GNUNET_NO == finger->is_present)
1909 /* If my identity is same as current closest peer then don't consider me*/
1911 GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1912 ¤t_closest_peer->best_known_destination))
1915 /* If I am my own finger, then ignore this finger. */
1916 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1920 /* If finger is a friend, then do nothing. As we have already checked
1921 * for each friend in compare_friend_and_current_successor(). */
1922 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1923 &finger->finger_identity)))
1927 /* We have a finger which not a friend, not my identity */
1928 /* Choose one of the trail to reach to finger. */
1929 finger_trail = select_finger_trail (finger);
1931 /* In case no trail found, ignore this finger. */
1932 if (NULL == finger_trail)
1935 closest_peer = select_closest_peer (&finger->finger_identity,
1936 ¤t_closest_peer->best_known_destination,
1937 current_closest_peer->destination_finger_value,
1938 current_closest_peer->is_predecessor);
1940 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1943 current_closest_peer->best_known_destination = finger->finger_identity;
1944 current_closest_peer->next_hop = finger_trail->friend.id;
1945 current_closest_peer->trail_id = finger_trail->trail_id;
1954 * Compare friend entry with current successor.
1955 * If friend identity and current_successor is same, then do nothing.
1956 * If friend is not congested and has not crossed trail threshold, then check
1957 * if friend peer identity is closer to final_destination_finger_value than
1958 * current_successor. If yes then update current_successor.
1959 * @param cls closure
1960 * @param key current public key
1961 * @param value struct Closest_Peer
1962 * @return #GNUNET_YES if we should continue to iterate,
1963 * #GNUNET_NO if not.
1966 compare_friend_and_current_closest_peer (void *cls,
1967 const struct GNUNET_PeerIdentity *key,
1970 struct FriendInfo *friend = value;
1971 struct Closest_Peer *current_closest_peer = cls;
1972 struct GNUNET_PeerIdentity *closest_peer;
1974 /* If friend is either congested or has crossed threshold, then don't consider
1976 if (GNUNET_YES == is_friend_congested (friend))
1979 /* If current_closest_peer and friend identity are same, then do nothing.*/
1981 GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
1982 ¤t_closest_peer->best_known_destination))
1985 closest_peer = select_closest_peer (&friend->id,
1986 ¤t_closest_peer->best_known_destination,
1987 current_closest_peer->destination_finger_value,
1988 current_closest_peer->is_predecessor);
1990 /* Is friend the closest successor? */
1991 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id, closest_peer))
1993 current_closest_peer->best_known_destination = friend->id;
1994 current_closest_peer->next_hop = friend->id;
2002 * Initialize current_successor to my_identity.
2003 * @param my_identity My peer identity
2004 * @return current_successor
2006 static struct Closest_Peer
2007 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2008 uint64_t destination_finger_value,
2009 unsigned int is_predecessor)
2011 struct Closest_Peer current_closest_peer;
2013 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2014 current_closest_peer.destination_finger_value = destination_finger_value;
2015 current_closest_peer.is_predecessor = is_predecessor;
2016 current_closest_peer.next_hop = my_identity;
2017 current_closest_peer.best_known_destination = my_identity;
2019 return current_closest_peer;
2024 * Find the successor for destination_finger_value among my_identity, all my
2025 * friend and all my fingers. Don't consider friends or fingers which are either
2026 * congested or have crossed the threshold.
2027 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2029 * @param destination_finger_value Peer closest to this value will be the next successor.
2030 * @param is_predecessor Are we looking for predecessor or finger?
2033 static struct Closest_Peer
2034 find_successor (uint64_t destination_finger_value,
2035 unsigned int is_predecessor)
2037 struct Closest_Peer current_closest_peer;
2039 /* Initialize current_successor to my_identity. */
2040 current_closest_peer = init_current_successor (my_identity,
2041 destination_finger_value,
2044 /* Compare each friend entry with current_successor and update current_successor
2045 * with friend if its closest. */
2048 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2049 &compare_friend_and_current_closest_peer,
2050 ¤t_closest_peer));
2052 /* Compare each finger entry with current_successor and update current_successor
2053 * with finger if its closest. */
2054 compare_finger_and_current_successor (¤t_closest_peer);
2056 return current_closest_peer;
2061 * Construct a Put message and send it to target_peer.
2062 * @param key Key for the content
2063 * @param block_type Type of the block
2064 * @param options Routing options
2065 * @param desired_replication_level Desired replication count
2066 * @param best_known_dest Peer to which this message should reach eventually,
2067 * as it is best known destination to me.
2068 * @param intermediate_trail_id Trail id in case
2069 * @param target_peer Peer to which this message will be forwarded.
2070 * @param hop_count Number of hops traversed so far.
2071 * @param put_path_length Total number of peers in @a put_path
2072 * @param put_path Number of peers traversed so far
2073 * @param expiration_time When does the content expire
2074 * @param data Content to store
2075 * @param data_size Size of content @a data in bytes
2078 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2079 enum GNUNET_BLOCK_Type block_type,
2080 enum GNUNET_DHT_RouteOption options,
2081 uint32_t desired_replication_level,
2082 struct GNUNET_PeerIdentity best_known_dest,
2083 struct GNUNET_HashCode intermediate_trail_id,
2084 struct GNUNET_PeerIdentity *target_peer,
2086 uint32_t put_path_length,
2087 struct GNUNET_PeerIdentity *put_path,
2088 struct GNUNET_TIME_Absolute expiration_time,
2089 const void *data, size_t data_size)
2091 struct PeerPutMessage *ppm;
2092 struct P2PPendingMessage *pending;
2093 struct FriendInfo *target_friend;
2094 struct GNUNET_PeerIdentity *pp;
2095 struct GNUNET_PeerIdentity next_hop;
2099 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2100 sizeof (struct PeerPutMessage);
2102 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2104 put_path_length = 0;
2105 msize = data_size + sizeof (struct PeerPutMessage);
2108 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2114 /* This is the first call made from clients file. So, we should search for the
2116 if (NULL == target_peer)
2119 struct Closest_Peer successor;
2121 memcpy (&key_value, key, sizeof (uint64_t));
2122 key_value = GNUNET_ntohll (key_value);
2124 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2125 best_known_dest = successor.best_known_destination;
2126 next_hop = successor.next_hop;
2127 intermediate_trail_id = successor.trail_id;
2129 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2131 /* I am the destination but we have already done datacache_put in client file. */
2135 GNUNET_assert (NULL !=
2137 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2141 GNUNET_assert (NULL !=
2143 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2146 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2147 pending->timeout = expiration_time;
2148 ppm = (struct PeerPutMessage *) &pending[1];
2149 pending->msg = &ppm->header;
2150 ppm->header.size = htons (msize);
2151 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2152 ppm->options = htonl (options);
2153 ppm->block_type = htonl (block_type);
2154 ppm->hop_count = htonl (hop_count + 1);
2155 ppm->desired_replication_level = htonl (desired_replication_level);
2156 ppm->put_path_length = htonl (put_path_length);
2157 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2158 ppm->best_known_destination = best_known_dest;
2161 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2162 if (put_path_length != 0)
2164 memcpy (pp, put_path,
2165 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2167 memcpy (&pp[put_path_length], data, data_size);
2169 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2170 target_friend->pending_count++;
2171 process_friend_queue (target_friend);
2176 * Construct a Get message and send it to target_peer.
2177 * @param key Key for the content
2178 * @param block_type Type of the block
2179 * @param options Routing options
2180 * @param desired_replication_level Desired replication count
2181 * @param best_known_dest Peer which should get this message. Same as target peer
2182 * if best_known_dest is a friend else its a finger.
2183 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2184 * in case it is a finger else set to 0.
2185 * @param target_peer Peer to which this message will be forwarded.
2186 * @param hop_count Number of hops traversed so far.
2187 * @param data Content to store
2188 * @param data_size Size of content @a data in bytes
2189 * @param get_path_length Total number of peers in @a get_path
2190 * @param get_path Number of peers traversed so far
2193 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2194 enum GNUNET_BLOCK_Type block_type,
2195 enum GNUNET_DHT_RouteOption options,
2196 uint32_t desired_replication_level,
2197 struct GNUNET_PeerIdentity best_known_dest,
2198 struct GNUNET_HashCode intermediate_trail_id,
2199 struct GNUNET_PeerIdentity *target_peer,
2201 uint32_t get_path_length,
2202 struct GNUNET_PeerIdentity *get_path)
2204 struct PeerGetMessage *pgm;
2205 struct P2PPendingMessage *pending;
2206 struct FriendInfo *target_friend;
2207 struct GNUNET_PeerIdentity *gp;
2210 msize = sizeof (struct PeerGetMessage) +
2211 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2213 /* In this case we don't make get_path_length = 0, as we need get path to
2214 * return the message back to querying client. */
2215 if (msize > GNUNET_SERVER_MAX_MESSAGE_SIZE)
2221 /* This is the first time we got request from our own client file. */
2222 if (NULL == target_peer)
2225 struct Closest_Peer successor;
2227 memcpy (&key_value, key, sizeof (uint64_t));
2228 key_value = GNUNET_ntohll (key_value);
2229 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2231 best_known_dest = successor.best_known_destination;
2232 intermediate_trail_id = successor.trail_id;
2234 /* I am the destination. I have the data. */
2235 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2238 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2239 NULL, 0, 1, &my_identity, NULL,&my_identity);
2245 GNUNET_assert (NULL !=
2247 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2248 &successor.next_hop)));
2254 GNUNET_assert (NULL !=
2256 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); //FIXME: assertion fails.
2259 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2260 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2261 pending->importance = 0; /* FIXME */
2262 pgm = (struct PeerGetMessage *) &pending[1];
2263 pending->msg = &pgm->header;
2264 pgm->header.size = htons (msize);
2265 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2266 pgm->get_path_length = htonl (get_path_length);
2267 pgm->best_known_destination = best_known_dest;
2269 pgm->intermediate_trail_id = intermediate_trail_id;
2270 pgm->hop_count = htonl (hop_count + 1);
2271 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2273 if (get_path_length != 0)
2275 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2278 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2279 target_friend->pending_count++;
2280 process_friend_queue (target_friend);
2285 * Send the get result to requesting client.
2286 * @param key Key of the requested data.
2287 * @param type Block type
2288 * @param target_peer Next peer to forward the message to.
2289 * @param source_peer Peer which has the data for the key.
2290 * @param put_path_length Number of peers in @a put_path
2291 * @param put_path Path taken to put the data at its stored location.
2292 * @param get_path_length Number of peers in @a get_path
2293 * @param get_path Path taken to reach to the location of the key.
2294 * @param expiration When will this result expire?
2295 * @param data Payload to store
2296 * @param data_size Size of the @a data
2299 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2300 enum GNUNET_BLOCK_Type type,
2301 const struct GNUNET_PeerIdentity *target_peer,
2302 const struct GNUNET_PeerIdentity *source_peer,
2303 unsigned int put_path_length,
2304 const struct GNUNET_PeerIdentity *put_path,
2305 unsigned int get_path_length,
2306 const struct GNUNET_PeerIdentity *get_path,
2307 struct GNUNET_TIME_Absolute expiration,
2308 const void *data, size_t data_size)
2310 struct PeerGetResultMessage *get_result;
2311 struct GNUNET_PeerIdentity *paths;
2312 struct P2PPendingMessage *pending;
2313 struct FriendInfo *target_friend;
2314 int current_path_index;
2317 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2319 sizeof (struct PeerGetResultMessage);
2321 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2327 current_path_index = 0;
2328 if(get_path_length > 0)
2330 current_path_index = search_my_index(get_path, get_path_length);
2331 if (-1 == current_path_index)
2337 if (0 == current_path_index)
2339 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2340 get_path, put_path_length,
2341 put_path, type, data_size, data);
2345 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2346 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2347 pending->importance = 0;
2348 get_result = (struct PeerGetResultMessage *)&pending[1];
2349 pending->msg = &get_result->header;
2350 get_result->header.size = htons (msize);
2351 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2352 get_result->key = *key;
2353 get_result->querying_peer = *source_peer;
2354 get_result->expiration_time = expiration;
2355 get_result->get_path_length = htonl (get_path_length);
2356 get_result->put_path_length = htonl (put_path_length);
2357 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2358 memcpy (paths, put_path,
2359 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2360 memcpy (&paths[put_path_length], get_path,
2361 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2362 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2364 GNUNET_assert (NULL !=
2366 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2367 &get_path[current_path_index - 1])));
2368 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2369 target_friend->pending_count++;
2370 process_friend_queue (target_friend);
2375 * Randomly choose one of your friends (which is not congested and have not crossed
2376 * trail threshold) from the friends_peer map
2377 * @return Friend Randomly chosen friend.
2378 * NULL in case friend peermap is empty, or all the friends are either
2379 * congested or have crossed trail threshold.
2381 static struct FriendInfo *
2382 select_random_friend ()
2384 unsigned int current_size;
2387 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2388 struct GNUNET_PeerIdentity key_ret;
2389 struct FriendInfo *friend;
2391 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2394 if (0 == current_size)
2397 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2398 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2400 /* Iterate till you don't reach to index. */
2401 for (j = 0; j < index ; j++)
2402 GNUNET_assert (GNUNET_YES ==
2403 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2406 /* Reset the index in friend peermap to 0 as we reached to the end. */
2407 if (j == current_size)
2410 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2411 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2415 /* Get the friend stored at the index, j*/
2416 GNUNET_assert (GNUNET_YES ==
2417 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2419 (const void **)&friend));
2421 /* This friend is not congested and has not crossed trail threshold. */
2422 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2423 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2429 } while (j != index);
2431 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2437 * Compute 64 bit value of finger_identity corresponding to a finger index using
2440 * n.finger[i] = n + pow (2,i),
2442 * n.finger[i] = n - 1, where
2445 * n.finger[i] = 64 bit finger value
2446 * @param finger_index Index corresponding to which we calculate 64 bit value.
2447 * @return 64 bit value.
2450 compute_finger_identity_value (unsigned int finger_index)
2454 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2455 my_id64 = GNUNET_ntohll (my_id64);
2457 /* Are we looking for immediate predecessor? */
2458 if (PREDECESSOR_FINGER_ID == finger_index)
2459 return (my_id64 -1);
2461 return (my_id64 + (unsigned long) pow (2, finger_index));
2466 * Choose a random friend. Start looking for the trail to reach to
2467 * finger identity corresponding to current_search_finger_index through
2468 * this random friend.
2470 * @param cls closure for this task
2471 * @param tc the context under which the task is running
2474 send_find_finger_trail_message (void *cls,
2475 const struct GNUNET_SCHEDULER_TaskContext *tc)
2477 struct FriendInfo *target_friend;
2478 struct GNUNET_TIME_Relative next_send_time;
2479 struct GNUNET_HashCode trail_id;
2480 unsigned int is_predecessor;
2481 uint64_t finger_id_value;
2483 /* Schedule another send_find_finger_trail_message task. */
2484 next_send_time.rel_value_us =
2485 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
2486 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2487 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2488 find_finger_trail_task =
2489 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
2492 /* No space in my routing table. (Source and destination peers also store entries
2493 * in their routing table). */
2494 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2497 target_friend = select_random_friend ();
2498 if (NULL == target_friend)
2503 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2504 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2509 /* Generate a unique trail id for trail we are trying to setup. */
2510 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2511 &trail_id, sizeof (trail_id));
2512 struct GNUNET_HashCode new_intermediate_trail_id;
2513 memset(&new_intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2514 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2515 target_friend->id, target_friend, 0, NULL,
2516 is_predecessor, trail_id,
2517 new_intermediate_trail_id);
2522 * In case there are already maximum number of possible trails to reach to a
2523 * finger, then check if the new trail's length is lesser than any of the
2525 * If yes then replace that old trail by new trail.
2527 * Note: Here we are taking length as a parameter to choose the best possible
2528 * trail, but there could be other parameters also like:
2529 * 1. duration of existence of a trail - older the better.
2530 * 2. if the new trail is completely disjoint than the
2531 * other trails, then may be choosing it is better.
2533 * @param existing_finger
2534 * @param new_finger_trail
2535 * @param new_finger_trail_length
2536 * @param new_finger_trail_id
2539 select_and_replace_trail (struct FingerInfo *existing_finger,
2540 const struct GNUNET_PeerIdentity *new_trail,
2541 unsigned int new_trail_length,
2542 struct GNUNET_HashCode new_trail_id)
2544 struct Trail *trail_list_iterator;
2545 unsigned int largest_trail_length;
2546 unsigned int largest_trail_index;
2547 struct Trail_Element *trail_element;
2550 largest_trail_length = new_trail_length;
2551 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2553 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2555 for (i = 0; i < existing_finger->trails_count; i++)
2557 trail_list_iterator = &existing_finger->trail_list[i];
2558 if (trail_list_iterator->trail_length > largest_trail_length)
2560 largest_trail_length = trail_list_iterator->trail_length;
2561 largest_trail_index = i;
2565 /* New trail is not better than existing ones. Send trail teardown. */
2566 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2568 struct GNUNET_PeerIdentity next_hop;
2570 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2571 GDS_ROUTING_remove_trail (new_trail_id);
2572 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2573 GDS_ROUTING_SRC_TO_DEST,
2578 /* Send trail teardown message across the replaced trail. */
2579 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2580 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2581 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2582 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2583 GDS_ROUTING_SRC_TO_DEST,
2584 replace_trail->trail_head->peer);
2585 /* Free the trail. */
2586 while (NULL != (trail_element = replace_trail->trail_head))
2588 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2589 replace_trail->trail_tail, trail_element);
2590 GNUNET_free_non_null (trail_element);
2593 /* Add new trial at that location. */
2594 replace_trail->is_present = GNUNET_YES;
2595 replace_trail->trail_length = new_trail_length;
2596 replace_trail->trail_id = new_trail_id;
2597 //FIXME: Do we need to add pointers for head and tail.
2599 while (i < new_trail_length)
2601 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2602 element->peer = new_trail[i];
2604 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2605 replace_trail->trail_tail,
2612 * Check if the new trail to reach to finger is unique or do we already have
2613 * such a trail present for finger.
2614 * @param existing_finger Finger identity
2615 * @param new_trail New trail to reach @a existing_finger
2616 * @param trail_length Total number of peers in new_trail.
2617 * @return #GNUNET_YES if the new trail is unique
2618 * #GNUNET_NO if same trail is already present.
2621 is_new_trail_unique (struct FingerInfo *existing_finger,
2622 const struct GNUNET_PeerIdentity *new_trail,
2623 unsigned int trail_length)
2625 struct Trail *trail_list_iterator;
2626 struct Trail_Element *trail_element;
2629 int trail_unique = GNUNET_NO;
2631 GNUNET_assert (existing_finger->trails_count > 0);
2633 /* Iterate over list of trails. */
2634 for (i = 0; i < existing_finger->trails_count; i++)
2636 trail_list_iterator = &existing_finger->trail_list[i];
2637 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2639 /* New trail and existing trail length are not same. */
2640 if (trail_list_iterator->trail_length != trail_length)
2642 trail_unique = GNUNET_YES;
2646 trail_element = trail_list_iterator->trail_head;
2647 for (j = 0; j < trail_list_iterator->trail_length; j++)
2649 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2650 &trail_element->peer))
2652 trail_unique = GNUNET_YES;
2655 trail_element = trail_element->next;
2658 trail_unique = GNUNET_NO;
2661 return trail_unique;
2666 * Add a new trail to existing finger. This function is called only when finger
2667 * is not my own identity or a friend.
2668 * @param existing_finger Finger
2669 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2670 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2671 * @param new_finger_trail_id Unique identifier of the trail.
2674 add_new_trail (struct FingerInfo *existing_finger,
2675 const struct GNUNET_PeerIdentity *new_trail,
2676 unsigned int new_trail_length,
2677 struct GNUNET_HashCode new_trail_id)
2679 struct Trail *trail_list_iterator;
2680 struct FriendInfo *first_friend;
2683 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2689 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2690 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2691 trail_list_iterator->trail_id = new_trail_id;
2692 trail_list_iterator->trail_length = new_trail_length;
2693 existing_finger->trails_count++;
2694 trail_list_iterator->is_present = GNUNET_YES;
2696 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2697 &existing_finger->finger_identity)));
2698 /* If finger is a friend then we never call this function. */
2699 GNUNET_assert (new_trail_length > 0);
2701 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2703 first_friend->trails_count++;
2705 for (i = 0; i < new_trail_length; i++)
2707 struct Trail_Element *element;
2709 element = GNUNET_new (struct Trail_Element);
2710 element->peer = new_trail[i];
2711 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2712 trail_list_iterator->trail_tail,
2715 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2721 * FIXME Check if this function is called for opposite direction if yes then
2722 * take it as parameter.
2723 * Get the next hop to send trail teardown message from routing table and
2724 * then delete the entry from routing table. Send trail teardown message for a
2725 * specific trail of a finger.
2726 * @param finger Finger whose trail is to be removed.
2727 * @param trail List of peers in trail from me to a finger, NOT including
2731 send_trail_teardown (struct FingerInfo *finger,
2732 struct Trail *trail)
2734 struct FriendInfo *friend;
2735 struct GNUNET_PeerIdentity *next_hop;
2737 GNUNET_assert (NULL !=
2738 (next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2739 GDS_ROUTING_SRC_TO_DEST)));
2741 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2744 GNUNET_assert (trail->is_present == GNUNET_YES);
2746 /* Finger is not a friend. */
2747 if (trail->trail_length > 0)
2749 GNUNET_assert (NULL != (friend =
2750 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2751 &trail->trail_head->peer)));
2755 GNUNET_assert (NULL != (friend =
2756 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2757 &finger->finger_identity)));
2760 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2761 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2762 friend->trails_count--;
2763 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2764 GDS_ROUTING_SRC_TO_DEST,
2770 * Send trail teardown message across all the trails to reach to finger.
2771 * @param finger Finger whose all the trail should be freed.
2774 send_all_finger_trails_teardown (struct FingerInfo *finger)
2778 for (i = 0; i < finger->trails_count; i++)
2780 struct Trail *trail;
2782 trail = &finger->trail_list[i];
2783 GNUNET_assert (trail->is_present == GNUNET_YES);
2784 send_trail_teardown (finger, trail);
2785 trail->is_present = GNUNET_NO;
2791 * Free a specific trail
2792 * @param trail List of peers to be freed.
2795 free_trail (struct Trail *trail)
2797 struct Trail_Element *trail_element;
2799 while (NULL != (trail_element = trail->trail_head))
2801 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2805 GNUNET_free_non_null (trail_element);
2807 trail->trail_head = NULL;
2808 trail->trail_tail = NULL;
2813 * Free finger and its trail.
2814 * @param finger Finger to be freed.
2817 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2819 struct Trail *trail;
2822 /* Free all the trails to reach to finger */
2823 for (i = 0; i < finger->trails_count; i++)
2825 trail = &finger->trail_list[i];
2826 //FIXME: Check if there are any missing entry in this list because of
2827 // how we insert. If not then no need of this check.
2828 if (GNUNET_NO == trail->is_present)
2831 if (trail->trail_length > 0)
2835 trail->is_present = GNUNET_NO;
2838 finger->is_present = GNUNET_NO;
2839 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2844 * FIXME: ensure that you are not adding any trail to reach to a friend which
2845 * is a finger. Also decide on should you increment trails count of a friend
2846 * which is also a finger.
2847 * Add a new entry in finger table at finger_table_index.
2848 * In case finger identity is me or a friend, then don't add a trail. NOTE
2849 * trail length to reach to a finger can be 0 only if the finger is a friend
2851 * In case a finger is a friend, then increment the trails count of the friend.
2852 * @param finger_identity Peer Identity of new finger
2853 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2854 * @param finger_trail_length Total number of peers in @a finger_trail.
2855 * @param trail_id Unique identifier of the trail.
2856 * @param finger_table_index Index in finger table.
2859 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2860 const struct GNUNET_PeerIdentity *finger_trail,
2861 unsigned int finger_trail_length,
2862 struct GNUNET_HashCode trail_id,
2863 unsigned int finger_table_index)
2865 struct FingerInfo *new_entry;
2866 struct FriendInfo *first_trail_hop;
2867 struct Trail *trail;
2870 new_entry = GNUNET_new (struct FingerInfo);
2871 new_entry->finger_identity = finger_identity;
2872 new_entry->finger_table_index = finger_table_index;
2873 new_entry->is_present = GNUNET_YES;
2875 /* If the new entry is my own identity. */
2876 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2878 new_entry->trails_count = 0;
2879 finger_table[finger_table_index] = *new_entry;
2880 GNUNET_free (new_entry);
2884 /* If finger is a friend, then we don't actually have a trail.
2885 * Just a trail id */
2886 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2889 new_entry->trail_list[0].trail_id = trail_id;
2890 new_entry->trails_count = 1;
2891 new_entry->trail_list[0].is_present = GNUNET_YES;
2892 new_entry->trail_list[0].trail_length = 0;
2893 new_entry->trail_list[0].trail_head = NULL;
2894 new_entry->trail_list[0].trail_tail = NULL;
2895 finger_table[finger_table_index] = *new_entry;
2896 GNUNET_assert (NULL !=
2898 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2899 &finger_identity)));
2901 first_trail_hop->trails_count++;
2902 GNUNET_free (new_entry);
2906 /* finger trail length can be 0 only in case if finger is my identity or
2907 finger is friend. We should never reach here. */
2908 GNUNET_assert (finger_trail_length > 0);
2910 GNUNET_assert (NULL !=
2912 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2913 &finger_trail[0])));
2914 new_entry->trails_count = 1;
2915 first_trail_hop->trails_count++;
2917 /* Copy the finger trail into trail. */
2918 trail = GNUNET_new (struct Trail);
2919 while (i < finger_trail_length)
2921 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2923 element->next = NULL;
2924 element->prev = NULL;
2925 element->peer = finger_trail[i];
2926 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2932 /* Add trail to trail list. */
2933 new_entry->trail_list[0].trail_head = trail->trail_head;
2934 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2935 new_entry->trail_list[0].trail_length = finger_trail_length;
2936 new_entry->trail_list[0].trail_id = trail_id;
2937 new_entry->trail_list[0].is_present = GNUNET_YES;
2938 finger_table[finger_table_index] = *new_entry;
2939 //GNUNET_free (new_entry);
2940 //GNUNET_free (trail);
2946 * Scan the trail to check if there is any other friend in the trail other than
2947 * first hop. If yes then shortcut the trail, send trail compression message to
2948 * peers which are no longer part of trail and send back the updated trail
2949 * and trail_length to calling function.
2950 * @param finger_identity Finger whose trail we will scan.
2951 * @param finger_trail [in, out] Trail to reach from source to finger,
2952 * @param finger_trail_length Total number of peers in original finger_trail.
2953 * @param finger_trail_id Unique identifier of the finger trail.
2954 * @return updated trail length in case we shortcut the trail, else original
2957 static struct GNUNET_PeerIdentity *
2958 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2959 const struct GNUNET_PeerIdentity *trail,
2960 unsigned int trail_length,
2961 struct GNUNET_HashCode trail_id,
2962 int *new_trail_length)
2964 struct FriendInfo *target_friend;
2965 struct GNUNET_PeerIdentity *new_trail;
2968 /* If I am my own finger identity, then we set trail_length = 0.
2969 Note: Here we don't send trail compression message, as no peer in its
2970 trail added an entry in its routing table.*/
2971 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2973 *new_trail_length = 0;
2977 if (0 == trail_length)
2979 *new_trail_length = 0;
2982 /* If finger identity is a friend. */
2983 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
2985 *new_trail_length = 0;
2987 /* If there is trail to reach this finger/friend */
2988 if (trail_length > 0)
2990 /* Finger is your first friend. */
2991 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
2992 GNUNET_assert (NULL !=
2994 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2997 /* Before you send a trail compression, get the routing entry
2998 from you routing table. update the fields in routing table
2999 to update your next hop to finger identity. */
3000 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3001 trail_id, finger_identity,
3007 /* For other cases, when its neither a friend nor my own identity.*/
3008 for (i = trail_length - 1; i > 0; i--)
3010 /* If the element at this index in trail is a friend. */
3011 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3013 struct FriendInfo *target_friend;
3016 GNUNET_assert (NULL !=
3018 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3020 GNUNET_assert (NULL !=
3021 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3023 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3024 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3029 /* Copy the trail from index i to index (trail_length -1) into a new trail
3030 * and update new trail length */
3031 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3032 while (i < trail_length)
3034 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3038 *new_trail_length = j+1;
3043 /* If we did not compress the trail, return the original trail back.*/
3044 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3045 *new_trail_length = trail_length;
3046 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3052 * Send verify successor message to your current successor over the shortest
3054 * @param successor Current successor.
3057 send_verify_successor_message (struct FingerInfo *successor)
3060 * FIXME: should we send a verify successor message across all the trails
3061 * in case we send through all friends. It complicates the logic, don't
3062 * do it at the moment. Write it as optimization and do it later.
3063 * 1. Here we can have 3 types of fingers
3064 * --> my own identity
3065 * Assumption that the calling function will not send request for
3066 * such successor. Move the logic here.
3067 * --> friend is a finger
3068 * Need to verify if we keep the trails count for a friend. In case of
3069 * friend there is no trail to reach to that friend, so
3070 * 1. no entry in routing table
3072 * 3. no trails count
3073 * 4. but do we increment the count of trails through the friend?
3074 * Trails count is used only to keep a limit on number of trails
3075 * that a friend should be part of. No need to increment the trails
3076 * count for a friend which is a finegr also. so, if finger = friend
3077 * then don't increment the trails count. But if the same friend
3078 * is the first friend to reach to some other finger then increment
3079 * the trails count. Not sure if this design is correct need to verify
3083 struct FriendInfo *target_friend;
3084 struct GNUNET_HashCode trail_id;
3086 struct Trail *trail;
3087 struct Trail_Element *element;
3088 unsigned int trail_length;
3092 trail = &successor->trail_list[i];
3094 /* Trail stored at this index. */
3095 GNUNET_assert (GNUNET_YES == trail->is_present);
3097 trail_id = trail->trail_id;
3098 trail_length = trail->trail_length;
3100 if (trail_length > 0)
3102 /* Copy the trail into peer list. */
3103 struct GNUNET_PeerIdentity peer_list[trail_length];
3105 element = trail->trail_head;
3106 while (j < trail_length)
3108 peer_list[j] = element->peer;
3109 element = element->next;
3113 GNUNET_assert (NULL != (target_friend =
3114 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3116 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3117 successor->finger_identity,
3118 trail_id, peer_list, trail_length,
3124 GNUNET_assert (NULL != (target_friend =
3125 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3126 &successor->finger_identity)));
3127 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3128 successor->finger_identity,
3137 * Update the current search finger index.
3140 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3141 unsigned int finger_table_index)
3143 struct FingerInfo *successor;
3145 if (finger_table_index != current_search_finger_index)
3148 successor = &finger_table[0];
3149 GNUNET_assert (GNUNET_YES == successor->is_present);
3151 /* We were looking for immediate successor. */
3152 if (0 == current_search_finger_index)
3154 /* Start looking for immediate predecessor. */
3155 current_search_finger_index = PREDECESSOR_FINGER_ID;
3157 /* If I am not my own successor, then send a verify successor message. */
3158 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3160 send_verify_successor_message (successor);
3165 current_search_finger_index = current_search_finger_index - 1;
3171 * Calculate finger_table_index from initial 64 bit finger identity value that
3172 * we send in trail setup message.
3173 * @param ultimate_destination_finger_value Value that we calculated from our
3174 * identity and finger_table_index.
3175 * @param is_predecessor Is the entry for predecessor or not?
3176 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3177 * finger_table_index > PREDECESSOR_FINGER_ID ,
3178 * if no valid finger_table_index is found.
3181 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3182 unsigned int is_predecessor)
3186 unsigned int finger_table_index;
3188 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3189 my_id64 = GNUNET_ntohll (my_id64);
3191 /* Is this a predecessor finger? */
3192 if (1 == is_predecessor)
3194 diff = my_id64 - ultimate_destination_finger_value;
3196 finger_table_index = PREDECESSOR_FINGER_ID;
3198 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3203 diff = ultimate_destination_finger_value - my_id64;
3204 finger_table_index = (log10 (diff))/(log10 (2));
3207 return finger_table_index;
3212 * Remove finger and its associated data structures from finger table.
3213 * @param finger Finger to be removed.
3216 remove_existing_finger (struct FingerInfo *existing_finger,
3217 unsigned int finger_table_index)
3219 struct FingerInfo *finger;
3221 finger = &finger_table[finger_table_index];
3222 GNUNET_assert (GNUNET_YES == finger->is_present);
3224 /* If I am my own finger, then we have no trails. */
3225 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3228 finger->is_present = GNUNET_NO;
3229 memset ((void *)&finger_table[finger_table_index], 0,
3230 sizeof (finger_table[finger_table_index]));
3234 /* For all other fingers, send trail teardown across all the trails to reach
3235 finger, and free the finger. */
3236 send_all_finger_trails_teardown (finger);
3237 free_finger (finger, finger_table_index);
3243 * Check if there is already an entry in finger_table at finger_table_index.
3244 * We get the finger_table_index from 64bit finger value we got from the network.
3245 * -- If yes, then select the closest finger.
3246 * -- If new and existing finger are same, then check if you can store more
3248 * -- If yes then add trail, else keep the best trails to reach to the
3250 * -- If the new finger is closest, remove the existing entry, send trail
3251 * teardown message across all the trails to reach the existing entry.
3252 * Add the new finger.
3253 * -- If new and existing finger are different, and existing finger is closest
3255 * -- Update current_search_finger_index.
3256 * @param finger_identity Peer Identity of new finger
3257 * @param finger_trail Trail to reach the new finger
3258 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3259 * @param is_predecessor Is this entry for predecessor in finger_table?
3260 * @param finger_value 64 bit value of finger identity that we got from network.
3261 * @param finger_trail_id Unique identifier of @finger_trail.
3264 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3265 const struct GNUNET_PeerIdentity *finger_trail,
3266 unsigned int finger_trail_length,
3267 unsigned int is_predecessor,
3268 uint64_t finger_value,
3269 struct GNUNET_HashCode finger_trail_id)
3271 struct FingerInfo *existing_finger;
3272 struct GNUNET_PeerIdentity *closest_peer;
3273 struct FingerInfo *successor;
3274 int updated_finger_trail_length;
3275 unsigned int finger_table_index;
3277 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3278 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3280 /* Invalid finger_table_index. */
3281 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3283 GNUNET_break_op (0);
3288 //GDS_ROUTING_test_print();
3289 /* If the new entry for any finger table index other than successor or predecessor
3290 * is same as successor then don't add it in finger table,
3291 * reset the current search finger index and exit. */
3292 if ((0 != finger_table_index) &&
3293 (PREDECESSOR_FINGER_ID != finger_table_index) &&
3294 (finger_table_index == current_search_finger_index)) //FIXME; why do I check this cond?
3296 successor = &finger_table[0];
3297 GNUNET_assert (GNUNET_YES == successor->is_present);
3298 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3299 &successor->finger_identity))
3301 current_search_finger_index = 0;
3306 existing_finger = &finger_table[finger_table_index];
3308 /* No entry present in finger_table for given finger map index. */
3309 if (GNUNET_NO == existing_finger->is_present)
3311 struct GNUNET_PeerIdentity *updated_trail;
3313 /* Shorten the trail if possible. */
3314 updated_finger_trail_length = finger_trail_length;
3316 scan_and_compress_trail (finger_identity, finger_trail,
3317 finger_trail_length, finger_trail_id,
3318 &updated_finger_trail_length);
3319 add_new_finger (finger_identity, updated_trail,
3320 updated_finger_trail_length,
3321 finger_trail_id, finger_table_index);
3322 update_current_search_finger_index (finger_identity,
3323 finger_table_index);
3328 /* If existing entry and finger identity are not same. */
3329 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3332 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3337 /* If the new finger is the closest peer. */
3338 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3340 struct GNUNET_PeerIdentity *updated_trail;
3341 /* Shorten the trail if possible. */
3342 updated_finger_trail_length = finger_trail_length;
3344 scan_and_compress_trail (finger_identity, finger_trail,
3345 finger_trail_length, finger_trail_id,
3346 &updated_finger_trail_length);
3348 remove_existing_finger (existing_finger, finger_table_index);
3349 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3350 finger_trail_id, finger_table_index);
3355 /* Existing finger is the closest one. We need to send trail teardown
3356 across the trail setup in routing table of all the peers. */
3357 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3359 if (finger_trail_length > 0)
3360 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3361 GDS_ROUTING_SRC_TO_DEST,
3364 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3365 GDS_ROUTING_SRC_TO_DEST,
3372 /* If both new and existing entry are same as my_identity, then do nothing. */
3373 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3378 /* If the existing finger is not a friend. */
3380 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3381 &existing_finger->finger_identity))
3383 struct GNUNET_PeerIdentity *updated_trail;
3385 /* Shorten the trail if possible. */
3386 updated_finger_trail_length = finger_trail_length;
3388 scan_and_compress_trail (finger_identity, finger_trail,
3389 finger_trail_length, finger_trail_id,
3390 &updated_finger_trail_length);
3391 /* If there is space to store more trails. */
3392 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3393 add_new_trail (existing_finger, updated_trail,
3394 updated_finger_trail_length, finger_trail_id);
3396 select_and_replace_trail (existing_finger, updated_trail,
3397 updated_finger_trail_length, finger_trail_id);
3401 update_current_search_finger_index (finger_identity, finger_table_index);
3406 * Core handler for P2P put messages.
3407 * @param cls closure
3408 * @param peer sender of the request
3409 * @param message message
3410 * @return #GNUNET_OK to keep the connection open,
3411 * #GNUNET_SYSERR to close it (signal serious error)
3414 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3415 const struct GNUNET_MessageHeader *message)
3417 struct PeerPutMessage *put;
3418 struct GNUNET_PeerIdentity *put_path;
3419 struct GNUNET_PeerIdentity best_known_dest;
3420 struct GNUNET_HashCode intermediate_trail_id;
3421 struct GNUNET_PeerIdentity *next_hop;
3422 enum GNUNET_DHT_RouteOption options;
3423 struct GNUNET_HashCode test_key;
3427 size_t payload_size;
3430 msize = ntohs (message->size);
3431 if (msize < sizeof (struct PeerPutMessage))
3433 GNUNET_break_op (0);
3437 put = (struct PeerPutMessage *) message;
3438 putlen = ntohl (put->put_path_length);
3441 sizeof (struct PeerPutMessage) +
3442 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3444 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3446 GNUNET_break_op (0);
3450 best_known_dest = put->best_known_destination;
3451 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3452 payload = &put_path[putlen];
3453 options = ntohl (put->options);
3454 intermediate_trail_id = put->intermediate_trail_id;
3456 payload_size = msize - (sizeof (struct PeerPutMessage) +
3457 putlen * sizeof (struct GNUNET_PeerIdentity));
3459 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3460 payload, payload_size, &test_key))
3463 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3465 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3466 GNUNET_break_op (0);
3467 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3468 "PUT with key `%s' for block with key %s\n",
3469 put_s, GNUNET_h2s_full (&test_key));
3470 GNUNET_free (put_s);
3475 GNUNET_break_op (0);
3478 /* cannot verify, good luck */
3482 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3484 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3485 ntohl (put->block_type),
3487 NULL, 0, /* bloom filer */
3488 NULL, 0, /* xquery */
3489 payload, payload_size))
3491 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3492 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3495 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3496 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3497 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3498 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3499 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3500 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3502 GNUNET_break_op (0);
3507 /* extend 'put path' by sender */
3508 struct GNUNET_PeerIdentity pp[putlen + 1];
3509 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3511 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3518 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3519 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3521 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3522 GDS_ROUTING_SRC_TO_DEST);
3523 if (NULL == next_hop)
3525 GNUNET_STATISTICS_update (GDS_stats,
3526 gettext_noop ("# Next hop to forward the packet not found "
3527 "trail setup request, packet dropped."),
3529 return GNUNET_SYSERR;
3534 struct Closest_Peer successor;
3535 key_value = GNUNET_ntohll (key_value);
3536 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3538 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3539 *next_hop = successor.next_hop;
3540 intermediate_trail_id = successor.trail_id;
3541 best_known_dest = successor.best_known_destination;
3544 GDS_CLIENTS_process_put (options,
3545 ntohl (put->block_type),
3546 ntohl (put->hop_count),
3547 ntohl (put->desired_replication_level),
3549 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3554 /* I am the final destination */
3555 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3557 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3558 &(put->key),putlen, pp, ntohl (put->block_type),
3559 payload_size, payload);
3563 GDS_NEIGHBOURS_send_put (&put->key,
3564 ntohl (put->block_type),ntohl (put->options),
3565 ntohl (put->desired_replication_level),
3566 best_known_dest, intermediate_trail_id, next_hop,
3567 ntohl (put->hop_count), putlen, pp,
3568 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3569 payload, payload_size);
3576 * Core handler for p2p get requests.
3578 * @param cls closure
3579 * @param peer sender of the request
3580 * @param message message
3581 * @return #GNUNET_OK to keep the connection open,
3582 * #GNUNET_SYSERR to close it (signal serious error)
3585 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3586 const struct GNUNET_MessageHeader *message)
3588 const struct PeerGetMessage *get;
3589 const struct GNUNET_PeerIdentity *get_path;
3590 struct GNUNET_PeerIdentity best_known_dest;
3591 struct GNUNET_HashCode intermediate_trail_id;
3592 struct GNUNET_PeerIdentity *next_hop;
3593 uint32_t get_length;
3597 msize = ntohs (message->size);
3598 if (msize < sizeof (struct PeerGetMessage))
3600 GNUNET_break_op (0);
3604 get = (const struct PeerGetMessage *)message;
3605 get_length = ntohl (get->get_path_length);
3606 best_known_dest = get->best_known_destination;
3607 intermediate_trail_id = get->intermediate_trail_id;
3608 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3611 sizeof (struct PeerGetMessage) +
3612 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3614 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3616 GNUNET_break_op (0);
3620 /* Add sender to get path */
3621 struct GNUNET_PeerIdentity gp[get_length + 1];
3623 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3624 gp[get_length] = *peer;
3625 get_length = get_length + 1;
3627 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3628 key_value = GNUNET_ntohll (key_value);
3630 /* I am not the final destination. I am part of trail to reach final dest. */
3631 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3633 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3634 GDS_ROUTING_SRC_TO_DEST);
3635 if (NULL == next_hop)
3637 GNUNET_STATISTICS_update (GDS_stats,
3638 gettext_noop ("# Next hop to forward the packet not found "
3639 "GET request, packet dropped."),
3641 return GNUNET_SYSERR;
3646 struct Closest_Peer successor;
3648 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3649 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3650 *next_hop = successor.next_hop;
3651 best_known_dest = successor.best_known_destination;
3652 intermediate_trail_id = successor.trail_id;
3655 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3656 get->desired_replication_level, get->get_path_length,
3658 /* I am the final destination. */
3659 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3661 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3663 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3664 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3665 get_length = get_length + 1;
3666 /* FIXME: here it may happen that we find our identity closest to key, but
3667 we don't have the data. then in that case, we should forward the packet
3668 to the next closest peer. */
3669 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3670 get_length, final_get_path,
3671 &final_get_path[get_length-2], &my_identity);
3675 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3676 get->desired_replication_level, best_known_dest,
3677 intermediate_trail_id, next_hop, 0,
3685 * Core handler for get result
3686 * @param cls closure
3687 * @param peer sender of the request
3688 * @param message message
3689 * @return #GNUNET_OK to keep the connection open,
3690 * #GNUNET_SYSERR to close it (signal serious error)
3693 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3694 const struct GNUNET_MessageHeader *message)
3696 const struct PeerGetResultMessage *get_result;
3697 const struct GNUNET_PeerIdentity *get_path;
3698 const struct GNUNET_PeerIdentity *put_path;
3699 const void *payload;
3700 size_t payload_size;
3702 unsigned int getlen;
3703 unsigned int putlen;
3704 int current_path_index;
3706 msize = ntohs (message->size);
3707 if (msize < sizeof (struct PeerGetResultMessage))
3709 GNUNET_break_op (0);
3713 get_result = (const struct PeerGetResultMessage *)message;
3714 getlen = ntohl (get_result->get_path_length);
3715 putlen = ntohl (get_result->put_path_length);
3718 sizeof (struct PeerGetResultMessage) +
3719 getlen * sizeof (struct GNUNET_PeerIdentity) +
3720 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3722 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3724 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3726 GNUNET_break_op (0);
3730 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3731 get_path = &put_path[putlen];
3732 payload = (const void *) &get_path[getlen];
3733 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3734 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3736 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3738 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3739 getlen, get_path, putlen,
3740 put_path, get_result->type, payload_size, payload);
3745 current_path_index = search_my_index (get_path, getlen);
3746 if (-1 == current_path_index )
3749 return GNUNET_SYSERR;
3751 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3752 &get_path[current_path_index - 1],
3753 &(get_result->querying_peer), putlen, put_path,
3754 getlen, get_path, get_result->expiration_time,
3755 payload, payload_size);
3758 return GNUNET_SYSERR;
3764 * @param final_dest_finger_val
3765 * @param intermediate_trail_id
3766 * @param is_predecessor
3767 * @param current_dest
3770 static struct Closest_Peer
3771 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3772 struct GNUNET_HashCode intermediate_trail_id,
3773 unsigned int is_predecessor,
3774 struct GNUNET_PeerIdentity *current_dest)
3776 struct Closest_Peer peer;
3778 /* Find a local best known peer. */
3779 peer = find_successor (final_dest_finger_val, is_predecessor);
3781 /* Am I just a part of a trail towards a finger (current_destination)? */
3782 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest)))
3784 /* Select best successor among one found locally and current_destination
3785 * that we got from network.*/
3786 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3789 struct GNUNET_PeerIdentity *closest_peer;
3790 closest_peer = select_closest_peer (&peer.best_known_destination,
3792 final_dest_finger_val,
3795 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3796 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3798 struct GNUNET_PeerIdentity *next_hop;
3799 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3800 GDS_ROUTING_SRC_TO_DEST);
3801 /* FIXME: Here we found next_hop NULL from routing table, but we still
3802 * have a next_hop from find_successor should we not break and choose that
3804 GNUNET_assert (NULL != next_hop);
3806 peer.next_hop = *next_hop;
3807 peer.best_known_destination = *current_dest;
3808 peer.trail_id = intermediate_trail_id;
3817 * Core handle for PeerTrailSetupMessage.
3818 * @param cls closure
3819 * @param message message
3820 * @param peer peer identity this notification is about
3821 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3824 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3825 const struct GNUNET_MessageHeader *message)
3827 const struct PeerTrailSetupMessage *trail_setup;
3828 const struct GNUNET_PeerIdentity *trail_peer_list;
3829 struct GNUNET_PeerIdentity current_dest;
3830 struct FriendInfo *target_friend;
3831 struct GNUNET_PeerIdentity source;
3832 uint64_t final_dest_finger_val;
3833 //struct GNUNET_HashCode *new_intermediate_trail_id;
3834 //struct GNUNET_PeerIdentity *local_best_known_dest;
3835 struct GNUNET_HashCode intermediate_trail_id;
3836 struct GNUNET_HashCode trail_id;
3837 unsigned int is_predecessor;
3838 uint32_t trail_length;
3841 msize = ntohs (message->size);
3842 if (msize < sizeof (struct PeerTrailSetupMessage))
3844 GNUNET_break_op (0);
3848 trail_setup = (const struct PeerTrailSetupMessage *) message;
3849 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3850 sizeof (struct GNUNET_PeerIdentity);
3851 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3852 sizeof (struct GNUNET_PeerIdentity) != 0)
3854 GNUNET_break_op (0);
3858 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3859 current_dest = trail_setup->best_known_destination;
3860 trail_id = trail_setup->trail_id;
3861 final_dest_finger_val =
3862 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3863 source = trail_setup->source_peer;
3864 is_predecessor = ntohl (trail_setup->is_predecessor);
3865 intermediate_trail_id = trail_setup->intermediate_trail_id;
3867 /* Is my routing table full? */
3868 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3870 /* As my routing table is full, I can no longer handle any more trail
3873 GNUNET_assert (NULL !=
3875 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
3876 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
3877 my_identity, is_predecessor,
3878 trail_peer_list, trail_length,
3879 trail_id, target_friend,
3880 CONGESTION_TIMEOUT);
3884 // new_intermediate_trail_id = GNUNET_new (struct GNUNET_HashCode);
3885 // local_best_known_dest = GNUNET_new (struct GNUNET_PeerIdentity);
3887 /* Get the next hop to forward the trail setup request. */
3888 struct Closest_Peer next_peer =
3889 get_local_best_known_next_hop (final_dest_finger_val,
3890 intermediate_trail_id,
3894 /* Am I the final destination? */
3895 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
3898 /* If I was not the source of this message for which now I am destination */
3899 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
3901 GDS_ROUTING_add (trail_id, *peer, my_identity);
3904 GNUNET_assert (NULL !=
3906 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
3907 GDS_NEIGHBOURS_send_trail_setup_result (source,
3909 target_friend, trail_length,
3911 final_dest_finger_val,
3912 is_predecessor, trail_id);
3916 /* Add yourself to list of peers. */
3917 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3919 memcpy (peer_list, trail_peer_list,
3920 trail_length * sizeof (struct GNUNET_PeerIdentity));
3921 peer_list[trail_length] = my_identity;
3922 GNUNET_assert (NULL !=
3924 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3925 &next_peer.next_hop)));
3926 GDS_NEIGHBOURS_send_trail_setup (source,
3927 final_dest_finger_val,
3928 next_peer.best_known_destination,
3929 target_friend, trail_length + 1, peer_list,
3930 is_predecessor, trail_id,
3931 next_peer.trail_id);
3938 /* FIXME: here we are calculating my_index and comparing also in this function.
3939 And we are doing it again here in this function. Re factor the code. */
3941 * FIXME: Should we call this function everywhere in all the handle functions
3942 * where we have a trail to verify from or a trail id. something like
3943 * if prev hop is not same then drop the message.
3944 * Check if sender_peer and peer from which we should receive the message are
3945 * same or different.
3946 * @param trail_peer_list List of peers in trail
3947 * @param trail_length Total number of peers in @a trail_peer_list
3948 * @param sender_peer Peer from which we got the message.
3949 * @param finger_identity Finger to which trail is setup. It is not part of trail.
3950 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
3951 * message are different.
3952 * #GNUNET_NO if sender_peer and peer from which we should receive the
3953 * message are different.
3956 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
3957 unsigned int trail_length,
3958 const struct GNUNET_PeerIdentity *sender_peer,
3959 struct GNUNET_PeerIdentity finger_identity,
3960 struct GNUNET_PeerIdentity source_peer)
3964 /* I am the source peer. */
3965 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3968 /* Is the first element of the trail is sender_peer.*/
3969 if (trail_length > 0)
3971 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
3977 /* Is finger the sender peer? */
3978 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
3985 /* Get my current location in the trail. */
3986 my_index = search_my_index (trail_peer_list, trail_length);
3990 /* I am the last element in the trail. */
3991 if ((trail_length - 1) == my_index)
3993 /* Is finger the sender_peer? */
3994 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4000 /* Is peer after me in trail the sender peer? */
4001 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4002 &trail_peer_list[my_index + 1]))
4012 * FIXME: we should also add a case where we search if we are present in the trail
4014 * Core handle for p2p trail setup result messages.
4016 * @param message message
4017 * @param peer sender of this message.
4018 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4021 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4022 const struct GNUNET_MessageHeader *message)
4024 const struct PeerTrailSetupResultMessage *trail_result;
4025 const struct GNUNET_PeerIdentity *trail_peer_list;
4026 struct GNUNET_PeerIdentity next_hop;
4027 struct FriendInfo *target_friend;
4028 struct GNUNET_PeerIdentity querying_peer;
4029 struct GNUNET_PeerIdentity finger_identity;
4030 uint32_t trail_length;
4031 uint64_t ulitmate_destination_finger_value;
4032 uint32_t is_predecessor;
4033 struct GNUNET_HashCode trail_id;
4037 msize = ntohs (message->size);
4038 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4040 GNUNET_break_op (0);
4044 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4045 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4046 sizeof (struct GNUNET_PeerIdentity);
4047 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4048 sizeof (struct GNUNET_PeerIdentity) != 0)
4050 GNUNET_break_op (0);
4054 is_predecessor = htonl (trail_result->is_predecessor);
4055 querying_peer = trail_result->querying_peer;
4056 finger_identity = trail_result->finger_identity;
4057 trail_id = trail_result->trail_id;
4058 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4059 ulitmate_destination_finger_value =
4060 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4062 /* FIXME: here we are calculating my_index and comparing also in this function.
4063 And we are doing it again here in this function. Re factor the code. */
4064 /* Ensure that sender peer is the peer from which we were expecting the message. */
4066 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
4068 peer, finger_identity, querying_peer))
4070 GNUNET_break_op (0);
4071 return GNUNET_SYSERR;
4075 /* Am I the one who initiated the query? */
4076 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer,
4079 /* If I am not my own finger identity, then add routing table entry. */
4080 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4082 GDS_ROUTING_add (trail_id, my_identity, *peer);
4085 /* FIXME: Remove this assert later. */
4086 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4088 finger_table_add (finger_identity, trail_peer_list,
4089 trail_length, ulitmate_destination_finger_value,
4090 is_predecessor, trail_id);
4094 /* Get my location in the trail. */
4095 my_index = search_my_index (trail_peer_list, trail_length);
4099 return GNUNET_SYSERR;
4102 /* FIXME: CHECK IF YOU ARE PRESENT MORE THAN ONCE IN THE TRAIL, IF YES
4103 THEN REMOVE ALL THE ENTRIES AND CHOOSE THE PEER THERE.*/
4106 next_hop = trail_result->querying_peer;
4108 next_hop = trail_peer_list[my_index - 1];
4110 /* If the querying_peer is its own finger, then don't add an entry in routing
4111 * table as querying peer will discard the trail. */
4112 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4113 &(trail_result->finger_identity))))
4115 GDS_ROUTING_add (trail_id, next_hop, *peer);
4118 GNUNET_assert (NULL !=
4120 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4121 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4122 target_friend, trail_length, trail_peer_list,
4124 ulitmate_destination_finger_value,
4132 * @param trail Trail to be inverted
4133 * @param trail_length Total number of peers in the trail.
4134 * @return Updated trail
4136 static struct GNUNET_PeerIdentity *
4137 invert_trail (const struct GNUNET_PeerIdentity *trail,
4138 unsigned int trail_length)
4142 struct GNUNET_PeerIdentity *inverted_trail;
4144 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4147 j = trail_length - 1;
4148 while (i < trail_length)
4150 inverted_trail[i] = trail[j];
4155 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4156 &inverted_trail[0]));
4157 return inverted_trail;
4164 * Return the shortest trail to reach from me to my_predecessor.
4165 * @param current_trail Trail from source to me.
4166 * @param current_trail_length Total number of peers in @a current_trail
4167 * @param trail_length [out] Total number of peers in selected trail.
4168 * @return Updated trail from source peer to my_predecessor.
4170 static struct GNUNET_PeerIdentity *
4171 trail_me_to_my_predecessor (const struct GNUNET_PeerIdentity *current_trail,
4172 unsigned int current_trail_length,
4173 unsigned int *trail_length)
4175 struct GNUNET_PeerIdentity *trail_me_to_predecessor;
4176 struct Trail *trail;
4177 struct Trail_Element *trail_element;
4178 struct FingerInfo *my_predecessor;
4180 unsigned int shortest_trail_length = 0;
4181 unsigned int trail_index = 0;
4182 unsigned int flag = 0;
4184 my_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4186 GNUNET_assert (GNUNET_YES == my_predecessor->is_present);
4190 /* Choose the shortest path from me to my predecessor. */
4191 for (i = 0; i < my_predecessor->trails_count; i++)
4193 trail = &my_predecessor->trail_list[i];
4196 shortest_trail_length = trail->trail_length;
4201 if (trail->trail_length > shortest_trail_length)
4203 shortest_trail_length = trail->trail_length;
4207 *trail_length = shortest_trail_length;
4208 GNUNET_assert(*trail_length != 0);
4209 trail_me_to_predecessor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
4212 /* Copy the selected trail and send this trail to calling function. */
4214 trail = &my_predecessor->trail_list[trail_index];
4215 trail_element = trail->trail_head;
4216 while ( i < shortest_trail_length)
4218 trail_me_to_predecessor[i] = trail_element->peer;
4220 trail_element = trail_element->next;
4223 return trail_me_to_predecessor;
4228 * FIXME In case predecessor is a friend then do we add it in routing table.
4229 * if not then check the logic of trail teardown in case we compress the trail
4230 * such that friend is finger. then do we remove the entry from end points or
4231 * not. Ideally we should remove the entries from end point.
4232 * Add finger as your predecessor. To add, first generate a new trail id, invert
4233 * the trail to get the trail from me to finger, add an entry in your routing
4234 * table, send add trail message to peers which are part of trail from me to
4235 * finger and add finger in finger table.
4238 * @param trail_length
4241 update_predecessor (struct GNUNET_PeerIdentity finger,
4242 struct GNUNET_PeerIdentity *trail,
4243 unsigned int trail_length)
4245 struct GNUNET_HashCode trail_to_new_predecessor_id;
4246 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4247 struct FriendInfo *target_friend;
4249 /* Generate trail id for trail from me to new predecessor = finger. */
4250 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4251 &trail_to_new_predecessor_id,
4252 sizeof (trail_to_new_predecessor_id));
4253 //test_finger_table_print();
4254 /* Finger is a friend. */
4255 if (trail_length == 0)
4257 trail_to_new_predecessor = NULL;
4258 /* FIXME: check that you always add trail entry even if your finger is
4260 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4261 GNUNET_assert (NULL != (target_friend =
4262 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4267 /* Invert the trail to get the trail from me to finger, NOT including the
4269 trail_to_new_predecessor = invert_trail (trail, trail_length);
4271 /* Add an entry in your routing table. */
4272 GDS_ROUTING_add (trail_to_new_predecessor_id,
4274 trail_to_new_predecessor[0]);
4276 GNUNET_assert (NULL != (target_friend =
4277 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4278 &trail_to_new_predecessor[0])));
4279 GNUNET_assert (NULL != (
4280 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4281 &trail[trail_length - 1])));
4284 /* Add entry in routing table of all peers that are part of trail from me
4285 to finger, including finger. */
4286 GDS_NEIGHBOURS_send_add_trail (my_identity,
4288 trail_to_new_predecessor_id,
4289 trail_to_new_predecessor,
4293 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4294 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4295 GNUNET_free_non_null (trail_to_new_predecessor);
4299 /* 3. In case you are successor, then
4300 * 3.1 check if you have a predecessor
4301 * 3.2 if no predecessor, then add the source of this message as your
4302 * predecessor. To add, first you should generate a new trail id,
4303 * invert the trail, send add trail message across new trail, add
4304 * an entry in finger table. Now, destination also have routing
4305 * table entry so add in your routing table also.
4306 * 3.3 If its closer than existing one, then do everything in step 1 and
4307 * free existing finger.
4308 * 3.3 If its same as the old one, then do nothing.
4309 * 3.4 if its not same as old one, and between source and old one, old one
4310 * is the correct predecessor, then construct a trail from source
4311 * to your old successor. scan the trail to remove duplicate entries.
4312 * 4. send verify successor result, with trail id of trail from source to
4313 * me. And also send the new trail from source to reach to its probable
4316 * 1. this function is called from both verify and notify.
4317 * 2. so write in a way that it is used in both.
4320 * Check if you have a predecessor.
4321 * 1. if no predecessor, then add finger as your predecessor. To add, first
4322 * generate a new trail id, invert the trail to get the trail from me to finger,
4323 * add an entry in your routing table, send add trail message to peers which
4324 * are part of trail from me to finger and add finger in finger table.
4325 * 2. If there is a predecessor, then compare existing one and finger.
4326 * 2.1 If finger is correct predecessor, then remove current_predecessor. And
4327 * do everything in step 1 to add finger into finger table.
4328 * 2.2 If current_predecessor is correct predecessor, the construct a trail from
4329 * finger to current_predecessor.
4332 * @param trail_length
4336 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4337 struct GNUNET_PeerIdentity *trail,
4338 unsigned int trail_length)
4340 struct FingerInfo *current_predecessor;
4341 struct GNUNET_PeerIdentity *closest_peer;
4342 uint64_t predecessor_value;
4343 unsigned int is_predecessor = 1;
4345 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4346 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4348 /* No predecessor. Add finger as your predecessor. */
4349 if (GNUNET_NO == current_predecessor->is_present)
4351 update_predecessor (finger, trail, trail_length);
4354 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4358 //test_finger_table_print();
4359 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4360 closest_peer = select_closest_peer (&finger,
4361 ¤t_predecessor->finger_identity,
4362 predecessor_value, is_predecessor);
4364 /* Finger is the closest predecessor. Remove the existing one and add the new
4366 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, &finger))
4368 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4369 update_predecessor (finger, trail, trail_length);
4378 * Core handle for p2p verify successor messages.
4379 * @param cls closure
4380 * @param message message
4381 * @param peer peer identity this notification is about
4382 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4385 handle_dht_p2p_verify_successor(void *cls,
4386 const struct GNUNET_PeerIdentity *peer,
4387 const struct GNUNET_MessageHeader *message)
4389 const struct PeerVerifySuccessorMessage *vsm;
4390 struct GNUNET_HashCode trail_id;
4391 struct GNUNET_PeerIdentity successor;
4392 struct GNUNET_PeerIdentity source_peer;
4393 struct GNUNET_PeerIdentity *trail;
4394 struct GNUNET_PeerIdentity *next_hop;
4395 struct GNUNET_PeerIdentity *trail_to_predecessor; //used unintialized somewhere.
4396 struct FingerInfo *current_predecessor;
4397 struct FriendInfo *target_friend;
4398 unsigned int trail_to_predecessor_length;
4400 unsigned int trail_length;
4402 msize = ntohs (message->size);
4404 /* Here we pass trail to reach from source to successor, and in case successor
4405 * does not have any predecessor, then we will add source as my predecessor.
4406 * So we pass the trail along with trail id. */
4407 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4409 GNUNET_break_op (0);
4413 vsm = (const struct PeerVerifySuccessorMessage *) message;
4414 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4415 sizeof (struct GNUNET_PeerIdentity);
4416 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4417 sizeof (struct GNUNET_PeerIdentity) != 0)
4419 GNUNET_break_op (0);
4423 trail_id = vsm->trail_id;
4424 source_peer = vsm->source_peer;
4425 successor = vsm->successor;
4426 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4428 //FIXME: we can have a check if peer is correct peer which should have
4429 // sent this message. use same function is_sender_peer_correct
4430 // but specify direction so that the function can be used in other functions
4433 /* I am not the successor of source_peer. Pass the message to next_hop on
4435 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4437 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4438 if (NULL == next_hop)
4441 return GNUNET_SYSERR;
4443 GNUNET_assert (NULL !=
4445 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4447 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4448 trail_id, trail, trail_length,
4453 /* I am the destination of this message. */
4455 /* Check if the source_peer could be our predecessor and if yes then update
4457 compare_and_update_predecessor (source_peer, trail, trail_length);
4459 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4461 /* Is source of this message NOT my predecessor. */
4462 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4465 /* if current predecessor is not a friend, we have a trail to reach to it*/
4466 if (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4467 ¤t_predecessor->finger_identity)))
4469 trail_to_predecessor =
4470 trail_me_to_my_predecessor (trail,
4472 &trail_to_predecessor_length);
4477 trail_to_predecessor = NULL;
4478 trail_to_predecessor_length = 0;
4480 GNUNET_assert (NULL !=
4482 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4483 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4484 current_predecessor->finger_identity,
4485 trail_id, trail_to_predecessor,
4486 trail_to_predecessor_length,
4487 GDS_ROUTING_DEST_TO_SRC,
4489 GNUNET_free_non_null (trail_to_predecessor);
4495 * Construct the trail from me to probable successor that goes through current
4496 * successor. Scan this trail to check if you can shortcut the trail somehow.
4497 * In case we can shortcut the trail, don't send trail compression as we don't
4498 * have any entry in routing table.
4499 * @param current_successor
4500 * @param probable_successor
4501 * @param trail_from_curr_to_probable_successor
4502 * @param trail_from_curr_to_probable_successor_length
4503 * @param trail_to_new_successor_length
4506 static struct GNUNET_PeerIdentity *
4507 get_trail_to_new_successor (struct FingerInfo *current_successor,
4508 struct GNUNET_PeerIdentity probable_successor,
4509 const struct GNUNET_PeerIdentity *trail_from_curr_to_probable_successor,
4510 unsigned int trail_from_curr_to_probable_successor_length,
4511 unsigned int *trail_to_new_successor_length)
4513 struct GNUNET_PeerIdentity *trail_to_new_successor;
4514 unsigned int shortest_trail_length;
4515 unsigned int flag = 0;
4516 unsigned int shortest_trail_index;
4517 struct Trail *trail;
4518 struct Trail_Element *trail_element;
4521 /* If the probable successor is a friend, then we don't need to have a trail
4523 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4524 &probable_successor))
4526 trail_to_new_successor = NULL;
4527 *trail_to_new_successor_length = 0;
4528 return trail_to_new_successor;
4532 * FIXME: can we some how use the select_finger_trail here??
4533 * complete this logic.
4534 * 1. Choose the shortest trail to reach to current successor.
4535 * 2. append the trail with the current trail
4536 * 3. scan the trail for duplicate elements
4537 * 4. scan the trail for friend
4538 * 5. get the shortest trail.
4539 * 6. send back the trail.
4543 /* Choose the shortest trail to reach the current_successor */
4544 for (i = 0; i < current_successor->trails_count; i++)
4546 trail = ¤t_successor->trail_list[i];
4549 shortest_trail_index = i;
4550 shortest_trail_length = trail->trail_length;
4555 if (shortest_trail_length > trail->trail_length)
4557 shortest_trail_index = i;
4558 shortest_trail_length = trail->trail_length;
4563 /* It means that probable successor is the friend of current successor. */
4564 if (0 == trail_from_curr_to_probable_successor_length)
4566 *trail_to_new_successor_length = shortest_trail_length + 1;
4567 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4568 (*trail_to_new_successor_length));
4569 /* Copy the selected trail and send this trail to calling function. */
4571 trail = ¤t_successor->trail_list[shortest_trail_index];
4572 trail_element = trail->trail_head;
4573 while ( i < shortest_trail_length)
4575 trail_to_new_successor[i] = trail_element->peer;
4577 trail_element = trail_element->next;
4580 trail_to_new_successor[i] = current_successor->finger_identity;
4584 *trail_to_new_successor_length = shortest_trail_length +
4585 trail_from_curr_to_probable_successor_length;
4586 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4587 (*trail_to_new_successor_length));
4588 /* Copy the selected trail and send this trail to calling function. */
4590 trail = ¤t_successor->trail_list[shortest_trail_index];
4591 trail_element = trail->trail_head;
4592 while ( i < shortest_trail_length)
4594 trail_to_new_successor[i] = trail_element->peer;
4596 trail_element = trail_element->next;
4600 while (j < trail_from_curr_to_probable_successor_length)
4602 trail_to_new_successor[i] = trail_from_curr_to_probable_successor[j];
4607 return trail_to_new_successor;
4612 * Compare probable successor and current successor.
4613 * If the probable successor is the correct successor, then construct the trail
4614 * from me to probable successor that goes through current successor. Scan this
4615 * trail to check if you can shortcut the trail somehow. In case we can short
4616 * cut the trail, don't send trail compression as we don't have any entry in
4618 * Once you have scanned trail, then add an entry in finger table.
4619 * Add an entry in routing table (Only if new successor is NOT a friend).
4620 * @param probable_successor Peer which could be our successor
4621 * @param trail_from_curr_to_probable_successor Trail from current successor
4622 * to probable successor, NOT
4624 * @param trail_from_curr_to_probable_successor_length Total number of peers
4625 * in @a trail_from_curr_to_probable_successor
4628 compare_and_update_successor (struct GNUNET_PeerIdentity probable_successor,
4629 const struct GNUNET_PeerIdentity *trail_from_curr_to_probable_successor,
4630 unsigned int trail_from_curr_to_probable_successor_length)
4632 struct GNUNET_PeerIdentity *closest_peer;
4633 struct GNUNET_PeerIdentity *trail_to_new_successor;
4634 struct GNUNET_HashCode trail_id;
4635 unsigned int trail_to_new_successor_length;
4636 uint64_t successor_value;
4637 struct FingerInfo *current_successor;
4638 struct FriendInfo *target_friend;
4639 unsigned int is_predecessor = 0;
4640 //test_finger_table_print();
4641 current_successor = &finger_table[0];
4642 GNUNET_assert (GNUNET_YES == current_successor->is_present);
4644 /* Compute the 64 bit value of successor identity. We need this as we need to
4645 * find the closest peer w.r.t this value.*/
4646 successor_value = compute_finger_identity_value (0);
4647 closest_peer = select_closest_peer (¤t_successor->finger_identity,
4648 &probable_successor,
4649 successor_value, is_predecessor);
4651 /* If the current_successor is the closest one, then exit. */
4652 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4653 ¤t_successor->finger_identity))
4656 /* probable successor is the closest_peer. */
4658 /* Get the trail to reach to your new successor. */
4659 trail_to_new_successor = get_trail_to_new_successor (current_successor,
4661 trail_from_curr_to_probable_successor,
4662 trail_from_curr_to_probable_successor_length,
4663 &trail_to_new_successor_length);
4664 /* Remove the existing successor. */
4665 remove_existing_finger (current_successor, 0);
4667 /* Generate a new trail id to reach to your new successor. */
4668 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4669 &trail_id, sizeof (trail_id));
4670 add_new_finger (probable_successor, trail_to_new_successor,
4671 trail_to_new_successor_length, trail_id, 0);
4673 /* If probable successor is not a friend, then add an entry in your own
4675 if (trail_to_new_successor_length > 0)
4677 /* FIXME: check that you always add trail entry even if your finger is
4679 GDS_ROUTING_add (trail_id, my_identity, trail_to_new_successor[0]);
4680 GNUNET_assert (NULL !=
4681 (target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4682 &trail_to_new_successor[0])));
4686 /* FIXME: check that you always add trail entry even if your finger is
4688 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4689 GNUNET_assert (NULL !=
4691 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4692 &probable_successor)));
4694 //test_finger_table_print();
4695 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4696 trail_from_curr_to_probable_successor,
4697 trail_from_curr_to_probable_successor_length,
4705 * Core handle for p2p verify successor result messages.
4706 * @param cls closure
4707 * @param message message
4708 * @param peer peer identity this notification is about
4709 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4712 handle_dht_p2p_verify_successor_result(void *cls,
4713 const struct GNUNET_PeerIdentity *peer,
4714 const struct GNUNET_MessageHeader *message)
4716 const struct PeerVerifySuccessorResultMessage *vsrm;
4717 enum GDS_ROUTING_trail_direction trail_direction;
4718 struct GNUNET_PeerIdentity querying_peer;
4719 struct GNUNET_HashCode trail_id;
4720 struct GNUNET_PeerIdentity *next_hop;
4721 struct FriendInfo *target_friend;
4722 struct GNUNET_PeerIdentity probable_successor;
4723 const struct GNUNET_PeerIdentity *trail;
4724 unsigned int trail_length;
4727 msize = ntohs (message->size);
4728 /* We send a trail to reach from old successor to new successor, if
4729 * old_successor != new_successor.*/
4730 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4732 GNUNET_break_op (0);
4736 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4737 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4738 sizeof (struct GNUNET_PeerIdentity);
4740 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4741 sizeof (struct GNUNET_PeerIdentity) != 0)
4743 GNUNET_break_op (0);
4747 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4748 querying_peer = vsrm->querying_peer;
4749 trail_direction = ntohl (vsrm->trail_direction);
4750 trail_id = vsrm->trail_id;
4751 probable_successor = vsrm->probable_successor;
4753 //FIXME: add a check to ensure that peer from which you got the message is
4755 /* I am the querying_peer. */
4756 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4758 compare_and_update_successor (probable_successor, trail, trail_length);
4762 /*If you are not the querying peer then pass on the message */
4763 GNUNET_assert (NULL != (next_hop =
4764 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
4765 GNUNET_assert (NULL !=
4767 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4768 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4769 vsrm->current_successor,
4770 probable_successor, trail_id,
4773 trail_direction, target_friend);
4779 * Core handle for p2p notify new successor messages.
4780 * @param cls closure
4781 * @param message message
4782 * @param peer peer identity this notification is about
4783 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4786 handle_dht_p2p_notify_new_successor(void *cls,
4787 const struct GNUNET_PeerIdentity *peer,
4788 const struct GNUNET_MessageHeader *message)
4790 const struct PeerNotifyNewSuccessorMessage *nsm;
4791 struct GNUNET_PeerIdentity *trail;
4792 struct GNUNET_PeerIdentity source;
4793 struct GNUNET_PeerIdentity new_successor;
4794 struct GNUNET_HashCode trail_id;
4795 struct GNUNET_PeerIdentity next_hop;
4796 struct FriendInfo *target_friend;
4799 uint32_t trail_length;
4801 msize = ntohs (message->size);
4802 /* We have the trail to reach from source to new successor. */
4803 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
4805 GNUNET_break_op (0);
4809 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
4810 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
4811 sizeof (struct GNUNET_PeerIdentity);
4812 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4813 sizeof (struct GNUNET_PeerIdentity) != 0)
4815 GNUNET_break_op (0);
4819 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
4820 source = nsm->source_peer;
4821 new_successor = nsm->new_successor;
4822 trail_id = nsm->trail_id;
4824 //FIXME: add a check to make sure peer is correct.
4826 /* I am the new_successor to source_peer. */
4827 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
4829 GDS_ROUTING_add (trail_id, *peer, my_identity);
4830 compare_and_update_predecessor (source, trail, trail_length);
4834 /* I am part of trail to reach to successor. */
4835 my_index = search_my_index (trail, trail_length);
4838 GNUNET_break_op (0);
4839 return GNUNET_SYSERR;
4841 if (trail_length == my_index)
4842 next_hop = new_successor;
4844 next_hop = trail[my_index + 1];
4846 /* Add an entry in routing table for trail from source to its new successor. */
4847 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
4848 GNUNET_assert (NULL !=
4850 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4851 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
4853 trail_id, target_friend);
4860 * Core handler for P2P trail rejection message
4861 * @param cls closure
4862 * @param message message
4863 * @param peer peer identity this notification is about
4864 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4867 handle_dht_p2p_trail_setup_rejection (void *cls,
4868 const struct GNUNET_PeerIdentity *peer,
4869 const struct GNUNET_MessageHeader *message)
4871 const struct PeerTrailRejectionMessage *trail_rejection;
4872 unsigned int trail_length;
4873 const struct GNUNET_PeerIdentity *trail_peer_list;
4874 struct FriendInfo *target_friend;
4875 struct GNUNET_TIME_Relative congestion_timeout;
4876 struct GNUNET_HashCode trail_id;
4877 struct GNUNET_PeerIdentity next_peer;
4878 struct GNUNET_PeerIdentity source;
4879 struct GNUNET_PeerIdentity *next_hop;
4880 uint64_t ultimate_destination_finger_value;
4881 unsigned int is_predecessor;
4884 msize = ntohs (message->size);
4885 /* We are passing the trail setup so far. */
4886 if (msize < sizeof (struct PeerTrailRejectionMessage))
4888 GNUNET_break_op (0);
4892 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
4893 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
4894 sizeof (struct GNUNET_PeerIdentity);
4895 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4896 sizeof (struct GNUNET_PeerIdentity) != 0)
4898 GNUNET_break_op (0);
4902 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
4903 is_predecessor = ntohl (trail_rejection->is_predecessor);
4904 congestion_timeout = trail_rejection->congestion_time;
4905 source = trail_rejection->source_peer;
4906 trail_id = trail_rejection->trail_id;
4907 ultimate_destination_finger_value =
4908 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
4910 /* First set the congestion time of the friend that sent you this message. */
4911 GNUNET_assert (NULL !=
4913 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4914 target_friend->congestion_timestamp =
4915 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
4916 congestion_timeout);
4918 /* I am the source peer which wants to setup the trail. Do nothing.
4919 * send_find_finger_trail_task is scheduled periodically.*/
4920 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
4923 /* If I am congested then pass this message to peer before me in trail. */
4924 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
4926 struct GNUNET_PeerIdentity *new_trail;
4927 unsigned int new_trail_length;
4929 /* Remove yourself from the trail setup so far. */
4930 if (trail_length == 1)
4933 new_trail_length = 0;
4938 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
4939 sizeof (struct GNUNET_PeerIdentity));
4941 /* Remove myself from the trail. */
4942 new_trail_length = trail_length -1;
4943 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4944 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4947 GNUNET_assert (NULL !=
4949 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4950 GDS_NEIGHBOURS_send_trail_rejection (source,
4951 ultimate_destination_finger_value,
4952 my_identity, is_predecessor,
4953 new_trail,new_trail_length,trail_id,
4954 target_friend, CONGESTION_TIMEOUT);
4956 GNUNET_free (new_trail);
4960 struct Closest_Peer successor;
4961 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
4962 /* Am I the final destination? */
4963 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
4966 if (0 == trail_length)
4969 next_peer = trail_peer_list[trail_length-1];
4971 GNUNET_assert (NULL !=
4973 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
4975 GDS_NEIGHBOURS_send_trail_setup_result (source,
4977 target_friend, trail_length,
4980 ultimate_destination_finger_value,
4985 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4987 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
4988 peer_list[trail_length] = my_identity;
4990 GNUNET_assert (NULL !=
4992 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4993 GDS_NEIGHBOURS_send_trail_setup (source,
4994 ultimate_destination_finger_value,
4995 successor.best_known_destination,
4996 target_friend, trail_length + 1, peer_list,
4997 is_predecessor, trail_id,
4998 successor.trail_id);
5005 * Core handle for p2p trail tear compression messages.
5006 * @param cls closure
5007 * @param message message
5008 * @param peer peer identity this notification is about
5009 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5012 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5013 const struct GNUNET_MessageHeader *message)
5015 const struct PeerTrailCompressionMessage *trail_compression;
5016 struct GNUNET_PeerIdentity *next_hop;
5017 struct FriendInfo *target_friend;
5018 struct GNUNET_HashCode trail_id;
5021 msize = ntohs (message->size);
5022 /* Here we pass only the trail id. */
5023 if (msize != sizeof (struct PeerTrailCompressionMessage))
5025 GNUNET_break_op (0);
5029 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5030 trail_id = trail_compression->trail_id;
5031 //FIXME: again check if peer is the correct peer. same logic as
5032 //trail teardown make a generic function.
5034 /* Am I the new first friend to reach to finger of this trail. */
5035 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5038 GNUNET_assert (NULL !=
5039 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5040 &trail_compression->source_peer)));
5041 /* Update your prev hop to source of this message. */
5042 GNUNET_assert (GNUNET_SYSERR !=
5043 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5044 trail_compression->source_peer)));
5048 /* Pass the message to next hop to finally reach to new_first_friend. */
5049 /* FIXME THIS FAILS.*/
5050 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5051 if (NULL == next_hop) //FIXME: Assertion failure
5057 GNUNET_assert (NULL !=
5059 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5061 GDS_ROUTING_remove_trail (trail_id);
5063 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5065 trail_compression->new_first_friend,
5072 * Core handler for trail teardown message.
5073 * @param cls closure
5074 * @param message message
5075 * @param peer sender of this messsage.
5076 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5079 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5080 const struct GNUNET_MessageHeader *message)
5082 const struct PeerTrailTearDownMessage *trail_teardown;
5083 enum GDS_ROUTING_trail_direction trail_direction;
5084 struct GNUNET_HashCode trail_id;
5085 struct GNUNET_PeerIdentity *next_hop;
5088 msize = ntohs (message->size);
5090 /* Here we pass only the trail id. */
5091 if (msize != sizeof (struct PeerTrailTearDownMessage))
5093 GNUNET_break_op (0);
5097 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5098 trail_direction = ntohl (trail_teardown->trail_direction);
5099 trail_id = trail_teardown->trail_id;
5101 /* Check if peer is the real peer from which we should get this message.*/
5102 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5103 /* FIXME: is using negation of trail direction correct. */
5105 GNUNET_assert (NULL != (prev_hop =
5106 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5107 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5110 return GNUNET_SYSERR;
5114 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5116 if (NULL == next_hop)
5119 return GNUNET_SYSERR;
5122 /* I am the next hop, which means I am the final destination. */
5123 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5125 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5130 /* If not final destination, then send a trail teardown message to next hop.*/
5131 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5132 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5133 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5141 * Core handle for p2p add trail message.
5142 * @param cls closure
5143 * @param message message
5144 * @param peer peer identity this notification is about
5145 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5148 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5149 const struct GNUNET_MessageHeader *message)
5151 const struct PeerAddTrailMessage *add_trail;
5152 const struct GNUNET_PeerIdentity *trail;
5153 struct GNUNET_HashCode trail_id;
5154 struct GNUNET_PeerIdentity destination_peer;
5155 struct GNUNET_PeerIdentity source_peer;
5156 struct GNUNET_PeerIdentity next_hop;
5157 unsigned int trail_length;
5158 unsigned int my_index;
5161 msize = ntohs (message->size);
5162 /* In this message we pass the whole trail from source to destination as we
5163 * are adding that trail.*/
5164 if (msize < sizeof (struct PeerAddTrailMessage))
5166 GNUNET_break_op (0);
5170 add_trail = (const struct PeerAddTrailMessage *) message;
5171 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5172 sizeof (struct GNUNET_PeerIdentity);
5173 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5174 sizeof (struct GNUNET_PeerIdentity) != 0)
5176 GNUNET_break_op (0);
5180 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5181 destination_peer = add_trail->destination_peer;
5182 source_peer = add_trail->source_peer;
5183 trail_id = add_trail->trail_id;
5185 //FIXME: add a check that sender peer is not malicious. Make it a generic
5186 // function so that it can be used in all other functions where we need the
5187 // same functionality.
5189 /* I am not the destination of the trail. */
5190 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5192 struct FriendInfo *target_friend;
5194 /* Get my location in the trail. */
5195 my_index = search_my_index (trail, trail_length);
5199 GNUNET_break_op (0);
5200 return GNUNET_SYSERR;
5204 if ((trail_length - 1) == my_index)
5207 next_hop = destination_peer;
5211 next_hop = trail[my_index + 1];
5213 /* FIXME: check that you always add trail entry even if your finger is
5215 /* Add in your routing table. */
5216 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5217 GNUNET_assert (NULL !=
5219 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5220 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5221 trail, trail_length, target_friend);
5224 /* FIXME: check that you always add trail entry even if your finger is
5226 /* I am the destination. Add an entry in routing table. */
5227 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5233 * Free the finger trail in which the first friend to reach to a finger is
5234 * disconnected_friend. Also remove entry from routing table for that particular
5236 * @param disconnected_friend PeerIdentity of friend which got disconnected
5237 * @param remove_finger Finger whose trail we need to check if it has
5238 * disconnected_friend as the first hop.
5239 * @return Total number of trails in which disconnected_friend was the first
5243 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5244 struct FingerInfo *remove_finger)
5246 unsigned int matching_trails_count;
5249 /* Number of trails with disconnected_friend as the first hop in the trail
5250 * to reach from me to remove_finger, NOT including endpoints. */
5251 matching_trails_count = 0;
5253 /* Iterate over all the trails of finger. */
5254 for (i = 0; i < remove_finger->trails_count; i++)
5256 struct Trail *trail;
5257 trail = &remove_finger->trail_list[i];
5259 /* This assertion is ensure that there are no gaps in the trail list.
5260 REMOVE IT AFTERWARDS. */
5261 GNUNET_assert (GNUNET_YES == trail->is_present);
5263 /* First friend to reach to finger is disconnected_peer. */
5264 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5265 disconnected_friend))
5267 struct GNUNET_PeerIdentity *next_hop;
5268 struct FriendInfo *remove_friend;
5270 GNUNET_assert (NULL !=
5272 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5273 disconnected_friend)));
5274 /* FIXME: removing no but check it. */
5275 //remove_friend->trails_count--;
5276 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5277 GDS_ROUTING_SRC_TO_DEST);
5279 /* Here it may happen that as all the peers got disconnected, the entry in
5280 routing table for that particular trail has been removed, because the
5281 previously disconnected peer was either a next hop or prev hop of that
5283 if (NULL == next_hop)
5286 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5288 matching_trails_count++;
5289 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5292 trail->is_present = GNUNET_NO;
5295 return matching_trails_count;
5300 * Iterate over finger_table entries.
5301 * 0. Ignore finger which is my_identity or if no valid entry present at
5302 * that finger index.
5303 * 1. If disconnected_friend is a finger, then remove the routing entry from
5304 your own table. Free the trail.
5305 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5306 * 2.1 Remove all the trails and entry from routing table in which disconnected
5307 * friend is the first friend in the trail. If disconnected_friend is the
5308 * first friend in all the trails to reach finger, then remove the finger.
5309 * @param disconnected_friend Peer identity of friend which got disconnected.
5312 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5314 struct FingerInfo *remove_finger;
5315 struct FriendInfo *remove_friend;
5316 int removed_trails_count;
5319 /* Iterate over finger table entries. */
5320 for (i = 0; i < MAX_FINGERS; i++)
5322 remove_finger = &finger_table[i];
5324 /* No finger stored at this trail index. */
5325 if (GNUNET_NO == remove_finger->is_present)
5328 /* I am my own finger, then ignore this finger. */
5329 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5333 /* Is disconnected_peer a finger? */
5334 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5335 &remove_finger->finger_identity))
5337 struct GNUNET_PeerIdentity *next_hop;
5338 struct GNUNET_HashCode trail_id;
5341 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5342 trail_id = remove_finger->trail_list[0].trail_id;
5346 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5348 /* FIXME: This assertion fails check why*/
5350 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5351 &remove_finger->finger_identity)));
5352 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5353 GNUNET_assert (NULL !=
5355 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5356 disconnected_peer)));
5359 remove_finger->trail_list[0].is_present = GNUNET_NO;
5360 //GNUNET_assert (0 != remove_friend->trails_count);
5361 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5362 remove_finger->is_present = GNUNET_NO;
5363 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5367 /* If finger is a friend but not disconnected_friend, then continue. */
5368 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5369 &remove_finger->finger_identity))
5372 /* Iterate over the list of trails to reach remove_finger. Check if
5373 * disconnected_friend is the first friend in any of the trail. */
5374 removed_trails_count = remove_matching_trails (disconnected_peer,
5376 remove_finger->trails_count =
5377 remove_finger->trails_count - removed_trails_count;
5378 /* All the finger trails had disconnected_friend as the first friend,
5379 * so free the finger. */
5380 if (remove_finger->trails_count == 0)
5382 remove_finger->is_present = GNUNET_NO;
5383 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5390 * Method called whenever a peer disconnects.
5392 * @param cls closure
5393 * @param peer peer identity this notification is about
5396 handle_core_disconnect (void *cls,
5397 const struct GNUNET_PeerIdentity *peer)
5399 struct FriendInfo *remove_friend;
5401 /* If disconnected to own identity, then return. */
5402 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5405 GNUNET_assert (NULL != (remove_friend =
5406 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5408 /* Remove fingers with peer as first friend or if peer is a finger. */
5409 remove_matching_fingers (peer);
5411 /* Remove any trail from routing table of which peer is a part of. This function
5412 * internally sends a trail teardown message in the direction of which
5413 * disconnected peer is not part of. */
5414 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5416 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5418 /* Remove peer from friend_peermap. */
5419 GNUNET_assert (GNUNET_YES ==
5420 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5424 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5427 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5429 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5430 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5439 * Method called whenever a peer connects.
5441 * @param cls closure
5442 * @param peer_identity peer identity this notification is about
5445 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5447 struct FriendInfo *friend;
5449 /* Check for connect to self message */
5450 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5453 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5455 /* If peer already exists in our friend_peermap, then exit. */
5456 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5463 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
5466 friend = GNUNET_new (struct FriendInfo);
5467 friend->id = *peer_identity;
5469 GNUNET_assert (GNUNET_OK ==
5470 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5471 peer_identity, friend,
5472 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5475 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5476 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5477 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5482 * To be called on core init/fail.
5484 * @param cls service closure
5485 * @param identity the public identity of this peer
5488 core_init (void *cls,
5489 const struct GNUNET_PeerIdentity *identity)
5491 my_identity = *identity;
5494 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5495 my_id64 = GNUNET_ntohll (my_id64);
5496 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5497 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5502 * Initialize finger table entries.
5505 finger_table_init ()
5510 for(i = 0; i < MAX_FINGERS; i++)
5512 finger_table[i].is_present = GNUNET_NO;
5513 for (j = 0; j < MAXIMUM_TRAILS_PER_FINGER; j++)
5514 finger_table[i].trail_list[j].is_present = GNUNET_NO;
5515 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5521 * Initialize neighbours subsystem.
5522 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5525 GDS_NEIGHBOURS_init (void)
5527 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5528 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5529 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5530 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5531 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5532 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5533 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5534 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5535 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5536 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5537 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5538 sizeof (struct PeerTrailCompressionMessage)},
5539 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5540 sizeof (struct PeerTrailTearDownMessage)},
5541 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5546 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5547 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5548 GNUNET_NO, core_handlers);
5549 if (NULL == core_api)
5550 return GNUNET_SYSERR;
5552 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5553 finger_table_init ();
5560 * Shutdown neighbours subsystem.
5563 GDS_NEIGHBOURS_done (void)
5565 if (NULL == core_api)
5568 GNUNET_CORE_disconnect (core_api);
5571 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5572 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5573 friend_peermap = NULL;
5575 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5578 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5579 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5587 * @return my identity
5589 struct GNUNET_PeerIdentity
5590 GDS_NEIGHBOURS_get_my_id (void)
5595 /* end of gnunet-service-xdht_neighbours.c */