Linux内存管理

1. 概述

  • 3种地址

    逻辑地址、虚拟地址(线性地址)、物理地址

    1. 逻辑地址:机器语言指令中用来指定一个操作数或者指令的地址。每一个逻辑地址由一个段(segment)和偏移量(offset)组成。
    2. 虚拟地址:对于32位系统是一个32位的无符号整型数据
    3. 物理地址:内存芯片单元寻址,与CPU的地址引脚发送到内存总线上的电信号对应。
  • 分段与分页

    硬件MMU通过分段单元(segmentation unit)的硬件电路把一个逻辑地址转换成虚拟地址;然后分页单元(paging unit)的硬件电路把虚拟地址转换成物理地址。

    由于不同的体系结构的CPU对分段支持不同,Linux为了应对这种差异,对分段支持也就有限。下边简单介绍一下分段,主要对分页进行深入的介绍。

  • 分段

    从硬件来看,逻辑地址由2部分组成:段选择符与偏移量。段选择符是一个16位长的字段,偏移量是一个32位长的字段。为了快速的找到段选择符,CPU提供了段寄存器,包括:cs、ss、ds、es、fs、gs。这6个中3个有专门的用途:

    1. cs 代码段寄存器,cs中有2位表示CPL,0代表内核态,3代表用户态。
    2. ss 栈段寄存器
    3. ds数据段寄存器

    每个段有一个8字节的段描述符表示,它描述段的特征,是一些状态信息(段的虚拟地址Base 32位、段的大小Limit 20位、表示是在内存的P、 1位等等)。段描述符放在GDT或LDT中。

    分段单元将一个逻辑地址转换成虚拟地址,其过程如下:

    1. 根据段选择符的TI,确定GDT或者LDT
    2. 根据段选择符的index 计算段描述符地址(index*8 + GDT地址)
    3. 段描述符的Base字段 + 逻辑地址偏移量得到虚拟地址(线性地址)。
    段选择符与段描述符

    Linux以非常有限的方式使用分段,运行在内核态与用户态的进程,有各自的代码段与数据段描述符,Linux将他们的BASE地址全都设为0x00000000,这样逻辑地址的offset地址就是虚拟地址了。

  • 术语表:

    • MMU:内存控制单元
    • CPL(current Privilege Level)当前特权级别,0内核态,3用户态
    • GDT(Golbal Descriptor Table)全局描述符表
    • LDT(Local Descriptor Table)局部描述符表
    • PAE(Physical Address Extension):物理地址扩展
    • NUMA:Non-Uniform Memory Acess非一致内存访问
    • PGD(Page Global Directory):页全局目录
    • PUD(Page Upper Directory):页上级目录
    • PMD(Page Middle Directory):页中间目录
    • PTE(Page Table):页表

2. 分段与分页

概念

分段是逻辑地址到虚拟地址(线性地址)之间的转换,分页是虚拟地址到物理地址之间的转换,也是内存管理的核心。

  • 分页单元

    分页单元把虚拟地址转换成物理地址。其中一个关键任务是把所请求的访问类型与虚拟地址的访问权限相比较,如果这次内存访问无效,就产生一个缺页异常。

  • 页(page)

    虚拟地址被分成以固定长度为单位的组,成为页(page)。页内部连续的虚拟地址被映射到连续的物理地址中。页是虚拟地址的一个概念,可以理解成最小单位,页既指一组虚拟地址,又指包含这组地址中的数据。

  • 页框(page frame)

    分页单元把所有的物理内存分成固定长度的页框(page frame)。页框的长度与页的长度一致。页框是物理内存的一个存储区域。页是一个数据块,可以存放在任何页框中。有点一个萝卜一个坑的样子。

  • 页表(page table)

    把虚拟地址映射到物理地址的结构就是页表

  • 页目录表(page directory)

    内存的空间挺大,对它的寻址自然不能遍历,于是就想到了树,想到了二分法,类似B树。页表是叶子节点,页目录表是中间节点。页目录表项与页表 项相同,包括:

    字段说明
    Present标志为1表示页在主存中,为0表示不在
    页框最高位字段也就是页框的起始地址,加相应的offset得到物理地址,类似BASE
    Accessed标志分页单元对相应页框寻址时,设置这个标志。
    Dirty标志只用于页表,当页框进行写操作时,就设置这个标志
    Read/Write标志寻取权限
    Page Size标志只应用于页目录项

Linux分页机制

这里不介绍硬件的分页机制,Linux采用了一种同时适用于32位和64位系统的四级分页模型(v5+版本的内核已经是五级分页了),4种页表分别称为:

  1. 页全局目录PGD(Page Global Directory)
  2. 页上级目录PUD(Page Upper Directory)
  3. 页中间目录PMD(Page Middle Directory)
  4. 页表(Page Table)

分页机制如下:

Linux分页模型

cr3是控制寄存器,存放的是PGD的物理地址,将虚拟地址划分成不同的区域,代表不同级别页表的地址

页表

  • 进程页表

    进程的虚拟地址空间分成2部分:

    1. 从0x00000000到0xbfffffff的虚拟地址,内核态与用户态都可以寻址
    2. 从0xc0000000到0xffffffff的虚拟地址,只有内核态才能寻址
  • 内核页表

    内核维护着一组自己使用的页表,驻留在主内核页全局目录。主内核页全局目录的最高目录项是所有进程PGD对应目录项的参考模型。

    内核页表所提供的最终映射会把从0xc0000000开始的虚拟地址转换为从0开始的物理地址,当内存大于4G时,Linux映射一个896MB的RAM窗口到内核虚拟地址空间,这部分内存永久的分配给内核,用来存放内核代码以及静态内核数据结构。剩余的RAM留着不映射,由动态映射来处理,称为动态内存。

