1. 线程

线程的事情要从CPU开始说起。CPU可以执行程序代码，我拿C语言写的计算两个数的和的程序举例子：

int a, b;
scanf("%d%d", &a, &b);
printf("%d", a + b);

这个程序学过C语言的人大体上是都写过的。不说太复杂的，我省略掉细节说，那么就是CPU会一行一行代码执行下来：首先给变量 a 和 b 分配空间，然后调用 scanf 从键盘获取输入的数字，然后计算两个数字的和，并且显示出来。

但是这么一台电脑，只拿来干这种事情，实在是很不合算。CPU那么快，分配完变量 a 和 b 的空间以后就坐那边等，等你输入完数字再瞬间算完显示出来，非常非常大量的时间都花在“等”上面了。这么用电脑，实在是很浪费。不应该不应该。

然后现在要说到多线程。书本上说到多线程的时候，时常爱拿出来说的一个例子是你可以拿电脑一边听歌一边写报告。现在还是拿个简化的模型来考虑，考虑听歌的时候电脑在干什么，考虑写报告的时候电脑在干什么。
对于听歌来说，电脑做的事情其实很简单：从硬盘中把MP3读出来，解码成声卡能识别的格式，把数据传到声卡上；这一小段放完以后，重复执行这个步骤，传下一个小段。因为电脑读MP3并且解码的速度是远远大于声卡播放声音的速度的（播放快了还能听吗？），所以电脑大部分时间还是空闲的。
再说写报告，如果你没有在往里面打字的话，电脑在干啥？电脑在算时间，时间差不多到了把输入光标隐藏起来，等时间差不多到了再把输入光标显示出来，然后你就看到光标在闪：显示和隐藏光标其实根本花不了多少时间，电脑大部分时间花在“等”上面。那么你在打字的时候呢？就算一分钟能敲300个按键，每个按键平均也就20毫秒，输入法对一个按键的反应时间不要那么久，结果大部分时间还是在等你按键。
现在把三件事情合起来，电脑需要等声卡播放完、需要等时间到了去闪光标、需要等你按键输入，全都在等。所以它在等声卡播放完之前可以处理你按键的事情，可以处理光标闪的事情，电脑可以同时干很多事。

2. 线程调度

电脑虽然能像上面说的那样同时干很多事，但是电脑系统并不能完全按照这样做。一个写报告的软件，在你也不输入光标也不闪的时候可以告诉系统“我现在没有要做的事情了”，但是如果开发软件的人做得不好，忘记告诉了或者怎么的，这电脑可能就卡死在这里面没有机会干其他事了。所以系统不能这样干，比如你现在要在CPU上执行程序，系统会分配给你一小段时间，你可以用CPU这么一段时间，如果时间到了你还没告诉系统“我现在暂时干完事了”，系统也会强行不让你继续运行，它会把你从CPU里拽出来，然后放另一个要用CPU的进去；只有说找不到什么程序要用CPU了，才会让你继续用。

这种会把你拽出来的方式叫做“抢占式多线程”；而这种你可以抱着CPU一直用到你觉得暂时用完了，比如上面算加法的C程序，执行到scanf的时候用户没输入，那也就是“暂时用完了”：要等用户输入了才能继续用CPU，这样的使用方式，叫做非抢占式多线程。Windows、Linux或者苹果这样的系统，都用的抢占式多线程的方式，这样才不会因为有一个程序写得不太好，抱着CPU不放，导致整个系统都没法用。

3. 线程切换

系统要强行把一个正在执行的程序从CPU里拖出来，就也要保证下次把这个程序再放CPU里去的时候它能继续这么执行。系统在把程序从CPU里拖出来的时候会保存程序的一系列信息，比如执行到哪里了、是通过调用了多少函数执行到这个位置的、执行到这边的时候各种变量的值是多少、算一半的那些东西放在寄存器里的值是多少，这类。这些东西都保存好之后，就可以把另一个程序的这些东西进CPU，这样就做到了“继续执行另一个程序”。然后等到了时间或者程序主动表示“这一段执行完了现在没事干了”，再把程序从CPU里弄出来。
在系统寻找下一个要放到CPU上执行的程序的时候，这种表示“没事干”的程序是不会被考虑的：都没事干了放进去干嘛。当然这种没事干的程序也能变成有事干，一个输入法你不按键盘的时候它没事干，你按键盘了它就有事干了；一个写文章的软件，光标显示着的时候和光标隐藏着的时候都是没事干，要从隐藏变成显示、显示变成隐藏的时候软件就有事干；一个播放音乐的软件，声卡在把程序送入的声音放完之前，播放器没事干，这段播完了的时候程序就有事干了：要送下一段进去。一个程序的状态会在这种有事干没事干之间变化。

这里上下文里提到的“程序”指的是线程。线条一样执行下来的程序。

线程的状态分为 新建、就绪、阻塞、运行、死亡 这么几个状态。重点关注就绪阻塞和运行：就绪，代表这个线程需要放到CPU上运行，比如事情干一半被操作系统强行从CPU拖出来的，就会是这种状态：它下次还要继续运行才行；阻塞，就像刚才说的，一个播放器，已经把要播放的一小段送到声卡那边去了，在声卡播放完这段之前没事干，没事干就是阻塞状态，等声卡播完这一段了它又会变成就绪状态，否则你听完这一小段音乐就听不到下一段了。运行，就是线程塞到CPU里运行了。

4. 模拟多线程网络服务器的线程切换开销

前面的基础概念说完了，现在要讲讲网络服务器这边是一种什么样的情况。这里以最简单的能架静态网站的HTTP服务器为例子了。

