Preskoči na vsebino

Datoteke Pack

Prikaži kot Markdown Uredi na GitHub Dokumentacija za bfe242f

Datoteke pack so mehanizem za učinkovito shranjevanje in prenos v git. Namesto da bi vsak objekt shranili kot ločeno datoteko, stisnjeno z zlib, datoteke pack združijo več objektov v eno datoteko z možnostjo delta stiskanja. Skoraj vsak kloniran repozitorij uporablja datoteke pack.

Struktura datoteke pack

Datoteka pack (.git/objects/pack/pack-{hash}.pack) vsebuje:

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

Kodiranje vrste objekta

Vsak vnos se začne s celoštevilskim zapisom spremenljive dolžine, v katerem se prepletata vrsta in velikost:

Koda
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

Vrednosti vrst:

Vrednost Vrsta
1 Commit
2 Tree
3 Blob
4 Oznaka
6 OFS_DELTA (delta na podlagi odmika)
7 REF_DELTA (delta na podlagi zgoščene vrednosti)

Branje datotek 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();

Razred PackFile:

  1. Preveri glavo PACK in številko različice
  2. V datoteki .idx poišče odmik ter razčleni zapis spremenljive dolžine za vrsto in velikost
  3. Razširi podatke, stisnjene z zlib
  4. Pri osnovnih objektih neposredno vrne vsebino
  5. Pri delta objektih razreši osnovo (po potrebi sledi verigam) in uporabi delto; razrešene objekte predpomni

Indeksne datoteke pack

Vsaka datoteka .pack ima ustrezno datoteko .idx za hitra iskanja. Brez indeksa je treba za iskanje objekta pregledati celotno datoteko pack.

Oblika indeksa v2

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

Tabela fanout omogoča binarno iskanje v O(log n): vnosi 256 povedo, koliko zgoščenih vrednosti se začne z vsakim možnim prvim bajtom.

Oblika indeksa v1

Starejša oblika brez kontrolnih vsot CRC32. Pitmaster podpira obe obliki: PackIndex::open() prebere datoteko v1, če manjka čarobna vrednost v2, zato ista koda deluje za obe.

Razreševanje delt

Objekti, zapisani z delto, hranijo navodila za obnovitev vsebine iz osnovnega objekta namesto celotne vsebine. To omogoča znatno stiskanje podobnih objektov (e.g, na primer zaporednih različic iste datoteke).

Vrste delt

OFS_DELTA (vrsta 6): osnovni objekt je določen z negativnim odmikom znotraj iste datoteke pack. Ta oblika je pogostejša, ker ni treba poznati zgoščene vrednosti osnovnega objekta.

REF_DELTA (vrsta 7): osnovni objekt je določen z njegovo zgoščeno vrednostjo. V git je lahko osnova zunaj datoteke pack (tanke datoteke pack). Pitmaster išče REF_DELTA osnove samo znotraj iste datoteke pack, zato tanke datoteke pack niso podprte (#16).

Navodila delte

Vsebina delte je zaporedje navodil za kopiranje in vstavljanje:

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

Navodila za kopiranje: 7 bitov X označuje, kateri bajti odmika in velikosti so prisotni. Odmik je dolg največ 4 bajte, velikost pa največ 3 bajte. Če je velikost nič, to pomeni 0x10000 (65536) bajtov.

Navodila za vstavljanje: 7 bitov L podaja dolžino dobesednih podatkov (1–127 bajtov). L=0 je rezervirano oziroma neveljavno.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

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

DeltaApplier:

  1. Iz glave delte (kodirane z LEB128) prebere pričakovano velikost osnove in velikost rezultata
  2. Ponavlja navodila:
    • Kopiranje: pridobi odmik in velikost ter kopira bajte iz vsebine osnove
    • Vstavljanje: pridobi dolžino ter kopira dobesedne bajte iz podatkov delte
  3. Preveri, ali se velikost rezultata ujema s pričakovano velikostjo

Verige delt

Osnovni objekt, zapisan z delto, je lahko sam zapisan z delto. PackFile::read() in readAtOffset() sledita verigi:

  1. Prebere vnos. Če gre za osnovno vrsto (commit, tree, blob, tag), ga vrne.
  2. Če je OFS_DELTA: izračuna odmik osnove (trenutni odmik minus kodirani negativni odmik), prebere osnovni vnos in rekurzivno nadaljuje.
  3. Če je REF_DELTA: v indeksu iste datoteke pack poišče osnovo po zgoščeni vrednosti in rekurzivno nadaljuje.
  4. Navodila delte uporabi za razrešeno osnovo.
  5. Uveljavi PITMASTER_MAX_DELTA_CHAIN (privzeto 50), da prepreči predolge verige.
PHP
// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

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

PackWriter

Pitmaster lahko zapisuje datoteke pack za omrežne operacije (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. Zbere objekte za vključitev v datoteko pack
  2. Serializira vsak objekt z glavo za vrsto in velikost v zapisu spremenljive dolžine
  3. Stisne vsebino z zlib
  4. Zapiše glavo PACK, vnose in zaključni podatek SHA-1

Trenutno zapisuje samo osnovne objekte (brez delta stiskanja). Delta stiskanje je optimizacija, ki jo je mogoče dodati pozneje; za učinkovitejše shranjevanje naj objekte preuredi git gc.

PackEnumerator

Pojdi skozi vse objekte v datoteki pack po vrstnem redu indeksa:

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";
}

Vsak element je razrešen GitObject.

MultiPackIndex

Za repozitorije z veliko datotekami pack večkratni indeks paketov (MIDX) omogoča skupno iskanje v vseh datotekah pack.

PHP
use Pitmaster\Pack\MultiPackIndex;

Datoteka MIDX (.git/objects/pack/multi-pack-index) vsebuje:

  • Tabelo fanout (podobno indeksu pack v2)
  • ID-je objektov, razvrščene med vsemi datotekami pack
  • Imena datotek pack in dodelitve datotek pack posameznim objektom
  • Odmike v posamezne datoteke pack

MultiPackIndex::open($path) razčleni datoteko MIDX ter omogoča findObject($hex) in packNames(). Iskanje objektov v repozitoriju je ne uporablja: zbirka objektov vedno bere posamezne datoteke .idx.

CommitGraph

Datoteka grafa commit pospeši pregledovanje zgodovine commitov in izračun osnovne točke za združevanje.

PHP
use Pitmaster\Pack\CommitGraph;

Datoteka je na lokaciji .git/objects/info/commit-graph in vsebuje:

  • ID-je commitov v razvrščenem vrstnem redu
  • Podatke o nadrejenih commitih (indeksirane, brez branja objektov)
  • Generacijske številke (za hitrejša preverjanja dosegljivosti)
  • Časovne oznake commitov

Če je datoteka prisotna, izračun osnovne točke za združevanje v ozadju Repository::merge(), mergeBase(), isBranchMerged() in preverjanja hitrega pomika pri pošiljanju bere povezave do nadrejenih commitov iz grafa commitov namesto posameznih objektov commit. CommitWalker (log) je ne uporablja.

Celoštevilski zapisi spremenljive dolžine

Datoteke pack uporabljajo več kodiranj celoštevilskih vrednosti spremenljive dolžine:

Zapis varint Git (glave vrste in velikosti)

Kodiranje MSB-continue, pri katerem najpomembnejši bit označuje, da sledijo dodatni bajti:

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 (glave delt)

Uporablja se v glavah navodil delte za velikost osnove in rezultata:

PHP
use Pitmaster\Encoding\Leb128;

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

BinaryReader

Nizkobitni tok bajtov s sledenjem položaju:

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