第八章 内存管理

本章通过三部分内容描述内核给自己动态分配内存：

                                                                                          页框处理 

                                                                                          内存区管理

                                                                                          非连续内存分配

页框管理                                                                                                  

Linux采用4KB页框大小作为标准的内存分配单元，基于以下两个原因：

1.由分页单元引发的缺页异常很容易得到解释，或者时由于请求的页存在但不允许进程对齐访问，或者是由于请求的页不存在。在第二种情况下，内存分配器必须找到一个4KB的空闲页框，并将其分配

2.虽然4KB和4MB都是磁盘块大小的倍数，但是在绝大数情况下，当主存和磁盘之间传输小块数据时更有效

页描述符

页框的状态信息保存在一个类型为page的页描述符中

所有的页描述符保存在mem_map数组中，每个页描述符长度为32字节

virt_to_page(addr)宏产生线性地址addr对应的页描述符地址

pfn_to_page(pfn)宏产生与页框号p f n对应的页描述符地址

页描述符（page）两个重要的字段：

_count：页框的引用计数

               如果为-1，则该页框空闲，可以被分配

               如果大于等于0，则说明该页框被分配给了一个或者多个进程，或者用于存放一些内核数据结构

               page_count( )函数返回_count +1的值，也就是该页使用者的数目 

flags：包含多达32个用来描述页框状态的标志

非一致内存访问（None-Uniform Memory Access，NUMA）

非一致内存访问：同一个cpu对不同内存单元的访问可能需要的时间不一样

节点（node）：物理内存被分为好几个节点

                            在一个单独的节点中，任一给定的CPU访问页面的时间都是相同的

节点描述度：每个节点都有一个类型为pg_data_t的描述符

                        所有节点的描述符都存放在一个单链表中，它的第一个元素由pgdat_list变量指向

由于80x86体系结构支持一致内存访问（Uniform Memory Acess，UMA），所以并不真正需要NUMA的支持。但是，Linux还是使用了节点，不过时单独一个节点。

在80x86结构中，把物理内存分组在一个单独的节点中可能没有用处，但是，这种方式有助于内核代码的处理更具有移植性。

管理区（zone）：每个节点又被分为好几个管理区

内存管理区

Linux内核必须处理80X86体系结构的两种硬件限制：

           1.ISA总线的直接内存存取（DMA）处理器有一个严格的限制：它们只对RAM的前16MB寻址

           2.在具有大容量RAM的现代32位计算机中，CPU不能直接访问所有的物理内存，因为线性地址太小了

为了应对这两种限制，Linux 2.6把每个内存节点的内存划分为3个管理区（zone）：

ZONE_DMA：包含低于16MB的内存页框

ZONE_NORMAL：包含高于16MB且低于896MB的内存页框

ZONE_HIGHMEM：包含高于从896MB开始高于896MB的内存页框

在64位体系结构上ZONE_HIFHMEM区总是空的

每个内存管理区都自己的描述符

每个页描述符都有到内存节点和到节点管理区（包含相应页框）的链接

page_zone( )函数接收一个页描述符的地址作为它的参数，它读取页描述符的flags的最高位，然后通过查看zone_table数组来确定相应管理区描述符的地址

2015.10.19.21.40

保留的页框池

内核为原子内存分配请求保留了一个页框池，只有在内存不足时才使用

min_free_kbytes：保留内存的数量，以KB为单位

                              大小取决于ZONE_DMA和ZONE_NORMAL内存管理区的页框数目

                               不能小于128也不能大于65536

计算公式：保留池大小^2=16*直接映射内存  保留池单位（KB）                          

分区页框分配器                    

被称作分区页框分配器（zoned page frame allocator）的内核子系统，处理对连续页框组的内存分配请求 

请求和释放页框

6个请求分配的函数和宏：

alloc_pages(gfp_mask,order)：用这个函数请求2^order个页框

                                                 它返回第一个页框的页描述符的线性地址，或者分配失败，返回NULL

alloc_page(gfp_mask)：用于获得一个单独页框的宏；它扩展为：

                                      alloc_pages(gfp_mask, 0)

                                       它返回所分配页框的页描述符的线性地址

_ _get_free_pages(gfp_mask,order)：该函数类似于alloc_pages()，但它返回第一个页框的线性地址