这样的HTTP服务器要做的事情，其实很简单地就只包含这么几个：接受用户的链接，接收用户发来的请求，发送用户请求的文件，关闭连接。但是由于网络传输是很慢的，服务器并不能处理完一个人再处理下一个人：万一遇上一个网络状态不太好的人，光是收请求和发文件就花了特别多的时间，甚至突然对方网络就断了，只能等超时，就会变成后面排了一堆要上你这个网站的人卡在这里。

然后就有了这样一种简单的做法，来一个用户连上来就开一个新线程，专门接收这个人发来的请求，专门给这个人发他要的文件。这样的话，连的人多了，系统里就会有一堆这样的线程，这样的线程执行的套路大概就是执行了一段代码，比如要分析用户的请求数据了，这个时候就会调用例如 recv 这样的函数获取用户发来的数据，但是实际上此时用户没有数据发来，那么这个线程就变成了“没事干”的状态，系统就把这个线程从CPU拖出来、塞别的进去运行了，直到通过网络收到了用户发来的请求，才会变回就绪状态。

现在模拟一下线程这样的行为，为了方便计时，我忽略了网络传输所需的时间，就只模拟这个“被从CPU里拖出来”的动作。然后一个线程干的事情其实就两个：一个是执行代码，这里用求三个数的平均数模拟；另一个就是“被从CPU里拖出来”。拖出来用的是 std::this_thread::yield(); 这种方法。我要等所有线程都创建完了才开始执行和计时，所以用了Barrier：这是一个能让指定数量的线程同时到达这个“栅栏”之后才能继续执行的机制

SYNCHRONIZATION_BARRIER barrier;
void ThreadFunc()
{
    EnterSynchronizationBarrier(&barrier, 0);
    std::vector<int> input(256 * 1024);
    std::vector<int> output(256 * 1024);

    for (int rep = 0; rep < 1000; ++rep)
    {
        for (size_t i = 0; i < input.size() - 2; ++i)
            output[i] = (input[i] + input[i + 1] + input[i + 2]) / 3;
        std::this_thread::yield();
    }
}

然后我现在开200个这样的线程让它跑：

int main()
{
    InitializeSynchronizationBarrier(&barrier, 201, -1);
    std::vector<std::thread> threads(200);

    for (size_t i = 0; i < threads.size(); ++i)
        threads[i] = std::thread(ThreadFunc);
    EnterSynchronizationBarrier(&barrier, 0);
    DeleteSynchronizationBarrier(&barrier);
    time_t beginTime = time(NULL);
    for (size_t i = 0; i < threads.size(); ++i)
        threads[i].join();
    std::cout << (time(NULL) - beginTime) << std::endl;
}

加上所需的头文件，整个程序是这样。这个程序主要是演示线程切换会花多少时间。使用后面提到的IO多路复用技术并不完全是因为节省线程切换的开销的，这里先不谈其他的影响因素，一个个理解会简单一些。可以直接复制去编译自己运行试试

#include <Windows.h>
#include <thread>
#include <vector>
#include <iostream>
#include <time.h>

SYNCHRONIZATION_BARRIER barrier;
void ThreadFunc()
{
    std::vector<int> input(256 * 1024);
    std::vector<int> output(256 * 1024);
    EnterSynchronizationBarrier(&barrier, 0);
    for (int rep = 0; rep < 1000; ++rep)
    {
        for (size_t i = 0; i < input.size() - 2; ++i)
            output[i] = (input[i] + input[i + 1] + input[i + 2]) / 3;
        std::this_thread::yield();
    }
}

int main()
{
    InitializeSynchronizationBarrier(&barrier, 201, -1);
    std::vector<std::thread> threads(200);

    for (size_t i = 0; i < threads.size(); ++i)
        threads[i] = std::thread(ThreadFunc);
    EnterSynchronizationBarrier(&barrier, 0);
    DeleteSynchronizationBarrier(&barrier);
    time_t beginTime = time(NULL);
    for (size_t i = 0; i < threads.size(); ++i)
        threads[i].join();
    std::cout << (time(NULL) - beginTime) << std::endl;
    return 0;
}

它能给出花的总时间。我这边运行以后，花费是 31。

5. 减少线程开销

以上程序代码用 std::this_thread::yield() 来模拟了“要从用户接收数据了，但是数据没来，所以让操作系统把当前线程从CPU抠出来，把CPU让给别人”这样的操作。这里有200个线程在执行，所以系统一直在这么些线程之间切换。我现在换一种方式，让同时运行的线程数正好一个CPU核心一个，这样在调用 yield 的时候，就会发生“系统发现没有其他线程要运行，所以继续让你用CPU”的情况，以此来模拟线程切换的开销小了的时候是什么样的。这里用一个“信号量”来控制同时运行的线程的数量，实际运行效果将是一个CPU核心上一个线程在跑，每次到 yield 的时候系统会看一圈有没有线程要用，没有要用所以就不切换。我直接给出整个程序代码了，和上面相比可以发现多了个 Semaphore（信号量） 而已。信号量是这样一种机制，你可以声明手头有多少个“资源”，这个资源拿走一个少一个，拿不到了就会在那边等；拿到的“人”用完了之后可以还回去，还回去直接就拿去给在那边等的“人”了。这样受到信号量的控制，比如我是4核CPU，那么200个线程里就只会有4个线程能进去执行算平均数和yield（模拟网络收发）这两个操作。那么yield的时候系统就会让你继续执行而没有切换，切换的开销大大减小了。

#include <Windows.h>
#include <thread>
#include <vector>
#include <iostream>
#include <time.h>

