plugin_datacache_heap.c File Reference

heap-only implementation of a database backend for the datacache More...

#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_datacache_plugin.h"

Include dependency graph for plugin_datacache_heap.c:

Go to the source code of this file.

Data Structures
struct	Plugin
	Handle for a plugin. More...
struct	Value
	Entry in the hash map. More...
struct	PutContext
	Closure for put_cb(). More...
struct	GetContext
	Closure for get_cb(). More...
struct	GetClosestContext
	Closure for find_closest(). More...

Macros
#define	LOG(kind, ...)   GNUNET_log_from (kind, "datacache-heap", __VA_ARGS__)
#define	LOG_STRERROR_FILE(kind, op, fn)
#define	NUM_HEAPS   24
#define	OVERHEAD   (sizeof(struct Value) + 64)

Functions
static enum GNUNET_GenericReturnValue	put_cb (void *cls, const struct GNUNET_HashCode *key, void *value)
	Function called during PUT to detect if an equivalent block already exists. More...
static ssize_t	heap_plugin_put (void *cls, uint32_t xor_distance, const struct GNUNET_DATACACHE_Block *block)
	Store an item in the datastore. More...
static enum GNUNET_GenericReturnValue	get_cb (void *cls, const struct GNUNET_HashCode *key, void *value)
	Function called during GET to find matching blocks. More...
static unsigned int	heap_plugin_get (void *cls, const struct GNUNET_HashCode *key, enum GNUNET_BLOCK_Type type, GNUNET_DATACACHE_Iterator iter, void *iter_cls)
	Iterate over the results for a particular key in the datastore. More...
static enum GNUNET_GenericReturnValue	heap_plugin_del (void *cls)
	Delete the entry with the lowest expiration value from the datacache right now. More...
static enum GNUNET_GenericReturnValue	find_closest (void *cls, const struct GNUNET_HashCode *key, void *value)
static unsigned int	heap_plugin_get_closest (void *cls, const struct GNUNET_HashCode *key, enum GNUNET_BLOCK_Type type, unsigned int num_results, GNUNET_DATACACHE_Iterator iter, void *iter_cls)
	Iterate over the results that are "close" to a particular key in the datacache. More...
void *	libgnunet_plugin_datacache_heap_init (void *cls)
	Entry point for the plugin. More...
void *	libgnunet_plugin_datacache_heap_done (void *cls)
	Exit point from the plugin. More...

Detailed Description

heap-only implementation of a database backend for the datacache

Author

Christian Grothoff

Definition in file plugin_datacache_heap.c.

Macro Definition Documentation

LOG

#define LOG	(		kind,
			...
	)		GNUNET_log_from (kind, "datacache-heap", __VA_ARGS__)

Definition at line 30 of file plugin_datacache_heap.c.

LOG_STRERROR_FILE

#define LOG_STRERROR_FILE	(		kind,
			op,
			fn
	)

Value:

                                                                       GNUNET_log_from_strerror_file (kind, \
                                                                       "datacache-heap", \
                                                                       op, fn)

Definition at line 32 of file plugin_datacache_heap.c.

NUM_HEAPS

#define NUM_HEAPS   24

Definition at line 36 of file plugin_datacache_heap.c.

OVERHEAD

#define OVERHEAD   (sizeof(struct Value) + 64)

Definition at line 88 of file plugin_datacache_heap.c.

Function Documentation

put_cb()

static enum GNUNET_GenericReturnValue put_cb ( void *  cls, const struct GNUNET_HashCode *  key, void *  value  )

static

Function called during PUT to detect if an equivalent block already exists.

Parameters

cls	the struct PutContext
key	the key for the value(s)
value	an existing value

Returns

GNUNET_YES if not found (to continue to iterate)

Definition at line 118 of file plugin_datacache_heap.c.

