Liuw's Thinkpad

从我使用Git与@liuhui998翻译Git Community Book的实践来看，Git是一个非常强大的工具。但是光有好工具是不够的，必须有好的工作流才可以保证协作的顺畅。

事出有因。我从liuhui998的仓库fork出来一份，然后开始翻译。刚刚开始在翻译的时候，我使用了一个分支liuw，然后在翻译完成之后，把liuw合并到master中去，然后push到github，再由liuhui998来pull。

liuhui998 pull了之后，也push到了他的github仓库。但是后来他觉得这样的分支结构有点乱，所以做了一个rebase操作。这下出问题了，rebase操作令得同样的commit有了不同的SHA1 ID，我在从他那里pull的时候，发现不能再进行fast-forward合并了。Progit中提到，“永远不要衍合那些已经推送到公共仓库的更新”，而liuhui998恰恰做的就是这样一件事。

在rebase之后，同样的commit内容有了不同的ID，所以在我pull回来的仓库中会出现两次，浪费空间。然后整个工作树也被搞得很难看。

当然，这也有我的一份责任，我在push之前，应该先把分支清理一下，自己先rebase好。

问题搞明白了就好办了，现在liuhui998的版本是最干净的，所以我直接采用他的版本就OK了。下面的upstream是liuhui998的github仓库，origin/master就是我的github仓库。

$ git reset --hard 5b9d65 # 回退到没有出问题的commit
$ git pull upstream master
... 可以直接fast-forward ...
$ git push --force # 改写origin/master，因为远程仓库原来被我搞乱了

很多东西，真是“纸上得来终觉浅，绝知此事要躬行”，看书都看到了，就是没有实际去做，也没有这个意识。

以后要养成好习惯，一是在发布自己的commit之前先进行清理，二是不要轻易rebase已经发布的commit。

http://www.kernel.org/pub/software/scm/git/docs/git-rebase.html 有提到 RECOVERING FROM UPSTREAM REBASE。

看龍書的時候發現原來正則表達式中的*和+是指語言學中的語言運算。

一個語言的Kleene閉包，記為L*，就是將L連接0次或者多次后得到的串集。L^0即為空串。

正閉包，記為L+，就是Kleene閉包不包含L^0。

“零拷贝”这个词也听到不少了，据说是可以明显提高性能。网上找到好文一篇。

Zero Copy I: User-Mode perspective

在一些程序，比如说HTTP服务器，需要向用户发送文件，有一部分是图片、静态网页之类不需要处理就可以直接发送的文件。土一点的做法无非是：

read(file_fd, buf, len);
write(socket_fd, buf, len);

实际上，read(2)这个操作，是首先把文件内容读入到内核缓冲区中去，然后再把文件内容从内核缓冲区拷贝到用户缓冲区；而write(2)这个操作，需要把用户缓冲区的内容拷贝到内核缓冲区。我们不需要对文件内容进行处理的情况下，却多用了一道拷贝工序，直接造成的开销有多了一次的上下文切换，以及浪费了缓冲区的内存。

为什么不把拷贝到用户空间的这一道工序去掉了，内核的两个缓冲区直接拷贝就好了。目前流行的做法是用sendfile(2)，在Linux里面的作用是把数据从一个文件描述符直接拷贝到别一个文件描述符。但是sendfile(2)的实现，好像是各个系统都有差异，使用的时候需要注意一下，在使用的时候最好先查一下手册。

但是从内核缓冲区到内核缓冲区的“零拷贝”，还不算真的完全没有拷贝。真正的“零拷贝”需要硬件支持。在具备Gather操作的DMA硬件支持下，内核只需要修改内部文件描述符的指向，然后等待硬件自动执行Gather操作，把数据取走。

五一期间看了一篇文章，Memory Barriers: a Hardware View for Software Hackers，对于Memory Barriers得到了更加深入的理解。

Cache本身的更新是遵守MESI（Modified，Exclusive，Shared，Invalid）协议的。CPU之间的Cache信息更新通过消息传递来完成。

但是现在CPU的设计中，在Cache之外加入了Store Buffer和Invalidate Queue。Store Buffer的加入，使得CPU对某内存单元的更新不能马上反映到Cache中；Invalidate Queue的存在，使得其他CPU对Cache的invalidate操作不能马上反映到Cache中。Store Buffer和Invalidate Queue提高了性能，但是也就导致了Cache的不一致。

