Linux内核中的内存屏障(1)

larmbr | 2014-02-14 | Tags: Linux内核, 内存管理

概览

SMP这种并行架构相比传统的单处理器带来相当可观的性能提升。一个不可避免的问题是并行架构的处理器间的交互问题。一种可能的解决方案是,每个CPU都有自己唯一可访问内存,处理器间通过消息传递进行通信。这种架构的问题是带给程序员(尤其是系统程序员)巨大的编程负担,因为需要处理数据分隔与传递。相反,被广泛应用的另一种架构是,多处理器间共享一个共享的内存地址空间。这种架构下每个处理器依然可能有自己的本地内存,但不同的是所有的内存对所有的处理器都是可以访问的,只存在访问效率的问题。本文也针对这种架构进行讨论。

共享的内存空间允许每个处理器都进行对任意内存位置的访问(access)操作,这会引起在单处器上没有的问题。考虑这种情况(此图示和例子来源于内核文档Documentation/memory-barriers.txt):

                :                :
    +-------+   :   +--------+   :   +-------+
    |       |   :   |        |   :   |       |
    | CPU 1 |<----->| Memory |<----->| CPU 2 |
    |       |   :   |        |   :   |       |
    +-------+   :   +--------+   :   +-------+
        ^       :       ^        :       ^
        |       :       |        :       |
        |       :       v        :       |
        |       :   +--------+   :       |
        |       :   |        |   :       |
        +---------->| Device |<----------+
                :   |        |   :
                :   +--------+   :

在如图的这种系统模型中,假设存在如下的内存访问操作:

CPU 1           CPU 2
=============== ===============
{ A == 1; B == 2 }
A = 3;          x = A;
B = 4;          y = B;

由于处理器出于效率而引入的乱序执行(out-of-order execution)和缓存的关系, 对于内存来说, 最后x和y的值可以有如下组合:

     x == 1, y == 2 
     x == 1, y == 4 
     x == 3, y == 2 
     x == 3, y == 4 

因此,对于在操作系统这一层次编程的程序员来说,他们需要一个内存模型,以协调处理器间正确地使用共享内存,这个模型叫做内存一致性模型(memory consistency model)或简称内存模型(memory model)

另外有一点需要明确的是,计算机是一个层层抽象的机器,最底层是裸机,再往上是能理解汇编程序的虚拟机,再往上是能理解更高层级编程语言(如C/C++,Java)的更高层级虚拟机。在高级层级编程语言这一层次,编程语言以及运行环境定义了这个层次的内存模型, 如C++, Java规范中分别定义了各自的内存模型。不过,本文主要着眼的是处理器架构层次定义的内存模型

一种直观的内存模型叫做顺序一致性模型(sequential consistency model), 简单讲,顺序一致性模型保证两件事:

每个处理器(或线程)的执行顺序是按照最后汇编的二进制程序中指令的顺序来执行的,
对于每个处理器(或线程),所有其他处理器(或线程)看到的执行顺序跟它的实际执行顺序一样。

由上两点就可以推出: 整个程序依照着一种有序的执行顺序执行。这种模型是非常直观的,运行在此架构下的程序的执行顺序跟一个不明白内存模型是何物的程序员他所期待的执行顺序一样。

不过,这种模型的效率低下,因为它阻止了处理器发挥乱序执行的能力以最大化并行度,因此在商用的处理器架构中,没有人使用这种模型。取而代之的是更弱的内存一致性模型

比如,耳熟能详的x86及其后续的兼容于它的x86_64架构,采用的是一种叫流程一致性(process consistency)的模型,简言之:

对于某个处理器的`写操作`,它可以按照其意愿重排执行顺序,但对于所有其它处理器,他们看到的顺序,就是它实际执行的顺序。也许这点很难理解,但很重要,后文详述。

还有更松散的弱内存模型, 给予处理器非常自由的重排指令的能力。因此,需要程序员(尤指系统程序员)采取必要的措施进行限制,以保证想要的结果。这就是本文的主题。实际上,这种处理器典型的就是DEC ALPHA, 因此,Linux的通用内存模型是基于它之上构建的。后文详述。

在继续之前,有三个概念要澄清。

`程序顺序(program order)`: 指给定的处理器上,程序最终编译后的二进制程序中的内存访问指令的顺序,因为编译器的优化可能会重排源程序中的指令顺序。
`执行顺序(execution order)`: 指给定的处理器上,内存访问指令的实际执行顺序。这可能由于处理器的乱序执行而与程序顺序不同。
`观察顺序(perceived order)`: 指给定的处理器上,其观察到的所有其他处理器的内存访问指令的实际执行顺序。这可能由于处理器的缓存及处理器间内存同步的优化而与执行顺序不同。

前面的几种内存模型的描述中,其实就用到了这几种顺序的等价描述。

何谓内存屏障

上文已经粗略描述了多处理架构下,为了提高并行度,充分挖掘处理器效率的做法会导致的一些与程序员期待的不同的执行结果的情况。本节更详细地描述这种情况, 即为何顺序一致性的模型难以保持的原因。

总的来说,在系统程序员关注的操作系统层面,会重排程序指令执行顺序的两个主要的来源是处理器优化编译器优化

处理器优化

共享内存的多处理架构的典型结构图如下:

图片

如图,共享内存的涵义其实是每个处理器拥有自己本地内存, 但所有的非本地内存亦可访问,但显然存在速度的差别。此外,每个处理器还拥有自己的本地缓存系统; 所有的处理器通过一个网络来通信。

显然,这种架构下的内存操作会有巨大的延时问题。为了缓解这些问题,处理器会采取一些优化措施, 而导致程序顺序被破坏。

  • 情景一: 设想某处理器发出一条某内存位置读的指令,恰好这个内存位置在远端内存,而且处理器本地缓存也没有命中。于是,为了等待这个值,处理器需要空转(stall)。这显然是效率的极大浪费,事实现代的处理器都有乱序执行引擎, 指令并不是直接被执行,而是放到等待队列里,等待操作数到位后才执行,而这期间处理器优先处理其他指令。也就是出于效率考虑,处理器会重排指令, 这就违背了程序顺序

  • 情景二: 设想有一个热点全局变量,那么在程序运行一段时间后,很可能很多个处理器的本地缓存都有该变量的一份拷贝。再设想现在有处理器A修改这个全局变量,这个修改会发布一条消息能过网络通知所有其他处理器更新该变量缓存。由于路径的问题,消息不会同时到达所有处理器,那么存在一种可能性,某处理器此时仍观察到旧的值,而采取一些基于该旧值的动作。也就是,执行顺序观察顺序不同,这可能导致出人意表的程序行为。

编译器优化

编译器的优化操作,如寄存器分配(register allocation), 循环不变里代码移动(loop-invariant code motion), 共同子表达式(common sub-expression elimination), 等等,都有可能导致内存访问操作被重排,甚至消除。因此,编译器优化也会影响指令重排。

另外,还有一种情况需要单独说明。一些设备会把它们的控制接口映射到程序的进程空间,对这种设备的访问叫做内存映射IO(Memory Mapped IO, MMIO), 对设备的地址寄存器与数据寄存器等寄存器的访问就如同读写内存一样方便。一般的访问模式是先传访问端口到地址寄存器AR, 再从数据寄存器DR中访问数据, 其代码顺序为:

*AR = 1;
x = *DR;

这种顺序可能会被编译器颠倒,结果自然是错误的程序行为。

综上,内存屏障就是在处理器/设备交互过程中,显式加入的一些干预措施,以防止处理器优化或编译优化,以保持想要的内存指令访问顺序

内存屏障的种类

Linux内核实现的屏障种类有以下几种:

写屏障(write barriers)

  • 定义: 在写屏障之前的所有写操作指令都会在写屏障之后的所有写操作指令更早发生。

  • 注意1: 这种顺序性是相对这些动作的承接者,即内存来说。也就是说,在一个处理器上加入写屏障不能保证别的处理器上看到的就是这种顺序,也就是观察顺序执行顺序无关。

  • 注意2: 写屏障不保证屏障之前的所有写操作在屏障指令结束前结束。也就是说,写屏障序列化了写操作的发生顺序,却没保证操作结果发生的序列化。

读屏障(write barriers)

  • 定义: 在读屏障之前的所有读操作指令都会在读屏障之后的所有读操作指令更早发生。另外,它还包含后文描述的数据依赖屏障的功能

  • 注意1: 这种顺序性是相对这些动作的承接者,即内存来说。也就是说,在一个处理器上加入读屏障不能保证别的处理器上实际执行的就是这种顺序,也就是观察顺序执行顺序无关。

  • 注意2: 读屏障不保证屏障之前的所有读操作在屏障指令结束前结束。也就是说,读屏障序列化了读操作的发生顺序,却没保证操作结果发生的序列化。

写屏障/读屏障举例

注意,之所以要把这两种屏障放在一起举例原因就是:写屏障必须与读屏障一起使用

例如:

     CPU 1           CPU 2
     =============== ===============
     a = 1;
     <write barrier>
     b = 2;          x = b;
                     y = a;

假如,CPU 2上观察到x值为2, 能否保证其观察到的y值为1?

不能!这就是前面的注意1强调的内容。原因可能是CPU 2上的缓存中存有a的旧值,而正如何谓内存屏障一节中情景二所说的,由于CPU 1上写操作消息传递的延迟,可能CPU 2还未接收到a值更改的消息。

