Tony Bai

如果它不存在，但是你能看见它 -- 它是虚拟的(IBM宣传虚拟内存之用语)。虚拟内存技术是计算机发展史上的一项重要的技术，它帮助应用程序摆脱了“体积”的限制。

记得上大学时，有一本书好像叫做“计算机网络 - 自顶向下”，全名记不太清了。书中从人们接触最多也最熟悉的“应用层”开始讲，一直讲到“物理层”，看完这本书后感觉效果不错。所以按照这种方法我也尝试着自上而下的去学习“虚存”，从我们最熟悉的C库接口调用说起，一直谈到底层的硬件支持设施。

1、初学者的疑惑
初学者往往都会写出以下这样的例子程序来学习malloc和free的使用。
int main() {
        int *p = malloc(10000);
        printf("p's address is 0x%p\n", p);
        free(p);
        return 0;
}
但往往结果让这些初学者们感到疑惑。比如上述的例子，在SUN SPARC 64编译后其输出如下：
p's address is 0x100100dc0
看到这样的结果，初学者往往心里嘀咕，“这台机器物理内存才4G，其地址空间总共才4294967296(dec)，而0x100100dc0转换十进制为4296019392(dec)，这个地址明显已经超出了我的物理内存的限制，这是怎么回事呢？”。其实这里的解释很简单：因为我们看到的都是“虚拟内存地址”。

2、“堆”为何物
malloc是个极其常见的内存分配接口函数，它主要负责运行时在“堆”上为程序动态分配内存空间。我们总是在口头上谈论着“堆”，那么“堆”到底为何物呢？我们已经知道了有“虚拟地址”这个东西的存在，想必“堆”和“虚拟地址”有着千丝万缕的联系^_^。我们来翻看一些经典书籍中的描述。在CS.APP[注1]中的描述是这样的：“堆是进程地址空间中的一段“虚拟地址”空间。在大多数的Unix系统中，堆是映射“二进制零区域(demand-zero)”实现的。其位置在bss段后，其增长方向为高地址方向”。

3、内存映射
前面谈到“demand-zero”这个新名词，那么什么叫“映射到demand-zero”呢？这里蕴含着一个极其重要的概念“内存映射”。内存映射好似一道桥梁，将放在物理磁盘上的对象和一段进程“虚拟地址”空间连接起来。磁盘上的对象，主要指的就是文件，在多数Unix的实现中支持两种文件的内存映射，分别为Regular File和匿名文件(如demand-zero)。映射的过程大致为将文件分成若干“虚拟内存基本单元(页)”大小存于“交换区”，直到CPU指令第一次访问到某个单元时，这个单元才真正被加载到物理内存中。

4、虚拟内存，何方神圣
看到这是不是有些“云里雾里”的感觉亚^_^。其实对于用户进程来说，它是看不到CPU和OS是如何相互配合完成内存管理的。它只认为它面前的是一个这样的情景：“一个完全被我拥有的CPU、一个从拥有M地址空间的物理内存(M = 2的n次方，n为地址总线宽度)...”。这里的用户进程眼中的“物理内存”实际就是“虚拟内存”。虚拟意味着假象，我们知道一个用户进程运行时可能仅仅占用的物理内存的一小部分。看来用户进程被欺骗了。而这个骗局是由操作系统和CPU共同布置的。为了让这个骗局一直维持下去，CPU和OS还是做了很多工作的，究竟有哪些工作呢？我们一一来看看。

1) 交换区(swap)
为了支持虚拟内存，操作系统在物理内存、磁盘之间交换数据的基本单元为“页”。页的大小是固定的，其因操作系统而异。这样一个用户进程在被加载之前首先要被分成若干个“页”，这些页存储在磁盘上。那么是不是进程启动后所有的页都被加载到物理内存中呢？答案是NO。在当前的Unix操作系统中，都有一个叫“交换区”的地方，“交换区”在磁盘上，它存储的是“已分配的虚拟内存页”。又有些糊涂是吧，什么叫已分配的页呢？一个进程虚拟内存页的加载流程大致是这样的：一旦用户进程一虚拟页需要被加载，则操作系统会在“交换区”中为该页分配一个页，一旦CPU访问的虚拟地址落入该页地址空间，则该页才被换入到物理内存中。在这个过程中虚拟页有多个状态，分别如下：
未分配的 － 进程虚拟页未得到加载指令，仍安静的待在磁盘上；
未缓存的 － OS为该进程虚拟页在交换区分配了一个空间，但是该虚拟页还未被引用；
已缓存的 － 该虚拟页被引用，被载入到物理内存中。

2) 换入换出
物理内存容量有限，当物理内存无空间存储新的内存页的时候，就需要将某些内存页从物理内存中移出以为新页腾出空间。这个过程对于那些被移出的页来说，就叫“换出”；相反对于那些新加入到物理内存中的页来说就叫做“换入”。

5、从缓存角度看虚存
现代计算机的存储体系是呈金字塔状的。越接近顶层，速度越快，容量越小，价格越贵；越接近底层，速度越慢，容量越大，价格越低。这样就形成了一个逐级缓存的机制。第K层设备永远是第K+1层设备的缓存。按照这种说法，在早期计算机中，主存是磁盘的缓存，CPU内的高级Cache是主存的缓存。现代计算机基本都支持虚拟内存机制，而虚存页是存储在磁盘上的，虚存页在主存中换入换出。按照缓存的概念，虚存属于容量大，速度慢的第K+1层，而处于第K层的主存就可以看作是虚拟内存的缓存。那么一切缓存理论就都可以应用在虚存和物理内存之间了，比如换入换出算法等。

6、硬件支持
在支持虚拟内存机制的计算机中，CPU都是以虚拟地址形式生成指令地址或者数据地址的，而这个虚拟地址对于物理内存来说是不可见的，那么是谁来屏蔽这个差异的呢？答案是MMU(Memory Management Unit)。MMU负责将CPU发出的虚拟地址转换成相应的物理内存地址。MMU不是孤立工作的，OS为其提供了很好的支持，OS在物理内存中为MMU维护着一张全局的页表，来帮助MMU找到正确地物理内存地址。

7、小结
这里简短而概要的对虚存进行了说明，虚存机制很复杂，不是一句两句能说清楚的，还需要慢慢探索^_^

[注1]
CS.APP - 《computer systems a programmer's perspective》 中文名：《深入理解计算机系统》。

不得不承认上次关于栈桢和栈操作写得有些笼统，这里做一次“补充”，美名其曰：“复习”。

下面的这个例子几乎就能覆盖所有的栈操作相关的内容了。
void dummy()
{
        int     i = 12;
        int     j = 13;
        char    c = 'a';
}

int main()
{
        dummy();
        return 0;
}

下面是利用MDB(注[1])反汇编的代码：
> main::dis
main:                           pushl   %ebp
main+1:                         movl    %esp,%ebp
main+3:                         subl    $8,%esp
main+6:                         andl    $0xf0,%esp
main+9:                         movl    $0,%eax
main+0xe:                       subl    %eax,%esp
main+0x10:                      call    -0x2a          
main+0x15:                      movl    $0,%eax
main+0x1a:                      leave
main+0x1b:                      ret

> dummy::dis
dummy:                          pushl   %ebp
dummy+1:                        movl    %esp,%ebp
dummy+3:                        subl    $0xc,%esp
dummy+6:                        movl    $0xc,-4(%ebp)
dummy+0xd:                      movl    $0xd,-8(%ebp)
dummy+0x14:                     movb    $0x61,-9(%ebp)
dummy+0x18:                     leave
dummy+0x19:                     ret

分析上面的汇编代码我们要解决如下几个方面问题：
1、过程调用的标准模式
我们知道发生过程调用的指令是call，那么call做了些什么呢？上面每个过程的最后都有leave指令，它又作了什么呢？我们不妨来跟踪一个栈帧的形成过程，分析后自然会有答案。

