自己实现动态内存分配

4.8 9 投票数

评分

本文写于 2018年11月04日，距今已超过 1 年，距 2020年03月27日的最后一次修改也已超过 3 个月，部分内容可能已经过时，您可以按需阅读。如果图片无法显示或者下载链接失效，请给我反馈，谢谢！

初始化

初始化必须被调用一次，且只能被调用一次：

if (initialized) {
    perror("You should call function mem_init() once and only once.\n");
    exit(-1);
}
if (initialSize <= 0) {
    perror("Positive integer expected.\n");
    m_error = E_BAD_ARGS;
    return -1;
}

划分内存，直接调用mmap()：

void *mem_start = mmap(NULL, initialSize, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0);

那么mmap()的返回值，其实就是整个空闲块列表的头地址。

之后记录头地址的指针地址，然后设置大小，设置链表的next为空表示链表结束：

mem = (MEM_FREE *) mem_start;
mem->size = initialSize - sizeof(MEM_FREE);
mem->next = NULL;

事情就应该到此结束了。

但是，内存要对齐。

所以要通过页表的大小来计算我到底需要多少大小的内存：

int page_size = getpagesize();
initialSize = (initialSize + page_size - 1 + sizeof(MEM_FREE)) / page_size * page_size;

这样计算得到的，就是我最终划分出来的内存的大小。

另外，mmap()里面的文件描述符，定位到/dev/zero：

int fd = open("/dev/zero", O_RDWR);
void *mem_start = mmap(NULL, initialSize, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, fd, 0);
close(fd);

除此而外，加上必要的异常处理，例如，initialSize非法值、mmap()出错……

if (initialSize <= 0) {
    perror("Positive integer expected.\n");
    m_error = E_BAD_ARGS;
    return -1;
}

if (mem_start <= 0) {
    perror("Call function mmap() error.\n");
    return -1;
}

两种维护空闲块列表的思路

类似数组的思路

定义一个头结点：

typedef struct head{
    int isFree;
    int size;
} HEAD;

其中isFree表示该块当前是空闲的还是被使用的，size表示该块的大小，该大小不包括表头。

需要记录的信息就是，mem_begin和mem_end，每次从内存的初始地址开始遍历，直到内存的结束地址。

1541308606230

如图所示，假设我申请的这块内存是在 $500$ 开始的，表头是 $2$ 个int一共是 $8$ 个字节。

那么，mem_begin就是 $500$，mem_end就是 $712$。

在图示状态下，内存还有 $2$ 个空闲块，一个大小是 $20$，一个大小是 $80$。

有一个正在被使用的内存，大小是 $50$，另一个正在被使用的内存，大小是 $30$。

在这样的模型下面，分配内存就变得非常简单。

在分析的时候，我只是随便找一个空闲块来分配出去，主要是为了方便分析。

具体实现的时候，这个空闲块是通过某种策略（最优算法、最差算法、首次匹配算法、首次循环匹配算法……）来确定的。

现在要申请一个大小为 $50$ 的内存。

那就从mem_begin，即 $500$ 开始遍历，令ptr为 $500$。

先看看ptr->isFree，发现是空闲的，然后检查大小够不够，发现 $20 < 50$ 不够，那就继续。

此时ptr = ptr + sizeof(HEAD) + ptr->size，即 $500+8+20=528$。

先看看ptr->isFree，发现是在使用中的，那就继续。

此时ptr = ptr + sizeof(HEAD) + ptr->size，即 $528+8+50=586$。

用类似的方法，找到了一个放得下的空闲块。

那么怎么分配呢？

首先要把这一块标记为使用中，即设置isFree为false，然后设置大小为 $50$。

1541309164410

这时候ptr是 $586$，那么ptr + sizeof(HEAD)就是我可以返回出去的地址，即 $586+8=594$就应该是我返回给主程序的地址。

别急着返回！

$80$ 的空间放下了 $50$，剩下的大小要更新。

首先明确了，ptr + sizeof(HEAD)就是我可以返回出去的地址，这个空闲块的结束的地方是ptr + sizeof(HEAD) + ptr->size。

对于上面这种情况，就应该是 $644$ 的地方结束。

原来的大小是 $80$，分配出去了 $50$，还剩下了 $22$，因为分配出去一块，还需要多一个表头记录信息，所以不是 $30$，是 $22$。

