Přejít k obsahu

Soubory pack

Zobrazit jako Markdown Upravit na GitHub Dokumentace na bfe242f

Soubory pack jsou mechanismem git pro efektivní ukládání a přenos. Místo ukládání každého objektu jako samostatného souboru komprimovaného pomocí zlib kombinují mnoho objektů do jednoho souboru s volitelnou kompresí delt. Soubory pack používá téměř každé naklonované úložiště.

Struktura souboru pack

Soubor pack (.git/objects/pack/pack-{hash}.pack) obsahuje:

Kód
Header:   PACK (4 bytes) + version (4 bytes, big-endian) + count (4 bytes, big-endian)
Entries:  [type+size varint] [delta-base] [zlib-compressed data] ...
Trailer:  checksum of the pack (20 bytes SHA-1, 32 bytes SHA-256)

Kódování typu objektu

Každá položka začíná celočíselnou hodnotou proměnné délky, v níž jsou typ a velikost proloženy:

Kód
First byte: 1TTTSSSS
  TTT  = object type (1-4 for base objects, 6 for OFS_DELTA, 7 for REF_DELTA)
  SSSS = first 4 bits of uncompressed size
  MSB  = 1 means more size bytes follow

Hodnoty typu:

Hodnota Typ
1 Commit
2 Tree
3 Blob
4 Tag
6 OFS_DELTA (delta založená na offsetu)
7 REF_DELTA (delta založená na hashi)

Čtení souborů pack

PHP
use Pitmaster\Pack\PackFile;

$pack = PackFile::open(
    '/path/to/.git/objects/pack/pack-abc123.pack',
    '/path/to/.git/objects/pack/pack-abc123.idx',
);

$pack->has($hex);               // Is the object in this pack?
$object = $pack->read($hex);    // Resolved GitObject, or null
$object = $pack->readAtOffset($offset);
$hashes = $pack->allHashes();

Třída PackFile:

  1. Ověří hlavičku PACK a číslo verze
  2. Vyhledá offset v souboru .idx a načte varint typu a velikosti položky
  3. Dekomprimuje data komprimovaná pomocí zlib
  4. U základních objektů vrátí obsah přímo
  5. U deltových objektů najde základ (postupuje řetězcem delt), použije deltu a objekty po vyřešení ukládá do mezipaměti

Soubory indexu pack

Ke každému souboru .pack patří soubor .idx pro rychlé vyhledávání. Bez indexu je nutné při hledání objektu prohledat celý soubor pack.

Formát indexu v2

Kód
Magic:    FF 74 4F 63 (identifies v2)
Version:  00 00 00 02
Fanout:   256 x 4-byte big-endian counts (cumulative)
Names:    N x 20-byte SHA-1 hashes, sorted (32 bytes for SHA-256)
CRC32s:   N x 4-byte CRC32 checksums
Offsets:  N x 4-byte pack offsets (MSB=1 means large offset table)
Large:    M x 8-byte offsets (for packs > 2GB)
Checksums: pack checksum + index checksum (20 bytes each for SHA-1)
PHP
use Pitmaster\Pack\PackIndex;

$index = PackIndex::open('/path/to/pack-abc123.idx');

// Look up an object
$offset = $index->findOffset($hex);  // Pack file offset, or null

// List all objects in the pack
$hashes = $index->allHashes();
$count = $index->objectCount();

Tabulka rozptylu umožňuje binární vyhledávání O(log n): položky 256 udávají, kolik hashů začíná každým možným prvním bajtem.

Formát indexu v1

Starší formát bez kontrolních součtů CRC32. Pitmaster podporuje oba formáty: PackIndex::open() načte soubor v1, pokud chybí magická hodnota v2, takže stejný kód funguje pro oba.

Řešení delt

Objekty uložené pomocí delty obsahují pokyny k obnovení obsahu ze základního objektu místo celého obsahu. Tím se dosahuje výrazné komprese u podobných objektů (e.g např. po sobě jdoucích verzí stejného souboru).

Typy delt

OFS_DELTA (typ 6): základní objekt je určen záporným offsetem v rámci stejného souboru pack. Tento typ je běžnější, protože nevyžaduje znalost hashe základního objektu.

