plugin_datacache_heap.c

Go to the documentation of this file.

/*
     This file is part of GNUnet
     Copyright (C) 2012, 2015, 2022 GNUnet e.V.
 
     GNUnet is free software: you can redistribute it and/or modify it
     under the terms of the GNU Affero General Public License as published
     by the Free Software Foundation, either version 3 of the License,
     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
     Affero General Public License for more details.
 
     You should have received a copy of the GNU Affero General Public License
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
     SPDX-License-Identifier: AGPL3.0-or-later
 */
 
#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_datacache_plugin.h"
 
#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
 
struct Plugin
{
  struct GNUNET_DATACACHE_PluginEnvironment *env;
 
  struct GNUNET_CONTAINER_MultiHashMap *map;
 
  struct GNUNET_CONTAINER_Heap *heaps[NUM_HEAPS];
};
 
 
struct Value
{
  struct GNUNET_DATACACHE_Block block;
 
  struct GNUNET_CONTAINER_HeapNode *hn;
 
  struct GNUNET_DHT_PathElement *put_path;
 
  uint32_t distance;
 
};
 
 
#define OVERHEAD (sizeof(struct Value) + 64)
 
 
struct PutContext
{
  const struct GNUNET_DATACACHE_Block *block;
 
  bool found;
};
 
 
static enum GNUNET_GenericReturnValue
put_cb (void *cls,
        const struct GNUNET_HashCode *key,
        void *value)
{
  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;
}
 
 
static ssize_t
heap_plugin_put (void *cls,
                 uint32_t xor_distance,
                 const struct GNUNET_DATACACHE_Block *block)
{
  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;
}
 
 
struct GetContext
{
  struct Value **values;
 
  unsigned int cnt;
 
  enum GNUNET_BLOCK_Type type;
};
 
 
static enum GNUNET_GenericReturnValue
get_cb (void *cls,
        const struct GNUNET_HashCode *key,
        void *value)
{
  struct GetContext *get_ctx = cls;
  struct Value *val = value;
 
  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));
  GNUNET_array_append (get_ctx->values,
                       get_ctx->cnt,
                       val);
  return GNUNET_OK;
}
 
 
static int
cmp_expiration (const void *a,
                const void *b)
{
  const struct Value *va = *(struct Value **) a;
  const struct Value *vb = *(struct Value **) b;
 
  if (va->block.expiration_time.abs_value_us >
      vb->block.expiration_time.abs_value_us)
    return -1;
  if (va->block.expiration_time.abs_value_us <
      vb->block.expiration_time.abs_value_us)
    return 1;
  return 0;
}
 
 
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)
{
  struct Plugin *plugin = cls;
  struct GetContext get_ctx = {
    .type = type
  };
  unsigned int ret;
 
  GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
                                              key,
                                              &get_cb,
                                              &get_ctx);
  /* Hand out the freshest block first: a key may hold several
     versions of the same (mutable) block, and a requester that stops
     at the first reply must not be given a nearly expired one. */
  qsort (get_ctx.values,
         get_ctx.cnt,
         sizeof (struct Value *),
         &cmp_expiration);
  ret = 0;
  for (unsigned int i = 0; i < get_ctx.cnt; i++)
  {
    ret++;
    if ( (NULL != iter) &&
         (GNUNET_OK != iter (iter_cls,
                             &get_ctx.values[i]->block)) )
      break;
  }
  GNUNET_array_grow (get_ctx.values,
                     get_ctx.cnt,
                     0);
  return ret;
}
 
 
static enum GNUNET_GenericReturnValue
heap_plugin_del (void *cls)
{
  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;
}
 
 
struct GetClosestContext
{
  struct Value **values;
 
  const struct GNUNET_HashCode *key;
 
  enum GNUNET_BLOCK_Type type;
 
  unsigned int num_results;
 
};
 
 
static enum GNUNET_GenericReturnValue
find_closest (void *cls,
              const struct GNUNET_HashCode *key,
              void *value)
{
  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;
}
 
 
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)
{
  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;
}
 
 
void *
libgnunet_plugin_datacache_heap_init (void *cls);
 
void *
libgnunet_plugin_datacache_heap_init (void *cls)
{
  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;
}
 
 
void *
libgnunet_plugin_datacache_heap_done (void *cls);
 
void *
libgnunet_plugin_datacache_heap_done (void *cls)
{
  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;
}
 
 
/* end of plugin_datacache_heap.c */