《深入理解LINUX内核》章节试读

《深入理解LINUX内核》的笔记-第85页 - Process descriptors handling

we learned that a process in Kernel Mode accesses a stack contained in the kernel data segment, which is different from the stack used by the process in User Mode1. kernel mode和user mode用的不是同一个stack。stack不同意味着从user mode切换到kernel mode时，需要刷新esp
2. 虽然在linux中，data segment跟code segment地址范围是一样的，但是还是要注意stack是属于data segment的
For each process, Linux packs two different data structures in a single per-process memory area: a small data structure linked to the process descriptor, namely the thread_info structure, and the Kernel Mode process stack.
task_struct的stack域就指向这一片内存区域：
http://lxr.free-electrons.com/source/include/linux/sched.h#L1294
thread_info的task域指向 task_struct
http://lxr.free-electrons.com/source/arch/x86/include/asm/thread_info.h#L53
所有 task_struct 跟 thread_info相互指向对方

《深入理解LINUX内核》的笔记-第5页

Linux 2.6内核笔记【中断、异常、抢占内核】
2009.6.18更新：参考http://linux.derkeiler.com/Mailing-Lists/Kernel/2004-03/4562.html ，查证LXR，重新诠释PREEMPT_ACTIVE标志。
【中断信号分类 】
中断信号是一个统称，统称那些改变CPU指令执行序列的事件。但它又分为两种：
一种是同步的，没那么突然，因为它只在一个指令的执行终止之后才发生，书中依从Intel的惯例，称为异常（Exception）。一般是编程错误（一般的处理是发信号）或者内核必须处理的异常情况（内核会采取恢复异常所需的一些步骤）；
一种是异步的，突然一些，因为它是由间隔定时器和I/O设备产生的，只遵循CPU时钟信号，所以可能在任何时候产生，书中也依从Intel的惯例，称为中断（Interrupt）。
【内核控制路径】
内核在允许中断信号到来之前，必须先准备好对它们的处理，也就是适当地初始化中断描述符表（Interrupt Descriptor Table, IDT）。
中断信号一来，CPU控制单元就自动把当前的程序计数器（eip、cs）和eflags保存到内核stack，然后把事先与发生的中断信号类型关联好的处理程序的地址（保存在IDT中）放进程序计数器。这时，内核控制路径（kernel control path）横空出世。
什么是内核控制路径？它是不是一个进程？不是。内核进程？也不是。它虽然也需要切换上下文，需要保存那些它可能使用的寄存器的并在返回时恢复，但这是一个非常轻的上下文切换。它诞生的时候并没有发生进程切换，处理中断的主语仍然是中断发生时正在执行的那个进程。那个进程就像突然被内核抓进了一间小屋做事，或者突然潜入了水（内核）里不见踪影，但它仍然在使用分配给它的那段时间片。
有趣的是，如果一个进程还在处理一个异常的时候，分配给它的时间片到期了，会发生什么事情呢？这取决于有没有启用内核抢占（Kernel Preemption），如果没有启用，进程就继续处理异常，如果启用了，进程可能会立即被抢占，异常的处理也就暂停了，直到schedule()再度选择原先那个进程（注意：内核处理中断的时候，必然会禁用内核抢占，所以这里才说是异常）。
【中断信号处理的约束】

中断信号处理需要满足下面三个严格的约束：
1)中断处理要尽可能块地完成、返回。因此只执行关键而紧急的部分，尽可能把更多的后续处理过程仅仅标志一下，放到之后再去执行。
2)一个中断还在处理的时候，另外一个中断可能又来了，这个时候最好能先放下手中的处理，先去处理新的中断，然后在回头来接着处理这个中断，这称之为中断和异常处理程序的嵌套执行（nested execution），或者说是内核控制路径的嵌套执行。要实现这一点，有一点必须满足，那就是中断处理程序运行期间不能阻塞，不能发生进程切换。
如果对异常的种类做一番思考，就会发现，异常最多嵌套两层，一个由系统调用产生，一个由系统调用执行过程中的缺页产生（这时必然挂起当前进程，发生进程切换）。与之相反，在复杂的情况下，中断产生的嵌套则可能任意多。
3)内核中存在一些临界区，在这些临界区，中断必须被禁止。中断处理程序要尽可能地减少进入临界区的次数和时间，为了内核的响应性能，中断应该在大部分时间都是启用的。
【异常的种类】

异常有很多种，其中比较有趣的有：
编号
异常
异常处理程序
信号
有趣之处

1
Debug
debug( )
SIGTRAP
用于调试

3
Breakpoint
int3( )
SIGTRAP

7
Device not available
device_not_available( )
None
用于在需要的时候才加载FPU 、MMX 、XMM
( 当cr0 的TS 标志被设置)

14
Page Fault
page_fault( )
SIGSEGV
如果是正常缺页，内核会挂起当前进程，然后将该页读入RAM ；如果是页错误，就发出信号。

4
Overflow
overflow( )
SIGSEGV
调试时非常常见的一个信号SIGSEQV ，Segment Violation ，呵呵，关注一下都是什么异常导致的。

5
Bounds check
bounds( )
SIGSEGV

10
Invalid TSS
invalid_TSS( )
SIGSEGV

13
General protection
general_protection( )
SIGSEGV

【中断描述符】

Intel 80x86 CPU认得三种中断描述符，Linux为了检验权限，将其细分为：
Interrupt Gate， DPL = 0的中断门，set_intr_gate(n,addr)，所有中断
System Interrupt Gate，DPL = 3的中断门，set_system_intr_gate(n,addr)，int3异常
System Gate，DPL = 3的陷阱门，set_system_gate(n,addr)，into、bound、int $0x80异常
Trap Gate， DPL = 0的陷阱门，set_trap_gate(n,addr)，大部分异常
Task Gate， DPL = 0的任务门，set_task_gate(n,gdt)，double fault异常
【异常处理的标准结构】
用汇编把大多数寄存器的值保存到kernel stack；
用C函数处理异常
通过ret_from_exception( ) 函数退出处理程序.
I/O中断处理的标准结构
将IRQ值和寄存器值保存到kernel stack；
给服务这条IRQ线的PIC发送应答，从而允许它继续发出中断；
执行和所有共享此IRQ的设备相关联的ISR；
通过跳转到ret_from_intr( ) 的地址结束中断处理。
【IRQ(Interrupt ReQuest)线（IRQ向量）的分配】

IRQ共享：几个设备共享一个IRQ，中断来时，每个设备的中断服务例程（Interrupt Service Routine，ISR）都执行，检查一下是否与己有关；
IRQ动态分配：IRQ可以在使用一个设备的时候才与一个设备关联，这样同一个IRQ就可以被不同的设备在不同时间使用。
中断向量中，0-19用于异常和非屏蔽中断，20-31被Intel保留了，32-238这个范围内都可以分配给物理IRQ，但128（0x80）被分配给用于系统调用的可编程异常。
延后的工作谁来做？
首先是两种非紧迫的、可中断的内核函数——可延迟函数（deferrable functions ），然后是通过工作队列（work queues ）来执行的函数。
软中断（softirq）是可重入函数而且必须明确地使用自旋锁保护其数据结构；tasklet在软中断基础上实现，但由于内核保证不会在两个CPU上同时运行相同类型的tasklet，所以它不必是可重入的。
【六种软中断】
Softirq
Index (priority)
Description

HI_SOFTIRQ
0
Handles high priority tasklets

TIMER_SOFTIRQ
1
Tasklets related to timer interrupts

NET_TX_SOFTIRQ
2
Transmits packets to network cards

NET_RX_SOFTIRQ
3
Receives packets from network cards

SCSI_SOFTIRQ
4
Post-interrupt processing of SCSI commands

TASKLET_SOFTIRQ
5
Handles regular tasklets

内核会在一些检查点（适宜的时候，其中有时钟中断）检查挂起的软中断，用__do_softirq()执行它们。__do_softirq()会循环若干次，以保证处理掉一些在处理过程中新出现的软中断，但如果还有更多新挂起的软中断，__do_softirq()就不管了，而是调用wakeup_softirq()唤醒每CPU内核进程ksoftirqd/n（这样就可以被调度，而不会一直占着CPU），来处理剩下的软中断。
这种做法是为了解决一个矛盾：与网络相关的软中断是高流量的，也是对实时性有一定要求的。但是如果do_softirq()为了实时性一直处理它们，就会一直不返回，结果用户程序就僵在那里了；如果do_softirq()处理完一些软中断就返回，不论这中间机器有无空闲，直到下一个时钟中断才又处理其余的，网络处理需要的许多实时性就得不到保证。现在的做法，唤醒内核进程，让它在后台调度，由于内核进程优先级很低，用户程序就有机会运行，不会僵死；但如果机器空闲下来，挂起的软中断很快就能被执行。
tasklet则多用于在I/O驱动程序的开发中实现可延迟函数。
但是，可延迟函数有一个限制，它是运行在中断上下文的，它执行时不可能有任何正在运行的进程，它也不能调用任何可阻塞（从而会休眠）的函数。这就是工作队列的意义所在。工作队列把需要执行的内核函数交给一些内核进程来执行。
处于效率的考虑，内核预定义了叫做events的工作队列，内核开发者可以用schedule_work族函数随意呼唤它们。
【内核抢占（Kernel Preemption）】

本章在很多地方都涉及到了内核抢占，我觉得还是将内核抢占在本章的笔记记完，不必像原书那样等到内核同步一章了。
在非抢占内核的情形，一个执行在内核态的进程是不可能被另外的进程取代的（进程切换）；而在抢占内核的情形，是有可能的：但只有当内核正在执行异常处理程序（尤其是系统调用），而且内核抢占没有被显式禁用的时候，才可能抢占内核。
一个例子：当A在处理异常的时候，一个中断的处理程序唤醒了优先级更高的B，在抢占内核的情形，就会发生强制性进程切换。这样做的目的是减少dispatch latency，即从进程（结束阻塞）变为可执行状态到它实际开始运行的时间间隔，降低了它被另外一个运行在内核态的进程延迟的风险。
进程描述符中的thread_info字段中有一个32位的preempt_counter字段，0-7位为抢占计数器，用于记录显式禁用内核抢占的次数；8-15位为软中断计数器，记录可延迟函数被禁用的次数；16-27为硬中断计数器，表示中断处理程序的嵌套数（irq_enter()递增它，irq_exit()递减它）；28位为PREEMPT_ACTIVE标志。只要内核检测到preempt_counter整体不为0，就不会进行内核抢占，这个简单的探测一下子保证了对众多不能抢占的情况的检测。
说明：
1）为了避免在可延迟函数访问的数据结构上发生的竞争条件，最简单直接的方法是禁用中断，但禁用中断有时太夸张了，所以有了禁用可延迟函数这回事。
2） PREEMPT_ACTIVE标志的本意是说明正在抢占，设置了之后preempt_counter就不再为0，从而执行抢占相关工作的代码不会被抢占。
它可被非常tricky地这样使用：
preempt_schedule()是内核抢占时进程调度的入口，其中调用了schedule()。它在调用schedule()前设置PREEMPT_ACTIVE标志，调用后清除这个标志。而schedule()会检查这个标志，对于不是TASK_RUNNING(state != 0)的进程，如果设置了PREEMPT_ACTIVE标志，就不会调用deactivate_task()，而deactivate_task()的工作是把进程从runqueue移除。
你可能会疑惑，为什么要预防已经不在RUNNING状态的进程从runqueue中移除？设想一下，一个进程刚把自己标志为TASK_INTERRUPTIBL，就被preempt了，它还没来得及把自己放进wait_queue中...这个时候当然要让它回头接着运行，直到把自己放进wait_queue然后自愿进程切换，那时才可以把它从runqueue中移除。
在面对内核的时候，思维不能僵化在操作系统提供给用户的进程切换的抽象中，而要想象一个永不停歇运行着的、虽然有意识地跳来跳去的指令流的。所以，没有标志为RUNNING不意味就不会还剩下一些（比如处理状态转换的）代码需要执行哦。
通过这个标志，保证了被抢占的进程将可以被正确地重新调度和运行。
在中断、异常、系统调用返回过程中也会设置PREEMPT_ACTIVE标志。
原本发表在我的技术博客：
　　
http://utensil.javaeye.com/category/69495

