Preskočiť na obsah

Súbory Pack

Zobraziť ako Markdown Upraviť na GitHub Dokumentácia na bfe242f

Súbory pack sú mechanizmom git na efektívne ukladanie a prenos. Namiesto ukladania každého objektu ako samostatného súboru komprimovaného pomocou zlib spájajú viacero objektov do jedného súboru s voliteľnou kompresiou delta. Súbory pack používa takmer každý naklonovaný repozitár.

Štruktúra súboru pack

Súbor 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ódovanie typu objektu

Každá položka sa začína celým číslom s premennou dĺžkou, v ktorom sa striedajú bity typu a veľkosti:

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 posune)
7 REF_DELTA (delta založená na hashi)

Čítanie súborov 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();

Trieda PackFile:

  1. Overí hlavičku PACK a číslo verzie
  2. Nájde posun pomocou súboru .idx a analyzuje varint typu a veľkosti položky
  3. Dekomprimuje údaje komprimované pomocou zlib
  4. Pri základných objektoch: vráti priamo obsah
  5. Pri delta objektoch: rozlíši základ (sledovaním reťazcov), použije deltu a uloží rozlíšené objekty do vyrovnávacej pamäte

Súbory indexu pack

Ku každému súboru .pack patrí súbor .idx na rýchle vyhľadávanie. Bez indexu by bolo potrebné hľadať objekt skenovaním celého súboru 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();

Tabuľka rozvetvenia umožňuje binárne vyhľadávanie O(log n): položky 256 uvádzajú počet hashov začínajúcich sa každým možným prvým bajtom.

Formát indexu v1

Starší formát bez kontrolných súčtov CRC32. Pitmaster podporuje oba formáty: PackIndex::open() načíta súbor v1, ak chýba magické číslo v2, takže rovnaký kód funguje pre oba.

Rozlíšenie delty

Objekty zakódované pomocou delty ukladajú pokyny na obnovenie obsahu zo základného objektu namiesto celého obsahu. Podobné objekty sa tak dajú výrazne komprimovať (e.g., napríklad po sebe idúce verzie toho istého súboru).

Typy delty

OFS_DELTA (typ 6): základný objekt sa určuje záporným posunom v rámci toho istého súboru pack. Tento typ je bežnejší, pretože netreba poznať hash základného objektu.

REF_DELTA (typ 7): základný objekt sa určuje podľa hashu. V git môže byť základ mimo súboru pack (tenké súbory pack). Pitmaster hľadá REF_DELTA základy iba v tom istom súbore pack, preto tenké súbory pack nie sú podporované (#16).

Pokyny delty

Obsah delty tvorí postupnosť pokynov na kopírovanie a vkladanie:

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

Pokyny na kopírovanie: 7 bitov X označuje, ktoré bajty posunu a veľkosti sú prítomné. Posun má najviac 4 bajty, veľkosť najviac 3 bajty. Ak je veľkosť nulová, znamená to 0x10000 (65536) bajtov.

Pokyny na vloženie: 7 bitov L udáva dĺžku doslovných údajov (1 až 127 bajtov). L=0 je vyhradená alebo neplatná hodnota.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

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

DeltaApplier:

  1. Načíta očakávanú veľkosť základu a výslednú veľkosť z hlavičky delty (kódované pomocou LEB128)
  2. Prechádza pokyny:
    • Kopírovanie: získa posun a veľkosť a skopíruje bajty zo základného obsahu
    • Vkladanie: získa dĺžku a skopíruje doslovné bajty z údajov delty
  3. Overí, či výsledná veľkosť zodpovedá očakávanej veľkosti

Reťazce delt

Základ objektu zakódovaného pomocou delty môže byť sám zakódovaný deltou. PackFile::read() a readAtOffset() sledujú reťazec:

  1. Načíta položku. Ak ide o základný typ (commit, tree, blob, tag), vráti ju.
  2. Ak ide o OFS_DELTA: vypočíta posun základu (aktuálny posun mínus zakódovaný záporný posun), načíta základnú položku a rekurzívne pokračuje.
  3. Ak ide o REF_DELTA: vyhľadá základ podľa hashu v indexe toho istého súboru pack a rekurzívne pokračuje.
  4. Použije pokyny delty na rozlíšený základ.
  5. Vynúti limit PITMASTER_MAX_DELTA_CHAIN (predvolene 50), aby zabránil nekonečným reťazcom.
PHP
// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

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

PackWriter

Pitmaster dokáže zapisovať súbory pack pre sieťové operácie (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. Zhromaždí objekty, ktoré sa majú zahrnúť do súboru pack
  2. Serializuje každý objekt s hlavičkou typu a veľkosti vo formáte varint
  3. Komprimuje obsah pomocou zlib
  4. Zapíše hlavičku PACK, položky a koncový údaj SHA-1

V súčasnosti zapisuje iba základné objekty (bez kompresie delta). Kompresiu delta možno pridať neskôr; pri efektívnejšom ukladaní nechajte objekty prezbaliť pomocou git gc.

PackEnumerator

Prechádza všetky objekty v súbore pack v poradí podľa 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 rozlíšený objekt GitObject.

MultiPackIndex

V repozitároch s mnohými súbormi pack poskytuje Multi-Pack Index (MIDX) jednotné vyhľadávanie naprieč všetkými súbormi pack.

PHP
use Pitmaster\Pack\MultiPackIndex;

Súbor MIDX (.git/objects/pack/multi-pack-index) obsahuje:

  • Tabuľku rozvetvenia (ako v indexe pack v2)
  • ID objektov zoradené naprieč všetkými súbormi pack
  • Názvy súborov pack a priradenie jednotlivých objektov k súborom pack
  • Posuny v jednotlivých súboroch pack

MultiPackIndex::open($path) analyzuje súbor MIDX a poskytuje findObject($hex) a packNames(). Vyhľadávanie objektov v repozitári ho nepoužíva: databáza objektov vždy číta jednotlivé súbory .idx.

CommitGraph

Súbor commit-graph urýchľuje prechádzanie históriou commitov a výpočet základov zlúčenia.

PHP
use Pitmaster\Pack\CommitGraph;

Nachádza sa v .git/objects/info/commit-graph a obsahuje:

  • OID commitov v zoradenom poradí
  • Informácie o rodičoch (indexované, bez potreby čítať objekty)
  • Generačné čísla (na rýchlejšie zisťovanie dosiahnuteľnosti)
  • Časové pečiatky commitov

Ak je súbor commit-graph dostupný, výpočet základu zlúčenia, ktorý vykonávajú Repository::merge(), mergeBase(), isBranchMerged() a kontrola zrýchleného posunu pri push, číta odkazy na rodičov z commit-graphu namiesto čítania jednotlivých objektov commitov. CommitWalker (log) ho nepoužíva.

Celé čísla s premenlivou dĺžkou

Súbory pack používajú niekoľko kódovaní celých čísel s premenlivou dĺžkou:

Varint Git (hlavičky typu a veľkosti)

Kódovanie s pokračovaním MSB, v ktorom najvýznamnejší bit označuje, či nasledujú ďalšie 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 delt)

Používa sa v hlavičkách pokynov delty na určenie veľkosti základu a výsledku:

PHP
use Pitmaster\Encoding\Leb128;

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

BinaryReader

Nízkoúrovňový bajtový prúd so sledovaním pozície:

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);