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. Use a global array of all known peers in find_successor, Only when
49 a new peer is added in finger or friend peer map, then re calculate
50 the array. Or else use the old one.*/
53 * Maximum possible fingers of a peer.
55 #define MAX_FINGERS 63
58 * Maximum allowed number of pending messages per friend peer.
60 #define MAXIMUM_PENDING_PER_FRIEND 64
63 * How long at least to wait before sending another find finger trail request,
64 * at most we wait twice this long.
66 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
69 * How long at most to wait for transmission of a GET request to another peer?
71 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
74 * Maximum number of trails allowed to go through a friend.
76 #define LINK_THRESHOLD 64
79 GNUNET_NETWORK_STRUCT_BEGIN
87 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
89 struct GNUNET_MessageHeader header;
94 uint32_t options GNUNET_PACKED;
99 uint32_t block_type GNUNET_PACKED;
104 uint32_t hop_count GNUNET_PACKED;
107 * Replication level for this message
109 uint32_t desired_replication_level GNUNET_PACKED;
112 * Length of the PUT path that follows (if tracked).
114 uint32_t put_path_length GNUNET_PACKED;
117 * Current destination to which this message is forwarded.
119 struct GNUNET_PeerIdentity current_destination;
122 * Peer whose finger is current_destination.
124 struct GNUNET_PeerIdentity current_source;
127 * When does the content expire?
129 struct GNUNET_TIME_AbsoluteNBO expiration_time;
132 * The key to store the value under.
134 struct GNUNET_HashCode key GNUNET_PACKED;
137 /* put path (if tracked) */
147 struct PeerGetResultMessage
150 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
152 struct GNUNET_MessageHeader header;
155 * The type for the data.
157 uint32_t type GNUNET_PACKED;
160 * Peer which will receive the get result message.
162 struct GNUNET_PeerIdentity source_peer;
165 * Number of peers recorded in the outgoing path from source to the
166 * stored location of this message.
168 uint32_t put_path_length GNUNET_PACKED;
171 * Length of the GET path that follows (if tracked).
173 uint32_t get_path_length GNUNET_PACKED;
176 * When does the content expire?
178 struct GNUNET_TIME_Absolute expiration_time;
181 * The key of the corresponding GET request.
183 struct GNUNET_HashCode key;
185 /* put path (if tracked) */
187 /* get path (if tracked) */
197 struct PeerGetMessage
200 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
202 struct GNUNET_MessageHeader header;
207 uint32_t options GNUNET_PACKED;
210 * Desired content type.
212 uint32_t block_type GNUNET_PACKED;
217 uint32_t hop_count GNUNET_PACKED;
220 * Desired replication level for this request.
222 uint32_t desired_replication_level GNUNET_PACKED;
225 * Total number of peers in get path.
227 unsigned int get_path_length;
230 * Peer which is an intermediate destination.
232 struct GNUNET_PeerIdentity current_destination;
235 * Source for which current_destination is the finger.
237 struct GNUNET_PeerIdentity current_source;
240 * The key we are looking for.
242 struct GNUNET_HashCode key;
250 * FIXME: Check the alignment in all the struct
251 * P2P Trail setup message
253 struct PeerTrailSetupMessage
257 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
259 struct GNUNET_MessageHeader header;
262 * Successor of this finger value will be our finger peer.
264 uint64_t destination_finger;
267 * Source peer which wants to setup the trail to one of its finger.
269 struct GNUNET_PeerIdentity source_peer;
272 * Peer to which this packet is forwarded.
274 struct GNUNET_PeerIdentity current_destination;
277 * In case the packet is forwarded to an intermediate finger, then
278 * current_source contains the peer id whose finger is the intermediate
279 * finger. In case the packet is forwarded to a friend, then it is NULL.
281 struct GNUNET_PeerIdentity current_source;
284 * Index into finger peer map, in NBO.
286 uint32_t finger_map_index;
289 * Number of entries in trail list, in NBO.
291 uint32_t trail_length GNUNET_PACKED;
297 * P2P Trail Setup Result message
299 struct PeerTrailSetupResultMessage
303 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
305 struct GNUNET_MessageHeader header;
308 * Finger to which we have found the path.
310 struct GNUNET_PeerIdentity finger_identity;
313 * Peer which was looking for the trail to finger.
315 struct GNUNET_PeerIdentity destination_peer;
318 * Index into finger peer map
320 uint32_t finger_map_index;
323 * Number of entries in trail list.
325 uint32_t trail_length GNUNET_PACKED;
332 struct PeerTrailRejectionMessage
335 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
337 struct GNUNET_MessageHeader header;
340 * Source peer which wants to set up the trail.
342 struct GNUNET_PeerIdentity source_peer;
345 * Peer which sent trail rejection message.
347 struct GNUNET_PeerIdentity congested_peer;
350 * Finger identity value.
352 uint64_t finger_identity;
355 * Index in finger peer map of source peer.
357 uint32_t finger_map_index;
360 * Total number of peers in the trail.
362 uint32_t trail_length;
369 * P2P Verify Successor message.
371 struct PeerVerifySuccessorMessage
375 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
377 struct GNUNET_MessageHeader header;
380 * Source peer which wants to verify its successor.
382 struct GNUNET_PeerIdentity source_peer;
385 * My current successor.
387 struct GNUNET_PeerIdentity successor;
390 * Total number of peers in trail to current successor.
392 uint32_t trail_length;
397 * P2P Verify Successor Result message.
399 struct PeerVerifySuccessorResultMessage
403 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
405 struct GNUNET_MessageHeader header;
408 * Destination peer which sent the request to verify its successor.
410 struct GNUNET_PeerIdentity destination_peer;
413 * Successor to which PeerVerifySuccessorMessage was sent.
415 struct GNUNET_PeerIdentity source_successor;
418 * source_successor's predecessor
420 struct GNUNET_PeerIdentity my_predecessor;
423 * Total number of peers in trail.
424 * If source_successor is not destination peer, then trail is from destination_peer
426 * If source_successor is destination peer, then trail is from destination_peer
427 * to source_successor.
429 uint32_t trail_length;
433 * P2P Notify New Successor message.
435 struct PeerNotifyNewSuccessorMessage
438 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
440 struct GNUNET_MessageHeader header;
443 * Source peer which wants to notify its new successor.
445 struct GNUNET_PeerIdentity source_peer;
448 * New successor identity.
450 struct GNUNET_PeerIdentity destination_peer;
453 * Number of peers in trail from source_peer to new successor.
455 uint32_t trail_length;
459 GNUNET_NETWORK_STRUCT_END
463 * Linked list of messages to send to a particular other peer.
465 struct P2PPendingMessage
468 * Pointer to next item in the list
470 struct P2PPendingMessage *next;
473 * Pointer to previous item in the list
475 struct P2PPendingMessage *prev;
478 * Message importance level. FIXME: used? useful?
480 unsigned int importance;
483 * When does this message time out?
485 struct GNUNET_TIME_Absolute timeout;
488 * Actual message to be sent, allocated at the end of the struct:
489 * // msg = (cast) &pm[1];
490 * // memcpy (&pm[1], data, len);
492 const struct GNUNET_MessageHeader *msg;
498 * Linked List of peers which are part of trail to reach a particular Finger.
503 * Pointer to next item in the list
505 struct TrailPeerList *next;
508 * Pointer to previous item in the list
510 struct TrailPeerList *prev;
513 * An element in this trail list
515 struct GNUNET_PeerIdentity peer;
521 * Entry in friend_peermap.
528 struct GNUNET_PeerIdentity id;
531 * Number of trail of which this friend is the first hop.
533 unsigned int trail_links;
536 * Count of outstanding messages for this friend.
538 unsigned int pending_count;
541 * Head of pending messages to be sent to this friend.
543 struct P2PPendingMessage *head;
546 * Tail of pending messages to be sent to this friend.
548 struct P2PPendingMessage *tail;
551 * Core handle for sending messages to this friend.
553 struct GNUNET_CORE_TransmitHandle *th;
559 * Entry in finger_peermap.
566 struct GNUNET_PeerIdentity finger_identity;
569 * Index in finger peer map
571 unsigned int finger_map_index;
574 * Total number of entries in trail from (me,finger]
576 unsigned int trail_length;
579 * Head of trail to reach this finger.
581 struct TrailPeerList *head;
584 * Tail of trail to reach this finger.
586 struct TrailPeerList *tail;
590 enum current_destination_type
599 * FIXME: Think of a better name.
600 * Data structure passed to sorting algorithm in find_successor.
605 * 64 bit value of peer identity
610 * Type : MY_ID, FINGER, FINGER, Value
612 enum current_destination_type type;
615 * Pointer to original data structure linked to peer id.
622 * FIXME: Think of better comments.
623 * An entry in Failed_Trail_List
628 * Source peer which was trying to setup up the trail to @a destination_finger_value
630 struct GNUNET_PeerIdentity source_peer;
633 * Value to which we were trying to find the closest successor.
635 uint64_t destination_finger_value;
638 * Peer which has crossed the threshold limit on its routing table size.
640 struct GNUNET_PeerIdentity congested_peer;
646 * Task that sends FIND FINGER TRAIL requests.
648 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
652 * Task that periodically verifies my successor.
654 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
657 * Identity of this peer.
659 static struct GNUNET_PeerIdentity my_identity;
662 * Hash map of all the friends of a peer
664 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
667 * Hash map of all the fingers of a peer
669 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
672 * Hash maps of all the trail which failed due to a congested peer.
674 static struct GNUNET_CONTAINER_MultiPeerMap *failed_trail_list;
679 static struct GNUNET_CORE_Handle *core_api;
682 * Finger map index for predecessor entry in finger peermap.
684 #define PREDECESSOR_FINGER_ID 64
687 * The current finger index that we have found trail to.
689 static unsigned int current_finger_index;
692 * Iterate over trail and search your index location in the array.
693 * @param trail Trail which contains list of peers.
694 * @return Index in the array.
697 search_my_index (const struct GNUNET_PeerIdentity *trail)
703 * Called when core is ready to send a message we asked for
704 * out to the destination.
706 * @param cls the 'struct FriendInfo' of the target friend
707 * @param size number of bytes available in buf
708 * @param buf where the callee should write the message
709 * @return number of bytes written to buf
712 core_transmit_notify (void *cls, size_t size, void *buf)
714 struct FriendInfo *peer = cls;
716 struct P2PPendingMessage *pending;
721 while ((NULL != (pending = peer->head)) &&
722 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
724 peer->pending_count--;
725 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
726 GNUNET_free (pending);
730 /* no messages pending */
736 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
737 GNUNET_CORE_PRIO_BEST_EFFORT,
738 GNUNET_TIME_absolute_get_remaining
739 (pending->timeout), &peer->id,
740 ntohs (pending->msg->size),
741 &core_transmit_notify, peer);
742 GNUNET_break (NULL != peer->th);
746 while ((NULL != (pending = peer->head)) &&
747 (size - off >= (msize = ntohs (pending->msg->size))))
749 GNUNET_STATISTICS_update (GDS_stats,
751 ("# Bytes transmitted to other peers"), msize,
753 memcpy (&cbuf[off], pending->msg, msize);
755 peer->pending_count--;
756 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
757 GNUNET_free (pending);
759 if (peer->head != NULL)
762 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
763 GNUNET_CORE_PRIO_BEST_EFFORT,
764 GNUNET_TIME_absolute_get_remaining
765 (pending->timeout), &peer->id, msize,
766 &core_transmit_notify, peer);
767 GNUNET_break (NULL != peer->th);
774 * Transmit all messages in the friend's message queue.
776 * @param peer message queue to process
779 process_friend_queue (struct FriendInfo *peer)
781 struct P2PPendingMessage *pending;
783 if (NULL == (pending = peer->head))
785 if (NULL != peer->th)
788 GNUNET_STATISTICS_update (GDS_stats,
790 ("# Bytes of bandwidth requested from core"),
791 ntohs (pending->msg->size), GNUNET_NO);
793 /* FIXME: Are we correctly initializing importance and pending. */
795 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
797 GNUNET_TIME_absolute_get_remaining
798 (pending->timeout), &peer->id,
799 ntohs (pending->msg->size),
800 &core_transmit_notify, peer);
801 GNUNET_break (NULL != peer->th);
806 * FIXME: In this function using const, does it affect only here right? not in
807 * the struct P2PTrailSetupMessage as their fields are not defined as const.
808 * Also, I changed current_destination and current_source from const to not,
809 * because when we make a call from handle_dht_p2p_trail_setup, then we are
810 * passing struct for current_destination and not current_source, as we are writing
811 * to these variables and we can not decalre them as const.
812 * Construct a trail message and forward it to a friend.
813 * @param source_peer Peer which wants to set up the trail to one of its finger.
814 * @param destination_finger Peer identity closest to this value will be
815 * @a source_peer's finger.
816 * @param current_destination Finger of the @a current_source, for which among
817 * its friends, its own identity and all fingers, this
818 * finger is the closest to the @a destination_finger
819 * @param current_source Peer for which @a current_destination is its finger.
820 * @param target_friend Friend to which this message should be forwarded.
821 * @param trail_length Numbers of peers in the trail found so far.
822 * @param trail_peer_list Peers this request has traversed so far
823 * @param finger_map_index Index in finger peer map
826 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
827 uint64_t destination_finger,
828 struct GNUNET_PeerIdentity *current_destination,
829 struct GNUNET_PeerIdentity *current_source,
830 struct FriendInfo *target_friend,
831 unsigned int trail_length,
832 const struct GNUNET_PeerIdentity *trail_peer_list,
833 unsigned int finger_map_index)
835 struct P2PPendingMessage *pending;
836 struct PeerTrailSetupMessage *tsm;
837 struct GNUNET_PeerIdentity *peer_list;
840 msize = sizeof (struct PeerTrailSetupMessage) +
841 (trail_length * sizeof (struct GNUNET_PeerIdentity));
843 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
849 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
851 /* SUPU: Its important to have such statistics as you need to keep track of
852 the packets lost due to full queue. */
853 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
857 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
858 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
859 tsm = (struct PeerTrailSetupMessage *) &pending[1];
860 pending->msg = &tsm->header;
861 tsm->header.size = htons (msize);
862 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
863 /* FIXME: understand where you need to use memcpy or direct assignment. */
864 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
865 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
866 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
867 memcpy (&(tsm->current_source), current_source, sizeof (struct GNUNET_PeerIdentity));
868 tsm->trail_length = htonl (trail_length);
869 tsm->finger_map_index = htonl (finger_map_index);
871 /* SUPU: here i guess its okay to have it as NULL as it is added at the end of
872 the struct but in case of current_destination and current_source, it is part
873 of the struct. thats why the confusion. */
874 if (trail_peer_list != NULL)
876 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
877 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
880 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
881 target_friend->pending_count++;
882 process_friend_queue (target_friend);
888 * Construct a trail setup result message and forward it to a friend.
889 * @param destination_peer Peer which will get the trail to one of its finger.
890 * @param source_finger Peer to which the trail has been setup to.
891 * @param target_friend Friend to which this message should be forwarded.
892 * @param trail_length Numbers of peers in the trail.
893 * @param trail_peer_list Peers which are part of the trail from source to destination.
894 * @param finger_map_index Index in finger peer map
897 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destination_peer,
898 const struct GNUNET_PeerIdentity *source_finger,
899 struct FriendInfo *target_friend,
900 unsigned int trail_length,
901 const struct GNUNET_PeerIdentity *trail_peer_list,
902 unsigned int finger_map_index)
904 struct P2PPendingMessage *pending;
905 struct PeerTrailSetupResultMessage *tsrm;
906 struct GNUNET_PeerIdentity *peer_list;
909 msize = sizeof (struct PeerTrailSetupResultMessage) +
910 (trail_length * sizeof (struct GNUNET_PeerIdentity));
912 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
918 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
920 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
924 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
925 pending->importance = 0;
926 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
927 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
928 pending->msg = &tsrm->header;
929 tsrm->header.size = htons (msize);
930 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
931 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
932 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
933 tsrm->trail_length = htonl (trail_length);
934 tsrm->finger_map_index = htonl (finger_map_index);
935 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
936 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
938 /* Send the message to chosen friend. */
939 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
940 target_friend->pending_count++;
941 process_friend_queue (target_friend);
946 * Construct a PeerVerifySuccessor message and send it to friend.
947 * @param source_peer Peer which wants to verify its successor
948 * @param successor Peer which is our current successor
949 * @param target_friend Friend to which this message should be forwarded.
950 * @param trail_peer_list Peer which are part of trail from source to destination
951 * @param trail_length Number of peers in the trail list.
953 void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *source_peer,
954 const struct GNUNET_PeerIdentity *successor,
955 struct FriendInfo *target_friend,
956 const struct GNUNET_PeerIdentity *trail_peer_list,
957 unsigned int trail_length)
959 struct PeerVerifySuccessorMessage *vsm;
960 struct P2PPendingMessage *pending;
961 struct GNUNET_PeerIdentity *peer_list;
964 msize = sizeof (struct PeerVerifySuccessorMessage) +
965 (trail_length * sizeof (struct GNUNET_PeerIdentity));
967 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
973 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
975 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
979 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
980 pending->importance = 0; /* FIXME */
981 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
982 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
983 pending->msg = &vsm->header;
984 vsm->header.size = htons (msize);
985 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
986 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
987 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
988 vsm->trail_length = htonl (trail_length);
989 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
990 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
992 /* Send the message to chosen friend. */
993 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
994 target_friend->pending_count++;
995 process_friend_queue (target_friend);
1001 * Construct a PeerVerifySuccessorResult message and send it to friend.
1002 * @param destination_peer Peer which sent verify successor message
1003 * @param source_successor Peer to which verify successor message was sent.
1004 * @param my_predecessor source_successor's predecessor.
1005 * @param target_friend Friend to which this message should be forwarded.
1006 * @param trail_peer_list Peers which are part of trail from source to destination
1007 * @param trail_length Number of peers in the trail list.
1009 void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *destination_peer,
1010 const struct GNUNET_PeerIdentity *source_successor,
1011 const struct GNUNET_PeerIdentity *my_predecessor,
1012 struct FriendInfo *target_friend,
1013 const struct GNUNET_PeerIdentity *trail_peer_list,
1014 unsigned int trail_length)
1016 struct PeerVerifySuccessorResultMessage *vsmr;
1017 struct P2PPendingMessage *pending;
1018 struct GNUNET_PeerIdentity *peer_list;
1021 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1022 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1024 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1031 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1033 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1037 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1038 pending->importance = 0; /* FIXME */
1039 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1040 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1041 pending->msg = &vsmr->header;
1042 vsmr->header.size = htons (msize);
1043 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1044 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1045 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1046 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1047 vsmr->trail_length = htonl (trail_length);
1048 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1049 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1051 /* Send the message to chosen friend. */
1052 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1053 target_friend->pending_count++;
1054 process_friend_queue (target_friend);
1059 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1060 * @param source_peer Peer which is sending notify message to its new successor.
1061 * @param destination_peer Peer which is the new destination.
1062 * @param target_friend Next friend to pass this message to.
1063 * @param peer_list List of peers in the trail to reach to destination_peer.
1064 * @param trail_length Total number of peers in peer list
1067 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1068 const struct GNUNET_PeerIdentity *destination_peer,
1069 struct FriendInfo *target_friend,
1070 const struct GNUNET_PeerIdentity *trail_peer_list,
1071 unsigned int trail_length)
1073 struct PeerNotifyNewSuccessorMessage *nsm;
1074 struct P2PPendingMessage *pending;
1075 struct GNUNET_PeerIdentity *peer_list;
1078 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1079 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1081 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1087 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1089 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1093 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1094 pending->importance = 0; /* FIXME */
1095 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1096 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1097 pending->msg = &nsm->header;
1098 nsm->header.size = htons (msize);
1099 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1100 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1101 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1102 nsm->trail_length = htonl (trail_length);
1104 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1105 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1107 /* Send the message to chosen friend. */
1108 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1109 target_friend->pending_count++;
1110 process_friend_queue (target_friend);
1115 * FIXME: Optimizaiton Once the basic code is running. Add the optimization
1116 * where you check if the threshold on number of links that should go through
1117 * a particular friend has crossed. If yes then again choose a different
1118 * friend. Important that the new friend chosen should be different. How to
1119 * ensure this? This is an important optimization as without this one x-vine
1120 * is actually not a sybil tolerant DHT.
1121 * Randomly choose one of your friends from the friends_peer map
1124 static struct FriendInfo *
1125 select_random_friend (struct GNUNET_PeerIdentity *congested_peer)
1127 unsigned int current_size;
1128 unsigned int *index;
1130 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1131 struct GNUNET_PeerIdentity key_ret;
1132 struct FriendInfo *friend;
1134 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1135 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1136 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1138 if (GNUNET_CONTAINER_multipeermap_size (friend_peermap) == 0)
1140 /* FIXME: It may happen that there is not friend in friend peermap but
1141 as this task has already been started it failed.*/
1147 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1155 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1157 /* TODO: Here you have chosen a random friend. Now you should check the size
1158 of its routing table size, and if its more than threshold, then check which
1159 of the entries has trail length greater than trail length threshold. we
1160 should without checking the routing table size also we should check the
1161 trail with trail length greater than threshold. then
1162 you should try to find a new route through this new node that has joined in
1163 only for those finger entries whose trail length is greater than threshold.
1164 But I don't want the new node to wait for this process to get over. so
1165 should i declare a function which will be called after some interval.*/
1174 * FIMXE: pass current_finger_index as argument.
1175 * Compute finger_identity to which we want to setup the trail
1176 * @return finger_identity
1179 compute_finger_identity()
1183 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1184 my_id64 = GNUNET_ntohll (my_id64);
1185 /*FIXME: Do we need a mod finger = ((my_id + pow(2, finger_index)) mod (pow (2, MAX_FINGERS))*/
1186 return (my_id64 + (unsigned long) pow (2, current_finger_index));
1191 * Compute immediate predecessor identity in the network.
1192 * @return peer identity of immediate predecessor.
1195 compute_predecessor_identity()
1199 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1200 my_id64 = GNUNET_ntohll (my_id64);
1201 return (my_id64 -1);
1206 * Periodically ping your successor to ask its current predecessor
1208 * @param cls closure for this task
1209 * @param tc the context under which the task is running
1212 send_verify_successor_message (void *cls,
1213 const struct GNUNET_SCHEDULER_TaskContext *tc )
1215 struct GNUNET_TIME_Relative next_send_time;
1216 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1217 struct GNUNET_PeerIdentity key_ret;
1218 struct FriendInfo *target_friend;
1219 struct GNUNET_PeerIdentity *next_hop;
1220 struct GNUNET_PeerIdentity *peer_list;
1221 struct FingerInfo *finger;
1222 unsigned int finger_index;
1226 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1227 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1229 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1230 (const void **)&finger))
1232 if (0 == finger->finger_map_index)
1239 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1242 goto send_new_request;
1244 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->trail_length);
1246 struct TrailPeerList *iterate;
1247 iterate = finger->head;
1249 while ( i < (finger->trail_length))
1251 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1252 iterate = iterate->next;
1256 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1257 memcpy (next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1258 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1260 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1261 &(finger->finger_identity),
1264 finger->trail_length);
1267 /* FIXME: Understand what this function is actually doing here. */
1269 next_send_time.rel_value_us =
1270 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1271 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1272 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1275 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1281 * FIXME - the main logic of handling the finger map index has changed.
1282 * first we start with finger index = 64, that index is reserved for the
1283 * predecessor always. Then we start going backwards, finger_index = 63 to 0
1284 * and once its 0 we again go back to 64. now, when you start looking for the finger
1285 * then your successor is always the finger with lowest finger index. in finger_table_add
1286 * whenever you do an entry you check for predecessor , if the new finger identity
1287 * is greater than existing one, then that should be your predecessor. In case of
1288 * other fingers also, if the new entry is smaller than existing one. If yes
1289 * then that is correct finger for that finger index. Also, the lowest finger index and
1290 * its corresponding finger identity is your successor.
1292 * Choose a random friend and start looking for the trail to reach to
1293 * finger identity through this random friend.
1295 * @param cls closure for this task
1296 * @param tc the context under which the task is running
1299 send_find_finger_trail_message (void *cls,
1300 const struct GNUNET_SCHEDULER_TaskContext *tc)
1302 struct FriendInfo *target_friend;
1303 struct GNUNET_TIME_Relative next_send_time;
1304 uint64_t finger_identity;
1305 unsigned int finger_map_index;
1307 /* FIXME: understand how does this scheduling of processes take place? */
1308 next_send_time.rel_value_us =
1309 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1310 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1311 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1312 /* FIXME: here we are just adding the process to the scheduling list. only
1313 when this function is executed, it may get scheduled. */
1314 find_finger_trail_task =
1315 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1317 target_friend = select_random_friend (NULL);
1319 if (NULL == target_friend)
1321 /* SUPU: Here we can get NULL in the case there is no friend in the peer map
1322 or all of the friends have reached their threshold. The first case should ideally
1323 never happen because in handle_core_disconnect we have already canceled the task
1324 but it may happen if we already started the process and we reached here and
1325 we cancelled the next task. So, it can return NULL in that case also. Should
1326 we handle both cases in same way or not? */
1330 /* FIXME: start with current_finger_index = 64, */
1331 if (PREDECESSOR_FINGER_ID == current_finger_index)
1333 /* FIXME: Where do we set the value back to PREDECESSR_FINGER_ID? Only
1334 when current_finger_index = 0, do we set it back to PREDECESSOR_FINGER_ID,
1335 in finger_table_add? Or is there any other possible condition, where we
1336 may need to set it to PREDECESSOR_FINGER_ID*/
1337 finger_identity = compute_predecessor_identity();
1341 finger_identity = compute_finger_identity();
1343 finger_map_index = current_finger_index;
1345 /* FIXME: verify if its correct to set current_destination and current_source
1347 GDS_NEIGHBOURS_send_trail_setup (&my_identity, finger_identity, &(target_friend->id),
1348 &(target_friend->id), target_friend, 0, NULL, finger_map_index);
1354 * @param destination_peer
1355 * @param existing_trail
1356 * @param trail_length
1359 static struct GNUNET_PeerIdentity *
1360 invert_trail_list (struct GNUNET_PeerIdentity *destination_peer,
1361 struct GNUNET_PeerIdentity *existing_trail,
1362 unsigned int trail_length)
1366 struct GNUNET_PeerIdentity *new_trail;
1369 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
1371 if (trail_length > 1)
1373 i = trail_length - 2;
1376 memcpy( &new_trail[j], &existing_trail[i], sizeof (struct GNUNET_PeerIdentity));
1381 memcpy (&new_trail[j], destination_peer, sizeof(struct GNUNET_PeerIdentity));
1390 * @param existing_finger
1395 compare_finger_identity (struct GNUNET_PeerIdentity *existing_finger,
1396 struct GNUNET_PeerIdentity *new_finger)
1399 ret = (existing_finger > new_finger) ? 1 :
1400 (existing_finger == new_finger) ? 0 : -1;
1407 * Check if there is a predecessor in our finger peer map or not.
1408 * If no, then return GNUNET_YES
1409 * else compare existing predecessor and peer, and find the correct
1411 * @param existing_predecessor
1412 * @param new_predecessor
1413 * @return #GNUNET_YES if new peer is predecessor
1414 * #GNUNET_NO if new peer is not the predecessor.
1417 compare_predecessor(struct GNUNET_PeerIdentity *peer)
1419 /* FIXME: here you should first check if you already have an entry in the
1420 finger peer map for finger index = 64, if yes then compare it with peer
1421 if not then just add the peer. */
1429 static struct GNUNET_PeerIdentity *
1430 check_for_successor ()
1435 * Scan the trail, check if there is a friend in the trail, then shortcut
1436 * the trail and return the new trail and trail length.
1437 * FIXME: How to send the trail length? Should I create a new array and copy into
1438 * it or modify the existing trail. also, how can it be done optimally?
1439 * @param finger_trail
1443 static struct GNUNET_PeerIdentity *
1444 scan_trail (struct GNUNET_PeerIdentity *finger_trail)
1451 * Add an entry in finger table. Before adding, check if there is already an
1452 * entry in finger peermap for the same index, if yes then choose the closest one.
1453 * In case both the existing identity and new identity are same, keep both the trail
1454 * only if the trails are different (Redundant routing). Also, a peer stored at index,i
1455 * if its same as peer stored index, i+1, and 'i' is the lowest finger map index
1456 * seen so far, then that peer is the successor. In case finger_map_index is PREDECESSOR_INDEX,
1457 * then simply add it as handle rest of the cases for it in a different function.
1458 * Also while adding an entry check the trail, scan the trail and check if there
1459 * is a friend in between, then shortcut the path.
1460 * @param finger_identity
1461 * @param finger_trail
1462 * @param finger_trail_length
1463 * @param finger_map_index
1466 void finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
1467 const struct GNUNET_PeerIdentity *finger_trail,
1468 uint32_t finger_trail_length,
1469 uint32_t finger_map_index)
1471 struct FingerInfo new_finger_entry;
1474 /* If I am my own finger, then return. */
1475 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, finger_identity))
1477 GNUNET_break (0); /* SUPU: Its here because I need to see when it happens. */
1481 if (finger_map_index == PREDECESSOR_FINGER_ID)
1484 /* For rest of current_finger_index, choose the correct finger and correct trail. */
1485 /* SUPU: Here I want to iterate over all the entries and see if there is already
1486 an entry for the finger map index. if yes then check if finger identity are same
1487 if yes then check the trail. if I use gnuent_container_multipeermap_iterate,
1488 i should stop after I found the finger map index, and just return the
1489 struct finger info. then I should call another function which takes care of
1490 finding the closest peer*/
1493 memcpy (&(new_finger_entry.finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
1494 new_finger_entry.finger_map_index = finger_map_index;
1495 /* FIXME: How do I get the length as well as the trail.
1496 * scan_trail (finger_trail);
1498 new_finger_entry.trail_length = finger_trail_length;
1501 while (i < finger_trail_length)
1503 struct TrailPeerList *element;
1504 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1505 element->next = NULL;
1506 element->prev = NULL;
1508 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
1509 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry.head, new_finger_entry.tail, element);
1513 GNUNET_assert (GNUNET_OK ==
1514 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1515 &(new_finger_entry.finger_identity),
1517 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
1519 /* FIXME: after adding an entry, I want to check if there is a successor, if yes
1520 then this function will return it and then we should schedule a verify successor
1522 if (NULL != check_for_successor())
1524 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1525 /* FIXME: Is it safe to set the finger index to predecessor_finger_id here? */
1526 current_finger_index = PREDECESSOR_FINGER_ID;
1530 /* FIXME: Not sure if this is the correct place to set the values. Look into
1531 send_find_finger_trail_message and check. */
1532 if(current_finger_index == 0)
1533 current_finger_index = PREDECESSOR_FINGER_ID;
1535 current_finger_index = current_finger_index - 1;
1540 /*FIXME: Here you need to set the correct value of finger_map_index,
1541 * in case it is 0, then you set it back to 64, and in case it is x,
1542 * then you set it back to x-1. current_finger_index = ( current_finger_index - 1) % MAX_FINGERS
1543 * we also need to change the logic of starting the process to look for a successor.
1544 * when you add an entry then go through whole trail and check if there is an entry
1545 * which is your friend, if yes then just collapse the trail. if you are not doing it
1546 * here then you need to do it in handle_core_disconnect where you will have to search
1547 * through whole trail find peer and then delete the finger.
1548 * Add an entry in finger table.
1549 * @param finger_identity Peer identity of finger
1550 * @param finger_trail Trail to reach the finger
1551 * @param trail_length Number of peers in the trail.
1552 * @param finger_map_index Index in finger peer map.
1555 void finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
1556 const struct GNUNET_PeerIdentity *finger_trail,
1557 unsigned int trail_length,
1558 const unsigned int finger_map_index)
1560 struct FingerInfo *new_finger_entry;
1561 //struct GNUNET_PeerIdentity key_ret;
1563 //struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1564 //struct FingerInfo *existing_finger;
1567 /* SUPU Here we trying to check if we already have an entry. If yes then we
1568 can keep two trails for redundant routing. if they are different then we
1569 need to choose the closest one. and remove the other one. */
1571 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1573 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1575 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1576 (const void **)&existing_finger))
1578 if ((finger_map_index == existing_finger->finger_map_index))
1580 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),finger_identity))
1582 /* FIXME: Here you should check if the trail is same. If yes then don't add the entry. it
1583 seems to be very suboptimal. */
1584 if ((existing_finger->trail_length) == trail_length)
1586 struct TrailPeerList *iterate;
1587 iterate = existing_finger->head;
1590 while (k < trail_length)
1592 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(iterate->peer), &finger_trail[k]))
1595 iterate = iterate->next;
1598 if (k == trail_length)
1608 if (finger_map_index == 1)
1610 ret = compare_predecessor (&(existing_finger->finger_identity),
1616 ret = compare_finger_identity (&(existing_finger->finger_identity),
1621 GNUNET_assert (GNUNET_YES ==
1622 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
1623 &(existing_finger->finger_identity),
1638 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
1639 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
1640 new_finger_entry->finger_map_index = finger_map_index;
1642 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, finger_identity))
1644 /* I am the finger */
1645 new_finger_entry->trail_length = 0;
1646 /* FIXME: If I am the finger then why do we even do an entry. don't add any
1647 * field because it is of no use. you may just send a message to yourself
1648 * when another peer send you a trail setup or put request. */
1653 while (i < trail_length)
1655 struct TrailPeerList *element;
1656 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1657 element->next = NULL;
1658 element->prev = NULL;
1660 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
1661 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
1664 new_finger_entry->trail_length = trail_length;
1667 /* FIXME: Here we are keeping multiple hashmap option so that there are
1668 multiple routes to reach to same finger, redundant routing.
1669 * Also same peers could be our fingers for different finger map index
1670 * Should we handle the case where we have same fingers at the different
1671 * finger index but with different trail to reach. */
1672 GNUNET_assert (GNUNET_OK ==
1673 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1674 &(new_finger_entry->finger_identity),
1676 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
1678 if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap)
1679 && (new_finger_entry->finger_map_index!= 1))
1681 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1687 * Compare two peer identities.
1688 * @param p1 Peer identity
1689 * @param p2 Peer identity
1690 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
1693 compare_peer_id (const void *p1, const void *p2)
1695 struct Sorting_List *p11;
1696 struct Sorting_List *p22;
1698 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
1699 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
1700 p11 = (struct Sorting_List *)p1;
1701 p22 = (struct Sorting_List *)p2;
1702 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
1703 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
1709 * Return the successor of value in all_known_peers.
1710 * @param all_known_peers list of all the peers
1711 * @param value value we have to search in the all_known_peers.
1714 static struct Sorting_List *
1715 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
1724 middle = (first + last)/2;
1726 while(first <= last)
1728 if(all_known_peers[middle].peer_id < value)
1732 else if(all_known_peers[middle].peer_id == value)
1734 if(middle == (size -1))
1736 return &all_known_peers[0];
1740 return &all_known_peers[middle+1];
1748 middle = (first + last)/2;
1755 * here you should set the current source instead of destination type.
1756 * so current_source is actual source till we don't find another current_source
1757 * but is it good. why are we wasting space in case current_Destination is just us.
1758 * also in many case current_destination is just me. so again it does not seem
1760 * Find closest successor for the value.
1761 * @param value Value for which we are looking for successor
1762 * FIXME: pass the correct value for current_destination
1763 * @param[out] current_destination set to the end of the finger to traverse next
1764 * @param type Next destination type
1765 * @return Peer identity of next hop, NULL if we are the
1766 * ultimate destination
1768 static struct GNUNET_PeerIdentity *
1769 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
1770 struct GNUNET_PeerIdentity *current_source)
1772 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1773 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1774 struct GNUNET_PeerIdentity key_ret;
1775 struct FriendInfo *friend;
1776 struct FingerInfo *finger;
1777 unsigned int finger_index;
1778 unsigned int friend_index;
1779 struct Sorting_List *successor;
1783 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
1784 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
1785 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
1788 struct Sorting_List all_known_peers[size];
1791 for (k = 0; k < size; k++)
1792 all_known_peers[k].peer_id = 0;
1794 /* Copy your identity at 0th index in all_known_peers. */
1796 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
1797 all_known_peers[j].type = MY_ID;
1798 all_known_peers[j].data = 0;
1802 all_known_peers[j].peer_id = value;
1803 all_known_peers[j].type = VALUE;
1804 all_known_peers[j].data = 0;
1807 /* Iterate over friend peer map and copy all the elements into array. */
1808 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1809 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1811 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1813 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
1814 all_known_peers[j].type = FRIEND;
1815 all_known_peers[j].data = friend;
1820 /* Iterate over finger map and copy all the entries into all_known_peers array. */
1821 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1822 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1824 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1826 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
1827 all_known_peers[j].type = FINGER;
1828 all_known_peers[j].data = finger;
1833 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1834 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
1836 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
1838 /* search value in all_known_peers array. */
1839 successor = find_closest_successor (all_known_peers, value, size);
1841 if (successor->type == MY_ID)
1845 else if (successor->type == FRIEND)
1847 struct FriendInfo *target_friend;
1848 target_friend = (struct FriendInfo *)successor->data;
1849 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1850 return current_destination;
1852 else if (successor->type == FINGER)
1854 struct GNUNET_PeerIdentity *next_hop;
1855 struct FingerInfo *finger;
1856 struct TrailPeerList *iterator;
1857 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
1858 finger = successor->data;
1859 iterator = finger->head;
1860 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1861 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
1862 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1863 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
1874 /** FIXME: by default I keep current_source, and destination as my own id.
1875 * in case we find a finger then we update current_source in the
1876 * find_successor message.
1877 * Construct a Put message and send it to target_peer.
1878 * @param key Key for the content
1879 * @param data Content to store
1880 * @param data_size Size of content @a data in bytes
1881 * @param block_type Type of the block
1882 * @param options Routing options
1883 * @param desired_replication_level Desired replication count
1884 * @param expiration_time When does the content expire
1885 * @param current_destination
1886 * @param current_source
1887 * @param target_peer Peer to which this message will be forwarded.
1888 * @param hop_count Number of hops traversed so far.
1889 * @param put_path_length Total number of peers in @a put_path
1890 * @param put_path Number of peers traversed so far
1893 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
1894 const void *data, size_t data_size,
1895 enum GNUNET_BLOCK_Type block_type,
1896 enum GNUNET_DHT_RouteOption options,
1897 uint32_t desired_replication_level,
1898 struct GNUNET_TIME_Absolute expiration_time,
1899 struct GNUNET_PeerIdentity *current_destination,
1900 struct GNUNET_PeerIdentity *current_source,
1901 struct GNUNET_PeerIdentity *target_peer,
1903 uint32_t put_path_length,
1904 struct GNUNET_PeerIdentity *put_path)
1906 struct PeerPutMessage *ppm;
1907 struct P2PPendingMessage *pending;
1908 struct FriendInfo *target_friend;
1909 struct GNUNET_PeerIdentity *pp;
1912 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
1913 sizeof (struct PeerPutMessage);
1915 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1917 put_path_length = 0;
1918 msize = data_size + sizeof (struct PeerPutMessage);
1921 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1927 /* This is the first call made from clients file. So, we should search for the
1929 if (NULL == target_peer)
1932 struct GNUNET_PeerIdentity *next_hop;
1934 memcpy (&key_value, key, sizeof (uint64_t));
1935 next_hop = find_successor (key_value, current_destination, current_source);
1936 if (NULL == next_hop) /* I am the destination do datacache_put */
1938 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
1939 block_type, data_size, data);
1943 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1946 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1947 pending->timeout = expiration_time;
1948 ppm = (struct PeerPutMessage *) &pending[1];
1949 pending->msg = &ppm->header;
1950 ppm->header.size = htons (msize);
1951 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
1952 ppm->options = htonl (options);
1953 ppm->block_type = htonl (block_type);
1954 ppm->hop_count = htonl (hop_count + 1);
1955 ppm->desired_replication_level = htonl (desired_replication_level);
1956 ppm->put_path_length = htonl (put_path_length);
1957 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1959 ppm->current_destination = *current_destination;
1960 ppm->current_source = *current_source;
1962 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
1963 if (put_path_length != 0)
1965 memcpy (pp, put_path,
1966 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
1968 memcpy (&pp[put_path_length], data, data_size);
1969 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1970 target_friend->pending_count++;
1971 process_friend_queue (target_friend);
1976 /** FIXME: by default I keep current_source, and destination as my own id.
1977 * in case we find a finger then we update current_source in the
1978 * find_successor message.
1979 * Construct a Get message and send it to target_peer.
1980 * @param key Key for the content
1981 * @param block_type Type of the block
1982 * @param options Routing options
1983 * @param desired_replication_level Desired replication count
1984 * @param expiration_time When does the content expire
1985 * @param current_destination
1986 * @param current_source
1987 * @param target_peer Peer to which this message will be forwarded.
1988 * @param hop_count Number of hops traversed so far.
1989 * @param put_path_length Total number of peers in @a put_path
1990 * @param put_path Number of peers traversed so far
1993 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
1994 enum GNUNET_BLOCK_Type block_type,
1995 enum GNUNET_DHT_RouteOption options,
1996 uint32_t desired_replication_level,
1997 struct GNUNET_PeerIdentity *current_destination,
1998 struct GNUNET_PeerIdentity *current_source,
1999 struct GNUNET_PeerIdentity *target_peer,
2001 uint32_t get_path_length,
2002 struct GNUNET_PeerIdentity *get_path)
2004 struct PeerGetMessage *pgm;
2005 struct P2PPendingMessage *pending;
2006 struct FriendInfo *target_friend;
2007 struct GNUNET_PeerIdentity *gp;
2010 msize = sizeof (struct PeerGetMessage) +
2011 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2013 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2019 if (NULL == target_peer)
2021 /* This is the first call from client file, we need to search for next_hop*/
2022 struct GNUNET_PeerIdentity *next_hop;
2025 memcpy (&key_value, key, sizeof (struct GNUNET_PeerIdentity));
2026 next_hop = find_successor (key_value, current_destination, current_source);
2027 if (NULL == next_hop) /* I am the destination do datacache_put */
2029 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2030 NULL, 0, 1, &my_identity, NULL,&my_identity);
2034 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2038 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2039 pending->importance = 0; /* FIXME */
2040 pgm = (struct PeerGetMessage *) &pending[1];
2041 pending->msg = &pgm->header;
2042 pgm->header.size = htons (msize);
2043 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2044 pgm->get_path_length = htonl (get_path_length);
2046 pgm->current_destination = *current_destination;
2047 pgm->current_source = *current_source;
2048 pgm->hop_count = htonl (hop_count + 1);
2050 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2051 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2052 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2053 target_friend->pending_count++;
2054 process_friend_queue (target_friend);
2059 * Send the get result to requesting client.
2060 * @param expiration When will this result expire?
2061 * @param key Key of the requested data.
2062 * @param put_path_length Number of peers in @a put_path
2063 * @param put_path Path taken to put the data at its stored location.
2064 * @param type Block type
2065 * @param data_size Size of the @a data
2066 * @param data Payload to store
2067 * @param get_path Path taken to reach to the location of the key.
2068 * @param get_path_length Number of peers in @a get_path
2069 * @param next_hop Next peer to forward the message to.
2070 * @param source_peer Peer which has the data for the key.
2073 GDS_NEIGHBOURS_send_get_result (struct GNUNET_TIME_Absolute expiration,
2074 const struct GNUNET_HashCode *key,
2075 unsigned int put_path_length,
2076 const struct GNUNET_PeerIdentity *put_path,
2077 enum GNUNET_BLOCK_Type type, size_t data_size,
2079 struct GNUNET_PeerIdentity *get_path,
2080 unsigned int get_path_length,
2081 struct GNUNET_PeerIdentity *next_hop,
2082 struct GNUNET_PeerIdentity *source_peer)
2084 struct PeerGetResultMessage *get_result;
2085 struct GNUNET_PeerIdentity *get_result_path;
2086 struct GNUNET_PeerIdentity *pp;
2087 struct P2PPendingMessage *pending;
2088 struct FriendInfo *target_friend;
2089 int current_path_index;
2092 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2093 sizeof (struct PeerPutMessage);
2095 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2101 current_path_index = search_my_index(get_path);
2102 if (0 == current_path_index)
2104 FPRINTF (stderr,_("\nSUPU %s, %s, %d"),__FILE__, __func__,__LINE__);
2105 GDS_CLIENTS_handle_reply (expiration, key, get_path_length, get_path, put_path_length,
2106 put_path, type, data_size, data);
2109 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2110 pending->importance = 0;
2111 get_result = (struct PeerGetResultMessage *)&pending[1];
2112 pending->msg = &get_result->header;
2113 get_result->header.size = htons (msize);
2114 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2115 get_result->key = *key;
2116 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2117 get_result->expiration_time = expiration;
2119 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2120 memcpy (get_result_path, get_path,
2121 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2122 memcpy (&get_result_path[get_path_length], data, data_size);
2123 /* FIXME: Is this correct? */
2124 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2125 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2127 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2128 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2129 target_friend->pending_count++;
2130 process_friend_queue (target_friend);
2135 * Send tral rejection message
2136 * @param source_peer Source peer which wants to set up the trail.
2137 * @param finger_identity Finger identity to which it want to setup the trail.
2138 * @param congested_peer Peer which has send trail rejection message
2139 * @param next_hop Peer to which this message should be forwarded.
2140 * @param finger_map_index
2141 * @param trail_peer_list
2142 * @param trail_length
2145 GDS_NEIGHBOURS_send_trail_rejection_message(struct GNUNET_PeerIdentity *source_peer,
2146 uint64_t finger_identity,
2147 struct GNUNET_PeerIdentity *congested_peer,
2148 const struct GNUNET_PeerIdentity *next_hop,
2149 unsigned int finger_map_index,
2150 struct GNUNET_PeerIdentity *trail_peer_list,
2151 unsigned int trail_length)
2153 struct PeerTrailRejectionMessage *trail_rejection;
2154 struct GNUNET_PeerIdentity *trail_list;
2155 struct P2PPendingMessage *pending;
2156 struct FriendInfo *target_friend;
2159 msize = sizeof (struct PeerTrailRejectionMessage);
2161 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2162 pending->importance = 0; /* FIXME */
2163 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2164 trail_rejection = (struct PeerTrailRejectionMessage *) &pending[1];
2165 pending->msg = &trail_rejection->header;
2166 trail_rejection->header.size = htons (msize);
2167 trail_rejection->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
2168 memcpy (&(trail_rejection->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2169 memcpy (&(trail_rejection->congested_peer), congested_peer, sizeof (struct GNUNET_PeerIdentity));
2170 memcpy (&(trail_rejection->finger_identity), &finger_identity, sizeof (uint64_t));
2171 trail_rejection->finger_map_index = htonl(finger_map_index);
2172 trail_rejection->trail_length = htonl (trail_length);
2174 trail_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2175 memcpy (trail_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2177 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2178 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2179 target_friend->pending_count++;
2180 process_friend_queue (target_friend);
2192 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2193 const struct GNUNET_MessageHeader *message)
2195 struct PeerPutMessage *put;
2196 struct GNUNET_PeerIdentity *put_path;
2197 struct GNUNET_HashCode test_key;
2198 enum GNUNET_DHT_RouteOption options;
2199 struct GNUNET_PeerIdentity current_destination;
2200 struct GNUNET_PeerIdentity current_source;
2201 struct GNUNET_PeerIdentity *next_hop;
2205 size_t payload_size;
2208 msize = ntohs (message->size);
2209 if (msize < sizeof (struct PeerPutMessage))
2211 GNUNET_break_op (0);
2215 put = (struct PeerPutMessage *) message;
2216 putlen = ntohl (put->put_path_length);
2219 sizeof (struct PeerPutMessage) +
2220 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2222 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2224 GNUNET_break_op (0);
2228 current_destination = put->current_destination;
2229 current_source = put->current_source;
2230 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2231 payload = &put_path[putlen];
2232 options = ntohl (put->options);
2233 payload_size = msize - (sizeof (struct PeerPutMessage) +
2234 putlen * sizeof (struct GNUNET_PeerIdentity));
2236 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
2237 payload, payload_size, &test_key))
2240 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
2242 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
2243 GNUNET_break_op (0);
2244 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2245 "PUT with key `%s' for block with key %s\n",
2246 put_s, GNUNET_h2s_full (&test_key));
2247 GNUNET_free (put_s);
2252 GNUNET_break_op (0);
2255 /* cannot verify, good luck */
2259 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
2261 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
2262 ntohl (put->block_type),
2264 NULL, 0, /* bloom filer */
2265 NULL, 0, /* xquery */
2266 payload, payload_size))
2268 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2269 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2272 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2273 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2274 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
2275 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2276 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2277 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2279 GNUNET_break_op (0);
2284 struct GNUNET_PeerIdentity pp[putlen + 1];
2285 /* extend 'put path' by sender */
2286 /* FIXME: Check what are we doing here? */
2287 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
2289 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
2296 memcpy (&key_value, &(put->key), sizeof (uint64_t));
2297 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2299 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2300 if (next_hop == NULL)
2302 /* refer to handle_dht_p2p_trail_setup. */
2307 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2310 if (NULL == next_hop) /* I am the final destination */
2312 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
2313 &(put->key),putlen, pp, ntohl (put->block_type),
2314 payload_size, payload);
2319 GDS_CLIENTS_process_put (options,
2320 ntohl (put->block_type),
2321 ntohl (put->hop_count),
2322 ntohl (put->desired_replication_level),
2324 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2329 GDS_NEIGHBOURS_send_put (&put->key, payload, payload_size,
2330 ntohl (put->block_type),ntohl (put->options),
2331 ntohl (put->desired_replication_level),
2332 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2333 ¤t_destination, ¤t_source, next_hop,
2334 ntohl (put->hop_count), putlen, pp);
2338 return GNUNET_SYSERR;
2343 * Core handler for p2p get requests.
2345 * @param cls closure
2346 * @param peer sender of the request
2347 * @param message message
2348 * @return #GNUNET_OK to keep the connection open,
2349 * #GNUNET_SYSERR to close it (signal serious error)
2352 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2353 const struct GNUNET_MessageHeader *message)
2355 struct PeerGetMessage *get;
2356 struct GNUNET_PeerIdentity *get_path;
2357 struct GNUNET_PeerIdentity current_destination;
2358 struct GNUNET_PeerIdentity current_source;
2359 struct GNUNET_PeerIdentity *next_hop;
2360 uint32_t get_length;
2364 msize = ntohs (message->size);
2365 if (msize < sizeof (struct PeerGetMessage))
2367 GNUNET_break_op (0);
2371 get = (struct PeerGetMessage *)message;
2372 get_length = ntohl (get->get_path_length);
2373 get_path = (struct GNUNET_PeerIdentity *)&get[1];
2374 current_destination = get->current_destination;
2375 current_source = get->current_source;
2378 sizeof (struct PeerGetMessage) +
2379 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
2381 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2383 GNUNET_break_op (0);
2387 /* Add sender to get path */
2388 struct GNUNET_PeerIdentity gp[get_length + 1];
2389 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
2390 gp[get_length + 1] = *peer;
2391 get_length = get_length + 1;
2393 memcpy (&key_value, &(get->key), sizeof (uint64_t));
2394 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2396 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2397 if (next_hop == NULL)
2399 /* refer to handle_dht_p2p_trail_setup. */
2404 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2407 if (NULL == next_hop)
2409 /* FIXME: Try to make this code also short and remove useless variables. */
2410 struct GNUNET_PeerIdentity final_get_path[get_length+1];
2411 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
2412 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
2413 get_length = get_length + 1;
2414 struct GNUNET_PeerIdentity *next_hop;
2415 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2416 memcpy (next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
2417 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
2418 get_length, final_get_path,next_hop, &my_identity);
2424 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
2425 get->desired_replication_level,¤t_destination,
2426 ¤t_source, next_hop, 0,
2429 return GNUNET_SYSERR;
2435 * Core handler for get result
2436 * @param cls closure
2437 * @param peer sender of the request
2438 * @param message message
2439 * @return #GNUNET_OK to keep the connection open,
2440 * #GNUNET_SYSERR to close it (signal serious error)
2443 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
2444 const struct GNUNET_MessageHeader *message)
2446 /* If you are the source, go back to the client file and there search for
2447 the requesting client and send back the result. */
2448 struct PeerGetResultMessage *get_result;
2449 struct GNUNET_PeerIdentity *get_path;
2450 struct GNUNET_PeerIdentity *put_path;
2452 size_t payload_size;
2454 unsigned int getlen;
2455 unsigned int putlen;
2456 int current_path_index;
2458 msize = ntohs (message->size);
2459 if (msize < sizeof (struct PeerGetResultMessage))
2461 GNUNET_break_op (0);
2465 get_result = (struct PeerGetResultMessage *)message;
2466 getlen = ntohl (get_result->get_path_length);
2467 putlen = ntohl (get_result->put_path_length);
2470 sizeof (struct PeerGetResultMessage) +
2471 getlen * sizeof (struct GNUNET_PeerIdentity) +
2472 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2474 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
2476 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
2478 GNUNET_break_op (0);
2482 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
2483 payload = &get_path[getlen];
2484 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
2485 getlen * sizeof (struct GNUNET_PeerIdentity));
2486 /* FIXME: Check if its correct or not. */
2488 put_path = &get_path[1];
2490 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
2492 //GDS_CLIENTS_process_get_result();
2493 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
2494 getlen, get_path, putlen,
2495 put_path, get_result->type, payload_size, payload);
2500 struct GNUNET_PeerIdentity *next_hop;
2501 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2502 current_path_index = search_my_index (get_path);
2503 /* FIXME: First check if you are adding yourself to the get path or not.
2504 if yes then don't check if current_path_index == 0, if not then check
2505 and next_hop == source_peer. */
2506 memcpy (next_hop, &get_path[current_path_index - 1], sizeof (struct GNUNET_PeerIdentity));
2508 GDS_NEIGHBOURS_send_get_result (get_result->expiration_time, &(get_result->key),
2510 get_result->type, payload_size,payload,
2512 next_hop, &(get_result->source_peer));
2515 return GNUNET_SYSERR;
2520 * Handle a PeerTrailSetupMessage.
2521 * @param cls closure
2522 * @param message message
2523 * @param peer peer identity this notification is about
2524 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2527 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
2528 const struct GNUNET_MessageHeader *message)
2530 const struct PeerTrailSetupMessage *trail_setup;
2531 struct GNUNET_PeerIdentity current_destination;
2532 struct GNUNET_PeerIdentity current_source;
2533 struct GNUNET_PeerIdentity source;
2534 struct GNUNET_PeerIdentity *next_hop;
2535 struct GNUNET_PeerIdentity next_peer;
2536 struct GNUNET_PeerIdentity *trail_peer_list;
2537 struct FriendInfo *target_friend;
2538 uint64_t destination_finger_value;
2539 uint32_t trail_length;
2540 uint32_t finger_map_index;
2543 msize = ntohs (message->size);
2544 if (msize < sizeof (struct PeerTrailSetupMessage))
2546 GNUNET_break_op (0);
2550 trail_setup = (const struct PeerTrailSetupMessage *) message;
2551 trail_length = ntohl (trail_setup->trail_length);
2553 if ((msize < sizeof (struct PeerTrailSetupMessage) +
2554 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2556 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2558 GNUNET_break_op (0);
2562 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
2563 current_destination = trail_setup->current_destination;
2564 current_source = trail_setup->current_source;
2565 source = trail_setup->source_peer;
2566 finger_map_index = ntohl (trail_setup->finger_map_index);
2567 destination_finger_value = ntohl (trail_setup->destination_finger);
2569 /* Check if you are part of the trail or current destination, and accordingly
2570 * find the next peer to send the message to. */
2571 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2573 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2574 /* OPTIMIZATION: do find_successor also and get a better path if possible. */
2575 if (next_hop == NULL)
2577 /* FIXME next_hop to NULL, 1. statistics update, drop the message.
2578 2. complain to sender with new message: trail lost */
2584 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
2587 /* Now add yourself to the trail. */
2588 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
2589 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2590 peer_list[trail_length] = my_identity;
2593 /* Check next_hop type and make the judgment what to do next. */
2594 if (NULL == next_hop) /* This means I am the final destination */
2596 if (trail_length == 1)
2598 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
2602 memcpy (&next_peer, &trail_peer_list[trail_length-2], sizeof (struct GNUNET_PeerIdentity));
2605 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
2606 /* FIXME: URGENT change it to handle the change in current_finger_index.
2607 compare to your own predecessor */
2608 if (compare_predecessor (&source) /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */)
2610 struct GNUNET_PeerIdentity *new_trail_list;
2611 new_trail_list = invert_trail_list (&source, peer_list, trail_length);
2612 finger_table_add (&source, new_trail_list, trail_length, PREDECESSOR_FINGER_ID);
2614 GDS_NEIGHBOURS_send_trail_setup_result (&source,
2616 target_friend, trail_length,
2623 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2624 GDS_NEIGHBOURS_send_trail_setup (&source,
2625 destination_finger_value,
2626 ¤t_destination, ¤t_source,
2627 target_friend, trail_length, peer_list,
2631 return GNUNET_SYSERR;
2636 * Core handle for p2p trail construction result messages.
2638 * @param message message
2639 * @param peer peer identity this notification is about
2640 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2643 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2644 const struct GNUNET_MessageHeader *message)
2646 const struct PeerTrailSetupResultMessage *trail_result;
2647 const struct GNUNET_PeerIdentity *trail_peer_list;
2648 uint32_t trail_length;
2649 uint32_t finger_map_index;
2652 msize = ntohs (message->size);
2653 if (msize < sizeof (struct PeerTrailSetupResultMessage))
2655 GNUNET_break_op (0);
2659 trail_result = (const struct PeerTrailSetupResultMessage *) message;
2660 trail_length = ntohl (trail_result->trail_length);
2663 sizeof (struct PeerTrailSetupResultMessage) +
2664 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2666 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2668 GNUNET_break_op (0);
2672 finger_map_index = htonl (trail_result->finger_map_index);
2673 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
2675 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2678 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
2684 struct GNUNET_PeerIdentity next_hop;
2685 struct FriendInfo *target_friend;
2688 my_index = search_my_index (trail_peer_list);
2691 next_hop = trail_result->destination_peer;
2694 next_hop = trail_peer_list[my_index - 1];
2696 /* Finger table of destination peer will not contain any trail for the case
2697 * where destination peer is its own finger identity. */
2698 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2699 &(trail_result->finger_identity))))
2701 GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
2705 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2706 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
2707 &(trail_result->finger_identity),
2708 target_friend, trail_length,
2713 return GNUNET_SYSERR;
2718 * FIXME: Use flag in the case finger peer map does not contain predcessor
2719 * then its NULL. Ideally it should never happen.
2720 * Get my current predecessor from the finger peer map
2721 * @return Current predecessor.
2723 static struct FingerInfo *
2726 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2727 struct GNUNET_PeerIdentity key_ret;
2728 unsigned int finger_index;
2729 struct FingerInfo *my_predecessor;
2731 /* Iterate over finger peer map and extract your predecessor. */
2732 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2733 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2735 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
2736 (finger_iter,&key_ret,(const void **)&my_predecessor))
2738 if(1 == my_predecessor->finger_map_index)
2744 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2745 return my_predecessor;
2750 * Core handle for p2p verify successor messages.
2751 * @param cls closure
2752 * @param message message
2753 * @param peer peer identity this notification is about
2754 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2757 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2758 const struct GNUNET_MessageHeader *message)
2760 const struct PeerVerifySuccessorMessage *vsm;
2761 const struct GNUNET_PeerIdentity *trail_peer_list;
2762 struct GNUNET_PeerIdentity next_hop;
2763 struct FriendInfo *target_friend;
2765 uint32_t trail_length;
2767 msize = ntohs (message->size);
2768 if (msize < sizeof (struct PeerVerifySuccessorMessage))
2770 GNUNET_break_op (0);
2774 vsm = (struct PeerVerifySuccessorMessage *) message;
2775 trail_length = ntohl (vsm->trail_length);
2777 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
2778 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2779 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2781 GNUNET_break_op (0);
2785 trail_peer_list = (const struct GNUNET_PeerIdentity *)&vsm[1];
2786 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
2788 /*FIXME:URGENT:IMPLEMENT Here you are the successor, here you should check your predecessor
2789 and if there is no predecessor then just add this peer and send result
2790 if there is some other predecessor, then construct a new trial and then
2791 send back the list to requesting peer. */
2797 my_index = search_my_index (trail_peer_list);
2798 memcpy (&next_hop, &trail_peer_list[my_index], sizeof (struct GNUNET_PeerIdentity));
2799 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2801 GDS_NEIGHBOURS_send_verify_successor (&(vsm->source_peer), &(vsm->successor),target_friend,
2802 trail_peer_list, trail_length);
2804 return GNUNET_SYSERR;
2809 * Core handle for p2p verify successor messages.
2810 * @param cls closure
2811 * @param message message
2812 * @param peer peer identity this notification is about
2813 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2816 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2817 const struct GNUNET_MessageHeader *message)
2819 struct PeerVerifySuccessorMessage *vsm;
2820 struct GNUNET_PeerIdentity *trail_peer_list;
2821 struct FriendInfo *target_friend;
2822 struct GNUNET_PeerIdentity *next_hop;
2823 struct GNUNET_PeerIdentity *source_peer;
2824 unsigned int trail_length;
2827 msize = ntohs (message->size);
2828 if (msize < sizeof (struct PeerVerifySuccessorMessage))
2830 GNUNET_break_op (0);
2834 vsm = (struct PeerVerifySuccessorMessage *) message;
2835 trail_length = ntohl (vsm->trail_length);
2837 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
2838 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2839 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2841 GNUNET_break_op (0);
2845 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
2846 source_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2847 memcpy (source_peer, &(vsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
2849 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2851 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
2853 struct FingerInfo *my_predecessor;
2854 if (trail_length == 1)
2855 memcpy (next_hop, source_peer, sizeof (struct GNUNET_PeerIdentity));
2858 int current_trail_index;
2859 current_trail_index = search_my_index (trail_peer_list);
2860 memcpy (next_hop, &trail_peer_list[current_trail_index-1], sizeof (struct GNUNET_PeerIdentity));
2862 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2863 GNUNET_free (next_hop);
2865 my_predecessor = get_predecessor();
2866 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (source_peer,
2867 &(my_predecessor->finger_identity))))
2869 GDS_NEIGHBOURS_send_verify_successor_result (source_peer,
2871 &(my_predecessor->finger_identity),
2878 struct GNUNET_PeerIdentity *new_successor_trail;
2879 int new_trail_length;
2882 new_trail_length = trail_length + my_predecessor->trail_length;
2883 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
2884 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
2885 struct TrailPeerList *iterator;
2886 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2887 iterator = my_predecessor->head;
2889 while (i < new_trail_length)
2891 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2892 iterator = iterator->next;
2896 GDS_NEIGHBOURS_send_verify_successor_result (source_peer,
2898 &(my_predecessor->finger_identity),
2900 new_successor_trail,
2907 unsigned int current_trail_index;
2908 current_trail_index = search_my_index (trail_peer_list);
2909 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2910 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2911 GNUNET_free (next_hop);
2913 GDS_NEIGHBOURS_send_verify_successor (source_peer, &(vsm->successor),target_friend,
2914 trail_peer_list, trail_length);
2921 * Core handle for p2p verify successor result messages.
2922 * @param cls closure
2923 * @param message message
2924 * @param peer peer identity this notification is about
2925 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2928 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2929 const struct GNUNET_MessageHeader *message)
2931 const struct PeerVerifySuccessorResultMessage *vsrm;
2932 const struct GNUNET_PeerIdentity *trail_peer_list;
2933 struct GNUNET_PeerIdentity next_hop;
2934 struct FriendInfo *target_friend;
2936 uint32_t trail_length;
2938 msize = ntohs (message->size);
2939 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
2941 GNUNET_break_op (0);
2945 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
2946 trail_length = ntohl (vsrm->trail_length);
2949 sizeof (struct PeerVerifySuccessorResultMessage) +
2950 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2952 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2954 GNUNET_break_op (0);
2958 trail_peer_list = (const struct GNUNET_PeerIdentity *) &vsrm[1];
2960 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity))))
2962 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
2964 finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0);
2965 memcpy (&next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
2966 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2967 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
2968 target_friend, trail_peer_list,
2977 my_index = search_my_index (trail_peer_list);
2979 memcpy (&next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
2981 memcpy (&next_hop, &trail_peer_list[my_index-1], sizeof (struct GNUNET_PeerIdentity));
2982 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2983 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
2984 &(vsrm->source_successor),
2985 &(vsrm->my_predecessor),
2991 return GNUNET_SYSERR;
2996 * Check if there is already an entry in finger_peermap for predecessor,
2997 * If not then add peer as your predecessor.
2998 * Else compare existing entry and peer, and choose the closest one as predecessor.
2999 * @param peer Peer identity
3000 * @param trail_peer_list Trail to reach from @a peer to me.
3003 update_predecessor (const struct GNUNET_PeerIdentity *peer,
3004 const struct GNUNET_PeerIdentity *trail_peer_list)
3006 /*FIXME: URGENT: Here you should first check if there is already an entry for predecessor
3007 field or not. if not then add peer. else compare existing entry and peer,
3008 and choose the closest one as predecessor. I am confused should I call a
3009 function which just checks if this peer can be predecessor or not, and then
3010 call another function to add it. Or call a single function which checks
3011 it all and add the entry. we are never going to communicate with the peer
3012 if it is my predecessor or not. so, we don't care about the result. */
3018 * Core handle for p2p notify new successor messages.
3019 * @param cls closure
3020 * @param message message
3021 * @param peer peer identity this notification is about
3022 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3025 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3026 const struct GNUNET_MessageHeader *message)
3028 const struct PeerNotifyNewSuccessorMessage *nsm;
3029 const struct GNUNET_PeerIdentity *trail_peer_list;
3031 uint32_t trail_length;
3033 msize = ntohs (message->size);
3034 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
3036 GNUNET_break_op (0);
3040 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
3041 trail_length = ntohl (nsm->trail_length);
3043 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3044 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3046 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3048 GNUNET_break_op (0);
3052 trail_peer_list = (const struct GNUNET_PeerIdentity *) &nsm[1];
3054 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), &my_identity)))
3056 update_predecessor (&(nsm->destination_peer), trail_peer_list);
3061 struct FriendInfo *target_friend;
3062 struct GNUNET_PeerIdentity next_hop;
3065 my_index = search_my_index (trail_peer_list);
3066 memcpy (&next_hop, &trail_peer_list[my_index+1], sizeof (struct GNUNET_PeerIdentity));
3067 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3068 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
3069 &(nsm->destination_peer),
3070 target_friend, trail_peer_list,
3074 return GNUNET_SYSERR;
3079 * FIXME: I am not sure if this is correct or not. once I am done with
3080 * basic implementation then will handle threshold limits.
3081 * Does it matter if the packet was going to a finger or friend?
3082 * Core handle for p2p trail rejection messages.
3083 * @param cls closure
3084 * @param message message
3085 * @param peer peer identity this notification is about
3086 * @return GNUNET_OK on success, GNUNET_SYSERR on error
3089 int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3090 const struct GNUNET_MessageHeader *message)
3092 struct PeerTrailRejectionMessage *trail_rejection;
3093 struct FailedTrail *trail_fail;
3094 struct FriendInfo *target_friend;
3095 struct GNUNET_PeerIdentity *trail_peer_list;
3096 unsigned int finger_map_index;
3099 msize = ntohs (message->size);
3100 if (msize < sizeof (struct PeerTrailRejectionMessage))
3102 GNUNET_break_op (0);
3106 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3107 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3108 finger_map_index = ntohl (trail_rejection->finger_map_index);
3109 trail_fail = GNUNET_malloc (sizeof (struct FailedTrail));
3110 memcpy (&(trail_fail->source_peer), &(trail_rejection->source_peer), sizeof (struct GNUNET_PeerIdentity));
3111 memcpy (&(trail_fail->congested_peer), &(trail_rejection->congested_peer), sizeof (struct GNUNET_PeerIdentity));
3112 memcpy (&(trail_fail->destination_finger_value), &(trail_rejection->finger_identity), sizeof (uint64_t));
3114 GNUNET_assert (GNUNET_OK ==
3115 GNUNET_CONTAINER_multipeermap_put (failed_trail_list, &(trail_fail->source_peer),
3116 trail_fail, GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
3118 /* FIXME: Is it okay if I pass the struct as parameter. */
3119 target_friend = select_random_friend (&(trail_fail->congested_peer));
3121 if(NULL != target_friend)
3123 GDS_NEIGHBOURS_send_trail_setup (&(trail_fail->source_peer),
3124 trail_fail->destination_finger_value,
3125 &(target_friend->id),
3126 NULL, target_friend, ntohl (trail_rejection->trail_length),
3131 return GNUNET_SYSERR;
3136 * FIXME: free_finger(remove_finger); Call this function at finger_table_add,
3137 when you replace an existing entry
3138 * Free finger and its trail.
3139 * @param remove_finger Finger to be freed.
3142 free_finger (struct FingerInfo *finger)
3144 struct TrailPeerList *peer;
3146 while (NULL != (peer = finger->head))
3148 GNUNET_CONTAINER_DLL_remove (finger->head, finger->tail, peer);
3152 GNUNET_free (finger);
3157 * Iterate over finger_peermap, and remove entries with peer as the first element
3159 * @param cls closure
3160 * @param key current public key
3161 * @param value value in the hash map
3162 * @return #GNUNET_YES if we should continue to
3164 * #GNUNET_NO if not.
3167 remove_matching_finger (void *cls,
3168 const struct GNUNET_PeerIdentity *key,
3171 struct FingerInfo *remove_finger = value;
3172 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
3174 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->head->peer, disconnected_peer))
3176 GNUNET_assert (GNUNET_YES ==
3177 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
3180 free_finger (remove_finger);
3187 * Method called whenever a peer disconnects.
3189 * @param cls closure
3190 * @param peer peer identity this notification is about
3193 handle_core_disconnect (void *cls,
3194 const struct GNUNET_PeerIdentity *peer)
3196 struct FriendInfo *remove_friend;
3198 /* Check for self message. */
3199 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
3202 /* Search for peer to remove in your friend_peermap. */
3204 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3206 if (NULL == remove_friend)
3212 /* Remove fingers for which this peer is the first element in the trail. */
3213 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap,
3214 &remove_matching_finger, (void *)peer);
3216 /* Remove routing trails of which this peer is a part. */
3217 GDS_ROUTING_remove_entry (peer);
3219 /* Remove the peer from friend_peermap. */
3220 GNUNET_assert (GNUNET_YES ==
3221 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
3225 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
3228 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3230 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3231 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3236 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
3238 GNUNET_SCHEDULER_cancel (verify_successor);
3239 verify_successor = GNUNET_SCHEDULER_NO_TASK;
3245 * Method called whenever a peer connects.
3247 * @param cls closure
3248 * @param peer_identity peer identity this notification is about
3251 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
3253 struct FriendInfo *friend;
3255 /* Check for connect to self message */
3256 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
3259 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
3261 /* If peer already exists in our friend_peermap, then exit. */
3262 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
3268 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
3271 friend = GNUNET_new (struct FriendInfo);
3272 friend->id = *peer_identity;
3274 GNUNET_assert (GNUNET_OK ==
3275 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
3276 peer_identity, friend,
3277 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
3279 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
3280 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
3281 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
3286 * To be called on core init/fail.
3288 * @param cls service closure
3289 * @param identity the public identity of this peer
3292 core_init (void *cls,
3293 const struct GNUNET_PeerIdentity *identity)
3295 my_identity = *identity;
3300 * Initialize neighbours subsystem.
3301 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3304 GDS_NEIGHBOURS_init (void)
3306 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
3307 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
3308 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
3309 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
3310 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
3311 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
3312 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
3313 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
3314 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
3315 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
3320 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
3321 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
3322 GNUNET_NO, core_handlers);
3323 if (NULL == core_api)
3324 return GNUNET_SYSERR;
3326 /* Initialize the current index in the finger map. */
3327 current_finger_index = PREDECESSOR_FINGER_ID;
3329 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
3330 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS * 4/3, GNUNET_NO);
3331 /* FIXME: Not sure if this value is correct for this data structure. also
3332 * not sure if we actually need any such data structure. Once done with other functions,
3333 * will revisit this part. */
3334 failed_trail_list = GNUNET_CONTAINER_multipeermap_create (LINK_THRESHOLD * 4/3, GNUNET_NO);
3340 * Shutdown neighbours subsystem.
3343 GDS_NEIGHBOURS_done (void)
3345 if (NULL == core_api)
3348 GNUNET_CORE_disconnect (core_api);
3351 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
3352 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
3353 friend_peermap = NULL;
3355 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
3356 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
3357 finger_peermap = NULL;
3359 /* FIXME: Here I have added GNUNET_break(0) as ideally if friend_peermap
3360 is already zero, then we really don't need to cancel it again. If this
3361 condition happens it mean we might have missed some corner case. */
3362 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3365 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3366 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3369 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
3372 GNUNET_SCHEDULER_cancel (verify_successor);
3373 verify_successor = GNUNET_SCHEDULER_NO_TASK;
3381 * @return my identity
3383 const struct GNUNET_PeerIdentity *
3384 GDS_NEIGHBOURS_get_my_id (void)
3386 return &my_identity;
3390 /* end of gnunet-service-xdht_neighbours.c */