如何实现一个malloc任何一个用过或学过C的人对malloc都不会陌生。大家都知道malloc可以

文件名称: 如何实现一个malloc

所属分类: C

开发工具:

文件大小: 766kb

下载次数: 0

上传时间: 2019-07-02

提供者: aba****

下载 (766kb)

不能下载？报告错误

详细说明：任何一个用过或学过C的人对malloc都不会陌生。大家都知道malloc可以分配一段连续的内存空间，并且在不再使用时可以通过free释放掉。但是，许多程序员对malloc背后的事情并不熟悉，许多人甚至把malloc当做操作系统所提供的系统调用或C的关键字。实际上，malloc只是C的标准库中提供的一个普通函数，而且实现malloc的基本思想并不复杂，任何一个对C和操作系统有些许了解的程序员都可以很容易理解。用这种技术时,每个进程仿佛自己独享一片2N字节的内存,其中N是机器位数。例如在64位CPU和64位操作系统下,每个进程的虚拟地址空间为 264Byte。这种虚拟地址空间的作用主要是简化程序的编写及方便操作系统对进程间内存的隔离管理,真实中的进程不太可能(也用不到)如此大的内存空间,实际能用到的内存取决于物理内存大小。由于在机器语言层面都是采用虛拟地址,当实际的机器码程序涉及到內存操作时,需要根据当前进程运行的实际上下文将虚拟地址转换为物理內存地址,才能实现对真实内存数据的操作。这个转换一般由一个叫MMU( Memory Management Uni)的硬件完成 2.12页与地址构成在现代操作系统中,不论是虛拟內存还是物理內存,都不是以字节为单位进行管理的,而是以页(Page)为单位。一个内存页是一段固定大小的连续内存地址的总称,具体到 Linux中,典型的内存页大小为4096Byte(4K)。所以内存地址可以分为页号和页内偏移量。下面以64位机器,4G物理内存,4K 页大小为例,虛拟内存地址和物理内存地址的组成如下: 页号(52bit) 偏移(l2bt) 页号(20bi) 偏移(12bit) 上面是虚拟内存地址,下面是物理内存地址。由于页大小都是4K,所以页内便宜都是用低12位表示,而剩下的高地址表示页号。 MMU映射单位并不是字节,而是页,这个映射通过查一个常驻内存的数据结构页表来实现。现在计算机具体的内存地址映射比较复杂,为了加快速度会引入系列缓存和优化,例如工B等机制。下面给出一个经过简化的内存地址翻译示意图,虽然经过了简化,但是基本原理与现代计算机真实的情况的一致的。虚拟页号(52bit) 偏移(12bit) 页表物理页号(20bi) 偏移(12bit) 2.1.3内存页与磁盘页我们知道一般将内存看做磁盘的的缓存,有时MMU在工作时,会发现页表表明某个内存页不在物理内存中,此时会触发一个缺页异常( Page Fault),此时系统会到磁盘中相应的地方将磁盘页载入到内存中,然后重新执行由于缺页而失败的机器指令。关于这部分,因为可以看做对 malloo实现是透明的,所以不再详细讲述,有兴趣的可以参考《深入理解计算机系统》相关章节。最后附上一张在维基百科找到的更加符合真实地址翻译的流程供大家参考,这张图加入了TLB和缺页异常的流程(图片来源页)。 TLB hit virtual address TLB physical address TLB miss TLB writ page table page table page not present page table write disk 2.2 Linux进程级内存管理 22.1内存排布明白了虚拟內存和物理内存的关系及相关的映射机制,下面看一下具体在一个进程内是如何排布内存的。以 Linux64位系统为例。理论上,64bit内存地址可用空间为 0×00000000000 FFFFFFFFFFFFFFFF,这是个相当庞大的空间, Linux实际上只用了其中一小部分(256T)。根据Lnux内核相关文档描述,Linuκ64位操作系统仅使用低47位,高17位做扩展(只能是全0或全1)。所以,实际用到的地址为空间为 0×00000000000000000×00007 FFFFFFFFF和0 XFFFF800000000000~ 0× FFFFFFFFFFFFFFFF,其中前面为用户空间( User Space),后者为内核空间( Kernel Space)。图示如下: 0ⅹ FFFF FF FFFF FF FF FF Kernel space DⅹFFFF80D000a00000 0X00 00 TF FFFFFF FF FF Srack Unused Mapping 0XOO 00 7F FFFF FFFF FF User space 0x00000000000000 ESS Data Code 0X0000000000000000 对用户来说,主要关注的空间是 User Space。将 User Space放大后,可以看到里面主要分为如下几段: code:这是整个用户空间的最低地址部分,存放的是指令(也就是程序所编译成的可执行机器码) pata:这里存放的是初始化过的全局变量 BSS:这里存放的是未初始化的全局变量 Heap:堆,这是我们本文重点关注的地方,堆自低地址向高地址增长,后面要讲到的brk相关的系统调用就是从这里分配内存 Mapping Area:这里是与mmap系统调用相关的区域。大多数实际的mao实现会考虑通过mmap分配较大块的内存区域,本文不讨论这种情况。这个区域自高地址向低地址增长 Stack:这是栈区域,自高地址向低地址增长下面我们主要关注Heap区域的操作。对整个nux内存排布有兴趣的同学可以参考其它资料。 222Heap内存模型一般来说, malloc所申请的内存主要从Heap区域分配(本文不考虑通过mmap 申请大块内存的情况)。由上文知道,进程所面对的虚拟内存地址空间,只有按页映射到物理内存地址, 才能真正使用。受物理存储容量限制,整个堆虚拟內存空间不可能全部映射到实际的物理内存。 Linux对堆的管理示意如下 Mapped Region Unmapped Region且 The Heap Linux维护一个 break指针,这个指针指向堆空间的某个地址。从堆起始地址到 break之间的地址空间为映射好的,可以供进程访问;而从 break往上,是未映射的地址空间,如果访问这段空间则程序会报错。 22.3bk与sbrk 由上文知道,要增加一个进程实际的可用堆大小,就需要将 break指针向高地址移动。 Linux通过bk和sbk系统调用操作 break指针。两个系统调用的原型如 1. int brk( void addr) 2. void*sbrk (intptr t increment brk将 break指针直接设置为某个地址,而sbrk将 break从当前位置移动 increment 所指定的增量。brk在执行成功时返回0,否则返回-1并设置erno为 ENOMEM sbk成功时返回 break移动之前所指向的地址,否则返回(oid*)-1。一个小技巧是,如果将 increment.设置为0,则可以获得当前 break的地址另外需要注意的是,由于 Linux是按页迸行內存映射的,所以如果 break被设置为没有按页大小对齐,则系统实际上会在最后映射一个完整的页,从而实际已映射的内存空间比 break指向的地方要大一些。但是使用 break之后的地址是很危险的 (尽管也许 break之后确实有一小块可用内存地址) 22.4资源限制与 rlimit 系统对每一个进程所分配的资源不是无限的,包括可映射的内存空间,因此每个进程有一个m表示当前进程可用的资源上限。这个限制可以通过getm系统调用得到,下面代码获取当前进程虚拟内存空间的 rlimit: 1. int main(i 2. struct rlimit *limit =(struct rlimit")malloc(sizeof(struct rlimit)) 3. getrlimit(RLIMIT AS, limit) 4. printf("soft limit: %ld, hard limit: %ld\n", limit->rlim cur, limit->rlim max) 其中rm是一个结构体 1. struct rlimit 2. rlim t rlim cur:/ Soft limit "/ 3. rlim t rlim max; Hard limit(ceiling for rlim cur)* 4. 每种资源有软限制和硬限制,并且可以通过 setrlimit对rim进行有条件设置。其中硬限制作为软限制的上限,非特权进程只能设置软限制,且不能超过硬限制。 3实现 malloc 3.1玩具实现在正式开始讨论maoc的实现前,我们可以利用上述知识实现一个简单但几乎没法用于真实的玩具 malloc,权当对上面知识的复习: 1./一个玩具maoc 2. #include 3.并 include< unistd.h> 4. void*malloc(size t size) 5.{ 6. void"p 7. p= sbrk(0) 8. if(sbrk(size)==(void* )-1) 9. return NULL. 10. return p, 这个 malloc每次都在当前breαk的基础上增加size所指定的字节数,并将之前 break的地址返回。这个maoc由于对所分配的内存缺乏记录,不便于内存释放,所以无法用于真实场景。 32正式实现下面严肃点讨论malc的实现方案 32.1数据结构首先我们要确定所采用的数据结构。一个简单可行方案是将堆内存空间以块 (Bock)的形式组织起来,每个块由meta区和数据区组成,meta区记录数据块的元信息(数据区大小、空闲标志位、指针等等),数据区是真实分配的内存区域,并且数据区的第一个字节地址即为malc返回的地址可以用如下结构体定义一个bock: 1. typedef struct s block*t block 2. struct s block i 3. size t size;/数据区大小 4. t block next;/指向下个块的苔针 5. int free;/是否是空內块 6. int padding;境充4字芳,保证met块长度为8的数 7. char datal1/这是—个虚字段,表示数据块的第一个字艺,长度不应计入meta 8 由于我们只考虑64位机器,为了方便,我们在结构体最后填充一个int,使得结构体本身的长度为8的倍数,以便内存对齐。示意图如下 next next data data da 日 pointer ointer pointer 322寻找合适的bock 现在考虑如何在 block链中查找合适的bock。一般来说有两种查找算法: First fit:从头开始,使用第一个数据区大小大于要求size的块所谓此次分配的块 Best fit:从头开始,遍历所有块,使用数据区大小大于size且差值最小的块作为此次分配的块两种方法各有千秋, best fi!有较高的内存使用率( payload较高),而 first fit 具有更好的运行效率。这里我们采用 first fi算法。 1./ First fit x/ 2.t block find_block(t block last, size_t size)t 3.t block b= first block 4. while(b &&!(b->free && b->size > size))i 5. last b: 6. b=b->next 7. 8. return b 9.} find block从fit_ block开始,查找第—个符合要求的bock并返回 block起始地址,如果找不到这返回NULL。这里在遍历时会更新一个叫ast的指针,这个指针始终指向当前遍历的bock。这是为了如果找不到合适的bock而开辟新 block使用的,具体会在接下来的一节用到。 323开辟新的bock 如果现有 block都不能满足size的要求,则需要在链表最后开辟一个新的blocκ 这里关键是如何只使用sbk创建一个 struct: 1.# define block size24/B子存在虚纵的at字,sieo不能正确计算meta 长度,这里天工设置 3. t block extend heap(t block last, size t st 4. t block b 5. b= sbrk(0 6. if(sbrk(BLOCK SIZE s)==(void *)-1) 7. return null. 8. b->size= s 9. b->next= NULL. 10. if(last) 11. last->next b 12.b->fee=0; 13. return b: 14.} 324分裂 block First fit一个比较致命的缺点,就是可能会让很小的sze占据很大的一块 block,此时,为了提高 payload,应该在剩余数据区足够大的情况下,将其分裂为一个新的 block,示意如下 next requested size unused space 2日 next next requested size 日已 free=l 实现代码 1. void split block(t block b, size t si 2. t block new: 3. new=b->data +s: 4. new->size b->size -- BLOCK SIZE 5. new->next= b->next 6. new->free 1 7. b->size =s 8. b->next= new 325 malloc的实现有了上面的代码,我们可以利用它们整合成一个简单但初步可用的maoc。注意首先我们要定义个bock链表的头 first block,初始化为NULL;另外,我们需要剩余空间至少有 BLOCK SIZE+8才执行分裂操作。由于我们希望malo分配的数据区是按8字节对齐,所以在size不为8的倍数时, 我们需要将size调整为大于size的最小的8的倍数: 1. size t align(size tsi

(系统自动生成,下载前可以参看下载内容)