2 This file is part of GNUnet.
3 (C) 2009-2013 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_nse_service.h"
34 #include "gnunet_ats_service.h"
35 #include "gnunet_core_service.h"
36 #include "gnunet_datacache_lib.h"
37 #include "gnunet_transport_service.h"
38 #include "gnunet_hello_lib.h"
39 #include "gnunet_dht_service.h"
40 #include "gnunet_statistics_service.h"
41 #include "gnunet-service-xdht.h"
42 #include "gnunet-service-xdht_clients.h"
43 #include "gnunet-service-xdht_datacache.h"
44 #include "gnunet-service-xdht_hello.h"
45 #include "gnunet-service-xdht_neighbours.h"
46 #include "gnunet-service-xdht_nse.h"
47 #include "gnunet-service-xdht_routing.h"
53 * 1. do we need some mechanism to check if we already have found trail to
54 * our finger at a particular index. also real finger identifier that we
55 * were looking for and successor it that we got. and whats the benefit of sending
56 * 64 bit finger for searching? can we just send gnuent_peeridentity finger id
57 * and only in find_successor we give 64 bit.
58 * 2. Think of better names for variable especially for variables of type
60 * 3. Add content and route replication later.
61 * 4. Algorithm to shorten the trail length - one possible solution could be
62 * when we are in trail seutp result part. each peer in the trail check if any of
63 * the corresponding peers is its friend list. Then it can shortcut the path.
64 * 4. As we start looking for finger from i = 0, using this parameter to
65 * generate random value does not look smart in send_find_finger_trail_message.
66 * 6. Need to add a new task, fix fingers. For node join/leave, we need to
67 * upgrade our finger table periodically. So, we should call fix_fingers
68 * and change our finger table.
69 * 7. Should we look for fingers one by one in send_find_finger_trail_setup
70 * 8. Change the message is gnunet_protocols.h
71 * 9. Can we just send the whole peer list as array for verify successor
72 * and verify successor result instead of the way in which we send in peertrailmessage.
73 * 10. I have added a new field trail length in finger info. so in finger_table_add
74 * find this value to be added.
79 * Maximum possible fingers of a peer.
80 * FIXME: Should it be 64 as we are doing all the operation on 64 bit numbers now?
82 #define MAX_FINGERS 64
85 * Maximum allowed number of pending messages per friend peer.
87 #define MAXIMUM_PENDING_PER_FRIEND 64
90 * How long at least to wait before sending another find finger trail request.
92 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
95 * How long at most to wait before sending another find finger trail request.
97 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 10)
100 * FIXME: Currently used in GDS_NEIGHBOURS_handle_trail_setup.
101 * I have just copied it from gnunet-service-dht_neighbours. Will it work here?
102 * How long at most to wait for transmission of a GET request to another peer?
104 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
106 GNUNET_NETWORK_STRUCT_BEGIN
109 * 1) Bloomfilter is not required for X-Vine.
110 * Keep the field now but remove it when implementing PUT/GET.
111 * 2) also, check the field of put/get/result if all are required for
117 struct PeerPutMessage
120 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
122 struct GNUNET_MessageHeader header;
127 uint32_t options GNUNET_PACKED;
132 uint32_t type GNUNET_PACKED;
137 uint32_t hop_count GNUNET_PACKED;
140 * Replication level for this message
142 uint32_t desired_replication_level GNUNET_PACKED;
145 * Length of the PUT path that follows (if tracked).
147 uint32_t put_path_length GNUNET_PACKED;
150 * When does the content expire?
152 struct GNUNET_TIME_AbsoluteNBO expiration_time;
155 * Bloomfilter (for peer identities) to stop circular routes
157 char bloomfilter[DHT_BLOOM_SIZE];
160 * The key we are storing under.
162 struct GNUNET_HashCode key;
164 /* put path (if tracked) */
174 struct PeerResultMessage
177 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
179 struct GNUNET_MessageHeader header;
184 uint32_t type GNUNET_PACKED;
187 * Length of the PUT path that follows (if tracked).
189 uint32_t put_path_length GNUNET_PACKED;
192 * Length of the GET path that follows (if tracked).
194 uint32_t get_path_length GNUNET_PACKED;
197 * When does the content expire?
199 struct GNUNET_TIME_AbsoluteNBO expiration_time;
202 * The key of the corresponding GET request.
204 struct GNUNET_HashCode key;
206 /* put path (if tracked) */
208 /* get path (if tracked) */
218 struct PeerGetMessage
221 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
223 struct GNUNET_MessageHeader header;
228 uint32_t options GNUNET_PACKED;
231 * Desired content type.
233 uint32_t type GNUNET_PACKED;
238 uint32_t hop_count GNUNET_PACKED;
241 * Desired replication level for this request.
243 uint32_t desired_replication_level GNUNET_PACKED;
246 * Size of the extended query.
248 uint32_t xquery_size;
251 * Bloomfilter mutator.
256 * Bloomfilter (for peer identities) to stop circular routes
258 char bloomfilter[DHT_BLOOM_SIZE];
261 * The key we are looking for.
263 struct GNUNET_HashCode key;
269 * A destination can be either a friend or finger.
271 enum current_destination_type
280 /* My own identity */
286 * P2P Trail setup message
287 * TODO: Take reference from put_path and get_path to understand how to use size of trail list.
289 struct PeerTrailSetupMessage
293 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
295 struct GNUNET_MessageHeader header;
298 * Source peer which wants to find trail to one of its finger.
300 struct GNUNET_PeerIdentity source_peer;
303 * FIXME: Do we need to store the real finger identifier we were searching
304 * for in our finger table. Whats the use of storing it if any?
305 * As we are not sending any hello messages to this destination
306 * finger, we are only searching for it, we can just send 64 bit.
307 * Finger id to which we want to set up the trail to.
309 struct GNUNET_PeerIdentity destination_finger; */
312 * Finger id to which we want to set up the trail to.
314 uint64_t destination_finger;
317 * If set to 1, then we are looking for trail to our immediate successor.
319 unsigned int successor_flag;
322 * If set to 1, then we are looking for trail to our immediate predecessor.
324 unsigned int predecessor_flag;
327 * If the message is forwarded to finger or friend.
329 enum current_destination_type current_destination_type;
332 * This field contains the peer to which this packet is forwarded.
334 struct GNUNET_PeerIdentity current_destination;
337 * Number of entries in trail list.
338 * FIXME: Is this data type correct?
339 * FIMXE: Is usage of GNUNET_PACKED correct?
341 uint32_t trail_length GNUNET_PACKED;
347 * P2P verify successor message.
349 struct PeerVerifySuccessorMessage
353 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
355 struct GNUNET_MessageHeader header;
358 * Source peer which wants to verify its successor.
360 struct GNUNET_PeerIdentity source_peer;
363 * Identity of our current successor.
365 struct GNUNET_PeerIdentity successor;
368 * Total number of peers in trail.
370 unsigned int trail_length;
373 * The current index in trail for next destination to send this message to.
375 unsigned int current_index;
383 struct PeerVerifySuccessorResultMessage
387 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
389 struct GNUNET_MessageHeader header;
392 * Destination peer which send the request to verify its successor.
394 struct GNUNET_PeerIdentity destination_peer;
397 * Identity of successor to which PeerVerifySuccessorMessage was sent.
399 struct GNUNET_PeerIdentity source_successor;
402 * source_successor's predecessor
404 struct GNUNET_PeerIdentity my_predecessor;
407 * Total number of peers in trail.
409 unsigned int trail_length;
412 * The current index in trail for next destination to send this message to.
414 unsigned int current_index;
421 struct PeerNotifyNewSuccessorMessage
427 /**FIXME: Here we can keep the whole list inside the message instead of attaching
428 * it all the time as the list remains constant all the time.
429 * P2P Trail setup Result message
431 struct PeerTrailSetupResultMessage
435 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
437 struct GNUNET_MessageHeader header;
440 * Finger to which we have found the path.
442 struct GNUNET_PeerIdentity finger;
445 * Peer which was looking for the trail to finger.
447 struct GNUNET_PeerIdentity destination_peer;
450 * This field contains the peer to which this packet is forwarded.
452 struct GNUNET_PeerIdentity current_destination;
455 * FIXME: Temporary field used to remember at which index we should read
456 * to get our next peer.
458 unsigned int current_index;
461 * If set to 1, then this trail is the trail to succcessor of our finger.
463 unsigned int successor_flag;
466 * If set to 1, then this trail is the trail to predecessor of our finger.
468 unsigned int predecessor_flag;
471 * Number of entries in trail list.
472 * FIXME: Is this data type correct?
473 * FIXME: Is usage of GNUNET_PACKED correct?
475 uint32_t trail_length GNUNET_PACKED;
479 GNUNET_NETWORK_STRUCT_END
483 * Linked list of messages to send to a particular other peer.
485 struct P2PPendingMessage
488 * Pointer to next item in the list
490 struct P2PPendingMessage *next;
493 * Pointer to previous item in the list
495 struct P2PPendingMessage *prev;
498 * When does this message time out?
500 struct GNUNET_TIME_Absolute timeout;
503 * Message importance level. FIXME: used? useful?
505 unsigned int importance;
508 * Actual message to be sent, allocated at the end of the struct:
509 * // msg = (cast) &pm[1];
510 * // memcpy (&pm[1], data, len);
512 const struct GNUNET_MessageHeader *msg;
518 * Linked List of peers which are part of trail to reach a particular Finger.
523 * Pointer to next item in the list
525 struct TrailPeerList *next;
528 * Pointer to previous item in the list
530 struct TrailPeerList *prev;
533 * An element in this trail list
535 struct GNUNET_PeerIdentity peer;
541 * 1.Previously I have added the field successor and predecessor of a friend.
542 * But whats the use and is it even possible to have those values.
543 * Entry in friend_peermap.
548 * What is the identity of the peer?
550 struct GNUNET_PeerIdentity id;
553 * Count of outstanding messages for peer.
555 unsigned int pending_count;
558 * Head of pending messages to be sent to this peer.
560 struct P2PPendingMessage *head;
563 * Tail of pending messages to be sent to this peer.
565 struct P2PPendingMessage *tail;
568 * Core handle for sending messages to this peer.
570 struct GNUNET_CORE_TransmitHandle *th;
576 * FIXME: We can also use an enum to say if its pred/suc/finger
577 * FIXME: As in chord , where we store the actual finger identity we were looking
578 * for and the real id which we got as successor. If we want to store like that
579 * then we will need to add a new field and search actual peer id.
580 * FIXME: Should we use another PeerIdentity which is smaller
581 * than 256 bits while storing.
582 * Predcessor is needed in case of node join/fail.
583 * Entry in finger_peermap.
590 struct GNUNET_PeerIdentity finger_identity;
593 * If 1, then this finger entry is first finger /successor of the peer.
595 unsigned int successor;
598 * If 1, then this finger entry is first predecessor of the peer.
600 unsigned int predecessor;
603 * Total number of entries in trail.
605 unsigned int trail_length;
608 * List of peers in the trail to reach this finger.
610 struct GNUNET_PeerIdentity *trail_peer_list;
616 * Task that sends FIND FINGER TRAIL requests.
618 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
622 * Task that periodically checks for the immediate successor.
624 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
627 * Identity of this peer.
629 static struct GNUNET_PeerIdentity my_identity;
632 * Hash map of all the friends of a peer
634 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
637 * Hash map of all the fingers of a peer
639 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
642 * TODO: Ask whats the use of ATS.
645 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
650 static struct GNUNET_CORE_Handle *core_api;
653 * FIXME: Is it safe to assume its initialized to 0 by default.
654 * The current finger index that we have found trail to.
656 static unsigned int current_finger_index;
660 * Called when core is ready to send a message we asked for
661 * out to the destination.
663 * @param cls the 'struct PeerInfo' of the target peer
664 * @param size number of bytes available in buf
665 * @param buf where the callee should write the message
666 * @return number of bytes written to buf
669 core_transmit_notify (void *cls, size_t size, void *buf)
671 struct FriendInfo *peer = cls;
673 struct P2PPendingMessage *pending;
678 while ((NULL != (pending = peer->head)) &&
679 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
681 peer->pending_count--;
682 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
683 GNUNET_free (pending);
687 /* no messages pending */
693 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
694 GNUNET_CORE_PRIO_BEST_EFFORT,
695 GNUNET_TIME_absolute_get_remaining
696 (pending->timeout), &peer->id,
697 ntohs (pending->msg->size),
698 &core_transmit_notify, peer);
699 GNUNET_break (NULL != peer->th);
703 while ((NULL != (pending = peer->head)) &&
704 (size - off >= (msize = ntohs (pending->msg->size))))
706 GNUNET_STATISTICS_update (GDS_stats,
708 ("# Bytes transmitted to other peers"), msize,
710 memcpy (&cbuf[off], pending->msg, msize);
712 peer->pending_count--;
713 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
714 GNUNET_free (pending);
716 if (peer->head != NULL)
719 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
720 GNUNET_CORE_PRIO_BEST_EFFORT,
721 GNUNET_TIME_absolute_get_remaining
722 (pending->timeout), &peer->id, msize,
723 &core_transmit_notify, peer);
724 GNUNET_break (NULL != peer->th);
731 * Transmit all messages in the friend's message queue.
733 * @param peer message queue to process
736 process_friend_queue (struct FriendInfo *peer)
738 struct P2PPendingMessage *pending;
740 if (NULL == (pending = peer->head))
742 if (NULL != peer->th)
745 GNUNET_STATISTICS_update (GDS_stats,
747 ("# Bytes of bandwidth requested from core"),
748 ntohs (pending->msg->size), GNUNET_NO);
750 /* FIXME: Are we correctly initializing importance and pending. */
752 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
754 GNUNET_TIME_absolute_get_remaining
755 (pending->timeout), &peer->id,
756 ntohs (pending->msg->size),
757 &core_transmit_notify, peer);
758 GNUNET_break (NULL != peer->th);
764 * We add the next destination i.e. friend to which we are sending the packet
765 * to our peer list in the calling function and we also increment trail_length
766 * in calling function i.e. send_find_finger_trail and handle_dht_p2p_trail_setup.
767 * Here we only copy the whole trail into our peer_list.
768 * Setup the trail message and forward it to a friend.
769 * @param source_peer Peer which wants to set up the trail to one of its finger.
770 * @param destination_finger Peer to which we want to set up the trail to.
771 * @param current_destination Current peer to which this message should be forwarded.
772 * @param trail_length Numbers of peers in the trail.
773 * @param trail_peer_list peers this request has traversed so far
774 * @param successor_flag If 1 then we are looking for trail to our successor.
777 GDS_NEIGHBOURS_handle_trail_setup(struct GNUNET_PeerIdentity *source_peer,
778 uint64_t *destination_finger,
779 struct FriendInfo *current_destination,
780 unsigned int trail_length,
781 struct GNUNET_PeerIdentity *trail_peer_list,
782 unsigned int successor_flag,
783 unsigned int predecessor_flag)
785 struct P2PPendingMessage *pending;
786 struct PeerTrailSetupMessage *tsm;
787 struct GNUNET_PeerIdentity *peer_list;
790 msize = sizeof (struct PeerTrailSetupMessage) +
791 (trail_length * sizeof (struct GNUNET_PeerIdentity));
793 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
799 if (current_destination->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
801 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
805 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
806 pending->importance = 0; /* FIXME */
807 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
808 tsm = (struct PeerTrailSetupMessage *) &pending[1];
809 pending->msg = &tsm->header;
810 tsm->header.size = htons (msize);
811 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
812 memcpy (&(tsm->destination_finger), destination_finger, sizeof (uint64_t));
813 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
814 memcpy (&(tsm->current_destination),&(current_destination->id),
815 sizeof (struct GNUNET_PeerIdentity));
816 tsm->current_destination_type = htonl(FRIEND);
817 tsm->trail_length = htonl(trail_length);
818 if(successor_flag == 1)
819 tsm->successor_flag = 1;
820 if(predecessor_flag == 1)
821 tsm->predecessor_flag = 1;
823 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
824 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
825 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
827 GNUNET_CONTAINER_DLL_insert_tail (current_destination->head, current_destination->tail, pending);
828 current_destination->pending_count++;
829 process_friend_queue (current_destination);
833 /**FIXME: As we are having a fixed list of trail peer list we can just
834 * store inside the message instead of attaching it all the time.
835 * Handle a tail setup result message.
836 * @param destination_peer Peer which will get the trail to one of its finger.
837 * @param source_finger Peer to which the trail has been setup to.
838 * @param current_destination Current peer to which this message should be forwarded.
839 * @param trail_length Numbers of peers in the trail.
840 * @param trail_peer_list peers this request has traversed so far
841 * @param current_trail_index Index in trail_peer_list.
844 GDS_NEIGHBOURS_handle_trail_setup_result (struct GNUNET_PeerIdentity *destination_peer,
845 struct GNUNET_PeerIdentity *source_finger,
846 struct FriendInfo *current_destination,
847 unsigned int trail_length,
848 const struct GNUNET_PeerIdentity *trail_peer_list,
849 unsigned int current_trail_index,
850 unsigned int successor_flag,
851 unsigned int predecessor_flag)
853 struct P2PPendingMessage *pending;
854 struct PeerTrailSetupResultMessage *tsrm;
855 struct GNUNET_PeerIdentity *peer_list;
858 msize = sizeof (struct PeerTrailSetupResultMessage) +
859 (trail_length * sizeof (struct GNUNET_PeerIdentity));
861 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
867 if (current_destination->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
869 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
873 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
874 pending->importance = 0; /* FIXME */
875 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
876 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
877 pending->msg = &tsrm->header;
878 tsrm->header.size = htons (msize);
879 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
880 memcpy (&(tsrm->current_destination), &(current_destination->id), sizeof(struct GNUNET_PeerIdentity));
881 memcpy (&(tsrm->destination_peer), destination_peer, sizeof(struct GNUNET_PeerIdentity));
882 memcpy (&(tsrm->finger), source_finger, sizeof(struct GNUNET_PeerIdentity));
883 tsrm->trail_length = htonl (trail_length);
884 tsrm->current_index = htonl (current_trail_index);
885 tsrm->successor_flag = htonl (successor_flag);
886 tsrm->predecessor_flag = htonl (predecessor_flag);
887 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
888 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
890 /* Send the message to chosen friend. */
891 GNUNET_CONTAINER_DLL_insert_tail (current_destination->head, current_destination->tail, pending);
892 current_destination->pending_count++;
893 process_friend_queue (current_destination);
897 /**FIXME: Calling function should provide the current destination
898 * and also should compute the new current_trail_index. Also you should add
899 * yourself to the list of peers and increment the length correctly. its
900 * responsibility of send_verify_successor_message and handle_verify_succesor_message.
901 * This function is called from send_verify_successor_message funciton
902 * and handle_dht_p2p_verify_successor.
903 * Construct a PeerVerifySuccessor message and send it to friend.
905 void GDS_NEIGUBOURS_handle_verify_successor(struct GNUNET_PeerIdentity *source_peer,
906 struct GNUNET_PeerIdentity *successor,
907 struct FriendInfo *current_destination,
908 struct GNUNET_PeerIdentity *trail_peer_list,
909 unsigned int trail_length,
910 unsigned int current_trail_index)
912 struct PeerVerifySuccessorMessage *vsm;
913 struct P2PPendingMessage *pending;
914 struct GNUNET_PeerIdentity *peer_list;
917 msize = sizeof (struct PeerVerifySuccessorMessage) +
918 (trail_length * sizeof(struct GNUNET_PeerIdentity));
920 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
926 if (current_destination->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
928 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
932 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
933 pending->importance = 0; /* FIXME */
934 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
935 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
936 pending->msg = &vsm->header;
937 vsm->header.size = htons (msize);
938 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
939 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
940 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
941 vsm->trail_length = htonl (trail_length);
942 vsm->current_index = htonl (current_trail_index);
944 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
945 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
947 /* Send the message to chosen friend. */
948 GNUNET_CONTAINER_DLL_insert_tail (current_destination->head, current_destination->tail, pending);
949 current_destination->pending_count++;
950 process_friend_queue (current_destination);
956 * 1. In this function we don't want the trail. so instead of maintaing the trail
957 * length and current_trail_index, we can just remove all the elements form trail list
958 * and current_destination = last element of trail list.
959 * 1. Responsiblity of calling function to provide new current destination.
960 * and correct current_trail_index.
961 * this function will be called by destination successor. and each peer
962 * which is in the trail to reach to the peer. as successor changed destination
963 * peer may have replaced the entry in its finger table. so you have to use the
964 * trial provided by source peer and so you should have source id in peerverifysuccessor
965 * Construct a PeerVerifySuccessorResult message and send it to friend.
967 void GDS_NEIGHBOURS_handle_verify_successor_result(struct GNUNET_PeerIdentity *destination_peer,
968 struct GNUNET_PeerIdentity *source_successor,
969 struct GNUNET_PeerIdentity *my_predecessor,
970 struct FriendInfo *current_destination,
971 struct GNUNET_PeerIdentity *trail_peer_list,
972 unsigned int trail_length,
973 unsigned int current_trail_index)
975 /* In this funciton, you receive
977 2. trial to reach that successor
979 4. current trail index --> this gives the next_hop on whose pending queue you should
981 struct PeerVerifySuccessorResultMessage *vsmr;
982 struct P2PPendingMessage *pending;
983 struct GNUNET_PeerIdentity *peer_list;
986 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
987 (trail_length * sizeof(struct GNUNET_PeerIdentity));
989 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
995 if (current_destination->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
997 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1001 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1002 pending->importance = 0; /* FIXME */
1003 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1004 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1005 pending->msg = &vsmr->header;
1006 vsmr->header.size = htons (msize);
1007 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1008 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1009 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1010 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1011 vsmr->trail_length = htonl (trail_length);
1012 vsmr->current_index = htonl (current_trail_index);
1014 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1015 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1017 /* Send the message to chosen friend. */
1018 GNUNET_CONTAINER_DLL_insert_tail (current_destination->head, current_destination->tail, pending);
1019 current_destination->pending_count++;
1020 process_friend_queue (current_destination);
1025 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1027 void GDS_NEIGHBOURS_handle_notify_new_successor()
1033 /**FIXME: Old implementation just to remove error
1034 * TODO: Modify this function to handle our get request.
1035 * Perform a GET operation. Forwards the given request to other
1036 * peers. Does not lookup the key locally. May do nothing if this is
1037 * the only peer in the network (or if we are the closest peer in the
1040 * @param type type of the block
1041 * @param options routing options
1042 * @param desired_replication_level desired replication count
1043 * @param hop_count how many hops did this request traverse so far?
1044 * @param key key for the content
1045 * @param xquery extended query
1046 * @param xquery_size number of bytes in @a xquery
1047 * @param reply_bf bloomfilter to filter duplicates
1048 * @param reply_bf_mutator mutator for @a reply_bf
1049 * @param peer_bf filter for peers not to select (again)
1052 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1053 enum GNUNET_DHT_RouteOption options,
1054 uint32_t desired_replication_level,
1055 uint32_t hop_count, const struct GNUNET_HashCode * key,
1056 const void *xquery, size_t xquery_size,
1057 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
1058 uint32_t reply_bf_mutator,
1059 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1063 1. take the key, get the 64 bit value of the key.
1064 2. call find_successor to get the successor of the key.
1065 3. successor can be either a friend or finger.
1066 4. update the field in get message to reflect if its a friend or finger table
1067 5. add the put message to pending message and send it.
1071 /**FIXME: Old implementation just to remove error.
1072 * TODO: Modify this function to handle our put request.
1073 * Perform a PUT operation. Forwards the given request to other
1074 * peers. Does not store the data locally. Does not give the
1075 * data to local clients. May do nothing if this is the only
1076 * peer in the network (or if we are the closest peer in the
1079 * @param type type of the block
1080 * @param options routing options
1081 * @param desired_replication_level desired replication count
1082 * @param expiration_time when does the content expire
1083 * @param hop_count how many hops has this message traversed so far
1084 * @param bf Bloom filter of peers this PUT has already traversed
1085 * @param key key for the content
1086 * @param put_path_length number of entries in @a put_path
1087 * @param put_path peers this request has traversed so far (if tracked)
1088 * @param data payload to store
1089 * @param data_size number of bytes in @a data
1092 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1093 enum GNUNET_DHT_RouteOption options,
1094 uint32_t desired_replication_level,
1095 struct GNUNET_TIME_Absolute expiration_time,
1097 struct GNUNET_CONTAINER_BloomFilter *bf,
1098 const struct GNUNET_HashCode *key,
1099 unsigned int put_path_length,
1100 struct GNUNET_PeerIdentity *put_path,
1101 const void *data, size_t data_size)
1105 1. take the key, get the 64 bit value of the key.
1106 2. call find_successor to get the successor of the key.
1107 3. successor can be either a friend or finger.
1108 4. update the field in put message to reflect if its a friend or finger table
1109 5. add the put message to pending message and send it.
1115 * FIXME: Check if this function actually iterates or not.
1116 * Randomly choose one of your friends from the friends_peer map
1119 static struct FriendInfo *
1120 select_random_friend()
1122 unsigned int current_size;
1123 unsigned int *index;
1125 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1126 struct GNUNET_PeerIdentity key_ret;
1127 struct FriendInfo *friend;
1129 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1131 /* Element stored at this index in friend_peermap should be selected friend. */
1132 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1134 /* Create an iterator for friend_peermap. */
1135 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1137 /* Set the position of iterator to index. */
1140 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1142 /* FIXME: I don't think we are actually incrementing iter. iter is always
1143 pointing to the same element. */
1150 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1160 * Compute finger_identity to which we want to setup the trail
1161 * FIXME: If we maintain a index that is value of current_finger_index
1162 * to which a particular entry in finger map corresponds then should we first
1163 * check if there is already an entry for that index. If yes then don't
1164 * search for trail to that finger.
1165 * @return finger_identity
1168 compute_finger_identity()
1171 uint64_t *finger_identity64;
1173 my_id64 = GNUNET_malloc (sizeof (uint64_t));
1174 finger_identity64 = GNUNET_malloc (sizeof (uint64_t));
1176 memcpy (my_id64, &(my_identity.public_key.q_y), sizeof (uint64_t));
1177 *finger_identity64 = fmod ((*my_id64 + pow (2,current_finger_index)),( (pow (2,MAX_FINGERS))));
1179 return finger_identity64;
1184 * Find immediate predecessor in the network.
1185 * @param me my own identity
1186 * @return peer identity of immediate predecessor.
1192 uint64_t *predecessor;
1194 my_id = GNUNET_malloc (sizeof (uint64_t));
1195 predecessor = GNUNET_malloc (sizeof (uint64_t));
1197 memcpy (my_id, &(my_identity.public_key.q_y), sizeof (uint64_t));
1198 *predecessor = fmod ((*my_id -1), (pow (2,MAX_FINGERS)));
1205 * Periodically ping your successor to ask its current predecessor
1207 * @param cls closure for this task
1208 * @param tc the context under which the task is running
1211 send_verify_successor_message(void *cls,
1212 const struct GNUNET_SCHEDULER_TaskContext *tc )
1214 struct GNUNET_TIME_Relative next_send_time;
1215 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1216 struct GNUNET_PeerIdentity key_ret;
1217 struct FriendInfo *current_destination;
1218 struct GNUNET_PeerIdentity *finger_trail;
1219 unsigned int finger_trail_length;
1220 unsigned int finger_trail_current_index;
1221 struct FingerInfo *finger;
1222 unsigned int finger_index;
1224 /* Iterate over your finger peermap to find the element with successor field set.
1225 That field is your successor. */
1226 /* FIXME: Again if the iteration is correct or not? */
1227 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1228 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1230 /* FIXME: I don't think we are actually iterating.
1231 Read about how to iterate over the multi peer map. */
1232 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1234 if(1 == finger->successor)
1235 break; /* FIXME: Do I come out of inner if or outer for */
1239 /* FIXME: Is this copy correct? */
1240 finger_trail = GNUNET_malloc ((finger->trail_length *
1241 sizeof (struct GNUNET_PeerIdentity)));
1242 current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1244 /* FIXME: Should we add ourself to peer list . When we get the result back
1245 then we should have to be in the list so that message reaches to us. */
1246 memcpy (finger_trail, finger->trail_peer_list,
1247 (finger->trail_length * sizeof (struct GNUNET_PeerIdentity)));
1248 finger_trail_length = finger->trail_length;
1249 finger_trail_current_index = 1;
1250 memcpy (current_destination, &finger_trail[1],
1251 sizeof (struct GNUNET_PeerIdentity));
1253 /* FIXME: current_destination should be friend not gnunet_peeridentity.
1254 Search over your friend_peermap to find the friend corresponding to
1255 current_destination. */
1256 GDS_NEIGUBOURS_handle_verify_successor (&my_identity,
1257 &(finger->finger_identity),
1258 current_destination,
1260 finger_trail_length,
1261 finger_trail_current_index);
1264 /* FIXME: Use a random value so that this message is send not at the same
1265 interval as send_find_finger_trail_message. */
1266 next_send_time.rel_value_us =
1267 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1268 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1269 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1270 (current_finger_index + 1));
1273 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1279 * Task to send a find finger trail message. We attempt to find trail
1280 * to our finger and successor in the network.
1282 * @param cls closure for this task
1283 * @param tc the context under which the task is running
1286 send_find_finger_trail_message (void *cls,
1287 const struct GNUNET_SCHEDULER_TaskContext *tc)
1289 struct FriendInfo *friend;
1290 struct GNUNET_TIME_Relative next_send_time;
1291 struct GNUNET_PeerIdentity *peer_list;
1292 unsigned int successor_flag;
1293 unsigned int predecessor_flag;
1294 uint64_t *finger_identity;
1296 if (1 == current_finger_index)
1298 /* We have started the process to find the successor. We should search
1299 for our predecessor. */
1300 finger_identity = find_predecessor();
1302 /* FIXME: There is no case in find_predecessor which returns NULL. It can
1303 return NULL, only if we already have found a trial to predecessor. is it
1304 required or not need to check.*/
1305 if(NULL == finger_identity)
1307 /* We already have a trail to reach to immediate predecessor. */
1308 goto new_find_finger_trail_request;
1310 predecessor_flag = 1;
1315 finger_identity = compute_finger_identity();
1317 if(finger_identity == NULL)
1319 goto new_find_finger_trail_request;
1323 if(0 == current_finger_index)
1325 /* We are searching for our successor in the network. */
1330 current_finger_index = current_finger_index + 1;
1331 friend = GNUNET_malloc (sizeof (struct FriendInfo));
1332 friend = select_random_friend();
1334 /* We found a friend.*/
1337 /*SUPU: Here you are adding yourself to peer list so that trail result
1338 reaches back to you. */
1339 unsigned int trail_length = 2;
1340 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
1341 memcpy (&peer_list[0], &(my_identity), sizeof (struct GNUNET_PeerIdentity));
1342 memcpy (&peer_list[1], &(friend->id), sizeof (struct GNUNET_PeerIdentity));
1344 GDS_NEIGHBOURS_handle_trail_setup (&my_identity, finger_identity,
1345 friend, trail_length, peer_list,
1346 successor_flag, predecessor_flag);
1349 /* FIXME: Should we be using current_finger_index to generate random interval.*/
1350 new_find_finger_trail_request:
1351 next_send_time.rel_value_us =
1352 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1353 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1354 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1355 (current_finger_index + 1));
1357 find_finger_trail_task =
1358 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1364 * Method called whenever a peer connects.
1366 * @param cls closure
1367 * @param peer peer identity this notification is about
1370 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer)
1372 struct FriendInfo *ret;
1374 /* Check for connect to self message */
1375 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1378 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1379 "Connected to %s\n",
1382 /* If peer already exists in our friend_peermap, then exit. */
1384 GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
1391 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
1395 ret = GNUNET_new (struct FriendInfo);
1398 GNUNET_assert (GNUNET_OK ==
1399 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
1401 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1404 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
1405 if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
1406 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
1411 * FIXME: Implement after testing finger/friend table setup.
1412 * Method called whenever a peer disconnects.
1414 * @param cls closure
1415 * @param peer peer identity this notification is about
1418 handle_core_disconnect (void *cls,
1419 const struct GNUNET_PeerIdentity *peer)
1422 * 1. remove the friend from the friend map.
1423 * 2. remove the trail for the fingers for which this peer was the first hop.
1424 * 3. start send_find_finger_trail for these fingers to find a new trail
1426 * 4. Also when a node gets disconnected, how should we update pointers of its
1427 * immediate successor and predecessor in the network ?
1428 * 5. Also how do we distribute the keys in the network?
1429 * 6. Here is case where we started put operation but a peer got disconnected and
1430 we removed the entry from the table. How to handle such a case.
1436 * To be called on core init/fail.
1438 * @param cls service closure
1439 * @param identity the public identity of this peer
1442 core_init (void *cls,
1443 const struct GNUNET_PeerIdentity *identity)
1445 my_identity = *identity;
1450 * Core handler for p2p put requests.
1452 * @param cls closure
1453 * @param peer sender of the request
1454 * @param message message
1455 * @param peer peer identity this notification is about
1456 * @return #GNUNET_OK to keep the connection open,
1457 * #GNUNET_SYSERR to close it (signal serious error)
1460 handle_dht_p2p_put (void *cls,
1461 const struct GNUNET_PeerIdentity *peer,
1462 const struct GNUNET_MessageHeader *message)
1465 1. Check if destination is friend or finger.
1466 2. If finger then get the next hop from routing table and
1467 * call GDS_NEGIHBOURS_handle_get.
1468 3. If friend then call find_successor to get the next hop and again
1469 * call GDS_NEIGHBOURS_handle_get to send to chosen hop.
1470 4. If you are the destination then do datacache_store.
1477 * Core handler for p2p get requests.
1479 * @param cls closure
1480 * @param peer sender of the request
1481 * @param message message
1482 * @return #GNUNET_OK to keep the connection open,
1483 * #GNUNET_SYSERR to close it (signal serious error)
1486 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1487 const struct GNUNET_MessageHeader *message)
1490 1. Check if destination is friend or finger.
1491 2. If finger then get the next hop from routing table and
1492 * call GDS_NEGIHBOURS_handle_get.
1493 3. If friend then call find_successor to get the next hop and again
1494 * call GDS_NEIGHBOURS_handle_get to send to chosen hop.
1495 4. If you are the destination then send the data back to source peer
1496 * Assuming we have trail setup we can
1497 * either store the whole trail or again do the search process..
1504 * Compare two peer identities.
1505 * @param p1 Peer identity
1506 * @param p2 Peer identity
1507 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
1510 compare_peer_id (const void *p1, const void *p2)
1512 return memcmp (p1, p2, sizeof (uint64_t));
1517 * Returns the previous element of value in all_known_peers.
1518 * @param all_known_peers list of all the peers
1519 * @param value value we have to search in the all_known_peers.
1522 static struct GNUNET_PeerIdentity *
1523 binary_search(struct GNUNET_PeerIdentity *all_known_peers, uint64_t *value,
1528 unsigned int middle;
1529 struct GNUNET_PeerIdentity *successor;
1530 successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1534 middle = (first + last)/2;
1536 while(first <= last)
1538 /* all_known_peers[middle] > value*/
1539 if(0 > compare_peer_id(&all_known_peers[middle], &value))
1543 else if(0 == compare_peer_id(&all_known_peers[middle], &value))
1547 successor = &(all_known_peers[size - 1]);
1550 successor = &(all_known_peers[middle-1]);
1557 middle = (first + last)/2;
1564 * Find closest successor for the value.
1565 * @param value Value for which we are looking for successor
1566 * @param current_destination NULL if my_identity is successor else finger/friend
1568 * @param type Next destination type
1569 * @return Peer identity of next destination i.e. successor of value.
1571 static struct GNUNET_PeerIdentity *
1572 find_successor(uint64_t *value, struct GNUNET_PeerIdentity *current_destination,
1573 enum current_destination_type *type)
1575 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1576 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1577 struct GNUNET_PeerIdentity key_ret;
1578 struct FriendInfo *friend;
1579 struct FingerInfo *finger;
1580 unsigned int finger_index;
1581 unsigned int friend_index;
1582 struct GNUNET_PeerIdentity *all_known_peers;
1583 struct GNUNET_PeerIdentity *successor;
1586 /* SUPU: 2 is added for my_identity and value. */
1587 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
1588 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
1591 all_known_peers = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * size);
1594 memcpy (&all_known_peers[j], &(my_identity), sizeof (struct GNUNET_PeerIdentity));
1596 memcpy (&all_known_peers[j], value, sizeof(struct GNUNET_PeerIdentity));
1598 /* Iterate over friend peermap and copy all the elements into array. */
1599 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1600 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1602 /* FIXME: I don't think we are actually iterating.
1603 Read about how to iterate over the multipeermap. */
1604 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1606 memcpy (&all_known_peers[j], &(friend->id), sizeof (struct GNUNET_PeerIdentity));
1611 /* Iterate over finger map and copy all the entries into all_known_peers array. */
1612 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1613 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1615 /* FIXME: I don't think we are actually iterating.
1616 Read about how to iterate over the multi peer map. */
1617 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1619 memcpy (&all_known_peers[j], &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1624 qsort (all_known_peers, size, sizeof (struct GNUNET_PeerIdentity), &compare_peer_id);
1626 /* search value in all_known_peers array. */
1627 successor = binary_search (all_known_peers, value, size);
1629 /* compare successor with my_identity, finger and friend */
1630 if(0 == GNUNET_CRYPTO_cmp_peer_identity(&(my_identity), successor))
1635 else if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
1639 memcpy (current_destination, successor, sizeof (struct GNUNET_PeerIdentity));
1642 else if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (finger_peermap,
1646 memcpy (current_destination, successor, sizeof (struct GNUNET_PeerIdentity));
1647 /* get the corresponding finger for succcesor and read the first element from
1648 the trail list and return that element. */
1649 struct FingerInfo *successor_finger;
1650 struct GNUNET_PeerIdentity *next_hop;
1651 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1652 successor_finger = GNUNET_malloc (sizeof (struct FingerInfo));
1653 successor_finger = GNUNET_CONTAINER_multipeermap_get (finger_peermap, successor);
1654 memcpy (next_hop, &(successor_finger->trail_peer_list[0]), sizeof (struct GNUNET_PeerIdentity));
1662 * Handle a PeerTrailSetupMessage.
1663 * @param cls closure
1664 * @param message message
1665 * @param peer peer identity this notification is about
1666 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1669 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1670 const struct GNUNET_MessageHeader *message)
1672 struct PeerTrailSetupMessage *trail_setup;
1673 struct GNUNET_PeerIdentity *next_hop;
1674 struct FriendInfo *target_friend;
1676 uint32_t trail_length;
1677 enum current_destination_type peer_type;
1678 struct GNUNET_PeerIdentity *trail_peer_list;
1679 uint32_t current_trail_index;
1680 struct GNUNET_PeerIdentity *next_peer;
1683 /* parse and validate message. */
1684 msize = ntohs (message->size);
1685 if (msize < sizeof (struct PeerTrailSetupMessage))
1687 GNUNET_break_op (0);
1691 trail_setup = (struct PeerTrailSetupMessage *) message;
1692 trail_length = ntohl (trail_setup->trail_length);
1693 peer_type = ntohl (trail_setup->current_destination_type);
1694 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_setup[1];
1697 sizeof (struct PeerTrailSetupMessage) +
1698 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1700 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1702 GNUNET_break_op (0);
1703 return GNUNET_YES; /*TODO: Why do we send GNUNET_YES here? */
1707 GNUNET_STATISTICS_update (GDS_stats,
1708 gettext_noop ("# TRAIL SETUP requests received"), 1,
1710 GNUNET_STATISTICS_update (GDS_stats,
1711 gettext_noop ("# TRAIL SETUP bytes received"), msize,
1714 if(peer_type == FRIEND)
1716 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
1719 next_hop = find_successor (&(trail_setup->destination_finger),
1720 &(trail_setup->current_destination),
1724 return GNUNET_SYSERR; /*TODO: Should we handle this case differently? */
1726 else if(peer_type == FINGER)
1728 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
1731 /* I am part of trail.
1732 SUPU: So, I should ask for next hop to reach the current_destination which is the finger
1733 for which this packet has been sent. */
1734 next_hop = GDS_ROUTING_search (&(trail_setup->source_peer),
1735 &(trail_setup->current_destination));
1738 call find_successor and compare the two peer ids
1739 and choose whichever is closest to the destination finger. */
1743 /* I am the current_destination finger
1744 FIXME: Why are we sending current_destination to find_successor.
1745 In this case, is it safe to assume current_Destination = my_identity.
1746 I guess we are sending current_destination so that we update it with new
1747 current_destination, if could either me, friend or finger.*/
1748 next_hop = find_successor (&(trail_setup->destination_finger),
1749 &(trail_setup->current_destination),&(peer_type));
1753 /* If you are the next hop */
1754 if(peer_type == MY_ID)
1756 /* FIXME: Verify if its allowed here to definer peer_list and define it
1757 again in the next block below? */
1758 struct GNUNET_PeerIdentity *peer_list;
1759 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length));
1760 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1761 current_trail_index = trail_length - 2;
1762 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); //FIXME: Do we need to allocate the memory?
1763 memcpy (next_peer, &peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
1765 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
1767 /* FIXME: It does not find a friend. Could be possible error in find_successor
1768 function. Change the logic in find_successor and change it again. */
1770 /* FIXME: Here as destination_finger is 64 bit instead of struct
1771 GNUNET_PeerIdentity, but you need destination_peer id. If you calling the
1772 function handle_Trail_setup_result from here, it means you are the
1773 destination. So, you can send your own identity. */
1774 GDS_NEIGHBOURS_handle_trail_setup_result (&(trail_setup->source_peer),
1776 target_friend, trail_length,
1777 peer_list,current_trail_index,
1778 trail_setup->successor_flag,
1779 trail_setup->predecessor_flag);
1784 /* Add next_hop to list of peers that trail setup message have traversed so far
1785 and increment trail length. */
1786 struct GNUNET_PeerIdentity *peer_list;
1787 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1));
1788 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1789 memcpy (&peer_list[trail_length], next_hop, sizeof (struct GNUNET_PeerIdentity));
1792 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1794 if(peer_type == FINGER)
1796 GDS_ROUTING_add (&(trail_setup->source_peer),
1797 &(trail_setup->current_destination),
1801 GDS_NEIGHBOURS_handle_trail_setup (&(trail_setup->source_peer),
1802 &(trail_setup->destination_finger),
1804 trail_setup->trail_length,
1805 peer_list,trail_setup->successor_flag,
1806 trail_setup->predecessor_flag);
1812 * Add an entry in finger table.
1813 * @param finger Finger to be added to finger table
1814 * @param peer_list peers this request has traversed so far
1815 * @param trail_length Numbers of peers in the trail.
1818 void finger_table_add(struct GNUNET_PeerIdentity *finger,
1819 const struct GNUNET_PeerIdentity *peer_list,
1820 unsigned int trail_length,
1821 unsigned int successor_flag,
1822 unsigned int predecessor_flag)
1824 /*FIXME: okay so there are two fields. one we should remember what finger
1825 identity we were looking for and what successor id we got. */
1826 struct FingerInfo *finger_entry;
1827 finger_entry = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1828 memcpy (&(finger_entry->finger_identity), finger, sizeof (struct GNUNET_PeerIdentity));
1829 memcpy (&(finger_entry->trail_peer_list), peer_list,
1830 sizeof (struct GNUNET_PeerIdentity)* trail_length);
1831 finger_entry->successor = successor_flag;
1832 finger_entry->predecessor = predecessor_flag;
1834 /*FIXME: Is it really a good time to call verify successor message. */
1835 if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap))
1836 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1841 * Core handle for p2p trail construction result messages.
1842 * @param cls closure
1843 * @param message message
1844 * @param peer peer identity this notification is about
1845 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1848 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1849 const struct GNUNET_MessageHeader *message)
1851 struct PeerTrailSetupResultMessage *trail_result;
1853 uint32_t trail_length;
1854 const struct GNUNET_PeerIdentity *trail_peer_list;
1855 uint32_t current_trail_index;
1856 struct GNUNET_PeerIdentity *next_peer;
1857 struct FriendInfo *target_friend;
1859 msize = ntohs (message->size);
1860 if (msize < sizeof (struct PeerTrailSetupMessage))
1862 GNUNET_break_op (0);
1866 trail_result = (struct PeerTrailSetupResultMessage *) message;
1867 trail_length = ntohl (trail_result->trail_length);
1868 current_trail_index = ntohl (trail_result->current_index);
1869 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
1872 sizeof (struct PeerTrailSetupResultMessage) +
1873 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1875 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1877 GNUNET_break_op (0);
1881 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->current_destination),
1884 /* Am I the destination? */
1885 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
1888 finger_table_add (&(trail_result->finger), trail_peer_list,trail_length,
1889 trail_result->successor_flag, trail_result->predecessor_flag);
1895 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1896 current_trail_index = current_trail_index - 1;
1897 memcpy (next_peer, &(trail_peer_list[trail_length-1]),
1898 sizeof (struct GNUNET_PeerIdentity));
1900 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
1902 GDS_NEIGHBOURS_handle_trail_setup_result(&(trail_result->destination_peer),
1903 &(trail_result->finger),
1904 target_friend, trail_length,
1905 trail_peer_list,current_trail_index,
1906 trail_result->successor_flag,
1907 trail_result->predecessor_flag);
1912 return GNUNET_SYSERR;
1917 * Core handle for p2p trail construction result messages.
1918 * @param cls closure
1919 * @param message message
1920 * @param peer peer identity this notification is about
1921 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1924 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
1925 const struct GNUNET_MessageHeader *message)
1928 * In this function you have received the message verify successor,
1929 * Now, either you are the destination or just part of the trail.
1930 * As we already know the whole path find out the next destination
1931 * and pass the packet forward.
1932 * If you are the final destination, check who is your predecessor.
1933 * and send your predecessor back to calling function. call GDS_NEIGHBOURS_handle_verify_successor
1934 * FIXME: Should we have a different handler function for it.
1936 struct PeerVerifySuccessorMessage *vsm;
1938 unsigned int trail_length;
1940 /* Uncomment after initialization
1941 struct GNUNET_PeerIdentity *trail_peer_list;
1942 unsigned int current_trail_index;
1943 struct GNUNET_PeerIdentity *next_peer;
1944 struct FriendInfo *target_friend;
1946 msize = ntohs (message->size);
1947 if (msize < sizeof (struct PeerVerifySuccessorMessage))
1949 GNUNET_break_op (0);
1953 vsm = (struct PeerVerifySuccessorMessage *) message;
1954 trail_length = ntohl (vsm->trail_length);
1955 //current_trail_index = ntohl (vsm->current_index);
1957 //trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1959 sizeof (struct PeerVerifySuccessorMessage) +
1960 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1962 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1964 GNUNET_break_op (0);
1968 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),
1971 /* You are the successor for which this message has been sent. */
1972 /* Search over your finger peer map to find the predecessor and then call
1973 GDS_NEIGHBOURS_handle_verify_successor_result with correct parameters. */
1974 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1975 struct GNUNET_PeerIdentity key_ret;
1976 unsigned int finger_index;
1977 struct FingerInfo *finger;
1978 struct GNUNET_PeerIdentity *destination_peer;
1980 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1981 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1983 /* FIXME: I don't think we are actually iterating.
1984 Read about how to iterate over the multi peer map. */
1985 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1987 if(1 == finger->predecessor)
1988 break; /* FIXME: Do I come out of inner if or outer for */
1992 destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1993 memcpy (destination_peer, &(vsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
1995 /*SUPU: Initialize all the fields. */
1996 /* FIXME: Initialize all the parameters of this function.
1997 Also, target_friend in this case is the peer id which is last in the trail.
1998 check if destination peer is in peer list or not. To check you will have to
1999 check the trail_setup and how we are adding the peer in there. */
2000 /* FIXME: Uncomment after initializing the fields
2001 * GDS_NEIGHBOURS_handle_verify_successor_result (destination_peer,
2003 &(finger->finger_identity),
2007 current_trail_index); */
2011 /* FIXME: Initialize all the parameters to
2012 * this function. Read the element at current_trail_index + 1
2013 and call GDS_NEIGHBOURS_handle_verify_successor with correct parameters. */
2014 /* FIXME: Uncomment after initializing the fields.
2015 * GDS_NEIGUBOURS_handle_verify_successor(&(vsm->source_peer),
2020 current_trail_index); */
2027 * Core handle for p2p trail construction result messages.
2028 * @param cls closure
2029 * @param message message
2030 * @param peer peer identity this notification is about
2031 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2034 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2035 const struct GNUNET_MessageHeader *message)
2038 * So, if you are the destination you should update your
2039 * predecessor field with peer id of source peer of this message.
2040 * If you are not the destination peer, then just check your routing
2041 * table and pass on the message.
2048 * Core handle for p2p trail construction result messages.
2049 * @param cls closure
2050 * @param message message
2051 * @param peer peer identity this notification is about
2052 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2055 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2056 const struct GNUNET_MessageHeader *message)
2059 * In this function you have received the message verify successor result,
2060 If you are not the destination, just pass this message forward
2061 * if you are destination,
2062 * then check if immediate predecessor of this peer is you or someone else.
2063 * If its you, then don't do anything.
2064 * If its some one else, then call notify method to let your new successor
2065 * know that you are its predecessor.
2072 * Initialize neighbours subsystem.
2073 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2076 GDS_NEIGHBOURS_init()
2078 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
2079 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
2080 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
2081 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
2082 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
2083 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
2084 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
2085 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
2089 /*TODO: What is ATS? Why do we need it? */
2090 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
2092 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
2093 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
2094 GNUNET_NO, core_handlers);
2095 if (core_api == NULL)
2096 return GNUNET_SYSERR;
2098 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
2099 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS, GNUNET_NO);
2106 * Shutdown neighbours subsystem.
2109 GDS_NEIGHBOURS_done ()
2111 if (NULL == core_api)
2114 GNUNET_CORE_disconnect (core_api);
2116 GNUNET_ATS_performance_done (atsAPI);
2119 /* FIXME: Once handle_core_disconnect is implemented, both below assertion should not
2121 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
2122 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
2123 friend_peermap = NULL;
2125 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
2126 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
2127 finger_peermap = NULL;
2129 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
2131 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
2132 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
2135 /* FIXME: fix_fingers will also be a task like this.
2137 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
2139 GNUNET_SCHEDULER_cancel (verify_successor);
2140 verify_successor = GNUNET_SCHEDULER_NO_TASK;
2147 * Get the ID of the local node.
2149 * @return identity of the local node
2151 struct GNUNET_PeerIdentity *
2152 GDS_NEIGHBOURS_get_id ()
2154 return &my_identity;
2158 /* end of gnunet-service-xdht_neighbours.c */