packfile

Packfile Parser

This package provides efficient extraction of commit OIDs from Git packfiles stored in object storage (S3, GCS, etc.) using range requests to minimize data transfer and costs.

Overview

The BlobStorePackfileParser extracts commit OIDs from packfiles without downloading the entire file. It uses an iterative algorithm with batched range requests to resolve delta chains efficiently.

Problem Statement

Git packfiles can be large (gigabytes) and contain thousands of objects. To identify which objects are commits, we need to:

1. Parse the packfile index (.idx) to get object offsets
2. Read object headers from the packfile (.pack) to determine types
3. Resolve delta objects (OFS_DELTA, REF_DELTA) to their base types

Downloading entire packfiles would be slow and expensive. This parser minimizes data transfer by:

• Using HTTP range requests to fetch only necessary byte ranges
• Batching objects into efficient 5MB clusters
• Resolving deltas iteratively within fetched ranges

Architecture

Key Components

1. OID Type (oid.go)

   • Binary representation of Git object identifiers
   • 20 bytes for SHA-1, 32 bytes for SHA-256
   • 50% memory savings vs hex strings
   • JSON marshaling with hex encoding

2. BlobStorePackfileParser (parser.go)

   • Main parser that coordinates the resolution process
   • Uses Go Cloud CDK blob.Bucket for storage abstraction
   • Configurable max iterations for DoS protection

Data Structures

// workItem represents an object that needs to be resolved
type workItem struct {
    hash   plumbing.Hash
    offset int64
}

// offsetRange represents a contiguous byte range to fetch
type offsetRange struct {
    start int64
    end   int64
    items []workItem
}

Algorithm

The parser uses an iterative work queue algorithm with delta resolution:

Phase 1: Index Parsing

Read packfile.idx
  ↓
Extract all [hash, offset] pairs
  ↓
Initialize workQueue with all objects

Phase 2: Iterative Resolution

WHILE workQueue is not empty AND iterations < maxIterations:

    1. CLUSTER: Group work items by proximity
       ├─ Sort by offset
       ├─ Group objects within 100KB gaps
       └─ Cap each cluster at 5MB

    2. FETCH: For each cluster
       ├─ HTTP Range request: [start, end)
       └─ Read cluster data into memory

    3. RESOLVE: For each object in cluster
       ├─ Parse object header
       ├─ IF direct type (commit/tree/blob/tag)
       │    └─ Mark as resolved
       ├─ ELSE IF delta type
       │    ├─ IF base is in current range
       │    │    └─ Recursively resolve within range
       │    └─ ELSE
       │         └─ Add base to workQueue
       └─ Continue to next object

    4. ITERATE: Process unresolved items in next iteration

Phase 3: Collection

Filter resolved objects
  ↓
Return all commits

Delta Resolution Strategy

Git packfiles use delta compression to save space. A delta object stores only the differences from a base object.

Delta Types

1. OFS_DELTA (type 6)

   • References base by negative offset
   • Example: Object at offset 5000 might reference base at offset 4500
   • Requires reverse hash lookup: offset → hash

2. REF_DELTA (type 7)

   • References base by SHA-1 hash
   • Example: Delta directly specifies base hash
   • Requires forward lookup: hash → offset

Resolution Within Ranges

When a delta and its base are in the same fetched range:

Range: [1000, 6000)
├─ Object A at 1500 (commit) ────────┐
├─ Object B at 3000 (OFS_DELTA) ─────┤ base at 1500
│    └─ Resolve: B inherits type from A
└─ Object C at 5000 (direct commit)

Result: Both A and C are commits (resolved in one iteration)

Resolution Across Ranges

When a delta's base is outside the current range:

Iteration 1:
Range: [5000, 10000)
└─ Object D at 6000 (OFS_DELTA, base at 2000)
   └─ Add base to workQueue

Iteration 2:
Range: [2000, 7000)
├─ Object E at 2000 (commit) ← base for D
└─ Object D at 6000 (now in range)
   └─ Resolve: D inherits type from E

Result: D is a commit (resolved in two iterations)

Clustering Strategy

Objects are grouped to minimize HTTP requests while respecting size limits:

