Linux 内存管理

引言

本文整理了 Linux 内核中内存管理的相关知识,其他 Linux 相关文章均收录于 <Linux系列文章>

内存管理

物理内存划分

在介绍内存管理之前,我们先来了解一下目前主流的两类计算机,它们分别以不同的方式管理内存:

  • UMA 计算机(一致内存访问,uniform memory access)所有 CPU 共用同一块连续内存,各个 CPU 访存速度相同。
  • NUMA 计算机(非一致内存访问,non-uniform memory access)每个 CPU 都有本地内存,可以快速访问,各个处理器之间通过总线连接,以支持对其他 CPU 的本地内存的访问,距离越远的内存访问速度越慢。

uma-numa
在 UMA 系统上,可以视作是只有一个 NUMA 内存节点来管理整个内存,所以 Linux 会以 NUMA 的视角来管理内存,对于 UMA 计算机只需要模拟一个单内存节点的 NUMA 就行。

在 Linux 中内存被划分为节点(NUMA 本地内存节点),每个节点关联到一个处理器上,在内核中用 pg_data_t 来表示一个节点。在每个 CPU 上,这些节点以链表的形式按照由近到远(距离这一 CPU)顺序组织起来。之所以这样做,是因为本地内存访问快,而越远的内存节点访问越慢,所以在需要内存分配时,会优先从速度快的内存节点上进行分配,如果速度快的内存节点可用内存不足时,才会考虑从更远的内存节点分配。
pg-data-link
除此之外,每个内存节点内又被划分为多个内存域,这是内存的进一步划分,这种进一步的划分帮助内核更加高效的管理和使用内存,同时内核也基于内存域建立起一个珍惜程度的层次结构,在内存分配时按照从”廉价->昂贵”的顺序分配使用。

  • ZONE_DMA:是和直接内存访问的内存域。该区域的长度依赖于处理器类型。在 IA-32 计算机上,一般为 16 MB,这是一些古老 ISA 设备(比如某些外接设备)可访存的最大尺寸,所以划分出这么一个区,这段内存十分宝贵,后面你会看到内核在进行内存分配时总是尽可能不使用该段内存,因为如果该段内存用尽了,和 ISA 设备的交互就会受到影响。
  • ZONE_DMA32:使用 32 位地址字能寻址的适合 DMA 的内存域。该域只存在于 64 位系统中,最大长度为 4GB。
  • ZONE_NORMAL:可直接映射到内核段的普通内存域,最大 896M。如果在 64 位系统中只有小于 4GB 的内存,那么所有内存都属于 ZONE_DMA32范围,ZONE_NORMAL为空。许多内核数据结构必须保存在该内存域,而不能放置到高端内存域。因此如果普通内存完全用尽,那么内核会面临紧急情况。所以只要高端内存域的内存没有用尽,都不会从普通内存域分配内存。
  • ZONE_HIGHMEM: 超出内核段的物理地址。高端内存是最廉价的,因为内核没有任何部分依赖于从该内存域分配的内存。如果高端内存域用尽,对内核没有任何副作用,这也是优先分配高端内存的原因。
  • ZONE_MOVABLE: 伪内存域,防止物理内存碎片化。

根据编译时的配置,可以无需考虑某些内存段。例如 64 位系统中,并不需要高端内存域。如果支持了只能访问 4 GB 以下内存的 32 位外设,才需要 DMA32 内存域。

每个内存域,又关联了一个数组,用于组织属于该内存域的物理内存页(页帧,4KB),每个页帧中都会记录该页是否被使用。除了这个一般性的数组之外,每个域中还会对每个 CPU 都有冷热页两组页链表。热页代表该页已加载到 CPU 高速缓存中,而冷页则相反。尽管一个内存域从属于某一内存节点,进而从属于某一 CPU-A,但是在 NUMA 模型中,其他 CPU-B 也是可以访问该内存的,所以 CPU-B 的高速缓存中也可能存在 CPU-A 的内存节点的某一页帧。在进行内存分配时,会参考这个冷热页的数据,如果分配的是热页,就可以免去将内存填入高速缓冲的过程。
cold-hot-page
上图就是冷热页的管理示意图,对于每个 CPU 都有一个冷页链表和一个热页链表,count 表示链表长度,high 表示一个最大页数阈值,如果超过了该阈值,则表明列表中页过多了就是适当的删除一些,因为冷热页的管理主要是为了加速内存的分配,所以没必要维护所有内存页的冷热情况,所以当超过 high 阈值时,需要将一些页还给伙伴系统。此外,因为 CPU 高速缓存一次填充过程可能填充多个页,所以图中的 batch 就是一个建议值,建议一次填充高速缓存过程中使用多少个页帧。

