Git - hash-function-transition Documentation (original) (raw)

Repository format extension

A SHA-256 repository uses repository format version 1 (seegitrepository-layout[5]) with extensions.objectFormat andextensions.compatObjectFormat (see git-config[1]) set to:

[core] repositoryFormatVersion = 1 [extensions] objectFormat = sha256 compatObjectFormat = sha1

The combination of setting core.repositoryFormatVersion=1 and populating extensions.* ensures that all versions of Git later thanv0.99.9l will die instead of trying to operate on the SHA-256 repository, instead producing an error message.

Between v0.99.9l and v2.7.0

$ git status fatal: Expected git repo version <= 0, found 1

After v2.7.0

$ git status fatal: unknown repository extensions found: objectformat compatobjectformat

See the "Transition plan" section below for more details on these repository extensions.

Object names

Objects can be named by their 40 hexadecimal digit SHA-1 name or 64 hexadecimal digit SHA-256 name, plus names derived from those (see gitrevisions(7)).

The SHA-1 name of an object is the SHA-1 of the concatenation of its type, length, a nul byte, and the object’s SHA-1 content. This is the traditional used in Git to name objects.

The SHA-256 name of an object is the SHA-256 of the concatenation of its type, length, a nul byte, and the object’s SHA-256 content.

Object format

The content as a byte sequence of a tag, commit, or tree object named by SHA-1 and SHA-256 differ because an object named by SHA-256 name refers to other objects by their SHA-256 names and an object named by SHA-1 name refers to other objects by their SHA-1 names.

The SHA-256 content of an object is the same as its SHA-1 content, except that objects referenced by the object are named using their SHA-256 names instead of SHA-1 names. Because a blob object does not refer to any other object, its SHA-1 content and SHA-256 content are the same.

The format allows round-trip conversion between SHA-256 content and SHA-1 content.

Object storage

Loose objects use zlib compression and packed objects use the packed format described in gitformat-pack[5], just like today. The content that is compressed and stored uses SHA-256 content instead of SHA-1 content.

Pack index

Pack index (.idx) files use a new v3 format that supports multiple hash functions. They have the following format (all integers are in network byte order):

• A header appears at the beginning and consists of the following:
  • The 4-byte pack index signature: \377t0c
  • 4-byte version number: 3
  • 4-byte length of the header section, including the signature and version number
  • 4-byte number of objects contained in the pack
  • 4-byte number of object formats in this pack index: 2
  • For each object format:
    * 4-byte format identifier (e.g., sha1 for SHA-1)
    * 4-byte length in bytes of shortened object names. This is the shortest possible length needed to make names in the shortened object name table unambiguous.
    * 4-byte integer, recording where tables relating to this format are stored in this index file, as an offset from the beginning.
  • 4-byte offset to the trailer from the beginning of this file.
  • Zero or more additional key/value pairs (4-byte key, 4-byte value). Only one key is supported: PSRC. See the "Loose objects and unreachable objects" section for supported values and how this is used. All other keys are reserved. Readers must ignore unrecognized keys.
• Zero or more NUL bytes. This can optionally be used to improve the alignment of the full object name table below.
• Tables for the first object format:
  • A sorted table of shortened object names. These are prefixes of the names of all objects in this pack file, packed together without offset values to reduce the cache footprint of the binary search for a specific object name.
  • A table of full object names in pack order. This allows resolving a reference to "the nth object in the pack file" (from a reachability bitmap or from the next table of another object format) to its object name.
  • A table of 4-byte values mapping object name order to pack order. For an object in the table of sorted shortened object names, the value at the corresponding index in this table is the index in the previous table for that same object. This can be used to look up the object in reachability bitmaps or to look up its name in another object format.
  • A table of 4-byte CRC32 values of the packed object data, in the order that the objects appear in the pack file. This is to allow compressed data to be copied directly from pack to pack during repacking without undetected data corruption.
  • A table of 4-byte offset values. For an object in the table of sorted shortened object names, the value at the corresponding index in this table indicates where that object can be found in the pack file. These are usually 31-bit pack file offsets, but large offsets are encoded as an index into the next table with the most significant bit set.
  • A table of 8-byte offset entries (empty for pack files less than 2 GiB). Pack files are organized with heavily used objects toward the front, so most object references should not need to refer to this table.
• Zero or more NUL bytes.
• Tables for the second object format, with the same layout as above, up to and not including the table of CRC32 values.
• Zero or more NUL bytes.
• The trailer consists of the following:
  • A copy of the 20-byte SHA-256 checksum at the end of the corresponding packfile.
  • 20-byte SHA-256 checksum of all of the above.

