394 lines
11 KiB
C
394 lines
11 KiB
C
#include <sys/mman.h>
|
|
#include <stdint.h> /* for intptr_t */
|
|
#include <unistd.h>
|
|
#include <errno.h>
|
|
#include <string.h> /* for memcpy() */
|
|
#include "rbtree.h"
|
|
#include "util.h"
|
|
#include "lj_mm.h"
|
|
#include "chunk.h"
|
|
#include "page_alloc.h"
|
|
#include "block_cache.h"
|
|
|
|
/* Forward Decl */
|
|
lm_alloc_t* alloc_info = NULL;
|
|
|
|
/* Initialize the page allocator, return 1 on success, 0 otherwise. */
|
|
int
|
|
lm_init_page_alloc(lm_chunk_t* chunk, ljmm_opt_t* mm_opt) {
|
|
if (!chunk) {
|
|
/* Trunk is not yet allocated */
|
|
return 0;
|
|
}
|
|
|
|
if (alloc_info) {
|
|
/* This function was succesfully invoked before */
|
|
return 1;
|
|
}
|
|
|
|
int page_num = chunk->page_num;
|
|
if (unlikely(mm_opt != NULL)) {
|
|
int pn = mm_opt->dbg_alloc_page_num;
|
|
if (((pn > 0) && (pn > page_num)) || !pn)
|
|
return 0;
|
|
else if (pn > 0) {
|
|
page_num = pn;
|
|
}
|
|
|
|
if (!bc_set_parameter(mm_opt->enable_block_cache,
|
|
mm_opt->blk_cache_in_page)) {
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
int alloc_sz = sizeof(lm_alloc_t) +
|
|
sizeof(lm_page_t) * (page_num + 1);
|
|
|
|
alloc_info = (lm_alloc_t*) MYMALLOC(alloc_sz);
|
|
if (!alloc_info) {
|
|
errno = ENOMEM;
|
|
return 0;
|
|
}
|
|
|
|
alloc_info->first_page = chunk->base;
|
|
alloc_info->page_num = page_num;
|
|
alloc_info->page_size = chunk->page_size;
|
|
alloc_info->page_size_log2 = log2_int32(chunk->page_size);
|
|
|
|
/* Init the page-info */
|
|
char* p = (char*)(alloc_info + 1);
|
|
int align = __alignof__(lm_page_t);
|
|
p = (char*)((((intptr_t)p) + align - 1) & ~align);
|
|
alloc_info->page_info = (lm_page_t*)p;
|
|
|
|
int i;
|
|
lm_page_t* pi = alloc_info->page_info;
|
|
for (i = 0; i < page_num; i++) {
|
|
pi[i].order = INVALID_ORDER;
|
|
pi[i].flags = 0;
|
|
}
|
|
|
|
/* Init the buddy allocator */
|
|
int e;
|
|
rb_tree_t* free_blks = &alloc_info->free_blks[0];
|
|
for (i = 0, e = MAX_ORDER; i < e; i++)
|
|
rbt_init(&free_blks[i]);
|
|
rbt_init(&alloc_info->alloc_blks);
|
|
|
|
/* Determine the max order */
|
|
int max_order = 0;
|
|
unsigned int bitmask;
|
|
for (bitmask = 0x80000000/*2G*/, max_order = 31;
|
|
bitmask;
|
|
bitmask >>= 1, max_order --) {
|
|
if (bitmask & page_num)
|
|
break;
|
|
}
|
|
alloc_info->max_order = max_order;
|
|
|
|
/* So, the ID of biggest block's first page is "1 << order". e.g.
|
|
* Suppose the chunk contains 11 pages, which will be divided into 3
|
|
* blocks, eaching containing 1, 2 and 8 pages. The indices of these
|
|
* blocks are 0, 1, 3 respectively, and their IDs are 5, 6, and 8
|
|
* respectively. In this case:
|
|
* alloc_info->idx_2_id_adj == 5 == page_id(*) - page_idx(*)
|
|
*/
|
|
int idx_2_id_adj = (1 << max_order) - (page_num & ((1 << max_order) - 1));
|
|
alloc_info->idx_2_id_adj = idx_2_id_adj;
|
|
|
|
/* Divide the chunk into blocks, smaller block first. Smaller blocks
|
|
* are likely allocated and deallocated frequently. Therefore, they are
|
|
* better off residing closer to data segment.
|
|
*/
|
|
int page_idx = 0;
|
|
int order = 0;
|
|
for (bitmask = 1, order = 0;
|
|
bitmask != 0;
|
|
bitmask = bitmask << 1, order++) {
|
|
if (page_num & bitmask) {
|
|
add_free_block(page_idx, order);
|
|
page_idx += (1 << order);
|
|
}
|
|
}
|
|
|
|
/*init the block cache */
|
|
bc_init();
|
|
|
|
return 1;
|
|
}
|
|
|
|
void
|
|
lm_fini_page_alloc(void) {
|
|
if (alloc_info) {
|
|
rb_tree_t* free_blks = &alloc_info->free_blks[0];
|
|
int i, e;
|
|
for (i = 0, e = MAX_ORDER; i < e; i++)
|
|
rbt_fini(free_blks + i);
|
|
|
|
rbt_fini(&alloc_info->alloc_blks);
|
|
|
|
MYFREE(alloc_info);
|
|
alloc_info = 0;
|
|
}
|
|
|
|
bc_fini();
|
|
}
|
|
|
|
/* To extend the given exiting allocated block such that it can accommodate
|
|
* at least new_sz bytes.
|
|
*/
|
|
int
|
|
extend_alloc_block(page_idx_t block_idx, size_t new_sz) {
|
|
rb_tree_t* rbt = &alloc_info->alloc_blks;
|
|
intptr_t alloc_sz;
|
|
int res = rbt_search(rbt, block_idx, &alloc_sz);
|
|
#ifdef DEBUG
|
|
ASSERT(res);
|
|
#else
|
|
(void)res;
|
|
#endif
|
|
|
|
int page_sz = alloc_info->page_size;
|
|
int page_sz_log2 = alloc_info->page_size_log2;
|
|
int min_page_num = (new_sz + page_sz - 1) >> page_sz_log2;
|
|
|
|
page_id_t blk_id = page_idx_to_id(block_idx);
|
|
int order = alloc_info->page_info[block_idx].order;
|
|
|
|
/* step 1: The in-place block extension is done by merging its *following*
|
|
* free buddy to a form bigger block. The extension process repeats until
|
|
* we find a block bigger enough to accommodate the <new_sz> bytes.
|
|
*/
|
|
int succ = 0;
|
|
int ord;
|
|
for (ord = order; ord <= alloc_info->max_order; ord++) {
|
|
if (min_page_num <= (1 << ord)) {
|
|
succ = 1;
|
|
break;
|
|
}
|
|
|
|
page_id_t buddy_id = blk_id ^ (1 << ord);
|
|
if (buddy_id < blk_id) {
|
|
/* The buddy block must reside at higher address. */
|
|
break;
|
|
}
|
|
|
|
int buddy_idx = page_id_to_idx(buddy_id);
|
|
if (!rbt_search(&alloc_info->free_blks[ord], buddy_idx, NULL)) {
|
|
/* bail out if the buddy is not available */
|
|
break;
|
|
}
|
|
}
|
|
|
|
/* This function is not supposed to shrink the existing block; therefore,
|
|
* if the existing block is big enough to accommodate allocation request,
|
|
* it need to return 0 to inform the caller that something fishy is
|
|
* happening.
|
|
*/
|
|
if (!succ || ord == order)
|
|
return 0;
|
|
|
|
/* Step 2: The previous step is merely a 'dry-run' of extension. This
|
|
* step is to perform real transformation.
|
|
*/
|
|
int t;
|
|
for (t = order; t < ord; t++) {
|
|
page_id_t buddy_id = blk_id ^ (1 << t);
|
|
int buddy_idx = page_id_to_idx(buddy_id);
|
|
remove_free_block(buddy_idx, t, 0);
|
|
reset_page_leader(alloc_info->page_info + buddy_idx);
|
|
}
|
|
|
|
migrade_alloc_block(block_idx, order, ord, new_sz);
|
|
|
|
return 1;
|
|
}
|
|
|
|
/* Free the block whose first page (aka block leader) is specified
|
|
* by "page_idx". return 1 on success and 0 otherwise.
|
|
*/
|
|
int
|
|
free_block(page_idx_t page_idx) {
|
|
(void)remove_alloc_block(page_idx);
|
|
|
|
lm_page_t* pi = alloc_info->page_info;
|
|
lm_page_t* page = pi + page_idx;
|
|
int order = page->order;
|
|
ASSERT (find_block(page_idx, order, NULL) == 0);
|
|
|
|
/* Consolidate adjacent buddies */
|
|
int page_num = alloc_info->page_num;
|
|
page_id_t page_id = page_idx_to_id(page_idx);
|
|
int min_page_id = alloc_info->idx_2_id_adj;
|
|
while (1) {
|
|
page_id_t buddy_id = page_id ^ (1<<order);
|
|
if (buddy_id < min_page_id)
|
|
break;
|
|
|
|
page_idx_t buddy_idx = page_id_to_idx(buddy_id);
|
|
if (buddy_idx >= page_num ||
|
|
pi[buddy_idx].order != order ||
|
|
!is_page_leader(pi + buddy_idx) ||
|
|
is_allocated_blk(pi + buddy_idx)) {
|
|
break;
|
|
}
|
|
remove_free_block(buddy_idx, order, 0);
|
|
reset_page_leader(alloc_info->page_info + buddy_idx);
|
|
|
|
page_id = page_id < buddy_id ? page_id : buddy_id;
|
|
order++;
|
|
}
|
|
|
|
add_free_block(page_id_to_idx(page_id), order);
|
|
return 1;
|
|
}
|
|
|
|
/**************************************************************************
|
|
*
|
|
* Debugging Support & Misc "cold" functions
|
|
*
|
|
**************************************************************************
|
|
*/
|
|
const lm_status_t*
|
|
lm_get_status(void) {
|
|
if (!alloc_info)
|
|
return NULL;
|
|
|
|
lm_status_t* s = (lm_status_t *)MYMALLOC(sizeof(lm_status_t));
|
|
s->first_page = alloc_info->first_page;
|
|
s->page_num = alloc_info->page_num;
|
|
s->idx_to_id = alloc_info->idx_2_id_adj;
|
|
s->alloc_blk_num = 0;
|
|
s->free_blk_num = 0;
|
|
s->free_blk_info = NULL;
|
|
s->alloc_blk_info = NULL;
|
|
rb_tree_t* rbt = &alloc_info->alloc_blks;
|
|
int alloc_blk_num = rbt_size(rbt);
|
|
|
|
/* Populate allocated block info */
|
|
if (alloc_blk_num) {
|
|
block_info_t* ai;
|
|
ai = (block_info_t*)MYMALLOC(sizeof(block_info_t) * alloc_blk_num);
|
|
|
|
rb_iter_t iter, iter_e;
|
|
int idx = 0;
|
|
for (iter = rbt_iter_begin(rbt), iter_e = rbt_iter_end(rbt);
|
|
iter != iter_e;
|
|
iter = rbt_iter_inc(rbt, iter)) {
|
|
rb_node_t* blk = rbt_iter_deref(iter);
|
|
ai[idx].page_idx = blk->key;
|
|
ai[idx].size = blk->value;
|
|
ai[idx].order = alloc_info->page_info[blk->key].order;
|
|
idx++;
|
|
}
|
|
|
|
s->alloc_blk_info = ai;
|
|
s->alloc_blk_num = idx;
|
|
}
|
|
|
|
/* Populate free block info */
|
|
int free_blk_num = 0;
|
|
int i, e;
|
|
for (i = 0, e = alloc_info->max_order; i <= e; i++) {
|
|
free_blk_num += rbt_size(alloc_info->free_blks + i);
|
|
}
|
|
if (free_blk_num) {
|
|
block_info_t* fi;
|
|
fi = (block_info_t*)MYMALLOC(sizeof(block_info_t) * free_blk_num);
|
|
|
|
int idx = 0;
|
|
int page_size_log2 = alloc_info->page_size_log2;
|
|
for (i = 0, e = alloc_info->max_order; i <= e; i++) {
|
|
rb_tree_t* rbt = alloc_info->free_blks + i;
|
|
|
|
rb_iter_t iter, iter_e;
|
|
for (iter = rbt_iter_begin(rbt), iter_e = rbt_iter_end(rbt);
|
|
iter != iter_e;
|
|
iter = rbt_iter_inc(rbt, iter)) {
|
|
rb_node_t* nd = rbt_iter_deref(iter);
|
|
fi[idx].page_idx = nd->key;
|
|
fi[idx].order = alloc_info->page_info[nd->key].order;
|
|
fi[idx].size = (1 << fi[idx].order) << page_size_log2;
|
|
idx++;
|
|
}
|
|
}
|
|
ASSERT(idx == free_blk_num);
|
|
|
|
s->free_blk_info = fi;
|
|
s->free_blk_num = idx;
|
|
}
|
|
|
|
return s;
|
|
}
|
|
|
|
void
|
|
lm_free_status(lm_status_t* status) {
|
|
if (!status)
|
|
return;
|
|
|
|
if (status->free_blk_info)
|
|
MYFREE(status->free_blk_info);
|
|
|
|
if (status->alloc_blk_info)
|
|
MYFREE(status->alloc_blk_info);
|
|
|
|
MYFREE(status);
|
|
}
|
|
|
|
#ifdef DEBUG
|
|
void
|
|
dump_page_alloc(FILE* f) {
|
|
if (!alloc_info) {
|
|
fprintf(f, "not initialized yet\n");
|
|
fflush(f);
|
|
return;
|
|
}
|
|
|
|
/* dump the buddy system */
|
|
fprintf (f, "Buddy system: max-order=%d, id - idx = %d\n",
|
|
alloc_info->max_order, alloc_info->idx_2_id_adj);
|
|
|
|
int i, e;
|
|
char* page_start_addr = alloc_info->first_page;
|
|
int page_sz_log = alloc_info->page_size_log2;
|
|
|
|
for (i = 0, e = alloc_info->max_order; i <= e; i++) {
|
|
rb_tree_t* free_blks = &alloc_info->free_blks[i];
|
|
|
|
if (rbt_is_empty(free_blks))
|
|
continue;
|
|
|
|
fprintf(f, "Order = %3d: ", i);
|
|
rb_iter_t iter, iter_e;
|
|
for (iter = rbt_iter_begin(free_blks),
|
|
iter_e = rbt_iter_end(free_blks);
|
|
iter != iter_e;
|
|
iter = rbt_iter_inc(free_blks, iter)) {
|
|
rb_node_t* node = rbt_iter_deref(iter);
|
|
page_idx_t page_idx = node->key;
|
|
char* addr = page_start_addr + (page_idx << page_sz_log);
|
|
fprintf(f, "pg_idx:%d (%p, len=%d), ", page_idx,
|
|
addr, (int)node->value);
|
|
verify_order(page_idx, i);
|
|
}
|
|
fputs("\n", f);
|
|
}
|
|
|
|
fprintf(f, "\nAllocated blocks:\n");
|
|
{
|
|
rb_tree_t* rbt = &alloc_info->alloc_blks;
|
|
rb_iter_t iter, iter_e;
|
|
int idx = 0;
|
|
for (iter = rbt_iter_begin(rbt), iter_e = rbt_iter_end(rbt);
|
|
iter != iter_e;
|
|
iter = rbt_iter_inc(rbt, iter)) {
|
|
rb_node_t* nd = rbt_iter_deref(iter);
|
|
int blk = nd->key;
|
|
fprintf(f, "%3d: pg_idx:%d, size:%ld, order = %d\n",
|
|
idx, blk, nd->value, alloc_info->page_info[blk].order);
|
|
idx++;
|
|
}
|
|
}
|
|
}
|
|
#endif
|