e820与kernel物理内存映射
我们都对操作系统如何管理内存有一定的了解，然而，在操作系统开始管理内存之前，首先要获取物理内存的信息，比如一共有多少物理地址是可用的，有哪些物理地址是被ACPI（Advanced Configuration and Power Interface）数据使用，这些信息从何而来呢？
e820就是BIOS像x86架构（包括x86_64）上的操作系统引导程序提供物理内存信息的功能。当请求BIOS中断号15H，并且置操作码AX=E820H的时候，BIOS就会向调用者报告可用的物理地址区间等信息，e820由此得名。
Linux内核也通过这种机制来获得物理地址信息，使用dmesg可以看到相关的信息：
[ 0.000000] BIOS-provided physical RAM map: [ 0.000000] BIOS-e820: 0000000000000000 - 000000000009e800 (usable) [ 0.000000] BIOS-e820: 000000000009e800 - 00000000000a0000 (reserved) [ 0.000000] BIOS-e820: 00000000000e0000 - 0000000000100000 (reserved) [ 0.000000] BIOS-e820: 0000000000100000 - 0000000020000000 (usable) #511MB [ 0.000000] BIOS-e820: 0000000020000000 - 0000000020200000 (reserved) [ 0.000000] BIOS-e820: 0000000020200000 - 0000000040000000 (usable) #510MB [ 0.000000] BIOS-e820: 0000000040000000 - 0000000040200000 (reserved) [ 0.000000] BIOS-e820: 0000000040200000 - 00000000aac0d000 (usable) #1706MB [ 0.000000] BIOS-e820: 00000000aac0d000 - 00000000aad8e000 (reserved) [ 0.000000] BIOS-e820: 00000000aad8e000 - 00000000aad95000 (usable) [ 0.000000] BIOS-e820: 00000000aad95000 - 00000000aad96000 (reserved) [ 0.000000] BIOS-e820: 00000000aad96000 - 00000000aad97000 (usable) [ 0.000000] BIOS-e820: 00000000aad97000 - 00000000aadb8000 (reserved) [ 0.000000] BIOS-e820: 00000000aadb8000 - 00000000aadc6000 (usable) [ 0.000000] BIOS-e820: 00000000aadc6000 - 00000000aade8000 (reserved) [ 0.000000] BIOS-e820: 00000000aade8000 - 00000000aaf23000 (usable) [ 0.000000] BIOS-e820: 00000000aaf23000 - 00000000aafe8000 (ACPI NVS) [ 0.000000] BIOS-e820: 00000000aafe8000 - 00000000aaffd000 (usable) [ 0.000000] BIOS-e820: 00000000aaffd000 - 00000000ab000000 (ACPI data) [ 0.000000] BIOS-e820: 00000000ab000000 - 00000000b0000000 (reserved) [ 0.000000] BIOS-e820: 00000000e0000000 - 00000000e4000000 (reserved) [ 0.000000] BIOS-e820: 00000000fec00000 - 00000000fec01000 (reserved) [ 0.000000] BIOS-e820: 00000000fed10000 - 00000000fed14000 (reserved) [ 0.000000] BIOS-e820: 00000000fed18000 - 00000000fed1a000 (reserved) [ 0.000000] BIOS-e820: 00000000fed1c000 - 00000000fed20000 (reserved) [ 0.000000] BIOS-e820: 00000000fee00000 - 00000000fee01000 (reserved) [ 0.000000] BIOS-e820: 00000000ff980000 - 00000000ffc00000 (reserved) [ 0.000000] BIOS-e820: 00000000ffd80000 - 0000000100000000 (reserved) [ 0.000000] BIOS-e820: 0000000100000000 - 000000014f800000 (usable) #1272MB
上面是我在自己计算机上得到的数据，其中usable的区间就是实际被映射到物理内存上的地址空间，上面标注出来的四个区间，就是我主要的四个可用的物理地址区间了，大约4GB。
- Usable：已经被映射到物理内存的物理地址。
- Reserved：这些区间是没有被映射到任何地方，不能当作RAM来使用，但是kernel可以决定将这些区间映射到其他地方，比如PCI设备。通过检查/proc/iomem这个虚拟文件，就可以知道这些reserved的空间，是如何进一步分配给不同的设备来使用了。
- ACPI data：映射到用来存放ACPI数据的RAM空间，操作系统应该将ACPI Table读入到这个区间内。
- ACPI NVS：映射到用来存放ACPI数据的非易失性存储空间，操作系统不能使用。
- Unusable：表示检测到发生错误的物理内存。这个在上面例子里没有，因为比较少见。
内核读到这些信息后，将其保存在e820map结构体中，有两个副本，一个符号名叫e820，还有一个符号名叫e820_saved。具体的数据结构可以参考arch/x86/include/asm/e820.h。随着内核的启动，内核还会修改e820的信息。
[ 0.000000] e820 update range: 0000000000000000 - 0000000000010000 (usable) ==> (reserved) [ 0.000000] e820 remove range: 00000000000a0000 - 0000000000100000 (usable) [ 0.000000] e820 update range: 00000000ab000000 - 0000000100000000 (usable) ==> (reserved)
比如在我的系统上发生了这样三次e820的改动，这些改动已经与BIOS没有任何关系了，只是内核自己通过修改自己的内存数据结构，来改变自己对内存区间的使用。
还有一个典型的例子是当内核启动参数中有置顶memmap这样的参数项时，内核会修改指定的usable的区间为reserved，这样内核就不能将虚拟地址映射到这些物理地址空间了，换言之就是不能使用这块物理内存了（其实通过ioremap还是可以将其映射到内核的虚拟地址空间的，但是这些行为都是自己控制的而不会受到其他程序的干扰）。这样当我们需要自己管理某段物理内存而不希望内核干预时就很有用处，比如基于物理内存的文件系统，就可以这样实现。
内核中还提供了一系列操作e820数据结构的函数，函数声明都在arch/x86/include/asm/e820.h，相应的定义都在arch/x86/kernel/e820.c中。文章开头看到的这段信息，就是由void __init e820_print_map(char *who)来打印的。
在这个过程中，e820_saved始终保持原始的状态不变，以便查询BIOS提供的真实映射信息，不过内核目前好像没有使用这个数据结构。我曾经有使用过它，用来检查某个物理地址是否确实是物理内存。
GCC __builtin_expect与kernel指令序列优化
在内核级的开发过程中，代码运行速度尤为重要，让我们先看两段汇编代码。
.LC1: .string "Hula!" .LC2: .string "Woo~" call __isoc99_scanf movl 28(%esp), %eax testl %eax, %eax je .L2 movl $.LC1, (%esp) call puts .L3: xorl %eax, %eax leave ret .L2: movl $.LC2, (%esp) call puts jmp .L3
.LC1: .string "Hula!" .LC2: .string "Woo~" call __isoc99_scanf movl 28(%esp), %eax testl %eax, %eax jne .L5 movl $.LC2, (%esp) call puts .L3: xorl %eax, %eax ret .L5: movl $.LC1, (%esp) call puts jmp .L3
上面两段代码为了方便阅读，都省略了一些与本次主题无关的代码。稍微阅读一下就可以发现，这两段代码做的事情其实是一样的。这是一个简单的if分支结构的编译结果，两段代码的差异在于是讲if段还是else段放在前面。这两者有着什么样的区别呢？
这要从现代的处理器架构说起。相信大家都知道流水线技术，就是CPU可以在统一个时钟周期内同时执行多条指令，当前指令尚未执行完毕，实际上就已经开始处理后面的指令了。然而当处理器遇到分支的时候，就无法判断即将执行的是哪个分支，流水线优化就受到了限制。
后来，随着处理器技术的发展，处理器开始直接预取分支后面的指令，如果发现分支预判错误，则抛弃之前的执行结果，重新转入正确的分支继续执行。更加现代的处理器甚至能够预取更多后面的指令，对于不依赖之前执行结果的指令都可以按照一定的规则预先执行得到结果。
再看上面的例子，我们就明白了，直接连接在je或者jne指令后面的分支可以在分支条件判断结束之前就开始运行，因此执行速度会更快，相反另一条分支则会慢一些。
在这个例子中两个分支都非常短，在更复杂的情况下，如果单个分支就很长，那么预取正确的指令还有助于Cache的命中。
GCC提供了__builtin_expect宏，作为编译分支时候的暗示。用法是__builtin_expect(var, expected_value)，也就是说，告诉编译器var这个变量的值比较可能是什么。在kernel中这个宏被用在likely和unlikely这两个宏定义中：
#define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0)
显而易见，这两个宏的意思是，条件x是很有可能成立，还是很有可能不成立。
int main()
{
int a;
scanf("%d", &a);
if (likely(a))
{
printf("Hula!\n");
}
else
{
printf("Woo~\n");
}
return 0;
}
上面第一段汇编代码，实际上就是这个程序编译产生的。相应的，把likely改为unlikely，就可以得到第二段的汇编代码。
在内核中，比如就绪队列不太可能为空，runqueue里的所有任务很有可能都在CFS queue里，以及一些很少见的竞争与冒险的情况，都有针对性地使用这种技术进行了优化。
GCC typeof在kernel中的使用——C语言的“编译时多态”
大家都知道，C语言本身没有多态的概念，函数没有重载的概念。然而随着C语言编写的软件逐渐庞大，越来越多地需要引入一些其他语言中的特性，来帮助更高效地进行开发，Linux kernel是一个典型例子。
在动态类型的语言里面，往往有typeof这种语法，来获取变量的数据类型，比如JavaScript当中，typeof以字符串型式返回了这个变量的数据类型，借由这种特性，往往可以根据传入参数的类型不同，产生不同的行为。
GCC提供的typeof，实际上是在预编译时处理的，最后实际转化为数据类型被编译器处理。用法上也和上述语言不太一样。
基本用法是这样的：
int a; typeof(a) b; //这等同于int b; typeof(&a) c; //这等同于int* c;
那么在内核中这种特性是怎样使用的呢？
/*
* Check at compile time that something is of a particular type.
* Always evaluates to 1 so you may use it easily in comparisons.
*/
#define typecheck(type,x) \
({ type __dummy; \
typeof(x) __dummy2; \
(void)(&__dummy == &__dummy2); \
1; \
})
/*
* Check at compile time that 'function' is a certain type, or is a pointer
* to that type (needs to use typedef for the function type.)
*/
#define typecheck_fn(type,function) \
({ typeof(type) __tmp = function; \
(void)__tmp; \
})
这两段代码来自于include/linux/typecheck.h，用于数据类型检查。
宏typecheck用于检查x是否是type类型，如果不是，那么编译器会抛出一个warning（warning: comparison of distinct pointer types lacks a cast）；而typecheck_fn则用于检查函数function是否是type类型，不一致则抛出warning（warning: initialization from incompatible pointer type）。
原理很简单，对于typecheck，只有当x的类型与value一致，&__dummy == &__dummy2的比较才不会因为类型不匹配而抛出warning，详情可以参考C语言对于指针操作的标准规定。对于typecheck_fn，当然也只有function的返回值和参数表与type描述一致，才不会因为类型不匹配而抛出warning。
到这里有人可能会有一个疑问，内核代码里执行类型检查会不会降低效率？答案是不会的，因为实际上，这些为类型检查而声明的临时变量，实际上在上下文中都没有使用，并且还特别地强制类型转换为void防止任何由这些临时变量产生的结果被使用的情况，因此在编译器优化时，就将这些无用的代码删除了。
然后kernel中还定义了使用另一种类型检查策略的获取最大最小值的宏。
/*
* ..and if you can't take the strict
* types, you can specify one yourself.
*
* Or not use min/max/clamp at all, of course.
*/
#define min_t(type, x, y) ({ \
type __min1 = (x); \
type __min2 = (y); \
__min1 < __min2 ? __min1: __min2; })
#define max_t(type, x, y) ({ \
type __max1 = (x); \
type __max2 = (y); \
__max1 > __max2 ? __max1: __max2; })
这个例子里面不要求x和y是严格等于type类型，只要x和y能够安全地完成隐式类型转换为type就可以安全通过编译，否则会抛出warning。
另外一个非常经典的例子就是交换变量。
/*
* swap - swap value of @a and @b
*/
#define swap(a, b) \
do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
试想如果没有typeof，要怎么在C语言中实现这种类似C++模板的特性呢？
最后不得不提的就是container_of宏，在kernel中也被广泛使用。
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
比如内核的task_struct数据结构中有一个member是sched_entity类型的se，这个member常常被调度器使用来决定进程的调度顺序，那么如果要根据这个se来获取包含它的task_struct，就可以使用container_of(p, task_struct, se)来实现（假设p是指向这个sched_entity的指针）。原理是先产生一个指针指向member，然后将这个指针减去member在这个struct中的偏移量，指针自然就指向了包含该member的对象了（这个地方用到了offsetof，含义一看便知，我就不再细说了）。
希望大家对typeof的使用有了一个更好的理解，欢迎评论！
