[lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c memory management

[Lai Jiangshan]

On 11/28/2011 09:43 PM, Mathieu Desnoyers wrote:
> Merged as:
> 
> commit b0b5525153fce8abae07b9573da1d5169e02eb2b
> Author: Lai Jiangshan <laijs at cn.fujitsu.com>
> Date:   Mon Nov 28 08:41:10 2011 -0500
> 
>     add rculfhash-mm-mmap.c memory management
>     
>     [ Edit by Mathieu Desnoyers:
>       - change "buckets" for "mmap" to better show the mapping between the
>         union member and the mm plugin.
>       - 80 col coding style fixups. ]

tbl_order contains pointers of bucket _order_ table
tbl_chunk contains pointers of bucket _chunk_ table
tbl_buckets is a table which contains _buckets_

But here, we focus on memory, so tbl_mmap is also good for me.

Thanks,
Lai

>     
>     Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
>     Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> 
> diff --git a/Makefile.am b/Makefile.am
> index 853ecd5..91a9fd1 100644
> --- a/Makefile.am
> +++ b/Makefile.am
> @@ -35,7 +35,8 @@ if COMPAT_FUTEX
>  COMPAT+=compat_futex.c
>  endif
>  
> -RCULFHASH=rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c
> +RCULFHASH = rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c \
> +		rculfhash-mm-mmap.c
>  
>  lib_LTLIBRARIES = liburcu-common.la \
>  		liburcu.la liburcu-qsbr.la \
> diff --git a/rculfhash-internal.h b/rculfhash-internal.h
> index f7c6590..cc14664 100644
> --- a/rculfhash-internal.h
> +++ b/rculfhash-internal.h
> @@ -108,6 +108,12 @@ struct cds_lfht {
>  		 * memory addressing.
>  		 */
>  		struct cds_lfht_node *tbl_chunk[0];
> +
> +		/*
> +		 * Memory mapping with room for all possible buckets.
> +		 * Their memory is allocated when needed.
> +		 */
> +		struct cds_lfht_node *tbl_mmap;
>  	};
>  };
>  
> diff --git a/rculfhash-mm-mmap.c b/rculfhash-mm-mmap.c
> new file mode 100644
> index 0000000..542c884
> --- /dev/null
> +++ b/rculfhash-mm-mmap.c
> @@ -0,0 +1,160 @@
> +/*
> + * rculfhash-mm-mmap.c
> + *
> + * mmap/reservation based memory management for Lock-Free RCU Hash Table
> + *
> + * 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 <unistd.h>
> +#include <sys/mman.h>
> +#include "rculfhash-internal.h"
> +
> +/* reserve inaccessible memory space without allocation any memory */
> +static void *memory_map(size_t length)
> +{
> +	void *ret = mmap(NULL, length, PROT_NONE,
> +			MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> +
> +	assert(ret != MAP_FAILED);
> +	return ret;
> +}
> +
> +static void memory_unmap(void *ptr, size_t length)
> +{
> +	int ret = munmap(ptr, length);
> +
> +	assert(ret == 0);
> +}
> +
> +static void memory_populate(void *ptr, size_t length)
> +{
> +	void *ret = mmap(ptr, length, PROT_READ | PROT_WRITE,
> +			MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> +
> +	assert(ret == ptr);
> +}
> +
> +/*
> + * Discard garbage memory and avoid system save it when try to swap it out.
> + * Make it still reserved, inaccessible.
> + */
> +static void memory_discard(void *ptr, size_t length)
> +{
> +	void *ret = mmap(ptr, length, PROT_NONE,
> +			MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> +
> +	assert(ret == ptr);
> +}
> +
> +static
> +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));
> +			assert(ht->tbl_mmap);
> +			return;
> +		}
> +		/* large table */
> +		ht->tbl_mmap = memory_map(ht->max_nr_buckets
> +			* sizeof(*ht->tbl_mmap));
> +		memory_populate(ht->tbl_mmap,
> +			ht->min_nr_alloc_buckets * sizeof(*ht->tbl_mmap));
> +	} else if (order > ht->min_alloc_buckets_order) {
> +		/* large table */
> +		unsigned long len = 1UL << (order - 1);
> +
> +		assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
> +		memory_populate(ht->tbl_mmap + len,
> +				len * sizeof(*ht->tbl_mmap));
> +	}
> +	/* 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) {
> +		if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) {
> +			/* small table */
> +			poison_free(ht->tbl_mmap);
> +			return;
> +		}
> +		/* large table */
> +		memory_unmap(ht->tbl_mmap,
> +			ht->max_nr_buckets * sizeof(*ht->tbl_mmap));
> +	} else if (order > ht->min_alloc_buckets_order) {
> +		/* large table */
> +		unsigned long len = 1UL << (order - 1);
> +
> +		assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
> +		memory_discard(ht->tbl_mmap + len, len * sizeof(*ht->tbl_mmap));
> +	}
> +	/* 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)
> +{
> +	return &ht->tbl_mmap[index];
> +}
> +
> +static
> +struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
> +		unsigned long max_nr_buckets)
> +{
> +	struct cds_lfht *ht;
> +	unsigned long page_bucket_size = getpagesize() / sizeof(*ht->tbl_mmap);
> +
> +	if (max_nr_buckets <= page_bucket_size) {
> +		/* small table */
> +		min_nr_alloc_buckets = max_nr_buckets;
> +	} else {
> +		/* large table */
> +		min_nr_alloc_buckets = max(min_nr_alloc_buckets,
> +					page_bucket_size);
> +	}
> +
> +	ht = calloc(1, sizeof(struct cds_lfht));
> +	assert(ht);
> +
> +	ht->mm = &cds_lfht_mm_mmap;
> +
> +	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_mmap = {
> +	.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 1224ea8..6ed7c8c 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -106,6 +106,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;
> +extern const struct cds_lfht_mm_type cds_lfht_mm_mmap;
>  
>  /*
>   * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
>