Object types¶

Valid object types are:

Type 5 is reserved for future expansion. Type 0 is invalid.

Size encoding¶

This document uses the following "size encoding" of non-negative integers: From each byte, the seven least significant bits are used to form the resulting integer. As long as the most significant bit is 1, this process continues; the byte with MSB 0 provides the last seven bits. The seven-bit chunks are concatenated. Later values are more significant.

This size encoding should not be confused with the "offset encoding", which is also used in this document.

Deltified representation¶

Conceptually there are only four object types: commit, tree, tag and blob. However to save space, an object could be stored as a "delta" of another "base" object. These representations are assigned new types ofs-delta and ref-delta, which is only valid in a pack file.

Both ofs-delta and ref-delta store the "delta" to be applied to another object (called base object) to reconstruct the object. The difference between them is, ref-delta directly encodes base object name. If the base object is in the same pack, ofs-delta encodes the offset of the base object in the pack instead.

The base object could also be deltified if it’s in the same pack. Ref-delta can also refer to an object outside the pack (i.e. the so-called "thin pack"). When stored on disk however, the pack should be self contained to avoid cyclic dependency.

The delta data starts with the size of the base object and the size of the object to be reconstructed. These sizes are encoded using the size encoding from above. The remainder of the delta data is a sequence of instructions to reconstruct the object from the base object. If the base object is deltified, it must be converted to canonical form first. Each instruction appends more and more data to the target object until it’s complete. There are two supported instructions so far: one for copying a byte range from the source object and one for inserting new data embedded in the instruction itself.

Each instruction has variable length. Instruction type is determined by the seventh bit of the first octet. The following diagrams follow the convention in RFC 1951 (Deflate compressed data format).

Instruction to copy from base object

+----------+---------+---------+---------+---------+-------+-------+-------+
| 1xxxxxxx | offset1 | offset2 | offset3 | offset4 | size1 | size2 | size3 |
+----------+---------+---------+---------+---------+-------+-------+-------+

+----------+---------+---------+
| 10000101 | offset1 | offset3 |
+----------+---------+---------+

Instruction to add new data

+----------+============+
| 0xxxxxxx |    data    |
+----------+============+

Reserved instruction

+----------+============
| 00000000 |
+----------+============

BTMP chunk¶

The Bitmapped Packfiles (BTMP) chunk encodes additional information about the objects in the multi-pack index’s reachability bitmap. Recall that objects from the MIDX are arranged in "pseudo-pack" order (see above) for reachability bitmaps.

From the example above, suppose we have packs "a", "b", and "c", with 10, 15, and 20 objects, respectively. In pseudo-pack order, those would be arranged as follows:

|a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19|

When working with single-pack bitmaps (or, equivalently, multi-pack reachability bitmaps with a preferred pack), git-pack-objects(1) performs “verbatim” reuse, attempting to reuse chunks of the bitmapped or preferred packfile instead of adding objects to the packing list.

When a chunk of bytes is reused from an existing pack, any objects contained therein do not need to be added to the packing list, saving memory and CPU time. But a chunk from an existing packfile can only be reused when the following conditions are met:

The BTMP chunk encodes the necessary information in order to implement multi-pack reuse over a set of packfiles as described above. Specifically, the BTMP chunk encodes three pieces of information (all 32-bit unsigned integers in network byte-order) for each packfile p that is stored in the MIDX, as follows:

bitmap_pos

bitmap_nr

For example, the BTMP chunk corresponding to the above example (with packs “a”, “b”, and “c”) would look like:

With this information in place, we can treat each packfile as individually reusable in the same fashion as verbatim pack reuse is performed on individual packs prior to the implementation of the BTMP chunk.

Background¶

To remove unreachable objects from your repository, Git offers git repack -Ad (see git-repack(1)). Quoting from the documentation:

[...] unreachable objects in a previous pack become loose, unpacked objects,
instead of being left in the old pack. [...] loose unreachable objects will be
pruned according to normal expiry rules with the next 'git gc' invocation.

Unreachable objects aren’t removed immediately, since doing so could race with an incoming push which may reference an object which is about to be deleted. Instead, those unreachable objects are stored as loose objects and stay that way until they are older than the expiration window, at which point they are removed by git-prune(1).

Git must store these unreachable objects loose in order to keep track of their per-object mtimes. If these unreachable objects were written into one big pack, then either freshening that pack (because an object contained within it was re-written) or creating a new pack of unreachable objects would cause the pack’s mtime to get updated, and the objects within it would never leave the expiration window. Instead, objects are stored loose in order to keep track of the individual object mtimes and avoid a situation where all cruft objects are freshened at once.

This can lead to undesirable situations when a repository contains many unreachable objects which have not yet left the grace period. Having large directories in the shards of .git/objects can lead to decreased performance in the repository. But given enough unreachable objects, this can lead to inode starvation and degrade the performance of the whole system. Since we can never pack those objects, these repositories often take up a large amount of disk space, since we can only zlib compress them, but not store them in delta chains.

Cruft packs¶

A cruft pack eliminates the need for storing unreachable objects in a loose state by including the per-object mtimes in a separate file alongside a single pack containing all loose objects.

A cruft pack is written by git repack --cruft when generating a new pack. git-pack-objects(1)'s --cruft option. Note that git repack --cruft is a classic all-into-one repack, meaning that everything in the resulting pack is reachable, and everything else is unreachable. Once written, the --cruft option instructs git repack to generate another pack containing only objects not packed in the previous step (which equates to packing all unreachable objects together). This progresses as follows:

This mode is invoked internally by git-repack(1) when instructed to write a cruft pack. Crucially, the set of in-core kept packs is exactly the set of packs which will not be deleted by the repack; in other words, they contain all of the repository’s reachable objects.

When a repository already has a cruft pack, git repack --cruft typically only adds objects to it. An exception to this is when git repack is given the --cruft-expiration option, which allows the generated cruft pack to omit expired objects instead of waiting for git-gc(1) to expire those objects later on.

It is git-gc(1) that is typically responsible for removing expired unreachable objects.

Alternatives¶

Notable alternatives to this design include:

On the location of mtime data, a new auxiliary file tied to the pack was chosen to avoid complicating the .idx format. If the .idx format were ever to gain support for optional chunks of data, it may make sense to consolidate the .mtimes format into the .idx itself.