SYNCHRONIZATION_BARRIER barrier;
HANDLE semaphore;
void ThreadFunc()
{
    std::vector<int> input(256 * 1024);
    std::vector<int> output(256 * 1024);
    EnterSynchronizationBarrier(&barrier, 0);
    WaitForSingleObject(semaphore, INFINITE);
    for (int rep = 0; rep < 1000; ++rep)
    {
        for (size_t i = 0; i < input.size() - 2; ++i)
            output[i] = (input[i] + input[i + 1] + input[i + 2]) / 3;
        std::this_thread::yield();
    }
    ReleaseSemaphore(semaphore, 1, NULL);
}

int main()
{
    InitializeSynchronizationBarrier(&barrier, 201, -1);
    semaphore = CreateSemaphore(0, std::thread::hardware_concurrency(), std::thread::hardware_concurrency(), 0);
    std::vector<std::thread> threads(200);

    for (size_t i = 0; i < threads.size(); ++i)
        threads[i] = std::thread(ThreadFunc);
    EnterSynchronizationBarrier(&barrier, 0);
    DeleteSynchronizationBarrier(&barrier);
    time_t beginTime = time(NULL);
    for (size_t i = 0; i < threads.size(); ++i)
        threads[i].join();
    std::cout << (time(NULL) - beginTime) << std::endl;
    CloseHandle(semaphore);
    return 0;
}

这个程序在我电脑上运行，最终输出是 21。

6. IO多路复用

从上面程序的对比，可以看出线程切换的开销小了之后，执行同样多的任务，性能要好不少，这个例子在我电脑上是差了差不多10秒钟。

那么回到刚才HTTP服务器的话题，HTTP服务器给一个连上来的用户开一个线程，网络又是一种很慢的输入输出（IO）方式，在调用 send 发送数据和调用 recv 接收数据的时候，会遇到发送缓冲区满了只能等、接收缓冲区空了只能等 这样的情况。因为你要等了，系统就会做线程切换，换到能运行的线程上。等你等到你要的东西了，再让你继续执行。效果就是和上面例子里前一个程序那样，切换线程花了很多时间。

那么 epoll、kqueue 是怎么一回事呢，你把网络通信那个“文件”设置成“非阻塞”模式之后，如果 send 遇到发送缓冲区满了、 recv 遇到接收缓冲区空了，它不会“等”，而是直接告诉你满了空了，这个时候你要做的事情是通过 epoll 或者 kqueue 机制，告诉系统“能发送数据、能接收数据了叫我”，因为线程没有在等，所以你可以接着干其他事，这里指的是处理其他用户的连接。等一波任务处理完之后，就回到“等 epoll / kqueue 叫”这样的阶段，epoll 和 kqueue 发现有用户可以发数据可以收数据了，就叫你，告诉你有多少用户可以收发了，然后你就接着处理这些用户——一切都是在同一个线程内执行，中间不进行切换。这样线程切换的开销就省掉了，就像上面第二个例子那样：yield 的时候不切换、继续让你执行。

还有一个“io完成端口”没说，其实它原理和 epoll、kqueue 差不多，只是它把顺序变了一下：不是可以 send 可以 recv 的时候叫你。调用 send、recv 的时候它不会告诉你缓冲区满了空了，而是确实去执行了，等到发完了、收完了再叫你，而不是可以发、可以收的时候叫你。这个层面上说其实没什么区别……

7. ？？？

这种“等系统叫你”的方式，会大大增加写出来的代码的复杂度。本来是 接收数据——处理数据 这样的流程，变成了 等系统叫你——接收数据——处理数据。而其中的“等系统叫你”当然不能呆在那边等，这样就和不用IO多路复用没什么两样了。到了“等系统叫你”这样的环节，你要把当前处理的代码 return 掉，然后去处理其他用户，然后等系统叫你的时候，又要重新回去执行对付这个用户的代码，还要回到刚才做一半的事情的状态里去，这个就很恶心：return都return了，这要怎么回。在这里通常是调用了一个新的函数，也就是一个处理代码，要被拆开成好几个不同的函数，就有了局部变量（“也就是状态”）在不同函数之间传递非常的麻烦。有个叫“协程”的技术可以用来解决这样的问题，但这不是这里要说的。协程可以模拟一种“伪return”，让代码的执行流程，可以有“从一个函数return”的效果；然后下次进来的时候能从这个“伪return”的地方继续执行，局部变量这样的状态就还在，写出来的代码也就和没用IO多路复用的时候差不多，大大降低了代码的复杂度。

这里提一下，为什么第二个示例程序不直接去掉 yield ，而是要执行 yield 然后由系统让你继续执行呢。因为对于 epoll、kqueue、iocp 来说，你告诉系统要等有“事件”的时候叫你，也是要时间要开销的，所以我就留在那边模拟这个开销了。而且你4核CPU跑你的程序的4个线程的时候，也不是一直四个线程都在上面的，操作系统还要执行其他程序对吧，比如桌面环境，比如后台的QQ，浏览器里网页上的动画还在动，或者你开在后面的音乐播放器……

想要研究x86架构下的内存管理，最重要的参考文档应该是英特尔官方关于内存管理方面的解释了。在 Intel? 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1 文档的第三个章节，详细解释了整个翻译过程，其中涉及到的寄存器和各种标志位的作用。长是比较长，而且又是英语的，但是说得很清楚。

而实验则是验证自己理解是不是正确的一个很好的方式。理论看了半天，也知道怎么算，套公式好像也能算得出来，但是却不知道有没有算对。有真实的环境，一测试一验证，就知道对不对了。如果自己理解有误，可以及早发现和纠正。

