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层会预先分配内存，当需要对象时可以直接获取，而不需要再去分配内存。