206 lines
5.3 KiB
C
206 lines
5.3 KiB
C
#ifndef _PAGE_ALLOC_H_
|
|
#define _PAGE_ALLOC_H_
|
|
|
|
#include "rbtree.h"
|
|
#include "util.h"
|
|
#include "chunk.h" /* for lm_chunk_t */
|
|
#include "lj_mm.h"
|
|
#include "block_cache.h"
|
|
|
|
/**************************************************************************
|
|
*
|
|
* Depicting page
|
|
*
|
|
**************************************************************************
|
|
*/
|
|
typedef struct {
|
|
short order; /* the order in the buddy allocation */
|
|
short flags;
|
|
} lm_page_t;
|
|
|
|
typedef enum {
|
|
PF_LEADER = (1 << 0), /* set if it's the first page of a block */
|
|
PF_ALLOCATED = (1 << 1), /* set if it's "leader" of a allocated block */
|
|
PF_LAST = PF_ALLOCATED,
|
|
} page_flag_t;
|
|
|
|
static inline int
|
|
is_page_leader(lm_page_t * p) {
|
|
return p->flags & PF_LEADER;
|
|
}
|
|
|
|
static inline void
|
|
set_page_leader(lm_page_t* p) {
|
|
p->flags |= PF_LEADER;
|
|
}
|
|
|
|
static inline void
|
|
reset_page_leader(lm_page_t* p) {
|
|
p->flags &= ~PF_LEADER;
|
|
}
|
|
|
|
static inline int
|
|
is_allocated_blk(lm_page_t* p) {
|
|
return is_page_leader(p) && (p->flags & PF_ALLOCATED);
|
|
}
|
|
|
|
static inline void
|
|
set_allocated_blk(lm_page_t* p) {
|
|
ASSERT(is_page_leader(p));
|
|
p->flags |= PF_ALLOCATED;
|
|
}
|
|
|
|
static inline void
|
|
reset_allocated_blk(lm_page_t* p) {
|
|
ASSERT(is_page_leader(p));
|
|
p->flags &= ~PF_ALLOCATED;
|
|
}
|
|
|
|
/* We could have up to 1M pages (4G/4k). Hence 20 */ #define MAX_ORDER 20
|
|
#define INVALID_ORDER (-1)
|
|
|
|
/**************************************************************************
|
|
*
|
|
* Buddy Allocation
|
|
*
|
|
**************************************************************************
|
|
*/
|
|
typedef struct {
|
|
char* first_page; /* The starting address of the first page */
|
|
lm_page_t* page_info;
|
|
/* Free blocks of the same order are ordered by a RB tree. */
|
|
rb_tree_t free_blks[MAX_ORDER];
|
|
rb_tree_t alloc_blks;
|
|
int max_order;
|
|
int page_num; /* This many pages in total */
|
|
int page_size; /* The size of page in byte, normally 4k*/
|
|
int page_size_log2; /* log2(page_size)*/
|
|
int idx_2_id_adj;
|
|
} lm_alloc_t;
|
|
|
|
extern lm_alloc_t* alloc_info;
|
|
|
|
static inline page_id_t
|
|
page_idx_to_id(page_idx_t idx) {
|
|
ASSERT(idx >= 0 && idx < alloc_info->page_num);
|
|
return idx + alloc_info->idx_2_id_adj;
|
|
}
|
|
|
|
static inline page_idx_t
|
|
page_id_to_idx(page_id_t id) {
|
|
int idx = id - alloc_info->idx_2_id_adj;
|
|
ASSERT(idx >= 0 && idx < alloc_info->page_num);
|
|
return idx;
|
|
}
|
|
|
|
static inline char*
|
|
get_page_addr(page_idx_t pg) {
|
|
return alloc_info->first_page + (pg << alloc_info->page_size_log2);
|
|
}
|
|
|
|
static inline int
|
|
verify_order(page_idx_t blk_leader, int order) {
|
|
return 0 == (page_idx_to_id(blk_leader) & ((1<<order) - 1));
|
|
}
|
|
|
|
static inline int
|
|
find_block(page_idx_t block, int order, intptr_t* value) {
|
|
ASSERT(order >= 0 && order <= alloc_info->max_order &&
|
|
verify_order(block, order));
|
|
|
|
return rbt_search(&alloc_info->free_blks[order], block, value);
|
|
}
|
|
|
|
/* If zap_pages is set, the corresponding pages will be removed via madvise()*/
|
|
static inline int
|
|
remove_free_block(page_idx_t block, int order, int zap_pages) {
|
|
#ifdef DEBUG
|
|
{
|
|
lm_page_t* page = alloc_info->page_info + block;
|
|
ASSERT(page->order == order && find_block(block, order, NULL));
|
|
ASSERT(!is_allocated_blk(page) && verify_order(block, order));
|
|
}
|
|
#endif
|
|
|
|
bc_remove_block(block, order, zap_pages);
|
|
|
|
return rbt_delete(&alloc_info->free_blks[order], block, NULL);
|
|
}
|
|
|
|
/* Add the free block of the given "order" to the buddy system */
|
|
static inline int
|
|
add_free_block(page_idx_t block, int order) {
|
|
lm_page_t* page = alloc_info->page_info + block;
|
|
|
|
ASSERT(order >= 0 && order <= alloc_info->max_order &&
|
|
verify_order(block, order));
|
|
|
|
page->order = order;
|
|
set_page_leader(page);
|
|
reset_allocated_blk(page);
|
|
|
|
bc_add_blk(block, order);
|
|
return rbt_insert(&alloc_info->free_blks[order], block, 0);
|
|
}
|
|
|
|
/* The extend given the exiting allocated block such that it could accommodate
|
|
* at least new_sz bytes.
|
|
*/
|
|
int extend_alloc_block(page_idx_t block, size_t new_sz);
|
|
|
|
static inline int
|
|
add_alloc_block(page_idx_t block, intptr_t sz, int order) {
|
|
int res = rbt_insert(&alloc_info->alloc_blks, block, (intptr_t)sz);
|
|
ASSERT(res);
|
|
|
|
lm_page_t* pg = alloc_info->page_info + block;
|
|
pg->order = order;
|
|
set_page_leader(pg);
|
|
set_allocated_blk(pg);
|
|
|
|
bc_remove_block(block, order, 0);
|
|
madvise(alloc_info->first_page + block,
|
|
(1 << order) << alloc_info->page_size_log2,
|
|
MADV_DODUMP);
|
|
|
|
return res;
|
|
}
|
|
|
|
static inline int
|
|
remove_alloc_block(page_idx_t block) {
|
|
ASSERT(is_page_leader(alloc_info->page_info + block));
|
|
int res = rbt_delete(&alloc_info->alloc_blks, block, NULL);
|
|
ASSERT(res);
|
|
return res;
|
|
}
|
|
|
|
static inline int
|
|
no_alloc_blocks(void) {
|
|
return rbt_is_empty(&alloc_info->alloc_blks);
|
|
}
|
|
|
|
static inline void
|
|
migrade_alloc_block(page_idx_t block, int ord_was, int ord_is, size_t new_map_sz) {
|
|
rb_tree_t* rbt = &alloc_info->alloc_blks;
|
|
int res = rbt_set_value(rbt, block, new_map_sz);
|
|
#ifdef DEBUG
|
|
ASSERT(res != 0 && alloc_info->page_info[block].order == ord_was);
|
|
#else
|
|
(void)res;
|
|
#endif
|
|
alloc_info->page_info[block].order = ord_is;
|
|
}
|
|
|
|
int free_block(page_idx_t page_idx);
|
|
|
|
/* Init & Fini */
|
|
int lm_init_page_alloc(lm_chunk_t* chunk, ljmm_opt_t* mm_opt);
|
|
void lm_fini_page_alloc(void);
|
|
|
|
/* Misc */
|
|
#ifdef DEBUG
|
|
void dump_page_alloc(FILE* f);
|
|
#endif
|
|
|
|
#endif /*_PAGE_ALLOC_H_*/
|