2 This file is part of GNUnet
3 Copyright (C) 2012, 2015 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details.
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
22 * @file datacache/plugin_datacache_heap.c
23 * @brief heap-only implementation of a database backend for the datacache
24 * @author Christian Grothoff
27 #include "gnunet_util_lib.h"
28 #include "gnunet_datacache_plugin.h"
30 #define LOG(kind, ...) GNUNET_log_from (kind, "datacache-heap", __VA_ARGS__)
32 #define LOG_STRERROR_FILE(kind, op, fn) GNUNET_log_from_strerror_file (kind, \
39 * Context for all functions in this plugin.
44 * Our execution environment.
46 struct GNUNET_DATACACHE_PluginEnvironment *env;
51 struct GNUNET_CONTAINER_MultiHashMap *map;
54 * Heaps sorted by distance.
56 struct GNUNET_CONTAINER_Heap *heaps[NUM_HEAPS];
61 * Entry in the hash map.
68 struct GNUNET_HashCode key;
73 struct GNUNET_TIME_Absolute discard_time;
76 * Corresponding node in the heap.
78 struct GNUNET_CONTAINER_HeapNode *hn;
83 struct GNUNET_PeerIdentity *path_info;
86 * Payload (actual payload follows this struct)
91 * Number of entries in @e path_info.
93 unsigned int path_info_len;
96 * How close is the hash to us? Determines which heap we are in!
103 enum GNUNET_BLOCK_Type type;
107 #define OVERHEAD (sizeof(struct Value) + 64)
111 * Closure for #put_cb().
116 * Expiration time for the new value.
118 struct GNUNET_TIME_Absolute discard_time;
121 * Data for the new value.
128 const struct GNUNET_PeerIdentity *path_info;
131 * Number of bytes in @e data.
138 enum GNUNET_BLOCK_Type type;
141 * Number of entries in @e path_info.
143 unsigned int path_info_len;
146 * Value to set to #GNUNET_YES if an equivalent block was found.
153 * Function called during PUT to detect if an equivalent block
156 * @param cls the `struct PutContext`
157 * @param key the key for the value(s)
158 * @param value an existing value
159 * @return #GNUNET_YES if not found (to continue to iterate)
163 const struct GNUNET_HashCode *key,
166 struct PutContext *put_ctx = cls;
167 struct Value *val = value;
169 if ((val->size == put_ctx->size) &&
170 (val->type == put_ctx->type) &&
171 (0 == memcmp (&val[1],
175 put_ctx->found = GNUNET_YES;
176 val->discard_time = GNUNET_TIME_absolute_max (val->discard_time,
177 put_ctx->discard_time);
178 /* replace old path with new path */
179 GNUNET_array_grow (val->path_info,
181 put_ctx->path_info_len);
182 GNUNET_memcpy (val->path_info,
184 put_ctx->path_info_len * sizeof(struct GNUNET_PeerIdentity));
185 GNUNET_CONTAINER_heap_update_cost (val->hn,
186 val->discard_time.abs_value_us);
187 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
188 "Got same value for key %s and type %d (size %u vs %u)\n",
191 (unsigned int) val->size,
192 (unsigned int) put_ctx->size);
200 * Store an item in the datastore.
202 * @param cls closure (our `struct Plugin`)
203 * @param key key to store data under
204 * @param xor_distance how close is @a key to our PID?
205 * @param size number of bytes in @a data
206 * @param data data to store
207 * @param type type of the value
208 * @param discard_time when to discard the value in any case
209 * @param path_info_len number of entries in @a path_info
210 * @param path_info a path through the network
211 * @return 0 if duplicate, -1 on error, number of bytes used otherwise
214 heap_plugin_put (void *cls,
215 const struct GNUNET_HashCode *key,
216 uint32_t xor_distance,
219 enum GNUNET_BLOCK_Type type,
220 struct GNUNET_TIME_Absolute discard_time,
221 unsigned int path_info_len,
222 const struct GNUNET_PeerIdentity *path_info)
224 struct Plugin *plugin = cls;
226 struct PutContext put_ctx;
228 put_ctx.found = GNUNET_NO;
231 put_ctx.path_info = path_info;
232 put_ctx.path_info_len = path_info_len;
233 put_ctx.discard_time = discard_time;
235 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
239 if (GNUNET_YES == put_ctx.found)
241 val = GNUNET_malloc (sizeof(struct Value) + size);
242 GNUNET_memcpy (&val[1],
247 val->discard_time = discard_time;
249 if (xor_distance >= NUM_HEAPS)
250 val->distance = NUM_HEAPS - 1;
252 val->distance = xor_distance;
253 GNUNET_array_grow (val->path_info,
256 GNUNET_memcpy (val->path_info,
258 path_info_len * sizeof(struct GNUNET_PeerIdentity));
259 (void) GNUNET_CONTAINER_multihashmap_put (plugin->map,
262 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
263 val->hn = GNUNET_CONTAINER_heap_insert (plugin->heaps[val->distance],
265 val->discard_time.abs_value_us);
266 return size + OVERHEAD;
271 * Closure for #get_cb().
276 * Function to call for each result.
278 GNUNET_DATACACHE_Iterator iter;
281 * Closure for @e iter.
286 * Number of results found.
291 * Block type requested.
293 enum GNUNET_BLOCK_Type type;
298 * Function called during GET to find matching blocks.
299 * Only matches by type.
301 * @param cls the `struct GetContext`
302 * @param key the key for the value(s)
303 * @param value an existing value
304 * @return #GNUNET_YES to continue to iterate
308 const struct GNUNET_HashCode *key,
311 struct GetContext *get_ctx = cls;
312 struct Value *val = value;
315 if ((get_ctx->type != val->type) &&
316 (GNUNET_BLOCK_TYPE_ANY != get_ctx->type))
319 GNUNET_TIME_absolute_get_remaining (val->discard_time).rel_value_us)
321 if (NULL != get_ctx->iter)
322 ret = get_ctx->iter (get_ctx->iter_cls,
325 (const char *) &val[1],
338 * Iterate over the results for a particular key
341 * @param cls closure (our `struct Plugin`)
343 * @param type entries of which type are relevant?
344 * @param iter maybe NULL (to just count)
345 * @param iter_cls closure for @a iter
346 * @return the number of results found
349 heap_plugin_get (void *cls,
350 const struct GNUNET_HashCode *key,
351 enum GNUNET_BLOCK_Type type,
352 GNUNET_DATACACHE_Iterator iter,
355 struct Plugin *plugin = cls;
356 struct GetContext get_ctx;
360 get_ctx.iter_cls = iter_cls;
362 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
371 * Delete the entry with the lowest expiration value
372 * from the datacache right now.
374 * @param cls closure (our `struct Plugin`)
375 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
378 heap_plugin_del (void *cls)
380 struct Plugin *plugin = cls;
383 for (unsigned int i = 0; i < NUM_HEAPS; i++)
385 val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i]);
390 return GNUNET_SYSERR;
391 GNUNET_assert (GNUNET_YES ==
392 GNUNET_CONTAINER_multihashmap_remove (plugin->map,
395 plugin->env->delete_notify (plugin->env->cls,
397 val->size + OVERHEAD);
398 GNUNET_free_non_null (val->path_info);
405 * Return a random value from the datastore.
407 * @param cls closure (our `struct Plugin`)
408 * @param iter maybe NULL (to just count)
409 * @param iter_cls closure for @a iter
410 * @return the number of results found
413 heap_plugin_get_random (void *cls,
414 GNUNET_DATACACHE_Iterator iter,
417 struct Plugin *plugin = cls;
418 struct GetContext get_ctx;
420 get_ctx.type = GNUNET_BLOCK_TYPE_ANY;
422 get_ctx.iter_cls = iter_cls;
424 GNUNET_CONTAINER_multihashmap_get_random (plugin->map,
432 * Closure for #find_closest().
434 struct GetClosestContext
436 struct Value **values;
438 unsigned int num_results;
440 const struct GNUNET_HashCode *key;
445 find_closest (void *cls,
446 const struct GNUNET_HashCode *key,
449 struct GetClosestContext *gcc = cls;
450 struct Value *val = value;
453 if (1 != GNUNET_CRYPTO_hash_cmp (key,
455 return GNUNET_OK; /* useless */
456 j = gcc->num_results;
457 for (unsigned int i = 0; i < gcc->num_results; i++)
459 if (NULL == gcc->values[i])
464 if (1 == GNUNET_CRYPTO_hash_cmp (&gcc->values[i]->key,
471 if (j == gcc->num_results)
473 gcc->values[j] = val;
479 * Iterate over the results that are "close" to a particular key in
480 * the datacache. "close" is defined as numerically larger than @a
481 * key (when interpreted as a circular address space), with small
484 * @param cls closure (internal context for the plugin)
485 * @param key area of the keyspace to look into
486 * @param num_results number of results that should be returned to @a iter
487 * @param iter maybe NULL (to just count)
488 * @param iter_cls closure for @a iter
489 * @return the number of results found
492 heap_plugin_get_closest (void *cls,
493 const struct GNUNET_HashCode *key,
494 unsigned int num_results,
495 GNUNET_DATACACHE_Iterator iter,
498 struct Plugin *plugin = cls;
499 struct Value *values[num_results];
500 struct GetClosestContext gcc = {
502 .num_results = num_results,
506 GNUNET_CONTAINER_multihashmap_iterate (plugin->map,
509 for (unsigned int i = 0; i < num_results; i++)
511 if (NULL == values[i])
516 (void *) &values[i][1],
518 values[i]->discard_time,
519 values[i]->path_info_len,
520 values[i]->path_info);
527 * Entry point for the plugin.
529 * @param cls closure (the `struct GNUNET_DATACACHE_PluginEnvironmnet`)
530 * @return the plugin's closure (our `struct Plugin`)
533 libgnunet_plugin_datacache_heap_init (void *cls)
535 struct GNUNET_DATACACHE_PluginEnvironment *env = cls;
536 struct GNUNET_DATACACHE_PluginFunctions *api;
537 struct Plugin *plugin;
539 plugin = GNUNET_new (struct Plugin);
540 plugin->map = GNUNET_CONTAINER_multihashmap_create (1024, /* FIXME: base on quota! */
542 for (unsigned int i = 0; i < NUM_HEAPS; i++)
543 plugin->heaps[i] = GNUNET_CONTAINER_heap_create (
544 GNUNET_CONTAINER_HEAP_ORDER_MIN);
546 api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions);
548 api->get = &heap_plugin_get;
549 api->put = &heap_plugin_put;
550 api->del = &heap_plugin_del;
551 api->get_random = &heap_plugin_get_random;
552 api->get_closest = &heap_plugin_get_closest;
553 LOG (GNUNET_ERROR_TYPE_INFO,
554 _ ("Heap datacache running\n"));
560 * Exit point from the plugin.
562 * @param cls closure (our "struct Plugin")
566 libgnunet_plugin_datacache_heap_done (void *cls)
568 struct GNUNET_DATACACHE_PluginFunctions *api = cls;
569 struct Plugin *plugin = api->cls;
572 for (unsigned int i = 0; i < NUM_HEAPS; i++)
574 while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i])))
576 GNUNET_assert (GNUNET_YES ==
577 GNUNET_CONTAINER_multihashmap_remove (plugin->map,
580 GNUNET_free_non_null (val->path_info);
583 GNUNET_CONTAINER_heap_destroy (plugin->heaps[i]);
585 GNUNET_CONTAINER_multihashmap_destroy (plugin->map);
586 GNUNET_free (plugin);
592 /* end of plugin_datacache_heap.c */