Aiur – ZelluX 的技术博客

Linear page table又叫virtual page table，是一种方便虚拟机监控器(VMM)/操作系统(OS)/应用程序访问页表的技巧。Xen、64位Linux内核、JOS操作系统中都用到了这种技巧。这里以x86_32的虚拟内存管理为例，简单介绍一下它的实现和使用，如有错误敬请指出。

一般情况下，如果OS需要访问某个页表，需要将它映射到自己的虚拟空间中，然后再访问。这样带来两个问题，一是访问比较繁琐，需要临时的页映射；二是对于Exokernel这种fork等行为都是在用户态程序实现的系统，可能会增加一下安全上的问题。因为用户程序在fork的时候需要访问自己的页表，而这时候除非操作系统提供另一些权限控制更精确的系统调用，否则就很难让不可信的应用程序访问自己的页表且不做有害的改动。

Linear page table很好的解决了这两个问题。它的实现很简单，只需要在页目录中增加一项VPT，和一般的页目录项不同的是，这个VPT指向的是页目录本身。

这样带来了什么好处呢？借用一下MIT 6.828课件上的图片来更好的说明这个问题

增加了VPT后，通常的物理地址->虚拟地址的转换还是没变。和之前唯一的不同在于虚拟地址的页目录索引号(PDX)为之前设置的VPT的时候。

举个例子来说，假如现在要访问的虚拟地址是(VPT << 22) | (VPT << 12)，即这里的PDX和PTX都等于VPT的时候，整个转换过程是怎么样的呢（假设TLB miss的情况）？首先根据cr3中的物理地址，硬件开始查找页目录中的第VPT项，然后根据这一项中的物理地址，找到了下一级“页表”。注意这时候硬件以为自己得到的页表地址，实际上访问的还是页目录本身。同样，在这个“页表”中找到第VPT项指出去的最终页，得到了最终页的物理地址。因为PTX还是等于VPT，所以最后得到的物理地址还是页目录的。

也就是说，通常的页表访问的顺序是 CR3->页目录->页表->最终页，现在访问这个特殊地址的过程则成了 CR3->页目录->页目录->页目录，通过VPT这一项在页目录上绕了两圈后返回。

接下来，再来看看如何通过这个机制来访问某个页表，假如现在要访问第i个页目录项指向的页表上的第j项，那么我们应该构造这样一个特殊地址：

(VPT << 22) | (i << 12) | (j * 4)

即PDX=VPT, PTX=i, offset=j*4。通过这个地址就能得到需要的页表项了，另外由于(i << 12) | (j * 4) = (i * 1024 + j) * 4，定义vpn为虚拟页的编号，vpn = i * 1024 + j，则这个地址可以转换为

(VPT << 22) + vpn * 4

在JOS中，就是把vpt定义为一个uint32_t的数组，然后vpt[vpn]就是第vpn个虚拟页的页表项了。前面提到的另一个问题，如果要让用户以只读权限访问页表，又应该怎么做呢？很简单，在页目录中为用户设置另一个只读项，指向页目录自己就行了。

今天碰到一个gcc优化相关的问题，为了让一个页变成脏页（页表中dirty位被置上），需要执行下面这段代码：

uint32_t *page;
// ...
page[0] = page[0];

最后一行代码很有可能被gcc优化掉，因为这段代码看起来没有任何实际的作用。那么如何防止gcc对这段代码做优化呢？

设置gcc编译时优化级别为-O0肯定是不合适的，这样对程序性能影响会比较大。stackoverflow上的Dietrich Epp给出了一个强制类型转换的方案：

((unsigned char volatile *)page)[0] = page[0];

通过volatile关键字禁止gcc的优化，和我之前采用的方法类似。

Plow同学给出了另一个利用gcc 4.4特性的方法：

#pragma GCC push_options
#pragma GCC optimize ("O0")

your code

#pragma GCC pop_options

这里用到了gcc 4.4的特性Function Specific Option Pragmas，在特定代码前保存当前的编译选项，然后对特定的代码使用O0优化级别，最后再恢复之前保存的编译选项。

俺觉得这个特性有些场合下挺好用的，在这里分享下，虽然因为编译器版本问题最后我还是用了前面一种方法。

前几天试用了下ECB，非常喜欢它的定义列表和文件浏览历史的功能。但是却发现了另外一个问题：使用ECB之前我把整个窗口分成左右两块，左边是代码，右边是cscope的查找结果，现在开启ECB之后就不能再切一块窗口给cscope用了。

