Aiur – ZelluX 的技术博客

FastForward for Efficient Pipeline Parallelism
http://systems.cs.colorado.edu/~moseleyt/publications/giacomoni-2008-ppopp-ff.pdf

这篇paper介绍了一种针对多核访问优化的队列， 主要的特点：
1. Lock-free
2. Single-producer/single-consumer
3. Cache-optimized

经典的Lamport的lock-free的队列实现可以用下面的伪代码来表述（同样只适用于单一生产者/单一消费者的情形）：

enqueue_nonblock(data) {
    if (NEXT(head) == tail) {
        return EWOULDBLOCK;
    }
    buffer[head] = data;
    head = NEXT(head);
    return 0;
}
dequeue_nonblock(data) {
    (head == tail) {
        return EWOULDBLOCK;
    }
    data = buffer[tail];
    tail = NEXT(tail);
    return 0;
}

这种实现尽管做到了lock-free，但是存在几个问题，首先是它只适用于sequential consistency内存模型，在relaxed consistency的内存模型里可能会出现类似于Double-Checked Lock(http://techblog.zellux.czm.cn/?p=30)的问题，当然这个问题可以通过插fence指令来解决；第二个问题是这篇paper着重解决的，就是enqueue和dequeue这两个操作都用到了tail和head这两个全局变量，导致多核在读取/修改这两个变量时的为了保证cache coherency会频繁的进行cache的更新，从而导致cache line threading，降低了效率。

接下来看FastForward的实现：

enqueue_nonblock(data) {
    if (NULL != buffer[head]) {
        return EWOULDBLOCK;
    }
    buffer[head] = data;
    head = NEXT(head);
    return 0;
}

dequeue_nonblock(data) {
    data = buffer[tail];
    if (NULL == data) {
        return EWOULDBLOCK;
    }
    buffer[tail] = NULL;
    tail = NEXT(tail);
    return 0;
}

这个版本的队列实现粗看和Lamport的那个区别很小，而实际上这里解决了一个重要的问题：解除了head和tail的共享问题。dequeue操作只需要关心tail，enqueue操作只关心head，这样两个变量就变成CPU本地的资源了，不需要做任何同步。当然这个实现同样局限于sequential consistency，不过加fence保证顺序的overhead不大。最后测试中这个版本的单次操作比Lamport的快3.7倍左右，可见这样一个小小的改动对性能的提升起了举足轻重的作用。

paper后面还严格的证明了这种队列实现的正确性，即保证了消费者读出的数据的顺序和它们在生产者写入时的顺序一致，此处略去。

同样是今年寒假读的

---

两年前的paper的升级版，这次是利用Disco在一个多核电脑上跑多个操作系统并虚拟成一个cluster。主要解决了两个问题，一是容错性，当硬件错误发生时如何把影响缩小到一个单元里；二是资源的管理，如何高效地在虚拟机间动态的分配物理CPU和内存。

容错和动态资源管理在某种程度上相互矛盾的。因此在分配资源的时候，要尽可能的减少一个虚拟机使用的cell数。这里的cell是指相对独立的容错 单元，后面还提到一个node的概念，Origin 2000上每个node含两个CPU。CD还提供了两种快速的进程间通讯的primitive，RPC和message。

关于容错，有这么个问题，Disco在操作系统和硬件之间多弄了这么一层虚拟层，某个虚拟的操作系统出问题时可以不影响到其他操作系统，可是操作系 统不也是保证了进程间的互相独立，当一个进程异常时不影响另一个进程吗？多设立一层Disco对容错有什么帮助吗？这个问题的答案在于，VMM的代码量很 小，可以看作是一个可信的系统软件层(trusted system software layer)，因为当VMM的代码行数少于五万行时，它的复杂度就和其他可信的层（如cache coherence protocol)差不多了，这个复杂度比现代操作系统的复杂度差不多要低两个等级。

传统操作系统通常使用一个全局的run queue来管理和分配进程在多个CPU上的运行，这种实现不适合CD的容错要求，也带来了更多的contention。所以CD为每个VCPU维护了一 个run queue，同时引入了VCPU migration的机制来平衡VCPU的负载，按颗粒度分三级，intra-node intra-cell inter-cell。内存管理方面，CD实现了memory borrowing机制，使得一个cell可以暂时的从其他cell里获得内存，如果这种借用受限于容错性，就只能使用原来的paging机制了。