Loose object index

A new file $GIT_OBJECT_DIR/loose-object-idx contains information about all loose objects. Its format is

loose-object-idx

(sha256-name SP sha1-name LF)*

where the object names are in hexadecimal format. The file is not sorted.

The loose object index is protected against concurrent writes by a lock file $GIT_OBJECT_DIR/loose-object-idx.lock. To add a new loose object:

1. Write the loose object to a temporary file, like today.
2. Open loose-object-idx.lock with O_CREAT | O_EXCL to acquire the lock.
3. Rename the loose object into place.
4. Open loose-object-idx with O_APPEND and write the new object
5. Unlink loose-object-idx.lock to release the lock.

To remove entries (e.g. in "git pack-refs" or "git-prune"):

1. Open loose-object-idx.lock with O_CREAT | O_EXCL to acquire the lock.
2. Write the new content to loose-object-idx.lock.
3. Unlink any loose objects being removed.
4. Rename to replace loose-object-idx, releasing the lock.

Translation table

The index files support a bidirectional mapping between SHA-1 names and SHA-256 names. The lookup proceeds similarly to ordinary object lookups. For example, to convert a SHA-1 name to a SHA-256 name:

1. Look for the object in idx files. If a match is present in the idx’s sorted list of truncated SHA-1 names, then:
   1. Read the corresponding entry in the SHA-1 name order to pack name order mapping.
   2. Read the corresponding entry in the full SHA-1 name table to verify we found the right object. If it is, then
   3. Read the corresponding entry in the full SHA-256 name table. That is the object’s SHA-256 name.
2. Check for a loose object. Read lines from loose-object-idx until we find a match.

Step (1) takes the same amount of time as an ordinary object lookup: O(number of packs * log(objects per pack)). Step (2) takes O(number of loose objects) time. To maintain good performance it will be necessary to keep the number of loose objects low. See the "Loose objects and unreachable objects" section below for more details.

Since all operations that make new objects (e.g., "git commit") add the new objects to the corresponding index, this mapping is possible for all objects in the object store.

Reading an object’s SHA-1 content

The SHA-1 content of an object can be read by converting all SHA-256 names of its SHA-256 content references to SHA-1 names using the translation table.

Fetch

Fetching from a SHA-1 based server requires translating between SHA-1 and SHA-256 based representations on the fly.

SHA-1s named in the ref advertisement that are present on the client can be translated to SHA-256 and looked up as local objects using the translation table.

Negotiation proceeds as today. Any "have"s generated locally are converted to SHA-1 before being sent to the server, and SHA-1s mentioned by the server are converted to SHA-256 when looking them up locally.

After negotiation, the server sends a packfile containing the requested objects. We convert the packfile to SHA-256 format using the following steps:

1. index-pack: inflate each object in the packfile and compute its SHA-1. Objects can contain deltas in OBJ_REF_DELTA format against objects the client has locally. These objects can be looked up using the translation table and their SHA-1 content read as described above to resolve the deltas.
2. topological sort: starting at the "want"s from the negotiation phase, walk through objects in the pack and emit a list of them, excluding blobs, in reverse topologically sorted order, with each object coming later in the list than all objects it references. (This list only contains objects reachable from the "wants". If the pack from the server contained additional extraneous objects, then they will be discarded.)
3. convert to SHA-256: open a new SHA-256 packfile. Read the topologically sorted list just generated. For each object, inflate its SHA-1 content, convert to SHA-256 content, and write it to the SHA-256 pack. Record the new SHA-1←→SHA-256 mapping entry for use in the idx.
4. sort: reorder entries in the new pack to match the order of objects in the pack the server generated and include blobs. Write a SHA-256 idx file
5. clean up: remove the SHA-1 based pack file, index, and topologically sorted list obtained from the server in steps 1 and 2.

Step 3 requires every object referenced by the new object to be in the translation table. This is why the topological sort step is necessary.

As an optimization, step 1 could write a file describing what non-blob objects each object it has inflated from the packfile references. This makes the topological sort in step 2 possible without inflating the objects in the packfile for a second time. The objects need to be inflated again in step 3, for a total of two inflations.

Step 4 is probably necessary for good read-time performance. "git pack-objects" on the server optimizes the pack file for good data locality (see Documentation/technical/pack-heuristics.adoc).

Details of this process are likely to change. It will take some experimenting to get this to perform well.

Push

