第八章 内存管理

  第八章 内存管理

一．导入

1.什么叫动态内存？

 答：RAM的某些部分永久的分配给内核，并用来存放内核代码以及静态内核数据结构。而RAM的其他部分成为动态内存。

2.如何有效的管理动态内存？

 答：尽可能做到需要时分配，不需要时释放。

3.内核给自己分配动态内存的三种方法：

 答：“页框管理”和“内存区管理”介绍了对连续物理内存区处理的两种不同技术，而“非连续内存区管理”介绍对处理非连续内存区的第三种技术。

二．页框管理

 Intel的Pentium处理区可以采用两种不同的页框大小：4KB和4MB。Linux采用4KB一筐大小作为标准的内存分配单元。

（一）页描述符

  1.内核必须记录每个页框当前的状态，当前的状态包括什么？

答：①内核必须能区分哪些页框包含的是属于进程的页，而哪些页框包含的是内核代码或内核数据。②内核还必须能够确定动态内存中的页框是否空闲。

  2.什么样的页框是空闲页框？

   答：如果内存中的页框不包含有用的数据，那么这个框就是空闲的。

  3.什么是有用的数据？

   答：用户态进程的数据，某个软件高速缓存的数据，动态分配的内核数据结构，设备驱动程序的缓冲，内核模块的代码等等。

  4.页框的状态信息保存在一个类型为page的页描述符中，其字段入下：

  5.所有的页描述符存放在mem_map数组中，因为每个描述符长度为32个字节，所以men_map所需要的空间略小于整个RAM的1%。

  6.详细了解以下两个字段：

    ⑴_count：页的引用计数器若该字段为—1，则相应页框空闲，并可分配给任一进程或内核本身；若其值大于或等于0，则说明页框被分配给了一个或多个进程，或用于存放一些内核数据结构。Page_count()函数返回_count加1后的值，也就是该页的使用者的数目。

    ⑵flags：包含32个用来描述页框状态的标志，对每个PG_xyz标志，内核都定义了曹总其值的一些宏。PageXyz宏返回标志的值，SetPageXyz和ClearPageXyz宏分别设置和清除相应的位。

（二）非一致内存访问（NUMA）

  1.非一致内存访问有什么特点？

   答：在这种模型中，给定CPU对不同内存单元的方位时间可能不一样。对每个CPU而言，内核都试图把耗时节点的访问次数减到最少，从而要小心的选择ＣＰＵ最常引用的内核数据的存放位置。

　2.每个节点都有一耳光类型为pg_data_t的描述符，字段如下。所有节点的苗师傅都存放在一个单向链表中，它的第一个元素有pgdat_list变量指向。

（三）内存管理区

  1.Linux内核不许处理80×86体系结构的两种硬件约束，这两种约束限制了页框可以使用的方式。

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

   ②在具有大容量的RAM的现代32位计算机中，CPU不能直接访问所有的物理内存。

  2.如何应对这种限制？

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

       ①ZONE_DMA:包含低16MB的内存页框。②ZONE_NORMAL:包含高于16MB且低于896MB的内存页框。③ZONE_HIGHMEM:包含从893MB开始高于896MB的内存页框。

  3.内核可以直接访问上述①②，但不能直接访问③。但他们都是线性的映射到线性空进第4个GB。

  4.每个内存管理区都有自己的描述符：

  5.当调用一个内存分配函数时，必须指明请求页框所在的管理区。内核通常指明它愿意使用哪个管理区。

（四）保留的页框池

  1.两种满足内存分配请求的方法：①若有足够的空闲内存可用，请求就会被立刻满足。②否则，必须回收一些内存，并且将发出请求的内核控制路径阻塞，知道有内存被释放。

  2.当请求内存时，一些内核控制路径不能被堵塞，此时计算机如何处理？

   答：这种情况往往发生在处理中断或在执行临界区内的代码是。此时，一条内核控制路径应当产生原子内存分配请求。原子请求从不被堵塞；若没有足够的空闲页，则仅仅是分配失败而已。

  3.为尽量减少原子内存分配请求失败的可能性，内核为原子内存分配请求保留了一个页框池，只有在内存不足时才使用。

  4.保留内存的数量（以KB为单位）存放在min_free_kbytes变量中。它的初始值在内核初始化时设置，取决于包含在ZONE_DMA和ZONE_NORMAL内存管理区的页框数目：

