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.
7 #ifndef USE_SYSTEM_MALLOC
8 #define _BSD_SOURCE // so we get MAP_ANON on linux
19 #define MAX_SCALE 31 // allocate blocks up to 4GB (arbitrary, could be bigger)
21 #define MIN_SCALE 3 // smallest allocated block is 8 bytes
22 #define MAX_POINTER_BITS 48
23 #define PAGE_SCALE 21 // 2MB pages
25 #define MIN_SCALE 2 // smallest allocated block is 4 bytes
26 #define MAX_POINTER_BITS 32
27 #define PAGE_SCALE 12 // 4KB pages
29 #define PAGE_SIZE (1 << PAGE_SCALE)
30 #define HEADERS_SIZE (((size_t)1 << (MAX_POINTER_BITS - PAGE_SCALE)) * sizeof(header_t))
32 typedef struct block {
36 // TODO: Break the page header into two parts. The first part is located in the header region. The
37 // second part is located on the page and is only used when there are free items.
38 typedef struct header {
42 block_t *free_list; // list of free blocks
45 uint8_t owner; // thread id of owner
46 uint8_t scale; // log2 of the block size
50 typedef struct size_class {
51 header_t *active_page;
52 header_t *oldest_partial;
53 header_t *newest_partial;
59 block_t *free_list[MAX_SCALE+1];
62 size_class_t size_class[MAX_SCALE+1];
64 block_t *blocks_from[MAX_NUM_THREADS];
65 block_t *blocks_to[MAX_NUM_THREADS];
66 } __attribute__((aligned(CACHE_LINE_SIZE))) tl_t;
68 static header_t *headers_ = NULL;
70 static tl_t tl_[MAX_NUM_THREADS] = {};
72 static inline header_t *get_header (void *r) {
73 ASSERT(((size_t)r >> PAGE_SCALE) < HEADERS_SIZE);
74 return headers_ + ((size_t)r >> PAGE_SCALE);
77 static void *get_new_region (int block_scale) {
78 LOCALIZE_THREAD_LOCAL(tid_, int);
80 tl_t *tl = &tl_[tid_]; // thread-local data
81 if (block_scale <= PAGE_SCALE && tl->free_pages != NULL) {
82 void *region = tl->free_pages;
83 tl->free_pages = tl->free_pages->next;
84 get_header(region)->scale = block_scale;
88 size_t region_size = (1 << block_scale);
89 if (region_size < PAGE_SIZE) {
90 region_size = PAGE_SIZE;
92 void *region = mmap(NULL, region_size, PROT_READ|PROT_WRITE, MAP_NORESERVE|MAP_ANON|MAP_PRIVATE, -1, 0);
93 TRACE("m1", "get_new_region: mmapped new region %p (size %p)", region, region_size);
94 if (region == (void *)-1) {
95 perror("get_new_region: mmap");
98 if ((size_t)region & (region_size - 1)) {
99 TRACE("m0", "get_new_region: region not aligned", 0, 0);
100 munmap(region, region_size);
101 region = mmap(NULL, region_size * 2, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
102 if (region == (void *)-1) {
103 perror("get_new_region: mmap");
106 TRACE("m0", "get_new_region: mmapped new region %p (size %p)", region, region_size * 2);
107 void *aligned = (void *)(((size_t)region + region_size) & ~(region_size - 1));
108 size_t extra = (char *)aligned - (char *)region;
110 munmap(region, extra);
111 TRACE("m0", "get_new_region: unmapped extra memory %p (size %p)", region, extra);
113 extra = ((char *)region + region_size) - (char *)aligned;
115 munmap((char *)aligned + region_size, extra);
116 TRACE("m0", "get_new_region: unmapped extra memory %p (size %p)", (char *)aligned + region_size, extra);
122 header_t *h = get_header(region);
123 TRACE("m1", "get_new_region: header %p (%p)", h, h - headers_);
124 assert(h->scale == 0);
125 h->scale = block_scale;
131 void mem_init (void) {
132 assert(headers_ == NULL);
133 // Allocate space for the page headers. This could be a big chunk of memory on 64 bit systems,
134 // but it just takes up virtual address space. Physical space used by the headers is still
135 // proportional to the amount of memory the user mallocs.
136 headers_ = mmap(NULL, HEADERS_SIZE, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
137 TRACE("m1", "mem_init: header page %p", headers_, 0);
139 // initialize spsc queues
140 for (int i = 0; i < MAX_NUM_THREADS; ++i) {
141 for (int j = 0; j < MAX_NUM_THREADS; ++j) {
143 tl_[i].blocks_to[j] = (block_t *)&(tl_[j].blocks_from[i]);
149 void nbd_free (void *x) {
150 TRACE("m1", "nbd_free: block %p page %p", x, (size_t)x & ~MASK(PAGE_SCALE));
152 LOCALIZE_THREAD_LOCAL(tid_, int);
153 block_t *b = (block_t *)x;
154 header_t *h = get_header(x);
155 int b_scale = h->scale;
156 TRACE("m1", "nbd_free: header %p scale %llu", h, b_scale);
157 ASSERT(b_scale && b_scale <= MAX_SCALE);
159 if (b_scale > PAGE_SCALE) {
160 int rc = munmap(x, 1 << b_scale);
166 memset(b, 0xcd, (1 << b_scale)); // bear trap
168 tl_t *tl = &tl_[tid_]; // thread-local data
169 if (h->owner == tid_) {
170 TRACE("m1", "nbd_free: private block, old free list head %p", tl->free_list[b_scale], 0);
172 #ifndef RECYCLE_PAGES
173 b->next = tl->free_list[b_scale];
174 tl->free_list[b_scale] = b;
175 #else //RECYCLE_PAGES
176 b->next = h->free_list;
179 size_class_t *sc = &tl->size_class[b_scale];
180 if (sc->active_page != h) {
181 if (h->num_in_use == 0) {
182 // remove <h> from the partial-page list
183 if (h->next != NULL) { h->next->prev = h->prev; }
184 if (h->prev != NULL) { h->prev->next = h->next; }
185 // put <h> on the free-page list
186 h->next = tl->free_pages;
189 // move <h> to the top of the partial-page list
190 if (h->next != NULL) {
191 h->next->prev = h->prev;
192 if (h->prev != NULL) { h->prev->next = h->next; }
193 h->prev = sc->newest_partial;
195 sc->newest_partial = h;
199 #endif//RECYCLE_PAGES
201 // push <b> onto it's owner's queue
202 int b_owner = h->owner;
203 TRACE("m1", "nbd_free: owner %llu", b_owner, 0);
205 // The assignment statements are volatile to prevent the compiler from reordering them.
206 VOLATILE_DEREF(b).next = NULL;
207 VOLATILE_DEREF(tl->blocks_to[b_owner]).next = b;
209 tl->blocks_to[b_owner] = b;
213 static inline void process_incoming_blocks (tl_t *tl) {
214 for (int p = 0; p < MAX_NUM_THREADS; ++p) {
215 block_t *b = tl->blocks_from[p];
216 if (EXPECT_FALSE(b == NULL)) continue; // the queue is completely empty
218 // Leave the last block on the queue. Removing the last block on the queue would create a
219 // race with the producer thread putting a new block on the queue.
220 for (block_t *next = b->next; next != NULL; b = next, next = b->next) {
221 // push <b> onto the appropriate free list
222 #ifndef RECYCLE_PAGES
223 int b_scale = get_header(b)->scale;
224 b->next = tl->free_list[b_scale];
225 tl->free_list[b_scale] = b;
226 #else //RECYCLE_PAGES
227 header_t *h = get_header(b);
228 b->next = h->free_list;
230 #endif//RECYCLE_PAGES
232 tl->blocks_from[p] = b;
236 static inline block_t *pop_free_list (tl_t *tl, int scale) {
237 #ifndef RECYCLE_PAGES
238 block_t **free_list = &tl->free_list[scale];
239 #else //RECYCLE_PAGES
240 size_class_t *sc = &tl->size_class[scale];
241 if (EXPECT_FALSE(sc->active_page == NULL))
243 block_t **free_list = &sc->active_page->free_list;
244 #endif//RECYCLE_PAGES
245 block_t *b = *free_list;
246 if (EXPECT_FALSE(b == NULL))
248 ASSERT(get_header(b)->scale == scale);
249 *free_list = b->next;
253 // Allocate a block of memory at least size <n>. Blocks are binned in powers-of-two. Round up <n> to
254 // the nearest power of two.
256 // First check the current thread's free list for an available block. If there are no blocks on the
257 // free list, pull items off of the current thread's incoming block queues and push them onto the
258 // free list. If we didn't get an appropriate size block off of the block queues then allocate a new
259 // page, break it up into blocks and push them onto the free list.
260 void *nbd_malloc (size_t n) {
261 // the scale is the log base 2 of <n>, rounded up
262 int b_scale = (sizeof(void *) * __CHAR_BIT__) - __builtin_clzl((n) - 1);
263 TRACE("m1", "nbd_malloc: size %llu (scale %llu)", n, b_scale);
265 if (EXPECT_FALSE(b_scale < MIN_SCALE)) { b_scale = MIN_SCALE; }
266 if (EXPECT_FALSE(b_scale > MAX_SCALE)) { return NULL; }
268 LOCALIZE_THREAD_LOCAL(tid_, int);
269 tl_t *tl = &tl_[tid_]; // thread-local data
271 block_t *b = pop_free_list(tl, b_scale);
273 TRACE("m1", "nbd_malloc: returning block %p", b, 0);
277 // The free list is empty so process blocks freed from other threads and then check again.
278 process_incoming_blocks(tl);
279 b = pop_free_list(tl, b_scale);
281 TRACE("m1", "nbd_malloc: returning block %p", b, 0);
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);
295 TRACE("m1", "nbd_malloc: returning block %p", b, 0);
298 // There are no partially allocated pages so get a new page.
300 #endif//RECYCLE_PAGES
303 char *page = get_new_region(b_scale);
304 b = (block_t *)page; // grab the first block on the page
306 // Break up the remainder of the page into blocks and put them on the free list. Start at the
307 // end of the page so that the free list ends up in increasing order, for ease of debugging.
308 if (b_scale < PAGE_SCALE) {
309 size_t block_size = (1 << b_scale);
310 block_t *head = NULL;
311 for (int offset = PAGE_SIZE - block_size; offset > 0; offset -= block_size) {
312 block_t *x = (block_t *)(page + offset);
313 x->next = head; head = x;
315 #ifndef RECYCLE_PAGES
316 tl->free_list[b_scale] = head;
317 #else //RECYCLE_PAGES
318 sc->active_page = get_header(page);
319 sc->active_page->free_list = head;
320 #endif//RECYCLE_PAGES
323 TRACE("m1", "nbd_malloc: returning block %p from new region %p", b, (size_t)b & ~MASK(PAGE_SCALE));
326 #else//USE_SYSTEM_MALLOC
329 void mem_init (void) {
333 void ndb_free (void *x) {
334 TRACE("m1", "nbd_free: %p", x, 0);
336 memset(x, 0xcd, sizeof(void *)); // bear trap
342 void *nbd_malloc (size_t n) {
343 TRACE("m1", "nbd_malloc: request size %llu", n, 0);
345 TRACE("m1", "nbd_malloc: returning %p", x, 0);
348 #endif//USE_SYSTEM_MALLOC