Linux 内核

2017-03-29 #linux

处理器的活动范围

内核空间的进程上下文、中断上下文
用户空间

Kernel 版本命名规则

比如 2.6.0 分别为：主版本号、从版本号、修订号。

从版本号为奇数表示开发版本、为偶数表示稳定版本。

编译、安装内核

make config    # 配置。或者用 menuconfig、xconfig、gconfig、oldconfig、defconfig
make [-jn]     # -jn 代表 n 个作业同时编译，一个处理器上一般运行 1~2 个作业。
make modules_install    # 具体安装目录跟体系结构和引导程序相关

menuconfig 是基于 ncurse 库的图形界面。

编译会生成 System.map 文件，它是内核符号表。

内核开发的特点

不能访问 C 库
必须用 GNU C
没有用户空间那样的内存保护机制
不能用浮点数
堆栈很小
时刻注意同步和并发（因为支持异步中断、抢占和 SMP）
考虑移植性

内联 (inline) 函数

函数会在调用的位置上展开，避免函数调用和返回带来的开销。GNU C 编译器支持内联函数。

分支优化

GCC 可优化分支代码，根据条件是否经常出现加上 likely() 或 unlikely() 即可。

if(unlikely(foo))
	;

内核的调度对象

是线程、非进程。

进程

处于执行期的程序以及它所包含的资源的总称。

任务队列与进程描述符

任务队列就是 task_struct 结构（进程描述符）的链表。

进程描述符的存放地址

存放在各个进程内核栈的尾端 (低地址)。它包在 thread_info 结构里面，是为了方便汇编代码计算它的偏移，它的第一项是 task_struct 结构的指针，实际空间由 slab 分配器分配。

进程的 ID 与范围

PID 是一个 pid_t 类型，实际就是 int 类型，但默认最大值是 32768，即 short int 范围。每个 PID 都存放在各自的进程描述符中。

cat /proc/sys/kernel/pid_max

进程的状态

5 种状态：运行、可中断、不可中断、僵死、停止。

运行态：表示正在执行或者在运行队列中等待执行。
可中断态：表示正在睡眠，即被阻塞了，在等待某些条件的达成（比如 I/O），一旦达成就会被设置为运行态。
不可中断态：与可中断态类似，只是不会被信号唤醒。
僵死态：表示进程已经结束，等待父进程调用 wait4() 来释放描述符。
停止态：不能运行，一般是收到某些信号导致或者处于调试期间。

set_task_state(task, state)    // 设置进程状态
set_current_state(state)       // 当前进程还可用 current 宏

写时拷贝 (COW)

COW = Copy On Write。

调用 fork() 后内核并不复制整个进程地址空间，而是让父子进程共享同一个拷贝。只有在需要写入的时候，数据才会被复制，使各个进程有自己的拷贝。

vfork() 与 fork() 的区别

fork() 用于父子进程运行同一个程序的不同分支，vfork() 是为了创建一个子进程来运行别的程序。

因此，考虑到性能，vfork() 不拷贝父进程的页表项，父进程将被阻塞，子进程在父进程空间运行，直到退出或调用 exec() 后父进程才能运行，这期间子进程不能写入数据。

创建线程

本质跟创建进程一样，但要指出需要共享的资源，即在调用 clone() 时加上参数标志，vfork() 和 fork() 最终都是调用 clone()。

内核线程 (kernel thread)

在后台执行一些任务，没有独立的地址空间，只能在内核空间运行，不能切换到用户空间去。其它和普通进程一样，可以被调度和抢占。

创建内核线程：内核线程只能由其它内核线程创建——通过调用 kernel_thread()。

终止进程的过程

一般发生在调用 exit() 后，先释放进程资源，然后向父进程发送信号，进程状态被设置为僵死，最后主动挂起。但是进程描述符会一直保留，直到父进程调用 wait4() 函数以后，所有资源才被销毁。

父进程先退出

如果父进程先退出，就给子进程在当前线程组内找一个线程作为父亲，如果不行，就让 init 做父进程。

抢占与让步

被调度程序强制挂起叫抢占，进程主动挂起叫让步。

抢占又分为用户抢占和内核抢占。

用户抢占：发生在从系统调用或中断处理程序返回用户空间时。内核有一个 need_resched 标志来表示是否需要重新调度，当进程时间片用完后，定时器处理程序就会设置该标志。每当从系统调用或中断处理程序返回用户空间时都会检查该标志，如果被设置，内核就会执行调度函数。

内核抢占：内核抢占发生在内核执行任务时。每个进程都有一个 preempt_count 技术器，上锁时加 1，释放锁时减 1。当从中断处理程序返回内核时会检查 need_resched 标志和 preempt_count 的值，如果需要调度且没有加锁，则会发生内核抢占。此外，内核中的任务阻塞、在内核中调用 schedule() 或者内核代码再次具有可抢占性时都会发生抢占。

进程类型

I/O 消耗类型、CPU 消耗类型。

判断是哪种类型，就看它大部分时间是在睡眠还是在运行，运行时间长过睡眠时间就是 CPU 消耗型，反之则是 I/O 消耗型。

进程优先级

即 nice 值和 priority 值。priority 才是真正的进程优先级，但却可以用 nice 值来调整 priority 值。