《深入理解LINUX内核》的笔记-第683页 - Reverse Mapping for Anonymous Pages

Figure 17-1 的解读：
page descriptor，即 struct page 包含了一个指向 struct anon_vma的结构，anon_vma包含了一个双向链表，链表的元素为 struct vm_area_struct 类型，每一个元素表示该vm area有一个虚拟页被map到了该物理页帧。struct vm_area_struct又包含了一个指向struct mm_struct的指针，我们知道mm_struct代表了某一个进程的地址空间，该结构体包含了一个指向该进程 PGD(page global directory)的指针 pgd，根据pgd我们就可以找到该进程的所有PTE，每一个PTE指向一个page descriptor所代表的物理页帧。Reverse Mapping 的目的就是在reclaim某一个物理页帧时，能够快速定位到所有指向它的PTEs，（这些PTEs可能分散在不同的进程，也可能分散在统一进程的不同vm_area_struct）。
Q1: 有了pgd，最终我们是可以定位到指向该物理页帧的PTE的，最笨的办法是挨个遍历所有的PTE，但是这个办法效率太低了。因为pgd是以线性地址为索引的，如何快速地从定位到该PTE呢？
A: The Page Table entry can then be determined by considering the starting linear address of the anonymous page, which is easily obtained from the memory region descriptor and the index field of the page descriptor.
Q2: 有没有可能一个vm_area_struct 有多个虚拟页面指向同一个物理页帧？如果允许，那么Q1中的定位方法还能使用吗？

《深入理解LINUX内核》的笔记-第89页 - The lists of TASK_RUNNING processes

Linux 2.6 implements the runqueue differently这里的新的runqueue实现应该就是指O(1)时间的调度算法，这个在现在的kernel也不用了，用的是CFS算法，据说是O(1)算法会导致饿死

《深入理解LINUX内核》的笔记-第378页 - Page Fault Exception Handler

do_page_fault 源码：http://lxr.free-electrons.com/source/arch/x86/mm/fault.c#L1283
The first operation of do_ page_fault( ) consists of reading the linear address that caused the Page Fault. When the exception occurs, the CPU control unit stores that value in the cr2 control register是CR2寄存器

《深入理解LINUX内核》的笔记-第92页 - the pidhash table and chained lists

Table 3-5:
现在pid只有3类了， PID, PGID和SID，即pid, thread group id 和 session id
http://lxr.free-electrons.com/source/include/linux/pid.h#L6
其中PID和PGID可以在task_struct 的 pid和tgid直接获得。而 sid比较复杂，目前我只知道用这个表达式可以获取得到
task_struct.pids[2].pid->numbers[0].nr
现在的pid已经有namespace机制（实现container的关键技术), 因此 现在已经没有 find_task_by_pid, 只有 find_task_by_pid_ns，它接受2个参数，即pid和pid_namespace
http://lxr.free-electrons.com/source/kernel/pid.c#L452
还有另外一个函数 find_task_by_vpid, 虽然只接受1个参数，但是它会在current task的namespace里面找。
http://lxr.free-electrons.com/source/kernel/pid.c#L460
这也产生了另外一个需求，即从一个 task_struct找到它的pid namespace
http://lxr.free-electrons.com/source/kernel/pid.c#L546
其基本实现就是 task_struct.pids[PIDTYPE_PID].pid->numbers[pid->level].ns
值得一提的是，即使有不同的namespace，但是系统只有一个hash table： pid_hash
http://lxr.free-electrons.com/source/kernel/pid.c#L44

《深入理解LINUX内核》的笔记-第70页

看起来有点费劲，难道是我老了吗？

《深入理解LINUX内核》的笔记-第707页 - The kswapd kernel threads

Some memory allocation requests are performed by interrupt and exception handlers, which cannot block the current process waiting for a page frame to be freed; moreover, some memory allocation requests are done by kernel control paths that have already acquired exclusive access to critical resources and that, therefore, cannot activate I/O data transfers.需要周期性reclaim pages的主要原因：kernel中有很多操作是不能sleep的

《深入理解LINUX内核》的笔记-第680页 - Design of the PFRA

PFRA使用LRU来区分used和in-used page，其实就是评估page是否活跃，reclaim肯定是先reclaim不活跃的page。那么问题就来了，PFRA要如何track每个page上一次被使用的时间呢？一些CPU体系结构从硬件层面提供LRU支持，即在page table entry中记录上一次被使用的时间，然后自动更新这些信息。然而x86并不支持这个特性，那么x86上的Linux又应该如何设计的呢？

《深入理解LINUX内核》的笔记-第350页 - Releasing a Noncontiguous Memory Area

Further accesses of the process to the released noncontiguous memory area will trigger Page Faults because of the null page table entries. However, the handler will consider such accesses a bug, because the master kernel page tables do not include valid entries.1. 释放非连续内存需要清除页表相关内容，跟分配时一样，这个操作只改动master kernel page table，并没有修改process page table。
2. 分配非连续内存时，process page table跟master kernel page table同步之后，process PGD和master kernel PGD的entries是一致的，这说说明在释放内存之前process PGD跟master kernel PGD 指向相同的PUD，从而PMD和page tables也是相同的。
3. 释放内存时，kernel只清除相关的的 pte，PUD和PMD保持不变。在所有pte都被清除的情况下，page table所占用的内存页不会被kernel回收，所以下次进程在kernel mode下试图访问这些内存区域时，会产生page fault，page fault handler在处理缺页是会发现master kernel page table没有包含合法的pte，所以不会复制pte，从而会认为这是一个bug。
题外话：32位linux这种内存设计虽然非常tricky，但是非常丑陋，Linus曾经固执的认为32位的linux永远不会支持超过1G的内存，以这个准则去设计linux 内存管理系统，后来当然也妥协了，但是只能修修补补，做一些非常tricky的hack。记得Linus在在一个访问中提到，他觉得最后悔的设计就是linux 32位系统的内存管理

《深入理解LINUX内核》的笔记-第40页 - Memory addressing

每个segment selector都对应一个segment descriptor 用来描述segment 的信息，包括segment 第一个byte的起始地址（这个地址是virtual address, or linear address)
8086 处理器里有段寄存器(register)，例如cs, ds, ss等。
注意，8086 处理器里 还有专门的、给segment descriptor有各自的寄存器（register), 程序员不能直接给这些descriptor 寄存器赋值，当一个segment selector 载入cs或其他段寄存器时，descriptor 寄存器的值是CPU自动从内存里载入的。
问题有，
1. 从内存哪个区域读入descriptor 的值呢？也就是，descriptor 的值保存在内存哪里呢?
2. 这些descriptor值是由OS来管理的吗？那是不是有一个表格，把 selector 和 descriptor 一一对应起来？在GDT中吗？
答案在40页里找到：
这些descriptor的确是保存在GDT或LDT里的。
的确有一个把selector 和 descriptor 一一对应起来的机制，用的就是selector 的高13位（3rd - 15th bit), 这个13位的值叫做 Index。把index 乘以8，就得到了对应的descriptor 在GDT上的偏移量。
书上举了一个例子，如果GDT的值是0x00020000, 而一个selector的Index的值是 2， 那么这个selector对应的descriptor 地址是0x00020000 + （2 * 8） = 0x00020010 （注意是10进制转16进制，2*8 = 16 = 0x10 )。
原来这个GDT就是存第一个descriptor的地址的！
下一个问题，如果修改了这个GDT指定的内存区域里的值，那么就可以改变程序对这个段的权限了？例如我把0x00020010 指定的descriptor 的值 中间的DPL位的值改变，那就可以修改权限了！不是吗? 我们可以这么做吗？

《深入理解LINUX内核》的笔记-第105页 - CH3: Process - Perfoming the Process Switch

好不容易回来看进程切换。之前看不懂的地方都被我记着了，现在其实我也才看到200页不到，碰巧有时间回来解决一下最看不懂的switch_to这个进程切换的关键宏。
首先是分享一个讲到switch_to的一篇博文：http://www.cnblogs.com/wz19860913/archive/2010/06/02/1748921.html
另外是我今天查了一下原来mov是intel汇编语言用的，movl是at&t的（*nix多用这种），而它们语法中的dst和src位置刚好相反，我草坑爹啊
为什么switch_to需要有3个参数prev,next,last？场景是这样的：
假设发生了3次进程切换，顺序如下：
A->B
B->C
C->A
当第一次切换前，prev=A，next=B，last=A
当最后切换到A时，由于进程的上下文已经被恢复了，所以这个时候prev=A，next=B没问题。假设没有last，就不知道是从哪个进程切换到A的，为了满足这个需求，last被赋值为上一个执行进程的进程描述符。
switch_to这个宏的执行过程分为下面4块：
1.保存数据。保存prev、next信息到寄存器，把eflags寄存器和ebp寄存器的内容压栈到当前进程（prev）的栈顶。把esp堆栈指针保存到prev下的thread.esp域中。
2.进程切换。将esp堆栈指针替换为next下的thread.esp。这就说明现在开始内核操作的内核堆栈是next下的。实际就是发生进程切换了。
3.执行__switch_to函数
4.恢复ebp和eflags寄存器的内容，给last赋值
————————————————————————————
至于__switch_to这个函数，可以参见上面给出的那个博客的地址的代码，然后对照着书上就能大致明白了。
关于上述博客地址中出现的fastcall（从eax,edx寄存器获得参数）可以参见这篇博文：http://blog.csdn.net/fly2k5/article/details/544112
忘记了TSS是啥的可以参见百科（或者直接看本书）：http://baike.baidu.com/view/1245759.htm?fr=aladdin#2

