forest

实现

一个动态内存申请器，能实现：malloc， free， realloc；

前置知识

CSAPP第9章：动态内存申请器，内存中的堆，链表；

蛋疼的检测工具

首先需要；

1
gcc -Wall -O2 -m32   -c -o mdriver.o mdriver.c

然后；

1
make mdriver mdriver.o mm.o memlib.o fsecs.o fcyc.o clock.o ftimer.o

以上两个出错请用下面指令解决；

1
sudo apt-get install gcc-multilib

下载出错请更新镜像，或者添加清华园下载路径：

1
2
deb http://mirrors.tuna.tsinghua.edu.cn/kali kali-rolling main contrib non-free
deb-src https://mirrors.tuna.tsinghua.edu.cn/kali kali-rolling main contrib non-free

输入以下命令打开下载源：

1
sudo vim /etc/apt/sources.list

按 i 进入编辑模式，完成后输入 :w 保存， :q退出；之后输入一遍：

1
sudo apt-get update && apt-get upgrade && apt-get dist-upgrade

然后就能输入第三条指令了，接着编译就行了；

其次，traces是缺失的，需要下载以进行检测；地址：

https://github.com/Davon-Feng/CSAPP-Labs/tree/master/yzf-malloclab-handout/traces

将10个文件装入文件夹，将文件夹放到和 mdriver 同级的地方；

并修改config.h里第15行的内容为自己的traces文件夹目录；

分析

  • 需要内存空间模拟堆；
  • 需要模拟已分配和未分配的块；
  • 需要管理这个空间（开始，结束，填充）；
  • 需要操控这个空间（放置，分割，合并，释放）；

已知内容

mem_heap，mem_brk两个指针分别指向堆的开始和结尾，mem_sbrk函数可以调节brk并返回旧brk的值，两个指针已初始化相等；

堆中的最小单位为4字节（1字），第一个字是双字边界对齐不使用的填充字；后面跟着两字的序言块，分配器使用私有的全局变量 heap_listp 指向序言块的第二个字开头；以一个0内容的已分配块作为结束的一个字；

使用隐式空闲链表，下一次适配，边界标记的堆块格式（最小4字，开头和结尾2字是标志字），立即合并；

标志字由整个块的大小或上分配位组成；

代码

I . 操作空闲链表的常数和宏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#define WSIZE 4     //一字的字节
#define DSIZE 8     //两字的字节
#define CHUNKSIZE (1<<12)       //延展一次堆的字节数

#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define MIN(x,y) ((x) < (y) ? (x) : (y))

//大小或上分配位打包的标志字
#define PACK(size,alloc) ((size) | (alloc))

//读写p指针处的一个字
#define GET(p) (*(unsigned int *)(p))       
#define PUT(p,val) (*(unsigned int *)(p) = (val))

//读取标志字中的大小和分配状态
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

//给出开头或结尾标志字的位置(bp指针指向块的有效载体)
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) - DSIZE + GET_SIZE(HDRP(bp)))

//给出前一个或下一个块的bp指针
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))

static char * heap_listp;
//下次适配记录之前的块
static char * prev_listp;

p是一个void * 指针，所以强制转换是必要的；

II . 创建空闲列表（堆）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int mm_init(void)
{   
    //分配4个字(1个初始填充，2个序言，1个结尾)
    if((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
        return -1;
    PUT(heap_listp,0);
    PUT(heap_listp + WSIZE,PACK(DSIZE,1));
    PUT(heap_listp + (2 * WSIZE),PACK(DSIZE,1));
    PUT(heap_listp + (3*WSIZE),PACK(0,1));
    heap_listp += (2*WSIZE);
    prev_listp = heap_listp;

    //延展空闲块
    if(extend_heap(CHUNKSIZE/WSIZE) == NULL)
        return -1;
    return 0;
}

static void * extend_heap(size_t words)
{
    char * bp;
    size_t size;

    //满足2字对齐
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if((long)(bp = mem_sbrk(size)) == -1)
        return NULL;
    
    //设置填充空闲块的头和尾，以及延展一个结束字
    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));
    PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));

    //合并空闲块，如果前面是的话
    prev_listp = coalesce(bp);
}

mm_init函数在创建初始堆空间；extend_heap函数在延展空闲块，用在init里，当然也可以用在当申请空间不足时的地方，所以单独成为一个函数；coalesce之后会讲到，是合并空闲块的函数，在填充和释放时用到；

注意，首次适配所记录的当前块指针如果被向前合并，则记录指针也需要随之改变，所以最好运用合并函数的地方都使其返回的值成为prev_listp；

III . 释放和合并块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void mm_free(void * bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    //设置头尾分配位0
    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));

    prev_listp = coalesce(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));

    //4种情况，前后块都是分配的，前后块都没分配，前后块有一者分配
    if(prev_alloc && next_alloc)
    {	
    	return bp;
	}    
    else if(!prev_alloc && next_alloc)
    {
        size += GET_SIZE(FTRP(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)
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp),PACK(size,0));
        PUT(FTRP(bp),PACK(size,0));
    }
    else
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp))) + GET_SIZE(FTRP(PREV_BLKP(bp)));
        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp = PREV_BLKP(bp);
    }
    return bp;
}

在第二个else if 的地方，HDRP需要写前面，因为FTRP会用HDRP处的内容；

IV . 放置和分割块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
void *mm_malloc(size_t size)
{   
    // 调整后大小
    size_t asize;
    //延展大小
    size_t extendsize;
    char *bp;

    //忽视无用请求
    if(size == 0)
        return NULL;
    
    //调整对齐要求
    if(size <= DSIZE)
        asize = 2 * DSIZE;
    else
        //向上取整
        asize = ((size + DSIZE + (DSIZE - 1)) / DSIZE) * DSIZE;

    //放置块
    if((bp = find_fit(asize)) != NULL)
    {
        place(bp,asize);
        return bp;
    }

    //空间不够延展
    extendsize = MAX(asize,CHUNKSIZE);
    if((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    place(bp,asize);
    return bp;
}

static void *find_fit(size_t asize)
{
    void * bp;
    
    //初始化使prev_listp指向了序言块
    for(bp = prev_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
        {
            prev_listp = bp;
            return bp;
        }
    }
    //后面找没有之后从头找
    for(bp = heap_listp; bp != prev_listp; bp = NEXT_BLKP(bp))
    {
        if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
        {
            prev_listp = bp;
            return bp;
        }
    }
    return NULL;
}

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));
    }
}

V . 重分配块大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void *mm_realloc(void *bp, size_t size)
{
    void * old_bp = bp;
    void * new_bp;
    size_t oldsize, newsize;

    //创建新的分配块
    new_bp = mm_malloc(size);
    if(new_bp == NULL)
        return NULL;
    oldsize = GET_SIZE(HDRP(old_bp));
    newsize = GET_SIZE(HDRP(new_bp));
    //比较新旧大小，如果新的更大，则复制原数据过去，如果更小，复制小的长度个原数据
    if(oldsize < newsize)
        newsize = oldsize;
    //取消结尾字
    memcpy(new_bp, old_bp, newsize-WSIZE);
    mm_free(old_bp);
    return new_bp;
}

VI . 检测

将代码打包到mm.c，使用之前的编译命令，搞出有代码的 mdriver；输入以检测：

1
./mdriver -V

如图：

check

总结

至此，实现了所分析的内容：

模拟空间，填充——extend_heap；

已分配和未分配的块——有头尾的列表模式以及宏定义的操作；

开头结尾——mm_init；

以及有小标题的放置，分割，释放，合并小函数；

forest