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.c143
1 files changed, 115 insertions, 28 deletions
diff --git a/src/datacache/plugin_datacache_heap.c b/src/datacache/plugin_datacache_heap.c
index 49e60bca1..ad5e7834d 100644
--- a/src/datacache/plugin_datacache_heap.c
+++ b/src/datacache/plugin_datacache_heap.c
@@ -31,7 +31,7 @@
31 31
32#define LOG_STRERROR_FILE(kind,op,fn) GNUNET_log_from_strerror_file (kind, "datacache-heap", op, fn) 32#define LOG_STRERROR_FILE(kind,op,fn) GNUNET_log_from_strerror_file (kind, "datacache-heap", op, fn)
33 33
34 34#define NUM_HEAPS 24
35 35
36/** 36/**
37 * Context for all functions in this plugin. 37 * Context for all functions in this plugin.
@@ -49,9 +49,9 @@ struct Plugin
49 struct GNUNET_CONTAINER_MultiHashMap *map; 49 struct GNUNET_CONTAINER_MultiHashMap *map;
50 50
51 /** 51 /**
52 * Heap for expirations. 52 * Heaps sorted by distance.
53 */ 53 */
54 struct GNUNET_CONTAINER_Heap *heap; 54 struct GNUNET_CONTAINER_Heap *heaps[NUM_HEAPS];
55 55
56}; 56};
57 57
@@ -92,6 +92,11 @@ struct Value
92 unsigned int path_info_len; 92 unsigned int path_info_len;
93 93
94 /** 94 /**
95 * How close is the hash to us? Determines which heap we are in!
96 */
97 uint32_t distance;
98
99 /**
95 * Type of the block. 100 * Type of the block.
96 */ 101 */
97 enum GNUNET_BLOCK_Type type; 102 enum GNUNET_BLOCK_Type type;
@@ -118,11 +123,6 @@ struct PutContext
118 const char *data; 123 const char *data;
119 124
120 /** 125 /**
121 * Heap from the plugin.
122 */
123 struct GNUNET_CONTAINER_Heap *heap;
124
125 /**
126 * Path information. 126 * Path information.
127 */ 127 */
128 const struct GNUNET_PeerIdentity *path_info; 128 const struct GNUNET_PeerIdentity *path_info;
@@ -168,7 +168,9 @@ put_cb (void *cls,
168 168
169 if ( (val->size == put_ctx->size) && 169 if ( (val->size == put_ctx->size) &&
170 (val->type == put_ctx->type) && 170 (val->type == put_ctx->type) &&
171 (0 == memcmp (&val[1], put_ctx->data, put_ctx->size)) ) 171 (0 == memcmp (&val[1],
172 put_ctx->data,
173 put_ctx->size)) )
172 { 174 {
173 put_ctx->found = GNUNET_YES; 175 put_ctx->found = GNUNET_YES;
174 val->discard_time = GNUNET_TIME_absolute_max (val->discard_time, 176 val->discard_time = GNUNET_TIME_absolute_max (val->discard_time,
@@ -178,8 +180,8 @@ put_cb (void *cls,
178 val->path_info_len, 180 val->path_info_len,
179 put_ctx->path_info_len); 181 put_ctx->path_info_len);
180 GNUNET_memcpy (val->path_info, 182 GNUNET_memcpy (val->path_info,
181 put_ctx->path_info, 183 put_ctx->path_info,
182 put_ctx->path_info_len * sizeof (struct GNUNET_PeerIdentity)); 184 put_ctx->path_info_len * sizeof (struct GNUNET_PeerIdentity));
183 GNUNET_CONTAINER_heap_update_cost (val->hn, 185 GNUNET_CONTAINER_heap_update_cost (val->hn,
184 val->discard_time.abs_value_us); 186 val->discard_time.abs_value_us);
185 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 187 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
@@ -199,6 +201,7 @@ put_cb (void *cls,
199 * 201 *
200 * @param cls closure (our `struct Plugin`) 202 * @param cls closure (our `struct Plugin`)
201 * @param key key to store data under 203 * @param key key to store data under
204 * @param xor_distance how close is @a key to our PID?
202 * @param size number of bytes in @a data 205 * @param size number of bytes in @a data
203 * @param data data to store 206 * @param data data to store
204 * @param type type of the value 207 * @param type type of the value
@@ -210,6 +213,7 @@ put_cb (void *cls,
210static ssize_t 213static ssize_t
211heap_plugin_put (void *cls, 214heap_plugin_put (void *cls,
212 const struct GNUNET_HashCode *key, 215 const struct GNUNET_HashCode *key,
216 uint32_t xor_distance,
213 size_t size, 217 size_t size,
214 const char *data, 218 const char *data,
215 enum GNUNET_BLOCK_Type type, 219 enum GNUNET_BLOCK_Type type,
@@ -222,7 +226,6 @@ heap_plugin_put (void *cls,
222 struct PutContext put_ctx; 226 struct PutContext put_ctx;
223 227
224 put_ctx.found = GNUNET_NO; 228 put_ctx.found = GNUNET_NO;
225 put_ctx.heap = plugin->heap;
226 put_ctx.data = data; 229 put_ctx.data = data;
227 put_ctx.size = size; 230 put_ctx.size = size;
228 put_ctx.path_info = path_info; 231 put_ctx.path_info = path_info;
@@ -236,22 +239,28 @@ heap_plugin_put (void *cls,
236 if (GNUNET_YES == put_ctx.found) 239 if (GNUNET_YES == put_ctx.found)
237 return 0; 240 return 0;
238 val = GNUNET_malloc (sizeof (struct Value) + size); 241 val = GNUNET_malloc (sizeof (struct Value) + size);
239 GNUNET_memcpy (&val[1], data, size); 242 GNUNET_memcpy (&val[1],
243 data,
244 size);
240 val->key = *key; 245 val->key = *key;
241 val->type = type; 246 val->type = type;
242 val->discard_time = discard_time; 247 val->discard_time = discard_time;
243 val->size = size; 248 val->size = size;
249 if (xor_distance >= NUM_HEAPS)
250 val->distance = NUM_HEAPS - 1;
251 else
252 val->distance = xor_distance;
244 GNUNET_array_grow (val->path_info, 253 GNUNET_array_grow (val->path_info,
245 val->path_info_len, 254 val->path_info_len,
246 path_info_len); 255 path_info_len);
247 GNUNET_memcpy (val->path_info, 256 GNUNET_memcpy (val->path_info,
248 path_info, 257 path_info,
249 path_info_len * sizeof (struct GNUNET_PeerIdentity)); 258 path_info_len * sizeof (struct GNUNET_PeerIdentity));
250 (void) GNUNET_CONTAINER_multihashmap_put (plugin->map, 259 (void) GNUNET_CONTAINER_multihashmap_put (plugin->map,
251 &val->key, 260 &val->key,
252 val, 261 val,
253 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); 262 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
254 val->hn = GNUNET_CONTAINER_heap_insert (plugin->heap, 263 val->hn = GNUNET_CONTAINER_heap_insert (plugin->heaps[val->distance],
255 val, 264 val,
256 val->discard_time.abs_value_us); 265 val->discard_time.abs_value_us);
257 return size + OVERHEAD; 266 return size + OVERHEAD;
@@ -369,7 +378,12 @@ heap_plugin_del (void *cls)
369 struct Plugin *plugin = cls; 378 struct Plugin *plugin = cls;
370 struct Value *val; 379 struct Value *val;
371 380
372 val = GNUNET_CONTAINER_heap_remove_root (plugin->heap); 381 for (unsigned int i=0;i<NUM_HEAPS;i++)
382 {
383 val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i]);
384 if (NULL != val)
385 break;
386 }
373 if (NULL == val) 387 if (NULL == val)
374 return GNUNET_SYSERR; 388 return GNUNET_SYSERR;
375 GNUNET_assert (GNUNET_YES == 389 GNUNET_assert (GNUNET_YES ==
@@ -413,6 +427,53 @@ heap_plugin_get_random (void *cls,
413 427
414 428
415/** 429/**
430 * Closure for #find_closest().
431 */
432struct GetClosestContext
433{
434 struct Value **values;
435
436 unsigned int num_results;
437
438 const struct GNUNET_HashCode *key;
439};
440
441
442static int
443find_closest (void *cls,
444 const struct GNUNET_HashCode *key,
445 void *value)
446{
447 struct GetClosestContext *gcc = cls;
448 struct Value *val = value;
449 unsigned int j;
450
451 if (1 != GNUNET_CRYPTO_hash_cmp (key,
452 gcc->key))
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 == GNUNET_CRYPTO_hash_cmp (&gcc->values[i]->key,
463 key))
464 {
465 j = i;
466 break;
467 }
468 }
469 if (j == gcc->num_results)
470 return GNUNET_OK;
471 gcc->values[j] = val;
472 return GNUNET_OK;
473}
474
475
476/**
416 * Iterate over the results that are "close" to a particular key in 477 * Iterate over the results that are "close" to a particular key in
417 * the datacache. "close" is defined as numerically larger than @a 478 * the datacache. "close" is defined as numerically larger than @a
418 * key (when interpreted as a circular address space), with small 479 * key (when interpreted as a circular address space), with small
@@ -432,8 +493,30 @@ heap_plugin_get_closest (void *cls,
432 GNUNET_DATACACHE_Iterator iter, 493 GNUNET_DATACACHE_Iterator iter,
433 void *iter_cls) 494 void *iter_cls)
434{ 495{
435 GNUNET_break (0); // not implemented! 496 struct Plugin *plugin = cls;
436 return 0; 497 struct Value *values[num_results];
498 struct GetClosestContext gcc = {
499 .values = values,
500 .num_results = num_results,
501 .key = key
502 };
503 GNUNET_CONTAINER_multihashmap_iterate (plugin->map,
504 &find_closest,
505 &gcc);
506 for (unsigned int i=0;i<num_results;i++)
507 {
508 if (NULL == values[i])
509 return i;
510 iter (iter_cls,
511 &values[i]->key,
512 values[i]->size,
513 (void *) &values[i][1],
514 values[i]->type,
515 values[i]->discard_time,
516 values[i]->path_info_len,
517 values[i]->path_info);
518 }
519 return num_results;
437} 520}
438 521
439 522
@@ -453,7 +536,8 @@ libgnunet_plugin_datacache_heap_init (void *cls)
453 plugin = GNUNET_new (struct Plugin); 536 plugin = GNUNET_new (struct Plugin);
454 plugin->map = GNUNET_CONTAINER_multihashmap_create (1024, /* FIXME: base on quota! */ 537 plugin->map = GNUNET_CONTAINER_multihashmap_create (1024, /* FIXME: base on quota! */
455 GNUNET_YES); 538 GNUNET_YES);
456 plugin->heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); 539 for (unsigned int i=0;i<NUM_HEAPS;i++)
540 plugin->heaps[i] = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
457 plugin->env = env; 541 plugin->env = env;
458 api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions); 542 api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions);
459 api->cls = plugin; 543 api->cls = plugin;
@@ -481,16 +565,19 @@ libgnunet_plugin_datacache_heap_done (void *cls)
481 struct Plugin *plugin = api->cls; 565 struct Plugin *plugin = api->cls;
482 struct Value *val; 566 struct Value *val;
483 567
484 while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heap))) 568 for (unsigned int i=0;i<NUM_HEAPS;i++)
485 { 569 {
486 GNUNET_assert (GNUNET_YES == 570 while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i])))
487 GNUNET_CONTAINER_multihashmap_remove (plugin->map, 571 {
488 &val->key, 572 GNUNET_assert (GNUNET_YES ==
489 val)); 573 GNUNET_CONTAINER_multihashmap_remove (plugin->map,
490 GNUNET_free_non_null (val->path_info); 574 &val->key,
491 GNUNET_free (val); 575 val));
576 GNUNET_free_non_null (val->path_info);
577 GNUNET_free (val);
578 }
579 GNUNET_CONTAINER_heap_destroy (plugin->heaps[i]);
492 } 580 }
493 GNUNET_CONTAINER_heap_destroy (plugin->heap);
494 GNUNET_CONTAINER_multihashmap_destroy (plugin->map); 581 GNUNET_CONTAINER_multihashmap_destroy (plugin->map);
495 GNUNET_free (plugin); 582 GNUNET_free (plugin);
496 GNUNET_free (api); 583 GNUNET_free (api);