正确的做法是,在CPU 2上插入读屏障。配对的读/写屏障才能保证正确的程序行为

    CPU 1           CPU 2
    =============== ===============
    a = 1;
    <write barrier>
    b = 2;          x = b;
                    <read barrier>
                    y = a;

通用屏障(general barriers)

  • 定义: 在通用屏障之前的所有写和读操作指令都会在通用屏障之后的所有写和读操作指令更早发生。

  • 注意1: 这种顺序性是相对这些动作的承接者,即内存来说。也就是说,在一个处理器上加入通用屏障不能保证别的处理器上看到的就是这种顺序,也就是观察顺序执行顺序无关。

  • 注意2: 通用屏障不保证屏障之前的所有写和读操作在屏障指令结束前结束。也就是说,通用屏障序列化了写和读操作的发生顺序,却没保证操作结果发生的序列化。

  • 注意3: 通用屏障是最严格的屏障,这也意味着它的低效率。它可以替换在写屏障或读屏障出现的地方

数据依赖屏障(data dependency barriers)

前文说过,DEC ALPHA在Linux所支持的处理器架构中拥有最松散的内存模型,所以DEC ALPHA架构的内存模型定义了Linux的通用内存模型。因此,在内核中,多引入了一种内存屏障,叫做数据依赖屏障,因为在DEC ALPHA上会出现以下这种问题。看例子:

     CPU 1           CPU 2
     =============== ===============
     { A == 1, B == 2, C = 3, P == &A, Q == &C }
     B = 4;
     <write barrier>
     P = &B
                     Q = P;
                     D = *Q;

在CPU 2上,这里有个明显的数据依赖, D要加载Q所指内存位置的值,而Q的地址又要从P中先加载。在除了DEC ALPHA的Linux支持的所有架构中,都严格保证了这种依赖性,因此不需要加这两条指令中加什么内存屏障。但是,DEC ALPHA的弱内存模型连这都无法保证!于是,Linux内核新增了这种叫数据依赖屏障的内存屏障。

     CPU 1           CPU 2
     =============== ===============
     { A == 1, B == 2, C = 3, P == &A, Q == &C }
     B = 4;
     <write barrier>
     P = &B
                     Q = P;
                     <data dependency barrier>
                     D = *Q;

加上这个屏障后,就能保证所有的架构都能处理这种问题。详细见下一篇文章讨论。

下一篇文章将讨论Linux中的内存屏障接口和一些实现上相关问题。

Linux内核4级页表的演进

larmbr | 2014-01-19 | Tags: Linux内核, 内存管理

Linux内存管理中core VM代码中,关于页表(page tables)管理的代码是个重点,是虚拟内存(Virtual Memory, VM)的基石,本文探讨Linux的页表实现及发展过程。

页表概览

在虚拟内存中,页表是个映射表的概念, 即从进程能理解的线性地址(linear address)映射到存储器上的物理地址(phisical address)。很显然,这个页表是需要常驻内存的东西, 以应对频繁的查询映射需要(实际上,现代支持VM的处理器都有一个叫TLB的硬件级页表缓存部件,本文不讨论)。

设想一个典型的32位的X86系统,它的虚拟内存用户空间(user space)大小为3G, 并且典型的一个页表项(page table entry, pte)大小为4 bytes,每一个页(page)大小为4k bytes。那么这3G空间一共有(3G/4k=)786432个页面,每个页面需要一个pte来保存映射信息,这样一共需要786432个pte!

如何存储这些信息呢?一个直观的做法是用数组来存储,这样每个页能存储(4k/4=)1K个,这样一共需要(786432/1k=)768个连续的物理页面(phsical page)。而且,这只是一个进程,如果要存放所有N个进程,这个数目还要乘上N! 这是个巨大的数目,哪怕内存能提供这样数量的空间,要找到连续768个连续的物理页面在系统运行一段时间后碎片化的情况下,也是不现实的。

Linux的页表实现

上面这种理论上的讨论显然不是实际情况。由于程序存在局部化特征, 这意味着在特定的时间内只有部分内存会被频繁访问,具体点,进程空间中的text段(即程序代码), 共享库都是固定在进程空间的某个特定部分,这样导致进程空间其实是非常稀疏的, 于是,从硬件层面开始,页表的实现就是采用分级页表的方式,Linux内核当然也这么做。所谓分级简单说就是,把整个进程空间分成区块,区块下面可以再细分,这样在内存中只要常驻某个区块的页表即可,这样可以大量节省内存

Linux最初的二级页表

Linux最初是在一台i386机器上开发的,这种机器是典型的32位X86架构,支持两级页表。如下图:

图片

一个32位虚拟地址如上图划分。当在进行地址转换时,

  • 结合在CR3寄存器中存放的页目录(page directory, PGD)的这一页的物理地址,再加上从虚拟地址中抽出高10位叫做页目录表项(内核也称这为pgd)的部分作为偏移, 即定位到可以描述该地址的pgd;

  • 从该pgd中可以获取可以描述该地址的页表的物理地址,再加上从虚拟地址中抽取中间10位作为偏移, 即定位到可以描述该地址的pte;

  • 在这个pte中即可获取该地址对应的页的物理地址, 加上从虚拟地址中抽取的最后12位,即形成该页的页内偏移, 即可最终完成从虚拟地址物理地址的转换。

从上述过程中,可以看出,对虚拟地址的分级解析过程,实际上就是不断深入页表层次,逐渐定位到最终地址的过程,所以这一过程被叫做page talbe walk

至于这种做法为什么能节省内存,举个更简单的例子更容易明白。比如要记录16个球场的使用情况,每张纸能记录4个场地的情况。采用4+4+4+4,共4张纸即可记录,但问题是球场使用得很少,有时候一整张纸记录的4个球场都没人使用。于是,采用4 x 4方案,即把16个球场分为4组,同样每张纸刚好能记录4组情况。这样,使用一张纸A来记录4个分组球场情况,当某个球场在使用时,只要额外使用多一张纸B来记录该球场,同时,在A上记录"某球场由纸B在记录"即可。这样在大部分球场使用很少的情况下,只要很少的纸即困记录,当有球场被使用,有需要再用额外的纸来记录,当不用就擦除。这里一个很重要的前提就是:局部性

Linux的三级页表

当X86引入物理地址扩展(Pisycal Addrress Extension, PAE)后,可以支持大于4G的物理内存(36位),但虚拟地址依然是32位,原先的页表项不适用,它实际多4 bytes被扩充到8 bytes,这意味着,每一页现在能存放的pte数目从1024变成512了(4k/8)。相应地,页表层级发生了变化,Linus新增加了一个层级,叫做页中间目录(page middle directory, PMD), 变成:

   31     29              20             11           0
   +-----+---------------+--------------+--------------+
   | PGD |      PMD      |      PTE     | page offset  |
   +-----+---------------+--------------+--------------+

实际的page table walk依然类似,只不过多了一级。

现在就同时存在2级页表和3级页表,在代码管理上肯定不方便。巧妙的是,Linux采取了一种抽象方法:所有架构全部使用3级页表: 即PGD -> PMD -> PTE。那只使用2级页表(如非PAE的X86)怎么办?

办法是针对使用2级页表的架构,把PMD抽象掉,即虚设一个PMD表项。这样在page table walk过程中,PGD本直接指向PTE的,现在不了,指向一个虚拟的PMD,然后再由PMD指向PTE。这种抽象保持了代码结构的统一。

Linux的四级页表

硬件在发展,3级页表很快又捉襟见肘了,原因是64位CPU出现了, 比如X86_64, 它的硬件是实实在在支持4级页表的。它支持48位的虚拟地址空间[1](不过Linux内核最开始只使用47位)。如下:

   47      38           29           20           11           0
   +------+------------+------------+------------+--------------+
   | PML4 |     PGD    |     PMD    |    PTE     | page offset  |
   +------+------------+------------+------------+--------------+

Linux内核针为使用原来的3级列表(PGD->PMD->PTE),做了折衷。即采用一个唯一的,共享的顶级层次,叫PML4[2]。这个PML4没有编码在地址中,这样就能套用原来的3级列表方案了。不过代价就是,由于只有唯一的PML4, 寻址空间被局限在(239=)512G, 而本来PML4段有9位, 可以支持512个PML4表项的。现在为了使用3级列表方案,只能限制使用一个, 512G的空间很快就又不够用了,解决方案呼之欲出。

在2004年10月,当时的X86_64架构代码的维护者Andi Kleen提交了一个叫做4level page tables for Linux的PATCH系列,为Linux内核带来了4级页表的支持。在他的解决方案中,不出意料地,按照X86_64规范,新增了一个PML4的层级, 在这种解决方案中,X86_64拥一个有512条目的PML4, 512条目的PGD, 512条目的PMD, 512条目的PTE。对于仍使用3级目录的架构来说,它们依然拥有一个虚拟的PML4,相关的代码会在编译时被优化掉。 这样,就把Linux内核的3级列表扩充为4级列表。这系列PATCH工作得不错,不久被纳入Andrew Morton的-mm树接受测试。

