plan.c

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

/*
      This file is part of GNUnet
      (C) 2008 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., 51 Franklin Street, Fifth Floor,
      Boston, MA 02110-1301, USA.
 */

/**
 * @file fs/gap/plan.c
 * @brief code to plan when to send requests where
 * @author Christian Grothoff
 */

#include "platform.h"
#include <math.h>
#include "gnunet_protocols.h"
#include "gnunet_stats_service.h"
#include "plan.h"
#include "pid_table.h"
#include "fs_dht.h"
#include "fs.h"
#include "gap.h"
#include "shared.h"

/**
 * How many entires are we allowed to plan-ahead
 * per peer (at most)?
 */
#define MAX_ENTRIES_PER_PEER 64


/**
 * Linked list summarizing how good other peers
 * were at producing responses for a client.
 */
struct PeerHistoryList
{

  /**
   * This is a linked list.
   */
  struct PeerHistoryList *next;

  /**
   * Last time we transmitted a request to this peer.
   */
  GNUNET_CronTime last_request_time;

  /**
   * Last time we received a response from this peer.
   */
  GNUNET_CronTime last_response_time;

  /**
   * What peer is this history entry for?
   */
  PID_INDEX peer;

  /**
   * Total number of requests send to the peer so far.
   */
  unsigned int request_count;

  /**
   * Total number of replies received from this peer so far.
   */
  unsigned int response_count;

  /**
   * TTL value used for last successful request.
   */
  int last_good_ttl;

  /**
   * Priority value used for last successful request.
   */
  unsigned int last_good_prio;

  /**
   * (Relative) TTL used in the last request.
   */
  int last_ttl_used;

  /**
   * Priority used for the last request.
   */
  unsigned int last_prio_used;

};

/**
 * Linked list with information for each client.
 */
struct ClientInfoList
{

  /**
   * This is a linked list.
   */
  struct ClientInfoList *next;

  /**
   * For which client is this data kept (NULL
   * if the "client" is another peer).
   */
  struct GNUNET_ClientHandle *client;

  /**
   * List of the history of reactions of other peers
   * to queries from this client.
   */
  struct PeerHistoryList *history;

  /**
   * If "client" is NULL, this is the peer for
   * which this is the history.
   */
  PID_INDEX peer;

};

/**
 * Linked list of rankings given to connected peers.  This list is
 * used to determine which peers should be considered for forwarding
 * of the query.
 */
struct PeerRankings
{
  /**
   * This is a linked list.
   */
  struct PeerRankings *next;

  /**
   * Peer that is being ranked.
   */
  PID_INDEX peer;

  /**
   * Recommended priority for this peer.
   */
  unsigned int prio;

  /**
   * Recommended Time-to-live for this peer.
   */
  int ttl;

  /**
   * Client score (higher is better).
   */
  unsigned int score;

  /**
   * How much bandwidth were we able to
   * reserve from gnunetd (0 to 32k) for
   * responses to an eventual query.
   */
  int reserved_bandwidth;

};


static GNUNET_CoreAPIForPlugins *coreAPI;

/**
 * Plan for query execution (for each peer, a list of
 * requests and when we should consider transmitting
 * them).
 */
static struct QueryPlanList *queries;

/**
 * Information about the performance of peers
 * for requests from various clients.
 */
static struct ClientInfoList *clients;

/**
 * Log_e(2).
 */
static double LOG_2;

static GNUNET_Stats_ServiceAPI *stats;

static int stat_gap_query_sent;

static int stat_gap_query_planned;

static int stat_gap_query_success;

static int stat_trust_spent;

/**
 * Find the entry in the client list corresponding
 * to the given client information.  If no such entry
 * exists, create one.
 */
static struct ClientInfoList *
find_or_create_client_entry (struct GNUNET_ClientHandle *client,
                             PID_INDEX peer)
{
  struct ClientInfoList *cl;

  cl = clients;
  while (cl != NULL)
    {
      if (((cl->client != NULL) &&
           (cl->client == client)) || ((cl->peer != 0) && (cl->peer == peer)))
        break;
      cl = cl->next;
    }
  if (cl != NULL)
    return cl;
  cl = GNUNET_malloc (sizeof (struct ClientInfoList));
  memset (cl, 0, sizeof (struct ClientInfoList));
  cl->next = clients;
  clients = cl;
  cl->client = client;
  cl->peer = peer;
  GNUNET_FS_PT_change_rc (peer, 1);
  return cl;
}