nice 值范围是 -20~19，默认为 0，值越大优先级越低。priority 值范围是 0~99。

系统会根据进程运行时间和类型等因素来动态调整 nice 值，然后再周期性的把它加到 priority 上，所以 nice + priority 就总共有 140 个优先级。

时间片用完怎么办？

用完了就不能再运行，等到所有进程都耗尽时间片后，会再次重新计算。

时间片没必要一次用完，可以分几次用，主动放弃处理器时间即可。

当一个进程的时间片耗尽时，就被移到过期数组，并重新计算时间片。当队列中的全部进程都过期后，只要交换过期数组和活跃数组的指针即可实现切换。

优先级越高则时间片越大。使用 CPU 过多，优先级会降低，反之则会提升。

新建的子进程和父进程将均分父进程的剩余时间片。

运行队列、优先级数组、优先级队列

每个处理器有一个运行队列，每个进程在同一时刻只能属于一个运行队列。

每个运行队列有两个优先级数组，一个活跃的，一个过期的（即时间片已用完）。

每个优先级数组中都有一个优先级队列和一个优先级位图。

优先级队列总共包含 140 个队列，对应每个优先级。当某队列中有进程处于运行态时，优先级位图中的相应位就会被置1，这样可以减少查找的时间。

调度过程

调度函数是 schedule() 。当进程主动挂起或者被抢占时都会执行该程序。

在活动优先级数组中找到第一个被置 1 的位，然后找到相应队列中的第一个进程执行。

这就是为什么优先级数值越大优先级反而越低，因为它是从位图的前面往后找的。

睡眠和唤醒的过程

睡眠时，进程被标记为休眠状态，从运行队列移到等待队列。唤醒时，正好相反，进程被设置为运行状态，从等待队列移到运行队列。

休眠状态有两种——可中断和不可中断，区别在于可中断的休眠进程能够被信号唤醒（比如定时器），而不可中断的只能等待条件满足（比如 I/O）。

多处理器负载均衡

由 load_balance() 函数实现。在 schedule() 执行时，只要当前运行队列为空就会调用它，或者每隔一段时间被定时器调用。

考虑到缓存命中的问题，一般是先转移过期数组中的进程，然后才会选择活动数组，而且先转移高优先级的进程。理想目标是让每个处理器的负载尽量相同。

上下文切换的过程

由 context_switch() 函数处理，它主要是先调用 switch_mm() 将虚拟内存映射到新进程，再调用 switch_to() 切换处理器状态。

实时调度策略

Linux 提供两种实时调度策略，SCHED_FIFO 和 SCHED_RR。

SCHED_FIFO 严格按优先级顺序执行，不使用时间片，一个执行完成或主动让出后才可以执行下一个，高优先级可以随时抢占低优先级。

SCHED_RR 是带有时间片的 SCHED_FIFO，该时间片用于在同一优先级的任务之间互相轮转，其它与 SCHED_FIFO 相同。

处理器绑定

进程允许在哪些处理器上执行是由 cpus_allowed 掩码值决定的（也叫处理器亲和力），每个处理器占 1 位，默认全部置1。可设置掩码值将进程绑定到指定的 1 个或多个处理器上执行。

子进程会继承父进程的该掩码值。

主动放弃处理器时间

内核代码调用 yield() 或者用户代码调用 sched_yield() 即可主动放弃处理器时间。

区别就是 yield() 要先判断进程处于可执行状态后才会调用 sched_yield()。

放弃后该进程被放到过期队列中，如果是实时进程则被放到队列最后。

系统调用

系统调用 xxx() 在内核中被定义为 sys_xxx()。

每个系统调用都有唯一的编号，一旦分配就不可改变，记录在 sys_call_table 中。

在 x86 上，通过软中断 int $0x80 产生异常，并执行第 128 号异常处理程序，即系统调用处理程序 system_call()。

系统调用号通过 eax 寄存器传入，还可传入 5 个参数，分别用 ebx,ecx,edx,esi,edi 寄存器。如果参数超过 5 个，可用一个单独寄存器指向用户地址空间，在该空间内包含所有参数。

返回值在 eax 寄存器中。错误码会写入 errno 全局变量，可用 perror() 函数获取对应的错误文本。

x86 后来增加了 sysenter 指令，比 int 更快、更专业。

增加系统调用

在系统调用表 sys_call_table 末尾增加一项，比如 .long sys_foo。把系统调用号加到 <asm/unistd.h> 中，比如 #define _NR_foo 283。系统调用必须编译进内核而非模块，可以放到 kernel/ 目录下的相关文件中。

系统调用需要 C 库支持，因此访问自定义的系统调用只能使用 Linux 上的一组宏 __syscalln() ，n=0~6 表示参数个数。该宏实际就是帮助申明一个 foo 函数，然后把参数塞到寄存器里，最后调用 283 号系统调用。

#define _NR_foo 283;
__syscall0(long, foo);
a = foo();

中断处理机制

分为上半部和下半部。中断需要立即响应和快速返回，因此不得不将处理过程切分为两个部分，上半部分即中断处理程序，工作时禁止中断，只做有严格时限的工作，其它工作则被推迟到下半部去执行，且会尽量开中断执行。

