Linux 笔记

数据结构

链表

相比普遍的链表实现方式，Linux 内核的实现比较独树一帜。普通的实现是数据通过在内部添加一个指向数据的 next 或 prev 节点指针，才能串联在链表中，存储这个结构到链表里的通常方法是在数据结构中嵌入一个链表指针，如 next 或 prev。而 Linux 内核中，是将链表节点塞入数据结构。

struct list_head{
    struct list_head *next;
    struct list_head *prev;
};

struct fox {
    unsigned long tail_length;
    unsigned long weight;
    bool is_fantastic;
    struct list_head list; // 所有fox结构体形成链表
}

内核还提供了一组链表操作接口，比如 list_add() 加入一个新节点到链表中，他们都有一个统一的特点，就是只接受 list_head 结构作为参数。通过使用宏 container_of()我们可以很方便地从链表指针找到父结构包含的任何变量，因为在 c 语言中，一个给定的结构中的变量偏移在编译时地址就被 ABI 固定下来了。

通过宏 container_of()，定义一个简单的函数就可以返回包含 list_head 的父类型结构体。

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

节约两次纲领（dereference）

如果已经获得了 next 和 prev 指针，就可以直接调用内部链表函数，省下提领指针的时间。前面的所有函数仅仅是找到 next 和 prev 指针，再去调用内部函数而已。内部函数和它们的外部包装函数（上面提到的，比如 list_del(list)）同名，只是前面多加了两条下划线。比如用__list_del(prev, next) 替代 list_del(list)。

队列

Linux 中通用队列实现是 kfifo，和多数的其他队列实现类似，主要提供两个操作：enqueue（入队）和 dequeue（出队）。kfifo 对象维护了两个偏移量：入口偏移和出口偏移。入口偏移是指下一次入队时的位置，出口偏移是指下一次出队列时的位置。出口偏移总是小于入口偏移。

enqueue 操作拷贝数据到队列入口偏移位置，拷贝完后，入口偏移会加上推入的元素数目。dequeue 操作类似。当出口偏移等于入口偏移时，说明队列为空，在新数据被推入前，不可以摘取任何数据了。当入口偏移等于队列长度时，说明在队列重置前，不可再有新数据推入队列。

创建和初始化 kfifo 对象时，它将使用由 buffer 指向的 size 字节大小的内存，size 必须是 2 次幂。

映射

映射是由唯一键组成的集合，每个键必然关联一个特定的值。主要支持三个操作：Add、Remove、Lookup。

映射不仅可以由散列表组成，还可以通过自平衡二叉搜索树来存储数据，散列表可以提供更好的平均的渐进复杂度，但是二叉搜索树在最坏情况能有更好的表现（对数复杂性相比线性复杂性），且二叉搜索树同时满足顺序保证，给用户的按序遍历带来很好的性能，二叉搜索树还不需要散列函数，需要的键类型可以通过定义<=操作算子就能满足条件。

Linux 内核用的不是通用的映射，它的目标是：映射一个唯一的标识数（UID）到一个指针。除了提供三个标准的映射操作外，还在 add 基础上实现了allocate操作，这个操作不但向 map 中加入了键值对，而且还可以产生 UID。

idr 数据结构用于映射用户空间的 UID，如将 inodify watch 的描述符或 POSIX 的定时器 ID 映射到内核中相关联的数据结构上，如 inotify_watch 或 k_itimer 结构体。

二叉树

• 二叉搜索树

• 自平衡二叉搜索树

一个节点的深度是从根节点算起，到达它一共需经过的父节点数目。处于树底层的节点称为叶子结点。一个树的高度是指书中的处于最底层节点的深度。而一个平衡的二叉搜索树是一个所有叶子结点深度差不超过 1的二叉搜索树。一个自平衡二叉搜索树指在操作中都维持半平衡状态的二叉搜索树。

• 红黑树

红黑树是典型的自平衡二叉搜索树，也是 Linux 中主要的平衡二叉树数据结构。红黑树具有特殊的着色属性，遵循着六个特性，维持着半平衡结构。

1. 所有的节点要么着红色，要么着黑色。
2. 叶子节点都是黑色。
3. 叶子节点不包含数据。
4. 所有非叶子节点都有两个子节点。
5. 如果一个节点是红色，则它的子节点都是黑色。
6. 在一个节点到其叶子节点的路径中，如果总是包含同样数目的黑色节点，则该路径相比其他路径是最短的。

这意味着树中最长的路径是红黑交替节点路径，从根节点到叶子节点的最长路径不会超过最短路径的两倍。

Linux 实现的红黑树称为 rbtree，除了一定的优化外，rbtree 类似于前面描述的经典红黑树，即保持了平衡性，所以插入效率和树中节点数目呈对数关系（ O(logN) ）。rbtree 的根节点为 rb_root，其他节点由 rb_node 描述，给定一个 rb_node，可以跟踪同名节点指针来找到它的左右子节点。

数据结构的选择

• 如果对数据集合的主要操作是遍历数据，就用链表。
• 当性能非首要考虑因素，或者只需要存储相对较少的数据项，或者当你要和内核中其他使用链表的代码交互时，优先选择链表。
• 如果需要存储一个大小不明的数据集合，选择链表更合适。
• 如果需要存储大量数据，但没有执行太多次时间紧迫的查询操作，最好使用链表
• 如果代码符合生产者/消费者模式，则使用队列，特别是如果你想要一个定长缓冲。
• 如果需要映射一个UID到一个对象，就使用映射。
• 如果需要存储大量数据，并且检索迅速，最好使用红黑树。