因此需要引入Memory Barriers。Store Buffer和Invalidate Queue应该分别对应使用wmb和rmb。当然直接使用通用mb也是可以的。

Roughly speaking, a “rmb” marks only the invalidate queue and a “wmb” marks only the store buffer, while a “mb” does both.

一般来说，Memory Barriers应该配对使用，比如说一方使用了rmb另外一方对应使用wmb。在Linux内核中，还存在着Data Dependence Memory Barrier，这是一个较弱的rmb。具体见Linux内核代码的Documentation/memory-barriers.txt。

目前我们组内对开发的管理还十分初级。Wiki刚刚开始用，没有用trac、bugzilla之类的工程控制工具，只用了Mercurial进行了版本控制，交流主要靠每周例会。

学生开发组织，我觉得是比较难做到规范化开发的。一则因为外围工具的学习成本高，项目等不及；二则因为学生组织与公司不一样，至少不会因为开发流程不规范而被fire掉。在学校里面，老板要的是效果、演示，不管你用什么方法去做。

在目前开发的过程中，也出现了一些问题。原来使用Mercurial的原因，就是一个DVCS看起来更适合我们项目。组内对于Xen都处于摸索的状态，需要做大量的实验，会产生大量的commit。使用svn的话，必须等到特性稳定之后才可以commit，不合适。

当然，实际使用过程中，我们仍然保持有一个“主”版本库，其中含有稳定的代码。原则上来说，主版本库更新之后，每个人都应该与之保持同步。

现在问题来了，大家都没有及时与主版本进行同步，所以现在diverge得越来越远了。到时再想merge的话，conflict将是一个很头痛的问题。但是用svn的话，这种情况就不会出现了。

当然，只要DVCS的使用者注意同步，这也不会是什么大问题。CVCS的好处是，这个步骤是强制的，不能有意无意的略过，大家必须保持一致。

现在我已经预见到以后merge会遇到的痛苦了。

UPDATE：和小胖聊了一下，发现其实还是工作流的问题。人是活的，工具是死的。工作流做好了，活用branch，CVCS也可以解决“不稳定的新特性commit”的问题。所以最现实的，就是把工作流做好。我们缺的不是工具，而是完整的工作流。

I use Git and Mercurial. Take a note on some of my configurations.

Git is configured via git(1) command. Configurations eventually go into .gitconfig, which can be edited by hand.

# note "--global" means per user
# system wide setting is set with "--system"
# if cd into project dir and without "--global", settings will be in project scope
$ git config --global user.name 'Wei Liu'
$ git config --global user.email liuw@liuw.name

# if use windows, better set
$ git config --global core.autocrlf true
$ git config --global core.safecrlf true

Mercurial is configured via ~/.hgrc or project specified .hgrc.

[ui]
username = Wei Liu

As far as I can see, Git is more powerful while Mercurial is easier to use. There’s still more to learn about DVCS. Some interesting stuffs:

http://www.python.org/dev/peps/pep-0374/

This article provides several usage scenarios on several VCS, quite useful to green hand like me.

http://code.google.com/p/support/wiki/DVCSAnalysis

Google’s analysis of Git and Mercurial. But I got the sense that the reviewer’s biased towards Mercurial. Anyway, Google is a Python company.

今天下午研究了一下Continuation，在Wikipedia上看到了Continuation Passing Style的相关介绍，带有例程（不过是用Scheme写的）。既然自己在用Emacs，那么试试把例子都用Elisp实现一下吧。

其中有一个函数，用来制作支持CPS的函数，原型是这样的：

(define (cps-prim f)
  (lambda args
    (let ((r (reverse args)))
      ((car r) (apply f
                (reverse (cdr r)))))))

这样用，比如说要制作一个支持CPS的减法运算：

(define cps- (cps-prim -))

假如不使用cps-prim，那么每个函数都要这样写：

(define cps- (a b k)
  (k (- a b)))

很显然，使用cps-prim更加方便点。于是我打算用Elisp也做一个同样的函数，谁让我这么懒呢。

Elisp比较乱，所以写了挺久的，但是总算是写出来了：

(defun cps-prim (f)
  #'(lambda (args)
      (let ((r (reverse args)))
        (funcall (car r) (apply f
                                (reverse (cdr r)))))))
(fset 'cps- (cps-prim '-))

但是使用cps-的时候，会提示f无值。好吧，查一个info，心彻底凉了。11.9.2中明确写到，Elisp是不支持闭包的，所以f在cps-中是unbound的。想偷懒偷不成咯。

