Git for Linux: 追踪代码历史的技巧

larmbr | 2013-10-27 | Tags: Linux内核, Git

图片


配图是Linus把其Linux内核版本库迁移到Git的第一个提交信息, 此时距离其开始开发Git仅仅过去13天!

Git作为一个版本控制工具, 不单只在Linux内核开发过程居功至伟, 而且在阅读代码过程中, 也堪称神器。且不妨称ctagscscope作为横向阅读代码的利器, 这两个工具都能记录当前代码符号定义与引用, 可谓旁征博引, 纵横捭阖, 让人在代码汪洋中不至于迷失; 但它们也有劣势: 无法记录代码的历史变更, 无从追溯代码的前世今身。不过Git弥补了这一缺憾, 可称之其为纵向阅读代码的利器, 追根溯源, 探赜索隐, 无往而不利。

下面介绍几条在阅读Linux代码过程中的小技巧(以下都是以跟踪着Linus的mainline tree[1]为前提)。

  • 查看某次提交的信息

    如果知道某个commit ID或其它引用格式(关于git的各种引用格式, 详阅man git-rev-parse中SPECIFYING REVISIONS一节), 运行

    git show <commit Id/revspec>
    

    就可以查看以下重要信息:

    • 本次提交修改了什么代码, 动了哪些文件, 增加(删除)了哪些代码。
    • 本次提交的提交信息, 一般作者会解释这次提交的原因, 解决了什么问题, 如何解决, 等等, 这些信息对理解代码相当重要。


  • 查看某个版本的代码库

    git checkout -b <分支名> <某个版本>
    

    这条命令检出某个版本(比如v3.10)的代码库, 到一个临时的分支, 分支名可任取。出于学习研究目的的话, 最好选择某个发行版本的代码(用git tag -l可查看有哪些版本)。原因有:

    • 如果每天都跟mainline同步代码的话, 那么除了发布时间节点为外, 你的代码库总是处于某个不确定状态: 要么刚合并了某个分支, 要么(稍好些), 刚发布了某个版本的第N个候选版(如: v3.X-rcN)。之所以称之为不确定是因为此时正在开发周期中, 代码还未正式发布, 还不稳定, 换言之, 可能被修改, 甚至被撤消。因此, 这种代码不适合作学习研究用。
    • 研究代码过程中, 少不了ctagscscope这两个利器。不过, 每次代码一变动, 就要重新生成这两个工具的数据库文件, 这是件很烦人也费时的事。
    • 时不时地可能会在代码中作上自己的注记或解释, 如果是在master分支的话, 很可能一更新代码就会有冲突; 检出到另一个分支, 就不会有这种问题。


  • 追踪特定文件的变化历史

    git log --follow <文件名>
    

    运行这条命令, 就可以追踪某个文件从诞生以来的变化历史。好处有:

    • 跟踪该文件的历史变化过程, 可以详细了解该模块代码的发展历程。尤其是, 结合前面的git show命令给出的提交信息, 更深入地了解发展变化的原因
    • 了解该文件最后一次改动的时间, 从侧面了解该模块的稳定程度与开发热度, 从而决定是深入详读还是大致略读。对于稳定的代码, 可详读; 而对于还在热烈开发中的代码, 也许代码还会变, 略读可能更合适。


  • 追踪文件内容的变化历史

    前一个命令可能从文件的视角, 宏观地把握变化方向, 当深入阅读代码时, 还需要另一个命令, 来帮助追踪了解具体的代码的变化。

    git blame -C -L <start>,<end> <文件名>
    

    该命令可以小到行的粒度来了解代码的变化历史, -C选项可以追踪某行代码之前是位于哪个文件中的, -L选项则是选定行范围, 这样对于很大的文件, 对整个文件运行该命令可能会比较久, 指定感兴趣的行范围可以缩短时间。这两个选项都是可选的

    使用场景:

    • 该命令会输出每一行引入的时间, 作者, commit ID, 有了这些信息, 或者用git show命令阅读作者引入时的提交信息, 了解该改动的原因和做法; 或者, 利用这些信息, 加上lkml关键字, 用Google搜索邮件列表存档, 更深入了解当时开发者们对这一变动的所解决的问题, 解决方法的讨论


  • 确定某次变化是哪次提交引入的

    设想某本内核书籍(旧内核版本)提及一个数据结构, 但在你当前阅读的代码里却没有这个结构, 你想知道是哪次提交删除了这个结构的, 为何删除, 这其中蕴含着二分查找的思想, 因此, git bisect命令是完成这一工作的不二选择。

    git bisect start HEAD  <旧版本>  --no-checkout
    git bisect run sh -c 'git show BISECT_HEAD:<包含那个结构的文件路径> | grep -q "struct <结构名>"'
    

    第一条命令, 指定了查找的范围, --no-checkout表示对于每一次检查, 不检出当前版本库, 以加快速度。

    第二条命令, 运行一个shell命令, 检查当前版本库中文件中是否包含所有考察的结构, 有则返回0, 无则返回一个非0值(本例中是grep -q的返回值, 非0值必需在1-127之间, 包括127, 但排除125, 详见man git-bisect)。BISECT_HEAD指代当前正在检查的版本。

    当这两条命令运行结束, 引入变化的提交就被找到了。然后, 用前述的git show可以查看该次提交的说明和内容, 以了解改变的原因。


实例演示