关于逻辑地址转物理地址的文章，已经有很多地方都能找到，包括公式啥的。但是大多只有理论上的解释，最多再给你个习题啥的。真正要动手在系统上做实验，一个要获取CR3寄存器，一个要访问物理内存读取页表，这两个操作略麻烦，不知道是不是阻碍动手做实验的原因。总之现在CR3能获取到了，通过 /dev/mem 这个设备也可以访问物理内存，可以说万事俱备了。

分页机制很好地实现了进程间的内存空间隔离：不同进程之间正常情况下只能在属于自己的内存空间中操作。而且这种隔离并不仅仅是不让你访问属于其他进程的地址，而是根本看不见其他进程的内存：不同进程就像在不同次元中运行。举个例子，同样一个地址，在不同的进程中，可以看到不同的数据，这就是靠分页机制实现的：进程中操作的所有地址，都要先进过一个转换，转换成物理地址，才操作内存。而这种转换，对于不同的进程，是不同的。所以同一个地址，通过不同的转换方式，可以转到不同的物理地址上去，保存在内存中不同的地方。就好像它们在不同的平行世界上一样。

Intel那个文档里的图片对于整个地址的转译过程说得很清楚，配上图片就更加容易理解了。这张图片的左上角，“逻辑地址”，或者说Far Pointer，就是平时写C语言程序的时候会遇到的叫“指针”的东西。
这个指针要最终操作物理内存，先要经过“分段”机制的翻译，将指针所表示的地址加上一个其所属的段的“段基址”，变成“线性地址”。所谓“所属的段”，写过见过汇编语言的同学可能会见过类似  CS: DS: ES: 这样的前缀，其中CS DS ES这些是段寄存器，里面保存了段的编号。通过段的编号可以在段表中找到这个段的信息，进而获取到段的基址。但是现在的操作系统，比如Windows、Linux、*BSD啥的，大部分情况下就直接给你把基址定为0。这样确实是比较方便了，任何数加上0还是原来的数，于是逻辑地址等于线性地址。那么把逻辑地址转为物理地址的时候就不理这个步骤了，直接去处理分页机制就好了。
分页的话，CPU的某个寄存器保存了“页表”的地址，这个页表可能有好几级。线性地址的每个部分都保存了每一级需要的索引（说白了就是数组下标），然后最后一部分保存了偏移。这个在下面具体情况的时候再去理解会比较容易。

实验在NetBSD 6.1.4上完成。已经通过这一篇文章中介绍的方法添加了获取CR3寄存器值的系统调用，调用号是475。

========================================================
1、x86-32，未开启PAE的情况
========================================================

这两张图把整个过程说明得非常清楚，首先获取CR3寄存器的值，然后通过这个值找到Page Directory，再根据Page Directory里的标志位确定还要不要继续到Page Table里面去找：因为Page Directory里也可能是直接指向一个4MB的内存页，这根据Page Directory Entry里第7（最右为第0位）位（PS位，全称Page Size）是不是1来决定它指向的是一个Page Table还是直接表示了一个4MB的内存页。这些页目录、页表项的前20位（4MB内存页的时候是前10位）代表了基地址，就是页表具体存放在哪里或者这个页具体在哪里。然后最后一位（Present位）是1还是0代表了这个页面是否存在。有这样一种情况，内存页会不存在：操作系统不是有一个机制叫做虚拟内存吗？可以通过将暂时不用的内存页写入硬盘，腾出这部分空间给急需内存的程序使用，这些数据如果以后又要用了，就再从硬盘中读出来。那么如果一个页面正好被放入硬盘了，就有可能明明是一个可以访问的地址，但是这个最后一位却是0。关于这些位的详细解释，看Intel的文档就能很清楚了。

这里面，CR3和Page Directory Entry和Page Table Entry涉及到的“地址”全部都指的是物理地址。

然后通过 /dev/mem 来操作物理内存，就可以写一个程序将虚拟地址转为物理地址，然后验证是否正确。一个简单的方法，就是声明一个变量，然后把它的地址转成物理地址，通过写入 /dev/mem 来改变它的值，最后读取这个变量看看它的值有没有变。这个过程中有一个需要注意的地方，就是如果一个页目录项或者页表项的末位为0，就直接认为转换失败了。以及就算转出了物理地址，如果在转完之后访问之前正好遇上操作系统把这个内存页换到硬盘的交换分区去了，也是会出错的。所以这个仅仅是实验，真正实用要考虑的东西实在是非常多，不要贸然搞这样的方法。要让内核把这个分页换回来虽然也不难，比如访问一下这个变量之类……不过这样程序逻辑就变麻烦了，而且又反正是实验嘛，就随便来了（殴）。实际实验过程中，因为程序体积小占的内存少，又因为是虚拟机里面、系统根本没运行其他东西，所以没遇到这种情况。

于是有如下测试程序：

#include <unistd.h>
#include <cstdio>
#include <fcntl.h>
#include <stdint.h>
using namespace std;

struct PhyAddr {
    uint32_t m_phyaddr;
    PhyAddr(uint32_t addr = 0) : m_phyaddr(addr)
    {
    }
    PhyAddr& operator += (uint32_t offset)
    {
        m_phyaddr += offset;
        return *this;
    }
};

bool AccessPhyMem(PhyAddr addr, bool isRead, void* buf, int len)
{
    int fd = open("/dev/mem", O_RDWR);
    if (fd <= 0)
        return false;
    lseek(fd, addr.m_phyaddr, SEEK_SET);
    if (isRead)
        read(fd, buf, len);
    else
        write(fd, buf, len);
    close(fd);
    return true;
}