CPU管理

CD有两个CPU平衡策略，一个在处理器空闲时发生，另一个定期平衡VCPU的负载。空闲调度时要同时考虑gang scheduling的限制以及因转移破坏的cache/node affinity。而定期的调度则是通过一棵全局的load tree的辅助来实现的。此外还需要一个scalable gang scheduler来保证效率，CD的调度器总是选择优先度最高的gang-runnable VCPU（等待时间最多），然后通过低开销的RPC通知那些拥有(和这个VCPU同属于一个虚拟机的VCPU)的处理器，这些处理器在收到消息后，立即停 止当前正在运行的VCPU，服从同一调度策略。通过这种方式实现的调度就不需要一个全局的管理器了。

内存管理

每个cell都维护了自己的freelist，每次接收请求时都优先分配本地node上的资源。内存借用也很直接，需要借用内存的cell向有空闲内存的cell发个RPC即可，RPC的返回结果是一个machine page的list。

测试结果

测试中CD是作为kernel process跑在IRIX 6.4上的，也就是说VMM的下面还有一层操作系统，主要是为了利用IRIX提供的设备驱动。CD在每个CPU上跑一个线程，完全占有整个CPU，IRIX只在需要设备驱动时才被激活。

测试比较了两个测试环境，跑在真机上的IRIX 6.4（增加了多核支持），和跑在CD上的IRIX 6.2。最后的结果显示大部分情况下（单核、8核、32核）后者和前者的差距在10%以内，最差情况下也只有20%的overhead。接下来的容错机制 的overhead同样很小，不高于2%。

趁还在编译内核的时候把以前写过的东西都转过来，今年寒假读的 (SOSP ’97)

Disco: running commodity operating systems on scalable multiprocessors

---

很早的一篇paper，发表的第二年Rosenblum就创办了VMWare。这篇paper介绍了一个跑在 FLASH机器上的虚拟机Disco，FLASH的架构是实验性质的cache coherent non-uniform memory architechure(ccNUMA)。

传统的VMM在实现上主要有三个问题

• overhead，例如特权指令需要由VMM模拟
• 资源管理，缺乏对资源配置的细粒度的了解，导致资源分布不均（如调度一个没有价值的计算任务）
• 通讯和共享，不同虚拟机是不是应该简单的看成是享有相同硬件资源的完全独立的操作系统？

实现细节

1. 虚拟CPU

Disco虚拟CPU时是把指令放到物理CPU上直接执行的。当调度到某个虚拟CPU时，Disco就把物理机的寄存器设置为虚拟机的寄存器并跳转到相应的PC。

直接执行的好处在于大多数操作能获得和在真机上跑一样的效率，而难点在于处理不能直接放到真机上运行的指令，如修改tlb，访问物理内存等。

Disco为每个虚拟CPU记录了一个类似于传统操作系统中process table entry的数据结构。为了模拟特权指令，Disco还在这个数据结构中维持了虚拟CPU的特权寄存器和tlb的内容。

在MIPS处理器上，Disco运行在kernel mode掌握着对硬件的完全控制；控制器交给虚拟机的操作系统时，Disco把CPU置为supervisor mode；当进入user mode时取消。Supervisor模式允许操作系统访问受保护的内存区域(supervisor segment)，但仍不能执行特权指令，也不能访问物理内存。诸如page fault的trap发生时，vmm会捕获到这个异常，修改相应的特权寄存器并跳转到虚拟机的trap vector。

2.虚拟内存

Disco增加了一层物理地址到机器地址的转换。虚拟机使用从0开始的物理地址，大小和为虚拟机的内存相等，Disco把这些物理地址映射到了 FLASH的40位机器地址上。这种映射的实现借助于MIPS处理器的software-reloaded TLB，当操作系统尝试在TLB中插入一个virtual-to-physical的映射时，Disco会把这里的physical address改成对应的machine address，这样之后通过这条TLB记录的地址访问就不需要再经过VMM的处理了，没有额外的overhead。