《深入理解LINUX内核》的笔记-第69页 - Memory Addressing: Provisional Kernel Page Tables

这一页的前后我来回看了很多次，我感觉这本书说得不太清楚啊我擦，不过可能对于很熟悉操作系统的人来说，这本书说得已经够清楚的了。
首先是为什么768条entry就是3MB，其实这个就是768 * 4KB = 3MB，4KB是一个页表或者页帧的大小。
这一节书中说要让0xc0000000~0xc07fffff的虚拟地址能映射到0x00000000~0x007fffff的物理地址，同时要让0x00000000~0x007fffff的虚拟地址能映射到0x00000000~0x007fffff的物理地址。也就是说上面提到的两个虚拟地址都映射到同一个物理地址中。意思就是让用户模式下执行的代码（代码段所在虚拟地址小于0xc0000000）以及让内核模式下执行的代码（代码段所在虚拟地址大于等于0xc0000000）的程序能访问同一个物理地址的内容。然后就是书中所说的0，1，0x300，0x301是啥意思？其实就是在全局页目录（Page Global Directory）中的第0，1，0x300，0x301条记录，其中0和1组成了两条记录，每条记录对应一张页面，2张页表刚好可以访问8MB的物理地址，这就是说虚拟地址为0x00000000~0x007fffff可以访问8MB的物理地址；0x300和0x301同理。
接着0和0x300的地址域会被设置为物理地址pg0，而1和0x301的地址域会被设置为pg0后面一个页框的地址，这样就完成了虚拟地址到物理地址的映射。
我知道一份和这个有关的笔记，也可以参考：http://www.douban.com/note/57007577/

《深入理解LINUX内核》的笔记-第42页 - memory addressing

Linux不提倡用segmentation, 因为segmentation和paging 功能重能合了，都是为了与实际地址分开。
P42里给出了四种固定的 descriptor的值， user data, user code, kernel data 和kernel code. 在 user mode 里的进程都用相同的user descriptor (也就是 user data, user code，所有用户进程都一样的), kernel mode就用 kernel data 和kernel code 两种descriptor .

《深入理解LINUX内核》的笔记-第343页 - Linear Addresses of Noncontiguous Memory Areas

1. vmalloc: 非连续内存只能HIGH_MEM分配
2. vmalloc_32: 只在ZONE_NORMAL和ZONE_DMA分配非连续内存
2. 这是在32bit的x86上的设计，64位是否需要这么复杂？

《深入理解LINUX内核》的笔记-第50页 - memory addressing

以此为激励起床的~~起床效果还不错，不过。。
TT 好不容易看完了introduction, 后面看不懂啊。。。全是宏神马的，
原以为是一些很经典的c代码呢
还是扎扎实实的看K&R c 吧先。。。

《深入理解LINUX内核》的笔记-第676页 - Page Frame Reclaiming

Reclaim page frame时，page table是如何变化的？
P679:
1. Reclaim disk caches的page frame时，不需要修改page table
2. Reclaim non-shared page时，需要清除进程相应的page table entry
3. Reclaim shared page时，需要清除所有引用这个page的进程的page table entry

《深入理解LINUX内核》的笔记-第303页 - Requesting and releasing page frames

alloc_pages 只返回第一个page的地址，由于所有的page都放在mem_map数组中，所以我们能知道后续page的地址。应该是这样吧？

《深入理解LINUX内核》的笔记-第29页 - Zombie processes

When a process terminates, the kernel changes the appropriate process descriptor pointers of all the existing children of the terminated process to make them become children of init. This process monitors the execution of all its children and routinely issues wait4( ) system calls, whose side effect is to get rid of all orphaned zombies.Init 调用wait4 的时候，如果子进程还没退出，是否会被阻塞？

《深入理解LINUX内核》的笔记-第680页 - Reverse Mapping

Q: 为什么需要Reverse Mapping？
A: As stated in the previous section, one of the objectives of the PFRA is to be able to free a shared page frame. To that end, the Linux 2.6 kernel is able to locate quickly all the Page Table entries that point to the same page frame. This activity is called reverse mapping .更加具体的场景：swap out page的时候需要更改所有的page table entries，令其失效。
Q: 如何区分mapped 和 anonymous pages ?
A: The mapping field of the page descriptor determines whether the page is mapped or anonymous, as follows: ...
这一章节讲得太抽象，应该白涉及到的几个数据结构列出来的：
page descriptor, struct page, 代表了每一个物理页帧: http://lxr.linux.no/linux+v3.19.1/include/linux/mm_types.h#L44
memory descriptor, struct mm_struct, 代表了整个进程的地址空间， http://lxr.linux.no/linux+v3.19.1/include/linux/mm_types.h#L346
memory region descriptor, struct vm_area_struct ,具体可参见 Linux Kernel Deverlopment 第3版 P309: http://lxr.linux.no/linux+v3.19.1/include/linux/mm_types.h#L248
anon_vma: http://lxr.linux.no/linux+v3.19.1/include/linux/rmap.h#L27
address_space: http://lxr.linux.no/linux+v3.19.1/include/linux/fs.h#L398

《深入理解LINUX内核》的笔记-第102页 - Process:Process Resource Limits

我看了这一页就没搞懂rlim_cur和rlim_max到底具体的区别在哪里。
后来了解到rlim_cur对于没有CAP_SYS_RESOURCE权限的用户来说，它的值最大只能被设置为rlim_max；而对于有CAP_SYS_RESOURCE权限的用户来说，它的值就可以不受限制。而实际在程序判断资源限制的时候，是根据rlim_cur来做判断的。
擦，我感觉看了这本书我自己也说不清这个了，也或许是我特么还是没搞懂。
不过感觉这个网页能够提供一点帮助：http://www.cnblogs.com/niocai/archive/2012/04/01/2428128.html
另外好像吐槽一下这本书通篇文字，直观的图片都没几个，看着真特么难受

《深入理解LINUX内核》的笔记-第84页 - Identifying a Process

The getpid( ) system call returns the value of tgid relative to the current process instead of the value of pid, so all the threads of a multithreaded application share the same identifier. Most processes belong to a thread group consisting of a single member; as thread group leaders, they have the tgid field equal to the pid field, thus the getpid( ) system call works as usual for this kind of process.

《深入理解LINUX内核》的笔记-第357页 - Memory Regions

vm_area_struct: http://lxr.free-electrons.com/source/include/linux/mm_types.h#L256
Memory regions owned by a process never overlap, and the kernel tries to merge regions when a new one is allocated right next to an existing one. Two adjacent regions can be merged if their access rights match.
The map_count field of the memory descriptor contains the number of regions owned by the process. By default, a process may own up to 65,536 different memory regions; however, the system administrator may change this limit by writing in the /proc/sys/vm/max_map_count file.
在我的ubuntu 14.04 上，这个数值是65530
A frequent operation performed by the kernel is to search the memory region that includes a specific linear address.具体进行哪些操作的时候需要查找memory region ?
The head of the red-black tree is referenced by the mm_rb field of the memory descriptor. Each memory region object stores the color of the node, as well as the pointers to the parent, the left child, and the right child, in the vm_rb field of type rb_node.
最新的rb_node的定义: http://lxr.free-electrons.com/source/include/linux/rbtree.h#L35
在2.6.11版本，也就是本书所采用的版本的结构是：
struct rb_node
{
struct rb_node *rb_parent;
int rb_color;
#define RB_RED 0
#define RB_BLACK 1
struct rb_node *rb_right;
struct rb_node *rb_left;
};
rb_color 应该是被encoded到parent指针里了，可以省4个字节

《深入理解LINUX内核》的笔记-第4页

Linux 2.6内核笔记【Process-3：fork、内核进程】
Utensil按：
最后的几篇Linux内核笔记实在是太难产了，这中途读完了APUE，并以JavaEye闲聊的形式做了无数细小的笔记（不日将整理为博客）；也第3次（还是第4次?）阅读了《ACE程序员指南》，不过这一次终于做下了笔记；也看完了Programming Erlang，用Erlang来写基于UDP的TCP的ErlyUbt已经渐渐现出眉目，也已push到了GitHub上面。可惜就是这段时间的该做的正事却没什么进展...
《Understanding Linux Kernel》在18号必须还给图书馆了...在这两天电脑坏了的日子里，第3次读了即将做笔记的中断与异常、内核同步、时间测量，其余的章节也略读完毕，这些章节希望能够写成一些细小的闲聊。预期电脑应该在今晚恢复正常，在这之前，我来到图书馆，开始写作这酝酿已久的笔记。 第一篇，是对Process的一个收尾。
【Process的终止 】
这不是本笔记关注的重点，只记下以下一点：
C库函数exit()调用exit_group()系统调用（做事的是do_group_exit()），这会终止整个线程组，而exit_group()会调用exit()系统调用（做事的是do_exit()）来终止一个指定的线程。
Process的诞生
POSIX里，创建process需要fork()，古老的fork()是很汗的，它会完整复制父进程的所有资源。Linux则将fork细分为下面三种情况：
如果是fork一个正常进程，那么就用Copy-on-Write（CoW）技术，子进程先用着父进程的所有页，它企图修改某一页时，再复制那一页给它去改；
如果要的是线程（轻量级进程），那么就是大家共同享有原先那些资源，大家一条船；
还有就是vfork()所代表的情况：子进程创建出来后，父进程阻塞，这样老虎不在家，猴子当大王，子进程继续用原先的地址空间，直到它终止，或者执行新的程序，父进程就结束阻塞。
一个关于系统调用的准备知识：系统调用xyz()的函数名往往为sys_xyz()，下文对系统调用仅以sys_xyz()的形态表达。
【clone()界面】

在Linux里，创建进程的总的界面是clone()，这个函数并没有定义在Linux内核源代码中，而是libc的一部分，它负责建立新进程的stack并调用sys_clone()。而sys_clone()里面实际干活的是do_fork()，而do_fork()做了许多前前后后的琐事，真正复制进程描述符和相关数据结构的是copy_process()。
clone()是这个样子的：clone(fn, arg, flags, child_stack, 其它我们不关心的参数)。
fn是新进程应执行的函数， arg是这个函数的参数。
flags的低字节指定新进程结束时发送给老进程的信号，通常为SIGCHLD，高字节则为clone_flag，clone_flag很重要，它决定了clone的行为。有趣的一些clone_flag包括（这些flag定义于<linux/ include/ linux/ sched.h >）：
CLONE_VM(Virtual Memory)：新老进程共享memory descriptor和所有Page Table；
CLONE_FS(File System)；
CLONE_FILES；
CLONE_SIGHAND(Signal Handling)：新老进程共享信号描述符（signal handler和现已blocked/pending的信号队列）；
CLONE_PTRACE：用于Debugging；
CLONE_PARENT：老进程的real_parent登记为新进程的parent和real_parent；
CLONE_THREAD：新进程加入老进程的线程组；
CLONE_STOPPED：创建你，但你别运行。
child_stack则是新进程用户态stack的地址，要么共享老进程的，要么老进程应为新进程分配新的stack。
【do_fork()探究 】
书中说：fork()和vfork()只不过是建立在调用clone()基础上的wrapper函数（也在libc中），实际上：
C代码
asmlinkage int sys_fork(struct pt_regs regs)
{
return do_fork(SIGCHLD, regs.esp, &regs, 0, NULL, NULL);
}