struct PageItemEntry {
    uint32_t m_entry;
    operator PhyAddr ()
    {
        PhyAddr r;
        r.m_phyaddr = m_entry & 0xfffff000;
        return r;
    }
    bool IsPresent()
    {
        return (m_entry & 1) == 1;
    }
};

struct PageDirEntry : public PageItemEntry {
    bool Is4MPage()
    {
        return (m_entry & 0x80) != 0;
    }
    operator PhyAddr ()
    {
        PhyAddr r = PageItemEntry::operator PhyAddr();
        if (Is4MPage())
            r.m_phyaddr &= 0xffc00000;
        return r;
    }
};

struct PageTblEntry : public PageItemEntry {
};

void SplitPtr(void* ptr, int* nDirIndex, int* nTblIndex, int* nOffset, int* nOffset2)
{
    *nDirIndex = (uint32_t)ptr >> 22;
    *nTblIndex = ((uint32_t)ptr >> 12) & 0x3ff;
    *nOffset = (uint32_t)ptr & 0xfff;
    *nOffset2 = (uint32_t)ptr & 0x003fffff;
}

int main()
{
    volatile int var = 0xfbfbfbfb;
    int val = 0x12349876;
    int nDirIndex, nTblIndex, nOffset, nOffset2;
    SplitPtr((void*)&var, &nDirIndex, &nTblIndex, &nOffset, &nOffset2);
    
    try {
        PhyAddr cr3 = syscall(475);
        PhyAddr varAddr;
        PageDirEntry pageDir[1024];
        AccessPhyMem(cr3, true, pageDir, sizeof(pageDir));
        if (!pageDir[nDirIndex].IsPresent())
            throw "Fail: Invalid page directory entry.";

        if (pageDir[nDirIndex].Is4MPage()) {
            varAddr = pageDir[nDirIndex];
            varAddr += nOffset2;
            AccessPhyMem(varAddr, false, &val, sizeof(val)); 
        } else {
            PageTblEntry pageTbl[1024];
            AccessPhyMem(pageDir[nDirIndex], true, pageTbl, sizeof(pageTbl));
            if (!pageTbl[nTblIndex].IsPresent())
                throw "Fail: Invalid page table entry.";
            varAddr = pageTbl[nTblIndex];
            varAddr += nOffset;
            AccessPhyMem(varAddr, false, &val, sizeof(val));
        }

        printf("%x\n", var);
    } catch(const char* msg) {
        fprintf(stderr, "%s\n", msg);
    }
    return 0;
}

简单说就是通过把var的地址转成物理地址，然后把val的值写入这个地址，最后输出var看看是否被改变了。

还是上面说的：就算都检查了 IsPresent() ，只要转成物理地址之后正好发生页面交换把var所在页面调入swap，这个写入仍然是有问题的。只是因为现在是实验所以才这么做。

顺便，如果提供的是另一个进程的CR3和另一个进程里的某个变量的地址，那么可以直接修改另一个进程里面的变量。注意volatile关键词，免得编译器生成的代码在你要输出的地方不重读变量。

========================================================
2、x86-32，开启PAE的情况
========================================================

到 /usr/src/sys/arch/i386/conf 里面找到 GENERIC 文件，把里面的 #options PAE 最前面的 # 去掉，然后config GENERIC之后编译安装新内核。这个内核就是启用PAE的内核了。接下去的实验就在这个内核上进行。

这个图上暂时能看出的是，一个指针本来是分成3部分或者2部分，现在变成4部分或者3部分了：多了一级。以及，页目录、页表的索引本来是10位，现在变成了9位（多的一级是2位），最后12位在4K内存页的时候是不变的，但是在2MB内存页的时候变成20位了（因为变成2MB了嘛……本来是4MB）。

但是一个更大的区别是，PAE模式下，页表项、页目录项之类的项都是64位的了。其实也就是原来32位前面多了32位高地址，再把原来1024个项变成512个项，其他其实还是一样。然后仔细看，多了好多Reserved的部分，原来32位的时候没有这些东西的。因为PAE实际上就支持到36位地址（注：Intel的说明文档中有这么一句 NOTES: 1. MAXPHYADDR is 36-bits on processors that do not support CPUID.80000008H leaf. On processors that do support CPUID.80000008H, MAXPHYADDR is implementation-specific and indicated by CPUID.80000008H:EAX[bits 7:0]. 但是我没看懂怎么样能让它突破36位。NetBSD下把那个Reversed的最高位拿来用了），所以36位往上的部分要mask掉（P.S. 我最初做实验的时候没有mask掉，结果出来的结果很奇怪，后来把它们dump出来一看才发现reserved那边不是0）。所以有了下面的实验代码：

#include <unistd.h>
#include <cstdio>
#include <fcntl.h>
#include <stdint.h>
using namespace std;

struct PhyAddr {
    uint64_t m_phyaddr;
    PhyAddr(uint64_t addr = 0) : m_phyaddr(addr)
    {
    }
    PhyAddr& operator += (uint64_t offset)
    {
        m_phyaddr += offset;
        return *this;
    }
};

bool AccessPhyMem(PhyAddr addr, bool isRead, void* buf, int len)
{
    int fd = open("/dev/mem", O_RDWR);
    if (fd <= 0)
        return false;
    lseek(fd, addr.m_phyaddr, SEEK_SET);
    if (isRead)
        read(fd, buf, len);
    else
        write(fd, buf, len);
    close(fd);
    return true;
}

struct PageItemEntry {
    uint64_t m_entry;
    operator PhyAddr ()
    {
        PhyAddr r;
        r.m_phyaddr = m_entry & 0xffffff000ull;
        return r;
    }
    bool IsPresent()
    {
        return (m_entry & 1) == 1;
    }
};

