内核研究

关键词：FreeBSD Linux POSIX 多核 操作系统 内核

摘要

在最新的计算机技术中，多处理器(Multi Processor)技术方兴未艾。作为计算机系统软件的最基本部分，操作系统(Operation System)对多处理器的支持，是非常重要的。本文对从设计实现角度出发，对主流的类UNIX操作系统支持多处理器的实现进行了初步分析和综述。

目前，类Unix操作系统对多处理器支持较好的，主要有Linux和FreeBSD。下面主要针对这两种操作系统进行阐述。

1.1. 主流类UNIX操作系统对多处理器支持的现状

1.1.1 多处理器系统概述

多处理器系统(Multi-processor System)源起于20世纪50年代的超级计算机。从1999年开始，随着Intel XEON处理器的推出，多处理器系统逐渐在基于x86体系结构的计算机中被使用。但是，当时的主流桌面操作系统对多处理器的支持尚不完善，因此并不能充分发挥多处理器的性能。

在计算机处理器主频进入GHz时代的今天，几何级数增长的计算需求与算术级数增长的处理器主频之间的矛盾，已经日益凸显。由于主频的上升，在同样的半导体工艺下，为了使得数字信号的波形上升沿和下降沿更加锋利，需要提升处理器核心电压以保证稳定。由于数字电路的功耗正比于电压的平方，且随时钟频率线性增加，因此，如果单一地使用提升主频的方法来提升处理器性能，功耗和散热将是严重的瓶颈。在这样的背景下，多核处理器就是处理器厂商克服功耗瓶颈，解决这一矛盾的方案。

操作系统作为体系结构/总线/输入输出硬件之上，对于软件提供系统服务接口的抽象层，对多核处理器的支持，从根本上决定了多核处理器能否发挥出最高效率。

1.1.2 Linux对多处理器的支持

Linux从2.0版本开始支持对称多处理器SMP(Symmetric Multi-Processing)，但仅仅是用一个锁来让各处理器串行地访问系统资源，并不能充分发挥多处理器的并行性能。直到Linux 2.6版本，才引入了实用的SMP系统下任务调度算法，其时间复杂度为常数O(1)。^[1]

为了提高调度效率，Linux可以将某个进程或线程绑定在特定的处理器上，也可以将中断定向至某个特定的处理器上。后者需要特定硬件的支持。^[2]

1.1.3 FreeBSD对多处理器的支持

FreeBSD从3.x版本开始，类似Linux地，使用一个巨型锁(Giant Lock)，来防止多个处理器同时进入内核。从FreeBSD 5.3开始，在内核的网络协议栈部分，支持无互锁地多处理器并行。FreeBSD从6.0开始支持多处理器安全(MP-Safe)的虚拟文件系统(VFS)。在FreeBSD 7.0新增的特性SMPng中，几乎完全去除了Giant Lock，这使得8个以上处理器的SMP系统，其性能几乎与处理器数目线性正相关。^[3][4]

1.2 操作系统支持多处理器的软件接口

为了支持多处理器，操作系统需要提供一系列的接口供上层软件使用。这些接口包括以下几类：

1.2.1 原子操作

在并行编程中，如果一个操作是不可中断的，瞬间完成的，那么，它被称为原子操作^[5]。类Unix系统提供的原子操作接口应当符合POSIX规约。

GNU提供了一系列原子操作，如以下的取-操作系列原语：

__sync_fetch_and_add ()

__sync_fetch_and_sub ()

__sync_fetch_and_or ()

__sync_fetch_and_and ()

__sync_fetch_and_xor ()

__sync_fetch_and_nand ()

这些原语虽然在GLIBC等链接库或头文件中以inline函数的方式实现，但是，它们仍然是操作系统并发同步机制的不可或缺的部分。^[6]

1.2.2 内存屏障

除原子操作外，内存屏障也是一个很重要的为并行编程提供的特性。为了提升执行性能，有的时候CPU会将指令打乱顺序执行，即所谓的乱序执行。对于并发编程中的一些情况，这种乱序执行可能会导致不期望的后果。为了避免这种情况的发生，内存屏障就是一个解决方案。