高端内存页框的内核映射

前面分页时将,将物理内存的前896MB直接映射到了虚拟地址以0xc0000000开始的第4GB的空间,而这空间只能被内核访问。这里物理内存高于896MB的ZONE_HIGHMEM管理区并没有映射在第4GB的空间,内核不能直接访问它们(32位系统)。那内核如何访问这些管理区呢?

物理内存布局

内核采用3种不同的机制将页框映射进高端内存:永久内核映射、临时内核映射、非连续内存分配。只有128MB(1024-896)的虚拟地址留给映射高端内存。永久内存映射可能阻塞当前进程,而临时内存映射并不会。

  1. 永久内核映射

    kmap()函数建立永久内核映射

    永久内核映射

    与之相对的是kunmap()撤销永久内核映射

  2. 临时内核映射

    kmap_atomic()函数

3. 物理内存分配

RAM中的某些部分永久的分配给了内核,用来存放内核代码以及静态内核数据。RAM的其余部分被成为动态内存,本节来看内核如何分配动态内存。

3.1 页(框)分配

物理内存组织

内存管理子系统使用节点(node)、区域(zone)和页(page)三级结构描述物理内存。

  • 节点(node)

    在NUMA(非一致内存访问)模型中,给定CPU对不同内存单元的访问时间可能不一样。系统的物理内存被划分为几个节点(Node),在单独的节点内,CPU访问页面所需的时间是相同的(均匀的),对于不同CPU这个时间可能不同。对于CPU,内核试图把耗时节点的访问次数降到最低。

    每个Node都有一个pg_data_t的节点描述符与之对应,所有节点描述符放到pgdat_list单向链表中。
    每个Node中的物理内存,又分成几个管理区(Zone)。

    如果不需要NUMA,Linux还是会使用节点,只不过链表就一个节点,包含了系统中所有的物理内存。

    内存节点使用pglist_data(pg_data_t)结构体来描述,内核定义了宏NODE_DATA(nid),来获取节点的pglist_data实例。

    typedef struct pglist_data {
    	struct zone node_zones[MAX_NR_ZONES];				// 内存zone数组,见下
    	struct zonelist node_zonelists[MAX_ZONELISTS];	// 备用区域列表
    	int nr_zones;																			// node中包括的内存zone数量
    #ifdef CONFIG_FLAT_NODE_MEM_MAP	
    	struct page *node_mem_map;								// 页描述符数组
    #ifdef CONFIG_CGROUP_MEM_RES_CTLR
    	struct page_cgroup *node_page_cgroup;		// 页的扩展属性
    #endif
        ...
    	unsigned long node_start_pfn;						// 该节点的起始物理页号
    	unsigned long node_present_pages; 			// 物理页总数
    	unsigned long node_spanned_pages; 		 // 物理页范围的总长度,包括空洞
    	int node_id;															// node标识符
    	...
    } pg_data_t;
    
  • 内存区域(zone)

    Linux把每个内存节点的物理内存划分为3个管理区Zone:

    • ZONE_DMA:低于16MB的内存页框
    • ZONE_NORMAL:高于16MB,且低于896MB的内存页框
    • ZONE_HIGHMEM:大于等于896MB的内存页框。

    ZONE_DMA与ZONE_NORMAL会直接映射到虚拟地址空间的的第4个GB(0xc0000000起),内核可以直接访问。ZONE_HIGHMEM不能由内核直接访问。

    与节点类似,区也有自己的描述符zone

    以上为32位的情况,内核地址空间只有1G,对于64位,由于虚拟地址空间足够大,不再如此,它的如下:

    • ZONE_DMA 与 ZONE_DMA32,基本同上
    • ZONE_NORMAL,直接映射到虚拟内存地址空间的内存区域
    • ZONE_HIGHMEM,32位时使用的,64位不再需要高端内存区域
    • ZONE_MOVABLE,伪内存区域,用来方式内存碎片化,本文暂不涉及
    • ZONE_DEVICE,为支持持久内存热插拔增加的内存区域

    每个内存区域用zone结构体描述,如下:

    struct zone {
    	unsigned long watermark[NR_WMARK];			// 页分配器使用的水线
        ...
    	unsigned long		lowmem_reserve[MAX_NR_ZONES];		// 页分配器使用,当前区域保留多少页不能借给高的区域类型
    	...
    	struct per_cpu_pageset __percpu *pageset;		// 每处理器页集合
        ...
    	struct free_area	free_area[MAX_ORDER];		// 不同长度的空闲区域
    	...
    	struct pglist_data	*zone_pgdat;			// 指向内存节点node的示例
    	unsigned long		zone_start_pfn;			// 当前区域的起始物理页
    
    	unsigned long		spanned_pages;		// 当前区域跨越的总页数,包括空洞
    	unsigned long		present_pages;		// 当前区域存在的物理页数量,不包括空洞
    
    	const char		*name;			// 区域名称
    };
    
  • 物理页(page)

    内核必须记录每个页框当前的状态,如:内核必须能区分哪些页框包含的是属于进程的页,而哪些页框包含的是内核代码或内核数据。页框的状态保存在页描述符page中,所有的页描述符存放在mem_map数组中.

    struct page {
    	/* First double word block */
    	unsigned long flags;	
    	struct address_space *mapping;	
    	...
        atomic_t  _mapcount;	// 页框中的页表项数目
        ...
        atomic_t  _count;			// 页框的引用计数器
       ...
        struct page *next;			/* Next partial slab */
      	int pages;		/* Nr of partial slabs left */
      	int pobjects;	/* Approximate # of objects */
        ...
    	struct kmem_cache *slab;	/* SLUB: Pointer to slab */
    	struct page *first_page;	/* Compound tail pages */
    }
    
  • 页框分配机制

    分区页框分配器用于处理对连续页框组的内存分配请求,如下图:

    1. 管理区分配器接收动态内存分配与释放的请求,在请求分配的情况下,搜索一个能满足所请求的一组连续页框内存的管理区
    2. 在每个管理区内,通过伙伴算法来分配页框。
    3. 为达到更好的系统性能,一小部分页框保留在高速缓存中,用于快速的满足对单个页框的分配请求。

    下边分别来看看它们。

