Pular para o conteúdo

Arquivos pack

Ver como Markdown Editar no GitHub Documentação em bfe242f

Arquivos pack são o mecanismo de git para armazenamento e transferência eficientes. Em vez de armazenar cada objeto como um arquivo zlib separado, os arquivos pack combinam muitos objetos em um único arquivo, com compactação delta opcional. Quase todos os repositórios clonados usam arquivos pack.

Estrutura do arquivo pack

Um arquivo pack (.git/objects/pack/pack-{hash}.pack) contém:

Código
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)

Codificação do tipo de objeto

Cada entrada começa com um inteiro de comprimento variável, no qual o tipo e o tamanho são intercalados:

Código
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

Valores de tipo:

Valor Tipo
1 Commit
2 Tree
3 Blob
4 Tag
6 OFS_DELTA (delta baseado em deslocamento)
7 REF_DELTA (delta baseado em hash)

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

A classe PackFile:

  1. Valida o cabeçalho PACK e o número da versão
  2. Encontra o deslocamento por meio do arquivo .idx e analisa o varint de tipo/tamanho da entrada
  3. Descompacta os dados compactados com zlib
  4. Para objetos base: retorna o conteúdo diretamente
  5. Para objetos delta: resolve a base (seguindo as cadeias) e aplica o delta, armazenando em cache os objetos resolvidos

Arquivos de índice pack

Todo arquivo .pack tem um arquivo .idx correspondente para consultas rápidas. Sem o índice, encontrar um objeto exige percorrer todo o pack.

Formato de índice v2

Código
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();

A tabela fanout permite uma pesquisa binária O(log n): as entradas 256 indicam quantos hashes começam com cada primeiro byte possível.

Formato de índice v1

Formato mais antigo sem somas de verificação CRC32. Pitmaster é compatível com ambos: PackIndex::open() lê um arquivo v1 quando a assinatura mágica v2 está ausente, para que o mesmo código funcione com qualquer um dos formatos.

Resolução de deltas

Objetos com delta armazenam instruções para reconstruir o conteúdo a partir de um objeto base, em vez de armazenar o conteúdo completo. Isso proporciona uma compactação significativa para objetos semelhantes (e.g, por exemplo, versões consecutivas do mesmo arquivo).

Tipos de delta

OFS_DELTA (tipo 6): o objeto base é identificado por um deslocamento negativo dentro do mesmo arquivo pack. É mais comum porque não exige conhecer o hash do objeto base.

REF_DELTA (tipo 7): o objeto base é identificado pelo hash. Em git, a base pode estar fora do pack (packs finos). Pitmaster procura bases REF_DELTA apenas dentro do mesmo pack, então não há suporte a packs finos (#16).

Instruções delta

O conteúdo delta é uma sequência de instruções de cópia e inserção:

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

Instruções de cópia: os 7 bits X indicam quais bytes de deslocamento e tamanho estão presentes. O deslocamento tem até 4 bytes e o tamanho, até 3 bytes. Se o tamanho for zero, significa 0x10000 (65536) bytes.

Instruções de inserção: os 7 bits L fornecem o comprimento dos dados literais (1-127 bytes). L=0 é reservado/inválido.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

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

O DeltaApplier:

  1. Lê o tamanho esperado da base e o tamanho do resultado do cabeçalho delta (codificados em LEB128)
  2. Percorre as instruções:
    • Cópia: extrai o deslocamento e o tamanho e copia bytes do conteúdo base
    • Inserção: extrai o comprimento e copia bytes literais dos dados delta
  3. Verifica se o tamanho do resultado corresponde ao tamanho esperado

Cadeias de delta

A base de um objeto com delta também pode ter delta. PackFile::read() e readAtOffset() percorrem a cadeia:

  1. Lê a entrada. Se for de um tipo base (commit, tree, blob, tag), retorna-a.
  2. Se for OFS_DELTA: calcula o deslocamento da base (deslocamento atual menos o deslocamento negativo codificado), lê a entrada base e repete recursivamente.
  3. Se for REF_DELTA: procura a base pelo hash no índice do mesmo pack e repete recursivamente.
  4. Aplica as instruções delta à base resolvida.
  5. Impõe PITMASTER_MAX_DELTA_CHAIN (padrão 50) para evitar cadeias excessivamente longas.
PHP
// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

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

PackWriter

Pitmaster pode gravar arquivos pack para operações de rede (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

O PackWriter:

  1. Reúne os objetos a incluir no pack
  2. Serializa cada objeto com um cabeçalho varint de tipo/tamanho
  3. Compacta o conteúdo com zlib
  4. Grava o cabeçalho PACK, as entradas e o rodapé SHA-1

Atualmente, grava apenas objetos base (sem compactação delta). A compactação delta é uma otimização que pode ser adicionada posteriormente; deixe git gc reempacotar para obter eficiência de armazenamento.

PackEnumerator

Percorrer todos os objetos em um pack, na ordem do índice:

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

Cada item é um GitObject resolvido.

MultiPackIndex

Para repositórios com muitos arquivos pack, o índice multipack (MIDX) oferece uma única consulta em todos os packs.

PHP
use Pitmaster\Pack\MultiPackIndex;

O arquivo MIDX (.git/objects/pack/multi-pack-index) contém:

  • Uma tabela fanout (como no índice pack v2)
  • IDs de objeto ordenados em todos os packs
  • Nomes dos arquivos pack e atribuições de pack por objeto
  • Deslocamentos nos arquivos pack individuais

MultiPackIndex::open($path) analisa um arquivo MIDX e oferece findObject($hex) e packNames(). As consultas de objetos no repositório não o utilizam: o banco de dados de objetos sempre lê os arquivos .idx individuais.

CommitGraph

O arquivo commit-graph acelera a navegação pelo histórico de commits e o cálculo da base de merge.

PHP
use Pitmaster\Pack\CommitGraph;

Localizado em .git/objects/info/commit-graph, ele contém:

  • OIDs de commit em ordem crescente
  • Informações dos pais (indexadas, sem necessidade de ler objetos)
  • Números de geração (para consultas de alcançabilidade mais rápidas)
  • Horários dos commits

Quando está presente, o cálculo da base de merge por trás de Repository::merge(), mergeBase(), isBranchMerged() e da verificação de avanço rápido do push lê os vínculos com os pais a partir do commit-graph, em vez de ler objetos de commit individuais. CommitWalker (log) não o utiliza.

Inteiros de comprimento variável

Os arquivos pack usam várias codificações de inteiros de comprimento variável:

Varint Git (cabeçalhos de tipo/tamanho)

Codificação de continuação por MSB, na qual o bit mais significativo indica que há mais bytes a seguir:

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 (cabeçalhos delta)

Usado nos cabeçalhos de instrução delta para o tamanho base e o tamanho do resultado:

PHP
use Pitmaster\Encoding\Leb128;

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

BinaryReader

Fluxo de bytes de baixo nível com rastreamento de posição:

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