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 typedef struct private_list {
  31     block_t *head;
  32     uint32_t next_pub;
  33     uint32_t count;
  34 } private_list_t;
  35
  36 static header_t *region_header_ = NULL;
  37
  38 static block_t *pub_free_list_[MAX_NUM_THREADS][MAX_SCALE+1][MAX_NUM_THREADS] = {};
  39 static private_list_t pri_free_list_[MAX_NUM_THREADS][MAX_SCALE+1] = {};
  40
  41 static void *get_new_region (int scale) {
  42     if (scale < REGION_SCALE) {
  43         scale = REGION_SCALE;
  44     }
  45     TRACE("m0", "get_new_region(): mmap new region scale: %llu", scale, 0);
  46     void *region = mmap(NULL, (1 << scale), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
  47     if (region == (void *)-1) {
  48         perror("get_new_region: mmap");
  49         exit(-1);
  50     }
  51     assert(region);
  52     return region;
  53 }
  54
  55 void mem_init (void) {
  56     assert(region_header_ == NULL);
  57     region_header_ = (header_t *)get_new_region(HEADER_REGION_SCALE);
  58     memset(region_header_, 0, REGION_SIZE);
  59 }
  60
  61 // Put <x> onto its owner's public free list (in the appropriate size bin).
  62 //
  63 // TODO: maybe we want to munmap() larger size blocks to reclaim virtual address space?
  64 void nbd_free (void *x) {
  65     assert(x);
  66     LOCALIZE_THREAD_LOCAL(tid_, int);
  67     block_t  *b = (block_t *)x;
  68     assert(((size_t)b >> REGION_SCALE) < ((1 << HEADER_REGION_SCALE) / sizeof(header_t)));
  69     header_t *h = region_header_ + ((size_t)b >> REGION_SCALE);
  70     TRACE("m0", "nbd_free(): block %p scale %llu", b, h->scale);
  71     if (h->owner == tid_) {
  72         TRACE("m0", "nbd_free(): private block, free list head %p",
  73                     h->owner, pri_free_list_[tid_][h->scale].head);
  74         b->next = pri_free_list_[tid_][h->scale].head;
  75         pri_free_list_[tid_][h->scale].head = b;
  76     } else {
  77         TRACE("m0", "nbd_free(): owner %llu free list head %p",
  78                     h->owner, pub_free_list_[h->owner][h->scale][tid_]);
  79         b->next = pub_free_list_[h->owner][h->scale][tid_];
  80         pub_free_list_[h->owner][h->scale][tid_] = b;
  81     }
  82 }
  83
  84 // Allocate a block of memory at least size <n>. Blocks are binned in powers-of-two. Round up
  85 // <n> to the nearest power-of-two.
  86 //
  87 // First check the current thread's private free list for an available block. If no blocks are on
  88 // the private free list, pull blocks off of the current thread's public free lists and put them
  89 // on the private free list. If we didn't find any blocks on the public free lists, allocate a new
  90 // region, break it up into blocks and put them on the private free list.
  91 void *nbd_malloc (size_t n) {
  92     assert(n);
  93     LOCALIZE_THREAD_LOCAL(tid_, int);
  94     if (n < sizeof(block_t)) {
  95         n = sizeof(block_t);
  96     }
  97     int b_scale = GET_SCALE(n);
  98     assert(b_scale <= MAX_SCALE);
  99     TRACE("m0", "nbd_malloc(): size %llu scale %llu", n, b_scale);
 100     private_list_t *pri = &pri_free_list_[tid_][b_scale]; // our private free list
 101     TRACE("m0", "nbd_malloc(): private free list %p first block %p", pri->list, pri->head);
 102
 103     // If our private free list is empty, try to find blocks on our public free list. If that fails,
 104     // allocate a new region.
 105     if (EXPECT_FALSE(pri->head == NULL)) {
 106         block_t **pubs = pub_free_list_[tid_][b_scale]; // our public free lists
 107         while (1) {
 108             // look for blocks on our public free lists round robin
 109             pri->next_pub = (pri->next_pub+1) & (MAX_NUM_THREADS-1);
 110
 111             TRACE("m0", "nbd_malloc(): searching public free list %llu", pri->next_pub, 0);
 112             if (pri->next_pub == tid_) {
 113                 uint32_t count = pri->count;
 114                 pri->count = 0;
 115                 // If our private list is empty and we haven't gotten at least half a region's worth
 116                 // of block's from our public lists, we allocate a new region. This guarentees that
 117                 // we amortize the cost of accessing our public lists accross enough nbd_malloc()
 118                 // calls.
 119                 uint32_t min_count = b_scale > REGION_SCALE ? 1 << (b_scale-REGION_SCALE-1) : 1;
 120                 if (count < min_count) {
 121                     char  *region = get_new_region(b_scale);
 122                     size_t b_size = 1 << b_scale;
 123                     size_t region_size = (b_size < REGION_SIZE) ? REGION_SIZE : b_size;
 124                     for (int i = region_size; i != 0; i -= b_size) {
 125                         block_t *b = (block_t *)(region + i - b_size);
 126                         b->next = pri->head;
 127                         pri->head = b;
 128                     }
 129                     break;
 130                 }
 131                 continue;
 132             }
 133
 134             if (pubs[pri->next_pub] != NULL) {
 135                 block_t *stolen = SYNC_SWAP(&pubs[pri->next_pub], NULL);
 136                 TRACE("m0", "nbd_malloc(): stole list %p first block %p", stolen);
 137                 if (stolen == NULL)
 138                     continue;
 139                 pri->head = stolen;
 140                 break;
 141             }
 142         }
 143         assert(pri->head);
 144     }
 145
 146     // Pull a block off of our private free list.
 147     block_t *b = pri->head;
 148     TRACE("m0", "nbd_malloc(): take block %p off of of private list (new head is %p)", b, pri->next);
 149     assert(b);
 150     pri->head = b->next;
 151     pri->count++;
 152     return b;
 153 }