Hoppa till innehåll

Packfiler

Visa som Markdown Redigera på GitHub Dokumentation på bfe242f

Packfiler är gits mekanism för effektiv lagring och överföring. I stället för att lagra varje objekt som en separat zlib-komprimerad fil samlar packfiler många objekt i en enda fil med valfri deltacomprimering. Nästan alla klonade förråd använder packfiler.

Packfilens struktur

En packfil (.git/objects/pack/pack-{hash}.pack) innehåller:

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

Kodning av objekttyper

Varje post inleds med ett heltal med variabel längd där typen och storleken är sammanflätade:

Kod
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

Typvärden:

Värde Typ
1 Commit
2 Tree
3 Blob
4 Tag
6 OFS_DELTA (offsetbaserad delta)
7 REF_DELTA (hashbaserad delta)

Läsa packfiler

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

Klassen PackFile:

  1. Validerar huvudet PACK och versionsnumret
  2. Hittar offseten via filen .idx och tolkar postens varint för typ/storlek
  3. Dekomprimerar de zlib-komprimerade data
  4. För basobjekt: returnerar innehållet direkt
  5. För deltaobjekt: löser upp basen (följer kedjor) och tillämpar deltan samt cachelagrar lösta objekt

Packindexfiler

Varje fil av typen .pack har en motsvarande fil av typen .idx för snabba sökningar. Utan indexet krävs en genomsökning av hela packfilen för att hitta ett objekt.

v2-indexformat

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

Fanout-tabellen möjliggör O(log n) binärsökning: de 256 posterna anger hur många hashvärden som börjar med varje möjlig första byte.

v1-indexformat

Äldre format utan CRC32-kontrollsummor. Pitmaster stöder båda: PackIndex::open() läser en fil av typen v1 när v2-magin saknas, så samma kod fungerar för båda.

Deltaupplösning

Deltakodade objekt lagrar instruktioner för att återskapa innehåll från ett basobjekt i stället för att lagra hela innehållet. Det ger betydande komprimering för liknande objekt (e.g, till exempel flera versioner av samma fil efter varandra).

Deltatyper

OFS_DELTA (typ 6): basobjektet identifieras med en negativ offset i samma packfil. Detta är vanligare eftersom basobjektets hash inte behöver vara känd.

REF_DELTA (typ 7): basobjektet identifieras med sin hash. I git kan basen finnas utanför paketet (tunna paket). Pitmaster söker endast efter REF_DELTA-baser i samma paket, så tunna paket stöds inte (#16).

Deltainstruktioner

Deltainnehåll är en sekvens av kopierings- och infogningsinstruktioner:

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

Kopieringsinstruktioner: de 7 X-bitarna anger vilka byte för offset och storlek som finns. Offseten är upp till 4 byte och storleken upp till 3 byte. Om storleken är noll betyder det 0x10000 (65536) byte.

Infogningsinstruktioner: de 7 L-bitarna anger längden på literaldata (1–127 byte). L=0 är reserverat/ogiltigt.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

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

DeltaApplier:

  1. Läser förväntad basstorlek och resultatstorlek från deltahuvudet (LEB128-kodat)
  2. Går igenom instruktionerna:
    • Kopiera: hämtar offset och storlek och kopierar byte från basinnehållet
    • Infoga: hämtar längden och kopierar bokstavliga byte från deltadatan
  3. Verifierar att resultatstorleken motsvarar den förväntade storleken

Deltakedjor

Basobjektet för ett deltakodat objekt kan i sin tur vara deltakodat. PackFile::read() och readAtOffset() följer kedjan:

  1. Läs posten. Om den är av en bastyp (commit, tree, blob, tagg) returnerar du den.
  2. Om OFS_DELTA: beräkna basens offset (aktuell offset minus den kodade negativa offseten), läs basposten och anropa rekursivt.
  3. Om REF_DELTA: slå upp basen efter hash i samma packfils index och anropa rekursivt.
  4. Tillämpa deltainstruktionerna på den upplösta basen.
  5. Upprätthåll PITMASTER_MAX_DELTA_CHAIN (standardvärde 50) för att förhindra okontrollerat långa kedjor.
PHP
// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

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

PackWriter

Pitmaster kan skriva packfiler för nätverksåtgärder (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. Samlar objekten som ska ingå i packfilen
  2. Serialiserar varje objekt med ett varint-huvud för typ/storlek
  3. Komprimerar innehållet med zlib
  4. Skriver PACK-huvudet, posterna och SHA-1-trailern

Skriver för närvarande bara basobjekt (ingen deltacomprimering). Deltacomprimering är en optimering som kan läggas till senare; låt git gc packa om för effektiv lagring.

PackEnumerator

Iterera genom alla objekt i en packfil, i indexordning:

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

Varje post är ett upplöst GitObject.

MultiPackIndex

För förråd med många packfiler ger multi-pack-indexet (MIDX) en enda sökning över alla packfiler.

PHP
use Pitmaster\Pack\MultiPackIndex;

MIDX-filen (.git/objects/pack/multi-pack-index) innehåller:

  • En fanout-tabell (liknande packindex v2)
  • Objekt-ID:n sorterade över alla packfiler
  • Packfilnamn och packtilldelning per objekt
  • Offsetar i de enskilda packfilerna

MultiPackIndex::open($path) tolkar en MIDX-fil och erbjuder findObject($hex) och packNames(). Objektuppslagningar i förrådet använder den inte: objektdatabasen läser alltid de enskilda .idx-filerna.

CommitGraph

Commit-graph-filen snabbar upp genomgången av commit-historiken och beräkningen av gemensam förfader vid sammanslagning.

PHP
use Pitmaster\Pack\CommitGraph;

Den ligger i .git/objects/info/commit-graph och innehåller:

  • Commit-OID:n i sorterad ordning
  • Föräldrainformation (indexerad, utan att objekt behöver läsas)
  • Generationsnummer (för snabbare nåbarhetsfrågor)
  • Tidsstämplar för commits

När den finns läser beräkningen av gemensam förfader bakom Repository::merge(), mergeBase(), isBranchMerged() och pushens snabbspolningskontroll föräldralänkar från commit-graph-filen i stället för att läsa enskilda commit-objekt. CommitWalker (log) använder den inte.

Heltal med variabel längd

Packfiler använder flera kodningar för heltal med variabel längd:

Git-varint (huvuden för typ/storlek)

MSB-fortsättningskodning där den mest signifikanta biten anger att fler byte följer:

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 (deltahuvuden)

Används i deltans instruktionshuvuden för basstorlek och resultatstorlek:

PHP
use Pitmaster\Encoding\Leb128;

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

BinaryReader

Byte-ström på låg nivå med positionsspårning:

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