CSAPP Malloc Lab
目标
实现一个简单的动态存储分配器。
评分标准
空间利用率应当减少internal 和 external fragmentation.
memory utilization
memory utilization = payload / heap size
fragmentation
internal fragmentation
external fragmentation
throughput
T 越接近Tlibc 吞吐量越高，也就是1s 内可以执行的op数量越多越好。
dynamic memory allocator
dynamic memory allocator分配heap的空间。
dynamic memory allocator 通过free list记录heap的free block, 收到free 请求的时候，查询free list 找到满足free request的block。
implicit free list 有多重查找free block 的方式，包括first fit, best fit, 和 next fit 等。
explicit free list 有多种insertion policy, 例如LIFO, 和address-ordered 等。
所以使用seglist 和first-fit.
allocator 设计重点
explicit list 和 seglist 还需要考虑
项目文件
主要是mm.c文件
介绍项目文件
memlib.c
return (void *)-1 是一个 C 语言中的语句，它的含义是将一个指针类型的值设置为 -1，然后将其转换为 void 指针类型，并返回。这通常用于表示一个特殊的错误条件或者指示函数执行失败。
mm.c 宏定义和常量
sizeof函数的单位是byte。
ALIGN 找到最小的alignment的倍数。
mm.c 文件需要实现的函数
mm_init 初始化heap和free list
mm_malloc 返回指向已经分配的block的payload的指针
mm_free 释放指向block的指针，为了避免fragmentation, 还需要执行free block 的合并。
seglist 设计和实现
指针操作
size = payload + header + footer
free list 函数操作
bp就是succ的地址，对于seglist的root节点。
DSIZE * (size + DSIZE + DSIZE -1)/DSIZE)
等价于
(size + DSIZE +DSIZE -1) & ~(0xF)
free block 最小是2 * DSIZE (16 bytes),
对于 (0,16), 直接返回 2 * DSIZE;
对于 size = 16n+ (0, 16), 返回16 * (n+1);
mm_init 初始化seglist
extend_heap , 通过mem_sbrk 修改，heap 范围，(mem_brk 等指针的位置)， 更新epilogue和prologue 的信息。
修改block 的allocated flag, 然后调用imme_coalesce, 查看prev_bp 和 next_bp是否可以合并，更新seglist 的 free block 数据。
使用first_fit查看是否有符合size大小的free blk, 没有的话，先合并，合并之后size仍然小于asize, 调用extend_heap函数。同时，如果找到的free blk 大于asize, 查看是否大于最小free blk size(header + footer + prev + succ, 4 word, word == 4 bytes), 大于进行split, 将剩余的部分加入seglist。
合并blk 存在4 种情况：
allocated blk 的header 和footer 不再记录size和allocate flag , 提高了heap的内存使用效率。
64位设备运行32程序
sudo yum install glibc.i686 libstdc++.i686
malloc 使用
#include <stdio.h>
#include <stdlib.h>
int main() {
// 使用 malloc 分配足够的空间来存储一个指针
int* ptr = (int*)malloc(sizeof(int*)*2);
if (ptr == NULL) {
// 检查内存分配是否成功
printf("内存分配失败\n");
return 1; // 返回错误码
}
// 假设有一个地址需要存储
int x = 222;
// 将地址存储到分配的内存中
*ptr = &x;
// 打印存储的地址值
printf("存储的地址值：%p\n", *ptr);
int * p = *ptr;
printf("val: %d \n", *p);
printf("存储的地址值：%p\n", &x);
*(ptr+1) = 333;
printf("val: %d \n", *(ptr+1));
// 释放分配的内存
free(ptr);
return 0; // 返回成功码
}
段错误
0x00000000 导致段错误
[root@edb3963640a6 malloclab-handout]# ./mdriver -V -f short1-bal.rep
Team Name:Nahida_team
Member 1 :Nahida:nahida@cs.cmu.edu
Measuring performance with gettimeofday().
Testing mm malloc
Reading tracefile: short1-bal.rep
Segmentation fault (core dumped)
执行指令出现段错误
Core was generated by `./mdriver -V -f short1-bal.rep'.
Program terminated with signal 11, Segmentation fault.
#0 0x0804b29b in delete_blk (bp=0xf69a6888 '\004' <repeats 200 times>...) at mm.c:309
309 PUT(GET_SUCCP(pred_bp), succ_bp);
Missing separate debuginfos, use: debuginfo-install glibc-2.17-326.el7_9.i686
(gdb) bt
#0 0x0804b29b in delete_blk (bp=0xf69a6888 '\004' <repeats 200 times>...) at mm.c:309
#1 0x0804b113 in imme_coalesce (bp=0xf69a6888) at mm.c:245
#2 0x0804b60d in mm_free (ptr=0xf69a6888) at mm.c:455
#3 0x08049d8c in eval_mm_valid (trace=0x824a050, tracenum=0, ranges=0xfffef17c) at mdriver.c:674
#4 0x08049039 in main (argc=4, argv=0xfffef294) at mdriver.c:296
prev_bp 指针和 bp指针指向同一个位置？
测试可以通过的case, 不存在prev_bp 和 bp地址一样的问题。
prev_bp (0xf69fa888) 到 bp(0xf69fb038) 是一个size 6064的block, 对于0x 00000000 使用get_alloc 得到0， 所以导致prev_bp 获取的指针地址不准确，导致段错误。
mm_malloc 问题
Testing mm malloc
Reading tracefile: ./traces/amptjp-bal.rep
Checking mm_malloc for correctness, ERROR [trace 0, line 203]: Payload (0xf69d6038:0xf69d6040) lies outside heap (0xf69bd008:0xf69d6037)
New value 应该是1320。
old value = 1424 时候得打断点。
return 是bp 还是bp_header, 使用bp_header会导致
举个例子，size = 13, 13+8 +7 = 28
00000000 00000000 00000000 00011100 && ~(0xF) = 00000000 00000000 00000000 00000001
而不是 00000000 00000000 00000000 00010000.
realloc-bal.rep 和 realloc2-bal.rep
Reading tracefile: realloc-bal.rep
Checking mm_malloc for correctness, ERROR [trace 9, line 7]: Payload (0xf69ed038:0xf69ed2b7) overlaps another payload (0xf69ed240:0xf69ed2bf)
Reading tracefile: realloc2-bal.rep
Checking mm_malloc for correctness, ERROR [trace 10, line 7]: mm_realloc did not preserve the data from old block
[root@edb3963640a6 malloclab-handout]# ./mdriver -f ./traces/realloc-bal.rep -V
Team Name:Nahida_team
Member 1 :Nahida:nahida@cs.cmu.edu
Measuring performance with gettimeofday().
Testing mm malloc
Reading tracefile: ./traces/realloc-bal.rep
Segmentation fault (core dumped)
imme_coalesce 会合并prev_bp 和bp, old_bp 一般是bp, 但是prev_bp 和bp 合并时会修改bp_header, 导致oldbp_size小于DSIZE, memcpy函数出现段错误。
[root@edb3963640a6 malloclab-handout]# ./mdriver -V
Team Name:Nahida_team
Member 1 :Nahida:nahida@cs.cmu.edu
Using default tracefiles in /home/csapp/Malloc_Lab/malloclab-handout/traces/
Measuring performance with gettimeofday().
Testing mm malloc
Reading tracefile: amptjp-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: cccp-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: cp-decl-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: expr-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: coalescing-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: random-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: random2-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: binary-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: binary2-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: realloc-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: realloc2-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Results for mm malloc:
trace valid util ops secs Kops
0 yes 98% 5694 0.013128 434
1 yes 94% 5848 0.013082 447
2 yes 98% 6648 0.012994 512
3 yes 99% 5380 0.013417 401
4 yes 66% 14400 0.013624 1057
5 yes 89% 4800 0.014118 340
6 yes 85% 4800 0.013772 349
7 yes 55% 12000 0.016546 725
8 yes 51% 24000 0.015425 1556
9 yes 48% 14401 0.030041 479
10 yes 45% 14401 0.015555 926
Total 75% 112372 0.171701 654
Perf index = 45 (util) + 40 (thru) = 85/100