table.c

GNUnet是一个安全的点对点网络框架

/*
      This file is part of GNUnet
      (C) 2006, 2007 Christian Grothoff (and other contributing authors)

      GNUnet is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
      by the Free Software Foundation; either version 2, or (at your
      option) any later version.

      GNUnet is distributed in the hope that it will be useful, but
      WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      General Public License for more details.

      You should have received a copy of the GNU General Public License
      along with GNUnet; see the file COPYING.  If not, write to the
      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
      Boston, MA 02111-1307, USA.
 */

/**
 * @file module/table.c
 * @brief maintains table of DHT connections of this peer
 * @author Christian Grothoff
 *
 * New DHT infrastructure plan:
 * - no RPC, pure async messaging
 * - stateful routing; needed for retry and reply routing
 * - no per-table storage; instead global,
 *   SQL database-based storage for entire peer
 * - no delete operation, just get/put + expiration
 * - no "put" confirmation, try a get to confirm important put!
 * - modules:
 *   + table.c: DHT-peer table, peer discovery cron jobs;
 *     code tries to fill table "as much as possible" over time;
 *     TODO: expose and improve reliabily metrics (to be added later)???
 *     TODO: better randomized neighbor selection in DHT_select_peer???
 *     TODO: add callback for discovery-message padding (use core callback
 *           for extra-available bandwidth)
 *     TODO: add LAN tunnels for increased connectivity choices
 *   + routing.c: tracking of get/put operations, retry, reply handling
 *     code tries best-match routing among entries in table
 *   + service.c: provide DHT services to rest of GNUnet process
 *     (i.e. register datastore with shared data, get/put operations)
 *   + cs.c: services to out-of-process DHT clients (via dht-lib)
 */

#include "platform.h"
#include <math.h>
#include "table.h"
#include "gnunet_protocols.h"
#include "gnunet_util.h"
#include "gnunet_dht_service.h"
#include "gnunet_stats_service.h"
#include "gnunet_identity_service.h"
#include "gnunet_pingpong_service.h"


/**
 * How often should the cron job for maintaining the DHT
 * run?
 */
#define MAINTAIN_FREQUENCY 1500 * GNUNET_CRON_MILLISECONDS

/**
 * What is the chance (1 in XXX) that we send DISCOVERY messages
 * to another peer?
 */
#define MAINTAIN_CHANCE (10 + 100 * total_peers)

/**
 * How long can a peer be inactive before we tiem it out?
 */
#define MAINTAIN_PEER_TIMEOUT MAINTAIN_FREQUENCY * MAINTAIN_CHANCE * 4

/**
 * What is the maximum number of known DHT-enabled peers
 * advertised for each DISCOVERY message?
 */
#define MAINTAIN_ADV_CAP 8

/**
 * Target number of peers per bucket
 */
#define MAINTAIN_BUCKET_SIZE 4


/**
 * Per-peer information.
 */
typedef struct
{

  /**
   * What was the last time we received a message from this peer?
   */
  GNUNET_CronTime lastActivity;

  /**
   * What was the last time we send a PING to this peer?
   */
  GNUNET_CronTime lastTimePingSend;

  /**
   * What is the average latency for replies received?
   */
  GNUNET_CronTime expected_latency;

  /**
   * Number of responses received
   */
  unsigned long long response_count;

  /**
   * Number of requests sent
   */
  unsigned long long request_count;

  /**
   * What is the identity of the peer?
   */
  GNUNET_PeerIdentity id;

} PeerInfo;

/**
 * Peers are grouped into buckets.
 */
typedef struct
{

  /**
   * Peers in this bucket.  NULL is used if no peer is known.
   */
  PeerInfo **peers;

  /**
   * Peers in this bucket fall into the distance-range
   * (2^bstart to 2^bend].
   */
  unsigned int bstart;

  /**
   * Peers in this bucket fall into the distance-range
   * (2^bstart to 2^bend].
   */
  unsigned int bend;

  unsigned int peers_size;

} PeerBucket;

/**
 * Global core API.
 */
static GNUNET_CoreAPIForPlugins *coreAPI;

/**
 * The buckets (Kademlia style routing table).
 */
static PeerBucket *buckets;

/**
 * Total number of active buckets.
 */
static unsigned int bucketCount;

/**
 * Total number of peers in routing table.
 */
static unsigned int total_peers;

/**
 * Mutex to synchronize access to tables.
 */
static struct GNUNET_Mutex *lock;

/**
 * Identity service.
 */
static GNUNET_Identity_ServiceAPI *identity;

/**
 * Statistics service.
 */
static GNUNET_Stats_ServiceAPI *stats;

/**
 * Pingpong service.
 */
static GNUNET_Pingpong_ServiceAPI *pingpong;

static int stat_dht_total_peers;

static int stat_dht_discoveries;

static int stat_dht_route_looks;

static int stat_dht_advertisements;

/**
 * The struct is followed by zero or more
 * PeerIdentities that the sender knows to
 * be participating in the DHT.
 */
typedef struct
{

  GNUNET_MessageHeader header;

  unsigned int space_available;

} P2P_DHT_Discovery;

/**
 * Request for a HELLO for another peer that is participating in the
 * DHT.  Receiver is expected to send back a HELLO for the peer that
 * is being requested.
 */
typedef struct
{

  GNUNET_MessageHeader header;

  unsigned int reserved;

  GNUNET_PeerIdentity peer;

} P2P_DHT_ASK_HELLO;

/**
 * Compute a (rough) estimate of the networks diameter.
 *
 * @return estimated network diameter
 */
