Malloc Lab 记录

by Gu Wei
2021年11月

1. 准备

该实验主要是让我们模拟一个动态分配器，实现mm_init、mm_malloc、mm_free和mm_realloc函数。handout里提供了两个简单的验证文件short1-bal.rep和short2-bal.rep来测试我们算法的内存利用率和吞吐量，可以调用./mdriver -f short1-bal.rep -V来查看单个文件的测试结果。该课程的其他测试数据可以从GitHub下载，得到一个trace文件夹，然后调用./mdriver -t ./trace -V来查看测试结果。

本实验只需要看书Section 9.9就可以完成了。书上给出了采用first hit policy隐式空闲链表的实现，而懒惰的我稍微改改抄抄就完成了next fit policy的隐式空闲链表。

2. 代码

​x
1
/*
2
 * mm-naive.c - The fastest, least memory-efficient malloc package.
3
 * 
4
 * In this naive approach, a block is allocated by simply incrementing
5
 * the brk pointer.  A block is pure payload. There are no headers or
6
 * footers.  Blocks are never coalesced or reused. Realloc is
7
 * implemented directly using mm_malloc and mm_free.
8
 *
9
 * NOTE TO STUDENTS: Replace this header comment with your own header
10
 * comment that gives a high level description of your solution.
11
 */
12
#include <stdio.h>
13
#include <stdlib.h>
14
#include <assert.h>
15
#include <unistd.h>
16
#include <string.h>
17

18
#include "mm.h"
19
#include "memlib.h"
20

21
/*********************************************************
22
 * NOTE TO STUDENTS: Before you do anything else, please
23
 * provide your team information in the following struct.
24
 ********************************************************/
25
team_t team = {
26
    /* Team name */
27
    "ateam",
28
    /* First member's full name */
29
    "Harry Bovik",
30
    /* First member's email address */
31
    "bovik@cs.cmu.edu",
32
    /* Second member's full name (leave blank if none) */
33
    "",
34
    /* Second member's email address (leave blank if none) */
35
    ""
36
};
37

38
/* single word (4) or double word (8) alignment */
39
#define ALIGNMENT 8
40

41
/* rounds up to the nearest multiple of ALIGNMENT */
42
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
43

44

45
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
46

47
/* Basic constants and macros */
48
#define WSIZE 4 /* Word and header/footer size (bytes) */
49
#define DSIZE 8 /* Double word size (bytes) */
50
#define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */
51

52
#define MAX(x, y) ((x) > (y)? (x) : (y))
53

54
/* Pack a size and allocated bit into a word */
55
#define PACK(size, alloc) ((size) | (alloc))
56

57
/* Read and write a word at address p */
58
#define GET(p) (*(unsigned int *)(p))
59
#define PUT(p, val) (*(unsigned int *)(p) = (val))
60

61
/* Read the size and allocated fields from address p */
62
#define GET_SIZE(p) (GET(p) & ~0x7)
63
#define GET_ALLOC(p) (GET(p) & 0x1)
64

65
/* Given block ptr bp, compute address of its header and footer */
66
#define HDRP(bp) ((char *)(bp) - WSIZE)
67
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
68

69
/* Given block ptr bp, compute address of next and previous blocks */
70
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
71
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
72

73
static void *extend_heap(size_t words);
74
static void *find_fit(size_t asize);
75
static void place(void *bp, size_t asize);
76
static void *coalesce(void *bp);
77

78
static char *heap_listp;
79
static char *pre_listp; /* next fit policy */
80

81
static void *extend_heap(size_t words)
82
{
83
    char *bp;
84
    size_t size;
85

86
    /* Allocate an even number of words to maintain alignment */
87
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
88
    if ((long)(bp = mem_sbrk(size)) == -1)
89
        return NULL;
90

91
    /* Initialize free block header/footer and the epilogue header */
92
    PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
93
    PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
94
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */
95

96
    /* Coalesce if the previous block was free */
97
    return coalesce(bp);
98
}
99
/* 
100
 * mm_init - initialize the malloc package.
101
 */
102
int mm_init(void)
103
{
104
    /* Create the initial empty heap */
105
    if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1)
106
        return -1;
107
    PUT(heap_listp, 0); /* Alignment padding */
108
    PUT(heap_listp + (1*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
109
    PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
110
    PUT(heap_listp + (3*WSIZE), PACK(0, 1)); /* Epilogue header */
111
    heap_listp += (2*WSIZE);
112
    pre_listp = heap_listp;
113
    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
114
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL)
115
        return -1;
116
    return 0;
117
}
118

119

