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 * FIXME: for congested peer just define a relative time as #define.
562 * Entry in friend_peermap.
569 struct GNUNET_PeerIdentity id;
572 * Number of trails for which this friend is the first hop.
574 unsigned int trails_count;
577 * Count of outstanding messages for this friend.
579 unsigned int pending_count;
582 * FIXME: Refer to time.c and gnunet_time_lib.h for correct functions.
583 * in handle_dht_p2p_trail_rejection, you should update these values
584 * and whenever you are selecting a friend in select_random_friend()
585 * and find_successor(), you should check congestion_duration = 0,
586 * then proceed else if congestion_duration < your current time then also
588 * struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
589 * struct GNUNET_TIME_Relative congestion_timeout =
590 * congestion_duration = GNUNET_TIME_absolute_add (start,congestion_timeout);
591 * in select_random_friend, GNUNET_TIME_absolute_get_remaning()
593 struct GNUNET_TIME_Absolute congestion_duration;
596 * Head of pending messages to be sent to this friend.
598 struct P2PPendingMessage *head;
601 * Tail of pending messages to be sent to this friend.
603 struct P2PPendingMessage *tail;
606 * Core handle for sending messages to this friend.
608 struct GNUNET_CORE_TransmitHandle *th;
614 * FIXME: make an array of trails. #define number of entries in the array =
615 * number of trails we want to keep. Remove head, tail of trails.
616 * Entry in finger_peermap.
623 struct GNUNET_PeerIdentity finger_identity;
626 * Index in finger peer map
628 unsigned int finger_map_index;
631 * Number of trails to reach to this finger.
633 unsigned int trail_count;
636 * Total number of entries in first trail from (me,finger)
638 unsigned int first_trail_length;
641 * Total number of entries in second trail from (me,finger)
643 unsigned int second_trail_length;
647 * Number of trail of which the first element to reach to this finger is
650 unsigned int first_friend_trails_count;
653 * Head of first trail to reach this finger.
655 struct TrailPeerList *first_trail_head;
658 * Tail of first trail to reach this finger.
660 struct TrailPeerList *first_trail_tail;
663 * Head of second trail to reach this finger.
665 struct TrailPeerList *second_trail_head;
668 * Tail of second trail to reach this finger.
670 struct TrailPeerList *second_trail_tail;
676 * FIXME: The name is not correct.
677 * Used to specify the kind of value stored in the array all_known_peers.
679 enum current_destination_type
689 * Data structure passed to sorting algorithm in find_successor().
694 * 64 bit value of peer identity
699 * FIXME: think of a better name for both the struct and destination_type
700 * Type : MY_ID, FINGER, FINGER, Value
702 enum current_destination_type type;
705 * Pointer to original data structure linked to peer id.
712 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
713 * get our first friend.
715 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
718 * Identity of this peer.
720 static struct GNUNET_PeerIdentity my_identity;
723 * Hash map of all the friends of a peer
725 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
728 * Hash map of all the fingers of a peer
730 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
735 static struct GNUNET_CORE_Handle *core_api;
738 * Finger map index for predecessor entry in finger peermap.
740 #define PREDECESSOR_FINGER_ID 64
743 * Maximum number of trails allowed to go through a friend.
744 * FIXME: Better name, Random value at the moment, need to be adjusted to maintain a balance
745 * between performance and Sybil tolerance.
747 #define TRAIL_THROUGH_FRIEND_THRESHOLD 64
750 * Possible number of different trails to reach to a finger. (Redundant routing)
752 #define TRAIL_COUNT 2
755 * The current finger index that we have want to find trail to.
757 static unsigned int current_search_finger_index;
761 * Iterate over trail and search your index location in the array.
762 * @param trail Trail which contains list of peers.
763 * @param trail_length Number of peers in the trail.
764 * @return Index in the array.
765 * #GNUNET_SYSERR, in case there is no entry which should not be the case ideally.
768 search_my_index (const struct GNUNET_PeerIdentity *trail,
773 while (i < trail_length)
775 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
781 return GNUNET_SYSERR;
785 * Compare two peer identities.
786 * @param p1 Peer identity
787 * @param p2 Peer identity
788 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
791 compare_peer_id (const void *p1, const void *p2)
793 struct Sorting_List *p11;
794 struct Sorting_List *p22;
796 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
797 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
798 p11 = (struct Sorting_List *)p1;
799 p22 = (struct Sorting_List *)p2;
800 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
801 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
807 * Return the predecessor of value in all_known_peers.
808 * @param all_known_peers list of all the peers
809 * @param value value we have to search in the all_known_peers.
810 * @param size Total numbers of elements
811 * @return Predecessor
813 static struct Sorting_List *
814 find_closest_predecessor(struct Sorting_List *all_known_peers, uint64_t value,
823 middle = (first + last)/2;
827 if(all_known_peers[middle].peer_id < value)
831 else if(all_known_peers[middle].peer_id == value)
835 return &all_known_peers[size - 1];
839 return &all_known_peers[middle - 1];
847 middle = (first + last)/2;
854 * Return the successor of value in all_known_peers.
855 * @param all_known_peers list of all the peers
856 * @param value value we have to search in the all_known_peers.
857 * @param size Total numbers of elements
860 static struct Sorting_List *
861 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
870 middle = (first + last)/2;
874 if(all_known_peers[middle].peer_id < value)
878 else if(all_known_peers[middle].peer_id == value)
880 if(middle == (size -1))
882 return &all_known_peers[0];
886 return &all_known_peers[middle+1];
894 middle = (first + last)/2;
901 * Called when core is ready to send a message we asked for
902 * out to the destination.
904 * @param cls the 'struct FriendInfo' of the target friend
905 * @param size number of bytes available in buf
906 * @param buf where the callee should write the message
907 * @return number of bytes written to buf
910 core_transmit_notify (void *cls, size_t size, void *buf)
912 struct FriendInfo *peer = cls;
914 struct P2PPendingMessage *pending;
919 while ((NULL != (pending = peer->head)) &&
920 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
922 peer->pending_count--;
923 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
924 GNUNET_free (pending);
928 /* no messages pending */
934 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
935 GNUNET_CORE_PRIO_BEST_EFFORT,
936 GNUNET_TIME_absolute_get_remaining
937 (pending->timeout), &peer->id,
938 ntohs (pending->msg->size),
939 &core_transmit_notify, peer);
940 GNUNET_break (NULL != peer->th);
944 while ((NULL != (pending = peer->head)) &&
945 (size - off >= (msize = ntohs (pending->msg->size))))
947 GNUNET_STATISTICS_update (GDS_stats,
949 ("# Bytes transmitted to other peers"), msize,
951 memcpy (&cbuf[off], pending->msg, msize);
953 peer->pending_count--;
954 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
955 GNUNET_free (pending);
957 if (peer->head != NULL)
960 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
961 GNUNET_CORE_PRIO_BEST_EFFORT,
962 GNUNET_TIME_absolute_get_remaining
963 (pending->timeout), &peer->id, msize,
964 &core_transmit_notify, peer);
965 GNUNET_break (NULL != peer->th);
973 * Transmit all messages in the friend's message queue.
975 * @param peer message queue to process
978 process_friend_queue (struct FriendInfo *peer)
980 struct P2PPendingMessage *pending;
982 if (NULL == (pending = peer->head))
984 if (NULL != peer->th)
987 GNUNET_STATISTICS_update (GDS_stats,
989 ("# Bytes of bandwidth requested from core"),
990 ntohs (pending->msg->size), GNUNET_NO);
992 /* FIXME: Are we correctly initializing importance and pending. */
994 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
996 GNUNET_TIME_absolute_get_remaining
997 (pending->timeout), &peer->id,
998 ntohs (pending->msg->size),
999 &core_transmit_notify, peer);
1000 GNUNET_break (NULL != peer->th);
1005 * Construct a trail setup message and forward it to a friend.
1006 * @param source_peer Peer which wants to set up the trail to one of its finger.
1007 * @param destination_finger Peer identity closest to this value will be
1008 * @a source_peer's finger.
1009 * @param current_destination next destination corresponding to @a current_source,
1010 * can be either a finger or a friend of @a current_source.
1011 * @param current_source Peer for which @a current_destination is its finger/friend.
1012 * @param target_friend Friend to which this message should be forwarded.
1013 * @param trail_length Numbers of peers in the trail found so far.
1014 * @param trail_peer_list Peers this request has traversed so far
1015 * @param finger_map_index Index in finger peer map
1018 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
1019 uint64_t destination_finger,
1020 struct GNUNET_PeerIdentity *current_destination,
1021 struct GNUNET_PeerIdentity *current_source,
1022 struct FriendInfo *target_friend,
1023 unsigned int trail_length,
1024 const struct GNUNET_PeerIdentity *trail_peer_list,
1025 unsigned int finger_map_index)
1027 struct P2PPendingMessage *pending;
1028 struct PeerTrailSetupMessage *tsm;
1029 struct GNUNET_PeerIdentity *peer_list;
1032 msize = sizeof (struct PeerTrailSetupMessage) +
1033 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1035 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1041 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1043 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1047 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1048 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1049 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1050 pending->msg = &tsm->header;
1051 tsm->header.size = htons (msize);
1052 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
1053 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
1054 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1055 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
1056 memcpy (&(tsm->current_source), current_source, sizeof (struct GNUNET_PeerIdentity));
1057 tsm->trail_length = htonl (trail_length);
1058 tsm->finger_map_index = htonl (finger_map_index);
1060 if (trail_length > 0)
1062 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1063 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1066 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1067 target_friend->pending_count++;
1068 process_friend_queue (target_friend);
1073 * Construct a trail setup result message and forward it to a friend.
1074 * @param destination_peer Peer which will get the trail to one of its finger.
1075 * @param source_finger Peer to which the trail has been setup to.
1076 * @param target_friend Friend to which this message should be forwarded.
1077 * @param trail_length Numbers of peers in the trail.
1078 * @param trail_peer_list Peers which are part of the trail from source to destination.
1079 * @param finger_map_index Index in finger peer map
1082 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destination_peer,
1083 const struct GNUNET_PeerIdentity *source_finger,
1084 struct FriendInfo *target_friend,
1085 unsigned int trail_length,
1086 const struct GNUNET_PeerIdentity *trail_peer_list,
1087 unsigned int finger_map_index)
1089 struct P2PPendingMessage *pending;
1090 struct PeerTrailSetupResultMessage *tsrm;
1091 struct GNUNET_PeerIdentity *peer_list;
1094 msize = sizeof (struct PeerTrailSetupResultMessage) +
1095 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1097 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1103 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1105 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1109 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1110 pending->importance = 0;
1111 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1112 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1113 pending->msg = &tsrm->header;
1114 tsrm->header.size = htons (msize);
1115 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
1116 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1117 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
1118 tsrm->trail_length = htonl (trail_length);
1119 tsrm->finger_map_index = htonl (finger_map_index);
1121 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1122 if (trail_length > 0)
1124 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1126 /* Send the message to chosen friend. */
1127 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1128 target_friend->pending_count++;
1129 process_friend_queue (target_friend);
1134 * Construct a PeerVerifySuccessor message and send it to friend.
1135 * @param source_peer Peer which wants to verify its successor
1136 * @param successor Peer which is our current successor
1137 * @param target_friend Friend to which this message should be forwarded.
1138 * @param trail_peer_list Peer which are part of trail from source to destination
1139 * @param trail_length Number of peers in the trail list.
1141 void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *source_peer,
1142 const struct GNUNET_PeerIdentity *successor,
1143 struct FriendInfo *target_friend,
1144 const struct GNUNET_PeerIdentity *trail_peer_list,
1145 unsigned int trail_length)
1147 struct PeerVerifySuccessorMessage *vsm;
1148 struct P2PPendingMessage *pending;
1149 struct GNUNET_PeerIdentity *peer_list;
1152 msize = sizeof (struct PeerVerifySuccessorMessage) +
1153 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1155 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1161 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1163 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1167 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1168 pending->importance = 0; /* FIXME */
1169 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1170 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1171 pending->msg = &vsm->header;
1172 vsm->header.size = htons (msize);
1173 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1174 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
1175 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1176 vsm->trail_length = htonl (trail_length);
1178 if (trail_length > 0)
1180 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1181 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1184 /* Send the message to chosen friend. */
1185 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1186 target_friend->pending_count++;
1187 process_friend_queue (target_friend);
1193 * Construct a PeerVerifySuccessorResult message and send it to friend.
1194 * @param destination_peer Peer which sent verify successor message
1195 * @param source_successor Peer to which verify successor message was sent.
1196 * @param my_predecessor source_successor's predecessor.
1197 * @param target_friend Friend to which this message should be forwarded.
1198 * @param trail_peer_list Peers which are part of trail from source to destination
1199 * @param trail_length Number of peers in the trail list.
1201 void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *destination_peer,
1202 const struct GNUNET_PeerIdentity *source_successor,
1203 const struct GNUNET_PeerIdentity *my_predecessor,
1204 struct FriendInfo *target_friend,
1205 const struct GNUNET_PeerIdentity *trail_peer_list,
1206 unsigned int trail_length)
1208 struct PeerVerifySuccessorResultMessage *vsmr;
1209 struct P2PPendingMessage *pending;
1210 struct GNUNET_PeerIdentity *peer_list;
1213 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1214 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1216 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1223 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1225 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1229 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1230 pending->importance = 0; /* FIXME */
1231 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1232 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1233 pending->msg = &vsmr->header;
1234 vsmr->header.size = htons (msize);
1235 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1236 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1237 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1238 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1239 vsmr->trail_length = htonl (trail_length);
1240 if (trail_length > 0)
1242 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1243 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1246 /* Send the message to chosen friend. */
1247 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1248 target_friend->pending_count++;
1249 process_friend_queue (target_friend);
1254 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1255 * @param source_peer Peer which is sending notify message to its new successor.
1256 * @param destination_peer Peer which is the new destination.
1257 * @param target_friend Next friend to pass this message to.
1258 * @param peer_list List of peers in the trail to reach to destination_peer.
1259 * @param trail_length Total number of peers in peer list
1262 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1263 const struct GNUNET_PeerIdentity *destination_peer,
1264 struct FriendInfo *target_friend,
1265 const struct GNUNET_PeerIdentity *trail_peer_list,
1266 unsigned int trail_length)
1268 struct PeerNotifyNewSuccessorMessage *nsm;
1269 struct P2PPendingMessage *pending;
1270 struct GNUNET_PeerIdentity *peer_list;
1273 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1274 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1276 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1282 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1284 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1288 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1289 pending->importance = 0; /* FIXME */
1290 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1291 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1292 pending->msg = &nsm->header;
1293 nsm->header.size = htons (msize);
1294 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1295 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1296 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1297 nsm->trail_length = htonl (trail_length);
1298 /* FIXME: Here I am not checking the trail length, as I am assuming that for new
1299 successor our old successor is a part of trail, so trail length > 1. */
1300 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1301 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1303 /* Send the message to chosen friend. */
1304 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1305 target_friend->pending_count++;
1306 process_friend_queue (target_friend);
1310 * Send a trail tear down message
1311 * @param source_peer Source of the trail.
1312 * @param destination_peer Destination of the trail.
1313 * @param discarded_trail Discarded trail from source to destination.
1314 * @param discarded_trail_length Total number of peers in trail_list.
1315 * @pararm target_peer Next peer to forward this message to.
1316 * @param new_first_friend The new first hop in the new trail from source to destination
1320 GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_PeerIdentity *source_peer,
1321 const struct GNUNET_PeerIdentity *destination_peer,
1322 const struct GNUNET_PeerIdentity *discarded_trail,
1323 unsigned int discarded_trail_length,
1324 struct FriendInfo *target_friend,
1325 const struct GNUNET_PeerIdentity *new_first_friend)
1327 struct P2PPendingMessage *pending;
1328 struct PeerTrailTearDownMessage *ttdm;
1329 struct GNUNET_PeerIdentity *peer_list;
1332 msize = sizeof (struct PeerTrailTearDownMessage) +
1333 (discarded_trail_length * sizeof(struct GNUNET_PeerIdentity));
1335 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1341 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1343 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1347 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1348 pending->importance = 0; /* FIXME */
1349 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1350 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1351 pending->msg = &ttdm->header;
1352 ttdm->header.size = htons (msize);
1353 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1354 memcpy (&(ttdm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1355 memcpy (&(ttdm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1356 memcpy (&(ttdm->new_first_friend),new_first_friend, sizeof (struct GNUNET_PeerIdentity));
1357 ttdm->trail_length = htonl (discarded_trail_length);
1359 peer_list = (struct GNUNET_PeerIdentity *) &ttdm[1];
1360 memcpy (peer_list, discarded_trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1362 /* Send the message to chosen friend. */
1363 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1364 target_friend->pending_count++;
1365 process_friend_queue (target_friend);
1370 * FIXME: call GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1371 * In case the friend chosen in select_random_friend() is congested or
1372 * has crossed trail_threshold, then get next friend which is not congested or
1373 * has not crossed trail threshold from friend peermap.
1374 * @param current_index Index in finger peermap chosen randomly
1375 * @param friend_peermap_size Total number of entries in friend peermap.
1376 * @param count Total number of time this function has been called, in case
1377 * count == sizeof(friend_peermap) - 1, it means none of the friends are free.
1378 * @return Friend Friend found.
1379 * NULL in case all the friends are congested or have crossed trail threshold.
1381 static struct FriendInfo *
1382 get_next_friend (unsigned int current_index,
1383 unsigned int friend_peermap_size,
1386 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1387 struct GNUNET_PeerIdentity key_ret;
1388 struct FriendInfo *friend;
1391 current_index = (current_index + 1) % friend_peermap_size;
1392 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1393 while(j < (current_index))
1395 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1403 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1405 if ((friend->trails_count > TRAIL_THROUGH_FRIEND_THRESHOLD) ||
1406 (0 != GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us))
1409 if (count == (friend_peermap_size -1))
1412 return get_next_friend (j,friend_peermap_size,count);
1422 * FIXME: call GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1423 * Randomly choose one of your friends from the friends_peer map
1424 * @return Friend Randomly chosen friend.
1425 * NULL in case friend peermap is empty, or all the friends are either
1426 * congested or have crossed trail threshold.
1428 static struct FriendInfo *
1429 select_random_friend ()
1431 unsigned int current_size;
1432 unsigned int *index;
1434 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1435 struct GNUNET_PeerIdentity key_ret;
1436 struct FriendInfo *friend;
1438 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1439 if (0 == current_size)
1442 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1443 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1447 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1457 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1459 if ((TRAIL_THROUGH_FRIEND_THRESHOLD == friend->trails_count) ||
1460 (0 != GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us))
1462 return get_next_friend (*index, current_size, 1);
1472 * Compute finger_identity to which we want to setup the trail
1473 * @return finger_identity
1476 compute_finger_identity()
1480 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1481 my_id64 = GNUNET_ntohll (my_id64);
1482 return (my_id64 + (unsigned long) pow (2, current_search_finger_index));
1487 * Compute immediate predecessor identity in the network.
1488 * @return peer identity of immediate predecessor.
1491 compute_predecessor_identity()
1495 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1496 my_id64 = GNUNET_ntohll (my_id64);
1497 return (my_id64 -1);
1502 * Ping your successor to verify if it is still your successor or not.
1505 send_verify_successor_message()
1507 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1508 struct GNUNET_PeerIdentity key_ret;
1509 struct FriendInfo *target_friend;
1510 struct GNUNET_PeerIdentity next_hop;
1511 struct GNUNET_PeerIdentity *peer_list;
1512 struct FingerInfo *finger;
1513 unsigned int finger_index;
1516 /* Find the successor from the finger peermap.*/
1517 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1518 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1520 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1521 (const void **)&finger))
1523 if (0 == finger->finger_map_index)
1530 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1532 /* Either you don't have a successor or you are your own successor, then don't
1533 send a successor message. */
1535 (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &(finger->finger_identity))))
1540 if (finger->first_trail_length > 0)
1542 struct TrailPeerList *iterate;
1544 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->first_trail_length);
1545 iterate = finger->first_trail_head;
1547 /* FIXME: SEGMENTATION FAULT. */
1548 while ( i < (finger->first_trail_length))
1550 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1551 iterate = iterate->next;
1554 memcpy (&next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1555 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
1559 /* If trail length = 0, then our successor is our friend. */
1561 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1562 &(finger->finger_identity));
1565 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1566 &(finger->finger_identity),
1569 finger->first_trail_length);
1574 * Choose a random friend and start looking for the trail to reach to
1575 * finger identity through this random friend.
1577 * @param cls closure for this task
1578 * @param tc the context under which the task is running
1581 send_find_finger_trail_message (void *cls,
1582 const struct GNUNET_SCHEDULER_TaskContext *tc)
1584 struct FriendInfo *target_friend;
1585 struct GNUNET_TIME_Relative next_send_time;
1586 uint64_t finger_identity;
1587 unsigned int finger_map_index;
1589 next_send_time.rel_value_us =
1590 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1591 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1592 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1593 find_finger_trail_task =
1594 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1597 target_friend = select_random_friend ();
1598 if (NULL == target_friend) /* Either all the friends are congested or reached trail threshold. */
1603 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
1605 finger_identity = compute_predecessor_identity();
1609 finger_identity = compute_finger_identity();
1612 finger_map_index = current_search_finger_index;
1613 GDS_NEIGHBOURS_send_trail_setup (&my_identity, finger_identity, &(target_friend->id),
1614 &my_identity, target_friend, 0, NULL, finger_map_index);
1619 * FIXME: You need to handle the case of predecessor in case you don't get
1620 * the call from finger table add then you should not send a trail teardown message
1621 * because no one has added that in their trail.
1622 * Scan the trail to check if any of my own friend is part of trail. If yes
1623 * then shortcut the trail, send a trail teardown for the discarded trail,
1624 * update trail list and trail_length.
1625 * @param trail[Out] Current trail to reach to @a finger, will be updated
1626 * in case we compress the trail.
1627 * @param trail_length[Out] Number of peers in @a finger_trail, will be updated
1628 * in case we compress the trail.
1629 * @param finger Finger identity
1632 scan_and_compress_trail (struct GNUNET_PeerIdentity *trail,
1633 unsigned int *trail_length,
1634 const struct GNUNET_PeerIdentity *finger)
1637 struct FriendInfo *target_friend;
1639 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger))
1645 if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger))
1647 int discarded_trail_length = *trail_length;
1648 target_friend = GNUNET_CONTAINER_multipeermap_get(friend_peermap, &trail[0]);
1649 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, trail,
1650 discarded_trail_length, target_friend, finger);
1656 i = *trail_length - 1;
1660 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
1662 /* This element of trail is not my friend. */
1667 /* A --> B(friend 1) --> C(friend 2)--> D ---> E, then we can rewrite the trail as
1669 * Now, we should remove the entry from A's routing table, B's routing table
1670 * and update the entry in C's routing table. Rest everything will be same.
1671 * C's routing table should have source peer as the prev.hop.
1673 struct GNUNET_PeerIdentity *discarded_trail;
1674 struct FriendInfo *target_friend;
1675 int discarded_trail_length;
1678 discarded_trail_length = i - 1;
1679 discarded_trail = GNUNET_malloc (discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1680 memcpy (discarded_trail, trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1681 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
1682 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, discarded_trail,
1683 discarded_trail_length, target_friend,
1686 /* Copy the trail from index i to index trail_length -1 and change
1687 trail length and return */
1688 while (i < *trail_length)
1690 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
1694 *trail_length = j+1;
1703 * FIXME: Is this correct? Here I am using dll_remove and its documentation
1704 * reads something else. Verify. Urgent.
1705 * Free finger and its trail.
1706 * @param finger Finger to be freed.
1709 free_finger (struct FingerInfo *finger)
1711 struct TrailPeerList *peer;
1713 if(finger->first_trail_head != NULL)
1715 while (NULL != (peer = finger->first_trail_head))
1717 GNUNET_CONTAINER_DLL_remove (finger->first_trail_head, finger->first_trail_tail, peer);
1722 if (finger->second_trail_head != NULL)
1724 while (NULL != (peer = finger->second_trail_head))
1726 GNUNET_CONTAINER_DLL_remove (finger->second_trail_head, finger->second_trail_tail, peer);
1729 GNUNET_free (finger);
1735 * FIXME: First check if both the trails are present if yes then send it
1736 * for both of them. Currently sending it only for one trail.
1737 * Send a trail teardown message for the trail of removed finger from the finger
1739 * @param existing_finger Finger to removed from the finger peermap.
1742 void send_trail_teardown (struct FingerInfo *removed_finger)
1744 struct GNUNET_PeerIdentity *peer_list;
1745 struct FriendInfo *friend;
1746 struct TrailPeerList *finger_trail;
1747 int removed_finger_trail_length = removed_finger->first_trail_length;
1750 if (removed_finger->first_trail_length == 0)
1753 finger_trail = removed_finger->first_trail_head;
1754 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(finger_trail->peer));
1755 peer_list = GNUNET_malloc ( removed_finger_trail_length * sizeof (struct GNUNET_PeerIdentity));
1756 while (i < removed_finger->first_trail_length)
1758 memcpy (&peer_list[i], &(finger_trail->peer), sizeof (struct GNUNET_PeerIdentity));
1759 finger_trail = finger_trail->next;
1763 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, &(removed_finger->finger_identity),
1764 peer_list, removed_finger_trail_length, friend,
1765 &(removed_finger->finger_identity));
1770 * FIXME: How do we understand which is the correct trail head?
1771 * Add a new trail to reach an existing finger in finger peermap and increment
1772 * the count of number of trails to reach to this finger.
1773 * @param existing_finger Finger
1774 * @param trail New trail to be added
1775 * @param trail_length Total number of peers in the trail.
1778 void add_new_trail (struct FingerInfo *existing_finger,
1779 struct GNUNET_PeerIdentity *trail,
1780 unsigned int trail_length)
1784 /* FIXME: Here you need to understand which trail is there and which not.
1785 In case first_trail_head != NULL, then that trail is present
1786 so you should add the second one. Need to verify this logic. */
1787 if (existing_finger->first_trail_head != NULL)
1789 while (i < trail_length)
1791 struct TrailPeerList *element;
1792 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1793 element->next = NULL;
1794 element->prev = NULL;
1796 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1797 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1801 else if (existing_finger->second_trail_head != NULL)
1803 while (i < trail_length)
1805 struct TrailPeerList *element;
1806 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1807 element->next = NULL;
1808 element->prev = NULL;
1810 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1811 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->first_trail_head, existing_finger->first_trail_tail, element);
1815 existing_finger->trail_count++;
1820 * In case there are already maximum number of possible trail to reach to a finger,
1821 * then check if the new trail's length is lesser than any of the existing trails.
1822 * If yes then replace that old trail by new trail.
1823 * Note: Here we are taking length as a parameter to choose the best possible trail,
1824 * but there could be other parameters also like - 1. duration of existence of a
1825 * trail - older the better. 2. if the new trail is completely disjoint than the
1826 * other trails, then may be choosing it is better.
1827 * @param existing_finger
1829 * @param trail_length
1830 * @return #GNUNET_YES
1834 void select_and_replace_trail (struct FingerInfo *existing_finger,
1835 struct GNUNET_PeerIdentity *new_trail,
1836 unsigned int new_trail_length)
1838 if (existing_finger->first_trail_length == existing_finger->second_trail_length)
1840 if (new_trail_length < existing_finger->first_trail_length)
1842 /* Randomly choose one of the trail. FIXME:currently I am just replacing the
1844 struct TrailPeerList *peer;
1847 while (NULL != (peer = existing_finger->first_trail_head))
1849 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1853 while (i < new_trail_length)
1855 struct TrailPeerList *element;
1856 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1857 element->next = NULL;
1858 element->prev = NULL;
1860 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1861 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1866 else if ((new_trail_length < existing_finger->second_trail_length) &&
1867 (existing_finger->second_trail_length < existing_finger->first_trail_length))
1869 /* Replace the first trail by the new trail. */
1870 struct TrailPeerList *peer;
1873 while (NULL != (peer = existing_finger->first_trail_head))
1875 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1879 while (i < new_trail_length)
1881 struct TrailPeerList *element;
1882 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1883 element->next = NULL;
1884 element->prev = NULL;
1886 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1887 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1891 else if ( (new_trail_length < existing_finger->first_trail_length) &&
1892 (existing_finger->first_trail_length < existing_finger->second_trail_length))
1894 /* Replace the second trail by the new trail. */
1895 struct TrailPeerList *peer;
1898 while (NULL != (peer = existing_finger->second_trail_head))
1900 GNUNET_CONTAINER_DLL_remove (existing_finger->second_trail_head, existing_finger->second_trail_tail, peer);
1904 while (i < new_trail_length)
1906 struct TrailPeerList *element;
1907 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1908 element->next = NULL;
1909 element->prev = NULL;
1911 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1912 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1920 * FIXME: If we remove a finger which is our friend, then how should we handle it.
1921 * Ideally only in case if the trail_length > 0,we increment the trail count
1922 * of the first friend in the trail to reach to the finger. in case finger is
1923 * our friend then trail length = 0, and hence, we have never incremented the
1924 * trail count associated with that friend.
1925 * Decrement the trail count for the first friend to reach to the finger.
1929 decrement_friend_trail_count (struct FingerInfo *finger)
1931 struct FriendInfo *first_trail_friend;
1932 struct FriendInfo *second_trail_friend;
1934 if(finger->first_trail_head != NULL)
1936 first_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1937 &(finger->first_trail_head->peer));
1938 first_trail_friend->trails_count--;
1941 if(finger->second_trail_head != NULL)
1943 second_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1944 &(finger->second_trail_head->peer));
1945 second_trail_friend->trails_count--;
1949 /* We will not need this variable any more, all_friends_trail_threshold,
1950 FIXME: REMOVE IT. */
1951 if (GNUNET_YES == all_friends_trail_threshold)
1953 all_friends_trail_threshold = GNUNET_NO;
1954 /* FIXME; Here you should reschedule the send_find_finger_task here. or
1962 * Select the closest finger. Used for both predecessor and other fingers..
1963 * But internally calls different functions for predecessor and other fingers.
1964 * @param existing_finger Finger in finger peermap.
1965 * @param new_finger New finger identity
1966 * @param finger_map_index Index in finger peermap where @a existing_finger is stored.
1967 * @return #GNUNET_YES if the new finger is closest.
1968 * #GNUNET_NO if the old finger is closest.
1969 * #GNUNET_SYSERR in case our own identity is closest (should never happen).
1972 int select_finger (struct FingerInfo *existing_finger,
1973 const struct GNUNET_PeerIdentity *new_finger,
1974 unsigned int finger_map_index)
1976 struct Sorting_List peers[3]; /* 3 for existing_finger, new_finger, my_identity */
1977 struct Sorting_List *closest_finger;
1981 for (k = 0; k < 3; k++)
1984 /* Add your entry to peers. */
1985 memcpy (&peers[0], &my_identity, sizeof (uint64_t));
1986 peers[0].type = MY_ID;
1987 peers[0].data = NULL;
1989 /* Add existing_finger identity to the peers. */
1990 memcpy (&peers[1], &(existing_finger->finger_identity), sizeof (uint64_t));
1991 peers[1].type = FINGER;
1992 peers[1].data = existing_finger;
1994 /* Add new_finger identity to the peers. s*/
1995 memcpy (&peers[2], &new_finger, sizeof (uint64_t));
1996 peers[2].type = VALUE;
1997 peers[2].data = NULL;
1999 memcpy (&value, &my_identity, sizeof (uint64_t));
2001 qsort (&peers, 3, sizeof (struct Sorting_List), &compare_peer_id);
2003 if (PREDECESSOR_FINGER_ID == finger_map_index)
2004 closest_finger = find_closest_predecessor (peers, value, 3);
2006 closest_finger = find_closest_successor (peers, value, 3);
2008 if (closest_finger->type == FINGER)
2012 else if (closest_finger->type == VALUE)
2016 else if (closest_finger->type == MY_ID);
2018 return GNUNET_SYSERR;
2024 * FIXME: Do we need to reinsert the existing finger into finger peermap
2025 * in case we add a new trail?
2026 * Choose the closest finger between existing finger and new finger.
2027 * If the new finger is closest and finger_map_index != PREDECESSOR_FINGER_ID,
2028 * then send a trail_teardown message along existing_finger's trail.
2029 * In case both the id's are same, and there is a place to keep more trails, then
2030 * store both of them. In case there is no space to store any more trail, then
2031 * choose the best trail (best - depends on length in current_implementation) and
2032 * discard the others.
2033 * @param existing_finger Existing entry in finger peer map
2034 * @param new_finger New finger
2035 * @param trail Trail to reach to the new finger from me.
2036 * @param trail_length Number of peers in the @a trail
2037 * @param finger_map_index If finger_map_index == PREDECESSOR_FINGER_INDEX,
2038 * then we use a different logic to find the closest
2040 * @return #GNUNET_YES In case we want to store the new entry.
2041 * #GNUNET_NO In case we want the existing entry.
2042 * #GNUNET_SYSERR Error.
2045 int select_closest_finger (struct FingerInfo *existing_finger,
2046 const struct GNUNET_PeerIdentity *new_finger,
2047 struct GNUNET_PeerIdentity *trail,
2048 unsigned int trail_length,
2049 unsigned int finger_map_index)
2051 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), new_finger))
2053 /* Both the new entry and existing entry are same. */
2054 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), &my_identity))
2056 /* If existing_finger is my_identity then trail_length = 0, trail = NULL. In
2057 this case you don't need to check the trails. Exit. */
2060 if (trail_length > 0)
2062 scan_and_compress_trail (trail, &trail_length, new_finger);
2064 if (existing_finger->trail_count < TRAIL_COUNT)
2066 add_new_trail (existing_finger, trail, trail_length);
2071 select_and_replace_trail (existing_finger, trail, trail_length);
2075 else if (GNUNET_YES == select_finger (existing_finger, new_finger, finger_map_index))
2077 /* new_finger is the correct finger. */
2078 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, new_finger))
2080 /* FIXME: Here in case the new finger is my_identity and old entry is not,
2081 should we keep the old entry even if the old entry is not the closest? */
2085 /* Clear all things associated with existing_finger (only if its not a
2087 if (PREDECESSOR_FINGER_ID != finger_map_index)
2088 send_trail_teardown (existing_finger);
2089 decrement_friend_trail_count (existing_finger);
2090 free_finger (existing_finger);
2092 if (trail_length > 0)
2094 scan_and_compress_trail (trail, &trail_length, new_finger);
2098 else if (GNUNET_NO == select_finger (existing_finger, new_finger,finger_map_index))
2100 /* existing_finger is the correct finger. */
2103 return GNUNET_SYSERR;
2108 * Check if there is a predecessor in our finger peer map or not.
2109 * If no, then return GNUNET_YES
2110 * else compare existing predecessor and peer, and find the correct
2112 * @param existing_predecessor
2113 * @param new_predecessor
2114 * @return #GNUNET_YES if new peer is predecessor
2115 * #GNUNET_NO if new peer is not the predecessor.
2118 compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer,
2119 struct GNUNET_PeerIdentity *trail,
2120 unsigned int trail_length)
2122 /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
2123 struct FingerInfo *existing_finger;
2124 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2125 struct FingerInfo *new_finger_entry;
2126 struct FriendInfo *first_friend_trail;
2128 int old_entry_found = GNUNET_NO;
2130 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2131 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2133 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2134 (const void **)&existing_finger))
2136 if (PREDECESSOR_FINGER_ID == existing_finger->finger_map_index)
2138 old_entry_found = GNUNET_YES;
2139 if( GNUNET_NO == select_closest_finger (existing_finger, peer, trail,
2140 trail_length,PREDECESSOR_FINGER_ID))
2147 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2149 /* FIXME: in case predecessor is my friend what ? */
2150 if((GNUNET_NO == old_entry_found)
2151 && (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity,peer)))
2157 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2158 memcpy (&(new_finger_entry->finger_identity), peer, sizeof (struct GNUNET_PeerIdentity));
2159 new_finger_entry->finger_map_index = PREDECESSOR_FINGER_ID;
2160 new_finger_entry->first_trail_length = trail_length;
2161 new_finger_entry->trail_count = 1;
2163 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity,peer)) /* finger_trail is NULL in case I am my own finger identity. */
2165 /* Invert the trail and then add. */
2166 if (trail_length != 0)
2168 i = trail_length - 1;
2171 struct TrailPeerList *element;
2172 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2173 element->next = NULL;
2174 element->prev = NULL;
2176 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
2177 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2180 struct TrailPeerList *element;
2181 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2182 element->next = NULL;
2183 element->prev = NULL;
2184 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
2185 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2187 /* FIXME: Currently we are not handling the second trail. In that case, finger
2188 trail count = min (first_friend, second_friend) trail count. */
2189 /* Incrementing the friend trails count. */
2190 if (trail_length > 0)
2192 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
2193 first_friend_trail->trails_count++;
2197 /* It means the finger is my friend. */
2198 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2199 first_friend_trail->trails_count++;
2201 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2204 GNUNET_assert (GNUNET_OK ==
2205 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2206 &(new_finger_entry->finger_identity),
2208 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
2215 * FIXME: Better name, and make the code more cleaner.
2216 * Compare the new finger entry added and our successor.
2217 * @return #GNUNET_YES if same.
2218 * #GNUNET_NO if not.
2221 compare_new_entry_and_successor (const struct GNUNET_PeerIdentity *new_finger,
2222 int finger_map_index)
2224 int successor_flag = 0;
2225 struct FingerInfo *successor_finger;
2226 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2229 if (PREDECESSOR_FINGER_ID == finger_map_index)
2232 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2233 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2235 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2236 (const void **)&successor_finger))
2238 if (successor_finger->finger_map_index == 0)
2245 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2247 /* Ideally we should never reach here. */
2248 if (successor_flag == 0)
2254 if (0 == GNUNET_CRYPTO_cmp_peer_identity (new_finger, &(successor_finger->finger_identity)))
2262 * Add a new entry in finger table.
2263 * @param finger_identity PeerIdentity of the new finger
2264 * @param finger_trail Trail to reach to the finger, can be NULL in case I am my own
2266 * @param finger_trail_length Number of peers in the trail, can be 0 in case finger
2267 * is a friend or I am my own finger.
2268 * @param finger_map_index Index in finger map.
2271 add_new_entry (const struct GNUNET_PeerIdentity *finger_identity,
2272 struct GNUNET_PeerIdentity *finger_trail,
2273 uint32_t finger_trail_length,
2274 uint32_t finger_map_index)
2276 struct FriendInfo *first_friend_trail;
2277 struct FingerInfo *new_finger_entry;
2280 /* Add a new entry. */
2281 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2282 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
2283 new_finger_entry->finger_map_index = finger_map_index;
2284 new_finger_entry->first_trail_length = finger_trail_length;
2285 new_finger_entry->trail_count = 1;
2287 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity)) /* finger_trail is NULL in case I am my own finger identity. */
2289 /* Incrementing the friend trails count. */
2290 if (finger_trail_length > 0)
2292 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_trail[0]);
2293 first_friend_trail->trails_count++;
2297 /* It means the finger is my friend. */
2298 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger_identity);
2299 first_friend_trail->trails_count++;
2301 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2303 /* Copy the trail. */
2305 while (i < finger_trail_length)
2307 struct TrailPeerList *element;
2308 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2309 element->next = NULL;
2310 element->prev = NULL;
2312 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
2313 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2318 return GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2319 &(new_finger_entry->finger_identity),
2321 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
2325 /**1. Should we check if there is already an entry for same finger id in the finger
2326 * peermap as we are checking for index. I think its too much of code and the use
2327 * of having unique identifier in finger map is only in case of find_successor
2328 * but anyways we will find the correct successor.
2329 * 2. you don't handle the second trail here as in new entry you will have only
2330 * one trail to reach to the finger.
2331 * Add an entry in the finger table. If there is already an existing entry in
2332 * the finger peermap for given finger map index, then choose the closest one.
2333 * In case both the new entry and old entry are same, store both of them. (Redundant
2335 * @param finger_identity
2336 * @param finger_trail
2337 * @param finger_trail_length
2338 * @param finger_map_index
2339 * @return #GNUNET_YES if the new entry is added.
2340 * #GNUNET_NO if the new entry is discarded.
2343 int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
2344 struct GNUNET_PeerIdentity *finger_trail,
2345 uint32_t finger_trail_length,
2346 uint32_t finger_map_index)
2348 struct FingerInfo *existing_finger;
2349 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2351 int old_entry_found = GNUNET_NO;
2352 int new_entry_added = GNUNET_NO;
2354 if (PREDECESSOR_FINGER_ID == finger_map_index)
2356 /* FIXME: Here GNUNET_NO, means that we did not update predecessor . But it
2357 we also need to handle the case that insertion failed in peer map after we decided to add
2359 if( GNUNET_YES == compare_and_update_predecessor (finger_identity, finger_trail, finger_trail_length))
2360 new_entry_added = GNUNET_YES;
2361 goto update_current_search_finger_index;
2364 /* Check if there is already an entry for the finger map index in the finger peer map. */
2365 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2366 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2368 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2369 (const void **)&existing_finger))
2371 if (existing_finger->finger_map_index == finger_map_index)
2373 old_entry_found = GNUNET_YES;
2374 if ( GNUNET_NO == select_closest_finger (existing_finger, finger_identity,
2375 finger_trail, finger_trail_length,
2377 goto update_current_search_finger_index;
2383 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2385 if (GNUNET_NO == old_entry_found)
2387 if (finger_trail_length > 0)
2389 scan_and_compress_trail (finger_trail, &finger_trail_length, finger_identity);
2392 /* SUPU: in this case you get GNUNET_NO, only when insertion fails in the peer map.
2393 so its an error as we already have decided to add the entry into finger peer map. */
2394 if(GNUNET_OK == add_new_entry (finger_identity,finger_trail,finger_trail_length, finger_map_index))
2395 new_entry_added = GNUNET_YES;
2399 update_current_search_finger_index:
2400 if (0 == finger_map_index)
2402 current_search_finger_index = PREDECESSOR_FINGER_ID;
2403 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity))
2404 send_verify_successor_message();
2406 else if (GNUNET_YES == compare_new_entry_and_successor (finger_identity,finger_map_index))
2408 current_search_finger_index = 0;
2412 current_search_finger_index = current_search_finger_index - 1;
2415 return new_entry_added;
2421 * @param all_known_peers
2427 static struct Sorting_List *
2428 get_next_successor (struct Sorting_List *all_known_peers,
2429 unsigned int array_size,
2430 struct FriendInfo *friend,
2433 /* 1. search friend in all_known_peers.
2434 2. get the next peer. if peer == my_identity or peer == value, then go to
2436 3. if friend then again check if threshold crossed or not . If not then return
2437 or else again increment. remember starting index of friend in all_known_peers
2438 and when you reach to it again then return NULL as it means all the friend
2439 are congested or threshold reached.
2446 * Check if the friend is congested or has crossed TRAIL_THRESHOLD. If yes
2447 * then choose the peer next to it in the array. In case number of times this
2448 * function is called is equal to total number of entries in the array then it
2449 * means that none of the friends are busy. But remember in this array you also
2450 * have your own identity, value that you were searching, You should skip those
2451 * and also keep the count = size -2. But if we call in this order is our get/put
2452 * not getting wrong.
2453 * @param all_known_peers
2455 * @param friend Friend to be checked if
2456 * @param key_value To be ignored
2457 * @return #GNUNET_YES
2461 check_friend_threshold_and_congestion (struct Sorting_List *all_known_peers,
2462 unsigned int array_size,
2463 struct FriendInfo *friend,
2466 if (friend->trails_count == TRAIL_THROUGH_FRIEND_THRESHOLD)
2475 * FIXME: In case a friend is either congested or has crossed its trail threshold,
2476 * then don't consider it as next successor, In case of finger if its first
2477 * friend has crossed the threshold then don't consider it. In case no finger
2478 * or friend is found, then return NULL.
2479 * Find closest successor for the value.
2480 * @param value Value for which we are looking for successor
2481 * @param[out] current_destination set to my_identity in case I am the final destination,
2482 * set to friend identity in case friend is final destination,
2483 * set to first friend to reach to finger, in case finger
2484 * is final destination.
2485 * @param[out] current_source set to my_identity.
2486 * @return Peer identity of next hop to send trail setup message to,
2487 * NULL in case all the friends are either congested or have crossed
2488 * their trail threshold.
2490 static struct GNUNET_PeerIdentity *
2491 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
2492 struct GNUNET_PeerIdentity *current_source)
2494 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
2495 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2496 struct GNUNET_PeerIdentity key_ret;
2497 struct FriendInfo *friend;
2498 struct FingerInfo *finger;
2499 unsigned int finger_index;
2500 unsigned int friend_index;
2501 struct Sorting_List *successor;
2505 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
2506 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
2507 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
2510 struct Sorting_List all_known_peers[size];
2513 for (k = 0; k < size; k++)
2514 all_known_peers[k].peer_id = 0;
2516 /* Copy your identity at 0th index in all_known_peers. */
2518 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
2519 all_known_peers[j].type = MY_ID;
2520 all_known_peers[j].data = 0;
2524 all_known_peers[j].peer_id = value;
2525 all_known_peers[j].type = VALUE;
2526 all_known_peers[j].data = 0;
2529 /* Iterate over friend peer map and copy all the elements into array. */
2530 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2531 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
2533 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
2535 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
2536 all_known_peers[j].type = FRIEND;
2537 all_known_peers[j].data = friend;
2543 /* Iterate over finger map and copy all the entries into all_known_peers array. */
2544 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2545 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2547 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
2549 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
2550 all_known_peers[j].type = FINGER;
2551 all_known_peers[j].data = finger;
2556 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2557 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
2560 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
2562 /* search value in all_known_peers array. */
2563 successor = find_closest_successor (all_known_peers, value, size);
2565 if (successor->type == MY_ID)
2567 memcpy (current_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2568 return &my_identity;
2570 else if (successor->type == FRIEND)
2572 struct FriendInfo *target_friend;
2573 target_friend = (struct FriendInfo *)successor->data;
2574 if( GNUNET_YES == check_friend_threshold_and_congestion (all_known_peers, size, target_friend, value))
2576 get_next_successor (all_known_peers, size, friend, value);
2578 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
2579 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2580 return current_destination;
2582 else if (successor->type == FINGER)
2584 struct GNUNET_PeerIdentity *next_hop;
2585 struct FingerInfo *finger;
2586 finger = successor->data;
2587 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2589 if (finger->first_trail_length > 0)
2591 struct TrailPeerList *iterator;
2592 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2593 iterator = finger->first_trail_head;
2594 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2596 else /* This means finger is our friend. */
2597 memcpy (next_hop, &(finger->finger_identity), sizeof(struct GNUNET_PeerIdentity));
2599 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
2600 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2612 * Construct a Put message and send it to target_peer.
2613 * @param key Key for the content
2614 * @param data Content to store
2615 * @param data_size Size of content @a data in bytes
2616 * @param block_type Type of the block
2617 * @param options Routing options
2618 * @param desired_replication_level Desired replication count
2619 * @param expiration_time When does the content expire
2620 * @param current_destination
2621 * @param current_source
2622 * @param target_peer Peer to which this message will be forwarded.
2623 * @param hop_count Number of hops traversed so far.
2624 * @param put_path_length Total number of peers in @a put_path
2625 * @param put_path Number of peers traversed so far
2628 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2629 const void *data, size_t data_size,
2630 enum GNUNET_BLOCK_Type block_type,
2631 enum GNUNET_DHT_RouteOption options,
2632 uint32_t desired_replication_level,
2633 struct GNUNET_TIME_Absolute expiration_time,
2634 struct GNUNET_PeerIdentity current_destination,
2635 struct GNUNET_PeerIdentity current_source,
2636 struct GNUNET_PeerIdentity *target_peer,
2638 uint32_t put_path_length,
2639 struct GNUNET_PeerIdentity *put_path)
2641 struct PeerPutMessage *ppm;
2642 struct P2PPendingMessage *pending;
2643 struct FriendInfo *target_friend;
2644 struct GNUNET_PeerIdentity *pp;
2647 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2648 sizeof (struct PeerPutMessage);
2650 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2652 put_path_length = 0;
2653 msize = data_size + sizeof (struct PeerPutMessage);
2656 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2662 /* This is the first call made from clients file. So, we should search for the
2664 if (NULL == target_peer)
2667 struct GNUNET_PeerIdentity *next_hop;
2669 memcpy (&key_value, key, sizeof (uint64_t));
2670 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2671 if (0 == GNUNET_CRYPTO_cmp_peer_identity(next_hop, &my_identity)) /* I am the destination do datacache_put */
2673 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
2674 block_type, data_size, data);
2678 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2681 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2682 pending->timeout = expiration_time;
2683 ppm = (struct PeerPutMessage *) &pending[1];
2684 pending->msg = &ppm->header;
2685 ppm->header.size = htons (msize);
2686 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
2687 ppm->options = htonl (options);
2688 ppm->block_type = htonl (block_type);
2689 ppm->hop_count = htonl (hop_count + 1);
2690 ppm->desired_replication_level = htonl (desired_replication_level);
2691 ppm->put_path_length = htonl (put_path_length);
2692 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2694 ppm->current_destination = current_destination;
2695 ppm->current_source = current_source;
2697 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2698 if (put_path_length != 0)
2700 memcpy (pp, put_path,
2701 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2703 memcpy (&pp[put_path_length], data, data_size);
2704 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2705 target_friend->pending_count++;
2706 process_friend_queue (target_friend);
2712 * Construct a Get message and send it to target_peer.
2713 * @param key Key for the content
2714 * @param block_type Type of the block
2715 * @param options Routing options
2716 * @param desired_replication_level Desired replication count
2717 * @param expiration_time When does the content expire
2718 * @param current_destination
2719 * @param current_source
2720 * @param target_peer Peer to which this message will be forwarded.
2721 * @param hop_count Number of hops traversed so far.
2722 * @param put_path_length Total number of peers in @a put_path
2723 * @param put_path Number of peers traversed so far
2726 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2727 enum GNUNET_BLOCK_Type block_type,
2728 enum GNUNET_DHT_RouteOption options,
2729 uint32_t desired_replication_level,
2730 struct GNUNET_PeerIdentity current_destination,
2731 struct GNUNET_PeerIdentity current_source,
2732 struct GNUNET_PeerIdentity *target_peer,
2734 uint32_t get_path_length,
2735 struct GNUNET_PeerIdentity *get_path)
2737 struct PeerGetMessage *pgm;
2738 struct P2PPendingMessage *pending;
2739 struct FriendInfo *target_friend;
2740 struct GNUNET_PeerIdentity *gp;
2743 msize = sizeof (struct PeerGetMessage) +
2744 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2746 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2752 if (NULL == target_peer)
2754 /* This is the first call from client file, we need to search for next_hop*/
2755 struct GNUNET_PeerIdentity *next_hop;
2758 memcpy (&key_value, key, sizeof (uint64_t));
2759 // FIXME: endianess of key_value!?
2760 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2761 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity,next_hop)) /* I am the destination do datacache_put */
2763 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2764 NULL, 0, 1, &my_identity, NULL,&my_identity);
2769 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2773 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2774 pending->importance = 0; /* FIXME */
2775 pgm = (struct PeerGetMessage *) &pending[1];
2776 pending->msg = &pgm->header;
2777 pgm->header.size = htons (msize);
2778 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2779 pgm->get_path_length = htonl (get_path_length);
2781 pgm->current_destination = current_destination;
2782 pgm->current_source = current_source;
2783 pgm->hop_count = htonl (hop_count + 1);
2787 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2788 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2790 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2791 target_friend->pending_count++;
2792 process_friend_queue (target_friend);
2797 * Send the get result to requesting client.
2798 * @param expiration When will this result expire?
2799 * @param key Key of the requested data.
2800 * @param put_path_length Number of peers in @a put_path
2801 * @param put_path Path taken to put the data at its stored location.
2802 * @param type Block type
2803 * @param data_size Size of the @a data
2804 * @param data Payload to store
2805 * @param get_path Path taken to reach to the location of the key.
2806 * @param get_path_length Number of peers in @a get_path
2807 * @param next_hop Next peer to forward the message to.
2808 * @param source_peer Peer which has the data for the key.
2811 GDS_NEIGHBOURS_send_get_result (struct GNUNET_TIME_Absolute expiration,
2812 const struct GNUNET_HashCode *key,
2813 unsigned int put_path_length,
2814 const struct GNUNET_PeerIdentity *put_path,
2815 enum GNUNET_BLOCK_Type type, size_t data_size,
2817 struct GNUNET_PeerIdentity *get_path,
2818 unsigned int get_path_length,
2819 struct GNUNET_PeerIdentity *next_hop,
2820 struct GNUNET_PeerIdentity *source_peer)
2822 struct PeerGetResultMessage *get_result;
2823 struct GNUNET_PeerIdentity *get_result_path;
2824 struct GNUNET_PeerIdentity *pp;
2825 struct P2PPendingMessage *pending;
2826 struct FriendInfo *target_friend;
2827 int current_path_index;
2830 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2831 sizeof (struct PeerPutMessage);
2833 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2839 if(get_path_length > 0)
2841 current_path_index = search_my_index(get_path, get_path_length);
2842 if (GNUNET_SYSERR == current_path_index)
2844 /* FIXME: This assertion always fails. FIX IT. */
2849 if (0 == current_path_index)
2851 GDS_CLIENTS_handle_reply (expiration, key, get_path_length, get_path, put_path_length,
2852 put_path, type, data_size, data);
2856 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2857 pending->importance = 0;
2858 get_result = (struct PeerGetResultMessage *)&pending[1];
2859 pending->msg = &get_result->header;
2860 get_result->header.size = htons (msize);
2861 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2862 get_result->key = *key;
2863 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2864 get_result->expiration_time = expiration;
2866 if (get_path_length != 0)
2868 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2869 memcpy (get_result_path, get_path,
2870 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2872 memcpy (&get_result_path[get_path_length], data, data_size);
2874 /* FIXME: Is this correct? */
2875 if (put_path_length != 0)
2877 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2878 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2880 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2881 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2882 target_friend->pending_count++;
2883 process_friend_queue (target_friend);
2888 * Send trail rejection message to the peer which sent me a trail setup message.
2889 * @param source_peer Source peer which wants to set up the trail.
2890 * @param finger_identity Value whose successor will be the finger of @a source_peer.
2891 * @param congested_peer Peer which has send trail rejection message.
2892 * @param next_hop Peer to which this message should be forwarded.
2893 * @param finger_map_index Index in @a source_peer finger peermap.
2894 * @param trail_peer_list Trail followed to reach from @a source_peer to next_hop,
2895 * NULL, in case the @a congested_peer was the first peer
2896 * to which trail setup message was forwarded.
2897 * @param trail_length Number of peers in trail_peer_list.
2900 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity *source_peer,
2901 uint64_t finger_identity,
2902 struct GNUNET_PeerIdentity *congested_peer,
2903 const struct GNUNET_PeerIdentity *next_hop,
2904 unsigned int finger_map_index,
2905 struct GNUNET_PeerIdentity *trail_peer_list,
2906 unsigned int trail_length)
2908 struct PeerTrailRejectionMessage *trail_rejection;
2909 struct GNUNET_PeerIdentity *trail_list;
2910 struct P2PPendingMessage *pending;
2911 struct FriendInfo *target_friend;
2914 msize = trail_length * sizeof(struct GNUNET_PeerIdentity) +
2915 sizeof (struct PeerTrailRejectionMessage);
2917 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2923 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2924 pending->importance = 0;
2925 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2926 trail_rejection = (struct PeerTrailRejectionMessage *) &pending[1];
2927 pending->msg = &trail_rejection->header;
2928 trail_rejection->header.size = htons (msize);
2929 trail_rejection->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
2930 memcpy (&(trail_rejection->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2931 memcpy (&(trail_rejection->congested_peer), congested_peer, sizeof (struct GNUNET_PeerIdentity));
2932 memcpy (&(trail_rejection->finger_identity_value), &finger_identity, sizeof (uint64_t));
2933 trail_rejection->finger_map_index = htonl(finger_map_index);
2934 trail_rejection->trail_length = htonl (trail_length);
2936 if (trail_length != 0)
2938 trail_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2939 memcpy (trail_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2942 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2943 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2944 target_friend->pending_count++;
2945 process_friend_queue (target_friend);
2950 * Core handler for P2P put messages.
2951 * @param cls closure
2952 * @param peer sender of the request
2953 * @param message message
2954 * @return #GNUNET_OK to keep the connection open,
2955 * #GNUNET_SYSERR to close it (signal serious error)
2958 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2959 const struct GNUNET_MessageHeader *message)
2961 struct PeerPutMessage *put;
2962 struct GNUNET_PeerIdentity *put_path;
2963 struct GNUNET_HashCode test_key;
2964 enum GNUNET_DHT_RouteOption options;
2965 struct GNUNET_PeerIdentity current_destination;
2966 struct GNUNET_PeerIdentity current_source;
2967 struct GNUNET_PeerIdentity *next_hop;
2971 size_t payload_size;
2974 msize = ntohs (message->size);
2975 if (msize < sizeof (struct PeerPutMessage))
2977 GNUNET_break_op (0);
2981 put = (struct PeerPutMessage *) message;
2982 putlen = ntohl (put->put_path_length);
2985 sizeof (struct PeerPutMessage) +
2986 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2988 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2990 GNUNET_break_op (0);
2994 current_destination = put->current_destination;
2995 current_source = put->current_source;
2996 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2997 payload = &put_path[putlen];
2998 options = ntohl (put->options);
2999 payload_size = msize - (sizeof (struct PeerPutMessage) +
3000 putlen * sizeof (struct GNUNET_PeerIdentity));
3002 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3003 payload, payload_size, &test_key))
3006 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3008 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3009 GNUNET_break_op (0);
3010 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3011 "PUT with key `%s' for block with key %s\n",
3012 put_s, GNUNET_h2s_full (&test_key));
3013 GNUNET_free (put_s);
3018 GNUNET_break_op (0);
3021 /* cannot verify, good luck */
3025 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3027 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3028 ntohl (put->block_type),
3030 NULL, 0, /* bloom filer */
3031 NULL, 0, /* xquery */
3032 payload, payload_size))
3034 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3035 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3038 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3039 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3040 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3041 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3042 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3043 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3045 GNUNET_break_op (0);
3050 struct GNUNET_PeerIdentity pp[putlen + 1];
3051 /* extend 'put path' by sender */
3052 /* FIXME: Check what are we doing here? */
3053 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3055 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3062 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3063 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3065 GDS_ROUTING_print();
3066 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3067 if (next_hop == NULL)
3069 /* refer to handle_dht_p2p_trail_setup. */
3074 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
3077 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop)) /* I am the final destination */
3079 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3080 &(put->key),putlen, pp, ntohl (put->block_type),
3081 payload_size, payload);
3086 GDS_CLIENTS_process_put (options,
3087 ntohl (put->block_type),
3088 ntohl (put->hop_count),
3089 ntohl (put->desired_replication_level),
3091 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3095 GDS_NEIGHBOURS_send_put (&put->key, payload, payload_size,
3096 ntohl (put->block_type),ntohl (put->options),
3097 ntohl (put->desired_replication_level),
3098 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3099 current_destination, current_source, next_hop,
3100 ntohl (put->hop_count), putlen, pp);
3104 return GNUNET_SYSERR;
3109 * Core handler for p2p get requests.
3111 * @param cls closure
3112 * @param peer sender of the request
3113 * @param message message
3114 * @return #GNUNET_OK to keep the connection open,
3115 * #GNUNET_SYSERR to close it (signal serious error)
3118 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3119 const struct GNUNET_MessageHeader *message)
3121 struct PeerGetMessage *get;
3122 struct GNUNET_PeerIdentity *get_path;
3123 struct GNUNET_PeerIdentity current_destination;
3124 struct GNUNET_PeerIdentity current_source;
3125 struct GNUNET_PeerIdentity *next_hop;
3126 uint32_t get_length;
3130 msize = ntohs (message->size);
3131 if (msize < sizeof (struct PeerGetMessage))
3133 GNUNET_break_op (0);
3137 get = (struct PeerGetMessage *)message;
3138 get_length = ntohl (get->get_path_length);
3139 get_path = (struct GNUNET_PeerIdentity *)&get[1];
3140 current_destination = get->current_destination;
3141 current_source = get->current_source;
3144 sizeof (struct PeerGetMessage) +
3145 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3147 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3149 GNUNET_break_op (0);
3153 /* Add sender to get path */
3154 struct GNUNET_PeerIdentity gp[get_length + 1];
3155 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3156 gp[get_length + 1] = *peer;
3157 get_length = get_length + 1;
3159 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3160 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3162 GDS_ROUTING_print();
3163 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3164 if (next_hop == NULL)
3166 /* refer to handle_dht_p2p_trail_setup. */
3171 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
3174 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop))
3176 /* I am the destination.*/
3177 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3178 struct GNUNET_PeerIdentity next_hop;
3180 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3181 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3182 get_length = get_length + 1;
3183 memcpy (&next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
3184 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3185 get_length, final_get_path,&next_hop, &my_identity);
3191 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3192 get->desired_replication_level,current_destination,
3193 current_source, next_hop, 0,
3196 return GNUNET_SYSERR;
3201 * FIXME: In case of trail, we don't have source and destination part of the trail,
3202 * Check if we follow the same in case of get/put/get_result. Also, in case of
3203 * put should we do a routing table add.
3204 * Core handler for get result
3205 * @param cls closure
3206 * @param peer sender of the request
3207 * @param message message
3208 * @return #GNUNET_OK to keep the connection open,
3209 * #GNUNET_SYSERR to close it (signal serious error)
3212 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3213 const struct GNUNET_MessageHeader *message)
3215 struct PeerGetResultMessage *get_result;
3216 struct GNUNET_PeerIdentity *get_path;
3217 struct GNUNET_PeerIdentity *put_path;
3219 size_t payload_size;
3221 unsigned int getlen;
3222 unsigned int putlen;
3223 int current_path_index;
3225 msize = ntohs (message->size);
3226 if (msize < sizeof (struct PeerGetResultMessage))
3228 GNUNET_break_op (0);
3232 get_result = (struct PeerGetResultMessage *)message;
3233 getlen = ntohl (get_result->get_path_length);
3234 putlen = ntohl (get_result->put_path_length);
3237 sizeof (struct PeerGetResultMessage) +
3238 getlen * sizeof (struct GNUNET_PeerIdentity) +
3239 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3241 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3243 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3245 GNUNET_break_op (0);
3249 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
3250 payload = &get_path[getlen];
3251 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3252 getlen * sizeof (struct GNUNET_PeerIdentity));
3253 /* FIXME: Check if its correct or not. */
3256 put_path = &get_path[1];
3260 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3262 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3263 getlen, get_path, putlen,
3264 put_path, get_result->type, payload_size, payload);
3269 struct GNUNET_PeerIdentity *next_hop;
3270 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3271 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3272 current_path_index = search_my_index (get_path, getlen);
3273 /* FIXME: First check if you are adding yourself to the get path or not.
3274 if yes then don't check if current_path_index == 0, if not then check
3275 and next_hop == source_peer. */
3276 memcpy (next_hop, &get_path[current_path_index - 1], sizeof (struct GNUNET_PeerIdentity));
3278 GDS_NEIGHBOURS_send_get_result (get_result->expiration_time, &(get_result->key),
3280 get_result->type, payload_size,payload,
3282 next_hop, &(get_result->source_peer));
3285 return GNUNET_SYSERR;
3290 * FIXME: Is all trails threshold and routing table has some link.
3291 * Core handle for PeerTrailSetupMessage.
3292 * @param cls closure
3293 * @param message message
3294 * @param peer peer identity this notification is about
3295 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3298 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3299 const struct GNUNET_MessageHeader *message)
3301 const struct PeerTrailSetupMessage *trail_setup;
3302 struct GNUNET_PeerIdentity current_destination;
3303 struct GNUNET_PeerIdentity current_source;
3304 struct GNUNET_PeerIdentity source;
3305 struct GNUNET_PeerIdentity *next_hop;
3306 struct GNUNET_PeerIdentity next_peer;
3307 struct GNUNET_PeerIdentity *trail_peer_list;
3308 struct FriendInfo *target_friend;
3309 uint64_t destination_finger_value;
3310 uint32_t trail_length;
3311 uint32_t finger_map_index;
3314 msize = ntohs (message->size);
3315 if (msize < sizeof (struct PeerTrailSetupMessage))
3317 GNUNET_break_op (0);
3321 trail_setup = (const struct PeerTrailSetupMessage *) message;
3322 trail_length = ntohl (trail_setup->trail_length);
3324 if ((msize < sizeof (struct PeerTrailSetupMessage) +
3325 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3327 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3329 GNUNET_break_op (0);
3333 if (trail_length > 0)
3334 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
3335 memcpy (¤t_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity));
3336 memcpy (¤t_source,&(trail_setup->current_source), sizeof (struct GNUNET_PeerIdentity));
3337 memcpy (&source, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity));
3338 finger_map_index = ntohl (trail_setup->finger_map_index);
3339 destination_finger_value = ntohl (trail_setup->destination_finger);
3342 /* FIXME: Here we need to check 3 things
3343 * 1. if my routing table is all full
3344 * 2. if all my friends are congested
3345 * 3. if trail threshold of my friends have crossed.
3346 * In all these cases we need to send back trail rejection message. */
3347 if ( (GNUNET_YES == all_friends_trail_threshold)
3348 || (GNUNET_YES == GDS_ROUTING_check_threshold()))
3350 /* If all the friends have reached their trail threshold or if there is no
3351 more space in routing table to store more trails, then reject. */
3352 GDS_NEIGHBOURS_send_trail_rejection (&source, destination_finger_value, &my_identity,
3353 peer,finger_map_index, trail_peer_list,trail_length);
3359 /* Check if you are current_destination or not. */
3360 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3362 GDS_ROUTING_print();
3363 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3364 /* OPTIMIZATION: Choose a peer from find_successor and choose the closest one.
3365 In case the closest one is from routing table and it is NULL, then update
3367 if (next_hop == NULL)
3369 /* FIXME: Should we inform the peer before us. If not then it may continue
3370 to send us request. But in case we want to inform we need to have a
3371 different kind of message. */
3372 GNUNET_STATISTICS_update (GDS_stats,
3373 gettext_noop ("# Trail not found in routing table during"
3374 "trail setup request, packet dropped."),
3381 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
3384 if (NULL == next_hop)
3386 return GNUNET_SYSERR;
3388 else if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
3390 if (trail_length == 0)
3392 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
3396 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3399 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3400 /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
3401 if (PREDECESSOR_FINGER_ID != finger_map_index)
3403 /* FIXME: Is this correct assumption? A peer which think I am its predecessor,
3404 then I am not its predecessor. */
3405 compare_and_update_predecessor (&source, trail_peer_list, trail_length );
3407 GDS_NEIGHBOURS_send_trail_setup_result (&source,
3409 target_friend, trail_length,
3416 /* Now add yourself to the trail. */
3417 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3418 if (trail_length != 0)
3419 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3420 peer_list[trail_length] = my_identity;
3422 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3423 GDS_NEIGHBOURS_send_trail_setup (&source,
3424 destination_finger_value,
3425 ¤t_destination, ¤t_source,
3426 target_friend, trail_length, peer_list,
3434 * Core handle for p2p trail construction result messages.
3436 * @param message message
3437 * @param peer peer identity this notification is about
3438 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3441 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3442 const struct GNUNET_MessageHeader *message)
3444 const struct PeerTrailSetupResultMessage *trail_result;
3445 struct GNUNET_PeerIdentity *trail_peer_list;
3446 uint32_t trail_length;
3447 uint32_t finger_map_index;
3450 msize = ntohs (message->size);
3451 if (msize < sizeof (struct PeerTrailSetupResultMessage))
3453 GNUNET_break_op (0);
3457 trail_result = (const struct PeerTrailSetupResultMessage *) message;
3458 trail_length = ntohl (trail_result->trail_length);
3461 sizeof (struct PeerTrailSetupResultMessage) +
3462 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3464 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3466 GNUNET_break_op (0);
3470 finger_map_index = htonl (trail_result->finger_map_index);
3471 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
3473 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3476 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
3482 struct GNUNET_PeerIdentity next_hop;
3483 struct FriendInfo *target_friend;
3486 my_index = search_my_index (trail_peer_list, trail_length);
3487 if (my_index == GNUNET_SYSERR)
3488 return GNUNET_SYSERR;
3492 next_hop = trail_result->destination_peer;
3495 next_hop = trail_peer_list[my_index - 1];
3497 /* Finger table of destination peer will not contain any trail for the case
3498 * where destination peer is its own finger identity.*/
3499 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3500 &(trail_result->finger_identity))))
3502 /* FIXME: First call GDS_ROUTING_search, only if it returns NULL, call
3503 GDS_ROUTING_add. But in case we have same 3 fields but 1 different next hop
3504 then we should add the entry but in current implementation of GDS_ROUTNG_search
3505 we don't handle it. */
3506 GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
3508 GDS_ROUTING_print();
3511 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3512 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
3513 &(trail_result->finger_identity),
3514 target_friend, trail_length,
3519 return GNUNET_SYSERR;
3524 * Get my current predecessor from the finger peer map
3525 * @return Current predecessor.
3527 static struct FingerInfo *
3530 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
3531 struct GNUNET_PeerIdentity key_ret;
3532 unsigned int finger_index;
3533 struct FingerInfo *my_predecessor;
3536 /* Iterate over finger peer map and extract your predecessor. */
3537 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
3538 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
3540 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
3541 (finger_iter,&key_ret,(const void **)&my_predecessor))
3543 if(PREDECESSOR_FINGER_ID == my_predecessor->finger_map_index)
3550 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
3555 return my_predecessor;
3560 * Core handle for p2p verify successor messages.
3561 * @param cls closure
3562 * @param message message
3563 * @param peer peer identity this notification is about
3564 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3567 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3568 const struct GNUNET_MessageHeader *message)
3570 const struct PeerVerifySuccessorMessage *vsm;
3571 const struct GNUNET_PeerIdentity *trail_peer_list;
3572 struct GNUNET_PeerIdentity source_peer;
3573 struct GNUNET_PeerIdentity next_hop;
3574 struct FriendInfo *target_friend;
3576 uint32_t trail_length;
3578 msize = ntohs (message->size);
3579 if (msize < sizeof (struct PeerVerifySuccessorMessage))
3581 GNUNET_break_op (0);
3585 vsm = (struct PeerVerifySuccessorMessage *) message;
3586 trail_length = ntohl (vsm->trail_length);
3588 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
3589 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3590 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3592 GNUNET_break_op (0);
3595 if (trail_length > 0)
3596 trail_peer_list = (const struct GNUNET_PeerIdentity *)&vsm[1];
3597 memcpy (&source_peer, &(vsm->source_peer), sizeof(struct GNUNET_PeerIdentity));
3599 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
3601 struct FingerInfo *my_predecessor;
3602 if (trail_length == 0)
3604 /* SUPU: If I am friend of source_peer, then trail_length == 0. */
3605 memcpy (&next_hop, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3609 /* SUPU: Here I am the final destination successor, and trail does not contain
3610 destination. So, the next hop is the last element in the trail. */
3611 memcpy (&next_hop, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3613 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3615 my_predecessor = get_predecessor();
3616 if (NULL == my_predecessor)
3619 return GNUNET_SYSERR;
3622 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3623 &(my_predecessor->finger_identity))))
3625 /* Source peer and my predecessor, both are same. */
3626 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3628 &(my_predecessor->finger_identity),
3635 struct GNUNET_PeerIdentity *new_successor_trail;
3636 struct TrailPeerList *iterator;
3637 int new_trail_length;
3640 new_trail_length = trail_length + my_predecessor->first_trail_length + 1;
3641 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
3642 if (trail_length > 0)
3643 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
3645 memcpy (&new_successor_trail[trail_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3647 if (my_predecessor->first_trail_length)
3649 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
3650 iterator = my_predecessor->first_trail_head;
3651 i = trail_length + 1;
3652 while (i < new_trail_length)
3654 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
3655 iterator = iterator->next;
3659 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3661 &(my_predecessor->finger_identity),
3663 new_successor_trail,
3672 if (trail_length == 0)
3675 return GNUNET_SYSERR;
3678 my_index = search_my_index (trail_peer_list, trail_length);
3679 if (my_index == GNUNET_SYSERR)
3682 return GNUNET_SYSERR;
3684 if (my_index == (trail_length - 1))
3686 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(vsm->successor));
3690 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3691 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3694 GDS_NEIGHBOURS_send_verify_successor (&(vsm->source_peer), &(vsm->successor),target_friend,
3695 trail_peer_list, trail_length);
3697 return GNUNET_SYSERR;
3701 /**FIXME: in case we have a new successor do we need to update the entries in
3702 * routing table to change the destination of the message from old successor
3703 * to new successor or when the old successor sends the message the I am not
3704 * your successor then it sends a trail teardown message across the old trail.
3705 * Need to decide on a strategy.
3706 * Core handle for p2p verify successor result messages.
3707 * @param cls closure
3708 * @param message message
3709 * @param peer peer identity this notification is about
3710 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3713 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3714 const struct GNUNET_MessageHeader *message)
3716 const struct PeerVerifySuccessorResultMessage *vsrm;
3717 struct GNUNET_PeerIdentity *trail_peer_list;
3718 struct GNUNET_PeerIdentity next_hop;
3719 struct FriendInfo *target_friend;
3721 uint32_t trail_length;
3723 msize = ntohs (message->size);
3724 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
3726 GNUNET_break_op (0);
3729 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
3730 trail_length = ntohl (vsrm->trail_length);
3733 sizeof (struct PeerVerifySuccessorResultMessage) +
3734 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3736 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3738 GNUNET_break_op (0);
3741 /* FIXME: URGENT: What happens when trail length = 0. */
3743 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
3745 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity))))
3747 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
3749 /* FIXME: Here we have got a new successor. But it may happen that our logic
3750 * says that this is not correct successor. so in finger table add it
3751 * failed to update the successor and we are still sending a notify
3752 * new successor. Here trail_length will be atleast 1, in case we have a new
3753 * successor because in that case our old successor is part of trail.
3754 * Could it be possible that our identity and my_predecessor is same. Check it. */
3755 if (GNUNET_YES == finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0))
3757 memcpy (&next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
3758 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3759 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
3760 target_friend, trail_peer_list,
3768 return GNUNET_SYSERR;
3776 my_index = search_my_index (trail_peer_list, trail_length);
3777 if (GNUNET_SYSERR == my_index)
3780 return GNUNET_SYSERR;
3785 /* Source is not part of trail, so if I am the last one then my index
3787 memcpy (&next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3791 memcpy (&next_hop, &trail_peer_list[my_index-1], sizeof (struct GNUNET_PeerIdentity));
3794 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3795 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
3796 &(vsrm->source_successor),
3797 &(vsrm->my_predecessor),
3803 return GNUNET_SYSERR;
3808 * Core handle for p2p notify new successor messages.
3809 * @param cls closure
3810 * @param message message
3811 * @param peer peer identity this notification is about
3812 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3815 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3816 const struct GNUNET_MessageHeader *message)
3818 const struct PeerNotifyNewSuccessorMessage *nsm;
3819 struct GNUNET_PeerIdentity *trail_peer_list;
3821 uint32_t trail_length;
3823 msize = ntohs (message->size);
3824 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
3826 GNUNET_break_op (0);
3829 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
3830 trail_length = ntohl (nsm->trail_length);
3832 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3833 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3835 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3837 GNUNET_break_op (0);
3840 if( trail_length > 1)
3842 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
3845 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), &my_identity)))
3847 /* I am the new successor. */
3848 struct GNUNET_PeerIdentity *new_predecessor;
3849 new_predecessor = GNUNET_new (struct GNUNET_PeerIdentity);
3850 memcpy (new_predecessor, &(nsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
3851 if (GNUNET_NO == compare_and_update_predecessor (new_predecessor, trail_peer_list,
3854 /* Someone claims to be my predecessor but its not closest predecessor
3857 return GNUNET_SYSERR;
3863 struct FriendInfo *target_friend;
3864 struct GNUNET_PeerIdentity next_hop;
3867 if (trail_length == 0)
3868 return GNUNET_SYSERR;
3870 my_index = search_my_index (trail_peer_list, trail_length);
3871 if (GNUNET_SYSERR == my_index)
3873 /* FIXME: happend once */
3875 return GNUNET_SYSERR;
3878 if (my_index == (trail_length - 1))
3880 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(nsm->destination_peer));
3884 memcpy (&next_hop, &trail_peer_list[my_index+1], sizeof (struct GNUNET_PeerIdentity));
3885 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3887 /* FIXME: Should we update the entries in routing table? */
3888 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
3889 &(nsm->destination_peer),
3890 target_friend, trail_peer_list,
3894 return GNUNET_SYSERR;
3899 * FIXME; Should we call select_random_friend from here in case I am the source
3900 * of the message or should I just return and in next iteration by default
3901 * we will call select random friend from send_find_finger_trail. But in that
3902 * case we should maintain a list of congested peer which failed to setup the
3903 * trail. and then in select random friend we should ignore them. this list
3904 * should have an expiration time and we should garbage collect it periodically.
3905 * Core handler for P2P trail rejection message
3906 * @param cls closure
3907 * @param message message
3908 * @param peer peer identity this notification is about
3909 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3912 int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3913 const struct GNUNET_MessageHeader *message)
3915 /* Here you have recevied the message it means that the peer next to you have
3916 failed to setup the trail to the finger identity value. now you should call
3917 find_successor and make sure that you don't choose the peer as next hop
3918 in order to do so, you need to pass a new parameter to find successor,
3919 congested peer - a peer which you should ignore. once you have found this
3920 peer then just send a trail setup message to that peer. In case you are
3921 also congested then remove yourself from the trail as this message
3922 reached to as you are part of the trail. and then send the message to
3923 element before you. Ideally you should be the last element in the trail as
3924 all the the elements before you have rejected you. In case you are source,
3925 then you should call select_random_Friend(congested_peer). in case you don't
3926 find any peer because congested peer then set flag that all friends are busy
3928 const struct PeerTrailRejectionMessage *trail_rejection;
3929 struct GNUNET_PeerIdentity *trail_peer_list;
3930 struct GNUNET_PeerIdentity source_peer;
3931 struct GNUNET_PeerIdentity congested_peer;
3932 struct FriendInfo *target_friend;
3933 struct GNUNET_PeerIdentity next_peer;
3934 struct GNUNET_PeerIdentity *next_hop;
3935 struct GNUNET_PeerIdentity current_source;
3936 struct GNUNET_PeerIdentity current_destination;
3938 uint32_t trail_length;
3939 uint32_t finger_map_index;
3940 uint64_t destination_finger_value;
3942 msize = ntohs (message->size);
3943 if (msize < sizeof (struct PeerTrailRejectionMessage))
3945 GNUNET_break_op (0);
3949 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3950 trail_length = ntohl (trail_rejection->trail_length);
3952 if ((msize < sizeof (struct PeerTrailRejectionMessage) +
3953 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3955 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3957 GNUNET_break_op (0);
3961 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3962 finger_map_index = ntohl (trail_rejection->finger_map_index);
3963 memcpy (&source_peer, &(trail_rejection->source_peer), sizeof(struct GNUNET_PeerIdentity));
3964 memcpy (&destination_finger_value, &(trail_rejection->finger_identity_value), sizeof (uint64_t));
3965 memcpy (&congested_peer, &(trail_rejection->congested_peer), sizeof (struct GNUNET_PeerIdentity));
3967 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source_peer)))
3969 /* I am the source of original trail setup message. Do nothing and exit. */
3970 /* In current implementation, when we don't get the result of a trail setup,
3971 then no entry is added to finger table and hence, by default a trail setup for
3972 the same finger map index is sent. so we don't need to send it here. */
3976 if(GDS_ROUTING_check_threshold())
3978 /* My routing state size has crossed the threshold, I can not be part of any more
3980 struct GNUNET_PeerIdentity *new_trail;
3982 if (trail_length == 1)
3984 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3988 /* FIXME: Here if I got the trail rejection message then I am the last element
3989 in the trail. So, I should choose trail_length-2.*/
3990 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
3993 /* Remove myself from the trail. */
3994 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3995 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3997 /* No more trails possible through me. send a trail rejection message to next hop. */
3998 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
3999 &next_peer,finger_map_index, new_trail,trail_length - 1);
4003 memcpy (¤t_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
4004 memcpy (¤t_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
4005 /* FIXME: After adding a new field in struct FriendInfo congested, then call
4006 find successor then it will never consider that friend by default. */
4007 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
4009 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, ¤t_destination))) /* This means I am the final destination */
4011 if (trail_length == 1)
4013 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
4017 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
4020 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
4021 compare_and_update_predecessor (&source_peer, trail_peer_list, trail_length);
4023 GDS_NEIGHBOURS_send_trail_setup_result (&source_peer,
4025 target_friend, trail_length,
4030 else if (NULL == next_hop)
4032 /* No peer found. Send a trail rejection message to previous peer in the trail. */
4034 struct GNUNET_PeerIdentity *new_trail;
4036 if (trail_length == 1)
4038 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
4042 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
4045 /* Remove myself from the trail. */
4046 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
4047 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
4049 /* No more trails possible through me. send a trail rejection message to next hop. */
4050 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
4051 &next_peer,finger_map_index, new_trail,trail_length - 1);
4056 /* Now add yourself to the trail. */
4057 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4058 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
4059 peer_list[trail_length] = my_identity;
4062 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4063 GDS_NEIGHBOURS_send_trail_setup (&source_peer,
4064 destination_finger_value,
4065 ¤t_destination, ¤t_source,
4066 target_friend, trail_length, peer_list,
4070 return GNUNET_SYSERR;
4074 /* Core handle for p2p trail tear down messages.
4075 * @param cls closure
4076 * @param message message
4077 * @param peer peer identity this notification is about
4078 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4081 int handle_dht_p2p_trail_teardown(void *cls, const struct GNUNET_PeerIdentity *peer,
4082 const struct GNUNET_MessageHeader *message)
4084 struct PeerTrailTearDownMessage *trail_teardown;
4085 struct GNUNET_PeerIdentity *discarded_trail;
4086 struct GNUNET_PeerIdentity next_hop;
4087 struct FriendInfo *target_friend;
4088 uint32_t discarded_trail_length;
4092 msize = ntohs (message->size);
4093 if (msize < sizeof (struct PeerTrailTearDownMessage))
4095 GNUNET_break_op (0);
4099 trail_teardown = (struct PeerTrailTearDownMessage *) message;
4100 discarded_trail_length = ntohl (trail_teardown->trail_length);
4102 if ((msize < sizeof (struct PeerTrailTearDownMessage) +
4103 discarded_trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
4104 (discarded_trail_length >
4105 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
4107 GNUNET_break_op (0);
4111 discarded_trail = (struct GNUNET_PeerIdentity *) &trail_teardown[1];
4113 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->new_first_friend),
4116 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer),
4124 * I am the new first hop in the trail to reach from source to destination.
4125 Update the trail in routing table with prev_hop == source peer. */
4126 return GDS_ROUTING_trail_update (&(trail_teardown->source_peer),
4127 &(trail_teardown->destination_peer), peer);
4132 /* This should always be the case. */
4133 if (discarded_trail_length > 0)
4135 my_index = search_my_index (discarded_trail, discarded_trail_length);
4136 if(GNUNET_SYSERR == my_index)
4137 return GNUNET_SYSERR;
4142 return GNUNET_SYSERR;
4144 GDS_ROUTING_print();
4145 if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
4146 &(trail_teardown->destination_peer),peer))
4148 /* Here we get GNUNET_NO, only if there is no matching entry found in routing
4154 /* In case we got this message when we removed an entry from finger table,
4155 then we need to send the message to destination. */
4156 if (my_index != (discarded_trail_length - 1))
4157 memcpy (&next_hop, &discarded_trail[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
4159 memcpy (&next_hop, &(trail_teardown->destination_peer), sizeof (struct GNUNET_PeerIdentity));
4160 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4162 GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer),
4163 &(trail_teardown->destination_peer),
4164 discarded_trail, discarded_trail_length,
4165 target_friend, &(trail_teardown->new_first_friend));
4168 return GNUNET_SYSERR;
4173 * FIXME: always gives segmentation fault.
4174 * Iterate over finger_peermap, and remove entries with peer as the first element
4176 * @param cls closure
4177 * @param key current public key
4178 * @param value value in the hash map
4179 * @return #GNUNET_YES if we should continue to
4181 * #GNUNET_NO if not.
4184 remove_matching_finger (void *cls,
4185 const struct GNUNET_PeerIdentity *key,
4188 struct FingerInfo *remove_finger = value;
4189 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
4191 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->first_trail_head->peer, disconnected_peer)
4192 || (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_finger->finger_identity), disconnected_peer)))
4194 GNUNET_assert (GNUNET_YES ==
4195 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
4198 free_finger (remove_finger);
4206 * Method called whenever a peer disconnects.
4208 * @param cls closure
4209 * @param peer peer identity this notification is about
4212 handle_core_disconnect (void *cls,
4213 const struct GNUNET_PeerIdentity *peer)
4215 struct FriendInfo *remove_friend;
4217 /* Check for self message. */
4218 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
4221 /* Search for peer to remove in your friend_peermap. */
4223 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4225 if (NULL == remove_friend)
4231 /* Remove fingers for which this peer is the first element in the trail or if
4232 * the friend is a finger. */
4233 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap,
4234 &remove_matching_finger, (void *)peer);
4236 /* Remove routing trails of which this peer is a part.
4237 * FIXME: Here do we only remove the entry from our own routing table
4238 * or do we also inform other peers which are part of trail. It seems to be
4239 * too much of messages exchanged. */
4240 GDS_ROUTING_print();
4241 GDS_ROUTING_remove_entry (peer);
4243 /* Remove the peer from friend_peermap. */
4244 GNUNET_assert (GNUNET_YES ==
4245 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
4249 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
4252 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4254 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4255 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4263 * Method called whenever a peer connects.
4265 * @param cls closure
4266 * @param peer_identity peer identity this notification is about
4269 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
4271 struct FriendInfo *friend;
4273 /* Check for connect to self message */
4274 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
4277 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
4279 /* If peer already exists in our friend_peermap, then exit. */
4280 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
4286 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
4289 friend = GNUNET_new (struct FriendInfo);
4290 friend->id = *peer_identity;
4291 friend->trails_count = 0;
4293 GNUNET_assert (GNUNET_OK ==
4294 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
4295 peer_identity, friend,
4296 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
4298 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
4299 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
4300 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
4305 * To be called on core init/fail.
4307 * @param cls service closure
4308 * @param identity the public identity of this peer
4311 core_init (void *cls,
4312 const struct GNUNET_PeerIdentity *identity)
4314 my_identity = *identity;
4319 * Initialize neighbours subsystem.
4320 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4323 GDS_NEIGHBOURS_init (void)
4325 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
4326 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
4327 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
4328 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
4329 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
4330 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
4331 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
4332 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
4333 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
4334 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
4335 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
4340 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
4341 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
4342 GNUNET_NO, core_handlers);
4343 if (NULL == core_api)
4344 return GNUNET_SYSERR;
4346 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
4347 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS * 4/3, GNUNET_NO);
4354 * Shutdown neighbours subsystem.
4357 GDS_NEIGHBOURS_done (void)
4359 if (NULL == core_api)
4362 GNUNET_CORE_disconnect (core_api);
4365 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
4366 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
4367 friend_peermap = NULL;
4369 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
4370 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
4371 finger_peermap = NULL;
4373 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4376 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4377 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4385 * @return my identity
4387 struct GNUNET_PeerIdentity
4388 GDS_NEIGHBOURS_get_my_id (void)
4394 /* end of gnunet-service-xdht_neighbours.c */