内存管理

页

内核把物理页作为内存管理的基本单位。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 用于存放页的状态，比如这个页是不是脏的，是不是被锁定在内存中等，flags 的每一位都单独表示一个状态，至少可以同时表示 32 种不同状态。

_count 存放页的引用计数，为 -1 时标识没有被当前内核引用，那么在新的分配中就可以使用它。一般不会直接访问这个字段，而是调用 page_count() 来检查。对 page_count() 来说，当_count 为负数时，返回 0，表示页空闲，如果返回一个正整数表示页在使用。这个页可以被页缓存使用（mapping 字段指向这个页关联的 address_space 对象），或者作为私有数据（由 private 指向），或者作为进程页表中的映射。

virtual 字段存放了页的虚拟地址。有些内存不永久映射到内核地址空间上，这种情况下这个字段为 NULL，在需要的时候才动态映射这些页。

这个结构只是描述了物理页的信息，而不是描述包含在其中的数据。内核用这个结构来管理系统中的所有页，因为内核需要知道一个页是否空闲，如果页已经被分配，还需要知道谁拥有这个页。拥有者可能是用户空间进程，也可能是动态分配的内核数据，还可能是静态内核代码或页高速缓存等。

区

区的出现是为了处理一些特定的限制：由于硬件限制，内核不能对所有页一视同仁，有些页位于内存中特定物理地址上，所以不能将其用于一些特定任务。此外，Linux 将系统的页划分为区后，形成不同的内存池，就可以根据用途来进行分配了。区的划分并没有任何物理意义，只是内核为了管理页面而采取的一种逻辑上的分组。

• 一些硬件只能用特定内存地址来访问 DMA。
• 一些体系结构的内存的物理寻址范围比虚拟寻址范围大得多，这样就有一些内存不能永久映射到内核空间上。

Linux 主要使用四种区：

• ZONE_DMA 这个区包含的页能用来执行 DMA 操作。在 x86 体系结构上，由于某些 PCI 设备只能在 24 位地址空间内执行 DMA 操作，所以 ISA 设备不能在整个 32 位的地址空间中执行 DMA，因为 ISA 设备只能访问物理内存的前 16MB。因此 ZONE_DMA 在 x86 上包含的所有页都在 0~16MB 的内存访问内。
• ZONE_DMA32 和 ZONE_DMA 类似，但是只能被 32 位设备访问
• ZONE_NORMAL 包含的都是能正常映射的页
• ZONE_HIGHEM 包含高端内存，其中的页并不能永久映射到内核地址空间。能否直接映射取决于体系结构，在 32 位 x86 系统上，ZONE_HIGHMEM 为高于 896M 的所有物理内存，其所在内存也被称为高端内存，而其余内存就是低端内存。在其他体系结构上，由于所有内存都被直接映射，所以 ZONE_HIGHMEM 为空。

区	描述	物理内存
ZONE_DMA	DMA 使用的页	<16MB
ZONE_NORMAL	正常可寻址的页	16~896MB
ZONE_HIGHMEM	动态映射的页	>896MB

当可供分配的资源不够时，内核会去占用其他可用区的内存。在 x86-64 体系结构下，由于它可以寻址和处理的 64 位内存空间较大，所以没有 ZONE_HIGHMEM 区，所有的物理内存都处于 ZONE_DMA 和 ZONE_NORMAL 中。

页的分配和释放接口

底层页分配的核心函数是 alloc_pages，它分配 1<<order 个连续的物理页，并返回指向第一个页的 page 结构体的指针。

struct page *alloc_pages(gfp_t gfp_mask, unsigned int order)

可以通过 page_address 获取它的逻辑地址，这个函数返回一个指向给定页当前所在的逻辑地址的指针。

void * page_address(struct page *page)

__get_free_pages 的作用类似，但是它是直接返回请求的第一个页的逻辑地址。

unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)

获取全是填充零的页，可以调用 get_zeroed_page，它的实现与__get_free_pages 类似，但是在返回前，会将所有数据填充为 0，保障系统安全。

unsigned long get_zeroed_page(unsigned int gfp_mask)

释放页可以使用以下函数。如果传递了错误的 struct page 或地址，用了错误的 order 值，这些都可能导致系统崩溃。

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

kmalloc()

kmalloc() 常用于以字节为单位分配内核内存，它与用户空间的 malloc() 一族函数非常类似，但是多了个 flags 参数。函数返回一个指向内存块的指针，至少有 size 大小，而且所分配的内存在物理上是连续的。

void * kmalloc(size_t size, gfp_t flags)

gfp_mask 标志常见于低级页分配函数和 kmalloc() ，可以分为三类：行为修饰符、区修饰符以及类型。

• 行为修饰符表示内核应该如何去分配所需的内存，在某些特定场景下只能使用特定方式分配内存。如中断处理程序要求内核在分配内存的时候不能睡眠。
• 区修饰符表示从哪分配内存。由于内核将物理内存分成了若干个区，每个区用于不同的目的，区修饰符指明了要从哪个区中分配。
• 类型标志组合了行为修饰符和区修饰符，将各种可能用到的组合归纳为不同类型，相当于已经加工好了，简化了修饰符的使用。

