Middle Earth

goagent 安装

2012-07-21T17:41:00+08:00

我总是后知后觉，现在才开始折腾 goagent。之前买过 VPN，最近一直用 ssh tunnel。试了 goagnet 才发现真心好用啊。

但是目前 GAE 貌似大面积被封了，所以 goagent 一开始安装都有问题，根本没法传到服务器上。

$ python uploader.zip
APPID:zhngsn-p4
Application: zhngsn-p4 
Host: appengine.google.com
INFO - - [Jul 21 17:45:56] Server: appengine.google.com
Rolling back the update.
Traceback (most recent call last):
  File "/usr/lib64/python2.7/runpy.py", line 162, in _run_module_as_main
    "__main__", fname, loader, pkg_name)
  File "/usr/lib64/python2.7/runpy.py", line 72, in _run_code
    exec code in run_globals
  File "uploader.zip/__main__.py", line 10, in <module>
    main()
[...]
  File "uploader.zip/google/appengine/tools/appengine_rpc.py", line 365, in Send
  File "/usr/lib64/python2.7/urllib2.py", line 400, in open
    response = self._open(req, data)
  File "/usr/lib64/python2.7/urllib2.py", line 418, in _open
    '_open', req)
  File "/usr/lib64/python2.7/urllib2.py", line 378, in _call_chain
    result = func(*args)
  File "/usr/lib64/python2.7/urllib2.py", line 1215, in https_open
    return self.do_open(httplib.HTTPSConnection, req)
  File "uploader.zip/fancy_urllib/__init__.py", line 367, in do_open
urllib2.URLError: <urlopen error [Errno 32] Broken pipe>

墙很高啊。

尝试用 tsocks，通过现有的 ssh tunnel 上传，一样的 URLError。有人提到可以设置 https_proxy 环境变量，但是手上又没有 http 代理 (socks5 代理能转成 http 代理么) 。

本来要放弃了，但是转念一想，刚才我还上传了 GAE 上的一个小网站呢。于是用 google 官方的 GAE SDK 试了下，还真成了。

goagent 代码其实很简单，需要上传到 GAE 的 app 就在 server/python 目录下。

所以，到 server/python 目录下，编辑 app.yaml，把申请的 app 名字填到第一行:

application: your-app-name

然后，把官方的 SDK 下载下来后，

/path/to/google_appengine/appcfg.py update .

就 OK 了。没被重置，也不需要每次都输密码。如果申请了多个应用做负载均衡，就依次修改 app.yaml，运行 appcfg.py update，把每一个都部署上。

go 版本在 server/go, 应该是一样的。

部署完后 (我搞了四个做负载均衡) 运行 local/proxy.py。

fedora 系统修复

2012-07-18T17:44:00+08:00

一台机器上安的 fedora 17，是用 beta 发布安装的。文档中提到 beta 发布会自动升级到正式版本，不需要改什么配置，所以就一直没在意。但是过了一段时间后，就开始出问题了。

主要的问题是 yum update 的时候报一大堆的 404 错误。类似这样的，

http://mirrors.sohu.com/fedora/releases/17/Everything/x86_64/os/drpms/LibRaw-0.14.3-3.fc17_0.14.3-4.fc17.x86_64.drpm:
[Errno 14] HTTP Error 404 - Not Found :
http://mirrors.sohu.com/fedora/releases/17/Everything/x86_64/os/drpms/LibRaw-0.14.3-3.fc17_0.14.3-4.fc17.x86_64.drpm

不只 LibRaw 这个包，还有很多，NetworkManager, alsa-plugins-pulseaudio 等等等等。

这个 404 错误显然是 yum 试图用 drpm 来升级，而它尝试的地址都不对，在源里是不存在的。但是当单独升级每个包的时候，好像不会报错。

尝试了 yum clean all, 没什么作用。最后偶然发现很多包的 repo 信息是 @koji-override-0/$releasever，而正常情况下应该是 fedora, fedora-updates 这样的。

于是首先用 yum list extras 找出所有这样的不正常的包.

yum list extras [glob_exp1] [...]
      List  the  packages installed on the system that are not available in any
      yum repository listed in the config file.

把上边得到的列表用 sed/cut 处理一下，用一个 for 循环，一个一个地单独升级，就能修复到正确的 repo 了。

然后呢… 发现不好使，有的包还是会尝试用 drpm。

最后的办法是先暂时把 drpm 支持关掉。升级完再打开。

而支持 drpm 的特性叫做 presto, 在 /etc/yum/pluginconf.d/presto.conf 里配置。(吭爹的名字，八杆子打不着)

Python dict 的实现

2012-07-09T17:01:00+08:00

Python (cpython) 的 dict 是用哈希表实现的。
碰撞的处理方法是 open addressing，因为 chaining 的 overhead 太高 (哈希表里记录的只是哈希值和相关的 object 的地址，不记录实际 object，所以如果用链表来做 chaining 的话，光 next 指针就占去了很多空间)。(不知道我理解得对不对)。