struct PageDirPtrEntry : public PageItemEntry {
};


struct PageDirEntry : public PageItemEntry {
    bool Is2MPage()
    {
        return (m_entry & 0x80) != 0;
    }
    operator PhyAddr ()
    {
        PhyAddr r = PageItemEntry::operator PhyAddr();
        if (Is2MPage())
            r.m_phyaddr &= 0xffff00000ull;
        return r;
    }
};

struct PageTblEntry : public PageItemEntry {
};

void SplitPtr(void* ptr, int* nDirPtrIndex, int* nDirIndex, int* nTblIndex, int* nOffset, int* nOffset2)
{
    *nDirPtrIndex = (uint32_t)ptr >> 30;
    *nDirIndex = ((uint32_t)ptr >> 21) & 0x1ff;
    *nTblIndex = ((uint32_t)ptr >> 12) & 0x1ff;
    *nOffset = (uint32_t)ptr & 0xfff;
    *nOffset2 = (uint32_t)ptr & 0x000fffff;
}

int main()
{
    volatile int var = 0xfbfbfbfb;
    int val = 0x12349876;
    int nDirPtrIndex, nDirIndex, nTblIndex, nOffset, nOffset2;
    SplitPtr((void*)&var, &nDirPtrIndex, &nDirIndex, &nTblIndex, &nOffset, &nOffset2);
    try {
        PhyAddr cr3 = syscall(475);
        PhyAddr varAddr;
        PageDirPtrEntry pageDirPtr[4];
        AccessPhyMem(cr3, true, pageDirPtr, sizeof(pageDirPtr));
        if (!pageDirPtr[nDirPtrIndex].IsPresent())
            throw "Fail: Invalid page directory pointer entry.";
        
        PageDirEntry pageDir[512];
        AccessPhyMem(pageDirPtr[nDirPtrIndex], true, pageDir, sizeof(pageDir));
        if (!pageDir[nDirIndex].IsPresent())
            throw "Fail: Invalid page directory entry.";

        if (pageDir[nDirIndex].Is2MPage()) {
            varAddr = pageDir[nDirIndex];
            varAddr += nOffset2;
            AccessPhyMem(varAddr, false, &val, sizeof(val)); 
        } else {
            PageTblEntry pageTbl[512];
            AccessPhyMem(pageDir[nDirIndex], true, pageTbl, sizeof(pageTbl));
            if (!pageTbl[nTblIndex].IsPresent())
                throw "Fail: Invalid page table entry.";
            varAddr = pageTbl[nTblIndex];
            varAddr += nOffset;
            AccessPhyMem(varAddr, false, &val, sizeof(val));
        }

        printf("%x\n", var);
    } catch(const char* msg) {
        fprintf(stderr, "%s\n", msg);
    }
    return 0;
}

效果和上面那个程序是一样的，就是在PAE下的转换。

========================================================
3、x86-64（AMD64，IA-32e）的情况
========================================================

在x86-64（以下简称64位）下，PAE强制开启，逻辑地址的长度扩充为48位，物理地址则可以使用52位（相比起来，32位下32位物理地址最大范围是4G，32位PAE下36位物理地址最大范围是64G，而52位地址则意味着范围到了4194304GB，也就是4096TB）。所以大内存的时候还是要靠64位。

在64位PAE下，页表比32位PAE多了一级，变成四级页表。新增加的一级命名为PML4（page map level 4，继Page Table，Page Directory，Page Directory Pointer之后终于直接简单粗暴用起数字来了）。但是换汤不换药，就是查找的时候多了一级而已。结构和原来基本一致，32位的那几个如果没写错，照着改改在64位下就能跑了。

因为换了64位系统，之前添加过的系统调用还要重新添加一次（好吧我换了一台虚拟机装了个AMD64的）。解包出源代码，然后到 /usr/src/sys/kern/syscalls.master 里面去加系统调用然后make init_sysent.c一下，再到 /usr/src/sys/arch/amd64/conf/files.amd64 添加一个源代码文件，并在源代码文件中写好实现。cr3还是在原来的地方：从lwp结构体获取到pcb，然后pcb_cr3成员就是。

#include <unistd.h>
#include <cstdio>
#include <fcntl.h>
#include <stdint.h>
using namespace std;

struct PhyAddr {
    uint64_t m_phyaddr;
    PhyAddr(uint64_t addr = 0) : m_phyaddr(addr)
    {
    }
    PhyAddr& operator += (uint64_t offset)
    {
        m_phyaddr += offset;
        return *this;
    }
};

bool AccessPhyMem(PhyAddr addr, bool isRead, void* buf, int len)
{
    int fd = open("/dev/mem", O_RDWR);
    if (fd <= 0)
        return false;
    lseek(fd, addr.m_phyaddr, SEEK_SET);
    if (isRead)
        read(fd, buf, len);
    else
        write(fd, buf, len);
    close(fd);
    return true;
}

struct PageItemEntry {
    uint64_t m_entry;
    operator PhyAddr ()
    {
        PhyAddr r;
        r.m_phyaddr = m_entry & 0xfffffffff000ull;
        return r;
    }
    bool IsPresent()
    {
        return (m_entry & 1) == 1;
    }
};

struct PML4Entry : public PageItemEntry {
};

struct PageDirPtrEntry : public PageItemEntry {
};


struct PageDirEntry : public PageItemEntry {
    bool Is2MPage()
    {
        return (m_entry & 0x80) != 0;
    }
    operator PhyAddr ()
    {
        PhyAddr r = PageItemEntry::operator PhyAddr();
        if (Is2MPage())
            r.m_phyaddr &= 0xfffffff00000ull;
        return r;
    }
};

