123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592 |
- /*
- This file is part of GNUnet
- Copyright (C) 2012, 2015 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
- */
- /**
- * @file datacache/plugin_datacache_heap.c
- * @brief heap-only implementation of a database backend for the datacache
- * @author Christian Grothoff
- */
- #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
- /**
- * Context for all functions in this plugin.
- */
- struct Plugin
- {
- /**
- * Our execution environment.
- */
- struct GNUNET_DATACACHE_PluginEnvironment *env;
- /**
- * Our hash map.
- */
- struct GNUNET_CONTAINER_MultiHashMap *map;
- /**
- * Heaps sorted by distance.
- */
- struct GNUNET_CONTAINER_Heap *heaps[NUM_HEAPS];
- };
- /**
- * Entry in the hash map.
- */
- struct Value
- {
- /**
- * Key for the entry.
- */
- struct GNUNET_HashCode key;
- /**
- * Expiration time.
- */
- struct GNUNET_TIME_Absolute discard_time;
- /**
- * Corresponding node in the heap.
- */
- struct GNUNET_CONTAINER_HeapNode *hn;
- /**
- * Path information.
- */
- struct GNUNET_PeerIdentity *path_info;
- /**
- * Payload (actual payload follows this struct)
- */
- size_t size;
- /**
- * Number of entries in @e path_info.
- */
- unsigned int path_info_len;
- /**
- * How close is the hash to us? Determines which heap we are in!
- */
- uint32_t distance;
- /**
- * Type of the block.
- */
- enum GNUNET_BLOCK_Type type;
- };
- #define OVERHEAD (sizeof (struct Value) + 64)
- /**
- * Closure for #put_cb().
- */
- struct PutContext
- {
- /**
- * Expiration time for the new value.
- */
- struct GNUNET_TIME_Absolute discard_time;
- /**
- * Data for the new value.
- */
- const char *data;
- /**
- * Path information.
- */
- const struct GNUNET_PeerIdentity *path_info;
- /**
- * Number of bytes in @e data.
- */
- size_t size;
- /**
- * Type of the node.
- */
- enum GNUNET_BLOCK_Type type;
- /**
- * Number of entries in @e path_info.
- */
- unsigned int path_info_len;
- /**
- * Value to set to #GNUNET_YES if an equivalent block was found.
- */
- int found;
- };
- /**
- * Function called during PUT to detect if an equivalent block
- * already exists.
- *
- * @param cls the `struct PutContext`
- * @param key the key for the value(s)
- * @param value an existing value
- * @return #GNUNET_YES if not found (to continue to iterate)
- */
- static int
- put_cb (void *cls,
- const struct GNUNET_HashCode *key,
- void *value)
- {
- 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;
- }
- /**
- * Store an item in the datastore.
- *
- * @param cls closure (our `struct Plugin`)
- * @param key key to store data under
- * @param xor_distance how close is @a key to our PID?
- * @param size number of bytes in @a data
- * @param data data to store
- * @param type type of the value
- * @param discard_time when to discard the value in any case
- * @param path_info_len number of entries in @a path_info
- * @param path_info a path through the network
- * @return 0 if duplicate, -1 on error, number of bytes used otherwise
- */
- 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)
- {
- 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;
- }
- /**
- * Closure for #get_cb().
- */
- struct GetContext
- {
- /**
- * Function to call for each result.
- */
- GNUNET_DATACACHE_Iterator iter;
- /**
- * Closure for @e iter.
- */
- void *iter_cls;
- /**
- * Number of results found.
- */
- unsigned int cnt;
- /**
- * Block type requested.
- */
- enum GNUNET_BLOCK_Type type;
- };
- /**
- * Function called during GET to find matching blocks.
- * Only matches by type.
- *
- * @param cls the `struct GetContext`
- * @param key the key for the value(s)
- * @param value an existing value
- * @return #GNUNET_YES to continue to iterate
- */
- static int
- get_cb (void *cls,
- const struct GNUNET_HashCode *key,
- void *value)
- {
- 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;
- }
- /**
- * Iterate over the results for a particular key
- * in the datastore.
- *
- * @param cls closure (our `struct Plugin`)
- * @param key
- * @param type entries of which type are relevant?
- * @param iter maybe NULL (to just count)
- * @param iter_cls closure for @a iter
- * @return the number of results found
- */
- 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;
- 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;
- }
- /**
- * Delete the entry with the lowest expiration value
- * from the datacache right now.
- *
- * @param cls closure (our `struct Plugin`)
- * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
- */
- static int
- 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->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;
- }
- /**
- * Return a random value from the datastore.
- *
- * @param cls closure (our `struct Plugin`)
- * @param iter maybe NULL (to just count)
- * @param iter_cls closure for @a iter
- * @return the number of results found
- */
- static unsigned int
- heap_plugin_get_random (void *cls,
- GNUNET_DATACACHE_Iterator iter,
- void *iter_cls)
- {
- 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;
- }
- /**
- * Closure for #find_closest().
- */
- struct GetClosestContext
- {
- struct Value **values;
- unsigned int num_results;
- const struct GNUNET_HashCode *key;
- };
- static int
- 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 */
- 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;
- }
- /**
- * Iterate over the results that are "close" to a particular key in
- * the datacache. "close" is defined as numerically larger than @a
- * key (when interpreted as a circular address space), with small
- * distance.
- *
- * @param cls closure (internal context for the plugin)
- * @param key area of the keyspace to look into
- * @param num_results number of results that should be returned to @a iter
- * @param iter maybe NULL (to just count)
- * @param iter_cls closure for @a iter
- * @return the number of results found
- */
- 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)
- {
- 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;
- }
- /**
- * Entry point for the plugin.
- *
- * @param cls closure (the `struct GNUNET_DATACACHE_PluginEnvironmnet`)
- * @return the plugin's closure (our `struct Plugin`)
- */
- 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_random = &heap_plugin_get_random;
- api->get_closest = &heap_plugin_get_closest;
- LOG (GNUNET_ERROR_TYPE_INFO,
- _("Heap datacache running\n"));
- return api;
- }
- /**
- * Exit point from the plugin.
- *
- * @param cls closure (our "struct Plugin")
- * @return NULL
- */
- 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->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;
- }
- /* end of plugin_datacache_heap.c */
|