]>
Commit | Line | Data |
---|---|---|
b84f767c DS |
1 | Git commit graph format |
2 | ======================= | |
3 | ||
4 | The Git commit graph stores a list of commit OIDs and some associated | |
5 | metadata, including: | |
6 | ||
7 | - The generation number of the commit. Commits with no parents have | |
8 | generation number 1; commits with parents have generation number | |
9 | one more than the maximum generation number of its parents. We | |
10 | reserve zero as special, and can be used to mark a generation | |
11 | number invalid or as "not computed". | |
12 | ||
13 | - The root tree OID. | |
14 | ||
15 | - The commit date. | |
16 | ||
17 | - The parents of the commit, stored using positional references within | |
18 | the graph file. | |
19 | ||
20 | These positional references are stored as unsigned 32-bit integers | |
06994ae0 | 21 | corresponding to the array position within the list of commit OIDs. Due |
a9aa3c09 DS |
22 | to some special constants we use to track parents, we can store at most |
23 | (1 << 30) + (1 << 29) + (1 << 28) - 1 (around 1.8 billion) commits. | |
b84f767c DS |
24 | |
25 | == Commit graph files have the following format: | |
26 | ||
27 | In order to allow extensions that add extra data to the graph, we organize | |
28 | the body into "chunks" and provide a binary lookup table at the beginning | |
29 | of the body. The header includes certain values, such as number of chunks | |
30 | and hash type. | |
31 | ||
32 | All 4-byte numbers are in network order. | |
33 | ||
34 | HEADER: | |
35 | ||
36 | 4-byte signature: | |
37 | The signature is: {'C', 'G', 'P', 'H'} | |
38 | ||
39 | 1-byte version number: | |
40 | Currently, the only valid version is 1. | |
41 | ||
42 | 1-byte Hash Version (1 = SHA-1) | |
43 | We infer the hash length (H) from this value. | |
44 | ||
45 | 1-byte number (C) of "chunks" | |
46 | ||
47 | 1-byte (reserved for later use) | |
48 | Current clients should ignore this value. | |
49 | ||
50 | CHUNK LOOKUP: | |
51 | ||
52 | (C + 1) * 12 bytes listing the table of contents for the chunks: | |
53 | First 4 bytes describe the chunk id. Value 0 is a terminating label. | |
54 | Other 8 bytes provide the byte-offset in current file for chunk to | |
55 | start. (Chunks are ordered contiguously in the file, so you can infer | |
56 | the length using the next chunk position if necessary.) Each chunk | |
57 | ID appears at most once. | |
58 | ||
59 | The remaining data in the body is described one chunk at a time, and | |
60 | these chunks may be given in any order. Chunks are required unless | |
61 | otherwise specified. | |
62 | ||
63 | CHUNK DATA: | |
64 | ||
65 | OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes) | |
66 | The ith entry, F[i], stores the number of OIDs with first | |
67 | byte at most i. Thus F[255] stores the total | |
68 | number of commits (N). | |
69 | ||
70 | OID Lookup (ID: {'O', 'I', 'D', 'L'}) (N * H bytes) | |
71 | The OIDs for all commits in the graph, sorted in ascending order. | |
72 | ||
a9aa3c09 | 73 | Commit Data (ID: {'C', 'D', 'A', 'T' }) (N * (H + 16) bytes) |
b84f767c DS |
74 | * The first H bytes are for the OID of the root tree. |
75 | * The next 8 bytes are for the positions of the first two parents | |
a9aa3c09 | 76 | of the ith commit. Stores value 0x7000000 if no parent in that |
b84f767c DS |
77 | position. If there are more than two parents, the second value |
78 | has its most-significant bit on and the other bits store an array | |
5af7417b | 79 | position into the Extra Edge List chunk. |
b84f767c DS |
80 | * The next 8 bytes store the generation number of the commit and |
81 | the commit time in seconds since EPOCH. The generation number | |
82 | uses the higher 30 bits of the first 4 bytes, while the commit | |
83 | time uses the 32 bits of the second 4 bytes, along with the lowest | |
84 | 2 bits of the lowest byte, storing the 33rd and 34th bit of the | |
85 | commit time. | |
86 | ||
5af7417b | 87 | Extra Edge List (ID: {'E', 'D', 'G', 'E'}) [Optional] |
b84f767c DS |
88 | This list of 4-byte values store the second through nth parents for |
89 | all octopus merges. The second parent value in the commit data stores | |
90 | an array position within this list along with the most-significant bit | |
91 | on. Starting at that array position, iterate through this list of commit | |
92 | positions for the parents until reaching a value with the most-significant | |
93 | bit on. The other bits correspond to the position of the last parent. | |
94 | ||
95 | TRAILER: | |
96 | ||
97 | H-byte HASH-checksum of all of the above. |