diff options
author | Nathan S. Evans <evans@in.tum.de> | 2010-11-17 14:22:35 +0000 |
---|---|---|
committer | Nathan S. Evans <evans@in.tum.de> | 2010-11-17 14:22:35 +0000 |
commit | 2bca0645ec82a82749be2d97f27d10ca828760e1 (patch) | |
tree | 749684306db8dc38552d235cf62a6f3e903a5295 /src | |
parent | 4a1012b083430b9685660c3b8fc4b163f75c75a0 (diff) | |
download | gnunet-2bca0645ec82a82749be2d97f27d10ca828760e1.tar.gz gnunet-2bca0645ec82a82749be2d97f27d10ca828760e1.zip |
better forward_count implementation, only timeout forwards, no limit for local requests (only remove on cancel)
Diffstat (limited to 'src')
-rw-r--r-- | src/dht/gnunet-service-dht.c | 79 |
1 files changed, 35 insertions, 44 deletions
diff --git a/src/dht/gnunet-service-dht.c b/src/dht/gnunet-service-dht.c index 296b77e42..7e6c20559 100644 --- a/src/dht/gnunet-service-dht.c +++ b/src/dht/gnunet-service-dht.c | |||
@@ -2709,17 +2709,19 @@ static unsigned int estimate_diameter() | |||
2709 | * forward the request to obtain the desired | 2709 | * forward the request to obtain the desired |
2710 | * target_replication count (on average). | 2710 | * target_replication count (on average). |
2711 | * | 2711 | * |
2712 | * Always 0, 1 or 2 (don't send, send once, split) | 2712 | * returns: target_replication / (est. hops) + (target_replication * hop_count) |
2713 | * where est. hops is typically 2 * the routing table depth | ||
2714 | * | ||
2715 | * @param hop_count number of hops the message has traversed | ||
2716 | * @param target_replication the number of total paths desired | ||
2717 | * | ||
2718 | * @return Some number of peers to forward the message to | ||
2713 | */ | 2719 | */ |
2714 | static unsigned int | 2720 | static unsigned int |
2715 | get_forward_count (unsigned int hop_count, size_t target_replication) | 2721 | get_forward_count (unsigned int hop_count, size_t target_replication) |
2716 | { | 2722 | { |
2717 | #if DOUBLE | ||
2718 | double target_count; | ||
2719 | double random_probability; | ||
2720 | #else | ||
2721 | uint32_t random_value; | 2723 | uint32_t random_value; |
2722 | #endif | 2724 | unsigned int forward_count; |
2723 | unsigned int target_value; | 2725 | unsigned int target_value; |
2724 | unsigned int diameter; | 2726 | unsigned int diameter; |
2725 | 2727 | ||
@@ -2761,38 +2763,19 @@ get_forward_count (unsigned int hop_count, size_t target_replication) | |||
2761 | return 0; | 2763 | return 0; |
2762 | } | 2764 | } |
2763 | 2765 | ||
2764 | #if DOUBLE | 2766 | random_value = 0; |
2765 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Replication %d, hop_count %u, diameter %u\n", target_replication, hop_count, diameter); | 2767 | target_value = target_replication / ((2.0 * (diameter)) + ((float)target_replication * hop_count)); |
2766 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Numerator %f, denominator %f\n", (double)target_replication, ((double)target_replication * (hop_count + 1) + diameter)); | 2768 | if (target_value > 1) |
2767 | target_count = /* target_count is ALWAYS < 1 unless replication is < 1 */ | 2769 | return (unsigned int)target_value; |
2768 | (double)target_replication / ((double)target_replication * (hop_count + 1) + diameter); | 2770 | else |
2769 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Target count is %f\n", target_count); | 2771 | random_value = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_STRONG, (unsigned int)-1); |
2770 | random_probability = ((double)GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, | ||
2771 | RAND_MAX)) / RAND_MAX; | ||
2772 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Random is %f\n", random_probability); | ||
2773 | |||
2774 | target_value = 0; | ||
2775 | //while (target_value < target_count) | ||
2776 | if (target_value < target_count) | ||
2777 | target_value++; /* target_value is ALWAYS 1 after this "loop", right? Because target_count is always > 0, right? Or does it become 0.00000... at some point because the hop count is so high? */ | ||
2778 | |||
2779 | |||
2780 | //if ((target_count + 1 - (double)target_value) > random_probability) | ||
2781 | if ((target_count) > random_probability) | ||
2782 | target_value++; | ||
2783 | #endif | ||
2784 | 2772 | ||
2785 | random_value = GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_STRONG, target_replication * (hop_count + 1) + diameter) + 1; | 2773 | if (random_value < (target_value * (unsigned int)-1)) |
2786 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "replication %u, at hop %d, will split with probability %f\n", target_replication, hop_count, target_replication / (double)((target_replication * (hop_count + 1) + diameter) + 1)); | 2774 | forward_count = 2; |
2787 | target_value = 1; | 2775 | else |
2788 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "random %u, target %u, max %u\n", random_value, target_replication, target_replication * (hop_count + 1) + diameter); | 2776 | forward_count = 1; |
2789 | if (random_value < target_replication) | ||
2790 | { | ||
2791 | increment_stats("# DHT Messages split"); | ||
2792 | target_value++; | ||
2793 | } | ||
2794 | 2777 | ||
2795 | return target_value; | 2778 | return forward_count; |
2796 | } | 2779 | } |
2797 | 2780 | ||
2798 | /* | 2781 | /* |
@@ -3340,7 +3323,7 @@ remove_forward_entry (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) | |||
3340 | 3323 | ||
3341 | if (record->head == NULL) /* No more entries in DLL */ | 3324 | if (record->head == NULL) /* No more entries in DLL */ |
3342 | { | 3325 | { |
3343 | GNUNET_assert(GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove(forward_list.hashmap, &record->key, record)); | 3326 | GNUNET_assert(GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove (forward_list.hashmap, &record->key, record)); |
3344 | GNUNET_free(record); | 3327 | GNUNET_free(record); |
3345 | } | 3328 | } |
3346 | if (source_info->find_peers_responded != NULL) | 3329 | if (source_info->find_peers_responded != NULL) |
@@ -3365,13 +3348,15 @@ static int cache_response(struct DHT_MessageContext *msg_ctx) | |||
3365 | struct GNUNET_TIME_Absolute now; | 3348 | struct GNUNET_TIME_Absolute now; |
3366 | unsigned int current_size; | 3349 | unsigned int current_size; |
3367 | 3350 | ||
3368 | current_size = GNUNET_CONTAINER_multihashmap_size(forward_list.hashmap); | 3351 | current_size = GNUNET_CONTAINER_multihashmap_size (forward_list.hashmap); |
3352 | |||
3353 | #if DELETE_WHEN_FULL | ||
3369 | while (current_size >= MAX_OUTSTANDING_FORWARDS) | 3354 | while (current_size >= MAX_OUTSTANDING_FORWARDS) |
3370 | { | 3355 | { |
3371 | source_info = GNUNET_CONTAINER_heap_remove_root(forward_list.minHeap); | 3356 | source_info = GNUNET_CONTAINER_heap_remove_root (forward_list.minHeap); |
3372 | GNUNET_assert(source_info != NULL); | 3357 | GNUNET_assert(source_info != NULL); |
3373 | record = source_info->record; | 3358 | record = source_info->record; |
3374 | GNUNET_CONTAINER_DLL_remove(record->head, record->tail, source_info); | 3359 | GNUNET_CONTAINER_DLL_remove (record->head, record->tail, source_info); |
3375 | if (record->head == NULL) /* No more entries in DLL */ | 3360 | if (record->head == NULL) /* No more entries in DLL */ |
3376 | { | 3361 | { |
3377 | GNUNET_assert(GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove(forward_list.hashmap, &record->key, record)); | 3362 | GNUNET_assert(GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove(forward_list.hashmap, &record->key, record)); |
@@ -3384,6 +3369,11 @@ static int cache_response(struct DHT_MessageContext *msg_ctx) | |||
3384 | GNUNET_free(source_info); | 3369 | GNUNET_free(source_info); |
3385 | current_size = GNUNET_CONTAINER_multihashmap_size(forward_list.hashmap); | 3370 | current_size = GNUNET_CONTAINER_multihashmap_size(forward_list.hashmap); |
3386 | } | 3371 | } |
3372 | #endif | ||
3373 | /** Non-local request and have too many outstanding forwards, discard! */ | ||
3374 | if ((current_size >= MAX_OUTSTANDING_FORWARDS) && (msg_ctx->client == NULL)) | ||
3375 | return GNUNET_NO; | ||
3376 | |||
3387 | now = GNUNET_TIME_absolute_get(); | 3377 | now = GNUNET_TIME_absolute_get(); |
3388 | record = GNUNET_CONTAINER_multihashmap_get(forward_list.hashmap, &msg_ctx->key); | 3378 | record = GNUNET_CONTAINER_multihashmap_get(forward_list.hashmap, &msg_ctx->key); |
3389 | if (record != NULL) /* Already know this request! */ | 3379 | if (record != NULL) /* Already know this request! */ |
@@ -3410,10 +3400,10 @@ static int cache_response(struct DHT_MessageContext *msg_ctx) | |||
3410 | 3400 | ||
3411 | source_info = GNUNET_malloc(sizeof(struct DHTRouteSource)); | 3401 | source_info = GNUNET_malloc(sizeof(struct DHTRouteSource)); |
3412 | source_info->record = record; | 3402 | source_info->record = record; |
3413 | source_info->delete_task = GNUNET_SCHEDULER_add_delayed(DHT_FORWARD_TIMEOUT, &remove_forward_entry, source_info); | 3403 | source_info->delete_task = GNUNET_SCHEDULER_add_delayed (DHT_FORWARD_TIMEOUT, &remove_forward_entry, source_info); |
3414 | source_info->find_peers_responded = GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K); | 3404 | source_info->find_peers_responded = GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K); |
3415 | memcpy(&source_info->source, msg_ctx->peer, sizeof(struct GNUNET_PeerIdentity)); | 3405 | memcpy(&source_info->source, msg_ctx->peer, sizeof(struct GNUNET_PeerIdentity)); |
3416 | GNUNET_CONTAINER_DLL_insert_after(record->head, record->tail, record->tail, source_info); | 3406 | GNUNET_CONTAINER_DLL_insert_after (record->head, record->tail, record->tail, source_info); |
3417 | if (msg_ctx->client != NULL) /* For local request, set timeout so high it effectively never gets pushed out */ | 3407 | if (msg_ctx->client != NULL) /* For local request, set timeout so high it effectively never gets pushed out */ |
3418 | { | 3408 | { |
3419 | source_info->client = msg_ctx->client; | 3409 | source_info->client = msg_ctx->client; |
@@ -4201,18 +4191,19 @@ handle_dht_local_route_stop(void *cls, struct GNUNET_SERVER_Client *client, | |||
4201 | "`%s:%s': Received `%s' request from client, uid %llu\n", my_short_id, "DHT", | 4191 | "`%s:%s': Received `%s' request from client, uid %llu\n", my_short_id, "DHT", |
4202 | "GENERIC STOP", GNUNET_ntohll (dht_stop_msg->unique_id)); | 4192 | "GENERIC STOP", GNUNET_ntohll (dht_stop_msg->unique_id)); |
4203 | #endif | 4193 | #endif |
4204 | record = GNUNET_CONTAINER_multihashmap_get(forward_list.hashmap, &dht_stop_msg->key); | 4194 | record = GNUNET_CONTAINER_multihashmap_get (forward_list.hashmap, &dht_stop_msg->key); |
4205 | if (record != NULL) | 4195 | if (record != NULL) |
4206 | { | 4196 | { |
4207 | pos = record->head; | 4197 | pos = record->head; |
4208 | 4198 | ||
4209 | while (pos != NULL) | 4199 | while (pos != NULL) |
4210 | { | 4200 | { |
4201 | /* If the client is non-null (local request) and the client matches the requesting client, remove the entry. */ | ||
4211 | if ((pos->client != NULL) && (pos->client->client_handle == client)) | 4202 | if ((pos->client != NULL) && (pos->client->client_handle == client)) |
4212 | { | 4203 | { |
4213 | GNUNET_SCHEDULER_cancel(pos->delete_task); | 4204 | GNUNET_SCHEDULER_cancel(pos->delete_task); |
4214 | pos->delete_task = GNUNET_SCHEDULER_NO_TASK; | 4205 | pos->delete_task = GNUNET_SCHEDULER_NO_TASK; |
4215 | GNUNET_SCHEDULER_add_now(&remove_forward_entry, pos); | 4206 | GNUNET_SCHEDULER_add_continuation (&remove_forward_entry, pos, GNUNET_SCHEDULER_REASON_PREREQ_DONE); |
4216 | } | 4207 | } |
4217 | pos = pos->next; | 4208 | pos = pos->next; |
4218 | } | 4209 | } |