不出意外的话,它将在v2.6.11版本中释出。但是,另一个知名开发者Nick Piggin提出了一些看法,他认为Andi的Patch很不错,不过他认为最好还是把PGD作为第一级目录,把新增加的层次放在中间,并给出了他自己的Patch:alternate 4-level page tables patches。Andi更想保持自己的PATCH, 他认为Nick不过是玩了改名的游戏,而且他的PATCH经过测试很稳定,快被合并到主线了,不宜再折腾。

不过Linus却表达了对Nick Piggin的支持,理由是Nick的做法conceptually least intrusive。毕竟作为Linux的扛把子,稳定对于Linus来说意义重大。

最终,不意外地,最后Nick Piggin的PATCH在v2.6.11版本中被合并入主线。在这种方案中,4级页表分别是:PGD -> PUD -> PMD -> PTE

参考:

  • http://lwn.net/Articles/106177/
  • 代码:
    • include/asm-generic/pgtable-nopud.h
    • include/asm-generic/pgtable-nopmd.h
    • arch/x86/include/asm/pgtable-2level*.h
    • arch/x86/include/asm/pgtable-3level*.h
    • arch/x86/include/asm/pgtable_64*.h

    * * * * * * 全文完 * * * * * *

[1]: 一开始就实现全64位的虚拟空间,一是实际用不到这么大的空间,二是技术实现上也有困难,所以首先推出X86_64架构CPU的AMD只只支持48位(256TB),但虚拟地址仍使用64位,只不过对高16位作位扩展,跟第48位值一样。这样方便以后扩展,另外一个副作用是:自然地分出用户与内核态两个空间。不多详述。

[2]: Page Map Layer 4, 这是首先引入X86_64 CPU的AMD的叫法。

vma, anon_vma和anon_vma_chain的联系

larmbr | 2013-12-08 | Tags: Linux内核, 内存管理, 内存映射

Linux提供了内存映射这一特性。它实现了把物理内存页映射(map)到进程的地址空间中, 以实现高效的数据操作或传输。内核在处理这一特性时, 使用了struct vm_area_struct, struct anon_vmastruct anon_vma_chain这三个重要数据结构, 所以理解这三个数据结构是重中之重, 本文试图厘清这三者的来历与联系。

vma

struct vm_area_struct在内核代码中常被简称为vma, 所以下文以vma指称这一结构。

vma是内存映射的单位, 它表示进程地址空间中的一个连续的区间, 其中字段vm_startvm_end标明这块连续区间的起始虚拟地址。在使用mmap系统调用创建映射时, 用户指定起始地址(可选)长度, 内核将据此寻找进程地址空间中符合条件的合法vma以供映射。cat /proc/<pid>/maps可以查看某一进程的所有映射区间。这是一个最容易理解的结构。

anon_vma

anon_vma的引入需要一番解释。

反向映射的引入

当Linux系统内存吃紧时, swap子系统会把一些页面释放, 交换到交换设备中, 以空出多余的内存页。虚拟内存的理念就是通过页表来维护虚拟地址到物理地址的映射。但是, 页表是种单向映射, 即通过虚拟地址查找物理地址很容易, 但反之-通过物理地址查找虚拟地址则很麻烦。这种问题在共享内存的情况下更加严重。而swap子系统在释放页面时就遇到这个问题, 对于特定页面(物理地址), 要找到映射到它的页表项(PTE), 并修改PTE, 以使其指向交换设备中的该页的位置。在2.4之前的内核中, 这是件费时的工作, 因为内核需要遍历每一个进程的所有页表, 以找出所有映射该页的页表项。

解决这一问题的做法是引入反向映射(reverse mapping)这一概念。该做法就是为每一个内存页(struct page)维护一个数据结构, 其中包含所有映射到该页的PTE, 这样在寻找一个内存页的反向映射时只要扫描这个结构即可, 大大提高了效率。这正是Rik van Riel的做法, 他在struct page中增加了一个pte_chain的字段, 它是一个指向所有映射到该页的PTE的链表指针。

当然, 它是有代价的。

  • 每个struct page都增加了一个字段, 而系统中每个内存页都对应一个struct page结构, 这意味着相当数量的内存被用来维护这个字段。而struct page是重要的内核数据结构, 存放在有限的低端内存中, 增加一个字段浪费了大量的保贵低端内存, 而且, 当物理内存很大时, 这种情况更突出, 这引起了伸缩性(scalability)问题。

  • 其它一些需要操作大量页面的函数慢下来了。fork()系统调用就是一个。由于Linux采取写时复制(COW, Copy On Write)的语义, 意味着新进程共享父进程的页表, 这样, 进程地址空间内的所有页都新增了一个PTE指向它, 因此, 需要为每个页新增一个反向映射, 这显著地拖慢了速度。

基于对象的反向映射

这种代价显然是不能容忍的, 于是, Dave McCracken提出了一个叫做基于对象的反向映射(object-based reverse mapping)的解决方案。他的观察是, 前面所述的代价来源于反向映射字段的引入, 而如果存在可以从struct page中获取映射到该页面的所有页表项, 这个字段就不需要了, 自然不需要付出这些代价。他确定找到了一种方法。

Linux的用户态内存页[1]大致分两种使用情况:

  • 其中一大部分叫做文件后备页(file-backed page), 顾名思义, 这种内存页的内容关联着后备存储系统中的文件, 比如程序的代码, 比如普通的文本文件, 这种内存页使用时一般通过上述的mmap系统调用映射到地址空间中, 并且, 在内存紧张时, 可以简单地丢弃, 因为可以从后备文件中轻易的恢复。

  • 一种叫匿名页(anonymous page), 这是一种普通的内存页, 比如栈或堆内存就属于这种, 这种内存页没有后备文件, 这也是其称为匿名的缘故。

Dave的方案中的对象指的就是第一种内存页的后备文件。他通过后备文件对象, 以迂回的方式算出PTE, 如图:

            struct page               struct address_space
      +------------------------+    +--------------------+
      |            .           |    |         .          | 
      |            .           |    |         .          | 
      |            .           |    |         .          |
      | address_space *mapping----->|  rb_root * i_mmap ----~+
      |            .           |    |         .          |   |
      |            .           |    |         .          |   |
      |            .           |    |         .          |   |
      +------------------------+    +--------------------+   |
                                                             |
                                                             |
                                                             |
                         struct vm_area_struct               |
                            +-------------+                  |
                            |      .      |                  |
                            |      .      |                  ↡
                page->index |  vm_start   |          +++++++++++++++++
      虚拟地址 <-----------  |   vm_end    | <------- |container_of运算|
         |                  |  vm_pgoff   |          +++++++++++++++++
         |                  |     .       |
         ↡                  |     .       | 
        PTE                 +-------------+

匿名页的反向映射

Dave的方案只解决了第一种内存页的反向映射, 于是, Andrea Arcangeli顺着Dave的思路, 给出了匿名页的反向映射解决方案。

如前所述, 匿名页没有所谓的后备文件, 所以, 上面的路肯定行不通。但是, 匿名页有个特点, 就是它们都是私有的, 而非共享的(比如栈, 椎内存都是独立每个进程的, 非共享的)。这意味着, 每一个匿名内存页, 只有一个PTE关联着它, 也就是只有一个vma关联着它。Andrea的方案是复用struct pagemapping字段, 因为对于匿名页, mappingnull, 不指向后备空间。复用方法是利用C语言的union, 在匿名页的情况下, mapping字段不是指向struct address_space的指针, 而是指向关联该内存页的唯一的vma。由此, 也可以方便地计算出PTE来。

但是, 事情并不是如此简单。当进程被fork复制时, 前面已经说过, 由于COW的语义, 新进程只是复制父进程的页表, 这意味着现在一个匿名页有两个页表指向它了, 这样, 上面的简单复用mapping字段的做法不适用了, 因为一个指针, 如何表示两个vma呢。

Andrea的做法就是加多一层。新创建一个struct anon_vma结构, 现在mapping字段是指向它了, 而anon_vma中, 不出意料的, 包含一个链表, 链接起所有的vma。每当进程fork一个子进程, 子进程由于COW机制会复制父进程的vma, 这个新vma就链接到父进程中的anon_vma中。这样, 每次unmap一个内存页时, 通过mapping字段指向的anon_vma, 就可以找到可能关联该页的vma链表, 遍历该链表, 就可以找到所有映射到该匿名页的PTE。

这也有代价, 那就是

  • 每个struct vm_area_struct结构多了一个list_head结构字段用以串起所有的vma
  • 需要额外为anon_vma结构分配内存。

但是, 这种方案所需要的内存远小于前面所提的在每个struct page中增加一个反向映射字段来得少, 因此是可以接受的。

以上, 便介绍完了anon_vma结构的来由和作用。

anon_vma_chain

anon_vma结构的提出, 完善了反向映射机制, 一路看来, 无论是效率还是内存使用, 都有了提升, 应该说是很完美的一套解决方案。但现实不断提出难题。一开始提到的Rik van Riel就举了一种工作负载(workload)的例子来反驳说该方案有缺陷。

前面的匿名页反向映射机制在解除一页映射时, 通过访问anon_vma访问vma链表, 遍历整个vma链表, 以查找可能映射到该页的PTE。但是, 这种方法忽略了一点: 当fork进程时复制而产生的子进程中的vma如果发生了写访问, 将会分配新的匿名页, 把该vma指向这个新的匿名页, 这个vma就跟原来的那个匿名页没有关系了, 但原来的vma链表却没反映出这种变化, 从而导致了不必要的对该vma的检查。 Rik举的例子正是对这种极端情况的描述。

