src/rculfhash-mm-mmap.c

   1 // SPDX-FileCopyrightText: 2011 Lai Jiangshan <laijs@cn.fujitsu.com>
   2 //
   3 // SPDX-License-Identifier: LGPL-2.1-or-later
   4
   5 /*
   6  * mmap/reservation based memory management for Lock-Free RCU Hash Table
   7  */
   8
   9 #include <unistd.h>
  10 #include <stdio.h>
  11 #include <errno.h>
  12 #include <stdlib.h>
  13 #include <sys/mman.h>
  14 #include <urcu/assert.h>
  15 #include "rculfhash-internal.h"
  16
  17 #ifndef MAP_ANONYMOUS
  18 #define MAP_ANONYMOUS           MAP_ANON
  19 #endif
  20
  21 /*
  22  * The allocation scheme used by the mmap based RCU hash table is to make a
  23  * large unaccessible mapping to reserve memory without allocating it.
  24  * Then smaller chunks are allocated by overlapping read/write mappings which
  25  * do allocate memory. Deallocation is done by an overlapping unaccessible
  26  * mapping.
  27  *
  28  * This scheme was tested on Linux, macOS and Solaris. However, on Cygwin the
  29  * mmap wrapper is based on the Windows NtMapViewOfSection API which doesn't
  30  * support overlapping mappings.
  31  *
  32  * An alternative to the overlapping mappings is to use mprotect to change the
  33  * protection on chunks of the large mapping, read/write to allocate and none
  34  * to deallocate. This works perfecty on Cygwin and Solaris but on Linux a
  35  * call to madvise is also required to deallocate and it just doesn't work on
  36  * macOS.
  37  *
  38  * For this reason, we keep to original scheme on all platforms except Cygwin.
  39  */
  40
  41
  42 /* Reserve inaccessible memory space without allocating it */
  43 static
  44 void *memory_map(size_t length)
  45 {
  46         void *ret;
  47
  48         ret = mmap(NULL, length, PROT_NONE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
  49         if (ret == MAP_FAILED) {
  50                 perror("mmap");
  51                 abort();
  52         }
  53         return ret;
  54 }
  55
  56 static
  57 void memory_unmap(void *ptr, size_t length)
  58 {
  59         if (munmap(ptr, length)) {
  60                 perror("munmap");
  61                 abort();
  62         }
  63 }
  64
  65 #ifdef __CYGWIN__
  66 /* Set protection to read/write to allocate a memory chunk */
  67 static
  68 void memory_populate(void *ptr, size_t length)
  69 {
  70         if (mprotect(ptr, length, PROT_READ | PROT_WRITE)) {
  71                 perror("mprotect");
  72                 abort();
  73         }
  74 }
  75
  76 /* Set protection to none to deallocate a memory chunk */
  77 static
  78 void memory_discard(void *ptr, size_t length)
  79 {
  80         if (mprotect(ptr, length, PROT_NONE)) {
  81                 perror("mprotect");
  82                 abort();
  83         }
  84 }
  85
  86 #else /* __CYGWIN__ */
  87
  88 static
  89 void memory_populate(void *ptr, size_t length)
  90 {
  91         if (mmap(ptr, length, PROT_READ | PROT_WRITE,
  92                         MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS,
  93                         -1, 0) != ptr) {
  94                 perror("mmap");
  95                 abort();
  96         }
  97 }
  98
  99 /*
 100  * Discard garbage memory and avoid system save it when try to swap it out.
 101  * Make it still reserved, inaccessible.
 102  */
 103 static
 104 void memory_discard(void *ptr, size_t length)
 105 {
 106         if (mmap(ptr, length, PROT_NONE,
 107                         MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS,
 108                         -1, 0) != ptr) {
 109                 perror("mmap");
 110                 abort();
 111         }
 112 }
 113 #endif /* __CYGWIN__ */
 114
 115 static
 116 void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
 117 {
 118         if (order == 0) {
 119                 if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) {
 120                         /* small table */
 121                         ht->tbl_mmap = ht->alloc->calloc(ht->alloc->state,
 122                                         ht->max_nr_buckets, sizeof(*ht->tbl_mmap));
 123                         urcu_posix_assert(ht->tbl_mmap);
 124                         return;
 125                 }
 126                 /* large table */
 127                 ht->tbl_mmap = memory_map(ht->max_nr_buckets
 128                         * sizeof(*ht->tbl_mmap));
 129                 memory_populate(ht->tbl_mmap,
 130                         ht->min_nr_alloc_buckets * sizeof(*ht->tbl_mmap));
 131         } else if (order > ht->min_alloc_buckets_order) {
 132                 /* large table */
 133                 unsigned long len = 1UL << (order - 1);
 134
 135                 urcu_posix_assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
 136                 memory_populate(ht->tbl_mmap + len,
 137                                 len * sizeof(*ht->tbl_mmap));
 138         }
 139         /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
 140 }
 141
 142 /*
 143  * cds_lfht_free_bucket_table() should be called with decreasing order.
 144  * When cds_lfht_free_bucket_table(0) is called, it means the whole
 145  * lfht is destroyed.
 146  */
 147 static
 148 void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
 149 {
 150         if (order == 0) {
 151                 if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) {
 152                         /* small table */
 153                         poison_free(ht->alloc, ht->tbl_mmap);
 154                         return;
 155                 }
 156                 /* large table */
 157                 memory_unmap(ht->tbl_mmap,
 158                         ht->max_nr_buckets * sizeof(*ht->tbl_mmap));
 159         } else if (order > ht->min_alloc_buckets_order) {
 160                 /* large table */
 161                 unsigned long len = 1UL << (order - 1);
 162
 163                 urcu_posix_assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
 164                 memory_discard(ht->tbl_mmap + len, len * sizeof(*ht->tbl_mmap));
 165         }
 166         /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
 167 }
 168
 169 static
 170 struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
 171 {
 172         return &ht->tbl_mmap[index];
 173 }
 174
 175 static
 176 struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
 177                 unsigned long max_nr_buckets, const struct cds_lfht_alloc *alloc)
 178 {
 179         unsigned long page_bucket_size;
 180
 181         page_bucket_size = getpagesize() / sizeof(struct cds_lfht_node);
 182         if (max_nr_buckets <= page_bucket_size) {
 183                 /* small table */
 184                 min_nr_alloc_buckets = max_nr_buckets;
 185         } else {
 186                 /* large table */
 187                 min_nr_alloc_buckets = max(min_nr_alloc_buckets,
 188                                         page_bucket_size);
 189         }
 190
 191         return __default_alloc_cds_lfht(
 192                         &cds_lfht_mm_mmap, alloc, sizeof(struct cds_lfht),
 193                         min_nr_alloc_buckets, max_nr_buckets);
 194 }
 195
 196 const struct cds_lfht_mm_type cds_lfht_mm_mmap = {
 197         .alloc_cds_lfht = alloc_cds_lfht,
 198         .alloc_bucket_table = cds_lfht_alloc_bucket_table,
 199         .free_bucket_table = cds_lfht_free_bucket_table,
 200         .bucket_at = bucket_at,
 201 };