这也意味着，之后在判断空闲块大小够不够分配的时候，要把多出来的表头的大小也一起考虑进去。

因此，在 $644$ 地方，我要令HEAD* h = (HEAD*)(644); h->isFree = false; h->size = 22;。

怎么把 $644$ 地址变成一个表头结点，怎么计算 $22$，怎么维护信息，就是各自实现的问题了。

那么，最后就应该变成下面这个样子。

1541309620888

这时候全部做完了，可以把 $594$ 这个地址返回出去了，分配就结束了。

下面考虑free的事情。

这只是一个指针，不带大小的，如何确定大小，就非常简单了，因为显然，一定是给的 $536,594$ 这些位置的地址，那么给定的ptr - sizeof(HEAD)就可以定位到表头结点，然后设置isFree为true就好了。

例如，要释放 $594$ 这个位置，那么 $594-8=586$ 就是这个内存对应的表头的位置，直接令 $586$ 的isFree为true就好了，size都不用动的。

似乎一切都很美好，但是别忘了还有一个事情，空闲块是要合并的。

如果现在内存是 $3$ 个大小为 $10$ 的空闲块，但是我要申请 $20$，明明是够的，但是内存都碎片化了，导致我以为没有足够的空间。

因此要合并。

由于这是数组实现的，所以很显然，每次合并只有可能和自己的左边或者右边合并。

也就是说，当 $594$ 被释放的时候，我只要检查他前面那个是不是空闲的、后面那个是不是空闲的，是，就合并。

例如，$594-8=586$ 被设置成free，然后 $586+8+50=644$ 的地方发现也是空闲的，那么这两块就可以合并。

只需要令 $586$ 的size加上 $644$ 的size再加上sizeof(HEAD)就可以了。

1541310134950

那么怎么找到前面的邻居？

好像通过直接的内存加减不能完成。

但是一定是可以通过某些手段来达到的。

例如，表头增加一个字段？prev、next？

可是，表头信息越多，就意味着内存实际可以用的越少，因为我需要大量的空间来记录信息。

如果不这样，至少，从头遍历是可以的，大不了从mem_begin遍历到mem_end，每次加上sizeof(HEAD)和ptr->size，直到找到被回收的那个位置的地址。

但是这样似乎花费的时间代价又大了，不划算，效率低。

但是不管怎么说，问题肯定是能解决的，总归是有办法的，而且办法很多，这里就不详细展开了。

那么，用数组实现的思路就介绍清楚了。

不过，这样做还会有一些潜在的风险，下面用链表思路的分析中会指出。

类似链表的思路

内存嘛，用链表来做会更加炫酷。

这个思路和上面那个思路是类似的，只是具体实现细节上面考虑的方面各不相同。

也没有孰优孰劣的分别，各有各的特色，也各有各的优点和缺点。

表头我是这样定义的：

typedef struct memory_use_header_t {
    int size;
    long long magic;
} MEM_USE;

typedef struct memory_free_node_t {
    int size;
    struct memory_free_node_t *next;
} MEM_FREE;

我把空闲的链表和使用中的链表分开了。

其中，memory_free_node_t彻底就是一个空闲块链表了，每一个链表的表头记录空闲块的大小，然后指向下一个空闲块。

memory_use_header_t是使用中的块的信息，保留了一个size记录的是使用中这块的大小是多少，以及，一个magic魔术数。

这个魔术数的作用下面会提到。

至于为什么magic我定义了long long。

因为我的服务器是 $64$ 位系统的，所以一个指针的大小就是 $8$，加上一个int是 $4$，一共是 $12$，又因为操作系统做了 $8$ 字节内存对齐，所以 $12$ 个字节被对齐到了 $16$ 个字节，于是，sizeof(MEM_FREE)是 $16$。

如果我令MEM_USE是int size和int magic的话，就是 $8$ 个字节，对齐以后还是 $8$ 个字节。

这样会带来什么问题，就是回收的时候要增加很多无谓的判断。

例如，有一个size是 $3$ 的块被分配出去了，那么实际占用的内存是一个 $8$ 的MEM_USE表头加上一个 $3$ 的内存，一共用掉了 $11$。

之后我试图把这个块回收，发现回收的时候，一共只有 $11$，竟然连MEM_FREE的表头都放不下。