(1) 我们从main + 0x10处开始，这里是一个call指令，此时的活动栈帧为main的栈帧，dummy栈帧尚未形成：
+          + 0xffffffff
|          |
+----------+
|          | main的返回地址，属于main的调用者栈帧范畴
+----------+ ---------------------------
|    A     | main栈帧栈底 <-- %ebp
+----------+
|    B     |
+----------+
|    C     | main栈帧栈顶 <-- %esp
+----------+
|          |
+          + 0x00000000

(2) 调用call指令后，未执行dummy前，此时main的栈帧已经结束，%eip中存放dummy起始指令地址准备执行。
+          + 0xffffffff
|          |
+----------+
|          | main的返回地址，属于main的调用者栈帧范畴
+----------+ ---------------------------
|    A     | main栈帧栈底 <--- %ebp
+----------+
|    B     |
+----------+
|    C     |
+----------+
|          | dummy的返回地址, main栈帧栈顶 <-- %esp
+----------+ ---------------------------
|          |
+          + 0x00000000
可见call首先将main调用的函数(这里是dummy)的返回地址pushl到栈中，形成main栈帧的最后一个部分，然后跳到dummy的起始处。所以call等价于下面两条指令：
pushl %eip  //将下一条指令地址压入栈中
jmp dummy

(3) 形成dummy栈帧
dummy首先将main的栈底保存起来，然后创建自己的栈底。
+          + 0xffffffff
|          |
+----------+
|          | dummy的返回地址，属于main的栈帧范畴
+----------+ ---------------------------
|    D     | dummy栈帧栈底 <-- %ebp，存储着main栈帧栈底
+----------+
|    E     |
+----------+
|    F     | dummy栈帧栈顶 <-- %esp
+----------+ ---------------------------
|          |
+          + 0x00000000

(4) dummy返回
dummy返回时调用的第一条指令leave，该指令相当于如下两条指令：
指令1： movl %ebp %esp // 将%esp置到dummy栈桢首部

该指令执行后状态如下：
+          + 0xffffffff
|          |
+----------+
|          | dummy的返回地址，属于main的栈帧范畴
+----------+ ---------------------------
|    D     | dummy栈帧栈底 <-- %esp <-- %ebp
+----------+
|    E     |
+----------+
|    F     | dummy栈帧栈顶
+----------+ ---------------------------
|          |
+          + 0x00000000

指令2：popl %ebp
该指令执行后状态如下：
+          + 0xffffffff
|          |
+----------+
|          | main的返回地址，属于main的调用者栈帧范畴
+----------+ ----------------------------
|    A     | main栈帧栈底 <--- %ebp
+----------+
|    B     |
+----------+
|    C     |
+----------+
|          | dummy的返回地址，main栈帧栈顶 <-- %esp
+----------+ ---------------------------
|    D     | dummy栈帧栈底
+----------+
|    E     |
+----------+
|    F     | dummy栈帧栈顶
+----------+ ---------------------------
|          |
+          + 0x00000000

dummy返回时调用的第二条指令ret，该指令相当于popl %eip，执行完内存栈的情况如下：
+          + 0xffffffff
|          |
+----------+
|          | main的返回地址，属于main的调用者栈帧范畴
+----------+ ----------------------------
|    A     | main栈帧栈底 <--- %ebp
+----------+
|    B     |
+----------+
|    C     | <-- %esp main栈帧栈顶
+----------+
|          | dummy的返回地址
+----------+ ---------------------------
|    D     | dummy栈帧栈底
+----------+
|    E     |
+----------+
|    F     | dummy栈帧栈顶
+----------+ ---------------------------
|          |
+          + 0x00000000

至此，main的栈桢又再次被恢复了。

经过上面分析，得出过程调用标准模式如下：
pushl %ebp
movl %esp %ebp
...
//过程体
...
leave
ret
其中ret和call对应，而leave则和最开始的那两句对应。

2、访问局部变量
在dummy的汇编码中我们可以清晰的看到对三个局部变量i,j,c的赋值语句：
movl    $0xc,-4(%ebp)
movl    $0xd,-8(%ebp)
movb    $0x61,-9(%ebp)
其三者有一个共同点就是“都是通过对%ebp的偏移来访问局部变量的”。

3、局部变量的分配
两个以上的局部变量的栈上分配涉及到栈内存的对齐问题，dummy的代码足以说明问题。我们在dummy的栈桢中分配了两个整型和一个char型变量，实际需要9个字节。那我们来看看汇编是否给我们只分配了9个字节呢？
movl    %esp,%ebp
subl    $0xc,%esp
movl    $0xc,-4(%ebp)
...
可以看出subl $0xc,%esp一句在内存栈上为我们留出12个字节的空间，在char c的后面又多分了3个字节，以保证对后面的变量的地址访问是对齐的。

4、对异构类型变量的分配和访问
举例如下：
struct test_t {
        int i;
        int j;
        int a[3];
};

void dummy()
{
        struct test_t t;
        t.i = 11;
        t.j = 12;
        t.a[0] = 'a';
        t.a[1] = 'b';
        t.a[2] = 'c';
}

int main()
{
        dummy();
        return 0;
}

> dummy::dis
dummy:                          pushl   %ebp
dummy+1:                        movl    %esp,%ebp
dummy+3:                        subl    $0x28,%esp
dummy+6:                        movl    $0xb,-0x28(%ebp)
dummy+0xd:                      movl    $0xc,-0x24(%ebp)
dummy+0x14:                     movl    $0x61,-0x20(%ebp)
dummy+0x1b:                     movl    $0x62,-0x1c(%ebp)
dummy+0x22:                     movl    $0x63,-0x18(%ebp)
dummy+0x29:                     leave
dummy+0x2a:                     ret

与上面的例子不同的是这次为了存储一个test_t类型结构，栈居然留出了0x28(40d)大小的空间，在t.a[2]与%ebp之间留了0x14(20)个字节空闲。这里的原因不得而知。如果是为了对齐，那么这个代价着实不小。

[注1]
在X86平台的Solaris9上，GDB反汇编使用的语法与我们的稍有差异，而使用Solaris自带的MDB(The Modular Debugger)则和我们的汇编语法保持一致。顺便说一句MDB是一个强大的调试工具，在Sun公司的网站上有其详细的使用说明。

不知道“软件抽象”这个标题能否恰好表达出我想表达出的意思，暂且就起这个名字吧。随着工作经验的增加，对软件开发所涉及的技术知识体系的理解也渐渐地清晰（起码自己是这么感觉的^_^），思考了若干时间后，拿出来给自己一个和大家交流的机会。

1、起源
这个想法起源于一次项目方案讨论例会，会上我们的项目遇到了“存储资源瓶颈”，遂有同事提出一个类似“数据中心”的方案，但考虑到部门目前没有相关经验和数据供参考，大家就否定了这一想法，会上我也并不赞同这一方案。会后坐在电脑前仔细考量了一下，又想起以前部门一弟兄曾提出的“将业务和通讯协议分离”的想法，感觉这是一个很有“前途”的方案。考虑到部门目前的业务模式和软件类别，将“协议和存储”从各个系统中分离出来将是一个很“革命性”的做法。会后又和两位要好的“战友”探讨过这个问题，他们也一致赞同。虽然我们的想法是美好的，但是毕竟我们不是领导，我们也只能在私下“愤青”一把。

2、观点
“软件是存储、通信、UI（user interface）和业务逻辑的紧密结合体。”
a) 在软件的生命周期中，较稳定的是存储和通信，最易变化的是业务逻辑；
b) 在软件的层次上，存储和通信一般处于底层，而业务逻辑处于最上层；
c) 不同类别的软件，其侧重点有所不同。如对于应用程序，其关注点应该在“业务逻辑”。

这些观点也许并不是什么新颖的，你可能在很多资料中都曾见到过类似的字眼儿。我觉得上面的观点有这么三点作用（现在我想到了三点^_^）。

a) 指导你的学习，制定你自己的学习计划。

