src/dht/gnunet-service-dht.c

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