为了方便计算TLB地址，Disco为每个虚拟机记录了一个pmap数据结构，每个pmap结构对应着虚拟机的一个物理页。pmap包含了一个指向 机器内存的引用，以及指向虚拟地址的映射（虚拟地址可能有多个，原文中用了复数形式），这主要用于页面被VMM回收时TLB的重置。另外MIPS处理器为 每个TLB记录标记了一个地址空间标识符（ASID, address space identifier），用来防止context switch时不必要的TLB刷新。Disco为了简单化处理，就在物理CPU被调度为另一个虚拟CPU时刷新TLB，这样ASID就能直接使用虚拟机提 供的了。

这样的处理带来了性能问题，由于TLB在虚拟CPU切换时会被刷新，带来了额外的TLB miss，而TLB miss由于需要被模拟，它的代价很大。为了减少这种性能影响，Disco维持了一个virtual-to-machine的二级软TLB，TLB miss发生的时候首先查看软TLB有没有相关的记录，如果找不到再交给虚拟机上的操作系统去处理。这种处理的影响就是虚拟机所看到的TLB会比实际 CPU的TLB大很多。

3. NUMA 内存管理

不怎么熟悉NUMA，这部分先粗读了，大致思想是通过动态的页面转移和复制维持locality，从而避免remote cache miss。

4. 虚拟IO设备

增加特殊的设备驱动是最清晰的实现方法，每个Disco设备都定义了一个monitor call，供设备驱动传参调用。对于支持DMA操作的设备，Disco也需要截获这些DMA请求并转换为相应的machine address。对于仅有一个虚拟机访问的设备，Disco只要保证访问的排外性并翻译DMA请求即可，而不需要虚拟IO资源。截获所有DMA操作的一个 好处是Disco可以在虚拟机间共享磁盘和内存资源。

5. Copy-on-write disks

DMA请求被截获时，如果请求的磁盘块已经在内存里了，就不需要再访问磁盘。如果请求的大小正好是虚拟机页面大小的整数倍，直接把对应的物理页映射 到虚拟机里就行，另外考虑到以后可能会修改这部分内存，需要将那些页面设为read-only，从而实现copy-on-write，同时这些处理对虚拟 机完全透明的。

磁盘被写入时，分两种情况处理：对于持久性的磁盘，如包含用户文件的，同一时间Disco只允许一个虚拟机挂载这个磁盘，其他虚拟机可以通过NFS 等分布式文件系统协议访问它；而对于非持久的磁盘，如根磁盘，使用copy-on-write的策略，即在写操作发生时记录下被修改的扇区，而copy- on-write的磁盘自身不会被修改。

6. 虚拟网络接口

虚拟机间通过NFS共享文件时，不做特殊处理的话，客户端和服务器端会各有一份buffer cache保存共享的数据。因此copy-on-write的策略同样被用在了网络实现上，虚拟机间的信息传送是通过在发送方和接收方上映射同一个只读页来完成的。

SPLASHOS: A Specialized Operating System

SPLASHOS是一个特制的跑在Disco上的library os，包括了线程创建、同步操作、libc函数和一个用于文件IO的NFS客户端栈，应用程序和这个library os链接后就能直接跑在Disco上，配合跑多个这样的操作系统的话就能利用起整个机器的资源。另外这种操作系统也不需要自己处理page fault等异常了，直接交给虚拟机就行。

测试结果

整个测试是跑在SimOS这个模拟器上的，模拟的配置是一个特点类似于FLASH的large-scale multiprocessor。测试的workload是四个比较具有代表性的，并行编译(pmake)，verilog模拟，raytrace和 sybase关系数据库。

测试的结果，跑单个workload的时间比不用Disco慢3%到16%

Paper标题是DFTL: A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings，PSU发表在ASPLOS 09上。这篇paper对我来说更像是篇flash存储的科普文。

flash存储单元分block和page，每个block有32/64个page，一个page有512/2048K大小。flash的一个缺点在于改写数据时只能先把要改写的block清空，然后再写，由于block的颗粒度比较大，这就带来了比较严重的性能问题。所以现在的flash都在驱动层维护了一张对文件系统透明的logical-to-physical address的映射表(Flash Translation Layer)，这样改写时只要先写在预先清空的page上，再把映射表的对应项的物理地址改成新的page的地址，然后把原来要改的页置为invalid，等gc去清空即可。

