最近想了解一下 Git 的實(shí)現(xiàn)耽梅，首先是看了 pro git 的 git 原理部分挨约。看完之后對(duì) git 的實(shí)現(xiàn)有了個(gè)大概的了解儒飒，但還是不過(guò)癮谬莹。于是把 git 的源碼 clone 下來(lái)看源碼是如何實(shí)現(xiàn)的，但是 git 的源碼實(shí)在太多了桩了，要耗費(fèi)太多精力了附帽。
我嘗試把跳轉(zhuǎn)到 Git 的第一個(gè) commit，代碼量就少了很多井誉，只有差不多 1000 行左右蕉扮。修改了一些代碼把程序編譯起來(lái)了】攀ィ看了下初始版本的 git喳钟，發(fā)現(xiàn)很多概念還是可以和現(xiàn)在的 git 的相通屁使，有閱讀的價(jià)值。
之后還看到 jacob Stopak 的解析奔则，對(duì) git 的代碼做了很多注釋蛮寂。看到的時(shí)候很是驚喜易茬，因?yàn)榫W(wǎng)上對(duì) git 這樣的解析很少酬蹋，看日期還是今年的 5 月 22 號(hào)發(fā)布的，新鮮的 >_<抽莱。
What Can We Learn from the Code in Git’s Initial Commit?
獲取源代碼并編譯
在這里使用 Jacob Stopak 的項(xiàng)目范抓，它對(duì) Git 的第一個(gè) commit 里面的代碼添加了大量注釋?zhuān)€修改了一些代碼方便我們?cè)诂F(xiàn)代操作系統(tǒng)上編譯。
獲取代碼
git clone https://bitbucket.org/jacobstopak/baby-git.git
編譯直接 make 就好了岸蜗，不過(guò)這里還是會(huì)出現(xiàn)編譯錯(cuò)誤尉咕，需要在 cache.h 文件修改下面的變量，加上 extern
extern const char *sha1_file_directory;
extern struct cache_entry **active_cache;
extern unsigned int active_nr, active_alloc;
直接 make
make
如果你想要嘗試使用 github 上 git 的源碼來(lái)編譯的話(huà)璃岳，可以進(jìn)行下面操作
# 先 clone 源碼
git clone https://github.com/git/git.git
# 根據(jù) log 找到第一個(gè) commit
git log --reverse
# 檢出第一個(gè) commit
git checkout e83c5163316f89bfbde7d9ab23ca2e25604af290
這里的源碼直接 make 的話(huà)會(huì)編譯失敗年缎，還需要作出下面的修改
首先是 Makefile 文件
# 把 LIBS 這行修改成這樣
LIBS= -lcrypto -lz
然后在 cache.h 中
#添加頭文件
#include <string.h>
和前面同樣的操作，把下面幾個(gè)變量加上 extern
extern const char *sha1_file_directory;
extern struct cache_entry **active_cache;
extern unsigned int active_nr, active_alloc;
之后就可以直接 make 了铃慷〉ノ撸或者你嫌麻煩可以用我 z.diff 文件，直接 apply 一下犁柜。
git apply z.diff
效果一樣洲鸠。
源碼結(jié)構(gòu)
可以看到 git 的開(kāi)始的時(shí)候只有 8 個(gè) .c 文件和 1 個(gè) .h 文件。
可以看到一下包含代碼和注釋行數(shù)只有 1037 行
cat *.c *.h | wc -l
1037
其中 7 個(gè) .c 文件可以對(duì)應(yīng)現(xiàn)在的 7 個(gè) git 命令
| 文件 | 當(dāng)前 Git | 作用 |
|---|---|---|
| init-db | git init | 初始化 git 倉(cāng)庫(kù) |
| update-cache | git add | 添加文件到暫存區(qū) |
| write-tree | git write-tree | 將暫存區(qū)的內(nèi)容寫(xiě)入到一個(gè) tree 對(duì)象到 git 的倉(cāng)庫(kù) |
| commit-tree | git commit | 基于指定的 tree 對(duì)象創(chuàng)建一個(gè) commit 對(duì)象到 git 的 倉(cāng)庫(kù) |
| read-tree | git read-tree | 顯示 git 倉(cāng)庫(kù)的樹(shù)對(duì)象內(nèi)容 |
| show-diff | diff | 顯示暫存的文件和工作目錄的文件差異 |
| cat-file | git cat-file | 顯示存儲(chǔ)在 Git 倉(cāng)庫(kù)中的對(duì)象內(nèi)容 |
至于 read-cache.c 文件則定義了一些程序一些公用的函數(shù)和幾個(gè)全局變量馋缅。
概念分析
Linus Torvalds 在 readme 中對(duì) git 的實(shí)現(xiàn)原理作出了一些解釋扒腕。
首先它給出了為什么要使用 git 這個(gè)名字的原因
- 隨機(jī)的三個(gè)字母組合，沒(méi)有和其他的 unix 命令沖突
- 簡(jiǎn)單
- 當(dāng)它好使的時(shí)候叫 global information tracker
- 不好使的時(shí)候叫 goddam idiotic truckload of sh*t
- random three-letter combination that is pronounceable, and not
actually used by any common UNIX command. The fact that it is a
mispronounciation of "get" may or may not be relevant.- stupid. contemptible and despicable. simple. Take your pick from the
dictionary of slang.- "global information tracker": you're in a good mood, and it actually
works for you. Angels sing, and a light suddenly fills the room.- "goddamn idiotic truckload of sh*t": when it breaks
它有兩個(gè)核心的概念
- objects databases
- current directory cache （相當(dāng)于現(xiàn)在的暫存區(qū)）
Object Databases
object database 相當(dāng)于一個(gè)基于文件系統(tǒng)的鍵值對(duì)數(shù)據(jù)庫(kù)萤悴，用文件的 sha-1 值作為鍵瘾腰，在 .dircache/objects 中存放各種類(lèi)型的數(shù)據(jù)。
在這里介紹三種類(lèi)型：
- blob
- tree
- commit
blob 對(duì)象用來(lái)存儲(chǔ)完整的文件內(nèi)容覆履，用于 git 追蹤文件內(nèi)容蹋盆。blob 的結(jié)構(gòu)
blob size\0blobdata(file content)
git 除了要追蹤文件內(nèi)容外還要追蹤文件名、文件存儲(chǔ)路徑和權(quán)限屬性之類(lèi)的信息硝全。這個(gè)時(shí)候我們引入 tree 對(duì)象來(lái)存儲(chǔ)這些信息栖雾。tree 只會(huì)保留 blob 對(duì)象的 sha-1 值，不會(huì)追蹤文件內(nèi)容伟众。（現(xiàn)在的 tree 對(duì)象還會(huì)可以 tree 對(duì)象嵌套 tree 對(duì)象析藕，現(xiàn)在這里還沒(méi)有）
大致的結(jié)構(gòu)是這樣的（省略了頭）
100644 a.txt (6e666502660a7e810b276afd62523c56b34c1671)
100644 b.txt (b 的 sha-1 值)
100644 c.txt (c 的 sha-1 值)
commit 對(duì)象，可以理解為我們的一個(gè) commit赂鲤，它記錄了特定時(shí)間的目錄樹(shù)（tree 對(duì)象）噪径、父 commit 的 sha-id（可以有多個(gè)或 0 個(gè)）柱恤、作者和提交者信息和對(duì)應(yīng)的 commit message。git 通過(guò) commit 對(duì)象來(lái)追蹤存儲(chǔ)庫(kù)的完整歷史開(kāi)發(fā)記錄找爱。
同樣是大致結(jié)構(gòu)：
tree 1c93ac491de01f734fedbe70f31c47ca965c93b6
parent 4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
author <zzk@archlinux> Sat Jun 27 14:41:43 2020
committer <zzk@archlinux> Sat Jun 27 14:41:43 2020
second commit
現(xiàn)在的 git 同樣還是一直在使用上面這些概念梗顺，通過(guò)管理這些對(duì)象來(lái)實(shí)現(xiàn)我們的版本控制。
Git 把每個(gè)文件的版本都完全保存下來(lái)车摄，會(huì)不會(huì)占用很多空間寺谤？是不是太暴力了？
git 會(huì)使用 zlib 對(duì)所有對(duì)象進(jìn)行壓縮吮播，代碼這類(lèi)文本數(shù)據(jù)可以做到很高的壓縮率（因?yàn)榇a中很多都是重復(fù)的变屁，比如關(guān)鍵字、函數(shù)調(diào)用）意狠。在現(xiàn)在的 git 還引入了 packfiles 機(jī)制粟关，會(huì)查找找命名及大小相近的文件，只保存文件不同版本之間的差異环戈，也是可以只保存 diff 的闷板。關(guān)于暴力的話(huà)，就是空間換時(shí)間方式了院塞，這樣做在版本跳轉(zhuǎn)的時(shí)候很快遮晚，不用一個(gè)一個(gè)地應(yīng)用 diff，直接拿出來(lái)就好了拦止。
Git 如何存儲(chǔ)這些對(duì)象县遣？
它們都被存放在 .dircache/objects 文件夾中，通過(guò)內(nèi)容的 sha-1 值來(lái)索引對(duì)用的對(duì)象汹族。在 dircache/objects 下還會(huì)生成 256 個(gè)子目錄（00～ff）萧求，用來(lái)索引前兩位的 sha-1 值。
Current directory cache
current directory cache 就是我們使用的暫存區(qū)顶瞒，它存儲(chǔ)在 .dircache/index 文件中饭聚，可以看作是一個(gè)臨時(shí)的 tree 對(duì)象。當(dāng)執(zhí)行 update-cache 時(shí)搁拙，就會(huì)創(chuàng)建對(duì)應(yīng)文件的 blob 對(duì)象，并將樹(shù)信息加到 .dircache/index 文件中法绵。
如何使用
前面說(shuō)的那些可能沒(méi)有實(shí)際使用會(huì)不太好理解箕速，下面我們可以實(shí)戰(zhàn)一下，使用一些初始版本的 git朋譬。
在這里我們會(huì)利用這些現(xiàn)有的命令
把暫存區(qū)的文件取出來(lái)（相當(dāng)于 git checkout -- file）
提交兩個(gè) commit 并在這兩個(gè) commit 的之間切換
先使用 init-db 創(chuàng)建存儲(chǔ)庫(kù)
$ ./init-db
可以看到創(chuàng)建了 .dircache 文件夾盐茎，和現(xiàn)在的 .git 文件是一樣的。
創(chuàng)建一個(gè)文件寫(xiě)入到暫存區(qū)徙赢，執(zhí)行 update-cache 會(huì)在 .dircache/objects 文件夾中生成一個(gè) blob 對(duì)象并把它加入到 .dircache/index 暫存區(qū)中字柠。
$ echo "123456" > a.txt
$ ./update-cache a.txt
使用 find 查看創(chuàng)建的 blob 對(duì)象
$ find .dircache/objects -type f
.dircache/objects/6e/666502660a7e810b276afd62523c56b34c1671
查看一下
$ cat .dircache/objects/6e/666502660a7e810b276afd62523c56b34c1671
xKOR0g0426156%
由于是用 zlib 壓縮過(guò)的沒(méi)解壓看不出來(lái)啥探越，我們可以使用 cat-file 查看
$ ./cat-file 6e666502660a7e810b276afd62523c56b34c1671
temp_git_file_O5J3ZL: blob
他會(huì)生成一個(gè)臨時(shí)文件，里面是解壓好的文件內(nèi)容窑业，可以看到我們保存到存儲(chǔ)庫(kù)里 a.txt 的內(nèi)容
$ cat temp_git_file_O5J3ZL
123456
現(xiàn)在我們把當(dāng)前的暫存區(qū)的內(nèi)容保存為 tree 對(duì)象到 .dircache/objects 中
$ ./write-tree
433aef473a665a9efe1cf21fbc617fbf833c71b5
寫(xiě)入成功會(huì)打印對(duì)象的 SHA-1 值钦幔，我們可以用 read-tree 查看這個(gè) tree 對(duì)象有什么
$ ./read-tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
100644 a.txt (6e666502660a7e810b276afd62523c56b34c1671)
現(xiàn)在可以提交我們的第一個(gè) commit 了，填寫(xiě)完 commit message 后按 crtrl+d 退出
$ ./commit-tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
Committing initial tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
first commit
4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
可以查看一下 commit 對(duì)象有什么東西
$ ./cat-file 4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
temp_git_file_pNLmni: commit
$ cat temp_git_file_pNLmni
tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
author <zzk@archlinux> Sat Jun 27 14:20:55 2020
committer <zzk@archlinux> Sat Jun 27 14:20:55 2020
first commit
我們完成了第一個(gè)提交常柄，現(xiàn)在我們對(duì) a.txt 做一下修改
$ echo "version2" > a.txt
用 show-diff 可以查看和暫存區(qū)的版本的差異
$ ./show-diff
a.txt: 6e666502660a7e810b276afd62523c56b34c1671
--- - 2020-06-27 14:27:19.975168003 +0800
+++ a.txt 2020-06-27 14:27:18.048129094 +0800
@@ -1 +1 @@
-123456
+version2
如果想取出暫存區(qū)的文件鲤氢，有兩個(gè)方法
- 使用生成的 diff，修改文件
- 用 cat-file 取出暫存區(qū)文件內(nèi)容（第二行有文件的 SHA-1 值）
先用 diff 試試
$ ./show-diff > a.diff
$ patch --reverse a.txt a.diff
patching file a.txt
$ cat a.txt
123456
可以看到文件又回到暫存區(qū)的版本了∥髋耍現(xiàn)在把文件再修改回去卷玉，使用 cat-file 來(lái)試試
$ echo "version2" > a.txt
$ ./show-diff
a.txt: 6e666502660a7e810b276afd62523c56b34c1671
--- - 2020-06-27 14:33:53.795263485 +0800
+++ a.txt 2020-06-27 14:33:50.726893274 +0800
@@ -1 +1 @@
-123456
+version2
$ ./cat-file 6e666502660a7e810b276afd62523c56b34c1671
temp_git_file_d4cTZ7: blob
$ mv temp_git_file_d4cTZ7 a.txt
$ cat a.txt
123456
現(xiàn)在我們準(zhǔn)備第二個(gè) commit ，再執(zhí)行一遍之前的操作
$ echo "verison2" > a.txt
$ ./update-cache a.txt
$ ./write-tree
1c93ac491de01f734fedbe70f31c47ca965c93b6
執(zhí)行 commit-tree 時(shí)候要注意喷市，由于這是第二個(gè)提交相种，需要用 -p 指定一下父提交的 SHA-id 也就是第一個(gè) commit
$ ./commit-tree 1c93ac491de01f734fedbe70f31c47ca965c93b6 -p 4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
second commit
3d4340867cb1dd857987fc2db9b1b4bc14af7051
看一下這個(gè) commit
$ ./cat-file 3d4340867cb1dd857987fc2db9b1b4bc14af7051
temp_git_file_8Cguru: commit
$ cat temp_git_file_8Cguru
tree 1c93ac491de01f734fedbe70f31c47ca965c93b6
parent 4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
author <zzk@archlinux> Sat Jun 27 14:41:43 2020
committer <zzk@archlinux> Sat Jun 27 14:41:43 2020
second commit
現(xiàn)在我們要把 a.txt 的版本切換到上一個(gè) commit，從上面的輸出可以找出 parent 提交的 SHA-id
我們利用這個(gè)父提交的 sha-id 找到對(duì)應(yīng)的 tree object 的 sha-id品姓，再?gòu)?tree object 找到對(duì)應(yīng) a.txt 的 blob object 的 sha-id寝并。最后利用 cat-file 就可以還原出來(lái)原始 a.txt 的內(nèi)容了。
$ ./cat-file 4ae1f8aae02d7178aa4fc52f45f068cd750aa3de
temp_git_file_MssRdY: commit
$ cat temp_git_file_MssRdY
tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
author <zzk@archlinux> Sat Jun 27 14:20:55 2020
committer <zzk@archlinux> Sat Jun 27 14:20:55 2020
first commit
$ ./read-tree 433aef473a665a9efe1cf21fbc617fbf833c71b5
100644 a.txt (6e666502660a7e810b276afd62523c56b34c1671)
$ ./cat-file 6e666502660a7e810b276afd62523c56b34c1671
temp_git_file_2RlDAI: blob
$ mv temp_git_file_2RlDAI a.txt
$ cat a.txt
123456
現(xiàn)在 a.txt 就被還原到了 第一個(gè) commit 時(shí)的狀態(tài)缭黔。
總結(jié)：原始的 git 很難用食茎。經(jīng)過(guò)不斷地打磨才成了今天這樣子好用，現(xiàn)在的 git 很多人只要會(huì) add馏谨、commit别渔、push 就完事了，也不用了解 git 原理惧互。
代碼分析
這里對(duì) git 的部分源碼進(jìn)行分析哎媚，由于前面已經(jīng)寫(xiě)了很多篇幅了，這里就不會(huì)對(duì)太多的代碼進(jìn)行分析喊儡，里面的代碼也是超簡(jiǎn)單拨与，可以說(shuō)是 linus 代碼寫(xiě)得漂亮。你自己看估計(jì)也花不了一會(huì)兒艾猜，而且 Jacob Stopak 對(duì)代碼做超多的注釋?zhuān)娴臎](méi)啥好說(shuō)的买喧。 甚至你可以根據(jù)前面的知識(shí)腦補(bǔ)出大概源碼了>_<。
在這里推薦一個(gè)閱讀源碼的工具 sourcetrail匆赃∮倜看源碼時(shí)很方便。
init-db.c
int main(int argc, char **argv)
{
char *sha1_dir = getenv(DB_ENVIRONMENT), *path;
int len, i, fd;
// 創(chuàng)建 .dircache 的目錄
if (mkdir(".dircache", 0700) < 0) {
perror("unable to create .dircache");
exit(1);
}
/*
* If you want to, you can share the DB area with any number of branches.
* That has advantages: you can save space by sharing all the SHA1 objects.
* On the other hand, it might just make lookup slower and messier. You
* be the judge.
*/
sha1_dir = getenv(DB_ENVIRONMENT);
if (sha1_dir) {
struct stat st;
if (!stat(sha1_dir, &st) < 0 && S_ISDIR(st.st_mode))
return 1;
fprintf(stderr, "DB_ENVIRONMENT set to bad directory %s: ", sha1_dir);
}
/*
* The default case is to have a DB per managed directory.
*/
sha1_dir = DEFAULT_DB_ENVIRONMENT;
fprintf(stderr, "defaulting to private storage area\n");
len = strlen(sha1_dir);
if (mkdir(sha1_dir, 0700) < 0) {
if (errno != EEXIST) {
perror(sha1_dir);
exit(1);
}
}
path = malloc(len + 40);
memcpy(path, sha1_dir, len);
// 創(chuàng)建 .dircache/objects 下的 256 個(gè)子目錄
for (i = 0; i < 256; i++) {
sprintf(path+len, "/%02x", i);
if (mkdir(path, 0700) < 0) {
if (errno != EEXIST) {
perror(path);
exit(1);
}
}
}
return 0;
}
init-db 就只是單純創(chuàng)建好這些目錄而已算柳，和我們前面看到的效果也一樣低淡。
這里介紹 update-cache.c 文件，主要說(shuō)一下怎么創(chuàng)建 blob 和加入 .dircache/index 文件。
首先看 main
int main(int argc, char **argv)
{
int i, newfd, entries;
// 將 .dircache/index 中的內(nèi)容讀入到 active_cache 這個(gè)全局變量中
entries = read_cache();
if (entries < 0) {
perror("cache corrupted");
return -1;
}
// 這里創(chuàng)建 lock 文件是為了不讓多個(gè) update-cahce 同時(shí)運(yùn)行的鎖文件
newfd = open(".dircache/index.lock", O_RDWR | O_CREAT | O_EXCL, 0600);
if (newfd < 0) {
perror("unable to create new cachefile");
return -1;
}
for (i = 1 ; i < argc; i++) {
char *path = argv[i];
// 驗(yàn)證路徑
if (!verify_path(path)) {
fprintf(stderr, "Ignoring path %s\n", argv[i]);
continue;
}
// 把文件添加到 object 數(shù)據(jù)庫(kù)中
if (add_file_to_cache(path)) {
fprintf(stderr, "Unable to add %s to database\n", path);
goto out;
}
}
// 更新 index 文件
if (!write_cache(newfd, active_cache, active_nr) && !rename(".dircache/index.lock", ".dircache/index"))
return 0;
out:
unlink(".dircache/index.lock");
}
通過(guò) main 函數(shù)可以看到生成 blob 應(yīng)該是在 add_file_to_cache 中做的蔗蹋、而更新 index 則是在 write_cache 中做的何荚。后面的可以自己追蹤一下。我說(shuō)一下大概做了啥
add_file_to_cache 中讀取文件然后構(gòu)造一個(gè) blob 對(duì)象進(jìn)行壓縮猪杭，最后計(jì)算 sha-1 值餐塘，把 壓縮好的 blob 對(duì)象存到 sha-1 值對(duì)應(yīng)的位置。（現(xiàn)在看文檔好像是先計(jì)算 sha-1 值再進(jìn)行壓縮了）之后通過(guò)文件名二分查找放入 active_cache 中（也就是 .dircahce/index 暫存區(qū)胁孙，這個(gè)變量是個(gè)全局變量開(kāi)始時(shí)將 .dircache/index 中的內(nèi)容讀入到里面）唠倦，因?yàn)槭菚捍鎱^(qū)是通過(guò)文件名進(jìn)行排序的，所以確認(rèn)一個(gè)文件是否在暫存區(qū)很快涮较，二分只要 logn稠鼻。
write_cache 中就是把 active_cache 再寫(xiě)回 .dircache/index.lock 文件，最后把鎖文件重命名為 .dircache/index 暫存區(qū)文件狂票。
這里是我的博客
