2 This file is part of GNUnet
3 (C) 2012 Christian Grothoff (and other contributing authors)
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., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, 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
187 static unsigned long long
188 heap_plugin_estimate_size (void *cls)
190 struct Plugin *plugin = cls;
197 * Store an item in the datastore.
200 * @param key key for the item
201 * @param size number of bytes in data
202 * @param data content stored
203 * @param type type of the content
204 * @param priority priority of the content
205 * @param anonymity anonymity-level for the content
206 * @param replication replication-level for the content
207 * @param expiration expiration time for the content
208 * @param msg set to error message
209 * @return GNUNET_OK on success
212 heap_plugin_put (void *cls,
213 const struct GNUNET_HashCode * key,
216 enum GNUNET_BLOCK_Type type,
217 uint32_t priority, uint32_t anonymity,
218 uint32_t replication,
219 struct GNUNET_TIME_Absolute expiration, char **msg)
221 struct Plugin *plugin = cls;
224 value = GNUNET_malloc (sizeof (struct Value) + size);
226 value->data = &value[1];
227 value->expire_heap = GNUNET_CONTAINER_heap_insert (plugin->by_expiration,
229 expiration.abs_value);
230 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
233 value->expiration = expiration;
236 struct ZeroAnonByType *zabt;
238 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
239 if (zabt->type == type)
243 zabt = GNUNET_malloc (sizeof (struct ZeroAnonByType));
245 GNUNET_CONTAINER_DLL_insert (plugin->zero_head,
249 if (zabt->array_size == zabt->array_pos)
251 GNUNET_array_grow (zabt->array,
253 zabt->array_size * 2 + 4);
255 value->zero_anon_offset = zabt->array_pos;
256 zabt->array[zabt->array_pos++] = value;
259 value->priority = priority;
260 value->anonymity = anonymity;
261 value->replication = replication;
263 memcpy (&value[1], data, size);
264 GNUNET_CONTAINER_multihashmap_put (plugin->keyvalue,
267 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
268 plugin->size += size;
274 * Delete the given value, removing it from the plugin's data
277 * @param plugin the plugin
278 * @param value value to delete
281 delete_value (struct Plugin *plugin,
284 GNUNET_assert (GNUNET_YES ==
285 GNUNET_CONTAINER_multihashmap_remove (plugin->keyvalue,
288 GNUNET_assert (value == GNUNET_CONTAINER_heap_remove_node (value->expire_heap));
289 GNUNET_assert (value == GNUNET_CONTAINER_heap_remove_node (value->replication_heap));
290 if (0 == value->anonymity)
292 struct ZeroAnonByType *zabt;
294 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
295 if (zabt->type == value->type)
297 GNUNET_assert (NULL != zabt);
298 zabt->array[value->zero_anon_offset] = zabt->array[--zabt->array_pos];
299 zabt->array[value->zero_anon_offset]->zero_anon_offset = value->zero_anon_offset;
300 if (0 == zabt->array_pos)
302 GNUNET_array_grow (zabt->array,
305 GNUNET_CONTAINER_DLL_remove (plugin->zero_head,
311 plugin->size -= value->size;
317 * Closure for iterator called during 'get_key'.
323 * Desired result offset / number of results.
330 struct Plugin *plugin;
333 * Requested value hash.
335 const struct GNUNET_HashCode * vhash;
340 enum GNUNET_BLOCK_Type type;
343 * Function to call with the result.
345 PluginDatumProcessor proc;
348 * Closure for 'proc'.
355 * Test if a value matches the specification from the 'get' context
358 * @param value the value to check against the query
359 * @return GNUNET_YES if the value matches
362 match (const struct GetContext *gc,
365 struct GNUNET_HashCode vh;
367 if ( (gc->type != GNUNET_BLOCK_TYPE_ANY) &&
368 (gc->type != value->type) )
370 if (NULL != gc->vhash)
372 GNUNET_CRYPTO_hash (&value[1], value->size, &vh);
373 if (0 != memcmp (&vh, gc->vhash, sizeof (struct GNUNET_HashCode)))
381 * Count number of matching values.
383 * @param cls the 'struct GetContext'
385 * @param val the 'struct Value'
386 * @return GNUNET_YES (continue iteration)
389 count_iterator (void *cls,
390 const struct GNUNET_HashCode *key,
393 struct GetContext *gc = cls;
394 struct Value *value = val;
396 if (GNUNET_NO == match (gc, value))
404 * Obtain matching value at 'offset'.
406 * @param cls the 'struct GetContext'
408 * @param val the 'struct Value'
409 * @return GNUNET_YES (continue iteration), GNUNET_NO if result was found
412 get_iterator (void *cls,
413 const struct GNUNET_HashCode *key,
416 struct GetContext *gc = cls;
417 struct Value *value = val;
419 if (GNUNET_NO == match (gc, value))
421 if (0 != gc->offset--)
424 gc->proc (gc->proc_cls,
432 (uint64_t) (long) value))
433 delete_value (gc->plugin, value);
439 * Get one of the results for a particular key in the datastore.
442 * @param offset offset of the result (modulo num-results);
443 * specific ordering does not matter for the offset
444 * @param key maybe NULL (to match all entries)
445 * @param vhash hash of the value, maybe NULL (to
446 * match all values that have the right key).
447 * Note that for DBlocks there is no difference
448 * betwen key and vhash, but for other blocks
450 * @param type entries of which type are relevant?
451 * Use 0 for any type.
452 * @param proc function to call on each matching value;
453 * will be called with NULL if nothing matches
454 * @param proc_cls closure for proc
457 heap_plugin_get_key (void *cls, uint64_t offset,
458 const struct GNUNET_HashCode *key,
459 const struct GNUNET_HashCode *vhash,
460 enum GNUNET_BLOCK_Type type, PluginDatumProcessor proc,
463 struct Plugin *plugin = cls;
464 struct GetContext gc;
471 gc.proc_cls = proc_cls;
474 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
480 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
483 gc.offset = offset % gc.offset;
484 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
490 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
497 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
500 gc.offset = offset % gc.offset;
501 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
510 * Get a random item for replication. Returns a single, not expired,
511 * random item from those with the highest replication counters. The
512 * item's replication counter is decremented by one IF it was positive
513 * before. Call 'proc' with all values ZERO or NULL if the datastore
517 * @param proc function to call the value (once only).
518 * @param proc_cls closure for proc
521 heap_plugin_get_replication (void *cls,
522 PluginDatumProcessor proc,
525 struct Plugin *plugin = cls;
528 value = GNUNET_CONTAINER_heap_remove_root (plugin->by_replication);
532 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
535 if (value->replication > 0)
537 value->replication--;
538 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
544 /* need a better way to pick a random item, replication level is always 0 */
545 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
548 value = GNUNET_CONTAINER_heap_walk_get_next (plugin->by_replication);
559 (uint64_t) (long) value))
560 delete_value (plugin, value);
565 * Get a random item for expiration. Call 'proc' with all values ZERO
566 * or NULL if the datastore is empty.
569 * @param proc function to call the value (once only).
570 * @param proc_cls closure for proc
573 heap_plugin_get_expiration (void *cls, PluginDatumProcessor proc,
576 struct Plugin *plugin = cls;
579 value = GNUNET_CONTAINER_heap_peek (plugin->by_expiration);
583 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
595 (uint64_t) (long) value))
596 delete_value (plugin, value);
601 * Update the priority for a particular key in the datastore. If
602 * the expiration time in value is different than the time found in
603 * the datastore, the higher value should be kept. For the
604 * anonymity level, the lower value is to be used. The specified
605 * priority should be added to the existing priority, ignoring the
608 * @param cls our "struct Plugin*"
609 * @param uid unique identifier of the datum
610 * @param delta by how much should the priority
611 * change? If priority + delta < 0 the
612 * priority should be set to 0 (never go
614 * @param expire new expiration time should be the
615 * MAX of any existing expiration time and
617 * @param msg set to error message
618 * @return GNUNET_OK on success
621 heap_plugin_update (void *cls,
624 struct GNUNET_TIME_Absolute expire, char **msg)
626 struct Plugin *plugin = cls;
629 value = (struct Value*) (long) uid;
630 GNUNET_assert (NULL != value);
631 if (value->expiration.abs_value != expire.abs_value)
633 value->expiration = expire;
634 GNUNET_CONTAINER_heap_update_cost (plugin->by_expiration,
638 if ( (delta < 0) && (value->priority < - delta) )
641 value->priority += delta;
647 * Call the given processor on an item with zero anonymity.
649 * @param cls our "struct Plugin*"
650 * @param offset offset of the result (modulo num-results);
651 * specific ordering does not matter for the offset
652 * @param type entries of which type should be considered?
653 * Use 0 for any type.
654 * @param proc function to call on each matching value;
655 * will be called with NULL if no value matches
656 * @param proc_cls closure for proc
659 heap_plugin_get_zero_anonymity (void *cls, uint64_t offset,
660 enum GNUNET_BLOCK_Type type,
661 PluginDatumProcessor proc, void *proc_cls)
663 struct Plugin *plugin = cls;
664 struct ZeroAnonByType *zabt;
669 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
671 if ( (type != GNUNET_BLOCK_TYPE_ANY) &&
672 (type != zabt->type) )
674 count += zabt->array_pos;
679 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
682 offset = offset % count;
683 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
685 if ( (type != GNUNET_BLOCK_TYPE_ANY) &&
686 (type != zabt->type) )
688 if (offset >= zabt->array_pos)
690 offset -= zabt->array_pos;
695 value = zabt->array[offset];
705 (uint64_t) (long) value))
706 delete_value (plugin, value);
714 heap_plugin_drop (void *cls)
716 /* nothing needs to be done */
721 * Closure for the 'return_value' function.
728 PluginKeyProcessor proc;
731 * Closure for 'proc'.
738 * Callback invoked to call callback on each value.
740 * @param cls the plugin
742 * @param val the value
743 * @return GNUNET_OK (continue to iterate)
746 return_value (void *cls,
747 const struct GNUNET_HashCode *key,
750 struct GetAllContext *gac = cls;
752 gac->proc (gac->proc_cls,
760 * Get all of the keys in the datastore.
763 * @param proc function to call on each key
764 * @param proc_cls closure for proc
767 heap_get_keys (void *cls,
768 PluginKeyProcessor proc,
771 struct Plugin *plugin = cls;
772 struct GetAllContext gac;
775 gac.proc_cls = proc_cls;
776 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
783 * Entry point for the plugin.
785 * @param cls the "struct GNUNET_DATASTORE_PluginEnvironment*"
786 * @return our "struct Plugin*"
789 libgnunet_plugin_datastore_heap_init (void *cls)
791 struct GNUNET_DATASTORE_PluginEnvironment *env = cls;
792 struct GNUNET_DATASTORE_PluginFunctions *api;
793 struct Plugin *plugin;
794 unsigned long long esize;
797 GNUNET_CONFIGURATION_get_value_number (env->cfg,
802 plugin = GNUNET_malloc (sizeof (struct Plugin));
804 plugin->keyvalue = GNUNET_CONTAINER_multihashmap_create (esize, GNUNET_YES);
805 plugin->by_expiration = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
806 plugin->by_replication = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
807 api = GNUNET_malloc (sizeof (struct GNUNET_DATASTORE_PluginFunctions));
809 api->estimate_size = &heap_plugin_estimate_size;
810 api->put = &heap_plugin_put;
811 api->update = &heap_plugin_update;
812 api->get_key = &heap_plugin_get_key;
813 api->get_replication = &heap_plugin_get_replication;
814 api->get_expiration = &heap_plugin_get_expiration;
815 api->get_zero_anonymity = &heap_plugin_get_zero_anonymity;
816 api->drop = &heap_plugin_drop;
817 api->get_keys = &heap_get_keys;
818 GNUNET_log_from (GNUNET_ERROR_TYPE_INFO, "heap",
819 _("Heap database running\n"));
825 * Callback invoked to free all value.
827 * @param cls the plugin
829 * @param val the value
830 * @return GNUNET_OK (continue to iterate)
833 free_value (void *cls,
834 const struct GNUNET_HashCode *key,
837 struct Plugin *plugin = cls;
838 struct Value *value = val;
840 delete_value (plugin, value);
846 * Exit point from the plugin.
847 * @param cls our "struct Plugin*"
848 * @return always NULL
851 libgnunet_plugin_datastore_heap_done (void *cls)
853 struct GNUNET_DATASTORE_PluginFunctions *api = cls;
854 struct Plugin *plugin = api->cls;
856 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
859 GNUNET_CONTAINER_multihashmap_destroy (plugin->keyvalue);
860 GNUNET_CONTAINER_heap_destroy (plugin->by_expiration);
861 GNUNET_CONTAINER_heap_destroy (plugin->by_replication);
862 GNUNET_free (plugin);
867 /* end of plugin_datastore_heap.c */