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. 64 bit platforms only!
   6  */
   7 #include <sys/mman.h>
   8 #include <stdio.h>
   9 #include <errno.h>
  10 #include "common.h"
  11 #include "runtime_local.h"
  12 #include "lwt.h"
  13
  14 #define GET_SCALE(n) (sizeof(n)*8-__builtin_clzl((n)-1)) // log2 of <n>, rounded up
  15 #define MAX_SCALE 31 // allocate blocks up to 4GB in size (arbitrary, could be bigger)
  16 #define REGION_SCALE 22 // 4MB regions
  17 #define REGION_SIZE (1 << REGION_SCALE)
  18 #define HEADER_REGION_SCALE 22 // 4MB is space enough for headers for over 2,000,000 regions
  19
  20 typedef struct block {
  21     struct block *next;
  22 } block_t;
  23
  24 // region header
  25 typedef struct header {
  26     uint8_t owner; // thread id of owner
  27     uint8_t scale; // log2 of the block size
  28 } header_t;
  29
  30 static header_t *region_header_ = NULL;
  31
  32 // TODO: experiment with different memory layouts (i.e. separate private and public lists)
  33 static block_t free_list_[MAX_NUM_THREADS][MAX_SCALE+1][MAX_NUM_THREADS];
  34
  35 static void *get_new_region (int scale) {
  36     if (scale < REGION_SCALE) {
  37         scale = REGION_SCALE;
  38     }
  39     TRACE("m0", "get_new_region(): mmap new region scale: %llu", scale, 0);
  40     void *region = mmap(NULL, (1 << scale), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
  41     if (region == (void *)-1) {
  42         perror("get_new_region: mmap");
  43         exit(-1);
  44     }
  45     assert(region);
  46     return region;
  47 }
  48
  49 void mem_init (void) {
  50     assert(region_header_ == NULL);
  51     region_header_ = (header_t *)get_new_region(HEADER_REGION_SCALE);
  52     memset(region_header_, 0, REGION_SIZE);
  53 }
  54
  55 // Put <x> onto its owner's public free list (in the appropriate size bin).
  56 //
  57 // TODO: maybe we want to munmap() larger size blocks to reclaim virtual address space?
  58 void nbd_free (void *x) {
  59     LOCALIZE_THREAD_LOCAL(tid_, int);
  60     block_t  *b = (block_t *)x;
  61     assert(((size_t)b >> REGION_SCALE) < ((1 << HEADER_REGION_SCALE) / sizeof(header_t)));
  62     header_t *h = region_header_ + ((size_t)b >> REGION_SCALE);
  63     TRACE("m0", "nbd_free(): block %p scale %llu", x, h->scale);
  64     block_t  *l = &free_list_[h->owner][h->scale][tid_];
  65     TRACE("m0", "nbd_free(): free list %p first block %p", l, l->next);
  66     b->next = l->next;
  67     l->next = b;
  68 }
  69
  70 // Allocate a block of memory at least size <n>. Blocks are binned in powers-of-two. Round up
  71 // <n> to the nearest power-of-two.
  72 //
  73 // First check the current thread's private free list for an available block. If no blocks are on
  74 // the private free list, pull all the available blocks off of the current thread's public free
  75 // lists and put them on the private free list. If we didn't find any blocks on the public free
  76 // lists, open a new region, break it up into blocks and put them on the private free list.
  77 void *nbd_malloc (size_t n) {
  78     LOCALIZE_THREAD_LOCAL(tid_, int);
  79     if (n < sizeof(block_t)) {
  80         n = sizeof(block_t);
  81     }
  82     int b_scale = GET_SCALE(n);
  83     assert(b_scale <= MAX_SCALE);
  84     TRACE("m0", "nbd_malloc(): size %llu scale %llu", n, b_scale);
  85     block_t *fls = free_list_[tid_][b_scale]; // our free lists
  86     block_t *pri = fls + tid_; // our private free list
  87     TRACE("m0", "nbd_malloc(): private free list %p first block %p", pri, pri->next);
  88
  89     // If our private free list is empty, fill it up with blocks from our public free lists
  90     if (EXPECT_FALSE(pri->next == NULL)) {
  91         int cnt = 0;
  92         block_t *last = pri;
  93         for (int i = 0; i < MAX_NUM_THREADS; ++i) {
  94             TRACE("m0", "nbd_malloc(): searching public free lists (%llu)", i, 0);
  95             block_t *pub = fls + i; // one of our public free lists
  96             TRACE("m0", "nbd_malloc(): public free list %p first block %p", pub, pub->next);
  97             if (EXPECT_FALSE(pub == pri))
  98                 continue;
  99
 100             if (pub->next != NULL) {
 101                 block_t *stolen = SYNC_SWAP(&pub->next, NULL);
 102                 TRACE("m0", "nbd_malloc(): stole list %p first block %p", pub, stolen);
 103                 if (stolen) {
 104                     last->next = stolen;
 105                     TRACE("m0", "nbd_malloc(): append to last block %p of private free list", last, 0);
 106                     while (last->next) {
 107                         ++cnt;
 108                         TRACE("m0", "nbd_malloc(): find last block in list: last %p last->next %p",
 109                               last, last->next);
 110                         last = last->next;
 111                     }
 112                 }
 113             }
 114         }
 115         TRACE("m0", "nbd_malloc(): moved %llu blocks from public to private free lists", cnt, 0);
 116
 117         if (b_scale >= REGION_SCALE) {
 118             if (cnt == 0) {
 119                 assert(pri->next == NULL);
 120                 pri->next = (block_t *)get_new_region(b_scale);
 121                 assert(pri->next->next == NULL);
 122             }
 123             assert(pri->next);
 124
 125         } else if (cnt < (1 << (REGION_SCALE - b_scale - 1))) {
 126
 127             // Even if we took a few blocks from our public lists we still break open a new region.
 128             // This guarentees that we are amortizing the cost of accessing our public lists accross
 129             // many nbd_malloc() calls.
 130             char *region = get_new_region(b_scale);
 131             size_t b_size = 1 << b_scale;
 132             for (int i = REGION_SIZE; i != 0; i -= b_size) {
 133                 block_t *b = (block_t *)(region + i - b_size);
 134                 b->next = pri->next;
 135                 //TRACE("m1", "nbd_malloc(): put new block %p ahead of %p on private list", b, b->next);
 136                 pri->next = b;
 137                 *b = *b;
 138             }
 139         }
 140
 141         assert(pri->next);
 142     }
 143
 144     // Pull a block off of our private free list.
 145     block_t *b = pri->next;
 146     TRACE("m0", "nbd_malloc(): take block %p off of of private list (new head is %p)", b, pri->next);
 147     pri->next = b->next;
 148
 149     assert(b);
 150     return b;
 151 }