Pwn进你的心
0%

CSapp-Malloc Lab

Posted on Edited on In 52k 47 mins.

Malloc Lab

学生实现他们自己版本的 malloc，free 和 realloc，当然不仅要正确的实现相关功能，也要满足速度效率等要求

开始实验之前需要一些前置知识

动态内存分配器

动态内存分配器维护了一个进程的虚拟内存区域（被称为堆）

对于每个进程，内核维护着一个变量brk（break），它指向堆的顶部

动态内存分配器把堆视为一组 不同大小的块 的集合体，每个块就是一个连续的虚拟内存片（chunk），它有两种状态：已分配（allocated），空闲（free）

动态内存分配器有两种风格，两个风格都要求应用 显式地 分配内存，不同之处在于哪个实体来负责释放已分配的块

  • 显式分配器：要求应用 显式地 释放已分配的块（主动释放，只有调用相应的函数才能将chunk释放掉），比如：C中的 malloc 和 free，C++中的 new 和 delete
  • 隐式分配器：要求应用 隐式地 释放已分配的块（自动释放，要求分配器自己检测chunk何时不被程序利用），比如：java，ML，Lisp都依赖 “垃圾收集” 来释放chunk

分配器的基本规则

在写分配器前，先要了解malloc的功能的特点：

基础功能

malloc 可以在 heap 获取一片内存（由数据结构chunk进行管理），并返回“chunk->FD”

如果 malloc 遇到问题（例如，程序要求的内存块比可用的虚拟内存还要大），那么它就返回 NULL，并设置 errno

free 可以释放一片内存空间

内存对齐

malloc 会返回至少为“chunk->size”字节的的chunk，chunk的大小也会受 内存对齐 的影响

案例：32位程序，一个空格代表4字节，初始16字，双字对齐

+ + 1：malloc申请了4字大小的chunk，实际上申请了4字 + 2：malloc申请了5字大小的chunk，实际上申请了6字（双字对齐） + 3：malloc申请了6字大小的chunk，实际上申请了6字 + 4：free释放了P2 + 5：malloc申请了2字大小的chunk，优先占用了P2的 free chunk（fastbin & Tcachebin） **内存管理** 内存管理可以分为以下几个问题： + 空闲块的组织方式 + 空闲块的再申请 + 空闲块的分割 + 空闲块的合并 为了应对这些问题，我们需要学习相应的技术 **必要检查** 先抛开安全方面的检查，malloc必须要满足一些约束条件： + 每个释放请求必须对应一个当前已分配的块，这个块是由一个以前的分配请求获得到的 + 立刻响应请求 + 不修改已经分配的chunk（申请的chunk不重叠） ## 内存块组织技术 针对空闲块的组织方法有以下三种： + 隐式空闲链表(implicit free list) + 显式空闲链表(explicit free list) + 分离空闲链表(segregated free list) 这里主要介绍前两种 **隐式空间链表** 任何实际的分配器都需要一些数据结构，允许它来区别块边界，以及区别已分配块和空闲块，大多数分配器将这些信息嵌入块本身：

隐式空闲链表就是一种简单空闲块组织结构，可以把堆 按地址顺序 组织成一个连续的，包含allocated chunk和free chunk的链表

阴影部分是已分配块，没有阴影的部分是空闲块，头部标记为（size / flag）

因为分配器需要通过 flag 才能辨别该chunk的类型，所以它在重新申请chunk时，需要遍历整个链表，以获取合适的free chunk

显式空闲链表

块分配与堆块的总数呈线性关系，所以对于通用的分配器，隐式空闲链表是不适合的，一种更好的方法是 将空闲块组织为某种形式 的显式数据结构

通过“free chunk->FD”和“free chunk->BK”把free chunk连接为一个双向链表

此后进行遍历时，就不用对allocated chunk进行操作了

放置策略

为了提高内存利用率，空闲块的再申请是必不可少的，想要获取合适的空闲块，程序必须先进行搜索，分配器执行这种搜索的方式是由放置策略（placement policy）确定的，一些常见的策略是：

  • 首次适配（first-fit）
  • 下次适配（next-fit）
  • 最佳适配（best-fit）

比如：隐式空闲链表中的最佳适配，就是采用遍历所有chunk方式

首次适配

首次适配算法的分配内存的设计思路是：物理内存页管理器顺着双向链表进行搜索空闲内存区域，直到找到一个足够大的空闲区域，然后立刻将其进行分配（或分割后分配），此后的内存块都不做处理

优点：速度迅速

缺点：分割后剩下的内存块会越来越难以利用

下次适配

下次适配和首次适配相似，只不过不是每次都从链表的起始处开始搜索，而是从上一次查询结束的地方开始

最佳适配

每一次都遍历所有内存块，获取最合适的

优点：剩下的内存块利用率较高

缺点：速度缓慢

空闲块分割

在 “空闲块再申请” 的过程中，不一定每一次都可以刚好分离相同大小的空闲块，所以在必要时刻需要对空闲块进行分割

对其再申请4字后，剩下的4字大小的free chunk更加难以利用了

边界标记

边界标记（boundary tag），允许在常数时间内进行对前面块的合并

在每个块的结尾处添加一个脚部（footer，边界标记）

​ // 原本内存块的 头部 就可以标记chunk的状态，脚部只是头部的一个副本

如果每个块包括这样一个脚部，那么分配器就可以通过检査它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块开始位置一个字的距离

考虑当分配器释放当前块时所有可能存在的情况：

  • 情况1：前面的块和后面的块都是已分配的
  • 情况2：前面的块是已分配的，后面的块是空闲的
  • 情况3：前面的块是空闲的，而后面的块是已分配的
  • 情况4：前面的和后面的块都是空闲的

有3个独立的内存块，释放中间那个内存块：

  • 情况1：不进行合并
  • 情况2：通过更新脚部的位置，和后面的块进行合并
  • 情况3：通过更新头部的位置，和前面的块进行合并
  • 情况4：同时更新头部和脚部的位置，和相邻两个块进行合并

缺陷：它要求每个块都保持一个头部和一个脚部，在应用程序操作许多个小块时，会产生显著的内存开销

性能提升

当所有malloc的基础要求完成过后，我们就需要考虑它的性能，分配器的编写者往往需要实现 吞吐率 最大化，和 内存使用率最大化 ，但是这两个性能又往往是冲突的

吞吐率最大化

吞吐率：单位时间里完成的请求数，比如：1秒完成500次申请请求，500次释放请求，那么它的吞吐率就是每秒1000次操作

合理性能：分配请求的 最糟运行时间 与 空闲块数量 形成的线性关系

内存利用率最大化

一个系统内所有进程分配的虚拟内存大全部数量，受磁盘上交换空间的数量限制

峰值利用率：用来描述分配器使用堆的效率

实验程序介绍

实验给出了“memlib.c”，提供了一个内存系统模拟程序，可以在不干涉系统内存的前提下进行实验

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*
 * memlib.c - a module that simulates the memory system.  Needed because it 
 *            allows us to interleave calls from the student's malloc package 
 *            with the system's malloc package in libc.
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include <errno.h>

#include "memlib.h"
#include "config.h"

/* private variables */
static char *mem_start_brk;  /* points to first byte of heap */
static char *mem_brk;        /* points to last byte of heap */
static char *mem_max_addr;   /* largest legal heap address */ 

/* 
 * mem_init - initialize the memory system model
 */
void mem_init(void)
{
    /* allocate the storage we will use to model the available VM */
    if ((mem_start_brk = (char *)malloc(MAX_HEAP)) == NULL) {
	fprintf(stderr, "mem_init_vm: malloc error\n");
	exit(1);
    }

    mem_max_addr = mem_start_brk + MAX_HEAP;  /* max legal heap address */
    mem_brk = mem_start_brk;                  /* heap is empty initially */
}