当然，之后的作业要求有提到，要做 $8$ 字节对齐，那么，申请size是 $3$ 的块，实际上被分配出去的是 $8$，加上MEM_USE的表头，一共是用掉了 $16$，回收的时候，至少可以放得下MEM_USE的表头，不会出现放不下的情况。

但是，这样的话，这个MEM_FREE的size就是 $0$，白白浪费了一个表头，啥事都没干，还白白要我的代码多判断很多东西。

所以我为了代码简洁，以及运行的高效（不需要各种判断），直接令MEM_USE和MEM_FREE的大小是一样的就好了，那就用了一个long long。

或许是我懒？

当然，还有一种方案，就是继续把MEM_FREE和MEM_USE合并起来。

typedef struct memory_header_t {
    int size;
    void* magic;
} MEM_HEAD;

一个表头扮演两个角色。

当作为MEM_FREE的时候，void* magic指向的是下一个空闲块表头的地址，最后一个空闲块的void* magic指向NULL，即void* magic充当了MEM_FREE* next的角色。

当作为MEM_USE的时候，void* magic = -1，或者在合法地址区间之外的一个地址。

那么，只需要判断MEM_HEAD -> magic 是不是等于(nil)或者别的MAGIC_ADDR就可以判断这是空闲块还是使用中的块。

free = (magic == MEM_IN_USE_MAGIC)

不好，万一正好某个内存是我在用的怎么办？

用0？可以。用一个void* = -1来表示？可以。

但是强行把int当做指针，或者把地址当做int可不是什么好习惯。

void*和MEM_HEAD*最好也别混起来用。

下面说说魔术数的使用。

能够由我来free的块，必须是我分配出去的，这意味着，它的地址减去表头的大小，一定是我存放表头信息的地方，且，整个地址，都在我的合法的地址区间之内。

数组实现的并不能解决这个问题——给一个ptr，减去 $8$？

那万一我给了一个：

int a = 3;
free(&a);

a的地址已经是不知道哪里的东西了，根本就不是我所管理的合法区间之内的地址，是别的地方的地址。

你这做了a的地址减去 $8$？那个地方就更不知道在哪里了，那个地方的void*被变成了HEAD*，然后在那个地址修改了free，天知道那个地方原来存的是什么数据，是int b还是某个char* s？

而魔术数的出现解决了这个问题，我先减去 $8$，看看，看看那里的魔术数是不是我的魔术数，如果是，那么这就是我分配出去的，否则，就报错。

if (head->magic != MEM_IN_USE_MAGIC) {
    perror("Maybe this pointer is not allocated by my allocator, refused to free.\n");
    m_error = E_BAD_POINTER;
    return (-1);
}

1541312390233

如图所示，空闲块列表是一个链表，head指向的是第一块空闲块的表头所在的地址，这个head->size是 $40$，head->next是下一个空闲块的表头的地址。

之后的空闲块链表的结点也是类似的，记录的是自己空闲块的大小，以及下一个空闲块的地址。

最后一个空闲块的next指向的是NULL。

而，使用中的块，其实只需要记录size就可以了，不需要串成链表。

1541312597676

下面就可以开始分配了。

我通过某种方法判断到了，需要分配的空闲块的地方在 $546$ 这个地方，我申请的大小是 $10$，放得下，加上表头也只有 $26$。

那么我就做如下修改。

首先，令ptr指向 $546$，然后ptr+sizeof(MEM_USE)就是我要返回的地址，即，分配以后返回的地址是 $546+16=562$。

由于上面保证了MEM_FREE和MEM_USE的大小是一样的，所以这里不需要做额外的计算。

别急着返回！

还修改新的空闲块信息。

$562$ 开始的 $10$ 大小，是我要分配出去的，那么，下一个空闲块表头，应该存放在 $562+10=572$ 的地方。

这个空闲块的大小，应该是原来的 $40$，减去分配出去的 $10$ 和一个 $16$ 的表头，$40-10-16=14$。

那么在 $572$ 的地方，设置size是 $14$，更新next指针为原来的那个空闲块的next。

特别的，对于空闲块列表的第一个空闲块被分配出去的时候，一定要修改空闲块列表的表头head指向的地方。

同样，对于最后一个空闲块列表分配的时候，记得next要指向NULL。

中间的其他的，就如同一般的链表维护，注意指向它的指针，以及它指向的下一个的指针，就没问题了。

1541313097258

得到的应该是类似这样子的。

回收似乎会麻烦一点。

首先，给定一个地址，要回收。