asmlinkage int sys_clone(struct pt_regs regs)
{
/* 略去用于把regs拆开成可以传递给do_fork的参数的代码 */
return do_fork(clone_flags, newsp, &regs, 0, parent_tidptr, child_tidptr);
}

asmlinkage int sys_vfork(struct pt_regs regs)
{
return do_fork(CLONE_VFORK | CLONE_VM | SIGCHLD, regs.esp, &regs, 0, NULL, NULL);
}
asmlinkage int sys_fork(struct pt_regs regs)
{
return do_fork(SIGCHLD, regs.esp, &regs, 0, NULL, NULL);
}
asmlinkage int sys_clone(struct pt_regs regs)
{
/* 略去用于把regs拆开成可以传递给do_fork的参数的代码 */
return do_fork(clone_flags, newsp, &regs, 0, parent_tidptr, child_tidptr);
}
asmlinkage int sys_vfork(struct pt_regs regs)
{
return do_fork(CLONE_VFORK | CLONE_VM | SIGCHLD, regs.esp, &regs, 0, NULL, NULL);
}
我一开始猜想，fork()和vfork()直接呼唤sys_fork()和sys_vfork()应该也没什么问题，但是，注意到这三个系统调用都只接受pt_regs这样仅包含寄存器的参数，显然clone()的工作中主要的部分是把它自身接受的参数转换成寄存器的值，事实上，clone还需要将fn和args压入stack，因为do_fork()是这样子的：
do_fork(clone_flags, stack_start, regs, 一些我们不关心的参数)
也就是说do_fork不了解也不需要知道fn和args，它做完fork之后，在某个return处，类似于之前在process切换用过的技巧（jmp+ret）将使CPU从stack中获取返回地址，并错误而正确地拿到了fn的地址。这正是clone()这个wrapper要做的事情，fork()和vfork()不妨复用clone()的辛苦。
do_fork()调用完copy_process之后，除非你指定CLONE_STOPPED，就会呼唤wake_up_new_task()，这里面有一点很有趣：
如果新老进程在同一CPU上运行，而且没有指定CLONE_VM（也就是终究要分家，要动用CoW），那么就会让新进程先于老进程运行，这样，如果新进程一上来就exec，就省去了CoW的功夫。
这是因为exec内部会调用flush_old_exec()，从与老进程的共享中中脱离，从此拥有自己的信号描述符、文件，释放了原先的mmap，消灭了对老进程的所有知识——这正是为什么成功执行的exec不会返回也无法返回。总之，此后再也没有共享，自然也不会需要CoW。（参见《Program Execution》一章《exec function》中的介绍。）
【内核进程（Kernel thread） 】
什么是书中所说的“内核线程”？首先要说明，由于Linux内核中对process和thread的混用，这里的thread其实完全可以理解为process，等价于普通的进程，不能理解为老进程中的一个属于内核的线程。因此，下文都称之为内核进程。
内核进程是会和其他进城一样被调度的实体，它和进程的唯一区别就是，它永远运行于内核态，也只访问属于内核的那一部分线性地址（大于PAGE_OFFSET的）。
这就使得创建它的时候非常省事，直接和创建它的普通进程共享小于PAGE_OFFSE的线性地址，反正它也不用：
C代码
int kernel_thread(int (*fn)(void *), void * arg, unsigned long flags)
{
/* 略去用于设置regs的代码 */
return do_fork(flags | CLONE_VM | CLONE_UNTRACED, 0, &regs, 0, NULL, NULL);
}
int kernel_thread(int (*fn)(void *), void * arg, unsigned long flags)
{
/* 略去用于设置regs的代码 */
return do_fork(flags | CLONE_VM | CLONE_UNTRACED, 0, &regs, 0, NULL, NULL);
}
<linux/ include/ linux/ sched.h >中甚至定义了
#define CLONE_KERNEL (CLONE_FS | CLONE_FILES | CLONE_SIGHAND )
可供kernel_thread()调用的时候使用，这样节省的克隆就更多了。
内核进程由于不受不必要的用户态上下文拖累，可以用于执行一些重要的内核任务，比如，刷新磁盘高速缓存，交换出不用的pageframe，服务网络连接等等，这些任务以前是周期性执行的进程，是线性的执行方式，现在的内核把用户态从他们身上剥离，并且和其它进程放到一起来调度，能获得更好的响应表现。
所有进程的祖先是进程0，称为idle进程或swapper进程，它是内核初始化时创建的一个内核进程，它初始化一堆数据结构之后会创建init进程，执行init()函数，其中调用exec执行了init程序，至此，init进程变成了一个普通进程。而idle进程之后则一直执行cpu_idle()函数没事干。调度程序只有在没有进程处于可运行状态（TASK_RUNNING）才会选择它。
如果有多个CPU，BIOS一开始会禁用其它CPU，只留一个，进程0就在其上诞生，它会激活其它CPU，并通过copy_process让每个CPU都有一个pid为0的进程，从而形成了每个CPU都有一个0进程的局面。
原本发表在我的技术博客：
　　
http://utensil.javaeye.com/category/69495

《深入理解LINUX内核》的笔记-第69页 - Provisional kernel Page Tables

For the sake of simplicity, let’s assume that the kernel’s segments, the provisional Page Tables, and the 128 KB memory area fit in the first 8 MB of RAM. In order to map 8 MB of RAM, two Page Tables are required.这是32bit的情况，在x86_64中应该是4张Page Table吧

《深入理解LINUX内核》的笔记-第51页 - 分页机制

书中有些地方没有很好地说明为什么二级分页结构比一级分页结构好，只是简单地说系统可以不为仍未使用的页表分配内存以节省空间，难道一级分页不能为未分配的页表节省空间？实际是这样，当一个线性地址过来的时候，如果使用一级分页，那么内存也必须能够找到这个一级分页所在的位置，这个位置存的内容叫一个entry，每个entry里面有一个P标记，P标记记录了当前内存是否有对应的物理地址。
而当使用二级分页结构时，系统首先查找的是页目录，页目录也是必须能够找到的，然后查看页目录的P标记，如果P标识没有被设置（即P标识为0）那么就不用再查这个页目录下的页表了，这些页表在内存中根本查不到。
因此关键问题在于第一级内容是必须被查到的，如果第一级的记录数量是2^10条，那么占用的大小就是2^10 * 32bit = 4KB，如果第一级的记录数量是2^20条，那么占用的大小是2^20 * 32bit = 4MB。因此对于一个程序，使用一级分页结构每个程序的页表大小最小为4MB，而使用二级分页结构则是4KB。当然无论使用一级还是二级分页结构，他们最终能映射到的内存范围是一样的。
关于页目录和页表中的一个entry的结构，大致可以参考下图：页表记录结构http://blog.csdn.net/drshenlei/article/details/4350928

《深入理解LINUX内核》的笔记-第348页 - Allocating a Non Continuous Memory Area

1. vmap: 跟 vmalloc作用类似，只不过vmap并不分配物理内存页
2. a noncontiguous memory area can be allocated by the vmalloc_32( ) function, which is very similar to vmalloc( ) but only allocates page frames from the ZONE_NORMAL and ZONE_DMA memory zones.疑问：ZONE_NORMAL和ZONE_DMA不是直接映射的吗？为什么还能够分配非连续内存？
3. 用vmalloc分配非连续内存时，需要而且只需要修改master kernel page table，并不修改进程的page table（进程的page table包含了kernel page table)，由于进程的page table并不包含新分配的内存的相关entries，因而进程在kernel mode反问这一部分内存时，会产生page fault，page fault handler会从master kernel page table从复制相关的条目，从而保持进程page table跟kernel page table之间的同步。
疑问：如果这部分分配的内存被释放了，那么进程 page table和master kernel page table之间又是如何保持同步的呢？

《深入理解LINUX内核》的笔记-第2页

Linux 2.6内核笔记【Process-1】
终于挣脱了《Understanding the Linux Kernel》的Process一章。中文版的翻译低级错误太多，所以只好继续看影印版。
简介部分，除了通常我们对Process的认识，Linux中值得一提的是：笨重的不分青红皂白把父进程整个地址空间都复制过来的fork()采用了传说中的Copy-on-Write技术；还有就是2.6启用了lightweight process来支持native的thread。从前是模拟pthread实现，现在的native thread有了LinuxThreads, Native POSIX Thread Library(NPTL)和IBM's Next Generation Posix Threading Package(NGPT)这些库支持。而这又引入了thread group的概念，因为属于同一进程的多个线程(lightweight process)虽然是process，却要以某种一致的方式响应getpid()之类的系统调用，因此被放在同一个thread group中。
也因为这个原因，本文中的process都直接写英文，偶尔出现进程，那是在传统的语境下讨论进程与线程之间的关系。
Process Descriptor，也就是struct task_struct，又名task_t，是一个长达306行，集合了众多设计智慧的结构。它非常复杂，不仅有很多字段来表征process的属性，还有很多指向其他结构的指针，比如thread_info这个非常重要的结构。
【process的状态 】
字段state
运行着的
TASK_RUNNING 其实是 可运行的。schedule()会按照时间片轮流让所有状态为TASK_RUNNING的process运行。
睡眠着、等待着的
TASK_INTERRUPTIBLE 在等待hardware interrupt, system resource,或是signal。
TASK_UNINTERRUPTIBLE 同上，但signal叫不醒。
停下来了的
TASK_STOPPED 退出了。
TASK_TRACED 被Debugger停下来。
字段exit_state或state：
EXIT_ZOMBIE 非正常死亡。其parent process还没有用wait4()或waitpid()获取他的遗物，所以内核不敢焚烧尸体。
EXIT_DEAD 遗物获取完毕了，可以焚烧尸体了。如果是非正常死亡，由于init会接过来做养父，所以init会获取他的遗物。
【process之间的组织 】