因为一般只使用类型修饰符就够了，所以只展示常见的类型标志：

标志	描述
GFP_ATOMIC	这个标志用在中断处理程序、下半部、持有自旋锁以及其他不能睡眠的地方
GFP_NOWAIT	与 GFP_ATOMIC 类似，不同之处在于，调用不会推给紧急内存池。这就增加了内存分配失败的可能性。
GFP_NOIO	这种分配可以阻塞，但是不会启动磁盘 I/O。这个标志在不能引发更多磁盘 I/O 时能阻塞 I/O 代码，会导致不好的递归
GFP_NOFS	这种分配在必要时可能阻塞，也可能启动磁盘 I/O，但是不会启动文件系统操作。这个标志在你不再启动一个文件系统的操作时，用在文件系统部分的代码中
GFP_KERNEL	这是一种常规的分配方式，可能会阻塞。这个标志在睡眠安全时用于进程上下文 diamante 中，为了获得调用者所需的内存，内核会尽力而为。这个标志应当是首选标志
GFP_USER	这是一种常规的分配方式，可能会阻塞。这个标志用于为用户空间进程分配内存
GFP_HIGHUSER	这是从 ZONE_HIGHMEM 进行分配，可能会阻塞。这个标志用于为用户空间分配内存
GFP_DMA	这是从 ZONE_DMA 进行分配，由获取能供 DMA 使用的内存的设备驱动程序使用，通常与以上某个标志组合使用。

内核中最常见的标志是 GFP_KERNEL，是普通优先级，由于调度可能阻塞，所以只能用在可以重新安全调度的进程上下文中，这个标志没有对请求的内存进行约束，所以内存分配成功的可能性比较高。

另一个极端的标志是 GFP_ATOMIC，表示不能睡眠的内存分配，它的调用需要满足很严格的限制。即使没有足够的内存块可以获取，内核也不能让调用者睡眠，因此它分配成功的机会较小。即使如此，在当前代码不能睡眠时（如中断处理程序，软中断和 tasklet），也只能选择 GFP_ATOMIC。

夹在俩中间的是 GFP_NOIO 和 GFP_NOFS，以这两个标志进行的分配可能会阻塞，但是他们会避免某些其他操作的执行。它们分别用于某些低级块 I/O 或文件系统的代码中，设想，如果文件系统的代码中需要分配内存，没有使用 GFP_NOFS，这种分配可能会引起你更多文件系统的操作，又导致了更多的分配，引发不期望发生的递归，最终导致死锁。总的来说，这两个标志用的还是极少的。

GFP_DMA 标志表示分配器必须满足 ZONE_DMA 进行分配的请求，这个标志用于需要 DMA 的内存的设备驱动中，一般和 GFP_ATOMIC 或 GFP_KERNEL 结合使用。

kfree() 用于释放 kamlloc() 分配的内存块，但是不可用于释放其余分配函数分配的内存，或者已经释放过的内存，否则会造成严重后果。

void kfree(const void *ptr)

vmalloc()

类似于 kmalloc()，但是 vmalloc() 分配的内存虚拟地址是连续的，而物理地址则无须连续。这也是用户空间分配函数的工作方式：由 malloc() 返回的页在进程的虚拟地址空间内是连续的，但并不能保证它们在物理 RAM 中也是连续的。vmalloc() 通过分配非连续的物理内存块，再修正页表，把内存映射到逻辑地址空间的连续区域中来实现这一点。

大多数情况下，只有硬件设备需要得到物理地址连续的内存，很多体系结构上，硬件设备都存在于内存管理单元之外，根本不能理解什么是虚拟地址，所以它们用到的任何内存去都必须是物理上和逻辑地址上都连续的块。对内核而言，所有内存看起来都是逻辑上连续的。

很多内核代码都用 kmalloc() 来获得内存，主要出于性能的考虑。vmalloc() 为了讲物理上部连续的页转换为虚拟地址空间上连续的页，必须专门建立页表项。而且必须一个一个进行映射（因为物理上是不连续的），这会导致比直接内存映射大得多的 TLB 抖动。因为这些原因，vmalloc() 仅有在不得已时才会使用，典型的是为了获取大块内存。如当模块被动态插入内核时，就把模块装载到由 vmalloc() 分配的内存上。

void * vmalloc(unsigned long size)

函数返回一个指向 size 大小逻辑上连续的内存块的指针。要释放的话需要调用 vfree()

void vfree(const void *addr)

slab 分配器

为了便于数据的频繁分配和回收，通常会使用空闲链表——相当于对象高速缓存，快速存储频繁使用的对象类型。

在内核中，空闲链表的主要问题之一是不能全局控制。当可用内存变得紧缺时，无法通知到每个空闲链表，让其收缩缓存大小以释放一些内存。实际上，内核对空闲链表无感（因为是编程人员实现，而不是内核中实现的）。为了解决这一问题，Linux 内核提供了 slab 分配器，它扮演了通用数据结构缓存层的角色。

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

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