因为较新的网卡芯片都支持分片发送数据包，可以为一个数据包指定几个位置、长度，网卡会将这些数据组成一个完整的数据发送出去。所以内核引入了skb分片存储的机制，所以一些指针的概念容易混淆。有人说，分片存储对零拷贝很有用处，还没有深究此事。下面是指针和长度的一些解释：

head：skb第一个分片的内存头

end: skb第一个分片的内存尾

tail：skb第一个分片的数据的尾

data：skb第一个分片的数据的头，与当前处理到那一层有关系，IP层处理时在ip头，tcp层处理时在tcp头。

len: data之后的整个长度，包括后续分片。

data_len：在skb分片存储时，第一个分片以后各分片长度的总和.

如果没有分片，data_len = 0

frags怎么存储还没有来及看，我将尽快看了发出来。

所谓交叉编译环境，就是在普通的 PC 机编译生成能在目标机（如 ARM ）上运行的软件。在 GNU 对工具链的定义中，整个交叉编译工具链应该是 GCC + binutils + glibc 。其中 GCC 又包括了预编译器 cpp 、 C 编译器 gcc 、汇编器 as 和链接器 ld 。

交叉编译工具链的获得方式：

（ 1 ）从网上下载已经构建好的交叉编译工具链，比如 ARM 的交叉编译工具链可以从 ftp://ftp.arm.linux.org.uk/pub/linux/arm/toochain/ 下载。注意这些已经做好了的交叉编译工具链往往规定了安装的路径（因为在编译时就制定了路径 --prefix ），可以查看一下 README 文档，通常的路径是“ /usr/local/arm/x.x.x ”，这时需要将工具包解压到这个路径下。

（ 2 ）使用 crosstool 自己构建，下面以构建 ARM 交叉编译工具链为例，说明构建步骤

1.  下载 crosstool-0.43.tar.gz

【 crosstool-0.43.tar.gz 】 http://kegel.com/crosstool/crosstool-0.43.tar.gz

2.  配置 crosstool-0.43

[leo@ crosstool]$ tar zxvf crosstool-0.43.tar.gz

[leo@ crosstool]$ cd crosstool-0.43

[leo @ crosstool-0.43]$ vi demo-arm.sh

修改下面几行，即设置 tarball 的路径、编译结果顶层路径以及需要编译的 gcc 版本。

TARBALLS_DIR=$HOME/Downloads

RESULT_TOP=$HOME/crosstool/arm

eval `cat arm.dat gcc-4.1.1-glibc-2.3.2.dat` sh all.sh --notest

[leo @ crosstool-0.43]$ vi gcc-4.0.0-glibc-2.3.2.dat

BINUTILS_DIR=binutils-2.16.1

GCC_DIR=gcc-4.0.0

GLIBC_DIR=glibc-2.3.2

LINUX_DIR=linux-2.6.15.4

LINUX_SANITIZED_HEADER_DIR=linux-libc-headers-2.6.12.0

GLIBCTHREADS_FILENAME=glibc-linuxthreads-2.3.2

GCC_CORE_DIR=gcc-3.3.6

  将以上所需的 tarball 放到 $(TARBALLS_DIR) 目录下面。

[leo @ crosstool-0.43]$ vi arm.dat

KERNELCONFIG=`pwd`/arm.config

TARGET=arm-linux

TARGET_CFLAGS="-O"

[leo @ crosstool-0.43]$ ./demo-arm.sh

  系统开始编译， 所有使用到的文件 ( 如果没有预先存放在 $(TARBALLS_DIR) 目录下面 ) ，则会在编译的时候自动下载。编译的时间可能需要几个小时。

【说明】红色部分为修改 / 增加部分

TARBALLS_DIR ：是下载的工具源码压缩包的存放目录。

31.
Q: 异常和中断有什么区别？
A: 中断是异常的一种，占用0号异常。中断是异步发生的，一般由硬件事件触发(如某GPIO引脚的电平跳变)，和指令执行阶段无关。而异常是指令触发发生的，也就是同步发生的。

32.
Q: 什么叫“精确异常”？
A: "精确异常" 的原文是precise exception。precise这个词其实有“穷讲究”的意思。在这里指的就是：当异常发生时，已经执行完memory阶段操作的指令均有效，未执行到该阶段的指令，在流水线中一律丢弃。该异常的触发者为该条指令。