我自己也回顾了一下我入司后的学习历程，其实也都是围绕着这个观点。下面简单列举几个每个方面涉及的知识领域：
存储 -- 虚拟存储系统(自认为是存储技术的一次标志性技术，在《深入理解计算机系统》一书中有很好的阐述)、文件IO等。
通信 -- 内部通信包括进程IPC、线程管理等，这种通信技术较为成熟；外部通信包括TCP/IP、Socket等。
业务逻辑 -- 现在很多建模技术及软件过程都是围绕和针对业务逻辑的，如UML、RUP和敏捷过程等。
UI -- 这个并不是很熟悉，但我相信在这方面也有太多的知识和技巧了。

b) 理解软件的发展
软件技术发展依旧那么迅速，我们可以从上述四个方面来理解：
存储 -- 如微软即将在下一代操作系统中推出的新一代的文件系统、新一代数据库技术等；
通讯 -- 内部通讯技术经过几十年的发展已经趋于成熟，但是外部通信技术还在突飞猛进的发展，如分布式、IPV6、VOIP、及时通讯技术以及在更火爆的无线通讯领域的各种技术等等；
业务逻辑 -- 如Ivar最近提出的“主动软件”及SMART过程等；
UI -- 我关注的不多，不举例了。

c) 思考你的设计
就像我们的项目，更加清晰的设计就是将存储、通信方面都都分离出来作为底层的支撑系统。对应这四个方面思考你的设计，不知道你是否已经有了些许想法呢。

3、小结
写到这也许起名为“软件抽象”有些言过其实。但一时也想不出什么更加“地道贴切”的名字，就暂用它撑撑门面吧！^_^。

入司后连续做过几个项目。最近在做一个新的项目的设计的时候，突然想到是不是该把以前项目中一些好的设计想法应用到新的项目中，并且尽量减少在新的项目中遗留以前的不好的设计呢？那么以前的项目中哪些是值得我去借鉴，哪些又是应该去避免的呢？真的很遗憾，自己并没有系统的反思和总结过，这就是我写下这篇Blog的直接起因。

一直在Unix平台下做设计和开发，所以下面谈的内容可能都有些局限性。作为设计原则本身，某些可能具有很强的通用性，而还有一些可能局限于某个平台、某个领域。这里我想到了以下几个方面(仅仅提出一些观点，而没有太关注具体的解决方法，给大家一个想象的空间^_^)：

1、扩展
扩展性在这里被我分为“性能扩展”和“功能扩展”两类。
1) 性能扩展
作为电信级系统，对其的性能要求肯定不会低。那么如何做性能扩展呢？有两种方法：提高单点处理能力（垂直扩展）和平行扩展。
垂直扩展 - 简单说就是一个进程不够，我再加一个进程做同样的处理。问题出现了：如何做进程间的通讯？使用共享内存（最快的IPC）还是其他IPC方式呢？还是一个权衡的过程。
水平扩展 - 简单说就是一台机器不够，我再加一台机器。咱们也时髦一把，弄个分布式。问题出现了：如何做分布式节点之间的通讯？目前流行soap，而且又有开源包，如gsoap，其唯一缺点也是致命缺点就是慢。所以我想大部分开发商还是使用自己的内部协议。另外分布式与钱还是挂钩的。分布式意味着需要更多的机器平台来承载我们的系统，机器是钱，对机器的服务也是钱。看来这也是大家都喜欢分布式的原因。

2) 功能扩展：
做电信软件，其面对的最大的问题可能就是“用户需求变化多端”这个问题，更有甚者就是“用户并不知道需求，需要你去引导用户”，这样就会给项目带来较大的风险。如何能在设计这一层来规避风险或者减小风险带来的损失呢？尽量划分清易变化的需求和较稳定的需求，采用面向接口编程的形式（记住面向接口并不是Java等语言的专利）。比如以动态链接的方式（有点plugin的意思）实现系统中那些易变化的功能模块。一旦用户需求改变，我们需要修改的只是一个动态链接库（即替换一个plugin）。

2、隔离
隔离是为了可测试和好维护。其缺点是可能带来性能上的缺失。
1) 可测试性
可测试性在当前可是衡量一个软件设计好坏的重要标准。大型程序，模块众多。首先应该想到的就是怎么做集成测试？集成测试可能需要把一个模块单独拿出来运行。这就需要我们在设计的时候使模块间的耦合性尽量小，比如我们可以采用文件或者MQ的方式来解除模块间的耦合。这样一旦模块A开发完毕，产生其输入数据的模块B还未完成，我们就可以使用模拟器来产生输入数据即可(生成文件或者手工写数据到MQ中)。

2) 维护性
软件脱离不了服务，服务也是钱，也算在软件的成本中。如果一个软件的维护成本过高，完全可能会使该项目赔本。可维护性高的一个很重要的指标就是能快速定位问题所在。隔离模块可以提高定位错误的效率。因为我们可以将某一模块从系统中拿出来，单独测试定位问题，一个一个的排查，而不是大海捞针般的在系统中胡乱撞。

隔离还有一点很重要，就是尽可能的让每个模块能单独可运行（并不一定是独立程序），而无须依赖其他模块。

3、灵活
在我看来体现一个系统是否灵活，最重要的一点就是其配置文件设计的灵活性和合理性。

1) 配置文件格式
现在Java世界的配置文件基本已经被xml格式所垄断，而在C这边仍旧使用着传统的“key - value”格式。xml的多级配置是传统“key - value”不能比拟的。
例如：
<!-- in xml format -->
<mqlist>
    <mq name="testmq1"/>
    <mq name="testmq2"/>
</mqlist>

# in "key - value" format
[mqlist]
name = testmq1;testmq2

在传统配置文件中我们需要对name字串进行解析才能得到各个mq的名字。而且大多数读"key - value"的程序可能都有对value值长度的限制，也就是说我们不能无限制的增加mq的个数。在xml中不存在这样的问题。况且现在像expat这样的开源包对xml的支持也很好。建议在以后设计时向xml格式配置文件转移。

2) 配置方式
一个灵活的配置，会给系统维护和变更带来极大的方便。甚至可以通过修改配置来满足用户新的需求。另外集中配置和分散配置也是需要设计者考虑的问题。比如将整个系统做成一个大程序，并做集中配置，那么除非有动态配置更新程序，否则一旦配置更改，就需要重启整个系统。相反如果系统是一个小程序的集合，采取分散配置，这样针对每个小程序的配置修改只会影响到其自己，只需重启相应的程序即可。

3) 配置粒度
很难用定义解释这个问题，举个例子可能会有更好理解。比如按照一定的配置格式写一个文件(由若干行记录组成)。对文件格式的配置可能如下：
粒度粗的配置
<record alignment="0" padding="0" ...>
                <field name="id" ... />
                <field name="type" ... />
</record>

粒度细的配置
<record ...>
                <field name="id" alignment="0" padding="0" ... />
                <field name="type" alignment="1" padding="0" ... />
</record>
可以看出“粒度粗的配置”只支持到区分记录间的对齐方式和填充字节的差异性；而“粒度细的配置”则支持到区分字段间的对齐方式和填充字节的差异性。一旦需求发生变化，要求每条记录的字段间的alignment和padding可以不同的话，那么“粒度粗的配置”则不能满足需求，而“粒度细的配置”仅仅通过改变配置即可满足这个需求。从这个例子可以看出配置粒度粗细选择某种程度上可能会影响程序的扩展性，一般来说配置粒度细的程序扩展性要更好些。

4、层次
做设计一定要考虑层次，这里体会不多也就不多说了，总之有一点就是“在做设计的时候心中一定要有层次的概念”。

5、小结
给我的感觉：设计是一门权衡的艺术，相信通过上面的一些文字也可以不充分的论证这一点。本文仅仅是我在做过一些项目后的一些体会，并没有很牢固的理论基础。自己也正在计划着读一些关于架构设计方面的书，来提高一下自己的理论水平^_^。