Rik采取的方案是又增加一层, 新增了一个结构叫anon_vma_chain:

struct anon_vma_chain {
    struct vm_area_struct *vma;
    struct anon_vma *anon_vma;
    struct list_head same_vma;
    struct list_head same_anon_vma;
};

vma中新增了一个字段anon_vma_chain, 是一个list_head结构, 它链接起所有关联到此vmaanon_vma。具体地, 当一个进程fork后, 子进程中拥有自己的vmaanon_vma, 不过, 由于COW机制, 此刻它们和父进程中的对应物是一样的。子进程中的vma跟之前一样, 也要链接到父进程的anon_vma中, 不过方法有了变化, 不再是直接链接, 而是通过anon_vma_chain这个结构。通过same_vma, 串联起共享这同vma的父进程的anon_vma和子进程的anon_vma; 同理, 通过same_anon_vma, 串联起共享同一anon_vma的父进程的vma和子进程的vma。如图:

                              父进程vma            
                      +---------------------------+
                      |                           |
                      |___________________________|
                      | list_head anon_vma_chain <---------------------------------+
   父进程anon_vma      |___________________________|                                |
     +--------+       |                           |                                |
   +-> head   |<---------- anon_vma *anon_vma <----                                |
   | +--------+       |___________________________|                                |
   |                                                                               |
   |                                                                               |
   |                          子进程vma                     子进程anon_vma_chain   |
   |                   +---------------------------+      +---------------------+  |
   |                   |                           |<------------ vma           |  |
   |                   |___________________________|      |_____________________|  |
   |                   |                           |      |                     |  |
   |                   | list_head anon_vma_chain <-------------> same_vma <-------+
   |  子进程anon_vma    |__________________________ |      |_____________________|     
   |  +--------+       |                           |      |                     |
   +-->  head  | <-------  anon_vma *anon_vma <--------------- anon_vma         |
      +-^------+       |___________________________|      |_____________________|
        |                                                 |                     |
        +-------------------------------------------------->  same_anon_vma     |
                                                          |_____________________|

当子进程写内存页时,发生COW, 子进程vma将指向自己的内存页(same_anon_vma链接将解除), 同时, 子进程的anon_vma将指向自己的vma(于是, same_vma也解除)。这样, 在解除一页映射时, 对于子进程自己的匿名页, 只要遍历子进程自己的anon_vma下的vma链表即可; 对于共享的页(未发生COW), 则按原来的方法遍历, 这样就大大减少了对拥有大量子进程的进程, 要遍历每个子进程的所有vma的情况。

再看anon_vma_chain这个名字, 它就像个粘合剂, 也像个链条, 把初始时父,子进程共享的vmaanon_vma串联起来, 当子进程通过COW拥有自己的匿名页后, 会发生解链, 以分冶策略各自管理, 从而使得在解除一页映射时, 减少了不必要的遍历次数, 也减少了相应的锁冲突, 从而提高了效率。

参考: o http://lwn.net/Articles/383162

* * * * * * 全文完 * * * * * *

[1]: 内核态的页Linux采用的是直接映射, 这样加快了速度。

Linux v3.8 CLONE_NEWUSER|CLONE_FS 提权漏洞EXP分析

larmbr | 2013-11-23 | Tags: Linux内核, 漏洞

提要:

2013年3月13日,SUSE的安全研究员Sebastian Krahmer发出一封名为:

CLONE_NEWUSER|CLONE_FS root exploit

的邮件,暴出3.8版本的Linux内核存在一个提权漏洞,并给出了PoC.

该exploit利用了3.8内核允许普通用户利用clone(... CLONE_NEWUSER | CLONE_FS, ...)创建新进程的漏洞,巧妙实现提权。该漏洞利用的精妙之处在于:只是利用两个概 念上的缺陷,不需要费尽心力写复杂的shellcode, 仅若干个普通API就实现了提权。而 且, 这个exploit完美地演绎了一个程序如何在不同的euid下3次运行,每次进行不同 的动作。三次运行环环相扣,一步步帮助获得系统的权限。

另一方面, 给力的是,当天内核开发者就及时给出了Fix.

漏洞分析:

1. CLONE_NEWUSER与CLONE_FS狼狈为奸。

随着Linux 3.8版本释出,标志历经多年开发(从2007年的2.6.23版本开始)的用户名字 空间(user namespace)的开发工作基本完成。这是第6个完成的内核名字空间。 它们是实现内核容器(container)中的一部分。内核容器是用于分隔资源,系统监管以及 虚拟化的一个轻量级工具,简单来说,就是把系统资源进行分隔,这样不同容器中的资源 互不感知对方,实现有效分隔。而用户名字空间的完成,有着重大意义,因为每个普通用 户都可以建立自己的名字空间。每一个用户名字空间中,有一套独立的uid系统,这意味 着每个空间中有各自的root用户!也就意味着,在这个名字空间中,进程可以拥有任意权 限(capabilities),包括调用chroot切换根目录。而本来分隔的名字空间类似sandbox,不 会带来太多安全问题。但是,3.8内核允许普通用户创建名字空间!

对于CLONE_NEWUSER来说,它意味着创建的新进程需要独立的用户名字空间。 至于CLONE_FS标志,它表示创建的子进程要跟父进程共享文件系统属性,比如有相同的根目录...

独立与共享?!这隐隐约约就带来了坏味道!于是,隐患已经埋下,潘多拉的盒子即将被打开......

2. chroot, 罪恶之

前面讲了,两个奇怪的标志一结合,立马带来了隐患。一个是独立的名字空间,一个是 共享的文件系统空间,如何让封印于盒子里的怪兽逃出生天呢。工具之一就是chroot!

chroot是在Linux系统中发挥根目录的切换作用的命令,它也带来系统的安全性等好处 。比如有玩过lfs或gentoo的同学都知道,当在host环境下搞定新环境的工具链后,一 条chroot命令就可以切换到新的环境,然后筚路蓝缕,开始打拼另一片天空。   如下:

 /( / : 原来的根目录)
        |
  -----------------------
|     |      |        |
bin  lib  home/lcx ......
              |
          newroot(/home/lcx/newroot : 新的环境的根目录)
              |
         -----------
         |    |  |
      bin   lib  usr .....

当执行: chroot /home/lcx/newroot

就将原来的/home/lcx/newroot变为新环境的根目录。此时,原来的文件系统被掩盖。 压迫不再,曾经的旧民翻身,新的政治秩序铺开。

那此时如果还用原来的名号,会发生什么情况呢?很简单,发生了"坐标系平移"。比如 旧环境的/bin/su,将被映射成新环境的/home/lcx/newroot/bin/su; 旧环境的/lib/ld-linux.so.2,将被映射成/home/lcx/newroot/lib/ld-linux.so.2.

好,咱花开两朵,先表一枝。这一厢先按下,稍后再叙。

3. 动态链接器ld-linux.so, 引狼入室

动态库顾名思义就是程序运行才加载依赖的库。在linux上,这是由一个叫ld-linux.s= 的家伙来执行加载动态库这项工作的。粗略地讲,ld-linux.so把程序加载与开始执行之 间活动,搜索程序用到的库,并映射到程序的进程空间,以及完成一些符号解析等dirty job, 然后,才把程序流控制权交到程序入口点开始执行。

此外,关于ld-linux.so还有一点需要强调, 它拥有与所执行程序相同的权限。意思就是 ,当程序以有效用户ID(euid)为root的ID运行时,那ld-linux也以root权限运行.

那ld-linux.so在哪? 它不应该包含在程序的可执行文件中。因为,如果系统有上千个 要用到动态库的程序, 哪岂不是有上千份拷贝.

其实, ld-linux.so是在系统中。在程序运行时,它首先被加载,然后由它加载动态库。   $ ls /lib | grep ld-linux (或ls /lib64 | grep ld-linux)

可以看到,存在/lib/ld-linux.so.2(我系统32位的,纯64位系统会发现它在/lib64中)。 由它的路径与名称看来,它本身就是一个库(用file命令查它户口,发现它是shared object, ELF格式中的一种:共享对象,其它库文件同样也是一这种格式)。

这里面隐含着,系统能加载ld-linux.so, 说明系统知道这个ld-linux.so的路径,它藏在哪呢,就在程序执行映象里:

$ readelf -l  /bin/ls

以上命令读取ls程序的可执行映象,能发现输出结果中出现有Requesting program interpreter:/lib/ld-linux.so.2的字样。

这里面,它作了一个假设: 我要找的动态链接器ld-linux.so它位于根目录下的lib目 录中。它硬编码了路径! 万一运行过程中这个根目录变了呢,这路径不就指到别的地方 去了?! 存在这种可能吗? 可能! 这就是这个exploit的妙处所在。

4. 打开魔盒

上面说的这个exploit妙在,它巧妙地在程序运行过程中,改变了根路径!

改变了根路径后,它执行了一个setuid程序su(运行ls -l /bin/su, 你会看到它的权限 是这样的:-rwsr-xr-x, 其中发现有一位变成了s。这个程序就叫setuid程序。至于这个 s的含义,涉及到真实用户ID与有效用户ID的关系,网上有详细解说,读者可以在网上找 到相关方面文章), 而这个su在运行前是先要运行ld-linux.so来加载动态库。