当从这篇文章了解到Mel Gorman引入迁移类型(Migration Type)以解决内存碎片问题的补丁时, 我想了解它们是何时引入mainline, 如何演变的, 是这么做的:

  • 我知道相关的关于Migration Type的定义在include/linux/mmzone.h中:

    enum {
         MIGRATE_UNMOVABLE,
         MIGRATE_RECLAIMABLE,
         MIGRATE_MOVABLE,
          ...
    }
    

    运行

    $ git log --oneline --follow include/linux/mmzone.h
    

    然后从输出中提交信息中搜索关键字眼, 比如"MOVABLE", 找到最早出现的提交, 用git show查看, 然后依次顺藤摸瓜, 接下来查看以后的每次提交, 看是否有关于这一部分的代码。

    这种方法局限在于:

    • 提交信息中不一定存在这个字眼, 所以, 对关键字的选取很重要。假设查不到, 可能会用"migration"等。
    • 以后每次都检查是个费力的工作。 好在可以用脚本自动化完成这一工作, 比如用git show显示之后的每一次提交变更的内容, 查找该关键字, 若存在, 则记录下该次的commit ID。
    • 有可能存在某次修改是关于这部分内容的, 却没有修改到这个文件。这种比较棘手, 但是, 考虑到, 比如前面这个enum定义是重中之重, 不触及这部分的修改的可能性比较小; 而且, 作为了解发展脉络, 失却一两次提交可能不是大问题, 所以, 这个问题影响不大。


  • 前一个做法是自底向上, 接下来的做法可称为自顶向下

    同样从enum定义这部分定义入手, 在我当前代码中, 这部分大概是位于include/linux/mmzone.h文件的第38一第41行, 运行:

    $ git blame -C -L 38,41 include/linux/mmzone.h
    47118af0 (Michal Nazarewicz 2011-12-29 13:09:50 +0100 38) enum {
    47118af0 (Michal Nazarewicz 2011-12-29 13:09:50 +0100 39)       MIGRATE_UNMOVABLE,
    47118af0 (Michal Nazarewicz 2011-12-29 13:09:50 +0100 40)       MIGRATE_RECLAIMABLE,
    47118af0 (Michal Nazarewicz 2011-12-29 13:09:50 +0100 41)       MIGRATE_MOVABLE,
    

    发现: 作者不是Mel Golman, 说明有人改动过, 于是, 运行

    $ git show 47118af0
    

    查看提交说明及提交内容, 发现:

    -#define MIGRATE_UNMOVABLE     0
    -#define MIGRATE_RECLAIMABLE   1
    -#define MIGRATE_MOVABLE       2
    -#define MIGRATE_PCPTYPES      3 /* the number of types on the pcp lists */
    -#define MIGRATE_RESERVE       3
    -#define MIGRATE_ISOLATE       4 /* can't allocate from here */
    -#define MIGRATE_TYPES         5
    +enum {
    +       MIGRATE_UNMOVABLE,
    +       MIGRATE_RECLAIMABLE,
    +       MIGRATE_MOVABLE,
    

    原来这一次提交中把宏定义变为enum定义。于是, 回退到这一次提交的前一次, 即宏定义的版本

    $ git checkout -b temp 47118af0^
    

    然后, 重复用git blame命令, 找出上一次修改这部分代码的提交, 如此递推, 可以找到最开始引入这部分代码的提交。

    值得一提的是, 上面用的是git checkout命令检出到另一个临时分支, 这之后的回退, 由于已经在temp分支了, 运行git reset <commit>^即可。研究完成之后, 可以运行git branch -D temp把这一分支删掉。

    同样, 这种方法可以用脚本自动化

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

[1]: 追踪Linus的mailine tree, 运行git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git

一个普适性的Git分支workflow

larmbr | 2013-10-04 | Tags: Git, workflow

Git作为一个分布式版本控制系统, 去中心化的基因深入骨子里。除了每个参与者的版本库皆能成为中心版本这一重要特性之外, 我想最能体现Git的优秀就是它对分支(branch)创建, 操作与删除的轻灵的驾驭能力, 这衍生了许多基于分支的强大的协同工作流(workflow)模式。

传统的版本控制系统(如SVN)对于分支的理解是另一份工作区的拷贝。这是一种很符合直觉的做法, 却也是一种非常重量级(High-weighed)的做法, 虽然SVN采取了廉价复制的做法, 这避免了复制所有工作区文件的做法, 只有在为了区分不同版本的对象时才会复制数据, 但本质上仍没脱离这个窠臼。

Git对于分支的创新性看法源于它本质上是一个按内容寻址的(content addressable)数据库! 它把所有的文件内容当成一个个存放在数据库中的对象, 叫做blob, 每个blob均有一个对应的键值(SHA-1 key), 而从文件系统视角看的目录, 则很自然地被当成是包含若干个blob的树对象, 叫做tree

当基于这个数据库构建可追踪历史的版本控制系统时, 每一次提交不过是对工作区内的blob或/和tree的修改后的一个整体快照(snapshot), 这个快照对象叫commit, 它包含有当前快照的tree的key, 因而可以获取当前整个工作区所有目录下所有文件的内容; 它还包含有一个指向前一次commit(第一次除外)的key的字段, 这样构建起一个提交历史的链表, 以此作为构建版本控制系统的基石。

因而, Git的分支仅仅就是包含某一个commit的key的文件(这个commit叫做当前分支的tip)! 由这个commit便可追溯以前的历史。因此, Git分支的创建与删除其实就是创建或删除一个文件, 相当轻灵快速的操作!

基本模型

所谓workflow, 直译为工作流, 局限于本文的语境, 在这里理解为基于Git的代码进入主版本库(master)的流程。

在这种workflow里, 人为定义一个版本库为中心版本库(central repo), 所有参与者都clone这个版本库, 从这里pull更新或push更新到这里。这个中心版本库里存在两个分支:

  master: 该分支中反映当前最新发布的代码状态。换言之, 该分支中的每一次提交都是一个新的版本(或修正版), 它是稳定的。   develop: 该分支中的代码反映下一个将发布的版本的代码状态。这是一个开发分支, 它的稳定性很差。它也叫集成分支(Integration branch), 因为许多每晚构建(nightly build)都是基于该分支。

这两个分支的交互如下:

  develop:    O --> O --> O --> O --> O ......
            ↗             \           \
           /               ↘           ↘
  master: O --------------> O ---------> O ......
          ↑                 ↑            ↑
        初始版本v1.0       v2.0          v3.0

如图, 当develop分支到达一个稳定点或完成既定的特性开发后, 就会被merge回master分支, 成为一个新的发布版本, 并打上一个标记, 以便以后查询或追踪。

这个workflow涉及的典型操作如下:

  $ git checkout -b develop master
    Switched to a new branch 'develop'

  ... 热烈的开发, 调试 ...

  $ git checkout master
    Switched to branch 'master'
  $ git merge --no-ff develop
    Merge made by the 'recursive' strategy.
  $ git tag -a v2.0

注意, --no-ff选项表示: 即使是fast-forward, 也要当成是合并, 生成一次合并提交。这避免了丢失掉这次合并的历史, 更重要的是, master分支中的提交是一个个发布的节点, 因而该选项能保证每一次合并都只引入一个提交。如图:

  git merge --no-ff :  A ---> B ----------------------> H
                               ↘                      ↗ 
                                 C ---> D ---> E ---> F

          git merge :  A ---> B ---> C ---> D ---> E ---> F
                               ↘                     
                                 C ---> D ---> E ---> F

3个辅助分支

以上两个分支是长期分支, 更精细化地, 还存在3个短期分支, 以辅助这一模型更好地运转。分别是:

  • feature: 虽然develop定位于开发分支, 但对于一些大的功能, 开发周期长, 无法在下一版本发布, 甚至具体什么时间点能完成也无法确定, 将这些功能的开发与下一版本的功能开始一起混合在develop中显然不是合理的做法, 为此必要增加一个新的分支, 它从develop分离, 在经历漫长的开发后, 可以合并回develop, 甚至可以选择这个新功能。然后, 这个分支的生命周期就可以结束了。

    这个分支涉及的典型操作如下:

    $ git checkout -b feature-x develop
      Switched to a new branch "feature-x"
    
      ... 漫长的开发, 调试 ...
    
    $ git checkout develop
      Switched to branch 'develop'
    $ git merge --no-ff feature-x
      Merge made by the 'recursive' strategy.
    $ git branch -d feature-x
      Deleted branch myfeature
    $ git push origin develop // 推送到中心服务器的develop分支
    
  • release: 在基本模型中, 一旦develop稳定了或完成了预定功能的开发后, 就合并回master形成一次新的发布。这种模型的问题是, develop分支的时效性非常强, 而要进入master要保证稳定性非常强, 这个点不是很好把握, 所以实践中, 有特性冻结(feature freeze)这一做法。就是当预定功能开发完毕, 处于候选发布状态时, 不再接受新的功能的提交, 只接受bugfix提交。这就促成了在完成预定功能开发后, 从develop分离出一个新的分支, 该分支将接受广泛测试, 修改bug, 以期达到稳定状态再合并加master。同时也要合并回develop, 确保其中的bug也得到修复。

    此外, 新增这个分支, 相当于增加一个缓冲层, 可以做额外的事情。比如做一些元数据处理, 如修改版本号, 修改总体的changelog等。

    这个分支涉及的典型操作如下(假设接下来的发布版本号定为2.0):

    $ git checkout -b release-v2.0 develop
      Switched to a new branch "release-v2.0"
    
      ... 测试, 只接受bugfix ...
    
    $ git checkout master
      Switched to branch 'master'
    $ git merge --no-ff release-2.0
      Merge made by the 'recursive' strategy.
    $ git tag -a 2.0
    
    $ git checkout develop
      Switched to branch 'develop'
    $ git merge --no-ff release-2.0 // 可能会有冲突, 有则解决之
      Merge made by the 'recursive' strategy.
    
    $ git branch -d feature-x
      Deleted branch myfeature
    
  • hotfix: 前两个临时分支都是计划中的, 而这个分支则可以说是计划外的, 因为它主要解决已经部署运行的发布版本中偶然出现的重大问题。比如上面的2.0发布并部署运行后, 发现了一个很严重的bug, 导致服务中断。此时, 将基于当前这个发布节点, 紧急分离出一个分支, 修复问题。

    这个分支涉及的典型操作如下(假设当前发布版本号定为2.0):

    $ git checkout -b hotfix-2.0.1 master
      Switched to a new branch "hotfix-1.2.1"
    
      ... 紧急修复问题 ...
    
    $ git checkout master
      Switched to branch 'master'
    $ git merge --no-ff hotfix-2.0.1
      Merge made by the 'recursive' strategy.
    $ git tag -a 2.0.1 // 重新发布一个当前版本的修订版本
    
    // 把补丁向后移植到**develop**中(如果此时有存在**release分支**, 则就移植到**release**中)
    $ git checkout develop
      Switched to branch 'develop'
    $ git merge --no-ff hotfix-2.0.1 
    
    $ git branch -d hotfix-2.0.1
      Deleted branch hotfix-2.0.1
    

    上面的操作过程, 有个要注意的点: 如果在向后移植时, 存在着一个release分支(即下一个版本快要发布了), 则应该向后移植到该release分支中, 而不是develop分支。因为该release分支最终也将会被合并回develop分支

总结

传统的主分支+开发分支同时存在, 使稳定版本与开发版本的合理分离, 确保开发过程的稳定推进。而Feature, Release, Hotfix三个辅助分支的加入, 则使这一过程能够被更精细地控制, 更好地应对实际开放环境中的问题。

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

x86实模式到保护模式及Linux启动协议的演变

larmbr | 2013-09-28 | Tags: Linux内核, x86, 实模式, 保护模式, 内核启动

操作系统的启动,英文称为bootstrap,又有汉译为“自举”,这一个自指涉的词汇生动地描述了操作系统启动前所遇的矛盾:

  • 加电瞬间所有硬件处于一种随机状态,如何完成第一条指令的加载,如何了解整机的硬件状态,以便完成后续的操作系统启动。

  • 即使第一条指令成功运行,如何把操作系统从外存加载到内存,以便执行一开始的初始化行为。

这两个问题都有了成熟的解决机制,为操作系统的启动铺设好了真正环境,分别是采取BIOS[1]和引导程序的解决方案。本文将从操作系统角度, 详述x86平台上与Linux内核启动过程悉悉相关的从实模式(virtual mode)保护模式(proctected mode)的演变过程, 以及x86平台上的Linux内核启动协议的变化。

洪荒时代: 实模式

从实模式到保护模式的变化,不仅是Intel处理器的一部发家史,更是30年来PC处理器的发展史。

Intel处理器从4004的开基立业,到8008的初露锋芒,再到8080的引起哄动,标记着PC时代的曙光已经到来。1978年推出首枚16位处理器8086; 同年,又趁热打铁地推出性能更出色的8088处理器。该处理器的特点是把地址线扩展到到20条,由此可以寻址1M字节的内存空间(220=1M)。出于向后兼容的要求,该处理器的设计别出心裁,引入了很多人耳熟能详的“段”的概念,即把20位的物理地址划分为称为16位的段:16位的段内偏移。还引入了段寄存器,用以配合完成段基址 << 4 + 段内偏移到20位物理地址转换过程, 如图。

  段基址: 0x1F21 << 4 + 段内偏移: 0x1027 = 物理地址: 0x 2 0 2 3 7

    0x 1 F 2 1 0
  + 0x   1 0 2 7
  --------------
    0x 2 0 2 3 7

这种模式就叫做实模式(real mode), 它有以下几个问题:

  • 显然, 这种寻址方法的最大寻址值是(0xFFFF : 0xFFFF =)0x10FFEF, 这比20位地址总线能寻址的1M字节范围还大0xFFEF字节。该CPU采取的方法是Wrap Around**, 即对1M取模, 因此, 多出的0x100000 - 0x10FFEF实际是映射到0x0 - 0xFFEF。

  • 从地址构造模式看, 可以发现段基址有个特征,其低4位全为0,也就是说每个段的起始地址一定是16的整数倍, 这反映了这个名字的由来, 物理地址空间已经被人为地划分为64k(216)为大小的区间。但注意, 这只是一个人为的划分, 换句话说, 没有任何硬件机制的隔离, 一个进程只要修改段基址寄存器的内容, 就可以随意访问其他段的内容! 这是一个重大的安全漏洞。

  • 这种地址构造模式还有另一个问题, 也就是一个物理地址可以有多种表示方法。注意最终的物理地址中间12位是段基址和段内偏移重合的, 所以, 理论上最多可以有212种组合方式可以构造出同一个物理地址!

文明时代: 保护模式

保护模式的滥觞: 80286

1982年, 伴随着Intel处理器史上最后一枚16位处理器80286的发布, 一种新的模式被引入了, 即为保护模式(proctected mode)。这一处理器地址总线宽度提高到了24位, 这意味着可以寻址(224=)16M字节的空间。不过前面说它仍然是16位的处理器, 因为它向后兼容, 仍然实现了前述的段寻址模式: 16位的段基址 : 16位的段内偏移。不同的是, 这枚CPU能够对内存及一些其他外围设备做硬件级的保护, 限制了一些非法地址的访问, 从而实现了硬件机制上的保护, 这也是这种名字的由来。

该处理器的更大意义是, 它出于向后兼容的需要, 开启了操作系统启动时从实模式保护模式切换这一传统, 一直沿续至今。前面说过实模式的第一个问题, 就是地址的回绕(wrap around), 在80286的引入后, 更增添了许多麻烦: 现在已经能寻址最多16M字节的空间了, 不存在超过1M要回绕这一问题了。但是, 在机器刚开始启动的时候, 仍处于实模式, 只能访问1M字节的空间, 意味着此时A20 - A23这4根地址线是用不到的。于是, Intel采用了一种叫A20 Gate的解决方案:

  • 在系统开机时, CPU复位, 这A20-A23置为0, 即A20 Gate被禁用,则对0x100000-0x10FFEF之间的地址进行寻址时,还是取模(回绕),从0开始访问内存。

  • 在进入保护模式后, 24根地址线全部启用, 即A20 Gate被开启,则对0x100000-0x10FFEF之间的地址进行寻址时,访问实际的地址对应的物理内存。

保护模式的辉煌: 32位处理器时代

1985年,Intel推出了里程碑式的80386处理器, 也开启了一个称为i386x86的光辉时代。这枚处理器不仅是首枚32位处理器,还引入分页模式,而分页模式是现代操作系统实现虚拟内存的先决条件。

同样为了向后兼容,80386保留了段机制, 但在保护模式下, 此时的16位段寄存器[2]存放的不再是段基址,而是一个13位的索引值,指向一张叫全局描述符表(GDT)局部描述符表(LDT)的某一项,表项长8字节, 包含着32位的段基址, 段长度, 段的访问权限之类的信息。前述的16位寄存器除了13位索引值外,剩下的两位(0-1)表示请求权限,一位(2)表示高13位是GDT还是LDT的索引值。此时的段寄存器被称为段选择子(selector)。 于是, 使用兼容的段基址和1段内偏移的方式, 通过一个间接的GDT表或LDT表, 从中取出段基址, 再加上段内偏移, 形成一个32位的地址。

  • 如果分布模式有启用, 这个地址就叫做线性地址(linear address), 要通过分页单元进一步处理, 形成最终的物理地址。

  • 如果分布模式没启用, 这个地址就是最终的物理地址。

Linux内核启动协议

Linux在X86平台上的启动协议随着内核的发展及硬件的发展,已经变得很复杂(详见内核源代码树Documentation/x86/boot.txt)。总的来说,启动协议分为旧内核(zImage)时代大内核(bzImage)时代(从协议2.0开始,已经发展到2.10)。接着将简要介绍这两种协议。

旧内核(zImage)时代

在旧内核时代(内核版本< 1.3.73),Linux内核映像还较小(zImage)。此时典型的物理内存布局如图1所示:

          |                        |
  0A000   +------------------------+
          |  Reserved for BIOS     |  Do not use.  Reserved for BIOS EBDA.
 09A000   +------------------------+
          |  Command line          |
          |  Stack/heap            |  For use by the kernel real-mode code.
 098000   +------------------------+
          |  Kernel setup          |  The kernel real-mode code.
 090200   +------------------------+
          |  Kernel boot sector    |  The kernel legacy boot sector.
 090000   +------------------------+
          |  Protected-mode kernel |  The bulk of the kernel image.
 001000   +------------------------+
          |  Boot loader           |  <- Boot sector entry point 0000:7C00
 001000   +------------------------+
          |  Reserved for MBR/BIOS |
 000800   +------------------------+
          |  Typically used by MBR |
 000600   +------------------------+
          |  BIOS use only         |
 000000   +------------------------+
图1: 旧内核时代物理内存布局

从图中看出,最高内存是0x0A000,即640K。这个数字历史缘于上世纪80年代,当时IBM所推出的第一台PC机采用的是前述的Intel 16位8088芯片,可供寻址的物理内存总共为1MB。这1MB中的低640KB供DOS以及应用程序使用,而高端的384KB则被留作它用,其中低端的640KB被称为常规内存(normal memory),高端的384KB则被称为保留内存(reserved memory),这两种不同的内存类型通过物理地址0xA0000得以分隔,此后这个分界线便被确定下来并沿用至今。

下面将结合linux-0.1.1版本的启动代码及上图,简述旧内核(zImage)时代启动协议。

  • 从0x00000至0x01000这4k空间主要是保留给BIOS使用,存放加电自检期间检查到的系统硬件配置。比如BIOS在初始化硬件时,会把中断向量初始化放在地址0开始的物理内存处。

  • 接下来从0x01000开始,就是可以存放引导程序的地方。引导程序负责把内核映像加载到内存,再将控制权交给内核。BIOS在完成其加电自检(POST), 检测外围设备等工作后, 就把磁盘设备上的MBR(Master Boot Record)加载到物理地址0x07c00处(而不是恰好在0x01000)。其实MBR正是存放着引导程序。MBR块是硬盘第一个扇区,它的大小只有512字节。如此小的引导程序能把内核映像加载到内存吗? 在Linux初期,内核映像(zImage,有别于后来的大内核bImage)是很小的, 比如0.1.1版本内核的大小才196KB。所以,512byte的引导程序是可以把内核映像加载到内存的,这部分代码对应于之前的/boot/boot_sect.S这个文件,从名字可以看出,boot sector意即启动扇区,正是指MBR块。它在编译后大小刚好为512字节,能放在MBR块处。

  • 从图1中可以看出0x90000-0x90200处标明为内核启动扇区,为何此处又有一个大小为0x200(刚好512字节)的启动扇区块? 其实,前述的boot_sect.S文件,不仅做的是加载内核映像,它的第一步动作是把自身从0x7c00复制到0x9000处, 再加载实模式内核模块kernel setup, 最后才加载保护模式映像模块system。至于为何要移动自身这一步动作,是因为后续的加载setup模块动作加载到0x90200,需要用到跳转指令,而实模式下一个段大小64k, 所以boot_sect.S必须把自身移动到距离加载setup模块一个段距离内。

  • 接下来可以看到从0x90200处开始是kernel setup区域。boot_sect.S移动自身到0x9000后,会继而从硬盘紧接着放MBR块的kernel setup模块(占4扇区)加载到0x90200处。这个setup模块是内核实模式代码,由/boot/setup.S文件编译而成。它的作用是把BIOS加电自检时保存在最开始(0x0处)的硬件信息复制到一个安全的地方(0x9000处,没错,将会覆盖boot_sect块,但此时boot_sect已经执行完毕,没有用处了), 以备内核接着使用。

  • 接着kernel setup模块会把保护模式内核映像(由boot_sect.S加载的system模块,加载在0x1000处,从图中亦可印证)整体移动到物理地址0x00000处。此外,为了为接下来的system模块在保护模式下运行,还要进行临时设置中断描述符表(IDT)和全局描述符表(GDT)的操作。从图中可看到,从0x98000开始开辟作为实模式下的setup模块使用的栈空间, 以作为之后C语言接手系统后, 各个函数的活动空间。

  • 最后, 系统的控制交割给保护模式下的system模块,由它完成更多的系统初始化功能,此处不再赘述。

以上整个过程如图2所描述。

图片

图2: 旧内核时代启动过程内核在内存中的位置变化

大内核(bzImage)时代

随着内核的发展,内核体积也越来越庞大,进入了大内核时代。像旧时代靠内核自身的512字节的引导程序已经无法完成如此复杂的功能,需要引入专门的引导程序。同时,启动协议也相应地进入了2.0时代。众所周知的引导程序有LInux LOader(LILO)及广泛使用的Grand Unified Bootloader(GRUB)。下面举例GRUB说明一下引导程序的加载内核的过程。

  • 首先执行基本的引导装载过程,该程序通常位于主引导记录(MBR)中,大小为512字节,由BIOS将其装入RAM中物理地址0x00007c00处,这就替代了旧内核时代内核自身的引程序,它的任务是建立实模式栈并利用BIOS指令将第二引导加载过程装入内存。

  • 第二引导加载过程(又称次引导过程)随后从磁盘读取可用操作系统的映射表,并提供给用户一个提示符,当用户选择需要被载入的操作系统,或是经过一段时间的延迟自动选择一个默认值之后,次引导过程便将相应分区下的内核映像以及initrd装载到内存中,而前述的映射表是GRUB通过读取/boot/grub/grub.conf文件中所设置的内容生成的。另外次引导过程还包括对特定文件系统(如ext2,ext3等)的支持以及对内核启动代码的初始化等职责,这就决定了次引导过程将占用较大的存储空间——连续多个扇区,从而无法装进单个扇区中,因此GRUB通常将该过程放在特定的文件系统中(通常是boot所在的根分区)。

  • 次引导过程拷贝到内存的目标中包括一个名为initrd的文件,该文件的全称为boot loader initialized RAM disk,即bootloader初始化内存盘。因为在Linux内核的启动过程中将会加载位于硬盘上的根文件系统,与硬盘相应的设备驱动程序又被存储在该文件系统中,这就导出一个矛盾:加载根文件系统需要使用设备驱动程序,而设备驱动程序在根文件系统加载之前又无法载入内存运行。当然解决该矛盾最简单的方法便是将设备驱动程序编译进内核,然而如今的Linux内核支持多种硬件架构,因此根文件系统可能被存储在IDE、SCSI、SATA、U盘等多种介质中,如果将所有的硬件驱动均编译进内核无疑将使得内核臃肿不堪,引入initrd正是为了解决如上问题,它主要用于实现一些模块的加载以及文件系统的安装等功能。在次引导过程完成相应文件的加载之后将会执行一个长跳转指令,该指令跳过实模式内核代码的前512个字节,也即跳到由前述链接脚本所指定的执行入口_start处开始执行,而所跳过的512字节正是我们之前剖析的Linux内核自带的引导程序,整个的衔接过程可谓天衣无缝。而内核自带的boot_sect模块已经失去了它的作用,所以,从2.6.24版本的内核开始,已经把boot_sect.Ssetup.S文件合并成为一个header.S文件。

此时的使用2.0启动协议的bzImage内核的内存空间布局如图3所示。

          ~                        ~
          |  Protected-mode kernel |
   100000 +------------------------+
          |  I/O memory hole       |
   0A0000 +------------------------+
          |  Reserved for BIOS     |   Leave as much as possible unused
          ~                        ~
          |  Command line          |   (Can also be below the X+10000 mark)
  X+10000 +------------------------+
          |  Stack/heap            |   For use by the kernel real-mode code.
  X+08000 +------------------------+
          |  Kernel setup          |   The kernel real-mode code.
          |  Kernel boot sector    |   The kernel legacy boot sector.
        X +------------------------+
          |  Boot loader           |   <- Boot sector entry point 0000:7C00
   001000 +------------------------+
          |  Reserved for MBR/BIOS |
   000800 +------------------------+
          |  Typically used by MBR |
   000600 +------------------------+
          |  BIOS use only         |
   000000 +------------------------+

   ... where the address X is as low as the design of the boot loader permits.
图3: 大内核时代物理内存布局

从图3可以看出,此时的内存大小也跟随着CPU寻址空间的扩展而增加到1M以上,但从0xA0000~0x100000-1范围内的物理内存通常保存BIOS例程,并且映射ISA图形卡上的内部内存。这个区域就是IBM兼容PC上从640KB到1MB之间的著名的洞——图1中的I/O memory hole:物理地址存在但被保留,不能由操作系统使用。

此外,我们发现内核实模式启动扇区起始地址被定义为一个未知数X, 并且指出X的取值应是引导程序所允许的尽量低的地址值。从X开始,实模式的boot sector和setup代码,加上实模式所用作栈或堆的空间,不能超过0x9A000。因为一些新的BIOS需要使用从起始地址0x9A000开始的额外内存空间,该内存空间即扩展的BIOS数据区EBDA(Extended BIOS Data Area)。因此引导程序需要利用BIOS的”INT 12h”例程来探测该BIOS所允许的最低内存地址是多少,保证实模式内核代码空间不超过这个点,以免数据被EBDA数据区覆盖。

最后,保护模式内核代码被加载到0x100000(即1M)处,而不是旧内核时代加载在0x10000处。这是大内核(bzImage)和小内核(zImage)的显著区别。

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

[1]: 现在已经有由Intel开始研发, 其后由一个专门的论坛研发维护的新标准UEFI, 用于取代老旧的BIOS。

[2]: 其实段选择器还有32位隐藏的部分, 存放着段基址, 在第一次访问描述符表后会把当前段基址存放于此处, 用于加快访问, 所以它实际上是48位, 详见Intel文档。

X86汇编调用框架浅析与CFI简介

larmbr | 2013-09-20 | Tags: x86, 汇编, CFI

[阅读本文仅需要一点x86汇编的知识。另, 本文的汇编使用AT&T语法]

在内核代码调试中, 或是漏洞分析中, 学会看懂backtrace或是熟悉汇编, 都是基础之功。这中间都牵涉到一个叫调用框架(call frame)的概念, 这个名词也叫栈帧(stack frame)活动过程记录(activation record)。所谓调用框架就是指称一个函数(或过程,或方法)被调用时位于内存中的一块区域, 其中保存着该函数体运行所需要的信息。这其中涉及到几点重要的考量:

  • 函数拥有明显的生存周期界限。在被调用进入执行第一条函数体指令时开始存在, 在返回调用者时消亡。
  • 函数可以输入参数以改变具体行为, 而具体参数值在运行时确定。
  • 函数可以被多次调用, 比如以循环或递归方式。

综合这些考量, 现代的硬件与操作系统一齐合作, 提供了一种方案, 就是调用框架:

操作系统在进程的地址空间中提供一块区域, 每当一个函数被调用, 就在其中开辟一段区域, 这段区域存放着函数活动过程的重要信息的记录, 当其返回时, 这块区域就被销毁, 这是`活动过程记录`得名的缘由。
函数调用链是一个`先入后出`的结构: A调用B, A的生命流程总比B长, 这块区域也体现了这种结构: 调用链上每个函数的活动记录都以先入后出的方式组织在这个区域中, 所以这块区域被叫做`栈`, 每个活动记录被叫做`栈帧`。
现代的CPU, 几乎都提供了实现这种栈的硬件支持: 有一个`寄存器SP`(stack pointer), 指向当前活动记录的顶端, 还有一个`寄存器BP`(base pointer),指向栈底。

下面就x86架构的调用框架进行分析。

x86的调用框架

下面是一个函数示例代码:

 /* demo.c */
 int demo(int a, int b) {
     long l1 = 1;
     int l2 = 2;
     return l1 + l2 + a + b;
 }

 int main(void) {
     demo(37, 42);
     return 0;
 }

编译成汇编代码, 用-O0选项, 表示不优化, 以生成可以和原始代码逐条对应的目标代码:

$ gcc --version
  gcc (Ubuntu/Linaro 4.7.2-2ubuntu1) 4.7.2
$ gcc -O0 -o demo.s -S demo.c 

结果如下, main函数只取一部分:

原始版                                 简化版   
demo:                                  demo:       
.LFB0:                                     pushl  %ebp
    .cfi_startproc                         movl   %esp, %ebp
    pushl   %ebp                           
    .cfi_def_cfa_offset 8                  subl   $16, %esp
    .cfi_offset 5, -8                      movl   $1, -8(%ebp)
    movl    %esp, %ebp                     movl   $2, -4(%ebp)
    .cfi_def_cfa_register 5                
    subl    $16, %esp                      movl   -4(%ebp), %eax
    movl    $1, -8(%ebp)                   movl   -8(%ebp), %edx
    movl    $2, -4(%ebp)                   addl   %eax, %edx
    movl    -4(%ebp), %eax    ----- >      movl   8(%ebp), %eax
    movl    -8(%ebp), %edx                 
    addl    %eax, %edx                     addl   %eax, %edx
    movl    8(%ebp), %eax                  movl   8(%ebp), %eax
    addl    %eax, %edx                     addl   %eax, %edx
    movl    12(%ebp), %eax                 movl   12(%ebp), %eax
    addl    %edx, %eax                     addl   %edx, %eax
    leave                                  
    .cfi_restore 5                         leave
    .cfi_def_cfa 4, 4                      ret
    ret
    .cfi_endproc

main:
    ...
    movl    $42, 4(%esp) // 把42赋给%esp指向地址再加4字节的位置
    movl    $37, (%esp)
    call    demo

左边为原始版本, 掺杂了许多包含.cfi_*的指令, 这部分放在本文最后讲述。 所以, 现在就上图右边的简化版本来进行讨论。

传参

对于x86架构, 前述的SPBP寄存器分别是espebp。包括x86在内的几乎所有现代的机器, 栈都是从高地址向低地址生长的, 一个例外是HP的PA-RISC机器[1]

main函数中, 有两条mov指令, 明显是执行传参的动作。在调用demo函数的指令call demo执行前, 栈是如此的形态:

 高地址  :          :
    |   |    42    |
    |   +----------+ <--- %esp + 4
    |   |    37    | 
 低地址  +----------+ <--- %esp

注意参数是以从右到左的方式传入的, 至于其原因, 后文再解释。

前序

call demo指令执行后, 就进入了demo函数的活动范围, 在其运行结束后, 控制流程又会返回到main函数的活动范围。这种嵌套结构, 本质地要求要记录下两层结构交汇点的信息, 以便在底一层结构消除后, 返回到上一层。

从CPU的观点来看, 由于它的指令寄存器eip存放的是下一条指令的地址, 这就要求: 在函数最后一条指令执行后, eip中能正确存放函数之后的下一条指令的位置, 术语叫返回地址, 这意味着这个返回地址必须存在某处以方便获取。由于一个CPU执行单元只有一个eip, 而在函数执行过程中, eip会被不断改变, 所以, 返回地址显然不能放在其中。通用的解决方案是: 把返回地址放在调用框架中, 作为其保存信息的一部分。

所以, call demo的效果是: 返回地址会被CPU自动压到栈上, 然后, eip中被装入demo函数第一条指令地址, 由此, 实现了函数调用。此时, 栈的形态是:

 高地址  :          :
    |   |    42    |
    |   +----------+ <--- %esp + 8
    |   |    37    | 
    |   +----------+ <--- %esp + 4
    |   | 返回地址  |
 低地址  +----------+ <--- %esp

demo函数的前两条指令, 执行了很奇怪的操作: 先把旧的ebp压栈, 再把当前的esp赋给ebp, 此时两个寄存器都指向同一位置。 栈形态如下:

 高地址  :          :
    |   |    42    |
    |   +----------+ <--- %esp + 12
    |   |    37    | 
    |   +----------+ <--- %esp + 8
    |   | 返回地址  |
    |   +----------+ <--- %esp + 4
    |   | 旧的ebp   |
 低地址  +----------+ <--- %esp(%ebp) 

这两步操作是个规范化步骤, 叫做前序(prologue), 它有两个作用 :

  • 标记一个新的调用框架。保存前一个函数的调用框架的基址(旧的ebp), 使ebp指向当前函数的调用框架基址。

  • 在函数的执行过程中, 函数的局部变量将会是在返回地址之下的区域开辟空间来存放, 由于ebp是固定的, 可以用它作标杆, 标示参数与局部变量的位置。比如第一个参数位于%ebp + 8, 第二个参数位于%ebp + 12。也正是这个原因, 参数采用从右到左传递, 对实现可变参数有利: 通过%ebp + 8获取第一个参数后, 可从中获知参数个数, 然后, 依次偏移, 即可获取各个参数。

局部变量

上面的汇编代码中, 在前序后, 开始第一条指令, 它把栈顶esp向下推了16字节。这一步的作用是为局部变量开辟空间。本例中只有两个局部变量, 且两者在x86上都分别是4字节, 按理说, 只要开辟8字节的空间即可, 本例中却开辟了16字节。这是因为GCC的栈上默认对齐是16字节[2]

之后, 局部变量也可以由ebp来访问。比如本例中, l1与l2分别由%ebp - 8%ebp - 4来表示。如图:

 高地址  :          :
    |   |    42    |
    |   +----------+ <--- %esp + 12
    |   |    37    | 
    |   +----------+ <--- %esp + 8
    |   | 返回地址  |
    |   +----------+ <--- %esp + 4
    |   | 旧的ebp   |
    |   +----------+ <--- %esp(%ebp) 
    |   |    l2    |
    |   +----------+ <--- %ebp - 4
    |   |    l1    |
 低地址  +----------+ <--- %ebp - 8 

尾声

在函数执行完, 就可以ret指令返回。注意前面有一条leave指令, 它等效于以下两条指令:

movl %ebp, %esp
pop %ebp

这两条指令叫尾声(epilogue), 可以看出, 它与前序相照应。执行完这两条指令后, ebp恢复为旧的ebp, 即指向调用者的基址, esp则指向返回地址。最后的ret指令, 弹出返回地址eip中, 由此, 便完成了从被调用函数到调用函数的返回。

CFI: 调用框架指令

在了解了调用框架之后, 就能明白CFI的作用了。CFI全称是Call Frame Instrctions, 即调用框架指令

CFI提供的调用框架信息, 为实现堆栈回绕(stack unwiding)异常处理(exception handling)提供了方便, 它在汇编指令中插入指令符(directive), 以生成DWARF[3]可用的堆栈回绕信息。这里列有gas(GNU Assembler)支持的CFI指令符

接下来分析上面的例子中出现了几个CFI指令符

在一个汇编函数的开头和结尾, 分别有.cfi_startproc.cfi_endproc标示着函数的起止。被包围的函数将在最终生成的程序的.eh_frame段中包含该函数的CFI记录, 详细请看这里

1 .cfi_def_cfa_offset 8一句。该指令表示: 此处距离CFA地址为8字节。这有两个信息点:

  • CFA(Canonical Frame Address)是标准框架地址, 它被定义为在前一个调用框架中调用当前函数时的栈顶指针。结合本例看, CFA如图所示:

    高地址  :          :
       |   |    42    |
       |   +----------+ <--- %esp + 12
       |   |    37    | 
       |   +----------+ <--- %esp + 8  <--- CFA
       |   | 返回地址  |
       |   +----------+
       |   | 旧的ebp   |
    低地址  +----------+ <--- %esp(%ebp) 
    
  • 至于此处指的是esp寄存器指向的位置。在push %ebp后, esp显然距离CFA为8字节。

2 .cfi_offset 5, -8一句。

把第5号寄存器[4]原先的值保存在距离CFA - 8的位置, 结合上图, 意义明显。

3 .cfi_def_cfa_register 5一句。

该指令是位于movl %esp, %ebp之后。它的意思是: 从这里开始, 使用ebp作为计算CFA的基址寄存器(前面用的是esp)。

4 .cfi_restore 5.cfi_def_cfa 4, 4这两句结合起来看。注意它们位于leave指令之后。

前一句意思是: 现在第5号寄存器恢复到函数开始的样子。第二句意思则是: 现在重新定义CFA, 它的值是第4号寄存器(esp)所指位置加4字节。这两句其实表述的就是尾声指令所做的事。意义亦很明显。

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

[1]: 关于栈生长方向的讨论, 可以看看这个帖子

[2]: 关于GCC的栈对齐值, 查看GCC文档-mpreferred-stack-boundary选项。

[3]: DWARF是一种调试信息格式

[4]: x86的8个通用寄存器依次分别是: eax, ebx, ecx, edx, esp, ebp, esi, edi