From 308d1cb3650b63d373e60eef0582d6e238b0d2d0 Mon Sep 17 00:00:00 2001 From: Lai Jiangshan Date: Mon, 28 Nov 2011 08:30:55 -0500 Subject: [PATCH] add rculfhash-mm-chunk.c memory management [ Edit by Mathieu Desnoyers: Update comment above struct cds_lfht_node *tbl_chunk. ] Signed-off-by: Lai Jiangshan Signed-off-by: Mathieu Desnoyers --- Makefile.am | 2 +- rculfhash-internal.h | 14 ++++++ rculfhash-mm-chunk.c | 107 +++++++++++++++++++++++++++++++++++++++++++ urcu/rculfhash.h | 1 + 4 files changed, 123 insertions(+), 1 deletion(-) create mode 100644 rculfhash-mm-chunk.c diff --git a/Makefile.am b/Makefile.am index 4d3f7bd..853ecd5 100644 --- a/Makefile.am +++ b/Makefile.am @@ -35,7 +35,7 @@ if COMPAT_FUTEX COMPAT+=compat_futex.c endif -RCULFHASH=rculfhash.c rculfhash-mm-order.c +RCULFHASH=rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c lib_LTLIBRARIES = liburcu-common.la \ liburcu.la liburcu-qsbr.la \ diff --git a/rculfhash-internal.h b/rculfhash-internal.h index 820e62c..f7c6590 100644 --- a/rculfhash-internal.h +++ b/rculfhash-internal.h @@ -38,6 +38,8 @@ #define MAX_TABLE_ORDER 64 #endif +#define MAX_CHUNK_TABLE (1UL << 10) + #ifndef min #define min(a, b) ((a) < (b) ? (a) : (b)) #endif @@ -94,6 +96,18 @@ struct cds_lfht { * levels to improve cache locality for small index orders. */ struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER]; + + /* + * Contains the bucket node chunks. The size of each + * bucket node chunk is ->min_alloc_size (we avoid to + * allocate chunks with different size). Chunks improve + * cache locality for small index orders, and are more + * friendly with environments where allocation of large + * contiguous memory areas is challenging due to memory + * fragmentation concerns or inability to use virtual + * memory addressing. + */ + struct cds_lfht_node *tbl_chunk[0]; }; }; diff --git a/rculfhash-mm-chunk.c b/rculfhash-mm-chunk.c new file mode 100644 index 0000000..0469776 --- /dev/null +++ b/rculfhash-mm-chunk.c @@ -0,0 +1,107 @@ +/* + * rculfhash-mm-chunk.c + * + * Chunk based memory management for Lock-Free RCU Hash Table + * + * Copyright 2011 - Lai Jiangshan + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include + +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)); + 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)); + assert(ht->tbl_chunk[i]); + } + } + /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */ +} + +/* + * cds_lfht_free_bucket_table() should be called with decreasing order. + * When cds_lfht_free_bucket_table(0) is called, it means the whole + * lfht is destroyed. + */ +static +void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order) +{ + if (order == 0) + poison_free(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]); + } + /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */ +} + +static +struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index) +{ + unsigned long chunk, offset; + + chunk = index >> ht->min_alloc_buckets_order; + offset = index & (ht->min_nr_alloc_buckets - 1); + return &ht->tbl_chunk[chunk][offset]; +} + +static +struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets, + unsigned long max_nr_buckets) +{ + struct cds_lfht *ht; + unsigned long nr_chunks, cds_lfht_size; + + min_nr_alloc_buckets = max(min_nr_alloc_buckets, + max_nr_buckets / MAX_CHUNK_TABLE); + + nr_chunks = max_nr_buckets / min_nr_alloc_buckets; + cds_lfht_size = offsetof(struct cds_lfht, tbl_chunk) + + sizeof(ht->tbl_chunk[0]) * nr_chunks; + cds_lfht_size = max(cds_lfht_size, sizeof(struct cds_lfht)); + ht = calloc(1, cds_lfht_size); + assert(ht); + + ht->mm = &cds_lfht_mm_chunk; + + ht->min_nr_alloc_buckets = min_nr_alloc_buckets; + ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets); + ht->max_nr_buckets = max_nr_buckets; + + ht->bucket_at = bucket_at; + + return ht; +} + +const struct cds_lfht_mm_type cds_lfht_mm_chunk = { + .alloc_cds_lfht = alloc_cds_lfht, + .alloc_bucket_table = cds_lfht_alloc_bucket_table, + .free_bucket_table = cds_lfht_free_bucket_table, + .bucket_at = bucket_at, +}; diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h index c03baf4..1224ea8 100644 --- a/urcu/rculfhash.h +++ b/urcu/rculfhash.h @@ -105,6 +105,7 @@ struct cds_lfht_mm_type { }; extern const struct cds_lfht_mm_type cds_lfht_mm_order; +extern const struct cds_lfht_mm_type cds_lfht_mm_chunk; /* * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly. -- 2.34.1