管理区分配器

管理区分配器是内核页框分配器的前端,它需要满足几个目标:

  1. 它应当保护保留的页框池(ps:本位没暂未涉及)
  2. 当内存不足且允许阻塞当前进程时,它应到触发页框回收算法,一旦某些页框被释放,再次尝试分配。
  3. 如果可能,应到保存小而珍贵的ZONE_DMA内存管理区。

管理区分配器通过前边提到的alloc_pages宏来处理对页框的分配:

管理区分配器同样负责释放框,它同样也依赖前面提到的__free_pages()来实现的,这里就不再赘言。

ps:有6个函数来请求页框:

函数(宏)描述
alloc_pages(gfp_mask, order)请求2^order个连续页框,返回一个page *
alloc_page(gfp_mask)获取一个单独的页框
__get_free_pages(gfp_mask, order)与alloc_pages类似,但返回一个所分配页框的虚拟地址char*
__get_free_page(gfp_mask)与alloc_page类似
get_zerod_page(gfp_mask)获取1个填满0的页框,返回页框的虚拟地址
__get_dma_pages(gfp_mask, order)从DMA中获取,返回页框的虚拟地址

gfp_mask可以指明从哪个分区获取,以及其他一些信息。

还有4个释放页框:

函数(宏)描述
__free_pages(page, order)page指向页描述符,引用计数-1,至0释放2^order个页框
free_pages(addr, order)同上,参数如addr
__free_page(page)释放1个
free_page(addr)释放1个,参数入为地址

伙伴分配算法

频繁的请求和释放不同大小的一组连续页框,必然导致在已分配页框的块内分散着很多小块的空闲页框,这就是所谓的外部碎片化的问题。内核通过伙伴算法,尽量避免为小块的请求而分割大的空闲块的方式,尽量避免碎片化。

描述如下:

把所有的空闲页框分组为11个块链表,每个块链表中的块分别包含大小为1,2,4,8,16,32,64,128,256,512,1024个连续的页框。1024个页框也就是4MB大小的连续空间。每个块的第一个页框的物理地址,是该块大小的整数倍。例如16个页框的块,其起始地址是16*4096( 4096 页框大小 )的倍数。

  • 假设申请256个页框的块(1MB),算法先在256的页框链表中查询是否有空闲的块。
  • 如果没有查询下一个更大的块,也就是512的页框的链表。如果存在就把512分成2个256,1个用于满足请求,另1个插入到256个页框的链表中。
  • 依次类推,直到1024(拆成512+256),如果还没有找到,则放弃并发出错信号。

逆过是页框释放的过程,也是该算法名字的由来。内核试图把大小为a的2个空闲块合并为1个大小为2a的单独快。

  • 两个块具有相同大小,a
  • 它们的物理地址是连续的
  • 第一个块的第一个页框的物理地址是2 * a * 4096的倍数

ps: 碎片是绝对的,逆碎片是相对的。

在这3.2版本的流程如下:

每CPU页高速缓存

内核经常请求和释放当个页框,为了提升系统性能,每个内存管理区定义了一个“每CPU”页框高速缓存,所有高速缓存包含一些预分配的页框,用于满足对单一内存的请求。

CPU页高速缓存的主要结构是存放在zone中的pageset字段中,里边主要结构是per_cpu_pages

struct per_cpu_pages {
	int count;		/* number of pages in the list */
	int high;		/* high watermark, emptying needed */
	int batch;		/* chunk size for buddy add/remove */

	/* Lists of pages, one per migrate type stored on the pcp-lists */
	struct list_head lists[MIGRATE_PCPTYPES];
};

本质是一个page的链表,这些page是从伙伴系统中分配来的,batch是每次从伙伴系统分配或回归的页框个数。 在v3.2版本的内核中,只有high一个位标,v2.6x版本中还有一个low标。

从页高速缓存中分配函数是buffered_rmqueue();释放函数是free_hot_cold_page(),这里暂不做深入的分析。

3.2 slab块分配

