From 83d63a1f916b073f8cf44cf91b6c0b3d118dabe5 Mon Sep 17 00:00:00 2001 From: Date: Mon, 21 Apr 2008 11:17:06 -0700 Subject: [PATCH] Fix for wheel algo to be dynamic --- ChangeLog | 2 ++ libmemcached/memcached.c | 8 +++++ libmemcached/memcached.h | 3 +- libmemcached/memcached_constants.h | 1 - libmemcached/memcached_hash.c | 53 ++---------------------------- libmemcached/memcached_hosts.c | 26 ++++++++++++--- tests/function.c | 18 ++++++++++ 7 files changed, 55 insertions(+), 56 deletions(-) diff --git a/ChangeLog b/ChangeLog index 9b99aafa..effd1d13 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,5 @@ + * Wheel uses less memory/dynamic allocation for size (no longer limited to + 512 hosts by default. * memslap memory leak fix * Added Ketama distribution * Fix assert.h compile problem on CentOS diff --git a/libmemcached/memcached.c b/libmemcached/memcached.c index bcc0477d..b681f6cb 100644 --- a/libmemcached/memcached.c +++ b/libmemcached/memcached.c @@ -49,6 +49,14 @@ void memcached_free(memcached_st *ptr) free(ptr->continuum); } + if (ptr->wheel) + { + if (ptr->call_free) + ptr->call_free(ptr, ptr->wheel); + else + free(ptr->wheel); + } + if (ptr->is_allocated == MEMCACHED_ALLOCATED) { if (ptr->call_free) diff --git a/libmemcached/memcached.h b/libmemcached/memcached.h index 45d4085f..935a4a13 100644 --- a/libmemcached/memcached.h +++ b/libmemcached/memcached.h @@ -81,7 +81,8 @@ struct memcached_st { memcached_hash hash; memcached_server_distribution distribution; void *user_data; - unsigned int wheel[MEMCACHED_WHEEL_SIZE]; + unsigned int *wheel; + uint32_t wheel_count; uint32_t continuum_count; memcached_continuum_item_st *continuum; memcached_clone_func on_clone; diff --git a/libmemcached/memcached_constants.h b/libmemcached/memcached_constants.h index e60a03b7..1d2b08ad 100644 --- a/libmemcached/memcached_constants.h +++ b/libmemcached/memcached_constants.h @@ -19,7 +19,6 @@ extern "C" { #define MEMCACHED_MAX_BUFFER 8196 #define MEMCACHED_MAX_HOST_LENGTH 64 #define MEMCACHED_MAX_HOST_SORT_LENGTH 86 /* Used for Ketama */ -#define MEMCACHED_WHEEL_SIZE 1024 #define MEMCACHED_POINTS_PER_SERVER 100 #define MEMCACHED_CONTINUUM_SIZE MEMCACHED_POINTS_PER_SERVER*100 /* This would then set max hosts to 100 */ #define MEMCACHED_STRIDE 4 diff --git a/libmemcached/memcached_hash.c b/libmemcached/memcached_hash.c index c0e928a1..4cb442cb 100644 --- a/libmemcached/memcached_hash.c +++ b/libmemcached/memcached_hash.c @@ -148,7 +148,7 @@ unsigned int dispatch_host(memcached_st *ptr, uint32_t hash) { unsigned int server_key; - server_key= hash % MEMCACHED_WHEEL_SIZE; + server_key= hash % MEMCACHED_STRIDE * ptr->wheel_count; return ptr->wheel[server_key]; } @@ -159,55 +159,8 @@ unsigned int dispatch_host(memcached_st *ptr, uint32_t hash) return hash % ptr->number_of_hosts; } - if (ptr->distribution == MEMCACHED_DISTRIBUTION_MODULA) - { - return hash % ptr->number_of_hosts; - } - else if (ptr->distribution == MEMCACHED_DISTRIBUTION_CONSISTENT) - { - unsigned int server_key; - - server_key= hash % MEMCACHED_WHEEL_SIZE; - - return ptr->wheel[server_key]; - } - else if (ptr->distribution == MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA) - { - int num = ptr->number_of_hosts * MEMCACHED_POINTS_PER_SERVER; - - hash = hash; - memcached_continuum_item_st *begin, *end, *left, *right, *middle; - begin = left = ptr->continuum; - end = right = ptr->continuum + (num - 1); - while(1) - { - middle = left + (right - left) / 2; - if(middle==end) - { - return begin->index; - } - if(middle==begin) - { - return end->index; - } - memcached_continuum_item_st *rmiddle = middle+1; - if(hashvalue && hash>=middle->value) - return middle->index; - - if(middle->value < hash) { - left = middle + 1; - }else if(middle->value > hash) { - right = middle - 1; - } - - if (left>right) - return left->index; - } - } - else - { - WATCHPOINT_ASSERT(0); - } + WATCHPOINT_ASSERT(0); /* We should never reach here */ + return 0; } unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_length) diff --git a/libmemcached/memcached_hosts.c b/libmemcached/memcached_hosts.c index 72de6d09..03ea81e3 100644 --- a/libmemcached/memcached_hosts.c +++ b/libmemcached/memcached_hosts.c @@ -8,16 +8,32 @@ memcached_return update_continuum(memcached_st *ptr); #define MEMCACHED_WHEEL_SIZE 1024 #define MEMCACHED_STRIDE 4 -static void rebalance_wheel(memcached_st *ptr) +static memcached_return rebalance_wheel(memcached_st *ptr) { unsigned int x; unsigned int y; unsigned int latch; + if (ptr->number_of_hosts > ptr->wheel_count) + { + uint32_t *new_ptr; + + if (ptr->call_realloc) + new_ptr= (uint32_t *)ptr->call_realloc(ptr, ptr->wheel, sizeof(uint32_t) * (ptr->number_of_hosts + MEMCACHED_CONTINUUM_ADDITION) * MEMCACHED_STRIDE); + else + new_ptr= (uint32_t *)realloc(ptr->wheel, sizeof(uint32_t) * (ptr->number_of_hosts + MEMCACHED_CONTINUUM_ADDITION) * MEMCACHED_STRIDE); + + if (new_ptr == 0) + return MEMCACHED_MEMORY_ALLOCATION_FAILURE; + + ptr->wheel= new_ptr; + ptr->wheel_count= ptr->number_of_hosts + MEMCACHED_CONTINUUM_ADDITION; + } + /* Seed the Wheel */ - memset(ptr->wheel, 0, sizeof(unsigned int) * MEMCACHED_WHEEL_SIZE); + memset(ptr->wheel, 0, sizeof(uint32_t) * MEMCACHED_STRIDE * ptr->wheel_count); - for (latch= y= x= 0; x < MEMCACHED_WHEEL_SIZE; x++, latch++) + for (latch= y= x= 0; x < MEMCACHED_STRIDE * ptr->wheel_count; x++, latch++) { if (latch == MEMCACHED_STRIDE) { @@ -29,6 +45,8 @@ static void rebalance_wheel(memcached_st *ptr) ptr->wheel[x]= y; } + + return MEMCACHED_SUCCESS; } static int compare_servers(const void *p1, const void *p2) @@ -65,7 +83,7 @@ memcached_return run_distribution(memcached_st *ptr) case MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA: return update_continuum(ptr); case MEMCACHED_DISTRIBUTION_CONSISTENT_WHEEL: - rebalance_wheel(ptr); + return rebalance_wheel(ptr); break; case MEMCACHED_DISTRIBUTION_MODULA: if (ptr->flags & MEM_USE_SORT_HOSTS) diff --git a/tests/function.c b/tests/function.c index a08e1eaa..dc4e6e9a 100644 --- a/tests/function.c +++ b/tests/function.c @@ -2458,6 +2458,23 @@ memcached_return set_memory_alloc(memcached_st *memc) return MEMCACHED_SUCCESS; } +memcached_return enable_wheel(memcached_st *memc) +{ + memcached_server_distribution value= MEMCACHED_DISTRIBUTION_CONSISTENT_WHEEL; + memcached_hash hash; + memcached_behavior_set(memc, MEMCACHED_BEHAVIOR_DISTRIBUTION, value); + pre_hsieh(memc); + + value= (memcached_server_distribution)memcached_behavior_get(memc, MEMCACHED_BEHAVIOR_DISTRIBUTION); + assert(value == MEMCACHED_DISTRIBUTION_CONSISTENT_WHEEL); + + hash= (memcached_hash)memcached_behavior_get(memc, MEMCACHED_BEHAVIOR_HASH); + assert(hash == MEMCACHED_HASH_HSIEH); + + + return MEMCACHED_SUCCESS; +} + memcached_return enable_consistent(memcached_st *memc) { memcached_server_distribution value= MEMCACHED_DISTRIBUTION_CONSISTENT; @@ -2689,6 +2706,7 @@ collection_st collection[] ={ {"poll_timeout", poll_timeout, 0, tests}, {"gets", enable_cas, 0, tests}, {"consistent", enable_consistent, 0, tests}, + {"wheel", enable_wheel, 0, tests}, {"memory_allocators", set_memory_alloc, 0, tests}, // {"udp", pre_udp, 0, tests}, {"version_1_2_3", check_for_1_2_3, 0, version_1_2_3}, -- 2.30.2