]>
Commit | Line | Data |
---|---|---|
977c47b4 ÆAB |
1 | gitformat-pack(5) |
2 | ================= | |
3 | ||
4 | NAME | |
5 | ---- | |
6 | gitformat-pack - Git pack format | |
7 | ||
8 | ||
9 | SYNOPSIS | |
10 | -------- | |
11 | [verse] | |
12 | $GIT_DIR/objects/pack/pack-*.{pack,idx} | |
13 | $GIT_DIR/objects/pack/pack-*.rev | |
6b6029dd | 14 | $GIT_DIR/objects/pack/pack-*.mtimes |
977c47b4 ÆAB |
15 | $GIT_DIR/objects/pack/multi-pack-index |
16 | ||
17 | DESCRIPTION | |
18 | ----------- | |
19 | ||
384f7d17 | 20 | The Git pack format is how Git stores most of its primary repository |
4d542687 | 21 | data. Over the lifetime of a repository, loose objects (if any) and |
977c47b4 ÆAB |
22 | smaller packs are consolidated into larger pack(s). See |
23 | linkgit:git-gc[1] and linkgit:git-pack-objects[1]. | |
24 | ||
25 | The pack format is also used over-the-wire, see | |
26 | e.g. linkgit:gitprotocol-v2[5], as well as being a part of | |
27 | other container formats in the case of linkgit:gitformat-bundle[5]. | |
9760662f | 28 | |
17420eaf | 29 | == Checksums and object IDs |
30 | ||
31 | In a repository using the traditional SHA-1, pack checksums, index checksums, | |
32 | and object IDs (object names) mentioned below are all computed using SHA-1. | |
33 | Similarly, in SHA-256 repositories, these values are computed using SHA-256. | |
34 | ||
5316c8e9 | 35 | == pack-*.pack files have the following format: |
9760662f | 36 | |
71362bd5 | 37 | - A header appears at the beginning and consists of the following: |
9760662f | 38 | |
1361fa3e SP |
39 | 4-byte signature: |
40 | The signature is: {'P', 'A', 'C', 'K'} | |
41 | ||
42 | 4-byte version number (network byte order): | |
48a8c26c | 43 | Git currently accepts version number 2 or 3 but |
1361fa3e SP |
44 | generates version 2 only. |
45 | ||
9760662f JH |
46 | 4-byte number of objects contained in the pack (network byte order) |
47 | ||
48 | Observation: we cannot have more than 4G versions ;-) and | |
49 | more than 4G objects in a pack. | |
50 | ||
0a4f051f | 51 | - The header is followed by a number of object entries, each of |
9760662f JH |
52 | which looks like this: |
53 | ||
54 | (undeltified representation) | |
979ea585 | 55 | n-byte type and length (3-bit type, (n-1)*7+4-bit length) |
9760662f JH |
56 | compressed data |
57 | ||
58 | (deltified representation) | |
979ea585 | 59 | n-byte type and length (3-bit type, (n-1)*7+4-bit length) |
17420eaf | 60 | base object name if OBJ_REF_DELTA or a negative relative |
06cb843f SS |
61 | offset from the delta object's position in the pack if this |
62 | is an OBJ_OFS_DELTA object | |
9760662f JH |
63 | compressed delta data |
64 | ||
0a4f051f | 65 | Observation: the length of each object is encoded in a variable |
9760662f JH |
66 | length format and is not constrained to 32-bit or anything. |
67 | ||
17420eaf | 68 | - The trailer records a pack checksum of all of the above. |
9760662f | 69 | |
011b6486 NTND |
70 | === Object types |
71 | ||
72 | Valid object types are: | |
73 | ||
74 | - OBJ_COMMIT (1) | |
75 | - OBJ_TREE (2) | |
76 | - OBJ_BLOB (3) | |
77 | - OBJ_TAG (4) | |
78 | - OBJ_OFS_DELTA (6) | |
79 | - OBJ_REF_DELTA (7) | |
80 | ||
81 | Type 5 is reserved for future expansion. Type 0 is invalid. | |
82 | ||
7b77f5a1 MÅ |
83 | === Size encoding |
84 | ||
85 | This document uses the following "size encoding" of non-negative | |
86 | integers: From each byte, the seven least significant bits are | |
87 | used to form the resulting integer. As long as the most significant | |
88 | bit is 1, this process continues; the byte with MSB 0 provides the | |
89 | last seven bits. The seven-bit chunks are concatenated. Later | |
90 | values are more significant. | |
91 | ||
92 | This size encoding should not be confused with the "offset encoding", | |
93 | which is also used in this document. | |
94 | ||
011b6486 NTND |
95 | === Deltified representation |
96 | ||
97 | Conceptually there are only four object types: commit, tree, tag and | |
98 | blob. However to save space, an object could be stored as a "delta" of | |
99 | another "base" object. These representations are assigned new types | |
100 | ofs-delta and ref-delta, which is only valid in a pack file. | |
101 | ||
102 | Both ofs-delta and ref-delta store the "delta" to be applied to | |
103 | another object (called 'base object') to reconstruct the object. The | |
17420eaf | 104 | difference between them is, ref-delta directly encodes base object |
105 | name. If the base object is in the same pack, ofs-delta encodes | |
011b6486 NTND |
106 | the offset of the base object in the pack instead. |
107 | ||
108 | The base object could also be deltified if it's in the same pack. | |
109 | Ref-delta can also refer to an object outside the pack (i.e. the | |
110 | so-called "thin pack"). When stored on disk however, the pack should | |
111 | be self contained to avoid cyclic dependency. | |
112 | ||
7b77f5a1 MÅ |
113 | The delta data starts with the size of the base object and the |
114 | size of the object to be reconstructed. These sizes are | |
115 | encoded using the size encoding from above. The remainder of | |
116 | the delta data is a sequence of instructions to reconstruct the object | |
011b6486 NTND |
117 | from the base object. If the base object is deltified, it must be |
118 | converted to canonical form first. Each instruction appends more and | |
119 | more data to the target object until it's complete. There are two | |
5676b04a | 120 | supported instructions so far: one for copying a byte range from the |
011b6486 NTND |
121 | source object and one for inserting new data embedded in the |
122 | instruction itself. | |
123 | ||
124 | Each instruction has variable length. Instruction type is determined | |
125 | by the seventh bit of the first octet. The following diagrams follow | |
126 | the convention in RFC 1951 (Deflate compressed data format). | |
127 | ||
128 | ==== Instruction to copy from base object | |
129 | ||
130 | +----------+---------+---------+---------+---------+-------+-------+-------+ | |
131 | | 1xxxxxxx | offset1 | offset2 | offset3 | offset4 | size1 | size2 | size3 | | |
132 | +----------+---------+---------+---------+---------+-------+-------+-------+ | |
133 | ||
134 | This is the instruction format to copy a byte range from the source | |
135 | object. It encodes the offset to copy from and the number of bytes to | |
136 | copy. Offset and size are in little-endian order. | |
137 | ||
138 | All offset and size bytes are optional. This is to reduce the | |
139 | instruction size when encoding small offsets or sizes. The first seven | |
5676b04a | 140 | bits in the first octet determine which of the next seven octets is |
011b6486 NTND |
141 | present. If bit zero is set, offset1 is present. If bit one is set |
142 | offset2 is present and so on. | |
143 | ||
144 | Note that a more compact instruction does not change offset and size | |
145 | encoding. For example, if only offset2 is omitted like below, offset3 | |
146 | still contains bits 16-23. It does not become offset2 and contains | |
147 | bits 8-15 even if it's right next to offset1. | |
148 | ||
149 | +----------+---------+---------+ | |
150 | | 10000101 | offset1 | offset3 | | |
151 | +----------+---------+---------+ | |
152 | ||
153 | In its most compact form, this instruction only takes up one byte | |
154 | (0x80) with both offset and size omitted, which will have default | |
155 | values zero. There is another exception: size zero is automatically | |
156 | converted to 0x10000. | |
157 | ||
158 | ==== Instruction to add new data | |
159 | ||
160 | +----------+============+ | |
161 | | 0xxxxxxx | data | | |
162 | +----------+============+ | |
163 | ||
0a4f051f | 164 | This is the instruction to construct the target object without the base |
011b6486 | 165 | object. The following data is appended to the target object. The first |
5676b04a | 166 | seven bits of the first octet determine the size of data in |
011b6486 NTND |
167 | bytes. The size must be non-zero. |
168 | ||
169 | ==== Reserved instruction | |
170 | ||
171 | +----------+============ | |
172 | | 00000000 | | |
173 | +----------+============ | |
174 | ||
175 | This is the instruction reserved for future expansion. | |
176 | ||
5316c8e9 | 177 | == Original (version 1) pack-*.idx files have the following format: |
9760662f JH |
178 | |
179 | - The header consists of 256 4-byte network byte order | |
180 | integers. N-th entry of this table records the number of | |
181 | objects in the corresponding pack, the first byte of whose | |
71362bd5 | 182 | object name is less than or equal to N. This is called the |
9760662f JH |
183 | 'first-level fan-out' table. |
184 | ||
1361fa3e | 185 | - The header is followed by sorted 24-byte entries, one entry |
9760662f JH |
186 | per object in the pack. Each entry is: |
187 | ||
188 | 4-byte network byte order integer, recording where the | |
189 | object is stored in the packfile as the offset from the | |
190 | beginning. | |
191 | ||
17420eaf | 192 | one object name of the appropriate size. |
9760662f | 193 | |
9760662f JH |
194 | - The file is concluded with a trailer: |
195 | ||
17420eaf | 196 | A copy of the pack checksum at the end of the corresponding |
197 | packfile. | |
9760662f | 198 | |
17420eaf | 199 | Index checksum of all of the above. |
9760662f JH |
200 | |
201 | Pack Idx file: | |
202 | ||
71362bd5 | 203 | -- +--------------------------------+ |
204 | fanout | fanout[0] = 2 (for example) |-. | |
205 | table +--------------------------------+ | | |
9760662f JH |
206 | | fanout[1] | | |
207 | +--------------------------------+ | | |
208 | | fanout[2] | | | |
209 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | | |
71362bd5 | 210 | | fanout[255] = total objects |---. |
211 | -- +--------------------------------+ | | | |
212 | main | offset | | | | |
213 | index | object name 00XXXXXXXXXXXXXXXX | | | | |
214 | table +--------------------------------+ | | | |
215 | | offset | | | | |
216 | | object name 00XXXXXXXXXXXXXXXX | | | | |
217 | +--------------------------------+<+ | | |
218 | .-| offset | | | |
219 | | | object name 01XXXXXXXXXXXXXXXX | | | |
220 | | +--------------------------------+ | | |
221 | | | offset | | | |
222 | | | object name 01XXXXXXXXXXXXXXXX | | | |
223 | | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ | | |
224 | | | offset | | | |
225 | | | object name FFXXXXXXXXXXXXXXXX | | | |
226 | --| +--------------------------------+<--+ | |
9760662f JH |
227 | trailer | | packfile checksum | |
228 | | +--------------------------------+ | |
229 | | | idxfile checksum | | |
230 | | +--------------------------------+ | |
a6080a0a | 231 | .-------. |
9760662f JH |
232 | | |
233 | Pack file entry: <+ | |
234 | ||
235 | packed object header: | |
979ea585 PE |
236 | 1-byte size extension bit (MSB) |
237 | type (next 3 bit) | |
a6080a0a | 238 | size0 (lower 4-bit) |
9760662f JH |
239 | n-byte sizeN (as long as MSB is set, each 7-bit) |
240 | size0..sizeN form 4+7+7+..+7 bit integer, size0 | |
979ea585 PE |
241 | is the least significant part, and sizeN is the |
242 | most significant part. | |
9760662f JH |
243 | packed object data: |
244 | If it is not DELTA, then deflated bytes (the size above | |
245 | is the size before compression). | |
9de328fe | 246 | If it is REF_DELTA, then |
17420eaf | 247 | base object name (the size above is the |
a6080a0a | 248 | size of the delta data that follows). |
9760662f | 249 | delta data, deflated. |
9de328fe PE |
250 | If it is OFS_DELTA, then |
251 | n-byte offset (see below) interpreted as a negative | |
252 | offset from the type-byte of the header of the | |
253 | ofs-delta entry (the size above is the size of | |
254 | the delta data that follows). | |
255 | delta data, deflated. | |
256 | ||
257 | offset encoding: | |
258 | n bytes with MSB set in all but the last one. | |
259 | The offset is then the number constructed by | |
260 | concatenating the lower 7 bit of each byte, and | |
261 | for n >= 2 adding 2^7 + 2^14 + ... + 2^(7*(n-1)) | |
262 | to the result. | |
263 | ||
71362bd5 | 264 | |
265 | ||
5316c8e9 TA |
266 | == Version 2 pack-*.idx files support packs larger than 4 GiB, and |
267 | have some other reorganizations. They have the format: | |
71362bd5 | 268 | |
269 | - A 4-byte magic number '\377tOc' which is an unreasonable | |
270 | fanout[0] value. | |
271 | ||
272 | - A 4-byte version number (= 2) | |
273 | ||
274 | - A 256-entry fan-out table just like v1. | |
275 | ||
17420eaf | 276 | - A table of sorted object names. These are packed together |
277 | without offset values to reduce the cache footprint of the | |
278 | binary search for a specific object name. | |
71362bd5 | 279 | |
280 | - A table of 4-byte CRC32 values of the packed object data. | |
281 | This is new in v2 so compressed data can be copied directly | |
f1cdcc70 | 282 | from pack to pack during repacking without undetected |
71362bd5 | 283 | data corruption. |
284 | ||
285 | - A table of 4-byte offset values (in network byte order). | |
286 | These are usually 31-bit pack file offsets, but large | |
287 | offsets are encoded as an index into the next table with | |
288 | the msbit set. | |
289 | ||
290 | - A table of 8-byte offset entries (empty for pack files less | |
291 | than 2 GiB). Pack files are organized with heavily used | |
292 | objects toward the front, so most object references should | |
293 | not need to refer to this table. | |
294 | ||
295 | - The same trailer as a v1 pack file: | |
296 | ||
0a4f051f | 297 | A copy of the pack checksum at the end of the |
71362bd5 | 298 | corresponding packfile. |
299 | ||
17420eaf | 300 | Index checksum of all of the above. |
e0d1bcf8 | 301 | |
2f4ba2a8 TB |
302 | == pack-*.rev files have the format: |
303 | ||
304 | - A 4-byte magic number '0x52494458' ('RIDX'). | |
305 | ||
306 | - A 4-byte version identifier (= 1). | |
307 | ||
308 | - A 4-byte hash function identifier (= 1 for SHA-1, 2 for SHA-256). | |
309 | ||
310 | - A table of index positions (one per packed object, num_objects in | |
311 | total, each a 4-byte unsigned integer in network order), sorted by | |
312 | their corresponding offsets in the packfile. | |
313 | ||
314 | - A trailer, containing a: | |
315 | ||
316 | checksum of the corresponding packfile, and | |
317 | ||
318 | a checksum of all of the above. | |
319 | ||
320 | All 4-byte numbers are in network order. | |
321 | ||
94cd775a TB |
322 | == pack-*.mtimes files have the format: |
323 | ||
324 | All 4-byte numbers are in network byte order. | |
325 | ||
326 | - A 4-byte magic number '0x4d544d45' ('MTME'). | |
327 | ||
328 | - A 4-byte version identifier (= 1). | |
329 | ||
330 | - A 4-byte hash function identifier (= 1 for SHA-1, 2 for SHA-256). | |
331 | ||
332 | - A table of 4-byte unsigned integers. The ith value is the | |
333 | modification time (mtime) of the ith object in the corresponding | |
334 | pack by lexicographic (index) order. The mtimes count standard | |
335 | epoch seconds. | |
336 | ||
337 | - A trailer, containing a checksum of the corresponding packfile, | |
338 | and a checksum of all of the above (each having length according | |
339 | to the specified hash function). | |
340 | ||
e0d1bcf8 DS |
341 | == multi-pack-index (MIDX) files have the following format: |
342 | ||
343 | The multi-pack-index files refer to multiple pack-files and loose objects. | |
344 | ||
345 | In order to allow extensions that add extra data to the MIDX, we organize | |
346 | the body into "chunks" and provide a lookup table at the beginning of the | |
347 | body. The header includes certain length values, such as the number of packs, | |
348 | the number of base MIDX files, hash lengths and types. | |
349 | ||
350 | All 4-byte numbers are in network order. | |
351 | ||
352 | HEADER: | |
353 | ||
354 | 4-byte signature: | |
355 | The signature is: {'M', 'I', 'D', 'X'} | |
356 | ||
357 | 1-byte version number: | |
358 | Git only writes or recognizes version 1. | |
359 | ||
360 | 1-byte Object Id Version | |
d9607542 DS |
361 | We infer the length of object IDs (OIDs) from this value: |
362 | 1 => SHA-1 | |
363 | 2 => SHA-256 | |
364 | If the hash type does not match the repository's hash algorithm, | |
365 | the multi-pack-index file should be ignored with a warning | |
366 | presented to the user. | |
e0d1bcf8 DS |
367 | |
368 | 1-byte number of "chunks" | |
369 | ||
370 | 1-byte number of base multi-pack-index files: | |
371 | This value is currently always zero. | |
372 | ||
373 | 4-byte number of pack files | |
374 | ||
375 | CHUNK LOOKUP: | |
376 | ||
377 | (C + 1) * 12 bytes providing the chunk offsets: | |
378 | First 4 bytes describe chunk id. Value 0 is a terminating label. | |
379 | Other 8 bytes provide offset in current file for chunk to start. | |
380 | (Chunks are provided in file-order, so you can infer the length | |
381 | using the next chunk position if necessary.) | |
382 | ||
a43a2e6c | 383 | The CHUNK LOOKUP matches the table of contents from |
977c47b4 | 384 | the chunk-based file format, see linkgit:gitformat-chunk[5]. |
a43a2e6c | 385 | |
e0d1bcf8 DS |
386 | The remaining data in the body is described one chunk at a time, and |
387 | these chunks may be given in any order. Chunks are required unless | |
388 | otherwise specified. | |
389 | ||
390 | CHUNK DATA: | |
391 | ||
32f3c541 | 392 | Packfile Names (ID: {'P', 'N', 'A', 'M'}) |
1bd80993 TB |
393 | Store the names of packfiles as a sequence of NUL-terminated |
394 | strings. There is no extra padding between the filenames, | |
395 | and they are listed in lexicographic order. The chunk itself | |
396 | is padded at the end with between 0 and 3 NUL bytes to make the | |
397 | chunk size a multiple of 4 bytes. | |
32f3c541 | 398 | |
5f5ccd95 TB |
399 | Bitmapped Packfiles (ID: {'B', 'T', 'M', 'P'}) |
400 | Stores a table of two 4-byte unsigned integers in network order. | |
401 | Each table entry corresponds to a single pack (in the order that | |
402 | they appear above in the `PNAM` chunk). The values for each table | |
403 | entry are as follows: | |
404 | - The first bit position (in pseudo-pack order, see below) to | |
405 | contain an object from that pack. | |
406 | - The number of bits whose objects are selected from that pack. | |
407 | ||
d7cacf29 DS |
408 | OID Fanout (ID: {'O', 'I', 'D', 'F'}) |
409 | The ith entry, F[i], stores the number of OIDs with first | |
410 | byte at most i. Thus F[255] stores the total | |
411 | number of objects. | |
412 | ||
0d5b3a5e DS |
413 | OID Lookup (ID: {'O', 'I', 'D', 'L'}) |
414 | The OIDs for all objects in the MIDX are stored in lexicographic | |
415 | order in this chunk. | |
416 | ||
662148c4 DS |
417 | Object Offsets (ID: {'O', 'O', 'F', 'F'}) |
418 | Stores two 4-byte values for every object. | |
419 | 1: The pack-int-id for the pack storing this object. | |
420 | 2: The offset within the pack. | |
eb31044f | 421 | If all offsets are less than 2^32, then the large offset chunk |
662148c4 DS |
422 | will not exist and offsets are stored as in IDX v1. |
423 | If there is at least one offset value larger than 2^32-1, then | |
eb31044f JB |
424 | the large offset chunk must exist, and offsets larger than |
425 | 2^31-1 must be stored in it instead. If the large offset chunk | |
662148c4 DS |
426 | exists and the 31st bit is on, then removing that bit reveals |
427 | the row in the large offsets containing the 8-byte offset of | |
428 | this object. | |
429 | ||
430 | [Optional] Object Large Offsets (ID: {'L', 'O', 'F', 'F'}) | |
431 | 8-byte offsets into large packfiles. | |
e0d1bcf8 | 432 | |
95e8383b TB |
433 | [Optional] Bitmap pack order (ID: {'R', 'I', 'D', 'X'}) |
434 | A list of MIDX positions (one per object in the MIDX, num_objects in | |
435 | total, each a 4-byte unsigned integer in network byte order), sorted | |
436 | according to their relative bitmap/pseudo-pack positions. | |
437 | ||
e0d1bcf8 DS |
438 | TRAILER: |
439 | ||
17420eaf | 440 | Index checksum of the above contents. |
b25fd24c TB |
441 | |
442 | == multi-pack-index reverse indexes | |
443 | ||
444 | Similar to the pack-based reverse index, the multi-pack index can also | |
445 | be used to generate a reverse index. | |
446 | ||
447 | Instead of mapping between offset, pack-, and index position, this | |
448 | reverse index maps between an object's position within the MIDX, and | |
449 | that object's position within a pseudo-pack that the MIDX describes | |
450 | (i.e., the ith entry of the multi-pack reverse index holds the MIDX | |
451 | position of ith object in pseudo-pack order). | |
452 | ||
453 | To clarify the difference between these orderings, consider a multi-pack | |
454 | reachability bitmap (which does not yet exist, but is what we are | |
455 | building towards here). Each bit needs to correspond to an object in the | |
456 | MIDX, and so we need an efficient mapping from bit position to MIDX | |
457 | position. | |
458 | ||
459 | One solution is to let bits occupy the same position in the oid-sorted | |
460 | index stored by the MIDX. But because oids are effectively random, their | |
461 | resulting reachability bitmaps would have no locality, and thus compress | |
462 | poorly. (This is the reason that single-pack bitmaps use the pack | |
463 | ordering, and not the .idx ordering, for the same purpose.) | |
464 | ||
465 | So we'd like to define an ordering for the whole MIDX based around | |
466 | pack ordering, which has far better locality (and thus compresses more | |
467 | efficiently). We can think of a pseudo-pack created by the concatenation | |
468 | of all of the packs in the MIDX. E.g., if we had a MIDX with three packs | |
469 | (a, b, c), with 10, 15, and 20 objects respectively, we can imagine an | |
470 | ordering of the objects like: | |
471 | ||
472 | |a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19| | |
473 | ||
474 | where the ordering of the packs is defined by the MIDX's pack list, | |
475 | and then the ordering of objects within each pack is the same as the | |
476 | order in the actual packfile. | |
477 | ||
478 | Given the list of packs and their counts of objects, you can | |
479 | naïvely reconstruct that pseudo-pack ordering (e.g., the object at | |
480 | position 27 must be (c,1) because packs "a" and "b" consumed 25 of the | |
481 | slots). But there's a catch. Objects may be duplicated between packs, in | |
482 | which case the MIDX only stores one pointer to the object (and thus we'd | |
483 | want only one slot in the bitmap). | |
484 | ||
485 | Callers could handle duplicates themselves by reading objects in order | |
486 | of their bit-position, but that's linear in the number of objects, and | |
487 | much too expensive for ordinary bitmap lookups. Building a reverse index | |
488 | solves this, since it is the logical inverse of the index, and that | |
489 | index has already removed duplicates. But, building a reverse index on | |
490 | the fly can be expensive. Since we already have an on-disk format for | |
491 | pack-based reverse indexes, let's reuse it for the MIDX's pseudo-pack, | |
492 | too. | |
493 | ||
494 | Objects from the MIDX are ordered as follows to string together the | |
495 | pseudo-pack. Let `pack(o)` return the pack from which `o` was selected | |
496 | by the MIDX, and define an ordering of packs based on their numeric ID | |
497 | (as stored by the MIDX). Let `offset(o)` return the object offset of `o` | |
498 | within `pack(o)`. Then, compare `o1` and `o2` as follows: | |
499 | ||
500 | - If one of `pack(o1)` and `pack(o2)` is preferred and the other | |
501 | is not, then the preferred one sorts first. | |
502 | + | |
503 | (This is a detail that allows the MIDX bitmap to determine which | |
504 | pack should be used by the pack-reuse mechanism, since it can ask | |
505 | the MIDX for the pack containing the object at bit position 0). | |
506 | ||
507 | - If `pack(o1) ≠ pack(o2)`, then sort the two objects in descending | |
508 | order based on the pack ID. | |
509 | ||
510 | - Otherwise, `pack(o1) = pack(o2)`, and the objects are sorted in | |
511 | pack-order (i.e., `o1` sorts ahead of `o2` exactly when `offset(o1) | |
512 | < offset(o2)`). | |
513 | ||
514 | In short, a MIDX's pseudo-pack is the de-duplicated concatenation of | |
515 | objects in packs stored by the MIDX, laid out in pack order, and the | |
516 | packs arranged in MIDX order (with the preferred pack coming first). | |
517 | ||
95e8383b TB |
518 | The MIDX's reverse index is stored in the optional 'RIDX' chunk within |
519 | the MIDX itself. | |
977c47b4 | 520 | |
5f5ccd95 TB |
521 | === `BTMP` chunk |
522 | ||
523 | The Bitmapped Packfiles (`BTMP`) chunk encodes additional information | |
524 | about the objects in the multi-pack index's reachability bitmap. Recall | |
525 | that objects from the MIDX are arranged in "pseudo-pack" order (see | |
526 | above) for reachability bitmaps. | |
527 | ||
528 | From the example above, suppose we have packs "a", "b", and "c", with | |
529 | 10, 15, and 20 objects, respectively. In pseudo-pack order, those would | |
530 | be arranged as follows: | |
531 | ||
532 | |a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19| | |
533 | ||
534 | When working with single-pack bitmaps (or, equivalently, multi-pack | |
535 | reachability bitmaps with a preferred pack), linkgit:git-pack-objects[1] | |
536 | performs ``verbatim'' reuse, attempting to reuse chunks of the bitmapped | |
537 | or preferred packfile instead of adding objects to the packing list. | |
538 | ||
539 | When a chunk of bytes is reused from an existing pack, any objects | |
540 | contained therein do not need to be added to the packing list, saving | |
541 | memory and CPU time. But a chunk from an existing packfile can only be | |
542 | reused when the following conditions are met: | |
543 | ||
544 | - The chunk contains only objects which were requested by the caller | |
545 | (i.e. does not contain any objects which the caller didn't ask for | |
546 | explicitly or implicitly). | |
547 | ||
548 | - All objects stored in non-thin packs as offset- or reference-deltas | |
549 | also include their base object in the resulting pack. | |
550 | ||
551 | The `BTMP` chunk encodes the necessary information in order to implement | |
552 | multi-pack reuse over a set of packfiles as described above. | |
553 | Specifically, the `BTMP` chunk encodes three pieces of information (all | |
554 | 32-bit unsigned integers in network byte-order) for each packfile `p` | |
555 | that is stored in the MIDX, as follows: | |
556 | ||
557 | `bitmap_pos`:: The first bit position (in pseudo-pack order) in the | |
558 | multi-pack index's reachability bitmap occupied by an object from `p`. | |
559 | ||
560 | `bitmap_nr`:: The number of bit positions (including the one at | |
561 | `bitmap_pos`) that encode objects from that pack `p`. | |
562 | ||
563 | For example, the `BTMP` chunk corresponding to the above example (with | |
564 | packs ``a'', ``b'', and ``c'') would look like: | |
565 | ||
566 | [cols="1,2,2"] | |
567 | |=== | |
568 | | |`bitmap_pos` |`bitmap_nr` | |
569 | ||
570 | |packfile ``a'' | |
571 | |`0` | |
572 | |`10` | |
573 | ||
574 | |packfile ``b'' | |
575 | |`10` | |
576 | |`15` | |
577 | ||
578 | |packfile ``c'' | |
579 | |`25` | |
580 | |`20` | |
581 | |=== | |
582 | ||
583 | With this information in place, we can treat each packfile as | |
584 | individually reusable in the same fashion as verbatim pack reuse is | |
585 | performed on individual packs prior to the implementation of the `BTMP` | |
586 | chunk. | |
587 | ||
6b6029dd ÆAB |
588 | == cruft packs |
589 | ||
590 | The cruft packs feature offer an alternative to Git's traditional mechanism of | |
591 | removing unreachable objects. This document provides an overview of Git's | |
592 | pruning mechanism, and how a cruft pack can be used instead to accomplish the | |
593 | same. | |
594 | ||
595 | === Background | |
596 | ||
597 | To remove unreachable objects from your repository, Git offers `git repack -Ad` | |
598 | (see linkgit:git-repack[1]). Quoting from the documentation: | |
599 | ||
600 | ---- | |
601 | [...] unreachable objects in a previous pack become loose, unpacked objects, | |
602 | instead of being left in the old pack. [...] loose unreachable objects will be | |
603 | pruned according to normal expiry rules with the next 'git gc' invocation. | |
604 | ---- | |
605 | ||
606 | Unreachable objects aren't removed immediately, since doing so could race with | |
607 | an incoming push which may reference an object which is about to be deleted. | |
608 | Instead, those unreachable objects are stored as loose objects and stay that way | |
609 | until they are older than the expiration window, at which point they are removed | |
610 | by linkgit:git-prune[1]. | |
611 | ||
612 | Git must store these unreachable objects loose in order to keep track of their | |
613 | per-object mtimes. If these unreachable objects were written into one big pack, | |
614 | then either freshening that pack (because an object contained within it was | |
615 | re-written) or creating a new pack of unreachable objects would cause the pack's | |
616 | mtime to get updated, and the objects within it would never leave the expiration | |
617 | window. Instead, objects are stored loose in order to keep track of the | |
618 | individual object mtimes and avoid a situation where all cruft objects are | |
619 | freshened at once. | |
620 | ||
621 | This can lead to undesirable situations when a repository contains many | |
622 | unreachable objects which have not yet left the grace period. Having large | |
623 | directories in the shards of `.git/objects` can lead to decreased performance in | |
624 | the repository. But given enough unreachable objects, this can lead to inode | |
625 | starvation and degrade the performance of the whole system. Since we | |
626 | can never pack those objects, these repositories often take up a large amount of | |
627 | disk space, since we can only zlib compress them, but not store them in delta | |
628 | chains. | |
629 | ||
630 | === Cruft packs | |
631 | ||
632 | A cruft pack eliminates the need for storing unreachable objects in a loose | |
633 | state by including the per-object mtimes in a separate file alongside a single | |
634 | pack containing all loose objects. | |
635 | ||
636 | A cruft pack is written by `git repack --cruft` when generating a new pack. | |
637 | linkgit:git-pack-objects[1]'s `--cruft` option. Note that `git repack --cruft` | |
638 | is a classic all-into-one repack, meaning that everything in the resulting pack is | |
639 | reachable, and everything else is unreachable. Once written, the `--cruft` | |
640 | option instructs `git repack` to generate another pack containing only objects | |
641 | not packed in the previous step (which equates to packing all unreachable | |
642 | objects together). This progresses as follows: | |
643 | ||
644 | 1. Enumerate every object, marking any object which is (a) not contained in a | |
645 | kept-pack, and (b) whose mtime is within the grace period as a traversal | |
646 | tip. | |
647 | ||
648 | 2. Perform a reachability traversal based on the tips gathered in the previous | |
649 | step, adding every object along the way to the pack. | |
650 | ||
651 | 3. Write the pack out, along with a `.mtimes` file that records the per-object | |
652 | timestamps. | |
653 | ||
654 | This mode is invoked internally by linkgit:git-repack[1] when instructed to | |
655 | write a cruft pack. Crucially, the set of in-core kept packs is exactly the set | |
656 | of packs which will not be deleted by the repack; in other words, they contain | |
657 | all of the repository's reachable objects. | |
658 | ||
659 | When a repository already has a cruft pack, `git repack --cruft` typically only | |
660 | adds objects to it. An exception to this is when `git repack` is given the | |
661 | `--cruft-expiration` option, which allows the generated cruft pack to omit | |
662 | expired objects instead of waiting for linkgit:git-gc[1] to expire those objects | |
663 | later on. | |
664 | ||
665 | It is linkgit:git-gc[1] that is typically responsible for removing expired | |
666 | unreachable objects. | |
667 | ||
6b6029dd ÆAB |
668 | === Alternatives |
669 | ||
670 | Notable alternatives to this design include: | |
671 | ||
3843ef89 | 672 | - The location of the per-object mtime data. |
6b6029dd ÆAB |
673 | |
674 | On the location of mtime data, a new auxiliary file tied to the pack was chosen | |
675 | to avoid complicating the `.idx` format. If the `.idx` format were ever to gain | |
676 | support for optional chunks of data, it may make sense to consolidate the | |
677 | `.mtimes` format into the `.idx` itself. | |
678 | ||
977c47b4 ÆAB |
679 | GIT |
680 | --- | |
681 | Part of the linkgit:git[1] suite |