其值在128和65536之间。

（五）分区页框分配器

  分区页框分配器是一种内核子系统，它处理对连续页框组的内存分配请求。

  其中“管理区分配器”接受动态内存分配与释放的请求。一小部分页框保留在高速缓存中用于快速的满足对单个页框的分配请求。

  1.请求和释放页框

   （1）可以通过6个烧友差别的函数和宏请求页框，他们返回第一个所分配页的线性地址，或者若分配失败，则返回NULL。

（2）用于请求页框的标志

  （3）在80×86体系结构中，后备管理区如下：

       ①若_ _GFP_DMA被置位，则只能从ZONE_DMA内存管理区获取页框。

       ②否则，若_ _GFP_HIGHMEM标志没有被置位，则只能按优先次序从ZONE_NORMAL和ZONE_DMA内存管理区获取页框。

       ③否则，按优先次序从ZONE_HIGHMEM、ZONE_NORMAL和ZONE_DMA内存管理区货物页框。

  （4）可以释放页框的函数和宏：_ _free_pages(page,order),free_pages(addr,order),_ _free_page(page),free_page(addr).

 （六）高端内存页框的内核映射

   896MB边界以上的页框返回所分配页框线性地址的页分配器函数不适用于高端内存，即不适用于ZONE_HIGHMEM内存管理区内的页框。

   内核采用以下三种不同的机制将页框映射到高端内存：①永久内核映射②临时内核映射③非连续内存分配。

  1.永久内核映射

   （1）永久内核映射允许内核建立高端页框到内核地址空间的长期映射，它不能用于中断处理程序和延迟函数。内核一次最多访问2MB或4MB的高端内存。

   （2）该页表映射的线性地址从PKMAP_BSST开始。Pkmap_count数组包含LAST_PKMAP个计数器，pkmap_page_table页表中的每一项都有一个。

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

      ②计数器为1：对应的页表项没有映射任何高端内存页框，但是他不能使用，因为自从她最后一次使用以来，其相应的TBL表现还未被刷新

      ③计数器为n（远大于1）：相应的页表项映射一个高端内存页框，这意味着正好有n-1个内核成分在使用这个页框。

   （3）为记录高端内存页框与永久内核映射包含的线性地址之间的关系，内核使用了page_address_htable散列表。该表包含一个page_address_map数据结构，用于为高端内存中的每一个页框进行当前映射。

 

   2.临时内核映射

   （1）建立临时内核映射决不会要求阻塞当前进程，可以用在中断处理程序和可延迟的函数，但是只有很少的临时内核映射可以同时建立起来。它比永久内核映射实现要简单。

 （七）伙伴系统算法

   1.外碎片

   （1）外碎片：频繁地请求和释放不同大小的一组连续页框，必然导致在已分配页框的块内分散了许多小块的空闲页框。

   （2）避免外碎片的方法：①利用分页单元把一组非连续的空闲页框映射到连续的线性地址空间。②开发一种适当的技术来记录现存的空闲连续页框快的情况，一尽量避免为满足对小块的请求而分割大的空闲块。

