2 This file is part of GNUnet
3 Copyright (C) 2012 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 datastore/plugin_datastore_heap.c
23 * @brief heap-based datastore backend; usually we want the datastore
24 * to be persistent, and storing data in the heap is obviously
25 * NOT going to be persistent; still, this plugin is useful for
26 * testing/benchmarking --- but never for production!
27 * @author Christian Grothoff
31 #include "gnunet_datastore_plugin.h"
35 * A value that we are storing.
42 struct GNUNET_HashCode key;
45 * Pointer to the value's data (allocated at the end of this struct).
50 * Entry for this value in the 'expire' heap.
52 struct GNUNET_CONTAINER_HeapNode *expire_heap;
55 * Entry for this value in the 'replication' heap.
57 struct GNUNET_CONTAINER_HeapNode *replication_heap;
60 * Expiration time for this value.
62 struct GNUNET_TIME_Absolute expiration;
65 * Offset of this value in the array of the 'struct ZeroAnonByType';
66 * only used if anonymity is zero.
68 unsigned int zero_anon_offset;
71 * Number of bytes in 'data'.
76 * Priority of the value.
81 * Anonymity level for the value.
86 * Replication level for the value.
93 enum GNUNET_BLOCK_Type type;
98 * We organize 0-anonymity values in arrays "by type".
100 struct ZeroAnonByType
103 * We keep these in a DLL.
105 struct ZeroAnonByType *next;
108 * We keep these in a DLL.
110 struct ZeroAnonByType *prev;
113 * Array of 0-anonymity items of the given type.
115 struct Value **array;
118 * Allocated size of the array.
120 unsigned int array_size;
123 * First unused offset in 'array'.
125 unsigned int array_pos;
128 * Type of all of the values in 'array'.
130 enum GNUNET_BLOCK_Type type;
135 * Context for all functions in this plugin.
140 * Our execution environment.
142 struct GNUNET_DATASTORE_PluginEnvironment *env;
145 * Mapping from keys to 'struct Value's.
147 struct GNUNET_CONTAINER_MultiHashMap *keyvalue;
150 * Heap organized by minimum expiration time.
152 struct GNUNET_CONTAINER_Heap *by_expiration;
155 * Heap organized by maximum replication value.
157 struct GNUNET_CONTAINER_Heap *by_replication;
160 * Head of list of arrays containing zero-anonymity values by type.
162 struct ZeroAnonByType *zero_head;
165 * Tail of list of arrays containing zero-anonymity values by type.
167 struct ZeroAnonByType *zero_tail;
170 * Size of all values we're storing.
172 unsigned long long size;
177 * Get an estimate of how much space the database is
180 * @param cls our "struct Plugin*"
181 * @return number of bytes used on disk
184 heap_plugin_estimate_size (void *cls, unsigned long long *estimate)
186 struct Plugin *plugin = cls;
188 if (NULL != estimate)
189 *estimate = plugin->size;
194 * Closure for iterator for updating.
199 * Number of bytes in 'data'.
204 * Pointer to the data.
209 * Priority of the value.
214 * Replication level for the value.
216 uint32_t replication;
219 * Expiration time for this value.
221 struct GNUNET_TIME_Absolute expiration;
224 * True if the value was found and updated.
231 * Update the matching value.
233 * @param cls the 'struct UpdateContext'
235 * @param val the 'struct Value'
236 * @return GNUNET_YES (continue iteration), GNUNET_NO if value was found
239 update_iterator (void *cls,
240 const struct GNUNET_HashCode *key,
243 struct UpdateContext *uc = cls;
244 struct Value *value = val;
246 if (value->size != uc->size)
248 if (0 != memcmp (value->data, uc->data, uc->size))
250 uc->expiration = GNUNET_TIME_absolute_max (value->expiration,
252 if (value->expiration.abs_value_us != uc->expiration.abs_value_us)
254 value->expiration = uc->expiration;
255 GNUNET_CONTAINER_heap_update_cost (value->expire_heap,
256 value->expiration.abs_value_us);
258 /* Saturating adds, don't overflow */
259 if (value->priority > UINT32_MAX - uc->priority)
260 value->priority = UINT32_MAX;
262 value->priority += uc->priority;
263 if (value->replication > UINT32_MAX - uc->replication)
264 value->replication = UINT32_MAX;
266 value->replication += uc->replication;
273 * Store an item in the datastore.
276 * @param key key for the item
277 * @param absent true if the key was not found in the bloom filter
278 * @param size number of bytes in data
279 * @param data content stored
280 * @param type type of the content
281 * @param priority priority of the content
282 * @param anonymity anonymity-level for the content
283 * @param replication replication-level for the content
284 * @param expiration expiration time for the content
285 * @param cont continuation called with success or failure status
286 * @param cont_cls continuation closure
289 heap_plugin_put (void *cls,
290 const struct GNUNET_HashCode *key,
294 enum GNUNET_BLOCK_Type type,
297 uint32_t replication,
298 struct GNUNET_TIME_Absolute expiration,
302 struct Plugin *plugin = cls;
307 struct UpdateContext uc;
311 uc.priority = priority;
312 uc.replication = replication;
313 uc.expiration = expiration;
315 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
321 cont (cont_cls, key, size, GNUNET_NO, NULL);
325 value = GNUNET_malloc (sizeof(struct Value) + size);
327 value->data = &value[1];
328 value->expire_heap = GNUNET_CONTAINER_heap_insert (plugin->by_expiration,
330 expiration.abs_value_us);
331 value->replication_heap = GNUNET_CONTAINER_heap_insert (
332 plugin->by_replication,
335 value->expiration = expiration;
338 struct ZeroAnonByType *zabt;
340 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
341 if (zabt->type == type)
345 zabt = GNUNET_new (struct ZeroAnonByType);
347 GNUNET_CONTAINER_DLL_insert (plugin->zero_head,
351 if (zabt->array_size == zabt->array_pos)
353 GNUNET_array_grow (zabt->array,
355 zabt->array_size * 2 + 4);
357 value->zero_anon_offset = zabt->array_pos;
358 zabt->array[zabt->array_pos++] = value;
361 value->priority = priority;
362 value->anonymity = anonymity;
363 value->replication = replication;
365 GNUNET_memcpy (&value[1], data, size);
366 GNUNET_CONTAINER_multihashmap_put (plugin->keyvalue,
369 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
370 plugin->size += size;
371 cont (cont_cls, key, size, GNUNET_OK, NULL);
376 * Delete the given value, removing it from the plugin's data
379 * @param plugin the plugin
380 * @param value value to delete
383 delete_value (struct Plugin *plugin,
386 GNUNET_assert (GNUNET_YES ==
387 GNUNET_CONTAINER_multihashmap_remove (plugin->keyvalue,
390 GNUNET_assert (value == GNUNET_CONTAINER_heap_remove_node (
391 value->expire_heap));
392 GNUNET_assert (value == GNUNET_CONTAINER_heap_remove_node (
393 value->replication_heap));
394 if (0 == value->anonymity)
396 struct ZeroAnonByType *zabt;
398 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
399 if (zabt->type == value->type)
401 GNUNET_assert (NULL != zabt);
402 zabt->array[value->zero_anon_offset] = zabt->array[--zabt->array_pos];
403 zabt->array[value->zero_anon_offset]->zero_anon_offset =
404 value->zero_anon_offset;
405 if (0 == zabt->array_pos)
407 GNUNET_array_grow (zabt->array,
410 GNUNET_CONTAINER_DLL_remove (plugin->zero_head,
416 plugin->size -= value->size;
422 * Closure for iterator called during 'get_key'.
427 * Lowest uid to consider.
432 * Value with lowest uid >= next_uid found so far.
439 enum GNUNET_BLOCK_Type type;
442 * If true, return a random value
449 * Obtain the matching value with the lowest uid >= next_uid.
451 * @param cls the 'struct GetContext'
453 * @param val the 'struct Value'
454 * @return GNUNET_YES (continue iteration), GNUNET_NO if result was found
457 get_iterator (void *cls,
458 const struct GNUNET_HashCode *key,
461 struct GetContext *gc = cls;
462 struct Value *value = val;
464 if ((gc->type != GNUNET_BLOCK_TYPE_ANY) &&
465 (gc->type != value->type))
472 if ((uint64_t) (intptr_t) value < gc->next_uid)
474 if ((NULL != gc->value) &&
483 * Get one of the results for a particular key in the datastore.
486 * @param next_uid return the result with lowest uid >= next_uid
487 * @param random if true, return a random result instead of using next_uid
488 * @param key maybe NULL (to match all entries)
489 * @param type entries of which type are relevant?
490 * Use 0 for any type.
491 * @param proc function to call on the matching value;
492 * will be called with NULL if nothing matches
493 * @param proc_cls closure for @a proc
496 heap_plugin_get_key (void *cls,
499 const struct GNUNET_HashCode *key,
500 enum GNUNET_BLOCK_Type type,
501 PluginDatumProcessor proc,
504 struct Plugin *plugin = cls;
505 struct GetContext gc;
508 gc.next_uid = next_uid;
513 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
519 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
524 if (NULL == gc.value)
526 proc (proc_cls, NULL, 0, NULL, 0, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
529 GNUNET_assert (GNUNET_OK ==
537 gc.value->replication,
538 gc.value->expiration,
539 (uint64_t) (intptr_t) gc.value));
544 * Get a random item for replication. Returns a single, not expired,
545 * random item from those with the highest replication counters. The
546 * item's replication counter is decremented by one IF it was positive
547 * before. Call 'proc' with all values ZERO or NULL if the datastore
551 * @param proc function to call the value (once only).
552 * @param proc_cls closure for proc
555 heap_plugin_get_replication (void *cls,
556 PluginDatumProcessor proc,
559 struct Plugin *plugin = cls;
562 value = GNUNET_CONTAINER_heap_remove_root (plugin->by_replication);
565 proc (proc_cls, NULL, 0, NULL, 0, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
568 if (value->replication > 0)
570 value->replication--;
571 value->replication_heap = GNUNET_CONTAINER_heap_insert (
572 plugin->by_replication,
578 /* need a better way to pick a random item, replication level is always 0 */
579 value->replication_heap = GNUNET_CONTAINER_heap_insert (
580 plugin->by_replication,
583 value = GNUNET_CONTAINER_heap_walk_get_next (plugin->by_replication);
585 GNUNET_assert (GNUNET_OK ==
595 (uint64_t) (intptr_t) value));
600 * Get a random item for expiration. Call 'proc' with all values ZERO
601 * or NULL if the datastore is empty.
604 * @param proc function to call the value (once only).
605 * @param proc_cls closure for proc
608 heap_plugin_get_expiration (void *cls, PluginDatumProcessor proc,
611 struct Plugin *plugin = cls;
614 value = GNUNET_CONTAINER_heap_peek (plugin->by_expiration);
617 proc (proc_cls, NULL, 0, NULL, 0, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
630 (uint64_t) (intptr_t) value))
631 delete_value (plugin, value);
636 * Call the given processor on an item with zero anonymity.
638 * @param cls our "struct Plugin*"
639 * @param next_uid return the result with lowest uid >= next_uid
640 * @param type entries of which type should be considered?
641 * Must not be zero (ANY).
642 * @param proc function to call on each matching value;
643 * will be called with NULL if no value matches
644 * @param proc_cls closure for proc
647 heap_plugin_get_zero_anonymity (void *cls, uint64_t next_uid,
648 enum GNUNET_BLOCK_Type type,
649 PluginDatumProcessor proc, void *proc_cls)
651 struct Plugin *plugin = cls;
652 struct ZeroAnonByType *zabt;
653 struct Value *value = NULL;
655 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
657 if ((type != GNUNET_BLOCK_TYPE_ANY) &&
658 (type != zabt->type))
660 for (int i = 0; i < zabt->array_pos; ++i)
662 if ((uint64_t) (intptr_t) zabt->array[i] < next_uid)
664 if ((NULL != value) &&
665 (zabt->array[i] > value))
667 value = zabt->array[i];
672 proc (proc_cls, NULL, 0, NULL, 0, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
675 GNUNET_assert (GNUNET_OK ==
685 (uint64_t) (intptr_t) value));
693 heap_plugin_drop (void *cls)
695 /* nothing needs to be done */
700 * Closure for the 'return_value' function.
707 PluginKeyProcessor proc;
710 * Closure for 'proc'.
717 * Callback invoked to call callback on each value.
719 * @param cls the plugin
721 * @param val the value
722 * @return GNUNET_OK (continue to iterate)
725 return_value (void *cls,
726 const struct GNUNET_HashCode *key,
729 struct GetAllContext *gac = cls;
731 gac->proc (gac->proc_cls,
739 * Get all of the keys in the datastore.
742 * @param proc function to call on each key
743 * @param proc_cls closure for proc
746 heap_get_keys (void *cls,
747 PluginKeyProcessor proc,
750 struct Plugin *plugin = cls;
751 struct GetAllContext gac;
754 gac.proc_cls = proc_cls;
755 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
758 proc (proc_cls, NULL, 0);
763 * Closure for iterator called during 'remove_key'.
785 * Obtain the matching value with the lowest uid >= next_uid.
787 * @param cls the 'struct GetContext'
789 * @param val the 'struct Value'
790 * @return GNUNET_YES (continue iteration), GNUNET_NO if result was found
793 remove_iterator (void *cls,
794 const struct GNUNET_HashCode *key,
797 struct RemoveContext *rc = cls;
798 struct Value *value = val;
800 if (value->size != rc->size)
802 if (0 != memcmp (value->data, rc->data, rc->size))
810 * Remove a particular key in the datastore.
813 * @param key key for the content
814 * @param size number of bytes in data
815 * @param data content stored
816 * @param cont continuation called with success or failure status
817 * @param cont_cls continuation closure for @a cont
820 heap_plugin_remove_key (void *cls,
821 const struct GNUNET_HashCode *key,
824 PluginRemoveCont cont,
827 struct Plugin *plugin = cls;
828 struct RemoveContext rc;
833 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
837 if (NULL == rc.value)
846 delete_value (plugin,
857 * Entry point for the plugin.
859 * @param cls the "struct GNUNET_DATASTORE_PluginEnvironment*"
860 * @return our "struct Plugin*"
863 libgnunet_plugin_datastore_heap_init (void *cls)
865 struct GNUNET_DATASTORE_PluginEnvironment *env = cls;
866 struct GNUNET_DATASTORE_PluginFunctions *api;
867 struct Plugin *plugin;
868 unsigned long long esize;
871 GNUNET_CONFIGURATION_get_value_number (env->cfg,
876 plugin = GNUNET_new (struct Plugin);
878 plugin->keyvalue = GNUNET_CONTAINER_multihashmap_create (esize, GNUNET_YES);
879 plugin->by_expiration = GNUNET_CONTAINER_heap_create (
880 GNUNET_CONTAINER_HEAP_ORDER_MIN);
881 plugin->by_replication = GNUNET_CONTAINER_heap_create (
882 GNUNET_CONTAINER_HEAP_ORDER_MAX);
883 api = GNUNET_new (struct GNUNET_DATASTORE_PluginFunctions);
885 api->estimate_size = &heap_plugin_estimate_size;
886 api->put = &heap_plugin_put;
887 api->get_key = &heap_plugin_get_key;
888 api->get_replication = &heap_plugin_get_replication;
889 api->get_expiration = &heap_plugin_get_expiration;
890 api->get_zero_anonymity = &heap_plugin_get_zero_anonymity;
891 api->drop = &heap_plugin_drop;
892 api->get_keys = &heap_get_keys;
893 api->remove_key = &heap_plugin_remove_key;
894 GNUNET_log_from (GNUNET_ERROR_TYPE_INFO, "heap",
895 _ ("Heap database running\n"));
901 * Callback invoked to free all value.
903 * @param cls the plugin
905 * @param val the value
906 * @return GNUNET_OK (continue to iterate)
909 free_value (void *cls,
910 const struct GNUNET_HashCode *key,
913 struct Plugin *plugin = cls;
914 struct Value *value = val;
916 delete_value (plugin, value);
922 * Exit point from the plugin.
923 * @param cls our "struct Plugin*"
924 * @return always NULL
927 libgnunet_plugin_datastore_heap_done (void *cls)
929 struct GNUNET_DATASTORE_PluginFunctions *api = cls;
930 struct Plugin *plugin = api->cls;
932 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
935 GNUNET_CONTAINER_multihashmap_destroy (plugin->keyvalue);
936 GNUNET_CONTAINER_heap_destroy (plugin->by_expiration);
937 GNUNET_CONTAINER_heap_destroy (plugin->by_replication);
938 GNUNET_free (plugin);
944 /* end of plugin_datastore_heap.c */