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)   GNUNET_log_from_strerror_file (kind, "datacache-heap", op, fn)
#define	NUM_HEAPS   24
#define	OVERHEAD   (sizeof (struct Value) + 64)

Functions
static int	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, const struct GNUNET_HashCode *key, uint32_t xor_distance, size_t size, const char *data, enum GNUNET_BLOCK_Type type, struct GNUNET_TIME_Absolute discard_time, unsigned int path_info_len, const struct GNUNET_PeerIdentity *path_info)
	Store an item in the datastore. More...
static int	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 int	heap_plugin_del (void *cls)
	Delete the entry with the lowest expiration value from the datacache right now. More...
static unsigned int	heap_plugin_get_random (void *cls, GNUNET_DATACACHE_Iterator iter, void *iter_cls)
	Return a random value from the datastore. More...
static int	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, 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.

Referenced by libgnunet_plugin_datacache_heap_init().

LOG_STRERROR_FILE

#define LOG_STRERROR_FILE	(		kind,
			op,
			fn
	)		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 34 of file plugin_datacache_heap.c.

Referenced by heap_plugin_del(), heap_plugin_put(), libgnunet_plugin_datacache_heap_done(), and libgnunet_plugin_datacache_heap_init().

OVERHEAD

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

Definition at line 107 of file plugin_datacache_heap.c.

Referenced by heap_plugin_del(), and heap_plugin_put().

Function Documentation

put_cb()

static int 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 162 of file plugin_datacache_heap.c.

References GNUNET_TIME_Absolute::abs_value_us, PutContext::data, Value::discard_time, PutContext::discard_time, PutContext::found, GNUNET_array_grow, GNUNET_CONTAINER_heap_update_cost(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_memcpy, GNUNET_NO, GNUNET_TIME_absolute_max(), GNUNET_YES, Value::hn, Value::path_info, PutContext::path_info, Value::path_info_len, PutContext::path_info_len, Value::size, PutContext::size, Value::type, PutContext::type, and value.

Referenced by GNUNET_DHT_monitor_start(), and heap_plugin_put().

{
  struct PutContext *put_ctx = cls;
  struct Value *val = value;

  if ( (val->size == put_ctx->size) &&
       (val->type == put_ctx->type) &&
       (0 == memcmp (&val[1],
                     put_ctx->data,
                     put_ctx->size)) )
  {
    put_ctx->found = GNUNET_YES;
    val->discard_time = GNUNET_TIME_absolute_max (val->discard_time,
                                                  put_ctx->discard_time);
    /* replace old path with new path */
    GNUNET_array_grow (val->path_info,
                       val->path_info_len,
                       put_ctx->path_info_len);
    GNUNET_memcpy (val->path_info,
                   put_ctx->path_info,
                   put_ctx->path_info_len * sizeof (struct GNUNET_PeerIdentity));
    GNUNET_CONTAINER_heap_update_cost (val->hn,
                                       val->discard_time.abs_value_us);
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                "Got same value for key %s and type %d (size %u vs %u)\n",
                GNUNET_h2s (key),
                val->type,
                (unsigned int) val->size,
                (unsigned int) put_ctx->size);
    return GNUNET_NO;
  }
  return GNUNET_YES;
}

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, const struct GNUNET_HashCode *  key, uint32_t  xor_distance, size_t  size, const char *  data, enum GNUNET_BLOCK_Type  type, struct GNUNET_TIME_Absolute  discard_time, unsigned int  path_info_len, const struct GNUNET_PeerIdentity *  path_info  )

static

Store an item in the datastore.

Parameters

cls	closure (our struct Plugin)
key	key to store data under
xor_distance	how close is key to our PID?
size	number of bytes in data
data	data to store
type	type of the value
discard_time	when to discard the value in any case
path_info_len	number of entries in path_info
path_info	a path through the network

Returns

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

Definition at line 214 of file plugin_datacache_heap.c.

References GNUNET_TIME_Absolute::abs_value_us, data, PutContext::data, Value::discard_time, PutContext::discard_time, Value::distance, PutContext::found, GNUNET_array_grow, GNUNET_CONTAINER_heap_insert(), GNUNET_CONTAINER_multihashmap_get_multiple(), GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE, GNUNET_malloc, GNUNET_memcpy, GNUNET_NO, GNUNET_YES, Plugin::heaps, Value::hn, Value::key, Plugin::key, Plugin::map, NUM_HEAPS, OVERHEAD, Value::path_info, PutContext::path_info, Value::path_info_len, PutContext::path_info_len, plugin, put_cb(), Value::size, PutContext::size, Plugin::size, Value::type, type, and PutContext::type.