注册&释放中断处理程序

使用 request_irq() 函数注册中断处理程序，参数包括中断号、处理程序、标志、自定义设备名、设备 ID。

不可中断标志 (SA_INTERRUPT)：表示中断处理程序运行时禁止所有中断，默认情况下仅屏蔽正处理的那条中断线，其它都是激活的。

随机数标志 (SA_SAMPLE_RANDOM)：表示该设备的中断间隔时间是随机的，可被用于产生随机数。

共享标志 (SA_SHIRQ)：表示多个中断程序共享该中断线，且都必须都设置该标志。

设备 ID：释放时用于识别共享中断线上的处理程序。

request_irq() 可能睡眠，因此不能在中断上下文或不允许阻塞的代码中调用。

释放中断处理程序调用 free_irq() 函数，参数是中断号和设备 ID。

释放后中断线被禁用，共享中断线则需要删除最后一个处理程序后才禁用。

为什么 request_irq() 可能睡眠？

注册时，内核需要在 /proc/irq/ 目录下创建以中断号命名的目录及相关文件。该操作的调用关系是 proc_mkdir() -> proc_create() -> kmalloc()，而 kmalloc() 函数是可以睡眠的。

编写中断处理程序

static irqreturn_t foo(int irq, void *dev_id, struct pt_regs *regs) {
	//...
}

只有在共享中断线上才使用 dev_id 参数，其它两个已经没用了。

如果是共享中断线上的无关处理程序则返回 IRQ_NONE，正确处理则返回 IRQ_HANDLED，或者返回 IRQ_RETVAL(x)。

中断处理程序与重入

中断处理程序无需是可重入的。因为中断处理程序执行时，相应的中断线在所有 CPU 上都是禁止的。

共享中断线上的处理程序执行过程

内核接收到中断后，会依次调用该中断线上的所有中断处理程序，因此无关的处理程序应该立即返回，且返回值是 IRQ_NONE。

中断上下文

当执行一个中断处理程序或下半部时，内核处于中断上下文中。中断上下文中不能调用会睡眠的函数。

查看中断信息

cat /proc/interrupts

禁止&激活中断

local_irq_disable();       // 禁止当前处理器上的中断
local_irq_enable();        // 激活

local_irq_save(flags);     // 同上，且会保存标志位
local_irq_restore(flags);

disable_irq(irq);          // 禁止所有处理器上的中断 (要等到当前中断处理程序执行完毕后才返回)
disable_irq_nosync(irq);   // 禁止所有处理器上的中断 (立即返回)
enable_irq(irq);
synchronize_irq(irq);

irqs_disable();            // 判断当前处理器上的中断是否被禁用
in_interrupt();            // 判断是否处于中断上下文（包括下半部）
in_irq();                  // 判断是否正执行中断处理程序（不含下半部）

disable 几次就必须 enable 相同次数后才能打开中断。另外，不应该禁止共享中断线。

中断处理过程

发生中断后，CPU 自动跳转到指定地址执行，该处汇编代码先将指定 IRQ 值压入栈，然后调用 do_IRQ() 函数，IRQ 就被当做参数传入。在调用该函数的前后，会保存和恢复被中断任务的寄存器。

下半部机制

有 3 种：软中断、tasklet、工作队列。

软中断

系统静态分配大小为 32 的软中断结构 (softirq_action) 数组，每个软中断结构包含一个处理程序和一个参数指针，内核将逐个处理被唤起的软中断，调用它的处理程序。

系统已分配的软中断有 6 个，tasklet 占了 2 个，一个高优先级的和一个普通的，网络接收和发送共占 2 个，SCSI 占 1 个，定时器占 1 个。

软中断之间不会抢占，因为在运行处理程序时当前 CPU 上的软中断会被禁止，但却可以且只能被中断处理程序抢占。

软中断不能休眠，且必须快速返回。

软中断（包括相同类型的）可以在其它处理器上同时执行，因此需要锁，大部分软中断处理程序通过绑定 CPU 等技巧来避免显式加锁，提升性能。

中断处理程序会在返回前唤起它的软中断，返回后内核会立即执行软中断。在 ksoftirqd 内核线程中也会检查并执行。有些代码，比如网络子系统也会检查和执行。最终，都是调用 do_softirq() 来处理。

ksoftirqd：每个处理器都有一个辅助处理软中断（包括 tasklet）的内核线程。因为软中断可能会不断的唤起自己，如果一直处理它，用户进程会饥饿，如果只处理一次，软中断又会饥饿。因此，折中的方案是在软中断大量出现时唤醒一组内核线程来执行，但优先级很低 (nice=19)，因为不能和用户进程抢夺资源。

注册软中断：将新的软中断结构插入到数组中的指定位置。因为是从数组起始位置逐个往后执行的，所以根据需要自己确定优先级。

唤起 (raise) 软中断：即设置为待处理状态。然后在下一次运行 do_softirq() 时就会被处理。

tasklet

