GNUnet  0.17.6
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 
41 struct Plugin
42 {
47 
52 
57 };
58 
59 
63 struct Value
64 {
69 
74 
79 
83  uint32_t distance;
84 
85 };
86 
87 
88 #define OVERHEAD (sizeof(struct Value) + 64)
89 
90 
94 struct PutContext
95 {
100 
104  bool found;
105 };
106 
107 
117 static enum GNUNET_GenericReturnValue
118 put_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;
141  val->block.put_path_length = put_ctx->block->put_path_length;
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 
164 static ssize_t
165 heap_plugin_put (void *cls,
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,
191  block->data_size);
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 
241  enum GNUNET_BLOCK_Type type;
242 };
243 
244 
254 static enum GNUNET_GenericReturnValue
255 get_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 
303 static unsigned int
304 heap_plugin_get (void *cls,
305  const struct GNUNET_HashCode *key,
306  enum GNUNET_BLOCK_Type type,
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 
332 static enum GNUNET_GenericReturnValue
333 heap_plugin_del (void *cls)
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));
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 
368  enum GNUNET_BLOCK_Type type;
369 
370  unsigned int num_results;
371 
372 };
373 
374 
375 static enum GNUNET_GenericReturnValue
376 find_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 
427 static unsigned int
429  const struct GNUNET_HashCode *key,
430  enum GNUNET_BLOCK_Type type,
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 
445  &find_closest,
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 
471 void *
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 
503 void *
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
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.
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
struct Plugin * 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 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:220
int GNUNET_CONTAINER_multihashmap_get_multiple(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map that match a particular key.
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.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
@ 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.
Definition: gnunet_common.h:96
@ GNUNET_OK
Definition: gnunet_common.h:99
@ GNUNET_YES
@ GNUNET_NO
Definition: gnunet_common.h:98
@ GNUNET_SYSERR
Definition: gnunet_common.h:97
#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:366
bool GNUNET_TIME_absolute_is_past(struct GNUNET_TIME_Absolute abs)
Test if abs is truly in the past (excluding now).
Definition: time.c:668
#define _(String)
GNU gettext support macro.
Definition: platform.h:177
static enum GNUNET_GenericReturnValue get_cb(void *cls, const struct GNUNET_HashCode *key, void *value)
Function called during GET to find matching blocks.
#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)
void * libgnunet_plugin_datacache_heap_done(void *cls)
Exit point from the plugin.
#define NUM_HEAPS
void * libgnunet_plugin_datacache_heap_init(void *cls)
Entry point for 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,...)
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 ...
GNUNET_DATACACHE_DeleteNotifyCallback delete_notify
Function to call whenever the plugin needs to discard content that it was asked to store.
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!
enum GNUNET_TESTBED_UnderlayLinkModelType type
the type of this model