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. Structure alignment.
51 3. In put, we don't have anything like put result. so we are not adding anything
53 4. Maintain a list of trails --> struct Trail *all_trails_head
54 * struct Trail *all_trails_tail. How do I keep it as an array and not as a list??
55 * First will complete the logic everywhere and then make this change.
56 5. At some places you use memcpy and at some places =, use uniformly.
57 6. I have removed compare_and_update_predecessor from handle_dht_p2p_Trail_setup
58 * (refer to google docs for reason).
62 * Maximum possible fingers of a peer.
64 #define MAX_FINGERS 66
67 * Maximum allowed number of pending messages per friend peer.
69 #define MAXIMUM_PENDING_PER_FRIEND 64
72 * How long to wait before sending another find finger trail request
74 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
77 * How long at most to wait for transmission of a request to another peer?
79 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
82 * Maximum number of trails stored per finger.
84 #define TRAILS_COUNT 2
87 * Used to distinguish put/get request use of find_successor() from others
89 #define PUT_GET_REQUEST 68
91 GNUNET_NETWORK_STRUCT_BEGIN
99 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
101 struct GNUNET_MessageHeader header;
106 uint32_t options GNUNET_PACKED;
111 uint32_t block_type GNUNET_PACKED;
116 uint32_t hop_count GNUNET_PACKED;
119 * Replication level for this message
120 * In the current implementation, this value is not used.
122 uint32_t desired_replication_level GNUNET_PACKED;
125 * Length of the PUT path that follows (if tracked).
127 uint32_t put_path_length GNUNET_PACKED;
130 * Current destination to which this message is forwarded.
132 struct GNUNET_PeerIdentity current_destination;
135 * Peer whose finger is current_destination.
137 struct GNUNET_PeerIdentity current_source;
140 * When does the content expire?
142 struct GNUNET_TIME_AbsoluteNBO expiration_time;
145 * The key to store the value under.
147 struct GNUNET_HashCode key GNUNET_PACKED;
149 /* put path (if tracked) */
159 struct PeerGetResultMessage
162 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
164 struct GNUNET_MessageHeader header;
167 * The type for the data.
169 uint32_t type GNUNET_PACKED;
172 * Peer which will receive the get result message.
174 struct GNUNET_PeerIdentity source_peer;
177 * Number of peers recorded in the outgoing path from source to the
178 * stored location of this message.
180 uint32_t put_path_length GNUNET_PACKED;
183 * Length of the GET path that follows (if tracked).
185 uint32_t get_path_length GNUNET_PACKED;
188 * When does the content expire?
190 struct GNUNET_TIME_Absolute expiration_time;
193 * The key of the corresponding GET request.
195 struct GNUNET_HashCode key;
197 /* put path (if tracked) */
199 /* get path (if tracked) */
209 struct PeerGetMessage
212 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
214 struct GNUNET_MessageHeader header;
219 uint32_t options GNUNET_PACKED;
222 * Desired content type.
224 uint32_t block_type GNUNET_PACKED;
229 uint32_t hop_count GNUNET_PACKED;
232 * Desired replication level for this request.
233 * In the current implementation, this value is not used.
235 uint32_t desired_replication_level GNUNET_PACKED;
238 * Total number of peers in get path.
240 unsigned int get_path_length;
243 * Peer which is an intermediate destination.
245 struct GNUNET_PeerIdentity current_destination;
248 * Source for which current_destination is the finger.
250 struct GNUNET_PeerIdentity current_source;
253 * The key we are looking for.
255 struct GNUNET_HashCode key;
263 * P2P Trail setup message
265 struct PeerTrailSetupMessage
269 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
271 struct GNUNET_MessageHeader header;
274 * Successor of this finger value will be our finger peer.
276 uint64_t destination_finger;
279 * Source peer which wants to setup the trail to one of its finger.
281 struct GNUNET_PeerIdentity source_peer;
284 * Peer to which this packet is forwarded.
286 struct GNUNET_PeerIdentity current_destination;
289 * In case the packet is forwarded to an intermediate finger, then
290 * current_source contains the peer id whose finger is the intermediate
291 * finger. In case the packet is forwarded to a friend, then it is NULL.
292 * FIXME: check the usage of current_source and fix this comment.
294 struct GNUNET_PeerIdentity current_source;
297 * Index into finger peer map, in Network Byte Order.
299 uint32_t finger_map_index;
302 * Number of entries in trail list, in Network Byte Order.
304 uint32_t trail_length GNUNET_PACKED;
306 /* Trail formed in the process. */
311 * P2P Trail Setup Result message
313 struct PeerTrailSetupResultMessage
317 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
319 struct GNUNET_MessageHeader header;
322 * Finger to which we have found the path.
324 struct GNUNET_PeerIdentity finger_identity;
327 * Peer which was looking for the trail to finger.
329 struct GNUNET_PeerIdentity destination_peer;
332 * Index into finger peer map in NBO.
334 uint32_t finger_map_index;
337 * Number of entries in trail list in NBO.
339 uint32_t trail_length GNUNET_PACKED;
341 /* Trail from destination_peer to finger_identity */
347 * P2P Trail Rejection Message.
349 struct PeerTrailRejectionMessage
352 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
354 struct GNUNET_MessageHeader header;
357 * Source peer which wants to set up the trail.
359 struct GNUNET_PeerIdentity source_peer;
362 * Peer which sent trail rejection message.
364 struct GNUNET_PeerIdentity congested_peer;
367 * Peer identity which will be successor to this value will be finger of
370 uint64_t finger_identity_value;
373 * Index in finger peer map of source peer.
375 uint32_t finger_map_index;
378 * Total number of peers in the trail.
380 uint32_t trail_length;
382 /* Trail_list from source_peer to peer which sent the message for trail setup
383 * to congested peer.*/
388 * P2P Verify Successor message.
390 struct PeerVerifySuccessorMessage
394 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
396 struct GNUNET_MessageHeader header;
399 * Source peer which wants to verify its successor.
401 struct GNUNET_PeerIdentity source_peer;
404 * My current successor.
406 struct GNUNET_PeerIdentity successor;
409 * Total number of peers in trail to current successor.
411 uint32_t trail_length;
413 /* Trail to reach to from source_peer to successor. */
418 * P2P Verify Successor Result message.
420 struct PeerVerifySuccessorResultMessage
424 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
426 struct GNUNET_MessageHeader header;
429 * Destination peer which sent the request to verify its successor.
431 struct GNUNET_PeerIdentity destination_peer;
434 * Successor to which PeerVerifySuccessorMessage was sent.
436 struct GNUNET_PeerIdentity source_successor;
439 * source_successor's predecessor
441 struct GNUNET_PeerIdentity my_predecessor;
444 * Total number of peers in trail.
446 uint32_t trail_length;
448 /* Trail to reach from destination_peer to its correct successor.
449 * If source_successor is not destination peer, then trail is from destination_peer
451 * If source_successor is destination peer, then trail is from destination_peer
452 * to source_successor. */
457 * P2P Notify New Successor message.
459 struct PeerNotifyNewSuccessorMessage
462 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
464 struct GNUNET_MessageHeader header;
467 * Source peer which wants to notify its new successor.
469 struct GNUNET_PeerIdentity source_peer;
472 * Old successor of source peer.
474 struct GNUNET_PeerIdentity old_successor;
477 * New successor identity.
479 struct GNUNET_PeerIdentity destination_peer;
482 * Number of peers in trail from source_peer to new successor.
484 uint32_t trail_length;
486 /* Trail to from source_peer to destination_peer. */
489 struct PeerTrailTearDownMessage
492 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
494 struct GNUNET_MessageHeader header;
497 * Source peer of this trail.
499 struct GNUNET_PeerIdentity source_peer;
502 * Destination peer of this trail.
504 struct GNUNET_PeerIdentity destination_peer;
507 * Trail from source_peer to destination_peer compressed such that
508 * new_first_friend is the first hop in the trail from source to
511 struct GNUNET_PeerIdentity new_first_friend;
513 * Number of peers in trail from source_peer to new first friend.
515 uint32_t trail_length;
517 /* Trail from source_peer to new first friend. */
521 struct PeerAddTrailMessage
524 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL
526 struct GNUNET_MessageHeader header;
529 * Source peer of the routing trail.
531 struct GNUNET_PeerIdentity source_peer;
534 * Destination peer of the routing trail.
536 struct GNUNET_PeerIdentity destination_peer;
539 * Total number of peers from source peer to destination peer.
541 unsigned int trail_length;
543 /* Trail from source peer to destination peer. */
547 GNUNET_NETWORK_STRUCT_END
551 * Linked list of messages to send to a particular other peer.
553 struct P2PPendingMessage
556 * Pointer to next item in the list
558 struct P2PPendingMessage *next;
561 * Pointer to previous item in the list
563 struct P2PPendingMessage *prev;
566 * Message importance level. FIXME: used? useful?
568 unsigned int importance;
571 * When does this message time out?
573 struct GNUNET_TIME_Absolute timeout;
576 * Actual message to be sent, allocated at the end of the struct:
577 * // msg = (cast) &pm[1];
578 * // memcpy (&pm[1], data, len);
580 const struct GNUNET_MessageHeader *msg;
586 * Linked List of peers which are part of trail to reach a particular Finger.
591 * Pointer to next item in the list
593 struct TrailPeerList *next;
596 * Pointer to previous item in the list
598 struct TrailPeerList *prev;
601 * An element in this trail list
603 struct GNUNET_PeerIdentity peer;
609 * FIXME: for congested peer just define a relative time as #define.
610 * Entry in friend_peermap.
617 struct GNUNET_PeerIdentity id;
620 * Number of trails for which this friend is the first hop.
622 unsigned int trails_count;
625 * Count of outstanding messages for this friend.
627 unsigned int pending_count;
630 * FIXME: Refer to time.c and gnunet_time_lib.h for correct functions.
631 * in handle_dht_p2p_trail_rejection, you should update these values
632 * and whenever you are selecting a friend in select_random_friend()
633 * and find_successor(), you should check congestion_duration = 0,
634 * then proceed else if congestion_duration < your current time then also
636 * struct GNUNET_TIME_Absolute start = GNUNET_TIME_absolute_get();
637 * struct GNUNET_TIME_Relative congestion_timeout =
638 * congestion_duration = GNUNET_TIME_absolute_add (start,congestion_timeout);
639 * in select_random_friend, GNUNET_TIME_absolute_get_remaning()
641 struct GNUNET_TIME_Absolute congestion_duration;
644 * Head of pending messages to be sent to this friend.
646 struct P2PPendingMessage *head;
649 * Tail of pending messages to be sent to this friend.
651 struct P2PPendingMessage *tail;
654 * Core handle for sending messages to this friend.
656 struct GNUNET_CORE_TransmitHandle *th;
662 * FIXME: make an array of trails. #define number of entries in the array =
663 * number of trails we want to keep. Remove head, tail of trails.
664 * Entry in finger_peermap.
671 struct GNUNET_PeerIdentity finger_identity;
674 * Index in finger peer map
676 unsigned int finger_map_index;
679 * Number of trails to reach to this finger.
681 unsigned int trail_count;
684 * Total number of entries in first trail from (me,finger)
686 unsigned int first_trail_length;
689 * Total number of entries in second trail from (me,finger)
691 unsigned int second_trail_length;
695 * Number of trail of which the first element to reach to this finger is
698 unsigned int first_friend_trails_count;
701 * Head of first trail to reach this finger.
703 struct TrailPeerList *first_trail_head;
706 * Tail of first trail to reach this finger.
708 struct TrailPeerList *first_trail_tail;
711 * Head of second trail to reach this finger.
713 struct TrailPeerList *second_trail_head;
716 * Tail of second trail to reach this finger.
718 struct TrailPeerList *second_trail_tail;
724 * FIXME: The name is not correct.
725 * Used to specify the kind of value stored in the array all_known_peers.
727 enum current_destination_type
737 * Data structure passed to sorting algorithm in find_successor().
742 * 64 bit value of peer identity
747 * FIXME: think of a better name for both the struct and destination_type
748 * Type : MY_ID, FINGER, FINGER, Value
750 enum current_destination_type type;
753 * Pointer to original data structure linked to peer id.
760 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
761 * get our first friend.
763 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
766 * Identity of this peer.
768 static struct GNUNET_PeerIdentity my_identity;
771 * Hash map of all the friends of a peer
773 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
776 * Hash map of all the fingers of a peer
778 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
783 static struct GNUNET_CORE_Handle *core_api;
786 * Finger map index for predecessor entry in finger peermap.
788 #define PREDECESSOR_FINGER_ID 64
791 * Maximum number of trails allowed to go through a friend.
792 * FIXME: Better name, Random value at the moment, need to be adjusted to maintain a balance
793 * between performance and Sybil tolerance.
795 #define TRAIL_THROUGH_FRIEND_THRESHOLD 64
798 * Possible number of different trails to reach to a finger. (Redundant routing)
800 #define TRAIL_COUNT 2
803 * The current finger index that we have want to find trail to.
805 static unsigned int current_search_finger_index;
809 * Iterate over trail and search your index location in the array.
810 * @param trail Trail which contains list of peers.
811 * @param trail_length Number of peers in the trail.
812 * @return Index in the array.
813 * #GNUNET_SYSERR, in case there is no entry which should not be the case ideally.
816 search_my_index (const struct GNUNET_PeerIdentity *trail,
821 while (i < trail_length)
823 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
829 return GNUNET_SYSERR;
833 * Compare two peer identities.
834 * @param p1 Peer identity
835 * @param p2 Peer identity
836 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
839 compare_peer_id (const void *p1, const void *p2)
841 struct Sorting_List *p11;
842 struct Sorting_List *p22;
844 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
845 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
846 p11 = (struct Sorting_List *)p1;
847 p22 = (struct Sorting_List *)p2;
848 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
849 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
855 * Return the predecessor of value in all_known_peers.
856 * @param all_known_peers list of all the peers
857 * @param value value we have to search in the all_known_peers.
858 * @param size Total numbers of elements
859 * @return Predecessor
861 static struct Sorting_List *
862 find_closest_predecessor(struct Sorting_List *all_known_peers, uint64_t value,
871 middle = (first + last)/2;
875 if(all_known_peers[middle].peer_id < value)
879 else if(all_known_peers[middle].peer_id == value)
883 return &all_known_peers[size - 1];
887 return &all_known_peers[middle - 1];
895 middle = (first + last)/2;
902 * Return the successor of value in all_known_peers.
903 * @param all_known_peers list of all the peers
904 * @param value value we have to search in the all_known_peers.
905 * @param size Total numbers of elements
908 static struct Sorting_List *
909 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
918 middle = (first + last)/2;
922 if(all_known_peers[middle].peer_id < value)
926 else if(all_known_peers[middle].peer_id == value)
928 if(middle == (size -1))
930 return &all_known_peers[0];
934 return &all_known_peers[middle+1];
942 middle = (first + last)/2;
949 * Called when core is ready to send a message we asked for
950 * out to the destination.
952 * @param cls the 'struct FriendInfo' of the target friend
953 * @param size number of bytes available in buf
954 * @param buf where the callee should write the message
955 * @return number of bytes written to buf
958 core_transmit_notify (void *cls, size_t size, void *buf)
960 struct FriendInfo *peer = cls;
962 struct P2PPendingMessage *pending;
967 while ((NULL != (pending = peer->head)) &&
968 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
970 peer->pending_count--;
971 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
972 GNUNET_free (pending);
976 /* no messages pending */
982 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
983 GNUNET_CORE_PRIO_BEST_EFFORT,
984 GNUNET_TIME_absolute_get_remaining
985 (pending->timeout), &peer->id,
986 ntohs (pending->msg->size),
987 &core_transmit_notify, peer);
988 GNUNET_break (NULL != peer->th);
992 while ((NULL != (pending = peer->head)) &&
993 (size - off >= (msize = ntohs (pending->msg->size))))
995 GNUNET_STATISTICS_update (GDS_stats,
997 ("# Bytes transmitted to other peers"), msize,
999 memcpy (&cbuf[off], pending->msg, msize);
1001 peer->pending_count--;
1002 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1003 GNUNET_free (pending);
1005 if (peer->head != NULL)
1008 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1009 GNUNET_CORE_PRIO_BEST_EFFORT,
1010 GNUNET_TIME_absolute_get_remaining
1011 (pending->timeout), &peer->id, msize,
1012 &core_transmit_notify, peer);
1013 GNUNET_break (NULL != peer->th);
1021 * Transmit all messages in the friend's message queue.
1023 * @param peer message queue to process
1026 process_friend_queue (struct FriendInfo *peer)
1028 struct P2PPendingMessage *pending;
1030 if (NULL == (pending = peer->head))
1032 if (NULL != peer->th)
1035 GNUNET_STATISTICS_update (GDS_stats,
1037 ("# Bytes of bandwidth requested from core"),
1038 ntohs (pending->msg->size), GNUNET_NO);
1040 /* FIXME: Are we correctly initializing importance and pending. */
1042 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
1043 pending->importance,
1044 GNUNET_TIME_absolute_get_remaining
1045 (pending->timeout), &peer->id,
1046 ntohs (pending->msg->size),
1047 &core_transmit_notify, peer);
1048 GNUNET_break (NULL != peer->th);
1053 * Construct a trail setup message and forward it to a friend.
1054 * @param source_peer Peer which wants to set up the trail to one of its finger.
1055 * @param destination_finger Peer identity closest to this value will be
1056 * @a source_peer's finger.
1057 * @param current_destination next destination corresponding to @a current_source,
1058 * can be either a finger or a friend of @a current_source.
1059 * @param current_source Peer for which @a current_destination is its finger/friend.
1060 * @param target_friend Friend to which this message should be forwarded.
1061 * @param trail_length Numbers of peers in the trail found so far.
1062 * @param trail_peer_list Peers this request has traversed so far
1063 * @param finger_map_index Index in finger peer map
1066 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
1067 uint64_t destination_finger,
1068 struct GNUNET_PeerIdentity *current_destination,
1069 struct GNUNET_PeerIdentity *current_source,
1070 struct FriendInfo *target_friend,
1071 unsigned int trail_length,
1072 const struct GNUNET_PeerIdentity *trail_peer_list,
1073 unsigned int finger_map_index)
1075 struct P2PPendingMessage *pending;
1076 struct PeerTrailSetupMessage *tsm;
1077 struct GNUNET_PeerIdentity *peer_list;
1080 msize = sizeof (struct PeerTrailSetupMessage) +
1081 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1083 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1089 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1091 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1095 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1096 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1097 tsm = (struct PeerTrailSetupMessage *) &pending[1];
1098 pending->msg = &tsm->header;
1099 tsm->header.size = htons (msize);
1100 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
1101 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
1102 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1103 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
1104 memcpy (&(tsm->current_source), current_source, sizeof (struct GNUNET_PeerIdentity));
1105 tsm->trail_length = htonl (trail_length);
1106 tsm->finger_map_index = htonl (finger_map_index);
1108 if (trail_length > 0)
1110 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1111 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1114 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1115 target_friend->pending_count++;
1116 process_friend_queue (target_friend);
1121 * Construct a trail setup result message and forward it to a friend.
1122 * @param destination_peer Peer which will get the trail to one of its finger.
1123 * @param source_finger Peer to which the trail has been setup to.
1124 * @param target_friend Friend to which this message should be forwarded.
1125 * @param trail_length Numbers of peers in the trail.
1126 * @param trail_peer_list Peers which are part of the trail from source to destination.
1127 * @param finger_map_index Index in finger peer map
1130 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destination_peer,
1131 const struct GNUNET_PeerIdentity *source_finger,
1132 struct FriendInfo *target_friend,
1133 unsigned int trail_length,
1134 const struct GNUNET_PeerIdentity *trail_peer_list,
1135 unsigned int finger_map_index)
1137 struct P2PPendingMessage *pending;
1138 struct PeerTrailSetupResultMessage *tsrm;
1139 struct GNUNET_PeerIdentity *peer_list;
1142 msize = sizeof (struct PeerTrailSetupResultMessage) +
1143 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1145 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1151 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1153 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1157 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1158 pending->importance = 0;
1159 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1160 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1161 pending->msg = &tsrm->header;
1162 tsrm->header.size = htons (msize);
1163 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
1164 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1165 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
1166 tsrm->trail_length = htonl (trail_length);
1167 tsrm->finger_map_index = htonl (finger_map_index);
1169 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1170 if (trail_length > 0)
1172 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1174 /* Send the message to chosen friend. */
1175 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1176 target_friend->pending_count++;
1177 process_friend_queue (target_friend);
1182 * Construct a PeerVerifySuccessor message and send it to friend.
1183 * @param source_peer Peer which wants to verify its successor
1184 * @param successor Peer which is our current successor
1185 * @param target_friend Friend to which this message should be forwarded.
1186 * @param trail_peer_list Peer which are part of trail from source to destination
1187 * @param trail_length Number of peers in the trail list.
1189 void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *source_peer,
1190 const struct GNUNET_PeerIdentity *successor,
1191 struct FriendInfo *target_friend,
1192 const struct GNUNET_PeerIdentity *trail_peer_list,
1193 unsigned int trail_length)
1195 struct PeerVerifySuccessorMessage *vsm;
1196 struct P2PPendingMessage *pending;
1197 struct GNUNET_PeerIdentity *peer_list;
1200 msize = sizeof (struct PeerVerifySuccessorMessage) +
1201 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1203 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1209 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1211 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1215 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1216 pending->importance = 0; /* FIXME */
1217 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1218 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1219 pending->msg = &vsm->header;
1220 vsm->header.size = htons (msize);
1221 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1222 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
1223 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1224 vsm->trail_length = htonl (trail_length);
1226 if (trail_length > 0)
1228 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1229 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1232 /* Send the message to chosen friend. */
1233 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1234 target_friend->pending_count++;
1235 process_friend_queue (target_friend);
1241 * Construct a PeerVerifySuccessorResult message and send it to friend.
1242 * @param destination_peer Peer which sent verify successor message
1243 * @param source_successor Peer to which verify successor message was sent.
1244 * @param my_predecessor source_successor's predecessor.
1245 * @param target_friend Friend to which this message should be forwarded.
1246 * @param trail_peer_list Peers which are part of trail from source to destination
1247 * @param trail_length Number of peers in the trail list.
1249 void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *destination_peer,
1250 const struct GNUNET_PeerIdentity *source_successor,
1251 const struct GNUNET_PeerIdentity *my_predecessor,
1252 struct FriendInfo *target_friend,
1253 const struct GNUNET_PeerIdentity *trail_peer_list,
1254 unsigned int trail_length)
1256 struct PeerVerifySuccessorResultMessage *vsmr;
1257 struct P2PPendingMessage *pending;
1258 struct GNUNET_PeerIdentity *peer_list;
1261 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1262 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1264 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1271 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1273 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1277 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1278 pending->importance = 0; /* FIXME */
1279 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1280 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1281 pending->msg = &vsmr->header;
1282 vsmr->header.size = htons (msize);
1283 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1284 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1285 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1286 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1287 vsmr->trail_length = htonl (trail_length);
1288 if (trail_length > 0)
1290 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1291 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1294 /* Send the message to chosen friend. */
1295 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1296 target_friend->pending_count++;
1297 process_friend_queue (target_friend);
1302 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1303 * @param source_peer Peer which is sending notify message to its new successor.
1304 * @param destination_peer Peer which is the new destination.
1305 * @param target_friend Next friend to pass this message to.
1306 * @param peer_list List of peers in the trail to reach to destination_peer.
1307 * @param trail_length Total number of peers in peer list
1310 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1311 const struct GNUNET_PeerIdentity *destination_peer,
1312 const struct GNUNET_PeerIdentity *old_successor,
1313 struct FriendInfo *target_friend,
1314 const struct GNUNET_PeerIdentity *trail_peer_list,
1315 unsigned int trail_length)
1317 struct PeerNotifyNewSuccessorMessage *nsm;
1318 struct P2PPendingMessage *pending;
1319 struct GNUNET_PeerIdentity *peer_list;
1322 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1323 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1325 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1331 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1333 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1337 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1338 pending->importance = 0; /* FIXME */
1339 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1340 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1341 pending->msg = &nsm->header;
1342 nsm->header.size = htons (msize);
1343 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1344 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1345 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1346 memcpy (&(nsm->old_successor), old_successor, sizeof (struct GNUNET_PeerIdentity));
1347 nsm->trail_length = htonl (trail_length);
1349 if (trail_length > 0)
1351 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1352 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1354 /* Send the message to chosen friend. */
1355 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1356 target_friend->pending_count++;
1357 process_friend_queue (target_friend);
1361 * Send a trail tear down message
1362 * @param source_peer Source of the trail.
1363 * @param destination_peer Destination of the trail.
1364 * @param discarded_trail Discarded trail from source to destination.
1365 * @param discarded_trail_length Total number of peers in trail_list.
1366 * @pararm target_peer Next peer to forward this message to.
1367 * @param new_first_friend The new first hop in the new trail from source to destination
1371 GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_PeerIdentity *source_peer,
1372 const struct GNUNET_PeerIdentity *destination_peer,
1373 const struct GNUNET_PeerIdentity *discarded_trail,
1374 unsigned int discarded_trail_length,
1375 struct FriendInfo *target_friend,
1376 const struct GNUNET_PeerIdentity *new_first_friend)
1378 struct P2PPendingMessage *pending;
1379 struct PeerTrailTearDownMessage *ttdm;
1380 struct GNUNET_PeerIdentity *peer_list;
1383 msize = sizeof (struct PeerTrailTearDownMessage) +
1384 (discarded_trail_length * sizeof(struct GNUNET_PeerIdentity));
1386 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1392 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1394 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1398 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1399 pending->importance = 0; /* FIXME */
1400 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1401 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1402 pending->msg = &ttdm->header;
1403 ttdm->header.size = htons (msize);
1404 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1405 memcpy (&(ttdm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1406 memcpy (&(ttdm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1407 memcpy (&(ttdm->new_first_friend),new_first_friend, sizeof (struct GNUNET_PeerIdentity));
1408 ttdm->trail_length = htonl (discarded_trail_length);
1410 if (discarded_trail_length > 0)
1412 peer_list = (struct GNUNET_PeerIdentity *) &ttdm[1];
1413 memcpy (peer_list, discarded_trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1415 /* Send the message to chosen friend. */
1416 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1417 target_friend->pending_count++;
1418 process_friend_queue (target_friend);
1424 * @param source_peer
1425 * @param destination_peer
1427 * @param trail_length
1428 * @param target_friend
1431 GDS_NEIGHBOURS_send_add_trail_message (struct GNUNET_PeerIdentity *source_peer,
1432 struct GNUNET_PeerIdentity *destination_peer,
1433 struct GNUNET_PeerIdentity *trail,
1434 unsigned int trail_length,
1435 struct FriendInfo *target_friend)
1437 struct P2PPendingMessage *pending;
1438 struct PeerAddTrailMessage *adm;
1439 struct GNUNET_PeerIdentity *peer_list;
1442 msize = sizeof (struct PeerAddTrailMessage) +
1443 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1445 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1451 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1453 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1457 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1458 pending->importance = 0; /* FIXME */
1459 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1460 adm = (struct PeerAddTrailMessage *) &pending[1];
1461 pending->msg = &adm->header;
1462 adm->header.size = htons (msize);
1463 adm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL);
1464 memcpy (&(adm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1465 memcpy (&(adm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1466 adm->trail_length = htonl (trail_length);
1468 if (trail_length > 0)
1470 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1471 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1474 /* Send the message to chosen friend. */
1475 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1476 target_friend->pending_count++;
1477 process_friend_queue (target_friend);
1482 * FIXME: CONGESTION: check the code once basic code is all correct. s
1483 * FIXME: call GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1484 * In case the friend chosen in select_random_friend() is congested or
1485 * has crossed trail_threshold, then get next friend which is not congested or
1486 * has not crossed trail threshold from friend peermap.
1487 * @param current_index Index in finger peermap chosen randomly
1488 * @param friend_peermap_size Total number of entries in friend peermap.
1489 * @param count Total number of time this function has been called, in case
1490 * count == sizeof(friend_peermap) - 1, it means none of the friends are free.
1491 * @return Friend Friend found.
1492 * NULL in case all the friends are congested or have crossed trail threshold.
1494 static struct FriendInfo *
1495 get_next_friend (unsigned int current_index,
1496 unsigned int friend_peermap_size,
1499 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1500 struct GNUNET_PeerIdentity key_ret;
1501 struct FriendInfo *friend;
1504 current_index = (current_index + 1) % friend_peermap_size;
1505 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1506 while(j < (current_index))
1508 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1516 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1518 if ((friend->trails_count > TRAIL_THROUGH_FRIEND_THRESHOLD) ||
1519 (0 != GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us))
1522 if (count == (friend_peermap_size -1))
1525 return get_next_friend (j,friend_peermap_size,count);
1535 * FIXME: CONGESTION: check the code once basic code is all correct.
1536 * FIXME: call GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1537 * Randomly choose one of your friends from the friends_peer map
1538 * @return Friend Randomly chosen friend.
1539 * NULL in case friend peermap is empty, or all the friends are either
1540 * congested or have crossed trail threshold.
1542 static struct FriendInfo *
1543 select_random_friend ()
1545 unsigned int current_size;
1546 unsigned int *index;
1548 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1549 struct GNUNET_PeerIdentity key_ret;
1550 struct FriendInfo *friend;
1552 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1553 if (0 == current_size)
1556 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1557 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1561 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1571 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1573 if ((TRAIL_THROUGH_FRIEND_THRESHOLD == friend->trails_count) ||
1574 (0 != GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us))
1576 return get_next_friend (*index, current_size, 1);
1586 * Compute finger_identity to which we want to setup the trail
1587 * @return finger_identity
1590 compute_finger_identity()
1594 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1595 my_id64 = GNUNET_ntohll (my_id64);
1596 return (my_id64 + (unsigned long) pow (2, current_search_finger_index));
1601 * Compute immediate predecessor identity in the network.
1602 * @return peer identity of immediate predecessor.
1605 compute_predecessor_identity()
1609 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1610 my_id64 = GNUNET_ntohll (my_id64);
1611 return (my_id64 -1);
1616 * Ping your successor to verify if it is still your successor or not.
1619 send_verify_successor_message()
1621 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1622 struct GNUNET_PeerIdentity key_ret;
1623 struct FriendInfo *target_friend;
1624 struct GNUNET_PeerIdentity next_hop;
1625 struct GNUNET_PeerIdentity *peer_list;
1626 struct FingerInfo *finger;
1627 unsigned int finger_index;
1630 /* Find the successor from the finger peermap.*/
1631 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1632 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1634 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1635 (const void **)&finger))
1637 if (0 == finger->finger_map_index)
1644 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1646 /* Either you don't have a successor or you are your own successor, then don't
1647 send a successor message. */
1649 (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &(finger->finger_identity))))
1654 if (finger->first_trail_length > 0)
1656 struct TrailPeerList *iterate;
1658 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->first_trail_length);
1659 iterate = finger->first_trail_head;
1661 while ( i < (finger->first_trail_length))
1663 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1664 iterate = iterate->next;
1667 memcpy (&next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1668 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
1672 /* If trail length = 0, then our successor is our friend. */
1674 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1675 &(finger->finger_identity));
1678 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1679 &(finger->finger_identity),
1682 finger->first_trail_length);
1687 * Choose a random friend and start looking for the trail to reach to
1688 * finger identity through this random friend.
1690 * @param cls closure for this task
1691 * @param tc the context under which the task is running
1694 send_find_finger_trail_message (void *cls,
1695 const struct GNUNET_SCHEDULER_TaskContext *tc)
1697 struct FriendInfo *target_friend;
1698 struct GNUNET_TIME_Relative next_send_time;
1699 uint64_t finger_identity;
1700 unsigned int finger_map_index;
1702 next_send_time.rel_value_us =
1703 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1704 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1705 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1706 find_finger_trail_task =
1707 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1710 target_friend = select_random_friend ();
1711 if (NULL == target_friend)
1716 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
1718 finger_identity = compute_predecessor_identity();
1722 finger_identity = compute_finger_identity();
1725 finger_map_index = current_search_finger_index;
1726 GDS_NEIGHBOURS_send_trail_setup (&my_identity, finger_identity, &(target_friend->id),
1727 &my_identity, target_friend, 0, NULL, finger_map_index);
1732 * Scan the trail to check if any of my own friend is part of trail. If yes
1733 * then shortcut the trail, send a trail teardown for the discarded trail,
1734 * update trail list and trail_length.
1735 * @param trail[Out] Current trail to reach to @a finger, will be updated
1736 * in case we compress the trail.
1737 * @param trail_length[Out] Number of peers in @a finger_trail, will be updated
1738 * in case we compress the trail.
1739 * @param finger Finger identity
1742 scan_and_compress_trail (struct GNUNET_PeerIdentity *trail,
1743 unsigned int *trail_length,
1744 const struct GNUNET_PeerIdentity *finger)
1747 struct FriendInfo *target_friend;
1749 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger))
1751 /* Here you don't send a trail teardown as no one added this in their
1757 if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger))
1759 int discarded_trail_length = *trail_length;
1760 target_friend = GNUNET_CONTAINER_multipeermap_get(friend_peermap, &trail[0]);
1761 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, trail,
1762 discarded_trail_length, target_friend, finger);
1768 i = *trail_length - 1;
1772 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
1774 /* This element of trail is not my friend. */
1779 /* A --> B(friend 1) --> C(friend 2)--> D ---> E, then we can rewrite the trail as
1781 * Now, we should remove the entry from A's routing table, B's routing table
1782 * and update the entry in C's routing table. Rest everything will be same.
1783 * C's routing table should have source peer as the prev.hop.
1785 struct GNUNET_PeerIdentity *discarded_trail;
1786 struct FriendInfo *target_friend;
1787 int discarded_trail_length;
1790 discarded_trail_length = i - 1;
1791 discarded_trail = GNUNET_malloc (discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1792 memcpy (discarded_trail, trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1793 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
1794 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, discarded_trail,
1795 discarded_trail_length, target_friend,
1798 /* Copy the trail from index i to index trail_length -1 and change
1799 trail length and return */
1800 while (i < *trail_length)
1802 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
1806 *trail_length = j+1;
1815 * FIXME: Adapt the code for List of trails.
1816 * Free finger and its trail.
1817 * @param finger Finger to be freed.
1820 free_finger (struct FingerInfo *finger)
1822 struct TrailPeerList *peer;
1824 if(finger->first_trail_head != NULL)
1826 while (NULL != (peer = finger->first_trail_head))
1828 GNUNET_CONTAINER_DLL_remove (finger->first_trail_head, finger->first_trail_tail, peer);
1833 if (finger->second_trail_head != NULL)
1835 while (NULL != (peer = finger->second_trail_head))
1837 GNUNET_CONTAINER_DLL_remove (finger->second_trail_head, finger->second_trail_tail, peer);
1840 GNUNET_free (finger);
1846 * FIXME: First check if both the trails are present if yes then send it
1847 * for both of them. Currently sending it only for one trail.
1848 * Send a trail teardown message for the trail of removed finger from the finger
1850 * @param existing_finger Finger to removed from the finger peermap.
1853 void send_trail_teardown (struct FingerInfo *removed_finger)
1855 struct GNUNET_PeerIdentity *peer_list;
1856 struct FriendInfo *friend;
1857 struct TrailPeerList *finger_trail;
1858 int removed_finger_trail_length = removed_finger->first_trail_length;
1861 if (removed_finger->first_trail_length == 0)
1864 finger_trail = removed_finger->first_trail_head;
1865 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(finger_trail->peer));
1866 peer_list = GNUNET_malloc ( removed_finger_trail_length * sizeof (struct GNUNET_PeerIdentity));
1867 while (i < removed_finger->first_trail_length)
1869 memcpy (&peer_list[i], &(finger_trail->peer), sizeof (struct GNUNET_PeerIdentity));
1870 finger_trail = finger_trail->next;
1874 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, &(removed_finger->finger_identity),
1875 peer_list, removed_finger_trail_length, friend,
1876 &(removed_finger->finger_identity));
1881 * FIXME: How do we understand which is the correct trail head?
1882 * Add a new trail to reach an existing finger in finger peermap and increment
1883 * the count of number of trails to reach to this finger.
1884 * @param existing_finger Finger
1885 * @param trail New trail to be added
1886 * @param trail_length Total number of peers in the trail.
1889 void add_new_trail (struct FingerInfo *existing_finger,
1890 struct GNUNET_PeerIdentity *trail,
1891 unsigned int trail_length)
1895 /* FIXME: Here you need to understand which trail is there and which not.
1896 In case first_trail_head != NULL, then that trail is present
1897 so you should add the second one. Need to verify this logic. */
1898 if (existing_finger->first_trail_head != NULL)
1900 while (i < trail_length)
1902 struct TrailPeerList *element;
1903 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1904 element->next = NULL;
1905 element->prev = NULL;
1907 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1908 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1912 else if (existing_finger->second_trail_head != NULL)
1914 while (i < trail_length)
1916 struct TrailPeerList *element;
1917 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1918 element->next = NULL;
1919 element->prev = NULL;
1921 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1922 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->first_trail_head, existing_finger->first_trail_tail, element);
1926 existing_finger->trail_count++;
1931 * In case there are already maximum number of possible trail to reach to a finger,
1932 * then check if the new trail's length is lesser than any of the existing trails.
1933 * If yes then replace that old trail by new trail.
1934 * Note: Here we are taking length as a parameter to choose the best possible trail,
1935 * but there could be other parameters also like - 1. duration of existence of a
1936 * trail - older the better. 2. if the new trail is completely disjoint than the
1937 * other trails, then may be choosing it is better.
1938 * @param existing_finger
1940 * @param trail_length
1941 * @return #GNUNET_YES
1945 void select_and_replace_trail (struct FingerInfo *existing_finger,
1946 struct GNUNET_PeerIdentity *new_trail,
1947 unsigned int new_trail_length)
1949 if (existing_finger->first_trail_length == existing_finger->second_trail_length)
1951 if (new_trail_length < existing_finger->first_trail_length)
1953 /* Randomly choose one of the trail. FIXME:currently I am just replacing the
1955 struct TrailPeerList *peer;
1958 while (NULL != (peer = existing_finger->first_trail_head))
1960 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1964 while (i < new_trail_length)
1966 struct TrailPeerList *element;
1967 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1968 element->next = NULL;
1969 element->prev = NULL;
1971 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1972 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1977 else if ((new_trail_length < existing_finger->second_trail_length) &&
1978 (existing_finger->second_trail_length < existing_finger->first_trail_length))
1980 /* Replace the first trail by the new trail. */
1981 struct TrailPeerList *peer;
1984 while (NULL != (peer = existing_finger->first_trail_head))
1986 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1990 while (i < new_trail_length)
1992 struct TrailPeerList *element;
1993 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1994 element->next = NULL;
1995 element->prev = NULL;
1997 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1998 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
2002 else if ( (new_trail_length < existing_finger->first_trail_length) &&
2003 (existing_finger->first_trail_length < existing_finger->second_trail_length))
2005 /* Replace the second trail by the new trail. */
2006 struct TrailPeerList *peer;
2009 while (NULL != (peer = existing_finger->second_trail_head))
2011 GNUNET_CONTAINER_DLL_remove (existing_finger->second_trail_head, existing_finger->second_trail_tail, peer);
2015 while (i < new_trail_length)
2017 struct TrailPeerList *element;
2018 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2019 element->next = NULL;
2020 element->prev = NULL;
2022 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
2023 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
2031 * FIXME: If we remove a finger which is our friend, then how should we handle it.
2032 * Ideally only in case if the trail_length > 0,we increment the trail count
2033 * of the first friend in the trail to reach to the finger. in case finger is
2034 * our friend then trail length = 0, and hence, we have never incremented the
2035 * trail count associated with that friend.
2036 * Decrement the trail count for the first friend to reach to the finger.
2040 decrement_friend_trail_count (struct FingerInfo *finger)
2042 struct FriendInfo *first_trail_friend;
2043 struct FriendInfo *second_trail_friend;
2045 if(finger->first_trail_head != NULL)
2047 first_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2048 &(finger->first_trail_head->peer));
2049 first_trail_friend->trails_count--;
2052 if(finger->second_trail_head != NULL)
2054 second_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2055 &(finger->second_trail_head->peer));
2056 second_trail_friend->trails_count--;
2060 /* We will not need this variable any more, all_friends_trail_threshold,
2061 FIXME: REMOVE IT. */
2062 if (GNUNET_YES == all_friends_trail_threshold)
2064 all_friends_trail_threshold = GNUNET_NO;
2065 /* FIXME; Here you should reschedule the send_find_finger_task here. or
2073 * FIXME: create a different data structure for storing the peer ids here.
2074 * Select the closest finger. Used for both predecessor and other fingers..
2075 * But internally calls different functions for predecessor and other fingers.
2076 * @param existing_finger Finger in finger peermap.
2077 * @param new_finger New finger identity
2078 * @param finger_map_index Index in finger peermap where @a existing_finger is stored.
2079 * @return #GNUNET_YES if the new finger is closest.
2080 * #GNUNET_NO if the old finger is closest.
2081 * #GNUNET_SYSERR in case our own identity is closest (should never happen).
2084 int select_finger (struct FingerInfo *existing_finger,
2085 const struct GNUNET_PeerIdentity *new_finger,
2086 unsigned int finger_map_index)
2088 struct Sorting_List peers[3]; /* 3 for existing_finger, new_finger, my_identity */
2089 struct Sorting_List *closest_finger;
2093 for (k = 0; k < 3; k++)
2096 /* Add your entry to peers. */
2097 memcpy (&peers[0], &my_identity, sizeof (uint64_t));
2098 peers[0].type = MY_ID;
2099 peers[0].data = NULL;
2101 /* Add existing_finger identity to the peers. */
2102 memcpy (&peers[1], &(existing_finger->finger_identity), sizeof (uint64_t));
2103 peers[1].type = FINGER;
2104 peers[1].data = existing_finger;
2106 /* Add new_finger identity to the peers. s*/
2107 memcpy (&peers[2], &new_finger, sizeof (uint64_t));
2108 peers[2].type = VALUE;
2109 peers[2].data = NULL;
2111 memcpy (&value, &my_identity, sizeof (uint64_t));
2112 qsort (&peers, 3, sizeof (struct Sorting_List), &compare_peer_id);
2114 if (PREDECESSOR_FINGER_ID == finger_map_index)
2115 closest_finger = find_closest_predecessor (peers, value, 3);
2117 closest_finger = find_closest_successor (peers, value, 3);
2119 if (closest_finger->type == FINGER)
2123 else if (closest_finger->type == VALUE)
2127 else if (closest_finger->type == MY_ID);
2129 return GNUNET_SYSERR;
2135 * FIXME: Better name, and make the code more cleaner.
2136 * Compare the new finger entry added and our successor.
2137 * @return #GNUNET_YES if same.
2138 * #GNUNET_NO if not.
2141 compare_new_entry_and_successor (const struct GNUNET_PeerIdentity *new_finger,
2142 int finger_map_index)
2144 int successor_flag = 0;
2145 struct FingerInfo *successor_finger;
2146 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2149 if (PREDECESSOR_FINGER_ID == finger_map_index)
2152 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2153 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2155 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2156 (const void **)&successor_finger))
2158 if (successor_finger->finger_map_index == 0)
2165 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2167 /* Ideally we should never reach here. */
2168 if (successor_flag == 0)
2174 if (0 == GNUNET_CRYPTO_cmp_peer_identity (new_finger, &(successor_finger->finger_identity)))
2182 * Add a new entry in finger table.
2183 * @param finger_identity PeerIdentity of the new finger
2184 * @param finger_trail Trail to reach to the finger, can be NULL in case I am my own
2186 * @param finger_trail_length Number of peers in the trail, can be 0 in case finger
2187 * is a friend or I am my own finger.
2188 * @param finger_map_index Index in finger map.
2191 add_new_entry (const struct GNUNET_PeerIdentity *finger_identity,
2192 struct GNUNET_PeerIdentity *finger_trail,
2193 uint32_t finger_trail_length,
2194 uint32_t finger_map_index)
2196 struct FriendInfo *first_friend_trail;
2197 struct FingerInfo *new_finger_entry;
2200 /* Add a new entry. */
2201 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
2202 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
2203 new_finger_entry->finger_map_index = finger_map_index;
2204 new_finger_entry->first_trail_length = finger_trail_length;
2205 new_finger_entry->trail_count = 1;
2207 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity)) /* finger_trail is NULL in case I am my own finger identity. */
2209 /* Incrementing the friend trails count. */
2210 if (finger_trail_length > 0)
2212 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_trail[0]);
2213 first_friend_trail->trails_count++;
2217 /* It means the finger is my friend. */
2218 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger_identity);
2219 first_friend_trail->trails_count++;
2221 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count;
2223 /* Copy the trail. */
2225 while (i < finger_trail_length)
2227 struct TrailPeerList *element;
2228 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2229 element->next = NULL;
2230 element->prev = NULL;
2232 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
2233 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2238 return GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2239 &(new_finger_entry->finger_identity),
2241 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
2246 * Choose the closest finger between existing finger and new finger.
2247 * If the new finger is closest, then send a trail_teardown message along
2248 * existing_finger's trail. In case both the id's are same, and there is a place
2249 * to add more trails, then store both of them. In case there is no space to
2250 * store any more trail, then choose the best trail (best - depends on length in
2251 * current_implementation) and discard the others.
2252 * @param existing_finger
2253 * @param new_finger Existing finger in finger_peermap for @a finger_map_index
2254 * @param trail Trail to reach from me to @a new_finger
2255 * @param trail_length Total number of peers in @a trail.
2256 * @param finger_map_index Index in finger peermap.
2257 * @return #GNUNET_YES In case we want to store the new entry.
2258 * #GNUNET_NO In case we want the existing entry.
2259 * #GNUNET_SYSERR Error.
2262 int select_closest_finger (struct FingerInfo *existing_finger,
2263 const struct GNUNET_PeerIdentity *new_finger,
2264 struct GNUNET_PeerIdentity *trail,
2265 unsigned int trail_length,
2266 unsigned int finger_map_index)
2268 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), new_finger))
2270 /* New entry and existing entry are same. */
2271 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), &my_identity))
2273 /* If existing_finger is my_identity then trail_length = 0, trail = NULL. In
2274 this case you don't need to check the trails. Exit. */
2277 if (trail_length > 0)
2279 scan_and_compress_trail (trail, &trail_length, new_finger);
2281 if (existing_finger->trail_count < TRAIL_COUNT)
2283 add_new_trail (existing_finger, trail, trail_length);
2288 select_and_replace_trail (existing_finger, trail, trail_length);
2292 else if (GNUNET_YES == select_finger (existing_finger, new_finger, finger_map_index))
2294 /* New finger is the closest finger. */
2295 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, new_finger))
2297 /* FIXME: Here in case the new finger is my_identity and old entry is not,
2298 should we keep the old entry even if the old entry is not the closest? */
2301 send_trail_teardown (existing_finger);
2302 decrement_friend_trail_count (existing_finger);
2303 free_finger (existing_finger);
2305 if (trail_length > 0)
2307 scan_and_compress_trail (trail, &trail_length, new_finger);
2311 else if (GNUNET_NO == select_finger (existing_finger, new_finger,finger_map_index))
2313 /* existing_finger is the closest finger. */
2316 return GNUNET_SYSERR;
2321 * Check if there is already an entry for finger map index in finger table.
2322 * If yes then choose the closest finger.
2323 * @param finger_identity Peer Identity of finger.
2324 * @param finger_trail Trail to reach from me to @a finger_identity
2325 * @param finger_trail_length Total number of peers in finger_trail.
2326 * @param finger_map_index Index in finger_peermap.
2327 * @return #GNUNET_YES if the new entry is added.
2328 * #GNUNET_NO if the new entry is discarded.
2331 int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
2332 struct GNUNET_PeerIdentity *finger_trail,
2333 uint32_t finger_trail_length,
2334 uint32_t finger_map_index)
2336 struct FingerInfo *existing_finger;
2337 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2339 int old_entry_found = GNUNET_NO;
2340 int new_entry_added = GNUNET_NO;
2342 /* Check if there is already an entry for the finger map index in the finger peer map. */
2343 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2344 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2346 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2347 (const void **)&existing_finger))
2349 if (existing_finger->finger_map_index == finger_map_index)
2351 old_entry_found = GNUNET_YES;
2352 if ( GNUNET_NO == select_closest_finger (existing_finger, finger_identity,
2353 finger_trail, finger_trail_length,
2355 goto update_current_search_finger_index;
2361 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2363 if (GNUNET_NO == old_entry_found)
2365 if (finger_trail_length > 0)
2367 scan_and_compress_trail (finger_trail, &finger_trail_length, finger_identity);
2371 /* FIXME: handle the case when addition in peer map failed. */
2372 if(GNUNET_OK == add_new_entry (finger_identity,finger_trail,finger_trail_length, finger_map_index))
2373 new_entry_added = GNUNET_YES;
2377 update_current_search_finger_index:
2378 if (0 == finger_map_index)
2380 current_search_finger_index = PREDECESSOR_FINGER_ID;
2381 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity))
2382 send_verify_successor_message();
2384 else if (GNUNET_YES == compare_new_entry_and_successor (finger_identity,finger_map_index))
2386 current_search_finger_index = 0;
2390 current_search_finger_index = current_search_finger_index - 1;
2393 return new_entry_added;
2399 * @param all_known_peers
2405 static struct Sorting_List *
2406 get_next_successor (struct Sorting_List *all_known_peers,
2407 unsigned int array_size,
2408 struct FriendInfo *friend,
2411 /* 1. search friend in all_known_peers.
2412 2. get the next peer. if peer == my_identity or peer == value, then go to
2414 3. if friend then again check if threshold crossed or not . If not then return
2415 or else again increment. remember starting index of friend in all_known_peers
2416 and when you reach to it again then return NULL as it means all the friend
2417 are congested or threshold reached.
2424 * Check if the friend is congested or has crossed TRAIL_THRESHOLD. If yes
2425 * then choose the peer next to it in the array. In case number of times this
2426 * function is called is equal to total number of entries in the array then it
2427 * means that none of the friends are busy. But remember in this array you also
2428 * have your own identity, value that you were searching, You should skip those
2429 * and also keep the count = size -2. But if we call in this order is our get/put
2430 * not getting wrong.
2431 * @param all_known_peers
2433 * @param friend Friend to be checked if
2434 * @param key_value To be ignored
2435 * @return #GNUNET_YES
2439 check_friend_threshold_and_congestion (struct Sorting_List *all_known_peers,
2440 unsigned int array_size,
2441 struct FriendInfo *friend,
2444 if (friend->trails_count == TRAIL_THROUGH_FRIEND_THRESHOLD)
2453 * FIXME: Complete the code for checking the threshold and getting the next
2454 * peer, add the case in finger.
2455 * In case a friend is either congested or has crossed its trail threshold,
2456 * then don't consider it as next successor, In case of finger if its first
2457 * friend has crossed the threshold then don't consider it. In case no finger
2458 * or friend is found, then return NULL.
2459 * Find closest successor for the value.
2460 * @param value Value for which we are looking for successor
2461 * @param[out] current_destination set to my_identity in case I am the final destination,
2462 * set to friend identity in case friend is final destination,
2463 * set to first friend to reach to finger, in case finger
2464 * is final destination.
2465 * @param[out] current_source set to my_identity.
2466 * @param finger_map_index Index in finger peer map.
2467 * @return Peer identity of next hop to send trail setup message to,
2468 * NULL in case all the friends are either congested or have crossed
2469 * their trail threshold.
2471 static struct GNUNET_PeerIdentity *
2472 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
2473 struct GNUNET_PeerIdentity *current_source, unsigned int finger_map_index)
2475 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
2476 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2477 struct GNUNET_PeerIdentity key_ret;
2478 struct FriendInfo *friend;
2479 struct FingerInfo *finger;
2480 unsigned int finger_index;
2481 unsigned int friend_index;
2482 struct Sorting_List *successor;
2486 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
2487 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
2488 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
2491 struct Sorting_List all_known_peers[size];
2494 for (k = 0; k < size; k++)
2495 all_known_peers[k].peer_id = 0;
2497 /* Copy your identity at 0th index in all_known_peers. */
2499 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
2500 all_known_peers[j].type = MY_ID;
2501 all_known_peers[j].data = 0;
2505 all_known_peers[j].peer_id = value;
2506 all_known_peers[j].type = VALUE;
2507 all_known_peers[j].data = 0;
2510 /* Iterate over friend peer map and copy all the elements into array. */
2511 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2512 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
2514 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
2516 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
2517 all_known_peers[j].type = FRIEND;
2518 all_known_peers[j].data = friend;
2524 /* Iterate over finger map and copy all the entries into all_known_peers array. */
2525 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2526 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2528 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
2530 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
2531 all_known_peers[j].type = FINGER;
2532 all_known_peers[j].data = finger;
2537 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2538 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
2541 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
2543 /* search value in all_known_peers array. */
2544 if (PREDECESSOR_FINGER_ID == finger_map_index)
2545 successor = find_closest_predecessor (all_known_peers, value, size);
2547 successor = find_closest_successor (all_known_peers, value, size);
2549 if (successor->type == MY_ID)
2551 memcpy (current_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2552 return &my_identity;
2554 else if (successor->type == FRIEND)
2556 struct FriendInfo *target_friend;
2557 target_friend = (struct FriendInfo *)successor->data;
2558 if( GNUNET_YES == check_friend_threshold_and_congestion (all_known_peers, size, target_friend, value))
2560 get_next_successor (all_known_peers, size, friend, value);
2562 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
2563 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2564 return current_destination;
2566 else if (successor->type == FINGER)
2568 struct GNUNET_PeerIdentity *next_hop;
2569 struct FingerInfo *finger;
2570 finger = successor->data;
2571 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2573 if (finger->first_trail_length > 0)
2575 struct TrailPeerList *iterator;
2576 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2577 iterator = finger->first_trail_head;
2578 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2580 else /* This means finger is our friend. */
2581 memcpy (next_hop, &(finger->finger_identity), sizeof(struct GNUNET_PeerIdentity));
2583 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
2584 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2596 * Construct a Put message and send it to target_peer.
2597 * @param key Key for the content
2598 * @param data Content to store
2599 * @param data_size Size of content @a data in bytes
2600 * @param block_type Type of the block
2601 * @param options Routing options
2602 * @param desired_replication_level Desired replication count
2603 * @param expiration_time When does the content expire
2604 * @param current_destination
2605 * @param current_source
2606 * @param target_peer Peer to which this message will be forwarded.
2607 * @param hop_count Number of hops traversed so far.
2608 * @param put_path_length Total number of peers in @a put_path
2609 * @param put_path Number of peers traversed so far
2612 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2613 const void *data, size_t data_size,
2614 enum GNUNET_BLOCK_Type block_type,
2615 enum GNUNET_DHT_RouteOption options,
2616 uint32_t desired_replication_level,
2617 struct GNUNET_TIME_Absolute expiration_time,
2618 struct GNUNET_PeerIdentity current_destination,
2619 struct GNUNET_PeerIdentity current_source,
2620 struct GNUNET_PeerIdentity *target_peer,
2622 uint32_t put_path_length,
2623 struct GNUNET_PeerIdentity *put_path)
2625 struct PeerPutMessage *ppm;
2626 struct P2PPendingMessage *pending;
2627 struct FriendInfo *target_friend;
2628 struct GNUNET_PeerIdentity *pp;
2631 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2632 sizeof (struct PeerPutMessage);
2634 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2636 put_path_length = 0;
2637 msize = data_size + sizeof (struct PeerPutMessage);
2640 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2646 /* This is the first call made from clients file. So, we should search for the
2648 if (NULL == target_peer)
2651 struct GNUNET_PeerIdentity *next_hop;
2653 memcpy (&key_value, key, sizeof (uint64_t));
2654 next_hop = find_successor (key_value, ¤t_destination, ¤t_source,PUT_GET_REQUEST);
2655 if (0 == GNUNET_CRYPTO_cmp_peer_identity(next_hop, &my_identity)) /* I am the destination do datacache_put */
2657 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
2658 block_type, data_size, data);
2662 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2665 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2666 pending->timeout = expiration_time;
2667 ppm = (struct PeerPutMessage *) &pending[1];
2668 pending->msg = &ppm->header;
2669 ppm->header.size = htons (msize);
2670 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
2671 ppm->options = htonl (options);
2672 ppm->block_type = htonl (block_type);
2673 ppm->hop_count = htonl (hop_count + 1);
2674 ppm->desired_replication_level = htonl (desired_replication_level);
2675 ppm->put_path_length = htonl (put_path_length);
2676 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2678 ppm->current_destination = current_destination;
2679 ppm->current_source = current_source;
2681 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2682 if (put_path_length != 0)
2684 memcpy (pp, put_path,
2685 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2687 memcpy (&pp[put_path_length], data, data_size);
2688 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2689 target_friend->pending_count++;
2690 process_friend_queue (target_friend);
2696 * Construct a Get message and send it to target_peer.
2697 * @param key Key for the content
2698 * @param block_type Type of the block
2699 * @param options Routing options
2700 * @param desired_replication_level Desired replication count
2701 * @param expiration_time When does the content expire
2702 * @param current_destination
2703 * @param current_source
2704 * @param target_peer Peer to which this message will be forwarded.
2705 * @param hop_count Number of hops traversed so far.
2706 * @param put_path_length Total number of peers in @a put_path
2707 * @param put_path Number of peers traversed so far
2710 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2711 enum GNUNET_BLOCK_Type block_type,
2712 enum GNUNET_DHT_RouteOption options,
2713 uint32_t desired_replication_level,
2714 struct GNUNET_PeerIdentity current_destination,
2715 struct GNUNET_PeerIdentity current_source,
2716 struct GNUNET_PeerIdentity *target_peer,
2718 uint32_t get_path_length,
2719 struct GNUNET_PeerIdentity *get_path)
2721 struct PeerGetMessage *pgm;
2722 struct P2PPendingMessage *pending;
2723 struct FriendInfo *target_friend;
2724 struct GNUNET_PeerIdentity *gp;
2727 msize = sizeof (struct PeerGetMessage) +
2728 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2730 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2736 if (NULL == target_peer)
2738 /* This is the first call from client file, we need to search for next_hop*/
2739 struct GNUNET_PeerIdentity *next_hop;
2742 memcpy (&key_value, key, sizeof (uint64_t));
2743 // FIXME: endianess of key_value!?
2744 next_hop = find_successor (key_value, ¤t_destination, ¤t_source,PUT_GET_REQUEST);
2745 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity,next_hop)) /* I am the destination do datacache_put */
2747 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2748 NULL, 0, 1, &my_identity, NULL,&my_identity);
2753 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2757 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2758 pending->importance = 0; /* FIXME */
2759 pgm = (struct PeerGetMessage *) &pending[1];
2760 pending->msg = &pgm->header;
2761 pgm->header.size = htons (msize);
2762 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2763 pgm->get_path_length = htonl (get_path_length);
2765 pgm->current_destination = current_destination;
2766 pgm->current_source = current_source;
2767 pgm->hop_count = htonl (hop_count + 1);
2771 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2772 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2774 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2775 target_friend->pending_count++;
2776 process_friend_queue (target_friend);
2781 * Send the get result to requesting client.
2782 * @param expiration When will this result expire?
2783 * @param key Key of the requested data.
2784 * @param put_path_length Number of peers in @a put_path
2785 * @param put_path Path taken to put the data at its stored location.
2786 * @param type Block type
2787 * @param data_size Size of the @a data
2788 * @param data Payload to store
2789 * @param get_path Path taken to reach to the location of the key.
2790 * @param get_path_length Number of peers in @a get_path
2791 * @param next_hop Next peer to forward the message to.
2792 * @param source_peer Peer which has the data for the key.
2795 GDS_NEIGHBOURS_send_get_result (struct GNUNET_TIME_Absolute expiration,
2796 const struct GNUNET_HashCode *key,
2797 unsigned int put_path_length,
2798 const struct GNUNET_PeerIdentity *put_path,
2799 enum GNUNET_BLOCK_Type type, size_t data_size,
2801 struct GNUNET_PeerIdentity *get_path,
2802 unsigned int get_path_length,
2803 struct GNUNET_PeerIdentity *next_hop,
2804 struct GNUNET_PeerIdentity *source_peer)
2806 struct PeerGetResultMessage *get_result;
2807 struct GNUNET_PeerIdentity *get_result_path;
2808 struct GNUNET_PeerIdentity *pp;
2809 struct P2PPendingMessage *pending;
2810 struct FriendInfo *target_friend;
2811 int current_path_index;
2814 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2815 sizeof (struct PeerPutMessage);
2817 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2823 if(get_path_length > 0)
2825 current_path_index = search_my_index(get_path, get_path_length);
2826 if (GNUNET_SYSERR == current_path_index)
2828 /* FIXME: This assertion always fails. FIX IT. */
2833 if (0 == current_path_index)
2835 GDS_CLIENTS_handle_reply (expiration, key, get_path_length, get_path, put_path_length,
2836 put_path, type, data_size, data);
2840 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2841 pending->importance = 0;
2842 get_result = (struct PeerGetResultMessage *)&pending[1];
2843 pending->msg = &get_result->header;
2844 get_result->header.size = htons (msize);
2845 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2846 get_result->key = *key;
2847 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2848 get_result->expiration_time = expiration;
2850 if (get_path_length != 0)
2852 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2853 memcpy (get_result_path, get_path,
2854 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2856 memcpy (&get_result_path[get_path_length], data, data_size);
2858 /* FIXME: Is this correct? */
2859 if (put_path_length != 0)
2861 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2862 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2864 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2865 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2866 target_friend->pending_count++;
2867 process_friend_queue (target_friend);
2872 * Send trail rejection message to the peer which sent me a trail setup message.
2873 * @param source_peer Source peer which wants to set up the trail.
2874 * @param finger_identity Value whose successor will be the finger of @a source_peer.
2875 * @param congested_peer Peer which has send trail rejection message.
2876 * @param next_hop Peer to which this message should be forwarded.
2877 * @param finger_map_index Index in @a source_peer finger peermap.
2878 * @param trail_peer_list Trail followed to reach from @a source_peer to next_hop,
2879 * NULL, in case the @a congested_peer was the first peer
2880 * to which trail setup message was forwarded.
2881 * @param trail_length Number of peers in trail_peer_list.
2884 GDS_NEIGHBOURS_send_trail_rejection (const struct GNUNET_PeerIdentity *source_peer,
2885 uint64_t finger_identity,
2886 const struct GNUNET_PeerIdentity *congested_peer,
2887 const struct GNUNET_PeerIdentity *next_hop,
2888 unsigned int finger_map_index,
2889 struct GNUNET_PeerIdentity *trail_peer_list,
2890 unsigned int trail_length)
2892 struct PeerTrailRejectionMessage *trail_rejection;
2893 struct GNUNET_PeerIdentity *trail_list;
2894 struct P2PPendingMessage *pending;
2895 struct FriendInfo *target_friend;
2898 msize = trail_length * sizeof(struct GNUNET_PeerIdentity) +
2899 sizeof (struct PeerTrailRejectionMessage);
2901 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2907 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2908 pending->importance = 0;
2909 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2910 trail_rejection = (struct PeerTrailRejectionMessage *) &pending[1];
2911 pending->msg = &trail_rejection->header;
2912 trail_rejection->header.size = htons (msize);
2913 trail_rejection->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
2914 memcpy (&(trail_rejection->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2915 memcpy (&(trail_rejection->congested_peer), congested_peer, sizeof (struct GNUNET_PeerIdentity));
2916 memcpy (&(trail_rejection->finger_identity_value), &finger_identity, sizeof (uint64_t));
2917 trail_rejection->finger_map_index = htonl (finger_map_index);
2918 trail_rejection->trail_length = htonl (trail_length);
2920 if (trail_length != 0)
2922 trail_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2923 memcpy (trail_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2926 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2927 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2928 target_friend->pending_count++;
2929 process_friend_queue (target_friend);
2934 * Core handler for P2P put messages.
2935 * @param cls closure
2936 * @param peer sender of the request
2937 * @param message message
2938 * @return #GNUNET_OK to keep the connection open,
2939 * #GNUNET_SYSERR to close it (signal serious error)
2942 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2943 const struct GNUNET_MessageHeader *message)
2945 struct PeerPutMessage *put;
2946 struct GNUNET_PeerIdentity *put_path;
2947 struct GNUNET_HashCode test_key;
2948 enum GNUNET_DHT_RouteOption options;
2949 struct GNUNET_PeerIdentity current_destination;
2950 struct GNUNET_PeerIdentity current_source;
2951 struct GNUNET_PeerIdentity *next_hop;
2955 size_t payload_size;
2958 msize = ntohs (message->size);
2959 if (msize < sizeof (struct PeerPutMessage))
2961 GNUNET_break_op (0);
2965 put = (struct PeerPutMessage *) message;
2966 putlen = ntohl (put->put_path_length);
2969 sizeof (struct PeerPutMessage) +
2970 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2972 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2974 GNUNET_break_op (0);
2978 current_destination = put->current_destination;
2979 current_source = put->current_source;
2980 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2981 payload = &put_path[putlen];
2982 options = ntohl (put->options);
2983 payload_size = msize - (sizeof (struct PeerPutMessage) +
2984 putlen * sizeof (struct GNUNET_PeerIdentity));
2986 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
2987 payload, payload_size, &test_key))
2990 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
2992 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
2993 GNUNET_break_op (0);
2994 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2995 "PUT with key `%s' for block with key %s\n",
2996 put_s, GNUNET_h2s_full (&test_key));
2997 GNUNET_free (put_s);
3002 GNUNET_break_op (0);
3005 /* cannot verify, good luck */
3009 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3011 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3012 ntohl (put->block_type),
3014 NULL, 0, /* bloom filer */
3015 NULL, 0, /* xquery */
3016 payload, payload_size))
3018 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3019 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3022 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3023 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3024 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3025 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3026 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3027 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3029 GNUNET_break_op (0);
3034 struct GNUNET_PeerIdentity pp[putlen + 1];
3035 /* extend 'put path' by sender */
3036 /* FIXME: Check what are we doing here? */
3037 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3039 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3046 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3047 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3049 GDS_ROUTING_print();
3050 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3051 if (next_hop == NULL)
3053 /* refer to handle_dht_p2p_trail_setup. */
3058 next_hop = find_successor (key_value, ¤t_destination, ¤t_source,PUT_GET_REQUEST);
3061 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop)) /* I am the final destination */
3063 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3064 &(put->key),putlen, pp, ntohl (put->block_type),
3065 payload_size, payload);
3070 GDS_CLIENTS_process_put (options,
3071 ntohl (put->block_type),
3072 ntohl (put->hop_count),
3073 ntohl (put->desired_replication_level),
3075 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3079 GDS_NEIGHBOURS_send_put (&put->key, payload, payload_size,
3080 ntohl (put->block_type),ntohl (put->options),
3081 ntohl (put->desired_replication_level),
3082 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3083 current_destination, current_source, next_hop,
3084 ntohl (put->hop_count), putlen, pp);
3088 return GNUNET_SYSERR;
3093 * Core handler for p2p get requests.
3095 * @param cls closure
3096 * @param peer sender of the request
3097 * @param message message
3098 * @return #GNUNET_OK to keep the connection open,
3099 * #GNUNET_SYSERR to close it (signal serious error)
3102 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3103 const struct GNUNET_MessageHeader *message)
3105 struct PeerGetMessage *get;
3106 struct GNUNET_PeerIdentity *get_path;
3107 struct GNUNET_PeerIdentity current_destination;
3108 struct GNUNET_PeerIdentity current_source;
3109 struct GNUNET_PeerIdentity *next_hop;
3110 uint32_t get_length;
3114 msize = ntohs (message->size);
3115 if (msize < sizeof (struct PeerGetMessage))
3117 GNUNET_break_op (0);
3121 get = (struct PeerGetMessage *)message;
3122 get_length = ntohl (get->get_path_length);
3123 get_path = (struct GNUNET_PeerIdentity *)&get[1];
3124 current_destination = get->current_destination;
3125 current_source = get->current_source;
3128 sizeof (struct PeerGetMessage) +
3129 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3131 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3133 GNUNET_break_op (0);
3137 /* Add sender to get path */
3138 struct GNUNET_PeerIdentity gp[get_length + 1];
3139 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3140 gp[get_length + 1] = *peer;
3141 get_length = get_length + 1;
3143 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3144 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3146 GDS_ROUTING_print();
3147 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
3148 if (next_hop == NULL)
3150 /* refer to handle_dht_p2p_trail_setup. */
3155 next_hop = find_successor (key_value, ¤t_destination, ¤t_source,PUT_GET_REQUEST);
3158 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop))
3160 /* I am the destination.*/
3161 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3162 struct GNUNET_PeerIdentity next_hop;
3164 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3165 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3166 get_length = get_length + 1;
3167 memcpy (&next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
3168 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3169 get_length, final_get_path,&next_hop, &my_identity);
3175 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3176 get->desired_replication_level,current_destination,
3177 current_source, next_hop, 0,
3180 return GNUNET_SYSERR;
3185 * FIXME: In case of trail, we don't have source and destination part of the trail,
3186 * Check if we follow the same in case of get/put/get_result. Also, in case of
3187 * put should we do a routing table add.
3188 * Core handler for get result
3189 * @param cls closure
3190 * @param peer sender of the request
3191 * @param message message
3192 * @return #GNUNET_OK to keep the connection open,
3193 * #GNUNET_SYSERR to close it (signal serious error)
3196 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3197 const struct GNUNET_MessageHeader *message)
3199 struct PeerGetResultMessage *get_result;
3200 struct GNUNET_PeerIdentity *get_path;
3201 struct GNUNET_PeerIdentity *put_path;
3203 size_t payload_size;
3205 unsigned int getlen;
3206 unsigned int putlen;
3207 int current_path_index;
3209 msize = ntohs (message->size);
3210 if (msize < sizeof (struct PeerGetResultMessage))
3212 GNUNET_break_op (0);
3216 get_result = (struct PeerGetResultMessage *)message;
3217 getlen = ntohl (get_result->get_path_length);
3218 putlen = ntohl (get_result->put_path_length);
3221 sizeof (struct PeerGetResultMessage) +
3222 getlen * sizeof (struct GNUNET_PeerIdentity) +
3223 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3225 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3227 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3229 GNUNET_break_op (0);
3233 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
3234 payload = &get_path[getlen];
3235 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3236 getlen * sizeof (struct GNUNET_PeerIdentity));
3237 /* FIXME: Check if its correct or not. */
3240 put_path = &get_path[1];
3244 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3246 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3247 getlen, get_path, putlen,
3248 put_path, get_result->type, payload_size, payload);
3253 struct GNUNET_PeerIdentity *next_hop;
3254 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3255 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3256 current_path_index = search_my_index (get_path, getlen);
3257 /* FIXME: First check if you are adding yourself to the get path or not.
3258 if yes then don't check if current_path_index == 0, if not then check
3259 and next_hop == source_peer. */
3260 memcpy (next_hop, &get_path[current_path_index - 1], sizeof (struct GNUNET_PeerIdentity));
3262 GDS_NEIGHBOURS_send_get_result (get_result->expiration_time, &(get_result->key),
3264 get_result->type, payload_size,payload,
3266 next_hop, &(get_result->source_peer));
3269 return GNUNET_SYSERR;
3274 * FIXME: URGENT: refactor it.
3275 * FIXME; now we can make a new ds to store 2 peers and one value as we are
3276 * using it at two places. Will complete the logic and then add a new ds.
3277 * In case finger map index is 64 do we need to call find_closest_predecessor?
3278 * Select the closest peer.
3280 * @param current_destination
3281 * @param current_source
3283 * @para finger_map_index
3284 * @return Peer which is closest, in case of error NULL.
3286 struct GNUNET_PeerIdentity *
3287 select_closest_peer (const struct GNUNET_PeerIdentity *prev_hop,
3288 struct GNUNET_PeerIdentity *current_destination,
3289 struct GNUNET_PeerIdentity *current_source,
3291 unsigned int finger_map_index)
3293 struct GNUNET_PeerIdentity *peer1;
3294 struct GNUNET_PeerIdentity *peer2;
3295 struct Sorting_List peers[3];
3296 struct Sorting_List *closest_finger;
3298 peer1 = GDS_ROUTING_search (current_source, current_destination, prev_hop);
3299 peer2 = find_successor (value, current_destination, current_source,finger_map_index);
3301 /* SUPU TEST CODE */
3302 struct GNUNET_PeerIdentity print_peer;
3303 memcpy (&print_peer, &peer1, sizeof (struct GNUNET_PeerIdentity));
3304 FPRINTF (stderr,_("\nSUPU %s, %s, %d,routing_peer = %s"), __FILE__, __func__,__LINE__,GNUNET_i2s(&print_peer));
3305 memcpy (&print_peer, &peer2, sizeof (struct GNUNET_PeerIdentity));
3306 FPRINTF (stderr,_("\nSUPU %s, %s, %d,find_successor_peer = %s"), __FILE__, __func__,__LINE__,GNUNET_i2s(&print_peer));
3307 /* SUPU TEST CODE ENDS*/
3308 if( (peer1 != NULL) && (peer2 != NULL))
3310 /* Add peer 1 to the list. */
3311 memcpy (&peers[0], &peer1, sizeof (uint64_t));
3312 peers[0].type = FINGER;
3313 peers[0].data = NULL;
3315 /* Add peer 2 to the list. */
3316 memcpy (&peers[1], &peer1, sizeof (uint64_t));
3317 peers[0].type = FRIEND;
3318 peers[0].data = NULL;
3320 /* Add value to the list. */
3321 memcpy (&peers[2], &peer1, sizeof (uint64_t));
3322 peers[0].type = VALUE;
3323 peers[0].data = NULL;
3325 qsort (&peers, 3, sizeof (struct Sorting_List), &compare_peer_id);
3326 if (PREDECESSOR_FINGER_ID == finger_map_index)
3327 closest_finger = find_closest_predecessor (peers, value, 3);
3329 closest_finger = find_closest_successor (peers, value, 3);
3332 if (closest_finger->type == FINGER)
3334 FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
3337 else if (closest_finger->type == VALUE)
3341 else if (closest_finger->type == FRIEND);
3343 /* If we are returning peer2 then find_successor has already taken care
3344 of setting up current_destination and current_source. */
3348 else if ((peer1 == NULL) && (peer2 == NULL))
3352 else if (peer1 == NULL)
3356 else if (peer2 == NULL)
3365 * Core handle for PeerTrailSetupMessage.
3366 * @param cls closure
3367 * @param message message
3368 * @param peer peer identity this notification is about
3369 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3372 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3373 const struct GNUNET_MessageHeader *message)
3375 const struct PeerTrailSetupMessage *trail_setup;
3376 struct GNUNET_PeerIdentity current_destination;
3377 struct GNUNET_PeerIdentity current_source;
3378 struct GNUNET_PeerIdentity source;
3379 struct GNUNET_PeerIdentity *next_hop;
3380 struct GNUNET_PeerIdentity next_peer;
3381 struct GNUNET_PeerIdentity *trail_peer_list;
3382 struct FriendInfo *target_friend;
3383 uint64_t destination_finger_value;
3384 uint32_t trail_length;
3385 uint32_t finger_map_index;
3388 msize = ntohs (message->size);
3389 if (msize < sizeof (struct PeerTrailSetupMessage))
3391 GNUNET_break_op (0);
3395 trail_setup = (const struct PeerTrailSetupMessage *) message;
3396 trail_length = ntohl (trail_setup->trail_length);
3398 if ((msize < sizeof (struct PeerTrailSetupMessage) +
3399 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3401 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3403 GNUNET_break_op (0);
3407 if (trail_length > 0)
3408 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
3409 memcpy (¤t_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity));
3410 memcpy (¤t_source,&(trail_setup->current_source), sizeof (struct GNUNET_PeerIdentity));
3411 memcpy (&source, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity));
3412 finger_map_index = ntohl (trail_setup->finger_map_index);
3413 destination_finger_value = ntohl (trail_setup->destination_finger);
3415 /* Check your routing table size, and if you can handle any more trails through you. */
3416 if (GNUNET_YES == GDS_ROUTING_check_threshold())
3418 GDS_NEIGHBOURS_send_trail_rejection (&source, destination_finger_value, &my_identity,
3419 peer, finger_map_index, trail_peer_list, trail_length);
3423 /* Check if you are current_destination or not. */
3424 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
3426 next_hop = select_closest_peer (peer, ¤t_destination, ¤t_source,
3427 destination_finger_value, finger_map_index);
3431 next_hop = find_successor (destination_finger_value, ¤t_destination,
3432 ¤t_source,finger_map_index);
3435 if (NULL == next_hop)
3437 GNUNET_STATISTICS_update (GDS_stats,
3438 gettext_noop ("# Trail not found in routing table during"
3439 "trail setup request, packet dropped."),
3441 return GNUNET_SYSERR;
3443 else if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
3445 if (trail_length == 0)
3447 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
3451 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3454 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3455 GDS_NEIGHBOURS_send_trail_setup_result (&source,
3457 target_friend, trail_length,
3464 /* Now add yourself to the trail. */
3465 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3466 if (trail_length != 0)
3467 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3468 peer_list[trail_length] = my_identity;
3470 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3471 GDS_NEIGHBOURS_send_trail_setup (&source,
3472 destination_finger_value,
3473 ¤t_destination, ¤t_source,
3474 target_friend, trail_length, peer_list,
3482 * Core handle for p2p trail construction result messages.
3484 * @param message message
3485 * @param peer peer identity this notification is about
3486 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3489 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3490 const struct GNUNET_MessageHeader *message)
3492 const struct PeerTrailSetupResultMessage *trail_result;
3493 struct GNUNET_PeerIdentity *trail_peer_list;
3494 struct GNUNET_PeerIdentity destination_peer;
3495 struct GNUNET_PeerIdentity finger_identity;
3496 uint32_t trail_length;
3497 uint32_t finger_map_index;
3500 msize = ntohs (message->size);
3501 if (msize < sizeof (struct PeerTrailSetupResultMessage))
3503 GNUNET_break_op (0);
3507 trail_result = (const struct PeerTrailSetupResultMessage *) message;
3508 trail_length = ntohl (trail_result->trail_length);
3511 sizeof (struct PeerTrailSetupResultMessage) +
3512 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3514 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3516 GNUNET_break_op (0);
3520 finger_map_index = htonl (trail_result->finger_map_index);
3521 memcpy (&destination_peer, &(trail_result->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3522 memcpy (&finger_identity, &(trail_result->finger_identity), sizeof (struct GNUNET_PeerIdentity));
3524 if (trail_length > 0)
3525 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
3528 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3531 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
3537 struct GNUNET_PeerIdentity next_hop;
3538 struct FriendInfo *target_friend;
3541 my_index = search_my_index (trail_peer_list, trail_length);
3542 if (my_index == GNUNET_SYSERR)
3543 return GNUNET_SYSERR;
3547 next_hop = trail_result->destination_peer;
3550 next_hop = trail_peer_list[my_index - 1];
3552 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3553 &(trail_result->finger_identity))))
3555 struct GNUNET_PeerIdentity *routing_next_hop;
3557 routing_next_hop = GDS_ROUTING_search (&destination_peer,&finger_identity,
3559 if ((NULL == routing_next_hop) ||
3560 (0 != GNUNET_CRYPTO_cmp_peer_identity(routing_next_hop, &next_hop)))
3562 GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
3565 GDS_ROUTING_print();
3568 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3569 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
3570 &(trail_result->finger_identity),
3571 target_friend, trail_length,
3576 return GNUNET_SYSERR;
3581 * Get my current predecessor from the finger peer map
3582 * @return Current predecessor.
3584 static struct FingerInfo *
3587 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
3588 struct GNUNET_PeerIdentity key_ret;
3589 unsigned int finger_index;
3590 struct FingerInfo *my_predecessor;
3593 /* Iterate over finger peer map and extract your predecessor. */
3594 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
3595 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
3597 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
3598 (finger_iter,&key_ret,(const void **)&my_predecessor))
3600 if(PREDECESSOR_FINGER_ID == my_predecessor->finger_map_index)
3607 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
3612 return my_predecessor;
3617 * Core handle for p2p verify successor messages.
3618 * @param cls closure
3619 * @param message message
3620 * @param peer peer identity this notification is about
3621 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3624 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3625 const struct GNUNET_MessageHeader *message)
3627 const struct PeerVerifySuccessorMessage *vsm;
3628 const struct GNUNET_PeerIdentity *trail_peer_list;
3629 struct GNUNET_PeerIdentity source_peer;
3630 struct GNUNET_PeerIdentity next_hop;
3631 struct FriendInfo *target_friend;
3633 uint32_t trail_length;
3635 msize = ntohs (message->size);
3636 if (msize < sizeof (struct PeerVerifySuccessorMessage))
3638 GNUNET_break_op (0);
3642 vsm = (struct PeerVerifySuccessorMessage *) message;
3643 trail_length = ntohl (vsm->trail_length);
3645 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
3646 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3647 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3649 GNUNET_break_op (0);
3652 if (trail_length > 0)
3653 trail_peer_list = (const struct GNUNET_PeerIdentity *)&vsm[1];
3654 memcpy (&source_peer, &(vsm->source_peer), sizeof(struct GNUNET_PeerIdentity));
3656 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
3658 struct FingerInfo *my_predecessor;
3659 if (trail_length == 0)
3661 memcpy (&next_hop, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3665 memcpy (&next_hop, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3667 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3669 my_predecessor = get_predecessor();
3670 if (NULL == my_predecessor)
3672 /* FIXME: should we just return. */
3676 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3677 &(my_predecessor->finger_identity))))
3679 /* Source peer and my predecessor, both are same. */
3680 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3682 &(my_predecessor->finger_identity),
3689 struct GNUNET_PeerIdentity *new_successor_trail;
3690 struct TrailPeerList *iterator;
3691 int new_trail_length;
3694 new_trail_length = trail_length + my_predecessor->first_trail_length + 1;
3695 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
3696 if (trail_length > 0)
3697 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
3699 memcpy (&new_successor_trail[trail_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3701 if (my_predecessor->first_trail_length)
3703 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
3704 iterator = my_predecessor->first_trail_head;
3705 i = trail_length + 1;
3706 while (i < new_trail_length)
3708 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
3709 iterator = iterator->next;
3713 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3715 &(my_predecessor->finger_identity),
3717 new_successor_trail,
3726 if (trail_length == 0)
3729 return GNUNET_SYSERR;
3732 my_index = search_my_index (trail_peer_list, trail_length);
3733 if (my_index == GNUNET_SYSERR)
3736 return GNUNET_SYSERR;
3738 if (my_index == (trail_length - 1))
3740 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(vsm->successor));
3744 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3745 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3748 GDS_NEIGHBOURS_send_verify_successor (&(vsm->source_peer), &(vsm->successor),target_friend,
3749 trail_peer_list, trail_length);
3751 return GNUNET_SYSERR;
3756 * Core handle for p2p verify successor result messages.
3757 * @param cls closure
3758 * @param message message
3759 * @param peer peer identity this notification is about
3760 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3763 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3764 const struct GNUNET_MessageHeader *message)
3766 const struct PeerVerifySuccessorResultMessage *vsrm;
3767 struct GNUNET_PeerIdentity *trail_peer_list;
3768 struct GNUNET_PeerIdentity next_hop;
3769 struct FriendInfo *target_friend;
3771 uint32_t trail_length;
3773 msize = ntohs (message->size);
3774 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
3776 GNUNET_break_op (0);
3779 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
3780 trail_length = ntohl (vsrm->trail_length);
3783 sizeof (struct PeerVerifySuccessorResultMessage) +
3784 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3786 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3788 GNUNET_break_op (0);
3792 if (trail_length > 0)
3793 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
3795 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity))))
3797 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
3799 if (GNUNET_YES == finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0))
3801 memcpy (&next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
3802 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3803 /* FIXME: first call scan_and_compress_trail and then call the notify new
3804 successor with new trail. */
3805 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
3806 &(vsrm->source_successor),
3807 target_friend, trail_peer_list,
3819 my_index = search_my_index (trail_peer_list, trail_length);
3820 if (GNUNET_SYSERR == my_index)
3823 return GNUNET_SYSERR;
3828 memcpy (&next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3832 memcpy (&next_hop, &trail_peer_list[my_index-1], sizeof (struct GNUNET_PeerIdentity));
3835 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3836 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
3837 &(vsrm->source_successor),
3838 &(vsrm->my_predecessor),
3844 return GNUNET_SYSERR;
3849 * Core handle for p2p notify new successor messages.
3850 * @param cls closure
3851 * @param message message
3852 * @param peer peer identity this notification is about
3853 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3856 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3857 const struct GNUNET_MessageHeader *message)
3859 const struct PeerNotifyNewSuccessorMessage *nsm;
3860 struct GNUNET_PeerIdentity *trail_peer_list;
3861 struct GNUNET_PeerIdentity source_peer;
3862 struct GNUNET_PeerIdentity old_successor;
3863 struct GNUNET_PeerIdentity new_successor;
3865 uint32_t trail_length;
3867 msize = ntohs (message->size);
3868 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
3870 GNUNET_break_op (0);
3873 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
3874 trail_length = ntohl (nsm->trail_length);
3876 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3877 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3879 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3881 GNUNET_break_op (0);
3885 if( trail_length > 0)
3886 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
3887 memcpy (&source_peer, &(nsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
3888 memcpy (&old_successor, &(nsm->old_successor), sizeof (struct GNUNET_PeerIdentity));
3889 memcpy (&new_successor, &(nsm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3891 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&new_successor, &my_identity)))
3893 /* I am the new successor. */
3894 struct GNUNET_PeerIdentity *new_predecessor;
3895 new_predecessor = GNUNET_new (struct GNUNET_PeerIdentity);
3896 memcpy (new_predecessor, &(nsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
3897 if (GNUNET_YES == finger_table_add (new_predecessor, trail_peer_list, trail_length, PREDECESSOR_FINGER_ID))
3899 /* You are adding a new predecessor in your finger table. but the intermediate
3900 peers don't have an entry in their routing table. So, you need to check the
3901 return value of finger_table_Add and if its successful then you should send
3902 routing_add_message. */
3908 struct FriendInfo *target_friend;
3909 struct GNUNET_PeerIdentity next_hop;
3912 if (trail_length == 0)
3913 return GNUNET_SYSERR;
3915 my_index = search_my_index (trail_peer_list, trail_length);
3916 if (GNUNET_SYSERR == my_index)
3918 /* FIXME: happend once */
3920 return GNUNET_SYSERR;
3923 if (my_index == (trail_length - 1))
3925 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(nsm->destination_peer));
3929 memcpy (&next_hop, &trail_peer_list[my_index+1], sizeof (struct GNUNET_PeerIdentity));
3930 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3933 GDS_ROUTING_remove_trail (&source_peer, &old_successor, peer);
3934 GDS_ROUTING_add (&(nsm->source_peer), &(nsm->destination_peer), &next_hop, peer);
3935 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
3936 &(nsm->destination_peer),
3937 &(nsm->old_successor),
3938 target_friend, trail_peer_list,
3942 return GNUNET_SYSERR;
3946 * FIXME: pass congestion time in struct PeerTrailRejectionMessage,
3947 * we are calling exact same thing here as in handle_dht_p2p_trail_seutp.set
3949 * if we make it a function then we can it here.
3950 * Core handler for P2P trail rejection message
3951 * @param cls closure
3952 * @param message message
3953 * @param peer peer identity this notification is about
3954 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3957 int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3958 const struct GNUNET_MessageHeader *message)
3960 const struct PeerTrailRejectionMessage *trail_rejection;
3961 struct GNUNET_PeerIdentity *trail_peer_list;
3962 struct FriendInfo *target_friend;
3963 struct GNUNET_PeerIdentity next_hop;
3964 struct GNUNET_PeerIdentity *next_peer;
3965 struct GNUNET_PeerIdentity source;
3966 struct GNUNET_PeerIdentity current_destination;
3967 struct GNUNET_PeerIdentity current_source;
3968 uint32_t trail_length;
3969 uint32_t finger_map_index;
3970 uint64_t destination_finger_value;
3973 msize = ntohs (message->size);
3974 if (msize < sizeof (struct PeerTrailRejectionMessage))
3976 GNUNET_break_op (0);
3980 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3981 trail_length = ntohl (trail_rejection->trail_length);
3983 if ((msize < sizeof (struct PeerTrailRejectionMessage) +
3984 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3986 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3988 GNUNET_break_op (0);
3992 if (trail_length > 0)
3993 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3994 finger_map_index = ntohl (trail_rejection->finger_map_index);
3995 memcpy (&destination_finger_value, &(trail_rejection->finger_identity_value), sizeof (uint64_t));
3996 memcpy (&source, &(trail_rejection->source_peer), sizeof (struct GNUNET_PeerIdentity));
3998 /* First set the congestion time of the friend that sent you this message. */
3999 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4000 //FIXME: target_friend->congestion_time ==?
4002 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(trail_rejection->source_peer))))
4007 if(GNUNET_YES == GDS_ROUTING_check_threshold())
4009 struct GNUNET_PeerIdentity *new_trail;
4010 unsigned int new_trail_length;
4012 if (trail_length == 1)
4015 new_trail_length = 0;
4016 memcpy (&next_hop, &(trail_rejection->source_peer), sizeof (struct GNUNET_PeerIdentity));
4020 memcpy (&next_hop, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
4021 /* Remove myself from the trail. */
4022 new_trail_length = trail_length -1;
4023 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4024 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4026 GDS_NEIGHBOURS_send_trail_rejection (&(trail_rejection->source_peer),
4027 destination_finger_value,
4028 &my_identity, &next_hop,finger_map_index,
4029 new_trail,new_trail_length);
4034 memcpy (¤t_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
4035 memcpy (¤t_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
4036 next_peer = find_successor (destination_finger_value,¤t_destination,
4037 ¤t_source, finger_map_index);
4038 if (NULL == next_peer)
4040 GNUNET_STATISTICS_update (GDS_stats,
4041 gettext_noop ("# Trail not found in routing table during"
4042 "trail setup request, packet dropped."),
4044 return GNUNET_SYSERR;
4046 else if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_peer, &my_identity)))/* This means I am the final destination */
4048 if (trail_length == 0)
4050 memcpy (&next_hop, &source, sizeof (struct GNUNET_PeerIdentity));
4054 memcpy (&next_hop, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
4056 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4057 GDS_NEIGHBOURS_send_trail_setup_result (&source,
4059 target_friend, trail_length,
4066 /* Now add yourself to the trail. */
4067 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4068 if (trail_length != 0)
4069 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
4070 peer_list[trail_length] = my_identity;
4072 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4073 GDS_NEIGHBOURS_send_trail_setup (&source,
4074 destination_finger_value,
4075 ¤t_destination, ¤t_source,
4076 target_friend, trail_length, peer_list,
4085 /* FIXME: there is a loop between in call from notify new successor to this function
4086 * check why and fix it.
4087 * Core handle for p2p trail tear down messages.
4088 * @param cls closure
4089 * @param message message
4090 * @param peer peer identity this notification is about
4091 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4094 int handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
4095 const struct GNUNET_MessageHeader *message)
4097 struct PeerTrailTearDownMessage *trail_teardown;
4098 struct GNUNET_PeerIdentity *discarded_trail;
4099 struct GNUNET_PeerIdentity next_hop;
4100 struct FriendInfo *target_friend;
4101 uint32_t discarded_trail_length;
4105 msize = ntohs (message->size);
4106 if (msize < sizeof (struct PeerTrailTearDownMessage))
4108 GNUNET_break_op (0);
4112 trail_teardown = (struct PeerTrailTearDownMessage *) message;
4113 discarded_trail_length = ntohl (trail_teardown->trail_length);
4115 if ((msize < sizeof (struct PeerTrailTearDownMessage) +
4116 discarded_trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
4117 (discarded_trail_length >
4118 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
4120 GNUNET_break_op (0);
4124 if (discarded_trail_length > 0)
4125 discarded_trail = (struct GNUNET_PeerIdentity *) &trail_teardown[1];
4127 /* SUPU TEST CODE */
4128 struct GNUNET_PeerIdentity print_peer;
4130 while ( k < discarded_trail_length)
4132 memcpy (&print_peer, &discarded_trail[k], sizeof (struct GNUNET_PeerIdentity));
4133 FPRINTF (stderr,_("\nSUPU %s, %s, %d,discarded_trail[%d]=%s"),
4134 __FILE__, __func__,__LINE__,k,GNUNET_i2s(&print_peer));
4137 /* SUPU TEST CODE ENDS*/
4138 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->new_first_friend),
4141 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer),
4149 * I am the new first hop in the trail to reach from source to destination.
4150 Update the trail in routing table with prev_hop == source peer. */
4151 return GDS_ROUTING_trail_update (&(trail_teardown->source_peer),
4152 &(trail_teardown->destination_peer), peer);
4157 /* This should always be the case. */
4158 if (discarded_trail_length > 0)
4160 my_index = search_my_index (discarded_trail, discarded_trail_length);
4161 if(GNUNET_SYSERR == my_index)
4162 return GNUNET_SYSERR;
4167 return GNUNET_SYSERR;
4169 GDS_ROUTING_print();
4170 if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
4171 &(trail_teardown->destination_peer),peer))
4173 /* Here we get GNUNET_NO, only if there is no matching entry found in routing
4179 /* In case we got this message when we removed an entry from finger table,
4180 then we need to send the message to destination. */
4181 if (my_index != (discarded_trail_length - 1))
4182 memcpy (&next_hop, &discarded_trail[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
4184 memcpy (&next_hop, &(trail_teardown->destination_peer), sizeof (struct GNUNET_PeerIdentity));
4185 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4187 GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer),
4188 &(trail_teardown->destination_peer),
4189 discarded_trail, discarded_trail_length,
4190 target_friend, &(trail_teardown->new_first_friend));
4193 return GNUNET_SYSERR;
4197 * Core handle for p2p routing table add messages.
4198 * @param cls closure
4199 * @param message message
4200 * @param peer peer identity this notification is about
4201 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4204 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
4205 const struct GNUNET_MessageHeader *message)
4207 /* This function is called in case when we update our predecessor as a new peer
4208 claims to be our successor. In that case as we did not do a trail setup,
4209 intermediate nodes don't know about this trail. our predecessor has added
4210 that trail but not we. So, we need to add it. Its only in case of predecessor
4211 and succcessor that we have a symmetric relation. */
4212 struct PeerAddTrailMessage *add_trail;
4213 struct GNUNET_PeerIdentity *trail;
4214 struct GNUNET_PeerIdentity next_hop;
4215 struct FriendInfo *target_friend;
4217 uint32_t trail_length;
4220 msize = ntohs (message->size);
4221 if (msize < sizeof (struct PeerAddTrailMessage))
4223 GNUNET_break_op (0);
4227 add_trail = (struct PeerAddTrailMessage *) message;
4228 trail_length = ntohl (add_trail->trail_length);
4230 if ((msize < sizeof (struct PeerAddTrailMessage) +
4231 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
4233 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
4235 GNUNET_break_op (0);
4239 if (trail_length > 0)
4240 trail = (struct GNUNET_PeerIdentity *)&add_trail[1];
4242 my_index = search_my_index (trail, trail_length);
4243 if (GNUNET_SYSERR == my_index)
4246 return GNUNET_SYSERR;
4249 memcpy(&next_hop, &(add_trail->source_peer), sizeof (struct GNUNET_PeerIdentity));
4251 memcpy (&next_hop, &trail[my_index - 1], sizeof (struct GNUNET_PeerIdentity));
4253 if (GNUNET_YES == GDS_ROUTING_add (&(add_trail->source_peer), &(add_trail->destination_peer),
4258 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4259 GDS_NEIGHBOURS_send_add_trail_message (&(add_trail->source_peer),
4260 &(add_trail->destination_peer),
4261 trail, trail_length,target_friend);
4267 /* FIXME: there is not space in routing table to add the trail. What should
4269 return GNUNET_SYSERR;
4275 * FIXME: Adapt the code for List of trails.
4276 * Iterate over finger_peermap, and remove entries with peer as the first element
4278 * @param cls closure
4279 * @param key current public key
4280 * @param value value in the hash map
4281 * @return #GNUNET_YES if we should continue to
4283 * #GNUNET_NO if not.
4286 remove_matching_finger (void *cls,
4287 const struct GNUNET_PeerIdentity *key,
4290 struct FingerInfo *remove_finger = value;
4291 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
4293 if (remove_finger->first_trail_length > 0)
4295 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->first_trail_head->peer, disconnected_peer))
4297 GNUNET_assert (GNUNET_YES ==
4298 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
4301 free_finger (remove_finger);
4304 else if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_finger->finger_identity),
4307 GNUNET_assert (GNUNET_YES ==
4308 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
4311 free_finger (remove_finger);
4319 * Method called whenever a peer disconnects.
4321 * @param cls closure
4322 * @param peer peer identity this notification is about
4325 handle_core_disconnect (void *cls,
4326 const struct GNUNET_PeerIdentity *peer)
4328 struct FriendInfo *remove_friend;
4330 /* Check for self message. */
4331 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
4334 /* Search for peer to remove in your friend_peermap. */
4336 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4338 if (NULL == remove_friend)
4344 /* Remove fingers for which this peer is the first element in the trail or if
4345 * the friend is a finger. */
4346 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap,
4347 &remove_matching_finger, (void *)peer);
4348 GDS_ROUTING_remove_entry (peer);
4350 /* Remove the peer from friend_peermap. */
4351 GNUNET_assert (GNUNET_YES ==
4352 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
4356 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
4359 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4361 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4362 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4370 * Method called whenever a peer connects.
4372 * @param cls closure
4373 * @param peer_identity peer identity this notification is about
4376 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
4378 struct FriendInfo *friend;
4380 /* Check for connect to self message */
4381 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
4384 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
4386 /* If peer already exists in our friend_peermap, then exit. */
4387 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
4393 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
4396 friend = GNUNET_new (struct FriendInfo);
4397 friend->id = *peer_identity;
4398 friend->trails_count = 0;
4400 GNUNET_assert (GNUNET_OK ==
4401 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
4402 peer_identity, friend,
4403 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
4405 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
4406 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
4407 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
4412 * To be called on core init/fail.
4414 * @param cls service closure
4415 * @param identity the public identity of this peer
4418 core_init (void *cls,
4419 const struct GNUNET_PeerIdentity *identity)
4421 my_identity = *identity;
4426 * Initialize neighbours subsystem.
4427 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4430 GDS_NEIGHBOURS_init (void)
4432 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
4433 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
4434 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
4435 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
4436 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
4437 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
4438 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
4439 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
4440 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
4441 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
4442 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
4443 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL, 0},
4448 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
4449 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
4450 GNUNET_NO, core_handlers);
4451 if (NULL == core_api)
4452 return GNUNET_SYSERR;
4454 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
4455 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS * 4/3, GNUNET_NO);
4462 * Shutdown neighbours subsystem.
4465 GDS_NEIGHBOURS_done (void)
4467 if (NULL == core_api)
4470 GNUNET_CORE_disconnect (core_api);
4473 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
4474 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
4475 friend_peermap = NULL;
4477 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
4478 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
4479 finger_peermap = NULL;
4481 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4484 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
4485 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
4493 * @return my identity
4495 struct GNUNET_PeerIdentity
4496 GDS_NEIGHBOURS_get_my_id (void)
4502 /* end of gnunet-service-xdht_neighbours.c */