Aiur – ZelluX 的技术博客

今天reddit programming上的一个帖子，提到了ubuntu上python-apport包的一个bug。

重现这个bug很简单：

Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> len(sys.modules)
35
>>> foo
Traceback (most recent call last):
  File "", line 1, in
NameError: name 'foo' is not defined
>>> len(sys.modules)
225
>>>

在执行foo之前，当前导入的包只有35个，执行之后却有了225个。问题出在Ubuntu的Apport系统，它为Python添加了一个异常处理方法，这里面的bug导致了这些多余的包被导入。

这个bug已经被人提交并被确认，目前暂时还没有补丁，最简单的避免方法就是把python-apport包卸载

原文地址： http://rhodesmill.org/brandon/2010/ubuntu-exception-190-modules/

SICP第二章里提到了一种用来画图的Lisp方言，用来演示数据抽象和闭包的表达能力（见http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.4）。

最近尝试了下，发现soegaard同学已经在PLT Scheme中实现了一个类似的库，可以很方便的在DrScheme上使用。

sicp.plt包使用很简单，在Language->Choose Language中选择Module，然后在需要用到这个包的时候用

(require (planet soegaard/sicp:2:1/sicp))

声明即可。第一次运行时DrScheme会自动下载这个包并安装，如果网络有限制可以先从http://planet.plt-scheme.org/display.ss?package=sicp.plt&owner=soegaard下载然后在DrScheme中选择本地包安装。

另外SICP上使用的两个painter（wave和rogers）没有在这个包里提供，取而代之是diagonal-shading和einstein。

下面这个程序显示了一个简单的分形图像：

#lang scheme

(require (planet "sicp.ss" ("soegaard" "sicp.plt" 2 1)))

(define (right-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (right-split painter (- n 1))))
        (beside painter (below smaller smaller)))))

(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))

(define (corner-split painter n)
  (if (= n 0)
      painter
      (let ((up (up-split painter (- n 1)))
            (right (right-split painter (- n 1))))
        (let ((top-left (beside up up))
              (bottom-right (below right right))
              (corner (corner-split painter (- n 1))))
          (beside (below painter top-left)
                  (below bottom-right corner))))))

(paint (corner-split diagonal-shading 4))

程序输出：

gitk是用Tcl/Tk写的工具，默认使用Tk 8.4，不支持抗锯齿，因此字体显示很难看。好在Tk 8.5支持了部分抗锯齿字体，修改gitk使用Tk 8.5后显示效果会好一点。

以Ubuntu为例，安装tk8.5包后，编辑/usr/bin/gitk文件，把开头调用wish的那行

exec /usr/bin/wish "$0" -- "$@"

改成

exec /usr/bin/wish8.5 "$0" -- "$@"

这样就能在gitk中开启抗锯齿了，虽然效果还不是很好。另外qgit也是一个不错的选择。

参考链接：http://navarra.ca/?p=44

这是一个让wordpress对移动设备更友好的插件，下载地址在http://wordpress.org/extend/plugins/wptouch/，当然也可以在wordpress后台查找wptouch并安装。

在iPod Touch上的效果图

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可以看到更详细的帮助信息。