/**
 * Find the entry in the history corresponding
 * to the given peer ID.  If no such entry
 * exists, create one.
 */
static struct PeerHistoryList *
find_or_create_history_entry (struct ClientInfoList *cl, PID_INDEX responder)
{
  struct PeerHistoryList *hl;

  hl = cl->history;
  while (hl != NULL)
    {
      if (hl->peer == responder)
        break;
      hl = hl->next;
    }
  if (hl != NULL)
    return hl;
  hl = GNUNET_malloc (sizeof (struct PeerHistoryList));
  memset (hl, 0, sizeof (struct PeerHistoryList));
  hl->next = cl->history;
  cl->history = hl;
  hl->peer = responder;
  GNUNET_FS_PT_change_rc (responder, 1);
  return hl;
}

struct QueryPlanList *
find_or_create_query_plan_list (PID_INDEX target)
{
  struct QueryPlanList *qpl;

  /* find query plan for target */
  qpl = queries;
  while ((qpl != NULL) && (qpl->peer != target))
    qpl = qpl->next;
  if (qpl == NULL)
    {
      qpl = GNUNET_malloc (sizeof (struct QueryPlanList));
      memset (qpl, 0, sizeof (struct QueryPlanList));
      qpl->peer = target;
      GNUNET_FS_PT_change_rc (target, 1);
      qpl->next = queries;
      queries = qpl;
    }
  return qpl;
}

static unsigned int
count_query_plan_entries (struct QueryPlanList *qpl)
{
  struct QueryPlanEntry *pos;
  unsigned int total;

  total = 0;
  pos = qpl->head;
  while (pos != NULL)
    {
      total++;
      pos = pos->next;
    }
  return total;
}

/**
 * Add the given request to the list of pending requests for the
 * specified target.  A random position in the queue will
 * be used.
 *
 * @param target what peer to send the request to
 * @param request the request to send
 * @param ttl time-to-live for the request
 * @param priority priority to use for the request
 */
static void
queue_request (PID_INDEX target,
               struct RequestList *request, int ttl, unsigned int prio)
{
  struct QueryPlanList *qpl;
  struct QueryPlanEntry *entry;
  struct QueryPlanEntry *pos;
  unsigned int total;

  /* find query plan for target */
  qpl = find_or_create_query_plan_list (target);
  /* construct entry */
  entry = GNUNET_malloc (sizeof (struct QueryPlanEntry));
  memset (entry, 0, sizeof (struct QueryPlanEntry));
  entry->request = request;
  entry->prio = prio;
  entry->ttl = GNUNET_FS_HELPER_bound_ttl (ttl, prio);
  entry->list = qpl;
  /* insert entry into request plan entries list */
  entry->plan_entries_next = request->plan_entries;
  request->plan_entries = entry;

  if (stats != NULL)
    stats->change (stat_gap_query_planned, 1);
  /* compute (random) insertion position in doubly-linked list */
  total = count_query_plan_entries (qpl);
  total = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, total + 1);
  pos = qpl->head;
  while (total-- > 0)
    pos = pos->next;
  /* insert into datastructure at pos */
  if (pos == NULL)
    {
      if (qpl->tail != NULL)
        qpl->tail->next = entry;
      else
        qpl->head = entry;
      entry->prev = qpl->tail;
      qpl->tail = entry;
    }
  else
    {
      entry->next = pos->next;
      if (pos->next == NULL)
        qpl->tail = entry;
      else
        pos->next->prev = entry;
      entry->prev = pos;
      pos->next = entry;
    }
}

/**
 * Closure for rank_peers callback function.
 */
struct RankingPeerContext
{
  struct PeerRankings *rankings;
  struct ClientInfoList *info;
  struct RequestList *request;
};

/**
 * Rank peers by their quality for a given
 * request (using history with client,
 * bandwidth availability, query proximity)
 *
 * @param identity the id of the node
 */