前面说了, ld-linux.so路径是硬编码成/lib/ld-linux.so.2的。但是, 现在根路径已 经变了! 所以, 此时的/lib/ld-linux.so.2已经不是指向真正的ld-linux.so了。它现 在指向了改变后的根目录下的lib/ld-linux.so.2。而这个位置, 放的就是exploit程序 自身! 这当然不是凑巧的,而是在改变根路径过程中使用了技巧而实现。

所以, 现在相当于又运行了exploit一次。不过, 这次的有效用户ID(EUID)是0。因为 前面说它执行了一个setuid的程序su。而在第3节说过, 执行ld-linux.so时, 它拥有跟 su一样的权限: 即EUID为0用户,也就是root的权限。这就是为什么要选用一个setuid权 限的程序的原因。

然后, 重新运行的exploit进程做了啥呢? 它把自己的uid设为0, 即让自己成为root用 户, 然后, 再运行一次bash。此时, 这个shell就是一个root权限的shell了。僭权成功 !!!

这就是这个exploit大概的思路, 至于是如何改变根路径的, 是重头戏, 有兴趣的读者 可以继续往下看。下面是对这个exploit更详细的讲解.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 分隔线 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

它是这么做的:

我们先设定这个exploit程序叫evil, 它的路径不妨设为/home/lcx/evil。然后我们进 入到/home/lcx目录,执行   $ ./evil

我们以普通用户运行这个程序。一切都还显得是风平浪静。我们称此时的进程为A。 A莫名其妙地做了这几个动作.

* 读取/proc/self/exe获取自己的路径,也就是/home/lcx/evil(这不是多此一举,因为
   程序自身并不知首自己的路径,而即使我们把程序放别的地方,它还是能准确找
   己的巢)。
* fork了一个进程B, 然后它就去睡觉, 间隔1秒醒来看evil这个程序文件的用户
  ID是否变成root了。当然, 现在还不是,所以它去睡觉~~~

创建出来的B干嘛呢?

*  在当前目录(/home/lcx)创建了一个chroot, 也就是/home/lcx/chroot。
*  在chroot下再建了两个目录,是为/home/lcx/chroot/bin和/home/lcx/chroot/lib。
*  在/hom/lcx/chroot/bin目录下, 它生成一个链接/home/lcx/chroot/bin/su,指向原来/bin/su。
*  在/hom/lcx/chroot/lib目录下, 它生成一个链接/hom/lcx/chroot/lib/ld-linux.so.2,
   但是, 它指向evil自己:/home/lcx/evil。
*  调用pipe API生成一个管道准备通信。和谁通信?这个稍后说。

不妨以图示说明:

      /
      |
 -------------------------
 |        |          |
bin       lib       home/lcx -------
 |          |            |          |
su      ld-linux.so   chroot       evil
            ^            |          ^
            |     -----------       |
            |     |         |       |
            |    bin       lib      |
            |     |         |       |
            |____su   ld-linux.so__ |

觉得跟上面介绍chroot一节时画的图有些类似? 没错, chroot要登场了, 前面这些莫名 其妙的动作不过是为舞台布景!

不过, 我们现在还是普通用户, 是没有root权限执行chroot的(是的,evil程序就是要获 取root权限, 但现在还不是)。但是,没有权限也要创造权限, 方法就是利用clone的 CLONE_NEWUSER, 生成一个新的子进程C。前面说过,它生成的子进程将在一个新的用户 命名空间里, 它可以做任何事, 包括chroot。

但是, 不要忘了, 现在我们是在子进程C的新的名字空间中, 再闹得天翻地覆也没用。 所以, 另一个标志出来救场了, 就是CLONE_FS。利用它我们可以巧妙地把魔鬼释放到盒 子外面! 前面说了这个标志是让子进程与父进程共享文件系统的属性的。那么, 当我们 在子进程里chroot后, 改变了根目录。既然是共享, 父进程的根目录也被改变了!

进程C做了什么好事呢?

* C从管道中读取一个字符。我们前面说过B创建了一个管道。管道是Linux中父子进
  程通信的一种方法。当一端读的时候,如果没数据,会被阻塞。所以,C从管道中读
  取什么信息不重要,关键是,C必须得等到它的父进程B往里面写入数据。

  那B写入数据前做了啥?
  * 它创建了UID映射,简言之。它写了/proc/${Pc}/uid_ma文件, 把B的uid映射到
    到C的uid。这里${Pc}是指C的pid, 它是从clone返回的。
  * 然后往管道中写了个字符。
  * 调用waitpid()等待它的子进程C。

  所以,等c读到这个字符时,实际上uid映射已经完成了。有什么用?接着看。

* C用setuid()把自己uid设为root(记住此时C是在自己的名字空间中,所以是允许它这
  么做的)。由于前面作了uid映射,所以此时B的uid也是root! 

* 当然,C最后调用chroot()切换了根目录!

前面说过, A每睡1秒就醒来看自己的uid是不是变成root了。现在,终于变成root了! 于是,A开心地再一次执行了evil这个程序(这是第2次运行这个程序)。此时,它的有效 用户ID(euid)是0,于是,它把/lib/ld-linux.so.2的权限设为04755。这个值表示,  这个程序现在是一个setuid程序了. 前面说过,C切换了根目录,并且CLONE_FS标志是 表示共享文件系统属性的,所以,这时修改的ld-linux.so.2其实就是evil!(参见上图) 。也就是, evil从一个普通的程序变成一个setuid程序! 然后,这个进程退出。

此时,C完成使命,它也退出。

另一方面,在管道中写入数据后就调用waitpid()等待C的B终于等到C退出, 它运行了一 个setuid程序su(前面通过uid映射,B此时的uid是0了,所以它能运行su)。如前面所说 , 这个su要调用/lib/ld-linux.so.2, 而当前根目录已经变为/home/lcx/chroot, 所以 ,此处调用的是/home/lcx/chroot/lib/ld-linux.so.2。而前面已经将/home/lcx/chroo t/lib/ld-linux.so.2链接到evil自身(见图).   所以,此时运行的还是evil自身.(这是evil这个程序第3次被运行了!)

不同的是此时运行的evil已经是一个setuid程序, 运行它时euid就是0! 还有,要注意, 现在是第三次运行eveil, 它已经是在chroot环境外了(受chroot影响的只有C和B)。

然后, evil把自己的uid设为0, 再运行bash。这是一个有root权限的bash, 并且是在 chroot环境外, 僭权成功!

Linux内核发布模式与开发组织模式(2)

larmbr | 2013-11-05 | Tags: Linux内核, 内核开发

Linux内核发布模式与开发组织模式(1) 一文中讲了Linux内核发布模式的演变历程, 这篇文章讲述Linux内核的开发组织模式, 顺带地, 会描述几个Linux内核开发者必须知道的重要的内核分支。

开发组织模式

Linux作为迄今全球规范最庞大开源合作项目, 在20多年的发展过程中, 逐渐形成一套基于信任链的层级组织模式, 这套模式有个术语叫司令官与副官工作流(dictator and lieutenat workflow)。在这种模式中, 有若干个管理员, 分别负责项目中的特定部分,是为副官(lieutenant); 所有这些管理员头上还有一位负责统筹的总管理员,是为司令官(dictator)。司令官维护的版本库用于提供给所有项目协作者(不仅仅是副官, 还可以包括来自全球的"士兵"), 以供他们拉取集成的项目代码。具体到Linux项目, 这种模式是这样运作的:

Linus作为项目司令官(dictator), 掌控大局, 把握项目发展方向, 并维护着一个权威的中心版本库, 叫做`mainline分支`。若干骨干开发者, 作为副官(lieutenant), 维护着各个子系统分支, 比如核心子系统, 内存管理子系统, 网络子系统, etc。这些子系统分支以`mainline分支`为`上游`(upstream)。 定期或不定期地, Linus会把各子系统分支合并进`mainline分支`。 在子系统分支下, 可能又有细分的分支, 同样遵循着类似的流程。 按照这种方式, Linux社区构建起一套基于`信任链`的层级开发组织模式, 有效地组织起全球数以千计的开发者。

