Multi-Execution: Multicore Caching for Data-Similar Executions 这篇paper针对以multi-execution这种模式运行的程序提出了一种新的cache手段。 所谓multi-execution，指的是同时运行同一个程序的多个进程，而它们的输入数据又互不相同。这种模式在machine-learning领域比较常见，一些相对独立的learner可以以并行的方式被训练，而它们的结果可以通过一种叫做boosting的方式合并起来。给我的感觉似乎有点像mapreduce？ 然后呢，作者们发现以这种方式运行的程序进程的数据有很大一部分是相同的，在合并cache数据上可以做一下文章，节省cache的使用。 于是这篇paper提出了一种叫做mergeable cache的架构，用于代替传统的L2 cache，L1 cache还是传统的cache架构。首先假设相同的数据的虚拟地址往往也是相同的（应该去掉了address space randomization的影响），以类似Page Coloring的策略进行物理页的分配，使得不同进程同一虚拟地址所对应的物理页都是相邻的。然后把虚拟地址的头9位作为cache tag，再为每个cache line记录一个bit vector用以表示某个processor的数据是否保存在这条cache line中。于是L2 cache hit当且仅当： 虚拟地址的头9位等于cache line的tag cache line中的bit vector的processor对应的位被置上 另外为了简化cache策略，L1和L2的数据内容是互斥的，或者说一段被cache的数据要么在L1，要么在L2，不可能同时存在于两者中。这样一来L2就只有从L1淘汰出来的数据了，而L2中的数据修改分三步完成： 把数据从L2中标记为不存在（对应processor的bit vector位置0） 数据进入L1 修改数据 这就是这篇paper提出的cache架构的主要内容，后面的evaluation部分做的也很不错。从数据中可以看出合并的cache里面dirty cache占了比较大的比例，从而说明简单的copy-on-write策略的效果不会很好，因为copy-on-write只能合并clean cache。最后平均的speedup提升在2.5x左右，很不错。但是对于数据无关的并行程序运行，会产生一定的overhead，此时可以选择传统的L2 cache机制。 阅读全文 →

读 Multi-Execution (ISCA ’09) 的时候看到的名词，中文叫做高速缓冲器页着色，有点拗口，还是用英文术语好了。 早期的处理器缓存都是映射虚拟内存的，这样带来两个问题，一是进程切换等场合下需要清空缓存，二是由于多个虚拟地址可能指向同一个物理地址，因此会出现缓存中数据别名的问题(data aliasing)。 于是现代的处理器更多的通过物理地址进行数据缓存，这也引入了另一个问题，虚拟内存中看到的相邻的两块数据在缓存中很有可能是不相邻的，如果操作系统分配物理页时不考虑这点就会影响性能。 举例来说，假设CPU能缓存4个物理页，缓存策略是 CS:APP 中提到的最简单的方式，即第n号缓存只用于物理页号除4余数为n的物理页(n=0,1,2,3)，比如第2号缓存对应于2,6,10,..号页面。现在用户为页面号为0的虚拟页申请空间，操作系统把第16号物理页分配给它；接下来用户又为页面号为1的虚拟页申请空间，而17-19号物理页已经用掉，此时操作系统就不应该分配20号物理页给它，因为20号物理页和16号物理页占用同一个缓存地区，假设用户程序的局部性(locality)很好的话这样的分配方式会产生比较严重的抖动(thrashing)，影响系统缓存的性能。所以操作系统应该分配21号物理页给它，而保证这种分配策略的方式就是为每个页标记不同的颜色，并使得同一时间使用的页面颜色尽可能的不同。 参考资料 http://en.wikipedia.org/wiki/CPU_cache http://www.freebsd.org/doc/en/articles/vm-design/page-coloring-optimizations.html 阅读全文 →

吴总讲的一篇paper，题目是Orchestra: Intrusion Detection Using Parallel Execution and Monitoring of Program Variants in User-Space，发在EuroSys ‘09上，UCI的。 这篇paper提出了一种检测栈上buffer overflow攻击的方法。想法很有意思，它运行两个孪生进程，这两个进程的唯一的区别就是一个进程的栈往上长而另一个进程的栈往下长，这样在大多数情况下如果没有出现buffer overflow的问题的话那么两者的行为应该是一致的。 栈的增长行为是由编译器控制的，作者修改了gcc的代码使之生成的代码的栈增长方向相反，关于这个编译器他们之间发过一篇paper在一个叫CATARS的workshop上，题目是Reverse stack execution in a multi-variant execution environment。 “行为一致”的精确定义是两者的system call的调用方式、参数都一样，也就是说这里system call成了两个进程运行的synchronization point。如果某个点上两个进程调用的syscall不同或者调用参数不同就认为它已经被buffer overflow攻击了。 整个monitor都是跑在user态的，主要利用了ptrace，使两者的行为尽可能的一致。这里要做的事情很多，比如要保证进程调用getpid()的得到返回值一样才能使得后面的其他系统调用的参数相同，又比如一个进程调用write写入文件时不能影响到另一个进程，此外还要保证两个进程获得的file descriptor、随机数、时间、信号等信息都相同，甚至在进程创建子进行的时候也要保证所有子线程关系的同构。 用ptrace能够解决上面的大多数问题，但还有一些open problem以及false positive。如这篇paper无法解决进程用MAP_SHARED方式打开一个文件并修改的情况，尽管作者说这种mmap的用例很少见；此外由于两个进程的同步并不是原子性的，中间可能被第三方的程序干扰（比如进程A读入某个文件开头后，该文件被其他进程修改，进程B再读取就和进程A读到的不一样了），这就造成了false positive；另外由于无法截取rdtsc指令的使用，也就无法保证它们的返回值一样，也可能引起另一种false positive。 感觉这个东东想法不错，但是没什么实用性，工程量也很大。 阅读全文 →