33.
Q: 对于TLB miss/Address error这样的异常，实际上为什么不会写入指令中的地址呢？
A: 因为这个时候指令只执行完ALU阶段，还没到Memory，所以被丢弃了。从处理器设计的角度来看，这种非法指令本身也不该生效。

34.
Q: 发生异常的时候，是不是会进入内核态？
A: 是的。当然如果原本就在内核态，那么还是会在内核态。一般来说，操作系统通用的进入内核，是通过一条syscall指令，产生类型为0x08的异常来实现的。

35.
Q: 我想知道，breakpoint, syscall和trap三种异常都是特殊指令触发的，它们有什么区别？
A: 一般说来，syscall指令是用于一般性的系统调用进入内核，类似于x86的调用门。
breakpoint是程序错误处理，例如，mips的除法指令，如果除数为0，会造成不确定的结果。编译器在对除法表达式进行处理的时候，就做一个判断，如果除数为0，则执行指令：break 0x07。如果运行时出现了除以0，那么，break 0x07这条指令会抛出一个breakpoint异常，子类型为0x07——这样，程序员在debug的时候看见这个异常信息，就可以判断，程序中除数出现了0。

20.
Q: CP0是干嘛的？
A: CP0是协处理器0，Co-Processor 0的缩写，MIPS最多可以支持4个协处理器，其中CP0是强制要求实现的，用于处理器的状态控制等。它包括MMU、异常控制、Cache控制等功能。

21.
Q: MIPS的其他协处理器都有什么呢？
A: 这个和具体厂商的实现有关系了。CP1是浮点协处理器，是可选的，CP2和CP3是厂家自定义的。

22.
Q: CP0里面都有哪些寄存器？一般用在什么场合？
A: CP0有32个寄存器，一般操作系统的内核才会接触到它们。主要有MMU类、异常控制类、断点控制类等。

23.
Q: 这几类寄存器各有哪些呢？
A: MMU相关的，有Index,Random, EntryLo0, EntryLo1, Context, EntryHi, MageMask和Wirds几个。具体用途介绍MMU的时候会提到。
异常控制相关的有Status, Cause, EPC, BadVaddr等。
断点控制的有Count, Compare, WatchLo, WatchHi等。
此外，还有PRId，用于确定CPU的类型；
LLAddr, 用于原子锁指令；
Config, 用于配置处理器。

24.
Q: 对CP0寄存器如何访问呢？
A: 有专门的指令访问。32bit读：
mfc0 rs, /*Move from co-processor 0*/
64bit读：
dmfc0 rs, /*Double move from co-processor 0*/
32bit写：
mtc0 rs, /*Move to co-processor 0*/
64bit写：
dmtc0 rs, /*Double move to co-processor 0*/

25.
Q: 对于CP0寄存器，如果只想修改其中的几个bit，该怎样做？
A: 只能先读取到GPR中，修改后写回。
如：
mfc0 t0, SR
nop
and t0, BIT_MASK_ALPHA
or t0, BIT_MASK_BETA
mtc0 t0, SR
nop

26.
Q: 为什么要在mfc和mtc后面插入一个nop指令？
A: 这是为了避免CP0 hazard，简单地说就是执行完mfc或mtc指令之后，有可能要等待一条指令的时间，数据才真正读取或写入到寄存器之中，在这个过程中如果修改相应寄存器会导致错误的结果。

27.
Q: 为什么会有hazard现象？

11.
Q: MIPS的内存空间有多大？
A: 在32-bit模式下是4GB，用户态可以使用的空间是2GB。

12.
Q: 用户态是使用哪部分内存？
A: 虚拟地址0x00000000-0x7fffffff的2GB，叫做user space, mapped & cached.

13.
Q: 什么是用户态，还有哪些别的状态呢？
A: MIPS除了用户态还有内核态，在内核态下可以访问全部资源，但用户态只能访问部分，如CP0、MMU等，用户态是不可以访问的。

