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)
571 struct P2PPendingMessage *pending;
573 if (NULL == (pending = peer->head))
575 if (NULL != peer->th)
577 GNUNET_STATISTICS_update (GDS_stats,
579 ("# Bytes of bandwidth requested from core"),
580 ntohs (pending->msg->size), GNUNET_NO);
582 /*FIXME : here I don't know the use of importance, time out
583 Will check at run time if its all correct. */
585 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
587 GNUNET_TIME_absolute_get_remaining
588 (pending->timeout), &peer->id,
589 ntohs (pending->msg->size),
590 &core_transmit_notify, peer);
591 GNUNET_break (NULL != peer->th);
596 * FIXME: Check the parameters.
597 * Set up the trial message and forwards this message to friend.
599 * @param Finger id to which we want to setup the trail.
600 * @param Friend id through which we will try to setup the trail.
603 GDS_NEIGHBOURS_trail_setup(struct GNUNET_PeerIdentity *finger_id,
604 struct FriendInfo *target_friend)
607 * FIXME: check if pending message actually contains the correct data.
609 struct P2PPendingMessage *pending;
610 /* FIXME: why I have defined as **? verify by testing. */
611 struct PeerTrailSetupMessage *tsm;
614 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
616 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
620 /* SUPU: Verify if this copy between pending message, tsm is correct? */
621 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
622 /*SUPU: What does this code do? Does this intialize pending with
624 tsm = (struct PeerTrailSetupMessage *) &pending[1];
625 pending->msg = &tsm->header;
626 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
627 tsm->destination_finger = finger_id;
628 tsm->source_peer = &my_identity;
629 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
630 target_friend->pending_count++;
631 process_friend_queue(target_friend);
635 /**FIXME: Old implementation just to remove error
636 * TODO: Modify this function to handle our get request.
637 * Perform a GET operation. Forwards the given request to other
638 * peers. Does not lookup the key locally. May do nothing if this is
639 * the only peer in the network (or if we are the closest peer in the
642 * @param type type of the block
643 * @param options routing options
644 * @param desired_replication_level desired replication count
645 * @param hop_count how many hops did this request traverse so far?
646 * @param key key for the content
647 * @param xquery extended query
648 * @param xquery_size number of bytes in @a xquery
649 * @param reply_bf bloomfilter to filter duplicates
650 * @param reply_bf_mutator mutator for @a reply_bf
651 * @param peer_bf filter for peers not to select (again)
654 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
655 enum GNUNET_DHT_RouteOption options,
656 uint32_t desired_replication_level,
657 uint32_t hop_count, const struct GNUNET_HashCode * key,
658 const void *xquery, size_t xquery_size,
659 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
660 uint32_t reply_bf_mutator,
661 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
666 /**FIXME: Old implementation just to remove error.
667 * TODO: Modify this function to handle our put request.
668 * Perform a PUT operation. Forwards the given request to other
669 * peers. Does not store the data locally. Does not give the
670 * data to local clients. May do nothing if this is the only
671 * peer in the network (or if we are the closest peer in the
674 * @param type type of the block
675 * @param options routing options
676 * @param desired_replication_level desired replication count
677 * @param expiration_time when does the content expire
678 * @param hop_count how many hops has this message traversed so far
679 * @param bf Bloom filter of peers this PUT has already traversed
680 * @param key key for the content
681 * @param put_path_length number of entries in @a put_path
682 * @param put_path peers this request has traversed so far (if tracked)
683 * @param data payload to store
684 * @param data_size number of bytes in @a data
687 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
688 enum GNUNET_DHT_RouteOption options,
689 uint32_t desired_replication_level,
690 struct GNUNET_TIME_Absolute expiration_time,
692 struct GNUNET_CONTAINER_BloomFilter *bf,
693 const struct GNUNET_HashCode *key,
694 unsigned int put_path_length,
695 struct GNUNET_PeerIdentity *put_path,
696 const void *data, size_t data_size)
702 /**FIXME: Old implementation just to remove error.
703 * Handle a reply (route to origin). Only forwards the reply back to
704 * other peers waiting for it. Does not do local caching or
705 * forwarding to local clients.
707 * @param target neighbour that should receive the block (if still connected)
708 * @param type type of the block
709 * @param expiration_time when does the content expire
710 * @param key key for the content
711 * @param put_path_length number of entries in put_path
712 * @param put_path peers the original PUT traversed (if tracked)
713 * @param get_path_length number of entries in put_path
714 * @param get_path peers this reply has traversed so far (if tracked)
715 * @param data payload of the reply
716 * @param data_size number of bytes in data
719 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
720 enum GNUNET_BLOCK_Type type,
721 struct GNUNET_TIME_Absolute expiration_time,
722 const struct GNUNET_HashCode * key,
723 unsigned int put_path_length,
724 const struct GNUNET_PeerIdentity *put_path,
725 unsigned int get_path_length,
726 const struct GNUNET_PeerIdentity *get_path,
727 const void *data, size_t data_size)
735 * I have written a code where
736 * 1. I choose a random index from 0 to current size of my map.
737 * 2. Create an iterator.
738 * 3. set the iterator value to the current index id.
739 * 4. get the element stored at that index id.
740 * 5. return the index to calling function.
741 * I have not yet tested this function and I am not sure if its correct.
742 * Randomly choose one of your friends from the friends_peer map
745 static struct FriendInfo *
748 unsigned int current_size;
751 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
752 struct GNUNET_PeerIdentity key_ret;
753 struct FriendInfo *friend;
755 current_size = GNUNET_CONTAINER_multipeermap_size(friend_peers);
757 /* Element stored at this index in friend_peers map should be chosen friend. */
758 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
760 /* Create an iterator for friend_peers map. */
761 iter = GNUNET_CONTAINER_multipeermap_iterator_create(friend_peers);
763 /* Set the position of iterator to index. */
766 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,NULL,NULL))
772 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,&key_ret,(const void **)&friend))
782 * TODO: Check the logic of using current_finger_id again.
783 * This code is not correct. I need to check the pointers and
784 * correct use of memcpy and all the data type.
785 * Use Chord formula finger[i]=(n+2^(i-1))mod m,
786 * where i = current finger map index - max. 256 bits
787 * n = own peer identity - 256 bits
788 * m = number of bits in peer id - 256 bits
789 * @return finger_peer_id for which we have to find the trail through network.
792 struct GNUNET_PeerIdentity *
793 finger_id_to_search()
796 struct GNUNET_PeerIdentity *finger_peer_id;
800 finger_peer_id = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
802 /* Copy unsigned char array into peer_id. */
803 if (0 == memcpy(&peer_id,&my_identity.public_key.q_y,sizeof(uint32_t)))
807 /* We do all the arithmetic operation on peer_id to get finger_id*/
808 finger_id = (uint32_t)(peer_id + pow(2,current_finger_id)) % MAX_FINGERS;
811 /* Copy the finger_id to finger_peer_id. */
812 if (0 == memcpy(&finger_peer_id->public_key.q_y,&finger_id,sizeof(uint32_t)))
815 /* FIXME: Here I increment the index so that next time when we enter this
816 function, then we begin the search from current index. Is it possible
817 to set this value when we add the finger id to our finger table. No, because
818 even there is a call going on to find the finger, we can start another call
819 to search another peer. */
820 current_finger_id = (current_finger_id+1) % MAX_FINGERS;
822 /* Check if you already have an entry in finger_peers for this finger_id.
823 If yes then again look for a new finger_id. */
824 if(NULL == GNUNET_CONTAINER_multipeermap_get(finger_peers,finger_peer_id))
826 /* Is the recursion safe here? */
827 finger_peer_id = finger_id_to_search();
830 return finger_peer_id;
835 * TODO: Implement after testing friend/finger map.
836 * TODO: Handle the case when we already have a trail to our predecessor in
838 * This function will be needed when we are handling node joins/fails
839 * to maintain correct pointer to our predecessor and successor in the network.
840 * Find immediate predecessor in the network.
841 * @param me my own identity
842 * @return peer identity of immediate predecessor.
845 struct GNUNET_PeerIdentity*
846 find_immediate_predecessor()
848 /* Using your own peer identity, calculate your predecessor
849 in the network. Try to setup path to this predecessor using
850 the same logic as used for other fingers.
851 If we already have a trail to our predecessor then send NULL and
852 calling function should be able to handle that case. */
858 * Task to send a find finger trail message. We attempt to find trail
859 * to our finger in the network.
861 * @param cls closure for this task
862 * @param tc the context under which the task is running
865 send_find_finger_trail_message (void *cls,
866 const struct GNUNET_SCHEDULER_TaskContext *tc)
868 struct GNUNET_PeerIdentity *finger_peer_id;
869 struct FriendInfo *friend_peer_id;
870 struct GNUNET_TIME_Relative next_send_time;
872 /* We already have found trail to each of our possible fingers in the network. */
873 if (GNUNET_CONTAINER_multipeermap_size(finger_peers) == MAX_FINGERS)
875 /* We can find trail to our immediate predecessor in the network. */
876 finger_peer_id = find_immediate_predecessor();
877 if(NULL == finger_peer_id)
879 /* We already have a trail to reach to immediate predecessor. */
880 goto new_find_trail_request;
885 /* Find the finger_peer_id for which we want to setup the trail */
886 finger_peer_id = finger_id_to_search();
889 /* Choose a friend randomly from your friend_peers map. */
890 friend_peer_id = get_random_friend();
892 /* We found a friend.*/
893 if(NULL != friend_peer_id)
894 GDS_NEIGHBOURS_trail_setup(finger_peer_id, friend_peer_id);
897 new_find_trail_request:
899 next_send_time.rel_value_us =
900 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
901 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
902 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
903 (current_finger_id + 1));
905 find_finger_trail_task =
906 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
912 * Method called whenever a peer connects.
915 * @param peer peer identity this notification is about
918 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer)
920 struct FriendInfo *ret;
922 /* Check for connect to self message */
923 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
926 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
930 /* If peer already exists in our friend_peers, then exit. */
932 GNUNET_CONTAINER_multipeermap_contains (friend_peers,
939 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
942 ret = GNUNET_new (struct FriendInfo);
945 GNUNET_assert (GNUNET_OK ==
946 GNUNET_CONTAINER_multipeermap_put (friend_peers,
948 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
950 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
951 if (1 == GNUNET_CONTAINER_multipeermap_size(friend_peers))
952 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
957 * FIXME: Implement after testing finger/friend table setup.
958 * Method called whenever a peer disconnects.
961 * @param peer peer identity this notification is about
964 handle_core_disconnect (void *cls,
965 const struct GNUNET_PeerIdentity *peer)
968 * 1. remove the friend from the friend map.
969 * 2. remove the trail for the fingers for which this peer was the first hop.
970 * 3. start send_find_finger_trail for these fingers to find a new trail
972 * 4. Also when a node gets disconnected, how should we update pointers of its
973 * immediate successor and predecessor in the network ?
974 * 5. Also how do we distribute the keys in the network?
975 * 6. Here is case where we started put operation but a peer got disconnected and
976 we removed the entry from the table. How to handle such a case.
982 * To be called on core init/fail.
984 * @param cls service closure
985 * @param identity the public identity of this peer
988 core_init (void *cls,
989 const struct GNUNET_PeerIdentity *identity)
991 my_identity = *identity;
992 GNUNET_CRYPTO_hash (identity,
993 sizeof (struct GNUNET_PeerIdentity),
999 * Core handler for p2p put requests.
1001 * @param cls closure
1002 * @param peer sender of the request
1003 * @param message message
1004 * @param peer peer identity this notification is about
1005 * @return #GNUNET_OK to keep the connection open,
1006 * #GNUNET_SYSERR to close it (signal serious error)
1009 handle_dht_p2p_put (void *cls,
1010 const struct GNUNET_PeerIdentity *peer,
1011 const struct GNUNET_MessageHeader *message)
1014 1. Search the friend,finger and check your own id to find the closest
1015 * predecessor the given key. --> find_predecessor()
1016 2. If self then datache_store
1017 3. If friend, then add to peer queue
1018 4. If finger, then add to the peer queue of the first hop.
1019 * in put message also maintain a field current_destination and use
1020 * same logic as trail setup to understand if you are just part of trail
1021 * to reach to a particular peer or you are endpoint of trail or just a friend.
1029 * Core handler for p2p get requests.
1031 * @param cls closure
1032 * @param peer sender of the request
1033 * @param message message
1034 * @return #GNUNET_OK to keep the connection open,
1035 * #GNUNET_SYSERR to close it (signal serious error)
1038 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1039 const struct GNUNET_MessageHeader *message)
1046 * Core handler for p2p result messages.
1048 * @param cls closure
1049 * @param message message
1050 * @param peer peer identity this notification is about
1051 * @return #GNUNET_YES (do not cut p2p connection)
1054 handle_dht_p2p_result (void *cls, const struct GNUNET_PeerIdentity *peer,
1055 const struct GNUNET_MessageHeader *message)
1063 * Are we comparing the predecessor with our own identity also.
1065 * Here also we would be comparing the numeric value of
1066 * peer identity. We read the element from our map. Extract
1067 * the peer id and compare it with destination id. But again
1068 * this comparison is on values. Same issue again.
1069 * Find the predecessor for given finger_id from the
1070 * friend and finger table.
1071 * if friend, then just return the friend
1072 * if finger, then return the next hop to forward the packet to and also
1073 * set the current_destination field to finger_id.
1074 * @param destination peer id's predecessor we are looking for.
1077 static struct GNUNET_PeerIdentity *
1078 find_successor(struct GNUNET_PeerIdentity *destination)
1080 unsigned int friend_index;
1081 unsigned int finger_index;
1082 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1083 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1084 struct GNUNET_PeerIdentity key_ret;
1085 struct FriendInfo *friend;
1086 struct FingerInfo *finger;
1088 /* Should I keep a variable to remember if GNUNET_PeerIdentity is
1089 friend or finger. */
1090 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peers);
1092 /*iterate over friend map till you reach a peer id such that destination <= peer id */
1093 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peers); friend_index++)
1095 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1098 * 1. Check if friend >= destination.
1099 * 2. If yes then check if friend <= current_predecessor,
1100 * if yes then curret_predecessor = friend.
1101 * 3 If not then do nothing.
1107 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peers);
1108 /*iterate over finger map till you reach a peer id such that destination <= peer id */
1109 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (friend_peers); finger_index++)
1111 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1114 * 1. Check if finger >= destination.
1115 * 2. If yes then check if finger <= current_predecessor,
1116 * if yes then curret_predecessor = finger.
1117 * 3 If not then do nothing.
1122 /* Check between friend and finger value to decide which is the predecessor.
1123 If friend, then send the friend id.
1124 If finger, then send the next hop.
1125 Also set the current_destination = friend, if friend
1126 or else current_destination = finger. */
1131 /* Traverse the trail list to find the prev hop to store in routing table. */
1133 struct GNUNET_PeerIdentity *
1134 find_trail_list_prev_hop(struct PeerTrailSetupMessage *trail_result)
1136 /*FIXME: I don't see any function in existing dll implementation, to
1137 just read the dll backward or forward. So, I would implement one here.
1138 * As no one else uses this functionality so I guess its okay to just
1139 * implement it here. */
1146 * 1. Check if we are maintaining the 64k size of struct PeerTrailSetupMessage.
1147 * when we add ourself to the trail list.
1148 * 2. Ensure every case is handled for current_destination.
1149 * 3. When should you call GDS_Routing_Add?
1150 * Core handler for P2P trail setup message.
1151 * @param cls closure
1152 * @param message message
1153 * @param peer peer identity this notification is about
1154 * @return #GNUNET_YES
1157 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1158 const struct GNUNET_MessageHeader *message)
1160 struct PeerTrailSetupMessage *trail_setup;
1161 struct GNUNET_PeerIdentity *next_hop;
1162 struct GNUNET_PeerIdentity *prev_hop;
1163 struct FriendInfo *friend;
1164 struct TrailPeerList *peer_entry;
1165 struct P2PPendingMessage *pending;
1169 msize = ntohs (message->size);
1170 if (msize < sizeof (struct PeerTrailSetupMessage))
1172 GNUNET_break_op (0);
1176 trail_setup = (struct PeerTrailSetupMessage *) message;
1178 GNUNET_STATISTICS_update (GDS_stats,
1179 gettext_noop ("# TRAIL SETUP requests received"), 1,
1181 GNUNET_STATISTICS_update (GDS_stats,
1182 gettext_noop ("# TRAIL SETUP bytes received"), msize,
1186 /* Check the value of current_destination and handle the respective case. */
1187 if(trail_setup->current_destination == NULL)
1189 /* Find the next peer to pass the trail setup message. */
1190 next_hop = find_successor(trail_setup->destination_finger);
1192 else if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_setup->current_destination,&my_identity)))
1194 /* I am current destination, find the next peer to pass the trail setup message. */
1195 next_hop = find_successor(trail_setup->destination_finger);
1199 /* I am part of the trail to reach to current_destination. */
1200 next_hop = GDS_Routing_search(trail_setup->source_peer, trail_setup->current_destination, trail_setup->tail->peer);
1204 if(0 == (GNUNET_CRYPTO_cmp_peer_identity(next_hop,&my_identity)))
1206 /* I am the closest successor of the destination finger in the network. */
1208 1. Prepare a trail setup result message.
1209 2. Add yourself to trail list.
1210 3. send packet to last element in the list.
1216 * Do we really need to pass the whole trail_setup? I guess
1217 * we can just pass the double linked list.
1219 prev_hop = find_trail_list_prev_hop(trail_setup);
1221 /* Add an entry in the routing table.
1222 SUPU: Here we are adding an entry to our routing table because we are not final
1223 destination.So, it means we are part of a routing trail. It may happen
1224 that we found next_hop from searching the routing table. So, in GDS_ROUTING_Add,
1225 we should first check if there is already an entry for current_destination. If yes
1227 GDS_ROUTING_add(trail_setup->source_peer,trail_setup->current_destination,prev_hop,next_hop);
1230 * 1. Insert next hop into trail list.
1231 * 2. I don't see any function to just read the DLL. Need to see again if there is
1232 * one. If not then need to write something. */
1233 peer_entry = GNUNET_malloc (sizeof (struct TrailPeerList));
1234 peer_entry->peer = &my_identity;
1235 peer_entry->next = NULL;
1236 peer_entry->prev = NULL;
1238 /*SUPU what is this stupid code that I have written. */
1239 GNUNET_CONTAINER_DLL_insert_tail(trail_setup->head->next,trail_setup->tail->prev,peer_entry);
1241 /* Find the struct FriendInfo for next_hop peer id. */
1242 friend = GNUNET_CONTAINER_multipeermap_get(friend_peers,next_hop);
1244 if (friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1246 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1250 /* Send trail setup message to next hop friend. */
1251 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
1252 trail_setup = (struct PeerTrailSetupMessage *) &pending[1];
1253 pending->msg = &trail_setup->header;
1254 GNUNET_CONTAINER_DLL_insert_tail (friend->head, friend->tail, pending);
1255 friend->pending_count++;
1256 process_friend_queue(friend);
1261 /* Add an entry to finger table. */
1263 void finger_table_add(struct PeerTrailSetupResultMessage *result)
1265 /* 1. create a struct FingerInfo and copy respective members
1266 * of result into this struct.
1267 * Add the whole trail in your finger table,
1268 also add interval. */
1272 /* Traverse the trail list to find the next hop to pass the result message. */
1274 struct GNUNET_PeerIdentity *
1275 find_trail_list_next_hop(struct PeerTrailSetupResultMessage *trail_result)
1277 /* Setup the current_destination value to new next hop found. */
1283 * Core handle for p2p trail construction result messages.
1284 * @param cls closure
1285 * @param message message
1286 * @param peer peer identity this notification is about
1287 * @return #GNUNET_YES (do not cut p2p connection)
1291 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1292 const struct GNUNET_MessageHeader *message)
1294 /* FIXME: Should it be const? */
1295 struct PeerTrailSetupResultMessage *trail_result;
1296 struct GNUNET_PeerIdentity *next_hop;
1297 struct FriendInfo *friend;
1298 struct P2PPendingMessage *pending;
1299 trail_result = (struct PeerTrailSetupResultMessage *) message;
1303 msize = ntohs (message->size);
1304 if (msize < sizeof (struct PeerTrailSetupResultMessage))
1306 GNUNET_break_op (0);
1310 /* This should always be the case. */
1311 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_result->current_destination,&my_identity)))
1313 /* Am I the destination ? */
1314 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_result->destination_peer,&my_identity)))
1316 /* I am the destination. Add the trail to my finger table. */
1317 finger_table_add(trail_result);
1322 /* Find the next peer in the trail list to pass the message to. */
1323 next_hop = find_trail_list_next_hop(trail_result);
1325 /* Find the struct FriendInfo for next_hop peer id. */
1326 friend = GNUNET_CONTAINER_multipeermap_get(friend_peers,next_hop);
1328 if (friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1330 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1333 /* Send trail setup result message to next hop friend. */
1335 I have not yet written the code to copy struct trail message to
1336 pending message. Also, before sending the message I need to check
1337 the MAXIMUM_PENDNIG_PEER limit is not crossed. Modify the same part
1338 of code for handle_dht_p2p_trail_setup. */
1339 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
1340 trail_result = (struct PeerTrailSetupResultMessage *) &pending[1];
1341 pending->msg = &trail_result->header;
1342 GNUNET_CONTAINER_DLL_insert_tail (friend->head, friend->tail, pending);
1343 friend->pending_count++;
1344 process_friend_queue(friend);
1350 return GNUNET_SYSERR;
1355 * Initialize neighbours subsystem.
1356 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1359 GDS_NEIGHBOURS_init()
1361 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
1362 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
1363 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
1364 {&handle_dht_p2p_result, GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT, 0},
1365 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
1366 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
1370 /*ASK: What is ATS? Why do we need it? */
1371 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
1373 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
1374 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
1375 GNUNET_NO, core_handlers);
1376 if (core_api == NULL)
1377 return GNUNET_SYSERR;
1379 friend_peers = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1380 finger_peers = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1387 * Shutdown neighbours subsystem.
1390 GDS_NEIGHBOURS_done ()
1392 if (NULL == core_api)
1394 GNUNET_CORE_disconnect (core_api);
1396 GNUNET_ATS_performance_done (atsAPI);
1399 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peers));
1400 GNUNET_CONTAINER_multipeermap_destroy (friend_peers);
1401 friend_peers = NULL;
1403 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peers));
1404 GNUNET_CONTAINER_multipeermap_destroy (finger_peers);
1405 finger_peers = NULL;
1407 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
1409 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
1410 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
1416 * Get the ID of the local node.
1418 * @return identity of the local node
1420 struct GNUNET_PeerIdentity *
1421 GDS_NEIGHBOURS_get_id ()
1423 return &my_identity;
1427 /* end of gnunet-service-xdht_neighbours.c */