Malloc Lab
在这个lab中，要求一步步实现对heap分配内存的管理实现。在第一部分中，checkpoint只要求实现速度够快的malloc，第二部分的final version中，通过删除footer，实现对internal fragment的减少。
First Part
在第一部分中，我们将实现：
- free block的linked list
- 回收内存free的coalesce
- 不同大小区间的多个链表链接的free block
首先，先需要来认识一些基本的常量的意义。
static const size_t wsize = sizeof(word_t);
wsize = 8 bytes 的数据大小单位是malloc lab中数据的最小单位。
static const size_t dsize = 2 * wsize;
dsize = 16 bytes 是两倍的wsize。可以被看作是一个header，一个footer。
static const size_t chunksize = (1 << 12);
chunksize是当剩余最大free block大小小于需要分配的block asize的大小时，extend的heap内存大小。
static const word_t alloc_mask = 0x1;
alloc_mask被用来识别一个block是不是被分配了，分配alloc置为1，free = 0
static const word_t size_mask = ~(word_t)0xF;
size_mask 被用来获取一个block的大小。
在认识了基本的常量之后，我们开始设计两种最基本的数据结构，block和free block
typedef struct block {
/** @brief Header contains size + allocation flag */
word_t header;
/**
* @brief A pointer to the block payload.*
*/
char payload[0];
} block_t;block存在两个field， header和payload。在sturct中并没有显式的标明footer，footer实际上是payload的最后一个word_t。通过这个函数我们能够更清楚的理解：
static word_t *header_to_footer(block_t *block) {
dbg_requires(get_size(block) != 0 &&
"Called header_to_footer on the epilogue block");
return (word_t *)(((char *)block->payload) + get_size(block) - dsize);
}char是一个byte所以通过将payload地址向后寻找存储数据payload大小的位移后，向前移动一个dsize
/** @brief Represents free block to be allocated */
typedef struct free_block {
/** @brief Header contains size + allocation flag */
word_t header;
/** @brief point to the previous block*/
word_t ptr_prev;
/** @brief point to the next block*/
word_t ptr_next;
} free_block_t;free_block是一个链表节点的结构。向前指向前一个free_block，向后指向后面一个free_block。header中存放了size，是否alloc的信息。free_block中同样需要footer，同样也没有显式的说明。因为在coalesce阶段需要获得物理上连续的block是不是free_block。于是在向前寻找block的时候需要能够通过前一个block的footer获得前一个block的header位置。
接下来，我们开始实现malloc第一部分的核心函数：
- mm_init：初始化heap
- malloc：分配block
- free：回收blcok
- coalesce_block：在split， free操作后，将相邻free_block合并，减少external fragment
- extend_heap：无合适大小free_block时extend新的chunk of heap.
- split_block_seg_list：分配block的时候，按需分配大小，将剩余的free_block分离开存放在相应的seg_list中。
- find_first_fit：寻找链表中第一个合适的free_block。
mm_init()
bool mm_init(void) {
// initialize the seg list
seg_list.list_num = 8;
seg_list.threshlds[0] = min_block_size;
seg_list.threshlds[1] = 64;
seg_list.threshlds[2] = 128;
seg_list.threshlds[3] = 256;
seg_list.threshlds[4] = 512;
seg_list.threshlds[5] = 2048;
seg_list.threshlds[6] = 4096;
seg_list.threshlds[7] = 8192;
for(int i = 0; i < seg_list.list_num; ++i){
seg_list.heads[i] = NULL;
}
// Create the initial empty heap
word_t *start = (word_t *)(mem_sbrk(2 * wsize));
if (start == (void *)-1) {
return false;
}
start[0] = pack(0, true); // Heap prologue (block footer)
start[1] = pack(0, true); // Heap epilogue (block header)
// Heap starts with first "block header", currently the epilogue
heap_start = (block_t *)&(start[1]);
// Extend the empty heap with a free block of chunksize bytes
if (extend_heap(chunksize) == NULL) {
return false;
}
if(vbs)printf("mm_init success...\n");
dbg_requires(mm_checkheap(__LINE__));
return true;
}在初始化中，干了一系列事情。
typedef struct {
block_t* heads[32];
size_t threshlds[32];
int list_num;
} segmentation_list_t;static segmentation_list_t seg_list;
seg_list是一个static指针数组，包含一系列不同大小free_block的链表表头。在mm_init中我们首次规定他们存储free_block的区间大小。
之后，初始化内存如图。当前只有一个free_block，size = 4096。
malloc()
asize = round_up(size + 2*dsize, dsize);
输入存放数据需要的size，但是我们需要手动帮他加上header，footer的空间。
block = find_first_fit(asize);
找到合适的free_blcok，如果找不到，就extend
split_block_seg_list(block, asize);
管理好剩下的free_block加入seg_list。
完成malloc
free()
write_block(block, size, false);
将block标记成free_block
coalesce_block(block);
合并回收free_block
coalesce_block()
static block_t *coalesce_block(block_t *block) {
block_t *pys_prev_block = find_prev(block);
block_t *pys_next_block = find_next(block);
size_t size = get_size(block);
bool pys_prev_alloc = get_alloc(pys_prev_block);
bool pys_next_alloc = get_alloc(pys_next_block);
if(pys_prev_alloc && pys_next_alloc){
if(vbs)printf("A\n");
insert_some_seg_list(block);
return block;
}else if (pys_prev_alloc && !pys_next_alloc)
{
if(vbs)printf("B\n");
size += get_size(pys_next_block);
remove_some_seg_list(pys_next_block);
write_block(block, size, false);
insert_some_seg_list(block);
}else if (!pys_prev_alloc && pys_next_alloc)
{
if(vbs)printf("C\n");
size += get_size(pys_prev_block);
remove_some_seg_list(pys_prev_block);
block = pys_prev_block;
write_block(block, size, false);
insert_some_seg_list(block);
}else{
if(vbs)printf("D\n");
size += get_size(pys_prev_block) + get_size(pys_next_block);
remove_some_seg_list(pys_prev_block);
remove_some_seg_list(pys_next_block);
block = pys_prev_block;
write_block(block, size, false);
insert_some_seg_list(block);
}
return block;
}合并前，先需要判断前后的block是不是可以合并的free_block。之后进行链表的移除，加入操作。
extend_heap()
size = round_up(size, dsize);
对需要扩展的大小对齐取整。
write_block(block, size, false);
标记新block为free_block
block_t *block_next = find_next(block);
write_epilogue(block_next);
添加下一个header作为epilogue.
block = coalesce_block(block);
合并新的free_block，添加到合适的seg_list中。
split_block_seg_list()
static void split_block_seg_list(block_t *block, size_t asize){
size_t size = get_size(block);
size_t remainder_size = size-asize;
if(remainder_size>=min_block_size){
remove_some_seg_list(block);
write_block(block, asize, true);
block_t *remainder_block = find_next(block);
write_block(remainder_block, remainder_size, false);
insert_some_seg_list(remainder_block);
}else{
remove_some_seg_list(block);
write_block(block, size, true);
}
}注意，分配block标记header为占用alloc状态写在了split_block_seg_list()函数的最后
find_first_fit
static block_t *find_first_fit(size_t asize) {
block_t *block;
int seg_idx = fit_which_seg(asize);
block_t *seg_head = seg_list.heads[seg_idx];
if(seg_head == NULL){ // The seg list of good size is empty
for(int i = seg_idx+1; i < seg_list.list_num; i++){
if(seg_list.heads[i] != NULL){ // Search from small to big
seg_head = seg_list.heads[i];
if(vdbg)printf("Fund another head at seg_idx[%d](size=%d):%llx", i, (int)get_threshld(i), (unsigned long long)&(seg_head->header));
break;
}
}
}
for(block = seg_head; block != NULL; block = get_list_next(block)){
if(!(get_alloc(block)) && (get_size(block)>=asize)){
return block;
}
}
return NULL; // no fit found
}此处注意，如果在size所在的seg_list区间内没有找到合适大小的block，需要在其他的seg_list中寻找，而不是直接返回NULL；
Second Part
在第二部分，我们将通过删除footer来减少internal fragment。
typedef struct block {
/** @brief Header contains size + allocation flag
* normal block:
* | size | x | mini | prev_alloc | alloc |
* | 63-4th:60bits| 3th:1bit |2th:1bit| 1th:1bit |0th:1bit|
* | | | 0 | | |
* mini block:
* | prev_address | x | mini | prev_alloc | alloc |
* | 63-4th:60bits| 3th:1bit |2th:1bit| 1th:1bit |0th:1bit|
* | | | 1 | | |
*/
word_t header;
/**
* @brief A pointer to the block payload.*
*/
char payload[0];
} block_t;
/** @brief Represents free block to be allocated */
typedef struct free_block {
/** @brief Header contains size + allocation flag
* normal block:
* | size | x | mini | prev_alloc | alloc |
* | 63-4th:60bits| 3th:1bit |2th:1bit| 1th:1bit |0th:1bit|
* | | | | | |
* mini block:
* | prev_address | x | mini | prev_alloc | alloc |
* | 63-4th:60bits| 3th:1bit |2th:1bit| 1th:1bit |0th:1bit|
* | | | | | |
*/
word_t header;
/** @brief point to the previous block*/
block_t *ptr_prev;
/** @brief point to the next block*/
block_t *ptr_next;
} free_block_t;在第一部分中，并没有直接显式的标出footer，因为这样可以便于删除footer的结构延续到第二部分。去除了footer之后，通过在header中标记上一个block是不是free_block就可以实现coalesce。同时为了进一步减少internal fragment，在header中标记mini，来区分普通block和mini block。注意，这里的mini指的是，内存连续的前一个block是否是mini的。引入如下常量
/** @brief Minimum block size (bytes) 16 bytes */
static const size_t min_block_size = dsize;
/** prev_alloc_mask is to find out the second last bit of the value to see whether prev alloc*/
static const word_t prev_alloc_mask = 0x1<<1;
/** prev_alloc_mask is to find out the second last bit of the value to see whether prev alloc*/
static const word_t mini_block_mask = 0x1<<2;同时，mini_block的free_block也做如下区别
typedef struct mini_free_block {
word_t header;
block_t *ptr_next;
} mini_free_block_t;所以一个mini_free_block是一个单向链表，因为没有空间给他一个ptr_prev指向前一个节点了。
对block结构的改动首先改变了标记站用block的实现逻辑。
static void write_block(block_t *block, size_t size, bool alloc) {
dbg_requires(block != NULL);
dbg_requires(size > 0);
bool prev_alloc = get_prev_alloc(block); // get the status of prev alloc
bool prev_mini = get_prev_mini(block); // get the status of prev mini
block->header = pack(size, alloc); // update the header
write_block_prev_alloc(block,
prev_alloc); // remain the prev allocation status
write_block_prev_mini(block, prev_mini); // remain the prev miniblock status
if (alloc == false &&
(size > min_block_size)) { // write footer if block free
word_t *footerp = header_to_footer(block);
*footerp = pack(size, alloc);
}
}其他的函数也要相应的改变标记的逻辑，在coalese中
// update the header's previous alloc to true
write_block_prev_alloc(block, true);
// update the next block's mini status
write_block_prev_mini(find_next(block), size == min_block_size);
// mark the next block's previous alloc status as false
write_block_prev_alloc(find_next(block), false);同时，如果前一个是mini，那么直接向前16bytes。如果前一个不是mini，且前一个没有被alloc，那么找到前一个block的footer，之后得到前一个的size，最后向前找到block的header。
因为mini_free_block是单向链表，所以在删除一个mini_free_block节点的时候，不可避免的会引入O(N)。
if (seg_idx == 0) {
dbg_requires(get_size(block) == min_block_size &&
"insert first seg list should be size 16");
// O(N) search
block_t *prev_block;
for (prev_block = seg_list.heads[0]; prev_block != NULL;
prev_block = get_list_next(prev_block)) {
if (&prev_block->header == &block->header) { // block found at head
seg_list.heads[0] = NULL;
break;
} else if (&(get_list_next(prev_block)->header) == &block->header) {
set_list_next(prev_block, NULL);
b2mf(block)->ptr_next = NULL;
break;
}
}
}至此，Malloc Lab完成。