_ _get_free_page(gfp_mask)：用于获得一个单独页框的宏；它扩展为：

                                                 _ _get_free_pages(gfp_mask)

                                                 返回所获取页框的线性地址

get_zeroed_page(gfp_mask)：函数用来获取填满0的页框；它调用：

                                         alloc_pages(gfp_mask | _ _GFP_ZERO,0)

                                         然后返回所获取页框的线性地址

_ _get_dma_pages(gfp_mask,order)：用这个宏获取适用于DMA的页框，它扩展为：

                                                         _ _get_free_pages(gfp_mask | _ _GFP_DMA，order)

4个释放页框的函数和宏：

_ _free_pages(page，order)：该函数先检查page指向的页描述符的指针，如果该页框未被保留（PG_reserved标志为0），就把描述符的count字段减1。如果count值为0，就假定从与page对应的页框开始的2^order个连续的页框不再使用

free_pages(addr，order)：该函数类似于_ _free_pages(page，order)，但是它接受的参数为要释放的第一个页框的线性地址addr

_ _free_page(page)：这个宏释放page所指页描述符对应的页框；它扩展为：

                                   _ _free_pages(addr，0)

free_page(addr)：该函数释放线性地址为addr的页框。它扩展为：

                               free_pages(addr，0)           

总结：对于分配函数或者宏，alloc_*的返回页框的页描述符的线性地址

                                                    *get*的返回页框的线性地址

            对于释放函数或者宏，_ _*的以页框的页描述符的线性地址为参数

                                                   非_ _开头的以页框的线性地址为参数       

2015.10.19

高端内存页框的内核映射

物理内存896MB以上的部分称为高端内存，这些内存的页框并不映射在内核线性地址的第四个GB，所以内核不能直接访问它们。

32位系统内核访问高端内存的方法：

1.高端内存页框的分配只能通过alloc_pages()函数和它的快捷函数alloc_page()函数。这些函数返回第一个分配页框的线性地址。

2.没有线性地址的页框不能被内核访问。因此，内核线性地址空间的最高128M的一部分专门用于映射高端内存页框。

内核采用三种不同的机制将页框映射到高端内存：永久内核映射

临时内核映射 非连续内存分配

建立永久内核映射可能堵塞当前进程；这发生在空闲页表项不存在时，也就是在高端内存上没有页表项可以用作页框的‘窗口’时。因此永久内核映射不能用于中断处理程序和可延迟函数。

建立临时内核映射绝不会要求堵塞当前进程；不过它的缺点是只有很少的临时内核映射可以同时建立起来。

永久内核映射

永久内核映射允许建立高端页框到内核地址空间的长期映射。它们使用主内核页表中一个专门的页表，其地址存放在pkmap_page_table变量中。

LAST_PKMAP：页表中的表项数

PKMAP_BASE：该页表相对应的线性首地址

pkmap_count数组：包含LAST_PKMAP个计数器，pkmap_page_table中的每一项都有

计数器为0，对应的页表项没有映射任何高端内存，并且可用

计数器为1，对应的页表项映射了相应的高端内存，但是它不可用

计数器为n，相应的页表项映射了一个高端页框，这意味这正好有n-1个内核成分正在使用这个页框为了记录高端内存页框与永久内核映射的线性地址之间的联系，内核使用了page_address_htable散列表。

page_address_htable包含一个page_address_map数据结构，该结构还包含执行页框描述符的指针和页框的线性地址。

page_address()函数用于返回页框的线性地址，参数是一个指向页描述符的指针。

两种情况：

1.如果页框不在高端内存上，则线性地址肯定存在并且通过计算页框下标，然后转换成物理地址，最后通过物理地址得到相应的线性地址

2.如果页框在高端内存中，该函数就到page_address_htable散列表中查找。如果在散列表中找到页框，page_address()就返回它的线性地址。

临时内核映射

临时内核映射比永久内核映射的实现要简单；此外，他们可以用在中断处理程序和可延迟函数的内部，因为它们从不阻塞当前进程。

每个CPU都有它自己的包含13个窗口的集合，它们用enum

km_type数据结构表示。每个符号标识了窗口的线性地址。

内核必须确保同一窗口永不会被两个不同的控制路径同时使用。因此，km_type结构的每一个符号只能由一种内核成分使用，并以该成分命名。最后一个符号KM_TYPE_NR本身不表示一个线性地址，但由每个CPU用来产生不同的可用窗口