/* 
 * mem_deinit - free the storage used by the memory system model
 */
void mem_deinit(void)
{
    free(mem_start_brk);
}

/*
 * mem_reset_brk - reset the simulated brk pointer to make an empty heap
 */
void mem_reset_brk()
{
    mem_brk = mem_start_brk;
}

/* 
 * mem_sbrk - simple model of the sbrk function. Extends the heap 
 *    by incr bytes and returns the start address of the new area. In
 *    this model, the heap cannot be shrunk.
 */
void *mem_sbrk(int incr) 
{
    char *old_brk = mem_brk;

    if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
	errno = ENOMEM;
	fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
	return (void *)-1;
    }
    mem_brk += incr;
    return (void *)old_brk;
}

/*
 * mem_heap_lo - return address of the first heap byte
 */
void *mem_heap_lo()
{
    return (void *)mem_start_brk;
}

/* 
 * mem_heap_hi - return address of last heap byte
 */
void *mem_heap_hi()
{
    return (void *)(mem_brk - 1);
}

/*
 * mem_heapsize() - returns the heap size in bytes
 */
size_t mem_heapsize() 
{
    return (size_t)(mem_brk - mem_start_brk);
}

/*
 * mem_pagesize() - returns the page size of the system
 */
size_t mem_pagesize()
{
    return (size_t)getpagesize();
}
  • void *mem sbrk(int incr)：和系统的 sbrk 一致，用于分配内存
  • void *mem_heap_lo(void)：返回指向堆的第一个字节的指针
  • void *mem_heap_hi(void)：返回指向堆的最后一个字节的指针
  • size_t mem_heapsize(void)：返回当前的堆大小
  • size_t mem_pagesize(void)：返回系统的 page size（页大小）

分配器包含在“mm.c”，需要完成下面几个函数：

1
2
3
4
int mm_init(void); // 初始化分配器，成功返回0，否则返回-1
void *mm_malloc(size_t size); // 
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);

最后，实验还给出了调试程序“mdriver.c”，可以给你的作品打分

隐式空闲链表+首次适配

第一次实验采用CSAPP上的案例，后续在进行修改

写程序之前需要先写入基本宏定义：

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
/* 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 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)))
  • PACK(size, alloc)：把”chunk->size”和”P”包装为1位
  • GET(p)：从 p 中读取4字节的数据（ 这里强制类型转换是至关重要的 ）
  • PUT(p, val) ：将 val 存放在参数 p 指向的地址中
  • GET_SIZE(p)：获取头部的SIZE（通过GET(p)获取头部，接着“UNPACK”）
  • GET_ALLOC(p)：获取”P位”
  • HDRP(bp)：返回指向当前块头部的指针（减去一字刚好计算出头部）
  • FTRP(bp)：返回指向当前块脚部的指针（加上SIZE后，相当于多加了一个脚部，所以减两字）
  • NEXT_BLKP(bp)：返回指向后面块BP的指针（从当前块的头部获取SIZE，相加）
  • PREV_BLKP(bp)：返回指向前面块BP的指针（从上一个块的脚部获取SIZE，相减）

注意：因为“FTRP”是根据“HDRP”计算出的，所以必须先写入头部，才能写入脚部

对堆进行初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
int mm_init(void)
{
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1)
        return -1;
    PUT(heap_listp, 0); 
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // 初始化头部(4~8)
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // 初始化脚部(8~12)
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // 初始化下一个头部(12~16)
    heap_listp += (2 * WSIZE);
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

创建一个空的空闲链表（采用隐式空间链表）：

  • heap_listp用于记录第一个内存块的数据区（与脚部重合，但是可以被宏定义识别）
  • 第一个内存块不写入数据（没有意义，后续操作都将会跳过它，直接获取下一个内存块）

接着它调用 extend_heap 函数

这个函数用于申请内存块，初始化使将堆扩展 CHUNKSIZE 字节，并且创建初始的空闲块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void *extend_heap(size_t words)
{
    void *bp;
    size_t size;

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

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

    /* Coalesce if the previous block was free */
    return coalesce(bp);
}

extend_heap保证了，“mem_sbrk(size)”的size大小为8的倍数（内存对齐）

后续的PUT填入了当前块的头部和脚部，和下一个块的头部

函数coalesce用于合并堆块，在mm_free中也会使用：

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

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));
    if (prev_alloc && next_alloc) {            /* Case 1 */
        return bp;
    }
    else if (prev_alloc && !next_alloc) {      /* Case 2 */
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
    }
    else if (!prev_alloc && next_alloc) {      /* Case 3 */
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }else {                                    /* Case 4 */
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    return bp;
}

coalesce先获取了上一个块的脚部，下一个块的头部，和当前的SIZE

  • case1：上一个块allocated，下一个块allocated，不合并
  • case2：上一个块allocated，下一个块free，把“SIZE”加上“NEXT_BLKP->SIZE”，更新脚部
  • case3：上一个块free，下一个块allocated，把“SIZE”加上“PREV_BLKP->SIZE”，更新头部
  • case4：上一个块free，下一个块free，把“SIZE”同时加上前后两者的“SIZE”，更新头部&脚部

mm_malloc函数会先检查请求的真假，然后进行申请，必须保证8字节对齐，另外需要8字节来存放头部和脚部，对于超过8字节的请求，一般的规则是加上开销字节，然后向上舍入到最接近的8的整数倍 

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
void *mm_malloc(size_t size)
{
    size_t asize;      /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;

    /* Ignore spurious requests */
    if (size <= 0)
        return NULL;
    /* Adjust block size to include overhead and alignment reqs. */
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        return bp;
    }
    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

mm_malloc中的：

1
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

保证了用于申请的asize一定为8的倍数，并且留有8字节头部和脚部的空间

find_fit用于查找合适的空闲块，place用于放置空闲块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void *find_fit(size_t asize)
{
    char *bp = heap_listp;
    size_t alloc;
    size_t size; /* heap_listp 指向第一个内存块，没有意义，直接获取下一个内存块 */
    while (GET_SIZE(HDRP(NEXT_BLKP(bp))) > 0) {
        bp = NEXT_BLKP(bp);
        alloc = GET_ALLOC(HDRP(bp));
        if (alloc) continue;
        size = GET_SIZE(HDRP(bp));
        if (size < asize) continue;
        return bp;
    } 
    return NULL;
}

采用首次适配（first-fit）：遇到allocated chunk，或者free chunk的size不够，就重新循环

直到找寻到合适的空闲块后，输出其BP（数据区指针）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void place(void *bp, size_t asize)
{
    size_t size = GET_SIZE(HDRP(bp));
    
    if ((size - asize) >= (2*DSIZE)) {
        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));
    } else {
        PUT(HDRP(bp),PACK(size,1));
        PUT(FTRP(bp),PACK(size,1));
    }
}

因为内存块最小为“ 2*DSIZE ”（16字节），所以如果切割剩余内存块小于16字节就不能进行切割，利用边界标记技术，可以通过“添加内存块边界”来进行切割

更新一下mm_realloc：

1
2
3
4
5
6
7
8
9
10
11
12
void *mm_realloc(void *ptr, size_t size)
{
    size_t oldsize = GET_SIZE(HDRP(ptr));
	void* newptr = mm_malloc(size);
	if (!newptr)
		return 0;
	if (!ptr)
		return newptr;
	memcpy(newptr, ptr, (size < oldsize ? size : oldsize));
	mm_free(ptr);
	return newptr;
}