在sina“北京奥运吉祥物”发布专题中，发现吉祥物评审委员会有位评委是个童话故事家，叫“郑渊洁”，这个名字听起来很熟悉，在网上搜索后才知道，原来小时侯最喜欢看的《舒克和贝塔》就出自这位作家之手，心中顿时涌动着对其之敬仰之情，遂下载了一本“待补充”的《郑渊洁童话全集》开始拜读。

虽已工作一载有余，但仍自认为“童心未泯”，暂且忘记工作的压力、生活上的不如意，进入郑叔叔的童话世界中，这简直就是一种享受。由于郑叔叔的童话作品数量庞大，遂只挑选了郑渊洁风靡童话世界的几部脍炙人口之作如《舒克和贝塔》、《大灰狼罗克》以及《皮皮鲁和鲁西西》系列。

童话，原本就是为孩子们准备的丰盛大餐，其特点是故事情节简单，文字通俗易懂并与蕴含着无穷的快乐元素和教育意义。对于我这样的成年选手，读起童话来自然效率很高。

《舒克与贝塔》故事情节较连续，篇幅也不小，而且童话中的主角是两只拥有活泼可爱的形象和正直无畏的品格的小老鼠，在我看来，舒克和贝塔在中国小朋友（和我同龄的80年代的那几代）的心目中的地位丝毫不亚于美国的那个米奇老鼠。看了《郑渊洁童话全集》中的“舒克与贝塔”后感觉自己小时侯好像并没有看全整部童话，这次正好弥补一下这个缺憾。

对《大灰狼罗克》这部作品，我并不是非常的熟悉，隐隐约约好像记得这部作品是在前几年被搬上了荧屏的。罗克是一名“热心肠”的好大灰狼，在第一集中就看得出来。《大灰狼罗克》这部作品章节相对独立，而且其照比《舒克与贝塔》显得渺小的多。读完罗克的故事感觉有些情节是影射某些社会现实的，这样自然少了些童话故事的色彩，总体感觉不如《舒克与贝塔》。

至于《皮皮鲁和鲁西西》系列，情节趋于科幻，也许是作者在创作的那个年代受到了当时“科幻”风的影响。记得小时候有一段时间荧幕上连续的上演《恐龙特急克塞号》、《变形金刚》、《霹雳贝贝》、《小龙人》等经典科幻作品。皮皮鲁身上有着现在孩子身上叛逆的性格，而且陶气、聪明和果敢，我想也正是这些才可以吸引儿童们的眼球，皮皮鲁和鲁西西系列是相对较晚的作品，所以自己关注的比较少。

一口气说了这么一丁儿点自己内心的童话心声:)，感觉孩提时代的我们比现在的孩子们要幸福，有那么多经典的影视作品供我们选择去看，现在的儿童只能饱受那些垃圾作品的摧残，可怜！呵呵一家之言而已！^_^

结构化程序的一个最基本的单元就是“函数”或者叫“过程”。在汇编这一层自然也相应的有支持这些概念的指令操作，如栈操作和栈帧的概念。

首先这里要为“打开汇编之门”那篇blog补充一点的是：汇编语言是与机器相关，这里的一切都是基于IA-32机器平台的。

1、寻址方式
我们已经知道在操作数表示中有一种是用来指示内存地址的内容的，在GNU Assembly中指示内存地址有多种方式，这些方式被统称“寻址方式”。通用的寻址格式为：“Imm(Eb, Ei, s)”[1]。解释一下：该表达式的计算方式为Imm + R[Eb] + R[Ei] * s，这一串的结果是什么呢？是一个存储器的地址，操作指令通过该操作数表达式计算出来的内存地址来访问内存。

由通用形式演化几种常见特殊形式如下：
1) Imm - 注意与$Imm区别，后者为立即数，而前者是以立即数形式承载的一个内存地址，这种方式叫绝对寻址；
2) (Ex) - 注意与Ex区别，后者为寄存器内容，而前者是以寄存器内容形式承载的一个内存地址，这种方式叫间接寻址；
3) Imm(Eb) - 其表示结果是内存地址为Imm + R[Eb]；
4) (Eb, Ei) - 其表示结果是内存地址为R[Eb] + R[Ei]；
5) Imm((Eb, Ei) - 其表示结果是内存地址为Imm + R[Eb] + R[Ei]。

2、寄存器使用
在“打开汇编之门”中曾经提过虽然寄存器的专用性已经降低，但是某些寄存器还是有其专用场合的。GNU为我们制定了一个寄存器使用规则，规则规定：“%eax、%ecx和%edx是由调用者负责存储的，而%ebx、%ebi和%esi则由被调用者保护，而%esp和%ebp都是栈操作专用的”。

3、栈操作
栈，实际上是一块儿专用的内存区域，每个进程地址空间都有其专有的栈区。地球人都知道关于栈有两种操作：Push和Pop。相应的GNU Assembly分别定义了“pushl S”和“popl D”分别来完成压栈和出栈操作。每个操作都包含两个步骤：移动栈顶指针和数据传送。
pushl S <=> R[%esp] <-- R[%esp] - 4 ；M[R[%esp]]<-- S
popl D <=>  D <-- M[R[%esp]]；R[%esp] <-- R[%esp] + 4

4、栈帧的形成
提到函数或者过程调用就不能离开栈操作。而每个函数或者过程调用也都离不开一个叫“栈帧”的概念。栈是用来传递参数、保存返回结果等作用的，而栈帧则是1对1映射到某个过程调用的。栈帧由%ebp来标识。我们来看看一个例子，通过该例子看看栈帧里到底有些什么东西？
void callee(int x, int y) {
 x = 1;
 y = 2;
}

void caller(int m, int n) {
 callee(m, n);
}

翻译为汇编代码为：
_callee:
 pushl %ebp   //保存调用者的栈帧地址
 movl %esp, %ebp  //初始化callee栈帧地址
 movl $1, 8(%ebp)  //获取参数x信息
 movl $2, 12(%ebp)  //获取参数y信息
 popl %ebp
 ret
... ...
... ...
_caller:
 pushl %ebp   //保存调用者的栈帧地址
 movl %esp, %ebp  //初始化caller栈帧地址
 subl $8, %esp  
 movl 12(%ebp), %eax  
 movl %eax, 4(%esp)
 movl 8(%ebp), %eax
 movl %eax, (%esp)
 call _callee
 leave
 ret
看看callee的汇编码：进入callee后首先保存其调用者caller的栈帧地址，然后读取其调用者caller栈帧中的参数信息进行计算。可以看出一个过程的栈帧中起码包括其上一个栈帧的起始地址，然后是一些参数信息，按照CS.APP说法，栈帧在存储参数信息之前还有可能保存一些本地变量或临时变量等。在每个过程的栈帧的结尾处都记录着过程返回地址，这个返回地址是由call执行时自动加入的。callee都是通过%ebp +/- 偏移量来获取参数信息的。用下面的图可以小结一下栈帧的模样(起始：%ebp所指的字节--> 终止：返回地址所在字节)：

+              +
 |               |
+----------+
| old %ebp | <--- %ebp
+----------+
| 本地变量 |
+----------+
|   参数n  |
+----------+
|   参数...|
+----------+
|   参数1  |
+----------+
| 返回地址 |
+----------+
|     ...        |
|                |<-- %esp

[注1]
这里采用了CS.APP中的表示方法，Eb表示基址寄存器，Ei表示变址寄存器，s为伸缩因子。我们使用R来表示引用某个寄存器的值，使用M来表示引用某内存地址。

工作这么长时间，一直在C语言这一层面上钻研和打拼，日积月累，很多关于C的疑惑在书本和资料中都难以找到答案。程序员是追求完美的一个种群，其头脑中哪怕是存在一点点的思维黑洞都会让其坐卧不宁。不久前在itput论坛上偶得《Computer Systems A Programmer's Perspective》（以下称CS.APP）这本经典好书，遂连夜拜读以求解惑。虽说书中没有能正面的回答我的一些疑惑，但是它却为我指明了一条通向“无惑”之路 -- 这就是打开汇编之门。

汇编语言是一门非常接近机器语言的语言，其语句与机器指令之间的对应关系更加简单和清晰。打开汇编之门不仅仅能解除高级语言给你带来的疑惑，它更能让你更加的理解现代计算机的运行体系，还有一点更加重要的是它给你带来的是一种自信的感觉，减少了你在高处摇摇欲坠的恐惧，响应了侯捷老师的“勿在浮沙筑高台”的号召。现在学习汇编的目的已与以前大大不同了。正如CS.APP中所说那样“程序员学习汇编的需求随着时间的推移也发生了变化，开始时是要求程序员能直接用汇编编写程序，现在则是要求能够阅读和理解优化编译器产生的代码”。能阅读和理解，这也恰恰是我的需求和目标。

在大学时接触过汇编，主要是Microsoft MASM宏汇编，不过那时的认识高度不够加上态度不端正，错失了一个很好的学习机会。现在绝大部分时间是使用GCC在Unix系列平台上工作，选择汇编语言当然是GNU汇编了，恰好CS.APP中使用的也是GNU的汇编语法。由于学习汇编的主要目的还是“解惑”，所以形式上多是以C代码和汇编代码的比较。

1、汇编让你看到更多
随着你使用的语言的层次的提高，你眼中的计算机将会越来越模糊，你的关注点也越来越远离语言本身而靠近另一端“问题域”，比如通过JAVA，你更多看到的是其虚拟机，而看不到真实的计算机；通过C，你看到的也仅仅是内存一层；到了汇编语言，你就可以深入到寄存器一层自由发挥了。汇编程序员眼里的“独特风景”包括：
a) “程序计数器(%eip)” -- 一个特殊寄存器，其中永远存储下一条将要执行的指令的地址；
b) 整数寄存器 -- 共8个，分别是%eax、%ebx、%ecx、%edx、%esi、%ebi、%esp和%ebp，它们可以存整数数据，可以存地址，也可以记录程序状态等。早期每个寄存器都有其特殊的用途，现在由于像linux这样的平台多采用“平面寻址[1]”，寄存器的特殊性已经不那么明显了。
c) 条件标志寄存器 -- 保存最近执行的算术指令的状态信息，用来实现控制流中的条件变化。
d) 浮点数寄存器 -- 顾名思义，用来存放浮点数。
虽说寄存器的特殊性程度已经弱化，但是实际上每个编译器在使用这些寄存器时还是遵循一定的规则的，以后再说。