内核内存组织

在启动装载程序将内核复制到内存,内核被装载到物理地址的一个固定位置,此位置在编译时确定。下图给出了物理内存最低几 MB 的布局,以及内核的各个部分的内存分布。注意:用户和内核虚拟地址空间采用 3:1 划分时,内核段的虚拟地址起始位置是 0xC0000000,因为物理内存映射到内核的虚拟地址空间时,采用了从线性映射方式。换句话说,将内核的虚拟地址减去 0xC0000000,则可以得到对应的物理地址。
kernel-physical-memory
前 4 KB 是留给 BIOS 使用的,一般会忽略。随后的 640 KB 也未使用,因为紧接着的 ROM 区域是系统规定的保留位置,这里要保存BIOS ROM 或者显卡 ROM。在 IA-32 内核中,0x100000 作为内核的起始位置,因为从这开始有足够的连续内存区,可容纳整个内核。内核占据的内存分为几个段:

  • _text和_etext 是代码段的起始和结束位置,包含了编译后的内核代码
  • 数据段位于_etext和_edata之间,包含了大量内核变量
  • 初始化数据在内核启动后就不再需要,在内核初始化完成后,其中的数据可以从内存中删除,给应用留出更多空间。

前面已经说过,在 IA-32 系统上内核通常将 4GB 的可用虚拟地址空间按照 3:1 的比例划分。低 3GB 内存供用户进程使用,高 1GB 内存供内核使用,在用户应用执行切换到核心态时,内核必须运行在一个可靠的环境中,因此内核才做了上述的隔离,将 1GB 地址空间永久划归内核使用,而应用进程无法使用该段地址。

除此之外,内核的物理地址页则线性地映射到内核地址空间的起始处,以便内核可以直接访问(物理地址 = 内核地址 - 0xC0000000),而不需复杂且耗时的页表操作。
mem-space
这里大家可能会有疑问,前面介绍内存分区时说 ZONE_NORMAL 是直接映射到内核地址空间的内存域,但是 ZONE_NORMAL 的最大范围只到 896M 啊,内核地址空间有 1G 那么大,剩下的 128 M 都干什么用了。
1GB-kernel-space
上图给出的就是内核空间 1GB 的完整分布,其中前面从 3G(0xC0000000)开始的 896 M 就对应了 ZONE_DMA + ZONE_NORMAL 的 896M 物理内存,这一段是线性映射的。在此之后,就是高端内存了。内核通过这 128MB 的空间,完成了对整个 ZONE_HIGHMEM 物理内存的访问。接下来,我们就看看它是怎么做的。

  • 首先我们看到,这 128 MB 的头 8MB 没有名字,这实际上是一个弃用区,它可用作针对任何内核故障的保护措施。如果访问越界地址(即无意地访问物理上不存在的内存区),则访问失败并生成一个异常,报告该错误。如果 vmalloc 区域紧接着直接映射,那么访问将成功而不会注意到错误。
  • 虚拟内存中连续、但物理内存中不连续的内存区,可以在 vmalloc 区域分配。该机制通常用于用户过程,内核自身会试图尽力避免非连续的物理地址。内核通常会成功,因为大部分大的内存块都
    在启动时分配给内核,那时内存的碎片尚不严重。但在已经运行了很长时间的系统上,在内核需要物理内存时,就可能出现可用空间不连续的情况。比如动态加载模块时。
  • 持久映射用于将高端内存域中的持久页映射到内核中,64 位体系结构中不存在高端内存,所以不存在该段。
  • 固定映射是与物理地址空间中的固定页关联的虚拟地址空间项,但具体关联的页帧可以自由选择。它与通过固定公式与物理内存关联的直接映射页不同,虚拟固定映射地址与物理内存位置之间的关联可以自行定义,关联建立后内核总能通过这块虚拟地址映射到某一物理地址。固定映射的优点在于,这些页不会从 TLB(页表缓存) 刷出,因此访问这段内存时,总能通过高速缓存取得物理地址。

