假期闲在家里，几乎没有什么事情可做，打算看看一些代码，了解一下他们是怎么实现的。当然首先想到的就是虽然一直在用，但是一直都没有用明白的Git了。

Git的项目位置在这里 。因为水平有限，而且git的用户手册也推荐从第一个版本开始进行，所以我当然很乐意从最早的版本开始了。

Git的第一个版本是Linus Torvalds在两周之内完成的。如果你直接clone了整个项目，你依然能获得Git的第一次提交：

1
git checkout e83c5163316f89bfbde7d9ab23ca2e25604af290

你将能看到一些有趣的提示：

1
2
3
4
5
6
7
8
9
10
11
12
13
$ git checkout e83c5163316f89bfbde7d9ab23ca2e25604af290
Note: checking out 'e83c5163316f89bfbde7d9ab23ca2e25604af290'.

You are in 'detached HEAD' state. You can look around, make experimental
changes and commit them, and you can discard any commits you make in this
state without impacting any branches by performing another checkout.

If you want to create a new branch to retain commits you create, you may
do so (now or later) by using -b with the checkout command again. Example:

  git checkout -b <new-branch-name>

HEAD is now at e83c51633... Initial revision of "git", the information manager from hell

基本概念

这里面只有八个c文件。以及一份比较长的声明：里面提到了git所使用的object database和 currrent directory cache 概念。

所谓object database指的是对象都根据他们的内容命名，然后每个对象可以通过使用这个命名来引用其他对象，根据这个来进行对象的层次引用。实际的实现方式就是每一个对象都用一个以哈希值命名的文件存储，然后通过在文件里面加入一个type字段来指定对象的类型。

在这个版本中，对象分为下面几种类型^1：

  • blob： 最基本的对象。不能引用任何其他对象，它所包含的信息只有文件内容。
  • tree ：其实就是一个引用和对象的排序列表，包括 blob 或其他对象的引用和对应对象的名字及模式，非常类似于文件系统中的目录。
  • changeset：这个对象对应现在的commit。它不仅有tree的物理状态，还描述了了我们如何得到的这个tree。
  • trust：对应现在的tag。这是为了验证人们对git产生的历史，防止篡改提交历史的作用，也是用于标记当前做的事情。

所谓current directory cache指的是一个包含目录内容的二进制文件；通过检索这个文件可以获得相关的信息。在这个版本中，它就是.dircache/index文件，实现方式是一个数组直接内存映射为一个文件。如果将整个.dircache视为一个数据库的话，这个文件用于存储全局变量。

　为了使现在依旧能编译成功，需要修改编译选项，将Makefile中的LIBS= -lssl改为LIBS= -lcrypto -lz 。^3若是希望一切正常，需要在cache.h中添上一行#include <string.h> ，并且将 read-cache.c 中的231行^2改为：if (size >= sizeof(struct cache_header))

我们可以使用make all编译所有的文件得到可执行文件。这个版本的使用逻辑如下：

首先通过init-db来初始化一个文件目录。在这个文件夹内做增删改之后，使用update-cache将改过的文件保存为index文件。通过write-tree将整个的更改提交到缓冲区中。可以用show-diff来查看本地文件与缓冲区中的文件的区别。

其中各个文件的功能如下：

  • init-db 初始化工作目录，类似于git init 。将在当前文件夹中创建一个.dircache目录，在其中创建一个objects文件夹，再在其中创建从00到ff的255个子目录，用于存放SHA1文件。
  • read-cache.c是唯一不产生可执行文件的翻译单元。这里面集合了对SHA1文件的一系列操作。其中有一个函数read-cache是用于读取和操作全局文件.dircache/index的。

update-cache

这个文件中所做的事情是，在index中对cache的内容进行存储，并将改动存到文件夹中。存储cache的数据结构定义如下（cache_entry）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
 * The "cache_time" is just the low 32 bits of the   "cache_time"是time的低32位。
 * time. It doesn't matter if it overflows - we only 这对于time是否溢出都无所谓。
 * check it for equality in the 32 bits we save. 我们只检查他与我们保存的低32上是否相等。
 */
struct cache_time {
    unsigned int sec;
    unsigned int nsec;
};

/*
 * dev/ino/uid/gid/size are also just tracked to the low 32 bits     dev/ino/uid/gid/size也是只追踪低32位。
 * Again - this is just a (very strong in practice) heuristic that   重复：这就是一个（在实践中非常强大的）启发式：
 * the inode hasn't changed.                                         inode没有发生改变。
 */
struct cache_entry {
    struct cache_time ctime;
    struct cache_time mtime;
    unsigned int st_dev;
    unsigned int st_ino;
    unsigned int st_mode;
    unsigned int st_uid;
    unsigned int st_gid;
    unsigned int st_size;
    unsigned char sha1[20];
    unsigned short namelen;
    unsigned char name[0];
};

在update-cache.c中，

  1. 首先调用了read_cache以初始化存储cache全局变量（或者），那是一个cache_entry的结构体数组，然后尝试读取index文件，将原有的内容加载到这个数组中。并创建一个index.lock文件。
  2. 然后update-cache会对每个参数调用一个add_file_to_cache的函数。在这个函数中会分配一个cache_entry结构体，将文件的stat里的相应属性填到这个结构体中
  3. 再往后的过程中，首先通过使用zlib库将文件连同文件的stat压缩为最大200 byte的串，再使用SHA1获得这个串的hash值写到cache_entry的sha1属性中。(index_fd)
  4. 确认这个entry是否已经在全局变量的数组中：有则更新、否则添加一条记录。(add_cache_entry)
  5. 将这个数组的相关信息写到一个cache_header结构体里面，连同整个数组都做一次SHA1，然后将结果存储到index.lock中。
  6. 将index.lock重命名为index，从而覆盖原有的index文件。

其中，cache_header的数据结构定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * Basic data structures for the directory cache 文件夹缓冲区的基本数据库
 *
 * NOTE NOTE NOTE! This is all in the native CPU byte format. It's   注意注意注意！这里全部采用的是本地CPU字节格式化。这里
 * not even trying to be portable. It's trying to be efficient. It's 甚至没有做尝试来使它可迁移化。这里是试着让他变得更有效。
 * just a cache, after all.                                          毕竟，它只是一个Cache。
 */

#define CACHE_SIGNATURE 0x44495243	/* "DIRC" */
struct cache_header {
    unsigned int signature;
    unsigned int version;
    unsigned int entries;
    unsigned char sha1[20];
};

总结

说实话读这个比我预想的轻松一点。而且发现有一些地方写得实在是很精妙的。

下面这里是一个很简单高效的内存对齐，直接+8之后后面几位直接取0。

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

然后还有一个很老练的地方是在之后，这里先给一个指针再往里面填东西的过程。我感觉这个过程比分开来写会紧凑得多了。

1
2
stream.next_in = metadata;
stream.avail_in = 1+sprintf(metadata, "blob %lu", (unsigned long) st->st_size);

其实讲道理，两周时间内完成一个东西并不是特别难的事情，但是更为重要的是编码中一些习惯和技巧。也许这只是一些惯例，不过也是说明自己还是手生，没有办法熟练地了解这些内容。