Перейти до вмісту

Pack-файли

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

Pack-файли — механізм git для ефективного зберігання та передавання даних. Замість зберігання кожного об'єкта в окремому стисненому файлі zlib, pack-файли об'єднують багато об'єктів в один файл із необов'язковим дельта-стисненням. Майже всі клоновані репозиторії використовують 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 (дельта за зміщенням)
7 REF_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. Для дельта-об'єктів розв'язує посилання на базовий об'єкт (проходячи ланцюжки) і застосовує дельту, кешуючи розв'язані об'єкти

Файли індексу 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();

Таблиця розгалужень дає змогу виконувати двійковий пошук O(log n): записи 256 вказують, скільки хешів починаються з кожного можливого першого байта.

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

Старіший формат без контрольних сум CRC32. Pitmaster підтримує обидва формати: PackIndex::open() читає файл v1, якщо відсутній магічний номер v2, тож той самий код працює з обома.

Розв'язання дельт

Дельта-об'єкти зберігають інструкції для відновлення вмісту з базового об'єкта замість повного вмісту. Це забезпечує значне стиснення схожих об'єктів (e.g., послідовних версій того самого файлу).

Типи дельт

OFS_DELTA (тип 6): базовий об'єкт визначається від'ємним зміщенням у тому самому pack-файлі. Такий тип поширеніший, бо не потребує знання хешу базового об'єкта.

REF_DELTA (тип 7): базовий об'єкт визначається за його хешем. У git базовий об'єкт може зберігатися поза pack-файлом (тонкі pack-файли). Pitmaster шукає REF_DELTA базові об'єкти лише в тому самому pack-файлі, тому тонкі pack-файли не підтримуються (#16).

Інструкції дельти

Вміст дельти — це послідовність інструкцій копіювання та вставлення:

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

Вказівки копіювання: 7 бітів X позначають, які байти зміщення та розміру присутні. Зміщення займає до 4 байтів, розмір — до 3 байтів. Якщо розмір дорівнює нулю, це означає 65536 байтів (0x10000).

Вказівки вставлення: 7 бітів L задають довжину літеральних даних (1-127 байтів). L=0 зарезервовано й недійсне.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

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

DeltaApplier:

  1. Читає очікувані розмір базового об'єкта та розмір результату із заголовка дельти (у кодуванні LEB128)
  2. Перебирає інструкції:
    • Копіювання: отримує зміщення й розмір та копіює байти з базового вмісту
    • Вставлення: отримує довжину й копіює літеральні байти з даних дельти
  3. Перевіряє, чи відповідає розмір результату очікуваному

Ланцюжки дельт

Базовий об'єкт дельта-об'єкта сам може бути дельта-об'єктом. PackFile::read() і readAtOffset() проходять цей ланцюжок:

  1. Читає запис. Якщо це базовий тип (commit, tree, blob, tag), повертає його.
  2. Якщо OFS_DELTA: обчислює зміщення базового об'єкта (поточне зміщення мінус закодоване від'ємне зміщення), читає базовий запис і переходить до нього рекурсивно.
  3. Якщо REF_DELTA: шукає базовий об'єкт за хешем в індексі того самого pack-файлу й переходить до нього рекурсивно.
  4. Застосовує інструкції дельти до розв'язаного базового об'єкта.
  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

Наразі записуються лише базові об'єкти (без дельта-стиснення). Дельта-стиснення можна додати пізніше як оптимізацію; для ефективнішого зберігання дозвольте 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-файлами multi-pack-index (MIDX) забезпечує єдиний пошук в усіх pack-файлах.

PHP
use Pitmaster\Pack\MultiPackIndex;

Файл MIDX (.git/objects/pack/multi-pack-index) містить:

  • Таблицю розгалужень (як в індексі pack v2)
  • ID об'єктів, відсортовані для всіх pack-файлів
  • Назви pack-файлів і призначення кожного об'єкта відповідному pack-файлу
  • Зміщення в окремих pack-файлах

MultiPackIndex::open($path) розбирає файл MIDX і надає findObject($hex) та packNames(). Пошук об'єктів у репозиторії ним не користується: база об'єктів завжди читає окремі файли .idx.

CommitGraph

Файл commit-graph прискорює обхід історії комітів і обчислення бази злиття.

PHP
use Pitmaster\Pack\CommitGraph;

Розташований у .git/objects/info/commit-graph, він містить:

  • OID комітів у відсортованому порядку
  • Інформацію про батьків (індексовану, без потреби читати об'єкти)
  • Номери генерації (для швидших запитів щодо досяжності)
  • Часові позначки комітів

Коли цей файл наявний, обчислення бази злиття для Repository::merge(), mergeBase(), isBranchMerged() і перевірки перемотування вперед під час push читає посилання на батьків із commit-graph, а не окремі об'єкти комітів. CommitWalker (log) його не використовує.

Цілі числа змінної довжини

У pack-файлах використовуються різні кодування цілих чисел змінної довжини:

Varint Git (заголовки типу/розміру)

Кодування з продовженням у старшому біті: старший біт указує, що за ним ідуть додаткові байти:

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 для базового розміру та розміру результату:

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