diff options
author | Christian Grothoff <christian@grothoff.org> | 2018-05-30 18:47:17 +0200 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2018-05-30 18:47:17 +0200 |
commit | adef29b3ed00afd42669ae35a73951c59f08a41b (patch) | |
tree | c8d6c7f60716c551b587aed7a1efe0d6e756833f /src/datacache/plugin_datacache_heap.c | |
parent | f5a18b7466f342ac9624adcdb65f104aef8ecb5e (diff) | |
download | gnunet-adef29b3ed00afd42669ae35a73951c59f08a41b.tar.gz gnunet-adef29b3ed00afd42669ae35a73951c59f08a41b.zip |
add proximity considerations to datacache
Diffstat (limited to 'src/datacache/plugin_datacache_heap.c')
-rw-r--r-- | src/datacache/plugin_datacache_heap.c | 117 |
1 files changed, 111 insertions, 6 deletions
diff --git a/src/datacache/plugin_datacache_heap.c b/src/datacache/plugin_datacache_heap.c index 49e60bca1..c32edf8e2 100644 --- a/src/datacache/plugin_datacache_heap.c +++ b/src/datacache/plugin_datacache_heap.c | |||
@@ -53,6 +53,11 @@ struct Plugin | |||
53 | */ | 53 | */ |
54 | struct GNUNET_CONTAINER_Heap *heap; | 54 | struct GNUNET_CONTAINER_Heap *heap; |
55 | 55 | ||
56 | /** | ||
57 | * Heap from the plugin for "closest" values. | ||
58 | */ | ||
59 | struct GNUNET_CONTAINER_Heap *cheap; | ||
60 | |||
56 | }; | 61 | }; |
57 | 62 | ||
58 | 63 | ||
@@ -92,6 +97,11 @@ struct Value | |||
92 | unsigned int path_info_len; | 97 | unsigned int path_info_len; |
93 | 98 | ||
94 | /** | 99 | /** |
100 | * Am I the closest peer? Determines which heap we are in! | ||
101 | */ | ||
102 | int am_closest; | ||
103 | |||
104 | /** | ||
95 | * Type of the block. | 105 | * Type of the block. |
96 | */ | 106 | */ |
97 | enum GNUNET_BLOCK_Type type; | 107 | enum GNUNET_BLOCK_Type type; |
@@ -118,6 +128,11 @@ struct PutContext | |||
118 | const char *data; | 128 | const char *data; |
119 | 129 | ||
120 | /** | 130 | /** |
131 | * Heap from the plugin for "closest" values. | ||
132 | */ | ||
133 | struct GNUNET_CONTAINER_Heap *cheap; | ||
134 | |||
135 | /** | ||
121 | * Heap from the plugin. | 136 | * Heap from the plugin. |
122 | */ | 137 | */ |
123 | struct GNUNET_CONTAINER_Heap *heap; | 138 | struct GNUNET_CONTAINER_Heap *heap; |
@@ -168,7 +183,9 @@ put_cb (void *cls, | |||
168 | 183 | ||
169 | if ( (val->size == put_ctx->size) && | 184 | if ( (val->size == put_ctx->size) && |
170 | (val->type == put_ctx->type) && | 185 | (val->type == put_ctx->type) && |
171 | (0 == memcmp (&val[1], put_ctx->data, put_ctx->size)) ) | 186 | (0 == memcmp (&val[1], |
187 | put_ctx->data, | ||
188 | put_ctx->size)) ) | ||
172 | { | 189 | { |
173 | put_ctx->found = GNUNET_YES; | 190 | put_ctx->found = GNUNET_YES; |
174 | val->discard_time = GNUNET_TIME_absolute_max (val->discard_time, | 191 | val->discard_time = GNUNET_TIME_absolute_max (val->discard_time, |
@@ -199,6 +216,7 @@ put_cb (void *cls, | |||
199 | * | 216 | * |
200 | * @param cls closure (our `struct Plugin`) | 217 | * @param cls closure (our `struct Plugin`) |
201 | * @param key key to store data under | 218 | * @param key key to store data under |
219 | * @param am_closest are we the closest peer? | ||
202 | * @param size number of bytes in @a data | 220 | * @param size number of bytes in @a data |
203 | * @param data data to store | 221 | * @param data data to store |
204 | * @param type type of the value | 222 | * @param type type of the value |
@@ -210,6 +228,7 @@ put_cb (void *cls, | |||
210 | static ssize_t | 228 | static ssize_t |
211 | heap_plugin_put (void *cls, | 229 | heap_plugin_put (void *cls, |
212 | const struct GNUNET_HashCode *key, | 230 | const struct GNUNET_HashCode *key, |
231 | int am_closest, | ||
213 | size_t size, | 232 | size_t size, |
214 | const char *data, | 233 | const char *data, |
215 | enum GNUNET_BLOCK_Type type, | 234 | enum GNUNET_BLOCK_Type type, |
@@ -223,6 +242,7 @@ heap_plugin_put (void *cls, | |||
223 | 242 | ||
224 | put_ctx.found = GNUNET_NO; | 243 | put_ctx.found = GNUNET_NO; |
225 | put_ctx.heap = plugin->heap; | 244 | put_ctx.heap = plugin->heap; |
245 | put_ctx.cheap = plugin->cheap; | ||
226 | put_ctx.data = data; | 246 | put_ctx.data = data; |
227 | put_ctx.size = size; | 247 | put_ctx.size = size; |
228 | put_ctx.path_info = path_info; | 248 | put_ctx.path_info = path_info; |
@@ -241,17 +261,20 @@ heap_plugin_put (void *cls, | |||
241 | val->type = type; | 261 | val->type = type; |
242 | val->discard_time = discard_time; | 262 | val->discard_time = discard_time; |
243 | val->size = size; | 263 | val->size = size; |
264 | val->am_closest = am_closest; | ||
244 | GNUNET_array_grow (val->path_info, | 265 | GNUNET_array_grow (val->path_info, |
245 | val->path_info_len, | 266 | val->path_info_len, |
246 | path_info_len); | 267 | path_info_len); |
247 | GNUNET_memcpy (val->path_info, | 268 | GNUNET_memcpy (val->path_info, |
248 | path_info, | 269 | path_info, |
249 | path_info_len * sizeof (struct GNUNET_PeerIdentity)); | 270 | path_info_len * sizeof (struct GNUNET_PeerIdentity)); |
250 | (void) GNUNET_CONTAINER_multihashmap_put (plugin->map, | 271 | (void) GNUNET_CONTAINER_multihashmap_put (plugin->map, |
251 | &val->key, | 272 | &val->key, |
252 | val, | 273 | val, |
253 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); | 274 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); |
254 | val->hn = GNUNET_CONTAINER_heap_insert (plugin->heap, | 275 | val->hn = GNUNET_CONTAINER_heap_insert (am_closest |
276 | ? plugin->cheap | ||
277 | : plugin->heap, | ||
255 | val, | 278 | val, |
256 | val->discard_time.abs_value_us); | 279 | val->discard_time.abs_value_us); |
257 | return size + OVERHEAD; | 280 | return size + OVERHEAD; |
@@ -371,6 +394,8 @@ heap_plugin_del (void *cls) | |||
371 | 394 | ||
372 | val = GNUNET_CONTAINER_heap_remove_root (plugin->heap); | 395 | val = GNUNET_CONTAINER_heap_remove_root (plugin->heap); |
373 | if (NULL == val) | 396 | if (NULL == val) |
397 | val = GNUNET_CONTAINER_heap_remove_root (plugin->cheap); | ||
398 | if (NULL == val) | ||
374 | return GNUNET_SYSERR; | 399 | return GNUNET_SYSERR; |
375 | GNUNET_assert (GNUNET_YES == | 400 | GNUNET_assert (GNUNET_YES == |
376 | GNUNET_CONTAINER_multihashmap_remove (plugin->map, | 401 | GNUNET_CONTAINER_multihashmap_remove (plugin->map, |
@@ -413,6 +438,53 @@ heap_plugin_get_random (void *cls, | |||
413 | 438 | ||
414 | 439 | ||
415 | /** | 440 | /** |
441 | * Closure for #find_closest(). | ||
442 | */ | ||
443 | struct GetClosestContext | ||
444 | { | ||
445 | struct Value **values; | ||
446 | |||
447 | unsigned int num_results; | ||
448 | |||
449 | const struct GNUNET_HashCode *key; | ||
450 | }; | ||
451 | |||
452 | |||
453 | static int | ||
454 | find_closest (void *cls, | ||
455 | const struct GNUNET_HashCode *key, | ||
456 | void *value) | ||
457 | { | ||
458 | struct GetClosestContext *gcc = cls; | ||
459 | struct Value *val = value; | ||
460 | unsigned int j; | ||
461 | |||
462 | if (1 != GNUNET_CRYPTO_hash_cmp (key, | ||
463 | gcc->key)) | ||
464 | return GNUNET_OK; /* useless */ | ||
465 | j = gcc->num_results; | ||
466 | for (unsigned int i=0;i<gcc->num_results;i++) | ||
467 | { | ||
468 | if (NULL == gcc->values[i]) | ||
469 | { | ||
470 | j = i; | ||
471 | break; | ||
472 | } | ||
473 | if (1 == GNUNET_CRYPTO_hash_cmp (&gcc->values[i]->key, | ||
474 | key)) | ||
475 | { | ||
476 | j = i; | ||
477 | break; | ||
478 | } | ||
479 | } | ||
480 | if (j == gcc->num_results) | ||
481 | return GNUNET_OK; | ||
482 | gcc->values[j] = val; | ||
483 | return GNUNET_OK; | ||
484 | } | ||
485 | |||
486 | |||
487 | /** | ||
416 | * Iterate over the results that are "close" to a particular key in | 488 | * Iterate over the results that are "close" to a particular key in |
417 | * the datacache. "close" is defined as numerically larger than @a | 489 | * the datacache. "close" is defined as numerically larger than @a |
418 | * key (when interpreted as a circular address space), with small | 490 | * key (when interpreted as a circular address space), with small |
@@ -432,8 +504,30 @@ heap_plugin_get_closest (void *cls, | |||
432 | GNUNET_DATACACHE_Iterator iter, | 504 | GNUNET_DATACACHE_Iterator iter, |
433 | void *iter_cls) | 505 | void *iter_cls) |
434 | { | 506 | { |
435 | GNUNET_break (0); // not implemented! | 507 | struct Plugin *plugin = cls; |
436 | return 0; | 508 | struct Value *values[num_results]; |
509 | struct GetClosestContext gcc = { | ||
510 | .values = values, | ||
511 | .num_results = num_results, | ||
512 | .key = key | ||
513 | }; | ||
514 | GNUNET_CONTAINER_multihashmap_iterate (plugin->map, | ||
515 | &find_closest, | ||
516 | &gcc); | ||
517 | for (unsigned int i=0;i<num_results;i++) | ||
518 | { | ||
519 | if (NULL == values[i]) | ||
520 | return i; | ||
521 | iter (iter_cls, | ||
522 | &values[i]->key, | ||
523 | values[i]->size, | ||
524 | (void *) &values[i][1], | ||
525 | values[i]->type, | ||
526 | values[i]->discard_time, | ||
527 | values[i]->path_info_len, | ||
528 | values[i]->path_info); | ||
529 | } | ||
530 | return num_results; | ||
437 | } | 531 | } |
438 | 532 | ||
439 | 533 | ||
@@ -454,6 +548,7 @@ libgnunet_plugin_datacache_heap_init (void *cls) | |||
454 | plugin->map = GNUNET_CONTAINER_multihashmap_create (1024, /* FIXME: base on quota! */ | 548 | plugin->map = GNUNET_CONTAINER_multihashmap_create (1024, /* FIXME: base on quota! */ |
455 | GNUNET_YES); | 549 | GNUNET_YES); |
456 | plugin->heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); | 550 | plugin->heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); |
551 | plugin->cheap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); | ||
457 | plugin->env = env; | 552 | plugin->env = env; |
458 | api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions); | 553 | api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions); |
459 | api->cls = plugin; | 554 | api->cls = plugin; |
@@ -490,7 +585,17 @@ libgnunet_plugin_datacache_heap_done (void *cls) | |||
490 | GNUNET_free_non_null (val->path_info); | 585 | GNUNET_free_non_null (val->path_info); |
491 | GNUNET_free (val); | 586 | GNUNET_free (val); |
492 | } | 587 | } |
588 | while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->cheap))) | ||
589 | { | ||
590 | GNUNET_assert (GNUNET_YES == | ||
591 | GNUNET_CONTAINER_multihashmap_remove (plugin->map, | ||
592 | &val->key, | ||
593 | val)); | ||
594 | GNUNET_free_non_null (val->path_info); | ||
595 | GNUNET_free (val); | ||
596 | } | ||
493 | GNUNET_CONTAINER_heap_destroy (plugin->heap); | 597 | GNUNET_CONTAINER_heap_destroy (plugin->heap); |
598 | GNUNET_CONTAINER_heap_destroy (plugin->cheap); | ||
494 | GNUNET_CONTAINER_multihashmap_destroy (plugin->map); | 599 | GNUNET_CONTAINER_multihashmap_destroy (plugin->map); |
495 | GNUNET_free (plugin); | 600 | GNUNET_free (plugin); |
496 | GNUNET_free (api); | 601 | GNUNET_free (api); |