GNUnet  0.16.x
plugin_datacache_heap.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet
3  Copyright (C) 2012, 2015 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 {
68  struct GNUNET_HashCode key;
69 
74 
79 
84 
88  size_t size;
89 
93  unsigned int path_info_len;
94 
98  uint32_t distance;
99 
103  enum GNUNET_BLOCK_Type type;
104 };
105 
106 
107 #define OVERHEAD (sizeof(struct Value) + 64)
108 
109 
114 {
119 
123  const char *data;
124 
129 
133  size_t size;
134 
138  enum GNUNET_BLOCK_Type type;
139 
143  unsigned int path_info_len;
144 
148  int found;
149 };
150 
151 
161 static enum GNUNET_GenericReturnValue
162 put_cb (void *cls,
163  const struct GNUNET_HashCode *key,
164  void *value)
165 {
166  struct PutContext *put_ctx = cls;
167  struct Value *val = value;
168 
169  if ((val->size == put_ctx->size) &&
170  (val->type == put_ctx->type) &&
171  (0 == memcmp (&val[1],
172  put_ctx->data,
173  put_ctx->size)))
174  {
175  put_ctx->found = GNUNET_YES;
177  put_ctx->discard_time);
178  /* replace old path with new path */
180  val->path_info_len,
181  put_ctx->path_info_len);
182  GNUNET_memcpy (val->path_info,
183  put_ctx->path_info,
184  put_ctx->path_info_len * sizeof(struct
189  "Got same value for key %s and type %d (size %u vs %u)\n",
190  GNUNET_h2s (key),
191  val->type,
192  (unsigned int) val->size,
193  (unsigned int) put_ctx->size);
194  return GNUNET_NO;
195  }
196  return GNUNET_YES;
197 }
198 
199 
214 static ssize_t
215 heap_plugin_put (void *cls,
216  const struct GNUNET_HashCode *key,
217  uint32_t xor_distance,
218  size_t size,
219  const char *data,
220  enum GNUNET_BLOCK_Type type,
222  unsigned int path_info_len,
223  const struct GNUNET_DHT_PathElement *path_info)
224 {
225  struct Plugin *plugin = cls;
226  struct Value *val;
227  struct PutContext put_ctx = {
228  .data = data,
229  .size = size,
230  .path_info = path_info,
231  .path_info_len = path_info_len,
232  .discard_time = discard_time,
233  .type = type
234  };
235 
237  "Storing %u bytes under key %s with path length %u\n",
238  (unsigned int) size,
239  GNUNET_h2s (key),
240  path_info_len);
242  key,
243  &put_cb,
244  &put_ctx);
245  if (GNUNET_YES == put_ctx.found)
246  return 0;
247  val = GNUNET_malloc (sizeof(struct Value) + size);
248  GNUNET_memcpy (&val[1],
249  data,
250  size);
251  val->key = *key;
252  val->type = type;
253  val->discard_time = discard_time;
254  val->size = size;
255  if (xor_distance >= NUM_HEAPS)
256  val->distance = NUM_HEAPS - 1;
257  else
258  val->distance = xor_distance;
260  val->path_info_len,
261  path_info_len);
262  GNUNET_memcpy (val->path_info,
263  path_info,
264  path_info_len * sizeof(struct GNUNET_DHT_PathElement));
266  &val->key,
267  val,
270  val,
272  return size + OVERHEAD;
273 }
274 
275 
280 {
285 
289  void *iter_cls;
290 
294  unsigned int cnt;
295 
299  enum GNUNET_BLOCK_Type type;
300 };
301 
302 
312 static int
313 get_cb (void *cls,
314  const struct GNUNET_HashCode *key,
315  void *value)
316 {
317  struct GetContext *get_ctx = cls;
318  struct Value *val = value;
319  int ret;
320 
321  if ( (get_ctx->type != val->type) &&
322  (GNUNET_BLOCK_TYPE_ANY != get_ctx->type) )
323  {
325  "Result for key %s does not match block type %d\n",
326  GNUNET_h2s (key),
327  get_ctx->type);
328  return GNUNET_OK;
329  }
331  {
333  "Result for key %s is expired\n",
334  GNUNET_h2s (key));
335  return GNUNET_OK;
336  }
338  "Found result for key %s\n",
339  GNUNET_h2s (key));
340  if (NULL != get_ctx->iter)
341  ret = get_ctx->iter (get_ctx->iter_cls,
342  key,
343  val->size,
344  (const char *) &val[1],
345  val->type,
346  val->discard_time,
347  val->path_info_len,
348  val->path_info);
349  else
350  ret = GNUNET_YES;
351  get_ctx->cnt++;
352  return ret;
353 }
354 
355 
367 static unsigned int
368 heap_plugin_get (void *cls,
369  const struct GNUNET_HashCode *key,
370  enum GNUNET_BLOCK_Type type,
372  void *iter_cls)
373 {
374  struct Plugin *plugin = cls;
375  struct GetContext get_ctx;
376 
377  get_ctx.type = type;
378  get_ctx.iter = iter;
379  get_ctx.iter_cls = iter_cls;
380  get_ctx.cnt = 0;
382  key,
383  &get_cb,
384  &get_ctx);
385  return get_ctx.cnt;
386 }
387 
388 
396 static int
397 heap_plugin_del (void *cls)
398 {
399  struct Plugin *plugin = cls;
400  struct Value *val;
401 
402  for (unsigned int i = 0; i < NUM_HEAPS; i++)
403  {
405  if (NULL != val)
406  break;
407  }
408  if (NULL == val)
409  return GNUNET_SYSERR;
412  &val->key,
413  val));
415  &val->key,
416  val->size + OVERHEAD);
417  GNUNET_free (val->path_info);
418  GNUNET_free (val);
419  return GNUNET_OK;
420 }
421 
422 
427 {
428  struct Value **values;
429 
430  const struct GNUNET_HashCode *key;
431 
432  enum GNUNET_BLOCK_Type type;
433 
434  unsigned int num_results;
435 
436 };
437 
438 
439 static enum GNUNET_GenericReturnValue
440 find_closest (void *cls,
441  const struct GNUNET_HashCode *key,
442  void *value)
443 {
444  struct GetClosestContext *gcc = cls;
445  struct Value *val = value;
446  unsigned int j;
447 
448  if (1 != GNUNET_CRYPTO_hash_cmp (key,
449  gcc->key))
450  return GNUNET_OK; /* useless */
451  if ( (val->type != gcc->type) &&
452  (GNUNET_BLOCK_TYPE_ANY != gcc->type) )
453  return GNUNET_OK; /* useless */
454  j = gcc->num_results;
455  for (unsigned int i = 0; i < gcc->num_results; i++)
456  {
457  if (NULL == gcc->values[i])
458  {
459  j = i;
460  break;
461  }
462  if (1 ==
463  GNUNET_CRYPTO_hash_cmp (&gcc->values[i]->key,
464  key))
465  {
466  j = i;
467  break;
468  }
469  }
470  if (j == gcc->num_results)
471  return GNUNET_OK;
472  gcc->values[j] = val;
473  return GNUNET_OK;
474 }
475 
476 
491 static unsigned int
493  const struct GNUNET_HashCode *key,
494  enum GNUNET_BLOCK_Type type,
495  unsigned int num_results,
497  void *iter_cls)
498 {
499  struct Plugin *plugin = cls;
500  struct Value *values[num_results];
501  struct GetClosestContext gcc = {
502  .values = values,
503  .type = type,
504  .num_results = num_results * 2,
505  .key = key
506  };
507 
509  &find_closest,
510  &gcc);
511  for (unsigned int i = 0; i < num_results * 2; i++)
512  {
513  if (NULL == values[i])
514  return i;
515  iter (iter_cls,
516  &values[i]->key,
517  values[i]->size,
518  (void *) &values[i][1],
519  values[i]->type,
520  values[i]->discard_time,
521  values[i]->path_info_len,
522  values[i]->path_info);
523  }
524  return num_results * 2;
525 }
526 
527 
534 void *
536 {
539  struct Plugin *plugin;
540 
541  plugin = GNUNET_new (struct Plugin);
542  plugin->map = GNUNET_CONTAINER_multihashmap_create (1024, /* FIXME: base on quota! */
543  GNUNET_YES);
544  for (unsigned int i = 0; i < NUM_HEAPS; i++)
547  plugin->env = env;
549  api->cls = plugin;
550  api->get = &heap_plugin_get;
551  api->put = &heap_plugin_put;
552  api->del = &heap_plugin_del;
553  api->get_closest = &heap_plugin_get_closest;
555  _ ("Heap datacache running\n"));
556  return api;
557 }
558 
559 
566 void *
568 {
570  struct Plugin *plugin = api->cls;
571  struct Value *val;
572 
573  for (unsigned int i = 0; i < NUM_HEAPS; i++)
574  {
575  while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i])))
576  {
579  &val->key,
580  val));
581  GNUNET_free (val->path_info);
582  GNUNET_free (val);
583  }
585  }
588  GNUNET_free (api);
589  return NULL;
590 }
591 
592 
593 /* end of plugin_datacache_heap.c */
struct GNUNET_MQ_Envelope * env
Definition: 005.c:1
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.
uint32_t data
The data value.
static char * value
Value of the record to add/remove.
static struct GNUNET_CONTAINER_MultiHashMap * values
Collection of all values (represented with ValueSet).
#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:92
@ GNUNET_OK
Definition: gnunet_common.h:95
@ GNUNET_YES
Definition: gnunet_common.h:97
@ GNUNET_NO
Definition: gnunet_common.h:94
@ GNUNET_SYSERR
Definition: gnunet_common.h:93
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.
enum GNUNET_GenericReturnValue(* GNUNET_DATACACHE_Iterator)(void *cls, const struct GNUNET_HashCode *key, size_t data_size, const char *data, enum GNUNET_BLOCK_Type type, struct GNUNET_TIME_Absolute exp, unsigned int path_info_len, const struct GNUNET_DHT_PathElement *path_info)
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.
int 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.
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_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.
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_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_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
#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.
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
static unsigned int size
Size of the "table".
Definition: peer.c:67
#define _(String)
GNU gettext support macro.
Definition: platform.h:177
#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 ssize_t heap_plugin_put(void *cls, const struct GNUNET_HashCode *key, uint32_t xor_distance, size_t size, const char *data, enum GNUNET_BLOCK_Type type, struct GNUNET_TIME_Absolute discard_time, unsigned int path_info_len, const struct GNUNET_DHT_PathElement *path_info)
Store an item in the datastore.
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 int get_cb(void *cls, const struct GNUNET_HashCode *key, void *value)
Function called during GET to find matching blocks.
#define LOG(kind,...)
static int heap_plugin_del(void *cls)
Delete the entry with the lowest expiration value from the datacache right now.
void * cls
Closure for all of the callbacks.
Handle to a node in a heap.
Internal representation of the hash map.
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.
Time for absolute times used by GNUnet, in microseconds.
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().
unsigned int path_info_len
Number of entries in path_info.
enum GNUNET_BLOCK_Type type
Type of the node.
int found
Value to set to GNUNET_YES if an equivalent block was found.
struct GNUNET_TIME_Absolute discard_time
Expiration time for the new value.
size_t size
Number of bytes in data.
const struct GNUNET_DHT_PathElement * path_info
Path information.
const char * data
Data for the new value.
Entry in the hash map.
struct GNUNET_HashCode key
Key for the entry.
struct GNUNET_DHT_PathElement * path_info
Path information.
size_t size
Payload (actual payload follows this struct)
struct GNUNET_CONTAINER_HeapNode * hn
Corresponding node in the heap.
enum GNUNET_BLOCK_Type type
Type of the block.
struct GNUNET_TIME_Absolute discard_time
Expiration time.
unsigned int path_info_len
Number of entries in path_info.
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