如何通过mmap正确处理内存管理？

Question

我正在尝试编写自己的malloc和free实现为了学习,只是mmap和munmap(从而brk和sbrk过时).我已经阅读了大量关于这个主题的文档,但是我看到的每个例子都使用sbrk或者不能很好地解释如何处理大区域的映射内存.

我想写的是这样的想法:我首先绘制一个大区域(即512页); 此区域将包含1到992字节之间的所有分配,以16字节为增量.稍后我将使用4096页区域进行更大的分配(如果请求的大小大于页面,则直接使用mmap).所以我需要一种方法来存储关于我分配或免费的每个块的信息.

我的问题是,我该如何正确处理这些信息？

我的问题是:如果我创建链表,如何为每个节点分配更多空间？或者我需要将其复制到映射区域吗？如果是这样,我如何在数据空间和预留空间之间徘徊？或者使用静态大小的数组更好？问题是我的区域大小取决于页面大小.

Answer 1

基于mmap的malloc有几种可能的实现方式:

顺序(首次拟合,最佳拟合).

想法:使用链接列表,其中最后一个块的大小与页面的剩余大小相同.

struct chunk
{
   size_t size;
   struct chunk *next;
   int is_free;
}

分配
1. 迭代你的列表以获得合适的免费块(可优化)
2. 如果找不到任何内容,请将最后一个块调整大小为所需大小,并为剩余大小创建一个空闲块.
3. 如果你到达页面的末尾,(size太小,并且next是NULL),只需mmap一个新页面(可优化:如果大小异常,则生成一个自定义页面......)
要自由,甚至更简单:只需设置is_free为1.可选地,您可以检查下一个块是否也是空闲的,并在更大的空闲块中合并(注意页面边框).

优点:易于实施,易于理解,易于调整.

缺点:效率不高(迭代你的整个列表来找到一个块？),需要大量的优化,繁忙的内存组织

二元伙伴(我喜欢二元算术和递归)

想法:使用2的幂作为大小单位:

struct chunk
{
   size_t size;
   int is_free;
}

这里的结构不需要next,你会看到.

原则如下:

执行:

分配一块大小 Size
1. 获得所需 Block_size = 2^k > size + sizeof(chunk)
2. 找到适合的树中最小的可用空间 block_size
3. 如果它可以变小,递归拆分它.
解冻一块
1. 设置is_free为1
2. 检查你的好友是否有空(XOR大小,不要忘记确认他和你一样大小)
3. 如果他是,他的大小加倍.递归.

优点:速度极快,内存高效,干净.

缺点:复杂,一些棘手的案例(页面边框和伙伴大小)需要保留您的页面列表

铲斗(我有很多时间可以输)

这是我没有尝试过的三个方法中唯一的方法,所以我只能谈论这个理论:

struct bucket
{
  size_t buck_num;  //number of data segment
  size_t buck_size; //size of a data segment
  void *page;
  void *freeinfo;
}

例如,对于4096字节页面中的512字节存储桶,表示它的位集将是8位位集,假设*freeinfo = 01001000这意味着第二和第五个存储桶是空闲的.

优点:从长远来看,迄今为止最快,最干净,在许多小额分配中效率最高

缺点:实现起来非常麻烦,对于小程序而言非常繁重,需要为位集提供单独的内存空间.

可能还有其他算法和实现,但这三个是最常用的,所以我希望你可以从中获得你想要做的事情.