2 This file is part of GNUnet
3 Copyright (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
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 msg set to error message
210 * @return GNUNET_OK on success
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, char **msg)
222 struct Plugin *plugin = cls;
225 value = GNUNET_malloc (sizeof (struct Value) + size);
227 value->data = &value[1];
228 value->expire_heap = GNUNET_CONTAINER_heap_insert (plugin->by_expiration,
230 expiration.abs_value_us);
231 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
234 value->expiration = expiration;
237 struct ZeroAnonByType *zabt;
239 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
240 if (zabt->type == type)
244 zabt = GNUNET_new (struct ZeroAnonByType);
246 GNUNET_CONTAINER_DLL_insert (plugin->zero_head,
250 if (zabt->array_size == zabt->array_pos)
252 GNUNET_array_grow (zabt->array,
254 zabt->array_size * 2 + 4);
256 value->zero_anon_offset = zabt->array_pos;
257 zabt->array[zabt->array_pos++] = value;
260 value->priority = priority;
261 value->anonymity = anonymity;
262 value->replication = replication;
264 memcpy (&value[1], data, size);
265 GNUNET_CONTAINER_multihashmap_put (plugin->keyvalue,
268 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
269 plugin->size += size;
275 * Delete the given value, removing it from the plugin's data
278 * @param plugin the plugin
279 * @param value value to delete
282 delete_value (struct Plugin *plugin,
285 GNUNET_assert (GNUNET_YES ==
286 GNUNET_CONTAINER_multihashmap_remove (plugin->keyvalue,
289 GNUNET_assert (value == GNUNET_CONTAINER_heap_remove_node (value->expire_heap));
290 GNUNET_assert (value == GNUNET_CONTAINER_heap_remove_node (value->replication_heap));
291 if (0 == value->anonymity)
293 struct ZeroAnonByType *zabt;
295 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
296 if (zabt->type == value->type)
298 GNUNET_assert (NULL != zabt);
299 zabt->array[value->zero_anon_offset] = zabt->array[--zabt->array_pos];
300 zabt->array[value->zero_anon_offset]->zero_anon_offset = value->zero_anon_offset;
301 if (0 == zabt->array_pos)
303 GNUNET_array_grow (zabt->array,
306 GNUNET_CONTAINER_DLL_remove (plugin->zero_head,
312 plugin->size -= value->size;
318 * Closure for iterator called during 'get_key'.
324 * Desired result offset / number of results.
331 struct Plugin *plugin;
334 * Requested value hash.
336 const struct GNUNET_HashCode * vhash;
341 enum GNUNET_BLOCK_Type type;
344 * Function to call with the result.
346 PluginDatumProcessor proc;
349 * Closure for 'proc'.
356 * Test if a value matches the specification from the 'get' context
359 * @param value the value to check against the query
360 * @return GNUNET_YES if the value matches
363 match (const struct GetContext *gc,
366 struct GNUNET_HashCode vh;
368 if ( (gc->type != GNUNET_BLOCK_TYPE_ANY) &&
369 (gc->type != value->type) )
371 if (NULL != gc->vhash)
373 GNUNET_CRYPTO_hash (&value[1], value->size, &vh);
374 if (0 != memcmp (&vh, gc->vhash, sizeof (struct GNUNET_HashCode)))
382 * Count number of matching values.
384 * @param cls the 'struct GetContext'
386 * @param val the 'struct Value'
387 * @return GNUNET_YES (continue iteration)
390 count_iterator (void *cls,
391 const struct GNUNET_HashCode *key,
394 struct GetContext *gc = cls;
395 struct Value *value = val;
397 if (GNUNET_NO == match (gc, value))
405 * Obtain matching value at 'offset'.
407 * @param cls the 'struct GetContext'
409 * @param val the 'struct Value'
410 * @return GNUNET_YES (continue iteration), GNUNET_NO if result was found
413 get_iterator (void *cls,
414 const struct GNUNET_HashCode *key,
417 struct GetContext *gc = cls;
418 struct Value *value = val;
420 if (GNUNET_NO == match (gc, value))
422 if (0 != gc->offset--)
425 gc->proc (gc->proc_cls,
433 (uint64_t) (long) value))
434 delete_value (gc->plugin, value);
440 * Get one of the results for a particular key in the datastore.
443 * @param offset offset of the result (modulo num-results);
444 * specific ordering does not matter for the offset
445 * @param key maybe NULL (to match all entries)
446 * @param vhash hash of the value, maybe NULL (to
447 * match all values that have the right key).
448 * Note that for DBlocks there is no difference
449 * betwen key and vhash, but for other blocks
451 * @param type entries of which type are relevant?
452 * Use 0 for any type.
453 * @param proc function to call on each matching value;
454 * will be called with NULL if nothing matches
455 * @param proc_cls closure for proc
458 heap_plugin_get_key (void *cls, uint64_t offset,
459 const struct GNUNET_HashCode *key,
460 const struct GNUNET_HashCode *vhash,
461 enum GNUNET_BLOCK_Type type, PluginDatumProcessor proc,
464 struct Plugin *plugin = cls;
465 struct GetContext gc;
472 gc.proc_cls = proc_cls;
475 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
481 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
484 gc.offset = offset % gc.offset;
485 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
491 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
498 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
501 gc.offset = offset % gc.offset;
502 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
511 * Get a random item for replication. Returns a single, not expired,
512 * random item from those with the highest replication counters. The
513 * item's replication counter is decremented by one IF it was positive
514 * before. Call 'proc' with all values ZERO or NULL if the datastore
518 * @param proc function to call the value (once only).
519 * @param proc_cls closure for proc
522 heap_plugin_get_replication (void *cls,
523 PluginDatumProcessor proc,
526 struct Plugin *plugin = cls;
529 value = GNUNET_CONTAINER_heap_remove_root (plugin->by_replication);
533 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
536 if (value->replication > 0)
538 value->replication--;
539 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
545 /* need a better way to pick a random item, replication level is always 0 */
546 value->replication_heap = GNUNET_CONTAINER_heap_insert (plugin->by_replication,
549 value = GNUNET_CONTAINER_heap_walk_get_next (plugin->by_replication);
560 (uint64_t) (long) value))
561 delete_value (plugin, value);
566 * Get a random item for expiration. Call 'proc' with all values ZERO
567 * or NULL if the datastore is empty.
570 * @param proc function to call the value (once only).
571 * @param proc_cls closure for proc
574 heap_plugin_get_expiration (void *cls, PluginDatumProcessor proc,
577 struct Plugin *plugin = cls;
580 value = GNUNET_CONTAINER_heap_peek (plugin->by_expiration);
584 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
596 (uint64_t) (long) value))
597 delete_value (plugin, value);
602 * Update the priority for a particular key in the datastore. If
603 * the expiration time in value is different than the time found in
604 * the datastore, the higher value should be kept. For the
605 * anonymity level, the lower value is to be used. The specified
606 * priority should be added to the existing priority, ignoring the
609 * @param cls our "struct Plugin*"
610 * @param uid unique identifier of the datum
611 * @param delta by how much should the priority
612 * change? If priority + delta < 0 the
613 * priority should be set to 0 (never go
615 * @param expire new expiration time should be the
616 * MAX of any existing expiration time and
618 * @param msg set to error message
619 * @return GNUNET_OK on success
622 heap_plugin_update (void *cls,
625 struct GNUNET_TIME_Absolute expire, char **msg)
627 struct Plugin *plugin = cls;
630 value = (struct Value*) (long) uid;
631 GNUNET_assert (NULL != value);
632 if (value->expiration.abs_value_us != expire.abs_value_us)
634 value->expiration = expire;
635 GNUNET_CONTAINER_heap_update_cost (plugin->by_expiration,
637 expire.abs_value_us);
639 if ( (delta < 0) && (value->priority < - delta) )
642 value->priority += delta;
648 * Call the given processor on an item with zero anonymity.
650 * @param cls our "struct Plugin*"
651 * @param offset offset of the result (modulo num-results);
652 * specific ordering does not matter for the offset
653 * @param type entries of which type should be considered?
654 * Use 0 for any type.
655 * @param proc function to call on each matching value;
656 * will be called with NULL if no value matches
657 * @param proc_cls closure for proc
660 heap_plugin_get_zero_anonymity (void *cls, uint64_t offset,
661 enum GNUNET_BLOCK_Type type,
662 PluginDatumProcessor proc, void *proc_cls)
664 struct Plugin *plugin = cls;
665 struct ZeroAnonByType *zabt;
670 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
672 if ( (type != GNUNET_BLOCK_TYPE_ANY) &&
673 (type != zabt->type) )
675 count += zabt->array_pos;
680 NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
683 offset = offset % count;
684 for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
686 if ( (type != GNUNET_BLOCK_TYPE_ANY) &&
687 (type != zabt->type) )
689 if (offset >= zabt->array_pos)
691 offset -= zabt->array_pos;
696 GNUNET_assert (NULL != zabt);
697 value = zabt->array[offset];
707 (uint64_t) (long) value))
708 delete_value (plugin, value);
716 heap_plugin_drop (void *cls)
718 /* nothing needs to be done */
723 * Closure for the 'return_value' function.
730 PluginKeyProcessor proc;
733 * Closure for 'proc'.
740 * Callback invoked to call callback on each value.
742 * @param cls the plugin
744 * @param val the value
745 * @return GNUNET_OK (continue to iterate)
748 return_value (void *cls,
749 const struct GNUNET_HashCode *key,
752 struct GetAllContext *gac = cls;
754 gac->proc (gac->proc_cls,
762 * Get all of the keys in the datastore.
765 * @param proc function to call on each key
766 * @param proc_cls closure for proc
769 heap_get_keys (void *cls,
770 PluginKeyProcessor proc,
773 struct Plugin *plugin = cls;
774 struct GetAllContext gac;
777 gac.proc_cls = proc_cls;
778 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
785 * Entry point for the plugin.
787 * @param cls the "struct GNUNET_DATASTORE_PluginEnvironment*"
788 * @return our "struct Plugin*"
791 libgnunet_plugin_datastore_heap_init (void *cls)
793 struct GNUNET_DATASTORE_PluginEnvironment *env = cls;
794 struct GNUNET_DATASTORE_PluginFunctions *api;
795 struct Plugin *plugin;
796 unsigned long long esize;
799 GNUNET_CONFIGURATION_get_value_number (env->cfg,
804 plugin = GNUNET_new (struct Plugin);
806 plugin->keyvalue = GNUNET_CONTAINER_multihashmap_create (esize, GNUNET_YES);
807 plugin->by_expiration = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
808 plugin->by_replication = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
809 api = GNUNET_new (struct GNUNET_DATASTORE_PluginFunctions);
811 api->estimate_size = &heap_plugin_estimate_size;
812 api->put = &heap_plugin_put;
813 api->update = &heap_plugin_update;
814 api->get_key = &heap_plugin_get_key;
815 api->get_replication = &heap_plugin_get_replication;
816 api->get_expiration = &heap_plugin_get_expiration;
817 api->get_zero_anonymity = &heap_plugin_get_zero_anonymity;
818 api->drop = &heap_plugin_drop;
819 api->get_keys = &heap_get_keys;
820 GNUNET_log_from (GNUNET_ERROR_TYPE_INFO, "heap",
821 _("Heap database running\n"));
827 * Callback invoked to free all value.
829 * @param cls the plugin
831 * @param val the value
832 * @return GNUNET_OK (continue to iterate)
835 free_value (void *cls,
836 const struct GNUNET_HashCode *key,
839 struct Plugin *plugin = cls;
840 struct Value *value = val;
842 delete_value (plugin, value);
848 * Exit point from the plugin.
849 * @param cls our "struct Plugin*"
850 * @return always NULL
853 libgnunet_plugin_datastore_heap_done (void *cls)
855 struct GNUNET_DATASTORE_PluginFunctions *api = cls;
856 struct Plugin *plugin = api->cls;
858 GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
861 GNUNET_CONTAINER_multihashmap_destroy (plugin->keyvalue);
862 GNUNET_CONTAINER_heap_destroy (plugin->by_expiration);
863 GNUNET_CONTAINER_heap_destroy (plugin->by_replication);
864 GNUNET_free (plugin);
869 /* end of plugin_datastore_heap.c */