malloc的实现原理_malloc函数实现

malloc申请内存的原理 　　对于程序申请的内存来说，一般都是虚拟内存，操作系统只需要负责给其分配足够的虚拟空间就好了，让程序以为自己具有这些内存空间，而实际意义上的物理内存，是等到非用不可的时候，才会使用的。

application申请内存时候的宏观图 　　1、物理内存相关 　　1.1 内存的表示与组织 　　有关究竟内存是采用分段还是分页的讨论，在第五章CPU工作模式中已经讨论过了。 　　简而言之，内存采取分段的方式，一是不利于对内存状态进行表示，二是分段会产生较大的内存碎片，三是内存与硬盘的交换效率较低。 　　我们之后对内存相关的代码和研究都是基于4KB分页的内存模型(CPU长模式下，64位)。 　　1.2 内存页的表示 　　逻辑上内存结构如下：

　　不过要注意，真实的地址空间是有空洞的，不是连续的，在第五章已经通过INT 15H中断了计算机的内存视图（e820map_t 结构数组已转换到phymmarge_t 结构数组），其中内存每一页都是4K对齐的，现在考虑第一个问题——如何表示一个内存页？ 　　如果用类似位图的方式来表示一个内存页已经被使用或者未被使用，比如标为1表示未被使用，为0表示已被使用。那么后续有关内存的分配算法等只能够采用最简单的遍历方式，但是效率却并不符合实际使用。 　　在实际的内存管理方式设计中，一个内存页的表示不仅要考虑它的状态（是否被分配），还要考虑到页的地址、分配次数、页的类型等，以结构的方式表示如下： 　　注意到上述masdsc_t结构占用的内存很小，这是因为每一个内存页就有一个这样的结构，它必须得小。另外，在物理地址和标志中，低12位被用作它用，这是由于内存页4K对齐。 　　1.3 内存分区 　　为了便于对内存的管理，以及不同内存区域功能的区分，我们通常会在逻辑上对内存进行分区，如下：

　　其中，硬件区位于低32MB空间，这个地址空间是给硬件使用的，它主要是提供给一些能够直接和内存交换数据的硬件，这些硬件不通过MMU进行虚拟地址到物理地址的转换，而是直接与物理地址打交道。 　　比较常见的是就是DMA访问内存，它只能访问低于24MB的物理内存，还有一些其他硬件也是如此，那么我们在分配内存的时候，就不应该将一部分低位内存分配出去。 　　之后的内存区，主要是考虑到内核也是运行在虚拟地址空间，将内核所使用的地址空间与物理地址空间一一对应，可以提高内存的运行效率。另外，有时需要在内核中分配连续、大块的内存，比如内核栈、显卡驱动等。总之，给内核单独分配一块区域具有很大的作用。 　　应用区，就是留给用户态程序所使用的内存区域了，这部分内存根据应用程序的需要，按需分配，如果访问到一个还没有与物理地址建立映射关系的虚拟地址时，会产生缺页异常，操作系统响应这个异常为其分配对应的物理内存页，从而达到“按需分配”。 　　那么如何表示一个内存区呢？其实无外乎内存页的状态，内存区的开始与结束物理地址等属性，用一个结构体来表示： 　　这些标志现在不会讲，继续往后看就懂了，现在只需要了解有这些属性就够了。 　　现在思考一个问题——如何将内存区域内存页相关联起来？ 　　1.4 组织内存页 　　由于内存页是用msadsc_t结构体来表示的，组织内存页，即是找到一个合理、高效地方式来组织msadsc_t结构体。 　　注意到msadsc_t结构体中有链表，那么用链表串起来？——遍历链表跟遍历位图没有多大区别。 　　在讲解代码的时候，先以一副图来表示如何在内存区memarea_t中组织内存页msadsc_t：

