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 {
44 
49 
54 };
55 
56 
60 struct Value {
65 
69  struct GNUNET_TIME_Absolute discard_time;
70 
75 
80 
84  size_t size;
85 
89  unsigned int path_info_len;
90 
94  uint32_t distance;
95 
100 };
101 
102 
103 #define OVERHEAD (sizeof(struct Value) + 64)
104 
105 
109 struct PutContext {
113  struct GNUNET_TIME_Absolute discard_time;
114 
118  const char *data;
119 
124 
128  size_t size;
129 
134 
138  unsigned int path_info_len;
139 
143  int found;
144 };
145 
146 
156 static int
157 put_cb(void *cls,
158  const struct GNUNET_HashCode *key,
159  void *value)
160 {
161  struct PutContext *put_ctx = cls;
162  struct Value *val = value;
163 
164  if ((val->size == put_ctx->size) &&
165  (val->type == put_ctx->type) &&
166  (0 == memcmp(&val[1],
167  put_ctx->data,
168  put_ctx->size)))
169  {
170  put_ctx->found = GNUNET_YES;
172  put_ctx->discard_time);
173  /* replace old path with new path */
175  val->path_info_len,
176  put_ctx->path_info_len);
178  put_ctx->path_info,
179  put_ctx->path_info_len * sizeof(struct GNUNET_PeerIdentity));
183  "Got same value for key %s and type %d (size %u vs %u)\n",
184  GNUNET_h2s(key),
185  val->type,
186  (unsigned int)val->size,
187  (unsigned int)put_ctx->size);
188  return GNUNET_NO;
189  }
190  return GNUNET_YES;
191 }
192 
193 
208 static ssize_t
209 heap_plugin_put(void *cls,
210  const struct GNUNET_HashCode *key,
211  uint32_t xor_distance,
212  size_t size,
213  const char *data,
214  enum GNUNET_BLOCK_Type type,
216  unsigned int path_info_len,
217  const struct GNUNET_PeerIdentity *path_info)
218 {
219  struct Plugin *plugin = cls;
220  struct Value *val;
221  struct PutContext put_ctx;
222 
223  put_ctx.found = GNUNET_NO;
224  put_ctx.data = data;
225  put_ctx.size = size;
226  put_ctx.path_info = path_info;
227  put_ctx.path_info_len = path_info_len;
228  put_ctx.discard_time = discard_time;
229  put_ctx.type = type;
231  key,
232  &put_cb,
233  &put_ctx);
234  if (GNUNET_YES == put_ctx.found)
235  return 0;
236  val = GNUNET_malloc(sizeof(struct Value) + size);
237  GNUNET_memcpy(&val[1],
238  data,
239  size);
240  val->key = *key;
241  val->type = type;
242  val->discard_time = discard_time;
243  val->size = size;
244  if (xor_distance >= NUM_HEAPS)
245  val->distance = NUM_HEAPS - 1;
246  else
247  val->distance = xor_distance;
249  val->path_info_len,
250  path_info_len);
252  path_info,
253  path_info_len * sizeof(struct GNUNET_PeerIdentity));
255  &val->key,
256  val,
258  val->hn = GNUNET_CONTAINER_heap_insert(plugin->heaps[val->distance],
259  val,
261  return size + OVERHEAD;
262 }
263 
264 
268 struct GetContext {
273 
277  void *iter_cls;
278 
282  unsigned int cnt;
283 
288 };
289 
290 
291 
301 static int
302 get_cb(void *cls,
303  const struct GNUNET_HashCode *key,
304  void *value)
305 {
306  struct GetContext *get_ctx = cls;
307  struct Value *val = value;
308  int ret;
309 
310  if ((get_ctx->type != val->type) &&
311  (GNUNET_BLOCK_TYPE_ANY != get_ctx->type))
312  return GNUNET_OK;
313  if (0 ==
315  return GNUNET_OK;
316  if (NULL != get_ctx->iter)
317  ret = get_ctx->iter(get_ctx->iter_cls,
318  key,
319  val->size,
320  (const char *)&val[1],
321  val->type,
322  val->discard_time,
323  val->path_info_len,
324  val->path_info);
325  else
326  ret = GNUNET_YES;
327  get_ctx->cnt++;
328  return ret;
329 }
330 
331 
343 static unsigned int
344 heap_plugin_get(void *cls,
345  const struct GNUNET_HashCode *key,
346  enum GNUNET_BLOCK_Type type,
348  void *iter_cls)
349 {
350  struct Plugin *plugin = cls;
351  struct GetContext get_ctx;
352 
353  get_ctx.type = type;
354  get_ctx.iter = iter;
355  get_ctx.iter_cls = iter_cls;
356  get_ctx.cnt = 0;
358  key,
359  &get_cb,
360  &get_ctx);
361  return get_ctx.cnt;
362 }
363 
364 
372 static int
373 heap_plugin_del(void *cls)
374 {
375  struct Plugin *plugin = cls;
376  struct Value *val;
377 
378  for (unsigned int i = 0; i < NUM_HEAPS; i++)
379  {
380  val = GNUNET_CONTAINER_heap_remove_root(plugin->heaps[i]);
381  if (NULL != val)
382  break;
383  }
384  if (NULL == val)
385  return GNUNET_SYSERR;
388  &val->key,
389  val));
390  plugin->env->delete_notify(plugin->env->cls,
391  &val->key,
392  val->size + OVERHEAD);
394  GNUNET_free(val);
395  return GNUNET_OK;
396 }
397 
398 
407 static unsigned int
410  void *iter_cls)
411 {
412  struct Plugin *plugin = cls;
413  struct GetContext get_ctx;
414 
415  get_ctx.type = GNUNET_BLOCK_TYPE_ANY;
416  get_ctx.iter = iter;
417  get_ctx.iter_cls = iter_cls;
418  get_ctx.cnt = 0;
420  &get_cb,
421  &get_ctx);
422  return get_ctx.cnt;
423 }
424 
425 
430  struct Value **values;
431 
432  unsigned int num_results;
433 
434  const struct GNUNET_HashCode *key;
435 };
436 
437 
438 static int
439 find_closest(void *cls,
440  const struct GNUNET_HashCode *key,
441  void *value)
442 {
443  struct GetClosestContext *gcc = cls;
444  struct Value *val = value;
445  unsigned int j;
446 
447  if (1 != GNUNET_CRYPTO_hash_cmp(key,
448  gcc->key))
449  return GNUNET_OK; /* useless */
450  j = gcc->num_results;
451  for (unsigned int i = 0; i < gcc->num_results; i++)
452  {
453  if (NULL == gcc->values[i])
454  {
455  j = i;
456  break;
457  }
458  if (1 == GNUNET_CRYPTO_hash_cmp(&gcc->values[i]->key,
459  key))
460  {
461  j = i;
462  break;
463  }
464  }
465  if (j == gcc->num_results)
466  return GNUNET_OK;
467  gcc->values[j] = val;
468  return GNUNET_OK;
469 }
470 
471 
485 static unsigned int
487  const struct GNUNET_HashCode *key,
488  unsigned int num_results,
490  void *iter_cls)
491 {
492  struct Plugin *plugin = cls;
493  struct Value *values[num_results];
494  struct GetClosestContext gcc = {
495  .values = values,
496  .num_results = num_results,
497  .key = key
498  };
499 
501  &find_closest,
502  &gcc);
503  for (unsigned int i = 0; i < num_results; i++)
504  {
505  if (NULL == values[i])
506  return i;
507  iter(iter_cls,
508  &values[i]->key,
509  values[i]->size,
510  (void *)&values[i][1],
511  values[i]->type,
512  values[i]->discard_time,
513  values[i]->path_info_len,
514  values[i]->path_info);
515  }
516  return num_results;
517 }
518 
519 
526 void *
528 {
531  struct Plugin *plugin;
532 
533  plugin = GNUNET_new(struct Plugin);
534  plugin->map = GNUNET_CONTAINER_multihashmap_create(1024, /* FIXME: base on quota! */
535  GNUNET_YES);
536  for (unsigned int i = 0; i < NUM_HEAPS; i++)
538  plugin->env = env;
540  api->cls = plugin;
541  api->get = &heap_plugin_get;
542  api->put = &heap_plugin_put;
543  api->del = &heap_plugin_del;
547  _("Heap datacache running\n"));
548  return api;
549 }
550 
551 
558 void *
560 {
562  struct Plugin *plugin = api->cls;
563  struct Value *val;
564 
565  for (unsigned int i = 0; i < NUM_HEAPS; i++)
566  {
567  while (NULL != (val = GNUNET_CONTAINER_heap_remove_root(plugin->heaps[i])))
568  {
571  &val->key,
572  val));
574  GNUNET_free(val);
575  }
577  }
579  GNUNET_free(plugin);
580  GNUNET_free(api);
581  return NULL;
582 }
583 
584 
585 
586 /* 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.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
static int get_cb(void *cls, const struct GNUNET_HashCode *key, void *value)
Function called during GET to find matching blocks.
#define GNUNET_NO
Definition: gnunet_common.h:78
struct GNUNET_CONTAINER_MultiHashMap * map
Our hash map.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
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:46
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:181
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.
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.
unsigned int GNUNET_CONTAINER_multihashmap_get_random(const struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Call it on a random value from the map, or not at all if the map is empty.
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:76
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).
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.
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
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:77
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.
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
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.