内存管理的目标
外存是程序存储的地方,内存是进程运行的地方。
内存管理的目标除了实现进程之间的隔离、进程与内核之间的隔离、减少物理内存并发使用的数量之外,还有以下几个目标。
1、减少内存碎片,包括外部碎片和内部碎片。外部碎片是指还在内存分配器中的内存,但是由于比较分散,无法满足用户大块连续内存分配的申请。内部碎片是指你申请了5个字节的内存,分配器给你分配了8个字节的内存,其中3个字节的内存是内部碎片。内存管理要尽量同时减少外部碎片和内部碎片。所以内存分配接口要灵活多样,同时满足多种不同的内存分配需求。既要满足大块连续内存分配的需求,又能满足小块零碎内存分配的需求。
2、内存分配效率要高。内存分配要尽量快地完成,比如说你设计了一种算法,能完全解决内存碎片问题,但是内存算法实现得特别复杂,每次分配都需要1毫秒的时间,这就不可取了。
3、提高物理内存的利用率。比如及时回收物理内存、对内存进行压缩。
Linux内存管理体系
Linux内存管理的整体模式是虚拟内存管理(分页内存管理),并在此基础上建立了一个庞大的内存管理体系。我们先来看一下总体结构图。
整个体系分为3部分,左边是物理内存,右边是虚拟内存,中间是虚拟内存映射(分页机制)。我们先从物理内存说起,内存管理的基础还是物理内存的管理。
物理内存那么大,应该怎么管理呢?首先要对物理内存进行层级区划,其原理可以类比于我国的行政区划管理。我国幅员辽阔,国家直接管理个人肯定是不行的,我国采取的是省县乡三级管理体系。把整个国家按照一定的规则和历史原因分成若干个省,每个省由省长管理。每个省再分成若干个县,每个县由县长管理。每个县再分成若干个乡,每个乡由乡长管理,乡长直接管理个人。(注意,类比是理解工具,不是论证工具)。对应的,物理内存也是采用类似的三级区域划分的方式来管理的,三个层级分别叫做节点(node)、区域(zone)、页面(page),对应到省、县、乡。系统首先把整个物理内存划分为N个节点,内存节点只是叫节点,大家不能把它看成一个点,要把它看成是相当于一个省的大区域。每个节点都有一个节点描述符,相当于是省长。节点下面再划分区域,每个区域都有区域描述符,相当于是县长。区域下面再划分页面,每个页面都有页面描述符,相当于是乡长。页面再下面就是字节了,相当于是个人。
对物理内存建立三级区域划分之后,就可以在其基础之上建立分配体系了。物理内存的分配体系可以类比于一个公司的销售体系,有工厂直接进行大额销售,有批发公司进行大量批发,有小卖部进行日常零售。物理内存的三级分配体系分别是buddy system、slab allocator和kmalloc。buddy system相当于是工厂销售,slab allocator相当于是批发公司,kmalloc相当于是小卖部,分别满足人们不同规模的需求。
物理内存有分配也有释放,但是当分配速度大于释放速度的时候,物理内存就会逐渐变得不够用了。此时我们就要进行内存回收了。内存回收首先考虑的是内存规整,也就是内存碎片整理,因为有可能我们不是可用内存不足了,而是内存太分散了,没法分配连续的内存。内存规整之后如果还是分配不到内存的话,就会进行页帧回收。内核的物理内存是不换页的,所以内核只会进行缓存回收。用户空间的物理内存是可以换页的,所以会对用户空间的物理内存进行换页以便回收其物理内存。用户空间的物理内存分为文件页和匿名页。对于文件页,如果其是clean的,可以直接丢弃内容,回收其物理内存,如果其是dirty的,则会先把其内容写回到文件,然后再回收内存。对于匿名页,如果系统配置的有swap区的话,则会把其内容先写入swap区,然后再回收,如果系统没有swap区的话则不会进行回收。把进程占用的但是当前并不在使用的物理内存进行回收,并分配给新的进程来使用的过程就叫做换页。进程被换页的物理内存后面如果再被使用到的话,还会通过缺页异常再换入内存。如果页帧回收之后还没有得到足够的物理内存,内核将会使用最后一招,OOM Killer。OOM Killer会按照一定的规则选择一个进程将其杀死,然后其物理内存就被释放了。
内核还有三个内存压缩技术zram、zswap、zcache,图里并没有画出来。它们产生的原因并不相同,zram和zswap产生的原因是因为把匿名页写入swap区是IO操作,是非常耗时的,使用zram和zswap可以达到用空间换时间的效果。zcache产生的原因是因为内核一般都有大量的pagecache,pagecache是对文件的缓存,有些文件缓存暂时用不到,可以对它们进行压缩,以节省内存空间,到用的时候再解压缩,以达到用时间换空间的效果。
物理内存的这些操作都是在内核里进行的,但是CPU访问内存用的并不是物理内存地址,而是虚拟内存地址。内核需要建立页表把虚拟内存映射到物理内存上,然后CPU就可以通过MMU用虚拟地址来访问物理内存了。虚拟内存地址空间分为两部分,内核空间和用户空间。内核空间只有一个,其页表映射是在内核启动的早期就建立的。用户空间有N个,用户空间是随着进程的创建而建立的,但是其页表映射并不是马上建立,而是在程序的运行过程中通过缺页异常逐步建立的。内核页表建立好了之后就不会再取消了,所以内核是不换页的,用户页表建立之后可能会因为内存回收而取消,所以用户空间是换页的。内核页表是在内核启动时建立的,内核空间的映射是线性映射,用户空间的页表是在运行时动态创建的,不可能做到线性映射,所以是随机映射。
有些书上会说用户空间是分页的,内核是不分页的,这是对英语paging的错误翻译,paging在这里不是分页的意思,而是换页的意思。分页是指整个分页机制,换页是内存回收中的操作,两者的含义是完全不同的。
现在我们对Linux内存管理体系已经有了宏观上的了解,下面我们就来对每个模块进行具体地分析。
物理内存区划
内核对物理内存进行了三级区划。为什么要进行三级区划,具体怎么划分的呢?这个不是软件随意决定的,而是和硬件因素有关。下面我们来看一下每一层级划分的原因,以及软件上是如果描述的。
物理内存节点
我国的省为什么要按照现在的这个形状来划分呢,主要是依据山川地形还有民俗风情等历史原因。那么物理内存划分为节点的原因是什么呢?这就要从UMA、NUMA说起了。我们用三个图来看一下。
图中的CPU都是物理CPU。当一个系统中的CPU越来越多、内存越来越多的时候,内存总线就会成为一个系统的瓶颈。如果大家都还挤在同一个总线上,速度必然很慢。于是我们可以采取一种方法,把一部分CPU和一部分内存直连在一起,构成一个节点,不同节点之间CPU访问内存采用间接方式。节点内的内存访问速度就会很快,节点之间的内存访问速度虽然很慢,但是我们可以尽量减少节点之间的内存访问,这样系统总的内存访问速度就会很快。
Linux中的代码对UMA和NUMA是统一处理的,因为UMA可以看成是只有一个节点的NUMA。如果编译内核时配置了CONFIG_NUMA,内核支持NUMA架构的计算机,内核中会定义节点指针数组来表示各个node。如果编译内核时没有配置CONFIG_NUMA,则内核只支持UMA架构的计算机,内核中会定义一个内存节点。这样所有其它的代码都可以统一处理了。
下面我们先来看一下节点描述符的定义。
linux-src/include/linux/mmzone.h
/* * On NUMA machines, each NUMA node would have a pg_data_t to describe * it's memory layout. On UMA machines there is a single pglist_data which * describes the whole memory. * * Memory statistics and page replacement data structures are maintained on a * per-zone basis. */ typedef struct pglist_data { /* * node_zones contains just the zones for THIS node. Not all of the * zones may be populated, but it is the full list. It is referenced by * this node's node_zonelists as well as other node's node_zonelists. */ struct zone node_zones[MAX_NR_ZONES]; /* * node_zonelists contains references to all zones in all nodes. * Generally the first zones will be references to this node's * node_zones. */ struct zonelist node_zonelists[MAX_ZONELISTS]; int nr_zones; /* number of populated zones in this node */ #ifdef CONFIG_FLATMEM /* means !SPARSEMEM */ struct page *node_mem_map; #ifdef CONFIG_PAGE_EXTENSION struct page_ext *node_page_ext; #endif #endif ... } pg_data_t;
对于UMA,内核会定义唯一的一个节点。
linux-src/mm/memblock.c
#ifndef CONFIG_NUMA struct pglist_data __refdata contig_page_data; EXPORT_SYMBOL(contig_page_data); #endif
查找内存节点的代码如下:
linux-src/include/linux/mmzone.h
extern struct pglist_data contig_page_data; static inline struct pglist_data *NODE_DATA(int nid) { return &contig_page_data; }
对于NUMA,内核会定义内存节点指针数组,不同架构定义的不一定相同,我们以x86为例。
linux-src/arch/x86/mm/numa.c
struct pglist_data *node_data[MAX_NUMNODES] __read_mostly; EXPORT_SYMBOL(node_data);
查找内存节点的代码如下:
linux-src/arch/x86/include/asm/mmzone_64.h
extern struct pglist_data *node_data[]; #define NODE_DATA(nid) (node_data[nid])
可以看出对于UMA,Linux是统一定义一个内存节点的,对于NUMA,Linux是在各架构代码下定义内存节点的。由于我们常见的电脑手机都是UMA的,后面的我们都以UMA为例进行讲解。pglist_data各自字段的含义我们在用到时再进行分析。
2.2 物理内存区域
内存节点下面再划分为不同的区域。划分区域的原因是什么呢?主要是因为各种软硬件的限制导致的。目前Linux中最多可以有6个区域,这些区域并不是每个都必然存在,有的是由config控制的。有些区域就算代码中配置了,但是在系统运行的时候也可能为空。下面我们依次介绍一下这6个区域。
ZONE_DMA:
由配置项CONFIG_ZONE_DMA决定是否存在。在x86上DMA内存区域是物理内存的前16M,这是因为早期的ISA总线上的DMA控制器只有24根地址总线,只能访问16M物理内存。为了兼容这些老的设备,所以需要专门开辟前16M物理内存作为一个区域供这些设备进行DMA操作时去分配物理内存。
ZONE_DMA32:
由配置项CONFIG_ZONE_DMA32决定是否存在。后来的DMA控制器有32根地址总线,可以访问4G物理内存了。但是在32位的系统上最多只支持4G物理内存,所以没必要专门划分一个区域。但是到了64位系统时候,很多CPU能支持48位到52位的物理内存,于是此时就有必要专门开个区域给32位的DMA控制器使用了。
ZONE_NORMAL:
常规内存,无配置项控制,必然存在,表示内核能够直接线性映射的普通内存区域。比如内核程序中代码段、全局变量以及kmalloc获取的堆内存等。
ZONE_HIGHMEM:
高端内存,由配置项CONFIG_HIGHMEM决定是否存在。只在32位系统上有,这是因为32位系统的内核空间只有1G,这1G虚拟空间中还有128M用于其它用途,所以只有896M虚拟内存空间用于直接映射物理内存,而32位系统支持的物理内存有4G,大于896M的物理内存是无法直接映射到内核空间的,所以把它们划为高端内存进行特殊处理。对于64位系统,从理论上来说,内核空间最大263-1,物理内存最大264,好像内核空间还是不够用。但是从现实来说,内核空间的一般配置为247,高达128T,物理内存暂时还远远没有这么多。所以从现实的角度来说,64位系统是不需要高端内存区域的。
ZONE_MOVABLE:
可移动内存,无配置项控制,必然存在,用于可热插拔的内存。内核启动参数movablecore用于指定此区域的大小。内核参数kernelcore也可用于指定非可移动内存的大小,剩余的内存都是可移动内存。如果两者同时指定的话,则会优先保证非可移动内存的大小至少有kernelcore这么大。如果两者都没指定,则可移动内存大小为0。
ZONE_DEVICE:
设备内存,由配置项CONFIG_ZONE_DEVICE决定是否存在,用于放置持久内存(也就是掉电后内容不会消失的内存)。一般的计算机中没有这种内存,默认的内存分配也不会从这里分配内存。持久内存可用于内核崩溃时保存相关的调试信息。
下面我们先来看一下这几个内存区域的类型定义。
linux-src/include/linux/mmzone.h
enum zone_type { #ifdef CONFIG_ZONE_DMA ZONE_DMA, #endif #ifdef CONFIG_ZONE_DMA32 ZONE_DMA32, #endif ZONE_NORMAL, #ifdef CONFIG_HIGHMEM ZONE_HIGHMEM, #endif ZONE_MOVABLE, #ifdef CONFIG_ZONE_DEVICE ZONE_DEVICE, #endif __MAX_NR_ZONES };
我们再来看一下区域描述符的定义。
linux-src/include/linux/mmzone.h
struct zone { /* Read-mostly fields */ /* zone watermarks, access with *_wmark_pages(zone) macros */ unsigned long _watermark[NR_WMARK]; unsigned long watermark_boost; unsigned long nr_reserved_highatomic; /* * We don't know if the memory that we're going to allocate will be * freeable or/and it will be released eventually, so to avoid totally * wasting several GB of ram we must reserve some of the lower zone * memory (otherwise we risk to run OOM on the lower zones despite * there being tons of freeable ram on the higher zones). This array is * recalculated at runtime if the sysctl_lowmem_reserve_ratio sysctl * changes. */ long lowmem_reserve[MAX_NR_ZONES]; #ifdef CONFIG_NUMA int node; #endif struct pglist_data *zone_pgdat; struct per_cpu_pages __percpu *per_cpu_pageset; struct per_cpu_zonestat __percpu *per_cpu_zonestats; /* * the high and batch values are copied to individual pagesets for * faster access */ int pageset_high; int pageset_batch; ... } ____cacheline_internodealigned_in_smp;
zone结构体中各个字段的含义我们在用到的时候再进行解释。
2.3 物理内存页面
每个内存区域下面再划分为若干个面积比较小但是又不太小的页面。页面的大小一般都是4K,这是由硬件规定的。内存节点和内存区域从逻辑上来说并不是非得有,只不过是由于各种硬件限制或者特殊需求才有的。内存页面倒不是因为硬件限制才有的,主要是出于逻辑原因才有的。页面是分页内存机制和底层内存分配的最小单元。如果没有页面的话,直接以字节为单位进行管理显然太麻烦了,所以需要有一个较小的基本单位,这个单位就叫做页面。页面的大小选多少合适呢?太大了不好,太小了也不好,这个数值还得是2的整数次幂,所以4K就非常合适。为啥是2的整数次幂呢?因为计算机是用二进制实现的,2的整数次幂做各种运算和特殊处理比较方便,后面用到的时候就能体会到。为啥是4K呢?因为最早Intel选择的就是4K,后面大部分CPU也都跟着选4K作为页面的大小了。
物理内存页面也叫做页帧。物理内存从开始起每4K、4K的,构成一个个页帧,这些页帧的编号依次是0、1、2、3…。页帧的编号也叫做pfn(page frame number)。很显然,一个页帧的物理地址和它的pfn有一个简单的数学关系,那就是其物理地址除以4K就是其pfn,其pfn乘以4K就是其物理地址。由于4K是2的整数次幂,所以这个乘除运算可以转化为移位运算。下面我们看一下相关的宏操作。
linux-src/include/linux/pfn.h
#define PFN_ALIGN(x) (((unsigned long)(x) + (PAGE_SIZE - 1)) & PAGE_MASK) #define PFN_UP(x) (((x) + PAGE_SIZE-1) >> PAGE_SHIFT) #define PFN_DOWN(x) ((x) >> PAGE_SHIFT) #define PFN_PHYS(x) ((phys_addr_t)(x) << PAGE_SHIFT) #define PHYS_PFN(x) ((unsigned long)((x) >> PAGE_SHIFT))
PAGE_SHIFT的值在大部分平台上都是等于12,2的12次方幂正好就是4K。
下面我们来看一下页面描述符的定义。
linux-src/include/linux/mm_types.h
struct page { unsigned long flags; /* Atomic flags, some possibly * updated asynchronously */ /* * Five words (20/40 bytes) are available in this union. * WARNING: bit 0 of the first word is used for PageTail(). That * means the other users of this union MUST NOT use the bit to * avoid collision and false-positive PageTail(). */ union { struct { /* Page cache and anonymous pages */ /** * @lru: Pageout list, eg. active_list protected by * lruvec->lru_lock. Sometimes used as a generic list * by the page owner. */ struct list_head lru; /* See page-flags.h for PAGE_MAPPING_FLAGS */ struct address_space *mapping; pgoff_t index; /* Our offset within mapping. */ /** * @private: Mapping-private opaque data. * Usually used for buffer_heads if PagePrivate. * Used for swp_entry_t if PageSwapCache. * Indicates order in the buddy system if PageBuddy. */ unsigned long private; };... #if defined(WANT_PAGE_VIRTUAL) void *virtual; /* Kernel virtual address (NULL if not kmapped, ie. highmem) */ #endif /* WANT_PAGE_VIRTUAL */ #ifdef LAST_CPUPID_NOT_IN_PAGE_FLAGS int _last_cpupid; #endif } _struct_page_alignment;
可以看到页面描述符的定义非常复杂,各种共用体套共用体。为什么这么复杂呢?这是因为物理内存的每个页帧都需要有一个页面描述符。对于4G的物理内存来说,需要有4G/4K=1M也就是100多万个页面描述符。所以竭尽全力地减少页面描述符的大小是非常必要的。又由于页面描述符记录的很多数据不都是同时在使用的,所以可以使用共用体来减少页面描述符的大小。页面描述符中各个字段的含义,我们在用到的时候再进行解释。
2.4 物理内存模型
计算机中有很多名称叫做内存模型的概念,它们的含义并不相同,大家要注意区分。此处讲的内存模型是Linux对物理内存地址空间连续性的抽象,用来表示物理内存的地址空间是否有空洞以及该如何处理空洞,因此这个概念也被叫做内存连续性模型。由于内存热插拔也会导致物理内存地址空间产生空洞,因此Linux内存模型也是内存热插拔的基础。
最开始的时候是没有内存模型的,后来有了其它的内存模型,这个最开始的情况就被叫做平坦内存模型(Flat Memory)。平坦内存模型看到的物理内存就是连续的没有空洞的内存。后来为了处理物理内存有空洞的情况以及内存热插拔问题,又开发出了离散内存模型(Discontiguous Memory)。但是离散内存模型的实现复用了NUMA的代码,导致NUMA和内存模型的耦合,实际上二者在逻辑上是正交的。内核后来又开发了稀疏内存模型(Sparse Memory),其实现和NUMA不再耦合在一起了,而且稀疏内存模型能同时处理平坦内存、稀疏内存、极度稀疏内存,还能很好地支持内存热插拔。于是离散内存模型就先被弃用了,后又被移出了内核。现在内核中就只有平坦内存模型和稀疏内存模型了。而且在很多架构中,如x86、ARM64,稀疏内存模型已经变成了唯一的可选项了,也就是必选内存模型。
系统有一个页面描述符的数组,用来描述系统中的所有页帧。这个数组是在系统启动时创建的,然后有一个全局的指针变量会指向这个数组。这个变量的名字在平坦内存中叫做mem_map,是全分配的,在稀疏内存中叫做vmemmap,内存空洞对应的页表描述符是不被映射的。学过C语言的人都知道指针与数组之间的关系,指针之间的减法以及指针与整数之间的加法与数组下标的关系。因此我们可以把页面描述符指针和页帧号相互转换。
我们来看一下页面描述符数组指针的定义和指针与页帧号之间的转换操作。
linux-src/mm/memory.c
#ifndef CONFIG_NUMA struct page *mem_map; EXPORT_SYMBOL(mem_map); #endif
linux-src/arch/x86/include/asm/pgtable_64.h
#define vmemmap ((struct page *)VMEMMAP_START)
linux-src/arch/x86/include/asm/pgtable_64_types.h
#ifdef CONFIG_DYNAMIC_MEMORY_LAYOUT # define VMEMMAP_START vmemmap_base #else # define VMEMMAP_START __VMEMMAP_BASE_L4 #endif /* CONFIG_DYNAMIC_MEMORY_LAYOUT */
linux-src/include/asm-generic/memory_model.h
#if defined(CONFIG_FLATMEM) #ifndef ARCH_PFN_OFFSET #define ARCH_PFN_OFFSET (0UL) #endif #define __pfn_to_page(pfn) (mem_map + ((pfn) - ARCH_PFN_OFFSET)) #define __page_to_pfn(page) ((unsigned long)((page) - mem_map) + \ ARCH_PFN_OFFSET) #elif defined(CONFIG_SPARSEMEM_VMEMMAP) /* memmap is virtually contiguous. */ #define __pfn_to_page(pfn) (vmemmap + (pfn)) #define __page_to_pfn(page) (unsigned long)((page) - vmemmap) #elif defined(CONFIG_SPARSEMEM) /* * Note: section's mem_map is encoded to reflect its start_pfn. * section[i].section_mem_map == mem_map's address - start_pfn; */ #define __page_to_pfn(pg) \ ({ const struct page *__pg = (pg); \ int __sec = page_to_section(__pg); \ (unsigned long)(__pg - __section_mem_map_addr(__nr_to_section(__sec))); \ }) #define __pfn_to_page(pfn) \ ({ unsigned long __pfn = (pfn); \ struct mem_section *__sec = __pfn_to_section(__pfn); \ __section_mem_map_addr(__sec) + __pfn; \ }) #endif /* CONFIG_FLATMEM/SPARSEMEM */ /* * Convert a physical address to a Page Frame Number and back */ #define __phys_to_pfn(paddr) PHYS_PFN(paddr) #define __pfn_to_phys(pfn) PFN_PHYS(pfn) #define page_to_pfn __page_to_pfn #define pfn_to_page __pfn_to_page
2.5 三级区划关系
我们对物理内存的三级区划有了简单的了解,下面我们再对它们之间的关系进行更进一步地分析。虽然在节点描述符中包含了所有的区域类型,但是除了第一个节点能包含所有的区域类型之外,其它的节点并不能包含所有的区域类型,因为有些区域类型(DMA、DMA32)必须从物理内存的起点开始。Normal、HighMem和Movable是可以出现在所有的节点上的。页面编号(pfn)是从物理内存的起点开始编号,不是每个节点或者区域重新编号的。所有区域的范围都必须是整数倍个页面,不能出现半个页面。节点描述符不仅记录自己所包含的区域,还会记录自己的起始页帧号和跨越页帧数量,区域描述符也会记录自己的起始页帧号和跨越页帧数量。
下面我们来画个图看一下节点与页面之间的关系以及x86上具体的区分划分情况。
三、物理内存分配
当我们把物理内存区划弄明白之后,再来学习物理内存分配就比较容易了。物理内存分配最底层的是页帧分配。页帧分配的分配单元是区域,分配粒度是页面。如何进行页帧分配呢?Linux采取的算法叫做伙伴系统(buddy system)。只有伙伴系统还不行,因为伙伴系统进行的是大粒度的分配,我们还需要批发与零售,于是便有了slab allocator和kmalloc。这几种内存分配方法分配的都是线性映射的内存,当系统连续内存不足的时候,Linux还提供了vmalloc用来分配非线性映射的内存。下面我们画图来看一下它们之间的关系。
Buddy System既是直接的内存分配接口,也是所有其它内存分配器的底层分配器。Slab建立在Buddy的基础之上,Kmalloc又建立在Slab的基础之上。Vmalloc和CMA也是建立在Buddy的基础之上。Linux采取的这种内存分配体系提供了丰富灵活的内存接口,还能同时减少外部碎片和内部碎片。
3.1 Buddy System
伙伴系统的基本管理单位是区域,最小分配粒度是页面。因为伙伴系统是建立在物理内存的三级区划上的,所以最小分配粒度是页面,不能比页面再小了。基本管理单位是区域,是因为每个区域的内存都有特殊的用途或者用法,不能随便混用,所以不能用节点作为基本管理单位。伙伴系统并不是直接管理一个个页帧的,而是把页帧组成页块(pageblock)来管理,页块是由连续的2n个页帧组成,n叫做这个页块的阶,n的范围是0到10。而且2n个页帧还有对齐的要求,首页帧的页帧号(pfn)必须能除尽2n,比如3阶页块的首页帧(pfn)必须除以8(23)能除尽,10阶页块的首页帧必须除以1024(210)能除尽。0阶页块只包含一个页帧,任意一个页帧都可以构成一个0阶页块,而且符合对齐要求,因为任何整数除以1(20)都能除尽。
3.1.1 伙伴系统的内存来源
伙伴系统管理的内存并不是全部的物理内存,而是内核在完成初步的初始化之后的未使用内存。内核在刚启动的时候有一个简单的早期内存管理器,它会记录系统的所有物理内存以及在它之前就被占用的内存,并为内核提供早期的内存分配服务。当内核的基础初始化完成之后,它就会把所有剩余可用的物理内存交给伙伴系统来管理,然后自己就退出历史舞台了。早期内存管理器会首先尝试把页帧以10阶页块的方式加入伙伴系统,不够10阶的以9阶页块的方式加入伙伴系统,以此类推,直到以0阶页块的方式把所有可用页帧都加入到伙伴系统。显而易见,内核刚启动的时候高阶页块比较多,低阶页块比较少。早期内存管理器以前是bootmem,后来是bootmem和memblock共存,可以通过config选择使用哪一个,现在是只有memblock了,bootmem已经被移出了内核。
3.1.2 伙伴系统的管理数据结构
伙伴系统的管理数据定义在区域描述符中,是结构体free_area的数组,数组大小是11,因为从0到10有11个数。free_area的定义如下所示:
linux-src/include/linux/mmzone.h
struct free_area { struct list_head free_list[MIGRATE_TYPES]; unsigned long nr_free; }; enum migratetype { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_RECLAIMABLE, MIGRATE_PCPTYPES, /* the number of types on the pcp lists */ MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES, #ifdef CONFIG_CMA /* * MIGRATE_CMA migration type is designed to mimic the way * ZONE_MOVABLE works. Only movable pages can be allocated * from MIGRATE_CMA pageblocks and page allocator never * implicitly change migration type of MIGRATE_CMA pageblock. * * The way to use it is to change migratetype of a range of * pageblocks to MIGRATE_CMA which can be done by * __free_pageblock_cma() function. What is important though * is that a range of pageblocks must be aligned to * MAX_ORDER_NR_PAGES should biggest page be bigger than * a single pageblock. */ MIGRATE_CMA, #endif #ifdef CONFIG_MEMORY_ISOLATION MIGRATE_ISOLATE, /* can't allocate from here */ #endif MIGRATE_TYPES };
可以看到free_area的定义非常简单,就是由MIGRATE_TYPES个链表组成,链表连接的是同一个阶的迁移类型相同的页帧。迁移类型是内核为了减少内存碎片而提出的技术,不同区域的页块有不同的默认迁移类型,比如DMA、NORMAL默认都是不可迁移(MIGRATE_UNMOVABLE)的页块,HIGHMEM、MOVABLE区域默认都是可迁移(MIGRATE_MOVABLE)的页块。我们申请的内存有时候是不可移动的内存,比如内核线性映射的内存,有时候是可以移动的内存,比如用户空间缺页异常分配的内存。我们把不同迁移类型的内存分开进行分配,在进行内存碎片整理的时候就比较方便,不会出现一片可移动内存中夹着一个不可移动的内存(这种情况就很碍事)。如果要分配的迁移类型的内存不足时就需要从其它的迁移类型中进行盗页了。内核定义了每种迁移类型的后备类型,如下所示:
linux-src/mm/page_alloc.c
/* * This array describes the order lists are fallen back to when * the free lists for the desirable migrate type are depleted */ static int fallbacks[MIGRATE_TYPES][3] = { [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_TYPES }, [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES }, [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_TYPES }, #ifdef CONFIG_CMA [MIGRATE_CMA] = { MIGRATE_TYPES }, /* Never used */ #endif #ifdef CONFIG_MEMORY_ISOLATION [MIGRATE_ISOLATE] = { MIGRATE_TYPES }, /* Never used */ #endif };
一种迁移类型的页块被盗页之后,它的迁移类型就改变了,所以一个页块的迁移类型是会改变的,有可能变来变去。当物理内存比较少时,这种变来变去就会特别频繁,这样迁移类型带来的好处就得不偿失了。因此内核定义了一个变量page_group_by_mobility_disabled,当物理内存比较少时就禁用迁移类型。
伙伴系统管理页块的方式可以用下图来表示:
3.1.3 伙伴系统的算法逻辑
伙伴系统对外提供的接口只能分配某一阶的页块,并不能随意分配若干个页帧。当分配n阶页块时,伙伴系统会优先查找n阶页块的链表,如果不为空的话就拿出来一个分配。如果为空的就去找n+1阶页块的链表,如果不为空的话,就拿出来一个,并分成两个n阶页块,其中一个加入n阶页块的链表中,另一个分配出去。如果n+1阶页块链表也是空的话,就去找n+2阶页块的链表,如果不为空的话,就拿出来一个,然后分成两个n+1阶的页块,其中一个加入到n+1阶的链表中去,剩下的一个再分成两个n阶页块,其中一个放入n阶页块的链表中去,另一个分配出去。如果n+2阶页块的链表也是空的,那就去找n+3阶页块的链表,重复此逻辑,直到找到10阶页块的链表。如果10阶页块的链表也是空的话,那就去找后备迁移类型的页块去分配,此时从最高阶的页块链表往低阶页块的链表开始查找,直到查到为止。如果后备页块也分配不到内存,那么就会进行内存回收,这是下一章的内容。
用户用完内存还给伙伴系统的时候,并不是直接还给其对应的n阶页块的链表就行了,而是会先进行合并。比如你申请了一个0阶页块,用完了之后要归还,我们假设其页帧号是5,来推演一下其归还过程。如果此时发现4号页帧也是free的,则4和5会合并成一个1阶页块,首页帧号是4。如果4号页帧不是free的,则5号页帧直接还给0阶页块链表中去。如果6号页帧free呢,会不会和5号页帧合并?不会,因为不满足页帧号对齐要求。如果5和6合并,将会成为一个1阶页块,1阶页块要求其首页帧的页号必须除以2(21)能除尽,而5除以2除不尽,所以5和6不能合并。而4和5合并之后,4除以2(21)是能除尽的。4和5合并成一个1阶页块之后还要查看是否能继续合并,如果此时有一个1阶页块是free的,由6和7组成的,此时它们就会合并成一个2阶页块,包含4、5、6、7共4个页帧,而且符合对齐要求,4除以4(22)是能除尽的。如果此时有一个1阶页块是free的,由2和3组成的,那么就不能合并,因为合并后的首页帧是2,2除以4(22)是除不尽的。继续此流程,如果合并后的n阶页块的前面或者后面还有free的同阶页块,而且也符合对齐要求,就会继续合并,直到无法合并或者已经到达了10阶页块,才会停止合并,然后把其插入到对应的页块链表中去。
3.1.4 伙伴系统的接口
下面我们来看一下伙伴系统的接口。伙伴系统提供了两类接口,一类是返回页表描述符的,一类是返回虚拟内存地址的。
linux-src/include/linux/gfp.h
struct page *alloc_pages(gfp_t gfp, unsigned int order); #define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0) struct page *alloc_pages_node(int nid, gfp_t gfp_mask,unsigned int order); void __free_pages(struct page *page, unsigned int order); #define __free_page(page) __free_pages((page), 0)
释放的接口很简单,只需要一个页表描述符指针加一个阶数。分配的接口中,有的会指定nodeid,就从那个节点中分配内存。不指定nodeid的接口,如果是在UMA中,那就从唯一的节点中分配内存,如果是NUMA,会按照一定的策略选择在哪个节点中分配内存。最复杂的参数是gfp,gfp是标记参数,可以分为两类标记,一类是指定分配区域的,一类是指定分配行为的,下面我们来看一下。
linux-src/include/linux/gfp.h
#define ___GFP_DMA 0x01u #define ___GFP_HIGHMEM 0x02u #define ___GFP_DMA32 0x04u #define ___GFP_MOVABLE 0x08u #define ___GFP_RECLAIMABLE 0x10u #define ___GFP_HIGH 0x20u #define ___GFP_IO 0x40u #define ___GFP_FS 0x80u #define ___GFP_ZERO 0x100u #define ___GFP_ATOMIC 0x200u #define ___GFP_DIRECT_RECLAIM 0x400u #define ___GFP_KSWAPD_RECLAIM 0x800u #define ___GFP_WRITE 0x1000u #define ___GFP_NOWARN 0x2000u #define ___GFP_RETRY_MAYFAIL 0x4000u #define ___GFP_NOFAIL 0x8000u #define ___GFP_NORETRY 0x10000u #define ___GFP_MEMALLOC 0x20000u #define ___GFP_COMP 0x40000u #define ___GFP_NOMEMALLOC 0x80000u #define ___GFP_HARDWALL 0x100000u #define ___GFP_THISNODE 0x200000u #define ___GFP_ACCOUNT 0x400000u #define ___GFP_ZEROTAGS 0x800000u #define ___GFP_SKIP_KASAN_POISON 0x1000000u #ifdef CONFIG_LOCKDEP #define ___GFP_NOLOCKDEP 0x2000000u #else #define ___GFP_NOLOCKDEP 0 #endif
其中前4个是指定分配区域的,内核里一共定义了6类区域,为啥只有4个指示符呢?因为ZONE_DEVICE有特殊用途,不在一般的内存分配管理中,当不指定区域类型时默认就是ZONE_NORMAL,所以4个就够了。是不是指定了哪个区域就只能在哪个区域分配内存呢,不是的。每个区域都有后备区域,当其内存不足时,会从其后备区域中分配内存。后备区域是在节点描述符中定义,我们来看一下:
linux-src/include/linux/mmzone.h
typedef struct pglist_data { struct zonelist node_zonelists[MAX_ZONELISTS]; } pg_data_t; enum { ZONELIST_FALLBACK, /* zonelist with fallback */ #ifdef CONFIG_NUMA /* * The NUMA zonelists are doubled because we need zonelists that * restrict the allocations to a single node for __GFP_THISNODE. */ ZONELIST_NOFALLBACK, /* zonelist without fallback (__GFP_THISNODE) */ #endif MAX_ZONELISTS }; struct zonelist { struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1]; }; struct zoneref { struct zone *zone; /* Pointer to actual zone */ int zone_idx; /* zone_idx(zoneref->zone) */ };
在UMA上,后备区域只有一个链表,就是本节点内的后备区域,在NUMA中后备区域有两个链表,包括本节点内的后备区域和其它节点的后备区域。这些后备区域是在内核启动时初始化的。对于本节点的后备区域,是按照区域类型的id排列的,高id的排在前面,低id的排在后面,后面的是前面的后备,前面的区域内存不足时可以从后面的区域里分配内存,反过来则不行。比如MOVABLE区域的内存不足时可以从NORMAL区域来分配,NORMAL区域的内存不足时可以从DMA区域来分配,反过来则不行。对于其它节点的后备区域,除了会符合前面的规则之外,还会考虑后备区域是按照节点优先的顺序来排列还是按照区域类型优先的顺序来排列。
下面我们再来看一下分配行为的flag都是什么含义。
__GFP_HIGH:调用者的优先级很高,要尽量满足分配请求。
__GFP_ATOMIC:调用者处在原子场景中,分配过程不能回收页或者睡眠,一般是中断处理程序会用。
__GFP_IO:可以进行磁盘IO操作。
__GFP_FS:可以进行文件系统的操作。
__GFP_KSWAPD_RECLAIM:当内存不足时允许异步回收。
__GFP_RECLAIM:当内存不足时允许同步回收和异步回收。
__GFP_REPEAT:允许重试,重试多次以后还是没有内存就返回失败。
__GFP_NOFAIL:不能失败,必须无限次重试。
__GFP_NORETRY:不要重试,当直接回收和内存规整之后还是分配不到内存的话就返回失败。
__GFP_ZERO:把要分配的页清零。
还有一些其它的flag就不再一一进行介绍了。
如果我们每次分配内存都把这些flag一一进行组合,那就太麻烦了,所以系统为我们定义了一些常用的组合,如下所示:
linux-src/include/linux/gfp.h
#define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM) #define GFP_KERNEL (__GFP_RECLAIM | __GFP_IO | __GFP_FS) #define GFP_NOIO (__GFP_RECLAIM) #define GFP_NOFS (__GFP_RECLAIM | __GFP_IO) #define GFP_USER (__GFP_RECLAIM | __GFP_IO | __GFP_FS | __GFP_HARDWALL) #define GFP_DMA __GFP_DMA #define GFP_DMA32 __GFP_DMA32 #define GFP_HIGHUSER (GFP_USER | __GFP_HIGHMEM) #define GFP_HIGHUSER_MOVABLE (GFP_HIGHUSER | __GFP_MOVABLE | __GFP_SKIP_KASAN_POISON)
中断中分配内存一般用GFP_ATOMIC,内核自己使用的内存一般用GFP_KERNEL,为用户空间分配内存一般用GFP_HIGHUSER_MOVABLE。
我们再来看一下直接返回虚拟内存的接口函数。
linux-src/include/linux/gfp.h
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order); #define __get_free_page(gfp_mask) __get_free_pages((gfp_mask), 0) #define __get_dma_pages(gfp_mask, order) __get_free_pages((gfp_mask) | GFP_DMA, (order)) unsigned long get_zeroed_page(gfp_t gfp_mask); void free_pages(unsigned long addr, unsigned int order); #define free_page(addr) free_pages((addr), 0)
此接口不能分配HIGHMEM中的内存,因为HIGHMEM中的内存不是直接映射到内核空间中去的。除此之外这个接口和前面的没有区别,其参数函数也跟前面的一样,就不再赘述了。
3.1.5 伙伴系统的实现
下面我们再来看一下伙伴系统的分配算法。
linux-src/mm/page_alloc.c
/* * This is the 'heart' of the zoned buddy allocator. */ struct page *__alloc_pages(gfp_t gfp, unsigned int order, int preferred_nid, nodemask_t *nodemask) { struct page *page; /* First allocation attempt */ page = get_page_from_freelist(alloc_gfp, order, alloc_flags, &ac); if (likely(page)) goto out; page = __alloc_pages_slowpath(alloc_gfp, order, &ac); out: return page; }
伙伴系统的所有分配接口最终都会使用__alloc_pages这个函数来进行分配。对这个函数进行删减之后,其逻辑也比较简单清晰,先使用函数get_page_from_freelist直接从free_area中进行分配,如果分配不到就使用函数 __alloc_pages_slowpath进行内存回收。内存回收的内容在下一章里面讲。
3.2 Slab Allocator
伙伴系统的最小分配粒度是页面,但是内核中有很多大量的同一类型结构体的分配请求,比如说进程的结构体task_struct,如果使用伙伴系统来分配显然不合适,如果自己分配一个页面,然后可以分割成多个task_struct,显然也很麻烦,于是内核中给我们提供了slab分配机制来满足这种需求。Slab的基本思想很简单,就是自己先从伙伴系统中分配一些页面,然后把这些页面切割成一个个同样大小的基本块,用户就可以从slab中申请分配一个同样大小的内存块了。如果slab中的内存不够用了,它会再向伙伴系统进行申请。不同的slab其基本块的大小并不相同,内核的每个模块都要为自己的特定需求分配特定的slab,然后再从这个slab中分配内存。
刚开始的时候内核中就只有一个slab,其接口和实现都叫slab。但是后来内核中又出现了两个slab实现,slob和slub。slob是针对嵌入式系统进行优化的,slub是针对内存比较多的系统进行优化的,它们的接口还是slab。由于现在的计算机内存普遍都比较大,连手机的的内存都6G、8G起步了,所以现在除了嵌入式系统之外,内核默认使用的都是slub。下面我们画个图看一下它们的关系。
可以看到Slab在不同的语境下有不同的含义,有时候指的是整个Slab机制,有时候指的是Slab接口,有时候指的是Slab实现。如果我们在讨论问题的时候遇到了歧义,可以加上汉语后缀以明确语义。
3.2.1 Slab接口
下面我们来看一下slab的接口:
linux-src/include/linux/slab.h
struct kmem_cache *kmem_cache_create(const char *name, unsigned int size, unsigned int align, slab_flags_t flags, void (*ctor)(void *)); void kmem_cache_destroy(struct kmem_cache *); void *kmem_cache_alloc(struct kmem_cache *, gfp_t flags); void kmem_cache_free(struct kmem_cache *, void *);
我们在使用slab时首先要创建slab,创建slab用的是接口kmem_cache_create,其中最重要的参数是size,它是基本块的大小,一般我们都会传递sizeof某个结构体。创建完slab之后,我们用kmem_cache_alloc从slab中分配内存,第一个参数指定哪个是从哪个slab中分配,第二个参数gfp指定如果slab的内存不足了如何从伙伴系统中去分配内存,gfp的函数和前面伙伴系统中讲的相同,此处就不再赘述了,函数返回的是一个指针,其指向的内存大小就是slab在创建时指定的基本块的大小。当我们用完一块内存时,就要用kmem_cache_free把它还给slab,第一个参数指定是哪个slab,第二个参数是我们要返回的内存。如果我们想要释放整个slab的话,就使用接口kmem_cache_destroy。
3.3 Kmalloc
内存中还有一些偶发的零碎的内存分配需求,一个模块如果仅仅为了分配一次5字节的内存,就去创建一个slab,那显然不划算。为此内核创建了一个统一的零碎内存分配器kmalloc,用户可以直接请求kmalloc分配若干个字节的内存。Kmalloc底层用的还是slab机制,kmalloc在启动的时候会预先创建一些不同大小的slab,用户请求分配任意大小的内存,kmalloc都会去大小刚刚满足的slab中去分配内存。
下面我们来看一下kmalloc的接口:
linux-src/include/linux/slab.h
void *kmalloc(size_t size, gfp_t flags); void kfree(const void *);
可以看到kmalloc的接口很简单,使用接口kmalloc就可以分配内存,第一个参数是你要分配的内存大小,第二个参数和伙伴系统的参数是一样的,这里就不再赘述了,返回值是一个内存指针,用这个指针就可以访问分配到的内存了。内存使用完了之后用kfree进行释放,参数是刚才分配到的内存指针。
我们以slub实现为例讲一下kmalloc的逻辑。Kmalloc中会定义一个全局的slab指针的二维数组,第一维下标代表的是kmalloc的类型,默认有四种类型,分别有DMA和NORMAL,这两个代表的是gfp中的区域,还有两个是CGROUP和RECLAIM,CGROUP代表的是在memcg中分配内存,RECLAIM代表的是可回收内存。第二维下标代表的是基本块大小的2的对数,不过下标0、1、2是例外,有特殊含义。在系统初始化的时候,会初始化这个数组,创建每一个slab,下标0除外,下标1对应的slab的基本块大小是96,下标2对应的slab的基本块的大小是192。在用kmalloc分配内存的时候,会先处理特殊情况,当size是0的时候直接返回空指针,当size大于8k的时候会则直接使用伙伴系统进行分配。然后先根据gfp参数选择kmalloc的类型,再根据size的大小选择index。如果2n-1+1 < size <= 2n,则index等于n,但是有特殊情况,当 64 < size <= 96时,index等于1,当 128 < size <= 192时,index等于2。Type和index都确定好之后,就找到了具体的slab了,就可以从这个slab中分配内存了。
标签:__,内核,管理,GFP,内存,linux,page,define From: https://www.cnblogs.com/god-of-death/p/17436043.html