如果为每个page都在内存中维护一份映射关系，会占用比较大的内存空间。以往的ftl的实现试图在page-level和block-level的映射中找平衡，但效果都不甚理想，尤其在随机写比较频繁时会产生比较严重的gc负荷，从而影响写操作的反应速度（因为预先清空的页面不足时需要先做gc）。这篇paper提出的DFTL可以比较好的减少gc的负荷，同时近需要很小的内存空间，前提是程序访问flash的locality很好。

感觉DFTL的大致思想仿照了二级页表和TLB：flash上的一些page保存了page-level的映射，分散在整个flash中，在内存里面有一个block-level的映射表，记录了每个page-level映射表在flash中的地址。内存中的映射表相当于二级页表中的page directory，指向了flash上的page-level映射表（page table），另外内存中还有一个全局的page-level的映射表用于记录最近访问到的page的logical-to-physical映射，类似于TLB。这样如果程序locality很好的情况下大多数情况下只要查询这张表就行了。

写完代码测试时重复的最多的步骤就是

1. 编译，复制vmlinuz和xen.gz
2. 重启VMware虚拟机
3. 启动domainU xm create domU.conf
4. 开一个screen窗口attach到domainU的console xm console #domid
5. 在domainU中运行测试程序

于是写了个自动执行3 4 5的脚步，主要用到了熊熊推荐的pexpect，这东东很赞啊

为了提高用户体验，读取domainU的启动信息时我采用的方法是读一行输出一行，读到结尾登陆字符时通过超时设置退出循环，这样可能效率比较低，不过测试脚本也不care这个了

实际使用时碰到了另一个问题，domainU执行完自动命令后命令行会出现很严重的对齐问题，最后发现登陆后运行一次reset就可以了。

脚本如下

#!/usr/bin/python

# Automatic test script for Xen DomainU
# Author: zellux

import pexpect, os

conf = {
    'login_name'     : 'm2-vm2',
    'domainU_name'   : 'R900-DomU0',
    'domainU_conf'   : '/home/wyx/domU1',
    'domainU_id'     : '2',
    'domainU_user'   : 'wyx',
    'domainU_passwd' : 'wyx',
    }

# Command to be executed after domainU starts
cmd = """
cd m2
cd reg_test
./base_test -t affinity
"""

# Create domainU
print '[M2 Test] Starting domainU ...',
pexpect.run('xm create %(domainU_conf)s' % conf)
print 'done'

# Get domainU id
print '[M2 Test] SGetting domainU id ...',
ret = pexpect.run('xm list')
for line in ret.split('\n')[1:]:
    part = line.split()
    if part[0] == conf['domainU_name']:
        conf['domainU_id'] = part[1]
        break
print 'done'

# Run domainU commands
child = pexpect.spawn('xm console %(domainU_id)s' % conf)
print '[M2 Test] SReading from domainU console...'
try:
    while True:
        child.expect('\n', timeout=1, )
        print child.before.split['\n'][-1]
except:
    pass

child.expect('%(login_name)s login:' % conf)
child.sendline(conf['domainU_user'])
child.sendline(conf['domainU_passwd'])

for line in cmd.split('\n'):
    child.sendline(line)

try:
    child.expect(pexpect.EOF, timeout=1)
except:
    pass
print child.before
child.interact()

MIT出品，发在1984年的TOCS上，很值得细细品味的一篇paper，可惜做presentation时由于是第一次在组会上讲，效果很差。

这篇paper的核心思想就是，在设计一个系统各个层次的功能时，如果把某个功能放到某一层时无法保证功能的完全可靠，那就干脆不要做，除非是为了性能等其他因素考虑。

这里举了一个文件传输的例子，假设要把电脑A的资料通过网络传输给电脑B，而其中文件系统、传输程序、网络等各个子系统都有可能出现问题，那么如果保证传输的可靠，即B能完整不出错的得到A的数据并保存呢？