再进一步想想，Elisp不支持闭包，是否就不支持高阶函数呢？个人程序设计语言方面没什么了解，只能google了。显然我不是第一个想到这个问题的，还真是发现了一些有趣的东西。

http://lambda-the-ultimate.org/node/1936

有人说：

Closure = Function x Environment

不得不说，这个等式，比一个冗长的定义更清楚。

RCU is short for Read-Copy Update, quite a weird name. There’s an explanation of this name from that Wiki page.

http://lwn.net/Articles/262464

http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html

http://en.wikipedia.org/wiki/Read-copy-update

在看PicoWebServer的一个security flaw分析，嗯，典型的栈溢出。虽然多了一个Unicode，但是还是可以做到DoS攻击的。作者的分析也挺不错，把出现问题的地方说得清楚了。

不过末尾有一句话有点大雷了：

An attacker has full control over the device if he is able to let the overwritten return address point to a “0D F0 A0 E1″ (“MOV PC, SP”) equivalent byte sequence. Since SP is the only register pointing into the potential shellcode supplied by an attacker, the aim of an attacker is to let PC equal SP.

还好作者用的是if he is able to，还有点不确定的意思。我是老老实实地用IDA Pro搜索了整个地址空间（是的，“整个”），也没有发现有这样的序列。首先，编译器不会产生这样的代码，那么在代码段内找是徒劳的了。其次，数据段有的话，那真是纯粹巧合了，看人品，而且数据段能不能执行，还是未知之数。

所以啊，总是easier said than done，虽然现在有这样的possibility，但是实际上做不做得到，那还真是认真考证一下才清楚。

师兄也和我说了，搞个什么MessageBox出来，那是不难，但是我们的目标还是要再远一点，要有点实际的东西出来。我也挺认同的，理念上的东西，大家都清楚，但是到底能不能用，可不可以，那还真是要做过才知道。不产生实际危害的漏洞，不是好漏洞（DoS不在考虑之列，这是比较次的危害）。

提一下我们现在的问题是什么：某个软件，接收ANSI字符（0×00-0xFF），然后把接收到的字符转换成Unicode再存储到缓冲区，然后造成了缓冲区溢出。问题是，我们虽然可以改写栈上PC的值，但是这是有限制的（Unicode转换的存在）。如何把控制流改到我们注入到栈上的shellcode中，这需要很多工夫了。目前这是第一步，先不考虑shellcode是否有效，就是要把PC的值搞到栈上就OK了。

这一周基本都在考虑这个问题，也有不少的想法，但是最后都被自己否掉了。罗列如下吧：

1. 把要发过去的ANSI串A看作是Unicode，先进行Unicode到ANSI的变换得到B，把B发过去，这样在Server端变换之后，就变成了A。这个想法的致命点是，ANSI只能映射Unicode的一个很小的子集，也就是说，变换过程不是满射的。而且从比例来看，只有1%左右有情况可以逆变换成功。于是有第二个想法。
2. 寻找Unicode编码中的闭包子集S，发过去S中的A变换后得到的B仍然在S之内，这样可以很容易通过控制A的生成来得到理想的B。但是现在我还没有找到这样的闭包。即使找到，也只有万里长征第一步，因为这样的S估计不会很大，变换出来的编码有限的话，对于地址的选择就很有讲究了。
3. 在其他段寻找如MOV PC, SP这样的序列（也就是上面文章的想法）。不用说，目前失败。
4. 构造某个系统调用/API的输入，然后跳转到那个系统调用/API。要求是这个系统调用/API足够强大，可以完成很多功能。但是矛盾的地方是，功能强大的API通常参数是十分复杂的，很难构造。而且，Windows CE的calling convention中，首先使用R0-R4去传送参数，不够才使用栈。怎么让R0-R4符合API的要求？看运气？否掉。
5. 从转换函数入手，当然，这个想法很烂。但是也不是说完全没有可能，先留着呗。

现在基本是能想到的都想了，但是总是有这样那样的限制，使得这些想法成为不可能。明天和师兄讨论一下，看他有没有什么其他想法吧。

免得以后重装时忘记了。

AutoSaveText
Close Tab By Double Click
Easy DragToGo
Firebug
FireGestures
FlagFox
FlashGot
Gostery
Gmail Manager
Greasemonkey
Header Spy
It’s All Text!
ScribeFire
XMarks