在 AMD64 系统中,因为 64 位地址空间阔度太大,当前并不需要这么大,所以只使用了一个较小的地址空间,地址字宽为 48 位。
amd64-memory-space
整个地址空间分为三部分:下半部用作用户空间,上半部用于内核空间。中间是禁用区。

vmalloc

我们知道,物理上连续的映射对内核来说是最好的(更快),但是可能并不是总都能成功,如果实在没法找到一块连续内存,也可以考虑像应用进程一样借助分页机制,考虑使用 vmalloc 段内存。这一段具有线性地址空间的所有性质,分配到其中的页可能位于物理内存中的任意地方,通过修改负责该区域的内核页表,就可以做到这一点。
vmalloc
如果能确信能够分配连续内存,那么就没有必要使用 vmalloc。毕竟该函数的目的就是在于分配大的内存块(在内存碎片严重的时候)。内核中有大约 400 处使用 vmalloc 的地方,大部分是在驱动程序。

持久映射

如果需要将高端页帧长期映射(作为持久映射)到内核地址空间中,必须使用 kmap 函数。需要映射的页用指向 page 的指针指定,作为该函数的参数。该函数在有必要时创建个映射(即,如果该页确实是高端页),并返回数据的地址。
kmap
在内核中通过哈希表的形式来管理持久映射的映射关系,通过链表来解决 hash 冲突的问题。

启动过程内存

在启动过程期间,尽管内存管理尚未初始化,但内核仍然需要分配内存以创建各种数据结构。bootmem 分配器用于在启动阶段早期分配内存。

显然,对该分配器的需求集中于简单性方面,而不是性能和通用性。因此内核开发者决定实现个最先适配(first-fit)分配器用于在启动阶段管理内存,这是可能想到的最简单方式。

该分配器使用一个位图来管理页,位图比特位的数目与系统中物理内存页的数目相同。比特位为1 ,表示已用页。比特位为0,表示空闲页。在需要分配内存时,分配器逐位扫描位图,直至找到一个能提供足够连续页的位置,即所谓的最先最佳(first-best)或最先适配位置。

该过程不是很高效,因为每次分配都必须从头扫描比特链。因此在内核完全初始化之后,不能将该分配器用于内存管理。伙伴系统(连同slab、slub或slob分配器)是一个好得多的方案。我们这就来介绍它们。

物理内存管理

伙伴系统

在内核初始化完成后,内存管理的职责由伙伴系统承担。前面说了每个内存节点都有多个内存域,在每个域中都有一个空闲内存管理组,伙伴系统按照连续物理内存段的大小进行了分组。管理的连续内存段的长度都为 2 的幂,换句话说,相邻两组的内存段,大小相差 2 倍。
buddy-memory-sample
上图就是伙伴系统的内存分组形式,最上面第 0 组中,连续内存的长度为 2^0=1(页),第 2 组管理的内存都是长度为 2^2=4 (页)的内存段。那么伙伴系统是怎么工作的呢?

当我们需要申请一个 2 页的连续内存段时,会先检查是否有现成的 2 页连续内存段,假设当前空闲内存情况如上图所示,可以看出当前没有长度为 2 的内存段,所以要向长度为 4 的组中借一个长度为 4 的内存段,然后将其拆分为 2 个长度为 2 的内存段,一半分配给内存申请者,一半放入第 1 组(管理内存段长度为 2 的组)继续管理。