在kernel 2.6.29上编译vmware modules时报错了 /usr/src/linux-2.6.29/arch/x86/include/asm/apicdef.h:132:1: warning: this is the location of the previous definition /tmp/vmware-config0/vmmon-only/linux/driver.c: In function ‘LinuxDriverSyncCallOnEachCPU’: /tmp/vmware-config0/vmmon-only/linux/driver.c:1423: error: too many arguments to function ‘smp_call_function’ /tmp/vmware-config0/vmmon-only/linux/driver.c: In function ‘LinuxDriver_Ioctl’: /tmp/vmware-config0/vmmon-only/linux/driver.c:1987: error: ‘struct task_struct’ has no member named ‘euid’ /tmp/vmware-config0/vmmon-only/linux/driver.c:1987: error: ‘struct task_struct’ has no member named ‘uid’ /tmp/vmware-config0/vmmon-only/linux/driver.c:1988: error: ‘struct task_struct’ has no member named ‘fsuid’ /tmp/vmware-config0/vmmon-only/linux/driver.c:1988: error: ‘struct task_struct’ has no member named ‘uid’ /tmp/vmware-config0/vmmon-only/linux/driver.c:1989: error: ‘struct task_struct’ has no member named ‘egid’ /tmp/vmware-config0/vmmon-only/linux/driver. 阅读全文 →

长时间使用Emacs经常会觉得小指疼痛，一个月前我把自己用的三台电脑（两台winxp，一台archlinux）的Caps Lock键的功能都改成了和左Ctrl一样，这样小指按起来就舒服多了，另外由于平时不需要用到Caps Lock键所以也不需要找个组合键来代替它了。 Windows下有个很方便的改键工具 remapkey，xp安装盘自带。 Mac OS X系统中改键也很方便，10.4以上版本的OSX中可以直接在Keyboard Preference里找到修改键位映射的选项。 Linux下的改键我知道两种方法，一种是修改xorg.conf文件，把里面的键盘设备设置改成 Section "InputDevice" Identifier "Generic Keyboard" Driver "kbd" Option "CoreKeyboard" Option "XkbRules" "xorg" Option "XkbModel" "pc104" Option "XkbLayout" "us" Option "XkbOptions" "ctrl:swapcaps" EndSection 另一种是使用xmodmap这个工具，具体可以参见这篇文章 Changing your caps lock into Ctrl in X，这里简单介绍下 修改前记得先备份当前的键位映射，xmodmap -pke > xmodmap.backup接下来运行 xmodmap -e 'keycode 66 = Control_L' xmodmap -e 'clear Lock' xmodmap -e 'add Control = Control_L' 这样就修改了Caps Lock的键位映射而不需要重启x，如果要在每次启动时自动修改Caps Lock键的映射，可以新建/修改一个.Xmodmap或者.xmodmap的文件，在里面加入 keycode 66 = Control_L clear Lock add Control = Control_L 阅读全文 →

http://linux.about.com/od/emacs_doc/a/emacsdoc567.htmM-x xterm-mouse-mode开启鼠标支持，操作的时候按住shift能恢复到之前的xterm鼠标模式 M-x mouse-wheel-mode开启滚轮支持 一些相关的参数： mouse-drag-copy-region 选中后自动复制 mouse-wheel-scroll-amount 每次滚动的行数 mouse-wheel-follow-mouse 滚动位置 mouse-wheel-progressive-speed 滚动速度 阅读全文 →

FastForward for Efficient Pipeline Parallelism http://systems.cs.colorado.edu/~moseleyt/publications/giacomoni-2008-ppopp-ff.pdf这篇paper介绍了一种针对多核访问优化的队列， 主要的特点： Lock-free Single-producer/single-consumer 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. 阅读全文 →

水木上有个帖子讨论tuple这个词该怎么读，于是有人翻出来这个三年前的新闻组邮件 http://coding.derkeiler.com/Archive/Python/comp.lang.python/2006-02/msg01915.htmlThen we went to hear Guido speak about Python 2.2 at a ZPUG meeting in Washington, DC. When he said toople I almost fell out of my chair laughing, particularly because the people who taught me to say it the “right” way were with me. When I looked over, they just hung their head in shame. I work with Guido now and I’m conflicted. I’m still conditioned to say tuhple. 阅读全文 →

Double-Checked Lock是一个常见的由于程序员把内存模型默认为sequential momery consistency导致的问题，具体见我去年写的一篇博文http://techblog.iamzellux.com/2008/07/singleton-pattern-and-double-checked-lock/虽然Java 5解决了这个问题，但是C++等语言中这个问题依然存在，依然有很多因为程序员假设sequential consistency而编译器做了错误的指令调度后导致的bug，见http://www.newsmth.net/bbscon.php?bid=335&id=250203CGO 09的这篇paper Detecting and Eliminating Potential Violations of Sequential Consistency for Concurrent C/C++ Programs针对这个问题进行了深入研究，通过加fence指令的方法解决了因编译器的指令调度造成的违背程序员原义的问题，可以在http://ppi.fudan.edu.cn/yuelu_duan下载到。没有认真读过，俺在这里就不误人子弟了 O.O 阅读全文 →

趁还在编译内核的时候把以前写过的东西都转过来，今年寒假读的 (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，同时这些处理对虚拟 机完全透明的。 阅读全文 →