RSS Feed

September, 2011

  1. Git源码阅读——git的cache结构

    September 26, 2011 by xudifsd

    在git的源码中有这样一句

    #define cache_entry_size(len) ((offsetof(struct cache_entry,name)+(len)+8)\
    &~7)

    开始我死活看不懂这什么意思,8这样的幻数已经够吓人的了,再来个对7取反码,实在看不懂。但是经过几天的研究终于明白这是什么意思了。

    背景

    前面的代码是描述cache的,cache在git中可以类比于CPU的高速缓存——为了加快访问速度,cache主要考虑的是工作目录和暂存对象(已经加到cache中但是并没有提交的对象)的差别,因此它只要将工作目录中的文件的stat信息保存即可。在新版的git中这样的概念改名叫做index了,所以现在所有的cache信息都存在.git/index文件中。保存信息的结构体原型如下:

    struct cache_entry {
    	struct cache_time ce_ctime;
    	struct cache_time ce_mtime;
    	unsigned int ce_dev;
    	unsigned int ce_ino;
    	unsigned int ce_mode;
    	unsigned int ce_uid;
    	unsigned int ce_gid;
    	unsigned int ce_size;
    	unsigned char sha1[20];
    	unsigned short ce_flags;
    	char name[0];
    };

    其中需要注意的是结构体的最后一个成员name,它用来存暂存对象的相对路径,是一个长度为0的数组,在gcc中使用这样的定义来让name的长度不定长,不用指针的原因就是git总是使用mmap(2)来读取index文件,之后直接将cache_entry指针指向正确的位置就行了,而且写到磁盘的时候也不需要再对文件名取指针内容,直接write(2)就行。而路径的长度信息就存在ce_flags中,但是它仅仅用低12位来存长度(这些已经足够存路径名了,因为在Linux系统中PATH_MAX == 4096 == 212),其他位用做其他用途,这就是为什么程序源码中还有一句:

    #define ce_namelen(ce) (CE_NAMEMASK & ntohs((ce)->ce_flags))

    这样一个宏函数可以求出ce指针的文件名长度。如果有一个cache_entry的指针ce,那么就可以通过cache_entry_size(ce_namelen(ce))来求得ce的实际大小。

    正由于cache是为了快速访问的,所以它的设计需要最大限度的考虑速度,这就是文章开头定义存在的原因:为了内存对齐——CPU访问对齐的变量更快,之所以必须要进行手工的对齐就是因为git是使用mmap(2)进行文件的读取。如果考虑到这一点那么最开始的代码也好解释了:对7取反码可以让结果能被8整除,但是如果一开始就不能被8整除那么结果就会小于另一个运算子,这样一来加8就是为了防止结果变小。但是这样怎么保证内存对齐的呢?因为在内存中所有cache元素都是存在数组中的,前一个元素的长度能被8整除,那么后一个元素的起始位置就能被8整除,而在mmap(2)时内核会选择一个对齐的地址放整个数组,这样一来数组中所有的元素都是对齐的了。

    读源码就像做侦探游戏一样,总是要猜作者到底要表达什么,而读好的代码更可以让人学到很多。


  2. Git源码阅读——对象数据库

    September 22, 2011 by xudifsd

    git其实就是一个CAS(Content-addressable storage)系统,要想取得一个对象就必须提供该对象的哈希值而非对象的路径,这样特性的实现方法就是使用对象的哈希值作为对象的路径。git使用的哈希算法是sha1算法。git的对象数据库还有一个属性就是所有的对象只能添加、读取,不能删除、修改,这样保证了整个代码历史的完整性。

    git对象文件

    所有git对象都保存在.git/objects中,例如

    .git/objects/03/7dc5e0f2cd4e0f4ff2385843beab28170c31f5

    表示一个对象,.git/objects目录下的目录名03是对象sha1值的前两位,文件名则是剩余的sha1值,这样类似于数据桶的结构可以让打开文件更快。由于git不保存文件的差别而是保存整个文件,所以对于一个只修改了几行的文件git也会保存两份几乎完全相同的内容,当跟踪的历史变长时数据冗余也会越来越多,这样的对象叫松散对象。不过git可以对所有对象进行打包,保存每个文件的不同,这样的动作叫垃圾收集,git会在每次进行网络传输或运行git gc时进行。

    git中所有对象都有一个公共的文件头,格式是:

    type size\0

    其中type是对象对应的类型,而size则是整数的字符串表示,表示对象内容的长度,’\0’之后的内容就是各个对象的内容。

    读取操作

    在git中我们只能通过20个字节的sha1哈希值来取得文件的内容,在代码中可以使用

    read_sha1_file(sha1, type, &size)

    来进行读取,参数type和size分别用于存从文件头中读出的对象类型和内容大小。但是read_sha1_file并不仅仅只是打开,解压再读取,由于可能对象已经被打包,read_sha1_file也包括了unpack之类的函数用来解析打包后的文件。

    写操作

    我们通过

    write_sha1_file(buffer, buffer_len, type, return_sha1)

    来进行写操作,其中buffer是对象的内容,buffer_len是内容的大小,type是对象的类型,最后通过return_sha1来接收刚刚写入对象的sha1值。需要注意的是写操作的实现:由于I/O可能会被中断,如果直接创建sha1文件,一旦中断会导致麻烦的数据不完整,而产生硬连接的link则很难被打断,所以为了最大限度地保证数据完整性,git使用临时文件:先调用mkstemp产生一个临时文件,并将内容写入,成功之后会调用link产生一个文件名为对应sha1值的指向临时文件的硬连接,再unlink临时文件。

    对象的属性

    git共有四种类型的对象:blob,tree,commit和tag。

    blob是最基本的对象,不能引用任何其他对象,它类似于文件系统中的文件,但与文件不同的是它自身没有任何文件名,它所包含的信息只有文件内容。这样的文件名和文件内容的分离可以实现对象的重用:如果你将一个文件加到git,然后对文件名进行修改但是没有修改文件内容,之后再将其加到git,这样并不会产生另一个blob对象,修改的只是tree对象中的引用名而已。

    tree对象的内容包括对其他tree对象或blob对象的引用和对应对象的名字及模式,这样的属性让tree非常类似于文件系统中的目录,tree引用tree类似于目录中的子目录,tree引用blob类似于目录中的文件。

    commit对象可以引用一个tree对象和零个或多个commit对象,commit引用的tree对象表示整个项目的根目录,而被引用的commit对象表示父commit,如果没有引用其他的commit,则表示该commit对象是整个项目的初次提交,而多个commit引用则表示由多个commit合并而来。

    tag对象可以引用任意类型的一个对象,它的作用就是给某个对象一个方便人们记忆的名字,比如可以对一个项目某个commit对象标为v1.0来表示这个项目的1.0版本,也可以将存有项目公钥的blob对象打上标签。


  3. 你所了解的历史只是真实历史的一部分

    September 15, 2011 by xudifsd

    我们都知道1861年美国打了一场著名的解放奴隶的南北战争,但是对于这个战争的原因却有不同的观点:

    按照中国教科书上的观点,北方和南方的经济基础是不一样的,北方主要是工业生产,而这些生产很多都是半自动化的,这样的产业对于劳动力的需求很低,但是对于自由消费者的需求却很旺盛,因此北方人民一直反对奴隶制度。与北方相反,南方主要是农业,而农业的自动化程度很低,所以整个南方对于劳动力需求旺盛,而廉价的黑奴则是最好的选择。

    教科书上让我们相信了,美国人民南北战争的原因一开始就是经济原因,与道德无关。

    但是林达的《我也有一个梦想》观点却更加令人信服,他是从移民成分的角度来分析的:北方的移民大部分都是“政治移民”,他们移民的原因并不是为了淘金,也不是为了发家致富而是他们在英国本土受到了政治迫害或者是宗教迫害。正是由于他们是“政治移民”而非“经济移民”,再加上他们受教育程度较高,他们从一开始就对蓄奴有反对的心理。而南方,特别是佐治亚这样的州当初是政府支持移民的,他们的移民口号是“把穷人都送走,英国会更富”,所以南方的移民大部分都是穷人,甚至是最为穷困的人,他们几乎都没有受过多少教育,因此他们对于北方人所坚持的反对蓄奴是不屑一顾的。

    从林达的口中我们可以得出美国人民南北战争的最基本原因是道德。

    我觉得林达的解释更加深入,正是由于北方人民一开始在道德层面就不是很支持奴隶制度,之后他们才发展劳动力需求少的工业生产,然后才造成了教科书上所说的局面。我倒不愿意把这解释成为中国的政治宣传,因为任何人在看待历史问题时都会有一定的局限性,要想真正弄明白一些历史真相那么无论是批评的或者是赞扬的都必须了解,任何人了解的历史都只是真是历史的一部分。


  4. 从美国宪法第一修正案到言论自由

    September 13, 2011 by xudifsd

    我们总是说美国人民非常自由,其中我觉得最为重要的自由就是言论自由了。这样的自由甚至被写入宪法修正案,也就是美国宪法非常著名的第一修正案

    条文的内容如下:

    Congress shall make no law respecting an establishment of religion, or prohibiting the free exercise thereof; or abridging the freedom of speech, or of the press; or the right of the people peaceably to assemble, and to petition the Government for a redress of grievances.

    虽然说懂得这些,但是还是无法深入理解言论自由。最近在看林达写的《历史深处的忧虑》,这本书非常好,里面以信件的形式描述了美国人民的政治生活以及美国政治产生的原因,读完这本书觉得受益匪浅,书中很大的一部分都提到了言论自由,但是由于书中的内容有些分散,所以我就在这把书中的观点集中一下。

    书中说道:

    在美国,“言论自由”和“追求真理”之间的界限,是划得非常清楚的。在这里,这是两件完全不相关的事情,言论自由只有一个目的,保证每个人能够说出他自己的声音,保证这个世界永远有不同的声音。而绝不是希望到了某一天,人们只有一种声音,哪怕公认为这是“真理”的声音。

    美国人民在考虑言论自由时和我们最大的一个不同就是他们认为言论自由和真理的探讨是无关的,也就是说言论自由并不是为了保证真理的产生而存在的。而我们在讨论时总是想要通过这样的自由来获得真理。其实将言论自由和真理绑定在一起是非常危险的,因为真理有一个非常可怕的属性——排他性,如果人们明确认为或者在潜意识中觉得言论自由是通往真理的唯一途径,那么在这种概念下,一旦自己觉得已经寻求到真理时,那么将言论自由抛弃也就成为顺利成章的事了。所以在很多国家,言论自由变成了非常可怕的东西,一旦人民开始利用这种自由往往意味着政权的垮台,而一旦新政权开始执政,又开始借助真理的排他性来限制言论自由。

    书中还举了一个滥用言论自由的例子——三k党制作了一部“种族与情理”的电视片,要在公共电视台播放。到底要不要将言论自由给公认的恶人,按照中国人的观点是“既然公认的恶人,那么剥夺他的权利也无可厚非”,但是我记得西方有个哲学家说的一句话可以解释为什么美国人将恶人平等对待——“我不同意你的观点,但是我誓死保护你说出你观点的权利。”

    书中的解释就更有意思了:

    在本世纪,美国的荷尔姆斯法官曾经就类似观点提出过很形象化的比喻,他把它称为言论的“战场化”和“市场化”。他认为,与其让不同的观点象在战场上一样殊死决斗,一方一定要扼杀另一方,那还不如把这些言论抛入“市场”,让他们去竞争,看看到底哪一种观点能被大家所接受。同意这一理论的人相信,宪法第一修正案的力量所在,正是让大家分享言论自由的理想和它的原则。根据这一理论,如果三K党播放他们的节目, 克莱弗牧师们所应该做的事情,不是去阻止他们的节目,而是应该也播出自己的观点。在这种“市场竞争”中能最终站得住脚的理论,才是更可靠和更持久的。但是,克莱弗牧师显然并不同意这样的观点。

    接受了三K党法律委托的斯蒂芬·潘弗所说的一段话, 颇能代表今天一般美国人的看法:“自由言论就是自由言论,对于流行观点和非流行观点都是一样的。我们不可能一边宣称这是一个自由的国家,一边又把言论划为可接受的和不可接受的两部分。 如果有一种检查制度可以把三K党从电视里剔出去,那么,同样的制度也许早就把马丁·路德·金的讲话从阿拉巴马州剔出去了。”必须听那些听不下去的话,“这正是我们必须为自由支付的代价”。

    在明白这些之前最让我吃惊的一件事就是08年美国大选时一名白人在网上公开宣布要刺杀奥巴马,而且最终法院的判决结果竟然是“这样的帖子不构成真正的威胁,因此该言论受到宪法第一修正案的保护”。现在我算是明白了“美国人把政府当成假想敌,任何公民只要不犯罪,真的几乎是想干什么就干什么了”,我想这样的社会也只有美国这样历史包袱少的国家能够承受的。