每个 slab 都包含一些对象成员（被缓存的数据结构）。每个 slab 处于三种状态之一：满、部分满或空。一个满的 slab 没有空闲的对象，一个空的 slab 没有被分配的对象。而部分满的 slab 中有些对象已分配，有些对象还是空闲的。当内核的某一部分需要一个新对象时，先从部分满的 slab 中分配，如果没有部分满的 slab，就从空的 slab中进行分配。如果没有空的 slab，就需要创建一个 slab了。这种策略能减少内存碎片。

以 inode 为例，它是磁盘索引节点在内存中的体现，会被频繁创建和释放，很有必要使用 slab 分配器来管理，因此 struct inode 就由 inode_cachep 高速缓存来分配。这种高速缓存由一个或多个 slab 组成，每个 slab 包含尽可能多的 struct inode 对象。当内核需要时，就从部分满或空的 slab 中返回一个指向已分配但是未使用的结构的指针，当内核用完后，slab 分配器会将该对象标记为空闲。

每个高速缓存都使用 kmem_cache 结构表示，该结构包含三个链表：slabs_full、slabs_partial 和 salbs_empty，都存放在 kmem_list3 结构中。这些链表包含了高速缓存中的所有 slab。

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

值得一提的是，slab 的描述符也可以放在 slab 里。此外，slab 分配器还可以创建新的 slab，具体是调用__get_free_pages()，以下是一个简化版的函数：

static 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;
}

函数使用__get_free_pages 为高速缓存分配足够多的内存，通过或运算将高速缓存需要的缺省标志传递到 flags 参数上，分配的大小为 2 的幂次方，存储在 cachep->gfporder 中。当需要释放内存时，针对特定的高速缓存页调用的是 kmem_freepages，最终调用的是 free_pages。

slab 层的关键在于避免频繁分配和释放页，因此，只有在当给定的高速缓存部分中既没有满也没有空的 slab 时才会调用页分配函数，只有在以下情况时才会调用释放函数：

• 当可用内存变得紧缺时，系统试图释放出更多内存以供使用。
• 当高速缓存显式地被撤销时。

slab 层的管理是基于每个高速缓存的基础上，通过提供给整个内核一系列简单的接口完成的，通过这些接口可以创建和撤销新的高速缓存，并在高速缓存中分配和释放对象。高速缓存和其内的 slab 的复杂管理完全可以通过 slab 层的内部机制来处理。

如果要创建一个新的高速缓存，调用的接口应该是 kmem_cache_create，它的第一个参数存放了高速缓存的名字，第二个参数是高速缓存中每个元素的大小，第三个参数是 slab 内第一个对象的偏移，用于确保在页内进行特定的对齐，通常使用 0 来标准对齐就行了。flags 用于控制高速缓存的行为，具体的标志下文再介绍。最后一个参数 ctor 是高速缓存的构造函数，当有新的页追加到高速缓存时，它才会被调用。实际上这个参数已经被抛弃了，Linux 内核的高速缓存不使用构造函数，所以可以设为 NULL。

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

控制高速缓存的标志：

• SLAB_HWCACHE_ALIGN 这个标志命令 slab 层把一个 slab 内的所有对象按高速缓存行对齐。这样做的好处是防止了伪共享问题：两个或多个对象尽管位于不同的内存地址，但映射到相同的高速缓存行。这样设置可以提高性能，但是很吃内存，对齐越严格，浪费的内存就越多，因此只有在对于频繁使用的高速缓存，且代码本身对性能又要求严格的情况下才会设置。
• SLAB_POISON 将 slab 用已知的值（a5a5a5a5，一个神秘值，常用于检测未初始化的内存，当一个指针指向 a5a5a5a5 时，很可能这个指针没初始化或已损坏）填充，即所谓的"中毒"，有利于对未初始化内存的访问。
• SLAB_RED_ZONE 导致 slab 层在已分配的内存周围插入"红色警戒区"来探测缓存越界。
• SLAB_PANIC 当分配失败时会提醒 slab 层，在要求分配只能成功时使用，比如系统启动初分配一个 VMA 结构的高速缓存。
• SLAB_CACHE_DMA 命令 slab 层使用可以 DMA 的内存给每个 slab 分配空间，只有分配的对象用于 DMA，且常驻于 ZONE_DMA 区时才需要这个标志。

kmem_cache_destroy 用于撤销一个高速缓存，通常在创建了自己的高速缓存的模块注销的代码中被调用。在调用前必须保证高速缓存中的所有 slab 都为空，以及在调用这个函数的过程中和调用结束后都不会访问这个高速缓存。

int kmem_cache_destroy(struct kmem_cache *cachep)

kmem_cache_alloc 用于获取对象，这个函数从给定的 cachep 中返回一个指向空闲对象的指针，如果 slab 中没有，那么 slab 必须通过 kmem_getpages 获取新的页，并用 flags 标记，此处应该用到 GFP_KERNEL 或 GFP_ATOMIC。

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

kmem_cache_free 用于释放对象，并将其返回给原先的 slab，给定的 objp 会被重新标记为空闲。

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

书中给定了一个 task_struct 的例子，取自 kernel/fork.c。首先内核用一个全局变量来存放指向 task_struct 高速缓存的指针，在内核初始化期间，fork_init() 会创建高速缓存。

struct kmem_cache *task_struct_cachep;

