[历史归档]本文原发布于 cstriker1407.info 个人博客内容为历史存档仅供参考。发布时间2015-02-08 标题【转】如何实现一个malloc分类操作系统 / linux 标签linux·malloc【转】如何实现一个malloc1 什么是malloc2 预备知识2.1 Linux内存管理2.1.1 虚拟内存地址与物理内存地址2.1.2 页与地址构成2.1.3 内存页与磁盘页2.2 Linux进程级内存管理2.2.1 内存排布2.2.2 Heap内存模型2.2.3 brk与sbrk2.2.4 资源限制与rlimit本文转自【 blog.codinglabs.org/articles/a-malloc-tutorial.html 】有删改。任何一个用过或学过C的人对malloc都不会陌生。大家都知道malloc可以分配一段连续的内存空间并且在不再使用时可以通过free释放掉。但是许多程序员对malloc背后的事情并不熟悉许多人甚至把malloc当做操作系统所提供的系统调用或C的关键字。实际上malloc只是C的标准库中提供的一个普通函数而且实现malloc的基本思想并不复杂任何一个对C和操作系统有些许了解的程序员都可以很容易理解。这篇文章通过实现一个简单的malloc来描述malloc背后的机制。当然与现有C的标准库实现例如glibc相比我们实现的malloc并不是特别高效但是这个实现比目前真实的malloc实现要简单很多因此易于理解。重要的是这个实现和真实实现在基本原理上是一致的。这篇文章将首先介绍一些所需的基本知识如操作系统对进程的内存管理以及相关的系统调用然后逐步实现一个简单的malloc。为了简单起见这篇文章将只考虑x86_64体系结构操作系统为Linux。1 什么是malloc在实现malloc之前先要相对正式地对malloc做一个定义。根据标准C库函数的定义malloc具有如下原型void*malloc(size_tsize);这个函数要实现的功能是在系统中分配一段连续的可用的内存具体有如下要求malloc分配的内存大小至少为size参数所指定的字节数malloc的返回值是一个指针指向一段可用内存的起始地址多次调用malloc所分配的地址不能有重叠部分除非某次malloc所分配的地址被释放掉malloc应该尽快完成内存分配并返回不能使用NP-hard的内存分配算法实现malloc时应同时实现内存大小调整和内存释放函数即realloc和free对于malloc更多的说明可以在命令行中键入以下命令查看man malloc2 预备知识在实现malloc之前需要先解释一些Linux系统内存相关的知识。2.1 Linux内存管理2.1.1 虚拟内存地址与物理内存地址为了简单现代操作系统在处理内存地址时普遍采用虚拟内存地址技术。即在汇编程序或机器语言层面当涉及内存地址时都是使用虚拟内存地址。采用这种技术时每个进程仿佛自己独享一片2N字节的内存其中N是机器位数。例如在64位CPU和64位操作系统下每个进程的虚拟地址空间为264Byte。这种虚拟地址空间的作用主要是简化程序的编写及方便操作系统对进程间内存的隔离管理真实中的进程不太可能也用不到如此大的内存空间实际能用到的内存取决于物理内存大小。由于在机器语言层面都是采用虚拟地址当实际的机器码程序涉及到内存操作时需要根据当前进程运行的实际上下文将虚拟地址转换为物理内存地址才能实现对真实内存数据的操作。这个转换一般由一个叫MMUMemory Management Unit的硬件完成。2.1.2 页与地址构成在现代操作系统中不论是虚拟内存还是物理内存都不是以字节为单位进行管理的而是以页Page为单位。一个内存页是一段固定大小的连续内存地址的总称具体到Linux中典型的内存页大小为4096Byte4K。所以内存地址可以分为页号和页内偏移量。下面以64位机器4G物理内存4K页大小为例虚拟内存地址和物理内存地址的组成如下上面是虚拟内存地址下面是物理内存地址。由于页大小都是4K所以页内便宜都是用低12位表示而剩下的高地址表示页号。MMU映射单位并不是字节而是页这个映射通过查一个常驻内存的数据结构页表来实现。现在计算机具体的内存地址映射比较复杂为了加快速度会引入一系列缓存和优化例如TLB等机制。下面给出一个经过简化的内存地址翻译示意图虽然经过了简化但是基本原理与现代计算机真实的情况的一致的。2.1.3 内存页与磁盘页我们知道一般将内存看做磁盘的的缓存有时MMU在工作时会发现页表表明某个内存页不在物理内存中此时会触发一个缺页异常Page Fault此时系统会到磁盘中相应的地方将磁盘页载入到内存中然后重新执行由于缺页而失败的机器指令。关于这部分因为可以看做对malloc实现是透明的所以不再详细讲述有兴趣的可以参考《深入理解计算机系统》相关章节。最后附上一张在维基百科找到的更加符合真实地址翻译的流程供大家参考这张图加入了TLB和缺页异常的流程图片来源页。2.2 Linux进程级内存管理2.2.1 内存排布明白了虚拟内存和物理内存的关系及相关的映射机制下面看一下具体在一个进程内是如何排布内存的。以Linux 64位系统为例。理论上64bit内存地址可用空间为0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF这是个相当庞大的空间Linux实际上只用了其中一小部分256T。根据Linux内核相关文档描述Linux64位操作系统仅使用低47位高17位做扩展只能是全0或全1。所以实际用到的地址为空间为0x0000000000000000 ~ 0x00007FFFFFFFFFFF和0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF其中前面为用户空间User Space后者为内核空间Kernel Space。图示如下对用户来说主要关注的空间是User Space。将User Space放大后可以看到里面主要分为如下几段Code这是整个用户空间的最低地址部分存放的是指令也就是程序所编译成的可执行机器码Data这里存放的是初始化过的全局变量BSS这里存放的是未初始化的全局变量Heap堆这是我们本文重点关注的地方堆自低地址向高地址增长后面要讲到的brk相关的系统调用就是从这里分配内存Mapping Area这里是与mmap系统调用相关的区域。大多数实际的malloc实现会考虑通过mmap分配较大块的内存区域本文不讨论这种情况。这个区域自高地址向低地址增长Stack这是栈区域自高地址向低地址增长下面我们主要关注Heap区域的操作。对整个Linux内存排布有兴趣的同学可以参考其它资料。2.2.2 Heap内存模型一般来说malloc所申请的内存主要从Heap区域分配本文不考虑通过mmap申请大块内存的情况。由上文知道进程所面对的虚拟内存地址空间只有按页映射到物理内存地址才能真正使用。受物理存储容量限制整个堆虚拟内存空间不可能全部映射到实际的物理内存。Linux对堆的管理示意如下Linux维护一个break指针这个指针指向堆空间的某个地址。从堆起始地址到break之间的地址空间为映射好的可以供进程访问而从break往上是未映射的地址空间如果访问这段空间则程序会报错。2.2.3 brk与sbrk由上文知道要增加一个进程实际的可用堆大小就需要将break指针向高地址移动。Linux通过brk和sbrk系统调用操作break指针。两个系统调用的原型如下intbrk(void*addr);void*sbrk(intptr_tincrement);brk将break指针直接设置为某个地址而sbrk将break从当前位置移动increment所指定的增量。brk在执行成功时返回0否则返回-1并设置errno为ENOMEMsbrk成功时返回break移动之前所指向的地址否则返回(void *)-1。一个小技巧是如果将increment设置为0则可以获得当前break的地址。另外需要注意的是由于Linux是按页进行内存映射的所以如果break被设置为没有按页大小对齐则系统实际上会在最后映射一个完整的页从而实际已映射的内存空间比break指向的地方要大一些。但是使用break之后的地址是很危险的尽管也许break之后确实有一小块可用内存地址。2.2.4 资源限制与rlimit系统对每一个进程所分配的资源不是无限的包括可映射的内存空间因此每个进程有一个rlimit表示当前进程可用的资源上限。这个限制可以通过getrlimit系统调用得到下面代码获取当前进程虚拟内存空间的rlimitintmain(){structrlimit*limit(structrlimit*)malloc(sizeof(structrlimit));getrlimit(RLIMIT_AS,limit);printf(soft limit:%ld,hard limit:%ld ,limit-rlim_cur,limit-rlim_max);}其中rlimit是一个结构体structrlimit{rlim_trlim_cur;/* Soft limit */rlim_trlim_max;/* Hard limit (ceiling for rlim_cur) */};每种资源有软限制和硬限制并且可以通过setrlimit对rlimit进行有条件设置。其中硬限制作为软限制的上限非特权进程只能设置软限制且不能超过硬限制。