CSAPP Malloc Lab
最近准备研究堆题，于是打算把 CSAPP 的 malloc lab 给完成了，记录一下知识点。
为什么要使用动态内存分配
虽然可以使用低级的 mmap 和 munmap 函数来创建和删除虚拟内存的区域，但是当程序运行时需要额外虚拟内存时，用动态内存分配器（dynamic memory allocator)更方便，也有更好的可移植性。
什么是动态内存分配器
动态内存分配器维护着一个进程的虚拟内存区域，称为堆（heap）（见下图）。它紧接在未初始化的数据区域（.bss段）后开始，并向高地址增长。 对于每个进程，内核维护着一个变量 brk，它指向堆的顶部。
分配器将堆视为一组不同大小的块（block）的集合来维护。每个块都是一块连续的虚拟内存，要么是已分配的，要么是空闲的。已分配的块显式地保留为供应用程序使用。空闲块保持空闲，直到它显式地被应用所分配。一个已分配的块保持已分配状态，直到它被释放。
函数定义
malloc
C 标准库提供了一个函数名为 malloc 显式内存分配器。程序通过调用 malloc 函数来从堆中分配块。
#include <stdlib.h>
/* 返回值:若成功则返回已分配块的指针，出错返回 NULL */
void *malloc(size_t size);
malloc 函数返回一个指针，指向大小为至少 size 字节的内存块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。实际中，对齐依赖于编译代码在 32 位模式（gcc -m32）还是 64 位模式中运行。在 32 位模式中，malloc 返回的块的地址总是 8 的倍数。在 64 位模式中，该地址总是 16 的倍数。
sbrk
sbrk 函数通过将内核的 brk 指针增加 incr 来扩展和收缩堆。如果成功，它就返回brk 的旧值，否则，它就返回 -1，并将 errono 设置为 ENOMEM ，如果 incr 为零， sbrk 就返回 brk 的当前值。
#include <stdlib.h>
/* 返回值：若成功则为旧的brk指针，出错返回 -1 */
void *sbrk(intptr_t incr);
free
程序通过调用 free 函数来释放已分配的堆块。
#include <stdlib.h>
void free(void *ptr);
ptr 参数必须指向一个从 malloc、calloc 或者 realloc 获得的已分配块的起始位置。如果不是，那么 free 的行为就是未定义的。更糟的是，既然它什么都不返回，free就不会告诉应用出现了错误。
分配器的实现
实现一：Implicit Free List（隐式空闲链表）
如何保存内存块的信息？
任何实际的分配器都需要一些数据结构，允许它来区别块边界，以及区别已分配块和空闲块。大多数分配器将这些信息嵌入块本身。一个简单的方法如下图所示。
在这种情况中，一个块是由一个字的头部（header）、有效载荷（payload），以及可能的一些额外的填充（padding）组成的。头部编码了这个块的大小（包括头部和所有的填充），以及这个块是已分配的还是空闲的。
由于对齐的要求，块大小必须是 8 或 16 的整数倍，因此我们可以巧妙地利用块大小的低位来保存块的分配情况。
上面这种数据结构有一个问题，合并空闲内存块时无法直接找到它的上一个内存块，需要从堆的开始进行遍历。Knuth 提出了一种叫边界标记的技术：每个块的结尾添加一个 footer（头部的副本），这样就可以通过头部的地址减去头部的大小定位到上一个块的 footer 从而得知上一个块的信息了。
如何放置有效负载到空闲块？
当一个应用请求一个 k 字节的块（payload）时，分配器需要搜索空闲链表，查找一个大小可以满足请求的空闲块。
分配器如何搜索空闲块有多种方式，被称为放置策略（placement policy）。常见的适配策略有首次适配（first fit)、下一次适配（next fit)和最佳适配（best fit)。
首次适配从头开始搜索空闲链表，选择第一个合适的空闲块。下一次适配和首次适配很相似，只不过不是从链表的起始处开始每次搜索，而是从上一次査询结束的地方开始。最佳适配检査每个空闲块，选择适合所需请求大小的最小空闲块。首次适配的优点是它趋向于将大的空闲块保留在链表的后面。缺点是它趋向于在靠近 链表起始处留下小空闲块的“碎片”，这就增加了对较大块的搜索时间。下一次适配是由Donald Knuth 作为首次适配的一种代替品最早提出的，源于这样一个想法：如果我们上一次在某个空闲块里已经发现了一个匹配，那么很可能下一次我们也能在这个剩余块中发现匹配。下一次适配比首次适配运行起来明显要快一些，尤其是当链表的前面布满了许多小的碎片时。然而，一些研究表明，下一次适配的内存利用率要比首次适配低得多。研究还表明最佳适配比首次适配和下一次适配的内存利用率都要高一些。然而，在简单空闲链表组织结构中，比如隐式空闲链表中，使用最佳适配的缺点是它要求对堆进行彻底的搜索。在后面，我们将看到更加精细复杂的分离式空闲链表组织，它接近于最佳适配策略，不需要进行彻底的堆搜索。
如何分割空闲块？
如果内存分配器搜索到的空闲块要比请求（payload）的大小大得多，以至于可以把空闲块分割成两个块，那么分配器就要考虑是否要进行分割，否则会造成内存空间的浪费。
由于对齐的需要以及需要记录内存块的信息，实际上最小的 payload 大小是有限制的。footer 和 header 各占 4 字节，payload 的大小最小必须为 8 字节来保证内存对齐。
如何合并内存块？
有 4 种可能的情况，见下图。
分配器设计
mem_init调用mem_sbrk(4*WSIZE)将堆扩大到 16 Bytes，起始一个 WSIZE 的空间用于对齐，后续3个 WSIZE 用于设置序言块和结尾块，序言块只有 header 和 footer，内容都是 8/1。结尾块的内容是 0/1 。 然后将 head_listp 指向序言块的 footer（相当于指向 payload）。序言块和结尾块不修改，这样做为合并空闲块和遍历堆块提供了方便。链表的形式如下
实现代码
实现了first Fit和 next fit，next fit得分更高， 跑出了 83 / 100 的成绩
Results for mm malloc:
trace valid util ops secs Kops
0 yes 91% 5694 0.001076 5293
1 yes 91% 5848 0.000707 8276
2 yes 95% 6648 0.001988 3344
3 yes 97% 5380 0.001947 2763
4 yes 66% 14400 0.000087164948
5 yes 90% 4800 0.003151 1523
6 yes 88% 4800 0.002977 1613
7 yes 55% 12000 0.007354 1632
8 yes 51% 24000 0.004272 5618
9 yes 27% 14401 0.031505 457
10 yes 45% 14401 0.001722 8362
Total 72% 112372 0.056786 1979
Perf index = 43 (util) + 40 (thru) = 83/100
/*
* mm-implicit-list.c - Plain malloc package using implicit list.
* Fit strategy: next fit.
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#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) */
""
};
/* 8 bytes alignment in 32bit mode */
#define ALIGNMENT 8
/* Rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
//* Basic constants and macros: */
#define WSIZE 4 /* Word and header/footer size (bytes) */
#define DSIZE 8 /* Doubleword size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */
#define MINBLOCKSIZE 16
/* Max value of 2 values */
#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) /* Take attention!!! size = header + payload + footer */
#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(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))
/* Global declarations */
static char *heap_listp, *prev_listp;
/* Function prototypes for internal helper routines */
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
/*
* 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(DSIZE, 1)); /* Epilogue header */
heap_listp += (2*WSIZE); /* make heap_listp points to epilogue header */
prev_listp = heap_listp;
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
/*
* 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 not 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; /* Minimum block size: WORD(HDR) + DWORD(Payload) + WORD(FTR) */
else
asize = ALIGN(size + 8);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
/* No fit. 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;
}
/*
* mm_free - Freeing a block and coalesce if necessary.
*/
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)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
size = GET_SIZE(HDRP(oldptr));
copySize = GET_SIZE(HDRP(newptr));
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize-WSIZE);
mm_free(oldptr);
return newptr;
}
/*
* coalesce - Merge freed block.
*/
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)
return bp;
else if (prev_alloc && !next_alloc) {
if (NEXT_BLKP(bp) == prev_listp)
prev_listp = bp;
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
prev_listp = bp;
}
else if (!prev_alloc && next_alloc) {
if (PREV_BLKP(bp) == prev_listp)
prev_listp = bp;
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);
prev_listp = bp;
}
else {
if (PREV_BLKP(bp) == prev_listp)
prev_listp = bp;
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);
prev_listp = bp;
}
// prev_listp = bp;
return bp;
}
/*
* extend_heap - Extend the heap with a free block and return that block's payload address.
*/
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));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
/* Coalesce if the previous block was free */
return coalesce(bp);
}
/* Find freeblock that fits the request size and return it's bp */
static void *find_fit(size_t asize)
{
// /* Find free block that fits the requsted asize. (first fit)*/
// for(char* bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
// if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize) {
// return bp;
// }
// }
// return NULL;
/* next fit */
for (char* bp = prev_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
{
if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize)
{
prev_listp = bp;
return bp;
}
}
for (char* bp = heap_listp; bp != prev_listp; bp = NEXT_BLKP(bp))
{
if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize)
{
prev_listp = bp;
return bp;
}
}
return NULL;
}
/* Place requested block in a free block, split if necessary */
static void place(void *bp, size_t asize)
{
size_t blk_size = GET_SIZE(HDRP(bp));
size_t remain_size = blk_size - asize;
/* split if we have space space */
if ( remain_size >= 16) {
/* set up malloced block */
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
/* set up spilited block */
PUT(HDRP(NEXT_BLKP(bp)), PACK(remain_size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(remain_size, 0));
}
else {
/* set up malloced block */
PUT(HDRP(bp), PACK(blk_size, 1));
PUT(FTRP(bp), PACK(blk_size, 1));
}
prev_listp = bp;
}
去掉分配块的Footer的实现代码
跑分基本上没区别….
Results for mm malloc:
trace valid util ops secs Kops
0 yes 90% 5694 0.000995 5721
1 yes 92% 5848 0.000603 9706
2 yes 94% 6648 0.001801 3692
3 yes 96% 5380 0.001816 2963
4 yes 66% 14400 0.000099146193
5 yes 89% 4800 0.003049 1574
6 yes 87% 4800 0.002710 1771
7 yes 55% 12000 0.006541 1835
8 yes 51% 24000 0.004291 5594
9 yes 26% 14401 0.031904 451
10 yes 34% 14401 0.001711 8419
Total 71% 112372 0.055518 2024
Perf index = 43 (util) + 40 (thru) = 83/100
/*
* mm.c - Malloc package using implicit free list. (without footer in allocated block)
* Free block's header stores its allocation status in the lowest bit)
* and its previous block's allocation status in the second lowest bit).
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#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) */
""
};
/* 8 bytes alignment in 32bit mode */
#define ALIGNMENT 8
/* Rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
//* Basic constants and macros: */
#define WSIZE 4 /* Word and header/footer size (bytes) */
#define DSIZE 8 /* Doubleword size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */
#define MINBLOCKSIZE 8 /* Minimum block size: WORD(HDR) + WORD(FTR) */
/* Max value of 2 values */
#define MAX(x, y) ((x) > (y) ? (x) : (y))
/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc)) /* `alloc` could be 0, 1, 2 or 3 */
/* 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) /* Take attention!!! size = header + payload + footer */
#define GET_ALLOC(p) (GET(p) & 0x1)
#define GET_PREV_ALLOC(p) (GET(p) & 0x2)
#define GET_PREALLOC(p) (GET(p) & 0x2)
/* Set and clear prev_alloc status at adress p*/
#define SET_PREV_ALLOC(p) (PUT(p, GET(p) | 0x2))
#define CLR_PREV_ALLOC(p) (PUT(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(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))
/* Global declarations */
static char *heap_listp, *prev_listp;
/* Function prototypes for internal helper routines */
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
/*
* 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, 3)); /* Prologue header */
PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 3)); /* Prologue footer */
PUT(heap_listp + (3*WSIZE), PACK(0, 3)); /* Epilogue header */
heap_listp += (2*WSIZE); /* make heap_listp points to epilogue header */
prev_listp = heap_listp;
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
/*
* 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 not fit */
char *bp;
/* Ignore spurious requests */
if (size == 0) {
return NULL;
}
/* Adjust block size to include overhead and alignment reqs */
if (size < WSIZE)
asize = MINBLOCKSIZE;
else
asize = ALIGN(size + 4);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
/* No fit. 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;
}
/*
* mm_free - Freeing a block and coalesce if necessary.
*/
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, GET_PREV_ALLOC(HDRP(bp))));
PUT(FTRP(bp), PACK(size, GET_PREV_ALLOC(HDRP(bp))));
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 *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
size = GET_SIZE(HDRP(oldptr));
copySize = GET_SIZE(HDRP(newptr));
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize-WSIZE);
mm_free(oldptr);
return newptr;
}
/*
* coalesce - Merge freed block.
*/
static void* coalesce(void* bp)
{
void* prev_bp = PREV_BLKP(bp);
void* next_bp = NEXT_BLKP(bp);
size_t prev_alloc = GET_PREV_ALLOC(HDRP(bp)); /* Now prev allocation status is in our current header */
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc) {
}
else if (prev_alloc && !next_alloc) {
size += GET_SIZE(HDRP(next_bp));
PUT(FTRP(next_bp), PACK(size, 2));
PUT(HDRP(bp), PACK(size, 2));
}
else if (!prev_alloc && next_alloc) {
size += GET_SIZE(HDRP(prev_bp));
PUT(FTRP(bp), PACK(size, 2));
PUT(HDRP(prev_bp), PACK(size, 2)); /* prev is free, PREV_BLKP(prev) must be allocated */
bp = prev_bp;
}
else {
size += GET_SIZE(HDRP(prev_bp)) +
GET_SIZE(FTRP(next_bp));
PUT(FTRP(next_bp), PACK(size, 2));
PUT(HDRP(prev_bp), PACK(size, 2));
bp = prev_bp;
}
CLR_PREV_ALLOC(HDRP(NEXT_BLKP(bp)));
prev_listp = bp;
return bp;
}
/*
* extend_heap - Extend the heap with a free block and return that block's payload address.
*/
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, GET_PREV_ALLOC(HDRP(bp))));
PUT(FTRP(bp), PACK(size, GET_PREV_ALLOC(HDRP(bp))));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
/* Coalesce if the previous block was free */
return coalesce(bp);
}
/* Find freeblock that fits the request size and return it's bp */
static void *find_fit(size_t asize)
{
for (char* bp = prev_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
{
if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize)
{
prev_listp = bp;
return bp;
}
}
for (char* bp = heap_listp; bp != prev_listp; bp = NEXT_BLKP(bp))
{
if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize)
{
prev_listp = bp;
return bp;
}
}
return NULL;
}
/* Place requested block in a free block, split if necessary */
static void place(void *bp, size_t asize)
{
size_t blk_size = GET_SIZE(HDRP(bp));
size_t remain_size = blk_size - asize;
/* split if we have space space */
if ( remain_size >= MINBLOCKSIZE) {
/* |4 Byte HDR| Payload | 4 Bytes FTR| */
/* set up malloced block */
PUT(HDRP(bp), PACK(asize, 3));
/* set up spilited block */
PUT(HDRP(NEXT_BLKP(bp)), PACK(remain_size, 2));
PUT(FTRP(NEXT_BLKP(bp)), PACK(remain_size, 2));
/* Clear alloc status of next */
CLR_PREV_ALLOC(HDRP(NEXT_BLKP(NEXT_BLKP(bp))));
}
else {
/* set up malloced block */
PUT(HDRP(bp), PACK(blk_size, 3));
/* Set alloc status of next block */
SET_PREV_ALLOC(HDRP(NEXT_BLKP(bp)));
}
prev_listp = bp;
}
实现二：Explicit Free List（显示空闲链表）
如何保存内存块的信息？
上面的实现有一个问题：每次在寻找未分配的块时需要同时遍历已分配的块和未分配的块，遍历已分配的块的操作显然是多余的。
一种更好的方法是将空闲块组织为某种形式的显示数据结构（双向链表），可以巧妙利用空闲块的 payload 部分来保存这个数据结构的指针（前驱 pred 和后继 succ）。如下图所示
堆块的放置、合并、分割
使用显式空闲链表，使首次适配（first fit）的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间可以是线性的，也可能是个常数，这取决于我们所选择的空闲链表中块的排序策略。
一种方法是用后进先出（LIFO）的顺序维护链表，将新释放的块放到链表的开头，使用LIFO和First Fit的放置策略释放堆块可以在常数时间内完成。如果使用了边界标记则合并堆块（基于堆地址的线性合并）也可以在常数时间内完成。
另一种方法是按地址顺序维护链表，后继的地址大于前驱块的地址，这种情况下，释放一个块需要线性时间来搜索链表确定前驱。但是，按照地址排序的首次适配比 LIFO 排序的首次适配有更高的内存利用率，接近最佳适配的利用率。
显式链表的缺点是空闲块必须足够大，以包含所有需要的指针，以及头部和可能的脚部。这就导致了更大的最小块大小，也潜在地提高了内部碎片的程度。
分配器设计
链表的形式和之前一样，唯一的区别就是空闲块的 payload 用于存放链表的指针
双向链表的维护比较复杂，建议把每种情况都考虑清楚再开始写代码，不然就是无尽的 debug
逻辑分析
mm_init():
HEAP: Padding|Prologue|Prologue|Epilogue, Free list = NULL
-->extend_head(4096):
Padding|Prologue|Prologue|HDR|Payload|FTR|Epilogue, Free list: NULL
-->coalesce(bp): No merge
-->insert(bp)
HEAP: Padding|Prologue|Prologue|HDR|Payload|FTR|Epilogue, Free list: Payload
malloc(size):
Padding|Prologue|Prologue|(HDR|Payload|FTR)n|Epilogue, Free list: Payload
/* Case 1 */
-->find_fit(size): Found Fit. Return bp of Payload
-->place(bp): Split
-->remove(bp): Free list: NULL
-->coalesce(NEXT_BLKP(bp)): No merge. Prev/Next block must be allocated since current is Free.
-->insert(NEXT_BLKP(bp))
Free list: NEXT_BLKP(bp)
-->place(bp): No Split:
-->remove(bp):
Free list: NULL
/* Case 2 */
-->find_fit(size): No Fit. Return NULL;
-->extend_heap(MAX(size, chunksize)
-->coalesce(new_bp)
/* Case 1: No merge */
-->insert(new_bp)
/* Case 2: Merg prev. Return PREV_BLKP(new_bp) */
bp = return value of extend_heap(): new_bp or PREV_BLKP(new_bp)
-->place(bp): Split
-->remove(bp);
-->coalesce(NEXT_BLKP(bp)): No Merge. We've just extended heap, NEXT_BLKP(bp) is LAST BLOCK
-->insert(NEXT_BLKP(bp))
-->place(bp): No Split:
-->remove(bp): Okay, bp newly added to free list or already in it.
free(bp):
-->coalesce(bp):
/* Case 1. No merge. */
-->insert(bp)
/* Case 2. Merg prev. */
/* Case 3. Merg next. Remove next block. */
-->remove(next_bp)
-->insert(bp)
/* Case 4. Merg prev and next. Remove next block. */
-->remove(next_bp)
realloc(bp):
it's just malloc, memcpy and free.
实现代码
使用LIFO顺序维护链表，First Fit和边界标记的显式空闲链表分配器实现如下，貌似性能并不如Implicit Free List，猜测是插入方式的原因
Results for mm malloc:
trace valid util ops secs Kops
0 yes 88% 5694 0.000233 24490
1 yes 93% 5848 0.000192 30538
2 yes 95% 6648 0.000325 20487
3 yes 97% 5380 0.000267 20112
4 yes 66% 14400 0.000307 46936
5 yes 89% 4800 0.000503 9541
6 yes 88% 4800 0.000483 9940
7 yes 55% 12000 0.001122 10698
8 yes 51% 24000 0.001411 17004
9 yes 27% 14401 0.032037 450
10 yes 30% 14401 0.002032 7087
Total 71% 112372 0.038911 2888
Perf index = 42 (util) + 40 (thru) = 82/100
/*
* mm.c - Malloc package using explicit free list.
* Newly freed block will be inserted to the head of free list.
*/
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#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
#ifdef DEBUG
# define DBG_PRINTF(...) printf(__VA_ARGS__)
# define CHECKHEAP(verbose) mm_checkheap(verbose)
#else
# define DBG_PRINTF(...)
# define CHECKHEAP(verbose)
#endif
/* 8 bytes alignment in 32bit mode */
#define ALIGNMENT 8
/* Rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
//* Basic constants and macros: */
#define WSIZE 4 /* Word and header/footer size (bytes) */
#define DSIZE 8 /* Doubleword size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */
#define MINBLOCKSIZE 16
/* Max value of 2 values */
#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 foward and back pointer field (foward and back blocks are logically linked) */
#define FDP(bp) (*(char **)(bp + WSIZE))
#define BKP(bp) (*(char **)(bp))
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))
/* Set BK and FD field of a block by given pointer */
#define SET_BKP(bp, bkp) (BKP(bp) = bkp)
#define SET_FDP(bp, fdp) (FDP(bp) = fdp)
/* Global declarations */
static char *heap_listp;
static char *freelist_headp;
/* Function prototypes for internal helper routines */
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void insert(void *bp); /* insert a free block to free list */
static void delete(void *bp); /* delete a free block from free list */
static void mm_checkheap(int verbose);
/*
* 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 */
freelist_headp = NULL;
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL) /* set free list head to the first free block */
return -1;
return 0;
}
/*
* 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)
{
DBG_PRINTF("Entering mm_malloc(%zu)\n", size);
size_t asize; /* Adjusted block size */
size_t extendsize; /* Amount to extend heap if not 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; /* Minimum block size: WORD(HDR) + DWORD(Payload) + WORD(FTR) */
else
asize = ALIGN(size + 8);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
/* No fit. 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;
}
/*
* mm_free - Freeing a block and coalesce if necessary.
*/
void mm_free(void *bp)
{
DBG_PRINTF("Entering mm_free(%p)\n", bp);
/* Modify header and footer then coalesce the block and insert it into free list */
PUT(HDRP(bp), PACK(GET_SIZE(HDRP(bp)),0));
PUT(FTRP(bp), PACK(GET_SIZE(HDRP(bp)),0));
coalesce(bp);
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
size = GET_SIZE(HDRP(oldptr));
copySize = GET_SIZE(HDRP(newptr));
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize-WSIZE);
mm_free(oldptr);
return newptr;
}
/*
* coalesce - Merge freed block if necessary.
* Return: Pointer of the merged block.
*/
static void* coalesce(void* bp)
{
DBG_PRINTF("Entering coalesce(%p), ", bp);
/*
* We have to save our adjacent block's address.
* After `PUT(HDRP(bp), PACK(newsize ,0))` will render NEXT_BLKP(bp) nonsense.
* It's really nasty and takes me a lot of time to debug.
*/
void* prev_bp = PREV_BLKP(bp);
void* next_bp = NEXT_BLKP(bp);
size_t prev_alloc = GET_ALLOC(FTRP(prev_bp));
size_t next_alloc = GET_ALLOC(HDRP(next_bp));
size_t current_size = GET_SIZE(HDRP(bp));
/* Case 0: no need to coalesce */
if (prev_alloc && next_alloc) {
DBG_PRINTF("no merge\n");
insert(bp);
return bp;
}
/*
* Case 1, previous block is free
*/
else if (!prev_alloc && next_alloc) {
DBG_PRINTF("merge prev(%p)\n", prev_bp);
/* setup merged block */
current_size += GET_SIZE(HDRP(prev_bp));
PUT(HDRP(prev_bp), PACK(current_size, 0));
PUT(FTRP(bp), PACK(current_size, 0));
return prev_bp;
}
/*
* Case 2, next block is free, we need to delete next block from free list.
*/
else if (prev_alloc && !next_alloc) {
DBG_PRINTF("merge next(%p)\n", next_bp);
/* Delete next block from free list */
delete(next_bp);
/* setup merged block */
current_size += GET_SIZE(HDRP(next_bp));
PUT(HDRP(bp), PACK(current_size, 0));
PUT(FTRP(bp), PACK(current_size, 0));
insert(bp);
return bp;
}
/*
* Case 3, previous and next block both are free, we need to delete next block from free list.
*/
else {
DBG_PRINTF("merge prev(%p) and next(%p)\n", prev_bp, next_bp);
/* Delete next block from free list */
delete(next_bp);
/* setup merged block */
current_size += GET_SIZE(HDRP(prev_bp));
current_size += GET_SIZE(FTRP(next_bp));
PUT(HDRP(prev_bp), PACK(current_size, 0));
PUT(FTRP(next_bp), PACK(current_size, 0));
return prev_bp;
}
}
/*
* extend_heap - Extend the heap with a free block and coalesce the new free block if necessary.
* Return : new free block's payload address.
*/
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
/* Allocate 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
* After mem_srbk(size), we are always at the end of epilogue footer,
* so we need to change the epilogue ftr to normal header and setup epilogue footer at the end of heap.
*/
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
// SET_BKP(bp, NULL);
// SET_FDP(bp, NULL);
/* Coalesce if the previous block was free */
return coalesce(bp);
}
/* find_fit - Find freeblock that fits the request size and return it's bp */
static void *find_fit(size_t asize)
{
DBG_PRINTF("Entering find_fit(%zu), ", asize);
/* Free list initailzed in mm_init(), freelist_headp points to the payload of free block */
/* Traverse free list */
for(void* current = freelist_headp; current != NULL; current = FDP(current)) {
if (GET_SIZE(HDRP(current)) >= asize) {
DBG_PRINTF("found %p, size: %u\n", current, GET_SIZE(HDRP(current)));
return current;
}
}
/* Not found */
DBG_PRINTF("not found\n");
return NULL;
}
/* place - Place requested block in current free block, split if necessary */
static void place(void *bp, size_t asize)
{
DBG_PRINTF("Entering place(%p)",bp);
delete(bp);
size_t size = GET_SIZE(HDRP(bp));
if ((size - asize) >= MINBLOCKSIZE)
{
/* set up current block */
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
DBG_PRINTF("split: %p and %p\n", bp, NEXT_BLKP(bp));
/* set up remain block */
PUT(HDRP(NEXT_BLKP(bp)), PACK(size-asize, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size-asize, 0));
coalesce(NEXT_BLKP(bp));
}
else {
DBG_PRINTF("no split\n");
/* Waste some space, we have no other way */
PUT(HDRP(bp), PACK(size, 1));
PUT(FTRP(bp), PACK(size, 1));
}
}
/*
* insert - Insert given block pointer to the head of free list.
* insert() is called by free() or place()
*/
static void insert(void* bp)
{
DBG_PRINTF("Entering insert(%p)\n", bp);
if (freelist_headp == NULL) {
DBG_PRINTF("Free list is NULL, make %p the head of free list\n", bp);
freelist_headp = bp;
SET_FDP(bp, NULL);
SET_BKP(bp, NULL);
CHECKHEAP(0);
return;
}
/* Set up current block */
SET_FDP(bp, freelist_headp);
SET_BKP(bp, 0);
/* Set next block */
SET_BKP(freelist_headp, bp);
/* Free list head is np now */
freelist_headp = bp;
CHECKHEAP(0);
}
/*
* delete - Remove given block pointer from free list.
* delete() is called by place() or coalesce();
* we dont' call delete() when there's no free block, so what we deleted is what we inserted.
*/
static void delete(void* bp)
{
DBG_PRINTF("Entering delete(%p)\n", bp);
/* Only one free block */
if(BKP(bp) == NULL && FDP(bp) == NULL) {
freelist_headp = NULL;
}
/* More than one free block, delete the first block */
else if (BKP(bp) == NULL) {
/* Fix free list head */
SET_BKP(FDP(bp), NULL);
freelist_headp = FDP(bp);
}
/* More than one free block, delete the last block */
else if (FDP(bp) == NULL) {
SET_FDP(BKP(bp), NULL);
}
/* More than two free block, delete the middle block */
else {
SET_FDP(BKP(bp), FDP(bp));
SET_BKP(FDP(bp), BKP(bp));
}
CHECKHEAP(0);
}
static void mm_checkheap(int verbose)
{
DBG_PRINTF("---------------CHECK HEAP START---------------------\n");
DBG_PRINTF("freelist_headp: %p\n", freelist_headp);
if (freelist_headp) {
DBG_PRINTF("Free List: %p<-", BKP(freelist_headp));
for (char * tmp = freelist_headp; tmp != NULL; tmp = FDP(tmp)) {
DBG_PRINTF("%p(size: %u)->", tmp, GET_SIZE(HDRP(tmp)));
}
DBG_PRINTF("%p\n", NULL);
}
DBG_PRINTF("---------------CHECK HEAP END----------------------\n");
}
实现三：Segregated Free List（分离式空闲链表）
实现代码
得分84，还有优化的空间
Results for mm malloc:
trace valid util ops secs Kops
0 yes 98% 5694 0.000302 18836
1 yes 94% 5848 0.000307 19061
2 yes 98% 6648 0.000374 17780
3 yes 99% 5380 0.000290 18526
4 yes 66% 14400 0.000525 27439
5 yes 89% 4800 0.001009 4757
6 yes 86% 4800 0.001024 4688
7 yes 55% 12000 0.007099 1690
8 yes 51% 24000 0.027033 888
9 yes 30% 14401 0.032619 441
10 yes 34% 14401 0.002412 5970
Total 73% 112372 0.072994 1539
Perf index = 44 (util) + 40 (thru) = 84/100
/*
mm.c - Malloc package using segregated free list.
Chunk details:
Chunks of memory are maintained using a `boundary tag' method as
described in e.g., Knuth or Standish. (See the paper by Paul
Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a
survey of such techniques.) Sizes of free chunks are stored both
in the front of each chunk and at the end. This makes
consolidating fragmented chunks into bigger chunks very fast. The
size fields also hold bits representing whether chunks are free or
in use.
An allocated chunk looks like this:
header-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| Size of chunk, in bytes |A|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. .
. |
footer-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| Same as header(`boundary tag`) |A|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
"header" is the front of the chunk for the purpose of most of the
malloc code, but "mem" is the pointer that is returned to the user.
Chunks always begin on even word boundaries, so the mem portion
(which is returned to the user) is also on an even word boundary, and
thus at least double-word aligned.
Free chunks are stored in doubly-linked lists, and look like this:
header-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| Size of chunk, in bytes |A|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Forward pointer to next chunk in free list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Back pointer to previous chunk in free list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unused space (may be 0 bytes long) .
. .
. |
footer-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| Same as header(`boundary tag`) |A|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The A (ALLOCATED) bit is set for prologue and epilogue block to help
determine block's boundary.
Prologue and epilogue block's size are set to 0.
Heap structure:
heap start-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| 4 btes padding |
free list heads-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Free list's head address(request size <= 8) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Free list's head address(request size <= 16) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| .
. Same as above, request size <= power of 2 .
. |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Free list's head address(request size > 4096) |
prologue header-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |A|
prologue footer->-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |A|
free and allocated chunks-> +-+-+-+-+-+-+-+-+-+-+-+
| .
. .
. |
epilogue footer->-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |A|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The free list head stores the starting address of each
free list for differnt size classes, from lower than 8
byts to bigger than 4096 bytes.
We have 10 free list entry, so no padding is needed.
*/
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#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) */
""
};
/*
Debugging macros:
*/
#define DEBUG 0
#define HEAP_CHECK 0
#if DEBUG == 1
# define DBG_PRINTF(...) printf(__VA_ARGS__)
#else
# define DBG_PRINTF(...)
#endif
#if HEAP_CHECK == 1
#define CHECKHEAP(verbose) mm_checkheap(verbose)
#else
#define CHECKHEAP(verbose)
#endif
/* 8 bytes alignment in 32bit mode */
#define ALIGNMENT 8
/* Rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
//* Basic constants and macros: */
#define WSIZE 4 /* Word and header/footer size (bytes) */
#define DSIZE 8 /* Doubleword size (bytes) */
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */
#define MINBLOCKSIZE 16 /* Minimum block size: WORD(HDR) + WORD(FDP) + WORD(BKP) + WORD(FTR) */
#define ALLOCATED 1
#define UNALLOCATED 0
/* Max value of 2 values */
#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, get value of foward and back pointer of that chunk (note those are different from HDRP() adn FTRP()) */
#define FDP(bp) (*(char **)(bp))
#define BKP(bp) (*(char **)(bp + WSIZE))
/* Given block ptr bp, set forward and back pointer's value of that block by given value*/
#define SET_FDP(bp, fdp) (FDP(bp) = fdp)
#define SET_BKP(bp, bkp) (BKP(bp) = bkp)
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))
/* Given block size, compute the free list offset */
#define LIST_OFFSET(size) \
(size <= 16 ? 0 :\
size <= 32 ? 1 :\
size <= 64 ? 2 :\
size <= 128 ? 3 :\
size <= 256 ? 4 :\
size <= 512 ? 5 :\
size <= 1024 ? 6 :\
size <= 2048 ? 7 :\
size <= 4096 ? 8 :\
9)
/* Global declarations */
static char *heap_listp;
static char *seglist_start;
static char *freelist_headp;
/* Function prototypes for internal helper routines */
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
static void insert(void *bp); /* insert a free block to free list */
static void delete(void *bp); /* delete a free block from free list */
static void mm_checkheap(int verbose);
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(14*WSIZE)) == (void *) -1)
return -1;
PUT(heap_listp, 0); /* Padding for alignment, user memory sits at 14*4 = 48 Bytes after heap start*/
PUT(heap_listp + (1*WSIZE), 0); /* Block size <= 16 */
PUT(heap_listp + (2*WSIZE), 0); /* Block size <= 32 */
PUT(heap_listp + (3*WSIZE), 0); /* Block size <= 64 */
PUT(heap_listp + (4*WSIZE), 0); /* Block size <= 128 */
PUT(heap_listp + (5*WSIZE), 0); /* Block size <= 256 */
PUT(heap_listp + (6*WSIZE), 0); /* Block size <= 512 */
PUT(heap_listp + (7*WSIZE), 0); /* Block size <= 1024 */
PUT(heap_listp + (8*WSIZE), 0); /* Block size <= 2048 */
PUT(heap_listp + (9*WSIZE), 0); /* Block size <= 4096 */
PUT(heap_listp + (10*WSIZE), 0); /* Block size > 4096 */
PUT(heap_listp + (11*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
PUT(heap_listp + (12*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
PUT(heap_listp + (13*WSIZE), PACK(0, 1)); /* Epilogue header */
seglist_start = heap_listp + WSIZE;
DBG_PRINTF("seglist_start: %p\n", seglist_start);
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE/WSIZE) == NULL) /* set free list head to the first free block */
return -1;
return 0;
}
/*
* 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)
{
DBG_PRINTF("Entering mm_malloc(%zu)\n", size);
CHECKHEAP(0);
size_t asize; /* Adjusted block size */
size_t extendsize; /* Amount to extend heap if not 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; /* Minimum block size: WORD(HDR) + DWORD(Payload) + WORD(FTR) */
else
asize = ALIGN(size + 8);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
/* No fit. 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;
}
/*
* mm_free - Freeing a block and coalesce if necessary.
*/
void mm_free(void *bp)
{
DBG_PRINTF("Entering mm_free(%p)\n", bp);
CHECKHEAP(0);
/* Modify header and footer then coalesce the block and insert it into free list */
PUT(HDRP(bp), PACK(GET_SIZE(HDRP(bp)),0));
PUT(FTRP(bp), PACK(GET_SIZE(HDRP(bp)),0));
coalesce(bp);
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
DBG_PRINTF("Entering mm_realloc(%p, %zu)\n", ptr, size);
CHECKHEAP(0);
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
size = GET_SIZE(HDRP(oldptr));
copySize = GET_SIZE(HDRP(newptr));
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize-WSIZE);
mm_free(oldptr);
return newptr;
}
/*
* coalesce - Merge freed block if necessary.
* Return: Pointer of the merged block.
*/
static void* coalesce(void* bp)
{
DBG_PRINTF("Entering coalesce(%p), ", bp);
/*
* We have to save our adjacent block's address.
* After `PUT(HDRP(bp), PACK(newsize ,0))` will render NEXT_BLKP(bp) nonsense.
* It's really nasty and takes me a lot of time to debug.
*/
void* prev_bp = PREV_BLKP(bp);
void* next_bp = NEXT_BLKP(bp);
size_t prev_alloc = GET_ALLOC(FTRP(prev_bp));
size_t next_alloc = GET_ALLOC(HDRP(next_bp));
size_t current_size = GET_SIZE(HDRP(bp));
/* Case 0: no need to coalesce */
if (prev_alloc && next_alloc) {
DBG_PRINTF("no merge\n");
insert(bp);
return bp;
}
/*
* Case 1, previous block is free
*/
else if (!prev_alloc && next_alloc) {
DBG_PRINTF("merge prev(%p)\n", prev_bp);
/* setup merged block */
current_size += GET_SIZE(HDRP(prev_bp));
delete(prev_bp);
PUT(HDRP(prev_bp), PACK(current_size, 0));
PUT(FTRP(bp), PACK(current_size, 0));
insert(prev_bp);
return prev_bp;
}
/*
* Case 2, next block is free, we need to delete next block from free list.
*/
else if (prev_alloc && !next_alloc) {
DBG_PRINTF("merge next(%p)\n", next_bp);
current_size += GET_SIZE(HDRP(next_bp));
/* Delete next block from free list */
delete(next_bp);
/* setup merged block */
PUT(HDRP(bp), PACK(current_size, 0));
PUT(FTRP(bp), PACK(current_size, 0));
insert(bp);
return bp;
}
/*
* Case 3, previous and next block both are free, we need to delete next block from free list.
*/
else {
DBG_PRINTF("merge prev(%p) and next(%p)\n", prev_bp, next_bp);
current_size += GET_SIZE(HDRP(prev_bp));
current_size += GET_SIZE(FTRP(next_bp));
/* Delete prev and next block from free list */
delete(prev_bp);
delete(next_bp);
/* setup merged block */
PUT(HDRP(prev_bp), PACK(current_size, 0));
PUT(FTRP(next_bp), PACK(current_size, 0));
insert(prev_bp);
return prev_bp;
}
}
/*
* extend_heap - Extend the heap with a free block and coalesce the new free block if necessary.
* Return : new free block's payload address.
*/
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
/* Allocate 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
* After mem_srbk(size), we are always at the end of epilogue footer,
* so we need to change the epilogue ftr to normal header and setup epilogue footer at the end of heap.
*/
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
/* Coalesce if the previous block was free */
return coalesce(bp);
}
/* find_fit - Find freeblock that fits the request size and return it's bp */
static void *find_fit(size_t asize)
{
DBG_PRINTF("Entering find_fit(%zu), ", asize);
/* Traverse all the free lists */
for ( int i = 0; i < 10; i++) {
DBG_PRINTF("LIST_OFFSET: %d\n", i);
freelist_headp = *(char **)(seglist_start + i * WSIZE);
/* Traverse free list */
for(void* current = freelist_headp; current != NULL; current = FDP(current)) {
if (GET_SIZE(HDRP(current)) >= asize) {
DBG_PRINTF("found %p, size: %u\n", current, GET_SIZE(HDRP(current)));
return current;
}
}
}
/* Not found */
DBG_PRINTF("not found\n");
return NULL;
}
/* place - Place requested block in current free block, split if necessary */
static void place(void *bp, size_t asize)
{
DBG_PRINTF("Entering place(%p)",bp);
delete(bp);
size_t size = GET_SIZE(HDRP(bp));
if ((size - asize) >= MINBLOCKSIZE)
{
/* set up current block */
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
DBG_PRINTF("split: %p and %p\n", bp, NEXT_BLKP(bp));
/* set up remain block */
PUT(HDRP(NEXT_BLKP(bp)), PACK(size-asize, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size-asize, 0));
coalesce(NEXT_BLKP(bp));
}
else {
DBG_PRINTF("no split\n");
/* Waste some space, we have no other way */
PUT(HDRP(bp), PACK(size, 1));
PUT(FTRP(bp), PACK(size, 1));
}
}
/*
* insert - Insert given block pointer to the head of free list.
* insert() is called by free() or place()
*/
static void insert(void* bp)
{
DBG_PRINTF("Entering insert(%p)\n", bp);
/* Locate freelist */
char **ptr_to_freelist_headp = (char **)(seglist_start + LIST_OFFSET(GET_SIZE(HDRP(bp))) * WSIZE);
DBG_PRINTF("LIST_OFFSET: %d\n", LIST_OFFSET(GET_SIZE(HDRP(bp))));
freelist_headp = *ptr_to_freelist_headp;
/* List is NULL, make bp as list head */
if (freelist_headp == NULL) {
DBG_PRINTF("Free list is NULL, make %p the head of free list\n", bp);
SET_FDP(bp, NULL);
SET_BKP(bp, NULL);
}
/* insert */
else {
DBG_PRINTF("Free list not null, %p will be new head\n", bp);
/* Set up current block */
SET_FDP(bp, freelist_headp);
SET_BKP(bp, 0);
/* Set up next block */
SET_BKP(freelist_headp, bp);
}
/* Free list head is np now */
*ptr_to_freelist_headp = bp;
return;
}
/*
* delete - Remove given block pointer from free list.
* delete() is called by place() or coalesce();
* we dont' call delete() when there's no free block, so what we deleted is what we inserted.
*/
static void delete(void* bp)
{
DBG_PRINTF("Entering delete(%p)\n", bp);
/* Locate freelist */
char **ptr_to_freelist_headp = (char **)(seglist_start + LIST_OFFSET(GET_SIZE(HDRP(bp))) * WSIZE);
DBG_PRINTF("LIST_OFFSET: %d\n", LIST_OFFSET(GET_SIZE(HDRP(bp))));
/* Only one free block */
if(BKP(bp) == NULL && FDP(bp) == NULL) {
DBG_PRINTF("Only one free block\n");
*ptr_to_freelist_headp = NULL;
}
/* More than one free block, delete the first block */
else if (BKP(bp) == NULL) {
DBG_PRINTF("More than one free block, delete the first block\n");
/* Fix free list head */
SET_BKP(FDP(bp), NULL);
DBG_PRINTF("New list head: %p\n", FDP(bp));
*ptr_to_freelist_headp = FDP(bp);
}
/* More than one free block, delete the last block */
else if (FDP(bp) == NULL) {
DBG_PRINTF("More than one free block, delete the last block\n");
SET_FDP(BKP(bp), NULL);
}
/* More than two free block, delete the middle block */
else {
DBG_PRINTF("More than two free block, delete the middle block\n");
SET_FDP(BKP(bp), FDP(bp));
SET_BKP(FDP(bp), BKP(bp));
}
}
static void check_freelist()
{
printf("---------------CHECK FREE LIST START----------------------\n");
for ( int i = 0; i < 10; i++) {
DBG_PRINTF("LIST_OFFSET: %d\n", i);
freelist_headp = *(char **)(seglist_start + i * WSIZE);
printf("freelist_headp: %p\n", freelist_headp);
char *cur, *next;
if ((cur = freelist_headp) != NULL)
{
printf("Free List: %p<-", BKP(cur));
while(cur != NULL)
{
next = FDP(cur);
printf("%p(size: %u)->", cur, GET_SIZE(HDRP(cur)));
/* Check if next free block points to us */
if(next != NULL && BKP(next) != cur) {
printf("\nNext free block does not point to current block!\n");
exit(1);
}
cur = next;
}
printf("%p\n", NULL);
}
else
{
printf("Free List is NULL.\n");
}
}
printf("--------------- CHECK FREE LIST END ----------------------\n");
}
static void mm_checkheap(int verbose)
{
check_freelist();
/*
* What we need to check:
* 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
*/
char *header_start = heap_listp + 11 * WSIZE; /* Prologue header */
/* Check prologue header */
if (GET_SIZE(header_start) != DSIZE || GET_ALLOC(header_start) != 1) {
printf("Prologue Header Malformed. Size: %d, Alloc: %d\n", GET_SIZE(header_start), GET_ALLOC(header_start));
exit(1);
}
if (GET_SIZE(header_start + WSIZE) != DSIZE || GET_ALLOC(header_start + WSIZE) != 1) {
printf("Prologue Footer Malformed.\n");
exit(1);
}
/* Traverse blocks, check status */
char *header = header_start + DSIZE;
while ( GET_SIZE(header) != 0) {
/* Alignment */
if((unsigned long)(header + WSIZE) % ALIGNMENT) {
printf("Address not aligned!\n");
exit(1);
}
/* No adjacent free block */
char *next = header + GET_SIZE(header);
if (!GET_ALLOC(header) && !GET_ALLOC(next)) {
printf("Adjacent free block!\n");
printf("Current header: %p, size: %d alloc: %dx\n", header, GET_SIZE(header), GET_ALLOC(header));
printf("Next header: %p, size: %d alloc: %dx\n", header, GET_SIZE(next), GET_ALLOC(next));
check_freelist();
exit(1);
}
header = next;
}
}
REF：