Zum Inhalt springen

Pack-Dateien

Als Markdown anzeigen Auf GitHub bearbeiten Dokumentation zu bfe242f

Pack-Dateien ermöglichen effiziente Speicherung und Übertragung in git. Statt jedes Objekt als separate zlib-komprimierte Datei abzulegen, fassen sie viele Objekte in einer Datei zusammen und können sie optional per Delta-Komprimierung speichern. Fast jedes geklonte Repository verwendet Pack-Dateien.

Aufbau einer Pack-Datei

Eine Pack-Datei (.git/objects/pack/pack-{hash}.pack) enthält:

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

Kodierung des Objekttyps

Jeder Eintrag beginnt mit einer Ganzzahl variabler Länge, in der Typ und Größe ineinander verschachtelt sind:

Code
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

Typwerte:

Wert Typ
1 Commit
2 Tree
3 Blob
4 Tag
6 OFS_DELTA (Delta auf Offsetbasis)
7 REF_DELTA (Hash-basiertes Delta)

Pack-Dateien lesen

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

Die Klasse PackFile:

  1. Validiert den PACK-Header und die Versionsnummer
  2. Ermittelt den Offset über die .idx-Datei und liest den Varint für Typ und Größe des Eintrags
  3. Dekomprimiert die zlib-komprimierten Daten
  4. Gibt bei Basisobjekten den Inhalt direkt zurück
  5. Löst bei Delta-Objekten das Basisobjekt auf (auch über Ketten hinweg), wendet das Delta an und speichert aufgelöste Objekte im Cache

Pack-Indexdateien

Zu jeder .pack-Datei gehört eine .idx-Datei für schnelle Suchvorgänge. Ohne den Index müsste zum Auffinden eines Objekts das gesamte Pack durchsucht werden.

Indexformat v2

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

Die Fan-out-Tabelle ermöglicht eine binäre Suche in O(log n): Die 256 Einträge geben an, wie viele Hashes mit dem jeweiligen möglichen ersten Byte beginnen.

Indexformat v1

Älteres Format ohne CRC32-Prüfsummen. Pitmaster unterstützt beide Formate: PackIndex::open() liest eine v1-Datei, wenn die v2-Magic Number fehlt, sodass derselbe Code mit beiden Formaten funktioniert.

Delta-Auflösung

Delta-Objekte speichern Anweisungen, mit denen sich der Inhalt aus einem Basisobjekt rekonstruieren lässt, statt den vollständigen Inhalt zu speichern. Das spart bei ähnlichen Objekten erheblich Speicherplatz (e.g. aufeinanderfolgende Versionen derselben Datei).

Delta-Typen

OFS_DELTA (Typ 6): Das Basisobjekt wird durch einen negativen Offset innerhalb derselben Pack-Datei identifiziert. Dieser Typ ist häufiger, da der Hash des Basisobjekts nicht bekannt sein muss.