整体逻辑：

  • 先用“extend_heap”初始化一个大小为CHUNKSIZE的大内存块，使其为free状态
  • 后续的malloc都在这个大内存块中分割
  • 如果大内存块不够用，就再次调用“extend_heap”进行申请

打分&完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 隐式空闲链表+首次适配 */
➜  [/home/ywhkkx/malloclab-handout] ./mdriver -v
Team Name:ateam
Member 1 :Harry Bovik:bovik@cs.cmu.edu
Using default tracefiles in /home/ywhkkx/malloclab-handout/traces/
Measuring performance with gettimeofday().

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.006554   869
 1       yes   99%    5848  0.005849  1000
 2       yes   99%    6648  0.010224   650
 3       yes  100%    5380  0.006037   891
 4       yes   66%   14400  0.000076188976
 5       yes   92%    4800  0.005052   950
 6       yes   92%    4800  0.006428   747
 7       yes   55%   12000  0.070162   171
 8       yes   51%   24000  0.237273   101
 9       yes   27%   14401  0.047580   303
10       yes   34%   14401  0.001504  9575
Total          74%  112372  0.396739   283

Perf index = 44 (util) + 19 (thru) = 63/100
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
 
#include "mm.h"
#include "memlib.h"
 
/* 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 SIZE_T_SIZE (ALIGN(sizeof(size_t)))
 
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12)
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))
#define PACK(size, alloc) ((size) | (alloc))
#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)
#define HDRP(bp) ((char*)(bp) - WSIZE)
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(((char*)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE(((char*)(bp) - DSIZE)))
static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void *find_fit(size_t size);
static void place(void *bp,size_t asize);
static char *heap_listp = 0;

/* 
 * mm_init - initialize the malloc package.
 */

int mm_init(void)
{
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1)
	    return -1;
    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(CHUNKSIZE/WSIZE) == NULL)
	    return -1;
    return 0;
}
 
static void* extend_heap(size_t words){
	char* bp;
	size_t size;
	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));
	return 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));
	if (prev_alloc && next_alloc)
		return bp;
	else if (prev_alloc && !next_alloc){
		size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
		PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
		PUT(HDRP(bp), PACK(size, 0));
	}
	else if (!prev_alloc && next_alloc){
		size += GET_SIZE(HDRP(PREV_BLKP(bp)));
		PUT(FTRP(bp), PACK(size, 0));
		PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
		bp = PREV_BLKP(bp);
	}
	else{
		size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
		PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
		PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
		bp = PREV_BLKP(bp);
	}
	return bp;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */

void *mm_malloc(size_t size)
{
	char *bp;
    size_t asize;
	size_t extendsize;
	if (size <= 0)
		return NULL;
	if (size <= DSIZE)
		asize = 2 * DSIZE;
	else
		asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / 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;
}
 
/*
 * mm_free - Freeing a block does nothing.
 */

void mm_free(void *ptr)
{
	size_t size = GET_SIZE(HDRP(ptr));
	PUT(HDRP(ptr), PACK(size, 0));
	PUT(FTRP(ptr), PACK(size, 0));
	coalesce(ptr);
	return;
}

static void *find_fit(size_t asize)
{
    char *bp = heap_listp;
    size_t alloc;
    size_t size;
    while (GET_SIZE(HDRP(NEXT_BLKP(bp))) > 0) {
        bp = NEXT_BLKP(bp);
        alloc = GET_ALLOC(HDRP(bp));
        if (alloc) continue;
        size = GET_SIZE(HDRP(bp));
        if (size < asize) continue;
        return bp;
    } 
    return NULL;
}
static void place(void *bp, size_t asize)
{
    size_t size = GET_SIZE(HDRP(bp));
    
    if ((size - asize) >= (2*DSIZE)) {
        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));
    } else {
        PUT(HDRP(bp),PACK(size,1));
        PUT(FTRP(bp),PACK(size,1));
    }
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */

void *mm_realloc(void *ptr, size_t size)
{
    size_t oldsize = GET_SIZE(HDRP(ptr));
	void* newptr = mm_malloc(size);
	if (!newptr)
		return 0;
	if (!ptr)
		return newptr;
	memcpy(newptr, ptr, (size < oldsize ? size : oldsize));
	mm_free(ptr);
	return newptr;
}

隐式空闲链表+下次适配

想要实现下次适配的代码和书上有所不同，需要有所改进

首先需要一个全局指针来记录“上一次操作”

1
static char* pre_listp;

在一些函数快结束时（不包括“place”和“coalesce”），该指针都要更新为当前块的BP（指向数据区的指针）

另外，“find_fit”需要重写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void *find_fit(size_t asize)
{
    char *bp = pre_listp;
    size_t alloc;
    size_t size;
    while (GET_SIZE(HDRP(NEXT_BLKP(bp))) > 0) {
        bp = NEXT_BLKP(bp);
        alloc = GET_ALLOC(HDRP(bp));
        if (alloc) continue;
        size = GET_SIZE(HDRP(bp));
        if (size < asize) continue;
        return bp;
    } 
    bp = heap_listp; /* 这里也是跳过第一个内存块，直接获取下一个 */
    while (bp != pre_listp) {
        bp = NEXT_BLKP(bp);
        alloc = GET_ALLOC(HDRP(bp));
        if (alloc) continue;
        size = GET_SIZE(HDRP(bp));
        if (size < asize) continue;
        return bp;
    } 
    return NULL;
}

这里需要注意：

  • 当下次适配遍历完所有的空闲块时，需要把BP重置为heap_listp（第一个内存块）
  • 只需要“mm_malloc”中记录一下“pre_listp”，重复记录可能会报错
  • 可以把“pre_listp”初始化为第二个内存块的BP（比如本程序），也可以初始化为第一个

打分&完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 隐式空闲链表+下次适配 */
➜  [/home/ywhkkx/malloclab-handout] ./mdriver -v
Team Name:ateam
Member 1 :Harry Bovik:bovik@cs.cmu.edu
Using default tracefiles in /home/ywhkkx/malloclab-handout/traces/
Measuring performance with gettimeofday().

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   89%    5694  0.001789  3183
 1       yes   91%    5848  0.001089  5371
 2       yes   95%    6648  0.003659  1817
 3       yes   97%    5380  0.002975  1808
 4       yes   66%   14400  0.000112128228
 5       yes   92%    4800  0.003465  1385
 6       yes   90%    4800  0.002659  1805
 7       yes   55%   12000  0.006609  1816
 8       yes   51%   24000  0.006411  3744
 9       yes   27%   14401  0.041252   349
10       yes   30%   14401  0.001649  8734
Total          71%  112372  0.071668  1568

Perf index = 43 (util) + 40 (thru) = 83/100
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/* 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 SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12) 
#define MAX(x,y) ((x) > (y)? (x) : (y))
#define PACK(size,alloc) ((size) | (alloc))
#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) 
#define HDRP(bp)        ((char *)(bp) - WSIZE)
#define FTRP(bp)        ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp)   ((char*)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp)   ((char*)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void* find_fit(size_t asize);
static void place(void* bp, size_t asize);

static char* heap_listp;
static char* pre_listp;

/* 
 * mm_init - initialize the malloc package.
 */

int mm_init(void)
{
    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);
    pre_listp = (unsigned int)heap_listp + DSIZE;
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

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

    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));
    pre_listp = coalesce(bp);
    return pre_listp;
}

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));
    if (prev_alloc && next_alloc)
        return bp;
    if (prev_alloc && !next_alloc)
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        PUT(HDRP(bp), PACK(size, 0));
    }
    else if (!prev_alloc && next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    else
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
            GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    return bp;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */

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 = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);
    if ((bp = find_fit(asize)) != NULL)
    {
        place(bp, asize);
        pre_listp = bp;
        return bp;
    }
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    pre_listp = bp;
    return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */

void mm_free(void* bp)
{
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    pre_listp = coalesce(bp);
    return;
}

static void* find_fit(size_t asize)
{
    char* bp = pre_listp;
    size_t alloc;
    size_t size;
    while (GET_SIZE(HDRP(NEXT_BLKP(bp))) > 0) {
        bp = NEXT_BLKP(bp);
        alloc = GET_ALLOC(HDRP(bp));
        if (alloc) continue;
        size = GET_SIZE(HDRP(bp));
        if (size < asize) continue;
        return bp;
    }
    bp = heap_listp;
    while (bp != pre_listp) {
        bp = NEXT_BLKP(bp);
        alloc = GET_ALLOC(HDRP(bp));
        if (alloc) continue;
        size = GET_SIZE(HDRP(bp));
        if (size < asize) continue;
        return bp;
    }
    return NULL;
}
static void place(void* bp, size_t asize)
{
    size_t size = GET_SIZE(HDRP(bp));

    if ((size - asize) >= (2 * DSIZE))
    {
        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));
    }
    else
    {
        PUT(HDRP(bp), PACK(size, 1));
        PUT(FTRP(bp), PACK(size, 1));
    }
    return;
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */

void* mm_realloc(void* ptr, size_t size)
{
    size_t oldsize = GET_SIZE(HDRP(ptr));
    void* newptr = mm_malloc(size);
    if (!newptr)
        return 0;
    pre_listp = newptr; 
    if (!ptr)
        return newptr;
    memcpy(newptr, ptr, (size < oldsize ? size : oldsize));
    mm_free(ptr);
    return newptr;
}

显式空间链表+首次适配+LIFO队列

上两次试验采用了隐式空间链表，这次尝试一些显示空间链表

显示空间链表需要把空闲块链接到一起，所以需要一个宏定义来指向下一个空闲块

1
#define NEXT_RP(bp)  ((unsigned int)(bp)+WSIZE) /*指向下一空闲块指针*/

显示空间链表采用双向链表，至少需要16字节，在空闲块中：

  • BP 指向（前驱）：上一个空闲块
  • BP+4 指向（后继）：下一个空闲块

另外还需要两个含函数来进行“插入”和“脱链”操作：

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
inline void __insert(char *bp)
{
    char *next = GET(root); /* 读取4字节的内容,转化为指针(数据可以随便转指针) */
    if(next != NULL) // 如果是root的第一个chunk,那么"next==NULL"
        PUT(next, bp);
    PUT(NEXT_RP(bp), next); 
    PUT(root,bp); 
}

inline void __remove(char *bp){
    char *pre = GET((bp)); /* 读取前4字节(指向前一个chunk) */
    char *next = GET(NEXT_RP(bp)); /* 读取后4字节(指向后一个chunk) */
    if(pre == NULL){ 
        if(next != NULL)
            PUT(next,0); /* 前无后有 */
        PUT(root,next); /* 前无后无 */
    }
    else{
        if(next != NULL) 
            PUT((next),pre); /* 前有后有 */
        PUT(NEXT_RP(pre),next); /* 前有后无 */
    }
    PUT(NEXT_RP(bp),0);
    PUT(bp,0);
}

在显式空间链表采用专门的链表来管理空闲块，这里采用后入先出队列

插入的逻辑：把root当成第一个空闲块，以后的空闲块都插入root的前驱（先写旧空闲块的后驱，再写新内存块的前驱）

脱链的逻辑：分为4种情况

  • 前有后有：中间某个 chunk，修改 nextchunk->last 为 lastchunk，修改 lastchunk->next 为 nextchunk，置空 chunk
  • 前有后无：root 的最后一个chunk，置空 lastchunk->next，置空 chunk
  • 前无后有：root 的第一个chunk，置空 nextchunk->last，修改 root 为 nextchunk，置空 chunk
  • 前无后无：root 的第一个并且是唯一一个chunk，直接置空 root，置空 chunk

下面是root依次插入 A，B，C，D 时的反应：（经典插头）

1
2
3
4
5
root(NULL)
root(A) => A(/NULL)
root(B) => B(/A) => A(B/NULL)
root(C) => C(/B) => B(C/A) => A(B/NULL)
root(D) => D(/C) => C(D/B) => B(C/A) => A(B/NULL)

下面是root分别释放 A，B，C，D 时的反应：

1
2
3
4
A: root(D) => D(/C) => C(D/B) => B(C/NULL)
B: root(D) => D(/C) => C(D/A) => A(C/NULL)
C: root(D) => D(/B) => B(D/A) => A(B/NULL)
D: root(C) => C(/B) => B(C/A) => A(B/NULL)

初始化函数发生了变化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int mm_init(void){
    if((heap_listp = mem_sbrk(6*WSIZE))==(void *)-1) 
        return -1;
    PUT(heap_listp,0);
    PUT(heap_listp+(1*WSIZE),0); // 初始化前驱
    PUT(heap_listp+(2*WSIZE),0); // 初始化后继
    PUT(heap_listp+(3*WSIZE),PACK(DSIZE,1)); // 初始化头(12~16)
    PUT(heap_listp+(4*WSIZE),PACK(DSIZE,1)); // 初始化脚(16~20)
    PUT(heap_listp+(5*WSIZE),PACK(0,1)); // 初始化下一个头部(20~~24)
    root = heap_listp + (1*WSIZE); // 初始化根节点
    heap_listp += (4*WSIZE);
    if((extend_heap(CHUNKSIZE/DSIZE)) == NULL) 
        return -1;
    return 0;
}

根节点就是第一次内存块的前驱（在root用完之前都是不变的）

合并模块对空闲块的管理更为复杂了：

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

    /*coalesce the block and change the point*/
    if(prev_alloc && !next_alloc){
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        __remove(NEXT_BLKP(bp)); /*使用了这个块，切记移除它*/
        PUT(HDRP(bp), PACK(size,0));
        PUT(FTRP(bp), PACK(size,0));
    }
    else if(!prev_alloc && next_alloc){
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        __remove(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(FTRP(NEXT_BLKP(bp)))+ GET_SIZE(HDRP(PREV_BLKP(bp)));
        __remove(PREV_BLKP(bp));/*使用了这个块，切记移除它*/
        __remove(NEXT_BLKP(bp));/*使用了这个块，切记移除它*/
        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp = PREV_BLKP(bp);
    }
    __insert(bp);/*新的空闲块，记住插入*/
    return bp;
}

只要空闲块发生过合并，就会被“remove”移出链表，在最后“insert”插入链表最前端

现在查找模块只需要在空闲块链表中查询就行了：（从头开始寻找）

1
2
3
4
5
6
7
8
9
10
static void *find_fit(size_t size){
    /*first fit*/
    char *bp = GET(root); /* 获取空闲链表头 */
    while(bp != NULL){
        if(GET_SIZE(HDRP(bp)) >= size) 
            return bp;  
        bp = GET(NEXT_RP(bp));
    }
    return NULL;
}

先获取链表最前端的空闲块，依次向后索引

放置模块需要多考虑前驱和后继的初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void place(void *bp,size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));
    __remove(bp);   /*使用了这个块，切记移除它*/
    if(csize-asize >= 2 *DSIZE){
        PUT(HDRP(bp),PACK(asize,1));
        PUT(FTRP(bp),PACK(asize,1));
        PUT(HDRP(NEXT_BLKP(bp)),PACK(csize-asize,0));
        PUT(FTRP(NEXT_BLKP(bp)),PACK(csize-asize,0));
        PUT(NEXT_RP(bp),0);
        PUT((NEXT_BLKP(bp)),0);
        coalesce(NEXT_BLKP(bp));
    }
    else{
        PUT(HDRP(bp),PACK(csize,1));
        PUT(FTRP(bp),PACK(csize,1));
    }
}