tasklet 基于软中断实现，系统默认注册了两个处理 tasklet 的软中断，一个高优先级的和一个普通的，高优先级的先执行。这两个 tasklet 在每个 CPU 上都有一个 tasklet_struct 结构的链表，该结构可以静态编译或动态创建，包含处理函数和参数指针。这两个 tasklet 都有对应的调度程序，可以将新 tasklet_struct 插入其中一个链表（为了缓存命中，总是在调度它的 CPU 上执行）并设置为待处理状态，然后唤醒所在的软中断。

tasklet 有“运行”、“被调度”两种状态，“被调度”表示等待运行，CPU 在执行前会检查 tasklet 必须是“被调度”状态且是激活的，然后将状态改为“运行”后才执行，防止在 SMP 中被并发调度。

tasklet_struct 中有一个引用计数器，用来表示它是激活或禁止，只有为 0 时才可执行。tasklet_disable() 和 tasklet_enable() 会影响该值。

工作队列

系统默认创建了一个 events 类型的工作队列 (workqueue_struct)，该工作队列在每个 CPU 上都有一个队列 (cpu_workqueue_struct) 和一个内核线程 (events/n，n 代表 CPU 号)。当有工作 (work_struct) 被插入队列时，相应的内核线程就会被唤醒，当队列中的所有工作都处理完后该内核线程又继续睡眠。

工作结构中有一个待处理标志，已处理完的工作会从队列中删除，且该标志被设置为 0。

工作结构中还有一个延时定时器，可将工作执行时间延后。

用户可以根据自己的需要创建其它类型的工作队列，同样的，该工作队列在每个 CPU 上都会有一个队列和一个内核线程。

工作在（内核的）进程空间执行，可以睡眠，但是不能访问用户空间。

下半部机制的选择

如果需要睡眠则选工作队列，因为它的工作在进程空间执行，否则选 tasklet 或软中断，这两者中又优先选择 tasklet，因为它操作更简单。

竞争与同步的基本概念

临界区：访问和操作共享数据的代码段。

竞争条件：两个线程处于同一个临界区中。

同步：避免并发和防止竞争条件。

并发与并行：并发是多个任务在同一时间间隔内执行，而并行是多个任务在同一时刻一起执行。前者类似一个人同时做几件事，后者类似多个人一起做事。

内核中可能造成并发执行的原因：中断、软中断、tasklet、内核抢占都可能打断当前任务。内核进程睡眠会导致重新调度。还有 SMP 并行执行。

应该锁什么：是给数据加锁，非代码。给代码加锁不易理解。最好把锁放到数据的结构体里面。

死锁：所有资源都被占用，且所有进程都在等待对方释放这些资源。

加锁粒度的影响：当锁争用严重时，加锁太粗会降低可扩展性；而锁争用不明显时，加锁太细会加大系统开销。

内核的同步方法

原子操作、自旋锁、读写自旋锁、信号量、读写信号量、完成变量、BKL、禁止抢占、Seqlock、顺序和屏障。

原子操作

保证指令在执行过程中不被打断。原子即不可切割的意思。

内核提供了针对整数和二进制位的原子操作接口。

整数操作包括初始化、读取、设置、加/减 n、递增/递减、加减后检查是否为 0 等等。

二进制位操作包括设置位、清除位、反转位、返回指定位的值、从指定位置查找第一个被设置或未被设置的位等等。

自旋锁 (spin lock)

只能被一个可执行线程持有。当线程试图获得一个已被占用的自旋锁时，就会一直忙循环，直到它可用（也可以加参数立即返回）。

自旋锁特别浪费处理器时间，所以不应该长时间持有，最好小于两次上下文切换的耗时。

自旋锁不可递归，想得到自己正持有的自旋锁，就会被锁死。

在中断处理程序中使用自旋锁时一定要先禁止本地中断。

不能睡眠。

想调试自旋锁就需要开启内核的配置选项 CONFIG_DEBUG_SPINLOCK 。

// 常规使用方式
spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;
spin_lock(&mr_lock);
/* your code */
spin_unlock(&mr_lock);


// 如果想在禁止中断的同时请求锁，就用下面的方式
unsigned long flags;
spin_lock_irqsave(&mr_lock, flags);
/* your code */
spin_unlock_irqrestore(&mr_lock, flags);


// 如果能确定在加锁前中断是激活的，就用下面的方式
spin_lock_irq(&mr_lock);
/* your code */
spin_unlock_irq(&mr_lock);


spin_lock_init();       // 动态创建自旋锁
spin_try_lock();        // 如果已被占用就立即返回
spin_is_locked();       // 检测状态

读-写自旋锁：允许多个读，但只能有一个写。

rwlock_t mr_rwlock = RW_LOCK_UNLOCKED;
read_lock(&mr_rwlock);
/* your code */
read_unlock(&mr_rwlock);

write_lock(&mr_rwlock);
/* your code */
write_unlock(&mr_rwlock);


read_lock_irq();            // write 有一样的 4 个接口
read_lock_irqsave();
read_unlock_irq();
read_unlock_irqrestore();
write_trylock();
rw_lock_init();
rw_is_locked();

信号量

允许 n 个锁持有者，获取锁加 1，释放锁减 1，如果 down 之后的计数大于等于 0 就获取锁，小于 0 就被放入等待队列。

可自定义持有者的数量，如果为 1 就是互斥信号量。

信号量比自旋锁的开销更大，但处理器利用率更好。