2、初窥汇编
下面是一个简单的C函数：
void dummy() {
 int a = 1234;
 int b = a;
}
我们使用gcc加-S选项将之转换成汇编代码如下(省略部分内容)：
 movl $1234, -4(%ebp)
 movl -4(%ebp), %eax
 movl %eax, -8(%ebp)
看了一眼又一眼，还是看不懂，只是发现些熟悉的内容，因为上面提过如%ebp、%eax等。这只是个引子，让我们感性的认识一下汇编的“容貌”。我们一点点地来看。咋看一眼汇编代码长得似乎很相似，没错，汇编代码就是一条一条的“指令+操作数”的语句的集合。汇编指令是固定的，每条指令都有其固定的用途，而操作数表示则有多种类型。

1) 操作数表示
大部分汇编指令都有一个或多个操作数，包括指令操作中的源和目的。一条标准的指令格式大致是这样的：“指令 + 源操作数 + 目的操作数”，其中源操作数可以是立即数、从寄存器中读出的数或从内存中读出的数；而目的操作数则可以是寄存器或内存。按这么一分类，操作数就大致有三种：
a) 立即数表示法 -- 如“movl $1234, -4(%ebp)”中的“$1234”，就是一个立即数作为操作数，按照GNU汇编语法，立即数表示为“$+整数”。立即数常用来表示代码中的一些常数，如上例中的“$1234”。注意一点的是立即数不能作为目的操作数。
b) 寄存器表示法 -- 这种比较简单，它就是表示寄存器之内容。如上面的“movl -4(%ebp), %eax”中的%eax就是使用寄存器表示法作源操作数，而“movl %eax, -8(%ebp)”中的%eax则是使用寄存器表示法作目的操作数。
c) 内存引用表示法 -- 计算出的该操作数的值表示的是相应的内存地址。汇编指令根据这个内存地址访问相应的内存位置。如上例“movl -4(%ebp), %eax”中的“-4(%ebp)”,其表示的内存地址为(%ebp寄存器中的内容-4)得到的值。

2) 数据传送指令
汇编语言中最最常用的指令 -- 数据传送指令，也是我们接触的第一种类别的汇编指令。其指令的格式为：“mov 源操作数, 目的操作数”。
mov系列支持从最小一个字节到最大双字的访问与传送。其中movb用来传送一字节信息，movw用来传送二字节，即一个字的信息，movl用来传送双字信息。这些不详说了。除此以外mov系列还提供两个带位扩展的指令movsbl和movzbl，我们举个例子来说明一下这两个特殊指令的作用何在：

a) movzbl指令
void dummy1() {
 unsigned char c = 'a';
 unsigned int a = c;
}
其对应的GNU汇编为(省略部分内容)：
 movb $97, -1(%ebp)   //'a'的ASCII码为97
 movzbl -1(%ebp), %eax
 movl %eax, -8(%ebp)
说明：在dummy1函数中“unsigned int a = c”语句完成的是一个从unsigned char到unsigned int的赋值操作，由于int的类型长度大于char类型长度，所以实际是将一个字节的内容拷贝到一个可以容纳4个字节的地方，这样的话需要对源数据进行一下扩展，即填充高位的3个字节。

如何填充呢？由于变量a和c都为无符号整型，所以只需要填充0即可。而movzbl就是干这个活的。movzbl指令负责拷贝一个字节，并用0填充其目的操作数中的其余各位，这种扩展方式叫“零扩展”。

b) movsbl指令
void dummy2() {
 signed char c = 'a';
 unsigned int a = c;
}

其对应的GNU汇编为(省略部分内容)：
 movb $97, -1(%ebp)   //'a'的ASCII码为97
 movsbl -1(%ebp), %eax
 movl %eax, -8(%ebp)
说明：在dummy2函数中“unsigned int a = c”语句完成的是一个从signed char到unsigned int的赋值操作，由于int的类型长度大于char类型长度，所以实际是将一个字节的内容拷贝到一个可以容纳4个字节的地方，这样的话需要对源数据进行一下扩展，即填充高位的3个字节。如何填充呢？GNU汇编告诉我们它使用了变量c的最高位来填充其余的3个字节。movsbl指令负责拷贝一个字节，并用源操作数的最高位填充其目的操作数中的其余各位，这种扩展方式叫“符号扩展”。实际上dummy2中变量a还是保留了变量c的符号位的，起码GCC是这么做的。

c) 在CS.APP中pushl和popl也别归入“数据传送指令”类别，但对于刚入门选手这两个指令还是稍显复杂，在以后谈到“procedure”时再细说。

3、小结
已经迈出了踏入汇编之门的第一步，汇编的确让我眼前敞亮了许多，看得多了，知道得多了，疑惑也就少了。

4、参考资料
1) 《Computer Systems A Programmer's Perspective》

[注1]
平面寻址：简单的将存储器看成一个大的、按照字节寻址的数组。不区分类型、符号、地址还是整数。注意汇编程序员看到也是进程空间的虚拟地址。

在Java、C++和C#等高级语言的单元测试正进行的如火如荼的时候，C好像做了看客，冷清的躲在了一个不起眼的角落里。C并不是没有单元测试工具，像Check和CUnit这样的工具也很有名气，只是和大名鼎鼎的JUnit比起来，还是显得有些英雄气短。很多大型的C项目，如APR等都没有使用像Check、CUnit这样通用的单元测试框架，而是另起炉灶自己编写。其实编写一个仅能满足单个项目需要的C单元测试工具包并非难事。在部分参考APR的ABTS的前提下，我们也来设计一套自己的简单的C语言单元测试包。

