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.c593
1 files changed, 0 insertions, 593 deletions
diff --git a/src/datacache/plugin_datacache_heap.c b/src/datacache/plugin_datacache_heap.c
deleted file mode 100644
index 5b50468a5..000000000
--- a/src/datacache/plugin_datacache_heap.c
+++ /dev/null
@@ -1,593 +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_DHT_PathElement *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_DHT_PathElement *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 enum GNUNET_GenericReturnValue
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
185 GNUNET_DHT_PathElement));
186 GNUNET_CONTAINER_heap_update_cost (val->hn,
187 val->discard_time.abs_value_us);
188 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
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
200/**
201 * Store an item in the datastore.
202 *
203 * @param cls closure (our `struct Plugin`)
204 * @param key key to store data under
205 * @param xor_distance how close is @a key to our PID?
206 * @param size number of bytes in @a data
207 * @param data data to store
208 * @param type type of the value
209 * @param discard_time when to discard the value in any case
210 * @param path_info_len number of entries in @a path_info
211 * @param path_info a path through the network
212 * @return 0 if duplicate, -1 on error, number of bytes used otherwise
213 */
214static ssize_t
215heap_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,
221 struct GNUNET_TIME_Absolute discard_time,
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
236 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
237 "Storing %u bytes under key %s with path length %u\n",
238 (unsigned int) size,
239 GNUNET_h2s (key),
240 path_info_len);
241 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
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;
259 GNUNET_array_grow (val->path_info,
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));
265 (void) GNUNET_CONTAINER_multihashmap_put (plugin->map,
266 &val->key,
267 val,
268 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
269 val->hn = GNUNET_CONTAINER_heap_insert (plugin->heaps[val->distance],
270 val,
271 val->discard_time.abs_value_us);
272 return size + OVERHEAD;
273}
274
275
276/**
277 * Closure for #get_cb().
278 */
279struct GetContext
280{
281 /**
282 * Function to call for each result.
283 */
284 GNUNET_DATACACHE_Iterator iter;
285
286 /**
287 * Closure for @e iter.
288 */
289 void *iter_cls;
290
291 /**
292 * Number of results found.
293 */
294 unsigned int cnt;
295
296 /**
297 * Block type requested.
298 */
299 enum GNUNET_BLOCK_Type type;
300};
301
302
303/**
304 * Function called during GET to find matching blocks.
305 * Only matches by type.
306 *
307 * @param cls the `struct GetContext`
308 * @param key the key for the value(s)
309 * @param value an existing value
310 * @return #GNUNET_YES to continue to iterate
311 */
312static int
313get_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 {
324 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
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 }
330 if (GNUNET_TIME_absolute_is_past (val->discard_time))
331 {
332 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
333 "Result for key %s is expired\n",
334 GNUNET_h2s (key));
335 return GNUNET_OK;
336 }
337 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
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
356/**
357 * Iterate over the results for a particular key
358 * in the datastore.
359 *
360 * @param cls closure (our `struct Plugin`)
361 * @param key
362 * @param type entries of which type are relevant?
363 * @param iter maybe NULL (to just count)
364 * @param iter_cls closure for @a iter
365 * @return the number of results found
366 */
367static unsigned int
368heap_plugin_get (void *cls,
369 const struct GNUNET_HashCode *key,
370 enum GNUNET_BLOCK_Type type,
371 GNUNET_DATACACHE_Iterator iter,
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;
381 GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
382 key,
383 &get_cb,
384 &get_ctx);
385 return get_ctx.cnt;
386}
387
388
389/**
390 * Delete the entry with the lowest expiration value
391 * from the datacache right now.
392 *
393 * @param cls closure (our `struct Plugin`)
394 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
395 */
396static int
397heap_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 {
404 val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i]);
405 if (NULL != val)
406 break;
407 }
408 if (NULL == val)
409 return GNUNET_SYSERR;
410 GNUNET_assert (GNUNET_YES ==
411 GNUNET_CONTAINER_multihashmap_remove (plugin->map,
412 &val->key,
413 val));
414 plugin->env->delete_notify (plugin->env->cls,
415 &val->key,
416 val->size + OVERHEAD);
417 GNUNET_free (val->path_info);
418 GNUNET_free (val);
419 return GNUNET_OK;
420}
421
422
423/**
424 * Closure for #find_closest().
425 */
426struct GetClosestContext
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
439static enum GNUNET_GenericReturnValue
440find_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
477/**
478 * Iterate over the results that are "close" to a particular key in
479 * the datacache. "close" is defined as numerically larger than @a
480 * key (when interpreted as a circular address space), with small
481 * distance.
482 *
483 * @param cls closure (internal context for the plugin)
484 * @param key area of the keyspace to look into
485 * @param type desired block type for the replies
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 enum GNUNET_BLOCK_Type type,
495 unsigned int num_results,
496 GNUNET_DATACACHE_Iterator iter,
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
508 GNUNET_CONTAINER_multihashmap_iterate (plugin->map,
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
528/**
529 * Entry point for the plugin.
530 *
531 * @param cls closure (the `struct GNUNET_DATACACHE_PluginEnvironmnet`)
532 * @return the plugin's closure (our `struct Plugin`)
533 */
534void *
535libgnunet_plugin_datacache_heap_init (void *cls)
536{
537 struct GNUNET_DATACACHE_PluginEnvironment *env = cls;
538 struct GNUNET_DATACACHE_PluginFunctions *api;
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++)
545 plugin->heaps[i] = GNUNET_CONTAINER_heap_create (
546 GNUNET_CONTAINER_HEAP_ORDER_MIN);
547 plugin->env = env;
548 api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions);
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;
554 LOG (GNUNET_ERROR_TYPE_INFO,
555 _ ("Heap datacache running\n"));
556 return api;
557}
558
559
560/**
561 * Exit point from the plugin.
562 *
563 * @param cls closure (our "struct Plugin")
564 * @return NULL
565 */
566void *
567libgnunet_plugin_datacache_heap_done (void *cls)
568{
569 struct GNUNET_DATACACHE_PluginFunctions *api = cls;
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 {
577 GNUNET_assert (GNUNET_YES ==
578 GNUNET_CONTAINER_multihashmap_remove (plugin->map,
579 &val->key,
580 val));
581 GNUNET_free (val->path_info);
582 GNUNET_free (val);
583 }
584 GNUNET_CONTAINER_heap_destroy (plugin->heaps[i]);
585 }
586 GNUNET_CONTAINER_multihashmap_destroy (plugin->map);
587 GNUNET_free (plugin);
588 GNUNET_free (api);
589 return NULL;
590}
591
592
593/* end of plugin_datacache_heap.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-26 02:43:13 +0000