概念

  • slab分配器

    伙伴分配算法采用页框作为基本内存区,这适合对大块内存的请求,如何处理对小内存区的请求呢?如几十或几百个字节。

    早期的解决方案是提供几何分布的内存区大小,内存区大小取决于2的幂而不取决于所存放的数据。这个与伙伴算法类似。一种更好的算法被称为slab分配器算法。

    高速缓存的主内存区被划分为多个slab,每个slab由一个或多个连续的页框组成,每个slab都存储同种类型的对象。

    slab分配在某些情况下表现不太好,后来的Linux版本中提供了2个改进的块分配器:SLUB分配器与SLOB分配器。SLUB抛弃了效果不明显的slab着色,这里也不对着色进行介绍。

  • 高速缓存描述符

    在本版本中,每个高速缓存都是由kmem_cache类型来描述的。

    struct kmem_cache {
    /* 1) Cache tunables. Protected by cache_chain_mutex */
    	unsigned int batchcount;	// 进出本地高速缓存的大批对象的数量
    	unsigned int limit;		// 本地高速缓存中空闲对象的最大数目
    	unsigned int shared;
    	unsigned int buffer_size;
    	u32 reciprocal_buffer_size;
    
    /* 2) touched by every alloc & free from the backend */
    	unsigned int flags;			/* constant flags */
    	unsigned int num;			// 一个单独slab中的对象个数
    
    /* 3) cache_grow/shrink */
    	unsigned int gfporder;		// 一个lab包含的连续页框数目的次幂
    	gfp_t gfpflags;			// 分配页框时,传递给伙伴系统函数的一组标志
    	size_t colour;			//  slab使用的颜色个数 
    	unsigned int colour_off;	 //  colour offset
    	struct kmem_cache *slabp_cache;		
    	unsigned int slab_size;		// 单个slab的大小
    	unsigned int dflags;		/* dynamic flags */
    	void (*ctor)(void *obj);
    
    /* 4) cache creation/removal */
    	const char *name;
    	struct list_head next;			// 高速缓存描述符双向链表使用的指针
        ...
    /* 6) per-cpu/per-node data, touched during every alloc/free */
    	struct kmem_list3 **nodelists;					// 这里存放着各个slabs
    	struct array_cache *array[NR_CPUS];			// 每CPU指针数组,指向包含空闲对象的本地高速缓存
    };
    

    这个kmem_list3中有:slabs_full全满、slabs_free全空、slabs_partial半满的3个链表,不同状态的slab在不同的链表中。

  • slab描述符

    高速缓存中每个slab都有自己的slab描述符:

    struct slab {
    	union {
    		struct {
    			struct list_head list;				// slab描述符的3个双向循环链表中的一个
    			unsigned long colouroff;		// slab中第一个对象的偏移
    			void *s_mem;		// slab中第一个对象的地址
    			unsigned int inuse;	 // 当前正在使用的slab中的对象个数
    			kmem_bufctl_t free;				// slab中下一个空闲对象的下标
    			unsigned short nodeid;
    		};
    		struct slab_rcu __slab_cover_slab_rcu;
    	};
    };
    

    每个对象都有类型为kmem_bufctl_t的描述符,它是一个无符号的整型。对象描述符存放在一个数组中,含义是下一个空闲对象在slab中的下标,实现了slab内部空闲对象的一个简单链表功能,空闲对象链表中的最后一个元素通常用BUFCTL_END(0Xffff)标记。

    s_mem指向第一个对象的地址,free指向空闲对象的下标。

    页高速缓存描述符kmem_cache与slab描述符slab的关系如下图所示:

本图是slub的,与上边的结构不完全相符;

高速缓存创建与销毁

  • 高速缓存的创建与销毁

    高速缓存被分成2种:普通和专用。普通高速缓存只用于slab分配器,而专用的高速缓存由内核的其余部分使用。

    在系统初始化期间,调用kmem_cache_init()和kmem_cache_sizes_init()来建立普通高速缓存;

    专门高速缓存由kmem_cache_create()函数创建。

    通过kmem_cache_destroy()销毁一个高速缓存。

  • slab分配器与页框分配器的接口

    当slab分配器创建新的slab时,它依靠分区页框分配器来获得一组连续的空闲页框,函数是kmem_getpages(),释放该页框的函数是kmem_freepages.

slab的分配、释放

一个新创建的高速缓存没有包含任何slab,因此也没有空闲的对象,只有当以下两个条件都为真是,才会给高速缓存分配slab:

  1. 已发出一个分配新对象的请求
  2. 高速缓存不包含任何空闲对象

其函数是cache_grow()

kmem_getpages()获取页框,alloc_slabmgmt()分配slab描述符,cache_init_objs()将构造函数应用到新slab包含的所有对象上。

释放slab也有2个条件:

  1. slab高速缓存中有太多的空闲对象
  2. 被周期性调用的定时器函数确定是否有完全未使用的slab能释放

其函数是:slab_destroy()

页高速缓存分配与释放slab

对象管理

  • slab对象的分配与释放

    通过kmem_cache_alloc()函数来获得新的对象,参数cachep指向高速缓存描述符,新对象必须从此处分配。

    通过kmem_cache_free()函数来释放一个由slab分配器分配给某个内核函数的对象,它的参数是cachep和objp。

  • 空闲对象的本地高速缓存

    kmem_cache中,最后一个字段是array,它是array_cache结构体数组,用于每个CPU缓存空闲的对象,对象大多数的分配和释放在这里完成,只有在本数组下溢或上溢时,才会涉及slab结构体。这个结构体如下:

    struct array_cache {
    	unsigned int avail;		// 可使用对象指针的个数
    	unsigned int limit;		// 对象的最大个数
    	unsigned int batchcount;	// 批量映射的古树
    	unsigned int touched;		// 
    	spinlock_t lock;
    	void *entry[];	
    };
    

    它与每CPU页高速缓存的结构类似,页高速缓存用于缓存对单独页框的申请,本地高速缓存用于缓存对对象的申请。

  • 通过对象

    通用对象通过kmalloc()函数进程申请,通过kfree()进行释放。

内存池

内存池通常叠加在slab分配器之上,用来保留slab对象,内存池能用来分配任何一种类型的动态内存,从整个页框到使用kmalloc()分配的小内存。

内存池对象由mempool_t描述:

typedef struct mempool_s {
	spinlock_t lock;
	int min_nr;		/* nr of elements at *elements */
	int curr_nr;		/* Current nr of elements at *elements */
	void **elements;	// 指向一个数组的指针,该数组由指向保留元素的指针组成

	void *pool_data;					//  池的拥有者可获得的私有数据
	mempool_alloc_t *alloc;		// 分配一个元素的的方法
	mempool_free_t *free;		// 释放一个元素的方法
	wait_queue_head_t wait;		// 当内存池为空时使用的等待队列
} mempool_t;

