[读书笔记] Linux内核动态内存分配

Book：Daniel P. Bovet, Marco Cesati, Understanding the Linux Kernel（中译版，陈莉君等）,  O'Reilly

---

在Linux中内核获取动态内存的方式相对进程是相当直接了当的。作为操作系统中优先级最高的成分，其内存请求不会被推迟，也不会插入任何针对编程错误的保护措施。其内存分配按其对象大致可分为三类：1. 连续页框；2. 专用或通用对象；3. 非连续的内存区。如果所请求的内存区得以满足，将返回一个页描述符地址或线性地址；否则，返回NULL。

第一类：连续页框【Buddy Allocator】

Buddy算法将内存划分为2的幂次方个分区，并使用best-fit方法来分配内存请求。当用户释放内存时，就会检查buddy块，查看其相邻的内存块是否也已经被释放。如果是的话，将合并内存块以最小化内存碎片。

__rmqueue(*zone, order)：此函数用于在管理区zone中找到一个适配当前请求大小为2^order的最小空闲块。
在管理区描述符中维护着一个类型为free_area的数组，其第k个元素标识所有大小为2^k的空闲块（其中free_area中的free_list双向循环链表通过lru字段链接这些空闲块对应的起始页框页描述符，nr_free记录这些空闲块的个数）。__rmqueue()函数从所请求order的链表开始，扫描每个可用块链表：
       若找到合适的空闲块，则从链表中删除它，并减少此free_area中的nr_free值，后执行expand函数，将找到块中多出的部分切割大小为2的幂次的块，插入相应的free_area中；若直到循环结束还找不到（free_area全空），则返回NULL。

buffered_rmqueue()：此函数应用“每CPU”页框高速缓存per_cpu_pages，当只需要分配一个页（order=0）时，首先在缓存中查找，如果缓存中已经没有预先分配好的内存页了，则从内存中取一些页放在缓存中，再从缓存中分配（若缓存中页框个数高过上界，则释放一些到Buddy系统中）；对于大于2个页的情况，则直接调用__rmqueue()进行分配。

__alloc_pages(gfp_mask, order, *zonelist)：此函数是Buddy Allocator的核心。gfp_mask标识指明如何寻找空闲页，如要求页框处于ZONE_DMA内、一次内存分配失败将不会产生警告信息等；order传入请求分配的内存大小；*zonelist按优先序列描述了适于内存分配的内存管理区。__alloc_pages函数循环扫描zonelist，若内存尚有盈余，调用buffered_rmqueue()进行分配；否则，调用以下策略充盈内存后进行分配：1. 回收页框；2. 消耗为内存不足预留的页；3. 阻塞当前进程；4. 杀死另外的进程释放一些内存。当然没有办法的办法就是返回NULL提示调用者内存分配失败。
常用的alloc_pages宏通过依次调用__alloc_pages实现。
__get_free_pages也通过调用alloc_pages实现，但它返回的是页的线性地址。

第二类：专用或通用对象【SLAB/SLUB/SLOB Allocator】

SLAB算法是面向对象的。内核对对象的初始化是十分耗时的，尤其对于小通用对象，甚至超过了对其进行分配和释放内存所需的时间。那么当它被析构时，就不应该将内存释放回一个全局的内存池，而是将内存保持为针对特定目的而初始化的状态，这样后续的内存分配就不需要再执行初始化函数了。SLAB算法就是基于以上思想提出的。下图给出了SLAB的组织结构。
       
kmem_cache定义了一个要管理的给定大小的对象池；
其包含了一个slab列表，有三种slab：slab_full（完全分配）、salbs_partial（部分分配）、slabs_empty（空）；
每一个slab列表都指向一些slab，slab通常是一段连续的内存块，被分配给多个object。
当slab不足时，需再分配内存初始化为slab；当空闲slab过多时，则释放一些内存到全局内存池中。

SLUB在保留SLAB基本思想的同时， 简化了kmem_cache，slab 等相关的管理数据结构，摒弃了SLAB 分配器中众多的队列概念，并针对多处理器、NUMA 系统进行优化，从而提高了性能和可扩展性并降低了内存的浪费；
SLOB则针对嵌入式系统，是内存受限系统中的一个SLAB 缓存实现。为保证内核模块的无缝迁移，其接口API函数与SLAB无异。

kmem_cache_alloc(*cachep, flags)：此函数从一个命名的缓存中分配一个对象。若当前缓存为空，则调用kmem_cache_file向缓存中填充本地高速缓存并获得一个空闲对象。flags字段标识内存分配的具体细节，如为用户分配内存、从高端内存中分配等。

kmem_cache_zalloc(*cachep, flags)：此函数与kmem_cache_alloc类似，但它在对象返回前对其进行清除操作。

kmalloc(size, flags)：此函数是内核中最常用的内存管理函数。如果对存储区的请求不频繁，就用一组普通高速缓存来处理，无需创建新slab缓存。kmalloc没有为要从中分配对象的某个slab 缓存命名，而是循环遍历可用缓存来查找可以满足大小限制的缓存。找到之后，就调用__cache_alloc（kmem_cache_alloc的核心）分配一个对象。

第三类：非连续的内存区

当对内存区的请求不是很频繁，那么通过连续的线性地址访问非连续的页框这种分配方式就会十分有意义。这种做法避免了外碎片，但必须打乱内核页表。此外，非连续内存区还提供了另一种是用高端内存页框的方法。

get_vm_area(size, flags)：此函数在线性地址VMALLOC_START和VMALLOC_END之间查找一个空闲的线性地址空间。它首先调用kmalloc()为非连续内存区对应的vm_struct类型描述符分配一个内存区；再通扫描纪录所有vm_struct的vmlist链表来查找一块满足（size+安全区间）大小要求的线性地址空间（每个vm_struct都记录其占据的VMALLOC可用线性地址空间，那么它们之间的空洞就是当前可用的）。如果成功，则返回该描述符地址，否则释放该描述符，返回NULL。

vmalloc(size)：此函数为内核分配一个非连续内存区，并将其映射到一个连续的线性地址空间。它首先调用gei_vm_area创建一个新的描述符，并返回分配给这个内存区的线性地址；然后调用kmalloc()分配一组连续页框用于存储一个页描述符指针数组，并调用memset()初始化这些指针为NULL；接着重复nr_page次调用alloc_page()分配非连续的页框，并将其页描述符指针存入上一步分配好的数组area->pages中去；最后调用map_vm_area()修改内核页表，为此非连续内存区的每个页框建立页表层级目录，最后在页表中标识所其对应的线性地址，这些线性地址取自第一步get_vm_area找到的区域。
vmalloc_32()函数与vmalloc()类似，但它只从ZONE_NORMAL和ZONE_DMA内存管理区中分配页框，不使用高端内存页框。
2.6版本内核中的vmap()也与vmalloc()类似，但它不分配页框，而是映射非连续内存区中已经分配的页框。