Referenced by libgnunet_plugin_datacache_heap_init().

{
  struct Plugin *plugin = cls;
  struct Value *val;
  struct PutContext put_ctx;

  put_ctx.found = GNUNET_NO;
  put_ctx.data = data;
  put_ctx.size = size;
  put_ctx.path_info = path_info;
  put_ctx.path_info_len = path_info_len;
  put_ctx.discard_time = discard_time;
  put_ctx.type = type;
  GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
                                              key,
                                              &put_cb,
                                              &put_ctx);
  if (GNUNET_YES == put_ctx.found)
    return 0;
  val = GNUNET_malloc (sizeof (struct Value) + size);
  GNUNET_memcpy (&val[1],
                 data,
                 size);
  val->key = *key;
  val->type = type;
  val->discard_time = discard_time;
  val->size = size;
  if (xor_distance >= NUM_HEAPS)
    val->distance = NUM_HEAPS - 1;
  else
    val->distance = xor_distance;
  GNUNET_array_grow (val->path_info,
                     val->path_info_len,
                     path_info_len);
  GNUNET_memcpy (val->path_info,
                 path_info,
                 path_info_len * sizeof (struct GNUNET_PeerIdentity));
  (void) GNUNET_CONTAINER_multihashmap_put (plugin->map,
                                            &val->key,
                                            val,
                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
  val->hn = GNUNET_CONTAINER_heap_insert (plugin->heaps[val->distance],
                                          val,
                                          val->discard_time.abs_value_us);
  return size + OVERHEAD;
}

Here is the call graph for this function:

Here is the caller graph for this function:

get_cb()

static int 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 308 of file plugin_datacache_heap.c.

References GetContext::cnt, Value::discard_time, GNUNET_BLOCK_TYPE_ANY, GNUNET_OK, GNUNET_TIME_absolute_get_remaining(), GNUNET_YES, GetContext::iter, GetContext::iter_cls, GNUNET_TIME_Relative::rel_value_us, ret, Value::size, Value::type, GetContext::type, and value.

Referenced by GNUNET_DHT_monitor_start(), heap_plugin_get(), and heap_plugin_get_random().

{
  struct GetContext *get_ctx = cls;
  struct Value *val = value;
  int ret;

  if ( (get_ctx->type != val->type) &&
       (GNUNET_BLOCK_TYPE_ANY != get_ctx->type) )
    return GNUNET_OK;
  if (0 ==
      GNUNET_TIME_absolute_get_remaining (val->discard_time).rel_value_us)
    return GNUNET_OK;
  if (NULL != get_ctx->iter)
    ret = get_ctx->iter (get_ctx->iter_cls,
                         key,
                         val->size,
                         (const char *) &val[1],
                         val->type,
                         val->discard_time,
                         val->path_info_len,
                         val->path_info);
  else
    ret = GNUNET_YES;
  get_ctx->cnt++;
  return ret;
}

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 350 of file plugin_datacache_heap.c.

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

Referenced by libgnunet_plugin_datacache_heap_init().

{
  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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

heap_plugin_del()

static int 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 379 of file plugin_datacache_heap.c.

References GNUNET_DATACACHE_PluginEnvironment::cls, GNUNET_DATACACHE_PluginEnvironment::delete_notify, Plugin::env, GNUNET_assert, GNUNET_CONTAINER_heap_remove_root(), GNUNET_CONTAINER_multihashmap_remove(), GNUNET_free, GNUNET_free_non_null, GNUNET_OK, GNUNET_SYSERR, GNUNET_YES, Plugin::heaps, Value::key, Plugin::map, NUM_HEAPS, OVERHEAD, Value::path_info, plugin, and Value::size.

Referenced by libgnunet_plugin_datacache_heap_init().

{
  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->key,
                                                       val));
  plugin->env->delete_notify (plugin->env->cls,
                              &val->key,
                              val->size + OVERHEAD);
  GNUNET_free_non_null (val->path_info);
  GNUNET_free (val);
  return GNUNET_OK;
}

Here is the call graph for this function:

Here is the caller graph for this function:

heap_plugin_get_random()

static unsigned int heap_plugin_get_random ( void *  cls, GNUNET_DATACACHE_Iterator  iter, void *  iter_cls  )