内存池由mempool_create()函数创建,alloc一般是mempool_alloc_slab(),free一般是mempool_free_slab()。

内存池是v2.6引入的特性。

3.3 非连续内存区管理

从PAGE_OFFSE(oxc0000000)开始的第4个GB的虚拟地址空间:

图中各部分如下:

  1. 开始部分是第896MB RAM进行映射的虚拟地址(物理内存映射)。
  2. 内存区的结尾包含的是固定映射的虚拟地址
  3. 从PKMAP_BASE开始用于高端内存页框的永久内核映射的虚拟地址
  4. 非连续内存区线性内存。在物理内存映射的末尾与第一个内存区之间插入8MB的安全区,用于捕获对内存的越界访问,同样插入其他4KB的安全区来隔离非连续的内存区。从VMALLOC_START到VMALLOC_END。

非连续内存的描述符

struct vm_struct {
	struct vm_struct	*next;		
	void			*addr;			// 内存区第一个内存单元的虚拟地址
	unsigned long		size;	// 内存去的大小 + 4KB(安全区)
	unsigned long		flags;		// 非连续内存区映射的内存的类型
	struct page		**pages;	// 指向数组的指针,该数组由页框描述符的指针组成
	unsigned int		nr_pages;	// 以上数组的个数,也就是内存区中页框的个数
	phys_addr_t		phys_addr;	// 该字段设为0,除非内存已被创建来映射一个硬件设备的I/O共享内存
	void			*caller;		// 指向下一个vm_struct结构的指针
};

获取非连续内存描述符

通过get_vm_area()函数在虚拟地址VMALLOC_START和VMALLOC_END之间查找一个空闲的区域,如过程如下:

非连续内存区的分配与释放

  • 分配非连续内存区

    分配非连续内存通过vmalloc()函数来完成,参数size表示所请求内存区的大小。其调用栈如下:

    __get_vm_area_node()用于获取非连续区描述符,相当于获取虚拟地址; alloc_pages_node()通过__alloc_pages()来获取页框;map_vm_area()是将虚拟地址与页框(物理地址)进行映射。

    除了vmalloc()之外,还提供了vmap()函数,它将映射非连续内存区中已分配的页框,这里不细讲了。

  • 释放非连续内存区

    释放非连续去通过vfree()函数,它对应vmalloc(),另外vunmap()函数释放vmap()。

    remove_vm_area()得到vm_struct描述符,并清除非连续内存区中的虚拟地址对应的页表项;

    kfree()来释放vm_struct描述符。

4. 进程地址空间分配

进程虚拟地址空间

进程的地址空间由允许进程使用的全部虚拟地址组成,每个进程所看到的虚拟地址集合是不同的,一个进程所使用的地址与另外一个进程所使用的地址之间没有关系,相互独立。内核可以通过增加、删除某些虚拟地址空间来动态修改进程的地址空间。如:

  1. exec函数装入一个完全不同的程序,装入之前的线性区被释放,一组新的线性区分配。
  2. 正在运行的进程可能对一个文件执行“内存映射”,内核会给这个进程分配一个新的线性区来映射这个文件。
  3. 进程可能持续想用户态的栈增加数据,指导这个栈的线性区用完,这种情况,内核也许会扩展这个线性区的大小。
  4. 通过调用malloc()函数来扩展自己的动态区(堆)。

这一部分主要是进程虚拟内存的分配,以及虚拟内存与物理内存的映射。

来看看内存的虚拟地址空间

32位如下:

64位进程由于有足够的地址空间了,不在如此。根据不同的配置64位虚拟地址的宽度可以不同。这里以48位为例。

内核空间与地址空间各使用高低48位的空间。

内存映射

内存映射是在进程的虚拟地址空间中创建一个映射,分为以下两种。

  1. 文件映射:文件支持的内存映射,把文件的一个区间映射到进程的虚拟地址空间,数据源是存储设备上的文件。
  2. 匿名映射:没有文件支持的内存映射,把物理内存映射到进程的虚拟地址空间,没有数据源。

通常把文件映射的物理页称为文件页,把匿名映射的物理页称为匿名页。

两个进程可以使用共享的文件映射实现共享内存。匿名映射通常是私有映射,共享的匿名映射只可能出现在父进程和子进程之间。
在进程的虚拟地址空间中,代码段和数据段是私有的文件映射,未初始化数据段、堆和栈是私有的匿名映射。

内存映射的原理如下:

  1. 创建内存映射的时候,在进程的用户虚拟地址空间中分配一个虚拟内存区域。
  2. Linux 内核采用延迟分配物理内存的策略,在进程第一次访问虚拟页的时候,产生缺页异常。如果是文件映射,先分配物理页,然后把文件指定区间的数据读到物理页中,最后在页表中把虚拟页映射到物理页;如果是匿名映射,先分配物理页,然后在页表中把虚拟页映射到物理页即可。