2015.10.20.23.28

伙伴系统

从本质上来说，避免内存外碎片的方法有两种：

1.利用分页单元把一组不连续的物理内存映射到连续的线性地址

2.开发一种适当的技术来记录现存的空闲连续页框块的情况，以尽量避免为满足对小块的请求而分割大的空闲块

Linux采用著名的伙伴系统（buddy

system）算法来解决外碎片问题。

把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1，2，4，8，16，32，64，128，256，512和1024个连续的页框。

每个块的第一个页框的物理地址是该块大小的整数倍。

满足以下三个条件的两个块称为伙伴：

1.两个块具有相同的大小，记作b

2.它们的物理地址是连续的

3.第一块的第一个页框物理地址是2*b*2^12

数据结构

Linux 2.6为每个管理区使用不同的伙伴系统

1.管理区描述符的zone_mem_map和size字段：

zone_mem_map：指向管理区的第一个页描述符的指针

size：管理区中页框的个数

2.包含11个元素，元素类型为free_area的一个数组，每个元素对应一种块的大小：

free_list字段：这个双向链表集中了大小为2^k页的空闲块对应的页描述符更精确地说，该链表包含每个空闲页块的起始页框的描述符

页描述符的lru：保存了指向链表中相邻元素的指针（p r e和next）

nr_free：它指定了大小为2^k的空闲块的个数

页描述符的private：一个2^k的空闲块的起始页框的页描述符的private置为order 即为k

分配块和释放块

分配块：_ _rmqueue()函数，参数为管理区描述符的地址和order

释放块：_ _free_pages_bulk()函数，参数为被释放块中所包含的第一个页描述符的地址（page）

管理区描述符的地址（zone），块大小的对数（order）

每CPU页框高速缓存

内核经常请求和释放单个页框，为了提高系统性能，每个内存管理区定义了一个“每CPU”页框高速缓存。

实际上，这里为每个CPU提供了两个高速缓存：一个热高速缓存和冷高速缓存

如果内核或者用户态进程在刚分配到页框后就立即向页框写，那么从热高速缓存中获取页框就对系统性能有利。

如果页框将要被DMA操作填充，那么从冷高速缓存中获取页框比较有利。

实现每CPU页框高速缓存的主要数据结构是存放在内存管理区描述符的pageset字段中的一个per_cpu_pageset数组数据结构。该数组包含为每个CPU提供的一个元素；这个元素依次有两个per_cpu_pages描述符组成，一个热高速缓存和一个冷高速缓存

通过每CPU页框高速缓存分配页框

函数buffered_rmqueue()：该函数在制定的内存管理区中分配页框。

参数：内存管理区描述符的地址，请求的内存大小的对数order，以及分配标志gfp_flags

释放页框到每CPU页框高速缓存

free_hot_page()和free_cold_page()：都是对free_hot_cold_page()函数的简单封装，接受的参数为将要释放的页框的描述符地址page和cold标志（指定是热高速缓存还是冷高速缓存）

管理区分配器

管理区分配器是内核页框分配器的前端。该成分必须分配一个包含足够多空闲页框的内存管理区，它满足以下几个目标：

1.它应该保护保留的页框池

2.当内存不足且允许阻塞当前进程时，它应当出发页框回收算法；一旦某些页框被释放，管理区分配器将再次尝试分配

3.如果可能它应当保存小而珍贵的ZONE_DMA内存管理区

对一组连续页框的每次请求实质上时通过alloc_pages()宏来处理的。接着，这个宏又再次调用__alloc_pages()函数，这个函数是管理区分配器的核心。它接受3个参数：

1.gfp_mask：在内存分配请求中指定的标志

2.order：将要分配的一组连续页框数量的对数

3.zonelist：指向zonelist数据结构的指针，该数据结构按优先次序少庙了适用于内存分配的内存管理区

分区页框分配器-->管理区页框分配器

释放一组页框

在前面的“分区页框分配器”一节描述的迎来释放页框的所有内核宏和函数都依赖于_

_free_pages函数。

它接受的参数为将要释放的第一个页框的页描述符的地址（page）和将要释放的一组页框的数量的对数（order）。

内存区管理