有时候面向对象的思想会阻碍我们对现实世界的表达，尤其是可能阻碍性能上的优化。
STL这种利用泛型实现的不侵入的，一般化的途径固然好。但 2.6内核中task_t的结构说明，使用侵入式的embeded数据结构，可以更好地在实体间织出多种关系，满足性能和各方面的要求。
只使用task_t一个结构，利用embeded的双向链表(struct list_head)和单向链表(struct hlist_head)，process之间就织出了process list、runqueue、waitqueue、pidhash table、chained list(thread group)等多个关系，并由外在的array统领，实现了高效率的查找与多个字段间的映射。
此笔记不具体复述书中的讨论，只勾勒基本图景。
process list包含了所有的task_t， 用的是双向链表，内嵌字段名是tasks。
runqueue包含了所有state为TASK_RUNNING的task_t，由140个（一个优先级一个）双向链表组成，内嵌字段名是run_list。这140个双向链表的头放在struct prio_array_t里的一个array中。
我们知道，PID可以唯一identify一个process。其实PID有4种，一种是process自身create时候内核 sequentially分配的ID(pid)，一种是thread group中leader的PID（tgid），这个ID其实是进程的主线程的ID，一种是process group中eader的PID(pgrp)[补充介绍：process group的一个常见例子就是：在Bash中执行ls|grep sth|more这样的命令，这里3个process就应该被组织在一个process group中]，还有一种是一个session中leader的PID。
因此pidhash table是一个有4项的array，每个array分别是一个对该类PID的hash。这个hash对collision的解决办法是chaining。以tgid为例，collide的tgid的进程被一个单向链表chain着，而同一tgid的进程则只有leader挂在chian上，其他则以双向链表的形式挂在leader上。
注意，根据我在LXR中的查证，2.6.11中的对pidhash table、chained list很重要的struct pid，在最新的2.6.29中已经被包裹在struct pid_link中，而且内部的字段也脱胎换骨，其中用于表达thread group的内嵌双向链表字段被拆出来直接放在task_t里。这样对thread group的表达就更为清晰直接。因此书中的讨论已不完全适用。
waitqueues，则是所有TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE状态的process。它们按所等待的事件分别排在不同的队（双向链表）中。
这里涉及的结构是wait_queue_t。它除了process的指针，还包含了flag和类型为wait_queue_func_t的唤醒处理函数。
flag为0说明等待的事件是nonexclusive的，所以事件发生时，唤醒所有等它的process，为1说明等待的事件是exclusive的，比如只有一个的资源，就只唤醒一个。
在队列中nonexclusive的process永远从前面加进去（不必分先来后到，大家一起醒），exclusive的process永远从后面加进去（要分先来后到）。这是由add_wait_queue()和add_wait_queue_exclusive()完成的。这样排队，使得wake_up宏中的循环可以在成功唤醒第一个exclusive的process就终止。
睡眠和唤醒process的函数或宏有：sleep_on族、2.6引入的wait族函数、wait_event族宏、wake_up族宏。这里只讲一下sleep_on()。
sleep_on()的本质就是把进程从runqueue拿出来放进wait_queue，然后重新调用schedule()，面对新的runqueue，按照算法，继续调度。schedule()返回之后（说明又让自己执行了），就把自己再从从wait_queue拿出来放进runqueue，然后接着执行自己接下来的代码。
【内核是如何获取当前process的】
用current这个宏可以获得当前process的task_t结构的指针。
低版本Linux的current是一个邪恶的全局变量。高版本则利用了内存布局，智能地推断出当前process。
Linux用一个union把当前process的thread_info和(倒着增长的)kernel栈放在一个两page长（8kb）的内存区域。
C代码
union thread_union {
struct thread_info thread_info;
unsigned long stack[2048]; /* 1024 for 4KB stacks */
};
union thread_union {
struct thread_info thread_info;
unsigned long stack[2048]; /* 1024 for 4KB stacks */
};
利用这样的内存布局，三行汇编就可以获得当前process:

Gnu as代码
movl $0xffffe000,%ecx /* or 0xfffff000 for 4KB stacks */

andl %esp,%ecx

movl (%ecx),p
movl $0xffffe000,%ecx /* or 0xfffff000 for 4KB stacks */
andl %esp,%ecx
movl (%ecx),p
第一二行mask掉esp的一部分，到达了thread_info所对齐的地方。
然后利用指向相应task_t的task字段在thread_info的offset 0的位置的事实，直接**ecx赋值给p，这时p就是当前process的task_t结构的指针。
原本发表在我的技术博客：
http://utensil.javaeye.com/category/69495

《深入理解LINUX内核》的笔记-第3页

Linux 2.6内核笔记【Process-2：切换】
在看Linux内核的时候发现，CPU自己认得（或者说is expecting）很多struct，很多时候内核要做的事情是在内存里准备好这些struct里CPU需要的数据，以供CPU完成相应的任务。比如寻址中的paging部分，内核只需要把page directory中的数据准备好，并把page directory的地址放入cr3，CPU自己就能根据page directory中的数据进行寻址。就像一种契约，CPU对struct的期望，正是内核所要做的事情，反过来说，内核要做的事情仅仅是满足CPU的期望而已。
不知读者是否与我有同感，但对于我而言，这使得写操作系统突然变得远远不如想象中那么困难了。因为困难的地方在底层，在硬件。这正是学编程的世界，没学之前，你永远觉得编程是不可能的事情——如果刚刚学会了C的语法，你会觉得，C里头把数据在内存里移来移去，加加减减，明明是只能让小孩子玩过家家的东西，怎么就可以在屏幕上画画？让机器做事？后来意识到了好多好多的库，原来自己只需要调用API就好了，那 API的那一边又是怎么实现的呢？终于知道API里面是怎么实现的了，却发现这些实现永远也只是在调用另外一层API，只不过更为底层的API。往地里越钻越深，穿越一层又一层的API，才发现最终不过是在为硬件的期望准备内存中的数据。当然这样的描述忽略了同时在底层我们也发出了汇编指令让机器去做一些除了操作内存加加减减的事情，但硬件才是生命自身，它的电路决定了它如何理会指令、中断和各种事件，如何突然不执行我们（比如，当前用户进程）给它的下一个指令，突然知道利用内存中的数据去进行上下文转换，如此等等。
其实上面这番话也可以反过来说。每当我们的知识前进一步，学的更深了，回头望去，我们承学的东西，不过是一层API，一层界面罢了。
一点感想，下面进入正题，这次的笔记是讲述Process的切换：
【TSS】
先介绍一下对80x86的hardware context switch很重要的TSS结构。
Task State Segment
A task gate descriptor provides an indirect, protected reference to a Task State Segment.
The Task State Segment is a special x86 structure which holds information about a task. It is used by the operating system kernel for task management. Specifically, the following information is stored in the TSS:
* Processor register state
* I/O Port permissions
* Inner level stack pointers
* Previous TSS link
All this information should be stored at specific locations within the TSS as specified in the IA-32 manuals.
在Linux低版本中，进程切换仅仅需要far jmp到要切换的进程的TSS的selector所在就可以了。（far jmp除了修改eip还修改cs）。
在Linux 2.6当中，TSS保存在每CPU一个的GDT（其地址存在gdtr中）中，虽然每个process的TSS不同，但Linux 2.6却不利用其中的 hardware context switch以一个far jmp来实现任务转换，而用一系列的mov指令来实现。这样做的原因是：
1、可以检验ds和es的值，以防恶意的forge。
2、硬转换和软转换所用时间相近，而且硬转换是无法再优化的，软转换则可以。
Linux 2.6对TSS的使用仅限于：
1、User Mode向Kernel Mode切换的时候，从TSS中获取Kernel Stack。
2、User Mode使用in或者out指令的时候，用TSS中的 I/O port permission bitmap验证权限.
有一点要注意，process switching是发生在Kernel Mode，在转为Kernel Mode的时候，用户进程使用的通用register已经保存在Kernel Stack上了。然而非通用的register，如esp，由于不能放在TSS中，所以是放在task_t中的一个类型为thread_struct的 thread字段中。
process切换两部分：切换paging这里不讲，切换kernel stack、hardware context是由switch_to宏完成的。
【switch_to宏中的last】
switch_to宏的任务就是让一个process停下来，然后让另外一个process运行起来。
switch_to(prev, next, last)。prev、next分别是切换前后的process的process descriptor(task_t)的地址。last的存在要解释一下：
由于switch_to中造成了进程的切换，所以其中前半部分指令在prev的语境(context、Kernel Stack)中执行，后半部分却在next的语境中执行。
假设B曾切换为O，那么由于一切换，B就停下来了，所以在B的感觉保持是next为O，prev为B。当我们要从A切换到B的时候，一切换B就醒了，但它却仍然以为next是O，prev是B，就不认识A了。然而A switch_to B中的后半部分却需要B知道A。
因此这个宏通常都是这么用的：switch_to(X, Y, X)。
【switch_to详解】

书上认为直接看pseudo的汇编代码比较好，我却觉得直接看Linux源代码中的inline汇编代码更为自在（为了阅读方便和语法高亮有效，却掉了原代码中宏定义的换行，想查看原来的代码，请访问http://lxr.linux.no/linux+v2.6.11/include/asm-i386/system.h#L15 ）：
C代码
#define switch_to(prev,next,last)
do {
unsigned long esi,edi;
asm volatile("pushfl\n\t"
"pushl %%ebp\n\t"
"movl %%esp,%0\n\t" /* save ESP */
"movl %5,%%esp\n\t" /* restore ESP */
"movl $1f,%1\n\t" /* save EIP */
"pushl %6\n\t" /* restore EIP */
"jmp __switch_to\n"
"1:\t"
"popl %%ebp\n\t"
"popfl"
:"=m" (prev->thread.esp),"=m" (prev->thread.eip),
"=a" (last),"=S" (esi),"=D" (edi)
:"m" (next->thread.esp),"m" (next->thread.eip),
"2" (prev), "d" (next));
} while (0)
#define switch_to(prev,next,last)
do {
unsigned long esi,edi;
asm volatile("pushfl\n\t"
"pushl %%ebp\n\t"
"movl %%esp,%0\n\t" /* save ESP */
"movl %5,%%esp\n\t" /* restore ESP */
"movl $1f,%1\n\t" /* save EIP */
"pushl %6\n\t" /* restore EIP */
"jmp __switch_to\n"
"1:\t"
"popl %%ebp\n\t"
"popfl"
:"=m" (prev->thread.esp),"=m" (prev->thread.eip),
"=a" (last),"=S" (esi),"=D" (edi)
:"m" (next->thread.esp),"m" (next->thread.eip),
"2" (prev), "d" (next));
} while (0)