鉴于减少复杂性，我们的目标仅仅是设计和实现一套能在单进程、单线程下工作良好的C单元测试包，我们暂且将之命名为CUT - C Unit test Toolkit。
1、CUT涉及的术语解释
曾经接触过多个有名的单元测试框架如JUnit、CppUnit、TestNG等，它们在对单元测试某些概念的理解上并不是全都一样的。这里我们也有我们自己的定义。
a) 一个逻辑unit test包含至少一个或者多个suite;
b) 一个suite包含至少0或者多个test case;
c) 每个test case中至少包含1个或者多个“断言类”语句。

2、CUT预告片
其实每设计一个程序之前自己都会考虑该提供给用户怎样的东东呢？下面是应该是CUT的经典用法：
cut_ts_t *suite = NULL;

CUT_TEST_BEGIN("classic usage of CUT");

CUT_TS_INIT(suite); 
CUT_TC_ADD(suite, "test case: tc_add", tc_add);
CUT_TC_ADD(suite, "test case: tc_sub", tc_sub);
CUT_TS_ADD(suite, my_setup, my_teardown);

CUT_TEST_RUN();

CUT_TEST_REPORT();

CUT_TEST_END();

3、CUT的组织结构
从上面的经典用法中也可以看出我们的CUT的组织是这样的：
            Test
             |
             |
        +-------------+
       TS-1    ...  TS-N
        |                |
        |                |
   +-------+ ...   +--------+
  TC-1   TC-N     TC-1     TC-N
其中：TS - Test Suite，TC - Test Case

4、CUT接口设计与实现
在“预告片”中我们已经暴露了大部分CUT的重要接口，在下面我们将伴随着实现逐一说明。另外在CUT的实现中我们使用了APR RING技术,不了解APR RING的可以参见我的上一篇Blog“APR分析-环篇”。
1) 主要数据结构
typedef void (*tc_func)(cut_tc_t *tc); /* Test Case标准原型函数指针，所有的Test Case都应该符合这个原型 */
typedef void (*fixture_func)();  /* 用于suite环境建立和拆除的func原型 */

/* Test Case数据结构 */
typedef struct cut_tc_t {
        APR_RING_ENTRY(cut_tc_t)        link;
        char                            name[CUT_MAX_STR_LEN+1];
        tc_func                         func;
        int                             failed;
} cut_tc_t;
typedef APR_RING_HEAD(cut_tc_head_t, cut_tc_t) cut_tc_head_t;

/* Test Suite数据结构 */
typedef struct cut_ts_t {
        APR_RING_ENTRY(cut_ts_t)        link;
        cut_tc_head_t                   tc_head;
        int                             failed; /* 失败用例总数 */
        int                             ran; /* 运行用例总数 */
        fixture_func                    sf; /* setup func */
        fixture_func                    tf; /* teardown func */
} cut_ts_t;
typedef APR_RING_HEAD(cut_ts_head_t, cut_ts_t) cut_ts_head_t;

/* 逻辑单元测试数据结构 */
typedef struct cut_test_t {
        char                            name[CUT_MAX_STR_LEN+1];
        cut_ts_head_t                   ts_head;
} cut_test_t;

2) CUT_TEST_BEGIN和CUT_TEST_END
这两者分别是一个逻辑Test的开始与结束。我们在CUT_TEST_BEGIN建立好我们的内部数据结构，其唯一宏参数用来加强可读性，在CUT_TEST_END中释放在测试过程中获取的系统资源。其实现如下：
#define CUT_TEST_BEGIN(desc) \
        cut_test_t *_cut_test = NULL; \
        _cut_test = malloc(sizeof(cut_test_t)); \
        if (_cut_test == NULL) { \
                return errno; \
        } \
        memset(_cut_test, 0, sizeof(cut_test_t)); \
        APR_RING_INIT(&(_cut_test->ts_head), cut_ts_t, link); \
        strncpy(_cut_test->name, desc, CUT_MAX_STR_LEN)

#define CUT_TEST_END() do { \
  /* 这里遍历Ring，释放其他相关内存,这里限于篇幅未写出 */
                if (_cut_test != NULL) { \
                        free(_cut_test); \
                } \
        } while(0)

3) CUT_TS_ADD和CUT_TC_ADD
前者负责向一逻辑单元测试中添加Test Suite，后者则负责向一个Test Suite中添加测试用例。在CUT中，每个Test Suite依赖两个Fixture Function- setup和teardown。setup用于建立测试环境，比如打开某文件，获得文件句柄供该Test Suite中的若干Test Case使用；而teardown则用来做后处理，释放setup以及在众多Test Case执行时分配的资源，比如上面关闭提到的文件句柄。

在实现CUT的Test Suite时，实际上加了一个对用户使用的限制，那就是CUT负责管理Test Suite的内存分配，说限制也好我觉得倒是给用户提供了一种方便。这两个宏的实现如下：
#define CUT_TEST_SUITE_INIT(suite) do { \
                if (suite == NULL) { \
                        suite = malloc(sizeof(cut_ts_t)); \
                        if (suite == NULL) { \
                                return errno; \
                        } \
                } \
                memset(suite, 0, sizeof(cut_ts_t)); \
                APR_RING_INIT(&(suite->tc_head), cut_tc_t, link); \
                suite->ran = 0; \
                suite->failed = 0; \
        } while(0)

#define CUT_TS_ADD(suite, f1, f2) do { \
                APR_RING_ELEM_INIT(suite, link); \
                suite->sf = f1; \
                suite->tf = f2; \
                APR_RING_INSERT_TAIL(&(_cut_test->ts_head), suite, cut_ts_t, link); \               
        } while(0)

#define CUT_TC_ADD(suite, desc, f1) do { \
                cut_tc_t *tc = NULL; \
                tc = malloc(sizeof(cut_tc_t)); \
                if (tc == NULL) { \
                        return errno; \
                } \
                memset(tc, 0, sizeof(cut_tc_t)); \
                strncpy(tc->name, desc, CUT_MAX_STR_LEN); \
                tc->func = f1; \
                APR_RING_ELEM_INIT(tc, link); \
                APR_RING_INSERT_TAIL(&(suite->tc_head), tc, cut_tc_t, link); \
        } while(0)

4) CUT_TEST_RUN和CUT_TEST_REPORT
这两个宏的作用分别是运行所有逻辑单元测试中的测试用例和报告测试情况，在这里CUT_TEST_REPORT输出形式较为简单，只是打印出此次单元测试运行用例总数和失败的用例数。当然要丰富其输出形式，让用户更快更早定位哪个测试用例失败也并不难，只需对CUT的实现稍作修改即可，这里仅是抛砖引玉。具体可参见成熟的工具的输出形式，如CUnit等。
#define CUT_TEST_RUN() do { \
                cut_ts_t *ts = NULL; \
                cut_tc_t *tc = NULL; \
                APR_RING_TRAVERSE(ts, &(_cut_test->ts_head), cut_ts_t, link) { \
                        if (ts != NULL) { \
                                if (ts->sf != NULL) { \
                                        ts->sf(); \ /* execute setup func */
                                } \
                                APR_RING_TRAVERSE(tc, &(ts->tc_head), cut_tc_t, link) { \
                                        if (tc != NULL) { \
                                APR_RING_TRAVERSE(tc, &(ts->tc_head), cut_tc_t, link) { \
                                        if (tc != NULL) { \
                                                tc->func(tc); \
                                        } \
                                } \
                                if (ts->tf != NULL) { \
                                        ts->tf(); \ /* execute teardown func */
                                } \
                        } \
                } \
        } while(0)

#define CUT_TEST_REPORT() do { \
                int ran = 0; \
                int failed = 0; \
                cut_ts_t *ts = NULL; \
                cut_tc_t *tc = NULL; \
                APR_RING_TRAVERSE(ts, &(_cut_test->ts_head), cut_ts_t, link) { \
                        if (ts != NULL) { \
                                APR_RING_TRAVERSE(tc, &(ts->tc_head), cut_tc_t, link) { \
                                        if (tc != NULL) { \
                                                ran++; \
                                                failed += tc->failed; \
                                        } \
                                } \
                        } \
                } \
                printf("total tc is %d, and failed tc is %d\n", ran, failed); \
        } while(0)