struct PageTblEntry : public PageItemEntry {
};

void SplitPtr(void* ptr, int* nPML4Index, int* nDirPtrIndex, int* nDirIndex, int* nTblIndex, int* nOffset, int* nOffset2)
{
    *nPML4Index = ((uint64_t)ptr >> 39) & 0x1ff;
    *nDirPtrIndex = ((uint64_t)ptr >> 30) & 0x1ff;
    *nDirIndex = ((uint64_t)ptr >> 21) & 0x1ff;
    *nTblIndex = ((uint64_t)ptr >> 12) & 0x1ff;
    *nOffset = (uint64_t)ptr & 0xfff;
    *nOffset2 = (uint64_t)ptr & 0x000fffff;
}

int main()
{
    volatile int var = 0xfbfbfbfb;
    int val = 0x12349876;
    int nPML4Index, nDirPtrIndex, nDirIndex, nTblIndex, nOffset, nOffset2;
    SplitPtr((void*)&var, &nPML4Index, &nDirPtrIndex, &nDirIndex, &nTblIndex, &nOffset, &nOffset2);
    try {
        PhyAddr cr3 = syscall(475);
        PhyAddr varAddr;
        
        PML4Entry pageMapL4[512];
        AccessPhyMem(cr3, true, pageMapL4, sizeof(pageMapL4));
        if (!pageMapL4[nPML4Index].IsPresent())
            throw "Fail: Invalid PML4 entry.";
        
        PageDirPtrEntry pageDirPtr[512];
        AccessPhyMem(pageMapL4[nPML4Index], true, pageDirPtr, sizeof(pageDirPtr));
        if (!pageDirPtr[nDirPtrIndex].IsPresent())
            throw "Fail: Invalid page directory pointer entry.";
        
        PageDirEntry pageDir[512];
        AccessPhyMem(pageDirPtr[nDirPtrIndex], true, pageDir, sizeof(pageDir));
        if (!pageDir[nDirIndex].IsPresent())
            throw "Fail: Invalid page directory entry.";

        if (pageDir[nDirIndex].Is2MPage()) {
            varAddr = pageDir[nDirIndex];
            varAddr += nOffset2;
            AccessPhyMem(varAddr, false, &val, sizeof(val)); 
        } else {
            PageTblEntry pageTbl[512];
            AccessPhyMem(pageDir[nDirIndex], true, pageTbl, sizeof(pageTbl));
            if (!pageTbl[nTblIndex].IsPresent())
                throw "Fail: Invalid page table entry.";
            varAddr = pageTbl[nTblIndex];
            varAddr += nOffset;
            AccessPhyMem(varAddr, false, &val, sizeof(val));
        }

        printf("%x\n", var);
    } catch(const char* msg) {
        fprintf(stderr, "%s\n", msg);
    }
    return 0;
}

和32位PAE的情况基本一样，多了一级，Page Directory Pointer变成了512个元素，以及逻辑地址变成了48位。

==============================================
4、总结一下
==============================================

添加系统调用本来的目的是为了做“x86平台内存分页机制”实验的时候来执行一些特权操作的。这里用的系统是NetBSD 6.1.4 i386版本。

NetBSD的源代码包里有一个syssrc.tgz，编译内核需要的是这个包。到它任意一个镜像FTP服务器上 /pub/NetBSD/NetBSD-6.1.4/source/sets/ 路径即可找到。

我自己操作成功的步骤是：

1、在系统调用表里面添加新系统调用。在 /usr/src/sys/kern/syscalls.master 文件末尾，按照它上面的写法，写一个自己的系统调用。这个文件的开头有各个参数、格式的说明。
其中有一个叫做RUMP的参数，从名字推断不出来是什么，查英语词典也不太有用，因为查出来单词的解释感觉对不上。上网搜了一下，有个叫RUMPKernel的东西，似乎是有点类似用户态跑的内核那种东西，但是和user mode linux又貌似不一样。没找到能理解它到底是做什么的教学，也没从makesyscalls.sh里面看出名堂来。如果定义了RUMP，那么这个系统调用在 /usr/src/sys/rump/librump/rumpkern/rump_syscalls.c 里面会出现；如果没定义，则这里会是另一个占位符。因为不会用，所以先放着……别用这个参数应该不会有什么问题。
例如要写一个能够返回cr3寄存器的值的系统调用，就写这么一个：
475  STD  { int|sys||getcr3(); }
其中int是返回类型，sys是前缀，里面貌似暂时没发现有其他前缀的，写了其他的会怎么样也不知道，试验的结果就是有一些比如syscalls.c文件里面，函数名前面会带着前缀（sys前缀的就不带着），然后在 /usr/src/sys/syscall.h 文件里，在SYS_后面也会继续跟着前缀。到底什么意义不太清楚……后面是函数名和参数。中间空着的那个是兼容性的东西，看了一下之前它们写的，老实说吧也没看懂，加了以后生成的函数名会经过特殊处理。因为不知道怎么用，所以也就先不用它。
所以也就迷迷糊糊跳过了一堆不知道干啥的选择，只挑会用的用，改完了这个文件。

2、生成新的系统调用相关代码。这个 syscalls.master 并不是代码文件，最终要对编译产生影响，还要利用它构建一下系统调用表入口啊啥的东西。有写好的Makefile，只要执行 make init_sysent.c 就可以重新构建好多个文件了，包括系统调用的那些头文件，甚至还有rump那边的代码也重新生成。