简单解说一下这里用到的gcc的inline汇编语法。首先看上去像是汇编代码的自然就是汇编代码了，每个指令写到一对""中（这是换行接着写同一个 string的好办法）还要加\n\t实在是比较麻烦但还算清晰可读。如果熟悉AT&T的汇编语法，读起来不是难事。
第一个冒号后面有很多类似于"=m" (prev->thread.esp)的东东以逗号相隔，这些是这段汇编所输出的操作数，=表达了这个意思。其中m代表内存中的变量，a代表%eax，S代表%esi，D代表%edi。但"=m" (prev->thread.esp)和"=a"(last)是完全不同的输出方向，前者在movl %%esp,%0一句中（%0代表了prev->thread.esp）把%esp的内容输出给了prev->thread.esp，后者则独立成句，直接在整段汇编的最后自动将last的值写到%eax，完成了last的使命。
第二个冒号后面的则是输入给这段汇编的操作数。其中d代表%edx。2代表了prev的值将与%2（也就是"=a"(last)）共用一个寄存器。
这些操作数在汇编中以%n（n是数字）的形式引用，输出和输入站在一个队里报数：输出的第一个是%0，顺次递增，到了"m" (next->thread.esp)就排到了%5，依此类推。
本来还应该有一个冒号，用来告诉编译器会被破坏的寄存器（因为笨笨的C编译器认为只有他自己在改寄存器，常常自作主张作出假设进行优化）。这里中途在jmp __switch_to我们的确破坏过%eax，但我们巧妙地改回来了（看下面），我们也破坏了%ebp和eflags，但我们通过一对push和pop 却也恢复了它们。因此我们不需要告诉编译器我们改过，因为我们改回来了。
asm后面的volatile是告诉C编译器不要随便以优化为理由改变其中代码的执行顺序。
还有一个地方需要解释，那就是$1f，这个指的是标号为1的代码的起始地址。在"1:\t"这一行我们定义了这个标号。
如果对gcc的inline汇编产生了兴趣，参见：http://www.ibiblio.org/gferg/ldp/GCC-Inline-Assembly-HOWTO.html#s5
下面开始详细分析：
C代码
/* 首先，我们在prev的语境中执行 */


/* 保存ebp和eflags于prev的Kernel Stack上 */

pushfl
pushl %ebp

%esp => prev->thread.esp /*保存了prev的esp */
next->thread.esp => %esp /*读出next之前保存的esp。这个时候，由于esp被改成了next的Kernel Stack，而标示process的thread_info挨着esp（参见笔记process-1中的对current的解释），我们现在实际变成了是在进程next的语境中执行了。不过我们还没有真正开始执行next自己的代码，且看下面 */

1 => prev->thread.eip /*把标号为1的代码的地址存入prev->thread.eip中，以备将来恢复。如果有人不知道，说明一下：CPU的eip寄存器中放的是CPU要执行的下一行代码的地址 */

/* 正是下面这两句的巧妙配合使得这两句执行完后，CPU完完全全跑去执行next代码，不再执行后面的代码。这也正是原书没有讲清楚的（过于分散了），各位读者注意咯!*/

pushl next->thread.eip /* 把原先保存下来的next的下一条指令地址，push到next的Kernel stack顶部。这个next->thread.eip通常储存的是next被切换之前push进stack的那个标号为1的代码地址（简称：next的1），但如果next从未被切换过，即是一个刚被fork了、新开始执行的进程，那么存在next->thread.eip中的就是 ret_from_fork()函数的起始地址。 */

jmp __switch_to /* __switch_to是一个用寄存器来传达参数的函数，里面执行了检查、保存FPU、保存debug寄存器等琐事。重点是：__switch_to是一个函数！这里居然用的是jmp而不是call！这正是巧妙之处。__switch_to()作为一个函数执行完了之后会返回(ret)，但由于我们不是call它的（call 会自动把下一条指令的地址push入stack顶部，相应地返回的时候ret会从stack的顶部获取返回地址——下一条指令的地址，这是一种完美的配合），ret就把上一句push入stack顶部的next->thread.eip当作下一条指令了，于是我们就自然而然地顺着next之前执行的地址执行下去了，直到下一次process切换回来。 */

/* .......下面的代码不会继续执行......直到进程切换回来然后跳到prev的1 */

1:

popl %ebp
popfl

/* 到这里这个宏就结束了，所以就会顺着执行prev的接下来的代码。这也正是为什么我们之前把prev的1的地址push进stack就可以达到回到prev自己的代码的原因。 */
/* 首先，我们在prev的语境中执行 */
/* 保存ebp和eflags于prev的Kernel Stack上 */
pushfl
pushl %ebp
%esp => prev->thread.esp /*保存了prev的esp */
next->thread.esp => %esp /*读出next之前保存的esp。这个时候，由于esp被改成了next的Kernel Stack，而标示process的thread_info挨着esp（参见笔记process-1中的对current的解释），我们现在实际变成了是在进程next的语境中执行了。不过我们还没有真正开始执行next自己的代码，且看下面 */
1 => prev->thread.eip /*把标号为1的代码的地址存入prev->thread.eip中，以备将来恢复。如果有人不知道，说明一下：CPU的eip寄存器中放的是CPU要执行的下一行代码的地址 */
/* 正是下面这两句的巧妙配合使得这两句执行完后，CPU完完全全跑去执行next代码，不再执行后面的代码。这也正是原书没有讲清楚的（过于分散了），各位读者注意咯!*/
pushl next->thread.eip /* 把原先保存下来的next的下一条指令地址，push到next的Kernel stack顶部。这个next->thread.eip通常储存的是next被切换之前push进stack的那个标号为1的代码地址（简称：next的1），但如果next从未被切换过，即是一个刚被fork了、新开始执行的进程，那么存在next->thread.eip中的就是 ret_from_fork()函数的起始地址。 */
jmp __switch_to /* __switch_to是一个用寄存器来传达参数的函数，里面执行了检查、保存FPU、保存debug寄存器等琐事。重点是：__switch_to是一个函数！这里居然用的是jmp而不是call！这正是巧妙之处。__switch_to()作为一个函数执行完了之后会返回(ret)，但由于我们不是call它的（call 会自动把下一条指令的地址push入stack顶部，相应地返回的时候ret会从stack的顶部获取返回地址——下一条指令的地址，这是一种完美的配合），ret就把上一句push入stack顶部的next->thread.eip当作下一条指令了，于是我们就自然而然地顺着next之前执行的地址执行下去了，直到下一次process切换回来。 */
/* .......下面的代码不会继续执行......直到进程切换回来然后跳到prev的1 */
1:
popl %ebp
popfl
/* 到这里这个宏就结束了，所以就会顺着执行prev的接下来的代码。这也正是为什么我们之前把prev的1的地址push进stack就可以达到回到prev自己的代码的原因。 */
这篇笔记不会解释__switch内部琐屑的细节了，因为最神奇的事情不是发生在里面，人生苦短，不用去琢磨过于琐屑的事情。
原本发表在我的技术博客：
http://utensil.javaeye.com/category/69495

《深入理解LINUX内核》的笔记-第1页

Linux 2.6内核笔记【内存管理】
4月14日
很多硬件的功能，物尽其用却未必好过软实现，Linux出于可移植性及其它原因，常常选择不去过分使用硬件特性。
比如 Linux只使用四个segment，分别是__USER_CS、__USER_DS、__KERNEL_CS、__KERNEL_DS，因为Paging可以完成segmentation的工作，而且可以完成的更好。而且这样简化了很多，统一了逻辑地址和线性地址。
而TSS存在每CPU一个的GDT中，虽然每个process的TSS不同，但Linux 2.6却不利用其中的hardware context switch（虽然低版本使用）以一个far jmp来实现任务转换，而用一系列的mov指令来实现。这样做的原因是：
1、可以检验ds和es的值，以防恶意的forge。
2、硬转换和软转换所用时间相近，而且硬转换是无法再优化的，软转换则可以。

4月15日
Paging也就是将linear地址转成物理地址的机制。
内存被视为一堆4k的小page frame（就像空的格子），在归OS管的Paging机制的苟延残喘下，仿佛地存放着多于page frame数目的page（数据）。要通过两层索引（directroy和table）来寻到page，再加offset寻到址。这两层索引中的entry包含一些标志表明该page在不在内存里，是否被改写过，最近是否访问过，以及读/写访问权限。
如果page entry里的Page Size标志和cr4的PSE标志设置了的话（Extended Paging），就是4M一片page frame，这样就只用directory一层索引了。
从奔腾pro开始，adress针脚非常神奇地从32增加到36，有了一个叫做PAE的机制，它启用（cr4的PAE标志设置）的时候就是2M一片page frame了。这样可以寻址64GB，远远超越了没启用前4GB的理论极限（实际极限1GB）。但这样的寻址非常别扭，因为物理地址虽然因此变成了36位，线性地址仍是32位，要想寻址超过4GB，要用cr3去指向不同的PDPT或在31-30bit指定PDPT中entry。不过，更郁闷的是，这并不能改变process的地址空间4GB的限制，仅仅是内核可以用这么多内存来运行更多的process。
在64位机器上，由于如果只用两层的话，索引条目会太多，严重消耗内存，所以只好再加层数，alpha、ia64、ppc64、sh64都是3层（虽然每层bit数不一），x86_64非常神奇地用了4层。
Paging换的是page，Cache换的是line。但是如何在Cache中确定某个内存地址在不在呢？或者说，某内存地址附近的数据，放在Cache中什么位置好呢？不能一对一映射过来(direct mapping)，这样会导致巨大的Cache；也不能随意放（fully associative）然后在旁边标记(tag)说是什么地址附近的，这样会导致每次找Cache都是线性查找。一个浪费空间一个浪费时间，因此有一种折衷叫做N-Way Set Associative，有点像Hash。首先把Cache分成很多个N line的集合，然后弄个hash函数把一个地址唯一地映射到某个集合里，之后至于放在这N line中的哪一line就无所谓了。找的时候，先一瞬间找到集合，然后对N line进行线性查找。
读的时候，自然有cache hit和cache miss。对于写操作，cache hit的话，可能有两种不同的处理方法：write-through（Cache和RAM都写）和wirte-back（line换出时写RAM）。Linux清空PCD (Page Cache Disable)和PWT (Page Write-Through)，永远启用cache并使用write-back策略。
哈哈，TLB（Translation Lookaside Buffers ）解决了我心中的一大疑问：每次寻址（将linear翻译成physical），都要非常艰辛地查directroy和table，访问多次RAM（你以为这些东西不是放在RAM里啊？！），岂不累死。幸好，我们有TLB，这样最近翻译的成果就可以缓存在里面，这样就省得每次翻译啦。
4月17日
Linux用了四层索引来做Paging。这样既可以通过隐藏掉中间两层来做无PAE的32位paging，又可以隐藏掉pud来支持有PAE的3位paging，还可以支持64位的paging。
pte_t Page Table
pmd_t Page Middle Directory
pud_t Page Upper Directory
pgd_t Page Global Directory
每个进程的内存空间中0到PAGE_OFFSET（0xc0000000，即3G）-1是用户空间，PAGE_OFFSET到0xffffffff（4G）则是内核空间（只有内核态才能寻址）。
启动的时候，Linux问BIOS内存格局如何，保留第1个MB（machine_specific_memory_setup()），然后把自己放在第2个MB开始的地方（从_text到_etext是内核代码，从_etext到_edata是初始化了的内核数据）。
在这个过程中：
Linux首先建立初始（provisional）页表（startup_32()），使RAM前8M（两页）可以用两种方式寻址，用来存放最小的自己（text、data、初始页表、128k的堆空间）。
初始pgd放在swapper_pg_dir中。所有项为0，但0、1与0x300、0x301分别完成线性地址的前8M和3G+8M到物理地址前8M的映射。
接着，Linux建立最终页表。
线性地址最高的128M保留给Fix-Mapped Linear Addresses和Noncontiguous Memory Allocation用，所以，最终页表只需要把PAGE_OFFSET后面的896M映射到物理地址的前896M。剩余RAM由Dynamic Remapping来完成。然后用zap_low_mapping()把原先那个初始页表清掉。
paging_init()会执行：
pagetable_init() //一个循环，初始化了swapper_pg_dir
cr3 <- swapper_pg_dir
cr4 |= PAE
__flush_tlb_all()
Linux利用CPU有限的指令和行为模式，实现了一系列操纵tlb的函数，应用于不同的情境。
值得一记的是Lazy TLB模式，在多CPU系统中，它可以避免无意义的TLB刷新。
原本发表在我的技术博客：
http://utensil.javaeye.com/category/69495