先减去 $16$，看看魔术数是不是我定义的，如果是我定义的，那就可以回收，否则拒绝回收。

那么如果需要回收，是不是就简单地修改表头结点就可以了呢？

由于上面保证了，MEM_USE和MEM_FREE的大小是一样的，且第一个数据域成员都是size，所以表头大小一样，意味着挂回空闲块列表的时候，表头的大小是不受影响的，也就是说size是不需要修改的。

所以，似乎只要简单地把magic换成next就好了。

事实上也确实如此。

但是，挂到哪儿呢？

最简单的，就是挂在表头，或者表的末尾。

不妨挂在表头。

那么就是简单地，令ptr->next = head，然后令head = ptr就好了。

1541313704911

如图，原来的空闲块列表是蓝色的，现在回收了一个绿色的，那么直接做一下指针的修改就可以了。

合并，也非常简单，因为自己就是表头，所以只能和自己后面的那个合并，不需要通过某种手段找到自己前面的空闲块在哪里。

如上面说的，将新的空闲块挂在了链表的表头以后，只需要做如下的计算。

首先明确，自己的开始的地址是head，自己的结束的地址是head + sizeof(HEAD) + head->size。

自己的next的开始的地址是head->next，自己的next的结束的地址是head->next + head->next->size + sizeof(HEAD)。

如果head + sizeof(HEAD) + head->size等于head->next，说明自己后面那个块，和自己是紧紧相邻的，就在自己后面，那么这时候只需要将自己的head->size加上sizeof(HEAD)再加上自己的head->next->size就可以了，然后修改自己的head->next为head->next->next。
如果head->next + head->next->size + sizeof(HEAD)等于head，类似地，只需要修改head->next->size = head->next->size + head->size + sizeof(HEAD)并修改head = head->next。

注意这些操作都需要计算sizeof(HEAD)的大小。

似乎没事？但是间隔着回收就发现有问题了。

1541314286127

按照$1,3,5,2,4$的顺序回收，就会发现，根本没有可以合并的块。

回收$1$的时候，和空闲块不是相邻的，不能合并。

1541314374178

回收了$3$，也不能合并。

1541314411290

全部回收完，根本没有可以合并的块，全部是不连着的。

1541314494037

但是事实上，全部都是空闲的。

所以有没有一种机制能够检测这种情况？

当然有。

最坏的情况，遍历总是可以完成的。

对于给定的块，遍历所有的块，计算所有的块的ptr和ptr + sizeof(HEAD) + ptr->size，比较所有这些地址，总能找到和给定的块相邻的两个块的地址，只要他们是空闲的。

然后，就一定可以通过某种机制通过next指针的指来指去，完成相邻的块的合并。

操作也不复杂，就是链表的基本操作嘛。

然后，对于所有的块，重复执行上面的过程，在一个 $N^2$ 的遍历中，一定可以完成所有块的合并。

如果嫌烦，那就把回收回来的块，不要挂在链表头上了，直接放到指定的地方。

所谓指定的地方，就是他被分配出去的地方。

然后一经放回，就立刻和左右邻居合并。

我用的就是这个策略，我会在下面的代码实现过程中详细说明这个操作过程。

输出空闲块列表

在实现之前，先完成mem_dump()函数，要看个结果。

因为空闲块是以链表的形式保存的。

而mem指向的是空闲块列表的第一个空闲块。

所以，只要遍历链表，就可以输出每一个空闲块的信息。

while (block != NULL) {
    void *beginAddr = (void *) block;
    int size = block->size;
    void *from = beginAddr + sizeof(MEM_FREE);
    void *to = from + size;
    MEM_FREE *next = block->next;
    printf("Header begin at %p, size=%d, from %p to %p, next %p.\n", beginAddr, size, from, to, next);
    block = next;
}

空闲块列表遍历的时候是不应该出现异常的，因为维护恰当的话，整个过程都是正确的，直到遍历到链表结束，正常退出。

但是需要注意一种情况，那就是没有调用mem_init()就尝试mem_dump()。

这种时候是不允许进行的，所以要给出未初始化的错误提示。

if (!initialized) {
    perror("You should call function mem_init() once and only once.\n");
    exit(-1);
}

内存的分配

核心代码

如上文所言，我通过某种分配策略找到了一个可以放得下的空闲块。

得到了这个空闲块的指针block。

