diff options
Diffstat (limited to 'src/datacache/plugin_datacache_heap.c')
-rw-r--r-- | src/datacache/plugin_datacache_heap.c | 143 |
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, | |||
210 | static ssize_t | 213 | static ssize_t |
211 | heap_plugin_put (void *cls, | 214 | heap_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 | */ | ||
432 | struct GetClosestContext | ||
433 | { | ||
434 | struct Value **values; | ||
435 | |||
436 | unsigned int num_results; | ||
437 | |||
438 | const struct GNUNET_HashCode *key; | ||
439 | }; | ||
440 | |||
441 | |||
442 | static int | ||
443 | find_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); |