[lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c memory management
Mathieu Desnoyers
mathieu.desnoyers at efficios.com
Mon Nov 28 09:15:41 EST 2011
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> 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.
I agree that "buckets" was also correct, but my primary intent here is
to show the mapping between the union entries and the individual memory
management plugins, which I think is better conveyed by "mmap" than
"buckets". I think it is also good that the field name reflects that
this points to a memory mapping that is not entirely populated rather
than to buckets, because "buckets" could mean those are all
pre-allocated (from the point of view of someone who reviews the code).
Using "mmap" for the mmap-plugin field leaves room, for instance, for a
new mm plugin called "bucket", which would pre-populate all memory for
all buckets. This could be useful for tables with maximum fixed-size
number of buckets.
By the way, I just pushed a few cleanup updates of my own into the tree.
Thanks!
Mathieu
>
> 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.
> >
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
More information about the lttng-dev
mailing list