Open addressing is preferred over chaining since the link overhead for
chaining would be substantial (100% with typical malloc overhead).

一般的哈希表在选择哈希函数时，都希望产生的哈希值尽量随机，但是 python 的哈希函数不是这样的。dict 和其它一些地方使用的哈希函数其实就是 python 的内置函数 hash ，它的返回值非常的不随机。比如对于最重要的两种 key，整数和字符串，整数的哈希值就是它本身，而字符串的哈希值计算也很简单。且看

>>> map(hash, (0, 1, 2, 3))
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-1658398457, -1658398460, -1658398459, -1658398462]

这样的好处是如果 key 是连续的整数或者字符串，几乎不会有碰撞。而且哈希值基本都是连续的，效率也比较高。

有时候，好处也是坏处。这样做的坏处是，表里会有数据连续地存在一块，而不是相互散开 (这正是哈希表，也称散列表的意义所在啊)，也就是，一旦有碰撞发生，用线性探测的方法来寻找可用位置是绝对不可行的。python 用的探测方法是一种 quadratic probing，保证不会受到连成块的数据的影响。
既然是使用 open addressing，也就是说整个哈希表存储在一段连续的内存中，或者说是一个数组 (dict 是用 C 实现的)。这意味着，当数组快满时 (比如超过 2/3)，需要把数组扩大 (resize)。
python 保证在修改元素的时候不会发生 resize，也就是保证了可以一边遍历 dict，一边修改元素。但是其它的操作就不一定了，所以会有这样的错误:

>>> a = {1:2, 3:4}
>>> for k in a:
...  del a[k]
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: dictionary changed size during iteration

>>> a = {1:2, 3:4}
>>> for k in a:
...  a[2*k]=1
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: dictionary changed size during iteration

参考

http://www.laurentluce.com/posts/python-dictionary-implementation/
http://hg.python.org/cpython/file/tip/Objects/dictobject.c
http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

python 有这么慢吗

2012-06-29T16:01:00+08:00

逻辑几乎相同的两段代码，python 比 C 慢 50 倍？

/* Find the sum of all numbers which are equal to the sum of the factorial of
   their digits. */

#include <stdio.h>

int solve()
{
    int f[10];
    int i, limit, sum;

    f[0] = 1;
    for (i=1; i<10; i++)
        f[i] = f[i-1]*i;
    limit = 7*f[9];
    sum = 0;
    for (i=3; i<=limit; i++) {
        int s = 0;
        int j = i;
        while (j>0) {
            s += f[j%10];
            j /= 10;
        }
        if (i==s)
            sum += i;
    }
    return sum;
}

int main()
{
    printf("%d\n", solve());
    return 0;
}

# Find the sum of all numbers which are equal to the sum of the factorial of
# their digits.

import math

def solve():
    f = [math.factorial(i) for i in range(10)]
    limit = 7*f[9]
    ret = []
    for i in range(3, limit+1):
        s = 0
        j = i
        while j>0:
            s += f[j%10]
            j /= 10
        if i==s:
            ret.append(i)
    return ret

print sum(solve())

$ time python 34-sum-of-digit-factorial.py
40730

real    0m5.053s
user    0m4.850s
sys     0m0.145s

$ time ./a.out
40730

real    0m0.115s
user    0m0.111s
sys     0m0.002s

这是 Project Euler 的第 34 题。

今日的农村

2012-06-28T21:27:00+08:00

端午回家，又到村庄的农田旁边走了走。原本的良田，现在是这样了。

农田被圈成了工地，道路早已废弃许久。走在曾经被植被覆盖的乡间，竟然也能被吹一脸土。

围墙里是曾经的农田。

路对面的耕地还没有被征去，但是农民早不敢投入任何成本，随便种下的葡萄苗，只等着被征的时候多换点拆迁款。

收拾得这么干净，也是一种无奈吧。

真正让人震惊的，是后边不远处的烟囱。正在建的小区，是打算把附近的村庄拆掉，然后把村民都迁过来的。但是化工厂就在旁边，这是怎样的居心？

现在如火如荼的拆迁，显然就是地方政府的圈钱运动。而中央政府睁只眼闭只眼，道理也很简单，在中国是哪些人还有自己的土地？只有农民还在名义上拥有属于自己的土地。只要动用“拆”这个字，就能把所有人赶到了 70 年产权的商品房里，腾出来的大片土地就又是一笔财源。只要忠厚的中国人都不说话，政府又何乐而不为？

动态分配的二维数组

2012-06-28T20:58:00+08:00

在 C 语言里，其实是可以动态分配二维数组的。只调用一次 malloc，就可以得到一个二维数组，并且支持 p[i][j] 这样的下标操作。代码如下:

int **alloc_2d(int rows, int cols)
{
    int **p, *data;
    int i;
    p = malloc(rows*sizeof(int *) + rows*cols*sizeof(int));
    data = (int*)(p+rows);
    for (i=0; i<rows; i++)
        p[i] = data + i*cols;
    return p;
}

