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. Remove extra comments - FIXME,TODO,SUPU
54 * 2. Use GNUNET_Log to debug
58 * Maximum possible fingers of a peer.
60 #define MAX_FINGERS 256
63 * Maximum allowed number of pending messages per friend peer.
65 #define MAXIMUM_PENDING_PER_FRIEND 64
68 * How long at least to wait before sending another find finger trail request.
70 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
73 * How long at most to wait before sending another find finger trail request.
75 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 10)
78 GNUNET_NETWORK_STRUCT_BEGIN
81 * 1) Bloomfilter is not required for X-Vine.
82 * Keep the field now but remove it when implementing PUT/GET.
83 * 2) also, check the field of put/get/result if all are required for
92 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
94 struct GNUNET_MessageHeader header;
99 uint32_t options GNUNET_PACKED;
104 uint32_t type GNUNET_PACKED;
109 uint32_t hop_count GNUNET_PACKED;
112 * Replication level for this message
114 uint32_t desired_replication_level GNUNET_PACKED;
117 * Length of the PUT path that follows (if tracked).
119 uint32_t put_path_length GNUNET_PACKED;
122 * When does the content expire?
124 struct GNUNET_TIME_AbsoluteNBO expiration_time;
127 * Bloomfilter (for peer identities) to stop circular routes
129 char bloomfilter[DHT_BLOOM_SIZE];
132 * The key we are storing under.
134 struct GNUNET_HashCode key;
136 /* put path (if tracked) */
146 struct PeerResultMessage
149 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
151 struct GNUNET_MessageHeader header;
156 uint32_t type GNUNET_PACKED;
159 * Length of the PUT path that follows (if tracked).
161 uint32_t put_path_length GNUNET_PACKED;
164 * Length of the GET path that follows (if tracked).
166 uint32_t get_path_length GNUNET_PACKED;
169 * When does the content expire?
171 struct GNUNET_TIME_AbsoluteNBO expiration_time;
174 * The key of the corresponding GET request.
176 struct GNUNET_HashCode key;
178 /* put path (if tracked) */
180 /* get path (if tracked) */
190 struct PeerGetMessage
193 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
195 struct GNUNET_MessageHeader header;
200 uint32_t options GNUNET_PACKED;
203 * Desired content type.
205 uint32_t type GNUNET_PACKED;
210 uint32_t hop_count GNUNET_PACKED;
213 * Desired replication level for this request.
215 uint32_t desired_replication_level GNUNET_PACKED;
218 * Size of the extended query.
220 uint32_t xquery_size;
223 * Bloomfilter mutator.
228 * Bloomfilter (for peer identities) to stop circular routes
230 char bloomfilter[DHT_BLOOM_SIZE];
233 * The key we are looking for.
235 struct GNUNET_HashCode key;
241 * FIXME: I have defined this struct between GNUNET_NETWORK_STRUCT_BEGIN. Is
242 * it correct? Also, I am using the same struct inside finger info and trailsetup
243 * trailsetupresult message. Is it correct? Verify while testing. */
245 * Linked List of peers which are part of trail to reach a particular Finger.
250 * Pointer to next item in the list
252 struct TrailPeerList *next;
255 * Pointer to previous item in the list
257 struct TrailPeerList *prev;
260 * An element in this trail list
262 struct GNUNET_PeerIdentity *peer;
268 * FIXME : I am using the same struct TrailPeerList in both finger info
269 * and peertrailsetupmessage. Verify if its okay.
270 * P2P Trail setup message
272 struct PeerTrailSetupMessage
275 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
277 struct GNUNET_MessageHeader header;
280 * Source peer which wants to find trail to one of its finger.
282 struct GNUNET_PeerIdentity *source_peer;
285 * Finger id to which we want to set up the trail to.
287 struct GNUNET_PeerIdentity *destination_finger;
290 * This field contains the peer to which this packet is forwarded.
292 struct GNUNET_PeerIdentity *current_destination;
295 * Head of trail list.
297 struct TrailPeerList *head;
300 * Tail of trail list.
302 struct TrailPeerList *tail;
308 * P2P Trail setup Result message
310 struct PeerTrailSetupResultMessage
313 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
315 struct GNUNET_MessageHeader header;
318 * Finger to which we have found the path.
320 struct GNUNET_PeerIdentity *finger;
323 * Peer which was looking for the trail to finger.
325 struct GNUNET_PeerIdentity *destination_peer;
328 * This field contains the peer to which this packet is forwarded.
330 struct GNUNET_PeerIdentity *current_destination;
333 * Head of trail list.
335 struct TrailPeerList *head;
338 * Tail of trail list.
340 struct TrailPeerList *tail;
344 GNUNET_NETWORK_STRUCT_END
348 * Linked list of messages to send to a particular other peer.
350 struct P2PPendingMessage
353 * Pointer to next item in the list
355 struct P2PPendingMessage *next;
358 * Pointer to previous item in the list
360 struct P2PPendingMessage *prev;
363 * When does this message time out?
365 struct GNUNET_TIME_Absolute timeout;
368 * Message importance level. FIXME: used? useful?
370 unsigned int importance;
373 * Actual message to be sent, allocated at the end of the struct:
374 * // msg = (cast) &pm[1];
375 * // memcpy (&pm[1], data, len);
377 const struct GNUNET_MessageHeader *msg;
382 * Entry in friend_peers map.
388 * What is the identity of the peer?
390 struct GNUNET_PeerIdentity id;
393 * Count of outstanding messages for peer.
395 unsigned int pending_count;
398 * Head of pending messages to be sent to this peer.
400 struct P2PPendingMessage *head;
403 * Tail of pending messages to be sent to this peer.
405 struct P2PPendingMessage *tail;
408 * TODO - How and where to use this?
409 * Core handle for sending messages to this peer.
411 struct GNUNET_CORE_TransmitHandle *th;
416 * Entry in finger_peers map.
421 * What is the identity of the finger peer?
423 struct GNUNET_PeerIdentity id;
426 * Start of the interval of keys for which this finger is responsible.
428 unsigned int interval_start;
431 * End of the interval of keys for which this finger is responsible.
433 unsigned int interval_end;
436 * Head of trail list.
438 struct TrailPeerList *head;
441 * Tail of trail list.
443 struct TrailPeerList *tail;
449 * Task that sends FIND FINGER TRAIL requests.
451 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
454 * Identity of this peer.
456 static struct GNUNET_PeerIdentity my_identity;
459 * FIXME: Not used anywhere in the code yet.
460 * Hash of the identity of this peer.
462 static struct GNUNET_HashCode my_identity_hash;
465 * Hash map of all the friends of a peer
467 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peers;
470 * Hash map of all the fingers of a peer
472 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peers;
475 * TODO: Ask whats the use of ATS.
478 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
483 static struct GNUNET_CORE_Handle *core_api;
486 * The current finger index that we have found trail to.
488 static unsigned int current_finger_id;
492 * Called when core is ready to send a message we asked for
493 * out to the destination.
495 * @param cls the 'struct FriendInfo' of the target friend peer
496 * @param size number of bytes available in buf
497 * @param buf where the callee should write the message
498 * @return number of bytes written to buf
501 core_transmit_notify (void *cls, size_t size, void *buf)
503 struct FriendInfo *peer = cls;
505 struct P2PPendingMessage *pending;
510 while ((NULL != (pending = peer->head)) &&
511 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
513 peer->pending_count--;
514 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
515 GNUNET_free (pending);
519 /* no messages pending */
525 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
527 GNUNET_TIME_absolute_get_remaining
528 (pending->timeout), &peer->id,
529 ntohs (pending->msg->size),
530 &core_transmit_notify, peer);
531 GNUNET_break (NULL != peer->th);
535 while ((NULL != (pending = peer->head)) &&
536 (size - off >= (msize = ntohs (pending->msg->size))))
538 GNUNET_STATISTICS_update (GDS_stats,
540 ("# Bytes transmitted to other peers"), msize,
542 memcpy (&cbuf[off], pending->msg, msize);
544 peer->pending_count--;
545 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
546 GNUNET_free (pending);
548 if (peer->head != NULL)
551 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
553 GNUNET_TIME_absolute_get_remaining
554 (pending->timeout), &peer->id, msize,
555 &core_transmit_notify, peer);
556 GNUNET_break (NULL != peer->th);
563 * Transmit all messages in the friend's message queue.
565 * @param peer message queue to process
568 process_friend_queue (struct FriendInfo *peer)
570 struct P2PPendingMessage *pending;
572 if (NULL == (pending = peer->head))
574 if (NULL != peer->th)
576 GNUNET_STATISTICS_update (GDS_stats,
578 ("# Bytes of bandwidth requested from core"),
579 ntohs (pending->msg->size), GNUNET_NO);
581 /*FIXME : here I don't know the use of importance, time out
582 Will check at run time if its all correct. */
584 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
586 GNUNET_TIME_absolute_get_remaining
587 (pending->timeout), &peer->id,
588 ntohs (pending->msg->size),
589 &core_transmit_notify, peer);
590 GNUNET_break (NULL != peer->th);
595 * FIXME: Check the parameters.
596 * Set up the trial message and forwards this message to friend.
598 * @param Finger id to which we want to setup the trail.
599 * @param Friend id through which we will try to setup the trail.
602 GDS_NEIGHBOURS_trail_setup(struct GNUNET_PeerIdentity *finger_id,
603 struct FriendInfo *target_friend)
606 * FIXME: check if pending message actually contains the correct data.
608 struct P2PPendingMessage *pending;
609 /* FIXME: why I have defined as **? verify by testing. */
610 struct PeerTrailSetupMessage *tsm;
612 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
614 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
618 /* SUPU: Verify if this copy between pending message, tsm is correct? */
619 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
620 /*SUPU: What does this code do? Does this initialize pending with
622 tsm = (struct PeerTrailSetupMessage *) &pending[1];
623 pending->msg = &tsm->header;
624 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
625 tsm->destination_finger = finger_id;
626 tsm->source_peer = &my_identity;
627 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
628 target_friend->pending_count++;
629 process_friend_queue(target_friend);
633 /**FIXME: Old implementation just to remove error
634 * TODO: Modify this function to handle our get request.
635 * Perform a GET operation. Forwards the given request to other
636 * peers. Does not lookup the key locally. May do nothing if this is
637 * the only peer in the network (or if we are the closest peer in the
640 * @param type type of the block
641 * @param options routing options
642 * @param desired_replication_level desired replication count
643 * @param hop_count how many hops did this request traverse so far?
644 * @param key key for the content
645 * @param xquery extended query
646 * @param xquery_size number of bytes in @a xquery
647 * @param reply_bf bloomfilter to filter duplicates
648 * @param reply_bf_mutator mutator for @a reply_bf
649 * @param peer_bf filter for peers not to select (again)
652 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
653 enum GNUNET_DHT_RouteOption options,
654 uint32_t desired_replication_level,
655 uint32_t hop_count, const struct GNUNET_HashCode * key,
656 const void *xquery, size_t xquery_size,
657 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
658 uint32_t reply_bf_mutator,
659 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
664 /**FIXME: Old implementation just to remove error.
665 * TODO: Modify this function to handle our put request.
666 * Perform a PUT operation. Forwards the given request to other
667 * peers. Does not store the data locally. Does not give the
668 * data to local clients. May do nothing if this is the only
669 * peer in the network (or if we are the closest peer in the
672 * @param type type of the block
673 * @param options routing options
674 * @param desired_replication_level desired replication count
675 * @param expiration_time when does the content expire
676 * @param hop_count how many hops has this message traversed so far
677 * @param bf Bloom filter of peers this PUT has already traversed
678 * @param key key for the content
679 * @param put_path_length number of entries in @a put_path
680 * @param put_path peers this request has traversed so far (if tracked)
681 * @param data payload to store
682 * @param data_size number of bytes in @a data
685 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
686 enum GNUNET_DHT_RouteOption options,
687 uint32_t desired_replication_level,
688 struct GNUNET_TIME_Absolute expiration_time,
690 struct GNUNET_CONTAINER_BloomFilter *bf,
691 const struct GNUNET_HashCode *key,
692 unsigned int put_path_length,
693 struct GNUNET_PeerIdentity *put_path,
694 const void *data, size_t data_size)
700 /**FIXME: Old implementation just to remove error.
701 * Handle a reply (route to origin). Only forwards the reply back to
702 * other peers waiting for it. Does not do local caching or
703 * forwarding to local clients.
705 * @param target neighbour that should receive the block (if still connected)
706 * @param type type of the block
707 * @param expiration_time when does the content expire
708 * @param key key for the content
709 * @param put_path_length number of entries in put_path
710 * @param put_path peers the original PUT traversed (if tracked)
711 * @param get_path_length number of entries in put_path
712 * @param get_path peers this reply has traversed so far (if tracked)
713 * @param data payload of the reply
714 * @param data_size number of bytes in data
717 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
718 enum GNUNET_BLOCK_Type type,
719 struct GNUNET_TIME_Absolute expiration_time,
720 const struct GNUNET_HashCode * key,
721 unsigned int put_path_length,
722 const struct GNUNET_PeerIdentity *put_path,
723 unsigned int get_path_length,
724 const struct GNUNET_PeerIdentity *get_path,
725 const void *data, size_t data_size)
733 * I have written a code where
734 * 1. I choose a random index from 0 to current size of my map.
735 * 2. Create an iterator.
736 * 3. set the iterator value to the current index id.
737 * 4. get the element stored at that index id.
738 * 5. return the index to calling function.
739 * I have not yet tested this function and I am not sure if its correct.
740 * Randomly choose one of your friends from the friends_peer map
743 static struct FriendInfo *
746 unsigned int current_size;
749 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
750 struct GNUNET_PeerIdentity key_ret;
751 struct FriendInfo *friend;
753 current_size = GNUNET_CONTAINER_multipeermap_size(friend_peers);
755 /* Element stored at this index in friend_peers map should be chosen friend. */
756 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
758 /* Create an iterator for friend_peers map. */
759 iter = GNUNET_CONTAINER_multipeermap_iterator_create(friend_peers);
761 /* Set the position of iterator to index. */
764 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,NULL,NULL))
770 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,&key_ret,(const void **)&friend))
780 * TODO: Check the logic of using current_finger_id again.
781 * This code is not correct. I need to check the pointers and
782 * correct use of memcpy and all the data type.
783 * Use Chord formula finger[i]=(n+2^(i-1))mod m,
784 * where i = current finger map index - max. 256 bits
785 * n = own peer identity - 256 bits
786 * m = number of bits in peer id - 256 bits
787 * @return finger_peer_id for which we have to find the trail through network.
790 struct GNUNET_PeerIdentity *
791 finger_id_to_search()
793 struct GNUNET_PeerIdentity *finger_peer_id;
797 finger_peer_id = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
799 /* Copy unsigned char array into peer_id. */
800 if (0 == memcpy(&peer_id,&my_identity.public_key.q_y,sizeof(uint32_t)))
803 /* We do all the arithmetic operation on peer_id to get finger_id*/
804 finger_id = (uint32_t)(peer_id + pow(2,current_finger_id)) % MAX_FINGERS;
806 /* Copy the finger_id to finger_peer_id. */
807 if (0 == memcpy(&finger_peer_id->public_key.q_y,&finger_id,sizeof(uint32_t)))
811 /* FIXME: Here I increment the index so that next time when we enter this
812 function, then we begin the search from current index. Is it possible
813 to set this value when we add the finger id to our finger table. No, because
814 even there is a call going on to find the finger, we can start another call
815 to search another peer. */
816 current_finger_id = (current_finger_id+1) % MAX_FINGERS;
818 /* Check if you already have an entry in finger_peers for this finger_id.
819 If yes then again look for a new finger_id. */
820 /*if(NULL != GNUNET_CONTAINER_multipeermap_get(finger_peers,finger_peer_id))
823 finger_peer_id = finger_id_to_search();
826 return finger_peer_id;
831 * TODO: Implement after testing friend/finger map.
832 * TODO: Handle the case when we already have a trail to our predecessor in
834 * This function will be needed when we are handling node joins/fails
835 * to maintain correct pointer to our predecessor and successor in the network.
836 * Find immediate predecessor in the network.
837 * @param me my own identity
838 * @return peer identity of immediate predecessor.
841 struct GNUNET_PeerIdentity*
842 find_immediate_predecessor()
844 /* Using your own peer identity, calculate your predecessor
845 * in the network. Try to setup path to this predecessor using
846 * the same logic as used for other fingers.
847 * If we already have a trail to our predecessor then send NULL and
848 * calling function should be able to handle that case.
855 * Task to send a find finger trail message. We attempt to find trail
856 * to our finger in the network.
858 * @param cls closure for this task
859 * @param tc the context under which the task is running
862 send_find_finger_trail_message (void *cls,
863 const struct GNUNET_SCHEDULER_TaskContext *tc)
865 struct GNUNET_PeerIdentity *finger_peer_id;
866 struct FriendInfo *friend_peer_id;
867 struct GNUNET_TIME_Relative next_send_time;
869 /* We already have found trail to each of our possible fingers in the network. */
870 if (GNUNET_CONTAINER_multipeermap_size(finger_peers) == MAX_FINGERS)
872 /* We can find trail to our immediate predecessor in the network. */
873 finger_peer_id = find_immediate_predecessor();
874 if(NULL == finger_peer_id)
876 /* We already have a trail to reach to immediate predecessor. */
877 goto new_find_trail_request;
882 /* Find the finger_peer_id for which we want to setup the trail */
883 finger_peer_id = finger_id_to_search();
886 /* Choose a friend randomly from your friend_peers map. */
887 friend_peer_id = get_random_friend();
889 /* We found a friend.*/
890 if(NULL != friend_peer_id)
891 GDS_NEIGHBOURS_trail_setup(finger_peer_id, friend_peer_id);
894 new_find_trail_request:
896 next_send_time.rel_value_us =
897 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
898 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
899 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
900 (current_finger_id + 1));
902 find_finger_trail_task =
903 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
909 * Method called whenever a peer connects.
912 * @param peer peer identity this notification is about
915 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer)
917 struct FriendInfo *ret;
919 /* Check for connect to self message */
920 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
923 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
927 /* If peer already exists in our friend_peers, then exit. */
929 GNUNET_CONTAINER_multipeermap_contains (friend_peers,
936 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
939 ret = GNUNET_new (struct FriendInfo);
942 GNUNET_assert (GNUNET_OK ==
943 GNUNET_CONTAINER_multipeermap_put (friend_peers,
945 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
947 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
948 if (1 == GNUNET_CONTAINER_multipeermap_size(friend_peers))
949 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
954 * FIXME: Implement after testing finger/friend table setup.
955 * Method called whenever a peer disconnects.
958 * @param peer peer identity this notification is about
961 handle_core_disconnect (void *cls,
962 const struct GNUNET_PeerIdentity *peer)
965 * 1. remove the friend from the friend map.
966 * 2. remove the trail for the fingers for which this peer was the first hop.
967 * 3. start send_find_finger_trail for these fingers to find a new trail
969 * 4. Also when a node gets disconnected, how should we update pointers of its
970 * immediate successor and predecessor in the network ?
971 * 5. Also how do we distribute the keys in the network?
972 * 6. Here is case where we started put operation but a peer got disconnected and
973 we removed the entry from the table. How to handle such a case.
979 * To be called on core init/fail.
981 * @param cls service closure
982 * @param identity the public identity of this peer
985 core_init (void *cls,
986 const struct GNUNET_PeerIdentity *identity)
988 my_identity = *identity;
989 GNUNET_CRYPTO_hash (identity,
990 sizeof (struct GNUNET_PeerIdentity),
996 * Core handler for p2p put requests.
999 * @param peer sender of the request
1000 * @param message message
1001 * @param peer peer identity this notification is about
1002 * @return #GNUNET_OK to keep the connection open,
1003 * #GNUNET_SYSERR to close it (signal serious error)
1006 handle_dht_p2p_put (void *cls,
1007 const struct GNUNET_PeerIdentity *peer,
1008 const struct GNUNET_MessageHeader *message)
1011 1. Search the friend,finger and check your own id to find the closest
1012 * predecessor the given key. --> find_predecessor()
1013 2. If self then datache_store
1014 3. If friend, then add to peer queue
1015 4. If finger, then add to the peer queue of the first hop.
1016 * in put message also maintain a field current_destination and use
1017 * same logic as trail setup to understand if you are just part of trail
1018 * to reach to a particular peer or you are endpoint of trail or just a friend.
1026 * Core handler for p2p get requests.
1028 * @param cls closure
1029 * @param peer sender of the request
1030 * @param message message
1031 * @return #GNUNET_OK to keep the connection open,
1032 * #GNUNET_SYSERR to close it (signal serious error)
1035 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1036 const struct GNUNET_MessageHeader *message)
1043 * Core handler for p2p result messages.
1045 * @param cls closure
1046 * @param message message
1047 * @param peer peer identity this notification is about
1048 * @return #GNUNET_YES (do not cut p2p connection)
1051 handle_dht_p2p_result (void *cls, const struct GNUNET_PeerIdentity *peer,
1052 const struct GNUNET_MessageHeader *message)
1059 * FIXME:1. Check if current_destination field is set correctly.
1060 * 2. Is it correct to use GNUNET_CMP_PEER_IDENTITY to find out the successor
1062 * The code flow seems to be very large. Could do better.
1063 * @param destination peer id's predecessor we are looking for.
1066 static struct GNUNET_PeerIdentity *
1067 find_successor(struct GNUNET_PeerIdentity *destination, struct GNUNET_PeerIdentity *current_destination)
1069 unsigned int friend_index;
1070 unsigned int finger_index;
1071 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1072 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1073 struct GNUNET_PeerIdentity key_ret;
1074 struct FriendInfo *friend;
1075 struct FingerInfo *finger;
1076 struct GNUNET_PeerIdentity *current_successor;
1078 /* FIXME: Temporary field used to understand if we got a friend or finger
1079 as next successor. find something better.*/
1081 int finger_peer = 0;
1082 int friend_peer = 1;
1085 current_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1087 /* initialize current_successor with your own identity.*/
1088 memcpy(current_successor,&my_identity,sizeof(struct GNUNET_PeerIdentity));
1091 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peers);
1093 /*iterate over friend map till you reach a peer id such that destination <= peer id */
1094 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peers); friend_index++)
1096 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1098 if(0 > GNUNET_CRYPTO_cmp_peer_identity(&friend->id,destination) ||
1099 (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id,destination)))
1101 /* If yes then check if finger <= current_successor */
1102 if(0 < GNUNET_CRYPTO_cmp_peer_identity(&friend->id,current_successor) ||
1103 (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id,current_successor)))
1105 memcpy(current_successor,friend,sizeof(struct GNUNET_PeerIdentity));
1106 successor = friend_peer;
1113 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peers);
1114 /*iterate over finger map till you reach a peer id such that destination <= peer id */
1115 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peers); finger_index++)
1117 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1119 if(0 > GNUNET_CRYPTO_cmp_peer_identity(&finger->id,destination) ||
1120 (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->id,destination)))
1122 /* If yes then check if finger <= current_friend_successor */
1123 if(0 < GNUNET_CRYPTO_cmp_peer_identity(&finger->id,current_successor)
1124 || (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->id,current_successor)))
1126 memcpy(current_successor,finger,sizeof(struct GNUNET_PeerIdentity));
1127 successor = finger_peer;
1133 if(successor == finger_peer)
1135 memcpy(current_destination,current_successor,sizeof(struct GNUNET_PeerIdentity));
1139 /* The successor is either my_identity or friend. */
1140 current_destination = NULL;
1143 return current_successor;
1147 /* Traverse the trail list to find the prev hop to store in routing table. */
1149 struct GNUNET_PeerIdentity *
1150 find_trail_list_prev_hop(struct PeerTrailSetupMessage *trail_result)
1152 /*FIXME: I don't see any function in existing dll implementation, to
1153 just read the dll backward or forward. So, I would implement one here.
1154 * As no one else uses this functionality so I guess its okay to just
1155 * implement it here. */
1162 * 1. Check if we are maintaining the 64k size of struct PeerTrailSetupMessage.
1163 * when we add ourself to the trail list.
1164 * 2. Ensure every case is handled for current_destination.
1165 * Core handler for P2P trail setup message.
1166 * @param cls closure
1167 * @param message message
1168 * @param peer peer identity this notification is about
1169 * @return #GNUNET_YES
1172 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1173 const struct GNUNET_MessageHeader *message)
1175 struct PeerTrailSetupMessage *trail_setup;
1176 struct GNUNET_PeerIdentity *next_hop;
1177 struct GNUNET_PeerIdentity *prev_hop;
1178 struct FriendInfo *friend;
1179 struct TrailPeerList *peer_entry;
1180 struct P2PPendingMessage *pending;
1184 msize = ntohs (message->size);
1185 if (msize < sizeof (struct PeerTrailSetupMessage))
1187 GNUNET_break_op (0);
1191 trail_setup = (struct PeerTrailSetupMessage *) message;
1193 GNUNET_STATISTICS_update (GDS_stats,
1194 gettext_noop ("# TRAIL SETUP requests received"), 1,
1196 GNUNET_STATISTICS_update (GDS_stats,
1197 gettext_noop ("# TRAIL SETUP bytes received"), msize,
1201 /* Check the value of current_destination and handle the respective case. */
1202 if(trail_setup->current_destination == NULL)
1204 /* Find the next peer to pass the trail setup message. */
1205 next_hop = find_successor(trail_setup->destination_finger,trail_setup->current_destination);
1207 else if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_setup->current_destination,&my_identity)))
1209 /* I am current destination, find the next peer to pass the trail setup message. */
1210 next_hop = find_successor(trail_setup->destination_finger,trail_setup->current_destination);
1214 /* I am part of the trail to reach to current_destination. */
1215 next_hop = GDS_Routing_search(trail_setup->source_peer, trail_setup->current_destination, trail_setup->tail->peer);
1219 if(0 == (GNUNET_CRYPTO_cmp_peer_identity(next_hop,&my_identity)))
1221 /* I am the closest successor of the destination finger in the network. */
1223 1. Prepare a trail setup result message.
1224 2. Add yourself to trail list.
1225 3. send packet to last element in the list.
1231 * Do we really need to pass the whole trail_setup? I guess
1232 * we can just pass the double linked list.
1234 prev_hop = find_trail_list_prev_hop(trail_setup);
1236 GDS_ROUTING_add(trail_setup->source_peer,trail_setup->current_destination,prev_hop,next_hop);
1238 peer_entry = GNUNET_malloc (sizeof (struct TrailPeerList));
1239 peer_entry->peer = &my_identity;
1240 peer_entry->next = NULL;
1241 peer_entry->prev = NULL;
1243 /*SUPU what is this stupid code that I have written. */
1244 GNUNET_CONTAINER_DLL_insert_tail(trail_setup->head->next,trail_setup->tail->prev,peer_entry);
1246 /* Find the struct FriendInfo for next_hop peer id. */
1247 friend = GNUNET_CONTAINER_multipeermap_get(friend_peers,next_hop);
1249 if (friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1251 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1255 /* Send trail setup message to next hop friend. */
1256 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
1258 /* FIXME: Check if we are properly initializing pending. */
1259 trail_setup = (struct PeerTrailSetupMessage *) &pending[1];
1260 pending->msg = &trail_setup->header;
1261 GNUNET_CONTAINER_DLL_insert_tail (friend->head, friend->tail, pending);
1262 friend->pending_count++;
1263 process_friend_queue(friend);
1268 /* Add an entry to finger table. */
1270 void finger_table_add(struct PeerTrailSetupResultMessage *result)
1272 /* 1. create a struct FingerInfo and copy respective members
1273 * of result into this struct.
1274 * Add the whole trail in your finger table,
1275 also add interval. */
1279 /* Traverse the trail list to find the next hop to pass the result message. */
1281 struct GNUNET_PeerIdentity *
1282 find_trail_list_next_hop(struct PeerTrailSetupResultMessage *trail_result)
1284 /* Setup the current_destination value to new next hop found. */
1290 * Core handle for p2p trail construction result messages.
1291 * @param cls closure
1292 * @param message message
1293 * @param peer peer identity this notification is about
1294 * @return #GNUNET_YES (do not cut p2p connection)
1298 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1299 const struct GNUNET_MessageHeader *message)
1301 /* FIXME: Should it be const? */
1302 struct PeerTrailSetupResultMessage *trail_result;
1303 struct GNUNET_PeerIdentity *next_hop;
1304 struct FriendInfo *friend;
1305 struct P2PPendingMessage *pending;
1306 trail_result = (struct PeerTrailSetupResultMessage *) message;
1310 msize = ntohs (message->size);
1311 if (msize < sizeof (struct PeerTrailSetupResultMessage))
1313 GNUNET_break_op (0);
1317 /* This should always be the case. */
1318 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_result->current_destination,&my_identity)))
1320 /* Am I the destination ? */
1321 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_result->destination_peer,&my_identity)))
1323 /* I am the destination. Add the trail to my finger table. */
1324 finger_table_add(trail_result);
1329 /* Find the next peer in the trail list to pass the message to. */
1330 next_hop = find_trail_list_next_hop(trail_result);
1332 /* Find the struct FriendInfo for next_hop peer id. */
1333 friend = GNUNET_CONTAINER_multipeermap_get(friend_peers,next_hop);
1335 if (friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1337 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1340 /* Send trail setup result message to next hop friend. */
1342 I have not yet written the code to copy struct trail message to
1343 pending message. Also, before sending the message I need to check
1344 the MAXIMUM_PENDNIG_PEER limit is not crossed. Modify the same part
1345 of code for handle_dht_p2p_trail_setup. */
1346 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
1347 trail_result = (struct PeerTrailSetupResultMessage *) &pending[1];
1348 pending->msg = &trail_result->header;
1349 GNUNET_CONTAINER_DLL_insert_tail (friend->head, friend->tail, pending);
1350 friend->pending_count++;
1351 process_friend_queue(friend);
1357 return GNUNET_SYSERR;
1362 * Initialize neighbours subsystem.
1363 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1366 GDS_NEIGHBOURS_init()
1368 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
1369 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
1370 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
1371 {&handle_dht_p2p_result, GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT, 0},
1372 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
1373 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
1377 /*ASK: What is ATS? Why do we need it? */
1378 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
1380 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
1381 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
1382 GNUNET_NO, core_handlers);
1383 if (core_api == NULL)
1384 return GNUNET_SYSERR;
1386 friend_peers = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1387 finger_peers = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1394 * Shutdown neighbours subsystem.
1397 GDS_NEIGHBOURS_done ()
1399 if (NULL == core_api)
1401 GNUNET_CORE_disconnect (core_api);
1403 GNUNET_ATS_performance_done (atsAPI);
1406 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peers));
1407 GNUNET_CONTAINER_multipeermap_destroy (friend_peers);
1408 friend_peers = NULL;
1410 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peers));
1411 GNUNET_CONTAINER_multipeermap_destroy (finger_peers);
1412 finger_peers = NULL;
1414 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
1416 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
1417 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
1423 * Get the ID of the local node.
1425 * @return identity of the local node
1427 struct GNUNET_PeerIdentity *
1428 GDS_NEIGHBOURS_get_id ()
1430 return &my_identity;
1434 /* end of gnunet-service-xdht_neighbours.c */