　　我们在内存区中新建一个新的结构体——memdivmer_t，意指内存的分割与合并，分割即是将内存分配出去，合并即是内存被释放之后的回收。 　　memdivmer_t结构体中有一个dm_mdmlielst指针指向bafhlst_t结构体数组。 　　而bafhlst_t链表将内存页msadsc_t用链表串联起来，并且每一个bafhlst_链表所拥有的内存页msadsc_t数量是不一样的，分别是0,2,4,6，……2^(n-1)，其中n是该bafhlst结构体在dm_mdmlielst数组中的下标！ 为什么要用这样的方式来组织内存页呢？需要注意的是，对于每一个bafhlst_t链表中的msadsc_t我们并不在意其中第一个 msadsc_t 结构对应的内存物理地址从哪里开始，但是第一个 msadsc_t 结构与最后一个 msadsc_t 结构，它们之间的内存物理地址是连续的。 　　举个例子，对于dm_mdmlielst数组第0个bafhlst，它挂载一个msadsc_t结构体，其内存地址可以是0x4000~0x5FFF； 　　对于dm_mdmlielst数组第1个bafhlst，它挂载2个msadsc_t结构体，其内存地址可以是0x~0x102FFF, 0x~0x104FFF，即是0x~0x4FFF的连续区域； 　　…… 　　对于dm_mdmlielst数组第n个bafhlst，它挂载2^(n-1)个msadsc_t结构体，其内存地址也是一段连续区域；通过这种方式，我们可以对内存中较大/较小的连续区域分别进行组织，减小了内存碎片出现的可能。其中上述两个结构体的实现代码分别如下： 　　2、内存的初始化 　　其实在内核启动最开始的阶段，我们需要先进行内存初始化才能够为后续的工作进行内存的分配和释放，虽然我们建立了内存页和内存区相关的结构体，但是还远远不够。 　　因为我们还没有在内存中建立对应的实例变量。我们都知道，在代码中实际操作的数据结构必须在内存中有相应的变量，而所谓对内存的初始化就是建立相应的数据结构对应的实例。 　　内存的初始化主要有以下几个部分： 　　3、内存的分配与释放 　　3.1 内存分配 　　也许你会想象内存分配是这么进行的：在一段循环代码中，遍历所有的内存页，而后将一个空闲的内存页返回即可。 　　但是现实是，内存管理器需要为内核、驱动、应用程序提供复杂的内存服务——需要多少内存页？内存页需不需要连续？物理地址是否有要求？ 　　由于这些现实问题的存在，关于内存的分配和释放不能采取上述简单遍历的方式。 　　有关这部分的代码详见代码仓库，下面是我梳理出的一个函数调用逻辑图：

　　其实整个内存分配阶段最重要的部分就是如何从dm_mdmlielst数组中找到合适的bafhlst_t结构体，因为如果找到的bafhlst_t结构体中内存页msadsc_t过大，就会产生内存碎片，不利于下次内存的分配；如果找到的bafhlst_t结构体中内存页msadsc_t过小，就需要多个bafhlst_t结构体组合完成这次分配，效率又不高。 　　这部分的逻辑在两个函数里，一个是对dm_mdmlielst数组中根据下标遍历找到合适的bafhlst_t： 　　二是，处理到的bafhlst_t结构体，根据实际需要的内存大小，有可能需要对其进行拆分，将其剩下的部分挂载其他的bafhlst_t上： 　　比如现在我们需要分配一个页面，这个算法将执行如下步骤： 　　1. 根据一个页面的请求，会返回 m_mdmlielst 数组中的第 0 个 bafhlst_t 结构（第0个bafhlst_t结构中挂载了一个内存页）。 　　2. 如果第 0 个 bafhlst_t 结构中有 msadsc_t 结构就直接返回，若没有 msadsc_t 结构（即这个bafhlst_t中的msadsc_t结构已经被用完了），就会继续查找 m_mdmlielst 数组中的第 1 个 bafhlst_t 结构。 　　3. 如果第 1 个 bafhlst_t 结构中也没有 msadsc_t 结构，就会继续查找 m_mdmlielst 数组中的第 2 个 bafhlst_t 结构。 　　4. 如果第 2 个 bafhlst_t 结构中有 msadsc_t 结构，记住第 2 个 bafhlst_t 结构中对应是 4 个连续的 msadsc_t 结构。这时让这 4 个连续的 msadsc_t 结构从第 2 个 bafhlst_t 结构中脱离。 　　5. 把这 4 个连续的 msadsc_t 结构，对半分割成 2 个双 msadsc_t 结构，把其中一个双 msadsc_t 结构挂载到第 1 个 bafhlst_t 结构中。 　　6. 把剩下一个双 msadsc_t 结构，继续对半分割成两个单 msadsc_t 结构，把其中一个单 msadsc_t 结构挂载到第 0 个 bafhlst_t 结构中，剩下一个单 msadsc_t 结构返回给请求者，完成内存分配。 　　整个过程如下图所示：