task_struct_cachep = kmem_cache_create("task_struct", sizeof(struct task_struct),
                                    ARCH_MIN_TASKALIGN, SLAB_PANIC | SALB_NOTRACK, NULL);

ARCH_MIN_TASKALIGN 定义的值与体系结构相关，通常是 L1 高速缓存的字节大小。SLAB_PANIC 在这用是因为这是系统操作必不可少的高速缓存，如果没有 SLAB_PANIC，就得自己检查返回值了。

当 fork 被调用时，do_fork->dup_task_struct 中会使用 kmem_cache_alloc 的获取一个 task_struct 对象。当进程描述符要被释放时，在 free_task_struct 中会调用 kmem_cache_free。

高端内存映射

高端内存是 32 位体系结构下，物理内存中的概念，指的是物理内存中 896M 直接映射区以上的内存区域，具体可以见一文了解 OS-内存布局。

永久映射

要映射一个 page 结构到内核地址空间，可以用 kmap，它在高端内存或低端内存都能用，如果 page 结构对应的是低端内存中的一页，函数只会单纯返回该页的虚拟地址。如果页在高端内存，还得简历一个永久映射，再返回地址。

void *kmap(struct page *page)

由于允许永久映射的数量是有限的，在不需要高端内存时，应该使用 kunmap 解除映射。

void kunmap(struct page *page)

临时映射

当必须创建一个映射，而当前上下文又不能睡眠时，可以使用临时映射，也叫原子映射。有一组保留的映射，可以存放新创建的映射，内核可以原子地把高端内存中的一个页映射到某个保留的映射中。通常用于中断处理程序，因为获取映射时不会阻塞。

可以通过 kmap_atomic 创建一个临时映射

void *kmap_atomic(struct page *page, enum km_type type)

通过 kunmap_atomic 取消映射，实际上这个函数没做什么事，因为 kmap 禁止内核抢占，且映射对每个处理器都是唯一的，只有在下一个临时映射到来前上一格临时映射才有效，内核完全可以忘记这个临时映射，下一个原子映射将自动覆盖前一个映射。

void kunmap_atomic(void *kvaddr, enum km_type type)

分配函数选择

如果需要连续的物理页，可以使用某个低级页分配器或 kmalloc。对于中断处理程序或其他不能睡眠的代码段，应该传入标志 GFP_ATOMIC，对于其余的代码，可以使用 GFP_KERNEL。

如果想从高端内存分配，就使用 alloc_pages，它返回一个指向 struct page 结构的指针，而不是一个虚拟地址，因为这个高端内存可能没被映射，要获得真正的指针，就要调用 kmap，将高端内存映射到内核的逻辑地址空间。

如果不需要物理上连续的页，只需要逻辑上连续的页，应该使用 vmalloc，虽然它有一定的性能损失。

如果要创建和撤销很多大的数据结构，考虑建立 slab 高速缓存，slab 层给每个处理器维护一个对象高速缓存，能极大地提高对象分配和回收的性能，slab 层会预先分配内存，当需要对象时可以直接获取，而不需要再去分配内存。

进程地址空间

Linux 是一个基于虚拟内存的操作系统，内核除了管理本身的内存外，还得管理用户空间中进程的内存，也就是系统中每个用户空间进程所看到的内存，即进程地址空间。所有进程之间都以虚拟内存的方式共享内存，对于一个进程而言，它房屋可以访问整个系统的所有物理内存，且它拥有的地址空间也可以远远大于系统物理内存。

地址空间

进程地址空间由进程可寻址的虚拟内存组成，在现代操作系统中，通常使用平坦的一个独立的连续区间来作为地址空间范围。

内存地址是一个给定的值，在地址空间范围之内，如 4021f000，这个值指的是进程地址空间中的一个特定的字节。尽管进程可以寻址所有的虚拟内存，但并不代表它有权访问所有的虚拟内存。而哪些能被进程访问的虚拟内存的地址区间，又被称为内存区域，通过内核，进程可以为自己的地址空间动态添加或减少动态区域。

每个内存区域也具有相关的权限，如对相关进程有可读、可写、可执行属性，如果一个进程访问了不在有效范围内的内存区域，或以不正确的方式访问了有效地址，内核会终止该进程，并返回“段错误”信息。

内存区域包含了各种内存对象，如：

• 可执行文件代码的内存映射，称为代码段（text section）。
• 可执行文件的已初始化全局变量的内存映射，称为数据段（data section）。
• 包含未初始化全局变量，即 bss 段的零页（block started by symbol，被赋予默认值–零值，所以不用再申请时显示初始化，减少了空间浪费）。
• 用于进程用户空间栈的零页的内存映射。
• 每一个诸如 C 库或动态连接程序等共享库的代码段、数据段和 bss 也会被载入进程的地址空间。
• 任何内存映射文件。
• 任何共享内存段。
• 任何匿名的内存映射。

实际上就是一文了解内存映射中提到的内存映射区，进程中任何的有效地址都必须在唯一的区域中，且这些区域之间不可以相互覆盖。

内存描述符

内核使用内存描述符来标识进程的地址空间，它包含了和进程地址空间有关的全部信息。下面列举了一些重要且典型的字段：

