2 This file is part of GNUnet.
3 (C) 2009-2014 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file dht/gnunet-service-xdht_neighbours.c
23 * @brief GNUnet DHT service's finger and friend table management code
24 * @author Supriti Singh
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_ats_service.h"
34 #include "gnunet_core_service.h"
35 #include "gnunet_datacache_lib.h"
36 #include "gnunet_transport_service.h"
37 #include "gnunet_dht_service.h"
38 #include "gnunet_statistics_service.h"
39 #include "gnunet-service-xdht.h"
40 #include "gnunet-service-xdht_clients.h"
41 #include "gnunet-service-xdht_datacache.h"
42 #include "gnunet-service-xdht_neighbours.h"
43 #include "gnunet-service-xdht_routing.h"
49 * 1. In X-Vine paper, there is no policy defined for replicating the data to
50 * recover in case of peer failure. We can do it in Chord way. In R5N, the key
51 * is hashed and then data is stored according to the key value generated after
57 * Maximum possible fingers (including predecessor) of a peer
59 #define MAX_FINGERS 65
62 * Maximum allowed number of pending messages per friend peer.
64 #define MAXIMUM_PENDING_PER_FRIEND 64
67 * How long to wait before sending another find finger trail request
69 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 5)
72 * How long at most to wait for transmission of a request to a friend ?
74 #define GET_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
77 * Duration for which I may remain congested.
78 * Note: Its a static value. In future, a peer may do some analysis and calculate
79 * congestion_timeout based on 'some' parameters.
81 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
84 * Maximum number of trails allowed to go through a friend.
86 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
89 * Maximum number of trails stored per finger.
91 #define MAXIMUM_TRAILS_PER_FINGER 1
94 * Finger map index for predecessor entry in finger table.
96 #define PREDECESSOR_FINGER_ID 64
99 * Wrap around in peer identity circle.
101 #define PEER_IDENTITES_WRAP_AROUND pow(2, 64) - 1
104 * FIXME: Its use only at 3 places check if you can remove it.
105 * To check if a finger is predecessor or not.
107 enum GDS_NEIGHBOURS_finger_type
109 GDS_FINGER_TYPE_PREDECESSOR = 1,
110 GDS_FINGER_TYPE_NON_PREDECESSOR = 0
113 GNUNET_NETWORK_STRUCT_BEGIN
118 struct PeerPutMessage
121 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
123 struct GNUNET_MessageHeader header;
128 uint32_t options GNUNET_PACKED;
133 uint32_t block_type GNUNET_PACKED;
138 uint32_t hop_count GNUNET_PACKED;
141 * Replication level for this message
142 * In the current implementation, this value is not used.
144 uint32_t desired_replication_level GNUNET_PACKED;
147 * Length of the PUT path that follows (if tracked).
149 uint32_t put_path_length GNUNET_PACKED;
152 * Best known destination (could be my friend or finger) which should
153 * get this message next.
155 struct GNUNET_PeerIdentity best_known_destination;
158 * In case best_known_destination is a finger, then trail to reach
159 * to that finger. Else its default value is 0.
161 struct GNUNET_HashCode intermediate_trail_id;
164 * When does the content expire?
166 struct GNUNET_TIME_AbsoluteNBO expiration_time;
169 * The key to store the value under.
171 struct GNUNET_HashCode key GNUNET_PACKED;
173 /* put path (if tracked) */
182 struct PeerGetMessage
185 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
187 struct GNUNET_MessageHeader header;
192 uint32_t options GNUNET_PACKED;
195 * Desired content type.
197 uint32_t block_type GNUNET_PACKED;
202 uint32_t hop_count GNUNET_PACKED;
205 * Desired replication level for this request.
206 * In the current implementation, this value is not used.
208 uint32_t desired_replication_level GNUNET_PACKED;
211 * Total number of peers in get path.
213 unsigned int get_path_length;
216 * Best known destination (could be my friend or finger) which should
217 * get this message next.
219 struct GNUNET_PeerIdentity best_known_destination;
222 * In case best_known_destination is a finger, then trail to reach
223 * to that finger. Else its default value is 0.
225 struct GNUNET_HashCode intermediate_trail_id;
228 * The key we are looking for.
230 struct GNUNET_HashCode key;
233 /* struct GNUNET_PeerIdentity[]*/
239 struct PeerGetResultMessage
242 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
244 struct GNUNET_MessageHeader header;
247 * The type for the data.
249 uint32_t type GNUNET_PACKED;
252 * Number of peers recorded in the outgoing path from source to the
253 * stored location of this message.
255 uint32_t put_path_length GNUNET_PACKED;
258 * Length of the GET path that follows (if tracked).
260 uint32_t get_path_length GNUNET_PACKED;
263 * Peer which queried for get and should get the result.
265 struct GNUNET_PeerIdentity querying_peer;
268 * When does the content expire?
270 struct GNUNET_TIME_Absolute expiration_time;
273 * The key of the corresponding GET request.
275 struct GNUNET_HashCode key;
277 /* put path (if tracked) */
279 /* get path (if tracked) */
286 * P2P Trail setup message
288 struct PeerTrailSetupMessage
291 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
293 struct GNUNET_MessageHeader header;
296 * Is source_peer trying to setup the trail to a predecessor or any finger.
298 uint32_t is_predecessor;
301 * Peer closest to this value will be our finger.
303 uint64_t final_destination_finger_value;
306 * Source peer which wants to setup the trail to one of its finger.
308 struct GNUNET_PeerIdentity source_peer;
311 * Best known destination (could be my friend or finger) which should
312 * get this message next.
314 struct GNUNET_PeerIdentity best_known_destination;
317 * In case best_known_destination is a finger, then trail id of trail to
318 * reach to this finger.
320 struct GNUNET_HashCode intermediate_trail_id;
323 * Trail id for trail which we are trying to setup.
325 struct GNUNET_HashCode trail_id;
327 /* List of peers which are part of trail setup so far.
328 * Trail does NOT include source_peer and peer which will be closest to
329 * ultimate_destination_finger_value.
330 * struct GNUNET_PeerIdentity trail[]
335 * P2P Trail Setup Result message
337 struct PeerTrailSetupResultMessage
341 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
343 struct GNUNET_MessageHeader header;
346 * Finger to which we have found the path.
348 struct GNUNET_PeerIdentity finger_identity;
351 * Peer which started trail_setup to find trail to finger_identity
353 struct GNUNET_PeerIdentity querying_peer;
356 * Is the trail setup to querying_peer's predecessor or finger?
358 uint32_t is_predecessor;
361 * Value to which finger_identity is the closest peer.
363 uint64_t ulitmate_destination_finger_value;
366 * Identifier of the trail from querying peer to finger_identity, NOT
367 * including both endpoints.
369 struct GNUNET_HashCode trail_id;
371 /* List of peers which are part of the trail from querying peer to
372 * finger_identity, NOT including both endpoints.
373 * struct GNUNET_PeerIdentity trail[]
378 * P2P Verify Successor Message.
380 struct PeerVerifySuccessorMessage
383 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
385 struct GNUNET_MessageHeader header;
388 * Peer which wants to verify its successor.
390 struct GNUNET_PeerIdentity source_peer;
393 * Source Peer's current successor.
395 struct GNUNET_PeerIdentity successor;
398 * Identifier of trail to reach from source_peer to successor.
400 struct GNUNET_HashCode trail_id;
402 /* List of the peers which are part of trail to reach from source_peer
403 * to successor, NOT including them
404 * struct GNUNET_PeerIdentity trail[]
409 * P2P Verify Successor Result Message
411 struct PeerVerifySuccessorResultMessage
414 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
416 struct GNUNET_MessageHeader header;
419 * Peer which sent the request to verify its successor.
421 struct GNUNET_PeerIdentity querying_peer;
424 * Successor to which PeerVerifySuccessorMessage was sent.
426 struct GNUNET_PeerIdentity current_successor;
429 * Current Predecessor of source_successor. It can be same as querying peer
430 * or different. In case it is different then it can be querying_peer's
431 * probable successor.
433 struct GNUNET_PeerIdentity probable_successor;
436 * Trail identifier of trail from querying_peer to current_successor.
438 struct GNUNET_HashCode trail_id;
441 * Direction in which we are looking at the trail.
443 uint32_t trail_direction;
445 /* In case probable_successor != querying_peer, then trail to reach from
446 * querying_peer to probable_successor, NOT including end points.
447 * struct GNUNET_PeerIdentity trail[]
452 * P2P Notify New Successor Message.
454 struct PeerNotifyNewSuccessorMessage
457 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
459 struct GNUNET_MessageHeader header;
462 * Peer which wants to notify its new successor.
464 struct GNUNET_PeerIdentity source_peer;
467 * New successor of source_peer.
469 struct GNUNET_PeerIdentity new_successor;
472 * Unique identifier of the trail from source_peer to new_successor,
473 * NOT including the endpoints.
475 struct GNUNET_HashCode trail_id;
477 /* List of peers in trail from source_peer to new_successor,
478 * NOT including the endpoints.
479 * struct GNUNET_PeerIdentity trail[]
484 * P2P Trail Compression Message.
486 struct PeerTrailCompressionMessage
489 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION
491 struct GNUNET_MessageHeader header;
494 * Source peer of this trail.
496 struct GNUNET_PeerIdentity source_peer;
499 * Trail from source_peer to destination_peer compressed such that
500 * new_first_friend is the first hop in the trail from source to
503 struct GNUNET_PeerIdentity new_first_friend;
506 * Unique identifier of trail.
508 struct GNUNET_HashCode trail_id;
513 * P2P Trail Tear Down message.
515 struct PeerTrailTearDownMessage
518 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
520 struct GNUNET_MessageHeader header;
523 * Unique identifier of the trail.
525 struct GNUNET_HashCode trail_id;
528 * Direction of trail.
530 uint32_t trail_direction;
535 * P2P Trail Rejection Message.
537 struct PeerTrailRejectionMessage
540 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
542 struct GNUNET_MessageHeader header;
545 * Peer which wants to set up the trail.
547 struct GNUNET_PeerIdentity source_peer;
550 * Peer which sent trail rejection message as it it congested.
552 struct GNUNET_PeerIdentity congested_peer;
555 * Peer identity closest to this value will be finger of
558 uint64_t ultimate_destination_finger_value;
561 * Is source_peer trying to setup the trail to its predecessor or finger.
563 uint32_t is_predecessor;
566 * Identifier for the trail that source peer is trying to setup.
568 struct GNUNET_HashCode trail_id;
571 * Relative time for which congested_peer will remain congested.
573 struct GNUNET_TIME_Relative congestion_time;
575 /* Trail_list from source_peer to peer which sent the message for trail setup
576 * to congested peer. This trail does NOT include source_peer.
577 struct GNUNET_PeerIdnetity trail[]*/
581 * P2P Add Trail Message.
583 struct PeerAddTrailMessage
586 * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
588 struct GNUNET_MessageHeader header;
591 * Source of the routing trail.
593 struct GNUNET_PeerIdentity source_peer;
596 * Destination of the routing trail.
598 struct GNUNET_PeerIdentity destination_peer;
601 * Unique identifier of the trail from source_peer to destination_peer,
602 * NOT including the endpoints.
604 struct GNUNET_HashCode trail_id;
606 /* Trail from source peer to destination peer, NOT including them.
607 * struct GNUNET_PeerIdentity trail[]
611 GNUNET_NETWORK_STRUCT_END
614 * Linked list of messages to send to a particular other peer.
616 struct P2PPendingMessage
619 * Pointer to next item in the list
621 struct P2PPendingMessage *next;
624 * Pointer to previous item in the list
626 struct P2PPendingMessage *prev;
629 * Message importance level. FIXME: used? useful?
631 unsigned int importance;
634 * When does this message time out?
636 struct GNUNET_TIME_Absolute timeout;
639 * Actual message to be sent, allocated at the end of the struct:
640 * // msg = (cast) &pm[1];
641 * // memcpy (&pm[1], data, len);
643 const struct GNUNET_MessageHeader *msg;
648 * Entry in friend_peermap.
655 struct GNUNET_PeerIdentity id;
658 * Number of trails for which this friend is the first hop or if the friend
661 unsigned int trails_count;
664 * Count of outstanding messages for this friend.
666 unsigned int pending_count;
669 * In case not 0, then amount of time for which this friend is congested.
671 struct GNUNET_TIME_Absolute congestion_timestamp;
674 * Head of pending messages to be sent to this friend.
676 struct P2PPendingMessage *head;
679 * Tail of pending messages to be sent to this friend.
681 struct P2PPendingMessage *tail;
684 * Core handle for sending messages to this friend.
686 struct GNUNET_CORE_TransmitHandle *th;
691 * An individual element of the trail to reach to a finger.
696 * Pointer to next item in the list
698 struct Trail_Element *next;
701 * Pointer to prev item in the list
703 struct Trail_Element *prev;
706 * An element in this trail.
708 struct GNUNET_PeerIdentity peer;
712 * FIXME: removed first_friend_trails_count, need to write a function
713 * to calculate each time we need it. Else, keep a pointer to first
714 * friend of in the trail.
715 * Information about an individual trail.
722 struct Trail_Element *trail_head;
727 struct Trail_Element *trail_tail;
730 * Unique identifier of this trail.
732 struct GNUNET_HashCode trail_id;
735 * Length of trail pointed
737 unsigned int trail_length;
740 * Is there a valid trail entry.
742 unsigned int is_present;
746 * An entry in finger_table
753 struct GNUNET_PeerIdentity finger_identity;
756 * Is any finger stored at this finger index.
758 unsigned int is_present;
761 * Index in finger peer map
763 uint32_t finger_table_index;
766 * Number of trails setup so far for this finger.
767 * Should not cross MAXIMUM_TRAILS_PER_FINGER.
769 uint32_t trails_count;
772 * Array of trails to reach to this finger.
774 struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER];
779 * Stores information about the peer which is closest to destination_finger_value.
780 * 'closest' can be either successor or predecessor depending on is_predecessor
786 * Destination finger value.
788 uint64_t destination_finger_value;
791 * Is finger_value a predecessor or any other finger.
793 unsigned int is_predecessor;
796 * Trail id to reach to peer.
797 * In case peer is my identity or friend, it is set to 0.
799 struct GNUNET_HashCode trail_id;
802 * Next destination. In case of friend and my_identity , it is same as next_hop
803 * In case of finger it is finger identity.
805 struct GNUNET_PeerIdentity best_known_destination;
808 * In case best_known_destination is a finger, then first friend in the trail
809 * to reach to it. In other case, same as best_known_destination.
811 struct GNUNET_PeerIdentity next_hop;
816 * Data structure to store the trail chosen to reach to finger.
818 struct Selected_Finger_Trail
821 * First friend in the trail to reach finger.
823 struct FriendInfo friend;
826 * Identifier of this trail.
828 struct GNUNET_HashCode trail_id;
831 * Total number of peers in this trail.
833 unsigned int trail_length;
837 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
838 * get our first friend.
840 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
843 * Identity of this peer.
845 static struct GNUNET_PeerIdentity my_identity;
848 * Peer map of all the friends of a peer
850 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
853 * Array of all the fingers.
855 static struct FingerInfo finger_table [MAX_FINGERS];
860 static struct GNUNET_CORE_Handle *core_api;
863 * The current finger index that we have want to find trail to. We start the
864 * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID
865 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
866 * we reset this index to 0.
868 static unsigned int current_search_finger_index;
872 * Called when core is ready to send a message we asked for
873 * out to the destination.
875 * @param cls the 'struct FriendInfo' of the target friend
876 * @param size number of bytes available in buf
877 * @param buf where the callee should write the message
878 * @return number of bytes written to buf
881 core_transmit_notify (void *cls, size_t size, void *buf)
883 struct FriendInfo *peer = cls;
885 struct P2PPendingMessage *pending;
890 while ((NULL != (pending = peer->head)) &&
891 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
893 peer->pending_count--;
894 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
895 GNUNET_free (pending);
899 /* no messages pending */
905 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
906 GNUNET_CORE_PRIO_BEST_EFFORT,
907 GNUNET_TIME_absolute_get_remaining
908 (pending->timeout), &peer->id,
909 ntohs (pending->msg->size),
910 &core_transmit_notify, peer);
911 GNUNET_break (NULL != peer->th);
915 while ((NULL != (pending = peer->head)) &&
916 (size - off >= (msize = ntohs (pending->msg->size))))
918 /*GNUNET_STATISTICS_update (GDS_stats,
920 ("# Bytes transmitted to other peers"), msize,
922 memcpy (&cbuf[off], pending->msg, msize);
924 peer->pending_count--;
925 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
926 GNUNET_free (pending);
928 if (peer->head != NULL)
931 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
932 GNUNET_CORE_PRIO_BEST_EFFORT,
933 GNUNET_TIME_absolute_get_remaining
934 (pending->timeout), &peer->id, msize,
935 &core_transmit_notify, peer);
936 GNUNET_break (NULL != peer->th);
943 * Transmit all messages in the friend's message queue.
945 * @param peer message queue to process
948 process_friend_queue (struct FriendInfo *peer)
950 struct P2PPendingMessage *pending;
952 if (NULL == (pending = peer->head))
954 if (NULL != peer->th)
957 GNUNET_STATISTICS_update (GDS_stats,
959 ("# Bytes of bandwidth requested from core"),
960 ntohs (pending->msg->size), GNUNET_NO);
963 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
965 GNUNET_TIME_absolute_get_remaining
966 (pending->timeout), &peer->id,
967 ntohs (pending->msg->size),
968 &core_transmit_notify, peer);
969 GNUNET_break (NULL != peer->th);
974 * Construct a trail setup message and forward it to target_friend
975 * @param source_peer Peer which wants to setup the trail
976 * @param ultimate_destination_finger_value Peer identity closest to this value
977 * will be finger to @a source_peer
978 * @param best_known_destination Best known destination (could be finger or friend)
979 * which should get this message. In case it is
980 * friend, then it is same as target_friend
981 * @param target_friend Friend to which message is forwarded now.
982 * @param trail_length Total number of peers in trail setup so far.
983 * @param trail_peer_list Trail setup so far
984 * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
985 * @param trail_id Unique identifier for the trail we are trying to setup.
986 * @param intermediate_trail_id Trail id of intermediate trail to reach to
987 * best_known_destination when its a finger. If not
988 * used then set to 0.
991 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
992 uint64_t ultimate_destination_finger_value,
993 struct GNUNET_PeerIdentity best_known_destination,
994 struct FriendInfo *target_friend,
995 unsigned int trail_length,
996 const struct GNUNET_PeerIdentity *trail_peer_list,
997 unsigned int is_predecessor,
998 struct GNUNET_HashCode trail_id,
999 struct GNUNET_HashCode intermediate_trail_id)
1001 struct P2PPendingMessage *pending;
1002 struct PeerTrailSetupMessage *tsm;
1003 struct GNUNET_PeerIdentity *peer_list;
1006 msize = sizeof (struct PeerTrailSetupMessage) +
1007 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1009 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1015 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1017 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1021 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1022 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1023 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1024 pending->msg = &tsm->header;
1025 tsm->header.size = htons (msize);
1026 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1027 tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1028 tsm->source_peer = source_peer;
1029 tsm->best_known_destination = best_known_destination;
1030 tsm->is_predecessor = htonl (is_predecessor);
1031 tsm->trail_id = trail_id;
1032 tsm->intermediate_trail_id = intermediate_trail_id;
1034 if (trail_length > 0)
1036 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1037 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1040 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1041 target_friend->pending_count++;
1042 process_friend_queue (target_friend);
1047 * Construct a trail setup result message and forward it to target friend.
1048 * @param querying_peer Peer which sent the trail setup request and should get
1050 * @param Finger Peer to which the trail has been setup to.
1051 * @param target_friend Friend to which this message should be forwarded.
1052 * @param trail_length Numbers of peers in the trail.
1053 * @param trail_peer_list Peers which are part of the trail from
1054 * querying_peer to Finger, NOT including them.
1055 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1056 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1058 * @param trail_id Unique identifier of the trail.
1061 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1062 struct GNUNET_PeerIdentity finger,
1063 struct FriendInfo *target_friend,
1064 unsigned int trail_length,
1065 const struct GNUNET_PeerIdentity *trail_peer_list,
1066 unsigned int is_predecessor,
1067 uint64_t ultimate_destination_finger_value,
1068 struct GNUNET_HashCode trail_id)
1070 struct P2PPendingMessage *pending;
1071 struct PeerTrailSetupResultMessage *tsrm;
1072 struct GNUNET_PeerIdentity *peer_list;
1075 msize = sizeof (struct PeerTrailSetupResultMessage) +
1076 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1078 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1084 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1086 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1090 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1091 pending->importance = 0;
1092 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1093 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1094 pending->msg = &tsrm->header;
1095 tsrm->header.size = htons (msize);
1096 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1097 tsrm->querying_peer = querying_peer;
1098 tsrm->finger_identity = finger;
1099 tsrm->is_predecessor = htonl (is_predecessor);
1100 tsrm->trail_id = trail_id;
1101 tsrm->ulitmate_destination_finger_value =
1102 GNUNET_htonll (ultimate_destination_finger_value);
1103 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1105 if (trail_length > 0)
1107 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1109 /* Send the message to chosen friend. */
1110 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1111 target_friend->pending_count++;
1112 process_friend_queue (target_friend);
1117 * Send trail rejection message to target friend
1118 * @param source_peer Peer which is trying to setup the trail.
1119 * @param ultimate_destination_finger_value Peer closest to this value will be
1120 * @a source_peer's finger
1121 * @param congested_peer Peer which sent this message as it is congested.
1122 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1123 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1124 * by congested_peer. This does NOT include @a source_peer
1125 * and congested_peer.
1126 * @param trail_length Total number of peers in trail_peer_list, NOT including
1127 * @a source_peer and @a congested_peer
1128 * @param trail_id Unique identifier of this trail.
1129 * @param congestion_timeout Duration given by congested peer as an estimate of
1130 * how long it may remain congested.
1133 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1134 uint64_t ultimate_destination_finger_value,
1135 struct GNUNET_PeerIdentity congested_peer,
1136 unsigned int is_predecessor,
1137 const struct GNUNET_PeerIdentity *trail_peer_list,
1138 unsigned int trail_length,
1139 struct GNUNET_HashCode trail_id,
1140 struct FriendInfo *target_friend,
1141 const struct GNUNET_TIME_Relative congestion_timeout)
1143 struct PeerTrailRejectionMessage *trm;
1144 struct P2PPendingMessage *pending;
1145 struct GNUNET_PeerIdentity *peer_list;
1148 msize = sizeof (struct PeerTrailRejectionMessage) +
1149 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1151 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1157 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1159 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1163 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1164 pending->importance = 0;
1165 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1166 trm = (struct PeerTrailRejectionMessage *)&pending[1];
1167 pending->msg = &trm->header;
1168 trm->header.size = htons (msize);
1169 trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1170 trm->source_peer = source_peer;
1171 trm->congested_peer = congested_peer;
1172 trm->congestion_time = congestion_timeout;
1173 trm->is_predecessor = htonl (is_predecessor);
1174 trm->trail_id = trail_id;
1175 trm->ultimate_destination_finger_value =
1176 GNUNET_htonll (ultimate_destination_finger_value);
1178 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1179 if (trail_length > 0)
1181 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1184 /* Send the message to chosen friend. */
1185 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1186 target_friend->pending_count++;
1187 process_friend_queue (target_friend);
1192 * Construct a verify successor message and forward it to target_friend.
1193 * @param source_peer Peer which wants to verify its successor.
1194 * @param successor Peer which is @a source_peer's current successor.
1195 * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1196 * NOT including them.
1197 * @param trail List of peers which are part of trail to reach from @a source_peer
1198 * to @a successor, NOT including them.
1199 * @param trail_length Total number of peers in @a trail.
1200 * @param target_friend Next friend to get this message.
1203 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1204 struct GNUNET_PeerIdentity successor,
1205 struct GNUNET_HashCode trail_id,
1206 struct GNUNET_PeerIdentity *trail,
1207 unsigned int trail_length,
1208 struct FriendInfo *target_friend)
1210 struct PeerVerifySuccessorMessage *vsm;
1211 struct P2PPendingMessage *pending;
1212 struct GNUNET_PeerIdentity *peer_list;
1215 msize = sizeof (struct PeerVerifySuccessorMessage) +
1216 (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1217 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1223 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1225 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1229 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1230 pending->importance = 0; /* FIXME */
1231 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1232 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1233 pending->msg = &vsm->header;
1234 vsm->header.size = htons (msize);
1235 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1236 vsm->source_peer = source_peer;
1237 vsm->successor = successor;
1238 vsm->trail_id = trail_id;
1240 if (trail_length != 0)
1242 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1243 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1246 /* Send the message to chosen friend. */
1247 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1248 target_friend->pending_count++;
1249 process_friend_queue (target_friend);
1254 * FIXME: In every function we pass target friend except for this one.
1255 * so, either change everything or this one. also, should se just store
1256 * the pointer to friend in routing table rather than gnunet_peeridentity.
1257 * if yes then we should keep friend info in.h andmake lot of changes.
1258 * Construct a trail teardown message and forward it to target friend.
1259 * @param trail_id Unique identifier of the trail.
1260 * @param trail_direction Direction of trail.
1261 * @param target_friend Friend to get this message.
1264 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1265 unsigned int trail_direction,
1266 struct GNUNET_PeerIdentity peer)
1268 struct PeerTrailTearDownMessage *ttdm;
1269 struct P2PPendingMessage *pending;
1270 struct FriendInfo *target_friend;
1273 msize = sizeof (struct PeerTrailTearDownMessage);
1275 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1281 /*FIXME:In what case friend can be null. ?*/
1282 if (NULL == (target_friend =
1283 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1286 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1288 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1292 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1293 pending->importance = 0; /* FIXME */
1294 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1295 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1296 pending->msg = &ttdm->header;
1297 ttdm->header.size = htons (msize);
1298 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1299 ttdm->trail_id = trail_id;
1300 ttdm->trail_direction = htonl (trail_direction);
1302 /* Send the message to chosen friend. */
1303 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1304 target_friend->pending_count++;
1305 process_friend_queue (target_friend);
1310 * Construct a verify successor result message and send it to target_friend
1311 * @param querying_peer Peer which sent the verify successor message.
1312 * @param source_successor Current_successor of @a querying_peer.
1313 * @param current_predecessor Current predecessor of @a successor. Could be same
1314 * or different from @a querying_peer.
1315 * @param trail_id Unique identifier of the trail from @a querying_peer to
1316 * @a successor, NOT including them.
1317 * @param trail List of peers which are part of trail from @a querying_peer to
1318 * @a successor, NOT including them.
1319 * @param trail_length Total number of peers in @a trail
1320 * @param trail_direction Direction in which we are sending the message. In this
1321 * case we are sending result from @a successor to @a querying_peer.
1322 * @param target_friend Next friend to get this message.
1325 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1326 struct GNUNET_PeerIdentity current_successor,
1327 struct GNUNET_PeerIdentity probable_successor,
1328 struct GNUNET_HashCode trail_id,
1329 const struct GNUNET_PeerIdentity *trail,
1330 unsigned int trail_length,
1331 enum GDS_ROUTING_trail_direction trail_direction,
1332 struct FriendInfo *target_friend)
1334 struct PeerVerifySuccessorResultMessage *vsmr;
1335 struct P2PPendingMessage *pending;
1336 struct GNUNET_PeerIdentity *peer_list;
1339 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1340 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1342 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1348 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1350 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1354 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1355 pending->importance = 0; /* FIXME */
1356 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1357 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1358 pending->msg = &vsmr->header;
1359 vsmr->header.size = htons (msize);
1360 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1361 vsmr->querying_peer = querying_peer;
1362 vsmr->current_successor = current_successor;
1363 vsmr->probable_successor = probable_successor;
1364 vsmr->trail_direction = htonl (trail_direction);
1365 vsmr->trail_id = trail_id;
1367 if (trail_length > 0)
1369 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1370 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1373 /* Send the message to chosen friend. */
1374 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1375 target_friend->pending_count++;
1376 process_friend_queue (target_friend);
1381 * Construct a notify new successor message and send it to target_friend
1382 * @param source_peer Peer which wants to notify to its new successor that it
1383 * could be its predecessor.
1384 * @param successor New successor of @a source_peer
1385 * @param successor_trail List of peers in Trail to reach from
1386 * @a source_peer to @a new_successor, NOT including
1388 * @param successor_trail_length Total number of peers in @a new_successor_trail.
1389 * @param successor_trail_id Unique identifier of @a new_successor_trail.
1390 * @param target_friend Next friend to get this message.
1393 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1394 struct GNUNET_PeerIdentity successor,
1395 const struct GNUNET_PeerIdentity *successor_trail,
1396 unsigned int successor_trail_length,
1397 struct GNUNET_HashCode succesor_trail_id,
1398 struct FriendInfo *target_friend)
1400 struct PeerNotifyNewSuccessorMessage *nsm;
1401 struct P2PPendingMessage *pending;
1402 struct GNUNET_PeerIdentity *peer_list;
1405 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1406 (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1408 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1414 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1416 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1420 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1421 pending->importance = 0; /* FIXME */
1422 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1423 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1424 pending->msg = &nsm->header;
1425 nsm->header.size = htons (msize);
1426 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1427 nsm->new_successor = successor;
1428 nsm->source_peer = source_peer;
1429 nsm->trail_id = succesor_trail_id;
1431 if (successor_trail_length > 0)
1433 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1434 memcpy (peer_list, successor_trail,
1435 successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1438 /* Send the message to chosen friend. */
1439 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1440 target_friend->pending_count++;
1441 process_friend_queue (target_friend);
1446 * Construct an add_trail message and send it to target_friend
1447 * @param source_peer Source of the trail.
1448 * @param destination_peer Destination of the trail.
1449 * @param trail_id Unique identifier of the trail from
1450 * @a source_peer to @a destination_peer, NOT including the endpoints.
1451 * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1452 * NOT including the endpoints.
1453 * @param trail_length Total number of peers in @a trail.
1454 * @param target_friend Next friend to get this message.
1457 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1458 struct GNUNET_PeerIdentity destination_peer,
1459 struct GNUNET_HashCode trail_id,
1460 const struct GNUNET_PeerIdentity *trail,
1461 unsigned int trail_length,
1462 struct FriendInfo *target_friend)
1464 struct PeerAddTrailMessage *adm;
1465 struct GNUNET_PeerIdentity *peer_list;
1466 struct P2PPendingMessage *pending;
1469 msize = sizeof (struct PeerAddTrailMessage) +
1470 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1472 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1478 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1480 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1484 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1485 pending->importance = 0; /* FIXME */
1486 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1487 adm = (struct PeerAddTrailMessage *) &pending[1];
1488 pending->msg = &adm->header;
1489 adm->header.size = htons (msize);
1490 adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1491 adm->source_peer = source_peer;
1492 adm->destination_peer = destination_peer;
1493 adm->trail_id = trail_id;
1495 if (trail_length > 0)
1497 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1498 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1500 /* Send the message to chosen friend. */
1501 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1502 target_friend->pending_count++;
1503 process_friend_queue (target_friend);
1509 * Construct a trail compression message and send it to target_friend.
1510 * @param source_peer Source of the trail.
1511 * @param trail_id Unique identifier of trail.
1512 * @param first_friend First hop in compressed trail to reach from source to finger
1513 * @param target_friend Next friend to get this message.
1516 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1517 struct GNUNET_HashCode trail_id,
1518 struct GNUNET_PeerIdentity first_friend,
1519 struct FriendInfo *target_friend)
1521 struct P2PPendingMessage *pending;
1522 struct PeerTrailCompressionMessage *tcm;
1525 msize = sizeof (struct PeerTrailCompressionMessage);
1527 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1533 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1535 GNUNET_STATISTICS_update (GDS_stats,
1536 gettext_noop ("# P2P messages dropped due to full queue"),
1540 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1541 pending->importance = 0; /* FIXME */
1542 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1543 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1544 pending->msg = &tcm->header;
1545 tcm->header.size = htons (msize);
1546 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1547 tcm->source_peer = source_peer;
1548 tcm->new_first_friend = first_friend;
1549 tcm->trail_id = trail_id;
1551 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1552 target_friend->pending_count++;
1553 process_friend_queue (target_friend);
1559 * Search my location in trail. In case I am present more than once in the
1560 * trail (can happen during trail setup), then return my lowest index.
1561 * @param trail List of peers
1562 * @return my_index if found
1563 * -1 if no entry found.
1566 search_my_index (const struct GNUNET_PeerIdentity *trail,
1570 int lowest_index = -1;
1572 for (i = 0; i < trail_length; i++)
1574 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1579 return lowest_index;
1584 * Check if the friend is congested or have reached maximum number of trails
1585 * it can be part of of.
1586 * @param friend Friend to be checked.
1587 * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1588 * #GNUNET_YES if friend is either congested or have crossed threshold
1591 is_friend_congested (struct FriendInfo *friend)
1593 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1594 ((0 == GNUNET_TIME_absolute_get_remaining
1595 (friend->congestion_timestamp).rel_value_us)))
1603 * FIXME; not handling the wrap around logic correctly.
1604 * Select closest finger to value.
1605 * @param peer1 First peer
1606 * @param peer2 Second peer
1607 * @param value Value to be compare
1608 * @return Closest peer
1610 static struct GNUNET_PeerIdentity *
1611 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1612 struct GNUNET_PeerIdentity *peer2,
1615 uint64_t peer1_value;
1616 uint64_t peer2_value;
1618 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1619 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1620 peer1_value = GNUNET_ntohll (peer1_value);
1621 peer2_value = GNUNET_ntohll (peer2_value);
1623 if (peer1_value == value)
1628 if (peer2_value == value)
1633 if (peer2_value < peer1_value)
1635 if ((peer2_value < value) && (value < peer1_value))
1639 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1640 ((0 < value) && (value < peer2_value)))
1646 if (peer1_value < peer2_value)
1648 if ((peer1_value < value) && (value < peer2_value))
1652 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1653 ((0 < value) && (value < peer1_value)))
1663 * Select closest predecessor to value.
1664 * @param peer1 First peer
1665 * @param peer2 Second peer
1666 * @param value Value to be compare
1667 * @return Peer which precedes value in the network.
1669 static struct GNUNET_PeerIdentity *
1670 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1671 struct GNUNET_PeerIdentity *peer2,
1674 uint64_t peer1_value;
1675 uint64_t peer2_value;
1677 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1678 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1679 peer1_value = GNUNET_ntohll (peer1_value);
1680 peer2_value = GNUNET_ntohll (peer2_value);
1682 if (peer1_value == value)
1685 if (peer2_value == value)
1688 if (peer1_value < peer2_value)
1690 if ((peer1_value < value) && (value < peer2_value))
1694 else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1695 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1701 if (peer2_value < peer1_value)
1703 if ((peer2_value < value) && (value < peer1_value))
1707 else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1708 ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1718 * This is a test function to print all the entries of friend table.
1721 test_friend_peermap_print ()
1723 struct FriendInfo *friend;
1724 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1725 struct GNUNET_PeerIdentity print_peer;
1726 struct GNUNET_PeerIdentity key_ret;
1729 print_peer = my_identity;
1730 FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1731 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1733 for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1735 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1737 (const void **)&friend))
1739 memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1740 FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1741 __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1748 * This is a test function, to print all the entries of finger table.
1751 test_finger_table_print()
1753 struct FingerInfo *finger;
1754 struct GNUNET_PeerIdentity print_peer;
1755 //struct Trail *trail;
1759 print_peer = my_identity;
1760 FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1761 for (i = 0; i < MAX_FINGERS; i++)
1763 finger = &finger_table[i];
1765 if (GNUNET_NO == finger->is_present)
1768 print_peer = finger->finger_identity;
1769 FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1770 __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1773 for (j = 0; j < finger->trails_count; j++)
1775 trail = &finger->trail_list[j];
1776 FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1777 struct Trail_Element *element;
1778 element = trail->trail_head;
1779 for (k = 0; k < trail->trail_length; k++)
1781 print_peer = element->peer;
1782 FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1783 element = element->next;
1792 * Select the closest peer among two peers (which should not be same)
1793 * with respect to value and finger_table_index
1794 * NOTE: peer1 != peer2
1795 * @param peer1 First peer
1796 * @param peer2 Second peer
1797 * @param value Value relative to which we find the closest
1798 * @param is_predecessor Is value a predecessor or any other finger.
1799 * @return Closest peer among two peers.
1801 static struct GNUNET_PeerIdentity *
1802 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1803 struct GNUNET_PeerIdentity *peer2,
1805 unsigned int is_predecessor)
1807 struct GNUNET_PeerIdentity *closest_peer;
1809 if (1 == is_predecessor)
1811 closest_peer = select_closest_predecessor (peer1, peer2, value);
1816 closest_peer = select_closest_finger (peer1, peer2, value);
1818 return closest_peer;
1823 * Iterate over the list of all the trails of a finger. In case the first
1824 * friend to reach the finger has reached trail threshold or is congested,
1825 * then don't select it. In case there multiple available good trails to reach
1826 * to Finger, choose the one with shortest trail length.
1827 * Note: We use length as parameter. But we can use any other suitable parameter
1829 * @param finger Finger
1830 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1831 * and trail length. NULL in case none of the trails are free.
1833 static struct Selected_Finger_Trail *
1834 select_finger_trail (struct FingerInfo *finger)
1836 struct FriendInfo *friend;
1837 struct Trail *iterator;
1838 struct Selected_Finger_Trail *finger_trail;
1840 unsigned int flag = 0;
1843 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1844 GNUNET_assert (finger->trails_count > 0);
1846 for (i = 0; i < finger->trails_count; i++)
1848 iterator = &finger->trail_list[i];
1850 /* No trail stored at this index. */
1851 if (GNUNET_NO == iterator->is_present)
1854 GNUNET_assert (NULL !=
1856 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1857 &iterator->trail_head->peer)));
1859 /* First friend to reach trail is not free. */
1860 if (GNUNET_YES == is_friend_congested (friend))
1869 finger_trail->trail_length = iterator->trail_length;
1870 finger_trail->friend = *friend;
1871 finger_trail->trail_id = iterator->trail_id;
1873 else if (finger_trail->trail_length > iterator->trail_length)
1875 finger_trail->friend = *friend;
1876 finger_trail->trail_id = iterator->trail_id;
1877 finger_trail->trail_length = iterator->trail_length;
1881 /* All the first friend in all the trails to reach to finger are either
1882 congested or have crossed trail threshold. */
1883 if (j == finger->trails_count)
1886 return finger_trail;
1891 * Compare FINGER entry with current successor. If finger's first friend of all
1892 * its trail is not congested and has not crossed trail threshold, then check
1893 * if finger peer identity is closer to final_destination_finger_value than
1894 * current_successor. If yes then update current_successor.
1895 * @param current_successor[in/out]
1899 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1901 struct FingerInfo *finger;
1902 struct GNUNET_PeerIdentity *closest_peer;
1903 struct Selected_Finger_Trail *finger_trail;
1906 /* Iterate over finger table. */
1907 for (i = 0; i < MAX_FINGERS; i++)
1909 finger = &finger_table[i];
1911 if (GNUNET_NO == finger->is_present)
1914 /* If my identity is same as current closest peer then don't consider me*/
1916 GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1917 ¤t_closest_peer->best_known_destination))
1920 /* If I am my own finger, then ignore this finger. */
1921 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1925 /* If finger is a friend, then do nothing. As we have already checked
1926 * for each friend in compare_friend_and_current_successor(). */
1927 if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1928 &finger->finger_identity)))
1933 /* Choose one of the trail to reach to finger. */
1934 finger_trail = select_finger_trail (finger);
1936 /* In case no trail found, ignore this finger. */
1937 if (NULL == finger_trail)
1940 closest_peer = select_closest_peer (&finger->finger_identity,
1941 ¤t_closest_peer->best_known_destination,
1942 current_closest_peer->destination_finger_value,
1943 current_closest_peer->is_predecessor);
1945 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1948 current_closest_peer->best_known_destination = finger->finger_identity;
1949 current_closest_peer->next_hop = finger_trail->friend.id;
1950 current_closest_peer->trail_id = finger_trail->trail_id;
1951 //GNUNET_free(finger_trail);//FIXME: where should we free the finger trail.
1959 * Compare friend entry with current successor.
1960 * If friend identity and current_successor is same, then do nothing.
1961 * If friend is not congested and has not crossed trail threshold, then check
1962 * if friend peer identity is closer to final_destination_finger_value than
1963 * current_successor. If yes then update current_successor.
1964 * @param cls closure
1965 * @param key current public key
1966 * @param value struct Closest_Peer
1967 * @return #GNUNET_YES if we should continue to iterate,
1968 * #GNUNET_NO if not.
1971 compare_friend_and_current_closest_peer (void *cls,
1972 const struct GNUNET_PeerIdentity *key,
1975 struct FriendInfo *friend = value;
1976 struct Closest_Peer *current_closest_peer = cls;
1977 struct GNUNET_PeerIdentity *closest_peer;
1979 /* Friend is either congested or has crossed threshold. */
1980 if (GNUNET_YES == is_friend_congested (friend))
1983 /* If current_closest_peer and friend identity are same, then do nothing.*/
1985 GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
1986 ¤t_closest_peer->best_known_destination))
1989 closest_peer = select_closest_peer (&friend->id,
1990 ¤t_closest_peer->best_known_destination,
1991 current_closest_peer->destination_finger_value,
1992 current_closest_peer->is_predecessor);
1994 /* Is friend the closest successor? */
1995 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id, closest_peer))
1997 current_closest_peer->best_known_destination = friend->id;
1998 current_closest_peer->next_hop = friend->id;
2006 * Initialize current_successor to my_identity.
2007 * @param my_identity My peer identity
2008 * @return Updated closest_peer
2010 static struct Closest_Peer
2011 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2012 uint64_t destination_finger_value,
2013 unsigned int is_predecessor)
2015 struct Closest_Peer current_closest_peer;
2017 memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2018 current_closest_peer.destination_finger_value = destination_finger_value;
2019 current_closest_peer.is_predecessor = is_predecessor;
2020 current_closest_peer.next_hop = my_identity;
2021 current_closest_peer.best_known_destination = my_identity;
2023 return current_closest_peer;
2028 * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2029 * peer. It could be because of the logic we wrote here. Verify if its correct.
2030 * If not then return immediate_successor.
2032 * Find the successor for destination_finger_value among my_identity, my
2033 * friends and my fingers. Don't consider friends or fingers which are either
2034 * congested or have crossed the threshold.
2035 * NOTE: In case a friend is also a finger, then it is always chosen as friend
2037 * @param destination_finger_value Peer closest to this value will be the next successor.
2038 * @param is_predecessor Are we looking for predecessor or finger?
2039 * @return Successor It is never NULL, in case none of friend or finger is closest,
2040 * then we return my_identity.
2042 static struct Closest_Peer
2043 find_successor (uint64_t destination_finger_value,
2044 unsigned int is_predecessor)
2046 struct Closest_Peer current_closest_peer;
2048 /* Initialize current_successor to my_identity. */
2049 current_closest_peer = init_current_successor (my_identity,
2050 destination_finger_value,
2053 /* Compare each friend entry with current_successor and update current_successor
2054 * with friend if its closest. */
2057 GNUNET_CONTAINER_multipeermap_iterate (friend_peermap,
2058 &compare_friend_and_current_closest_peer,
2059 ¤t_closest_peer));
2061 /* Compare each finger entry with current_successor and update current_successor
2062 * with finger if its closest. */
2063 compare_finger_and_current_successor (¤t_closest_peer);
2065 return current_closest_peer;
2070 * Construct a Put message and send it to target_peer.
2071 * @param key Key for the content
2072 * @param block_type Type of the block
2073 * @param options Routing options
2074 * @param desired_replication_level Desired replication count
2075 * @param best_known_dest Peer to which this message should reach eventually,
2076 * as it is best known destination to me.
2077 * @param intermediate_trail_id Trail id in case
2078 * @param target_peer Peer to which this message will be forwarded.
2079 * @param hop_count Number of hops traversed so far.
2080 * @param put_path_length Total number of peers in @a put_path
2081 * @param put_path Number of peers traversed so far
2082 * @param expiration_time When does the content expire
2083 * @param data Content to store
2084 * @param data_size Size of content @a data in bytes
2087 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2088 enum GNUNET_BLOCK_Type block_type,
2089 enum GNUNET_DHT_RouteOption options,
2090 uint32_t desired_replication_level,
2091 struct GNUNET_PeerIdentity best_known_dest,
2092 struct GNUNET_HashCode intermediate_trail_id,
2093 struct GNUNET_PeerIdentity *target_peer,
2095 uint32_t put_path_length,
2096 struct GNUNET_PeerIdentity *put_path,
2097 struct GNUNET_TIME_Absolute expiration_time,
2098 const void *data, size_t data_size)
2100 struct PeerPutMessage *ppm;
2101 struct P2PPendingMessage *pending;
2102 struct FriendInfo *target_friend;
2103 struct GNUNET_PeerIdentity *pp;
2104 struct GNUNET_PeerIdentity next_hop;
2108 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2109 sizeof (struct PeerPutMessage);
2111 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2113 put_path_length = 0;
2114 msize = data_size + sizeof (struct PeerPutMessage);
2117 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2123 /* This is the first call made from clients file. So, we should search for the
2125 if (NULL == target_peer)
2128 struct Closest_Peer successor;
2130 memcpy (&key_value, key, sizeof (uint64_t));
2131 key_value = GNUNET_ntohll (key_value);
2133 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2134 best_known_dest = successor.best_known_destination;
2135 next_hop = successor.next_hop;
2136 intermediate_trail_id = successor.trail_id;
2138 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity))
2140 /* I am the destination but we have already done datacache_put in client file. */
2144 GNUNET_assert (NULL !=
2146 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
2150 GNUNET_assert (NULL !=
2152 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer)));
2155 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2156 pending->timeout = expiration_time;
2157 ppm = (struct PeerPutMessage *) &pending[1];
2158 pending->msg = &ppm->header;
2159 ppm->header.size = htons (msize);
2160 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2161 ppm->options = htonl (options);
2162 ppm->block_type = htonl (block_type);
2163 ppm->hop_count = htonl (hop_count + 1);
2164 ppm->desired_replication_level = htonl (desired_replication_level);
2165 ppm->put_path_length = htonl (put_path_length);
2166 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2167 ppm->best_known_destination = best_known_dest;
2170 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2171 if (put_path_length != 0)
2173 memcpy (pp, put_path,
2174 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2176 memcpy (&pp[put_path_length], data, data_size);
2178 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2179 target_friend->pending_count++;
2180 process_friend_queue (target_friend);
2185 * Construct a Get message and send it to target_peer.
2186 * @param key Key for the content
2187 * @param block_type Type of the block
2188 * @param options Routing options
2189 * @param desired_replication_level Desired replication count
2190 * @param best_known_dest Peer which should get this message. Same as target peer
2191 * if best_known_dest is a friend else its a finger.
2192 * @param intermediate_trail_id Trail id to reach to @a best_known_dest
2193 * in case it is a finger else set to 0.
2194 * @param target_peer Peer to which this message will be forwarded.
2195 * @param hop_count Number of hops traversed so far.
2196 * @param data Content to store
2197 * @param data_size Size of content @a data in bytes
2198 * @param get_path_length Total number of peers in @a get_path
2199 * @param get_path Number of peers traversed so far
2202 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2203 enum GNUNET_BLOCK_Type block_type,
2204 enum GNUNET_DHT_RouteOption options,
2205 uint32_t desired_replication_level,
2206 struct GNUNET_PeerIdentity best_known_dest,
2207 struct GNUNET_HashCode intermediate_trail_id,
2208 struct GNUNET_PeerIdentity *target_peer,
2210 uint32_t get_path_length,
2211 struct GNUNET_PeerIdentity *get_path)
2213 struct PeerGetMessage *pgm;
2214 struct P2PPendingMessage *pending;
2215 struct FriendInfo *target_friend;
2216 struct GNUNET_PeerIdentity *gp;
2219 msize = sizeof (struct PeerGetMessage) +
2220 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2222 /* In this case we don't make get_path_length = 0, as we need get path to
2223 * return the message back to querying client. */
2224 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2230 /* This is the first time we got request from our own client file. */
2231 if (NULL == target_peer)
2234 struct Closest_Peer successor;
2236 memcpy (&key_value, key, sizeof (uint64_t));
2237 key_value = GNUNET_ntohll (key_value);
2238 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2240 best_known_dest = successor.best_known_destination;
2241 intermediate_trail_id = successor.trail_id;
2243 /* I am the destination. I have the data. */
2244 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2247 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2248 NULL, 0, 1, &my_identity, NULL,&my_identity);
2254 GNUNET_assert (NULL !=
2256 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2257 &successor.next_hop)));
2263 GNUNET_assert (NULL !=
2265 GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); //FIXME: assertion fails.
2268 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2269 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2270 pending->importance = 0; /* FIXME */
2271 pgm = (struct PeerGetMessage *) &pending[1];
2272 pending->msg = &pgm->header;
2273 pgm->header.size = htons (msize);
2274 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2275 pgm->get_path_length = htonl (get_path_length);
2276 pgm->best_known_destination = best_known_dest;
2278 pgm->intermediate_trail_id = intermediate_trail_id;
2279 pgm->hop_count = htonl (hop_count + 1);
2280 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2282 if (get_path_length != 0)
2284 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2287 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2288 target_friend->pending_count++;
2289 process_friend_queue (target_friend);
2294 * Send the get result to requesting client.
2295 * @param key Key of the requested data.
2296 * @param type Block type
2297 * @param target_peer Next peer to forward the message to.
2298 * @param source_peer Peer which has the data for the key.
2299 * @param put_path_length Number of peers in @a put_path
2300 * @param put_path Path taken to put the data at its stored location.
2301 * @param get_path_length Number of peers in @a get_path
2302 * @param get_path Path taken to reach to the location of the key.
2303 * @param expiration When will this result expire?
2304 * @param data Payload to store
2305 * @param data_size Size of the @a data
2308 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2309 enum GNUNET_BLOCK_Type type,
2310 const struct GNUNET_PeerIdentity *target_peer,
2311 const struct GNUNET_PeerIdentity *source_peer,
2312 unsigned int put_path_length,
2313 const struct GNUNET_PeerIdentity *put_path,
2314 unsigned int get_path_length,
2315 const struct GNUNET_PeerIdentity *get_path,
2316 struct GNUNET_TIME_Absolute expiration,
2317 const void *data, size_t data_size)
2319 struct PeerGetResultMessage *get_result;
2320 struct GNUNET_PeerIdentity *paths;
2321 struct P2PPendingMessage *pending;
2322 struct FriendInfo *target_friend;
2323 int current_path_index;
2326 msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) +
2328 sizeof (struct PeerGetResultMessage);
2330 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2336 current_path_index = 0;
2337 if(get_path_length > 0)
2339 current_path_index = search_my_index(get_path, get_path_length);
2340 if (-1 == current_path_index)
2346 if (0 == current_path_index)
2348 GDS_CLIENTS_handle_reply (expiration, key, get_path_length,
2349 get_path, put_path_length,
2350 put_path, type, data_size, data);
2354 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2355 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2356 pending->importance = 0;
2357 get_result = (struct PeerGetResultMessage *)&pending[1];
2358 pending->msg = &get_result->header;
2359 get_result->header.size = htons (msize);
2360 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2361 get_result->key = *key;
2362 get_result->querying_peer = *source_peer;
2363 get_result->expiration_time = expiration;
2364 get_result->get_path_length = htonl (get_path_length);
2365 get_result->put_path_length = htonl (put_path_length);
2366 paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2367 memcpy (paths, put_path,
2368 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2369 memcpy (&paths[put_path_length], get_path,
2370 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2371 memcpy (&paths[put_path_length + get_path_length], data, data_size);
2373 GNUNET_assert (NULL !=
2375 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2376 &get_path[current_path_index - 1])));
2377 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2378 target_friend->pending_count++;
2379 process_friend_queue (target_friend);
2384 * Randomly choose one of your friends (which is not congested and have not crossed
2385 * trail threshold) from the friend_peermap
2386 * @return Friend Randomly chosen friend.
2387 * NULL in case friend peermap is empty, or all the friends are either
2388 * congested or have crossed trail threshold.
2390 static struct FriendInfo *
2391 select_random_friend ()
2393 unsigned int current_size;
2396 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2397 struct GNUNET_PeerIdentity key_ret;
2398 struct FriendInfo *friend;
2400 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2403 if (0 == current_size)
2406 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2407 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2409 /* Iterate till you don't reach to index. */
2410 for (j = 0; j < index ; j++)
2411 GNUNET_assert (GNUNET_YES ==
2412 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2415 /* Reset the index in friend peermap to 0 as we reached to the end. */
2416 if (j == current_size)
2419 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2420 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2424 /* Get the friend stored at the index, j*/
2425 GNUNET_assert (GNUNET_YES ==
2426 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2428 (const void **)&friend));
2430 /* This friend is not congested and has not crossed trail threshold. */
2431 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2432 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2438 } while (j != index);
2440 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2446 * Compute 64 bit value of finger_identity corresponding to a finger index using
2448 * For all fingers, n.finger[i] = n + pow (2,i),
2449 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2450 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2451 * @param finger_index Index corresponding to which we calculate 64 bit value.
2452 * @return 64 bit value.
2455 compute_finger_identity_value (unsigned int finger_index)
2459 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2460 my_id64 = GNUNET_ntohll (my_id64);
2462 /* Are we looking for immediate predecessor? */
2463 if (PREDECESSOR_FINGER_ID == finger_index)
2464 return (my_id64 - 1);
2467 uint64_t add = (uint64_t)1 << finger_index;
2468 return (my_id64 + add);
2474 * Choose a random friend. Calculate the next finger identity to search,from
2475 * current_search_finger_index. Start looking for the trail to reach to
2476 * finger identity through this random friend.
2478 * @param cls closure for this task
2479 * @param tc the context under which the task is running
2482 send_find_finger_trail_message (void *cls,
2483 const struct GNUNET_SCHEDULER_TaskContext *tc)
2485 struct FriendInfo *target_friend;
2486 struct GNUNET_TIME_Relative next_send_time;
2487 struct GNUNET_HashCode trail_id;
2488 struct GNUNET_HashCode new_intermediate_trail_id;
2489 unsigned int is_predecessor;
2490 uint64_t finger_id_value;
2492 /* Schedule another send_find_finger_trail_message task. */
2493 next_send_time.rel_value_us =
2494 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
2495 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2496 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2497 find_finger_trail_task =
2498 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
2501 /* No space in my routing table. (Source and destination peers also store entries
2502 * in their routing table). */
2503 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2506 target_friend = select_random_friend ();
2507 if (NULL == target_friend)
2512 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2513 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2518 /* Generate a unique trail id for trail we are trying to setup. */
2519 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2520 &trail_id, sizeof (trail_id));
2521 memset(&new_intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2523 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2524 target_friend->id, target_friend, 0, NULL,
2525 is_predecessor, trail_id,
2526 new_intermediate_trail_id);
2531 * In case there are already maximum number of possible trails to reach to a
2532 * finger, then check if the new trail's length is lesser than any of the
2534 * If yes then replace that old trail by new trail.
2536 * Note: Here we are taking length as a parameter to choose the best possible
2537 * trail, but there could be other parameters also like:
2538 * 1. duration of existence of a trail - older the better.
2539 * 2. if the new trail is completely disjoint than the
2540 * other trails, then may be choosing it is better.
2542 * @param existing_finger
2543 * @param new_finger_trail
2544 * @param new_finger_trail_length
2545 * @param new_finger_trail_id
2548 select_and_replace_trail (struct FingerInfo *existing_finger,
2549 const struct GNUNET_PeerIdentity *new_trail,
2550 unsigned int new_trail_length,
2551 struct GNUNET_HashCode new_trail_id)
2553 struct Trail *trail_list_iterator;
2554 unsigned int largest_trail_length;
2555 unsigned int largest_trail_index;
2556 struct Trail_Element *trail_element;
2559 largest_trail_length = new_trail_length;
2560 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2562 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2564 for (i = 0; i < existing_finger->trails_count; i++)
2566 trail_list_iterator = &existing_finger->trail_list[i];
2567 if (trail_list_iterator->trail_length > largest_trail_length)
2569 largest_trail_length = trail_list_iterator->trail_length;
2570 largest_trail_index = i;
2574 /* New trail is not better than existing ones. Send trail teardown. */
2575 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2577 struct GNUNET_PeerIdentity next_hop;
2579 memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2580 GDS_ROUTING_remove_trail (new_trail_id);
2581 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2582 GDS_ROUTING_SRC_TO_DEST,
2587 /* Send trail teardown message across the replaced trail. */
2588 struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2589 existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2590 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2591 GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2592 GDS_ROUTING_SRC_TO_DEST,
2593 replace_trail->trail_head->peer);
2594 /* Free the trail. */
2595 while (NULL != (trail_element = replace_trail->trail_head))
2597 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2598 replace_trail->trail_tail, trail_element);
2599 GNUNET_free_non_null (trail_element);
2602 /* Add new trial at that location. */
2603 replace_trail->is_present = GNUNET_YES;
2604 replace_trail->trail_length = new_trail_length;
2605 replace_trail->trail_id = new_trail_id;
2606 //FIXME: Do we need to add pointers for head and tail.
2608 while (i < new_trail_length)
2610 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2611 element->peer = new_trail[i];
2613 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2614 replace_trail->trail_tail,
2621 * Check if the new trail to reach to finger is unique or do we already have
2622 * such a trail present for finger.
2623 * @param existing_finger Finger identity
2624 * @param new_trail New trail to reach @a existing_finger
2625 * @param trail_length Total number of peers in new_trail.
2626 * @return #GNUNET_YES if the new trail is unique
2627 * #GNUNET_NO if same trail is already present.
2630 is_new_trail_unique (struct FingerInfo *existing_finger,
2631 const struct GNUNET_PeerIdentity *new_trail,
2632 unsigned int trail_length)
2634 struct Trail *trail_list_iterator;
2635 struct Trail_Element *trail_element;
2638 int trail_unique = GNUNET_NO;
2640 GNUNET_assert (existing_finger->trails_count > 0);
2642 /* Iterate over list of trails. */
2643 for (i = 0; i < existing_finger->trails_count; i++)
2645 trail_list_iterator = &existing_finger->trail_list[i];
2646 GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2648 /* New trail and existing trail length are not same. */
2649 if (trail_list_iterator->trail_length != trail_length)
2651 trail_unique = GNUNET_YES;
2655 trail_element = trail_list_iterator->trail_head;
2656 for (j = 0; j < trail_list_iterator->trail_length; j++)
2658 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2659 &trail_element->peer))
2661 trail_unique = GNUNET_YES;
2664 trail_element = trail_element->next;
2667 trail_unique = GNUNET_NO;
2670 return trail_unique;
2675 * Add a new trail to existing finger. This function is called only when finger
2676 * is not my own identity or a friend.
2677 * @param existing_finger Finger
2678 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2679 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2680 * @param new_finger_trail_id Unique identifier of the trail.
2683 add_new_trail (struct FingerInfo *existing_finger,
2684 const struct GNUNET_PeerIdentity *new_trail,
2685 unsigned int new_trail_length,
2686 struct GNUNET_HashCode new_trail_id)
2688 struct Trail *trail_list_iterator;
2689 struct FriendInfo *first_friend;
2692 if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2698 trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2699 GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2700 trail_list_iterator->trail_id = new_trail_id;
2701 trail_list_iterator->trail_length = new_trail_length;
2702 existing_finger->trails_count++;
2703 trail_list_iterator->is_present = GNUNET_YES;
2705 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2706 &existing_finger->finger_identity)));
2707 /* If finger is a friend then we never call this function. */
2708 GNUNET_assert (new_trail_length > 0);
2710 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2712 first_friend->trails_count++;
2714 for (i = 0; i < new_trail_length; i++)
2716 struct Trail_Element *element;
2718 element = GNUNET_new (struct Trail_Element);
2719 element->peer = new_trail[i];
2720 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2721 trail_list_iterator->trail_tail,
2724 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2730 * FIXME Check if this function is called for opposite direction if yes then
2731 * take it as parameter.
2732 * Get the next hop to send trail teardown message from routing table and
2733 * then delete the entry from routing table. Send trail teardown message for a
2734 * specific trail of a finger.
2735 * @param finger Finger whose trail is to be removed.
2736 * @param trail List of peers in trail from me to a finger, NOT including
2740 send_trail_teardown (struct FingerInfo *finger,
2741 struct Trail *trail)
2743 struct FriendInfo *friend;
2744 struct GNUNET_PeerIdentity *next_hop;
2746 GNUNET_assert (NULL !=
2747 (next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
2748 GDS_ROUTING_SRC_TO_DEST)));
2750 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2753 GNUNET_assert (trail->is_present == GNUNET_YES);
2755 /* Finger is not a friend. */
2756 if (trail->trail_length > 0)
2758 GNUNET_assert (NULL != (friend =
2759 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2760 &trail->trail_head->peer)));
2764 GNUNET_assert (NULL != (friend =
2765 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2766 &finger->finger_identity)));
2769 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails.
2770 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2771 friend->trails_count--;
2772 GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2773 GDS_ROUTING_SRC_TO_DEST,
2779 * Send trail teardown message across all the trails to reach to finger.
2780 * @param finger Finger whose all the trail should be freed.
2783 send_all_finger_trails_teardown (struct FingerInfo *finger)
2787 for (i = 0; i < finger->trails_count; i++)
2789 struct Trail *trail;
2791 trail = &finger->trail_list[i];
2792 GNUNET_assert (trail->is_present == GNUNET_YES);
2793 send_trail_teardown (finger, trail);
2794 trail->is_present = GNUNET_NO;
2800 * Free a specific trail
2801 * @param trail List of peers to be freed.
2804 free_trail (struct Trail *trail)
2806 struct Trail_Element *trail_element;
2808 while (NULL != (trail_element = trail->trail_head))
2810 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2814 GNUNET_free_non_null (trail_element);
2816 trail->trail_head = NULL;
2817 trail->trail_tail = NULL;
2822 * Free finger and its trail.
2823 * @param finger Finger to be freed.
2826 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2828 struct Trail *trail;
2831 /* Free all the trails to reach to finger */
2832 for (i = 0; i < finger->trails_count; i++)
2834 trail = &finger->trail_list[i];
2835 //FIXME: Check if there are any missing entry in this list because of
2836 // how we insert. If not then no need of this check.
2837 if (GNUNET_NO == trail->is_present)
2840 if (trail->trail_length > 0)
2844 trail->is_present = GNUNET_NO;
2847 finger->is_present = GNUNET_NO;
2848 memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2853 * FIXME: ensure that you are not adding any trail to reach to a friend which
2854 * is a finger. Also decide on should you increment trails count of a friend
2855 * which is also a finger.
2856 * Add a new entry in finger table at finger_table_index.
2857 * In case finger identity is me or a friend, then don't add a trail. NOTE
2858 * trail length to reach to a finger can be 0 only if the finger is a friend
2860 * In case a finger is a friend, then increment the trails count of the friend.
2861 * @param finger_identity Peer Identity of new finger
2862 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2863 * @param finger_trail_length Total number of peers in @a finger_trail.
2864 * @param trail_id Unique identifier of the trail.
2865 * @param finger_table_index Index in finger table.
2868 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2869 const struct GNUNET_PeerIdentity *finger_trail,
2870 unsigned int finger_trail_length,
2871 struct GNUNET_HashCode trail_id,
2872 unsigned int finger_table_index)
2874 struct FingerInfo *new_entry;
2875 struct FriendInfo *first_trail_hop;
2876 struct Trail *trail;
2879 new_entry = GNUNET_new (struct FingerInfo);
2880 new_entry->finger_identity = finger_identity;
2881 new_entry->finger_table_index = finger_table_index;
2882 new_entry->is_present = GNUNET_YES;
2884 /* If the new entry is my own identity. */
2885 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2887 new_entry->trails_count = 0;
2888 finger_table[finger_table_index] = *new_entry;
2889 GNUNET_free (new_entry);
2893 /* If finger is a friend, then we don't actually have a trail.
2894 * Just a trail id */
2895 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2898 new_entry->trail_list[0].trail_id = trail_id;
2899 new_entry->trails_count = 1;
2900 new_entry->trail_list[0].is_present = GNUNET_YES;
2901 new_entry->trail_list[0].trail_length = 0;
2902 new_entry->trail_list[0].trail_head = NULL;
2903 new_entry->trail_list[0].trail_tail = NULL;
2904 finger_table[finger_table_index] = *new_entry;
2905 GNUNET_assert (NULL !=
2907 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2908 &finger_identity)));
2910 first_trail_hop->trails_count++;
2911 GNUNET_free (new_entry);
2915 /* finger trail length can be 0 only in case if finger is my identity or
2916 finger is friend. We should never reach here. */
2917 GNUNET_assert (finger_trail_length > 0);
2919 GNUNET_assert (NULL !=
2921 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2922 &finger_trail[0])));
2923 new_entry->trails_count = 1;
2924 first_trail_hop->trails_count++;
2926 /* Copy the finger trail into trail. */
2927 trail = GNUNET_new (struct Trail);
2928 while (i < finger_trail_length)
2930 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2932 element->next = NULL;
2933 element->prev = NULL;
2934 element->peer = finger_trail[i];
2935 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2941 /* Add trail to trail list. */
2942 new_entry->trail_list[0].trail_head = trail->trail_head;
2943 new_entry->trail_list[0].trail_tail = trail->trail_tail;
2944 new_entry->trail_list[0].trail_length = finger_trail_length;
2945 new_entry->trail_list[0].trail_id = trail_id;
2946 new_entry->trail_list[0].is_present = GNUNET_YES;
2947 finger_table[finger_table_index] = *new_entry;
2948 //GNUNET_free (new_entry);
2949 //GNUNET_free (trail);
2955 * Scan the trail to check if there is any other friend in the trail other than
2956 * first hop. If yes then shortcut the trail, send trail compression message to
2957 * peers which are no longer part of trail and send back the updated trail
2958 * and trail_length to calling function.
2959 * @param finger_identity Finger whose trail we will scan.
2960 * @param finger_trail [in, out] Trail to reach from source to finger,
2961 * @param finger_trail_length Total number of peers in original finger_trail.
2962 * @param finger_trail_id Unique identifier of the finger trail.
2963 * @return updated trail length in case we shortcut the trail, else original
2966 static struct GNUNET_PeerIdentity *
2967 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2968 const struct GNUNET_PeerIdentity *trail,
2969 unsigned int trail_length,
2970 struct GNUNET_HashCode trail_id,
2971 int *new_trail_length)
2973 struct FriendInfo *target_friend;
2974 struct GNUNET_PeerIdentity *new_trail;
2977 /* I am my own finger. */
2978 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2980 *new_trail_length = 0;
2984 if (0 == trail_length)
2986 *new_trail_length = 0;
2990 /* If finger identity is a friend. */
2991 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
2993 *new_trail_length = 0;
2995 /* If there is trail to reach this finger/friend */
2996 if (trail_length > 0)
2998 /* Finger is your first friend. */
2999 GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3000 GNUNET_assert (NULL !=
3002 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3006 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3007 trail_id, finger_identity,
3013 /* For other cases, when its neither a friend nor my own identity.*/
3014 for (i = trail_length - 1; i > 0; i--)
3016 /* If the element at this index in trail is a friend. */
3017 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3019 struct FriendInfo *target_friend;
3022 GNUNET_assert (NULL !=
3024 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3026 GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3027 GDS_NEIGHBOURS_send_trail_compression (my_identity,
3032 /* Copy the trail from index i to index (trail_length -1) into a new trail
3033 * and update new trail length */
3034 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3035 while (i < trail_length)
3037 memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3041 *new_trail_length = j+1;
3042 GNUNET_assert((j+1) == (trail_length - 1)); //FIXME: remove it afterwards.
3047 /* If we did not compress the trail, return the original trail back.*/
3048 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
3049 *new_trail_length = trail_length;
3050 memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3056 * Send verify successor message to your current successor over the shortest
3058 * @param successor Current successor.
3061 send_verify_successor_message (struct FingerInfo *successor)
3064 * FIXME: should we send a verify successor message across all the trails
3065 * in case we send through all friends. It complicates the logic, don't
3066 * do it at the moment. Write it as optimization and do it later.
3067 * 1. Here we can have 3 types of fingers
3068 * --> my own identity
3069 * Assumption that the calling function will not send request for
3070 * such successor. Move the logic here.
3071 * --> friend is a finger
3072 * Need to verify if we keep the trails count for a friend. In case of
3073 * friend there is no trail to reach to that friend, so
3074 * 1. no entry in routing table
3076 * 3. no trails count
3077 * 4. but do we increment the count of trails through the friend?
3078 * Trails count is used only to keep a limit on number of trails
3079 * that a friend should be part of. No need to increment the trails
3080 * count for a friend which is a finegr also. so, if finger = friend
3081 * then don't increment the trails count. But if the same friend
3082 * is the first friend to reach to some other finger then increment
3083 * the trails count. Not sure if this design is correct need to verify
3087 struct FriendInfo *target_friend;
3088 struct GNUNET_HashCode trail_id;
3090 struct Trail *trail;
3091 struct Trail_Element *element;
3092 unsigned int trail_length;
3096 trail = &successor->trail_list[i];
3098 /* Trail stored at this index. */
3099 GNUNET_assert (GNUNET_YES == trail->is_present);
3101 trail_id = trail->trail_id;
3102 trail_length = trail->trail_length;
3104 if (trail_length > 0)
3106 /* Copy the trail into peer list. */
3107 struct GNUNET_PeerIdentity peer_list[trail_length];
3109 element = trail->trail_head;
3110 while (j < trail_length)
3112 peer_list[j] = element->peer;
3113 element = element->next;
3117 GNUNET_assert (NULL != (target_friend =
3118 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3120 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3121 successor->finger_identity,
3122 trail_id, peer_list, trail_length,
3128 GNUNET_assert (NULL != (target_friend =
3129 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3130 &successor->finger_identity)));
3131 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3132 successor->finger_identity,
3141 * Update the current search finger index.
3144 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3145 unsigned int finger_table_index)
3147 struct FingerInfo *successor;
3149 if (finger_table_index != current_search_finger_index)
3152 successor = &finger_table[0];
3153 GNUNET_assert (GNUNET_YES == successor->is_present);
3155 /* We were looking for immediate successor. */
3156 if (0 == current_search_finger_index)
3158 /* Start looking for immediate predecessor. */
3159 current_search_finger_index = PREDECESSOR_FINGER_ID;
3161 /* If I am not my own successor, then send a verify successor message. */
3162 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3164 send_verify_successor_message (successor);
3169 current_search_finger_index = current_search_finger_index - 1;
3175 * Calculate finger_table_index from initial 64 bit finger identity value that
3176 * we send in trail setup message.
3177 * @param ultimate_destination_finger_value Value that we calculated from our
3178 * identity and finger_table_index.
3179 * @param is_predecessor Is the entry for predecessor or not?
3180 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3181 * finger_table_index > PREDECESSOR_FINGER_ID ,
3182 * if no valid finger_table_index is found.
3185 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3186 unsigned int is_predecessor)
3190 unsigned int finger_table_index;
3192 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3193 my_id64 = GNUNET_ntohll (my_id64);
3195 /* Is this a predecessor finger? */
3196 if (1 == is_predecessor)
3198 diff = my_id64 - ultimate_destination_finger_value;
3200 finger_table_index = PREDECESSOR_FINGER_ID;
3202 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3207 diff = ultimate_destination_finger_value - my_id64;
3208 finger_table_index = (log10 (diff))/(log10 (2));
3211 return finger_table_index;
3216 * Remove finger and its associated data structures from finger table.
3217 * @param finger Finger to be removed.
3220 remove_existing_finger (struct FingerInfo *existing_finger,
3221 unsigned int finger_table_index)
3223 struct FingerInfo *finger;
3225 finger = &finger_table[finger_table_index];
3226 GNUNET_assert (GNUNET_YES == finger->is_present);
3228 /* If I am my own finger, then we have no trails. */
3229 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3232 finger->is_present = GNUNET_NO;
3233 memset ((void *)&finger_table[finger_table_index], 0,
3234 sizeof (finger_table[finger_table_index]));
3238 /* For all other fingers, send trail teardown across all the trails to reach
3239 finger, and free the finger. */
3240 send_all_finger_trails_teardown (finger);
3241 free_finger (finger, finger_table_index);
3247 * Check if there is already an entry in finger_table at finger_table_index.
3248 * We get the finger_table_index from 64bit finger value we got from the network.
3249 * -- If yes, then select the closest finger.
3250 * -- If new and existing finger are same, then check if you can store more
3252 * -- If yes then add trail, else keep the best trails to reach to the
3254 * -- If the new finger is closest, remove the existing entry, send trail
3255 * teardown message across all the trails to reach the existing entry.
3256 * Add the new finger.
3257 * -- If new and existing finger are different, and existing finger is closest
3259 * -- Update current_search_finger_index.
3260 * @param finger_identity Peer Identity of new finger
3261 * @param finger_trail Trail to reach the new finger
3262 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3263 * @param is_predecessor Is this entry for predecessor in finger_table?
3264 * @param finger_value 64 bit value of finger identity that we got from network.
3265 * @param finger_trail_id Unique identifier of @finger_trail.
3268 finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3269 const struct GNUNET_PeerIdentity *finger_trail,
3270 unsigned int finger_trail_length,
3271 unsigned int is_predecessor,
3272 uint64_t finger_value,
3273 struct GNUNET_HashCode finger_trail_id)
3275 struct FingerInfo *existing_finger;
3276 struct GNUNET_PeerIdentity *closest_peer;
3277 struct FingerInfo *successor;
3278 int updated_finger_trail_length;
3279 unsigned int finger_table_index;
3281 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3282 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3284 /* Invalid finger_table_index. */
3285 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3287 GNUNET_break_op (0);
3291 /* New entry same as successor. */
3292 if ((0 != finger_table_index) &&
3293 (PREDECESSOR_FINGER_ID != finger_table_index))
3295 successor = &finger_table[0];
3296 GNUNET_assert (GNUNET_YES == successor->is_present);
3297 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3298 &successor->finger_identity))
3300 current_search_finger_index = 0;
3305 existing_finger = &finger_table[finger_table_index];
3307 /* No entry present in finger_table for given finger map index. */
3308 if (GNUNET_NO == existing_finger->is_present)
3310 struct GNUNET_PeerIdentity *updated_trail;
3312 /* Shorten the trail if possible. */
3313 updated_finger_trail_length = finger_trail_length;
3315 scan_and_compress_trail (finger_identity, finger_trail,
3316 finger_trail_length, finger_trail_id,
3317 &updated_finger_trail_length);
3318 add_new_finger (finger_identity, updated_trail,
3319 updated_finger_trail_length,
3320 finger_trail_id, finger_table_index);
3321 update_current_search_finger_index (finger_identity,
3322 finger_table_index);
3327 /* If existing entry and finger identity are not same. */
3328 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3331 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3336 /* If the new finger is the closest peer. */
3337 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3339 struct GNUNET_PeerIdentity *updated_trail;
3340 /* Shorten the trail if possible. */
3341 updated_finger_trail_length = finger_trail_length;
3343 scan_and_compress_trail (finger_identity, finger_trail,
3344 finger_trail_length, finger_trail_id,
3345 &updated_finger_trail_length);
3347 remove_existing_finger (existing_finger, finger_table_index);
3348 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3349 finger_trail_id, finger_table_index);
3354 /* Existing finger is the closest one. We need to send trail teardown
3355 across the trail setup in routing table of all the peers. */
3356 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3358 if (finger_trail_length > 0)
3359 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3360 GDS_ROUTING_SRC_TO_DEST,
3363 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3364 GDS_ROUTING_SRC_TO_DEST,
3371 /* If both new and existing entry are same as my_identity, then do nothing. */
3372 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3377 /* If the existing finger is not a friend. */
3379 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3380 &existing_finger->finger_identity))
3382 struct GNUNET_PeerIdentity *updated_trail;
3384 /* Shorten the trail if possible. */
3385 updated_finger_trail_length = finger_trail_length;
3387 scan_and_compress_trail (finger_identity, finger_trail,
3388 finger_trail_length, finger_trail_id,
3389 &updated_finger_trail_length);
3390 /* If there is space to store more trails. */
3391 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3392 add_new_trail (existing_finger, updated_trail,
3393 updated_finger_trail_length, finger_trail_id);
3395 select_and_replace_trail (existing_finger, updated_trail,
3396 updated_finger_trail_length, finger_trail_id);
3400 update_current_search_finger_index (finger_identity, finger_table_index);
3405 * Core handler for P2P put messages.
3406 * @param cls closure
3407 * @param peer sender of the request
3408 * @param message message
3409 * @return #GNUNET_OK to keep the connection open,
3410 * #GNUNET_SYSERR to close it (signal serious error)
3413 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3414 const struct GNUNET_MessageHeader *message)
3416 struct PeerPutMessage *put;
3417 struct GNUNET_PeerIdentity *put_path;
3418 struct GNUNET_PeerIdentity best_known_dest;
3419 struct GNUNET_HashCode intermediate_trail_id;
3420 struct GNUNET_PeerIdentity *next_hop;
3421 enum GNUNET_DHT_RouteOption options;
3422 struct GNUNET_HashCode test_key;
3426 size_t payload_size;
3429 msize = ntohs (message->size);
3430 if (msize < sizeof (struct PeerPutMessage))
3432 GNUNET_break_op (0);
3436 put = (struct PeerPutMessage *) message;
3437 putlen = ntohl (put->put_path_length);
3440 sizeof (struct PeerPutMessage) +
3441 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3443 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3445 GNUNET_break_op (0);
3449 best_known_dest = put->best_known_destination;
3450 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3451 payload = &put_path[putlen];
3452 options = ntohl (put->options);
3453 intermediate_trail_id = put->intermediate_trail_id;
3455 payload_size = msize - (sizeof (struct PeerPutMessage) +
3456 putlen * sizeof (struct GNUNET_PeerIdentity));
3458 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3459 payload, payload_size, &test_key))
3462 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3464 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3465 GNUNET_break_op (0);
3466 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3467 "PUT with key `%s' for block with key %s\n",
3468 put_s, GNUNET_h2s_full (&test_key));
3469 GNUNET_free (put_s);
3474 GNUNET_break_op (0);
3477 /* cannot verify, good luck */
3481 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3483 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3484 ntohl (put->block_type),
3486 NULL, 0, /* bloom filer */
3487 NULL, 0, /* xquery */
3488 payload, payload_size))
3490 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3491 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3494 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3495 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3496 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3497 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3498 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3499 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3501 GNUNET_break_op (0);
3506 /* extend 'put path' by sender */
3507 struct GNUNET_PeerIdentity pp[putlen + 1];
3508 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3510 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3517 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3518 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3520 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3521 GDS_ROUTING_SRC_TO_DEST);
3522 if (NULL == next_hop)
3524 GNUNET_STATISTICS_update (GDS_stats,
3525 gettext_noop ("# Next hop to forward the packet not found "
3526 "trail setup request, packet dropped."),
3528 return GNUNET_SYSERR;
3533 struct Closest_Peer successor;
3534 key_value = GNUNET_ntohll (key_value);
3535 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3537 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3538 *next_hop = successor.next_hop;
3539 intermediate_trail_id = successor.trail_id;
3540 best_known_dest = successor.best_known_destination;
3543 GDS_CLIENTS_process_put (options,
3544 ntohl (put->block_type),
3545 ntohl (put->hop_count),
3546 ntohl (put->desired_replication_level),
3548 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3553 /* I am the final destination */
3554 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest))
3556 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3557 &(put->key),putlen, pp, ntohl (put->block_type),
3558 payload_size, payload);
3562 GDS_NEIGHBOURS_send_put (&put->key,
3563 ntohl (put->block_type),ntohl (put->options),
3564 ntohl (put->desired_replication_level),
3565 best_known_dest, intermediate_trail_id, next_hop,
3566 ntohl (put->hop_count), putlen, pp,
3567 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3568 payload, payload_size);
3575 * Core handler for p2p get requests.
3577 * @param cls closure
3578 * @param peer sender of the request
3579 * @param message message
3580 * @return #GNUNET_OK to keep the connection open,
3581 * #GNUNET_SYSERR to close it (signal serious error)
3584 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3585 const struct GNUNET_MessageHeader *message)
3587 const struct PeerGetMessage *get;
3588 const struct GNUNET_PeerIdentity *get_path;
3589 struct GNUNET_PeerIdentity best_known_dest;
3590 struct GNUNET_HashCode intermediate_trail_id;
3591 struct GNUNET_PeerIdentity *next_hop;
3592 uint32_t get_length;
3596 msize = ntohs (message->size);
3597 if (msize < sizeof (struct PeerGetMessage))
3599 GNUNET_break_op (0);
3603 get = (const struct PeerGetMessage *)message;
3604 get_length = ntohl (get->get_path_length);
3605 best_known_dest = get->best_known_destination;
3606 intermediate_trail_id = get->intermediate_trail_id;
3607 get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3610 sizeof (struct PeerGetMessage) +
3611 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3613 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3615 GNUNET_break_op (0);
3619 /* Add sender to get path */
3620 struct GNUNET_PeerIdentity gp[get_length + 1];
3622 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3623 gp[get_length] = *peer;
3624 get_length = get_length + 1;
3626 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3627 key_value = GNUNET_ntohll (key_value);
3629 /* I am not the final destination. I am part of trail to reach final dest. */
3630 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3632 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3633 GDS_ROUTING_SRC_TO_DEST);
3634 if (NULL == next_hop)
3636 GNUNET_STATISTICS_update (GDS_stats,
3637 gettext_noop ("# Next hop to forward the packet not found "
3638 "GET request, packet dropped."),
3640 return GNUNET_SYSERR;
3645 struct Closest_Peer successor;
3647 successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3648 next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3649 *next_hop = successor.next_hop;
3650 best_known_dest = successor.best_known_destination;
3651 intermediate_trail_id = successor.trail_id;
3654 GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3655 get->desired_replication_level, get->get_path_length,
3657 /* I am the final destination. */
3658 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3660 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3662 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3663 memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3664 get_length = get_length + 1;
3665 /* FIXME: here it may happen that we find our identity closest to key, but
3666 we don't have the data. then in that case, we should forward the packet
3667 to the next closest peer. */
3668 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3669 get_length, final_get_path,
3670 &final_get_path[get_length-2], &my_identity);
3674 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3675 get->desired_replication_level, best_known_dest,
3676 intermediate_trail_id, next_hop, 0,
3684 * Core handler for get result
3685 * @param cls closure
3686 * @param peer sender of the request
3687 * @param message message
3688 * @return #GNUNET_OK to keep the connection open,
3689 * #GNUNET_SYSERR to close it (signal serious error)
3692 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3693 const struct GNUNET_MessageHeader *message)
3695 const struct PeerGetResultMessage *get_result;
3696 const struct GNUNET_PeerIdentity *get_path;
3697 const struct GNUNET_PeerIdentity *put_path;
3698 const void *payload;
3699 size_t payload_size;
3701 unsigned int getlen;
3702 unsigned int putlen;
3703 int current_path_index;
3705 msize = ntohs (message->size);
3706 if (msize < sizeof (struct PeerGetResultMessage))
3708 GNUNET_break_op (0);
3712 get_result = (const struct PeerGetResultMessage *)message;
3713 getlen = ntohl (get_result->get_path_length);
3714 putlen = ntohl (get_result->put_path_length);
3717 sizeof (struct PeerGetResultMessage) +
3718 getlen * sizeof (struct GNUNET_PeerIdentity) +
3719 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3721 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3723 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3725 GNUNET_break_op (0);
3729 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3730 get_path = &put_path[putlen];
3731 payload = (const void *) &get_path[getlen];
3732 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3733 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3735 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3737 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3738 getlen, get_path, putlen,
3739 put_path, get_result->type, payload_size, payload);
3744 current_path_index = search_my_index (get_path, getlen);
3745 if (-1 == current_path_index )
3748 return GNUNET_SYSERR;
3750 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3751 &get_path[current_path_index - 1],
3752 &(get_result->querying_peer), putlen, put_path,
3753 getlen, get_path, get_result->expiration_time,
3754 payload, payload_size);
3757 return GNUNET_SYSERR;
3762 * Find the next hop to pass trail setup message. First find the local best known
3763 * hop from your own identity, friends and finger. If you were part of trail,
3764 * then get the next hop from routing table. Compare next_hop from routing table
3765 * and local best known hop, and return the closest one to final_dest_finger_val
3766 * @param final_dest_finger_val 64 bit value of finger identity
3767 * @param intermediate_trail_id If you are part of trail to reach to some other
3768 * finger, then it is the trail id to reach to
3769 * that finger, else set to 0.
3770 * @param is_predecessor Are we looking for closest successor or predecessor.
3771 * @param current_dest In case you are part of trail, then finger to which
3772 * we should forward the message. Else my own identity
3773 * @return Closest Peer for @a final_dest_finger_val
3775 static struct Closest_Peer
3776 get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3777 struct GNUNET_HashCode intermediate_trail_id,
3778 unsigned int is_predecessor,
3779 struct GNUNET_PeerIdentity prev_hop,
3780 struct GNUNET_PeerIdentity source,
3781 struct GNUNET_PeerIdentity *current_dest)
3783 struct Closest_Peer peer;
3785 /* Find a local best known peer. */
3786 peer = find_successor (final_dest_finger_val, is_predecessor);
3788 /* Am I just a part of a trail towards a finger (current_destination)? */
3789 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest)))
3791 /* Select best successor among one found locally and current_destination
3792 * that we got from network.*/
3793 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3796 struct GNUNET_PeerIdentity *closest_peer;
3797 closest_peer = select_closest_peer (&peer.best_known_destination,
3799 final_dest_finger_val,
3802 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3803 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3805 struct GNUNET_PeerIdentity *next_hop;
3806 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3807 GDS_ROUTING_SRC_TO_DEST);
3808 GNUNET_assert (NULL != next_hop);
3810 peer.next_hop = *next_hop;
3811 peer.best_known_destination = *current_dest;
3812 peer.trail_id = intermediate_trail_id;
3821 * Core handle for PeerTrailSetupMessage.
3822 * @param cls closure
3823 * @param message message
3824 * @param peer peer identity this notification is about
3825 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3828 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3829 const struct GNUNET_MessageHeader *message)
3831 const struct PeerTrailSetupMessage *trail_setup;
3832 const struct GNUNET_PeerIdentity *trail_peer_list;
3833 struct GNUNET_PeerIdentity current_dest;
3834 struct FriendInfo *target_friend;
3835 struct GNUNET_PeerIdentity source;
3836 uint64_t final_dest_finger_val;
3837 struct GNUNET_HashCode intermediate_trail_id;
3838 struct GNUNET_HashCode trail_id;
3839 unsigned int is_predecessor;
3840 uint32_t trail_length;
3843 msize = ntohs (message->size);
3844 if (msize < sizeof (struct PeerTrailSetupMessage))
3846 GNUNET_break_op (0);
3847 return GNUNET_SYSERR;
3850 trail_setup = (const struct PeerTrailSetupMessage *) message;
3851 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3852 sizeof (struct GNUNET_PeerIdentity);
3853 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
3854 sizeof (struct GNUNET_PeerIdentity) != 0)
3856 GNUNET_break_op (0);
3860 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3861 current_dest = trail_setup->best_known_destination;
3862 trail_id = trail_setup->trail_id;
3863 final_dest_finger_val =
3864 GNUNET_ntohll (trail_setup->final_destination_finger_value);
3865 source = trail_setup->source_peer;
3866 is_predecessor = ntohl (trail_setup->is_predecessor);
3867 intermediate_trail_id = trail_setup->intermediate_trail_id;
3869 /* Is my routing table full? */
3870 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3872 GNUNET_assert (NULL !=
3874 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
3875 GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
3876 my_identity, is_predecessor,
3877 trail_peer_list, trail_length,
3878 trail_id, target_friend,
3879 CONGESTION_TIMEOUT);
3883 /* If I was the source and got the message back, then set trail length to 0.*/
3884 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3888 /* Get the next hop to forward the trail setup request. */
3889 struct Closest_Peer next_peer =
3890 get_local_best_known_next_hop (final_dest_finger_val,
3891 intermediate_trail_id,
3897 /* Am I the final destination? */
3898 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
3901 /* If I was not the source of this message for which now I am destination */
3902 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
3904 GDS_ROUTING_add (trail_id, *peer, my_identity);
3907 if(trail_length > 0)
3909 GNUNET_assert (NULL !=
3911 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3912 &trail_peer_list[trail_length-1])));
3916 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
3918 finger_table_add (my_identity, NULL, 0, is_predecessor,
3919 final_dest_finger_val, trail_id);
3922 GNUNET_assert (NULL !=
3924 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source)));
3927 GDS_NEIGHBOURS_send_trail_setup_result (source,
3929 target_friend, trail_length,
3932 final_dest_finger_val,trail_id);
3936 GNUNET_assert (NULL !=
3938 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3939 &next_peer.next_hop)));
3941 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3943 /* Add yourself to list of peers. */
3944 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3946 memcpy (peer_list, trail_peer_list,
3947 trail_length * sizeof (struct GNUNET_PeerIdentity));
3948 peer_list[trail_length] = my_identity;
3950 GDS_NEIGHBOURS_send_trail_setup (source,
3951 final_dest_finger_val,
3952 next_peer.best_known_destination,
3953 target_friend, trail_length + 1, peer_list,
3954 is_predecessor, trail_id,
3955 next_peer.trail_id);
3958 GDS_NEIGHBOURS_send_trail_setup (source,
3959 final_dest_finger_val,
3960 next_peer.best_known_destination,
3961 target_friend, 0, NULL,
3962 is_predecessor, trail_id,
3963 next_peer.trail_id);
3969 /* FIXME: here we are calculating my_index and comparing also in this function.
3970 And we are doing it again here in this function. Re factor the code. */
3972 * FIXME: Should we call this function everywhere in all the handle functions
3973 * where we have a trail to verify from or a trail id. something like
3974 * if prev hop is not same then drop the message.
3975 * Check if sender_peer and peer from which we should receive the message are
3976 * same or different.
3977 * @param trail_peer_list List of peers in trail
3978 * @param trail_length Total number of peers in @a trail_peer_list
3979 * @param sender_peer Peer from which we got the message.
3980 * @param finger_identity Finger to which trail is setup. It is not part of trail.
3981 * @return #GNUNET_YES if sender_peer and peer from which we should receive the
3982 * message are different.
3983 * #GNUNET_NO if sender_peer and peer from which we should receive the
3984 * message are different.
3987 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
3988 unsigned int trail_length,
3989 const struct GNUNET_PeerIdentity *sender_peer,
3990 struct GNUNET_PeerIdentity finger_identity,
3991 struct GNUNET_PeerIdentity source_peer)
3995 /* I am the source peer. */
3996 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3999 /* Is the first element of the trail is sender_peer.*/
4000 if (trail_length > 0)
4002 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4008 /* Is finger the sender peer? */
4009 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4016 /* Get my current location in the trail. */
4017 my_index = search_my_index (trail_peer_list, trail_length);
4021 /* I am the last element in the trail. */
4022 if ((trail_length - 1) == my_index)
4024 /* Is finger the sender_peer? */
4025 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4031 /* Is peer after me in trail the sender peer? */
4032 if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4033 &trail_peer_list[my_index + 1]))
4043 * FIXME: we should also add a case where we search if we are present in the trail
4045 * Core handle for p2p trail setup result messages.
4047 * @param message message
4048 * @param peer sender of this message.
4049 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4052 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4053 const struct GNUNET_MessageHeader *message)
4055 const struct PeerTrailSetupResultMessage *trail_result;
4056 const struct GNUNET_PeerIdentity *trail_peer_list;
4057 struct GNUNET_PeerIdentity next_hop;
4058 struct FriendInfo *target_friend;
4059 struct GNUNET_PeerIdentity querying_peer;
4060 struct GNUNET_PeerIdentity finger_identity;
4061 uint32_t trail_length;
4062 uint64_t ulitmate_destination_finger_value;
4063 uint32_t is_predecessor;
4064 struct GNUNET_HashCode trail_id;
4068 msize = ntohs (message->size);
4069 if (msize < sizeof (struct PeerTrailSetupResultMessage))
4071 GNUNET_break_op (0);
4075 trail_result = (const struct PeerTrailSetupResultMessage *) message;
4076 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4077 sizeof (struct GNUNET_PeerIdentity);
4078 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4079 sizeof (struct GNUNET_PeerIdentity) != 0)
4081 GNUNET_break_op (0);
4085 is_predecessor = ntohl (trail_result->is_predecessor);
4086 querying_peer = trail_result->querying_peer;
4087 finger_identity = trail_result->finger_identity;
4088 trail_id = trail_result->trail_id;
4089 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4090 ulitmate_destination_finger_value =
4091 GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4093 /* FIXME: here we are calculating my_index and comparing also in this function.
4094 And we are doing it again here in this function. Re factor the code. */
4095 /* Ensure that sender peer is the peer from which we were expecting the message. */
4097 if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
4099 peer, finger_identity, querying_peer))
4101 GNUNET_break_op (0);
4102 return GNUNET_SYSERR;
4106 /* Am I the one who initiated the query? */
4107 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4109 /* If I am not my own finger identity, then add routing table entry. */
4110 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4112 GDS_ROUTING_add (trail_id, my_identity, *peer);
4115 finger_table_add (finger_identity, trail_peer_list, trail_length,
4116 is_predecessor, ulitmate_destination_finger_value, trail_id);
4120 /* Get my location in the trail. */
4121 my_index = search_my_index (trail_peer_list, trail_length);
4125 return GNUNET_SYSERR;
4129 next_hop = trail_result->querying_peer;
4131 next_hop = trail_peer_list[my_index - 1];
4133 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4134 &(trail_result->finger_identity))))
4136 GDS_ROUTING_add (trail_id, next_hop, *peer);
4139 GNUNET_assert (NULL !=
4141 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4142 GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4143 target_friend, trail_length, trail_peer_list,
4145 ulitmate_destination_finger_value,
4153 * @param trail Trail to be inverted
4154 * @param trail_length Total number of peers in the trail.
4155 * @return Updated trail
4157 static struct GNUNET_PeerIdentity *
4158 invert_trail (const struct GNUNET_PeerIdentity *trail,
4159 unsigned int trail_length)
4163 struct GNUNET_PeerIdentity *inverted_trail;
4165 inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4168 j = trail_length - 1;
4169 while (i < trail_length)
4171 inverted_trail[i] = trail[j];
4176 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4177 &inverted_trail[0]));
4178 return inverted_trail;
4183 * Return the shortest trail to reach from me to my_predecessor.
4184 * @param current_trail Trail from source to me.
4185 * @param current_trail_length Total number of peers in @a current_trail
4186 * @param trail_length [out] Total number of peers in selected trail.
4187 * @return Updated trail from source peer to my_predecessor.
4189 static struct GNUNET_PeerIdentity *
4190 trail_me_to_my_predecessor (const struct GNUNET_PeerIdentity *current_trail,
4191 unsigned int current_trail_length,
4192 unsigned int *trail_length)
4194 struct GNUNET_PeerIdentity *trail_me_to_predecessor;
4195 struct Trail *trail;
4196 struct Trail_Element *trail_element;
4197 struct FingerInfo *my_predecessor;
4199 unsigned int shortest_trail_length = 0;
4200 unsigned int trail_index = 0;
4201 unsigned int flag = 0;
4203 my_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4205 GNUNET_assert (GNUNET_YES == my_predecessor->is_present);
4209 /* Choose the shortest path from me to my predecessor. */
4210 for (i = 0; i < my_predecessor->trails_count; i++)
4212 trail = &my_predecessor->trail_list[i];
4215 shortest_trail_length = trail->trail_length;
4220 if (trail->trail_length > shortest_trail_length)
4222 shortest_trail_length = trail->trail_length;
4226 *trail_length = shortest_trail_length;
4227 GNUNET_assert(*trail_length != 0);
4228 trail_me_to_predecessor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
4231 /* Copy the selected trail and send this trail to calling function. */
4233 trail = &my_predecessor->trail_list[trail_index];
4234 trail_element = trail->trail_head;
4235 while ( i < shortest_trail_length)
4237 trail_me_to_predecessor[i] = trail_element->peer;
4239 trail_element = trail_element->next;
4242 return trail_me_to_predecessor;
4247 * FIXME In case predecessor is a friend then do we add it in routing table.
4248 * if not then check the logic of trail teardown in case we compress the trail
4249 * such that friend is finger. then do we remove the entry from end points or
4250 * not. Ideally we should remove the entries from end point.
4251 * Add finger as your predecessor. To add, first generate a new trail id, invert
4252 * the trail to get the trail from me to finger, add an entry in your routing
4253 * table, send add trail message to peers which are part of trail from me to
4254 * finger and add finger in finger table.
4257 * @param trail_length
4260 update_predecessor (struct GNUNET_PeerIdentity finger,
4261 struct GNUNET_PeerIdentity *trail,
4262 unsigned int trail_length)
4264 struct GNUNET_HashCode trail_to_new_predecessor_id;
4265 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4266 struct FriendInfo *target_friend;
4268 /* Generate trail id for trail from me to new predecessor = finger. */
4269 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4270 &trail_to_new_predecessor_id,
4271 sizeof (trail_to_new_predecessor_id));
4272 //test_finger_table_print();
4273 /* Finger is a friend. */
4274 if (trail_length == 0)
4276 trail_to_new_predecessor = NULL;
4277 /* FIXME: check that you always add trail entry even if your finger is
4279 GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger); /*FIXME; Check that the corresponding pred adds entry also. */
4280 GNUNET_assert (NULL != (target_friend =
4281 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4286 /* Invert the trail to get the trail from me to finger, NOT including the
4288 trail_to_new_predecessor = invert_trail (trail, trail_length);
4290 /* Add an entry in your routing table. */
4291 GDS_ROUTING_add (trail_to_new_predecessor_id,
4293 trail_to_new_predecessor[0]);
4295 GNUNET_assert (NULL != (target_friend =
4296 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4297 &trail_to_new_predecessor[0])));
4298 GNUNET_assert (NULL != (
4299 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4300 &trail[trail_length - 1])));
4303 /* Add entry in routing table of all peers that are part of trail from me
4304 to finger, including finger. */
4305 GDS_NEIGHBOURS_send_add_trail (my_identity,
4307 trail_to_new_predecessor_id,
4308 trail_to_new_predecessor,
4312 add_new_finger (finger, trail_to_new_predecessor, trail_length,
4313 trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4314 GNUNET_free_non_null (trail_to_new_predecessor);
4318 /* 3. In case you are successor, then
4319 * 3.1 check if you have a predecessor
4320 * 3.2 if no predecessor, then add the source of this message as your
4321 * predecessor. To add, first you should generate a new trail id,
4322 * invert the trail, send add trail message across new trail, add
4323 * an entry in finger table. Now, destination also have routing
4324 * table entry so add in your routing table also.
4325 * 3.3 If its closer than existing one, then do everything in step 1 and
4326 * free existing finger.
4327 * 3.3 If its same as the old one, then do nothing.
4328 * 3.4 if its not same as old one, and between source and old one, old one
4329 * is the correct predecessor, then construct a trail from source
4330 * to your old successor. scan the trail to remove duplicate entries.
4331 * 4. send verify successor result, with trail id of trail from source to
4332 * me. And also send the new trail from source to reach to its probable
4335 * 1. this function is called from both verify and notify.
4336 * 2. so write in a way that it is used in both.
4339 * Check if you have a predecessor.
4340 * 1. if no predecessor, then add finger as your predecessor. To add, first
4341 * generate a new trail id, invert the trail to get the trail from me to finger,
4342 * add an entry in your routing table, send add trail message to peers which
4343 * are part of trail from me to finger and add finger in finger table.
4344 * 2. If there is a predecessor, then compare existing one and finger.
4345 * 2.1 If finger is correct predecessor, then remove current_predecessor. And
4346 * do everything in step 1 to add finger into finger table.
4347 * 2.2 If current_predecessor is correct predecessor, the construct a trail from
4348 * finger to current_predecessor.
4351 * @param trail_length
4355 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4356 struct GNUNET_PeerIdentity *trail,
4357 unsigned int trail_length)
4359 struct FingerInfo *current_predecessor;
4360 struct GNUNET_PeerIdentity *closest_peer;
4361 uint64_t predecessor_value;
4362 unsigned int is_predecessor = 1;
4364 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4365 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4367 /* No predecessor. Add finger as your predecessor. */
4368 if (GNUNET_NO == current_predecessor->is_present)
4370 update_predecessor (finger, trail, trail_length);
4373 if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4377 //test_finger_table_print();
4378 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4379 closest_peer = select_closest_peer (&finger,
4380 ¤t_predecessor->finger_identity,
4381 predecessor_value, is_predecessor);
4383 /* Finger is the closest predecessor. Remove the existing one and add the new
4385 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, &finger))
4387 remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4388 update_predecessor (finger, trail, trail_length);
4397 * Check if the the peer from which we got the message is the valid peer from
4398 * which we should expect the message.
4399 * @param peer Peer from which we got the message.
4400 * @param trail_id Trail in which peer should be either my prev_hop or next_hop
4401 * depending on the @a trail_direction.
4402 * @param trail_direction Is trail from source to destination or opposite way.
4403 * @return #GNUNET_YES if Peer is valid.
4404 * #GNUNET_NO if Peer is not valid.
4407 is_sender_peer_valid (const struct GNUNET_PeerIdentity *peer,
4408 struct GNUNET_HashCode trail_id,
4409 enum GDS_ROUTING_trail_direction trail_direction)
4411 struct GNUNET_PeerIdentity *peer_routing_table;
4413 peer_routing_table = GDS_ROUTING_get_next_hop (trail_id, !trail_direction);
4415 if(0 == GNUNET_CRYPTO_cmp_peer_identity (peer, peer_routing_table))
4422 * Core handle for p2p verify successor messages.
4423 * @param cls closure
4424 * @param message message
4425 * @param peer peer identity this notification is about
4426 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4429 handle_dht_p2p_verify_successor(void *cls,
4430 const struct GNUNET_PeerIdentity *peer,
4431 const struct GNUNET_MessageHeader *message)
4433 const struct PeerVerifySuccessorMessage *vsm;
4434 struct GNUNET_HashCode trail_id;
4435 struct GNUNET_PeerIdentity successor;
4436 struct GNUNET_PeerIdentity source_peer;
4437 struct GNUNET_PeerIdentity *trail;
4438 struct GNUNET_PeerIdentity *next_hop;
4439 struct GNUNET_PeerIdentity *trail_to_predecessor; //used unintialized somewhere.
4440 struct FingerInfo *current_predecessor;
4441 struct FriendInfo *target_friend;
4442 unsigned int trail_to_predecessor_length = 0;
4444 unsigned int trail_length;
4446 msize = ntohs (message->size);
4448 if (msize < sizeof (struct PeerVerifySuccessorMessage))
4450 GNUNET_break_op (0);
4454 vsm = (const struct PeerVerifySuccessorMessage *) message;
4455 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4456 sizeof (struct GNUNET_PeerIdentity);
4457 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4458 sizeof (struct GNUNET_PeerIdentity) != 0)
4460 GNUNET_break_op (0);
4464 trail_id = vsm->trail_id;
4465 source_peer = vsm->source_peer;
4466 successor = vsm->successor;
4467 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4469 if(GNUNET_NO == is_sender_peer_valid (peer,trail_id, GDS_ROUTING_SRC_TO_DEST))
4472 return GNUNET_SYSERR;
4475 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4477 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4479 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4480 if (NULL == next_hop)
4483 return GNUNET_SYSERR;
4485 GNUNET_assert (NULL !=
4487 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4489 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4490 trail_id, trail, trail_length,
4495 /* I am the destination of this message. */
4497 /* Check if the source_peer could be our predecessor and if yes then update
4499 compare_and_update_predecessor (source_peer, trail, trail_length);
4501 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4503 /* Is source of this message NOT my predecessor. */
4504 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity,
4507 /* if current predecessor is not a friend, we have a trail to reach to it*/
4508 if (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4509 ¤t_predecessor->finger_identity)))
4511 trail_to_predecessor =
4512 trail_me_to_my_predecessor (trail,
4514 &trail_to_predecessor_length);
4519 trail_to_predecessor = GNUNET_new(struct GNUNET_PeerIdentity);
4520 trail_to_predecessor = NULL;
4521 trail_to_predecessor_length = 0;
4523 GNUNET_assert (NULL !=
4525 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4526 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4527 current_predecessor->finger_identity,
4528 trail_id, trail_to_predecessor,
4529 trail_to_predecessor_length,
4530 GDS_ROUTING_DEST_TO_SRC,
4532 GNUNET_free_non_null (trail_to_predecessor);
4538 * Construct the trail from me to probable successor that goes through current
4539 * successor. Scan this trail to check if you can shortcut the trail somehow.
4540 * In case we can shortcut the trail, don't send trail compression as we don't
4541 * have any entry in routing table.
4542 * @param current_successor
4543 * @param probable_successor
4544 * @param trail_from_curr_to_probable_successor
4545 * @param trail_from_curr_to_probable_successor_length
4546 * @param trail_to_new_successor_length
4549 static struct GNUNET_PeerIdentity *
4550 get_trail_to_new_successor (struct FingerInfo *current_successor,
4551 struct GNUNET_PeerIdentity probable_successor,
4552 const struct GNUNET_PeerIdentity *trail_from_curr_to_probable_successor,
4553 unsigned int trail_from_curr_to_probable_successor_length,
4554 unsigned int *trail_to_new_successor_length)
4556 struct GNUNET_PeerIdentity *trail_to_new_successor;
4557 unsigned int shortest_trail_length = 0;
4558 unsigned int flag = 0;
4559 unsigned int shortest_trail_index = 0;
4560 struct Trail *trail;
4561 struct Trail_Element *trail_element;
4564 /* If the probable successor is a friend, then we don't need to have a trail
4566 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4567 &probable_successor))
4569 trail_to_new_successor = NULL;
4570 *trail_to_new_successor_length = 0;
4571 return trail_to_new_successor;
4575 * FIXME: can we some how use the select_finger_trail here??
4576 * complete this logic.
4577 * 1. Choose the shortest trail to reach to current successor.
4578 * 2. append the trail with the current trail
4579 * 3. scan the trail for duplicate elements
4580 * 4. scan the trail for friend
4581 * 5. get the shortest trail.
4582 * 6. send back the trail.
4586 /* Choose the shortest trail to reach the current_successor */
4587 for (i = 0; i < current_successor->trails_count; i++)
4589 trail = ¤t_successor->trail_list[i];
4592 shortest_trail_index = i;
4593 shortest_trail_length = trail->trail_length;
4598 if (shortest_trail_length > trail->trail_length)
4600 shortest_trail_index = i;
4601 shortest_trail_length = trail->trail_length;
4606 /* It means that probable successor is the friend of current successor. */
4607 if (0 == trail_from_curr_to_probable_successor_length)
4609 *trail_to_new_successor_length = shortest_trail_length + 1;
4610 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4611 (*trail_to_new_successor_length));
4612 /* Copy the selected trail and send this trail to calling function. */
4614 trail = ¤t_successor->trail_list[shortest_trail_index];
4615 trail_element = trail->trail_head;
4616 while ( i < shortest_trail_length)
4618 trail_to_new_successor[i] = trail_element->peer;
4620 trail_element = trail_element->next;
4623 trail_to_new_successor[i] = current_successor->finger_identity;
4627 *trail_to_new_successor_length = shortest_trail_length +
4628 trail_from_curr_to_probable_successor_length;
4629 trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4630 (*trail_to_new_successor_length));
4631 /* Copy the selected trail and send this trail to calling function. */
4633 trail = ¤t_successor->trail_list[shortest_trail_index];
4634 trail_element = trail->trail_head;
4635 while ( i < shortest_trail_length)
4637 trail_to_new_successor[i] = trail_element->peer;
4639 trail_element = trail_element->next;
4643 while (j < trail_from_curr_to_probable_successor_length)
4645 trail_to_new_successor[i] = trail_from_curr_to_probable_successor[j];
4650 return trail_to_new_successor;
4655 * Compare probable successor and current successor.
4656 * If the probable successor is the correct successor, then construct the trail
4657 * from me to probable successor that goes through current successor. Scan this
4658 * trail to check if you can shortcut the trail somehow. In case we can short
4659 * cut the trail, don't send trail compression as we don't have any entry in
4661 * Once you have scanned trail, then add an entry in finger table.
4662 * Add an entry in routing table (Only if new successor is NOT a friend).
4663 * @param probable_successor Peer which could be our successor
4664 * @param trail_from_curr_to_probable_successor Trail from current successor
4665 * to probable successor, NOT
4667 * @param trail_from_curr_to_probable_successor_length Total number of peers
4668 * in @a trail_from_curr_to_probable_successor
4671 compare_and_update_successor (struct GNUNET_PeerIdentity probable_successor,
4672 const struct GNUNET_PeerIdentity *trail_from_curr_to_probable_successor,
4673 unsigned int trail_from_curr_to_probable_successor_length)
4675 struct GNUNET_PeerIdentity *closest_peer;
4676 struct GNUNET_PeerIdentity *trail_to_new_successor;
4677 struct GNUNET_HashCode trail_id;
4678 unsigned int trail_to_new_successor_length;
4679 uint64_t successor_value;
4680 struct FingerInfo *current_successor;
4681 struct FriendInfo *target_friend;
4682 unsigned int is_predecessor = 0;
4683 //test_finger_table_print();
4684 current_successor = &finger_table[0];
4685 GNUNET_assert (GNUNET_YES == current_successor->is_present);
4687 /* Compute the 64 bit value of successor identity. We need this as we need to
4688 * find the closest peer w.r.t this value.*/
4689 successor_value = compute_finger_identity_value (0);
4690 closest_peer = select_closest_peer (¤t_successor->finger_identity,
4691 &probable_successor,
4692 successor_value, is_predecessor);
4694 /* If the current_successor is the closest one, then exit. */
4695 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4696 ¤t_successor->finger_identity))
4699 /* probable successor is the closest_peer. */
4701 /* Get the trail to reach to your new successor. */
4702 trail_to_new_successor = get_trail_to_new_successor (current_successor,
4704 trail_from_curr_to_probable_successor,
4705 trail_from_curr_to_probable_successor_length,
4706 &trail_to_new_successor_length);
4707 /* Remove the existing successor. */
4708 remove_existing_finger (current_successor, 0);
4710 /* Generate a new trail id to reach to your new successor. */
4711 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4712 &trail_id, sizeof (trail_id));
4713 add_new_finger (probable_successor, trail_to_new_successor,
4714 trail_to_new_successor_length, trail_id, 0);
4717 if (trail_to_new_successor_length > 0)
4719 GDS_ROUTING_add (trail_id, my_identity, trail_to_new_successor[0]);
4720 GNUNET_assert (NULL !=
4721 (target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4722 &trail_to_new_successor[0])));
4726 GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4727 GNUNET_assert (NULL !=
4729 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4730 &probable_successor)));
4733 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4734 trail_from_curr_to_probable_successor,
4735 trail_from_curr_to_probable_successor_length,
4743 * Core handle for p2p verify successor result messages.
4744 * @param cls closure
4745 * @param message message
4746 * @param peer peer identity this notification is about
4747 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4750 handle_dht_p2p_verify_successor_result(void *cls,
4751 const struct GNUNET_PeerIdentity *peer,
4752 const struct GNUNET_MessageHeader *message)
4754 const struct PeerVerifySuccessorResultMessage *vsrm;
4755 enum GDS_ROUTING_trail_direction trail_direction;
4756 struct GNUNET_PeerIdentity querying_peer;
4757 struct GNUNET_HashCode trail_id;
4758 struct GNUNET_PeerIdentity *next_hop;
4759 struct FriendInfo *target_friend;
4760 struct GNUNET_PeerIdentity probable_successor;
4761 const struct GNUNET_PeerIdentity *trail;
4762 unsigned int trail_length;
4765 msize = ntohs (message->size);
4766 /* We send a trail to reach from old successor to new successor, if
4767 * old_successor != new_successor.*/
4768 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4770 GNUNET_break_op (0);
4774 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4775 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4776 sizeof (struct GNUNET_PeerIdentity);
4778 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
4779 sizeof (struct GNUNET_PeerIdentity) != 0)
4781 GNUNET_break_op (0);
4785 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4786 querying_peer = vsrm->querying_peer;
4787 trail_direction = ntohl (vsrm->trail_direction);
4788 trail_id = vsrm->trail_id;
4789 probable_successor = vsrm->probable_successor;
4791 //FIXME: add a check to ensure that peer from which you got the message is
4793 /* I am the querying_peer. */
4794 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4796 compare_and_update_successor (probable_successor, trail, trail_length);
4800 /*If you are not the querying peer then pass on the message */
4801 GNUNET_assert (NULL != (next_hop =
4802 GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
4803 GNUNET_assert (NULL !=
4805 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4806 GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4807 vsrm->current_successor,
4808 probable_successor, trail_id,
4811 trail_direction, target_friend);
4817 * Core handle for p2p notify new successor messages.
4818 * @param cls closure
4819 * @param message message
4820 * @param peer peer identity this notification is about
4821 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4824 handle_dht_p2p_notify_new_successor(void *cls,
4825 const struct GNUNET_PeerIdentity *peer,
4826 const struct GNUNET_MessageHeader *message)
4828 const struct PeerNotifyNewSuccessorMessage *nsm;
4829 struct GNUNET_PeerIdentity *trail;
4830 struct GNUNET_PeerIdentity source;
4831 struct GNUNET_PeerIdentity new_successor;
4832 struct GNUNET_HashCode trail_id;
4833 struct GNUNET_PeerIdentity next_hop;
4834 struct FriendInfo *target_friend;
4837 uint32_t trail_length;
4839 msize = ntohs (message->size);
4840 /* We have the trail to reach from source to new successor. */
4841 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
4843 GNUNET_break_op (0);
4847 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
4848 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
4849 sizeof (struct GNUNET_PeerIdentity);
4850 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4851 sizeof (struct GNUNET_PeerIdentity) != 0)
4853 GNUNET_break_op (0);
4857 trail = (struct GNUNET_PeerIdentity *) &nsm[1];
4858 source = nsm->source_peer;
4859 new_successor = nsm->new_successor;
4860 trail_id = nsm->trail_id;
4862 //FIXME: add a check to make sure peer is correct.
4864 /* I am the new_successor to source_peer. */
4865 if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
4867 GDS_ROUTING_add (trail_id, *peer, my_identity);
4868 compare_and_update_predecessor (source, trail, trail_length);
4872 /* I am part of trail to reach to successor. */
4873 my_index = search_my_index (trail, trail_length);
4876 GNUNET_break_op (0);
4877 return GNUNET_SYSERR;
4879 if ((trail_length-1) == my_index) //FIXMe: SHOULD IT BE TRAIL_LENGTH - 1.s
4880 next_hop = new_successor;
4882 next_hop = trail[my_index + 1];
4884 /* Add an entry in routing table for trail from source to its new successor. */
4885 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
4886 GNUNET_assert (NULL !=
4888 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4889 GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
4891 trail_id, target_friend);
4898 * Core handler for P2P trail rejection message
4899 * @param cls closure
4900 * @param message message
4901 * @param peer peer identity this notification is about
4902 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4905 handle_dht_p2p_trail_setup_rejection (void *cls,
4906 const struct GNUNET_PeerIdentity *peer,
4907 const struct GNUNET_MessageHeader *message)
4909 const struct PeerTrailRejectionMessage *trail_rejection;
4910 unsigned int trail_length;
4911 const struct GNUNET_PeerIdentity *trail_peer_list;
4912 struct FriendInfo *target_friend;
4913 struct GNUNET_TIME_Relative congestion_timeout;
4914 struct GNUNET_HashCode trail_id;
4915 struct GNUNET_PeerIdentity next_peer;
4916 struct GNUNET_PeerIdentity source;
4917 struct GNUNET_PeerIdentity *next_hop;
4918 uint64_t ultimate_destination_finger_value;
4919 unsigned int is_predecessor;
4922 msize = ntohs (message->size);
4923 /* We are passing the trail setup so far. */
4924 if (msize < sizeof (struct PeerTrailRejectionMessage))
4926 GNUNET_break_op (0);
4930 trail_rejection = (const struct PeerTrailRejectionMessage *) message;
4931 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
4932 sizeof (struct GNUNET_PeerIdentity);
4933 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
4934 sizeof (struct GNUNET_PeerIdentity) != 0)
4936 GNUNET_break_op (0);
4940 trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
4941 is_predecessor = ntohl (trail_rejection->is_predecessor);
4942 congestion_timeout = trail_rejection->congestion_time;
4943 source = trail_rejection->source_peer;
4944 trail_id = trail_rejection->trail_id;
4945 ultimate_destination_finger_value =
4946 GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
4948 /* First set the congestion time of the friend that sent you this message. */
4949 GNUNET_assert (NULL !=
4951 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4952 target_friend->congestion_timestamp =
4953 GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
4954 congestion_timeout);
4956 /* I am the source peer which wants to setup the trail. Do nothing.
4957 * send_find_finger_trail_task is scheduled periodically.*/
4958 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
4961 /* If I am congested then pass this message to peer before me in trail. */
4962 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
4964 struct GNUNET_PeerIdentity *new_trail;
4965 unsigned int new_trail_length;
4967 /* Remove yourself from the trail setup so far. */
4968 if (trail_length == 1)
4971 new_trail_length = 0;
4976 memcpy (&next_hop , &trail_peer_list[trail_length - 2],
4977 sizeof (struct GNUNET_PeerIdentity));
4979 /* Remove myself from the trail. */
4980 new_trail_length = trail_length -1;
4981 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4982 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4985 GNUNET_assert (NULL !=
4987 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4988 GDS_NEIGHBOURS_send_trail_rejection (source,
4989 ultimate_destination_finger_value,
4990 my_identity, is_predecessor,
4991 new_trail,new_trail_length,trail_id,
4992 target_friend, CONGESTION_TIMEOUT);
4994 GNUNET_free (new_trail);
4998 struct Closest_Peer successor;
4999 successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5000 /* Am I the final destination? */
5001 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5004 if (0 == trail_length)
5007 next_peer = trail_peer_list[trail_length-1];
5009 GNUNET_assert (NULL !=
5011 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5013 GDS_NEIGHBOURS_send_trail_setup_result (source,
5015 target_friend, trail_length,
5018 ultimate_destination_finger_value,
5023 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5025 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5026 peer_list[trail_length] = my_identity;
5028 GNUNET_assert (NULL !=
5030 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5032 GDS_NEIGHBOURS_send_trail_setup (source,
5033 ultimate_destination_finger_value,
5034 successor.best_known_destination,
5035 target_friend, trail_length + 1, peer_list,
5036 is_predecessor, trail_id,
5037 successor.trail_id);
5044 * Core handle for p2p trail tear compression messages.
5045 * @param cls closure
5046 * @param message message
5047 * @param peer peer identity this notification is about
5048 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5051 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5052 const struct GNUNET_MessageHeader *message)
5054 const struct PeerTrailCompressionMessage *trail_compression;
5055 struct GNUNET_PeerIdentity *next_hop;
5056 struct FriendInfo *target_friend;
5057 struct GNUNET_HashCode trail_id;
5060 msize = ntohs (message->size);
5062 if (msize != sizeof (struct PeerTrailCompressionMessage))
5064 GNUNET_break_op (0);
5068 trail_compression = (const struct PeerTrailCompressionMessage *) message;
5069 trail_id = trail_compression->trail_id;
5071 /* Am I the new first friend to reach to finger of this trail. */
5072 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5075 GNUNET_assert (NULL !=
5076 (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5077 &trail_compression->source_peer)));
5079 /* Update your prev hop to source of this message. */
5080 GNUNET_assert (GNUNET_SYSERR !=
5081 (GDS_ROUTING_update_trail_prev_hop (trail_id,
5082 trail_compression->source_peer)));
5086 /* Pass the message to next hop to finally reach to new_first_friend. */
5087 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5088 GDS_ROUTING_test_print();
5090 if (NULL == next_hop)
5096 GNUNET_assert (NULL !=
5098 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5100 GDS_ROUTING_remove_trail (trail_id);
5102 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5104 trail_compression->new_first_friend,
5111 * Core handler for trail teardown message.
5112 * @param cls closure
5113 * @param message message
5114 * @param peer sender of this messsage.
5115 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5118 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5119 const struct GNUNET_MessageHeader *message)
5121 const struct PeerTrailTearDownMessage *trail_teardown;
5122 enum GDS_ROUTING_trail_direction trail_direction;
5123 struct GNUNET_HashCode trail_id;
5124 struct GNUNET_PeerIdentity *next_hop;
5127 msize = ntohs (message->size);
5129 /* Here we pass only the trail id. */
5130 if (msize != sizeof (struct PeerTrailTearDownMessage))
5132 GNUNET_break_op (0);
5136 trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5137 trail_direction = ntohl (trail_teardown->trail_direction);
5138 trail_id = trail_teardown->trail_id;
5140 /* Check if peer is the real peer from which we should get this message.*/
5141 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5142 /* FIXME: is using negation of trail direction correct. */
5144 GNUNET_assert (NULL != (prev_hop =
5145 GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5146 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5149 return GNUNET_SYSERR;
5153 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5155 if (NULL == next_hop)
5158 return GNUNET_SYSERR;
5161 /* I am the next hop, which means I am the final destination. */
5162 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5164 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5169 /* If not final destination, then send a trail teardown message to next hop.*/
5170 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5171 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5172 GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5180 * Core handle for p2p add trail message.
5181 * @param cls closure
5182 * @param message message
5183 * @param peer peer identity this notification is about
5184 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5187 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5188 const struct GNUNET_MessageHeader *message)
5190 const struct PeerAddTrailMessage *add_trail;
5191 const struct GNUNET_PeerIdentity *trail;
5192 struct GNUNET_HashCode trail_id;
5193 struct GNUNET_PeerIdentity destination_peer;
5194 struct GNUNET_PeerIdentity source_peer;
5195 struct GNUNET_PeerIdentity next_hop;
5196 unsigned int trail_length;
5197 unsigned int my_index;
5200 msize = ntohs (message->size);
5201 /* In this message we pass the whole trail from source to destination as we
5202 * are adding that trail.*/
5203 if (msize < sizeof (struct PeerAddTrailMessage))
5205 GNUNET_break_op (0);
5209 add_trail = (const struct PeerAddTrailMessage *) message;
5210 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5211 sizeof (struct GNUNET_PeerIdentity);
5212 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5213 sizeof (struct GNUNET_PeerIdentity) != 0)
5215 GNUNET_break_op (0);
5219 trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5220 destination_peer = add_trail->destination_peer;
5221 source_peer = add_trail->source_peer;
5222 trail_id = add_trail->trail_id;
5224 //FIXME: add a check that sender peer is not malicious. Make it a generic
5225 // function so that it can be used in all other functions where we need the
5226 // same functionality.
5228 /* I am not the destination of the trail. */
5229 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5231 struct FriendInfo *target_friend;
5233 /* Get my location in the trail. */
5234 my_index = search_my_index (trail, trail_length);
5238 GNUNET_break_op (0);
5239 return GNUNET_SYSERR;
5243 if ((trail_length - 1) == my_index)
5246 next_hop = destination_peer;
5250 next_hop = trail[my_index + 1];
5252 /* FIXME: check that you always add trail entry even if your finger is
5254 /* Add in your routing table. */
5255 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5256 GNUNET_assert (NULL !=
5258 GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5259 GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5260 trail, trail_length, target_friend);
5263 /* FIXME: check that you always add trail entry even if your finger is
5265 /* I am the destination. Add an entry in routing table. */
5266 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5272 * Free the finger trail in which the first friend to reach to a finger is
5273 * disconnected_friend. Also remove entry from routing table for that particular
5275 * @param disconnected_friend PeerIdentity of friend which got disconnected
5276 * @param remove_finger Finger whose trail we need to check if it has
5277 * disconnected_friend as the first hop.
5278 * @return Total number of trails in which disconnected_friend was the first
5282 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5283 struct FingerInfo *remove_finger)
5285 unsigned int matching_trails_count;
5288 /* Number of trails with disconnected_friend as the first hop in the trail
5289 * to reach from me to remove_finger, NOT including endpoints. */
5290 matching_trails_count = 0;
5292 /* Iterate over all the trails of finger. */
5293 for (i = 0; i < remove_finger->trails_count; i++)
5295 struct Trail *trail;
5296 trail = &remove_finger->trail_list[i];
5298 /* This assertion is ensure that there are no gaps in the trail list.
5299 REMOVE IT AFTERWARDS. */
5300 GNUNET_assert (GNUNET_YES == trail->is_present);
5302 /* First friend to reach to finger is disconnected_peer. */
5303 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5304 disconnected_friend))
5306 struct GNUNET_PeerIdentity *next_hop;
5307 struct FriendInfo *remove_friend;
5309 GNUNET_assert (NULL !=
5311 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5312 disconnected_friend)));
5313 /* FIXME: removing no but check it. */
5314 //remove_friend->trails_count--;
5315 next_hop = GDS_ROUTING_get_next_hop (trail->trail_id,
5316 GDS_ROUTING_SRC_TO_DEST);
5318 /* Here it may happen that as all the peers got disconnected, the entry in
5319 routing table for that particular trail has been removed, because the
5320 previously disconnected peer was either a next hop or prev hop of that
5322 if (NULL == next_hop)
5325 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5327 matching_trails_count++;
5328 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5331 trail->is_present = GNUNET_NO;
5334 return matching_trails_count;
5339 * Iterate over finger_table entries.
5340 * 0. Ignore finger which is my_identity or if no valid entry present at
5341 * that finger index.
5342 * 1. If disconnected_friend is a finger, then remove the routing entry from
5343 your own table. Free the trail.
5344 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5345 * 2.1 Remove all the trails and entry from routing table in which disconnected
5346 * friend is the first friend in the trail. If disconnected_friend is the
5347 * first friend in all the trails to reach finger, then remove the finger.
5348 * @param disconnected_friend Peer identity of friend which got disconnected.
5351 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5353 struct FingerInfo *remove_finger;
5354 struct FriendInfo *remove_friend;
5355 int removed_trails_count;
5358 /* Iterate over finger table entries. */
5359 for (i = 0; i < MAX_FINGERS; i++)
5361 remove_finger = &finger_table[i];
5363 /* No finger stored at this trail index. */
5364 if (GNUNET_NO == remove_finger->is_present)
5367 /* I am my own finger, then ignore this finger. */
5368 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5372 /* Is disconnected_peer a finger? */
5373 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5374 &remove_finger->finger_identity))
5376 struct GNUNET_PeerIdentity *next_hop;
5377 struct GNUNET_HashCode trail_id;
5380 GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5381 trail_id = remove_finger->trail_list[0].trail_id;
5385 GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5387 /* FIXME: This assertion fails check why*/
5389 (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5390 &remove_finger->finger_identity)));
5391 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5392 GNUNET_assert (NULL !=
5394 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5395 disconnected_peer)));
5398 remove_finger->trail_list[0].is_present = GNUNET_NO;
5399 //GNUNET_assert (0 != remove_friend->trails_count);
5400 //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5401 remove_finger->is_present = GNUNET_NO;
5402 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5406 /* If finger is a friend but not disconnected_friend, then continue. */
5407 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5408 &remove_finger->finger_identity))
5411 /* Iterate over the list of trails to reach remove_finger. Check if
5412 * disconnected_friend is the first friend in any of the trail. */
5413 removed_trails_count = remove_matching_trails (disconnected_peer,
5415 remove_finger->trails_count =
5416 remove_finger->trails_count - removed_trails_count;
5417 /* All the finger trails had disconnected_friend as the first friend,
5418 * so free the finger. */
5419 if (remove_finger->trails_count == 0)
5421 remove_finger->is_present = GNUNET_NO;
5422 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5429 * Method called whenever a peer disconnects.
5431 * @param cls closure
5432 * @param peer peer identity this notification is about
5435 handle_core_disconnect (void *cls,
5436 const struct GNUNET_PeerIdentity *peer)
5438 struct FriendInfo *remove_friend;
5440 /* If disconnected to own identity, then return. */
5441 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5444 GNUNET_assert (NULL != (remove_friend =
5445 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5447 /* Remove fingers with peer as first friend or if peer is a finger. */
5448 remove_matching_fingers (peer);
5450 /* Remove any trail from routing table of which peer is a part of. This function
5451 * internally sends a trail teardown message in the direction of which
5452 * disconnected peer is not part of. */
5453 GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5455 //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5457 /* Remove peer from friend_peermap. */
5458 GNUNET_assert (GNUNET_YES ==
5459 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5463 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5466 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5468 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5469 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5478 * Method called whenever a peer connects.
5480 * @param cls closure
5481 * @param peer_identity peer identity this notification is about
5484 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5486 struct FriendInfo *friend;
5488 /* Check for connect to self message */
5489 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5492 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5494 /* If peer already exists in our friend_peermap, then exit. */
5495 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
5502 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
5505 friend = GNUNET_new (struct FriendInfo);
5506 friend->id = *peer_identity;
5508 GNUNET_assert (GNUNET_OK ==
5509 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5510 peer_identity, friend,
5511 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5514 /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/
5515 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
5516 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5521 * To be called on core init/fail.
5523 * @param cls service closure
5524 * @param identity the public identity of this peer
5527 core_init (void *cls,
5528 const struct GNUNET_PeerIdentity *identity)
5530 my_identity = *identity;
5533 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5534 my_id64 = GNUNET_ntohll (my_id64);
5535 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5536 "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5541 * Initialize finger table entries.
5544 finger_table_init ()
5549 for(i = 0; i < MAX_FINGERS; i++)
5551 finger_table[i].is_present = GNUNET_NO;
5552 for (j = 0; j < MAXIMUM_TRAILS_PER_FINGER; j++)
5553 finger_table[i].trail_list[j].is_present = GNUNET_NO;
5554 memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5560 * Initialize neighbours subsystem.
5561 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5564 GDS_NEIGHBOURS_init (void)
5566 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5567 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5568 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5569 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5570 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5571 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5572 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5573 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5574 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5575 {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5576 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION,
5577 sizeof (struct PeerTrailCompressionMessage)},
5578 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
5579 sizeof (struct PeerTrailTearDownMessage)},
5580 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5585 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5586 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5587 GNUNET_NO, core_handlers);
5588 if (NULL == core_api)
5589 return GNUNET_SYSERR;
5591 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5592 finger_table_init ();
5599 * Shutdown neighbours subsystem.
5602 GDS_NEIGHBOURS_done (void)
5604 if (NULL == core_api)
5607 GNUNET_CORE_disconnect (core_api);
5610 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5611 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5612 friend_peermap = NULL;
5614 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5617 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5618 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5626 * @return my identity
5628 struct GNUNET_PeerIdentity
5629 GDS_NEIGHBOURS_get_my_id (void)
5634 /* end of gnunet-service-xdht_neighbours.c */