同样是今年寒假读的 容错和动态资源管理在某种程度上相互矛盾的。因此在分配资源的时候，要尽可能的减少一个虚拟机使用的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机制了。 测试比较了两个测试环境，跑在真机上的IRIX 6.4（增加了多核支持），和跑在CD上的IRIX 6.2。最后的结果显示大部分情况下（单核、8核、32核）后者和前者的差距在10%以内，最差情况下也只有20%的overhead。接下来的容错机制 的overhead同样很小，不高于2%。 阅读全文 →

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很好的情况下大多数情况下只要查询这张表就行了。 阅读全文 →

写完代码测试时重复的最多的步骤就是 编译，复制vmlinuz和xen.gz 重启VMware虚拟机 启动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 . 阅读全文 →

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. 阅读全文 →

http://emacsbugs.donarmstrong.com/cgi-bin/bugreport.cgi?bug=2800Emacs在窗口过窄时使用minibuffer的auto-complete功能会挂掉，就把这bug报告上去了。负责人貌似是MIT的物理系毕业的博士？敬仰下。 从后面回复来看，似乎这个bug emacs22里也有，应该还是蛮常见的呀，为啥之前没人report呢@@ 不管怎么说，总算也给Emacs出了份力，嘿嘿。 阅读全文 →

在默认的基础上，把这几个都改成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 阅读全文 →

最近有点忙，今天总算在某个课题deadline前把论文憋出来交上去了。跑这儿来推荐两篇上个月看到的比较有意思的paper，都比较偏理论，也很老。 今天写介绍下第一篇，剑桥大学的A Logic of Authentication，中了SOSP ‘89，整理后发在1990年的ACM Transactions on Computer Systems上。 http://www.csie.fju.edu.tw/~yeh/research/papers/os-reading-list/burrows-tocs90-logic.pdf （另一篇是Safe Kernel Extensions Without Run-Time Checking，改天再写点介绍） 这篇paper的主要工作是通过构造一种多种类的模态逻辑(many-sorted model logic)，来检查网络中验证协议的安全性。 基础的逻辑分三部分： 原语，如验证双方A和B，以及服务器S，下文用P Q R泛指 密钥，如K_ab代表a和b之间的通讯密钥，K_a代表a的公钥，{K_a}^{-1}代表对应的私钥，下文用K泛指 公式（或者陈述），用N_a, N_b等表示，下文用X Y泛指 接下来定义以下约定（constructs） P 信任 X: 原语P完全信任X P 看到 X: 有人发送了一条包含X的信息给P，P可以阅读它或者重复它（当然通常是在做了解密操作后） P 说了 X: 原语P发送过一条包含X的信息，同时也可以确定P是相信X的正确性的 P 控制 X: P可以判定X的正确与否。例如生成密钥的服务器通常被默认为拥有对密钥质量的审核权。 X 是新鲜的: 在此之前X没有被发送过。这个事实可以通过绑定一个时间戳或者其他只会使用一次的标记来证明。 P <-K-> Q: P和Q可以通过共享密钥K进行通讯，且这个K是好的，即不会被P Q不信任的原语知道。 K-> P: P拥有K这么一个公钥，且它对应的解密密钥K^{-1}不会被其他不被P信任的原语知道。 P <=X=> Q: X是一个只被P和Q或者P和Q共同信任的原语知道的陈述，只有P和Q可以通过X来相互证明它们各自的身份，X的一个例子就是密码。 {X}_K: X是一个被K加密了的陈述 _Y: 陈述X被Y所绑定，Y可以用来证明发送X的人的身份 好了，总算把这些约定列完了，然后来看看通过这些约定能推出一些什么东东： 如果 P 相信 (P <-K-> Q), 且 P 看到 {X}_K，那么 P 相信 Q 说了 X。这个例子很简单，既然P Q有安全的密钥K，那么P看到通过K加密后的X肯定认为就是Q发出的。 阅读全文 →

今天下午真是惊悚，我想把机房的winxp分区删了，ftp上好放点美剧，结果winxp的那个分区是扩展分区，删掉后导致linux的几个分区都消失了。赶紧把硬盘拆下来装到实验室用Disk Genius修复了下，数据基本没什么损坏，分区表还是有点问题。差一点俺就见不到这个博客了 =_= 然后把昨天折腾了一晚上没搞定的debian 4安装搞定了，关键在于netinst.iso的版本号要和hd-media的完全一致，4.0r7。 编译xen/linux所需的包 apt-get install gettext zlib1g-dev python-dev libncurses-dev libssl-dev libx11-dev bridge-utils iproute gawk 另外 initrd文件的生成需要安装initrd-tools包 kernel中memory barrier的实现很简单，barrier宏展开后就是 asm volatile(”” : : : “memory”) 这样就保证了在barrier()执行后，cpu不会直接读取寄存器中cache的内存值。 生成initrd mkinitramfs -o /boot/initrd-2.6.18.8-xen.img 2.6.18.8-xen syscall和m2_fastcall的性能测试 测的是getpid()函数，当然为了保证m2_fastcall不在运行逻辑上吃亏，它的对应功能仅仅是返回current->pid，第一次测出来的结果是syscall明显由于m2_fastcall。宋大牛指出很有可能是glibc做了缓存，果然，自己用汇编发软中断后的数据就正常了。 阅读全文 →

Fishing reading Xen 内存管理综述 and have a superficial look on Xen source code. 在Debian x86-64上编译并安装了Xen 3.3.0，安装需要的几个包zlib1g-dev python-dev libncurses-dev libssl-dev libx11-dev bridge-utils iproute gawk gettext 3.interrupt gate的注册 [arch/x86/traps.c] set_swint_gate(TRAP_int3,&int3); /* usable from all privileges */ set_swint_gate(TRAP_overflow,&overflow); /* usable from all privileges */ set_intr_gate(TRAP_bounds,&bounds); set_intr_gate(TRAP_invalid_op,&invalid_op); set_intr_gate(TRAP_no_device,&device_not_available); set_intr_gate(TRAP_copro_seg,&coprocessor_segment_overrun); set_intr_gate(TRAP_invalid_tss,&invalid_TSS); 以page_fault为例 SAVE_ALL负责把rsp以外的15个寄存器的值保存入栈，然后从exception table中读出对应的函数地址，并调用(do_page_fault)。 新年第一次例会讲了两篇发在SOSP ‘1967上的古董paper Dijkstra的The structure of the “the”-multiprogramming system，第一次提出了操作系统的分层结构，从而可以运行多个任务，另外里面还提出了semaphore等用来解决concurrent问题的方案，以及类似virtual address的想法，如果这两个概念也是在这个paper第一次提出的话，我只能说Dijkstra是个神了 @.@ 第二篇是Peter Denning的The working set model for program behavior，里面用了大量的数学公式（主要是概率统计方面）推导得出了\tau和traverse time T的关系，这里的\tau是一个参数，某个页面在经过\tau时间没有被访问后即被认为是可以替换的，这样就不需要用LRU之类的算法花时间来寻找一个victim page了。paper后面还给出了调度和资源分配的算法。 阅读全文 →

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). 阅读全文 →