不能在持有自旋锁时获取信号量，因为信号量会睡眠。

中断上下文只能用自旋锁，要睡眠只能用信号量。

static DECLARE_MUTEX(mr_sem);          // 静态创建互斥信号量
if(down_interruptible(&mr_sem)){
	// ...
}
/* your code */
up(&mr_sem);


static DECLARE_SEMAPHORE_GENERIC(name,count);    // 静态创建信号量
sema_init(sem,count);     // 初始化动态创建的信号量
init_MUTEX(sem);          // 初始化动态创建的互斥信号量
init_MUTEX_LOCKED(sem);   // 初始化后计数设置为0，即上锁状态
down(sem);                // 如果已被占用就进入不可中断睡眠状态
down_trylock(sem);

读-写信号量：可以同时有多个读者，但写者只能有一个。

#include <linux/rwsem.h>

static DECLARE_RWSEM(mr_rwsem);    // 静态创建
init_rwsem(sem)                    // 初始化动态创建的读-写信号量

down_read(&mr_rwsem);
/* your code */
up_read(&mr_rwsem);

down_write(&mr_rwsem);
/* your code */
up_write(&mr_rwsem);

down_read_trylock();    // 非阻塞接口
down_write_trylock();
downgrade_writer();     // 写锁转为读锁

完成变量

睡眠并等待特定事件发生，然后被唤醒。

DECLEAR_COMPLETION(mr_comp);   // 通过宏静态创建并初始化
init_completion(comp);         // 动态创建并初始化
wait_for_completion(comp);     // 等待指定的完成变量接收信号
complete(comp);                // 发信号唤醒正在等待的任务

BKL

大内核锁，新代码中已不再使用。

它是一个全局自旋锁、可以睡眠（当睡眠时锁被丢弃，唤醒时又重新获得，所以不会发生死锁）、可以递归、可用于进程上下文。

lock_kernel();
/* your code */
unlock_kernel();

kernel_locked();     // 是否被持有

Seqlock

获取写锁会增加序列值，获取读锁则返回当前序列值，如果读操作前后的序列值相同，表示读操作没有被干扰且读取的数据是正确的，否则重复读取，直到前后值一致。

Seqlock 对写者更有利。

不应该睡眠，否则读者会一直循环。

seqlock_t mr_seq_lock = SEQLOCK_UNLOCKED;

// 写操作
write_seqlock(&mr_seq_lock);
/* your code */
write_sequnlock(&mr_seq_lock);

// 读操作
unsigned long seq;
do{
	seq = read_seqbegin(&mr_seq_lock);
	/* your code */
}while(read_seqretry(&mr_seq_lock, seq));

禁止抢占

持有自旋锁时就是禁止抢占的，但有些数据是每个处理器独有的，不需要锁，用禁止抢占操作会更好。

禁止抢占可以嵌套调用，且可以调用任意次，但禁止和激活次数要匹配。

preempt_disable();       // 增加抢占计数，禁止抢占
preempt_enable();        // 减少抢占计数，为0时将检查调度
preempt_enable_no_resched();   // 同上，但不检查调度
preempt_count();         // 返回抢占计数

屏障 (barrier)

可确保指令按顺序执行。

编译器和处理器为了提高效率，可能对读写指令重新排序。某些情况下，必须通过屏障保证指令不被重新排序。

屏障分为读屏障和写屏障。

系统时间

节拍率 (tick rate)：即时钟中断的频率。系统定时器能以固定频率触发时钟中断，该频率可设定。

节拍 (tick)：两个时钟中断的间隔时间。

HZ：一个宏，表示节拍率，默认值为 1000。

jiffies：一个全局变量 (unsigned long)，表示自系统启动以来产生的节拍总数。因此系统启动的秒数就等于 jiffies/HZ。

实时时钟 (RTC)：RTC 用来持久存储系统时间，和 CMOS 集成在一起，包括 BIOS 的保存和设置都是由同一个电池供电。内核通过读取 RTC 来初始化墙上时间，该时间存放在 xtime 变量中。

实际时间：即墙上时间 xtime 的值，表示自 UTC 时间 1970-01-01 00:00:00 以来经过的秒数。它是个结构体，包含秒和纳秒。读写 xtime 必须使用 xtime_lock 锁，它是个 seqlock。从用户空间获取该值用 gettimeofday()，对应的系统调用是 sys_gettimeofday()。

系统定时器：通过可编程中断时钟 (PIT) 可周期性的触发中断。

jiffies 回绕

不要直接比较 jiffies 值，使用 time_after(x,y), time_before(x,y) 等一系列宏来比较。它们将 unsigned long 变成 long 后再比较，利用了最高位的符号位。

时钟中断处理程序

do_timer() 函数会：

递增 jiffies 值
更新进程耗时统计值和剩余时间片
处理已到期的动态定时器
更新墙上时钟 xtime

动态定时器

到达指定时间后自动执行指定的函数，然后该定时器被自动销毁。

使用动态定时器：创建并初始化一个定时器，填充过期时间（绝对节拍数）、函数和参数，然后激活定时器。可以修改已激活定时器的过期时间，或者在过期前删除它。

定时器在时钟中断发生后，作为软中断在下半部执行。

volatile 关键字

