本系列文章為中國科學技術大學計算機專業學科基礎課《計算機系統》布置的實驗，上課所用教材和内容為黑書CSAPP，當時花費很大精力和彎路，現來總結下各個實驗，本文章為第五個實驗——動态記憶體配置設定（Malloc lab）。
一、實驗名稱：Malloc lab
二、實驗學時： 3
三、實驗内容和目的：
1. 目的
/afs/cs/project/ics/im/labs/malloclab/
在該實驗中，需要用C語言實作一個動态存儲配置設定器（dynamic storage allocater）。需要實作malloc、free、realloc等功能。當然不僅要正确的實作相關功能也要滿足速度效率等要求。
2. 步驟
tar xvf malloclab-handout.tar解壓檔案
我們需要修改的唯一檔案是mm.c，包含如下幾個需要實作的函數
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size)
3. 解釋
mm_init:在調用mm_malloc，mm_realloc或mm_free之前，調用mm_init進行初始化，正确傳回0。
mm_malloc：在堆區域配置設定指定大小的塊，配置設定的空間，傳回的指針應該是8位元組對齊的
mm_free:釋放指針指向的block
mm_realloc:傳回指向一個大小為size的區域指針，滿足一下條件：
if ptr is NULL, the call is equivalent to mm_malloc(size);
if size is equal to zero, the call is equivalent to mm_free(ptr);
if ptr is not NULL：先按照size指定的大小配置設定空間，将原有資料從頭到尾拷貝到新配置設定的記憶體區域，而後釋放原來ptr所指記憶體區域
4. 可以調用的函數
void *mem_sbrk(int incr): Expands the heap by incr bytes, where incr is apositive non-zero integer and returns a generic pointer to the first byte of the newly allocated heap area.
void *mem_heap_lo(void):Returns a generic pointer to the first byte in the heap.
void *mem_heap_hi(void): Returns a generic pointer to the last byte in the heap.
size_t mem_heapsize(void):Returns the current size of the heap in bytes.
size_t mem_pagesize(void): Returns the system’s page size in bytes (4K onLinux systems).
5. 驗證方法
mdriver.c：負責測試mm.c的正确性,空間使用率和吞吐量
-f <tracefile>: -f後添加一些trace file來測試我們實作的函數
-V:列印出診斷資訊
./mdriver -V -f short1-bal.rep
6. 程式設計規則
不能改變mm.c中函數接口
不能直接調用任何記憶體管理的庫函數和系統函數malloc, calloc, free, realloc, sbrk, brk
不能定義任何全局或者靜态複合資料結構如arrays, structs, trees，允許使用integers, floats, and pointers等簡單資料類型
隻要送出mm.c檔案
四、實驗步驟及結果：
1. mm_init函數
空閑塊的組織方法-Segregated free list方法
segregated free list 中大小類的分類方法如下，并且将該list表放在heap的頭部，通過序言塊将它與資料隔離。在每一個大小類中，空閑塊按照size由大到小排序。
*
* mm_init - initialize the malloc package.
* The return value should be -1 if there was a problem in performing the initialization, 0 otherwise
*/
int mm_init(void)
{
int listnumber;
char *heap;
/* 初始化分離空閑連結清單 */
for (listnumber = 0; listnumber < LISTMAX; listnumber++)
{
segregated_free_lists[listnumber] = NULL;
}
/* 初始化堆 */
if ((long)(heap = mem_sbrk(4 * WSIZE)) == -1)
return -1;
/* 這裡的結構參見本文上面的“堆的起始和結束結構” */
PUT(heap, 0);
PUT(heap + (1 * WSIZE), PACK(DSIZE, 1));
PUT(heap + (2 * WSIZE), PACK(DSIZE, 1));
PUT(heap + (3 * WSIZE), PACK(0, 1));
/* 擴充堆 */
if (extend_heap(INITCHUNKSIZE) == NULL)
return -1;
return 0;
}
空閑塊查找方法 - best fit
因為同一大小類中空閑塊由小到大排序，是以查找是第一個合适的就是最适配的mm_malloc函數。
2.mm_malloc函數
/*
* mm_malloc - Allocate a block by incrementing the brk pointer.
* Always allocate a block whose size is a multiple of the alignment.
*/
void *mm_malloc(size_t size)
{
if (size == 0)
return NULL;
/* 記憶體對齊 */
if (size <= DSIZE)
{
size = 2 * DSIZE;
}
else
{
size = ALIGN(size + DSIZE);
}
int listnumber = 0;
size_t searchsize = size;
void *ptr = NULL;
while (listnumber < LISTMAX)
{
/* 尋找對應鍊 */
if (((searchsize <= 1) && (segregated_free_lists[listnumber] != NULL)))
{
ptr = segregated_free_lists[listnumber];
/* 在該鍊尋找大小合适的free塊 */
while ((ptr != NULL) && ((size > GET_SIZE(HDRP(ptr)))))
{
ptr = PRED(ptr);
}
/* 找到對應的free塊 */
if (ptr != NULL)
break;
}
searchsize >>= 1;
listnumber++;
}
/* 沒有找到合适的free塊，擴充堆 */
if (ptr == NULL)
{
if ((ptr = extend_heap(MAX(size, CHUNKSIZE))) == NULL)
return NULL;
}
/* 在free塊中allocate size大小的塊 */
ptr = place(ptr, size);
return ptr;
}
3. mm_free函數
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *ptr)
{
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
/* 插入分離空閑連結清單 */
insert_node(ptr, size);
/* 注意合并 */
coalesce(ptr);
}
4. mm_realloc函數
mm_realloc 改進：
對于請求的newsize>原始的oldsize這種情況，我們将運用類似coalesce中的方法，先去檢查前後是否有空閑塊，并是否滿足前後空閑塊和目前已配置設定的空閑塊size相加大于newsize，如果是則合并，不需要再重新請求空閑塊。如果不行，則需要重新mm_malloc一塊新的空間。
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
void *new_block = ptr;
int remainder;
if (size == 0)
return NULL;
/* 記憶體對齊 */
if (size <= DSIZE)
{
size = 2 * DSIZE;
}
else
{
size = ALIGN(size + DSIZE);
}
/* 如果size小于原來塊的大小，直接傳回原來的塊 */
if ((remainder = GET_SIZE(HDRP(ptr)) - size) >= 0)
{
return ptr;
}
/* 否則先檢查位址連續下一個塊是否為free塊或者該塊是堆的結束塊，因為我們要盡可能利用相鄰的free塊，以此減小“external fragmentation” */
else if (!GET_ALLOC(HDRP(NEXT_BLKP(ptr))) || !GET_SIZE(HDRP(NEXT_BLKP(ptr))))
{
/* 即使加上後面連續位址上的free塊空間也不夠，需要擴充塊 */
if ((remainder = GET_SIZE(HDRP(ptr)) + GET_SIZE(HDRP(NEXT_BLKP(ptr))) - size) < 0)
{
if (extend_heap(MAX(-remainder, CHUNKSIZE)) == NULL)
return NULL;
remainder += MAX(-remainder, CHUNKSIZE);
}
/* 删除剛剛利用的free塊并設定新塊的頭尾 */
delete_node(NEXT_BLKP(ptr));
PUT(HDRP(ptr), PACK(size + remainder, 1));
PUT(FTRP(ptr), PACK(size + remainder, 1));
}
/* 沒有可以利用的連續free塊，而且size大于原來的塊，這時隻能申請新的不連續的free塊、複制原塊内容、釋放原塊 */
else
{
new_block = mm_malloc(size);
memcpy(new_block, ptr, GET_SIZE(HDRP(ptr)));
mm_free(ptr);
}
return new_block;
}
5.實驗結果
測試用例1：99分
測試用例2：93分