3、在文件列表中添加自己的代码文件。到 /usr/src/sys/conf 文件夹下，找一个叫做 files 的文件，里面是会被编译的文件的列表。可以看出 file 是定义一个要被编译的文件，直接在文件中搜索 sys_ 很快能找到它原本放系统调用的地方，往里面添加一个自己的代码文件即可。
但是这样添加的是全局的，想要只针对某一架构，比如cr3啥的是i386、amd64这一类用的，就到 /usr/src/sys/arch/i386/conf/files.i386 里面去添加会比较好。代码也就直接放在 i386 文件夹里面了。
file指令的后面有一些看起来像是用tag来定义文件作用的，使它们在某些配置下文件不会被编译。留空的话应该是什么时候都会被编译吧，不然大部分文件还是总是要被编译，却没有看到大量同一种tag。
如果需要把syscall.h之类的文件复制到 /usr/include/sys 里面，就到 /usr/src/sys/sys 去调用一下 make includes 即可（我没这样做）。

4、因为添加了新的系统调用，还需要实现它们才行。所以要创建一个刚才添加的那个代码文件，写上函数实现。系统调用的函数名，比如刚才那个，是 sys_getcr3。其中sys就是定义的前缀，然后是函数名。对系统调用来说，参数和返回值是固定的（第二个参数“固定”是指针，虽然指针类型会根据系统调用的参数不同而不同），在 /usr/src/sys/sys/syscallargs.h 文件里可以找到函数的原型，三个参数以及返回int。第三个参数一眼应该能看出来，是给你传递返回值的。中间一个参数是给你传递参数的，第一个参数好像是当前进程的一些状态信息，lwp是lightweight process的缩写，具体定义在 sys/lwp.h 里面，字面意思是轻量级进程。要取cr3可以从这里面取（cr3在PCB里面，PCB在那个lwp里面。PCB的定义和CPU类型相关，里面看到的一些 machine/xxxx 文件实际上是 /usr/src/sys/arch/硬件架构名/includes 里面的文件，构建编译环境的时候会被复制到 /usr/src/sys/arch/硬件架构名/conf/配置名/machine 文件夹里。i386的includes文件夹里有一个pcb.h），当然也可以直接用汇编来取。
取传进来的系统调用参数的时候，要用 SCARG 宏来取。SCARG宏的第一个参数是表示参数的结构体的形参，就是系统调用实现的第二个参数：那个struct。第二个参数是成员名。假设有一个这样的系统调用原型：
void getmagicnumber(int* x);
然后变成这样的系统调用：
int sys_getmagicnumber(struct lwp* l, struct sys_getmagicnumber_args* v, register_t* ret);
取参数的时候，就用
int* x = (int*) SCARG(v, x);
即可取到。因为它结构体的定义其实并不是简单把你参数全部排列进去，还考虑到高位优先和低位优先的时候，如果参数比较短，比如参数的类型是2字节的，那么应该放在前两位还是放在后两位这样的事情。所以用这个宏来取会比较通用。
返回值是代表系统调用有没有成功，成功的话返回0就可以了，没成功的话返回错误号。

5、访问用户态传进来的指针的时候，要用copyin和copyout。用man命令可以查到copyin和copyout的说明。其中copyin是从用户态内存复制到内核态内存，后者相反。貌似还有一个版本可以复制到其他进程的内存里去……

这样搞完，就可以直接重新编译内核了。因为没有对内核进行其他配置，所以直接用它原有的 GENERIC的 配置就好了。到 /usr/src/sys/arch/i386/conf 文件夹下面，用命令 config GENERIC 可以生成一个编译环境，然后根据提示 cd ../compile/GENERIC 切换到编译用的文件夹下， make depends 目测是处理依赖关系的，然后再 make 就能编译出内核了。编译非常快，虚拟机里面、第一次编译也就10分钟不到（我原来用的电脑比较慢，又没有硬件虚拟化支持，在虚拟机里要15分钟）。编译之后把生成的 netbsd 文件复制到 / 下，重启即可引导新内核。新内核里面就有自己添加的系统调用了。

最后给出我自己添加的getcr3系统调用的实现：

1、在 /usr/src/sys/kern/syscalls.master 文件末尾添加：

475    STD          { void*|sys||getcr3(); }

然后调用 make init_sysent.c 让它重建一下。

2、创建 /usr/src/sys/arch/i386/sys_mycalls.c 文件，内容是

#include <sys/syscallargs.h>
#include <sys/lwp.h>
#include <machine/pcb.h>
#include <sys/types.h>
#include <sys/systm.h>

int sys_getcr3(struct lwp* l, const void* v, register_t* ret)
{
	struct pcb* pcb = (struct pcb*) lwp_getpcb(l);
	*ret = pcb->pcb_cr3;
	return 0;
}

3、修改 /usr/src/sys/arch/i386/conf/files.i386 文件，找个地方加入

file    arch/i386/sys_mycalls.c

在内核构件完成之后，就可以编译这样的代码来试试看啦

#include <unistd.h>
#include <stdio.h>

int main()
{
	printf("cr3 = %08x\n", syscall(475));
	sleep(1);
	return 0;
}

加入sleep是因为如果反复运行一个进程，会发现系统每次都分配同一个页表给它。但是两个不同的进程是不会有相同的页表的，所以两个一起运行就能看到不同的页表指针。但是这个程序结束得太快，有的时候甚至后面的进程还没运行前面的进程就结束了，于是加上了sleep延缓进程结束，达到目的。最终效果是这样的：

这给接下去做x86内存分页机制的实验提供了前提条件。

这次搞下来，感想是从它头文件里面貌似能翻出好多好东西出来……