aboutsummaryrefslogtreecommitdiff
path: root/src/dht/gnunet-service-dht.c
diff options
context:
space:
mode:
authorChristian Grothoff <christian@grothoff.org>2011-09-27 20:47:21 +0000
committerChristian Grothoff <christian@grothoff.org>2011-09-27 20:47:21 +0000
commit18ad006e1f9b322d4760fb1473e8182f0d6ae7f0 (patch)
treeb27c918b33f8ce5fa5651299c9f93ff6e963c3ed /src/dht/gnunet-service-dht.c
parent89bc96f3fc0509f872c8372caac099d81ed36622 (diff)
downloadgnunet-18ad006e1f9b322d4760fb1473e8182f0d6ae7f0.tar.gz
gnunet-18ad006e1f9b322d4760fb1473e8182f0d6ae7f0.zip
DCE
Diffstat (limited to 'src/dht/gnunet-service-dht.c')
-rw-r--r--src/dht/gnunet-service-dht.c4773
1 files changed, 0 insertions, 4773 deletions
diff --git a/src/dht/gnunet-service-dht.c b/src/dht/gnunet-service-dht.c
deleted file mode 100644
index 2650baeb2..000000000
--- a/src/dht/gnunet-service-dht.c
+++ /dev/null
@@ -1,4773 +0,0 @@
1/*
2 This file is part of GNUnet.
3 (C) 2009, 2010, 2011 Christian Grothoff (and other contributing authors)
4
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.
9
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.
14
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.
19*/
20
21/**
22 * @file dht/gnunet-service-dht.c
23 * @brief GNUnet DHT service
24 * @author Christian Grothoff
25 * @author Nathan Evans
26 *
27 * TODO:
28 * - decide which 'benchmark'/test functions to keep (malicious code, kademlia, etc.)
29 * - decide on 'stop_on_closest', 'stop_on_found', 'do_find_peer', 'paper_forwarding'
30 * - use OPTION_MULTIPLE instead of linked list for the forward_list.hashmap
31 * - use different 'struct DHT_MessageContext' for the different types of
32 * messages (currently rather confusing, especially with things like
33 * peer bloom filters occuring when processing replies).
34 * - why do we have request UIDs again?
35 */
36
37#include "platform.h"
38#include "gnunet_block_lib.h"
39#include "gnunet_constants.h"
40#include "gnunet_protocols.h"
41#include "gnunet_nse_service.h"
42#include "gnunet_core_service.h"
43#include "gnunet_util_lib.h"
44#include "gnunet_datacache_lib.h"
45#include "gnunet_transport_service.h"
46#include "gnunet_hello_lib.h"
47#include "gnunet_dht_service.h"
48#include "gnunet_statistics_service.h"
49#include "dhtlog.h"
50#include "dht.h"
51#include <fenv.h>
52
53
54/**
55 * How many buckets will we allow total.
56 */
57#define MAX_BUCKETS sizeof (GNUNET_HashCode) * 8
58
59/**
60 * Should the DHT issue FIND_PEER requests to get better routing tables?
61 */
62#define DEFAULT_DO_FIND_PEER GNUNET_YES
63
64/**
65 * Defines whether find peer requests send their HELLO's outgoing,
66 * or expect replies to contain hellos.
67 */
68#define FIND_PEER_WITH_HELLO GNUNET_YES
69
70/**
71 * What is the maximum number of peers in a given bucket.
72 */
73#define DEFAULT_BUCKET_SIZE 4
74
75#define DEFAULT_CORE_QUEUE_SIZE 32
76
77/**
78 * Minimum number of peers we need for "good" routing,
79 * any less than this and we will allow messages to
80 * travel much further through the network!
81 */
82#define MINIMUM_PEER_THRESHOLD 20
83
84/**
85 * Number of requests we track at most (for routing replies).
86 */
87#define DHT_MAX_RECENT (1024 * 16)
88
89/**
90 * How long do we wait at most when queueing messages with core
91 * that we are sending on behalf of other peers.
92 */
93#define DHT_DEFAULT_P2P_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 10)
94
95/**
96 * Default importance for handling messages on behalf of other peers.
97 */
98#define DHT_DEFAULT_P2P_IMPORTANCE 0
99
100/**
101 * How long to keep recent requests around by default.
102 */
103#define DEFAULT_RECENT_REMOVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 60)
104
105/**
106 * Default time to wait to send find peer messages sent by the dht service.
107 */
108#define DHT_DEFAULT_FIND_PEER_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
109
110/**
111 * Default importance for find peer messages sent by the dht service.
112 */
113#define DHT_DEFAULT_FIND_PEER_IMPORTANCE 8
114
115/**
116 * Default replication parameter for find peer messages sent by the dht service.
117 */
118#define DHT_DEFAULT_FIND_PEER_REPLICATION 4
119
120/**
121 * How long at least to wait before sending another find peer request.
122 */
123#define DHT_MINIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
124
125/**
126 * How long at most to wait before sending another find peer request.
127 */
128#define DHT_MAXIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 8)
129
130/**
131 * How often to update our preference levels for peers in our routing tables.
132 */
133#define DHT_DEFAULT_PREFERENCE_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
134
135/**
136 * How long at most on average will we allow a reply forward to take
137 * (before we quit sending out new requests)
138 */
139#define MAX_REQUEST_TIME GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 1)
140
141/**
142 * How many initial requests to send out (in true Kademlia fashion)
143 */
144#define DEFAULT_KADEMLIA_REPLICATION 3
145
146/**
147 * Default frequency for sending malicious get messages
148 */
149#define DEFAULT_MALICIOUS_GET_FREQUENCY GNUNET_TIME_UNIT_SECONDS
150
151/**
152 * Default frequency for sending malicious put messages
153 */
154#define DEFAULT_MALICIOUS_PUT_FREQUENCY GNUNET_TIME_UNIT_SECONDS
155
156/**
157 * How many time differences between requesting a core send and
158 * the actual callback to remember.
159 */
160#define MAX_REPLY_TIMES 8
161
162
163/**
164 * Linked list of messages to send to clients.
165 */
166struct P2PPendingMessage
167{
168 /**
169 * Pointer to next item in the list
170 */
171 struct P2PPendingMessage *next;
172
173 /**
174 * Pointer to previous item in the list
175 */
176 struct P2PPendingMessage *prev;
177
178 /**
179 * Message importance level.
180 */
181 unsigned int importance;
182
183 /**
184 * Time when this request was scheduled to be sent.
185 */
186 struct GNUNET_TIME_Absolute scheduled;
187
188 /**
189 * How long to wait before sending message.
190 */
191 struct GNUNET_TIME_Relative timeout;
192
193 /**
194 * Actual message to be sent; // avoid allocation
195 */
196 const struct GNUNET_MessageHeader *msg; // msg = (cast) &pm[1]; // memcpy (&pm[1], data, len);
197
198};
199
200
201/**
202 * Per-peer information.
203 */
204struct PeerInfo
205{
206 /**
207 * Next peer entry (DLL)
208 */
209 struct PeerInfo *next;
210
211 /**
212 * Prev peer entry (DLL)
213 */
214 struct PeerInfo *prev;
215
216 /**
217 * Count of outstanding messages for peer.
218 */
219 unsigned int pending_count;
220
221 /**
222 * Head of pending messages to be sent to this peer.
223 */
224 struct P2PPendingMessage *head;
225
226 /**
227 * Tail of pending messages to be sent to this peer.
228 */
229 struct P2PPendingMessage *tail;
230
231 /**
232 * Core handle for sending messages to this peer.
233 */
234 struct GNUNET_CORE_TransmitHandle *th;
235
236 /**
237 * Task for scheduling message sends.
238 */
239 GNUNET_SCHEDULER_TaskIdentifier send_task;
240
241 /**
242 * Task for scheduling preference updates
243 */
244 GNUNET_SCHEDULER_TaskIdentifier preference_task;
245
246 /**
247 * Preference update context
248 */
249 struct GNUNET_CORE_InformationRequestContext *info_ctx;
250
251 /**
252 * What is the identity of the peer?
253 */
254 struct GNUNET_PeerIdentity id;
255
256#if 0
257 /**
258 * What is the average latency for replies received?
259 */
260 struct GNUNET_TIME_Relative latency;
261
262 /**
263 * Transport level distance to peer.
264 */
265 unsigned int distance;
266#endif
267
268 /**
269 * Task for scheduling periodic ping messages for this peer.
270 */
271 GNUNET_SCHEDULER_TaskIdentifier ping_task;
272};
273
274
275/**
276 * Peers are grouped into buckets.
277 */
278struct PeerBucket
279{
280 /**
281 * Head of DLL
282 */
283 struct PeerInfo *head;
284
285 /**
286 * Tail of DLL
287 */
288 struct PeerInfo *tail;
289
290 /**
291 * Number of peers in the bucket.
292 */
293 unsigned int peers_size;
294};
295
296
297/**
298 * Linked list of messages to send to clients.
299 */
300struct PendingMessage
301{
302 /**
303 * Pointer to next item in the list
304 */
305 struct PendingMessage *next;
306
307 /**
308 * Pointer to previous item in the list
309 */
310 struct PendingMessage *prev;
311
312 /**
313 * Actual message to be sent; // avoid allocation
314 */
315 const struct GNUNET_MessageHeader *msg; // msg = (cast) &pm[1]; // memcpy (&pm[1], data, len);
316
317};
318
319
320/**
321 * Struct containing information about a client,
322 * handle to connect to it, and any pending messages
323 * that need to be sent to it.
324 */
325struct ClientList
326{
327 /**
328 * Linked list of active clients
329 */
330 struct ClientList *next;
331
332 /**
333 * The handle to this client
334 */
335 struct GNUNET_SERVER_Client *client_handle;
336
337 /**
338 * Handle to the current transmission request, NULL
339 * if none pending.
340 */
341 struct GNUNET_CONNECTION_TransmitHandle *transmit_handle;
342
343 /**
344 * Linked list of pending messages for this client
345 */
346 struct PendingMessage *pending_head;
347
348 /**
349 * Tail of linked list of pending messages for this client
350 */
351 struct PendingMessage *pending_tail;
352};
353
354
355/**
356 * Context containing information about a DHT message received.
357 */
358struct DHT_MessageContext
359{
360 /**
361 * The client this request was received from.
362 * (NULL if received from another peer)
363 */
364 struct ClientList *client;
365
366 /**
367 * The peer this request was received from.
368 */
369 struct GNUNET_PeerIdentity peer;
370
371 /**
372 * Bloomfilter for this routing request.
373 */
374 struct GNUNET_CONTAINER_BloomFilter *bloom;
375
376 /**
377 * extended query (see gnunet_block_lib.h).
378 */
379 const void *xquery;
380
381 /**
382 * Bloomfilter to filter out duplicate replies.
383 */
384 struct GNUNET_CONTAINER_BloomFilter *reply_bf;
385
386 /**
387 * The key this request was about
388 */
389 GNUNET_HashCode key;
390
391 /**
392 * How long should we wait to transmit this request?
393 */
394 struct GNUNET_TIME_Relative timeout;
395
396 /**
397 * The unique identifier of this request
398 */
399 uint64_t unique_id;
400
401 /**
402 * Number of bytes in xquery.
403 */
404 size_t xquery_size;
405
406 /**
407 * Mutator value for the reply_bf, see gnunet_block_lib.h
408 */
409 uint32_t reply_bf_mutator;
410
411 /**
412 * Desired replication level
413 */
414 uint32_t replication;
415
416 /**
417 * Network size estimate, either ours or the sum of
418 * those routed to thus far. =~ Log of number of peers
419 * chosen from for this request.
420 */
421 uint32_t network_size;
422
423 /**
424 * Any message options for this request
425 */
426 uint32_t msg_options;
427
428 /**
429 * How many hops has the message already traversed?
430 */
431 uint32_t hop_count;
432
433 /**
434 * How many peer identities are present in the path history?
435 */
436 uint32_t path_history_len;
437
438 /**
439 * Path history.
440 */
441 char *path_history;
442
443 /**
444 * How important is this message?
445 */
446 unsigned int importance;
447
448 /**
449 * Should we (still) forward the request on to other peers?
450 */
451 int do_forward;
452
453 /**
454 * Did we forward this message? (may need to remember it!)
455 */
456 int forwarded;
457
458 /**
459 * Are we the closest known peer to this key (out of our neighbors?)
460 */
461 int closest;
462};
463
464
465/**
466 * Record used for remembering what peers are waiting for what
467 * responses (based on search key).
468 */
469struct DHTRouteSource
470{
471 /**
472 * This is a DLL.
473 */
474 struct DHTRouteSource *next;
475
476 /**
477 * This is a DLL.
478 */
479 struct DHTRouteSource *prev;
480
481 /**
482 * UID of the request, 0 if from another peer.
483 */
484 uint64_t uid;
485
486 /**
487 * Source of the request. Replies should be forwarded to
488 * this peer.
489 */
490 struct GNUNET_PeerIdentity source;
491
492 /**
493 * If this was a local request, remember the client; otherwise NULL.
494 */
495 struct ClientList *client;
496
497 /**
498 * Pointer to this nodes heap location (for removal)
499 */
500 struct GNUNET_CONTAINER_HeapNode *hnode;
501
502 /**
503 * Back pointer to the record storing this information.
504 */
505 struct DHTQueryRecord *record;
506
507 /**
508 * Task to remove this entry on timeout.
509 */
510 GNUNET_SCHEDULER_TaskIdentifier delete_task;
511
512 /**
513 * Bloomfilter of peers we have already sent back as
514 * replies to the initial request. Allows us to not
515 * forward the same peer multiple times for a find peer
516 * request.
517 */
518 struct GNUNET_CONTAINER_BloomFilter *find_peers_responded;
519
520};
521
522
523/**
524 * Entry in the DHT routing table.
525 */
526struct DHTQueryRecord
527{
528 /**
529 * Head of DLL for result forwarding.
530 */
531 struct DHTRouteSource *head;
532
533 /**
534 * Tail of DLL for result forwarding.
535 */
536 struct DHTRouteSource *tail;
537
538 /**
539 * Key that the record concerns.
540 */
541 GNUNET_HashCode key;
542
543};
544
545
546/**
547 * Context used to calculate the number of find peer messages
548 * per X time units since our last scheduled find peer message
549 * was sent. If we have seen too many messages, delay or don't
550 * send our own out.
551 */
552struct FindPeerMessageContext
553{
554 unsigned int count;
555
556 struct GNUNET_TIME_Absolute start;
557
558 struct GNUNET_TIME_Absolute end;
559};
560
561
562/**
563 * DHT Routing results structure
564 */
565struct DHTResults
566{
567 /**
568 * Min heap for removal upon reaching limit
569 */
570 struct GNUNET_CONTAINER_Heap *minHeap;
571
572
573 /**
574 * Hashmap for fast key based lookup
575 */
576 struct GNUNET_CONTAINER_MultiHashMap *hashmap;
577};
578
579
580/**
581 * DHT structure for recent requests.
582 */
583struct RecentRequests
584{
585 /**
586 * Min heap for removal upon reaching limit
587 */
588 struct GNUNET_CONTAINER_Heap *minHeap;
589
590#if HAVE_UID_FOR_TESTING > 1
591 /**
592 * Hashmap for key based lookup
593 */
594 struct GNUNET_CONTAINER_MultiHashMap *hashmap;
595#endif
596
597};
598
599
600struct RecentRequest
601{
602 /**
603 * Position of this node in the min heap.
604 */
605 struct GNUNET_CONTAINER_HeapNode *heap_node;
606
607 /**
608 * Bloomfilter containing entries for peers
609 * we forwarded this request to.
610 */
611 struct GNUNET_CONTAINER_BloomFilter *bloom;
612
613 /**
614 * Timestamp of this request, for ordering
615 * the min heap.
616 */
617 struct GNUNET_TIME_Absolute timestamp;
618
619 /**
620 * Key of this request.
621 */
622 GNUNET_HashCode key;
623
624 /**
625 * Unique identifier for this request, 0 if from another peer.
626 */
627 uint64_t uid;
628
629 /**
630 * Task to remove this entry on timeout.
631 */
632 GNUNET_SCHEDULER_TaskIdentifier remove_task;
633};
634
635
636/**
637 * log of the current network size estimate, used as the point where
638 * we switch between random and deterministic routing. Default
639 * value of 4.0 is used if NSE module is not available (i.e. not
640 * configured).
641 */
642static double log_of_network_size_estimate = 4.0;
643
644/**
645 * Recent requests by hash/uid and by time inserted.
646 */
647static struct RecentRequests recent;
648
649/**
650 * Context to use to calculate find peer rates.
651 */
652static struct FindPeerMessageContext find_peer_context;
653
654/**
655 * Don't use our routing algorithm, always route
656 * to closest peer; initially send requests to 3
657 * peers.
658 */
659static int strict_kademlia;
660
661/**
662 * Routing option to end routing when closest peer found.
663 */
664static int stop_on_closest;
665
666/**
667 * Routing option to end routing when data is found.
668 */
669static int stop_on_found;
670
671/**
672 * Whether DHT needs to manage find peer requests, or
673 * an external force will do it on behalf of the DHT.
674 */
675static int do_find_peer;
676
677/**
678 * Use exactly the forwarding formula as described in
679 * the paper if set to GNUNET_YES, otherwise use the
680 * slightly modified version.
681 */
682static int paper_forwarding;
683
684/**
685 * PUT Peer Identities of peers we know about into
686 * the datacache.
687 */
688static int put_peer_identities;
689
690/**
691 * Use the "real" distance metric when selecting the
692 * next routing hop. Can be less accurate.
693 */
694static int use_real_distance;
695
696/**
697 * How many peers have we added since we sent out our last
698 * find peer request?
699 */
700static unsigned int newly_found_peers;
701
702/**
703 * Container of active queries we should remember
704 */
705static struct DHTResults forward_list;
706
707/**
708 * Handle to the datacache service (for inserting/retrieving data)
709 */
710static struct GNUNET_DATACACHE_Handle *datacache;
711
712/**
713 * Handle for the statistics service.
714 */
715struct GNUNET_STATISTICS_Handle *stats;
716
717/**
718 * Handle to get our current HELLO.
719 */
720static struct GNUNET_TRANSPORT_GetHelloHandle *ghh;
721
722/**
723 * The configuration the DHT service is running with
724 */
725static const struct GNUNET_CONFIGURATION_Handle *cfg;
726
727/**
728 * Handle to the core service
729 */
730static struct GNUNET_CORE_Handle *coreAPI;
731
732/**
733 * Handle to the transport service, for getting our hello
734 */
735static struct GNUNET_TRANSPORT_Handle *transport_handle;
736
737/**
738 * The identity of our peer.
739 */
740static struct GNUNET_PeerIdentity my_identity;
741
742/**
743 * Short id of the peer, for printing
744 */
745static char *my_short_id;
746
747/**
748 * Our HELLO
749 */
750static struct GNUNET_MessageHeader *my_hello;
751
752/**
753 * Task to run when we shut down, cleaning up all our trash
754 */
755static GNUNET_SCHEDULER_TaskIdentifier cleanup_task;
756
757/**
758 * The lowest currently used bucket.
759 */
760static unsigned int lowest_bucket; /* Initially equal to MAX_BUCKETS - 1 */
761
762/**
763 * The buckets (Kademlia routing table, complete with growth).
764 * Array of size MAX_BUCKET_SIZE.
765 */
766static struct PeerBucket k_buckets[MAX_BUCKETS];
767
768/**
769 * Hash map of all known peers, for easy removal from k_buckets on disconnect.
770 */
771static struct GNUNET_CONTAINER_MultiHashMap *all_known_peers;
772
773/**
774 * Recently seen find peer requests.
775 */
776static struct GNUNET_CONTAINER_MultiHashMap *recent_find_peer_requests;
777
778/**
779 * Maximum size for each bucket.
780 */
781static unsigned int bucket_size = DEFAULT_BUCKET_SIZE;
782
783/**
784 * List of active clients.
785 */
786static struct ClientList *client_list;
787
788/**
789 * Handle to the DHT logger.
790 */
791static struct GNUNET_DHTLOG_Handle *dhtlog_handle;
792
793/**
794 * Whether or not to send routing debugging information
795 * to the dht logging server
796 */
797static unsigned int debug_routes;
798
799/**
800 * Whether or not to send FULL route information to
801 * logging server
802 */
803static unsigned int debug_routes_extended;
804
805/**
806 * GNUNET_YES or GNUNET_NO, whether or not to act as
807 * a malicious node which drops all messages
808 */
809static unsigned int malicious_dropper;
810
811/**
812 * GNUNET_YES or GNUNET_NO, whether or not to act as
813 * a malicious node which sends out lots of GETS
814 */
815static unsigned int malicious_getter;
816
817/**
818 * GNUNET_YES or GNUNET_NO, whether or not to act as
819 * a malicious node which sends out lots of PUTS
820 */
821static unsigned int malicious_putter;
822
823/**
824 * Frequency for malicious get requests.
825 */
826static struct GNUNET_TIME_Relative malicious_get_frequency;
827
828/**
829 * Frequency for malicious put requests.
830 */
831static struct GNUNET_TIME_Relative malicious_put_frequency;
832
833/**
834 * Kademlia replication
835 */
836static unsigned long long kademlia_replication;
837
838/**
839 * Reply times for requests, if we are busy, don't send any
840 * more requests!
841 */
842static struct GNUNET_TIME_Relative reply_times[MAX_REPLY_TIMES];
843
844/**
845 * Current counter for replies.
846 */
847static unsigned int reply_counter;
848
849/**
850 * Our handle to the BLOCK library.
851 */
852static struct GNUNET_BLOCK_Context *block_context;
853
854/**
855 * Network size estimation handle.
856 */
857static struct GNUNET_NSE_Handle *nse;
858
859
860/**
861 * Callback that is called when network size estimate is updated.
862 *
863 * @param cls closure
864 * @param timestamp time when the estimate was received from the server (or created by the server)
865 * @param logestimate the log(Base 2) value of the current network size estimate
866 * @param std_dev standard deviation for the estimate
867 *
868 */
869static void
870update_network_size_estimate (void *cls, struct GNUNET_TIME_Absolute timestamp,
871 double logestimate, double std_dev)
872{
873 log_of_network_size_estimate = logestimate;
874}
875
876
877/**
878 * Forward declaration.
879 */
880static size_t
881send_generic_reply (void *cls, size_t size, void *buf);
882
883
884/** Declare here so retry_core_send is aware of it */
885static size_t
886core_transmit_notify (void *cls, size_t size, void *buf);
887
888
889/**
890 * Convert unique ID to hash code.
891 *
892 * @param uid unique ID to convert
893 * @param hash set to uid (extended with zeros)
894 */
895static void
896hash_from_uid (uint64_t uid, GNUNET_HashCode * hash)
897{
898 memset (hash, 0, sizeof (GNUNET_HashCode));
899 *((uint64_t *) hash) = uid;
900}
901
902
903/**
904 * Given the largest send delay, artificially decrease it
905 * so the next time around we may have a chance at sending
906 * again.
907 */
908static void
909decrease_max_send_delay (struct GNUNET_TIME_Relative max_time)
910{
911 unsigned int i;
912
913 for (i = 0; i < MAX_REPLY_TIMES; i++)
914 {
915 if (reply_times[i].rel_value == max_time.rel_value)
916 {
917 reply_times[i].rel_value = reply_times[i].rel_value / 2;
918 return;
919 }
920 }
921}
922
923
924/**
925 * Find the maximum send time of the recently sent values.
926 *
927 * @return the average time between asking core to send a message
928 * and when the buffer for copying it is passed
929 */
930static struct GNUNET_TIME_Relative
931get_max_send_delay ()
932{
933 unsigned int i;
934 struct GNUNET_TIME_Relative max_time;
935
936 max_time = GNUNET_TIME_relative_get_zero ();
937
938 for (i = 0; i < MAX_REPLY_TIMES; i++)
939 {
940 if (reply_times[i].rel_value > max_time.rel_value)
941 max_time.rel_value = reply_times[i].rel_value;
942 }
943#if DEBUG_DHT
944 if (max_time.rel_value > MAX_REQUEST_TIME.rel_value)
945 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Max send delay was %llu\n",
946 (unsigned long long) max_time.rel_value);
947#endif
948 return max_time;
949}
950
951
952static void
953increment_stats (const char *value)
954{
955 if (stats == NULL)
956 return;
957 GNUNET_STATISTICS_update (stats, value, 1, GNUNET_NO);
958}
959
960
961static void
962decrement_stats (const char *value)
963{
964 if (stats == NULL)
965 return;
966 GNUNET_STATISTICS_update (stats, value, -1, GNUNET_NO);
967}
968
969
970/**
971 * Try to send another message from our core send list
972 */
973static void
974try_core_send (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
975{
976 struct PeerInfo *peer = cls;
977 struct P2PPendingMessage *pending;
978 size_t ssize;
979
980 peer->send_task = GNUNET_SCHEDULER_NO_TASK;
981
982 if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
983 return;
984
985 if (peer->th != NULL)
986 return; /* Message send already in progress */
987
988 pending = peer->head;
989 if (pending != NULL)
990 {
991 ssize = ntohs (pending->msg->size);
992#if DEBUG_DHT > 1
993 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
994 "`%s:%s': Calling notify_transmit_ready with size %d for peer %s\n",
995 my_short_id, "DHT", ssize, GNUNET_i2s (&peer->id));
996#endif
997 pending->scheduled = GNUNET_TIME_absolute_get ();
998 reply_counter++;
999 if (reply_counter >= MAX_REPLY_TIMES)
1000 reply_counter = 0;
1001 peer->th =
1002 GNUNET_CORE_notify_transmit_ready (coreAPI, GNUNET_YES,
1003 pending->importance,
1004 pending->timeout, &peer->id, ssize,
1005 &core_transmit_notify, peer);
1006 if (peer->th == NULL)
1007 increment_stats ("# notify transmit ready failed");
1008 }
1009}
1010
1011
1012/**
1013 * Function called to send a request out to another peer.
1014 * Called both for locally initiated requests and those
1015 * received from other peers.
1016 *
1017 * @param msg the encapsulated message
1018 * @param peer the peer to forward the message to
1019 * @param msg_ctx the context of the message (hop count, bloom, etc.)
1020 */
1021static void
1022forward_result_message (const struct GNUNET_MessageHeader *msg,
1023 struct PeerInfo *peer,
1024 struct DHT_MessageContext *msg_ctx)
1025{
1026 struct GNUNET_DHT_P2PRouteResultMessage *result_message;
1027 struct P2PPendingMessage *pending;
1028 size_t msize;
1029 size_t psize;
1030 char *path_start;
1031 char *path_offset;
1032
1033#if DEBUG_PATH
1034 unsigned int i;
1035#endif
1036
1037 increment_stats (STAT_RESULT_FORWARDS);
1038 msize =
1039 sizeof (struct GNUNET_DHT_P2PRouteResultMessage) + ntohs (msg->size) +
1040 (sizeof (struct GNUNET_PeerIdentity) * msg_ctx->path_history_len);
1041 GNUNET_assert (msize <= GNUNET_SERVER_MAX_MESSAGE_SIZE);
1042 psize = sizeof (struct P2PPendingMessage) + msize;
1043 pending = GNUNET_malloc (psize);
1044 pending->msg = (struct GNUNET_MessageHeader *) &pending[1];
1045 pending->importance = DHT_SEND_PRIORITY;
1046 pending->timeout = GNUNET_TIME_relative_get_forever ();
1047 result_message = (struct GNUNET_DHT_P2PRouteResultMessage *) pending->msg;
1048 result_message->header.size = htons (msize);
1049 result_message->header.type =
1050 htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ROUTE_RESULT);
1051 result_message->outgoing_path_length = htonl (msg_ctx->path_history_len);
1052 if (msg_ctx->path_history_len > 0)
1053 {
1054 /* End of pending is where enc_msg starts */
1055 path_start = (char *) &pending[1];
1056 /* Offset by the size of the enc_msg */
1057 path_start += ntohs (msg->size);
1058 memcpy (path_start, msg_ctx->path_history,
1059 msg_ctx->path_history_len * (sizeof (struct GNUNET_PeerIdentity)));
1060#if DEBUG_PATH
1061 for (i = 0; i < msg_ctx->path_history_len; i++)
1062 {
1063 path_offset =
1064 &msg_ctx->path_history[i * sizeof (struct GNUNET_PeerIdentity)];
1065 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1066 "(forward_result) Key %s Found peer %d:%s\n",
1067 GNUNET_h2s (&msg_ctx->key), i,
1068 GNUNET_i2s ((struct GNUNET_PeerIdentity *) path_offset));
1069 }
1070#endif
1071 }
1072 result_message->options = htonl (msg_ctx->msg_options);
1073 result_message->hop_count = htonl (msg_ctx->hop_count + 1);
1074#if HAVE_UID_FOR_TESTING
1075 result_message->unique_id = GNUNET_htonll (msg_ctx->unique_id);
1076#endif
1077 memcpy (&result_message->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
1078 /* Copy the enc_msg, then the path history as well! */
1079 memcpy (&result_message[1], msg, ntohs (msg->size));
1080 path_offset = (char *) &result_message[1];
1081 path_offset += ntohs (msg->size);
1082 /* If we have path history, copy it to the end of the whole thing */
1083 if (msg_ctx->path_history_len > 0)
1084 memcpy (path_offset, msg_ctx->path_history,
1085 msg_ctx->path_history_len * (sizeof (struct GNUNET_PeerIdentity)));
1086#if DEBUG_DHT > 1
1087 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1088 "%s:%s Adding pending message size %d for peer %s\n", my_short_id,
1089 "DHT", msize, GNUNET_i2s (&peer->id));
1090#endif
1091 peer->pending_count++;
1092 increment_stats ("# pending messages scheduled");
1093 GNUNET_CONTAINER_DLL_insert_after (peer->head, peer->tail, peer->tail,
1094 pending);
1095 if (peer->send_task == GNUNET_SCHEDULER_NO_TASK)
1096 peer->send_task = GNUNET_SCHEDULER_add_now (&try_core_send, peer);
1097}
1098
1099
1100/**
1101 * Called when core is ready to send a message we asked for
1102 * out to the destination.
1103 *
1104 * @param cls closure (NULL)
1105 * @param size number of bytes available in buf
1106 * @param buf where the callee should write the message
1107 * @return number of bytes written to buf
1108 */
1109static size_t
1110core_transmit_notify (void *cls, size_t size, void *buf)
1111{
1112 struct PeerInfo *peer = cls;
1113 char *cbuf = buf;
1114 struct P2PPendingMessage *pending;
1115
1116 size_t off;
1117 size_t msize;
1118
1119 peer->th = NULL;
1120 if (buf == NULL)
1121 {
1122 /* client disconnected */
1123#if DEBUG_DHT
1124 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "`%s:%s': buffer was NULL\n",
1125 my_short_id, "DHT");
1126#endif
1127 return 0;
1128 }
1129
1130 if (peer->head == NULL)
1131 return 0;
1132
1133 off = 0;
1134 pending = peer->head;
1135#if DUMB
1136 reply_times[reply_counter] =
1137 GNUNET_TIME_absolute_get_difference (pending->scheduled,
1138 GNUNET_TIME_absolute_get ());
1139 msize = ntohs (pending->msg->size);
1140 if (msize <= size)
1141 {
1142 off = msize;
1143 memcpy (cbuf, pending->msg, msize);
1144 peer->pending_count--;
1145 increment_stats ("# pending messages sent");
1146 GNUNET_assert (peer->pending_count >= 0);
1147 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1148 GNUNET_free (pending);
1149 }
1150#else
1151 while (NULL != pending &&
1152 (size - off >= (msize = ntohs (pending->msg->size))))
1153 {
1154 memcpy (&cbuf[off], pending->msg, msize);
1155 off += msize;
1156 peer->pending_count--;
1157 increment_stats ("# pending messages sent");
1158 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
1159 GNUNET_free (pending);
1160 pending = peer->head;
1161 }
1162#endif
1163 if ((peer->head != NULL) && (peer->send_task == GNUNET_SCHEDULER_NO_TASK))
1164 peer->send_task = GNUNET_SCHEDULER_add_now (&try_core_send, peer);
1165
1166 return off;
1167}
1168
1169
1170/**
1171 * Compute the distance between have and target as a 32-bit value.
1172 * Differences in the lower bits must count stronger than differences
1173 * in the higher bits.
1174 *
1175 * @return 0 if have==target, otherwise a number
1176 * that is larger as the distance between
1177 * the two hash codes increases
1178 */
1179static unsigned int
1180distance (const GNUNET_HashCode * target, const GNUNET_HashCode * have)
1181{
1182 unsigned int bucket;
1183 unsigned int msb;
1184 unsigned int lsb;
1185 unsigned int i;
1186
1187 /* We have to represent the distance between two 2^9 (=512)-bit
1188 * numbers as a 2^5 (=32)-bit number with "0" being used for the
1189 * two numbers being identical; furthermore, we need to
1190 * guarantee that a difference in the number of matching
1191 * bits is always represented in the result.
1192 *
1193 * We use 2^32/2^9 numerical values to distinguish between
1194 * hash codes that have the same LSB bit distance and
1195 * use the highest 2^9 bits of the result to signify the
1196 * number of (mis)matching LSB bits; if we have 0 matching
1197 * and hence 512 mismatching LSB bits we return -1 (since
1198 * 512 itself cannot be represented with 9 bits) */
1199
1200 /* first, calculate the most significant 9 bits of our
1201 * result, aka the number of LSBs */
1202 bucket = GNUNET_CRYPTO_hash_matching_bits (target, have);
1203 /* bucket is now a value between 0 and 512 */
1204 if (bucket == 512)
1205 return 0; /* perfect match */
1206 if (bucket == 0)
1207 return (unsigned int) -1; /* LSB differs; use max (if we did the bit-shifting
1208 * below, we'd end up with max+1 (overflow)) */
1209
1210 /* calculate the most significant bits of the final result */
1211 msb = (512 - bucket) << (32 - 9);
1212 /* calculate the 32-9 least significant bits of the final result by
1213 * looking at the differences in the 32-9 bits following the
1214 * mismatching bit at 'bucket' */
1215 lsb = 0;
1216 for (i = bucket + 1;
1217 (i < sizeof (GNUNET_HashCode) * 8) && (i < bucket + 1 + 32 - 9); i++)
1218 {
1219 if (GNUNET_CRYPTO_hash_get_bit (target, i) !=
1220 GNUNET_CRYPTO_hash_get_bit (have, i))
1221 lsb |= (1 << (bucket + 32 - 9 - i)); /* first bit set will be 10,
1222 * last bit set will be 31 -- if
1223 * i does not reach 512 first... */
1224 }
1225 return msb | lsb;
1226}
1227
1228
1229/**
1230 * Return a number that is larger the closer the
1231 * "have" GNUNET_hash code is to the "target".
1232 *
1233 * @return inverse distance metric, non-zero.
1234 * Must fudge the value if NO bits match.
1235 */
1236static unsigned int
1237inverse_distance (const GNUNET_HashCode * target, const GNUNET_HashCode * have)
1238{
1239 if (GNUNET_CRYPTO_hash_matching_bits (target, have) == 0)
1240 return 1; /* Never return 0! */
1241 return ((unsigned int) -1) - distance (target, have);
1242}
1243
1244
1245/**
1246 * Find the optimal bucket for this key, regardless
1247 * of the current number of buckets in use.
1248 *
1249 * @param hc the hashcode to compare our identity to
1250 *
1251 * @return the proper bucket index, or GNUNET_SYSERR
1252 * on error (same hashcode)
1253 */
1254static int
1255find_bucket (const GNUNET_HashCode * hc)
1256{
1257 unsigned int bits;
1258
1259 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey, hc);
1260 if (bits == MAX_BUCKETS)
1261 return GNUNET_SYSERR;
1262 return MAX_BUCKETS - bits - 1;
1263}
1264
1265
1266/**
1267 * Find which k-bucket this peer should go into,
1268 * taking into account the size of the k-bucket
1269 * array. This means that if more bits match than
1270 * there are currently buckets, lowest_bucket will
1271 * be returned.
1272 *
1273 * @param hc GNUNET_HashCode we are finding the bucket for.
1274 *
1275 * @return the proper bucket index for this key,
1276 * or GNUNET_SYSERR on error (same hashcode)
1277 */
1278static int
1279find_current_bucket (const GNUNET_HashCode * hc)
1280{
1281 int actual_bucket;
1282
1283 actual_bucket = find_bucket (hc);
1284 if (actual_bucket == GNUNET_SYSERR) /* hc and our peer identity match! */
1285 return lowest_bucket;
1286 if (actual_bucket < lowest_bucket) /* actual_bucket not yet used */
1287 return lowest_bucket;
1288 return actual_bucket;
1289}
1290
1291
1292/**
1293 * Find a routing table entry from a peer identity
1294 *
1295 * @param peer the peer identity to look up
1296 *
1297 * @return the routing table entry, or NULL if not found
1298 */
1299static struct PeerInfo *
1300find_peer_by_id (const struct GNUNET_PeerIdentity *peer)
1301{
1302 int bucket;
1303 struct PeerInfo *pos;
1304
1305 bucket = find_current_bucket (&peer->hashPubKey);
1306
1307 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1308 return NULL;
1309
1310 pos = k_buckets[bucket].head;
1311 while (pos != NULL)
1312 {
1313 if (0 == memcmp (&pos->id, peer, sizeof (struct GNUNET_PeerIdentity)))
1314 return pos;
1315 pos = pos->next;
1316 }
1317 return NULL; /* No such peer. */
1318}
1319
1320/* Forward declaration */
1321static void
1322update_core_preference (void *cls,
1323 const struct GNUNET_SCHEDULER_TaskContext *tc);
1324
1325
1326/**
1327 * Function called with statistics about the given peer.
1328 *
1329 * @param cls closure
1330 * @param peer identifies the peer
1331 * @param bpm_out set to the current bandwidth limit (sending) for this peer
1332 * @param amount set to the amount that was actually reserved or unreserved;
1333 * either the full requested amount or zero (no partial reservations)
1334 * @param res_delay if the reservation could not be satisfied (amount was 0), how
1335 * long should the client wait until re-trying?
1336 * @param preference current traffic preference for the given peer
1337 */
1338static void
1339update_core_preference_finish (void *cls,
1340 const struct GNUNET_PeerIdentity *peer,
1341 struct GNUNET_BANDWIDTH_Value32NBO bpm_out,
1342 int32_t amount,
1343 struct GNUNET_TIME_Relative res_delay,
1344 uint64_t preference)
1345{
1346 struct PeerInfo *peer_info = cls;
1347
1348 peer_info->info_ctx = NULL;
1349 GNUNET_SCHEDULER_add_delayed (DHT_DEFAULT_PREFERENCE_INTERVAL,
1350 &update_core_preference, peer_info);
1351}
1352
1353static void
1354update_core_preference (void *cls,
1355 const struct GNUNET_SCHEDULER_TaskContext *tc)
1356{
1357 struct PeerInfo *peer = cls;
1358 uint64_t preference;
1359 unsigned int matching;
1360
1361 if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
1362 {
1363 return;
1364 }
1365 matching =
1366 GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey,
1367 &peer->id.hashPubKey);
1368 if (matching >= 64)
1369 {
1370#if DEBUG_DHT
1371 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1372 "Peer identifier matches by %u bits, only shifting as much as we can!\n",
1373 matching);
1374#endif
1375 matching = 63;
1376 }
1377 preference = 1LL << matching;
1378 peer->info_ctx =
1379 GNUNET_CORE_peer_change_preference (coreAPI, &peer->id,
1380 GNUNET_TIME_UNIT_FOREVER_REL,
1381 GNUNET_BANDWIDTH_VALUE_MAX, 0,
1382 preference,
1383 &update_core_preference_finish, peer);
1384}
1385
1386
1387/**
1388 * Given a peer and its corresponding bucket,
1389 * remove it from that bucket. Does not free
1390 * the PeerInfo struct, nor cancel messages
1391 * or free messages waiting to be sent to this
1392 * peer!
1393 *
1394 * @param peer the peer to remove
1395 * @param bucket the bucket the peer belongs to
1396 */
1397static void
1398remove_peer (struct PeerInfo *peer, unsigned int bucket)
1399{
1400 GNUNET_assert (k_buckets[bucket].peers_size > 0);
1401 GNUNET_CONTAINER_DLL_remove (k_buckets[bucket].head, k_buckets[bucket].tail,
1402 peer);
1403 k_buckets[bucket].peers_size--;
1404#if CHANGE_LOWEST
1405 if ((bucket == lowest_bucket) && (k_buckets[lowest_bucket].peers_size == 0) &&
1406 (lowest_bucket < MAX_BUCKETS - 1))
1407 lowest_bucket++;
1408#endif
1409}
1410
1411/**
1412 * Removes peer from a bucket, then frees associated
1413 * resources and frees peer.
1414 *
1415 * @param peer peer to be removed and freed
1416 * @param bucket which bucket this peer belongs to
1417 */
1418static void
1419delete_peer (struct PeerInfo *peer, unsigned int bucket)
1420{
1421 struct P2PPendingMessage *pos;
1422 struct P2PPendingMessage *next;
1423
1424 remove_peer (peer, bucket); /* First remove the peer from its bucket */
1425 if (peer->send_task != GNUNET_SCHEDULER_NO_TASK)
1426 GNUNET_SCHEDULER_cancel (peer->send_task);
1427 if ((peer->th != NULL) && (coreAPI != NULL))
1428 GNUNET_CORE_notify_transmit_ready_cancel (peer->th);
1429
1430 pos = peer->head;
1431 while (pos != NULL) /* Remove any pending messages for this peer */
1432 {
1433 increment_stats
1434 ("# dht pending messages discarded (due to disconnect/shutdown)");
1435 next = pos->next;
1436 GNUNET_free (pos);
1437 pos = next;
1438 }
1439
1440 GNUNET_assert (GNUNET_CONTAINER_multihashmap_contains
1441 (all_known_peers, &peer->id.hashPubKey));
1442 GNUNET_assert (GNUNET_YES ==
1443 GNUNET_CONTAINER_multihashmap_remove (all_known_peers,
1444 &peer->id.hashPubKey,
1445 peer));
1446 GNUNET_free (peer);
1447 decrement_stats (STAT_PEERS_KNOWN);
1448}
1449
1450
1451/**
1452 * Iterator over hash map entries.
1453 *
1454 * @param cls closure
1455 * @param key current key code
1456 * @param value PeerInfo of the peer to move to new lowest bucket
1457 * @return GNUNET_YES if we should continue to
1458 * iterate,
1459 * GNUNET_NO if not.
1460 */
1461static int
1462move_lowest_bucket (void *cls, const GNUNET_HashCode * key, void *value)
1463{
1464 struct PeerInfo *peer = value;
1465 int new_bucket;
1466
1467 GNUNET_assert (lowest_bucket > 0);
1468 new_bucket = lowest_bucket - 1;
1469 remove_peer (peer, lowest_bucket);
1470 GNUNET_CONTAINER_DLL_insert_after (k_buckets[new_bucket].head,
1471 k_buckets[new_bucket].tail,
1472 k_buckets[new_bucket].tail, peer);
1473 k_buckets[new_bucket].peers_size++;
1474 return GNUNET_YES;
1475}
1476
1477
1478/**
1479 * The current lowest bucket is full, so change the lowest
1480 * bucket to the next lower down, and move any appropriate
1481 * entries in the current lowest bucket to the new bucket.
1482 */
1483static void
1484enable_next_bucket ()
1485{
1486 struct GNUNET_CONTAINER_MultiHashMap *to_remove;
1487 struct PeerInfo *pos;
1488
1489 GNUNET_assert (lowest_bucket > 0);
1490 to_remove = GNUNET_CONTAINER_multihashmap_create (bucket_size);
1491 pos = k_buckets[lowest_bucket].head;
1492
1493 /* Populate the array of peers which should be in the next lowest bucket */
1494 while (pos != NULL)
1495 {
1496 if (find_bucket (&pos->id.hashPubKey) < lowest_bucket)
1497 GNUNET_CONTAINER_multihashmap_put (to_remove, &pos->id.hashPubKey, pos,
1498 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
1499 pos = pos->next;
1500 }
1501
1502 /* Remove peers from lowest bucket, insert into next lowest bucket */
1503 GNUNET_CONTAINER_multihashmap_iterate (to_remove, &move_lowest_bucket, NULL);
1504 GNUNET_CONTAINER_multihashmap_destroy (to_remove);
1505 lowest_bucket = lowest_bucket - 1;
1506}
1507
1508
1509/**
1510 * Find the closest peer in our routing table to the
1511 * given hashcode.
1512 *
1513 * @return The closest peer in our routing table to the
1514 * key, or NULL on error.
1515 */
1516static struct PeerInfo *
1517find_closest_peer (const GNUNET_HashCode * hc)
1518{
1519 struct PeerInfo *pos;
1520 struct PeerInfo *current_closest;
1521 unsigned int lowest_distance;
1522 unsigned int temp_distance;
1523 int bucket;
1524 int count;
1525
1526 lowest_distance = -1;
1527
1528 if (k_buckets[lowest_bucket].peers_size == 0)
1529 return NULL;
1530
1531 current_closest = NULL;
1532 for (bucket = lowest_bucket; bucket < MAX_BUCKETS; bucket++)
1533 {
1534 pos = k_buckets[bucket].head;
1535 count = 0;
1536 while ((pos != NULL) && (count < bucket_size))
1537 {
1538 temp_distance = distance (&pos->id.hashPubKey, hc);
1539 if (temp_distance <= lowest_distance)
1540 {
1541 lowest_distance = temp_distance;
1542 current_closest = pos;
1543 }
1544 pos = pos->next;
1545 count++;
1546 }
1547 }
1548 GNUNET_assert (current_closest != NULL);
1549 return current_closest;
1550}
1551
1552
1553/**
1554 * Function called to send a request out to another peer.
1555 * Called both for locally initiated requests and those
1556 * received from other peers.
1557 *
1558 * @param msg the encapsulated message
1559 * @param peer the peer to forward the message to
1560 * @param msg_ctx the context of the message (hop count, bloom, etc.)
1561 */
1562static void
1563forward_message (const struct GNUNET_MessageHeader *msg, struct PeerInfo *peer,
1564 struct DHT_MessageContext *msg_ctx)
1565{
1566 struct GNUNET_DHT_P2PRouteMessage *route_message;
1567 struct P2PPendingMessage *pending;
1568 size_t msize;
1569 size_t psize;
1570 char *route_path;
1571
1572 increment_stats (STAT_ROUTE_FORWARDS);
1573 GNUNET_assert (peer != NULL);
1574 if ((msg_ctx->closest != GNUNET_YES) &&
1575 (peer == find_closest_peer (&msg_ctx->key)))
1576 increment_stats (STAT_ROUTE_FORWARDS_CLOSEST);
1577
1578 msize =
1579 sizeof (struct GNUNET_DHT_P2PRouteMessage) + ntohs (msg->size) +
1580 (msg_ctx->path_history_len * sizeof (struct GNUNET_PeerIdentity));
1581 GNUNET_assert (msize <= GNUNET_SERVER_MAX_MESSAGE_SIZE);
1582 psize = sizeof (struct P2PPendingMessage) + msize;
1583 pending = GNUNET_malloc (psize);
1584 pending->msg = (struct GNUNET_MessageHeader *) &pending[1];
1585 pending->importance = msg_ctx->importance;
1586 pending->timeout = msg_ctx->timeout;
1587 route_message = (struct GNUNET_DHT_P2PRouteMessage *) pending->msg;
1588 route_message->header.size = htons (msize);
1589 route_message->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ROUTE);
1590 route_message->options = htonl (msg_ctx->msg_options);
1591 route_message->hop_count = htonl (msg_ctx->hop_count + 1);
1592 route_message->network_size = htonl (msg_ctx->network_size);
1593 route_message->desired_replication_level = htonl (msg_ctx->replication);
1594#if HAVE_UID_FOR_TESTING
1595 route_message->unique_id = GNUNET_htonll (msg_ctx->unique_id);
1596#endif
1597 if (msg_ctx->bloom != NULL)
1598 GNUNET_assert (GNUNET_OK ==
1599 GNUNET_CONTAINER_bloomfilter_get_raw_data (msg_ctx->bloom,
1600 route_message->
1601 bloomfilter,
1602 DHT_BLOOM_SIZE));
1603 memcpy (&route_message->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
1604 memcpy (&route_message[1], msg, ntohs (msg->size));
1605 if (GNUNET_DHT_RO_RECORD_ROUTE ==
1606 (msg_ctx->msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
1607 {
1608 route_message->outgoing_path_length = htonl (msg_ctx->path_history_len);
1609 /* Set pointer to start of enc_msg */
1610 route_path = (char *) &route_message[1];
1611 /* Offset to the end of the enc_msg */
1612 route_path += ntohs (msg->size);
1613 /* Copy the route_path after enc_msg */
1614 memcpy (route_path, msg_ctx->path_history,
1615 msg_ctx->path_history_len * sizeof (struct GNUNET_PeerIdentity));
1616 }
1617#if DEBUG_DHT > 1
1618 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1619 "%s:%s Adding pending message size %d for peer %s\n", my_short_id,
1620 "DHT", msize, GNUNET_i2s (&peer->id));
1621#endif
1622 peer->pending_count++;
1623 increment_stats ("# pending messages scheduled");
1624 GNUNET_CONTAINER_DLL_insert_after (peer->head, peer->tail, peer->tail,
1625 pending);
1626 if (peer->send_task == GNUNET_SCHEDULER_NO_TASK)
1627 peer->send_task = GNUNET_SCHEDULER_add_now (&try_core_send, peer);
1628}
1629
1630
1631/**
1632 * Task run to check for messages that need to be sent to a client.
1633 *
1634 * @param client a ClientList, containing the client and any messages to be sent to it
1635 */
1636static void
1637process_pending_messages (struct ClientList *client)
1638{
1639 if ((client->pending_head == NULL) || (client->transmit_handle != NULL))
1640 return;
1641 client->transmit_handle =
1642 GNUNET_SERVER_notify_transmit_ready (client->client_handle,
1643 ntohs (client->pending_head->
1644 msg->size),
1645 GNUNET_TIME_UNIT_FOREVER_REL,
1646 &send_generic_reply, client);
1647}
1648
1649/**
1650 * Callback called as a result of issuing a GNUNET_SERVER_notify_transmit_ready
1651 * request. A ClientList is passed as closure, take the head of the list
1652 * and copy it into buf, which has the result of sending the message to the
1653 * client.
1654 *
1655 * @param cls closure to this call
1656 * @param size maximum number of bytes available to send
1657 * @param buf where to copy the actual message to
1658 *
1659 * @return the number of bytes actually copied, 0 indicates failure
1660 */
1661static size_t
1662send_generic_reply (void *cls, size_t size, void *buf)
1663{
1664 struct ClientList *client = cls;
1665 char *cbuf = buf;
1666 struct PendingMessage *reply;
1667 size_t off;
1668 size_t msize;
1669
1670 client->transmit_handle = NULL;
1671 if (buf == NULL)
1672 {
1673 /* client disconnected */
1674 return 0;
1675 }
1676 off = 0;
1677 while ((NULL != (reply = client->pending_head)) &&
1678 (size >= off + (msize = ntohs (reply->msg->size))))
1679 {
1680 GNUNET_CONTAINER_DLL_remove (client->pending_head, client->pending_tail,
1681 reply);
1682 memcpy (&cbuf[off], reply->msg, msize);
1683 GNUNET_free (reply);
1684 off += msize;
1685 }
1686 process_pending_messages (client);
1687#if DEBUG_DHT
1688 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1689 "Transmitted %u bytes of replies to client\n",
1690 (unsigned int) off);
1691#endif
1692 return off;
1693}
1694
1695
1696/**
1697 * Add a PendingMessage to the clients list of messages to be sent
1698 *
1699 * @param client the active client to send the message to
1700 * @param pending_message the actual message to send
1701 */
1702static void
1703add_pending_message (struct ClientList *client,
1704 struct PendingMessage *pending_message)
1705{
1706 GNUNET_CONTAINER_DLL_insert_after (client->pending_head, client->pending_tail,
1707 client->pending_tail, pending_message);
1708 process_pending_messages (client);
1709}
1710
1711
1712/**
1713 * Called when a reply needs to be sent to a client, as
1714 * a result it found to a GET or FIND PEER request.
1715 *
1716 * @param client the client to send the reply to
1717 * @param message the encapsulated message to send
1718 * @param msg_ctx the context of the received message
1719 */
1720static void
1721send_reply_to_client (struct ClientList *client,
1722 const struct GNUNET_MessageHeader *message,
1723 struct DHT_MessageContext *msg_ctx)
1724{
1725 struct GNUNET_DHT_RouteResultMessage *reply;
1726 struct PendingMessage *pending_message;
1727 uint16_t msize;
1728 size_t tsize;
1729 char *reply_offset;
1730
1731#if DEBUG_PATH
1732 char *path_offset;
1733 unsigned int i;
1734#endif
1735#if DEBUG_DHT
1736 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "`%s:%s': Sending reply to client.\n",
1737 my_short_id, "DHT");
1738#endif
1739 msize = ntohs (message->size);
1740 tsize =
1741 sizeof (struct GNUNET_DHT_RouteResultMessage) + msize +
1742 (msg_ctx->path_history_len * sizeof (struct GNUNET_PeerIdentity));
1743 if (tsize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1744 {
1745 GNUNET_break_op (0);
1746 return;
1747 }
1748 pending_message = GNUNET_malloc (sizeof (struct PendingMessage) + tsize);
1749 pending_message->msg = (struct GNUNET_MessageHeader *) &pending_message[1];
1750 reply = (struct GNUNET_DHT_RouteResultMessage *) &pending_message[1];
1751 reply->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_RESULT);
1752 reply->header.size = htons (tsize);
1753 reply->outgoing_path_length = htonl (msg_ctx->path_history_len);
1754 reply->unique_id = GNUNET_htonll (msg_ctx->unique_id);
1755 memcpy (&reply->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
1756 reply_offset = (char *) &reply[1];
1757 memcpy (&reply[1], message, msize);
1758 if (msg_ctx->path_history_len > 0)
1759 {
1760 reply_offset += msize;
1761 memcpy (reply_offset, msg_ctx->path_history,
1762 msg_ctx->path_history_len * sizeof (struct GNUNET_PeerIdentity));
1763 }
1764#if DEBUG_PATH
1765 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1766 "Returning message with outgoing path length %d\n",
1767 msg_ctx->path_history_len);
1768 for (i = 0; i < msg_ctx->path_history_len; i++)
1769 {
1770 path_offset =
1771 &msg_ctx->path_history[i * sizeof (struct GNUNET_PeerIdentity)];
1772 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Found peer %d:%s\n", i,
1773 GNUNET_i2s ((struct GNUNET_PeerIdentity *) path_offset));
1774 }
1775#endif
1776 add_pending_message (client, pending_message);
1777}
1778
1779/**
1780 * Consider whether or not we would like to have this peer added to
1781 * our routing table. Check whether bucket for this peer is full,
1782 * if so return negative; if not return positive. Since peers are
1783 * only added on CORE level connect, this doesn't actually add the
1784 * peer to the routing table.
1785 *
1786 * @param peer the peer we are considering adding
1787 *
1788 * @return GNUNET_YES if we want this peer, GNUNET_NO if not (bucket
1789 * already full)
1790 */
1791static int
1792consider_peer (struct GNUNET_PeerIdentity *peer)
1793{
1794 int bucket;
1795
1796 if ((GNUNET_YES ==
1797 GNUNET_CONTAINER_multihashmap_contains (all_known_peers,
1798 &peer->hashPubKey)) ||
1799 (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity))))
1800 return GNUNET_NO; /* We already know this peer (are connected even!) */
1801 bucket = find_current_bucket (&peer->hashPubKey);
1802
1803 if ((k_buckets[bucket].peers_size < bucket_size) ||
1804 ((bucket == lowest_bucket) && (lowest_bucket > 0)))
1805 return GNUNET_YES;
1806
1807 return GNUNET_NO;
1808}
1809
1810
1811/**
1812 * Task used to remove forwarding entries, either
1813 * after timeout, when full, or on shutdown.
1814 *
1815 * @param cls the entry to remove
1816 * @param tc context, reason, etc.
1817 */
1818static void
1819remove_forward_entry (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
1820{
1821 struct DHTRouteSource *source_info = cls;
1822 struct DHTQueryRecord *record;
1823
1824 source_info = GNUNET_CONTAINER_heap_remove_node (source_info->hnode);
1825 record = source_info->record;
1826 GNUNET_CONTAINER_DLL_remove (record->head, record->tail, source_info);
1827
1828 if (record->head == NULL) /* No more entries in DLL */
1829 {
1830 GNUNET_assert (GNUNET_YES ==
1831 GNUNET_CONTAINER_multihashmap_remove (forward_list.hashmap,
1832 &record->key, record));
1833 GNUNET_free (record);
1834 }
1835 if (source_info->find_peers_responded != NULL)
1836 GNUNET_CONTAINER_bloomfilter_free (source_info->find_peers_responded);
1837 GNUNET_free (source_info);
1838}
1839
1840/**
1841 * Main function that handles whether or not to route a result
1842 * message to other peers, or to send to our local client.
1843 *
1844 * @param msg the result message to be routed
1845 * @param msg_ctx context of the message we are routing
1846 *
1847 * @return the number of peers the message was routed to,
1848 * GNUNET_SYSERR on failure
1849 */
1850static int
1851route_result_message (struct GNUNET_MessageHeader *msg,
1852 struct DHT_MessageContext *msg_ctx)
1853{
1854 struct GNUNET_PeerIdentity new_peer;
1855 struct DHTQueryRecord *record;
1856 struct DHTRouteSource *pos;
1857 struct PeerInfo *peer_info;
1858 const struct GNUNET_MessageHeader *hello_msg;
1859
1860#if DEBUG_DHT > 1
1861 unsigned int i;
1862#endif
1863
1864 increment_stats (STAT_RESULTS);
1865 /**
1866 * If a find peer result message is received and contains a valid
1867 * HELLO for another peer, offer it to the transport service.
1868 */
1869 if (ntohs (msg->type) == GNUNET_MESSAGE_TYPE_DHT_FIND_PEER_RESULT)
1870 {
1871 if (ntohs (msg->size) <= sizeof (struct GNUNET_MessageHeader))
1872 GNUNET_break_op (0);
1873
1874 hello_msg = &msg[1];
1875 if ((ntohs (hello_msg->type) != GNUNET_MESSAGE_TYPE_HELLO) ||
1876 (GNUNET_SYSERR ==
1877 GNUNET_HELLO_get_id ((const struct GNUNET_HELLO_Message *) hello_msg,
1878 &new_peer)))
1879 {
1880 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1881 "%s:%s Received non-HELLO message type in find peer result message!\n",
1882 my_short_id, "DHT");
1883 GNUNET_break_op (0);
1884 return GNUNET_NO;
1885 }
1886 else /* We have a valid hello, and peer id stored in new_peer */
1887 {
1888 find_peer_context.count++;
1889 increment_stats (STAT_FIND_PEER_REPLY);
1890 if (GNUNET_YES == consider_peer (&new_peer))
1891 {
1892 increment_stats (STAT_HELLOS_PROVIDED);
1893 GNUNET_TRANSPORT_offer_hello (transport_handle, hello_msg, NULL, NULL);
1894 GNUNET_CORE_peer_request_connect (coreAPI, &new_peer, NULL, NULL);
1895 }
1896 }
1897 }
1898
1899 if (malicious_dropper == GNUNET_YES)
1900 record = NULL;
1901 else
1902 record =
1903 GNUNET_CONTAINER_multihashmap_get (forward_list.hashmap, &msg_ctx->key);
1904
1905 if (record == NULL) /* No record of this message! */
1906 {
1907#if DEBUG_DHT
1908 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1909 "`%s:%s': Have no record of response key %s uid %llu\n",
1910 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
1911 msg_ctx->unique_id);
1912#endif
1913#if DEBUG_DHT_ROUTING
1914 if ((debug_routes_extended) && (dhtlog_handle != NULL))
1915 {
1916 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_RESULT,
1917 msg_ctx->hop_count, GNUNET_SYSERR,
1918 &my_identity, &msg_ctx->key, &msg_ctx->peer,
1919 NULL);
1920 }
1921#endif
1922 return 0;
1923 }
1924
1925 pos = record->head;
1926 while (pos != NULL)
1927 {
1928#if STRICT_FORWARDING
1929 if (ntohs (msg->type) == GNUNET_MESSAGE_TYPE_DHT_FIND_PEER_RESULT) /* If we have already forwarded this peer id, don't do it again! */
1930 {
1931 if (GNUNET_YES ==
1932 GNUNET_CONTAINER_bloomfilter_test (pos->find_peers_responded,
1933 &new_peer.hashPubKey))
1934 {
1935 increment_stats ("# find peer responses NOT forwarded (bloom match)");
1936 pos = pos->next;
1937 continue;
1938 }
1939 else
1940 {
1941 GNUNET_CONTAINER_bloomfilter_add (pos->find_peers_responded,
1942 &new_peer.hashPubKey);
1943 }
1944 }
1945#endif
1946
1947 if (0 == memcmp (&pos->source, &my_identity, sizeof (struct GNUNET_PeerIdentity))) /* Local client (or DHT) initiated request! */
1948 {
1949#if DEBUG_DHT
1950 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1951 "`%s:%s': Sending response key %s uid %llu to client\n",
1952 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
1953 msg_ctx->unique_id);
1954#endif
1955#if DEBUG_DHT_ROUTING
1956 if ((debug_routes_extended) && (dhtlog_handle != NULL))
1957 {
1958 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_RESULT,
1959 msg_ctx->hop_count, GNUNET_YES,
1960 &my_identity, &msg_ctx->key, &msg_ctx->peer,
1961 NULL);
1962 }
1963#endif
1964 increment_stats (STAT_RESULTS_TO_CLIENT);
1965 if (ntohs (msg->type) == GNUNET_MESSAGE_TYPE_DHT_GET_RESULT)
1966 increment_stats (STAT_GET_REPLY);
1967#if DEBUG_DHT > 1
1968 for (i = 0; i < msg_ctx->path_history_len; i++)
1969 {
1970 char *path_offset;
1971
1972 path_offset =
1973 &msg_ctx->path_history[i * sizeof (struct GNUNET_PeerIdentity)];
1974 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1975 "(before client) Key %s Found peer %d:%s\n",
1976 GNUNET_h2s (&msg_ctx->key), i,
1977 GNUNET_i2s ((struct GNUNET_PeerIdentity *) path_offset));
1978 }
1979#endif
1980 send_reply_to_client (pos->client, msg, msg_ctx);
1981 }
1982 else /* Send to peer */
1983 {
1984 peer_info = find_peer_by_id (&pos->source);
1985 if (peer_info == NULL) /* Didn't find the peer in our routing table, perhaps peer disconnected! */
1986 {
1987 pos = pos->next;
1988 continue;
1989 }
1990#if DEBUG_DHT
1991 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1992 "`%s:%s': Forwarding response key %s uid %llu to peer %s\n",
1993 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
1994 msg_ctx->unique_id, GNUNET_i2s (&peer_info->id));
1995#endif
1996#if DEBUG_DHT_ROUTING
1997 if ((debug_routes_extended) && (dhtlog_handle != NULL))
1998 {
1999 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_RESULT,
2000 msg_ctx->hop_count, GNUNET_NO,
2001 &my_identity, &msg_ctx->key,
2002 &msg_ctx->peer, &pos->source);
2003 }
2004#endif
2005 forward_result_message (msg, peer_info, msg_ctx);
2006 /* Try removing forward entries after sending once, only allows ONE response per request */
2007 if (pos->delete_task != GNUNET_SCHEDULER_NO_TASK)
2008 {
2009 GNUNET_SCHEDULER_cancel (pos->delete_task);
2010 pos->delete_task =
2011 GNUNET_SCHEDULER_add_now (&remove_forward_entry, pos);
2012 }
2013 }
2014 pos = pos->next;
2015 }
2016 return 0;
2017}
2018
2019
2020/**
2021 * Iterator for local get request results,
2022 *
2023 * @param cls closure for iterator, a DatacacheGetContext
2024 * @param exp when does this value expire?
2025 * @param key the key this data is stored under
2026 * @param size the size of the data identified by key
2027 * @param data the actual data
2028 * @param type the type of the data
2029 *
2030 * @return GNUNET_OK to continue iteration, anything else
2031 * to stop iteration.
2032 */
2033static int
2034datacache_get_iterator (void *cls, struct GNUNET_TIME_Absolute exp,
2035 const GNUNET_HashCode * key, size_t size,
2036 const char *data, enum GNUNET_BLOCK_Type type)
2037{
2038 struct DHT_MessageContext *msg_ctx = cls;
2039 struct DHT_MessageContext new_msg_ctx;
2040 struct GNUNET_DHT_GetResultMessage *get_result;
2041 enum GNUNET_BLOCK_EvaluationResult eval;
2042 const struct DHTPutEntry *put_entry;
2043 int get_size;
2044 char *path_offset;
2045
2046#if DEBUG_PATH
2047 unsigned int i;
2048#endif
2049
2050#if DEBUG_DHT
2051 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2052 "`%s:%s': Received `%s' response from datacache\n", my_short_id,
2053 "DHT", "GET");
2054#endif
2055
2056 put_entry = (const struct DHTPutEntry *) data;
2057
2058 if (size !=
2059 sizeof (struct DHTPutEntry) + put_entry->data_size +
2060 (put_entry->path_length * sizeof (struct GNUNET_PeerIdentity)))
2061 {
2062 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2063 "Path + data size doesn't add up for data inserted into datacache!\nData size %d, path length %d, expected %d, got %d\n",
2064 put_entry->data_size, put_entry->path_length,
2065 sizeof (struct DHTPutEntry) + put_entry->data_size +
2066 (put_entry->path_length * sizeof (struct GNUNET_PeerIdentity)),
2067 size);
2068 msg_ctx->do_forward = GNUNET_NO;
2069 return GNUNET_OK;
2070 }
2071
2072 eval =
2073 GNUNET_BLOCK_evaluate (block_context, type, key, &msg_ctx->reply_bf,
2074 msg_ctx->reply_bf_mutator, msg_ctx->xquery,
2075 msg_ctx->xquery_size, &put_entry[1],
2076 put_entry->data_size);
2077
2078 switch (eval)
2079 {
2080 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2081 msg_ctx->do_forward = GNUNET_NO;
2082 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2083 memcpy (&new_msg_ctx, msg_ctx, sizeof (struct DHT_MessageContext));
2084 if (GNUNET_DHT_RO_RECORD_ROUTE ==
2085 (msg_ctx->msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
2086 {
2087 new_msg_ctx.msg_options = GNUNET_DHT_RO_RECORD_ROUTE;
2088#if DEBUG_PATH
2089 for (i = 0; i < new_msg_ctx.path_history_len; i++)
2090 {
2091 path_offset =
2092 &new_msg_ctx.path_history[i * sizeof (struct GNUNET_PeerIdentity)];
2093 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2094 "(get_iterator) Key %s Found peer %d:%s\n",
2095 GNUNET_h2s (&msg_ctx->key), i,
2096 GNUNET_i2s ((struct GNUNET_PeerIdentity *) path_offset));
2097 }
2098#endif
2099 }
2100
2101 get_size =
2102 sizeof (struct GNUNET_DHT_GetResultMessage) + put_entry->data_size +
2103 (put_entry->path_length * sizeof (struct GNUNET_PeerIdentity));
2104 get_result = GNUNET_malloc (get_size);
2105 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_GET_RESULT);
2106 get_result->header.size = htons (get_size);
2107 get_result->expiration = GNUNET_TIME_absolute_hton (exp);
2108 get_result->type = htons (type);
2109 get_result->put_path_length = htons (put_entry->path_length);
2110 path_offset = (char *) &put_entry[1];
2111 path_offset += put_entry->data_size;
2112#if DEBUG_PATH
2113 for (i = 0; i < put_entry->path_length; i++)
2114 {
2115 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2116 "(get_iterator PUT path) Key %s Found peer %d:%s\n",
2117 GNUNET_h2s (&msg_ctx->key), i,
2118 GNUNET_i2s ((struct GNUNET_PeerIdentity *)
2119 &path_offset[i *
2120 sizeof (struct
2121 GNUNET_PeerIdentity)]));
2122 }
2123#endif
2124 /* Copy the actual data and the path_history to the end of the get result */
2125 memcpy (&get_result[1], &put_entry[1],
2126 put_entry->data_size +
2127 (put_entry->path_length * sizeof (struct GNUNET_PeerIdentity)));
2128 new_msg_ctx.peer = my_identity;
2129 new_msg_ctx.bloom = NULL;
2130 new_msg_ctx.hop_count = 0;
2131 new_msg_ctx.importance = DHT_DEFAULT_P2P_IMPORTANCE + 2; /* Make result routing a higher priority */
2132 new_msg_ctx.timeout = DHT_DEFAULT_P2P_TIMEOUT;
2133 increment_stats (STAT_GET_RESPONSE_START);
2134 route_result_message (&get_result->header, &new_msg_ctx);
2135 GNUNET_free (get_result);
2136 break;
2137 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2138#if DEBUG_DHT
2139 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "`%s:%s': Duplicate block error\n",
2140 my_short_id, "DHT");
2141#endif
2142 break;
2143 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2144#if DEBUG_DHT
2145 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "`%s:%s': Invalid request error\n",
2146 my_short_id, "DHT");
2147#endif
2148 break;
2149 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2150#if DEBUG_DHT
2151 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2152 "`%s:%s': Valid request, no results.\n", my_short_id, "DHT");
2153#endif
2154 GNUNET_break (0);
2155 break;
2156 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2157 GNUNET_break_op (0);
2158 msg_ctx->do_forward = GNUNET_NO;
2159 break;
2160 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2161#if DEBUG_DHT
2162 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2163 "`%s:%s': Unsupported block type (%u) in response!\n",
2164 my_short_id, "DHT", type);
2165#endif
2166 /* msg_ctx->do_forward = GNUNET_NO; // not sure... */
2167 break;
2168 }
2169 return GNUNET_OK;
2170}
2171
2172
2173/**
2174 * Main function that handles whether or not to route a message to other
2175 * peers.
2176 *
2177 * @param msg the message to be routed
2178 * @param msg_ctx the context containing all pertinent information about the message
2179 */
2180static void
2181route_message (const struct GNUNET_MessageHeader *msg,
2182 struct DHT_MessageContext *msg_ctx);
2183
2184
2185/**
2186 * Server handler for all dht get requests, look for data,
2187 * if found, send response either to clients or other peers.
2188 *
2189 * @param msg the actual get message
2190 * @param msg_ctx struct containing pertinent information about the get request
2191 *
2192 * @return number of items found for GET request
2193 */
2194static unsigned int
2195handle_dht_get (const struct GNUNET_MessageHeader *msg,
2196 struct DHT_MessageContext *msg_ctx)
2197{
2198 const struct GNUNET_DHT_GetMessage *get_msg;
2199 uint16_t msize;
2200 uint16_t bf_size;
2201 unsigned int results;
2202 const char *end;
2203 enum GNUNET_BLOCK_Type type;
2204
2205 msize = ntohs (msg->size);
2206 if (msize < sizeof (struct GNUNET_DHT_GetMessage))
2207 {
2208 GNUNET_break (0);
2209 return 0;
2210 }
2211 get_msg = (const struct GNUNET_DHT_GetMessage *) msg;
2212 bf_size = ntohs (get_msg->bf_size);
2213 msg_ctx->xquery_size = ntohs (get_msg->xquery_size);
2214 msg_ctx->reply_bf_mutator = get_msg->bf_mutator;
2215 if (msize !=
2216 sizeof (struct GNUNET_DHT_GetMessage) + bf_size + msg_ctx->xquery_size)
2217 {
2218 GNUNET_break_op (0);
2219 return 0;
2220 }
2221 end = (const char *) &get_msg[1];
2222 if (msg_ctx->xquery_size == 0)
2223 {
2224 msg_ctx->xquery = NULL;
2225 }
2226 else
2227 {
2228 msg_ctx->xquery = (const void *) end;
2229 end += msg_ctx->xquery_size;
2230 }
2231 if (bf_size == 0)
2232 {
2233 msg_ctx->reply_bf = NULL;
2234 }
2235 else
2236 {
2237 msg_ctx->reply_bf =
2238 GNUNET_CONTAINER_bloomfilter_init (end, bf_size,
2239 GNUNET_DHT_GET_BLOOMFILTER_K);
2240 }
2241 type = (enum GNUNET_BLOCK_Type) ntohl (get_msg->type);
2242#if DEBUG_DHT
2243 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2244 "`%s:%s': Received `%s' request, message type %u, key %s, uid %llu\n",
2245 my_short_id, "DHT", "GET", type, GNUNET_h2s (&msg_ctx->key),
2246 msg_ctx->unique_id);
2247#endif
2248 increment_stats (STAT_GETS);
2249 results = 0;
2250#if HAVE_MALICIOUS
2251 if (type == GNUNET_BLOCK_DHT_MALICIOUS_MESSAGE_TYPE)
2252 {
2253 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->reply_bf);
2254 return results;
2255 }
2256#endif
2257 msg_ctx->do_forward = GNUNET_YES;
2258 if (datacache != NULL)
2259 results =
2260 GNUNET_DATACACHE_get (datacache, &msg_ctx->key, type,
2261 &datacache_get_iterator, msg_ctx);
2262#if DEBUG_DHT
2263 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2264 "`%s:%s': Found %d results for `%s' request uid %llu\n",
2265 my_short_id, "DHT", results, "GET", msg_ctx->unique_id);
2266#endif
2267 if (results >= 1)
2268 {
2269#if DEBUG_DHT_ROUTING
2270 if ((debug_routes) && (dhtlog_handle != NULL))
2271 {
2272 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_GET,
2273 msg_ctx->hop_count, GNUNET_YES, &my_identity,
2274 &msg_ctx->key);
2275 }
2276
2277 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2278 {
2279 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
2280 msg_ctx->hop_count, GNUNET_YES, &my_identity,
2281 &msg_ctx->key, &msg_ctx->peer, NULL);
2282 }
2283#endif
2284 }
2285 else
2286 {
2287 /* check query valid */
2288 if (GNUNET_BLOCK_EVALUATION_REQUEST_INVALID ==
2289 GNUNET_BLOCK_evaluate (block_context, type, &msg_ctx->key,
2290 &msg_ctx->reply_bf, msg_ctx->reply_bf_mutator,
2291 msg_ctx->xquery, msg_ctx->xquery_size, NULL, 0))
2292 {
2293 GNUNET_break_op (0);
2294 msg_ctx->do_forward = GNUNET_NO;
2295 }
2296 }
2297
2298 if (msg_ctx->hop_count == 0) /* Locally initiated request */
2299 {
2300#if DEBUG_DHT_ROUTING
2301 if ((debug_routes) && (dhtlog_handle != NULL))
2302 {
2303 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_GET,
2304 msg_ctx->hop_count, GNUNET_NO, &my_identity,
2305 &msg_ctx->key);
2306 }
2307#endif
2308 }
2309 if (msg_ctx->do_forward == GNUNET_YES)
2310 route_message (msg, msg_ctx);
2311 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->reply_bf);
2312 return results;
2313}
2314
2315
2316static void
2317remove_recent_find_peer (void *cls,
2318 const struct GNUNET_SCHEDULER_TaskContext *tc)
2319{
2320 GNUNET_HashCode *key = cls;
2321
2322 GNUNET_assert (GNUNET_YES ==
2323 GNUNET_CONTAINER_multihashmap_remove
2324 (recent_find_peer_requests, key, NULL));
2325 GNUNET_free (key);
2326}
2327
2328
2329/**
2330 * Server handler for initiating local dht find peer requests
2331 *
2332 * @param find_msg the actual find peer message
2333 * @param msg_ctx struct containing pertinent information about the request
2334 *
2335 */
2336static void
2337handle_dht_find_peer (const struct GNUNET_MessageHeader *find_msg,
2338 struct DHT_MessageContext *msg_ctx)
2339{
2340 struct GNUNET_MessageHeader *find_peer_result;
2341 struct GNUNET_DHT_FindPeerMessage *find_peer_message;
2342 struct DHT_MessageContext *new_msg_ctx;
2343 struct GNUNET_CONTAINER_BloomFilter *incoming_bloom;
2344 size_t hello_size;
2345 size_t tsize;
2346 GNUNET_HashCode *recent_hash;
2347 struct GNUNET_MessageHeader *other_hello;
2348 size_t other_hello_size;
2349 struct GNUNET_PeerIdentity peer_id;
2350
2351 find_peer_message = (struct GNUNET_DHT_FindPeerMessage *) find_msg;
2352 GNUNET_break_op (ntohs (find_msg->size) >=
2353 (sizeof (struct GNUNET_DHT_FindPeerMessage)));
2354 if (ntohs (find_msg->size) < sizeof (struct GNUNET_DHT_FindPeerMessage))
2355 return;
2356 other_hello = NULL;
2357 other_hello_size = 0;
2358 if (ntohs (find_msg->size) > sizeof (struct GNUNET_DHT_FindPeerMessage))
2359 {
2360 other_hello_size =
2361 ntohs (find_msg->size) - sizeof (struct GNUNET_DHT_FindPeerMessage);
2362 other_hello = GNUNET_malloc (other_hello_size);
2363 memcpy (other_hello, &find_peer_message[1], other_hello_size);
2364 if ((GNUNET_HELLO_size ((struct GNUNET_HELLO_Message *) other_hello) == 0)
2365 || (GNUNET_OK !=
2366 GNUNET_HELLO_get_id ((struct GNUNET_HELLO_Message *) other_hello,
2367 &peer_id)))
2368 {
2369 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2370 "Received invalid HELLO message in find peer request!\n");
2371 GNUNET_free (other_hello);
2372 return;
2373 }
2374#if FIND_PEER_WITH_HELLO
2375 if (GNUNET_YES == consider_peer (&peer_id))
2376 {
2377 increment_stats (STAT_HELLOS_PROVIDED);
2378 GNUNET_TRANSPORT_offer_hello (transport_handle, other_hello, NULL, NULL);
2379 GNUNET_CORE_peer_request_connect (coreAPI, &peer_id, NULL, NULL);
2380 route_message (find_msg, msg_ctx);
2381 GNUNET_free (other_hello);
2382 return;
2383 }
2384 else /* We don't want this peer! */
2385 {
2386 route_message (find_msg, msg_ctx);
2387 GNUNET_free (other_hello);
2388 return;
2389 }
2390#endif
2391 }
2392
2393#if DEBUG_DHT
2394 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2395 "`%s:%s': Received `%s' request from client, key %s (msg size %d, we expected %d)\n",
2396 my_short_id, "DHT", "FIND PEER", GNUNET_h2s (&msg_ctx->key),
2397 ntohs (find_msg->size), sizeof (struct GNUNET_MessageHeader));
2398#endif
2399 if (my_hello == NULL)
2400 {
2401#if DEBUG_DHT
2402 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2403 "`%s': Our HELLO is null, can't return.\n", "DHT");
2404#endif
2405 GNUNET_free_non_null (other_hello);
2406 route_message (find_msg, msg_ctx);
2407 return;
2408 }
2409
2410 incoming_bloom =
2411 GNUNET_CONTAINER_bloomfilter_init (find_peer_message->bloomfilter,
2412 DHT_BLOOM_SIZE, DHT_BLOOM_K);
2413 if (GNUNET_YES ==
2414 GNUNET_CONTAINER_bloomfilter_test (incoming_bloom,
2415 &my_identity.hashPubKey))
2416 {
2417 increment_stats (STAT_BLOOM_FIND_PEER);
2418 GNUNET_CONTAINER_bloomfilter_free (incoming_bloom);
2419 GNUNET_free_non_null (other_hello);
2420 route_message (find_msg, msg_ctx);
2421 return; /* We match the bloomfilter, do not send a response to this peer (they likely already know us!) */
2422 }
2423 GNUNET_CONTAINER_bloomfilter_free (incoming_bloom);
2424
2425#if RESTRICT_FIND_PEER
2426
2427 /**
2428 * Ignore any find peer requests from a peer we have seen very recently.
2429 */
2430 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! */
2431 {
2432 increment_stats ("# dht find peer requests ignored (recently seen!)");
2433 GNUNET_free_non_null (other_hello);
2434 return;
2435 }
2436
2437 /**
2438 * Use this check to only allow the peer to respond to find peer requests if
2439 * it would be beneficial to have the requesting peer in this peers routing
2440 * table. Can be used to thwart peers flooding the network with find peer
2441 * requests that we don't care about. However, if a new peer is joining
2442 * the network and has no other peers this is a problem (assume all buckets
2443 * full, no one will respond!).
2444 */
2445 memcpy (&peer_id.hashPubKey, &msg_ctx->key, sizeof (GNUNET_HashCode));
2446 if (GNUNET_NO == consider_peer (&peer_id))
2447 {
2448 increment_stats ("# dht find peer requests ignored (do not need!)");
2449 GNUNET_free_non_null (other_hello);
2450 route_message (find_msg, msg_ctx);
2451 return;
2452 }
2453#endif
2454
2455 recent_hash = GNUNET_malloc (sizeof (GNUNET_HashCode));
2456 memcpy (recent_hash, &msg_ctx->key, sizeof (GNUNET_HashCode));
2457 if (GNUNET_SYSERR !=
2458 GNUNET_CONTAINER_multihashmap_put (recent_find_peer_requests,
2459 &msg_ctx->key, NULL,
2460 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
2461 {
2462#if DEBUG_DHT
2463 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2464 "Adding recent remove task for key `%s`!\n",
2465 GNUNET_h2s (&msg_ctx->key));
2466#endif
2467 /* Only add a task if there wasn't one for this key already! */
2468 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_relative_multiply
2469 (GNUNET_TIME_UNIT_SECONDS, 30),
2470 &remove_recent_find_peer, recent_hash);
2471 }
2472 else
2473 {
2474 GNUNET_free (recent_hash);
2475#if DEBUG_DHT
2476 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2477 "Received duplicate find peer request too soon!\n");
2478#endif
2479 }
2480
2481 /* Simplistic find_peer functionality, always return our hello */
2482 hello_size = ntohs (my_hello->size);
2483 tsize = hello_size + sizeof (struct GNUNET_MessageHeader);
2484
2485 if (tsize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2486 {
2487 GNUNET_break_op (0);
2488 GNUNET_free_non_null (other_hello);
2489 return;
2490 }
2491
2492 find_peer_result = GNUNET_malloc (tsize);
2493 find_peer_result->type = htons (GNUNET_MESSAGE_TYPE_DHT_FIND_PEER_RESULT);
2494 find_peer_result->size = htons (tsize);
2495 memcpy (&find_peer_result[1], my_hello, hello_size);
2496#if DEBUG_DHT
2497 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2498 "`%s': Sending hello size %d to requesting peer.\n", "DHT",
2499 hello_size);
2500#endif
2501
2502 new_msg_ctx = GNUNET_malloc (sizeof (struct DHT_MessageContext));
2503 memcpy (new_msg_ctx, msg_ctx, sizeof (struct DHT_MessageContext));
2504 new_msg_ctx->peer = my_identity;
2505 new_msg_ctx->bloom =
2506 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
2507 new_msg_ctx->hop_count = 0;
2508 new_msg_ctx->importance = DHT_DEFAULT_P2P_IMPORTANCE + 2; /* Make find peer requests a higher priority */
2509 new_msg_ctx->timeout = DHT_DEFAULT_P2P_TIMEOUT;
2510 increment_stats (STAT_FIND_PEER_ANSWER);
2511 if (GNUNET_DHT_RO_RECORD_ROUTE ==
2512 (msg_ctx->msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
2513 {
2514 new_msg_ctx->msg_options = GNUNET_DHT_RO_RECORD_ROUTE;
2515 new_msg_ctx->path_history_len = msg_ctx->path_history_len;
2516 /* Assign to previous msg_ctx path history, caller should free after our return */
2517 new_msg_ctx->path_history = msg_ctx->path_history;
2518 }
2519 route_result_message (find_peer_result, new_msg_ctx);
2520 GNUNET_free (new_msg_ctx);
2521#if DEBUG_DHT_ROUTING
2522 if ((debug_routes) && (dhtlog_handle != NULL))
2523 {
2524 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_FIND_PEER,
2525 msg_ctx->hop_count, GNUNET_YES, &my_identity,
2526 &msg_ctx->key);
2527 }
2528#endif
2529 GNUNET_free_non_null (other_hello);
2530 GNUNET_free (find_peer_result);
2531 route_message (find_msg, msg_ctx);
2532}
2533
2534
2535/**
2536 * Server handler for initiating local dht put requests
2537 *
2538 * @param msg the actual put message
2539 * @param msg_ctx struct containing pertinent information about the request
2540 */
2541static void
2542handle_dht_put (const struct GNUNET_MessageHeader *msg,
2543 struct DHT_MessageContext *msg_ctx)
2544{
2545 const struct GNUNET_DHT_PutMessage *put_msg;
2546 struct DHTPutEntry *put_entry;
2547 unsigned int put_size;
2548 char *path_offset;
2549 enum GNUNET_BLOCK_Type put_type;
2550 size_t data_size;
2551 int ret;
2552 GNUNET_HashCode key;
2553 struct DHTQueryRecord *record;
2554
2555 GNUNET_assert (ntohs (msg->size) >= sizeof (struct GNUNET_DHT_PutMessage));
2556
2557 put_msg = (const struct GNUNET_DHT_PutMessage *) msg;
2558 put_type = (enum GNUNET_BLOCK_Type) ntohl (put_msg->type);
2559#if HAVE_MALICIOUS
2560 if (put_type == GNUNET_BLOCK_DHT_MALICIOUS_MESSAGE_TYPE)
2561 {
2562#if DEBUG_DHT_ROUTING
2563 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2564 {
2565 /** Log routes that die due to high load! */
2566 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
2567 msg_ctx->hop_count, GNUNET_SYSERR,
2568 &my_identity, &msg_ctx->key, &msg_ctx->peer,
2569 NULL);
2570 }
2571#endif
2572 return;
2573 }
2574#endif
2575 data_size =
2576 ntohs (put_msg->header.size) - sizeof (struct GNUNET_DHT_PutMessage);
2577 ret =
2578 GNUNET_BLOCK_get_key (block_context, put_type, &put_msg[1], data_size,
2579 &key);
2580 if (GNUNET_NO == ret)
2581 {
2582#if DEBUG_DHT_ROUTING
2583 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2584 {
2585 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
2586 msg_ctx->hop_count, GNUNET_SYSERR,
2587 &my_identity, &msg_ctx->key, &msg_ctx->peer,
2588 NULL);
2589 }
2590#endif
2591 /* invalid reply */
2592 GNUNET_break_op (0);
2593 return;
2594 }
2595 if ((GNUNET_YES == ret) &&
2596 (0 != memcmp (&key, &msg_ctx->key, sizeof (GNUNET_HashCode))))
2597 {
2598#if DEBUG_DHT_ROUTING
2599 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2600 {
2601 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
2602 msg_ctx->hop_count, GNUNET_SYSERR,
2603 &my_identity, &msg_ctx->key, &msg_ctx->peer,
2604 NULL);
2605 }
2606#endif
2607 /* invalid wrapper: key mismatch! */
2608 GNUNET_break_op (0);
2609 return;
2610 }
2611 /* ret == GNUNET_SYSERR means that there is no known relationship between
2612 * data and the key, so we cannot check it */
2613#if DEBUG_DHT
2614 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2615 "`%s:%s': Received `%s' request (inserting data!), message type %d, key %s, uid %llu\n",
2616 my_short_id, "DHT", "PUT", put_type, GNUNET_h2s (&msg_ctx->key),
2617 msg_ctx->unique_id);
2618#endif
2619#if DEBUG_DHT_ROUTING
2620 if (msg_ctx->hop_count == 0) /* Locally initiated request */
2621 {
2622 if ((debug_routes) && (dhtlog_handle != NULL))
2623 {
2624 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_PUT,
2625 msg_ctx->hop_count, GNUNET_NO, &my_identity,
2626 &msg_ctx->key);
2627 }
2628 }
2629#endif
2630
2631 record = GNUNET_CONTAINER_multihashmap_get(forward_list.hashmap,
2632 &msg_ctx->key);
2633 if (NULL != record)
2634 {
2635 struct DHTRouteSource *pos;
2636 struct GNUNET_DHT_GetResultMessage *get_result;
2637 struct DHT_MessageContext new_msg_ctx;
2638 size_t get_size;
2639
2640 pos = record->head;
2641 while (pos != NULL)
2642 {
2643 /* TODO: do only for local started requests? or also for remote peers? */
2644 /* TODO: include this in statistics? under what? */
2645 /* TODO: reverse order of path_history? */
2646 if (NULL == pos->client)
2647 {
2648 pos = pos->next;
2649 continue;
2650 }
2651
2652 memcpy (&new_msg_ctx, msg_ctx, sizeof (struct DHT_MessageContext));
2653 if (GNUNET_DHT_RO_RECORD_ROUTE ==
2654 (msg_ctx->msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
2655 {
2656 new_msg_ctx.msg_options = GNUNET_DHT_RO_RECORD_ROUTE;
2657#if DEBUG_PATH
2658 for (i = 0; i < new_msg_ctx.path_history_len; i++)
2659 {
2660 path_offset =
2661 &new_msg_ctx.path_history[i * sizeof (struct GNUNET_PeerIdentity)];
2662 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2663 "(put for active get) Key %s Found peer %d:%s\n",
2664 GNUNET_h2s (&msg_ctx->key), i,
2665 GNUNET_i2s ((struct GNUNET_PeerIdentity *) path_offset));
2666 }
2667#endif
2668 }
2669
2670 get_size =
2671 sizeof (struct GNUNET_DHT_GetResultMessage) + data_size +
2672 (msg_ctx->path_history_len * sizeof (struct GNUNET_PeerIdentity));
2673 get_result = GNUNET_malloc (get_size);
2674 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_GET_RESULT);
2675 get_result->header.size = htons (get_size);
2676 get_result->expiration = put_msg->expiration;
2677 get_result->type = put_msg->type;
2678 get_result->put_path_length = htons (msg_ctx->path_history_len);
2679
2680 /* Copy the actual data and the path_history to the end of the get result */
2681 memcpy (&get_result[1], &put_msg[1], data_size);
2682 path_offset = (char *) &get_result[1];
2683 path_offset += data_size;
2684 memcpy (path_offset, msg_ctx->path_history,
2685 msg_ctx->path_history_len * sizeof (struct GNUNET_PeerIdentity));
2686 new_msg_ctx.peer = my_identity;
2687 new_msg_ctx.bloom = NULL;
2688 new_msg_ctx.hop_count = 0;
2689 /* Make result routing a higher priority */
2690 new_msg_ctx.importance = DHT_DEFAULT_P2P_IMPORTANCE + 2;
2691 new_msg_ctx.timeout = DHT_DEFAULT_P2P_TIMEOUT;
2692 new_msg_ctx.unique_id = pos->uid;
2693 send_reply_to_client(pos->client, &get_result->header, &new_msg_ctx);
2694 GNUNET_free (get_result);
2695 pos = pos->next;
2696 }
2697 }
2698
2699 if (msg_ctx->closest != GNUNET_YES)
2700 {
2701 route_message (msg, msg_ctx);
2702 return;
2703 }
2704
2705#if DEBUG_DHT
2706 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2707 "`%s:%s': Received `%s' request (inserting data!), message type %d, key %s, uid %llu\n",
2708 my_short_id, "DHT", "PUT", put_type, GNUNET_h2s (&msg_ctx->key),
2709 msg_ctx->unique_id);
2710#endif
2711
2712#if DEBUG_DHT_ROUTING
2713 if ((debug_routes_extended) && (dhtlog_handle != NULL))
2714 {
2715 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
2716 msg_ctx->hop_count, GNUNET_YES, &my_identity,
2717 &msg_ctx->key, &msg_ctx->peer, NULL);
2718 }
2719
2720 if ((debug_routes) && (dhtlog_handle != NULL))
2721 {
2722 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_PUT,
2723 msg_ctx->hop_count, GNUNET_YES, &my_identity,
2724 &msg_ctx->key);
2725 }
2726#endif
2727
2728 increment_stats (STAT_PUTS_INSERTED);
2729 if (datacache != NULL)
2730 {
2731 /* Put size is actual data size plus struct overhead plus path length (if any) */
2732 put_size =
2733 data_size + sizeof (struct DHTPutEntry) +
2734 (msg_ctx->path_history_len * sizeof (struct GNUNET_PeerIdentity));
2735 put_entry = GNUNET_malloc (put_size);
2736 put_entry->data_size = data_size;
2737 put_entry->path_length = msg_ctx->path_history_len;
2738 /* Copy data to end of put entry */
2739 memcpy (&put_entry[1], &put_msg[1], data_size);
2740 if (msg_ctx->path_history_len > 0)
2741 {
2742 /* Copy path after data */
2743 path_offset = (char *) &put_entry[1];
2744 path_offset += data_size;
2745 memcpy (path_offset, msg_ctx->path_history,
2746 msg_ctx->path_history_len * sizeof (struct GNUNET_PeerIdentity));
2747 }
2748
2749 ret =
2750 GNUNET_DATACACHE_put (datacache, &msg_ctx->key, put_size,
2751 (const char *) put_entry, put_type,
2752 GNUNET_TIME_absolute_ntoh (put_msg->expiration));
2753 GNUNET_free (put_entry);
2754 }
2755 else
2756 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2757 "`%s:%s': %s request received, but have no datacache!\n",
2758 my_short_id, "DHT", "PUT");
2759
2760 if (stop_on_closest == GNUNET_NO)
2761 route_message (msg, msg_ctx);
2762}
2763
2764
2765/**
2766 * To how many peers should we (on average)
2767 * forward the request to obtain the desired
2768 * target_replication count (on average).
2769 *
2770 * returns: target_replication / (est. hops) + (target_replication * hop_count)
2771 * where est. hops is typically 2 * the routing table depth
2772 *
2773 * @param hop_count number of hops the message has traversed
2774 * @param target_replication the number of total paths desired
2775 *
2776 * @return Some number of peers to forward the message to
2777 */
2778static unsigned int
2779get_forward_count (unsigned int hop_count, size_t target_replication)
2780{
2781 uint32_t random_value;
2782 unsigned int forward_count;
2783 float target_value;
2784
2785 /**
2786 * If we are behaving in strict kademlia mode, send multiple initial requests,
2787 * but then only send to 1 or 0 peers based strictly on the number of hops.
2788 */
2789 if (strict_kademlia == GNUNET_YES)
2790 {
2791 if (hop_count == 0)
2792 return kademlia_replication;
2793 if (hop_count < log_of_network_size_estimate * 2.0)
2794 return 1;
2795 return 0;
2796 }
2797
2798 if (hop_count > log_of_network_size_estimate * 2.0)
2799 {
2800 if (GNUNET_YES == paper_forwarding)
2801 {
2802 /* Once we have reached our ideal number of hops, don't stop forwarding! */
2803 return 1;
2804 }
2805#if DEBUG_DHT
2806 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2807 "Hop count too high (est %f, lowest %d), NOT Forwarding request\n",
2808 log_of_network_size_estimate * 2.0, lowest_bucket);
2809#endif
2810 return 0;
2811 }
2812
2813 if (GNUNET_YES == paper_forwarding)
2814 {
2815 /* FIXME: re-run replication trials with this formula */
2816 target_value =
2817 1 + (target_replication - 1.0) / (log_of_network_size_estimate +
2818 ((float) (target_replication - 1.0) *
2819 hop_count));
2820 /* Set forward count to floor of target_value */
2821 forward_count = (unsigned int) target_value;
2822 /* Subtract forward_count (floor) from target_value (yields value between 0 and 1) */
2823 target_value = target_value - forward_count;
2824 random_value =
2825 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_STRONG, UINT32_MAX);
2826
2827 if (random_value < (target_value * UINT32_MAX))
2828 forward_count += 1;
2829 }
2830 else
2831 {
2832 random_value = 0;
2833 forward_count = 1;
2834 target_value =
2835 target_replication / (log_of_network_size_estimate +
2836 ((float) target_replication * hop_count));
2837 if (target_value > 1)
2838 {
2839 /* Set forward count to floor of target_value */
2840 forward_count = (unsigned int) target_value;
2841 /* Subtract forward_count (floor) from target_value (yields value between 0 and 1) */
2842 target_value = target_value - forward_count;
2843 }
2844 else
2845 random_value =
2846 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_STRONG, UINT32_MAX);
2847
2848 if (random_value < (target_value * UINT32_MAX))
2849 forward_count += 1;
2850 }
2851
2852 return forward_count;
2853}
2854
2855
2856/**
2857 * Check whether my identity is closer than any known peers.
2858 * If a non-null bloomfilter is given, check if this is the closest
2859 * peer that hasn't already been routed to.
2860 *
2861 * @param target hash code to check closeness to
2862 * @param bloom bloomfilter, exclude these entries from the decision
2863 * @return GNUNET_YES if node location is closest,
2864 * GNUNET_NO otherwise.
2865 */
2866static int
2867am_closest_peer (const GNUNET_HashCode * target,
2868 struct GNUNET_CONTAINER_BloomFilter *bloom)
2869{
2870 int bits;
2871 int other_bits;
2872 int bucket_num;
2873 int count;
2874 struct PeerInfo *pos;
2875 unsigned int my_distance;
2876
2877 if (0 == memcmp (&my_identity.hashPubKey, target, sizeof (GNUNET_HashCode)))
2878 return GNUNET_YES;
2879
2880 bucket_num = find_current_bucket (target);
2881
2882 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey, target);
2883 my_distance = distance (&my_identity.hashPubKey, target);
2884 pos = k_buckets[bucket_num].head;
2885 count = 0;
2886 while ((pos != NULL) && (count < bucket_size))
2887 {
2888 if ((bloom != NULL) &&
2889 (GNUNET_YES ==
2890 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey)))
2891 {
2892 pos = pos->next;
2893 continue; /* Skip already checked entries */
2894 }
2895
2896 other_bits = GNUNET_CRYPTO_hash_matching_bits (&pos->id.hashPubKey, target);
2897 if (other_bits > bits)
2898 return GNUNET_NO;
2899 else if (other_bits == bits) /* We match the same number of bits */
2900 {
2901 if (strict_kademlia != GNUNET_YES) /* Return that we at as close as any other peer */
2902 return GNUNET_YES;
2903 if (distance (&pos->id.hashPubKey, target) < my_distance) /* Check all known peers, only return if we are the true closest */
2904 return GNUNET_NO;
2905 }
2906 pos = pos->next;
2907 }
2908
2909 /* No peers closer, we are the closest! */
2910 return GNUNET_YES;
2911}
2912
2913
2914/**
2915 * Select a peer from the routing table that would be a good routing
2916 * destination for sending a message for "target". The resulting peer
2917 * must not be in the set of blocked peers.<p>
2918 *
2919 * Note that we should not ALWAYS select the closest peer to the
2920 * target, peers further away from the target should be chosen with
2921 * exponentially declining probability.
2922 *
2923 * @param target the key we are selecting a peer to route to
2924 * @param bloom a bloomfilter containing entries this request has seen already
2925 * @param hops how many hops has this message traversed thus far
2926 *
2927 * @return Peer to route to, or NULL on error
2928 */
2929static struct PeerInfo *
2930select_peer (const GNUNET_HashCode * target,
2931 struct GNUNET_CONTAINER_BloomFilter *bloom, unsigned int hops)
2932{
2933 unsigned int bc;
2934 unsigned int count;
2935 unsigned int selected;
2936 struct PeerInfo *pos;
2937 unsigned int distance;
2938 unsigned int largest_distance;
2939 struct PeerInfo *chosen;
2940
2941 /** If we are doing kademlia routing (saves some cycles) */
2942 if ((strict_kademlia == GNUNET_YES) || (hops >= log_of_network_size_estimate))
2943 {
2944 /* greedy selection (closest peer that is not in bloomfilter) */
2945 largest_distance = 0;
2946 chosen = NULL;
2947 for (bc = lowest_bucket; bc < MAX_BUCKETS; bc++)
2948 {
2949 pos = k_buckets[bc].head;
2950 count = 0;
2951 while ((pos != NULL) && (count < bucket_size))
2952 {
2953 /* If we are doing strict Kademlia routing, then checking the bloomfilter is basically cheating! */
2954 if (GNUNET_NO ==
2955 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))
2956 {
2957 distance = inverse_distance (target, &pos->id.hashPubKey);
2958 if (distance > largest_distance)
2959 {
2960 chosen = pos;
2961 largest_distance = distance;
2962 }
2963 }
2964 count++;
2965 pos = pos->next;
2966 }
2967 }
2968 if ((largest_distance > 0) && (chosen != NULL))
2969 {
2970 GNUNET_CONTAINER_bloomfilter_add (bloom, &chosen->id.hashPubKey);
2971 return chosen;
2972 }
2973 return NULL; /* no peer available or we are the closest */
2974 }
2975
2976
2977 /* select "random" peer */
2978 /* count number of peers that are available and not filtered */
2979 count = 0;
2980 for (bc = lowest_bucket; bc < MAX_BUCKETS; bc++)
2981 {
2982 pos = k_buckets[bc].head;
2983 while ((pos != NULL) && (count < bucket_size))
2984 {
2985 if (GNUNET_YES ==
2986 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))
2987 {
2988 pos = pos->next;
2989 increment_stats ("# peer blocked from selection by Bloom filter");
2990 continue; /* Ignore bloomfiltered peers */
2991 }
2992 count++;
2993 pos = pos->next;
2994 }
2995 }
2996 if (count == 0) /* No peers to select from! */
2997 {
2998 increment_stats ("# failed to select peer");
2999 return NULL;
3000 }
3001 /* Now actually choose a peer */
3002 selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, count);
3003 count = 0;
3004 for (bc = lowest_bucket; bc < MAX_BUCKETS; bc++)
3005 {
3006 pos = k_buckets[bc].head;
3007 while ((pos != NULL) && (count < bucket_size))
3008 {
3009 if (GNUNET_YES ==
3010 GNUNET_CONTAINER_bloomfilter_test (bloom, &pos->id.hashPubKey))
3011 {
3012 pos = pos->next;
3013 continue; /* Ignore bloomfiltered peers */
3014 }
3015 if (0 == selected--)
3016 return pos;
3017 pos = pos->next;
3018 }
3019 }
3020 GNUNET_break (0);
3021 return NULL;
3022}
3023
3024
3025/**
3026 * Task used to remove recent entries, either
3027 * after timeout, when full, or on shutdown.
3028 *
3029 * @param cls the entry to remove
3030 * @param tc context, reason, etc.
3031 */
3032static void
3033remove_recent (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
3034{
3035 struct RecentRequest *req = cls;
3036 static GNUNET_HashCode hash;
3037
3038 GNUNET_assert (req != NULL);
3039 hash_from_uid (req->uid, &hash);
3040#if HAVE_UID_FOR_TESTING > 1
3041 GNUNET_assert (GNUNET_YES ==
3042 GNUNET_CONTAINER_multihashmap_remove (recent.hashmap, &hash,
3043 req));
3044#endif
3045 GNUNET_CONTAINER_heap_remove_node (req->heap_node);
3046 GNUNET_CONTAINER_bloomfilter_free (req->bloom);
3047 GNUNET_free (req);
3048
3049 /*
3050 * if ( (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0) && (0 == GNUNET_CONTAINER_multihashmap_size(recent.hashmap)) && (0 == GNUNET_CONTAINER_heap_get_size(recent.minHeap)))
3051 * {
3052 * GNUNET_CONTAINER_multihashmap_destroy(recent.hashmap);
3053 * GNUNET_CONTAINER_heap_destroy(recent.minHeap);
3054 * }
3055 */
3056}
3057
3058/**
3059 * Remember this routing request so that if a reply is
3060 * received we can either forward it to the correct peer
3061 * or return the result locally.
3062 *
3063 * @param msg_ctx Context of the route request
3064 *
3065 * @return GNUNET_YES if this response was cached, GNUNET_NO if not
3066 */
3067static int
3068cache_response (struct DHT_MessageContext *msg_ctx)
3069{
3070 struct DHTQueryRecord *record;
3071 struct DHTRouteSource *source_info;
3072 struct DHTRouteSource *pos;
3073 struct GNUNET_TIME_Absolute now;
3074 unsigned int current_size;
3075
3076 current_size = GNUNET_CONTAINER_multihashmap_size (forward_list.hashmap);
3077
3078#if DELETE_WHEN_FULL
3079 while (current_size >= MAX_OUTSTANDING_FORWARDS)
3080 {
3081 source_info = GNUNET_CONTAINER_heap_remove_root (forward_list.minHeap);
3082 GNUNET_assert (source_info != NULL);
3083 record = source_info->record;
3084 GNUNET_CONTAINER_DLL_remove (record->head, record->tail, source_info);
3085 if (record->head == NULL) /* No more entries in DLL */
3086 {
3087 GNUNET_assert (GNUNET_YES ==
3088 GNUNET_CONTAINER_multihashmap_remove (forward_list.hashmap,
3089 &record->key,
3090 record));
3091 GNUNET_free (record);
3092 }
3093 if (source_info->delete_task != GNUNET_SCHEDULER_NO_TASK)
3094 {
3095 GNUNET_SCHEDULER_cancel (source_info->delete_task);
3096 source_info->delete_task = GNUNET_SCHEDULER_NO_TASK;
3097 }
3098 if (source_info->find_peers_responded != NULL)
3099 GNUNET_CONTAINER_bloomfilter_free (source_info->find_peers_responded);
3100 GNUNET_free (source_info);
3101 current_size = GNUNET_CONTAINER_multihashmap_size (forward_list.hashmap);
3102 }
3103#endif
3104 /** Non-local request and have too many outstanding forwards, discard! */
3105 if ((current_size >= MAX_OUTSTANDING_FORWARDS) && (msg_ctx->client == NULL))
3106 return GNUNET_NO;
3107
3108 now = GNUNET_TIME_absolute_get ();
3109 record =
3110 GNUNET_CONTAINER_multihashmap_get (forward_list.hashmap, &msg_ctx->key);
3111 if (record != NULL) /* Already know this request! */
3112 {
3113 pos = record->head;
3114 while (pos != NULL)
3115 {
3116 if (0 ==
3117 memcmp (&msg_ctx->peer, &pos->source,
3118 sizeof (struct GNUNET_PeerIdentity)))
3119 break; /* Already have this peer in reply list! */
3120 pos = pos->next;
3121 }
3122 if ((pos != NULL) && (pos->client == msg_ctx->client)) /* Seen this already */
3123 {
3124 GNUNET_CONTAINER_heap_update_cost (forward_list.minHeap, pos->hnode,
3125 now.abs_value);
3126 return GNUNET_NO;
3127 }
3128 }
3129 else
3130 {
3131 record = GNUNET_malloc (sizeof (struct DHTQueryRecord));
3132 GNUNET_assert (GNUNET_OK ==
3133 GNUNET_CONTAINER_multihashmap_put (forward_list.hashmap,
3134 &msg_ctx->key, record,
3135 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
3136 memcpy (&record->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
3137 }
3138
3139 source_info = GNUNET_malloc (sizeof (struct DHTRouteSource));
3140 source_info->record = record;
3141 source_info->delete_task =
3142 GNUNET_SCHEDULER_add_delayed (DHT_FORWARD_TIMEOUT, &remove_forward_entry,
3143 source_info);
3144 source_info->find_peers_responded =
3145 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
3146 source_info->source = msg_ctx->peer;
3147 GNUNET_CONTAINER_DLL_insert_after (record->head, record->tail, record->tail,
3148 source_info);
3149 if (msg_ctx->client != NULL) /* For local request, set timeout so high it effectively never gets pushed out */
3150 {
3151 source_info->client = msg_ctx->client;
3152 now = GNUNET_TIME_absolute_get_forever ();
3153 }
3154 source_info->hnode =
3155 GNUNET_CONTAINER_heap_insert (forward_list.minHeap, source_info,
3156 now.abs_value);
3157 source_info->uid = msg_ctx->unique_id;
3158#if DEBUG_DHT > 1
3159 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3160 "`%s:%s': Created new forward source info for %s uid %llu\n",
3161 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
3162 msg_ctx->unique_id);
3163#endif
3164 return GNUNET_YES;
3165}
3166
3167
3168/**
3169 * Main function that handles whether or not to route a message to other
3170 * peers.
3171 *
3172 * @param msg the message to be routed
3173 * @param msg_ctx the context containing all pertinent information about the message
3174 */
3175static void
3176route_message (const struct GNUNET_MessageHeader *msg,
3177 struct DHT_MessageContext *msg_ctx)
3178{
3179 int i;
3180 struct PeerInfo *selected;
3181
3182#if DEBUG_DHT_ROUTING > 1
3183 struct PeerInfo *nearest;
3184#endif
3185 unsigned int target_forward_count;
3186 unsigned int forward_count;
3187 struct RecentRequest *recent_req;
3188#if HAVE_UID_FOR_TESTING > 1
3189 GNUNET_HashCode unique_hash;
3190#endif
3191 char *stat_forward_count;
3192 char *temp_stat_str;
3193
3194#if DEBUG_DHT_ROUTING
3195 int ret;
3196#endif
3197
3198 if (malicious_dropper == GNUNET_YES)
3199 {
3200#if DEBUG_DHT_ROUTING
3201 if ((debug_routes_extended) && (dhtlog_handle != NULL))
3202 {
3203 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
3204 msg_ctx->hop_count, GNUNET_SYSERR,
3205 &my_identity, &msg_ctx->key, &msg_ctx->peer,
3206 NULL);
3207 }
3208#endif
3209 if (msg_ctx->bloom != NULL)
3210 {
3211 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->bloom);
3212 msg_ctx->bloom = NULL;
3213 }
3214 return;
3215 }
3216
3217 increment_stats (STAT_ROUTES);
3218 target_forward_count =
3219 get_forward_count (msg_ctx->hop_count, msg_ctx->replication);
3220 GNUNET_asprintf (&stat_forward_count, "# forward counts of %d",
3221 target_forward_count);
3222 increment_stats (stat_forward_count);
3223 GNUNET_free (stat_forward_count);
3224 if (msg_ctx->bloom == NULL)
3225 msg_ctx->bloom =
3226 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
3227
3228 if ((stop_on_closest == GNUNET_YES) && (msg_ctx->closest == GNUNET_YES) &&
3229 (ntohs (msg->type) == GNUNET_MESSAGE_TYPE_DHT_PUT))
3230 target_forward_count = 0;
3231
3232 /**
3233 * NOTICE: In Kademlia, a find peer request goes no further if the peer doesn't return
3234 * any closer peers (which is being checked for below). Since we are doing recursive
3235 * routing we have no choice but to stop forwarding in this case. This means that at
3236 * any given step the request may NOT be forwarded to alpha peers (because routes will
3237 * stop and the parallel route will not be aware of it). Of course, assuming that we
3238 * have fulfilled the Kademlia requirements for routing table fullness this will never
3239 * ever ever be a problem.
3240 *
3241 * However, is this fair?
3242 *
3243 * Since we use these requests to build our routing tables (and we build them in the
3244 * testing driver) we will ignore this restriction for FIND_PEER messages so that
3245 * routing tables still get constructed.
3246 */
3247 if ((GNUNET_YES == strict_kademlia) && (msg_ctx->closest == GNUNET_YES) &&
3248 (msg_ctx->hop_count > 0) &&
3249 (ntohs (msg->type) != GNUNET_MESSAGE_TYPE_DHT_FIND_PEER))
3250 target_forward_count = 0;
3251
3252#if HAVE_UID_FOR_TESTING > 1
3253 /* BUG HERE: recent uses unique_id! So if all unique-IDs are 0, we get
3254 easily into trouble!!! Also, this should not even be necessary... */
3255 hash_from_uid (msg_ctx->unique_id, &unique_hash);
3256 if (GNUNET_YES ==
3257 GNUNET_CONTAINER_multihashmap_contains (recent.hashmap, &unique_hash))
3258 {
3259 recent_req =
3260 GNUNET_CONTAINER_multihashmap_get (recent.hashmap, &unique_hash);
3261 GNUNET_assert (recent_req != NULL);
3262 if (0 != memcmp (&recent_req->key, &msg_ctx->key, sizeof (GNUNET_HashCode)))
3263 increment_stats (STAT_DUPLICATE_UID);
3264 else
3265 {
3266 increment_stats (STAT_RECENT_SEEN);
3267 GNUNET_CONTAINER_bloomfilter_or2 (msg_ctx->bloom, recent_req->bloom,
3268 DHT_BLOOM_SIZE);
3269 }
3270 }
3271 else
3272#endif
3273 {
3274 recent_req = GNUNET_malloc (sizeof (struct RecentRequest));
3275 recent_req->uid = msg_ctx->unique_id;
3276 memcpy (&recent_req->key, &msg_ctx->key, sizeof (GNUNET_HashCode));
3277 recent_req->remove_task =
3278 GNUNET_SCHEDULER_add_delayed (DEFAULT_RECENT_REMOVAL, &remove_recent,
3279 recent_req);
3280 recent_req->heap_node =
3281 GNUNET_CONTAINER_heap_insert (recent.minHeap, recent_req,
3282 GNUNET_TIME_absolute_get ().abs_value);
3283 recent_req->bloom =
3284 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
3285#if HAVE_UID_FOR_TESTING > 1
3286 GNUNET_CONTAINER_multihashmap_put (recent.hashmap, &unique_hash, recent_req,
3287 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
3288#endif
3289 }
3290
3291 if (GNUNET_CONTAINER_heap_get_size (recent.minHeap) > DHT_MAX_RECENT)
3292 {
3293 recent_req = GNUNET_CONTAINER_heap_peek (recent.minHeap);
3294 GNUNET_assert (recent_req != NULL);
3295 GNUNET_SCHEDULER_cancel (recent_req->remove_task);
3296 recent_req->remove_task =
3297 GNUNET_SCHEDULER_add_now (&remove_recent, recent_req);
3298 }
3299
3300 forward_count = 0;
3301 for (i = 0; i < target_forward_count; i++)
3302 {
3303 selected = select_peer (&msg_ctx->key, msg_ctx->bloom, msg_ctx->hop_count);
3304 if (selected == NULL)
3305 break;
3306 forward_count++;
3307 if (GNUNET_CRYPTO_hash_matching_bits
3308 (&selected->id.hashPubKey,
3309 &msg_ctx->key) >=
3310 GNUNET_CRYPTO_hash_matching_bits (&my_identity.hashPubKey,
3311 &msg_ctx->key))
3312 GNUNET_asprintf (&temp_stat_str,
3313 "# requests routed to close(r) peer hop %u",
3314 msg_ctx->hop_count);
3315 else
3316 GNUNET_asprintf (&temp_stat_str,
3317 "# requests routed to less close peer hop %u",
3318 msg_ctx->hop_count);
3319 if (temp_stat_str != NULL)
3320 {
3321 increment_stats (temp_stat_str);
3322 GNUNET_free (temp_stat_str);
3323 }
3324 GNUNET_CONTAINER_bloomfilter_add (msg_ctx->bloom,
3325 &selected->id.hashPubKey);
3326#if DEBUG_DHT_ROUTING > 1
3327 nearest = find_closest_peer (&msg_ctx->key);
3328 nearest_buf = GNUNET_strdup (GNUNET_i2s (&nearest->id));
3329 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3330 "`%s:%s': Forwarding request key %s uid %llu to peer %s (closest %s, bits %d, distance %u)\n",
3331 my_short_id, "DHT", GNUNET_h2s (&msg_ctx->key),
3332 msg_ctx->unique_id, GNUNET_i2s (&selected->id), nearest_buf,
3333 GNUNET_CRYPTO_hash_matching_bits (&nearest->id.hashPubKey,
3334 msg_ctx->key),
3335 distance (&nearest->id.hashPubKey, msg_ctx->key));
3336 GNUNET_free (nearest_buf);
3337#endif
3338#if DEBUG_DHT_ROUTING
3339 if ((debug_routes_extended) && (dhtlog_handle != NULL))
3340 {
3341 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
3342 msg_ctx->hop_count, GNUNET_NO,
3343 &my_identity, &msg_ctx->key, &msg_ctx->peer,
3344 &selected->id);
3345 }
3346#endif
3347 forward_message (msg, selected, msg_ctx);
3348 }
3349
3350 if (msg_ctx->bloom != NULL)
3351 {
3352 GNUNET_CONTAINER_bloomfilter_or2 (recent_req->bloom, msg_ctx->bloom,
3353 DHT_BLOOM_SIZE);
3354 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->bloom);
3355 msg_ctx->bloom = NULL;
3356 }
3357
3358#if DEBUG_DHT_ROUTING
3359 if (forward_count == 0)
3360 ret = GNUNET_SYSERR;
3361 else
3362 ret = GNUNET_NO;
3363
3364 if ((debug_routes_extended) && (dhtlog_handle != NULL))
3365 {
3366 dhtlog_handle->insert_route (NULL, msg_ctx->unique_id, DHTLOG_ROUTE,
3367 msg_ctx->hop_count, ret, &my_identity,
3368 &msg_ctx->key, &msg_ctx->peer, NULL);
3369 }
3370#endif
3371}
3372
3373
3374/**
3375 * Main function that handles whether or not to route a message to other
3376 * peers.
3377 *
3378 * @param msg the message to be routed
3379 * @param msg_ctx the context containing all pertinent information about the message
3380 */
3381static void
3382demultiplex_message (const struct GNUNET_MessageHeader *msg,
3383 struct DHT_MessageContext *msg_ctx)
3384{
3385 /* FIXME: Should we use closest excluding those we won't route to (the bloomfilter problem)? */
3386 msg_ctx->closest = am_closest_peer (&msg_ctx->key, msg_ctx->bloom);
3387
3388 switch (ntohs (msg->type))
3389 {
3390 case GNUNET_MESSAGE_TYPE_DHT_GET: /* Add to hashmap of requests seen, search for data (always) */
3391 cache_response (msg_ctx);
3392 handle_dht_get (msg, msg_ctx);
3393 break;
3394 case GNUNET_MESSAGE_TYPE_DHT_PUT: /* Check if closest, if so insert data. */
3395 increment_stats (STAT_PUTS);
3396 handle_dht_put (msg, msg_ctx);
3397 break;
3398 case GNUNET_MESSAGE_TYPE_DHT_FIND_PEER: /* Check if closest and not started by us, check options, add to requests seen */
3399 increment_stats (STAT_FIND_PEER);
3400 if (((msg_ctx->hop_count > 0) &&
3401 (0 !=
3402 memcmp (&msg_ctx->peer, &my_identity,
3403 sizeof (struct GNUNET_PeerIdentity)))) ||
3404 (msg_ctx->client != NULL))
3405 {
3406 cache_response (msg_ctx);
3407 if ((msg_ctx->closest == GNUNET_YES) ||
3408 (msg_ctx->msg_options == GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE))
3409 handle_dht_find_peer (msg, msg_ctx);
3410 }
3411 else
3412 route_message (msg, msg_ctx);
3413#if DEBUG_DHT_ROUTING
3414 if (msg_ctx->hop_count == 0) /* Locally initiated request */
3415 {
3416 if ((debug_routes) && (dhtlog_handle != NULL))
3417 {
3418 dhtlog_handle->insert_dhtkey (NULL, &msg_ctx->key);
3419 dhtlog_handle->insert_query (NULL, msg_ctx->unique_id, DHTLOG_FIND_PEER,
3420 msg_ctx->hop_count, GNUNET_NO,
3421 &my_identity, &msg_ctx->key);
3422 }
3423 }
3424#endif
3425 break;
3426 default:
3427 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3428 "`%s': Message type (%d) not handled, forwarding anyway!\n",
3429 "DHT", ntohs (msg->type));
3430 route_message (msg, msg_ctx);
3431 }
3432}
3433
3434
3435/**
3436 * Iterator over hash map entries.
3437 *
3438 * @param cls client to search for in source routes
3439 * @param key current key code (ignored)
3440 * @param value value in the hash map, a DHTQueryRecord
3441 * @return GNUNET_YES if we should continue to
3442 * iterate,
3443 * GNUNET_NO if not.
3444 */
3445static int
3446find_client_records (void *cls, const GNUNET_HashCode * key, void *value)
3447{
3448 struct ClientList *client = cls;
3449 struct DHTQueryRecord *record = value;
3450 struct DHTRouteSource *pos;
3451
3452 pos = record->head;
3453 while (pos != NULL)
3454 {
3455 if (pos->client == client)
3456 break;
3457 pos = pos->next;
3458 }
3459 if (pos != NULL)
3460 {
3461 GNUNET_CONTAINER_DLL_remove (record->head, record->tail, pos);
3462 GNUNET_CONTAINER_heap_remove_node (pos->hnode);
3463 if (pos->delete_task != GNUNET_SCHEDULER_NO_TASK)
3464 {
3465 GNUNET_SCHEDULER_cancel (pos->delete_task);
3466 pos->delete_task = GNUNET_SCHEDULER_NO_TASK;
3467 }
3468 if (pos->find_peers_responded != NULL)
3469 GNUNET_CONTAINER_bloomfilter_free (pos->find_peers_responded);
3470 GNUNET_free (pos);
3471 }
3472 if (record->head == NULL) /* No more entries in DLL */
3473 {
3474 GNUNET_assert (GNUNET_YES ==
3475 GNUNET_CONTAINER_multihashmap_remove (forward_list.hashmap,
3476 &record->key, record));
3477 GNUNET_free (record);
3478 }
3479 return GNUNET_YES;
3480}
3481
3482/**
3483 * Functions with this signature are called whenever a client
3484 * is disconnected on the network level.
3485 *
3486 * @param cls closure (NULL for dht)
3487 * @param client identification of the client; NULL
3488 * for the last call when the server is destroyed
3489 */
3490static void
3491handle_client_disconnect (void *cls, struct GNUNET_SERVER_Client *client)
3492{
3493 struct ClientList *pos = client_list;
3494 struct ClientList *prev;
3495 struct ClientList *found;
3496 struct PendingMessage *reply;
3497
3498 prev = NULL;
3499 found = NULL;
3500 while (pos != NULL)
3501 {
3502 if (pos->client_handle == client)
3503 {
3504 if (prev != NULL)
3505 prev->next = pos->next;
3506 else
3507 client_list = pos->next;
3508 found = pos;
3509 break;
3510 }
3511 prev = pos;
3512 pos = pos->next;
3513 }
3514
3515 if (found != NULL)
3516 {
3517 if (found->transmit_handle != NULL)
3518 GNUNET_CONNECTION_notify_transmit_ready_cancel (found->transmit_handle);
3519
3520 while (NULL != (reply = found->pending_head))
3521 {
3522 GNUNET_CONTAINER_DLL_remove (found->pending_head, found->pending_tail,
3523 reply);
3524 GNUNET_free (reply);
3525 }
3526 GNUNET_CONTAINER_multihashmap_iterate (forward_list.hashmap,
3527 &find_client_records, found);
3528 GNUNET_free (found);
3529 }
3530}
3531
3532/**
3533 * Find a client if it exists, add it otherwise.
3534 *
3535 * @param client the server handle to the client
3536 *
3537 * @return the client if found, a new client otherwise
3538 */
3539static struct ClientList *
3540find_active_client (struct GNUNET_SERVER_Client *client)
3541{
3542 struct ClientList *pos = client_list;
3543 struct ClientList *ret;
3544
3545 while (pos != NULL)
3546 {
3547 if (pos->client_handle == client)
3548 return pos;
3549 pos = pos->next;
3550 }
3551
3552 ret = GNUNET_malloc (sizeof (struct ClientList));
3553 ret->client_handle = client;
3554 ret->next = client_list;
3555 client_list = ret;
3556
3557 return ret;
3558}
3559
3560#if HAVE_MALICIOUS
3561/**
3562 * Task to send a malicious put message across the network.
3563 *
3564 * @param cls closure for this task
3565 * @param tc the context under which the task is running
3566 */
3567static void
3568malicious_put_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
3569{
3570 static struct GNUNET_DHT_PutMessage put_message;
3571 static struct DHT_MessageContext msg_ctx;
3572 static GNUNET_HashCode key;
3573 uint32_t random_key;
3574
3575 if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
3576 return;
3577 put_message.header.size = htons (sizeof (struct GNUNET_DHT_PutMessage));
3578 put_message.header.type = htons (GNUNET_MESSAGE_TYPE_DHT_PUT);
3579 put_message.type = htonl (GNUNET_BLOCK_DHT_MALICIOUS_MESSAGE_TYPE);
3580 put_message.expiration =
3581 GNUNET_TIME_absolute_hton (GNUNET_TIME_absolute_get_forever ());
3582 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
3583 random_key =
3584 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
3585 GNUNET_CRYPTO_hash (&random_key, sizeof (uint32_t), &key);
3586 memcpy (&msg_ctx.key, &key, sizeof (GNUNET_HashCode));
3587 msg_ctx.unique_id =
3588 GNUNET_ntohll (GNUNET_CRYPTO_random_u64
3589 (GNUNET_CRYPTO_QUALITY_WEAK, UINT64_MAX));
3590 msg_ctx.replication = ntohl (DHT_DEFAULT_FIND_PEER_REPLICATION);
3591 msg_ctx.msg_options = ntohl (0);
3592 msg_ctx.network_size = log_of_network_size_estimate;
3593 msg_ctx.peer = my_identity;
3594 msg_ctx.importance = DHT_DEFAULT_P2P_IMPORTANCE;
3595 msg_ctx.timeout = DHT_DEFAULT_P2P_TIMEOUT;
3596#if DEBUG_DHT_ROUTING
3597 if (dhtlog_handle != NULL)
3598 dhtlog_handle->insert_dhtkey (NULL, &key);
3599#endif
3600 increment_stats (STAT_PUT_START);
3601 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3602 "%s:%s Sending malicious PUT message with hash %s\n", my_short_id,
3603 "DHT", GNUNET_h2s (&key));
3604 demultiplex_message (&put_message.header, &msg_ctx);
3605 GNUNET_SCHEDULER_add_delayed (malicious_put_frequency, &malicious_put_task,
3606 NULL);
3607}
3608
3609
3610/**
3611 * Task to send a malicious put message across the network.
3612 *
3613 * @param cls closure for this task
3614 * @param tc the context under which the task is running
3615 */
3616static void
3617malicious_get_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
3618{
3619 static struct GNUNET_DHT_GetMessage get_message;
3620 struct DHT_MessageContext msg_ctx;
3621 static GNUNET_HashCode key;
3622 uint32_t random_key;
3623
3624 if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
3625 return;
3626
3627 get_message.header.size = htons (sizeof (struct GNUNET_DHT_GetMessage));
3628 get_message.header.type = htons (GNUNET_MESSAGE_TYPE_DHT_GET);
3629 get_message.type = htonl (GNUNET_BLOCK_DHT_MALICIOUS_MESSAGE_TYPE);
3630 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
3631 random_key =
3632 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
3633 GNUNET_CRYPTO_hash (&random_key, sizeof (uint32_t), &key);
3634 memcpy (&msg_ctx.key, &key, sizeof (GNUNET_HashCode));
3635 msg_ctx.unique_id =
3636 GNUNET_ntohll (GNUNET_CRYPTO_random_u64
3637 (GNUNET_CRYPTO_QUALITY_WEAK, UINT64_MAX));
3638 msg_ctx.replication = ntohl (DHT_DEFAULT_FIND_PEER_REPLICATION);
3639 msg_ctx.msg_options = ntohl (0);
3640 msg_ctx.network_size = log_of_network_size_estimate;
3641 msg_ctx.peer = my_identity;
3642 msg_ctx.importance = DHT_DEFAULT_P2P_IMPORTANCE;
3643 msg_ctx.timeout = DHT_DEFAULT_P2P_TIMEOUT;
3644#if DEBUG_DHT_ROUTING
3645 if (dhtlog_handle != NULL)
3646 dhtlog_handle->insert_dhtkey (NULL, &key);
3647#endif
3648 increment_stats (STAT_GET_START);
3649 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3650 "%s:%s Sending malicious GET message with hash %s\n", my_short_id,
3651 "DHT", GNUNET_h2s (&key));
3652 demultiplex_message (&get_message.header, &msg_ctx);
3653 GNUNET_SCHEDULER_add_delayed (malicious_get_frequency, &malicious_get_task,
3654 NULL);
3655}
3656#endif
3657
3658
3659/**
3660 * Iterator over hash map entries.
3661 *
3662 * @param cls closure
3663 * @param key current key code
3664 * @param value value in the hash map
3665 * @return GNUNET_YES if we should continue to
3666 * iterate,
3667 * GNUNET_NO if not.
3668 */
3669static int
3670add_known_to_bloom (void *cls, const GNUNET_HashCode * key, void *value)
3671{
3672 struct GNUNET_CONTAINER_BloomFilter *bloom = cls;
3673
3674 GNUNET_CONTAINER_bloomfilter_add (bloom, key);
3675 return GNUNET_YES;
3676}
3677
3678/**
3679 * Task to send a find peer message for our own peer identifier
3680 * so that we can find the closest peers in the network to ourselves
3681 * and attempt to connect to them.
3682 *
3683 * @param cls closure for this task
3684 * @param tc the context under which the task is running
3685 */
3686static void
3687send_find_peer_message (void *cls,
3688 const struct GNUNET_SCHEDULER_TaskContext *tc)
3689{
3690 struct GNUNET_DHT_FindPeerMessage *find_peer_msg;
3691 struct DHT_MessageContext msg_ctx;
3692 struct GNUNET_TIME_Relative next_send_time;
3693 struct GNUNET_CONTAINER_BloomFilter *temp_bloom;
3694
3695 if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
3696 return;
3697
3698 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! */
3699 {
3700 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3701 "Have %d newly found peers since last find peer message sent!\n",
3702 newly_found_peers);
3703 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
3704 &send_find_peer_message, NULL);
3705 newly_found_peers = 0;
3706 return;
3707 }
3708
3709 increment_stats (STAT_FIND_PEER_START);
3710#if FIND_PEER_WITH_HELLO
3711 find_peer_msg =
3712 GNUNET_malloc (sizeof (struct GNUNET_DHT_FindPeerMessage) +
3713 GNUNET_HELLO_size ((struct GNUNET_HELLO_Message *)
3714 my_hello));
3715 find_peer_msg->header.size =
3716 htons (sizeof (struct GNUNET_DHT_FindPeerMessage) +
3717 GNUNET_HELLO_size ((struct GNUNET_HELLO_Message *) my_hello));
3718 memcpy (&find_peer_msg[1], my_hello,
3719 GNUNET_HELLO_size ((struct GNUNET_HELLO_Message *) my_hello));
3720#else
3721 find_peer_msg = GNUNET_malloc (sizeof (struct GNUNET_DHT_FindPeerMessage));
3722 find_peer_msg->header.size =
3723 htons (sizeof (struct GNUNET_DHT_FindPeerMessage));
3724#endif
3725 find_peer_msg->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_FIND_PEER);
3726 temp_bloom =
3727 GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K);
3728 GNUNET_CONTAINER_multihashmap_iterate (all_known_peers, &add_known_to_bloom,
3729 temp_bloom);
3730 GNUNET_assert (GNUNET_OK ==
3731 GNUNET_CONTAINER_bloomfilter_get_raw_data (temp_bloom,
3732 find_peer_msg->
3733 bloomfilter,
3734 DHT_BLOOM_SIZE));
3735 GNUNET_CONTAINER_bloomfilter_free (temp_bloom);
3736 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
3737 memcpy (&msg_ctx.key, &my_identity.hashPubKey, sizeof (GNUNET_HashCode));
3738 msg_ctx.unique_id =
3739 GNUNET_ntohll (GNUNET_CRYPTO_random_u64
3740 (GNUNET_CRYPTO_QUALITY_STRONG, UINT64_MAX));
3741 msg_ctx.replication = DHT_DEFAULT_FIND_PEER_REPLICATION;
3742 msg_ctx.msg_options = GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE;
3743 msg_ctx.network_size = log_of_network_size_estimate;
3744 msg_ctx.peer = my_identity;
3745 msg_ctx.importance = DHT_DEFAULT_FIND_PEER_IMPORTANCE;
3746 msg_ctx.timeout = DHT_DEFAULT_FIND_PEER_TIMEOUT;
3747
3748 demultiplex_message (&find_peer_msg->header, &msg_ctx);
3749 GNUNET_free (find_peer_msg);
3750 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3751 "`%s:%s': Sent `%s' request to some (?) peers\n", my_short_id,
3752 "DHT", "FIND PEER");
3753 if (newly_found_peers < bucket_size)
3754 {
3755 next_send_time.rel_value =
3756 (DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value / 2) +
3757 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_STRONG,
3758 DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value / 2);
3759 }
3760 else
3761 {
3762 next_send_time.rel_value =
3763 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value +
3764 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_STRONG,
3765 DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value -
3766 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value);
3767 }
3768
3769 GNUNET_assert (next_send_time.rel_value != 0);
3770 find_peer_context.count = 0;
3771 newly_found_peers = 0;
3772 find_peer_context.start = GNUNET_TIME_absolute_get ();
3773 if (GNUNET_YES == do_find_peer)
3774 {
3775 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_peer_message,
3776 NULL);
3777 }
3778}
3779
3780/**
3781 * Handler for any generic DHT messages, calls the appropriate handler
3782 * depending on message type, sends confirmation if responses aren't otherwise
3783 * expected.
3784 *
3785 * @param cls closure for the service
3786 * @param client the client we received this message from
3787 * @param message the actual message received
3788 */
3789static void
3790handle_dht_local_route_request (void *cls, struct GNUNET_SERVER_Client *client,
3791 const struct GNUNET_MessageHeader *message)
3792{
3793 const struct GNUNET_DHT_RouteMessage *dht_msg =
3794 (const struct GNUNET_DHT_RouteMessage *) message;
3795 const struct GNUNET_MessageHeader *enc_msg;
3796 struct DHT_MessageContext msg_ctx;
3797
3798 enc_msg = (const struct GNUNET_MessageHeader *) &dht_msg[1];
3799#if DEBUG_DHT
3800 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3801 "`%s:%s': Received `%s' request from client, message type %d, key %s, uid %llu\n",
3802 my_short_id, "DHT", "GENERIC", ntohs (message->type),
3803 GNUNET_h2s (&dht_msg->key), GNUNET_ntohll (dht_msg->unique_id));
3804#endif
3805#if DEBUG_DHT_ROUTING
3806 if (dhtlog_handle != NULL)
3807 dhtlog_handle->insert_dhtkey (NULL, &dht_msg->key);
3808#endif
3809
3810 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
3811 msg_ctx.client = find_active_client (client);
3812 memcpy (&msg_ctx.key, &dht_msg->key, sizeof (GNUNET_HashCode));
3813 msg_ctx.unique_id = GNUNET_ntohll (dht_msg->unique_id);
3814 msg_ctx.replication = ntohl (dht_msg->desired_replication_level);
3815 msg_ctx.msg_options = ntohl (dht_msg->options);
3816 if (GNUNET_DHT_RO_RECORD_ROUTE ==
3817 (msg_ctx.msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
3818 {
3819 msg_ctx.path_history = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
3820 memcpy (msg_ctx.path_history, &my_identity,
3821 sizeof (struct GNUNET_PeerIdentity));
3822 msg_ctx.path_history_len = 1;
3823 }
3824 msg_ctx.network_size = log_of_network_size_estimate;
3825 msg_ctx.peer = my_identity;
3826 msg_ctx.importance = DHT_DEFAULT_P2P_IMPORTANCE + 4; /* Make local routing a higher priority */
3827 msg_ctx.timeout = DHT_DEFAULT_P2P_TIMEOUT;
3828
3829 if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_GET)
3830 increment_stats (STAT_GET_START);
3831 else if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_PUT)
3832 increment_stats (STAT_PUT_START);
3833 else if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_FIND_PEER)
3834 increment_stats (STAT_FIND_PEER_START);
3835
3836 if (GNUNET_YES == malicious_dropper)
3837 {
3838 if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_GET)
3839 {
3840#if DEBUG_DHT_ROUTING
3841 if ((debug_routes) && (dhtlog_handle != NULL))
3842 {
3843 dhtlog_handle->insert_query (NULL, msg_ctx.unique_id, DHTLOG_GET,
3844 msg_ctx.hop_count, GNUNET_NO, &my_identity,
3845 &msg_ctx.key);
3846 }
3847#endif
3848 }
3849 else if (ntohs (enc_msg->type) == GNUNET_MESSAGE_TYPE_DHT_PUT)
3850 {
3851#if DEBUG_DHT_ROUTING
3852 if ((debug_routes) && (dhtlog_handle != NULL))
3853 {
3854 dhtlog_handle->insert_query (NULL, msg_ctx.unique_id, DHTLOG_PUT,
3855 msg_ctx.hop_count, GNUNET_NO, &my_identity,
3856 &msg_ctx.key);
3857 }
3858#endif
3859 }
3860 GNUNET_SERVER_receive_done (client, GNUNET_OK);
3861 GNUNET_free_non_null (msg_ctx.path_history);
3862 return;
3863 }
3864
3865 demultiplex_message (enc_msg, &msg_ctx);
3866 GNUNET_SERVER_receive_done (client, GNUNET_OK);
3867
3868}
3869
3870/**
3871 * Handler for any locally received DHT control messages,
3872 * sets malicious flags mostly for now.
3873 *
3874 * @param cls closure for the service
3875 * @param client the client we received this message from
3876 * @param message the actual message received
3877 *
3878 */
3879static void
3880handle_dht_control_message (void *cls, struct GNUNET_SERVER_Client *client,
3881 const struct GNUNET_MessageHeader *message)
3882{
3883 const struct GNUNET_DHT_ControlMessage *dht_control_msg =
3884 (const struct GNUNET_DHT_ControlMessage *) message;
3885
3886#if DEBUG_DHT
3887 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3888 "`%s:%s': Received `%s' request from client, command %d\n",
3889 my_short_id, "DHT", "CONTROL", ntohs (dht_control_msg->command));
3890#endif
3891
3892 switch (ntohs (dht_control_msg->command))
3893 {
3894 case GNUNET_MESSAGE_TYPE_DHT_FIND_PEER:
3895 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3896 "Sending self seeking find peer request!\n");
3897 GNUNET_SCHEDULER_add_now (&send_find_peer_message, NULL);
3898 break;
3899#if HAVE_MALICIOUS
3900 case GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_GET:
3901 if (ntohs (dht_control_msg->variable) > 0)
3902 malicious_get_frequency.rel_value = ntohs (dht_control_msg->variable);
3903 if (malicious_get_frequency.rel_value == 0)
3904 malicious_get_frequency = DEFAULT_MALICIOUS_GET_FREQUENCY;
3905 if (malicious_getter != GNUNET_YES)
3906 GNUNET_SCHEDULER_add_now (&malicious_get_task, NULL);
3907 malicious_getter = GNUNET_YES;
3908 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3909 "%s:%s Initiating malicious GET behavior, frequency %llu\n",
3910 my_short_id, "DHT", malicious_get_frequency.rel_value);
3911 break;
3912 case GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_PUT:
3913 if (ntohs (dht_control_msg->variable) > 0)
3914 malicious_put_frequency.rel_value = ntohs (dht_control_msg->variable);
3915 if (malicious_put_frequency.rel_value == 0)
3916 malicious_put_frequency = DEFAULT_MALICIOUS_PUT_FREQUENCY;
3917 if (malicious_putter != GNUNET_YES)
3918 GNUNET_SCHEDULER_add_now (&malicious_put_task, NULL);
3919 malicious_putter = GNUNET_YES;
3920 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3921 "%s:%s Initiating malicious PUT behavior, frequency %d\n",
3922 my_short_id, "DHT", malicious_put_frequency);
3923 break;
3924 case GNUNET_MESSAGE_TYPE_DHT_MALICIOUS_DROP:
3925#if DEBUG_DHT_ROUTING
3926 if ((malicious_dropper != GNUNET_YES) && (dhtlog_handle != NULL))
3927 dhtlog_handle->set_malicious (&my_identity);
3928#endif
3929 malicious_dropper = GNUNET_YES;
3930 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3931 "%s:%s Initiating malicious DROP behavior\n", my_short_id,
3932 "DHT");
3933 break;
3934#endif
3935 default:
3936 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3937 "%s:%s Unknown control command type `%d'!\n", my_short_id,
3938 "DHT", ntohs (dht_control_msg->command));
3939 break;
3940 }
3941
3942 GNUNET_SERVER_receive_done (client, GNUNET_OK);
3943}
3944
3945/**
3946 * Handler for any generic DHT stop messages, calls the appropriate handler
3947 * depending on message type (if processed locally)
3948 *
3949 * @param cls closure for the service
3950 * @param client the client we received this message from
3951 * @param message the actual message received
3952 *
3953 */
3954static void
3955handle_dht_local_route_stop (void *cls, struct GNUNET_SERVER_Client *client,
3956 const struct GNUNET_MessageHeader *message)
3957{
3958
3959 const struct GNUNET_DHT_StopMessage *dht_stop_msg =
3960 (const struct GNUNET_DHT_StopMessage *) message;
3961 struct DHTQueryRecord *record;
3962 struct DHTRouteSource *pos;
3963
3964#if DEBUG_DHT
3965 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
3966 "`%s:%s': Received `%s' request from client, uid %llu\n",
3967 my_short_id, "DHT", "GENERIC STOP",
3968 GNUNET_ntohll (dht_stop_msg->unique_id));
3969#endif
3970 record =
3971 GNUNET_CONTAINER_multihashmap_get (forward_list.hashmap,
3972 &dht_stop_msg->key);
3973 if (record != NULL)
3974 {
3975 pos = record->head;
3976
3977 while (pos != NULL)
3978 {
3979 /* If the client is non-null (local request) and the client matches the requesting client, remove the entry. */
3980 if ((pos->client != NULL) && (pos->client->client_handle == client))
3981 {
3982 if (pos->delete_task != GNUNET_SCHEDULER_NO_TASK)
3983 GNUNET_SCHEDULER_cancel (pos->delete_task);
3984 pos->delete_task =
3985 GNUNET_SCHEDULER_add_now (&remove_forward_entry, pos);
3986 }
3987 pos = pos->next;
3988 }
3989 }
3990
3991 GNUNET_SERVER_receive_done (client, GNUNET_OK);
3992}
3993
3994
3995/**
3996 * Core handler for p2p route requests.
3997 *
3998 * @param cls closure
3999 * @param message message
4000 * @param peer peer identity this notification is about
4001 * @param atsi performance data
4002 * @return GNUNET_OK to keep the connection open,
4003 * GNUNET_SYSERR to close it (signal serious error)
4004 */
4005static int
4006handle_dht_p2p_route_request (void *cls, const struct GNUNET_PeerIdentity *peer,
4007 const struct GNUNET_MessageHeader *message,
4008 const struct GNUNET_TRANSPORT_ATS_Information
4009 *atsi)
4010{
4011#if DEBUG_DHT
4012 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4013 "`%s:%s': Received P2P request from peer %s\n", my_short_id,
4014 "DHT", GNUNET_i2s (peer));
4015#endif
4016 struct GNUNET_DHT_P2PRouteMessage *incoming =
4017 (struct GNUNET_DHT_P2PRouteMessage *) message;
4018 struct GNUNET_MessageHeader *enc_msg =
4019 (struct GNUNET_MessageHeader *) &incoming[1];
4020 struct DHT_MessageContext *msg_ctx;
4021 char *route_path;
4022 int path_size;
4023
4024 if (ntohs (enc_msg->size) >= GNUNET_SERVER_MAX_MESSAGE_SIZE - 1)
4025 {
4026 GNUNET_break_op (0);
4027 return GNUNET_YES;
4028 }
4029
4030 if (malicious_dropper == GNUNET_YES)
4031 {
4032#if DEBUG_DHT_ROUTING
4033 if ((debug_routes_extended) && (dhtlog_handle != NULL))
4034 {
4035 /** Log routes that die due to high load! */
4036 dhtlog_handle->insert_route (NULL,
4037#if HAVE_UID_FOR_TESTING
4038 GNUNET_ntohll (incoming->unique_id),
4039#else
4040 0,
4041#endif
4042 DHTLOG_ROUTE, ntohl (incoming->hop_count),
4043 GNUNET_SYSERR, &my_identity, &incoming->key,
4044 peer, NULL);
4045 }
4046#endif
4047 return GNUNET_YES;
4048 }
4049
4050 if (get_max_send_delay ().rel_value > MAX_REQUEST_TIME.rel_value)
4051 {
4052 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4053 "Sending of previous replies took too long, backing off!\n");
4054 increment_stats ("# route requests dropped due to high load");
4055 decrease_max_send_delay (get_max_send_delay ());
4056#if DEBUG_DHT_ROUTING
4057 if ((debug_routes_extended) && (dhtlog_handle != NULL))
4058 {
4059 /** Log routes that die due to high load! */
4060 dhtlog_handle->insert_route (NULL,
4061#if HAVE_UID_FOR_TESTING
4062 GNUNET_ntohll (incoming->unique_id),
4063#else
4064 0,
4065#endif
4066 DHTLOG_ROUTE, ntohl (incoming->hop_count),
4067 GNUNET_SYSERR, &my_identity, &incoming->key,
4068 peer, NULL);
4069 }
4070#endif
4071 return GNUNET_YES;
4072 }
4073 msg_ctx = GNUNET_malloc (sizeof (struct DHT_MessageContext));
4074 msg_ctx->bloom =
4075 GNUNET_CONTAINER_bloomfilter_init (incoming->bloomfilter, DHT_BLOOM_SIZE,
4076 DHT_BLOOM_K);
4077 GNUNET_assert (msg_ctx->bloom != NULL);
4078 msg_ctx->hop_count = ntohl (incoming->hop_count);
4079 memcpy (&msg_ctx->key, &incoming->key, sizeof (GNUNET_HashCode));
4080 msg_ctx->replication = ntohl (incoming->desired_replication_level);
4081#if HAVE_UID_FOR_TESTING
4082 msg_ctx->unique_id = GNUNET_ntohll (incoming->unique_id);
4083#endif
4084 msg_ctx->msg_options = ntohl (incoming->options);
4085 if (GNUNET_DHT_RO_RECORD_ROUTE ==
4086 (msg_ctx->msg_options & GNUNET_DHT_RO_RECORD_ROUTE))
4087 {
4088 path_size =
4089 ntohl (incoming->outgoing_path_length) *
4090 sizeof (struct GNUNET_PeerIdentity);
4091 if (ntohs (message->size) !=
4092 (sizeof (struct GNUNET_DHT_P2PRouteMessage) + ntohs (enc_msg->size) +
4093 path_size))
4094 {
4095 GNUNET_break_op (0);
4096 GNUNET_free (msg_ctx);
4097 return GNUNET_YES;
4098 }
4099 route_path = (char *) &incoming[1];
4100 route_path = route_path + ntohs (enc_msg->size);
4101 msg_ctx->path_history =
4102 GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) + path_size);
4103 memcpy (msg_ctx->path_history, route_path, path_size);
4104 memcpy (&msg_ctx->path_history[path_size], &my_identity,
4105 sizeof (struct GNUNET_PeerIdentity));
4106 msg_ctx->path_history_len = ntohl (incoming->outgoing_path_length) + 1;
4107 }
4108 msg_ctx->network_size = ntohl (incoming->network_size);
4109 msg_ctx->peer = *peer;
4110 msg_ctx->importance = DHT_DEFAULT_P2P_IMPORTANCE;
4111 msg_ctx->timeout = DHT_DEFAULT_P2P_TIMEOUT;
4112 demultiplex_message (enc_msg, msg_ctx);
4113 if (msg_ctx->bloom != NULL)
4114 {
4115 GNUNET_CONTAINER_bloomfilter_free (msg_ctx->bloom);
4116 msg_ctx->bloom = NULL;
4117 }
4118 GNUNET_free (msg_ctx);
4119 return GNUNET_YES;
4120}
4121
4122
4123/**
4124 * Core handler for p2p route results.
4125 *
4126 * @param cls closure
4127 * @param message message
4128 * @param peer peer identity this notification is about
4129 * @param atsi performance data
4130 *
4131 */
4132static int
4133handle_dht_p2p_route_result (void *cls, const struct GNUNET_PeerIdentity *peer,
4134 const struct GNUNET_MessageHeader *message,
4135 const struct GNUNET_TRANSPORT_ATS_Information
4136 *atsi)
4137{
4138#if DEBUG_DHT
4139 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4140 "`%s:%s': Received request from peer %s\n", my_short_id, "DHT",
4141 GNUNET_i2s (peer));
4142#endif
4143 const struct GNUNET_DHT_P2PRouteResultMessage *incoming =
4144 (const struct GNUNET_DHT_P2PRouteResultMessage *) message;
4145 struct GNUNET_MessageHeader *enc_msg =
4146 (struct GNUNET_MessageHeader *) &incoming[1];
4147 struct DHT_MessageContext msg_ctx;
4148
4149#if DEBUG_PATH
4150 char *path_offset;
4151 unsigned int i;
4152#endif
4153 if (ntohs (enc_msg->size) >= GNUNET_SERVER_MAX_MESSAGE_SIZE - 1)
4154 {
4155 GNUNET_break_op (0);
4156 return GNUNET_YES;
4157 }
4158
4159 if (malicious_dropper == GNUNET_YES)
4160 {
4161#if DEBUG_DHT_ROUTING
4162 if ((debug_routes_extended) && (dhtlog_handle != NULL))
4163 {
4164 /** Log routes that die due to high load! */
4165 dhtlog_handle->insert_route (NULL,
4166#if HAVE_UID_FOR_TESTING
4167 GNUNET_ntohll (incoming->unique_id),
4168#else
4169 0,
4170#endif
4171 DHTLOG_ROUTE, ntohl (incoming->hop_count),
4172 GNUNET_SYSERR, &my_identity, &incoming->key,
4173 peer, NULL);
4174 }
4175#endif
4176 return GNUNET_YES;
4177 }
4178
4179 memset (&msg_ctx, 0, sizeof (struct DHT_MessageContext));
4180 memcpy (&msg_ctx.key, &incoming->key, sizeof (GNUNET_HashCode));
4181#if HAVE_UID_FOR_TESTING
4182 msg_ctx.unique_id = GNUNET_ntohll (incoming->unique_id);
4183#endif
4184 msg_ctx.msg_options = ntohl (incoming->options);
4185 msg_ctx.hop_count = ntohl (incoming->hop_count);
4186 msg_ctx.peer = *peer;
4187 msg_ctx.importance = DHT_DEFAULT_P2P_IMPORTANCE + 2; /* Make result routing a higher priority */
4188 msg_ctx.timeout = DHT_DEFAULT_P2P_TIMEOUT;
4189 if ((GNUNET_DHT_RO_RECORD_ROUTE ==
4190 (msg_ctx.msg_options & GNUNET_DHT_RO_RECORD_ROUTE)) &&
4191 (ntohl (incoming->outgoing_path_length) > 0))
4192 {
4193 if (ntohs (message->size) -
4194 sizeof (struct GNUNET_DHT_P2PRouteResultMessage) -
4195 ntohs (enc_msg->size) !=
4196 ntohl (incoming->outgoing_path_length) *
4197 sizeof (struct GNUNET_PeerIdentity))
4198 {
4199#if DEBUG_DHT
4200 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4201 "Return message indicated a path was included, but sizes are wrong: Total size %d, enc size %d, left %d, expected %d\n",
4202 ntohs (message->size), ntohs (enc_msg->size),
4203 ntohs (message->size) -
4204 sizeof (struct GNUNET_DHT_P2PRouteResultMessage) -
4205 ntohs (enc_msg->size),
4206 ntohl (incoming->outgoing_path_length) *
4207 sizeof (struct GNUNET_PeerIdentity));
4208#endif
4209 GNUNET_break_op (0);
4210 return GNUNET_NO;
4211 }
4212 msg_ctx.path_history = (char *) &incoming[1];
4213 msg_ctx.path_history += ntohs (enc_msg->size);
4214 msg_ctx.path_history_len = ntohl (incoming->outgoing_path_length);
4215#if DEBUG_PATH
4216 for (i = 0; i < msg_ctx.path_history_len; i++)
4217 {
4218 path_offset =
4219 &msg_ctx.path_history[i * sizeof (struct GNUNET_PeerIdentity)];
4220 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4221 "(handle_p2p_route_result) Key %s Found peer %d:%s\n",
4222 GNUNET_h2s (&msg_ctx.key), i,
4223 GNUNET_i2s ((struct GNUNET_PeerIdentity *) path_offset));
4224 }
4225#endif
4226 }
4227 route_result_message (enc_msg, &msg_ctx);
4228 return GNUNET_YES;
4229}
4230
4231
4232/**
4233 * Receive the HELLO from transport service,
4234 * free current and replace if necessary.
4235 *
4236 * @param cls NULL
4237 * @param message HELLO message of peer
4238 */
4239static void
4240process_hello (void *cls, const struct GNUNET_MessageHeader *message)
4241{
4242#if DEBUG_DHT
4243 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4244 "Received our `%s' from transport service\n", "HELLO");
4245#endif
4246
4247 GNUNET_assert (message != NULL);
4248 GNUNET_free_non_null (my_hello);
4249 my_hello = GNUNET_malloc (ntohs (message->size));
4250 memcpy (my_hello, message, ntohs (message->size));
4251}
4252
4253
4254/**
4255 * Task run during shutdown.
4256 *
4257 * @param cls unused
4258 * @param tc unused
4259 */
4260static void
4261shutdown_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
4262{
4263 int bucket_count;
4264 struct PeerInfo *pos;
4265
4266 if (NULL != ghh)
4267 {
4268 GNUNET_TRANSPORT_get_hello_cancel (ghh);
4269 ghh = NULL;
4270 }
4271 if (transport_handle != NULL)
4272 {
4273 GNUNET_free_non_null (my_hello);
4274 GNUNET_TRANSPORT_disconnect (transport_handle);
4275 transport_handle = NULL;
4276 }
4277 if (NULL != nse)
4278 {
4279 GNUNET_NSE_disconnect (nse);
4280 nse = NULL;
4281 }
4282 if (coreAPI != NULL)
4283 {
4284#if DEBUG_DHT
4285 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%s:%s Disconnecting core!\n",
4286 my_short_id, "DHT");
4287#endif
4288 GNUNET_CORE_disconnect (coreAPI);
4289 coreAPI = NULL;
4290 }
4291 for (bucket_count = lowest_bucket; bucket_count < MAX_BUCKETS; bucket_count++)
4292 {
4293 while (k_buckets[bucket_count].head != NULL)
4294 {
4295 pos = k_buckets[bucket_count].head;
4296#if DEBUG_DHT
4297 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4298 "%s:%s Removing peer %s from bucket %d!\n", my_short_id,
4299 "DHT", GNUNET_i2s (&pos->id), bucket_count);
4300#endif
4301 delete_peer (pos, bucket_count);
4302 }
4303 }
4304 if (datacache != NULL)
4305 {
4306#if DEBUG_DHT
4307 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%s:%s Destroying datacache!\n",
4308 my_short_id, "DHT");
4309#endif
4310 GNUNET_DATACACHE_destroy (datacache);
4311 datacache = NULL;
4312 }
4313 if (stats != NULL)
4314 {
4315 GNUNET_STATISTICS_destroy (stats, GNUNET_YES);
4316 stats = NULL;
4317 }
4318 if (dhtlog_handle != NULL)
4319 {
4320 GNUNET_DHTLOG_disconnect (dhtlog_handle);
4321 dhtlog_handle = NULL;
4322 }
4323 if (block_context != NULL)
4324 {
4325 GNUNET_BLOCK_context_destroy (block_context);
4326 block_context = NULL;
4327 }
4328 GNUNET_free_non_null (my_short_id);
4329 my_short_id = NULL;
4330}
4331
4332
4333/**
4334 * To be called on core init/fail.
4335 *
4336 * @param cls service closure
4337 * @param server handle to the server for this service
4338 * @param identity the public identity of this peer
4339 * @param publicKey the public key of this peer
4340 */
4341static void
4342core_init (void *cls, struct GNUNET_CORE_Handle *server,
4343 const struct GNUNET_PeerIdentity *identity,
4344 const struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded *publicKey)
4345{
4346
4347 if (server == NULL)
4348 {
4349#if DEBUG_DHT
4350 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%s: Connection to core FAILED!\n",
4351 "dht", GNUNET_i2s (identity));
4352#endif
4353 GNUNET_SCHEDULER_cancel (cleanup_task);
4354 GNUNET_SCHEDULER_add_now (&shutdown_task, NULL);
4355 return;
4356 }
4357#if DEBUG_DHT
4358 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4359 "%s: Core connection initialized, I am peer: %s\n", "dht",
4360 GNUNET_i2s (identity));
4361#endif
4362
4363 /* Copy our identity so we can use it */
4364 memcpy (&my_identity, identity, sizeof (struct GNUNET_PeerIdentity));
4365 if (my_short_id != NULL)
4366 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
4367 "%s Receive CORE INIT message but have already been initialized! Did CORE fail?\n",
4368 "DHT SERVICE");
4369 my_short_id = GNUNET_strdup (GNUNET_i2s (&my_identity));
4370 if (dhtlog_handle != NULL)
4371 dhtlog_handle->insert_node (NULL, &my_identity);
4372}
4373
4374
4375static struct GNUNET_SERVER_MessageHandler plugin_handlers[] = {
4376 {&handle_dht_local_route_request, NULL, GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE,
4377 0},
4378 {&handle_dht_local_route_stop, NULL,
4379 GNUNET_MESSAGE_TYPE_DHT_LOCAL_ROUTE_STOP, 0},
4380 {&handle_dht_control_message, NULL, GNUNET_MESSAGE_TYPE_DHT_CONTROL, 0},
4381 {NULL, NULL, 0, 0}
4382};
4383
4384
4385static struct GNUNET_CORE_MessageHandler core_handlers[] = {
4386 {&handle_dht_p2p_route_request, GNUNET_MESSAGE_TYPE_DHT_P2P_ROUTE, 0},
4387 {&handle_dht_p2p_route_result, GNUNET_MESSAGE_TYPE_DHT_P2P_ROUTE_RESULT, 0},
4388 {NULL, 0, 0}
4389};
4390
4391
4392/**
4393 * Method called whenever a peer connects.
4394 *
4395 * @param cls closure
4396 * @param peer peer identity this notification is about
4397 * @param atsi performance data
4398 */
4399static void
4400handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer,
4401 const struct GNUNET_TRANSPORT_ATS_Information *atsi)
4402{
4403 struct PeerInfo *ret;
4404 struct DHTPutEntry *put_entry;
4405 int peer_bucket;
4406
4407 /* Check for connect to self message */
4408 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
4409 return;
4410
4411#if DEBUG_DHT
4412 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4413 "%s:%s Receives core connect message for peer %s distance %d!\n",
4414 my_short_id, "dht", GNUNET_i2s (peer), distance);
4415#endif
4416
4417 if (GNUNET_YES ==
4418 GNUNET_CONTAINER_multihashmap_contains (all_known_peers,
4419 &peer->hashPubKey))
4420 {
4421#if DEBUG_DHT
4422 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4423 "%s:%s Received %s message for peer %s, but already have peer in RT!",
4424 my_short_id, "DHT", "CORE CONNECT", GNUNET_i2s (peer));
4425#endif
4426 GNUNET_break (0);
4427 return;
4428 }
4429
4430 if ((datacache != NULL) && (GNUNET_YES == put_peer_identities))
4431 {
4432 put_entry =
4433 GNUNET_malloc (sizeof (struct DHTPutEntry) +
4434 sizeof (struct GNUNET_PeerIdentity));
4435 put_entry->path_length = 0;
4436 put_entry->data_size = sizeof (struct GNUNET_PeerIdentity);
4437 memcpy (&put_entry[1], peer, sizeof (struct GNUNET_PeerIdentity));
4438 GNUNET_DATACACHE_put (datacache, &peer->hashPubKey,
4439 sizeof (struct DHTPutEntry) +
4440 sizeof (struct GNUNET_PeerIdentity),
4441 (char *) put_entry, GNUNET_BLOCK_TYPE_DHT_HELLO,
4442 GNUNET_TIME_absolute_get_forever ());
4443 GNUNET_free (put_entry);
4444 }
4445 else if (datacache == NULL)
4446 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
4447 "DHT has no connection to datacache!\n");
4448
4449 peer_bucket = find_current_bucket (&peer->hashPubKey);
4450 GNUNET_assert (peer_bucket >= lowest_bucket);
4451 GNUNET_assert (peer_bucket < MAX_BUCKETS);
4452 ret = GNUNET_malloc (sizeof (struct PeerInfo));
4453#if 0
4454 ret->latency = latency;
4455 ret->distance = distance;
4456#endif
4457 ret->id = *peer;
4458 GNUNET_CONTAINER_DLL_insert_after (k_buckets[peer_bucket].head,
4459 k_buckets[peer_bucket].tail,
4460 k_buckets[peer_bucket].tail, ret);
4461 k_buckets[peer_bucket].peers_size++;
4462#if DO_UPDATE_PREFERENCE
4463 if ((GNUNET_CRYPTO_hash_matching_bits
4464 (&my_identity.hashPubKey, &peer->hashPubKey) > 0) &&
4465 (k_buckets[peer_bucket].peers_size <= bucket_size))
4466 ret->preference_task =
4467 GNUNET_SCHEDULER_add_now (&update_core_preference, ret);
4468#endif
4469 if ((k_buckets[lowest_bucket].peers_size) >= bucket_size)
4470 enable_next_bucket ();
4471 newly_found_peers++;
4472 GNUNET_CONTAINER_multihashmap_put (all_known_peers, &peer->hashPubKey, ret,
4473 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
4474 increment_stats (STAT_PEERS_KNOWN);
4475
4476#if DEBUG_DHT
4477 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4478 "%s:%s Adding peer to routing list: %s\n", my_short_id, "DHT",
4479 ret == NULL ? "NOT ADDED" : "PEER ADDED");
4480#endif
4481}
4482
4483
4484/**
4485 * Method called whenever a peer disconnects.
4486 *
4487 * @param cls closure
4488 * @param peer peer identity this notification is about
4489 */
4490static void
4491handle_core_disconnect (void *cls, const struct GNUNET_PeerIdentity *peer)
4492{
4493 struct PeerInfo *to_remove;
4494 int current_bucket;
4495
4496 /* Check for disconnect from self message */
4497 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
4498 return;
4499#if DEBUG_DHT
4500 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4501 "%s:%s: Received peer disconnect message for peer `%s' from %s\n",
4502 my_short_id, "DHT", GNUNET_i2s (peer), "CORE");
4503#endif
4504
4505 if (GNUNET_YES !=
4506 GNUNET_CONTAINER_multihashmap_contains (all_known_peers,
4507 &peer->hashPubKey))
4508 {
4509 GNUNET_break (0);
4510#if DEBUG_DHT
4511 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
4512 "%s:%s: do not have peer `%s' in RT, can't disconnect!\n",
4513 my_short_id, "DHT", GNUNET_i2s (peer));
4514#endif
4515 return;
4516 }
4517 increment_stats (STAT_DISCONNECTS);
4518 GNUNET_assert (GNUNET_CONTAINER_multihashmap_contains
4519 (all_known_peers, &peer->hashPubKey));
4520 to_remove =
4521 GNUNET_CONTAINER_multihashmap_get (all_known_peers, &peer->hashPubKey);
4522 GNUNET_assert (to_remove != NULL);
4523 if (NULL != to_remove->info_ctx)
4524 {
4525 GNUNET_CORE_peer_change_preference_cancel (to_remove->info_ctx);
4526 to_remove->info_ctx = NULL;
4527 }
4528 GNUNET_assert (0 ==
4529 memcmp (peer, &to_remove->id,
4530 sizeof (struct GNUNET_PeerIdentity)));
4531 current_bucket = find_current_bucket (&to_remove->id.hashPubKey);
4532 delete_peer (to_remove, current_bucket);
4533}
4534
4535
4536/**
4537 * Process dht requests.
4538 *
4539 * @param cls closure
4540 * @param server the initialized server
4541 * @param c configuration to use
4542 */
4543static void
4544run (void *cls, struct GNUNET_SERVER_Handle *server,
4545 const struct GNUNET_CONFIGURATION_Handle *c)
4546{
4547 struct GNUNET_TIME_Relative next_send_time;
4548 unsigned long long temp_config_num;
4549
4550 cfg = c;
4551 datacache = GNUNET_DATACACHE_create (cfg, "dhtcache");
4552 GNUNET_SERVER_add_handlers (server, plugin_handlers);
4553 GNUNET_SERVER_disconnect_notify (server, &handle_client_disconnect, NULL);
4554 nse = GNUNET_NSE_connect (cfg, &update_network_size_estimate, NULL);
4555 coreAPI = GNUNET_CORE_connect (cfg, /* Main configuration */
4556 DEFAULT_CORE_QUEUE_SIZE, /* queue size */
4557 NULL, /* Closure passed to DHT functions */
4558 &core_init, /* Call core_init once connected */
4559 &handle_core_connect, /* Handle connects */
4560 &handle_core_disconnect, /* remove peers on disconnects */
4561 NULL, /* Do we care about "status" updates? */
4562 NULL, /* Don't want notified about all incoming messages */
4563 GNUNET_NO, /* For header only inbound notification */
4564 NULL, /* Don't want notified about all outbound messages */
4565 GNUNET_NO, /* For header only outbound notification */
4566 core_handlers); /* Register these handlers */
4567
4568 if (coreAPI == NULL)
4569 return;
4570 transport_handle =
4571 GNUNET_TRANSPORT_connect (cfg, NULL, NULL, NULL, NULL, NULL);
4572 if (transport_handle != NULL)
4573 ghh = GNUNET_TRANSPORT_get_hello (transport_handle, &process_hello, NULL);
4574 else
4575 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
4576 "Failed to connect to transport service!\n");
4577 block_context = GNUNET_BLOCK_context_create (cfg);
4578 lowest_bucket = MAX_BUCKETS - 1;
4579 forward_list.hashmap =
4580 GNUNET_CONTAINER_multihashmap_create (MAX_OUTSTANDING_FORWARDS / 10);
4581 forward_list.minHeap =
4582 GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
4583 all_known_peers = GNUNET_CONTAINER_multihashmap_create (MAX_BUCKETS / 8);
4584 GNUNET_assert (all_known_peers != NULL);
4585 if (GNUNET_YES ==
4586 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht_testing",
4587 "mysql_logging"))
4588 {
4589 debug_routes = GNUNET_YES;
4590 }
4591
4592 if (GNUNET_YES ==
4593 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "strict_kademlia"))
4594 {
4595 strict_kademlia = GNUNET_YES;
4596 }
4597
4598 if (GNUNET_YES ==
4599 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "stop_on_closest"))
4600 {
4601 stop_on_closest = GNUNET_YES;
4602 }
4603
4604 if (GNUNET_YES ==
4605 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "stop_found"))
4606 {
4607 stop_on_found = GNUNET_YES;
4608 }
4609
4610 if (GNUNET_YES ==
4611 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "malicious_getter"))
4612 {
4613 malicious_getter = GNUNET_YES;
4614 if (GNUNET_NO ==
4615 GNUNET_CONFIGURATION_get_value_time (cfg, "DHT",
4616 "MALICIOUS_GET_FREQUENCY",
4617 &malicious_get_frequency))
4618 malicious_get_frequency = DEFAULT_MALICIOUS_GET_FREQUENCY;
4619 }
4620
4621 if (GNUNET_YES ==
4622 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "malicious_putter"))
4623 {
4624 malicious_putter = GNUNET_YES;
4625 if (GNUNET_NO ==
4626 GNUNET_CONFIGURATION_get_value_time (cfg, "DHT",
4627 "MALICIOUS_PUT_FREQUENCY",
4628 &malicious_put_frequency))
4629 malicious_put_frequency = DEFAULT_MALICIOUS_PUT_FREQUENCY;
4630 }
4631
4632 if (GNUNET_OK ==
4633 GNUNET_CONFIGURATION_get_value_number (cfg, "DHT", "bucket_size",
4634 &temp_config_num))
4635 {
4636 bucket_size = (unsigned int) temp_config_num;
4637 }
4638
4639 if (GNUNET_OK !=
4640 GNUNET_CONFIGURATION_get_value_number (cfg, "DHT", "kad_alpha",
4641 &kademlia_replication))
4642 {
4643 kademlia_replication = DEFAULT_KADEMLIA_REPLICATION;
4644 }
4645
4646 if (GNUNET_YES ==
4647 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "malicious_dropper"))
4648 {
4649 malicious_dropper = GNUNET_YES;
4650 }
4651
4652 if (GNUNET_NO ==
4653 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "do_find_peer"))
4654 {
4655 do_find_peer = GNUNET_NO;
4656 }
4657 else
4658 do_find_peer = GNUNET_YES;
4659
4660 if (GNUNET_YES ==
4661 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "use_real_distance"))
4662 use_real_distance = GNUNET_YES;
4663
4664 if (GNUNET_YES ==
4665 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht_testing",
4666 "mysql_logging_extended"))
4667 {
4668 debug_routes = GNUNET_YES;
4669 debug_routes_extended = GNUNET_YES;
4670 }
4671
4672#if DEBUG_DHT_ROUTING
4673 if (GNUNET_YES == debug_routes)
4674 {
4675 dhtlog_handle = GNUNET_DHTLOG_connect (cfg);
4676 if (dhtlog_handle == NULL)
4677 {
4678 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
4679 "Could not connect to mysql logging server, logging will not happen!");
4680 }
4681 }
4682#endif
4683
4684 if (GNUNET_YES ==
4685 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "paper_forwarding"))
4686 paper_forwarding = GNUNET_YES;
4687
4688 if (GNUNET_YES ==
4689 GNUNET_CONFIGURATION_get_value_yesno (cfg, "dht", "put_peer_identities"))
4690 put_peer_identities = GNUNET_YES;
4691
4692 stats = GNUNET_STATISTICS_create ("dht", cfg);
4693
4694 if (stats != NULL)
4695 {
4696 GNUNET_STATISTICS_set (stats, STAT_ROUTES, 0, GNUNET_NO);
4697 GNUNET_STATISTICS_set (stats, STAT_ROUTE_FORWARDS, 0, GNUNET_NO);
4698 GNUNET_STATISTICS_set (stats, STAT_ROUTE_FORWARDS_CLOSEST, 0, GNUNET_NO);
4699 GNUNET_STATISTICS_set (stats, STAT_RESULTS, 0, GNUNET_NO);
4700 GNUNET_STATISTICS_set (stats, STAT_RESULTS_TO_CLIENT, 0, GNUNET_NO);
4701 GNUNET_STATISTICS_set (stats, STAT_RESULT_FORWARDS, 0, GNUNET_NO);
4702 GNUNET_STATISTICS_set (stats, STAT_GETS, 0, GNUNET_NO);
4703 GNUNET_STATISTICS_set (stats, STAT_PUTS, 0, GNUNET_NO);
4704 GNUNET_STATISTICS_set (stats, STAT_PUTS_INSERTED, 0, GNUNET_NO);
4705 GNUNET_STATISTICS_set (stats, STAT_FIND_PEER, 0, GNUNET_NO);
4706 GNUNET_STATISTICS_set (stats, STAT_FIND_PEER_START, 0, GNUNET_NO);
4707 GNUNET_STATISTICS_set (stats, STAT_GET_START, 0, GNUNET_NO);
4708 GNUNET_STATISTICS_set (stats, STAT_PUT_START, 0, GNUNET_NO);
4709 GNUNET_STATISTICS_set (stats, STAT_FIND_PEER_REPLY, 0, GNUNET_NO);
4710 GNUNET_STATISTICS_set (stats, STAT_FIND_PEER_ANSWER, 0, GNUNET_NO);
4711 GNUNET_STATISTICS_set (stats, STAT_BLOOM_FIND_PEER, 0, GNUNET_NO);
4712 GNUNET_STATISTICS_set (stats, STAT_GET_REPLY, 0, GNUNET_NO);
4713 GNUNET_STATISTICS_set (stats, STAT_GET_RESPONSE_START, 0, GNUNET_NO);
4714 GNUNET_STATISTICS_set (stats, STAT_HELLOS_PROVIDED, 0, GNUNET_NO);
4715 GNUNET_STATISTICS_set (stats, STAT_DISCONNECTS, 0, GNUNET_NO);
4716 }
4717 if (GNUNET_YES == do_find_peer)
4718 {
4719 next_send_time.rel_value =
4720 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value +
4721 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_STRONG,
4722 (DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value /
4723 2) -
4724 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value);
4725 find_peer_context.start = GNUNET_TIME_absolute_get ();
4726 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_peer_message,
4727 &find_peer_context);
4728 }
4729
4730 /* Scheduled the task to clean up when shutdown is called */
4731 cleanup_task =
4732 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL,
4733 &shutdown_task, NULL);
4734}
4735
4736
4737/**
4738 * The main function for the dht service.
4739 *
4740 * @param argc number of arguments from the command line
4741 * @param argv command line arguments
4742 * @return 0 ok, 1 on error
4743 */
4744int
4745main (int argc, char *const *argv)
4746{
4747 int ret;
4748
4749#if HAVE_UID_FOR_TESTING > 1
4750 recent.hashmap = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT / 2);
4751#endif
4752 recent.minHeap =
4753 GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
4754 recent_find_peer_requests =
4755 GNUNET_CONTAINER_multihashmap_create (MAX_BUCKETS / 8);
4756 ret =
4757 (GNUNET_OK ==
4758 GNUNET_SERVICE_run (argc, argv, "dht", GNUNET_SERVICE_OPTION_NONE, &run,
4759 NULL)) ? 0 : 1;
4760#if HAVE_UID_FOR_TESTING > 1
4761 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (recent.hashmap));
4762 GNUNET_CONTAINER_multihashmap_destroy (recent.hashmap);
4763 recent.hashmap = NULL;
4764#endif
4765 GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent.minHeap));
4766 GNUNET_CONTAINER_heap_destroy (recent.minHeap);
4767 recent.minHeap = NULL;
4768 GNUNET_CONTAINER_multihashmap_destroy (recent_find_peer_requests);
4769 recent_find_peer_requests = NULL;
4770 return ret;
4771}
4772
4773/* end of gnunet-service-dht.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-30 08:53:29 +0000