malloc lab

为什么开这个仓库

在github上看了别人写的csapp的malloc lab，总感觉迷迷糊糊，csapp的lab只是叫你写malloc和free之类的内存操作接口，但是并没有直接让你看到内存的布局，编写者对程序是如何工作的也知之甚少，所以看完csapp的malloc lab，我决定自己写一个malloc lab，自己设置一个虚拟的内存，自己操作这块内存，自己测试程序的运行状况

设置虚拟内存

（有关malloc的代码都将分布在mymalloc.h中，测试mymalloc.h的代码分布在demo.c中）

#define MAX_MEM_SIZE 1000000

uint8_t MEMORY[MAX_MEM_SIZE] = {0};

首先分配一个全局数组，uint8_t刚好是char类型的长度，数组的大小就是1000000字节，用这个数组来模拟内存，稍后，我们的heap将从这片虚拟的内存中分配

heap

uint8_t *pstart, *pend;

void heap_init()
{
    pstart =  MEMORY;
    pend   = &MEMORY[4096];
}

首先定义了两个全局指针，pstart和pend，pstart指向heap的开始位置，pend指向heap结束位置的后一个字节，pend并不属于heap区域，heap区域是pstart到pend-1之间的区域

heap_init函数用于初始换heap区域，heap的起始位置与MEMORY重叠，heap的初始区域是MEMORTY下标0~4095这块4096字节大小的区域

heap应该是可以调节大小的，在ptmalloc中使用sbrk函数来调节heap区域的大小

sbrk函数原型：

void* sbrk(intptr_t increment);

参数increment是一个整数（可以是负数），用于与heap末位置相加来调整heap的大小，函数的返回值是上一次heap的末位置，所以如果increment是0，则会获取当前heap末位置的指针

由此，定义我们自己的sbrk函数：

void* mysbrk(int increment)
{
    void* pret = pend;
    pend += increment;
    return pret;
}

测试heap：

demo_heap.c

#include<stdio.h>
#include"mymalloc.h"

int main()
{
    heap_init();
    printf("origin heap:\n");
    printf("pstart: %p\npend: %p\nheap_size: %ld\n", pstart, pend, pend-pstart);
    
    printf("\nadd 10 bytes:\n");
    mysbrk(10);
    printf("pstart: %p\npend: %p\nheap_size: %ld\n", pstart, pend, pend-pstart);

    printf("\nsub 5 bytes\n");
    mysbrk(-5);
    printf("pstart: %p\npend: %p\nheap_size: %ld\n", pstart, pend, pend-pstart);

    return 0;
}

看起来一切正常

chunk

在ptmalloc中，每次分配出来的内存称为chunk，chunk的结构如下：

每个chunk的开头都有两个dword，第一个dword是prev_size，记录上一个chunk的size，第二个dword是size，记录本chunk的大小，size字段的最低两个bit，一个是M，代表这个chunk是否是mmap()函数分配的，另一个是P，代表当前chunk是否处于使用状态（为什么可以复用这两个bit的原因将在后文解释），开头的两个字之后就是用户可以使用的区域了，也就是data区域，

是否是mmap()分配的好理解，每次我们调用malloc时，都会传递一个表示申请内存大小的size作为参数，当这个参数在一定范围内时，malloc是从heap中分配内存来返回给用户使用，但是当size超出这个范围时，可能是因为heap不够大，也可能是为了提高内存利用率（大块内存直接由操作系统可以提高内存的利用率，减少内存碎片的产生），这块内存将由mmap分配，由mumap释放，分配和释放都是直接由操作系统进行，M为1时表示这块chunk是由mmap分配的，为0时表示不是由mmap分配的（在我们的实现中将不考虑mmap）

是否处于使用状态又是什么意思？

