| blob | 1ef1c08d52c2f9867dc3ccf68a7883d7b8aa1d81 |
1 '\" t
2 .\" Title: gitformat-commit-graph
3 .\" Author: [FIXME: author] [see http://www.docbook.org/tdg5/en/html/author]
4 .\" Generator: DocBook XSL Stylesheets vsnapshot <http://docbook.sf.net/>
5 .\" Date: 2023-09-13
6 .\" Manual: Git Manual
7 .\" Source: Git 2.42.0.176.gd6c51973e4
8 .\" Language: English
9 .\"
10 .TH "GITFORMAT\-COMMIT\-GRAPH" "5" "2023\-09\-13" "Git 2\&.42\&.0\&.176\&.gd6c519" "Git Manual"
11 .\" -----------------------------------------------------------------
12 .\" * Define some portability stuff
13 .\" -----------------------------------------------------------------
14 .\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
15 .\" http://bugs.debian.org/507673
16 .\" http://lists.gnu.org/archive/html/groff/2009-02/msg00013.html
17 .\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
18 .ie \n(.g .ds Aq \(aq
19 .el .ds Aq '
20 .\" -----------------------------------------------------------------
21 .\" * set default formatting
22 .\" -----------------------------------------------------------------
23 .\" disable hyphenation
24 .nh
25 .\" disable justification (adjust text to left margin only)
26 .ad l
27 .\" -----------------------------------------------------------------
28 .\" * MAIN CONTENT STARTS HERE *
29 .\" -----------------------------------------------------------------
30 .SH "NAME"
31 gitformat-commit-graph \- Git commit\-graph format
32 .SH "SYNOPSIS"
33 .sp
34 .nf
35 $GIT_DIR/objects/info/commit\-graph
36 $GIT_DIR/objects/info/commit\-graphs/*
37 .fi
38 .sp
39 .SH "DESCRIPTION"
40 .sp
41 The Git commit\-graph stores a list of commit OIDs and some associated metadata, including:
42 .sp
43 .RS 4
44 .ie n \{\
45 \h'-04'\(bu\h'+03'\c
46 .\}
47 .el \{\
48 .sp -1
49 .IP \(bu 2.3
50 .\}
51 The generation number of the commit\&.
52 .RE
53 .sp
54 .RS 4
55 .ie n \{\
56 \h'-04'\(bu\h'+03'\c
57 .\}
58 .el \{\
59 .sp -1
60 .IP \(bu 2.3
61 .\}
62 The root tree OID\&.
63 .RE
64 .sp
65 .RS 4
66 .ie n \{\
67 \h'-04'\(bu\h'+03'\c
68 .\}
69 .el \{\
70 .sp -1
71 .IP \(bu 2.3
72 .\}
73 The commit date\&.
74 .RE
75 .sp
76 .RS 4
77 .ie n \{\
78 \h'-04'\(bu\h'+03'\c
79 .\}
80 .el \{\
81 .sp -1
82 .IP \(bu 2.3
83 .\}
84 The parents of the commit, stored using positional references within the graph file\&.
85 .RE
86 .sp
87 .RS 4
88 .ie n \{\
89 \h'-04'\(bu\h'+03'\c
90 .\}
91 .el \{\
92 .sp -1
93 .IP \(bu 2.3
94 .\}
95 The Bloom filter of the commit carrying the paths that were changed between the commit and its first parent, if requested\&.
96 .RE
97 .sp
98 These positional references are stored as unsigned 32\-bit integers corresponding to the array position within the list of commit OIDs\&. Due to some special constants we use to track parents, we can store at most (1 << 30) + (1 << 29) + (1 << 28) \- 1 (around 1\&.8 billion) commits\&.
99 .SH "COMMIT\-GRAPH FILES HAVE THE FOLLOWING FORMAT:"
100 .sp
101 In order to allow extensions that add extra data to the graph, we organize the body into "chunks" and provide a binary lookup table at the beginning of the body\&. The header includes certain values, such as number of chunks and hash type\&.
102 .sp
103 All multi\-byte numbers are in network byte order\&.
104 .SS "HEADER:"
105 .sp
106 .if n \{\
107 .RS 4
108 .\}
109 .nf
110 4\-byte signature:
111 The signature is: {\*(AqC\*(Aq, \*(AqG\*(Aq, \*(AqP\*(Aq, \*(AqH\*(Aq}
112 .fi
113 .if n \{\
114 .RE
115 .\}
116 .sp
117 .if n \{\
118 .RS 4
119 .\}
120 .nf
121 1\-byte version number:
122 Currently, the only valid version is 1\&.
123 .fi
124 .if n \{\
125 .RE
126 .\}
127 .sp
128 .if n \{\
129 .RS 4
130 .\}
131 .nf
132 1\-byte Hash Version
133 We infer the hash length (H) from this value:
134 1 => SHA\-1
135 2 => SHA\-256
136 If the hash type does not match the repository\*(Aqs hash algorithm, the
137 commit\-graph file should be ignored with a warning presented to the
138 user\&.
139 .fi
140 .if n \{\
141 .RE
142 .\}
143 .sp
144 .if n \{\
145 .RS 4
146 .\}
147 .nf
148 1\-byte number (C) of "chunks"
149 .fi
150 .if n \{\
151 .RE
152 .\}
153 .sp
154 .if n \{\
155 .RS 4
156 .\}
157 .nf
158 1\-byte number (B) of base commit\-graphs
159 We infer the length (H*B) of the Base Graphs chunk
160 from this value\&.
161 .fi
162 .if n \{\
163 .RE
164 .\}
165 .SS "CHUNK LOOKUP:"
166 .sp
167 .if n \{\
168 .RS 4
169 .\}
170 .nf
171 (C + 1) * 12 bytes listing the table of contents for the chunks:
172 First 4 bytes describe the chunk id\&. Value 0 is a terminating label\&.
173 Other 8 bytes provide the byte\-offset in current file for chunk to
174 start\&. (Chunks are ordered contiguously in the file, so you can infer
175 the length using the next chunk position if necessary\&.) Each chunk
176 ID appears at most once\&.
177 .fi
178 .if n \{\
179 .RE
180 .\}
181 .sp
182 .if n \{\
183 .RS 4
184 .\}
185 .nf
186 The CHUNK LOOKUP matches the table of contents from
187 the chunk\-based file format, see linkgit:gitformat\-chunk[5]
188 .fi
189 .if n \{\
190 .RE
191 .\}
192 .sp
193 .if n \{\
194 .RS 4
195 .\}
196 .nf
197 The remaining data in the body is described one chunk at a time, and
198 these chunks may be given in any order\&. Chunks are required unless
199 otherwise specified\&.
200 .fi
201 .if n \{\
202 .RE
203 .\}
204 .SS "CHUNK DATA:"
205 .sp
206 .it 1 an-trap
207 .nr an-no-space-flag 1
208 .nr an-break-flag 1
209 .br
210 .ps +1
211 \fBOID Fanout (ID: {O, I, D, F}) (256 * 4 bytes)\fR
212 .RS 4
213 .sp
214 .if n \{\
215 .RS 4
216 .\}
217 .nf
218 The ith entry, F[i], stores the number of OIDs with first
219 byte at most i\&. Thus F[255] stores the total
220 number of commits (N)\&.
221 .fi
222 .if n \{\
223 .RE
224 .\}
225 .RE
226 .sp
227 .it 1 an-trap
228 .nr an-no-space-flag 1
229 .nr an-break-flag 1
230 .br
231 .ps +1
232 \fBOID Lookup (ID: {O, I, D, L}) (N * H bytes)\fR
233 .RS 4
234 .sp
235 .if n \{\
236 .RS 4
237 .\}
238 .nf
239 The OIDs for all commits in the graph, sorted in ascending order\&.
240 .fi
241 .if n \{\
242 .RE
243 .\}
244 .RE
245 .sp
246 .it 1 an-trap
247 .nr an-no-space-flag 1
248 .nr an-break-flag 1
249 .br
250 .ps +1
251 \fBCommit Data (ID: {C, D, A, T }) (N * (H + 16) bytes)\fR
252 .RS 4
253 .sp
254 .RS 4
255 .ie n \{\
256 \h'-04'\(bu\h'+03'\c
257 .\}
258 .el \{\
259 .sp -1
260 .IP \(bu 2.3
261 .\}
262 The first H bytes are for the OID of the root tree\&.
263 .RE
264 .sp
265 .RS 4
266 .ie n \{\
267 \h'-04'\(bu\h'+03'\c
268 .\}
269 .el \{\
270 .sp -1
271 .IP \(bu 2.3
272 .\}
273 The next 8 bytes are for the positions of the first two parents of the ith commit\&. Stores value 0x70000000 if no parent in that position\&. If there are more than two parents, the second value has its most\-significant bit on and the other bits store an array position into the Extra Edge List chunk\&.
274 .RE
275 .sp
276 .RS 4
277 .ie n \{\
278 \h'-04'\(bu\h'+03'\c
279 .\}
280 .el \{\
281 .sp -1
282 .IP \(bu 2.3
283 .\}
284 The next 8 bytes store the topological level (generation number v1) of the commit and the commit time in seconds since EPOCH\&. The generation number uses the higher 30 bits of the first 4 bytes, while the commit time uses the 32 bits of the second 4 bytes, along with the lowest 2 bits of the lowest byte, storing the 33rd and 34th bit of the commit time\&.
285 .RE
286 .RE
287 .sp
288 .it 1 an-trap
289 .nr an-no-space-flag 1
290 .nr an-break-flag 1
291 .br
292 .ps +1
293 \fBGeneration Data (ID: {G, D, A, 2 }) (N * 4 bytes) [Optional]\fR
294 .RS 4
295 .sp
296 .RS 4
297 .ie n \{\
298 \h'-04'\(bu\h'+03'\c
299 .\}
300 .el \{\
301 .sp -1
302 .IP \(bu 2.3
303 .\}
304 This list of 4\-byte values store corrected commit date offsets for the commits, arranged in the same order as commit data chunk\&.
305 .RE
306 .sp
307 .RS 4
308 .ie n \{\
309 \h'-04'\(bu\h'+03'\c
310 .\}
311 .el \{\
312 .sp -1
313 .IP \(bu 2.3
314 .\}
315 If the corrected commit date offset cannot be stored within 31 bits, the value has its most\-significant bit on and the other bits store the position of corrected commit date into the Generation Data Overflow chunk\&.
316 .RE
317 .sp
318 .RS 4
319 .ie n \{\
320 \h'-04'\(bu\h'+03'\c
321 .\}
322 .el \{\
323 .sp -1
324 .IP \(bu 2.3
325 .\}
326 Generation Data chunk is present only when commit\-graph file is written by compatible versions of Git and in case of split commit\-graph chains, the topmost layer also has Generation Data chunk\&.
327 .RE
328 .RE
329 .sp
330 .it 1 an-trap
331 .nr an-no-space-flag 1
332 .nr an-break-flag 1
333 .br
334 .ps +1
335 \fBGeneration Data Overflow (ID: {G, D, O, 2 }) [Optional]\fR
336 .RS 4
337 .sp
338 .RS 4
339 .ie n \{\
340 \h'-04'\(bu\h'+03'\c
341 .\}
342 .el \{\
343 .sp -1
344 .IP \(bu 2.3
345 .\}
346 This list of 8\-byte values stores the corrected commit date offsets for commits with corrected commit date offsets that cannot be stored within 31 bits\&.
347 .RE
348 .sp
349 .RS 4
350 .ie n \{\
351 \h'-04'\(bu\h'+03'\c
352 .\}
353 .el \{\
354 .sp -1
355 .IP \(bu 2.3
356 .\}
357 Generation Data Overflow chunk is present only when Generation Data chunk is present and atleast one corrected commit date offset cannot be stored within 31 bits\&.
358 .RE
359 .RE
360 .sp
361 .it 1 an-trap
362 .nr an-no-space-flag 1
363 .nr an-break-flag 1
364 .br
365 .ps +1
366 \fBExtra Edge List (ID: {E, D, G, E}) [Optional]\fR
367 .RS 4
368 .sp
369 .if n \{\
370 .RS 4
371 .\}
372 .nf
373 This list of 4\-byte values store the second through nth parents for
374 all octopus merges\&. The second parent value in the commit data stores
375 an array position within this list along with the most\-significant bit
376 on\&. Starting at that array position, iterate through this list of commit
377 positions for the parents until reaching a value with the most\-significant
378 bit on\&. The other bits correspond to the position of the last parent\&.
379 .fi
380 .if n \{\
381 .RE
382 .\}
383 .RE
384 .sp
385 .it 1 an-trap
386 .nr an-no-space-flag 1
387 .nr an-break-flag 1
388 .br
389 .ps +1
390 \fBBloom Filter Index (ID: {B, I, D, X}) (N * 4 bytes) [Optional]\fR
391 .RS 4
392 .sp
393 .RS 4
394 .ie n \{\
395 \h'-04'\(bu\h'+03'\c
396 .\}
397 .el \{\
398 .sp -1
399 .IP \(bu 2.3
400 .\}
401 The ith entry, BIDX[i], stores the number of bytes in all Bloom filters from commit 0 to commit i (inclusive) in lexicographic order\&. The Bloom filter for the i\-th commit spans from BIDX[i\-1] to BIDX[i] (plus header length), where BIDX[\-1] is 0\&.
402 .RE
403 .sp
404 .RS 4
405 .ie n \{\
406 \h'-04'\(bu\h'+03'\c
407 .\}
408 .el \{\
409 .sp -1
410 .IP \(bu 2.3
411 .\}
412 The BIDX chunk is ignored if the BDAT chunk is not present\&.
413 .RE
414 .RE
415 .sp
416 .it 1 an-trap
417 .nr an-no-space-flag 1
418 .nr an-break-flag 1
419 .br
420 .ps +1
421 \fBBloom Filter Data (ID: {B, D, A, T}) [Optional]\fR
422 .RS 4
423 .sp
424 .RS 4
425 .ie n \{\
426 \h'-04'\(bu\h'+03'\c
427 .\}
428 .el \{\
429 .sp -1
430 .IP \(bu 2.3
431 .\}
432 It starts with header consisting of three unsigned 32\-bit integers:
433 .sp
434 .RS 4
435 .ie n \{\
436 \h'-04'\(bu\h'+03'\c
437 .\}
438 .el \{\
439 .sp -1
440 .IP \(bu 2.3
441 .\}
442 Version of the hash algorithm being used\&. We currently only support value 1 which corresponds to the 32\-bit version of the murmur3 hash implemented exactly as described in
443 \m[blue]\fBhttps://en\&.wikipedia\&.org/wiki/MurmurHash#Algorithm\fR\m[]
444 and the double hashing technique using seed values 0x293ae76f and 0x7e646e2 as described in
445 \m[blue]\fBhttps://doi\&.org/10\&.1007/978\-3\-540\-30494\-4_26\fR\m[]
446 "Bloom Filters in Probabilistic Verification"
447 .RE
448 .sp
449 .RS 4
450 .ie n \{\
451 \h'-04'\(bu\h'+03'\c
452 .\}
453 .el \{\
454 .sp -1
455 .IP \(bu 2.3
456 .\}
457 The number of times a path is hashed and hence the number of bit positions that cumulatively determine whether a file is present in the commit\&.
458 .RE
459 .sp
460 .RS 4
461 .ie n \{\
462 \h'-04'\(bu\h'+03'\c
463 .\}
464 .el \{\
465 .sp -1
466 .IP \(bu 2.3
467 .\}
468 The minimum number of bits
469 \fIb\fR
470 per entry in the Bloom filter\&. If the filter contains
471 \fIn\fR
472 entries, then the filter size is the minimum number of 64\-bit words that contain n*b bits\&.
473 .RE
474 .RE
475 .sp
476 .RS 4
477 .ie n \{\
478 \h'-04'\(bu\h'+03'\c
479 .\}
480 .el \{\
481 .sp -1
482 .IP \(bu 2.3
483 .\}
484 The rest of the chunk is the concatenation of all the computed Bloom filters for the commits in lexicographic order\&.
485 .RE
486 .sp
487 .RS 4
488 .ie n \{\
489 \h'-04'\(bu\h'+03'\c
490 .\}
491 .el \{\
492 .sp -1
493 .IP \(bu 2.3
494 .\}
495 Note: Commits with no changes or more than 512 changes have Bloom filters of length one, with either all bits set to zero or one respectively\&.
496 .RE
497 .sp
498 .RS 4
499 .ie n \{\
500 \h'-04'\(bu\h'+03'\c
501 .\}
502 .el \{\
503 .sp -1
504 .IP \(bu 2.3
505 .\}
506 The BDAT chunk is present if and only if BIDX is present\&.
507 .RE
508 .RE
509 .sp
510 .it 1 an-trap
511 .nr an-no-space-flag 1
512 .nr an-break-flag 1
513 .br
514 .ps +1
515 \fBBase Graphs List (ID: {B, A, S, E}) [Optional]\fR
516 .RS 4
517 .sp
518 .if n \{\
519 .RS 4
520 .\}
521 .nf
522 This list of H\-byte hashes describe a set of B commit\-graph files that
523 form a commit\-graph chain\&. The graph position for the ith commit in this
524 file\*(Aqs OID Lookup chunk is equal to i plus the number of commits in all
525 base graphs\&. If B is non\-zero, this chunk must exist\&.
526 .fi
527 .if n \{\
528 .RE
529 .\}
530 .RE
531 .SS "TRAILER:"
532 .sp
533 .if n \{\
534 .RS 4
535 .\}
536 .nf
537 H\-byte HASH\-checksum of all of the above\&.
538 .fi
539 .if n \{\
540 .RE
541 .\}
542 .SH "HISTORICAL NOTES:"
543 .sp
544 The Generation Data (GDA2) and Generation Data Overflow (GDO2) chunks have the number \fI2\fR in their chunk IDs because a previous version of Git wrote possibly erroneous data in these chunks with the IDs "GDAT" and "GDOV"\&. By changing the IDs, newer versions of Git will silently ignore those older chunks and write the new information without trusting the incorrect data\&.
545 .SH "GIT"
546 .sp
547 Part of the \fBgit\fR(1) suite