1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "bytes"
7 "encoding/binary"
8 "encoding/hex"
9 "errors"
10 "fmt"
11 "io"
12 "io/fs"
13 "math"
14 "os"
15 "path/filepath"
16 "sync/atomic"
17)
18
19// This file reads Git commit-graph files (gitformat-commit-graph): a single
20// objects/info/commit-graph or a split chain
21// objects/info/commit-graphs/commit-graph-chain plus graph-<hash>.graph
22// layers. Files are mmapped read-only and never written.
23//
24// Lifecycle. openCommitGraph returns a graph holding one reference (the
25// owner's). A reader that may outlive a concurrent reopen calls retain
26// (which fails once the graph is closed) and release when done. The owner
27// calls close when it replaces the graph; close is idempotent, only the first
28// call drops the owner's reference. The mappings are unmapped when the last
29// reference is dropped; no accessor may be used after that. Layers are
30// immutable files named after their checksum, so a concurrent
31// "git commit-graph write" never changes a mapped file; it can only delete
32// it, which does not affect an existing mapping. It can however delete a
33// layer between the moment the chain is read and the moment the layer is
34// opened: openCommitGraph then starts again from the chain, and gives up with
35// errNoGraph (callers fall back to the objects) if that keeps happening.
36//
37// File mapping is done by mapFile (mmap_*.go), which falls back to reading
38// the file where mmap is unavailable.
39//
40// Positions are global across the chain: the commits of the base layer come
41// first, then those of the next layer, and so on. Within a layer commits are
42// sorted by object id.
43//
44// Every offset read from a file is bounds-checked. Structural problems found
45// when opening return an error wrapping errGraphCorrupt; per-commit problems
46// (edge list, overflow generation) are reported by the accessor that meets
47// them. No accessor panics on malformed input.
48
49var (
50 // errGraphCorrupt wraps every error caused by malformed graph content.
51 // After merging with the core it becomes an alias of (or is wrapped
52 // with) ErrCorrupt.
53 errGraphCorrupt = errors.New("corrupt commit-graph")
54 // errGraphUnsupported wraps valid graphs this reader does not handle
55 // (SHA-256, unknown format version).
56 errGraphUnsupported = errors.New("unsupported commit-graph")
57 // errNoGraph means the repository has no commit-graph.
58 errNoGraph = errors.New("no commit-graph")
59 // errGraphPosition is returned for a position >= numCommits.
60 errGraphPosition = errors.New("commit-graph position out of range")
61)
62
63func graphCorruptf(format string, args ...any) error {
64 return fmt.Errorf("%w: %s", errGraphCorrupt, fmt.Sprintf(format, args...))
65}
66
67const (
68 graphHashSize = 20
69 graphHeaderSize = 8
70 graphChunkEntrySize = 12
71 graphCommitSize = graphHashSize + 16 // tree, 2 parents, level+time
72 graphFanoutSize = 256 * 4
73
74 graphParentNone = 0x70000000 // no parent in this slot
75 graphParentExtra = 0x80000000 // second slot: index into the EDGE chunk
76 graphEdgeLast = 0x80000000 // EDGE entry: last parent of the commit
77 graphPosMask = 0x7fffffff
78 graphGenOverflow = 0x80000000 // GDA2 entry: index into GDO2
79
80 graphMaxLayers = 256 // the base count is a single byte
81 graphMaxParents = 1 << 13
82 graphMaxChain = graphMaxLayers * (2*graphHashSize + 1)
83
84 chunkOIDF = 'O'<<24 | 'I'<<16 | 'D'<<8 | 'F'
85 chunkOIDL = 'O'<<24 | 'I'<<16 | 'D'<<8 | 'L'
86 chunkCDAT = 'C'<<24 | 'D'<<16 | 'A'<<8 | 'T'
87 chunkEDGE = 'E'<<24 | 'D'<<16 | 'G'<<8 | 'E'
88 chunkGDA2 = 'G'<<24 | 'D'<<16 | 'A'<<8 | '2'
89 chunkGDO2 = 'G'<<24 | 'D'<<16 | 'O'<<8 | '2'
90 chunkBIDX = 'B'<<24 | 'I'<<16 | 'D'<<8 | 'X'
91 chunkBDAT = 'B'<<24 | 'D'<<16 | 'A'<<8 | 'T'
92 chunkBASE = 'B'<<24 | 'A'<<16 | 'S'<<8 | 'E'
93)
94
95// graphLayer is one commit-graph file.
96type graphLayer struct {
97 data []byte
98 numBase int // base graphs declared in the header
99 base uint32 // global position of the first commit
100 n uint32 // commits in this layer
101 fanout []byte
102 oidl []byte
103 cdat []byte
104 edge []byte
105 gda2 []byte
106 gdo2 []byte
107 bidx []byte
108 bdat []byte
109 baseList []byte
110
111 // Changed-path Bloom filter settings, valid when hasBloom.
112 hasBloom bool
113 bloomVersion uint32
114 bloomHashes uint32
115 bloomBits uint32
116}
117
118// commitGraph is a (possibly split) commit-graph.
119type commitGraph struct {
120 layers []graphLayer // base first
121 total uint32
122 genV2 bool // every layer has GDA2: generation() is a corrected date
123
124 refs atomic.Int64
125 closed atomic.Bool
126 unmaps []func() error
127}
128
129// graphOpenRetries is how many times openCommitGraph starts over when a
130// layer disappears under it, after the first attempt.
131const graphOpenRetries = 3
132
133// graphBeforeLayerOpen, when set by a test, is called with the path of each
134// chain layer right before it is opened.
135var graphBeforeLayerOpen func(path string)
136
137// graphMmap maps a file read-only. The returned function releases the
138// mapping.
139func graphMmap(path string) ([]byte, func() error, error) {
140 f, err := os.Open(path)
141 if err != nil {
142 return nil, nil, err
143 }
144 defer func() { _ = f.Close() }()
145 st, err := f.Stat()
146 if err != nil {
147 return nil, nil, err
148 }
149 if !st.Mode().IsRegular() {
150 return nil, nil, graphCorruptf("%s: not a regular file", filepath.Base(path))
151 }
152 size := st.Size()
153 if size < graphHeaderSize+graphChunkEntrySize+graphHashSize {
154 return nil, nil, graphCorruptf("%s: file too short (%d bytes)", filepath.Base(path), size)
155 }
156 if size > math.MaxInt32 {
157 return nil, nil, graphCorruptf("%s: file too large (%d bytes)", filepath.Base(path), size)
158 }
159 data, unmap, err := mapFile(f, size)
160 if err != nil {
161 return nil, nil, fmt.Errorf("map %s: %w", filepath.Base(path), err)
162 }
163 return data, unmap, nil
164}
165
166// openCommitGraph opens the commit-graph of the objects directory objectsDir:
167// objects/info/commit-graph if present, else the split chain. It returns
168// errNoGraph when there is none. The result holds one reference.
169//
170// A concurrent "git commit-graph write --split" can merge layers and delete
171// the old ones between the read of the chain and the open of a layer. The
172// chain is then read again, up to graphOpenRetries more times; if layers keep
173// disappearing the error wraps errNoGraph and the cause, so that callers fall
174// back to reading objects.
175func openCommitGraph(objectsDir string) (*commitGraph, error) {
176 var gone error
177 for attempt := 0; attempt <= graphOpenRetries; attempt++ {
178 g, err := openCommitGraphOnce(objectsDir)
179 if err == nil || !errors.Is(err, fs.ErrNotExist) {
180 return g, err
181 }
182 gone = err
183 }
184 return nil, fmt.Errorf("%w: layers kept disappearing: %w", errNoGraph, gone)
185}
186
187func openCommitGraphOnce(objectsDir string) (*commitGraph, error) {
188 infoDir := filepath.Join(objectsDir, "info")
189 data, unmap, err := graphMmap(filepath.Join(infoDir, "commit-graph"))
190 switch {
191 case err == nil:
192 l, perr := parseGraphLayer(data)
193 if perr != nil {
194 _ = unmap()
195 return nil, fmt.Errorf("commit-graph: %w", perr)
196 }
197 g, aerr := assembleGraph([]*graphLayer{l}, nil)
198 if aerr != nil {
199 _ = unmap()
200 return nil, fmt.Errorf("commit-graph: %w", aerr)
201 }
202 g.unmaps = []func() error{unmap}
203 return g, nil
204 case errors.Is(err, fs.ErrNotExist):
205 return openCommitGraphChain(infoDir)
206 default:
207 return nil, fmt.Errorf("commit-graph: %w", err)
208 }
209}
210
211func openCommitGraphChain(infoDir string) (*commitGraph, error) {
212 dir := filepath.Join(infoDir, "commit-graphs")
213 names, err := readGraphChain(filepath.Join(dir, "commit-graph-chain"))
214 if err != nil {
215 return nil, err
216 }
217 layers := make([]*graphLayer, 0, len(names))
218 unmaps := make([]func() error, 0, len(names))
219 cleanup := func() {
220 for _, u := range unmaps {
221 _ = u()
222 }
223 }
224 for _, name := range names {
225 file := "graph-" + hex.EncodeToString(name[:]) + ".graph"
226 path := filepath.Join(dir, file)
227 if graphBeforeLayerOpen != nil {
228 graphBeforeLayerOpen(path)
229 }
230 data, unmap, err := graphMmap(path)
231 if err != nil {
232 cleanup()
233 return nil, fmt.Errorf("commit-graph chain layer: %w", err)
234 }
235 unmaps = append(unmaps, unmap)
236 l, err := parseGraphLayer(data)
237 if err != nil {
238 cleanup()
239 return nil, fmt.Errorf("commit-graph layer %s: %w", file, err)
240 }
241 layers = append(layers, l)
242 }
243 g, err := assembleGraph(layers, names)
244 if err != nil {
245 cleanup()
246 return nil, fmt.Errorf("commit-graph chain: %w", err)
247 }
248 g.unmaps = unmaps
249 return g, nil
250}
251
252// readGraphChain reads commit-graph-chain.
253func readGraphChain(path string) ([][graphHashSize]byte, error) {
254 f, err := os.Open(path)
255 if err != nil {
256 if errors.Is(err, fs.ErrNotExist) {
257 return nil, errNoGraph
258 }
259 return nil, fmt.Errorf("commit-graph chain: %w", err)
260 }
261 defer func() { _ = f.Close() }()
262 raw, err := io.ReadAll(io.LimitReader(f, graphMaxChain+1))
263 if err != nil {
264 return nil, fmt.Errorf("commit-graph chain: %w", err)
265 }
266 return parseGraphChain(raw)
267}
268
269// parseGraphChain parses the content of commit-graph-chain: one lowercase
270// hex checksum per line, base layer first.
271func parseGraphChain(raw []byte) ([][graphHashSize]byte, error) {
272 if len(raw) == 0 {
273 return nil, errNoGraph
274 }
275 const line = 2*graphHashSize + 1
276 if len(raw) > graphMaxChain || len(raw)%line != 0 {
277 return nil, graphCorruptf("commit-graph-chain: bad size %d", len(raw))
278 }
279 names := make([][graphHashSize]byte, len(raw)/line)
280 for i := range names {
281 row := raw[i*line : (i+1)*line]
282 if row[line-1] != '\n' {
283 return nil, graphCorruptf("commit-graph-chain: line %d not terminated", i+1)
284 }
285 if _, err := hex.Decode(names[i][:], row[:line-1]); err != nil {
286 return nil, graphCorruptf("commit-graph-chain: line %d: %v", i+1, err)
287 }
288 }
289 return names, nil
290}
291
292// parseGraphLayer validates the header, the chunk table and the sizes of the
293// chunks it understands. It does not verify the checksum nor the content of
294// individual records.
295func parseGraphLayer(data []byte) (*graphLayer, error) {
296 if len(data) < graphHeaderSize+graphChunkEntrySize+graphHashSize {
297 return nil, graphCorruptf("file too short (%d bytes)", len(data))
298 }
299 if string(data[:4]) != "CGPH" {
300 return nil, graphCorruptf("bad signature %q", data[:4])
301 }
302 if data[4] != 1 {
303 return nil, fmt.Errorf("%w: version %d", errGraphUnsupported, data[4])
304 }
305 switch data[5] {
306 case 1:
307 case 2:
308 return nil, fmt.Errorf("%w: SHA-256", errGraphUnsupported)
309 default:
310 return nil, graphCorruptf("unknown hash version %d", data[5])
311 }
312 nChunks := int(data[6])
313 l := &graphLayer{data: data, numBase: int(data[7])}
314
315 tableEnd := uint64(graphHeaderSize + (nChunks+1)*graphChunkEntrySize)
316 bodyEnd := uint64(len(data) - graphHashSize)
317 if tableEnd > bodyEnd {
318 return nil, graphCorruptf("chunk table exceeds file")
319 }
320
321 var ids [256]uint32
322 prevOff := tableEnd
323 for i := 0; i <= nChunks; i++ {
324 ent := data[graphHeaderSize+i*graphChunkEntrySize:]
325 id := binary.BigEndian.Uint32(ent)
326 off := binary.BigEndian.Uint64(ent[4:])
327 if (id == 0) != (i == nChunks) {
328 return nil, graphCorruptf("chunk table: bad terminator at entry %d", i)
329 }
330 if off < prevOff || off > bodyEnd {
331 return nil, graphCorruptf("chunk table: bad offset %d for entry %d", off, i)
332 }
333 if i > 0 {
334 // Close the previous chunk: it spans [its offset, this offset).
335 if err := l.setChunk(ids[i-1], data[prevOff:off]); err != nil {
336 return nil, err
337 }
338 }
339 for j := 0; j < i; j++ {
340 if ids[j] == id {
341 return nil, graphCorruptf("chunk table: duplicate chunk %08x", id)
342 }
343 }
344 ids[i] = id
345 prevOff = off
346 }
347
348 if err := l.validate(); err != nil {
349 return nil, err
350 }
351 return l, nil
352}
353
354// setChunk records chunk id. Unknown chunks (and the obsolete GDAT/GDOV) are
355// ignored.
356func (l *graphLayer) setChunk(id uint32, b []byte) error {
357 switch id {
358 case chunkOIDF:
359 l.fanout = b
360 case chunkOIDL:
361 l.oidl = b
362 case chunkCDAT:
363 l.cdat = b
364 case chunkEDGE:
365 l.edge = b
366 case chunkGDA2:
367 l.gda2 = b
368 case chunkGDO2:
369 l.gdo2 = b
370 case chunkBIDX:
371 l.bidx = b
372 case chunkBDAT:
373 l.bdat = b
374 case chunkBASE:
375 l.baseList = b
376 }
377 return nil
378}
379
380func (l *graphLayer) validate() error {
381 if len(l.fanout) != graphFanoutSize {
382 return graphCorruptf("OIDF chunk missing or has size %d", len(l.fanout))
383 }
384 var prev uint32
385 for i := 0; i < 256; i++ {
386 v := binary.BigEndian.Uint32(l.fanout[i*4:])
387 if v < prev {
388 return graphCorruptf("OIDF chunk not monotonic at %d", i)
389 }
390 prev = v
391 }
392 if prev >= graphParentNone {
393 return graphCorruptf("too many commits (%d)", prev)
394 }
395 l.n = prev
396 n := uint64(prev)
397 if l.oidl == nil || uint64(len(l.oidl)) != n*graphHashSize {
398 return graphCorruptf("OIDL chunk missing or has size %d for %d commits", len(l.oidl), n)
399 }
400 if l.cdat == nil || uint64(len(l.cdat)) != n*graphCommitSize {
401 return graphCorruptf("CDAT chunk missing or has size %d for %d commits", len(l.cdat), n)
402 }
403 if len(l.edge)%4 != 0 {
404 return graphCorruptf("EDGE chunk size %d not a multiple of 4", len(l.edge))
405 }
406 // Optional chunks of the wrong size disable their feature in this layer,
407 // as in git, instead of failing the layer. Without GDA2 in every layer
408 // generation() falls back to topological levels (see assembleGraph).
409 if l.gda2 != nil && uint64(len(l.gda2)) != n*4 {
410 l.gda2 = nil
411 }
412 if len(l.gdo2)%8 != 0 {
413 return graphCorruptf("GDO2 chunk size %d not a multiple of 8", len(l.gdo2))
414 }
415 if l.numBase > 0 && uint64(len(l.baseList)) != uint64(l.numBase)*graphHashSize {
416 return graphCorruptf("BASE chunk has size %d for %d base graphs", len(l.baseList), l.numBase)
417 }
418 if l.numBase == 0 && len(l.baseList) != 0 {
419 return graphCorruptf("BASE chunk present without base graphs")
420 }
421 // Bloom filters need both chunks, correctly sized; otherwise git ignores
422 // them (the layer has no changed-path data).
423 if l.bidx != nil && l.bdat != nil && uint64(len(l.bidx)) == n*4 && len(l.bdat) >= bloomHeaderSize {
424 l.bloomVersion = binary.BigEndian.Uint32(l.bdat)
425 l.bloomHashes = binary.BigEndian.Uint32(l.bdat[4:])
426 l.bloomBits = binary.BigEndian.Uint32(l.bdat[8:])
427 // Unknown versions are ignored like git does; an absurd hash
428 // count would only make queries slow.
429 l.hasBloom = (l.bloomVersion == 1 || l.bloomVersion == 2) &&
430 l.bloomHashes >= 1 && l.bloomHashes <= bloomMaxHashes
431 }
432 return nil
433}
434
435// assembleGraph builds a graph from validated layers, base first. names are
436// the chain entries (checksums) of the layers, nil for a single file.
437func assembleGraph(layers []*graphLayer, names [][graphHashSize]byte) (*commitGraph, error) {
438 if len(layers) == 0 {
439 return nil, errNoGraph
440 }
441 if len(layers) > graphMaxLayers {
442 return nil, graphCorruptf("too many layers (%d)", len(layers))
443 }
444 if names != nil && len(names) != len(layers) {
445 return nil, graphCorruptf("%d layers for %d chain entries", len(layers), len(names))
446 }
447 if names == nil && len(layers) > 1 {
448 return nil, graphCorruptf("%d layers without chain entries", len(layers))
449 }
450 g := &commitGraph{layers: make([]graphLayer, len(layers)), genV2: true}
451 var total uint64
452 for k, l := range layers {
453 if l.numBase != k {
454 return nil, graphCorruptf("layer %d declares %d base graphs", k, l.numBase)
455 }
456 for i := 0; i < k; i++ {
457 if !bytes.Equal(l.baseList[i*graphHashSize:(i+1)*graphHashSize], names[i][:]) {
458 return nil, graphCorruptf("layer %d: base graph %d does not match the chain", k, i)
459 }
460 }
461 if names != nil && !bytes.Equal(l.data[len(l.data)-graphHashSize:], names[k][:]) {
462 return nil, graphCorruptf("layer %d: checksum does not match its name in the chain", k)
463 }
464 l.base = uint32(total)
465 total += uint64(l.n)
466 if total >= graphParentNone {
467 return nil, graphCorruptf("too many commits in chain")
468 }
469 if l.gda2 == nil {
470 g.genV2 = false
471 }
472 g.layers[k] = *l
473 }
474 g.total = uint32(total)
475 g.refs.Store(1)
476 return g, nil
477}
478
479// retain adds a reference. It reports false once the graph is closed, even
480// if readers still hold references.
481func (g *commitGraph) retain() bool {
482 if g.closed.Load() {
483 return false
484 }
485 for {
486 n := g.refs.Load()
487 if n <= 0 {
488 return false
489 }
490 if g.refs.CompareAndSwap(n, n+1) {
491 return true
492 }
493 }
494}
495
496// release drops a reference; the last one unmaps the files.
497func (g *commitGraph) release() error {
498 switch n := g.refs.Add(-1); {
499 case n > 0:
500 return nil
501 case n == 0:
502 var first error
503 for _, unmap := range g.unmaps {
504 if err := unmap(); err != nil && first == nil {
505 first = err
506 }
507 }
508 g.unmaps = nil
509 return first
510 default:
511 g.refs.Add(1)
512 return errors.New("commit-graph released too many times")
513 }
514}
515
516// close drops the owner's reference. Only the first call has an effect, so
517// calling it again never drops a reference held by a reader.
518func (g *commitGraph) close() error {
519 if !g.closed.CompareAndSwap(false, true) {
520 return nil
521 }
522 return g.release()
523}
524
525// numCommits is the number of commits in the whole chain.
526func (g *commitGraph) numCommits() uint32 { return g.total }
527
528// numLayers is the number of files in the chain.
529func (g *commitGraph) numLayers() int { return len(g.layers) }
530
531// hasGenerationV2 reports whether generation returns corrected commit dates
532// (GDA2 present in every layer, as git requires) rather than topological
533// levels. The two must not be compared with each other.
534func (g *commitGraph) hasGenerationV2() bool { return g.genV2 }
535
536// layerOf finds the layer holding the global position pos and the index of
537// the commit inside it.
538func (g *commitGraph) layerOf(pos uint32) (*graphLayer, uint32) {
539 if pos >= g.total {
540 return nil, 0
541 }
542 for i := len(g.layers) - 1; i >= 0; i-- {
543 if l := &g.layers[i]; pos >= l.base {
544 return l, pos - l.base
545 }
546 }
547 return nil, 0
548}
549
550// find looks up id in one layer using the fanout table.
551func (l *graphLayer) find(id *[graphHashSize]byte) (uint32, bool) {
552 b := int(id[0])
553 var lo uint32
554 if b > 0 {
555 lo = binary.BigEndian.Uint32(l.fanout[(b-1)*4:])
556 }
557 hi := binary.BigEndian.Uint32(l.fanout[b*4:]) // <= l.n, checked when opening
558 for lo < hi {
559 mid := lo + (hi-lo)/2
560 off := int(mid) * graphHashSize
561 switch c := bytes.Compare(l.oidl[off:off+graphHashSize], id[:]); {
562 case c == 0:
563 return mid, true
564 case c < 0:
565 lo = mid + 1
566 default:
567 hi = mid
568 }
569 }
570 return 0, false
571}
572
573// lookup returns the global position of commit id. It does not allocate.
574func (g *commitGraph) lookup(id [graphHashSize]byte) (uint32, bool) {
575 for i := len(g.layers) - 1; i >= 0; i-- {
576 l := &g.layers[i]
577 if idx, ok := l.find(&id); ok {
578 return l.base + idx, true
579 }
580 }
581 return 0, false
582}
583
584// commitID returns the object id at pos.
585func (g *commitGraph) commitID(pos uint32) (id [graphHashSize]byte, err error) {
586 l, idx := g.layerOf(pos)
587 if l == nil {
588 return id, errGraphPosition
589 }
590 copy(id[:], l.oidl[int(idx)*graphHashSize:])
591 return id, nil
592}
593
594// record returns the CDAT record of pos.
595func (g *commitGraph) record(pos uint32) (*graphLayer, []byte, error) {
596 l, idx := g.layerOf(pos)
597 if l == nil {
598 return nil, nil, errGraphPosition
599 }
600 off := int(idx) * graphCommitSize
601 return l, l.cdat[off : off+graphCommitSize], nil
602}
603
604// rootTree returns the root tree id of the commit at pos.
605func (g *commitGraph) rootTree(pos uint32) (id [graphHashSize]byte, err error) {
606 _, rec, err := g.record(pos)
607 if err != nil {
608 return id, err
609 }
610 copy(id[:], rec)
611 return id, nil
612}
613
614// commitTime returns the commit time in seconds since the epoch (34 bits).
615func (g *commitGraph) commitTime(pos uint32) (int64, error) {
616 _, rec, err := g.record(pos)
617 if err != nil {
618 return 0, err
619 }
620 return graphRecordTime(rec), nil
621}
622
623func graphRecordTime(rec []byte) int64 {
624 hi := uint64(binary.BigEndian.Uint32(rec[graphHashSize+8:]) & 3)
625 lo := uint64(binary.BigEndian.Uint32(rec[graphHashSize+12:]))
626 return int64(hi<<32 | lo)
627}
628
629// topoLevel returns the topological level (generation number v1) of pos;
630// 0 means "not computed".
631func (g *commitGraph) topoLevel(pos uint32) (uint32, error) {
632 _, rec, err := g.record(pos)
633 if err != nil {
634 return 0, err
635 }
636 return binary.BigEndian.Uint32(rec[graphHashSize+8:]) >> 2, nil
637}
638
639// generation returns the corrected commit date of pos when
640// hasGenerationV2, else its topological level. In both cases a commit has a
641// strictly greater generation than each of its parents.
642func (g *commitGraph) generation(pos uint32) (uint64, error) {
643 l, idx := g.layerOf(pos)
644 if l == nil {
645 return 0, errGraphPosition
646 }
647 off := int(idx) * graphCommitSize
648 rec := l.cdat[off : off+graphCommitSize]
649 if !g.genV2 {
650 return uint64(binary.BigEndian.Uint32(rec[graphHashSize+8:]) >> 2), nil
651 }
652 v := binary.BigEndian.Uint32(l.gda2[int(idx)*4:])
653 offset := uint64(v)
654 if v&graphGenOverflow != 0 {
655 oi := uint64(v & graphPosMask)
656 if (oi+1)*8 > uint64(len(l.gdo2)) {
657 return 0, graphCorruptf("GDA2 overflow index %d beyond GDO2 (%d bytes)", oi, len(l.gdo2))
658 }
659 offset = binary.BigEndian.Uint64(l.gdo2[oi*8:])
660 if offset >= 1<<62 {
661 return 0, graphCorruptf("GDO2 offset %d out of range", offset)
662 }
663 }
664 return uint64(graphRecordTime(rec)) + offset, nil
665}
666
667// appendParents appends the parent positions of pos, in commit order, to dst
668// and returns it. It allocates only if dst has to grow (octopus merges).
669func (g *commitGraph) appendParents(dst []uint32, pos uint32) ([]uint32, error) {
670 l, rec, err := g.record(pos)
671 if err != nil {
672 return dst, err
673 }
674 // Parents are in this layer or in a lower one.
675 limit := l.base + l.n
676 p1 := binary.BigEndian.Uint32(rec[graphHashSize:])
677 p2 := binary.BigEndian.Uint32(rec[graphHashSize+4:])
678 if p1 == graphParentNone {
679 if p2 != graphParentNone {
680 return dst, graphCorruptf("commit %d has a second parent but no first", pos)
681 }
682 return dst, nil
683 }
684 if p1 >= limit {
685 return dst, graphCorruptf("commit %d: parent %d out of range", pos, p1)
686 }
687 dst = append(dst, p1)
688 switch {
689 case p2 == graphParentNone:
690 return dst, nil
691 case p2&graphParentExtra == 0:
692 if p2 >= limit {
693 return dst, graphCorruptf("commit %d: parent %d out of range", pos, p2)
694 }
695 return append(dst, p2), nil
696 }
697 count := 1
698 for e := uint64(p2 & graphPosMask); ; e++ {
699 if (e+1)*4 > uint64(len(l.edge)) {
700 return dst, graphCorruptf("commit %d: EDGE list overruns the chunk", pos)
701 }
702 v := binary.BigEndian.Uint32(l.edge[e*4:])
703 p := v & graphPosMask
704 if p >= limit {
705 return dst, graphCorruptf("commit %d: parent %d out of range", pos, p)
706 }
707 if count++; count > graphMaxParents {
708 return dst, graphCorruptf("commit %d: too many parents", pos)
709 }
710 dst = append(dst, p)
711 if v&graphEdgeLast != 0 {
712 return dst, nil
713 }
714 }
715}
716
717// graphFileStamp identifies a version of a file for change detection.
718type graphFileStamp struct {
719 exists bool
720 size int64
721 mtime int64
722 ino uint64
723}
724
725// graphStamp identifies the on-disk commit-graph state: the single file and
726// the chain file (layers are immutable and named by checksum).
727type graphStamp struct{ single, chain graphFileStamp }
728
729// trusted reports whether unchanged stat data proves that the files did not
730// change, for a stamp taken at the given time (unix nanoseconds). This is
731// Git's racy rule, the one of fileSig.same: a write that follows within the
732// clock granularity of the previous modification can leave the stat data as
733// it was, so the data only proves anything once the newest modification is
734// older than racyWindow when the stamp was taken. Git writes graph files by
735// rename, which already changes the inode; the rule covers the rest. The
736// time is that of the stamp, not of the last reload: measuring from the
737// reload would restart the window each time and reload a busy repository
738// forever.
739func (s graphStamp) trusted(at int64) bool {
740 newest := int64(math.MinInt64)
741 for _, f := range [...]graphFileStamp{s.single, s.chain} {
742 if f.exists {
743 newest = max(newest, f.mtime)
744 }
745 }
746 return newest == math.MinInt64 || at-newest > int64(racyWindow)
747}
748
749// graphPaths are the paths statGraph looks at, built once.
750type graphPaths struct{ single, chain statPath }
751
752func newGraphPaths(objectsDir string) graphPaths {
753 return graphPaths{
754 single: newStatPath(objectsDir + "/info/commit-graph"),
755 chain: newStatPath(objectsDir + "/info/commit-graphs/commit-graph-chain"),
756 }
757}
758
759func statGraphFile(p *statPath) graphFileStamp {
760 st, err := p.stat(false)
761 if err != nil || !st.exists {
762 return graphFileStamp{}
763 }
764 return graphFileStamp{exists: true, size: st.size, mtime: st.mtime, ino: st.ino}
765}
766
767// stamp returns the stamp of the commit-graph files. Comparing two stamps
768// tells whether openCommitGraph may give another result.
769func (g *graphPaths) stamp() graphStamp {
770 return graphStamp{single: statGraphFile(&g.single), chain: statGraphFile(&g.chain)}
771}
772
773// statGraph returns the stamp of the commit-graph files of objectsDir.
774func statGraph(objectsDir string) graphStamp {
775 p := newGraphPaths(objectsDir)
776 return p.stamp()
777}