每次访问时都从内存获取该变量的值，防止编译器优化后从寄存器取数据，保证取到最新的值。

延迟执行

// 忙等待
unsigned long delay = jiffies + 10;      // 延迟 10 个节拍，或者用 n*HZ 表示 n 秒
while(time_before(jiffies,delay))
	;                                    // cond_resched();  允许重新调度，这样更好


udelay();                // 微妙级延迟
mdelay();                // 毫秒级延迟
schedule_timeout();      // 睡眠直到延时耗尽才被唤醒 (参数为节拍数，或者用 n*HZ 表示秒)

内存管理单元

页 (Page)：32 位一般是 4K，64 位一般是 8K。

区 (Zone)：为了方便管理，内核将页划分为三个不同的区。ZONE_DMA 区的页可执行 DMA 操作，ZONE_NORMAL 区的页能正常映射，ZONE_HIGHMEM 区的页是高端内存，不能永久映射到内核空间。

内存分配&释放

分配&释放页

用 alloc_pages() 可分配连续的物理页并返回 page 对象，再用 page_address() 将 page 对象转为第一个页的逻辑地址。或者用 __get_free_pages() 可直接返回第一个页的逻辑地址。如果只需要一页，可以用 alloc_page() 或 __get_free_page() 分配。get_zeroed_page() 也只分配一页并返回逻辑地址，但会将该页清 0。

用 __free_pages() 或 free_pages() 释放连续多页，用 free_page() 释放一页。
分配&释放块

使用 kmalloc() 可分配指定大小的内存，其中的标志参数可以是行为修饰符、区修饰符和类型标志的组合。

行为修饰符：表示分配时是否可睡眠、是否可启动磁盘 I/O 等等。

区修饰符：表示从哪个区分配。

类型标志：表示是否可阻塞等。

释放内存块用 kfree()。

vmalloc() 分配内存的虚拟地址是连续的，但物理地址不要求连续。kmalloc() 则确保物理地址连续（虚拟地址自然也连续）。

slab 分配器

内核中常用的数据结构都是固定大小的，为了加速分配和防止产生内存碎片，抽象出一个 slab 层，由它来分配和管理常用数据结构（也称为对象）。

首先创建一个特定对象的 cache 结构，一个 cache 可包含多个 slab，每个 slab 都是若干物理连续的页，slab 空间被划分为若干个对象空间。

slab 只有全满、部分满、全空三种状态。当一个 cache 中的 slab 全满后，可以再调用 kmem_getpages() 分配更多 slab 并加入 cache 中。释放则用 kmem_freepages()。

从用户角度来说，对象是从 cache 中分配的——虽然它只是维护 slab 信息的一个结构体。

slab 描述符可以在 slab 之外另行分配，也可以放在 slab 自身最开始的地方。

kmem_cache_create();     // 创建 cache
kmem_cache_destroy();    // 销毁 cache
kmem_cache_alloc();      // 分配对象空间
kmem_cache_free();       // 释放对象空间

中断栈

每个进程都有 1 个页的内核栈专门供中断处理程序使用。

历史上，每个进程都有 2 个页的内核栈，供进程和中断一起使用，即中断处理程序使用被中断进程的内核栈。但是长时间运行后碎片不断增加，要找到两个未分配的连续页越来越困难，因此 2.6 内核引入选项可以设置内核栈为单页，这时中断栈也就独立出来了，即进程内核栈和中断栈分开且各占 1 个页。

内核没有防范栈溢出的机制，因此它是悄无声息的发生的，且影响很大，最先波及的就是 thread_info 结构，因为它在栈的末端，可能会导致宕机或删除用户数据。

高端内存映射

在 x86 体系上，高于 896M 的物理内存都是高端内存，高端内存的页被映射到 3G~4G 线性地址空间。

永久映射

使用 kmap() 将指定 page 结构映射到内核地址空间，如果该页位于低端内存则直接返回虚拟地址，如果位于高端内存则建立永久映射后再返回地址。

该函数可以睡眠，所以只能用于进程上下文。

永久映射的数量是有限的。

使用 kunmap() 可解除映射。
临时映射

如果要建立映射而当前上下文又不允许睡眠时，就只能用临时映射，也叫原子映射。

使用 kmap_atomic() 建立临时映射，kunmap_atomic() 解除映射。

建立映射时有一个类型参数用来说明映射的目的。

它使用的是一组保留映射，当禁止内核抢占时，新的映射可能直接覆盖老的映射。

每 CPU 数据

每 CPU 数据一般存放在数组中，用 CPU 号当数组索引。

使用方式一般是先通过 get_cpu() 返回 CPU 号并禁止内核抢占，然后处理数组元素 a[n]，最后用 put_cpu() 激活内核抢占。

禁止内核抢占是因为如果其它处理器抢占并重新调度了代码，这个 cpu 号就没用了；或者别的任务抢占了代码，就可能并发访问同一个数据，处于竞争状况。

使用期间不可以睡眠，因为等你醒来时可能已经到别的 CPU 上去运行了。

每 CPU 数据既可以编译时分配也可以运行时动态分配。在模块中不能使用编译时分配的每 CPU 变量，因为链接器会将它们放在一个特殊的段 (.data.percpu) 中。