然后，只要设置block->size为请求的大小，并返回block + sizeof(MEM_USE)的地址。

在返回之前，要维护空闲块，newFreeBlock = block + block->size + sizeof(MEM_USE)就是新的空闲块的地址，在这个新的地址上，设置newFreeBlock->size = 原block->size - 请求的size - sizeof(MEM_USE)，设置newFreeBlock->next = 原block->next。

代码如下：

int newSize = block->size - sizeq - sizeof(MEM_USE);
MEM_FREE *next = block->next;
MEM_USE *head = (MEM_USE *) block;
head->size = sizeq;
head->magic = MEM_IN_USE_MAGIC;
void *ptr = (void *) head + sizeof(MEM_USE);
block = (MEM_FREE *) (ptr + sizeq);
block->size = newSize;
block->next = next;
return ptr;

当然，特别的，如果分配出去的内存是第一块或者最后一块，还要注意修改空闲块列表的表头的指针。中间其他的部分，只要维护前prev和后next的指针就可以了。

if (last == NULL) {
    mem = block; // 第一块被分配出去了，修改空闲块的表头指针
} else {
    last->next = block; // 否则，block->prev->next修改为新的空闲块的地址
}

多种分配策略

三种分配策略是比较简单的，就是找到合适的内存块。

首次匹配策略，就是找到第一个放得下的。

case M_FIRSTFIT:
while (block != NULL) {
    size = block->size;
    if (sizeq + sizeof(MEM_USE) < size) {
        target = block;
        break;
    } else {
        last = block;
        block = block->next;
    }
}
break;

最优匹配，就是找放得下的里面最小的。

那就要先遍历一遍，然后找到放得下的里面最小的，顺便记录一下它的prev方便后面做事情。

case M_BESTFIT:
while (block != NULL) {
    size = block->size;
    if (sizeq + sizeof(MEM_USE) < size) {
        if (target == NULL || size < target->size) {
            prev = last;
            target = block;
        }
    }
    last = block;
    block = block->next;
}
break;

最差匹配，类似的，遍历一遍，找到最大的空闲块，然后顺便记录一下最大这个的prev。

case M_WORSTFIT:
while (block != NULL) {
    size = block->size;
    if (sizeq + sizeof(MEM_USE) < size) {
        if (target == NULL || size > target->size) {
            prev = last;
            target = block;
        }
    }
    last = block;
    block = block->next;
}
break;

然后做一下异常处理，譬如，全部遍历完，发现没有放得下的空间了，就应该是返回一个错误。

if (target == NULL) {
    printf("No free space.\n");
    m_error = E_NO_SPACE;
    return NULL;
}

又例如，要做 $8$ 字节对齐。

int roundup = 8;
sizeq = ((sizeq / roundup) + 1) * roundup;

诸如其他细节，实现的时候留意一下。

内存的回收

核心代码

一些常规的异常就不提了：没有初始化、检查是不是自己分配出去的块……

下面就是回收。

如上文所提及的，我想要把回收回来的块，直接放在属于它自己的位置。

如上面说的，将新的空闲块挂在了链表的表头以后，只需要做如下的计算。

首先明确，自己的开始的地址是head，自己的结束的地址是head + sizeof(HEAD) + head->size。

自己的next的开始的地址是head->next，自己的next的结束的地址是head->next + head->next->size + sizeof(HEAD)。

如果head + sizeof(HEAD) + head->size等于head->next，说明自己后面那个块，和自己是紧紧相邻的，就在自己后面，那么这时候只需要将自己的head->size加上sizeof(HEAD)再加上自己的head->next->size就可以了，然后修改自己的head->next为head->next->next。

如果head->next + head->next->size + sizeof(HEAD)等于head，类似地，只需要修改head->next->size = head->next->size + head->size + sizeof(HEAD)并修改head = head->next。

注意这些操作都需要计算sizeof(HEAD)的大小。

MEM_USE *head = (void *) (ptr - sizeof(MEM_USE));
void *blockStart = (void *) head;
void *blockEnd = ((void *) head + head->size + sizeof(MEM_USE));
MEM_FREE *location = (MEM_FREE *) mem;
MEM_FREE *last = NULL;

然后遍历，找到属于自己的位置，所谓属于自己的位置，就是，自己的开始地址，小于后一个块的开始地址，大于前一个块的开始地址。