const (
    maxClusterSize = 5 * 1024 * 1024  // 5MB max per range
    minClusterSize = 256 * 1024        // 256KB min per object
    maxGap         = 100 * 1024        // 100KB gap threshold
)

Clustering Rules

1. Sort by offset: Process objects in packfile order
2. Group nearby objects: Combine if gap < 100KB
3. Respect size limit: Split if cluster would exceed 5MB
4. Minimum read size: Read at least 256KB per object

Example Clustering

Objects:     A      B       C            D
Offsets:   [100] [500]  [1000]       [200000]
            └─────┬─────┘              └──────┘
              Cluster 1                Cluster 2
            Gap: 400B, 500B           Gap: 199KB
            Size: ~1KB                Size: ~256KB

Performance Characteristics

Best Case (No Deltas or Shallow Chains)

• Iterations: 1
• Range Requests: 20-50 for 10,000 objects
• Data Transfer: ~100-250MB for large repos

Typical Case (30-40% Deltas, Depth 1-2)

• Iterations: 2-3
• Range Requests: 30-70 for 10,000 objects
• First iteration: Resolves ~80-90% of objects
• Second iteration: Resolves remaining dependencies
• Data Transfer: ~150-350MB for large repos

Worst Case (Deep, Scattered Delta Chains)

• Iterations: 4-5 (limited by maxIterations)
• Range Requests: 100+ for pathological cases
• Data Transfer: ~500MB+ for adversarial packfiles

Comparison to Alternatives

Security Considerations

DoS Protection

The parser includes configurable iteration limits to prevent DoS attacks:

const defaultMaxIterations = 100

Attack Vector: Adversarial packfile with circular or pathological delta chains

• Delta A references base B
• Delta B references base C
• Delta C references base A (cycle)
• OR: Very deep chain (A→B→C→D→...→Z)

Mitigation:

• Limit maximum iterations to 100 (default)
• Return error if exceeded
• Configurable via WithMaxIterations()

Trade-offs

• Lower limit (e.g., 10): More DoS protection, may fail on legitimate complex packfiles
• Higher limit (e.g., 200): Allows complex packfiles, increases vulnerability
• Default (100): Balances security and functionality

Usage

Basic Usage

// Open bucket
bucket, _ := blob.OpenBucket(ctx, "s3://my-bucket?region=us-west-2")
defer bucket.Close()

// Create parser and extract commits
parser := packfile.NewBlobStorePackfileParser(bucket)
commits, err := parser.ExtractCommitOIDs(ctx, "pack-abc.pack", "pack-abc.idx")

With Custom Iteration Limit

// Stricter DoS protection
parser := packfile.NewBlobStorePackfileParser(bucket).WithMaxIterations(50)

// More permissive for trusted packfiles
parser := packfile.NewBlobStorePackfileParser(bucket).WithMaxIterations(200)

Implementation Details

Object Header Parsing

Git packfile object headers encode type and size:

Byte 0: MTTT SSSS
  M = MSB (more bytes follow)
  T = Type (3 bits)
  S = Size (4 bits)

Types:
  1 = Commit
  2 = Tree
  3 = Blob
  4 = Tag
  6 = OFS_DELTA
  7 = REF_DELTA

OFS_DELTA Offset Encoding

Negative offset uses variable-length encoding:

First byte:  0VVV VVVV (V = offset bits)
More bytes:  1VVV VVVV (continue)
Last byte:   0VVV VVVV (done)

Decode:
  offset = firstByte & 0x7F
  while (byte & 0x80):
      offset = ((offset + 1) << 7) | (byte & 0x7F)
  baseOffset = currentOffset - offset

REF_DELTA Hash Encoding

Base hash is stored directly as 20 bytes (SHA-1) following the object header.

Future Improvements

Potential optimizations:

1. Reverse index cache: Pre-build offset→hash map for O(1) lookups
2. Parallel fetching: Fetch multiple ranges concurrently
3. Adaptive clustering: Adjust cluster size based on packfile structure
4. Delta chain depth limit: Additional DoS protection per-chain
5. Metrics: Track iterations, range requests, data transfer

References

• Git Packfile Format
• Git Index Format
• Go Cloud CDK Blob
• HTTP Range Requests (RFC 7233)