如果某个时刻,由于内存的释放,两个内存段都处于空闲状态,并且它们是连续的,就比如我们刚才例子中分配的两半内存段,都空闲时,伙伴系统会自动将其合并,并上交到第 2 组(管理长度为 4 的内存段)管辖。
zone-buddy
因为伙伴系统是按照内存域来管理的,并且我们前面也介绍了,在进行内存分配时,不同域的分配优先级各不相同,DMA 相较于 NORMAL 要小,所以内核中维护了如上的内存分配备用列表,列表中的域按照珍稀程度排序。优先分配不重要的内存域。值得一提的是,备用列表中也要考虑其他内存节点的内存域,最终综合优先级为 本地内存>其他节点内存HIGH_MEM > NORMAL > DMA
back-list
有关伙伴系统的状态可以通过 /proc/buddyinfo 查看,它会展示伙伴系统中各个层中,空闲的内存段数量,例如,DMA32 内存区的伙伴系统中,长度为 2^1=2 (页)的连续内存段的数量为 1219 个。

1
2
3
cat /proc/buddyinfo
Node 0,zone DMA 9 13 12 6 2 1 2 3 1 2 0
Node 0,zone DMA32 5058 1219 300 205 85 52 32 13 12 1 0

避免碎片

在上面的伙伴系统介绍中,一个链表就能满足所有需求,但是 Linux 的内存管理中一直有一个长期存在的问题:系统运行长时间后,物理内存会产生很多碎片。
page-spark
从上图中可以看出,尽管散布着许多空闲页,25% 的物理内存未分配,但是最大的连续空闲页只有一页。这对于应用进程没有问题,因为其内存是通过页表映射的,无论空闲页在物理内存中是否连续,应用程序在内存地址空间中看到的始终是连续的内存,如上图。但是,在内核中就不一样了,因为内核使用线性映射,不使用页表,所以物理不连续的内存在内核地址空间中就不连续。这时候,当内核需要一个超过 1 页的连续内存时就拿不到。

内核通过一个叫做反碎片的机制来从源头改善这个问题。它是如何工作的呢?首先,内核将已分配的页划分为三个类型:

  • 不可移动页:在内存中有固定位置,不能移动到其他地方,核心内核分配的大多数内存属于该类。
  • 可回收页:不能直接移动,但是可以删除,其内容可以从某些源重新生成。比如内存短缺时,发生页面回收。
  • 可以移动页:可以随意移动。用户应用属于该类别。它是通过页表映射的,所以可以复制到新位置,页表项可以相应的更新,应用程序感知不到该过程。

页的可移动性,依赖该页属于 3 种类别的哪一种。内核使用的反碎片技术,即基于将具有相同可移动性的页分组的思想。为什么这种方法有助于减少碎片?考虑一下不分类时会发生的情况,可移动的页和不可移动的页散在一起,由于某些页无法移动,不可移动的页不能位于可移动内存区的中间,导致在原本几乎全空的内存区中无法通过移动内存也来获得更大的连续区域。
fragmentation-example
如果根据页的可移动性,将其分配到不同的列表中,即可防止这种情形。这样虽然不可移动的页中仍然难以找到较大的连续空闲空间,但是对可移动或可回收的页就容易多了,我们可以通过移动或者回收来获得更大的连续内存。

考虑到内存的可移动性之后,伙伴系统的内存管理结构就变成了如下的形式。
buddy-memory
但要注意,从最初开始,内存并未划分为可移动性不同的区。最初所有的页都是可移动的,其他类型的页是在运行时形成的。那么这些不可移动的页是怎么来的呢?在进行内存分配时,会通过分配掩码告知内核,这块内存的迁移类型,如果要分配的是不可移动的页,而没有不可移动类型的空闲页时,会从其他类型的内存区中”盗取”,而且在策略上倾向于盗取一块更大的内存区,这样这块较大内存区会在不可移动类中逐渐演化成多个更小的不可移动区。这种优先”盗取”大块内存区的策略,显然能减少对可移动内存区的污染。

实际上,在启动期间分配可移动内存区的情况较少,那么分配器有很高的几率分配长度最大的内存区,并将其从可移动列表转换到不可移动列表。由于分配的内存区长度是最大的,因此不会向可移动内存中引入碎片。

总而言之,这种做法避免了启动期间内核分配的内存(经常在系统的整个运行时间都不释放)散布到物理内存各处,从而使其他类型的内存分配免受碎片的干扰,这也是页可移动性分组框架的最重要的目标之一。