{
  struct PutContext *put_ctx = cls;
  struct Value *val = value;
 
  if ((val->block.data_size == put_ctx->block->data_size) &&
      (val->block.type == put_ctx->block->type) &&
      (0 == memcmp (val->block.data,
                    put_ctx->block->data,
                    put_ctx->block->data_size)))
  {
    put_ctx->found = true;
    val->block.expiration_time
      = GNUNET_TIME_absolute_max (val->block.expiration_time,
                                  put_ctx->block->expiration_time);
    /* replace old path with new path */
    GNUNET_free (val->put_path);
    val->put_path = GNUNET_memdup (put_ctx->block->put_path,
                                   put_ctx->block->put_path_length
                                   * sizeof (struct GNUNET_DHT_PathElement));
    val->block.put_path = val->put_path;
    val->block.put_path_length = put_ctx->block->put_path_length;
    GNUNET_CONTAINER_heap_update_cost (val->hn,
                                       val->block.expiration_time.abs_value_us);
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                "Got same value for key %s and type %u (size %u vs %u)\n",
                GNUNET_h2s (key),
                (unsigned int) val->block.type,
                (unsigned int) val->block.data_size,
                (unsigned int) put_ctx->block->data_size);
    return GNUNET_NO;
  }
  return GNUNET_YES;
}

References GNUNET_TIME_Absolute::abs_value_us, Value::block, PutContext::block, GNUNET_DATACACHE_Block::data, GNUNET_DATACACHE_Block::data_size, GNUNET_DATACACHE_Block::expiration_time, PutContext::found, GNUNET_CONTAINER_heap_update_cost(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, GNUNET_h2s(), GNUNET_log, GNUNET_memdup, GNUNET_NO, GNUNET_TIME_absolute_max(), GNUNET_YES, Value::hn, key, GNUNET_DATACACHE_Block::put_path, Value::put_path, GNUNET_DATACACHE_Block::put_path_length, GNUNET_DATACACHE_Block::type, and value.

Referenced by heap_plugin_put().

Here is the call graph for this function:

Here is the caller graph for this function:

heap_plugin_put()

static ssize_t heap_plugin_put ( void *  cls, uint32_t  xor_distance, const struct GNUNET_DATACACHE_Block *  block  )

static

Store an item in the datastore.

Parameters

cls	closure (our struct Plugin)
xor_distance	how close is key to our PID?
block	data to store

Returns

0 if duplicate, -1 on error, number of bytes used otherwise

Definition at line 165 of file plugin_datacache_heap.c.

{
  struct Plugin *plugin = cls;
  struct Value *val;
  struct PutContext put_ctx = {
    .block = block,
    .found = false
  };
 
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "Storing %u bytes under key %s with path length %u\n",
              (unsigned int) block->data_size,
              GNUNET_h2s (&block->key),
              block->put_path_length);
  GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
                                              &block->key,
                                              &put_cb,
                                              &put_ctx);
  if (GNUNET_YES == put_ctx.found)
    return 0;
  val = GNUNET_malloc (sizeof(struct Value)
                       + block->data_size);
  GNUNET_memcpy (&val[1],
                 block->data,
                 block->data_size);
  val->block = *block;
  val->block.data = &val[1];
  if (xor_distance >= NUM_HEAPS)
    val->distance = NUM_HEAPS - 1;
  else
    val->distance = xor_distance;
  if (0 != block->put_path_length)
  {
    val->put_path
      = GNUNET_memdup (block->put_path,
                       block->put_path_length
                       * sizeof (struct GNUNET_DHT_PathElement));
    val->block.put_path = val->put_path;
  }
  (void) GNUNET_CONTAINER_multihashmap_put (plugin->map,
                                            &val->block.key,
                                            val,
                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
  val->hn = GNUNET_CONTAINER_heap_insert (
    plugin->heaps[val->distance],
    val,
    val->block.expiration_time.abs_value_us);
  return val->block.data_size + OVERHEAD;
}

References GNUNET_TIME_Absolute::abs_value_us, Value::block, PutContext::block, GNUNET_DATACACHE_Block::data, GNUNET_DATACACHE_Block::data_size, Value::distance, GNUNET_DATACACHE_Block::expiration_time, PutContext::found, GNUNET_CONTAINER_heap_insert(), GNUNET_CONTAINER_multihashmap_get_multiple(), GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE, GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_malloc, GNUNET_memcpy, GNUNET_memdup, GNUNET_YES, Value::hn, GNUNET_DATACACHE_Block::key, NUM_HEAPS, OVERHEAD, plugin, put_cb(), GNUNET_DATACACHE_Block::put_path, Value::put_path, and GNUNET_DATACACHE_Block::put_path_length.