14.
Q: 那么，怎样从用户态进入内核态呢？
A: 一般的正常渠道是执行syscall指令。另外还有trap/brackpoint等指令，会引发相应的异常，进入内核态。当然程序错误引起的异常(如非对齐地址访问、未映射的地址访问)也会引发异常，进入内核态。

15.
Q: 在内核态下可以访问多大的内存空间呢？
A: 4GB，但是从0x80000000到0xBFFFFFFF有特殊用途。0x80000000到0x9FFFFFFF，和0xA0000000到0xBFFFFFFF这两段地址，硬件上指向同一段物理地址，0x00000000到0x1fffffff。

16.
Q: 为什么要这样做？
A: 0xA0000000到0xBFFFFFFF是不经过Cache访问的，可以保证在上电时就可用，并且，作为硬件IO寄存器映射地址时，不会被cache 扰乱。MIPS的上电启动地址，0xBFC00000就在这段内存中。而0x80000000到0x9FFFFFFF这段地址是经过Cache映射的，内核代码段和堆栈往往放在这一段内存，以保证访问和执行速度。

17.
Q: 我的硬件工程师将bootrom连接到总线的0xBFC00000地址了，为什么系统不能启动？
A: 0xBFC00000是逻辑地址(程序中的地址)，对应的物理地址(将逻辑分析仪连接在总线上，捕捉到的地址)是0x1FC00000。

18.
Q: 那么，0xC0000000到0xFFFFFFFF的地址空间是干嘛的？
A: 可以作为内核使用的内存，比如kmalloc之类的函数分配使用。这段内存是通过MMU和TLB映射的。

19.

最近问我MIPS体系结构相关问题的人越来越多，在这里小结一下。
一般在职业有段者水平的MIPS体系结构问题，都能在这里找到答案。

1.
Q: MIPS有多少一般用途的寄存器？
A: 32个。

2.
Q: 我在看反汇编代码的时候，看到一些寄存器名叫zero, a1, a2...还有sp, ra这样的名字。为什么给他们起这些名字呢？
A: MIPS的通用寄存器中，按照编译器的通常的约定，某些寄存器是做专门用途的，比如sp就是堆栈指针，ra是函数调用的返回地址等等。当然你也可以不按照这些约定编程，例如用$2存放堆栈指针，$3存放返回地址，但这样的程序，和标准库链接就不能工作了。

3.
Q: 为什么MIPS的SP寄存器也是通用寄存器呢？而且MIPS似乎没有专门的压栈/出栈指令啊。
A: 这是MIPS这样的RISC处理器，同x86为代表的CISC处理器的重大区别之一。RISC没有专门的硬件实现的堆栈寄存器/指令，改为软件实现，在函数入口堆栈指针递减，堆栈向低地址生长，返回处恢复堆栈值，销毁堆栈帧。

4.
Q: MIPS的堆栈用软件实现，那么，MIPS的函数调用开销会更大吗？
A: 这是x86为首的CISC支持者，经常诟病RISC的一点。但是，实际上，我们知道，MIPS使用了4个GPR(一般用途寄存器)来传递前4个Word的函数参数，而x86只有EAX一个寄存器用于传递函数参数。所以，如果函数的参数小于或等于4个word，那就不需要使用栈。我们知道，大多数函数的参数都在4 个word以内。——所以，这一点不比太担心。另外，写太多参数的函数时，建议使用结构体传递这些参数。

5.
Q: MIPS的lh, lb这样的指令，会改变寄存器里的前2个/1个字节，还是后2个/1个字节？
A:一般来说是低位。

6.
Q: MIPS是大端(Big-endian)的，还是小端的(Little-endian)？

to be added

to be added

第14章 桥：基本概念
在讲述桥的第一个章节中，我们将看到：桥是什么，如何使用它，以及桥的使用限制等。我会着重描述透明桥，地址学习，以及转发数据库的使用。在本章中，我会解释为什么桥不能在有环路的拓扑中使用，而在下一章中，我们会看到生成树（STP）协议如何解决这个问题。当然，还有很多其他类型的桥，不过它们很少被用到，而且linux内核也没有实现它们。
本章所使用的网络拓扑并不代表真实的网络环境，它们只是按教学的要求而绘制的演示拓扑。