释放的时候调用 free 即可。

再看我之前那些用一维数组模拟二维数组的拙劣代码，真是不堪回首。

计算区间内的素数

2012-06-27T20:47:00+08:00

生成素数的一般方法是用“筛”，古老的 Sieve of Eratosthenes，来生成 [1,n] 之间的所有素数。这里的问题稍有变化，要求计算某个区间 [m,n] 内的素数，其中 m 和 n 都有可能很大，但是 n-m 不大。

这其实是 SPOJ 上的第二道题 (PRIME1)。

由于 m 和 n 很大，所以不能用试除法 (trial division)，而且 Sieve of Eratosthenes 也不可行。

这种情况可以用分段的筛 (segmented sieve)。也就是先用 sieve 计算出 [1,sqrt(n)] 上的素数。然后用这个素数表，在 [m,n] 上再次应用 sieve，得到所求的素数。两次的筛都不是很大，可以放在内存中，而且速度也可以接受。如果 n-m 还是很大，还可以再次分成几段来做 sieve，这是这里的做法。 (我怎么觉得后面这种情况才是 segmented sieve 呢?)

一个类似的用这种分段策略的题目是，假设一个文件里有 4 billion 个整数，数字都是普通的 int，也就是有 32 位。要求找到一个不在这个文件里的整数，限制可用内存为 10MB 。

用一般的 bitmap 肯定是不行的。可以采用分段策略，通过两次遍历完成。把 2³² 这个区间分成若干段，第一次遍历求每一个区间中数字出现的个数。然后找出一个必然存在缺失数字的区间，对这个小的区间创建 bitmap，进行第二次遍历，找到一个缺失的数字。空间复杂度满足要求，因为假设有 M 个小区间，每个区间有 N 个数，那么 M*N=2^32，第一次遍历需要 M*4B，第二次遍历需要 N*4B (假设 bitmap 都用 int 数组)。所以 M 和 N 都取为 2¹⁶ = 65536 即可。

dup3, pipe2, epoll_create1

2012-06-27T09:51:00+08:00

dup, pipe, epoll_create 这些函数都有一些变种，dup3, pipe2, epoll_create1 。为什么会这样？原因是这些接口设计时考虑不足，导致无法进行扩展，当新需求出现的时候，只能再添加新的接口。

这些函数有什么相同之处呢，它们都是用来创建新的文件描述符的 (file descriptor)。这个需求就是跟文件描述符相关。

在通过 fork/exec 创建一个新进程的时候，默认的行为是子进程继承父进程的所有已打开的文件。为了安全性，一般会把文件设成 close-on-exec，也就是说执行 exec 的时候，自动把文件关闭。否则的话，父进程的文件就会泄漏给子进程。

比如浏览器里，假设一个 tab 是银行付款页面，另一个 tab 是“某个”页面，这个页面需要用一个 plugin，而浏览器通过 fork/exec 来运行这个 plugin。如果文件描述符没有设置为 close-on-exec，那么银行页面的文件就有可能泄漏给这个 plugin。然后…

所以一般都会通过 fcntl 来设置一个 flag, FD_CLOEXEC，保证在 fork/exec 的时候自动关闭文件。但是由于 open 和 fcntl 之间总是存在一定的时间差，所以在多线程的程序里会有潜在的危险。一个办法是用锁，保证 open 和 fcntl 之间不会进行 fork，但是这并不可行 (且看引用原文的描述)。

最好的办法就是给 open 添加一个 flag，使得文件在打开时就已经设为 close-on-exec。

但是… 能打开文件 (也就是创建文件描述符) 的函数不只有 open。由于 UNIX 众所周知的设计特点，socket/accept/pipe/dup/epoll 都能创建文件描述符。而最大的问题是，不是所有的函数都像 open 那样有一个 flags 参数。比如 int pipe(int pipefd[2])。管道固然是个绝佳的概念，但是谁也没想到，后人竟然想对管道设置 flag。

但是为了保证原子性得设置 close-on-exec，必须要有 flag 参数，所以对这些函数只能创建新的接口，dup3, pipe2 等等就是这样来的。这个解决方案不算完美，但也没有更好的办法了 (比如 linus 提出过一个“间接系统调用”的方案)。

而另一些函数，比如 int socket(int domain, int type, int protocol)，虽然没有 flag，但有一个 type 参数。由于 type 的取值范围很有限，而且 type 和 flag 还算有点相似，所以开发者决定复用这个参数，把 SOCK_CLOEXEC 看作新的 type。这样函数接口就不需要修改了。

这样，所有能创建文件描述符的接口就都(相当于)有 flag 参数了，不仅可以用于设置 close-on-exec，而且也能方便将来的其它扩展。比如 XXX_NONBLOCK (现在已有)，和提了好久的 non-sequential file descriptor 的支持。

引用: udrepper.livejournal.com

firefox 被某智篡改的主页

2012-06-25T21:34:00+08:00