REF_DELTA (typ 7): základní objekt je určen svým hashem. V gitu může být základ mimo soubor pack (tenké soubory pack). Pitmaster hledá základy REF_DELTA pouze v rámci stejného souboru pack, takže tenké soubory pack nejsou podporovány (#16).

Pokyny delty

Obsah delty tvoří posloupnost pokynů ke kopírování a vkládání:

Kód
Copy:   1XXXXXXX [offset bytes] [size bytes]   (copy from base)
Insert: 0LLLLLLL <L bytes of literal data>       (insert new data)

Pokyny ke kopírování: 7 bitů X určuje, které bajty offsetu a velikosti jsou přítomné. Offset může mít až 4 bajty, velikost až 3 bajty. Pokud je velikost nula, znamená to 65536 bajtů.

Pokyny k vložení: 7 bitů L udává délku doslovných dat (1–127 bajtů). L=0 je vyhrazená/neplatná hodnota.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

$result = DeltaApplier::apply($baseContent, $deltaInstructions);

DeltaApplier:

  1. Načte očekávanou velikost základu a výslednou velikost z hlavičky delty (kódování LEB128)
  2. Prochází pokyny:
    • Kopírování: načte offset a velikost a zkopíruje bajty z obsahu základu
    • Vložení: načte délku a zkopíruje doslovné bajty z dat delty
  3. Ověří, že výsledná velikost odpovídá očekávané velikosti

Řetězce delt

Základ objektu uloženého pomocí delty může být sám uložen pomocí delty. PackFile::read() a readAtOffset() postupují řetězcem:

  1. Načte položku. Pokud jde o základní typ (commit, tree, blob, tag), vrátí ji.
  2. U OFS_DELTA vypočítá offset základu (aktuální offset minus zakódovaný záporný offset), načte základní položku a rekurzivně pokračuje.
  3. U REF_DELTA vyhledá základ podle hashe v indexu stejného souboru pack a rekurzivně pokračuje.
  4. Použije pokyny delty na vyřešený základ.
  5. Vynutí limit PITMASTER_MAX_DELTA_CHAIN (výchozí hodnota 50), aby zabránil nekonečně dlouhým řetězcům.
PHP
// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

// Read the effective limit
$max = \Pitmaster\Pack\DeltaResolver::maxChainDepth();

PackWriter

Pitmaster může zapisovat soubory pack pro síťové operace (push).

PHP
use Pitmaster\Pack\PackWriter;
use Pitmaster\Pack\PackIndexer;

$packData = PackWriter::encode($objects);           // GitObject[] to pack bytes
$paths = PackWriter::write($packDir, $objects);     // ['packPath' => ..., 'idxPath' => ..., 'hash' => ...]

$idxPath = PackIndexer::writeIndex($packPath);      // Build the .idx for a received pack

PackWriter:

  1. Shromáždí objekty, které mají být zahrnuty do souboru pack
  2. Serializuje každý objekt s hlavičkou varint typu a velikosti
  3. Komprimuje obsah pomocí zlib
  4. Zapíše hlavičku PACK, položky a závěrečný SHA-1

V současnosti zapisuje pouze základní objekty (bez komprese delt). Komprese delt je optimalizace, kterou lze přidat později; přenechte přebalení kvůli efektivnějšímu ukládání nástroji git gc.

PackEnumerator

Procházet všechny objekty v souboru pack v pořadí podle indexu:

PHP
use Pitmaster\Pack\PackEnumerator;

$enumerator = new PackEnumerator($packFile); // a PackFile opened with its .idx

foreach ($enumerator->enumerate() as $object) {
    echo "{$object->type->value} {$object->id->hex} {$object->size()}\n";
}

Každá položka je vyřešený objekt GitObject.

MultiPackIndex

U úložišť s mnoha soubory pack poskytuje multi-pack-index (MIDX) jednotné vyhledávání napříč všemi soubory pack.

PHP
use Pitmaster\Pack\MultiPackIndex;

Soubor MIDX (.git/objects/pack/multi-pack-index) obsahuje:

  • Tabulku rozptylu (jako index pack v2)
  • ID objektů seřazená napříč všemi soubory pack
  • Názvy souborů pack a přiřazení jednotlivých objektů k souborům pack
  • Offsety v jednotlivých souborech pack

MultiPackIndex::open($path) analyzuje soubor MIDX a poskytuje findObject($hex) a packNames(). Vyhledávání objektů v úložišti jej nepoužívá: databáze objektů vždy čte jednotlivé soubory .idx.

CommitGraph

Soubor commit-graph urychluje procházení historie commitů a výpočet základů sloučení.

PHP
use Pitmaster\Pack\CommitGraph;

Nachází se v .git/objects/info/commit-graph a obsahuje:

  • OID commitů v seřazeném pořadí
  • Informace o rodičích (indexované, bez nutnosti číst objekty)
  • Generační čísla (pro rychlejší dotazy na dosažitelnost)
  • Časová razítka commitů

Pokud je k dispozici, výpočet základního sloučení pro Repository::merge(), mergeBase(), isBranchMerged() a kontrola rychlého posunu při odesílání čtou odkazy na rodiče z grafu commitů namísto jednotlivých objektů commitů. CommitWalker (log) tuto možnost nepoužívá.

Celá čísla proměnné délky

Soubory pack používají několik kódování celých čísel proměnné délky:

Git varint (hlavičky typu a velikosti)

Kódování MSB-continue, kde nejvýznamnější bit označuje, že následují další bajty:

PHP
use Pitmaster\Encoding\VarInt;

$size = VarInt::decodePackSize($reader, $initialBits);  // continues the size from the first header byte
$offset = VarInt::decodeOfsOffset($reader);             // OFS_DELTA base distance
$header = VarInt::encodePackSize($type, $size);

LEB128 (hlavičky rozdílů)

Používá se v hlavičkách instrukcí rozdílu pro velikost základu a výsledku:

PHP
use Pitmaster\Encoding\Leb128;

$value = Leb128::decodeUnsigned($reader);   // a BinaryReader
$bytes = Leb128::encodeUnsigned($value);

BinaryReader

Nízkourovňový proud bajtů se sledováním pozice:

PHP
use Pitmaster\Encoding\BinaryReader;

$reader = new BinaryReader($data);
$byte = $reader->readByte();
$int = $reader->readUint32();   // big-endian
$bytes = $reader->read(20);
$hash = $reader->readHash(20);
$reader->position();  // Current offset
$reader->seek(0);