unsigned int
GNUNET_DHT_estimate_network_diameter ()
{
  unsigned int i;
  for (i = bucketCount - 1; i > 0; i--)
    {
      if (buckets[i].peers_size > 0)
        break;
    }
  return i + 1;
}

/**
 * Get the index of the lowest bit of the two GNUNET_hash codes that
 * differs.
 */
static unsigned int
get_bit_distance (const GNUNET_HashCode * h1, const GNUNET_HashCode * h2)
{
  unsigned int i;
  int diff;

  for (i = 0; i < sizeof (GNUNET_HashCode) * 8; i++)
    {
      diff = GNUNET_hash_get_bit (h1, i) - GNUNET_hash_get_bit (h2, i);
      if (diff != 0)
        return i;
    }
  return sizeof (GNUNET_HashCode) * 8;
}

/**
 * @return NULL if peer is the current host
 */
static PeerBucket *
findBucketFor (const GNUNET_PeerIdentity * peer)
{
  unsigned int index;
  int i;

  if (0 == memcmp (peer, coreAPI->my_identity, sizeof (GNUNET_PeerIdentity)))
    return NULL;                /* myself! */
  index = get_bit_distance (&peer->hashPubKey,
                            &coreAPI->my_identity->hashPubKey);
  i = bucketCount - 1;
  while ((buckets[i].bstart >= index) && (i > 0))
    i--;
  if ((buckets[i].bstart <= index) && (buckets[i].bend >= index))
    return &buckets[i];
  GNUNET_GE_BREAK (NULL, 0);
  return NULL;
}

/**
 * Find the PeerInfo for the given peer. Returns NULL if peer is not
 * in our DHT routing table.
 */
static PeerInfo *
findPeerEntryInBucket (PeerBucket * bucket, const GNUNET_PeerIdentity * peer)
{
  unsigned int i;

  if (bucket == NULL)
    return NULL;
  for (i = 0; i < bucket->peers_size; i++)
    if (0 ==
        memcmp (peer, &bucket->peers[i]->id, sizeof (GNUNET_PeerIdentity)))
      return bucket->peers[i];
  return NULL;
}

/**
 * Find the PeerInfo for the given peer. Returns NULL if peer is not
 * in our DHT routing table.
 */
static PeerInfo *
findPeerEntry (const GNUNET_PeerIdentity * peer)
{
  return findPeerEntryInBucket (findBucketFor (peer), peer);
}

/**
 * Return a number that is the larger the closer the
 * "have" GNUNET_hash code is to the "target".  The basic
 * idea is that if "have" would be in the n-th lowest
 * bucket of "target", the returned value should be
 * 2^n.  However, the largest number we can return
 * is 2^31, so this number may have to be scaled.
 *
 * @return inverse distance metric, non-zero.
 */
static unsigned int
inverse_distance (const GNUNET_HashCode * target,
                  const GNUNET_HashCode * have)
{
  unsigned int bucket;
  double d;

  bucket = get_bit_distance (target, have);
  d = bucket * 32;
  d = exp2 (d / (sizeof (GNUNET_HashCode) * 8));
  if (d > ((unsigned int) -1))
    return -1;
  return (unsigned int) d;
}

/**
 * Select a peer from the routing table that would be a good routing
 * destination for sending a message for "target".  The resulting peer
 * must not be in the set of blocked peers.<p>
 *
 * Note that we should not ALWAYS select the closest peer to the
 * target, peers further away from the target should be chosen with
 * exponentially declining probability (this function is also used for
 * populating the target's routing table).
 *
 * @return GNUNET_OK on success, GNUNET_SYSERR on error
 */
int
GNUNET_DHT_select_peer (GNUNET_PeerIdentity * set,
                        const GNUNET_HashCode * target,
                        const GNUNET_PeerIdentity * blocked,
                        unsigned int blocked_size)
{
  unsigned long long total_distance;
  unsigned long long selected;
  unsigned int distance;
  unsigned int bc;
  unsigned int ec;
  unsigned int i;
  int match;
  const PeerBucket *bucket;
  const PeerInfo *pi;

  GNUNET_mutex_lock (lock);
  if (stats != NULL)
    stats->change (stat_dht_route_looks, 1);
  total_distance = 0;
  for (bc = 0; bc < bucketCount; bc++)
    {
      bucket = &buckets[bc];
      for (ec = 0; ec < bucket->peers_size; ec++)
        {
          pi = bucket->peers[ec];
          match = GNUNET_NO;
          for (i = 0; i < blocked_size; i++)
            {
              if (0 ==
                  memcmp (&pi->id, &blocked[i], sizeof (GNUNET_PeerIdentity)))
                {
                  match = GNUNET_YES;
                  break;
                }
            }
          if (match == GNUNET_YES)
            continue;
          total_distance += inverse_distance (target, &pi->id.hashPubKey);
        }
    }
  if (total_distance == 0)
    {
      GNUNET_mutex_unlock (lock);
      return GNUNET_SYSERR;
    }
  selected = GNUNET_random_u64 (GNUNET_RANDOM_QUALITY_WEAK, total_distance);
  for (bc = 0; bc < bucketCount; bc++)
    {
      bucket = &buckets[bc];
      for (ec = 0; ec < bucket->peers_size; ec++)
        {
          pi = bucket->peers[ec];
          match = GNUNET_NO;
          for (i = 0; i < blocked_size; i++)
            {
              if (0 ==
                  memcmp (&pi->id, &blocked[i], sizeof (GNUNET_PeerIdentity)))
                {
                  match = GNUNET_YES;
                  break;
                }
            }
          if (match == GNUNET_YES)
            continue;
          distance = inverse_distance (target, &pi->id.hashPubKey);
          if (distance > selected)
            {
              *set = pi->id;
              GNUNET_mutex_unlock (lock);