malloc底层原理实现

使用过c语言的都知道malloc是一个动态分配内存的函数，还可以通过free释放内存空间。 如果我们想分析一下malloc的源码，这其实不是一会就能看懂的，但是我们可以讨论一下malloc的简单实现。 在这之前，我们先来看一下虚拟内存空间。 虚拟内存空间时操作系统实现内存管理的一种机制。操作系统为每个进程维护一个虚拟内存空间。操作系统会将虚拟内存和实际的物理内存进行映射，CPU芯片上叫做存储器管理单元(Memory Management Unit，MMU)的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容是由操作系统管理。虚拟内存使得用户感觉内存空间时连续的，同时给进程提供独占内存的假象。 我们可以看到虚拟内存空间的顶部是内核管理的内存空间，下面则是用户的内存空间，用户空间无权访问内核的内存空间。 我们可以看到一个区域，运行时堆。我们可以看到运行时堆上面还有一块黑色部分，这就是还未映射的内存。 在已经映射的内存空间结尾有一个break指针，这个指针下面是映射好的内存，可以访问，上面则是未映射的访问，不能访问。可以通过系统调用sbrk(位移量)能一定brk指针的位置，同时返回brk指针的位置，达到申请内存的目。brk(void *addr)系统调用可以直接将brk设置为某个地址，成功返回0，不成功返回-1。而rlimit则是限制进程堆内存容量的指针。 在操作系统角度来看，分配内存有两种方式，一种是采用推进brk指针来增加堆的有效区域来申请内存空间，还有一种是采用mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。这两种方式都是分配虚拟内存，只有当第一次访问虚拟地址空间时，操作系统给分配物理内存空间。 malloc是采用brk的方式来动态分配内存。 那么来谈一下空间内配的实现问题。 其中一种是隐式链表，实际上是数组，malloc分配空间必然有一个数据结构，允许它来区分边界，区分已分配和空间的空间，数据结构中包含一个头部信息和有效载荷，有效载荷的首地址就是malloc返回的地址，可能在尾部还有填充，为了保持内存对齐。头部相当于该数据结构的元数据，其中包含了块大小和是否是空闲空间的信息，这样可以根据头地址和块大小的地址推出下一个内存块的地址，这就是隐式链表。

malloc基本的实现原理就是维护一个内存空闲链表，当申请内存空间时，搜索内存空闲链表，找到适配的空闲内存空间，然后将空间分割成两个内存块，一个变成分配块，一个变成新的空闲块。如果没有搜索到，那么就会用sbrk()才推进brk指针来申请内存空间。 搜索空闲块最常见的算法有：首次适配，下一次适配，最佳适配。 首次适配：第一次找到足够大的内存块就分配，这种方法会产生很多的内存碎片。 下一次适配：也就是说等第二次找到足够大的内存块就分配，这样会产生比较少的内存碎片。 最佳适配：对堆进行彻底的搜索，从头开始，遍历所有块，使用数据区大小大于size且差值最小的块作为此次分配的块。

在释放内存块后，如果不进行合并，那么相邻的空闲内存块还是相当于两个内存块，会形成一种假碎片。所以当释放内存后，我们需要将两个相邻的内存块进行合并。

还有一种实现方式则是采用显示空闲链表，这个是真正的链表形式。在之前的有效载荷中加入了之前前驱和后驱的指针，也可以称为双向链表。维护空闲链表的的方式第一种是用后进先出（LIFO），将新释放的块放置在链表的开始处。另一种方法是按照地址的顺序来维护。