其他模块和书上的代码差不多，需要注意一下：何时该“插入”，何时该“脱链”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 显式空间链表+LIFO队列+首次适配 */
➜  [/home/ywhkkx/malloclab-handout] ./mdriver -v
Team Name:ateam
Member 1 :Harry Bovik:bovik@cs.cmu.edu
Using default tracefiles in /home/ywhkkx/malloclab-handout/traces/
Measuring performance with gettimeofday().

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   89%    5694  0.000167 34157
 1       yes   92%    5848  0.000093 62747
 2       yes   94%    6648  0.000327 20355
 3       yes   96%    5380  0.000195 27661
 4       yes   99%   14400  0.000093155005
 5       yes   88%    4800  0.000390 12301
 6       yes   85%    4800  0.000413 11625
 7       yes   55%   12000  0.001840  6522
 8       yes   51%   24000  0.001684 14249
 9       yes   26%   14401  0.041531   347
10       yes   34%   14401  0.001982  7266
Total          74%  112372  0.048714  2307

Perf index = 44 (util) + 40 (thru) = 84/100
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/* 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 SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12) 
#define MAX(x,y) ((x) > (y)? (x) : (y))
#define PACK(size,alloc) ((size) | (alloc))
#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) 
#define HDRP(bp)        ((char *)(bp) - WSIZE)
#define FTRP(bp)        ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp)   ((char*)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp)   ((char*)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
#define NEXT_RP(bp)     ((unsigned int)(bp)+WSIZE)

int mm_check(char* function);
static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void* find_fit(size_t asize);
static void place(void* bp, size_t asize);
void __insert(char* p);
void __remove(char* p);

static char* heap_listp = NULL;
static char* root = NULL;

/* 
 * mm_init - initialize the malloc package.
 */

int mm_init(void)
{
    if ((heap_listp = mem_sbrk(6 * WSIZE)) == (void*)-1)
        return -1;
    PUT(heap_listp, 0);
    PUT(heap_listp + (1 * WSIZE), 0);
    PUT(heap_listp + (2 * WSIZE), 0);
    PUT(heap_listp + (3 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (4 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (5 * WSIZE), PACK(0, 1));
    root = heap_listp + (1 * WSIZE);
    heap_listp += (4 * WSIZE);
    if ((extend_heap(CHUNKSIZE / DSIZE)) == NULL)
        return -1;
    return 0;
}

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

    size = (words % 2) ? (words + 1) * DSIZE : words * DSIZE;
    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));
    PUT(NEXT_RP(bp), 0);
    PUT(bp, 0);
    return 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));
    if (prev_alloc && !next_alloc)
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        __remove(NEXT_BLKP(bp));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    else if (!prev_alloc && next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        __remove(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(PREV_BLKP(bp))) +
            GET_SIZE(FTRP(NEXT_BLKP(bp)));
        __remove(PREV_BLKP(bp));
        __remove(NEXT_BLKP(bp));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    __insert(bp);
    return bp;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */

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 = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);
    if ((bp = find_fit(asize)) != NULL)
    {
        place(bp, asize);
        return bp;
    }
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / DSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */

void mm_free(void* bp)
{
    if (bp == NULL)
        return;
    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(NEXT_RP(bp), 0);
    PUT(bp, 0);
    coalesce(bp);
}

static void* find_fit(size_t size)
{   
    char* bp = GET(root);
    while (bp != NULL)
    {   
        if (GET_SIZE(HDRP(bp)) >= size)
            return bp;
        bp = GET(NEXT_RP(bp));
    }
    return NULL;
}

static void place(void* bp, size_t asize)
{
    size_t size = GET_SIZE(HDRP(bp));
    __remove(bp);
    if ((size - asize) >= (2 * DSIZE))
    {
        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));
        PUT(NEXT_RP(bp), 0);
        PUT((NEXT_BLKP(bp)), 0);
        coalesce(NEXT_BLKP(bp));
    }
    else
    {
        PUT(HDRP(bp), PACK(size, 1));
        PUT(FTRP(bp), PACK(size, 1));
    }
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */

void* mm_realloc(void* ptr, size_t size) {

    void* newptr = mm_malloc(size);
    if (!newptr) {
        return 0;
    }
    if (ptr == NULL) {
        return newptr;
    }

    size_t oldsize = GET_SIZE(HDRP(ptr));
    memcpy(newptr, ptr, oldsize < size ? oldsize : size);
    mm_free(ptr);

    return newptr;
}

inline void __insert(char* bp)
{
    char* next = GET(root);
    if (next != NULL)
        PUT(next, bp);
    PUT(NEXT_RP(bp), next);
    PUT(root, bp);
}

inline void __remove(char* bp)
{
    char* pre = GET((bp));
    char* next = GET(NEXT_RP(bp));
    if (pre == NULL)
    {
        if (next != NULL)
            PUT(next, 0);
        PUT(root, next);
    }
    else 
    {
        if (next != NULL)
            PUT((next), pre);
        PUT(NEXT_RP(pre), next);
    }
    PUT(NEXT_RP(bp), 0);
    PUT(bp, 0);
}

隐式空闲链表+下次适配+增添标记位

和第二次试验很相似，只不过需要去除ALLOC内存块的脚部，并在一些位置进行修改

开始实验之前先进行一下思考：假设ALLOC内存块没有脚部

1
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

那么，宏定义“PREV_BLKP(bp)”将会失效，ALLOC内存块将不能获取它前面的内存块，回看第二次实验的代码，发现就只有合并模块会受到影响：刚刚被free的ALLOC内存块不清楚上一个内存块是否为ALLOC

解决办法：对标记位进行操作，使头部可以表示上一个内存块的状态

分配的内存块大小为8的倍数，最后3位数值恒定，理论上有3个标志位可以用，以上代码中，最后一个标志位被用于记录“当前内存块是否为ALLOC”，与之类似，我们可以使用倒数第二个标志位来记录“上一个内存块是否为ALLOC”

1
2
3
#define PREALLOC(x) ((!x) ? 0 : 2) // 根据"x"中是否有数据来获取"0 & 2"
#define PACK(size, prealloc, alloc) ((size) | (PREALLOC(prealloc)) | (alloc))
#define GET_PREALLOC(p) (GET(p) & 0x2) // 获取倒数第二个标志位

这些宏定义可以简化我们的操作

1
2
3
4
5
6
inline void set_next_prealloc(void* bp, size_t prealloc)
{
    size_t size = GET_SIZE(HDRP(NEXT_BLKP(bp))); // 获取下一个内存块的size
    size_t alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 获取下一个内存块的alloc
    PUT(HDRP(NEXT_BLKP(bp)), PACK(size,prealloc,alloc));
}

这个函数可以根据当前内存块的状态，来更新下一个内存块的头部

接下来的代码和第二次实验区别不大，但需要注意一下：

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
void* mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char* bp;

    if (size <= 0)
        return NULL;
    if (size <= WSIZE) 
 // if (size <= DSIZE)   
        asize = DSIZE;
    //  asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + WSIZE + (DSIZE - 1)) / DSIZE);
    //  asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / 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;
}

“mm_malloc”获取ALLOC内存块时，不用写入脚部，可以少申请4字节，最小字节数可以变为“8”

