[lttng-dev] [PATCH 10/12] move memory management code out as rculfhash-mm-order.c
Mathieu Desnoyers
mathieu.desnoyers at efficios.com
Mon Nov 28 08:27:37 EST 2011
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Yep, this is clean! :)
Merged, thanks!
Mathieu
> ---
> Makefile.am | 5 ++-
> rculfhash-internal.h | 115 ++++++++++++++++++++++++++++++++++++++++++++++++
> rculfhash-mm-order.c | 101 ++++++++++++++++++++++++++++++++++++++++++
> rculfhash.c | 119 +++++---------------------------------------------
> urcu/rculfhash.h | 14 +++++-
> 5 files changed, 245 insertions(+), 109 deletions(-)
> create mode 100644 rculfhash-internal.h
> create mode 100644 rculfhash-mm-order.c
>
> diff --git a/Makefile.am b/Makefile.am
> index 1290551..4d3f7bd 100644
> --- a/Makefile.am
> +++ b/Makefile.am
> @@ -22,6 +22,7 @@ EXTRA_DIST = $(top_srcdir)/urcu/arch/*.h $(top_srcdir)/urcu/uatomic/*.h \
> gpl-2.0.txt lgpl-2.1.txt lgpl-relicensing.txt \
> README LICENSE compat_arch_x86.c \
> urcu-call-rcu-impl.h urcu-defer-impl.h \
> + rculfhash-internal.h \
> ChangeLog API.txt
>
> if COMPAT_ARCH
> @@ -34,6 +35,8 @@ if COMPAT_FUTEX
> COMPAT+=compat_futex.c
> endif
>
> +RCULFHASH=rculfhash.c rculfhash-mm-order.c
> +
> lib_LTLIBRARIES = liburcu-common.la \
> liburcu.la liburcu-qsbr.la \
> liburcu-mb.la liburcu-signal.la liburcu-bp.la \
> @@ -62,7 +65,7 @@ liburcu_signal_la_LIBADD = liburcu-common.la
> liburcu_bp_la_SOURCES = urcu-bp.c urcu-pointer.c $(COMPAT)
> liburcu_bp_la_LIBADD = liburcu-common.la
>
> -liburcu_cds_la_SOURCES = rculfqueue.c rculfstack.c rculfhash.c $(COMPAT)
> +liburcu_cds_la_SOURCES = rculfqueue.c rculfstack.c $(RCULFHASH) $(COMPAT)
> liburcu_cds_la_LIBADD = liburcu-common.la
>
> pkgconfigdir = $(libdir)/pkgconfig
> diff --git a/rculfhash-internal.h b/rculfhash-internal.h
> new file mode 100644
> index 0000000..820e62c
> --- /dev/null
> +++ b/rculfhash-internal.h
> @@ -0,0 +1,115 @@
> +#ifndef _URCU_RCULFHASH_INTERNAL_H
> +#define _URCU_RCULFHASH_INTERNAL_H
> +
> +/*
> + * urcu/rculfhash-internal.h
> + *
> + * Internal header for Lock-Free RCU Hash Table
> + *
> + * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> + * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
> + *
> + * 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 <urcu/rculfhash.h>
> +
> +#ifdef DEBUG
> +#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
> +#else
> +#define dbg_printf(fmt, args...)
> +#endif
> +
> +#if (CAA_BITS_PER_LONG == 32)
> +#define MAX_TABLE_ORDER 32
> +#else
> +#define MAX_TABLE_ORDER 64
> +#endif
> +
> +#ifndef min
> +#define min(a, b) ((a) < (b) ? (a) : (b))
> +#endif
> +
> +#ifndef max
> +#define max(a, b) ((a) > (b) ? (a) : (b))
> +#endif
> +
> +struct ht_items_count;
> +
> +/*
> + * cds_lfht: Top-level data structure representing a lock-free hash
> + * table. Defined in the implementation file to make it be an opaque
> + * cookie to users.
> + */
> +struct cds_lfht {
> + unsigned long size; /* always a power of 2, shared (RCU) */
> + int flags;
> +
> + /*
> + * We need to put the work threads offline (QSBR) when taking this
> + * mutex, because we use synchronize_rcu within this mutex critical
> + * section, which waits on read-side critical sections, and could
> + * therefore cause grace-period deadlock if we hold off RCU G.P.
> + * completion.
> + */
> + pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
> + pthread_attr_t *resize_attr; /* Resize threads attributes */
> + unsigned int in_progress_resize, in_progress_destroy;
> + unsigned long resize_target;
> + int resize_initiated;
> + const struct rcu_flavor_struct *flavor;
> +
> + long count; /* global approximate item count */
> + struct ht_items_count *split_count; /* split item count */
> +
> + /* memory management related fields are located at the end */
> + const struct cds_lfht_mm_type *mm;
> +
> + unsigned long min_alloc_buckets_order;
> + unsigned long min_nr_alloc_buckets;
> + unsigned long max_nr_buckets;
> +
> + struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
> + unsigned long index);
> +
> + union {
> + /*
> + * Contains the per order-index-level bucket node table.
> + * The size of each bucket node table is half the number
> + * of hashes contained in this order (except for order 0).
> + * The minimum allocation buckets size parameter allows
> + * combining the bucket node arrays of the lowermost
> + * levels to improve cache locality for small index orders.
> + */
> + struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
> + };
> +};
> +
> +extern unsigned int fls_ulong(unsigned long x);
> +extern int get_count_order_ulong(unsigned long x);
> +
> +#ifdef POISON_FREE
> +#define poison_free(ptr) \
> + do { \
> + if (ptr) { \
> + memset(ptr, 0x42, sizeof(*(ptr))); \
> + free(ptr); \
> + } \
> + } while (0)
> +#else
> +#define poison_free(ptr) free(ptr)
> +#endif
> +
> +#endif /* _URCU_RCULFHASH_INTERNAL_H */
> diff --git a/rculfhash-mm-order.c b/rculfhash-mm-order.c
> new file mode 100644
> index 0000000..69e2b62
> --- /dev/null
> +++ b/rculfhash-mm-order.c
> @@ -0,0 +1,101 @@
> +/*
> + * rculfhash-mm-order.c
> + *
> + * Order based memory management for Lock-Free RCU Hash Table
> + *
> + * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> + * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
> + *
> + * 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 <rculfhash-internal.h>
> +
> +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));
> + 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));
> + assert(ht->tbl_order[order]);
> + }
> + /* 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_order[0]);
> + else if (order > ht->min_alloc_buckets_order)
> + poison_free(ht->tbl_order[order]);
> + /* 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 order;
> +
> + if (index < ht->min_nr_alloc_buckets) {
> + dbg_printf("bucket index %lu order 0 aridx 0\n", index);
> + return &ht->tbl_order[0][index];
> + }
> + /*
> + * equivalent to get_count_order_ulong(index + 1), but optimizes
> + * away the non-existing 0 special-case for
> + * get_count_order_ulong.
> + */
> + order = fls_ulong(index);
> + dbg_printf("bucket index %lu order %lu aridx %lu\n",
> + index, order, index & ((1UL << (order - 1)) - 1));
> + return &ht->tbl_order[order][index & ((1UL << (order - 1)) - 1)];
> +}
> +
> +static
> +struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
> + unsigned long max_nr_buckets)
> +{
> + struct cds_lfht *ht;
> +
> + ht = calloc(1, sizeof(struct cds_lfht));
> + assert(ht);
> +
> + ht->mm = &cds_lfht_mm_order;
> +
> + 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_order = {
> + .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/rculfhash.c b/rculfhash.c
> index 8dc9c59..49c7863 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -165,15 +165,10 @@
> #include <urcu/uatomic.h>
> #include <urcu/compiler.h>
> #include <urcu/rculfhash.h>
> +#include <rculfhash-internal.h>
> #include <stdio.h>
> #include <pthread.h>
>
> -#ifdef DEBUG
> -#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
> -#else
> -#define dbg_printf(fmt, args...)
> -#endif
> -
> /*
> * Split-counters lazily update the global counter each 1024
> * addition/removal. It automatically keeps track of resize required.
> @@ -191,26 +186,12 @@
> #define MIN_TABLE_ORDER 0
> #define MIN_TABLE_SIZE (1UL << MIN_TABLE_ORDER)
>
> -#if (CAA_BITS_PER_LONG == 32)
> -#define MAX_TABLE_ORDER 32
> -#else
> -#define MAX_TABLE_ORDER 64
> -#endif
> -
> /*
> * Minimum number of bucket nodes to touch per thread to parallelize grow/shrink.
> */
> #define MIN_PARTITION_PER_THREAD_ORDER 12
> #define MIN_PARTITION_PER_THREAD (1UL << MIN_PARTITION_PER_THREAD_ORDER)
>
> -#ifndef min
> -#define min(a, b) ((a) < (b) ? (a) : (b))
> -#endif
> -
> -#ifndef max
> -#define max(a, b) ((a) > (b) ? (a) : (b))
> -#endif
> -
> /*
> * The removed flag needs to be updated atomically with the pointer.
> * It indicates that no node must attach to the node scheduled for
> @@ -240,45 +221,6 @@ struct ht_items_count {
> } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
>
> /*
> - * cds_lfht: Top-level data structure representing a lock-free hash
> - * table. Defined in the implementation file to make it be an opaque
> - * cookie to users.
> - */
> -struct cds_lfht {
> - unsigned long size; /* always a power of 2, shared (RCU) */
> - int flags;
> -
> - /*
> - * We need to put the work threads offline (QSBR) when taking this
> - * mutex, because we use synchronize_rcu within this mutex critical
> - * section, which waits on read-side critical sections, and could
> - * therefore cause grace-period deadlock if we hold off RCU G.P.
> - * completion.
> - */
> - pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
> - pthread_attr_t *resize_attr; /* Resize threads attributes */
> - unsigned int in_progress_resize, in_progress_destroy;
> - unsigned long resize_target;
> - int resize_initiated;
> - const struct rcu_flavor_struct *flavor;
> -
> - long count; /* global approximate item count */
> - struct ht_items_count *split_count; /* split item count */
> -
> - unsigned long min_alloc_buckets_order;
> - unsigned long min_nr_alloc_buckets;
> - unsigned long max_nr_buckets;
> - /*
> - * Contains the per order-index-level bucket node table. The size
> - * of each bucket node table is half the number of hashes contained
> - * in this order (except for order 0). The minimum allocation size
> - * parameter allows combining the bucket node arrays of the lowermost
> - * levels to improve cache locality for small index orders.
> - */
> - struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
> -};
> -
> -/*
> * rcu_resize_work: Contains arguments passed to RCU worker thread
> * responsible for performing lazy resize.
> */
> @@ -505,18 +447,6 @@ int get_count_order_ulong(unsigned long x)
> return fls_ulong(x - 1);
> }
>
> -#ifdef POISON_FREE
> -#define poison_free(ptr) \
> - do { \
> - if (ptr) { \
> - memset(ptr, 0x42, sizeof(*(ptr))); \
> - free(ptr); \
> - } \
> - } while (0)
> -#else
> -#define poison_free(ptr) free(ptr)
> -#endif
> -
> static
> void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth);
>
> @@ -743,16 +673,7 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
> static
> void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> {
> - if (order == 0) {
> - ht->tbl[0] = calloc(ht->min_nr_alloc_buckets,
> - sizeof(struct cds_lfht_node));
> - assert(ht->tbl[0]);
> - } else if (order > ht->min_alloc_buckets_order) {
> - ht->tbl[order] = calloc(1UL << (order -1),
> - sizeof(struct cds_lfht_node));
> - assert(ht->tbl[order]);
> - }
> - /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> + return ht->mm->alloc_bucket_table(ht, order);
> }
>
> /*
> @@ -763,32 +684,13 @@ void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> static
> void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> {
> - if (order == 0)
> - poison_free(ht->tbl[0]);
> - else if (order > ht->min_alloc_buckets_order)
> - poison_free(ht->tbl[order]);
> - /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> + return ht->mm->free_bucket_table(ht, order);
> }
>
> static inline
> struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> {
> - unsigned long order;
> -
> - if ((__builtin_constant_p(index) && index == 0)
> - || index < ht->min_nr_alloc_buckets) {
> - dbg_printf("bucket index %lu order 0 aridx 0\n", index);
> - return &ht->tbl[0][index];
> - }
> - /*
> - * equivalent to get_count_order_ulong(index + 1), but optimizes
> - * away the non-existing 0 special-case for
> - * get_count_order_ulong.
> - */
> - order = fls_ulong(index);
> - dbg_printf("bucket index %lu order %lu aridx %lu\n",
> - index, order, index & ((1UL << (order - 1)) - 1));
> - return &ht->tbl[order][index & ((1UL << (order - 1)) - 1)];
> + return ht->bucket_at(ht, index);
> }
>
> static inline
> @@ -1354,6 +1256,7 @@ 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)
> {
> @@ -1368,7 +1271,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> if (!init_size || (init_size & (init_size - 1)))
> return NULL;
>
> - if (!max_nr_buckets)
> + /* max_nr_buckets == 0 for order based mm means infinite */
> + if (mm == &cds_lfht_mm_order && !max_nr_buckets)
> max_nr_buckets = 1UL << (MAX_TABLE_ORDER - 1);
>
> /* max_nr_buckets must be power of two */
> @@ -1379,8 +1283,12 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> init_size = max(init_size, MIN_TABLE_SIZE);
> max_nr_buckets = max(max_nr_buckets, min_nr_alloc_buckets);
> init_size = min(init_size, max_nr_buckets);
> - ht = calloc(1, sizeof(struct cds_lfht));
> +
> + ht = mm->alloc_cds_lfht(min_nr_alloc_buckets, max_nr_buckets);
> assert(ht);
> + assert(ht->mm == mm);
> + assert(ht->bucket_at == mm->bucket_at);
> +
> ht->flags = flags;
> ht->flavor = flavor;
> ht->resize_attr = attr;
> @@ -1389,9 +1297,6 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> pthread_mutex_init(&ht->resize_mutex, NULL);
> order = get_count_order_ulong(init_size);
> ht->resize_target = 1UL << order;
> - 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;
> cds_lfht_create_bucket(ht, 1UL << order);
> ht->size = 1UL << order;
> return ht;
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index a886b04..926aa14 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -95,6 +95,17 @@ enum {
> CDS_LFHT_ACCOUNTING = (1U << 1),
> };
>
> +struct cds_lfht_mm_type {
> + struct cds_lfht *(*alloc_cds_lfht)(unsigned long min_nr_alloc_buckets,
> + unsigned long max_nr_buckets);
> + 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,
> + unsigned long index);
> +};
> +
> +extern const struct cds_lfht_mm_type cds_lfht_mm_order;
> +
> /*
> * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
> */
> @@ -102,6 +113,7 @@ 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);
>
> @@ -138,7 +150,7 @@ struct cds_lfht *cds_lfht_new(unsigned long init_size,
> pthread_attr_t *attr)
> {
> return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets,
> - flags, &rcu_flavor, attr);
> + flags, &cds_lfht_mm_order, &rcu_flavor, attr);
> }
>
> /*
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
More information about the lttng-dev
mailing list