《深入理解LINUX内核》的笔记-第81页 - Process Descriptor

The six data structures on the right side of the figure refer to specific resources owned by the process.大家都知道process是resource分配的单位，那么在linux kernel中这个resource具体指什么呢： 内存、文件、signal、tty ...

《深入理解LINUX内核》的笔记-第362页 - Memory Region Access Rights

3类跟内存权限相关的标志位:
1. 保存在PTE中，为CPU硬件所用
2. 保存在page descriptor，即 struct page，为Linux内核所用
3. 保存在memory region descritor，即 struct vm_area_struct 中

《深入理解LINUX内核》的笔记-第678页 - Selecting a Taget Page

1. Mapped page
2. Anonymous page
3. Shared or non-shared: 如果一个page属于不同的进程地址空间，则是shared的，如果只属于non-shared，则是non-shared的。
4. reclaim pages时，可将其分为unreclaimable, swappable, syncable和discardable

《深入理解LINUX内核》的笔记-第140页 - Interrupts and Exceptions: Interrupt Descriptor Table

我主要是看到IDT的最大存储大小为2048字节时感觉到蒙了，我去，为啥书上直接就说因为一个中断向量对应于IDT的一个记录而每个记录的大小为8字节，所以整个中断描述符表（IDT）的大小就是256*8 = 2048字节。
我了个去啊，这个256是怎么来的？本段一开始说“IDT格式与第二章所描述的GDT及LDT类似”，然后我去翻第2章，特么也没发现这个256是怎么来的呀。
这个时候可能有人会说：傻X，这个256不就是告诉你中断向量不超过256个吗。但是我翻了下第三章还没翻到过，然后翻了好多页的英文我感觉眼睛已瞎。
上网查吧，顺便把参考地址也发这里：
百度百科中断描述符表：http://baike.baidu.com/view/2224051.htm?fr=aladdin
维基百科（看这本晦涩的英文版已经提高你读英文的能力了）：http://en.wikipedia.org/wiki/Interrupt_descriptor_table
百度百科中断向量：http://baike.baidu.com/item/%E4%B8%AD%E6%96%AD%E5%90%91%E9%87%8F?fr=aladdin
这本书读起来对于我这种凡人来说真特么是一种折磨。我看豆瓣对这本书的评论里不少人都给了满5好评，我去，怎么人和人的差距就这么大呢？
再吐槽几句，这本书经常突然来个“Thus”或者“Therefore”，就像上数学课“地球和火星都是行星，因此一年有365天”。这结论我经常没搞懂是怎么搞出来的，当然最大的问题还是出在自己，因为我看了后面几页基本就把前面几页忘了！没错！

《深入理解LINUX内核》的笔记-第81页 - Process State

TASK_INTERRUPTABLE 和 TASK_UNINTERRUPTABLE， 补充两篇相关的文章：
Kernel Korner - Sleeping in the Kernel, 介绍如何在内核中避免一些race condition，从而安全地sleep http://www.linuxjournal.com/article/8144?page=0,0
TASK_KILLABLE，介绍 Kernel中新引入的process state，本书是2005年出版，因此没有介绍这个状态。 http://lwn.net/Articles/288056/
引自第二篇文章：The problem with that idea is that, in many cases, the introduction of interruptible sleeps is likely to lead to application bugs.可见对于user space程序员来说，了解sleep的模式还是很有意义的，在碰到系统调用API时应该将这个性质考虑在内。
Q：常见的系统调用哪些是interruptable？哪些是uninterruptable?

《深入理解LINUX内核》的笔记-第6页

