4 * mmap/reservation based memory management for Lock-Free RCU Hash Table
6 * Copyright 2011 - Lai Jiangshan <laijs@cn.fujitsu.com>
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
28 #include <urcu/assert.h>
29 #include "rculfhash-internal.h"
32 #define MAP_ANONYMOUS MAP_ANON
36 * The allocation scheme used by the mmap based RCU hash table is to make a
37 * large unaccessible mapping to reserve memory without allocating it.
38 * Then smaller chunks are allocated by overlapping read/write mappings which
39 * do allocate memory. Deallocation is done by an overlapping unaccessible
42 * This scheme was tested on Linux, macOS and Solaris. However, on Cygwin the
43 * mmap wrapper is based on the Windows NtMapViewOfSection API which doesn't
44 * support overlapping mappings.
46 * An alternative to the overlapping mappings is to use mprotect to change the
47 * protection on chunks of the large mapping, read/write to allocate and none
48 * to deallocate. This works perfecty on Cygwin and Solaris but on Linux a
49 * call to madvise is also required to deallocate and it just doesn't work on
52 * For this reason, we keep to original scheme on all platforms except Cygwin.
56 /* Reserve inaccessible memory space without allocating it */
58 void *memory_map(size_t length
)
62 ret
= mmap(NULL
, length
, PROT_NONE
, MAP_PRIVATE
| MAP_ANONYMOUS
, -1, 0);
63 if (ret
== MAP_FAILED
) {
71 void memory_unmap(void *ptr
, size_t length
)
73 if (munmap(ptr
, length
)) {
80 /* Set protection to read/write to allocate a memory chunk */
82 void memory_populate(void *ptr
, size_t length
)
84 if (mprotect(ptr
, length
, PROT_READ
| PROT_WRITE
)) {
90 /* Set protection to none to deallocate a memory chunk */
92 void memory_discard(void *ptr
, size_t length
)
94 if (mprotect(ptr
, length
, PROT_NONE
)) {
100 #else /* __CYGWIN__ */
103 void memory_populate(void *ptr
, size_t length
)
105 if (mmap(ptr
, length
, PROT_READ
| PROT_WRITE
,
106 MAP_FIXED
| MAP_PRIVATE
| MAP_ANONYMOUS
,
114 * Discard garbage memory and avoid system save it when try to swap it out.
115 * Make it still reserved, inaccessible.
118 void memory_discard(void *ptr
, size_t length
)
120 if (mmap(ptr
, length
, PROT_NONE
,
121 MAP_FIXED
| MAP_PRIVATE
| MAP_ANONYMOUS
,
127 #endif /* __CYGWIN__ */
130 void cds_lfht_alloc_bucket_table(struct cds_lfht
*ht
, unsigned long order
)
133 if (ht
->min_nr_alloc_buckets
== ht
->max_nr_buckets
) {
135 ht
->tbl_mmap
= calloc(ht
->max_nr_buckets
,
136 sizeof(*ht
->tbl_mmap
));
137 urcu_posix_assert(ht
->tbl_mmap
);
141 ht
->tbl_mmap
= memory_map(ht
->max_nr_buckets
142 * sizeof(*ht
->tbl_mmap
));
143 memory_populate(ht
->tbl_mmap
,
144 ht
->min_nr_alloc_buckets
* sizeof(*ht
->tbl_mmap
));
145 } else if (order
> ht
->min_alloc_buckets_order
) {
147 unsigned long len
= 1UL << (order
- 1);
149 urcu_posix_assert(ht
->min_nr_alloc_buckets
< ht
->max_nr_buckets
);
150 memory_populate(ht
->tbl_mmap
+ len
,
151 len
* sizeof(*ht
->tbl_mmap
));
153 /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
157 * cds_lfht_free_bucket_table() should be called with decreasing order.
158 * When cds_lfht_free_bucket_table(0) is called, it means the whole
162 void cds_lfht_free_bucket_table(struct cds_lfht
*ht
, unsigned long order
)
165 if (ht
->min_nr_alloc_buckets
== ht
->max_nr_buckets
) {
167 poison_free(ht
->tbl_mmap
);
171 memory_unmap(ht
->tbl_mmap
,
172 ht
->max_nr_buckets
* sizeof(*ht
->tbl_mmap
));
173 } else if (order
> ht
->min_alloc_buckets_order
) {
175 unsigned long len
= 1UL << (order
- 1);
177 urcu_posix_assert(ht
->min_nr_alloc_buckets
< ht
->max_nr_buckets
);
178 memory_discard(ht
->tbl_mmap
+ len
, len
* sizeof(*ht
->tbl_mmap
));
180 /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
184 struct cds_lfht_node
*bucket_at(struct cds_lfht
*ht
, unsigned long index
)
186 return &ht
->tbl_mmap
[index
];
190 struct cds_lfht
*alloc_cds_lfht(unsigned long min_nr_alloc_buckets
,
191 unsigned long max_nr_buckets
)
193 unsigned long page_bucket_size
;
195 page_bucket_size
= getpagesize() / sizeof(struct cds_lfht_node
);
196 if (max_nr_buckets
<= page_bucket_size
) {
198 min_nr_alloc_buckets
= max_nr_buckets
;
201 min_nr_alloc_buckets
= max(min_nr_alloc_buckets
,
205 return __default_alloc_cds_lfht(
206 &cds_lfht_mm_mmap
, sizeof(struct cds_lfht
),
207 min_nr_alloc_buckets
, max_nr_buckets
);
210 const struct cds_lfht_mm_type cds_lfht_mm_mmap
= {
211 .alloc_cds_lfht
= alloc_cds_lfht
,
212 .alloc_bucket_table
= cds_lfht_alloc_bucket_table
,
213 .free_bucket_table
= cds_lfht_free_bucket_table
,
214 .bucket_at
= bucket_at
,