伙伴系统算法采用页框作为基本内存区，这适合于大块内存的请求，但对小内存区的请求，比如几十字节或几百字节？显然，如果为了存放很少的字节而给它分配一个整页框，这显然是一种浪费

slab分配器

高速缓存被划分为多个slab，每个slab由一个或者多个连续的页框组成，这些页框包含已分配的对象，也包含空闲的对象。

高速缓存描述符

每个高速缓存都由kmap_cache_t类型的数据来描述，称为高速缓存描述符。

slab描述符

高速缓存中的每个slab都有自己的类型为slab_t的描述符，称为slab描述符

slab描述符可以放在两个地方：

外部slab描述符：存放在slab外部，位于cache_sizes指向的一个不适合ISADMA的普通高速缓存中

内部slab描述符：存放在slab内部，位于分配给slab的第一个页框的起始地址

普通和专用高速缓存

高速缓存被分为两种类型：

普通高速缓存：只由slab分配器用于自己的目的

专用高速缓存：有内核的其余部分使用

普通高速缓存是：

1.第一个高速缓存叫做kmem_cache，包含由内核使用的其余高速缓存的高速缓存描述符。cache_cache变量包含第一个高速缓存的高速缓存描述符。

2.另外一些高速缓存包含用作普通用途的内存区。内存区大小的范围一般包含13个集合分区的内存区。一个叫做malloc_sizes的表分别指向26个高速缓存描述符，与其相关的内存大小为32，64，128，256，512，1024，2048，4096，8192，16384，32768，65536和131072字节。对于每中大小，都有两个高速缓存：一个适用于ISADMA分配，另一个适用于常规分配

在系统初始化期间调用kmem_cache_init()和kmem_cache_sizes_init()来建立普通高速映射。

2015.10.21.23:36

slab分配器与分区分页分配器的接口

当slab分配器创建新的slab时，它依靠分区分配器来获得一组连续的空闲页框。

它调用kmem_getpages()函数：

void* kmem_getpages(kmem_cache_t *cachep，int flags)

参数：cachep高速缓存描述符

flags说明如何分配请求页框

在相反的操作中，通过调用kmem_freepages()函数可以释放给slab的页框

给高速缓存分配slab

一个新创建的高速缓存没有包含任何slab，因此没有空闲对象。只有当满足以下两个条件都为真时，才给高速缓存分配slab：

1.已发出分配新对象的请求

2.高速缓存不包含任何空闲对象

从高速缓存中释放slab

在下列两种条件下才能撤销slab：

1.slab高速缓存中有太多的空闲对象

2.被周期性调用的定时器函数确定是否有完全未使用的slab能被释放

内存分配层次：分区页框分配器--->管理器分配器------>slab分配器------>slab对象

对象描述符

每个对象都有类型为kmem_bufctl_t的描述符。对象描述符存放在一个数组中，位于相应的slab描述符之后。因此，对象描述符也有两种可能的存放方式：

内部对象描述符：存放在slab的外面，位于slabp_cache字段指向的一个普通高速缓存中

外部对象描述符：存放在slab的内部，正好位于描述符所描述的对象之前

数组中的第一个对象描述符描述slab中的第一个对象，依次类推。对象描述符只不过是一个无符号整数，只有在对象空闲时才有效。它包含的是下一个空闲对象在slab中的下标，因此实现了slab空闲对象的一个简单链表。空闲对象链表中的最后一个元素的对象描述符用常规值BUFCTL_END（0xffff）标记。

对齐内存中的对象

slab分配器所管理的对象可以在内存中进行对齐，页就是说，存放它们的内存单元的起始物理地址是一个给定常量的倍数，通常是2。这个常量就叫对齐因子（alignment

factor）。

通常情况下，如果内存单元的物理地址是字对齐的，那么微机内存单元的存取会非常块。

当创建一个新的slab高速缓存时，就可以让它所包含的对象在第一级硬件高速缓存中对齐。为了做到这点，设置SLAB_HWCACHE_ALIGN高速缓存描述符标志。kmem_cache_create()函数按如下方式处理请求：

1.如果对象的大小大于高速缓存行（cacheline）的一半，就在RAM中根据L1_CACHE_BYTES的倍数（也就是行的开始）对齐对象

2.否则，对象的大小就是L1_CACHE_BYTES的因子取整。这可以保证一个小对象不会横跨两个高速缓存行。