while (location != NULL && (void *) blockStart > (void *) location) {
    last = location;
    location = location->next; 
    // 如果是这样维护的，那么空闲块一定是有序的，所以location的next一定大于当前空闲块结束的地方
}

直接把回收的块放在这里，修改前后的next指针就可以了。

回收的合并

因为内存已经放在了指定的位置，且我们遍历的时候已经留下了prev、block和next，只需要看前后两邻居是不是空闲的、且计算是不是内存地址相邻，就可以完成合并。

以往后合并为例。

先计算出空闲块的结束的地址。

lastEnd = (void *) last + last->size + sizeof(MEM_FREE);

如果地址重合，说明可以合并，修改size即可。

if (lastEnd == blockStart) {
    last->size += head->size + sizeof(MEM_USE);
    merg = 1;
}

向前合并也是类似的。

block->size = head->size + sizeof(MEM_USE) + location->size;
block->next = location->next;

但是需要特别注意的，如果这个回收回来的块，既和前面可以合并，又和后面可以合并，需要注意，它的size只能被加一次，而不能前面加一次，后面又加一次。

if (last != NULL && lastEnd == blockStart) {
    last->size += location->size + sizeof(MEM_FREE);
    last->next = location->next;
}

以及，常规问题，如果合并在了链表头或者别的什么情况，那要注意修改空闲块的头地址。

if (last == NULL) {
    mem = block;
} else {
    last->next = block;
}

在不需要合并的情况下，只要简单地修改前后指针，把他插入到链表的给定位置就可以了。

block->size = head->size;
last->next = block;
block->next = location;

特别的，当插入到表头之前，或者表尾之后，需要特别的处理。

if (merg) 
    return 0;

if (last == NULL) {
    block->next = mem;
    block->size = head->size + sizeof(MEM_USE) - sizeof(MEM_FREE);
    mem = block;
} else if (location == NULL) {
    block->next = NULL;
    last->size = head->size 
}

简单的测试

int main(int argc, const char *argv[]) {
    printf("sizeof(MEM_FREE)=%d\n", sizeof(MEM_FREE));
    printf("sizeof(MEM_USE)=%d\n", sizeof(MEM_USE));
    printf("=================\n");
    mem_init(5000);
    printf("After mem_init(5000):\n");
    mem_dump();
    printf("=================\n");
    void *a = mem_alloc(1000, M_FIRSTFIT);
    printf("After mem_alloc(1000, M_FIRSTFIT):\n");
    mem_dump();
    printf("=================\n");
    void *b = mem_alloc(500, M_BESTFIT);
    printf("After mem_alloc(500, M_BESTFIT):\n");
    mem_dump();
    printf("=================\n");
    mem_free(a);
    printf("After free a:\n");
    mem_dump();
    printf("=================\n");
    void *c = mem_alloc(200, M_BESTFIT);
    printf("After mem_alloc(200, M_BESTFIT):\n");
    mem_dump();
    printf("=================\n");
    void *d = mem_alloc(200, M_WORSTFIT);
    printf("After mem_alloc(200, M_WORSTFIT):\n");
    mem_dump();
    printf("=================\n");
    mem_free(b);
    printf("After free b:\n");
    mem_dump();
    printf("=================\n");
    mem_free(d);
    printf("After free d:\n");
    mem_dump();
    printf("=================\n");
    mem_free(c);
    printf("After free c:\n");
    mem_dump();
    return 0;
}

一切正常。

