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"
48 1. to randomly choose one of the routes in case there are multiple
49 routes to reach to the finger.
50 3. Structure alignment.
51 5. In put, we don't have anything like put result. so we are not adding anything
56 * Maximum possible fingers of a peer.
58 #define MAX_FINGERS 66
61 * Maximum allowed number of pending messages per friend peer.
63 #define MAXIMUM_PENDING_PER_FRIEND 64
66 * How long to wait before sending another find finger trail request
68 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
71 * How long at most to wait for transmission of a request to another peer?
73 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
75 GNUNET_NETWORK_STRUCT_BEGIN
83 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
85 struct GNUNET_MessageHeader header;
90 uint32_t options GNUNET_PACKED;
95 uint32_t block_type GNUNET_PACKED;
100 uint32_t hop_count GNUNET_PACKED;
103 * Replication level for this message
104 * In the current implementation, this value is not used.
106 uint32_t desired_replication_level GNUNET_PACKED;
109 * Length of the PUT path that follows (if tracked).
111 uint32_t put_path_length GNUNET_PACKED;
114 * Current destination to which this message is forwarded.
116 struct GNUNET_PeerIdentity current_destination;
119 * Peer whose finger is current_destination.
121 struct GNUNET_PeerIdentity current_source;
124 * When does the content expire?
126 struct GNUNET_TIME_AbsoluteNBO expiration_time;
129 * The key to store the value under.
131 struct GNUNET_HashCode key GNUNET_PACKED;
133 /* put path (if tracked) */
143 struct PeerGetResultMessage
146 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
148 struct GNUNET_MessageHeader header;
151 * The type for the data.
153 uint32_t type GNUNET_PACKED;
156 * Peer which will receive the get result message.
158 struct GNUNET_PeerIdentity source_peer;
161 * Number of peers recorded in the outgoing path from source to the
162 * stored location of this message.
164 uint32_t put_path_length GNUNET_PACKED;
167 * Length of the GET path that follows (if tracked).
169 uint32_t get_path_length GNUNET_PACKED;
172 * When does the content expire?
174 struct GNUNET_TIME_Absolute expiration_time;
177 * The key of the corresponding GET request.
179 struct GNUNET_HashCode key;
181 /* put path (if tracked) */
183 /* get path (if tracked) */
193 struct PeerGetMessage
196 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
198 struct GNUNET_MessageHeader header;
203 uint32_t options GNUNET_PACKED;
206 * Desired content type.
208 uint32_t block_type GNUNET_PACKED;
213 uint32_t hop_count GNUNET_PACKED;
216 * Desired replication level for this request.
217 * In the current implementation, this value is not used.
219 uint32_t desired_replication_level GNUNET_PACKED;
222 * Total number of peers in get path.
224 unsigned int get_path_length;
227 * Peer which is an intermediate destination.
229 struct GNUNET_PeerIdentity current_destination;
232 * Source for which current_destination is the finger.
234 struct GNUNET_PeerIdentity current_source;
237 * The key we are looking for.
239 struct GNUNET_HashCode key;
247 * P2P Trail setup message
249 struct PeerTrailSetupMessage
253 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
255 struct GNUNET_MessageHeader header;
258 * Successor of this finger value will be our finger peer.
260 uint64_t destination_finger;
263 * Source peer which wants to setup the trail to one of its finger.
265 struct GNUNET_PeerIdentity source_peer;
268 * Peer to which this packet is forwarded.
270 struct GNUNET_PeerIdentity current_destination;
273 * In case the packet is forwarded to an intermediate finger, then
274 * current_source contains the peer id whose finger is the intermediate
275 * finger. In case the packet is forwarded to a friend, then it is NULL.
276 * FIXME: check the usage of current_source and fix this comment.
278 struct GNUNET_PeerIdentity current_source;
281 * Index into finger peer map, in Network Byte Order.
283 uint32_t finger_map_index;
286 * Number of entries in trail list, in Network Byte Order.
288 uint32_t trail_length GNUNET_PACKED;
290 /* Trail formed in the process. */
295 * P2P Trail Setup Result message
297 struct PeerTrailSetupResultMessage
301 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
303 struct GNUNET_MessageHeader header;
306 * Finger to which we have found the path.
308 struct GNUNET_PeerIdentity finger_identity;
311 * Peer which was looking for the trail to finger.
313 struct GNUNET_PeerIdentity destination_peer;
316 * Index into finger peer map in NBO.
318 uint32_t finger_map_index;
321 * Number of entries in trail list in NBO.
323 uint32_t trail_length GNUNET_PACKED;
325 /* Trail from destination_peer to finger_identity */
331 * P2P Trail Rejection Message.
333 struct PeerTrailRejectionMessage
336 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
338 struct GNUNET_MessageHeader header;
341 * Source peer which wants to set up the trail.
343 struct GNUNET_PeerIdentity source_peer;
346 * Peer which sent trail rejection message.
348 struct GNUNET_PeerIdentity congested_peer;
351 * Peer identity which will be successor to this value will be finger of
354 uint64_t finger_identity_value;
357 * Index in finger peer map of source peer.
359 uint32_t finger_map_index;
362 * Total number of peers in the trail.
364 uint32_t trail_length;
366 /* Trail_list from source_peer to peer which sent the message for trail setup
367 * to congested peer.*/
372 * P2P Verify Successor message.
374 struct PeerVerifySuccessorMessage
378 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
380 struct GNUNET_MessageHeader header;
383 * Source peer which wants to verify its successor.
385 struct GNUNET_PeerIdentity source_peer;
388 * My current successor.
390 struct GNUNET_PeerIdentity successor;
393 * Total number of peers in trail to current successor.
395 uint32_t trail_length;
397 /* Trail to reach to from source_peer to successor. */
402 * P2P Verify Successor Result message.
404 struct PeerVerifySuccessorResultMessage
408 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
410 struct GNUNET_MessageHeader header;
413 * Destination peer which sent the request to verify its successor.
415 struct GNUNET_PeerIdentity destination_peer;
418 * Successor to which PeerVerifySuccessorMessage was sent.
420 struct GNUNET_PeerIdentity source_successor;
423 * source_successor's predecessor
425 struct GNUNET_PeerIdentity my_predecessor;
428 * Total number of peers in trail.
430 uint32_t trail_length;
432 /* Trail to reach from destination_peer to its correct successor.
433 * If source_successor is not destination peer, then trail is from destination_peer
435 * If source_successor is destination peer, then trail is from destination_peer
436 * to source_successor. */
441 * P2P Notify New Successor message.
443 struct PeerNotifyNewSuccessorMessage
446 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
448 struct GNUNET_MessageHeader header;
451 * Source peer which wants to notify its new successor.
453 struct GNUNET_PeerIdentity source_peer;
456 * New successor identity.
458 struct GNUNET_PeerIdentity destination_peer;
461 * Number of peers in trail from source_peer to new successor.
463 uint32_t trail_length;
465 /* Trail to from source_peer to destination_peer. */
468 struct PeerTrailTearDownMessage
471 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
473 struct GNUNET_MessageHeader header;
476 * Source peer of this trail.
478 struct GNUNET_PeerIdentity source_peer;
481 * Destination peer of this trail.
483 struct GNUNET_PeerIdentity destination_peer;
486 * Trail from source_peer to destination_peer compressed such that
487 * new_first_friend is the first hop in the trail from source to
490 struct GNUNET_PeerIdentity new_first_friend;
492 * Number of peers in trail from source_peer to new first friend.
494 uint32_t trail_length;
496 /* Trail to from source_peer to new first friend. */
499 GNUNET_NETWORK_STRUCT_END
503 * Linked list of messages to send to a particular other peer.
505 struct P2PPendingMessage
508 * Pointer to next item in the list
510 struct P2PPendingMessage *next;
513 * Pointer to previous item in the list
515 struct P2PPendingMessage *prev;
518 * Message importance level. FIXME: used? useful?
520 unsigned int importance;
523 * When does this message time out?
525 struct GNUNET_TIME_Absolute timeout;
528 * Actual message to be sent, allocated at the end of the struct:
529 * // msg = (cast) &pm[1];
530 * // memcpy (&pm[1], data, len);
532 const struct GNUNET_MessageHeader *msg;
538 * Linked List of peers which are part of trail to reach a particular Finger.
543 * Pointer to next item in the list
545 struct TrailPeerList *next;
548 * Pointer to previous item in the list
550 struct TrailPeerList *prev;
553 * An element in this trail list
555 struct GNUNET_PeerIdentity peer;
561 * Entry in friend_peermap.
568 struct GNUNET_PeerIdentity id;
571 * 1. used in select_random_friend(), in case the friend has trails_count > TRAILS_THROUGH_FRIEND,
572 * then choose another friend.
573 * 2. in case of find_successor(), if the number of trails going through the friend
574 * has already crossed, then choose another friend.
575 * 3. in case of find_successor(), if we choose a finger, and if friend through
576 * which we reach this finger has crossed the limit then choose another finger/friend.
577 * 4. One way to implement in case of find_successor, is 1) you can have a global
578 * array of the entries and only when an entry is added in finger table, friend table,
579 * then you re calculate the array. In array while adding the element you check
580 * the threshold of the friend in case its friend, and in case of finger check
581 * the threshold of the first friend in the trail. If crossed then don't add the
582 * entries in the array. When the count goes down, then again set a flag and
583 * recalculte the array. Store a field in Finger table also, which will be
584 * equal to number of trails going through the first friend.
585 * Number of trail of which this friend is the first hop.
586 * 5.FIXME: understand where you need to use memcpy or direct assignment.
588 unsigned int trails_count;
591 * Count of outstanding messages for this friend.
593 unsigned int pending_count;
596 * FIXME: Refer to time.c and gnunet_time_lib.h for correct functions.
597 * in handle_dht_p2p_trail_rejection, you should update these values
598 * and whenever you are selecting a friend in select_random_friend()
599 * and find_successor(), you should check congestion_duration = 0,
600 * then proceed else if congestion_duration < your current time then also
602 * struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
603 * struct GNUNET_TIME_Relative congestion_timeout =
604 * congestion_duration = GNUNET_TIME_absolute_add (start,congestion_timeout);
606 struct GNUNET_TIME_Absolute congestion_duration;
609 * Head of pending messages to be sent to this friend.
611 struct P2PPendingMessage *head;
614 * Tail of pending messages to be sent to this friend.
616 struct P2PPendingMessage *tail;
619 * Core handle for sending messages to this friend.
621 struct GNUNET_CORE_TransmitHandle *th;
627 * Entry in finger_peermap.
634 struct GNUNET_PeerIdentity finger_identity;
637 * Index in finger peer map
639 unsigned int finger_map_index;
642 * Number of trails to reach to this finger.
644 unsigned int trail_count;
647 * Total number of entries in first trail from (me,finger)
649 unsigned int first_trail_length;
652 * Total number of entries in second trail from (me,finger)
654 unsigned int second_trail_length;
658 * Number of trail of which the first element to reach to this finger is
661 unsigned int first_friend_trails_count;
664 * Head of first trail to reach this finger.
666 struct TrailPeerList *first_trail_head;
669 * Tail of first trail to reach this finger.
671 struct TrailPeerList *first_trail_tail;
674 * Head of second trail to reach this finger.
676 struct TrailPeerList *second_trail_head;
679 * Tail of second trail to reach this finger.
681 struct TrailPeerList *second_trail_tail;
687 * FIXME: The name is not correct.
688 * Used to specify the kind of value stored in the array all_known_peers.
690 enum current_destination_type
700 * Data structure passed to sorting algorithm in find_successor().
705 * 64 bit value of peer identity
710 * FIXME: think of a better name for both the struct and destination_type
711 * Type : MY_ID, FINGER, FINGER, Value
713 enum current_destination_type type;
716 * Pointer to original data structure linked to peer id.
723 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
724 * get our first friend.
726 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
729 * Identity of this peer.
731 static struct GNUNET_PeerIdentity my_identity;
734 * Hash map of all the friends of a peer
736 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
739 * Hash map of all the fingers of a peer
741 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
746 static struct GNUNET_CORE_Handle *core_api;
749 * Finger map index for predecessor entry in finger peermap.
751 #define PREDECESSOR_FINGER_ID 64
754 * Maximum number of trails allowed to go through a friend.
755 * FIXME: Better name, Random value at the moment, need to be adjusted to maintain a balance
756 * between performance and Sybil tolerance.
758 #define TRAIL_THROUGH_FRIEND_THRESHOLD 64
761 * Possible number of different trails to reach to a finger. (Redundant routing)
763 #define TRAIL_COUNT 2
766 * FIXME: better name.
767 * Set to GNUNET_YES, when the number of trails going through all my friends
768 * have reached the TRAIL_THROUGH_FRIEND_THRESHOLD.
770 static unsigned int all_friends_trail_threshold;
773 * The current finger index that we have want to find trail to.
775 static unsigned int current_search_finger_index;
779 * Iterate over trail and search your index location in the array.
780 * @param trail Trail which contains list of peers.
781 * @param trail_length Number of peers in the trail.
782 * @return Index in the array.
783 * #GNUNET_SYSERR, in case there is no entry which should not be the case ideally.
786 search_my_index (const struct GNUNET_PeerIdentity *trail,
791 while (i < trail_length)
793 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
799 return GNUNET_SYSERR;
803 * Compare two peer identities.
804 * @param p1 Peer identity
805 * @param p2 Peer identity
806 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
809 compare_peer_id (const void *p1, const void *p2)
811 struct Sorting_List *p11;
812 struct Sorting_List *p22;
814 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
815 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
816 p11 = (struct Sorting_List *)p1;
817 p22 = (struct Sorting_List *)p2;
818 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
819 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
825 * Return the predecessor of value in all_known_peers.
826 * @param all_known_peers list of all the peers
827 * @param value value we have to search in the all_known_peers.
828 * @param size Total numbers of elements
829 * @return Predecessor
831 static struct Sorting_List *
832 find_closest_predecessor(struct Sorting_List *all_known_peers, uint64_t value,
841 middle = (first + last)/2;
845 if(all_known_peers[middle].peer_id < value)
849 else if(all_known_peers[middle].peer_id == value)
853 return &all_known_peers[size - 1];
857 return &all_known_peers[middle - 1];
865 middle = (first + last)/2;
872 * Return the successor of value in all_known_peers.
873 * @param all_known_peers list of all the peers
874 * @param value value we have to search in the all_known_peers.
875 * @param size Total numbers of elements
878 static struct Sorting_List *
879 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
888 middle = (first + last)/2;
892 if(all_known_peers[middle].peer_id < value)
896 else if(all_known_peers[middle].peer_id == value)
898 if(middle == (size -1))
900 return &all_known_peers[0];
904 return &all_known_peers[middle+1];
912 middle = (first + last)/2;
919 * Called when core is ready to send a message we asked for
920 * out to the destination.
922 * @param cls the 'struct FriendInfo' of the target friend
923 * @param size number of bytes available in buf
924 * @param buf where the callee should write the message
925 * @return number of bytes written to buf
928 core_transmit_notify (void *cls, size_t size, void *buf)
930 struct FriendInfo *peer = cls;
932 struct P2PPendingMessage *pending;
937 while ((NULL != (pending = peer->head)) &&
938 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
940 peer->pending_count--;
941 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
942 GNUNET_free (pending);
946 /* no messages pending */
952 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
953 GNUNET_CORE_PRIO_BEST_EFFORT,
954 GNUNET_TIME_absolute_get_remaining
955 (pending->timeout), &peer->id,
956 ntohs (pending->msg->size),
957 &core_transmit_notify, peer);
958 GNUNET_break (NULL != peer->th);
962 while ((NULL != (pending = peer->head)) &&
963 (size - off >= (msize = ntohs (pending->msg->size))))
965 GNUNET_STATISTICS_update (GDS_stats,
967 ("# Bytes transmitted to other peers"), msize,
969 memcpy (&cbuf[off], pending->msg, msize);
971 peer->pending_count--;
972 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
973 GNUNET_free (pending);
975 if (peer->head != NULL)
978 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
979 GNUNET_CORE_PRIO_BEST_EFFORT,
980 GNUNET_TIME_absolute_get_remaining
981 (pending->timeout), &peer->id, msize,
982 &core_transmit_notify, peer);
983 GNUNET_break (NULL != peer->th);
991 * Transmit all messages in the friend's message queue.
993 * @param peer message queue to process
996 process_friend_queue (struct FriendInfo *peer)
998 struct P2PPendingMessage *pending;
1000 if (NULL == (pending = peer->head))
1002 if (NULL != peer->th)
1005 GNUNET_STATISTICS_update (GDS_stats,
1007 ("# Bytes of bandwidth requested from core"),
1008 ntohs (pending->msg->size), GNUNET_NO);
1010 /* FIXME: Are we correctly initializing importance and pending. */
1012 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1013 pending->importance,
1014 GNUNET_TIME_absolute_get_remaining
1015 (pending->timeout), &peer->id,
1016 ntohs (pending->msg->size),
1017 &core_transmit_notify, peer);
1018 GNUNET_break (NULL != peer->th);
1023 * Construct a trail message and forward it to a friend.
1024 * @param source_peer Peer which wants to set up the trail to one of its finger.
1025 * @param destination_finger Peer identity closest to this value will be
1026 * @a source_peer's finger.
1027 * @param current_destination Finger of the @a current_source, for which among
1028 * its friends, its own identity and all fingers, this
1029 * finger is the closest to the @a destination_finger
1030 * @param current_source Peer for which @a current_destination is its finger.
1031 * @param target_friend Friend to which this message should be forwarded.
1032 * @param trail_length Numbers of peers in the trail found so far.
1033 * @param trail_peer_list Peers this request has traversed so far
1034 * @param finger_map_index Index in finger peer map
1037 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
1038 uint64_t destination_finger,
1039 struct GNUNET_PeerIdentity *current_destination,
1040 struct GNUNET_PeerIdentity *current_source,
1041 struct FriendInfo *target_friend,
1042 unsigned int trail_length,
1043 const struct GNUNET_PeerIdentity *trail_peer_list,
1044 unsigned int finger_map_index)
1046 struct P2PPendingMessage *pending;
1047 struct PeerTrailSetupMessage *tsm;
1048 struct GNUNET_PeerIdentity *peer_list;
1051 msize = sizeof (struct PeerTrailSetupMessage) +
1052 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1054 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1060 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1062 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1066 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1067 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1068 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1069 pending->msg = &tsm->header;
1070 tsm->header.size = htons (msize);
1071 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
1072 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
1073 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1074 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
1075 memcpy (&(tsm->current_source), current_source, sizeof (struct GNUNET_PeerIdentity));
1076 tsm->trail_length = htonl (trail_length);
1077 tsm->finger_map_index = htonl (finger_map_index);
1079 if (trail_length > 0)
1081 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1082 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1085 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1086 target_friend->pending_count++;
1087 process_friend_queue (target_friend);
1093 * Construct a trail setup result message and forward it to a friend.
1094 * @param destination_peer Peer which will get the trail to one of its finger.
1095 * @param source_finger Peer to which the trail has been setup to.
1096 * @param target_friend Friend to which this message should be forwarded.
1097 * @param trail_length Numbers of peers in the trail.
1098 * @param trail_peer_list Peers which are part of the trail from source to destination.
1099 * @param finger_map_index Index in finger peer map
1102 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destination_peer,
1103 const struct GNUNET_PeerIdentity *source_finger,
1104 struct FriendInfo *target_friend,
1105 unsigned int trail_length,
1106 const struct GNUNET_PeerIdentity *trail_peer_list,
1107 unsigned int finger_map_index)
1109 struct P2PPendingMessage *pending;
1110 struct PeerTrailSetupResultMessage *tsrm;
1111 struct GNUNET_PeerIdentity *peer_list;
1114 msize = sizeof (struct PeerTrailSetupResultMessage) +
1115 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1117 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1123 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1125 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1129 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1130 pending->importance = 0;
1131 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1132 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1133 pending->msg = &tsrm->header;
1134 tsrm->header.size = htons (msize);
1135 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
1136 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1137 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
1138 tsrm->trail_length = htonl (trail_length);
1139 tsrm->finger_map_index = htonl (finger_map_index);
1141 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1142 if (trail_length > 0)
1144 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1146 /* Send the message to chosen friend. */
1147 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1148 target_friend->pending_count++;
1149 process_friend_queue (target_friend);
1154 * Construct a PeerVerifySuccessor message and send it to friend.
1155 * @param source_peer Peer which wants to verify its successor
1156 * @param successor Peer which is our current successor
1157 * @param target_friend Friend to which this message should be forwarded.
1158 * @param trail_peer_list Peer which are part of trail from source to destination
1159 * @param trail_length Number of peers in the trail list.
1161 void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *source_peer,
1162 const struct GNUNET_PeerIdentity *successor,
1163 struct FriendInfo *target_friend,
1164 const struct GNUNET_PeerIdentity *trail_peer_list,
1165 unsigned int trail_length)
1167 struct PeerVerifySuccessorMessage *vsm;
1168 struct P2PPendingMessage *pending;
1169 struct GNUNET_PeerIdentity *peer_list;
1172 msize = sizeof (struct PeerVerifySuccessorMessage) +
1173 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1175 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1181 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1183 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1187 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1188 pending->importance = 0; /* FIXME */
1189 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1190 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1191 pending->msg = &vsm->header;
1192 vsm->header.size = htons (msize);
1193 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1194 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
1195 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1196 vsm->trail_length = htonl (trail_length);
1198 if (trail_length > 0)
1200 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1201 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1204 /* Send the message to chosen friend. */
1205 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1206 target_friend->pending_count++;
1207 process_friend_queue (target_friend);
1213 * Construct a PeerVerifySuccessorResult message and send it to friend.
1214 * @param destination_peer Peer which sent verify successor message
1215 * @param source_successor Peer to which verify successor message was sent.
1216 * @param my_predecessor source_successor's predecessor.
1217 * @param target_friend Friend to which this message should be forwarded.
1218 * @param trail_peer_list Peers which are part of trail from source to destination
1219 * @param trail_length Number of peers in the trail list.
1221 void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *destination_peer,
1222 const struct GNUNET_PeerIdentity *source_successor,
1223 const struct GNUNET_PeerIdentity *my_predecessor,
1224 struct FriendInfo *target_friend,
1225 const struct GNUNET_PeerIdentity *trail_peer_list,
1226 unsigned int trail_length)
1228 struct PeerVerifySuccessorResultMessage *vsmr;
1229 struct P2PPendingMessage *pending;
1230 struct GNUNET_PeerIdentity *peer_list;
1233 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1234 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1236 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1243 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1245 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1249 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1250 pending->importance = 0; /* FIXME */
1251 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1252 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1253 pending->msg = &vsmr->header;
1254 vsmr->header.size = htons (msize);
1255 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1256 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1257 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1258 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1259 vsmr->trail_length = htonl (trail_length);
1260 if (trail_length > 0)
1262 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1263 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1266 /* Send the message to chosen friend. */
1267 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1268 target_friend->pending_count++;
1269 process_friend_queue (target_friend);
1274 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1275 * @param source_peer Peer which is sending notify message to its new successor.
1276 * @param destination_peer Peer which is the new destination.
1277 * @param target_friend Next friend to pass this message to.
1278 * @param peer_list List of peers in the trail to reach to destination_peer.
1279 * @param trail_length Total number of peers in peer list
1282 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1283 const struct GNUNET_PeerIdentity *destination_peer,
1284 struct FriendInfo *target_friend,
1285 const struct GNUNET_PeerIdentity *trail_peer_list,
1286 unsigned int trail_length)
1288 struct PeerNotifyNewSuccessorMessage *nsm;
1289 struct P2PPendingMessage *pending;
1290 struct GNUNET_PeerIdentity *peer_list;
1293 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1294 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1296 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1302 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1304 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1308 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1309 pending->importance = 0; /* FIXME */
1310 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1311 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1312 pending->msg = &nsm->header;
1313 nsm->header.size = htons (msize);
1314 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1315 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1316 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1317 nsm->trail_length = htonl (trail_length);
1318 /* FIXME: Here I am not checking the trail length, as I am assuming that for new
1319 successor our old successor is a part of trail, so trail length > 1. */
1320 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1321 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1323 /* Send the message to chosen friend. */
1324 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1325 target_friend->pending_count++;
1326 process_friend_queue (target_friend);
1330 * Send a trail tear down message
1331 * @param source_peer Source of the trail.
1332 * @param destination_peer Destination of the trail.
1333 * @param discarded_trail Discarded trail from source to destination.
1334 * @param discarded_trail_length Total number of peers in trail_list.
1335 * @pararm target_peer Next peer to forward this message to.
1336 * @param new_first_friend The new first hop in the new trail from source to destination
1340 GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_PeerIdentity *source_peer,
1341 const struct GNUNET_PeerIdentity *destination_peer,
1342 const struct GNUNET_PeerIdentity *discarded_trail,
1343 unsigned int discarded_trail_length,
1344 struct FriendInfo *target_friend,
1345 const struct GNUNET_PeerIdentity *new_first_friend)
1347 struct P2PPendingMessage *pending;
1348 struct PeerTrailTearDownMessage *ttdm;
1349 struct GNUNET_PeerIdentity *peer_list;
1352 msize = sizeof (struct PeerTrailTearDownMessage) +
1353 (discarded_trail_length * sizeof(struct GNUNET_PeerIdentity));
1355 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1361 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1363 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1367 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1368 pending->importance = 0; /* FIXME */
1369 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1370 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1371 pending->msg = &ttdm->header;
1372 ttdm->header.size = htons (msize);
1373 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1374 memcpy (&(ttdm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1375 memcpy (&(ttdm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1376 memcpy (&(ttdm->new_first_friend),new_first_friend, sizeof (struct GNUNET_PeerIdentity));
1377 ttdm->trail_length = htonl (discarded_trail_length);
1379 peer_list = (struct GNUNET_PeerIdentity *) &ttdm[1];
1380 memcpy (peer_list, discarded_trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1382 /* Send the message to chosen friend. */
1383 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1384 target_friend->pending_count++;
1385 process_friend_queue (target_friend);
1390 * FIMXE: Change the return value, to handle the case where all friends
1392 * FIXME: Handle congested peer - don't choose this friend, also don't choose
1393 * the friend if the link threshold has crossed. Not implemented yet.
1394 * Randomly choose one of your friends from the friends_peer map
1397 static struct FriendInfo *
1398 select_random_friend ()
1400 unsigned int current_size;
1401 unsigned int *index;
1403 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1404 struct GNUNET_PeerIdentity key_ret;
1405 struct FriendInfo *friend;
1407 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1408 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1409 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1413 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1421 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1423 /* Possible number of trails that can go through this friend has been reached. */
1424 if (friend->trails_count > TRAIL_THROUGH_FRIEND_THRESHOLD)
1426 /* FIXME: What should I do now, should I call this same function again and
1427 remember the index, j so that call random function without j and find
1428 a new friend. Also, I need some way to make sure that if number of times
1429 I have called the function is equal to number of entries in friend peermap.
1430 then I should return NULL. but its much better to have a function which
1431 just eliminates looking at the entries with threshold crossed. URGENT: Whats
1432 the best way to handle this case? */
1442 * Compute finger_identity to which we want to setup the trail
1443 * @return finger_identity
1446 compute_finger_identity()
1450 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1451 my_id64 = GNUNET_ntohll (my_id64);
1452 return (my_id64 + (unsigned long) pow (2, current_search_finger_index));
1457 * Compute immediate predecessor identity in the network.
1458 * @return peer identity of immediate predecessor.
1461 compute_predecessor_identity()
1465 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1466 my_id64 = GNUNET_ntohll (my_id64);
1467 return (my_id64 -1);
1472 * Ping your successor to verify if it is still your successor or not.
1475 send_verify_successor_message()
1477 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1478 struct GNUNET_PeerIdentity key_ret;
1479 struct FriendInfo *target_friend;
1480 struct GNUNET_PeerIdentity next_hop;
1481 struct GNUNET_PeerIdentity *peer_list;
1482 struct FingerInfo *finger;
1483 unsigned int finger_index;
1486 /* Find the successor from the finger peermap.*/
1487 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1488 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1490 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1491 (const void **)&finger))
1493 if (0 == finger->finger_map_index)
1500 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1502 /* Either you don't have a successor or you are your own successor, then don't
1503 send a successor message. */
1505 (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &(finger->finger_identity))))
1510 if (finger->first_trail_length > 0)
1512 struct TrailPeerList *iterate;
1514 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->first_trail_length);
1515 iterate = finger->first_trail_head;
1517 while ( i < (finger->first_trail_length))
1520 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1521 iterate = iterate->next;
1524 memcpy (&next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1525 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
1529 /* If trail length = 0, then our successor is our friend. */
1531 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1532 &(finger->finger_identity));
1535 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1536 &(finger->finger_identity),
1539 finger->first_trail_length);
1545 * 1. Need to handle the case where all friends are either congested or
1546 * have reached their threshold.
1547 * 2. If we need all_friends_trail_threshold
1548 * 3. do we need to check if friend peermap is empty or not.
1549 * Choose a random friend and start looking for the trail to reach to
1550 * finger identity through this random friend.
1552 * @param cls closure for this task
1553 * @param tc the context under which the task is running
1556 send_find_finger_trail_message (void *cls,
1557 const struct GNUNET_SCHEDULER_TaskContext *tc)
1559 struct FriendInfo *target_friend;
1560 struct GNUNET_TIME_Relative next_send_time;
1561 uint64_t finger_identity;
1562 unsigned int finger_map_index;
1564 next_send_time.rel_value_us =
1565 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1566 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1567 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1568 find_finger_trail_task =
1569 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1572 if (GNUNET_YES == all_friends_trail_threshold)
1574 /* All friends in friend peer map, have reached their trail threshold. No
1575 more new trail can be created. */
1579 target_friend = select_random_friend ();
1580 if (NULL == target_friend)
1582 all_friends_trail_threshold = GNUNET_YES;
1586 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
1588 finger_identity = compute_predecessor_identity();
1592 finger_identity = compute_finger_identity();
1595 finger_map_index = current_search_finger_index;
1596 GDS_NEIGHBOURS_send_trail_setup (&my_identity, finger_identity, &(target_friend->id),
1597 &my_identity, target_friend, 0, NULL, finger_map_index);
1602 * FIXME: You need to handle the case of predecessor in case you don't get
1603 * the call from finger table add then you should not send a trail teardown message
1604 * because no one has added that in their trail.
1605 * Scan the trail to check if any of my own friend is part of trail. If yes
1606 * then shortcut the trail, send a trail teardown for the discarded trail,
1607 * update trail list and trail_length.
1608 * @param trail[Out] Current trail to reach to @a finger, will be updated
1609 * in case we compress the trail.
1610 * @param trail_length[Out] Number of peers in @a finger_trail, will be updated
1611 * in case we compress the trail.
1612 * @param finger Finger identity
1615 scan_and_compress_trail (struct GNUNET_PeerIdentity *trail,
1616 unsigned int *trail_length,
1617 const struct GNUNET_PeerIdentity *finger)
1620 struct FriendInfo *target_friend;
1622 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger))
1628 if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger))
1630 int discarded_trail_length = *trail_length;
1631 target_friend = GNUNET_CONTAINER_multipeermap_get(friend_peermap, &trail[0]);
1632 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, trail,
1633 discarded_trail_length, target_friend, finger);
1639 i = *trail_length - 1;
1642 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
1644 /* This element of trail is not my friend. */
1649 /* A --> B(friend 1) --> C(friend 2)--> D ---> E, then we can rewrite the trail as
1651 * Now, we should remove the entry from A's routing table, B's routing table
1652 * and update the entry in C's routing table. Rest everything will be same.
1653 * C's routing table should have source peer as the prev.hop.
1655 struct GNUNET_PeerIdentity *discarded_trail;
1656 struct FriendInfo *target_friend;
1657 int discarded_trail_length;
1660 discarded_trail_length = i - 1;
1661 discarded_trail = GNUNET_malloc (discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1662 memcpy (discarded_trail, trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1663 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
1664 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, discarded_trail,
1665 discarded_trail_length, target_friend,
1668 /* Copy the trail from index i to index trail_length -1 and change
1669 trail length and return */
1670 while (i < *trail_length)
1672 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
1676 *trail_length = j+1;
1685 * FIXME: Is this correct? Here I am using dll_remove and its documentation
1686 * reads something else. Verify. Urgent.
1687 * Free finger and its trail.
1688 * @param finger Finger to be freed.
1691 free_finger (struct FingerInfo *finger)
1693 struct TrailPeerList *peer;
1695 if(finger->first_trail_head != NULL)
1697 while (NULL != (peer = finger->first_trail_head))
1699 GNUNET_CONTAINER_DLL_remove (finger->first_trail_head, finger->first_trail_tail, peer);
1704 if (finger->second_trail_head != NULL)
1706 while (NULL != (peer = finger->second_trail_head))
1708 GNUNET_CONTAINER_DLL_remove (finger->second_trail_head, finger->second_trail_tail, peer);
1711 GNUNET_free (finger);
1717 * FIXME: First check if both the trails are present if yes then send it
1718 * for both of them. Currently sending it only for one trail.
1719 * Send a trail teardown message for the trail of removed finger from the finger
1721 * @param existing_finger Finger to removed from the finger peermap.
1724 void send_trail_teardown (struct FingerInfo *removed_finger)
1726 struct GNUNET_PeerIdentity *peer_list;
1727 struct FriendInfo *friend;
1728 struct TrailPeerList *finger_trail;
1729 int removed_finger_trail_length = removed_finger->first_trail_length;
1732 if (removed_finger->first_trail_length == 0)
1734 finger_trail = removed_finger->first_trail_head;
1735 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(finger_trail->peer));
1736 peer_list = GNUNET_malloc ( removed_finger_trail_length * sizeof (struct GNUNET_PeerIdentity));
1737 while (i < removed_finger->first_trail_length)
1739 memcpy (&peer_list[i], &(finger_trail->peer), sizeof (struct GNUNET_PeerIdentity));
1740 finger_trail = finger_trail->next;
1744 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, &(removed_finger->finger_identity),
1745 peer_list, removed_finger_trail_length, friend,
1746 &(removed_finger->finger_identity));
1751 * FIXME: How do we understand which is the correct trail head?
1752 * Add a new trail to reach an existing finger in finger peermap and increment
1753 * the count of number of trails to reach to this finger.
1754 * @param existing_finger Finger
1755 * @param trail New trail to be added
1756 * @param trail_length Total number of peers in the trail.
1759 void add_new_trail (struct FingerInfo *existing_finger,
1760 struct GNUNET_PeerIdentity *trail,
1761 unsigned int trail_length)
1765 /* FIXME: Here you need to understand which trail is there and which not.
1766 In case first_trail_head != NULL, then that trail is present
1767 so you should add the second one. Need to verify this logic. */
1768 if (existing_finger->first_trail_head != NULL)
1770 while (i < trail_length)
1772 struct TrailPeerList *element;
1773 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1774 element->next = NULL;
1775 element->prev = NULL;
1777 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1778 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1782 else if (existing_finger->second_trail_head != NULL)
1784 while (i < trail_length)
1786 struct TrailPeerList *element;
1787 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1788 element->next = NULL;
1789 element->prev = NULL;
1791 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1792 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->first_trail_head, existing_finger->first_trail_tail, element);
1796 existing_finger->trail_count++;
1801 * In case there are already maximum number of possible trail to reach to a finger,
1802 * then check if the new trail's length is lesser than any of the existing trails.
1803 * If yes then replace that old trail by new trail.
1804 * Note: Here we are taking length as a parameter to choose the best possible trail,
1805 * but there could be other parameters also like - 1. duration of existence of a
1806 * trail - older the better. 2. if the new trail is completely disjoint than the
1807 * other trails, then may be choosing it is better.
1808 * @param existing_finger
1810 * @param trail_length
1811 * @return #GNUNET_YES
1815 void select_and_replace_trail (struct FingerInfo *existing_finger,
1816 struct GNUNET_PeerIdentity *new_trail,
1817 unsigned int new_trail_length)
1819 if (existing_finger->first_trail_length == existing_finger->second_trail_length)
1821 if (new_trail_length < existing_finger->first_trail_length)
1823 /* Randomly choose one of the trail. FIXME:currently I am just replacing the
1825 struct TrailPeerList *peer;
1828 while (NULL != (peer = existing_finger->first_trail_head))
1830 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1834 while (i < new_trail_length)
1836 struct TrailPeerList *element;
1837 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1838 element->next = NULL;
1839 element->prev = NULL;
1841 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1842 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1847 else if ((new_trail_length < existing_finger->second_trail_length) &&
1848 (existing_finger->second_trail_length < existing_finger->first_trail_length))
1850 /* Replace the first trail by the new trail. */
1851 struct TrailPeerList *peer;
1854 while (NULL != (peer = existing_finger->first_trail_head))
1856 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1860 while (i < new_trail_length)
1862 struct TrailPeerList *element;
1863 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1864 element->next = NULL;
1865 element->prev = NULL;
1867 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1868 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1872 else if ( (new_trail_length < existing_finger->first_trail_length) &&
1873 (existing_finger->first_trail_length < existing_finger->second_trail_length))
1875 /* Replace the second trail by the new trail. */
1876 struct TrailPeerList *peer;
1879 while (NULL != (peer = existing_finger->second_trail_head))
1881 GNUNET_CONTAINER_DLL_remove (existing_finger->second_trail_head, existing_finger->second_trail_tail, peer);
1885 while (i < new_trail_length)
1887 struct TrailPeerList *element;
1888 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1889 element->next = NULL;
1890 element->prev = NULL;
1892 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1893 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1901 * FIXME: If we remove a finger which is our friend, then how should we handle it.
1902 * Ideally only in case if the trail_length > 0,we increment the trail count
1903 * of the first friend in the trail to reach to the finger. in case finger is
1904 * our friend then trail length = 0, and hence, we have never incremented the
1905 * trail count associated with that friend.
1906 * Decrement the trail count for the first friend to reach to the finger.
1910 decrement_friend_trail_count (struct FingerInfo *finger)
1912 struct FriendInfo *first_trail_friend;
1913 struct FriendInfo *second_trail_friend;
1915 if(finger->first_trail_head != NULL)
1917 first_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1918 &(finger->first_trail_head->peer));
1919 first_trail_friend->trails_count--;
1922 if(finger->second_trail_head != NULL)
1924 second_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1925 &(finger->second_trail_head->peer));
1926 second_trail_friend->trails_count--;
1930 /* We will not need this variable any more, all_friends_trail_threshold,
1931 FIXME: REMOVE IT. */
1932 if (GNUNET_YES == all_friends_trail_threshold)
1934 all_friends_trail_threshold = GNUNET_NO;
1935 /* FIXME; Here you should reschedule the send_find_finger_task here. or
1943 * Select the closest finger. Used for both predecessor and other fingers..
1944 * But internally calls different functions for predecessor and other fingers.
1945 * @param existing_finger Finger in finger peermap.
1946 * @param new_finger New finger identity
1947 * @param finger_map_index Index in finger peermap where @a existing_finger is stored.
1948 * @return #GNUNET_YES if the new finger is closest.
1949 * #GNUNET_NO if the old finger is closest.
1950 * #GNUNET_SYSERR in case our own identity is closest (should never happen).
1953 int select_finger (struct FingerInfo *existing_finger,
1954 const struct GNUNET_PeerIdentity *new_finger,
1955 unsigned int finger_map_index)
1957 struct Sorting_List peers[3]; /* 3 for existing_finger, new_finger, my_identity */
1958 struct Sorting_List *closest_finger;
1962 for (k = 0; k < 3; k++)
1965 /* Add your entry to peers. */
1966 memcpy (&peers[0], &my_identity, sizeof (uint64_t));
1967 peers[0].type = MY_ID;
1968 peers[0].data = NULL;
1970 /* Add existing_finger identity to the peers. */
1971 memcpy (&peers[1], &(existing_finger->finger_identity), sizeof (uint64_t));
1972 peers[1].type = FINGER;
1973 peers[1].data = existing_finger;
1975 /* Add new_finger identity to the peers. s*/
1976 memcpy (&peers[2], &new_finger, sizeof (uint64_t));
1977 peers[2].type = VALUE;
1978 peers[2].data = NULL;
1980 memcpy (&value, &my_identity, sizeof (uint64_t));
1982 qsort (&peers, 3, sizeof (struct Sorting_List), &compare_peer_id);
1984 if (PREDECESSOR_FINGER_ID == finger_map_index)
1985 closest_finger = find_closest_predecessor (peers, value, 3);
1987 closest_finger = find_closest_successor (peers, value, 3);
1989 if (closest_finger->type == FINGER)
1993 else if (closest_finger->type == VALUE)
1997 else if (closest_finger->type == MY_ID);
1999 return GNUNET_SYSERR;
2005 * FIXME: Do we need to reinsert the existing finger into finger peermap
2006 * in case we add a new trail?
2007 * Choose the closest finger between existing finger and new finger.
2008 * If the new finger is closest and finger_map_index != PREDECESSOR_FINGER_ID,
2009 * then send a trail_teardown message along existing_finger's trail.
2010 * In case both the id's are same, and there is a place to keep more trails, then
2011 * store both of them. In case there is no space to store any more trail, then
2012 * choose the best trail (best - depends on length in current_implementation) and
2013 * discard the others.
2014 * @param existing_finger Existing entry in finger peer map
2015 * @param new_finger New finger
2016 * @param trail Trail to reach to the new finger from me.
2017 * @param trail_length Number of peers in the @a trail
2018 * @param finger_map_index If finger_map_index == PREDECESSOR_FINGER_INDEX,
2019 * then we use a different logic to find the closest
2021 * @return #GNUNET_YES In case we want to store the new entry.
2022 * #GNUNET_NO In case we want the existing entry.
2023 * #GNUNET_SYSERR Error.
2026 int select_closest_finger (struct FingerInfo *existing_finger,
2027 const struct GNUNET_PeerIdentity *new_finger,
2028 struct GNUNET_PeerIdentity *trail,
2029 unsigned int trail_length,
2030 unsigned int finger_map_index)
2032 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), new_finger))
2034 /* Both the new entry and existing entry are same. */
2035 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), &my_identity))
2037 /* If existing_finger is my_identity then trail_length = 0, trail = NULL. In
2038 this case you don't need to check the trails. Exit. */
2041 if (trail_length > 0)
2043 scan_and_compress_trail (trail, &trail_length, new_finger);
2045 if (existing_finger->trail_count < TRAIL_COUNT)
2047 add_new_trail (existing_finger, trail, trail_length);
2052 select_and_replace_trail (existing_finger, trail, trail_length);
2056 else if (GNUNET_YES == select_finger (existing_finger, new_finger, finger_map_index))
2058 /* new_finger is the correct finger. */
2059 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, new_finger))
2061 /* FIXME: Here in case the new finger is my_identity and old entry is not,
2062 should we keep the old entry even if the old entry is not the closest? */
2066 /* Clear all things associated with existing_finger (only if its not a
2068 if (PREDECESSOR_FINGER_ID != finger_map_index)
2069 send_trail_teardown (existing_finger);
2070 decrement_friend_trail_count (existing_finger);
2071 free_finger (existing_finger);
2073 if (trail_length > 0)
2075 scan_and_compress_trail (trail, &trail_length, new_finger);
2079 else if (GNUNET_NO == select_finger (existing_finger, new_finger,finger_map_index))
2081 /* existing_finger is the correct finger. */
2084 return GNUNET_SYSERR;
2089 * Check if there is a predecessor in our finger peer map or not.
2090 * If no, then return GNUNET_YES
2091 * else compare existing predecessor and peer, and find the correct
2093 * @param existing_predecessor
2094 * @param new_predecessor
2095 * @return #GNUNET_YES if new peer is predecessor
2096 * #GNUNET_NO if new peer is not the predecessor.
2099 compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer,
2100 struct GNUNET_PeerIdentity *trail,
2101 unsigned int trail_length)
2103 /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
2104 struct FingerInfo *existing_finger;
2105 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2106 struct FingerInfo *new_finger_entry;
2107 struct FriendInfo *first_friend_trail;
2109 int old_entry_found = GNUNET_NO;
2111 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2112 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2114 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2115 (const void **)&existing_finger))
2117 if (PREDECESSOR_FINGER_ID == existing_finger->finger_map_index)
2119 old_entry_found = GNUNET_YES;
2120 if( GNUNET_NO == select_closest_finger (existing_finger, peer, trail,
2121 trail_length,PREDECESSOR_FINGER_ID))
2128 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2129 if(GNUNET_NO == old_entry_found)
2135 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2136 memcpy (&(new_finger_entry->finger_identity), peer, sizeof (struct GNUNET_PeerIdentity));
2137 new_finger_entry->finger_map_index = PREDECESSOR_FINGER_ID;
2138 new_finger_entry->first_trail_length = trail_length;
2139 new_finger_entry->trail_count = 1;
2141 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity,peer)) /* finger_trail is NULL in case I am my own finger identity. */
2143 /* FIXME: Currently we are not handling the second trail. In that case, finger
2144 trail count = min (first_friend, second_friend) trail count. */
2145 /* Incrementing the friend trails count. */
2146 if (trail_length > 0)
2148 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
2149 first_friend_trail->trails_count++;
2153 /* It means the finger is my friend. */
2154 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2155 first_friend_trail->trails_count++;
2157 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2159 /* Invert the trail and then add. */
2160 if (trail_length != 0)
2162 i = trail_length - 1;
2165 struct TrailPeerList *element;
2166 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2167 element->next = NULL;
2168 element->prev = NULL;
2170 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
2171 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2174 struct TrailPeerList *element;
2175 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2176 element->next = NULL;
2177 element->prev = NULL;
2178 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
2179 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2182 GNUNET_assert (GNUNET_OK ==
2183 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2184 &(new_finger_entry->finger_identity),
2186 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
2193 * FIXME: Better name, and make the code more cleaner.
2194 * Compare the new finger entry added and our successor.
2195 * @return #GNUNET_YES if same.
2196 * #GNUNET_NO if not.
2199 compare_new_entry_and_successor (const struct GNUNET_PeerIdentity *new_finger,
2200 int finger_map_index)
2202 int successor_flag = 0;
2203 struct FingerInfo *successor_finger;
2204 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2207 if (PREDECESSOR_FINGER_ID == finger_map_index)
2210 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2211 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2213 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2214 (const void **)&successor_finger))
2216 if (successor_finger->finger_map_index == 0)
2223 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2225 /* Ideally we should never reach here. */
2226 if (successor_flag == 0)
2232 if (0 == GNUNET_CRYPTO_cmp_peer_identity (new_finger, &(successor_finger->finger_identity)))
2240 * Add a new entry in finger table.
2241 * @param finger_identity PeerIdentity of the new finger
2242 * @param finger_trail Trail to reach to the finger, can be NULL in case I am my own
2244 * @param finger_trail_length Number of peers in the trail, can be 0 in case finger
2245 * is a friend or I am my own finger.
2246 * @param finger_map_index Index in finger map.
2249 add_new_entry (const struct GNUNET_PeerIdentity *finger_identity,
2250 struct GNUNET_PeerIdentity *finger_trail,
2251 uint32_t finger_trail_length,
2252 uint32_t finger_map_index)
2254 struct FriendInfo *first_friend_trail;
2255 struct FingerInfo *new_finger_entry;
2258 /* Add a new entry. */
2259 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2260 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
2261 new_finger_entry->finger_map_index = finger_map_index;
2262 new_finger_entry->first_trail_length = finger_trail_length;
2263 new_finger_entry->trail_count = 1;
2265 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity)) /* finger_trail is NULL in case I am my own finger identity. */
2267 /* Incrementing the friend trails count. */
2268 if (finger_trail_length > 0)
2270 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_trail[0]);
2271 first_friend_trail->trails_count++;
2275 /* It means the finger is my friend. */
2276 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger_identity);
2277 first_friend_trail->trails_count++;
2279 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2281 /* Copy the trail. */
2283 while (i < finger_trail_length)
2285 struct TrailPeerList *element;
2286 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2287 element->next = NULL;
2288 element->prev = NULL;
2290 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
2291 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2296 return GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2297 &(new_finger_entry->finger_identity),
2299 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
2303 /**1. Should we check if there is already an entry for same finger id in the finger
2304 * peermap as we are checking for index. I think its too much of code and the use
2305 * of having unique identifier in finger map is only in case of find_successor
2306 * but anyways we will find the correct successor.
2307 * 2. you don't handle the second trail here as in new entry you will have only
2308 * one trail to reach to the finger.
2309 * Add an entry in the finger table. If there is already an existing entry in
2310 * the finger peermap for given finger map index, then choose the closest one.
2311 * In case both the new entry and old entry are same, store both of them. (Redundant
2313 * @param finger_identity
2314 * @param finger_trail
2315 * @param finger_trail_length
2316 * @param finger_map_index
2317 * @return #GNUNET_YES if the new entry is added.
2318 * #GNUNET_NO if the new entry is discarded.
2321 int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
2322 struct GNUNET_PeerIdentity *finger_trail,
2323 uint32_t finger_trail_length,
2324 uint32_t finger_map_index)
2326 struct FingerInfo *existing_finger;
2327 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2329 int old_entry_found = GNUNET_NO;
2330 int new_entry_added = GNUNET_NO;
2332 if (PREDECESSOR_FINGER_ID == finger_map_index)
2334 /* FIXME: Here GNUNET_NO, means that we did not update predecessor . But it
2335 we also need to handle the case that insertion failed in peer map after we decided to add
2337 if( GNUNET_YES == compare_and_update_predecessor (finger_identity, finger_trail, finger_trail_length))
2338 new_entry_added = GNUNET_YES;
2339 goto update_current_search_finger_index;
2342 /* Check if there is already an entry for the finger map index in the finger peer map. */
2343 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2344 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2346 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2347 (const void **)&existing_finger))
2349 if (existing_finger->finger_map_index == finger_map_index)
2351 old_entry_found = GNUNET_YES;
2352 if ( GNUNET_NO == select_closest_finger (existing_finger, finger_identity,
2353 finger_trail, finger_trail_length,
2355 goto update_current_search_finger_index;
2361 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2363 if (GNUNET_NO == old_entry_found)
2365 if (finger_trail_length > 0)
2367 scan_and_compress_trail (finger_trail, &finger_trail_length, finger_identity);
2370 /* SUPU: in this case you get GNUNET_NO, only when insertion fails in the peer map.
2371 so its an error as we already have decided to add the entry into finger peer map. */
2372 if(GNUNET_OK == add_new_entry (finger_identity,finger_trail,finger_trail_length, finger_map_index))
2373 new_entry_added = GNUNET_YES;
2377 update_current_search_finger_index:
2378 if (0 == finger_map_index)
2380 current_search_finger_index = PREDECESSOR_FINGER_ID;
2381 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity))
2382 send_verify_successor_message();
2384 else if (GNUNET_YES == compare_new_entry_and_successor (finger_identity,finger_map_index))
2386 current_search_finger_index = 0;
2390 current_search_finger_index = current_search_finger_index - 1;
2393 return new_entry_added;
2398 * FIXME: In case a friend is either congested or has crossed its trail threshold,
2399 * then don't consider it as next successor, In case of finger if its first
2400 * friend has crossed the threshold then don't consider it. In case no finger
2401 * or friend is found, then return NULL.
2402 * Find closest successor for the value.
2403 * @param value Value for which we are looking for successor
2404 * @param[out] current_destination set to my_identity in case I am the final destination,
2405 * set to friend identity in case friend is final destination,
2406 * set to first friend to reach to finger, in case finger
2407 * is final destination.
2408 * @param[out] current_source set to my_identity.
2409 * @return Peer identity of next hop to send trail setup message to,
2410 * NULL in case all the friends are either congested or have crossed
2411 * their trail threshold.
2413 static struct GNUNET_PeerIdentity *
2414 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
2415 struct GNUNET_PeerIdentity *current_source)
2417 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
2418 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2419 struct GNUNET_PeerIdentity key_ret;
2420 struct FriendInfo *friend;
2421 struct FingerInfo *finger;
2422 unsigned int finger_index;
2423 unsigned int friend_index;
2424 struct Sorting_List *successor;
2428 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
2429 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
2430 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
2433 struct Sorting_List all_known_peers[size];
2436 for (k = 0; k < size; k++)
2437 all_known_peers[k].peer_id = 0;
2439 /* Copy your identity at 0th index in all_known_peers. */
2441 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
2442 all_known_peers[j].type = MY_ID;
2443 all_known_peers[j].data = 0;
2447 all_known_peers[j].peer_id = value;
2448 all_known_peers[j].type = VALUE;
2449 all_known_peers[j].data = 0;
2452 /* Iterate over friend peer map and copy all the elements into array. */
2453 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2454 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
2456 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
2458 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
2459 all_known_peers[j].type = FRIEND;
2460 all_known_peers[j].data = friend;
2466 /* Iterate over finger map and copy all the entries into all_known_peers array. */
2467 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2468 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2470 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
2472 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
2473 all_known_peers[j].type = FINGER;
2474 all_known_peers[j].data = finger;
2479 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2480 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
2483 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
2485 /* search value in all_known_peers array. */
2486 successor = find_closest_successor (all_known_peers, value, size);
2488 if (successor->type == MY_ID)
2490 memcpy (current_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2491 return &my_identity;
2493 else if (successor->type == FRIEND)
2495 struct FriendInfo *target_friend;
2496 target_friend = (struct FriendInfo *)successor->data;
2497 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
2498 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2499 return current_destination;
2501 else if (successor->type == FINGER)
2503 struct GNUNET_PeerIdentity *next_hop;
2504 struct FingerInfo *finger;
2505 finger = successor->data;
2506 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2508 if (finger->first_trail_length > 0)
2510 struct TrailPeerList *iterator;
2511 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2512 iterator = finger->first_trail_head;
2513 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2515 else /* This means finger is our friend. */
2516 memcpy (next_hop, &(finger->finger_identity), sizeof(struct GNUNET_PeerIdentity));
2518 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
2519 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2531 * Construct a Put message and send it to target_peer.
2532 * @param key Key for the content
2533 * @param data Content to store
2534 * @param data_size Size of content @a data in bytes
2535 * @param block_type Type of the block
2536 * @param options Routing options
2537 * @param desired_replication_level Desired replication count
2538 * @param expiration_time When does the content expire
2539 * @param current_destination
2540 * @param current_source
2541 * @param target_peer Peer to which this message will be forwarded.
2542 * @param hop_count Number of hops traversed so far.
2543 * @param put_path_length Total number of peers in @a put_path
2544 * @param put_path Number of peers traversed so far
2547 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2548 const void *data, size_t data_size,
2549 enum GNUNET_BLOCK_Type block_type,
2550 enum GNUNET_DHT_RouteOption options,
2551 uint32_t desired_replication_level,
2552 struct GNUNET_TIME_Absolute expiration_time,
2553 struct GNUNET_PeerIdentity current_destination,
2554 struct GNUNET_PeerIdentity current_source,
2555 struct GNUNET_PeerIdentity *target_peer,
2557 uint32_t put_path_length,
2558 struct GNUNET_PeerIdentity *put_path)
2560 struct PeerPutMessage *ppm;
2561 struct P2PPendingMessage *pending;
2562 struct FriendInfo *target_friend;
2563 struct GNUNET_PeerIdentity *pp;
2566 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2567 sizeof (struct PeerPutMessage);
2569 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2571 put_path_length = 0;
2572 msize = data_size + sizeof (struct PeerPutMessage);
2575 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2581 /* This is the first call made from clients file. So, we should search for the
2583 if (NULL == target_peer)
2586 struct GNUNET_PeerIdentity *next_hop;
2588 memcpy (&key_value, key, sizeof (uint64_t));
2589 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2591 if (0 == GNUNET_CRYPTO_cmp_peer_identity(next_hop, ¤t_destination)) /* I am the destination do datacache_put */
2593 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
2594 block_type, data_size, data);
2598 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2601 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2602 pending->timeout = expiration_time;
2603 ppm = (struct PeerPutMessage *) &pending[1];
2604 pending->msg = &ppm->header;
2605 ppm->header.size = htons (msize);
2606 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
2607 ppm->options = htonl (options);
2608 ppm->block_type = htonl (block_type);
2609 ppm->hop_count = htonl (hop_count + 1);
2610 ppm->desired_replication_level = htonl (desired_replication_level);
2611 ppm->put_path_length = htonl (put_path_length);
2612 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2614 ppm->current_destination = current_destination;
2615 ppm->current_source = current_source;
2617 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2618 if (put_path_length != 0)
2620 memcpy (pp, put_path,
2621 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2623 memcpy (&pp[put_path_length], data, data_size);
2624 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2625 target_friend->pending_count++;
2626 process_friend_queue (target_friend);
2632 * Construct a Get message and send it to target_peer.
2633 * @param key Key for the content
2634 * @param block_type Type of the block
2635 * @param options Routing options
2636 * @param desired_replication_level Desired replication count
2637 * @param expiration_time When does the content expire
2638 * @param current_destination
2639 * @param current_source
2640 * @param target_peer Peer to which this message will be forwarded.
2641 * @param hop_count Number of hops traversed so far.
2642 * @param put_path_length Total number of peers in @a put_path
2643 * @param put_path Number of peers traversed so far
2646 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2647 enum GNUNET_BLOCK_Type block_type,
2648 enum GNUNET_DHT_RouteOption options,
2649 uint32_t desired_replication_level,
2650 struct GNUNET_PeerIdentity current_destination,
2651 struct GNUNET_PeerIdentity current_source,
2652 struct GNUNET_PeerIdentity *target_peer,
2654 uint32_t get_path_length,
2655 struct GNUNET_PeerIdentity *get_path)
2657 struct PeerGetMessage *pgm;
2658 struct P2PPendingMessage *pending;
2659 struct FriendInfo *target_friend;
2660 struct GNUNET_PeerIdentity *gp;
2663 msize = sizeof (struct PeerGetMessage) +
2664 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2666 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2672 if (NULL == target_peer)
2674 /* This is the first call from client file, we need to search for next_hop*/
2675 struct GNUNET_PeerIdentity *next_hop;
2678 memcpy (&key_value, key, sizeof (uint64_t));
2679 // FIXME: endianess of key_value!?
2680 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2682 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity,next_hop)) /* I am the destination do datacache_put */
2684 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2685 NULL, 0, 1, &my_identity, NULL,&my_identity);
2690 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2694 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2695 pending->importance = 0; /* FIXME */
2696 pgm = (struct PeerGetMessage *) &pending[1];
2697 pending->msg = &pgm->header;
2698 pgm->header.size = htons (msize);
2699 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2700 pgm->get_path_length = htonl (get_path_length);
2702 pgm->current_destination = current_destination;
2703 pgm->current_source = current_source;
2704 pgm->hop_count = htonl (hop_count + 1);
2708 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2709 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2711 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2712 target_friend->pending_count++;
2713 process_friend_queue (target_friend);
2718 * Send the get result to requesting client.
2719 * @param expiration When will this result expire?
2720 * @param key Key of the requested data.
2721 * @param put_path_length Number of peers in @a put_path
2722 * @param put_path Path taken to put the data at its stored location.
2723 * @param type Block type
2724 * @param data_size Size of the @a data
2725 * @param data Payload to store
2726 * @param get_path Path taken to reach to the location of the key.
2727 * @param get_path_length Number of peers in @a get_path
2728 * @param next_hop Next peer to forward the message to.
2729 * @param source_peer Peer which has the data for the key.
2732 GDS_NEIGHBOURS_send_get_result (struct GNUNET_TIME_Absolute expiration,
2733 const struct GNUNET_HashCode *key,
2734 unsigned int put_path_length,
2735 const struct GNUNET_PeerIdentity *put_path,
2736 enum GNUNET_BLOCK_Type type, size_t data_size,
2738 struct GNUNET_PeerIdentity *get_path,
2739 unsigned int get_path_length,
2740 struct GNUNET_PeerIdentity *next_hop,
2741 struct GNUNET_PeerIdentity *source_peer)
2743 struct PeerGetResultMessage *get_result;
2744 struct GNUNET_PeerIdentity *get_result_path;
2745 struct GNUNET_PeerIdentity *pp;
2746 struct P2PPendingMessage *pending;
2747 struct FriendInfo *target_friend;
2748 int current_path_index;
2751 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2752 sizeof (struct PeerPutMessage);
2754 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2760 current_path_index = search_my_index(get_path, get_path_length);
2761 if (GNUNET_SYSERR == current_path_index)
2766 if (0 == current_path_index)
2768 GDS_CLIENTS_handle_reply (expiration, key, get_path_length, get_path, put_path_length,
2769 put_path, type, data_size, data);
2773 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2774 pending->importance = 0;
2775 get_result = (struct PeerGetResultMessage *)&pending[1];
2776 pending->msg = &get_result->header;
2777 get_result->header.size = htons (msize);
2778 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2779 get_result->key = *key;
2780 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2781 get_result->expiration_time = expiration;
2783 if (get_path_length != 0)
2785 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2786 memcpy (get_result_path, get_path,
2787 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2789 memcpy (&get_result_path[get_path_length], data, data_size);
2791 /* FIXME: Is this correct? */
2792 if (put_path_length != 0)
2794 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2795 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2797 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2798 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2799 target_friend->pending_count++;
2800 process_friend_queue (target_friend);
2805 * Send trail rejection message to the peer which sent me a trail setup message.
2806 * @param source_peer Source peer which wants to set up the trail.
2807 * @param finger_identity Value whose successor will be the finger of @a source_peer.
2808 * @param congested_peer Peer which has send trail rejection message.
2809 * @param next_hop Peer to which this message should be forwarded.
2810 * @param finger_map_index Index in @a source_peer finger peermap.
2811 * @param trail_peer_list Trail followed to reach from @a source_peer to next_hop,
2812 * NULL, in case the @a congested_peer was the first peer
2813 * to which trail setup message was forwarded.
2814 * @param trail_length Number of peers in trail_peer_list.
2817 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity *source_peer,
2818 uint64_t finger_identity,
2819 struct GNUNET_PeerIdentity *congested_peer,
2820 const struct GNUNET_PeerIdentity *next_hop,
2821 unsigned int finger_map_index,
2822 struct GNUNET_PeerIdentity *trail_peer_list,
2823 unsigned int trail_length)
2825 struct PeerTrailRejectionMessage *trail_rejection;
2826 struct GNUNET_PeerIdentity *trail_list;
2827 struct P2PPendingMessage *pending;
2828 struct FriendInfo *target_friend;
2831 msize = trail_length * sizeof(struct GNUNET_PeerIdentity) +
2832 sizeof (struct PeerTrailRejectionMessage);
2834 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2840 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2841 pending->importance = 0;
2842 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2843 trail_rejection = (struct PeerTrailRejectionMessage *) &pending[1];
2844 pending->msg = &trail_rejection->header;
2845 trail_rejection->header.size = htons (msize);
2846 trail_rejection->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
2847 memcpy (&(trail_rejection->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2848 memcpy (&(trail_rejection->congested_peer), congested_peer, sizeof (struct GNUNET_PeerIdentity));
2849 memcpy (&(trail_rejection->finger_identity_value), &finger_identity, sizeof (uint64_t));
2850 trail_rejection->finger_map_index = htonl(finger_map_index);
2851 trail_rejection->trail_length = htonl (trail_length);
2853 if (trail_length != 0)
2855 trail_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2856 memcpy (trail_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2859 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2860 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2861 target_friend->pending_count++;
2862 process_friend_queue (target_friend);
2867 * Core handler for P2P put messages.
2868 * @param cls closure
2869 * @param peer sender of the request
2870 * @param message message
2871 * @return #GNUNET_OK to keep the connection open,
2872 * #GNUNET_SYSERR to close it (signal serious error)
2875 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2876 const struct GNUNET_MessageHeader *message)
2878 struct PeerPutMessage *put;
2879 struct GNUNET_PeerIdentity *put_path;
2880 struct GNUNET_HashCode test_key;
2881 enum GNUNET_DHT_RouteOption options;
2882 struct GNUNET_PeerIdentity current_destination;
2883 struct GNUNET_PeerIdentity current_source;
2884 struct GNUNET_PeerIdentity *next_hop;
2888 size_t payload_size;
2891 msize = ntohs (message->size);
2892 if (msize < sizeof (struct PeerPutMessage))
2894 GNUNET_break_op (0);
2898 put = (struct PeerPutMessage *) message;
2899 putlen = ntohl (put->put_path_length);
2902 sizeof (struct PeerPutMessage) +
2903 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2905 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2907 GNUNET_break_op (0);
2911 current_destination = put->current_destination;
2912 current_source = put->current_source;
2913 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2914 payload = &put_path[putlen];
2915 options = ntohl (put->options);
2916 payload_size = msize - (sizeof (struct PeerPutMessage) +
2917 putlen * sizeof (struct GNUNET_PeerIdentity));
2919 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
2920 payload, payload_size, &test_key))
2923 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
2925 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
2926 GNUNET_break_op (0);
2927 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2928 "PUT with key `%s' for block with key %s\n",
2929 put_s, GNUNET_h2s_full (&test_key));
2930 GNUNET_free (put_s);
2935 GNUNET_break_op (0);
2938 /* cannot verify, good luck */
2942 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
2944 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
2945 ntohl (put->block_type),
2947 NULL, 0, /* bloom filer */
2948 NULL, 0, /* xquery */
2949 payload, payload_size))
2951 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2952 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2955 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2956 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2957 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
2958 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2959 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2960 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2962 GNUNET_break_op (0);
2967 struct GNUNET_PeerIdentity pp[putlen + 1];
2968 /* extend 'put path' by sender */
2969 /* FIXME: Check what are we doing here? */
2970 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
2972 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
2979 memcpy (&key_value, &(put->key), sizeof (uint64_t));
2980 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2982 GDS_ROUTING_print();
2983 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2984 if (next_hop == NULL)
2986 /* refer to handle_dht_p2p_trail_setup. */
2991 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2994 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop)) /* I am the final destination */
2996 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
2997 &(put->key),putlen, pp, ntohl (put->block_type),
2998 payload_size, payload);
3003 GDS_CLIENTS_process_put (options,
3004 ntohl (put->block_type),
3005 ntohl (put->hop_count),
3006 ntohl (put->desired_replication_level),
3008 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3013 GDS_NEIGHBOURS_send_put (&put->key, payload, payload_size,
3014 ntohl (put->block_type),ntohl (put->options),
3015 ntohl (put->desired_replication_level),
3016 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3017 current_destination, current_source, next_hop,
3018 ntohl (put->hop_count), putlen, pp);
3022 return GNUNET_SYSERR;
3027 * Core handler for p2p get requests.
3029 * @param cls closure
3030 * @param peer sender of the request
3031 * @param message message
3032 * @return #GNUNET_OK to keep the connection open,
3033 * #GNUNET_SYSERR to close it (signal serious error)
3036 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3037 const struct GNUNET_MessageHeader *message)
3039 struct PeerGetMessage *get;
3040 struct GNUNET_PeerIdentity *get_path;
3041 struct GNUNET_PeerIdentity current_destination;
3042 struct GNUNET_PeerIdentity current_source;
3043 struct GNUNET_PeerIdentity *next_hop;
3044 uint32_t get_length;
3048 msize = ntohs (message->size);
3049 if (msize < sizeof (struct PeerGetMessage))
3051 GNUNET_break_op (0);
3055 get = (struct PeerGetMessage *)message;
3056 get_length = ntohl (get->get_path_length);
3057 get_path = (struct GNUNET_PeerIdentity *)&get[1];
3058 current_destination = get->current_destination;
3059 current_source = get->current_source;
3062 sizeof (struct PeerGetMessage) +
3063 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3065 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3067 GNUNET_break_op (0);
3071 /* Add sender to get path */
3072 struct GNUNET_PeerIdentity gp[get_length + 1];
3073 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3074 gp[get_length + 1] = *peer;
3075 get_length = get_length + 1;
3077 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3078 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3080 GDS_ROUTING_print();
3081 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3082 if (next_hop == NULL)
3084 /* refer to handle_dht_p2p_trail_setup. */
3089 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
3092 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop))
3094 /* I am the destination.*/
3095 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3096 struct GNUNET_PeerIdentity next_hop;
3098 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3099 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3100 get_length = get_length + 1;
3101 memcpy (&next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
3103 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3104 get_length, final_get_path,&next_hop, &my_identity);
3110 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3111 get->desired_replication_level,current_destination,
3112 current_source, next_hop, 0,
3115 return GNUNET_SYSERR;
3120 * FIXME: In case of trail, we don't have source and destination part of the trail,
3121 * Check if we follow the same in case of get/put/get_result. Also, in case of
3122 * put should we do a routing table add.
3123 * Core handler for get result
3124 * @param cls closure
3125 * @param peer sender of the request
3126 * @param message message
3127 * @return #GNUNET_OK to keep the connection open,
3128 * #GNUNET_SYSERR to close it (signal serious error)
3131 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3132 const struct GNUNET_MessageHeader *message)
3134 struct PeerGetResultMessage *get_result;
3135 struct GNUNET_PeerIdentity *get_path;
3136 struct GNUNET_PeerIdentity *put_path;
3138 size_t payload_size;
3140 unsigned int getlen;
3141 unsigned int putlen;
3142 int current_path_index;
3144 msize = ntohs (message->size);
3145 if (msize < sizeof (struct PeerGetResultMessage))
3147 GNUNET_break_op (0);
3151 get_result = (struct PeerGetResultMessage *)message;
3152 getlen = ntohl (get_result->get_path_length);
3153 putlen = ntohl (get_result->put_path_length);
3156 sizeof (struct PeerGetResultMessage) +
3157 getlen * sizeof (struct GNUNET_PeerIdentity) +
3158 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3160 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3162 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3164 GNUNET_break_op (0);
3168 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
3169 payload = &get_path[getlen];
3170 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3171 getlen * sizeof (struct GNUNET_PeerIdentity));
3172 /* FIXME: Check if its correct or not. */
3175 put_path = &get_path[1];
3179 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3181 //GDS_CLIENTS_process_get_result();
3182 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3183 getlen, get_path, putlen,
3184 put_path, get_result->type, payload_size, payload);
3189 struct GNUNET_PeerIdentity *next_hop;
3190 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3191 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3192 current_path_index = search_my_index (get_path, getlen);
3193 /* FIXME: First check if you are adding yourself to the get path or not.
3194 if yes then don't check if current_path_index == 0, if not then check
3195 and next_hop == source_peer. */
3196 memcpy (next_hop, &get_path[current_path_index - 1], sizeof (struct GNUNET_PeerIdentity));
3198 GDS_NEIGHBOURS_send_get_result (get_result->expiration_time, &(get_result->key),
3200 get_result->type, payload_size,payload,
3202 next_hop, &(get_result->source_peer));
3205 return GNUNET_SYSERR;
3210 * FIXME: Is all trails threshold and routing table has some link.
3211 * Core handle for PeerTrailSetupMessage.
3212 * @param cls closure
3213 * @param message message
3214 * @param peer peer identity this notification is about
3215 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3218 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3219 const struct GNUNET_MessageHeader *message)
3221 const struct PeerTrailSetupMessage *trail_setup;
3222 struct GNUNET_PeerIdentity current_destination;
3223 struct GNUNET_PeerIdentity current_source;
3224 struct GNUNET_PeerIdentity source;
3225 struct GNUNET_PeerIdentity *next_hop;
3226 struct GNUNET_PeerIdentity next_peer;
3227 struct GNUNET_PeerIdentity *trail_peer_list;
3228 struct FriendInfo *target_friend;
3229 uint64_t destination_finger_value;
3230 uint32_t trail_length;
3231 uint32_t finger_map_index;
3234 msize = ntohs (message->size);
3235 if (msize < sizeof (struct PeerTrailSetupMessage))
3237 GNUNET_break_op (0);
3241 trail_setup = (const struct PeerTrailSetupMessage *) message;
3242 trail_length = ntohl (trail_setup->trail_length);
3244 if ((msize < sizeof (struct PeerTrailSetupMessage) +
3245 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3247 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3249 GNUNET_break_op (0);
3253 if (trail_length > 0)
3254 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
3255 memcpy (¤t_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity));
3256 memcpy (¤t_source,&(trail_setup->current_source), sizeof (struct GNUNET_PeerIdentity));
3257 memcpy (&source, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity));
3258 finger_map_index = ntohl (trail_setup->finger_map_index);
3259 destination_finger_value = ntohl (trail_setup->destination_finger);
3262 /* FIXME: Here we need to check 3 things
3263 * 1. if my routing table is all full
3264 * 2. if all my friends are congested
3265 * 3. if trail threshold of my friends have crossed.
3266 * In all these cases we need to send back trail rejection message. */
3267 if ( (GNUNET_YES == all_friends_trail_threshold)
3268 || (GNUNET_YES == GDS_ROUTING_check_threshold()))
3270 /* If all the friends have reached their trail threshold or if there is no
3271 more space in routing table to store more trails, then reject. */
3272 GDS_NEIGHBOURS_send_trail_rejection (&source, destination_finger_value, &my_identity,
3273 peer,finger_map_index, trail_peer_list,trail_length);
3279 /* Check if you are current_destination or not. */
3280 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3282 GDS_ROUTING_print();
3283 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3284 /* OPTIMIZATION: Choose a peer from find_successor and choose the closest one.
3285 In case the closest one is from routing table and it is NULL, then update
3287 if (next_hop == NULL)
3289 /* FIXME: Should we inform the peer before us. If not then it may continue
3290 to send us request. But in case we want to inform we need to have a
3291 different kind of message. */
3292 GNUNET_STATISTICS_update (GDS_stats,
3293 gettext_noop ("# Trail not found in routing table during"
3294 "trail setup request, packet dropped."),
3301 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
3304 if (NULL == next_hop)
3306 return GNUNET_SYSERR;
3308 else if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
3310 if (trail_length == 0)
3312 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
3316 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3319 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3320 /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
3321 if (PREDECESSOR_FINGER_ID != finger_map_index)
3323 /* FIXME: Is this correct assumption? A peer which think I am its predecessor,
3324 then I am not its predecessor. */
3325 compare_and_update_predecessor (&source, trail_peer_list, trail_length );
3327 GDS_NEIGHBOURS_send_trail_setup_result (&source,
3329 target_friend, trail_length,
3336 /* Now add yourself to the trail. */
3337 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3338 if (trail_length != 0)
3339 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3340 peer_list[trail_length] = my_identity;
3342 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3343 GDS_NEIGHBOURS_send_trail_setup (&source,
3344 destination_finger_value,
3345 ¤t_destination, ¤t_source,
3346 target_friend, trail_length, peer_list,
3354 * Core handle for p2p trail construction result messages.
3356 * @param message message
3357 * @param peer peer identity this notification is about
3358 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3361 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3362 const struct GNUNET_MessageHeader *message)
3364 const struct PeerTrailSetupResultMessage *trail_result;
3365 struct GNUNET_PeerIdentity *trail_peer_list;
3366 uint32_t trail_length;
3367 uint32_t finger_map_index;
3370 msize = ntohs (message->size);
3371 if (msize < sizeof (struct PeerTrailSetupResultMessage))
3373 GNUNET_break_op (0);
3377 trail_result = (const struct PeerTrailSetupResultMessage *) message;
3378 trail_length = ntohl (trail_result->trail_length);
3381 sizeof (struct PeerTrailSetupResultMessage) +
3382 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3384 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3386 GNUNET_break_op (0);
3390 finger_map_index = htonl (trail_result->finger_map_index);
3391 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
3393 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3396 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
3402 struct GNUNET_PeerIdentity next_hop;
3403 struct FriendInfo *target_friend;
3406 my_index = search_my_index (trail_peer_list, trail_length);
3407 if (my_index == GNUNET_SYSERR)
3408 return GNUNET_SYSERR;
3412 next_hop = trail_result->destination_peer;
3415 next_hop = trail_peer_list[my_index - 1];
3417 /* Finger table of destination peer will not contain any trail for the case
3418 * where destination peer is its own finger identity.*/
3419 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3420 &(trail_result->finger_identity))))
3422 /* FIXME: First call GDS_ROUTING_search, only if it returns NULL, call
3423 GDS_ROUTING_add. But in case we have same 3 fields but 1 different next hop
3424 then we should add the entry but in current implementation of GDS_ROUTNG_search
3425 we don't handle it. */
3426 GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
3428 GDS_ROUTING_print();
3431 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3432 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
3433 &(trail_result->finger_identity),
3434 target_friend, trail_length,
3439 return GNUNET_SYSERR;
3444 * Get my current predecessor from the finger peer map
3445 * @return Current predecessor.
3447 static struct FingerInfo *
3450 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
3451 struct GNUNET_PeerIdentity key_ret;
3452 unsigned int finger_index;
3453 struct FingerInfo *my_predecessor;
3456 /* Iterate over finger peer map and extract your predecessor. */
3457 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
3458 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
3460 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
3461 (finger_iter,&key_ret,(const void **)&my_predecessor))
3463 if(PREDECESSOR_FINGER_ID == my_predecessor->finger_map_index)
3470 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
3475 return my_predecessor;
3480 * Core handle for p2p verify successor messages.
3481 * @param cls closure
3482 * @param message message
3483 * @param peer peer identity this notification is about
3484 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3487 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3488 const struct GNUNET_MessageHeader *message)
3490 const struct PeerVerifySuccessorMessage *vsm;
3491 const struct GNUNET_PeerIdentity *trail_peer_list;
3492 struct GNUNET_PeerIdentity source_peer;
3493 struct GNUNET_PeerIdentity next_hop;
3494 struct FriendInfo *target_friend;
3496 uint32_t trail_length;
3498 msize = ntohs (message->size);
3499 if (msize < sizeof (struct PeerVerifySuccessorMessage))
3501 GNUNET_break_op (0);
3505 vsm = (struct PeerVerifySuccessorMessage *) message;
3506 trail_length = ntohl (vsm->trail_length);
3508 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
3509 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3510 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3512 GNUNET_break_op (0);
3515 if (trail_length > 0)
3516 trail_peer_list = (const struct GNUNET_PeerIdentity *)&vsm[1];
3517 memcpy (&source_peer, &(vsm->source_peer), sizeof(struct GNUNET_PeerIdentity));
3519 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
3521 struct FingerInfo *my_predecessor;
3522 if (trail_length == 0)
3524 /* SUPU: If I am friend of source_peer, then trail_length == 0. */
3525 memcpy (&next_hop, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3529 /* SUPU: Here I am the final destination successor, and trail does not contain
3530 destination. So, the next hop is the last element in the trail. */
3531 memcpy (&next_hop, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3533 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3535 my_predecessor = get_predecessor();
3536 if (NULL == my_predecessor)
3539 return GNUNET_SYSERR;
3542 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3543 &(my_predecessor->finger_identity))))
3545 /* Source peer and my predecessor, both are same. */
3546 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3548 &(my_predecessor->finger_identity),
3555 struct GNUNET_PeerIdentity *new_successor_trail;
3556 struct TrailPeerList *iterator;
3557 int new_trail_length;
3560 new_trail_length = trail_length + my_predecessor->first_trail_length + 1;
3561 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
3562 if (trail_length > 0)
3563 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
3565 memcpy (&new_successor_trail[trail_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3567 if (my_predecessor->first_trail_length)
3569 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
3570 iterator = my_predecessor->first_trail_head;
3571 i = trail_length + 1;
3572 while (i < new_trail_length)
3574 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
3575 iterator = iterator->next;
3579 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3581 &(my_predecessor->finger_identity),
3583 new_successor_trail,
3592 if (trail_length == 0)
3595 return GNUNET_SYSERR;
3598 my_index = search_my_index (trail_peer_list, trail_length);
3599 if (my_index == GNUNET_SYSERR)
3602 return GNUNET_SYSERR;
3604 if (my_index == (trail_length - 1))
3606 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(vsm->successor));
3610 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3611 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3614 GDS_NEIGHBOURS_send_verify_successor (&(vsm->source_peer), &(vsm->successor),target_friend,
3615 trail_peer_list, trail_length);
3617 return GNUNET_SYSERR;
3621 /**FIXME: in case we have a new successor do we need to update the entries in
3622 * routing table to change the destination of the message from old successor
3623 * to new successor or when the old successor sends the message the I am not
3624 * your successor then it sends a trail teardown message across the old trail.
3625 * Need to decide on a strategy.
3626 * Core handle for p2p verify successor result messages.
3627 * @param cls closure
3628 * @param message message
3629 * @param peer peer identity this notification is about
3630 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3633 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3634 const struct GNUNET_MessageHeader *message)
3636 const struct PeerVerifySuccessorResultMessage *vsrm;
3637 struct GNUNET_PeerIdentity *trail_peer_list;
3638 struct GNUNET_PeerIdentity next_hop;
3639 struct FriendInfo *target_friend;
3641 uint32_t trail_length;
3643 msize = ntohs (message->size);
3644 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
3646 GNUNET_break_op (0);
3649 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
3650 trail_length = ntohl (vsrm->trail_length);
3653 sizeof (struct PeerVerifySuccessorResultMessage) +
3654 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3656 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3658 GNUNET_break_op (0);
3661 /* FIXME: URGENT: What happens when trail length = 0. */
3663 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
3665 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity))))
3667 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
3669 /* FIXME: Here we have got a new successor. But it may happen that our logic
3670 * says that this is not correct successor. so in finger table add it
3671 * failed to update the successor and we are still sending a notify
3672 * new successor. Here trail_length will be atleast 1, in case we have a new
3673 * successor because in that case our old successor is part of trail.
3674 * Could it be possible that our identity and my_predecessor is same. Check it. */
3675 if (GNUNET_YES == finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0))
3677 memcpy (&next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
3678 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3679 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
3680 target_friend, trail_peer_list,
3688 return GNUNET_SYSERR;
3696 my_index = search_my_index (trail_peer_list, trail_length);
3697 if (GNUNET_SYSERR == my_index)
3700 return GNUNET_SYSERR;
3705 /* Source is not part of trail, so if I am the last one then my index
3707 memcpy (&next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3711 memcpy (&next_hop, &trail_peer_list[my_index-1], sizeof (struct GNUNET_PeerIdentity));
3714 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3715 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
3716 &(vsrm->source_successor),
3717 &(vsrm->my_predecessor),
3723 return GNUNET_SYSERR;
3728 * Core handle for p2p notify new successor messages.
3729 * @param cls closure
3730 * @param message message
3731 * @param peer peer identity this notification is about
3732 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3735 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3736 const struct GNUNET_MessageHeader *message)
3738 const struct PeerNotifyNewSuccessorMessage *nsm;
3739 struct GNUNET_PeerIdentity *trail_peer_list;
3741 uint32_t trail_length;
3743 msize = ntohs (message->size);
3744 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
3746 GNUNET_break_op (0);
3749 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
3750 trail_length = ntohl (nsm->trail_length);
3752 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3753 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3755 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3757 GNUNET_break_op (0);
3761 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
3763 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), &my_identity)))
3765 /* I am the new successor. */
3766 struct GNUNET_PeerIdentity new_predecessor;
3767 memcpy (&new_predecessor, &(nsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
3768 if (GNUNET_NO == compare_and_update_predecessor (&new_predecessor, trail_peer_list,
3771 /* Someone claims to be my predecessor but its not closest predecessor
3774 return GNUNET_SYSERR;
3780 struct FriendInfo *target_friend;
3781 struct GNUNET_PeerIdentity next_hop;
3784 my_index = search_my_index (trail_peer_list, trail_length);
3785 if (GNUNET_SYSERR == my_index)
3788 return GNUNET_SYSERR;
3791 if (my_index == (trail_length - 1))
3793 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(nsm->destination_peer));
3797 memcpy (&next_hop, &trail_peer_list[my_index+1], sizeof (struct GNUNET_PeerIdentity));
3798 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3800 /* FIXME: Should we update the entries in routing table? */
3801 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
3802 &(nsm->destination_peer),
3803 target_friend, trail_peer_list,
3807 return GNUNET_SYSERR;
3812 * FIXME; Should we call select_random_friend from here in case I am the source
3813 * of the message or should I just return and in next iteration by default
3814 * we will call select random friend from send_find_finger_trail. But in that
3815 * case we should maintain a list of congested peer which failed to setup the
3816 * trail. and then in select random friend we should ignore them. this list
3817 * should have an expiration time and we should garbage collect it periodically.
3818 * Core handler for P2P trail rejection message
3819 * @param cls closure
3820 * @param message message
3821 * @param peer peer identity this notification is about
3822 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3825 int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3826 const struct GNUNET_MessageHeader *message)
3828 /* Here you have recevied the message it means that the peer next to you have
3829 failed to setup the trail to the finger identity value. now you should call
3830 find_successor and make sure that you don't choose the peer as next hop
3831 in order to do so, you need to pass a new parameter to find successor,
3832 congested peer - a peer which you should ignore. once you have found this
3833 peer then just send a trail setup message to that peer. In case you are
3834 also congested then remove yourself from the trail as this message
3835 reached to as you are part of the trail. and then send the message to
3836 element before you. Ideally you should be the last element in the trail as
3837 all the the elements before you have rejected you. In case you are source,
3838 then you should call select_random_Friend(congested_peer). in case you don't
3839 find any peer because congested peer then set flag that all friends are busy
3841 const struct PeerTrailRejectionMessage *trail_rejection;
3842 struct GNUNET_PeerIdentity *trail_peer_list;
3843 struct GNUNET_PeerIdentity source_peer;
3844 struct GNUNET_PeerIdentity congested_peer;
3845 struct FriendInfo *target_friend;
3846 struct GNUNET_PeerIdentity next_peer;
3847 struct GNUNET_PeerIdentity *next_hop;
3848 struct GNUNET_PeerIdentity current_source;
3849 struct GNUNET_PeerIdentity current_destination;
3851 uint32_t trail_length;
3852 uint32_t finger_map_index;
3853 uint64_t destination_finger_value;
3855 msize = ntohs (message->size);
3856 if (msize < sizeof (struct PeerTrailRejectionMessage))
3858 GNUNET_break_op (0);
3862 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3863 trail_length = ntohl (trail_rejection->trail_length);
3865 if ((msize < sizeof (struct PeerTrailRejectionMessage) +
3866 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3868 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3870 GNUNET_break_op (0);
3874 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3875 finger_map_index = ntohl (trail_rejection->finger_map_index);
3876 memcpy (&source_peer, &(trail_rejection->source_peer), sizeof(struct GNUNET_PeerIdentity));
3877 memcpy (&destination_finger_value, &(trail_rejection->finger_identity_value), sizeof (uint64_t));
3878 memcpy (&congested_peer, &(trail_rejection->congested_peer), sizeof (struct GNUNET_PeerIdentity));
3880 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source_peer)))
3882 /* I am the source of original trail setup message. Do nothing and exit. */
3883 /* In current implementation, when we don't get the result of a trail setup,
3884 then no entry is added to finger table and hence, by default a trail setup for
3885 the same finger map index is sent. so we don't need to send it here. */
3889 if(GDS_ROUTING_check_threshold())
3891 /* My routing state size has crossed the threshold, I can not be part of any more
3893 struct GNUNET_PeerIdentity *new_trail;
3895 if (trail_length == 1)
3897 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3901 /* FIXME: Here if I got the trail rejection message then I am the last element
3902 in the trail. So, I should choose trail_length-2.*/
3903 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
3906 /* Remove myself from the trail. */
3907 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3908 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3910 /* No more trails possible through me. send a trail rejection message to next hop. */
3911 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
3912 &next_peer,finger_map_index, new_trail,trail_length - 1);
3916 memcpy (¤t_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
3917 memcpy (¤t_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
3918 /* FIXME: After adding a new field in struct FriendInfo congested, then call
3919 find successor then it will never consider that friend by default. */
3920 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
3922 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, ¤t_destination))) /* This means I am the final destination */
3924 if (trail_length == 1)
3926 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3930 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3933 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3934 compare_and_update_predecessor (&source_peer, trail_peer_list, trail_length);
3936 GDS_NEIGHBOURS_send_trail_setup_result (&source_peer,
3938 target_friend, trail_length,
3943 else if (NULL == next_hop)
3945 /* No peer found. Send a trail rejection message to previous peer in the trail. */
3947 struct GNUNET_PeerIdentity *new_trail;
3949 if (trail_length == 1)
3951 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3955 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
3958 /* Remove myself from the trail. */
3959 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3960 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3962 /* No more trails possible through me. send a trail rejection message to next hop. */
3963 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
3964 &next_peer,finger_map_index, new_trail,trail_length - 1);
3969 /* Now add yourself to the trail. */
3970 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3971 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3972 peer_list[trail_length] = my_identity;
3975 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3976 GDS_NEIGHBOURS_send_trail_setup (&source_peer,
3977 destination_finger_value,
3978 ¤t_destination, ¤t_source,
3979 target_friend, trail_length, peer_list,
3983 return GNUNET_SYSERR;
3987 /* Core handle for p2p trail tear down messages.
3988 * @param cls closure
3989 * @param message message
3990 * @param peer peer identity this notification is about
3991 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3994 int handle_dht_p2p_trail_teardown(void *cls, const struct GNUNET_PeerIdentity *peer,
3995 const struct GNUNET_MessageHeader *message)
3997 struct PeerTrailTearDownMessage *trail_teardown;
3998 struct GNUNET_PeerIdentity *discarded_trail;
3999 struct GNUNET_PeerIdentity next_hop;
4000 struct FriendInfo *target_friend;
4001 uint32_t discarded_trail_length;
4005 msize = ntohs (message->size);
4006 if (msize < sizeof (struct PeerTrailTearDownMessage))
4008 GNUNET_break_op (0);
4012 trail_teardown = (struct PeerTrailTearDownMessage *) message;
4013 discarded_trail_length = ntohl (trail_teardown->trail_length);
4015 if ((msize < sizeof (struct PeerTrailTearDownMessage) +
4016 discarded_trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
4017 (discarded_trail_length >
4018 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
4020 GNUNET_break_op (0);
4024 discarded_trail = (struct GNUNET_PeerIdentity *) &trail_teardown[1];
4026 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->new_first_friend),
4029 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer),
4037 * I am the new first hop in the trail to reach from source to destination.
4038 Update the trail in routing table with prev_hop == source peer. */
4043 my_index = search_my_index (discarded_trail, discarded_trail_length);
4044 if(GNUNET_SYSERR == my_index)
4045 return GNUNET_SYSERR;
4047 GDS_ROUTING_print();
4048 if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
4049 &(trail_teardown->destination_peer),peer))
4051 /* Here we get GNUNET_NO, only if there is no matching entry found in routing
4057 memcpy (&next_hop, &discarded_trail[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
4058 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4059 GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer),
4060 &(trail_teardown->destination_peer),
4061 discarded_trail, discarded_trail_length,
4062 target_friend, &(trail_teardown->new_first_friend));
4065 return GNUNET_SYSERR;
4070 * Iterate over finger_peermap, and remove entries with peer as the first element
4072 * @param cls closure
4073 * @param key current public key
4074 * @param value value in the hash map
4075 * @return #GNUNET_YES if we should continue to
4077 * #GNUNET_NO if not.
4080 remove_matching_finger (void *cls,
4081 const struct GNUNET_PeerIdentity *key,
4084 struct FingerInfo *remove_finger = value;
4085 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
4087 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->first_trail_head->peer, disconnected_peer)
4088 || (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_finger->finger_identity), disconnected_peer)))
4090 GNUNET_assert (GNUNET_YES ==
4091 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
4094 free_finger (remove_finger);
4102 * Method called whenever a peer disconnects.
4104 * @param cls closure
4105 * @param peer peer identity this notification is about
4108 handle_core_disconnect (void *cls,
4109 const struct GNUNET_PeerIdentity *peer)
4111 struct FriendInfo *remove_friend;
4113 /* Check for self message. */
4114 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
4117 /* Search for peer to remove in your friend_peermap. */
4119 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4121 if (NULL == remove_friend)
4127 /* Remove fingers for which this peer is the first element in the trail or if
4128 * the friend is a finger. */
4129 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap,
4130 &remove_matching_finger, (void *)peer);
4132 /* Remove routing trails of which this peer is a part.
4133 * FIXME: Here do we only remove the entry from our own routing table
4134 * or do we also inform other peers which are part of trail. It seems to be
4135 * too much of messages exchanged. */
4136 GDS_ROUTING_print();
4137 GDS_ROUTING_remove_entry (peer);
4139 /* Remove the peer from friend_peermap. */
4140 GNUNET_assert (GNUNET_YES ==
4141 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
4145 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
4148 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4150 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4151 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4159 * Method called whenever a peer connects.
4161 * @param cls closure
4162 * @param peer_identity peer identity this notification is about
4165 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
4167 struct FriendInfo *friend;
4169 /* Check for connect to self message */
4170 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
4173 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
4175 /* If peer already exists in our friend_peermap, then exit. */
4176 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
4182 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
4185 friend = GNUNET_new (struct FriendInfo);
4186 friend->id = *peer_identity;
4187 friend->trails_count = 0;
4189 GNUNET_assert (GNUNET_OK ==
4190 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
4191 peer_identity, friend,
4192 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
4194 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
4195 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
4196 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
4201 * To be called on core init/fail.
4203 * @param cls service closure
4204 * @param identity the public identity of this peer
4207 core_init (void *cls,
4208 const struct GNUNET_PeerIdentity *identity)
4210 my_identity = *identity;
4215 * Initialize neighbours subsystem.
4216 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4219 GDS_NEIGHBOURS_init (void)
4221 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
4222 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
4223 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
4224 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
4225 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
4226 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
4227 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
4228 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
4229 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
4230 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
4231 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
4236 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
4237 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
4238 GNUNET_NO, core_handlers);
4239 if (NULL == core_api)
4240 return GNUNET_SYSERR;
4242 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
4243 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS * 4/3, GNUNET_NO);
4244 all_friends_trail_threshold = GNUNET_NO;
4251 * Shutdown neighbours subsystem.
4254 GDS_NEIGHBOURS_done (void)
4256 if (NULL == core_api)
4259 GNUNET_CORE_disconnect (core_api);
4262 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
4263 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
4264 friend_peermap = NULL;
4266 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
4267 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
4268 finger_peermap = NULL;
4270 /* FIXME: Here I have added GNUNET_break(0) as ideally if friend_peermap
4271 is already zero, then we really don't need to cancel it again. If this
4272 condition happens it mean we might have missed some corner case. But we
4273 cancel the task only in handle_core_disconnect. it may happen that this
4274 function is called but not handle_core_disconnect, In that case GNUNET_break(0)
4276 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4279 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4280 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4288 * @return my identity
4290 struct GNUNET_PeerIdentity
4291 GDS_NEIGHBOURS_get_my_id (void)
4297 /* end of gnunet-service-xdht_neighbours.c */