0%

malloc

简述malloc实现原理

malloc可以分别由伙伴系统或基于链表的实现;

  • 它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表;
  • 调用malloc函数时,它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后,将该内存块一分为二(一块的大小与用户请求的大小相等,另一块的大小就是剩下的字节)。接下来,将分配给用户的那块内存传给用户,并将剩下的那块(如果有的话)返回到连接表上。
  • 调用free函数时,它将用户释放的内存块连接到空闲链上。到最后,空闲链会被切成很多的小内存片段,如果这时用户申请一个大的内存片段,那么空闲链上可能没有可以满足用户要求的片段了。于是,malloc函数请求延时,并开始在空闲链上翻箱倒柜地检查各内存片段,对它们进行整理,将相邻的小空闲块合并成较大的内存块。

详述

malloc是C语言最常用的标准库函数之一,用于在程序运行中动态地申请内存空间。我们都会使用它,其函数原型为:

1
extern void *malloc(unsigned int num_bytes);

那么它是怎么实现的呢?不同的编译环境中对它的实现可能不同。比如glibc(The GNU C Library)就有自己对malloc库函数的实现方法,并且是开源的。如果让我们自己实现malloc功能的函数,该怎么写?下面学习一下malloc实现的原理。

首先,我们需要知道,操作系统内核是怎么把一段内存分配给进程的?这当然需要系统调用了。用户态申请分配内容的系统调用是sbrk(n),参数n是期望得到的内存字节数。但是,频繁的调用sbrk进行分配会使得真实内存出现越来越多的零碎空间。Linux操作系统的基本分配方式是伙伴分配方式,所以即使申请的字节数不是2的幂数,系统也会分配出2的幂数的空间来。因此malloc的实现不会是每次都动用内核的。

malloc采用的总体策略是:

先系统调用sbrk一次,会得到一段较大的并且是连续的空间。进程把系统内核分配给自己的这段空间留着慢慢用。之后调用malloc时就从这段空间中分配,free回收时就再还回来(而不是还给系统内核)。只有当这段空间全部被分配掉时还不够用时,才再次系统调用sbrk。当然,这一次调用sbrk后内核分配给进程的空间和刚才的那块空间一般不会是相邻的。

malloc如何使用得到动态内存空间?一次sbrk之后,malloc就会保留着一段大的连续空间(称作堆空间)。之后对于堆空间malloc不断地分配,free不断地收回,这段空间里的格局必定是“乱七八糟”,有的已分配,有的未分配。

实现动态内存分配往往要考虑以下四个问题:

  • 空闲块组织:我们如何记录空闲块?
  • 选择:我们如何选择一个合适的空闲块来作为一个新分配的块?
  • 分割:在我们选了一个空闲块分配出我们需要的大小之后,我们如何处理这个空闲块中的剩余部分?
  • 合并:我们如何处理一个刚刚被释放的块?

malloc的空闲链表机制:这是对问题(1)的解答。有两种方法:

  • 显式空闲链表
  • 隐式空闲链表。

空闲链表

  • 显式空闲链表:用一个链表将可用的内存块连接为一个长长的列表,称为空闲链表。将堆组织成双向空闲链表,每一个空闲块结点都包含一个祖先指针和一个后继指针。链表中的每个结点记录一个连续的、未分配的内存小块。结点的结构很简单,只需要记录可用内存小块的首地址和大小即可。

  • 隐式空闲链表:隐式空闲链表由N个块组成,一个块由头部、有效载荷(只包括已分配的块),以及可能的一些额外的填充(为了保证内存字节对齐而需要的填充)和尾部组成。头部大小为4个字节,在强加双字对齐的约束之后,块大小总是8的倍数,所以用高29位来表示存储块大小,剩余3位中利用最低位来表示块是否已分配(1表示已分配,0表示空闲);尾部和头部的内容一样,加入尾部是为了分配器可以判断出一个块的起始位置和状态。整个堆空间就是一个隐式空闲链表,从低地址向高地址生长,第一个和最后一个8字节标记为已分配,以确定堆的大小。

空闲链表如何从中选择分配内存块?

这是对问题(2)的解答。有下面四种选择方法。

  • 首次适应法(First Fit):链表按块地址排序。选择第一个满足要求的空闲块。特点:低地址碎片多,高地址碎片少。
  • 最佳适应法(Best Fit):链表按空闲块大小排序。选择满足要求的,且大小最小的空闲块。特点:费时间,并且会出现很小的碎片。
  • 最坏适应法(Worst Fit):链表按空闲块大小排序。选择最大的空闲块。特点:碎片少,容易缺乏大块。
  • 循环首次适应法(Next Fit):链表按块地址排序。从上次分配位置开始找到第一个满足要求的空闲块。特点:碎片分布的又多又均匀。

如何处理被选空闲块中的剩余部分?

这是对问题(3)的解答。一般来讲,是要把剩余的部分再插入回到空闲链表中去的。要注意一个空闲块分割成两个块时,需要腾出若干字节作为块的头部尾部等部分。

如何合并被释放的块?

这是对问题(4)的解答。有两种方法:立即合并、推迟合并。对于隐式空闲链表,合并的具体过程是,

  • 前后块都已分配:直接释放当前块即可;

  • 前块分配、后块空闲:和后块合并;

  • 前块空闲、后块分配:和前块合并;

  • 前后块都已空闲:和前后块合并;

glibc对malloc的实现

目前最新版本为2.18,glibc源码目录/glibc-2.18/malloc中可以看到。在glibc的malloc的实现中, 分配虚存有两种系统调用可用: brk()和mmap(), 如果要分配大块内存, glibc会使用mmap()去分配内存,这种内存靠近栈。

基于UNIX 的系统有两个可映射到附加内存中的基本系统调用:
brk: brk() 是一个非常简单的系统调用。还记得系统中断点吗?该位置是进程映射的内存边界。 brk()只是简单地将这个位置向前或者向后移动,就可以向进程添加内存或者从进程取走内存。sbrk()是以增量的方式增加扩大内存。

mmap: mmap(),或者说是“内存映像”,类似于 brk(),但是更为灵活。首先,它可以映射任何位置的内存,而不单单只局限于进程。其次,它不仅可以将虚拟地址映射到物理的 RAM 或者 swap,它还可以将它们映射到文件和文件位置,这样,读写内存将对文件中的数据进行读写。不过在这里,我们只关心 mmap向进程添加被映射的内存的能力。

在glibc的malloc的实现有一个优化:

  1. 当malloc()一块很小的内存是, glibc调用brk(), 只需要在heap中移动一下指针, 即可获得可用虚存, 这样分配得到的地址较小.
  2. 当malloc()一块较大内存时, glibc调用mmap(), 需要在内核中重新分配vma结构等, 他会在靠近栈的地方分配虚存, 这样返回的地址大.

Reference