malloc lab（问题在贴中）
一、内存系统模型内存模型由memlib.c包所提供，允许我们在不干涉malloc系统包的情况下，运行分配器。其中含有以下函数：
mem_init()：用malloc函数得到一个大的、双字对齐的字节数组，视为堆。
mem_heap变量：指向堆的首地址
mem_brk变量：指向堆顶，它与mem_heap之间的字节表示已分配的虚拟内存
mem_sbrk()：请求额外的堆内存（让mem_brk增加），且不会收缩堆
二、分配器的函数原型
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
mm_init()函数初始化分配器，若成功返回0，否则返回-1。mm_malloc()和mm_free()函数与原始的malloc和free原型和语义相同。这些函数在源文件mm.c中。
分配器对块大小使用双字边界对齐，采用教材图9-39所示的块格式，如下：
最小块大小为16（有效载荷不允许为0），空闲链表组织为一个隐式空闲链表，并具有以下恒定形式：
第一个字为填充字（不使用），后面紧跟着一个特殊的序言块，这是一个8字节的已分配块，只由一个头部和一个脚部组成。序言块是在初始化时创建，并且永不释放。
序言块后紧跟的是0个或多个普通块。
堆总是以一个特殊的结尾块来结束，这个块是一个大小为0的已分配块，只由一个头部组成。
分配器用一个static的全局变量heap_listp指向序言块。
三、操纵空闲链表的基本常数和宏
在空闲链表中操作头部和脚部要大量使用强制类型转换和指针运算，因此，预定义一些宏（macro）来访问和遍历空闲链表很有帮助，见教材图9-43。
PACK(size, alloc)：将大小和已分配位打包成一个字（头部/脚部）
GET(p)：返回地址p处的字
GET_SIZE(p)：返回地址p处的字的大小（头部/脚部）
GET_ALLOC(p)：返回地址p处的字的已分配位（头部/脚部）
bp：该指针表示块指针，即有效载荷第一个字节的地址
HDRP(bp)/FTRP(bp)：返回这个块的头部/脚部地址
NEXT_BLKP(bp)/PREV_BLKP(bp)：返回下一个块/前一个块的块指针
四、创建初始空闲链表
1、mm_init()从内存系统得到4个字，并将它们初始化为填充字、序言块头部、序言块脚部、结尾块。然后调用extend_heap()函数，将堆扩展CHUNKSIZE字节，并创建初始空闲块。（见mm.c）
2、extend_heap()为保持双字对齐，将请求大小向上舍入到最接近的2字倍数，然后调用mem_sbrk()请求额外的堆空间。该空间紧接在结尾块之后。
巧妙的是，结尾块就作为新空间的头部，而新空间的最后一个字作为新的结尾块。
最后，由于extend_heap()也可能被mm_malloc()调用，因此很可能旧的块是以一个空闲块结束，因此需要coalesce()函数来合并这两个空闲块。
五、释放和合并块
mm_free()用于释放一个块。该函数释放所请求的块（bp），并调用coalesce()函数来合并与之邻接的空闲块。（4种情况，见图9-40）
六、分配块
mm_malloc()函数用来分配大小为size的块。函数必须调整请求的大小，从而为头部和脚部留出空间，并满足双字对齐的要求。最小块大小为16字节（载荷不能为0）。
分配器调整了请求大小之后，会搜索空闲链表，寻找一个合适的空闲块（有多种策略，这里采用首次适配）。如果能找到，就放着这个请求块，并可选地分割出多余的部分；如果不能找到，就调用extend_heap()来扩展堆，并将请求放在这个新空闲块中。最后返回新分配的块
可选地分割：将请求块放置在空闲块的起始位置，只有当剩余部分的大于等于最小块大小时，才进行分割。
七、编写程序，测试分配器是否正确
随机生成100个整数存入链表，然后输出链表中的所有结点，最后清空整个链表。要求使用自己的动态分配器。
示例程序：test.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "memlib.h"
#include "mm.h"
struct Node
{
int element;
struct Node * next;
};
void Insert(struct Node * L, int X)
{
struct Node *P, *Q;
P = L;
while (P->next != NULL)
P = P->next;
Q = mm_malloc(sizeof(struct Node));
Q->element = X;
Q->next = P->next;
P->next = Q;
}
void PrintList(struct Node * L)
{
struct Node *P;
P = L->next;
while (P != NULL)
{
printf("%d ", P->element);
P = P->next;
}
printf("\n");
}
void ClearList(struct Node * L) // delete all nodes
{
struct Node *P;
while (L->next != NULL)
{
P = L->next;
L->next = P->next;
mm_free(P);
}
}
int main()
{
int i;
struct Node * L;
mem_init();
if (mm_init() == -1)
exit(-1);
L = mm_malloc(sizeof(struct Node)); // Header
L->next = NULL;
srand(time(NULL));
for (i = 0; i < 100; i ++)
Insert(L, rand() % 100);
PrintList(L);
ClearList(L);
}
示例程序：memlib.h
#include <unistd.h>
void mem_init(void);
void *mem_sbrk(int incr);
示例程序：mm.h
extern int mm_init(void);
extern void *mm_malloc (size_t size);
extern void mm_free (void *ptr);
示例程序：mm.c
/*
* Simple, 32-bit and 64-bit clean allocator based on implicit free
* lists, first-fit placement, and boundary tag coalescing, as described
* in the CS:APP3e text. Blocks must be aligned to doubleword (8 byte)
* boundaries. Minimum block size is 16 bytes.
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "mm.h"
#include "memlib.h"
/* 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)))
/* Global variables */
static char *heap_listp = 0; /* Pointer to first block */
/* Function prototypes for internal helper routines */
static void *extend_heap(size_t words);
static void place(void *bp, size_t asize);
static void *find_fit(size_t asize);
static void *coalesce(void *bp);
/*
* mm_init - Initialize the memory manager
*/
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);
/* 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 with at least size bytes of payload
*/
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;
}
/*
* mm_free - Free a block
*/
void mm_free(void *bp)
{
if (bp == 0)
return;
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
/*
* coalesce - Boundary tag coalescing. Return ptr to coalesced block
*/
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));
if (prev_alloc && next_alloc) { /* Case 1 */
return bp;
}
else 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);
}
return bp;
}
/*
* extend_heap - Extend heap with free block and return its block pointer
*/
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);
}
/*
* place - Place block of asize bytes at start of free block bp
* and split if remainder would be at least minimum block size
*/
static void 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));
}
else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*
* find_fit - Find a fit for a block with asize bytes
*/
static void *find_fit(size_t asize)
{
/* First-fit search */
void *bp;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
return NULL; /* No fit */
}
示例程序：memlib.c
/*
* memlib.c - a module that simulates the memory system. Needed
* because it allows us to interleave calls from the student's malloc
* package with the system's malloc package in libc.
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <errno.h>
#include "memlib.h"
#define MAX_HEAP (20*(1<<20)) /* 20 MB */
/* Private global variables */
static char *mem_heap; /* Points to first byte of heap */
static char *mem_brk; /* Points to last byte of heap plus 1 */
static char *mem_max_addr; /* Max legal heap addr plus 1*/
/*
* mem_init - Initialize the memory system model
*/
void mem_init(void)
{
mem_heap = (char *)malloc(MAX_HEAP);
mem_brk = (char *)mem_heap;
mem_max_addr = (char *)(mem_heap + MAX_HEAP);
}
/*
* mem_sbrk - Simple model of the sbrk function. Extends the heap
* by incr bytes and returns the start address of the new area. In
* this model, the heap cannot be shrunk.
*/
void *mem_sbrk(int incr)
{
char *old_brk = mem_brk;
if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
errno = ENOMEM;
fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
return (void *)-1;
}
mem_brk += incr;
return (void *)old_brk;
}
问题：在mm.c中增加函数printblocks()，功能为扫描整个堆，并输出已分配块和空闲块的数量。在mm_free()函数的最后调用此函数。
2、在分配器中，将搜索策略由首次适配改为最佳适配策略。
3、在mm.c中增加函数mm_realloc()，其功能与realloc()功能一致。编写一个程序测试realloc是否成功。
4、在隐式空闲链表的基础上，实现简单分离存储。
5、将隐式空闲链表改为显式空闲链表。
