X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=runtime%2Fmem.c;fp=runtime%2Fmem.c;h=0967c4afb524b93b0941907da78d88b5568d76a8;hp=0000000000000000000000000000000000000000;hb=efd90a1b8a9d3bbb1bdd8e6ae41b3462e7193fb2;hpb=69f813b01bb0472f9ec5368b26a702bcc06f7e29 diff --git a/runtime/mem.c b/runtime/mem.c new file mode 100644 index 0000000..0967c4a --- /dev/null +++ b/runtime/mem.c @@ -0,0 +1,151 @@ +/* + * Written by Josh Dybnis and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + * + * Extreamly fast multi-threaded malloc. 64 bit platforms only! + */ +#include +#include +#include +#include "common.h" +#include "lwt.h" +#include "tls.h" + +#define GET_SCALE(n) (sizeof(n)*8-__builtin_clzl((n)-1)) // log2 of , rounded up +#define MAX_SCALE 31 // allocate blocks up to 4GB in size (arbitrary, could be bigger) +#define REGION_SCALE 22 // 4MB regions +#define REGION_SIZE (1 << REGION_SCALE) +#define HEADER_REGION_SCALE 22 // 4MB is space enough for headers for over 2,000,000 regions + +typedef struct block { + struct block *next; +} block_t; + +// region header +typedef struct header { + char owner; // thread id of owner + char scale; // log2 of the block size +} header_t; + +static header_t *region_header_ = NULL; + +// TODO: experiment with different memory layouts (i.e. separate private and public lists) +static block_t free_list_[MAX_NUM_THREADS][MAX_SCALE+1][MAX_NUM_THREADS]; + +static void *get_new_region (int scale) { + if (scale < REGION_SCALE) { + scale = REGION_SCALE; + } + TRACE("m0", "get_new_region(): mmap new region scale: %llu", scale, 0); + void *region = mmap(NULL, (1 << scale), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0); + if (region == (void *)-1) { + perror("get_new_region: mmap"); + exit(-1); + } + assert(region); + return region; +} + +void mem_init (void) { + assert(region_header_ == NULL); + region_header_ = (header_t *)get_new_region(HEADER_REGION_SCALE); + memset(region_header_, 0, REGION_SIZE); +} + +// Put onto its owner's public free list (in the appropriate size bin). +// +// TODO: maybe we want to munmap() larger size blocks to reclaim virtual address space? +void nbd_free (void *x) { + LOCALIZE_THREAD_LOCAL(tid_, int); + block_t *b = (block_t *)x; + assert(((size_t)b >> REGION_SCALE) < ((1 << HEADER_REGION_SCALE) / sizeof(header_t))); + header_t *h = region_header_ + ((size_t)b >> REGION_SCALE); + TRACE("m0", "nbd_free(): block %p scale %llu", x, h->scale); + block_t *l = &free_list_[(int)h->owner][(int)h->scale][tid_]; + TRACE("m0", "nbd_free(): free list %p first block %p", l, l->next); + b->next = l->next; + l->next = b; +} + +// Allocate a block of memory at least size . Blocks are binned in powers-of-two. Round up +// to the nearest power-of-two. +// +// First check the current thread's private free list for an available block. If no blocks are on +// the private free list, pull all the available blocks off of the current thread's public free +// lists and put them on the private free list. If we didn't find any blocks on the public free +// lists, open a new region, break it up into blocks and put them on the private free list. +void *nbd_malloc (size_t n) { + LOCALIZE_THREAD_LOCAL(tid_, int); + if (n < sizeof(block_t)) { + n = sizeof(block_t); + } + int b_scale = GET_SCALE(n); + assert(b_scale <= MAX_SCALE); + TRACE("m0", "nbd_malloc(): size %llu scale %llu", n, b_scale); + block_t *fls = free_list_[tid_][b_scale]; // our free lists + block_t *pri = fls + tid_; // our private free list + TRACE("m0", "nbd_malloc(): private free list %p first block %p", pri, pri->next); + + // If our private free list is empty, fill it up with blocks from our public free lists + if (EXPECT_FALSE(pri->next == NULL)) { + int cnt = 0; + block_t *last = pri; + for (int i = 0; i < MAX_NUM_THREADS; ++i) { + TRACE("m0", "nbd_malloc(): searching public free lists (%llu)", i, 0); + block_t *pub = fls + i; // one of our public free lists + TRACE("m0", "nbd_malloc(): public free list %p first block %p", pub, pub->next); + if (EXPECT_FALSE(pub == pri)) + continue; + + if (pub->next != NULL) { + block_t *stolen = SYNC_SWAP(&pub->next, NULL); + TRACE("m0", "nbd_malloc(): stole list %p first block %p", pub, stolen); + if (stolen) { + last->next = stolen; + TRACE("m0", "nbd_malloc(): append to last block %p of private free list", last, 0); + while (last->next) { + ++cnt; + TRACE("m0", "nbd_malloc(): find last block in list: last %p last->next %p", + last, last->next); + last = last->next; + } + } + } + } + TRACE("m0", "nbd_malloc(): moved %llu blocks from public to private free lists", cnt, 0); + + if (b_scale >= REGION_SCALE) { + if (cnt == 0) { + assert(pri->next == NULL); + pri->next = (block_t *)get_new_region(b_scale); + assert(pri->next->next == NULL); + } + assert(pri->next); + + } else if (cnt < (1 << (REGION_SCALE - b_scale - 1))) { + + // Even if we took a few blocks from our public lists we still break open a new region. + // This guarentees that we are amortizing the cost of accessing our public lists accross + // many nbd_malloc() calls. + char *region = get_new_region(b_scale); + size_t b_size = 1 << b_scale; + for (int i = REGION_SIZE; i != 0; i -= b_size) { + block_t *b = (block_t *)(region + i - b_size); + b->next = pri->next; + //TRACE("m1", "nbd_malloc(): put new block %p ahead of %p on private list", b, b->next); + pri->next = b; + *b = *b; + } + } + + assert(pri->next); + } + + // Pull a block off of our private free list. + block_t *b = pri->next; + TRACE("m0", "nbd_malloc(): take block %p off of of private list (new head is %p)", b, pri->next); + pri->next = b->next; + + assert(b); + return b; +}