X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fdatacache%2Fplugin_datacache_heap.c;h=aeb0101633302748259448c5302f29b4a4c8f2bf;hb=4e29ecde9b3ad3e34af359f18b6679c06b17ce78;hp=aee6cd5b8986ee9f76554c817505ed4d3e8837e2;hpb=3d7fefedc9ba60bd8e8448efe8b628446d958536;p=oweals%2Fgnunet.git diff --git a/src/datacache/plugin_datacache_heap.c b/src/datacache/plugin_datacache_heap.c index aee6cd5b8..aeb010163 100644 --- a/src/datacache/plugin_datacache_heap.c +++ b/src/datacache/plugin_datacache_heap.c @@ -1,21 +1,16 @@ /* This file is part of GNUnet - (C) 2012 Christian Grothoff (and other contributing authors) + 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 General Public License as published - by the Free Software Foundation; either version 3, or (at your - option) any later version. + 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 - 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. + Affero General Public License for more details. */ /** @@ -31,7 +26,7 @@ #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. @@ -49,9 +44,9 @@ struct Plugin struct GNUNET_CONTAINER_MultiHashMap *map; /** - * Heap for expirations. + * Heaps sorted by distance. */ - struct GNUNET_CONTAINER_Heap *heap; + struct GNUNET_CONTAINER_Heap *heaps[NUM_HEAPS]; }; @@ -87,15 +82,20 @@ struct Value size_t size; /** - * Number of entries in 'path_info'. + * 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; - + }; @@ -103,32 +103,27 @@ struct Value /** - * Closure for 'put_cb'. + * Closure for #put_cb(). */ struct PutContext { /** * Expiration time for the new value. */ - struct GNUNET_TIME_Absolute discard_time; + struct GNUNET_TIME_Absolute discard_time; /** * Data for the new value. */ const char *data; - /** - * Heap from the plugin. - */ - struct GNUNET_CONTAINER_Heap *heap; - /** * Path information. */ const struct GNUNET_PeerIdentity *path_info; /** - * Number of bytes in 'data'. + * Number of bytes in @e data. */ size_t size; @@ -138,12 +133,12 @@ struct PutContext enum GNUNET_BLOCK_Type type; /** - * Number of entries in 'path_info'. + * Number of entries in @e path_info. */ unsigned int path_info_len; /** - * Value to set to GNUNET_YES if an equivalent block was found. + * Value to set to #GNUNET_YES if an equivalent block was found. */ int found; }; @@ -153,10 +148,10 @@ struct PutContext * Function called during PUT to detect if an equivalent block * already exists. * - * @param cls the 'struct PutContext' + * @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) + * @param value an existing value + * @return #GNUNET_YES if not found (to continue to iterate) */ static int put_cb (void *cls, @@ -168,20 +163,21 @@ put_cb (void *cls, if ( (val->size == put_ctx->size) && (val->type == put_ctx->type) && - (0 == memcmp (&val[1], put_ctx->data, put_ctx->size)) ) + (0 == memcmp (&val[1], + put_ctx->data, + put_ctx->size)) ) { - put_ctx->found = GNUNET_YES; + 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); - memcpy (val->path_info, - put_ctx->path_info, - put_ctx->path_info_len * sizeof (struct GNUNET_PeerIdentity)); - GNUNET_CONTAINER_heap_update_cost (put_ctx->heap, - val->hn, + 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", @@ -198,19 +194,24 @@ put_cb (void *cls, /** * Store an item in the datastore. * - * @param cls closure (our "struct Plugin") + * @param cls closure (our `struct Plugin`) * @param key key to store data under - * @param size number of bytes in data + * @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 'path_info' + * @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 + * @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, size_t size, - const char *data, enum GNUNET_BLOCK_Type type, +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) @@ -220,7 +221,6 @@ heap_plugin_put (void *cls, const struct GNUNET_HashCode * key, size_t size, struct PutContext put_ctx; put_ctx.found = GNUNET_NO; - put_ctx.heap = plugin->heap; put_ctx.data = data; put_ctx.size = size; put_ctx.path_info = path_info; @@ -229,26 +229,33 @@ heap_plugin_put (void *cls, const struct GNUNET_HashCode * key, size_t size, put_ctx.type = type; GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map, key, - put_cb, + &put_cb, &put_ctx); if (GNUNET_YES == put_ctx.found) return 0; val = GNUNET_malloc (sizeof (struct Value) + size); - memcpy (&val[1], data, 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); - memcpy (val->path_info, path_info, - path_info_len * sizeof (struct GNUNET_PeerIdentity)); + 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->heap, + val->hn = GNUNET_CONTAINER_heap_insert (plugin->heaps[val->distance], val, val->discard_time.abs_value_us); return size + OVERHEAD; @@ -256,7 +263,7 @@ heap_plugin_put (void *cls, const struct GNUNET_HashCode * key, size_t size, /** - * Closure for 'get_cb'. + * Closure for #get_cb(). */ struct GetContext { @@ -266,7 +273,7 @@ struct GetContext GNUNET_DATACACHE_Iterator iter; /** - * Closure for 'iter'. + * Closure for @e iter. */ void *iter_cls; @@ -287,10 +294,10 @@ struct GetContext * Function called during GET to find matching blocks. * Only matches by type. * - * @param cls the 'struct GetContext' + * @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 + * @param value an existing value + * @return #GNUNET_YES to continue to iterate */ static int get_cb (void *cls, @@ -310,7 +317,7 @@ get_cb (void *cls, val->size, (const char *) &val[1], val->type, - val->discard_time, + val->discard_time, val->path_info_len, val->path_info); else @@ -324,28 +331,30 @@ get_cb (void *cls, * Iterate over the results for a particular key * in the datastore. * - * @param cls closure (our "struct Plugin") + * @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 iter + * @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) +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.iter_cls = iter_cls; get_ctx.cnt = 0; GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map, key, - get_cb, + &get_cb, &get_ctx); return get_ctx.cnt; } @@ -355,16 +364,21 @@ heap_plugin_get (void *cls, const struct GNUNET_HashCode * key, * 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 + * @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; - - val = GNUNET_CONTAINER_heap_remove_root (plugin->heap); + + for (unsigned int i=0;iheaps[i]); + if (NULL != val) + break; + } if (NULL == val) return GNUNET_SYSERR; GNUNET_assert (GNUNET_YES == @@ -380,11 +394,132 @@ heap_plugin_del (void *cls) } +/** + * 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;inum_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;ikey, + 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") + * @param cls closure (the `struct GNUNET_DATACACHE_PluginEnvironmnet`) + * @return the plugin's closure (our `struct Plugin`) */ void * libgnunet_plugin_datacache_heap_init (void *cls) @@ -393,17 +528,21 @@ libgnunet_plugin_datacache_heap_init (void *cls) struct GNUNET_DATACACHE_PluginFunctions *api; struct Plugin *plugin; - plugin = GNUNET_malloc (sizeof (struct Plugin)); + plugin = GNUNET_new (struct Plugin); plugin->map = GNUNET_CONTAINER_multihashmap_create (1024, /* FIXME: base on quota! */ GNUNET_YES); - plugin->heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); + for (unsigned int i=0;iheaps[i] = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); plugin->env = env; - api = GNUNET_malloc (sizeof (struct GNUNET_DATACACHE_PluginFunctions)); + 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; - LOG (GNUNET_ERROR_TYPE_INFO, _("Heap datacache running\n")); + 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; } @@ -421,15 +560,19 @@ libgnunet_plugin_datacache_heap_done (void *cls) struct Plugin *plugin = api->cls; struct Value *val; - while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heap))) + for (unsigned int i=0;imap, - &val->key, - val)); - GNUNET_free (val); + 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_heap_destroy (plugin->heap); GNUNET_CONTAINER_multihashmap_destroy (plugin->map); GNUNET_free (plugin); GNUNET_free (api);