如果把验证做在子系统，比如网络数据包校验，文件系统里也为每个文件加checksum，读出来的时候验证下，从而避免磁盘出错的可能。但是这些常见的措施只能保证部分环节的正确性，降低出错的可能，并不能从根本上保证数据传输的可靠性。举个例子来说，这里如果文件传输程序出了bug，网络和文件系统里面的检查即使通过了，最后的结果还是错误的。

针对这个问题的End-to-End的解决方案很简单，就是在电脑A上保留一份该文件的checksum，电脑B接收并保存后再算一次checksum，相等就说明传输成功了（当然这里要钻牛角尖的话也可以说还是有可能出问题的，但是这个概率已经小到可以完全忽视的地步了，在这里我们假设checksum符合就说明这个环节没有问题）。而这种保障措施不需要任何子系统的参与，也就是End-to-End的。

那么当一个子系统对要做的事情并不完全了解的时候（比如这里的网络传输层只能保证对方接受到的数据包的正确性，却不知道文件有没有损坏），是不是就没必要在子系统实现这个功能了呢？从正确性是来说是，但是考虑到其他方面，在子系统作检查还有另外两个好处：

一是大大的降低了出错的概率，准确的说是出错的概率呈指数级降低，这在并不需要一种完美的保障措施的场合下还是很有用的；

二是提高了性能，如果只用End-to-End的检验的话，有可能传输中丢了个包要等整个文件传输完毕做checksum的时候才会发现；而如果中间在网络传输层加个丢包检验的话就可以及早的发现错误并恢复了。这个问题在网络不可靠，或者文件很大的情况下尤为突出，仅仅是End-to-End的保证会使传输时间的期望值随着文件大小的增加呈指数级上升。

上网络课的时候有一次老师的问题就是既然OSI七层协议的上层（如transport层）已经做了校验措施，为什么下层（如data-link层）还会有“多余”的error detection呢？当时我想到的一个答案就是为了性能考虑，因为那会儿正好在读这篇paper

但是并不是说把功能放到子系统里就一定能提高性能了。如果子系统里面塞满了各种并不是上层都必需的检验机制，整个系统的性能势必会受到影响。所以这个trade-off值得深思熟虑。Exokernel的论文就提出了传统的操作系统中存在的这样一个问题，底层内核过于冗余，影响了应用程序性能，也隐藏了一些对部分应用程序比较重要的信息（比如给数据库提供磁盘原生数据访问的API可以获得更优的性能，另外应用程序也应当能控制自己发生缺页错误时候的行为）。

这里的“End”在不同的环境下会对应不同的模块。比如在网上聊天这个通信过程中，没有必要在底层做很多校验来保证数据包的完整性，这时候及时性更重要，当数据包丢失或者数据出错时，会有一个更常用的End-to-End的解决方案：没听清的那一方通过语音要求重述就行了，“我听不清，能再说一遍刚才的话吗？”，而此时的End自然是谈话双方。如果换一种情形，在语音留言系统中，就需要保证传输的正确性了，因为这时候数据的及时性变得很次要，而留言系统的特点要求用End-to-End的验证加上底层的措施来保证一方的语音信息尽可能忠实的保存到另一方的留言系统中。

修改于 2010.2.16

在默认的基础上，把这几个都改成built-in (*)，通过Xen启动时就不需要额外加载initrd了

2010.1.19更新：支持网络

Device Drivers
	SCSI device support  --->
		<*>   SCSI disk support
		<*>   SCSI generic support
		      SCSI low-level drivers  --->
			[*] LSI Logic New Generation RAID Device Drivers
			<*> Serial ATA (SATA) support
				<*>   Intel PIIX/ICH SATA support
	Fusion MPT device support  --->
		<*> Fusion MPT ScsiHost drivers for SPI
		<*> Fusion MPT ScsiHost drivers for FC
		<*> Fusion MPT ScsiHost drivers for SAS
		(128) Maximum number of scatter gather entries (16 - 128)
		<*> Fusion MPT misc device (ioctl) driver
		<*> Fusion MPT LAN driver
	Network device support  --->
		Ethernet (10 or 100Mbit)  --->
			[*] EISA, VLB, PCI and on board controllers 

<*>   AMD PCnet32 PCI support