static void
rank_peers (const GNUNET_PeerIdentity * identity, void *data)
{
  struct RankingPeerContext *rpc = data;
  struct PeerRankings *rank;
  struct PeerHistoryList *history;
  long long history_score;
  unsigned int proximity_score;
  GNUNET_CronTime now;
  GNUNET_CronTime last;
  unsigned int prio;
  int ttl;
  unsigned int allowable_prio;
  long long score;
  PID_INDEX peer;

  peer = GNUNET_FS_PT_intern (identity);
  if ((peer == rpc->request->response_target) ||
      (count_query_plan_entries (find_or_create_query_plan_list (peer)) >
       MAX_ENTRIES_PER_PEER))
    {
      GNUNET_FS_PT_change_rc (peer, -1);
      return;                   /* ignore! */
    }
  rank = GNUNET_malloc (sizeof (struct PeerRankings));
  memset (rank, 0, sizeof (struct PeerRankings));
  rank->peer = peer;
  rank->reserved_bandwidth =
    coreAPI->p2p_bandwidth_downstream_reserve (identity,
                                               GNUNET_GAP_ESTIMATED_DATA_SIZE);
  history = NULL;
  if (rpc->info != NULL)
    {
      history = rpc->info->history;
      while ((history != NULL) && (history->peer != rank->peer))
        history = history->next;
    }
  now = GNUNET_get_time ();
  history_score = 0;            /* no bias from history */
  if ((history != NULL) && (history->request_count > 0))
    {
      last = history->last_response_time;
      if (last >= now)
        last = now - 1;
      /* the more responses we have in relation
         to the number of requests we sent, the
         higher we score; the score is the more
         significant the more recent the last
         response was */
      history_score
        =
        (GNUNET_GAP_MAX_GAP_DELAY * history->response_count) /
        (history->request_count * (now - last));
      if (history->response_count == 0)
        history_score =
          -history->request_count * coreAPI->p2p_connections_iterate (NULL,
                                                                      NULL);
      if (history_score > (1 << 30))
        history_score = (1 << 30);
    }
  /* check query proximity */
  proximity_score =
    GNUNET_hash_distance_u32 (&rpc->request->queries[0],
                              &identity->hashPubKey);

  /* generate score, ttl and priority */
  prio = rpc->request->last_prio_used + GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 2);      /* increase over time */
  if ((history != NULL) && (prio < history->last_good_prio))
    prio = history->last_good_prio - GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 2); /* fall over time */
  if (prio > 1)
    {
      allowable_prio = GNUNET_FS_GAP_get_average_priority () + 1;
      if (prio > allowable_prio)
        prio = allowable_prio;
    }
  if ((rpc->request->response_client == NULL) &&
      (prio > rpc->request->remaining_value))
    prio = rpc->request->remaining_value;
  if (prio > 0)
    {
      ttl = (1 << 30);          /* bound only by priority */
    }
  else
    {
      if (rpc->request->response_client != NULL)
        ttl = 0;                /* initiator expiration is always "now" */
      else
        {
          ttl =
            (int) (((long long) (rpc->request->expiration -
                                 now)) / (long long) GNUNET_CRON_SECONDS);
        }
      if (ttl < 0)
        {
          ttl -=
            GNUNET_GAP_TTL_DECREMENT +
            GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK,
                               2 * GNUNET_GAP_TTL_DECREMENT);
          if (ttl > 0)          /* integer underflow */
            ttl = -(1 << 30);
        }
      else
        {
          ttl -=
            GNUNET_GAP_TTL_DECREMENT +
            GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK,
                               2 * GNUNET_GAP_TTL_DECREMENT);
        }
    }
  ttl = GNUNET_FS_HELPER_bound_ttl (ttl, prio);
  rank->prio = prio;
  rank->ttl = ttl;

  /* compute combined score */
  /* open question: any good weights for the scoring? */
  score = history_score + rank->reserved_bandwidth - proximity_score;
  if (score <= -(1 << 16))
    {
      /* would underflow, use lowest legal score */
      rank->score = 1;
    }
  else
    {
      rank->score = (unsigned int) ((1 << 16) + score);
      if (rank->score < score)  /* integer overflow */
        rank->score = -1;       /* max int */