- 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 first block %p", pri->head, 0);
+
+ // 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 allocate a new region. This guarentees that
+ // we amortize 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;