2 This file is part of GNUnet.
3 Copyright (C) 2009-2015 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-wdht_neighbours.c
23 * @brief GNUnet DHT service's finger and friend table management code
24 * @author Supriti Singh
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_ats_service.h"
34 #include "gnunet_core_service.h"
35 #include "gnunet_datacache_lib.h"
36 #include "gnunet_transport_service.h"
37 #include "gnunet_dht_service.h"
38 #include "gnunet_statistics_service.h"
39 #include "gnunet-service-xdht.h"
40 #include "gnunet-service-wdht_clients.h"
41 #include "gnunet-service-wdht_datacache.h"
42 #include "gnunet-service-wdht_neighbours.h"
47 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
52 #define FOO_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
55 * The number of layered ID to use.
57 #define NUMBER_LAYERED_ID 8
60 * Contains all the layered ID.
62 struct GNUNET_PeerIdentity layered_id[NUMBER_LAYERED_ID];
65 GNUNET_NETWORK_STRUCT_BEGIN
68 * Setup a finger using the underlay topology ("social network").
70 struct FingerSetupMessage
73 * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP
75 struct GNUNET_MessageHeader header;
78 * Number of hops this message has taken so far, we stop at
81 uint16_t hops_taken GNUNET_PACKED;
84 * Layer for the request, in NBO.
86 uint16_t layer GNUNET_PACKED;
89 * Unique (random) identifier this peer will use to
90 * identify the finger (in future messages).
92 struct GNUNET_HashCode finger_id;
98 * Response to a `struct FingerSetupMessage`.
100 struct FingerSetupResponseMessage
103 * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP_RESPONSE
105 struct GNUNET_MessageHeader header;
108 * Zero, for alignment.
110 uint32_t reserved GNUNET_PACKED;
113 * Unique (random) identifier this peer will use to
114 * identify the finger (in future messages).
116 struct GNUNET_HashCode finger_id;
119 * Random location in the respective layer where the
120 * random path of the finger setup terminated.
122 struct GNUNET_HashCode location;
128 * Response to an event that causes a finger to die.
130 struct FingerDestroyMessage
133 * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_DESTROY
135 struct GNUNET_MessageHeader header;
138 * Zero, for alignment.
140 uint32_t reserved GNUNET_PACKED;
143 * Unique (random) identifier this peer will use to
144 * identify the finger (in future messages).
146 struct GNUNET_HashCode finger_id;
152 * Send a message along a finger.
154 struct FingerRouteMessage
157 * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_ROUTE
159 struct GNUNET_MessageHeader header;
162 * Zero, for alignment.
164 uint32_t reserved GNUNET_PACKED;
167 * Unique (random) identifier this peer will use to
168 * identify the finger (in future messages).
170 struct GNUNET_HashCode finger_id;
172 /* followed by payload to send along the finger */
179 struct PeerPutMessage
182 * Type: #GNUNET_MESSAGE_TYPE_WDHT_PUT
184 struct GNUNET_MessageHeader header;
189 uint32_t options GNUNET_PACKED;
194 uint32_t block_type GNUNET_PACKED;
199 uint32_t hop_count GNUNET_PACKED;
202 * Replication level for this message
203 * In the current implementation, this value is not used.
205 uint32_t desired_replication_level GNUNET_PACKED;
208 * Length of the PUT path that follows (if tracked).
210 uint32_t put_path_length GNUNET_PACKED;
213 * When does the content expire?
215 struct GNUNET_TIME_AbsoluteNBO expiration_time;
218 * The key to store the value under.
220 struct GNUNET_HashCode key GNUNET_PACKED;
222 /* put path (if tracked) */
231 struct PeerGetMessage
234 * Type: #GNUNET_MESSAGE_TYPE_WDHT_GET
236 struct GNUNET_MessageHeader header;
241 uint32_t options GNUNET_PACKED;
244 * Desired content type.
246 uint32_t block_type GNUNET_PACKED;
251 uint32_t hop_count GNUNET_PACKED;
254 * Desired replication level for this request.
255 * In the current implementation, this value is not used.
257 uint32_t desired_replication_level GNUNET_PACKED;
260 * Total number of peers in get path.
262 unsigned int get_path_length;
265 * The key we are looking for.
267 struct GNUNET_HashCode key;
270 /* struct GNUNET_PeerIdentity[]*/
277 struct PeerGetResultMessage
280 * Type: #GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT
282 struct GNUNET_MessageHeader header;
285 * The type for the data.
287 uint32_t type GNUNET_PACKED;
290 * Number of peers recorded in the outgoing path from source to the
291 * stored location of this message.
293 uint32_t put_path_length GNUNET_PACKED;
296 * Length of the GET path that follows (if tracked).
298 uint32_t get_path_length GNUNET_PACKED;
301 * Peer which queried for get and should get the result.
303 struct GNUNET_PeerIdentity querying_peer;
306 * When does the content expire?
308 struct GNUNET_TIME_Absolute expiration_time;
311 * The key of the corresponding GET request.
313 struct GNUNET_HashCode key;
315 /* put path (if tracked) */
317 /* get path (if tracked) */
323 GNUNET_NETWORK_STRUCT_END
326 * Entry in friend_peermap.
332 * Information we keep per trail.
338 * MDLL entry in the list of all trails with the same predecessor.
340 struct Tail *prev_succ;
343 * MDLL entry in the list of all trails with the same predecessor.
345 struct Tail *next_succ;
348 * MDLL entry in the list of all trails with the same predecessor.
350 struct Tail *prev_pred;
353 * MDLL entry in the list of all trails with the same predecessor.
355 struct Tail *next_pred;
358 * Our predecessor in the trail, NULL if we are initiator (?).
360 struct FriendInfo *pred;
363 * Our successor in the trail, NULL if we are the last peer.
365 struct FriendInfo *succ;
368 * Identifier of the trail with the predecessor.
370 struct GNUNET_HashCode pred_id;
373 * Identifier of the trail with the successor.
375 struct GNUNET_HashCode succ_id;
378 * When does this trail expire.
380 struct GNUNET_TIME_Absolute expiration_time;
383 * Location of this trail in the heap.
385 struct GNUNET_CONTAINER_HeapNode *hn;
391 * Entry in friend_peermap.
398 struct GNUNET_PeerIdentity id;
400 struct Tail *pred_head;
402 struct Tail *pred_tail;
404 struct Tail *succ_head;
406 struct Tail *succ_tail;
409 * Core handle for sending messages to this friend.
411 struct GNUNET_MQ_Handle *mq;
418 * Task to timeout trails that have expired.
420 static struct GNUNET_SCHEDULER_Task *trail_timeout_task;
423 * Task to perform random walks.
425 static struct GNUNET_SCHEDULER_Task *random_walk_task;
428 * Identity of this peer.
430 static struct GNUNET_PeerIdentity my_identity;
433 * Peer map of all the fingers of a peer
435 static struct GNUNET_CONTAINER_MultiPeerMap *fingers_peermap;
438 * Peer map of all the successors of a peer
440 static struct GNUNET_CONTAINER_MultiPeerMap *successors_peermap;
443 * Tail map, mapping tail identifiers to `struct Trail`s
445 static struct GNUNET_CONTAINER_MultiHashMap *tail_map;
448 * Tail heap, organizing trails by expiration time.
450 static struct GNUNET_CONTAINER_Heap *tail_heap;
455 static struct GNUNET_CORE_Handle *core_api;
459 * Handle the put request from the client.
461 * @param key Key for the content
462 * @param block_type Type of the block
463 * @param options Routing options
464 * @param desired_replication_level Desired replication count
465 * @param expiration_time When does the content expire
466 * @param data Content to store
467 * @param data_size Size of content @a data in bytes
470 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
471 enum GNUNET_BLOCK_Type block_type,
472 enum GNUNET_DHT_RouteOption options,
473 uint32_t desired_replication_level,
474 struct GNUNET_TIME_Absolute expiration_time,
475 const void *data, size_t data_size)
481 * Handle the get request from the client file. If I am destination do
482 * datacache put and return. Else find the target friend and forward message
485 * @param key Key for the content
486 * @param block_type Type of the block
487 * @param options Routing options
488 * @param desired_replication_level Desired replication count
491 GDS_NEIGHBOURS_handle_get (const struct GNUNET_HashCode *key,
492 enum GNUNET_BLOCK_Type block_type,
493 enum GNUNET_DHT_RouteOption options,
494 uint32_t desired_replication_level)
501 * Send the get result to requesting client.
503 * @param key Key of the requested data.
504 * @param type Block type
505 * @param target_peer Next peer to forward the message to.
506 * @param source_peer Peer which has the data for the key.
507 * @param put_path_length Number of peers in @a put_path
508 * @param put_path Path taken to put the data at its stored location.
509 * @param get_path_length Number of peers in @a get_path
510 * @param get_path Path taken to reach to the location of the key.
511 * @param expiration When will this result expire?
512 * @param data Payload to store
513 * @param data_size Size of the @a data
516 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
517 enum GNUNET_BLOCK_Type type,
518 const struct GNUNET_PeerIdentity *target_peer,
519 const struct GNUNET_PeerIdentity *source_peer,
520 unsigned int put_path_length,
521 const struct GNUNET_PeerIdentity *put_path,
522 unsigned int get_path_length,
523 const struct GNUNET_PeerIdentity *get_path,
524 struct GNUNET_TIME_Absolute expiration,
525 const void *data, size_t data_size)
531 * Method called whenever a peer disconnects.
534 * @param peer peer identity this notification is about
537 handle_core_disconnect (void *cls,
538 const struct GNUNET_PeerIdentity *peer)
540 struct FriendInfo *remove_friend;
542 /* If disconnected to own identity, then return. */
543 if (0 == memcmp (&my_identity,
545 sizeof (struct GNUNET_PeerIdentity)))
548 if (NULL == (remove_friend =
549 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
556 GNUNET_assert (GNUNET_YES ==
557 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
560 /* FIXME: do stuff */
561 GNUNET_MQ_destroy (remove_friend->mq);
562 GNUNET_free (remove_friend);
564 GNUNET_CONTAINER_multipeermap_size (friend_peermap))
566 GNUNET_SCHEDULER_cancel (random_walk_task);
567 random_walk_task = NULL;
573 * Initiate a random walk.
579 do_random_walk (void *cls,
580 const struct GNUNET_SCHEDULER_TaskContext *tc)
582 struct FriendInfo *friend;
583 struct GNUNET_MQ_Envelope *env;
584 struct FingerSetupMessage *fsm;
586 friend = NULL; // FIXME: pick at random...
587 env = GNUNET_MQ_msg (fsm,
588 GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP);
589 fsm->hops_task = htons (0);
590 fsm->layer = htons (0); // FIXME: not always 0...
591 GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
593 GNUNET_MQ_send (friend->mq,
599 * Method called whenever a peer connects.
602 * @param peer_identity peer identity this notification is about
605 handle_core_connect (void *cls,
606 const struct GNUNET_PeerIdentity *peer_identity)
608 struct FriendInfo *friend;
610 /* Check for connect to self message */
611 if (0 == memcmp (&my_identity,
613 sizeof (struct GNUNET_PeerIdentity)))
616 /* If peer already exists in our friend_peermap, then exit. */
618 GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
625 friend = GNUNET_new (struct FriendInfo);
626 friend->id = *peer_identity;
627 friend->mq = GNUNET_CORE_mq_create (core_api,
629 GNUNET_assert (GNUNET_OK ==
630 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
633 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
636 if (NULL == random_walk_task)
638 /* start random walks! */
639 random_walk_task = GNUNET_SCHEDULER_add_now (&do_random_walk,
646 * To be called on core init/fail.
648 * @param cls service closure
649 * @param identity the public identity of this peer
652 core_init (void *cls,
653 const struct GNUNET_PeerIdentity *identity)
655 my_identity = *identity;
660 * Handle a `struct FingerSetupMessage` from a GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP
663 * @param cls closure (NULL)
664 * @param peer sender identity
665 * @param message the setup message
666 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
669 handle_dht_p2p_finger_setup (void *cls,
670 const struct GNUNET_PeerIdentity *peer,
671 const struct GNUNET_MessageHeader *message)
673 const struct FingerSetupMessage *fsm;
675 fsm = (const struct FingerSetupMessage *) message;
679 * 1 check if the hops_taken is < to log(honest node)
680 * 1.a.1 if true : increments the hops_taken
681 * 1.a.2 send the same structure
682 * 1.b if false : drop the message
689 * Handle a `struct FingerSetupResponseMessage` from a GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP_RESPONSE
692 * @param cls closure (NULL)
693 * @param peer sender identity
694 * @param message the setup response message
695 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
698 handle_dht_p2p_finger_setup_response (void *cls,
699 const struct GNUNET_PeerIdentity *peer,
700 const struct GNUNET_MessageHeader *message)
702 const struct FingerSetupResponseMessage *fsrm;
704 fsm = (const struct FingerSetupResponseMessage *) message;
708 * 1 check if we are the correct layer
709 * 1.a if true : add the return value in the db structure
710 * 1.b if true : do nothing
718 * Handle a `struct FingerDestroyMessage`.
720 * @param cls closure (NULL)
721 * @param peer sender identity
722 * @param message the finger destroy message
723 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
726 handle_dht_p2p_finger_destroy (void *cls,
727 const struct GNUNET_PeerIdentity *peer,
728 const struct GNUNET_MessageHeader *message)
730 const struct FingerDestroyMessage *fdm;
732 fdm = (const struct FingerDestroyMessage *) message;
736 * 1 check if message comme from a trail
737 * 1.a.1 if true: send the destroy message to the rest trail
738 * 1.a.2 clean the trail structure
739 * 1.a.3 did i have to remove the trail and ID from the db structure?
740 * 1.b if false: do nothing
747 * Handle a `struct FingerRouteMessage`.
749 * @param cls closure (NULL)
750 * @param peer sender identity
751 * @param message the finger route message
752 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
755 handle_dht_p2p_finger_route (void *cls,
756 const struct GNUNET_PeerIdentity *peer,
757 const struct GNUNET_MessageHeader *message)
759 const struct FingerRouteMessage *frm;
761 frm = (const struct FingerRouteMessage *) message;
762 /* FIXME: check the size of the message */
766 * 1 find the good trail
767 * 2 send the finger route message
774 * Handle a `struct FingerSetupMessage` from a GNUNET_MESSAGE_TYPE_WDHT_NEIGHBOUR_FIND
777 * @param cls closure (NULL)
778 * @param peer sender identity
779 * @param message the finger setup message
780 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
783 handle_dht_p2p_neighbour_find (void *cls,
784 const struct GNUNET_PeerIdentity *peer,
785 const struct GNUNET_MessageHeader *message)
787 const struct FingerSetupMessage *fsm;
789 fsm = (const struct FingerSetupMessage *) message;
795 * Handle a `struct FingerSetupResponseMessage` from a GNUNET_MESSAGE_TYPE_WDHT_NEIGHBOUR_FIND
798 * @param cls closure (NULL)
799 * @param peer sender identity
800 * @param message the finger setup response message
801 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
804 handle_dht_p2p_neighbour_found (void *cls,
805 const struct GNUNET_PeerIdentity *peer,
806 const struct GNUNET_MessageHeader *message)
808 const struct FingerSetupResponseMessage *fsrm;
810 fsrm = (const struct FingerSetupResponseMessage *) message;
816 * Handle a `struct PeerGetMessage`.
818 * @param cls closure (NULL)
819 * @param peer sender identity
820 * @param message the peer get message
821 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
824 handle_dht_p2p_peer_get (void *cls,
825 const struct GNUNET_PeerIdentity *peer,
826 const struct GNUNET_MessageHeader *message)
828 const struct PeerGetMessage *pgm;
830 pgm = (const struct PeerGetMessage *) message;
834 * 1 extract the result
836 * 3 send it using the good trail
838 * What do i do when i don't have the key/value?
845 * Handle a `struct PeerGetResultMessage`.
847 * @param cls closure (NULL)
848 * @param peer sender identity
849 * @param message the peer get result message
850 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
853 handle_dht_p2p_peer_get_result (void *cls,
854 const struct GNUNET_PeerIdentity *peer,
855 const struct GNUNET_MessageHeader *message)
857 const struct PeerGetResultMessage *pgrm;
859 pgrm = (const struct PeerGetResultMessage *) message;
863 * 1 extract the result
864 * 2 create a peerGetResult struct
865 * 3 send it using the good trail
867 * What do i do when i don't have the key/value?
875 * Handle a `struct PeerPutMessage`.
877 * @param cls closure (NULL)
878 * @param peer sender identity
879 * @param message the peer put message
880 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
883 handle_dht_p2p_peer_put (void *cls,
884 const struct GNUNET_PeerIdentity *peer,
885 const struct GNUNET_MessageHeader *message)
887 const struct PeerGetResultMessage *pgrm;
889 pgrm = (const struct PeerGetResultMessage *) message;
893 * 1 check the size of the message
894 * 2 use the API to add the value in the "database". Check on the xdht file, how to do it.
895 * 3 Did i a have to return a notification or did i have to return GNUNET_[OK|SYSERR]?
902 * Initialize neighbours subsystem.
903 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
906 GDS_NEIGHBOURS_init (void)
908 static const struct GNUNET_CORE_MessageHandler core_handlers[] = {
909 { &handle_dht_p2p_finger_setup,
910 GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP,
911 sizeof (struct FingerSetupMessage) },
912 { &handle_dht_p2p_finger_setup_response,
913 GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP_RESPONSE,
914 sizeof (struct FingerSetupResponseMessage) },
915 { &handle_dht_p2p_finger_destroy,
916 GNUNET_MESSAGE_TYPE_WDHT_FINGER_DESTROY,
917 sizeof (struct FingerDestroyMessage) },
918 { &handle_dht_p2p_finger_route,
919 GNUNET_MESSAGE_TYPE_WDHT_FINGER_ROUTE,
921 { &handle_dht_p2p_neighbour_find,
922 GNUNET_MESSAGE_TYPE_WDHT_NEIGHBOUR_FIND,
923 sizeof (struct FingerSetupMessage) },
924 { &handle_dht_p2p_neighbour_found,
925 GNUNET_MESSAGE_TYPE_WDHT_NEIGHBOUR_FOUND,
926 sizeof (struct FingerSetupResponseMessage) },
927 { &handle_dht_p2p_peer_get,
928 GNUNET_MESSAGE_TYPE_WDHT_GET,
929 sizeof (struct PeerGetMessage) },
930 { &handle_dht_p2p_peer_get_result,
931 GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT,
933 { &handle_dht_p2p_peer_put,
934 GNUNET_MESSAGE_TYPE_WDHT_PUT,
940 GNUNET_CORE_connect (GDS_cfg, NULL,
942 &handle_core_connect,
943 &handle_core_disconnect,
948 if (NULL == core_api)
949 return GNUNET_SYSERR;
951 fingers_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
952 successors_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
959 * Shutdown neighbours subsystem.
962 GDS_NEIGHBOURS_done (void)
964 if (NULL == core_api)
966 GNUNET_CORE_disconnect (core_api);
969 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
970 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
971 friend_peermap = NULL;
978 * @return my identity
980 struct GNUNET_PeerIdentity
981 GDS_NEIGHBOURS_get_my_id (void)
986 /* end of gnunet-service-wdht_neighbours.c */