前面提到过，mmap分配的内存直接由操作系统管理，mumap之后直接返还给操作系统，但是如果一块内存不是mmap分配的，那么这块内存将由堆管理器管理，free掉这块内存后，不会直接归还给操作系统，堆管理器会将其统一管理起来，这些内存仍然以chunk的形式存在，但是free掉之后，我们就称其为free chunk，没有被free的chunk就是正在处于使用状态的chunk，他的P标志位会被设置为1，free chunk的P标志位则是0

那么为什么可以复用size的最低两个bit呢？

因为在32位机器上，chunk的size默认是16的整数倍，在64位机器上，chunk的size默认32的整数倍，那么chunk的size必定是8的整数倍，8的二进制表示为1000，最后三个bit永远是0，不会被使用到，所以可以复用size字段的最低两个bit

当chunk处于使用状态时，chunk的data字段可能时垃圾数据，也可能是用户填充的数据，当chunk被free之后，chunk就变成了free chunk，free chunk的data字段的前两个dword是有意义的（由堆管理器设置），如图：

fd是一个指针，指向上一个free chunk

bk是一个指针，指向下一个free chunk

可能有人现在已经懵了，什么上一个chunk的size，什么指向上一个free chunk

首先明确一点，chunk不等与free chunk

chunk也可能是正在被使用的chunk，malloc分配出一个chunk之后，他就是chunk，正在被使用的chunk

free一个正在被使用的chunk后，它还是chunk，但是是free chunk

chunk包含了inuse chunk和free chunk

还有一点就是，chunk是物理连续的，但free chunk不一定物理连续

chunk是堆中一个个物理相邻的内存块，堆管理器保证chunk是物理相邻的

free chunk是bin中的双向链表：

显而易见的是：不可能所有的free chunk都是物理相邻的，因为它们中间还分布着inuse chunk，所以堆管理器将所有free chunk的信息保存到bin中（free chunk的实体仍然在heap中），为什么要将free chunk的信息收集起来？这样做的目的后面再说

我们现在要做的就是：

调用mallo时，在heap中创建chunk
调用free时，将free chunk的信息保存到bin中（为什么是bin？如果ptmalloc是我写的，我叫它shit都行）

我们每次创建chunk都是紧跟在已创建的chunk之后，所以为了方便的找到这个位置，我们定义一个ptop_chunk指针指向已分配的chunk的末尾，那么显然，我们每次创建chunk都相当于是在切割堆中剩余的空间，我们不妨给这块空间起一个名字，叫top chunk（其实这就是规范的叫法）

uint8_t* ptop_chunk;

一开始，heap中没有chunk，所以这时ptop_chunk应该指向heap的起始位置，也就是pstart

向heap_init中添加代码：

void heap_init()
{
    pstart =  MEMORY;
    pend   = &MEMORY[4096];
    ptop_chunk = pstart;
}

实现第一版mymalloc

mymalloc接收一个参数，然后根据这个size在heap中分配chunk

首先，用户并不会关心chunk是什么，用户需要的是size大小的内存来存放数据，所以chunk的size不应该等于用户要求的size，chunk_size应该还要加上chunk的头部，其次，我们之前提到过，64位模式下，size必须是16的整数倍，如果用户请求17个字节，那么chunk的大小因该是：

16(chunk_header) + 17(request_size) + 15(padding) = 48

15个字节的填充保证了chunk的size为16的倍数（在ptmalloc中其实并非如此，这只是第一版，我会在后面进行改进，实际是用户请求17个字节，chunk的大小将是32个字节）

我们可以这样计算chunk的size：（暂时认为这是正确的吧！）

你可能会想到int64_t会发生溢出，但其实在ptmalloc中，如果申请的size过大，mmap将代替堆管理器工作，但是我们的malloc中不涉及mmap，那就默认用户请求的size不会造成溢出吧

int64_t chunk_size = (size + 16) + (size % 16 ? 16 - (size%16) : 0);

接着就是在heap中布置chunk结构了，我们需要设置的只有chunk的头部，data字段将由用户自行填充