打分&完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 隐式空闲链表+下次适配 */
➜  [/home/ywhkkx/malloclab-handout] ./mdriver -v
Team Name:ateam
Member 1 :Harry Bovik:bovik@cs.cmu.edu
Using default tracefiles in /home/ywhkkx/malloclab-handout/traces/
Measuring performance with gettimeofday().

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   89%    5694  0.002184  2607
 1       yes   92%    5848  0.001025  5704
 2       yes   95%    6648  0.003881  1713
 3       yes   97%    5380  0.002774  1939
 4       yes   66%   14400  0.000101142292
 5       yes   92%    4800  0.004425  1085
 6       yes   91%    4800  0.003771  1273
 7       yes   55%   12000  0.007433  1614
 8       yes   51%   24000  0.007050  3404
 9       yes   27%   14401  0.042339   340
10       yes   30%   14401  0.001879  7663
Total          71%  112372  0.076863  1462

Perf index = 43 (util) + 40 (thru) = 83/100
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/* 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 SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12) 
#define MAX(x,y) ((x) > (y)? (x) : (y))
#define PREALLOC(x) ((!x) ? 0 : 2)
#define PACK(size,prealloc,alloc) ((size) | (PREALLOC(prealloc)) | (alloc))
#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) 
#define GET_PREALLOC(p) (GET(p) & 0x2)
#define HDRP(bp)        ((char *)(bp) - WSIZE)
#define FTRP(bp)        ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define NEXT_BLKP(bp)   ((char*)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp)   ((char*)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void* find_fit(size_t asize);
static void place(void* bp, size_t asize);
inline void set_next_prealloc(void* bp, size_t prealloc);

static char* heap_listp;
static char* pre_listp;

/*
 * mm_init - initialize the malloc package.
 */

int mm_init(void)
{
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1)
        return -1;
    PUT(heap_listp, 0);
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1, 1));
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1, 1));
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1, 1));
    heap_listp += (2 * WSIZE);
    pre_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, prealloc;

    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)
        return NULL;
    prealloc = GET_PREALLOC(HDRP(bp));
    PUT(HDRP(bp), PACK(size, prealloc, 0));
    PUT(FTRP(bp), PACK(size, prealloc, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 0, 1));
    return coalesce(bp);
}

static void* coalesce(void* bp)
{
    size_t prev_alloc = GET_PREALLOC(HDRP((bp)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));
    if (prev_alloc && next_alloc)
    {
        set_next_prealloc(bp, 0);
        pre_listp = bp;
        return bp;
    }
    if (prev_alloc && !next_alloc)
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 1, 0));
        PUT(HDRP(bp), PACK(size, 1, 0));
    }
    else if (!prev_alloc && next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 1, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 1, 0));
        bp = PREV_BLKP(bp);
    }
    else
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
            GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 1, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 1, 0));
        bp = PREV_BLKP(bp);
    }
    set_next_prealloc(bp, 0);
    pre_listp = bp;
    return bp;
}

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */

void* mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char* bp;

    if (size <= 0)
        return NULL;
    if (size <= WSIZE)
        asize = DSIZE;
    else
        asize = DSIZE * ((size + WSIZE + (DSIZE - 1)) / DSIZE);
    if ((bp = find_fit(asize)) != NULL)
    {
        place(bp, asize);
        pre_listp = bp;
        return bp;
    }
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
    place(bp, asize);
    pre_listp = bp;
    return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */

void mm_free(void* bp)
{
    size_t size = GET_SIZE(HDRP(bp));
    size_t prealloc = GET_PREALLOC(HDRP(bp));
    PUT(HDRP(bp), PACK(size, prealloc, 0));
    PUT(FTRP(bp), PACK(size, prealloc, 0));
    coalesce(bp);
    return;
}

static void* find_fit(size_t asize)
{
    char* bp = pre_listp;
    size_t alloc;
    size_t size;
    while (GET_SIZE(HDRP(NEXT_BLKP(bp))) > 0) {
        bp = NEXT_BLKP(bp);
        alloc = GET_ALLOC(HDRP(bp));
        if (alloc) continue;
        size = GET_SIZE(HDRP(bp));
        if (size < asize) continue;
        return bp;
    }
    bp = heap_listp;
    while (bp != pre_listp) {
        bp = NEXT_BLKP(bp);
        alloc = GET_ALLOC(HDRP(bp));
        if (alloc) continue;
        size = GET_SIZE(HDRP(bp));
        if (size < asize) continue;
        return bp;
    }
    return NULL;
}
static void place(void* bp, size_t asize)
{
    size_t size = GET_SIZE(HDRP(bp));

    if ((size - asize) >= DSIZE)
    {
        PUT(HDRP(bp), PACK(asize, 1, 1));
        PUT(FTRP(bp), PACK(asize, 1, 1));
        PUT(HDRP(NEXT_BLKP(bp)), PACK(size - asize, 1, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size - asize, 1, 0));
        set_next_prealloc(bp, 0);
    }
    else
    {
        PUT(HDRP(bp), PACK(size, 1, 1));
        set_next_prealloc(bp, 1);
    }
    pre_listp = bp;
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */

void* mm_realloc(void* ptr, size_t size)
{
    size_t oldsize = GET_SIZE(HDRP(ptr));
    void* newptr = mm_malloc(size);
    if (!newptr)
        return 0;
    pre_listp = newptr;
    if (!ptr)
        return newptr;
    memcpy(newptr, ptr, (size < oldsize ? size : oldsize));
    mm_free(ptr);
    return newptr;
}

inline void set_next_prealloc(void* bp, size_t prealloc)
{
    size_t size = GET_SIZE(HDRP(NEXT_BLKP(bp)));
    size_t alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(size, prealloc, alloc));
}

分离式空闲链表+首次适配

分离式空闲链表（Segregated Free Lists），采用了 分离存储 技术，同时维护多个空闲链表，其中每个链表中的块有大致相等的大小

实现 分离存储 有许多中方法，CSAPP简单提及了三种：

  • 简单分离存储
  • 分离适配
  • 伙伴系统

这里采用 简单分离存储 的方式实现分离式空闲链表，同一区域的空闲块用前驱和后继指针进行连接

多了两个宏定义：

1
2
#define PREV_LINKNODE_RP(bp) ((char*)(bp))
#define NEXT_LINKNODE_RP(bp) ((char*)(bp)+WSIZE)
  • PREV_LINKNODE_RP(bp)：获取上一个空闲块
  • NEXT_LINKNODE_RP(bp)：获取下一个空闲块
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
int mm_init(void)
{
    if((heap_listp = mem_sbrk(14*WSIZE))==(void *)-1)
        return -1;
    PUT(heap_listp,0);              /*block size list<=8*/
    PUT(heap_listp+(1*WSIZE),0);    /*block size list<=16*/
    PUT(heap_listp+(2*WSIZE),0);    /*block size list<=32*/
    PUT(heap_listp+(3*WSIZE),0);    /*block size list<=64*/
    PUT(heap_listp+(4*WSIZE),0);    /*block size list<=128*/
    PUT(heap_listp+(5*WSIZE),0);    /*block size list<=256*/
    PUT(heap_listp+(6*WSIZE),0);    /*block size list<=512*/
    PUT(heap_listp+(7*WSIZE),0);    /*block size list<=2048*/
    PUT(heap_listp+(8*WSIZE),0);    /*block size list<=4096*/
    PUT(heap_listp+(9*WSIZE),0);    /*block size list>4096*/
    PUT(heap_listp+(10*WSIZE),0);
    PUT(heap_listp+(11*WSIZE),PACK(DSIZE,1)); // 初始化头部
    PUT(heap_listp+(12*WSIZE),PACK(DSIZE,1)); // 初始化脚部
    PUT(heap_listp+(13*WSIZE),PACK(0,1)); // 初始化下一个内存块的头部

    block_list_start = heap_listp;
    heap_listp += (12*WSIZE);

    if((extend_heap(CHUNKSIZE/DSIZE))==NULL) 
        return -1;
    return 0;
}