　　结合上面的代码、过程解释、流程图，现在我们对内存分配的具体过程有了较为详细的理解：如果当前下标的bafhlst_t中的msadsc结构不够，那就继续往后查，如果用不完当前bafhlst结构体中的msadsc还有剩余，就挂载到其之前的bafhlst_t结构体中。 　　3.2 内存释放 　　内存的释放过程，其实是内存分配的逆过程。因为代码量太多，这里同样不放出具体的代码，详情可见cosmos/hal/x86/memdivmer.c，我梳理出的函数调用逻辑如下：

　　而在这个调用逻辑中，重点则是理解最后一个函数——如何将释放的内存页放到合适的bafhlst_t上呢？ 　　先来看看代码： 　　比如，现在我们要释放一个页面，这个算法将执行如下步骤。 　　（1）释放一个页面，会返回 m_mdmlielst 数组中的第 0 个 bafhlst_t 结构。 　　（2）设置这个页面对应的 msadsc_t 结构的相关信息，表示已经执行了释放操作。 　　（3）开始查看第 0 个 bafhlst_t 结构中有没有空闲的 msadsc_t，并且它和要释放的 msadsc_t 对应的物理地址是连续的。没有则把这个释放的 msadsc_t 挂载第 0 个 bafhlst_t 结构中，算法结束，否则进入下一步（即有空闲的msadsc并且地址连续）。 　　（4）把第 0 个 bafhlst_t 结构中的 msadsc_t 结构拿出来与释放的 msadsc_t 结构，合并成 2 个连续且更大的 msadsc_t。 　　（5）继续查看第 1 个 bafhlst_t 结构中有没有空闲的 msadsc_t，而且这个空闲 msadsc_t 要和上一步合并的 2 个 msadsc_t 对应的物理地址是连续的。没有则把这个合并的 2 个 msadsc_t 挂载第 1 个 bafhlst_t 结构中，算法结束，否则进入下一步。 　　（6）把第 1 个 bafhlst_t 结构中的 2 个连续的 msadsc_t 结构，还有合并的 2 个地址连续的 msadsc_t 结构拿出来，合并成 4 个连续且更大的 msadsc_t 结构。 　　（7）继续查看第 2 个 bafhlst_t 结构，有没有空闲的 msadsc_t 结构，并且它要和上一步合并的 4 个 msadsc_t 结构对应的物理地址是连续的。没有则把这个合并的 4 个 msadsc_t 挂载第 2 个 bafhlst_t 结构中，算法结束。 　　（8）…… 　　将上述过程，以流程图的方式表现如下：

　　4、内存页的细分 　　在之前的学习中，我们将内存页的大小定为4KB（也可以是2MB等等）。 　　试想，在我们写代码的时候，经常会出现动态分配数组的情况： 　　如上例，需要分配15个字节大小的内存空间。如果说这15个字节的内存空间，就单独分配一页4KB，内存使用率岂不是极低？ 　　如果为了解决这种方式就将页的大小降低，那么势必会增加在页管理方面的性能损耗。 　　那么可不可以逻辑上再将页进行细分呢？——比如单独拿出一些内存页，将其划分为32 字节、64 字节、128 字节、256 字节、512 字节等大小的内存小块，如下图所示。

　　当需要分配较小的内存空间时，就从这些内存小块中选出合适的空间分配出去。 　　4.1 内存对象 　　将内存页中逻辑上划分的内存小块称为内存对象。用下面这个结构体来表示内存对象： 　　同时，为了方便放置内存对象，设置一个内存对象容器来保存内存对象，结构体如下： 　　上述代码一共有四个结构体，分别是内存对象容器kmsob_t，容器的扩展容量kmbext_t，用于管理内存对象占用的内存msclst_t与msomdc_t。它们之间的关系如下：

