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