Imported Upstream version 0.9.2upstream/0.9.2

1 files changed, 383 insertions, 0 deletions

diff --git a/src/dht/gnunet-service-dht_routing.c b/src/dht/gnunet-service-dht_routing.c
new file mode 100644
index 0000000..a880bf7
--- /dev/null
+++ b/src/dht/gnunet-service-dht_routing.c
@@ -0,0 +1,383 @@
+/*
+     This file is part of GNUnet.
+     (C) 2011 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 3, 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 dht/gnunet-service-dht_routing.c
+ * @brief GNUnet DHT tracking of requests for routing replies
+ * @author Christian Grothoff
+ */
+#include "platform.h"
+#include "gnunet-service-dht_neighbours.h"
+#include "gnunet-service-dht_routing.h"
+#include "gnunet-service-dht.h"
+
+
+/**
+ * Number of requests we track at most (for routing replies).
+ */
+#define DHT_MAX_RECENT (1024 * 16)
+
+
+/**
+ * Information we keep about all recent GET requests
+ * so that we can route replies.
+ */
+struct RecentRequest
+{
+
+  /**
+   * The peer this request was received from.
+   */
+  struct GNUNET_PeerIdentity peer;
+
+  /**
+   * Key of this request.
+   */
+  GNUNET_HashCode key;
+
+  /**
+   * Position of this node in the min heap.
+   */
+  struct GNUNET_CONTAINER_HeapNode *heap_node;
+
+  /**
+   * Bloomfilter for replies to drop.
+   */
+  struct GNUNET_CONTAINER_BloomFilter *reply_bf;
+
+  /**
+   * Type of the requested block.
+   */
+  enum GNUNET_BLOCK_Type type;
+
+  /**
+   * extended query (see gnunet_block_lib.h).  Allocated at the
+   * end of this struct.
+   */
+  const void *xquery;
+
+  /**
+   * Number of bytes in xquery.
+   */
+  size_t xquery_size;
+
+  /**
+   * Mutator value for the reply_bf, see gnunet_block_lib.h
+   */
+  uint32_t reply_bf_mutator;
+
+  /**
+   * Request options.
+   */
+  enum GNUNET_DHT_RouteOption options;
+
+};
+
+
+/**
+ * Recent requests by time inserted.
+ */
+static struct GNUNET_CONTAINER_Heap *recent_heap;
+
+/**
+ * Recently seen requests by key.
+ */
+static struct GNUNET_CONTAINER_MultiHashMap *recent_map;
+
+
+/**
+ * Closure for the 'process' function.
+ */
+struct ProcessContext
+{
+  /**
+   * Path of the original PUT
+   */
+  const struct GNUNET_PeerIdentity *put_path;
+
+  /**
+   * Path of the reply.
+   */
+  const struct GNUNET_PeerIdentity *get_path;
+
+  /**
+   * Payload of the reply.
+   */
+  const void *data;
+
+  /**
+   * Expiration time of the result.
+   */
+  struct GNUNET_TIME_Absolute expiration_time;
+
+  /**
+   * Number of entries in 'put_path'.
+   */
+  unsigned int put_path_length;
+
+  /**
+   * Number of entries in 'get_path'.
+   */
+  unsigned int get_path_length;
+
+  /**
+   * Number of bytes in 'data'.
+   */
+  size_t data_size;
+
+  /**
+   * Type of the reply.
+   */
+  enum GNUNET_BLOCK_Type type;
+
+};
+
+
+/**
+ * Forward the result to the given peer if it matches the request.
+ *
+ * @param cls the 'struct ProcessContext' with the result
+ * @param key the query
+ * @param value the 'struct RecentRequest' with the request
+ * @return GNUNET_OK (continue to iterate),
+ *         GNUNET_SYSERR if the result is malformed or type unsupported
+ */
+static int
+process (void *cls, const GNUNET_HashCode * key, void *value)
+{
+  struct ProcessContext *pc = cls;
+  struct RecentRequest *rr = value;
+  enum GNUNET_BLOCK_EvaluationResult eval;
+  unsigned int gpl;
+  unsigned int ppl;
+  GNUNET_HashCode hc;
+  const GNUNET_HashCode *eval_key;
+
+  if ((rr->type != GNUNET_BLOCK_TYPE_ANY) && (rr->type != pc->type))
+    return GNUNET_OK;           /* type missmatch */
+
+  if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
+  {
+    gpl = pc->get_path_length;
+    ppl = pc->put_path_length;
+  }
+  else
+  {
+    gpl = 0;
+    ppl = 0;
+  }
+  if ((0 != (rr->options & GNUNET_DHT_RO_FIND_PEER)) &&
+      (pc->type == GNUNET_BLOCK_TYPE_DHT_HELLO))
+  {
+    /* key may not match HELLO, which is OK since
+     * the search is approximate.  Still, the evaluation
+     * would fail since the match is not exact.  So
+     * we fake it by changing the key to the actual PID ... */
+    GNUNET_BLOCK_get_key (GDS_block_context, GNUNET_BLOCK_TYPE_DHT_HELLO,
+                          pc->data, pc->data_size, &hc);
+    eval_key = &hc;
+  }
+  else
+  {
+    eval_key = key;
+  }
+  eval =
+      GNUNET_BLOCK_evaluate (GDS_block_context, pc->type, eval_key,
+                             &rr->reply_bf, rr->reply_bf_mutator, rr->xquery,
+                             rr->xquery_size, pc->data, pc->data_size);
+  switch (eval)
+  {
+  case GNUNET_BLOCK_EVALUATION_OK_MORE:
+  case GNUNET_BLOCK_EVALUATION_OK_LAST:
+    GNUNET_STATISTICS_update (GDS_stats,
+                              gettext_noop
+                              ("# Good REPLIES matched against routing table"),
+                              1, GNUNET_NO);
+    GDS_NEIGHBOURS_handle_reply (&rr->peer, pc->type, pc->expiration_time, key,
+                                 ppl, pc->put_path, gpl, pc->get_path, pc->data,
+                                 pc->data_size);
+    break;
+  case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
+    GNUNET_STATISTICS_update (GDS_stats,
+                              gettext_noop
+                              ("# Duplicate REPLIES matched against routing table"),
+                              1, GNUNET_NO);
+    return GNUNET_OK;
+  case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
+    GNUNET_STATISTICS_update (GDS_stats,
+                              gettext_noop
+                              ("# Invalid REPLIES matched against routing table"),
+                              1, GNUNET_NO);
+    return GNUNET_SYSERR;
+  case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
+  case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
+    GNUNET_break (0);
+    return GNUNET_OK;
+  case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
+    GNUNET_STATISTICS_update (GDS_stats,
+                              gettext_noop
+                              ("# Unsupported REPLIES matched against routing table"),
+                              1, GNUNET_NO);
+    return GNUNET_SYSERR;
+  default:
+    GNUNET_break (0);
+    return GNUNET_SYSERR;
+  }
+  return GNUNET_OK;
+}
+
+
+/**
+ * Handle a reply (route to origin).  Only forwards the reply back to
+ * other peers waiting for it.  Does not do local caching or
+ * forwarding to local clients.  Essentially calls
+ * GDS_NEIGHBOURS_handle_reply for all peers that sent us a matching
+ * request recently.
+ *
+ * @param type type of the block
+ * @param expiration_time when does the content expire
+ * @param key key for the content
+ * @param put_path_length number of entries in put_path
+ * @param put_path peers the original PUT traversed (if tracked)
+ * @param get_path_length number of entries in put_path
+ * @param get_path peers this reply has traversed so far (if tracked)
+ * @param data payload of the reply
+ * @param data_size number of bytes in data
+ */
+void
+GDS_ROUTING_process (enum GNUNET_BLOCK_Type type,
+                     struct GNUNET_TIME_Absolute expiration_time,
+                     const GNUNET_HashCode * key, unsigned int put_path_length,
+                     const struct GNUNET_PeerIdentity *put_path,
+                     unsigned int get_path_length,
+                     const struct GNUNET_PeerIdentity *get_path,
+                     const void *data, size_t data_size)
+{
+  struct ProcessContext pc;
+
+  pc.type = type;
+  pc.expiration_time = expiration_time;
+  pc.put_path_length = put_path_length;
+  pc.put_path = put_path;
+  pc.get_path_length = get_path_length;
+  pc.get_path = get_path;
+  pc.data = data;
+  pc.data_size = data_size;
+  GNUNET_CONTAINER_multihashmap_get_multiple (recent_map, key, &process, &pc);
+}
+
+
+/**
+ * Add a new entry to our routing table.
+ *
+ * @param sender peer that originated the request
+ * @param type type of the block
+ * @param options options for processing
+ * @param key key for the content
+ * @param xquery extended query
+ * @param xquery_size number of bytes in xquery
+ * @param reply_bf bloomfilter to filter duplicates
+ * @param reply_bf_mutator mutator for reply_bf
+*/
+void
+GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
+                 enum GNUNET_BLOCK_Type type,
+                 enum GNUNET_DHT_RouteOption options,
+                 const GNUNET_HashCode * key, const void *xquery,
+                 size_t xquery_size,
+                 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
+                 uint32_t reply_bf_mutator)
+{
+  struct RecentRequest *recent_req;
+
+  while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
+  {
+    GNUNET_STATISTICS_update (GDS_stats,
+                              gettext_noop
+                              ("# Entries removed from routing table"), 1,
+                              GNUNET_NO);
+    recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
+    GNUNET_assert (recent_req != NULL);
+    GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
+    GNUNET_CONTAINER_bloomfilter_free (recent_req->reply_bf);
+    GNUNET_free (recent_req);
+  }
+
+  GNUNET_STATISTICS_update (GDS_stats,
+                            gettext_noop ("# Entries added to routing table"),
+                            1, GNUNET_NO);
+  recent_req = GNUNET_malloc (sizeof (struct RecentRequest) + xquery_size);
+  recent_req->peer = *sender;
+  recent_req->key = *key;
+  recent_req->heap_node =
+      GNUNET_CONTAINER_heap_insert (recent_heap, recent_req,
+                                    GNUNET_TIME_absolute_get ().abs_value);
+  recent_req->reply_bf = GNUNET_CONTAINER_bloomfilter_copy (reply_bf);
+  recent_req->type = type;
+  recent_req->options = options;
+  recent_req->xquery = &recent_req[1];
+  recent_req->xquery_size = xquery_size;
+  recent_req->reply_bf_mutator = reply_bf_mutator;
+  GNUNET_CONTAINER_multihashmap_put (recent_map, key, recent_req,
+                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
+
+
+}
+
+
+/**
+ * Initialize routing subsystem.
+ */
+void
+GDS_ROUTING_init ()
+{
+  recent_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
+  recent_map = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3);
+}
+
+
+/**
+ * Shutdown routing subsystem.
+ */
+void
+GDS_ROUTING_done ()
+{
+  struct RecentRequest *recent_req;
+
+  while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
+  {
+    GNUNET_STATISTICS_update (GDS_stats,
+                              gettext_noop
+                              ("# Entries removed from routing table"), 1,
+                              GNUNET_NO);
+    recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
+    GNUNET_assert (recent_req != NULL);
+    GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
+    GNUNET_CONTAINER_bloomfilter_free (recent_req->reply_bf);
+    GNUNET_free (recent_req);
+  }
+  GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent_heap));
+  GNUNET_CONTAINER_heap_destroy (recent_heap);
+  recent_heap = NULL;
+  GNUNET_CONTAINER_multihashmap_destroy (recent_map);
+  recent_map = NULL;
+}
+
+/* end of gnunet-service-dht_routing.c */