抓抓大牛的博客(http://www.cnblogs.com/JeffreyZhao)上看到的链接，原文地址是
http://blog.objectmentor.com/articles/2009/02/26/10-papers-every-programmer-should-read-at-least-twice

貌似我只读过那篇Reflections on Trusting Trust，水木的Programming版搜索作者为modico的帖子的前四篇就是介绍这篇paper的。

先贴个列表，改天好好读一读

1. On the criteria to be used in decomposing systems into modules – David Parnas
2. A Note On Distributed Computing – Jim Waldo, Geoff Wyant, Ann Wollrath, Sam Kendall
3. The Next 700 Programming Languages – P. J. Landin
4. Can Programming Be Liberated from the von Neumann Style? – John Backus
5. Reflections on Trusting Trust – Ken Thompson
6. Lisp: Good News, Bad News, How to Win Big – Richard Gabriel
7. An experimental evaluation of the assumption of independence in multiversion programming – John Knight and Nancy Leveson
8. Arguments and Results – James Noble
9. A Laboratory For Teaching Object-Oriented Thinking – Kent Beck, Ward Cunningham
10. Programming as an Experience: the inspiration for Self – David Ungar, Randall B. Smith

作者博客后面还新增了对它们的简要评论

今天下午真是惊悚，我想把机房的winxp分区删了，ftp上好放点美剧，结果winxp的那个分区是扩展分区，删掉后导致linux的几个分区都消失了。赶紧把硬盘拆下来装到实验室用Disk Genius修复了下，数据基本没什么损坏，分区表还是有点问题。差一点俺就见不到这个博客了 =_=

然后把昨天折腾了一晚上没搞定的debian 4安装搞定了，关键在于netinst.iso的版本号要和hd-media的完全一致，4.0r7。

1. 编译xen/linux所需的包
apt-get install gettext zlib1g-dev python-dev libncurses-dev libssl-dev libx11-dev bridge-utils iproute gawk

另外 initrd文件的生成需要安装initrd-tools包

2. kernel中memory barrier的实现很简单，barrier宏展开后就是
asm volatile(“” : : : “memory”)
这样就保证了在barrier()执行后，cpu不会直接读取寄存器中cache的内存值。

3. 生成initrd
mkinitramfs -o /boot/initrd-2.6.18.8-xen.img 2.6.18.8-xen

4. syscall和m2_fastcall的性能测试
测的是getpid()函数，当然为了保证m2_fastcall不在运行逻辑上吃亏，它的对应功能仅仅是返回current->pid，第一次测出来的结果是syscall明显由于m2_fastcall。宋大牛指出很有可能是glibc做了缓存，果然，自己用汇编发软中断后的数据就正常了。

1. x86_64上不支持segment机制，Xen是通过页表机制来控制访问权限的，Xen及其相关数据驻留在0xffff8000 00000000 – 0xffff87ff ffffffff，也就是在原来的kernel space的低地址部分，而x86_32上驻留在最上面的。

[include/asm-x86/config.h]
/*
 * Memory layout:
 *  0x0000000000000000 - 0x00007fffffffffff [128TB, 2^47 bytes, PML4:0-255]
 *    Guest-defined use (see below for compatibility mode guests).
 *  0x0000800000000000 - 0xffff7fffffffffff [16EB]
 *    Inaccessible: current arch only supports 48-bit sign-extended VAs.
 *  0xffff800000000000 - 0xffff803fffffffff [256GB, 2^38 bytes, PML4:256]
 *    Read-only machine-to-phys translation table (GUEST ACCESSIBLE).
 *  0xffff804000000000 - 0xffff807fffffffff [256GB, 2^38 bytes, PML4:256]
 *    Reserved for future shared info with the guest OS (GUEST ACCESSIBLE).
 *  0xffff808000000000 - 0xffff80ffffffffff [512GB, 2^39 bytes, PML4:257]
 *    Reserved for future use.
 *  0xffff810000000000 - 0xffff817fffffffff [512GB, 2^39 bytes, PML4:258]
 *    Guest linear page table.
 *  0xffff818000000000 - 0xffff81ffffffffff [512GB, 2^39 bytes, PML4:259]
 *    Shadow linear page table.
 *  0xffff820000000000 - 0xffff827fffffffff [512GB, 2^39 bytes, PML4:260]
 *    Per-domain mappings (e.g., GDT, LDT).
 *  0xffff828000000000 - 0xffff8283ffffffff [16GB,  2^34 bytes, PML4:261]
 *    Machine-to-phys translation table.
 *  0xffff828400000000 - 0xffff8287ffffffff [16GB,  2^34 bytes, PML4:261]
 *    Page-frame information array.
 *  0xffff828800000000 - 0xffff828bffffffff [16GB,  2^34 bytes, PML4:261]
 *    ioremap()/fixmap area.
 *  0xffff828c00000000 - 0xffff828c3fffffff [1GB,   2^30 bytes, PML4:261]
 *    Compatibility machine-to-phys translation table.
 *  0xffff828c40000000 - 0xffff828c7fffffff [1GB,   2^30 bytes, PML4:261]
 *    High read-only compatibility machine-to-phys translation table.
 *  0xffff828c80000000 - 0xffff828cbfffffff [1GB,   2^30 bytes, PML4:261]
 *    Xen text, static data, bss.
 *  0xffff828cc0000000 - 0xffff82ffffffffff [461GB,             PML4:261]
 *    Reserved for future use.
 *  0xffff830000000000 - 0xffff83ffffffffff [1TB,   2^40 bytes, PML4:262-263]
 *    1:1 direct mapping of all physical memory.
 *  0xffff840000000000 - 0xffff87ffffffffff [4TB,   2^42 bytes, PML4:264-271]
 *    Reserved for future use.
 *  0xffff880000000000 - 0xffffffffffffffff [120TB, PML4:272-511]
 *    Guest-defined use.
 */

2.shadow page table主要用在两个地方，一是full-virtualization下的页表维护，overhead很大，不过有了VT-x或者AMD-V的硬件支持后会在一定程度上减少这个代价；二是在guest os被live-migrate的时候，需要一个shadow page table来跟踪转移后被修改的页面。

今天还搞清楚了以前我一直模糊的一个概念。以前翻过一点那本The Definitive Guide to Xen Hypervisor，里面提到一个writable page table，然后我就把这个东西和后来看的那篇paper的shadow page table搞混了，其实是两个完全不一样的东西。shadow page table如前文所说，仅用于full-virtualization的情况，硬件访问到的是Xen维护的shadow page table而不是guest page table；而writable page table则是用在para-virtualization的场合，

3. arch/x86/traps.c::do_page_fault()->fixup_page_fault()

当满足以下几个条件时，xen调用ptwr_do_page_fault()处理guest os更新页表的情况：
(1) 不在irq中断过程中 且 中断未被禁用(eflags的if被置上)
(2) 出错地址不属于hypervisor的保留地址
(3) guest os处于kernel mode
(4) error code的write位被置上，而reserved位未被置上

接下来看这个关键性的ptwr_do_page_fault()，通过guest_get_eff_l1e获得被访问的virtual address对应的PTE，然后获得这个PTE对应的page，接下来确定当前的情况是guest os正在尝试修改一个PTE，要满足下面几个条件：
(1) present位被置上，rw位没有被置上
(2) mfn(machine frame number)正确，即小于最大值，检查的代码是!mfn_valid(l1e_get_pfn(pte))，这是由于是在pv模式下，mfn=pfn。
(3) page的类型PGT_l1_page_table，即最下层的page table
(4) page的引用计数不为0
(5) page的owner为当前domain

这些检查都通过后，调用x86_emulate()函数执行ptwr_emulate_ops代码。

另外Xen 3.3.1这里似乎利用了reserved bit位，根据Intel手册的说法，When the PSE and PAE flags in control register CR4 are set, the processor generates a page fault if reserved bits are not set to 0. 以及The RSVD flag indicates that the processor detected 1s in reserved bits of the page directory, when the PSE or PAE flags in control register CR4 are set to 1。于是就可以在第一次guest os试图修改pte被xen截获后把这个reserved bit给置上，下次访问前还是会因为这个reserved bit而出page table，此时检查下guest os改的machine address是否正确，然后再把reserved bit给清零即可。