从v2.6时代, 确立并持续到今天的一个新版本的开发流程大概是这样的[1]:

  1. 合并窗口打开

    从v2.6.14起, Linux就引入一个叫合并窗口(merge window)的概念, 这是一个持续两周的时间窗口。伴随着上一个版本的发布, 下一个新版本的开发就宣告开始, Linus会开启这个合并窗口, 在此期间, 各个子系统的维护者向Linus发出请求, 请求合并自己维护的子系统分支中, 精心挑选的新特性或新功能补丁。当然, 这些补丁不是凭空而来, 在这之前, 这些补丁很早就进入该子系统维护者的分支, 经历了若干测试了。两周时间一到, 合并窗口关闭, 基本该新版本所有的新功能确定, Linus释出第一个候选版本, 是为rc1(release candidate)。

    这个rc1也面向所有用户开放下载, Linus等开发者们的希望当然是鼓励更多的用户去帮忙测试。没有来得及在这个合并窗口中进入mainline的, 只有等待下一个版本的合并周期了[2]

  2. 发布若干轮候选版本

    在发布了第一个候选版本rc1后, 距离真正发布这个新版本还有6到10周。原因是: 这些代码虽然在这之前有经过特性分支的测试, 但正如前一篇文章所说, 实际上少有开发者或用户愿意去测试特性分支, 因此, 测试的覆盖度或强度其实不如预期, 所以, 接下来这6至10周, 就是要使这些代码稳定的过程: 修补bug, 修补安全漏洞, 消除regression[3], 等等。Linus大概每周就发布一个rc版本, 比如2.6.X-rc2, 2.6.X-rc3, etc。

    当然, 开发者们也希望能有更多的用户可以在各种各样的平台上测试这些候选版, 但如前一篇文章所言, 事实上也少有用户去测试。对于准备入门内核开发的人来说, 帮忙测试这些候选版, 可以发现很多问题, 并设法解决, 这是一个被鼓励的做法。

    何时认为代码已经稳定了呢? 内核开发者们的目标是, 尽量消除上一个发行版中的已知的regression。不过现实难有这么美好, 有些不是太严重的regression如果仍无法消除, 内核开发者也会暂时放过(毕竟, 不能无限期拖下去, 因为各个子系统的维护者手中的补丁日渐增加, 都等着下一个合并窗口打开呢, 拖太久对这些维护者来说是个很重的负担)。总之, 若干轮rc版本发布后, 新的版本就会发布!

  3. 正式版本发布后的维护

    新版本发布后, Linus会把它转交给一个团队来继续维护, 这个团队就是前一篇文章所说的Greg Kroah-Hartman领导的-stable分支维护团队。Linus本人则致力于下一个新版本的开发, 开启新一个合并窗口...

    这个-stable分支的起缘上一篇文章已经解释过, 它的目标就是: 把修补bug或安全漏洞的补丁, 向后移植到这个刚发布的版本中(当然, 这些修补肯定也会进入mainline中), 然后不定期地发布一个v2.6.X.Y(或v3.X.Y)的版本。随着每个Y版本号递增, 都会有若干个bug或漏洞被修补。

    这个维护过程大概会持续到下一个新版本发布, 然后这个版本就会被标记为EOF(End Of Life), 不再继续有官方的维护; 但对于一些标明LTS(Long Term Support)的版本, 则会持续有长达数年的维护。比如v3.0-stable分支, 在本文写作的今日(2013-08-12), 释出了v3.0.90, 此时, 距离v3.0发布, 已经过了将近两年又一个月了。

重要的内核分支

上面所述就是一个开发流程的大致面貌。如果从补丁的生命流程来看整个开发流程的话, 要牵涉到几个重要的内核分支[4]

各个子系统分支

前文说过, 补丁是经过各层级的分支, 一步步进入mainline的。这里有所有放置在www.kernel.org上的各子模块或子系统的git分支列表

对开发者来说, 提交补丁时, 找到正确的子模块或子系统维护者, 并把补丁提交给到相应的邮件列表, 是非常关键的。 内核代码中有一个脚本: scripts/get_maintainer.pl, 可以帮助决定你手头上的补丁, 应该提交给哪个(些)开发者。

-mm分支

各个子系统维护者的分支代码, 虽然在合并到Linus的mainline前已经经过若干测试, 但毕竟只是在自己的子系统内测试, 还必须要有整合测试, 而这通常是暴露出更多问题的地方, 因此非常重要。这个整合测试的分支, 就是由核心开发者Andrew Keith Paul Morton维护的-mm分支[5]

前一篇文章说过, 这个分支诞生于2.6发布前的特性冻洁期, 所有要最终进入mainline的代码都要经过该分支的测试, 它也是新功能的试验场, 被叫做特性分支。该分支主要包含的有:

各个子系统维护者的代码树
因各种原因没进入相应子系统的零散补丁
一些不会进入`mainline`的仅用于debug目的的工具补丁
一些牵强的还不足以在下个版本中释出的补丁

另外, 值得一提的是, Andrew 的-mm分支不是用git来维护的, 而是用其开发的quilt工具, 这是一个补丁集管理工具。

-mm分支的无所不包, 产生了不少问题, 导致Andrew不堪重负, 以至后来催生了-next分支, 对于子系统测试这一大部分功能被转移到-next分支中, 而Andrew则着重负责前述剩下的三种补丁, 这样他有更多的精力来review和测试代码。

后来, 为了满足一些开发者获取更新鲜热辣的-mm分支, Andrew又创建了一个新的-mmotm分支, 取意-mm tree of the moment现在-mm分支已经慢慢淡化了, -mmotm取代了它。人们谈论-mm, 其实就是谈论-mmotm。这个分支是基于mainline的代码, 差不多一周多就会发布一次, 以补丁集的形式发布, 用户可以用quilt工具把这些补丁应用在该补丁集释出时的mainline最新代码上。更多详情, 看这里

-next分支

-next分支是由Stephen Rothwell维护的。前一节说过, 它是Andrew的-mm分支衍生的产物, 从Stephen发表的一封宣告该分支诞生的邮件中可以看出该分支诞生的初衷。

旧的-mm分支存在几个严重的问题:

太过庞杂, 旨在作为功能测试场的该分支吸收了n多子系统的代码, 也是许多独立补丁的收集站, 合并所有这些代码的繁重工作导致该分支是几周一个发布。
如此长的发布周期, 导致问题积累, 不能快速得到修正。因此, `-mm分支`经常存在严重的regression现象。
前面两点又导致少有开发者愿于基于它来做测试, 因而子系统维护者也就很少测试其它子系统的代码, 这违背了这个分支存在的初衷。

因此, Andrew提出建立-next分支的设想, Stephen Rothwell承担了这一分支的维护工作。事实证明, 这一分支很成功:

基于自动化的构建, 该分支每天都会自动去拉取(截至本文写作)多达222个子系统分支代码, 构建一颗`全新的git tree`。自动完成合并, 并基于几种典型的配置自动编译和运行。如果合并失败, 编译失败, 或运行时失败, 该分支会被剔除出`当天的代码树`, 并通过邮件通知该分支维护者。这样的结果是, 及早地消除问题, 减少在之后的合并窗口中, 被Linus拉取时候, 出现种种冲突或编译失败的可能性。这样相对之前粗糙的`-mm分支`, 稳定了不少, 因而也得到更多的开发者的注意, 从而得到更多的测试。 值得一提的是, 开发者通过拉取该分支代码, 基本就可以窥见下一个版本中即将增加的新功能的全貌,这也是该分支取名`next`的原因。正是这一分支, 及早且频繁地进行各子系统代码的整合与构建, 从而可以确保`合并窗口`期间, 代码进入`mainline`的过程更平和些, 因此, 它是现今Linux开发过程中不可或缺的重要一环。

