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 which wants to notify its new successor.
483 struct GNUNET_PeerIdentity source_peer;
486 * New successor identity.
488 struct GNUNET_PeerIdentity destination_peer;
491 * Number of peers in trail from source_peer to new successor.
493 uint32_t trail_length;
495 /* Trail to from source_peer to destination_peer. */
498 GNUNET_NETWORK_STRUCT_END
502 * Linked list of messages to send to a particular other peer.
504 struct P2PPendingMessage
507 * Pointer to next item in the list
509 struct P2PPendingMessage *next;
512 * Pointer to previous item in the list
514 struct P2PPendingMessage *prev;
517 * Message importance level. FIXME: used? useful?
519 unsigned int importance;
522 * When does this message time out?
524 struct GNUNET_TIME_Absolute timeout;
527 * Actual message to be sent, allocated at the end of the struct:
528 * // msg = (cast) &pm[1];
529 * // memcpy (&pm[1], data, len);
531 const struct GNUNET_MessageHeader *msg;
537 * Linked List of peers which are part of trail to reach a particular Finger.
542 * Pointer to next item in the list
544 struct TrailPeerList *next;
547 * Pointer to previous item in the list
549 struct TrailPeerList *prev;
552 * An element in this trail list
554 struct GNUNET_PeerIdentity peer;
560 * Entry in friend_peermap.
567 struct GNUNET_PeerIdentity id;
570 * 1. used in select_random_friend(), in case the friend has trails_count > TRAILS_THROUGH_FRIEND,
571 * then choose another friend.
572 * 2. in case of find_successor(), if the number of trails going through the friend
573 * has already crossed, then choose another friend.
574 * 3. in case of find_successor(), if we choose a finger, and if friend through
575 * which we reach this finger has crossed the limit then choose another finger/friend.
576 * 4. One way to implement in case of find_successor, is 1) you can have a global
577 * array of the entries and only when an entry is added in finger table, friend table,
578 * then you re calculate the array. In array while adding the element you check
579 * the threshold of the friend in case its friend, and in case of finger check
580 * the threshold of the first friend in the trail. If crossed then don't add the
581 * entries in the array. When the count goes down, then again set a flag and
582 * recalculte the array. Store a field in Finger table also, which will be
583 * equal to number of trails going through the first friend.
584 * Number of trail of which this friend is the first hop.
585 * 5.FIXME: understand where you need to use memcpy or direct assignment.
587 unsigned int trails_count;
590 * Count of outstanding messages for this friend.
592 unsigned int pending_count;
595 * Head of pending messages to be sent to this friend.
597 struct P2PPendingMessage *head;
600 * Tail of pending messages to be sent to this friend.
602 struct P2PPendingMessage *tail;
605 * Core handle for sending messages to this friend.
607 struct GNUNET_CORE_TransmitHandle *th;
613 * Entry in finger_peermap.
620 struct GNUNET_PeerIdentity finger_identity;
623 * Index in finger peer map
625 unsigned int finger_map_index;
628 * Number of trails to reach to this finger.
630 unsigned int trail_count;
633 * Total number of entries in first trail from (me,finger)
635 unsigned int first_trail_length;
638 * Total number of entries in second trail from (me,finger)
640 unsigned int second_trail_length;
644 * Number of trail of which the first element to reach to this finger is
647 unsigned int first_friend_trails_count;
650 * Head of first trail to reach this finger.
652 struct TrailPeerList *first_trail_head;
655 * Tail of first trail to reach this finger.
657 struct TrailPeerList *first_trail_tail;
660 * Head of second trail to reach this finger.
662 struct TrailPeerList *second_trail_head;
665 * Tail of second trail to reach this finger.
667 struct TrailPeerList *second_trail_tail;
673 * FIXME: The name is not correct.
674 * Used to specify the kind of value stored in the array all_known_peers.
676 enum current_destination_type
686 * Data structure passed to sorting algorithm in find_successor().
691 * 64 bit value of peer identity
696 * FIXME: think of a better name for both the struct and destination_type
697 * Type : MY_ID, FINGER, FINGER, Value
699 enum current_destination_type type;
702 * Pointer to original data structure linked to peer id.
709 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
710 * get our first friend.
712 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
715 * Identity of this peer.
717 static struct GNUNET_PeerIdentity my_identity;
720 * Hash map of all the friends of a peer
722 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
725 * Hash map of all the fingers of a peer
727 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
732 static struct GNUNET_CORE_Handle *core_api;
735 * Finger map index for predecessor entry in finger peermap.
737 #define PREDECESSOR_FINGER_ID 64
740 * Maximum number of trails allowed to go through a friend.
741 * FIXME: Better name, Random value at the moment, need to be adjusted to maintain a balance
742 * between performance and Sybil tolerance.
744 #define TRAIL_THROUGH_FRIEND_THRESHOLD 64
747 * Possible number of different trails to reach to a finger. (Redundant routing)
749 #define TRAIL_COUNT 2
752 * FIXME: better name.
753 * Set to GNUNET_YES, when the number of trails going through all my friends
754 * have reached the TRAIL_THROUGH_FRIEND_THRESHOLD.
756 static unsigned int all_friends_trail_threshold;
759 * The current finger index that we have want to find trail to.
761 static unsigned int current_search_finger_index;
765 * Iterate over trail and search your index location in the array.
766 * @param trail Trail which contains list of peers.
767 * @param trail_length Number of peers in the trail.
768 * @return Index in the array.
769 * #GNUNET_SYSERR, in case there is no entry which should not be the case ideally.
772 search_my_index (const struct GNUNET_PeerIdentity *trail,
777 while (i < trail_length)
779 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
785 return GNUNET_SYSERR;
789 * Compare two peer identities.
790 * @param p1 Peer identity
791 * @param p2 Peer identity
792 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
795 compare_peer_id (const void *p1, const void *p2)
797 struct Sorting_List *p11;
798 struct Sorting_List *p22;
800 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
801 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
802 p11 = (struct Sorting_List *)p1;
803 p22 = (struct Sorting_List *)p2;
804 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
805 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
811 * Return the predecessor of value in all_known_peers.
812 * @param all_known_peers list of all the peers
813 * @param value value we have to search in the all_known_peers.
814 * @param size Total numbers of elements
815 * @return Predecessor
817 static struct Sorting_List *
818 find_closest_predecessor(struct Sorting_List *all_known_peers, uint64_t value,
827 middle = (first + last)/2;
831 if(all_known_peers[middle].peer_id < value)
835 else if(all_known_peers[middle].peer_id == value)
839 return &all_known_peers[size - 1];
843 return &all_known_peers[middle - 1];
851 middle = (first + last)/2;
858 * Return the successor of value in all_known_peers.
859 * @param all_known_peers list of all the peers
860 * @param value value we have to search in the all_known_peers.
861 * @param size Total numbers of elements
864 static struct Sorting_List *
865 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
874 middle = (first + last)/2;
878 if(all_known_peers[middle].peer_id < value)
882 else if(all_known_peers[middle].peer_id == value)
884 if(middle == (size -1))
886 return &all_known_peers[0];
890 return &all_known_peers[middle+1];
898 middle = (first + last)/2;
905 * Called when core is ready to send a message we asked for
906 * out to the destination.
908 * @param cls the 'struct FriendInfo' of the target friend
909 * @param size number of bytes available in buf
910 * @param buf where the callee should write the message
911 * @return number of bytes written to buf
914 core_transmit_notify (void *cls, size_t size, void *buf)
916 struct FriendInfo *peer = cls;
918 struct P2PPendingMessage *pending;
923 while ((NULL != (pending = peer->head)) &&
924 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
926 peer->pending_count--;
927 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
928 GNUNET_free (pending);
932 /* no messages pending */
938 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
939 GNUNET_CORE_PRIO_BEST_EFFORT,
940 GNUNET_TIME_absolute_get_remaining
941 (pending->timeout), &peer->id,
942 ntohs (pending->msg->size),
943 &core_transmit_notify, peer);
944 GNUNET_break (NULL != peer->th);
948 while ((NULL != (pending = peer->head)) &&
949 (size - off >= (msize = ntohs (pending->msg->size))))
951 GNUNET_STATISTICS_update (GDS_stats,
953 ("# Bytes transmitted to other peers"), msize,
955 memcpy (&cbuf[off], pending->msg, msize);
957 peer->pending_count--;
958 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
959 GNUNET_free (pending);
961 if (peer->head != NULL)
964 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
965 GNUNET_CORE_PRIO_BEST_EFFORT,
966 GNUNET_TIME_absolute_get_remaining
967 (pending->timeout), &peer->id, msize,
968 &core_transmit_notify, peer);
969 GNUNET_break (NULL != peer->th);
977 * Transmit all messages in the friend's message queue.
979 * @param peer message queue to process
982 process_friend_queue (struct FriendInfo *peer)
984 struct P2PPendingMessage *pending;
986 if (NULL == (pending = peer->head))
988 if (NULL != peer->th)
991 GNUNET_STATISTICS_update (GDS_stats,
993 ("# Bytes of bandwidth requested from core"),
994 ntohs (pending->msg->size), GNUNET_NO);
996 /* FIXME: Are we correctly initializing importance and pending. */
998 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1000 GNUNET_TIME_absolute_get_remaining
1001 (pending->timeout), &peer->id,
1002 ntohs (pending->msg->size),
1003 &core_transmit_notify, peer);
1004 GNUNET_break (NULL != peer->th);
1009 * Construct a trail message and forward it to a friend.
1010 * @param source_peer Peer which wants to set up the trail to one of its finger.
1011 * @param destination_finger Peer identity closest to this value will be
1012 * @a source_peer's finger.
1013 * @param current_destination Finger of the @a current_source, for which among
1014 * its friends, its own identity and all fingers, this
1015 * finger is the closest to the @a destination_finger
1016 * @param current_source Peer for which @a current_destination is its finger.
1017 * @param target_friend Friend to which this message should be forwarded.
1018 * @param trail_length Numbers of peers in the trail found so far.
1019 * @param trail_peer_list Peers this request has traversed so far
1020 * @param finger_map_index Index in finger peer map
1023 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
1024 uint64_t destination_finger,
1025 struct GNUNET_PeerIdentity *current_destination,
1026 struct GNUNET_PeerIdentity *current_source,
1027 struct FriendInfo *target_friend,
1028 unsigned int trail_length,
1029 const struct GNUNET_PeerIdentity *trail_peer_list,
1030 unsigned int finger_map_index)
1032 struct P2PPendingMessage *pending;
1033 struct PeerTrailSetupMessage *tsm;
1034 struct GNUNET_PeerIdentity *peer_list;
1037 msize = sizeof (struct PeerTrailSetupMessage) +
1038 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1040 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1046 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1048 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1052 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1053 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1054 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1055 pending->msg = &tsm->header;
1056 tsm->header.size = htons (msize);
1057 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
1058 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
1059 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1060 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
1061 memcpy (&(tsm->current_source), current_source, sizeof (struct GNUNET_PeerIdentity));
1062 tsm->trail_length = htonl (trail_length);
1063 tsm->finger_map_index = htonl (finger_map_index);
1065 if (trail_length > 0)
1067 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1068 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1071 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1072 target_friend->pending_count++;
1073 process_friend_queue (target_friend);
1079 * Construct a trail setup result message and forward it to a friend.
1080 * @param destination_peer Peer which will get the trail to one of its finger.
1081 * @param source_finger Peer to which the trail has been setup to.
1082 * @param target_friend Friend to which this message should be forwarded.
1083 * @param trail_length Numbers of peers in the trail.
1084 * @param trail_peer_list Peers which are part of the trail from source to destination.
1085 * @param finger_map_index Index in finger peer map
1088 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destination_peer,
1089 const struct GNUNET_PeerIdentity *source_finger,
1090 struct FriendInfo *target_friend,
1091 unsigned int trail_length,
1092 const struct GNUNET_PeerIdentity *trail_peer_list,
1093 unsigned int finger_map_index)
1095 struct P2PPendingMessage *pending;
1096 struct PeerTrailSetupResultMessage *tsrm;
1097 struct GNUNET_PeerIdentity *peer_list;
1100 msize = sizeof (struct PeerTrailSetupResultMessage) +
1101 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1103 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1109 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1111 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1115 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1116 pending->importance = 0;
1117 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1118 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1119 pending->msg = &tsrm->header;
1120 tsrm->header.size = htons (msize);
1121 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
1122 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1123 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
1124 tsrm->trail_length = htonl (trail_length);
1125 tsrm->finger_map_index = htonl (finger_map_index);
1127 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1128 if (trail_length > 0)
1130 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1132 /* Send the message to chosen friend. */
1133 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1134 target_friend->pending_count++;
1135 process_friend_queue (target_friend);
1140 * Construct a PeerVerifySuccessor message and send it to friend.
1141 * @param source_peer Peer which wants to verify its successor
1142 * @param successor Peer which is our current successor
1143 * @param target_friend Friend to which this message should be forwarded.
1144 * @param trail_peer_list Peer which are part of trail from source to destination
1145 * @param trail_length Number of peers in the trail list.
1147 void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *source_peer,
1148 const struct GNUNET_PeerIdentity *successor,
1149 struct FriendInfo *target_friend,
1150 const struct GNUNET_PeerIdentity *trail_peer_list,
1151 unsigned int trail_length)
1153 struct PeerVerifySuccessorMessage *vsm;
1154 struct P2PPendingMessage *pending;
1155 struct GNUNET_PeerIdentity *peer_list;
1158 msize = sizeof (struct PeerVerifySuccessorMessage) +
1159 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1161 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1167 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1169 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1173 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1174 pending->importance = 0; /* FIXME */
1175 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1176 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1177 pending->msg = &vsm->header;
1178 vsm->header.size = htons (msize);
1179 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1180 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
1181 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1182 vsm->trail_length = htonl (trail_length);
1184 if (trail_length > 0)
1186 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1187 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1190 /* Send the message to chosen friend. */
1191 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1192 target_friend->pending_count++;
1193 process_friend_queue (target_friend);
1199 * Construct a PeerVerifySuccessorResult message and send it to friend.
1200 * @param destination_peer Peer which sent verify successor message
1201 * @param source_successor Peer to which verify successor message was sent.
1202 * @param my_predecessor source_successor's predecessor.
1203 * @param target_friend Friend to which this message should be forwarded.
1204 * @param trail_peer_list Peers which are part of trail from source to destination
1205 * @param trail_length Number of peers in the trail list.
1207 void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *destination_peer,
1208 const struct GNUNET_PeerIdentity *source_successor,
1209 const struct GNUNET_PeerIdentity *my_predecessor,
1210 struct FriendInfo *target_friend,
1211 const struct GNUNET_PeerIdentity *trail_peer_list,
1212 unsigned int trail_length)
1214 struct PeerVerifySuccessorResultMessage *vsmr;
1215 struct P2PPendingMessage *pending;
1216 struct GNUNET_PeerIdentity *peer_list;
1219 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1220 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1222 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1229 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1231 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1235 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1236 pending->importance = 0; /* FIXME */
1237 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1238 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1239 pending->msg = &vsmr->header;
1240 vsmr->header.size = htons (msize);
1241 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1242 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1243 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1244 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1245 vsmr->trail_length = htonl (trail_length);
1246 if (trail_length > 0)
1248 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1249 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1252 /* Send the message to chosen friend. */
1253 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1254 target_friend->pending_count++;
1255 process_friend_queue (target_friend);
1260 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1261 * @param source_peer Peer which is sending notify message to its new successor.
1262 * @param destination_peer Peer which is the new destination.
1263 * @param target_friend Next friend to pass this message to.
1264 * @param peer_list List of peers in the trail to reach to destination_peer.
1265 * @param trail_length Total number of peers in peer list
1268 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1269 const struct GNUNET_PeerIdentity *destination_peer,
1270 struct FriendInfo *target_friend,
1271 const struct GNUNET_PeerIdentity *trail_peer_list,
1272 unsigned int trail_length)
1274 struct PeerNotifyNewSuccessorMessage *nsm;
1275 struct P2PPendingMessage *pending;
1276 struct GNUNET_PeerIdentity *peer_list;
1279 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1280 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1282 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1288 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1290 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1294 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1295 pending->importance = 0; /* FIXME */
1296 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1297 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1298 pending->msg = &nsm->header;
1299 nsm->header.size = htons (msize);
1300 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1301 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1302 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1303 nsm->trail_length = htonl (trail_length);
1304 /* FIXME: Here I am not checking the trail length, as I am assuming that for new
1305 successor our old successor is a part of trail, so trail length > 1. */
1306 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1307 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1309 /* Send the message to chosen friend. */
1310 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1311 target_friend->pending_count++;
1312 process_friend_queue (target_friend);
1316 * Send a trail tear down message
1317 * @param source_peer Source of the trail.
1318 * @param destination_peer Destination of the trail.
1319 * @param trail_list Peers in the trail from @a source_peer to @a destination_peer
1320 * @param trail_length Total number of peers in trail_list.
1321 * @pararm target_peer Next peer to forward this message to.
1324 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_PeerIdentity *source_peer,
1325 const struct GNUNET_PeerIdentity *destination_peer,
1326 struct GNUNET_PeerIdentity *trail_peer_list,
1327 unsigned int trail_length,
1328 struct FriendInfo *target_friend)
1330 struct P2PPendingMessage *pending;
1331 struct PeerTrailTearDownMessage *ttdm;
1332 struct GNUNET_PeerIdentity *peer_list;
1335 msize = sizeof (struct PeerTrailTearDownMessage) +
1336 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1338 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1344 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1346 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1350 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1351 pending->importance = 0; /* FIXME */
1352 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1353 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1354 pending->msg = &ttdm->header;
1355 ttdm->header.size = htons (msize);
1356 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1357 memcpy (&(ttdm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1358 memcpy (&(ttdm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1359 ttdm->trail_length = htonl (trail_length);
1361 peer_list = (struct GNUNET_PeerIdentity *) &ttdm[1];
1362 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1364 /* Send the message to chosen friend. */
1365 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1366 target_friend->pending_count++;
1367 process_friend_queue (target_friend);
1372 * FIMXE: Change the return value, to handle the case where all friends
1374 * FIXME: Handle congested peer - don't choose this friend, also don't choose
1375 * the friend if the link threshold has crossed. Not implemented yet.
1376 * Randomly choose one of your friends from the friends_peer map
1379 static struct FriendInfo *
1380 select_random_friend ()
1382 unsigned int current_size;
1383 unsigned int *index;
1385 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1386 struct GNUNET_PeerIdentity key_ret;
1387 struct FriendInfo *friend;
1389 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1390 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1391 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1395 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1403 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1405 /* Possible number of trails that can go through this friend has been reached. */
1406 if (friend->trails_count > TRAIL_THROUGH_FRIEND_THRESHOLD)
1408 /* FIXME: What should I do now, should I call this same function again and
1409 remember the index, j so that call random function without j and find
1410 a new friend. Also, I need some way to make sure that if number of times
1411 I have called the function is equal to number of entries in friend peermap.
1412 then I should return NULL. but its much better to have a function which
1413 just eliminates looking at the entries with threshold crossed. URGENT: Whats
1414 the best way to handle this case? */
1424 * Compute finger_identity to which we want to setup the trail
1425 * @return finger_identity
1428 compute_finger_identity()
1432 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1433 my_id64 = GNUNET_ntohll (my_id64);
1434 return (my_id64 + (unsigned long) pow (2, current_search_finger_index));
1439 * Compute immediate predecessor identity in the network.
1440 * @return peer identity of immediate predecessor.
1443 compute_predecessor_identity()
1447 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1448 my_id64 = GNUNET_ntohll (my_id64);
1449 return (my_id64 -1);
1454 * Ping your successor to verify if it is still your successor or not.
1457 send_verify_successor_message()
1459 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1460 struct GNUNET_PeerIdentity key_ret;
1461 struct FriendInfo *target_friend;
1462 struct GNUNET_PeerIdentity next_hop;
1463 struct GNUNET_PeerIdentity *peer_list;
1464 struct FingerInfo *finger;
1465 unsigned int finger_index;
1468 /* Find the successor from the finger peermap.*/
1469 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1470 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1472 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1473 (const void **)&finger))
1475 if (0 == finger->finger_map_index)
1482 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1484 /* Either you don't have a successor or you are your own successor, then don't
1485 send a successor message. */
1487 (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &(finger->finger_identity))))
1492 if (finger->first_trail_length > 0)
1494 struct TrailPeerList *iterate;
1496 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->first_trail_length);
1497 iterate = finger->first_trail_head;
1499 while ( i < (finger->first_trail_length))
1502 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1503 iterate = iterate->next;
1506 memcpy (&next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1507 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
1511 /* If trail length = 0, then our successor is our friend. */
1513 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1514 &(finger->finger_identity));
1517 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1518 &(finger->finger_identity),
1521 finger->first_trail_length);
1527 * 1. Need to handle the case where all friends are either congested or
1528 * have reached their threshold.
1529 * 2. If we need all_friends_trail_threshold
1530 * 3. do we need to check if friend peermap is empty or not.
1531 * Choose a random friend and start looking for the trail to reach to
1532 * finger identity through this random friend.
1534 * @param cls closure for this task
1535 * @param tc the context under which the task is running
1538 send_find_finger_trail_message (void *cls,
1539 const struct GNUNET_SCHEDULER_TaskContext *tc)
1541 struct FriendInfo *target_friend;
1542 struct GNUNET_TIME_Relative next_send_time;
1543 uint64_t finger_identity;
1544 unsigned int finger_map_index;
1546 next_send_time.rel_value_us =
1547 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1548 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1549 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1550 find_finger_trail_task =
1551 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1554 if (GNUNET_YES == all_friends_trail_threshold)
1556 /* All friends in friend peer map, have reached their trail threshold. No
1557 more new trail can be created. */
1561 target_friend = select_random_friend ();
1562 if (NULL == target_friend)
1564 all_friends_trail_threshold = GNUNET_YES;
1568 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
1570 finger_identity = compute_predecessor_identity();
1574 finger_identity = compute_finger_identity();
1577 finger_map_index = current_search_finger_index;
1578 GDS_NEIGHBOURS_send_trail_setup (&my_identity, finger_identity, &(target_friend->id),
1579 &my_identity, target_friend, 0, NULL, finger_map_index);
1585 /* In this function, we want to return the compressed trail and the trail length.
1586 We can send back a new trail and update the trail length value as we get as
1587 parameter to our function. There are many cases where we don't need to call
1588 this function. Move that logic to calling function. */
1590 * Scan the trail to check if any of my own friend is part of trail. If yes
1591 * then shortcut the trail, update trail length and send back the new trail.
1592 * @param trail[Out] Current trail to reach to @a finger, will be updated
1593 * in case we compress the trail.
1594 * @param trail_length[Out] Number of peers in @a finger_trail, will be updated
1595 * in case we compress the trail.
1596 * @param finger Finger identity
1599 scan_and_compress_trail (struct GNUNET_PeerIdentity *trail,
1600 unsigned int *trail_length,
1601 const struct GNUNET_PeerIdentity *finger)
1605 /* If finger is my friend, then set trail_length = 0;*/
1606 if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger))
1608 /* supu' delete entry from the thrail. */
1614 i = *trail_length - 1;
1617 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
1619 /* This element of trail is not my friend. */
1624 /* A --> B(friend 1) --> C(friend 2)--> D ---> E, then we can rewrite the trail as
1626 * Now, we should remove the entry from A's routing table, B's routing table
1627 * and update the entry in C's routing table. Rest everything will be same.
1628 * C's routing table should have source peer as the prev.hop.
1629 * In case we found a friend not at i = 0, then we can discard all the
1630 peers before it in the trail and short cut the path. We need to send
1631 trail teardown message also but not to all the peers in the trail. only
1632 the peer just behind me and also update the routing table of the friend,
1633 to prev hop as the source peer ie my_identity. */
1634 struct GNUNET_PeerIdentity *discarded_trail;
1635 struct FriendInfo *target_friend;
1636 int discarded_trail_length;
1638 /* Here I am adding the friend (C) found to the discarded trail also, as we
1639 need to update its routing table also. */
1640 discarded_trail_length = i;
1641 discarded_trail = GNUNET_malloc (discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1642 memcpy (discarded_trail, trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1643 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
1644 /* send_update_routing_table(friend). so that it removes prev hop
1645 and update it to source for given finger. */
1646 /* FIXME: Modify trail_teardown function to handle such cases. In case
1647 the last element of the trail update the routing table, in case it
1648 is trail compression. But teardown is called from various places so
1649 need to differentiate these two cases. URGENT*/
1650 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, discarded_trail,
1651 discarded_trail_length, target_friend);
1653 /* Copy the trail from index i to index trail_length -1 and change
1654 trail length and return */
1655 while (i < *trail_length)
1657 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
1661 *trail_length = j+1;
1670 * FIXME: Is this correct? Here I am using dll_remove and its documentation
1671 * reads something else. Verify. Urgent.
1672 * Free finger and its trail.
1673 * @param finger Finger to be freed.
1676 free_finger (struct FingerInfo *finger)
1678 struct TrailPeerList *peer;
1680 if(finger->first_trail_head != NULL)
1682 while (NULL != (peer = finger->first_trail_head))
1684 GNUNET_CONTAINER_DLL_remove (finger->first_trail_head, finger->first_trail_tail, peer);
1689 if (finger->second_trail_head != NULL)
1691 while (NULL != (peer = finger->second_trail_head))
1693 GNUNET_CONTAINER_DLL_remove (finger->second_trail_head, finger->second_trail_tail, peer);
1696 GNUNET_free (finger);
1702 * * 1.* If you remove an entry from finger table, and if the finger is not your friend
1703 * and the trail length > 1 for the finger that you removed, then you should send
1704 * a trail_teardown message along the trail. so that the peers which have an
1705 * entry in their routing table for this trail can remove it from their routing
1708 * TODO: First check if both the trails are present if yes then send it
1710 * @param existing_finger
1713 void send_trail_teardown (struct FingerInfo *existing_finger)
1715 struct GNUNET_PeerIdentity *peer_list;
1716 struct FriendInfo *friend;
1717 struct TrailPeerList *finger_trail;
1718 int existing_finger_trail_length = existing_finger->first_trail_length;
1722 if (existing_finger->first_trail_length == 0)
1724 finger_trail = existing_finger->first_trail_head;
1725 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(finger_trail->peer));
1726 peer_list = GNUNET_malloc ( existing_finger_trail_length * sizeof (struct GNUNET_PeerIdentity));
1727 while (i < existing_finger->first_trail_length)
1729 memcpy (&peer_list[i], &(finger_trail->peer), sizeof (struct GNUNET_PeerIdentity));
1730 finger_trail = finger_trail->next;
1734 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, &(existing_finger->finger_identity),
1735 peer_list, existing_finger_trail_length, friend);
1740 * Add a new trail to reach an existing finger in finger peermap.
1741 * @param existing_finger
1743 * @param trail_length
1746 void add_new_trail (struct FingerInfo *existing_finger,
1747 struct GNUNET_PeerIdentity *trail,
1748 unsigned int trail_length)
1753 if (existing_finger->second_trail_head != NULL)
1755 while (i < trail_length)
1757 struct TrailPeerList *element;
1758 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1759 element->next = NULL;
1760 element->prev = NULL;
1762 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1763 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1767 else if (existing_finger->second_trail_head != NULL)
1769 while (i < trail_length)
1771 struct TrailPeerList *element;
1772 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1773 element->next = NULL;
1774 element->prev = NULL;
1776 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1777 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1781 existing_finger->trail_count++;
1786 * FIXME: In this case first you should check which of the trail is longest and
1787 * the just discard it. Right now you are not checking it.
1788 * In case there are already maximum number of possible trail to reach to a finger,
1789 * then check if the new trail can replace an existing one. If yes then replace.
1790 * @param existing_finger
1792 * @param trail_length
1793 * @return #GNUNET_YES
1797 void select_and_replace_trail (struct FingerInfo *existing_finger,
1798 struct GNUNET_PeerIdentity *trail,
1799 unsigned int trail_length)
1801 if (trail_length < existing_finger->first_trail_length)
1803 struct TrailPeerList *peer;
1806 while (NULL != (peer = existing_finger->first_trail_head))
1808 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1812 while (i < trail_length)
1814 struct TrailPeerList *element;
1815 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1816 element->next = NULL;
1817 element->prev = NULL;
1819 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1820 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1824 else if (trail_length < existing_finger->second_trail_length)
1826 struct TrailPeerList *peer;
1829 while (NULL != (peer = existing_finger->second_trail_head))
1831 GNUNET_CONTAINER_DLL_remove (existing_finger->second_trail_head, existing_finger->second_trail_tail, peer);
1835 while (i < trail_length)
1837 struct TrailPeerList *element;
1838 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1839 element->next = NULL;
1840 element->prev = NULL;
1842 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1843 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1851 * FIXME: If we remove a finger which is our friend, then do we need to handle it
1852 * differentlty in regard to trail count.
1853 * Decrement the trail count for the first friend to reach to the finger.
1857 decrement_friend_trail_count (struct FingerInfo *finger)
1859 struct FriendInfo *first_trail_friend;
1860 struct FriendInfo *second_trail_friend;
1862 if(finger->first_trail_head != NULL)
1864 first_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1865 &(finger->first_trail_head->peer));
1866 first_trail_friend->trails_count--;
1869 if(finger->second_trail_head != NULL)
1871 second_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1872 &(finger->second_trail_head->peer));
1873 second_trail_friend->trails_count--;
1876 if (GNUNET_YES == all_friends_trail_threshold)
1878 all_friends_trail_threshold = GNUNET_NO;
1879 /* FIXME; Here you should reschedule the send_find_finger_task here. or
1886 * FIXME: consider the case where my_id = 2, and we are in circle from 0 to 7.
1887 * my current_predecessor is 6, and now the new finger 1. Here we are checking
1888 * if existing_finger < new_entry then new_entry is predecessor. This holds
1889 * true in case where lets say existing_finger = 5, new_entry= 6. But in the case
1890 * above, 6 > 1 but still 1 is correct predecessor. We have not handled it here.
1891 * We can put all the three values in an array and then the peer just before me
1892 * will be mine predecessor.
1893 * FIXME: Currently I am using struct Sorting_list to compare the values,
1894 * will create a new ds if needed.
1895 * @param existing_finger
1900 int select_finger (struct FingerInfo *existing_finger,
1901 const struct GNUNET_PeerIdentity *new_finger,
1902 unsigned int finger_map_index)
1904 struct Sorting_List peers[3]; /* 3 for existing_finger, new_finger, my_identity */
1905 struct Sorting_List *closest_finger;
1909 for (k = 0; k < 3; k++)
1912 memcpy (&peers[0], &my_identity, sizeof (uint64_t));
1913 peers[0].type = MY_ID;
1914 peers[0].data = NULL;
1916 memcpy (&peers[1], &(existing_finger->finger_identity), sizeof (uint64_t));
1917 peers[1].type = FINGER;
1918 peers[1].data = existing_finger;
1920 memcpy (&peers[2], &new_finger, sizeof (uint64_t));
1921 peers[2].type = VALUE;
1922 peers[2].data = NULL;
1924 memcpy (&value, &my_identity, sizeof (uint64_t));
1927 qsort (&peers, 3, sizeof (struct Sorting_List), &compare_peer_id);
1929 if (PREDECESSOR_FINGER_ID == finger_map_index)
1930 closest_finger = find_closest_predecessor (peers, value, 3);
1932 closest_finger = find_closest_successor (peers, value, 3);
1934 if (closest_finger->type == FINGER)
1938 else if (closest_finger->type == VALUE)
1942 else if (closest_finger->type == MY_ID);
1944 return GNUNET_SYSERR;
1950 * Choose the closest finger between existing_finger and new_finger. In case new_finger
1951 * is closest and finger_map_index != PREDCESSOR_FINGER_ID,
1952 * then send a tear down message along the trail to reach existing_finger.
1953 * @param existing_finger Existing entry in finger peer map
1954 * @param new_finger New finger
1955 * @param trail Trail to reach to the new finger from me.
1956 * @param trail_length Number of peers in the @a trail
1957 * @param finger_map_index If finger_map_index == PREDECESSOR_FINGER_INDEX,
1958 * then we use a different logic to find the closest
1960 * @return #GNUNET_YES In case we want to store the new entry.
1961 * #GNUNET_NO In case we want the existing entry.
1962 * #GNUNET_SYSERR Error.
1965 int select_closest_finger (struct FingerInfo *existing_finger,
1966 const struct GNUNET_PeerIdentity *new_finger,
1967 struct GNUNET_PeerIdentity *trail,
1968 unsigned int trail_length,
1969 unsigned int finger_map_index)
1971 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), new_finger))
1973 /* Both the new entry and existing entry are same. */
1974 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), &my_identity))
1976 /* If both are same then exit. You already have that entry in your finger table,
1977 then you don't need to add it again. */
1980 if (trail_length > 1)
1982 scan_and_compress_trail (trail, &trail_length, new_finger);
1984 if (existing_finger->trail_count < TRAIL_COUNT)
1986 add_new_trail (existing_finger, trail, trail_length);
1991 select_and_replace_trail (existing_finger, trail, trail_length);
1995 else if (GNUNET_YES == select_finger (existing_finger, new_finger, finger_map_index))
1997 /* Here in case finger_map_index was Predecessor_finger then also you don't
1998 need to send trail teardown and in case its successor then you found it in
1999 trail_setup and then you don't need to send trail teardown. FIXME: check if
2000 its true for every call made to finger_table_add. Also, if we have an entry
2001 which is not my identity should I replace it with my identity or not? */
2002 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, new_finger))
2004 return GNUNET_NO; /* FIXME: In case I have a peer id which is not my id then
2005 * should I keep it as finger */
2008 /* new_finger is the correct finger. */
2009 if (PREDECESSOR_FINGER_ID != finger_map_index)
2010 send_trail_teardown (existing_finger);
2012 decrement_friend_trail_count (existing_finger);
2013 free_finger (existing_finger);
2014 if (trail_length > 1)
2015 scan_and_compress_trail (trail, &trail_length, new_finger);
2018 else if (GNUNET_NO == select_finger (existing_finger, new_finger,finger_map_index))
2020 /* existing_finger is the correct finger. */
2023 return GNUNET_SYSERR;
2028 * Check if there is a predecessor in our finger peer map or not.
2029 * If no, then return GNUNET_YES
2030 * else compare existing predecessor and peer, and find the correct
2032 * @param existing_predecessor
2033 * @param new_predecessor
2034 * @return #GNUNET_YES if new peer is predecessor
2035 * #GNUNET_NO if new peer is not the predecessor.
2038 compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer,
2039 struct GNUNET_PeerIdentity *trail,
2040 unsigned int trail_length)
2042 /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
2043 struct FingerInfo *existing_finger;
2044 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2045 struct FingerInfo *new_finger_entry;
2046 struct FriendInfo *first_friend_trail;
2049 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2050 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2052 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2053 (const void **)&existing_finger))
2055 if (PREDECESSOR_FINGER_ID == existing_finger->finger_map_index)
2057 if( GNUNET_NO == select_closest_finger (existing_finger, peer, trail,
2058 trail_length,PREDECESSOR_FINGER_ID))
2065 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2067 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2068 memcpy (&(new_finger_entry->finger_identity), peer, sizeof (struct GNUNET_PeerIdentity));
2069 new_finger_entry->finger_map_index = PREDECESSOR_FINGER_ID;
2070 new_finger_entry->first_trail_length = trail_length;
2072 if (trail != NULL) /* finger_trail is NULL in case I am my own finger identity. */
2074 /* FIXME: Currently we are not handling the second trail. In that case, finger
2075 trail count = min (first_friend, second_friend) trail count. */
2076 /* Incrementing the friend trails count. */
2077 if (trail_length > 0)
2079 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
2080 first_friend_trail->trails_count++;
2084 /* It means the finger is my friend. */
2085 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2086 first_friend_trail->trails_count++;
2088 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2090 if (trail_length != 0)
2092 i = trail_length - 1;
2095 struct TrailPeerList *element;
2096 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2097 element->next = NULL;
2098 element->prev = NULL;
2100 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
2101 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2104 struct TrailPeerList *element;
2105 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2106 element->next = NULL;
2107 element->prev = NULL;
2108 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
2109 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2112 GNUNET_assert (GNUNET_OK ==
2113 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2114 &(new_finger_entry->finger_identity),
2116 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
2123 * FIXME: Better name, and make the code more cleaner.
2124 * Compare the new finger entry added and our successor.
2125 * @return #GNUNET_YES if same.
2126 * #GNUNET_NO if not.
2129 compare_new_entry_and_successor (const struct GNUNET_PeerIdentity *new_finger,
2130 int finger_map_index)
2132 int successor_flag = 0;
2133 struct FingerInfo *successor_finger;
2134 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2137 if (PREDECESSOR_FINGER_ID == finger_map_index)
2140 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2141 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2143 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2144 (const void **)&successor_finger))
2146 if (successor_finger->finger_map_index == 0)
2153 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2155 /* Ideally we should never reach here. */
2156 if (successor_flag == 0)
2162 if (0 == GNUNET_CRYPTO_cmp_peer_identity (new_finger, &(successor_finger->finger_identity)))
2170 * Add a new entry in finger table.
2171 * @param finger_identity PeerIdentity of the new finger
2172 * @param finger_trail Trail to reach to the finger, can be NULL in case I am my own
2174 * @param finger_trail_length Number of peers in the trail, can be 0 in case finger
2175 * is a friend or I am my own finger.
2176 * @param finger_map_index Index in finger map.
2179 add_new_entry (const struct GNUNET_PeerIdentity *finger_identity,
2180 struct GNUNET_PeerIdentity *finger_trail,
2181 uint32_t finger_trail_length,
2182 uint32_t finger_map_index)
2184 struct FriendInfo *first_friend_trail;
2185 struct FingerInfo *new_finger_entry;
2188 /* Add a new entry. */
2189 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2190 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
2191 new_finger_entry->finger_map_index = finger_map_index;
2192 new_finger_entry->first_trail_length = finger_trail_length;
2193 new_finger_entry->trail_count = 1;
2195 if (finger_trail != NULL) /* finger_trail is NULL in case I am my own finger identity. */
2197 /* Incrementing the friend trails count. */
2198 if (finger_trail_length > 0)
2200 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_trail[0]);
2201 first_friend_trail->trails_count++;
2205 /* It means the finger is my friend. */
2206 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger_identity);
2207 first_friend_trail->trails_count++;
2209 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2211 /* Copy the trail. */
2213 while (i < finger_trail_length)
2215 struct TrailPeerList *element;
2216 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2217 element->next = NULL;
2218 element->prev = NULL;
2220 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
2221 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2226 return GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2227 &(new_finger_entry->finger_identity),
2229 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
2234 * 1. removed predecessor_finger_id check as in select_closest_finger we check it
2235 * and handle it accordingly.
2236 * 2. you don't handle the second trail here as in new entry you will have only
2237 * one trail to reach to the finger.
2238 * 3. check how do you handle the return value of this function.
2239 * FIXME: Functions calling finger_table_add will not check if finger identity
2240 * and my identity are same, it should be done in this function.
2241 * Add an entry in the finger table. If there is already an existing entry in
2242 * the finger peermap for given finger map index, then choose the closest one.
2243 * In case both the new entry and old entry are same, store both of them. (Redundant
2245 * @param finger_identity
2246 * @param finger_trail
2247 * @param finger_trail_length
2248 * @param finger_map_index
2249 * @return #GNUNET_YES if the new entry is added.
2250 * #GNUNET_NO if the new entry is discarded.
2253 int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
2254 struct GNUNET_PeerIdentity *finger_trail,
2255 uint32_t finger_trail_length,
2256 uint32_t finger_map_index)
2258 struct FingerInfo *existing_finger;
2259 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2261 int new_entry_added = GNUNET_NO;
2263 /* Check if there is already an entry for the finger map index in the finger peer map. */
2264 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2265 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2267 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2268 (const void **)&existing_finger))
2270 if (existing_finger->finger_map_index == finger_map_index)
2272 if ( GNUNET_NO == select_closest_finger (existing_finger, finger_identity,
2273 finger_trail, finger_trail_length,finger_map_index))
2274 goto update_current_search_finger_index;
2280 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2282 if(GNUNET_OK == add_new_entry (finger_identity,finger_trail,finger_trail_length, finger_map_index))
2283 new_entry_added = GNUNET_YES;
2287 update_current_search_finger_index:
2288 if (0 == finger_map_index)
2290 current_search_finger_index = PREDECESSOR_FINGER_ID;
2291 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity))
2292 send_verify_successor_message();
2294 else if (GNUNET_YES == compare_new_entry_and_successor (finger_identity,finger_map_index))
2296 /* If the new entry is same as our successor, then reset the current_search_finger_index to 0*/
2297 current_search_finger_index = 0;
2301 current_search_finger_index = current_search_finger_index - 1;
2304 return new_entry_added;
2309 * FIXME: In case a friend is either congested or has crossed its trail threshold,
2310 * then don't consider it as next successor, In case of finger if its first
2311 * friend has crossed the threshold then don't consider it. In case no finger
2312 * or friend is found, then return NULL.
2313 * Find closest successor for the value.
2314 * @param value Value for which we are looking for successor
2315 * @param[out] current_destination set to my_identity in case I am the final destination,
2316 * set to friend identity in case friend is final destination,
2317 * set to first friend to reach to finger, in case finger
2318 * is final destination.
2319 * @param[out] current_source set to my_identity.
2320 * @return Peer identity of next hop to send trail setup message to,
2321 * NULL in case all the friends are either congested or have crossed
2322 * their trail threshold.
2324 static struct GNUNET_PeerIdentity *
2325 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
2326 struct GNUNET_PeerIdentity *current_source)
2328 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
2329 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2330 struct GNUNET_PeerIdentity key_ret;
2331 struct FriendInfo *friend;
2332 struct FingerInfo *finger;
2333 unsigned int finger_index;
2334 unsigned int friend_index;
2335 struct Sorting_List *successor;
2339 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
2340 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
2341 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
2344 struct Sorting_List all_known_peers[size];
2347 for (k = 0; k < size; k++)
2348 all_known_peers[k].peer_id = 0;
2350 /* Copy your identity at 0th index in all_known_peers. */
2352 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
2353 all_known_peers[j].type = MY_ID;
2354 all_known_peers[j].data = 0;
2358 all_known_peers[j].peer_id = value;
2359 all_known_peers[j].type = VALUE;
2360 all_known_peers[j].data = 0;
2363 /* Iterate over friend peer map and copy all the elements into array. */
2364 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2365 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
2367 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
2369 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
2370 all_known_peers[j].type = FRIEND;
2371 all_known_peers[j].data = friend;
2377 /* Iterate over finger map and copy all the entries into all_known_peers array. */
2378 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2379 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2381 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
2383 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
2384 all_known_peers[j].type = FINGER;
2385 all_known_peers[j].data = finger;
2390 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2391 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
2394 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
2396 /* search value in all_known_peers array. */
2397 successor = find_closest_successor (all_known_peers, value, size);
2399 if (successor->type == MY_ID)
2401 memcpy (current_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2402 return &my_identity;
2404 else if (successor->type == FRIEND)
2406 struct FriendInfo *target_friend;
2407 target_friend = (struct FriendInfo *)successor->data;
2408 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
2409 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2410 return current_destination;
2412 else if (successor->type == FINGER)
2414 struct GNUNET_PeerIdentity *next_hop;
2415 struct FingerInfo *finger;
2416 finger = successor->data;
2417 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2419 if (finger->first_trail_length > 0)
2421 struct TrailPeerList *iterator;
2422 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2423 iterator = finger->first_trail_head;
2424 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2426 else /* This means finger is our friend. */
2427 memcpy (next_hop, &(finger->finger_identity), sizeof(struct GNUNET_PeerIdentity));
2429 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
2430 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2441 /** FIXME: by default I keep current_source, and destination as my own id.
2442 * in case we find a finger then we update current_source in the
2443 * find_successor message.
2444 * Construct a Put message and send it to target_peer.
2445 * @param key Key for the content
2446 * @param data Content to store
2447 * @param data_size Size of content @a data in bytes
2448 * @param block_type Type of the block
2449 * @param options Routing options
2450 * @param desired_replication_level Desired replication count
2451 * @param expiration_time When does the content expire
2452 * @param current_destination
2453 * @param current_source
2454 * @param target_peer Peer to which this message will be forwarded.
2455 * @param hop_count Number of hops traversed so far.
2456 * @param put_path_length Total number of peers in @a put_path
2457 * @param put_path Number of peers traversed so far
2460 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2461 const void *data, size_t data_size,
2462 enum GNUNET_BLOCK_Type block_type,
2463 enum GNUNET_DHT_RouteOption options,
2464 uint32_t desired_replication_level,
2465 struct GNUNET_TIME_Absolute expiration_time,
2466 struct GNUNET_PeerIdentity current_destination,
2467 struct GNUNET_PeerIdentity current_source,
2468 struct GNUNET_PeerIdentity *target_peer,
2470 uint32_t put_path_length,
2471 struct GNUNET_PeerIdentity *put_path)
2473 struct PeerPutMessage *ppm;
2474 struct P2PPendingMessage *pending;
2475 struct FriendInfo *target_friend;
2476 struct GNUNET_PeerIdentity *pp;
2479 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2480 sizeof (struct PeerPutMessage);
2482 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2484 put_path_length = 0;
2485 msize = data_size + sizeof (struct PeerPutMessage);
2488 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2494 /* This is the first call made from clients file. So, we should search for the
2496 if (NULL == target_peer)
2499 struct GNUNET_PeerIdentity *next_hop;
2500 memcpy (&key_value, key, sizeof (uint64_t));
2501 struct GNUNET_PeerIdentity curr_dest;
2502 struct GNUNET_PeerIdentity curr_src;
2503 memcpy (&curr_dest, ¤t_destination, sizeof (struct GNUNET_PeerIdentity));
2504 memcpy (&curr_src, ¤t_source, sizeof (struct GNUNET_PeerIdentity));
2505 next_hop = find_successor (key_value, &curr_dest, &curr_src);
2506 /* FIXME: I am copying back current_destination and current_source. but I am not
2507 sure, if its correct. I am doing so just to remove the code from client file.*/
2508 memcpy (¤t_destination, &curr_dest, sizeof (struct GNUNET_PeerIdentity));
2509 memcpy (¤t_source, &curr_src, sizeof (struct GNUNET_PeerIdentity));
2511 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity,¤t_destination)) /* I am the destination do datacache_put */
2513 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
2514 block_type, data_size, data);
2518 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2521 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2522 pending->timeout = expiration_time;
2523 ppm = (struct PeerPutMessage *) &pending[1];
2524 pending->msg = &ppm->header;
2525 ppm->header.size = htons (msize);
2526 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
2527 ppm->options = htonl (options);
2528 ppm->block_type = htonl (block_type);
2529 ppm->hop_count = htonl (hop_count + 1);
2530 ppm->desired_replication_level = htonl (desired_replication_level);
2531 ppm->put_path_length = htonl (put_path_length);
2532 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2534 ppm->current_destination = current_destination;
2535 ppm->current_source = current_source;
2537 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2538 if (put_path_length != 0)
2540 memcpy (pp, put_path,
2541 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2543 memcpy (&pp[put_path_length], data, data_size);
2544 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2545 target_friend->pending_count++;
2546 process_friend_queue (target_friend);
2551 /** FIXME: by default I keep current_source, and destination as my own id.
2552 * in case we find a finger then we update current_source in the
2553 * find_successor message.
2554 * Construct a Get message and send it to target_peer.
2555 * @param key Key for the content
2556 * @param block_type Type of the block
2557 * @param options Routing options
2558 * @param desired_replication_level Desired replication count
2559 * @param expiration_time When does the content expire
2560 * @param current_destination
2561 * @param current_source
2562 * @param target_peer Peer to which this message will be forwarded.
2563 * @param hop_count Number of hops traversed so far.
2564 * @param put_path_length Total number of peers in @a put_path
2565 * @param put_path Number of peers traversed so far
2568 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2569 enum GNUNET_BLOCK_Type block_type,
2570 enum GNUNET_DHT_RouteOption options,
2571 uint32_t desired_replication_level,
2572 struct GNUNET_PeerIdentity current_destination,
2573 struct GNUNET_PeerIdentity current_source,
2574 struct GNUNET_PeerIdentity *target_peer,
2576 uint32_t get_path_length,
2577 struct GNUNET_PeerIdentity *get_path)
2579 struct PeerGetMessage *pgm;
2580 struct P2PPendingMessage *pending;
2581 struct FriendInfo *target_friend;
2582 struct GNUNET_PeerIdentity *gp;
2585 msize = sizeof (struct PeerGetMessage) +
2586 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2588 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2594 if (NULL == target_peer)
2596 /* This is the first call from client file, we need to search for next_hop*/
2597 struct GNUNET_PeerIdentity *next_hop;
2599 struct GNUNET_PeerIdentity curr_dest;
2600 struct GNUNET_PeerIdentity curr_src;
2601 memcpy (&curr_dest, ¤t_destination, sizeof (struct GNUNET_PeerIdentity));
2602 memcpy (&curr_src, ¤t_source, sizeof (struct GNUNET_PeerIdentity));
2603 memcpy (&key_value, key, sizeof (uint64_t));
2604 // FIXME: endianess of key_value!?
2605 next_hop = find_successor (key_value, &curr_dest, &curr_src);
2606 /* FIXME: Again I am copying back value of current_destination, current_source,
2607 Think of a better solution. */
2608 memcpy (¤t_destination, &curr_dest, sizeof (struct GNUNET_PeerIdentity));
2609 memcpy (¤t_source, &curr_src, sizeof (struct GNUNET_PeerIdentity));
2610 if (NULL == next_hop) /* I am the destination do datacache_put */
2612 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2613 NULL, 0, 1, &my_identity, NULL,&my_identity);
2618 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2622 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2623 pending->importance = 0; /* FIXME */
2624 pgm = (struct PeerGetMessage *) &pending[1];
2625 pending->msg = &pgm->header;
2626 pgm->header.size = htons (msize);
2627 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2628 pgm->get_path_length = htonl (get_path_length);
2630 pgm->current_destination = current_destination;
2631 pgm->current_source = current_source;
2632 pgm->hop_count = htonl (hop_count + 1);
2634 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2635 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2636 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2637 target_friend->pending_count++;
2638 process_friend_queue (target_friend);
2643 * Send the get result to requesting client.
2644 * @param expiration When will this result expire?
2645 * @param key Key of the requested data.
2646 * @param put_path_length Number of peers in @a put_path
2647 * @param put_path Path taken to put the data at its stored location.
2648 * @param type Block type
2649 * @param data_size Size of the @a data
2650 * @param data Payload to store
2651 * @param get_path Path taken to reach to the location of the key.
2652 * @param get_path_length Number of peers in @a get_path
2653 * @param next_hop Next peer to forward the message to.
2654 * @param source_peer Peer which has the data for the key.
2657 GDS_NEIGHBOURS_send_get_result (struct GNUNET_TIME_Absolute expiration,
2658 const struct GNUNET_HashCode *key,
2659 unsigned int put_path_length,
2660 const struct GNUNET_PeerIdentity *put_path,
2661 enum GNUNET_BLOCK_Type type, size_t data_size,
2663 struct GNUNET_PeerIdentity *get_path,
2664 unsigned int get_path_length,
2665 struct GNUNET_PeerIdentity *next_hop,
2666 struct GNUNET_PeerIdentity *source_peer)
2668 struct PeerGetResultMessage *get_result;
2669 struct GNUNET_PeerIdentity *get_result_path;
2670 struct GNUNET_PeerIdentity *pp;
2671 struct P2PPendingMessage *pending;
2672 struct FriendInfo *target_friend;
2673 int current_path_index;
2676 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2677 sizeof (struct PeerPutMessage);
2679 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2685 current_path_index = search_my_index(get_path, get_path_length);
2686 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
2687 if (0 == current_path_index)
2689 GDS_CLIENTS_handle_reply (expiration, key, get_path_length, get_path, put_path_length,
2690 put_path, type, data_size, data);
2693 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2694 pending->importance = 0;
2695 get_result = (struct PeerGetResultMessage *)&pending[1];
2696 pending->msg = &get_result->header;
2697 get_result->header.size = htons (msize);
2698 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2699 get_result->key = *key;
2700 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2701 get_result->expiration_time = expiration;
2703 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2704 memcpy (get_result_path, get_path,
2705 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2706 memcpy (&get_result_path[get_path_length], data, data_size);
2707 /* FIXME: Is this correct? */
2708 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2709 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2711 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2712 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2713 target_friend->pending_count++;
2714 process_friend_queue (target_friend);
2719 * Send trail rejection message to the peer which sent me a trail setup message.
2720 * @param source_peer Source peer which wants to set up the trail.
2721 * @param finger_identity Value whose successor will be the finger of @a source_peer.
2722 * @param congested_peer Peer which has send trail rejection message.
2723 * @param next_hop Peer to which this message should be forwarded.
2724 * @param finger_map_index Index in @a source_peer finger peermap.
2725 * @param trail_peer_list Trail followed to reach from @a source_peer to next_hop,
2726 * NULL, in case the @a congested_peer was the first peer
2727 * to which trail setup message was forwarded.
2728 * @param trail_length Number of peers in trail_peer_list.
2731 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity *source_peer,
2732 uint64_t finger_identity,
2733 struct GNUNET_PeerIdentity *congested_peer,
2734 const struct GNUNET_PeerIdentity *next_hop,
2735 unsigned int finger_map_index,
2736 struct GNUNET_PeerIdentity *trail_peer_list,
2737 unsigned int trail_length)
2739 struct PeerTrailRejectionMessage *trail_rejection;
2740 struct GNUNET_PeerIdentity *trail_list;
2741 struct P2PPendingMessage *pending;
2742 struct FriendInfo *target_friend;
2745 msize = trail_length * sizeof(struct GNUNET_PeerIdentity) +
2746 sizeof (struct PeerTrailRejectionMessage);
2748 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2754 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2755 pending->importance = 0;
2756 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2757 trail_rejection = (struct PeerTrailRejectionMessage *) &pending[1];
2758 pending->msg = &trail_rejection->header;
2759 trail_rejection->header.size = htons (msize);
2760 trail_rejection->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
2761 memcpy (&(trail_rejection->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2762 memcpy (&(trail_rejection->congested_peer), congested_peer, sizeof (struct GNUNET_PeerIdentity));
2763 memcpy (&(trail_rejection->finger_identity_value), &finger_identity, sizeof (uint64_t));
2764 trail_rejection->finger_map_index = htonl(finger_map_index);
2765 trail_rejection->trail_length = htonl (trail_length);
2767 if (trail_length != 0)
2769 trail_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2770 memcpy (trail_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2773 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2774 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2775 target_friend->pending_count++;
2776 process_friend_queue (target_friend);
2781 * Core handler for P2P put messages.
2782 * @param cls closure
2783 * @param peer sender of the request
2784 * @param message message
2785 * @return #GNUNET_OK to keep the connection open,
2786 * #GNUNET_SYSERR to close it (signal serious error)
2789 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2790 const struct GNUNET_MessageHeader *message)
2792 struct PeerPutMessage *put;
2793 struct GNUNET_PeerIdentity *put_path;
2794 struct GNUNET_HashCode test_key;
2795 enum GNUNET_DHT_RouteOption options;
2796 struct GNUNET_PeerIdentity current_destination;
2797 struct GNUNET_PeerIdentity current_source;
2798 struct GNUNET_PeerIdentity *next_hop;
2802 size_t payload_size;
2805 msize = ntohs (message->size);
2806 if (msize < sizeof (struct PeerPutMessage))
2808 GNUNET_break_op (0);
2812 put = (struct PeerPutMessage *) message;
2813 putlen = ntohl (put->put_path_length);
2816 sizeof (struct PeerPutMessage) +
2817 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2819 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2821 GNUNET_break_op (0);
2825 current_destination = put->current_destination;
2826 current_source = put->current_source;
2827 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2828 payload = &put_path[putlen];
2829 options = ntohl (put->options);
2830 payload_size = msize - (sizeof (struct PeerPutMessage) +
2831 putlen * sizeof (struct GNUNET_PeerIdentity));
2833 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
2834 payload, payload_size, &test_key))
2837 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
2839 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
2840 GNUNET_break_op (0);
2841 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2842 "PUT with key `%s' for block with key %s\n",
2843 put_s, GNUNET_h2s_full (&test_key));
2844 GNUNET_free (put_s);
2849 GNUNET_break_op (0);
2852 /* cannot verify, good luck */
2856 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
2858 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
2859 ntohl (put->block_type),
2861 NULL, 0, /* bloom filer */
2862 NULL, 0, /* xquery */
2863 payload, payload_size))
2865 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2866 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2869 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2870 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2871 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
2872 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2873 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2874 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2876 GNUNET_break_op (0);
2881 struct GNUNET_PeerIdentity pp[putlen + 1];
2882 /* extend 'put path' by sender */
2883 /* FIXME: Check what are we doing here? */
2884 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
2886 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
2893 memcpy (&key_value, &(put->key), sizeof (uint64_t));
2894 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2896 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2897 if (next_hop == NULL)
2899 /* refer to handle_dht_p2p_trail_setup. */
2904 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2907 if (NULL == next_hop) /* I am the final destination */
2909 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
2910 &(put->key),putlen, pp, ntohl (put->block_type),
2911 payload_size, payload);
2916 GDS_CLIENTS_process_put (options,
2917 ntohl (put->block_type),
2918 ntohl (put->hop_count),
2919 ntohl (put->desired_replication_level),
2921 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2926 GDS_NEIGHBOURS_send_put (&put->key, payload, payload_size,
2927 ntohl (put->block_type),ntohl (put->options),
2928 ntohl (put->desired_replication_level),
2929 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2930 current_destination, current_source, next_hop,
2931 ntohl (put->hop_count), putlen, pp);
2935 return GNUNET_SYSERR;
2940 * Core handler for p2p get requests.
2942 * @param cls closure
2943 * @param peer sender of the request
2944 * @param message message
2945 * @return #GNUNET_OK to keep the connection open,
2946 * #GNUNET_SYSERR to close it (signal serious error)
2949 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2950 const struct GNUNET_MessageHeader *message)
2952 struct PeerGetMessage *get;
2953 struct GNUNET_PeerIdentity *get_path;
2954 struct GNUNET_PeerIdentity current_destination;
2955 struct GNUNET_PeerIdentity current_source;
2956 struct GNUNET_PeerIdentity *next_hop;
2957 uint32_t get_length;
2961 msize = ntohs (message->size);
2962 if (msize < sizeof (struct PeerGetMessage))
2964 GNUNET_break_op (0);
2968 get = (struct PeerGetMessage *)message;
2969 get_length = ntohl (get->get_path_length);
2970 get_path = (struct GNUNET_PeerIdentity *)&get[1];
2971 current_destination = get->current_destination;
2972 current_source = get->current_source;
2975 sizeof (struct PeerGetMessage) +
2976 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
2978 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2980 GNUNET_break_op (0);
2983 /* Add sender to get path */
2984 struct GNUNET_PeerIdentity gp[get_length + 1];
2985 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
2986 gp[get_length + 1] = *peer;
2987 get_length = get_length + 1;
2989 memcpy (&key_value, &(get->key), sizeof (uint64_t));
2990 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2992 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2993 if (next_hop == NULL)
2995 /* refer to handle_dht_p2p_trail_setup. */
3000 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
3003 if (NULL == next_hop)
3005 /* FIXME: Try to make this code also short and remove useless variables. */
3006 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3007 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3008 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3009 get_length = get_length + 1;
3010 struct GNUNET_PeerIdentity *next_hop;
3011 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3012 memcpy (next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
3013 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3014 get_length, final_get_path,next_hop, &my_identity);
3020 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3021 get->desired_replication_level,current_destination,
3022 current_source, next_hop, 0,
3025 return GNUNET_SYSERR;
3031 * FIXME: In case of trail, we don't have source and destination part of the trail,
3032 * Check if we follow the same in case of get/put/get_result. Also, in case of
3033 * put should we do a routing table add.
3034 * Core handler for get result
3035 * @param cls closure
3036 * @param peer sender of the request
3037 * @param message message
3038 * @return #GNUNET_OK to keep the connection open,
3039 * #GNUNET_SYSERR to close it (signal serious error)
3042 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3043 const struct GNUNET_MessageHeader *message)
3045 struct PeerGetResultMessage *get_result;
3046 struct GNUNET_PeerIdentity *get_path;
3047 struct GNUNET_PeerIdentity *put_path;
3049 size_t payload_size;
3051 unsigned int getlen;
3052 unsigned int putlen;
3053 int current_path_index;
3055 msize = ntohs (message->size);
3056 if (msize < sizeof (struct PeerGetResultMessage))
3058 GNUNET_break_op (0);
3062 get_result = (struct PeerGetResultMessage *)message;
3063 getlen = ntohl (get_result->get_path_length);
3064 putlen = ntohl (get_result->put_path_length);
3067 sizeof (struct PeerGetResultMessage) +
3068 getlen * sizeof (struct GNUNET_PeerIdentity) +
3069 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3071 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3073 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3075 GNUNET_break_op (0);
3079 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
3080 payload = &get_path[getlen];
3081 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3082 getlen * sizeof (struct GNUNET_PeerIdentity));
3083 /* FIXME: Check if its correct or not. */
3086 put_path = &get_path[1];
3090 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3092 //GDS_CLIENTS_process_get_result();
3093 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3094 getlen, get_path, putlen,
3095 put_path, get_result->type, payload_size, payload);
3100 struct GNUNET_PeerIdentity *next_hop;
3101 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3102 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3103 current_path_index = search_my_index (get_path, getlen);
3104 /* FIXME: First check if you are adding yourself to the get path or not.
3105 if yes then don't check if current_path_index == 0, if not then check
3106 and next_hop == source_peer. */
3107 memcpy (next_hop, &get_path[current_path_index - 1], sizeof (struct GNUNET_PeerIdentity));
3109 GDS_NEIGHBOURS_send_get_result (get_result->expiration_time, &(get_result->key),
3111 get_result->type, payload_size,payload,
3113 next_hop, &(get_result->source_peer));
3116 return GNUNET_SYSERR;
3121 * FIXME: Is all trails threshold and routing table has some link.
3122 * Core handle for PeerTrailSetupMessage.
3123 * @param cls closure
3124 * @param message message
3125 * @param peer peer identity this notification is about
3126 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3129 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3130 const struct GNUNET_MessageHeader *message)
3132 const struct PeerTrailSetupMessage *trail_setup;
3133 struct GNUNET_PeerIdentity current_destination;
3134 struct GNUNET_PeerIdentity current_source;
3135 struct GNUNET_PeerIdentity source;
3136 struct GNUNET_PeerIdentity *next_hop;
3137 struct GNUNET_PeerIdentity next_peer;
3138 struct GNUNET_PeerIdentity *trail_peer_list;
3139 struct FriendInfo *target_friend;
3140 uint64_t destination_finger_value;
3141 uint32_t trail_length;
3142 uint32_t finger_map_index;
3145 msize = ntohs (message->size);
3146 if (msize < sizeof (struct PeerTrailSetupMessage))
3148 GNUNET_break_op (0);
3152 trail_setup = (const struct PeerTrailSetupMessage *) message;
3153 trail_length = ntohl (trail_setup->trail_length);
3155 if ((msize < sizeof (struct PeerTrailSetupMessage) +
3156 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3158 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3160 GNUNET_break_op (0);
3164 if (trail_length > 0)
3165 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
3166 memcpy (¤t_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity));
3167 memcpy (¤t_source,&(trail_setup->current_source), sizeof (struct GNUNET_PeerIdentity));
3168 memcpy (&source, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity));
3169 finger_map_index = ntohl (trail_setup->finger_map_index);
3170 destination_finger_value = ntohl (trail_setup->destination_finger);
3173 /* FIXME: Here we need to check 3 things
3174 * 1. if my routing table is all full
3175 * 2. if all my friends are congested
3176 * 3. if trail threshold of my friends have crossed.
3177 * In all these cases we need to send back trail rejection message. */
3178 if ( (GNUNET_YES == all_friends_trail_threshold)
3179 || (GNUNET_YES == GDS_ROUTING_check_threshold()))
3181 /* If all the friends have reached their trail threshold or if there is no
3182 more space in routing table to store more trails, then reject. */
3183 GDS_NEIGHBOURS_send_trail_rejection (&source, destination_finger_value, &my_identity,
3184 peer,finger_map_index, trail_peer_list,trail_length);
3190 /* Check if you are current_destination or not. */
3191 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3193 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3194 /* OPTIMIZATION: Choose a peer from find_successor and choose the closest one.
3195 In case the closest one is from routing table and it is NULL, then update
3197 if (next_hop == NULL)
3199 /* FIXME: Should we inform the peer before us. If not then it may continue
3200 to send us request. But in case we want to inform we need to have a
3201 different kind of message. */
3202 GNUNET_STATISTICS_update (GDS_stats,
3203 gettext_noop ("# Trail not found in routing table during"
3204 "trail setup request, packet dropped."),
3211 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
3214 if (NULL == next_hop)
3216 return GNUNET_SYSERR;
3218 else if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
3220 if (trail_length == 0)
3222 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
3226 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3229 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3231 /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
3232 if (PREDECESSOR_FINGER_ID != finger_map_index)
3234 /* FIXME: Is this correct assumption? A peer which think I am its predecessor,
3235 then I am not its predecessor. */
3236 compare_and_update_predecessor (&source, trail_peer_list, trail_length );
3238 GDS_NEIGHBOURS_send_trail_setup_result (&source,
3240 target_friend, trail_length,
3247 /* Now add yourself to the trail. */
3248 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3249 if (trail_length != 0)
3250 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3251 peer_list[trail_length] = my_identity;
3254 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3255 GDS_NEIGHBOURS_send_trail_setup (&source,
3256 destination_finger_value,
3257 ¤t_destination, ¤t_source,
3258 target_friend, trail_length, peer_list,
3266 * Core handle for p2p trail construction result messages.
3268 * @param message message
3269 * @param peer peer identity this notification is about
3270 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3273 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3274 const struct GNUNET_MessageHeader *message)
3276 const struct PeerTrailSetupResultMessage *trail_result;
3277 struct GNUNET_PeerIdentity *trail_peer_list;
3278 uint32_t trail_length;
3279 uint32_t finger_map_index;
3282 msize = ntohs (message->size);
3283 if (msize < sizeof (struct PeerTrailSetupResultMessage))
3285 GNUNET_break_op (0);
3289 trail_result = (const struct PeerTrailSetupResultMessage *) message;
3290 trail_length = ntohl (trail_result->trail_length);
3293 sizeof (struct PeerTrailSetupResultMessage) +
3294 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3296 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3298 GNUNET_break_op (0);
3302 finger_map_index = htonl (trail_result->finger_map_index);
3303 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
3305 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3308 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
3314 struct GNUNET_PeerIdentity next_hop;
3315 struct FriendInfo *target_friend;
3318 my_index = search_my_index (trail_peer_list, trail_length);
3319 if (my_index == GNUNET_SYSERR)
3320 return GNUNET_SYSERR;
3324 next_hop = trail_result->destination_peer;
3327 next_hop = trail_peer_list[my_index - 1];
3329 /* Finger table of destination peer will not contain any trail for the case
3330 * where destination peer is its own finger identity.*/
3331 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3332 &(trail_result->finger_identity))))
3334 GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
3338 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3339 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
3340 &(trail_result->finger_identity),
3341 target_friend, trail_length,
3346 return GNUNET_SYSERR;
3351 * Get my current predecessor from the finger peer map
3352 * @return Current predecessor.
3354 static struct FingerInfo *
3357 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
3358 struct GNUNET_PeerIdentity key_ret;
3359 unsigned int finger_index;
3360 struct FingerInfo *my_predecessor;
3363 /* Iterate over finger peer map and extract your predecessor. */
3364 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
3365 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
3367 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
3368 (finger_iter,&key_ret,(const void **)&my_predecessor))
3370 if(PREDECESSOR_FINGER_ID == my_predecessor->finger_map_index)
3377 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
3382 return my_predecessor;
3387 * Core handle for p2p verify successor messages.
3388 * @param cls closure
3389 * @param message message
3390 * @param peer peer identity this notification is about
3391 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3394 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3395 const struct GNUNET_MessageHeader *message)
3397 const struct PeerVerifySuccessorMessage *vsm;
3398 const struct GNUNET_PeerIdentity *trail_peer_list;
3399 struct GNUNET_PeerIdentity source_peer;
3400 struct GNUNET_PeerIdentity next_hop;
3401 struct FriendInfo *target_friend;
3403 uint32_t trail_length;
3405 msize = ntohs (message->size);
3406 if (msize < sizeof (struct PeerVerifySuccessorMessage))
3408 GNUNET_break_op (0);
3412 vsm = (struct PeerVerifySuccessorMessage *) message;
3413 trail_length = ntohl (vsm->trail_length);
3415 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
3416 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3417 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3419 GNUNET_break_op (0);
3422 trail_peer_list = (const struct GNUNET_PeerIdentity *)&vsm[1];
3423 memcpy (&source_peer, &(vsm->source_peer), sizeof(struct GNUNET_PeerIdentity));
3425 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
3427 struct FingerInfo *my_predecessor;
3428 if (trail_length == 0)
3430 /* SUPU: If I am friend of source_peer, then trail_length == 0. */
3431 memcpy (&next_hop, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3435 /* SUPU: Here I am the final destination successor, and trail does not contain
3436 destination. So, the next hop is the last element in the trail. */
3437 memcpy (&next_hop, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3439 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3441 my_predecessor = get_predecessor();
3442 if (NULL == my_predecessor)
3445 return GNUNET_SYSERR;
3448 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3449 &(my_predecessor->finger_identity))))
3451 /* Source peer and my predecessor, both are same. */
3452 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3454 &(my_predecessor->finger_identity),
3461 struct GNUNET_PeerIdentity *new_successor_trail;
3462 struct TrailPeerList *iterator;
3463 int new_trail_length;
3466 new_trail_length = trail_length + my_predecessor->first_trail_length + 1;
3467 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
3468 if (trail_length > 0)
3469 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
3471 memcpy (&new_successor_trail[trail_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3473 if (my_predecessor->first_trail_length)
3475 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
3476 iterator = my_predecessor->first_trail_head;
3477 i = trail_length + 1;
3478 while (i < new_trail_length)
3480 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
3481 iterator = iterator->next;
3486 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3488 &(my_predecessor->finger_identity),
3490 new_successor_trail,
3499 my_index = search_my_index (trail_peer_list, trail_length);
3500 if (my_index == GNUNET_SYSERR)
3503 return GNUNET_SYSERR;
3505 if (my_index == (trail_length - 1))
3507 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(vsm->successor));
3511 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3512 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3515 GDS_NEIGHBOURS_send_verify_successor (&(vsm->source_peer), &(vsm->successor),target_friend,
3516 trail_peer_list, trail_length);
3518 return GNUNET_SYSERR;
3523 * Core handle for p2p verify successor result messages.
3524 * @param cls closure
3525 * @param message message
3526 * @param peer peer identity this notification is about
3527 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3530 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3531 const struct GNUNET_MessageHeader *message)
3533 const struct PeerVerifySuccessorResultMessage *vsrm;
3534 struct GNUNET_PeerIdentity *trail_peer_list;
3535 struct GNUNET_PeerIdentity next_hop;
3536 struct FriendInfo *target_friend;
3538 uint32_t trail_length;
3540 msize = ntohs (message->size);
3541 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
3543 GNUNET_break_op (0);
3546 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
3547 trail_length = ntohl (vsrm->trail_length);
3550 sizeof (struct PeerVerifySuccessorResultMessage) +
3551 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3553 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3555 GNUNET_break_op (0);
3558 /* FIXME: URGENT: What happens when trail length = 0. */
3560 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
3562 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity))))
3564 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
3566 /* FIXME: Here we have got a new successor. But it may happen that our logic
3567 * says that this is not correct successor. so in finger table add it
3568 * failed to update the successor and we are still sending a notify
3569 * new successor. Here trail_length will be atleast 1, in case we have a new
3570 * successor because in that case our old successor is part of trail.
3571 * Could it be possible that our identity and my_predecessor is same. Check it. */
3572 if (GNUNET_YES == finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0))
3574 memcpy (&next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
3575 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3576 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
3577 target_friend, trail_peer_list,
3585 return GNUNET_SYSERR;
3593 my_index = search_my_index (trail_peer_list, trail_length);
3594 if (GNUNET_SYSERR == my_index)
3597 return GNUNET_SYSERR;
3602 /* Source is not part of trail, so if I am the last one then my index
3604 memcpy (&next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3608 memcpy (&next_hop, &trail_peer_list[my_index-1], sizeof (struct GNUNET_PeerIdentity));
3611 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3612 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
3613 &(vsrm->source_successor),
3614 &(vsrm->my_predecessor),
3620 return GNUNET_SYSERR;
3625 * Core handle for p2p notify new successor messages.
3626 * @param cls closure
3627 * @param message message
3628 * @param peer peer identity this notification is about
3629 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3632 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3633 const struct GNUNET_MessageHeader *message)
3635 const struct PeerNotifyNewSuccessorMessage *nsm;
3636 struct GNUNET_PeerIdentity *trail_peer_list;
3638 uint32_t trail_length;
3640 msize = ntohs (message->size);
3641 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
3643 GNUNET_break_op (0);
3646 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
3647 trail_length = ntohl (nsm->trail_length);
3649 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3650 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3652 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3654 GNUNET_break_op (0);
3658 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
3660 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), &my_identity)))
3662 /* I am the new successor. */
3663 struct GNUNET_PeerIdentity new_predecessor;
3664 memcpy (&new_predecessor, &(nsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
3665 if (GNUNET_NO == compare_and_update_predecessor (&new_predecessor, trail_peer_list,
3668 /* Someone claims to be my predecessor but its not closest predecessor
3671 return GNUNET_SYSERR;
3677 struct FriendInfo *target_friend;
3678 struct GNUNET_PeerIdentity next_hop;
3681 my_index = search_my_index (trail_peer_list, trail_length);
3682 if (GNUNET_SYSERR == my_index)
3685 return GNUNET_SYSERR;
3688 if (my_index == (trail_length - 1))
3690 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(nsm->destination_peer));
3694 memcpy (&next_hop, &trail_peer_list[my_index+1], sizeof (struct GNUNET_PeerIdentity));
3695 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3697 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
3698 &(nsm->destination_peer),
3699 target_friend, trail_peer_list,
3703 return GNUNET_SYSERR;
3708 * FIXME; Should we call select_random_friend from here in case I am the source
3709 * of the message or should I just return and in next iteration by default
3710 * we will call select random friend from send_find_finger_trail. But in that
3711 * case we should maintain a list of congested peer which failed to setup the
3712 * trail. and then in select random friend we should ignore them. this list
3713 * should have an expiration time and we should garbage collect it periodically.
3714 * Core handler for P2P trail rejection message
3715 * @param cls closure
3716 * @param message message
3717 * @param peer peer identity this notification is about
3718 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3721 int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3722 const struct GNUNET_MessageHeader *message)
3724 /* Here you have recevied the message it means that the peer next to you have
3725 failed to setup the trail to the finger identity value. now you should call
3726 find_successor and make sure that you don't choose the peer as next hop
3727 in order to do so, you need to pass a new parameter to find successor,
3728 congested peer - a peer which you should ignore. once you have found this
3729 peer then just send a trail setup message to that peer. In case you are
3730 also congested then remove yourself from the trail as this message
3731 reached to as you are part of the trail. and then send the message to
3732 element before you. Ideally you should be the last element in the trail as
3733 all the the elements before you have rejected you. In case you are source,
3734 then you should call select_random_Friend(congested_peer). in case you don't
3735 find any peer because congested peer then set flag that all friends are busy
3737 const struct PeerTrailRejectionMessage *trail_rejection;
3738 struct GNUNET_PeerIdentity *trail_peer_list;
3739 struct GNUNET_PeerIdentity source_peer;
3740 struct GNUNET_PeerIdentity congested_peer;
3741 struct FriendInfo *target_friend;
3742 struct GNUNET_PeerIdentity next_peer;
3743 struct GNUNET_PeerIdentity *next_hop;
3744 struct GNUNET_PeerIdentity current_source;
3745 struct GNUNET_PeerIdentity current_destination;
3747 uint32_t trail_length;
3748 uint32_t finger_map_index;
3749 uint64_t destination_finger_value;
3751 msize = ntohs (message->size);
3752 if (msize < sizeof (struct PeerTrailRejectionMessage))
3754 GNUNET_break_op (0);
3758 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3759 trail_length = ntohl (trail_rejection->trail_length);
3761 if ((msize < sizeof (struct PeerTrailRejectionMessage) +
3762 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3764 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3766 GNUNET_break_op (0);
3770 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3771 finger_map_index = ntohl (trail_rejection->finger_map_index);
3772 memcpy (&source_peer, &(trail_rejection->source_peer), sizeof(struct GNUNET_PeerIdentity));
3773 memcpy (&destination_finger_value, &(trail_rejection->finger_identity_value), sizeof (uint64_t));
3774 memcpy (&congested_peer, &(trail_rejection->congested_peer), sizeof (struct GNUNET_PeerIdentity));
3776 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source_peer)))
3778 /* I am the source of original trail setup message. Do nothing and exit. */
3779 /* In current implementation, when we don't get the result of a trail setup,
3780 then no entry is added to finger table and hence, by default a trail setup for
3781 the same finger map index is sent. so we don't need to send it here. */
3785 if(GDS_ROUTING_check_threshold())
3787 /* My routing state size has crossed the threshold, I can not be part of any more
3789 struct GNUNET_PeerIdentity *new_trail;
3791 if (trail_length == 1)
3793 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3797 /* FIXME: Here if I got the trail rejection message then I am the last element
3798 in the trail. So, I should choose trail_length-2.*/
3799 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
3802 /* Remove myself from the trail. */
3803 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3804 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3806 /* No more trails possible through me. send a trail rejection message to next hop. */
3807 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
3808 &next_peer,finger_map_index, new_trail,trail_length - 1);
3812 memcpy (¤t_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
3813 memcpy (¤t_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
3814 /* FIXME: After adding a new field in struct FriendInfo congested, then call
3815 find successor then it will never consider that friend by default. */
3816 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
3818 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, ¤t_destination))) /* This means I am the final destination */
3820 if (trail_length == 1)
3822 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3826 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3829 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3830 compare_and_update_predecessor (&source_peer, trail_peer_list, trail_length);
3832 GDS_NEIGHBOURS_send_trail_setup_result (&source_peer,
3834 target_friend, trail_length,
3839 else if (NULL == next_hop)
3841 /* No peer found. Send a trail rejection message to previous peer in the trail. */
3843 struct GNUNET_PeerIdentity *new_trail;
3845 if (trail_length == 1)
3847 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3851 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
3854 /* Remove myself from the trail. */
3855 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3856 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3858 /* No more trails possible through me. send a trail rejection message to next hop. */
3859 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
3860 &next_peer,finger_map_index, new_trail,trail_length - 1);
3865 /* Now add yourself to the trail. */
3866 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3867 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3868 peer_list[trail_length] = my_identity;
3871 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3872 GDS_NEIGHBOURS_send_trail_setup (&source_peer,
3873 destination_finger_value,
3874 ¤t_destination, ¤t_source,
3875 target_friend, trail_length, peer_list,
3879 return GNUNET_SYSERR;
3884 * FIXME: we don't send trail teardown to finger for which the trail was setup.
3885 * Trail teardown only aim is to remove entries from the routing table. Destination
3886 * finger does not have any entry in its routing table. So, it does not need
3888 * Core handle for p2p trail tear down messages.
3889 * @param cls closure
3890 * @param message message
3891 * @param peer peer identity this notification is about
3892 * @return GNUNET_OK on success, GNUNET_SYSERR on error
3895 int handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
3896 const struct GNUNET_MessageHeader *message)
3898 struct PeerTrailTearDownMessage *trail_teardown;
3899 struct GNUNET_PeerIdentity *trail_peer_list;
3900 struct GNUNET_PeerIdentity next_hop;
3901 struct FriendInfo *target_friend;
3902 uint32_t trail_length;
3906 msize = ntohs (message->size);
3907 if (msize < sizeof (struct PeerTrailTearDownMessage))
3909 GNUNET_break_op (0);
3913 trail_teardown = (struct PeerTrailTearDownMessage *) message;
3914 trail_length = ntohl (trail_teardown->trail_length);
3916 if ((msize < sizeof (struct PeerTrailTearDownMessage) +
3917 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3919 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3921 GNUNET_break_op (0);
3925 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_teardown[1];
3927 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer), &my_identity)))
3929 /* I am the destination of the trail, but I am not part of trail. I don't
3930 need to remove any entry from my routing table. So, I should not get this
3936 my_index = search_my_index (trail_peer_list, trail_length);
3937 if(GNUNET_SYSERR == my_index)
3938 return GNUNET_SYSERR;
3940 if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
3941 &(trail_teardown->destination_peer),peer))
3943 /* Here we get GNUNET_NO, only if there is no matching entry found in routing
3949 /* I am the last element of the trail. */
3950 if(my_index == trail_length - 1)
3953 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3954 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3956 GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer),
3957 &(trail_teardown->destination_peer),
3958 trail_peer_list, trail_length, target_friend);
3963 * Iterate over finger_peermap, and remove entries with peer as the first element
3965 * @param cls closure
3966 * @param key current public key
3967 * @param value value in the hash map
3968 * @return #GNUNET_YES if we should continue to
3970 * #GNUNET_NO if not.
3973 remove_matching_finger (void *cls,
3974 const struct GNUNET_PeerIdentity *key,
3977 struct FingerInfo *remove_finger = value;
3978 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
3980 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->first_trail_head->peer, disconnected_peer)
3981 || (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_finger->finger_identity), disconnected_peer)))
3983 GNUNET_assert (GNUNET_YES ==
3984 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
3987 free_finger (remove_finger);
3995 * Method called whenever a peer disconnects.
3997 * @param cls closure
3998 * @param peer peer identity this notification is about
4001 handle_core_disconnect (void *cls,
4002 const struct GNUNET_PeerIdentity *peer)
4004 struct FriendInfo *remove_friend;
4006 /* Check for self message. */
4007 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
4010 /* Search for peer to remove in your friend_peermap. */
4012 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4014 if (NULL == remove_friend)
4020 /* Remove fingers for which this peer is the first element in the trail or if
4021 * the friend is a finger. */
4022 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap,
4023 &remove_matching_finger, (void *)peer);
4025 /* Remove routing trails of which this peer is a part.
4026 * FIXME: Here do we only remove the entry from our own routing table
4027 * or do we also inform other peers which are part of trail. It seems to be
4028 * too much of messages exchanged. */
4029 GDS_ROUTING_remove_entry (peer);
4031 /* Remove the peer from friend_peermap. */
4032 GNUNET_assert (GNUNET_YES ==
4033 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
4037 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
4040 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4042 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4043 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4051 * Method called whenever a peer connects.
4053 * @param cls closure
4054 * @param peer_identity peer identity this notification is about
4057 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
4059 struct FriendInfo *friend;
4061 /* Check for connect to self message */
4062 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
4065 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
4067 /* If peer already exists in our friend_peermap, then exit. */
4068 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
4074 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
4077 friend = GNUNET_new (struct FriendInfo);
4078 friend->id = *peer_identity;
4079 friend->trails_count = 0;
4081 GNUNET_assert (GNUNET_OK ==
4082 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
4083 peer_identity, friend,
4084 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
4086 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
4087 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
4088 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
4093 * To be called on core init/fail.
4095 * @param cls service closure
4096 * @param identity the public identity of this peer
4099 core_init (void *cls,
4100 const struct GNUNET_PeerIdentity *identity)
4102 my_identity = *identity;
4107 * Initialize neighbours subsystem.
4108 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4111 GDS_NEIGHBOURS_init (void)
4113 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
4114 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
4115 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
4116 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
4117 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
4118 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
4119 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
4120 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
4121 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
4122 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
4123 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
4128 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
4129 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
4130 GNUNET_NO, core_handlers);
4131 if (NULL == core_api)
4132 return GNUNET_SYSERR;
4134 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
4135 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS * 4/3, GNUNET_NO);
4136 all_friends_trail_threshold = GNUNET_NO;
4143 * Shutdown neighbours subsystem.
4146 GDS_NEIGHBOURS_done (void)
4148 if (NULL == core_api)
4151 GNUNET_CORE_disconnect (core_api);
4154 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
4155 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
4156 friend_peermap = NULL;
4158 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
4159 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
4160 finger_peermap = NULL;
4162 /* FIXME: Here I have added GNUNET_break(0) as ideally if friend_peermap
4163 is already zero, then we really don't need to cancel it again. If this
4164 condition happens it mean we might have missed some corner case. But we
4165 cancel the task only in handle_core_disconnect. it may happen that this
4166 function is called but not handle_core_disconnect, In that case GNUNET_break(0)
4168 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4171 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4172 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4180 * @return my identity
4182 struct GNUNET_PeerIdentity
4183 GDS_NEIGHBOURS_get_my_id (void)
4189 /* end of gnunet-service-xdht_neighbours.c */