内核首选第二种方法。

  （3）解决外碎片问题的方法：伙伴系统算法。

     把所有的空闲页框分组为11个块链表，每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续的页框。对1024个页框的最大请求对应着4MB大小的连续RAM块。每个块的第一个页框的物理地址是该块大小的整数倍。大小为16个页框的块，其气势地址是16×的倍数。

     其逆过程即页框快的释放过程。

     内核试图把大小为b的一对空闲伙伴块合并为一个大小为2b的单独块。

     两个称作伙伴的块：①两个块具有相同的大小，记作b

                       ②他们的物理地址是连续的

                       ③第一块的第一个页框的物理地址是2×b×的倍数。

  2.数据结构

   在80×86结构中，有三种伙伴系统：第一种处理适合ISA DMA的页框，第二种处理“常规”页框，第三种处理高端内存页框。

   每个伙伴系统书用的主要数据结构：①mem_map数组。每个管理区都关系到mem_map元素的子集，子集中的第一个元素和元素的个数分别由管理区描述符的zone_mem和size字段指定。②包含11个元素、元素类型为free_area的一个数组，每个元素对应一种块大小。该数组存放在管理区描述符的free_area字段中。

  3.分配块

   _ _rmqueue(函数)用来在管理区中找到一个空闲块。该函数需要两个参数：管理区描述符的地址和order（请求的空闲页块大小的对数值（0表示一个单页块，1表示一个两页块，以此类推））。若页块被成功分配，函数返回第一个被分配页框的页描述符，否则，返回NULL。

  4.释放块

   _ _free_pages_bulk()函数按照伙伴系统的策略释放页框。使用3个参数：①page——被释放块中所包含的第一个页框描述符的地址②zone——管理区描述符的地址③order——块大小的对数。

（八）每CPU页框高速缓存

  每CPU页框高速缓存：内核经常请求和释放单个页框。为了提升系统性能，每个内存管理区定义了一个“每CPU”页框高速缓存。所有“每CPU”页框高速缓存包含一些预先分配的页框，他们被用于满足本地CPU发出的单一内存请求。

  计算机为每个内存管理器区和每个CPU提供两个高速缓存：热高速缓存和冷高速缓存。

  若内核或用户态进程在刚分配到页框后立即向页框写，那么从热高速缓存中获得页框就对系统性能有利；若页框将要被DMA操作填充，那么从冷高速缓存中获得页框较方便。

 1.通过每CPU页框告诉缓存分配页框

  Buffered_rmqueue()函数在指定的内存管理区中分配页框。它使用每CPU页框告诉缓存来处理单一页框请求。其参数为①内存管理区描述符的地址②请求分配的内存大小的对数order③分配标志gfp_flags。

  若gfp_falgs中的_ _GFP_COLD标志被置位，则页框从冷高速缓存中获取，否则从热高速缓存中获取。本质上操作如下：

     

 2.释放页框到每CPU页框告诉缓存

  内核使用free_hot_page()和free_cold_page()函数。他们都是free_hot_cold_page()的简单封装，接收的参数为将要释放的页框的描述符地址page和cold标志（指定是热高速缓存还是冷高速缓存）。执行操作如下：

 （十）管理区分配器

   管理区分配器是内核页框分配器的前端。

   管理区分配器必须满足以下目标：①它应当保护保留的页框池②当内存不足且允许阻塞当前进程是，它应当触发页框回收算法，一旦某些页框被释放，管理区分配器将再次尝试分配③如果可能，它应当保存小而珍贵的ZONE_DMA内存管理区。

   _ _alloc_pages()函数是管理区分配器的核心，接受以下3个参数：①gfp_mask——在内存分配请求中指定的标志②order——将要分配的一组连续页框数量的对数③zonelist——指向zonelist数据结构的指针，该数据结构按优先次序描述了适于内存分配的内存管理区。

  释放一组页框

   用来释放页框的所有内核宏和函数都依赖于_ _free_pages()函数，参数为将要释放的第一个页框的页描述符的地址（page）和将要释放的一组连续页框的数量的对数（order）。该函数执行如下操作：

二．内存区管理

  1.伙伴系统算法采用页框作为基本内存区，这适合于对大块的请求，那么如何处理对小内存区的请求呢？

  答：引入一种新的数据结构来描述在同一页框中如何分配小内存区。

  2.内碎片：由于请求内存的大小与分配给它的大小不匹配而造成的。

  3.如何解决内碎片问题？

   答：提供按集合分布的内存区大小，即内存区的大小取决于2的幂而不取决于所存放的数据大小，这样可以保证内碎片小于50%。

