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
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
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 * Store an item in the datastore.
201 * @param key key for the item
202 * @param size number of bytes in data
203 * @param data content stored
204 * @param type type of the content
205 * @param priority priority of the content
206 * @param anonymity anonymity-level for the content
207 * @param replication replication-level for the content
208 * @param expiration expiration time for the content
209 * @param cont continuation called with success or failure status
210 * @param cont_cls continuation closure
213 heap_plugin_put (void *cls,
214 const struct GNUNET_HashCode * key,
217 enum GNUNET_BLOCK_Type type,
218 uint32_t priority, uint32_t anonymity,
219 uint32_t replication,
220 struct GNUNET_TIME_Absolute expiration,
224 struct Plugin *plugin = cls;
227 value = GNUNET_malloc (sizeof (struct Value) + size);
229 value->data = &value[1];
230 value->expire_heap = GNUNET_CONTAINER_heap_insert (plugin->by_expiration,
232 expiration.abs_value_us);
233 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
236 value->expiration = expiration;
239 struct ZeroAnonByType *zabt;
241 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
242 if (zabt->type == type)
246 zabt = GNUNET_new (struct ZeroAnonByType);
248 GNUNET_CONTAINER_DLL_insert (plugin->zero_head,
252 if (zabt->array_size == zabt->array_pos)
254 GNUNET_array_grow (zabt->array,
256 zabt->array_size * 2 + 4);
258 value->zero_anon_offset = zabt->array_pos;
259 zabt->array[zabt->array_pos++] = value;
262 value->priority = priority;
263 value->anonymity = anonymity;
264 value->replication = replication;
266 GNUNET_memcpy (&value[1], data, size);
267 GNUNET_CONTAINER_multihashmap_put (plugin->keyvalue,
270 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
271 plugin->size += size;
272 cont (cont_cls, key, size, GNUNET_OK, NULL);
277 * Delete the given value, removing it from the plugin's data
280 * @param plugin the plugin
281 * @param value value to delete
284 delete_value (struct Plugin *plugin,
287 GNUNET_assert (GNUNET_YES ==
288 GNUNET_CONTAINER_multihashmap_remove (plugin->keyvalue,
291 GNUNET_assert (value == GNUNET_CONTAINER_heap_remove_node (value->expire_heap));
292 GNUNET_assert (value == GNUNET_CONTAINER_heap_remove_node (value->replication_heap));
293 if (0 == value->anonymity)
295 struct ZeroAnonByType *zabt;
297 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
298 if (zabt->type == value->type)
300 GNUNET_assert (NULL != zabt);
301 zabt->array[value->zero_anon_offset] = zabt->array[--zabt->array_pos];
302 zabt->array[value->zero_anon_offset]->zero_anon_offset = value->zero_anon_offset;
303 if (0 == zabt->array_pos)
305 GNUNET_array_grow (zabt->array,
308 GNUNET_CONTAINER_DLL_remove (plugin->zero_head,
314 plugin->size -= value->size;
320 * Closure for iterator called during 'get_key'.
326 * Desired result offset / number of results.
333 struct Plugin *plugin;
336 * Requested value hash.
338 const struct GNUNET_HashCode * vhash;
343 enum GNUNET_BLOCK_Type type;
346 * Function to call with the result.
348 PluginDatumProcessor proc;
351 * Closure for 'proc'.
358 * Test if a value matches the specification from the 'get' context
361 * @param value the value to check against the query
362 * @return GNUNET_YES if the value matches
365 match (const struct GetContext *gc,
368 struct GNUNET_HashCode vh;
370 if ( (gc->type != GNUNET_BLOCK_TYPE_ANY) &&
371 (gc->type != value->type) )
373 if (NULL != gc->vhash)
375 GNUNET_CRYPTO_hash (&value[1], value->size, &vh);
376 if (0 != memcmp (&vh, gc->vhash, sizeof (struct GNUNET_HashCode)))
384 * Count number of matching values.
386 * @param cls the 'struct GetContext'
388 * @param val the 'struct Value'
389 * @return GNUNET_YES (continue iteration)
392 count_iterator (void *cls,
393 const struct GNUNET_HashCode *key,
396 struct GetContext *gc = cls;
397 struct Value *value = val;
399 if (GNUNET_NO == match (gc, value))
407 * Obtain matching value at 'offset'.
409 * @param cls the 'struct GetContext'
411 * @param val the 'struct Value'
412 * @return GNUNET_YES (continue iteration), GNUNET_NO if result was found
415 get_iterator (void *cls,
416 const struct GNUNET_HashCode *key,
419 struct GetContext *gc = cls;
420 struct Value *value = val;
422 if (GNUNET_NO == match (gc, value))
424 if (0 != gc->offset--)
427 gc->proc (gc->proc_cls,
435 (uint64_t) (long) value))
436 delete_value (gc->plugin, value);
442 * Get one of the results for a particular key in the datastore.
445 * @param offset offset of the result (modulo num-results);
446 * specific ordering does not matter for the offset
447 * @param key maybe NULL (to match all entries)
448 * @param vhash hash of the value, maybe NULL (to
449 * match all values that have the right key).
450 * Note that for DBlocks there is no difference
451 * betwen key and vhash, but for other blocks
453 * @param type entries of which type are relevant?
454 * Use 0 for any type.
455 * @param proc function to call on each matching value;
456 * will be called with NULL if nothing matches
457 * @param proc_cls closure for proc
460 heap_plugin_get_key (void *cls, uint64_t offset,
461 const struct GNUNET_HashCode *key,
462 const struct GNUNET_HashCode *vhash,
463 enum GNUNET_BLOCK_Type type, PluginDatumProcessor proc,
466 struct Plugin *plugin = cls;
467 struct GetContext gc;
474 gc.proc_cls = proc_cls;
477 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
483 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
486 gc.offset = offset % gc.offset;
487 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
493 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
500 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
503 gc.offset = offset % gc.offset;
504 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
513 * Get a random item for replication. Returns a single, not expired,
514 * random item from those with the highest replication counters. The
515 * item's replication counter is decremented by one IF it was positive
516 * before. Call 'proc' with all values ZERO or NULL if the datastore
520 * @param proc function to call the value (once only).
521 * @param proc_cls closure for proc
524 heap_plugin_get_replication (void *cls,
525 PluginDatumProcessor proc,
528 struct Plugin *plugin = cls;
531 value = GNUNET_CONTAINER_heap_remove_root (plugin->by_replication);
535 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
538 if (value->replication > 0)
540 value->replication--;
541 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
547 /* need a better way to pick a random item, replication level is always 0 */
548 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
551 value = GNUNET_CONTAINER_heap_walk_get_next (plugin->by_replication);
562 (uint64_t) (long) value))
563 delete_value (plugin, value);
568 * Get a random item for expiration. Call 'proc' with all values ZERO
569 * or NULL if the datastore is empty.
572 * @param proc function to call the value (once only).
573 * @param proc_cls closure for proc
576 heap_plugin_get_expiration (void *cls, PluginDatumProcessor proc,
579 struct Plugin *plugin = cls;
582 value = GNUNET_CONTAINER_heap_peek (plugin->by_expiration);
586 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
598 (uint64_t) (long) value))
599 delete_value (plugin, value);
604 * Update the priority for a particular key in the datastore. If
605 * the expiration time in value is different than the time found in
606 * the datastore, the higher value should be kept. For the
607 * anonymity level, the lower value is to be used. The specified
608 * priority should be added to the existing priority, ignoring the
611 * @param cls our `struct Plugin *`
612 * @param uid unique identifier of the datum
613 * @param delta by how much should the priority
615 * @param expire new expiration time should be the
616 * MAX of any existing expiration time and
618 * @param cont continuation called with success or failure status
619 * @param cons_cls continuation closure
622 heap_plugin_update (void *cls,
625 struct GNUNET_TIME_Absolute expire,
626 PluginUpdateCont cont,
631 value = (struct Value*) (long) uid;
632 GNUNET_assert (NULL != value);
633 if (value->expiration.abs_value_us != expire.abs_value_us)
635 value->expiration = expire;
636 GNUNET_CONTAINER_heap_update_cost (value->expire_heap,
637 expire.abs_value_us);
639 /* Saturating add, don't overflow */
640 if (value->priority > UINT32_MAX - delta)
641 value->priority = UINT32_MAX;
643 value->priority += delta;
644 cont (cont_cls, GNUNET_OK, NULL);
649 * Call the given processor on an item with zero anonymity.
651 * @param cls our "struct Plugin*"
652 * @param offset offset of the result (modulo num-results);
653 * specific ordering does not matter for the offset
654 * @param type entries of which type should be considered?
655 * Use 0 for any type.
656 * @param proc function to call on each matching value;
657 * will be called with NULL if no value matches
658 * @param proc_cls closure for proc
661 heap_plugin_get_zero_anonymity (void *cls, uint64_t offset,
662 enum GNUNET_BLOCK_Type type,
663 PluginDatumProcessor proc, void *proc_cls)
665 struct Plugin *plugin = cls;
666 struct ZeroAnonByType *zabt;
671 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
673 if ( (type != GNUNET_BLOCK_TYPE_ANY) &&
674 (type != zabt->type) )
676 count += zabt->array_pos;
681 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
684 offset = offset % count;
685 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
687 if ( (type != GNUNET_BLOCK_TYPE_ANY) &&
688 (type != zabt->type) )
690 if (offset >= zabt->array_pos)
692 offset -= zabt->array_pos;
697 GNUNET_assert (NULL != zabt);
698 value = zabt->array[offset];
708 (uint64_t) (long) value))
709 delete_value (plugin, value);
717 heap_plugin_drop (void *cls)
719 /* nothing needs to be done */
724 * Closure for the 'return_value' function.
731 PluginKeyProcessor proc;
734 * Closure for 'proc'.
741 * Callback invoked to call callback on each value.
743 * @param cls the plugin
745 * @param val the value
746 * @return GNUNET_OK (continue to iterate)
749 return_value (void *cls,
750 const struct GNUNET_HashCode *key,
753 struct GetAllContext *gac = cls;
755 gac->proc (gac->proc_cls,
763 * Get all of the keys in the datastore.
766 * @param proc function to call on each key
767 * @param proc_cls closure for proc
770 heap_get_keys (void *cls,
771 PluginKeyProcessor proc,
774 struct Plugin *plugin = cls;
775 struct GetAllContext gac;
778 gac.proc_cls = proc_cls;
779 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
782 proc (proc_cls, NULL, 0);
787 * Entry point for the plugin.
789 * @param cls the "struct GNUNET_DATASTORE_PluginEnvironment*"
790 * @return our "struct Plugin*"
793 libgnunet_plugin_datastore_heap_init (void *cls)
795 struct GNUNET_DATASTORE_PluginEnvironment *env = cls;
796 struct GNUNET_DATASTORE_PluginFunctions *api;
797 struct Plugin *plugin;
798 unsigned long long esize;
801 GNUNET_CONFIGURATION_get_value_number (env->cfg,
806 plugin = GNUNET_new (struct Plugin);
808 plugin->keyvalue = GNUNET_CONTAINER_multihashmap_create (esize, GNUNET_YES);
809 plugin->by_expiration = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
810 plugin->by_replication = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
811 api = GNUNET_new (struct GNUNET_DATASTORE_PluginFunctions);
813 api->estimate_size = &heap_plugin_estimate_size;
814 api->put = &heap_plugin_put;
815 api->update = &heap_plugin_update;
816 api->get_key = &heap_plugin_get_key;
817 api->get_replication = &heap_plugin_get_replication;
818 api->get_expiration = &heap_plugin_get_expiration;
819 api->get_zero_anonymity = &heap_plugin_get_zero_anonymity;
820 api->drop = &heap_plugin_drop;
821 api->get_keys = &heap_get_keys;
822 GNUNET_log_from (GNUNET_ERROR_TYPE_INFO, "heap",
823 _("Heap database running\n"));
829 * Callback invoked to free all value.
831 * @param cls the plugin
833 * @param val the value
834 * @return GNUNET_OK (continue to iterate)
837 free_value (void *cls,
838 const struct GNUNET_HashCode *key,
841 struct Plugin *plugin = cls;
842 struct Value *value = val;
844 delete_value (plugin, value);
850 * Exit point from the plugin.
851 * @param cls our "struct Plugin*"
852 * @return always NULL
855 libgnunet_plugin_datastore_heap_done (void *cls)
857 struct GNUNET_DATASTORE_PluginFunctions *api = cls;
858 struct Plugin *plugin = api->cls;
860 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
863 GNUNET_CONTAINER_multihashmap_destroy (plugin->keyvalue);
864 GNUNET_CONTAINER_heap_destroy (plugin->by_expiration);
865 GNUNET_CONTAINER_heap_destroy (plugin->by_replication);
866 GNUNET_free (plugin);
871 /* end of plugin_datastore_heap.c */