　　其中内存对象容器是用来挂载不同大小的内存对象，当当前内存页空间分配完毕之后，就需要再次向物理内存页面管理器请求分配一个内存页，而后在新的内存页上进行内存对象的划分，这个新的内存页就是所谓的扩展容量。 　　4.2 内存对象分配 　　那么如何分配内存对象呢？ 　　在我们的设计中，内存对象分配的核心函数是kmsob new opkmsob。它的功能很简单的，就是负责从空闲内存对象链表中取出第一个内存对象，返回它的首地址。 　　4.3 内存对象释放 　　内存对象释放的过程其实就是内存对象分配的逆过程：先根据释放内存对象的地址和大小，找到对应的内存对象容器，然后把该内存对象加入到对应内存对象容器的空闲链表上，最后查看是否需要释放内存对象容器占用的物理内存页面，代码如下： 　　值得注意的是，当频繁请求不同大小的内存对象并再释放时，就会留下大量的空闲内存对象，这对于内存也是一种浪费。因此我们需要一种策略来将空闲内存对象容器回收，先看看代码： 　　上述代码的主要逻辑就是，查看内存对象容器是否空闲（即该内存对象容器中全部都是空闲的内存对象），如果是空闲的，就对其进行销毁。 　　5、虚拟内存相关 　　大家需要明白，之前我们所有对内存的管理，是针对物理内存的。但是对于运行的进程来说，它们的地址空间应该都是虚拟内存地址，因此，接下来我们就需要学习如何表示虚拟内存页，并且如何将虚拟内存页和物理内存页相关联，最后我们研究如何分配和释放虚拟内存。 　　5.1 虚拟内存的表示 　　首先，虚拟地址空间有多大取决于处理器的位数——32位的处理器的虚拟地址空间为0~0xFFFFFFFF；64位的虚拟机地址空间为0xFFFFFFFFFFFFFFFF。但我们应该明白，虚拟地址空间只是一个逻辑上的概念，既然是逻辑上的概念，那么我们就可以对这个虚拟地址空间进行相关的安排和设计。 　　5.2 虚拟内存分区 　　同物理内存划分段一样，我们也对虚拟地址空间进行分段，将一部分地址用来放内核，另一部分地址用来放应用。对于x86 CPU，根据CPU所处的工作模式不同，我们可以将虚拟地址空间划分如下：

　　值得注意的是，长模式下的内存空间实在是太大，现在CPU其实只实现了48位的地址寻址，然而寄存器确实是64位的，因此高16位的数值其实是第47位的扩展。由于长模式下“天然”将内存空间分为了上下两个部分（排除保留空间），那就一部分给内核，另一部分给应用，结合各个部分的堆、栈、指令区、数据区、MMU页表等概念，我们将整个虚拟地址空间划分如下：

　　线性映射区使得内核能通过加减一个固定值的方式，方便的完成虚拟地址与物理地址的转换。 　　5.3 虚拟内存的表示 　　那么我们用什么样的数据结构来表示虚拟内存页以及相应的内存区呢？——在物理内存设计时，我们采用了一个内存页来表示一个内存，一个内存区间就是一系列内存页。 　　但是在虚拟内存空间，这个方法行不通——因为虚拟地址空间太大了！常见物理内存大小也就8G、16G等等，但是对于64位机，虚拟地址可达2^64次方，这是一个天文数字，单单是保存这些数据结构就足以将物理内存给用关，所以只能另寻它路。 　　由于虚拟地址空间往往是以区为单位的，比如栈区、堆区，指令区、数据区，这些区内部往往是连续的，区与区之间却间隔了很大空间，而且每个区的空间扩大时我们不会建立新的虚拟地址区间数据结构，而是改变其中的指针，这就节约了内存空间。 　　基于这个现象，我们将虚拟内存区的数据结构设计如下： 　　将所有的虚拟内存区顺序串联起来，就是整个虚拟内存地址空间： 　　虚拟地址是针对应用程序也就是进程而言的，那么它应该是进程的一个属性。对于一个进程来说，单单了解自身的虚拟地址空间还不够，还需要知道其他的信息，比如虚拟地址到物理内存地址的映射关系、各个区的开始和结束地址等,我们将这些信息组织起来共同表示一个进程的地址空间，结构体如下： 　　每段虚拟地址区间，在用到的时候都会映射对应的物理页面。前面我们物理内存管理器的设计，每分配一个或者一组内存页面，都会返回一个 msadsc_t 结构，所以我们还需要一个数据结构来挂载 msadsc_t 结构。 　　考虑到把一个文件映射到进程的虚拟地址空间中，只需要在内存页面中保留一份共享文件，多个程序就都可以共享它。我们用一个结构体来管理它： 　　另外，再设计一个数据结构，用来挂载所有的kvmemcbox_t结构体,： 　　我们对上面所有的数据结构做一个梳理：