（一）slab分配器

  1.slab分配器模式对基于内存区分配算法有较高的效率。

  2.slab分配器模式基于以下前提：①所存放的数据可以影响内存区的分配方式②内核函数倾向于反复请求同一类型的内存区③对内存区的请求可以根据它们发生的频率来分类④数据结构的起始地址不是物理地址2的幂⑤硬件高速缓存的高性能可以尽可能的限制对伙伴系统分配器调用。

  3.包含告诉缓存的主内存区被划分为多个slab，每个slab有一个或多个连续的页框组成，这些页框中既包含已分配的对象，也包含空闲对象。

（二）高速缓存描述符

  1.每个高速缓存是由kmem_cache_t类型的数据结构来描述的，下面为几个字段：

（三）slab描述符

  1.slab描述符字段：

2.slab两个可能存放的地方：①外部slab描述符——存放在slab外部，位于cache_sizes指向的一个不适合ISA DMA的普通高速缓存中。②内部slab描述符——存放在slab内部，位于分配给slab的第一个页框的起始位置。

3.当对象小雨512MB时，slab分配器选择第二种方案。

4.如果slab描述符存放在slab外部，那么高速缓存描述符的flags字段中的CFLGS_OFF_SLAB标志被置为1，否则被置为0.

（四）普通和专用高速缓存

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

   专用高速缓存由内核的其余部分使用。

  2.普通高速缓存：①第一个高速缓存叫做kmem_cache，包含由内核使用的其余高速缓存的高速缓存描述符。Cache_cache变量包含第一个高速缓存的描述符。②另外一些高速缓存包含用作普通用途的内存区。对于每种大小，都有两个高速缓存：一个适用于ISA DMA分配，另一个适用于常规分配。

  3.准用高速缓存：由kmem_cache_create()函数创建的。

（五）slab分配器与分区页框分配器的接口

  1.当slab分配器创建新的slab时，它依靠分区页框分配器来获得一组连续的空闲页框。调用kmem_getpages()函数，等价于以下代码：

  2.参数含义：①cachep——指向需要额外页框的高速缓存的高速缓存描述符

             ②flags——说明如何请求页框。这组标志与存放在高速缓存描述符的gfpflags               字段中的专用高速缓存分配器标志相结合。

  3.调用kmem_freepages()函数可以释放分配给slab的页框：

（六）给高速缓存分配slab

  1.给高速缓存分配slab的条件：①已发出一个分配新对象的请求②高速缓存不包含任何空闲对象。

  2.给定一个页框，内核必须确定它是否被slab分配器使用。如果是，就迅速得到相应高速缓存和slab描述符的地址。

（七）从高速缓存中释放slab

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

（八）对象描述符

  1.每个对象都有一个类型为kmem_bufctl_t的一个描述符。

  2.对象描述符放在一个数组中，位于相应的slab描述符之后。

  3.分类：①外部对象描述符——存放在slab的外面，位于高速缓存描述符的slabp_cache字段指向的一个普通高速缓存中。②内部对象描述符——存放在slab的内部，正好位于描述符所描述的对象之前。

  4.数组中的第一个对象描述符描述slab中的第一个对象，以此类推。对象描述符是一个无符号整数，只有在空闲对象是才有意义。

  5.对象描述符包含下一个空闲对象在slab中的下标，实现了slab内部空闲对象的一个简单链表。

（九）对齐内存中的对象

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

  2.slab分配器所允许的最大对齐因子是4096，即页框大小。

  3.若内存单元的物理地址是字大小对齐的，那么微机对内存单元的存取会非常快。

