Към съдържанието

Pack файлове

Преглед като Markdown Редактиране в GitHub Документация за bfe242f

Pack файловете са механизмът на git за ефективно съхранение и прехвърляне. Вместо всеки обект да се съхранява в отделен компресиран със zlib файл, pack файловете обединяват множество обекти в един файл с незадължително delta компресиране. Почти всяко клонирано хранилище използва pack файлове.

Структура на pack файл

Pack файл (.git/objects/pack/pack-{hash}.pack) съдържа:

Код
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)

Кодиране на типа обект

Всеки запис започва с цяло число с променлива дължина, в което типът и размерът са преплетени:

Код
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

Стойности на типовете:

Стойност Тип
1 Commit
2 Tree
3 Blob
4 Tag
6 OFS_DELTA (delta, базирано на отместване)
7 REF_DELTA (delta, базирано на хеш)

Четене на 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();

Класът PackFile:

  1. Проверява заглавната част и номера на версията на PACK
  2. Намира отместването чрез файла .idx и анализира varint-а за тип/размер на записа
  3. Декомпресира данните, компресирани със zlib
  4. За базови обекти: връща съдържанието директно
  5. За delta обекти: разрешава базата (следвайки веригите) и прилага delta, като кешира разрешените обекти

Индексни файлове на pack

Всеки файл .pack има съответстващ файл .idx за бързо търсене. Без индекса намирането на обект изисква сканиране на целия pack.

Формат на индекс v2

Код
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 позволява двоично търсене O(log n): записите 256 показват колко хеша започват с всеки възможен първи байт.

Формат на индекс v1

По-стар формат без контролни суми CRC32. Pitmaster поддържа и двата формата: PackIndex::open() чете файл v1, когато липсва магическата стойност v2, така че един и същ код работи и с двата.

Разрешаване на delta

Delta обектите съхраняват инструкции за възстановяване на съдържанието от базов обект, вместо да пазят цялото съдържание. Така се постига значително компресиране при сходни обекти (e.g., последователни версии на един и същ файл).

Типове delta

OFS_DELTA (тип 6): базовият обект се идентифицира чрез отрицателно отместване в същия pack файл. По-разпространен е, защото не изисква познаване на хеша на базовия обект.

REF_DELTA (тип 7): базовият обект се идентифицира чрез хеша си. В git базата може да се намира извън pack файла (тънки pack файлове). Pitmaster търси базите на REF_DELTA само в същия pack файл, затова тънките pack файлове не се поддържат (#16).

Инструкции за delta

Съдържанието на delta е поредица от инструкции за копиране и вмъкване:

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

Инструкции за копиране: 7-те бита X показват кои байтове за отместване и размер присъстват. Отместването е до 4 байта, а размерът — до 3 байта. Ако размерът е нула, това означава 0x10000 (65536) байта.

Инструкции за вмъкване: 7-те L бита задават дължината на литералните данни (1-127 байта). L=0 е запазена/невалидна стойност.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

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

DeltaApplier:

  1. Чете очаквания размер на базата и размера на резултата от заглавната част на delta (кодирани с LEB128)
  2. Изпълнява инструкциите последователно:
    • Копиране: извлича отместването и размера и копира байтовете от съдържанието на базата
    • Вмъкване: извлича дължината и копира литералните байтове от данните на delta
  3. Проверява дали размерът на резултата съвпада с очаквания размер

Вериги delta

Базовият обект на delta обект може сам да бъде delta обект. PackFile::read() и readAtOffset() следват веригата:

  1. Прочита записа. Ако е от базов тип (commit, tree, blob, tag), го връща.
  2. За OFS_DELTA: изчислява отместването на базата (текущото отместване минус кодираната отрицателна стойност), чете базовия запис и повтаря рекурсивно.
  3. За REF_DELTA: търси базата по хеш в индекса на същия pack файл и повтаря рекурсивно.
  4. Прилага инструкциите на delta върху разрешената база.
  5. Прилага ограничение PITMASTER_MAX_DELTA_CHAIN (по подразбиране 50), за да предотврати прекалено дълги вериги.
PHP
// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

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

PackWriter

Pitmaster може да записва pack файлове за мрежови операции (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. Събира обектите за включване в pack файла
  2. Сериализира всеки обект със заглавка varint за тип/размер
  3. Компресира съдържанието със zlib
  4. Записва заглавката PACK, записите и крайния запис SHA-1

Понастоящем записва само базови обекти (без delta компресиране). Delta компресирането е оптимизация, която може да бъде добавена по-късно; оставете git gc да препакетира обектите за по-ефективно съхранение.

PackEnumerator

Обхожда всички обекти в pack файла, в реда на индекса:

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

Всеки елемент е разрешен GitObject.

MultiPackIndex

За хранилища с много pack файлове MultiPackIndex (MIDX) осигурява общо търсене във всички тях.

PHP
use Pitmaster\Pack\MultiPackIndex;

Файлът MIDX (.git/objects/pack/multi-pack-index) съдържа:

  • Таблица fanout (като в индекса на pack v2)
  • Object ID, сортирани във всички pack файлове
  • Имена на pack файловете и зададен pack файл за всеки обект
  • Отмествания във всеки от отделните pack файлове

MultiPackIndex::open($path) анализира MIDX файл и предоставя findObject($hex) и packNames(). Търсенето на обекти в хранилището не го използва: базата от обекти винаги чете отделните файлове .idx.

CommitGraph

Файлът commit-graph ускорява обхождането на историята на commit-ите и изчисляването на базата за сливане.

PHP
use Pitmaster\Pack\CommitGraph;

Намира се в .git/objects/info/commit-graph и съдържа:

  • OID на commit-ите, сортирани по ред
  • Информация за родителите (индексирана, без нужда от четене на обектите)
  • Номера на поколенията (за по-бързи заявки за достижимост)
  • Времеви маркери на commit-ите

Когато е налично, изчисляването на базовия общ комит зад Repository::merge(), mergeBase(), isBranchMerged() и проверката за fast-forward при push чете връзките към родителските комити от commit-graph, вместо да чете отделните обекти на комитите. CommitWalker (log) не го използва.

Цели числа с променлива дължина

Файловете pack използват няколко кодирания за цели числа с променлива дължина:

Git varint (заглавки на тип/размер)

Кодиране с продължение чрез MSB, при което най-значимият бит показва, че следват още байтове:

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)

Използва се в заглавките на delta инструкциите за базовия размер и размера на резултата:

PHP
use Pitmaster\Encoding\Leb128;

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

BinaryReader

Ниско ниво на потока от байтове с проследяване на позицията:

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