线性区(虚拟地址)

  • 线性区结构图

    内核频繁执行的一个操作是查找包含指定虚拟地址的线性区,链表的复杂度是o(n),与线性区的多少相关,对于普通进程,线性区的使用非常少,但对于像数据库这种进程,使用的线性区会非常多,o(n)就不能满足需求了。于是就使用了红黑树来加快查找速度。

    因此为了存放进行的线性区,Linux既使用链表,也使用了红黑树。这两种数据结构包含指向同一线性区描述符的指针,当插入或删除一个线性区描述符时,内核通过红黑树查询前后元素,快速更新链表而不用扫描链表。

    链表的表头由mm_struct中的mmap字段所指向,所有的vm_area_struct都在vm_next字段存放指向链表下一个元素的指针。

    红黑树的首部由mm_struct中的mm_rb字段指向,所有的vm_area_struct在vm_rb中存放节点颜色、parent、左、右孩子。

  • 内存描述符

    与进程地址空间有关的信息都在mm_struct中,如下:

    struct mm_struct {
    	struct vm_area_struct * mmap;		// 指向线性区对象的链表头
    	struct rb_root mm_rb;						// 指向线性区对象的红黑树根
    	struct vm_area_struct * mmap_cache;	 // 指向最后一个引用的线性区对象
    #ifdef CONFIG_MMU
    	unsigned long (*get_unmapped_area) (struct file *filp,
    				unsigned long addr, unsigned long len,
    				unsigned long pgoff, unsigned long flags);			// 在进程虚拟地址空间,寻找有效虚拟地址空间的方法
    	void (*unmap_area) (struct mm_struct *mm, unsigned long addr);	// 释放虚拟地址空间的方法
    #endif
    	unsigned long mmap_base;		// 标记第一个分配的匿名线性区虚拟地址
    	unsigned long task_size;		/* size of task vm space */
    	unsigned long cached_hole_size; 	/* if non-zero, the largest hole below free_area_cache */
    	unsigned long free_area_cache;		// 从这个地址开始搜索进程地址空间中空闲区间
    	pgd_t * pgd;							// 页全局目录
    	atomic_t mm_users;			// 使用计数How many users with user space? 
    	atomic_t mm_count;			// 使用计数How many references to "struct mm_struct" (users count as 1) 
    	int map_count;				// 线性区的个数
    
    	spinlock_t page_table_lock;			// 页表与线性区的自旋锁 
    	struct rw_semaphore mmap_sem;
    	struct list_head mmlist;	// 指向内存描述符链表中的相邻元素
    	unsigned long hiwater_rss;	// 进程拥有的最大页框数/* High-watermark of RSS usage */
    	unsigned long hiwater_vm;	// 进行线性空间中最大页数 /* High-water virtual memory usage */
    
    	unsigned long total_vm;			// 进程地址空间的大小 /* Total pages mapped */
    	unsigned long locked_vm;	// 锁住而不能换出的页个数 /* Pages that have PG_mlocked set */
    	unsigned long pinned_vm;	/* Refcount permanently increased */
    	unsigned long shared_vm;	// 共享文件内存映射中的页数 /* Shared pages (files) */
    	unsigned long exec_vm;		// 可执行内存映射中的页数 /* VM_EXEC & ~VM_WRITE */
    	unsigned long stack_vm;		// 用户态堆栈中的页数 /* VM_GROWSUP/DOWN */
    	unsigned long reserved_vm;	// 在保留区中的页数 或 特殊线性区中页数/* VM_RESERVED|VM_IO pages */
    	unsigned long def_flags;		// 线性区默认的访问标志
    	unsigned long nr_ptes;		// 进程的页表数 /* Page table pages */
    	unsigned long start_code, end_code, start_data, end_data;		// 代码段与数据段的起止位置
    	unsigned long start_brk, brk, start_stack;		// 堆的起始位置、当前位置、用户栈的起始位置
    	unsigned long arg_start, arg_end, env_start, env_end;		// 命令行参数的起止位置、环境变量的起止位置
    
    	unsigned long saved_auxv[AT_VECTOR_SIZE];  // 执行ELF程序时使用
    	struct mm_rss_stat rss_stat;
    	struct linux_binfmt *binfmt;
    	cpumask_var_t cpu_vm_mask_var; // 懒惰TLB交换的位掩码
    	mm_context_t context;				// 指向有关特定体系结构信息的表
    	...
    	unsigned long flags; /* Must use atomic bitops to access the bits */
    	struct core_state *core_state; /* coredumping support */
    #ifdef CONFIG_AIO
    	spinlock_t		ioctx_lock;				// 保护异步io上下文链表的锁
    	struct hlist_head	ioctx_list;		// 异步io上下文链表
    #endif
        ...
    };
    

    所有的内存描述符存放在一个双向链表中,每个mmlist字段存放链表相邻的元素地址。链表的第一个元素是初始化进程0使用的内存描述符。

    mm_users是使用这个进程地址空间的线程的个数;mm_count是mm_struct的引用计数。

    假设有2个线程,mm_users为2,mm_count为1(两个线程是一个单位)。当mm_users递减到0,mm_count减1,当mm_count等于0,mm_struct将释放。

  • 内核线程的内存描述符

    内核线程仅运行在内核态,它们永远不会访问低于TASK_SIZE(0xc0000000)的地址,与普通进程相反,内核线程不适用线性区,mm_struct中很多字段对内核线程没有意义。

    因为大于TASK_SIZE虚拟地址的相应页表项总是相同的,因此一个内核线程可以使用任何mm_struct。内核线程总是使用一组最近运行的普通进程的mm_struct。

    在进程描述符中,总是包含2个mm_struct:mm与active_mm。mm字段指向进程所拥有的内存描述符,而active_mm字段指向进程运行时所使用的内存描述符。对于普通进程这两个字段相同,对于内核线程mm总是为NULL,当内核线程得以运行时,它的active_mm初始或成前一个运行进程的active_mm值。

    只要处于内核态的一个进程为高端虚拟地址(高于TASK_SIZE)修改也页表项,那么也应到更新系统中所有进程页表集合中的响应表象,也就是对内核态的所有进程都有效。触及所有进程的页表集合是费时操作,Linux采用一种延迟方式。

  • 线性区描述符

    Linux通过vm_area_struct的对象实现线性区,定义如下:

    struct vm_area_struct {
    	struct mm_struct * vm_mm;	// 指向线性区所在的内存描述符
    	unsigned long vm_start;		// 线性区内的第一个虚拟地址
    	unsigned long vm_end;		// 线性区之后的第一个虚拟地址
    
    	struct vm_area_struct *vm_next, *vm_prev;	// 进程链表中的下一个线性区与上一个线性区
    
    	pgprot_t vm_page_prot;		// 线性区中页框的访问许可权
    	unsigned long vm_flags;		// 线性区的标志
    
    	struct rb_node vm_rb;	// 用于红黑树的数据
    
    	union {
    		struct {
    			struct list_head list;
    			void *parent;	/* aligns with prio_tree_node parent */
    			struct vm_area_struct *head;
    		} vm_set;
    
    		struct raw_prio_tree_node prio_tree_node;
    	} shared;		// 连接到反映射使用的数据结构
    
    	struct list_head anon_vma_chain; // 指向匿名线性区链表的指针
    	struct anon_vma *anon_vma;	// 指针,以上都由于映射页的反向映射
    
    	/* Function pointers to deal with this struct. */
    	const struct vm_operations_struct *vm_ops;
    
    	unsigned long vm_pgoff;		//  在映射文件中的偏移量
    	struct file * vm_file;		//  指向映射文件的文件对象
    	void * vm_private_data;		// 指向内存区的私有数据 was vm_pte (shared mem) */
    
    #ifndef CONFIG_MMU
    	struct vm_region *vm_region;	/* NOMMU mapping region */
    #endif
    #ifdef CONFIG_NUMA
    	struct mempolicy *vm_policy;	/* NUMA policy for the VMA */
    #endif
    };
    

    进程所拥有的线性区从来不重叠,并且内核尽力把新分配的线性区与紧邻的现有线性区进行合并。如果两个相邻区的访问权限相匹配,就把他们合并到一起。

  • 线性区访问权限

    线性区由一组号码连续的页所构成。前边已经介绍了与页相的2种标志了:在页表项中的几个标志,如:Read/Write、Present或User/Supervisor;存放在每个页(框)描述符(page)中flag标志

    这里介绍第3种,线性区vm_area_struct中的vm_flags字段:

    标志名说明标志名说明
    VM_READ页是可读VM_LOCKED线性区中的被锁住,不能换出
    VM_WRITE页是可写VM_IO线性区映射设备的IO地址空间
    VM_EXEC页是可执行VM_SEQ_READ应用程序顺序访问页
    VM_SHARED页可以由几个进程共享VM_RAND_READ应用程序以真正的顺序访问页
    VM_GROWSDOWN线性区可以向低地址扩展VM_HUGETLB通过扩展分页机制处理线性区中的页
    VM_GROWSUP线性区可以向高地址扩展VM_NONLINEAR实现非线性文件映射
    VM_SHM线性区用于IPC的共享内存

    页表标志的初始值存放在vm_area_struct描述符的vm_page_prot字段中,当增加一个页时,内存根据vm_page_prot字段的值设置相应页表项中的标志,但并不是直接设置成该标志的。

线性区的基本操作

  • 查找给定地址的最邻近区: find_vma()

    find就是红黑树的查询,代码如下:

    struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
    {
    	struct vm_area_struct *vma = NULL;
    
    	if (mm) {
    		vma = mm->mmap_cache;
    		if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
    			struct rb_node * rb_node;
    
    			rb_node = mm->mm_rb.rb_node;
    			vma = NULL;
    
    			while (rb_node) {
    				struct vm_area_struct * vma_tmp;
    
    				vma_tmp = rb_entry(rb_node,
    						struct vm_area_struct, vm_rb);
    
    				if (vma_tmp->vm_end > addr) {
    					vma = vma_tmp;
    					if (vma_tmp->vm_start <= addr)
    						break;
    					rb_node = rb_node->rb_left;
    				} else
    					rb_node = rb_node->rb_right;
    			}
    			if (vma)
    				mm->mmap_cache = vma;
    		}
    	}
    	return vma;
    }
    
  • 查找一个与给定地址区间相重叠的线性区:find_vma_intersection()

    static inline struct vm_area_struct * find_vma_intersection(struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr)
    {
    	struct vm_area_struct * vma = find_vma(mm,start_addr);
    
    	if (vma && end_addr <= vma->vm_start)
    		vma = NULL;
    	return vma;
    }
    

    ps:这个if判断的用处有点疑问

  • 查找一个空闲的地址空间:get_unmapped_area()

    get_unmapped_area()搜查进程的地址空间,以找到一个可以使用的虚拟地址空间。

    这里用了函数指针调用的的,是一种多态方式。

    unsigned long
    get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
    		unsigned long pgoff, unsigned long flags)
    {
    	unsigned long (*get_area)(struct file *, unsigned long,
    				  unsigned long, unsigned long, unsigned long);
    
    	unsigned long error = arch_mmap_check(addr, len, flags);
    	if (error)
    		return error;
    
    	/* Careful about overflows.. */
    	if (len > TASK_SIZE)
    		return -ENOMEM;
    
    	get_area = current->mm->get_unmapped_area;
    	if (file && file->f_op && file->f_op->get_unmapped_area)
    		get_area = file->f_op->get_unmapped_area;
    	addr = get_area(file, addr, len, pgoff, flags);
    	if (IS_ERR_VALUE(addr))
    		return addr;
    
    	if (addr > TASK_SIZE - len)
    		return -ENOMEM;
    	if (addr & ~PAGE_MASK)
    		return -EINVAL;
    
    	return arch_rebalance_pgtables(addr, len);
    }
    

    函数根据虚拟地址空间是否应用用于文件内存映射或匿名内存映射,调用两个方法分别是file的get_unmapped_area与内存描述符mm的get_unmapped_area。后者由arch_get_unmapped_area()实现。

  • 向内核描述符链表插入一个线性区: insert_vm_struct()

    这个调用栈如下图所示:

    find_vma_prepare()在红黑树mm->mm_rb中查找vma应该位于何处。

    __vma_link_list()vma插入到链表中;__vma_link_rbvma插入到红黑树中。

  • 分配虚拟地址空间

    do_mmap()函数为当前进程创建并初始化一个新的线性区。在分配成功之后,可以把这个新的线性区与进程已有的其他线性区进行合并。其调用栈如下:

    这里边根据标识有着很多的处理do_mmap_pgoff()先调用上边的get_unmapped_area()获得新的线性区间,如果获取到,就返回。否则就执行mmap_region()。

    find_vma_prepare()确定新区间之间的线性对象的位置,以及在红黑树中新线性区的位置。

    vma_merge试图把它与随后的线性区进行合并,如果成功则跳出。

    kmem_cache_zalloc()是调用slab分配函数kmem_cache_alloc为新线性区分配一个vm_area_struct(vma)的数据结构,接着是对这个vma对象的初始化

    vma_link把新线性区插入到线性区链表和红黑树中,然后增加mm中total_vm字段的进程地址空间的大小。

    如果有VM_LOCKED标志,会调用make_pages_present,分配线性区的所有页。

  • 释放虚拟地址区间

    do_munmap()与do_mmap()相反的操作,它释放了虚拟地址空间。其调用栈如下:

    通过find_vma()找到要删除的vma;

    根据起止地址进行判断,如果删除的空间在一个vma的中间,会调用__split_vma()将原来的vma进行切分;

    detach_vmas_to_be_unmapped()从进程地址空间中删除位于虚拟地址空间中的线性空间。

    unmap_region()清楚与虚拟地址区间对应的页表项,并释放相应的页框。

    remove_vma_list()更新一些统计信息,并释放vma占用的内存。

缺页异常处理程序

linux的缺页异常处理程序必须区分2种情况:有编程错误所引起的异常,及由引起属于进程地址空间但还尚未分配物理页框的页所引起的异常。

do_page_fault()函数是x86上的缺页中断服务程序,负责处理缺页异常。这块的代码还主要是判断的条件比较多,其流程图(v2.6)如下:

适合分页的也就是请求分页那一块:地址在线性区内,读请求页不存在,或者写请求,会进行请求分页或写时复制。

其代码的调用栈如下:

对于页的分配是在handle_mm_fault()中完成的。

  • 请求调页

    请求调页是一种动态内存分配技术,它把页框的分配推迟到不能再推迟为止,知道进程要访问的页不在RAM中位置,由此引起一个缺页异常。

    进程在开始运行的时候并不访问其地址空间中的全部地址,甚至有一部分地址永远也不会被使用。这样请求调页能更好的使用空闲内存。

  • 写时复制

    写实复制就是在父子进程复制完成之后,它们共享页框而不是复制页框,只要页框被共享,它们就不能被修改。无论父子进程何时试图写一个共享的页框,这是就产生一个异常,这时内核就把页复制到一个新的页框中,并标记为可写。这是原来页框仍是写保护,当其他进程试图写入时,内核检查写进程是否是页框唯一的属主,如果是,把这个页框标记为可写。

进程地址空间的创建与删除

  • 创建地址空间

    创建进程的地址空间是在copy_mm()中完成,而它是在fork、clone等中被调用。对于Linux线程(CLONE_VM标志),它们共享同一地址空间,允许对同一组页进行寻址,这样copy_mm()也比较简单。对于fork进程情况,就需要进行一系列的准备操作了,如下图所示:

    如果是线程,则增加mm_users即可;

    如果是进程,dup_mm()创建一个新的地址空间,创建一个新的内存描述符mm,然后调用memcpy将旧的mm拷贝到新的mm中;对于依赖体系结构的事情,由init_new_context()来完成;最后dup_mmap()函数既复制父进程的线性区,也复制父进程的页表。

  • 释放地址空间

    当进程结束,内核调用exit_mm()释放进程的地址空间。

    设置一个core_thread,通过schedule()重新调度,将内存卸载到一个转储文件中;

    并且增加了内存描述符的mm_count,这一点有点疑惑;

    最后调用mmput()释放了局部描述符表、线性区描述符和页表。

堆的管理

每个进程都有一个特殊的线性区heap,用于满足对动态内存的申请。内存描述符的start_brk与brk分别限定了这个区的开始与结束地址。这里简单总结一下API。

api描述
malloc(size)请求size个字节的动态内存
calloc(n, size)请求含有n个大小为size的数组
realloc(ptr, size)改变前2个函数分配内存区字段的大小
free(addr)释放malloc、calloc分配的地址为addr的线性区
brk(addr)直接修改堆的大小,addr参数指定current -> mm -> brk的新值
sbrk(incr)与brk类似,incr指定减小或增大的以字节为单位的堆大小

5. 后记

本文主要参考《深入理解Linux内核》中内存管理的章节,以及《Linux内核深度解析》相关章节的部分内容。

本文的主线有2条,其一是物理内存与虚拟内存的关系,其二是内核与进程内存使用的差异。

从Linux内核深度解析可以看到,内存管理还有几个比较重要的部分,包括巨型页、反碎片技术、页回收等,这些也可以在本文基础上深入,本文暂不进行整理,以后会对它们进行学习。
整个的内存相关的内容如下:

# Linux 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×