除了根据可移动性组织页之外,内核还提供了另一种手段:虚拟内存域 ZONE_MOVABLE。基本思想很简单,将可用的内存划分为两个内存域,一个用于可移动分配,一个用于不可移动分配,这样自然就不会出现不可移动页污染可移动区内存的情况。

分配过程

分配的简略过程如下:

  1. 在内存分配时,会按照前面介绍的分配优先级,挨个扫描所有的内存域,内存节点,直到找到所需的内存页,这里要考虑到伙伴系统的大内存区拆分
  2. 如果没有找到,它会唤醒内核交换线程,交换线程会缩减内核缓存(回写)或进行页面回收(换出内存页)
  3. 交换线程处理完后,内核会重新进行内存分配。
  4. 如果还没有找到空闲页,内核会进行更加激进的处理,比如主动的内存整理(只针对可移动页),放宽各种限制,从保留内存中分配(内核会保留一部分内存用于应对这种情况),如果还是找不到可用内存甚至会调起 OOM Killer,该函数选择一个内核认为犯有分配过多内存”罪行”的进程,并杀死它。
  5. 如果最终内核找到了适当的内存域,并有足够的空闲页可供分配,那么它会检查这些页是否连续,其次还要按照伙伴系统的方式将这些页从空闲页链表中移除。
  6. 如果要分配的页大小为 1,即单页分配,内核会进行优化,该页不是从伙伴系统取得,而是从冷热页缓存中获取,这一点我们前面提过,热页不需要重新填入高级缓存,所以能省不少时间。

释放页

释放的简略过程如下:

  1. 如果释放的是单页,则通过冷热页缓存释放,如果冷热页缓存中页太多了,则将一些页还给伙伴系统
  2. 伙伴系统,如果发现有空闲页可以合并,就会进行合并,一级一级向上进行

buddy-combine

slab 分配器

上面描述的伙伴系统支持按页分配内存,但这个单位太大了。如果需要为一个 10 个字符的字符串分配空间,分配一个 4KB 或更多空间的完整页面,不仅浪费而且完全不可接受。显然要将页拆分为更小的单位,可以容纳大量的小对象。

为此必须引入新的管理机制,这会给内核带来更大的开销。为最小化这个额外负担对系统性能的影响,该管理层的实现应该尽可能紧凑,以便不要对处理器的高速缓存和 TLB(页表缓存) 带来显著影响。同时,内核还必须保证内存利用的速度和效率。不仅 Linux,而且类似的 UNIX 和所有其他的操作系统,都需要面对这个问题。slab 分配器就是为了解决这个问题而生,它对许多种类工作负荷都非常高效。

提供小内存块不是 slab 分配器的唯一任务。由于结构上的特点,它也用作一个缓存,主要针对经常分配并释放的对象。当 slab 缓存内存不足时,才会去伙伴系统申请新的页帧,或者当页帧过多时,将一些页帧还回伙伴系统。通过建立 slab 缓存,内核能够储备一些对象,供后续使用,即使在初始化状态,也是如此。举例来说,为管理与进程关联的文件系统数据,内核必须经常生成struct fs_struct的新实例。此类型实例占据的内存块同样需要经常回收(在进程结束时)。换句话说,内核趋向于非常有规律地分配并释放大小为sizeof(fs_struct)的内存块。slab 分配器将释放的内存块保存在个内部列表中,并不马上返回给伙伴系统。在请求为该类对象分配一个新实例时,会使用最近释放的内存块。这有两个优点。首先,由于内核不必使用伙伴系统算法,处理时间会变短。其次,由于该内存块仍然是“新”的,因此其仍然驻留在 CPU 高速缓存的概率较高。

尽管 slab 分配器对许多可能的工作负荷都工作良好,但也有一些情形,它无法提供最优性能。比如微小的嵌入式系统,和配备有大量物理内存的大规模并行系统。在大型系统上仅 slab 的数据结构就需要很多 G 字节内存。对嵌入式系统来说,slab 分配器代码量和复杂性都太高。于是就有了如下两个变体:

  • slob:进行了特别优化,减少代码量。
  • slub:将页帧打包为组,试图最小化所需的内存开销。

