簡體中文 ▾ 主題 ▾ 最新版本 ▾ gitformat-commit-graph 最後更新於 2.47.0

名稱

gitformat-commit-graph - Git commit-graph 格式

概要

$GIT_DIR/objects/info/commit-graph
$GIT_DIR/objects/info/commit-graphs/*

描述

Git commit-graph 儲存了一系列 commit OID 和一些相關元資料,包括

  • commit 的生成號。

  • 根樹 OID。

  • commit 日期。

  • commit 的父提交,使用圖檔案內的位置引用儲存。

  • 如果請求,commit 攜帶的、在 commit 及其第一個父提交之間發生更改的路徑的 Bloom 過濾器。

這些位置引用儲存為無符號 32 位整數,對應於 commit OID 列表中的陣列位置。由於我們使用了一些特殊常量來跟蹤父提交,我們可以儲存最多 (1 << 30) + (1 << 29) + (1 << 28) - 1(約 18 億)個 commit。

Commit-graph 檔案的格式如下

為了允許擴充套件新增額外資料到圖,我們將主體組織成“塊”,並在主體的開頭提供一個二進位制查詢表。頭部包含某些值,例如塊的數量和雜湊型別。

所有多位元組數字均採用網路位元組序。

頭部

4-byte signature:
    The signature is: {'C', 'G', 'P', 'H'}
1-byte version number:
    Currently, the only valid version is 1.
 1-byte Hash Version
     We infer the hash length (H) from this value:
1 => SHA-1
2 => SHA-256
     If the hash type does not match the repository's hash algorithm, the
     commit-graph file should be ignored with a warning presented to the
     user.
1-byte number (C) of "chunks"
1-byte number (B) of base commit-graphs
    We infer the length (H*B) of the Base Graphs chunk
    from this value.

塊查詢

(C + 1) * 12 bytes listing the table of contents for the chunks:
    First 4 bytes describe the chunk id. Value 0 is a terminating label.
    Other 8 bytes provide the byte-offset in current file for chunk to
    start. (Chunks are ordered contiguously in the file, so you can infer
    the length using the next chunk position if necessary.) Each chunk
    ID appears at most once.
The CHUNK LOOKUP matches the table of contents from
the chunk-based file format, see gitformat-chunk[5]
The remaining data in the body is described one chunk at a time, and
these chunks may be given in any order. Chunks are required unless
otherwise specified.

塊資料

OID Fanout (ID: {O, I, D, F}) (256 * 4 位元組)

The ith entry, F[i], stores the number of OIDs with first
byte at most i. Thus F[255] stores the total
number of commits (N).

OID 查詢 (ID: {O, I, D, L}) (N * H 位元組)

The OIDs for all commits in the graph, sorted in ascending order.

Commit 資料 (ID: {C, D, A, T }) (N * (H + 16) 位元組)

  • 前 H 位元組用於儲存根樹的 OID。

  • 接下來的 8 位元組用於儲存第 i 個 commit 的前兩個父提交的位置。當該位置沒有父提交時,儲存值 0x70000000。如果存在兩個以上的父提交,第二個值最高有效位將置為 1,其他位儲存一個數組位置,指向 Extra Edge List 塊。

  • 接下來的 8 位元組儲存 commit 的拓撲級別(生成號 v1)以及自 EPOCH 以來的秒數。生成號使用前 4 位元組的更高 30 位,而 commit 時間使用第二個 4 位元組的 32 位,以及最低位元組的最低 2 位,用於儲存 commit 時間的第 33 位和第 34 位。

Generation Data (ID: {G, D, A, 2 }) (N * 4 位元組) [可選]

  • 此 4 位元組值列表按與 commit 資料塊相同的順序儲存 commit 的已更正提交日期偏移量。

  • 如果已更正的提交日期偏移量無法儲存在 31 位內,則該值最高有效位將置為 1,其他位儲存已更正的提交日期在 Generation Data Overflow 塊中的位置。

  • Generation Data 塊僅在 commit-graph 檔案由相容版本的 Git 寫入時存在,並且在分片 commit-graph 鏈的情況下,最頂層也包含 Generation Data 塊。

Generation Data Overflow (ID: {G, D, O, 2 }) [可選]

  • 此 8 位元組值列表儲存無法在 31 位記憶體儲的已更正 commit 日期偏移量的 commit 的已更正 commit 日期偏移量。

  • Generation Data Overflow 塊僅在 Generation Data 塊存在且至少一個已更正的提交日期偏移量無法在 31 位記憶體儲時存在。

Extra Edge List (ID: {E, D, G, E}) [可選]

This list of 4-byte values store the second through nth parents for
all octopus merges. The second parent value in the commit data stores
an array position within this list along with the most-significant bit
on. Starting at that array position, iterate through this list of commit
positions for the parents until reaching a value with the most-significant
bit on. The other bits correspond to the position of the last parent.

Bloom Filter Index (ID: {B, I, D, X}) (N * 4 位元組) [可選]

  • 第 i 個條目 BIDX[i] 儲存從 commit 0 到 commit i(含)的所有 Bloom 過濾器的位元組數,按字典順序排列。第 i 個 commit 的 Bloom 過濾器從 BIDX[i-1] 到 BIDX[i](加上頭部長度),其中 BIDX[-1] 為 0。

  • 如果不存在 BDAT 塊,則 BIDX 塊將被忽略。

Bloom Filter Data (ID: {B, D, A, T}) [可選]

  • 它以一個包含三個無符號 32 位整數的頭部開始

    • 正在使用的雜湊演算法的版本。我們目前支援值 2,它對應於 murmur3 雜湊的 32 位版本,其實現方式與 https://en.wikipedia.org/wiki/MurmurHash#Algorithm 中描述的完全相同,並且使用種子值 0x293ae76f 和 0x7e646e2 的雙雜湊技術,如 https://doi.org/10.1007/978-3-540-30494-4_26 "Bloom Filters in Probabilistic Verification" 中所述。版本 1 的 Bloom 過濾器存在一個 bug,當 char 為 signed 且倉庫的路徑名包含大於等於 0x80 的字元時會出現該 bug;Git 支援讀取和寫入它們,但此功能將在 Git 的未來版本中被移除。

    • 路徑被雜湊的次數,因此累積確定檔案是否存在於 commit 中的位數。

    • 每個條目的最小位數 b。如果過濾器包含 n 個條目,則過濾器的大小是包含 n*b 位的最小 64 位字數。

  • 塊的其餘部分是按字典順序排列的所有計算出的 Bloom 過濾器的串聯。

  • 注意:沒有更改或更改超過 512 個的 commit 具有長度為一的 Bloom 過濾器,其中所有位都被設定為零或一,分別表示。

  • BDAT 塊的存在僅當 BIDX 塊存在時才存在。

Base Graphs List (ID: {B, A, S, E}) [可選]

This list of H-byte hashes describe a set of B commit-graph files that
form a commit-graph chain. The graph position for the ith commit in this
file's OID Lookup chunk is equal to i plus the number of commits in all
base graphs.  If B is non-zero, this chunk must exist.

尾部

H-byte HASH-checksum of all of the above.

歷史說明

Generation Data (GDA2) 和 Generation Data Overflow (GDO2) 塊在其塊 ID 中包含數字 *2*,因為 Git 的早期版本可能在 ID 為“GDAT”和“GDOV”的塊中寫入了可能錯誤的 GDA2 資料。透過更改 ID,較新版本的 Git 將會靜默忽略這些舊塊,並寫入新資訊,而不信任不正確的資料。

GIT

Git[1] 套件的一部分