From ac7352545826996e3866c599e4a8eff05fb662ca Mon Sep 17 00:00:00 2001 From: Xenofon Foukas Date: Thu, 15 Feb 2024 15:21:42 +0000 Subject: [PATCH] Add support for custom memory allocators for rculfhash The current implementation of rculfhash relies on calloc() to allocate memory for its buckets. This can in some cases lead to latency spikes when accessing the hash table, which can be avoided by using an optimized custom memory allocator. However, there is currently no way of replacing the default allocator with a custom one. This commit allows custom allocators to be used during the table initialization. The default behavior of the hash table remains unaffected, by using the stdlib calloc() and free(), if no custom allocator is given. Signed-off-by: Xenofon Foukas Signed-off-by: Mathieu Desnoyers Change-Id: Id9a405e5dc42e5564ff8623394c86056a4d1ff48 --- include/urcu/rculfhash.h | 73 +++++++++++++++++++++++++++++++++++- src/rculfhash-internal.h | 11 ++++-- src/rculfhash-mm-chunk.c | 16 ++++---- src/rculfhash-mm-mmap.c | 10 ++--- src/rculfhash-mm-order.c | 16 ++++---- src/rculfhash.c | 80 +++++++++++++++++++++++++++++++++++----- 6 files changed, 170 insertions(+), 36 deletions(-) diff --git a/include/urcu/rculfhash.h b/include/urcu/rculfhash.h index 8385cd9..8b57cd8 100644 --- a/include/urcu/rculfhash.h +++ b/include/urcu/rculfhash.h @@ -68,6 +68,18 @@ struct cds_lfht_iter { #endif }; +/* + * cds_lfht_alloc: Callbacks if we want to use custom memory allocator. + */ +struct cds_lfht_alloc { + void *(*malloc)(void *state, size_t size); + void *(*calloc)(void *state, size_t nmemb, size_t size); + void *(*realloc)(void *state, void *ptr, size_t size); + void *(*aligned_alloc)(void *state, size_t alignment, size_t size); + void (*free)(void *state, void *ptr); + void *state; +}; + static inline struct cds_lfht_node *cds_lfht_iter_get_node(struct cds_lfht_iter *iter) { @@ -115,7 +127,7 @@ enum { struct cds_lfht_mm_type { struct cds_lfht *(*alloc_cds_lfht)(unsigned long min_nr_alloc_buckets, - unsigned long max_nr_buckets); + unsigned long max_nr_buckets, const struct cds_lfht_alloc *alloc); void (*alloc_bucket_table)(struct cds_lfht *ht, unsigned long order); void (*free_bucket_table)(struct cds_lfht *ht, unsigned long order); struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht, @@ -138,6 +150,19 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size, const struct rcu_flavor_struct *flavor, pthread_attr_t *attr); +/* + * _cds_lfht_new_with_alloc - API used by cds_lfht_new_with_flavor_alloc. + */ +extern +struct cds_lfht *_cds_lfht_new_with_alloc(unsigned long init_size, + unsigned long min_nr_alloc_buckets, + unsigned long max_nr_buckets, + int flags, + const struct cds_lfht_mm_type *mm, + const struct cds_lfht_alloc *alloc, + const struct rcu_flavor_struct *flavor, + pthread_attr_t *attr); + /* * cds_lfht_new_flavor - allocate a hash table tied to a RCU flavor. * @init_size: number of buckets to allocate initially. Must be power of two. @@ -180,6 +205,52 @@ struct cds_lfht *cds_lfht_new_flavor(unsigned long init_size, flags, NULL, flavor, attr); } +/* + * cds_lfht_new_with_flavor_alloc - allocate a hash table tied to a RCU flavor. + * @init_size: number of buckets to allocate initially. Must be power of two. + * @min_nr_alloc_buckets: the minimum number of allocated buckets. + * (must be power of two) + * @max_nr_buckets: the maximum number of hash table buckets allowed. + * (must be power of two, 0 is accepted, means + * "infinite") + * @flavor: flavor of liburcu to use to synchronize the hash table + * @alloc: Custom memory allocator for hash table memory management. + * NULL for default. If a custom allocator is used, then + * the whole interface of struct cds_lfht_alloc must be implemented. + * @flags: hash table creation flags (can be combined with bitwise or: '|'). + * 0: no flags. + * CDS_LFHT_AUTO_RESIZE: automatically resize hash table. + * CDS_LFHT_ACCOUNTING: count the number of node addition + * and removal in the table + * @attr: optional resize worker thread attributes. NULL for default. + * + * Return NULL on error. + * Note: the RCU flavor must be already included before the hash table header. + * + * The programmer is responsible for ensuring that resize operation has a + * priority equal to hash table updater threads. It should be performed by + * specifying the appropriate priority in the pthread "attr" argument, and, + * for CDS_LFHT_AUTO_RESIZE, by ensuring that call_rcu worker threads also have + * this priority level. Having lower priority for call_rcu and resize threads + * does not pose any correctness issue, but the resize operations could be + * starved by updates, thus leading to long hash table bucket chains. + * Threads calling cds_lfht_new are NOT required to be registered RCU + * read-side threads. It can be called very early. (e.g. before RCU is + * initialized) + */ +static inline +struct cds_lfht *cds_lfht_new_with_flavor_alloc(unsigned long init_size, + unsigned long min_nr_alloc_buckets, + unsigned long max_nr_buckets, + int flags, + const struct rcu_flavor_struct *flavor, + const struct cds_lfht_alloc *alloc, + pthread_attr_t *attr) +{ + return _cds_lfht_new_with_alloc(init_size, min_nr_alloc_buckets, max_nr_buckets, + flags, NULL, alloc, flavor, attr); +} + #ifdef URCU_API_MAP /* diff --git a/src/rculfhash-internal.h b/src/rculfhash-internal.h index 081f32e..7225ec9 100644 --- a/src/rculfhash-internal.h +++ b/src/rculfhash-internal.h @@ -59,6 +59,7 @@ struct cds_lfht { /* Initial configuration items */ unsigned long max_nr_buckets; const struct cds_lfht_mm_type *mm; /* memory management plugin */ + const struct cds_lfht_alloc *alloc; /* memory allocator for mm */ const struct rcu_flavor_struct *flavor; /* RCU flavor */ long count; /* global approximate item count */ @@ -139,30 +140,32 @@ extern unsigned int cds_lfht_fls_ulong(unsigned long x); extern int cds_lfht_get_count_order_ulong(unsigned long x); #ifdef POISON_FREE -#define poison_free(ptr) \ +#define poison_free(alloc, ptr) \ do { \ if (ptr) { \ memset(ptr, 0x42, sizeof(*(ptr))); \ - free(ptr); \ + alloc->free(alloc->state, ptr); \ } \ } while (0) #else -#define poison_free(ptr) free(ptr) +#define poison_free(alloc, ptr) alloc->free(alloc->state, ptr) #endif static inline struct cds_lfht *__default_alloc_cds_lfht( const struct cds_lfht_mm_type *mm, + const struct cds_lfht_alloc *alloc, unsigned long cds_lfht_size, unsigned long min_nr_alloc_buckets, unsigned long max_nr_buckets) { struct cds_lfht *ht; - ht = calloc(1, cds_lfht_size); + ht = alloc->calloc(alloc->state, 1, cds_lfht_size); urcu_posix_assert(ht); ht->mm = mm; + ht->alloc = alloc; ht->bucket_at = mm->bucket_at; ht->min_nr_alloc_buckets = min_nr_alloc_buckets; ht->min_alloc_buckets_order = diff --git a/src/rculfhash-mm-chunk.c b/src/rculfhash-mm-chunk.c index cf3a9ff..93931ee 100644 --- a/src/rculfhash-mm-chunk.c +++ b/src/rculfhash-mm-chunk.c @@ -14,15 +14,15 @@ static void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order) { if (order == 0) { - ht->tbl_chunk[0] = calloc(ht->min_nr_alloc_buckets, - sizeof(struct cds_lfht_node)); + ht->tbl_chunk[0] = ht->alloc->calloc(ht->alloc->state, + ht->min_nr_alloc_buckets, sizeof(struct cds_lfht_node)); urcu_posix_assert(ht->tbl_chunk[0]); } else if (order > ht->min_alloc_buckets_order) { unsigned long i, len = 1UL << (order - 1 - ht->min_alloc_buckets_order); for (i = len; i < 2 * len; i++) { - ht->tbl_chunk[i] = calloc(ht->min_nr_alloc_buckets, - sizeof(struct cds_lfht_node)); + ht->tbl_chunk[i] = ht->alloc->calloc(ht->alloc->state, + ht->min_nr_alloc_buckets, sizeof(struct cds_lfht_node)); urcu_posix_assert(ht->tbl_chunk[i]); } } @@ -38,12 +38,12 @@ static void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order) { if (order == 0) - poison_free(ht->tbl_chunk[0]); + poison_free(ht->alloc, ht->tbl_chunk[0]); else if (order > ht->min_alloc_buckets_order) { unsigned long i, len = 1UL << (order - 1 - ht->min_alloc_buckets_order); for (i = len; i < 2 * len; i++) - poison_free(ht->tbl_chunk[i]); + poison_free(ht->alloc, ht->tbl_chunk[i]); } /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */ } @@ -60,7 +60,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index) static struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets, - unsigned long max_nr_buckets) + unsigned long max_nr_buckets, const struct cds_lfht_alloc *alloc) { unsigned long nr_chunks, cds_lfht_size; @@ -72,7 +72,7 @@ struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets, cds_lfht_size = max(cds_lfht_size, sizeof(struct cds_lfht)); return __default_alloc_cds_lfht( - &cds_lfht_mm_chunk, cds_lfht_size, + &cds_lfht_mm_chunk, alloc, cds_lfht_size, min_nr_alloc_buckets, max_nr_buckets); } diff --git a/src/rculfhash-mm-mmap.c b/src/rculfhash-mm-mmap.c index be931e0..2b4bc42 100644 --- a/src/rculfhash-mm-mmap.c +++ b/src/rculfhash-mm-mmap.c @@ -118,8 +118,8 @@ void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order) if (order == 0) { if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) { /* small table */ - ht->tbl_mmap = calloc(ht->max_nr_buckets, - sizeof(*ht->tbl_mmap)); + ht->tbl_mmap = ht->alloc->calloc(ht->alloc->state, + ht->max_nr_buckets, sizeof(*ht->tbl_mmap)); urcu_posix_assert(ht->tbl_mmap); return; } @@ -150,7 +150,7 @@ void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order) if (order == 0) { if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) { /* small table */ - poison_free(ht->tbl_mmap); + poison_free(ht->alloc, ht->tbl_mmap); return; } /* large table */ @@ -174,7 +174,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index) static struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets, - unsigned long max_nr_buckets) + unsigned long max_nr_buckets, const struct cds_lfht_alloc *alloc) { unsigned long page_bucket_size; @@ -189,7 +189,7 @@ struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets, } return __default_alloc_cds_lfht( - &cds_lfht_mm_mmap, sizeof(struct cds_lfht), + &cds_lfht_mm_mmap, alloc, sizeof(struct cds_lfht), min_nr_alloc_buckets, max_nr_buckets); } diff --git a/src/rculfhash-mm-order.c b/src/rculfhash-mm-order.c index 1014c38..2b0f707 100644 --- a/src/rculfhash-mm-order.c +++ b/src/rculfhash-mm-order.c @@ -14,12 +14,12 @@ static void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order) { if (order == 0) { - ht->tbl_order[0] = calloc(ht->min_nr_alloc_buckets, - sizeof(struct cds_lfht_node)); + ht->tbl_order[0] = ht->alloc->calloc(ht->alloc->state, + ht->min_nr_alloc_buckets, sizeof(struct cds_lfht_node)); urcu_posix_assert(ht->tbl_order[0]); } else if (order > ht->min_alloc_buckets_order) { - ht->tbl_order[order] = calloc(1UL << (order -1), - sizeof(struct cds_lfht_node)); + ht->tbl_order[order] = ht->alloc->calloc(ht->alloc->state, + 1UL << (order -1), sizeof(struct cds_lfht_node)); urcu_posix_assert(ht->tbl_order[order]); } /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */ @@ -34,9 +34,9 @@ static void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order) { if (order == 0) - poison_free(ht->tbl_order[0]); + poison_free(ht->alloc, ht->tbl_order[0]); else if (order > ht->min_alloc_buckets_order) - poison_free(ht->tbl_order[order]); + poison_free(ht->alloc, ht->tbl_order[order]); /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */ } @@ -62,10 +62,10 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index) static struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets, - unsigned long max_nr_buckets) + unsigned long max_nr_buckets, const struct cds_lfht_alloc *alloc) { return __default_alloc_cds_lfht( - &cds_lfht_mm_order, sizeof(struct cds_lfht), + &cds_lfht_mm_order, alloc, sizeof(struct cds_lfht), min_nr_alloc_buckets, max_nr_buckets); } diff --git a/src/rculfhash.c b/src/rculfhash.c index 02c7f0f..8d7c1e6 100644 --- a/src/rculfhash.c +++ b/src/rculfhash.c @@ -249,6 +249,7 @@ #include #include #include +#include #include "compat-getcpu.h" #include @@ -568,6 +569,50 @@ unsigned int cds_lfht_fls_ulong(unsigned long x) #endif } +static void *cds_lfht_malloc(void *state __attribute__((unused)), + size_t size) +{ + return malloc(size); +} + +static void *cds_lfht_calloc(void *state __attribute__((unused)), + size_t nmemb, size_t size) +{ + return calloc(nmemb, size); +} + +static void *cds_lfht_realloc(void *state __attribute__((unused)), + void *ptr, size_t size) +{ + return realloc(ptr, size); +} + +static void *cds_lfht_aligned_alloc(void *state __attribute__((unused)), + size_t alignment, size_t size) +{ + void *ptr; + + if (posix_memalign(&ptr, alignment, size)) + return NULL; + return ptr; +} + +static void cds_lfht_free(void *state __attribute__((unused)), void *ptr) +{ + free(ptr); +} + + +/* Default memory allocator */ +static struct cds_lfht_alloc cds_lfht_default_alloc = { + .malloc = cds_lfht_malloc, + .calloc = cds_lfht_calloc, + .realloc = cds_lfht_realloc, + .aligned_alloc = cds_lfht_aligned_alloc, + .free = cds_lfht_free, + .state = NULL, +}; + /* * Return the minimum order for which x <= (1UL << order). * Return -1 if x is 0. @@ -666,7 +711,7 @@ void alloc_split_items_count(struct cds_lfht *ht) urcu_posix_assert(split_count_mask >= 0); if (ht->flags & CDS_LFHT_ACCOUNTING) { - ht->split_count = calloc(split_count_mask + 1, + ht->split_count = ht->alloc->calloc(ht->alloc->state, split_count_mask + 1, sizeof(struct ht_items_count)); urcu_posix_assert(ht->split_count); } else { @@ -677,7 +722,7 @@ void alloc_split_items_count(struct cds_lfht *ht) static void free_split_items_count(struct cds_lfht *ht) { - poison_free(ht->split_count); + poison_free(ht->alloc, ht->split_count); } static @@ -1262,7 +1307,7 @@ void partition_resize_helper(struct cds_lfht *ht, unsigned long i, nr_threads = 1; } partition_len = len >> cds_lfht_get_count_order_ulong(nr_threads); - work = calloc(nr_threads, sizeof(*work)); + work = ht->alloc->calloc(ht->alloc->state, nr_threads, sizeof(*work)); if (!work) { dbg_printf("error allocating for resize, single-threading\n"); goto fallback; @@ -1303,7 +1348,7 @@ void partition_resize_helper(struct cds_lfht *ht, unsigned long i, ret = pthread_join(work[thread].thread_id, NULL); urcu_posix_assert(!ret); } - free(work); + ht->alloc->free(ht->alloc->state, work); /* * A pthread_create failure above will either lead in us having @@ -1596,11 +1641,12 @@ void cds_lfht_node_init_deleted(struct cds_lfht_node *node) node->next = flag_removed(NULL); } -struct cds_lfht *_cds_lfht_new(unsigned long init_size, +struct cds_lfht *_cds_lfht_new_with_alloc(unsigned long init_size, unsigned long min_nr_alloc_buckets, unsigned long max_nr_buckets, int flags, const struct cds_lfht_mm_type *mm, + const struct cds_lfht_alloc *alloc, const struct rcu_flavor_struct *flavor, pthread_attr_t *attr) { @@ -1637,7 +1683,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size, max_nr_buckets = max(max_nr_buckets, min_nr_alloc_buckets); init_size = min(init_size, max_nr_buckets); - ht = mm->alloc_cds_lfht(min_nr_alloc_buckets, max_nr_buckets); + ht = mm->alloc_cds_lfht(min_nr_alloc_buckets, max_nr_buckets, alloc ? : &cds_lfht_default_alloc); + urcu_posix_assert(ht); urcu_posix_assert(ht->mm == mm); urcu_posix_assert(ht->bucket_at == mm->bucket_at); @@ -1657,6 +1704,19 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size, return ht; } +struct cds_lfht *_cds_lfht_new(unsigned long init_size, + unsigned long min_nr_alloc_buckets, + unsigned long max_nr_buckets, + int flags, + const struct cds_lfht_mm_type *mm, + const struct rcu_flavor_struct *flavor, + pthread_attr_t *attr) +{ + return _cds_lfht_new_with_alloc(init_size, + min_nr_alloc_buckets, max_nr_buckets, + flags, mm, NULL, flavor, attr); +} + void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash, cds_lfht_match_fct match, const void *key, struct cds_lfht_iter *iter) @@ -1945,7 +2005,7 @@ void do_auto_resize_destroy_cb(struct urcu_work *work) if (ret) urcu_die(ret); ht->flavor->unregister_thread(); - poison_free(ht); + poison_free(ht->alloc, ht); } /* @@ -1989,7 +2049,7 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr) ret = pthread_mutex_destroy(&ht->resize_mutex); if (ret) ret = -EBUSY; - poison_free(ht); + poison_free(ht->alloc, ht); return ret; } @@ -2144,7 +2204,7 @@ void do_resize_cb(struct urcu_work *work) _do_cds_lfht_resize(ht); mutex_unlock(&ht->resize_mutex); ht->flavor->unregister_thread(); - poison_free(work); + poison_free(ht->alloc, work); } static @@ -2160,7 +2220,7 @@ void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht) if (uatomic_load(&ht->in_progress_destroy, CMM_RELAXED)) { return; } - work = malloc(sizeof(*work)); + work = ht->alloc->malloc(ht->alloc->state, sizeof(*work)); if (work == NULL) { dbg_printf("error allocating resize work, bailing out\n"); return; -- 2.39.5