在初始的第一个内存块的前面：定义了若干个分离的空间链表

“extend_heap”，“mm_malloc”和第三次实验（显示空间链表）的差别不大

“find_fit”和“place”需要重写（首次适配）：

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
static void *find_fit(size_t size)
{
    /*first fit*/ 
    char *root = find_list_root(size); // 根据size获取相应的空间链表
    for(root; root!=(heap_listp-(2*WSIZE)); root+=WSIZE) 
    { /* root+WSIZE：指向有更大空闲块的空闲链表 */
        char *tmpP = GET(root); // 获取当前空间链表中最前面的内存块
        while(tmpP != NULL) 
        { /* 遍历当前空间链表：从前往后 */
            if(GET_SIZE(HDRP(tmpP))>=size)
                return tmpP;
            tmpP = GET(NEXT_LINKNODE_RP(tmpP));
        }
    }
    return NULL;
}

static void place(void *bp,size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));
    fix_linklist(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)); // 初始化脚部
        PUT(NEXT_LINKNODE_RP(bp),0); // 初始化后继
        PUT(PREV_LINKNODE_RP(bp),0); // 初始化前继
        coalesce(bp);
    }
    else // 刚好合适
    {
        PUT(HDRP(bp),PACK(csize,1));
        PUT(FTRP(bp),PACK(csize,1));
    }
}
  • Find_fit 的逻辑：首先根据size获取相应的空间链表，遍历当前链表所以的空闲块，如果没有合适的空闲块就“root+=WSIZE”，在有更大空闲块的空间链表中寻找，获取合适的空间链表后，先获取该链表中最前面的那个空闲块，再从前往后进行遍历
  • Place的逻辑：在判断是否切割前先脱链，接着完成后续操作

这里引入了两个对空间链表进行操作的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline char *find_list_root(size_t size)
{
    int i = 0;
    if(size<=8) i=0;
    else if(size<=16) i= 1;
    else if(size<=32) i= 2;
    else if(size<=64) i= 3;
    else if(size<=128) i= 4;
    else if(size<=256) i= 5;
    else if(size<=512) i= 6;
    else if(size<=2048) i= 7;
    else if(size<=4096) i= 8;
    else i= 9;
    /*find the index of bin which will put this block */
    return block_list_start+(i*WSIZE);
}

根据“size”获取对应空间链表的位置，不多说

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline void fix_linklist(char *p)
{
    char *root = find_list_root(GET_SIZE(HDRP(p)));
    char *prevp = GET(PREV_LINKNODE_RP(p));
    char *nextp = GET(NEXT_LINKNODE_RP(p));

    if(prevp == NULL)
    {
        if(nextp != NULL)PUT(PREV_LINKNODE_RP(nextp),0);
        PUT(root,nextp);
    }
    else
    {
        if(nextp != NULL)PUT(PREV_LINKNODE_RP(nextp),prevp);
        PUT(NEXT_LINKNODE_RP(prevp),nextp);
    }
    PUT(NEXT_LINKNODE_RP(p),NULL);
    PUT(PREV_LINKNODE_RP(p),NULL);
}

脱链操作，跟第三次实验中的“__remove”功能类似

“mm_free”的变化不大，主要是“coalesce”变化较大：

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

    if(prev_alloc && next_alloc)
    {
        insert_to_list(bp); // 插入对应空间链表的头部
    	return bp;
    }
    if(prev_alloc && !next_alloc)
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        fix_linklist(NEXT_BLKP(bp)); // 把下一个空闲块脱链
        PUT(HDRP(bp), PACK(size,0));
        PUT(FTRP(bp), PACK(size,0));
    }
    else if(!prev_alloc && next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        fix_linklist(PREV_BLKP(bp)); // 把上一个空闲块脱链
        PUT(FTRP(bp),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp = PREV_BLKP(bp);
    }
    else
    {
        size +=GET_SIZE(FTRP(NEXT_BLKP(bp)))+ GET_SIZE(HDRP(PREV_BLKP(bp)));
        fix_linklist(PREV_BLKP(bp)); // 把上一个空闲块脱链
        fix_linklist(NEXT_BLKP(bp)); // 把下一个空闲块脱链
        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp = PREV_BLKP(bp);
    }
    insert_to_list(bp); // 插入对应空间链表的头部
    return bp;
}

在合并之后，需要把被合并的空闲块脱链，最后新的空闲块插入对应的空间链表中

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
inline void insert_to_list(char *p)
{
    char *root = find_list_root(GET_SIZE(HDRP(p))); 
    char *prevp = root; // 获取root的地址
    char *nextp = GET(root); // 获取root指向的那个空闲块(可能为NULL)

    while(nextp!=NULL) // 优化操作，写上可以增加1分
    {
        if(GET_SIZE(HDRP(nextp))>=GET_SIZE(HDRP(p))) 
            break;
        prevp = nextp;
        nextp = GET(NEXT_LINKNODE_RP(nextp));
    }
    if(prevp == root) // 插入该空间链表的头部(没有进行优化操作)
    {
        PUT(root,p); /* PUT(prevp,p); */
        PUT(NEXT_LINKNODE_RP(p),nextp);
        PUT(PREV_LINKNODE_RP(p),NULL);
        if(nextp!=NULL) // 根据优化操作进行调整
            PUT(PREV_LINKNODE_RP(nextp),p);
    }
    else // 插入该空间链表的中段（受优化操作影响）
    {
        PUT(NEXT_LINKNODE_RP(prevp),p);
        PUT(PREV_LINKNODE_RP(p),prevp);
        PUT(NEXT_LINKNODE_RP(p),nextp);
        if(nextp!=NULL) 
            PUT(PREV_LINKNODE_RP(nextp),p);
    }
}

基本逻辑：

一，先获取当前空间链表，进行优化操作：

  • 在同一个空间链表中，空闲块的大小也是有差异的，该优化操作会获取“root指向的那个空闲块”（第一个空闲块）比较改空闲块的大小，如果不符合条件，程序就会把“下一个空闲块”当做“root”继续进行后续操作（相当于把“root”和“第一个空闲块”向后“平移”了1个单位），这样操作保证了：小内存块在前，大内存块在后

二，后续操作要分情况进行：

  • 插入该空间链表的头部：在“root”中写入指向它前驱的指针，在它的前驱中写入NULL，后继中写入第一个内存块的地址，最后调整第一个内存块的前驱指针
  • 插入该空间链表的中段：在“prevp”的后继中写入它自己的指针，在它的前驱中写入“prevp”，后继中写入“nextp”，最后调整“nextp”（第一个内存块）的前驱指针

1645520942860

整体逻辑：

结合“find_fit”来看，本程序才用了 半个LIFO队列 （后入先出，但又不完全是）

  • 获取空闲块时：从前往后进行遍历
  • 插入空闲块时：尽可能插入头部

这种对内存块进行大小排序，优先获取小内存块的做法的确提高了效率（指多打了1分）

