From mboxrd@z Thu Jan 1 00:00:00 1970 From: mathieu.desnoyers@efficios.com (Mathieu Desnoyers) Date: Mon, 28 Nov 2011 09:15:41 -0500 Subject: [lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c memory management In-Reply-To: <4ED39546.6040802@cn.fujitsu.com> References: <1322467688-2930-1-git-send-email-laijs@cn.fujitsu.com> <1322467688-2930-13-git-send-email-laijs@cn.fujitsu.com> <20111128134318.GL2663@Krystal> <4ED39546.6040802@cn.fujitsu.com> Message-ID: <20111128141541.GA15616@Krystal> * 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 > > 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 > > Signed-off-by: Mathieu Desnoyers > > > > 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 > > + * > > + * 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 > > +#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