From acd4e556bf8e21005dc42500e3f76b40adb89949 Mon Sep 17 00:00:00 2001 From: Brian Aker Date: Tue, 19 Jan 2010 17:09:50 -0800 Subject: [PATCH] Updates for libmemached to use libhashkit --- libhashkit/hashkit.c | 61 ++++++++++++++++- libhashkit/hashkit.h | 6 ++ libhashkit/types.h | 1 + libmemcached/behavior.c | 35 ++++------ libmemcached/constants.h | 1 + libmemcached/hash.c | 136 +------------------------------------- libmemcached/hosts.c | 14 ++-- libmemcached/include.am | 4 +- libmemcached/memcached.c | 42 +++++++++--- libmemcached/memcached.h | 5 +- tests/hashkit_functions.c | 34 ++++++++++ tests/mem_functions.c | 4 +- 12 files changed, 162 insertions(+), 181 deletions(-) diff --git a/libhashkit/hashkit.c b/libhashkit/hashkit.c index cd33c4e7..9a7e93e9 100644 --- a/libhashkit/hashkit.c +++ b/libhashkit/hashkit.c @@ -49,9 +49,6 @@ void hashkit_free(hashkit_st *self) } } -/** - @note We do assume source is valid. If source does not exist, we allocate. -*/ hashkit_st *hashkit_clone(hashkit_st *destination, const hashkit_st *source) { if (source == NULL) @@ -73,6 +70,14 @@ hashkit_st *hashkit_clone(hashkit_st *destination, const hashkit_st *source) return destination; } +bool hashkit_compare(const hashkit_st *first, const hashkit_st *second) +{ + if (first->base_hash.function == second->base_hash.function && + first->base_hash.context == second->base_hash.context) + return true; + + return false; +} uint32_t hashkit_generate_value(const hashkit_st *self, const char *key, size_t key_length) { @@ -117,6 +122,7 @@ hashkit_return_t hashkit_set_base_function(hashkit_st *self, hashkit_hash_algori case HASHKIT_HASH_JENKINS: self->base_hash.function= hashkit_jenkins; break; + case HASHKIT_HASH_CUSTOM: case HASHKIT_HASH_MAX: default: return HASHKIT_FAILURE; @@ -141,6 +147,54 @@ hashkit_return_t hashkit_set_base_function_custom(hashkit_st *self, hashkit_hash return HASHKIT_FAILURE; } +hashkit_hash_algorithm_t hashkit_get_base_function(const hashkit_st *self) +{ + if (self->base_hash.function == hashkit_one_at_a_time) + { + return HASHKIT_HASH_DEFAULT; + } + else if (self->base_hash.function == hashkit_md5) + { + return HASHKIT_HASH_MD5; + } + else if (self->base_hash.function == hashkit_crc32) + { + return HASHKIT_HASH_CRC; + } + else if (self->base_hash.function == hashkit_fnv1_64) + { + return HASHKIT_HASH_FNV1_64; + } + else if (self->base_hash.function == hashkit_fnv1a_64) + { + return HASHKIT_HASH_FNV1A_64; + } + else if (self->base_hash.function == hashkit_fnv1_32) + { + return HASHKIT_HASH_FNV1_32; + } + else if (self->base_hash.function == hashkit_fnv1a_32) + { + return HASHKIT_HASH_FNV1A_32; + } +#ifdef HAVE_HSIEH_HASH + else if (self->base_hash.function == hashkit_hsieh) + { + return HASHKIT_HASH_HSIEH; + } +#endif + else if (self->base_hash.function == hashkit_murmur) + { + return HASHKIT_HASH_MURMUR; + } + else if (self->base_hash.function == hashkit_jenkins) + { + return HASHKIT_HASH_JENKINS; + } + + return HASHKIT_HASH_CUSTOM; +} + uint32_t libhashkit_generate_value(const char *key, size_t key_length, hashkit_hash_algorithm_t hash_algorithm) { switch (hash_algorithm) @@ -169,6 +223,7 @@ uint32_t libhashkit_generate_value(const char *key, size_t key_length, hashkit_h return libhashkit_murmur(key, key_length); case HASHKIT_HASH_JENKINS: return libhashkit_jenkins(key, key_length); + case HASHKIT_HASH_CUSTOM: case HASHKIT_HASH_MAX: default: #ifdef HAVE_DEBUG diff --git a/libhashkit/hashkit.h b/libhashkit/hashkit.h index 68709358..9b0b32ef 100644 --- a/libhashkit/hashkit.h +++ b/libhashkit/hashkit.h @@ -42,6 +42,9 @@ hashkit_st *hashkit_create(hashkit_st *hash); HASHKIT_API hashkit_st *hashkit_clone(hashkit_st *destination, const hashkit_st *ptr); +HASHKIT_API +bool hashkit_compare(const hashkit_st *first, const hashkit_st *second); + HASHKIT_API void hashkit_free(hashkit_st *hash); @@ -51,6 +54,9 @@ uint32_t hashkit_generate_value(const hashkit_st *self, const char *key, size_t HASHKIT_API hashkit_return_t hashkit_set_base_function(hashkit_st *hash, hashkit_hash_algorithm_t hash_algorithm); +HASHKIT_API +hashkit_hash_algorithm_t hashkit_get_base_function(const hashkit_st *hash); + HASHKIT_API hashkit_return_t hashkit_set_base_function_custom(hashkit_st *hash, hashkit_hash_fn function, void *context); diff --git a/libhashkit/types.h b/libhashkit/types.h index b3ea7346..b2e5f798 100644 --- a/libhashkit/types.h +++ b/libhashkit/types.h @@ -32,6 +32,7 @@ typedef enum { HASHKIT_HASH_HSIEH, HASHKIT_HASH_MURMUR, HASHKIT_HASH_JENKINS, + HASHKIT_HASH_CUSTOM, HASHKIT_HASH_MAX } hashkit_hash_algorithm_t; diff --git a/libmemcached/behavior.c b/libmemcached/behavior.c index d2f031a1..67a261d3 100644 --- a/libmemcached/behavior.c +++ b/libmemcached/behavior.c @@ -21,23 +21,6 @@ static bool set_flag(uint64_t data) return data ? true : false; } -static memcached_return_t set_hash(memcached_hash_t *store, memcached_hash_t type) -{ -#ifndef HAVE_HSIEH_HASH - if (type == MEMCACHED_HASH_HSIEH) - return MEMCACHED_FAILURE; -#endif - if (type < MEMCACHED_HASH_MAX) - { - *store= type; - } - else - { - return MEMCACHED_FAILURE; - } - - return MEMCACHED_SUCCESS; -} /* This function is used to modify the behavior of running client. @@ -283,9 +266,9 @@ uint64_t memcached_behavior_get(memcached_st *ptr, case MEMCACHED_BEHAVIOR_KETAMA: return (ptr->distribution == MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA) ? (uint64_t) 1 : 0; case MEMCACHED_BEHAVIOR_HASH: - return ptr->hash; + return hashkit_get_base_function(&ptr->hashkit); case MEMCACHED_BEHAVIOR_KETAMA_HASH: - return ptr->distribution_hash; + return hashkit_get_base_function(&ptr->distribution_hashkit); case MEMCACHED_BEHAVIOR_SERVER_FAILURE_LIMIT: return ptr->server_failure_limit; case MEMCACHED_BEHAVIOR_SORT_HOSTS: @@ -398,20 +381,26 @@ memcached_server_distribution_t memcached_behavior_get_distribution(memcached_st memcached_return_t memcached_behavior_set_key_hash(memcached_st *ptr, memcached_hash_t type) { - return set_hash(&ptr->hash, type); + hashkit_return_t rc; + rc= hashkit_set_base_function(&ptr->hashkit, (hashkit_hash_algorithm_t)type); + + return rc == HASHKIT_SUCCESS ? MEMCACHED_SUCCESS : MEMCACHED_FAILURE; } memcached_hash_t memcached_behavior_get_key_hash(memcached_st *ptr) { - return ptr->hash; + return (memcached_hash_t)hashkit_get_base_function(&ptr->hashkit); } memcached_return_t memcached_behavior_set_distribution_hash(memcached_st *ptr, memcached_hash_t type) { - return set_hash(&ptr->distribution_hash, type); + hashkit_return_t rc; + rc= hashkit_set_base_function(&ptr->distribution_hashkit, (hashkit_hash_algorithm_t)type); + + return rc == HASHKIT_SUCCESS ? MEMCACHED_SUCCESS : MEMCACHED_FAILURE; } memcached_hash_t memcached_behavior_get_distribution_hash(memcached_st *ptr) { - return ptr->distribution_hash; + return (memcached_hash_t)hashkit_get_base_function(&ptr->distribution_hashkit); } diff --git a/libmemcached/constants.h b/libmemcached/constants.h index 3446c9cc..ab210c3c 100644 --- a/libmemcached/constants.h +++ b/libmemcached/constants.h @@ -145,6 +145,7 @@ typedef enum { MEMCACHED_HASH_HSIEH, MEMCACHED_HASH_MURMUR, MEMCACHED_HASH_JENKINS, + MEMCACHED_HASH_CUSTOM, MEMCACHED_HASH_MAX } memcached_hash_t; diff --git a/libmemcached/hash.c b/libmemcached/hash.c index 6ead8d46..e6458c25 100644 --- a/libmemcached/hash.c +++ b/libmemcached/hash.c @@ -1,109 +1,9 @@ #include "common.h" -/* Defines */ -static uint64_t FNV_64_INIT= UINT64_C(0xcbf29ce484222325); -static uint64_t FNV_64_PRIME= UINT64_C(0x100000001b3); - -static uint32_t FNV_32_INIT= 2166136261UL; -static uint32_t FNV_32_PRIME= 16777619; - -/* Prototypes */ -static uint32_t internal_generate_hash(const char *key, size_t key_length); -static uint32_t internal_generate_md5(const char *key, size_t key_length); - uint32_t memcached_generate_hash_value(const char *key, size_t key_length, memcached_hash_t hash_algorithm) { - uint32_t hash= 1; /* Just here to remove compile warning */ - uint32_t x= 0; - - switch (hash_algorithm) - { - case MEMCACHED_HASH_DEFAULT: - hash= internal_generate_hash(key, key_length); - break; - case MEMCACHED_HASH_MD5: - hash= internal_generate_md5(key, key_length); - break; - case MEMCACHED_HASH_CRC: - hash= ((hash_crc32(key, key_length) >> 16) & 0x7fff); - if (hash == 0) - hash= 1; - break; - /* FNV hash'es lifted from Dustin Sallings work */ - case MEMCACHED_HASH_FNV1_64: - { - /* Thanks to pierre@demartines.com for the pointer */ - uint64_t temp_hash; - - temp_hash= FNV_64_INIT; - for (x= 0; x < key_length; x++) - { - temp_hash *= FNV_64_PRIME; - temp_hash ^= (uint64_t)key[x]; - } - hash= (uint32_t)temp_hash; - } - break; - case MEMCACHED_HASH_FNV1A_64: - { - hash= (uint32_t) FNV_64_INIT; - for (x= 0; x < key_length; x++) - { - uint32_t val= (uint32_t)key[x]; - hash ^= val; - hash *= (uint32_t) FNV_64_PRIME; - } - } - break; - case MEMCACHED_HASH_FNV1_32: - { - hash= FNV_32_INIT; - for (x= 0; x < key_length; x++) - { - uint32_t val= (uint32_t)key[x]; - hash *= FNV_32_PRIME; - hash ^= val; - } - } - break; - case MEMCACHED_HASH_FNV1A_32: - { - hash= FNV_32_INIT; - for (x= 0; x < key_length; x++) - { - uint32_t val= (uint32_t)key[x]; - hash ^= val; - hash *= FNV_32_PRIME; - } - } - break; - case MEMCACHED_HASH_HSIEH: - { -#ifdef HAVE_HSIEH_HASH - hash= hsieh_hash(key, key_length); -#endif - break; - } - case MEMCACHED_HASH_MURMUR: - { - hash= murmur_hash(key, key_length); - break; - } - case MEMCACHED_HASH_JENKINS: - { - hash= jenkins_hash(key, key_length, 13); - break; - } - case MEMCACHED_HASH_MAX: - default: - { - WATCHPOINT_ASSERT(0); - break; - } - } - - return hash; + return libhashkit_generate_value(key, key_length, (hashkit_hash_algorithm_t)hash_algorithm); } uint32_t generate_hash(memcached_st *ptr, const char *key, size_t key_length) @@ -116,8 +16,9 @@ uint32_t generate_hash(memcached_st *ptr, const char *key, size_t key_length) if (memcached_server_count(ptr) == 1) return 0; - hash= memcached_generate_hash_value(key, key_length, ptr->hash); + hash= hashkit_generate_value(&ptr->hashkit, key, key_length); WATCHPOINT_ASSERT(hash); + return hash; } @@ -206,34 +107,3 @@ uint32_t memcached_generate_hash(memcached_st *ptr, const char *key, size_t key_ return dispatch_host(ptr, hash); } - -static uint32_t internal_generate_hash(const char *key, size_t key_length) -{ - const char *ptr= key; - uint32_t value= 0; - - while (key_length--) - { - uint32_t val= (uint32_t) *ptr++; - value += val; - value += (value << 10); - value ^= (value >> 6); - } - value += (value << 3); - value ^= (value >> 11); - value += (value << 15); - - return value == 0 ? 1 : (uint32_t) value; -} - -static uint32_t internal_generate_md5(const char *key, size_t key_length) -{ - unsigned char results[16]; - - md5_signature((unsigned char*)key, (unsigned int)key_length, results); - - return ((uint32_t) (results[3] & 0xFF) << 24) - | ((uint32_t) (results[2] & 0xFF) << 16) - | ((uint32_t) (results[1] & 0xFF) << 8) - | (results[0] & 0xFF); -} diff --git a/libmemcached/hosts.c b/libmemcached/hosts.c index c6c9eb8e..6853845a 100644 --- a/libmemcached/hosts.c +++ b/libmemcached/hosts.c @@ -213,17 +213,16 @@ static memcached_return_t update_continuum(memcached_st *ptr) if (is_ketama_weighted) { - unsigned int i; - for (i = 0; i < pointer_per_hash; i++) + for (uint32_t x = 0; x < pointer_per_hash; x++) { - value= ketama_server_hash(sort_host, (uint32_t) sort_host_length, (int) i); + value= ketama_server_hash(sort_host, (uint32_t) sort_host_length, (int) x); ptr->continuum[continuum_index].index= host_index; ptr->continuum[continuum_index++].value= value; } } else { - value= memcached_generate_hash_value(sort_host, sort_host_length, ptr->distribution_hash); + value= hashkit_generate_value(&ptr->distribution_hashkit, sort_host, sort_host_length); ptr->continuum[continuum_index].index= host_index; ptr->continuum[continuum_index++].value= value; } @@ -258,17 +257,16 @@ static memcached_return_t update_continuum(memcached_st *ptr) if (is_ketama_weighted) { - unsigned int i; - for (i = 0; i < pointer_per_hash; i++) + for (uint32_t x = 0; x < pointer_per_hash; x++) { - value= ketama_server_hash(sort_host, (uint32_t) sort_host_length, (int) i); + value= ketama_server_hash(sort_host, (uint32_t) sort_host_length, (int) x); ptr->continuum[continuum_index].index= host_index; ptr->continuum[continuum_index++].value= value; } } else { - value= memcached_generate_hash_value(sort_host, sort_host_length, ptr->distribution_hash); + value= hashkit_generate_value(&ptr->distribution_hashkit, sort_host, sort_host_length); ptr->continuum[continuum_index].index= host_index; ptr->continuum[continuum_index++].value= value; } diff --git a/libmemcached/include.am b/libmemcached/include.am index d8549d69..a786b222 100644 --- a/libmemcached/include.am +++ b/libmemcached/include.am @@ -118,8 +118,8 @@ if INCLUDE_HSIEH_SRC libmemcached_libmemcached_la_SOURCES += libmemcached/hsieh_hash.c endif -libmemcached_libmemcached_la_DEPENDENCIES= libmemcached/libmemcachedcallbacks.la libmemcached/libmemcachedinternal.la -libmemcached_libmemcached_la_LIBADD= $(LIBM) libmemcached/libmemcachedcallbacks.la libmemcached/libmemcachedinternal.la +libmemcached_libmemcached_la_DEPENDENCIES= libmemcached/libmemcachedcallbacks.la libmemcached/libmemcachedinternal.la libhashkit/libhashkit.la +libmemcached_libmemcached_la_LIBADD= $(LIBM) libmemcached/libmemcachedcallbacks.la libmemcached/libmemcachedinternal.la libhashkit/libhashkit.la libmemcached_libmemcached_la_LDFLAGS= ${AM_LDFLAGS} -version-info ${MEMCACHED_LIBRARY_VERSION} if BUILD_LIBMEMCACHEDUTIL diff --git a/libmemcached/memcached.c b/libmemcached/memcached.c index c53d958a..be084199 100644 --- a/libmemcached/memcached.c +++ b/libmemcached/memcached.c @@ -28,13 +28,18 @@ static const memcached_st global_copy= { } }; -static inline void _memcached_init(memcached_st *self) +static inline bool _memcached_init(memcached_st *self) { self->state= global_copy.state; self->flags= global_copy.flags; self->distribution= MEMCACHED_DISTRIBUTION_MODULA; - self->hash= MEMCACHED_HASH_DEFAULT; + + hashkit_st *hash_ptr; + hash_ptr= hashkit_create(&self->hashkit); + if (! hash_ptr) + return false; + self->continuum_points_counter= 0; self->number_of_hosts= 0; @@ -63,11 +68,11 @@ static inline void _memcached_init(memcached_st *self) self->next_distribution_rebuild= 0; self->prefix_key_length= 0; self->number_of_replicas= 0; - self->distribution_hash= MEMCACHED_HASH_DEFAULT; + hash_ptr= hashkit_create(&self->distribution_hashkit); + if (! hash_ptr) + return false; self->continuum= NULL; - - memcached_set_memory_allocators(self, NULL, NULL, NULL, NULL, NULL); self->allocators= memcached_allocators_return_default(); self->on_clone= NULL; @@ -75,6 +80,8 @@ static inline void _memcached_init(memcached_st *self) self->get_key_failure= NULL; self->delete_trigger= NULL; self->callbacks= NULL; + + return true; } memcached_st *memcached_create(memcached_st *ptr) @@ -100,7 +107,11 @@ memcached_st *memcached_create(memcached_st *ptr) memcached_set_processing_input(ptr, false); #endif - _memcached_init(ptr); + if (! _memcached_init(ptr)) + { + memcached_free(ptr); + return NULL; + } if (! memcached_result_create(ptr, &ptr->result)) { @@ -198,8 +209,23 @@ memcached_st *memcached_clone(memcached_st *clone, memcached_st *source) new_clone->connect_timeout= source->connect_timeout; new_clone->retry_timeout= source->retry_timeout; new_clone->distribution= source->distribution; - new_clone->hash= source->hash; - new_clone->distribution_hash= source->distribution_hash; + + hashkit_st *hash_ptr; + + hash_ptr= hashkit_clone(&new_clone->hashkit, &source->hashkit); + if (! hash_ptr) + { + memcached_free(new_clone); + return NULL; + } + + hash_ptr= hashkit_clone(&new_clone->distribution_hashkit, &source->distribution_hashkit); + if (! hash_ptr) + { + memcached_free(new_clone); + return NULL; + } + new_clone->user_data= source->user_data; new_clone->snd_timeout= source->snd_timeout; diff --git a/libmemcached/memcached.h b/libmemcached/memcached.h index 044b6f0b..a98a8c82 100644 --- a/libmemcached/memcached.h +++ b/libmemcached/memcached.h @@ -29,6 +29,7 @@ #include #include #include +#include // Everything above this line must be in the order specified. #include #include @@ -83,7 +84,7 @@ struct memcached_st { bool verify_key:1; } flags; memcached_server_distribution_t distribution; - memcached_hash_t hash; + hashkit_st hashkit; uint32_t continuum_points_counter; // Ketama uint32_t number_of_hosts; memcached_server_st *servers; @@ -105,7 +106,7 @@ struct memcached_st { time_t next_distribution_rebuild; // Ketama size_t prefix_key_length; uint32_t number_of_replicas; - memcached_hash_t distribution_hash; + hashkit_st distribution_hashkit; memcached_result_st result; memcached_continuum_item_st *continuum; // Ketama diff --git a/tests/hashkit_functions.c b/tests/hashkit_functions.c index d97b40c8..b7403e18 100644 --- a/tests/hashkit_functions.c +++ b/tests/hashkit_functions.c @@ -320,6 +320,9 @@ static test_return_t hashkit_set_base_function_test(hashkit_st *hashk) if (rc == HASHKIT_FAILURE && algo == HASHKIT_HASH_HSIEH) continue; + if (rc == HASHKIT_FAILURE && algo == HASHKIT_HASH_CUSTOM) + continue; + test_true(rc == HASHKIT_SUCCESS); switch (algo) @@ -354,6 +357,7 @@ static test_return_t hashkit_set_base_function_test(hashkit_st *hashk) case HASHKIT_HASH_JENKINS: list= jenkins_values; break; + case HASHKIT_HASH_CUSTOM: case HASHKIT_HASH_MAX: default: list= NULL; @@ -400,10 +404,40 @@ static test_return_t hashkit_set_base_function_custom_test(hashkit_st *hashk) return TEST_SUCCESS; } +static test_return_t hashkit_get_base_function_test(hashkit_st *hashk) +{ + for (hashkit_hash_algorithm_t algo = HASHKIT_HASH_DEFAULT; algo < HASHKIT_HASH_MAX; algo++) + { + hashkit_return_t rc; + + if (HASHKIT_HASH_CUSTOM || HASHKIT_HASH_HSIEH) + continue; + + rc= hashkit_set_base_function(hashk, algo); + test_true(rc == HASHKIT_SUCCESS); + + test_true(hashkit_get_base_function(hashk) == algo); + } + return TEST_SUCCESS; +} + +static test_return_t hashkit_compare_test(hashkit_st *hashk) +{ + hashkit_st *clone; + + clone= hashkit_clone(NULL, hashk); + + test_true(hashkit_compare(clone, hashk)); + + return TEST_SUCCESS; +} + test_st hashkit_st_functions[] ={ {"hashkit_generate_value", 0, (test_callback_fn)hashkit_generate_value_test}, {"hashkit_set_base_function", 0, (test_callback_fn)hashkit_set_base_function_test}, {"hashkit_set_base_function_custom", 0, (test_callback_fn)hashkit_set_base_function_custom_test}, + {"hashkit_get_base_function", 0, (test_callback_fn)hashkit_get_base_function_test}, + {"hashkit_compare", 0, (test_callback_fn)hashkit_compare_test}, {0, 0, 0} }; diff --git a/tests/mem_functions.c b/tests/mem_functions.c index 4c1b56b5..6a8cb11f 100644 --- a/tests/mem_functions.c +++ b/tests/mem_functions.c @@ -258,8 +258,8 @@ static test_return_t clone_test(memcached_st *memc) test_true(memc_clone->flags.randomize_replica_read == memc->flags.randomize_replica_read); } test_true(memc_clone->get_key_failure == memc->get_key_failure); - test_true(memc_clone->hash == memc->hash); - test_true(memc_clone->distribution_hash == memc->distribution_hash); + test_true(hashkit_compare(&memc_clone->hashkit, &memc->hashkit)); + test_true(hashkit_compare(&memc_clone->distribution_hashkit, &memc->distribution_hashkit)); test_true(memc_clone->io_bytes_watermark == memc->io_bytes_watermark); test_true(memc_clone->io_msg_watermark == memc->io_msg_watermark); test_true(memc_clone->io_key_prefetch == memc->io_key_prefetch); -- 2.30.2