slab
slab 分配器由管理性数据的缓存对象和被管理对象的各个 slab 组成。每个缓存只负责一种对象类型(例如 unix_sock),或提供一个一般性的缓冲区(按照 buffer 大小分为多个缓存,比如 10 byte 的对应一个缓存 20 byte 的对应另一个缓存)。各个缓存中的 slab 数量各不相同,这与已使用页的数目,对象长度等有关。
slab-structure
为了更好地利用 CPU 缓存,slab 缓存会为每个 CPU 保存一个释放列表,它会按照后进先出 LIFO 的顺序分配,内核假定刚释放的对象仍在 CPU 高速缓冲中,会尽快再次分配它,只有当对应 CPU 的释放为空时才会从空闲列表中挑选 slab 对象。
slab-memory
此外,slab 缓存还会考虑到对齐的情况,以更好地利用高速缓存。

高速缓存和 TLB(页表缓存)

高速缓存对系统总体性能十分关键,这也是内核尽可能提高其利用效率的原因。这主要是通过在内存中巧妙地对齐内核数据。使用数据结构时正确对齐,确实对高速缓存有影响,但这只是隐式的,内核提供了一些命令,可以直接作用于处理器的高速缓存和 TLB(页表缓存)。但这些命令并非用于提高系统的效率,而是用于维护缓存内容的一致性,确保不出现不正确和过时的缓存项。例如,在从一个进程的地址空间移除一个映射时,内核负责从 TLB(页表缓存) 删除对应项。如果未能这样做,那么在先前被映射占据的虚拟内存地址添加新数据时,对该地址的读写操作将被重定向到物理内存中不正确的地址。又比如其他 CPU-B 准备要修改 CPU-A 的内存节点中的某块内容,就需要刷出 CPU-A 上对应内存块的高速缓存,然后再修改内存,这样才能保证一致性。

参考内容

[1]《Linux内核设计与实现》
[2]《Linux系统编程》
[3]《深入理解Linux内核》
[4]《深入Linux内核架构》
[5] Linux 内核进程管理之进程ID
[6] 服务器三大体系SMP、NUMA、MPP介绍
[7] Linux中的物理内存管理 [一]
[8] Linux内核中的page migration和compaction机制简介
[9] 物理地址、虚拟地址(线性地址)、逻辑地址以及MMU的知识
[10] 逻辑地址
[11] linux内核学习笔记-struct vm_area_struct
[12] Linux中匿名页的反向映射
[13] 系统调用过程详解
[14] 再谈Linux内核中的RCU机制
[15] Unix domain socket 和 TCP/IP socket 的区别
[16] Linux通用块设备层
[17] ext2文件系统结构分析
[18] linux ACL权限规划:getfacl,setfacl使用
[18] 查找——图文翔解RadixTree(基数树)
[19] 页缓存page cache和地址空间address_space
[20] rocketmq使用的系统参数(dirty_background_ration dirty_ratio)
[21] Linux内存调节之zone watermark
[22] Linux的内存回收和交换
[23] Linux中的内存回收[一]
[24] linux内存源码分析 - 内存回收(整体流程)
[25] Linux 软中断机制分析
[26] 对 jiffies 溢出、回绕及 time_after 宏的理解
[27] learn-linux-network-namespace
[28] 显式拥塞通知
[29] 聊聊 TCP 长连接和心跳那些事
[30] 关于 TCP/IP,必知必会的十个问题
[31] TCP协议三次握手连接四次握手断开和DOS攻击
[32] TCP 的那些事儿(上)
[33] TCP 的那些事儿(下)

贝克街的流浪猫 wechat
您的打赏将鼓励我继续分享!
  • 本文作者: 贝克街的流浪猫
  • 本文链接: https://www.beikejiedeliulangmao.top/linux/memory-management/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议,转载请注明出处!
  • 创作声明: 本文基于上述所有参考内容进行创作,其中可能涉及复制、修改或者转换,图片均来自网络,如有侵权请联系我,我会第一时间进行删除。