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 * Task that periodically verifies my successor. This task is started when we
716 * have found our successor.
718 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
721 * Identity of this peer.
723 static struct GNUNET_PeerIdentity my_identity;
726 * Hash map of all the friends of a peer
728 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
731 * Hash map of all the fingers of a peer
733 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
738 static struct GNUNET_CORE_Handle *core_api;
741 * Finger map index for predecessor entry in finger peermap.
743 #define PREDECESSOR_FINGER_ID 64
746 * Maximum number of trails allowed to go through a friend.
747 * FIXME: Better name, Random value at the moment, need to be adjusted to maintain a balance
748 * between performance and Sybil tolerance.
750 #define TRAIL_THROUGH_FRIEND_THRESHOLD 64
753 * Possible number of different trails to reach to a finger. (Redundant routing)
755 #define TRAIL_COUNT 2
758 * FIXME: better name.
759 * Set to GNUNET_YES, when the number of trails going through all my friends
760 * have reached the TRAIL_THROUGH_FRIEND_THRESHOLD.
762 static unsigned int all_friends_trail_threshold;
765 * The current finger index that we have want to find trail to.
767 static unsigned int current_search_finger_index;
771 * Iterate over trail and search your index location in the array.
772 * @param trail Trail which contains list of peers.
773 * @param trail_length Number of peers in the trail.
774 * @return Index in the array.
775 * #GNUNET_SYSERR, in case there is no entry which should not be the case ideally.
778 search_my_index (const struct GNUNET_PeerIdentity *trail,
783 while (i < trail_length)
785 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
791 return GNUNET_SYSERR;
795 * Compare two peer identities.
796 * @param p1 Peer identity
797 * @param p2 Peer identity
798 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
801 compare_peer_id (const void *p1, const void *p2)
803 struct Sorting_List *p11;
804 struct Sorting_List *p22;
806 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
807 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
808 p11 = (struct Sorting_List *)p1;
809 p22 = (struct Sorting_List *)p2;
810 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
811 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
817 * Return the predecessor of value in all_known_peers.
818 * @param all_known_peers list of all the peers
819 * @param value value we have to search in the all_known_peers.
820 * @param size Total numbers of elements
821 * @return Predecessor
823 static struct Sorting_List *
824 find_closest_predecessor(struct Sorting_List *all_known_peers, uint64_t value,
833 middle = (first + last)/2;
837 if(all_known_peers[middle].peer_id < value)
841 else if(all_known_peers[middle].peer_id == value)
845 return &all_known_peers[size - 1];
849 return &all_known_peers[middle - 1];
857 middle = (first + last)/2;
864 * Return the successor of value in all_known_peers.
865 * @param all_known_peers list of all the peers
866 * @param value value we have to search in the all_known_peers.
867 * @param size Total numbers of elements
870 static struct Sorting_List *
871 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
880 middle = (first + last)/2;
884 if(all_known_peers[middle].peer_id < value)
888 else if(all_known_peers[middle].peer_id == value)
890 if(middle == (size -1))
892 return &all_known_peers[0];
896 return &all_known_peers[middle+1];
904 middle = (first + last)/2;
911 * Called when core is ready to send a message we asked for
912 * out to the destination.
914 * @param cls the 'struct FriendInfo' of the target friend
915 * @param size number of bytes available in buf
916 * @param buf where the callee should write the message
917 * @return number of bytes written to buf
920 core_transmit_notify (void *cls, size_t size, void *buf)
922 struct FriendInfo *peer = cls;
924 struct P2PPendingMessage *pending;
929 while ((NULL != (pending = peer->head)) &&
930 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
932 peer->pending_count--;
933 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
934 GNUNET_free (pending);
938 /* no messages pending */
944 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
945 GNUNET_CORE_PRIO_BEST_EFFORT,
946 GNUNET_TIME_absolute_get_remaining
947 (pending->timeout), &peer->id,
948 ntohs (pending->msg->size),
949 &core_transmit_notify, peer);
950 GNUNET_break (NULL != peer->th);
954 while ((NULL != (pending = peer->head)) &&
955 (size - off >= (msize = ntohs (pending->msg->size))))
957 GNUNET_STATISTICS_update (GDS_stats,
959 ("# Bytes transmitted to other peers"), msize,
961 memcpy (&cbuf[off], pending->msg, msize);
963 peer->pending_count--;
964 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
965 GNUNET_free (pending);
967 if (peer->head != NULL)
970 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
971 GNUNET_CORE_PRIO_BEST_EFFORT,
972 GNUNET_TIME_absolute_get_remaining
973 (pending->timeout), &peer->id, msize,
974 &core_transmit_notify, peer);
975 GNUNET_break (NULL != peer->th);
983 * Transmit all messages in the friend's message queue.
985 * @param peer message queue to process
988 process_friend_queue (struct FriendInfo *peer)
990 struct P2PPendingMessage *pending;
992 if (NULL == (pending = peer->head))
994 if (NULL != peer->th)
997 GNUNET_STATISTICS_update (GDS_stats,
999 ("# Bytes of bandwidth requested from core"),
1000 ntohs (pending->msg->size), GNUNET_NO);
1002 /* FIXME: Are we correctly initializing importance and pending. */
1004 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1005 pending->importance,
1006 GNUNET_TIME_absolute_get_remaining
1007 (pending->timeout), &peer->id,
1008 ntohs (pending->msg->size),
1009 &core_transmit_notify, peer);
1010 GNUNET_break (NULL != peer->th);
1015 * Construct a trail message and forward it to a friend.
1016 * @param source_peer Peer which wants to set up the trail to one of its finger.
1017 * @param destination_finger Peer identity closest to this value will be
1018 * @a source_peer's finger.
1019 * @param current_destination Finger of the @a current_source, for which among
1020 * its friends, its own identity and all fingers, this
1021 * finger is the closest to the @a destination_finger
1022 * @param current_source Peer for which @a current_destination is its finger.
1023 * @param target_friend Friend to which this message should be forwarded.
1024 * @param trail_length Numbers of peers in the trail found so far.
1025 * @param trail_peer_list Peers this request has traversed so far
1026 * @param finger_map_index Index in finger peer map
1029 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
1030 uint64_t destination_finger,
1031 struct GNUNET_PeerIdentity *current_destination,
1032 struct GNUNET_PeerIdentity *current_source,
1033 struct FriendInfo *target_friend,
1034 unsigned int trail_length,
1035 const struct GNUNET_PeerIdentity *trail_peer_list,
1036 unsigned int finger_map_index)
1038 struct P2PPendingMessage *pending;
1039 struct PeerTrailSetupMessage *tsm;
1040 struct GNUNET_PeerIdentity *peer_list;
1043 msize = sizeof (struct PeerTrailSetupMessage) +
1044 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1046 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1052 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1054 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1058 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1059 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1060 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1061 pending->msg = &tsm->header;
1062 tsm->header.size = htons (msize);
1063 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
1064 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
1065 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1066 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
1067 memcpy (&(tsm->current_source), current_source, sizeof (struct GNUNET_PeerIdentity));
1068 tsm->trail_length = htonl (trail_length);
1069 tsm->finger_map_index = htonl (finger_map_index);
1071 if (trail_length > 0)
1073 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1074 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1077 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1078 target_friend->pending_count++;
1079 process_friend_queue (target_friend);
1085 * Construct a trail setup result message and forward it to a friend.
1086 * @param destination_peer Peer which will get the trail to one of its finger.
1087 * @param source_finger Peer to which the trail has been setup to.
1088 * @param target_friend Friend to which this message should be forwarded.
1089 * @param trail_length Numbers of peers in the trail.
1090 * @param trail_peer_list Peers which are part of the trail from source to destination.
1091 * @param finger_map_index Index in finger peer map
1094 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destination_peer,
1095 const struct GNUNET_PeerIdentity *source_finger,
1096 struct FriendInfo *target_friend,
1097 unsigned int trail_length,
1098 const struct GNUNET_PeerIdentity *trail_peer_list,
1099 unsigned int finger_map_index)
1101 struct P2PPendingMessage *pending;
1102 struct PeerTrailSetupResultMessage *tsrm;
1103 struct GNUNET_PeerIdentity *peer_list;
1106 msize = sizeof (struct PeerTrailSetupResultMessage) +
1107 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1109 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1115 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1117 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1121 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1122 pending->importance = 0;
1123 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1124 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1125 pending->msg = &tsrm->header;
1126 tsrm->header.size = htons (msize);
1127 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
1128 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1129 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
1130 tsrm->trail_length = htonl (trail_length);
1131 tsrm->finger_map_index = htonl (finger_map_index);
1133 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1134 if (trail_length > 0)
1136 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1138 /* Send the message to chosen friend. */
1139 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1140 target_friend->pending_count++;
1141 process_friend_queue (target_friend);
1146 * Construct a PeerVerifySuccessor message and send it to friend.
1147 * @param source_peer Peer which wants to verify its successor
1148 * @param successor Peer which is our current successor
1149 * @param target_friend Friend to which this message should be forwarded.
1150 * @param trail_peer_list Peer which are part of trail from source to destination
1151 * @param trail_length Number of peers in the trail list.
1153 void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *source_peer,
1154 const struct GNUNET_PeerIdentity *successor,
1155 struct FriendInfo *target_friend,
1156 const struct GNUNET_PeerIdentity *trail_peer_list,
1157 unsigned int trail_length)
1159 struct PeerVerifySuccessorMessage *vsm;
1160 struct P2PPendingMessage *pending;
1161 struct GNUNET_PeerIdentity *peer_list;
1164 msize = sizeof (struct PeerVerifySuccessorMessage) +
1165 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1167 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1173 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1175 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1179 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1180 pending->importance = 0; /* FIXME */
1181 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1182 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1183 pending->msg = &vsm->header;
1184 vsm->header.size = htons (msize);
1185 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1186 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
1187 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1188 vsm->trail_length = htonl (trail_length);
1190 if (trail_length > 0)
1192 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1193 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1196 /* Send the message to chosen friend. */
1197 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1198 target_friend->pending_count++;
1199 process_friend_queue (target_friend);
1205 * Construct a PeerVerifySuccessorResult message and send it to friend.
1206 * @param destination_peer Peer which sent verify successor message
1207 * @param source_successor Peer to which verify successor message was sent.
1208 * @param my_predecessor source_successor's predecessor.
1209 * @param target_friend Friend to which this message should be forwarded.
1210 * @param trail_peer_list Peers which are part of trail from source to destination
1211 * @param trail_length Number of peers in the trail list.
1213 void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *destination_peer,
1214 const struct GNUNET_PeerIdentity *source_successor,
1215 const struct GNUNET_PeerIdentity *my_predecessor,
1216 struct FriendInfo *target_friend,
1217 const struct GNUNET_PeerIdentity *trail_peer_list,
1218 unsigned int trail_length)
1220 struct PeerVerifySuccessorResultMessage *vsmr;
1221 struct P2PPendingMessage *pending;
1222 struct GNUNET_PeerIdentity *peer_list;
1225 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1226 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1228 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1235 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1237 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1241 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1242 pending->importance = 0; /* FIXME */
1243 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1244 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1245 pending->msg = &vsmr->header;
1246 vsmr->header.size = htons (msize);
1247 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1248 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1249 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1250 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1251 vsmr->trail_length = htonl (trail_length);
1252 if (trail_length > 0)
1254 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1255 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1258 /* Send the message to chosen friend. */
1259 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1260 target_friend->pending_count++;
1261 process_friend_queue (target_friend);
1266 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1267 * @param source_peer Peer which is sending notify message to its new successor.
1268 * @param destination_peer Peer which is the new destination.
1269 * @param target_friend Next friend to pass this message to.
1270 * @param peer_list List of peers in the trail to reach to destination_peer.
1271 * @param trail_length Total number of peers in peer list
1274 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1275 const struct GNUNET_PeerIdentity *destination_peer,
1276 struct FriendInfo *target_friend,
1277 const struct GNUNET_PeerIdentity *trail_peer_list,
1278 unsigned int trail_length)
1280 struct PeerNotifyNewSuccessorMessage *nsm;
1281 struct P2PPendingMessage *pending;
1282 struct GNUNET_PeerIdentity *peer_list;
1285 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1286 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1288 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1294 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1296 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1300 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1301 pending->importance = 0; /* FIXME */
1302 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1303 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1304 pending->msg = &nsm->header;
1305 nsm->header.size = htons (msize);
1306 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1307 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1308 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1309 nsm->trail_length = htonl (trail_length);
1310 /* FIXME: Here I am not checking the trail length, as I am assuming that for new
1311 successor our old successor is a part of trail, so trail length > 1. */
1312 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1313 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1315 /* Send the message to chosen friend. */
1316 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1317 target_friend->pending_count++;
1318 process_friend_queue (target_friend);
1322 * Send a trail tear down message
1323 * @param source_peer Source of the trail.
1324 * @param destination_peer Destination of the trail.
1325 * @param trail_list Peers in the trail from @a source_peer to @a destination_peer
1326 * @param trail_length Total number of peers in trail_list.
1327 * @pararm target_peer Next peer to forward this message to.
1330 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_PeerIdentity *source_peer,
1331 const struct GNUNET_PeerIdentity *destination_peer,
1332 struct GNUNET_PeerIdentity *trail_peer_list,
1333 unsigned int trail_length,
1334 struct FriendInfo *target_friend)
1336 struct P2PPendingMessage *pending;
1337 struct PeerTrailTearDownMessage *ttdm;
1338 struct GNUNET_PeerIdentity *peer_list;
1341 msize = sizeof (struct PeerTrailTearDownMessage) +
1342 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1344 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1350 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1352 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1356 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1357 pending->importance = 0; /* FIXME */
1358 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1359 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1360 pending->msg = &ttdm->header;
1361 ttdm->header.size = htons (msize);
1362 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1363 memcpy (&(ttdm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1364 memcpy (&(ttdm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1365 ttdm->trail_length = htonl (trail_length);
1367 peer_list = (struct GNUNET_PeerIdentity *) &ttdm[1];
1368 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1370 /* Send the message to chosen friend. */
1371 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1372 target_friend->pending_count++;
1373 process_friend_queue (target_friend);
1378 * FIMXE: Change the return value, to handle the case where all friends
1380 * FIXME: Handle congested peer - don't choose this friend, also don't choose
1381 * the friend if the link threshold has crossed. Not implemented yet.
1382 * Randomly choose one of your friends from the friends_peer map
1385 static struct FriendInfo *
1386 select_random_friend ()
1388 unsigned int current_size;
1389 unsigned int *index;
1391 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1392 struct GNUNET_PeerIdentity key_ret;
1393 struct FriendInfo *friend;
1395 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1396 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1397 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1401 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1409 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1411 /* Possible number of trails that can go through this friend has been reached. */
1412 if (friend->trails_count > TRAIL_THROUGH_FRIEND_THRESHOLD)
1414 /* FIXME: What should I do now, should I call this same function again and
1415 remember the index, j so that call random function without j and find
1416 a new friend. Also, I need some way to make sure that if number of times
1417 I have called the function is equal to number of entries in friend peermap.
1418 then I should return NULL. but its much better to have a function which
1419 just eliminates looking at the entries with threshold crossed. URGENT: Whats
1420 the best way to handle this case? */
1430 * Compute finger_identity to which we want to setup the trail
1431 * @return finger_identity
1434 compute_finger_identity()
1438 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1439 my_id64 = GNUNET_ntohll (my_id64);
1440 return (my_id64 + (unsigned long) pow (2, current_search_finger_index));
1445 * Compute immediate predecessor identity in the network.
1446 * @return peer identity of immediate predecessor.
1449 compute_predecessor_identity()
1453 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1454 my_id64 = GNUNET_ntohll (my_id64);
1455 return (my_id64 -1);
1460 * Periodically ping your successor to ask its current predecessor
1462 * @param cls closure for this task
1463 * @param tc the context under which the task is running
1466 send_verify_successor_message (void *cls,
1467 const struct GNUNET_SCHEDULER_TaskContext *tc )
1469 struct GNUNET_TIME_Relative next_send_time;
1470 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1471 struct GNUNET_PeerIdentity key_ret;
1472 struct FriendInfo *target_friend;
1473 struct GNUNET_PeerIdentity next_hop;
1474 struct GNUNET_PeerIdentity *peer_list;
1475 struct FingerInfo *finger;
1476 unsigned int finger_index;
1479 /* Find the successor from the finger peermap.*/
1480 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1481 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1483 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1484 (const void **)&finger))
1486 if (0 == finger->finger_map_index)
1493 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1497 goto send_new_request;
1500 if (finger->first_trail_length > 0)
1502 struct TrailPeerList *iterate;
1504 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->first_trail_length);
1505 iterate = finger->first_trail_head;
1507 while ( i < (finger->first_trail_length))
1510 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1511 iterate = iterate->next;
1514 memcpy (&next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1515 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
1519 /* If trail length = 0, then our successor is our friend. */
1521 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1522 &(finger->finger_identity));
1525 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1526 &(finger->finger_identity),
1529 finger->first_trail_length);
1532 next_send_time.rel_value_us =
1533 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1534 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1535 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1538 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1545 * 1. Need to handle the case where all friends are either congested or
1546 * have reached their threshold.
1547 * 2. If we need all_friends_trail_threshold
1548 * 3. do we need to check if friend peermap is empty or not.
1549 * Choose a random friend and start looking for the trail to reach to
1550 * finger identity through this random friend.
1552 * @param cls closure for this task
1553 * @param tc the context under which the task is running
1556 send_find_finger_trail_message (void *cls,
1557 const struct GNUNET_SCHEDULER_TaskContext *tc)
1559 struct FriendInfo *target_friend;
1560 struct GNUNET_TIME_Relative next_send_time;
1561 uint64_t finger_identity;
1562 unsigned int finger_map_index;
1564 next_send_time.rel_value_us =
1565 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1566 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1567 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1568 find_finger_trail_task =
1569 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1572 if (GNUNET_YES == all_friends_trail_threshold)
1574 /* All friends in friend peer map, have reached their trail threshold. No
1575 more new trail can be created. */
1579 target_friend = select_random_friend ();
1580 if (NULL == target_friend)
1582 all_friends_trail_threshold = GNUNET_YES;
1586 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
1588 finger_identity = compute_predecessor_identity();
1592 finger_identity = compute_finger_identity();
1595 finger_map_index = current_search_finger_index;
1596 GDS_NEIGHBOURS_send_trail_setup (&my_identity, finger_identity, &(target_friend->id),
1597 &my_identity, target_friend, 0, NULL, finger_map_index);
1603 /* In this function, we want to return the compressed trail and the trail length.
1604 We can send back a new trail and update the trail length value as we get as
1605 parameter to our function. There are many cases where we don't need to call
1606 this function. Move that logic to calling function. */
1608 * Scan the trail to check if any of my own friend is part of trail. If yes
1609 * then shortcut the trail, update trail length and send back the new trail.
1610 * @param trail[Out] Current trail to reach to @a finger, will be updated
1611 * in case we compress the trail.
1612 * @param trail_length[Out] Number of peers in @a finger_trail, will be updated
1613 * in case we compress the trail.
1614 * @param finger Finger identity
1617 scan_and_compress_trail (struct GNUNET_PeerIdentity *trail,
1618 unsigned int *trail_length,
1619 const struct GNUNET_PeerIdentity *finger)
1623 /* If finger is my friend, then set trail_length = 0;*/
1624 if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger))
1626 /* supu' delete entry from the thrail. */
1632 i = *trail_length - 1;
1635 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
1637 /* This element of trail is not my friend. */
1642 /* A --> B(friend 1) --> C(friend 2)--> D ---> E, then we can rewrite the trail as
1644 * Now, we should remove the entry from A's routing table, B's routing table
1645 * and update the entry in C's routing table. Rest everything will be same.
1646 * C's routing table should have source peer as the prev.hop.
1647 * In case we found a friend not at i = 0, then we can discard all the
1648 peers before it in the trail and short cut the path. We need to send
1649 trail teardown message also but not to all the peers in the trail. only
1650 the peer just behind me and also update the routing table of the friend,
1651 to prev hop as the source peer ie my_identity. */
1652 struct GNUNET_PeerIdentity *discarded_trail;
1653 struct FriendInfo *target_friend;
1654 int discarded_trail_length;
1656 /* Here I am adding the friend (C) found to the discarded trail also, as we
1657 need to update its routing table also. */
1658 discarded_trail_length = i;
1659 discarded_trail = GNUNET_malloc (discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1660 memcpy (discarded_trail, trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1661 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
1662 /* send_update_routing_table(friend). so that it removes prev hop
1663 and update it to source for given finger. */
1664 /* FIXME: Modify trail_teardown function to handle such cases. In case
1665 the last element of the trail update the routing table, in case it
1666 is trail compression. But teardown is called from various places so
1667 need to differentiate these two cases. URGENT*/
1668 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, discarded_trail,
1669 discarded_trail_length, target_friend);
1671 /* Copy the trail from index i to index trail_length -1 and change
1672 trail length and return */
1673 while (i < *trail_length)
1675 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
1679 *trail_length = j+1;
1688 * FIXME: Is this correct? Here I am using dll_remove and its documentation
1689 * reads something else. Verify. Urgent.
1690 * Free finger and its trail.
1691 * @param finger Finger to be freed.
1694 free_finger (struct FingerInfo *finger)
1696 struct TrailPeerList *peer;
1698 if(finger->first_trail_head != NULL)
1700 while (NULL != (peer = finger->first_trail_head))
1702 GNUNET_CONTAINER_DLL_remove (finger->first_trail_head, finger->first_trail_tail, peer);
1707 if (finger->second_trail_head != NULL)
1709 while (NULL != (peer = finger->second_trail_head))
1711 GNUNET_CONTAINER_DLL_remove (finger->second_trail_head, finger->second_trail_tail, peer);
1714 GNUNET_free (finger);
1720 * * 1.* If you remove an entry from finger table, and if the finger is not your friend
1721 * and the trail length > 1 for the finger that you removed, then you should send
1722 * a trail_teardown message along the trail. so that the peers which have an
1723 * entry in their routing table for this trail can remove it from their routing
1726 * TODO: First check if both the trails are present if yes then send it
1728 * @param existing_finger
1731 void send_trail_teardown (struct FingerInfo *existing_finger)
1733 struct GNUNET_PeerIdentity *peer_list;
1734 struct FriendInfo *friend;
1735 struct TrailPeerList *finger_trail;
1736 int existing_finger_trail_length = existing_finger->first_trail_length;
1740 if (existing_finger->first_trail_length == 0)
1742 finger_trail = existing_finger->first_trail_head;
1743 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(finger_trail->peer));
1744 peer_list = GNUNET_malloc ( existing_finger_trail_length * sizeof (struct GNUNET_PeerIdentity));
1745 while (i < existing_finger->first_trail_length)
1747 memcpy (&peer_list[i], &(finger_trail->peer), sizeof (struct GNUNET_PeerIdentity));
1748 finger_trail = finger_trail->next;
1752 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, &(existing_finger->finger_identity),
1753 peer_list, existing_finger_trail_length, friend);
1758 * Add a new trail to reach an existing finger in finger peermap.
1759 * @param existing_finger
1761 * @param trail_length
1764 void add_new_trail (struct FingerInfo *existing_finger,
1765 struct GNUNET_PeerIdentity *trail,
1766 unsigned int trail_length)
1771 if (existing_finger->second_trail_head != NULL)
1773 while (i < trail_length)
1775 struct TrailPeerList *element;
1776 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1777 element->next = NULL;
1778 element->prev = NULL;
1780 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1781 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1785 else if (existing_finger->second_trail_head != NULL)
1787 while (i < trail_length)
1789 struct TrailPeerList *element;
1790 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1791 element->next = NULL;
1792 element->prev = NULL;
1794 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1795 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1799 existing_finger->trail_count++;
1804 * FIXME: In this case first you should check which of the trail is longest and
1805 * the just discard it. Right now you are not checking it.
1806 * In case there are already maximum number of possible trail to reach to a finger,
1807 * then check if the new trail can replace an existing one. If yes then replace.
1808 * @param existing_finger
1810 * @param trail_length
1811 * @return #GNUNET_YES
1815 void select_and_replace_trail (struct FingerInfo *existing_finger,
1816 struct GNUNET_PeerIdentity *trail,
1817 unsigned int trail_length)
1819 if (trail_length < existing_finger->first_trail_length)
1821 struct TrailPeerList *peer;
1824 while (NULL != (peer = existing_finger->first_trail_head))
1826 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1830 while (i < trail_length)
1832 struct TrailPeerList *element;
1833 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1834 element->next = NULL;
1835 element->prev = NULL;
1837 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1838 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1842 else if (trail_length < existing_finger->second_trail_length)
1844 struct TrailPeerList *peer;
1847 while (NULL != (peer = existing_finger->second_trail_head))
1849 GNUNET_CONTAINER_DLL_remove (existing_finger->second_trail_head, existing_finger->second_trail_tail, peer);
1853 while (i < trail_length)
1855 struct TrailPeerList *element;
1856 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1857 element->next = NULL;
1858 element->prev = NULL;
1860 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1861 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1869 * FIXME: If we remove a finger which is our friend, then do we need to handle it
1870 * differentlty in regard to trail count.
1871 * Decrement the trail count for the first friend to reach to the finger.
1875 decrement_friend_trail_count (struct FingerInfo *finger)
1877 struct FriendInfo *first_trail_friend;
1878 struct FriendInfo *second_trail_friend;
1880 if(finger->first_trail_head != NULL)
1882 first_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1883 &(finger->first_trail_head->peer));
1884 first_trail_friend->trails_count--;
1887 if(finger->second_trail_head != NULL)
1889 second_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1890 &(finger->second_trail_head->peer));
1891 second_trail_friend->trails_count--;
1894 if (GNUNET_YES == all_friends_trail_threshold)
1896 all_friends_trail_threshold = GNUNET_NO;
1897 /* FIXME; Here you should reschedule the send_find_finger_task here. or
1904 * FIXME: consider the case where my_id = 2, and we are in circle from 0 to 7.
1905 * my current_predecessor is 6, and now the new finger 1. Here we are checking
1906 * if existing_finger < new_entry then new_entry is predecessor. This holds
1907 * true in case where lets say existing_finger = 5, new_entry= 6. But in the case
1908 * above, 6 > 1 but still 1 is correct predecessor. We have not handled it here.
1909 * We can put all the three values in an array and then the peer just before me
1910 * will be mine predecessor.
1911 * FIXME: Currently I am using struct Sorting_list to compare the values,
1912 * will create a new ds if needed.
1913 * @param existing_finger
1918 int select_finger (struct FingerInfo *existing_finger,
1919 const struct GNUNET_PeerIdentity *new_finger,
1920 unsigned int finger_map_index)
1922 struct Sorting_List peers[3]; /* 3 for existing_finger, new_finger, my_identity */
1923 struct Sorting_List *closest_finger;
1927 for (k = 0; k < 3; k++)
1930 memcpy (&peers[0], &my_identity, sizeof (uint64_t));
1931 peers[0].type = MY_ID;
1932 peers[0].data = NULL;
1934 memcpy (&peers[1], &(existing_finger->finger_identity), sizeof (uint64_t));
1935 peers[1].type = FINGER;
1936 peers[1].data = existing_finger;
1938 memcpy (&peers[2], &new_finger, sizeof (uint64_t));
1939 peers[2].type = VALUE;
1940 peers[2].data = NULL;
1942 memcpy (&value, &my_identity, sizeof (uint64_t));
1945 qsort (&peers, 3, sizeof (struct Sorting_List), &compare_peer_id);
1947 if (PREDECESSOR_FINGER_ID == finger_map_index)
1948 closest_finger = find_closest_predecessor (peers, value, 3);
1950 closest_finger = find_closest_successor (peers, value, 3);
1952 if (closest_finger->type == FINGER)
1956 else if (closest_finger->type == VALUE)
1960 else if (closest_finger->type == MY_ID);
1962 return GNUNET_SYSERR;
1968 * Choose the closest finger between existing_finger and new_finger. In case new_finger
1969 * is closest and finger_map_index != PREDCESSOR_FINGER_ID,
1970 * then send a tear down message along the trail to reach existing_finger.
1971 * @param existing_finger Existing entry in finger peer map
1972 * @param new_finger New finger
1973 * @param trail Trail to reach to the new finger from me.
1974 * @param trail_length Number of peers in the @a trail
1975 * @param finger_map_index If finger_map_index == PREDECESSOR_FINGER_INDEX,
1976 * then we use a different logic to find the closest
1978 * @return #GNUNET_YES In case we want to store the new entry.
1979 * #GNUNET_NO In case we want the existing entry.
1980 * #GNUNET_SYSERR Error.
1983 int select_closest_finger (struct FingerInfo *existing_finger,
1984 const struct GNUNET_PeerIdentity *new_finger,
1985 struct GNUNET_PeerIdentity *trail,
1986 unsigned int trail_length,
1987 unsigned int finger_map_index)
1990 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), new_finger))
1992 /* Both the new entry and existing entry are same. */
1993 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), &my_identity))
1995 /* If both are same then exit. You already have that entry in your finger table,
1996 then you don't need to add it again. */
1999 if (trail_length > 1)
2001 scan_and_compress_trail (trail, &trail_length, new_finger);
2003 if (existing_finger->trail_count < TRAIL_COUNT)
2005 add_new_trail (existing_finger, trail, trail_length);
2010 select_and_replace_trail (existing_finger, trail, trail_length);
2014 else if (GNUNET_YES == select_finger (existing_finger, new_finger, finger_map_index))
2016 /* Here in case finger_map_index was Predecessor_finger then also you don't
2017 need to send trail teardown and in case its successor then you found it in
2018 trail_setup and then you don't need to send trail teardown. FIXME: check if
2019 its true for every call made to finger_table_add. Also, if we have an entry
2020 which is not my identity should I replace it with my identity or not? */
2021 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, new_finger))
2023 return GNUNET_NO; /* FIXME: In case I have a peer id which is not my id then
2024 * should I keep it as finger */
2027 /* new_finger is the correct finger. */
2028 if (PREDECESSOR_FINGER_ID != finger_map_index)
2029 send_trail_teardown (existing_finger);
2031 decrement_friend_trail_count (existing_finger);
2032 free_finger (existing_finger);
2033 if (trail_length > 1)
2034 scan_and_compress_trail (trail, &trail_length, new_finger);
2037 else if (GNUNET_NO == select_finger (existing_finger, new_finger,finger_map_index))
2039 /* existing_finger is the correct finger. */
2042 return GNUNET_SYSERR;
2047 * Check if there is a predecessor in our finger peer map or not.
2048 * If no, then return GNUNET_YES
2049 * else compare existing predecessor and peer, and find the correct
2051 * @param existing_predecessor
2052 * @param new_predecessor
2053 * @return #GNUNET_YES if new peer is predecessor
2054 * #GNUNET_NO if new peer is not the predecessor.
2057 compare_and_update_predecessor (const struct GNUNET_PeerIdentity *peer,
2058 struct GNUNET_PeerIdentity *trail,
2059 unsigned int trail_length)
2061 /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
2062 struct FingerInfo *existing_finger;
2063 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2064 struct FingerInfo *new_finger_entry;
2065 struct FriendInfo *first_friend_trail;
2068 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2069 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2071 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2072 (const void **)&existing_finger))
2074 if (PREDECESSOR_FINGER_ID == existing_finger->finger_map_index)
2076 if( GNUNET_NO == select_closest_finger (existing_finger, peer, trail,
2077 trail_length,PREDECESSOR_FINGER_ID))
2084 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2086 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2087 memcpy (&(new_finger_entry->finger_identity), peer, sizeof (struct GNUNET_PeerIdentity));
2088 new_finger_entry->finger_map_index = PREDECESSOR_FINGER_ID;
2089 new_finger_entry->first_trail_length = trail_length;
2091 if (trail != NULL) /* finger_trail is NULL in case I am my own finger identity. */
2093 /* FIXME: Currently we are not handling the second trail. In that case, finger
2094 trail count = min (first_friend, second_friend) trail count. */
2095 /* Incrementing the friend trails count. */
2096 if (trail_length > 0)
2098 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
2099 first_friend_trail->trails_count++;
2103 /* It means the finger is my friend. */
2104 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
2105 first_friend_trail->trails_count++;
2107 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2109 if (trail_length != 0)
2111 i = trail_length - 1;
2114 struct TrailPeerList *element;
2115 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2116 element->next = NULL;
2117 element->prev = NULL;
2119 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
2120 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2123 struct TrailPeerList *element;
2124 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2125 element->next = NULL;
2126 element->prev = NULL;
2127 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
2128 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2131 GNUNET_assert (GNUNET_OK ==
2132 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2133 &(new_finger_entry->finger_identity),
2135 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
2142 * FIXME: Better name, and make the code more cleaner.
2143 * Compare the new finger entry added and our successor.
2144 * @return #GNUNET_YES if same.
2145 * #GNUNET_NO if not.
2148 compare_new_entry_and_successor (const struct GNUNET_PeerIdentity *new_finger,
2149 int finger_map_index)
2151 int successor_flag = 0;
2152 struct FingerInfo *successor_finger;
2153 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2156 if (PREDECESSOR_FINGER_ID == finger_map_index)
2159 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2160 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2162 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2163 (const void **)&successor_finger))
2165 if (successor_finger->finger_map_index == 0)
2172 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2174 /* Ideally we should never reach here. */
2175 if (successor_flag == 0)
2181 if (0 == GNUNET_CRYPTO_cmp_peer_identity (new_finger, &(successor_finger->finger_identity)))
2189 * FIXME: ensure that function sending finger_table_add checks if source and your
2190 * identity is same, if yes then set trail_list to NULL and trail length = 0.
2191 * Add an entry in the finger table. If there is already an existing entry in
2192 * the finger peermap for given finger map index, then choose the closest one.
2193 * In case both the new entry and old entry are same, store both of them. (Redundant
2195 * @param finger_identity
2196 * @param finger_trail
2197 * @param finger_trail_length
2198 * @param finger_map_index
2199 * @return #GNUNET_YES if the new entry is added.
2200 * #GNUNET_NO if the new entry is discarded.
2203 int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
2204 struct GNUNET_PeerIdentity *finger_trail,
2205 uint32_t finger_trail_length,
2206 uint32_t finger_map_index)
2208 struct FingerInfo *new_finger_entry;
2209 struct FingerInfo *existing_finger;
2210 struct FriendInfo *first_friend_trail;
2211 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2212 int new_entry_added_flag = 0;
2215 if (PREDECESSOR_FINGER_ID == finger_map_index)
2217 compare_and_update_predecessor (finger_identity, finger_trail, finger_trail_length);
2218 goto update_current_search_finger_index;
2221 /* Check if there is already an entry for the finger map index in the finger peer map. */
2222 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2223 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2225 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2226 (const void **)&existing_finger))
2228 if (existing_finger->finger_map_index == finger_map_index)
2230 if ( GNUNET_NO == select_closest_finger (existing_finger, finger_identity,
2231 finger_trail, finger_trail_length,finger_map_index))
2232 goto update_current_search_finger_index;
2238 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2240 /* Add a new entry. */
2241 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2242 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
2243 new_finger_entry->finger_map_index = finger_map_index;
2244 new_finger_entry->first_trail_length = finger_trail_length;
2245 new_finger_entry->trail_count = 1;
2247 if (finger_trail != NULL) /* finger_trail is NULL in case I am my own finger identity. */
2249 /* FIXME: Currently we are not handling the second trail. In that case, finger
2250 trail count = min (first_friend, second_friend) trail count. */
2251 /* Incrementing the friend trails count. */
2252 if (finger_trail_length > 0)
2254 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_trail[0]);
2255 first_friend_trail->trails_count++;
2259 /* It means the finger is my friend. */
2260 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger_identity);
2261 first_friend_trail->trails_count++;
2263 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2265 /* Copy the trail. */
2267 while (i < finger_trail_length)
2269 struct TrailPeerList *element;
2270 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2271 element->next = NULL;
2272 element->prev = NULL;
2274 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
2275 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2280 new_entry_added_flag = 1;
2281 GNUNET_assert (GNUNET_OK ==
2282 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2283 &(new_finger_entry->finger_identity),
2285 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
2287 /* Update the value of current_search_finger_index. */
2288 update_current_search_finger_index:
2289 if (0 == finger_map_index )
2291 current_search_finger_index = PREDECESSOR_FINGER_ID;
2292 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,&(new_finger_entry->finger_identity)))
2293 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
2295 else if (GNUNET_YES == compare_new_entry_and_successor (finger_identity,finger_map_index))
2297 /* If the new entry is same as our successor, then reset the current_search_finger_index to 0*/
2298 current_search_finger_index = 0;
2302 current_search_finger_index = current_search_finger_index - 1;
2305 if (1 == new_entry_added_flag)
2313 * FIXME: In case a friend is either congested or has crossed its trail threshold,
2314 * then don't consider it as next successor, In case of finger if its first
2315 * friend has crossed the threshold then don't consider it. In case no finger
2316 * or friend is found, then return NULL.
2317 * Find closest successor for the value.
2318 * @param value Value for which we are looking for successor
2319 * @param[out] current_destination set to my_identity in case I am the final destination,
2320 * set to friend identity in case friend is final destination,
2321 * set to first friend to reach to finger, in case finger
2322 * is final destination.
2323 * @param[out] current_source set to my_identity.
2324 * @return Peer identity of next hop to send trail setup message to,
2325 * NULL in case all the friends are either congested or have crossed
2326 * their trail threshold.
2328 static struct GNUNET_PeerIdentity *
2329 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
2330 struct GNUNET_PeerIdentity *current_source)
2332 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
2333 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2334 struct GNUNET_PeerIdentity key_ret;
2335 struct FriendInfo *friend;
2336 struct FingerInfo *finger;
2337 unsigned int finger_index;
2338 unsigned int friend_index;
2339 struct Sorting_List *successor;
2343 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
2344 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
2345 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
2348 struct Sorting_List all_known_peers[size];
2351 for (k = 0; k < size; k++)
2352 all_known_peers[k].peer_id = 0;
2354 /* Copy your identity at 0th index in all_known_peers. */
2356 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
2357 all_known_peers[j].type = MY_ID;
2358 all_known_peers[j].data = 0;
2362 all_known_peers[j].peer_id = value;
2363 all_known_peers[j].type = VALUE;
2364 all_known_peers[j].data = 0;
2367 /* Iterate over friend peer map and copy all the elements into array. */
2368 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2369 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
2371 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
2373 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
2374 all_known_peers[j].type = FRIEND;
2375 all_known_peers[j].data = friend;
2381 /* Iterate over finger map and copy all the entries into all_known_peers array. */
2382 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2383 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2385 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
2387 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
2388 all_known_peers[j].type = FINGER;
2389 all_known_peers[j].data = finger;
2394 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2395 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
2398 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
2400 /* search value in all_known_peers array. */
2401 successor = find_closest_successor (all_known_peers, value, size);
2403 if (successor->type == MY_ID)
2405 memcpy (current_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2408 else if (successor->type == FRIEND)
2410 struct FriendInfo *target_friend;
2411 target_friend = (struct FriendInfo *)successor->data;
2412 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
2413 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2414 return current_destination;
2416 else if (successor->type == FINGER)
2418 struct GNUNET_PeerIdentity *next_hop;
2419 struct FingerInfo *finger;
2420 finger = successor->data;
2421 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2423 if (finger->first_trail_length > 0)
2425 struct TrailPeerList *iterator;
2426 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2427 iterator = finger->first_trail_head;
2428 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2430 else /* This means finger is our friend. */
2431 memcpy (next_hop, &(finger->finger_identity), sizeof(struct GNUNET_PeerIdentity));
2433 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
2434 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2445 /** FIXME: by default I keep current_source, and destination as my own id.
2446 * in case we find a finger then we update current_source in the
2447 * find_successor message.
2448 * Construct a Put message and send it to target_peer.
2449 * @param key Key for the content
2450 * @param data Content to store
2451 * @param data_size Size of content @a data in bytes
2452 * @param block_type Type of the block
2453 * @param options Routing options
2454 * @param desired_replication_level Desired replication count
2455 * @param expiration_time When does the content expire
2456 * @param current_destination
2457 * @param current_source
2458 * @param target_peer Peer to which this message will be forwarded.
2459 * @param hop_count Number of hops traversed so far.
2460 * @param put_path_length Total number of peers in @a put_path
2461 * @param put_path Number of peers traversed so far
2464 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2465 const void *data, size_t data_size,
2466 enum GNUNET_BLOCK_Type block_type,
2467 enum GNUNET_DHT_RouteOption options,
2468 uint32_t desired_replication_level,
2469 struct GNUNET_TIME_Absolute expiration_time,
2470 struct GNUNET_PeerIdentity current_destination,
2471 struct GNUNET_PeerIdentity current_source,
2472 struct GNUNET_PeerIdentity *target_peer,
2474 uint32_t put_path_length,
2475 struct GNUNET_PeerIdentity *put_path)
2477 struct PeerPutMessage *ppm;
2478 struct P2PPendingMessage *pending;
2479 struct FriendInfo *target_friend;
2480 struct GNUNET_PeerIdentity *pp;
2483 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2484 sizeof (struct PeerPutMessage);
2486 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2488 put_path_length = 0;
2489 msize = data_size + sizeof (struct PeerPutMessage);
2492 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2498 /* This is the first call made from clients file. So, we should search for the
2500 if (NULL == target_peer)
2503 struct GNUNET_PeerIdentity *next_hop;
2504 memcpy (&key_value, key, sizeof (uint64_t));
2505 struct GNUNET_PeerIdentity curr_dest;
2506 struct GNUNET_PeerIdentity curr_src;
2507 memcpy (&curr_dest, ¤t_destination, sizeof (struct GNUNET_PeerIdentity));
2508 memcpy (&curr_src, ¤t_source, sizeof (struct GNUNET_PeerIdentity));
2509 next_hop = find_successor (key_value, &curr_dest, &curr_src);
2510 /* FIXME: I am copying back current_destination and current_source. but I am not
2511 sure, if its correct. I am doing so just to remove the code from client file.*/
2512 memcpy (¤t_destination, &curr_dest, sizeof (struct GNUNET_PeerIdentity));
2513 memcpy (¤t_source, &curr_src, sizeof (struct GNUNET_PeerIdentity));
2515 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity,¤t_destination)) /* I am the destination do datacache_put */
2517 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
2518 block_type, data_size, data);
2522 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2525 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2526 pending->timeout = expiration_time;
2527 ppm = (struct PeerPutMessage *) &pending[1];
2528 pending->msg = &ppm->header;
2529 ppm->header.size = htons (msize);
2530 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
2531 ppm->options = htonl (options);
2532 ppm->block_type = htonl (block_type);
2533 ppm->hop_count = htonl (hop_count + 1);
2534 ppm->desired_replication_level = htonl (desired_replication_level);
2535 ppm->put_path_length = htonl (put_path_length);
2536 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2538 ppm->current_destination = current_destination;
2539 ppm->current_source = current_source;
2541 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2542 if (put_path_length != 0)
2544 memcpy (pp, put_path,
2545 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2547 memcpy (&pp[put_path_length], data, data_size);
2548 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2549 target_friend->pending_count++;
2550 process_friend_queue (target_friend);
2555 /** FIXME: by default I keep current_source, and destination as my own id.
2556 * in case we find a finger then we update current_source in the
2557 * find_successor message.
2558 * Construct a Get message and send it to target_peer.
2559 * @param key Key for the content
2560 * @param block_type Type of the block
2561 * @param options Routing options
2562 * @param desired_replication_level Desired replication count
2563 * @param expiration_time When does the content expire
2564 * @param current_destination
2565 * @param current_source
2566 * @param target_peer Peer to which this message will be forwarded.
2567 * @param hop_count Number of hops traversed so far.
2568 * @param put_path_length Total number of peers in @a put_path
2569 * @param put_path Number of peers traversed so far
2572 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2573 enum GNUNET_BLOCK_Type block_type,
2574 enum GNUNET_DHT_RouteOption options,
2575 uint32_t desired_replication_level,
2576 struct GNUNET_PeerIdentity current_destination,
2577 struct GNUNET_PeerIdentity current_source,
2578 struct GNUNET_PeerIdentity *target_peer,
2580 uint32_t get_path_length,
2581 struct GNUNET_PeerIdentity *get_path)
2583 struct PeerGetMessage *pgm;
2584 struct P2PPendingMessage *pending;
2585 struct FriendInfo *target_friend;
2586 struct GNUNET_PeerIdentity *gp;
2589 msize = sizeof (struct PeerGetMessage) +
2590 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2592 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2598 if (NULL == target_peer)
2600 /* This is the first call from client file, we need to search for next_hop*/
2601 struct GNUNET_PeerIdentity *next_hop;
2603 struct GNUNET_PeerIdentity curr_dest;
2604 struct GNUNET_PeerIdentity curr_src;
2605 memcpy (&curr_dest, ¤t_destination, sizeof (struct GNUNET_PeerIdentity));
2606 memcpy (&curr_src, ¤t_source, sizeof (struct GNUNET_PeerIdentity));
2607 memcpy (&key_value, key, sizeof (uint64_t));
2608 // FIXME: endianess of key_value!?
2609 next_hop = find_successor (key_value, &curr_dest, &curr_src);
2610 /* FIXME: Again I am copying back value of current_destination, current_source,
2611 Think of a better solution. */
2612 memcpy (¤t_destination, &curr_dest, sizeof (struct GNUNET_PeerIdentity));
2613 memcpy (¤t_source, &curr_src, sizeof (struct GNUNET_PeerIdentity));
2614 if (NULL == next_hop) /* I am the destination do datacache_put */
2616 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2617 NULL, 0, 1, &my_identity, NULL,&my_identity);
2622 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2626 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2627 pending->importance = 0; /* FIXME */
2628 pgm = (struct PeerGetMessage *) &pending[1];
2629 pending->msg = &pgm->header;
2630 pgm->header.size = htons (msize);
2631 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2632 pgm->get_path_length = htonl (get_path_length);
2634 pgm->current_destination = current_destination;
2635 pgm->current_source = current_source;
2636 pgm->hop_count = htonl (hop_count + 1);
2638 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2639 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2640 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2641 target_friend->pending_count++;
2642 process_friend_queue (target_friend);
2647 * Send the get result to requesting client.
2648 * @param expiration When will this result expire?
2649 * @param key Key of the requested data.
2650 * @param put_path_length Number of peers in @a put_path
2651 * @param put_path Path taken to put the data at its stored location.
2652 * @param type Block type
2653 * @param data_size Size of the @a data
2654 * @param data Payload to store
2655 * @param get_path Path taken to reach to the location of the key.
2656 * @param get_path_length Number of peers in @a get_path
2657 * @param next_hop Next peer to forward the message to.
2658 * @param source_peer Peer which has the data for the key.
2661 GDS_NEIGHBOURS_send_get_result (struct GNUNET_TIME_Absolute expiration,
2662 const struct GNUNET_HashCode *key,
2663 unsigned int put_path_length,
2664 const struct GNUNET_PeerIdentity *put_path,
2665 enum GNUNET_BLOCK_Type type, size_t data_size,
2667 struct GNUNET_PeerIdentity *get_path,
2668 unsigned int get_path_length,
2669 struct GNUNET_PeerIdentity *next_hop,
2670 struct GNUNET_PeerIdentity *source_peer)
2672 struct PeerGetResultMessage *get_result;
2673 struct GNUNET_PeerIdentity *get_result_path;
2674 struct GNUNET_PeerIdentity *pp;
2675 struct P2PPendingMessage *pending;
2676 struct FriendInfo *target_friend;
2677 int current_path_index;
2680 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2681 sizeof (struct PeerPutMessage);
2683 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2689 current_path_index = search_my_index(get_path, get_path_length);
2690 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
2691 if (0 == current_path_index)
2693 GDS_CLIENTS_handle_reply (expiration, key, get_path_length, get_path, put_path_length,
2694 put_path, type, data_size, data);
2697 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2698 pending->importance = 0;
2699 get_result = (struct PeerGetResultMessage *)&pending[1];
2700 pending->msg = &get_result->header;
2701 get_result->header.size = htons (msize);
2702 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2703 get_result->key = *key;
2704 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2705 get_result->expiration_time = expiration;
2707 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2708 memcpy (get_result_path, get_path,
2709 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2710 memcpy (&get_result_path[get_path_length], data, data_size);
2711 /* FIXME: Is this correct? */
2712 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2713 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2715 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2716 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2717 target_friend->pending_count++;
2718 process_friend_queue (target_friend);
2723 * Send trail rejection message to the peer which sent me a trail setup message.
2724 * @param source_peer Source peer which wants to set up the trail.
2725 * @param finger_identity Value whose successor will be the finger of @a source_peer.
2726 * @param congested_peer Peer which has send trail rejection message.
2727 * @param next_hop Peer to which this message should be forwarded.
2728 * @param finger_map_index Index in @a source_peer finger peermap.
2729 * @param trail_peer_list Trail followed to reach from @a source_peer to next_hop,
2730 * NULL, in case the @a congested_peer was the first peer
2731 * to which trail setup message was forwarded.
2732 * @param trail_length Number of peers in trail_peer_list.
2735 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity *source_peer,
2736 uint64_t finger_identity,
2737 struct GNUNET_PeerIdentity *congested_peer,
2738 const struct GNUNET_PeerIdentity *next_hop,
2739 unsigned int finger_map_index,
2740 struct GNUNET_PeerIdentity *trail_peer_list,
2741 unsigned int trail_length)
2743 struct PeerTrailRejectionMessage *trail_rejection;
2744 struct GNUNET_PeerIdentity *trail_list;
2745 struct P2PPendingMessage *pending;
2746 struct FriendInfo *target_friend;
2749 msize = trail_length * sizeof(struct GNUNET_PeerIdentity) +
2750 sizeof (struct PeerTrailRejectionMessage);
2752 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2758 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2759 pending->importance = 0;
2760 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2761 trail_rejection = (struct PeerTrailRejectionMessage *) &pending[1];
2762 pending->msg = &trail_rejection->header;
2763 trail_rejection->header.size = htons (msize);
2764 trail_rejection->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
2765 memcpy (&(trail_rejection->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2766 memcpy (&(trail_rejection->congested_peer), congested_peer, sizeof (struct GNUNET_PeerIdentity));
2767 memcpy (&(trail_rejection->finger_identity_value), &finger_identity, sizeof (uint64_t));
2768 trail_rejection->finger_map_index = htonl(finger_map_index);
2769 trail_rejection->trail_length = htonl (trail_length);
2771 if (trail_length != 0)
2773 trail_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2774 memcpy (trail_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2777 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2778 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2779 target_friend->pending_count++;
2780 process_friend_queue (target_friend);
2785 * Core handler for P2P put messages.
2786 * @param cls closure
2787 * @param peer sender of the request
2788 * @param message message
2789 * @return #GNUNET_OK to keep the connection open,
2790 * #GNUNET_SYSERR to close it (signal serious error)
2793 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2794 const struct GNUNET_MessageHeader *message)
2796 struct PeerPutMessage *put;
2797 struct GNUNET_PeerIdentity *put_path;
2798 struct GNUNET_HashCode test_key;
2799 enum GNUNET_DHT_RouteOption options;
2800 struct GNUNET_PeerIdentity current_destination;
2801 struct GNUNET_PeerIdentity current_source;
2802 struct GNUNET_PeerIdentity *next_hop;
2806 size_t payload_size;
2809 msize = ntohs (message->size);
2810 if (msize < sizeof (struct PeerPutMessage))
2812 GNUNET_break_op (0);
2816 put = (struct PeerPutMessage *) message;
2817 putlen = ntohl (put->put_path_length);
2820 sizeof (struct PeerPutMessage) +
2821 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2823 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2825 GNUNET_break_op (0);
2829 current_destination = put->current_destination;
2830 current_source = put->current_source;
2831 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2832 payload = &put_path[putlen];
2833 options = ntohl (put->options);
2834 payload_size = msize - (sizeof (struct PeerPutMessage) +
2835 putlen * sizeof (struct GNUNET_PeerIdentity));
2837 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
2838 payload, payload_size, &test_key))
2841 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
2843 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
2844 GNUNET_break_op (0);
2845 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2846 "PUT with key `%s' for block with key %s\n",
2847 put_s, GNUNET_h2s_full (&test_key));
2848 GNUNET_free (put_s);
2853 GNUNET_break_op (0);
2856 /* cannot verify, good luck */
2860 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
2862 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
2863 ntohl (put->block_type),
2865 NULL, 0, /* bloom filer */
2866 NULL, 0, /* xquery */
2867 payload, payload_size))
2869 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2870 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2873 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2874 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2875 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
2876 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2877 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2878 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2880 GNUNET_break_op (0);
2885 struct GNUNET_PeerIdentity pp[putlen + 1];
2886 /* extend 'put path' by sender */
2887 /* FIXME: Check what are we doing here? */
2888 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
2890 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
2897 memcpy (&key_value, &(put->key), sizeof (uint64_t));
2898 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2900 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2901 if (next_hop == NULL)
2903 /* refer to handle_dht_p2p_trail_setup. */
2908 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2911 if (NULL == next_hop) /* I am the final destination */
2913 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
2914 &(put->key),putlen, pp, ntohl (put->block_type),
2915 payload_size, payload);
2920 GDS_CLIENTS_process_put (options,
2921 ntohl (put->block_type),
2922 ntohl (put->hop_count),
2923 ntohl (put->desired_replication_level),
2925 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2930 GDS_NEIGHBOURS_send_put (&put->key, payload, payload_size,
2931 ntohl (put->block_type),ntohl (put->options),
2932 ntohl (put->desired_replication_level),
2933 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2934 current_destination, current_source, next_hop,
2935 ntohl (put->hop_count), putlen, pp);
2939 return GNUNET_SYSERR;
2944 * Core handler for p2p get requests.
2946 * @param cls closure
2947 * @param peer sender of the request
2948 * @param message message
2949 * @return #GNUNET_OK to keep the connection open,
2950 * #GNUNET_SYSERR to close it (signal serious error)
2953 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2954 const struct GNUNET_MessageHeader *message)
2956 struct PeerGetMessage *get;
2957 struct GNUNET_PeerIdentity *get_path;
2958 struct GNUNET_PeerIdentity current_destination;
2959 struct GNUNET_PeerIdentity current_source;
2960 struct GNUNET_PeerIdentity *next_hop;
2961 uint32_t get_length;
2965 msize = ntohs (message->size);
2966 if (msize < sizeof (struct PeerGetMessage))
2968 GNUNET_break_op (0);
2972 get = (struct PeerGetMessage *)message;
2973 get_length = ntohl (get->get_path_length);
2974 get_path = (struct GNUNET_PeerIdentity *)&get[1];
2975 current_destination = get->current_destination;
2976 current_source = get->current_source;
2979 sizeof (struct PeerGetMessage) +
2980 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
2982 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2984 GNUNET_break_op (0);
2987 /* Add sender to get path */
2988 struct GNUNET_PeerIdentity gp[get_length + 1];
2989 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
2990 gp[get_length + 1] = *peer;
2991 get_length = get_length + 1;
2993 memcpy (&key_value, &(get->key), sizeof (uint64_t));
2994 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2996 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2997 if (next_hop == NULL)
2999 /* refer to handle_dht_p2p_trail_setup. */
3004 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
3007 if (NULL == next_hop)
3009 /* FIXME: Try to make this code also short and remove useless variables. */
3010 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3011 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3012 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3013 get_length = get_length + 1;
3014 struct GNUNET_PeerIdentity *next_hop;
3015 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3016 memcpy (next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
3017 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3018 get_length, final_get_path,next_hop, &my_identity);
3024 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3025 get->desired_replication_level,current_destination,
3026 current_source, next_hop, 0,
3029 return GNUNET_SYSERR;
3035 * FIXME: In case of trail, we don't have source and destination part of the trail,
3036 * Check if we follow the same in case of get/put/get_result. Also, in case of
3037 * put should we do a routing table add.
3038 * Core handler for get result
3039 * @param cls closure
3040 * @param peer sender of the request
3041 * @param message message
3042 * @return #GNUNET_OK to keep the connection open,
3043 * #GNUNET_SYSERR to close it (signal serious error)
3046 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3047 const struct GNUNET_MessageHeader *message)
3049 struct PeerGetResultMessage *get_result;
3050 struct GNUNET_PeerIdentity *get_path;
3051 struct GNUNET_PeerIdentity *put_path;
3053 size_t payload_size;
3055 unsigned int getlen;
3056 unsigned int putlen;
3057 int current_path_index;
3059 msize = ntohs (message->size);
3060 if (msize < sizeof (struct PeerGetResultMessage))
3062 GNUNET_break_op (0);
3066 get_result = (struct PeerGetResultMessage *)message;
3067 getlen = ntohl (get_result->get_path_length);
3068 putlen = ntohl (get_result->put_path_length);
3071 sizeof (struct PeerGetResultMessage) +
3072 getlen * sizeof (struct GNUNET_PeerIdentity) +
3073 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3075 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3077 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3079 GNUNET_break_op (0);
3083 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
3084 payload = &get_path[getlen];
3085 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3086 getlen * sizeof (struct GNUNET_PeerIdentity));
3087 /* FIXME: Check if its correct or not. */
3090 put_path = &get_path[1];
3094 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3096 //GDS_CLIENTS_process_get_result();
3097 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3098 getlen, get_path, putlen,
3099 put_path, get_result->type, payload_size, payload);
3104 struct GNUNET_PeerIdentity *next_hop;
3105 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3106 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3107 current_path_index = search_my_index (get_path, getlen);
3108 /* FIXME: First check if you are adding yourself to the get path or not.
3109 if yes then don't check if current_path_index == 0, if not then check
3110 and next_hop == source_peer. */
3111 memcpy (next_hop, &get_path[current_path_index - 1], sizeof (struct GNUNET_PeerIdentity));
3113 GDS_NEIGHBOURS_send_get_result (get_result->expiration_time, &(get_result->key),
3115 get_result->type, payload_size,payload,
3117 next_hop, &(get_result->source_peer));
3120 return GNUNET_SYSERR;
3125 * FIXME: Is all trails threshold and routing table has some link.
3126 * Core handle for PeerTrailSetupMessage.
3127 * @param cls closure
3128 * @param message message
3129 * @param peer peer identity this notification is about
3130 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3133 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3134 const struct GNUNET_MessageHeader *message)
3136 const struct PeerTrailSetupMessage *trail_setup;
3137 struct GNUNET_PeerIdentity current_destination;
3138 struct GNUNET_PeerIdentity current_source;
3139 struct GNUNET_PeerIdentity source;
3140 struct GNUNET_PeerIdentity *next_hop;
3141 struct GNUNET_PeerIdentity next_peer;
3142 struct GNUNET_PeerIdentity *trail_peer_list;
3143 struct FriendInfo *target_friend;
3144 uint64_t destination_finger_value;
3145 uint32_t trail_length;
3146 uint32_t finger_map_index;
3149 msize = ntohs (message->size);
3150 if (msize < sizeof (struct PeerTrailSetupMessage))
3152 GNUNET_break_op (0);
3156 trail_setup = (const struct PeerTrailSetupMessage *) message;
3157 trail_length = ntohl (trail_setup->trail_length);
3159 if ((msize < sizeof (struct PeerTrailSetupMessage) +
3160 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3162 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3164 GNUNET_break_op (0);
3168 if (trail_length > 0)
3169 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
3170 memcpy (¤t_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity));
3171 memcpy (¤t_source,&(trail_setup->current_source), sizeof (struct GNUNET_PeerIdentity));
3172 memcpy (&source, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity));
3173 finger_map_index = ntohl (trail_setup->finger_map_index);
3174 destination_finger_value = ntohl (trail_setup->destination_finger);
3176 /* Trail setup request looped back to me. */
3177 if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
3179 finger_table_add (&my_identity, NULL, 0, finger_map_index);
3184 /* FIXME: Here we need to check 3 things
3185 * 1. if my routing table is all full
3186 * 2. if all my friends are congested
3187 * 3. if trail threshold of my friends have crossed.
3188 * In all these cases we need to send back trail rejection message. */
3189 if ( (GNUNET_YES == all_friends_trail_threshold)
3190 || (GNUNET_YES == GDS_ROUTING_check_threshold()))
3192 /* If all the friends have reached their trail threshold or if there is no
3193 more space in routing table to store more trails, then reject. */
3194 GDS_NEIGHBOURS_send_trail_rejection (&source, destination_finger_value, &my_identity,
3195 peer,finger_map_index, trail_peer_list,trail_length);
3200 /* Check if you are current_destination or not. */
3201 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3203 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3204 /* OPTIMIZATION: Choose a peer from find_successor and choose the closest one.
3205 In case the closest one is from routing table and it is NULL, then update
3207 if (next_hop == NULL)
3209 /* FIXME: Should we inform the peer before us. If not then it may continue
3210 to send us request. But in case we want to inform we need to have a
3211 different kind of message. */
3212 GNUNET_STATISTICS_update (GDS_stats,
3213 gettext_noop ("# Trail not found in routing table during"
3214 "trail setup request, packet dropped."),
3221 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
3223 if (NULL == next_hop)
3224 return GNUNET_SYSERR;
3226 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity))) /* This means I am the final destination */
3228 if (trail_length == 0)
3230 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
3234 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3237 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3239 /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */
3240 if (PREDECESSOR_FINGER_ID != finger_map_index)
3242 /* FIXME: Is this correct assumption? A peer which think I am its predecessor,
3243 then I am not its predecessor. */
3244 compare_and_update_predecessor (&source, trail_peer_list, trail_length );
3247 GDS_NEIGHBOURS_send_trail_setup_result (&source,
3249 target_friend, trail_length,
3256 /* Now add yourself to the trail. */
3257 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3258 if (trail_length != 0)
3259 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3260 peer_list[trail_length] = my_identity;
3263 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3264 GDS_NEIGHBOURS_send_trail_setup (&source,
3265 destination_finger_value,
3266 ¤t_destination, ¤t_source,
3267 target_friend, trail_length, peer_list,
3274 * Core handle for p2p trail construction result messages.
3276 * @param message message
3277 * @param peer peer identity this notification is about
3278 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3281 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3282 const struct GNUNET_MessageHeader *message)
3284 const struct PeerTrailSetupResultMessage *trail_result;
3285 struct GNUNET_PeerIdentity *trail_peer_list;
3286 uint32_t trail_length;
3287 uint32_t finger_map_index;
3290 msize = ntohs (message->size);
3291 if (msize < sizeof (struct PeerTrailSetupResultMessage))
3293 GNUNET_break_op (0);
3297 trail_result = (const struct PeerTrailSetupResultMessage *) message;
3298 trail_length = ntohl (trail_result->trail_length);
3301 sizeof (struct PeerTrailSetupResultMessage) +
3302 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3304 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3306 GNUNET_break_op (0);
3310 finger_map_index = htonl (trail_result->finger_map_index);
3311 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
3313 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3316 /* FIXME: Is it important to check here if source and my identity is same or not.
3317 we are already checking it in handle_dht_p2p_trail_setup. And if we got that
3318 message then we will not get it here. */
3319 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
3325 struct GNUNET_PeerIdentity next_hop;
3326 struct FriendInfo *target_friend;
3329 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3330 /* FIXME: Make sure you are passing the current length */
3331 my_index = search_my_index (trail_peer_list, trail_length);
3334 next_hop = trail_result->destination_peer;
3337 next_hop = trail_peer_list[my_index - 1];
3339 /* Finger table of destination peer will not contain any trail for the case
3340 * where destination peer is its own finger identity. */
3341 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3342 &(trail_result->finger_identity))))
3344 GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
3348 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3349 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
3350 &(trail_result->finger_identity),
3351 target_friend, trail_length,
3356 return GNUNET_SYSERR;
3361 * Get my current predecessor from the finger peer map
3362 * @return Current predecessor.
3364 static struct FingerInfo *
3367 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
3368 struct GNUNET_PeerIdentity key_ret;
3369 unsigned int finger_index;
3370 struct FingerInfo *my_predecessor;
3373 /* Iterate over finger peer map and extract your predecessor. */
3374 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
3375 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
3377 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
3378 (finger_iter,&key_ret,(const void **)&my_predecessor))
3380 if(PREDECESSOR_FINGER_ID == my_predecessor->finger_map_index)
3387 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
3392 return my_predecessor;
3397 * Core handle for p2p verify successor messages.
3398 * @param cls closure
3399 * @param message message
3400 * @param peer peer identity this notification is about
3401 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3404 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3405 const struct GNUNET_MessageHeader *message)
3407 const struct PeerVerifySuccessorMessage *vsm;
3408 const struct GNUNET_PeerIdentity *trail_peer_list;
3409 struct GNUNET_PeerIdentity source_peer;
3410 struct GNUNET_PeerIdentity next_hop;
3411 struct FriendInfo *target_friend;
3413 uint32_t trail_length;
3415 msize = ntohs (message->size);
3416 if (msize < sizeof (struct PeerVerifySuccessorMessage))
3418 GNUNET_break_op (0);
3422 vsm = (struct PeerVerifySuccessorMessage *) message;
3423 trail_length = ntohl (vsm->trail_length);
3425 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
3426 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3427 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3429 GNUNET_break_op (0);
3432 trail_peer_list = (const struct GNUNET_PeerIdentity *)&vsm[1];
3433 memcpy (&source_peer, &(vsm->source_peer), sizeof(struct GNUNET_PeerIdentity));
3435 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
3437 struct FingerInfo *my_predecessor;
3438 if (trail_length == 0)
3440 /* SUPU: If I am friend of source_peer, then trail_length == 0. */
3441 memcpy (&next_hop, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3445 /* SUPU: Here I am the final destination successor, and trail does not contain
3446 destination. So, the next hop is the last element in the trail. */
3447 memcpy (&next_hop, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3449 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3451 my_predecessor = get_predecessor();
3452 if (NULL == my_predecessor)
3455 return GNUNET_SYSERR;
3458 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3459 &(my_predecessor->finger_identity))))
3461 /* Source peer and my predecessor, both are same. */
3462 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3464 &(my_predecessor->finger_identity),
3471 struct GNUNET_PeerIdentity *new_successor_trail;
3472 struct TrailPeerList *iterator;
3473 int new_trail_length;
3476 new_trail_length = trail_length + my_predecessor->first_trail_length + 1;
3477 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
3478 if (trail_length > 0)
3479 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
3481 memcpy (&new_successor_trail[trail_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3483 if (my_predecessor->first_trail_length)
3485 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
3486 iterator = my_predecessor->first_trail_head;
3487 i = trail_length + 1;
3488 while (i < new_trail_length)
3490 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
3491 iterator = iterator->next;
3496 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3498 &(my_predecessor->finger_identity),
3500 new_successor_trail,
3509 my_index = search_my_index (trail_peer_list, trail_length);
3510 if (my_index == GNUNET_SYSERR)
3513 return GNUNET_SYSERR;
3515 if (my_index == (trail_length - 1))
3517 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(vsm->successor));
3521 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3522 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3524 GDS_NEIGHBOURS_send_verify_successor (&(vsm->source_peer), &(vsm->successor),target_friend,
3525 trail_peer_list, trail_length);
3527 return GNUNET_SYSERR;
3532 * Core handle for p2p verify successor result messages.
3533 * @param cls closure
3534 * @param message message
3535 * @param peer peer identity this notification is about
3536 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3539 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3540 const struct GNUNET_MessageHeader *message)
3542 const struct PeerVerifySuccessorResultMessage *vsrm;
3543 struct GNUNET_PeerIdentity *trail_peer_list;
3544 struct GNUNET_PeerIdentity next_hop;
3545 struct FriendInfo *target_friend;
3547 uint32_t trail_length;
3549 msize = ntohs (message->size);
3550 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
3552 GNUNET_break_op (0);
3555 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
3556 trail_length = ntohl (vsrm->trail_length);
3559 sizeof (struct PeerVerifySuccessorResultMessage) +
3560 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3562 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3564 GNUNET_break_op (0);
3567 /* FIXME: URGENT: What happens when trail length = 0. */
3569 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
3571 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity))))
3573 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
3575 /* FIXME: Here we have got a new successor. But it may happen that our logic
3576 * says that this is not correct successor. so in finger table add it
3577 * failed to update the successor and we are still sending a notify
3578 * new successor. Here trail_length will be atleast 1, in case we have a new
3579 * successor because in that case our old successor is part of trail.
3580 * Could it be possible that our identity and my_predecessor is same. Check it. */
3581 if (GNUNET_YES == finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0))
3583 memcpy (&next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
3584 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3585 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
3586 target_friend, trail_peer_list,
3594 return GNUNET_SYSERR;
3602 my_index = search_my_index (trail_peer_list, trail_length);
3603 if (GNUNET_SYSERR == my_index)
3606 return GNUNET_SYSERR;
3611 /* Source is not part of trail, so if I am the last one then my index
3613 memcpy (&next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3617 memcpy (&next_hop, &trail_peer_list[my_index-1], sizeof (struct GNUNET_PeerIdentity));
3620 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3621 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
3622 &(vsrm->source_successor),
3623 &(vsrm->my_predecessor),
3629 return GNUNET_SYSERR;
3634 * Core handle for p2p notify new successor messages.
3635 * @param cls closure
3636 * @param message message
3637 * @param peer peer identity this notification is about
3638 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3641 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3642 const struct GNUNET_MessageHeader *message)
3644 const struct PeerNotifyNewSuccessorMessage *nsm;
3645 struct GNUNET_PeerIdentity *trail_peer_list;
3647 uint32_t trail_length;
3649 msize = ntohs (message->size);
3650 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
3652 GNUNET_break_op (0);
3655 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
3656 trail_length = ntohl (nsm->trail_length);
3658 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3659 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3661 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3663 GNUNET_break_op (0);
3667 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
3669 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), &my_identity)))
3671 /* I am the new successor. */
3672 struct GNUNET_PeerIdentity new_predecessor;
3673 memcpy (&new_predecessor, &(nsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
3674 if (GNUNET_NO == compare_and_update_predecessor (&new_predecessor, trail_peer_list,
3677 /* Someone claims to be my predecessor but its not closest predecessor
3680 return GNUNET_SYSERR;
3686 struct FriendInfo *target_friend;
3687 struct GNUNET_PeerIdentity next_hop;
3690 my_index = search_my_index (trail_peer_list, trail_length);
3691 if (GNUNET_SYSERR == my_index)
3694 return GNUNET_SYSERR;
3697 if (my_index == (trail_length - 1))
3699 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(nsm->destination_peer));
3703 memcpy (&next_hop, &trail_peer_list[my_index+1], sizeof (struct GNUNET_PeerIdentity));
3704 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3706 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
3707 &(nsm->destination_peer),
3708 target_friend, trail_peer_list,
3712 return GNUNET_SYSERR;
3717 * FIXME; Should we call select_random_friend from here in case I am the source
3718 * of the message or should I just return and in next iteration by default
3719 * we will call select random friend from send_find_finger_trail. But in that
3720 * case we should maintain a list of congested peer which failed to setup the
3721 * trail. and then in select random friend we should ignore them. this list
3722 * should have an expiration time and we should garbage collect it periodically.
3723 * Core handler for P2P trail rejection message
3724 * @param cls closure
3725 * @param message message
3726 * @param peer peer identity this notification is about
3727 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3730 int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3731 const struct GNUNET_MessageHeader *message)
3733 /* Here you have recevied the message it means that the peer next to you have
3734 failed to setup the trail to the finger identity value. now you should call
3735 find_successor and make sure that you don't choose the peer as next hop
3736 in order to do so, you need to pass a new parameter to find successor,
3737 congested peer - a peer which you should ignore. once you have found this
3738 peer then just send a trail setup message to that peer. In case you are
3739 also congested then remove yourself from the trail as this message
3740 reached to as you are part of the trail. and then send the message to
3741 element before you. Ideally you should be the last element in the trail as
3742 all the the elements before you have rejected you. In case you are source,
3743 then you should call select_random_Friend(congested_peer). in case you don't
3744 find any peer because congested peer then set flag that all friends are busy
3746 const struct PeerTrailRejectionMessage *trail_rejection;
3747 struct GNUNET_PeerIdentity *trail_peer_list;
3748 struct GNUNET_PeerIdentity source_peer;
3749 struct GNUNET_PeerIdentity congested_peer;
3750 struct FriendInfo *target_friend;
3751 struct GNUNET_PeerIdentity next_peer;
3752 struct GNUNET_PeerIdentity *next_hop;
3753 struct GNUNET_PeerIdentity current_source;
3754 struct GNUNET_PeerIdentity current_destination;
3756 uint32_t trail_length;
3757 uint32_t finger_map_index;
3758 uint64_t destination_finger_value;
3760 msize = ntohs (message->size);
3761 if (msize < sizeof (struct PeerTrailRejectionMessage))
3763 GNUNET_break_op (0);
3767 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3768 trail_length = ntohl (trail_rejection->trail_length);
3770 if ((msize < sizeof (struct PeerTrailRejectionMessage) +
3771 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3773 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3775 GNUNET_break_op (0);
3779 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3780 finger_map_index = ntohl (trail_rejection->finger_map_index);
3781 memcpy (&source_peer, &(trail_rejection->source_peer), sizeof(struct GNUNET_PeerIdentity));
3782 memcpy (&destination_finger_value, &(trail_rejection->finger_identity_value), sizeof (uint64_t));
3783 memcpy (&congested_peer, &(trail_rejection->congested_peer), sizeof (struct GNUNET_PeerIdentity));
3785 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source_peer)))
3787 /* I am the source of original trail setup message. Do nothing and exit. */
3788 /* In current implementation, when we don't get the result of a trail setup,
3789 then no entry is added to finger table and hence, by default a trail setup for
3790 the same finger map index is sent. so we don't need to send it here. */
3794 if(GDS_ROUTING_check_threshold())
3796 /* My routing state size has crossed the threshold, I can not be part of any more
3798 struct GNUNET_PeerIdentity *new_trail;
3800 if (trail_length == 1)
3802 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3806 /* FIXME: Here if I got the trail rejection message then I am the last element
3807 in the trail. So, I should choose trail_length-2.*/
3808 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
3811 /* Remove myself from the trail. */
3812 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3813 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3815 /* No more trails possible through me. send a trail rejection message to next hop. */
3816 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
3817 &next_peer,finger_map_index, new_trail,trail_length - 1);
3821 memcpy (¤t_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
3822 memcpy (¤t_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
3823 /* FIXME: After adding a new field in struct FriendInfo congested, then call
3824 find successor then it will never consider that friend by default. */
3825 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
3827 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, ¤t_destination))) /* This means I am the final destination */
3829 if (trail_length == 1)
3831 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3835 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3838 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3839 compare_and_update_predecessor (&source_peer, trail_peer_list, trail_length);
3841 GDS_NEIGHBOURS_send_trail_setup_result (&source_peer,
3843 target_friend, trail_length,
3848 else if (NULL == next_hop)
3850 /* No peer found. Send a trail rejection message to previous peer in the trail. */
3852 struct GNUNET_PeerIdentity *new_trail;
3854 if (trail_length == 1)
3856 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3860 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
3863 /* Remove myself from the trail. */
3864 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3865 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3867 /* No more trails possible through me. send a trail rejection message to next hop. */
3868 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
3869 &next_peer,finger_map_index, new_trail,trail_length - 1);
3874 /* Now add yourself to the trail. */
3875 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3876 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3877 peer_list[trail_length] = my_identity;
3880 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3881 GDS_NEIGHBOURS_send_trail_setup (&source_peer,
3882 destination_finger_value,
3883 ¤t_destination, ¤t_source,
3884 target_friend, trail_length, peer_list,
3888 return GNUNET_SYSERR;
3893 * FIXME: we don't send trail teardown to finger for which the trail was setup.
3894 * Trail teardown only aim is to remove entries from the routing table. Destination
3895 * finger does not have any entry in its routing table. So, it does not need
3897 * Core handle for p2p trail tear down messages.
3898 * @param cls closure
3899 * @param message message
3900 * @param peer peer identity this notification is about
3901 * @return GNUNET_OK on success, GNUNET_SYSERR on error
3904 int handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
3905 const struct GNUNET_MessageHeader *message)
3907 struct PeerTrailTearDownMessage *trail_teardown;
3908 struct GNUNET_PeerIdentity *trail_peer_list;
3909 struct GNUNET_PeerIdentity next_hop;
3910 struct FriendInfo *target_friend;
3911 uint32_t trail_length;
3915 msize = ntohs (message->size);
3916 if (msize < sizeof (struct PeerTrailTearDownMessage))
3918 GNUNET_break_op (0);
3922 trail_teardown = (struct PeerTrailTearDownMessage *) message;
3923 trail_length = ntohl (trail_teardown->trail_length);
3925 if ((msize < sizeof (struct PeerTrailTearDownMessage) +
3926 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3928 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3930 GNUNET_break_op (0);
3934 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_teardown[1];
3936 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer), &my_identity)))
3938 /* I am the destination of the trail, but I am not part of trail. I don't
3939 need to remove any entry from my routing table. So, I should not get this
3945 my_index = search_my_index (trail_peer_list, trail_length);
3946 if(GNUNET_SYSERR == my_index)
3947 return GNUNET_SYSERR;
3949 if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
3950 &(trail_teardown->destination_peer),peer))
3952 /* Here we get GNUNET_NO, only if there is no matching entry found in routing
3958 /* I am the last element of the trail. */
3959 if(my_index == trail_length - 1)
3962 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3963 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3965 GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer),
3966 &(trail_teardown->destination_peer),
3967 trail_peer_list, trail_length, target_friend);
3972 * Iterate over finger_peermap, and remove entries with peer as the first element
3974 * @param cls closure
3975 * @param key current public key
3976 * @param value value in the hash map
3977 * @return #GNUNET_YES if we should continue to
3979 * #GNUNET_NO if not.
3982 remove_matching_finger (void *cls,
3983 const struct GNUNET_PeerIdentity *key,
3986 struct FingerInfo *remove_finger = value;
3987 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
3989 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->first_trail_head->peer, disconnected_peer)
3990 || (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_finger->finger_identity), disconnected_peer)))
3992 GNUNET_assert (GNUNET_YES ==
3993 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
3996 free_finger (remove_finger);
4004 * Method called whenever a peer disconnects.
4006 * @param cls closure
4007 * @param peer peer identity this notification is about
4010 handle_core_disconnect (void *cls,
4011 const struct GNUNET_PeerIdentity *peer)
4013 struct FriendInfo *remove_friend;
4015 /* Check for self message. */
4016 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
4019 /* Search for peer to remove in your friend_peermap. */
4021 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4023 if (NULL == remove_friend)
4029 /* Remove fingers for which this peer is the first element in the trail or if
4030 * the friend is a finger. */
4031 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap,
4032 &remove_matching_finger, (void *)peer);
4034 /* Remove routing trails of which this peer is a part.
4035 * FIXME: Here do we only remove the entry from our own routing table
4036 * or do we also inform other peers which are part of trail. It seems to be
4037 * too much of messages exchanged. */
4038 GDS_ROUTING_remove_entry (peer);
4040 /* Remove the peer from friend_peermap. */
4041 GNUNET_assert (GNUNET_YES ==
4042 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
4046 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
4049 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4051 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4052 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4057 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
4059 GNUNET_SCHEDULER_cancel (verify_successor);
4060 verify_successor = GNUNET_SCHEDULER_NO_TASK;
4066 * Method called whenever a peer connects.
4068 * @param cls closure
4069 * @param peer_identity peer identity this notification is about
4072 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
4074 struct FriendInfo *friend;
4076 /* Check for connect to self message */
4077 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
4080 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
4082 /* If peer already exists in our friend_peermap, then exit. */
4083 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
4089 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
4092 friend = GNUNET_new (struct FriendInfo);
4093 friend->id = *peer_identity;
4094 friend->trails_count = 0;
4096 GNUNET_assert (GNUNET_OK ==
4097 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
4098 peer_identity, friend,
4099 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
4101 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
4102 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
4103 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
4108 * To be called on core init/fail.
4110 * @param cls service closure
4111 * @param identity the public identity of this peer
4114 core_init (void *cls,
4115 const struct GNUNET_PeerIdentity *identity)
4117 my_identity = *identity;
4119 FPRINTF (stderr,_("\nSUPU %s, %s, %d, my_identity = %s"),
4120 __FILE__, __func__,__LINE__, GNUNET_i2s(&my_identity));
4125 * Initialize neighbours subsystem.
4126 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4129 GDS_NEIGHBOURS_init (void)
4131 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
4132 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
4133 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
4134 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
4135 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
4136 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
4137 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
4138 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
4139 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
4140 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
4141 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
4146 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
4147 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
4148 GNUNET_NO, core_handlers);
4149 if (NULL == core_api)
4150 return GNUNET_SYSERR;
4152 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
4153 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS * 4/3, GNUNET_NO);
4154 all_friends_trail_threshold = GNUNET_NO;
4161 * Shutdown neighbours subsystem.
4164 GDS_NEIGHBOURS_done (void)
4166 if (NULL == core_api)
4169 GNUNET_CORE_disconnect (core_api);
4172 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
4173 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
4174 friend_peermap = NULL;
4176 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
4177 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
4178 finger_peermap = NULL;
4180 /* FIXME: Here I have added GNUNET_break(0) as ideally if friend_peermap
4181 is already zero, then we really don't need to cancel it again. If this
4182 condition happens it mean we might have missed some corner case. But we
4183 cancel the task only in handle_core_disconnect. it may happen that this
4184 function is called but not handle_core_disconnect, In that case GNUNET_break(0)
4186 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4189 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4190 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4193 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
4196 GNUNET_SCHEDULER_cancel (verify_successor);
4197 verify_successor = GNUNET_SCHEDULER_NO_TASK;
4204 * FIXME: Here I want to send only the value not the address. Initially
4205 * I wanted to make it const struct * so that no other function can change it.
4206 * then in client file, i make a copy and send that copy. now I have made this
4210 * @return my identity
4212 struct GNUNET_PeerIdentity
4213 GDS_NEIGHBOURS_get_my_id (void)
4219 /* end of gnunet-service-xdht_neighbours.c */