Referenced by libgnunet_plugin_datacache_heap_init().

Here is the call graph for this function:

Here is the caller graph for this function:

get_cb()

static enum GNUNET_GenericReturnValue get_cb ( void *  cls, const struct GNUNET_HashCode *  key, void *  value  )

static

Function called during GET to find matching blocks.

Only matches by type.

Parameters

cls	the struct GetContext
key	the key for the value(s)
value	an existing value

Returns

GNUNET_YES to continue to iterate

Definition at line 255 of file plugin_datacache_heap.c.

{
  struct GetContext *get_ctx = cls;
  struct Value *val = value;
  enum GNUNET_GenericReturnValue ret;
 
  if ( (get_ctx->type != val->block.type) &&
       (GNUNET_BLOCK_TYPE_ANY != get_ctx->type) )
  {
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                "Result for key %s does not match block type %d\n",
                GNUNET_h2s (key),
                get_ctx->type);
    return GNUNET_OK;
  }
  if (GNUNET_TIME_absolute_is_past (val->block.expiration_time))
  {
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                "Result for key %s is expired\n",
                GNUNET_h2s (key));
    return GNUNET_OK;
  }
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "Found result for key %s\n",
              GNUNET_h2s (key));
  if (NULL != get_ctx->iter)
    ret = get_ctx->iter (get_ctx->iter_cls,
                         &val->block);
  else
    ret = GNUNET_YES;
  get_ctx->cnt++;
  return ret;
}

References Value::block, GetContext::cnt, GNUNET_DATACACHE_Block::expiration_time, GNUNET_BLOCK_TYPE_ANY, GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_OK, GNUNET_TIME_absolute_is_past(), GNUNET_YES, GetContext::iter, GetContext::iter_cls, key, ret, GNUNET_DATACACHE_Block::type, GetContext::type, and value.

Referenced by heap_plugin_get().

Here is the call graph for this function:

Here is the caller graph for this function:

heap_plugin_get()

static unsigned int heap_plugin_get ( void *  cls, const struct GNUNET_HashCode *  key, enum GNUNET_BLOCK_Type  type, GNUNET_DATACACHE_Iterator  iter, void *  iter_cls  )

static

Iterate over the results for a particular key in the datastore.

Parameters

cls	closure (our struct Plugin)
key
type	entries of which type are relevant?
iter	maybe NULL (to just count)
iter_cls	closure for iter

Returns

the number of results found

Definition at line 304 of file plugin_datacache_heap.c.

{
  struct Plugin *plugin = cls;
  struct GetContext get_ctx;
 
  get_ctx.type = type;
  get_ctx.iter = iter;
  get_ctx.iter_cls = iter_cls;
  get_ctx.cnt = 0;
  GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
                                              key,
                                              &get_cb,
                                              &get_ctx);
  return get_ctx.cnt;
}

References GetContext::cnt, get_cb(), GNUNET_CONTAINER_multihashmap_get_multiple(), GetContext::iter, GetContext::iter_cls, key, plugin, type, and GetContext::type.

Referenced by libgnunet_plugin_datacache_heap_init().

Here is the call graph for this function:

Here is the caller graph for this function:

heap_plugin_del()

static enum GNUNET_GenericReturnValue heap_plugin_del ( void *  cls )

static

Delete the entry with the lowest expiration value from the datacache right now.

Parameters

cls	closure (our struct Plugin)

Returns

GNUNET_OK on success, GNUNET_SYSERR on error

Definition at line 333 of file plugin_datacache_heap.c.

