这个LAB 是上完CMU CSAPP的16-20 LECTURE之后，就可以做了。
csapp 课程观看地址：https://search.bilibili.com/all?keyword=csapp&from_source=banner_search
lab 6 下载地址: http://csapp.cs.cmu.edu/3e/labs.html
找到MALLOC lab, 点击SELF-STUDY HANDOUT
第一个版本是使用了IMPLICT LIST, NEXT_FIT，快速达到83分。（30分钟）
随后实现老师上课说的单HEADER，不要FOOTER的策略，发现并没有很大提高。
随后开始对REALLOC优化，也只能提高到了89分。
从第三部分开始 完整实现了SEG FREE LIST + MEM CHECK（帮助我找到一个链表SIZE ORDER的BUG）从97分上升到了98分。
前置功课
1.看一遍WRITE UP
2.把书上相关章节的代码理解透
3.学习使用GDB
image.png
image.png
image.png
另外的DEBUG神技
image.png
image.png
任务目标
实现自己的 malloc, free, realloc 函数。
我们需要做的是完成在 mm.c 中的以下几个函数
int mm_init(void);
void *malloc(size_t size);
void free(void *ptr);
void *realloc(void *ptr, size_t size);
void mm_checkheap(int);
mm-init：在这里执行所有的初始化操作，包括分配初始的堆区域。注意，必须在这里重新初始化所有的全局变量，并且不要调用 mem.init 函数。成功的话返回 0 ，否则返回 -1
malloc：至少需要分配 size 这么大的空间（可能因为对齐的原因会更大一点，8 byte 对齐），不能超出堆的范围，也不能覆盖其他已分配的区域
free：释放 ptr 指针指向的区域（这个区域必须是已分配的），free(NULL) 什么都不做
realloc：重新分配，根据传入指针的不同，有不同的表现
ptr 为 NULL 时，等同于 malloc(size)
size 为 0 时，等同于 free(ptr)，需要返回 NULL
ptr 不为 NULL 时，一定是指向一个已分配的空间的，就根据新的 size 的大小进行调整，并让 ptr指向新的地址（如果是新地址的话），并且旧的区域应该被释放。另外需要注意的是，需要把原来 block 的值复制过去
mm_checkheap：扫描堆并检查其状态，注意，只有在检测到错误时才输出内容并调用 exit 退出。mm_heapchecker(__Line__); 传入的参数是当前行数，方便大家找到错误位置。
memlib.c 模拟了内存系统，可以调用下面的方法来得到响应的信息：
void *mem_sbrk(int incr)：让堆扩展 incr 个字节，并返回新分配的地址的头指针
void *mem_heap_lo(void)：返回指向堆的第一个字节的指针
void *mem_heap_hi(void)：返回指向堆的最后一个字节的指针
size_t mem_heapsize(void)：返回当前的堆大小
size_t mem_pagesize(void)：返回系统的 page size
head checker 需要做的工作有：
检查堆(implicit list, explicit list, segregated list)
Check epilogue and prologue blocks
Check each block’s address alignment
Check heap boundaries
Check each block’s header and footer: size(minimum size, slignment), previous/net allocate/free bit consistency, header and footer matching each other
Check coalescing: no two consecutive free blocks in the heap
检查 free list(explicit list, segregated list)
All next/previous pointer are consistent (is A’s next pointer points ot B, B’s previous pointer should point to A)
All free list pointers points between mem_heap_lo() and mem_heap_hi()
Count free blocks by iterating through every block and traversing free list by pointers and see if they match
All blocks in each list bucket fall within bucket size range(segregated list)
需要注意的地方：
不能改动 mm.h，但是可以在 mm.c 中添加 static 方法使代码更好理解
mm.c 中不能定义任何全局 array, tree 或 list，但是可以定义全局 struct 和诸如 integer, float 和 pointer 等变量
返回的指针必须是 8-byte 对齐的
编译代码不能有警告
建议先实现 explcit free list
1.使用课本代码
首先把CSAPP 课本上的隐式链表法的代码抄下来，之后需要自己写2个函数
image.png
其中PLACE 这个函数要注意 如果差小于2 * DSIZE的 话，是没必要切割的。因为在这种做法中，最少的块代下也是2 * DSIZE。因为HEAD+FOOTER 花掉一个DISZE，还需要存数据然后按8对齐，所以至少还要一个DSIZE。
static void *find_fit(size_t asize)
{
char *bp = heap_listp;
size_t alloc;
size_t size;
while (GET_SIZE(HDRP(NEXT_BLKP(bp))) > 0) {
bp = NEXT_BLKP(bp);
alloc = GET_ALLOC(HDRP(bp));
if (alloc) continue;
size = GET_SIZE(HDRP(bp));
if (size < asize) continue;
return bp;
}
return NULL;
}
static void place(void *bp, size_t asize)
{
size_t size = GET_SIZE(HDRP(bp));
if ((size - asize) >= (2*DSIZE)) {
PUT(HDRP(bp),PACK(asize,1));
PUT(FTRP(bp),PACK(asize,1));
PUT(HDRP(NEXT_BLKP(bp)),PACK(size - asize,0));
PUT(FTRP(NEXT_BLKP(bp)),PACK(size - asize,0));
} else {
PUT(HDRP(bp),PACK(size,1));
PUT(FTRP(bp),PACK(size,1));
}
}
写完之后跑一下，发现最后2个应该是因为REALLOC 没有更新的原因而没过。
更新REALLOC
void *mm_realloc(void *ptr, size_t size)
{
if (ptr == NULL)
return mm_malloc(size);
if (size == 0) {
mm_free(ptr);
return NULL;
}
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
size = GET_SIZE(HDRP(ptr));
copySize = GET_SIZE(HDRP(newptr));
if (size < copySize)
copySize = size;
memcpy(newptr, ptr, copySize - WSIZE);
mm_free(ptr);
return newptr;
}
第一版最后得分
image.png
2. 尝试使用NEXT-FIT替代FIRST-FIT
跑分结果
image.png
代码改动如下
/*
* mm-naive.c - The fastest, least memory-efficient malloc package.
*
* In this naive approach, a block is allocated by simply incrementing
* the brk pointer. A block is pure payload. There are no headers or
* footers. Blocks are never coalesced or reused. Realloc is
* implemented directly using mm_malloc and mm_free.
*
* NOTE TO STUDENTS: Replace this header comment with your own header
* comment that gives a high level description of your solution.
*/
#include
#include
#include
#include
#include
#include "mm.h"
#include "memlib.h"
/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
/* Team name */
"ateam",
/* First member's full name */
"Harry Bovik",
/* First member's email address */
"bovik@cs.cmu.edu",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
/* Basic constants and macros */
#define WSIZE 4 /* Word and header/footer size (bytes) */
#define DSIZE 8 /* Double word size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */
#define MAX(x, y) ((x) > (y)? (x) : (y))
/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))
/* Read and write a word at address p */
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void *coalesce(void *bp);
static char *heap_listp;
static char *pre_listp;
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* Initialize free block header/footer and the epilogue header */
PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */
/* Coalesce if the previous block was free */
return coalesce(bp);
}
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0); /* Alignment padding */
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
PUT(heap_listp + (3*WSIZE), PACK(0, 1)); /* Epilogue header */
heap_listp += (2*WSIZE);
pre_listp = heap_listp;
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
static void *find_fit(size_t asize)
{
char *bp = pre_listp;
size_t alloc;
size_t size;
while (GET_SIZE(HDRP(NEXT_BLKP(bp))) > 0) {
bp = NEXT_BLKP(bp);
alloc = GET_ALLOC(HDRP(bp));
if (alloc) continue;
size = GET_SIZE(HDRP(bp));
if (size < asize) continue;
return bp;
}
bp = heap_listp;
while (bp != pre_listp) {
bp = NEXT_BLKP(bp);
alloc = GET_ALLOC(HDRP(bp));
if (alloc) continue;
size = GET_SIZE(HDRP(bp));
if (size < asize) continue;
return bp;
}
return NULL;
}
static void place(void *bp, size_t asize)
{
size_t size = GET_SIZE(HDRP(bp));
if ((size - asize) >= (2*DSIZE)) {
PUT(HDRP(bp),PACK(asize,1));
PUT(FTRP(bp),PACK(asize,1));
PUT(HDRP(NEXT_BLKP(bp)),PACK(size - asize,0));
PUT(FTRP(NEXT_BLKP(bp)),PACK(size - asize,0));
} else {
PUT(HDRP(bp),PACK(size,1));
PUT(FTRP(bp),PACK(size,1));
}
pre_listp = bp;
}
/*
* 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)
{
size_t asize; /* Adjusted block size */
size_t extendsize; /* Amount to extend heap if no fit */
char *bp;
/* Ignore spurious requests */
if (size == 0)
return NULL;
/* Adjust block size to include overhead and alignment reqs. */
if (size <= DSIZE)
asize = 2*DSIZE;
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
/* No fit found. Get more memory and place the block */
extendsize = MAX(asize,CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
//int isPre = (pre_listp == bp);
if (prev_alloc && next_alloc) { // Case 1
pre_listp = bp;
return bp;
}
if (prev_alloc && !next_alloc) { /* Case 2 */
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size,0));
}
else if (!prev_alloc && next_alloc) { /* Case 3 */
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
else { /* Case 4 */
size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
pre_listp = bp;
return bp;
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
if (ptr == NULL)
return mm_malloc(size);
if (size == 0)
mm_free(ptr);
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
size = GET_SIZE(HDRP(ptr));
copySize = GET_SIZE(HDRP(newptr));
if (size < copySize)
copySize = size;
memcpy(newptr, ptr, copySize - WSIZE);
mm_free(ptr);
return newptr;
}
3. 尝试使用PPT的方法去掉ALLOC BLOCK的FOOTER
跑分差不多
image.png
/*
* mm-naive.c - The fastest, least memory-efficient malloc package.
*
* In this naive approach, a block is allocated by simply incrementing
* the brk pointer. A block is pure payload. There are no headers or
* footers. Blocks are never coalesced or reused. Realloc is
* implemented directly using mm_malloc and mm_free.
*
* NOTE TO STUDENTS: Replace this header comment with your own header
* comment that gives a high level description of your solution.
*/
#include
#include
#include
#include
#include
#include "mm.h"
#include "memlib.h"
/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
/* Team name */
"ateam",
/* First member's full name */
"Harry Bovik",
/* First member's email address */
"bovik@cs.cmu.edu",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
/* Basic constants and macros */
#define WSIZE 4 /* Word and header/footer size (bytes) */
#define DSIZE 8 /* Double word size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */
#define MAX(x, y) ((x) > (y)? (x) : (y))
#define PREALLOC(x) ((!x) ? 0 : 2)
/* Pack a size and allocated bit into a word */
#define PACK(size, prealloc, alloc) ((size) | (PREALLOC(prealloc)) | (alloc))
/* Read and write a word at address p */
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define GET_PREALLOC(p) (GET(p) & 0x2)
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void *coalesce(void *bp);
inline void set_next_prealloc(void* bp, size_t prealloc);
static char *heap_listp;
static char *pre_listp;
static void *extend_heap(size_t words)
{
char *bp;
size_t size, prealloc;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* Initialize free block header/footer and the epilogue header */
prealloc = GET_PREALLOC(HDRP(bp));
PUT(HDRP(bp), PACK(size,prealloc, 0)); /* Free block header */
PUT(FTRP(bp), PACK(size,prealloc, 0)); /* Free block footer */
PUT(HDRP(NEXT_BLKP(bp)), PACK(0,0, 1)); /* New epilogue header */
/* Coalesce if the previous block was free */
return coalesce(bp);
}
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0); /* Alignment padding */
PUT(heap_listp + (1*WSIZE), PACK(DSIZE,1, 1)); /* Prologue header */
PUT(heap_listp + (2*WSIZE), PACK(DSIZE,1, 1)); /* Prologue footer */
PUT(heap_listp + (3*WSIZE), PACK(0,1, 1)); /* Epilogue header */
heap_listp += DSIZE;
pre_listp = heap_listp;
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
static void *find_fit(size_t asize)
{
char *bp = pre_listp;
size_t alloc;
size_t size;
while (GET_SIZE(HDRP(NEXT_BLKP(bp))) > 0) {
bp = NEXT_BLKP(bp);
alloc = GET_ALLOC(HDRP(bp));
if (alloc) continue;
size = GET_SIZE(HDRP(bp));
if (size < asize) continue;
return bp;
}
bp = heap_listp;
while (bp != pre_listp) {
bp = NEXT_BLKP(bp);
alloc = GET_ALLOC(HDRP(bp));
if (alloc) continue;
size = GET_SIZE(HDRP(bp));
if (size < asize) continue;
return bp;
}
return NULL;
}
static void place(void *bp, size_t asize)
{
size_t size = GET_SIZE(HDRP(bp));
if ((size - asize) >= DSIZE) {
PUT(HDRP(bp),PACK(asize,1,1));
//PUT(FTRP(bp),PACK(asize,1,1));
PUT(HDRP(NEXT_BLKP(bp)),PACK(size - asize,1,0));
PUT(FTRP(NEXT_BLKP(bp)),PACK(size - asize,1,0));
set_next_prealloc(bp,0);
} else {
PUT(HDRP(bp),PACK(size,1,1));
set_next_prealloc(bp,1);
//PUT(FTRP(bp),PACK(size,1,1));
}
pre_listp = bp;
}
/*
* 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)
{
size_t asize; /* Adjusted block size */
size_t extendsize; /* Amount to extend heap if no fit */
char *bp;
/* Ignore spurious requests */
if (size == 0)
return NULL;
/* Adjust block size to include overhead and alignment reqs. */
if (size <= WSIZE)
asize = DSIZE;
else
asize = DSIZE * ((size + (WSIZE) + (DSIZE-1)) / DSIZE);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
/* No fit found. Get more memory and place the block */
extendsize = MAX(asize,CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_PREALLOC(HDRP(bp));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && !next_alloc) { /* Case 2 */
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size,1, 0));
PUT(FTRP(bp), PACK(size,1, 0));
}
else if (!prev_alloc && next_alloc) { /* Case 3 */
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size,1, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size,1, 0));
bp = PREV_BLKP(bp);
}
else if (!prev_alloc && !next_alloc){ /* Case 4 */
size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size,1, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size,1, 0));
bp = PREV_BLKP(bp);
}
set_next_prealloc(bp,0);
pre_listp = bp;
return bp;
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
size_t prealloc = GET_PREALLOC(HDRP(bp));
PUT(HDRP(bp), PACK(size,prealloc, 0));
PUT(FTRP(bp), PACK(size,prealloc, 0));
coalesce(bp);
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
if (ptr == NULL)
return mm_malloc(size);
if (size == 0)
mm_free(ptr);
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
size = GET_SIZE(HDRP(ptr));
copySize = GET_SIZE(HDRP(newptr));
if (size < copySize)
copySize = size;
memcpy(newptr, ptr, copySize - WSIZE);
mm_free(ptr);
return newptr;
}
inline void set_next_prealloc(void* bp, size_t prealloc)
{
size_t size = GET_SIZE(HDRP(NEXT_BLKP(bp)));
size_t alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(NEXT_BLKP(bp)), PACK(size,prealloc,alloc));
}
经过对REALLOC方法做了优化，针对最后2个CASE，代码最终获得了89分。
image.png
看来课本赠送的方法很难上90分了。 下面就要自己实现一把老师上课讲的Segregated Free Lists
4. 实现Segregated Free Lists
在写代码前必须心中要有代码的架子，然后依据骨架来填写代码。
1.首先需要维护一个数组来存Segregated Free Lists
大小依次为{1}{2~3}{4~7}{8~15}...{2048~4095}... 也就是根据2的幂来。然后保证链表的大小有序性。例如第一条链，A是B的successor，B是A的predecessor，A的大小小于等于B
image.png
2.明确ALLOC块结构 和 FREE块结构。根据显示链表法可得。
image.png
那么如果是FREE BLOCK，就会有如下的宏方法。
#define PRED_PTR(ptr) ((void *)(ptr))
#define SUCC_PTR(ptr) ((void *)(ptr) + WSIZE)
#define PRED(ptr) (*(void **)(ptr))
#define SUCC(ptr) (*(void **)(SUCC_PTR(ptr)))
因为多了PTR属性，我们还需要去SET PTR
#define SET_PTR(p, ptr) (*(unsigned int *)(p) = (unsigned int)(ptr))
3. 明确基本算法
3.1 INIT HEAP的时候要初始化seg_free_lists，随后是课本代码
在EXTEND HEAP的时候，拿到FREE块，根据SIZE放进对应的空闲链表。
3.2 MALLOC 的时候，计算ASIZE。随后用右移，来定位到对应的seg_free_list,随后进行循环，找到第一个满足的FREE BLOCK。做PLACE操作。如果没有找到就到下一个seg_free_list去找。全没找到，那么退出循环时；指针应该为NULL，就要EXTEND HEAP。
3.3 FREE, 把对应的块先置为FREE状态。进行coalesce。直接分4种情况考虑。（下面4种CASE 的意义，和课本上一致，不做额外解释）
CASE 1， 需要进行INSERT NODE， return ptr
CASE 2, 合并之后，DELETE后面的NODE，最后INSERT
CASE 3， 删除前面的节点，合并，指针移到之前，INSERT
CASE 4， 删除前后的节点，合并，指针移到之前，INSERT
3.4 REALLOC 算出ASIZE，如果ASIZE 小于原来的块大小，直接返回原来的块。（这种做法在我做小实验的时候，发现UTIL率更高，就是有小的也不切割）
否则检查是否可以将后一个块 或 前一个块吸纳进来。（当然根据WRITES UP 这个优化的REALLOC，可以最后写）
都不行就只能MALLOC ，MEMCPY， 然后FREE。
4. 如何写辅助函数
4.1 INSERT NODE(void *ptr, size_t size)
对SIZE 右移，找到最先能符合要求的链。然后找到大小合适的位置进行插入。
分4个情况，空链插入，开头插入，结尾插入，中间插入。
而链表连接就通过我们之前的宏。举个例子
SET_PTR(PRED_PTR(ptr), pre_ptr);
SET_PTR(SUCC_PTR(pre_ptr), ptr);
4.2 DELETE NODE(void *ptr)
根据PTR取到SIZE，对SIZE 右移，找到最先能符合要求的链。
还是和上面一样分为4种可能性。比如在中间的可以这么写
SET_PTR(SUCC_PTR(PRED(ptr)), SUCC(ptr));
SET_PTR(PRED_PTR(SUCC(ptr)), PRED(ptr));
4.3 PLACE(void *ptr, size_t size)
计算剩余块的大小，小于 2 * DSIZE
直接更新HEADER, FOOTER。
如果SIZE大于一个MAGIC NUMBER 需要放在后面，把前半部分切割出来。
<的话，放在前面。这就需要重新返回BP指针
为什么这样呢？
否则分离原块，但这里要注意这样一种情况（在binary-bal.rep和binary2-bal.rep有体现）：
* 如果每次allocate的块大小按照小、大、小、大的连续顺序来的话，我们的free块将会被“拆”成以下这种结构：
* 其中s代表小的块，B代表大的块
s B s B s B s B
+--+----------+--+----------+-+-----------+-+---------+
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
+--+----------+--+----------+-+-----------+-+---------+
* 这样看起来没什么问题，但是如果程序后来free的时候不是按照”小、大、小、大“的顺序来释放的话就会出现“external fragmentation”
* 例如当程序将大的块全部释放了，但小的块依旧是allocated：
s s s s
+--+----------+--+----------+-+-----------+-+---------+
| | | | | | | | |
| | Free | | Free | | Free | | Free |
| | | | | | | | |
+--+----------+--+----------+-+-----------+-+---------+
* 这样即使我们有很多free的大块可以使用，但是由于他们不是连续的，我们不能将它们合并，如果下一次来了一个大小为B+1的allocate请求
* 我们就还需要重新去找一块Free块
* 与此相反，如果我们根据allocate块的大小将小的块放在连续的地方，将达到开放在连续的地方：
s s s s s s B B B
+--+--+--+--+--+--+----------+------------+-----------+
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
+--+--+--+--+--+--+----------+------------+-----------+
* 这样即使程序连续释放s或者B，我们也能够合并free块，不会产生external fragmentation
* 这里“大小”相对判断是根据binary-bal.rep和binary2-bal.rep这两个文件设置的，我这里在96附近能够达到最优值
*
4. 定了数据结构和算法后，实现void mm_checkheap(int verbose)
参考代码
http://csapp.cs.cmu.edu/3e/ics3/code/vm/malloc/mm.c
image.png
先把架子搭好
/* below code if for check heap invarints */
/*
* mm_checkheap - Check the heap for correctness
*/
void mm_checkheap(int verbose)
{
checkheap(verbose);
}
//heap level
void checkheap(int verbose)
{
char *bp = heap_listp;
if (verbose)
printf("Heap (%p):\n", heap_listp);
if ((GET_SIZE(HDRP(heap_listp)) != DSIZE) || !GET_ALLOC(HDRP(heap_listp)))
printf("Bad prologue header\n");
// block level
checkblock(heap_listp);
int pre_free = 0;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (verbose)
printblock(bp);
int cur_free = checkblock(bp);
if (pre_free && cur_free) {
printf("Contiguous free blocks\n");
}
}
//list level
int i = 0;
for (; i < LIST_MAX; i++) {
if (verbose)
printlist(bp);
checklist(seg_free_lists[i]);
}
if (verbose)
printblock(bp);
if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp))))
printf("Bad epilogue header\n");
}
4.1 实现check block, print block
static void printblock(void *bp)
{
long int hsize, halloc, fsize, falloc;
hsize = GET_SIZE(HDRP(bp));
halloc = GET_ALLOC(HDRP(bp));
fsize = GET_SIZE(FTRP(bp));
falloc = GET_ALLOC(FTRP(bp));
if (hsize == 0) {
printf("%p: EOL\n", bp);
return;
}
printf("%p: header: [%ld:%c] footer: [%ld:%c]\n", bp,
hsize, (halloc ? 'a' : 'f'),
fsize, (falloc ? 'a' : 'f'));
}
static int checkblock(void *bp)
{
//area is aligned
if ((size_t)bp % 8)
printf("Error: %p is not doubleword aligned\n", bp);
//header and footer match
if (GET(HDRP(bp)) != GET(FTRP(bp)))
printf("Error: header does not match footer\n");
size_t size = GET_SIZE(HDRP(bp));
//size is valid
if (size % 8)
printf("Error: %p payload size is not doubleword aligned\n", bp);
return GET_ALLOC(HDRP(bp));
}
4.2 实现check list, print list
static void printlist(void *i, long size)
{
long int hsize, halloc;
for(;i != NULL;i = SUCC(i))
{
hsize = GET_SIZE(HDRP(i));
halloc = GET_ALLOC(HDRP(i));
printf("[listnode %ld] %p: header: [%ld:%c] prev: [%p] next: [%p]\n",
size, i,
hsize, (halloc ? 'a' : 'f'),
PRED(i), SUCC(i));
}
}
static void checklist(void *i, size_t tar)
{
void *pre = NULL;
long int hsize, halloc;
for(;i != NULL;i = SUCC(i))
{
if (PRED(i) != pre) printf("Error: pred point error\n");
if (pre != NULL && SUCC(pre) != i) printf("Error: succ point error\n");
hsize = GET_SIZE(HDRP(i));
halloc = GET_ALLOC(HDRP(i));
if (halloc) printf("Error: list node should be free\n");
if (pre != NULL && (GET_SIZE(HDRP(pre)) > hsize))
printf("Error: list size order error\n");
if (hsize < tar || ((tar != (1<<15)) && (hsize > (tar << 1)-1)))
printf("Error: list node size error\n");
pre = i;
}
}
5.最终代码实现
image.png
使用DEBUG 模式 ， CHECK HEAP， 发现链表大小的顺序有错。虽然也能过。
image.png
修复了这个BUG后
image.png
/*
* mm-naive.c - The fastest, least memory-efficient malloc package.
*
* In this naive approach, a block is allocated by simply incrementing
* the brk pointer. A block is pure payload. There are no headers or
* footers. Blocks are never coalesced or reused. Realloc is
* implemented directly using mm_malloc and mm_free.
*
* NOTE TO STUDENTS: Replace this header comment with your own header
* comment that gives a high level description of your solution.
*/
#include
#include
#include
#include
#include
#include "mm.h"
#include "memlib.h"
/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
/* Team name */
"ateam",
/* First member's full name */
"Harry Bovik",
/* First member's email address */
"bovik@cs.cmu.edu",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
#define DEBUG 1
/* If you want debugging output, use the following macro. When you hand
* in, remove the #define DEBUG line. */
#ifdef DEBUG
# define DBG_PRINTF(...) printf(__VA_ARGS__)
# define CHECKHEAP(verbose) mm_checkheap(verbose)
#else
# define DBG_PRINTF(...)
# define CHECKHEAP(verbose)
#endif
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define LISTMAX 16
/* Basic constants and macros */
#define WSIZE 4 /* Word and header/footer size (bytes) */
#define DSIZE 8 /* Double word size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */
#define INITCHUNKSIZE (1<<6)
#define MAX(x, y) ((x) > (y)? (x) : (y))
#define MIN(x, y) ((x) < (y)? (x) : (y))
/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))
/* Read and write a word at address p */
#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))
/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
/* for explict linkedlist */
#define PRED_PTR(ptr) ((char *)(ptr))
#define SUCC_PTR(ptr) ((char *)(ptr) + WSIZE)
#define PRED(ptr) (*(char **)(ptr))
#define SUCC(ptr) (*(char **)(SUCC_PTR(ptr)))
#define SET_PTR(p, ptr) (*(unsigned int *)(p) = (unsigned int)(ptr))
static void *extend_heap(size_t words);
static void *place(void *bp, size_t asize);
static void *coalesce(void *bp);
static void insert_node(void *bp, size_t size);
static void delete_node(void *bp);
static size_t get_asize(size_t size);
static void *realloc_coalesce(void *bp,size_t newSize,int *isNextFree);
static void realloc_place(void *bp,size_t asize);
void checkheap(int verbose);
void mm_checkheap(int verbose);
void *seg_free_lists[LISTMAX];
char *heap_listp;
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* Initialize free block header/footer and the epilogue header */
PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */
/* Coalesce if the previous block was free include insert*/
return coalesce(bp);
}
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)//done
{
int i;
/* initiliaze seg_free_lists */
for (i = 0; i < LISTMAX; i++) {
seg_free_lists[i] = NULL;
}
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0); /* Alignment padding */
PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
PUT(heap_listp + (3*WSIZE), PACK(0, 1)); /* Epilogue header */
heap_listp += (2*WSIZE);
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(INITCHUNKSIZE/WSIZE) == NULL)
return -1;
CHECKHEAP(1);
return 0;
}
static void *place(void *bp, size_t asize)//done
{
size_t size = GET_SIZE(HDRP(bp));
delete_node(bp);
if ((size - asize) < (2*DSIZE)) {
PUT(HDRP(bp),PACK(size,1));
PUT(FTRP(bp),PACK(size,1));
} else if (asize >= 96) {
PUT(HDRP(bp),PACK(size - asize,0));
PUT(FTRP(bp),PACK(size - asize,0));
PUT(HDRP(NEXT_BLKP(bp)),PACK(asize,1));
PUT(FTRP(NEXT_BLKP(bp)),PACK(asize,1));
insert_node(bp,size - asize);
return NEXT_BLKP(bp);
} else {
PUT(HDRP(bp),PACK(asize,1));
PUT(FTRP(bp),PACK(asize,1));
PUT(HDRP(NEXT_BLKP(bp)),PACK(size - asize,0));
PUT(FTRP(NEXT_BLKP(bp)),PACK(size - asize,0));
insert_node(NEXT_BLKP(bp),size - asize);
}
return bp;
}
static void insert_node(void *bp, size_t size)
{
int tar = 0;
size_t j;
for (j = size; (j > 1) && (tar < LISTMAX - 1); ) {
j >>= 1;
tar++;
}
char *i = seg_free_lists[tar];
char *pre = NULL;
while ((i != NULL) && (size > GET_SIZE(HDRP(i)))) {
pre = i;
i = SUCC(i);
}// i should be first node size >= input size
if (i == NULL && pre == NULL) {//empty list
seg_free_lists[tar] = bp;
SET_PTR(PRED_PTR(bp), NULL);
SET_PTR(SUCC_PTR(bp), NULL);
} else if (i == NULL && pre != NULL) {// add the last
SET_PTR(PRED_PTR(bp), pre);
SET_PTR(SUCC_PTR(bp), NULL);
SET_PTR(SUCC_PTR(pre), bp);
} else if (pre == NULL) {// add the first
seg_free_lists[tar] = bp;
SET_PTR(PRED_PTR(i), bp);
SET_PTR(SUCC_PTR(bp), i);
SET_PTR(PRED_PTR(bp), NULL);
} else {
SET_PTR(PRED_PTR(bp), pre);
SET_PTR(SUCC_PTR(bp), i);
SET_PTR(PRED_PTR(i), bp);
SET_PTR(SUCC_PTR(pre), bp);
}
}
static void delete_node(void *bp)//done
{
size_t size = GET_SIZE(HDRP(bp)), j;
int tar = 0;
for (j = size; (j > 1) && (tar < LISTMAX - 1); j >>= 1) {
tar++;
}
if (PRED(bp) == NULL) { // first one
seg_free_lists[tar] = SUCC(bp);
if (SUCC(bp) != NULL)
SET_PTR(PRED_PTR(SUCC(bp)), NULL);
} else if (SUCC(bp) == NULL) { //last one
SET_PTR(SUCC_PTR(PRED(bp)), NULL);
} else {
SET_PTR(SUCC_PTR(PRED(bp)), SUCC(bp));
SET_PTR(PRED_PTR(SUCC(bp)), PRED(bp));
}
}
/*
* 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)
{
size_t asize, search; /* Adjusted block size */
size_t extendsize; /* Amount to extend heap if no fit */
char *bp = NULL;
/* Ignore spurious requests */
if (size == 0)
return NULL;
/* Adjust block size to include overhead and alignment reqs. */
asize = get_asize(size);
search = asize;
int target;
for (target = 0; target < LISTMAX; target++, search >>= 1) {
/* find target seg_free_list*/
if ((search > 1) || (seg_free_lists[target] == NULL)) continue;
char *i = seg_free_lists[target];
for(;i != NULL;i = SUCC(i))
{
if (GET_SIZE(HDRP(i)) < asize) continue;
bp = i;
break;
}
if (bp != NULL) break;
}
if (bp == NULL) {
/* No fit found. Get more memory and place the block */
extendsize = MAX(asize,CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
}
bp = place(bp, asize);
CHECKHEAP(1);
return bp;
}
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && !next_alloc) { /* Case 2 */
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
delete_node(NEXT_BLKP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size,0));
}
else if (!prev_alloc && next_alloc) { /* Case 3 */
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
delete_node(PREV_BLKP(bp));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
else if (!prev_alloc && !next_alloc){ /* Case 4 */
size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
GET_SIZE(FTRP(NEXT_BLKP(bp)));
delete_node(PREV_BLKP(bp));
delete_node(NEXT_BLKP(bp));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
insert_node(bp,size);
return bp;
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
CHECKHEAP(1);
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
if (ptr == NULL)
return mm_malloc(size);
if (size == 0) {
mm_free(ptr);
return NULL;
}
void *newptr;
size_t asize, oldsize;
oldsize = GET_SIZE(HDRP(ptr));
asize = get_asize(size);
if(oldsize { int isnextFree; char *bp = realloc_coalesce(ptr,asize,&isnextFree); if(isnextFree==1){ /*next block is free*/ realloc_place(bp,asize); } else if(isnextFree ==0 && bp != ptr){ /*previous block is free, move the point to new address,and move the payload*/ memcpy(bp, ptr, size); realloc_place(bp,asize); }else{ /*realloc_coalesce is fail*/ newptr = mm_malloc(size); memcpy(newptr, ptr, size); mm_free(ptr); CHECKHEAP(1); return newptr; } CHECKHEAP(1); return bp; } else if(oldsize>asize) {/*just change the size of ptr*/ realloc_place(ptr,asize); CHECKHEAP(1); return ptr; } CHECKHEAP(1); return ptr; } static size_t get_asize(size_t size) { size_t asize; if(size <= DSIZE){ asize = 2*(DSIZE); }else{ asize = ALIGN(size + DSIZE); } return asize; } static void *realloc_coalesce(void *bp,size_t newSize,int *isNextFree) { size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); size_t size = GET_SIZE(HDRP(bp)); *isNextFree = 0; /*coalesce the block and change the point*/ if(prev_alloc && !next_alloc) { size += GET_SIZE(HDRP(NEXT_BLKP(bp))); if(size>=newSize) { delete_node(NEXT_BLKP(bp)); PUT(HDRP(bp), PACK(size,1)); PUT(FTRP(bp), PACK(size,1)); *isNextFree = 1; } } else if(!prev_alloc && next_alloc) { size += GET_SIZE(HDRP(PREV_BLKP(bp))); if(size>=newSize) { delete_node(PREV_BLKP(bp)); PUT(FTRP(bp),PACK(size,1)); PUT(HDRP(PREV_BLKP(bp)),PACK(size,1)); bp = PREV_BLKP(bp); } } else if(!prev_alloc && !next_alloc) { size +=GET_SIZE(FTRP(NEXT_BLKP(bp)))+ GET_SIZE(HDRP(PREV_BLKP(bp))); if(size>=newSize) { delete_node(PREV_BLKP(bp)); delete_node(NEXT_BLKP(bp)); PUT(FTRP(NEXT_BLKP(bp)),PACK(size,1)); PUT(HDRP(PREV_BLKP(bp)),PACK(size,1)); bp = PREV_BLKP(bp); } } return bp; } static void realloc_place(void *bp,size_t asize) { size_t csize = GET_SIZE(HDRP(bp)); /* if((csize-asize)>=(2*DSIZE)) { PUT(HDRP(bp),PACK(asize,1)); PUT(FTRP(bp),PACK(asize,1)); bp = NEXT_BLKP(bp); PUT(HDRP(bp),PACK(csize-asize,0)); PUT(FTRP(bp),PACK(csize-asize,0)); coalesce(bp); } else { PUT(HDRP(bp),PACK(csize,1)); PUT(FTRP(bp),PACK(csize,1)); } */ PUT(HDRP(bp),PACK(csize,1)); PUT(FTRP(bp),PACK(csize,1)); } /* below code if for check heap invarints */ static void printblock(void *bp) { long int hsize, halloc, fsize, falloc; hsize = GET_SIZE(HDRP(bp)); halloc = GET_ALLOC(HDRP(bp)); fsize = GET_SIZE(FTRP(bp)); falloc = GET_ALLOC(FTRP(bp)); if (hsize == 0) { printf("%p: EOL\n", bp); return; } printf("%p: header: [%ld:%c] footer: [%ld:%c]\n", bp, hsize, (halloc ? 'a' : 'f'), fsize, (falloc ? 'a' : 'f')); } static int checkblock(void *bp) { //area is aligned if ((size_t)bp % 8) printf("Error: %p is not doubleword aligned\n", bp); //header and footer match if (GET(HDRP(bp)) != GET(FTRP(bp))) printf("Error: header does not match footer\n"); size_t size = GET_SIZE(HDRP(bp)); //size is valid if (size % 8) printf("Error: %p payload size is not doubleword aligned\n", bp); return GET_ALLOC(HDRP(bp)); } static void printlist(void *i, long size) { long int hsize, halloc; for(;i != NULL;i = SUCC(i)) { hsize = GET_SIZE(HDRP(i)); halloc = GET_ALLOC(HDRP(i)); printf("[listnode %ld] %p: header: [%ld:%c] prev: [%p] next: [%p]\n", size, i, hsize, (halloc ? 'a' : 'f'), PRED(i), SUCC(i)); } } static void checklist(void *i, size_t tar) { void *pre = NULL; long int hsize, halloc; for(;i != NULL;i = SUCC(i)) { if (PRED(i) != pre) printf("Error: pred point error\n"); if (pre != NULL && SUCC(pre) != i) printf("Error: succ point error\n"); hsize = GET_SIZE(HDRP(i)); halloc = GET_ALLOC(HDRP(i)); if (halloc) printf("Error: list node should be free\n"); if (pre != NULL && (GET_SIZE(HDRP(pre)) > hsize)) printf("Error: list size order error\n"); if (hsize < tar || ((tar != (1<<15)) && (hsize > (tar << 1)-1))) printf("Error: list node size error\n"); pre = i; } } /* * mm_checkheap - Check the heap for correctness */ void mm_checkheap(int verbose) { checkheap(verbose); } //heap level void checkheap(int verbose) { char *bp = heap_listp; if (verbose) printf("Heap (%p):\n", heap_listp); if ((GET_SIZE(HDRP(heap_listp)) != DSIZE) || !GET_ALLOC(HDRP(heap_listp))) printf("Bad prologue header\n"); // block level checkblock(heap_listp); int pre_free = 0; for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { if (verbose) printblock(bp); int cur_free = checkblock(bp); //no contiguous free blocks if (pre_free && cur_free) { printf("Contiguous free blocks\n"); } } //list level int i = 0, tarsize = 1; for (; i < LISTMAX; i++) { if (verbose) printlist(seg_free_lists[i], tarsize); checklist(seg_free_lists[i],tarsize); tarsize <<= 1; } if (verbose) printblock(bp); if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp)))) printf("Bad epilogue header\n"); }