端午回家，升级了下家里电脑的 firefox，发现主页竟然给改成 firefox.com.cn 上的一个地址了，又是某智做的好事。而且是默认项，“恢复默认设置”也不管用。解决办法是设成 about:home，就能恢复 firefox (真正)默认的主页了。

某智现在做的，还算是在忍受范围内，没有之前那一堆“火狐魔镜”之类的东西了。不过依然让人不爽，比如默认搜索引擎设成 baidu ，这符合 mozilla 的官方政策吗？再次怀疑 mozilla 搞这些的必要性。

newline

2012-06-21T14:42:00+08:00

翻译是一件看起来简单做起来难的事。在维基百科上查到了这么一段话，想翻译成中文，吭吃吭吃好不容易写完，感觉却还是佶屈聱牙。

“There is also some confusion whether newlines terminate or separate lines. If a newline is considered a separator, there will be no newline after the last line of a file. The general convention on most systems is to add a newline even after the last line, i.e. to treat newline as a line terminator. Some programs have problems processing the last line of a file if it is not newline terminated. Conversely, programs that expect newline to be used as a separator will interpret a final newline as starting a new (empty) line.” (en.wikipedia.org)

“换行字符可以看作是行的结束符，也可以看作行之间的分隔符，这两种处理方式之间存在一些歧义。如果换行字符被当作分隔符，那么文件的最后一行就不需要再有换行字符。但是多数系统的做法是在最后一行的后面也加上一个换行字符，也就是把换行字符看作是行的结束符。这样的程序在处理末行没有换行字符的文件时，可能会存在问题。相反地，有的程序把换行符看作分隔符，就会把最末尾的换行字符看作是新行的开始，也就是多出了一个空行。” (zh.wikipedia.org)

P.S. 写了个简单的 tail 程序，却总是多出一行来。结果发现，用 getline 等函数其实就相当于把换行符当作了分隔符，而不是结束符 (C++ 的 getline 的定义就是 getline ( istream& is, string& str, char delim ), 指明了 “delim”)。所以最后的这个换行应该特殊处理。

asdf

2012-06-20T23:04:00+08:00

MS 出平板了？今天看到的这段话还真准，(apple) rarely makes a random jump into a disconnected market just to chase a shiny new trinket (I’m looking at you, Microsoft, and your Bing, MSN, and Zune debacles).

http://www.quora.com/Apple-Inc-2/Is-Apple-really-going-to-try-and-kill-Google

拭目以待吧。

P.S. 我本来要发 twitter 的，结果这字数限制实在让人崩溃，一句话都说不完。还是自家地盘爽。

GNU Screen: altscreen on

2012-06-19T13:06:00+08:00

折腾起来，真是一发而不可收。

刚发现了 screen 的这个选项，使能之后，退出程序或者按 ctrl-z 之后不会留下“残余”。

altscreen on|off

