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.
22 * @file dht/gnunet-service-dht.c
23 * @brief GNUnet DHT service
24 * @author Christian Grothoff
25 * @author Nathan Evans
29 #include "gnunet_block_lib.h"
30 #include "gnunet_client_lib.h"
31 #include "gnunet_getopt_lib.h"
32 #include "gnunet_os_lib.h"
33 #include "gnunet_protocols.h"
34 #include "gnunet_service_lib.h"
35 #include "gnunet_core_service.h"
36 #include "gnunet_signal_lib.h"
37 #include "gnunet_util_lib.h"
38 #include "gnunet_datacache_lib.h"
39 #include "gnunet_transport_service.h"
40 #include "gnunet_hello_lib.h"
41 #include "gnunet_dht_service.h"
42 #include "gnunet_statistics_service.h"
47 #define PRINT_TABLES GNUNET_NO
49 #define REAL_DISTANCE GNUNET_NO
51 #define EXTRA_CHECKS GNUNET_NO
54 * How many buckets will we allow total.
56 #define MAX_BUCKETS sizeof (GNUNET_HashCode) * 8
59 * Should the DHT issue FIND_PEER requests to get better routing tables?
61 #define DEFAULT_DO_FIND_PEER GNUNET_YES
64 * Defines whether find peer requests send their HELLO's outgoing,
65 * or expect replies to contain hellos.
67 #define FIND_PEER_WITH_HELLO GNUNET_YES
70 * What is the maximum number of peers in a given bucket.
72 #define DEFAULT_BUCKET_SIZE 4
74 #define DEFAULT_CORE_QUEUE_SIZE 32
77 * Minimum number of peers we need for "good" routing,
78 * any less than this and we will allow messages to
79 * travel much further through the network!
81 #define MINIMUM_PEER_THRESHOLD 20
83 #define DHT_MAX_RECENT 1000
85 #define FIND_PEER_CALC_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 60)
88 * Default time to wait to send messages on behalf of other peers.
90 #define DHT_DEFAULT_P2P_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 10)
93 * Default importance for handling messages on behalf of other peers.
95 #define DHT_DEFAULT_P2P_IMPORTANCE 0
98 * How long to keep recent requests around by default.
100 #define DEFAULT_RECENT_REMOVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 15)
103 * Default time to wait to send find peer messages sent by the dht service.
105 #define DHT_DEFAULT_FIND_PEER_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
108 * Default importance for find peer messages sent by the dht service.
110 #define DHT_DEFAULT_FIND_PEER_IMPORTANCE 8
113 * Default replication parameter for find peer messages sent by the dht service.
115 #define DHT_DEFAULT_FIND_PEER_REPLICATION 4
118 * Default options for find peer requests sent by the dht service.
120 #define DHT_DEFAULT_FIND_PEER_OPTIONS GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE
121 /*#define DHT_DEFAULT_FIND_PEER_OPTIONS GNUNET_DHT_RO_NONE*/
124 * How long at least to wait before sending another find peer request.
126 #define DHT_MINIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
129 * How long at most to wait before sending another find peer request.
131 #define DHT_MAXIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 8)
134 * How often to update our preference levels for peers in our routing tables.
136 #define DHT_DEFAULT_PREFERENCE_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
139 * How long at most on average will we allow a reply forward to take
140 * (before we quit sending out new requests)
142 #define MAX_REQUEST_TIME GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 1)
145 * How many initial requests to send out (in true Kademlia fashion)
147 #define DEFAULT_KADEMLIA_REPLICATION 3
150 * Default frequency for sending malicious get messages
152 #define DEFAULT_MALICIOUS_GET_FREQUENCY 1000 /* Number of milliseconds */
155 * Default frequency for sending malicious put messages
157 #define DEFAULT_MALICIOUS_PUT_FREQUENCY 1000 /* Default is in milliseconds */
160 #define DHT_DEFAULT_PING_DELAY GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 1)
163 * Real maximum number of hops, at which point we refuse
164 * to forward the message.
166 #define DEFAULT_MAX_HOPS 10
169 * How many time differences between requesting a core send and
170 * the actual callback to remember.
172 #define MAX_REPLY_TIMES 8
174 enum ConvergenceOptions
177 * Use the linear method for convergence.
182 * Converge using a fast converging square
188 * Converge using a slower exponential
191 DHT_CONVERGE_EXPONENTIAL,
194 * Don't do any special convergence, allow
195 * the algorithm to hopefully route to closer
201 * Binary convergence, start routing to closest
202 * only after set number of hops.
208 * Linked list of messages to send to clients.
210 struct P2PPendingMessage
213 * Pointer to next item in the list
215 struct P2PPendingMessage *next;
218 * Pointer to previous item in the list
220 struct P2PPendingMessage *prev;
223 * Message importance level.
225 unsigned int importance;
228 * Time when this request was scheduled to be sent.
230 struct GNUNET_TIME_Absolute scheduled;
233 * How long to wait before sending message.
235 struct GNUNET_TIME_Relative timeout;
238 * Actual message to be sent; // avoid allocation
240 const struct GNUNET_MessageHeader *msg; // msg = (cast) &pm[1]; // memcpy (&pm[1], data, len);
245 * Per-peer information.
250 * Next peer entry (DLL)
252 struct PeerInfo *next;
255 * Prev peer entry (DLL)
257 struct PeerInfo *prev;
260 * Count of outstanding messages for peer.
262 unsigned int pending_count;
265 * Head of pending messages to be sent to this peer.
267 struct P2PPendingMessage *head;
270 * Tail of pending messages to be sent to this peer.
272 struct P2PPendingMessage *tail;
275 * Core handle for sending messages to this peer.
277 struct GNUNET_CORE_TransmitHandle *th;
280 * Task for scheduling message sends.
282 GNUNET_SCHEDULER_TaskIdentifier send_task;
285 * Task for scheduling preference updates
287 GNUNET_SCHEDULER_TaskIdentifier preference_task;
290 * Preference update context
292 struct GNUNET_CORE_InformationRequestContext *info_ctx;
295 * What is the identity of the peer?
297 struct GNUNET_PeerIdentity id;
301 * What is the average latency for replies received?
303 struct GNUNET_TIME_Relative latency;
306 * Transport level distance to peer.
308 unsigned int distance;
312 * Holds matching bits from peer to current target,
313 * used for distance comparisons between peers. May
314 * be considered a really bad idea.
315 * FIXME: remove this value (create struct which holds
316 * a single peerinfo and the matching bits, use
317 * that to pass to comparator)
319 unsigned int matching_bits;
322 * Task for scheduling periodic ping messages for this peer.
324 GNUNET_SCHEDULER_TaskIdentifier ping_task;
328 * Peers are grouped into buckets.
335 struct PeerInfo *head;
340 struct PeerInfo *tail;
343 * Number of peers in the bucket.
345 unsigned int peers_size;
349 * Linked list of messages to send to clients.
351 struct PendingMessage
354 * Pointer to next item in the list
356 struct PendingMessage *next;
359 * Pointer to previous item in the list
361 struct PendingMessage *prev;
364 * Actual message to be sent; // avoid allocation
366 const struct GNUNET_MessageHeader *msg; // msg = (cast) &pm[1]; // memcpy (&pm[1], data, len);
371 * Struct containing information about a client,
372 * handle to connect to it, and any pending messages
373 * that need to be sent to it.
378 * Linked list of active clients
380 struct ClientList *next;
383 * The handle to this client
385 struct GNUNET_SERVER_Client *client_handle;
388 * Handle to the current transmission request, NULL
391 struct GNUNET_CONNECTION_TransmitHandle *transmit_handle;
394 * Linked list of pending messages for this client
396 struct PendingMessage *pending_head;
399 * Tail of linked list of pending messages for this client
401 struct PendingMessage *pending_tail;
406 * Context containing information about a DHT message received.
408 struct DHT_MessageContext
411 * The client this request was received from.
412 * (NULL if received from another peer)
414 struct ClientList *client;
417 * The peer this request was received from.
418 * (NULL if received from local client)
420 const struct GNUNET_PeerIdentity *peer;
423 * Bloomfilter for this routing request.
425 struct GNUNET_CONTAINER_BloomFilter *bloom;
428 * extended query (see gnunet_block_lib.h).
433 * Bloomfilter to filter out duplicate replies.
435 struct GNUNET_CONTAINER_BloomFilter *reply_bf;
438 * The key this request was about
443 * How long should we wait to transmit this request?
445 struct GNUNET_TIME_Relative timeout;
448 * The unique identifier of this request
453 * Number of bytes in xquery.
458 * Mutator value for the reply_bf, see gnunet_block_lib.h
460 uint32_t reply_bf_mutator;
463 * Desired replication level
465 uint32_t replication;
468 * Network size estimate, either ours or the sum of
469 * those routed to thus far. =~ Log of number of peers
470 * chosen from for this request.
472 uint32_t network_size;
475 * Any message options for this request
477 uint32_t msg_options;
480 * How many hops has the message already traversed?
485 * How many peer identities are present in the path history?
487 uint32_t path_history_len;
495 * How important is this message?
497 unsigned int importance;
500 * Should we (still) forward the request on to other peers?
505 * Did we forward this message? (may need to remember it!)
510 * Are we the closest known peer to this key (out of our neighbors?)
516 * Record used for remembering what peers are waiting for what
517 * responses (based on search key).
519 struct DHTRouteSource
524 struct DHTRouteSource *next;
529 struct DHTRouteSource *prev;
532 * Source of the request. Replies should be forwarded to
535 struct GNUNET_PeerIdentity source;
538 * If this was a local request, remember the client; otherwise NULL.
540 struct ClientList *client;
543 * Pointer to this nodes heap location (for removal)
545 struct GNUNET_CONTAINER_HeapNode *hnode;
548 * Back pointer to the record storing this information.
550 struct DHTQueryRecord *record;
553 * Task to remove this entry on timeout.
555 GNUNET_SCHEDULER_TaskIdentifier delete_task;
558 * Bloomfilter of peers we have already sent back as
559 * replies to the initial request. Allows us to not
560 * forward the same peer multiple times for a find peer
563 struct GNUNET_CONTAINER_BloomFilter *find_peers_responded;
568 * Entry in the DHT routing table.
570 struct DHTQueryRecord
573 * Head of DLL for result forwarding.
575 struct DHTRouteSource *head;
578 * Tail of DLL for result forwarding.
580 struct DHTRouteSource *tail;
583 * Key that the record concerns.
588 * GET message of this record (what we already forwarded?).
590 //DV_DHT_MESSAGE get; Try to get away with not saving this.
593 * Bloomfilter of the peers we've replied to so far
595 //struct GNUNET_BloomFilter *bloom_results; Don't think we need this, just remove from DLL on response.
600 * Context used to calculate the number of find peer messages
601 * per X time units since our last scheduled find peer message
602 * was sent. If we have seen too many messages, delay or don't
605 struct FindPeerMessageContext
609 struct GNUNET_TIME_Absolute start;
611 struct GNUNET_TIME_Absolute end;
615 * DHT Routing results structure
620 * Min heap for removal upon reaching limit
622 struct GNUNET_CONTAINER_Heap *minHeap;
625 * Hashmap for fast key based lookup
627 struct GNUNET_CONTAINER_MultiHashMap *hashmap;
632 * DHT structure for recent requests.
634 struct RecentRequests
637 * Min heap for removal upon reaching limit
639 struct GNUNET_CONTAINER_Heap *minHeap;
642 * Hashmap for key based lookup
644 struct GNUNET_CONTAINER_MultiHashMap *hashmap;
650 * Position of this node in the min heap.
652 struct GNUNET_CONTAINER_HeapNode *heap_node;
655 * Bloomfilter containing entries for peers
656 * we forwarded this request to.
658 struct GNUNET_CONTAINER_BloomFilter *bloom;
661 * Timestamp of this request, for ordering
664 struct GNUNET_TIME_Absolute timestamp;
667 * Key of this request.
672 * Unique identifier for this request.
677 * Task to remove this entry on timeout.
679 GNUNET_SCHEDULER_TaskIdentifier remove_task;
682 struct RepublishContext
697 * Which kind of convergence will we be using?
699 static enum ConvergenceOptions converge_option;
702 * Modifier for the convergence function
704 static float converge_modifier;
707 * Recent requests by hash/uid and by time inserted.
709 static struct RecentRequests recent;
712 * Context to use to calculate find peer rates.
714 static struct FindPeerMessageContext find_peer_context;
717 * Don't use our routing algorithm, always route
718 * to closest peer; initially send requests to 3
721 static unsigned int strict_kademlia;
724 * Routing option to end routing when closest peer found.
726 static unsigned int stop_on_closest;
729 * Routing option to end routing when data is found.
731 static unsigned int stop_on_found;
734 * Whether DHT needs to manage find peer requests, or
735 * an external force will do it on behalf of the DHT.
737 static unsigned int do_find_peer;
740 * Once we have stored an item in the DHT, refresh it
741 * according to our republish interval.
743 static unsigned int do_republish;
746 * Use exactly the forwarding formula as described in
747 * the paper if set to GNUNET_YES, otherwise use the
748 * slightly modified version.
750 static unsigned int paper_forwarding;
753 * PUT Peer Identities of peers we know about into
756 static unsigned int put_peer_identities;
759 * Use the "real" distance metric when selecting the
760 * next routing hop. Can be less accurate.
762 static unsigned int use_real_distance;
765 * How many peers have we added since we sent out our last
768 static unsigned int newly_found_peers;
771 * Container of active queries we should remember
773 static struct DHTResults forward_list;
776 * Handle to the datacache service (for inserting/retrieving data)
778 static struct GNUNET_DATACACHE_Handle *datacache;
781 * Handle for the statistics service.
783 struct GNUNET_STATISTICS_Handle *stats;
787 * The configuration the DHT service is running with
789 static const struct GNUNET_CONFIGURATION_Handle *cfg;
792 * Handle to the core service
794 static struct GNUNET_CORE_Handle *coreAPI;
797 * Handle to the transport service, for getting our hello
799 static struct GNUNET_TRANSPORT_Handle *transport_handle;
802 * The identity of our peer.
804 static struct GNUNET_PeerIdentity my_identity;
807 * Short id of the peer, for printing
809 static char *my_short_id;
814 static struct GNUNET_MessageHeader *my_hello;
817 * Task to run when we shut down, cleaning up all our trash
819 static GNUNET_SCHEDULER_TaskIdentifier cleanup_task;
822 * The lowest currently used bucket.
824 static unsigned int lowest_bucket; /* Initially equal to MAX_BUCKETS - 1 */
827 * The maximum number of hops before we stop routing messages.
829 static unsigned long long max_hops;
832 * How often to republish content we have previously stored.
834 static struct GNUNET_TIME_Relative dht_republish_frequency;
837 * GNUNET_YES to stop at max_hops, GNUNET_NO to heuristically decide when to stop forwarding.
839 static int use_max_hops;
842 * The buckets (Kademlia routing table, complete with growth).
843 * Array of size MAX_BUCKET_SIZE.
845 static struct PeerBucket k_buckets[MAX_BUCKETS]; /* From 0 to MAX_BUCKETS - 1 */
848 * Hash map of all known peers, for easy removal from k_buckets on disconnect.
850 static struct GNUNET_CONTAINER_MultiHashMap *all_known_peers;
853 * Recently seen find peer requests.
855 static struct GNUNET_CONTAINER_MultiHashMap *recent_find_peer_requests;
858 * Maximum size for each bucket.
860 static unsigned int bucket_size = DEFAULT_BUCKET_SIZE; /* Initially equal to DEFAULT_BUCKET_SIZE */
863 * List of active clients.
865 static struct ClientList *client_list;
868 * Handle to the DHT logger.
870 static struct GNUNET_DHTLOG_Handle *dhtlog_handle;
873 * Whether or not to send routing debugging information
874 * to the dht logging server
876 static unsigned int debug_routes;
879 * Whether or not to send FULL route information to
882 static unsigned int debug_routes_extended;
885 * GNUNET_YES or GNUNET_NO, whether or not to act as
886 * a malicious node which drops all messages
888 static unsigned int malicious_dropper;
891 * GNUNET_YES or GNUNET_NO, whether or not to act as
892 * a malicious node which sends out lots of GETS
894 static unsigned int malicious_getter;
897 * GNUNET_YES or GNUNET_NO, whether or not to act as
898 * a malicious node which sends out lots of PUTS
900 static unsigned int malicious_putter;
903 * Frequency for malicious get requests.
905 static unsigned long long malicious_get_frequency;
908 * Frequency for malicious put requests.
910 static unsigned long long malicious_put_frequency;
913 * Kademlia replication
915 static unsigned long long kademlia_replication;
918 * Reply times for requests, if we are busy, don't send any
921 static struct GNUNET_TIME_Relative reply_times[MAX_REPLY_TIMES];
924 * Current counter for replies.
926 static unsigned int reply_counter;
929 * Our handle to the BLOCK library.
931 static struct GNUNET_BLOCK_Context *block_context;
935 * Forward declaration.
937 static size_t send_generic_reply (void *cls, size_t size, void *buf);
940 /** Declare here so retry_core_send is aware of it */
941 static size_t core_transmit_notify (void *cls, size_t size, void *buf);
944 * Convert unique ID to hash code.
946 * @param uid unique ID to convert
947 * @param hash set to uid (extended with zeros)
950 hash_from_uid (uint64_t uid, GNUNET_HashCode * hash)
952 memset (hash, 0, sizeof (GNUNET_HashCode));
953 *((uint64_t *) hash) = uid;
958 * Calculate the average send time between messages so that we can
959 * ignore certain requests if we get too busy.
961 * @return the average time between asking core to send a message
962 * and when the buffer for copying it is passed
964 static struct GNUNET_TIME_Relative
965 get_average_send_delay ()
968 unsigned int divisor;
969 struct GNUNET_TIME_Relative average_time;
970 average_time = GNUNET_TIME_relative_get_zero ();
972 for (i = 0; i < MAX_REPLY_TIMES; i++)
974 average_time = GNUNET_TIME_relative_add (average_time, reply_times[i]);
975 if (reply_times[i].abs_value == (uint64_t) 0)
985 average_time = GNUNET_TIME_relative_divide (average_time, divisor);
987 "Avg send delay: %u sends is %llu\n",
988 divisor, (unsigned long long) average_time.abs_value);
994 * Given the largest send delay, artificially decrease it
995 * so the next time around we may have a chance at sending
999 decrease_max_send_delay (struct GNUNET_TIME_Relative max_time)
1002 for (i = 0; i < MAX_REPLY_TIMES; i++)
1004 if (reply_times[i].rel_value == max_time.rel_value)
1006 reply_times[i].rel_value = reply_times[i].rel_value / 2;
1013 * Find the maximum send time of the recently sent values.
1015 * @return the average time between asking core to send a message
1016 * and when the buffer for copying it is passed
1018 static struct GNUNET_TIME_Relative
1019 get_max_send_delay ()
1022 struct GNUNET_TIME_Relative max_time;
1023 max_time = GNUNET_TIME_relative_get_zero ();
1025 for (i = 0; i < MAX_REPLY_TIMES; i++)
1027 if (reply_times[i].rel_value > max_time.rel_value)
1028 max_time.rel_value = reply_times[i].rel_value;
1031 if (max_time.rel_value > MAX_REQUEST_TIME.rel_value)
1032 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Max send delay was %llu\n",
1033 (unsigned long long) max_time.rel_value);
1039 increment_stats (const char *value)
1043 GNUNET_STATISTICS_update (stats, value, 1, GNUNET_NO);
1048 * Try to send another message from our core send list
1051 try_core_send (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
1053 struct PeerInfo *peer = cls;
1054 struct P2PPendingMessage *pending;
1057 peer->send_task = GNUNET_SCHEDULER_NO_TASK;
1059 if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN)
1062 if (peer->th != NULL)
1063 return; /* Message send already in progress */
1065 pending = peer->head;
1066 if (pending != NULL)
1068 ssize = ntohs (pending->msg->size);
1070 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1071 "`%s:%s': Calling notify_transmit_ready with size %d for peer %s\n",
1072 my_short_id, "DHT", ssize, GNUNET_i2s (&peer->id));
1074 pending->scheduled = GNUNET_TIME_absolute_get ();
1076 if (reply_counter >= MAX_REPLY_TIMES)
1079 GNUNET_CORE_notify_transmit_ready (coreAPI,
1081 pending->importance,
1082 pending->timeout, &peer->id, ssize,
1083 &core_transmit_notify, peer);
1084 if (peer->th == NULL)
1085 increment_stats ("# notify transmit ready failed");
1090 * Function called to send a request out to another peer.
1091 * Called both for locally initiated requests and those
1092 * received from other peers.
1094 * @param msg the encapsulated message
1095 * @param peer the peer to forward the message to
1096 * @param msg_ctx the context of the message (hop count, bloom, etc.)
1099 forward_result_message (const struct GNUNET_MessageHeader *msg,
1100 struct PeerInfo *peer,
1101 struct DHT_MessageContext *msg_ctx)
1103 struct GNUNET_DHT_P2PRouteResultMessage *result_message;
1104 struct P2PPendingMessage *pending;
1113 increment_stats (STAT_RESULT_FORWARDS);
1115 sizeof (struct GNUNET_DHT_P2PRouteResultMessage) + ntohs (msg->size) + (sizeof(struct GNUNET_PeerIdentity) * msg_ctx->path_history_len);
1116 GNUNET_assert (msize <= GNUNET_SERVER_MAX_MESSAGE_SIZE);
1117 psize = sizeof (struct P2PPendingMessage) + msize;
1118 pending = GNUNET_malloc (psize);
1119 pending->msg = (struct GNUNET_MessageHeader *) &pending[1];
1120 pending->importance = DHT_SEND_PRIORITY;
1121 pending->timeout = GNUNET_TIME_relative_get_forever ();
1122 result_message = (struct GNUNET_DHT_P2PRouteResultMessage *) pending->msg;
1123 result_message->header.size = htons (msize);
1124 result_message->header.type =
1125 htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ROUTE_RESULT);
1126 result_message->outgoing_path_length = htonl (msg_ctx->path_history_len);
1127 if (msg_ctx->path_history_len > 0)
1129 /* End of pending is where enc_msg starts */
1130 path_start = (char *)&pending[1];
1131 /* Offset by the size of the enc_msg */
1132 path_start += ntohs (msg->size);
1133 memcpy(path_start, msg_ctx->path_history, msg_ctx->path_history_len * (sizeof(struct GNUNET_PeerIdentity)));
1135 for (i = 0; i < msg_ctx->path_history_len; i++)
1137 path_offset = &msg_ctx->path_history[i * sizeof(struct GNUNET_PeerIdentity)];
1138 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "(forward_result) Key %s Found peer %d:%s\n", GNUNET_h2s(&msg_ctx->key), i, GNUNET_i2s((struct GNUNET_PeerIdentity *)path_offset));
1142 result_message->options = htonl (msg_ctx->msg_options);
1143 result_message->hop_count = htonl (msg_ctx->hop_count + 1);
1144 GNUNET_assert (GNUNET_OK ==
1145 GNUNET_CONTAINER_bloomfilter_get_raw_data (msg_ctx->bloom,
1149 result_message->unique_id = GNUNET_htonll (msg_ctx->unique_id);
1150 memcpy (&result_message->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
1151 /* Copy the enc_msg, then the path history as well! */
1152 memcpy (&result_message[1], msg, ntohs (msg->size));
1153 path_offset = (char *)&result_message[1];
1154 path_offset += ntohs (msg->size);
1155 /* If we have path history, copy it to the end of the whole thing */
1156 if (msg_ctx->path_history_len > 0)
1157 memcpy(path_offset, msg_ctx->path_history, msg_ctx->path_history_len * (sizeof(struct GNUNET_PeerIdentity)));
1159 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1160 "%s:%s Adding pending message size %d for peer %s\n",
1161 my_short_id, "DHT", msize, GNUNET_i2s (&peer->id));
1163 peer->pending_count++;
1164 increment_stats ("# pending messages scheduled");
1165 GNUNET_CONTAINER_DLL_insert_after (peer->head, peer->tail, peer->tail,
1167 if (peer->send_task == GNUNET_SCHEDULER_NO_TASK)
1168 peer->send_task = GNUNET_SCHEDULER_add_now (&try_core_send, peer);
1173 * Called when core is ready to send a message we asked for
1174 * out to the destination.
1176 * @param cls closure (NULL)
1177 * @param size number of bytes available in buf
1178 * @param buf where the callee should write the message
1179 * @return number of bytes written to buf
1182 core_transmit_notify (void *cls, size_t size, void *buf)
1184 struct PeerInfo *peer = cls;
1186 struct P2PPendingMessage *pending;
1193 /* client disconnected */
1195 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "`%s:%s': buffer was NULL\n",
1196 my_short_id, "DHT");
1201 if (peer->head == NULL)
1205 pending = peer->head;
1207 reply_times[reply_counter] =
1208 GNUNET_TIME_absolute_get_difference (pending->scheduled,
1209 GNUNET_TIME_absolute_get ());
1210 msize = ntohs (pending->msg->size);
1214 memcpy (cbuf, pending->msg, msize);
1215 peer->pending_count--;
1216 increment_stats ("# pending messages sent");
1217 GNUNET_assert (peer->pending_count >= 0);
1218 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1219 GNUNET_free (pending);
1222 while (NULL != pending &&
1223 (size - off >= (msize = ntohs (pending->msg->size))))
1225 memcpy (&cbuf[off], pending->msg, msize);
1227 peer->pending_count--;
1228 increment_stats ("# pending messages sent");
1229 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1230 GNUNET_free (pending);
1231 pending = peer->head;
1234 if ((peer->head != NULL) && (peer->send_task == GNUNET_SCHEDULER_NO_TASK))
1235 peer->send_task = GNUNET_SCHEDULER_add_now (&try_core_send, peer);
1242 * Compute the distance between have and target as a 32-bit value.
1243 * Differences in the lower bits must count stronger than differences
1244 * in the higher bits.
1246 * @return 0 if have==target, otherwise a number
1247 * that is larger as the distance between
1248 * the two hash codes increases
1251 distance (const GNUNET_HashCode * target, const GNUNET_HashCode * have)
1253 unsigned int bucket;
1258 /* We have to represent the distance between two 2^9 (=512)-bit
1259 numbers as a 2^5 (=32)-bit number with "0" being used for the
1260 two numbers being identical; furthermore, we need to
1261 guarantee that a difference in the number of matching
1262 bits is always represented in the result.
1264 We use 2^32/2^9 numerical values to distinguish between
1265 hash codes that have the same LSB bit distance and
1266 use the highest 2^9 bits of the result to signify the
1267 number of (mis)matching LSB bits; if we have 0 matching
1268 and hence 512 mismatching LSB bits we return -1 (since
1269 512 itself cannot be represented with 9 bits) */
1271 /* first, calculate the most significant 9 bits of our
1272 result, aka the number of LSBs */
1273 bucket = GNUNET_CRYPTO_hash_matching_bits (target, have);
1274 /* bucket is now a value between 0 and 512 */
1276 return 0; /* perfect match */
1278 return (unsigned int) -1; /* LSB differs; use max (if we did the bit-shifting
1279 below, we'd end up with max+1 (overflow)) */
1281 /* calculate the most significant bits of the final result */
1282 msb = (512 - bucket) << (32 - 9);
1283 /* calculate the 32-9 least significant bits of the final result by
1284 looking at the differences in the 32-9 bits following the
1285 mismatching bit at 'bucket' */
1287 for (i = bucket + 1;
1288 (i < sizeof (GNUNET_HashCode) * 8) && (i < bucket + 1 + 32 - 9); i++)
1290 if (GNUNET_CRYPTO_hash_get_bit (target, i) !=
1291 GNUNET_CRYPTO_hash_get_bit (have, i))
1292 lsb |= (1 << (bucket + 32 - 9 - i)); /* first bit set will be 10,
1293 last bit set will be 31 -- if
1294 i does not reach 512 first... */
1300 * Return a number that is larger the closer the
1301 * "have" GNUNET_hash code is to the "target".
1303 * @return inverse distance metric, non-zero.
1304 * Must fudge the value if NO bits match.
1307 inverse_distance (const GNUNET_HashCode * target,
1308 const GNUNET_HashCode * have)
1310 if (GNUNET_CRYPTO_hash_matching_bits (target, have) == 0)
1311 return 1; /* Never return 0! */
1312 return ((unsigned int) -1) - distance (target, have);
1316 * Find the optimal bucket for this key, regardless
1317 * of the current number of buckets in use.
1319 * @param hc the hashcode to compare our identity to
1321 * @return the proper bucket index, or GNUNET_SYSERR
1322 * on error (same hashcode)
1325 find_bucket (const GNUNET_HashCode * hc)
1329 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey, hc);
1330 if (bits == MAX_BUCKETS)
1331 return GNUNET_SYSERR;
1332 return MAX_BUCKETS - bits - 1;
1336 * Find which k-bucket this peer should go into,
1337 * taking into account the size of the k-bucket
1338 * array. This means that if more bits match than
1339 * there are currently buckets, lowest_bucket will
1342 * @param hc GNUNET_HashCode we are finding the bucket for.
1344 * @return the proper bucket index for this key,
1345 * or GNUNET_SYSERR on error (same hashcode)
1348 find_current_bucket (const GNUNET_HashCode * hc)
1351 actual_bucket = find_bucket (hc);
1353 if (actual_bucket == GNUNET_SYSERR) /* hc and our peer identity match! */
1354 return lowest_bucket;
1355 else if (actual_bucket < lowest_bucket) /* actual_bucket not yet used */
1356 return lowest_bucket;
1358 return actual_bucket;
1363 * Find a routing table entry from a peer identity
1365 * @param peer the peer to look up
1367 * @return the bucket number holding the peer, GNUNET_SYSERR if not found
1370 find_bucket_by_peer (const struct PeerInfo *peer)
1373 struct PeerInfo *pos;
1375 for (bucket = lowest_bucket; bucket < MAX_BUCKETS - 1; bucket++)
1377 pos = k_buckets[bucket].head;
1386 return GNUNET_SYSERR; /* No such peer. */
1392 * Print the complete routing table for this peer.
1395 print_routing_table ()
1398 struct PeerInfo *pos;
1399 char char_buf[30000];
1401 memset (char_buf, 0, sizeof (char_buf));
1404 sprintf (&char_buf[char_pos], "Printing routing table for peer %s\n",
1406 //fprintf(stderr, "Printing routing table for peer %s\n", my_short_id);
1407 for (bucket = lowest_bucket; bucket < MAX_BUCKETS; bucket++)
1409 pos = k_buckets[bucket].head;
1410 char_pos += sprintf (&char_buf[char_pos], "Bucket %d:\n", bucket);
1411 //fprintf(stderr, "Bucket %d:\n", bucket);
1414 //fprintf(stderr, "\tPeer %s, best bucket %d, %d bits match\n", GNUNET_i2s(&pos->id), find_bucket(&pos->id.hashPubKey), GNUNET_CRYPTO_hash_matching_bits(&pos->id.hashPubKey, &my_identity.hashPubKey));
1416 sprintf (&char_buf[char_pos],
1417 "\tPeer %s, best bucket %d, %d bits match\n",
1418 GNUNET_i2s (&pos->id), find_bucket (&pos->id.hashPubKey),
1419 GNUNET_CRYPTO_hash_matching_bits (&pos->id.hashPubKey,
1425 fprintf (stderr, "%s", char_buf);
1431 * Find a routing table entry from a peer identity
1433 * @param peer the peer identity to look up
1435 * @return the routing table entry, or NULL if not found
1437 static struct PeerInfo *
1438 find_peer_by_id (const struct GNUNET_PeerIdentity *peer)
1441 struct PeerInfo *pos;
1442 bucket = find_current_bucket (&peer->hashPubKey);
1444 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1447 pos = k_buckets[bucket].head;
1450 if (0 == memcmp (&pos->id, peer, sizeof (struct GNUNET_PeerIdentity)))
1454 return NULL; /* No such peer. */
1457 /* Forward declaration */
1459 update_core_preference (void *cls,
1460 const struct GNUNET_SCHEDULER_TaskContext *tc);
1462 * Function called with statistics about the given peer.
1464 * @param cls closure
1465 * @param peer identifies the peer
1466 * @param bpm_out set to the current bandwidth limit (sending) for this peer
1467 * @param amount set to the amount that was actually reserved or unreserved;
1468 * either the full requested amount or zero (no partial reservations)
1469 * @param res_delay if the reservation could not be satisfied (amount was 0), how
1470 * long should the client wait until re-trying?
1471 * @param preference current traffic preference for the given peer
1474 update_core_preference_finish (void *cls,
1475 const struct GNUNET_PeerIdentity *peer,
1476 struct GNUNET_BANDWIDTH_Value32NBO bpm_out,
1478 struct GNUNET_TIME_Relative res_delay,
1479 uint64_t preference)
1481 struct PeerInfo *peer_info = cls;
1482 peer_info->info_ctx = NULL;
1483 GNUNET_SCHEDULER_add_delayed (DHT_DEFAULT_PREFERENCE_INTERVAL,
1484 &update_core_preference, peer_info);
1488 update_core_preference (void *cls,
1489 const struct GNUNET_SCHEDULER_TaskContext *tc)
1491 struct PeerInfo *peer = cls;
1492 uint64_t preference;
1493 unsigned int matching;
1494 if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN)
1499 GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey,
1500 &peer->id.hashPubKey);
1504 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1505 "Peer identifier matches by %u bits, only shifting as much as we can!\n",
1510 preference = 1LL << matching;
1511 peer->info_ctx = GNUNET_CORE_peer_change_preference (coreAPI,
1513 GNUNET_TIME_relative_get_forever
1515 GNUNET_BANDWIDTH_value_init
1518 &update_core_preference_finish,
1523 * Really add a peer to a bucket (only do assertions
1526 * @param peer GNUNET_PeerIdentity of the peer to add
1527 * @param bucket the already figured out bucket to add
1529 * @param atsi performance information
1531 * @return the newly added PeerInfo
1533 static struct PeerInfo *
1534 add_peer (const struct GNUNET_PeerIdentity *peer,
1535 unsigned int bucket,
1536 const struct GNUNET_TRANSPORT_ATS_Information *atsi)
1538 struct PeerInfo *new_peer;
1539 GNUNET_assert (bucket < MAX_BUCKETS);
1540 GNUNET_assert (peer != NULL);
1541 new_peer = GNUNET_malloc (sizeof (struct PeerInfo));
1543 new_peer->latency = latency;
1544 new_peer->distance = distance;
1547 memcpy (&new_peer->id, peer, sizeof (struct GNUNET_PeerIdentity));
1549 GNUNET_CONTAINER_DLL_insert_after (k_buckets[bucket].head,
1550 k_buckets[bucket].tail,
1551 k_buckets[bucket].tail, new_peer);
1552 k_buckets[bucket].peers_size++;
1554 #if DO_UPDATE_PREFERENCE
1555 if ((GNUNET_CRYPTO_hash_matching_bits
1556 (&my_identity.hashPubKey, &peer->hashPubKey) > 0)
1557 && (k_buckets[bucket].peers_size <= bucket_size))
1560 new_peer->preference_task =
1561 GNUNET_SCHEDULER_add_now (&update_core_preference, new_peer);
1569 * Given a peer and its corresponding bucket,
1570 * remove it from that bucket. Does not free
1571 * the PeerInfo struct, nor cancel messages
1572 * or free messages waiting to be sent to this
1575 * @param peer the peer to remove
1576 * @param bucket the bucket the peer belongs to
1579 remove_peer (struct PeerInfo *peer, unsigned int bucket)
1581 GNUNET_assert (k_buckets[bucket].peers_size > 0);
1582 GNUNET_CONTAINER_DLL_remove (k_buckets[bucket].head,
1583 k_buckets[bucket].tail, peer);
1584 k_buckets[bucket].peers_size--;
1586 if ((bucket == lowest_bucket) && (k_buckets[lowest_bucket].peers_size == 0)
1587 && (lowest_bucket < MAX_BUCKETS - 1))
1593 * Removes peer from a bucket, then frees associated
1594 * resources and frees peer.
1596 * @param peer peer to be removed and freed
1597 * @param bucket which bucket this peer belongs to
1600 delete_peer (struct PeerInfo *peer, unsigned int bucket)
1602 struct P2PPendingMessage *pos;
1603 struct P2PPendingMessage *next;
1605 struct PeerInfo *peer_pos;
1607 peer_pos = k_buckets[bucket].head;
1608 while ((peer_pos != NULL) && (peer_pos != peer))
1609 peer_pos = peer_pos->next;
1610 if (peer_pos == NULL)
1612 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1613 "%s:%s: Expected peer `%s' in bucket %d\n", my_short_id,
1614 "DHT", GNUNET_i2s (&peer->id), bucket);
1615 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1616 "%s:%s: Lowest bucket: %d, find_current_bucket: %d, peer resides in bucket: %d\n",
1617 my_short_id, "DHT", lowest_bucket,
1618 find_current_bucket (&peer->id.hashPubKey),
1619 find_bucket_by_peer (peer));
1621 GNUNET_assert (peer_pos != NULL);
1623 remove_peer (peer, bucket); /* First remove the peer from its bucket */
1625 if (peer->send_task != GNUNET_SCHEDULER_NO_TASK)
1626 GNUNET_SCHEDULER_cancel (peer->send_task);
1627 if ((peer->th != NULL) && (coreAPI != NULL))
1628 GNUNET_CORE_notify_transmit_ready_cancel (peer->th);
1631 while (pos != NULL) /* Remove any pending messages for this peer */
1634 ("# dht pending messages discarded (due to disconnect/shutdown)");
1640 GNUNET_assert (GNUNET_CONTAINER_multihashmap_contains
1641 (all_known_peers, &peer->id.hashPubKey));
1642 GNUNET_assert (GNUNET_YES ==
1643 GNUNET_CONTAINER_multihashmap_remove (all_known_peers,
1644 &peer->id.hashPubKey,
1651 * Iterator over hash map entries.
1653 * @param cls closure
1654 * @param key current key code
1655 * @param value PeerInfo of the peer to move to new lowest bucket
1656 * @return GNUNET_YES if we should continue to
1661 move_lowest_bucket (void *cls, const GNUNET_HashCode * key, void *value)
1663 struct PeerInfo *peer = value;
1666 GNUNET_assert (lowest_bucket > 0);
1667 new_bucket = lowest_bucket - 1;
1668 remove_peer (peer, lowest_bucket);
1669 GNUNET_CONTAINER_DLL_insert_after (k_buckets[new_bucket].head,
1670 k_buckets[new_bucket].tail,
1671 k_buckets[new_bucket].tail, peer);
1672 k_buckets[new_bucket].peers_size++;
1678 * The current lowest bucket is full, so change the lowest
1679 * bucket to the next lower down, and move any appropriate
1680 * entries in the current lowest bucket to the new bucket.
1683 enable_next_bucket ()
1685 struct GNUNET_CONTAINER_MultiHashMap *to_remove;
1686 struct PeerInfo *pos;
1687 GNUNET_assert (lowest_bucket > 0);
1688 to_remove = GNUNET_CONTAINER_multihashmap_create (bucket_size);
1689 pos = k_buckets[lowest_bucket].head;
1692 fprintf (stderr, "Printing RT before new bucket\n");
1693 print_routing_table ();
1695 /* Populate the array of peers which should be in the next lowest bucket */
1698 if (find_bucket (&pos->id.hashPubKey) < lowest_bucket)
1699 GNUNET_CONTAINER_multihashmap_put (to_remove, &pos->id.hashPubKey,
1701 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
1705 /* Remove peers from lowest bucket, insert into next lowest bucket */
1706 GNUNET_CONTAINER_multihashmap_iterate (to_remove, &move_lowest_bucket,
1708 GNUNET_CONTAINER_multihashmap_destroy (to_remove);
1709 lowest_bucket = lowest_bucket - 1;
1711 fprintf (stderr, "Printing RT after new bucket\n");
1712 print_routing_table ();
1717 * Find the closest peer in our routing table to the
1720 * @return The closest peer in our routing table to the
1721 * key, or NULL on error.
1723 static struct PeerInfo *
1724 find_closest_peer (const GNUNET_HashCode * hc)
1726 struct PeerInfo *pos;
1727 struct PeerInfo *current_closest;
1728 unsigned int lowest_distance;
1729 unsigned int temp_distance;
1733 lowest_distance = -1;
1735 if (k_buckets[lowest_bucket].peers_size == 0)
1738 current_closest = NULL;
1739 for (bucket = lowest_bucket; bucket < MAX_BUCKETS; bucket++)
1741 pos = k_buckets[bucket].head;
1743 while ((pos != NULL) && (count < bucket_size))
1745 temp_distance = distance (&pos->id.hashPubKey, hc);
1746 if (temp_distance <= lowest_distance)
1748 lowest_distance = temp_distance;
1749 current_closest = pos;
1755 GNUNET_assert (current_closest != NULL);
1756 return current_closest;
1761 * Function called to send a request out to another peer.
1762 * Called both for locally initiated requests and those
1763 * received from other peers.
1765 * @param msg the encapsulated message
1766 * @param peer the peer to forward the message to
1767 * @param msg_ctx the context of the message (hop count, bloom, etc.)
1770 forward_message (const struct GNUNET_MessageHeader *msg,
1771 struct PeerInfo *peer, struct DHT_MessageContext *msg_ctx)
1773 struct GNUNET_DHT_P2PRouteMessage *route_message;
1774 struct P2PPendingMessage *pending;
1779 increment_stats (STAT_ROUTE_FORWARDS);
1780 GNUNET_assert (peer != NULL);
1781 if ((msg_ctx->closest != GNUNET_YES)
1782 && (peer == find_closest_peer (&msg_ctx->key)))
1783 increment_stats (STAT_ROUTE_FORWARDS_CLOSEST);
1785 msize = sizeof (struct GNUNET_DHT_P2PRouteMessage) + ntohs (msg->size) + (msg_ctx->path_history_len * sizeof(struct GNUNET_PeerIdentity));
1786 GNUNET_assert (msize <= GNUNET_SERVER_MAX_MESSAGE_SIZE);
1787 psize = sizeof (struct P2PPendingMessage) + msize;
1788 pending = GNUNET_malloc (psize);
1789 pending->msg = (struct GNUNET_MessageHeader *) &pending[1];
1790 pending->importance = msg_ctx->importance;
1791 pending->timeout = msg_ctx->timeout;
1792 route_message = (struct GNUNET_DHT_P2PRouteMessage *) pending->msg;
1793 route_message->header.size = htons (msize);
1794 route_message->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ROUTE);
1795 route_message->options = htonl (msg_ctx->msg_options);
1796 route_message->hop_count = htonl (msg_ctx->hop_count + 1);
1797 route_message->network_size = htonl (msg_ctx->network_size);
1798 route_message->desired_replication_level = htonl (msg_ctx->replication);
1799 route_message->unique_id = GNUNET_htonll (msg_ctx->unique_id);
1800 if (msg_ctx->bloom != NULL)
1801 GNUNET_assert (GNUNET_OK ==
1802 GNUNET_CONTAINER_bloomfilter_get_raw_data (msg_ctx->bloom,
1806 memcpy (&route_message->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
1807 memcpy (&route_message[1], msg, ntohs (msg->size));
1808 if (GNUNET_DHT_RO_RECORD_ROUTE == (msg_ctx->msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
1810 route_message->outgoing_path_length = htonl(msg_ctx->path_history_len);
1811 /* Set pointer to start of enc_msg */
1812 route_path = (char *)&route_message[1];
1813 /* Offset to the end of the enc_msg */
1814 route_path += ntohs (msg->size);
1815 /* Copy the route_path after enc_msg */
1816 memcpy (route_path, msg_ctx->path_history, msg_ctx->path_history_len * sizeof(struct GNUNET_PeerIdentity));
1819 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1820 "%s:%s Adding pending message size %d for peer %s\n",
1821 my_short_id, "DHT", msize, GNUNET_i2s (&peer->id));
1823 peer->pending_count++;
1824 increment_stats ("# pending messages scheduled");
1825 GNUNET_CONTAINER_DLL_insert_after (peer->head, peer->tail, peer->tail,
1827 if (peer->send_task == GNUNET_SCHEDULER_NO_TASK)
1828 peer->send_task = GNUNET_SCHEDULER_add_now (&try_core_send, peer);
1833 * Task used to send ping messages to peers so that
1834 * they don't get disconnected.
1836 * @param cls the peer to send a ping message to
1837 * @param tc context, reason, etc.
1840 periodic_ping_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
1842 struct PeerInfo *peer = cls;
1843 struct GNUNET_MessageHeader ping_message;
1844 struct DHT_MessageContext msg_ctx;
1846 if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN)
1849 ping_message.size = htons (sizeof (struct GNUNET_MessageHeader));
1850 ping_message.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PING);
1852 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
1854 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1855 "%s:%s Sending periodic ping to %s\n", my_short_id, "DHT",
1856 GNUNET_i2s (&peer->id));
1858 forward_message (&ping_message, peer, &msg_ctx);
1860 GNUNET_SCHEDULER_add_delayed (DHT_DEFAULT_PING_DELAY, &periodic_ping_task,
1865 * Schedule PING messages for the top X peers in each
1866 * bucket of the routing table (so core won't disconnect them!)
1869 schedule_ping_messages ()
1871 unsigned int bucket;
1873 struct PeerInfo *pos;
1874 for (bucket = lowest_bucket; bucket < MAX_BUCKETS; bucket++)
1876 pos = k_buckets[bucket].head;
1880 if ((count < bucket_size)
1881 && (pos->ping_task == GNUNET_SCHEDULER_NO_TASK))
1882 GNUNET_SCHEDULER_add_now (&periodic_ping_task, pos);
1883 else if ((count >= bucket_size)
1884 && (pos->ping_task != GNUNET_SCHEDULER_NO_TASK))
1886 GNUNET_SCHEDULER_cancel (pos->ping_task);
1887 pos->ping_task = GNUNET_SCHEDULER_NO_TASK;
1897 * Attempt to add a peer to our k-buckets.
1899 * @param peer the peer identity of the peer being added
1900 * @param bucket the bucket that we want this peer to go in
1901 * @param atsi transport ATS information
1903 * @return NULL if the peer was not added,
1904 * pointer to PeerInfo for new peer otherwise
1906 static struct PeerInfo *
1907 try_add_peer (const struct GNUNET_PeerIdentity *peer,
1908 unsigned int bucket,
1909 const struct GNUNET_TRANSPORT_ATS_Information *atsi)
1912 struct PeerInfo *new_peer;
1914 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1917 peer_bucket = find_current_bucket (&peer->hashPubKey);
1919 GNUNET_assert (peer_bucket >= lowest_bucket);
1920 new_peer = add_peer (peer, peer_bucket, atsi);
1922 if ((k_buckets[lowest_bucket].peers_size) >= bucket_size)
1923 enable_next_bucket ();
1925 schedule_ping_messages ();
1932 * Task run to check for messages that need to be sent to a client.
1934 * @param client a ClientList, containing the client and any messages to be sent to it
1937 process_pending_messages (struct ClientList *client)
1939 if (client->pending_head == NULL)
1941 if (client->transmit_handle != NULL)
1944 client->transmit_handle =
1945 GNUNET_SERVER_notify_transmit_ready (client->client_handle,
1946 ntohs (client->pending_head->
1948 GNUNET_TIME_UNIT_FOREVER_REL,
1949 &send_generic_reply, client);
1953 * Callback called as a result of issuing a GNUNET_SERVER_notify_transmit_ready
1954 * request. A ClientList is passed as closure, take the head of the list
1955 * and copy it into buf, which has the result of sending the message to the
1958 * @param cls closure to this call
1959 * @param size maximum number of bytes available to send
1960 * @param buf where to copy the actual message to
1962 * @return the number of bytes actually copied, 0 indicates failure
1965 send_generic_reply (void *cls, size_t size, void *buf)
1967 struct ClientList *client = cls;
1969 struct PendingMessage *reply;
1973 client->transmit_handle = NULL;
1976 /* client disconnected */
1980 while ((NULL != (reply = client->pending_head)) &&
1981 (size >= off + (msize = ntohs (reply->msg->size))))
1983 GNUNET_CONTAINER_DLL_remove (client->pending_head,
1984 client->pending_tail, reply);
1985 memcpy (&cbuf[off], reply->msg, msize);
1986 GNUNET_free (reply);
1989 process_pending_messages (client);
1991 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1992 "Transmitted %u bytes of replies to client\n",
1993 (unsigned int) off);
2000 * Add a PendingMessage to the clients list of messages to be sent
2002 * @param client the active client to send the message to
2003 * @param pending_message the actual message to send
2006 add_pending_message (struct ClientList *client,
2007 struct PendingMessage *pending_message)
2009 GNUNET_CONTAINER_DLL_insert_after (client->pending_head,
2010 client->pending_tail,
2011 client->pending_tail, pending_message);
2012 process_pending_messages (client);
2017 * Called when a reply needs to be sent to a client, as
2018 * a result it found to a GET or FIND PEER request.
2020 * @param client the client to send the reply to
2021 * @param message the encapsulated message to send
2022 * @param msg_ctx the context of the received message
2025 send_reply_to_client (struct ClientList *client,
2026 const struct GNUNET_MessageHeader *message,
2027 struct DHT_MessageContext *msg_ctx)
2029 struct GNUNET_DHT_RouteResultMessage *reply;
2030 struct PendingMessage *pending_message;
2039 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2040 "`%s:%s': Sending reply to client.\n", my_short_id, "DHT");
2042 msize = ntohs (message->size);
2043 tsize = sizeof (struct GNUNET_DHT_RouteResultMessage) + msize + (msg_ctx->path_history_len * sizeof(struct GNUNET_PeerIdentity));
2044 if (tsize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2046 GNUNET_break_op (0);
2049 pending_message = GNUNET_malloc (sizeof (struct PendingMessage) + tsize);
2050 pending_message->msg = (struct GNUNET_MessageHeader *) &pending_message[1];
2051 reply = (struct GNUNET_DHT_RouteResultMessage *) &pending_message[1];
2052 reply->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_RESULT);
2053 reply->header.size = htons (tsize);
2054 reply->outgoing_path_length = htonl(msg_ctx->path_history_len);
2055 reply->unique_id = GNUNET_htonll (msg_ctx->unique_id);
2056 memcpy (&reply->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
2057 reply_offset = (char *)&reply[1];
2058 memcpy (&reply[1], message, msize);
2059 if (msg_ctx->path_history_len > 0)
2061 reply_offset += msize;
2062 memcpy(reply_offset, msg_ctx->path_history, msg_ctx->path_history_len * sizeof(struct GNUNET_PeerIdentity));
2065 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Returning message with outgoing path length %d\n", msg_ctx->path_history_len);
2066 for (i = 0; i < msg_ctx->path_history_len; i++)
2068 path_offset = &msg_ctx->path_history[i * sizeof(struct GNUNET_PeerIdentity)];
2069 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Found peer %d:%s\n", i, GNUNET_i2s((struct GNUNET_PeerIdentity *)path_offset));
2072 add_pending_message (client, pending_message);
2076 * Consider whether or not we would like to have this peer added to
2077 * our routing table. Check whether bucket for this peer is full,
2078 * if so return negative; if not return positive. Since peers are
2079 * only added on CORE level connect, this doesn't actually add the
2080 * peer to the routing table.
2082 * @param peer the peer we are considering adding
2084 * @return GNUNET_YES if we want this peer, GNUNET_NO if not (bucket
2088 consider_peer (struct GNUNET_PeerIdentity *peer)
2093 GNUNET_CONTAINER_multihashmap_contains (all_known_peers,
2096 memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity))))
2097 return GNUNET_NO; /* We already know this peer (are connected even!) */
2098 bucket = find_current_bucket (&peer->hashPubKey);
2100 if ((k_buckets[bucket].peers_size < bucket_size)
2101 || ((bucket == lowest_bucket) && (lowest_bucket > 0)))
2109 * Task used to remove forwarding entries, either
2110 * after timeout, when full, or on shutdown.
2112 * @param cls the entry to remove
2113 * @param tc context, reason, etc.
2116 remove_forward_entry (void *cls,
2117 const struct GNUNET_SCHEDULER_TaskContext *tc)
2119 struct DHTRouteSource *source_info = cls;
2120 struct DHTQueryRecord *record;
2122 GNUNET_CONTAINER_heap_remove_node (source_info->hnode);
2123 record = source_info->record;
2124 GNUNET_CONTAINER_DLL_remove (record->head, record->tail, source_info);
2126 if (record->head == NULL) /* No more entries in DLL */
2128 GNUNET_assert (GNUNET_YES ==
2129 GNUNET_CONTAINER_multihashmap_remove
2130 (forward_list.hashmap, &record->key, record));
2131 GNUNET_free (record);
2133 if (source_info->find_peers_responded != NULL)
2134 GNUNET_CONTAINER_bloomfilter_free (source_info->find_peers_responded);
2135 GNUNET_free (source_info);
2139 * Main function that handles whether or not to route a result
2140 * message to other peers, or to send to our local client.
2142 * @param msg the result message to be routed
2143 * @param msg_ctx context of the message we are routing
2145 * @return the number of peers the message was routed to,
2146 * GNUNET_SYSERR on failure
2149 route_result_message (struct GNUNET_MessageHeader *msg,
2150 struct DHT_MessageContext *msg_ctx)
2152 struct GNUNET_PeerIdentity new_peer;
2153 struct DHTQueryRecord *record;
2154 struct DHTRouteSource *pos;
2155 struct PeerInfo *peer_info;
2156 const struct GNUNET_MessageHeader *hello_msg;
2160 increment_stats (STAT_RESULTS);
2162 * If a find peer result message is received and contains a valid
2163 * HELLO for another peer, offer it to the transport service.
2165 if (ntohs (msg->type) == GNUNET_MESSAGE_TYPE_DHT_FIND_PEER_RESULT)
2167 if (ntohs (msg->size) <= sizeof (struct GNUNET_MessageHeader))
2168 GNUNET_break_op (0);
2170 hello_msg = &msg[1];
2171 if ((ntohs (hello_msg->type) != GNUNET_MESSAGE_TYPE_HELLO)
2172 || (GNUNET_SYSERR ==
2173 GNUNET_HELLO_get_id ((const struct GNUNET_HELLO_Message *)
2174 hello_msg, &new_peer)))
2176 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2177 "%s:%s Received non-HELLO message type in find peer result message!\n",
2178 my_short_id, "DHT");
2179 GNUNET_break_op (0);
2182 else /* We have a valid hello, and peer id stored in new_peer */
2184 find_peer_context.count++;
2185 increment_stats (STAT_FIND_PEER_REPLY);
2186 if (GNUNET_YES == consider_peer (&new_peer))
2188 increment_stats (STAT_HELLOS_PROVIDED);
2189 GNUNET_TRANSPORT_offer_hello (transport_handle, hello_msg, NULL, NULL);
2190 GNUNET_CORE_peer_request_connect (coreAPI,
2191 GNUNET_TIME_relative_multiply
2192 (GNUNET_TIME_UNIT_SECONDS, 5),
2193 &new_peer, NULL, NULL);
2198 if (malicious_dropper == GNUNET_YES)
2202 GNUNET_CONTAINER_multihashmap_get (forward_list.hashmap, &msg_ctx->key);
2204 if (record == NULL) /* No record of this message! */
2207 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2208 "`%s:%s': Have no record of response key %s uid %llu\n",
2209 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
2210 msg_ctx->unique_id);
2212 #if DEBUG_DHT_ROUTING
2213 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2215 dhtlog_handle->insert_route (NULL,
2221 &msg_ctx->key, msg_ctx->peer, NULL);
2224 if (msg_ctx->bloom != NULL)
2226 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->bloom);
2227 msg_ctx->bloom = NULL;
2235 #if STRICT_FORWARDING
2236 if (ntohs (msg->type) == GNUNET_MESSAGE_TYPE_DHT_FIND_PEER_RESULT) /* If we have already forwarded this peer id, don't do it again! */
2239 GNUNET_CONTAINER_bloomfilter_test (pos->find_peers_responded,
2240 &new_peer.hashPubKey))
2243 ("# find peer responses NOT forwarded (bloom match)");
2248 GNUNET_CONTAINER_bloomfilter_add (pos->find_peers_responded,
2249 &new_peer.hashPubKey);
2253 if (0 == memcmp (&pos->source, &my_identity, sizeof (struct GNUNET_PeerIdentity))) /* Local client (or DHT) initiated request! */
2256 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2257 "`%s:%s': Sending response key %s uid %llu to client\n",
2258 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
2259 msg_ctx->unique_id);
2261 #if DEBUG_DHT_ROUTING
2262 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2264 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id,
2265 DHTLOG_RESULT, msg_ctx->hop_count,
2266 GNUNET_YES, &my_identity,
2267 &msg_ctx->key, msg_ctx->peer,
2271 increment_stats (STAT_RESULTS_TO_CLIENT);
2272 if (ntohs (msg->type) == GNUNET_MESSAGE_TYPE_DHT_GET_RESULT)
2273 increment_stats (STAT_GET_REPLY);
2275 for (i = 0; i < msg_ctx->path_history_len; i++)
2277 path_offset = &msg_ctx->path_history[i * sizeof(struct GNUNET_PeerIdentity)];
2279 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "(before client) Key %s Found peer %d:%s\n", GNUNET_h2s(&msg_ctx->key), i, GNUNET_i2s((struct GNUNET_PeerIdentity *)path_offset));
2282 send_reply_to_client (pos->client, msg, msg_ctx);
2284 else /* Send to peer */
2286 peer_info = find_peer_by_id (&pos->source);
2287 if (peer_info == NULL) /* Didn't find the peer in our routing table, perhaps peer disconnected! */
2293 if (msg_ctx->bloom == NULL)
2295 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE,
2297 GNUNET_CONTAINER_bloomfilter_add (msg_ctx->bloom,
2298 &my_identity.hashPubKey);
2300 GNUNET_CONTAINER_bloomfilter_test (msg_ctx->bloom,
2301 &peer_info->id.hashPubKey)))
2304 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2305 "`%s:%s': Forwarding response key %s uid %llu to peer %s\n",
2306 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
2307 msg_ctx->unique_id, GNUNET_i2s (&peer_info->id));
2309 #if DEBUG_DHT_ROUTING
2310 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2312 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id,
2315 GNUNET_NO, &my_identity,
2316 &msg_ctx->key, msg_ctx->peer,
2320 forward_result_message (msg, peer_info, msg_ctx);
2321 /* Try removing forward entries after sending once, only allows ONE response per request */
2322 if (pos->delete_task != GNUNET_SCHEDULER_NO_TASK)
2324 GNUNET_SCHEDULER_cancel (pos->delete_task);
2326 GNUNET_SCHEDULER_add_now (&remove_forward_entry, pos);
2332 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2333 "`%s:%s': NOT Forwarding response (bloom match) key %s uid %llu to peer %s\n",
2334 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
2335 msg_ctx->unique_id, GNUNET_i2s (&peer_info->id));
2341 if (msg_ctx->bloom != NULL)
2343 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->bloom);
2344 msg_ctx->bloom = NULL;
2350 * Iterator for local get request results,
2352 * @param cls closure for iterator, a DatacacheGetContext
2353 * @param exp when does this value expire?
2354 * @param key the key this data is stored under
2355 * @param size the size of the data identified by key
2356 * @param data the actual data
2357 * @param type the type of the data
2359 * @return GNUNET_OK to continue iteration, anything else
2360 * to stop iteration.
2363 datacache_get_iterator (void *cls,
2364 struct GNUNET_TIME_Absolute exp,
2365 const GNUNET_HashCode * key,
2366 size_t size, const char *data,
2367 enum GNUNET_BLOCK_Type type)
2369 struct DHT_MessageContext *msg_ctx = cls;
2370 struct DHT_MessageContext *new_msg_ctx;
2371 struct GNUNET_DHT_GetResultMessage *get_result;
2372 enum GNUNET_BLOCK_EvaluationResult eval;
2373 const struct DHTPutEntry *put_entry;
2381 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2382 "`%s:%s': Received `%s' response from datacache\n", my_short_id,
2386 put_entry = (const struct DHTPutEntry *)data;
2388 if (size != sizeof(struct DHTPutEntry) +
2389 put_entry->data_size +
2390 (put_entry->path_length * sizeof(struct GNUNET_PeerIdentity)))
2393 GNUNET_ERROR_TYPE_WARNING,
2394 "Path + data size doesn't add up for data inserted into datacache!\nData size %d, path length %d, expected %d, got %d\n",
2395 put_entry->data_size, put_entry->path_length,
2396 sizeof(struct DHTPutEntry) + put_entry->data_size
2397 + (put_entry->path_length * sizeof(struct GNUNET_PeerIdentity)),
2399 msg_ctx->do_forward = GNUNET_NO;
2403 eval = GNUNET_BLOCK_evaluate (block_context,
2407 msg_ctx->reply_bf_mutator,
2409 msg_ctx->xquery_size, &put_entry[1], put_entry->data_size);
2413 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2414 msg_ctx->do_forward = GNUNET_NO;
2415 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2416 new_msg_ctx = GNUNET_malloc (sizeof (struct DHT_MessageContext));
2417 memcpy (new_msg_ctx, msg_ctx, sizeof (struct DHT_MessageContext));
2418 if (GNUNET_DHT_RO_RECORD_ROUTE == (msg_ctx->msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
2420 new_msg_ctx->msg_options = GNUNET_DHT_RO_RECORD_ROUTE;
2421 new_msg_ctx->path_history_len = msg_ctx->path_history_len;
2422 /* Assign to previous msg_ctx path history, caller should free after our return */
2423 new_msg_ctx->path_history = msg_ctx->path_history;
2425 for (i = 0; i < new_msg_ctx->path_history_len; i++)
2427 path_offset = &new_msg_ctx->path_history[i * sizeof(struct GNUNET_PeerIdentity)];
2428 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "(get_iterator) Key %s Found peer %d:%s\n", GNUNET_h2s(&msg_ctx->key), i, GNUNET_i2s((struct GNUNET_PeerIdentity *)path_offset));
2433 get_size = sizeof (struct GNUNET_DHT_GetResultMessage) + put_entry->data_size + (put_entry->path_length * sizeof(struct GNUNET_PeerIdentity));
2434 get_result = GNUNET_malloc (get_size);
2435 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_GET_RESULT);
2436 get_result->header.size = htons (get_size);
2437 get_result->expiration = GNUNET_TIME_absolute_hton (exp);
2438 get_result->type = htons (type);
2439 get_result->put_path_length = htons(put_entry->path_length);
2440 path_offset = (char *)&put_entry[1];
2441 path_offset += put_entry->data_size;
2443 for (i = 0; i < put_entry->path_length; i++)
2445 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "(get_iterator PUT path) Key %s Found peer %d:%s\n", GNUNET_h2s(&msg_ctx->key), i, GNUNET_i2s((struct GNUNET_PeerIdentity *)&path_offset[i * sizeof(struct GNUNET_PeerIdentity)]));
2448 /* Copy the actual data and the path_history to the end of the get result */
2449 memcpy (&get_result[1], &put_entry[1], put_entry->data_size + (put_entry->path_length * sizeof(struct GNUNET_PeerIdentity)));
2450 new_msg_ctx->peer = &my_identity;
2451 new_msg_ctx->bloom =
2452 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
2453 new_msg_ctx->hop_count = 0;
2454 new_msg_ctx->importance = DHT_DEFAULT_P2P_IMPORTANCE + 2; /* Make result routing a higher priority */
2455 new_msg_ctx->timeout = DHT_DEFAULT_P2P_TIMEOUT;
2456 increment_stats (STAT_GET_RESPONSE_START);
2457 route_result_message (&get_result->header, new_msg_ctx);
2458 GNUNET_free (new_msg_ctx);
2459 GNUNET_free (get_result);
2461 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2463 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2464 "`%s:%s': Duplicate block error\n", my_short_id, "DHT");
2467 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2469 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2470 "`%s:%s': Invalid request error\n", my_short_id, "DHT");
2473 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2475 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2476 "`%s:%s': Valid request, no results.\n", my_short_id,
2481 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2482 GNUNET_break_op (0);
2483 msg_ctx->do_forward = GNUNET_NO;
2485 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2487 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2488 "`%s:%s': Unsupported block type (%u) in response!\n",
2489 my_short_id, "DHT", type);
2491 /* msg_ctx->do_forward = GNUNET_NO; // not sure... */
2499 * Main function that handles whether or not to route a message to other
2502 * @param msg the message to be routed
2503 * @param msg_ctx the context containing all pertinent information about the message
2506 route_message (const struct GNUNET_MessageHeader *msg,
2507 struct DHT_MessageContext *msg_ctx);
2511 * Server handler for all dht get requests, look for data,
2512 * if found, send response either to clients or other peers.
2514 * @param msg the actual get message
2515 * @param msg_ctx struct containing pertinent information about the get request
2517 * @return number of items found for GET request
2520 handle_dht_get (const struct GNUNET_MessageHeader *msg,
2521 struct DHT_MessageContext *msg_ctx)
2523 const struct GNUNET_DHT_GetMessage *get_msg;
2526 unsigned int results;
2528 enum GNUNET_BLOCK_Type type;
2530 msize = ntohs (msg->size);
2531 if (msize < sizeof (struct GNUNET_DHT_GetMessage))
2536 get_msg = (const struct GNUNET_DHT_GetMessage *) msg;
2537 bf_size = ntohs (get_msg->bf_size);
2538 msg_ctx->xquery_size = ntohs (get_msg->xquery_size);
2539 msg_ctx->reply_bf_mutator = get_msg->bf_mutator; /* FIXME: ntohl? */
2541 sizeof (struct GNUNET_DHT_GetMessage) + bf_size + msg_ctx->xquery_size)
2546 end = (const char *) &get_msg[1];
2547 if (msg_ctx->xquery_size == 0)
2549 msg_ctx->xquery = NULL;
2553 msg_ctx->xquery = (const void *) end;
2554 end += msg_ctx->xquery_size;
2558 msg_ctx->reply_bf = NULL;
2562 msg_ctx->reply_bf = GNUNET_CONTAINER_bloomfilter_init (end,
2564 GNUNET_DHT_GET_BLOOMFILTER_K);
2566 type = (enum GNUNET_BLOCK_Type) ntohl (get_msg->type);
2568 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2569 "`%s:%s': Received `%s' request, message type %u, key %s, uid %llu\n",
2572 type, GNUNET_h2s (&msg_ctx->key), msg_ctx->unique_id);
2574 increment_stats (STAT_GETS);
2577 if (type == GNUNET_BLOCK_DHT_MALICIOUS_MESSAGE_TYPE)
2579 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->reply_bf);
2583 msg_ctx->do_forward = GNUNET_YES;
2584 if (datacache != NULL)
2586 = GNUNET_DATACACHE_get (datacache,
2587 &msg_ctx->key, type,
2588 &datacache_get_iterator, msg_ctx);
2590 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2591 "`%s:%s': Found %d results for `%s' request uid %llu\n",
2592 my_short_id, "DHT", results, "GET", msg_ctx->unique_id);
2596 #if DEBUG_DHT_ROUTING
2597 if ((debug_routes) && (dhtlog_handle != NULL))
2599 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_GET,
2600 msg_ctx->hop_count, GNUNET_YES,
2601 &my_identity, &msg_ctx->key);
2604 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2606 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
2607 msg_ctx->hop_count, GNUNET_YES,
2608 &my_identity, &msg_ctx->key,
2609 msg_ctx->peer, NULL);
2615 /* check query valid */
2616 if (GNUNET_BLOCK_EVALUATION_REQUEST_INVALID
2617 == GNUNET_BLOCK_evaluate (block_context,
2621 msg_ctx->reply_bf_mutator,
2623 msg_ctx->xquery_size, NULL, 0))
2625 GNUNET_break_op (0);
2626 msg_ctx->do_forward = GNUNET_NO;
2630 if (msg_ctx->hop_count == 0) /* Locally initiated request */
2632 #if DEBUG_DHT_ROUTING
2633 if ((debug_routes) && (dhtlog_handle != NULL))
2635 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_GET,
2636 msg_ctx->hop_count, GNUNET_NO,
2637 &my_identity, &msg_ctx->key);
2641 if (msg_ctx->do_forward == GNUNET_YES)
2642 route_message (msg, msg_ctx);
2643 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->reply_bf);
2648 remove_recent_find_peer (void *cls,
2649 const struct GNUNET_SCHEDULER_TaskContext *tc)
2651 GNUNET_HashCode *key = cls;
2653 GNUNET_assert (GNUNET_YES ==
2654 GNUNET_CONTAINER_multihashmap_remove
2655 (recent_find_peer_requests, key, NULL));
2660 * Server handler for initiating local dht find peer requests
2662 * @param find_msg the actual find peer message
2663 * @param msg_ctx struct containing pertinent information about the request
2667 handle_dht_find_peer (const struct GNUNET_MessageHeader *find_msg,
2668 struct DHT_MessageContext *msg_ctx)
2670 struct GNUNET_MessageHeader *find_peer_result;
2671 struct GNUNET_DHT_FindPeerMessage *find_peer_message;
2672 struct DHT_MessageContext *new_msg_ctx;
2673 struct GNUNET_CONTAINER_BloomFilter *incoming_bloom;
2676 GNUNET_HashCode *recent_hash;
2677 struct GNUNET_MessageHeader *other_hello;
2678 size_t other_hello_size;
2679 struct GNUNET_PeerIdentity peer_id;
2681 find_peer_message = (struct GNUNET_DHT_FindPeerMessage *) find_msg;
2682 GNUNET_break_op (ntohs (find_msg->size) >=
2683 (sizeof (struct GNUNET_DHT_FindPeerMessage)));
2684 if (ntohs (find_msg->size) < sizeof (struct GNUNET_DHT_FindPeerMessage))
2687 other_hello_size = 0;
2688 if (ntohs (find_msg->size) > sizeof (struct GNUNET_DHT_FindPeerMessage))
2691 ntohs (find_msg->size) - sizeof (struct GNUNET_DHT_FindPeerMessage);
2692 other_hello = GNUNET_malloc (other_hello_size);
2693 memcpy (other_hello, &find_peer_message[1], other_hello_size);
2694 if ((GNUNET_HELLO_size ((struct GNUNET_HELLO_Message *) other_hello) ==
2697 GNUNET_HELLO_get_id ((struct GNUNET_HELLO_Message *)
2698 other_hello, &peer_id)))
2700 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2701 "Received invalid HELLO message in find peer request!\n");
2702 GNUNET_free (other_hello);
2705 #if FIND_PEER_WITH_HELLO
2706 if (GNUNET_YES == consider_peer (&peer_id))
2708 increment_stats (STAT_HELLOS_PROVIDED);
2709 GNUNET_TRANSPORT_offer_hello (transport_handle, other_hello, NULL, NULL);
2710 GNUNET_CORE_peer_request_connect (coreAPI,
2711 GNUNET_TIME_relative_multiply
2712 (GNUNET_TIME_UNIT_SECONDS, 5),
2713 &peer_id, NULL, NULL);
2714 route_message (find_msg, msg_ctx);
2715 GNUNET_free (other_hello);
2718 else /* We don't want this peer! */
2720 route_message (find_msg, msg_ctx);
2721 GNUNET_free (other_hello);
2728 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2729 "`%s:%s': Received `%s' request from client, key %s (msg size %d, we expected %d)\n",
2730 my_short_id, "DHT", "FIND PEER", GNUNET_h2s (&msg_ctx->key),
2731 ntohs (find_msg->size), sizeof (struct GNUNET_MessageHeader));
2733 if (my_hello == NULL)
2736 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2737 "`%s': Our HELLO is null, can't return.\n", "DHT");
2739 GNUNET_free_non_null (other_hello);
2740 route_message (find_msg, msg_ctx);
2745 GNUNET_CONTAINER_bloomfilter_init (find_peer_message->bloomfilter,
2746 DHT_BLOOM_SIZE, DHT_BLOOM_K);
2748 GNUNET_CONTAINER_bloomfilter_test (incoming_bloom,
2749 &my_identity.hashPubKey))
2751 increment_stats (STAT_BLOOM_FIND_PEER);
2752 GNUNET_CONTAINER_bloomfilter_free (incoming_bloom);
2753 GNUNET_free_non_null (other_hello);
2754 route_message (find_msg, msg_ctx);
2755 return; /* We match the bloomfilter, do not send a response to this peer (they likely already know us!) */
2757 GNUNET_CONTAINER_bloomfilter_free (incoming_bloom);
2759 #if RESTRICT_FIND_PEER
2762 * Ignore any find peer requests from a peer we have seen very recently.
2764 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_contains (recent_find_peer_requests, &msg_ctx->key)) /* We have recently responded to a find peer request for this peer! */
2766 increment_stats ("# dht find peer requests ignored (recently seen!)");
2767 GNUNET_free_non_null (other_hello);
2772 * Use this check to only allow the peer to respond to find peer requests if
2773 * it would be beneficial to have the requesting peer in this peers routing
2774 * table. Can be used to thwart peers flooding the network with find peer
2775 * requests that we don't care about. However, if a new peer is joining
2776 * the network and has no other peers this is a problem (assume all buckets
2777 * full, no one will respond!).
2779 memcpy (&peer_id.hashPubKey, &msg_ctx->key, sizeof (GNUNET_HashCode));
2780 if (GNUNET_NO == consider_peer (&peer_id))
2782 increment_stats ("# dht find peer requests ignored (do not need!)");
2783 GNUNET_free_non_null (other_hello);
2784 route_message (find_msg, msg_ctx);
2789 recent_hash = GNUNET_malloc (sizeof (GNUNET_HashCode));
2790 memcpy (recent_hash, &msg_ctx->key, sizeof (GNUNET_HashCode));
2791 if (GNUNET_SYSERR !=
2792 GNUNET_CONTAINER_multihashmap_put (recent_find_peer_requests,
2793 &msg_ctx->key, NULL,
2794 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
2797 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2798 "Adding recent remove task for key `%s`!\n",
2799 GNUNET_h2s (&msg_ctx->key));
2801 /* Only add a task if there wasn't one for this key already! */
2802 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_relative_multiply
2803 (GNUNET_TIME_UNIT_SECONDS, 30),
2804 &remove_recent_find_peer, recent_hash);
2808 GNUNET_free (recent_hash);
2810 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2811 "Received duplicate find peer request too soon!\n");
2815 /* Simplistic find_peer functionality, always return our hello */
2816 hello_size = ntohs (my_hello->size);
2817 tsize = hello_size + sizeof (struct GNUNET_MessageHeader);
2819 if (tsize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2821 GNUNET_break_op (0);
2822 GNUNET_free_non_null (other_hello);
2826 find_peer_result = GNUNET_malloc (tsize);
2827 find_peer_result->type = htons (GNUNET_MESSAGE_TYPE_DHT_FIND_PEER_RESULT);
2828 find_peer_result->size = htons (tsize);
2829 memcpy (&find_peer_result[1], my_hello, hello_size);
2831 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2832 "`%s': Sending hello size %d to requesting peer.\n",
2836 new_msg_ctx = GNUNET_malloc (sizeof (struct DHT_MessageContext));
2837 memcpy (new_msg_ctx, msg_ctx, sizeof (struct DHT_MessageContext));
2838 new_msg_ctx->peer = &my_identity;
2839 new_msg_ctx->bloom =
2840 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
2841 new_msg_ctx->hop_count = 0;
2842 new_msg_ctx->importance = DHT_DEFAULT_P2P_IMPORTANCE + 2; /* Make find peer requests a higher priority */
2843 new_msg_ctx->timeout = DHT_DEFAULT_P2P_TIMEOUT;
2844 increment_stats (STAT_FIND_PEER_ANSWER);
2845 if (GNUNET_DHT_RO_RECORD_ROUTE == (msg_ctx->msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
2847 new_msg_ctx->msg_options = GNUNET_DHT_RO_RECORD_ROUTE;
2848 new_msg_ctx->path_history_len = msg_ctx->path_history_len;
2849 /* Assign to previous msg_ctx path history, caller should free after our return */
2850 new_msg_ctx->path_history = msg_ctx->path_history;
2852 route_result_message (find_peer_result, new_msg_ctx);
2853 GNUNET_free (new_msg_ctx);
2854 #if DEBUG_DHT_ROUTING
2855 if ((debug_routes) && (dhtlog_handle != NULL))
2857 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_FIND_PEER,
2858 msg_ctx->hop_count, GNUNET_YES,
2859 &my_identity, &msg_ctx->key);
2862 GNUNET_free_non_null (other_hello);
2863 GNUNET_free (find_peer_result);
2864 route_message (find_msg, msg_ctx);
2868 * Task used to republish data.
2869 * Forward declaration; function call loop.
2871 * @param cls closure (a struct RepublishContext)
2872 * @param tc runtime context for this task
2875 republish_content (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc);
2878 * Server handler for initiating local dht put requests
2880 * @param msg the actual put message
2881 * @param msg_ctx struct containing pertinent information about the request
2884 handle_dht_put (const struct GNUNET_MessageHeader *msg,
2885 struct DHT_MessageContext *msg_ctx)
2887 const struct GNUNET_DHT_PutMessage *put_msg;
2888 struct DHTPutEntry *put_entry;
2889 unsigned int put_size;
2891 enum GNUNET_BLOCK_Type put_type;
2894 struct RepublishContext *put_context;
2895 GNUNET_HashCode key;
2897 GNUNET_assert (ntohs (msg->size) >= sizeof (struct GNUNET_DHT_PutMessage));
2899 put_msg = (const struct GNUNET_DHT_PutMessage *) msg;
2900 put_type = (enum GNUNET_BLOCK_Type) ntohl (put_msg->type);
2902 if (put_type == GNUNET_BLOCK_DHT_MALICIOUS_MESSAGE_TYPE)
2904 #if DEBUG_DHT_ROUTING
2905 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2907 /** Log routes that die due to high load! */
2908 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
2909 msg_ctx->hop_count, GNUNET_SYSERR,
2910 &my_identity, &msg_ctx->key,
2911 msg_ctx->peer, NULL);
2918 ntohs (put_msg->header.size) - sizeof (struct GNUNET_DHT_PutMessage);
2920 GNUNET_BLOCK_get_key (block_context, put_type, &put_msg[1], data_size,
2922 if (GNUNET_NO == ret)
2924 #if DEBUG_DHT_ROUTING
2925 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2927 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
2928 msg_ctx->hop_count, GNUNET_SYSERR,
2929 &my_identity, &msg_ctx->key,
2930 msg_ctx->peer, NULL);
2934 GNUNET_break_op (0);
2937 if ((GNUNET_YES == ret) &&
2938 (0 != memcmp (&key, &msg_ctx->key, sizeof (GNUNET_HashCode))))
2940 #if DEBUG_DHT_ROUTING
2941 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2943 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
2944 msg_ctx->hop_count, GNUNET_SYSERR,
2945 &my_identity, &msg_ctx->key,
2946 msg_ctx->peer, NULL);
2949 /* invalid wrapper: key mismatch! */
2950 GNUNET_break_op (0);
2953 /* ret == GNUNET_SYSERR means that there is no known relationship between
2954 data and the key, so we cannot check it */
2956 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2957 "`%s:%s': Received `%s' request (inserting data!), message type %d, key %s, uid %llu\n",
2958 my_short_id, "DHT", "PUT", put_type, GNUNET_h2s (&msg_ctx->key),
2959 msg_ctx->unique_id);
2961 #if DEBUG_DHT_ROUTING
2962 if (msg_ctx->hop_count == 0) /* Locally initiated request */
2964 if ((debug_routes) && (dhtlog_handle != NULL))
2966 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_PUT,
2967 msg_ctx->hop_count, GNUNET_NO,
2968 &my_identity, &msg_ctx->key);
2973 if (msg_ctx->closest != GNUNET_YES)
2975 route_message (msg, msg_ctx);
2980 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2981 "`%s:%s': Received `%s' request (inserting data!), message type %d, key %s, uid %llu\n",
2982 my_short_id, "DHT", "PUT", put_type, GNUNET_h2s (&msg_ctx->key),
2983 msg_ctx->unique_id);
2986 #if DEBUG_DHT_ROUTING
2987 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2989 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
2990 msg_ctx->hop_count, GNUNET_YES,
2991 &my_identity, &msg_ctx->key, msg_ctx->peer,
2995 if ((debug_routes) && (dhtlog_handle != NULL))
2997 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_PUT,
2998 msg_ctx->hop_count, GNUNET_YES,
2999 &my_identity, &msg_ctx->key);
3003 increment_stats (STAT_PUTS_INSERTED);
3004 if (datacache != NULL)
3006 /* Put size is actual data size plus struct overhead plus path length (if any) */
3007 put_size = data_size + sizeof(struct DHTPutEntry) + (msg_ctx->path_history_len * sizeof(struct GNUNET_PeerIdentity));
3008 put_entry = GNUNET_malloc(put_size);
3009 put_entry->data_size = data_size;
3010 put_entry->path_length = msg_ctx->path_history_len;
3011 /* Copy data to end of put entry */
3012 memcpy(&put_entry[1], &put_msg[1], data_size);
3013 if (msg_ctx->path_history_len > 0)
3015 /* Copy path after data */
3016 path_offset = (char *)&put_entry[1];
3017 path_offset += data_size;
3018 memcpy(path_offset, msg_ctx->path_history, msg_ctx->path_history_len * sizeof(struct GNUNET_PeerIdentity));
3021 ret = GNUNET_DATACACHE_put (datacache, &msg_ctx->key, put_size,
3022 (char *) put_entry, put_type,
3023 GNUNET_TIME_absolute_ntoh
3024 (put_msg->expiration));
3025 GNUNET_free (put_entry);
3027 if ((ret == GNUNET_YES) && (do_republish == GNUNET_YES))
3029 put_context = GNUNET_malloc (sizeof (struct RepublishContext));
3030 memcpy (&put_context->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
3031 put_context->type = put_type;
3032 GNUNET_SCHEDULER_add_delayed (dht_republish_frequency,
3033 &republish_content, put_context);
3037 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3038 "`%s:%s': %s request received, but have no datacache!\n",
3039 my_short_id, "DHT", "PUT");
3041 if (stop_on_closest == GNUNET_NO)
3042 route_message (msg, msg_ctx);
3046 * Estimate the diameter of the network based
3047 * on how many buckets are currently in use.
3048 * Concept here is that the diameter of the network
3049 * is roughly the distance a message must travel in
3050 * order to reach its intended destination. Since
3051 * at each hop we expect to get one bit closer, and
3052 * we have one bit per bucket, the number of buckets
3053 * in use should be the largest number of hops for
3054 * a successful message. (of course, this assumes we
3055 * know all peers in the network!)
3057 * @return ballpark diameter figure
3060 estimate_diameter ()
3062 return MAX_BUCKETS - lowest_bucket;
3066 * To how many peers should we (on average)
3067 * forward the request to obtain the desired
3068 * target_replication count (on average).
3070 * returns: target_replication / (est. hops) + (target_replication * hop_count)
3071 * where est. hops is typically 2 * the routing table depth
3073 * @param hop_count number of hops the message has traversed
3074 * @param target_replication the number of total paths desired
3076 * @return Some number of peers to forward the message to
3079 get_forward_count (unsigned int hop_count, size_t target_replication)
3081 uint32_t random_value;
3082 unsigned int forward_count;
3084 unsigned int diameter;
3086 diameter = estimate_diameter ();
3088 if (GNUNET_NO == use_max_hops)
3089 max_hops = (diameter + 1) * 2;
3092 * If we are behaving in strict kademlia mode, send multiple initial requests,
3093 * but then only send to 1 or 0 peers based strictly on the number of hops.
3095 if (strict_kademlia == GNUNET_YES)
3098 return kademlia_replication;
3099 else if (hop_count < max_hops)
3105 /* FIXME: the smaller we think the network is the more lenient we should be for
3106 * routing right? The estimation below only works if we think we have reasonably
3107 * full routing tables, which for our RR topologies may not be the case!
3109 if (hop_count > max_hops)
3112 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3113 "`%s:%s': Hop count too high (est %d, lowest %d), NOT Forwarding request\n",
3114 my_short_id, "DHT", estimate_diameter (), lowest_bucket);
3116 /* FIXME: does this work as intended, isn't the decision to forward or not made based on closeness as well? */
3117 if (GNUNET_YES == paper_forwarding) /* Once we have reached our ideal number of hops, don't stop forwarding! */
3125 if (GNUNET_YES == paper_forwarding)
3127 /* FIXME: re-run replication trials with this formula */
3128 target_value = 1 + (target_replication - 1.0) / (diameter
3129 + ((float) (target_replication - 1.0) * hop_count));
3130 /* Set forward count to floor of target_value */
3131 forward_count = (unsigned int) target_value;
3132 /* Subtract forward_count (floor) from target_value (yields value between 0 and 1) */
3133 target_value = target_value - forward_count;
3134 random_value = GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_STRONG,
3137 if (random_value < (target_value * UINT32_MAX))
3144 target_value = target_replication / (diameter
3145 + ((float) target_replication * hop_count));
3146 if (target_value > 1)
3148 /* Set forward count to floor of target_value */
3149 forward_count = (unsigned int) target_value;
3150 /* Subtract forward_count (floor) from target_value (yields value between 0 and 1) */
3151 target_value = target_value - forward_count;
3154 random_value = GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_STRONG,
3157 if (random_value < (target_value * UINT32_MAX))
3161 return forward_count;
3165 * Check whether my identity is closer than any known peers.
3166 * If a non-null bloomfilter is given, check if this is the closest
3167 * peer that hasn't already been routed to.
3169 * @param target hash code to check closeness to
3170 * @param bloom bloomfilter, exclude these entries from the decision
3172 * Return GNUNET_YES if node location is closest, GNUNET_NO
3176 am_closest_peer (const GNUNET_HashCode * target,
3177 struct GNUNET_CONTAINER_BloomFilter *bloom)
3183 struct PeerInfo *pos;
3184 unsigned int my_distance;
3186 if (0 == memcmp (&my_identity.hashPubKey, target, sizeof (GNUNET_HashCode)))
3189 bucket_num = find_current_bucket (target);
3191 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey, target);
3192 my_distance = distance (&my_identity.hashPubKey, target);
3193 pos = k_buckets[bucket_num].head;
3195 while ((pos != NULL) && (count < bucket_size))
3199 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)))
3202 continue; /* Skip already checked entries */
3206 GNUNET_CRYPTO_hash_matching_bits (&pos->id.hashPubKey, target);
3207 if (other_bits > bits)
3209 else if (other_bits == bits) /* We match the same number of bits */
3211 if (strict_kademlia != GNUNET_YES) /* Return that we at as close as any other peer */
3213 else if (distance (&pos->id.hashPubKey, target) < my_distance) /* Check all known peers, only return if we are the true closest */
3219 /* No peers closer, we are the closest! */
3225 * Return this peers adjusted value based on the convergence
3226 * function chosen. This is the key function for randomized
3227 * routing decisions.
3229 * @param target the key of the request
3230 * @param peer the peer we would like the value of
3231 * @param hops number of hops this message has already traveled
3233 * @return bit distance from target to peer raised to an exponent
3234 * adjusted based on the current routing convergence algorithm
3237 static unsigned long long
3238 converge_distance (const GNUNET_HashCode * target,
3239 struct PeerInfo *peer, unsigned int hops)
3241 unsigned long long ret;
3242 unsigned int other_matching_bits;
3243 double base_converge_modifier = .1; /* Value that "looks" good (when plotted), have to start somewhere */
3244 double temp_modifier;
3250 curr_max_hops = max_hops;
3252 curr_max_hops = (estimate_diameter () + 1) * 2;
3254 if (converge_modifier > 0)
3255 temp_modifier = converge_modifier * base_converge_modifier;
3258 temp_modifier = base_converge_modifier;
3259 base_converge_modifier = 0.0;
3262 GNUNET_assert (temp_modifier > 0);
3264 other_matching_bits =
3265 GNUNET_CRYPTO_hash_matching_bits (target, &peer->id.hashPubKey);
3267 switch (converge_option)
3269 case DHT_CONVERGE_RANDOM:
3270 return 1; /* Always return 1, choose equally among all peers */
3271 case DHT_CONVERGE_LINEAR:
3272 calc_value = hops * curr_max_hops * temp_modifier;
3274 case DHT_CONVERGE_SQUARE:
3276 * Simple square based curve.
3279 (sqrt (hops) / sqrt (curr_max_hops)) * (curr_max_hops /
3283 case DHT_CONVERGE_EXPONENTIAL:
3285 * Simple exponential curve.
3287 if (base_converge_modifier > 0)
3288 calc_value = (temp_modifier * hops * hops) / curr_max_hops;
3290 calc_value = (hops * hops) / curr_max_hops;
3292 case DHT_CONVERGE_BINARY:
3294 * If below the cutoff, route randomly (return 1),
3295 * If above the cutoff, return the maximum possible
3296 * value first (always route to closest, because
3300 if (hops >= converge_modifier) /* Past cutoff */
3309 /* Take the log (base e) of the number of bits matching the other peer */
3310 exponent = log (other_matching_bits);
3312 /* Check if we would overflow; our largest possible value is 2^64 approx. e^44.361419555836498 */
3313 if (exponent * calc_value >= 44.361419555836498)
3316 /* Clear errno and all math exceptions */
3318 feclearexcept (FE_ALL_EXCEPT);
3319 ret = (unsigned long long) pow (other_matching_bits, calc_value);
3320 if ((errno != 0) || fetestexcept (FE_INVALID | FE_DIVBYZERO | FE_OVERFLOW |
3323 if (0 != fetestexcept (FE_OVERFLOW))
3324 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "FE_OVERFLOW\n");
3325 if (0 != fetestexcept (FE_INVALID))
3326 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "FE_INVALID\n");
3327 if (0 != fetestexcept (FE_UNDERFLOW))
3328 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "FE_UNDERFLOW\n");
3336 * Comparison function for two struct PeerInfo's
3337 * which have already had their matching bits to
3338 * some target calculated.
3340 * @param p1 a pointer pointer to a struct PeerInfo
3341 * @param p2 a pointer pointer to a struct PeerInfo
3343 * @return 0 if equidistant to target,
3344 * -1 if p1 is closer,
3348 compare_peers (const void *p1, const void *p2)
3350 struct PeerInfo **first = (struct PeerInfo **) p1;
3351 struct PeerInfo **second = (struct PeerInfo **) p2;
3353 if ((*first)->matching_bits > (*second)->matching_bits)
3355 if ((*first)->matching_bits < (*second)->matching_bits)
3363 * Select a peer from the routing table that would be a good routing
3364 * destination for sending a message for "target". The resulting peer
3365 * must not be in the set of blocked peers.<p>
3367 * Note that we should not ALWAYS select the closest peer to the
3368 * target, peers further away from the target should be chosen with
3369 * exponentially declining probability.
3371 * @param target the key we are selecting a peer to route to
3372 * @param bloom a bloomfilter containing entries this request has seen already
3373 * @param hops how many hops has this message traversed thus far
3375 * @return Peer to route to, or NULL on error
3377 static struct PeerInfo *
3378 select_peer (const GNUNET_HashCode * target,
3379 struct GNUNET_CONTAINER_BloomFilter *bloom, unsigned int hops)
3384 unsigned int offset;
3385 unsigned int my_matching_bits;
3387 struct PeerInfo *pos;
3388 struct PeerInfo *sorted_closest[bucket_size];
3389 unsigned long long temp_converge_distance;
3390 unsigned long long total_distance;
3391 unsigned long long selected;
3393 unsigned long long stats_total_distance;
3397 unsigned int distance;
3398 unsigned int largest_distance;
3399 struct PeerInfo *chosen;
3402 GNUNET_CRYPTO_hash_matching_bits (target, &my_identity.hashPubKey);
3405 /** If we are doing kademlia routing, or converge is binary (saves some cycles) */
3406 if ((strict_kademlia == GNUNET_YES) ||
3407 ((converge_option == DHT_CONVERGE_BINARY)
3408 && (hops >= converge_modifier)))
3410 largest_distance = 0;
3412 for (bc = lowest_bucket; bc < MAX_BUCKETS; bc++)
3414 pos = k_buckets[bc].head;
3416 while ((pos != NULL) && (count < bucket_size))
3418 /* If we are doing strict Kademlia routing, then checking the bloomfilter is basically cheating! */
3420 GNUNET_CONTAINER_bloomfilter_test (bloom,
3421 &pos->id.hashPubKey))
3423 distance = inverse_distance (target, &pos->id.hashPubKey);
3424 if (distance > largest_distance)
3427 largest_distance = distance;
3435 if ((largest_distance > 0) && (chosen != NULL))
3437 GNUNET_CONTAINER_bloomfilter_add (bloom, &chosen->id.hashPubKey);
3448 /* Three steps: order peers in closest bucket (most matching bits).
3449 * Then go over all LOWER buckets (matching same bits we do)
3450 * Then go over all HIGHER buckets (matching less then we do)
3453 closest_bucket = find_current_bucket (target);
3454 GNUNET_assert (closest_bucket >= lowest_bucket);
3455 pos = k_buckets[closest_bucket].head;
3457 offset = 0; /* Need offset as well as count in case peers are bloomfiltered */
3458 memset (sorted_closest, 0, sizeof (sorted_closest));
3459 /* Put any peers in the closest bucket in the sorting array */
3460 while ((pos != NULL) && (count < bucket_size))
3463 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))
3467 continue; /* Ignore bloomfiltered peers */
3469 pos->matching_bits =
3470 GNUNET_CRYPTO_hash_matching_bits (&pos->id.hashPubKey, target);
3471 sorted_closest[offset] = pos;
3477 /* Sort the peers in descending order */
3478 qsort (&sorted_closest[0], offset, sizeof (struct PeerInfo *),
3481 /* Put the sorted closest peers into the possible bins first, in case of overflow. */
3482 for (i = 0; i < offset; i++)
3484 temp_converge_distance =
3485 converge_distance (target, sorted_closest[i], hops);
3487 GNUNET_CONTAINER_bloomfilter_test (bloom,
3488 &sorted_closest[i]->id.
3490 break; /* Ignore bloomfiltered peers */
3491 if (total_distance + temp_converge_distance > total_distance) /* Handle largest case and overflow */
3492 total_distance += temp_converge_distance;
3494 break; /* overflow case */
3497 /* Now handle peers in lower buckets (matches same # of bits as target) */
3498 for (bc = lowest_bucket; bc < closest_bucket; bc++)
3500 pos = k_buckets[bc].head;
3502 while ((pos != NULL) && (count < bucket_size))
3505 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))
3509 continue; /* Ignore bloomfiltered peers */
3511 temp_converge_distance = converge_distance (target, pos, hops);
3512 if (total_distance + temp_converge_distance > total_distance) /* Handle largest case and overflow */
3513 total_distance += temp_converge_distance;
3515 break; /* overflow case */
3521 /* Now handle all the further away peers */
3522 for (bc = closest_bucket + 1; bc < MAX_BUCKETS; bc++)
3524 pos = k_buckets[bc].head;
3526 while ((pos != NULL) && (count < bucket_size))
3529 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))
3533 continue; /* Ignore bloomfiltered peers */
3535 temp_converge_distance = converge_distance (target, pos, hops);
3536 if (total_distance + temp_converge_distance > total_distance) /* Handle largest case and overflow */
3537 total_distance += temp_converge_distance;
3539 break; /* overflow case */
3545 if (total_distance == 0) /* No peers to select from! */
3547 increment_stats ("# failed to select peer");
3551 #if DEBUG_DHT_ROUTING > 1
3554 /* Put the sorted closest peers into the possible bins first, in case of overflow. */
3555 stats_total_distance = 0;
3556 for (i = 0; i < offset; i++)
3559 GNUNET_CONTAINER_bloomfilter_test (bloom,
3560 &sorted_closest[i]->id.
3562 break; /* Ignore bloomfiltered peers */
3563 temp_converge_distance =
3564 converge_distance (target, sorted_closest[i], hops);
3565 if (stats_total_distance + temp_converge_distance > stats_total_distance) /* Handle largest case and overflow */
3566 stats_total_distance += temp_converge_distance;
3568 break; /* overflow case */
3569 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3570 "Choose %d matching bits (%d bits match me) (%.2f percent) converge ret %llu\n",
3571 GNUNET_CRYPTO_hash_matching_bits (&sorted_closest[i]->id.
3572 hashPubKey, target),
3573 GNUNET_CRYPTO_hash_matching_bits (&sorted_closest[i]->id.
3575 &my_identity.hashPubKey),
3576 (temp_converge_distance / (double) total_distance) * 100,
3577 temp_converge_distance);
3580 /* Now handle peers in lower buckets (matches same # of bits as target) */
3581 for (bc = lowest_bucket; bc < closest_bucket; bc++)
3583 pos = k_buckets[bc].head;
3585 while ((pos != NULL) && (count < bucket_size))
3588 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))
3592 continue; /* Ignore bloomfiltered peers */
3594 temp_converge_distance = converge_distance (target, pos, hops);
3595 if (stats_total_distance + temp_converge_distance > stats_total_distance) /* Handle largest case and overflow */
3596 stats_total_distance += temp_converge_distance;
3598 break; /* overflow case */
3599 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3600 "Choose %d matching bits (%d bits match me) (%.2f percent) converge ret %llu\n",
3601 GNUNET_CRYPTO_hash_matching_bits (&pos->id.hashPubKey,
3603 GNUNET_CRYPTO_hash_matching_bits (&pos->id.hashPubKey,
3606 (temp_converge_distance / (double) total_distance) *
3607 100, temp_converge_distance);
3613 /* Now handle all the further away peers */
3614 for (bc = closest_bucket + 1; bc < MAX_BUCKETS; bc++)
3616 pos = k_buckets[bc].head;
3618 while ((pos != NULL) && (count < bucket_size))
3621 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))
3625 continue; /* Ignore bloomfiltered peers */
3627 temp_converge_distance = converge_distance (target, pos, hops);
3628 if (stats_total_distance + temp_converge_distance > stats_total_distance) /* Handle largest case and overflow */
3629 stats_total_distance += temp_converge_distance;
3631 break; /* overflow case */
3632 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3633 "Choose %d matching bits (%d bits match me) (%.2f percent) converge ret %llu\n",
3634 GNUNET_CRYPTO_hash_matching_bits (&pos->id.hashPubKey,
3636 GNUNET_CRYPTO_hash_matching_bits (&pos->id.hashPubKey,
3639 (temp_converge_distance / (double) total_distance) *
3640 100, temp_converge_distance);
3645 /* END PRINT STATS */
3648 /* Now actually choose a peer */
3650 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, total_distance);
3652 /* Go over closest sorted peers. */
3653 for (i = 0; i < offset; i++)
3656 GNUNET_CONTAINER_bloomfilter_test (bloom,
3657 &sorted_closest[i]->id.
3659 break; /* Ignore bloomfiltered peers */
3660 temp_converge_distance =
3661 converge_distance (target, sorted_closest[i], hops);
3662 if (temp_converge_distance >= selected)
3663 return sorted_closest[i];
3665 selected -= temp_converge_distance;
3668 /* Now handle peers in lower buckets (matches same # of bits as target) */
3669 for (bc = lowest_bucket; bc < closest_bucket; bc++)
3671 pos = k_buckets[bc].head;
3673 while ((pos != NULL) && (count < bucket_size))
3676 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))
3680 continue; /* Ignore bloomfiltered peers */
3682 temp_converge_distance = converge_distance (target, pos, hops);
3683 if (temp_converge_distance >= selected)
3686 selected -= temp_converge_distance;
3692 /* Now handle all the further away peers */
3693 for (bc = closest_bucket + 1; bc < MAX_BUCKETS; bc++)
3695 pos = k_buckets[bc].head;
3697 while ((pos != NULL) && (count < bucket_size))
3700 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))
3704 continue; /* Ignore bloomfiltered peers */
3706 temp_converge_distance = converge_distance (target, pos, hops);
3707 if (temp_converge_distance >= selected)
3710 selected -= temp_converge_distance;
3716 increment_stats ("# failed to select peer");
3722 * Task used to remove recent entries, either
3723 * after timeout, when full, or on shutdown.
3725 * @param cls the entry to remove
3726 * @param tc context, reason, etc.
3729 remove_recent (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
3731 struct RecentRequest *req = cls;
3732 static GNUNET_HashCode hash;
3734 GNUNET_assert (req != NULL);
3735 hash_from_uid (req->uid, &hash);
3736 GNUNET_assert (GNUNET_YES ==
3737 GNUNET_CONTAINER_multihashmap_remove (recent.hashmap, &hash,
3739 GNUNET_CONTAINER_heap_remove_node (req->heap_node);
3740 GNUNET_CONTAINER_bloomfilter_free (req->bloom);
3744 if ((tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN) && (0 == GNUNET_CONTAINER_multihashmap_size(recent.hashmap)) && (0 == GNUNET_CONTAINER_heap_get_size(recent.minHeap)))
3746 GNUNET_CONTAINER_multihashmap_destroy(recent.hashmap);
3747 GNUNET_CONTAINER_heap_destroy(recent.minHeap);
3753 * Remember this routing request so that if a reply is
3754 * received we can either forward it to the correct peer
3755 * or return the result locally.
3757 * @param msg_ctx Context of the route request
3759 * @return GNUNET_YES if this response was cached, GNUNET_NO if not
3762 cache_response (struct DHT_MessageContext *msg_ctx)
3764 struct DHTQueryRecord *record;
3765 struct DHTRouteSource *source_info;
3766 struct DHTRouteSource *pos;
3767 struct GNUNET_TIME_Absolute now;
3768 unsigned int current_size;
3770 current_size = GNUNET_CONTAINER_multihashmap_size (forward_list.hashmap);
3772 #if DELETE_WHEN_FULL
3773 while (current_size >= MAX_OUTSTANDING_FORWARDS)
3775 source_info = GNUNET_CONTAINER_heap_remove_root (forward_list.minHeap);
3776 GNUNET_assert (source_info != NULL);
3777 record = source_info->record;
3778 GNUNET_CONTAINER_DLL_remove (record->head, record->tail, source_info);
3779 if (record->head == NULL) /* No more entries in DLL */
3781 GNUNET_assert (GNUNET_YES ==
3782 GNUNET_CONTAINER_multihashmap_remove
3783 (forward_list.hashmap, &record->key, record));
3784 GNUNET_free (record);
3786 if (source_info->delete_task != GNUNET_SCHEDULER_NO_TASK)
3788 GNUNET_SCHEDULER_cancel (source_info->delete_task);
3789 source_info->delete_task = GNUNET_SCHEDULER_NO_TASK;
3791 if (source_info->find_peers_responded != NULL)
3792 GNUNET_CONTAINER_bloomfilter_free (source_info->find_peers_responded);
3793 GNUNET_free (source_info);
3795 GNUNET_CONTAINER_multihashmap_size (forward_list.hashmap);
3798 /** Non-local request and have too many outstanding forwards, discard! */
3799 if ((current_size >= MAX_OUTSTANDING_FORWARDS) && (msg_ctx->client == NULL))
3802 now = GNUNET_TIME_absolute_get ();
3804 GNUNET_CONTAINER_multihashmap_get (forward_list.hashmap, &msg_ctx->key);
3805 if (record != NULL) /* Already know this request! */
3811 memcmp (msg_ctx->peer, &pos->source,
3812 sizeof (struct GNUNET_PeerIdentity)))
3813 break; /* Already have this peer in reply list! */
3816 if ((pos != NULL) && (pos->client == msg_ctx->client)) /* Seen this already */
3818 GNUNET_CONTAINER_heap_update_cost (forward_list.minHeap, pos->hnode,
3825 record = GNUNET_malloc (sizeof (struct DHTQueryRecord));
3826 GNUNET_assert (GNUNET_OK ==
3827 GNUNET_CONTAINER_multihashmap_put (forward_list.hashmap,
3828 &msg_ctx->key, record,
3829 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
3830 memcpy (&record->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
3833 source_info = GNUNET_malloc (sizeof (struct DHTRouteSource));
3834 source_info->record = record;
3835 source_info->delete_task =
3836 GNUNET_SCHEDULER_add_delayed (DHT_FORWARD_TIMEOUT, &remove_forward_entry,
3838 source_info->find_peers_responded =
3839 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
3840 memcpy (&source_info->source, msg_ctx->peer,
3841 sizeof (struct GNUNET_PeerIdentity));
3842 GNUNET_CONTAINER_DLL_insert_after (record->head, record->tail, record->tail,
3844 if (msg_ctx->client != NULL) /* For local request, set timeout so high it effectively never gets pushed out */
3846 source_info->client = msg_ctx->client;
3847 now = GNUNET_TIME_absolute_get_forever ();
3849 source_info->hnode =
3850 GNUNET_CONTAINER_heap_insert (forward_list.minHeap, source_info,
3853 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3854 "`%s:%s': Created new forward source info for %s uid %llu\n",
3855 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
3856 msg_ctx->unique_id);
3863 * Main function that handles whether or not to route a message to other
3866 * @param msg the message to be routed
3867 * @param msg_ctx the context containing all pertinent information about the message
3870 route_message (const struct GNUNET_MessageHeader *msg,
3871 struct DHT_MessageContext *msg_ctx)
3874 struct PeerInfo *selected;
3875 #if DEBUG_DHT_ROUTING > 1
3876 struct PeerInfo *nearest;
3878 unsigned int target_forward_count;
3879 unsigned int forward_count;
3880 struct RecentRequest *recent_req;
3881 GNUNET_HashCode unique_hash;
3882 char *stat_forward_count;
3883 char *temp_stat_str;
3884 #if DEBUG_DHT_ROUTING
3888 if (malicious_dropper == GNUNET_YES)
3890 #if DEBUG_DHT_ROUTING
3891 if ((debug_routes_extended) && (dhtlog_handle != NULL))
3893 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
3894 msg_ctx->hop_count, GNUNET_SYSERR,
3895 &my_identity, &msg_ctx->key,
3896 msg_ctx->peer, NULL);
3899 if (msg_ctx->bloom != NULL)
3901 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->bloom);
3902 msg_ctx->bloom = NULL;
3907 increment_stats (STAT_ROUTES);
3908 target_forward_count =
3909 get_forward_count (msg_ctx->hop_count, msg_ctx->replication);
3910 GNUNET_asprintf (&stat_forward_count, "# forward counts of %d",
3911 target_forward_count);
3912 increment_stats (stat_forward_count);
3913 GNUNET_free (stat_forward_count);
3914 if (msg_ctx->bloom == NULL)
3916 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
3918 if ((stop_on_closest == GNUNET_YES) && (msg_ctx->closest == GNUNET_YES)
3919 && (ntohs (msg->type) == GNUNET_MESSAGE_TYPE_DHT_PUT))
3920 target_forward_count = 0;
3923 * NOTICE: In Kademlia, a find peer request goes no further if the peer doesn't return
3924 * any closer peers (which is being checked for below). Since we are doing recursive
3925 * routing we have no choice but to stop forwarding in this case. This means that at
3926 * any given step the request may NOT be forwarded to alpha peers (because routes will
3927 * stop and the parallel route will not be aware of it). Of course, assuming that we
3928 * have fulfilled the Kademlia requirements for routing table fullness this will never
3929 * ever ever be a problem.
3931 * However, is this fair?
3933 * Since we use these requests to build our routing tables (and we build them in the
3934 * testing driver) we will ignore this restriction for FIND_PEER messages so that
3935 * routing tables still get constructed.
3937 if ((GNUNET_YES == strict_kademlia) && (msg_ctx->closest == GNUNET_YES)
3938 && (msg_ctx->hop_count > 0)
3939 && (ntohs (msg->type) != GNUNET_MESSAGE_TYPE_DHT_FIND_PEER))
3940 target_forward_count = 0;
3943 GNUNET_CONTAINER_bloomfilter_add (msg_ctx->bloom, &my_identity.hashPubKey);
3944 hash_from_uid (msg_ctx->unique_id, &unique_hash);
3946 GNUNET_CONTAINER_multihashmap_contains (recent.hashmap, &unique_hash))
3949 GNUNET_CONTAINER_multihashmap_get (recent.hashmap, &unique_hash);
3950 GNUNET_assert (recent_req != NULL);
3952 memcmp (&recent_req->key, &msg_ctx->key, sizeof (GNUNET_HashCode)))
3953 increment_stats (STAT_DUPLICATE_UID);
3956 increment_stats (STAT_RECENT_SEEN);
3957 GNUNET_CONTAINER_bloomfilter_or2 (msg_ctx->bloom, recent_req->bloom,
3963 recent_req = GNUNET_malloc (sizeof (struct RecentRequest));
3964 recent_req->uid = msg_ctx->unique_id;
3965 memcpy (&recent_req->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
3966 recent_req->remove_task =
3967 GNUNET_SCHEDULER_add_delayed (DEFAULT_RECENT_REMOVAL, &remove_recent,
3969 recent_req->heap_node =
3970 GNUNET_CONTAINER_heap_insert (recent.minHeap, recent_req,
3971 GNUNET_TIME_absolute_get ().abs_value);
3973 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
3974 GNUNET_CONTAINER_multihashmap_put (recent.hashmap, &unique_hash,
3976 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
3979 if (GNUNET_CONTAINER_multihashmap_size (recent.hashmap) > DHT_MAX_RECENT)
3981 recent_req = GNUNET_CONTAINER_heap_peek (recent.minHeap);
3982 GNUNET_assert (recent_req != NULL);
3983 GNUNET_SCHEDULER_cancel (recent_req->remove_task);
3984 GNUNET_SCHEDULER_add_now (&remove_recent, recent_req);
3988 for (i = 0; i < target_forward_count; i++)
3991 select_peer (&msg_ctx->key, msg_ctx->bloom, msg_ctx->hop_count);
3993 if (selected != NULL)
3996 if (GNUNET_CRYPTO_hash_matching_bits
3997 (&selected->id.hashPubKey,
3999 GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey,
4001 GNUNET_asprintf (&temp_stat_str,
4002 "# requests routed to close(r) peer hop %u",
4003 msg_ctx->hop_count);
4005 GNUNET_asprintf (&temp_stat_str,
4006 "# requests routed to less close peer hop %u",
4007 msg_ctx->hop_count);
4008 if (temp_stat_str != NULL)
4010 increment_stats (temp_stat_str);
4011 GNUNET_free (temp_stat_str);
4013 GNUNET_CONTAINER_bloomfilter_add (msg_ctx->bloom,
4014 &selected->id.hashPubKey);
4015 #if DEBUG_DHT_ROUTING > 1
4016 nearest = find_closest_peer (&msg_ctx->key);
4017 nearest_buf = GNUNET_strdup (GNUNET_i2s (&nearest->id));
4018 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4019 "`%s:%s': Forwarding request key %s uid %llu to peer %s (closest %s, bits %d, distance %u)\n",
4020 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
4021 msg_ctx->unique_id, GNUNET_i2s (&selected->id),
4023 GNUNET_CRYPTO_hash_matching_bits (&nearest->id.
4026 distance (&nearest->id.hashPubKey, msg_ctx->key));
4027 GNUNET_free (nearest_buf);
4029 #if DEBUG_DHT_ROUTING
4030 if ((debug_routes_extended) && (dhtlog_handle != NULL))
4032 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id,
4033 DHTLOG_ROUTE, msg_ctx->hop_count,
4034 GNUNET_NO, &my_identity,
4035 &msg_ctx->key, msg_ctx->peer,
4039 forward_message (msg, selected, msg_ctx);
4043 if (msg_ctx->bloom != NULL)
4045 GNUNET_CONTAINER_bloomfilter_or2 (recent_req->bloom, msg_ctx->bloom,
4047 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->bloom);
4048 msg_ctx->bloom = NULL;
4051 #if DEBUG_DHT_ROUTING
4052 if (forward_count == 0)
4053 ret = GNUNET_SYSERR;
4057 if ((debug_routes_extended) && (dhtlog_handle != NULL))
4059 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
4060 msg_ctx->hop_count, ret,
4061 &my_identity, &msg_ctx->key, msg_ctx->peer,
4070 * Main function that handles whether or not to route a message to other
4073 * @param msg the message to be routed
4074 * @param msg_ctx the context containing all pertinent information about the message
4077 demultiplex_message (const struct GNUNET_MessageHeader *msg,
4078 struct DHT_MessageContext *msg_ctx)
4080 /* FIXME: Should we use closest excluding those we won't route to (the bloomfilter problem)? */
4081 msg_ctx->closest = am_closest_peer (&msg_ctx->key, msg_ctx->bloom);
4083 switch (ntohs (msg->type))
4085 case GNUNET_MESSAGE_TYPE_DHT_GET: /* Add to hashmap of requests seen, search for data (always) */
4086 cache_response (msg_ctx);
4087 handle_dht_get (msg, msg_ctx);
4089 case GNUNET_MESSAGE_TYPE_DHT_PUT: /* Check if closest, if so insert data. */
4090 increment_stats (STAT_PUTS);
4091 handle_dht_put (msg, msg_ctx);
4093 case GNUNET_MESSAGE_TYPE_DHT_FIND_PEER: /* Check if closest and not started by us, check options, add to requests seen */
4094 increment_stats (STAT_FIND_PEER);
4095 if (((msg_ctx->hop_count > 0)
4097 memcmp (msg_ctx->peer, &my_identity,
4098 sizeof (struct GNUNET_PeerIdentity))))
4099 || (msg_ctx->client != NULL))
4101 cache_response (msg_ctx);
4102 if ((msg_ctx->closest == GNUNET_YES)
4103 || (msg_ctx->msg_options ==
4104 GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE))
4105 handle_dht_find_peer (msg, msg_ctx);
4108 route_message (msg, msg_ctx);
4109 #if DEBUG_DHT_ROUTING
4110 if (msg_ctx->hop_count == 0) /* Locally initiated request */
4112 if ((debug_routes) && (dhtlog_handle != NULL))
4114 dhtlog_handle->insert_dhtkey (NULL, &msg_ctx->key);
4115 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id,
4117 msg_ctx->hop_count, GNUNET_NO,
4118 &my_identity, &msg_ctx->key);
4124 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
4125 "`%s': Message type (%d) not handled, forwarding anyway!\n",
4126 "DHT", ntohs (msg->type));
4127 route_message (msg, msg_ctx);
4135 * Iterator for local get request results,
4137 * @param cls closure for iterator, NULL
4138 * @param exp when does this value expire?
4139 * @param key the key this data is stored under
4140 * @param size the size of the data identified by key
4141 * @param data the actual data
4142 * @param type the type of the data
4144 * @return GNUNET_OK to continue iteration, anything else
4145 * to stop iteration.
4148 republish_content_iterator (void *cls,
4149 struct GNUNET_TIME_Absolute exp,
4150 const GNUNET_HashCode * key,
4151 size_t size, const char *data, uint32_t type)
4154 struct DHT_MessageContext *new_msg_ctx;
4155 struct GNUNET_DHT_PutMessage *put_msg;
4157 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4158 "`%s:%s': Received `%s' response from datacache\n", my_short_id,
4161 new_msg_ctx = GNUNET_malloc (sizeof (struct DHT_MessageContext));
4163 put_msg = GNUNET_malloc (sizeof (struct GNUNET_DHT_PutMessage) + size);
4164 put_msg->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_PUT);
4165 put_msg->header.size = htons (sizeof (struct GNUNET_DHT_PutMessage) + size);
4166 put_msg->expiration = GNUNET_TIME_absolute_hton (exp);
4167 put_msg->type = htons (type);
4168 memcpy (&put_msg[1], data, size);
4169 new_msg_ctx->unique_id =
4170 GNUNET_ntohll (GNUNET_CRYPTO_random_u64
4171 (GNUNET_CRYPTO_QUALITY_WEAK, UINT64_MAX));
4172 new_msg_ctx->replication = ntohl (DEFAULT_PUT_REPLICATION);
4173 new_msg_ctx->msg_options = ntohl (0);
4174 new_msg_ctx->network_size = estimate_diameter ();
4175 new_msg_ctx->peer = &my_identity;
4176 new_msg_ctx->bloom =
4177 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
4178 new_msg_ctx->hop_count = 0;
4179 new_msg_ctx->importance = DHT_DEFAULT_P2P_IMPORTANCE;
4180 new_msg_ctx->timeout = DHT_DEFAULT_P2P_TIMEOUT;
4181 increment_stats (STAT_PUT_START);
4182 demultiplex_message (&put_msg->header, new_msg_ctx);
4184 GNUNET_free (new_msg_ctx);
4185 GNUNET_free (put_msg);
4190 * Task used to republish data.
4192 * @param cls closure (a struct RepublishContext)
4193 * @param tc runtime context for this task
4196 republish_content (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
4198 struct RepublishContext *put_context = cls;
4200 unsigned int results;
4202 if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN)
4204 GNUNET_free (put_context);
4208 GNUNET_assert (datacache != NULL); /* If we have no datacache we never should have scheduled this! */
4210 GNUNET_DATACACHE_get (datacache, &put_context->key, put_context->type,
4211 &republish_content_iterator, NULL);
4212 if (results == 0) /* Data must have expired */
4213 GNUNET_free (put_context);
4214 else /* Reschedule task for next time period */
4215 GNUNET_SCHEDULER_add_delayed (dht_republish_frequency, &republish_content,
4222 * Iterator over hash map entries.
4224 * @param cls client to search for in source routes
4225 * @param key current key code (ignored)
4226 * @param value value in the hash map, a DHTQueryRecord
4227 * @return GNUNET_YES if we should continue to
4232 find_client_records (void *cls, const GNUNET_HashCode * key, void *value)
4234 struct ClientList *client = cls;
4235 struct DHTQueryRecord *record = value;
4236 struct DHTRouteSource *pos;
4240 if (pos->client == client)
4246 GNUNET_CONTAINER_DLL_remove (record->head, record->tail, pos);
4247 GNUNET_CONTAINER_heap_remove_node (pos->hnode);
4248 if (pos->delete_task != GNUNET_SCHEDULER_NO_TASK)
4250 GNUNET_SCHEDULER_cancel (pos->delete_task);
4251 pos->delete_task = GNUNET_SCHEDULER_NO_TASK;
4253 if (pos->find_peers_responded != NULL)
4254 GNUNET_CONTAINER_bloomfilter_free (pos->find_peers_responded);
4257 if (record->head == NULL) /* No more entries in DLL */
4259 GNUNET_assert (GNUNET_YES ==
4260 GNUNET_CONTAINER_multihashmap_remove
4261 (forward_list.hashmap, &record->key, record));
4262 GNUNET_free (record);
4268 * Functions with this signature are called whenever a client
4269 * is disconnected on the network level.
4271 * @param cls closure (NULL for dht)
4272 * @param client identification of the client; NULL
4273 * for the last call when the server is destroyed
4276 handle_client_disconnect (void *cls, struct GNUNET_SERVER_Client *client)
4278 struct ClientList *pos = client_list;
4279 struct ClientList *prev;
4280 struct ClientList *found;
4281 struct PendingMessage *reply;
4287 if (pos->client_handle == client)
4290 prev->next = pos->next;
4292 client_list = pos->next;
4302 if (found->transmit_handle != NULL)
4303 GNUNET_CONNECTION_notify_transmit_ready_cancel
4304 (found->transmit_handle);
4306 while (NULL != (reply = found->pending_head))
4308 GNUNET_CONTAINER_DLL_remove (found->pending_head,
4309 found->pending_tail, reply);
4310 GNUNET_free (reply);
4312 GNUNET_CONTAINER_multihashmap_iterate (forward_list.hashmap,
4313 &find_client_records, found);
4314 GNUNET_free (found);
4319 * Find a client if it exists, add it otherwise.
4321 * @param client the server handle to the client
4323 * @return the client if found, a new client otherwise
4325 static struct ClientList *
4326 find_active_client (struct GNUNET_SERVER_Client *client)
4328 struct ClientList *pos = client_list;
4329 struct ClientList *ret;
4333 if (pos->client_handle == client)
4338 ret = GNUNET_malloc (sizeof (struct ClientList));
4339 ret->client_handle = client;
4340 ret->next = client_list;
4348 * Task to send a malicious put message across the network.
4350 * @param cls closure for this task
4351 * @param tc the context under which the task is running
4354 malicious_put_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
4356 static struct GNUNET_DHT_PutMessage put_message;
4357 static struct DHT_MessageContext msg_ctx;
4358 static GNUNET_HashCode key;
4359 uint32_t random_key;
4361 if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN)
4363 put_message.header.size = htons (sizeof (struct GNUNET_DHT_PutMessage));
4364 put_message.header.type = htons (GNUNET_MESSAGE_TYPE_DHT_PUT);
4365 put_message.type = htonl (GNUNET_BLOCK_DHT_MALICIOUS_MESSAGE_TYPE);
4366 put_message.expiration =
4367 GNUNET_TIME_absolute_hton (GNUNET_TIME_absolute_get_forever ());
4368 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
4370 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
4371 GNUNET_CRYPTO_hash (&random_key, sizeof (uint32_t), &key);
4372 memcpy (&msg_ctx.key, &key, sizeof (GNUNET_HashCode));
4374 GNUNET_ntohll (GNUNET_CRYPTO_random_u64
4375 (GNUNET_CRYPTO_QUALITY_WEAK, UINT64_MAX));
4376 msg_ctx.replication = ntohl (DHT_DEFAULT_FIND_PEER_REPLICATION);
4377 msg_ctx.msg_options = ntohl (0);
4378 msg_ctx.network_size = estimate_diameter ();
4379 msg_ctx.peer = &my_identity;
4380 msg_ctx.importance = DHT_DEFAULT_P2P_IMPORTANCE;
4381 msg_ctx.timeout = DHT_DEFAULT_P2P_TIMEOUT;
4382 #if DEBUG_DHT_ROUTING
4383 if (dhtlog_handle != NULL)
4384 dhtlog_handle->insert_dhtkey (NULL, &key);
4386 increment_stats (STAT_PUT_START);
4387 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4388 "%s:%s Sending malicious PUT message with hash %s\n",
4389 my_short_id, "DHT", GNUNET_h2s (&key));
4390 demultiplex_message (&put_message.header, &msg_ctx);
4391 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_relative_multiply
4392 (GNUNET_TIME_UNIT_MILLISECONDS,
4393 malicious_put_frequency),
4394 &malicious_put_task, NULL);
4399 * Task to send a malicious put message across the network.
4401 * @param cls closure for this task
4402 * @param tc the context under which the task is running
4405 malicious_get_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
4407 static struct GNUNET_DHT_GetMessage get_message;
4408 struct DHT_MessageContext msg_ctx;
4409 static GNUNET_HashCode key;
4410 uint32_t random_key;
4412 if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN)
4415 get_message.header.size = htons (sizeof (struct GNUNET_DHT_GetMessage));
4416 get_message.header.type = htons (GNUNET_MESSAGE_TYPE_DHT_GET);
4417 get_message.type = htonl (GNUNET_BLOCK_DHT_MALICIOUS_MESSAGE_TYPE);
4418 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
4420 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
4421 GNUNET_CRYPTO_hash (&random_key, sizeof (uint32_t), &key);
4422 memcpy (&msg_ctx.key, &key, sizeof (GNUNET_HashCode));
4424 GNUNET_ntohll (GNUNET_CRYPTO_random_u64
4425 (GNUNET_CRYPTO_QUALITY_WEAK, UINT64_MAX));
4426 msg_ctx.replication = ntohl (DHT_DEFAULT_FIND_PEER_REPLICATION);
4427 msg_ctx.msg_options = ntohl (0);
4428 msg_ctx.network_size = estimate_diameter ();
4429 msg_ctx.peer = &my_identity;
4430 msg_ctx.importance = DHT_DEFAULT_P2P_IMPORTANCE;
4431 msg_ctx.timeout = DHT_DEFAULT_P2P_TIMEOUT;
4432 #if DEBUG_DHT_ROUTING
4433 if (dhtlog_handle != NULL)
4434 dhtlog_handle->insert_dhtkey (NULL, &key);
4436 increment_stats (STAT_GET_START);
4437 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4438 "%s:%s Sending malicious GET message with hash %s\n",
4439 my_short_id, "DHT", GNUNET_h2s (&key));
4440 demultiplex_message (&get_message.header, &msg_ctx);
4441 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_relative_multiply
4442 (GNUNET_TIME_UNIT_MILLISECONDS,
4443 malicious_get_frequency),
4444 &malicious_get_task, NULL);
4450 * Iterator over hash map entries.
4452 * @param cls closure
4453 * @param key current key code
4454 * @param value value in the hash map
4455 * @return GNUNET_YES if we should continue to
4460 add_known_to_bloom (void *cls, const GNUNET_HashCode * key, void *value)
4462 struct GNUNET_CONTAINER_BloomFilter *bloom = cls;
4463 GNUNET_CONTAINER_bloomfilter_add (bloom, key);
4468 * Task to send a find peer message for our own peer identifier
4469 * so that we can find the closest peers in the network to ourselves
4470 * and attempt to connect to them.
4472 * @param cls closure for this task
4473 * @param tc the context under which the task is running
4476 send_find_peer_message (void *cls,
4477 const struct GNUNET_SCHEDULER_TaskContext *tc)
4479 struct GNUNET_DHT_FindPeerMessage *find_peer_msg;
4480 struct DHT_MessageContext msg_ctx;
4481 struct GNUNET_TIME_Relative next_send_time;
4482 struct GNUNET_CONTAINER_BloomFilter *temp_bloom;
4484 struct GNUNET_TIME_Relative time_diff;
4485 struct GNUNET_TIME_Absolute end;
4487 double count_per_interval;
4489 if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN)
4492 if ((newly_found_peers > bucket_size) && (GNUNET_YES == do_find_peer)) /* If we are finding peers already, no need to send out our request right now! */
4494 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
4495 "Have %d newly found peers since last find peer message sent!\n",
4497 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
4498 &send_find_peer_message, NULL);
4499 newly_found_peers = 0;
4503 increment_stats (STAT_FIND_PEER_START);
4505 end = GNUNET_TIME_absolute_get ();
4507 GNUNET_TIME_absolute_get_difference (find_peer_context.start, end);
4509 if (time_diff.abs_value > FIND_PEER_CALC_INTERVAL.abs_value)
4511 multiplier = time_diff.abs_value / FIND_PEER_CALC_INTERVAL.abs_value;
4512 count_per_interval = find_peer_context.count / multiplier;
4516 multiplier = FIND_PEER_CALC_INTERVAL.abs_value / time_diff.abs_value;
4517 count_per_interval = find_peer_context.count * multiplier;
4521 #if FIND_PEER_WITH_HELLO
4523 GNUNET_malloc (sizeof (struct GNUNET_DHT_FindPeerMessage) +
4524 GNUNET_HELLO_size ((struct GNUNET_HELLO_Message *)
4526 find_peer_msg->header.size =
4527 htons (sizeof (struct GNUNET_DHT_FindPeerMessage) +
4528 GNUNET_HELLO_size ((struct GNUNET_HELLO_Message *) my_hello));
4529 memcpy (&find_peer_msg[1], my_hello,
4530 GNUNET_HELLO_size ((struct GNUNET_HELLO_Message *) my_hello));
4532 find_peer_msg = GNUNET_malloc (sizeof (struct GNUNET_DHT_FindPeerMessage));
4533 find_peer_msg->header.size =
4534 htons (sizeof (struct GNUNET_DHT_FindPeerMessage));
4536 find_peer_msg->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_FIND_PEER);
4538 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
4539 GNUNET_CONTAINER_multihashmap_iterate (all_known_peers, &add_known_to_bloom,
4541 GNUNET_assert (GNUNET_OK ==
4542 GNUNET_CONTAINER_bloomfilter_get_raw_data (temp_bloom,
4546 GNUNET_CONTAINER_bloomfilter_free (temp_bloom);
4547 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
4548 memcpy (&msg_ctx.key, &my_identity.hashPubKey, sizeof (GNUNET_HashCode));
4550 GNUNET_ntohll (GNUNET_CRYPTO_random_u64
4551 (GNUNET_CRYPTO_QUALITY_STRONG, UINT64_MAX));
4552 msg_ctx.replication = DHT_DEFAULT_FIND_PEER_REPLICATION;
4553 msg_ctx.msg_options = DHT_DEFAULT_FIND_PEER_OPTIONS;
4554 msg_ctx.network_size = estimate_diameter ();
4555 msg_ctx.peer = &my_identity;
4556 msg_ctx.importance = DHT_DEFAULT_FIND_PEER_IMPORTANCE;
4557 msg_ctx.timeout = DHT_DEFAULT_FIND_PEER_TIMEOUT;
4559 demultiplex_message (&find_peer_msg->header, &msg_ctx);
4560 GNUNET_free (find_peer_msg);
4561 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4562 "`%s:%s': Sent `%s' request to some (?) peers\n", my_short_id,
4563 "DHT", "FIND PEER");
4564 if (newly_found_peers < bucket_size)
4566 next_send_time.rel_value =
4567 (DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value / 2) +
4568 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_STRONG,
4569 DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value /
4574 next_send_time.rel_value = DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value +
4575 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_STRONG,
4576 DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value -
4577 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value);
4580 GNUNET_assert (next_send_time.rel_value != 0);
4581 find_peer_context.count = 0;
4582 newly_found_peers = 0;
4583 find_peer_context.start = GNUNET_TIME_absolute_get ();
4584 if (GNUNET_YES == do_find_peer)
4586 GNUNET_SCHEDULER_add_delayed (next_send_time,
4587 &send_find_peer_message, NULL);
4592 * Handler for any generic DHT messages, calls the appropriate handler
4593 * depending on message type, sends confirmation if responses aren't otherwise
4596 * @param cls closure for the service
4597 * @param client the client we received this message from
4598 * @param message the actual message received
4601 handle_dht_local_route_request (void *cls,
4602 struct GNUNET_SERVER_Client *client,
4603 const struct GNUNET_MessageHeader *message)
4605 const struct GNUNET_DHT_RouteMessage *dht_msg =
4606 (const struct GNUNET_DHT_RouteMessage *) message;
4607 const struct GNUNET_MessageHeader *enc_msg;
4608 struct DHT_MessageContext msg_ctx;
4610 enc_msg = (const struct GNUNET_MessageHeader *) &dht_msg[1];
4612 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4613 "`%s:%s': Received `%s' request from client, message type %d, key %s, uid %llu\n",
4617 ntohs (message->type),
4618 GNUNET_h2s (&dht_msg->key), GNUNET_ntohll (dht_msg->unique_id));
4620 #if DEBUG_DHT_ROUTING
4621 if (dhtlog_handle != NULL)
4622 dhtlog_handle->insert_dhtkey (NULL, &dht_msg->key);
4625 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
4626 msg_ctx.client = find_active_client (client);
4627 memcpy (&msg_ctx.key, &dht_msg->key, sizeof (GNUNET_HashCode));
4628 msg_ctx.unique_id = GNUNET_ntohll (dht_msg->unique_id);
4629 msg_ctx.replication = ntohl (dht_msg->desired_replication_level);
4630 msg_ctx.msg_options = ntohl (dht_msg->options);
4631 if (GNUNET_DHT_RO_RECORD_ROUTE == (msg_ctx.msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
4633 msg_ctx.path_history = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
4634 memcpy(msg_ctx.path_history, &my_identity, sizeof(struct GNUNET_PeerIdentity));
4635 msg_ctx.path_history_len = 1;
4637 msg_ctx.network_size = estimate_diameter ();
4638 msg_ctx.peer = &my_identity;
4639 msg_ctx.importance = DHT_DEFAULT_P2P_IMPORTANCE + 4; /* Make local routing a higher priority */
4640 msg_ctx.timeout = DHT_DEFAULT_P2P_TIMEOUT;
4642 if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_GET)
4643 increment_stats (STAT_GET_START);
4644 else if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_PUT)
4645 increment_stats (STAT_PUT_START);
4646 else if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_FIND_PEER)
4647 increment_stats (STAT_FIND_PEER_START);
4649 if (GNUNET_YES == malicious_dropper)
4651 if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_GET)
4653 #if DEBUG_DHT_ROUTING
4654 if ((debug_routes) && (dhtlog_handle != NULL))
4656 dhtlog_handle->insert_query (NULL, msg_ctx.unique_id,
4657 DHTLOG_GET, msg_ctx.hop_count,
4658 GNUNET_NO, &my_identity,
4663 else if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_PUT)
4665 #if DEBUG_DHT_ROUTING
4666 if ((debug_routes) && (dhtlog_handle != NULL))
4668 dhtlog_handle->insert_query (NULL, msg_ctx.unique_id,
4669 DHTLOG_PUT, msg_ctx.hop_count,
4670 GNUNET_NO, &my_identity,
4675 GNUNET_SERVER_receive_done (client, GNUNET_OK);
4676 GNUNET_free_non_null(msg_ctx.path_history);
4680 demultiplex_message (enc_msg, &msg_ctx);
4681 GNUNET_SERVER_receive_done (client, GNUNET_OK);
4686 * Handler for any locally received DHT control messages,
4687 * sets malicious flags mostly for now.
4689 * @param cls closure for the service
4690 * @param client the client we received this message from
4691 * @param message the actual message received
4695 handle_dht_control_message (void *cls, struct GNUNET_SERVER_Client *client,
4696 const struct GNUNET_MessageHeader *message)
4698 const struct GNUNET_DHT_ControlMessage *dht_control_msg =
4699 (const struct GNUNET_DHT_ControlMessage *) message;
4702 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4703 "`%s:%s': Received `%s' request from client, command %d\n",
4704 my_short_id, "DHT", "CONTROL",
4705 ntohs (dht_control_msg->command));
4708 switch (ntohs (dht_control_msg->command))
4710 case GNUNET_MESSAGE_TYPE_DHT_FIND_PEER:
4711 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4712 "Sending self seeking find peer request!\n");
4713 GNUNET_SCHEDULER_add_now (&send_find_peer_message, NULL);
4716 case GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_GET:
4717 if (ntohs (dht_control_msg->variable) > 0)
4718 malicious_get_frequency = ntohs (dht_control_msg->variable);
4719 if (malicious_get_frequency == 0)
4720 malicious_get_frequency = DEFAULT_MALICIOUS_GET_FREQUENCY;
4721 if (malicious_getter != GNUNET_YES)
4722 GNUNET_SCHEDULER_add_now (&malicious_get_task, NULL);
4723 malicious_getter = GNUNET_YES;
4724 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4725 "%s:%s Initiating malicious GET behavior, frequency %d\n",
4726 my_short_id, "DHT", malicious_get_frequency);
4728 case GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_PUT:
4729 if (ntohs (dht_control_msg->variable) > 0)
4730 malicious_put_frequency = ntohs (dht_control_msg->variable);
4731 if (malicious_put_frequency == 0)
4732 malicious_put_frequency = DEFAULT_MALICIOUS_PUT_FREQUENCY;
4733 if (malicious_putter != GNUNET_YES)
4734 GNUNET_SCHEDULER_add_now (&malicious_put_task, NULL);
4735 malicious_putter = GNUNET_YES;
4736 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4737 "%s:%s Initiating malicious PUT behavior, frequency %d\n",
4738 my_short_id, "DHT", malicious_put_frequency);
4740 case GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_DROP:
4741 #if DEBUG_DHT_ROUTING
4742 if ((malicious_dropper != GNUNET_YES) && (dhtlog_handle != NULL))
4743 dhtlog_handle->set_malicious (&my_identity);
4745 malicious_dropper = GNUNET_YES;
4746 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4747 "%s:%s Initiating malicious DROP behavior\n", my_short_id,
4752 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
4753 "%s:%s Unknown control command type `%d'!\n",
4754 my_short_id, "DHT", ntohs (dht_control_msg->command));
4758 GNUNET_SERVER_receive_done (client, GNUNET_OK);
4762 * Handler for any generic DHT stop messages, calls the appropriate handler
4763 * depending on message type (if processed locally)
4765 * @param cls closure for the service
4766 * @param client the client we received this message from
4767 * @param message the actual message received
4771 handle_dht_local_route_stop (void *cls, struct GNUNET_SERVER_Client *client,
4772 const struct GNUNET_MessageHeader *message)
4775 const struct GNUNET_DHT_StopMessage *dht_stop_msg =
4776 (const struct GNUNET_DHT_StopMessage *) message;
4777 struct DHTQueryRecord *record;
4778 struct DHTRouteSource *pos;
4780 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4781 "`%s:%s': Received `%s' request from client, uid %llu\n",
4782 my_short_id, "DHT", "GENERIC STOP",
4783 GNUNET_ntohll (dht_stop_msg->unique_id));
4786 GNUNET_CONTAINER_multihashmap_get (forward_list.hashmap,
4787 &dht_stop_msg->key);
4794 /* If the client is non-null (local request) and the client matches the requesting client, remove the entry. */
4795 if ((pos->client != NULL) && (pos->client->client_handle == client))
4797 if (pos->delete_task != GNUNET_SCHEDULER_NO_TASK)
4798 GNUNET_SCHEDULER_cancel (pos->delete_task);
4799 pos->delete_task = GNUNET_SCHEDULER_add_now (&remove_forward_entry, pos);
4805 GNUNET_SERVER_receive_done (client, GNUNET_OK);
4810 * Core handler for p2p route requests.
4812 * @param cls closure
4813 * @param message message
4814 * @param peer peer identity this notification is about
4815 * @param atsi performance data
4819 handle_dht_p2p_route_request (void *cls,
4820 const struct GNUNET_PeerIdentity *peer,
4821 const struct GNUNET_MessageHeader *message,
4822 const struct GNUNET_TRANSPORT_ATS_Information
4826 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4827 "`%s:%s': Received P2P request from peer %s\n", my_short_id,
4828 "DHT", GNUNET_i2s (peer));
4830 struct GNUNET_DHT_P2PRouteMessage *incoming =
4831 (struct GNUNET_DHT_P2PRouteMessage *) message;
4832 struct GNUNET_MessageHeader *enc_msg =
4833 (struct GNUNET_MessageHeader *) &incoming[1];
4834 struct DHT_MessageContext *msg_ctx;
4838 if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_P2P_PING) /* Throw these away. FIXME: Don't throw these away? (reply) */
4841 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4842 "%s:%s Received P2P Ping message.\n", my_short_id, "DHT");
4847 if (ntohs (enc_msg->size) >= GNUNET_SERVER_MAX_MESSAGE_SIZE - 1)
4849 GNUNET_break_op (0);
4853 if (malicious_dropper == GNUNET_YES)
4855 #if DEBUG_DHT_ROUTING
4856 if ((debug_routes_extended) && (dhtlog_handle != NULL))
4858 /** Log routes that die due to high load! */
4859 dhtlog_handle->insert_route (NULL,
4860 GNUNET_ntohll (incoming->unique_id),
4862 ntohl (incoming->hop_count),
4863 GNUNET_SYSERR, &my_identity,
4864 &incoming->key, peer, NULL);
4870 if (get_max_send_delay ().rel_value > MAX_REQUEST_TIME.rel_value)
4872 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4873 "Sending of previous replies took too long, backing off!\n");
4874 increment_stats ("# route requests dropped due to high load");
4875 decrease_max_send_delay (get_max_send_delay ());
4876 #if DEBUG_DHT_ROUTING
4877 if ((debug_routes_extended) && (dhtlog_handle != NULL))
4879 /** Log routes that die due to high load! */
4880 dhtlog_handle->insert_route (NULL,
4881 GNUNET_ntohll (incoming->unique_id),
4883 ntohl (incoming->hop_count),
4884 GNUNET_SYSERR, &my_identity,
4885 &incoming->key, peer, NULL);
4890 msg_ctx = GNUNET_malloc (sizeof (struct DHT_MessageContext));
4892 GNUNET_CONTAINER_bloomfilter_init (incoming->bloomfilter, DHT_BLOOM_SIZE,
4894 GNUNET_assert (msg_ctx->bloom != NULL);
4895 msg_ctx->hop_count = ntohl (incoming->hop_count);
4896 memcpy (&msg_ctx->key, &incoming->key, sizeof (GNUNET_HashCode));
4897 msg_ctx->replication = ntohl (incoming->desired_replication_level);
4898 msg_ctx->unique_id = GNUNET_ntohll (incoming->unique_id);
4899 msg_ctx->msg_options = ntohl (incoming->options);
4900 if (GNUNET_DHT_RO_RECORD_ROUTE == (msg_ctx->msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
4902 path_size = ntohl(incoming->outgoing_path_length) * sizeof(struct GNUNET_PeerIdentity);
4903 GNUNET_assert(ntohs(message->size) ==
4904 (sizeof(struct GNUNET_DHT_P2PRouteMessage) +
4905 ntohs(enc_msg->size) +
4907 route_path = (char *)&incoming[1];
4908 route_path = route_path + ntohs(enc_msg->size);
4909 msg_ctx->path_history = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity) + path_size);
4910 memcpy(msg_ctx->path_history, route_path, path_size);
4911 memcpy(&msg_ctx->path_history[path_size], &my_identity, sizeof(struct GNUNET_PeerIdentity));
4912 msg_ctx->path_history_len = ntohl(incoming->outgoing_path_length) + 1;
4914 msg_ctx->network_size = ntohl (incoming->network_size);
4915 msg_ctx->peer = peer;
4916 msg_ctx->importance = DHT_DEFAULT_P2P_IMPORTANCE;
4917 msg_ctx->timeout = DHT_DEFAULT_P2P_TIMEOUT;
4918 demultiplex_message (enc_msg, msg_ctx);
4919 if (msg_ctx->bloom != NULL)
4921 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->bloom);
4922 msg_ctx->bloom = NULL;
4924 GNUNET_free (msg_ctx);
4930 * Core handler for p2p route results.
4932 * @param cls closure
4933 * @param message message
4934 * @param peer peer identity this notification is about
4935 * @param atsi performance data
4939 handle_dht_p2p_route_result (void *cls,
4940 const struct GNUNET_PeerIdentity *peer,
4941 const struct GNUNET_MessageHeader *message,
4942 const struct GNUNET_TRANSPORT_ATS_Information
4946 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4947 "`%s:%s': Received request from peer %s\n", my_short_id, "DHT",
4950 struct GNUNET_DHT_P2PRouteResultMessage *incoming =
4951 (struct GNUNET_DHT_P2PRouteResultMessage *) message;
4952 struct GNUNET_MessageHeader *enc_msg =
4953 (struct GNUNET_MessageHeader *) &incoming[1];
4954 struct DHT_MessageContext msg_ctx;
4959 if (ntohs (enc_msg->size) >= GNUNET_SERVER_MAX_MESSAGE_SIZE - 1)
4961 GNUNET_break_op (0);
4965 if (malicious_dropper == GNUNET_YES)
4967 #if DEBUG_DHT_ROUTING
4968 if ((debug_routes_extended) && (dhtlog_handle != NULL))
4970 /** Log routes that die due to high load! */
4971 dhtlog_handle->insert_route (NULL,
4972 GNUNET_ntohll (incoming->unique_id),
4974 ntohl (incoming->hop_count),
4975 GNUNET_SYSERR, &my_identity,
4976 &incoming->key, peer, NULL);
4982 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
4983 // FIXME: call GNUNET_BLOCK_evaluate (...) -- instead of doing your own bloomfilter!
4985 GNUNET_CONTAINER_bloomfilter_init (incoming->bloomfilter, DHT_BLOOM_SIZE,
4987 GNUNET_assert (msg_ctx.bloom != NULL);
4988 memcpy (&msg_ctx.key, &incoming->key, sizeof (GNUNET_HashCode));
4989 msg_ctx.unique_id = GNUNET_ntohll (incoming->unique_id);
4990 msg_ctx.msg_options = ntohl (incoming->options);
4991 msg_ctx.hop_count = ntohl (incoming->hop_count);
4992 msg_ctx.peer = peer;
4993 msg_ctx.importance = DHT_DEFAULT_P2P_IMPORTANCE + 2; /* Make result routing a higher priority */
4994 msg_ctx.timeout = DHT_DEFAULT_P2P_TIMEOUT;
4995 if ((GNUNET_DHT_RO_RECORD_ROUTE == (msg_ctx.msg_options & GNUNET_DHT_RO_RECORD_ROUTE)) && (ntohl (incoming->outgoing_path_length) > 0))
4997 if (ntohs(message->size) - sizeof(struct GNUNET_DHT_P2PRouteResultMessage) - ntohs(enc_msg->size) !=
4998 ntohl (incoming->outgoing_path_length) * sizeof(struct GNUNET_PeerIdentity))
5000 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Return message indicated a path was included, but sizes are wrong!\nTotal message size %d, enc_msg size %d, left over %d, expected %d\n",
5001 ntohs(message->size), ntohs(enc_msg->size),
5002 ntohs(message->size) - sizeof(struct GNUNET_DHT_P2PRouteResultMessage) - ntohs(enc_msg->size),
5003 ntohl(incoming->outgoing_path_length) * sizeof(struct GNUNET_PeerIdentity));
5006 msg_ctx.path_history = (char *)&incoming[1];
5007 msg_ctx.path_history += ntohs(enc_msg->size);
5008 msg_ctx.path_history_len = ntohl (incoming->outgoing_path_length);
5010 for (i = 0; i < msg_ctx.path_history_len; i++)
5012 path_offset = &msg_ctx.path_history[i * sizeof(struct GNUNET_PeerIdentity)];
5013 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "(handle_p2p_route_result) Key %s Found peer %d:%s\n", GNUNET_h2s(&msg_ctx.key), i, GNUNET_i2s((struct GNUNET_PeerIdentity *)path_offset));
5017 route_result_message (enc_msg, &msg_ctx);
5023 * Receive the HELLO from transport service,
5024 * free current and replace if necessary.
5027 * @param message HELLO message of peer
5030 process_hello (void *cls, const struct GNUNET_MessageHeader *message)
5033 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5034 "Received our `%s' from transport service\n", "HELLO");
5037 GNUNET_assert (message != NULL);
5038 GNUNET_free_non_null (my_hello);
5039 my_hello = GNUNET_malloc (ntohs (message->size));
5040 memcpy (my_hello, message, ntohs (message->size));
5045 * Task run during shutdown.
5051 shutdown_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
5054 struct PeerInfo *pos;
5056 if (transport_handle != NULL)
5058 GNUNET_free_non_null (my_hello);
5059 GNUNET_TRANSPORT_get_hello_cancel (transport_handle, &process_hello,
5061 GNUNET_TRANSPORT_disconnect (transport_handle);
5063 for (bucket_count = lowest_bucket; bucket_count < MAX_BUCKETS;
5066 while (k_buckets[bucket_count].head != NULL)
5068 pos = k_buckets[bucket_count].head;
5070 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5071 "%s:%s Removing peer %s from bucket %d!\n", my_short_id,
5072 "DHT", GNUNET_i2s (&pos->id), bucket_count);
5074 delete_peer (pos, bucket_count);
5077 if (coreAPI != NULL)
5080 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5081 "%s:%s Disconnecting core!\n", my_short_id, "DHT");
5083 GNUNET_CORE_disconnect (coreAPI);
5086 if (datacache != NULL)
5089 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5090 "%s:%s Destroying datacache!\n", my_short_id, "DHT");
5092 GNUNET_DATACACHE_destroy (datacache);
5097 GNUNET_STATISTICS_destroy (stats, GNUNET_YES);
5100 if (dhtlog_handle != NULL)
5102 GNUNET_DHTLOG_disconnect (dhtlog_handle);
5103 dhtlog_handle = NULL;
5105 if (block_context != NULL)
5107 GNUNET_BLOCK_context_destroy (block_context);
5108 block_context = NULL;
5110 GNUNET_free_non_null (my_short_id);
5116 * To be called on core init/fail.
5118 * @param cls service closure
5119 * @param server handle to the server for this service
5120 * @param identity the public identity of this peer
5121 * @param publicKey the public key of this peer
5124 core_init (void *cls,
5125 struct GNUNET_CORE_Handle *server,
5126 const struct GNUNET_PeerIdentity *identity,
5127 const struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded *publicKey)
5133 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5134 "%s: Connection to core FAILED!\n", "dht",
5135 GNUNET_i2s (identity));
5137 GNUNET_SCHEDULER_cancel (cleanup_task);
5138 GNUNET_SCHEDULER_add_now (&shutdown_task, NULL);
5142 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5143 "%s: Core connection initialized, I am peer: %s\n", "dht",
5144 GNUNET_i2s (identity));
5147 /* Copy our identity so we can use it */
5148 memcpy (&my_identity, identity, sizeof (struct GNUNET_PeerIdentity));
5149 if (my_short_id != NULL)
5150 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
5151 "%s Receive CORE INIT message but have already been initialized! Did CORE fail?\n",
5153 my_short_id = GNUNET_strdup (GNUNET_i2s (&my_identity));
5154 /* Set the server to local variable */
5157 if (dhtlog_handle != NULL)
5158 dhtlog_handle->insert_node (NULL, &my_identity);
5162 static struct GNUNET_SERVER_MessageHandler plugin_handlers[] = {
5163 {&handle_dht_local_route_request, NULL, GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE,
5165 {&handle_dht_local_route_stop, NULL,
5166 GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_STOP, 0},
5167 {&handle_dht_control_message, NULL, GNUNET_MESSAGE_TYPE_DHT_CONTROL, 0},
5172 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5173 {&handle_dht_p2p_route_request, GNUNET_MESSAGE_TYPE_DHT_P2P_ROUTE, 0},
5174 {&handle_dht_p2p_route_result, GNUNET_MESSAGE_TYPE_DHT_P2P_ROUTE_RESULT, 0},
5180 * Method called whenever a peer connects.
5182 * @param cls closure
5183 * @param peer peer identity this notification is about
5184 * @param atsi performance data
5187 handle_core_connect (void *cls,
5188 const struct GNUNET_PeerIdentity *peer,
5189 const struct GNUNET_TRANSPORT_ATS_Information *atsi)
5191 struct PeerInfo *ret;
5192 struct DHTPutEntry *put_entry;
5193 /* Check for connect to self message */
5194 if (0 == memcmp(&my_identity, peer, sizeof(struct GNUNET_PeerIdentity)))
5198 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5199 "%s:%s Receives core connect message for peer %s distance %d!\n",
5200 my_short_id, "dht", GNUNET_i2s (peer), distance);
5204 GNUNET_CONTAINER_multihashmap_contains (all_known_peers,
5208 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5209 "%s:%s Received %s message for peer %s, but already have peer in RT!",
5210 my_short_id, "DHT", "CORE CONNECT", GNUNET_i2s (peer));
5215 if ((datacache != NULL) && (GNUNET_YES == put_peer_identities))
5217 put_entry = GNUNET_malloc(sizeof(struct DHTPutEntry) + sizeof (struct GNUNET_PeerIdentity));
5218 put_entry->path_length = 0;
5219 put_entry->data_size = sizeof (struct GNUNET_PeerIdentity);
5220 memcpy(&put_entry[1], peer, sizeof (struct GNUNET_PeerIdentity));
5221 GNUNET_DATACACHE_put (datacache, &peer->hashPubKey,
5222 sizeof(struct DHTPutEntry) + sizeof (struct GNUNET_PeerIdentity),
5223 (char *)put_entry, GNUNET_BLOCK_TYPE_DHT_HELLO,
5224 GNUNET_TIME_absolute_get_forever ());
5225 GNUNET_free (put_entry);
5227 else if (datacache == NULL)
5228 GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "DHT has no connection to datacache!\n");
5229 ret = try_add_peer (peer, find_current_bucket (&peer->hashPubKey), atsi);
5232 newly_found_peers++;
5233 GNUNET_CONTAINER_multihashmap_put (all_known_peers, &peer->hashPubKey,
5235 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
5238 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5239 "%s:%s Adding peer to routing list: %s\n", my_short_id, "DHT",
5240 ret == NULL ? "NOT ADDED" : "PEER ADDED");
5246 * Method called whenever a peer disconnects.
5248 * @param cls closure
5249 * @param peer peer identity this notification is about
5252 handle_core_disconnect (void *cls, const struct GNUNET_PeerIdentity *peer)
5254 struct PeerInfo *to_remove;
5257 /* Check for disconnect from self message */
5258 if (0 == memcmp(&my_identity, peer, sizeof(struct GNUNET_PeerIdentity)))
5261 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5262 "%s:%s: Received peer disconnect message for peer `%s' from %s\n",
5263 my_short_id, "DHT", GNUNET_i2s (peer), "CORE");
5267 GNUNET_CONTAINER_multihashmap_contains (all_known_peers,
5271 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5272 "%s:%s: do not have peer `%s' in RT, can't disconnect!\n",
5273 my_short_id, "DHT", GNUNET_i2s (peer));
5277 increment_stats (STAT_DISCONNECTS);
5278 GNUNET_assert (GNUNET_CONTAINER_multihashmap_contains
5279 (all_known_peers, &peer->hashPubKey));
5281 GNUNET_CONTAINER_multihashmap_get (all_known_peers, &peer->hashPubKey);
5282 GNUNET_assert (to_remove != NULL);
5284 memcmp (peer, &to_remove->id,
5285 sizeof (struct GNUNET_PeerIdentity)));
5286 current_bucket = find_current_bucket (&to_remove->id.hashPubKey);
5287 delete_peer (to_remove, current_bucket);
5292 * Process dht requests.
5294 * @param cls closure
5295 * @param server the initialized server
5296 * @param c configuration to use
5300 struct GNUNET_SERVER_Handle *server,
5301 const struct GNUNET_CONFIGURATION_Handle *c)
5303 struct GNUNET_TIME_Relative next_send_time;
5304 unsigned long long temp_config_num;
5305 char *converge_modifier_buf;
5308 datacache = GNUNET_DATACACHE_create (cfg, "dhtcache");
5309 GNUNET_SERVER_add_handlers (server, plugin_handlers);
5310 GNUNET_SERVER_disconnect_notify (server, &handle_client_disconnect, NULL);
5311 coreAPI = GNUNET_CORE_connect (cfg, /* Main configuration */
5312 DEFAULT_CORE_QUEUE_SIZE, /* queue size */
5313 NULL, /* Closure passed to DHT functions */
5314 &core_init, /* Call core_init once connected */
5315 &handle_core_connect, /* Handle connects */
5316 &handle_core_disconnect, /* remove peers on disconnects */
5317 NULL, /* Do we care about "status" updates? */
5318 NULL, /* Don't want notified about all incoming messages */
5319 GNUNET_NO, /* For header only inbound notification */
5320 NULL, /* Don't want notified about all outbound messages */
5321 GNUNET_NO, /* For header only outbound notification */
5322 core_handlers); /* Register these handlers */
5324 if (coreAPI == NULL)
5326 transport_handle = GNUNET_TRANSPORT_connect (cfg,
5327 NULL, NULL, NULL, NULL, NULL);
5328 if (transport_handle != NULL)
5329 GNUNET_TRANSPORT_get_hello (transport_handle, &process_hello, NULL);
5331 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
5332 "Failed to connect to transport service!\n");
5333 block_context = GNUNET_BLOCK_context_create (cfg);
5334 lowest_bucket = MAX_BUCKETS - 1;
5335 forward_list.hashmap =
5336 GNUNET_CONTAINER_multihashmap_create (MAX_OUTSTANDING_FORWARDS / 10);
5337 forward_list.minHeap =
5338 GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
5339 all_known_peers = GNUNET_CONTAINER_multihashmap_create (MAX_BUCKETS / 8);
5340 recent_find_peer_requests =
5341 GNUNET_CONTAINER_multihashmap_create (MAX_BUCKETS / 8);
5342 GNUNET_assert (all_known_peers != NULL);
5344 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht_testing",
5347 debug_routes = GNUNET_YES;
5351 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "strict_kademlia"))
5353 strict_kademlia = GNUNET_YES;
5357 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "stop_on_closest"))
5359 stop_on_closest = GNUNET_YES;
5363 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "stop_found"))
5365 stop_on_found = GNUNET_YES;
5369 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "malicious_getter"))
5371 malicious_getter = GNUNET_YES;
5372 if (GNUNET_NO == GNUNET_CONFIGURATION_get_value_number (cfg, "DHT",
5373 "MALICIOUS_GET_FREQUENCY",
5374 &malicious_get_frequency))
5375 malicious_get_frequency = DEFAULT_MALICIOUS_GET_FREQUENCY;
5378 if (GNUNET_YES != GNUNET_CONFIGURATION_get_value_number (cfg, "DHT",
5382 max_hops = DEFAULT_MAX_HOPS;
5385 if (GNUNET_YES == GNUNET_CONFIGURATION_get_value_yesno (cfg, "DHT",
5388 use_max_hops = GNUNET_YES;
5392 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "malicious_putter"))
5394 malicious_putter = GNUNET_YES;
5395 if (GNUNET_NO == GNUNET_CONFIGURATION_get_value_number (cfg, "DHT",
5396 "MALICIOUS_PUT_FREQUENCY",
5397 &malicious_put_frequency))
5398 malicious_put_frequency = DEFAULT_MALICIOUS_PUT_FREQUENCY;
5401 dht_republish_frequency = GNUNET_DHT_DEFAULT_REPUBLISH_FREQUENCY;
5403 GNUNET_CONFIGURATION_get_value_number (cfg, "DHT",
5404 "REPLICATION_FREQUENCY",
5407 dht_republish_frequency =
5408 GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES,
5413 GNUNET_CONFIGURATION_get_value_number (cfg, "DHT", "bucket_size",
5416 bucket_size = (unsigned int) temp_config_num;
5420 GNUNET_CONFIGURATION_get_value_number (cfg, "DHT", "kad_alpha",
5421 &kademlia_replication))
5423 kademlia_replication = DEFAULT_KADEMLIA_REPLICATION;
5427 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "malicious_dropper"))
5429 malicious_dropper = GNUNET_YES;
5433 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "republish"))
5434 do_republish = GNUNET_NO;
5437 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "do_find_peer"))
5439 do_find_peer = GNUNET_NO;
5442 do_find_peer = GNUNET_YES;
5445 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "use_real_distance"))
5446 use_real_distance = GNUNET_YES;
5449 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht_testing",
5450 "mysql_logging_extended"))
5452 debug_routes = GNUNET_YES;
5453 debug_routes_extended = GNUNET_YES;
5456 #if DEBUG_DHT_ROUTING
5457 if (GNUNET_YES == debug_routes)
5459 dhtlog_handle = GNUNET_DHTLOG_connect (cfg);
5460 if (dhtlog_handle == NULL)
5462 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
5463 "Could not connect to mysql logging server, logging will not happen!");
5468 converge_option = DHT_CONVERGE_BINARY;
5470 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "converge_linear"))
5472 converge_option = DHT_CONVERGE_LINEAR;
5474 else if (GNUNET_YES ==
5475 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht",
5476 "converge_exponential"))
5478 converge_option = DHT_CONVERGE_EXPONENTIAL;
5480 else if (GNUNET_YES ==
5481 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht",
5484 converge_option = DHT_CONVERGE_RANDOM;
5486 else if (GNUNET_YES ==
5487 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht",
5490 converge_option = DHT_CONVERGE_BINARY;
5493 converge_modifier = 4.0;
5495 GNUNET_CONFIGURATION_get_value_string (cfg, "dht", "converge_modifier",
5496 &converge_modifier_buf))
5498 if (1 != sscanf (converge_modifier_buf, "%f", &converge_modifier))
5500 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
5501 "Failed to read decimal value for %s from `%s'\n",
5502 "CONVERGE_MODIFIER", converge_modifier_buf);
5503 converge_modifier = 0.0;
5505 GNUNET_free (converge_modifier_buf);
5509 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "paper_forwarding"))
5510 paper_forwarding = GNUNET_YES;
5513 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "put_peer_identities"))
5514 put_peer_identities = GNUNET_YES;
5516 stats = GNUNET_STATISTICS_create ("dht", cfg);
5520 GNUNET_STATISTICS_set (stats, STAT_ROUTES, 0, GNUNET_NO);
5521 GNUNET_STATISTICS_set (stats, STAT_ROUTE_FORWARDS, 0, GNUNET_NO);
5522 GNUNET_STATISTICS_set (stats, STAT_ROUTE_FORWARDS_CLOSEST, 0,
5524 GNUNET_STATISTICS_set (stats, STAT_RESULTS, 0, GNUNET_NO);
5525 GNUNET_STATISTICS_set (stats, STAT_RESULTS_TO_CLIENT, 0, GNUNET_NO);
5526 GNUNET_STATISTICS_set (stats, STAT_RESULT_FORWARDS, 0, GNUNET_NO);
5527 GNUNET_STATISTICS_set (stats, STAT_GETS, 0, GNUNET_NO);
5528 GNUNET_STATISTICS_set (stats, STAT_PUTS, 0, GNUNET_NO);
5529 GNUNET_STATISTICS_set (stats, STAT_PUTS_INSERTED, 0, GNUNET_NO);
5530 GNUNET_STATISTICS_set (stats, STAT_FIND_PEER, 0, GNUNET_NO);
5531 GNUNET_STATISTICS_set (stats, STAT_FIND_PEER_START, 0, GNUNET_NO);
5532 GNUNET_STATISTICS_set (stats, STAT_GET_START, 0, GNUNET_NO);
5533 GNUNET_STATISTICS_set (stats, STAT_PUT_START, 0, GNUNET_NO);
5534 GNUNET_STATISTICS_set (stats, STAT_FIND_PEER_REPLY, 0, GNUNET_NO);
5535 GNUNET_STATISTICS_set (stats, STAT_FIND_PEER_ANSWER, 0, GNUNET_NO);
5536 GNUNET_STATISTICS_set (stats, STAT_BLOOM_FIND_PEER, 0, GNUNET_NO);
5537 GNUNET_STATISTICS_set (stats, STAT_GET_REPLY, 0, GNUNET_NO);
5538 GNUNET_STATISTICS_set (stats, STAT_GET_RESPONSE_START, 0, GNUNET_NO);
5539 GNUNET_STATISTICS_set (stats, STAT_HELLOS_PROVIDED, 0, GNUNET_NO);
5540 GNUNET_STATISTICS_set (stats, STAT_DISCONNECTS, 0, GNUNET_NO);
5542 /* FIXME: if there are no recent requests then these never get freed, but alternative is _annoying_! */
5543 recent.hashmap = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT / 2);
5545 GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
5546 if (GNUNET_YES == do_find_peer)
5548 next_send_time.rel_value = DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value +
5549 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_STRONG,
5550 (DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value /
5552 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value);
5553 find_peer_context.start = GNUNET_TIME_absolute_get ();
5554 GNUNET_SCHEDULER_add_delayed (next_send_time,
5555 &send_find_peer_message,
5556 &find_peer_context);
5559 /* Scheduled the task to clean up when shutdown is called */
5560 cleanup_task = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL,
5561 &shutdown_task, NULL);
5565 * The main function for the dht service.
5567 * @param argc number of arguments from the command line
5568 * @param argv command line arguments
5569 * @return 0 ok, 1 on error
5572 main (int argc, char *const *argv)
5577 GNUNET_SERVICE_run (argc,
5580 GNUNET_SERVICE_OPTION_NONE, &run, NULL)) ? 0 : 1;
5581 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (recent.hashmap));
5582 GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent.minHeap));
5583 GNUNET_CONTAINER_multihashmap_destroy (recent_find_peer_requests);
5584 GNUNET_CONTAINER_multihashmap_destroy (recent.hashmap);
5585 GNUNET_CONTAINER_heap_destroy (recent.minHeap);