Linux内核设计与实现 读书笔记
第二章 Linux内核
1 内核开发特点
1）内核编译时不能访问C库；
2）浮点数很难使用；
3）内核只有一个定长堆栈；
4）注意同步和并发。
第三章 进程管理
1 current宏：查找当前运行进程的进程描述符。
2 进程状态（5种）
TASK_RUNNING ：1）正在运行；2）在运行队列中等待执行。
TASK_INTERRUPTIBLE：进程正在睡眠，可以被信号唤醒。
TASK_UNINTERRUPTIBLE：进程正在睡眠，不会收到信号被唤醒。
TASK_ZOMBIE：僵死态，进程已经结束，父进程未使用wait4()。
TASK_STOPPED
3 进程上下文
进程进入内核空间时，current宏依然有效，内核“代表进程执行”。
4 进程创建
1）fork()：拷贝当前进程创建一个子进程。
2）exec()：读取可执行文件并载入地址空间开始运行。
3）写时拷贝（copy-on-wrtie）：推迟数据拷贝，在需要写入数据时，数据才会被复制。
4）vfork()：不拷贝父进程的页表项，子进程作为父进程的一个线程在它的地址空间运行，父进程被阻塞直至子进程退出，子进程不能向地址块空间写入数据。
5 线程
Linux把所有的线程都当作进程来实现。
6 内核线程：独立运行在内核中的标准进程。内核线程没有独立的地址空间，只能在内核空间中运行，创建内核线程用kernel_thread()。
7 进程终结
1）释放资源；
2）进入TASK_ZOMBIE；
3）等待wait4()。
第四章 进程调度
1 多任务系统
非抢占式多任务：主动让步
抢占式多任务（preemptive）：时间片
2 进程
IO消耗型：常常阻塞
处理器消耗型：执行代码
3 动态优先级调度方法
允许调度程序根据需要加减优先级。
两组优先级范围：
1）nice值：-20至+19，默认值为0，nice值越大，优先级越低。
2）实时优先级：0至99，任何实时进程优先级都高于普通进程。
4 时间片
默认时间片为20ms。
进程时间片用完——进程到期——所有进程都到期——重新计算时间片
5 可执行列队（runqueue）：每个处理器一个的可执行进程链表，还包含每个处理器的调度信息。
cpu_rq(processor)：返回给定处理器的可执行队列指针。
this_rq()：返回当前处理器的可执行队列。
task_rq(task)：返回给定任务所在的队列指针。
this_rq_lock()：锁住当前可执行列队。
rq_unlock()：释放给定列队上的锁。
★为了避免死锁，要锁住多个运行列队的代码，需要按同样的顺序获得这些锁。
6 优先级数组
每个运行列队有两个优先级数组：一个活跃的，一个过期的。
优先级数组包含一个优先级位图，共有140个优先级用了5个32位长整形保存。
活动数组：可执行队列上的进程还有时间片剩余。
过期数组：可执行队列上的进程耗尽了时间片。
★进程从活动数组移动至过期数组时重新计算时间片。
■重新计算时间片，以静态优先级为基础计算。
■为了判断Linux进程类型，Linux记录了进程用于休眠和执行的时间。
■若进程交互性非常强，时间片用完后，会被再次放入活动数组。
7 休眠
休眠通过等待列队进程处理。
等待列队：wait_queue_head_t
静态创建等待列队：DECLARE_WAITQUEUE
动态创建等待列队：init_waitqueue_head()
加入等待列队：add_wait_queue()
移出等待列队：remove_wait_queue()
8 负载平衡
保证可执行列队之间的负载处于均衡状态（用于SMP）。
两种调用方法：1）当前可执行列队为空；2）系统定时器200ms一次。
9 上下文切换
1）将虚拟内存从上一个进程映射到新的进程中；
2）将上个进程处理器的状态切换到新的进程，保存、恢复栈信息和寄存器信息。
10 schedule()被调用的时间
1）某个进程耗尽时间片时；
2）优先级高的进程进入可执行态时；
3）返回用户空间时；
4）中断返回时。
11 内核抢占
只要没有持有锁，内核就可以进行抢占。preempt_count计数器记录内核锁的数量。
内核抢占时机：
1）从中断返回内核空间时；
2）当内核代码再一次具有可抢占性的时候；
3）内核任务显示调用shedule()；
4）内核任务阻塞。
12 实时性
内核实时调度策略：
1）SCHED_FIFO：简单，先进先出调度；
2）SCHED_RR：时间片轮转调度，耗尽时间片后不再执行。
■SCHED_NORMAL 是普通、非实时的调度策略。
■内核实时调度策略是基于静态优先级的：内核不为实时进程计算动态优先级，实时优先级范围：0-99。
■动态非实时优先级范围：100-139（对应nice值-20至+19）。
第五章 系统调用
1 应用程序通过软中断机制通知内核。
2 参数验证
指针：
1）指针指向的内存区域属于用户空间；
2）指针指向的内存区域属于本进程地址空间；
3）如果读，内存标记为可读；如果写，内存标记为可写。
3 copy_to_user()的三个参数：
1）进程空间的目的地址内存；
2）内核空间源地址；
3）需要拷贝的数据长度（字节数）。
copybit_from_user()和上面相反。
第六章 中断和中断处理程序
1 上半部和下半部
上半部：中断处理程序
下半部：稍后完成的工作
2 注册中断
int request_irq(irq, *handle, irqflag, *devname, *devid)
irq 中断号。
handle 一个指针，指向中断处理程序。
irqflag 标志位：SA_INTERRUPT 快速中断处理程序（禁止其他中断）；SA_SHIRQ：可在多个中断处理程序间共享中断线。
devname 与中断相关的设备的ASCII文本表示法。
dev_id 用于共享中断线，当中断需要退出时，dev_id提供唯一的标志信息。从共享中断线的中断处理程序中删除指定程序。
3 释放中断
free_irq(unsigned int irq, void *dev_id)
4 中断处理程序
irqreturn_t intr_handle(int irq, void *dev_id, struct pt_regs *regs)
regs：一个指向结构体的指针，包含中断处理之前的处理器寄存器和状态，regs使用越来越少，应该忽略。
返回值irqreturn_t：
1）IRQ_NONE：中断对应设备并不是注册函数期间指定的产生源；
2）IRQ_HANDLE：正常返回值。
重入问题：Linux的中断处理程序无需考虑重入，当一个给定的中断处理程序正在执行，相应的中断会被屏蔽。
5 中断上下文
★中断上下文不可以睡眠，不能从中断上下文中调用睡眠函数。
中断栈：现在中断处理程序拥有自己的栈，每个处理器一个，大小为4KB。
6 中断控制
local_irq_disable()：禁止当前处理器上的本地中断；
local_irq_enable()：允许中断；
local_irq_save(flag)：禁止中断并保存系统状态；
local_irq_restore(flag)：恢复中断并恢复到原来的状态；
disable_irq(unsigned int irq)：禁止指定中断线；
disable_irq_nosync()：不等待当前中断处理完毕就禁止指定中断；
enable_irq(unsigned int irq)：允许指定中断；
synchronize_irq()：等待一个特定的中断处理程序的退出。
★如果调用了两次disable_irq()，需要对应调用两次enable_irq()才可以恢复。
第七章 下半部和推后执行的工作
1 下半部
1）缩短中断执行时间；
2）下半部执行时允许响应所有的中断。
2 下半部的类型
1）BH：早期实现，现在已经淘汰；
2）任务列队（task queue）；
3）软中断（softirq）：静态定义的下半部接口，共32个，可在所有处理上同时执行。
4）tasklet：基于软终端的动态下半部实现，不同类型的tasklet可在不同处理器同时执行，相同类型的tasklet不可以同时执行。
5）工作列队（work queue）：取代任务列队，对推后执行的工作排队。
6）内核定时器：将操作推后到某个确定的时间段。
3 软中断
1）软中断最多有32个。
2）一个软中断不会抢占另外一个软中断，唯一可以抢占软中断的是中断处理程序。
3）软中断的执行时机：（1）从一个硬件中断代码返回时；（2）在ksoftirq内核线程中；（3）显示检查和执行处理的软中断代码中，如网络子系统。
4）软中断保留给系统中对时间要求最严格和最重要的下半部使用：如网络和SCSI。
4 tasklet
1）tasklet通过软中断实现，本身也是软中断，有两种：HI_SOFTIRQ（优先级较高）和TASKLET_SOFTIRQ。
2）的状态有：0、TASKLET_STATE_SCHED（已经被调度，正等待运行）和TASKLET_STATE_RUN（正在运行，应用于多核系统）。
3）tasklet的调度过程：
（1）检查tasklet的状态是否为SCHED——>返回；
（2）保存中断，禁止本地中断；
（3）将调度tasklet加入tasklet_vec或者tasklet_hi_vec表头；
（4）唤起TASKLET_SOFTIRQ或HI_SOFTIRQ中断——>do_softirq()；
（5）恢复中断并恢复原状态。
4）使用tasklet
（1）声明
静态创建
DECLARE_TASKLET
DECLARE_TASKLET_DISABLED
动态创建
tasklet_init(t,tasklet_handle,dev)
（2）handle
void tasklet_handle(unsigned long data)
★由于tasklet靠软中断实现，所以tasklet执行中不能睡眠——>不能使用信号量或阻塞函数。
tasklet运行时运行中断，需要做好保护工作。
（3）调度
tasklet_schedule(&my_tasklet) 加入调度列队
tasklet_disable() 禁止莫个tasklet，若正在执行则等待执行完毕再禁止
tasklet_disable_nosync() 立即禁止（不太安全）
tasklet_enable() 激活一个tasklet
tasklet_kill() 去掉列队的第一个tasklet
（4）ksoftirq 辅助软中断内核线程
内核不会立即处理重新触发的软中断，当大量软中断出现时，内核会唤起一组线程来处理这些负载。（nice=19）
5 工作队列（work queue）
1）工作队列可把工作推后，交由一个内核线程去执行。
2）工作队列在进程上下文执行，允许重新调度甚至是睡眠，但无法访问用户空间。
3）实现
工作者线程 events/n，n是处理器编号。
worker_thread()函数：执行一个死循环并休眠，当有操作，线程被唤醒。
4）使用工作队列
（1）声明
静态创建
DECLARE_WORK(name, void(*func)(void*), void *data)
动态创建
INIT_WORK(struct work_struct *work, void (*func)(void*), void *data)
（2）处理函数
void work_handle(void *data)
（3）调度
shedule_work(&work) 马上调度
shedule_delayed_work(&work,delay) 延时调度
（4）刷新
flush_scheduled_work(void)
等待队列中所有对象都被执行后才返回。
cancel_delayed_work(struct work_struct *work)
取消延时的工作。
（5）创建新的工作列队
可在默认的工作列队外创建新的进程：
creat_work(const char *name)
queue_work() 类似schedule_work()，针对自己的进程。
queue_delayed_work()
flush_workqueue()
6 下半部机制的选择
下半部 上下文 顺序执行要求
软中断 中断 没有
tasklet 中断 同类型不可以同时执行
工作队列 进程 没有（和进程上下文一样被调度）
1）易用性：工作列队>tasklet>软中断
2）速度：软中断>tasklet>工作队列
3）开销：工作队列>>tasklet、软中断
7 下半部的锁机制
1）tasklet
（1）相同类型的tasklet不允许同时执行，无需同步。
（2）不同类型的tasklet需使用锁机制。
2）软中断所有共享数据结构都需要合适的锁。
3）进程上下文和下半部共享中断，上下文访问共享数据前，需禁止下半部并获取锁的使用权。
4）中断上下文和下半部共享中断，需禁止中断并取得锁使用权。
local_bh_disable() 禁止本地处理器的软中断和tasklet处理,不用禁止工作列队。
local_bh_enable()
第八章 内核同步介绍
1 临界区和竞争条件
临界区：访问和操作共享数据的代码段。
竞争条件：两个执行线程处于同一个临界区中。
2 内核中造成并发的原因
1）中断：任何时刻异步发生，打断当前执行的代码。
2）软中断和tasklet：任何时刻唤醒或调度软中断、tasklet。
3）内核抢占（preempt）。
4）睡眠及与用户空间的同步：唤醒调度程序，调度新进程执行。
5）对称多处理器（SMP）。
3 需要加速的代码
1）中断安全代码；
2）SMP安全代码；
3）抢占安全代码。
★给数据加锁而不是给代码加锁。
4 编程需注意的问题：
1）数据是否全局？除了当前线程，其他线程是否可以访问？
2）数据是否在进程/中断上下文中共享？是否在两个不同中断中共享？
3）进程在访问数据时可否被抢占？被调度的新进程是否会访问同一数据？
4）当前进程是否会睡眠（阻塞）在某些资源上？共享数据处于何种状态？
5）怎样防止数据失控？若在另一处理器上调度？
5 预防死锁
1）★加锁顺序是关键，使用嵌套锁必须以相同顺序获取锁；
2）防止发生饥饿；
3）不要重复请求同一个锁；
4）复杂的加锁方案也可能造成死锁——简化设计；
5）建议以获取锁相反的顺序来释放锁。
第九章 内核同步方法
1 原子操作
原子操作执行过程不被打断，原子操作接口分为整数操作接口和单独位操作接口。
2 原子整数操作
只有atomic_t类型可用于整数原子操作。
atomic_t类型保证编译器不对相应的值进行优化。
atomic_t类型可以屏蔽不同体系结构上实现原子类型的差异。
atomic_t类型只能使用24位（现在已经没有这个限制）。
定义：
asm/atomic.h
atomic_t v;
atomic_t u = ATOMIC_INIT(0);
操作：
atomic_set(&v, 4)
atomic_add(z, &v)
atomic_sub(int i, atomic *v)
atomic_inc(&v)
atomic_dec(&v)
atomic_read(&v) 转成整形
atomic_dec_and_test(&v) 给定原子变量减1，若为0则返回真。
3 原子位操作
原子位操作对普通的内存地址操作，没有atomic_t类型。
定义：
asm/bitops.h
操作：
set_bit(int nr, void *addr)
clear_bit(int nr, void *addr)
change_bit(int nr, void *addr) 翻转
test_and_set_bit() 设置并返回原先的值
test_and_clear_bit()
test_and_change()
test_bit() 返回第nr位
非原子操作：
__test_bit()
4 自旋锁
自旋锁最多只能被一个可执行线程持有。若一个线程试图获得一个被征用的自旋锁，线程会一直忙循环——选择——等待锁可用。
缺点：由于自旋锁在等待时自旋（浪费处理器时间），因此自旋锁不应长时间持有。
优点：线程不用睡眠，不用进行上下文切换。
数据结构：
结构相关代码： asm/spinlock.h
接口定义： linux/spinlock.h
声明： spinlock_t mr_lock = SPIN_LOCK_UNLOCKED
加锁： spin_lock(&mr_lock)
解锁： spin_unlock(&mr_lock)
自旋锁特点：
自旋锁最多被一个线程持有，为SMP提供了并发保护机制。
单处理器编程时并不会加入自旋锁，仅当做检测内核抢占的开关。
如果禁止内核抢占，则自旋锁无效。
自旋锁可用于中断处理程序中（信号量不可用于自旋锁，会自旋），中断中使用自旋锁首先应当关中断。
自旋锁不可递归。
自旋锁操作：
spin_lock_irqsave(&mr_lock, flag) 保存中断当前状态，关中断，获取锁
spin_unlock_irqstore(&mr_lock, flag) 恢复中断到加锁前状态并释放锁
spin_lock_irq(&mr_lock) 关中断，获取锁
spin_unlock_irq(&mr_lock) 关中断，释放锁
因为很难搞清楚中断情况，推荐使用前者。
其他操作：
spin_lock_init() 动态初始化知道spinlock_t
spin_trylock() 试图获取指定锁，若未获取则返回非0
spin_is_locked() 如制定锁当前正在被获取，则返回非0
4 读写自旋锁
读写不同锁，多人和可并发持有读者锁，写锁只能被一个任务持有。
用法：
rwlock_t mr_rwlock = RW_LOCK_UNLOCKED;
read_lock(&mr_rwlock)
read_unlock(&mr_rwlock)
write_lock(&mr_rwlock)
write_unlock(&mr_rwlock)
注意：
（1）不可将读锁“升级”为写锁，写锁会等待读锁。
（2）多个读者可以安全获得同一个读锁，也可递归获取读锁。
5 信号量
1）信号量的特点
（1）Linux中的信号量是一种睡眠锁；
（2）信号量适用于锁会被长期占有的情况；
（3）由于信号量会睡眠，所以只能用于进程上下文中，中断上下文不支持调度；
（4）可以在持有信号量时睡眠；
（5）不可以在持有信号量时使用自旋锁；
（6）信号量允许任意数目的锁持有者，自旋锁一个时刻只允许一个任务持有；
（7）在声明时课指定信号量拥有的持有者数量。
2）创建信号量
定义： asm/semaphore.h
静态声明： static DECLARE_SEMAPHORE_GENEIC(none， count)
互斥信号量声明：static DECLARE_MUTEX(name)
动态创建： sema_init(sem, count)
动态创建互斥对象：init_MUTEX(sem) （注意大小写）
3）使用信号量
down() 信号计数减1，若为0或大于0，则获取信号量，若为负数，则任务等待。
up() 信号计数加1，若等待队列不为空，唤醒等待任务。
down_interruptible(struct semaphore*) 若信号量已被征用，则可进入中断睡眠状态。
down_trylock() 试图获取信号量，若已被征用，则立刻返回非零值。
6 读-写信号量（都是互斥信号量）
定义： linux/rwsem.h
静态声明： static DECLARE_RWSEM(name)
动态创建： init_rwsem(struct rw_semaphore *sem)
功能： down_read()
up_read()
down_write()
up_write()
downgrade_writer() 动态将写锁转换为读锁
7 自旋锁与信号量
中断上下文中只能使用自旋锁。
任务睡眠时只能使用信号量。
需求 建议
低开销加锁 优先使用自旋锁
短期锁定 优先使用自旋锁
长期加锁 优先使用信号量
中断上下文加锁 使用自旋锁
持有锁需要睡眠 使用信号量
8 完成变量
完成变量是同步两个任务的一种简单方法。
定义： linux/completion.h
静态创建： DECLARE_COMPLETION(mr_comp)
动态创建： init_completion()
方法： wait_for_completion(struct completion *) 等待指定的完成变量接受信号
complete(struct completion*) 发信号唤醒等待任务
9 禁止抢占
内核代码使用自旋锁作为非抢占区域的标记。
preempt_disable() 增加抢占计数值，从而禁止内核抢占
preempt_enable() 减少抢占计数值，当减为0时检查和执行被挂起的任务
preempt_enable_no_resched()
preempt_count() 返回抢占计数
get_cpu()
put_cpu()
10 顺序和屏障
屏障（barrier）：确保城乡运行顺序的指令。
rmb() 阻止跨越屏障的转入动作发生重排序。
read_barrier_depends() 阻止跨越屏障的具有数据依赖关系的载入动作重排序。
wmb() 阻止跨越屏障的载入和存储动作发生重排序。
mb() 阻止跨越屏障的载入和存储动作发生重排序。
smp_rmb() 在SMP上提供rmb()功能，在UP上提供barrier()功能。
smp_read_barrier_depends()
smp_wmb()
smp_mb()
barrirer() 阻止编译器跨越屏障对载入或存储操作进行优化。
第十章 定时器和时间管理
1 时钟中断的工作
1）跟新系统运行时间；
2）跟新实际时间；
3）在SMP系统中均衡调度各处理器的运行列队；
4）检查当前进程是否耗尽时间片，若耗尽则进行重新调度；
5）运行超时的动态定时器；
6）更新资源消耗和处理器时间的统计值。
2 节拍率 HZ
ARM 100（10ms）
i386 1000（1ms）
x86-64
提高HZ的优点：
1）更高时钟中断解析度；
2）提高时间驱动事件的准确性（平均误差5ms->0.5ms）；
3）内核定时器能够以更高的频度和更高准确度执行；
4）依赖定时器的系统调用（如poll和select）能以更高精度运行；
5）对资源消耗和系统运行时间的测量更准确；
6）提供进程抢占的准确度。
缺点：
1）系统负担增加；
2）中断占用处理器的时间增加。
3 jifies
jiffies全局变量用来记录系统自启动以来产生的节拍总数。
定义： linux/jiffies.h
extern unsigned long volatile jiffies;
extern u64 jiffies_64;
jiffies取jifies_64的低32位
jiffies溢出回绕：
#define time_after(unknown, known) ((long)(known)-(long)(unknown)<0)
#define time_before(unknown, known) ((long)(unknown)-(long)(known)<0)
4 时间中断处理程序
流程：
1）获得锁 xtime_lock；
2）需要时应答或重设系统时钟；
3）周期性使用墙上时间（实际时间）更新实时时钟；
4）调用架构无关的do_timer()函数；
（1）增加jiffies；
（2）更新资源消耗的统计值；
（3）执行到期的动态定时器；
（4）执行schedule_tick()；
（5）更新墙上时间->存有xtime中；
（6）计算平均负载。
5 实际时间（墙上时间）
定义; kernel/timer.c
struct timespec xtime;
struct timespec {
time_t tv_sec; //秒，自1970.7.1开始的秒数
long tv_nsec; //纳秒，自上一秒开始的纳秒数
}
读写xtime需要用xtime_lock锁，是一个seqlock锁。
用户空间获取墙上时间的接口：gettimeofday()
内核空间获取墙上时间的接口：sys_gettimeofday() <-系统调用
设置当前时间接口：settimeofday()
6 定时器（动态定时器）
定义： linux/timer.h
struct time_list my_timer
初始化：
init_timer(&my_timer);
my_timer.expires = jiffies + delay;
my_timer.data = 0;
my_timer.function = my_function;
处理函数格式：
void my_function(unsigned long data)
激活：
add_timer(&my_timer)
修改定时时间：
mod_timer(&my_timer, jiffies+delay)
停止定时器：
del_timer(&my_timer)
del_timer_sync() <-用于SMP，不可用户中断上下文
7 延迟执行
1）忙等待
unsigned long delay = jiffies + delays;
while(time_before(jiffies, delay));
2）代码等待时允许内核重新调度其他任务
unsigned long delay = jiffies + delays;
while(time_before(jiffies, delay))
cond_resched();
★延迟执行在任何情况下都不应该在持有锁或禁止中断时发生。
★jiffies采用volatile型，每次循环都会从内存中读取。
3）短延迟
linux/delay.h
void udelay(unsigned long usecs);
void mdelay(unsigned long msecs);
★短延时是通过循环实现的。
★BogoMips不是为了表现机器性能，而是同udelay和mdelay使用。
4）schedule_timeout()
将需要延迟的任务睡眠至延迟时间耗尽（不能保证时间准确，因为会重新调度）。
使用：
set_current_state(TASK_INTERRUPTIBLE);
schedule_timeout(X*HZ);
使用场合为进程上下文且不能持有锁。
第十一章 内存管理
1 页
物理也是内存管理的基本单位。
定义：
linux/mm.h
struct page {
page_flag_t flags; //页的状态（脏、锁定）
atomic_t _count; //页的引用记录（0：内核没有引用，可用于新分配）
atomic_t _mapcount;
unsigned long private; //页作为私有数据时使用
struct address_space *mapping; //页作为页缓存时使用
pgoff_t index;
struct list_head lru;
void *virtual; //虚拟地址
}
2 区（zone）
ZONE_DMA：包含的页用来执行DMA操作。
ZONE_NORMAL：正常映射的页。
ZONE_HIGHMEM：“高端内存”（并不能永久映射到内核地址空间）。
3 获得页（获取页的接口）
1）sttuct page* alloc_pages(unsigned int gfp_mask, unsigned int order)
分配2^x个连续物理页，并返回指向第一个页结构体的指针。
2）void* page_address(struct page * page)
返回给定物理页的逻辑地址。
3）unsigned long __get_free_pages(unsigned int gft_mask, unsigned int order)
与alloc_page()相同，但直接返回第一页的物理地址。
4）struct page* alloc_page(gfp_mask)
unsigned long __get_free_page()
以上两个函数只分配一页。
5）unsigned long get_zeroed_page(gfp_mask)
只分配一页，且内容填充0，返回逻辑地址指针。
释放页：
void __free_pages(struct page *page, unsigned int order);
void free_pages(unsigned long addr, unsigned int order);
void free_page(unsigned long addr);
★获取页后注意进行错误检查。
4 kmalloc()
定义： linux/slab.h
void* kmalloc(size_t, int flags)
★分配的内存在物理上是连续的。
★最大能分配128KB。
★必须检查分配是否成功。
kfree()和kmalloc()对应
void kfree(const void *ptr);
5 gfp_mask标志
该标志可以分为三类：
（1）行为修饰符：描述内核如何分配所需内存。
（2）区修饰符：从哪个区分配内存。
（3）类型：组合了行为和区修饰符，提供了常用的标志。
类型标志：
（1）GFP_ATOMIC 分配高级、优先，用于中断、下半部、锁中及其他不能睡眠的情况（分配成功率较低）。
（2）GFP_NOIO 分配可阻塞，不会启动磁盘IO。
（3）GFP_NOFS 分配可阻塞，可能启动磁盘IO，不会启动文件系统。
（4）GFP_KERNEL 最常使用，可阻塞。睡眠安全时用于进程上下文（没有锁的情况）。
（5）GFP_USER 常规分配方式，可阻塞，用于为用户空间分配内存。
（6）GFP_HIGHUSER 从ZONE_HIGHMEM分配可阻塞，用于为用户空间分配内存。
（7）GFP_DMA 从ZONE_DMA分配内存
6 vmallc()
分配内存，虚拟地址连续，物理地址不一定连续（类似malloc）。
vmalloc()为了把物理上不连续的页转换为虚拟地址连续的页，需要专门建立页表项。
通过vmalloc()获得的页必须一个一个进行映射，导致TLB抖动增大，因此仅在不得已情况下调用，且可能睡眠，不能用于中断上下文。
7 slab分配器
slab分配器把不同对象划分为不同的高速缓存组，如进程描述符组、索引节点组、kmalloc组等等。
高速缓存又被划分为不同的slba，slab由一个或多个物理连续的页组成（一般一页）。
slab的状态分为：满、部分满和空。
高速缓存的数据结构 kmem_cache_t保存着三个链表：slabs_full、slabs_partial和slabs_empty。
8 slab分配器接口
1）创建
kmem_cache_t * kmem_cache_creat(const char* name, size_t size, size_t align, unsigned long flags,
void (*ctor)(void*, kmem_cache_t *, unsigned long), （构造）
void (*dtor)(void*, kmem_cache_t *, unsigned long)) （析构）
2）销毁
int kmem_cache_destroy(kmem_cache_t *cachep)
3）从高速缓冲中获取对象
void* kmem_cache_alloc(kmem_chache_t *cachep, int flags)
4）释放一个对象
void kmem_cache_free(kmem_cache_t *cachep, void *objp)
9 高端内存
X86中，高于896MB的内存是高端内存，不能永久映射到内核空间。
永久映射：映射一个给定的page结构体到内核地址空间
void* kmap(struct page *page) 低端内存：返回虚拟地址；高端内存：建立永久映射再返回。
void kunmap(struct page *page)
临时映射（原子映射）：当上下文不能睡眠时，可使用临时映射（可用于中断）
void* kmap_atomic(struct page *page， enum km_type type)
void kunmap_atomic(void *kvaddr, enum km_type type)
第十二章 虚拟文件系统
1 Unix文件系统
四要素：文件、目录、索引节点（inode）、安装点（mount point）
索引结点：存储访问权限、大小、拥有者、创建时间等信息。
超级块：存储文件系统的控制信息。
2 VFS对象
1）超级块对象：代表一个已安装的文件系统。
2）索引节点对象：代表一个文件。
3）目录项对象：代表一个目录项，是路径的一个组成部分。
4）文件对象：代表由进程打开的文件。
VFS将目录作为文件来处理，目录项不同于目录。
3 超级块对象
各种文件系统必须实现超级块，用于存储指定文件系统信息。
超级块通常存放于磁盘的特定扇区中。
对于sysfs等非磁盘文件系统，超级块存在内存中。
4 索引节点对象
索引节点对象包含内核在操作文件或目录时需要的全部信息。
没有索引节点的文件系统，内核需要建立这些信息。
一个索引节点代表文件系统中的一个文件（包括设备、管道等特殊文件）。
5 目录项对象（dentry）
路径中的每个组成部分都由一个索引节点对象表示。
目录项：每个目录项代表一个目录中的一个组成部分。
eg： /bin/vi “/”“bin”“vi”是三个目录项
目录项不保存在磁盘上，VFS根据路径现场创建。
目录项的状态：
（1）被使用：对应一个有效的inode，且对象存在使用者；
（2）未使用：对应一个有效的inode，VFS当前未使用；
（3）负，没有对应的有效索引节点。
目录项缓存：
（1）“被使用的”目录项链表；
（2）“最近被使用”的双向链表；
（3）散列表及散列函数。
6 文件对象
表示进程已打开的文件，是打开文件在内存中的表示。
文件对象在内存中，也没有对应的磁盘数据。
第十三章 块IO层
1 各种设备
块设备：随机访问固定大小数据片的设备。
字符设备：按字符流方式有序被访问，和块设备的区别在于随机访问。
扇区：物理设备的最小可寻址单元（物理属性）。
块：文件系统的最小逻辑可寻址单元。
2 IO调度程序
内核会针对IO操作进行合并、排序预操作。
Linux电梯调度算法（2.4内核中的旧算法）：
（1）相邻合并；
（2）驻留时间过长的请求放入队列尾部；
（3）保证扇区的磁盘访问顺序；
（4）不合适的请求插入位置被放入列队尾部。
新的调度算法：
（1）最后期限IO调度，每个请求都有一个超时时间，读默认500ms，写默认5s。
（2）预测IO调度，保持良好的读响应，同时提供良好的全局吞吐率。
（3）完全公正的排队IO调度程序（CFQ），IO进程列队采用时间片轮转。
（4）空操作IO调度程序，不进行排序，只进行合并，适用于闪存等无需“寻道”的介质。
第十四章 进程地址空间
1 内存区域可包含的内存对象
1）可执行文件代码的内存映射，代码段（text section）；
2）可执行文件已初始化全局变量的内存映射，数据段（data section）；
3）未初始化全局变量（bss段的零页）；
4）用于进程用户空间栈的零页的内存映射；
5）每一个诸如C库或动态连接程序等共享库的代码段、数据段和bss段；
6）任何内存映射文件；
7）任何匿名的内存映射，如malloc()分配的内存；
2 内存描述符
1）内核用mmap和mm_rb两个结构体描述内存对象。
mmap：链表，利于简单、高效地遍历所有元素。
mm_rb：红黑树，适合搜索指定元素。
2）内核用内存描述符（mm_strcut）表示进程的地址空间。
3）current->mm指向当前进程的内存描述符。
4）内核线程：内核线程没有进程地址空间，也没有相关的内存描述符。新内核线程直接使用前一个进程的内存描述符。
3 内存区域
vm_area_struct 结构体：描述指定地址空间内存连续区间上的一个独立内存范围。
VMA标志：标志内存区域所包含的页面的行为和信息。
eg. C库在物理内存中仅占用一份空间（空间不可写），不需为每个进程保存一个C库。
4 内存区域接口
find_vma()：指定地址空间搜索第一个vm_end大于addr的内存区域。
find_vma_prev()：返回第一个小于addr的VMA。
find_vma_intersection()：返回第一个和指定地址区间相交的VMA。
mmap()\do_mmap()：将一个新的地址区间加入到进程地址空间中。
unsigned long do_mmap(struct file *file, unsgined long addr, unsigned long len,
unsigned long prot, unsigned long flag, unsigned long offset)
file：指定文件，NULL为匿名映射，否则为文件映射。
offset：文件的偏移。
len：长度。
addr：可选参数，指定空闲区域的起始地址。
prot：指定内存区域中页面的访问权限
（1）PROT_READ 对应VM_READ
（2）PROT_WRITE 对应VM_WRITE
（3）PROT_EXEX 对应VM_EXEC
（4）PROT_NONE 页不可访问
flag：指定VMA标志
（1）MAP_SHARED 映射可以被共享
（2）MAP_PRIVATE 映射不可以被共享
（3）MAP_FIXED 新区间必须开始于指定地址addr
（4）MAP_ANONYMOUS 映射是匿名的
（5）MAP_GROWSDOWN VM_GROWSDOWN
（6）MAP_DENYWRITE VM_DENYWRITE
（7）MAP_EXECUTABLE VM_EXECUTABLE
（8）MAP_LOCKED VM_LOCKED
（9）MAP_NORESERVE 不需为映射保留空间
（10）MAP_POPULATE 填充页表
（11）MAP_NONBLOCK 在IO操作上不阻塞
调用流程：
mmap()->mmap2()->do_mmap()（内核系统调用）
5 页表项
虚拟地址——>物理地址：查询页表
三级页表机制：
PGD：一级页表，全局目录
PMD：二级页表
PTE：最后一级页表
mm->PGD->PMD->PTE->物理地址
TLB：缓冲虚拟地址到物理地址的信息。
第十五章 页高速缓存和页回写
1 页高速缓存
1）Linux内核的一种主要磁盘缓存，减少对磁盘的IO操作（将磁盘数据缓存至主存中）；
2）页高速缓存缓存的是页面，所有的页IO操作都通过也高速缓存。
2 页回写
脏数据：页高速缓存比后台存储数据新的数据。
脏数据被写回：
（1）空闲内存低于一个阈值，脏数据写回以释放内存。
（2）脏页在内存中驻留超过一个特定的阈值。
pdflush内核线程：负责定时将脏数据刷入磁盘。pdflush线程可以有多个处理不同的设备列队。
第十六章 模块
1 构建模块
将模块放在内核外：
makefile
obj-m := fishing.o
fishing-objs := fishing-main.o fishing-line.o
make -C /kernel/source/location SUBDIRS = $PWD modules
2 模块参数
module_param(name, type, perm)
name：用户可见的参数名
type：参数类型
perm：sysfs文件系统下的文件权限
3 导出符号表
导出的内核函数可被模块调用。
EXPORT_SYMBOL()
EXPORT_SYMBOL_GPL()
第十七章 kobject与sysfs
1 统一设备模型
kobject：包含引用计数，父子关系和对象名称等基本对象道具，以统一方式提供这些功能。
ktype：定义了一些kobject相关默认特性，如析构、sysfs行为等。
kset：
（1）嵌入的kobject作为kobject组的基类；
（2）kset将相关的kobject集合在一起，相关的kobject以独立目录与sysfs中。
subsystem：包含kset的集合，是sysfs的根目录映射。
2 kobject使用方法
初始化：kobject_init(struct kobject *kobj)
设置名称：kobject_set_name(struct kobject *kobj, const char* fmt,...)
增加引用计数：struct kobject* kobjec_get(struct kobject *kobj)
减少引用计数：void kobject_put(struct kobject *kobj)
3 sysfs
将kobject导入sysfs：
int kobject_add(struct kobject *kobj)
kobject_register()函数包含kobject_init()和kobject_add()两个函数的功能。
删除一个kobject对应文件目录：
void kobject_del(struct kobject *kobj)
kobject_unregister包含kobject_del()和kobject_put()功能
创建新属性：
int sysfs_create_file(struct kobject *kobj, const struct attribute *attr)
创建符号链接：
int sysfs_create_link(struct kobject *kobj, struct kobject *target, char* name)
删除新属性：
void sysfs_remove_file(struct kobject *kobj, const struct attribute *attr)
void sysfs_remove_link(struct kobject *kobj, char* name)
第十八章 调试
1 printk
★可在进程、中断上下文中调用printk
★可在持有锁时调用printk
★可在SMP上调用printk
记录等级：
0 KERN_EMERG 紧急情况
1 KERN_ALERT 需立即注意的错误
2 KERN_CRIT 临界情况
3 KERN_ERR 错误
4 KERN_WARNING 警告
5 KERN_NOTICE 普通，可能需要注意
6 KERN_INFO 非正式信息
7 KERN_DEBUG 调试信息
默认的等级是KERN_WARNING。
记录缓冲区（LOG_BUF_LEN）：
CONFIG_LOG_BUF_SHIFT 可调整缓冲区大小
守护进程：
klogd，从记录缓冲区中获取内核消息。
syslogd，将消息保存于内核日志中。
kallsysm：
CONFIG_KALLSYMS 可载入内核镜像对应的内存地址符号名称，使内核稍大，但便于调试。
2 引发BUG
可以打印oops信息的函数：
BUG()
BUG_ON(bad_thing)
打印oops并挂起整个系统：
panic()
回朔栈信息：
dump_stack()
3 GDB
（1）gdb vmlinux /proc/kcore
（2）p global_variable 打印一个变量
（3）dissable function 反汇编一个函数
4 时间重复限制
static unsigned long pre_jiffy = jiffies;
if(time_after(jiffies, prev_jiffy + 2*Hz)){
prev_jiffy = jiffies;
printk("XXXX");
}
5 次数重复限制
static unsigned long limit = 0;
if(linux < 5) {
limit++;
printk("xxx");
}
第十九章 可移植性
1 字长规则
1）ANSI C标准规定，一个char长度是8位；
2）Linux当前体系中，int都是32位的；
3）Linux当前系统中，short都是16位的；
4）long的长度可能是32位或64位；
5）不应该假设 sizeof(int) == sizeof(long)；
6）不应该假设指针和int长度相等。
2 不透明类型
pid_t、atomic_t ——> int
dev_t、gid_t、uid_t
1)不要假设该类型长度；
2)不要将该类型转化为C标准类型；
3)编程时要保证类型实际存储空间和格式发生变化后代码不受影响。
第二十章 其他
1 Linux的编程风格
1）缩进：用制表符（tab）每次缩进8个字符；
2）括号：左括号紧跟在语句的最后，与语句同一行。右括号新起一行；
3）每行代码长度：尽可能保证每行代码不超过80个字符；
4）命名规范：不允许混合大小写；
5）函数：代码应不超过两屏，局部变量不超过十个。
6）注释：bug以“FIXME”开头；
7）尽量少用typedef；
8）在源码中尽量不要用ifdef。
2 创建补丁
1）创建整个内核patch
diff -urN linux-origin/ linux-change/ > my_patch
2）创建指定文件的patch
diff -u linux-origin/some/file linux-change/some/file > my_patch_file
3）在自己代码目录下执行patch
patch -p1 < ../my_patch
附录A：链表
1 链表结构体
struct list_head{
struct list_head *next;
struct list_head *prev;
};
Linux的链表可以从任何一个节点开始遍历，因此每个独立节点都可看做是链表头。
单独的list_head无意义，需要嵌入自己的结构体中。
eg. struct my_struct{
struct list_head list;
unsigned long dong;
void *cat;
};
初始化：
eg. struct my_struct *p;
p->dog = 0;
p->cat = NULL:
INIT_LIST_HEAD(&p->list);
静态创建：
struct my_struct mine = {
.list = LIST_HEAD_INIT(mine.list); //INIT_LIST_HEAD？
.dog = 0;
.cat = NULL;
};
直接声明和初始化静态链表：
static LIST_HEAD(fox);
2 操作链表
1）增加节点（head后插入）
list_add(struct list_head *new, struct list_head *head)
2）把节点增加到链表尾（head节点前插入）
list_add_tail(struct list_head *new, struct list_head *head)
3）从链表删除一个节点
list_del(struct list_head *entry)
不会释放entry和占用内存。
4）删除一个节点并对其重新初始化
list_del_init(struct list_head *entry)
再次初始化entry。
5）把节点从一个链表移到另一个链表（head后）
list_move(struct list_head *list, struct list_head *head)
6）把节点从一个链表移到另一个链表末尾
list_move_tail(struct list_head *list, struct list_head *head)
7）检查链表是否为空
list_empty(struct list_head *head)
8）合并两链表（list插入head后）
list_splice(struct list_head *list, struct list_head *head)
9）合并，并重新初始化list指向的链表
list_splice_init(struct list_head *list, struct list_head *head)
10）遍历链表
list_for_each()
eg. struct list_head *p;
list_for_each(p, list){
//p指向某元素
}
11）取得包含list_head的结构体
list_entry()
参数：
（1）指向给定链表元素的指针；
（2）嵌入了链表结构体类型的引用；
（3）结构体中链表成员的名称。
eg. struct list_head *p;
struct my_struct *my;
list_for_each(p, &mine->list){
my = list_entry(p, struct my_struct, list);
}