而在chunk_header中，我们当前需要设置的只有size，prev_size是上一个chunk的size，我们在分配这个chunk时，是无法的知上一个chunk的size的，ptmalloc使用了巧妙地方法在其他地方设置prev_size，在这里我们就暂且不设置prev_size，然后就是P标志位（表示chunk是否处于使用状态），当前，我们的malloc每次都是从top_chunk中切割chunk，在这种情况下，我们总是将P标志位置为1，你可能会想：将P置为1是否代表top_chunk的前一个chunk总是inuse？

答案是肯定得，但是以现在的代码来解释这个断言是没有道理的，在后面我们将完善代码，使之更像ptmalloc，那是，我再来解释为什么top_chunk的前一个chunk必定使inuse的

定义一个打包函数，可以将chunk_size和P标志位打包

typedef enum p {free, inuse} P;

/*
 * 将size和P打包
 */
int64_t pack(int32_t size,  P statu)
{
    return size | statu;
}

将打包后的数值放入size字段：

size字段使chunk的第二个dword

*((int64_t*)(ptop_chunk) + 1) = pack(chunk_size, inuse);

然后将ptop_chunk加上chunk_size，并返回指向data字段的指针

void* ret = (void*)ptop_chunk + 16;
ptop_chunk += chunk_size;
return ret;

最后，考虑一下特殊情况，当mallo第一个chunk是，因为第一个chunk前面不会有chunk，所以我们可以将prev_size设为0

定义一个全局变量表示chunk的数量

//chunk的数量
unsigned chunk_num = 0;

如果是第一个chunk，将prev_size置为0

if (chunk_num == 0)
    {
        *(int64_t*)ptop_chunk = 0;
    }

第一版mymalloc完整代码

void* mymalloc(int64_t size)
{
    //不合法的size
    if (size <= 0)
    {
        return NULL;
    }
    //计算chunk的size
    int64_t chunk_size = (size + 16) + (size % 16 ? 16 - (size%16) : 0);

    //在heap中布置chunk结构
    *((int64_t*)(ptop_chunk) + 1) = pack(chunk_size, inuse);

    //如果是第一个chunk
    if (chunk_num == 0)
    {
        *(int64_t*)ptop_chunk = 0;
    }
    chunk_num++;

    void* ret = (void*)(ptop_chunk + 16);
    ptop_chunk += chunk_size;
    return ret;
}

测试第一版mymalloc

demo_mymalloc_version_1.c

#include<stdio.h>
#include"mymalloc.h"

int main()
{
    heap_init();

    int* pchunk1 = (int*)mymalloc(sizeof(int));

    int* pchunk2 = (int*)mymalloc(sizeof(int));

    char* pchunk3 = (char*)mymalloc(sizeof(char) * 8);

    char* pchunk4 = (char*)mymalloc(sizeof(char) * 17);

    int* pchunk5 = (int*)mymalloc(sizeof(int) * 5);

    printf("patsrt: %p\n", pstart);

    printf("\nchunk1: %p\n", pchunk1);
    printf("chunk2: %p\n", pchunk2);
    printf("chunk3: %p\n", pchunk3);
    printf("chunk4: %p\n", pchunk4);
    printf("chunk4: %p\n", pchunk5);

    printf("\nheap:\n");
    for (int i = 0; i < (ptop_chunk-pstart)/8; i++)
    {
        printf("%p %016lx\n", ((int64_t*)pstart)+i, *(((int64_t*)pstart)+i));
    }

    return 0;
}

测试5次malloc后heap中的内存分布，红色的框框是chunk头，箭头指向的是chunk的数据段

从测试来看，基本满足我们的要求

第一版free

free接收一个指针作为参数，free做两件事：

将P位置置为free
将free后的chunk放入bin中

现在，我们将bin设置为单向链表，这是最简单的链表，也是ptmalloc中fastbin使用的结构，在之后我们会使用更加复杂的结构

