aboutsummaryrefslogtreecommitdiff
path: root/src/datacache/plugin_datacache_heap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/datacache/plugin_datacache_heap.c')
-rw-r--r--src/datacache/plugin_datacache_heap.c592
1 files changed, 0 insertions, 592 deletions
diff --git a/src/datacache/plugin_datacache_heap.c b/src/datacache/plugin_datacache_heap.c
deleted file mode 100644
index 074437e7d..000000000
--- a/src/datacache/plugin_datacache_heap.c
+++ /dev/null
@@ -1,592 +0,0 @@
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
21/**
22 * @file datacache/plugin_datacache_heap.c
23 * @brief heap-only implementation of a database backend for the datacache
24 * @author Christian Grothoff
25 */
26#include "platform.h"
27#include "gnunet_util_lib.h"
28#include "gnunet_datacache_plugin.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
38/**
39 * Context for all functions in this plugin.
40 */
41struct Plugin
42{
43 /**
44 * Our execution environment.
45 */
46 struct GNUNET_DATACACHE_PluginEnvironment *env;
47
48 /**
49 * Our hash map.
50 */
51 struct GNUNET_CONTAINER_MultiHashMap *map;
52
53 /**
54 * Heaps sorted by distance.
55 */
56 struct GNUNET_CONTAINER_Heap *heaps[NUM_HEAPS];
57};
58
59
60/**
61 * Entry in the hash map.
62 */
63struct Value
64{
65 /**
66 * Key for the entry.
67 */
68 struct GNUNET_HashCode key;
69
70 /**
71 * Expiration time.
72 */
73 struct GNUNET_TIME_Absolute discard_time;
74
75 /**
76 * Corresponding node in the heap.
77 */
78 struct GNUNET_CONTAINER_HeapNode *hn;
79
80 /**
81 * Path information.
82 */
83 struct GNUNET_PeerIdentity *path_info;
84
85 /**
86 * Payload (actual payload follows this struct)
87 */
88 size_t size;
89
90 /**
91 * Number of entries in @e path_info.
92 */
93 unsigned int path_info_len;
94
95 /**
96 * How close is the hash to us? Determines which heap we are in!
97 */
98 uint32_t distance;
99
100 /**
101 * Type of the block.
102 */
103 enum GNUNET_BLOCK_Type type;
104};
105
106
107#define OVERHEAD (sizeof(struct Value) + 64)
108
109
110/**
111 * Closure for #put_cb().
112 */
113struct PutContext
114{
115 /**
116 * Expiration time for the new value.
117 */
118 struct GNUNET_TIME_Absolute discard_time;
119
120 /**
121 * Data for the new value.
122 */
123 const char *data;
124
125 /**
126 * Path information.
127 */
128 const struct GNUNET_PeerIdentity *path_info;
129
130 /**
131 * Number of bytes in @e data.
132 */
133 size_t size;
134
135 /**
136 * Type of the node.
137 */
138 enum GNUNET_BLOCK_Type type;
139
140 /**
141 * Number of entries in @e path_info.
142 */
143 unsigned int path_info_len;
144
145 /**
146 * Value to set to #GNUNET_YES if an equivalent block was found.
147 */
148 int found;
149};
150
151
152/**
153 * Function called during PUT to detect if an equivalent block
154 * already exists.
155 *
156 * @param cls the `struct PutContext`
157 * @param key the key for the value(s)
158 * @param value an existing value
159 * @return #GNUNET_YES if not found (to continue to iterate)
160 */
161static int
162put_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;
176 val->discard_time = GNUNET_TIME_absolute_max (val->discard_time,
177 put_ctx->discard_time);
178 /* replace old path with new path */
179 GNUNET_array_grow (val->path_info,
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));
185 GNUNET_CONTAINER_heap_update_cost (val->hn,
186 val->discard_time.abs_value_us);
187 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
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
199/**
200 * Store an item in the datastore.
201 *
202 * @param cls closure (our `struct Plugin`)
203 * @param key key to store data under
204 * @param xor_distance how close is @a key to our PID?
205 * @param size number of bytes in @a data
206 * @param data data to store
207 * @param type type of the value
208 * @param discard_time when to discard the value in any case
209 * @param path_info_len number of entries in @a path_info
210 * @param path_info a path through the network
211 * @return 0 if duplicate, -1 on error, number of bytes used otherwise
212 */
213static ssize_t
214heap_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,
220 struct GNUNET_TIME_Absolute discard_time,
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;
235 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
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;
253 GNUNET_array_grow (val->path_info,
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,
262 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
263 val->hn = GNUNET_CONTAINER_heap_insert (plugin->heaps[val->distance],
264 val,
265 val->discard_time.abs_value_us);
266 return size + OVERHEAD;
267}
268
269
270/**
271 * Closure for #get_cb().
272 */
273struct GetContext
274{
275 /**
276 * Function to call for each result.
277 */
278 GNUNET_DATACACHE_Iterator iter;
279
280 /**
281 * Closure for @e iter.
282 */
283 void *iter_cls;
284
285 /**
286 * Number of results found.
287 */
288 unsigned int cnt;
289
290 /**
291 * Block type requested.
292 */
293 enum GNUNET_BLOCK_Type type;
294};
295
296
297/**
298 * Function called during GET to find matching blocks.
299 * Only matches by type.
300 *
301 * @param cls the `struct GetContext`
302 * @param key the key for the value(s)
303 * @param value an existing value
304 * @return #GNUNET_YES to continue to iterate
305 */
306static int
307get_cb (void *cls,
308 const struct GNUNET_HashCode *key,
309 void *value)
310{
311 struct GetContext *get_ctx = cls;
312 struct Value *val = value;
313 int ret;
314
315 if ((get_ctx->type != val->type) &&
316 (GNUNET_BLOCK_TYPE_ANY != get_ctx->type))
317 return GNUNET_OK;
318 if (0 ==
319 GNUNET_TIME_absolute_get_remaining (val->discard_time).rel_value_us)
320 return GNUNET_OK;
321 if (NULL != get_ctx->iter)
322 ret = get_ctx->iter (get_ctx->iter_cls,
323 key,
324 val->size,
325 (const char *) &val[1],
326 val->type,
327 val->discard_time,
328 val->path_info_len,
329 val->path_info);
330 else
331 ret = GNUNET_YES;
332 get_ctx->cnt++;
333 return ret;
334}
335
336
337/**
338 * Iterate over the results for a particular key
339 * in the datastore.
340 *
341 * @param cls closure (our `struct Plugin`)
342 * @param key
343 * @param type entries of which type are relevant?
344 * @param iter maybe NULL (to just count)
345 * @param iter_cls closure for @a iter
346 * @return the number of results found
347 */
348static unsigned int
349heap_plugin_get (void *cls,
350 const struct GNUNET_HashCode *key,
351 enum GNUNET_BLOCK_Type type,
352 GNUNET_DATACACHE_Iterator iter,
353 void *iter_cls)
354{
355 struct Plugin *plugin = cls;
356 struct GetContext get_ctx;
357
358 get_ctx.type = type;
359 get_ctx.iter = iter;
360 get_ctx.iter_cls = iter_cls;
361 get_ctx.cnt = 0;
362 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
363 key,
364 &get_cb,
365 &get_ctx);
366 return get_ctx.cnt;
367}
368
369
370/**
371 * Delete the entry with the lowest expiration value
372 * from the datacache right now.
373 *
374 * @param cls closure (our `struct Plugin`)
375 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
376 */
377static int
378heap_plugin_del (void *cls)
379{
380 struct Plugin *plugin = cls;
381 struct Value *val;
382
383 for (unsigned int i = 0; i < NUM_HEAPS; i++)
384 {
385 val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i]);
386 if (NULL != val)
387 break;
388 }
389 if (NULL == val)
390 return GNUNET_SYSERR;
391 GNUNET_assert (GNUNET_YES ==
392 GNUNET_CONTAINER_multihashmap_remove (plugin->map,
393 &val->key,
394 val));
395 plugin->env->delete_notify (plugin->env->cls,
396 &val->key,
397 val->size + OVERHEAD);
398 GNUNET_free (val->path_info);
399 GNUNET_free (val);
400 return GNUNET_OK;
401}
402
403
404/**
405 * Return a random value from the datastore.
406 *
407 * @param cls closure (our `struct Plugin`)
408 * @param iter maybe NULL (to just count)
409 * @param iter_cls closure for @a iter
410 * @return the number of results found
411 */
412static unsigned int
413heap_plugin_get_random (void *cls,
414 GNUNET_DATACACHE_Iterator iter,
415 void *iter_cls)
416{
417 struct Plugin *plugin = cls;
418 struct GetContext get_ctx;
419
420 get_ctx.type = GNUNET_BLOCK_TYPE_ANY;
421 get_ctx.iter = iter;
422 get_ctx.iter_cls = iter_cls;
423 get_ctx.cnt = 0;
424 GNUNET_CONTAINER_multihashmap_get_random (plugin->map,
425 &get_cb,
426 &get_ctx);
427 return get_ctx.cnt;
428}
429
430
431/**
432 * Closure for #find_closest().
433 */
434struct GetClosestContext
435{
436 struct Value **values;
437
438 unsigned int num_results;
439
440 const struct GNUNET_HashCode *key;
441};
442
443
444static int
445find_closest (void *cls,
446 const struct GNUNET_HashCode *key,
447 void *value)
448{
449 struct GetClosestContext *gcc = cls;
450 struct Value *val = value;
451 unsigned int j;
452
453 if (1 != GNUNET_CRYPTO_hash_cmp (key,
454 gcc->key))
455 return GNUNET_OK; /* useless */
456 j = gcc->num_results;
457 for (unsigned int i = 0; i < gcc->num_results; i++)
458 {
459 if (NULL == gcc->values[i])
460 {
461 j = i;
462 break;
463 }
464 if (1 == GNUNET_CRYPTO_hash_cmp (&gcc->values[i]->key,
465 key))
466 {
467 j = i;
468 break;
469 }
470 }
471 if (j == gcc->num_results)
472 return GNUNET_OK;
473 gcc->values[j] = val;
474 return GNUNET_OK;
475}
476
477
478/**
479 * Iterate over the results that are "close" to a particular key in
480 * the datacache. "close" is defined as numerically larger than @a
481 * key (when interpreted as a circular address space), with small
482 * distance.
483 *
484 * @param cls closure (internal context for the plugin)
485 * @param key area of the keyspace to look into
486 * @param num_results number of results that should be returned to @a iter
487 * @param iter maybe NULL (to just count)
488 * @param iter_cls closure for @a iter
489 * @return the number of results found
490 */
491static unsigned int
492heap_plugin_get_closest (void *cls,
493 const struct GNUNET_HashCode *key,
494 unsigned int num_results,
495 GNUNET_DATACACHE_Iterator iter,
496 void *iter_cls)
497{
498 struct Plugin *plugin = cls;
499 struct Value *values[num_results];
500 struct GetClosestContext gcc = {
501 .values = values,
502 .num_results = num_results,
503 .key = key
504 };
505
506 GNUNET_CONTAINER_multihashmap_iterate (plugin->map,
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
526/**
527 * Entry point for the plugin.
528 *
529 * @param cls closure (the `struct GNUNET_DATACACHE_PluginEnvironmnet`)
530 * @return the plugin's closure (our `struct Plugin`)
531 */
532void *
533libgnunet_plugin_datacache_heap_init (void *cls)
534{
535 struct GNUNET_DATACACHE_PluginEnvironment *env = cls;
536 struct GNUNET_DATACACHE_PluginFunctions *api;
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++)
543 plugin->heaps[i] = GNUNET_CONTAINER_heap_create (
544 GNUNET_CONTAINER_HEAP_ORDER_MIN);
545 plugin->env = env;
546 api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions);
547 api->cls = plugin;
548 api->get = &heap_plugin_get;
549 api->put = &heap_plugin_put;
550 api->del = &heap_plugin_del;
551 api->get_random = &heap_plugin_get_random;
552 api->get_closest = &heap_plugin_get_closest;
553 LOG (GNUNET_ERROR_TYPE_INFO,
554 _ ("Heap datacache running\n"));
555 return api;
556}
557
558
559/**
560 * Exit point from the plugin.
561 *
562 * @param cls closure (our "struct Plugin")
563 * @return NULL
564 */
565void *
566libgnunet_plugin_datacache_heap_done (void *cls)
567{
568 struct GNUNET_DATACACHE_PluginFunctions *api = cls;
569 struct Plugin *plugin = api->cls;
570 struct Value *val;
571
572 for (unsigned int i = 0; i < NUM_HEAPS; i++)
573 {
574 while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i])))
575 {
576 GNUNET_assert (GNUNET_YES ==
577 GNUNET_CONTAINER_multihashmap_remove (plugin->map,
578 &val->key,
579 val));
580 GNUNET_free (val->path_info);
581 GNUNET_free (val);
582 }
583 GNUNET_CONTAINER_heap_destroy (plugin->heaps[i]);
584 }
585 GNUNET_CONTAINER_multihashmap_destroy (plugin->map);
586 GNUNET_free (plugin);
587 GNUNET_free (api);
588 return NULL;
589}
590
591
592/* end of plugin_datacache_heap.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-23 08:24:25 +0000