Linux 2.6内核笔记【内核同步】
Utensil按：这应该是最实用，最接近日常编程的一章了。
同步机制用于避免对共享数据的不安全访问而导致的数据崩溃。下面按从轻到重讲述内核同步机制。
【最好的同步】
同步是一件烦人、容易出错，最重要的是拖慢并行的事情，所以最好的同步就是不用同步——这不是废话，而是在内核设计时的重要考虑。对不同的任务，量体裁衣，以不同的机制来处理；对每种机制，加以不同程度的限制，从而不同程度地简化用这个机制完成任务的编码难度，其中就包括减少对同步机制的需要。以下是一些书中举出的“设计简化同步”的例子：
Interrupt handlers and tasklets need not to be coded as reentrant functions.
Per-CPU variables accessed by softirqs and tasklets only do not require synchronization.
A data structure accessed by only one kind of tasklet does not require synchronization.
【每CPU变量（Per-CPU variables）】
第二好的同步技术，是不共享。因此我们有了每CPU变量。但注意：内核抢占可能使每CPU变量产生竞争条件，因此内核控制路径应该在禁用抢占的情况下访问每CPU变量。
【原子操作（Atomic operation）】
具有“读-修改-写”特征的指令，如果不是原子的，就会出现竞争条件。
非对齐的内存访问不是原子的；
单处理器中，inc、dec这样的操作是原子的；
多处理器中，由于会发生内存总线被其它CPU窃用，所以这些操作要加上lock前缀（0xf0），这样可以锁定内存总线，保证一条指令的原子性；
有rep前缀(0xf2、0xf3)的指令不是原子的，每一循环控制单元都会检查挂起的中断。
Linux提供了atomic_t和一系列的宏来进行原子操作。
【优化屏障（Optimization barrier）、内存屏障（Memory barrier）】
编译器喜欢在优化代码时重新安排代码的执行顺序，由于它对某些代码顺序执行的意义没有感知，所以可能对一些必须顺序执行的代码构成致命伤，比如把同步原语之后的指令放到同步原语之前去执行——顺便带一句，C++0x中对并行的改进正是努力使编译器能感知这些顺序的意义。
优化屏障barrier()宏，展开来是asm volatile("":::"memory") 。这是一段空汇编，但volatile关键字禁止它与程序中的其它指令重新组合，而 memory则强迫编译器认为RAM的所有内存单元都给这段汇编改过了，因此编译器不能因为懒惰和优化直接使用之前放在寄存器里的内存变量值。但 优化屏障只阻止指令组合，不足以阻止指令重新排序。
内存屏障原语mb()保证，在原语之后的操作开始执行之前，原语之前的已经完成，任何汇编语言指令都不能穿过内存屏障。
80x86处理器中，I/O操作指令，有lock前缀的指令，写控制、系统、调试寄存器的指令，自动起内存屏障的作用。Pentium 4还引入了lfence、sfence和mfence这些指令，专门实现内存屏障。
rmb()在Pentium 4之后使用lfence，之前则使用带lock的无意义指令来实现。wmb()直接展开为barrier()，因为Intel处理器不会对写内存访问重新排序。
【自旋锁（Spin Locks）】
自旋锁是一种忙等的锁，当获取锁失败，进程不会休眠，而是一直在那里自旋（spin）或者说忙等（busy waiting），不断循环执行cpu_relax()——它等价于pause指令或者rep; nop指令。
自旋锁用spinlock_t表示，其中两个字段，slock代表锁的状态（1为未锁），break_lock代表有无其它进程在忙等这个锁，这两个字段都受到原子操作的保护。
我们详细讨论一下spin_lock(slp)宏（slp代表要获取的spinlock_t）：
首先禁用内核抢占（preempt_disable()），然后调用平台相关的_raw_spin_trylock()，其中用xchg原子性地交换了8位寄存器%al（存着0）和slp->slock，如果交换出来的是正数（说明原先未锁），那么锁已经获得（0已经写入了slp->slock，上好了锁）。
否则，获锁失败，执行下列步骤：
1）执行preempt_enable()，这样其它进程就有可能取代正在等待自旋锁的进程。注意preempt_enable()本质上仅仅是将显式禁用抢占的次数减一，并不意味着就一定可以抢占了，能否抢占还取决于本次禁用之前有否禁用抢占、是否正在中断处理中、是否禁用了软中断以及PREEMPT_ACTIVE标志等等因素。就像，领导说：“我这里没问题了，你问问别的领导的意见吧。”。
2）如果break_lock==0，就置为1.这样，持有锁的进程就能感知有没人在等锁，如果它觉得自己占着太长时间了，可以提前释放。
3）执行等待循环：while (spin_is_locked(slp) && slp->break_lock) cpu_relax();
4）跳转回到“首先”，再次试图获取自旋锁。
奇怪的是，我未能在LXR中找到这段描述对应的源代码，也无从验证我由while (spin_is_locked(slp) && slp->break_lock) 产生的的一个疑问：当锁易手之后，怎么处理break_lock这个字段？
【读/写自旋锁（Read/Write Spin Locks）与顺序锁（Seqlock）】
读/写自旋锁允许并发读，写锁则独占。注意：在已有读者加读锁的情况下，写者不能获得写锁。读/写自旋锁rwlock_t的32位字段lock使用了25位，拆分为两部分，24位被设置则表示未锁，0-23位是读者计数器的补码，有读者时，0-23位不为0，有写者时，0-23位为0（写时无读者）。
顺序锁则允许在读者正在读的时候，写者写入。这样做的优点是：写者无需等待读锁，缺点是有时读者不得不重复读取直到获得有效的副本。顺序锁seqlock_t有两个字段：一个是spinlock_t，写者需要获取，一个是顺序计数器，写者写时其值为奇数，写完时为偶数。读者每次读，前后都会检查顺序计数器。
顺序锁的适用场合：读者的临界区代码没有副作用，写者不常写，而且，被保护的数据结构不包括写者会改而读者会解引用（dereference, *）的指针。
【 RCU(Read-Copy Update)】
锁还是少用的好：使用被所有CPU共享的锁，由于高速缓存行侦听（原书译为窃用）和失效而有很高的开销（a high overhead due to cache line-snooping and invalidation）。
RCU允许多个读者和写者并发运行，它不使用锁，但它仅能保护被动态分配并通过指针引用的数据结构，而且在被RCU保护的临界区，任何内核控制路径都不能睡眠。
读者读时执行rcu_read_lock()（仅相当于preempt_disable()），读完执行rcu_read_unlock()（仅相当于 preempt_enable( ) ）。这很轻松，但是，内核要求每个读者在执行进程切换、返回用户态执行或执行idle循环之前，必须结束读并执行 rcu_read_unlock()，原因在写者这边：
写者要更新一个数据结构的时候，会读取并制作一份拷贝，更新拷贝里的值然后修改指向旧数据的指针指向拷贝，这里会使用一个内存屏障来保证只有修改完成，指针才进行更新。但难点是，指针更新完之后不能马上释放旧数据，因为读者可能还在读，所以，写者调用call_rcu()。
call_rcu()接受rcu_head描述符（通常嵌入在要释放的数据结构中——它自己知道自己是注定要受RCU保护的）的指针和回调函数（通常用来“析构”...）作为参数，把它们放在一个rcu_head描述符里，然后插入到一个每CPU的链表中。
每一个时钟中断，内核都会检查是否已经经过了静止状态（gone through quiescent state，即已发生进程切换、返回用户态执行或执行idle循环） ——如果已经经过了静止状态，加上每个读者都遵循了内核的要求，自然所有的读者也都读完了旧拷贝。如果所有的CPU都经过了静止状态，那么就可以大开杀戒，让本地tasklet去执行链表中的回调函数来释放旧的数据结构。
RCU是2.6的新功能，用在网络层和虚拟文件系统中。
（按：RCU描述起来可累了，尤其是原书和源代码中对静止状态都语焉不详，很难理解其确切含义，暂时只能整理成上面这种理解，以后在研究下usage，弄清实际上应该如何理解。疑问所在：因为静止状态从字面上感觉，应该指旧数据结构仍需“静止地”残余的状态，但是由于内核后来还需要检查是否否度过了静止阶段，那么如何检查这种“仍需”？显然更为容易的是检查进程切换什么的，所以只好把静止状态理解为还未发生进程切换、返回用户态执行或执行idle循环的状态，然后再“ 经过了 ”。怎么想怎么别扭。）
【信号量（Semaphores）】
这个可不是System V的IPC信号量，仅仅是供内核路径使用的信号量。信号量对于内核而言太重了，因为获取不到锁的时候需要进程睡眠！所以中断处理程序不能用，可延迟函数也不能用...
信号量struct semaphore包含3个字段，一个是atomic_t的count，也就是我们在IPC信号量那里已经熟知的表示可用资源的一个计数器；一个是一个互斥的等待队列，因为这里涉及了睡眠，信号量的up()原语在释放资源的同时需要唤醒一个之前心里堵得慌睡着了的进程；最后一个是sleepers，表示是否有进程堵在那里，用于在down()里面进行细节得恐怖而又非常有效的优化（为此，作者感叹：Much of the complexity of the semaphore implementation is precisely due to the effort of avoiding costly instructions in the main branch of the execution flow.）
自然还有读/写信号量，这里不再敷述。
【完成原语（Completion）】
原书将之非常不准确地翻译为补充原语。
Completion是一种类似信号量的原语，其数据结构如下：
struct completion { unsigned int done; wait_queue_head_t wait; };
它拥有类似于up()的函数complete()和类似于down()的wait_for_completion()。
它和信号量的真正区别是如何使用等待队列中包含的自旋锁。在完成原语这边，自旋锁用来确保complete()和wait_for_completion()之间不会相互竞争（并发执行），而在信号量那边，自旋锁用于避免down()与down()的相互竞争。
那么在什么情况下up()和down()可能出现竞争呢？
其实do_fork()的源代码中就包含一个活生生的例子，用于实现vfork()，下面略去了与vfork()无关的代码：
C代码
long do_fork(...)
{
struct task_struct *p;
/* ... */
long pid = alloc_pidmap();
/* ... */
/* p是复制出来的新进程 */
p = copy_process(...);

if (!IS_ERR(p)) {
/* 声明一个叫做vfork的完成原语 */
struct completion vfork;

if (clone_flags & CLONE_VFORK) {
/* 把vfork这个完成原语传递给新进程 */
p->vfork_done = &vfork;

/* 初始化：未完成状态；
这相当于一个一开始就为0的信号量——初始关闭，获取必睡的锁 */
init_completion(&vfork);
}

/* ... */

if (!(clone_flags & CLONE_STOPPED))
/* 此时新进程运行 */
wake_up_new_task(p, clone_flags);
else
p->state = TASK_STOPPED;

/* ... */

if (clone_flags & CLONE_VFORK) {
/* 等待：新进程执行完会调用complete()标志done——相当于up()。
这里相当于一个down()，所以老进程睡了 */
wait_for_completion(&vfork);
/* 接下来的代码继续执行的时候，老进程醒了，这并不一定说明新进程结束了。新进程可能仅仅是正在另外一个CPU上执行complete()函数，这时就出现了竞争条件。 */
/* ... */

}/* 完成原语vfork出作用域，消失了。如果使用的是信号量而非完成原语，相当于该信号量被销毁了，而这时新进程可能还在另外一个CPU执行up()/complete() */
} else {
free_pidmap(pid);
pid = PTR_ERR(p);
}
return pid;
}
long do_fork(...)
{
struct task_struct *p;
/* ... */
long pid = alloc_pidmap();
/* ... */
/* p是复制出来的新进程 */
p = copy_process(...);

if (!IS_ERR(p)) {
/* 声明一个叫做vfork的完成原语 */
struct completion vfork;
if (clone_flags & CLONE_VFORK) {
/* 把vfork这个完成原语传递给新进程 */
p->vfork_done = &vfork;

/* 初始化：未完成状态；
这相当于一个一开始就为0的信号量——初始关闭，获取必睡的锁 */
init_completion(&vfork);
}
/* ... */
if (!(clone_flags & CLONE_STOPPED))
/* 此时新进程运行 */
wake_up_new_task(p, clone_flags);
else
p->state = TASK_STOPPED;

/* ... */
if (clone_flags & CLONE_VFORK) {
/* 等待：新进程执行完会调用complete()标志done——相当于up()。
这里相当于一个down()，所以老进程睡了 */
wait_for_completion(&vfork);
/* 接下来的代码继续执行的时候，老进程醒了，这并不一定说明新进程结束了。新进程可能仅仅是正在另外一个CPU上执行complete()函数，这时就出现了竞争条件。 */
/* ... */

}/* 完成原语vfork出作用域，消失了。如果使用的是信号量而非完成原语，相当于该信号量被销毁了，而这时新进程可能还在另外一个CPU执行up()/complete() */
} else {
free_pidmap(pid);
pid = PTR_ERR(p);
}
return pid;
}

【禁止本地中断】
local_irq_disable()宏使用了cli汇编指令，通过清除IF标志，关闭了本地CPU上的中断。离开临界区时，则会恢复IF标志原先的值。
禁止中断，在单CPU情形可以确保一组内核语句被当作一个临界区处理，因为这样不会受到新的中断的打扰。然而多CPU的情形中，禁止的仅是本地CPU的中断，因此，要和自旋锁配合使用，Linux提供了一组宏来把中断激活/禁止与自旋锁结合起来，例如spin_lock_irq()、spin_lock_bh()等。
【禁止可延迟函数】
可延迟函数禁止是中断禁止的一种弱化的形式，它通过前一篇笔记描述过的preempt_count字段来进行，具体的调用函数是local_bh_disable()。这里不再重复。
【系统的并发度】
为了性能，系统的并发度应该尽可能高。它取决于同时运转的I/O设备数（这需要尽可能减短中断禁止的时间），也取决于进行有效工作的CPU数（这需要尽可能避免使用基于自旋锁的同步原语，因为它对硬件高速缓存有不良影响）。
有两种情况，既可以维持较高的并发度，也可以达到同步：
共享的数据结构是一个单独的整数值，这样原子操作就足以保护它，这是在内核中广泛使用的引用计数器；
类似将元素插入链表中这样的操作设计两次指针赋值，虽然不是原子的，但只要两次赋值依序进行，单一的一次操作仍能保证数据的一致性和完整性，因此，需要在两个指针赋值中间加入一个写内存屏障原语。
【大内核锁（Big Kernel Lock,BKL）】
大内核锁从前被广泛使用，现在用于保护旧的代码，从前它的实现是自旋锁，2.6.11之后则变成了一种特殊的信号量kernel_sem。kernel_sem中有一个lock_depth的字段，允许一个进程多次获得BKL。
改变实现的目的是使得在被大内核锁保护的临界区内允许内核抢占或自愿切换。在自愿进程切换的情形（进程在持有BKL的情况下调用schedule()），schedule()会为之释放锁，切换回来的时候又为之获取锁，非常周到的服务。在抢占的情形，preempt_schedule_irq()会通过篡改lock_depth欺骗schedule()这个进程没有持有BKL，因此被抢占的进程得以继续持有这个锁。
原本发表在我的技术博客：
　　
http://utensil.javaeye.com/category/69495

《深入理解LINUX内核》的笔记-第81页 - Process: Process Descriptor

这里关于task_struct，以及里面的链表结构，参见这篇博文会理解得更好（包括博文里面的链接）：
http://blog.csdn.net/hongchangfirst/article/details/7075026
关于里面提到的container_of这个宏，这里解释得会更清楚一些：http://www.cnblogs.com/Anker/p/3472271.html
而关于链表的，这里解释得也不错（但是我感觉图片中的箭头画得不准确）：
http://www.cnblogs.com/riky/archive/2006/12/28/606242.html

《深入理解LINUX内核》的笔记-第89页 - The process list

process 0: swapper, init_task, idle process
process 1: init

《深入理解LINUX内核》的笔记-第345页 - allocating a noncontiguous memory area

vmalloc的工作原理：
1. 查找可用的连续的虚拟地址区间
2. 计算出需要的页面数量n
3. 循环n次，每次调用alloc_page 申请一个页面
4. 修改master kernel page table的相关pte，将步骤1的虚拟地址 与步骤3得到的物理页帧map起来
5. vmalloc过程并不会修改current process的页表，因此后续进程访问vmalloc返回的内存时会产生page fault，page fault handler再讲master kernel page table相关的pte复制到current process的页表中