GNUnet  0.10.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, "datacache-heap", op, fn)
33 
34 #define NUM_HEAPS 24
35 
39 struct Plugin
40 {
45 
50 
55 
56 };
57 
58 
62 struct Value
63 {
68 
72  struct GNUNET_TIME_Absolute discard_time;
73 
78 
83 
87  size_t size;
88 
92  unsigned int path_info_len;
93 
97  uint32_t distance;
98 
103 
104 };
105 
106 
107 #define OVERHEAD (sizeof (struct Value) + 64)
108 
109 
114 {
118  struct GNUNET_TIME_Absolute discard_time;
119 
123  const char *data;
124 
129 
133  size_t size;
134 
139 
143  unsigned int path_info_len;
144 
148  int found;
149 };
150 
151 
161 static int
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 GNUNET_PeerIdentity));
188  "Got same value for key %s and type %d (size %u vs %u)\n",
189  GNUNET_h2s (key),
190  val->type,
191  (unsigned int) val->size,
192  (unsigned int) put_ctx->size);
193  return GNUNET_NO;
194  }
195  return GNUNET_YES;
196 }
197 
198 
213 static ssize_t
214 heap_plugin_put (void *cls,
215  const struct GNUNET_HashCode *key,
216  uint32_t xor_distance,
217  size_t size,
218  const char *data,
219  enum GNUNET_BLOCK_Type type,
221  unsigned int path_info_len,
222  const struct GNUNET_PeerIdentity *path_info)
223 {
224  struct Plugin *plugin = cls;
225  struct Value *val;
226  struct PutContext put_ctx;
227 
228  put_ctx.found = GNUNET_NO;
229  put_ctx.data = data;
230  put_ctx.size = size;
231  put_ctx.path_info = path_info;
232  put_ctx.path_info_len = path_info_len;
233  put_ctx.discard_time = discard_time;
234  put_ctx.type = type;
236  key,
237  &put_cb,
238  &put_ctx);
239  if (GNUNET_YES == put_ctx.found)
240  return 0;
241  val = GNUNET_malloc (sizeof (struct Value) + size);
242  GNUNET_memcpy (&val[1],
243  data,
244  size);
245  val->key = *key;
246  val->type = type;
247  val->discard_time = discard_time;
248  val->size = size;
249  if (xor_distance >= NUM_HEAPS)
250  val->distance = NUM_HEAPS - 1;
251  else
252  val->distance = xor_distance;
254  val->path_info_len,
255  path_info_len);
256  GNUNET_memcpy (val->path_info,
257  path_info,
258  path_info_len * sizeof (struct GNUNET_PeerIdentity));
259  (void) GNUNET_CONTAINER_multihashmap_put (plugin->map,
260  &val->key,
261  val,
263  val->hn = GNUNET_CONTAINER_heap_insert (plugin->heaps[val->distance],
264  val,
266  return size + OVERHEAD;
267 }
268 
269 
274 {
279 
283  void *iter_cls;
284 
288  unsigned int cnt;
289 
294 };
295 
296 
297 
307 static int
308 get_cb (void *cls,
309  const struct GNUNET_HashCode *key,
310  void *value)
311 {
312  struct GetContext *get_ctx = cls;
313  struct Value *val = value;
314  int ret;
315 
316  if ( (get_ctx->type != val->type) &&
317  (GNUNET_BLOCK_TYPE_ANY != get_ctx->type) )
318  return GNUNET_OK;
319  if (0 ==
321  return GNUNET_OK;
322  if (NULL != get_ctx->iter)
323  ret = get_ctx->iter (get_ctx->iter_cls,
324  key,
325  val->size,
326  (const char *) &val[1],
327  val->type,
328  val->discard_time,
329  val->path_info_len,
330  val->path_info);
331  else
332  ret = GNUNET_YES;
333  get_ctx->cnt++;
334  return ret;
335 }
336 
337 
349 static unsigned int
350 heap_plugin_get (void *cls,
351  const struct GNUNET_HashCode *key,
352  enum GNUNET_BLOCK_Type type,
354  void *iter_cls)
355 {
356  struct Plugin *plugin = cls;
357  struct GetContext get_ctx;
358 
359  get_ctx.type = type;
360  get_ctx.iter = iter;
361  get_ctx.iter_cls = iter_cls;
362  get_ctx.cnt = 0;
364  key,
365  &get_cb,
366  &get_ctx);
367  return get_ctx.cnt;
368 }
369 
370 
378 static int
379 heap_plugin_del (void *cls)
380 {
381  struct Plugin *plugin = cls;
382  struct Value *val;
383 
384  for (unsigned int i=0;i<NUM_HEAPS;i++)
385  {
386  val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i]);
387  if (NULL != val)
388  break;
389  }
390  if (NULL == val)
391  return GNUNET_SYSERR;
394  &val->key,
395  val));
396  plugin->env->delete_notify (plugin->env->cls,
397  &val->key,
398  val->size + OVERHEAD);
400  GNUNET_free (val);
401  return GNUNET_OK;
402 }
403 
404 
413 static unsigned int
416  void *iter_cls)
417 {
418  struct Plugin *plugin = cls;
419  struct GetContext get_ctx;
420 
421  get_ctx.type = GNUNET_BLOCK_TYPE_ANY;
422  get_ctx.iter = iter;
423  get_ctx.iter_cls = iter_cls;
424  get_ctx.cnt = 0;
426  &get_cb,
427  &get_ctx);
428  return get_ctx.cnt;
429 }
430 
431 
436 {
437  struct Value **values;
438 
439  unsigned int num_results;
440 
441  const struct GNUNET_HashCode *key;
442 };
443 
444 
445 static int
446 find_closest (void *cls,
447  const struct GNUNET_HashCode *key,
448  void *value)
449 {
450  struct GetClosestContext *gcc = cls;
451  struct Value *val = value;
452  unsigned int j;
453 
454  if (1 != GNUNET_CRYPTO_hash_cmp (key,
455  gcc->key))
456  return GNUNET_OK; /* useless */
457  j = gcc->num_results;
458  for (unsigned int i=0;i<gcc->num_results;i++)
459  {
460  if (NULL == gcc->values[i])
461  {
462  j = i;
463  break;
464  }
465  if (1 == GNUNET_CRYPTO_hash_cmp (&gcc->values[i]->key,
466  key))
467  {
468  j = i;
469  break;
470  }
471  }
472  if (j == gcc->num_results)
473  return GNUNET_OK;
474  gcc->values[j] = val;
475  return GNUNET_OK;
476 }
477 
478 
492 static unsigned int
494  const struct GNUNET_HashCode *key,
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  .num_results = num_results,
504  .key = key
505  };
507  &find_closest,
508  &gcc);
509  for (unsigned int i=0;i<num_results;i++)
510  {
511  if (NULL == values[i])
512  return i;
513  iter (iter_cls,
514  &values[i]->key,
515  values[i]->size,
516  (void *) &values[i][1],
517  values[i]->type,
518  values[i]->discard_time,
519  values[i]->path_info_len,
520  values[i]->path_info);
521  }
522  return num_results;
523 }
524 
525 
532 void *
534 {
537  struct Plugin *plugin;
538 
539  plugin = GNUNET_new (struct Plugin);
540  plugin->map = GNUNET_CONTAINER_multihashmap_create (1024, /* FIXME: base on quota! */
541  GNUNET_YES);
542  for (unsigned int i=0;i<NUM_HEAPS;i++)
544  plugin->env = env;
546  api->cls = plugin;
547  api->get = &heap_plugin_get;
548  api->put = &heap_plugin_put;
549  api->del = &heap_plugin_del;
553  _("Heap datacache running\n"));
554  return api;
555 }
556 
557 
564 void *
566 {
568  struct Plugin *plugin = api->cls;
569  struct Value *val;
570 
571  for (unsigned int i=0;i<NUM_HEAPS;i++)
572  {
573  while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i])))
574  {
577  &val->key,
578  val));
580  GNUNET_free (val);
581  }
583  }
585  GNUNET_free (plugin);
586  GNUNET_free (api);
587  return NULL;
588 }
589 
590 
591 
592 /* end of plugin_datacache_heap.c */
void * cls
Closure to pass to all plugin functions.
size_t size
Payload (actual payload follows this struct)
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.
unsigned int path_info_len
Number of entries in path_info.
ssize_t(* 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_PeerIdentity *path_info)
Store an item in the datastore.
int(* del)(void *cls)
Delete the entry with the lowest expiration value from the datacache right now.
uint64_t rel_value_us
The actual value.
void * libgnunet_plugin_datacache_heap_init(void *cls)
Entry point for the plugin.
Any type of block, used as a wildcard when searching.
static struct GNUNET_CONTAINER_MultiHashMap * values
Collection of all values (represented with ValueSet).
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.
size_t size
Number of bytes in data.
GNUNET_BLOCK_Type
Blocks in the datastore and the datacache must have a unique type.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static int heap_plugin_del(void *cls)
Delete the entry with the lowest expiration value from the datacache right now.
uint32_t distance
How close is the hash to us? Determines which heap we are in!
struct GNUNET_CONTAINER_Heap * heaps[24]
Heaps sorted by distance.
char * key
TLS key.
const char * data
Data for the new value.
static int get_cb(void *cls, const struct GNUNET_HashCode *key, void *value)
Function called during GET to find matching blocks.
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_HashMapIterator it, void *it_cls)
Iterate over all entries in the map.
#define GNUNET_NO
Definition: gnunet_common.h:81
struct GNUNET_CONTAINER_MultiHashMap * map
Our hash map.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:78
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
void * iter_cls
Closure for iter.
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 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_PeerIdentity *path_info)
Store an item in the datastore.
static int find_closest(void *cls, const struct GNUNET_HashCode *key, void *value)
static int ret
Final status code.
Definition: gnunet-arm.c:89
const struct GNUNET_HashCode * key
uint64_t abs_value_us
The actual value.
Internal representation of the hash map.
#define OVERHEAD
struct GNUNET_BLOCK_PluginFunctions * api
Plugin API.
Definition: block.c:47
GNUNET_DATACACHE_DeleteNotifyCallback delete_notify
Function to call whenever the plugin needs to discard content that it was asked to store...
#define _(String)
GNU gettext support macro.
Definition: platform.h:208
static struct GNUNET_ATS_SolverFunctions * plugin
Our solver.
struct GNUNET_TIME_Absolute discard_time
Expiration time for the new value.
unsigned int cnt
Number of results found.
Closure for put_cb().
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
#define GNUNET_memcpy(dst, src, n)
int found
Value to set to GNUNET_YES if an equivalent block was found.
static char * value
Value of the record to add/remove.
struct GNUNET_DATACACHE_PluginEnvironment * env
Our execution environment.
unsigned int(* get_closest)(void *cls, const struct GNUNET_HashCode *key, 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.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
GNUNET_DATACACHE_Iterator iter
Function to call for each result.
enum GNUNET_BLOCK_Type type
Type of the block.
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:317
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 returned by the initialization function of the plugin
Handle to a node in a heap.
enum GNUNET_BLOCK_Type type
Block type requested.
Heap with the minimum cost at the root.
#define NUM_HEAPS
void GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap)
Destroys the heap.
A 512-bit hashcode.
static unsigned int heap_plugin_get_random(void *cls, GNUNET_DATACACHE_Iterator iter, void *iter_cls)
Return a random value from the datastore.
struct GNUNET_HashCode key
Key for the entry.
Node in the heap.
Closure for find_closest().
#define GNUNET_SYSERR
Definition: gnunet_common.h:79
void * iter_cls
Iterator cls.
const struct GNUNET_PeerIdentity * path_info
Path information.
Closure for get_cb().
#define LOG(kind,...)
unsigned int path_info_len
Number of entries in path_info.
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.
struct GNUNET_CONTAINER_Heap * GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order)
Create a new heap.
Allow multiple values with the same key.
Entry in the hash map.
static unsigned int heap_plugin_get_closest(void *cls, const struct GNUNET_HashCode *key, 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.
The identity of the host (wraps the signing key of the peer).
unsigned int GNUNET_CONTAINER_multihashmap_get_random(const struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_HashMapIterator it, void *it_cls)
Call it on a random value from the map, or not at all if the map is empty.
unsigned long long size
Size of all values we&#39;re storing.
Handle for a plugin.
Definition: block.c:37
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:278
int GNUNET_CONTAINER_multihashmap_get_multiple(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_HashMapIterator it, void *it_cls)
Iterate over all entries in the map that match a particular key.
void * libgnunet_plugin_datacache_heap_done(void *cls)
Exit point from the plugin.
struct GNUNET_CONTAINER_HeapNode * hn
Corresponding node in the heap.
#define GNUNET_log(kind,...)
void * GNUNET_CONTAINER_heap_remove_root(struct GNUNET_CONTAINER_Heap *heap)
Remove root of the heap.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
int(* 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_PeerIdentity *path_info)
An iterator over a set of items stored in the datacache.
struct GNUNET_TIME_Relative GNUNET_TIME_absolute_get_remaining(struct GNUNET_TIME_Absolute future)
Given a timestamp in the future, how much time remains until then?
Definition: time.c:331
void * cls
Closure to use for callbacks.
enum GNUNET_TESTBED_UnderlayLinkModelType type
the type of this model
Time for absolute times used by GNUnet, in microseconds.
#define GNUNET_YES
Definition: gnunet_common.h:80
unsigned int(* get_random)(void *cls, GNUNET_DATACACHE_Iterator iter, void *iter_cls)
Return a random value from the datastore.
struct GNUNET_TIME_Absolute discard_time
Expiration time.
static int put_cb(void *cls, const struct GNUNET_HashCode *key, void *value)
Function called during PUT to detect if an equivalent block already exists.
uint32_t data
The data value.
struct GNUNET_PeerIdentity * path_info
Path information.
The datastore service will pass a pointer to a struct of this type as the first and only argument to ...
GNUNET_PEERSTORE_Processor iter
Iterator.
enum GNUNET_BLOCK_Type type
Type of the node.
#define GNUNET_malloc(size)
Wrapper around malloc.
unsigned int(* 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.
#define GNUNET_free(ptr)
Wrapper around free.