120
static void *find_fit(size_t asize)
121
{
122
    void *bp;
123

124
    for (bp = pre_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
125
    {
126
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
127
            return bp;
128
    }
129
    for (bp = heap_listp; bp != pre_listp; bp = NEXT_BLKP(bp))
130
    {
131
        if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
132
            return bp;
133
    }
134
    return NULL;
135
}
136

137
static void place(void *bp, size_t asize)
138
{
139
    size_t csize = GET_SIZE(HDRP(bp));
140
    
141
    if ((csize - asize) >= (2*DSIZE)) { /* split */
142
        PUT(HDRP(bp),PACK(asize,1));
143
        PUT(FTRP(bp),PACK(asize,1));
144
        PUT(HDRP(NEXT_BLKP(bp)),PACK(csize - asize,0));
145
        PUT(FTRP(NEXT_BLKP(bp)),PACK(csize - asize,0));
146
    }
147
    else {
148
        PUT(HDRP(bp),PACK(csize,1));
149
        PUT(FTRP(bp),PACK(csize,1));
150
    }
151
    pre_listp = bp;
152
}
153
/* 
154
 * mm_malloc - Allocate a block by incrementing the brk pointer.
155
 *     Always allocate a block whose size is a multiple of the alignment.
156
 */
157
void *mm_malloc(size_t size)
158
{
159
    size_t asize; /* Adjusted block size */
160
    size_t extendsize; /* Amount to extend heap if no fit */
161
    char *bp;
162
    
163
    /* Ignore spurious requests */
164
    if (size == 0)
165
        return NULL;
166
    
167
    /* Adjust block size to include overhead and alignment reqs. */
168
    if (size <= DSIZE)
169
        asize = 2*DSIZE;
170
    else
171
        asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
172
    
173
    /* Search the free list for a fit */
174
    if ((bp = find_fit(asize)) != NULL) {
175
        place(bp, asize);
176
        return bp;
177
    }
178

179
    /* No fit found. Get more memory and place the block */
180
    extendsize = MAX(asize,CHUNKSIZE);
181
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
182
        return NULL;
183
    place(bp, asize);
184
    return bp;
185
}
186

187
static void *coalesce(void *bp)
188
{
189
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
190
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
191
    size_t size = GET_SIZE(HDRP(bp));
192

193
    if (prev_alloc && next_alloc) {             /* Case 1 */ 
194
        pre_listp = bp;
195
        return bp;
196
    }
197

198
    else if (prev_alloc && !next_alloc) {       /* Case 2 */
199
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
200
        PUT(HDRP(bp), PACK(size, 0));
201
        PUT(FTRP(bp), PACK(size,0));
202
    }
203

204
    else if (!prev_alloc && next_alloc) {       /* Case 3 */
205
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
206
        PUT(FTRP(bp), PACK(size, 0));
207
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
208
        bp = PREV_BLKP(bp);
209
        
210
    }
211

212
    else {                                      /* Case 4 */
213
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
214
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
215
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
216
        bp = PREV_BLKP(bp);
217
    }
218
    pre_listp = bp;
219
    return bp;
220
}
221
/*
222
 * mm_free - Freeing a block does nothing.
223
 */
224
void mm_free(void *bp)
225
{
226
    size_t size = GET_SIZE(HDRP(bp));
227

228
    PUT(HDRP(bp), PACK(size, 0));
229
    PUT(FTRP(bp), PACK(size, 0));
230
    coalesce(bp);
231
}
232

233

234
/*
235
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
236
 */
237
void *mm_realloc(void *ptr, size_t size)
238
{
239
    if (ptr == NULL)
240
        return mm_malloc(size);
241
    if (size == 0) {
242
        mm_free(ptr);
243
        return NULL;
244
    }
245

246
    void *newptr;
247
    size_t newSize, oldSize;
248
    newptr = mm_malloc(size);
249
    if (newptr == NULL)
250
        return NULL;
251
    oldSize = GET_SIZE(HDRP(ptr));
252
    newSize = GET_SIZE(HDRP(newptr));
253
    if (oldSize < newSize)
254
        newSize = oldSize;
255
    memcpy(newptr, ptr, newSize - DSIZE);
256
    mm_free(ptr);
257
    return newptr;
258
}

事实上只需要写mm_realloc函数以及修改find_fit就可以了。其他函数要么在文本中有，要么在课后练习的答案中有。

3. 测试

xxxxxxxxxx
16
1
Results for mm malloc:
2
trace  valid  util     ops      secs  Kops
3
 0       yes   90%    5694  0.001195  4766
4
 1       yes   93%    5848  0.000806  7257
5
 2       yes   94%    6648  0.002441  2724
6
 3       yes   96%    5380  0.002535  2122
7
 4       yes   66%   14400  0.000097148607
8
 5       yes   89%    4800  0.002055  2336
9
 6       yes   87%    4800  0.002005  2394
10
 7       yes   55%   12000  0.013150   913
11
 8       yes   51%   24000  0.006653  3608
12
 9       yes   26%   14401  0.081437   177
13
10       yes   34%   14401  0.001959  7349
14
Total          71%  112372  0.114333   983
15

16
Perf index = 43 (util) + 40 (thru) = 83/100

trace9和trace10测试了mm_realloc函数，可见mm_realloc函数的空间利用率（util）相当的低。这是因为我们的实现相当的naive。如果想要提高空间利用率，可以realloc时先尝试合并前后空闲块，并尝试在原先的位置放置数据。但是懒惰的我不想再为此写一个coalesce函数了。

4. 就这？

对书上代码的稍微修改就可以达到83/100的分数，此时可能只用了半天不到的时间。但是这个lab其实远不只如此。malloclab的实现还有以下几种选择：

• 显式空闲链表：将所有的free block数链接起来。缩短allocation time，但是会增加内部碎片。
• 分离适配：维护多个链表，每个链表中的块大小都在一定的范围之内，不同链表的块的大小范围不同。相当麻烦的编程，优秀的空间利用率和速度。GNU中的malloc就采用该思路。如果按该思路实现该lab可以得到满分，只不过消失了一周的时间。
• 伙伴系统：块大小均为2的幂次方。不错的寻找和合并速度。但是造成很多内部碎片，不适合通常意义下的allocator。不过对于一个频繁申请2的幂次方块的程序来说，伙伴系统将是不错的选择。

个人认为如果想要实现分离适配的话，应该算是所有实验中编程量和编程难度最大的一个lab了。

5. 写在后面

本人于2021/11/14水完了malloc lab，用时一天左右。malloc lab其实相当有挑战性，只不过懒惰的我明白放弃其实是种智慧。最后一个poxy lab应该不会做了，套接字可能就直接上自顶向下了。可能本篇作为所有lab的收尾有点心不甘，但是又何妨。最后以csapp官网的一句话收尾malloc lab：

One of our favorite labs. When students finish this one, they really understand pointers!