sizeof(MEM_FREE)=16
sizeof(MEM_USE)=16
=================
After mem_init(5000):
Header begin at 0x7f82ac153000, size=8176, from 0x7f82ac153010 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
now allocating...
block->size=8176,next=(nil)
new size=7152
next=(nil)
After mem_alloc(1000, M_FIRSTFIT):
Header begin at 0x7f82ac153400, size=7152, from 0x7f82ac153410 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
now allocating...
block->size=7152,next=(nil)
new size=6632
next=(nil)
After mem_alloc(500, M_BESTFIT):
Header begin at 0x7f82ac153608, size=6632, from 0x7f82ac153618 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
After free a:
Header begin at 0x7f82ac153000, size=1008, from 0x7f82ac153010 to 0x7f82ac153400, next 0x7f82ac153608.
Header begin at 0x7f82ac153608, size=6632, from 0x7f82ac153618 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
now allocating...
block->size=1008,next=0x7f82ac153608
new size=784
next=0x7f82ac153608
After mem_alloc(200, M_BESTFIT):
Header begin at 0x7f82ac1530e0, size=784, from 0x7f82ac1530f0 to 0x7f82ac153400, next 0x7f82ac153608.
Header begin at 0x7f82ac153608, size=6632, from 0x7f82ac153618 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
now allocating...
block->size=6632,next=(nil)
new size=6408
next=(nil)
After mem_alloc(200, M_WORSTFIT):
Header begin at 0x7f82ac1530e0, size=784, from 0x7f82ac1530f0 to 0x7f82ac153400, next 0x7f82ac1536e8.
Header begin at 0x7f82ac1536e8, size=6408, from 0x7f82ac1536f8 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
After free b:
Header begin at 0x7f82ac1530e0, size=1304, from 0x7f82ac1530f0 to 0x7f82ac153608, next 0x7f82ac1536e8.
Header begin at 0x7f82ac1536e8, size=6408, from 0x7f82ac1536f8 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
After free d:
Header begin at 0x7f82ac1530e0, size=7952, from 0x7f82ac1530f0 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

=================
After free c:
Header begin at 0x7f82ac153000, size=8176, from 0x7f82ac153010 to 0x7f82ac155000, next (nil).
End of MEM_FREE.

编译成库

删掉main()函数，然后在makefile写上：

libmem: mem.c
    gcc -c -fpic mem.c
    gcc -shared -o libmem.so mem.o

1542447950994

幕后

zerol 给出了一个更简洁的写法，当然，这样的代价就是，表头浪费的空间太多了，需要 24 个字节，为此，zerol 辩解称“它页表不是 4096 吗，我才用了 24，但是写起来就很舒服，你那样写，写复杂了”。

以下是部分代码：

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdbool.h>
#include <sys/mman.h>
#include <assert.h>
#include "mem.h"

#define MEM_IN_USE_MAGIC 11235813

char buf[10000000];
typedef struct orzKBlack {
    size_t sz;
    int used;
    struct orzKBlack *pre, *nxt;
} P;
P *head = &buf;
const size_t P_SZ = sizeof(P);
int pgsz;

void try_merge(P* p) {
    if (!p) return;
    if (p->used == MEM_IN_USE_MAGIC) return;
    if (!p->nxt || p->nxt->used == MEM_IN_USE_MAGIC) return;
    p->sz += P_SZ + p->nxt->sz;
    p->nxt = p->nxt->nxt;
}

int mem_free(void* ptr) {
    P* p = ptr - P_SZ;
    if (p->used != MEM_IN_USE_MAGIC) {
        assert(0);
    }
    p->used = -1;
    try_merge(p);
    try_merge(p->pre);
    return 0;
}

void* fix(P* p, size_t sz) {
    p->used = MEM_IN_USE_MAGIC;
    void* res = (void*)p + P_SZ;
    P* pp = res + sz;
    pp->nxt = p->nxt;
    pp->pre = p;
    if (p->nxt) p->nxt->pre = pp;
    p->nxt = pp;
    pp->sz = p->sz - sz - P_SZ;
    p->sz = sz;
    return res;
}

void* mem_alloc(int _sz, int tp) {
    if (_sz <= 0) {
        assert(0);
    }
    size_t sz = _sz;
    sz = ((sz - 1) / pgsz + 1) * pgsz;
    if (tp == M_FIRSTFIT) {
        for (P* u = head; u != NULL; u = u->nxt)
            if (sz <= u->sz + P_SZ) return fix(u, sz);
    }
    assert(0);
}

void mem_dump() {
    puts("-------------");
    for (P* u = head; u != NULL; u = u->nxt) {
        printf("%p %d %lu %p %p\n", u, u->used, u->sz, u->pre, u->nxt);
    }
    puts("-------------");
}

int main() {
    head->sz = 100000 - P_SZ;
    head->pre = head->nxt = NULL;
    head->used = -1;
    pgsz = getpagesize();

    printf("sizeof p: %lu\n", P_SZ);
    printf("pgsz : %d\n", pgsz);

    mem_dump();
    void* hhh = mem_alloc(6000, M_FIRSTFIT);
    mem_dump();
    void* hhhh = mem_alloc(70000, M_FIRSTFIT);
    mem_dump();
    mem_free(hhh);
    mem_dump();
    mem_free(hhhh);
    mem_dump();
}