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.
43 struct GNUNET_HashCode key;
46 * Pointer to the value's data (allocated at the end of this struct).
51 * Entry for this value in the 'expire' heap.
53 struct GNUNET_CONTAINER_HeapNode *expire_heap;
56 * Entry for this value in the 'replication' heap.
58 struct GNUNET_CONTAINER_HeapNode *replication_heap;
61 * Expiration time for this value.
63 struct GNUNET_TIME_Absolute expiration;
66 * Offset of this value in the array of the 'struct ZeroAnonByType';
67 * only used if anonymity is zero.
69 unsigned int zero_anon_offset;
72 * Number of bytes in 'data'.
77 * Priority of the value.
82 * Anonymity level for the value.
87 * Replication level for the value.
94 enum GNUNET_BLOCK_Type type;
100 * We organize 0-anonymity values in arrays "by type".
102 struct ZeroAnonByType
106 * We keep these in a DLL.
108 struct ZeroAnonByType *next;
111 * We keep these in a DLL.
113 struct ZeroAnonByType *prev;
116 * Array of 0-anonymity items of the given type.
118 struct Value **array;
121 * Allocated size of the array.
123 unsigned int array_size;
126 * First unused offset in 'array'.
128 unsigned int array_pos;
131 * Type of all of the values in 'array'.
133 enum GNUNET_BLOCK_Type type;
138 * Context for all functions in this plugin.
143 * Our execution environment.
145 struct GNUNET_DATASTORE_PluginEnvironment *env;
148 * Mapping from keys to 'struct Value's.
150 struct GNUNET_CONTAINER_MultiHashMap *keyvalue;
153 * Heap organized by minimum expiration time.
155 struct GNUNET_CONTAINER_Heap *by_expiration;
158 * Heap organized by maximum replication value.
160 struct GNUNET_CONTAINER_Heap *by_replication;
163 * Head of list of arrays containing zero-anonymity values by type.
165 struct ZeroAnonByType *zero_head;
168 * Tail of list of arrays containing zero-anonymity values by type.
170 struct ZeroAnonByType *zero_tail;
173 * Size of all values we're storing.
175 unsigned long long size;
181 * Get an estimate of how much space the database is
184 * @param cls our "struct Plugin*"
185 * @return number of bytes used on disk
188 heap_plugin_estimate_size (void *cls, unsigned long long *estimate)
190 struct Plugin *plugin = cls;
192 if (NULL != estimate)
193 *estimate = plugin->size;
198 * Closure for iterator for updating.
203 * Number of bytes in 'data'.
208 * Pointer to the data.
213 * Priority of the value.
218 * Replication level for the value.
220 uint32_t replication;
223 * Expiration time for this value.
225 struct GNUNET_TIME_Absolute expiration;
228 * True if the value was found and updated.
235 * Update the matching value.
237 * @param cls the 'struct UpdateContext'
239 * @param val the 'struct Value'
240 * @return GNUNET_YES (continue iteration), GNUNET_NO if value was found
243 update_iterator (void *cls,
244 const struct GNUNET_HashCode *key,
247 struct UpdateContext *uc = cls;
248 struct Value *value = val;
250 if (value->size != uc->size)
252 if (0 != memcmp (value->data, uc->data, uc->size))
254 uc->expiration = GNUNET_TIME_absolute_max (value->expiration,
256 if (value->expiration.abs_value_us != uc->expiration.abs_value_us)
258 value->expiration = uc->expiration;
259 GNUNET_CONTAINER_heap_update_cost (value->expire_heap,
260 value->expiration.abs_value_us);
262 /* Saturating adds, don't overflow */
263 if (value->priority > UINT32_MAX - uc->priority)
264 value->priority = UINT32_MAX;
266 value->priority += uc->priority;
267 if (value->replication > UINT32_MAX - uc->replication)
268 value->replication = UINT32_MAX;
270 value->replication += uc->replication;
276 * Store an item in the datastore.
279 * @param key key for the item
280 * @param absent true if the key was not found in the bloom filter
281 * @param size number of bytes in data
282 * @param data content stored
283 * @param type type of the content
284 * @param priority priority of the content
285 * @param anonymity anonymity-level for the content
286 * @param replication replication-level for the content
287 * @param expiration expiration time for the content
288 * @param cont continuation called with success or failure status
289 * @param cont_cls continuation closure
292 heap_plugin_put (void *cls,
293 const struct GNUNET_HashCode *key,
297 enum GNUNET_BLOCK_Type type,
300 uint32_t replication,
301 struct GNUNET_TIME_Absolute expiration,
305 struct Plugin *plugin = cls;
309 struct UpdateContext uc;
313 uc.priority = priority;
314 uc.replication = replication;
315 uc.expiration = expiration;
317 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
323 cont (cont_cls, key, size, GNUNET_NO, NULL);
327 value = GNUNET_malloc (sizeof (struct Value) + size);
329 value->data = &value[1];
330 value->expire_heap = GNUNET_CONTAINER_heap_insert (plugin->by_expiration,
332 expiration.abs_value_us);
333 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
336 value->expiration = expiration;
339 struct ZeroAnonByType *zabt;
341 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
342 if (zabt->type == type)
346 zabt = GNUNET_new (struct ZeroAnonByType);
348 GNUNET_CONTAINER_DLL_insert (plugin->zero_head,
352 if (zabt->array_size == zabt->array_pos)
354 GNUNET_array_grow (zabt->array,
356 zabt->array_size * 2 + 4);
358 value->zero_anon_offset = zabt->array_pos;
359 zabt->array[zabt->array_pos++] = value;
362 value->priority = priority;
363 value->anonymity = anonymity;
364 value->replication = replication;
366 GNUNET_memcpy (&value[1], data, size);
367 GNUNET_CONTAINER_multihashmap_put (plugin->keyvalue,
370 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
371 plugin->size += size;
372 cont (cont_cls, key, size, GNUNET_OK, NULL);
377 * Delete the given value, removing it from the plugin's data
380 * @param plugin the plugin
381 * @param value value to delete
384 delete_value (struct Plugin *plugin,
387 GNUNET_assert (GNUNET_YES ==
388 GNUNET_CONTAINER_multihashmap_remove (plugin->keyvalue,
391 GNUNET_assert (value == GNUNET_CONTAINER_heap_remove_node (value->expire_heap));
392 GNUNET_assert (value == GNUNET_CONTAINER_heap_remove_node (value->replication_heap));
393 if (0 == value->anonymity)
395 struct ZeroAnonByType *zabt;
397 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
398 if (zabt->type == value->type)
400 GNUNET_assert (NULL != zabt);
401 zabt->array[value->zero_anon_offset] = zabt->array[--zabt->array_pos];
402 zabt->array[value->zero_anon_offset]->zero_anon_offset = value->zero_anon_offset;
403 if (0 == zabt->array_pos)
405 GNUNET_array_grow (zabt->array,
408 GNUNET_CONTAINER_DLL_remove (plugin->zero_head,
414 plugin->size -= value->size;
420 * Closure for iterator called during 'get_key'.
426 * Lowest uid to consider.
431 * Value with lowest uid >= next_uid found so far.
438 enum GNUNET_BLOCK_Type type;
441 * 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) &&
475 (value > 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 (plugin->by_replication,
577 /* need a better way to pick a random item, replication level is always 0 */
578 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
581 value = GNUNET_CONTAINER_heap_walk_get_next (plugin->by_replication);
583 GNUNET_assert (GNUNET_OK ==
593 (uint64_t) (intptr_t) value));
598 * Get a random item for expiration. Call 'proc' with all values ZERO
599 * or NULL if the datastore is empty.
602 * @param proc function to call the value (once only).
603 * @param proc_cls closure for proc
606 heap_plugin_get_expiration (void *cls, PluginDatumProcessor proc,
609 struct Plugin *plugin = cls;
612 value = GNUNET_CONTAINER_heap_peek (plugin->by_expiration);
615 proc (proc_cls, NULL, 0, NULL, 0, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
628 (uint64_t) (intptr_t) value))
629 delete_value (plugin, value);
634 * Call the given processor on an item with zero anonymity.
636 * @param cls our "struct Plugin*"
637 * @param next_uid return the result with lowest uid >= next_uid
638 * @param type entries of which type should be considered?
639 * Must not be zero (ANY).
640 * @param proc function to call on each matching value;
641 * will be called with NULL if no value matches
642 * @param proc_cls closure for proc
645 heap_plugin_get_zero_anonymity (void *cls, uint64_t next_uid,
646 enum GNUNET_BLOCK_Type type,
647 PluginDatumProcessor proc, void *proc_cls)
649 struct Plugin *plugin = cls;
650 struct ZeroAnonByType *zabt;
651 struct Value *value = NULL;
653 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
655 if ( (type != GNUNET_BLOCK_TYPE_ANY) &&
656 (type != zabt->type) )
658 for (int i = 0; i < zabt->array_pos; ++i)
660 if ( (uint64_t) (intptr_t) zabt->array[i] < next_uid)
662 if ( (NULL != value) &&
663 (zabt->array[i] > value) )
665 value = zabt->array[i];
670 proc (proc_cls, NULL, 0, NULL, 0, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
673 GNUNET_assert (GNUNET_OK ==
683 (uint64_t) (intptr_t) value));
691 heap_plugin_drop (void *cls)
693 /* nothing needs to be done */
698 * Closure for the 'return_value' function.
705 PluginKeyProcessor proc;
708 * Closure for 'proc'.
715 * Callback invoked to call callback on each value.
717 * @param cls the plugin
719 * @param val the value
720 * @return GNUNET_OK (continue to iterate)
723 return_value (void *cls,
724 const struct GNUNET_HashCode *key,
727 struct GetAllContext *gac = cls;
729 gac->proc (gac->proc_cls,
737 * Get all of the keys in the datastore.
740 * @param proc function to call on each key
741 * @param proc_cls closure for proc
744 heap_get_keys (void *cls,
745 PluginKeyProcessor proc,
748 struct Plugin *plugin = cls;
749 struct GetAllContext gac;
752 gac.proc_cls = proc_cls;
753 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
756 proc (proc_cls, NULL, 0);
761 * 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 (GNUNET_CONTAINER_HEAP_ORDER_MIN);
880 plugin->by_replication = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
881 api = GNUNET_new (struct GNUNET_DATASTORE_PluginFunctions);
883 api->estimate_size = &heap_plugin_estimate_size;
884 api->put = &heap_plugin_put;
885 api->get_key = &heap_plugin_get_key;
886 api->get_replication = &heap_plugin_get_replication;
887 api->get_expiration = &heap_plugin_get_expiration;
888 api->get_zero_anonymity = &heap_plugin_get_zero_anonymity;
889 api->drop = &heap_plugin_drop;
890 api->get_keys = &heap_get_keys;
891 api->remove_key = &heap_plugin_remove_key;
892 GNUNET_log_from (GNUNET_ERROR_TYPE_INFO, "heap",
893 _("Heap database running\n"));
899 * Callback invoked to free all value.
901 * @param cls the plugin
903 * @param val the value
904 * @return GNUNET_OK (continue to iterate)
907 free_value (void *cls,
908 const struct GNUNET_HashCode *key,
911 struct Plugin *plugin = cls;
912 struct Value *value = val;
914 delete_value (plugin, value);
920 * Exit point from the plugin.
921 * @param cls our "struct Plugin*"
922 * @return always NULL
925 libgnunet_plugin_datastore_heap_done (void *cls)
927 struct GNUNET_DATASTORE_PluginFunctions *api = cls;
928 struct Plugin *plugin = api->cls;
930 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
933 GNUNET_CONTAINER_multihashmap_destroy (plugin->keyvalue);
934 GNUNET_CONTAINER_heap_destroy (plugin->by_expiration);
935 GNUNET_CONTAINER_heap_destroy (plugin->by_replication);
936 GNUNET_free (plugin);
941 /* end of plugin_datastore_heap.c */