作为想入门内核开发的人来说, 我个人觉得每天跟踪这个分支, 并编译测试该分支, 是一个相当不错的入手点。所以, 有必要说说该分支具体是如何工作的。

  1. 跟踪该分支

    按照这份FAQ说明的做法, 可以基于Linus的mainline分支, 构建对这-next分支的跟踪。

    git remote add linux-next git://git.kernel.org/pub/scm/linux/kernel/git/next/linux-next.git  # 新增一个源, 叫linux-next
    git fetch linux-next  # 把源linux-next上的所有分支都抓取到本地, 对于每一个分支b的当前指向, 存放在本地的remotes/linux-next/b中
    git fetch --tags linux-next # 确保把所有的tag标记及这些标记指向的对象都抓取下来
    
  2. 该分支的构建流程

    该分支树的最大特点就是: 每天都是一个全新的树, 抛弃之前的历史。因此, 使用git pull来更新是不正确的。当按照前面的做法构建对该分支的跟踪后, 每天获取该树的最新动态的正确做法是:

    git remote update linux-next
    

    从该树源码目录Next/merge.log中可以看出, Stephen是如何构建当天这棵树的。下面是从本文写作当天的最新-next分支: next-20130812抽取出来的操作指令:

    # 解释点1
    $ git checkout master
    $ git reset --hard stable
    
    # 解释点2
    $ git merge --no-ff origin/master
    $ git merge --no-ff fixes/master
       .
       . (省略若干个git merge --no-ff ...)
       .
    
    # 解释点3
    $ git merge akpm-current/current
    $ git commit -v -a
    $ git diff -M --stat --summary HEAD^..
    
    # 解释点4
    $ git am -3 ../patches/0001-memcontrol-further-merge-fix-patch.patch
    $ git reset HEAD^
    $ git add -A .
    $ git commit -v -a --amend
    
    # 解释点5
    $ git clone -s -l -n -q . ../rebase-tmp
    
    # 解释点6
    $ cd ../rebase-tmp
    $ git checkout -b akpm remotes/origin/akpm/master
    $ git rebase --onto master remotes/origin/akpm/master-base
    
    # 解释点7
    $ cd ../next
    $ git fetch -f ../rebase-tmp akpm:akpm/master
    $ git merge --no-ff akpm/master
    
    # 解释点8
    $ rm -rf ../rebase-tmp
    
    1. 开始时, 处于next目录。首先, 先检出到-next treemaster, 然后, 一个git reset --hard stable强制把这个分支的内容, 变为Linus的mainline tree当天的状态(stable追踪的是Linus的mainline tree), 因为, -next分支是要测试下一个合并窗口的新功能代码的, 只有保证每天基于Linus的代码成功地合并, 编译, Linus在合并窗口打开时, 才能平和顺利地合并这些子系统分支 。所以, 这棵树每天都基于当天Linus的mainline tree构建, 可以把它看成是包含将在下一版本加入的新功能的mainline tree

    2. 接下来是若干行的git merge --no-ff操作, 就是合并各个子系统分支的操作了。对照Next/trees文件, 可以看到每一棵被合并的git tree, 都有一条git merge操作。 --no-ff选项作用是: 即使这次合并是fast-forward, 也强制生成一条合并信息[6]

    3. 对于merge冲突的分支, 需要人工介入, Stephen会尝试修补冲突, git commit生成一次提交, 然后git diff打印出本次冲突的内容。然后, Stephen会发一封邮件到linux-next@vger.kernel.org和该分支维护者, 告知此事, 并给出他做的修改(当然, 如果分支维护者认为如此修改不正确, 就回复邮件告知如何修改)。

    4. 对于独立的补丁, 则用git am打上, 然后git reset HEAD^把最新提交回退一次, 再git commit -v -a --amend作一次修补提交。这几条命令的作用是: 这个独立的补丁本应是属于akpm-current/current分支的, 但不知何故遗漏了, 所以, 手工打上, 并整合到该分支上, 做一次独立的提交。

    5. 当所有分支合并完毕, git clone . ../rebase-tmp完成了重新生成当天-next tree的魔术的主要部分: 把当前目录clone到一个新的临时目录rebase-tmp中。注意: 应该把rebase-tmp看成一个源, 只不过这个源在本地。理解这一点, 对理解后面的命令很重要。

    6. 去到rebase-tmp中。注意, 现在来到新的一个, 那么, 对于这个源来说, 它的远程源origin其实就是next目录。

      git checkout -b akpm remotes/origin/akpm/master检出远程源(next目录)的akpm/master分支到一个新的分支akpm中, 此时处于akpm分支中, HEAD指向akpm, 也就是指向akpm/master[7] 。如图:

                                                      HEAD
                                                       |
         remote: akpm/master-base --->  A---B---C <---akpm(remote : akpm/master)
      
                                          D---E---F---G <---master
      

      根据当前HEAD的指向, git rebase一句的完整形式是: git rebase --onto master remotes/origin/akpm/master-base remotes/origin/akpm/master, 意为: 把当前节点HEAD(即akpm/master)与(远程源即next目录)中的akpm/master-base分支这之间的提交, rebase到master分支上来; 同时, 当前分支会被自动切换到master。如图:

         remote: akpm/master-base ---> A---B---C <---akpm(remote : akpm/master)
                                      /
                         D---E---F---G  <---master
                                     |
                                   HEAD
      

      总之, 执行完这两条命令后, 源rebase-tmp中, master分支最新部分是来自next目录中akpm/master-base分支akpm/master分支之间的所有提交。

    7. 回到next源

      git fetch -f把刚刚构建的rebase-tmp目录作为源, 以akpm分支作为远程分支, 强制更新本地的akpm/master分支。然后, 再合并。

      因为rebase-tmp源是从next源 clone过去的, 所以, next源其实也有着与上面类似的结构, 经过合并, 其结构如图:

                        A---B---C <--- akpm/master
                       /        ^
          D---E---F---G         |
                              master
                                ^
                                |
                               HEAD
      

      现在综合起来看第6, 7步, 如此大费周章, 就是为了把akpm分支上的更新, 拣出来, 用rebase操作放置到master分支最前头。

      akpm/master-baseakpm/master之间的提交是来自于Andrew Morton的-mmotm分支的补丁集。而之所以要拣选出来放在最前头的原因是: Andrew Morton的-mmotm分支是用quilt来维护的, quilt是一个补丁集管理工具, 对补丁的先后次序很严格。而且, Andrew Morton会基于-next分支来做测试, 因而, -next分支上应用的-mmotm的补丁要放最前头, 这样才能方便Andrew方便地基于-next上继续打后续的补丁做测试。

    8. rebase-tmp无用了, 可以删除掉。

mainline分支

当新一个版本开发周期开始, Linus开启合并窗口, 之前经过-next分支检验的各个子系统代码, 在子系统维护者发出pull request后, 如果Linus批准, 就会被其拉入mainline。当然, 也有极少数例外的补丁是直接提交到mainline中的。不出意外, 它们都将成为下一个版本中释出的代码。

通过层次模式, 一步步从开发者手中, 进入相应模块, 再到子系统中, 再经过-mm分支-next分支, 最终进入mainline。道路是曲折的, 但这也是保证Linux内核代码的高质量的一重要途径。

-stable分支

-stable分支顾名思义就是稳定的分支, 它现在主要由Greg Kroah-Hartman在维护。它的目的在于对已经发布的正式版本(比如v2.6时代的v2.6.X, 及v3.0时代的v3.X)的后续维护, 只包括一些bugfix或安全补丁, 不包括功能补丁。 每当Linus发布一个新版本, 就把它丢给Greg K-H,进入-stable分支 由他带领的团队来维护。不定期地, Greg K-H会拣选出一些bugfix或安全补丁, 然后发布一个修订版(比如v2.6时代的v2.6.X.Y, 及v3.0时代的v3.X.Y)。对于大多数版本, 在下一版本出来后不久, 该版本的-stable分支维护工作就将结束, 它会被标上EOF(End Of Life)标记; 也有一些版本, 会被标记上LTS(Long Term Support)而长期支持。内核源码中Documentation/stable_kernel_rules.txt详细解释了如何投递补丁到这一分支。

这个分支的诞生说来也有一番曲折。早在v2.6.11之前, 是没有对已经发布的版本发由后续修订版这一惯例的。如前一篇文章所说, 在v2.6时代以前, Linux的发布模式是维护一个奇数号(如v2.3)的开放版本2-3年, 等到它非常稳定了, 再升级到稳定版本号释放出来。 这种文火熬老汤的做法, 能保证发行版本出来后非常稳定。进入v2.6后, Linux社区抛弃了这种漫长的发布周期模式; 直接在2.6版本上开发新功能, 以Andrew Morton的-mm分支代替之前的奇数版本号开发版本的功能, 作为新功能的试验场, 采用较短周期的开发模式。仅一年就从v2.6.0发布到v2.6.10, 尽管整个社区都对代码质量有严格管控, 但仍免不了每个版本都有测试不充分的补丁进入, 导致不少问题, 比如v2.6.8发布当天就暴露了NFS代码一个重大错误, 无可奈何下, 当天Linus就又发布了一个修订版本v2.6.8.1, 历史上第一次引入发布新版本后, 再发布修订版本。对于快速开发而引进的缺乏足够测试的先天痼疾, Linus有想过稍微改变下模式, 但开发者们并不看好。于是, 亡羊补牢成了一个比较务实的做法。Greg K-H就勇敢地承担了这一在Linus看来"无趣, 吃力不讨好"的工作, 还定下了这一分支的"三条五例"

到本文写作的今天, 这一分支已经工作了8年, 事实证明它工作得不错; 不过, 也存在问题: 因为进入-stable分支的补丁也终将进入mainle(也很好理解, 否则在前面的修订版解决了某个问题, 但到下一个正式版, 问题又出现), 所以, 有一些开发者投机取巧, 利用它来绕过前面说的开发组织模式, 使补丁更容易地进入到mainline中。比如, 在最近的v3.10.1发布邮件上, Greg K-H就有一番报怨。有人忽视前面说的"三条五例", 混水摸鱼想把既非修改一个确定的bug, 也非修补某个特定问题的补丁标记为准备进入-stable分支; 更严重的, 进入这个分支的补丁原意就是要尽快地修补问题, 但有些开发者却扣着这些补丁, 等到下一个合并窗口打开才发出, 只因合并窗口期间, 会有大量补丁涌入Linus的mainline, 这样更容易进入。

当然, 也有开发者反驳Greg K-H的抱怨, 道出这也是开发者囿于雇主的发行版时间表的压力而不得不为之。其实立场不同, 利益考究自然不同, -stable分支作为各种方案权衡下的产物, 是开发者的承诺, 也是终端用户和发行版商的企盼, 纷扰纠葛, 原也说不到一个准。

-staging分支

内核中还有一个重要也特殊的分支: -staging分支。2008年6月10日, Greg K-H在内核邮件列表上发了一封邮件, 宣布创建了一个新的-staging tree, , 它的目的是要存放那些还不足以进入mainline的独立的文件系统或驱动代码。有开发者质疑说已经存在-next分支, 为何还要增加一个类似功能的分支。 Greg K-H表示说, 这个分支里的代码都是从未出现在mainline中的; 它们会将很近的将来进入mainline, 但不是下一个版本, 甚至都不保证说一定会进入。

2009年3月18日, Greg K-H又写了一篇博文, 再次申明了这棵分支树的作用。值得注意的是, 文中提到, 该分支已经包含在内核源码中, 就位于drivers/staing目录。 并且, 本文前面提到的每日一建的-next分支都有包含-staging分支的最新代码, 需要基于-staging分支工作的, 应该每天检出-next分支, 并基于其上作开发。

还有一点值得说的是, Greg K-H鼓励Janitor[8]项目新手和驱动开发者新手, 从这个分支入手, 因为这个分支上有很多简单的工作做, 适合新手入门内核开发。

