pd.if.org Git - nbds/blob - runtime/mem.c

   1 /*
   2  * Written by Josh Dybnis and released to the public domain, as explained at
   3  * http://creativecommons.org/licenses/publicdomain
   4  *
   5  * Extreamly fast multi-threaded malloc.
   6  */
   7 #ifndef USE_SYSTEM_MALLOC
   8 #define _BSD_SOURCE // so we get MAP_ANON on linux
   9 #include <stdlib.h>
  10 #include <stdio.h>
  11 #include <errno.h>
  12 #include <sys/mman.h>
  13 #include "common.h"
  14 #include "rlocal.h"
  15 #include "lwt.h"
  16
  17 #ifndef NBD32
  18 #define MAX_SCALE        36 // allocate blocks up to 64GB (arbitrary, could be bigger)
  19 #define MIN_SCALE         3 // smallest allocated block is 8 bytes
  20 #define MAX_POINTER_BITS 48
  21 #define PAGE_SCALE       21 // 2MB pages
  22 #else
  23 #define MAX_SCALE        31
  24 #define MIN_SCALE         2 // smallest allocated block is 4 bytes
  25 #define MAX_POINTER_BITS 32
  26 #define PAGE_SCALE       12 // 4KB pages
  27 #endif
  28 #define PAGE_SIZE        (1ULL << PAGE_SCALE)
  29 #define HEADERS_SIZE     (((size_t)1ULL << (MAX_POINTER_BITS - PAGE_SCALE)) * sizeof(header_t))
  30
  31 typedef struct block {
  32     struct block *next;
  33 } block_t;
  34
  35 // TODO: Break the page header into two parts. The first part is located in the header region. The
  36 //       second part is located on the page and is only used when there are free items.
  37 typedef struct header {
  38 #ifdef  RECYCLE_PAGES
  39     struct header *next;
  40     struct header *prev;
  41     block_t *free_list; // list of free blocks
  42     int num_in_use;
  43 #endif//RECYCLE_PAGES
  44     uint8_t owner; // thread id of owner
  45     uint8_t scale; // log2 of the block size
  46 } header_t;
  47
  48 #ifdef RECYCLE_PAGES
  49 typedef struct size_class {
  50     header_t *active_page;
  51     header_t *oldest_partial;
  52     header_t *newest_partial;
  53 } size_class_t;
  54 #endif//RECYCLE_PAGES
  55
  56 typedef struct tl {
  57 #ifndef RECYCLE_PAGES
  58     block_t *free_list[MAX_SCALE+1];
  59 #else
  60     header_t *free_pages;
  61     size_class_t size_class[MAX_SCALE+1];
  62 #endif//RECYCLE_PAGES
  63     block_t *blocks_from[MAX_NUM_THREADS];
  64     block_t *blocks_to[MAX_NUM_THREADS];
  65 } __attribute__((aligned(CACHE_LINE_SIZE))) tl_t;
  66
  67 static header_t *headers_ = NULL;
  68
  69 static tl_t tl_[MAX_NUM_THREADS] = {};
  70
  71 static inline header_t *get_header (void *r) {
  72     ASSERT(((size_t)r >> PAGE_SCALE) < HEADERS_SIZE);
  73     return headers_ + ((size_t)r >> PAGE_SCALE);
  74 }
  75
  76 static void *get_new_region (int block_scale) {
  77     int thread_index = GET_THREAD_INDEX();
  78 #ifdef RECYCLE_PAGES
  79     tl_t *tl = &tl_[thread_index]; // thread-local data
  80     if (block_scale <= PAGE_SCALE && tl->free_pages != NULL) {
  81         void *region = tl->free_pages;
  82         tl->free_pages = tl->free_pages->next;
  83         get_header(region)->scale = block_scale;
  84         return region;
  85     }
  86 #endif//RECYCLE_PAGES
  87     size_t region_size = (1ULL << block_scale);
  88     if (region_size < PAGE_SIZE) {
  89         region_size = PAGE_SIZE;
  90     }
  91     void *region = mmap(NULL, region_size, PROT_READ|PROT_WRITE, MAP_NORESERVE|MAP_ANON|MAP_PRIVATE, -1, 0);
  92     TRACE("m1", "get_new_region: mmapped new region %p (size %p)", region, region_size);
  93     if (region == (void *)-1) {
  94         perror("get_new_region: mmap");
  95         exit(-1);
  96     }
  97     if ((size_t)region & (region_size - 1)) {
  98         TRACE("m0", "get_new_region: region not aligned", 0, 0);
  99         munmap(region, region_size);
 100         region = mmap(NULL, region_size * 2, PROT_READ|PROT_WRITE, MAP_NORESERVE|MAP_ANON|MAP_PRIVATE, -1, 0);
 101         if (region == (void *)-1) {
 102             perror("get_new_region: mmap");
 103             exit(-1);
 104         }
 105         TRACE("m0", "get_new_region: mmapped new region %p (size %p)", region, region_size * 2);
 106         void *aligned = (void *)(((size_t)region + region_size) & ~(region_size - 1));
 107         size_t extra = (char *)aligned - (char *)region;
 108         if (extra) {
 109             munmap(region, extra);
 110             TRACE("m0", "get_new_region: unmapped extra memory %p (size %p)", region, extra);
 111         }
 112         extra = ((char *)region + region_size) - (char *)aligned;
 113         if (extra) {
 114             munmap((char *)aligned + region_size, extra);
 115             TRACE("m0", "get_new_region: unmapped extra memory %p (size %p)", (char *)aligned + region_size, extra);
 116         }
 117         region = aligned;
 118     }
 119     assert(region);
 120
 121     header_t *h = get_header(region);
 122     TRACE("m1", "get_new_region: header %p (%p)", h, h - headers_);
 123     assert(h->scale == 0);
 124     h->scale = block_scale;
 125     h->owner = thread_index;
 126
 127     return region;
 128 }
 129
 130 void mem_init (void) {
 131     assert(headers_ == NULL);
 132     // Allocate space for the page headers. This could be a big chunk of memory on 64 bit systems,
 133     // but it just takes up virtual address space. Physical space used by the headers is still
 134     // proportional to the amount of memory the user mallocs.
 135     headers_ = mmap(NULL, HEADERS_SIZE, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
 136     TRACE("m1", "mem_init: header page %p", headers_, 0);
 137
 138     // initialize spsc queues
 139     for (int i = 0; i < MAX_NUM_THREADS; ++i) {
 140         for (int j = 0; j < MAX_NUM_THREADS; ++j) {
 141             if (i != j) {
 142                 tl_[i].blocks_to[j] = (block_t *)&(tl_[j].blocks_from[i]);
 143             }
 144         }
 145     }
 146 }
 147
 148 void nbd_free (void *x) {
 149     TRACE("m1", "nbd_free: block %p page %p", x, (size_t)x & ~MASK(PAGE_SCALE));
 150     ASSERT(x);
 151     block_t  *b = (block_t *)x;
 152     header_t *h = get_header(x);
 153     int b_scale = h->scale;
 154     TRACE("m1", "nbd_free: header %p scale %llu", h, b_scale);
 155     ASSERT(b_scale && b_scale <= MAX_SCALE);
 156 #ifdef RECYCLE_PAGES
 157     if (b_scale > PAGE_SCALE) {
 158         int rc = munmap(x, 1ULL << b_scale);
 159         ASSERT(rc == 0);
 160         rc = rc;
 161     }
 162 #endif
 163 #ifndef NDEBUG
 164     memset(b, 0xcd, (1ULL << b_scale)); // bear trap
 165 #endif
 166     int thread_index = GET_THREAD_INDEX();
 167     tl_t *tl = &tl_[thread_index]; // thread-local data
 168     if (h->owner == thread_index) {
 169         TRACE("m1", "nbd_free: private block, old free list head %p", tl->free_list[b_scale], 0);
 170
 171 #ifndef RECYCLE_PAGES
 172         b->next = tl->free_list[b_scale];
 173         tl->free_list[b_scale] = b;
 174 #else //RECYCLE_PAGES
 175         b->next = h->free_list;
 176         h->free_list = b;
 177         h->num_in_use--;
 178         size_class_t *sc = &tl->size_class[b_scale];
 179         if (sc->active_page != h) {
 180             if (h->num_in_use == 0) {
 181                 // remove <h> from the partial-page list
 182                 if (h->next != NULL) { h->next->prev = h->prev; }
 183                 if (h->prev != NULL) { h->prev->next = h->next; }
 184                 // put <h> on the free-page list
 185                 h->next = tl->free_pages;
 186                 tl->free_pages = h;
 187             } else {
 188                 // move <h> to the top of the partial-page list
 189                 if (h->next != NULL) {
 190                     h->next->prev = h->prev;
 191                     if (h->prev != NULL) { h->prev->next = h->next; }
 192                     h->prev = sc->newest_partial;
 193                     h->next = NULL;
 194                     sc->newest_partial = h;
 195                 }
 196             }
 197         }
 198 #endif//RECYCLE_PAGES
 199     } else {
 200         // push <b> onto it's owner's queue
 201         int b_owner = h->owner;
 202         TRACE("m1", "nbd_free: owner %llu", b_owner, 0);
 203
 204         // The assignment statements are volatile to prevent the compiler from reordering them.
 205         VOLATILE_DEREF(b).next = NULL;
 206         VOLATILE_DEREF(tl->blocks_to[b_owner]).next = b;
 207
 208         tl->blocks_to[b_owner] = b;
 209     }
 210 }
 211
 212 static inline void process_incoming_blocks (tl_t *tl) {
 213     for (int p = 0; p < MAX_NUM_THREADS; ++p) {
 214         block_t *b = tl->blocks_from[p];
 215         if (EXPECT_FALSE(b == NULL)) continue; // the queue is completely empty
 216
 217         // Leave the last block on the queue. Removing the last block on the queue would create a
 218         // race with the producer thread putting a new block on the queue.
 219         for (block_t *next = b->next; next != NULL; b = next, next = b->next) {
 220             // push <b> onto the appropriate free list
 221 #ifndef RECYCLE_PAGES
 222             int b_scale = get_header(b)->scale;
 223             b->next = tl->free_list[b_scale];
 224             tl->free_list[b_scale] = b;
 225 #else //RECYCLE_PAGES
 226             header_t *h = get_header(b);
 227             b->next = h->free_list;
 228             h->free_list = b;
 229 #endif//RECYCLE_PAGES
 230         }
 231         tl->blocks_from[p] = b;
 232     }
 233 }
 234
 235 static inline block_t *pop_free_list (tl_t *tl, int scale) {
 236 #ifndef RECYCLE_PAGES
 237     block_t **free_list = &tl->free_list[scale];
 238 #else //RECYCLE_PAGES
 239     size_class_t *sc = &tl->size_class[scale];
 240     if (EXPECT_FALSE(sc->active_page == NULL))
 241         return NULL;
 242     block_t **free_list = &sc->active_page->free_list;
 243 #endif//RECYCLE_PAGES
 244     block_t *b = *free_list;
 245     if (EXPECT_FALSE(b == NULL))
 246         return NULL;
 247     ASSERT(get_header(b)->scale == scale);
 248     *free_list = b->next;
 249     return b;
 250 }
 251
 252 // Allocate a block of memory at least size <n>. Blocks are binned in powers-of-two. Round up <n> to
 253 // the nearest power of two.
 254 //
 255 // First check the current thread's free list for an available block. If there are no blocks on the
 256 // free list, pull items off of the current thread's incoming block queues and push them onto the
 257 // free list. If we didn't get an appropriate size block off of the block queues then allocate a new
 258 // page, break it up into blocks and push them onto the free list.
 259 void *nbd_malloc (size_t n) {
 260     // the scale is the log base 2 of <n>, rounded up
 261     int b_scale = (sizeof(void *) * __CHAR_BIT__) - __builtin_clzl((n) - 1);
 262     TRACE("m1", "nbd_malloc: size %llu (scale %llu)", n, b_scale);
 263
 264     if (EXPECT_FALSE(b_scale < MIN_SCALE)) { b_scale = MIN_SCALE; }
 265     if (EXPECT_FALSE(b_scale > MAX_SCALE)) { return NULL; }
 266
 267     tl_t *tl = &tl_[GET_THREAD_INDEX()]; // thread-local data
 268
 269     block_t *b = pop_free_list(tl, b_scale);
 270     if (b != NULL) {
 271         TRACE("m1", "nbd_malloc: returning block %p", b, 0);
 272         return b;
 273     assert(b);
 274     }
 275
 276     // The free list is empty so process blocks freed from other threads and then check again.
 277     process_incoming_blocks(tl);
 278     b = pop_free_list(tl, b_scale);
 279     if (b != NULL) {
 280         TRACE("m1", "nbd_malloc: returning block %p", b, 0);
 281         return b;
 282     assert(b);
 283     }
 284
 285 #ifdef  RECYCLE_PAGES
 286     // The current active page is completely allocated. Make the oldest partially allocated page
 287     // the new active page.
 288     size_class_t *sc = &tl->size_class[b_scale];
 289     if (sc->oldest_partial != NULL) {
 290         sc->active_page = sc->oldest_partial;
 291         sc->oldest_partial = sc->oldest_partial->next;
 292         sc->oldest_partial->prev = NULL;
 293         b = pop_free_list(tl, b_scale);
 294         ASSERT(b != NULL);
 295         TRACE("m1", "nbd_malloc: returning block %p", b, 0);
 296         return b;
 297     assert(b);
 298     }
 299     // There are no partially allocated pages so get a new page.
 300
 301 #endif//RECYCLE_PAGES
 302
 303     // Get a new page.
 304     char *page = get_new_region(b_scale);
 305     b = (block_t *)page; // grab the first block on the page
 306
 307     // Break up the remainder of the page into blocks and put them on the free list. Start at the
 308     // end of the page so that the free list ends up in increasing order, for ease of debugging.
 309     if (b_scale < PAGE_SCALE) {
 310         size_t block_size = (1ULL << b_scale);
 311         block_t *head = NULL;
 312         for (int offset = PAGE_SIZE - block_size; offset > 0; offset -= block_size) {
 313             block_t *x = (block_t *)(page + offset);
 314             x->next = head; head = x;
 315         }
 316 #ifndef RECYCLE_PAGES
 317         tl->free_list[b_scale] = head;
 318 #else //RECYCLE_PAGES
 319         sc->active_page = get_header(page);
 320         sc->active_page->free_list = head;
 321 #endif//RECYCLE_PAGES
 322     }
 323
 324     TRACE("m1", "nbd_malloc: returning block %p from new region %p", b, (size_t)b & ~MASK(PAGE_SCALE));
 325     assert(b);
 326     return b;
 327 }
 328 #else//USE_SYSTEM_MALLOC
 329 #include <stdlib.h>
 330 #include "common.h"
 331 #include "rlocal.h"
 332 #include "lwt.h"
 333
 334 void mem_init (void) {
 335     return;
 336 }
 337
 338 void nbd_free (void *x) {
 339     TRACE("m1", "nbd_free: %p", x, 0);
 340 #ifndef NDEBUG
 341     memset(x, 0xcd, sizeof(void *)); // bear trap
 342 #endif//NDEBUG
 343     free(x);
 344     return;
 345 }
 346
 347 void *nbd_malloc (size_t n) {
 348     TRACE("m1", "nbd_malloc: request size %llu", n, 0);
 349     void *x = malloc(n);
 350     TRACE("m1", "nbd_malloc: returning %p", x, 0);
 351     return x;
 352 }
 353 #endif//USE_SYSTEM_MALLOC