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
154 * Configuration to use.
156 const struct GNUNET_CONFIGURATION_Handle *cfg;
159 * Socket (if available).
161 struct GNUNET_CLIENT_Connection *client;
164 * Currently pending transmission request (or NULL).
166 struct GNUNET_CLIENT_TransmitHandle *th;
169 * Head of linked list of messages we would like to transmit.
171 struct PendingMessage *pending_head;
174 * Tail of linked list of messages we would like to transmit.
176 struct PendingMessage *pending_tail;
179 * Hash map containing the current outstanding unique requests
180 * (values are of type 'struct GNUNET_DHT_RouteHandle').
182 struct GNUNET_CONTAINER_MultiHashMap *active_requests;
185 * Task for trying to reconnect.
187 GNUNET_SCHEDULER_TaskIdentifier reconnect_task;
190 * How quickly should we retry? Used for exponential back-off on
193 struct GNUNET_TIME_Relative retry_time;
196 * Generator for unique ids.
204 * Transmit the next pending message, called by notify_transmit_ready
207 transmit_pending (void *cls,
213 * Handler for messages received from the DHT service
214 * a demultiplexer which handles numerous message types
218 service_message_handler (void *cls,
219 const struct GNUNET_MessageHeader *msg);
225 * Try to (re)connect to the DHT service.
227 * @return GNUNET_YES on success, GNUNET_NO on failure.
230 try_connect (struct GNUNET_DHT_Handle *handle)
232 if (handle->client != NULL)
234 handle->client = GNUNET_CLIENT_connect ("dht", handle->cfg);
235 if (handle->client == NULL)
237 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
238 _("Failed to connect to the DHT service!\n"));
241 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
242 "Starting to process replies from DHT\n");
243 GNUNET_CLIENT_receive (handle->client,
244 &service_message_handler,
246 GNUNET_TIME_UNIT_FOREVER_REL);
252 * Add the request corresponding to the given route handle
253 * to the pending queue (if it is not already in there).
255 * @param cls the 'struct GNUNET_DHT_Handle*'
256 * @param key key for the request (not used)
257 * @param value the 'struct GNUNET_DHT_RouteHandle*'
258 * @return GNUNET_YES (always)
261 add_request_to_pending (void *cls,
262 const GNUNET_HashCode *key,
265 struct GNUNET_DHT_Handle *handle = cls;
266 struct GNUNET_DHT_RouteHandle *rh = value;
268 if (GNUNET_NO == rh->message->in_pending_queue)
270 GNUNET_CONTAINER_DLL_insert (handle->pending_head,
271 handle->pending_tail,
273 rh->message->in_pending_queue = GNUNET_YES;
280 * Try reconnecting to the dht service.
282 * @param cls GNUNET_DHT_Handle
283 * @param tc scheduler context
286 try_reconnect (void *cls,
287 const struct GNUNET_SCHEDULER_TaskContext *tc)
289 struct GNUNET_DHT_Handle *handle = cls;
291 if (handle->retry_time.rel_value < GNUNET_CONSTANTS_SERVICE_RETRY.rel_value)
292 handle->retry_time = GNUNET_CONSTANTS_SERVICE_RETRY;
294 handle->retry_time = GNUNET_TIME_relative_multiply (handle->retry_time, 2);
295 if (handle->retry_time.rel_value > GNUNET_CONSTANTS_SERVICE_TIMEOUT.rel_value)
296 handle->retry_time = GNUNET_CONSTANTS_SERVICE_TIMEOUT;
297 handle->reconnect_task = GNUNET_SCHEDULER_NO_TASK;
298 handle->client = GNUNET_CLIENT_connect ("dht", handle->cfg);
299 if (handle->client == NULL)
301 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
302 "dht reconnect failed(!)\n");
306 GNUNET_CONTAINER_multihashmap_iterate (handle->active_requests,
307 &add_request_to_pending,
309 if (handle->pending_head == NULL)
312 GNUNET_CLIENT_notify_transmit_ready (handle->client,
313 ntohs(handle->pending_head->msg->size),
314 GNUNET_TIME_UNIT_FOREVER_REL,
322 * Try reconnecting to the DHT service.
324 * @param handle handle to dht to (possibly) disconnect and reconnect
327 do_disconnect (struct GNUNET_DHT_Handle *handle)
329 if (handle->client == NULL)
332 GNUNET_CLIENT_disconnect (handle->client, GNUNET_NO);
333 handle->client = NULL;
334 handle->reconnect_task = GNUNET_SCHEDULER_add_delayed (handle->retry_time,
341 * Try to send messages from list of messages to send
344 process_pending_messages (struct GNUNET_DHT_Handle *handle)
346 struct PendingMessage *head;
348 if (handle->client == NULL)
350 do_disconnect(handle);
353 if (handle->th != NULL)
355 if (NULL == (head = handle->pending_head))
357 handle->th = GNUNET_CLIENT_notify_transmit_ready (handle->client,
358 ntohs (head->msg->size),
359 GNUNET_TIME_UNIT_FOREVER_REL,
363 if (NULL == handle->th)
365 do_disconnect (handle);
372 * Transmit the next pending message, called by notify_transmit_ready
375 transmit_pending (void *cls,
379 struct GNUNET_DHT_Handle *handle = cls;
380 struct PendingMessage *head;
386 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Transmission to DHT service failed! Reconnecting!\n");
387 do_disconnect (handle);
390 if (NULL == (head = handle->pending_head))
393 tsize = ntohs (head->msg->size);
396 process_pending_messages (handle);
399 memcpy (buf, head->msg, tsize);
400 GNUNET_CONTAINER_DLL_remove (handle->pending_head,
401 handle->pending_tail,
403 if (head->timeout_task != GNUNET_SCHEDULER_NO_TASK)
405 GNUNET_SCHEDULER_cancel (head->timeout_task);
406 head->timeout_task = GNUNET_SCHEDULER_NO_TASK;
408 if (NULL != head->cont)
410 GNUNET_SCHEDULER_add_continuation (head->cont,
412 GNUNET_SCHEDULER_REASON_PREREQ_DONE);
414 head->cont_cls = NULL;
416 head->in_pending_queue = GNUNET_NO;
417 if (GNUNET_YES == head->free_on_send)
419 process_pending_messages (handle);
420 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
421 "Forwarded request of %u bytes to DHT service\n",
422 (unsigned int) tsize);
428 * Process a given reply that might match the given
432 process_reply (void *cls,
433 const GNUNET_HashCode *key,
436 const struct GNUNET_DHT_RouteResultMessage *dht_msg = cls;
437 struct GNUNET_DHT_RouteHandle *rh = value;
438 const struct GNUNET_MessageHeader *enc_msg;
441 const struct GNUNET_PeerIdentity **outgoing_path;
442 const struct GNUNET_PeerIdentity *pos;
443 uint32_t outgoing_path_length;
447 uid = GNUNET_ntohll (dht_msg->unique_id);
450 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
451 "Reply UID did not match request UID\n");
454 enc_msg = (const struct GNUNET_MessageHeader *)&dht_msg[1];
455 enc_size = ntohs (enc_msg->size);
456 if (enc_size < sizeof (struct GNUNET_MessageHeader))
461 path_offset = (char *)&dht_msg[1];
462 path_offset += enc_size;
463 pos = (const struct GNUNET_PeerIdentity *) path_offset;
464 outgoing_path_length = ntohl (dht_msg->outgoing_path_length);
465 if (outgoing_path_length * sizeof (struct GNUNET_PeerIdentity) > ntohs(dht_msg->header.size) - enc_size)
471 if (outgoing_path_length > 0)
473 outgoing_path = GNUNET_malloc ((outgoing_path_length + 1) * sizeof (struct GNUNET_PeerIdentity*));
474 for (i = 0; i < outgoing_path_length; i++)
476 outgoing_path[i] = pos;
479 outgoing_path[outgoing_path_length] = NULL;
482 outgoing_path = NULL;
484 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
485 "Processing reply.\n");
486 rh->iter (rh->iter_cls,
490 GNUNET_free_non_null (outgoing_path);
496 * Handler for messages received from the DHT service
497 * a demultiplexer which handles numerous message types
499 * @param cls the 'struct GNUNET_DHT_Handle'
500 * @param msg the incoming message
503 service_message_handler (void *cls,
504 const struct GNUNET_MessageHeader *msg)
506 struct GNUNET_DHT_Handle *handle = cls;
507 const struct GNUNET_DHT_RouteResultMessage *dht_msg;
511 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
512 "Error receiving data from DHT service, reconnecting\n");
513 do_disconnect (handle);
516 if (ntohs (msg->type) != GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_RESULT)
519 do_disconnect (handle);
522 if (ntohs (msg->size) < sizeof (struct GNUNET_DHT_RouteResultMessage))
525 do_disconnect (handle);
528 dht_msg = (const struct GNUNET_DHT_RouteResultMessage *) msg;
529 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
530 "Comparing reply `%s' against %u pending requests.\n",
531 GNUNET_h2s (&dht_msg->key),
532 GNUNET_CONTAINER_multihashmap_size (handle->active_requests));
533 GNUNET_CONTAINER_multihashmap_get_multiple (handle->active_requests,
537 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
538 "Continuing to process replies from DHT\n");
539 GNUNET_CLIENT_receive (handle->client,
540 &service_message_handler,
541 handle, GNUNET_TIME_UNIT_FOREVER_REL);
547 * Initialize the connection with the DHT service.
549 * @param cfg configuration to use
550 * @param ht_len size of the internal hash table to use for
551 * processing multiple GET/FIND requests in parallel
553 * @return handle to the DHT service, or NULL on error
555 struct GNUNET_DHT_Handle *
556 GNUNET_DHT_connect (const struct GNUNET_CONFIGURATION_Handle *cfg,
559 struct GNUNET_DHT_Handle *handle;
561 handle = GNUNET_malloc (sizeof (struct GNUNET_DHT_Handle));
563 handle->uid_gen = GNUNET_CRYPTO_random_u64(GNUNET_CRYPTO_QUALITY_WEAK, UINT64_MAX);
564 handle->active_requests = GNUNET_CONTAINER_multihashmap_create (ht_len);
565 if (GNUNET_NO == try_connect (handle))
567 GNUNET_DHT_disconnect (handle);
575 * Shutdown connection with the DHT service.
577 * @param handle handle of the DHT connection to stop
580 GNUNET_DHT_disconnect (struct GNUNET_DHT_Handle *handle)
582 struct PendingMessage *pm;
583 GNUNET_assert(handle != NULL);
584 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size(handle->active_requests));
585 if (handle->th != NULL)
587 GNUNET_CLIENT_notify_transmit_ready_cancel (handle->th);
590 while (NULL != (pm = handle->pending_head))
592 GNUNET_CONTAINER_DLL_remove (handle->pending_head,
593 handle->pending_tail,
595 GNUNET_assert (GNUNET_YES == pm->free_on_send);
596 if (GNUNET_SCHEDULER_NO_TASK != pm->timeout_task)
597 GNUNET_SCHEDULER_cancel (pm->timeout_task);
598 if (NULL != pm->cont)
599 GNUNET_SCHEDULER_add_continuation (pm->cont,
601 GNUNET_SCHEDULER_REASON_TIMEOUT);
602 pm->in_pending_queue = GNUNET_NO;
605 if (handle->client != NULL)
607 GNUNET_CLIENT_disconnect (handle->client, GNUNET_YES);
608 handle->client = NULL;
610 GNUNET_CONTAINER_multihashmap_destroy(handle->active_requests);
611 GNUNET_free (handle);
617 /* ***** Special low-level API providing generic routing abstraction ***** */
621 * Timeout for the transmission of a fire&forget-request. Clean it up.
623 * @param cls the 'struct PendingMessage'
624 * @param tc scheduler context
627 timeout_route_request (void *cls,
628 const struct GNUNET_SCHEDULER_TaskContext *tc)
630 struct PendingMessage *pending = cls;
631 struct GNUNET_DHT_Handle *handle;
633 if (pending->free_on_send != GNUNET_YES)
635 /* timeouts should only apply to fire & forget requests! */
639 handle = pending->handle;
640 GNUNET_CONTAINER_DLL_remove (handle->pending_head,
641 handle->pending_tail,
643 if (pending->cont != NULL)
644 pending->cont (pending->cont_cls,
646 GNUNET_free (pending);
651 * Initiate a generic DHT route operation.
653 * @param handle handle to the DHT service
654 * @param key the key to look up
655 * @param desired_replication_level how many peers should ultimately receive
656 * this message (advisory only, target may be too high for the
657 * given DHT or not hit exactly).
658 * @param options options for routing
659 * @param enc send the encapsulated message to a peer close to the key
660 * @param iter function to call on each result, NULL if no replies are expected
661 * @param iter_cls closure for iter
662 * @param timeout when to abort with an error if we fail to get
663 * a confirmation for the request (when necessary) or how long
664 * to wait for tramission to the service; only applies
666 * @param cont continuation to call when the request has been transmitted
667 * the first time to the service
668 * @param cont_cls closure for cont
669 * @return handle to stop the request, NULL if the request is "fire and forget"
671 struct GNUNET_DHT_RouteHandle *
672 GNUNET_DHT_route_start (struct GNUNET_DHT_Handle *handle,
673 const GNUNET_HashCode *key,
674 uint32_t desired_replication_level,
675 enum GNUNET_DHT_RouteOption options,
676 const struct GNUNET_MessageHeader *enc,
677 struct GNUNET_TIME_Relative timeout,
678 GNUNET_DHT_ReplyProcessor iter,
680 GNUNET_SCHEDULER_Task cont,
683 struct PendingMessage *pending;
684 struct GNUNET_DHT_RouteMessage *message;
685 struct GNUNET_DHT_RouteHandle *route_handle;
689 esize = ntohs (enc->size);
690 if (sizeof (struct GNUNET_DHT_RouteMessage) + esize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
695 msize = sizeof (struct GNUNET_DHT_RouteMessage) + esize;
696 pending = GNUNET_malloc (sizeof (struct PendingMessage) + msize);
697 message = (struct GNUNET_DHT_RouteMessage*) &pending[1];
698 pending->msg = &message->header;
699 pending->handle = handle;
700 pending->cont = cont;
701 pending->cont_cls = cont_cls;
703 message->header.size = htons (msize);
704 message->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE);
706 message->options = htonl ((uint32_t) options);
707 message->desired_replication_level = htonl (desired_replication_level);
709 message->unique_id = GNUNET_htonll (handle->uid_gen);
710 memcpy (&message[1], enc, esize);
714 route_handle = GNUNET_malloc (sizeof (struct GNUNET_DHT_RouteHandle));
715 route_handle->key = *key;
716 route_handle->iter = iter;
717 route_handle->iter_cls = iter_cls;
718 route_handle->dht_handle = handle;
719 route_handle->uid = handle->uid_gen;
720 route_handle->message = pending;
721 GNUNET_CONTAINER_multihashmap_put (handle->active_requests,
724 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
729 pending->free_on_send = GNUNET_YES;
730 pending->timeout_task = GNUNET_SCHEDULER_add_delayed (timeout,
731 &timeout_route_request,
734 GNUNET_CONTAINER_DLL_insert (handle->pending_head,
735 handle->pending_tail,
737 pending->in_pending_queue = GNUNET_YES;
738 process_pending_messages (handle);
739 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
740 "DHT route start request processed, returning %p\n",
747 * Stop a previously issued routing request
749 * @param route_handle handle to the request to stop
752 GNUNET_DHT_route_stop (struct GNUNET_DHT_RouteHandle *route_handle)
754 struct GNUNET_DHT_Handle *handle;
755 struct PendingMessage *pending;
756 struct GNUNET_DHT_StopMessage *message;
759 handle = route_handle->dht_handle;
760 if (GNUNET_NO == route_handle->message->in_pending_queue)
762 /* need to send stop message */
763 msize = sizeof (struct GNUNET_DHT_StopMessage);
764 pending = GNUNET_malloc (sizeof (struct PendingMessage) +
766 message = (struct GNUNET_DHT_StopMessage*) &pending[1];
767 pending->msg = &message->header;
768 message->header.size = htons (msize);
769 message->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_STOP);
770 message->unique_id = GNUNET_htonll (route_handle->uid);
771 message->key = route_handle->key;
772 pending->handle = handle;
773 pending->free_on_send = GNUNET_YES;
774 pending->in_pending_queue = GNUNET_YES;
775 GNUNET_CONTAINER_DLL_insert (handle->pending_head,
776 handle->pending_tail,
778 process_pending_messages (handle);
782 /* simply remove pending request from message queue before
783 transmission, no need to transmit STOP request! */
784 GNUNET_CONTAINER_DLL_remove (handle->pending_head,
785 handle->pending_tail,
786 route_handle->message);
788 GNUNET_assert (GNUNET_YES ==
789 GNUNET_CONTAINER_multihashmap_remove (route_handle->dht_handle->active_requests,
792 GNUNET_free(route_handle->message);
793 GNUNET_free(route_handle);
794 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
795 "DHT route stop request processed\n");
800 /* ***** Special API for controlling DHT routing maintenance ******* */
804 * Send a control message to the DHT.
806 * @param handle handle to the DHT service
807 * @param command command
808 * @param variable variable to the command
809 * @param cont continuation to call when done (transmitting request to service)
810 * @param cont_cls closure for cont
813 send_control_message (struct GNUNET_DHT_Handle *handle,
816 GNUNET_SCHEDULER_Task cont,
819 struct GNUNET_DHT_ControlMessage *msg;
820 struct PendingMessage *pending;
822 pending = GNUNET_malloc (sizeof (struct PendingMessage) +
823 sizeof(struct GNUNET_DHT_ControlMessage));
824 msg = (struct GNUNET_DHT_ControlMessage*) &pending[1];
825 pending->msg = &msg->header;
826 msg->header.size = htons (sizeof(struct GNUNET_DHT_ControlMessage));
827 msg->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_CONTROL);
828 msg->command = htons (command);
829 msg->variable = htons (variable);
830 pending->free_on_send = GNUNET_YES;
831 pending->cont = cont;
832 pending->cont_cls = cont_cls;
833 pending->in_pending_queue = GNUNET_YES;
834 GNUNET_CONTAINER_DLL_insert (handle->pending_head,
835 handle->pending_tail,
837 process_pending_messages (handle);
842 * Send a message to the DHT telling it to issue a single find
843 * peer request using the peers unique identifier as key. This
844 * is used to fill the routing table, and is normally controlled
845 * by the DHT itself. However, for testing and perhaps more
846 * close control over the DHT, this can be explicitly managed.
848 * @param handle handle to the DHT service
849 * @param cont continuation to call when done (transmitting request to service)
850 * @param cont_cls closure for cont
853 GNUNET_DHT_find_peers (struct GNUNET_DHT_Handle *handle,
854 GNUNET_SCHEDULER_Task cont,
857 send_control_message (handle,
858 GNUNET_MESSAGE_TYPE_DHT_FIND_PEER, 0,
867 * Send a message to the DHT telling it to start issuing random GET
868 * requests every 'frequency' milliseconds.
870 * @param handle handle to the DHT service
871 * @param frequency delay between sending malicious messages
874 GNUNET_DHT_set_malicious_getter (struct GNUNET_DHT_Handle *handle,
875 struct GNUNET_TIME_Relative frequency)
877 if (frequency.rel_value > UINT16_MAX)
882 send_control_message (handle,
883 GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_GET, frequency.rel_value,
888 * Send a message to the DHT telling it to start issuing random PUT
889 * requests every 'frequency' milliseconds.
891 * @param handle handle to the DHT service
892 * @param frequency delay between sending malicious messages
895 GNUNET_DHT_set_malicious_putter (struct GNUNET_DHT_Handle *handle,
896 struct GNUNET_TIME_Relative frequency)
898 if (frequency.rel_value > UINT16_MAX)
904 send_control_message (handle,
905 GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_PUT, frequency.rel_value,
911 * Send a message to the DHT telling it to start dropping
912 * all requests received.
914 * @param handle handle to the DHT service
917 GNUNET_DHT_set_malicious_dropper (struct GNUNET_DHT_Handle *handle)
919 send_control_message (handle,
920 GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_DROP, 0,
926 /* end of dht_api.c */