* * * * * * 全文完 * * * * * *

[1]: 注意, 这里描述的只是普遍或理想的流程, 事实上, 有不少例外。

[2]: 这就有一个例外, 比如是新增的硬件驱动, 过了这个合并窗口还是可能被接受的, 因为之前代码库中没有这些代码, 引入不会造成regression。

[3]: regression就是指之前正常的代码, 因为新引入的补丁而不能正常工作, 出现倒退的现象。

[4]: 现在包括Linus在内的基本所有子系统维护者都使用git来协作维护代码, 所以内核分支经常被叫做-XXX tree, 不过负责-mm分支的Andrw Morton使用的是自己开发的quilt工具来管理补丁。所以, 本文统统以分支来指称。

[5]: -mm这个名字确实是来自Memory Management。该分支起初是作为内存管理的分支, 进入v2.6时代后, 响应发布模式的变化, Andrew把它变为一个功能测试分支, 作为向Linus提供通过考验的补丁的中转站。

[6]: 强制生成合并信息是为了更好的保留历史信息, 虽然, 对-next tree 这种生命周期只有一天的树, 保留历史信息作用不大, 但它可以给其它开发者一个提示: 这里合并了某某分支, 而简单的fast-forward只能留下提交信息。

[7]: akpm就是Andrew Keith Paul Morton名字的缩写。

[8]: Janitor项目旨在帮助新手进入内核开发领域。

Linux内核发布模式与开发组织模式(1)

larmbr | 2013-11-02 | Tags: Linux内核, 内核开发

Linux内核社区经历20多年的发展,逐渐形成了一套完善的开发模式。作为想要加入社区进行开发的人来说,当然必须熟悉下这套模式啦,其中最重要的两点是:

  • 内核发布模式
  • 内核开发组织模式

本文将对第一点进行讲述, 第二点在下一篇中讲述。(没耐心看完整篇文章的的朋友,直接看本文总结)

内核发布模式

追溯Linux内核版本号发展沿革,可知其经历了三个阶段,这分别为

v1.0以前时期
v1.0至v2.6时期
v2.6至今

v1.0以前时期

从Linus于1991年10月5日正式发布v0.0.2开始[1], 到1994年3月14日发布v1.0, 这中间经历了若干个版本的发布。此时尚未形成模式。

v1.0至v2.6时期

这一段时期,Linux用的是著名的奇数号开发版本,偶数号稳定版本模式。版本号模式为(以下引用文字来自维基百科):

A.B.C

  • A大幅度转变的内核。这是很少发生变化,只有当发生重大变化的代码和核心发生才会发生。在历史上曾改变两次的内核:1994年的1.0及1996年的2.0。
  • B是指一些重大修改的内核。
  • C是指轻微修订的内核。这个数字当有安全补丁,bug修复,新的功能或驱动程序,内核便会有变化。

其中,当B为奇数,标明这是一个开发版本; 当B为偶数,标明这是一个稳定版本。其运转模式如下:

新的特性或功能总是基于稳定版本开发, 如果新增的代码太过于庞大与激进, Linus就会另开一个比当前版本号大1的奇数版本号,是为开发版本。新特性或新功能代码被引入该开发版本, 如果该版本被认为方向不对, 则干脆就直接抛弃该版本内核; 相反, 如果该版本稳定下来, 则考虑把它 1) 合并为当前稳定版本。2) 另开一个分支,变成一个新的偶数版本号。

这样粗粒度的版本号模式,意味着相当长的发布周期: 一般是2-3年一个稳定版本, 如图1所示: 从v2.0 到 v2.2,从v2.2 到 v2.4, 从v2.4 到 v2.6, 都经历了2-3年不等的时间。

图片

图1: v1.0 - v2.6 发布时间

如此长的发布间隔时间,意味着:一个新的硬件上市,买家需要花几年的时间来等待内核的支持,这是无法忍受的;而这也迫使各个发行版本商从开发版本中向后移植新的特性,这导致了发行版间内核的分歧越来越大, 这是人们所讨厌的。这是这个版本号模式抛弃的重要原因。

v2.6至今

  1. 固定的2.6版本号

    进入v2.6时期,Linux内核核心开发者决定不再创建2.7分支, 而继续在2.6分支上进行新功能的开发。核心开发者Greg Kroah-Hartman写了一篇文章对此作了一些解释。大概原因是: 在2.6版本释出前, Linus的主内核分支(mainline)进行了长达数个月的特性冻结, 不再接受新特性代码。这样, 进入Linus主内核分支的代码都首先经过另一个核心开发者Andrew Morton)维护的-mm分支(将在下篇文章中讲述)的测试; 而且其它子系统维护者也会把他们的分支代码先在Andrew Morton的-mm分支中进行测试, 之后代码才支进入Linus的mainline。可以说-mm分支取代了v2.6时代之前奇数号分支这一新功能试验场的作用。这样的模式稳定了不少, 新功能也得以更快速被吸收入mainline内核中。于是, 前面所述的奇开发偶稳定, 长周期的版本号模式被抛弃了。 2.6版本号固定下来, 内核沿着2.6.X的递增版本号进行发布。

  2. 第四位版本号偶然登场: 2.6.X.Y

    在这样的模式引导下, 内核确实加快了开发步伐: 从2003年12月8日2004年12月24日这一年时间内, 内核发布了v2.6.0v2.6.1011个版本。这样激进的步伐还是招致了不少内核开发者的意见, 他们认为每个v2.6.X版本都是伪装的开发版本, 因为还是有很多不稳定的PATCH被引进了。这其间一个事件也反映了这一点, 并且让内核的版本号又多了一位: 在Linus发布v2.6.8当天, NFS代码中就发现了一个亟待解决的重大错误,而此时显然不会为了修改这一个错误而再发布一个新的版本,于是,Linus发布了v2.6.8.1

  3. 第四位版本号确立地位

    激进的步伐引发的问题当然也让Linus对这一模式进行了思考。于是, 在发布v2.6.11当天,Linus发了封邮件, 宣布要采用一种新的模式: 重回奇偶版本模式, 但这种模式较之2.6前的奇偶模式更小粒度。2.6.<奇>2.6.<偶>都是稳定版本, 只不过, 对奇数版本来说, 对新功能代码的接受更加宽容, 但它必须被密切关注, 以确保它们不会出现大问题; 对偶数版本, 则更加谨慎, 只接受一些被认为是稳定的补丁。

    Linus这种表面看都是稳定版本, 内里则行奇偶之别的做法并未得到开发者们的认同。在那封邮件里, 出现了少有的很长的讨论, 大家认为出现问题的原因还是因为测试太少。虽然, 补丁在进入Linus的mainline前有经过前面所说的-mm分支的测试; 在Linus每发布一个版本前的rc预览版本(将在下篇文章中讲述)也经过用户的测试, 但实际问题是这两个途径都没发挥它们的作用: -mm分支因为是新代码的试验场, 不太稳定,有时连编译都失败, 少有开发者愿意在该分支上测试; 而rc版本在用户看来不是正式的官方发布版, 也少有人愿意测试它们。

    既然测试太少问题难解, 那不妨以补救方式来对正式版本进行修正!

    有人提出了这个建议, 并把前面所说的v2.6.8引入的四位版本号拿来使用: 每当释出一个v2.6.X版本, 如果有重要的bugfix或安全补丁, 则移植到v2.6.X上, 并释出新的bugfix版本: v2.6.X.Y。Linus本人起初不看好, 觉得这是一项没有多少成就感, 吃力不讨好的工作, 没有人愿意做。但Greg Kroah-Hartman站出来, 并建立新的一个-stable分支来做这件事。他进行这种尝试的第一个版本就是v2.6.11.1

    事实证明这样做挺好, 并且该模式也一直延续到今天(这是后话, 在下篇文章中详述)。

  4. 3.0时代, 换汤不换药

    在2011年7月21日,Linus释出了原本应为v2.6.40的新版本v3.0, Linus在邮件中解释说, 新的3.0版本号,只是为了庆祝Linux20周年庆,同时丢弃掉笨重的2.6.X数字系统。

    可以说,3.0时代的版本号模式并没有改变, 只不过是把2.6改成了3, 并且从0开始版本号计数而已, 它的象征意味更浓些。

总结

从v2.6开始的版本号模式, 缩短了版本周期(大概2-3个月一个版本), 改变了之前以奇偶数分开发,稳定版的漫长周期模式。 每个版本都有若干个(5-7个)候选版本(rc, release candidate)的形式发布, 作为预览版。 一般来说,只有第一个rc接受新特性或新功能代码, 此rc就是俗称的合并窗口, 当开发者认为该版本已经解决了上一个版本的一些regression问题, 内核足够稳定了, 就会发布新版本。新的版本释出后会交到Greg K-H维护的-stable分支进行维护, 接受bugfix或安全补丁。而Linus则开启合并窗口, 进行下一个新的版本的开发。如此周而复始。

* * * * * * 全文完 * * * * * *

[1]: 其实对Linux项目真正诞生的日期,存在不同的看法:有人认为是1991年8月25日Linus在Usenet上发表的关于Linux系统的帖子开始,也有人认为应从v0.0.2版本公开发布之日算起。可以看看Linus本人的看法