REF_DELTA (Typ 7): Das Basisobjekt wird durch seinen Hash identifiziert. In git kann sich das Basisobjekt außerhalb des Packs befinden (Thin Packs). Pitmaster sucht REF_DELTA-Basisobjekte nur im selben Pack, daher werden Thin Packs nicht unterstützt (#16).

Delta-Anweisungen

Delta-Inhalte bestehen aus einer Folge von Kopier- und Einfügeanweisungen:

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

Kopieranweisungen: Die 7 X-Bits geben an, welche Offset- und Größenbytes vorhanden sind. Der Offset ist bis zu 4 Bytes lang, die Größe bis zu 3 Bytes. Ist die Größe null, steht sie für 0x10000 (65536) Bytes.

Einfügeanweisungen: Die 7 L-Bits geben die Länge der literalen Daten an (1-127 Bytes). L=0 ist reserviert und ungültig.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

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

Der DeltaApplier:

  1. Liest die erwartete Basisgröße und Ergebnisgröße aus dem Delta-Header (LEB128-kodiert)
  2. Durchläuft die Anweisungen:
    • Kopieren: Ermittelt Offset und Größe und kopiert Bytes aus dem Basisinhalt
    • Einfügen: Ermittelt die Länge und kopiert literale Bytes aus den Delta-Daten
  3. Prüft, ob die Ergebnisgröße der erwarteten Größe entspricht

Delta-Ketten

Das Basisobjekt eines Delta-Objekts kann selbst ein Delta-Objekt sein. PackFile::read() und readAtOffset() verfolgen die Kette:

  1. Liest den Eintrag. Ist er ein Basistyp (Commit, Tree, Blob, Tag), wird er zurückgegeben.
  2. Bei OFS_DELTA: Berechnet den Basis-Offset (aktueller Offset minus kodierter negativer Offset), liest den Basiseintrag und ruft sich rekursiv auf.
  3. Bei REF_DELTA: Sucht das Basisobjekt anhand des Hashes im Index desselben Packs und ruft sich rekursiv auf.
  4. Wendet die Delta-Anweisungen auf das aufgelöste Basisobjekt an.
  5. Erzwingt PITMASTER_MAX_DELTA_CHAIN (standardmäßig 50), um endlose Ketten zu verhindern.
PHP
// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

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

PackWriter

Pitmaster kann Pack-Dateien für Netzwerkoperationen (Push) schreiben.

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

Der PackWriter:

  1. Sammelt die ins Pack aufzunehmenden Objekte
  2. Serialisiert jedes Objekt mit einem Varint-Header für Typ und Größe
  3. Komprimiert den Inhalt mit zlib
  4. Schreibt den PACK-Header, die Einträge und den SHA-1-Trailer

Derzeit werden nur Basisobjekte geschrieben (ohne Delta-Komprimierung). Delta-Komprimierung ist eine Optimierung, die später ergänzt werden kann; für effiziente Speicherung kann git gc ein neues Pack erstellen.

PackEnumerator

Alle Objekte eines Packs in Indexreihenfolge durchlaufen:

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

Jedes Element ist ein aufgelöstes GitObject.

MultiPackIndex

Bei Repositorys mit vielen Pack-Dateien ermöglicht der Multi-Pack-Index (MIDX eine einzige Suche über alle Packs hinweg.

PHP
use Pitmaster\Pack\MultiPackIndex;

Die MIDX-Datei (.git/objects/pack/multi-pack-index) enthält:

  • Eine Fan-out-Tabelle (wie bei Pack-Index v2)
  • Objekt-IDs, sortiert über alle Packs hinweg
  • Pack-Dateinamen und Pack-Zuordnungen pro Objekt
  • Offsets in den einzelnen Pack-Dateien

MultiPackIndex::open($path) liest eine MIDX-Datei ein und stellt findObject($hex) und packNames() bereit. Objekte im Repository werden nicht darüber gesucht: Die Objektdatenbank liest immer die einzelnen .idx-Dateien.

CommitGraph

Die Commit-Graph-Datei beschleunigt das Durchlaufen der Commit-Historie und die Berechnung der Merge-Basis.

PHP
use Pitmaster\Pack\CommitGraph;

Sie befindet sich unter .git/objects/info/commit-graph und enthält:

  • Commit-OIDs in sortierter Reihenfolge
  • Informationen zu Eltern-Commits (indiziert, ohne Objekte lesen zu müssen)
  • Generationsnummern (für schnellere Erreichbarkeitsabfragen)
  • Commit-Zeitstempel

Wenn eine Commit-Graph-Datei vorhanden ist, liest die Berechnung der Merge-Basis hinter Repository::merge(), mergeBase(), isBranchMerged() und der Push-Fast-Forward-Prüfung die Elternverknüpfungen aus dem Commit-Graph statt einzelne Commit-Objekte zu lesen. CommitWalker (Log) verwendet sie nicht.

Ganzzahlen variabler Länge

Pack-Dateien verwenden mehrere Kodierungen für Ganzzahlen variabler Länge:

Git-Varint (Typ-/Größen-Header)

MSB-Fortsetzungskodierung, bei der das höchstwertige Bit anzeigt, dass weitere Bytes folgen:

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 (Delta-Header)

Wird in Delta-Anweisungs-Headern für Basis- und Ergebnisgröße verwendet:

PHP
use Pitmaster\Encoding\Leb128;

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

BinaryReader

Byte-Stream auf niedriger Ebene mit Positionsverfolgung:

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