struct mm_struct {
    struct vm_area_struct *mmap;        // 内存区域链表
    struct rb_root mm_rb;               // VMA 形成的红黑树
    struct vm_area_struct *mmap_cache;  // 最近使用的内存区域
    unsigned long free_area_cache;      // 地址空间第一个空洞
    pgd_t *pgd;                         // 页全局目录
    atomic_t mm_users;                  // 使用地址空间的用户数
    atomic_t mm_count;                  // 主使用计数器
    int map_count;                      // 内存区域的个数
    spinlock_t page_table_lock;         // 页表锁
    struct list_head mmlist;            // 所有 mm_struct 形成的链表
    unsigned long start_code;           // 代码段起始地址
    unsigned long end_code;             // 代码段结束地址
    unsigned long start_data;           // 数据段起始地址
    unsigned long end_data;             // 数据段结束地址
    unsigned long start_brk;            // 堆起始地址
    unsigned long brk;                  // 堆结束地址
    unsigned long start_stack;          // 进程栈的首地址
    unsigned long rss;  //              // 所分配的物理页
    ...
}

mm_users 字段主要用来记录共用此命名空间的线程数量，如果是俩线程共享该地址空间，那么 mm_users 值为 2。在 linux 创建线程时，会有如下操作，代码中仅仅更新了 mm_user 的值，并使子进程和父进程共享 mm_struct 结构体（如果不是创建线程，则子进程会重新申请 mm_struct 结构体）。

if (clone_flags & CLONE_VM) {
    // current 是父进程，tsk 在 fork() 执行期间是子进程
    atomic_inc(&current->mm->mm_users);
    tsk->mm = current->mm;
}

mm_count 则主要记录对此 mm_struct 结构体的引用情况，比如在内核线程调度进来的时候，它会借用上一个进程的地址空间（虽然它不会对该地址空间操作），此时 mm_count 就会增加 1。从另一个层面来理解的话，可以理解为 mm_count 是以进程为单位的，而 mm_users 则是以线程为单位的。

mmap 和 mm_rb 俩不同的数据将结果描述对象是相同的，在一文了解 os-内存映射中提到，这是用于管理该地址空间中所有内存区域的一种方式，前者以链表形式存放，后者以红黑树形式存放，内核为了内存区域上各种不同操作都能获得高性能，所以同时使用了这两种数据结构，此处不再概述。

所有的 mm_struct 结构体都通过自身的 mm_list 字段连在一个双向链表中，恰巧符合上文数据结构中 Linux 链表实现的描述。链表的头节点是 init_mm 内存描述符，代表 init 进程的地址空间。

在进程描述符 task_struct 中，mm 字段存放这该进程使用的内存描述符，通常在 fork 中利用 copy_mm() 来拷贝父进程的内存描述符，而子进程的 mm_struct 实际上是通过 allocate_mm() 宏从 mm_cachep slab 缓存中获取的。

在描述 mm_users 字段时笔者引入了一个代码段，它描述了 clone() 创建新进程的一个过程。在调用 clone 时设置了 CLONE_VM 标志，目的是父进程希望与子进程共享地址空间，即我们常讲的线程，这也是进程和 Linux 中所谓线程间本质上的唯一区别，线程对内核来说仅仅是一个共享特定资源的进程而已。

引用计数

前文交代了 mm_users 与 mm_count 的意义，在进程退出时，内核调用 exit_mm()，其中通过 mmput() 减少内存描述符中的 mm_users 用户计数，当用户计数降为 0 时，会调用 mmdrop()，减少 mm_count 使用计数。如果使用计数也降为 0，说明内核中已经没有对象引用该文件描述符了，所以会调用 free_mm() 宏通过 kmem_cache_free() 将 mm_struct 解耦提归还给 mm_cachep slab 缓存。

mm_struct 与内核线程

内核线程没有地址空间，自然也没有 mm_struct，所以它对应的 task_struct 中的 mm 字段为 NULL，恰恰说明了内核线程是没有上下文的。

内核线程不会去访问任何用户空间的内存，它们没有页，也不需要页表，但是访问内核时确实也需要一部分数据，所以它们会直接使用前一个进程的内存描述符。

当一个进程被调度时，该进程 mm 字段指向的地址空间被加载到内存中，task_struct 的 active__mm 会更新，指向新的地址空间。当一个内核线程被调度时，内核会发现它的 mm 字段为 NULL，所以会保留前一个进程的地址空间，active_mm 指向前一个进程的地址空间，在内核线程需要的时候就能通过前一个进程的地址空间去使用一些关于内核内存相关的信息。

虚拟内存区域

内存区域由 vm_area_struct 结构体描述，通常简称 VMA。而常说的内存区域其实与虚拟内存区域是一个东西，它如前文所讲，描述了指定地址空间内连续区间上的一个独立内存范围，内核将每个内存区域作为一个单独的内存对象管理，每个区域都有属于自己的属性（如访问控制权限）。实际上，每一个区域都代表不同类型的内存区域（如内存映射文件或进程用户空间栈）。下面给出一些主要的属性