5) 断言集合
评价一个单元测试工具好坏的重要标准之一就是它的断言集的多寡和易用性。大部分单元测试工具都提供几十个各种各样的断言接口，我这里仅仅是举一个断言接口例子：
我们提供一个整型数判等断言接口：
void cut_int_equal(cut_case_t *tc, const int expected, const int actual, int lineno)
{
        if (expected != actual) {
                tc->failed += 1;
  /* 其他处理，如记录断言发生位置信息等 */
        }
}

这样我们就可以在我们的测试用例中这样使用了：
void tc_add(cut_case_t *tc) {
        int a = 1;
        int b = 2;
        cut_int_equal(tc, 3, add(a, b), __LINE__);
}

5、一个简单但完整的测试实例
CUT以头文件和静态库的形式发布，使用CUT只需要引用其头文件，并在链接时链接CUT的静态库即可。
在下面的例子中我们执行了两个测试用例：
#include "cut.h"
#include "my_math.h" //for add and sub interface

void my_setup() {
        printf("setup for suite\n");
}

void my_teardown() {
        printf("teardown for suite\n");
}

void tc_add(cut_case_t *tc) {
        int a = 1;
        int b = 2;
        cut_int_equal(tc, 3, add(a, b), __LINE__);
}

void tc_sub(cut_case_t *tc) {
        int a = 3;
        int b = 1;
        cut_int_equal(tc, 1, sub(a, b), __LINE__); // 会导致断言错误
}

int main() {
        cut_suite_t *suite = NULL;

        CUT_TEST_BEGIN("test with cut");

        CUT_TEST_SUITE_INIT(suite);

        CUT_TC_ADD(suite, "test tpl_addition:", tc_add);
        CUT_TC_ADD(suite, "test tpl_subtraction:", tc_sub);
        CUT_TS_ADD(suite, my_setup, my_teardown);

        CUT_TEST_RUN();

        CUT_TEST_REPORT();

        CUT_TEST_END();

        return 0;
}

测试结果：
total tc is 2, and failed tc is 1

6、小结
这里仅仅是提出一种实现C Unit Testing Framework的方案，而且仅仅是证明其可行，其离成熟的程度还远得很。我们可以从已经成熟的单元测试工具那里借鉴很多东西过来，如Test Group概念、XML配置等。改进是永无止境的，任重道远啊:)。

APR中少见对数据结构的封装，好像唯一例外的就是其对循环链表，即环(RING)的封装。

在大学的时候学的不是计算机专业，但大三的时候我所学的专业曾开过一门好像叫“计算机软件开发基础”的课，使用的是清华的一本教材，课程的内容包括数据结构。说实话听过几节课，那个老师讲的还不错，只是由于课程目标所限，没讲那么深罢了。当然我接触数据结构要早于这门课的开课时间。早在大一下学期就开始到计算机专业旁听“数据结构”，再说一次实话，虽号称名校名专业，但是那个老师的讲课水平却不敢恭维。

言归正传! 简单说说环(RING)：环是一个首尾相连的双向链表，也就是我们所说的循环链表。对应清华的那本经典的《数据结构》一书中线性表一章的内容，按照书中分类其属于线性表中的链式存储的一种。环是很常见也很实用的数据结构，相信在这个世界上环的实现不止成千上万，但是APR RING(按照APR RING源代码中的注释所说，APR RING的实现源自4.4BSD)却是其中较独特的一个，其最大的特点是其所有对RING的操作都由一组宏(大约30个左右)来实现。在这里不能逐个分析，仅说说一些让人印象深刻的方面吧。

1、如何使用APR RING？
我们先来点感性认识! 下面是一个典型的使用APR RING的样例：
假设环节点的结构如下：
struct  elem_t {    /* APR RING链接的元素类型定义 */
    APR_RING_ENTRY(elem_t)  link; /* 链接域 */
    int                                     foo; /* 数据域 */
};

APR_RING_HEAD(elem_head_t, elem_t);

int main() {
    struct elem_head_t  head;
    struct elem_t       *el;

    APR_RING_INIT(&head, elem_t, link);

    /* 使用其他操作宏插入、删除等操作，例如 */
    el = malloc(sizeof(elem_t);
    el->foo = 20051103;
    APR_RING_ELEM_INIT(el, link);
    APR_RING_INSERT_TAIL(&h, el, elem_t, link);
}

2、APR RING的难点--“哨兵”
环是通过头节点来管理的，头节点是这样一种节点，其next指针指向RING的第一个节点，其prev指针指向RING的最后一个节点，即尾节点。但是通过察看源码发现APR RING通过APR_RING_HEAD宏定义的头节点形式如下：
#define APR_RING_HEAD(head, elem)     \
    struct head {       \
             struct elem *next;      \
             struct elem *prev;      \
    }
如果按照上面的例子进行宏展开，其形式如下：
struct elem_head_t {
     struct elem_t *next;
     struct elem_t *prev;
};

而一个普通的元素elem_t展开形式如下：
struct elem_t {
     struct {       \
        struct elem_t *next;     \
        struct elem_t *prev;     \
     } link;

     int foo;
};
通过对比可以看得出头节点仅仅相当于一个elem_t的link域。这样做的话必然带来对普通节点和头节点在处理上的不一致，为了避免这种情况的发生，APR RING引入了“哨兵(sentinel)”节点的概念。我们先看看哨兵节点在整个链表中的位置。

sentinel->next = 链表的第一个节点；
sentinel->prev = 链表的最后一个节点；

但是察看APR RING的源码你会发现sentinel节点只是个虚拟存在的节点，这个虚拟节点既有数据域(虚拟出来的，不能引用)又有链接域，好似与普通节点并无差别。在APR RING的源文件中使用了下面这幅图来说明sentinel的位置，同时也指出了sentinel和head的关系 -- head即为sentinel虚拟节点的link域。

 普通节点
+->+-------+<--
   |struct |
   |elem   |
   +-------+
   |prev   |
   |   next|
   +-------+
   | etc.  |
   .       .
   .       .

sentinel节点
+->+--------+<--
   |sentinel|
   |elem    |
   +--------+
   |ring    |
   |   head |
   +--------+

再看看下面APR_RING_INIT的源代码：
#define APR_RING_INIT(hp, elem, link) do {    \
            APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link); \
           APR_RING_LAST((hp))  = APR_RING_SENTINEL((hp), elem, link); \
    } while (0)
你会发现：初始化RING实际上是将head的next和prev指针都指向了sentinel虚拟节点了。从sentinel的角度来说相当于其自己的link域的next和prev都指向了自己。所以判断APR RING是否为空只需要判断RING的首个节点是否为sentinel虚拟节点即可。APR_RING_EMPTY宏就是这么做的：
#define APR_RING_EMPTY(hp, elem, link)     \
    (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))

那么如何计算sentinel虚拟节点的地址呢？
我们这样思考：从普通节点说起，如果我们知道一个普通节点的首地址(elem_addr)，那么我们计算其link域的地址(link_addr)的公式就应该为link_addr = elem_addr + offsetof(elem_t, link)；前面我们一直在说sentinel虚拟节点看起来和普通节点没什么区别，所以它仍然符合该计算公式。前面我们又说过head_addr是sentinel节点的link域，这样的话我们将head_addr输入到公式中得到head_addr = sentinel_addr + offsetof(elem_t, link)，做一下变换即可得到sentinel_addr = head_addr - offsetof(elem_t, link)。看看APR RING源代码就是这样实现的：
#define APR_RING_SENTINEL(hp, elem, link)    \
    (struct elem *)((char *)(hp) - APR_OFFSETOF(struct elem, link))

