GNUnet 0.21.0
plugin_datacache_heap.c
Go to the documentation of this file.
1/*
2 This file is part of GNUnet
3 Copyright (C) 2012, 2015, 2022 GNUnet e.V.
4
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.
9
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.
14
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/>.
17
18 SPDX-License-Identifier: AGPL3.0-or-later
19 */
20
26#include "platform.h"
27#include "gnunet_util_lib.h"
29
30#define LOG(kind, ...) GNUNET_log_from (kind, "datacache-heap", __VA_ARGS__)
31
32#define LOG_STRERROR_FILE(kind, op, fn) GNUNET_log_from_strerror_file (kind, \
33 "datacache-heap", \
34 op, fn)
35
36#define NUM_HEAPS 24
37
41struct Plugin
42{
47
52
57};
58
59
63struct Value
64{
69
74
79
83 uint32_t distance;
84
85};
86
87
88#define OVERHEAD (sizeof(struct Value) + 64)
89
90
95{
100
104 bool found;
105};
106
107
118put_cb (void *cls,
119 const struct GNUNET_HashCode *key,
120 void *value)
121{
122 struct PutContext *put_ctx = cls;
123 struct Value *val = value;
124
125 if ((val->block.data_size == put_ctx->block->data_size) &&
126 (val->block.type == put_ctx->block->type) &&
127 (0 == memcmp (val->block.data,
128 put_ctx->block->data,
129 put_ctx->block->data_size)))
130 {
131 put_ctx->found = true;
134 put_ctx->block->expiration_time);
135 /* replace old path with new path */
136 GNUNET_free (val->put_path);
137 val->put_path = GNUNET_memdup (put_ctx->block->put_path,
138 put_ctx->block->put_path_length
139 * sizeof (struct GNUNET_DHT_PathElement));
140 val->block.put_path = val->put_path;
145 "Got same value for key %s and type %u (size %u vs %u)\n",
146 GNUNET_h2s (key),
147 (unsigned int) val->block.type,
148 (unsigned int) val->block.data_size,
149 (unsigned int) put_ctx->block->data_size);
150 return GNUNET_NO;
151 }
152 return GNUNET_YES;
153}
154
155
164static ssize_t
166 uint32_t xor_distance,
167 const struct GNUNET_DATACACHE_Block *block)
168{
169 struct Plugin *plugin = cls;
170 struct Value *val;
171 struct PutContext put_ctx = {
172 .block = block,
173 .found = false
174 };
175
177 "Storing %u bytes under key %s with path length %u\n",
178 (unsigned int) block->data_size,
179 GNUNET_h2s (&block->key),
182 &block->key,
183 &put_cb,
184 &put_ctx);
185 if (GNUNET_YES == put_ctx.found)
186 return 0;
187 val = GNUNET_malloc (sizeof(struct Value)
188 + block->data_size);
189 GNUNET_memcpy (&val[1],
190 block->data,
192 val->block = *block;
193 val->block.data = &val[1];
194 if (xor_distance >= NUM_HEAPS)
195 val->distance = NUM_HEAPS - 1;
196 else
197 val->distance = xor_distance;
198 if (0 != block->put_path_length)
199 {
200 val->put_path
203 * sizeof (struct GNUNET_DHT_PathElement));
204 val->block.put_path = val->put_path;
205 }
207 &val->block.key,
208 val,
211 plugin->heaps[val->distance],
212 val,
214 return val->block.data_size + OVERHEAD;
215}
216
217
222{
227
231 void *iter_cls;
232
236 unsigned int cnt;
237
242};
243
244
255get_cb (void *cls,
256 const struct GNUNET_HashCode *key,
257 void *value)
258{
259 struct GetContext *get_ctx = cls;
260 struct Value *val = value;
262
263 if ( (get_ctx->type != val->block.type) &&
264 (GNUNET_BLOCK_TYPE_ANY != get_ctx->type) )
265 {
267 "Result for key %s does not match block type %d\n",
268 GNUNET_h2s (key),
269 get_ctx->type);
270 return GNUNET_OK;
271 }
273 {
275 "Result for key %s is expired\n",
276 GNUNET_h2s (key));
277 return GNUNET_OK;
278 }
280 "Found result for key %s\n",
281 GNUNET_h2s (key));
282 if (NULL != get_ctx->iter)
283 ret = get_ctx->iter (get_ctx->iter_cls,
284 &val->block);
285 else
286 ret = GNUNET_YES;
287 get_ctx->cnt++;
288 return ret;
289}
290
291
303static unsigned int
305 const struct GNUNET_HashCode *key,
308 void *iter_cls)
309{
310 struct Plugin *plugin = cls;
311 struct GetContext get_ctx;
312
313 get_ctx.type = type;
314 get_ctx.iter = iter;
315 get_ctx.iter_cls = iter_cls;
316 get_ctx.cnt = 0;
318 key,
319 &get_cb,
320 &get_ctx);
321 return get_ctx.cnt;
322}
323
324
334{
335 struct Plugin *plugin = cls;
336 struct Value *val;
337
338 for (unsigned int i = 0; i < NUM_HEAPS; i++)
339 {
341 if (NULL != val)
342 break;
343 }
344 if (NULL == val)
345 return GNUNET_SYSERR;
348 &val->block.key,
349 val));
350 plugin->env->delete_notify (plugin->env->cls,
351 &val->block.key,
352 val->block.data_size + OVERHEAD);
353 GNUNET_free (val->put_path);
354 GNUNET_free (val);
355 return GNUNET_OK;
356}
357
358
363{
364 struct Value **values;
365
366 const struct GNUNET_HashCode *key;
367
369
370 unsigned int num_results;
371
372};
373
374
376find_closest (void *cls,
377 const struct GNUNET_HashCode *key,
378 void *value)
379{
380 struct GetClosestContext *gcc = cls;
381 struct Value *val = value;
382 unsigned int j;
383
384 if (1 != GNUNET_CRYPTO_hash_cmp (key,
385 gcc->key))
386 return GNUNET_OK; /* useless */
387 if ( (val->block.type != gcc->type) &&
388 (GNUNET_BLOCK_TYPE_ANY != gcc->type) )
389 return GNUNET_OK; /* useless */
390 j = gcc->num_results;
391 for (unsigned int i = 0; i < gcc->num_results; i++)
392 {
393 if (NULL == gcc->values[i])
394 {
395 j = i;
396 break;
397 }
398 if (1 ==
400 key))
401 {
402 j = i;
403 break;
404 }
405 }
406 if (j == gcc->num_results)
407 return GNUNET_OK;
408 gcc->values[j] = val;
409 return GNUNET_OK;
410}
411
412
427static unsigned int
429 const struct GNUNET_HashCode *key,
431 unsigned int num_results,
433 void *iter_cls)
434{
435 struct Plugin *plugin = cls;
436 struct Value *values[num_results];
437 struct GetClosestContext gcc = {
438 .values = values,
439 .type = type,
440 .num_results = num_results * 2,
441 .key = key
442 };
443
446 &gcc);
447 for (unsigned int i = 0; i < num_results * 2; i++)
448 {
449 if (NULL == values[i])
450 return i;
451 if ( (NULL != iter) &&
452 (GNUNET_SYSERR ==
453 iter (iter_cls,
454 &values[i]->block)) )
455 {
457 "Ending iteration (client error)\n");
458 return i;
459 }
460 }
461 return num_results * 2;
462}
463
464
471void *
473{
476 struct Plugin *plugin;
477
478 plugin = GNUNET_new (struct Plugin);
479 plugin->map = GNUNET_CONTAINER_multihashmap_create (1024, /* FIXME: base on quota! */
480 GNUNET_YES);
481 for (unsigned int i = 0; i < NUM_HEAPS; i++)
484 plugin->env = env;
486 api->cls = plugin;
487 api->get = &heap_plugin_get;
488 api->put = &heap_plugin_put;
489 api->del = &heap_plugin_del;
490 api->get_closest = &heap_plugin_get_closest;
492 _ ("Heap datacache running\n"));
493 return api;
494}
495
496
503void *
505{
507 struct Plugin *plugin = api->cls;
508 struct Value *val;
509
510 for (unsigned int i = 0; i < NUM_HEAPS; i++)
511 {
512 while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i])))
513 {
516 &val->block.key,
517 val));
518 GNUNET_free (val->put_path);
519 GNUNET_free (val);
520 }
522 }
525 GNUNET_free (api);
526 return NULL;
527}
528
529
530/* end of plugin_datacache_heap.c */
struct GNUNET_MQ_Envelope * env
Definition: 005.c:1
static int ret
Final status code.
Definition: gnunet-arm.c:94
struct TestcasePlugin * plugin
The process handle to the testbed service.
struct GNUNET_HashCode key
The key used in the DHT.
static char * value
Value of the record to add/remove.
static uint32_t type
Type string converted to DNS type value.
static struct GNUNET_CONTAINER_MultiHashMap * values
Collection of all values (represented with ValueSet).
API for database backends for the datacache.
enum GNUNET_GenericReturnValue(* GNUNET_DATACACHE_Iterator)(void *cls, const struct GNUNET_DATACACHE_Block *block)
An iterator over a set of items stored in the datacache.
int GNUNET_CRYPTO_hash_cmp(const struct GNUNET_HashCode *h1, const struct GNUNET_HashCode *h2)
Compare function for HashCodes, producing a total ordering of all hashcodes.
Definition: crypto_hash.c:221
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MultiHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multihashmap_remove(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, const void *value)
Remove the given key-value pair from the map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multihashmap_get_multiple(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_MultiHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map that match a particular key.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE
Allow multiple values with the same key.
void * GNUNET_CONTAINER_heap_remove_root(struct GNUNET_CONTAINER_Heap *heap)
Remove root of the heap.
void GNUNET_CONTAINER_heap_update_cost(struct GNUNET_CONTAINER_HeapNode *node, GNUNET_CONTAINER_HeapCostType new_cost)
Updates the cost of any node in the tree.
struct GNUNET_CONTAINER_HeapNode * GNUNET_CONTAINER_heap_insert(struct GNUNET_CONTAINER_Heap *heap, void *element, GNUNET_CONTAINER_HeapCostType cost)
Inserts a new element into the heap.
struct GNUNET_CONTAINER_Heap * GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order)
Create a new heap.
void GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap)
Destroys the heap.
@ GNUNET_CONTAINER_HEAP_ORDER_MIN
Heap with the minimum cost at the root.
#define GNUNET_log(kind,...)
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
GNUNET_GenericReturnValue
Named constants for return values.
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
@ GNUNET_ERROR_TYPE_DEBUG
@ GNUNET_ERROR_TYPE_INFO
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
#define GNUNET_memdup(buf, size)
Allocate and initialize a block of memory.
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_max(struct GNUNET_TIME_Absolute t1, struct GNUNET_TIME_Absolute t2)
Return the maximum of two absolute time values.
Definition: time.c:367
bool GNUNET_TIME_absolute_is_past(struct GNUNET_TIME_Absolute abs)
Test if abs is truly in the past (excluding now).
Definition: time.c:669
#define _(String)
GNU gettext support macro.
Definition: platform.h:178
static enum GNUNET_GenericReturnValue get_cb(void *cls, const struct GNUNET_HashCode *key, void *value)
Function called during GET to find matching blocks.
void * libgnunet_plugin_datacache_heap_init(void *cls)
Entry point for the plugin.
#define OVERHEAD
static enum GNUNET_GenericReturnValue put_cb(void *cls, const struct GNUNET_HashCode *key, void *value)
Function called during PUT to detect if an equivalent block already exists.
static unsigned int heap_plugin_get(void *cls, const struct GNUNET_HashCode *key, enum GNUNET_BLOCK_Type type, GNUNET_DATACACHE_Iterator iter, void *iter_cls)
Iterate over the results for a particular key in the datastore.
static unsigned int heap_plugin_get_closest(void *cls, const struct GNUNET_HashCode *key, enum GNUNET_BLOCK_Type type, unsigned int num_results, GNUNET_DATACACHE_Iterator iter, void *iter_cls)
Iterate over the results that are "close" to a particular key in the datacache.
static enum GNUNET_GenericReturnValue find_closest(void *cls, const struct GNUNET_HashCode *key, void *value)
#define NUM_HEAPS
void * libgnunet_plugin_datacache_heap_done(void *cls)
Exit point from the plugin.
static enum GNUNET_GenericReturnValue heap_plugin_del(void *cls)
Delete the entry with the lowest expiration value from the datacache right now.
static ssize_t heap_plugin_put(void *cls, uint32_t xor_distance, const struct GNUNET_DATACACHE_Block *block)
Store an item in the datastore.
#define LOG(kind,...)
GNUNET_BLOCK_Type
WARNING: This header is generated! In order to add DHT block types, you must register them in GANA,...
@ GNUNET_BLOCK_TYPE_ANY
Identifier for any block.
void * cls
Closure for all of the callbacks.
Handle to a node in a heap.
Internal representation of the hash map.
Information about a block stored in the datacache.
const struct GNUNET_DHT_PathElement * put_path
PUT path taken by the block, array of peer identities.
enum GNUNET_BLOCK_Type type
Type of the block.
const void * data
Actual block data.
struct GNUNET_HashCode key
Key of the block.
size_t data_size
Number of bytes in data.
unsigned int put_path_length
Length of the put_path array.
struct GNUNET_TIME_Absolute expiration_time
When does the block expire?
The datastore service will pass a pointer to a struct of this type as the first and only argument to ...
void * cls
Closure to use for callbacks.
struct returned by the initialization function of the plugin
void * cls
Closure to pass to all plugin functions.
A (signed) path tracking a block's flow through the DHT is represented by an array of path elements,...
A 512-bit hashcode.
uint64_t abs_value_us
The actual value.
Closure for find_closest().
enum GNUNET_BLOCK_Type type
const struct GNUNET_HashCode * key
Closure for get_cb().
void * iter_cls
Closure for iter.
enum GNUNET_BLOCK_Type type
Block type requested.
GNUNET_DATACACHE_Iterator iter
Function to call for each result.
unsigned int cnt
Number of results found.
Handle for a plugin.
Definition: block.c:38
struct GNUNET_BLOCK_PluginFunctions * api
Plugin API.
Definition: block.c:47
struct GNUNET_DATACACHE_PluginEnvironment * env
Our execution environment.
struct GNUNET_CONTAINER_MultiHashMap * map
Our hash map.
struct GNUNET_CONTAINER_Heap * heaps[24]
Heaps sorted by distance.
Closure for put_cb().
const struct GNUNET_DATACACHE_Block * block
Block data.
bool found
Value to set to true if an equivalent block was found.
Entry in the hash map.
struct GNUNET_CONTAINER_HeapNode * hn
Corresponding node in the heap.
struct GNUNET_DATACACHE_Block block
Block data.
struct GNUNET_DHT_PathElement * put_path
Put path as a non-const pointer.
uint32_t distance
How close is the hash to us? Determines which heap we are in!