X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=runtime%2Fmem.c;h=57d94aa59fe817aa3e88c5c8dc4dc4365639336a;hp=f6fd318aef75f732c781b7d4a62585d6b382ea99;hb=6b4f3ea4891b6c0e65dfd6d41f49aee2daa9e23d;hpb=fb536c12185fd1e339b5fd479d9ef84554b436df diff --git a/runtime/mem.c b/runtime/mem.c index f6fd318..57d94aa 100644 --- a/runtime/mem.c +++ b/runtime/mem.c @@ -2,20 +2,27 @@ * 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! + * Extreamly fast multi-threaded malloc. */ +#define _BSD_SOURCE // so we get MAP_ANON on linux #include #include #include #include "common.h" -#include "runtime_local.h" +#include "rlocal.h" #include "lwt.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 GET_SCALE(n) (sizeof(void *)*__CHAR_BIT__ - __builtin_clzl((n) - 1)) // log2 of , rounded up +#ifndef NBD32 +#define MAX_POINTER_BITS 48 +#define REGION_SCALE 21 // 2mb regions +#else +#define MAX_POINTER_BITS 32 +#define REGION_SCALE 12 // 4kb regions +#endif #define REGION_SIZE (1 << REGION_SCALE) -#define HEADER_REGION_SCALE 22 // 4MB is space enough for headers for over 2,000,000 regions +#define HEADER_REGION_SCALE ((MAX_POINTER_BITS - REGION_SCALE) + GET_SCALE(sizeof(header_t))) +#define MAX_SCALE 31 // allocate blocks up to 4GB in size (arbitrary, could be bigger) typedef struct block { struct block *next; @@ -27,125 +34,185 @@ typedef struct header { uint8_t scale; // log2 of the block size } header_t; -static header_t *region_header_ = NULL; +typedef struct tl { + block_t *free_blocks[MAX_SCALE+1]; + block_t *blocks_from[MAX_NUM_THREADS]; + block_t *blocks_to[MAX_NUM_THREADS]; +} __attribute__((aligned(CACHE_LINE_SIZE))) tl_t ; + +static header_t *headers_ = 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 tl_t tl_[MAX_NUM_THREADS] = {}; -static void *get_new_region (int scale) { - if (scale < REGION_SCALE) { - scale = REGION_SCALE; +static inline header_t *get_header (void *r) { + return headers_ + ((size_t)r >> REGION_SCALE); +} + +static void *get_new_region (int block_scale) { + size_t sz = (1 << block_scale); + if (sz < REGION_SIZE) { + sz = REGION_SIZE; } - 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); + void *region = mmap(NULL, sz, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0); + TRACE("m1", "get_new_region: mmapped new region %p (size %p)", region, sz); if (region == (void *)-1) { perror("get_new_region: mmap"); exit(-1); } + if ((size_t)region & (sz - 1)) { + TRACE("m0", "get_new_region: region not aligned", 0, 0); + munmap(region, sz); + region = mmap(NULL, sz * 2, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0); + if (region == (void *)-1) { + perror("get_new_region: mmap"); + exit(-1); + } + TRACE("m0", "get_new_region: mmapped new region %p (size %p)", region, sz * 2); + void *aligned = (void *)(((size_t)region + sz) & ~(sz - 1)); + size_t extra = (char *)aligned - (char *)region; + if (extra) { + munmap(region, extra); + TRACE("m0", "get_new_region: unmapped extra memory %p (size %p)", region, extra); + } + extra = ((char *)region + sz) - (char *)aligned; + if (extra) { + munmap((char *)aligned + sz, extra); + TRACE("m0", "get_new_region: unmapped extra memory %p (size %p)", (char *)aligned + sz, extra); + } + region = aligned; + } assert(region); + if (headers_ != NULL) { + LOCALIZE_THREAD_LOCAL(tid_, int); + header_t *h = get_header(region); + TRACE("m1", "get_new_region: header %p (%p)", h, h - headers_); + + assert(h->scale == 0); + h->scale = block_scale; + h->owner = tid_; + } + 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); +#ifdef USE_SYSTEM_MALLOC + return; +#endif + assert(headers_ == NULL); + // Allocate a region for the region headers. This could be a big chunk of memory (256MB) on 64 bit systems, + // but it just takes up virtual address space. Physical address space used by the headers is still proportional + // to the amount of memory we alloc. + headers_ = (header_t *)get_new_region(HEADER_REGION_SCALE); + TRACE("m1", "mem_init: header region %p", headers_, 0); + memset(headers_, 0, (1 << HEADER_REGION_SCALE)); } // 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? +// TODO: maybe we want to munmap() larger size blocks? void nbd_free (void *x) { +#ifdef USE_SYSTEM_MALLOC + TRACE("m1", "nbd_free: %p", x, 0); +#ifndef NDEBUG + //memset(x, 0xcd, sizeof(void *)); // bear trap +#endif//NDEBUG + free(x); + return; +#endif//USE_SYSTEM_MALLOC + TRACE("m1", "nbd_free: block %p region %p", x, (size_t)x & ~MASK(REGION_SCALE)); + + assert(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_[h->owner][h->scale][tid_]; - TRACE("m0", "nbd_free(): free list %p first block %p", l, l->next); - b->next = l->next; - l->next = b; + header_t *h = get_header(x); + TRACE("m1", "nbd_free: header %p scale %llu", h, h->scale); + assert(h->scale && h->scale <= MAX_SCALE); +#ifndef NDEBUG + memset(b, 0xcd, (1 << h->scale)); // bear trap +#endif + tl_t *tl = &tl_[tid_]; // thread-local data + if (h->owner == tid_) { + TRACE("m1", "nbd_free: private block, old free list head %p", tl->free_blocks[h->scale], 0); + b->next = tl->free_blocks[h->scale]; + tl->free_blocks[h->scale] = b; + } else { + TRACE("m1", "nbd_free: owner %llu", h->owner, 0); + // push onto it's owner's queue + VOLATILE(b->next) = NULL; + if (EXPECT_FALSE(tl->blocks_to[h->owner] == NULL)) { + VOLATILE(tl_[h->owner].blocks_from[tid_]) = b; + } else { + VOLATILE(tl->blocks_to[h->owner]->next) = b; + } + tl->blocks_to[h->owner] = 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. +// the private free list, pull 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, allocate 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); +#ifdef USE_SYSTEM_MALLOC + TRACE("m1", "nbd_malloc: request size %llu (scale %llu)", n, GET_SCALE(n)); + void *x = malloc(n); + TRACE("m1", "nbd_malloc: returning %p", x, 0); + return x; +#endif + if (EXPECT_FALSE(n == 0)) + return NULL; if (n < sizeof(block_t)) { n = sizeof(block_t); } int b_scale = GET_SCALE(n); + assert(b_scale >= 2); 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("m1", "nbd_malloc: request size %llu (scale %llu)", n, b_scale); + LOCALIZE_THREAD_LOCAL(tid_, int); + tl_t *tl = &tl_[tid_]; // thread-local data + + // If our private free list is empty, try to find blocks on our public free list. If that fails, + // allocate a new region. + if (EXPECT_FALSE(tl->free_blocks[b_scale] == NULL)) { + for (int i = 0; i < MAX_NUM_THREADS; ++ i) { + block_t *x = tl->blocks_from[i]; + if (x != NULL) { + block_t *next = x->next; + if (next != NULL) { + do { + header_t *h = get_header(x); + x->next = tl->free_blocks[h->scale]; + tl->free_blocks[h->scale] = x; + x = next; + next = x->next; + } while (next != NULL); + tl->blocks_from[i] = x; } } } - 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); + // allocate a new region + if (tl->free_blocks[b_scale] == NULL) { + char *region = get_new_region(b_scale); size_t b_size = 1 << b_scale; - for (int i = REGION_SIZE; i != 0; i -= b_size) { + size_t region_size = (b_size < REGION_SIZE) ? REGION_SIZE : b_size; + 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; + b->next = tl->free_blocks[b_scale]; + tl->free_blocks[b_scale] = b; } } - - assert(pri->next); + assert(tl->free_blocks[b_scale] != NULL); } // 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); + block_t *b = tl->free_blocks[b_scale]; + TRACE("m1", "nbd_malloc: returning block %p (region %p) from private list", b, (size_t)b & ~MASK(REGION_SCALE)); + ASSERT(b); + ASSERT(get_header(b)->scale == b_scale); + tl->free_blocks[b_scale] = b->next; return b; }