static

Return a random value from the datastore.

Parameters

cls	closure (our struct Plugin)
iter	maybe NULL (to just count)
iter_cls	closure for iter

Returns

the number of results found

Definition at line 414 of file plugin_datacache_heap.c.

References GetContext::cnt, get_cb(), GNUNET_BLOCK_TYPE_ANY, GNUNET_CONTAINER_multihashmap_get_random(), Plugin::iter, GetContext::iter, Plugin::iter_cls, GetContext::iter_cls, Plugin::map, plugin, and GetContext::type.

Referenced by libgnunet_plugin_datacache_heap_init().

{
  struct Plugin *plugin = cls;
  struct GetContext get_ctx;

  get_ctx.type = GNUNET_BLOCK_TYPE_ANY;
  get_ctx.iter = iter;
  get_ctx.iter_cls = iter_cls;
  get_ctx.cnt = 0;
  GNUNET_CONTAINER_multihashmap_get_random (plugin->map,
                                            &get_cb,
                                            &get_ctx);
  return get_ctx.cnt;
}

Here is the call graph for this function:

Here is the caller graph for this function:

find_closest()

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

static

Definition at line 446 of file plugin_datacache_heap.c.

References GNUNET_CRYPTO_hash_cmp(), GNUNET_OK, Value::key, GetClosestContext::key, GetClosestContext::num_results, value, and GetClosestContext::values.

Referenced by heap_plugin_get_closest().

{
  struct GetClosestContext *gcc = cls;
  struct Value *val = value;
  unsigned int j;

  if (1 != GNUNET_CRYPTO_hash_cmp (key,
                                   gcc->key))
    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]->key,
                                     key))
    {
      j = i;
      break;
    }
  }
  if (j == gcc->num_results)
    return GNUNET_OK;
  gcc->values[j] = val;
  return GNUNET_OK;
}

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, 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
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 493 of file plugin_datacache_heap.c.

References find_closest(), GNUNET_CONTAINER_multihashmap_iterate(), Plugin::iter, Plugin::map, GetClosestContext::num_results, plugin, Plugin::size, type, values, and GetClosestContext::values.

Referenced by libgnunet_plugin_datacache_heap_init().

{
  struct Plugin *plugin = cls;
  struct Value *values[num_results];
  struct GetClosestContext gcc = {
    .values = values,
    .num_results = num_results,
    .key = key
  };
  GNUNET_CONTAINER_multihashmap_iterate (plugin->map,
                                         &find_closest,
                                         &gcc);
  for (unsigned int i=0;i<num_results;i++)
  {
    if (NULL == values[i])
      return i;
    iter (iter_cls,
          &values[i]->key,
          values[i]->size,
          (void *) &values[i][1],
          values[i]->type,
          values[i]->discard_time,
          values[i]->path_info_len,
          values[i]->path_info);
  }
  return num_results;
}

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 533 of file plugin_datacache_heap.c.

References _, Plugin::api, GNUNET_DATACACHE_PluginEnvironment::cls, GNUNET_DATACACHE_PluginFunctions::cls, GNUNET_DATACACHE_PluginFunctions::del, Plugin::env, GNUNET_DATACACHE_PluginFunctions::get, GNUNET_DATACACHE_PluginFunctions::get_closest, GNUNET_DATACACHE_PluginFunctions::get_random, 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_get_random(), heap_plugin_put(), Plugin::heaps, LOG, Plugin::map, NUM_HEAPS, plugin, and GNUNET_DATACACHE_PluginFunctions::put.

{
  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_random = &heap_plugin_get_random;
  api->get_closest = &heap_plugin_get_closest;
  LOG (GNUNET_ERROR_TYPE_INFO,
       _("Heap datacache running\n"));
  return api;
}

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 565 of file plugin_datacache_heap.c.

References Plugin::api, 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_free_non_null, GNUNET_YES, Plugin::heaps, Value::key, Plugin::map, NUM_HEAPS, Value::path_info, and plugin.

{
  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->key,
                                                           val));
      GNUNET_free_non_null (val->path_info);
      GNUNET_free (val);
    }
    GNUNET_CONTAINER_heap_destroy (plugin->heaps[i]);
  }
  GNUNET_CONTAINER_multihashmap_destroy (plugin->map);
  GNUNET_free (plugin);
  GNUNET_free (api);
  return NULL;
}

Here is the call graph for this function: