Linux内核设计与实现(12)---内存管理

内存管理，个人感觉应该是内核里最复杂的一部分了，目前还没做这方面相关的工作，因此没打算深究，只学点皮毛，搞懂点基本原理，以便更好理解OS的其他部分吧。

1.页

内核把物理页作为内存管理的基本单位(MMU是以页为单位处理)，体系结构不同，支持的页大小也不尽相同，大多数32位体系结构是4KB页，64位体系结构8KB页。

内核用struct page结构表示系统中的每个物理页(几个重要域)

struct page {
    unsigned long         flags;
    atomic_t              _count;
    atomic_t              _mapcount;
    unsigned long private;
    struct address_space *mapping;
    pgoff_t               index;
    struct list_head      lru;
    void *virtual;
};

flags:存放页的状态，比如页是不是脏的，是否被锁定在内存中等。

_count:存放页的引用计数，当计数为-1时表示当前内核并没有引用该页。检查引用计数用page_count()函数，当返回0时表示页空闲。

virtual:是页的虚拟地址，有些内存（比如高端内存）并不永久映射到内核地址空间，这时域值为NULL,需要的时候，必须动态地映射这些页。

page结构与物理页相关，该结构对页的描述只是短暂的，内核仅仅用这个数据结构来描述当前时刻相关物理页中存放的东西，目的在于描述物理内存本身，而不是其中资源。因为由于交换等原因，虚拟页可能不再和同一个page结构相关联。内核用这一结构来管理系统中所有的页，每个物理页都要分配一个这样的结构。

2. 区

由于硬件限制，有些页位于内存中特定的物理地址上，不能用于一些特定的任务，所以内核把页划分为不同的区(ZONE).

Linux必须处理如下两种内存缺陷引起的内存寻址问题。

a.一些硬件只能用在某些特定的内存地址来执行DMA。

b.一些体系结构的内存的物理寻址范围比虚拟寻址范围大得多，这样就有一些内存不能永久地映射在内核空间上。

因为存在这些制约条件，Linux主要使用了四种区：

ZONE_DMA:这个区包含的页能用来执行DMA操作。

ZONE_DMA32：和ZONE_DMA类似，该区包含的页面可用来执行DMA操作，不同之处在于这些页面只能被32位设备访问。在某些体系结构，该区比ZONE_DMA更大。

ZONE_NORMAL：这个区包含的都是能正常映射的页。

ZONE_HIGHEM: 高端内存，其中的页并不能永久地映射到内核地址空间。

区的实际使用是和体系结构相关的，某些体系结构内存在任何地址空间执行DMA都没有问题。在X86-32每个区所占页的列表如下

每个区都用struct zone表示，在定义

struct zone {
unsigned long            watermark[NR_WMARK];
unsigned long            lowmem_reserve[MAX_NR_ZONES];
struct per_cpu_pageset   pageset[NR_CPUS];
spinlock_t               lock;
    struct free_area         free_area[MAX_ORDER]
spinlock_t               lru_lock;
struct zone_lru {
struct list_head list;
unsigned long    nr_saved_scan;
} lru[NR_LRU_LISTS];
struct zone_reclaim_stat reclaim_stat;
unsigned long            pages_scanned;
unsigned long            flags;
atomic_long_t            vm_stat[NR_VM_ZONE_STAT_ITEMS];
int prev_priority;
unsigned int inactive_ratio;
wait_queue_head_t *wait_table;
unsigned long            wait_table_hash_nr_entries;
unsigned long            wait_table_bits;
struct pglist_data *zone_pgdat;
unsigned long            zone_start_pfn;
unsigned long            spanned_pages;
unsigned long            present_pages;
const char *name;
};

这个结构体很大，但是系统中只有三个区，因此，也只有三个这样的结构。几个重要域如下：

Lock域是一个自旋锁，它防止结构被并发访问，这个域只保护结构，而不保护驻留在这个区中的所有页。

watermark 数组持有该区最小值，最低和最高水位值，内核使用水位为每个内存区设置合理的内存消耗基准。该水位随空闲内存的多少而变化。

name域是一个以NULL结束的字符串表示这个区的名字，内核启动期间初始化这个值，三个区名字分别是”DMA”,”Normal” 和”HighMem”。

3. 获得页

内核提供的请求内存的接口，都是以页为单位，定义于
(1)

struct page * alloc_pages(gfp_t gfp_mask, unsigned int order)
分配2order(1<<order)个连续的物理页，返回一个指针，该指针指向第一个page结构体，出错返回NULL。
void *page_address(struct page *page)； //返回指定物理页当前所在的逻辑地址.
还可以直接调用
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order);
如果只需要申请一个页，可以用
struct page *alloc_page(gfp_t gfp_mask);
unsigned long __get_free_page(gfp_t  gfp_mask);//这两个函数功能与上面相同，只是order值为0.

(2)如果需要让返回的页内容全为0，用这个函数

unsigned long get_zeroed_page(gfp_t gfp_mask) ;//分配返回一个页，逻辑地址，并且内容全清零

底层分配页方法列表：

(3)释放页

释放页内存函数：

void __free_pages(struct page *page, unsigned int order)；
void free_pages(unsigned long addr, unsigned int order)；
void free_page(unsigned long  addr);

分别与上述分配函数配套使用，释放页要谨慎，只能释放属于你的页。错误释放，容易导致系统崩溃。

分配内存应该做错误检查，若失败，应该做相应处理；在程序开始就先进行内存分配是有意义的。

4. kmalloc()

用来获得以字节为单位的一块内存，所分配内存在物理上是连续的，在定义

void *kmalloc(size_t size, gfp_t flags);

gfp_mask标志，可分为三类：行为修饰符、区修饰符、类型

(1).行为修饰符

表示内核应当如何分配所需内存，某些特定情况下，只能使用某些特定的方法分配内存。比如中断处理程序中要求分配内存函数不能睡眠。

在定义，中包含这个头文件。

可以同时指定这些分配标志，比如

ptr = kmalloc(size, __GFP_WAIT|__GFP_IO|__GFP_FS);

表示也分配器(最终调用alloc_pages())在分配时可以阻塞，可以执行I/O,还可以执行文件系统操作。

大多数分配都会指定这些修饰符，但一般不是直接指定，而是采用类型标志。

(2).区修饰符

表示从哪儿分配内存，内核把物理内存分为多个区，每个区用于不同目的。

分配可以从任何区开始，不过优先从ZONE_NORMAL开始，这样确保其他区在需要时有足够的空闲页。

不能给_get_free_pages()或kmalloc()指定ZONE_HIGHMEM，因为这两个函数返回都是逻辑地址，而不是page结构，高端内存可能还没有映射到内核的虚拟地址空间，因此根本没有逻辑地址。只有alloc_pages()才能分配高端内存。大多数情况下ZONE_NORMAL足矣。

 (3).类型

组合行为修饰符和区修饰符，将各种可能用到的组合归纳为不同类型，简化了修饰符的使用。

内核趋向于使用正确的类型标志。

GFP_KERNEL:内核中最常用标志，可能引起睡眠，普通优先级，只用在可以重新安全调度进程上下文中(没有持有锁),这个标志对内核如何获取请求的内存没有任何限制，可以让调用者睡眠、交换、刷新一些页到硬盘等，所以分配成功可能性很高。

GFP_ATOMIC: 不能睡眠，分配成功相对机会较小(特别内存短缺时)。

GFP_NOIO和GFPNOFS:可能引起阻塞，用在某些低级块I/O或文件系统中，内核使用较少。

GFP_DMA：表示分配器必须满足从ZONE_DMA进行分配，一般与GFP_ATOMIC和GFP_KERNEL结合使用。

标志常用情形列表

kfree():在定义

void kfree(const void *ptr);

配对使用，释放kmalloc()分配的内存。释放属于内核其他部分的内存，可能导致严重后果，但kfree(NULL)是安全的。

 

5.vmalloc()

vmalloc()与kmalloc()工作方式类似，不同点：

vmalloc()分配的内存：虚拟地址连续，物理地址不一定连续。

kmalloc()分配的内存：虚拟地址连续，物理地址也连续。

尽管只有某些情况下才需要物理上连续的内存块，但内核多用kmalloc()来分配内存，主要是基于性能的考虑：vmalloc()函数为了把物理上不连续的页转换为虚拟地址空间上连续的页，必须专门建立页表项，vmalloc()获得的页必须一个一个进行映射，这会导致比直接内存映射大得多的TLB抖动。

vmalloc()在声明

void *vmalloc(unsigned long size);

该函数返回一个指针，指向逻辑上连续的一块内存区，大小至少为size；发生错误时函数返回NULL。

函数可能睡眠，因此不能在中断上下文 ，也不能在不允许阻塞的情况下进行调用。

释放vmalloc()分配的页

void vfree(const void *addr);

该函数也可以睡眠，没有返回值。

6.alsb层

为了便于数据的频繁分配和回收，常常会用到空闲链表，空闲链表包含可供使用的、已经分配好的数据结构块。当需要一个新的数据结构实例时，从空闲链表抓取一个，而不需要分配内存，当不再使用这个数据结构实例时，把它放回空闲链表，而不是释放它。实际上，空闲链表就相当于对象高速缓存。

而内核是不知道任何空闲链表存在的，所以提供了一个slab分配器(slab层)来扮演通用数据结构缓存层的角色。

slab分配器基本设计思想：

①频繁使用的数据结构也会频繁分配和释放，应当缓存它们；

②频繁分配和回收会导致内存碎片，空闲链表的缓存会连续存放，避免碎片；

③回收的对象可以立即投入下一次使用，因此对于频繁分配和释放，空闲链表能够提高其性能；

④如果分配器知道对象大小、页大小和总的高速缓存的大小这些概念，它会做出更明智的决策；

⑤如果让部分缓存专属于单个处理器(系统中每个处理器独立)，那么分配和释放就可以在不加SMP锁的情况下进行；

⑥如果分配器是与NUMA相关的，它就可以从相同的内存节点为请求者进行分配；

⑦对存放的对象进行着色，以防止多个对象映射到相同的高速缓存行；

6.1 slab层的设计

slab层把不同的对象划分为所谓高速缓存组，其中每个高速缓存组都存放不同类型的对象，每种对象类型对应一个高速缓存。比如一个高速缓存存放进程描述符(task_struct)，另一个高速缓存存放索引节点对象(struct inode)。kmalloc()接口建立在slab层之上，使用了一组通用高速缓存。

这些高速缓存又被划分为slab，slab由一个或多个物理上连续的页组成。一般情况下，一个slab仅仅由一页组成。每个高速缓存可以有多个slab。

每个slab都处于三种状态之一：满、部分满或空；当内核需要一个新对象时，先从部分满的slab进行分配，如果没有部分满的slab，就从空slab分配，如果没有空的slab,就要创建一个slab，这种策略能减少碎片。

看一个实例，inode结构(磁盘索引节点在内存中的体现)会频繁地创建和释放，因此，用slab分配器来管理很合适。struct inode由inode_cachep高速缓存进行分配。

这种高速缓存由一个或多个slab组成，每个slab包含尽可能多的struct inode对象，当内核请求分配一个新的inode结构时，内核从部分满或空的slab返回一个指向已分配但未使用的inode结构的指针。当内核用完inode对象后，slab分配器就把该对象标记为空闲，高速缓存、slab及对象的关系：

每个高速缓存都使用kmem_cache结构表示，其包含一个kmem_list3结构，这个结构包含三个链表：slabs_full, slabs_partial, slabs_empty.这些链表包含高速缓存中所有的slab。

而slab用struct slab来描述：

struct slab {
    struct list_head list; //满、部分满或空链表
    unsigned long colouroff; //slab着色的偏移量
    void *s_mem;        / //slab的第一个对象
    unsigned int inuse;     //slab中已分配的对象数
    kmem_bufctl_t free; //第一个空闲对象，如果有的话
    unsigned short nodeid;
};

slab描述符在slab之外分配，若空间足够也可以把描述符放在slab里面。

slab分配器可以创建新的slab,通过__get_free_pages()低级内核页分配器进行的

忽略与NUMA相关的代码，一个简单的kmem_getpages()函数

static inline void * kmem_getpages(struct kmem_cache *cachep, gfp_t flags)
{
    void *addr;
    flags |= cachep->gfpflags;
    addr = (void*) __get_free_pages(flags, cachep->gfporder);
    return addr;
}

接着调用kmem_freepages()释放内存；

slab分配器的关键就是避免频繁分配和释放页，只有当给定高速缓存中没有空的slab时，才会调用页分配函数；只有当内存变得紧缺，系统试图释放出更多内存以供使用，或者当高速缓存显式地被撤销时才会释放内存。

slab层的管理，就是在每个高速缓存的基础上，通过一组接口来创建和撤销新的高速缓存，并且在缓存中分配和释放对象，高速缓存及其内的slab复杂管理完全由slab层的内部机制来处理。

6.2 slab分配器的接口

(1)创建新的高速缓存

struct kmem_cache *
kmem_cache_create (const char *name, size_t size, size_t align,
    unsigned long flags, void (*ctor)(void *))

name:高速缓存名字, 在/proc/slabinfo可以看到；

size:高速缓存中每个元素的大小；

align: slab内第一个对象的偏移，确保业内对齐，一般用0即可；

flags: SLAB标志，可选参数，控制高速缓存行为，0表示没有特殊行为，可以一个或多个标志进行或运行；

SLAB_HWCACHE_ALIGN ：该标志命令slab层把一个slab内的所有对象按高速缓存行对齐，这可以提高性能，但以增加内存开销为代价，防止“错误的共享”。

SLAB_POISON ：是slab层用已知的值(a5a5a5a5)填充slab，就是所谓“中毒”，有利于对位初始化内存的访问。

SLAB_RED_ZONE ：在已分配的内存周围插入“红色警戒区”以探测缓冲越界。

SLAB_PANIC：标志当分配失败时提醒slab层。这在要求分配只能成功的时候非常有用，比如在系统初启动时分配一个VMA结构的高速缓存。

SLAB_CACHE_DMA：这个标志分配的slab层使用可以执行DMA的内存给每个slab分配空间。只有分配对象用于DMA，并且必须驻留在ZONE_DMA区时才用此标志。

ctor：高速缓存的构造函数，只有再新的页追加到高速缓存时，构造函数才被调用。实际上Linux啮合的高速缓存不使用构造函数，赋值NULL即可。

kmem_cache_create()在成功时返回一个指向所创建高速缓存的指针，否则返回NULL;

这个函数可能会睡眠，因此不能在中断上下文中使用。

要撤销一个高速缓存，调用

int kmem_cache_destroy(struct  kmem_cache *cachep);

这个函数通常在模块注销时调用，它也会睡眠，成功返回0，失败返回非零。调用该函数之前，必须确保：

①高速缓存中的所有slab都必须为空

②在调用kmem_cache_destroy()过程中，之后都不能再访问这个高速缓存。

(2)从缓存中获取对象：

创建高速缓存之后，可以通过下列函数获取对象

void * kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags);

从给定的高速缓存cachep中，返回一个指向对象的指针，如果高速缓存的所有slab都没有空闲的对象，那么slab层必须通过kmem_getpages()获取新的页，flags的值传递给_get_free_pages()。一般用到的是GFP_KERNEL或GFP_ATOMIC。

最后，释放一个对象，把它返回给原先的slab，可以用：

void kmem_cache_free(struct kmem_cache *cachep, void *objp);

这样就能把cachep中的对象objp标记为空闲。

(3)slab分配器的使用实例—task_strcut

首先，内核用一个全局变量存放指向task_struct高速缓存的指针：

static struct kmem_cache *task_struct_cachep;

内核初始化期间，在定义与kernel/fork.c的fork_init()中会创建高速缓存：

/* create a slab on which task_structs can be allocated */
    task_struct_cachep =
        kmem_cache_create("task_struct", sizeof(struct task_struct),
            ARCH_MIN_TASKALIGN, SLAB_PANIC | SLAB_NOTRACK, NULL);

创建一个名为task_struct的高速缓存，其中存放的就是类型为struct task_struct的对象，该对象被创建后存放在slab中偏移量为ARCH_MIN_TASKALIGN字节的地方，ARCH_MIN_TASKALIGN的值与体系结构相关，通常定义为L1高速缓存的字节大小。没有构造函数，不用检查返回值，因为设置了SLAB_PANIC标志，如果分配失败，slab分配器就调用panic()函数。

每当进程调用fork()时，一定会创建一个新的进程描述符，在dup_task_struct()中完成：

# define alloc_task_struct()    kmem_cache_alloc(task_struct_cachep, GFP_KERNEL)
struct task_struct *tsk;
…
tsk = alloc_task_struct();

进程执行完后，如果没有子进程在等待的话，它的进程描述符就会被释放，并返回给task_struct_cachep slab高速缓存，这在free_task_struct()中执行，tsk是现有进程：

kmem_cache_free(task_struct_cachep, tsk);

由于进程描述符是内核的核心组成部分，时刻都要用到，因此task_struct_cachep高速缓存绝对不会被撤销掉。

slab层负责内存紧缺情况下所有底层的对齐、着色、分配、释放和回收等。如果要频繁创建很多相同类型的对象，那么就应该考虑使用slab高速缓存，也就是说，不要自己去实现空闲链表。

7. 在栈上静态分配

在用户空间，以前讨论的那些分配的例子，有不少可以在栈上发生，因为用户空间能够奢侈地负担起非常大的栈，而且栈空间可以动态增长，但是内核，却不能这么奢侈—内核栈小且固定。

每个进程的内核栈大小既依赖体系结构，也与编译时的选项有关。

(1) 单页内核栈

每个进程的整个调用链必须放在自己的内核栈中，中断处理程序也曾经使用它们所中断的进程的内核栈，这样中断处理也放在内核栈中，这就要求更加严格的约束。

2.6内核引入一个选项设置单页内核栈，当激活这个选项时，中断程序不再使用进程内核栈，而是实现了一个中断栈。

内核栈是1页或者2页，取决于编译时配置，在任何情况下，无限制的递归和alloc()是不允许的。

(2) 在栈上光明正大的工作

在任意一个函数中，都必须尽量节省栈资源，局部变量所占之和不要超过几百字节，在栈上进行大量的静态分配(比如大型数组或大型结构体)都是很危险的。

栈溢出时悄无声息，会覆盖掉thread_info结构和邻堆栈末端的东西。

最好的情况是引起崩溃，最坏的情况悄无声息的破坏数据。

因此大块内存的分配最好是的动态分配。

8. 高端内存的映射

在高端内存中的页不能永久地映射到内核地址空间上，因此通过alloc_pages()以__GFP_HIGHMEM标志获得的页不可能有逻辑地址。在X86体系结构，高端内存中的页被映射到3GB~4GB。

(1) 永久映射

一个给定的page结构映射到内核虚拟地址空间，使用在定义的函数：

void *kmap(struct  page *page);

这个函数在高端内存低端内存上都能用，如果page结构对应的是低端内存中的一页，函数返回该页的虚拟地址，如果页位于高端内存，则会建立一个永久映射，再返回地址，这个函数可以睡眠，因此只能用在进程上下文中。

因为允许永久映射的数量是有限的，当不再需要高端内存时，应该解除映射

void kunmap(struct page *page);

(2) 临时映射

当必须创建一个映射而当前的上下文又不能睡眠时，内核提供了临时映射，也就是所谓的原子映射。

void *kmap_atomic(struct page *page, enum km_type type);
type是下列枚举类型之一，在<asm/kmap_types.h>定义
enum km_type {
    KM_BOUNCE_READ,
    KM_SKB_SUNRPC_DATA,
    KM_SKB_DATA_SOFTIRQ,
    KM_USER0,
    KM_USER1,
    KM_BIO_SRC_IRQ,
    KM_BIO_DST_IRQ,
    KM_PTE0,
    KM_PTE1,
    KM_IRQ0,
    KM_IRQ1,
    KM_SOFTIRQ0,
    KM_SOFTIRQ1,
    KM_L1_CACHE,
    KM_L2_CACHE,
    KM_TYPE_NR
};

这个函数不会阻塞，因此可以用在中断上下文和其他不能重新调度的地方。它也禁止抢占，这是有必要的，因为映射对每个处理器都是唯一的。

通过下列函数取消映射：

void kunmap_atomic(void *kvaadr, enum km_type  type);//这个函数也不会阻塞。

9.每个CPU的分配

支持SMP的现代操作系统使用每个CPU上的数据，对于给定的处理器其数据是唯一的。一般来说，每个CPU的数据存放在一个数组中，数组的每一项对应系统中一个处理器。比如可以声明如下数据：

unsigned int my_percpu[NR_CPUS];

访问方式如下：

int cpu;
cpu = get_cpu(); //获取当前处理器，并且禁止内核抢占
my_percpu[cpu]++;
printk(“my_percpu on cpu=%d is %lu\n”,cpu,my_percpu[cpu]);
put_cpu(); //激活内核抢占

由于数据对当前处理器是唯一的，对于多处理器不存在并发问题，不需要加锁；另，由于get_cpu()禁止内核抢占，也不存在竞争条件。所以，这个数据操作是安全的。

10.新的每个CPU接口

2.6内核为了方便创建和操作CPU数据，引进了新的操作接口，称作percpu。该接口归纳了CPU数据操作行为，简化了创建和操作每个CPU的数据。

在声明

10.1 编译时的每个CPU数据

DEFINE_PER_CPU(type,  name);

这个宏为系统中的每个处理器都创建一个类型为type，名字为name的变量实例。如果在别处申明，以防编译时警告，可以用

DECLARE_PER_CPU(type, name);
可用get_cpu_var()和put_cpu_var()操作变量。
get_cpu_var(name)++; //get_cpu_var()返回当前处理器上的指定变量，同时禁止抢占
put_cpu_var(name); //操作完成，重新激活内核抢占
还可以获得别的处理器上的每个CPU数据；
per_cpu(name, cpu)++;//该函数不会禁止内核抢占，也不会提供任意形式的锁保护。

这些编译时每个CPU数据的例子并不能在模块内使用，因为链接程序实际上将它们创建在一个唯一的可执行段中(.data.percpu)。

10.2 运行时的每个CPU数据

运行时为每个处理器创建所需内存的实例，原型在

void *alloc_percpu(type); //该宏为每个处理器分配一个type型数据，按单字节对齐
void * __alloc_percpu(size_t size, size_t align);//为每个处理器分配一个size大小对象，按align对齐
void free_percpu(const void *); //释放所有处理器上指定的每个CPU数据
alloc_percpu()实际上是对__alloc_percpu()的一个封装宏，比如：
struct rabid_cheetah = alloc_percpu(struct rabid_cheetah);
等价于
struct rabid_cheetah = __alloc_percpu(sizeof(struct  rabid_cheetah), __alignof__(struct  rabid_cheetah));
__alignof__()是gcc的一个功能，返回指定类型或lvalue所需的对齐字节数。

alloc_percpu()返回一个指针，它用来间接引用动态创建的每个CPU数据，内核提供两个宏来利用指针获取每个CPU数据：
get_cpu_var(ptr); //返回一个void类型指针，该指针指向处理器的ptr的拷贝，禁止内核抢占
put_cpu_var(ptr); //重新激活内核抢占
一个完整的例子：
void *percpu_ptr;
unsigned long *foo;
percpu_ptr = alloc_percpu(unsigned long);
if (!ptr)
    …//出错处理
foo = get_cpu_var(percpu_ptr);
/*操作foo…*/
put_cpu_var(percpu_ptr);

11. 使用每个CPU数据的原因

使用每个CPU数据的好处：

①减少了数据锁定，你需要确保本地处理器只会访问它自己的唯一数据，系统本身并不存在任何措施禁止你从事欺骗活动；

②可以大大减少缓存失效；

每个CPU数据在中断上下文或进程上下文中使用都很安全，但注意，不能在访问每个CPU数据过程中睡眠，否则，醒来后可能已经到了其他处理器上。

12．分配函数的选择

如果需要连续的物理页，可以使用某个低级页分配器或kmalloc()。这是内核常用分配方式，两个最常用的标志是GFP_ATOMIC和GFP_KERNEL。

如果想从高端内存进行分配，就是要alloc_pages()，它返回一个指向struct page结构的指针，而不是一个指向某个逻辑地址的指针。因为高端内存可能没有被映射，访问它唯一方法是通过相应的struct page结构，为了获得真正的指针，应该调用kmap()，吧高端内存映射到内核的逻辑地址空间。

如果不需要物理上连续的页，仅需要虚拟地址上连续的页，那就是用vmalloc(),但vmalloc()相对kmalloc()来说，有一定性能损失。

如果要创建和撤销很多大的数据结构，那就考虑用slab高速缓存。slab层会给每个处理器维持一个对象高速缓存(空闲链表).