struct vm_area_struct {
    struct mm_struct *vm_mm;                // 相关的 mm_struct 结构体
    unsigned long vm_start;                 // 区间首地址
    unsigned long vm_end;                   // 区间尾地址
    struct vm_area_struct *vm_next;         // VMA 链表
    pgprot_t vm_page_prot;                  // 访问控制权限
    unsigned long vm_flags;                 // 标志
    struct rb_node vm_rb;                   // 树上该 VMA 的节点
    struct list_head anon_vma_node;         // anon_vma 项
    struct anon_vma *anon_vma;              // 匿名 VMA 对象
    struct vm_operations_struct *vm_ops;    // 操作表，关联对应的操作方法
    struct file *vm_file;                   // 被映射的文件（如果存在）
    void *vm_private_data;                  // 私有数据
    ...
}

每个 VMA 对齐相关的 mm_struct 来说都是唯一的，即使俩独立的进程将同一个文件映射到各自的地址空间，他们分别都有一个 VMA 来标志自己的内存区域。换句话说，当俩线程共享一个地址空间时，它们就共享该地址空间中的所有 VMA。

和物理页的访问权限不同，flags（即 VMA 标志）反映了内核处理页面需要遵循的行为准则。常见的 VM_READ、VM_WRITE 和 VM_EXEC 标志内存区域中可读、可写和可执行权限。

VM_SHARD 指明该内存区域包含的映射是否可以在多进程间共享，如果设置了这个标志，说明其为共享映射，否则称为私有映射。

比较有意思的是 VM_SEQ_READ 标志，它暗示了内核应用程序对映射内容执行有序的读操作，这样内核就可以用预读机制（在读数据时有意按顺序多读取一些本次请求外的数据，希望多读的数据能够很快被用到）来优化效率。VM_RAND_READ 则相反，对于这种标志的区域，内核可以减少或取消文件预读。

vm_ops 是函数操作表，由 vm_operations_struct 结构体表示，定义了指定内存区域相关的操作函数表，函数操作表字段的设置兼容了 vm_area_struct 通用对象的作用，操作表中描述的是对特定对象实例的特定方法。

struct vm_operations_strut {
    void (*open) (strut vm_area_struct *);
    void (*close) (strut vm_area_struct *);
    int (*fault) (strut vm_area_struct *, struct vm_fault *);
    int (*page_mkwrite) (strut vm_area_struct *vma, struct vm_fault *vmf);
    int(*access) (struct vm_area_struct *, unsigned long, void *, int, int);
}

创建地址区间——mmap() 与 do_mmap()

内核使用内核函数 do_mmap() 创建一个新的内存区域，如果该内存区域与一个已存在的内存区域相邻，且它们都有相同的访问权限时，两个区间会合并为一个。do_mmap 的定义如下

unsigned long do_mmap(struct file *file, unsigned long addr, unsigned long len, 
    unsigned long prot, unsigned long flag, unsigned long offset)

映射由 file 指定的文件，具体映射是从文件中偏移 offset 处开始，长为 len 的范围内存的数据。如果 file 为 NULL 且 offset 为 0，说明是匿名映射，如果指定了 file 和 offset，那么为文件映射。addr 用于指定搜索空闲区域的起始位置，是可选项。prot 指定内存区域内页面的访问权限。flag 指定 VMA 标志，上文有提到。

当新创建的内存区域不与其余内存区域相邻时，内核会从 vm_area_cachep slab 缓存中分配一个 vma 结构体，并使用 vma_link() 将新分配的内存区域添加到地址空间的内存区域链表和红黑树中，还得更新 mm_struct 的 total_vm 字段，然后才返回新分配内存区域的起始地址。

在用户空间中可以通过 mmap 系统调用（mmap2()）来调用 do_mmap，与最原始的 mmap 相比，它的最后一个参数更改为了使用页面偏移而非字节偏移来指定偏移量，这样可以映射更大的文件和更大的偏移位置。

最原始的 mmap 在内核中已经没有对应的实现，实际上在 c 库中最终也是调用的 mmap2，mmap 的作用只是将字节偏移转换为页面偏移，底层还是用的 mmap2。

do_munmap() 从特定进程地址空间中删除指定地址区间，用户空间可以通过系统调用 munmap() 来使用，munmap() 则只是对 do_munmap 的简单封装。

int do_munmap(struct mm_struct *mm, unsigned long start, size_t len)

页表

应用程序操作的对象是映射到物理内存上的虚拟内存，但处理器直接操作的却是物理内存。当应用程序需要访问一个虚拟地址时，必须将虚拟地址转换为物理地址，处理器才能解析地址访问。而地址转换需要查询页表，即需要将虚拟地址分段，使得每一个虚拟地址都作为索引指向页表，页表项则指向下一级页表或最终页面。

Linux 中使用三级页表完成地址转换，利用多级页表能够节约地址转换占用的空间。如果用静态页表来实现页表，即使不存放数据，光是页表也会占用大量空间。Linux 对所有体系结构（包括不支持三级页表的体系结构）都用三级页表管理，因为三级页表结构可以利用最大公约数思想——按照需要在编译时简化使用页表的三级结构，如只使用两级。最大公约数思想我理解为追求共同点，即兼容，使用三级结构时，可以兼容使用二级的情况。

顶级页表是页全局目录 PGD，包含一个 pgd_t 类型（等同于 unsigned long）的数组，PGD 表项指向二级页目录中的表项 PMD。二级页表是中间页目录 PMD，是一个 pmd_t 类型的数组，表项指向 PTE 中的表项。PTE 简称页表，包含了 pte_t 类型的页表项，该页表项指向物理页。

