[施工完成] CSAPP Malloc lab

Mar 14, 2021 · 9 min read · CSAPP

背景

动手实现一个memory allocator,体会core到爆炸的乐趣(不是

trace file 结构分析

trace file 是对allocator的输入的描述，可以从mdriver.c中的

1static trace_t *read_trace(char *tracedir, char *filename);

看到Parse的逻辑，从而得到trace file的结构。

1  fscanf(tracefile, "%d", &(trace->sugg_heapsize)); /* not used */
2  fscanf(tracefile, "%d", &(trace->num_ids));
3  // 似乎只有num_ops用到了。。
4  fscanf(tracefile, "%d", &(trace->num_ops));
5  fscanf(tracefile, "%d", &(trace->weight)); /* not used */

trace file起始位置的4个数的含义，其中第二个和第三个比较重要。 num_ids表示一共有多少个不同的内存块(对应后续的指令可以显示指定操作哪个内存块，从而确保allocator对malloc和free的顺序没有任何依赖的保证)，num_ops表示操作数，也就是malloc(对应'a'),realloc(对应'r'),free(对应'f')三种操作的个数。

 1 while (fscanf(tracefile, "%s", type) != EOF) {
 2    switch (type[0]) {
 3      case 'a':
 4        fscanf(tracefile, "%u %u", &index, &size);
 5        trace->ops[op_index].type = ALLOC;
 6        trace->ops[op_index].index = index;
 7        trace->ops[op_index].size = size;
 8        max_index = (index > max_index) ? index : max_index;
 9        break;
10      case 'r':
11        fscanf(tracefile, "%u %u", &index, &size);
12        trace->ops[op_index].type = REALLOC;
13        trace->ops[op_index].index = index;
14        trace->ops[op_index].size = size;
15        max_index = (index > max_index) ? index : max_index;
16        break;
17      case 'f':
18        fscanf(tracefile, "%ud", &index);
19        trace->ops[op_index].type = FREE;
20        trace->ops[op_index].index = index;
21        break;
22      default:
23        printf("Bogus type character (%c) in tracefile %s\n", type[0], path);
24        exit(1);
25    }
26    op_index++;
27  }
28

对于每一个操作，如果是malloc/relloc, 后面两个参数分别表示操作几号内存块，以及需要分配的内存大小是多少。如果是free,则只有一个参数，表示要操作几号内存块

implicit free list

这种也就是CS:APP3e text中着重描述的那种，补充了一些checker逻辑，放在这里作为baseline

结构图如下:

这种是带一个boundary tag的，也就是一个footer. footer完全是header内容的副本。这样做的好处是可以很容易从当前block找到上一个block,只需要常数复杂度的操作，否则需要O(n)复杂度整个遍历一遍。对应的代价是有效载荷的比例变低了。

  1
  2int mm_init(void) {
  3  /* Create the initial empty heap */
  4  if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)  // line:vm:mm:begininit
  5    return -1;
  6  PUT(heap_listp, 0);                            /* Alignment padding */
  7  PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* Prologue header */
  8  PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
  9  PUT(heap_listp + (3 * WSIZE), PACK(0, 1));     /* Epilogue header */
 10  heap_listp += (2 * WSIZE);                     // line:vm:mm:endinit
 11  /* $end mminit */
 12
 13#ifdef NEXT_FIT
 14  rover = heap_listp;
 15#endif
 16  /* $begin mminit */
 17
 18  /* Extend the empty heap with a free block of CHUNKSIZE bytes */
 19  if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;
 20  //   checkheap(1);
 21  return 0;
 22}
 23/* $end mminit */
 24
 25/*
 26 * mm_malloc - Allocate a block with at least size bytes of payload
 27 */
 28/* $begin mmmalloc */
 29void *mm_malloc(size_t size) {
 30  size_t asize;      /* Adjusted block size */
 31  size_t extendsize; /* Amount to extend heap if no fit */
 32  char *bp;
 33
 34  /* $end mmmalloc */
 35  if (heap_listp == 0) {
 36    mm_init();
 37  }
 38  /* $begin mmmalloc */
 39  /* Ignore spurious requests */
 40  if (size == 0) return NULL;
 41
 42  /* Adjust block size to include overhead and alignment reqs. */
 43  if (size <= DSIZE)    // line:vm:mm:sizeadjust1
 44    asize = 2 * DSIZE;  // line:vm:mm:sizeadjust2
 45  else
 46    asize = DSIZE *
 47            ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);  // line:vm:mm:sizeadjust3
 48
 49  /* Search the free list for a fit */
 50  if ((bp = find_fit(asize)) != NULL) {  // line:vm:mm:findfitcall
 51    place(bp, asize);                    // line:vm:mm:findfitplace
 52    return bp;
 53  }
 54
 55  /* No fit found. Get more memory and place the block */
 56  extendsize = MAX(asize, CHUNKSIZE);  // line:vm:mm:growheap1
 57  if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
 58    return NULL;     // line:vm:mm:growheap2
 59  place(bp, asize);  // line:vm:mm:growheap3
 60  mm_checkheap(0);
 61
 62  return bp;
 63}
 64/* $end mmmalloc */
 65
 66/*
 67 * mm_free - Free a block
 68 */
 69/* $begin mmfree */
 70void mm_free(void *bp) {
 71  /* $end mmfree */
 72  if (bp == 0) return;
 73
 74  /* $begin mmfree */
 75  size_t size = GET_SIZE(HDRP(bp));
 76  /* $end mmfree */
 77  if (heap_listp == 0) {
 78    mm_init();
 79  }
 80  /* $begin mmfree */
 81
 82  PUT(HDRP(bp), PACK(size, 0));
 83  PUT(FTRP(bp), PACK(size, 0));
 84  coalesce(bp);
 85}
 86
 87/* $end mmfree */
 88/*
 89 * coalesce - Boundary tag coalescing. Return ptr to coalesced block
 90 */
 91/* $begin mmfree */
 92static void *coalesce(void *bp) {
 93  size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
 94  size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
 95  size_t size = GET_SIZE(HDRP(bp));
 96
 97  if (prev_alloc && next_alloc) { /* Case 1 */
 98    return bp;
 99  }
100
101  else if (prev_alloc && !next_alloc) { /* Case 2 */
102    size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
103    PUT(HDRP(bp), PACK(size, 0));
104    PUT(FTRP(bp), PACK(size, 0));
105  }
106
107  else if (!prev_alloc && next_alloc) { /* Case 3 */
108    size += GET_SIZE(HDRP(PREV_BLKP(bp)));
109    PUT(FTRP(bp), PACK(size, 0));
110    PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
111    bp = PREV_BLKP(bp);
112  }
113
114  else { /* Case 4 */
115    size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
116    PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
117    PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
118    bp = PREV_BLKP(bp);
119  }
120  /* $end mmfree */
121#ifdef NEXT_FIT
122  /* Make sure the rover isn't pointing into the free block */
123  /* that we just coalesced */
124  if ((rover > (char *)bp) && (rover < NEXT_BLKP(bp))) rover = bp;
125#endif
126  /* $begin mmfree */
127  return bp;
128}
129/* $end mmfree */
130
131/*
132 * mm_realloc - Naive implementation of realloc
133 */
134void *mm_realloc(void *ptr, size_t size) {
135  size_t oldsize;
136  void *newptr;
137
138  /* If size == 0 then this is just free, and we return NULL. */
139  if (size == 0) {
140    mm_free(ptr);
141    return 0;
142  }
143
144  /* If oldptr is NULL, then this is just malloc. */
145  if (ptr == NULL) {
146    return mm_malloc(size);
147  }
148
149  newptr = mm_malloc(size);
150
151  /* If realloc() fails the original block is left untouched  */
152  if (!newptr) {
153    return 0;
154  }
155
156  /* Copy the old data. */
157  oldsize = GET_SIZE(HDRP(ptr));
158  if (size < oldsize) oldsize = size;
159  memcpy(newptr, ptr, oldsize);
160
161  /* Free the old block. */
162  mm_free(ptr);
163
164  return newptr;
165}
166
167/*
168 * mm_checkheap - Check the heap for correctness
169 */
170void mm_checkheap(int verbose) { checkheap(verbose); }
171
172/*
173 * The remaining routines are internal helper routines
174 */
175
176/*
177 * extend_heap - Extend heap with free block and return its block pointer
178 */
179/* $begin mmextendheap */
180static void *extend_heap(size_t words) {
181  char *bp;
182  size_t size;
183
184  /* Allocate an even number of words to maintain alignment */
185  size = (words % 2) ? (words + 1) * WSIZE
186                     : words * WSIZE;                  // line:vm:mm:beginextend
187  if ((long)(bp = mem_sbrk(size)) == -1) return NULL;  // line:vm:mm:endextend
188
189  /* Initialize free block header/footer and the epilogue header */
190  PUT(HDRP(bp), PACK(size, 0));
191  /* Free block header */  // line:vm:mm:freeblockhdr
192  PUT(FTRP(bp), PACK(size, 0));
193  /* Free block footer */  // line:vm:mm:freeblockftr
194  PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
195  /* New epilogue header */  // line:vm:mm:newepihdr
196
197  /* Coalesce if the previous block was free */
198  return coalesce(bp);  // line:vm:mm:returnblock
199}
200/* $end mmextendheap */
201
202/*
203 * place - Place block of asize bytes at start of free block bp
204 *         and split if remainder would be at least minimum block size
205 */
206/* $begin mmplace */
207/* $begin mmplace-proto */
208static void place(void *bp, size_t asize)
209/* $end mmplace-proto */
210{
211  size_t csize = GET_SIZE(HDRP(bp));
212
213  if ((csize - asize) >= (2 * DSIZE)) {
214    PUT(HDRP(bp), PACK(asize, 1));
215    PUT(FTRP(bp), PACK(asize, 1));
216    bp = NEXT_BLKP(bp);
217    PUT(HDRP(bp), PACK(csize - asize, 0));
218    PUT(FTRP(bp), PACK(csize - asize, 0));
219  } else {
220    PUT(HDRP(bp), PACK(csize, 1));
221    PUT(FTRP(bp), PACK(csize, 1));
222  }
223}
224/* $end mmplace */
225
226/*
227 * find_fit - Find a fit for a block with asize bytes
228 */
229/* $begin mmfirstfit */
230/* $begin mmfirstfit-proto */
231static void *find_fit(size_t asize)
232/* $end mmfirstfit-proto */
233{
234  /* $end mmfirstfit */
235
236#ifdef NEXT_FIT
237  /* Next fit search */
238  char *oldrover = rover;
239
240  /* Search from the rover to the end of list */
241  for (; GET_SIZE(HDRP(rover)) > 0; rover = NEXT_BLKP(rover))
242    if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover))))
243      return rover;
244
245  /* search from start of list to old rover */
246  for (rover = heap_listp; rover < oldrover; rover = NEXT_BLKP(rover))
247    if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover))))
248      return rover;
249
250  return NULL; /* no fit found */
251#else
252  /* $begin mmfirstfit */
253  /* First-fit search */
254  void *bp;
255
256  for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
257    if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
258      return bp;
259    }
260  }
261  return NULL; /* No fit */
262#endif
263}
264/* $end mmfirstfit */
265
266static void printblock(void *bp) {
267  size_t hsize, halloc, fsize, falloc;
268
269  checkheap(0);
270  hsize = GET_SIZE(HDRP(bp));
271  halloc = GET_ALLOC(HDRP(bp));
272  fsize = GET_SIZE(FTRP(bp));
273  falloc = GET_ALLOC(FTRP(bp));
274
275  if (hsize == 0) {
276    printf("%p: EOL\n", bp);
277    return;
278  }
279
280  printf("%p: header: [%ld:%c] footer: [%ld:%c]\n", bp, hsize,
281         (halloc ? 'a' : 'f'), fsize, (falloc ? 'a' : 'f'));
282}
283
284static void checkblock(void *bp) {
285  if ((size_t)bp % 8) printf("Error: %p is not doubleword aligned\n", bp);
286  if (GET(HDRP(bp)) != GET(FTRP(bp)))
287    printf("Error: header does not match footer\n");
288  // check last 3 bit: 001 or 000
289  int last_three_bit_value = GET_LAST_THREE_BIT(HDRP(bp));
290  printf("last three bit value:%d\n", last_three_bit_value);
291  if (last_three_bit_value != 0 && last_three_bit_value != 1) {
292    printf("ERROR:invalid blocks bp:%p\n", bp);
293  }
294}
295
296static void checkoverlap(void *bp, void *nxt) {
297  // [begin,end), 左闭右开区间
298  void *cur_end = FTRP(bp) + WSIZE;
299  void *nxt_begin = HDRP(nxt);
300  if (cur_end > nxt_begin) {
301    printf("ERROR: blocks overlap cur_end: %p  nxt_begin:%p \n", cur_end,
302           nxt_begin);
303  }
304}
305
306/*
307 * checkheap - Minimal check of the heap for consistency
308 */
309void checkheap(int verbose) {
310  printf("in checkheap verbose:%d\n", verbose);
311  char *bp = heap_listp;
312
313  if (verbose) printf("Heap (%p):\n", heap_listp);
314
315  // prologue block 双字大小(8字节)，并且是allocate的状态。
316  // 这里只检查了header，因为checkblock中检查了header和footer的一致性（指内容完全一致)
317  if ((GET_SIZE(HDRP(heap_listp)) != DSIZE) || !GET_ALLOC(HDRP(heap_listp)))
318    printf("Bad prologue header\n");
319  checkblock(heap_listp);
320
321  //连续空闲块的个数，遇到非free的清零，如果值大于等于2，说明有块躲过了合并
322  int free_block_cnt = 0;
323
324  // 遍历所有block. 除了epilogue
325  // block,所有block不管是allocate还是free,size都是大于0的
326  for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
327    if (verbose) printblock(bp);
328    checkblock(bp);
329
330    // 检查是否有没合并的free block
331    int alloc = GET_ALLOC(HDRP(bp));
332    if (!alloc) {
333      free_block_cnt++;
334      if (free_block_cnt >= 2) {
335        printf("contiguous free blocks that somehow escaped coalescing\n");
336        if (verbose) {
337          // 打印当前Block和上一个block
338          printblock(bp);
339          printblock(PREV_BLKP(bp));
340        }
341      }
342    } else {
343      free_block_cnt = 0;
344    }
345
346    // check (allocated) blocks overlap
347    // 查看当前block的footer地址是否小于下一个block的header地址
348    checkoverlap(bp, NEXT_BLKP(bp));
349  }
350
351  if (verbose) printblock(bp);
352  if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp))))
353    printf("Bad epilogue header\n");
354}
355