每 CPU 数据的好处是可以减少数据锁定和缓存失效。

虚拟文件系统 (VFS)

该抽象层使用户可以直接用 open(),read(),write() 这样的系统调用而无需考虑具体文件系统和存储介质。

VFS 中的主要对象类型：超级块对象 (super_block)、索引节点对象 (inode)、目录项对象 (dentry)、文件对象 (file)。

超级块对象代表一个已挂载的文件系统；索引节点对象代表一个文件；路径中的每一个部分都是一个目录项对象，它可以代表一个目录或普通文件；文件对象代表由进程打开的文件。它们内部都有一个操作对象，包含所有可用操作。

超级块的操作：所有操作都是针对索引节点和文件系统。新建/销毁/读取/变脏/释放索引节点、将索引节点写入磁盘、将超级块写入磁盘、将文件系统元数据写入磁盘、禁止修改文件系统并替换超级块、文件系统解锁、获取文件系统状态、重新挂载文件系统、清除索引节点及相关数据、中断挂载（比如 NFS）。

索引节点的操作：所有操作都是用来管理目录项中的文件或目录。为目录项对象新建索引节点、在指定目录中寻找索引节点、创建软/硬链接、从目录中删除索引节点、在目录中创建/删除目录、在目录中创建特殊文件、移动文件、读取符号链接的内容、跟踪符号链接找到它指向的索引节点、检查索引节点所代表的文件是否允许特定访问模式（比如 ACL）、设置/获取/删除目录项的特殊属性、索引节点变更通知。

目录项的操作：所有操作都是针对目录项对象本身。判断目录项对象是否有效、为目录项生成散列值、删除/释放目录项、释放目录项的索引节点。

目录项缓存 (dcache)：放入缓存中可加快查找。包括被使用的目录项链表、最近被使用的双向链表。

文件的操作：所有操作都是针对文件本身。偏移、读取文件到缓冲、写缓冲到文件、同步的读/写、返回目录列表中下一个目录、poll()、ioctl()、文件映射到内存、打开/冲刷/释放/同步/加锁文件等等。

VFS 相关的其它对象类型：文件系统类型 (file_system_type)、挂载点 (vfsmount)、files_struct、fs_struct、namespace。

每个文件系统类型对象中都包含一个超级块对象链表。挂载点对象中包含挂载的位置和挂载的文件系统的超级块。files_struct、fs_struct、namespace是与进程相关的，每个进程中都有它们的指针。files_struct 包含进程打开的所有文件的描述符。fs_struct 包括 root 安装点对象、pwd 目录项对象、默认的文件访问权限等。namespace 用于单进程命名空间，每个进程都看到唯一挂载的文件系统。

块 I/O 层

块：是文件系统的抽象，只能基于块来访问文件系统。

块大小：必须是扇区大小和 2 的整数倍，且不超过页的大小。

块缓冲 (block buffer)：每个缓冲区对应一个块，相当于磁盘块在内存的表示。每个缓冲区都有描述符，被称作缓冲区头 (buffer head)。

bio 结构体：它主要包含一个 bio_vec 结构的链表，每个 bio_vec 结构内包含页面、偏移和大小。bio 结构将分散的内存区域表示为一个完整的缓冲区。

块 I/O 的对象：早期的块 I/O 对象是缓冲区头 (buffer head)，所以对大块数据的 I/O 请求必须按块分割，然后再组合；而bio 结构体可以将若干的内存小区域聚合成一个缓冲区，因此以它作为块 I/O 对象时，请求不需要再额外的分割。

请求队列：每个块 I/O 的请求 (request) 都被放入请求队列 (request_queue) 中。

I/O 调度程序：负责提交 I/O 请求的子系统。

减少磁盘寻址时间的方法：合并或排序请求。

常用调度算法：Linus 电梯 -> 最终期限 I/O 调度 -> 预测 I/O 调度。

Linus 电梯即按照平常的电梯模式，循环的从前往后执行链表上的请求，并交叉处理读和写请求。但是大块的 I/O 请求可能让后面的请求产生饥饿，因此最终期限 I/O 调度为每个请求增加了超时时间。但是频繁的在读和写请求之间切换增加了寻址次数，也就降低了系统吞吐量，因此预测 I/O 调度又增加了预测功能，以减少寻址次数。

虚拟内存区域 (VMA)

即进程地址空间中的一个连续且独立的区间，比如代码段、数据段、BSS 段等等。在同一进程地址空间中它们是不能重叠的，因为都有不同的权限和属性。

VMA 类型：代码段、数据段（已初始化的全局变量）、BSS 段（未初始化的全局变量）、进程的用户空间栈、共享库（的代码段、数据段、BSS 段）、内存映射文件、共享内存、匿名内存映射（malloc 分配的内存）、命令行参数、环境变量。

VMA 对象由 vm_area_struct 结构描述。它的 vm_start,vm_end 字段表示该区域的起始、结束地址。

VMA 标志：表示 VMA 的权限和属性，比如是否可读/写/执行、增长方向（即堆或栈）、是否共享内存、是否映射文件、是否映射 I/O 设备空间、能否在 fork() 时被拷贝、是否线性映射等等。