Push is simpler than fetch because the objects referenced by the pushed objects are already in the translation table. The SHA-1 content of each object being pushed can be read as described in the "Reading an object’s SHA-1 content" section to generate the pack written by git send-pack.

Signed Commits

We add a new field "gpgsig-sha256" to the commit object format to allow signing commits without relying on SHA-1. It is similar to the existing "gpgsig" field. Its signed payload is the SHA-256 content of the commit object with any "gpgsig" and "gpgsig-sha256" fields removed.

This means commits can be signed

1. using SHA-1 only, as in existing signed commit objects
2. using both SHA-1 and SHA-256, by using both gpgsig-sha256 and gpgsig fields.
3. using only SHA-256, by only using the gpgsig-sha256 field.

Old versions of "git verify-commit" can verify the gpgsig signature in cases (1) and (2) without modifications and view case (3) as an ordinary unsigned commit.

Signed Tags

We add a new field "gpgsig-sha256" to the tag object format to allow signing tags without relying on SHA-1. Its signed payload is the SHA-256 content of the tag with its gpgsig-sha256 field and "-----BEGIN PGP SIGNATURE-----" delimited in-body signature removed.

This means tags can be signed

1. using SHA-1 only, as in existing signed tag objects
2. using both SHA-1 and SHA-256, by using gpgsig-sha256 and an in-body signature.
3. using only SHA-256, by only using the gpgsig-sha256 field.

Mergetag embedding

The mergetag field in the SHA-1 content of a commit contains the SHA-1 content of a tag that was merged by that commit.

The mergetag field in the SHA-256 content of the same commit contains the SHA-256 content of the same tag.

Submodules

To convert recorded submodule pointers, you need to have the converted submodule repository in place. The translation table of the submodule can be used to look up the new hash.

Loose objects and unreachable objects

Fast lookups in the loose-object-idx require that the number of loose objects not grow too high.

"git gc --auto" currently waits for there to be 6700 loose objects present before consolidating them into a packfile. We will need to measure to find a more appropriate threshold for it to use.

"git gc --auto" currently waits for there to be 50 packs present before combining packfiles. Packing loose objects more aggressively may cause the number of pack files to grow too quickly. This can be mitigated by using a strategy similar to Martin Fick’s exponential rolling garbage collection script:https://gerrit-review.googlesource.com/c/gerrit/+/35215

"git gc" currently expels any unreachable objects it encounters in pack files to loose objects in an attempt to prevent a race when pruning them (in case another process is simultaneously writing a new object that refers to the about-to-be-deleted object). This leads to an explosion in the number of loose objects present and disk space usage due to the objects in delta form being replaced with independent loose objects. Worse, the race is still present for loose objects.

Instead, "git gc" will need to move unreachable objects to a new packfile marked as UNREACHABLE_GARBAGE (using the PSRC field; see below). To avoid the race when writing new objects referring to an about-to-be-deleted object, code paths that write new objects will need to copy any objects from UNREACHABLE_GARBAGE packs that they refer to new, non-UNREACHABLE_GARBAGE packs (or loose objects). UNREACHABLE_GARBAGE are then safe to delete if their creation time (as indicated by the file’s mtime) is long enough ago.

To avoid a proliferation of UNREACHABLE_GARBAGE packs, they can be combined under certain circumstances. If "gc.garbageTtl" is set to greater than one day, then packs created within a single calendar day, UTC, can be coalesced together. The resulting packfile would have an mtime before midnight on that day, so this makes the effective maximum ttl the garbageTtl + 1 day. If "gc.garbageTtl" is less than one day, then we divide the calendar day into intervals one-third of that ttl in duration. Packs created within the same interval can be coalesced together. The resulting packfile would have an mtime before the end of the interval, so this makes the effective maximum ttl equal to the garbageTtl * 4/3.

The UNREACHABLE_GARBAGE setting goes in the PSRC field of the pack index. More generally, that field indicates where a pack came from:

• 1 (PACK_SOURCE_RECEIVE) for a pack received over the network
• 2 (PACK_SOURCE_AUTO) for a pack created by a lightweight "gc --auto" operation
• 3 (PACK_SOURCE_GC) for a pack created by a full gc
• 4 (PACK_SOURCE_UNREACHABLE_GARBAGE) for potential garbage discovered by gc
• 5 (PACK_SOURCE_INSERT) for locally created objects that were written directly to a pack file, e.g. from "git add ."

This information can be useful for debugging and for "gc --auto" to make appropriate choices about which packs to coalesce.