至此APR RING使用一个虚拟sentinel节点分隔RING的首尾节点，已达到对节点操作一致的目的。

3、使用时注意事项
这里在使用APR RING时有几点限制：
a) 在定义RING的元素结构时，需要把APR_RING_ENTRY放在结构的第一个字段的位置。
b) 链接一种类型的元素就要使用APR_RING_HEAD宏定义该种类型RING的头节点类型。学过C++或者了解泛型的人可能都会体味到这里的设计有那么一点范型的味道。比如：
模板：APR_RING_HEAD(T_HEAD, T) ---- 链接----> T类型元素
实例化：APR_RING_HEAD(elem_head_t, elem_t) --- 链接---->elem_t类型元素
 
4、APR RING不足之处
1) 缺少遍历接口
浏览APR RING源码后发现缺少一个遍历宏接口，这里提供一种正向遍历实现：

#define APR_RING_TRAVERSE(ep, hp, elem, link)    \
            for ((ep)  = APR_RING_FIRST((hp));     \
            (ep) != APR_RING_SENTINEL((hp), elem, link);   \
           (ep)  = APR_RING_NEXT((ep), link))
大家还可以模仿写出反向遍历的接口APR_RING_REVERSE_TRAVERSE。

离我的上一篇BLOG已经时隔一个月有余，项目忙是一方面原因，最主要的还是自己没什么“收获”。在最近的项目中总是和内存打交道，时间长了，便有了些许问题，原本我就不是不求甚解者，遂趁此机会又复习了些内存相关资料。

其实下面的话题都是源于在实际项目中碰到的问题，我们通过推敲一句话来开始吧!

1、推敲一句话
在《C专家编程》一书中，有这样的说法“Malloced memory is always aligned appropriately for the largest size of atomic access on a machine”,中文版中翻译为“被分配的内存总是经过对齐，以适合机器上最大尺寸的原子访问”。这句话我也不只看过一遍，不过仅在这次我对它作了认真的推敲，其实整篇也都是围绕着这句话写的。
a) 对齐：数据项仅能存储在地址是该数据项整数倍的内存位置上。在不同的平台上对内存对齐的要求不同，比如在Windows平台上数据项也可以存储在非对齐的内存地址上。但在Sun SPARC平台上如果数据地址没对齐，对它的访问就会带来严重后果(CORE DUMP)。稍后继续详说。
b) 最大尺寸：在32为平台上一般为8字节，在64位平台上为16字节。
c) 原子访问：原子，顾名思义，不可拆分的(严格意义上，在科学界原子并不是最小的粒子，是可拆分的，但在我们这里它就是不可拆分的)。原子访问就是不能被中断的访问。

2、虚拟内存与Cache
太古老的就不说了，我们从“虚拟内存”和Cache说起，为什么莫名其妙的谈到“虚拟内存”和Cache了呢？其实真正需要内存地址对齐的就是这“两位”。虚拟内存技术和Cache的出现追其原因都是因为人们的“物质财富”拮据 -- 内存条太贵。虚拟内存允许你拿硬盘做内存，这样一来就满足了应用程序对内存地址空间的旺盛需求问题，但随之而来的是大量的磁盘操作，使数据的访问速度下降了。人们遂在CPU内加了Cache。

1) 虚拟内存管理以“页”作为基本传输和保护单位在“物理内存”和“硬磁盘”之间倒腾数据。每页大小是固定的，一般为4KB一页。一旦确定了页的大小那么就相当于给了各原子数据项一个不成文的建议：“你们最好不要跨页存储”。什么是“跨页存储”？举个跨页存储例子如下：有这么一个原子类型为int的变量n = 1，其在进程地址空间的存储方式如下：(按照big-endian，高位存在低地址上)

+  ..       + 0x0000 (0000)<--------第一页
|            |
|  ..        |
+-------+
|            |
+-------+ 0x0ffd
|   0       |
+-------+ 0x0ffe
|   0      |
+-------+ 0x0fff (4095)
|   0      |
+-------+ 0x1000 (4096)<-------- 第二页
|   1      |
+-------+ 0x1001 (4097)
|            |
|  ..        |

上图中变量n的存储空间横跨两个内存“页”。那么为什么最好不要跨页存储呢？如上例一旦int n跨页存储，那么程序在访问该变量的时候就必须通过两次换页才能完整的访问该数据，这照比不跨页存储的数据多了一次换页的工作。像这样如果不做约束的话，那么像n这样的数据将会到处都是，那么将会系统的性能很差。在Sun SPARC平台上像这样跨页存储会导致BUS ERROR，在Windows平台上也会带来性能上的下降。相反如果每个数据都是按照页边界对齐的话就不会带来上面的问题。

2) 除了虚拟内存的机制，Cache也是一个要求内存对齐的重要原因。一个Cache由若干Cache Line组成，每个Line中包括一个标签(tag)和一个数据块(Cache Block)组成，CPU在读写Cache时一般是按照Cache Line整行读写的，Cache结构如下图：

tag  |                block
       | 0              8              16              31
-----+---------------+---------------+---------------
       | 32             |                    |                                     Line 0
-----+---------------+---------------+---------------
       | 64             |                    |                                     Line 1
-----+---------------+---------------+---------------

同虚拟内存一样，原子类型数据项不应该跨Cache Line边界存储。具体不详述了。

3、编译器甜头
如果上述问题都让应用程序员自己来解决的话，那就太困难了。庆幸的是我们尝到了“编译器甜头”，编译器通过自动分配和填充数据(在内存中)来进行对齐。对数据进行对齐可以迫使每个内存访问局限在一个cache line或一个单独的页面(page)内。这样就极大简化了cache controller和MMC这样的硬件设计和实现，并且大大提高了访存速度。总结一下：要求数据对齐，从另一个角度说就是不允许原子类型数据项跨越页面或者Cache边界。

4、常见操作未对齐内存的问题
在Sun的Solaris SPARC Runtime Check文档中列出了常见的几种操作未对齐内存的问题：(在Sun SPARC Solaris 9下测试，GCC 3.4.2)
1) 未对齐读(Misaligned Read)
例子：
   int  j;
   char *s = "hello world";
   int  *i = (int *)&s[1];
   j = *i; /* Dump Core */

分析：s指向的字符串中每个字符地址仅仅能满足1字节对齐，而读该数据项时却要求8字节对齐(GCC默认)，&s[1]显然不满足对齐要求，运行出Core。

2) 未对齐写(Misaligned Write)
例子：
   char *s = "hello world";
   int  *i = (int *)&s[1];
   *i      = 'm' ; /* Dump Core */

分析：s指向的字符串中每个字符地址仅仅能满足1字节对齐，而上面程序却向该地址写数据时却要求8字节对齐(GCC默认)，&s[1]显然不满足对齐要求，运行出Core。

3) 未对齐Free
例子：
   char *ptr = (char *)malloc(4);
   ptr++;
   free(ptr); /* Misaligned free */
分析：略

5、什么时候需要考虑到内存对齐
考虑内存对齐的一个典型情况就是“在异构平台间以C结构体的方式进行数据交互”。举个简单的例子：“现需要在Windows平台将一个test_t类型的数据写入一个二进制文件并将该二进制文件在Linux平台下解析，在不指定对齐系数的前提下：Windows平台默认对齐系数为8，而Linux平台默认对齐系数为4”。(暂不考虑字节序的影响)

假设test_t结构如下:
struct test_t {
    double d;
    char   c;
};

在Windows平台下将一个test_t写入二进制文件，由于对齐后test_t大小为16，所以该二进制文件大小为16；将该文件传到Linux上并解析，由于Linux上对齐后的test_t大小为12，导致Linux上的程序验证该二进制文件的完整性失败，解析失败。解决方案：在两个平台使用相同的对齐系数。如对其系数为8：
#pragma pack(8)
struct test_t {
    double d;
    char   c;
};
#pragma pack()
这样两边就能完美对正了。