{
  struct Plugin *plugin = cls;
  struct Value *val;
 
  for (unsigned int i = 0; i < NUM_HEAPS; i++)
  {
    val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i]);
    if (NULL != val)
      break;
  }
  if (NULL == val)
    return GNUNET_SYSERR;
  GNUNET_assert (GNUNET_YES ==
                 GNUNET_CONTAINER_multihashmap_remove (plugin->map,
                                                       &val->block.key,
                                                       val));
  plugin->env->delete_notify (plugin->env->cls,
                              &val->block.key,
                              val->block.data_size + OVERHEAD);
  GNUNET_free (val->put_path);
  GNUNET_free (val);
  return GNUNET_OK;
}

References Value::block, GNUNET_TESTING_PluginFunctions::cls, GNUNET_DATACACHE_Block::data_size, GNUNET_assert, GNUNET_CONTAINER_heap_remove_root(), GNUNET_CONTAINER_multihashmap_remove(), GNUNET_free, GNUNET_OK, GNUNET_SYSERR, GNUNET_YES, GNUNET_DATACACHE_Block::key, NUM_HEAPS, OVERHEAD, plugin, and Value::put_path.

Referenced by libgnunet_plugin_datacache_heap_init().

Here is the call graph for this function:

Here is the caller graph for this function:

find_closest()

static enum GNUNET_GenericReturnValue find_closest ( void *  cls, const struct GNUNET_HashCode *  key, void *  value  )

static

Definition at line 376 of file plugin_datacache_heap.c.

{
  struct GetClosestContext *gcc = cls;
  struct Value *val = value;
  unsigned int j;
 
  if (1 != GNUNET_CRYPTO_hash_cmp (key,
                                   gcc->key))
    return GNUNET_OK; /* useless */
  if ( (val->block.type != gcc->type) &&
       (GNUNET_BLOCK_TYPE_ANY != gcc->type) )
    return GNUNET_OK; /* useless */
  j = gcc->num_results;
  for (unsigned int i = 0; i < gcc->num_results; i++)
  {
    if (NULL == gcc->values[i])
    {
      j = i;
      break;
    }
    if (1 ==
        GNUNET_CRYPTO_hash_cmp (&gcc->values[i]->block.key,
                                key))
    {
      j = i;
      break;
    }
  }
  if (j == gcc->num_results)
    return GNUNET_OK;
  gcc->values[j] = val;
  return GNUNET_OK;
}

References Value::block, GNUNET_BLOCK_TYPE_ANY, GNUNET_CRYPTO_hash_cmp(), GNUNET_OK, key, GNUNET_DATACACHE_Block::key, GetClosestContext::key, GetClosestContext::num_results, GNUNET_DATACACHE_Block::type, GetClosestContext::type, value, and GetClosestContext::values.

Referenced by heap_plugin_get_closest().

Here is the call graph for this function:

Here is the caller graph for this function:

heap_plugin_get_closest()

static unsigned int heap_plugin_get_closest ( void *  cls, const struct GNUNET_HashCode *  key, enum GNUNET_BLOCK_Type  type, unsigned int  num_results, GNUNET_DATACACHE_Iterator  iter, void *  iter_cls  )

static

Iterate over the results that are "close" to a particular key in the datacache.

"close" is defined as numerically larger than key (when interpreted as a circular address space), with small distance.

Parameters

cls	closure (internal context for the plugin)
key	area of the keyspace to look into
type	desired block type for the replies
num_results	number of results that should be returned to iter
iter	maybe NULL (to just count)
iter_cls	closure for iter

Returns

the number of results found

Definition at line 428 of file plugin_datacache_heap.c.

{
  struct Plugin *plugin = cls;
  struct Value *values[num_results];
  struct GetClosestContext gcc = {
    .values = values,
    .type = type,
    .num_results = num_results * 2,
    .key = key
  };
 
  GNUNET_CONTAINER_multihashmap_iterate (plugin->map,
                                         &find_closest,
                                         &gcc);
  for (unsigned int i = 0; i < num_results * 2; i++)
  {
    if (NULL == values[i])
      return i;
    if ( (NULL != iter) &&
         (GNUNET_SYSERR ==
          iter (iter_cls,
                &values[i]->block)) )
    {
      LOG (GNUNET_ERROR_TYPE_DEBUG,
           "Ending iteration (client error)\n");
      return i;
    }
  }
  return num_results * 2;
}