VMA 操作：VMA 结构中还包括一组操作 (vm_operations_struct)。比如将指定 VMA 加入地址空间 (open)、从地址空间删除指定 VMA (close)、访问的页不存在时的处理程序 (nopage)、为将要发生的缺页中断预映射 (populate) 等等。

匿名映射：即某个 VMA 没有映射任何文件，否则就是文件映射。

cat /proc/<pid>/maps      # 查看进程 VMA (设备标志为00:00表示没有映射文件，索引节点为0表示数据全0)
pmap <pid>                # 同上 (可读性更好)

如果想新建的 VMA 和已有的相邻且权限相同，则创建时会合并它们。

// 内核空间创建&删除 VMA
do_mmap();
do_munmap();

// 用户空间创建&删除 VMA
mmap();
munmap();

内存描述符

描述进程地址空间的结构体 (mm_struct)。

内存描述符中的一些重要字段：mm_users 表示共享该地址空间的进程数量。mm_count 表示该结构体是否被引用。mmap 和 mm_rb 包含进程地址空间中的全部 VMA，前者为链表，有利于快速遍历全部元素，而后者为红黑树，更适合快速查找指定元素。所有内存描述符都通过自身的 mmlist 字段形成双向链表，链表首元素是 init_mm，表示 init 进程的地址空间。

内核线程没有进程地址空间，也没有相关的内存描述符，它的进程描述符的 mm 字段为空，也没有用户上下文。

allocate_mm();    // 分配内存描述符
free_mm();        // 销毁内存描述符

父子进程共享内存空间

调用 clone() 时使用 CLONE_VM 标志。这样创建的子进程其实就是线程，它的进程描述符的 mm 字段指向父进程的内存描述符。

TLB

Translation Lookaside Buffer

它是虚拟地址转物理地址的硬件缓存，当需要访问虚拟地址时先查 TLB，如果有对应的物理地址就立即返回，否则就搜索页表获取物理地址。

页高速缓存

将磁盘中的数据缓存到内存，把对磁盘的访问变成对内存的访问。

缓存的单位是页，使用 address_space 结构体表示。

脏页回写：当空闲内存低于阈值，或者脏页驻留时间超过阈值，就会回写到磁盘。脏页由一群内核线程 (pdflush) 在后台回写，它们被周期性的唤醒。

膝上型电脑模式：是一种特殊的回写策略，它会找准磁盘运转的时机回写磁盘，而不会专门为回写激活磁盘。默认关闭，当笔记本使用电池时就会开启。通过 /proc/sys/vm/laptop_mode 设置。

sysfs

一个用户空间的文件系统，用来表示内核中 kobject 对象的层次结构。它可替代以前需要由 ioctl 和 procfs 才能完成的功能。

kobject：在统一设备模型中，每个设备结构中都内嵌了一个 kobject 结构，该结构包括引用计数、名称、父指针等。用它可将设备结构组织成树的形式。当关闭各个设备的电源时，可以从叶子向根的方向遍历。它在 sysfs 中映射成一个目录。

ktype：相同属性的 kobject 的集合，用于描述一组 kobject 的属性。

kset：仅仅是一组 kobject 的集合。

subsystem：是一组 ksets 的集合。在 sysfs 中映射为顶层目录。

sysfs 中的文件映射的是 ktype 中的属性 (attribute)。ktype 提供一组默认属性，因此其中的 kobject 就都具有这些属性。当读/写属性时，是通过调用 ktype 操作表 (sysfs_ops) 中的 show(),store() 函数实现的。

kobject_get();
kobject_put();
kobject_init();    // 初始化后引用计数为1，为0时被销毁。

kobject_add();     // 向 sysfs 中添加 kobject
kobject_del();

kobject_register();      // 等于 init+add
kobject_unregister();    // 等于 del+put

sysfs_create_file();
sysfs_remove_file();
sysfs_create_link();
sysfs_remove_link();

模块

模板如下：

#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>

// 初始化函数在模块加载时被调用，成功装载就返回0，否则返回非0
static int xxx_init(void)
{
	printk(KERN_ALERT "hello\n");
	return 0;
}

// 退出函数在模块卸载时被调用
static void xxx_exit(void)
{
	printk(KERN_ALERT "Goodbye");    
}

module_init(xxx_init);
module_exit(xxx_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Eric Zhong");

模块参数：可以为驱动程序声明参数，并在启动或载入时使用指定的参数值，对驱动程序属于全局变量，并会出现在 sysfs 中。

导出符号表：只有导出的内核函数才可以被模块调用。使用 EXPORT_SYMBOL(func_name) 或 EXPORT_SYMBOL_GPL(func_name) 来导出函数，后者导出的函数只对标记了 GPL 的模块可见。

make -C /kernel/source/location SUBDIR=$PWD modules     # 编译模块
make modules_install       # 安装模块到 /lib/modules/<version>/kernel/ 目录下

depmod      # 更新所有的依赖关系  (依赖信息文件：/lib/modules/<version>/modules.dep)
depmod -A   # 只为新模块生成依赖

insmod <module>       # 载入模块
rmmod <module>        # 卸载模块
modprobe <module>     # 自动加载模块和依赖
modprobe -r <module>  # 卸载模块及依赖模块 (如果没被使用)