打分&完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*  分离式空闲链表+首次适配 */
➜  [/home/ywhkkx/malloclab-handout] ./mdriver -v
Team Name:ateam
Member 1 :Harry Bovik:bovik@cs.cmu.edu
Using default tracefiles in /home/ywhkkx/malloclab-handout/traces/
Measuring performance with gettimeofday().

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.000104 54645
 1       yes   99%    5848  0.000097 60538
 2       yes   99%    6648  0.000271 24559
 3       yes  100%    5380  0.000103 52182
 4       yes   99%   14400  0.000096150000
 5       yes   95%    4800  0.001038  4624
 6       yes   95%    4800  0.000852  5636
 7       yes   55%   12000  0.000177 67912
 8       yes   51%   24000  0.000557 43103
 9       yes   22%   14401  0.042128   342
10       yes   30%   14401  0.002138  6737
Total          77%  112372  0.047560  2363

Perf index = 46 (util) + 40 (thru) = 86/100
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/* 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 SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12) 
#define MAX(x,y) ((x) > (y)? (x) : (y))
#define PREALLOC(x) ((!x) ? 0 : 2)
#define PACK(size,alloc)    ((size) | (alloc))
#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) 
#define GET_PREALLOC(p) (GET(p) & 0x2)
#define HDRP(bp)        ((char *)(bp) - WSIZE)
#define FTRP(bp)   ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
#define PREV_LINKNODE_RP(bp) ((char*)(bp))
#define NEXT_LINKNODE_RP(bp) ((char*)(bp)+WSIZE)
#define NEXT_BLKP(bp)   ((char*)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp)   ((char*)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))


static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void* find_fit(size_t asize);
static void place(void* bp, size_t asize);
void insert_to_list(char* p);
void fix_linklist(char* p);
inline char* find_list_root(size_t size);
static char* heap_listp = NULL;
static char* block_list_start = NULL;

/*
 * mm_init - initialize the malloc package.
 */

int mm_init(void)
{
    if ((heap_listp = mem_sbrk(14 * WSIZE)) == (void*)-1)
        return -1;
    PUT(heap_listp, 0);
    PUT(heap_listp + (1 * WSIZE), 0);
    PUT(heap_listp + (2 * WSIZE), 0);
    PUT(heap_listp + (3 * WSIZE), 0);
    PUT(heap_listp + (4 * WSIZE), 0);
    PUT(heap_listp + (5 * WSIZE), 0);
    PUT(heap_listp + (6 * WSIZE), 0);
    PUT(heap_listp + (7 * WSIZE), 0);
    PUT(heap_listp + (8 * WSIZE), 0);
    PUT(heap_listp + (9 * WSIZE), 0);
    PUT(heap_listp + (10 * WSIZE), 0);
    PUT(heap_listp + (11 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (12 * WSIZE), PACK(DSIZE, 1));
    PUT(heap_listp + (13 * WSIZE), PACK(0, 1));

    block_list_start = heap_listp;
    heap_listp += (12 * WSIZE);

    if ((extend_heap(CHUNKSIZE / DSIZE)) == NULL)
        return -1;
    return  0;
}

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

    size = (dwords % 2) ? (dwords + 1) * DSIZE : dwords * DSIZE;

    if ((long)(bp = mem_sbrk(size)) == (void*)-1)
        return NULL;
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(PREV_LINKNODE_RP(bp), NULL);
    PUT(NEXT_LINKNODE_RP(bp), NULL);

    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

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

    /*coalesce the block and change the point*/
    if (prev_alloc && next_alloc)
    {
        insert_to_list(bp);
        return bp;
    }
    if (prev_alloc && !next_alloc)
    {
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        fix_linklist(NEXT_BLKP(bp));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    else if (!prev_alloc && next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        fix_linklist(PREV_BLKP(bp));
        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    else
    {
        size += GET_SIZE(FTRP(NEXT_BLKP(bp))) + GET_SIZE(HDRP(PREV_BLKP(bp)));
        fix_linklist(PREV_BLKP(bp));
        fix_linklist(NEXT_BLKP(bp));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    insert_to_list(bp);
    return bp;
}

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */

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 = (DSIZE) * ((size + (DSIZE)+(DSIZE - 1)) / (DSIZE));
    if ((bp = find_fit(asize)) != NULL)
    {
        place(bp, asize);
        return bp;
    }

    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize / DSIZE)) == NULL)
    {
        return NULL;
    }
    place(bp, asize);
    return bp;
}

/*
 * mm_free - Freeing a block does nothing.
 */

void mm_free(void* bp)
{
    if (bp == 0)
        return;
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(NEXT_LINKNODE_RP(bp), NULL);
    PUT(PREV_LINKNODE_RP(bp), NULL);
    coalesce(bp);
}

static void* find_fit(size_t size)
{
    char* root = find_list_root(size);
    for (root; root != (heap_listp - (2 * WSIZE)); root += WSIZE)
    {
        char* tmpP = GET(root);
        while (tmpP != NULL)
        {
            if (GET_SIZE(HDRP(tmpP)) >= size)
                return tmpP;
            tmpP = GET(NEXT_LINKNODE_RP(tmpP));
        }
    }
    return NULL;
}

static void place(void* bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));
    fix_linklist(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));
        PUT(NEXT_LINKNODE_RP(bp), 0);
        PUT(PREV_LINKNODE_RP(bp), 0);
        coalesce(bp);
    }
    else
    {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */

void* mm_realloc(void* ptr, size_t size)
{
    size_t oldsize = GET_SIZE(HDRP(ptr));
    void* newptr = mm_malloc(size);
    if (!newptr)
        return 0;
    if (!ptr)
        return newptr;
    memcpy(newptr, ptr, (size < oldsize ? size : oldsize));
    mm_free(ptr);
    return newptr;
}

inline char* find_list_root(size_t size)
{
    int i = 0;
    if (size <= 8) i = 0;
    else if (size <= 16) i = 1;
    else if (size <= 32) i = 2;
    else if (size <= 64) i = 3;
    else if (size <= 128) i = 4;
    else if (size <= 256) i = 5;
    else if (size <= 512) i = 6;
    else if (size <= 2048) i = 7;
    else if (size <= 4096) i = 8;
    else i = 9;
    return block_list_start + (i * WSIZE);
}

inline void fix_linklist(char* p)
{
    char* root = find_list_root(GET_SIZE(HDRP(p)));
    char* prevp = GET(PREV_LINKNODE_RP(p));
    char* nextp = GET(NEXT_LINKNODE_RP(p));

    if (prevp == NULL)
    {
        if (nextp != NULL)PUT(PREV_LINKNODE_RP(nextp), 0);
        PUT(root, nextp);
    }
    else
    {
        if (nextp != NULL)PUT(PREV_LINKNODE_RP(nextp), prevp);
        PUT(NEXT_LINKNODE_RP(prevp), nextp);
    }

    PUT(NEXT_LINKNODE_RP(p), NULL);
    PUT(PREV_LINKNODE_RP(p), NULL);
}

inline void insert_to_list(char* p)
{
    char* root = find_list_root(GET_SIZE(HDRP(p)));
    char* prevp = root;
    char* nextp = GET(root); 

    while (nextp != NULL)
    {
        if (GET_SIZE(HDRP(nextp)) >= GET_SIZE(HDRP(p)))
            break;
        prevp = nextp;
        nextp = GET(NEXT_LINKNODE_RP(nextp));
    }
    if (prevp == root)
    {
        PUT(root, p);
        PUT(NEXT_LINKNODE_RP(p), nextp);
        PUT(PREV_LINKNODE_RP(p), NULL);
        if (nextp != NULL)
            PUT(PREV_LINKNODE_RP(nextp), p);
    }
    else
    {
        PUT(NEXT_LINKNODE_RP(prevp), p);
        PUT(PREV_LINKNODE_RP(p), prevp);
        PUT(NEXT_LINKNODE_RP(p), nextp);
        if (nextp != NULL)
            PUT(PREV_LINKNODE_RP(nextp), p);
    }
}