Explicit Free Lists

隐式列表的坏处是。。每次allocate的时候，需要遍历全部block去找free block. 显然，我们可以维护一个free list的链表，使得每次allocate的时候，只需要遍历free block 结构如图:

这里很巧妙的一点是，由于free block中的payload是没有被使用的，因此把上一个free block和下一个free block的地址都放在了当前free block的payload中，而没有单独维护一个数据结构。

需要注意的是，由于现在payload中存放了两个指针，因此目前一个block的最小size变成了16字节(heade,footer各4字节，payload要至少能放下两个指针，8字节，一共16字节)

还有几个值得一提的是比如序言快的设计，是一个header紧跟着一个footer,没有payload

序言快很重要的一点是, HDRP和FTPR中间没有payload, 这其实意味着，可以把footer当成bp, 往前4个字节就是header 因此把free_list_star 放在序言快的footer的部分，作为一个结尾标志。判断条件可以统一成SIZE(HEAD(bp))= 0 这里是个挺巧妙的做法

还有就是一些链表操作，原来leetcode里面的链表题还是有实际用处的2333

 1// remove node in free list
 2// a->b->c ，remove b的做法是，将a->next指向c,c->prev 指向a
 3// 特殊情况: bp是free list的初始节点，此时直接调整free_list_start
 4static void remove_node_from_free_list(void *bp) {
 5  if (GET_PREV_PTR(bp)) {
 6    SET_NEXT_PTR(GET_PREV_PTR(bp), GET_NEXT_PTR(bp));
 7  } else {
 8    free_list_start = GET_NEXT_PTR(bp);
 9  }
10  SET_PREV_PTR(GET_NEXT_PTR(bp), GET_PREV_PTR(bp));
11}
12
13// 向free list中插入node
14// 这里涉及插入到哪里的策略
15// 暂时使用头插法,也就是每次插入到free list的头部
16// 对于 b->c,插入a,做法是
17// a->next = free_list_start
18// a->prev = null
19// free_list_start->prev = a
20// free_list_start = a
21
22static void insert_node_in_free_list(void *bp) {
23  SET_NEXT_PTR(bp, free_list_start);
24  SET_PREV_PTR(free_list_start, bp);
25  SET_PREV_PTR(bp, NULL);
26  free_list_start = bp;
27}

经验就是，由于涉及到比较底层的操作。。还挺难写的。。可以多定义一些宏来帮助开发。。（嗯。。也就core了100多次把。。

完整的代码在这里 111qqz's github

参考链接

HarshTrivedi/malloc

[施工完成] CSAPP Malloc lab

背景

trace file 结构分析

implicit free list

Explicit Free Lists

参考链接

Posts in this Series

背景