2 This file is part of GNUnet.
3 (C) 2009, 2010 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.
23 * @brief library to access the DHT service
24 * @author Christian Grothoff
25 * @author Nathan Evans
29 #include "gnunet_bandwidth_lib.h"
30 #include "gnunet_client_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_container_lib.h"
33 #include "gnunet_arm_service.h"
34 #include "gnunet_hello_lib.h"
35 #include "gnunet_protocols.h"
36 #include "gnunet_server_lib.h"
37 #include "gnunet_time_lib.h"
38 #include "gnunet_dht_service.h"
41 #define DEBUG_DHT_API GNUNET_NO
44 * Entry in our list of messages to be (re-)transmitted.
49 * This is a doubly-linked list.
51 struct PendingMessage *prev;
54 * This is a doubly-linked list.
56 struct PendingMessage *next;
59 * Message that is pending, allocated at the end
62 const struct GNUNET_MessageHeader *msg;
65 * Handle to the DHT API context.
67 struct GNUNET_DHT_Handle *handle;
70 * Continuation to call when the request has been
71 * transmitted (for the first time) to the service; can be NULL.
73 GNUNET_SCHEDULER_Task cont;
81 * Timeout task for this message
83 GNUNET_SCHEDULER_TaskIdentifier timeout_task;
86 * Unique ID for this request
91 * Free the saved message once sent, set to GNUNET_YES for messages
92 * that do not receive responses; GNUNET_NO if this pending message
93 * is aliased from a 'struct GNUNET_DHT_RouteHandle' and will be freed
99 * GNUNET_YES if this message is in our pending queue right now.
101 int in_pending_queue;
107 * Handle to a route request
109 struct GNUNET_DHT_RouteHandle
113 * Iterator to call on data receipt
115 GNUNET_DHT_ReplyProcessor iter;
118 * Closure for the iterator callback
123 * Main handle to this DHT api
125 struct GNUNET_DHT_Handle *dht_handle;
128 * The actual message sent for this request,
129 * used for retransmitting requests on service
130 * failure/reconnect. Freed on route_stop.
132 struct PendingMessage *message;
135 * Key that this get request is for
140 * Unique identifier for this request (for key collisions). FIXME: redundant!?
148 * Connection to the DHT service.
150 struct GNUNET_DHT_Handle
155 struct GNUNET_SCHEDULER_Handle *sched;
158 * Configuration to use.
160 const struct GNUNET_CONFIGURATION_Handle *cfg;
163 * Socket (if available).
165 struct GNUNET_CLIENT_Connection *client;
168 * Currently pending transmission request (or NULL).
170 struct GNUNET_CLIENT_TransmitHandle *th;
173 * Head of linked list of messages we would like to transmit.
175 struct PendingMessage *pending_head;
178 * Tail of linked list of messages we would like to transmit.
180 struct PendingMessage *pending_tail;
183 * Hash map containing the current outstanding unique requests
184 * (values are of type 'struct GNUNET_DHT_RouteHandle').
186 struct GNUNET_CONTAINER_MultiHashMap *active_requests;
189 * Generator for unique ids.
197 * Transmit the next pending message, called by notify_transmit_ready
200 transmit_pending (void *cls,
206 * Handler for messages received from the DHT service
207 * a demultiplexer which handles numerous message types
211 service_message_handler (void *cls,
212 const struct GNUNET_MessageHeader *msg);
218 * Try to (re)connect to the DHT service.
220 * @return GNUNET_YES on success, GNUNET_NO on failure.
223 try_connect (struct GNUNET_DHT_Handle *handle)
225 if (handle->client != NULL)
227 handle->client = GNUNET_CLIENT_connect (handle->sched, "dht", handle->cfg);
228 if (handle->client == NULL)
230 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
231 _("Failed to connect to the DHT service!\n"));
234 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
235 "Starting to process replies from DHT\n");
236 GNUNET_CLIENT_receive (handle->client,
237 &service_message_handler,
239 GNUNET_TIME_UNIT_FOREVER_REL);
245 * Add the request corresponding to the given route handle
246 * to the pending queue (if it is not already in there).
248 * @param cls the 'struct GNUNET_DHT_Handle*'
249 * @param key key for the request (not used)
250 * @param value the 'struct GNUNET_DHT_RouteHandle*'
251 * @return GNUNET_YES (always)
254 add_request_to_pending (void *cls,
255 const GNUNET_HashCode *key,
258 struct GNUNET_DHT_Handle *handle = cls;
259 struct GNUNET_DHT_RouteHandle *rh = value;
261 if (GNUNET_NO == rh->message->in_pending_queue)
263 GNUNET_CONTAINER_DLL_insert (handle->pending_head,
264 handle->pending_tail,
266 rh->message->in_pending_queue = GNUNET_YES;
273 * Re-connect to the DHT, re-issue all pending requests if needed.
276 reconnect (struct GNUNET_DHT_Handle *handle)
278 if (handle->client != NULL)
280 GNUNET_CLIENT_disconnect (handle->client,
282 handle->client = NULL;
284 if (GNUNET_YES != try_connect (handle))
286 GNUNET_CONTAINER_multihashmap_iterate (handle->active_requests,
287 &add_request_to_pending,
289 if (handle->pending_head == NULL)
291 GNUNET_CLIENT_notify_transmit_ready (handle->client,
292 ntohs(handle->pending_head->msg->size),
293 GNUNET_TIME_UNIT_FOREVER_REL,
302 * Try to send messages from list of messages to send
305 process_pending_messages (struct GNUNET_DHT_Handle *handle)
307 struct PendingMessage *head;
309 if (GNUNET_YES != try_connect (handle))
311 if (handle->th != NULL)
313 if (NULL == (head = handle->pending_head))
315 handle->th = GNUNET_CLIENT_notify_transmit_ready (handle->client,
316 ntohs (head->msg->size),
317 GNUNET_TIME_UNIT_FOREVER_REL,
321 if (NULL == handle->th)
330 * Transmit the next pending message, called by notify_transmit_ready
333 transmit_pending (void *cls,
337 struct GNUNET_DHT_Handle *handle = cls;
338 struct PendingMessage *head;
347 if (NULL == (head = handle->pending_head))
350 tsize = ntohs (head->msg->size);
353 process_pending_messages (handle);
356 memcpy (buf, head->msg, tsize);
357 GNUNET_CONTAINER_DLL_remove (handle->pending_head,
358 handle->pending_tail,
360 if (head->timeout_task != GNUNET_SCHEDULER_NO_TASK)
362 GNUNET_SCHEDULER_cancel (handle->sched,
364 head->timeout_task = GNUNET_SCHEDULER_NO_TASK;
366 if (NULL != head->cont)
368 GNUNET_SCHEDULER_add_continuation (handle->sched,
371 GNUNET_SCHEDULER_REASON_PREREQ_DONE);
373 head->cont_cls = NULL;
375 head->in_pending_queue = GNUNET_NO;
376 if (GNUNET_YES == head->free_on_send)
378 process_pending_messages (handle);
379 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
380 "Forwarded request of %u bytes to DHT service\n",
381 (unsigned int) tsize);
389 * Process a given reply that might match the given
393 process_reply (void *cls,
394 const GNUNET_HashCode *key,
397 const struct GNUNET_DHT_RouteResultMessage *dht_msg = cls;
398 struct GNUNET_DHT_RouteHandle *rh = value;
399 const struct GNUNET_MessageHeader *enc_msg;
402 const struct GNUNET_PeerIdentity **get_path;
403 const struct GNUNET_PeerIdentity **put_path;
404 const struct GNUNET_PeerIdentity *pos;
409 uid = GNUNET_ntohll (dht_msg->unique_id);
412 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
413 "Reply UID did not match request UID\n");
416 enc_size = ntohs (dht_msg->header.size) - sizeof (struct GNUNET_DHT_RouteResultMessage);
417 if (enc_size < sizeof (struct GNUNET_MessageHeader))
422 pos = (const struct GNUNET_PeerIdentity *) &dht_msg[1];
423 ppl = ntohs (dht_msg->put_path_length);
424 gpl = ntohs (dht_msg->get_path_length);
425 if ( (ppl + gpl) * sizeof (struct GNUNET_PeerIdentity) > enc_size)
432 put_path = GNUNET_malloc ((ppl+1) * sizeof (struct GNUNET_PeerIdentity*));
438 put_path[ppl] = NULL;
444 get_path = GNUNET_malloc ((gpl+1) * sizeof (struct GNUNET_PeerIdentity*));
450 get_path[gpl] = NULL;
454 enc_size -= (ppl + gpl) * sizeof (struct GNUNET_PeerIdentity);
455 enc_msg = (const struct GNUNET_MessageHeader *) pos;
456 if (enc_size != ntohs (enc_msg->size))
459 GNUNET_free_non_null (get_path);
460 GNUNET_free_non_null (put_path);
463 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
464 "Processing reply.\n");
465 rh->iter (rh->iter_cls,
470 GNUNET_free_non_null (get_path);
471 GNUNET_free_non_null (put_path);
477 * Handler for messages received from the DHT service
478 * a demultiplexer which handles numerous message types
480 * @param cls the 'struct GNUNET_DHT_Handle'
481 * @param msg the incoming message
484 service_message_handler (void *cls,
485 const struct GNUNET_MessageHeader *msg)
487 struct GNUNET_DHT_Handle *handle = cls;
488 const struct GNUNET_DHT_RouteResultMessage *dht_msg;
490 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
495 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
496 "Error receiving data from DHT service, reconnecting\n");
500 if (ntohs (msg->type) != GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_RESULT)
506 if (ntohs (msg->size) < sizeof (struct GNUNET_DHT_RouteResultMessage))
512 dht_msg = (const struct GNUNET_DHT_RouteResultMessage *) msg;
513 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
514 "Comparing reply `%s' against %u pending requests.\n",
515 GNUNET_h2s (&dht_msg->key),
516 GNUNET_CONTAINER_multihashmap_size (handle->active_requests));
517 GNUNET_CONTAINER_multihashmap_get_multiple (handle->active_requests,
521 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
522 "Continuing to process replies from DHT\n");
523 GNUNET_CLIENT_receive (handle->client,
524 &service_message_handler,
525 handle, GNUNET_TIME_UNIT_FOREVER_REL);
531 * Initialize the connection with the DHT service.
533 * @param sched scheduler to use
534 * @param cfg configuration to use
535 * @param ht_len size of the internal hash table to use for
536 * processing multiple GET/FIND requests in parallel
538 * @return handle to the DHT service, or NULL on error
540 struct GNUNET_DHT_Handle *
541 GNUNET_DHT_connect (struct GNUNET_SCHEDULER_Handle *sched,
542 const struct GNUNET_CONFIGURATION_Handle *cfg,
545 struct GNUNET_DHT_Handle *handle;
547 handle = GNUNET_malloc (sizeof (struct GNUNET_DHT_Handle));
549 handle->sched = sched;
550 handle->uid_gen = GNUNET_CRYPTO_random_u64(GNUNET_CRYPTO_QUALITY_WEAK, UINT64_MAX);
551 handle->active_requests = GNUNET_CONTAINER_multihashmap_create (ht_len);
552 if (GNUNET_NO == try_connect (handle))
554 GNUNET_DHT_disconnect (handle);
562 * Shutdown connection with the DHT service.
564 * @param handle handle of the DHT connection to stop
567 GNUNET_DHT_disconnect (struct GNUNET_DHT_Handle *handle)
569 struct PendingMessage *pm;
571 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size(handle->active_requests));
572 if (handle->th != NULL)
574 GNUNET_CLIENT_notify_transmit_ready_cancel (handle->th);
577 while (NULL != (pm = handle->pending_head))
579 GNUNET_CONTAINER_DLL_remove (handle->pending_head,
580 handle->pending_tail,
582 GNUNET_assert (GNUNET_YES == pm->free_on_send);
583 if (GNUNET_SCHEDULER_NO_TASK != pm->timeout_task)
584 GNUNET_SCHEDULER_cancel (handle->sched,
586 if (NULL != pm->cont)
587 GNUNET_SCHEDULER_add_continuation (handle->sched,
590 GNUNET_SCHEDULER_REASON_TIMEOUT);
591 pm->in_pending_queue = GNUNET_NO;
594 if (handle->client != NULL)
596 GNUNET_CLIENT_disconnect (handle->client, GNUNET_YES);
597 handle->client = NULL;
599 GNUNET_CONTAINER_multihashmap_destroy(handle->active_requests);
600 GNUNET_free (handle);
606 /* ***** Special low-level API providing generic routing abstraction ***** */
610 * Timeout for the transmission of a fire&forget-request. Clean it up.
612 * @param cls the 'struct PendingMessage'
613 * @param tc scheduler context
616 timeout_route_request (void *cls,
617 const struct GNUNET_SCHEDULER_TaskContext *tc)
619 struct PendingMessage *pending = cls;
620 struct GNUNET_DHT_Handle *handle;
622 if (pending->free_on_send != GNUNET_YES)
624 /* timeouts should only apply to fire & forget requests! */
628 handle = pending->handle;
629 GNUNET_CONTAINER_DLL_remove (handle->pending_head,
630 handle->pending_tail,
632 if (pending->cont != NULL)
633 pending->cont (pending->cont_cls,
635 GNUNET_free (pending);
640 * Initiate a generic DHT route operation.
642 * @param handle handle to the DHT service
643 * @param key the key to look up
644 * @param desired_replication_level how many peers should ultimately receive
645 * this message (advisory only, target may be too high for the
646 * given DHT or not hit exactly).
647 * @param options options for routing
648 * @param enc send the encapsulated message to a peer close to the key
649 * @param iter function to call on each result, NULL if no replies are expected
650 * @param iter_cls closure for iter
651 * @param timeout when to abort with an error if we fail to get
652 * a confirmation for the request (when necessary) or how long
653 * to wait for tramission to the service; only applies
655 * @param cont continuation to call when the request has been transmitted
656 * the first time to the service
657 * @param cont_cls closure for cont
658 * @return handle to stop the request, NULL if the request is "fire and forget"
660 struct GNUNET_DHT_RouteHandle *
661 GNUNET_DHT_route_start (struct GNUNET_DHT_Handle *handle,
662 const GNUNET_HashCode *key,
663 uint32_t desired_replication_level,
664 enum GNUNET_DHT_RouteOption options,
665 const struct GNUNET_MessageHeader *enc,
666 struct GNUNET_TIME_Relative timeout,
667 GNUNET_DHT_ReplyProcessor iter,
669 GNUNET_SCHEDULER_Task cont,
672 struct PendingMessage *pending;
673 struct GNUNET_DHT_RouteMessage *message;
674 struct GNUNET_DHT_RouteHandle *route_handle;
678 esize = ntohs (enc->size);
679 if (sizeof (struct GNUNET_DHT_RouteMessage) + esize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
684 msize = sizeof (struct GNUNET_DHT_RouteMessage) + esize;
685 pending = GNUNET_malloc (sizeof (struct PendingMessage) + msize);
686 message = (struct GNUNET_DHT_RouteMessage*) &pending[1];
687 pending->msg = &message->header;
688 pending->handle = handle;
689 pending->cont = cont;
690 pending->cont_cls = cont_cls;
692 message->header.size = htons (msize);
693 message->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE);
695 message->options = htonl ((uint32_t) options);
696 message->desired_replication_level = htonl (desired_replication_level);
698 message->unique_id = GNUNET_htonll (handle->uid_gen);
699 memcpy (&message[1], enc, esize);
703 route_handle = GNUNET_malloc (sizeof (struct GNUNET_DHT_RouteHandle));
704 route_handle->key = *key;
705 route_handle->iter = iter;
706 route_handle->iter_cls = iter_cls;
707 route_handle->dht_handle = handle;
708 route_handle->uid = handle->uid_gen;
709 route_handle->message = pending;
710 GNUNET_CONTAINER_multihashmap_put (handle->active_requests,
713 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
718 pending->free_on_send = GNUNET_YES;
719 pending->timeout_task = GNUNET_SCHEDULER_add_delayed (handle->sched,
721 &timeout_route_request,
724 GNUNET_CONTAINER_DLL_insert (handle->pending_head,
725 handle->pending_tail,
727 pending->in_pending_queue = GNUNET_YES;
728 process_pending_messages (handle);
729 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
730 "DHT route start request processed, returning %p\n",
737 * Stop a previously issued routing request
739 * @param route_handle handle to the request to stop
742 GNUNET_DHT_route_stop (struct GNUNET_DHT_RouteHandle *route_handle)
744 struct GNUNET_DHT_Handle *handle;
745 struct PendingMessage *pending;
746 struct GNUNET_DHT_StopMessage *message;
749 handle = route_handle->dht_handle;
750 if (GNUNET_NO == route_handle->message->in_pending_queue)
752 /* need to send stop message */
753 msize = sizeof (struct GNUNET_DHT_StopMessage);
754 pending = GNUNET_malloc (sizeof (struct PendingMessage) +
756 message = (struct GNUNET_DHT_StopMessage*) &pending[1];
757 pending->msg = &message->header;
758 message->header.size = htons (msize);
759 message->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_STOP);
760 message->unique_id = GNUNET_htonll (route_handle->uid);
761 message->key = route_handle->key;
762 pending->handle = handle;
763 pending->free_on_send = GNUNET_YES;
764 pending->in_pending_queue = GNUNET_YES;
765 GNUNET_CONTAINER_DLL_insert (handle->pending_head,
766 handle->pending_tail,
768 process_pending_messages (handle);
772 /* simply remove pending request from message queue before
773 transmission, no need to transmit STOP request! */
774 GNUNET_CONTAINER_DLL_remove (handle->pending_head,
775 handle->pending_tail,
776 route_handle->message);
778 GNUNET_assert (GNUNET_YES ==
779 GNUNET_CONTAINER_multihashmap_remove (route_handle->dht_handle->active_requests,
782 GNUNET_free(route_handle->message);
783 GNUNET_free(route_handle);
784 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
785 "DHT route stop request processed\n");
790 /* ***** Special API for controlling DHT routing maintenance ******* */
794 * Send a control message to the DHT.
796 * @param handle handle to the DHT service
797 * @param command command
798 * @param variable variable to the command
799 * @param cont continuation to call when done (transmitting request to service)
800 * @param cont_cls closure for cont
803 send_control_message (struct GNUNET_DHT_Handle *handle,
806 GNUNET_SCHEDULER_Task cont,
809 struct GNUNET_DHT_ControlMessage *msg;
810 struct PendingMessage *pending;
812 pending = GNUNET_malloc (sizeof (struct PendingMessage) +
813 sizeof(struct GNUNET_DHT_ControlMessage));
814 msg = (struct GNUNET_DHT_ControlMessage*) &pending[1];
815 pending->msg = &msg->header;
816 msg->header.size = htons (sizeof(struct GNUNET_DHT_ControlMessage));
817 msg->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_CONTROL);
818 msg->command = htons (command);
819 msg->variable = htons (variable);
820 pending->free_on_send = GNUNET_YES;
821 pending->cont = cont;
822 pending->cont_cls = cont_cls;
823 pending->in_pending_queue = GNUNET_YES;
824 GNUNET_CONTAINER_DLL_insert (handle->pending_head,
825 handle->pending_tail,
827 process_pending_messages (handle);
832 * Send a message to the DHT telling it to issue a single find
833 * peer request using the peers unique identifier as key. This
834 * is used to fill the routing table, and is normally controlled
835 * by the DHT itself. However, for testing and perhaps more
836 * close control over the DHT, this can be explicitly managed.
838 * @param handle handle to the DHT service
839 * @param cont continuation to call when done (transmitting request to service)
840 * @param cont_cls closure for cont
843 GNUNET_DHT_find_peers (struct GNUNET_DHT_Handle *handle,
844 GNUNET_SCHEDULER_Task cont,
847 send_control_message (handle,
848 GNUNET_MESSAGE_TYPE_DHT_FIND_PEER, 0,
857 * Send a message to the DHT telling it to start issuing random GET
858 * requests every 'frequency' milliseconds.
860 * @param handle handle to the DHT service
861 * @param frequency delay between sending malicious messages
864 GNUNET_DHT_set_malicious_getter (struct GNUNET_DHT_Handle *handle,
865 struct GNUNET_TIME_Relative frequency)
867 if (frequency.value > UINT16_MAX)
872 send_control_message (handle,
873 GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_GET, frequency.value,
878 * Send a message to the DHT telling it to start issuing random PUT
879 * requests every 'frequency' milliseconds.
881 * @param handle handle to the DHT service
882 * @param frequency delay between sending malicious messages
885 GNUNET_DHT_set_malicious_putter (struct GNUNET_DHT_Handle *handle,
886 struct GNUNET_TIME_Relative frequency)
888 if (frequency.value > UINT16_MAX)
893 send_control_message (handle,
894 GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_PUT, frequency.value,
900 * Send a message to the DHT telling it to start dropping
901 * all requests received.
903 * @param handle handle to the DHT service
906 GNUNET_DHT_set_malicious_dropper (struct GNUNET_DHT_Handle *handle)
908 send_control_message (handle,
909 GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_DROP, 0,
915 /* end of dht_api.c */