csapp-malloclab
MorphLing
1月 23, 2021
主要尝试了两种方法，隐式空闲链表(implicit free list)和隔离空闲链表(segregated free list)，当然还有一种显式空闲链表法，但是感觉类似于单个的隔离空闲链表。
隐式空闲链表
每一段内存空间都有一个header和一个footer记录这段内存空间的大小和存储状态。不同的分配策略对得分影响非常大，first fit只有53分，改成next fit后有84分。
宏定义
#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)))
#define MAXHEAP (20 * (1 << 20))
#define BLOCK (1 << 12)
#define WSIZE 4
#define DSIZE 8
#define GET(x) (*((unsigned int*)(x)))
#define PUT(x, y) (*((unsigned int*)(x)) = (y))
#define PACK(x, y) ((x) | (y))
#define GETSZ(x) (GET(x) & (~0x7))
#define GETAL(x) (GET(x) & 0x1)
#define HD(x) ((x) - WSIZE)
#define FT(x) ((x) + GETSZ(HD(x)) - DSIZE)
#define PRE(x) ((x) - GETSZ((x) - DSIZE))
#define SUF(x) ((x) + GETSZ(HD(x)))
#define max(a, b) ((a) > (b) ? (a) : (b))
一部分宏定义和书上略有不同，但功能基本一样。
堆扩张
堆扩张要求双字对齐，所以如果字数为单数则加一。
void *extend(size_t words) {
void *bp;
if (words & 1) words++;
size_t size = words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return (void *)-1;
PUT(HD(bp), PACK(size, 0));
PUT(FT(bp), PACK(size, 0));
PUT(HD(SUF(bp)), PACK(0, 1));
bp = combine(bp);
return bp;
}
初始化
int mm_init(void)
{
head = mem_sbrk(4 * WSIZE);
PUT(head, PACK(0, 1));
PUT(head + 1 * WSIZE, PACK(DSIZE, 1));
PUT(head + 2 * WSIZE, PACK(DSIZE, 1));
PUT(head + 3 * WSIZE, PACK(0, 1));
head += 2 * WSIZE;
if (extend(BLOCK / WSIZE) == (void *)-1)
return -1;
return 0;
}
在最前面设置一个大小为8个字节，只有一个header和一个footer的已分配空间作为边界，并将链表头设置在这块空间上。
分配
分配时需要判断空闲块大小减去需要的内存大小后，剩下的部分是否能作为一个新的空闲块。
因为一个空闲块需要包含header和footer，所以这要求每一个空闲块至少为8个字节。
这里先用的是first fit的方式，也就是从链表头开始，找到第一个空间足够的地址，效率较低。
void *find_fit(size_t size) {
void *bp;
for (bp = head; GETSZ(HD(bp)) > 0; bp = SUF(bp)) {
if (!GETAL(HD(bp)) && GETSZ(HD(bp)) >= size) {
return bp;
}
}
size_t newsize = max(BLOCK, size);
bp = extend(newsize / WSIZE);
return bp;
}
void *mm_malloc(size_t size) {
int newsize = ALIGN(size + SIZE_T_SIZE);
void *bp = find_fit(newsize);
if (bp == (void *)-1) return bp;
size_t space = GETSZ(HD(bp));
PUT(HD(bp), PACK(space, 1));
PUT(FT(bp), PACK(space, 1));
if (space - newsize >= DSIZE) {
PUT(HD(bp), PACK(newsize, 1));
PUT(FT(bp), PACK(newsize, 1));
PUT(HD(SUF(bp)), PACK(space - newsize, 0));
PUT(FT(SUF(bp)), PACK(space - newsize, 0));
}
return bp;
}
也可以改成next fit的分配策略，效率较高（同时释放部分也要作相应修改，避免prefit指向不存在的内存地址）
void *next_fit(size_t size) {
void *bp;
for (bp = prefit; GETSZ(HD(bp)) > 0; bp = SUF(bp)) {
if (!GETAL(HD(bp)) && GETSZ(HD(bp)) >= size) {
prefit = bp;
return bp;
}
}
for (bp = head; bp != prefit; bp = SUF(bp)) {
if (!GETAL(HD(bp)) && GETSZ(HD(bp)) >= size) {
prefit = bp;
return bp;
}
}
size_t newsize = max(size, CHUNKSIZE);
bp = extend(newsize / WSIZE);
prefit = bp;
return bp;
}
合并
void combine_with_suffix(void *ptr) {
size_t suf_size = GETSZ(HD(SUF(ptr)));
if (prefit == SUF(ptr)) prefit = ptr;
PUT(FT(ptr), 0);
PUT(HD(SUF(ptr)), 0);
PUT(HD(ptr), PACK(GETSZ(HD(ptr)) + suf_size, 0));
PUT(FT(ptr), PACK(GETSZ(HD(ptr)), 0));
}
void *combine(void *ptr) {
size_t pre_alloc = GETAL(HD(PRE(ptr)));
size_t suf_alloc = GETAL(HD(SUF(ptr)));
if (pre_alloc && suf_alloc)
return ptr;
if (pre_alloc && !suf_alloc) {
combine_with_suffix(ptr);
return ptr;
}
if (!pre_alloc && suf_alloc) {
void *bp = PRE(ptr);
combine_with_suffix(PRE(ptr));
return bp;
}
if (!pre_alloc && !suf_alloc) {
void *bp = PRE(ptr);
combine_with_suffix(ptr);
combine_with_suffix(PRE(ptr));
return bp;
}
return (void *)-1;
}
如果当前空闲块前后的内存空间也是空闲的，那么就合并成一个空闲块。
释放
void mm_free(void *ptr)
{
size_t size = GETSZ(HD(ptr));
PUT(HD(ptr), PACK(size, 0));
PUT(FT(ptr), PACK(size, 0));
combine(ptr);
}
再分配
没有特殊处理，就是free+malloc+memcpy
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;
copySize = GETSZ(HD(oldptr));
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
隔离空闲链表
这个方法相对来说比较复杂，但得分也可以进一步提高到90。
思路就是创建多个链表，把所有空闲段按照大小分到不同的链表里，跟显式分配一样，空闲块的前两个字分别存放的是链表前驱和后继的内存地址。这样的好处是分配内存时，寻址的时间减少，但缺点是内存碎片可能较多，内存空间利用率较低。
一个优化是在分配内存时，判断需要分配的内存大小是否超过某个临界值（这里根据测试选择的是96），若超过了则放在空闲段的尾部，把前半段切割出来，否则放在头部。
原理是这样可以使得较大的块相对集中， 较小的块也相对集中，不容易出现两个大块之间被某个小块隔开的情况，可以减少内存碎片。
根据空间大小找对应链表是通过get_target函数实现的，其实就是取以2为底的对数。
其他的好像也没啥了。
/*
* Segregated free list.
* scores:90/100
*/
#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 */
"Yunfan Li",
/* First member's full name */
"Yunfan Li",
/* First member's email address */
"10195501416@stu.ecnu.edu.cn",
/* 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 MAXLIST 25
/* 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<<8)
#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)))
/* 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))
inline static size_t get_asize(size_t size);
inline static size_t get_target(size_t size);
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);
static void delete_node(void *bp);
void *seg_free_lists[MAXLIST];
void *heap_listp;
int mm_init(void) {
for (size_t i = 0; i < MAXLIST; i++) {
seg_free_lists[i] = NULL;
}
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0);
PUT(heap_listp + 1 * WSIZE, PACK(DSIZE, 1));
PUT(heap_listp + 2 * WSIZE, PACK(DSIZE, 1));
PUT(heap_listp + 3 * WSIZE, PACK(0, 1));
heap_listp += 2 * WSIZE;
if (extend_heap(INITCHUNKSIZE/WSIZE) == NULL)
return -1;
return 0;
}
void *mm_malloc(size_t size)
{
size_t asize, search;
size_t extendsize;
char *bp = NULL;
if (size == 0)
return NULL;
asize = get_asize(size);
size_t target = get_target(asize);
for (; target < MAXLIST; target++) {
if ((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) {
extendsize = MAX(asize,CHUNKSIZE);
if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
return NULL;
}
bp = place(bp, asize);
return bp;
}
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);
}
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;
copySize = GET_SIZE(HDRP(oldptr));
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
inline static size_t get_target(size_t size) {
size_t tar = 0;
for (size_t j = size; (j > 1) && tar < MAXLIST; j >>= 1) tar++;
return tar;
}
inline 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 *extend_heap(size_t words)
{
size_t size = (words % 2) ? words + 1 : words;
size *= WSIZE;
char *bp = mem_sbrk(size);
if (bp == (void *)-1) return NULL;
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
bp = coalesce(bp);
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;
if (!next_alloc && !prev_alloc) {
size = GET_SIZE(HDRP(bp)) + GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
delete_node(PREV_BLKP(bp));
delete_node(NEXT_BLKP(bp));
bp = PREV_BLKP(bp);
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
} else if (!next_alloc && prev_alloc) {
size = GET_SIZE(HDRP(bp)) + 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 (next_alloc && !prev_alloc) {
size = GET_SIZE(HDRP(bp)) + GET_SIZE(HDRP(PREV_BLKP(bp)));
delete_node(PREV_BLKP(bp));
bp = PREV_BLKP(bp);
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
insert_node(bp);
return bp;
}
static void *place(void *bp, size_t asize)
{
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);
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));
}
return bp;
}
static void insert_node(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
size_t tar = get_target(size);
void *succ = seg_free_lists[tar];
seg_free_lists[tar] = bp;
if (succ != NULL) SET_PTR(PRED_PTR(succ), bp);
SET_PTR(SUCC_PTR(bp), succ);
SET_PTR(PRED_PTR(bp), NULL);
}
static void delete_node(void *bp)
{
if (PRED(bp) != NULL)
SET_PTR(SUCC_PTR(PRED(bp)), SUCC(bp));
else {
size_t size = GET_SIZE(HDRP(bp));
size_t tar = get_target(size);
seg_free_lists[tar] = SUCC(bp);
}
if (SUCC(bp) != NULL) SET_PTR(PRED_PTR(SUCC(bp)), PRED(bp));
}