2 This file is part of GNUnet.
3 (C) 2009-2014 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file dht/gnunet-service-xdht_neighbours.c
23 * @brief GNUnet DHT service's finger and friend table management code
24 * @author Supriti Singh
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_ats_service.h"
34 #include "gnunet_core_service.h"
35 #include "gnunet_datacache_lib.h"
36 #include "gnunet_transport_service.h"
37 #include "gnunet_dht_service.h"
38 #include "gnunet_statistics_service.h"
39 #include "gnunet-service-xdht.h"
40 #include "gnunet-service-xdht_clients.h"
41 #include "gnunet-service-xdht_datacache.h"
42 #include "gnunet-service-xdht_neighbours.h"
43 #include "gnunet-service-xdht_routing.h"
49 * 1. In X-Vine paper, there is no policy defined for replicating the data to
50 * recover in case of peer failure. We can do it in Chord way. In R5N, the key
51 * is hashed and then data is stored according to the key value generated after
53 * 2. We will keep an entry in routing table even if its a friend for the moment.
54 * Because I am not sure if there is a case where it will not work.
55 * Trail id we can keep but actually there is no trail.
60 * Maximum possible fingers (including predecessor) of a peer
62 #define MAX_FINGERS 65
65 * Maximum allowed number of pending messages per friend peer.
67 #define MAXIMUM_PENDING_PER_FRIEND 64
70 * How long to wait before sending another find finger trail request
72 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
75 * How long at most to wait for transmission of a request to a friend ?
77 #define GET_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
80 * Duration for which I may remain congested.
81 * Note: Its a static value. In future, a peer may do some analysis and calculate
82 * congestion_timeout based on 'some' parameters.
84 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
87 * Maximum number of trails allowed to go through a friend.
89 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
92 * Maximum number of trails stored per finger.
94 #define MAXIMUM_TRAILS_PER_FINGER 1
97 * Finger map index for predecessor entry in finger table.
99 #define PREDECESSOR_FINGER_ID 64
102 * Wrap around in peer identity circle.
104 #define PEER_IDENTITES_WRAP_AROUND pow(2, 64) - 1
107 * FIXME: Its use only at 3 places check if you can remove it.
108 * To check if a finger is predecessor or not.
110 enum GDS_NEIGHBOURS_finger_type
112 GDS_FINGER_TYPE_PREDECESSOR = 0,
113 GDS_FINGER_TYPE_NON_PREDECESSOR = 1
116 GNUNET_NETWORK_STRUCT_BEGIN
121 struct PeerPutMessage
124 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
126 struct GNUNET_MessageHeader header;
131 uint32_t options GNUNET_PACKED;
136 uint32_t block_type GNUNET_PACKED;
141 uint32_t hop_count GNUNET_PACKED;
144 * Replication level for this message
145 * In the current implementation, this value is not used.
147 uint32_t desired_replication_level GNUNET_PACKED;
150 * Length of the PUT path that follows (if tracked).
152 uint32_t put_path_length GNUNET_PACKED;
155 * Best known destination (could be my friend or finger) which should
156 * get this message next.
158 struct GNUNET_PeerIdentity best_known_destination;
161 * In case best_known_destination is a finger, then trail to reach
162 * to that finger. Else its default value is 0.
164 struct GNUNET_HashCode intermediate_trail_id;
167 * When does the content expire?
169 struct GNUNET_TIME_AbsoluteNBO expiration_time;
172 * The key to store the value under.
174 struct GNUNET_HashCode key GNUNET_PACKED;
176 /* put path (if tracked) */
185 struct PeerGetMessage
188 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
190 struct GNUNET_MessageHeader header;
195 uint32_t options GNUNET_PACKED;
198 * Desired content type.
200 uint32_t block_type GNUNET_PACKED;
205 uint32_t hop_count GNUNET_PACKED;
208 * Desired replication level for this request.
209 * In the current implementation, this value is not used.
211 uint32_t desired_replication_level GNUNET_PACKED;
214 * Total number of peers in get path.
216 unsigned int get_path_length;
219 * Best known destination (could be my friend or finger) which should
220 * get this message next.
222 struct GNUNET_PeerIdentity best_known_destination;
225 * In case best_known_destination is a finger, then trail to reach
226 * to that finger. Else its default value is 0.
228 struct GNUNET_HashCode intermediate_trail_id;
231 * The key we are looking for.
233 struct GNUNET_HashCode key;
236 /* struct GNUNET_PeerIdentity[]*/
242 struct PeerGetResultMessage
245 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
247 struct GNUNET_MessageHeader header;
250 * The type for the data.
252 uint32_t type GNUNET_PACKED;
255 * Number of peers recorded in the outgoing path from source to the
256 * stored location of this message.
258 uint32_t put_path_length GNUNET_PACKED;
261 * Length of the GET path that follows (if tracked).
263 uint32_t get_path_length GNUNET_PACKED;
266 * Peer which queried for get and should get the result.
268 struct GNUNET_PeerIdentity querying_peer;
271 * When does the content expire?
273 struct GNUNET_TIME_Absolute expiration_time;
276 * The key of the corresponding GET request.
278 struct GNUNET_HashCode key;
280 /* put path (if tracked) */
282 /* get path (if tracked) */
289 * P2P Trail setup message
291 struct PeerTrailSetupMessage
294 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
296 struct GNUNET_MessageHeader header;
299 * Is source_peer trying to setup the trail to a predecessor or any finger.
301 uint32_t is_predecessor;
304 * Peer closest to this value will be our finger.
306 uint64_t final_destination_finger_value;
309 * Source peer which wants to setup the trail to one of its finger.
311 struct GNUNET_PeerIdentity source_peer;
314 * Best known destination (could be my friend or finger) which should
315 * get this message next.
317 struct GNUNET_PeerIdentity best_known_destination;
320 * In case best_known_destination is a finger, then trail id of trail to
321 * reach to this finger.
323 struct GNUNET_HashCode intermediate_trail_id;
326 * Trail id for trail which we are trying to setup.
328 struct GNUNET_HashCode trail_id;
330 /* List of peers which are part of trail setup so far.
331 * Trail does NOT include source_peer and peer which will be closest to
332 * ultimate_destination_finger_value.
333 * struct GNUNET_PeerIdentity trail[]
338 * P2P Trail Setup Result message
340 struct PeerTrailSetupResultMessage
344 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
346 struct GNUNET_MessageHeader header;
349 * Finger to which we have found the path.
351 struct GNUNET_PeerIdentity finger_identity;
354 * Peer which started trail_setup to find trail to finger_identity
356 struct GNUNET_PeerIdentity querying_peer;
359 * Is the trail setup to querying_peer's predecessor or finger?
361 uint32_t is_predecessor;
364 * Value to which finger_identity is the closest peer.
366 uint64_t ulitmate_destination_finger_value;
369 * Identifier of the trail from querying peer to finger_identity, NOT
370 * including both endpoints.
372 struct GNUNET_HashCode trail_id;
374 /* List of peers which are part of the trail from querying peer to
375 * finger_identity, NOT including both endpoints.
376 * struct GNUNET_PeerIdentity trail[]
381 * P2P Verify Successor Message.
383 struct PeerVerifySuccessorMessage
386 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
388 struct GNUNET_MessageHeader header;
391 * Peer which wants to verify its successor.
393 struct GNUNET_PeerIdentity source_peer;
396 * Source Peer's current successor.
398 struct GNUNET_PeerIdentity successor;
401 * Identifier of trail to reach from source_peer to successor.
403 struct GNUNET_HashCode trail_id;
405 /* List of the peers which are part of trail to reach from source_peer
406 * to successor, NOT including them
407 * struct GNUNET_PeerIdentity trail[]
412 * P2P Verify Successor Result Message
414 struct PeerVerifySuccessorResultMessage
417 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
419 struct GNUNET_MessageHeader header;
422 * Peer which sent the request to verify its successor.
424 struct GNUNET_PeerIdentity querying_peer;
427 * Successor to which PeerVerifySuccessorMessage was sent.
429 struct GNUNET_PeerIdentity current_successor;
432 * Current Predecessor of source_successor. It can be same as querying peer
433 * or different. In case it is different then it can be querying_peer's
434 * probable successor.
436 struct GNUNET_PeerIdentity probable_successor;
439 * Trail identifier of trail from querying_peer to current_successor.
441 struct GNUNET_HashCode trail_id;
444 * Direction in which we are looking at the trail.
446 uint32_t trail_direction;
448 /* In case probable_successor != querying_peer, then trail to reach from
449 * querying_peer to probable_successor, NOT including end points.
450 * struct GNUNET_PeerIdentity trail[]
455 * P2P Notify New Successor Message.
457 struct PeerNotifyNewSuccessorMessage
460 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
462 struct GNUNET_MessageHeader header;
465 * Peer which wants to notify its new successor.
467 struct GNUNET_PeerIdentity source_peer;
470 * New successor of source_peer.
472 struct GNUNET_PeerIdentity new_successor;
475 * Unique identifier of the trail from source_peer to new_successor,
476 * NOT including the endpoints.
478 struct GNUNET_HashCode trail_id;
480 /* List of peers in trail from source_peer to new_successor,
481 * NOT including the endpoints.
482 * struct GNUNET_PeerIdentity trail[]
487 * P2P Trail Compression Message.
489 struct PeerTrailCompressionMessage
492 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION
494 struct GNUNET_MessageHeader header;
497 * Source peer of this trail.
499 struct GNUNET_PeerIdentity source_peer;
502 * Trail from source_peer to destination_peer compressed such that
503 * new_first_friend is the first hop in the trail from source to
506 struct GNUNET_PeerIdentity new_first_friend;
509 * Unique identifier of trail.
511 struct GNUNET_HashCode trail_id;
516 * P2P Trail Tear Down message.
518 struct PeerTrailTearDownMessage
521 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
523 struct GNUNET_MessageHeader header;
526 * Unique identifier of the trail.
528 struct GNUNET_HashCode trail_id;
531 * Direction of trail.
533 uint32_t trail_direction;
538 * P2P Trail Rejection Message.
540 struct PeerTrailRejectionMessage
543 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
545 struct GNUNET_MessageHeader header;
548 * Peer which wants to set up the trail.
550 struct GNUNET_PeerIdentity source_peer;
553 * Peer which sent trail rejection message as it it congested.
555 struct GNUNET_PeerIdentity congested_peer;
558 * Peer identity closest to this value will be finger of
561 uint64_t ultimate_destination_finger_value;
564 * Is source_peer trying to setup the trail to its predecessor or finger.
566 uint32_t is_predecessor;
569 * Identifier for the trail that source peer is trying to setup.
571 struct GNUNET_HashCode trail_id;
574 * Relative time for which congested_peer will remain congested.
576 struct GNUNET_TIME_Relative congestion_time;
578 /* Trail_list from source_peer to peer which sent the message for trail setup
579 * to congested peer. This trail does NOT include source_peer.
580 struct GNUNET_PeerIdnetity trail[]*/
584 * P2P Add Trail Message.
586 struct PeerAddTrailMessage
589 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
591 struct GNUNET_MessageHeader header;
594 * Source of the routing trail.
596 struct GNUNET_PeerIdentity source_peer;
599 * Destination of the routing trail.
601 struct GNUNET_PeerIdentity destination_peer;
604 * Unique identifier of the trail from source_peer to destination_peer,
605 * NOT including the endpoints.
607 struct GNUNET_HashCode trail_id;
609 /* Trail from source peer to destination peer, NOT including them.
610 * struct GNUNET_PeerIdentity trail[]
614 GNUNET_NETWORK_STRUCT_END
617 * Linked list of messages to send to a particular other peer.
619 struct P2PPendingMessage
622 * Pointer to next item in the list
624 struct P2PPendingMessage *next;
627 * Pointer to previous item in the list
629 struct P2PPendingMessage *prev;
632 * Message importance level. FIXME: used? useful?
634 unsigned int importance;
637 * When does this message time out?
639 struct GNUNET_TIME_Absolute timeout;
642 * Actual message to be sent, allocated at the end of the struct:
643 * // msg = (cast) &pm[1];
644 * // memcpy (&pm[1], data, len);
646 const struct GNUNET_MessageHeader *msg;
651 * Entry in friend_peermap.
658 struct GNUNET_PeerIdentity id;
661 * Number of trails for which this friend is the first hop or if the friend
664 unsigned int trails_count;
667 * Count of outstanding messages for this friend.
669 unsigned int pending_count;
672 * In case not 0, then amount of time for which this friend is congested.
674 struct GNUNET_TIME_Absolute congestion_timestamp;
677 * Head of pending messages to be sent to this friend.
679 struct P2PPendingMessage *head;
682 * Tail of pending messages to be sent to this friend.
684 struct P2PPendingMessage *tail;
687 * Core handle for sending messages to this friend.
689 struct GNUNET_CORE_TransmitHandle *th;
694 * An individual element of the trail to reach to a finger.
699 * Pointer to next item in the list
701 struct Trail_Element *next;
704 * Pointer to prev item in the list
706 struct Trail_Element *prev;
709 * An element in this trail.
711 struct GNUNET_PeerIdentity peer;
715 * FIXME: removed first_friend_trails_count, need to write a function
716 * to calculate each time we need it. Else, keep a pointer to first
717 * friend of in the trail.
718 * Information about an individual trail.
725 struct Trail_Element *trail_head;
730 struct Trail_Element *trail_tail;
733 * Unique identifier of this trail.
735 struct GNUNET_HashCode trail_id;
738 * Length of trail pointed
740 unsigned int trail_length;
743 * Is there a valid trail entry.
745 unsigned int is_present;
749 * An entry in finger_table
756 struct GNUNET_PeerIdentity finger_identity;
759 * Is any finger stored at this finger index.
761 unsigned int is_present;
764 * Index in finger peer map
766 uint32_t finger_table_index;
769 * Number of trails setup so far for this finger.
770 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
772 uint32_t trails_count;
775 * Array of trails to reach to this finger.
777 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
782 * Data structure to keep track of closest peer seen so far in find_successor()
787 * Destination finger value.
789 uint64_t destination_finger_value;
792 * Is finger_value a predecessor or any other finger.
794 unsigned int is_predecessor;
797 * Trail id to reach to peer.
798 * In case peer is my identity or friend, it is set to NULL.
800 struct GNUNET_HashCode *trail_id;
803 * Next destination. In case of friend and my_identity , it is same as next_hop
804 * In case of finger it is finger identity.
806 struct GNUNET_PeerIdentity best_known_destination;
809 * In case best_known_destination is a finger, then first friend in the trail
810 * to reach to it. In other case, same as best_known_destination.
812 struct GNUNET_PeerIdentity next_hop;
817 * Data structure to store the trail chosen to reach to finger.
819 struct Selected_Finger_Trail
822 * First friend in the trail to reach finger.
824 struct FriendInfo friend;
827 * Identifier of this trail.
829 struct GNUNET_HashCode *trail_id;
832 * Total number of peers in this trail.
834 unsigned int trail_length;
838 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
839 * get our first friend.
841 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
844 * Identity of this peer.
846 static struct GNUNET_PeerIdentity my_identity;
849 * Peer map of all the friends of a peer
851 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
854 * Array of all the fingers.
856 static struct FingerInfo finger_table [MAX_FINGERS];
861 static struct GNUNET_CORE_Handle *core_api;
864 * The current finger index that we have want to find trail to. We start the
865 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
866 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
867 * we reset this index to 0.
869 static unsigned int current_search_finger_index;
873 * Called when core is ready to send a message we asked for
874 * out to the destination.
876 * @param cls the 'struct FriendInfo' of the target friend
877 * @param size number of bytes available in buf
878 * @param buf where the callee should write the message
879 * @return number of bytes written to buf
882 core_transmit_notify (void *cls, size_t size, void *buf)
884 struct FriendInfo *peer = cls;
886 struct P2PPendingMessage *pending;
891 while ((NULL != (pending = peer->head)) &&
892 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
894 peer->pending_count--;
895 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
896 GNUNET_free (pending);
900 /* no messages pending */
906 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
907 GNUNET_CORE_PRIO_BEST_EFFORT,
908 GNUNET_TIME_absolute_get_remaining
909 (pending->timeout), &peer->id,
910 ntohs (pending->msg->size),
911 &core_transmit_notify, peer);
912 GNUNET_break (NULL != peer->th);
916 while ((NULL != (pending = peer->head)) &&
917 (size - off >= (msize = ntohs (pending->msg->size))))
919 /*GNUNET_STATISTICS_update (GDS_stats,
921 ("# Bytes transmitted to other peers"), msize,
923 memcpy (&cbuf[off], pending->msg, msize);
925 peer->pending_count--;
926 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
927 GNUNET_free (pending);
929 if (peer->head != NULL)
932 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
933 GNUNET_CORE_PRIO_BEST_EFFORT,
934 GNUNET_TIME_absolute_get_remaining
935 (pending->timeout), &peer->id, msize,
936 &core_transmit_notify, peer);
937 GNUNET_break (NULL != peer->th);
944 * Transmit all messages in the friend's message queue.
946 * @param peer message queue to process
949 process_friend_queue (struct FriendInfo *peer)
951 struct P2PPendingMessage *pending;
953 if (NULL == (pending = peer->head))
955 if (NULL != peer->th)
958 GNUNET_STATISTICS_update (GDS_stats,
960 ("# Bytes of bandwidth requested from core"),
961 ntohs (pending->msg->size), GNUNET_NO);
964 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
966 GNUNET_TIME_absolute_get_remaining
967 (pending->timeout), &peer->id,
968 ntohs (pending->msg->size),
969 &core_transmit_notify, peer);
970 GNUNET_break (NULL != peer->th);
975 * Return friend corresponding to peer.
980 GDS_NEIGHBOURS_get_friend (struct GNUNET_PeerIdentity peer)
982 struct FriendInfo *friend;
983 GNUNET_assert (NULL != (friend =
984 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
990 * Construct a trail setup message and forward it to target_friend
991 * @param source_peer Peer which wants to setup the trail
992 * @param ultimate_destination_finger_value Peer identity closest to this value
993 * will be finger to @a source_peer
994 * @param best_known_destination Best known destination (could be finger or friend)
995 * which should get this message. In case it is
996 * friend, then it is same as target_friend
997 * @param target_friend Friend to which message is forwarded now.
998 * @param trail_length Total number of peers in trail setup so far.
999 * @param trail_peer_list Trail setup so far
1000 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1001 * @param trail_id Unique identifier for the trail we are trying to setup.
1002 * @param intermediate_trail_id Trail id of intermediate trail to reach to
1003 * best_known_destination when its a finger. If not
1004 * used then set to 0.
1007 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1008 uint64_t ultimate_destination_finger_value,
1009 struct GNUNET_PeerIdentity best_known_destination,
1010 struct FriendInfo *target_friend,
1011 unsigned int trail_length,
1012 const struct GNUNET_PeerIdentity *trail_peer_list,
1013 unsigned int is_predecessor,
1014 struct GNUNET_HashCode trail_id,
1015 struct GNUNET_HashCode *intermediate_trail_id)
1017 struct P2PPendingMessage *pending;
1018 struct PeerTrailSetupMessage *tsm;
1019 struct GNUNET_PeerIdentity *peer_list;
1022 msize = sizeof (struct PeerTrailSetupMessage) +
1023 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1025 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1031 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1033 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1037 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1038 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1039 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1040 pending->msg = &tsm->header;
1041 tsm->header.size = htons (msize);
1042 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1043 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1044 tsm->source_peer = source_peer;
1045 tsm->best_known_destination = best_known_destination;
1046 tsm->is_predecessor = htonl (is_predecessor);
1047 tsm->trail_id = trail_id;
1049 if (NULL == intermediate_trail_id)
1050 memset (&tsm->intermediate_trail_id, 0, sizeof (tsm->intermediate_trail_id));
1052 tsm->intermediate_trail_id = *intermediate_trail_id;
1054 if (trail_length > 0)
1056 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1057 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1060 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1061 target_friend->pending_count++;
1062 process_friend_queue (target_friend);
1067 * Construct a trail setup result message and forward it to target friend.
1068 * @param querying_peer Peer which sent the trail setup request and should get
1070 * @param Finger Peer to which the trail has been setup to.
1071 * @param target_friend Friend to which this message should be forwarded.
1072 * @param trail_length Numbers of peers in the trail.
1073 * @param trail_peer_list Peers which are part of the trail from
1074 * querying_peer to Finger, NOT including them.
1075 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1076 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1078 * @param trail_id Unique identifier of the trail.
1081 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1082 struct GNUNET_PeerIdentity finger,
1083 struct FriendInfo *target_friend,
1084 unsigned int trail_length,
1085 const struct GNUNET_PeerIdentity *trail_peer_list,
1086 unsigned int is_predecessor,
1087 uint64_t ultimate_destination_finger_value,
1088 struct GNUNET_HashCode trail_id)
1090 struct P2PPendingMessage *pending;
1091 struct PeerTrailSetupResultMessage *tsrm;
1092 struct GNUNET_PeerIdentity *peer_list;
1095 msize = sizeof (struct PeerTrailSetupResultMessage) +
1096 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1098 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1104 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1106 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1110 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1111 pending->importance = 0;
1112 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1113 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1114 pending->msg = &tsrm->header;
1115 tsrm->header.size = htons (msize);
1116 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1117 tsrm->querying_peer = querying_peer;
1118 tsrm->finger_identity = finger;
1119 tsrm->is_predecessor = htonl (is_predecessor);
1120 tsrm->trail_id = trail_id;
1121 tsrm->ulitmate_destination_finger_value =
1122 GNUNET_htonll (ultimate_destination_finger_value);
1123 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1124 if (trail_length > 0)
1126 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1128 /* Send the message to chosen friend. */
1129 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1130 target_friend->pending_count++;
1131 process_friend_queue (target_friend);
1136 * Send trail rejection message to target friend
1137 * @param source_peer Peer which is trying to setup the trail.
1138 * @param ultimate_destination_finger_value Peer closest to this value will be
1139 * @a source_peer's finger
1140 * @param congested_peer Peer which sent this message as it is congested.
1141 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1142 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1143 * by congested_peer. This does NOT include @a source_peer
1144 * and congested_peer.
1145 * @param trail_length Total number of peers in trail_peer_list, NOT including
1146 * @a source_peer and @a congested_peer
1147 * @param trail_id Unique identifier of this trail.
1148 * @param congestion_timeout Duration given by congested peer as an estimate of
1149 * how long it may remain congested.
1152 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1153 uint64_t ultimate_destination_finger_value,
1154 struct GNUNET_PeerIdentity congested_peer,
1155 unsigned int is_predecessor,
1156 const struct GNUNET_PeerIdentity *trail_peer_list,
1157 unsigned int trail_length,
1158 struct GNUNET_HashCode trail_id,
1159 struct FriendInfo *target_friend,
1160 const struct GNUNET_TIME_Relative congestion_timeout)
1162 struct PeerTrailRejectionMessage *trm;
1163 struct P2PPendingMessage *pending;
1164 struct GNUNET_PeerIdentity *peer_list;
1167 msize = sizeof (struct PeerTrailRejectionMessage) +
1168 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1170 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1176 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1178 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1182 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1183 pending->importance = 0;
1184 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1185 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1186 pending->msg = &trm->header;
1187 trm->header.size = htons (msize);
1188 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1189 trm->source_peer = source_peer;
1190 trm->congested_peer = congested_peer;
1191 trm->congestion_time = congestion_timeout;
1192 trm->is_predecessor = htonl (is_predecessor);
1193 trm->trail_id = trail_id;
1194 trm->ultimate_destination_finger_value =
1195 GNUNET_htonll (ultimate_destination_finger_value);
1197 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1198 if (trail_length > 0)
1200 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1203 /* Send the message to chosen friend. */
1204 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1205 target_friend->pending_count++;
1206 process_friend_queue (target_friend);
1211 * Construct a verify successor message and forward it to target_friend.
1212 * @param source_peer Peer which wants to verify its successor.
1213 * @param successor Peer which is @a source_peer's current successor.
1214 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1215 * NOT including them.
1216 * @param trail List of peers which are part of trail to reach from @a source_peer
1217 * to @a successor, NOT including them.
1218 * @param trail_length Total number of peers in @a trail.
1219 * @param target_friend Next friend to get this message.
1222 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1223 struct GNUNET_PeerIdentity successor,
1224 struct GNUNET_HashCode trail_id,
1225 struct GNUNET_PeerIdentity *trail,
1226 unsigned int trail_length,
1227 struct FriendInfo *target_friend)
1229 struct PeerVerifySuccessorMessage *vsm;
1230 struct P2PPendingMessage *pending;
1231 struct GNUNET_PeerIdentity *peer_list;
1234 msize = sizeof (struct PeerVerifySuccessorMessage) +
1235 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1236 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1242 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1244 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1248 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1249 pending->importance = 0; /* FIXME */
1250 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1251 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1252 pending->msg = &vsm->header;
1253 vsm->header.size = htons (msize);
1254 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1255 vsm->source_peer = source_peer;
1256 vsm->successor = successor;
1257 vsm->trail_id = trail_id;
1259 if (trail_length != 0)
1261 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1262 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1265 /* Send the message to chosen friend. */
1266 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1267 target_friend->pending_count++;
1268 process_friend_queue (target_friend);
1273 * FIXME: In every function we pass target friend except for this one.
1274 * so, either change everything or this one. also, should se just store
1275 * the pointer to friend in routing table rather than gnunet_peeridentity.
1276 * if yes then we should keep friend info in.h andmake lot of changes.
1277 * Construct a trail teardown message and forward it to target friend.
1278 * @param trail_id Unique identifier of the trail.
1279 * @param trail_direction Direction of trail.
1280 * @param target_friend Friend to get this message.
1283 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1284 unsigned int trail_direction,
1285 struct GNUNET_PeerIdentity peer)
1287 struct PeerTrailTearDownMessage *ttdm;
1288 struct P2PPendingMessage *pending;
1289 struct FriendInfo *target_friend;
1292 msize = sizeof (struct PeerTrailTearDownMessage);
1294 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1300 /*FIXME:In what case friend can be null. ?*/
1301 if (NULL == (target_friend =
1302 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1305 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1307 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1311 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1312 pending->importance = 0; /* FIXME */
1313 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1314 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1315 pending->msg = &ttdm->header;
1316 ttdm->header.size = htons (msize);
1317 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1318 ttdm->trail_id = trail_id;
1319 ttdm->trail_direction = htonl (trail_direction);
1321 /* Send the message to chosen friend. */
1322 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1323 target_friend->pending_count++;
1324 process_friend_queue (target_friend);
1329 * Construct a verify successor result message and send it to target_friend
1330 * @param querying_peer Peer which sent the verify successor message.
1331 * @param source_successor Current_successor of @a querying_peer.
1332 * @param current_predecessor Current predecessor of @a successor. Could be same
1333 * or different from @a querying_peer.
1334 * @param trail_id Unique identifier of the trail from @a querying_peer to
1335 * @a successor, NOT including them.
1336 * @param trail List of peers which are part of trail from @a querying_peer to
1337 * @a successor, NOT including them.
1338 * @param trail_length Total number of peers in @a trail
1339 * @param trail_direction Direction in which we are sending the message. In this
1340 * case we are sending result from @a successor to @a querying_peer.
1341 * @param target_friend Next friend to get this message.
1344 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1345 struct GNUNET_PeerIdentity current_successor,
1346 struct GNUNET_PeerIdentity probable_successor,
1347 struct GNUNET_HashCode trail_id,
1348 const struct GNUNET_PeerIdentity *trail,
1349 unsigned int trail_length,
1350 enum GDS_ROUTING_trail_direction trail_direction,
1351 struct FriendInfo *target_friend)
1353 struct PeerVerifySuccessorResultMessage *vsmr;
1354 struct P2PPendingMessage *pending;
1355 struct GNUNET_PeerIdentity *peer_list;
1358 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1359 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1361 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1367 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1369 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1373 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1374 pending->importance = 0; /* FIXME */
1375 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1376 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1377 pending->msg = &vsmr->header;
1378 vsmr->header.size = htons (msize);
1379 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1380 vsmr->querying_peer = querying_peer;
1381 vsmr->current_successor = current_successor;
1382 vsmr->probable_successor = probable_successor;
1383 vsmr->trail_direction = htonl (trail_direction);
1384 vsmr->trail_id = trail_id;
1386 if (trail_length > 0)
1388 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1389 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1392 /* Send the message to chosen friend. */
1393 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1394 target_friend->pending_count++;
1395 process_friend_queue (target_friend);
1400 * Construct a notify new successor message and send it to target_friend
1401 * @param source_peer Peer which wants to notify to its new successor that it
1402 * could be its predecessor.
1403 * @param successor New successor of @a source_peer
1404 * @param successor_trail List of peers in Trail to reach from
1405 * @a source_peer to @a new_successor, NOT including
1407 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1408 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1409 * @param target_friend Next friend to get this message.
1412 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1413 struct GNUNET_PeerIdentity successor,
1414 const struct GNUNET_PeerIdentity *successor_trail,
1415 unsigned int successor_trail_length,
1416 struct GNUNET_HashCode succesor_trail_id,
1417 struct FriendInfo *target_friend)
1419 struct PeerNotifyNewSuccessorMessage *nsm;
1420 struct P2PPendingMessage *pending;
1421 struct GNUNET_PeerIdentity *peer_list;
1424 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1425 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1427 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1433 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1435 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1439 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1440 pending->importance = 0; /* FIXME */
1441 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1442 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1443 pending->msg = &nsm->header;
1444 nsm->header.size = htons (msize);
1445 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1446 nsm->new_successor = successor;
1447 nsm->source_peer = source_peer;
1448 nsm->trail_id = succesor_trail_id;
1450 if (successor_trail_length > 0)
1452 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1453 memcpy (peer_list, successor_trail,
1454 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1457 /* Send the message to chosen friend. */
1458 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1459 target_friend->pending_count++;
1460 process_friend_queue (target_friend);
1465 * Construct an add_trail message and send it to target_friend
1466 * @param source_peer Source of the trail.
1467 * @param destination_peer Destination of the trail.
1468 * @param trail_id Unique identifier of the trail from
1469 * @a source_peer to @a destination_peer, NOT including the endpoints.
1470 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1471 * NOT including the endpoints.
1472 * @param trail_length Total number of peers in @a trail.
1473 * @param target_friend Next friend to get this message.
1476 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1477 struct GNUNET_PeerIdentity destination_peer,
1478 struct GNUNET_HashCode trail_id,
1479 const struct GNUNET_PeerIdentity *trail,
1480 unsigned int trail_length,
1481 struct FriendInfo *target_friend)
1483 struct PeerAddTrailMessage *adm;
1484 struct GNUNET_PeerIdentity *peer_list;
1485 struct P2PPendingMessage *pending;
1488 msize = sizeof (struct PeerAddTrailMessage) +
1489 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1491 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1497 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1499 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1503 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1504 pending->importance = 0; /* FIXME */
1505 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1506 adm = (struct PeerAddTrailMessage *) &pending[1];
1507 pending->msg = &adm->header;
1508 adm->header.size = htons (msize);
1509 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1510 adm->source_peer = source_peer;
1511 adm->destination_peer = destination_peer;
1512 adm->trail_id = trail_id;
1514 if (trail_length > 0)
1516 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1517 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1519 /* Send the message to chosen friend. */
1520 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1521 target_friend->pending_count++;
1522 process_friend_queue (target_friend);
1528 * Construct a trail compression message and send it to target_friend.
1529 * @param source_peer Source of the trail.
1530 * @param trail_id Unique identifier of trail.
1531 * @param first_friend First hop in compressed trail to reach from source to finger
1532 * @param target_friend Next friend to get this message.
1535 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1536 struct GNUNET_HashCode trail_id,
1537 struct GNUNET_PeerIdentity first_friend,
1538 struct FriendInfo *target_friend)
1540 struct P2PPendingMessage *pending;
1541 struct PeerTrailCompressionMessage *tcm;
1544 msize = sizeof (struct PeerTrailCompressionMessage);
1546 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1552 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1554 GNUNET_STATISTICS_update (GDS_stats,
1555 gettext_noop ("# P2P messages dropped due to full queue"),
1559 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1560 pending->importance = 0; /* FIXME */
1561 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1562 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1563 pending->msg = &tcm->header;
1564 tcm->header.size = htons (msize);
1565 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1566 tcm->source_peer = source_peer;
1567 tcm->new_first_friend = first_friend;
1568 tcm->trail_id = trail_id;
1570 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1571 target_friend->pending_count++;
1572 process_friend_queue (target_friend);
1578 * Search my location in trail. In case I am present more than once in the
1579 * trail (can happen during trail setup), then return my lowest index.
1580 * @param trail List of peers
1581 * @return my_index if found
1582 * -1 if no entry found.
1585 search_my_index (const struct GNUNET_PeerIdentity *trail,
1589 int lowest_index = -1;
1591 for (i = 0; i < trail_length; i++)
1593 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1597 return lowest_index;
1602 * Check if the friend is congested or have reached maximum number of trails
1603 * it can be part of of.
1604 * @param friend Friend to be checked.
1605 * @return #GNUNET_YES if friend is not congested or have not crossed threshold.
1606 * #GNUNET_NO if friend is either congested or have crossed threshold
1609 is_friend_congested (struct FriendInfo *friend)
1611 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
1612 ((0 == GNUNET_TIME_absolute_get_remaining
1613 (friend->congestion_timestamp).rel_value_us)))
1621 * FIXME; not handling the wrap around logic correctly.
1622 * Select closest finger to value.
1623 * @param peer1 First peer
1624 * @param peer2 Second peer
1625 * @param value Value to be compare
1626 * @return Closest peer
1628 static struct GNUNET_PeerIdentity *
1629 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1630 struct GNUNET_PeerIdentity *peer2,
1633 uint64_t peer1_value;
1634 uint64_t peer2_value;
1636 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1637 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1638 peer1_value = GNUNET_ntohll (peer1_value);
1639 peer2_value = GNUNET_ntohll (peer2_value);
1640 //value = GNUNET_ntohll (value); //FIXME: Is it correct to do it here?
1642 if (peer1_value == value)
1647 if (peer2_value == value)
1652 if (peer2_value < peer1_value)
1654 if ((peer2_value < value) && (value < peer1_value))
1658 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1659 ((0 < value) && (value < peer2_value)))
1665 if (peer1_value < peer2_value)
1667 if ((peer1_value < value) && (value < peer2_value))
1671 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1672 ((0 < value) && (value < peer1_value)))
1682 * Select closest predecessor to value.
1683 * @param peer1 First peer
1684 * @param peer2 Second peer
1685 * @param value Value to be compare
1686 * @return Peer which precedes value in the network.
1688 static struct GNUNET_PeerIdentity *
1689 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1690 struct GNUNET_PeerIdentity *peer2,
1693 uint64_t peer1_value;
1694 uint64_t peer2_value;
1696 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1697 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1698 peer1_value = GNUNET_ntohll (peer1_value);
1699 peer2_value = GNUNET_ntohll (peer2_value);
1701 if (peer1_value == value)
1704 if (peer2_value == value)
1707 if (peer1_value < peer2_value)
1709 if ((peer1_value < value) && (value < peer2_value))
1711 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1712 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1716 if (peer2_value < peer1_value)
1718 if ((peer2_value < value) && (value < peer1_value))
1720 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1721 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1729 * This is a test function to print all the entries of friend table.
1732 test_friend_peermap_print ()
1734 struct FriendInfo *friend;
1735 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1736 struct GNUNET_PeerIdentity print_peer;
1737 struct GNUNET_PeerIdentity key_ret;
1740 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1742 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1744 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1746 (const void **)&friend))
1748 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1749 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1750 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1756 * This is a test function, to print all the entries of finger table.
1759 test_finger_table_print()
1761 struct FingerInfo *finger;
1762 struct GNUNET_PeerIdentity print_peer;
1763 struct Trail *trail;
1768 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE"));
1769 for (i = 0; i < MAX_FINGERS; i++)
1771 finger = &finger_table[i];
1773 if (GNUNET_NO == finger->is_present)
1776 print_peer = finger->finger_identity;
1777 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1778 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1781 for (j = 0; j < finger->trails_count; j++)
1783 trail = &finger->trail_list[j];
1784 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1785 struct Trail_Element *element;
1786 element = trail->trail_head;
1787 for (k = 0; k < trail->trail_length; k++)
1789 print_peer = element->peer;
1790 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1791 element = element->next;
1799 * Select the closest peer among two peers (which should not be same)
1800 * with respect to value and finger_table_index
1801 * NOTE: peer1 != peer2
1802 * @param peer1 First peer
1803 * @param peer2 Second peer
1804 * @param value Value relative to which we find the closest
1805 * @param is_predecessor Is value a predecessor or any other finger.
1806 * @return Closest peer among two peers.
1808 static struct GNUNET_PeerIdentity *
1809 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1810 struct GNUNET_PeerIdentity *peer2,
1812 unsigned int is_predecessor)
1814 struct GNUNET_PeerIdentity *closest_peer;
1816 if (1 == is_predecessor)
1818 closest_peer = select_closest_predecessor (peer1, peer2, value);
1822 closest_peer = select_closest_finger (peer1, peer2, value);
1824 return closest_peer;
1829 * Iterate over the list of all the trails of a finger. In case the first
1830 * friend to reach the finger has reached trail threshold or is congested,
1831 * then don't select it. In case there multiple available good trails to reach
1832 * to Finger, choose the one with shortest trail length.
1833 * Note: We use length as parameter. But we can use any other suitable parameter
1835 * @param finger Finger
1836 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1837 * and trail length. NULL in case none of the trails are free.
1839 static struct Selected_Finger_Trail *
1840 select_finger_trail (struct FingerInfo *finger)
1842 struct FriendInfo *friend;
1843 struct Trail *iterator;
1844 struct Selected_Finger_Trail *finger_trail;
1846 unsigned int flag = 0;
1849 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1851 /* It can never happen that we have a finger (which is not a friend or my identity),
1852 and we don't have a trail to reach to it. */
1853 GNUNET_assert (finger->trails_count > 0);
1855 for (i = 0; i < finger->trails_count; i++)
1857 iterator = &finger->trail_list[i];
1859 /* No trail stored at this index. */
1860 if (GNUNET_NO == iterator->is_present)
1865 GNUNET_assert (NULL !=
1867 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1868 &iterator->trail_head->peer)));
1870 /* First friend to reach trail is not free. */
1871 if (GNUNET_YES == is_friend_congested (friend))
1876 /* This is the first time we enter the loop. Set finger trail length to
1877 * trail length of this trail. */
1881 finger_trail->trail_length = iterator->trail_length;
1882 finger_trail->friend = *friend;
1883 finger_trail->trail_id = &iterator->trail_id;
1884 //memcmp (finger_trail->trail_id, &iterator->trail_id, sizeof (struct GNUNET_HashCode));
1886 else if (finger_trail->trail_length > iterator->trail_length)
1888 /* Check if the trail length of this trail is least seen so far. If yes then
1889 set finger_trail to this trail.*/
1890 finger_trail->friend = *friend;
1891 finger_trail->trail_id = &iterator->trail_id;
1892 //memcmp (finger_trail->trail_id, &iterator->trail_id, sizeof (struct GNUNET_HashCode));
1893 finger_trail->trail_length = iterator->trail_length;
1897 /* All the first friend in all the trails to reach to finger are either
1898 congested or have crossed trail threshold. */
1899 if (j == finger->trails_count)
1902 return finger_trail;
1910 * Compare FINGER entry with current successor. If finger's first friend of all
1911 * its trail is not congested and has not crossed trail threshold, then check
1912 * if finger peer identity is closer to final_destination_finger_value than
1913 * current_successor. If yes then update current_successor.
1914 * @param current_successor[in/out]
1918 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1920 struct FingerInfo *finger;
1921 struct GNUNET_PeerIdentity *closest_peer;
1922 struct Selected_Finger_Trail *finger_trail;
1925 /* Iterate over finger table. */
1926 for (i = 0; i < MAX_FINGERS; i++)
1928 finger = &finger_table[i];
1930 /* No valid entry at this index, go to next element.*/
1931 if (GNUNET_NO == finger->is_present)
1934 /* If my identity is same as current closest peer then don't consider me*/
1936 GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1937 ¤t_closest_peer->best_known_destination))
1940 /* If I am my own finger, then ignore this finger. */
1941 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1945 /* If finger is a friend, then do nothing. As we have already checked
1946 * for each friend in compare_friend_and_current_successor(). */
1947 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1948 &finger->finger_identity)))
1952 /* We have a finger which not a friend, not my identity */
1953 /* Choose one of the trail to reach to finger. */
1954 finger_trail = select_finger_trail (finger);
1956 /* In case no trail found, ignore this finger. */
1957 if (NULL == finger_trail)
1960 closest_peer = select_closest_peer (&finger->finger_identity,
1961 ¤t_closest_peer->best_known_destination,
1962 current_closest_peer->destination_finger_value,
1963 current_closest_peer->is_predecessor);
1965 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1968 current_closest_peer->best_known_destination = finger->finger_identity;
1969 current_closest_peer->next_hop = finger_trail->friend.id;
1970 current_closest_peer->trail_id = finger_trail->trail_id;
1978 * Compare friend entry with current successor.
1979 * If friend identity and current_successor is same, then do nothing.
1980 * If friend is not congested and has not crossed trail threshold, then check
1981 * if friend peer identity is closer to final_destination_finger_value than
1982 * current_successor. If yes then update current_successor.
1983 * @param cls closure
1984 * @param key current public key
1985 * @param value struct Closest_Peer
1986 * @return #GNUNET_YES if we should continue to iterate,
1987 * #GNUNET_NO if not.
1990 compare_friend_and_current_closest_peer (void *cls,
1991 const struct GNUNET_PeerIdentity *key,
1994 struct FriendInfo *friend = value;
1995 struct Closest_Peer *current_closest_peer = cls;
1996 struct GNUNET_PeerIdentity *closest_peer;
1998 /* If friend is either congested or has crossed threshold, then don't consider
2000 if (GNUNET_YES == is_friend_congested (friend))
2003 /* If current_closest_peer and friend identity are same, then do nothing.*/
2005 GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2006 ¤t_closest_peer->best_known_destination))
2009 closest_peer = select_closest_peer (&friend->id,
2010 ¤t_closest_peer->best_known_destination,
2011 current_closest_peer->destination_finger_value,
2012 current_closest_peer->is_predecessor);
2014 /* Is friend the closest successor? */
2015 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id, closest_peer))
2017 current_closest_peer->best_known_destination = friend->id;
2018 current_closest_peer->next_hop = friend->id;
2026 * Initialize current_successor to my_identity.
2027 * @param my_identity My peer identity
2028 * @return current_successor
2030 static struct Closest_Peer *
2031 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2032 uint64_t destination_finger_value,
2033 unsigned int is_predecessor)
2035 struct Closest_Peer *current_closest_peer;
2037 current_closest_peer = GNUNET_new (struct Closest_Peer);
2038 //memset (¤t_closest_peer->trail_id, 0, sizeof (current_closest_peer->trail_id));
2039 current_closest_peer->trail_id = NULL;
2040 current_closest_peer->destination_finger_value = destination_finger_value;
2041 current_closest_peer->is_predecessor = is_predecessor;
2042 current_closest_peer->next_hop = my_identity;
2043 current_closest_peer->best_known_destination = my_identity;
2045 return current_closest_peer;
2050 * Find the successor for destination_finger_value among my_identity, all my
2051 * friend and all my fingers. Don't consider friends or fingers which are either
2052 * congested or have crossed the threshold.
2053 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2055 * @param destination_finger_value Peer closest to this value will be the next successor.
2056 * @param local_best_known_destination[out] Updated to my_identity if I am the
2057 * final destination. Updated to friend
2058 * identity in case a friend is successor,
2059 * updated to finger in case finger is the
2061 * @param new_intermediate_trail_id[out] In case a finger is the
2062 * @a local_best_known_destination,
2063 * then it is the trail to reach it. Else
2065 * @param is_predecessor Are we looking for predecessor or finger?
2066 * @return Next hop to reach to local_best_known_destination. In case my_identity
2067 * or a friend is a local_best_known_destination, then
2068 * next_hop = local_best_known_destination. Else
2069 * next_hop is the first friend to reach to finger (local_best_known_destination)
2071 static struct GNUNET_PeerIdentity *
2072 find_successor (uint64_t destination_finger_value,
2073 struct GNUNET_PeerIdentity *local_best_known_destination,
2074 struct GNUNET_HashCode *new_intermediate_trail_id,
2075 unsigned int is_predecessor)
2077 struct Closest_Peer *current_closest_peer;
2078 struct GNUNET_PeerIdentity *next_hop;
2080 /* Initialize current_successor to my_identity. */
2081 current_closest_peer = init_current_successor (my_identity,
2082 destination_finger_value,
2084 /* Compare each friend entry with current_successor and update current_successor
2085 * with friend if its closest. */
2088 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2089 &compare_friend_and_current_closest_peer,
2090 current_closest_peer));
2092 /* Compare each finger entry with current_successor and update current_successor
2093 * with finger if its closest. */
2094 compare_finger_and_current_successor (current_closest_peer);
2095 *local_best_known_destination = current_closest_peer->best_known_destination;
2096 if (current_closest_peer->trail_id != NULL)
2098 /* FIXME I was assigning values but if address is NULL, then how do we assing. */
2099 memcpy (new_intermediate_trail_id,current_closest_peer->trail_id,sizeof (struct GNUNET_HashCode));
2102 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
2103 *next_hop = current_closest_peer->next_hop;
2112 * Construct a Put message and send it to target_peer.
2113 * @param key Key for the content
2114 * @param block_type Type of the block
2115 * @param options Routing options
2116 * @param desired_replication_level Desired replication count
2117 * @param best_known_dest Peer to which this message should reach eventually,
2118 * as it is best known destination to me.
2119 * @param intermediate_trail_id Trail id in case
2120 * @param target_peer Peer to which this message will be forwarded.
2121 * @param hop_count Number of hops traversed so far.
2122 * @param put_path_length Total number of peers in @a put_path
2123 * @param put_path Number of peers traversed so far
2124 * @param expiration_time When does the content expire
2125 * @param data Content to store
2126 * @param data_size Size of content @a data in bytes
2129 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2130 enum GNUNET_BLOCK_Type block_type,
2131 enum GNUNET_DHT_RouteOption options,
2132 uint32_t desired_replication_level,
2133 struct GNUNET_PeerIdentity *best_known_dest,
2134 struct GNUNET_HashCode *intermediate_trail_id,
2135 struct GNUNET_PeerIdentity *target_peer,
2137 uint32_t put_path_length,
2138 struct GNUNET_PeerIdentity *put_path,
2139 struct GNUNET_TIME_Absolute expiration_time,
2140 const void *data, size_t data_size)
2142 struct PeerPutMessage *ppm;
2143 struct P2PPendingMessage *pending;
2144 struct FriendInfo *target_friend;
2145 struct GNUNET_PeerIdentity *pp;
2146 struct GNUNET_PeerIdentity local_best_known_dest;
2149 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2150 sizeof (struct PeerPutMessage);
2152 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2154 put_path_length = 0;
2155 msize = data_size + sizeof (struct PeerPutMessage);
2158 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2164 /* This is the first call made from clients file. So, we should search for the
2166 if (NULL == target_peer)
2169 struct GNUNET_PeerIdentity *next_hop;
2171 memcpy (&key_value, key, sizeof (uint64_t));
2172 key_value = GNUNET_ntohll (key_value);
2174 next_hop = find_successor (key_value, &local_best_known_dest,
2175 intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
2176 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&local_best_known_dest, &my_identity))
2178 /* I am the destination but we have already done datacache_put in client file. */
2182 GNUNET_assert (NULL !=
2183 (target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
2184 GNUNET_free (next_hop);
2188 GNUNET_assert (NULL !=
2190 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2193 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2194 pending->timeout = expiration_time;
2195 ppm = (struct PeerPutMessage *) &pending[1];
2196 pending->msg = &ppm->header;
2197 ppm->header.size = htons (msize);
2198 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2199 ppm->options = htonl (options);
2200 ppm->block_type = htonl (block_type);
2201 ppm->hop_count = htonl (hop_count + 1);
2202 ppm->desired_replication_level = htonl (desired_replication_level);
2203 ppm->put_path_length = htonl (put_path_length);
2204 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2205 if (NULL == best_known_dest)
2206 ppm->best_known_destination = local_best_known_dest;
2208 ppm->best_known_destination = *best_known_dest;
2210 if (NULL == intermediate_trail_id)
2211 memset (&ppm->intermediate_trail_id, 0, sizeof (ppm->intermediate_trail_id));
2213 ppm->intermediate_trail_id = *intermediate_trail_id;
2214 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2215 if (put_path_length != 0)
2217 memcpy (pp, put_path,
2218 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2220 memcpy (&pp[put_path_length], data, data_size);
2222 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2223 target_friend->pending_count++;
2224 process_friend_queue (target_friend);
2229 * Construct a Get message and send it to target_peer.
2230 * @param key Key for the content
2231 * @param block_type Type of the block
2232 * @param options Routing options
2233 * @param desired_replication_level Desired replication count
2234 * @param best_known_dest Peer which should get this message. Same as target peer
2235 * if best_known_dest is a friend else its a finger.
2236 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2237 * in case it is a finger else set to 0.
2238 * @param target_peer Peer to which this message will be forwarded.
2239 * @param hop_count Number of hops traversed so far.
2240 * @param data Content to store
2241 * @param data_size Size of content @a data in bytes
2242 * @param get_path_length Total number of peers in @a get_path
2243 * @param get_path Number of peers traversed so far
2246 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2247 enum GNUNET_BLOCK_Type block_type,
2248 enum GNUNET_DHT_RouteOption options,
2249 uint32_t desired_replication_level,
2250 const struct GNUNET_PeerIdentity *best_known_dest,
2251 struct GNUNET_HashCode *intermediate_trail_id,
2252 struct GNUNET_PeerIdentity *target_peer,
2254 uint32_t get_path_length,
2255 struct GNUNET_PeerIdentity *get_path)
2257 struct PeerGetMessage *pgm;
2258 struct P2PPendingMessage *pending;
2259 struct FriendInfo *target_friend;
2260 struct GNUNET_PeerIdentity local_best_known_dest;
2261 struct GNUNET_PeerIdentity *gp;
2264 msize = sizeof (struct PeerGetMessage) +
2265 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2267 /* In this case we don't make get_path_length = 0, as we need get path to
2268 * return the message back to querying client. */
2269 if (msize > GNUNET_SERVER_MAX_MESSAGE_SIZE)
2274 //test_friend_peermap_print();
2275 //test_finger_table_print();
2277 /* This is the first time we got request from our own client file. */
2278 if (NULL == target_peer)
2280 struct GNUNET_PeerIdentity *next_hop;
2283 memcpy (&key_value, key, sizeof (uint64_t));
2284 key_value = GNUNET_ntohll (key_value);
2286 /* Find the next destination to forward the packet. */
2287 next_hop = find_successor (key_value, &local_best_known_dest,
2288 intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
2290 /* I am the destination. I have the data. */
2291 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2292 &local_best_known_dest))
2294 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2295 NULL, 0, 1, &my_identity, NULL,&my_identity);
2301 GNUNET_assert (NULL !=
2303 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
2305 GNUNET_free (next_hop);
2309 local_best_known_dest = *best_known_dest;
2310 GNUNET_assert (NULL !=
2312 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2315 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2316 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2317 pending->importance = 0; /* FIXME */
2318 pgm = (struct PeerGetMessage *) &pending[1];
2319 pending->msg = &pgm->header;
2320 pgm->header.size = htons (msize);
2321 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2322 pgm->get_path_length = htonl (get_path_length);
2323 pgm->best_known_destination = local_best_known_dest;
2326 if (NULL == intermediate_trail_id)
2327 memset ((void *)&pgm->intermediate_trail_id, 0, sizeof (pgm->intermediate_trail_id));
2329 pgm->intermediate_trail_id = *intermediate_trail_id;
2330 pgm->hop_count = htonl (hop_count + 1);
2331 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2333 if (get_path_length != 0)
2335 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2338 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2339 target_friend->pending_count++;
2340 process_friend_queue (target_friend);
2345 * Send the get result to requesting client.
2346 * @param key Key of the requested data.
2347 * @param type Block type
2348 * @param target_peer Next peer to forward the message to.
2349 * @param source_peer Peer which has the data for the key.
2350 * @param put_path_length Number of peers in @a put_path
2351 * @param put_path Path taken to put the data at its stored location.
2352 * @param get_path_length Number of peers in @a get_path
2353 * @param get_path Path taken to reach to the location of the key.
2354 * @param expiration When will this result expire?
2355 * @param data Payload to store
2356 * @param data_size Size of the @a data
2359 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2360 enum GNUNET_BLOCK_Type type,
2361 const struct GNUNET_PeerIdentity *target_peer,
2362 const struct GNUNET_PeerIdentity *source_peer,
2363 unsigned int put_path_length,
2364 const struct GNUNET_PeerIdentity *put_path,
2365 unsigned int get_path_length,
2366 const struct GNUNET_PeerIdentity *get_path,
2367 struct GNUNET_TIME_Absolute expiration,
2368 const void *data, size_t data_size)
2370 struct PeerGetResultMessage *get_result;
2371 struct GNUNET_PeerIdentity *paths;
2372 struct P2PPendingMessage *pending;
2373 struct FriendInfo *target_friend;
2374 int current_path_index;
2377 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2379 sizeof (struct PeerGetResultMessage);
2381 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2387 current_path_index = 0;
2388 if(get_path_length > 0)
2390 current_path_index = search_my_index(get_path, get_path_length);
2391 if (-1 == current_path_index)
2397 if (0 == current_path_index)
2399 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2400 get_path, put_path_length,
2401 put_path, type, data_size, data);
2405 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2406 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2407 pending->importance = 0;
2408 get_result = (struct PeerGetResultMessage *)&pending[1];
2409 pending->msg = &get_result->header;
2410 get_result->header.size = htons (msize);
2411 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2412 get_result->key = *key;
2413 get_result->querying_peer = *source_peer;
2414 get_result->expiration_time = expiration;
2415 get_result->get_path_length = htonl (get_path_length);
2416 get_result->put_path_length = htonl (put_path_length);
2417 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2418 memcpy (paths, put_path,
2419 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2420 memcpy (&paths[put_path_length], get_path,
2421 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2422 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2424 GNUNET_assert (NULL !=
2426 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2427 &get_path[current_path_index - 1])));
2428 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2429 target_friend->pending_count++;
2430 process_friend_queue (target_friend);
2435 * Randomly choose one of your friends (which is not congested and have not crossed
2436 * trail threshold) from the friends_peer map
2437 * @return Friend Randomly chosen friend.
2438 * NULL in case friend peermap is empty, or all the friends are either
2439 * congested or have crossed trail threshold.
2441 static struct FriendInfo *
2442 select_random_friend ()
2444 unsigned int current_size;
2447 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2448 struct GNUNET_PeerIdentity key_ret;
2449 struct FriendInfo *friend;
2451 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2454 if (0 == current_size)
2457 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2458 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2460 /* Iterate till you don't reach to index. */
2461 for (j = 0; j < index ; j++)
2462 GNUNET_assert (GNUNET_YES ==
2463 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2466 /* Reset the index in friend peermap to 0 as we reached to the end. */
2467 if (j == current_size)
2470 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2471 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2475 /* Get the friend stored at the index, j*/
2476 GNUNET_assert (GNUNET_YES ==
2477 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2479 (const void **)&friend));
2481 /* This friend is not congested and has not crossed trail threshold. */
2482 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2483 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2489 } while (j != index);
2491 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2497 * Compute 64 bit value of finger_identity corresponding to a finger index using
2500 * n.finger[i] = n + pow (2,i),
2502 * n.finger[i] = n - 1, where
2505 * n.finger[i] = 64 bit finger value
2506 * @param finger_index Index corresponding to which we calculate 64 bit value.
2507 * @return 64 bit value.
2510 compute_finger_identity_value (unsigned int finger_index)
2514 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2515 my_id64 = GNUNET_ntohll (my_id64);
2517 /* Are we looking for immediate predecessor? */
2518 if (PREDECESSOR_FINGER_ID == finger_index)
2519 return (my_id64 -1);
2521 return (my_id64 + (unsigned long) pow (2, finger_index));
2526 * Choose a random friend. Start looking for the trail to reach to
2527 * finger identity corresponding to current_search_finger_index through
2528 * this random friend.
2530 * @param cls closure for this task
2531 * @param tc the context under which the task is running
2534 send_find_finger_trail_message (void *cls,
2535 const struct GNUNET_SCHEDULER_TaskContext *tc)
2537 struct FriendInfo *target_friend;
2538 struct GNUNET_TIME_Relative next_send_time;
2539 struct GNUNET_HashCode trail_id;
2540 unsigned int is_predecessor;
2541 uint64_t finger_id_value;
2543 /* Schedule another send_find_finger_trail_message task. */
2544 next_send_time.rel_value_us =
2545 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
2546 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2547 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2548 find_finger_trail_task =
2549 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
2552 /* No space in my routing table. (Source and destination peers also store entries
2553 * in their routing table). */
2554 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2557 target_friend = select_random_friend ();
2558 if (NULL == target_friend)
2563 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2564 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2569 /* Generate a unique trail id for trail we are trying to setup. */
2570 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2571 &trail_id, sizeof (trail_id));
2572 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2573 target_friend->id, target_friend, 0, NULL,
2574 is_predecessor, trail_id, NULL);
2579 * In case there are already maximum number of possible trails to reach to a
2580 * finger, then check if the new trail's length is lesser than any of the
2582 * If yes then replace that old trail by new trail.
2584 * Note: Here we are taking length as a parameter to choose the best possible
2585 * trail, but there could be other parameters also like:
2586 * 1. duration of existence of a trail - older the better.
2587 * 2. if the new trail is completely disjoint than the
2588 * other trails, then may be choosing it is better.
2590 * @param existing_finger
2591 * @param new_finger_trail
2592 * @param new_finger_trail_length
2593 * @param new_finger_trail_id
2596 select_and_replace_trail (struct FingerInfo *existing_finger,
2597 const struct GNUNET_PeerIdentity *new_trail,
2598 unsigned int new_trail_length,
2599 struct GNUNET_HashCode new_trail_id)
2601 struct Trail *trail_list_iterator;
2602 unsigned int largest_trail_length;
2603 unsigned int largest_trail_index;
2604 struct Trail_Element *trail_element;
2607 largest_trail_length = new_trail_length;
2608 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2610 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2612 for (i = 0; i < existing_finger->trails_count; i++)
2614 trail_list_iterator = &existing_finger->trail_list[i];
2615 if (trail_list_iterator->trail_length > largest_trail_length)
2617 largest_trail_length = trail_list_iterator->trail_length;
2618 largest_trail_index = i;
2622 /* New trail is not better than existing ones. Send trail teardown. */
2623 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2625 struct GNUNET_PeerIdentity next_hop;
2627 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2628 GDS_ROUTING_remove_trail (new_trail_id);
2629 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2630 GDS_ROUTING_SRC_TO_DEST,
2635 /* Send trail teardown message across the replaced trail. */
2636 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2637 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2638 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2639 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2640 GDS_ROUTING_SRC_TO_DEST,
2641 replace_trail->trail_head->peer);
2642 /* Free the trail. */
2643 while (NULL != (trail_element = replace_trail->trail_head))
2645 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2646 replace_trail->trail_tail, trail_element);
2647 GNUNET_free_non_null (trail_element);
2650 /* Add new trial at that location. */
2651 replace_trail->is_present = GNUNET_YES;
2652 replace_trail->trail_length = new_trail_length;
2653 replace_trail->trail_id = new_trail_id;
2654 //FIXME: Do we need to add pointers for head and tail.
2656 while (i < new_trail_length)
2658 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2659 element->peer = new_trail[i];
2661 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2662 replace_trail->trail_tail,
2669 * Check if the new trail to reach to finger is unique or do we already have
2670 * such a trail present for finger.
2671 * @param existing_finger Finger identity
2672 * @param new_trail New trail to reach @a existing_finger
2673 * @param trail_length Total number of peers in new_trail.
2674 * @return #GNUNET_YES if the new trail is unique
2675 * #GNUNET_NO if same trail is already present.
2678 is_new_trail_unique (struct FingerInfo *existing_finger,
2679 const struct GNUNET_PeerIdentity *new_trail,
2680 unsigned int trail_length)
2682 struct Trail *trail_list_iterator;
2683 struct Trail_Element *trail_element;
2686 int trail_unique = GNUNET_NO;
2688 GNUNET_assert (existing_finger->trails_count > 0);
2690 /* Iterate over list of trails. */
2691 for (i = 0; i < existing_finger->trails_count; i++)
2693 trail_list_iterator = &existing_finger->trail_list[i];
2694 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2696 /* New trail and existing trail length are not same. */
2697 if (trail_list_iterator->trail_length != trail_length)
2699 trail_unique = GNUNET_YES;
2703 trail_element = trail_list_iterator->trail_head;
2704 for (j = 0; j < trail_list_iterator->trail_length; j++)
2706 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2707 &trail_element->peer))
2709 trail_unique = GNUNET_YES;
2712 trail_element = trail_element->next;
2715 trail_unique = GNUNET_NO;
2718 return trail_unique;
2723 * Add a new trail to existing finger. This function is called only when finger
2724 * is not my own identity or a friend.
2725 * @param existing_finger Finger
2726 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2727 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2728 * @param new_finger_trail_id Unique identifier of the trail.
2731 add_new_trail (struct FingerInfo *existing_finger,
2732 const struct GNUNET_PeerIdentity *new_trail,
2733 unsigned int new_trail_length,
2734 struct GNUNET_HashCode new_trail_id)
2736 struct Trail *trail_list_iterator;
2737 struct FriendInfo *first_friend;
2740 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2746 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2747 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2748 trail_list_iterator->trail_id = new_trail_id;
2749 trail_list_iterator->trail_length = new_trail_length;
2750 existing_finger->trails_count++;
2751 trail_list_iterator->is_present = GNUNET_YES;
2753 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2754 &existing_finger->finger_identity)));
2755 /* If finger is a friend then we never call this function. */
2756 GNUNET_assert (new_trail_length > 0);
2758 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2760 first_friend->trails_count++;
2762 for (i = 0; i < new_trail_length; i++)
2764 struct Trail_Element *element;
2766 element = GNUNET_new (struct Trail_Element);
2767 element->peer = new_trail[i];
2768 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2769 trail_list_iterator->trail_tail,
2772 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2778 * FIXME Check if this function is called for opposite direction if yes then
2779 * take it as parameter.
2780 * Get the next hop to send trail teardown message from routing table and
2781 * then delete the entry from routing table. Send trail teardown message for a
2782 * specific trail of a finger.
2783 * @param finger Finger whose trail is to be removed.
2784 * @param trail List of peers in trail from me to a finger, NOT including
2788 send_trail_teardown (struct FingerInfo *finger,
2789 struct Trail *trail)
2791 struct FriendInfo *friend;
2792 struct GNUNET_PeerIdentity *next_hop;
2795 GNUNET_assert (NULL !=
2796 (next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2797 GDS_ROUTING_SRC_TO_DEST)));
2799 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2801 //GDS_ROUTING_test_print();
2802 GNUNET_assert (trail->is_present == GNUNET_YES);
2804 /* Finger is not a friend. */
2805 if (trail->trail_length > 0)
2807 GNUNET_assert (NULL != (friend =
2808 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2809 &trail->trail_head->peer)));
2813 GNUNET_assert (NULL != (friend =
2814 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2815 &finger->finger_identity)));
2818 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id));
2819 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2820 friend->trails_count--;
2821 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2822 GDS_ROUTING_SRC_TO_DEST,
2828 * Send trail teardown message across all the trails to reach to finger.
2829 * @param finger Finger whose all the trail should be freed.
2832 send_all_finger_trails_teardown (struct FingerInfo *finger)
2836 for (i = 0; i < finger->trails_count; i++)
2838 struct Trail *trail;
2840 trail = &finger->trail_list[i];
2841 GNUNET_assert (trail->is_present == GNUNET_YES);
2842 send_trail_teardown (finger, trail);
2843 trail->is_present = GNUNET_NO;
2849 * Free a specific trail
2850 * @param trail List of peers to be freed.
2853 free_trail (struct Trail *trail)
2855 struct Trail_Element *trail_element;
2857 while (NULL != (trail_element = trail->trail_head))
2859 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2863 GNUNET_free_non_null (trail_element);
2865 trail->trail_head = NULL;
2866 trail->trail_tail = NULL;
2871 * Free finger and its trail.
2872 * @param finger Finger to be freed.
2875 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2877 struct Trail *trail;
2880 /* Free all the trails to reach to finger */
2881 for (i = 0; i < finger->trails_count; i++)
2883 trail = &finger->trail_list[i];
2884 //FIXME: Check if there are any missing entry in this list because of
2885 // how we insert. If not then no need of this check.
2886 if (GNUNET_NO == trail->is_present)
2889 if (trail->trail_length > 0)
2893 trail->is_present = GNUNET_NO;
2896 finger->is_present = GNUNET_NO;
2897 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2902 * FIXME: ensure that you are not adding any trail to reach to a friend which
2903 * is a finger. Also decide on should you increment trails count of a friend
2904 * which is also a finger.
2905 * Add a new entry in finger table at finger_table_index.
2906 * In case finger identity is me or a friend, then don't add a trail. NOTE
2907 * trail length to reach to a finger can be 0 only if the finger is a friend
2909 * In case a finger is a friend, then increment the trails count of the friend.
2910 * @param finger_identity Peer Identity of new finger
2911 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2912 * @param finger_trail_length Total number of peers in @a finger_trail.
2913 * @param trail_id Unique identifier of the trail.
2914 * @param finger_table_index Index in finger table.
2917 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2918 const struct GNUNET_PeerIdentity *finger_trail,
2919 unsigned int finger_trail_length,
2920 struct GNUNET_HashCode trail_id,
2921 unsigned int finger_table_index)
2923 struct FingerInfo *new_entry;
2924 struct FriendInfo *first_trail_hop;
2925 struct Trail *trail;
2928 new_entry = GNUNET_new (struct FingerInfo);
2929 new_entry->finger_identity = finger_identity;
2930 new_entry->finger_table_index = finger_table_index;
2931 new_entry->is_present = GNUNET_YES;
2933 /* If the new entry is my own identity. */
2934 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2936 new_entry->trails_count = 0;
2937 finger_table[finger_table_index] = *new_entry;
2938 GNUNET_free (new_entry);
2942 /* If finger is a friend, then we don't actually have a trail.
2943 * Just a trail id */
2944 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2947 new_entry->trail_list[0].trail_id = trail_id;
2948 new_entry->trails_count = 1;
2949 new_entry->trail_list[0].is_present = GNUNET_YES;
2950 new_entry->trail_list[0].trail_length = 0;
2951 new_entry->trail_list[0].trail_head = NULL;
2952 new_entry->trail_list[0].trail_tail = NULL;
2953 finger_table[finger_table_index] = *new_entry;
2954 GNUNET_assert (NULL !=
2956 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2957 &finger_identity)));
2959 first_trail_hop->trails_count++;
2960 GNUNET_free (new_entry);
2964 /* finger trail length can be 0 only in case if finger is my identity or
2965 finger is friend. We should never reach here. */
2966 GNUNET_assert (finger_trail_length > 0);
2968 GNUNET_assert (NULL !=
2970 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2971 &finger_trail[0])));
2972 new_entry->trails_count = 1;
2973 first_trail_hop->trails_count++;
2975 /* Copy the finger trail into trail. */
2976 trail = GNUNET_new (struct Trail);
2977 while (i < finger_trail_length)
2979 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2981 element->next = NULL;
2982 element->prev = NULL;
2983 element->peer = finger_trail[i];
2984 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2990 /* Add trail to trail list. */
2991 new_entry->trail_list[0].trail_head = trail->trail_head;
2992 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2993 new_entry->trail_list[0].trail_length = finger_trail_length;
2994 new_entry->trail_list[0].trail_id = trail_id;
2995 new_entry->trail_list[0].is_present = GNUNET_YES;
2996 finger_table[finger_table_index] = *new_entry;
2997 //GNUNET_free (new_entry);
2998 //GNUNET_free (trail);
3004 * Scan the trail to check if there is any other friend in the trail other than
3005 * first hop. If yes then shortcut the trail, send trail compression message to
3006 * peers which are no longer part of trail and send back the updated trail
3007 * and trail_length to calling function.
3008 * @param finger_identity Finger whose trail we will scan.
3009 * @param finger_trail [in, out] Trail to reach from source to finger,
3010 * @param finger_trail_length Total number of peers in original finger_trail.
3011 * @param finger_trail_id Unique identifier of the finger trail.
3012 * @return updated trail length in case we shortcut the trail, else original
3015 static struct GNUNET_PeerIdentity *
3016 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
3017 const struct GNUNET_PeerIdentity *trail,
3018 unsigned int trail_length,
3019 struct GNUNET_HashCode trail_id,
3020 int *new_trail_length)
3022 struct FriendInfo *target_friend;
3023 struct GNUNET_PeerIdentity *new_trail;
3026 /* If I am my own finger identity, then we set trail_length = 0.
3027 Note: Here we don't send trail compression message, as no peer in its
3028 trail added an entry in its routing table.*/
3029 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3031 *new_trail_length = 0;
3035 if (0 == trail_length)
3037 *new_trail_length = 0;
3040 /* If finger identity is a friend. */
3041 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3043 *new_trail_length = 0;
3045 /* If there is trail to reach this finger/friend */
3046 if (trail_length > 0)
3048 /* Finger is your first friend. */
3049 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3050 GNUNET_assert (NULL !=
3052 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3055 /* Before you send a trail compression, get the routing entry
3056 from you routing table. update the fields in routing table
3057 to update your next hop to finger identity. */
3058 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3059 trail_id, finger_identity,
3065 /* For other cases, when its neither a friend nor my own identity.*/
3066 for (i = trail_length - 1; i > 0; i--)
3068 /* If the element at this index in trail is a friend. */
3069 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3071 struct FriendInfo *target_friend;
3074 GNUNET_assert (NULL !=
3076 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3078 GNUNET_assert (NULL !=
3079 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3081 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3082 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3087 /* Copy the trail from index i to index (trail_length -1) into a new trail
3088 * and update new trail length */
3089 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3090 while (i < trail_length)
3092 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3096 *new_trail_length = j+1;
3101 /* If we did not compress the trail, return the original trail back.*/
3102 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3103 *new_trail_length = trail_length;
3104 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3110 * Send verify successor message to your current successor over the shortest
3112 * @param successor Current successor.
3115 send_verify_successor_message (struct FingerInfo *successor)
3118 * FIXME: should we send a verify successor message across all the trails
3119 * in case we send through all friends. It complicates the logic, don't
3120 * do it at the moment. Write it as optimization and do it later.
3121 * 1. Here we can have 3 types of fingers
3122 * --> my own identity
3123 * Assumption that the calling function will not send request for
3124 * such successor. Move the logic here.
3125 * --> friend is a finger
3126 * Need to verify if we keep the trails count for a friend. In case of
3127 * friend there is no trail to reach to that friend, so
3128 * 1. no entry in routing table
3130 * 3. no trails count
3131 * 4. but do we increment the count of trails through the friend?
3132 * Trails count is used only to keep a limit on number of trails
3133 * that a friend should be part of. No need to increment the trails
3134 * count for a friend which is a finegr also. so, if finger = friend
3135 * then don't increment the trails count. But if the same friend
3136 * is the first friend to reach to some other finger then increment
3137 * the trails count. Not sure if this design is correct need to verify
3141 struct FriendInfo *target_friend;
3142 struct GNUNET_HashCode trail_id;
3144 struct Trail *trail;
3145 struct Trail_Element *element;
3146 unsigned int trail_length;
3150 trail = &successor->trail_list[i];
3152 /* Trail stored at this index. */
3153 GNUNET_assert (GNUNET_YES == trail->is_present);
3155 trail_id = trail->trail_id;
3156 trail_length = trail->trail_length;
3158 if (trail_length > 0)
3160 /* Copy the trail into peer list. */
3161 struct GNUNET_PeerIdentity peer_list[trail_length];
3163 element = trail->trail_head;
3164 while (j < trail_length)
3166 peer_list[j] = element->peer;
3167 element = element->next;
3171 GNUNET_assert (NULL != (target_friend =
3172 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3174 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3175 successor->finger_identity,
3176 trail_id, peer_list, trail_length,
3182 GNUNET_assert (NULL != (target_friend =
3183 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3184 &successor->finger_identity)));
3185 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3186 successor->finger_identity,
3195 * Update the current search finger index.
3198 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3199 unsigned int finger_table_index)
3201 struct FingerInfo *successor;
3203 if (finger_table_index != current_search_finger_index)
3206 successor = &finger_table[0];
3207 GNUNET_assert (GNUNET_YES == successor->is_present);
3209 /* We were looking for immediate successor. */
3210 if (0 == current_search_finger_index)
3212 /* Start looking for immediate predecessor. */
3213 current_search_finger_index = PREDECESSOR_FINGER_ID;
3215 /* If I am not my own successor, then send a verify successor message. */
3216 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3218 send_verify_successor_message (successor);
3223 current_search_finger_index = current_search_finger_index - 1;
3229 * Calculate finger_table_index from initial 64 bit finger identity value that
3230 * we send in trail setup message.
3231 * @param ultimate_destination_finger_value Value that we calculated from our
3232 * identity and finger_table_index.
3233 * @param is_predecessor Is the entry for predecessor or not?
3234 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3235 * finger_table_index > PREDECESSOR_FINGER_ID ,
3236 * if no valid finger_table_index is found.
3239 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3240 unsigned int is_predecessor)
3244 unsigned int finger_table_index;
3246 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3247 my_id64 = GNUNET_ntohll (my_id64);
3249 /* Is this a predecessor finger? */
3250 if (1 == is_predecessor)
3252 diff = my_id64 - ultimate_destination_finger_value;
3254 finger_table_index = PREDECESSOR_FINGER_ID;
3256 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3261 diff = ultimate_destination_finger_value - my_id64;
3262 finger_table_index = (log10 (diff))/(log10 (2));
3265 return finger_table_index;
3270 * Remove finger and its associated data structures from finger table.
3271 * @param finger Finger to be removed.
3274 remove_existing_finger (struct FingerInfo *existing_finger,
3275 unsigned int finger_table_index)
3277 struct FingerInfo *finger;
3279 finger = &finger_table[finger_table_index];
3280 GNUNET_assert (GNUNET_YES == finger->is_present);
3282 /* If I am my own finger, then we have no trails. */
3283 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3286 finger->is_present = GNUNET_NO;
3287 memset ((void *)&finger_table[finger_table_index], 0,
3288 sizeof (finger_table[finger_table_index]));
3292 /* For all other fingers, send trail teardown across all the trails to reach
3293 finger, and free the finger. */
3294 send_all_finger_trails_teardown (finger);
3295 free_finger (finger, finger_table_index);
3301 * FIXME: Check for memory leaks.
3302 * Check if there is already an entry in finger_table at finger_table_index.
3303 * We get the finger_table_index from 64bit finger value we got from the network.
3304 * -- If yes, then select the closest finger.
3305 * -- If new and existing finger are same, then check if you can store more
3307 * -- If yes then add trail, else keep the best trails to reach to the
3309 * -- If the new finger is closest, remove the existing entry, send trail
3310 * teardown message across all the trails to reach the existing entry.
3311 * Add the new finger.
3312 * -- If new and existing finger are different, and existing finger is closest
3314 * -- Update current_search_finger_index.
3315 * @param finger_identity Peer Identity of new finger
3316 * @param finger_trail Trail to reach the new finger
3317 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3318 * @param is_predecessor Is this entry for predecessor in finger_table?
3319 * @param finger_value 64 bit value of finger identity that we got from network.
3320 * @param finger_trail_id Unique identifier of @finger_trail.
3323 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3324 const struct GNUNET_PeerIdentity *finger_trail,
3325 unsigned int finger_trail_length,
3326 unsigned int is_predecessor,
3327 uint64_t finger_value,
3328 struct GNUNET_HashCode finger_trail_id)
3330 struct FingerInfo *existing_finger;
3331 struct GNUNET_PeerIdentity *closest_peer;
3332 struct FingerInfo *successor;
3333 int updated_finger_trail_length;
3334 unsigned int finger_table_index;
3336 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3337 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3339 /* Invalid finger_table_index. */
3340 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3342 GNUNET_break_op (0);
3345 //test_finger_table_print();
3346 //s test_friend_peermap_print();
3347 /* If the new entry for any finger table index other than successor or predecessor
3348 * is same as successor then don't add it in finger table,
3349 * reset the current search finger index and exit. */
3350 if ((0 != finger_table_index) &&
3351 (PREDECESSOR_FINGER_ID != finger_table_index) &&
3352 (finger_table_index == current_search_finger_index)) //FIXME; why do I check this cond?
3354 successor = &finger_table[0];
3355 GNUNET_assert (GNUNET_YES == successor->is_present);
3356 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3357 &successor->finger_identity))
3359 current_search_finger_index = 0;
3364 existing_finger = &finger_table[finger_table_index];
3366 /* No entry present in finger_table for given finger map index. */
3367 if (GNUNET_NO == existing_finger->is_present)
3369 struct GNUNET_PeerIdentity *updated_trail;
3371 /* Shorten the trail if possible. */
3372 updated_finger_trail_length = finger_trail_length;
3374 scan_and_compress_trail (finger_identity, finger_trail,
3375 finger_trail_length, finger_trail_id,
3376 &updated_finger_trail_length);
3377 add_new_finger (finger_identity, updated_trail,
3378 updated_finger_trail_length,
3379 finger_trail_id, finger_table_index);
3380 update_current_search_finger_index (finger_identity,
3381 finger_table_index);
3386 /* If existing entry and finger identity are not same. */
3387 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3390 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3395 /* If the new finger is the closest peer. */
3396 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3398 struct GNUNET_PeerIdentity *updated_trail;
3399 /* Shorten the trail if possible. */
3400 updated_finger_trail_length = finger_trail_length;
3402 scan_and_compress_trail (finger_identity, finger_trail,
3403 finger_trail_length, finger_trail_id,
3404 &updated_finger_trail_length);
3406 remove_existing_finger (existing_finger, finger_table_index);
3407 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3408 finger_trail_id, finger_table_index);
3413 /* Existing finger is the closest one. We need to send trail teardown
3414 across the trail setup in routing table of all the peers. */
3415 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3417 if (finger_trail_length > 0)
3418 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3419 GDS_ROUTING_SRC_TO_DEST,
3422 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3423 GDS_ROUTING_SRC_TO_DEST,
3430 /* If both new and existing entry are same as my_identity, then do nothing. */
3431 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3436 /* If the existing finger is not a friend. */
3438 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3439 &existing_finger->finger_identity))
3441 struct GNUNET_PeerIdentity *updated_trail;
3443 /* Shorten the trail if possible. */
3444 updated_finger_trail_length = finger_trail_length;
3446 scan_and_compress_trail (finger_identity, finger_trail,
3447 finger_trail_length, finger_trail_id,
3448 &updated_finger_trail_length);
3449 /* If there is space to store more trails. */
3450 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3451 add_new_trail (existing_finger, updated_trail,
3452 updated_finger_trail_length, finger_trail_id);
3454 select_and_replace_trail (existing_finger, updated_trail,
3455 updated_finger_trail_length, finger_trail_id);
3459 update_current_search_finger_index (finger_identity, finger_table_index);
3465 * Core handler for P2P put messages.
3466 * @param cls closure
3467 * @param peer sender of the request
3468 * @param message message
3469 * @return #GNUNET_OK to keep the connection open,
3470 * #GNUNET_SYSERR to close it (signal serious error)
3473 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3474 const struct GNUNET_MessageHeader *message)
3476 struct PeerPutMessage *put;
3477 struct GNUNET_PeerIdentity *put_path;
3478 struct GNUNET_HashCode test_key;
3479 enum GNUNET_DHT_RouteOption options;
3480 struct GNUNET_PeerIdentity best_known_dest;
3481 struct GNUNET_HashCode intermediate_trail_id;
3482 struct GNUNET_PeerIdentity *next_hop;
3486 size_t payload_size;
3489 msize = ntohs (message->size);
3490 if (msize < sizeof (struct PeerPutMessage))
3492 GNUNET_break_op (0);
3496 put = (struct PeerPutMessage *) message;
3497 putlen = ntohl (put->put_path_length);
3500 sizeof (struct PeerPutMessage) +
3501 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3503 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3505 GNUNET_break_op (0);
3509 best_known_dest = put->best_known_destination;
3510 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3511 payload = &put_path[putlen];
3512 options = ntohl (put->options);
3513 intermediate_trail_id = put->intermediate_trail_id;
3515 payload_size = msize - (sizeof (struct PeerPutMessage) +
3516 putlen * sizeof (struct GNUNET_PeerIdentity));
3518 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3519 payload, payload_size, &test_key))
3522 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3524 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3525 GNUNET_break_op (0);
3526 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3527 "PUT with key `%s' for block with key %s\n",
3528 put_s, GNUNET_h2s_full (&test_key));
3529 GNUNET_free (put_s);
3534 GNUNET_break_op (0);
3537 /* cannot verify, good luck */
3541 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3543 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3544 ntohl (put->block_type),
3546 NULL, 0, /* bloom filer */
3547 NULL, 0, /* xquery */
3548 payload, payload_size))
3550 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3551 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3554 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3555 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3556 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3557 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3558 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3559 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3561 GNUNET_break_op (0);
3566 /* extend 'put path' by sender */
3567 struct GNUNET_PeerIdentity pp[putlen + 1];
3568 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3570 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3577 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3578 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3580 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3581 GDS_ROUTING_SRC_TO_DEST);
3585 key_value = GNUNET_ntohll (key_value);
3586 next_hop = find_successor (key_value, &best_known_dest,
3587 &intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
3590 if (NULL == next_hop)
3592 GNUNET_STATISTICS_update (GDS_stats,
3593 gettext_noop ("# Next hop to forward the packet not found "
3594 "trail setup request, packet dropped."),
3596 return GNUNET_SYSERR;
3599 GDS_CLIENTS_process_put (options,
3600 ntohl (put->block_type),
3601 ntohl (put->hop_count),
3602 ntohl (put->desired_replication_level),
3604 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3609 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest)) /* I am the final destination */
3611 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3612 &(put->key),putlen, pp, ntohl (put->block_type),
3613 payload_size, payload);
3614 GNUNET_free_non_null (next_hop);
3619 GDS_NEIGHBOURS_send_put (&put->key,
3620 ntohl (put->block_type),ntohl (put->options),
3621 ntohl (put->desired_replication_level),
3622 &best_known_dest, &intermediate_trail_id, next_hop,
3623 ntohl (put->hop_count), putlen, pp,
3624 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3625 payload, payload_size);
3629 return GNUNET_SYSERR;
3634 * Core handler for p2p get requests.
3636 * @param cls closure
3637 * @param peer sender of the request
3638 * @param message message
3639 * @return #GNUNET_OK to keep the connection open,
3640 * #GNUNET_SYSERR to close it (signal serious error)
3643 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3644 const struct GNUNET_MessageHeader *message)
3646 const struct PeerGetMessage *get;
3647 const struct GNUNET_PeerIdentity *get_path;
3648 struct GNUNET_PeerIdentity best_known_dest;
3649 struct GNUNET_HashCode intermediate_trail_id;
3650 struct GNUNET_PeerIdentity *next_hop;
3651 uint32_t get_length;
3655 msize = ntohs (message->size);
3656 if (msize < sizeof (struct PeerGetMessage))
3658 GNUNET_break_op (0);
3662 get = (const struct PeerGetMessage *)message;
3663 get_length = ntohl (get->get_path_length);
3664 best_known_dest = get->best_known_destination;
3665 intermediate_trail_id = get->intermediate_trail_id;
3666 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3669 sizeof (struct PeerGetMessage) +
3670 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3672 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3674 GNUNET_break_op (0);
3678 /* Add sender to get path */
3679 struct GNUNET_PeerIdentity gp[get_length + 1];
3681 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3682 gp[get_length] = *peer;
3683 get_length = get_length + 1;
3685 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3686 key_value = GNUNET_ntohll (key_value);
3688 /* I am not the final destination. I am part of trail to reach final dest. */
3689 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3691 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3692 GDS_ROUTING_SRC_TO_DEST);
3696 /* Get the next hop to pass the message to. */
3697 next_hop = find_successor (key_value, &best_known_dest,
3698 &intermediate_trail_id, GDS_FINGER_TYPE_NON_PREDECESSOR);
3701 if (NULL == next_hop)
3703 GNUNET_STATISTICS_update (GDS_stats,
3704 gettext_noop ("# Next hop to forward the packet not found "
3705 "trail setup request, packet dropped."),
3707 return GNUNET_SYSERR;
3709 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3710 get->desired_replication_level, get->get_path_length,
3712 /* I am the final destination. */
3713 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3715 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3717 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3718 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3719 get_length = get_length + 1;
3720 /* FIXME: here it may happen that we find our identity closest to key, but
3721 we don't have the data. then in that case, we should forward the packet
3722 to the next closest peer. */
3723 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3724 get_length, final_get_path,
3725 &final_get_path[get_length-2], &my_identity);
3731 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3732 get->desired_replication_level, &best_known_dest,
3733 &intermediate_trail_id, next_hop, 0,
3735 GNUNET_free (next_hop);
3737 return GNUNET_SYSERR;
3742 * Core handler for get result
3743 * @param cls closure
3744 * @param peer sender of the request
3745 * @param message message
3746 * @return #GNUNET_OK to keep the connection open,
3747 * #GNUNET_SYSERR to close it (signal serious error)
3750 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3751 const struct GNUNET_MessageHeader *message)
3753 const struct PeerGetResultMessage *get_result;
3754 const struct GNUNET_PeerIdentity *get_path;
3755 const struct GNUNET_PeerIdentity *put_path;
3756 const void *payload;
3757 size_t payload_size;
3759 unsigned int getlen;
3760 unsigned int putlen;
3761 int current_path_index;
3763 msize = ntohs (message->size);
3764 if (msize < sizeof (struct PeerGetResultMessage))
3766 GNUNET_break_op (0);
3770 get_result = (const struct PeerGetResultMessage *)message;
3771 getlen = ntohl (get_result->get_path_length);
3772 putlen = ntohl (get_result->put_path_length);
3775 sizeof (struct PeerGetResultMessage) +
3776 getlen * sizeof (struct GNUNET_PeerIdentity) +
3777 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3779 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3781 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3783 GNUNET_break_op (0);
3787 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3788 get_path = &put_path[putlen];
3789 payload = (const void *) &get_path[getlen];
3790 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3791 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3793 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3795 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3796 getlen, get_path, putlen,
3797 put_path, get_result->type, payload_size, payload);
3802 current_path_index = search_my_index (get_path, getlen);
3803 if (-1 == current_path_index )
3806 return GNUNET_SYSERR;
3808 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3809 &get_path[current_path_index - 1],
3810 &(get_result->querying_peer), putlen, put_path,
3811 getlen, get_path, get_result->expiration_time,
3812 payload, payload_size);
3815 return GNUNET_SYSERR;
3820 * Get the best known next destination (local_dest) among your fingers, friends
3821 * and my identity. In case I was part of trail to reach to some other destination
3822 * (current_dest), then compare current_dest and local_dest, and choose the
3824 * @param final_dest_finger_value Peer closest to this value will be
3825 * @a local_best_known_dest
3826 * @param local_best_known_dest[out] Updated to peer identity which is closest to
3827 * @a final_dest_finger_value.
3828 * @param new_intermediate_trail_id In case @a local_best_known_dest is a finger,
3829 * then the trail id to reach to the finger
3830 * @param is_predecessor Is source peer trying to setup trail to its predecessor
3832 * @param current_dest Peer which should get this message ultimately according
3833 * to the peer which sent me this message. It could be me
3834 * or some other peer. In case it is not me, then I am a part
3835 * of trail to reach to that peer.
3838 static struct GNUNET_PeerIdentity *
3839 get_local_best_known_next_hop (uint64_t final_dest_finger_value,
3840 struct GNUNET_PeerIdentity *local_best_known_dest,
3841 struct GNUNET_HashCode *new_intermediate_trail_id,
3842 struct GNUNET_HashCode intermediate_trail_id,
3843 unsigned int is_predecessor,
3844 struct GNUNET_PeerIdentity *current_dest)
3846 struct GNUNET_PeerIdentity *next_hop_to_local_best_known_dest;
3848 /* Choose a local best known hop among your fingers, friends and you. */
3849 next_hop_to_local_best_known_dest = find_successor (final_dest_finger_value,
3850 local_best_known_dest,
3851 new_intermediate_trail_id,
3854 /* Are we just a part of a trail towards a finger (current_destination)? */
3855 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest)))
3857 struct GNUNET_PeerIdentity *closest_peer;
3859 /* Select best successor among one found locally and current_destination
3860 * that we got from network.*/
3861 if (0 != GNUNET_CRYPTO_cmp_peer_identity (local_best_known_dest, current_dest))
3863 // GDS_ROUTING_test_print();
3864 closest_peer = select_closest_peer (local_best_known_dest,
3866 final_dest_finger_value,
3869 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3870 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3872 struct GNUNET_PeerIdentity *next_hop;
3873 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3874 GDS_ROUTING_SRC_TO_DEST);
3875 /* FIXME: Here we found next_hop NULL from routing table, but we still
3876 * have a next_hop from find_successor should we not break and choose that
3878 if (NULL == next_hop)
3880 GNUNET_break_op (0);
3883 next_hop_to_local_best_known_dest = next_hop;
3884 local_best_known_dest = current_dest;
3885 *new_intermediate_trail_id = intermediate_trail_id;
3890 GNUNET_assert (NULL != next_hop_to_local_best_known_dest);
3891 return next_hop_to_local_best_known_dest;
3896 * Core handle for PeerTrailSetupMessage.
3897 * @param cls closure
3898 * @param message message
3899 * @param peer peer identity this notification is about
3900 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3903 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3904 const struct GNUNET_MessageHeader *message)
3906 const struct PeerTrailSetupMessage *trail_setup;
3907 const struct GNUNET_PeerIdentity *trail_peer_list;
3908 struct GNUNET_PeerIdentity *local_best_known_dest;
3909 struct GNUNET_PeerIdentity current_dest;
3910 struct GNUNET_PeerIdentity *next_hop_towards_local_best_known_dest;
3911 struct FriendInfo *target_friend;
3912 struct GNUNET_PeerIdentity source;
3913 uint64_t final_dest_finger_val;
3914 struct GNUNET_HashCode *new_intermediate_trail_id;
3915 struct GNUNET_HashCode intermediate_trail_id;
3916 struct GNUNET_HashCode trail_id;
3917 unsigned int is_predecessor;
3918 uint32_t trail_length;
3921 msize = ntohs (message->size);
3922 if (msize < sizeof (struct PeerTrailSetupMessage))
3924 GNUNET_break_op (0);
3928 trail_setup = (const struct PeerTrailSetupMessage *) message;
3929 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3930 sizeof (struct GNUNET_PeerIdentity);
3931 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3932 sizeof (struct GNUNET_PeerIdentity) != 0)
3934 GNUNET_break_op (0);
3938 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3939 current_dest = trail_setup->best_known_destination;
3940 trail_id = trail_setup->trail_id;
3941 final_dest_finger_val =
3942 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3943 source = trail_setup->source_peer;
3944 is_predecessor = ntohl (trail_setup->is_predecessor);
3945 intermediate_trail_id = trail_setup->intermediate_trail_id;
3947 /* Is my routing table full? */
3948 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3950 /* As my routing table is full, I can no longer handle any more trail
3953 GNUNET_assert (NULL !=
3955 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
3956 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
3957 my_identity, is_predecessor,
3958 trail_peer_list, trail_length,
3959 trail_id, target_friend,
3960 CONGESTION_TIMEOUT);
3964 new_intermediate_trail_id = GNUNET_new (struct GNUNET_HashCode);
3965 local_best_known_dest = GNUNET_new (struct GNUNET_PeerIdentity);
3967 /* Get the next hop to forward the trail setup request. */
3968 next_hop_towards_local_best_known_dest =
3969 get_local_best_known_next_hop (final_dest_finger_val,
3970 local_best_known_dest,
3971 new_intermediate_trail_id,
3972 intermediate_trail_id,
3976 GNUNET_assert (NULL != local_best_known_dest);
3977 GNUNET_assert (NULL != next_hop_towards_local_best_known_dest);
3979 /* Am I the final destination? */
3980 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (local_best_known_dest,
3983 /* If I was not the source of this message for which now I am destination */
3984 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
3986 GDS_ROUTING_add (trail_id, *peer, my_identity);
3989 GNUNET_assert (NULL !=
3991 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
3992 GDS_NEIGHBOURS_send_trail_setup_result (source,
3994 target_friend, trail_length,
3996 final_dest_finger_val,
3997 is_predecessor, trail_id);
4001 /* Add yourself to list of peers. */
4002 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4004 memcpy (peer_list, trail_peer_list,
4005 trail_length * sizeof (struct GNUNET_PeerIdentity));
4006 peer_list[trail_length] = my_identity;
4007 GNUNET_assert (NULL !=
4009 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4010 next_hop_towards_local_best_known_dest)));
4011 /* FIXME; CHECK IF INTERMEDIATE TRAIL ID is 0 thne pas null. */
4013 GDS_NEIGHBOURS_send_trail_setup (source,
4014 final_dest_finger_val,
4015 *local_best_known_dest,
4016 target_friend, trail_length + 1, peer_list,
4017 is_predecessor, trail_id,
4018 new_intermediate_trail_id);
4020 GNUNET_free (local_best_known_dest);
4025 /* FIXME: here we are calculating my_index and comparing also in this function.
4026 And we are doing it again here in this function. Re factor the code. */
4028 * FIXME: Should we call this function everywhere in all the handle functions
4029 * where we have a trail to verify from or a trail id. something like
4030 * if prev hop is not same then drop the message.
4031 * Check if sender_peer and peer from which we should receive the message are
4032 * same or different.
4033 * @param trail_peer_list List of peers in trail
4034 * @param trail_length Total number of peers in @a trail_peer_list
4035 * @param sender_peer Peer from which we got the message.
4036 * @param finger_identity Finger to which trail is setup. It is not part of trail.
4037 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
4038 * message are different.
4039 * #GNUNET_NO if sender_peer and peer from which we should receive the
4040 * message are different.
4043 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
4044 unsigned int trail_length,
4045 const struct GNUNET_PeerIdentity *sender_peer,
4046 struct GNUNET_PeerIdentity finger_identity,
4047 struct GNUNET_PeerIdentity source_peer)
4051 /* I am the source peer. */
4052 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4055 /* Is the first element of the trail is sender_peer.*/
4056 if (trail_length > 0)
4058 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4064 /* Is finger the sender peer? */
4065 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4072 /* Get my current location in the trail. */
4073 my_index = search_my_index (trail_peer_list, trail_length);
4077 /* I am the last element in the trail. */
4078 if ((trail_length - 1) == my_index)
4080 /* Is finger the sender_peer? */
4081 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4087 /* Is peer after me in trail the sender peer? */
4088 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4089 &trail_peer_list[my_index + 1]))
4099 * FIXME: we should also add a case where we search if we are present in the trail
4101 * Core handle for p2p trail setup result messages.
4103 * @param message message
4104 * @param peer sender of this message.
4105 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4108 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4109 const struct GNUNET_MessageHeader *message)
4111 const struct PeerTrailSetupResultMessage *trail_result;
4112 const struct GNUNET_PeerIdentity *trail_peer_list;
4113 struct GNUNET_PeerIdentity next_hop;
4114 struct FriendInfo *target_friend;
4115 struct GNUNET_PeerIdentity querying_peer;
4116 struct GNUNET_PeerIdentity finger_identity;
4117 uint32_t trail_length;
4118 uint64_t ulitmate_destination_finger_value;
4119 uint32_t is_predecessor;
4120 struct GNUNET_HashCode trail_id;
4124 msize = ntohs (message->size);
4125 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4127 GNUNET_break_op (0);
4131 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4132 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4133 sizeof (struct GNUNET_PeerIdentity);
4134 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4135 sizeof (struct GNUNET_PeerIdentity) != 0)
4137 GNUNET_break_op (0);
4141 is_predecessor = htonl (trail_result->is_predecessor);
4142 querying_peer = trail_result->querying_peer;
4143 finger_identity = trail_result->finger_identity;
4144 trail_id = trail_result->trail_id;
4145 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4146 ulitmate_destination_finger_value =
4147 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4149 /* FIXME: here we are calculating my_index and comparing also in this function.
4150 And we are doing it again here in this function. Re factor the code. */
4151 /* Ensure that sender peer is the peer from which we were expecting the message. */
4153 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
4155 peer, finger_identity, querying_peer))
4157 GNUNET_break_op (0);
4158 return GNUNET_SYSERR;
4162 /* Am I the one who initiated the query? */
4163 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer,
4166 /* If I am not my own finger identity, then add routing table entry. */
4167 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4169 GDS_ROUTING_add (trail_id, my_identity, *peer);
4172 /* FIXME: Remove this assert later. */
4173 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4175 finger_table_add (finger_identity, trail_peer_list,
4176 trail_length, ulitmate_destination_finger_value,
4177 is_predecessor, trail_id);
4181 /* Get my location in the trail. */
4182 my_index = search_my_index (trail_peer_list, trail_length);
4186 return GNUNET_SYSERR;
4189 /* FIXME: CHECK IF YOU ARE PRESENT MORE THAN ONCE IN THE TRAIL, IF YES
4190 THEN REMOVE ALL THE ENTRIES AND CHOOSE THE PEER THERE.*/
4193 next_hop = trail_result->querying_peer;
4195 next_hop = trail_peer_list[my_index - 1];
4197 /* If the querying_peer is its own finger, then don't add an entry in routing
4198 * table as querying peer will discard the trail. */
4199 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4200 &(trail_result->finger_identity))))
4202 GDS_ROUTING_add (trail_id, next_hop, *peer);
4205 GNUNET_assert (NULL !=
4207 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4208 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4209 target_friend, trail_length, trail_peer_list,
4211 ulitmate_destination_finger_value,
4219 * @param trail Trail to be inverted
4220 * @param trail_length Total number of peers in the trail.
4221 * @return Updated trail
4223 static struct GNUNET_PeerIdentity *
4224 invert_trail (const struct GNUNET_PeerIdentity *trail,
4225 unsigned int trail_length)
4229 struct GNUNET_PeerIdentity *inverted_trail;
4231 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4234 j = trail_length - 1;
4235 while (i < trail_length)
4237 inverted_trail[i] = trail[j];
4241 return inverted_trail;
4246 * Return the shortest trail to reach from me to my_predecessor.
4247 * @param my_predecessor my current predecessor.
4248 * @param current_trail Trail from source to me.
4249 * @param current_trail_length Total number of peers in @a current_trail
4250 * @param trail_length [out] Total number of peers in selected trail.
4251 * @return Updated trail from source peer to my_predecessor.
4253 static struct GNUNET_PeerIdentity *
4254 trail_source_to_my_predecessor (const struct GNUNET_PeerIdentity *current_trail,
4255 unsigned int current_trail_length,
4256 unsigned int *trail_length)
4258 struct GNUNET_PeerIdentity *trail_me_to_predecessor;
4259 struct Trail *trail;
4260 struct Trail_Element *trail_element;
4261 struct FingerInfo *my_predecessor;
4263 unsigned int shortest_trail_length = 0;
4264 unsigned int trail_index = 0;
4266 my_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4268 GNUNET_assert (GNUNET_YES == my_predecessor->is_present);
4270 //if my_predecessor is a friend then don't send back any trail. as
4271 // there is no trail.
4274 /* Choose the shortest path from me to my predecessor. */
4275 for (i = 0; i < my_predecessor->trails_count; i++)
4277 trail = &my_predecessor->trail_list[i];
4278 if (trail->trail_length > shortest_trail_length)
4280 shortest_trail_length = trail->trail_length;
4284 *trail_length = shortest_trail_length;
4285 trail_me_to_predecessor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
4288 /* Copy the selected trail and send this trail to calling function. */
4290 trail = &my_predecessor->trail_list[trail_index];
4291 trail_element = trail->trail_head;
4292 while ( i < shortest_trail_length)
4294 trail_me_to_predecessor[i] = trail_element->peer;
4296 trail_element = trail_element->next;
4299 return trail_me_to_predecessor;
4304 * FIXME In case predecessor is a friend then do we add it in routing table.
4305 * if not then check the logic of trail teardown in case we compress the trail
4306 * such that friend is finger. then do we remove the entry from end points or
4307 * not. Ideally we should remove the entries from end point.
4308 * Add finger as your predecessor. To add, first generate a new trail id, invert
4309 * the trail to get the trail from me to finger, add an entry in your routing
4310 * table, send add trail message to peers which are part of trail from me to
4311 * finger and add finger in finger table.
4314 * @param trail_length
4317 update_predecessor (struct GNUNET_PeerIdentity finger,
4318 struct GNUNET_PeerIdentity *trail,
4319 unsigned int trail_length)
4321 struct GNUNET_HashCode trail_to_new_predecessor_id;
4322 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4323 struct FriendInfo *target_friend;
4325 /* Generate trail id for trail from me to new predecessor = finger. */
4326 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4327 &trail_to_new_predecessor_id,
4328 sizeof (trail_to_new_predecessor_id));
4329 //test_finger_table_print();
4330 /* Finger is a friend. */
4331 if (trail_length == 0)
4333 trail_to_new_predecessor = NULL;
4334 /* FIXME: check that you always add trail entry even if your finger is
4336 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger);
4337 GNUNET_assert (NULL != (target_friend =
4338 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4343 /* Invert the trail to get the trail from me to finger, NOT including the
4345 trail_to_new_predecessor = invert_trail (trail, trail_length);
4347 /* Add an entry in your routing table. */
4348 GDS_ROUTING_add (trail_to_new_predecessor_id,
4350 trail_to_new_predecessor[trail_length - 1]);
4352 GNUNET_assert (NULL != (target_friend =
4353 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4354 &trail_to_new_predecessor[0])));
4355 GNUNET_assert (NULL != (
4356 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4357 &trail[trail_length - 1])));
4360 /* Add entry in routing table of all peers that are part of trail from me
4361 to finger, including finger. */
4362 GDS_NEIGHBOURS_send_add_trail (my_identity,
4364 trail_to_new_predecessor_id,
4365 trail_to_new_predecessor,
4369 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4370 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4371 GNUNET_free_non_null (trail_to_new_predecessor);
4375 /* 3. In case you are successor, then
4376 * 3.1 check if you have a predecessor
4377 * 3.2 if no predecessor, then add the source of this message as your
4378 * predecessor. To add, first you should generate a new trail id,
4379 * invert the trail, send add trail message across new trail, add
4380 * an entry in finger table. Now, destination also have routing
4381 * table entry so add in your routing table also.
4382 * 3.3 If its closer than existing one, then do everything in step 1 and
4383 * free existing finger.
4384 * 3.3 If its same as the old one, then do nothing.
4385 * 3.4 if its not same as old one, and between source and old one, old one
4386 * is the correct predecessor, then construct a trail from source
4387 * to your old successor. scan the trail to remove duplicate entries.
4388 * 4. send verify successor result, with trail id of trail from source to
4389 * me. And also send the new trail from source to reach to its probable
4392 * 1. this function is called from both verify and notify.
4393 * 2. so write in a way that it is used in both.
4396 * Check if you have a predecessor.
4397 * 1. if no predecessor, then add finger as your predecessor. To add, first
4398 * generate a new trail id, invert the trail to get the trail from me to finger,
4399 * add an entry in your routing table, send add trail message to peers which
4400 * are part of trail from me to finger and add finger in finger table.
4401 * 2. If there is a predecessor, then compare existing one and finger.
4402 * 2.1 If finger is correct predecessor, then remove current_predecessor. And
4403 * do everything in step 1 to add finger into finger table.
4404 * 2.2 If current_predecessor is correct predecessor, the construct a trail from
4405 * finger to current_predecessor.
4408 * @param trail_length
4412 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4413 struct GNUNET_PeerIdentity *trail,
4414 unsigned int trail_length)
4416 struct FingerInfo *current_predecessor;
4417 struct GNUNET_PeerIdentity *closest_peer;
4418 uint64_t predecessor_value;
4419 unsigned int is_predecessor = 1;
4421 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4423 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4425 /* No predecessor. Add finger as your predecessor. */
4426 if (GNUNET_NO == current_predecessor->is_present)
4428 update_predecessor (finger, trail, trail_length);
4431 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4435 //test_finger_table_print();
4436 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4437 closest_peer = select_closest_peer (&finger,
4438 ¤t_predecessor->finger_identity,
4439 predecessor_value, is_predecessor);
4441 /* Finger is the closest predecessor. Remove the existing one and add the new
4443 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, &finger))
4445 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4446 update_predecessor (finger, trail, trail_length);
4455 * FIXME: if i have no predecessor and I get a new predecessor but the first
4456 * friend to reach to that hop is congested then?
4457 * 1. check if you are the successor or not.
4458 * 2. if not then get the next hop from routing table, and pass the message,
4459 * 3. In case you are successor, then
4460 * 3.1 check if you have a predecessor
4461 * 3.2 if no predecessor, then add the source of this message as your
4462 * predecessor. To add, first you should generate a new trail id,
4463 * invert the trail, send add trail message across new trail, add
4464 * an entry in finger table. Now, destination also have routing
4465 * table entry so add in your routing table also.
4466 * 3.3 If its closer than existing one, then do everything in step 1 and
4467 * free existing finger.
4468 * 3.3 If its same as the old one, then do nothing.
4469 * 3.4 if its not same as old one, and between source and old one, old one
4470 * is the correct predecessor, then choose the shortest path to reach
4471 * from you to your predecessor. Pass this trail to source of this message.
4472 * It is the responsibility of source peer to scan the trail to reach to
4473 * its new probable successor.
4474 * 4. send verify successor result, with trail id of trail from source to
4475 * me. And also send the trail from me to reach to my predecessor, if
4476 * my_predecessor != source.
4478 * Core handle for p2p verify successor messages.
4479 * @param cls closure
4480 * @param message message
4481 * @param peer peer identity this notification is about
4482 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4485 handle_dht_p2p_verify_successor(void *cls,
4486 const struct GNUNET_PeerIdentity *peer,
4487 const struct GNUNET_MessageHeader *message)
4489 const struct PeerVerifySuccessorMessage *vsm;
4490 struct GNUNET_HashCode trail_id;
4491 struct GNUNET_PeerIdentity successor;
4492 struct GNUNET_PeerIdentity source_peer;
4493 struct GNUNET_PeerIdentity *trail;
4494 struct GNUNET_PeerIdentity *next_hop;
4495 struct GNUNET_PeerIdentity *trail_to_predecessor;
4496 struct FingerInfo *current_predecessor;
4497 struct FriendInfo *target_friend;
4498 unsigned int trail_to_predecessor_length;
4500 unsigned int trail_length;
4502 msize = ntohs (message->size);
4504 /* Here we pass trail to reach from source to successor, and in case successor
4505 * does not have any predecessor, then we will add source as my predecessor.
4506 * So we pass the trail along with trail id. */
4507 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4509 GNUNET_break_op (0);
4513 vsm = (const struct PeerVerifySuccessorMessage *) message;
4514 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4515 sizeof (struct GNUNET_PeerIdentity);
4516 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4517 sizeof (struct GNUNET_PeerIdentity) != 0)
4519 GNUNET_break_op (0);
4523 trail_id = vsm->trail_id;
4524 source_peer = vsm->source_peer;
4525 successor = vsm->successor;
4526 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4528 //FIXME: we can have a check if peer is correct peer which should have
4529 // sent this message. use same function is_sender_peer_correct
4530 // but specify direction so that the function can be used in other functions
4533 /* I am not the successor of source_peer. Pass the message to next_hop on
4535 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4537 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4538 if (NULL == next_hop)
4541 return GNUNET_SYSERR;
4543 GNUNET_assert (NULL !=
4545 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4547 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4548 trail_id, trail, trail_length,
4553 /* I am the destination of this message. */
4555 /* Check if the source_peer could be our predecessor and if yes then update
4557 compare_and_update_predecessor (source_peer, trail, trail_length);
4559 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4561 /* Is source of this message NOT my predecessor. */
4562 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4565 /* if current predecessor is not a friend, we have a trail to reach to it*/
4566 if (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4567 ¤t_predecessor->finger_identity)))
4569 trail_to_predecessor =
4570 trail_source_to_my_predecessor (trail,
4572 &trail_to_predecessor_length);
4577 trail_to_predecessor = NULL;
4578 trail_to_predecessor_length = 0;
4580 GNUNET_assert (NULL !=
4582 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4583 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4584 current_predecessor->finger_identity,
4585 trail_id, trail_to_predecessor,
4586 trail_to_predecessor_length,
4587 GDS_ROUTING_DEST_TO_SRC,
4589 GNUNET_free_non_null (trail_to_predecessor);
4595 * Construct the trail from me to probable successor that goes through current
4596 * successor. Scan this trail to check if you can shortcut the trail somehow.
4597 * In case we can shortcut the trail, don't send trail compression as we don't
4598 * have any entry in routing table.
4599 * @param current_successor
4600 * @param probable_successor
4601 * @param trail_from_curr_to_probable_successor
4602 * @param trail_from_curr_to_probable_successor_length
4603 * @param trail_to_new_successor_length
4606 static struct GNUNET_PeerIdentity *
4607 get_trail_to_new_successor (struct FingerInfo *current_successor,
4608 struct GNUNET_PeerIdentity probable_successor,
4609 const struct GNUNET_PeerIdentity *trail,
4610 unsigned int trail_length,
4611 unsigned int *trail_to_new_successor_length)
4613 struct GNUNET_PeerIdentity *trail_to_new_successor;
4615 /* If the probable successor is a friend, then we don't need to have a trail
4617 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4618 &probable_successor))
4620 trail_to_new_successor = NULL;
4621 *trail_to_new_successor_length = 0;
4622 return trail_to_new_successor;
4626 * FIXME: can we some how use the select_finger_trail here??
4627 * complete this logic.
4628 * 1. Choose the shortest trail to reach to current successor.
4629 * 2. append the trail with the current trail
4630 * 3. scan the trail for duplicate elements
4631 * 4. scan the trail for friend
4632 * 5. get the shortest trail.
4633 * 6. send back the trail.
4640 * Compare probable successor and current successor.
4641 * If the probable successor is the correct successor, then construct the trail
4642 * from me to probable successor that goes through current successor. Scan this
4643 * trail to check if you can shortcut the trail somehow. In case we can short
4644 * cut the trail, don't send trail compression as we don't have any entry in
4646 * Once you have scanned trail, then add an entry in finger table.
4647 * Add an entry in routing table (Only if new successor is NOT a friend).
4648 * @param probable_successor Peer which could be our successor
4649 * @param trail_from_curr_to_probable_successor Trail from current successor
4650 * to probable successor, NOT
4652 * @param trail_from_curr_to_probable_successor_length Total number of peers
4653 * in @a trail_from_curr_to_probable_successor
4656 compare_and_update_successor (struct GNUNET_PeerIdentity probable_successor,
4657 const struct GNUNET_PeerIdentity *trail_from_curr_to_probable_successor,
4658 unsigned int trail_from_curr_to_probable_successor_length)
4660 struct GNUNET_PeerIdentity *closest_peer;
4661 struct GNUNET_PeerIdentity *trail_to_new_successor;
4662 struct GNUNET_HashCode trail_id;
4663 unsigned int trail_to_new_successor_length;
4664 uint64_t successor_value;
4665 struct FingerInfo *current_successor;
4666 struct FriendInfo *target_friend;
4667 unsigned int is_predecessor = 0;
4668 //test_finger_table_print();
4669 current_successor = &finger_table[0];
4670 GNUNET_assert (GNUNET_YES == current_successor->is_present);
4672 /* Compute the 64 bit value of successor identity. We need this as we need to
4673 * find the closest peer w.r.t this value.*/
4674 successor_value = compute_finger_identity_value (0);
4675 closest_peer = select_closest_peer (¤t_successor->finger_identity,
4676 &probable_successor,
4677 successor_value, is_predecessor);
4679 /* If the current_successor is the closest one, then exit. */
4680 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4681 ¤t_successor->finger_identity))
4684 /* probable successor is the closest_peer. */
4686 /* Get the trail to reach to your new successor. */
4687 trail_to_new_successor = get_trail_to_new_successor (current_successor,
4689 trail_from_curr_to_probable_successor,
4690 trail_from_curr_to_probable_successor_length,
4691 &trail_to_new_successor_length);
4692 /* Remove the existing successor. */
4693 remove_existing_finger (current_successor, 0);
4695 /* Generate a new trail id to reach to your new successor. */
4696 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4697 &trail_id, sizeof (trail_id));
4698 add_new_finger (probable_successor, trail_to_new_successor,
4699 trail_to_new_successor_length, trail_id, 0);
4701 /* If probable successor is not a friend, then add an entry in your own
4703 if (trail_to_new_successor_length > 0)
4705 /* FIXME: check that you always add trail entry even if your finger is
4707 GDS_ROUTING_add (trail_id, my_identity, trail_to_new_successor[0]);
4708 GNUNET_assert (NULL !=
4709 (target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4710 &trail_to_new_successor[0])));
4714 /* FIXME: check that you always add trail entry even if your finger is
4716 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4717 GNUNET_assert (NULL !=
4719 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4720 &probable_successor)));
4722 //test_finger_table_print();
4723 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4724 trail_from_curr_to_probable_successor,
4725 trail_from_curr_to_probable_successor_length,
4733 * 1. If you are not the querying peer then pass on the message,
4734 * 2. If you are querying peer, then
4735 * 2.1 is new successor same as old one
4736 * 2.1.1 if yes then do noting
4737 * 2.1.2 if no then you need to notify the new one about your existence,
4738 * 2.1.2,1 also you need to remove the older successor, remove entry
4739 * from finger table, send trail teardown message across all the trail
4740 * of older successor. Call notify new successor with new trail id
4741 * and new trail to reach it.
4742 * Core handle for p2p verify successor result messages.
4743 * @param cls closure
4744 * @param message message
4745 * @param peer peer identity this notification is about
4746 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4749 handle_dht_p2p_verify_successor_result(void *cls,
4750 const struct GNUNET_PeerIdentity *peer,
4751 const struct GNUNET_MessageHeader *message)
4753 const struct PeerVerifySuccessorResultMessage *vsrm;
4754 enum GDS_ROUTING_trail_direction trail_direction;
4755 struct GNUNET_PeerIdentity querying_peer;
4756 struct GNUNET_HashCode trail_id;
4757 struct GNUNET_PeerIdentity *next_hop;
4758 struct FriendInfo *target_friend;
4759 struct GNUNET_PeerIdentity probable_successor;
4760 const struct GNUNET_PeerIdentity *trail;
4761 unsigned int trail_length;
4764 msize = ntohs (message->size);
4765 /* We send a trail to reach from old successor to new successor, if
4766 * old_successor != new_successor.*/
4767 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4769 GNUNET_break_op (0);
4773 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4774 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4775 sizeof (struct GNUNET_PeerIdentity);
4777 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4778 sizeof (struct GNUNET_PeerIdentity) != 0)
4780 GNUNET_break_op (0);
4784 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4785 querying_peer = vsrm->querying_peer;
4786 trail_direction = ntohl (vsrm->trail_direction);
4787 trail_id = vsrm->trail_id;
4788 probable_successor = vsrm->probable_successor;
4790 //FIXME: add a check to ensure that peer from which you got the message is
4792 /* I am the querying_peer. */
4793 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4795 compare_and_update_successor (probable_successor, trail, trail_length);
4799 /*If you are not the querying peer then pass on the message */
4800 GNUNET_assert (NULL != (next_hop =
4801 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
4802 GNUNET_assert (NULL !=
4804 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4805 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4806 vsrm->current_successor,
4807 probable_successor, trail_id,
4810 trail_direction, target_friend);
4816 * Add entry in your routing table if source of the message is not a friend.
4817 * Irrespective if destination peer accepts source peer as predecessor or not,
4818 * we need to add an entry. So, that in next round to verify successor, source
4819 * is able to reach to its successor.
4820 * Check if you are the new successor of this message
4821 * 1. If yes the call function compare_and_update_successor(). This function
4822 * checks if source is real predecessor or not and take action accordingly.
4823 * 2. If not then find the next hop to find the message from the trail that
4824 * you got from the message and pass on the message.
4825 * Core handle for p2p notify new successor messages.
4826 * @param cls closure
4827 * @param message message
4828 * @param peer peer identity this notification is about
4829 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4832 handle_dht_p2p_notify_new_successor(void *cls,
4833 const struct GNUNET_PeerIdentity *peer,
4834 const struct GNUNET_MessageHeader *message)
4836 const struct PeerNotifyNewSuccessorMessage *nsm;
4837 struct GNUNET_PeerIdentity *trail;
4838 struct GNUNET_PeerIdentity source;
4839 struct GNUNET_PeerIdentity new_successor;
4840 struct GNUNET_HashCode trail_id;
4841 struct GNUNET_PeerIdentity next_hop;
4842 struct FriendInfo *target_friend;
4845 uint32_t trail_length;
4847 msize = ntohs (message->size);
4848 /* We have the trail to reach from source to new successor. */
4849 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
4851 GNUNET_break_op (0);
4855 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
4856 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
4857 sizeof (struct GNUNET_PeerIdentity);
4858 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4859 sizeof (struct GNUNET_PeerIdentity) != 0)
4861 GNUNET_break_op (0);
4865 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
4866 source = nsm->source_peer;
4867 new_successor = nsm->new_successor;
4868 trail_id = nsm->trail_id;
4870 //FIXME: add a check to make sure peer is correct.
4872 /* I am the new_successor to source_peer. */
4873 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
4875 GDS_ROUTING_add (trail_id, *peer, my_identity);
4876 compare_and_update_predecessor (source, trail, trail_length);
4880 /* I am part of trail to reach to successor. */
4881 my_index = search_my_index (trail, trail_length);
4884 GNUNET_break_op (0);
4885 return GNUNET_SYSERR;
4887 if (trail_length == my_index)
4888 next_hop = new_successor;
4890 next_hop = trail[my_index + 1];
4892 /* Add an entry in routing table for trail from source to its new successor. */
4893 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
4894 GNUNET_assert (NULL !=
4896 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4897 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
4899 trail_id, target_friend);
4906 * 1. Set the congestion timeout for the friend which is congested and sent
4908 * 2. Check if you were the source of this message
4909 * 2.1 If yes then exit. find_finger_trail_task is scheduled periodically.
4910 * So, we will eventually send a new request to setup trail to finger.
4911 * 2. Check if you can handle more trails through you. (Routing table space)
4912 * 2.1 If not then you are congested. Set your congestion time and pass this
4913 * message to peer before you in the trail setup so far.
4914 * 2.2 If yes, the call find_successor(). It will give you the next hop to
4915 * pass this message.
4916 * 2.2.1 If you are the final destination, then send back the trail setup
4918 * 2.2.2 If you are not the final dest, then send trail setup message to
4920 * Core handler for P2P trail rejection message
4921 * @param cls closure
4922 * @param message message
4923 * @param peer peer identity this notification is about
4924 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4927 handle_dht_p2p_trail_setup_rejection (void *cls,
4928 const struct GNUNET_PeerIdentity *peer,
4929 const struct GNUNET_MessageHeader *message)
4931 const struct PeerTrailRejectionMessage *trail_rejection;
4932 unsigned int trail_length;
4933 const struct GNUNET_PeerIdentity *trail_peer_list;
4934 struct FriendInfo *target_friend;
4935 struct GNUNET_TIME_Relative congestion_timeout;
4936 struct GNUNET_HashCode trail_id;
4937 struct GNUNET_PeerIdentity next_destination;
4938 struct GNUNET_HashCode new_intermediate_trail_id;
4939 struct GNUNET_PeerIdentity next_peer;
4940 struct GNUNET_PeerIdentity source;
4941 struct GNUNET_PeerIdentity *next_hop;
4942 uint64_t ultimate_destination_finger_value;
4943 unsigned int is_predecessor;
4946 msize = ntohs (message->size);
4947 /* We are passing the trail setup so far. */
4948 if (msize < sizeof (struct PeerTrailRejectionMessage))
4950 GNUNET_break_op (0);
4954 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
4955 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
4956 sizeof (struct GNUNET_PeerIdentity);
4957 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4958 sizeof (struct GNUNET_PeerIdentity) != 0)
4960 GNUNET_break_op (0);
4964 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
4965 is_predecessor = ntohl (trail_rejection->is_predecessor);
4966 congestion_timeout = trail_rejection->congestion_time;
4967 source = trail_rejection->source_peer;
4968 trail_id = trail_rejection->trail_id;
4969 ultimate_destination_finger_value =
4970 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
4972 /* First set the congestion time of the friend that sent you this message. */
4973 GNUNET_assert (NULL !=
4975 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4976 target_friend->congestion_timestamp =
4977 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
4978 congestion_timeout);
4980 /* I am the source peer which wants to setup the trail. Do nothing.
4981 * send_find_finger_trail_task is scheduled periodically.*/
4982 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
4985 /* If I am congested then pass this message to peer before me in trail. */
4986 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
4988 struct GNUNET_PeerIdentity *new_trail;
4989 unsigned int new_trail_length;
4991 /* Remove yourself from the trail setup so far. */
4992 if (trail_length == 1)
4995 new_trail_length = 0;
5000 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
5001 sizeof (struct GNUNET_PeerIdentity));
5003 /* Remove myself from the trail. */
5004 new_trail_length = trail_length -1;
5005 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5006 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5009 GNUNET_assert (NULL !=
5011 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5012 GDS_NEIGHBOURS_send_trail_rejection (source,
5013 ultimate_destination_finger_value,
5014 my_identity, is_predecessor,
5015 new_trail,new_trail_length,trail_id,
5016 target_friend, CONGESTION_TIMEOUT);
5018 GNUNET_free (new_trail);
5022 /* Look for next_hop to pass the trail setup message */
5023 next_hop = find_successor (ultimate_destination_finger_value,
5025 &new_intermediate_trail_id,
5028 /* Am I the final destination? */
5029 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))
5031 /* Add an entry in routing table only
5032 * 1. If I am not the original source which sent the request for trail setup
5033 FIXME: check that you always add trail entry even if your finger is
5035 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
5036 GNUNET_assert (GNUNET_YES == GDS_ROUTING_add (trail_id, *peer, my_identity));
5038 if (0 == trail_length)
5041 next_peer = trail_peer_list[trail_length-1];
5043 GNUNET_assert (NULL !=
5045 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5046 GDS_NEIGHBOURS_send_trail_setup_result (source,
5048 target_friend, trail_length,
5051 ultimate_destination_finger_value,
5056 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5058 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5059 peer_list[trail_length] = my_identity;
5061 GNUNET_assert (NULL !=
5063 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5064 GDS_NEIGHBOURS_send_trail_setup (source,
5065 ultimate_destination_finger_value,
5067 target_friend, trail_length + 1, peer_list,
5068 is_predecessor, trail_id,
5069 &new_intermediate_trail_id);
5072 GNUNET_free (next_hop);
5078 * If you are the new first friend, then update prev hop to source of this message
5079 * else get the next hop and pass this message forward to ultimately reach
5081 * Core handle for p2p trail tear compression messages.
5082 * @param cls closure
5083 * @param message message
5084 * @param peer peer identity this notification is about
5085 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5088 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5089 const struct GNUNET_MessageHeader *message)
5091 const struct PeerTrailCompressionMessage *trail_compression;
5092 struct GNUNET_PeerIdentity *next_hop;
5093 struct FriendInfo *target_friend;
5094 struct GNUNET_HashCode trail_id;
5097 msize = ntohs (message->size);
5098 /* Here we pass only the trail id. */
5099 if (msize != sizeof (struct PeerTrailCompressionMessage))
5101 GNUNET_break_op (0);
5105 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5106 trail_id = trail_compression->trail_id;
5107 //FIXME: again check if peer is the correct peer. same logic as
5108 //trail teardown make a generic function.
5110 /* Am I the new first friend to reach to finger of this trail. */
5111 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5114 GNUNET_assert (NULL !=
5115 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5116 &trail_compression->source_peer)));
5117 /* Update your prev hop to source of this message. */
5118 GNUNET_assert (GNUNET_SYSERR !=
5119 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5120 trail_compression->source_peer)));
5124 /* Pass the message to next hop to finally reach to new_first_friend. */
5125 /* FIXME THIS FAILS.*/
5126 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5127 if (NULL == next_hop)
5133 GNUNET_assert (NULL !=
5135 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5137 GDS_ROUTING_remove_trail (trail_id);
5139 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5141 trail_compression->new_first_friend,
5148 * Remove entry from your own routing table and pass the message to next
5149 * peer in the trail.
5150 * Core handler for trail teardown message.
5151 * @param cls closure
5152 * @param message message
5153 * @param peer sender of this messsage.
5154 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5157 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5158 const struct GNUNET_MessageHeader *message)
5160 const struct PeerTrailTearDownMessage *trail_teardown;
5161 enum GDS_ROUTING_trail_direction trail_direction;
5162 struct GNUNET_HashCode trail_id;
5163 struct GNUNET_PeerIdentity *next_hop;
5166 msize = ntohs (message->size);
5168 /* Here we pass only the trail id. */
5169 if (msize != sizeof (struct PeerTrailTearDownMessage))
5171 GNUNET_break_op (0);
5175 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5176 trail_direction = ntohl (trail_teardown->trail_direction);
5177 trail_id = trail_teardown->trail_id;
5179 /* Check if peer is the real peer from which we should get this message.*/
5180 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5181 /* FIXME: is using negation of trail direction correct. */
5183 GNUNET_assert (NULL != (prev_hop =
5184 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5185 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5188 return GNUNET_SYSERR;
5192 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5194 if (NULL == next_hop)
5197 return GNUNET_SYSERR;
5200 /* I am the next hop, which means I am the final destination. */
5201 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5203 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5208 /* If not final destination, then send a trail teardown message to next hop.*/
5209 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5210 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5211 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5219 * Add an entry in your routing table. If you are destination of this message
5220 * then next_hop in routing table should be your own identity. If you are NOT
5221 * destination, then get the next hop and forward message to it.
5222 * Core handle for p2p add trail message.
5223 * @param cls closure
5224 * @param message message
5225 * @param peer peer identity this notification is about
5226 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5229 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5230 const struct GNUNET_MessageHeader *message)
5232 const struct PeerAddTrailMessage *add_trail;
5233 const struct GNUNET_PeerIdentity *trail;
5234 struct GNUNET_HashCode trail_id;
5235 struct GNUNET_PeerIdentity destination_peer;
5236 struct GNUNET_PeerIdentity source_peer;
5237 struct GNUNET_PeerIdentity next_hop;
5238 unsigned int trail_length;
5239 unsigned int my_index;
5242 msize = ntohs (message->size);
5243 /* In this message we pass the whole trail from source to destination as we
5244 * are adding that trail.*/
5245 if (msize < sizeof (struct PeerAddTrailMessage))
5247 GNUNET_break_op (0);
5251 add_trail = (const struct PeerAddTrailMessage *) message;
5252 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5253 sizeof (struct GNUNET_PeerIdentity);
5254 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5255 sizeof (struct GNUNET_PeerIdentity) != 0)
5257 GNUNET_break_op (0);
5261 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5262 destination_peer = add_trail->destination_peer;
5263 source_peer = add_trail->source_peer;
5264 trail_id = add_trail->trail_id;
5266 //FIXME: add a check that sender peer is not malicious. Make it a generic
5267 // function so that it can be used in all other functions where we need the
5268 // same functionality.
5270 /* I am not the destination of the trail. */
5271 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5273 struct FriendInfo *target_friend;
5275 /* Get my location in the trail. */
5276 my_index = search_my_index (trail, trail_length);
5280 GNUNET_break_op (0);
5281 return GNUNET_SYSERR;
5285 if ((trail_length - 1) == my_index)
5288 next_hop = destination_peer;
5292 next_hop = trail[my_index + 1];
5294 /* FIXME: check that you always add trail entry even if your finger is
5296 /* Add in your routing table. */
5297 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5298 GNUNET_assert (NULL !=
5300 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5301 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5302 trail, trail_length, target_friend);
5305 /* FIXME: check that you always add trail entry even if your finger is
5307 /* I am the destination. Add an entry in routing table. */
5308 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5314 * Free the finger trail in which the first friend to reach to a finger is
5315 * disconnected_friend. Also remove entry from routing table for that particular
5317 * @param disconnected_friend PeerIdentity of friend which got disconnected
5318 * @param remove_finger Finger whose trail we need to check if it has
5319 * disconnected_friend as the first hop.
5320 * @return Total number of trails in which disconnected_friend was the first
5324 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5325 struct FingerInfo *remove_finger)
5327 unsigned int matching_trails_count;
5330 /* Number of trails with disconnected_friend as the first hop in the trail
5331 * to reach from me to remove_finger, NOT including endpoints. */
5332 matching_trails_count = 0;
5334 /* Iterate over all the trails of finger. */
5335 for (i = 0; i < remove_finger->trails_count; i++)
5337 struct Trail *trail;
5338 trail = &remove_finger->trail_list[i];
5340 /* This assertion is ensure that there are no gaps in the trail list.
5341 REMOVE IT AFTERWARDS. */
5342 GNUNET_assert (GNUNET_YES == trail->is_present);
5344 /* First friend to reach to finger is disconnected_peer. */
5345 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5346 disconnected_friend))
5348 struct GNUNET_PeerIdentity *next_hop;
5349 struct FriendInfo *remove_friend;
5351 GNUNET_assert (NULL !=
5353 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5354 disconnected_friend)));
5355 /* FIXME: removing no but check it. */
5356 //remove_friend->trails_count--;
5357 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5358 GDS_ROUTING_SRC_TO_DEST);
5360 /* Here it may happen that as all the peers got disconnected, the entry in
5361 routing table for that particular trail has been removed, because the
5362 previously disconnected peer was either a next hop or prev hop of that
5364 if (NULL == next_hop)
5367 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5369 matching_trails_count++;
5370 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5373 trail->is_present = GNUNET_NO;
5376 return matching_trails_count;
5381 * Iterate over finger_table entries.
5382 * 0. Ignore finger which is my_identity or if no valid entry present at
5383 * that finger index.
5384 * 1. If disconnected_friend is a finger, then remove the routing entry from
5385 your own table. Free the trail.
5386 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5387 * 2.1 Remove all the trails and entry from routing table in which disconnected
5388 * friend is the first friend in the trail. If disconnected_friend is the
5389 * first friend in all the trails to reach finger, then remove the finger.
5390 * @param disconnected_friend Peer identity of friend which got disconnected.
5393 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5395 struct FingerInfo *remove_finger;
5396 struct FriendInfo *remove_friend;
5397 int removed_trails_count;
5400 /* Iterate over finger table entries. */
5401 for (i = 0; i < MAX_FINGERS; i++)
5403 remove_finger = &finger_table[i];
5405 /* No finger stored at this trail index. */
5406 if (GNUNET_NO == remove_finger->is_present)
5409 /* I am my own finger, then ignore this finger. */
5410 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5414 /* Is disconnected_peer a finger? */
5415 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5416 &remove_finger->finger_identity))
5418 struct GNUNET_PeerIdentity *next_hop;
5419 struct GNUNET_HashCode trail_id;
5422 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5423 trail_id = remove_finger->trail_list[0].trail_id;
5427 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5430 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5431 &remove_finger->finger_identity)));
5432 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5433 GNUNET_assert (NULL !=
5435 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5436 disconnected_peer)));
5439 remove_finger->trail_list[0].is_present = GNUNET_NO;
5440 //GNUNET_assert (0 != remove_friend->trails_count);
5441 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5442 remove_finger->is_present = GNUNET_NO;
5443 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5447 /* If finger is a friend but not disconnected_friend, then continue. */
5448 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5449 &remove_finger->finger_identity))
5452 /* Iterate over the list of trails to reach remove_finger. Check if
5453 * disconnected_friend is the first friend in any of the trail. */
5454 removed_trails_count = remove_matching_trails (disconnected_peer,
5456 remove_finger->trails_count =
5457 remove_finger->trails_count - removed_trails_count;
5458 /* All the finger trails had disconnected_friend as the first friend,
5459 * so free the finger. */
5460 if (remove_finger->trails_count == 0)
5462 remove_finger->is_present = GNUNET_NO;
5463 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5470 * Method called whenever a peer disconnects.
5472 * @param cls closure
5473 * @param peer peer identity this notification is about
5476 handle_core_disconnect (void *cls,
5477 const struct GNUNET_PeerIdentity *peer)
5479 struct FriendInfo *remove_friend;
5481 /* If disconnected to own identity, then return. */
5482 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5485 GNUNET_assert (NULL != (remove_friend =
5486 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5488 /* Remove fingers with peer as first friend or if peer is a finger. */
5489 remove_matching_fingers (peer);
5491 /* Remove any trail from routing table of which peer is a part of. This function
5492 * internally sends a trail teardown message in the direction of which
5493 * disconnected peer is not part of. */
5494 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5496 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5498 /* Remove peer from friend_peermap. */
5499 GNUNET_assert (GNUNET_YES ==
5500 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5504 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5507 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5509 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5510 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5519 * Method called whenever a peer connects.
5521 * @param cls closure
5522 * @param peer_identity peer identity this notification is about
5525 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5527 struct FriendInfo *friend;
5529 /* Check for connect to self message */
5530 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5533 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5535 /* If peer already exists in our friend_peermap, then exit. */
5536 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5543 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
5546 friend = GNUNET_new (struct FriendInfo);
5547 friend->id = *peer_identity;
5549 GNUNET_assert (GNUNET_OK ==
5550 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5551 peer_identity, friend,
5552 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5555 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5556 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5557 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5562 * To be called on core init/fail.
5564 * @param cls service closure
5565 * @param identity the public identity of this peer
5568 core_init (void *cls,
5569 const struct GNUNET_PeerIdentity *identity)
5571 my_identity = *identity;
5572 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5573 "my_indentity = %s\n",GNUNET_i2s(&my_identity));
5578 * Initialize finger table entries.
5581 finger_table_init ()
5586 for(i = 0; i < MAX_FINGERS; i++)
5588 finger_table[i].is_present = GNUNET_NO;
5589 for (j = 0; j < MAXIMUM_TRAILS_PER_FINGER; j++)
5590 finger_table[i].trail_list[j].is_present = GNUNET_NO;
5591 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5597 * Initialize neighbours subsystem.
5598 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5601 GDS_NEIGHBOURS_init (void)
5603 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5604 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5605 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5606 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5607 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5608 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5609 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5610 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5611 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5612 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5613 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5614 sizeof (struct PeerTrailCompressionMessage)},
5615 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5616 sizeof (struct PeerTrailTearDownMessage)},
5617 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5622 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5623 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5624 GNUNET_NO, core_handlers);
5625 if (NULL == core_api)
5626 return GNUNET_SYSERR;
5628 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5629 finger_table_init ();
5636 * Shutdown neighbours subsystem.
5639 GDS_NEIGHBOURS_done (void)
5641 if (NULL == core_api)
5644 GNUNET_CORE_disconnect (core_api);
5647 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5648 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5649 friend_peermap = NULL;
5651 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5654 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5655 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5663 * @return my identity
5665 struct GNUNET_PeerIdentity
5666 GDS_NEIGHBOURS_get_my_id (void)
5671 /* end of gnunet-service-xdht_neighbours.c */