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 2. Use a global array of all known peers in find_successor, Only when
51 a new peer is added in finger or friend peer map, then re calculate
52 the array. Or else use the old one. The benefit of having this list is something
53 I am not sure. only when the code is complete and working I will do this part.
54 3. Structure alignment.
55 4. Check where do you set all_friends_trail_threshold? In select_random_friend?
56 5. In put, we don't have anything like put result. so we are not adding anything
61 * Maximum possible fingers of a peer.
63 #define MAX_FINGERS 66
66 * Maximum allowed number of pending messages per friend peer.
68 #define MAXIMUM_PENDING_PER_FRIEND 64
71 * How long to wait before sending another find finger trail request
73 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
76 * How long at most to wait for transmission of a request to another peer?
78 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
80 GNUNET_NETWORK_STRUCT_BEGIN
88 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
90 struct GNUNET_MessageHeader header;
95 uint32_t options GNUNET_PACKED;
100 uint32_t block_type GNUNET_PACKED;
105 uint32_t hop_count GNUNET_PACKED;
108 * Replication level for this message
109 * In the current implementation, this value is not used.
111 uint32_t desired_replication_level GNUNET_PACKED;
114 * Length of the PUT path that follows (if tracked).
116 uint32_t put_path_length GNUNET_PACKED;
119 * Current destination to which this message is forwarded.
121 struct GNUNET_PeerIdentity current_destination;
124 * Peer whose finger is current_destination.
126 struct GNUNET_PeerIdentity current_source;
129 * When does the content expire?
131 struct GNUNET_TIME_AbsoluteNBO expiration_time;
134 * The key to store the value under.
136 struct GNUNET_HashCode key GNUNET_PACKED;
138 /* put path (if tracked) */
148 struct PeerGetResultMessage
151 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
153 struct GNUNET_MessageHeader header;
156 * The type for the data.
158 uint32_t type GNUNET_PACKED;
161 * Peer which will receive the get result message.
163 struct GNUNET_PeerIdentity source_peer;
166 * Number of peers recorded in the outgoing path from source to the
167 * stored location of this message.
169 uint32_t put_path_length GNUNET_PACKED;
172 * Length of the GET path that follows (if tracked).
174 uint32_t get_path_length GNUNET_PACKED;
177 * When does the content expire?
179 struct GNUNET_TIME_Absolute expiration_time;
182 * The key of the corresponding GET request.
184 struct GNUNET_HashCode key;
186 /* put path (if tracked) */
188 /* get path (if tracked) */
198 struct PeerGetMessage
201 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
203 struct GNUNET_MessageHeader header;
208 uint32_t options GNUNET_PACKED;
211 * Desired content type.
213 uint32_t block_type GNUNET_PACKED;
218 uint32_t hop_count GNUNET_PACKED;
221 * Desired replication level for this request.
222 * In the current implementation, this value is not used.
224 uint32_t desired_replication_level GNUNET_PACKED;
227 * Total number of peers in get path.
229 unsigned int get_path_length;
232 * Peer which is an intermediate destination.
234 struct GNUNET_PeerIdentity current_destination;
237 * Source for which current_destination is the finger.
239 struct GNUNET_PeerIdentity current_source;
242 * The key we are looking for.
244 struct GNUNET_HashCode key;
252 * P2P Trail setup message
254 struct PeerTrailSetupMessage
258 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
260 struct GNUNET_MessageHeader header;
263 * Successor of this finger value will be our finger peer.
265 uint64_t destination_finger;
268 * Source peer which wants to setup the trail to one of its finger.
270 struct GNUNET_PeerIdentity source_peer;
273 * Peer to which this packet is forwarded.
275 struct GNUNET_PeerIdentity current_destination;
278 * In case the packet is forwarded to an intermediate finger, then
279 * current_source contains the peer id whose finger is the intermediate
280 * finger. In case the packet is forwarded to a friend, then it is NULL.
281 * FIXME: check the usage of current_source and fix this comment.
283 struct GNUNET_PeerIdentity current_source;
286 * Index into finger peer map, in Network Byte Order.
288 uint32_t finger_map_index;
291 * Number of entries in trail list, in Network Byte Order.
293 uint32_t trail_length GNUNET_PACKED;
295 /* Trail formed in the process. */
300 * P2P Trail Setup Result message
302 struct PeerTrailSetupResultMessage
306 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
308 struct GNUNET_MessageHeader header;
311 * Finger to which we have found the path.
313 struct GNUNET_PeerIdentity finger_identity;
316 * Peer which was looking for the trail to finger.
318 struct GNUNET_PeerIdentity destination_peer;
321 * Index into finger peer map in NBO.
323 uint32_t finger_map_index;
326 * Number of entries in trail list in NBO.
328 uint32_t trail_length GNUNET_PACKED;
330 /* Trail from destination_peer to finger_identity */
336 * P2P Trail Rejection Message.
338 struct PeerTrailRejectionMessage
341 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
343 struct GNUNET_MessageHeader header;
346 * Source peer which wants to set up the trail.
348 struct GNUNET_PeerIdentity source_peer;
351 * Peer which sent trail rejection message.
353 struct GNUNET_PeerIdentity congested_peer;
356 * Peer identity which will be successor to this value will be finger of
359 uint64_t finger_identity_value;
362 * Index in finger peer map of source peer.
364 uint32_t finger_map_index;
367 * Total number of peers in the trail.
369 uint32_t trail_length;
371 /* Trail_list from source_peer to peer which sent the message for trail setup
372 * to congested peer.*/
377 * P2P Verify Successor message.
379 struct PeerVerifySuccessorMessage
383 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
385 struct GNUNET_MessageHeader header;
388 * Source peer which wants to verify its successor.
390 struct GNUNET_PeerIdentity source_peer;
393 * My current successor.
395 struct GNUNET_PeerIdentity successor;
398 * Total number of peers in trail to current successor.
400 uint32_t trail_length;
402 /* Trail to reach to from source_peer to successor. */
407 * P2P Verify Successor Result message.
409 struct PeerVerifySuccessorResultMessage
413 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
415 struct GNUNET_MessageHeader header;
418 * Destination peer which sent the request to verify its successor.
420 struct GNUNET_PeerIdentity destination_peer;
423 * Successor to which PeerVerifySuccessorMessage was sent.
425 struct GNUNET_PeerIdentity source_successor;
428 * source_successor's predecessor
430 struct GNUNET_PeerIdentity my_predecessor;
433 * Total number of peers in trail.
435 uint32_t trail_length;
437 /* Trail to reach from destination_peer to its correct successor.
438 * If source_successor is not destination peer, then trail is from destination_peer
440 * If source_successor is destination peer, then trail is from destination_peer
441 * to source_successor. */
446 * P2P Notify New Successor message.
448 struct PeerNotifyNewSuccessorMessage
451 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
453 struct GNUNET_MessageHeader header;
456 * Source peer which wants to notify its new successor.
458 struct GNUNET_PeerIdentity source_peer;
461 * New successor identity.
463 struct GNUNET_PeerIdentity destination_peer;
466 * Number of peers in trail from source_peer to new successor.
468 uint32_t trail_length;
470 /* Trail to from source_peer to destination_peer. */
473 struct PeerTrailTearDownMessage
476 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
478 struct GNUNET_MessageHeader header;
481 * Source peer of this trail.
483 struct GNUNET_PeerIdentity source_peer;
486 * Destination peer of this trail.
488 struct GNUNET_PeerIdentity destination_peer;
491 * Trail from source_peer to destination_peer compressed such that
492 * new_first_friend is the first hop in the trail from source to
495 struct GNUNET_PeerIdentity new_first_friend;
497 * Number of peers in trail from source_peer to new first friend.
499 uint32_t trail_length;
501 /* Trail to from source_peer to new first friend. */
504 GNUNET_NETWORK_STRUCT_END
508 * Linked list of messages to send to a particular other peer.
510 struct P2PPendingMessage
513 * Pointer to next item in the list
515 struct P2PPendingMessage *next;
518 * Pointer to previous item in the list
520 struct P2PPendingMessage *prev;
523 * Message importance level. FIXME: used? useful?
525 unsigned int importance;
528 * When does this message time out?
530 struct GNUNET_TIME_Absolute timeout;
533 * Actual message to be sent, allocated at the end of the struct:
534 * // msg = (cast) &pm[1];
535 * // memcpy (&pm[1], data, len);
537 const struct GNUNET_MessageHeader *msg;
543 * Linked List of peers which are part of trail to reach a particular Finger.
548 * Pointer to next item in the list
550 struct TrailPeerList *next;
553 * Pointer to previous item in the list
555 struct TrailPeerList *prev;
558 * An element in this trail list
560 struct GNUNET_PeerIdentity peer;
566 * Entry in friend_peermap.
573 struct GNUNET_PeerIdentity id;
576 * 1. used in select_random_friend(), in case the friend has trails_count > TRAILS_THROUGH_FRIEND,
577 * then choose another friend.
578 * 2. in case of find_successor(), if the number of trails going through the friend
579 * has already crossed, then choose another friend.
580 * 3. in case of find_successor(), if we choose a finger, and if friend through
581 * which we reach this finger has crossed the limit then choose another finger/friend.
582 * 4. One way to implement in case of find_successor, is 1) you can have a global
583 * array of the entries and only when an entry is added in finger table, friend table,
584 * then you re calculate the array. In array while adding the element you check
585 * the threshold of the friend in case its friend, and in case of finger check
586 * the threshold of the first friend in the trail. If crossed then don't add the
587 * entries in the array. When the count goes down, then again set a flag and
588 * recalculte the array. Store a field in Finger table also, which will be
589 * equal to number of trails going through the first friend.
590 * Number of trail of which this friend is the first hop.
591 * 5.FIXME: understand where you need to use memcpy or direct assignment.
593 unsigned int trails_count;
596 * Count of outstanding messages for this friend.
598 unsigned int pending_count;
601 * Head of pending messages to be sent to this friend.
603 struct P2PPendingMessage *head;
606 * Tail of pending messages to be sent to this friend.
608 struct P2PPendingMessage *tail;
611 * Core handle for sending messages to this friend.
613 struct GNUNET_CORE_TransmitHandle *th;
619 * Entry in finger_peermap.
626 struct GNUNET_PeerIdentity finger_identity;
629 * Index in finger peer map
631 unsigned int finger_map_index;
634 * Number of trails to reach to this finger.
636 unsigned int trail_count;
639 * Total number of entries in first trail from (me,finger)
641 unsigned int first_trail_length;
644 * Total number of entries in second trail from (me,finger)
646 unsigned int second_trail_length;
650 * Number of trail of which the first element to reach to this finger is
653 unsigned int first_friend_trails_count;
656 * Head of first trail to reach this finger.
658 struct TrailPeerList *first_trail_head;
661 * Tail of first trail to reach this finger.
663 struct TrailPeerList *first_trail_tail;
666 * Head of second trail to reach this finger.
668 struct TrailPeerList *second_trail_head;
671 * Tail of second trail to reach this finger.
673 struct TrailPeerList *second_trail_tail;
679 * FIXME: The name is not correct.
680 * Used to specify the kind of value stored in the array all_known_peers.
682 enum current_destination_type
692 * Data structure passed to sorting algorithm in find_successor().
697 * 64 bit value of peer identity
702 * FIXME: think of a better name for both the struct and destination_type
703 * Type : MY_ID, FINGER, FINGER, Value
705 enum current_destination_type type;
708 * Pointer to original data structure linked to peer id.
715 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
716 * get our first friend.
718 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
721 * Identity of this peer.
723 static struct GNUNET_PeerIdentity my_identity;
726 * Hash map of all the friends of a peer
728 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
731 * Hash map of all the fingers of a peer
733 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
738 static struct GNUNET_CORE_Handle *core_api;
741 * Finger map index for predecessor entry in finger peermap.
743 #define PREDECESSOR_FINGER_ID 64
746 * Maximum number of trails allowed to go through a friend.
747 * FIXME: Better name, Random value at the moment, need to be adjusted to maintain a balance
748 * between performance and Sybil tolerance.
750 #define TRAIL_THROUGH_FRIEND_THRESHOLD 64
753 * Possible number of different trails to reach to a finger. (Redundant routing)
755 #define TRAIL_COUNT 2
758 * FIXME: better name.
759 * Set to GNUNET_YES, when the number of trails going through all my friends
760 * have reached the TRAIL_THROUGH_FRIEND_THRESHOLD.
762 static unsigned int all_friends_trail_threshold;
765 * The current finger index that we have want to find trail to.
767 static unsigned int current_search_finger_index;
771 * Iterate over trail and search your index location in the array.
772 * @param trail Trail which contains list of peers.
773 * @param trail_length Number of peers in the trail.
774 * @return Index in the array.
775 * #GNUNET_SYSERR, in case there is no entry which should not be the case ideally.
778 search_my_index (const struct GNUNET_PeerIdentity *trail,
783 while (i < trail_length)
785 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
791 return GNUNET_SYSERR;
795 * Compare two peer identities.
796 * @param p1 Peer identity
797 * @param p2 Peer identity
798 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
801 compare_peer_id (const void *p1, const void *p2)
803 struct Sorting_List *p11;
804 struct Sorting_List *p22;
806 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
807 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
808 p11 = (struct Sorting_List *)p1;
809 p22 = (struct Sorting_List *)p2;
810 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
811 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
817 * Return the predecessor of value in all_known_peers.
818 * @param all_known_peers list of all the peers
819 * @param value value we have to search in the all_known_peers.
820 * @param size Total numbers of elements
821 * @return Predecessor
823 static struct Sorting_List *
824 find_closest_predecessor(struct Sorting_List *all_known_peers, uint64_t value,
833 middle = (first + last)/2;
837 if(all_known_peers[middle].peer_id < value)
841 else if(all_known_peers[middle].peer_id == value)
845 return &all_known_peers[size - 1];
849 return &all_known_peers[middle - 1];
857 middle = (first + last)/2;
864 * Return the successor of value in all_known_peers.
865 * @param all_known_peers list of all the peers
866 * @param value value we have to search in the all_known_peers.
867 * @param size Total numbers of elements
870 static struct Sorting_List *
871 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
880 middle = (first + last)/2;
884 if(all_known_peers[middle].peer_id < value)
888 else if(all_known_peers[middle].peer_id == value)
890 if(middle == (size -1))
892 return &all_known_peers[0];
896 return &all_known_peers[middle+1];
904 middle = (first + last)/2;
911 * Called when core is ready to send a message we asked for
912 * out to the destination.
914 * @param cls the 'struct FriendInfo' of the target friend
915 * @param size number of bytes available in buf
916 * @param buf where the callee should write the message
917 * @return number of bytes written to buf
920 core_transmit_notify (void *cls, size_t size, void *buf)
922 struct FriendInfo *peer = cls;
924 struct P2PPendingMessage *pending;
929 while ((NULL != (pending = peer->head)) &&
930 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
932 peer->pending_count--;
933 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
934 GNUNET_free (pending);
938 /* no messages pending */
944 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
945 GNUNET_CORE_PRIO_BEST_EFFORT,
946 GNUNET_TIME_absolute_get_remaining
947 (pending->timeout), &peer->id,
948 ntohs (pending->msg->size),
949 &core_transmit_notify, peer);
950 GNUNET_break (NULL != peer->th);
954 while ((NULL != (pending = peer->head)) &&
955 (size - off >= (msize = ntohs (pending->msg->size))))
957 GNUNET_STATISTICS_update (GDS_stats,
959 ("# Bytes transmitted to other peers"), msize,
961 memcpy (&cbuf[off], pending->msg, msize);
963 peer->pending_count--;
964 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
965 GNUNET_free (pending);
967 if (peer->head != NULL)
970 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
971 GNUNET_CORE_PRIO_BEST_EFFORT,
972 GNUNET_TIME_absolute_get_remaining
973 (pending->timeout), &peer->id, msize,
974 &core_transmit_notify, peer);
975 GNUNET_break (NULL != peer->th);
983 * Transmit all messages in the friend's message queue.
985 * @param peer message queue to process
988 process_friend_queue (struct FriendInfo *peer)
990 struct P2PPendingMessage *pending;
992 if (NULL == (pending = peer->head))
994 if (NULL != peer->th)
997 GNUNET_STATISTICS_update (GDS_stats,
999 ("# Bytes of bandwidth requested from core"),
1000 ntohs (pending->msg->size), GNUNET_NO);
1002 /* FIXME: Are we correctly initializing importance and pending. */
1004 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1005 pending->importance,
1006 GNUNET_TIME_absolute_get_remaining
1007 (pending->timeout), &peer->id,
1008 ntohs (pending->msg->size),
1009 &core_transmit_notify, peer);
1010 GNUNET_break (NULL != peer->th);
1015 * Construct a trail message and forward it to a friend.
1016 * @param source_peer Peer which wants to set up the trail to one of its finger.
1017 * @param destination_finger Peer identity closest to this value will be
1018 * @a source_peer's finger.
1019 * @param current_destination Finger of the @a current_source, for which among
1020 * its friends, its own identity and all fingers, this
1021 * finger is the closest to the @a destination_finger
1022 * @param current_source Peer for which @a current_destination is its finger.
1023 * @param target_friend Friend to which this message should be forwarded.
1024 * @param trail_length Numbers of peers in the trail found so far.
1025 * @param trail_peer_list Peers this request has traversed so far
1026 * @param finger_map_index Index in finger peer map
1029 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
1030 uint64_t destination_finger,
1031 struct GNUNET_PeerIdentity *current_destination,
1032 struct GNUNET_PeerIdentity *current_source,
1033 struct FriendInfo *target_friend,
1034 unsigned int trail_length,
1035 const struct GNUNET_PeerIdentity *trail_peer_list,
1036 unsigned int finger_map_index)
1038 struct P2PPendingMessage *pending;
1039 struct PeerTrailSetupMessage *tsm;
1040 struct GNUNET_PeerIdentity *peer_list;
1043 msize = sizeof (struct PeerTrailSetupMessage) +
1044 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1046 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1052 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1054 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1058 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1059 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1060 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1061 pending->msg = &tsm->header;
1062 tsm->header.size = htons (msize);
1063 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
1064 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
1065 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1066 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
1067 memcpy (&(tsm->current_source), current_source, sizeof (struct GNUNET_PeerIdentity));
1068 tsm->trail_length = htonl (trail_length);
1069 tsm->finger_map_index = htonl (finger_map_index);
1071 if (trail_length > 0)
1073 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1074 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1077 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1078 target_friend->pending_count++;
1079 process_friend_queue (target_friend);
1085 * Construct a trail setup result message and forward it to a friend.
1086 * @param destination_peer Peer which will get the trail to one of its finger.
1087 * @param source_finger Peer to which the trail has been setup to.
1088 * @param target_friend Friend to which this message should be forwarded.
1089 * @param trail_length Numbers of peers in the trail.
1090 * @param trail_peer_list Peers which are part of the trail from source to destination.
1091 * @param finger_map_index Index in finger peer map
1094 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destination_peer,
1095 const struct GNUNET_PeerIdentity *source_finger,
1096 struct FriendInfo *target_friend,
1097 unsigned int trail_length,
1098 const struct GNUNET_PeerIdentity *trail_peer_list,
1099 unsigned int finger_map_index)
1101 struct P2PPendingMessage *pending;
1102 struct PeerTrailSetupResultMessage *tsrm;
1103 struct GNUNET_PeerIdentity *peer_list;
1106 msize = sizeof (struct PeerTrailSetupResultMessage) +
1107 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1109 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1115 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1117 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1121 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1122 pending->importance = 0;
1123 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1124 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1125 pending->msg = &tsrm->header;
1126 tsrm->header.size = htons (msize);
1127 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
1128 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1129 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
1130 tsrm->trail_length = htonl (trail_length);
1131 tsrm->finger_map_index = htonl (finger_map_index);
1133 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1134 if (trail_length > 0)
1136 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1138 /* Send the message to chosen friend. */
1139 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1140 target_friend->pending_count++;
1141 process_friend_queue (target_friend);
1146 * Construct a PeerVerifySuccessor message and send it to friend.
1147 * @param source_peer Peer which wants to verify its successor
1148 * @param successor Peer which is our current successor
1149 * @param target_friend Friend to which this message should be forwarded.
1150 * @param trail_peer_list Peer which are part of trail from source to destination
1151 * @param trail_length Number of peers in the trail list.
1153 void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *source_peer,
1154 const struct GNUNET_PeerIdentity *successor,
1155 struct FriendInfo *target_friend,
1156 const struct GNUNET_PeerIdentity *trail_peer_list,
1157 unsigned int trail_length)
1159 struct PeerVerifySuccessorMessage *vsm;
1160 struct P2PPendingMessage *pending;
1161 struct GNUNET_PeerIdentity *peer_list;
1164 msize = sizeof (struct PeerVerifySuccessorMessage) +
1165 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1167 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1173 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1175 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1179 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1180 pending->importance = 0; /* FIXME */
1181 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1182 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1183 pending->msg = &vsm->header;
1184 vsm->header.size = htons (msize);
1185 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1186 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
1187 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1188 vsm->trail_length = htonl (trail_length);
1190 if (trail_length > 0)
1192 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1193 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1196 /* Send the message to chosen friend. */
1197 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1198 target_friend->pending_count++;
1199 process_friend_queue (target_friend);
1205 * Construct a PeerVerifySuccessorResult message and send it to friend.
1206 * @param destination_peer Peer which sent verify successor message
1207 * @param source_successor Peer to which verify successor message was sent.
1208 * @param my_predecessor source_successor's predecessor.
1209 * @param target_friend Friend to which this message should be forwarded.
1210 * @param trail_peer_list Peers which are part of trail from source to destination
1211 * @param trail_length Number of peers in the trail list.
1213 void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *destination_peer,
1214 const struct GNUNET_PeerIdentity *source_successor,
1215 const struct GNUNET_PeerIdentity *my_predecessor,
1216 struct FriendInfo *target_friend,
1217 const struct GNUNET_PeerIdentity *trail_peer_list,
1218 unsigned int trail_length)
1220 struct PeerVerifySuccessorResultMessage *vsmr;
1221 struct P2PPendingMessage *pending;
1222 struct GNUNET_PeerIdentity *peer_list;
1225 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1226 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1228 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1235 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1237 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1241 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1242 pending->importance = 0; /* FIXME */
1243 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1244 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1245 pending->msg = &vsmr->header;
1246 vsmr->header.size = htons (msize);
1247 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1248 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1249 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1250 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1251 vsmr->trail_length = htonl (trail_length);
1252 if (trail_length > 0)
1254 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1255 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1258 /* Send the message to chosen friend. */
1259 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1260 target_friend->pending_count++;
1261 process_friend_queue (target_friend);
1266 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1267 * @param source_peer Peer which is sending notify message to its new successor.
1268 * @param destination_peer Peer which is the new destination.
1269 * @param target_friend Next friend to pass this message to.
1270 * @param peer_list List of peers in the trail to reach to destination_peer.
1271 * @param trail_length Total number of peers in peer list
1274 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1275 const struct GNUNET_PeerIdentity *destination_peer,
1276 struct FriendInfo *target_friend,
1277 const struct GNUNET_PeerIdentity *trail_peer_list,
1278 unsigned int trail_length)
1280 struct PeerNotifyNewSuccessorMessage *nsm;
1281 struct P2PPendingMessage *pending;
1282 struct GNUNET_PeerIdentity *peer_list;
1285 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1286 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1288 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1294 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1296 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1300 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1301 pending->importance = 0; /* FIXME */
1302 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1303 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1304 pending->msg = &nsm->header;
1305 nsm->header.size = htons (msize);
1306 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1307 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1308 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1309 nsm->trail_length = htonl (trail_length);
1310 /* FIXME: Here I am not checking the trail length, as I am assuming that for new
1311 successor our old successor is a part of trail, so trail length > 1. */
1312 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1313 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1315 /* Send the message to chosen friend. */
1316 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1317 target_friend->pending_count++;
1318 process_friend_queue (target_friend);
1322 * Send a trail tear down message
1323 * @param source_peer Source of the trail.
1324 * @param destination_peer Destination of the trail.
1325 * @param discarded_trail Discarded trail from source to destination.
1326 * @param discarded_trail_length Total number of peers in trail_list.
1327 * @pararm target_peer Next peer to forward this message to.
1328 * @param new_first_friend The new first hop in the new trail from source to destination
1332 GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_PeerIdentity *source_peer,
1333 const struct GNUNET_PeerIdentity *destination_peer,
1334 const struct GNUNET_PeerIdentity *discarded_trail,
1335 unsigned int discarded_trail_length,
1336 struct FriendInfo *target_friend,
1337 const struct GNUNET_PeerIdentity *new_first_friend)
1339 struct P2PPendingMessage *pending;
1340 struct PeerTrailTearDownMessage *ttdm;
1341 struct GNUNET_PeerIdentity *peer_list;
1344 msize = sizeof (struct PeerTrailTearDownMessage) +
1345 (discarded_trail_length * sizeof(struct GNUNET_PeerIdentity));
1347 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1353 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1355 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1359 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1360 pending->importance = 0; /* FIXME */
1361 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1362 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1363 pending->msg = &ttdm->header;
1364 ttdm->header.size = htons (msize);
1365 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1366 memcpy (&(ttdm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1367 memcpy (&(ttdm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1368 memcpy (&(ttdm->new_first_friend),new_first_friend, sizeof (struct GNUNET_PeerIdentity));
1369 ttdm->trail_length = htonl (discarded_trail_length);
1371 peer_list = (struct GNUNET_PeerIdentity *) &ttdm[1];
1372 memcpy (peer_list, discarded_trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1374 /* Send the message to chosen friend. */
1375 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1376 target_friend->pending_count++;
1377 process_friend_queue (target_friend);
1382 * FIMXE: Change the return value, to handle the case where all friends
1384 * FIXME: Handle congested peer - don't choose this friend, also don't choose
1385 * the friend if the link threshold has crossed. Not implemented yet.
1386 * Randomly choose one of your friends from the friends_peer map
1389 static struct FriendInfo *
1390 select_random_friend ()
1392 unsigned int current_size;
1393 unsigned int *index;
1395 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1396 struct GNUNET_PeerIdentity key_ret;
1397 struct FriendInfo *friend;
1399 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1400 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1401 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1405 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1413 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1415 /* Possible number of trails that can go through this friend has been reached. */
1416 if (friend->trails_count > TRAIL_THROUGH_FRIEND_THRESHOLD)
1418 /* FIXME: What should I do now, should I call this same function again and
1419 remember the index, j so that call random function without j and find
1420 a new friend. Also, I need some way to make sure that if number of times
1421 I have called the function is equal to number of entries in friend peermap.
1422 then I should return NULL. but its much better to have a function which
1423 just eliminates looking at the entries with threshold crossed. URGENT: Whats
1424 the best way to handle this case? */
1434 * Compute finger_identity to which we want to setup the trail
1435 * @return finger_identity
1438 compute_finger_identity()
1442 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1443 my_id64 = GNUNET_ntohll (my_id64);
1444 return (my_id64 + (unsigned long) pow (2, current_search_finger_index));
1449 * Compute immediate predecessor identity in the network.
1450 * @return peer identity of immediate predecessor.
1453 compute_predecessor_identity()
1457 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1458 my_id64 = GNUNET_ntohll (my_id64);
1459 return (my_id64 -1);
1464 * Ping your successor to verify if it is still your successor or not.
1467 send_verify_successor_message()
1469 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1470 struct GNUNET_PeerIdentity key_ret;
1471 struct FriendInfo *target_friend;
1472 struct GNUNET_PeerIdentity next_hop;
1473 struct GNUNET_PeerIdentity *peer_list;
1474 struct FingerInfo *finger;
1475 unsigned int finger_index;
1478 /* Find the successor from the finger peermap.*/
1479 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1480 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1482 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1483 (const void **)&finger))
1485 if (0 == finger->finger_map_index)
1492 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1494 /* Either you don't have a successor or you are your own successor, then don't
1495 send a successor message. */
1497 (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &(finger->finger_identity))))
1502 if (finger->first_trail_length > 0)
1504 struct TrailPeerList *iterate;
1506 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->first_trail_length);
1507 iterate = finger->first_trail_head;
1509 while ( i < (finger->first_trail_length))
1512 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1513 iterate = iterate->next;
1516 memcpy (&next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1517 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
1521 /* If trail length = 0, then our successor is our friend. */
1523 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1524 &(finger->finger_identity));
1527 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1528 &(finger->finger_identity),
1531 finger->first_trail_length);
1537 * 1. Need to handle the case where all friends are either congested or
1538 * have reached their threshold.
1539 * 2. If we need all_friends_trail_threshold
1540 * 3. do we need to check if friend peermap is empty or not.
1541 * Choose a random friend and start looking for the trail to reach to
1542 * finger identity through this random friend.
1544 * @param cls closure for this task
1545 * @param tc the context under which the task is running
1548 send_find_finger_trail_message (void *cls,
1549 const struct GNUNET_SCHEDULER_TaskContext *tc)
1551 struct FriendInfo *target_friend;
1552 struct GNUNET_TIME_Relative next_send_time;
1553 uint64_t finger_identity;
1554 unsigned int finger_map_index;
1556 next_send_time.rel_value_us =
1557 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1558 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1559 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1560 find_finger_trail_task =
1561 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1564 if (GNUNET_YES == all_friends_trail_threshold)
1566 /* All friends in friend peer map, have reached their trail threshold. No
1567 more new trail can be created. */
1571 target_friend = select_random_friend ();
1572 if (NULL == target_friend)
1574 all_friends_trail_threshold = GNUNET_YES;
1578 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
1580 finger_identity = compute_predecessor_identity();
1584 finger_identity = compute_finger_identity();
1587 finger_map_index = current_search_finger_index;
1588 GDS_NEIGHBOURS_send_trail_setup (&my_identity, finger_identity, &(target_friend->id),
1589 &my_identity, target_friend, 0, NULL, finger_map_index);
1594 * Scan the trail to check if any of my own friend is part of trail. If yes
1595 * then shortcut the trail, send a trail teardown for the discarded trail,
1596 * update trail list and trail_length.
1597 * @param trail[Out] Current trail to reach to @a finger, will be updated
1598 * in case we compress the trail.
1599 * @param trail_length[Out] Number of peers in @a finger_trail, will be updated
1600 * in case we compress the trail.
1601 * @param finger Finger identity
1604 scan_and_compress_trail (struct GNUNET_PeerIdentity *trail,
1605 unsigned int *trail_length,
1606 const struct GNUNET_PeerIdentity *finger)
1609 struct FriendInfo *target_friend;
1611 /* If finger is my friend, then send a trail teardown message and then set
1612 * trail_length = 0; */
1613 if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger))
1615 int discarded_trail_length = *trail_length;
1616 target_friend = GNUNET_CONTAINER_multipeermap_get(friend_peermap, &trail[0]);
1617 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, trail,
1618 discarded_trail_length, target_friend, finger);
1624 i = *trail_length - 1;
1627 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
1629 /* This element of trail is not my friend. */
1634 /* A --> B(friend 1) --> C(friend 2)--> D ---> E, then we can rewrite the trail as
1636 * Now, we should remove the entry from A's routing table, B's routing table
1637 * and update the entry in C's routing table. Rest everything will be same.
1638 * C's routing table should have source peer as the prev.hop.
1640 struct GNUNET_PeerIdentity *discarded_trail;
1641 struct FriendInfo *target_friend;
1642 int discarded_trail_length;
1645 discarded_trail_length = i - 1;
1646 discarded_trail = GNUNET_malloc (discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1647 memcpy (discarded_trail, trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1648 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
1650 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, discarded_trail,
1651 discarded_trail_length, target_friend,
1654 /* Copy the trail from index i to index trail_length -1 and change
1655 trail length and return */
1656 while (i < *trail_length)
1658 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
1662 *trail_length = j+1;
1671 * FIXME: Is this correct? Here I am using dll_remove and its documentation
1672 * reads something else. Verify. Urgent.
1673 * Free finger and its trail.
1674 * @param finger Finger to be freed.
1677 free_finger (struct FingerInfo *finger)
1679 struct TrailPeerList *peer;
1681 if(finger->first_trail_head != NULL)
1683 while (NULL != (peer = finger->first_trail_head))
1685 GNUNET_CONTAINER_DLL_remove (finger->first_trail_head, finger->first_trail_tail, peer);
1690 if (finger->second_trail_head != NULL)
1692 while (NULL != (peer = finger->second_trail_head))
1694 GNUNET_CONTAINER_DLL_remove (finger->second_trail_head, finger->second_trail_tail, peer);
1697 GNUNET_free (finger);
1703 * FIXME: First check if both the trails are present if yes then send it
1704 * for both of them. Currently sending it only for one trail.
1705 * Send a trail teardown message for the trail of removed finger from the finger
1707 * @param existing_finger Finger to removed from the finger peermap.
1710 void send_trail_teardown (struct FingerInfo *removed_finger)
1712 struct GNUNET_PeerIdentity *peer_list;
1713 struct FriendInfo *friend;
1714 struct TrailPeerList *finger_trail;
1715 int removed_finger_trail_length = removed_finger->first_trail_length;
1718 if (removed_finger->first_trail_length == 0)
1720 finger_trail = removed_finger->first_trail_head;
1721 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(finger_trail->peer));
1722 peer_list = GNUNET_malloc ( removed_finger_trail_length * sizeof (struct GNUNET_PeerIdentity));
1723 while (i < removed_finger->first_trail_length)
1725 memcpy (&peer_list[i], &(finger_trail->peer), sizeof (struct GNUNET_PeerIdentity));
1726 finger_trail = finger_trail->next;
1730 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, &(removed_finger->finger_identity),
1731 peer_list, removed_finger_trail_length, friend,
1732 &(removed_finger->finger_identity));
1737 * FIXME: How do we understand which is the correct trail head?
1738 * Add a new trail to reach an existing finger in finger peermap and increment
1739 * the count of number of trails to reach to this finger.
1740 * @param existing_finger Finger
1741 * @param trail New trail to be added
1742 * @param trail_length Total number of peers in the trail.
1745 void add_new_trail (struct FingerInfo *existing_finger,
1746 struct GNUNET_PeerIdentity *trail,
1747 unsigned int trail_length)
1751 /* FIXME: Here you need to understand which trail is there and which not.
1752 In case first_trail_head != NULL, then that trail is present
1753 so you should add the second one. Need to verify this logic. */
1754 if (existing_finger->first_trail_head != NULL)
1756 while (i < trail_length)
1758 struct TrailPeerList *element;
1759 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1760 element->next = NULL;
1761 element->prev = NULL;
1763 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1764 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1768 else if (existing_finger->second_trail_head != NULL)
1770 while (i < trail_length)
1772 struct TrailPeerList *element;
1773 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1774 element->next = NULL;
1775 element->prev = NULL;
1777 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1778 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->first_trail_head, existing_finger->first_trail_tail, element);
1782 existing_finger->trail_count++;
1787 * In case there are already maximum number of possible trail to reach to a finger,
1788 * then check if the new trail's length is lesser than any of the existing trails.
1789 * If yes then replace that old trail by new trail.
1790 * Note: Here we are taking length as a parameter to choose the best possible trail,
1791 * but there could be other parameters also like - 1. duration of existence of a
1792 * trail - older the better. 2. if the new trail is completely disjoint than the
1793 * other trails, then may be choosing it is better.
1794 * @param existing_finger
1796 * @param trail_length
1797 * @return #GNUNET_YES
1801 void select_and_replace_trail (struct FingerInfo *existing_finger,
1802 struct GNUNET_PeerIdentity *new_trail,
1803 unsigned int new_trail_length)
1805 if (existing_finger->first_trail_length == existing_finger->second_trail_length)
1807 if (new_trail_length < existing_finger->first_trail_length)
1809 /* Randomly choose one of the trail. FIXME:currently I am just replacing the
1811 struct TrailPeerList *peer;
1814 while (NULL != (peer = existing_finger->first_trail_head))
1816 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1820 while (i < new_trail_length)
1822 struct TrailPeerList *element;
1823 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1824 element->next = NULL;
1825 element->prev = NULL;
1827 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1828 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1833 else if ((new_trail_length < existing_finger->second_trail_length) &&
1834 (existing_finger->second_trail_length < existing_finger->first_trail_length))
1836 /* Replace the first trail by the new trail. */
1837 struct TrailPeerList *peer;
1840 while (NULL != (peer = existing_finger->first_trail_head))
1842 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1846 while (i < new_trail_length)
1848 struct TrailPeerList *element;
1849 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1850 element->next = NULL;
1851 element->prev = NULL;
1853 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1854 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1858 else if ( (new_trail_length < existing_finger->first_trail_length) &&
1859 (existing_finger->first_trail_length < existing_finger->second_trail_length))
1861 /* Replace the second trail by the new trail. */
1862 struct TrailPeerList *peer;
1865 while (NULL != (peer = existing_finger->second_trail_head))
1867 GNUNET_CONTAINER_DLL_remove (existing_finger->second_trail_head, existing_finger->second_trail_tail, peer);
1871 while (i < new_trail_length)
1873 struct TrailPeerList *element;
1874 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1875 element->next = NULL;
1876 element->prev = NULL;
1878 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1879 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1887 * FIXME: If we remove a finger which is our friend, then how should we handle it.
1888 * Ideally only in case if the trail_length > 0,we increment the trail count
1889 * of the first friend in the trail to reach to the finger. in case finger is
1890 * our friend then trail length = 0, and hence, we have never incremented the
1891 * trail count associated with that friend.
1892 * Decrement the trail count for the first friend to reach to the finger.
1896 decrement_friend_trail_count (struct FingerInfo *finger)
1898 struct FriendInfo *first_trail_friend;
1899 struct FriendInfo *second_trail_friend;
1901 if(finger->first_trail_head != NULL)
1903 first_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1904 &(finger->first_trail_head->peer));
1905 first_trail_friend->trails_count--;
1908 if(finger->second_trail_head != NULL)
1910 second_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1911 &(finger->second_trail_head->peer));
1912 second_trail_friend->trails_count--;
1916 /* We will not need this variable any more, all_friends_trail_threshold,
1917 FIXME: REMOVE IT. */
1918 if (GNUNET_YES == all_friends_trail_threshold)
1920 all_friends_trail_threshold = GNUNET_NO;
1921 /* FIXME; Here you should reschedule the send_find_finger_task here. or
1929 * Select the closest finger. Used for both predecessor and other fingers..
1930 * But internally calls different functions for predecessor and other fingers.
1931 * @param existing_finger Finger in finger peermap.
1932 * @param new_finger New finger identity
1933 * @param finger_map_index Index in finger peermap where @a existing_finger is stored.
1934 * @return #GNUNET_YES if the new finger is closest.
1935 * #GNUNET_NO if the old finger is closest.
1936 * #GNUNET_SYSERR in case our own identity is closest (should never happen).
1939 int select_finger (struct FingerInfo *existing_finger,
1940 const struct GNUNET_PeerIdentity *new_finger,
1941 unsigned int finger_map_index)
1943 struct Sorting_List peers[3]; /* 3 for existing_finger, new_finger, my_identity */
1944 struct Sorting_List *closest_finger;
1948 for (k = 0; k < 3; k++)
1951 /* Add your entry to peers. */
1952 memcpy (&peers[0], &my_identity, sizeof (uint64_t));
1953 peers[0].type = MY_ID;
1954 peers[0].data = NULL;
1956 /* Add existing_finger identity to the peers. */
1957 memcpy (&peers[1], &(existing_finger->finger_identity), sizeof (uint64_t));
1958 peers[1].type = FINGER;
1959 peers[1].data = existing_finger;
1961 /* Add new_finger identity to the peers. s*/
1962 memcpy (&peers[2], &new_finger, sizeof (uint64_t));
1963 peers[2].type = VALUE;
1964 peers[2].data = NULL;
1966 memcpy (&value, &my_identity, sizeof (uint64_t));
1968 qsort (&peers, 3, sizeof (struct Sorting_List), &compare_peer_id);
1970 if (PREDECESSOR_FINGER_ID == finger_map_index)
1971 closest_finger = find_closest_predecessor (peers, value, 3);
1973 closest_finger = find_closest_successor (peers, value, 3);
1975 if (closest_finger->type == FINGER)
1979 else if (closest_finger->type == VALUE)
1983 else if (closest_finger->type == MY_ID);
1985 return GNUNET_SYSERR;
1991 * FIXME: Do we need to reinsert the existing finger into finger peermap
1992 * in case we add a new trail?
1993 * Choose the closest finger between existing finger and new finger.
1994 * If the new finger is closest and finger_map_index != PREDECESSOR_FINGER_ID,
1995 * then send a trail_teardown message along existing_finger's trail.
1996 * In case both the id's are same, and there is a place to keep more trails, then
1997 * store both of them. In case there is no space to store any more trail, then
1998 * choose the best trail (best - depends on length in current_implementation) and
1999 * discard the others.
2000 * @param existing_finger Existing entry in finger peer map
2001 * @param new_finger New finger
2002 * @param trail Trail to reach to the new finger from me.
2003 * @param trail_length Number of peers in the @a trail
2004 * @param finger_map_index If finger_map_index == PREDECESSOR_FINGER_INDEX,
2005 * then we use a different logic to find the closest
2007 * @return #GNUNET_YES In case we want to store the new entry.
2008 * #GNUNET_NO In case we want the existing entry.
2009 * #GNUNET_SYSERR Error.
2012 int select_closest_finger (struct FingerInfo *existing_finger,
2013 const struct GNUNET_PeerIdentity *new_finger,
2014 struct GNUNET_PeerIdentity *trail,
2015 unsigned int trail_length,
2016 unsigned int finger_map_index)
2018 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), new_finger))
2020 /* Both the new entry and existing entry are same. */
2021 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), &my_identity))
2023 /* If existing_finger is my_identity then trail_length = 0, trail = NULL. In
2024 this case you don't need to check the trails. Exit. */
2027 if (trail_length > 1)
2029 scan_and_compress_trail (trail, &trail_length, new_finger);
2031 if (existing_finger->trail_count < TRAIL_COUNT)
2033 add_new_trail (existing_finger, trail, trail_length);
2038 select_and_replace_trail (existing_finger, trail, trail_length);
2042 else if (GNUNET_YES == select_finger (existing_finger, new_finger, finger_map_index))
2044 /* new_finger is the correct finger. */
2045 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, new_finger))
2047 /* FIXME: Here in case the new finger is my_identity and old entry is not,
2048 should we keep the old entry even if the old entry is not the closest? */
2052 /* Clear all things associated with existing_finger (only if its not a
2054 if (PREDECESSOR_FINGER_ID != finger_map_index)
2055 send_trail_teardown (existing_finger);
2056 decrement_friend_trail_count (existing_finger);
2057 free_finger (existing_finger);
2059 if (trail_length > 1)
2060 scan_and_compress_trail (trail, &trail_length, new_finger);
2063 else if (GNUNET_NO == select_finger (existing_finger, new_finger,finger_map_index))
2065 /* existing_finger is the correct finger. */
2068 return GNUNET_SYSERR;
2073 * Check if there is a predecessor in our finger peer map or not.
2074 * If no, then return GNUNET_YES
2075 * else compare existing predecessor and peer, and find the correct
2077 * @param existing_predecessor
2078 * @param new_predecessor
2079 * @return #GNUNET_YES if new peer is predecessor
2080 * #GNUNET_NO if new peer is not the predecessor.
2083 compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer,
2084 struct GNUNET_PeerIdentity *trail,
2085 unsigned int trail_length)
2087 /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
2088 struct FingerInfo *existing_finger;
2089 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2090 struct FingerInfo *new_finger_entry;
2091 struct FriendInfo *first_friend_trail;
2094 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2095 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2097 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2098 (const void **)&existing_finger))
2100 if (PREDECESSOR_FINGER_ID == existing_finger->finger_map_index)
2102 if( GNUNET_NO == select_closest_finger (existing_finger, peer, trail,
2103 trail_length,PREDECESSOR_FINGER_ID))
2110 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2112 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2113 memcpy (&(new_finger_entry->finger_identity), peer, sizeof (struct GNUNET_PeerIdentity));
2114 new_finger_entry->finger_map_index = PREDECESSOR_FINGER_ID;
2115 new_finger_entry->first_trail_length = trail_length;
2116 new_finger_entry->trail_count = 1;
2118 if (trail != NULL) /* finger_trail is NULL in case I am my own finger identity. */
2120 /* FIXME: Currently we are not handling the second trail. In that case, finger
2121 trail count = min (first_friend, second_friend) trail count. */
2122 /* Incrementing the friend trails count. */
2123 if (trail_length > 0)
2125 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
2126 first_friend_trail->trails_count++;
2130 /* It means the finger is my friend. */
2131 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2132 first_friend_trail->trails_count++;
2134 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2136 /* Invert the trail and then add. */
2137 if (trail_length != 0)
2139 i = trail_length - 1;
2142 struct TrailPeerList *element;
2143 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2144 element->next = NULL;
2145 element->prev = NULL;
2147 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
2148 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2151 struct TrailPeerList *element;
2152 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2153 element->next = NULL;
2154 element->prev = NULL;
2155 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
2156 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2159 GNUNET_assert (GNUNET_OK ==
2160 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2161 &(new_finger_entry->finger_identity),
2163 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
2170 * FIXME: Better name, and make the code more cleaner.
2171 * Compare the new finger entry added and our successor.
2172 * @return #GNUNET_YES if same.
2173 * #GNUNET_NO if not.
2176 compare_new_entry_and_successor (const struct GNUNET_PeerIdentity *new_finger,
2177 int finger_map_index)
2179 int successor_flag = 0;
2180 struct FingerInfo *successor_finger;
2181 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2184 if (PREDECESSOR_FINGER_ID == finger_map_index)
2187 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2188 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2190 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2191 (const void **)&successor_finger))
2193 if (successor_finger->finger_map_index == 0)
2200 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2202 /* Ideally we should never reach here. */
2203 if (successor_flag == 0)
2209 if (0 == GNUNET_CRYPTO_cmp_peer_identity (new_finger, &(successor_finger->finger_identity)))
2217 * Add a new entry in finger table.
2218 * @param finger_identity PeerIdentity of the new finger
2219 * @param finger_trail Trail to reach to the finger, can be NULL in case I am my own
2221 * @param finger_trail_length Number of peers in the trail, can be 0 in case finger
2222 * is a friend or I am my own finger.
2223 * @param finger_map_index Index in finger map.
2226 add_new_entry (const struct GNUNET_PeerIdentity *finger_identity,
2227 struct GNUNET_PeerIdentity *finger_trail,
2228 uint32_t finger_trail_length,
2229 uint32_t finger_map_index)
2231 struct FriendInfo *first_friend_trail;
2232 struct FingerInfo *new_finger_entry;
2235 /* Add a new entry. */
2236 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2237 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
2238 new_finger_entry->finger_map_index = finger_map_index;
2239 new_finger_entry->first_trail_length = finger_trail_length;
2240 new_finger_entry->trail_count = 1;
2242 if (finger_trail != NULL) /* finger_trail is NULL in case I am my own finger identity. */
2244 /* Incrementing the friend trails count. */
2245 if (finger_trail_length > 0)
2247 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_trail[0]);
2248 first_friend_trail->trails_count++;
2252 /* It means the finger is my friend. */
2253 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger_identity);
2254 first_friend_trail->trails_count++;
2256 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2258 /* Copy the trail. */
2260 while (i < finger_trail_length)
2262 struct TrailPeerList *element;
2263 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2264 element->next = NULL;
2265 element->prev = NULL;
2267 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
2268 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2273 return GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2274 &(new_finger_entry->finger_identity),
2276 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
2280 /**1. Should we check if there is already an entry for same finger id in the finger
2281 * peermap as we are checking for index. I think its too much of code and the use
2282 * of having unique identifier in finger map is only in case of find_successor
2283 * but anyways we will find the correct successor.
2284 * 2. you don't handle the second trail here as in new entry you will have only
2285 * one trail to reach to the finger.
2286 * Add an entry in the finger table. If there is already an existing entry in
2287 * the finger peermap for given finger map index, then choose the closest one.
2288 * In case both the new entry and old entry are same, store both of them. (Redundant
2290 * @param finger_identity
2291 * @param finger_trail
2292 * @param finger_trail_length
2293 * @param finger_map_index
2294 * @return #GNUNET_YES if the new entry is added.
2295 * #GNUNET_NO if the new entry is discarded.
2298 int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
2299 struct GNUNET_PeerIdentity *finger_trail,
2300 uint32_t finger_trail_length,
2301 uint32_t finger_map_index)
2303 struct FingerInfo *existing_finger;
2304 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2306 int new_entry_added = GNUNET_NO;
2308 if (PREDECESSOR_FINGER_ID == finger_map_index)
2310 /* FIXME: Here GNUNET_NO, means that we did not update predecessor . But it
2311 we also need to handle the case that insertion failed in peer map after we decided to add
2313 if( GNUNET_YES == compare_and_update_predecessor (finger_identity, finger_trail, finger_trail_length))
2314 new_entry_added = GNUNET_YES;
2315 goto update_current_search_finger_index;
2318 /* Check if there is already an entry for the finger map index in the finger peer map. */
2319 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2320 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2322 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2323 (const void **)&existing_finger))
2325 if (existing_finger->finger_map_index == finger_map_index)
2327 if ( GNUNET_NO == select_closest_finger (existing_finger, finger_identity,
2328 finger_trail, finger_trail_length,
2330 goto update_current_search_finger_index;
2336 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2337 /* SUPU: in this case you get GNUNET_NO, only when insertion fails in the peer map.
2338 so its an error as we already have decided to add the entry into finger peer map. */
2339 if(GNUNET_OK == add_new_entry (finger_identity,finger_trail,finger_trail_length, finger_map_index))
2340 new_entry_added = GNUNET_YES;
2344 update_current_search_finger_index:
2345 if (0 == finger_map_index)
2347 current_search_finger_index = PREDECESSOR_FINGER_ID;
2348 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity))
2349 send_verify_successor_message();
2351 else if (GNUNET_YES == compare_new_entry_and_successor (finger_identity,finger_map_index))
2353 current_search_finger_index = 0;
2357 current_search_finger_index = current_search_finger_index - 1;
2361 return new_entry_added;
2366 * FIXME: In case a friend is either congested or has crossed its trail threshold,
2367 * then don't consider it as next successor, In case of finger if its first
2368 * friend has crossed the threshold then don't consider it. In case no finger
2369 * or friend is found, then return NULL.
2370 * Find closest successor for the value.
2371 * @param value Value for which we are looking for successor
2372 * @param[out] current_destination set to my_identity in case I am the final destination,
2373 * set to friend identity in case friend is final destination,
2374 * set to first friend to reach to finger, in case finger
2375 * is final destination.
2376 * @param[out] current_source set to my_identity.
2377 * @return Peer identity of next hop to send trail setup message to,
2378 * NULL in case all the friends are either congested or have crossed
2379 * their trail threshold.
2381 static struct GNUNET_PeerIdentity *
2382 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
2383 struct GNUNET_PeerIdentity *current_source)
2385 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
2386 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2387 struct GNUNET_PeerIdentity key_ret;
2388 struct FriendInfo *friend;
2389 struct FingerInfo *finger;
2390 unsigned int finger_index;
2391 unsigned int friend_index;
2392 struct Sorting_List *successor;
2396 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
2397 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
2398 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
2401 struct Sorting_List all_known_peers[size];
2404 for (k = 0; k < size; k++)
2405 all_known_peers[k].peer_id = 0;
2407 /* Copy your identity at 0th index in all_known_peers. */
2409 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
2410 all_known_peers[j].type = MY_ID;
2411 all_known_peers[j].data = 0;
2415 all_known_peers[j].peer_id = value;
2416 all_known_peers[j].type = VALUE;
2417 all_known_peers[j].data = 0;
2420 /* Iterate over friend peer map and copy all the elements into array. */
2421 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2422 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
2424 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
2426 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
2427 all_known_peers[j].type = FRIEND;
2428 all_known_peers[j].data = friend;
2434 /* Iterate over finger map and copy all the entries into all_known_peers array. */
2435 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2436 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2438 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
2440 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
2441 all_known_peers[j].type = FINGER;
2442 all_known_peers[j].data = finger;
2447 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2448 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
2451 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
2453 /* search value in all_known_peers array. */
2454 successor = find_closest_successor (all_known_peers, value, size);
2456 if (successor->type == MY_ID)
2458 memcpy (current_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2459 return &my_identity;
2461 else if (successor->type == FRIEND)
2463 struct FriendInfo *target_friend;
2464 target_friend = (struct FriendInfo *)successor->data;
2465 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
2466 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2467 return current_destination;
2469 else if (successor->type == FINGER)
2471 struct GNUNET_PeerIdentity *next_hop;
2472 struct FingerInfo *finger;
2473 finger = successor->data;
2474 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2476 if (finger->first_trail_length > 0)
2478 struct TrailPeerList *iterator;
2479 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2480 iterator = finger->first_trail_head;
2481 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2483 else /* This means finger is our friend. */
2484 memcpy (next_hop, &(finger->finger_identity), sizeof(struct GNUNET_PeerIdentity));
2486 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
2487 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2499 * Construct a Put message and send it to target_peer.
2500 * @param key Key for the content
2501 * @param data Content to store
2502 * @param data_size Size of content @a data in bytes
2503 * @param block_type Type of the block
2504 * @param options Routing options
2505 * @param desired_replication_level Desired replication count
2506 * @param expiration_time When does the content expire
2507 * @param current_destination
2508 * @param current_source
2509 * @param target_peer Peer to which this message will be forwarded.
2510 * @param hop_count Number of hops traversed so far.
2511 * @param put_path_length Total number of peers in @a put_path
2512 * @param put_path Number of peers traversed so far
2515 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2516 const void *data, size_t data_size,
2517 enum GNUNET_BLOCK_Type block_type,
2518 enum GNUNET_DHT_RouteOption options,
2519 uint32_t desired_replication_level,
2520 struct GNUNET_TIME_Absolute expiration_time,
2521 struct GNUNET_PeerIdentity current_destination,
2522 struct GNUNET_PeerIdentity current_source,
2523 struct GNUNET_PeerIdentity *target_peer,
2525 uint32_t put_path_length,
2526 struct GNUNET_PeerIdentity *put_path)
2528 struct PeerPutMessage *ppm;
2529 struct P2PPendingMessage *pending;
2530 struct FriendInfo *target_friend;
2531 struct GNUNET_PeerIdentity *pp;
2534 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2535 sizeof (struct PeerPutMessage);
2537 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2539 put_path_length = 0;
2540 msize = data_size + sizeof (struct PeerPutMessage);
2543 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2549 /* This is the first call made from clients file. So, we should search for the
2551 if (NULL == target_peer)
2554 struct GNUNET_PeerIdentity *next_hop;
2556 memcpy (&key_value, key, sizeof (uint64_t));
2557 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2559 if (0 == GNUNET_CRYPTO_cmp_peer_identity(next_hop, ¤t_destination)) /* I am the destination do datacache_put */
2561 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
2562 block_type, data_size, data);
2566 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2569 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2570 pending->timeout = expiration_time;
2571 ppm = (struct PeerPutMessage *) &pending[1];
2572 pending->msg = &ppm->header;
2573 ppm->header.size = htons (msize);
2574 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
2575 ppm->options = htonl (options);
2576 ppm->block_type = htonl (block_type);
2577 ppm->hop_count = htonl (hop_count + 1);
2578 ppm->desired_replication_level = htonl (desired_replication_level);
2579 ppm->put_path_length = htonl (put_path_length);
2580 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2582 ppm->current_destination = current_destination;
2583 ppm->current_source = current_source;
2585 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2586 if (put_path_length != 0)
2588 memcpy (pp, put_path,
2589 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2591 memcpy (&pp[put_path_length], data, data_size);
2592 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2593 target_friend->pending_count++;
2594 process_friend_queue (target_friend);
2600 * Construct a Get message and send it to target_peer.
2601 * @param key Key for the content
2602 * @param block_type Type of the block
2603 * @param options Routing options
2604 * @param desired_replication_level Desired replication count
2605 * @param expiration_time When does the content expire
2606 * @param current_destination
2607 * @param current_source
2608 * @param target_peer Peer to which this message will be forwarded.
2609 * @param hop_count Number of hops traversed so far.
2610 * @param put_path_length Total number of peers in @a put_path
2611 * @param put_path Number of peers traversed so far
2614 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2615 enum GNUNET_BLOCK_Type block_type,
2616 enum GNUNET_DHT_RouteOption options,
2617 uint32_t desired_replication_level,
2618 struct GNUNET_PeerIdentity current_destination,
2619 struct GNUNET_PeerIdentity current_source,
2620 struct GNUNET_PeerIdentity *target_peer,
2622 uint32_t get_path_length,
2623 struct GNUNET_PeerIdentity *get_path)
2625 struct PeerGetMessage *pgm;
2626 struct P2PPendingMessage *pending;
2627 struct FriendInfo *target_friend;
2628 struct GNUNET_PeerIdentity *gp;
2631 msize = sizeof (struct PeerGetMessage) +
2632 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2634 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2640 if (NULL == target_peer)
2642 /* This is the first call from client file, we need to search for next_hop*/
2643 struct GNUNET_PeerIdentity *next_hop;
2646 memcpy (&key_value, key, sizeof (uint64_t));
2647 // FIXME: endianess of key_value!?
2648 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2650 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity,next_hop)) /* I am the destination do datacache_put */
2652 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2653 NULL, 0, 1, &my_identity, NULL,&my_identity);
2658 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2662 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2663 pending->importance = 0; /* FIXME */
2664 pgm = (struct PeerGetMessage *) &pending[1];
2665 pending->msg = &pgm->header;
2666 pgm->header.size = htons (msize);
2667 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2668 pgm->get_path_length = htonl (get_path_length);
2670 pgm->current_destination = current_destination;
2671 pgm->current_source = current_source;
2672 pgm->hop_count = htonl (hop_count + 1);
2676 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2677 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2679 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2680 target_friend->pending_count++;
2681 process_friend_queue (target_friend);
2686 * Send the get result to requesting client.
2687 * @param expiration When will this result expire?
2688 * @param key Key of the requested data.
2689 * @param put_path_length Number of peers in @a put_path
2690 * @param put_path Path taken to put the data at its stored location.
2691 * @param type Block type
2692 * @param data_size Size of the @a data
2693 * @param data Payload to store
2694 * @param get_path Path taken to reach to the location of the key.
2695 * @param get_path_length Number of peers in @a get_path
2696 * @param next_hop Next peer to forward the message to.
2697 * @param source_peer Peer which has the data for the key.
2700 GDS_NEIGHBOURS_send_get_result (struct GNUNET_TIME_Absolute expiration,
2701 const struct GNUNET_HashCode *key,
2702 unsigned int put_path_length,
2703 const struct GNUNET_PeerIdentity *put_path,
2704 enum GNUNET_BLOCK_Type type, size_t data_size,
2706 struct GNUNET_PeerIdentity *get_path,
2707 unsigned int get_path_length,
2708 struct GNUNET_PeerIdentity *next_hop,
2709 struct GNUNET_PeerIdentity *source_peer)
2711 struct PeerGetResultMessage *get_result;
2712 struct GNUNET_PeerIdentity *get_result_path;
2713 struct GNUNET_PeerIdentity *pp;
2714 struct P2PPendingMessage *pending;
2715 struct FriendInfo *target_friend;
2716 int current_path_index;
2719 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2720 sizeof (struct PeerPutMessage);
2722 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2728 current_path_index = search_my_index(get_path, get_path_length);
2729 if (GNUNET_SYSERR == current_path_index)
2734 if (0 == current_path_index)
2736 GDS_CLIENTS_handle_reply (expiration, key, get_path_length, get_path, put_path_length,
2737 put_path, type, data_size, data);
2741 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2742 pending->importance = 0;
2743 get_result = (struct PeerGetResultMessage *)&pending[1];
2744 pending->msg = &get_result->header;
2745 get_result->header.size = htons (msize);
2746 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2747 get_result->key = *key;
2748 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2749 get_result->expiration_time = expiration;
2751 if (get_path_length != 0)
2753 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2754 memcpy (get_result_path, get_path,
2755 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2757 memcpy (&get_result_path[get_path_length], data, data_size);
2759 /* FIXME: Is this correct? */
2760 if (put_path_length != 0)
2762 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2763 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2765 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2766 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2767 target_friend->pending_count++;
2768 process_friend_queue (target_friend);
2773 * Send trail rejection message to the peer which sent me a trail setup message.
2774 * @param source_peer Source peer which wants to set up the trail.
2775 * @param finger_identity Value whose successor will be the finger of @a source_peer.
2776 * @param congested_peer Peer which has send trail rejection message.
2777 * @param next_hop Peer to which this message should be forwarded.
2778 * @param finger_map_index Index in @a source_peer finger peermap.
2779 * @param trail_peer_list Trail followed to reach from @a source_peer to next_hop,
2780 * NULL, in case the @a congested_peer was the first peer
2781 * to which trail setup message was forwarded.
2782 * @param trail_length Number of peers in trail_peer_list.
2785 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity *source_peer,
2786 uint64_t finger_identity,
2787 struct GNUNET_PeerIdentity *congested_peer,
2788 const struct GNUNET_PeerIdentity *next_hop,
2789 unsigned int finger_map_index,
2790 struct GNUNET_PeerIdentity *trail_peer_list,
2791 unsigned int trail_length)
2793 struct PeerTrailRejectionMessage *trail_rejection;
2794 struct GNUNET_PeerIdentity *trail_list;
2795 struct P2PPendingMessage *pending;
2796 struct FriendInfo *target_friend;
2799 msize = trail_length * sizeof(struct GNUNET_PeerIdentity) +
2800 sizeof (struct PeerTrailRejectionMessage);
2802 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2808 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2809 pending->importance = 0;
2810 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2811 trail_rejection = (struct PeerTrailRejectionMessage *) &pending[1];
2812 pending->msg = &trail_rejection->header;
2813 trail_rejection->header.size = htons (msize);
2814 trail_rejection->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
2815 memcpy (&(trail_rejection->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2816 memcpy (&(trail_rejection->congested_peer), congested_peer, sizeof (struct GNUNET_PeerIdentity));
2817 memcpy (&(trail_rejection->finger_identity_value), &finger_identity, sizeof (uint64_t));
2818 trail_rejection->finger_map_index = htonl(finger_map_index);
2819 trail_rejection->trail_length = htonl (trail_length);
2821 if (trail_length != 0)
2823 trail_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2824 memcpy (trail_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2827 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2828 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2829 target_friend->pending_count++;
2830 process_friend_queue (target_friend);
2835 * Core handler for P2P put messages.
2836 * @param cls closure
2837 * @param peer sender of the request
2838 * @param message message
2839 * @return #GNUNET_OK to keep the connection open,
2840 * #GNUNET_SYSERR to close it (signal serious error)
2843 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2844 const struct GNUNET_MessageHeader *message)
2846 struct PeerPutMessage *put;
2847 struct GNUNET_PeerIdentity *put_path;
2848 struct GNUNET_HashCode test_key;
2849 enum GNUNET_DHT_RouteOption options;
2850 struct GNUNET_PeerIdentity current_destination;
2851 struct GNUNET_PeerIdentity current_source;
2852 struct GNUNET_PeerIdentity *next_hop;
2856 size_t payload_size;
2859 msize = ntohs (message->size);
2860 if (msize < sizeof (struct PeerPutMessage))
2862 GNUNET_break_op (0);
2866 put = (struct PeerPutMessage *) message;
2867 putlen = ntohl (put->put_path_length);
2870 sizeof (struct PeerPutMessage) +
2871 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2873 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2875 GNUNET_break_op (0);
2879 current_destination = put->current_destination;
2880 current_source = put->current_source;
2881 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2882 payload = &put_path[putlen];
2883 options = ntohl (put->options);
2884 payload_size = msize - (sizeof (struct PeerPutMessage) +
2885 putlen * sizeof (struct GNUNET_PeerIdentity));
2887 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
2888 payload, payload_size, &test_key))
2891 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
2893 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
2894 GNUNET_break_op (0);
2895 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2896 "PUT with key `%s' for block with key %s\n",
2897 put_s, GNUNET_h2s_full (&test_key));
2898 GNUNET_free (put_s);
2903 GNUNET_break_op (0);
2906 /* cannot verify, good luck */
2910 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
2912 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
2913 ntohl (put->block_type),
2915 NULL, 0, /* bloom filer */
2916 NULL, 0, /* xquery */
2917 payload, payload_size))
2919 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2920 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2923 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2924 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2925 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
2926 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2927 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2928 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2930 GNUNET_break_op (0);
2935 struct GNUNET_PeerIdentity pp[putlen + 1];
2936 /* extend 'put path' by sender */
2937 /* FIXME: Check what are we doing here? */
2938 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
2940 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
2947 memcpy (&key_value, &(put->key), sizeof (uint64_t));
2948 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2950 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2951 if (next_hop == NULL)
2953 /* refer to handle_dht_p2p_trail_setup. */
2958 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2961 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop)) /* I am the final destination */
2963 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
2964 &(put->key),putlen, pp, ntohl (put->block_type),
2965 payload_size, payload);
2970 GDS_CLIENTS_process_put (options,
2971 ntohl (put->block_type),
2972 ntohl (put->hop_count),
2973 ntohl (put->desired_replication_level),
2975 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2980 GDS_NEIGHBOURS_send_put (&put->key, payload, payload_size,
2981 ntohl (put->block_type),ntohl (put->options),
2982 ntohl (put->desired_replication_level),
2983 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2984 current_destination, current_source, next_hop,
2985 ntohl (put->hop_count), putlen, pp);
2989 return GNUNET_SYSERR;
2994 * Core handler for p2p get requests.
2996 * @param cls closure
2997 * @param peer sender of the request
2998 * @param message message
2999 * @return #GNUNET_OK to keep the connection open,
3000 * #GNUNET_SYSERR to close it (signal serious error)
3003 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3004 const struct GNUNET_MessageHeader *message)
3006 struct PeerGetMessage *get;
3007 struct GNUNET_PeerIdentity *get_path;
3008 struct GNUNET_PeerIdentity current_destination;
3009 struct GNUNET_PeerIdentity current_source;
3010 struct GNUNET_PeerIdentity *next_hop;
3011 uint32_t get_length;
3015 msize = ntohs (message->size);
3016 if (msize < sizeof (struct PeerGetMessage))
3018 GNUNET_break_op (0);
3022 get = (struct PeerGetMessage *)message;
3023 get_length = ntohl (get->get_path_length);
3024 get_path = (struct GNUNET_PeerIdentity *)&get[1];
3025 current_destination = get->current_destination;
3026 current_source = get->current_source;
3029 sizeof (struct PeerGetMessage) +
3030 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3032 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3034 GNUNET_break_op (0);
3038 /* Add sender to get path */
3039 struct GNUNET_PeerIdentity gp[get_length + 1];
3040 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3041 gp[get_length + 1] = *peer;
3042 get_length = get_length + 1;
3044 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3045 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3047 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3048 if (next_hop == NULL)
3050 /* refer to handle_dht_p2p_trail_setup. */
3055 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
3058 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop))
3060 /* I am the destination.*/
3061 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3062 struct GNUNET_PeerIdentity next_hop;
3064 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3065 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3066 get_length = get_length + 1;
3067 memcpy (&next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
3069 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3070 get_length, final_get_path,&next_hop, &my_identity);
3076 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3077 get->desired_replication_level,current_destination,
3078 current_source, next_hop, 0,
3081 return GNUNET_SYSERR;
3086 * FIXME: In case of trail, we don't have source and destination part of the trail,
3087 * Check if we follow the same in case of get/put/get_result. Also, in case of
3088 * put should we do a routing table add.
3089 * Core handler for get result
3090 * @param cls closure
3091 * @param peer sender of the request
3092 * @param message message
3093 * @return #GNUNET_OK to keep the connection open,
3094 * #GNUNET_SYSERR to close it (signal serious error)
3097 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3098 const struct GNUNET_MessageHeader *message)
3100 struct PeerGetResultMessage *get_result;
3101 struct GNUNET_PeerIdentity *get_path;
3102 struct GNUNET_PeerIdentity *put_path;
3104 size_t payload_size;
3106 unsigned int getlen;
3107 unsigned int putlen;
3108 int current_path_index;
3110 msize = ntohs (message->size);
3111 if (msize < sizeof (struct PeerGetResultMessage))
3113 GNUNET_break_op (0);
3117 get_result = (struct PeerGetResultMessage *)message;
3118 getlen = ntohl (get_result->get_path_length);
3119 putlen = ntohl (get_result->put_path_length);
3122 sizeof (struct PeerGetResultMessage) +
3123 getlen * sizeof (struct GNUNET_PeerIdentity) +
3124 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3126 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3128 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3130 GNUNET_break_op (0);
3134 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
3135 payload = &get_path[getlen];
3136 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3137 getlen * sizeof (struct GNUNET_PeerIdentity));
3138 /* FIXME: Check if its correct or not. */
3141 put_path = &get_path[1];
3145 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3147 //GDS_CLIENTS_process_get_result();
3148 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3149 getlen, get_path, putlen,
3150 put_path, get_result->type, payload_size, payload);
3155 struct GNUNET_PeerIdentity *next_hop;
3156 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3157 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3158 current_path_index = search_my_index (get_path, getlen);
3159 /* FIXME: First check if you are adding yourself to the get path or not.
3160 if yes then don't check if current_path_index == 0, if not then check
3161 and next_hop == source_peer. */
3162 memcpy (next_hop, &get_path[current_path_index - 1], sizeof (struct GNUNET_PeerIdentity));
3164 GDS_NEIGHBOURS_send_get_result (get_result->expiration_time, &(get_result->key),
3166 get_result->type, payload_size,payload,
3168 next_hop, &(get_result->source_peer));
3171 return GNUNET_SYSERR;
3176 * FIXME: Is all trails threshold and routing table has some link.
3177 * Core handle for PeerTrailSetupMessage.
3178 * @param cls closure
3179 * @param message message
3180 * @param peer peer identity this notification is about
3181 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3184 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3185 const struct GNUNET_MessageHeader *message)
3187 const struct PeerTrailSetupMessage *trail_setup;
3188 struct GNUNET_PeerIdentity current_destination;
3189 struct GNUNET_PeerIdentity current_source;
3190 struct GNUNET_PeerIdentity source;
3191 struct GNUNET_PeerIdentity *next_hop;
3192 struct GNUNET_PeerIdentity next_peer;
3193 struct GNUNET_PeerIdentity *trail_peer_list;
3194 struct FriendInfo *target_friend;
3195 uint64_t destination_finger_value;
3196 uint32_t trail_length;
3197 uint32_t finger_map_index;
3200 msize = ntohs (message->size);
3201 if (msize < sizeof (struct PeerTrailSetupMessage))
3203 GNUNET_break_op (0);
3207 trail_setup = (const struct PeerTrailSetupMessage *) message;
3208 trail_length = ntohl (trail_setup->trail_length);
3210 if ((msize < sizeof (struct PeerTrailSetupMessage) +
3211 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3213 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3215 GNUNET_break_op (0);
3219 if (trail_length > 0)
3220 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
3221 memcpy (¤t_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity));
3222 memcpy (¤t_source,&(trail_setup->current_source), sizeof (struct GNUNET_PeerIdentity));
3223 memcpy (&source, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity));
3224 finger_map_index = ntohl (trail_setup->finger_map_index);
3225 destination_finger_value = ntohl (trail_setup->destination_finger);
3228 /* FIXME: Here we need to check 3 things
3229 * 1. if my routing table is all full
3230 * 2. if all my friends are congested
3231 * 3. if trail threshold of my friends have crossed.
3232 * In all these cases we need to send back trail rejection message. */
3233 if ( (GNUNET_YES == all_friends_trail_threshold)
3234 || (GNUNET_YES == GDS_ROUTING_check_threshold()))
3236 /* If all the friends have reached their trail threshold or if there is no
3237 more space in routing table to store more trails, then reject. */
3238 GDS_NEIGHBOURS_send_trail_rejection (&source, destination_finger_value, &my_identity,
3239 peer,finger_map_index, trail_peer_list,trail_length);
3245 /* Check if you are current_destination or not. */
3246 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3248 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3249 /* OPTIMIZATION: Choose a peer from find_successor and choose the closest one.
3250 In case the closest one is from routing table and it is NULL, then update
3252 if (next_hop == NULL)
3254 /* FIXME: Should we inform the peer before us. If not then it may continue
3255 to send us request. But in case we want to inform we need to have a
3256 different kind of message. */
3257 GNUNET_STATISTICS_update (GDS_stats,
3258 gettext_noop ("# Trail not found in routing table during"
3259 "trail setup request, packet dropped."),
3266 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
3269 if (NULL == next_hop)
3271 return GNUNET_SYSERR;
3273 else if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
3275 if (trail_length == 0)
3277 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
3281 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3284 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3286 /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
3287 if (PREDECESSOR_FINGER_ID != finger_map_index)
3289 /* FIXME: Is this correct assumption? A peer which think I am its predecessor,
3290 then I am not its predecessor. */
3291 compare_and_update_predecessor (&source, trail_peer_list, trail_length );
3293 GDS_NEIGHBOURS_send_trail_setup_result (&source,
3295 target_friend, trail_length,
3302 /* Now add yourself to the trail. */
3303 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3304 if (trail_length != 0)
3305 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3306 peer_list[trail_length] = my_identity;
3309 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3310 GDS_NEIGHBOURS_send_trail_setup (&source,
3311 destination_finger_value,
3312 ¤t_destination, ¤t_source,
3313 target_friend, trail_length, peer_list,
3321 * Core handle for p2p trail construction result messages.
3323 * @param message message
3324 * @param peer peer identity this notification is about
3325 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3328 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3329 const struct GNUNET_MessageHeader *message)
3331 const struct PeerTrailSetupResultMessage *trail_result;
3332 struct GNUNET_PeerIdentity *trail_peer_list;
3333 uint32_t trail_length;
3334 uint32_t finger_map_index;
3337 msize = ntohs (message->size);
3338 if (msize < sizeof (struct PeerTrailSetupResultMessage))
3340 GNUNET_break_op (0);
3344 trail_result = (const struct PeerTrailSetupResultMessage *) message;
3345 trail_length = ntohl (trail_result->trail_length);
3348 sizeof (struct PeerTrailSetupResultMessage) +
3349 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3351 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3353 GNUNET_break_op (0);
3357 finger_map_index = htonl (trail_result->finger_map_index);
3358 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
3360 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3363 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
3369 struct GNUNET_PeerIdentity next_hop;
3370 struct FriendInfo *target_friend;
3373 my_index = search_my_index (trail_peer_list, trail_length);
3374 if (my_index == GNUNET_SYSERR)
3375 return GNUNET_SYSERR;
3379 next_hop = trail_result->destination_peer;
3382 next_hop = trail_peer_list[my_index - 1];
3384 /* Finger table of destination peer will not contain any trail for the case
3385 * where destination peer is its own finger identity.*/
3386 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3387 &(trail_result->finger_identity))))
3389 GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
3393 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3394 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
3395 &(trail_result->finger_identity),
3396 target_friend, trail_length,
3401 return GNUNET_SYSERR;
3406 * Get my current predecessor from the finger peer map
3407 * @return Current predecessor.
3409 static struct FingerInfo *
3412 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
3413 struct GNUNET_PeerIdentity key_ret;
3414 unsigned int finger_index;
3415 struct FingerInfo *my_predecessor;
3418 /* Iterate over finger peer map and extract your predecessor. */
3419 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
3420 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
3422 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
3423 (finger_iter,&key_ret,(const void **)&my_predecessor))
3425 if(PREDECESSOR_FINGER_ID == my_predecessor->finger_map_index)
3432 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
3437 return my_predecessor;
3442 * Core handle for p2p verify successor messages.
3443 * @param cls closure
3444 * @param message message
3445 * @param peer peer identity this notification is about
3446 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3449 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3450 const struct GNUNET_MessageHeader *message)
3452 const struct PeerVerifySuccessorMessage *vsm;
3453 const struct GNUNET_PeerIdentity *trail_peer_list;
3454 struct GNUNET_PeerIdentity source_peer;
3455 struct GNUNET_PeerIdentity next_hop;
3456 struct FriendInfo *target_friend;
3458 uint32_t trail_length;
3460 msize = ntohs (message->size);
3461 if (msize < sizeof (struct PeerVerifySuccessorMessage))
3463 GNUNET_break_op (0);
3467 vsm = (struct PeerVerifySuccessorMessage *) message;
3468 trail_length = ntohl (vsm->trail_length);
3470 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
3471 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3472 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3474 GNUNET_break_op (0);
3477 if (trail_length > 0)
3478 trail_peer_list = (const struct GNUNET_PeerIdentity *)&vsm[1];
3479 memcpy (&source_peer, &(vsm->source_peer), sizeof(struct GNUNET_PeerIdentity));
3481 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
3483 struct FingerInfo *my_predecessor;
3484 if (trail_length == 0)
3486 /* SUPU: If I am friend of source_peer, then trail_length == 0. */
3487 memcpy (&next_hop, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3491 /* SUPU: Here I am the final destination successor, and trail does not contain
3492 destination. So, the next hop is the last element in the trail. */
3493 memcpy (&next_hop, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3495 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3497 my_predecessor = get_predecessor();
3498 if (NULL == my_predecessor)
3501 return GNUNET_SYSERR;
3504 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3505 &(my_predecessor->finger_identity))))
3507 /* Source peer and my predecessor, both are same. */
3508 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3510 &(my_predecessor->finger_identity),
3517 struct GNUNET_PeerIdentity *new_successor_trail;
3518 struct TrailPeerList *iterator;
3519 int new_trail_length;
3522 new_trail_length = trail_length + my_predecessor->first_trail_length + 1;
3523 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
3524 if (trail_length > 0)
3525 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
3527 memcpy (&new_successor_trail[trail_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3529 if (my_predecessor->first_trail_length)
3531 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
3532 iterator = my_predecessor->first_trail_head;
3533 i = trail_length + 1;
3534 while (i < new_trail_length)
3536 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
3537 iterator = iterator->next;
3541 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3543 &(my_predecessor->finger_identity),
3545 new_successor_trail,
3554 my_index = search_my_index (trail_peer_list, trail_length);
3555 if (my_index == GNUNET_SYSERR)
3558 return GNUNET_SYSERR;
3560 if (my_index == (trail_length - 1))
3562 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(vsm->successor));
3566 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3567 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3570 GDS_NEIGHBOURS_send_verify_successor (&(vsm->source_peer), &(vsm->successor),target_friend,
3571 trail_peer_list, trail_length);
3573 return GNUNET_SYSERR;
3577 /**FIXME: in case we have a new successor do we need to update the entries in
3578 * routing table to change the destination of the message from old successor
3579 * to new successor or when the old successor sends the message the I am not
3580 * your successor then it sends a trail teardown message across the old trail.
3581 * Need to decide on a strategy.
3582 * Core handle for p2p verify successor result messages.
3583 * @param cls closure
3584 * @param message message
3585 * @param peer peer identity this notification is about
3586 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3589 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3590 const struct GNUNET_MessageHeader *message)
3592 const struct PeerVerifySuccessorResultMessage *vsrm;
3593 struct GNUNET_PeerIdentity *trail_peer_list;
3594 struct GNUNET_PeerIdentity next_hop;
3595 struct FriendInfo *target_friend;
3597 uint32_t trail_length;
3599 msize = ntohs (message->size);
3600 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
3602 GNUNET_break_op (0);
3605 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
3606 trail_length = ntohl (vsrm->trail_length);
3609 sizeof (struct PeerVerifySuccessorResultMessage) +
3610 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3612 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3614 GNUNET_break_op (0);
3617 /* FIXME: URGENT: What happens when trail length = 0. */
3619 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
3621 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity))))
3623 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
3625 /* FIXME: Here we have got a new successor. But it may happen that our logic
3626 * says that this is not correct successor. so in finger table add it
3627 * failed to update the successor and we are still sending a notify
3628 * new successor. Here trail_length will be atleast 1, in case we have a new
3629 * successor because in that case our old successor is part of trail.
3630 * Could it be possible that our identity and my_predecessor is same. Check it. */
3631 if (GNUNET_YES == finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0))
3633 memcpy (&next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
3634 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3635 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
3636 target_friend, trail_peer_list,
3644 return GNUNET_SYSERR;
3652 my_index = search_my_index (trail_peer_list, trail_length);
3653 if (GNUNET_SYSERR == my_index)
3656 return GNUNET_SYSERR;
3661 /* Source is not part of trail, so if I am the last one then my index
3663 memcpy (&next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3667 memcpy (&next_hop, &trail_peer_list[my_index-1], sizeof (struct GNUNET_PeerIdentity));
3670 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3671 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
3672 &(vsrm->source_successor),
3673 &(vsrm->my_predecessor),
3679 return GNUNET_SYSERR;
3684 * Core handle for p2p notify new successor messages.
3685 * @param cls closure
3686 * @param message message
3687 * @param peer peer identity this notification is about
3688 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3691 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3692 const struct GNUNET_MessageHeader *message)
3694 const struct PeerNotifyNewSuccessorMessage *nsm;
3695 struct GNUNET_PeerIdentity *trail_peer_list;
3697 uint32_t trail_length;
3699 msize = ntohs (message->size);
3700 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
3702 GNUNET_break_op (0);
3705 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
3706 trail_length = ntohl (nsm->trail_length);
3708 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3709 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3711 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3713 GNUNET_break_op (0);
3717 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
3719 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), &my_identity)))
3721 /* I am the new successor. */
3722 struct GNUNET_PeerIdentity new_predecessor;
3723 memcpy (&new_predecessor, &(nsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
3724 if (GNUNET_NO == compare_and_update_predecessor (&new_predecessor, trail_peer_list,
3727 /* Someone claims to be my predecessor but its not closest predecessor
3730 return GNUNET_SYSERR;
3736 struct FriendInfo *target_friend;
3737 struct GNUNET_PeerIdentity next_hop;
3740 my_index = search_my_index (trail_peer_list, trail_length);
3741 if (GNUNET_SYSERR == my_index)
3744 return GNUNET_SYSERR;
3747 if (my_index == (trail_length - 1))
3749 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(nsm->destination_peer));
3753 memcpy (&next_hop, &trail_peer_list[my_index+1], sizeof (struct GNUNET_PeerIdentity));
3754 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3756 /* FIXME: Should we update the entries in routing table? */
3757 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
3758 &(nsm->destination_peer),
3759 target_friend, trail_peer_list,
3763 return GNUNET_SYSERR;
3768 * FIXME; Should we call select_random_friend from here in case I am the source
3769 * of the message or should I just return and in next iteration by default
3770 * we will call select random friend from send_find_finger_trail. But in that
3771 * case we should maintain a list of congested peer which failed to setup the
3772 * trail. and then in select random friend we should ignore them. this list
3773 * should have an expiration time and we should garbage collect it periodically.
3774 * Core handler for P2P trail rejection message
3775 * @param cls closure
3776 * @param message message
3777 * @param peer peer identity this notification is about
3778 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3781 int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3782 const struct GNUNET_MessageHeader *message)
3784 /* Here you have recevied the message it means that the peer next to you have
3785 failed to setup the trail to the finger identity value. now you should call
3786 find_successor and make sure that you don't choose the peer as next hop
3787 in order to do so, you need to pass a new parameter to find successor,
3788 congested peer - a peer which you should ignore. once you have found this
3789 peer then just send a trail setup message to that peer. In case you are
3790 also congested then remove yourself from the trail as this message
3791 reached to as you are part of the trail. and then send the message to
3792 element before you. Ideally you should be the last element in the trail as
3793 all the the elements before you have rejected you. In case you are source,
3794 then you should call select_random_Friend(congested_peer). in case you don't
3795 find any peer because congested peer then set flag that all friends are busy
3797 const struct PeerTrailRejectionMessage *trail_rejection;
3798 struct GNUNET_PeerIdentity *trail_peer_list;
3799 struct GNUNET_PeerIdentity source_peer;
3800 struct GNUNET_PeerIdentity congested_peer;
3801 struct FriendInfo *target_friend;
3802 struct GNUNET_PeerIdentity next_peer;
3803 struct GNUNET_PeerIdentity *next_hop;
3804 struct GNUNET_PeerIdentity current_source;
3805 struct GNUNET_PeerIdentity current_destination;
3807 uint32_t trail_length;
3808 uint32_t finger_map_index;
3809 uint64_t destination_finger_value;
3811 msize = ntohs (message->size);
3812 if (msize < sizeof (struct PeerTrailRejectionMessage))
3814 GNUNET_break_op (0);
3818 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3819 trail_length = ntohl (trail_rejection->trail_length);
3821 if ((msize < sizeof (struct PeerTrailRejectionMessage) +
3822 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3824 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3826 GNUNET_break_op (0);
3830 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3831 finger_map_index = ntohl (trail_rejection->finger_map_index);
3832 memcpy (&source_peer, &(trail_rejection->source_peer), sizeof(struct GNUNET_PeerIdentity));
3833 memcpy (&destination_finger_value, &(trail_rejection->finger_identity_value), sizeof (uint64_t));
3834 memcpy (&congested_peer, &(trail_rejection->congested_peer), sizeof (struct GNUNET_PeerIdentity));
3836 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source_peer)))
3838 /* I am the source of original trail setup message. Do nothing and exit. */
3839 /* In current implementation, when we don't get the result of a trail setup,
3840 then no entry is added to finger table and hence, by default a trail setup for
3841 the same finger map index is sent. so we don't need to send it here. */
3845 if(GDS_ROUTING_check_threshold())
3847 /* My routing state size has crossed the threshold, I can not be part of any more
3849 struct GNUNET_PeerIdentity *new_trail;
3851 if (trail_length == 1)
3853 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3857 /* FIXME: Here if I got the trail rejection message then I am the last element
3858 in the trail. So, I should choose trail_length-2.*/
3859 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
3862 /* Remove myself from the trail. */
3863 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3864 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3866 /* No more trails possible through me. send a trail rejection message to next hop. */
3867 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
3868 &next_peer,finger_map_index, new_trail,trail_length - 1);
3872 memcpy (¤t_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
3873 memcpy (¤t_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
3874 /* FIXME: After adding a new field in struct FriendInfo congested, then call
3875 find successor then it will never consider that friend by default. */
3876 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
3878 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, ¤t_destination))) /* This means I am the final destination */
3880 if (trail_length == 1)
3882 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3886 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3889 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3890 compare_and_update_predecessor (&source_peer, trail_peer_list, trail_length);
3892 GDS_NEIGHBOURS_send_trail_setup_result (&source_peer,
3894 target_friend, trail_length,
3899 else if (NULL == next_hop)
3901 /* No peer found. Send a trail rejection message to previous peer in the trail. */
3903 struct GNUNET_PeerIdentity *new_trail;
3905 if (trail_length == 1)
3907 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3911 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
3914 /* Remove myself from the trail. */
3915 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3916 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3918 /* No more trails possible through me. send a trail rejection message to next hop. */
3919 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
3920 &next_peer,finger_map_index, new_trail,trail_length - 1);
3925 /* Now add yourself to the trail. */
3926 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3927 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3928 peer_list[trail_length] = my_identity;
3931 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3932 GDS_NEIGHBOURS_send_trail_setup (&source_peer,
3933 destination_finger_value,
3934 ¤t_destination, ¤t_source,
3935 target_friend, trail_length, peer_list,
3939 return GNUNET_SYSERR;
3943 /* Core handle for p2p trail tear down messages.
3944 * @param cls closure
3945 * @param message message
3946 * @param peer peer identity this notification is about
3947 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3950 int handle_dht_p2p_trail_teardown(void *cls, const struct GNUNET_PeerIdentity *peer,
3951 const struct GNUNET_MessageHeader *message)
3953 struct PeerTrailTearDownMessage *trail_teardown;
3954 struct GNUNET_PeerIdentity *discarded_trail;
3955 struct GNUNET_PeerIdentity next_hop;
3956 struct FriendInfo *target_friend;
3957 uint32_t discarded_trail_length;
3961 msize = ntohs (message->size);
3962 if (msize < sizeof (struct PeerTrailTearDownMessage))
3964 GNUNET_break_op (0);
3968 trail_teardown = (struct PeerTrailTearDownMessage *) message;
3969 discarded_trail_length = ntohl (trail_teardown->trail_length);
3971 if ((msize < sizeof (struct PeerTrailTearDownMessage) +
3972 discarded_trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3973 (discarded_trail_length >
3974 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3976 GNUNET_break_op (0);
3980 discarded_trail = (struct GNUNET_PeerIdentity *) &trail_teardown[1];
3982 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->new_first_friend),
3985 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer),
3993 * I am the new first hop in the trail to reach from source to destination.
3994 Update the trail in routing table with prev_hop == source peer. */
3999 my_index = search_my_index (discarded_trail, discarded_trail_length);
4000 if(GNUNET_SYSERR == my_index)
4001 return GNUNET_SYSERR;
4003 if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
4004 &(trail_teardown->destination_peer),peer))
4006 /* Here we get GNUNET_NO, only if there is no matching entry found in routing
4012 memcpy (&next_hop, &discarded_trail[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
4013 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4015 GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer),
4016 &(trail_teardown->destination_peer),
4017 discarded_trail, discarded_trail_length,
4018 target_friend, &(trail_teardown->new_first_friend));
4021 return GNUNET_SYSERR;
4027 * FIXME: we don't send trail teardown to finger for which the trail was setup.
4028 * Trail teardown only aim is to remove entries from the routing table. Destination
4029 * finger does not have any entry in its routing table. So, it does not need
4031 * Core handle for p2p trail tear down messages.
4032 * @param cls closure
4033 * @param message message
4034 * @param peer peer identity this notification is about
4035 * @return GNUNET_OK on success, GNUNET_SYSERR on error
4038 int handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
4039 const struct GNUNET_MessageHeader *message)
4041 struct PeerTrailTearDownMessage *trail_teardown;
4042 struct GNUNET_PeerIdentity *trail_peer_list;
4043 struct GNUNET_PeerIdentity next_hop;
4044 struct FriendInfo *target_friend;
4045 uint32_t trail_length;
4049 msize = ntohs (message->size);
4050 if (msize < sizeof (struct PeerTrailTearDownMessage))
4052 GNUNET_break_op (0);
4056 trail_teardown = (struct PeerTrailTearDownMessage *) message;
4057 trail_length = ntohl (trail_teardown->trail_length);
4059 if ((msize < sizeof (struct PeerTrailTearDownMessage) +
4060 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
4062 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
4064 GNUNET_break_op (0);
4068 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_teardown[1];
4070 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer), &my_identity)))
4072 /* I am the destination of the trail, but I am not part of trail. I don't
4073 need to remove any entry from my routing table. So, I should not get this
4079 my_index = search_my_index (trail_peer_list, trail_length);
4080 if(GNUNET_SYSERR == my_index)
4081 return GNUNET_SYSERR;
4083 if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
4084 &(trail_teardown->destination_peer),peer))
4086 /* Here we get GNUNET_NO, only if there is no matching entry found in routing
4092 /* I am the last element of the trail. */
4093 if(my_index == trail_length - 1)
4096 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
4097 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4098 /* FIXME:add a new field new_first_friend. */
4099 GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer),
4100 &(trail_teardown->destination_peer),
4101 trail_peer_list, trail_length, target_friend);
4107 * Iterate over finger_peermap, and remove entries with peer as the first element
4109 * @param cls closure
4110 * @param key current public key
4111 * @param value value in the hash map
4112 * @return #GNUNET_YES if we should continue to
4114 * #GNUNET_NO if not.
4117 remove_matching_finger (void *cls,
4118 const struct GNUNET_PeerIdentity *key,
4121 struct FingerInfo *remove_finger = value;
4122 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
4124 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->first_trail_head->peer, disconnected_peer)
4125 || (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_finger->finger_identity), disconnected_peer)))
4127 GNUNET_assert (GNUNET_YES ==
4128 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
4131 free_finger (remove_finger);
4139 * Method called whenever a peer disconnects.
4141 * @param cls closure
4142 * @param peer peer identity this notification is about
4145 handle_core_disconnect (void *cls,
4146 const struct GNUNET_PeerIdentity *peer)
4148 struct FriendInfo *remove_friend;
4150 /* Check for self message. */
4151 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
4154 /* Search for peer to remove in your friend_peermap. */
4156 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4158 if (NULL == remove_friend)
4164 /* Remove fingers for which this peer is the first element in the trail or if
4165 * the friend is a finger. */
4166 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap,
4167 &remove_matching_finger, (void *)peer);
4169 /* Remove routing trails of which this peer is a part.
4170 * FIXME: Here do we only remove the entry from our own routing table
4171 * or do we also inform other peers which are part of trail. It seems to be
4172 * too much of messages exchanged. */
4173 GDS_ROUTING_remove_entry (peer);
4175 /* Remove the peer from friend_peermap. */
4176 GNUNET_assert (GNUNET_YES ==
4177 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
4181 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
4184 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4186 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4187 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4195 * Method called whenever a peer connects.
4197 * @param cls closure
4198 * @param peer_identity peer identity this notification is about
4201 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
4203 struct FriendInfo *friend;
4205 /* Check for connect to self message */
4206 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
4209 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
4211 /* If peer already exists in our friend_peermap, then exit. */
4212 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
4218 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
4221 friend = GNUNET_new (struct FriendInfo);
4222 friend->id = *peer_identity;
4223 friend->trails_count = 0;
4225 GNUNET_assert (GNUNET_OK ==
4226 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
4227 peer_identity, friend,
4228 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
4230 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
4231 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
4232 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
4237 * To be called on core init/fail.
4239 * @param cls service closure
4240 * @param identity the public identity of this peer
4243 core_init (void *cls,
4244 const struct GNUNET_PeerIdentity *identity)
4246 my_identity = *identity;
4251 * Initialize neighbours subsystem.
4252 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4255 GDS_NEIGHBOURS_init (void)
4257 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
4258 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
4259 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
4260 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
4261 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
4262 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
4263 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
4264 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
4265 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
4266 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
4267 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
4272 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
4273 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
4274 GNUNET_NO, core_handlers);
4275 if (NULL == core_api)
4276 return GNUNET_SYSERR;
4278 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
4279 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS * 4/3, GNUNET_NO);
4280 all_friends_trail_threshold = GNUNET_NO;
4287 * Shutdown neighbours subsystem.
4290 GDS_NEIGHBOURS_done (void)
4292 if (NULL == core_api)
4295 GNUNET_CORE_disconnect (core_api);
4298 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
4299 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
4300 friend_peermap = NULL;
4302 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
4303 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
4304 finger_peermap = NULL;
4306 /* FIXME: Here I have added GNUNET_break(0) as ideally if friend_peermap
4307 is already zero, then we really don't need to cancel it again. If this
4308 condition happens it mean we might have missed some corner case. But we
4309 cancel the task only in handle_core_disconnect. it may happen that this
4310 function is called but not handle_core_disconnect, In that case GNUNET_break(0)
4312 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4315 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4316 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4324 * @return my identity
4326 struct GNUNET_PeerIdentity
4327 GDS_NEIGHBOURS_get_my_id (void)
4333 /* end of gnunet-service-xdht_neighbours.c */