感谢stackoverflow上的sanitynic，给出了自定义ECB窗口的参考。现在俺终于能把cscope窗口绑定到屏幕左下角啦。

自定义ECB layout其实也挺方便的，上图对应的配置为

(ecb-layout-define "my-cscope-layout" left nil
                   (ecb-set-methods-buffer)
                   (ecb-split-ver 0.5 t)
                   (other-window 1)
                   (ecb-set-history-buffer)
                   (ecb-split-ver 0.25 t)
                   (other-window 1)
                   (ecb-set-cscope-buffer))

(defecb-window-dedicator ecb-set-cscope-buffer " *ECB cscope-buf*"
                         (switch-to-buffer "*cscope*"))

(setq ecb-layout-name "my-cscope-layout")

;; Disable buckets so that history buffer can display more entries
(setq ecb-history-make-buckets 'never)

my-cscope-layout这个layout左边窗口分为三部分，最上面的函数列表占一半高度，中间为历史文件列表，下面为cscope的查找结果，它们各占四分之一的高度。

另外再简单提下cscope插件的安装和配置，使用前需确认当前系统已经安装了cscope，另外要有cscope-indexer这个脚本。在cscope/contrib目录下找到一个xcscope.el，复制到Emacs的插件目录中，并在Emacs初始化文件中加入

(require 'xcscope)

即可。某些发行版的包里面似乎没有cscope-indexer和xcscope.el，直接从网上下一个好了。

几个常用的快捷键：
C-c s I 建立cscope索引
C-c s a 设置搜索目录
C-c s d 查找定义
C-c s s 查找字符串
C-c s c 查找调用者
C-c s n 下一个查找结果
C-c s p 上一个查找结果
更多的快捷键可以通过C-h b在cscope-minor-mode区找到。

简单来说就是给定一个未初始化的巨大的数组，然后通过它实现一个字典。所谓未初始化是指一开始里面元素的值都是随机的，巨大是指可以假设数组长度范围很大，对这个数组做初始化工作（例如清零）的代价自然也是很大。现在的问题是，利用这个数组设计出来的字典，要求初始化、查找、插入、删除操作都能在O(1)时间内完成。

Intructor’s Manual 上的解答设计了一个很巧妙的验证策略。假设T为那个巨大的数组，S为辅助栈，那么对于一个键k，如果k存在于这个字典中，则T[k]保存的是 k在S中的位置j，而S[j]则保存了k值。即1 ≤ T[k] ≤ top[S], S[ T[k] ] = k, T [ S[j] ] = j，我们称这个条件为“验证环”。这个设计的关键在于T和S能够互相验证，从而排除了未初始化位置上随机值的干扰。

还有一个问题就是，键k对应的值v应该怎么保存呢？其实只要维护另外一个和T或者S平行的数组就行了，既然S的元素个数远小于T，选择和S平行即可。

根据这个验证策略，我们就能设计出词典的基本操作了：
初始化：建立一个大小为0的栈
查找：给定键k，检查 1 ≤ T [k] ≤ top[S] && S[ T[k] ] = k，如果满足则返回对应值，否则返回NULL
插入：如果键已经存在则直接替换；否则将新的键值入栈，并且维护T[k] ← top[S]
删除：要确保两件事，一是验证环要被破坏，二是栈S的空洞要被填补。通过把栈顶的元素移动到要删除的元素位置，我们能同时确保这两点：

S[ T[k] ] ← S[ top[S] ]
S[ T[k] ] ← S [ top[S] ]
T[ S[ T[k] ] ] ← T [k]
T[k] ← 0
top[S] ← top[S] − 1

所有操作都能在O(1)时间内完成

原题：We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct-address dictionary on a huge array. Each stored object should use O(1) space; the operations SEARCH, INSERT, and DELETE should take O(1) time each; and the initialization of the data structure should take O(1) time. (Hint: Use an additional stack, whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)

semantic是cedet的组件之一，它可以对程序做语义分析，结合company等其他插件，可以实现自动补全菜单等功能。

之前用semantic+company写MIT 6.828的lab时几乎不需要什么特殊的设置就能直接用了，这次拿来改Xen的代码的时候却出现了semantic无法找到符号定义的问题，究其原因在于MIT 6.828的目录结构相对简单，头文件都在inc/目录下，而Xen的头文件在多个目录下，而且做预处理时还要加上Makefile里定义的一些预定义宏。今天参考了Alex Ott的这篇文章终于成功地让semantic支持Xen的代码分析了：

这里分享一下和项目相关的一些设置，semantic安装等问题请参考网上的其他文章。也可以参考我的配置文件http://code.google.com/p/zellux-emacs-conf/source/browse/my-cc-mode.el，cscope ecb semantic和company等配置都在这个文件里了，不过有点混乱。

;; Danimoth-specified configurations
(add-to-list 'semanticdb-project-roots "~/danimoth/xen")

(setq semanticdb-project-roots
      (list
       (expand-file-name "/")))

(setq danimoth-base-dir "/home/wyx/danimoth")

(add-to-list 'auto-mode-alist (cons danimoth-base-dir 'c++-mode))
(add-to-list 'auto-mode-alist (cons danimoth-base-dir 'c-mode))

(add-to-list 'semantic-lex-c-preprocessor-symbol-file (concat danimoth-base-dir "/xen/include/config.h"))
(add-to-list 'semantic-lex-c-preprocessor-symbol-file (concat danimoth-base-dir "/xen/include/asm-x86/config.h"))

(ede-cpp-root-project "Danimoth"
                      :name "Danimoth"
                      ;; Any file at root directory of the project
                      :file "~/danimoth/xen/Makefile"
                      ;; Relative to the project's root directory
                      :include-path '("/"
                                      "/include/asm-x86"
                                      "/include/xen"
                                      "/include/public"
                                      "/include/acpi"
                                      "/arch/x86/cpu/"
                                      )
                      ;; Pre-definds macro for preprocessing
                      :spp-table '(("__XEN__" . "")
                                   ))

其中，/home/wyx/danimoth/xen是项目的主目录，xen/include/config.h和xen/include/asm-x86/config.h里定义了一些基本的宏。

接下来，ede-cpp-root-project指定了这个项目的其他信息：
:file 指向项目主目录下任一一个存在的文件
:include-path 指定头文件的所在目录
:spp-table 给出了预处理时的使用的宏，通常是在Makefile里使用-DXXX定义的宏，例如这里的__XEN__。

配置好semantic后，可以用M-x semantic-ia-complete-symbol测试。如果Emacs能正确显示补全列表，这就说明semantic已经配置成功了。配合这个简单的company设置，就能用Shift-Tab显示类似图片中的自动补全菜单了。

终端下的效果图（Windows 7下使用pietty远登）

下载

http://ecb.sourceforge.net/downloads.html CVS或者压缩包都可以，当然也可以通过各发行版的包管理器安装。

安装

在.emacs中加入

;; ECB configurations
(add-to-list 'load-path "~/emacs/ecb-2.40")
(add-to-list 'load-path "~/emacs/cedet-1.0pre6/eieio")
(add-to-list 'load-path "~/emacs/cedet-1.0pre6/semantic")
(add-to-list 'load-path "~/emacs/cedet-1.0pre6/speedbar")
(setq semantic-load-turn-everything-on t)
(require 'semantic-load)
(require 'ecb-autoloads)

运行Emacs后执行ecb-byte-compile，并重启Emacs（我这里不重启的话执行ecb-active后会报错）。

使用

第一次使用时先要设置项目目录，M-x customize-variable <RET> ecb-source-path <RET>，在这里加上你的项目根目录。

接下来使用M-x ecb-active就能激活ECB了，成功激活后Emacs窗口会被切成左右两半。左边的几个窗口依次显示：目录，当前目录下的文件，当前文件中的函数/全局变量等定义，文件浏览历史。如果打开了一个源文件后函数定义窗口里面是空的，有可能是因为这个项目过大cedet尚未完成对它的分析，闲置一段时间后就能看到文件里的定义。

ECB提供了方便在这些窗口间切换的快捷键：

切换到目录窗口 Ctrl-c . g d
切换到函数/方法窗口 Ctrl-c . g m
切换到文件窗口 Ctrl-c . g s
切换到历史窗口 Ctrl-c . g h
切换到上一个编辑窗口 Ctrl-c . g l

最基本的使用就是这样，Ctrl-C . h可以看到更详细的帮助信息。

reddit programming版面最近的热帖，下面这个程序输出的结果是一个近似的圆周率(3.156)。

#define _ F-->00 || F-OO--;
long F=00,OO=00;
main(){F_OO();printf("%1.3f\n", 4.*-F/OO/OO);}F_OO()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
       _-_-_-_-_-_-_-_-_
            _-_-_-_
}

乍看下这个程序有点莫名其妙，分析一下宏后就知道它的方法了。两个全局变量F和OO分别记录 圆的面积和直径 的相反数，根据4*面积/直径/直径就能得到近似的圆周率了。

至于面积和直径的计算，F在会在每一个_展开的地方减一，这样就得到了圆的面积。直径的计算要展开几行代码才能看得更清楚：

F-->00 || F-OO--;
-F-->00 || F-OO--;
-F-->00 || F-OO--;
-F-->00 || F-OO--;

F-->00 || F-OO--;
-F-->00 || F-OO--;
-F-->00 || F-OO--;
-F-->00 || F-OO--;
-F-->00 || F-OO--;
-F-->00 || F-OO--;
-F-->00 || F-OO--;
-F-->00 || F-OO--;
-F-->00 || F-OO--;

这是用cpp展开圆形前两行代码的结果，因为或运算的特殊性，F- OO- -只会在每一段的第一行执行，所以OO- -执行的次数就等于圆的直径了。

因为大多数情况下程序都是通过libc间接地发出系统调用的，所以只要编译一个只使用int 0×80的glibc库，然后在执行程序的时候用LD_LIBRARY_PATH或其他方法指定使用新编译的glibc库即可。

以glibc-2.9, Linux i386为例，在sysdeps/unix/sysv/linux/i386/syscall.S中可以看到

 ENTRY (syscall)

     PUSHARGS_6      /* Save register contents.  */
     _DOARGS_6(44)       /* Load arguments.  */
     movl 20(%esp), %eax /* Load syscall number into %eax.  */
     ENTER_KERNEL        /* Do the system call.  */
     POPARGS_6       /* Restore register contents.  */
     cmpl $-4095, %eax   /* Check %eax for error.  */
     jae SYSCALL_ERROR_LABEL /* Jump to error handler if error.  */

这里使用了ENTER_KERNEL这个宏做系统调用，接下来在sysdeps/unix/sysv/linux/i386/sysdep.h里可以找到这个宏的定义

/* The original calling convention for system calls on Linux/i386 is
   to use int $0x80.  */
#ifdef I386_USE_SYSENTER
# ifdef SHARED
#  define ENTER_KERNEL call *%gs:SYSINFO_OFFSET
# else
#  define ENTER_KERNEL call *_dl_sysinfo
# endif
#else
# define ENTER_KERNEL int $0x80
#endif

而I386_USE_SYSENTER这个宏也是在同一个头文件中定义的

#if defined USE_DL_SYSINFO \
    && (!defined NOT_IN_libc || defined IS_IN_libpthread)
# define I386_USE_SYSENTER   1
#else
# undef I386_USE_SYSENTER
#endif

把这个条件宏改成

#undef I386_USE_SYSENTER

就能强制glibc使用int 0×80了。

这个方法只能过滤通过glibc做的系统调用。对于程序里写死使用sysenter的情况就要使用反汇编或者其他手段了。

在Pro Git上看到的技巧，git的源代码包里的contrib/completion目录下有个git-completion.bash，把这个文件保存到~/.git-completion.bash，然后在.bashrc中加入一行

source ~/.git-completion.bash

这样就能在bash下用tab自动补全git命令、branch等内容了。另外Debian/Ubuntu里有个包就叫git-completion，这个包安装完成后会自动把这个补全脚本放到/etc/bash_completion.d/下，由bash-compleletion载入执行。

使用grep在ps aux的输出结果中查找进程的时候经常会把grep进程本身也找出来，比如查找emacs进程：

$ ps aux | grep emacs
wyx   7090  0.0  0.0   3336   796 pts/2 S+ 04:49 0:00 grep emacs
wyx  10128  0.1  4.9  66904 50388 pts/3 S+ Jan21 2:21 emacs

一个常见的防止grep进程出现的方法就是在后面再加一个grep -v grep：

$ ps aux | grep emacs | grep -v grep
wyx  10128  0.1  4.9  66904 50388 pts/3 S+ Jan21 2:21 emacs

今天在Santosa的博客上看到了另一个巧妙的做法，使用grep [e]macs来搜索emacs这个进程：

$ ps aux | grep [e]macs
wyx  10128  0.1  4.9  66904 50388 pts/3 S+ Jan21 2:21 emacs

为什么会有这样的效果，知道grep正则中[]的作用后想一想就能明白啦。很有意思的trick，虽然说它比grep -v grep也未必方便多少，因为后者能通过alias简化输入。