X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=runtime%2Fmem.c;h=7e56909fbd994cd7f77f0355b2898ef61d7d6067;hp=c65dfb05c7705fce3e2900ef6d306d708ba153ad;hb=1da02238e784eaba7bc8193f62a738e9d3f3ee1a;hpb=9ec5405d406696c6cbdb7a47ade7fccc736a8b53 diff --git a/runtime/mem.c b/runtime/mem.c index c65dfb0..7e56909 100644 --- a/runtime/mem.c +++ b/runtime/mem.c @@ -8,8 +8,8 @@ #include #include #include "common.h" +#include "runtime_local.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) @@ -27,10 +27,16 @@ typedef struct header { uint8_t scale; // log2 of the block size } header_t; +typedef struct private_list { + block_t *head; + uint32_t next_pub; + uint32_t count; +} private_list_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 block_t *pub_free_list_[MAX_NUM_THREADS][MAX_SCALE+1][MAX_NUM_THREADS] = {}; +static private_list_t pri_free_list_[MAX_NUM_THREADS][MAX_SCALE+1] = {}; static void *get_new_region (int scale) { if (scale < REGION_SCALE) { @@ -56,25 +62,34 @@ void mem_init (void) { // // TODO: maybe we want to munmap() larger size blocks to reclaim virtual address space? void nbd_free (void *x) { + 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_[(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; + TRACE("m0", "nbd_free(): block %p scale %llu", b, h->scale); + if (h->owner == tid_) { + TRACE("m0", "nbd_free(): private block, free list head %p", + h->owner, pri_free_list_[tid_][h->scale].head); + b->next = pri_free_list_[tid_][h->scale].head; + pri_free_list_[tid_][h->scale].head = b; + } else { + TRACE("m0", "nbd_free(): owner %llu free list head %p", + h->owner, pub_free_list_[h->owner][h->scale][tid_]); + b->next = pub_free_list_[h->owner][h->scale][tid_]; + pub_free_list_[h->owner][h->scale][tid_] = 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) { + assert(n); LOCALIZE_THREAD_LOCAL(tid_, int); if (n < sizeof(block_t)) { n = sizeof(block_t); @@ -82,70 +97,57 @@ void *nbd_malloc (size_t n) { 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; + private_list_t *pri = &pri_free_list_[tid_][b_scale]; // our private free list + TRACE("m0", "nbd_malloc(): private free list %p first block %p", pri->list, pri->head); + + // 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(pri->head == NULL)) { + block_t **pubs = pub_free_list_[tid_][b_scale]; // our public free lists + while (1) { + // look for blocks on our public free lists round robin + pri->next_pub = (pri->next_pub+1) & (MAX_NUM_THREADS-1); + + TRACE("m0", "nbd_malloc(): searching public free list %llu", pri->next_pub, 0); + if (pri->next_pub == tid_) { + uint32_t count = pri->count; + pri->count = 0; + // If our private list is empty and we haven't gotten at least half a region's worth + // of block's from our public lists, we break open a new region. This guarentees + // that we are amortizing the cost of accessing our public lists accross enough + // nbd_malloc() calls. + uint32_t min_count = b_scale > REGION_SCALE ? 1 << (b_scale-REGION_SCALE-1) : 1; + if (count < min_count) { + char *region = get_new_region(b_scale); + size_t b_size = 1 << b_scale; + 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->head; + pri->head = b; } + break; } + continue; } - } - 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; + if (pubs[pri->next_pub] != NULL) { + block_t *stolen = SYNC_SWAP(&pubs[pri->next_pub], NULL); + TRACE("m0", "nbd_malloc(): stole list %p first block %p", stolen); + if (stolen == NULL) + continue; + pri->head = stolen; + break; } } - - assert(pri->next); + assert(pri->head); } // Pull a block off of our private free list. - block_t *b = pri->next; + block_t *b = pri->head; 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); + pri->head = b->next; + pri->count++; return b; }