显然，slab分配器在这里所做的事情就是以内存空间换取访问时间，即通过人为地增加对象的大小来获得较好的高速缓存性能，因此也引起额外的内碎片。

slab着色

同一硬件高速缓存行可以映射RAM中很多不同的块。而相同大小的对象倾向于存放在高速缓存内相同的偏移量处。在不同的slab内具有相同偏移量的对象最终可能映射在同一高速缓存中。高速缓存硬件可能因此而花费内存周期在同一高速缓存行与RAM内存单元之间来来往往传送两个对象，而其他的高速缓存行并未充分使用。slab分配器通过一种叫做slab着色（slab

coloring）的策略，尽量降低高速缓存的这种不愉快行为：把叫做颜色（color）的不同随机数分配给slab。

在slab内放置对象有很多可能的方式。方式的选择取决于对下列变量所作的决定：

num：可以在slab中存放的对象的个数（其值在高速缓存描述符的num字段中）

osize：对象的大小，包括对齐的字节

dsize：slab描述符的大小加上所有对象描述符的大小，就等于硬件高速缓存行大小的最小倍数。如果slab描述符和对象描述符都存放在外部，那么这个值就为0

free：在slab内未使用字节（没有分配给任一对象的字节）的个数

一个slab中的总字节长度可以表示为如下表达式：

slab的长度=(num * osize) + dsize + free

free总是小于osize，因为否则的话，就有可能把另外的对象放在slab内。

slab分配器利用空闲未用的字节free来对slab着色。

可用颜色的个数为free/aln（aln对齐因子）。因此，第一个颜色为0，最后一个颜色为

(free/aln– 1)。

如果用颜色col对一个slab着色，那么第一个对象的偏移量（相对于slab的起始位置）就等于

col* aln +  dsize字节。着色本质上导致把slab上的一些空闲区域从末尾移到开始。如下图：

只有当free足够大时，着色才起作用。

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

slab分配器的每个高速缓存包含一个称作slab本地高速缓存的数据结构（每个CPU都有一个），该结构由一个指向被时方对象的小指针数组组成。slab对象的大多数分配和释放只影响本地数组，只有在本地数组上溢或者下溢才更新slab数据结构。

高速缓存描述符的array字段（struct array_cache*[]，即指针数组）是一组指向array_cache数据结构的指针，系统中的每个CPU对应于一个。array_cache结构的字段如下：

本地高速缓存描述符并不包含本地高速缓存本身的地址；事实上，它正好位于描述符之后。当然本地高速缓存描述符存放的是指向已释放对象的指针，而不是对象本身。

内存池

内存池和保留页框池的区别：

保留的页框池：用于满足中断处理程序或者内部临界区发出的原子内存分配请求

内存池：是动态内存的储备，只能被特定的内核成分（即池的拥有者使用）使用

内存池描述符为mempool_t。

非连续内存管理区

把内存区映射到一组连续的页框是最好的选择，这样会充分利用高速缓存并获得较低的平均访问时间。不过，如果对内存区的请求不是很频繁，那么通过连续的线性地址来访问非连续的页框这样一种分配模式就会很有意义。这种模式的主要优点是避免了外碎片，而缺点是打乱了内核页表。

Linux非连续内存的应用：

1.为活动的交换区分配数据结构

2.为模块分配空间，或者给某些I/O驱动程序分配缓冲区

3.非连续内存分配还提供了一种使用高端内存的方法

非连续内存区的线性地址

第四GB线性地址的使用情况：

1.内存区的开始部分包含的是对896MB

RAM进行映射的线性地址；直接映射的物理内存末尾所对应的线性地址保存在high_memory变量中

2.内存区的结尾部分包含的是对固定映射的线性地址

3.从PKMAP_BASE开始，我们查找用于高端内存页框的永久映射的线性地址

4.其余线性地址可以用于非连续内存区。在物理内存映射的莫为与第一个内存之间插入一个大小为8MB（宏为VMALLOC_OFFSET）的安全区，目的是为了“捕获”对内存的越界访问。

如下图：从PAGE_OFFSET开始的线性地址空间

非连续内存区的描述符

每个非连续内存区都对应这一个类型vm_struct的描述符，下图列出了它的字段：

2015.10.23