If  set to on, "alternate screen" support is enabled in virtual terminals,
just like in xterm.  Initial setting is `off'.

(git 需要设置下 pager，linuxtips.manki.in):

git config --global core.pager 'less -+X -+F'

Colorful Term

2012-06-19T10:35:00+08:00

虽然之前折腾过256 色的 terminal，但是总觉得效果好像不大对。下边是正确的折腾步骤。

首先环境变量 TERM 应该设成 xterm-256color (保证你有这个文件 /usr/share/terminfo/x/xterm-256color)。

在 ~/.bashrc 里写

export TERM=xterm-256color

但是要注意的是，这一行必须写在导入系统设置之前，也就是这样

# User specific aliases and functions

export TERM=xterm-256color

# Source global definitions
if [ -f /etc/bashrc ]; then
        . /etc/bashrc
fi

if [ -f /etc/profile ];then
        source /etc/profile
fi

否则，就是这副很普通的样子，

正确的话是这个俨然闪闪放光的样子，

所以默认的 .bashrc 把 “User specific aliases and functions” 放在前边，还是大有深意的。

(当然，影响的只是 ls，vim 等应该不受影响。)

screen 里不需要特殊的配置。有人提到需要换成 screen-256color (在 .screenrc 里写 term screen-256color)，但是我在 fedora 17 上没遇到什么问题。
然后是 solarized 的主题，就不细说了，把 gnome-terminal 和 vim 设好就 ok。

P.S. vim 的 set t_Co=256，貌似是没有任何作用，跟我用了 solarized 的 colorscheme 有关？不管怎么设，vim 和 gvim 都是一个样子的。

Perfect

2012-06-15T16:19:00+08:00

今天才突然意识到，”perfect” 有“完全”的意思。比如“完全平方数”是 “perfect square” ，“现在完成式”是 “present perfect”。

P.S. 数学小贴士：完全平方数都有奇数个因子，其它整数都有偶数个因子。

Migrate to Octopress - follow up

2012-06-14T21:45:00+08:00

部署完发现问题还是挺多的。主要就是几个链接没有了，包括 feed, archive 等等。

搜索了一番，这里提到了对 blogger 的 redirect。代码在这 (github.com)。

其实就是几条 URL 匹配规则。因为 octopress 虽然基本是静态的，但是其实是有一个小的 web 框架的 (sinatra)，所以还是比较灵活。

我把我用的 heroku 部署相关的东西放这了 (github.com)。octopress 需要的 patch 在这 (github.com)。

Migrate to Octopress

2012-06-14T17:42:00+08:00

心血来潮，把 blog 换到了 octopress。用了几年的 blogger，以前看到 octopress/jekyll 的时候，从来都觉得没什么，blogger 这种 It just works™ 的就很好。结果昨天重装了个系统，头脑一热，顺带把 blog 也换了。人啊，奇怪的生物。

我这人特别不喜欢遇到 404 的链接，所以到了我迁移网站的时候，就理所当然要努力保证兼容性了。感谢 octopress，其实就是改个配置的事儿。

# file : _config.yml
permalink: /:year/:month/:title.html

然后用这个小工具把 blogger 上原来的文章和留言都抓过来。这段代码还有不少版本，我也是根据前人的稍微修改了下，具体使用的过程网上也有不少文章。这里还要感谢 blogger，把打包下载做得这么容易，让用户很容易就跑了。什么是大国心态?

然后由于我之前(好像)用的是 feedburner，所以这块就省事了，订阅我博客的人应该不需要什么改动。

然后写篇声明，写完后把 DNS 一改，就 ok 了，无缝迁移，哈哈。目前发现只有各个月的 archive 页面丢掉了，其它链接应该没有 404 的。

还有一点是，之前就开始用 disqus，所以留言也都还保留着。这个也很好，感谢 disqus。

网站放在 heroku 上，因为我不是很愿意把 blog 内容搞个 public repo，放到 github 上。但是 octopress 文档里的部署到 heroku 的方法不很 (很不!) 爽，因为要把生成的乱七八糟的内容都加到 repo 里。所以找了一个办法，给 octopress 打了个补丁:

还搜到了一个办法是利用 heroku 的 custom buildpack，嗯，太复杂。

octopress 是挺漂亮的，但是在 google 的过程中，发现大家都长一个样…

用 markdown 写的第一篇 blog，撒花。

P.S.

feed 还是出问题了，如果之前订阅的是 http://blog.zhangsen.org/feeds/posts/default, Google Reader 其实记录的仍然是这个地址，而不是重定向的 feedburner，TODO, FIXME。

rbtree in linux kernel

2012-05-27T16:48:00+08:00

正在(重新)看算法导论。这是看 http://lwn.net/Articles/184495/ 的一个小结。

红黑树作为近似平衡的二叉搜索树，由于高效的操作，尤其是插入和删除能很快的 rebalancing (不会 go off for an indeterminate period of time rebalancing itself)，所以在 kernel 里有很多应用。

kernel 里的红黑树在 lib/rbtree.c 里实现。为了效率，rbtree 不是按照黑盒子的方式实现的，用户必须实现自己的插入和搜索函数。因为如果用函数指针来指定比较操作，由此带来的大量的间接的函数调用势必会影响效率。

rbtree 的另一个特点是，跟 kernel 里的 list 类似，struct rb_node 是作为成员嵌套进用户的数据结构的，而不是像通常的课本上那样，定义一个节点的结构，然后把 satellite data 放进这个结构。rbtree 都是在这个 rb_node 上进行操作，如果涉及到了实际数据，比如插入和搜索，就需要用户自己实现。

从一个 struct rb_node 取得包含它的 struct 可以通过 container_of() 或者 rb_entry() 来实现。

rb_node 里包含左右子节点的指针，父节点的指针，还有节点的颜色。特殊之处在于用了一个 unsigned long 来同时记录颜色和父节点的指针。貌似是依赖于指针的最后两位一定是 0。所以可以把最后一位用来标记颜色。这样就省了一个 int。

搜索就是普通 BST 的搜索，遍历一下即可，没有特殊的地方。

而插入的时候，需要调用 rbtree 的几个函数。用户需要自己实现找到要插入的位置，然后调用 rb_link_node 来插入新节点，最后调用 rb_insert_color 来 fixup (recoloring)。

rbtree 还提供了几个函数来实现遍历，rb_first, rb_last, rb_next, rb_prev。

rbtree 还提供了对 augmented rbtree 的支持。Documentation/rbtree.txt 举了一个 interval tree 的例子。用户需要在插入和删除节点的时候需要提供合适的 callback 来处理 augmentation 信息。

P.S. 最近都是在 google docs 里写东西，然后遇到适合发布的就贴到 blog 里来。这样子的感觉好多了，不会在 blog 里留一堆废掉的草稿。当然，发布的只是很小一部分，比如已经写了将近 40 页的算法导论的笔记 (而且看了还不到一半)，估计不会发了 ;)

git internals

2012-04-19T21:14:00+08:00

这是在 beihang open source club 讲 git 的讲稿。正好借着这个机会把之前看的东西整理整理。其实好几个月之前就跟 grissiom 大概聊过这些内容了，但现在才找到机会(和动力)写下来。

这有带图片和(一点)格式的版本: https://docs.google.com/document/pub?id=1FFssCYnbMgKk9rEEctDWz23Ne8WV4Uy5rOIehX0Rdkw

0.

git 本质上是一个 content-addressable filesystem，然后在其上做了个 VCS 的界面。

git 一开始的设计都是围绕着怎么操作这个文件系统来的，所以原来的用户界面不是“那么的”友好。现在的界面已经好多了，但是明白底下这个文件系统的机制，能帮助你更好的发掘 git 的潜力。

prerequisite: 读者应该对 git 的基本使用方法，尤其是 staging area 有所了解。可以看此文 http://progit.org/2011/07/11/reset.html 的 The Three Trees of Git 一节。

1. plumbing 和 porcelain

git 一开始并不是想提供一个 VCS，而是一个 VCS toolkit。所以 git 有一些很底层的命令，由这些命令再组成更上层的界面。(UNIX 哲学)

底层的这些命令称为 plumbing commands，上层的命令称为 porcelain commands。

例子：

$ echo ‘test content’ | git hash-object -w –stdin
$ git cat-file -p d670460b4b4a

2. .git 目录结构

$ git init
Initialized empty Git repository in /home/jesse/src/gittalk/.git/

$ ls -a
. .. .git

$ ls -F .git
config description HEAD hooks/ info/ objects/ refs/

$ touch a
$ git add a
$ ls .git -F
config description HEAD hooks/ index info/ objects/ refs/

git 运行所需要的所有文件都在 .git 里。

config: 配置文件
description: GitWeb 用。
info: .git/info/exclude
hooks: 脚本

HEAD, index, objects, refs: git 的核心。

objects: 所有的数据
refs: 指向 commit object 的指针
HEAD: 当前 branch
index: staging area 信息

3. content-addressable filesystem

content-addressable filesystem，什么意思？就是一个简单的 key-value 系统。

git hash-object 把一个 object 作为 value 存入文件系统，然后返回这个 object 的 key。key 是一个长度为 40 的 sha1 值。

$ find .git/objects/ -type f
$
$ echo ‘test content’ | git hash-object -w –stdin
d670460b4b4aece5915caf5c68d12f560a9fe3e4
$
$ find .git/objects/ -type f
.git/objects/d6/70460b4b4aece5915caf5c68d12f560a9fe3e4

存入一个 value 后，可以通过 key 把它读取出来：

$ git cat-file -p d670460b4b4aece5915caf5c68d12f560a9fe3e4
test content

这里的 object 是一个字符串。

hash-object 也可以读取文件内容作为 value 存入：

$ echo ‘version 1’ > test.txt
$ git hash-object -w test.txt
83baae61804e65cc73a7201a7252750c76066a30

试试对文件做点修改：

$ echo ‘version 2’ > test.txt
$ git hash-object -w test.txt
1f7a7a472abf3dd9643fd615f6da379c4acb3e3a

现在文件系统或者数据库里有三个 object 了：

$ find .git/objects -type f
.git/objects/83/baae61804e65cc73a7201a7252750c76066a30
.git/objects/d6/70460b4b4aece5915caf5c68d12f560a9fe3e4
.git/objects/1f/7a7a472abf3dd9643fd615f6da379c4acb3e3a

也就是说，git 的操作是以文件为单位的，一个文件作出修改后，都以新的 object 存入。

object 存入时，用 zip 算法进行压缩，然后用 sha1 算法计算 key。

4. objects

注意到，上边的三个 object 存的都是文件内容，没有文件名或者创建时间这些信息，也没有用我们平时用 git commit 时填入的 commit message 等等。

git 有若干种 object，上边用 hash-object 创建的是 blob 类型的 object。

$ git cat-file -t 1f7a7a472a
blob

cat-file -t 打印某个 object 的类型信息。

还有两种比较重要的 object。tree object 和 commit object。tree 对应目录树的概念，把 blob 组织起来。而 commit object 与 tree 对应，并且 commit 之间有 parent-child 的关系，这样就能形成 VCS 的历史记录了。

5. tree

tree 类似于 UNIX 系统上的目录。一个 tree object 包含一组 tree entry。每个 tree entry 是一个 blob (其实是一个 blob 的 sha1 值)，或者是一个 subtree (的 sha1 值), 以及它们的名字、类型、权限。

$ git cat-file -p master^{tree}
100644 blob a906cb2a4a904a152e80877d4088654daad0c859      README
100644 blob 8f94139338f9404f26296befa88755fc2598c289      Rakefile
040000 tree 99f1a6d12cb4b6f19c8655fca46c3ecf317074e0      lib

master^{tree} 是 master 分支上最后一个 commit 所指向的 tree。这个 tree object 包含三个 entry (也就是三个 sha1 值)，其中两个是 blob，第三个是另一个 tree object。这三个 sha1 值还有对应的 mode 和 filename。

git 创建 tree 的方式是使用当前 staging area 的内容创建一个 tree object。所以需要先创建 staging-area 或者 index。

创建 index 的命令是 git update-index

$ git update-index –add –cacheinfo 100644 \
    83baae61804e65cc73a7201a7252750c76066a30 test.txt

把 83baae 这个 blob object (包含“version 1”的那个)，按照指定的 mode 和名字，加入 index。

100644 表示一个 normal file。文件还可以设为可执行，或者是符号链接。但是 git 支持的权限很有限，是 UNIX 上文件模型的子集。

然后用 git write-tree 创建 tree object。

$ git write-tree
d8329fc1cc938780ffdd9f94e0d364e0ea74f579

$ find .git/objects/ -type f
.git/objects/83/baae61804e65cc73a7201a7252750c76066a30
.git/objects/d6/70460b4b4aece5915caf5c68d12f560a9fe3e4
.git/objects/d8/329fc1cc938780ffdd9f94e0d364e0ea74f579
.git/objects/1f/7a7a472abf3dd9643fd615f6da379c4acb3e3a

$ git cat-file -p d8329fc1cc938780ffdd9f94e0d364e0ea74f579
100644 blob 83baae61804e65cc73a7201a7252750c76066a30    test.txt

$ git cat-file -t d8329fc1cc938780ffdd9f94e0d364e0ea74f579
tree

这样就创建了一个新的 tree object，它包含一个文件 test.txt。现在一共有三个 blob 和一个 tree 了。object 文件是包含类型信息的，git 能够知道 d8329fc 是个 tree object。

再创建一个 tree object。把当前目录下的 test.txt (包含”version 2”) 加入，并且加入一个新文件 new.txt。

$ git update-index test.txt
$ echo ‘new file’ > new.txt
$ git update-index –add new.txt

$ git write-tree
0155eb4229851634a0f03eb265b69f5a2d56f341

$ git cat-file -p 0155eb422
100644 blob fa49b077972391ad58037050f2a75f74e3671e92    new.txt
100644 blob 1f7a7a472abf3dd9643fd615f6da379c4acb3e3a    test.txt

这个 tree object 包含两个文件。

虽然 tree object 是有结构的，但仍然是很基本的数据。我们可以把之前创建的第一个 tree 读入staging area (现在的 staging area 是第二个 tree 里的东西)，并且放进一个子目录。

$ git read-tree –prefix=bak d8329fc1cc938780ffdd9f94e0d364e0ea74f579

$ git write-tree
3c4e9cd789d88d8d89c1073707c3585e41b0e614

$ git cat-file -p 3c4e
040000 tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579      bak
100644 blob fa49b077972391ad58037050f2a75f74e3671e92      new.txt
100644 blob 1f7a7a472abf3dd9643fd615f6da379c4acb3e3a      test.txt

新建的第三个 tree 相当于包含前两个 tree 的内容。(注意，这些操作都是在 index 和后端存储之间进行的，没有动到 working dir。)

6. commit object

文件的基本信息在 tree 里保存，那 tree 的基本信息呢？比如创建 tree 的时间、人物、原因。所以 git 又提供了 commit object 保存这些信息。

$ echo ‘first commit’ | git commit-tree d8329f
9fa147d9147f7dbbfa641ebe2992a336bc1a4c93

git commit-tree 能创建一个新的 commit object。

$ git cat-file -p 9fa147d9
tree d8329fc1cc938780ffdd9f94e0d364e0ea74f579
author Jesse Zhang <xxx@xxx> 1334569863 +0800
committer Jesse Zhang <xxx@xxx> 1334569863 +0800

first commit

现在能看到 git log 的样子了。

再创建两个 commit。

$ echo ‘second commit’ | git commit-tree 0155eb -p 9fa147d91
b951b414a680c16e48c095a080b435874a5da79e

$ echo ‘third commit’ | git commit-tree 3c4e9c -p b951b414
29c0bd0cd9084ad30e0eaca38632500d700d6644

这两个 commit 都用 -p 指定了 parent commit。第一个 commit 没有指定 parent，所以是一个 initial commit，或者 root commit，或者 orphan commit。

现在已经能用 git log 了。

$ git log –stat 29c0bd0
commit 29c0bd0cd9084ad30e0eaca38632500d700d6644
Author: Jesse Zhang <xxx>
Date:   Mon Apr 16 17:54:25 2012 +0800

    third commit

bak/test.txt |    1 +
1 files changed, 1 insertions(+), 0 deletions(-)

commit b951b414a680c16e48c095a080b435874a5da79e
Author: Jesse Zhang <xxx>
Date:   Mon Apr 16 17:54:12 2012 +0800

    second commit

new.txt |    1 +
test.txt |    2 +-
2 files changed, 2 insertions(+), 1 deletions(-)

commit 9fa147d9147f7dbbfa641ebe2992a336bc1a4c93
Author: Jesse Zhang <xxx>
Date:   Mon Apr 16 17:51:03 2012 +0800

    first commit

test.txt |    1 +
1 files changed, 1 insertions(+), 0 deletions(-)

7. git references

使用上边提到的 objects，已经可以建立起完整的历史了，但是所有的 key 都是 sha1 值，不便使用。利用 references，或者 refs，可以把 sha1 值与一个名字联系起来。

一个 ref 是一个简单的文本文件，其内容是一个 sha1 值，表示这个 ref 指向的 object。

$ find .git/refs
.git/refs
.git/refs/heads
.git/refs/tags

$ find .git/refs -type f
$

新建一个 “head reference” (ref 还分好几种，这种指向某个 commit 的叫 head ref，放在 .git/refs/heads/ 目录下)，让它指向最新的 commit：

echo “29c0bd0cd9084ad30e0eaca38632500d700d6644” > .git/refs/heads/master

这样就用这个 ref 指代其 sha1 值了：

$ git log –pretty=oneline master
29c0bd0cd9084ad30e0eaca38632500d700d6644 third commit
b951b414a680c16e48c095a080b435874a5da79e second commit
9fa147d9147f7dbbfa641ebe2992a336bc1a4c93 first commit

git 不推荐手动修改 ref 文件。可以使用 update-ref 命令：

$ git update-ref refs/heads/master 29c0bd0cd9084ad30e0eaca38632500d700d6644

这其实就是 git 里的 branch，一个很简单的指向某个 commit 的指针，或者说 ref。

用 update-ref 创建一个新 branch：

$ git update-ref refs/heads/test b951b414a

$ git log –pretty=oneline test
b951b414a680c16e48c095a080b435874a5da79e second commit
9fa147d9147f7dbbfa641ebe2992a336bc1a4c93 first commit

repo 现在的结构：

并且可以使用 git branch 了，已经有了两个分支：

$ git branch
* master
test

在创建新分支的时候，git 仅仅是创建了一个简单的 ref，把新分支名与指定的 commit 联系起来。所以创建分支是个非常 cheap 的。

那么 merge 分支呢？

1). git 拿到要进行合并的分支，找到它们所代表的 sha1 值，
2). 读取这两个 sha1 值所表示的 commit object，
3). 读取这两个 commit 对应的 tree object。
4). 创建新 tree。把这两个 tree 合并到一块，产生一个新的 tree (以及可能的新的 blob)
5). 创建 merge commit。把这个 tree 提交为新的 commit，就是最后的 merge commit。merge commit 有多个 parent。

8. HEAD

git 怎么知道当前的最新 commit 呢？或者说怎么知道当前所在的分支？

HEAD 文件用来记录当前的分支。HEAD 也是一个 ref，但是它称作一个 symbolic ref，因为 HEAD 文件里不是包含 sha1 值，而是指向另外一个 ref (refs 目录里的一个文件)。

$ cat .git/HEAD ref: refs/heads/master

执行 git checkout <branch> 的时候，git 就会更新 HEAD 文件，切换到新分支。

执行 git commit 的时候，新创建的 commit object 的 parent 就是 HEAD 所指向的那个 commit。

可以使用 git symbolic-ref 来读取或修改 HEAD 这种 symbolic ref：

$ git symbolic-ref HEAD
refs/heads/master

$ git symbolic-ref HEAD refs/heads/test
$ cat .git/HEAD
ref: refs/heads/test

9. 不讲

tags, remotes

10. 资料

本文所有内容来自 Pro Git 第 9 章，Git Internals, http://progit.org/book/ch9-0.html。

其他资料：

git 手册的 Hack git 那一章，http://schacon.github.com/git/user-manual.html#hacking-git 。尤其是其中提到的 git 的第一个 commit:

$ git checkout e83c5163

gnome3

2012-04-17T20:53:00+08:00

gnome3 大多数时候还是比较顺手的。不顺手的地方基本也能找到相应的插件。

1. alt-tab 把窗口都组合到一块去，这个比较恶。幸好有一些插件，比如 https://extensions.gnome.org/extension/38/windows-alt-tab/ 。能恢复到原来的样子。win7 在任务栏上把窗口也组合到一块，也很烦人，但是起码 alt-tab 是正常的。(而且人家有配置选项好吧？）

2. 关机按钮。这个就不多说了，相应的插件目前在 https://extensions.gnome.org 上排第一位。(https://extensions.gnome.org/extension/5/alternative-status-menu/)

3. 现在的网络管理简直就是个鸡肋，想配 VPN 都没地方找。不过幸好，还可以从命令行运行原来的：

$ nm-connection-editor

然后就可以照常导入 vpnc 的配置文件了，等等。

最后再强调一下，gnome3 大多数时候还是比较顺手的 :) 确实能让人感觉更专注，支持插件也是个很棒的设计。

kindle and wifi

2012-04-16T20:17:00+08:00

The Kindle was designed in the USA and so uses only the US Wi-Fi channels one to 11

http://www.pcpro.co.uk/realworld/370147/why-your-kindle-wont-connect-to-wi-fi

怪不得我的 kindle 死活连不上 wifi。只好把自动扫描信道关了，选个 11 以内的。