首先，定义两个函数快速转换pdata和pchunk

void* pdata2pchunk(void* pdata)
{
    return (void*)((uint8_t*)pdata-16);
}

void* pchunk2pdata(void* pchunk)
{
    return (void*)((uint8_t*)pchunk+16);
}

pdata是指向chunk中数据字段的指针，是返回给用户的指针

pchunk是指向chunk开头的指针，也就是指向prev_size字段

定义一个bin头指针

//bin头指针
intptr_t* bin;

第一版myfree函数

void myfree(void* pdata)
{
    //获取指向chunk头部的指针
    void* pchunk = pdata2pchunk(pdata);
    //将P标志位置为free
    *((int64_t*)pdata-1) &= ~0x1;
    
    if(bin == NULL) //如果bin中没有chunk
    {
        bin = (intptr_t*)pchunk;
        *(intptr_t*)pdata = 0;
    }
    else //bin中有chunk
    {
        *(intptr_t*)pdata = (intptr_t)bin; //将前一个bin保存到这一个chunk的fd字段
        bin = (intptr_t*)pchunk; //将这一个chunkd
    }
}

一开始，bin里面什么都没有

执行完依次free之后，bin中存放的是指向chunk_a的指针，这个指针指向了chunk_a，并且chunk_a的fd指针被置为0

执行完第二次free之后，bin中保存的是指向chunk_b的指针，而不再是chunk_a的指针了，我们也不必担心chunk_a会丢失，此时chunk_b的fd字段保存的是pchunk_a，所以它会指向chunk_a

后面的free以此类推

测试第一版myfree

demo_myfree_version_1.c

#include<stdio.h>
#include"../mymalloc.h"

int main()
{

    heap_init();
    int* a = (int*)mymalloc(sizeof(int));
    int* b = (int*)mymalloc(sizeof(int));
    int* c = (int*)mymalloc(sizeof(int));

    *a = 1;
    *b = 2;
    *c = 3; 

    myfree(a);
    myfree(b);
    myfree(c);

    printf("bin: %p\n", bin);

    printf("\nheap:\n");
    for (int i = 0; i < (ptop_chunk-pstart)/8; i++)
    {
        printf("%p %016lx\n", ((int64_t*)pstart)+i, *(((int64_t*)pstart)+i));
    }

    printf("\nbin:\n");

    intptr_t* pItem = bin;
    intptr_t fd = *(intptr_t*)pchunk2pdata(pItem);
    while(fd != 0)
    {
        printf("%p -> ", pItem);
        pItem = (intptr_t*)(fd);
        fd = *(intptr_t*)pchunk2pdata(pItem);
    }
    printf("%p\n", pItem);

    return 0;
}

从内存布局也可以看出：

bin指向chunk_c，chunk_a的fd指向chunk_b，chunk_b的fd指向chunk_a

使用free chunk

至此，我们实现了可以切割top chunk来分配chunk的malloc，实现了可以将未使用的chunk放入bin的free

你可能回想：为什么要把free chunk收集起来？

答案显而易见，收集起来是为了再次使用

如果你在程序的一个地方malloc了20个字节，那么有很大的可能你会在程序的其他地方多次malloc20个字节的内存，如果每次都从top chunk中去切割是很不方便的，还会造成内存碎片

所以每次free，我们都将free chunk放入bin中，下一次malloc内存是，我们下去bin中查找有没有合适大小的free chunk，如果有，那就直接将这个free chunk返回给用户

定义一个函数，用于由pchunk推算该chunk的size

int64_t pchunk2size(void* pchunk)
{
    return *(int64*)((int8_t*)pchunk+8) & ~0x1;
}

在mymalloc函数中添加如下代码：

pfree_chunk用来指向一个free_chunk，函数best_fit（稍后实现）用来寻找合适的free_chunk，如果找到，返回该chunk并将其返回给用户，如果未找到，返回NULL，继续从top chunk中切割chunk

