2 * Written by Josh Dybnis and released to the public domain, as explained at
3 * http://creativecommons.org/licenses/publicdomain
5 * Extreamly fast multi-threaded malloc. 64 bit platforms only!
7 #define _BSD_SOURCE // so we get MAP_ANON on linux
15 #define GET_SCALE(n) (sizeof(void *)*__CHAR_BIT__ - __builtin_clzl((n) - 1)) // log2 of <n>, rounded up
16 #define MAX_SCALE 31 // allocate blocks up to 4GB in size (arbitrary, could be bigger)
17 #define REGION_SCALE 22 // 4MB regions
18 #define REGION_SIZE (1 << REGION_SCALE)
19 #define HEADER_REGION_SCALE 22 // 4MB is space enough for headers for over 2,000,000 regions
21 typedef struct block {
26 typedef struct header {
27 uint8_t owner; // thread id of owner
28 uint8_t scale; // log2 of the block size
31 typedef struct private_list {
37 static header_t *region_header_ = NULL;
39 static block_t *pub_free_list_[MAX_NUM_THREADS][MAX_SCALE+1][MAX_NUM_THREADS] = {};
40 static private_list_t pri_free_list_[MAX_NUM_THREADS][MAX_SCALE+1] = {};
42 static void *get_new_region (int scale) {
43 if (scale < REGION_SCALE) {
46 TRACE("m0", "get_new_region(): mmap new region scale: %llu", scale, 0);
47 void *region = mmap(NULL, (1 << scale), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
48 if (region == (void *)-1) {
49 perror("get_new_region: mmap");
56 void mem_init (void) {
57 assert(region_header_ == NULL);
58 region_header_ = (header_t *)get_new_region(HEADER_REGION_SCALE);
59 memset(region_header_, 0, REGION_SIZE);
62 // Put <x> onto its owner's public free list (in the appropriate size bin).
64 // TODO: maybe we want to munmap() larger size blocks to reclaim virtual address space?
65 void nbd_free (void *x) {
67 LOCALIZE_THREAD_LOCAL(tid_, int);
68 block_t *b = (block_t *)x;
69 assert(((size_t)b >> REGION_SCALE) < ((1 << HEADER_REGION_SCALE) / sizeof(header_t)));
70 header_t *h = region_header_ + ((size_t)b >> REGION_SCALE);
72 memset(b, 0xcd, (1 << h->scale));
74 TRACE("m0", "nbd_free(): block %p scale %llu", b, h->scale);
75 if (h->owner == tid_) {
76 TRACE("m0", "nbd_free(): private block, free list head %p",
77 h->owner, pri_free_list_[tid_][h->scale].head);
78 b->next = pri_free_list_[tid_][h->scale].head;
79 pri_free_list_[tid_][h->scale].head = b;
81 TRACE("m0", "nbd_free(): owner %llu free list head %p",
82 h->owner, pub_free_list_[h->owner][h->scale][tid_]);
84 b->next = pub_free_list_[h->owner][h->scale][tid_];
85 } while (SYNC_CAS(&pub_free_list_[h->owner][h->scale][tid_], b->next, b) != b->next);
89 // Allocate a block of memory at least size <n>. Blocks are binned in powers-of-two. Round up
90 // <n> to the nearest power-of-two.
92 // First check the current thread's private free list for an available block. If no blocks are on
93 // the private free list, pull blocks off of the current thread's public free lists and put them
94 // on the private free list. If we didn't find any blocks on the public free lists, allocate a new
95 // region, break it up into blocks and put them on the private free list.
96 void *nbd_malloc (size_t n) {
98 LOCALIZE_THREAD_LOCAL(tid_, int);
99 if (n < sizeof(block_t)) {
102 int b_scale = GET_SCALE(n);
103 assert(b_scale <= MAX_SCALE);
104 TRACE("m0", "nbd_malloc(): size %llu scale %llu", n, b_scale);
105 private_list_t *pri = &pri_free_list_[tid_][b_scale]; // our private free list
106 TRACE("m0", "nbd_malloc(): private free list first block %p", pri->head, 0);
108 // If our private free list is empty, try to find blocks on our public free list. If that fails,
109 // allocate a new region.
110 if (EXPECT_FALSE(pri->head == NULL)) {
111 block_t **pubs = pub_free_list_[tid_][b_scale]; // our public free lists
113 // look for blocks on our public free lists round robin
114 pri->next_pub = (pri->next_pub+1) & (MAX_NUM_THREADS-1);
116 TRACE("m0", "nbd_malloc(): searching public free list %llu", pri->next_pub, 0);
117 if (pri->next_pub == tid_) {
118 uint32_t count = pri->count;
120 // If our private list is empty and we haven't gotten at least half a region's worth
121 // of block's from our public lists, we allocate a new region. This guarentees that
122 // we amortize the cost of accessing our public lists accross enough nbd_malloc()
124 uint32_t min_count = b_scale > REGION_SCALE ? 1 << (b_scale-REGION_SCALE-1) : 1;
125 if (count < min_count) {
126 char *region = get_new_region(b_scale);
127 size_t b_size = 1 << b_scale;
128 size_t region_size = (b_size < REGION_SIZE) ? REGION_SIZE : b_size;
129 for (int i = region_size; i != 0; i -= b_size) {
130 block_t *b = (block_t *)(region + i - b_size);
139 if (pubs[pri->next_pub] != NULL) {
140 block_t *stolen = SYNC_SWAP(&pubs[pri->next_pub], NULL);
141 TRACE("m0", "nbd_malloc(): stole list %p", stolen, 0);
151 // Pull a block off of our private free list.
152 block_t *b = pri->head;
153 TRACE("m0", "nbd_malloc(): take block %p off of of private list (new head is %p)", b, b->next);