查页表这件事比较追求效率，所以一般由硬件完成。此外多数结构还实现了一个翻译后缓冲器（translate lookaside buffer，TLB，好久没听译名都忘了 TLB 原本的含义…），TLB 为虚拟地址到物理地址映射的硬件缓存，当请求访问一个虚拟地址时，处理器会先检查 TLB 中是否包含该映射，如果有则直接命中，立即返回，否则才通过页表搜索物理地址。

每个进程都有自己的页表，线程会共享页表。mm_struct 中的 pgd 字段指向的就是进程的页全局目录，操作和检索页表的时候都得用 page_table_lock 来锁住页表防止竞态条件。所以多线程的情况下，线程切换免去了切换进程时上下文切换得切换页表导致 TLB 失效的开销，这恰恰是多线程场景优于多进程场景的原因之一。书中（当时是 2.6）还描述了将来的改进可能包括在写时拷贝的方式共享页表，来消除 fork() 操作中页表拷贝带来的消耗，可以更快提升 fork() 的效率，避免大页表阻塞 fork() 操作。这一点其实在 22 年的时候就有计划了Introduce Copy-On-Write to Page Table，而且貌似有相关论文已经发表 Effects of copy-on-write memory management on the response time of UNIX fork operations，但是对一些属性的引用关系和计数会比较复杂，所以实现起来也相对复杂。

页高速缓存与页回写

页高速缓存实现磁盘缓存，主要用来减少对磁盘的 I/O 操作，具体的讲是通过将磁盘中的数据缓存在物理内存中，将对磁盘的访问转变为对物理内存的访问。页回写是指将页高速缓存中的变更数据刷新回磁盘的操作。

磁盘高速缓存存在的原因有二：

• 一方面，访问磁盘的速度（ms 级别）远远低于访问内存的速度（ns 级别），相差了几个数量级。
• 另一方面是根据临时局部原理，数据一旦被访问就很有可能在短期内再次被访问到。临时局部原理能保证，如果第一次访问数据时缓存它，那么极有可能在短期内再次被高速缓存命中。由于内存访问比磁盘快，加上临时局部原理的保证，使得磁盘的内存缓存为系统存储性能带来很大提升。

缓存手段

页高速缓存由内存中的物理页组成，其包含的内容对应磁盘上的物理块。页高速缓存大小可以动态调整。

写缓存

缓存一般被实现为三种策略之一：

1. 不缓存。高速缓存不去缓存任何写操作，当对一个缓存中的数据片进行写时，将直接跳过缓存，写到磁盘中，同时使得缓存中的数据失效。如果后续读操作进行时，需要重新从磁盘中读数据。这也是典型的只读缓存处理策略，笔者在 geekcache 中主要也是使用这种方式。对于常见的缓存来说，这种策略却很少使用，因为这种策略不仅不缓存写操作，还需要额外功夫使得缓存数据失效。
2. 写操作自动更新内存缓存，同时也更新磁盘文件。也被称为写透缓存，因为写操作会立刻穿透缓存到磁盘中。书中的描述比较简略，这种应该是同步直写策略，会降低缓存的访问性能，增加缓存响应延迟。但是能保证缓存数据时刻与磁盘数据同步，而且不需要让缓存失效，同时实现也比较简单。
3. 回写策略，也是 Linux 所采用的。写操作直接写到缓存中，后端存储不会立刻更新，而是将页高速缓存中被写入的页标记为脏页，并加入到脏页链表中，由回写进程周期性将脏写链表中的页写回到磁盘，可以保证缓存数据与磁盘数据的最终一致性。这个策略会有数据丢失的风险，而且实现复杂度高，但是能方便以后更多时间内合并更多的数据和再一次刷新，减少磁盘 I/O 次数。

缓存淘汰策略

作用是为更重要的缓存项腾出位置，或者是收缩缓存大小，腾出内存给其他地方使用。

1. 最近最少使用

经典的 LRU 算法，跟中每个页面的访问踪迹（或者说按照访问时间为序），来回收最老时间戳的页面。它假定缓存的数据越久没被访问过，则越不可能近期再被访问，而最近访问的最有可能被再次访问。对于许多文件被访问一次后就不再被访问的场景，LRU 起不到啥明显的效果，当然，内核也并不能预测到哪些文件只会被访问一次，但是它可以知道过去这个文件被访问了多少次。

2. 双链策略

对我来说是个比较陌生的概念，可能之前在哪里也看到过。Linux 实现的是一个修改过的 LRU，维护了两个链表：活跃链表和非活跃链表。处于活跃链表上的页面不会被淘汰，而在非活跃链表上的页面可以被淘汰的。活跃链表中的页面必须得从非活跃链表中晋升。两个链表都被伪 LRU 规则维护：页面从尾部加入，从头部移除，像队列一样。两个链表中还得维持平衡，当活跃链表中页面超过了非活跃链表，那么活跃链表的头页面会被移回非活跃链表。双链策略解决了传统 LRU 算法对仅一次访问的窘迫，而且也更加简单的实现了伪 LRU 语义，也被称为 LRU/2，更普遍的 n 个链表被称为 LRU/n。

Linux 页高速缓存

address_space

参考

• 《Linux 内核设计与实现》
• linux 进程地址空间 mm_struct 结构体中 mm_user 和 mm_count 的疑问