　　从上倒下，从左到右来理解这个图。一个进程的虚拟地址空间由virmemadrs_t 结构管理，图上每一个 kmvarsdsc_t 结构就表示一个已经分配出去的虚拟地址空间。由于虚拟地址空间需要映射到实际物理内存页面，统一用kvmemcbox_t来管理，而所有的kvmemcbox_t都被kvmemcboxmgr来管理。 　　5.4 虚拟内存的分配 　　在我们的设计中，进程可以指定虚拟内存的开始地址（可能失败，因为被用了），也可以由系统分配，但是一定会指定分配内存的大小。 　　那么如何从地址空间中找到一个合适的虚拟地址分配出去？其实重点是遍历，是的，遍历。 　　参考neohope的留言——虚拟地址空间分配函数调用过程如下： 　　vma_new_vadrs -> vma_new_vadrs_core ->-> vma_find_kmvarsdsc 　　1、查找合适的 kmvarsdsc_t结构 　　2、如果可以复用找到的kmvarsdsc_t结构，扩容 　　3、如果无法复用，创建新的kmvarsdsc_t结构，加入到 virmemadrs_t【按地址有序】 　　其中，vma_find_kmvarsdsc->vma_find_kmvarsdsc_is_ok的查找过程为依次检查virmemadrs_t中全部 kmvarsdsc_t结构： 　　1、如果没有指定起始地址，则判断当前kmvarsdsc_t与下一个kmvarsdsc_t之间，是否有未分配的虚拟地址，长度满足要求，否则就查询下一个结构； 　　2、如果制定了起始地址，则判断当前kmvarsdsc_t与 下一个kmvarsdsc_t之间，，是否有未分配的虚拟地址，起始地址和长度都满足要求，否则就查询下一个结构；这个部分的核心代码如下： 　　5.5 虚拟内存的释放 　　这个部分的重点是找到合适的kmvarsdsc_t的结构体，而后将释放的虚拟内存地址放进去。 　　同样借用neohope的留言来解释这个过程：虚拟地址空间释放 vma_del_vadrs ->vma_del_vadrs_core ->->vma_del_find_kmvarsdsc 根据起始地址，查找要释放虚拟地址空间的kmvarsdsc_t结构； 　　根据要释放的空间与kmvarsdsc_t结构起始地址有四种情况： 　　A、首位都相等，砍掉kmvarsdsc_t结构 　　B、开始相等，砍掉kmvarsdsc_t开始 　　C、结尾相等，砍掉kmvarsdsc_t结尾 　　D、首尾都不相等，砍掉中间部分，两边拆分为两个kmvarsdsc_t结构 　　代码就不放了，就是根据释放的空间与kmvarsdsc_t结构体空间的关系来决定释放的方式。 　　5.6 虚拟内存的虚与实——缺页异常 　　其实当我们完成虚拟地址分配之后，这个虚拟地址是不能用的！ 　　如果我们对这个虚拟地址进行访问，那么它会产生一个缺页异常——因为我们仅仅是分配了一个虚拟地址空间，就对它进行访问，所以才会缺页。我们并没有为这个虚拟地址空间分配任何物理内存页面，建立对应的 MMU 页。 　　那么我们在分配虚拟地址的时候就分配相应的物理地址，而后建立MMU页面？ 　　但是为了节约物理内存，实际操作系统设计的时候是采用延迟分配的方式。 　　何为延迟分配？——就是先将虚拟地址分配出去，但是不分配相对应的物理内存页面，等到程序运行到这个虚拟地址时，才会去分配物理内存。 　　这个过程的核心代码如下： 　　对上述代码总结一下，主要是三件事：查看这个kmvarsdsc_t 虚拟地址是否合法；建立一个kvmemcbox结构体，挂载到kmvarsdsc_t 上；为kmvarsdsc_t 的kvmemcbox结构体分配一个物理内存页面，并加入MMU页表数据。