References find_closest(), GNUNET_CONTAINER_multihashmap_iterate(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_SYSERR, key, LOG, GetClosestContext::num_results, plugin, type, values, and GetClosestContext::values.

Referenced by libgnunet_plugin_datacache_heap_init().

Here is the call graph for this function:

Here is the caller graph for this function:

libgnunet_plugin_datacache_heap_init()

void * libgnunet_plugin_datacache_heap_init

(

void *

cls

)

Entry point for the plugin.

Parameters

cls	closure (the struct GNUNET_DATACACHE_PluginEnvironmnet)

Returns

the plugin's closure (our struct Plugin)

Definition at line 474 of file plugin_datacache_heap.c.

{
  struct GNUNET_DATACACHE_PluginEnvironment *env = cls;
  struct GNUNET_DATACACHE_PluginFunctions *api;
  struct Plugin *plugin;
 
  plugin = GNUNET_new (struct Plugin);
  plugin->map = GNUNET_CONTAINER_multihashmap_create (1024,   /* FIXME: base on quota! */
                                                      GNUNET_YES);
  for (unsigned int i = 0; i < NUM_HEAPS; i++)
    plugin->heaps[i] = GNUNET_CONTAINER_heap_create (
      GNUNET_CONTAINER_HEAP_ORDER_MIN);
  plugin->env = env;
  api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions);
  api->cls = plugin;
  api->get = &heap_plugin_get;
  api->put = &heap_plugin_put;
  api->del = &heap_plugin_del;
  api->get_closest = &heap_plugin_get_closest;
  LOG (GNUNET_ERROR_TYPE_INFO,
       _ ("Heap datacache running\n"));
  return api;
}

References _, Plugin::api, GNUNET_BLOCK_PluginFunctions::cls, GNUNET_DATACACHE_PluginEnvironment::cls, env, GNUNET_CONTAINER_heap_create(), GNUNET_CONTAINER_HEAP_ORDER_MIN, GNUNET_CONTAINER_multihashmap_create(), GNUNET_ERROR_TYPE_INFO, GNUNET_new, GNUNET_YES, heap_plugin_del(), heap_plugin_get(), heap_plugin_get_closest(), heap_plugin_put(), LOG, NUM_HEAPS, and plugin.

Here is the call graph for this function:

libgnunet_plugin_datacache_heap_done()

void * libgnunet_plugin_datacache_heap_done

(

void *

cls

)

Exit point from the plugin.

Parameters

cls	closure (our "struct Plugin")

Returns

NULL

Definition at line 508 of file plugin_datacache_heap.c.

{
  struct GNUNET_DATACACHE_PluginFunctions *api = cls;
  struct Plugin *plugin = api->cls;
  struct Value *val;
 
  for (unsigned int i = 0; i < NUM_HEAPS; i++)
  {
    while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i])))
    {
      GNUNET_assert (GNUNET_YES ==
                     GNUNET_CONTAINER_multihashmap_remove (plugin->map,
                                                           &val->block.key,
                                                           val));
      GNUNET_free (val->put_path);
      GNUNET_free (val);
    }
    GNUNET_CONTAINER_heap_destroy (plugin->heaps[i]);
  }
  GNUNET_CONTAINER_multihashmap_destroy (plugin->map);
  GNUNET_free (plugin);
  GNUNET_free (api);
  return NULL;
}

References Plugin::api, Value::block, GNUNET_BLOCK_PluginFunctions::cls, GNUNET_DATACACHE_PluginFunctions::cls, GNUNET_assert, GNUNET_CONTAINER_heap_destroy(), GNUNET_CONTAINER_heap_remove_root(), GNUNET_CONTAINER_multihashmap_destroy(), GNUNET_CONTAINER_multihashmap_remove(), GNUNET_free, GNUNET_YES, GNUNET_DATACACHE_Block::key, NUM_HEAPS, plugin, and Value::put_path.

Here is the call graph for this function: