1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "bytes"
7 "encoding/binary"
8 "io"
9 "os"
10 "sync/atomic"
11)
12
13const (
14 packHeaderLen = 12
15 packTrailerLen = 20
16
17 objOfsDelta = 6
18 objRefDelta = 7
19)
20
21// pack is an open pack file with its index, both mapped read-only. It is
22// shared by the snapshots that list it and unmapped when the last one is
23// released.
24type pack struct {
25 id uint32
26 name string // "pack-<hash>", without extension
27 idx *idxFile
28 data []byte // the whole .pack file
29 sig fileSig
30 unmap [2]func() error
31 refs atomic.Int32
32
33 hdrs atomic.Pointer[headerCache] // created by the first deltified header
34}
35
36func (p *pack) retain() { p.refs.Add(1) }
37
38func (p *pack) release() {
39 if p.refs.Add(-1) == 0 {
40 for _, f := range p.unmap {
41 if f != nil {
42 _ = f()
43 }
44 }
45 p.data, p.idx = nil, nil
46 }
47}
48
49// openPack maps and validates dir/<name>.idx and dir/<name>.pack. It returns
50// (nil, nil) when a file vanished, which happens while a repack replaces it.
51func openPack(dir, name string, id uint32, sig fileSig) (*pack, error) {
52 idxF, err := os.Open(dir + "/" + name + ".idx")
53 if err != nil {
54 return nil, ignoreMissing(err)
55 }
56 defer func() { _ = idxF.Close() }()
57 packF, err := os.Open(dir + "/" + name + ".pack")
58 if err != nil {
59 return nil, ignoreMissing(err)
60 }
61 defer func() { _ = packF.Close() }()
62 idxStat, err := idxF.Stat()
63 if err != nil {
64 return nil, err
65 }
66 packStat, err := packF.Stat()
67 if err != nil {
68 return nil, err
69 }
70 idxData, unmapIdx, err := mapFile(idxF, idxStat.Size())
71 if err != nil {
72 return nil, err
73 }
74 packData, unmapPack, err := mapFile(packF, packStat.Size())
75 if err != nil {
76 _ = unmapIdx()
77 return nil, err
78 }
79 p := &pack{id: id, name: name, data: packData, sig: sig, unmap: [2]func() error{unmapIdx, unmapPack}}
80 p.refs.Store(1)
81 if p.idx, err = parseIdx(idxData); err != nil {
82 p.release()
83 return nil, wrapPack(name, err)
84 }
85 if err := p.validate(); err != nil {
86 p.release()
87 return nil, wrapPack(name, err)
88 }
89 return p, nil
90}
91
92// validate checks the pack header and ties the pack to its index.
93func (p *pack) validate() error {
94 if len(p.data) < packHeaderLen+packTrailerLen {
95 return corrupt("pack too short (%d bytes)", len(p.data))
96 }
97 if string(p.data[:4]) != "PACK" {
98 return corrupt("bad pack signature")
99 }
100 if v := binary.BigEndian.Uint32(p.data[4:8]); v != 2 && v != 3 {
101 return corrupt("pack version %d", v)
102 }
103 if n := binary.BigEndian.Uint32(p.data[8:12]); n != p.idx.n {
104 return corrupt("pack holds %d objects, index %d", n, p.idx.n)
105 }
106 if !bytes.Equal(p.data[len(p.data)-packTrailerLen:], p.idx.packHash) {
107 return corrupt("pack checksum differs from its index")
108 }
109 return nil
110}
111
112func wrapPack(name string, err error) error {
113 return &packError{name: name, err: err}
114}
115
116type packError struct {
117 name string
118 err error
119}
120
121func (e *packError) Error() string { return e.name + ": " + e.err.Error() }
122func (e *packError) Unwrap() error { return e.err }
123
124// entryHdr is a parsed pack entry header.
125type entryHdr struct {
126 typ uint8 // 1..4, objOfsDelta or objRefDelta
127 size uint64 // inflated size of the entry data (the delta for deltas)
128 data uint64 // offset of the zlib stream
129 baseOff uint64 // objOfsDelta: absolute offset of the base
130 baseID ObjectID
131}
132
133func (h *entryHdr) isDelta() bool { return h.typ == objOfsDelta || h.typ == objRefDelta }
134
135// parseEntryHeader parses the header of the entry at off in a whole pack
136// file (header, entries and trailer). It never reads outside data.
137func parseEntryHeader(data []byte, off uint64) (h entryHdr, err error) {
138 end := uint64(len(data))
139 if end < packHeaderLen+packTrailerLen {
140 return h, corrupt("pack too short")
141 }
142 end -= packTrailerLen
143 if off < packHeaderLen || off >= end {
144 return h, corrupt("entry offset %d outside pack", off)
145 }
146 p := off
147 c := data[p]
148 p++
149 h.typ = (c >> 4) & 7
150 h.size = uint64(c & 0x0f)
151 for shift := uint(4); c&0x80 != 0; shift += 7 {
152 if p >= end || shift > 56 {
153 return h, corrupt("bad entry size at %d", off)
154 }
155 c = data[p]
156 p++
157 h.size |= uint64(c&0x7f) << shift
158 }
159 switch h.typ {
160 case uint8(TypeCommit), uint8(TypeTree), uint8(TypeBlob), uint8(TypeTag):
161 case objOfsDelta:
162 if p >= end {
163 return h, corrupt("truncated delta offset at %d", off)
164 }
165 c = data[p]
166 p++
167 rel := uint64(c & 0x7f)
168 for c&0x80 != 0 {
169 if p >= end || rel >= 1<<56 {
170 return h, corrupt("bad delta offset at %d", off)
171 }
172 c = data[p]
173 p++
174 rel = (rel+1)<<7 | uint64(c&0x7f)
175 }
176 if rel == 0 || rel > off-packHeaderLen {
177 return h, corrupt("delta base offset %d outside pack at %d", rel, off)
178 }
179 h.baseOff = off - rel
180 case objRefDelta:
181 if end-p < 20 {
182 return h, corrupt("truncated delta base id at %d", off)
183 }
184 copy(h.baseID[:], data[p:p+20])
185 p += 20
186 default:
187 return h, corrupt("entry type %d at %d", h.typ, off)
188 }
189 if p >= end {
190 return h, corrupt("entry at %d has no data", off)
191 }
192 h.data = p
193 return h, nil
194}
195
196// stream returns the compressed bytes of the entry.
197func (p *pack) stream(h *entryHdr) []byte {
198 return p.data[h.data : len(p.data)-packTrailerLen]
199}
200
201// inflateEntry inflates the entry data into dst, which has the exact size
202// announced by the header.
203func (p *pack) inflateEntry(h *entryHdr, dst []byte) error {
204 src := p.stream(h)
205 // Deflate cannot expand a byte into more than 1032 bytes.
206 if h.size/1032 > uint64(len(src)) {
207 return corrupt("entry of %d bytes in %d compressed bytes", h.size, len(src))
208 }
209 m, err := getMem(src)
210 if err != nil {
211 return err
212 }
213 defer putMem(m)
214 return inflateExact(&m.zr, dst, m.scratch[:])
215}
216
217// chainEnd follows the chain of delta headers from off without inflating
218// anything. It returns the type of the base object.
219func (p *pack) chainEnd(off uint64, h entryHdr) (Type, error) {
220 for depth := 0; ; depth++ {
221 if !h.isDelta() {
222 return Type(h.typ), nil
223 }
224 if depth >= maxDeltaDepth {
225 return 0, corrupt("delta chain longer than %d", maxDeltaDepth)
226 }
227 var err error
228 off, err = p.baseOffset(&h, off)
229 if err != nil {
230 return 0, err
231 }
232 if h, err = parseEntryHeader(p.data, off); err != nil {
233 return 0, err
234 }
235 }
236}
237
238// baseOffset returns the offset of the base of a delta entry. A ref-delta
239// base must be in the same pack, as Git requires.
240func (p *pack) baseOffset(h *entryHdr, self uint64) (uint64, error) {
241 if h.typ == objOfsDelta {
242 return h.baseOff, nil
243 }
244 pos, ok := p.idx.find(&h.baseID)
245 if !ok {
246 return 0, corrupt("delta base %s not in pack %s", h.baseID.String(), p.name)
247 }
248 off, err := p.idx.offset(pos)
249 if err != nil {
250 return 0, err
251 }
252 if off == self {
253 return 0, corrupt("delta is its own base at %d", self)
254 }
255 return off, nil
256}
257
258// header returns the type and size of the object at off. The result of a
259// deltified object, which costs an inflate to find, is cached per pack.
260func (p *pack) header(off uint64) (Type, int64, error) {
261 if off >= uint64(len(p.data)) {
262 // Not an entry of this pack: let readHeader reject it, and keep the
263 // cache to real offsets.
264 typ, size, _, err := p.readHeader(off)
265 return typ, size, err
266 }
267 hc := p.hdrs.Load()
268 if hc != nil {
269 if typ, size, ok := hc.get(off); ok {
270 return typ, size, nil
271 }
272 }
273 typ, size, deltified, err := p.readHeader(off)
274 if err != nil || !deltified {
275 return typ, size, err
276 }
277 if hc == nil {
278 hc = newHeaderCache(p.idx.n)
279 if !p.hdrs.CompareAndSwap(nil, hc) {
280 hc = p.hdrs.Load()
281 }
282 }
283 hc.put(off, typ, size)
284 return typ, size, nil
285}
286
287// readHeader reads the type and size of the object at off from the pack.
288// deltified tells that the size comes from the start of a delta, which it
289// had to inflate.
290func (p *pack) readHeader(off uint64) (_ Type, _ int64, deltified bool, _ error) {
291 h, err := parseEntryHeader(p.data, off)
292 if err != nil {
293 return 0, 0, false, err
294 }
295 if !h.isDelta() {
296 if h.size > 1<<62 {
297 return 0, 0, false, corrupt("entry size %d", h.size)
298 }
299 return Type(h.typ), int64(h.size), false, nil
300 }
301 typ, err := p.chainEnd(off, h)
302 if err != nil {
303 return 0, 0, false, err
304 }
305 // The result size is the second varint of the delta, at its start.
306 m, err := getMem(p.stream(&h))
307 if err != nil {
308 return 0, 0, false, err
309 }
310 defer putMem(m)
311 n := min(uint64(len(m.scratch)), h.size)
312 if _, err := io.ReadFull(&m.zr, m.scratch[:n]); err != nil {
313 return 0, 0, false, corrupt("delta header: %v", err)
314 }
315 _, rs, _, err := deltaHeader(m.scratch[:n])
316 if err != nil {
317 return 0, 0, false, err
318 }
319 if rs > 1<<62 {
320 return 0, 0, false, corrupt("delta result size %d", rs)
321 }
322 return typ, int64(rs), true, nil
323}
324
325// readPacked resolves the object at off into dst (grown as needed) and
326// returns its type and content.
327func (r *Repo) readPacked(p *pack, off uint64, dst []byte) (Type, []byte, error) {
328 h, err := parseEntryHeader(p.data, off)
329 if err != nil {
330 return 0, nil, err
331 }
332 if !h.isDelta() {
333 if h.size > uint64(r.opts.maxObject) {
334 return 0, nil, tooLarge(h.size, r.opts.maxObject)
335 }
336 dst = grow(dst, int(h.size))
337 if err := p.inflateEntry(&h, dst); err != nil {
338 return 0, nil, err
339 }
340 return Type(h.typ), dst, nil
341 }
342
343 // Collect the chain of deltas down to a base that is a plain object or
344 // a cached result.
345 type link struct {
346 hdr entryHdr
347 off uint64
348 }
349 var arr [64]link
350 chain := arr[:0]
351 var (
352 baseTyp Type
353 base []byte
354 baseFresh bool // base is a private slice that may be cached as is
355 scratch [2]*buffer
356 )
357 defer func() {
358 putBuf(scratch[0])
359 putBuf(scratch[1])
360 }()
361 cur, curHdr := off, h
362 for {
363 if curHdr.isDelta() {
364 if len(chain) >= maxDeltaDepth {
365 return 0, nil, corrupt("delta chain longer than %d", maxDeltaDepth)
366 }
367 chain = append(chain, link{curHdr, cur})
368 next, err := p.baseOffset(&curHdr, cur)
369 if err != nil {
370 return 0, nil, err
371 }
372 cur = next
373 if t, data, ok := r.cache.get(cacheKey{p.id, cur}); ok {
374 baseTyp, base = t, data
375 break
376 }
377 if curHdr, err = parseEntryHeader(p.data, cur); err != nil {
378 return 0, nil, err
379 }
380 continue
381 }
382 if curHdr.size > uint64(r.opts.maxObject) {
383 return 0, nil, tooLarge(curHdr.size, r.opts.maxObject)
384 }
385 baseTyp = Type(curHdr.typ)
386 n := int(curHdr.size)
387 if r.cache.fits(n) {
388 base, baseFresh = make([]byte, n), true
389 } else {
390 scratch[0] = getBuf()
391 scratch[0].b = grow(scratch[0].b, n)
392 base = scratch[0].b
393 }
394 if err := p.inflateEntry(&curHdr, base); err != nil {
395 return 0, nil, err
396 }
397 if baseFresh {
398 r.cache.putOwned(cacheKey{p.id, cur}, baseTyp, base)
399 }
400 break
401 }
402
403 delta := getBuf()
404 defer putBuf(delta)
405 for i := len(chain) - 1; i >= 0; i-- {
406 l := chain[i]
407 if l.hdr.size > uint64(r.opts.maxObject) {
408 return 0, nil, tooLarge(l.hdr.size, r.opts.maxObject)
409 }
410 delta.b = grow(delta.b, int(l.hdr.size))
411 if err := p.inflateEntry(&l.hdr, delta.b); err != nil {
412 return 0, nil, err
413 }
414 bs, rs, body, err := deltaHeader(delta.b)
415 if err != nil {
416 return 0, nil, err
417 }
418 if bs != uint64(len(base)) {
419 return 0, nil, corrupt("delta at %d expects a base of %d bytes, got %d", l.off, bs, len(base))
420 }
421 if rs > uint64(r.opts.maxObject) {
422 return 0, nil, tooLarge(rs, r.opts.maxObject)
423 }
424 var out []byte
425 fresh := false
426 switch {
427 case i == 0:
428 out = grow(dst, int(rs))
429 case r.cache.fits(int(rs)):
430 out, fresh = make([]byte, rs), true
431 default:
432 // Write into the scratch buffer that does not hold base.
433 k := 0
434 if scratch[0] != nil && len(base) > 0 && len(scratch[0].b) > 0 && &scratch[0].b[0] == &base[0] {
435 k = 1
436 }
437 if scratch[k] == nil {
438 scratch[k] = getBuf()
439 }
440 scratch[k].b = grow(scratch[k].b, int(rs))
441 out = scratch[k].b
442 }
443 if err := applyDelta(out, base, delta.b, body); err != nil {
444 return 0, nil, err
445 }
446 if fresh {
447 r.cache.putOwned(cacheKey{p.id, l.off}, baseTyp, out)
448 }
449 base = out
450 }
451 return baseTyp, base, nil
452}
453
454func tooLarge(size uint64, limit int64) error {
455 return &sizeError{size: size, limit: limit}
456}
457
458type sizeError struct {
459 size uint64
460 limit int64
461}
462
463func (e *sizeError) Error() string {
464 return ErrTooLarge.Error() + ": " + itoa(e.size) + " bytes, limit " + itoa(uint64(e.limit))
465}
466func (e *sizeError) Unwrap() error { return ErrTooLarge }
467
468func itoa(v uint64) string {
469 var b [20]byte
470 i := len(b)
471 for {
472 i--
473 b[i] = byte('0' + v%10)
474 v /= 10
475 if v == 0 {
476 break
477 }
478 }
479 return string(b[i:])
480}