void* pfree_chunk;
if ((pfree_chunk = best_fit(chunk_size)) != NULL)
{
    *(int64_t*)((int8_t*)pfree_chunk+8) |= 0x1; //将P标志位设置位inuse
    return pchunk2pdata(pfree_chunk);
}

best_fit函数，顾名思义：寻找最匹配的free chunk

void* best_fit(int64_t size)
{
    // 如果bin为空，直接返回NULL
    if (bin == NULL)
    {
        return NULL;
    }
    //遍历bin寻找合适的free chunk
    intptr_t* pItem = bin;
    intptr_t fd = *(intptr_t*)pchunk2pdata(pItem);
    while(fd != 0)
    {
        if(pchunk2size(pItem) == size)
        {
            return (void*)pItem;
        }
        pItem = (intptr_t*)(fd);
        fd = *(intptr_t*)pchunk2pdata(pItem);
    }
    if(pchunk2size(pItem) == size)
    {
        return (void*)pItem;
    }

    return NULL;
}

第二版mymalloc：

void* mymalloc(int64_t size)
{
    //不合法的size
    if (size <= 0)
    {
        return NULL;
    }
    //计算chunk的size
    int64_t chunk_size = (size + 16) + (size % 16 ? 16-(size%16) : 0);

    void* pfree_chunk;
    if ((pfree_chunk = best_fit(chunk_size)) != NULL)
    {
        *(int64_t*)((int8_t*)pfree_chunk+8) |= 0x1; //将P标志位设置位inuse
        return pchunk2pdata(pfree_chunk);
    }

    //在heap中布置chunk结构
    *((int64_t*)(ptop_chunk) + 1) = pack(chunk_size, inuse);

    //如果是第一个chunk
    if (chunk_num == 0)
    {
        *(int64_t*)ptop_chunk = 0;
    }
    chunk_num++;

    void* ret = (void*)(ptop_chunk + 16);
    ptop_chunk += chunk_size;
    return ret;
}

测试使用free chunk

#include<stdio.h>
#include"../mymalloc.h"

int main(void)
{
    heap_init();

    char* a = (char*)mymalloc(0xf); //0x20
    char* b = (char*)mymalloc(0x11); //0x30
    char* c = (char*)mymalloc(0x21); //0x40

    printf("a: %p\n", a);
    printf("b: %p\n", b);
    printf("c: %p\n", c);

    myfree(a);
    myfree(b);
    myfree(c);

    char* d = (char*)mymalloc(0x12); //0x30
    char* e = (char*)mymalloc(0x22); //0x40
    char* f = (char*)mymalloc(0x32); //0x50

    printf("d: %p\n", d);
    printf("e: %p\n", e);
    printf("f: %p\n", f);


    printf("\nheap:\n");
    for (int i = 0; i < (ptop_chunk-pstart)/8; i++)
    {
        printf("%p %016lx\n", ((int64_t*)pstart)+i, *(((int64_t*)pstart)+i));
    }

    return 0;
}

从测试结果也可以看出free chunk确实被重复使用了

b申请了0x11字节的内存，所以b的chunk size为0x20，b被free之后，bin中就存在了一个size为0x20的free chunk，而后d申请0x12字节的内存，b的chunk size也为0x20，所以此时bin中的那个起初由b使用的free chunk会被再次分配给d使用，c和e同理

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

README.md

README.md

malloc lab

为什么开这个仓库

设置虚拟内存

heap

chunk

实现第一版mymalloc

测试第一版mymalloc

第一版free

测试第一版myfree

使用free chunk

测试使用free chunk

Files

README.md

Latest commit

History

README.md

File metadata and controls

malloc lab

为什么开这个仓库

设置虚拟内存

heap

chunk

实现第一版mymalloc

测试第一版mymalloc

第一版free

测试第一版myfree

使用free chunk

测试使用free chunk