（十）slab着色

  1.slab着色：把叫做颜色的不同随机数分配各slab

  2.几种变量：①num——可以在slab中存放的对象个数②osize——对象的大小，包括对齐的字节③dsize——slab描述符的大小加上所有对象描述符的大小，就等于硬件告诉缓存行大小的最小倍数④free——在slab内未用字节的个数。

一个slab中的总字节长度=（num×osize）+dsize+free

  3.free总是小于osize，但可以大于aln。

  4.具有不同颜色的slab把slab的第一个对象存放在不同的内存单元，同时满足对齐约束。可用颜色个数为free/aln。第一个颜色表示0，最后一个颜色表示（free/aln）-1.

  5.若用颜色col对一个slab着色，那么第一个对象的偏移量就等于col×aln+dsize字节。

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

（十一）分配slab对象

   通过调用kmem_cache_alloc()函数可以获得新对象。参数cachep指向高速缓存描述符参数flag标书传递给分期页框分配器函数的标志。该函数等价于以下代码：

（十二）释放slab对象

   kmem_cache_free()函数释放一个曾经由slab分配器分配给某个内核函数的对象。其参数为cachep（高速缓存描述符的地址）和objp（将被释放对象的地址）。

（十三）通用对象

   如果请求不频繁，就用一组普通告诉缓存来处理，高速缓存中的对象具有几何分布的大小，范围在32到131072之间。

   调用kmalloc（）函数可以得到这种类型的对象，函数等价于以下代码：

（十四）内存池

  1.一个内存池允许一个内核成分，如块设备子系统，仅在内存不足的紧急情况下分配一些动态内存来使用。

  2.内存池是动态内存的储备，只能被特定的内核成分使用。

  3.内存池能被用来分配任何一种类型的额动态内存，从整个页框到使用kmalloc（）分配的小内存区。我们一般讲内存池处理的内存单元看做“内存元素”。

  4.内存池由mempool_t对象描述，其字段如下：

  5.alloc和free方法与基本的内存分配进行交互，分别用于获得和释放一个内存元素。

三．非连续内存区管理

 1.非连续内存区管理模式：通过连续的线性地址来方位非连续的页框。

 2.这种模式的又要有点事避免了外碎片，而缺点是必须打乱内核页表。

 3.非连续内存区的大小必须是4096的倍数。

 4.Linux内核使用非连续内存区的几个方面：①为活动的交换区非配数据结构，②为模块分配空间，③给某些I/O驱动程序分配缓冲区等等。

（一）非连续内存区的线性地址

  要查找线性地址的一个空选取，可以从PAGE_OFFSET开始查找。如下

   ①内存区的开始部分包含的是对前896MB RAM进行映射的线性地址。

   ②内存区的结尾部分包含的是固定映射的线性地址。

   ③从PKMAP_BAST开始，查找用于高端内存页框的永久内核映射的线性地址。

   ④其余的线性地址可以用于非连续内存区。

（二）非连续内存区的描述符

  每个非连续内存区都对应着一个类型为vm_struct的描述符，其字段如下：

  

（三）分配非连续内存区

  1.vmalloc（）函数给内核分配一个非连续的内存区。参数size表示所请求内存区的大小。如果这个函数能够满足请求，就返回新的内存区的起始地址，否则，返回NULL指针：

2.修改内核使用的页表项，一次表明分配给非连续内存区的每个页框对应着一个线性地址，这个线性地址包含在vmalloc（）产生的非连续线性地址空间中，用map_vm_area()实现：

它的三个参数：①area——指向内存区的vm_struct②prot——已分配页框的保护位。③page——指向一个指针数组的变量的地址，该指针数组的指针指向页描述符。

（四）释放非连续内存区

  1.vfree（）函数释放vmalloc()或vmalloc_32()创建的非连续内存区，而vunmap（）函数释放vmap（）创建的内存区。

   他们使用同一个参数——将要释放的内存区的其实线性地址address

  2.vunmap（）函数接收两个参数：将要释放的内存区的起始地址的地址addr，和标志deallocate_pages。