1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "bufio"
7 "bytes"
8 "encoding/binary"
9 "encoding/hex"
10 "errors"
11 "fmt"
12 "io/fs"
13 "os"
14 "os/exec"
15 "path/filepath"
16 "sort"
17 "strconv"
18 "strings"
19 "sync"
20 "sync/atomic"
21 "testing"
22 "time"
23)
24
25// oid is the raw object id used by the graph code until the core's ObjectID
26// is merged.
27type oid = [20]byte
28
29// graphTestHex parses a 40-digit hex string.
30func graphTestHex(s string) oid {
31 var id oid
32 if _, err := hex.Decode(id[:], []byte(s)); err != nil || len(s) != 40 {
33 panic("graphTestHex: bad id " + strconv.Quote(s))
34 }
35 return id
36}
37
38// ---- git fixtures ---------------------------------------------------------
39
40func graphGitEnv(date int64) []string {
41 env := append(os.Environ(),
42 "GIT_CONFIG_GLOBAL=/dev/null",
43 "GIT_CONFIG_NOSYSTEM=1",
44 "GIT_TERMINAL_PROMPT=0",
45 "GIT_AUTHOR_NAME=T", "GIT_AUTHOR_EMAIL=t@example.com",
46 "GIT_COMMITTER_NAME=T", "GIT_COMMITTER_EMAIL=t@example.com",
47 )
48 if date != 0 {
49 d := strconv.FormatInt(date, 10) + " +0000"
50 env = append(env, "GIT_AUTHOR_DATE="+d, "GIT_COMMITTER_DATE="+d)
51 }
52 return env
53}
54
55func graphGit(t testing.TB, dir string, date int64, args ...string) string {
56 t.Helper()
57 return graphGitIn(t, dir, date, "", args...)
58}
59
60func graphGitStdin(t testing.TB, dir, stdin string, args ...string) string {
61 t.Helper()
62 return graphGitIn(t, dir, 0, stdin, args...)
63}
64
65func graphGitIn(t testing.TB, dir string, date int64, stdin string, args ...string) string {
66 t.Helper()
67 cmd := exec.Command("git", args...)
68 cmd.Stdin = strings.NewReader(stdin)
69 cmd.Dir = dir
70 cmd.Env = graphGitEnv(date)
71 var stderr bytes.Buffer
72 cmd.Stderr = &stderr
73 out, err := cmd.Output()
74 if err != nil {
75 t.Fatalf("git %s: %v\n%s", strings.Join(args, " "), err, stderr.String())
76 }
77 return string(out)
78}
79
80// gtRepo is a scratch repository with a deterministic clock.
81type gtRepo struct {
82 t testing.TB
83 dir string
84 clock int64
85}
86
87func newGTRepo(t testing.TB) *gtRepo {
88 t.Helper()
89 requireGit(t)
90 r := >Repo{t: t, dir: t.TempDir(), clock: 1_700_000_000}
91 r.git("init", "-q", "-b", "main")
92 return r
93}
94
95func (r *gtRepo) git(args ...string) string {
96 r.t.Helper()
97 return graphGit(r.t, r.dir, r.clock, args...)
98}
99
100func (r *gtRepo) objects() string { return filepath.Join(r.dir, ".git", "objects") }
101
102func (r *gtRepo) write(path, content string) {
103 r.t.Helper()
104 full := filepath.Join(r.dir, path)
105 if err := os.MkdirAll(filepath.Dir(full), 0o755); err != nil {
106 r.t.Fatal(err)
107 }
108 if err := os.WriteFile(full, []byte(content), 0o644); err != nil {
109 r.t.Fatal(err)
110 }
111}
112
113func (r *gtRepo) tick() int64 {
114 r.clock += 60
115 return r.clock
116}
117
118// commit writes files (path, content pairs) and commits them.
119func (r *gtRepo) commit(files ...string) {
120 r.t.Helper()
121 for i := 0; i+1 < len(files); i += 2 {
122 r.write(files[i], files[i+1])
123 }
124 r.tick()
125 r.git("add", "-A")
126 r.git("commit", "-q", "-m", fmt.Sprintf("c%d", r.clock))
127}
128
129// commitAt commits with an explicit date (to build clock skew).
130func (r *gtRepo) commitAt(date int64, files ...string) {
131 r.t.Helper()
132 for i := 0; i+1 < len(files); i += 2 {
133 r.write(files[i], files[i+1])
134 }
135 r.git("add", "-A")
136 graphGit(r.t, r.dir, date, "commit", "-q", "-m", fmt.Sprintf("c%d", date))
137}
138
139func (r *gtRepo) remove(path string) {
140 r.t.Helper()
141 r.tick()
142 r.git("rm", "-q", "-r", path)
143 r.git("commit", "-q", "-m", "rm "+path)
144}
145
146// stageOne: linear history with nested dirs, deletes, non-ASCII and
147// high-bit paths, an empty commit, clock skew and ordinary merges.
148func (r *gtRepo) stageOne() {
149 r.commit("README", "r\n", "src/a.go", "a\n", "src/pkg/b.go", "b\n")
150 r.commit("src/a.go", "a2\n", "docs/guide.md", "g\n")
151 r.commit("café/menü.txt", "x\n", "\xe9\xe8/\xff\xfe.txt", "latin1\n", "日本語/ファイル.txt", "j\n")
152 r.commit("src/pkg/deep/er/c.go", "c\n")
153 r.tick()
154 r.git("commit", "-q", "--allow-empty", "-m", "empty")
155 r.remove("docs")
156 // clock skew: a child older than its parent.
157 r.commitAt(r.clock-5000, "src/skew.go", "s\n")
158 r.commit("src/a.go", "a3\n")
159
160 r.git("checkout", "-q", "-b", "topic")
161 r.commit("topic/one.txt", "1\n")
162 r.commit("topic/two.txt", "2\n", "src/pkg/b.go", "b2\n")
163 r.git("checkout", "-q", "main")
164 r.commit("main-only.txt", "m\n")
165 r.tick()
166 r.git("merge", "-q", "--no-ff", "-m", "merge topic", "topic")
167 r.commit("README", "r2\n")
168}
169
170// stageTwo: an octopus merge (5 parents) and a merge of an older branch.
171func (r *gtRepo) stageTwo() {
172 for i := 1; i <= 4; i++ {
173 r.git("checkout", "-q", "-b", fmt.Sprintf("b%d", i), "main")
174 r.commit(fmt.Sprintf("oct/b%d.txt", i), fmt.Sprintf("%d\n", i), "ünï/b"+strconv.Itoa(i), "x\n")
175 r.commit(fmt.Sprintf("oct/b%d.txt", i), fmt.Sprintf("%d%d\n", i, i))
176 }
177 r.git("checkout", "-q", "main")
178 r.commit("after.txt", "a\n")
179 r.tick()
180 r.git("merge", "-q", "--no-ff", "-m", "octopus", "b1", "b2", "b3", "b4")
181 r.commit("src/a.go", "a4\n")
182 r.tick()
183 r.git("merge", "-q", "--no-ff", "-m", "merge topic again", "topic")
184}
185
186// stageThree: more linear commits, a merge whose parents are in base layers.
187func (r *gtRepo) stageThree() {
188 r.git("checkout", "-q", "-b", "late", "topic")
189 r.commit("late/x.txt", "x\n")
190 r.git("checkout", "-q", "main")
191 r.commit("src/pkg/b.go", "b3\n")
192 r.tick()
193 r.git("merge", "-q", "--no-ff", "-m", "merge late", "late")
194 for i := range 5 {
195 r.commit(fmt.Sprintf("tail/%d.txt", i), "t\n")
196 }
197}
198
199type gcase struct {
200 name string
201 split bool
202 bloom bool
203 cfg []string // -c key=value before the subcommand
204 bloomVer uint32 // expected BDAT version when bloom
205 wantGenV2 bool
206}
207
208// writeGraph runs git commit-graph write. git leaves its files read-only.
209func (r *gtRepo) writeGraph(c gcase) {
210 r.t.Helper()
211 args := []string{}
212 for _, kv := range c.cfg {
213 args = append(args, "-c", kv)
214 }
215 args = append(args, "commit-graph", "write", "--reachable")
216 if c.bloom {
217 args = append(args, "--changed-paths")
218 } else {
219 args = append(args, "--no-changed-paths")
220 }
221 if c.split {
222 args = append(args, "--split=no-merge")
223 }
224 r.git(args...)
225}
226
227// buildCase creates the three-stage history, writing a graph after each.
228func buildCase(t *testing.T, c gcase) *gtRepo {
229 r := newGTRepo(t)
230 r.stageOne()
231 r.writeGraph(c)
232 r.stageTwo()
233 r.writeGraph(c)
234 r.stageThree()
235 r.writeGraph(c)
236 r.git("commit-graph", "verify")
237 return r
238}
239
240// ---- reference data from git ---------------------------------------------
241
242type refCommit struct {
243 id oid
244 tree oid
245 parents []oid
246 ctime int64
247}
248
249func gitCommits(t testing.TB, dir string) []refCommit {
250 t.Helper()
251 out := graphGit(t, dir, 0, "log", "--all", "--format=%H %T %P|%ct")
252 var cs []refCommit
253 for _, line := range strings.Split(strings.TrimSpace(out), "\n") {
254 left, ct, ok := strings.Cut(line, "|")
255 if !ok {
256 t.Fatalf("bad log line %q", line)
257 }
258 f := strings.Fields(left)
259 c := refCommit{id: graphTestHex(f[0]), tree: graphTestHex(f[1])}
260 for _, p := range f[2:] {
261 c.parents = append(c.parents, graphTestHex(p))
262 }
263 c.ctime, _ = strconv.ParseInt(ct, 10, 64)
264 cs = append(cs, c)
265 }
266 return cs
267}
268
269// checkGraphAgainstGit compares every commit of g with git's view.
270func checkGraphAgainstGit(t *testing.T, dir string, g *commitGraph, wantMerges bool) []refCommit {
271 t.Helper()
272 cs := gitCommits(t, dir)
273 if int(g.numCommits()) != len(cs) {
274 t.Fatalf("numCommits = %d, git has %d commits", g.numCommits(), len(cs))
275 }
276 byID := make(map[oid]*refCommit, len(cs))
277 for i := range cs {
278 byID[cs[i].id] = &cs[i]
279 }
280 var buf [8]uint32
281 sawOctopus, sawMerge := false, false
282 for i := range cs {
283 c := &cs[i]
284 pos, ok := g.lookup(c.id)
285 if !ok {
286 t.Fatalf("lookup(%x) not found", c.id)
287 }
288 if id, err := g.commitID(pos); err != nil || id != c.id {
289 t.Fatalf("commitID(%d) = %x, %v; want %x", pos, id, err, c.id)
290 }
291 if tree, err := g.rootTree(pos); err != nil || tree != c.tree {
292 t.Fatalf("rootTree(%d) = %x, %v; want %x", pos, tree, err, c.tree)
293 }
294 if ct, err := g.commitTime(pos); err != nil || ct != c.ctime {
295 t.Fatalf("commitTime(%d) = %d, %v; want %d", pos, ct, err, c.ctime)
296 }
297 ps, err := g.appendParents(buf[:0], pos)
298 if err != nil {
299 t.Fatalf("appendParents(%d): %v", pos, err)
300 }
301 if len(ps) != len(c.parents) {
302 t.Fatalf("commit %x: %d parents, git has %d", c.id, len(ps), len(c.parents))
303 }
304 for j, p := range ps {
305 pid, err := g.commitID(p)
306 if err != nil || pid != c.parents[j] {
307 t.Fatalf("commit %x parent %d = %x, %v; want %x", c.id, j, pid, err, c.parents[j])
308 }
309 }
310 sawMerge = sawMerge || len(ps) == 2
311 sawOctopus = sawOctopus || len(ps) > 2
312 }
313 if wantMerges && (!sawMerge || !sawOctopus) {
314 t.Errorf("fixture lacks merge (%v) or octopus (%v)", sawMerge, sawOctopus)
315 }
316 checkGeneration(t, g, cs, byID, wantMerges)
317 return cs
318}
319
320// checkGeneration verifies the topological level exactly (1 + max parents)
321// and, when present, the corrected commit date (max(date, max parents + 1)).
322func checkGeneration(t *testing.T, g *commitGraph, cs []refCommit, byID map[oid]*refCommit, wantSkew bool) {
323 t.Helper()
324 level := func(id oid) uint32 {
325 pos, _ := g.lookup(id)
326 v, err := g.topoLevel(pos)
327 if err != nil {
328 t.Fatal(err)
329 }
330 return v
331 }
332 gen := func(id oid) uint64 {
333 pos, _ := g.lookup(id)
334 v, err := g.generation(pos)
335 if err != nil {
336 t.Fatal(err)
337 }
338 return v
339 }
340 skewed := false
341 for i := range cs {
342 c := &cs[i]
343 wantLevel := uint32(1)
344 wantGen := uint64(c.ctime)
345 for _, p := range c.parents {
346 if l := level(p) + 1; l > wantLevel {
347 wantLevel = l
348 }
349 if v := gen(p) + 1; g.hasGenerationV2() && v > wantGen {
350 wantGen = v
351 }
352 }
353 if got := level(c.id); got != wantLevel {
354 t.Fatalf("topoLevel(%x) = %d, want %d", c.id, got, wantLevel)
355 }
356 if g.hasGenerationV2() {
357 got := gen(c.id)
358 if got != wantGen {
359 t.Fatalf("generation(%x) = %d, want corrected date %d", c.id, got, wantGen)
360 }
361 skewed = skewed || got != uint64(c.ctime)
362 } else if got := gen(c.id); got != uint64(wantLevel) {
363 t.Fatalf("generation(%x) = %d, want level %d", c.id, got, wantLevel)
364 }
365 for _, p := range c.parents {
366 if gen(p) >= gen(c.id) {
367 t.Fatalf("generation not increasing from parent %x to %x", p, c.id)
368 }
369 }
370 }
371 if wantSkew && g.hasGenerationV2() && !skewed {
372 t.Error("clock skew fixture produced no corrected date different from the commit time")
373 }
374 _ = byID
375}
376
377// ---- conformance ----------------------------------------------------------
378
379func graphCases() []gcase {
380 return []gcase{
381 {name: "single", wantGenV2: true},
382 {name: "single-bloom", bloom: true, bloomVer: 1, wantGenV2: true},
383 {name: "split", split: true, wantGenV2: true},
384 {name: "split-bloom", split: true, bloom: true, bloomVer: 1, wantGenV2: true},
385 {name: "split-bloom-v1", split: true, bloom: true, bloomVer: 1, wantGenV2: true,
386 cfg: []string{"commitGraph.changedPathsVersion=1"}},
387 {name: "split-bloom-v2-explicit", split: true, bloom: true, bloomVer: 2, wantGenV2: true,
388 cfg: []string{"commitGraph.changedPathsVersion=2"}},
389 {name: "split-gen1", split: true, bloom: true, bloomVer: 1,
390 cfg: []string{"commitGraph.generationVersion=1"}},
391 {name: "single-gen1", cfg: []string{"commitGraph.generationVersion=1"}},
392 }
393}
394
395func TestGraphConformance(t *testing.T) {
396 for _, c := range graphCases() {
397 t.Run(c.name, func(t *testing.T) {
398 r := buildCase(t, c)
399 g, err := openCommitGraph(r.objects())
400 if err != nil {
401 t.Fatal(err)
402 }
403 defer func() { _ = g.close() }()
404
405 wantLayers := 1
406 if c.split {
407 wantLayers = 3
408 }
409 if g.numLayers() != wantLayers {
410 t.Fatalf("layers = %d, want %d", g.numLayers(), wantLayers)
411 }
412 if g.hasGenerationV2() != c.wantGenV2 {
413 t.Fatalf("hasGenerationV2 = %v, want %v", g.hasGenerationV2(), c.wantGenV2)
414 }
415 cs := checkGraphAgainstGit(t, r.dir, g, true)
416
417 // Positions are dense and round-trip, and absent ids miss.
418 for pos := uint32(0); pos < g.numCommits(); pos++ {
419 id, err := g.commitID(pos)
420 if err != nil {
421 t.Fatal(err)
422 }
423 if p, ok := g.lookup(id); !ok || p != pos {
424 t.Fatalf("lookup(commitID(%d)) = %d, %v", pos, p, ok)
425 }
426 }
427 for i := range cs {
428 miss := cs[i].id
429 miss[19] ^= 0x5a
430 if _, ok := g.lookup(miss); ok {
431 if _, real := byIDHas(cs, miss); !real {
432 t.Fatalf("lookup found absent id %x", miss)
433 }
434 }
435 }
436 if _, err := g.commitID(g.numCommits()); !errors.Is(err, errGraphPosition) {
437 t.Fatalf("commitID(numCommits) err = %v", err)
438 }
439 if _, err := g.appendParents(nil, g.numCommits()); !errors.Is(err, errGraphPosition) {
440 t.Fatalf("appendParents(numCommits) err = %v", err)
441 }
442
443 checkBloomAgainstGit(t, r.dir, g, cs, c)
444 })
445 }
446}
447
448func byIDHas(cs []refCommit, id oid) (int, bool) {
449 for i := range cs {
450 if cs[i].id == id {
451 return i, true
452 }
453 }
454 return 0, false
455}
456
457func TestGraphNone(t *testing.T) {
458 r := newGTRepo(t)
459 r.commit("a", "a\n")
460 if _, err := openCommitGraph(r.objects()); !errors.Is(err, errNoGraph) {
461 t.Fatalf("err = %v, want errNoGraph", err)
462 }
463}
464
465// A split chain written with the default merge strategy still reads fine.
466func TestGraphSplitDefaultMerge(t *testing.T) {
467 r := newGTRepo(t)
468 for i := range 4 {
469 r.commit(fmt.Sprintf("f%d", i), "x\n")
470 r.git("commit-graph", "write", "--reachable", "--split", "--changed-paths")
471 }
472 g, err := openCommitGraph(r.objects())
473 if err != nil {
474 t.Fatal(err)
475 }
476 defer func() { _ = g.close() }()
477 checkGraphAgainstGit(t, r.dir, g, false)
478}
479
480func TestGraphRefcount(t *testing.T) {
481 r := newGTRepo(t)
482 r.commit("a", "a\n")
483 r.git("commit-graph", "write", "--reachable")
484 g, err := openCommitGraph(r.objects())
485 if err != nil {
486 t.Fatal(err)
487 }
488 if !g.retain() {
489 t.Fatal("retain failed on open graph")
490 }
491 if err := g.close(); err != nil { // owner drops its reference
492 t.Fatal(err)
493 }
494 // Still usable: the reader holds a reference.
495 if g.numCommits() != 1 {
496 t.Fatal("numCommits")
497 }
498 if _, err := g.commitID(0); err != nil {
499 t.Fatal(err)
500 }
501 if err := g.release(); err != nil {
502 t.Fatal(err)
503 }
504 if g.retain() {
505 t.Fatal("retain succeeded on closed graph")
506 }
507 if err := g.release(); err == nil {
508 t.Fatal("over-release not reported")
509 }
510}
511
512// close is idempotent: a second call must not drop a reader's reference.
513func TestGraphCloseIdempotent(t *testing.T) {
514 r := newGTRepo(t)
515 r.commit("a", "a\n")
516 r.git("commit-graph", "write", "--reachable")
517 g, err := openCommitGraph(r.objects())
518 if err != nil {
519 t.Fatal(err)
520 }
521 if !g.retain() {
522 t.Fatal("retain failed on open graph")
523 }
524 var unmapped atomic.Int32
525 for i, u := range g.unmaps {
526 g.unmaps[i] = func() error { unmapped.Add(1); return u() }
527 }
528 for range 3 {
529 if err := g.close(); err != nil {
530 t.Fatal(err)
531 }
532 }
533 if unmapped.Load() != 0 {
534 t.Fatal("unmapped while a reader holds a reference")
535 }
536 if g.retain() {
537 t.Fatal("retain succeeded after close")
538 }
539 if _, err := g.commitID(0); err != nil {
540 t.Fatal(err)
541 }
542 if err := g.release(); err != nil {
543 t.Fatal(err)
544 }
545 if unmapped.Load() != int32(len(g.layers)) {
546 t.Fatalf("unmapped %d files, want %d", unmapped.Load(), len(g.layers))
547 }
548 if err := g.close(); err != nil {
549 t.Fatal(err)
550 }
551 if unmapped.Load() != int32(len(g.layers)) {
552 t.Fatal("close after the last release unmapped again")
553 }
554}
555
556// Readers retain, read and release while the owner closes (more than once).
557// The files must never be unmapped while a reader holds a reference; a read
558// of an unmapped file would also crash the test.
559func TestGraphConcurrentCloseRetain(t *testing.T) {
560 r := newGTRepo(t)
561 for i := range 5 {
562 r.commit(fmt.Sprintf("f%d", i), "x\n")
563 r.git("commit-graph", "write", "--reachable", "--split=no-merge", "--changed-paths")
564 }
565 const readers = 16
566 rounds := 20
567 if testing.Short() {
568 rounds = 3
569 }
570 for range rounds {
571 g, err := openCommitGraph(r.objects())
572 if err != nil {
573 t.Fatal(err)
574 }
575 var active, unmapped atomic.Int32
576 for i, u := range g.unmaps {
577 g.unmaps[i] = func() error {
578 if active.Load() != 0 {
579 t.Error("unmapped while referenced")
580 }
581 unmapped.Store(1)
582 return u()
583 }
584 }
585 var wg sync.WaitGroup
586 start := make(chan struct{})
587 var retained atomic.Int64
588 for range readers {
589 wg.Go(func() {
590 <-start
591 for range 200 {
592 if !g.retain() {
593 return
594 }
595 retained.Add(1)
596 active.Add(1)
597 if unmapped.Load() != 0 {
598 t.Error("reference granted on unmapped graph")
599 }
600 for pos := range g.numCommits() {
601 id, err := g.commitID(pos)
602 if err != nil {
603 t.Error(err)
604 }
605 if got, ok := g.lookup(id); !ok || got != pos {
606 t.Errorf("lookup(%d) = %d, %v", pos, got, ok)
607 }
608 if _, err := g.appendParents(nil, pos); err != nil {
609 t.Error(err)
610 }
611 g.maybeChanged(pos, []byte("f1"))
612 }
613 active.Add(-1)
614 if err := g.release(); err != nil {
615 t.Error(err)
616 }
617 }
618 })
619 }
620 close(start)
621 for range 3 {
622 wg.Go(func() {
623 if err := g.close(); err != nil {
624 t.Error(err)
625 }
626 })
627 }
628 wg.Wait()
629 if unmapped.Load() != 1 {
630 t.Fatal("files never unmapped")
631 }
632 if g.retain() {
633 t.Fatal("retain succeeded after close")
634 }
635 }
636}
637
638// A layer removed or rewritten while a graph is open must not affect it.
639func TestGraphSurvivesRewrite(t *testing.T) {
640 r := newGTRepo(t)
641 r.stageOne()
642 c := gcase{split: true, bloom: true}
643 r.writeGraph(c)
644 g, err := openCommitGraph(r.objects())
645 if err != nil {
646 t.Fatal(err)
647 }
648 defer func() { _ = g.close() }()
649 before := g.numCommits()
650 r.stageTwo()
651 r.git("commit-graph", "write", "--reachable", "--changed-paths") // replaces the chain
652 if st := statGraph(r.objects()); !st.single.exists || st.chain.exists {
653 t.Fatalf("unexpected stamp %+v", st)
654 }
655 if g.numCommits() != before {
656 t.Fatal("numCommits changed")
657 }
658 for pos := uint32(0); pos < before; pos++ {
659 if _, err := g.commitID(pos); err != nil {
660 t.Fatal(err)
661 }
662 }
663}
664
665// setLayerHook installs graphBeforeLayerOpen for the duration of the test.
666func setLayerHook(t *testing.T, f func(path string)) {
667 t.Helper()
668 graphBeforeLayerOpen = f
669 t.Cleanup(func() { graphBeforeLayerOpen = nil })
670}
671
672// splitChainRepo has a graph chain of several layers.
673func splitChainRepo(t *testing.T) *gtRepo {
674 r := newGTRepo(t)
675 for i := range 3 {
676 r.commit(fmt.Sprintf("f%d", i), "x\n")
677 r.git("commit-graph", "write", "--reachable", "--split=no-merge", "--changed-paths")
678 }
679 return r
680}
681
682// A concurrent merging "commit-graph write --split" deletes the layers named
683// by the chain just read: opening starts again and succeeds.
684func TestGraphOpenRetriesVanishedLayer(t *testing.T) {
685 r := splitChainRepo(t)
686 calls := 0
687 setLayerHook(t, func(string) {
688 if calls++; calls == 1 {
689 r.git("commit-graph", "write", "--reachable", "--split=replace", "--changed-paths", "--expire-time=now")
690 }
691 })
692 g, err := openCommitGraph(r.objects())
693 if err != nil {
694 t.Fatal(err)
695 }
696 defer func() { _ = g.close() }()
697 if g.numLayers() != 1 {
698 t.Fatalf("layers = %d, want the replaced chain of 1", g.numLayers())
699 }
700 checkGraphAgainstGit(t, r.dir, g, false)
701}
702
703// Layers that keep vanishing end in errNoGraph, which callers treat as
704// "read the objects instead", wrapping the cause.
705func TestGraphOpenGivesUpOnVanishedLayer(t *testing.T) {
706 r := splitChainRepo(t)
707 calls := 0
708 setLayerHook(t, func(path string) {
709 calls++
710 _ = os.Remove(path)
711 })
712 g, err := openCommitGraph(r.objects())
713 if err == nil {
714 _ = g.close()
715 t.Fatal("opened a graph with a missing layer")
716 }
717 if !errors.Is(err, errNoGraph) || !errors.Is(err, fs.ErrNotExist) {
718 t.Fatalf("err = %v, want errNoGraph wrapping ErrNotExist", err)
719 }
720 if calls != 1+graphOpenRetries {
721 t.Fatalf("%d attempts, want %d", calls, 1+graphOpenRetries)
722 }
723}
724
725// Opening in a loop while git rewrites the chain: success or errNoGraph only.
726func TestGraphOpenStressSplitWrite(t *testing.T) {
727 r := newGTRepo(t)
728 r.commit("a", "a\n")
729 r.git("commit-graph", "write", "--reachable", "--split", "--changed-paths")
730 commits := 150
731 if testing.Short() {
732 commits = 10
733 }
734 var done atomic.Bool
735 writerErr := make(chan error, 1)
736 go func() {
737 defer done.Store(true)
738 for i := range commits {
739 for _, args := range [][]string{
740 {"commit", "-q", "--allow-empty", "-m", fmt.Sprint("s", i)},
741 {"commit-graph", "write", "--reachable", "--split", "--changed-paths", "--expire-time=now"},
742 } {
743 cmd := exec.Command("git", args...)
744 cmd.Dir = r.dir
745 cmd.Env = graphGitEnv(0)
746 if out, err := cmd.CombinedOutput(); err != nil {
747 writerErr <- fmt.Errorf("git %v: %v\n%s", args, err, out)
748 return
749 }
750 }
751 }
752 writerErr <- nil
753 }()
754 // Count the layer opens beyond the chain length: retries.
755 var layerOpens atomic.Int64
756 setLayerHook(t, func(string) { layerOpens.Add(1) })
757 var opened, none int
758 deadline := time.Now().Add(2 * time.Minute)
759 for !done.Load() && time.Now().Before(deadline) {
760 g, err := openCommitGraph(r.objects())
761 switch {
762 case err == nil:
763 opened++
764 if g.numCommits() == 0 {
765 t.Error("empty graph")
766 }
767 _ = g.close()
768 case errors.Is(err, errNoGraph):
769 none++
770 default:
771 t.Fatalf("open: %v", err)
772 }
773 }
774 if err := <-writerErr; err != nil {
775 t.Fatal(err)
776 }
777 t.Logf("opened %d, no graph %d, layer opens %d", opened, none, layerOpens.Load())
778 if opened == 0 {
779 t.Error("never opened a graph")
780 }
781}
782
783func TestGraphStamp(t *testing.T) {
784 r := newGTRepo(t)
785 r.commit("a", "a\n")
786 s0 := statGraph(r.objects())
787 if s0.single.exists || s0.chain.exists {
788 t.Fatalf("stamp = %+v", s0)
789 }
790 r.git("commit-graph", "write", "--reachable", "--split")
791 s1 := statGraph(r.objects())
792 if !s1.chain.exists || s1 == s0 {
793 t.Fatalf("stamp = %+v", s1)
794 }
795 r.commit("b", "b\n")
796 r.git("commit-graph", "write", "--reachable", "--split=no-merge")
797 if s2 := statGraph(r.objects()); s2 == s1 {
798 t.Fatal("stamp did not change after a new layer")
799 }
800}
801
802// ---- synthetic graph writer ----------------------------------------------
803
804// synthLayer builds a commit-graph layer byte for byte, for cases git does
805// not produce (generation overflow, wide octopus, corruption).
806type synthLayer struct {
807 ids []oid // must be sorted
808 trees []oid
809 parents [][]uint32 // global positions
810 times []int64
811 levels []uint32
812 gda2 []uint32 // nil: no chunk
813 gdo2 []uint64
814 bidx []uint32
815 bdat []byte // including the 12-byte header
816 base []oid // base graph checksums
817 skipEdge bool
818}
819
820func (s *synthLayer) bytes() []byte {
821 n := len(s.ids)
822 var oidl, cdat, edge, gda2, gdo2, bidx, base bytes.Buffer
823 fan := make([]uint32, 256)
824 for _, id := range s.ids {
825 fan[id[0]]++
826 oidl.Write(id[:])
827 }
828 for i := 1; i < 256; i++ {
829 fan[i] += fan[i-1]
830 }
831 var fanout bytes.Buffer
832 for _, v := range fan {
833 _ = binary.Write(&fanout, binary.BigEndian, v)
834 }
835 be := binary.BigEndian
836 put32 := func(b *bytes.Buffer, v uint32) { _ = binary.Write(b, be, v) }
837 for i := range n {
838 var tree oid
839 if i < len(s.trees) {
840 tree = s.trees[i]
841 }
842 cdat.Write(tree[:])
843 var ps []uint32
844 if i < len(s.parents) {
845 ps = s.parents[i]
846 }
847 p1, p2 := uint32(graphParentNone), uint32(graphParentNone)
848 if len(ps) > 0 {
849 p1 = ps[0]
850 }
851 switch {
852 case len(ps) == 2:
853 p2 = ps[1]
854 case len(ps) > 2:
855 p2 = graphParentExtra | uint32(edge.Len()/4)
856 for j, p := range ps[1:] {
857 if j == len(ps)-2 {
858 p |= graphEdgeLast
859 }
860 put32(&edge, p)
861 }
862 }
863 put32(&cdat, p1)
864 put32(&cdat, p2)
865 var tm int64
866 if i < len(s.times) {
867 tm = s.times[i]
868 }
869 var lv uint32 = 1
870 if i < len(s.levels) {
871 lv = s.levels[i]
872 }
873 put32(&cdat, lv<<2|uint32(tm>>32)&3)
874 put32(&cdat, uint32(tm))
875 }
876 for _, v := range s.gda2 {
877 put32(&gda2, v)
878 }
879 for _, v := range s.gdo2 {
880 _ = binary.Write(&gdo2, be, v)
881 }
882 for _, v := range s.bidx {
883 put32(&bidx, v)
884 }
885 for _, b := range s.base {
886 base.Write(b[:])
887 }
888
889 type chunk struct {
890 id uint32
891 data []byte
892 }
893 chunks := []chunk{{chunkOIDF, fanout.Bytes()}, {chunkOIDL, oidl.Bytes()}, {chunkCDAT, cdat.Bytes()}}
894 if edge.Len() > 0 && !s.skipEdge {
895 chunks = append(chunks, chunk{chunkEDGE, edge.Bytes()})
896 }
897 if s.gda2 != nil {
898 chunks = append(chunks, chunk{chunkGDA2, gda2.Bytes()})
899 }
900 if s.gdo2 != nil {
901 chunks = append(chunks, chunk{chunkGDO2, gdo2.Bytes()})
902 }
903 if s.bdat != nil {
904 chunks = append(chunks, chunk{chunkBIDX, bidx.Bytes()}, chunk{chunkBDAT, s.bdat})
905 }
906 if len(s.base) > 0 {
907 chunks = append(chunks, chunk{chunkBASE, base.Bytes()})
908 }
909
910 var out bytes.Buffer
911 out.WriteString("CGPH")
912 out.Write([]byte{1, 1, byte(len(chunks)), byte(len(s.base))})
913 off := uint64(graphHeaderSize + (len(chunks)+1)*graphChunkEntrySize)
914 for _, c := range chunks {
915 put32(&out, c.id)
916 _ = binary.Write(&out, be, off)
917 off += uint64(len(c.data))
918 }
919 put32(&out, 0)
920 _ = binary.Write(&out, be, off)
921 for _, c := range chunks {
922 out.Write(c.data)
923 }
924 out.Write(make([]byte, graphHashSize))
925 return out.Bytes()
926}
927
928func synthIDs(n int) []oid {
929 ids := make([]oid, n)
930 for i := range ids {
931 ids[i][0] = byte(i * 251 / max(n, 1))
932 binary.BigEndian.PutUint32(ids[i][16:], uint32(i))
933 }
934 sort.Slice(ids, func(a, b int) bool { return bytes.Compare(ids[a][:], ids[b][:]) < 0 })
935 return ids
936}
937
938func mustParseSynth(t testing.TB, b []byte) *commitGraph {
939 t.Helper()
940 l, err := parseGraphLayer(b)
941 if err != nil {
942 t.Fatal(err)
943 }
944 g, err := assembleGraph([]*graphLayer{l}, nil)
945 if err != nil {
946 t.Fatal(err)
947 }
948 return g
949}
950
951func TestGraphSyntheticOctopusAndOverflow(t *testing.T) {
952 const n = 12
953 s := &synthLayer{ids: synthIDs(n)}
954 s.parents = make([][]uint32, n)
955 s.times = make([]int64, n)
956 s.gda2 = make([]uint32, n)
957 for i := range n {
958 s.times[i] = 1_000_000 + int64(i)
959 s.gda2[i] = uint32(i)
960 }
961 s.parents[11] = []uint32{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} // 11 parents
962 s.parents[10] = []uint32{9}
963 s.parents[9] = []uint32{8, 7}
964 s.parents[8] = []uint32{7, 6, 5}
965 // Overflow: commit 3 has a 40-bit offset, and a time over 32 bits.
966 s.gda2[3] = graphGenOverflow | 1
967 s.gdo2 = []uint64{7, 1 << 40}
968 s.times[4] = 1<<33 + 5
969
970 g := mustParseSynth(t, s.bytes())
971 defer func() { _ = g.close() }()
972 var buf [4]uint32
973 for pos := range uint32(n) {
974 ps, err := g.appendParents(buf[:0], pos)
975 if err != nil {
976 t.Fatal(err)
977 }
978 want := s.parents[pos]
979 if len(ps) != len(want) {
980 t.Fatalf("pos %d: parents %v, want %v", pos, ps, want)
981 }
982 for i := range ps {
983 if ps[i] != want[i] {
984 t.Fatalf("pos %d: parents %v, want %v", pos, ps, want)
985 }
986 }
987 }
988 if !g.hasGenerationV2() {
989 t.Fatal("expected generation v2")
990 }
991 if v, err := g.generation(3); err != nil || v != uint64(s.times[3])+1<<40 {
992 t.Fatalf("overflow generation = %d, %v", v, err)
993 }
994 if v, err := g.generation(2); err != nil || v != uint64(s.times[2])+2 {
995 t.Fatalf("generation(2) = %d, %v", v, err)
996 }
997 if v, err := g.commitTime(4); err != nil || v != 1<<33+5 {
998 t.Fatalf("34-bit time = %d, %v", v, err)
999 }
1000}
1001
1002func TestGraphSyntheticCorruption(t *testing.T) {
1003 const n = 6
1004 mk := func(f func(s *synthLayer)) *synthLayer {
1005 s := &synthLayer{ids: synthIDs(n), parents: make([][]uint32, n), times: make([]int64, n)}
1006 s.parents[5] = []uint32{0, 1, 2}
1007 if f != nil {
1008 f(s)
1009 }
1010 return s
1011 }
1012 t.Run("ok", func(t *testing.T) {
1013 g := mustParseSynth(t, mk(nil).bytes())
1014 _ = g.close()
1015 })
1016 t.Run("parent out of range", func(t *testing.T) {
1017 g := mustParseSynth(t, mk(func(s *synthLayer) { s.parents[2] = []uint32{9} }).bytes())
1018 if _, err := g.appendParents(nil, 2); !errors.Is(err, errGraphCorrupt) {
1019 t.Fatalf("err = %v", err)
1020 }
1021 // A parent equal to the commit's own layer end is rejected, a
1022 // parent in a later position of the same layer is accepted (the
1023 // graph is not required to be topologically ordered by id).
1024 if _, err := g.appendParents(nil, 5); err != nil {
1025 t.Fatal(err)
1026 }
1027 })
1028 t.Run("edge list overrun", func(t *testing.T) {
1029 g := mustParseSynth(t, mk(func(s *synthLayer) {
1030 s.parents[5] = []uint32{0, 1, 2}
1031 }).bytes())
1032 l := &g.layers[0]
1033 // Clear the "last" bit of the final EDGE entry.
1034 last := len(l.edge) - 4
1035 mutable := append([]byte(nil), l.edge...)
1036 mutable[last] &^= 0x80
1037 l.edge = mutable
1038 if _, err := g.appendParents(nil, 5); !errors.Is(err, errGraphCorrupt) {
1039 t.Fatalf("err = %v", err)
1040 }
1041 })
1042 t.Run("missing edge chunk", func(t *testing.T) {
1043 g := mustParseSynth(t, mk(func(s *synthLayer) { s.skipEdge = true }).bytes())
1044 if _, err := g.appendParents(nil, 5); !errors.Is(err, errGraphCorrupt) {
1045 t.Fatalf("err = %v", err)
1046 }
1047 })
1048 t.Run("overflow index out of range", func(t *testing.T) {
1049 g := mustParseSynth(t, mk(func(s *synthLayer) {
1050 s.gda2 = make([]uint32, n)
1051 s.gda2[1] = graphGenOverflow | 3
1052 s.gdo2 = []uint64{1}
1053 }).bytes())
1054 if _, err := g.generation(1); !errors.Is(err, errGraphCorrupt) {
1055 t.Fatalf("err = %v", err)
1056 }
1057 if _, err := g.generation(0); err != nil {
1058 t.Fatal(err)
1059 }
1060 })
1061 t.Run("second parent without first", func(t *testing.T) {
1062 g := mustParseSynth(t, mk(nil).bytes())
1063 l := &g.layers[0]
1064 rec := append([]byte(nil), l.cdat...)
1065 binary.BigEndian.PutUint32(rec[graphHashSize:], graphParentNone)
1066 binary.BigEndian.PutUint32(rec[graphHashSize+4:], 1)
1067 l.cdat = rec
1068 if _, err := g.appendParents(nil, 0); !errors.Is(err, errGraphCorrupt) {
1069 t.Fatalf("err = %v", err)
1070 }
1071 })
1072}
1073
1074func TestGraphParseErrors(t *testing.T) {
1075 good := (&synthLayer{ids: synthIDs(4)}).bytes()
1076 if _, err := parseGraphLayer(good); err != nil {
1077 t.Fatal(err)
1078 }
1079 mut := func(f func(b []byte) []byte) []byte { return f(append([]byte(nil), good...)) }
1080 cases := map[string][]byte{
1081 "empty": nil,
1082 "short": good[:20],
1083 "signature": mut(func(b []byte) []byte { b[0] = 'X'; return b }),
1084 "hash version": mut(func(b []byte) []byte { b[5] = 9; return b }),
1085 "chunk count": mut(func(b []byte) []byte { b[6] = 255; return b }),
1086 "offset past": mut(func(b []byte) []byte { binary.BigEndian.PutUint64(b[12:], 1<<62); return b }),
1087 "offset behind": mut(func(b []byte) []byte { binary.BigEndian.PutUint64(b[12:], 1); return b }),
1088 "dup chunk": mut(func(b []byte) []byte { copy(b[8+12:], b[8:12]); return b }),
1089 "fanout order": mut(func(b []byte) []byte { binary.BigEndian.PutUint32(b[(8+5*12)+4:], 99); return b }),
1090 "truncated": good[:len(good)-30],
1091 }
1092 for name, b := range cases {
1093 if _, err := parseGraphLayer(b); !errors.Is(err, errGraphCorrupt) {
1094 t.Errorf("%s: err = %v, want corrupt", name, err)
1095 }
1096 }
1097 sha256 := mut(func(b []byte) []byte { b[5] = 2; return b })
1098 if _, err := parseGraphLayer(sha256); !errors.Is(err, errGraphUnsupported) {
1099 t.Errorf("sha256: err = %v", err)
1100 }
1101 v2 := mut(func(b []byte) []byte { b[4] = 2; return b })
1102 if _, err := parseGraphLayer(v2); !errors.Is(err, errGraphUnsupported) {
1103 t.Errorf("version 2: err = %v", err)
1104 }
1105 // Every truncation and every single-byte corruption of the header and
1106 // chunk table must be handled without panicking.
1107 for i := range good {
1108 _, _ = parseGraphLayer(good[:i])
1109 }
1110 for i := range min(len(good), 8+6*12) {
1111 for _, v := range []byte{0, 1, 0x7f, 0x80, 0xff} {
1112 b := append([]byte(nil), good...)
1113 b[i] = v
1114 exerciseGraphBytes(b)
1115 }
1116 }
1117}
1118
1119func TestGraphChainParse(t *testing.T) {
1120 h1 := strings.Repeat("ab", 20)
1121 h2 := strings.Repeat("01", 20)
1122 names, err := parseGraphChain([]byte(h1 + "\n" + h2 + "\n"))
1123 if err != nil || len(names) != 2 || names[1][0] != 1 {
1124 t.Fatalf("names = %v, err = %v", names, err)
1125 }
1126 for _, bad := range []string{h1, h1 + "\r\n", strings.Repeat("zz", 20) + "\n", h1 + "\n" + "x\n"} {
1127 if _, err := parseGraphChain([]byte(bad)); !errors.Is(err, errGraphCorrupt) {
1128 t.Errorf("%q: err = %v", bad, err)
1129 }
1130 }
1131 if _, err := parseGraphChain(nil); !errors.Is(err, errNoGraph) {
1132 t.Errorf("empty chain: err = %v", err)
1133 }
1134}
1135
1136func TestGraphChainMismatch(t *testing.T) {
1137 r := newGTRepo(t)
1138 r.commit("a", "a\n")
1139 r.git("commit-graph", "write", "--reachable", "--split=no-merge")
1140 r.commit("b", "b\n")
1141 r.git("commit-graph", "write", "--reachable", "--split=no-merge")
1142 chainPath := filepath.Join(r.objects(), "info", "commit-graphs", "commit-graph-chain")
1143 raw, err := os.ReadFile(chainPath)
1144 if err != nil {
1145 t.Fatal(err)
1146 }
1147 lines := strings.Fields(string(raw))
1148 if len(lines) != 2 {
1149 t.Fatalf("chain = %q", raw)
1150 }
1151 g, err := openCommitGraph(r.objects())
1152 if err != nil {
1153 t.Fatal(err)
1154 }
1155 _ = g.close()
1156
1157 // Reverse: layer 0 would be the top layer, which declares a base.
1158 if err := os.Chmod(chainPath, 0o644); err != nil {
1159 t.Fatal(err)
1160 }
1161 if err := os.WriteFile(chainPath, []byte(lines[1]+"\n"+lines[0]+"\n"), 0o644); err != nil {
1162 t.Fatal(err)
1163 }
1164 if _, err := openCommitGraph(r.objects()); !errors.Is(err, errGraphCorrupt) {
1165 t.Fatalf("reversed chain: err = %v", err)
1166 }
1167 // Top layer alone declares one base but the chain has none.
1168 if err := os.WriteFile(chainPath, []byte(lines[1]+"\n"), 0o644); err != nil {
1169 t.Fatal(err)
1170 }
1171 if _, err := openCommitGraph(r.objects()); !errors.Is(err, errGraphCorrupt) {
1172 t.Fatalf("truncated chain: err = %v", err)
1173 }
1174 // A missing layer file is an error, not a panic.
1175 if err := os.WriteFile(chainPath, []byte(strings.Repeat("0", 40)+"\n"), 0o644); err != nil {
1176 t.Fatal(err)
1177 }
1178 if _, err := openCommitGraph(r.objects()); err == nil {
1179 t.Fatal("missing layer accepted")
1180 }
1181 // Two layers whose base list names the wrong checksum.
1182 if err := os.WriteFile(chainPath, []byte(lines[0]+"\n"+lines[0]+"\n"), 0o644); err != nil {
1183 t.Fatal(err)
1184 }
1185 if _, err := openCommitGraph(r.objects()); !errors.Is(err, errGraphCorrupt) {
1186 t.Fatalf("duplicated layer: err = %v", err)
1187 }
1188}
1189
1190// A layer file whose trailer is not the name the chain gives it is rejected.
1191func TestGraphLayerChecksumMustMatchName(t *testing.T) {
1192 mk := func(sum byte, base []oid) *graphLayer {
1193 s := &synthLayer{ids: synthIDs(3), base: base}
1194 b := s.bytes()
1195 for i := len(b) - graphHashSize; i < len(b); i++ {
1196 b[i] = sum
1197 }
1198 l, err := parseGraphLayer(b)
1199 if err != nil {
1200 t.Fatal(err)
1201 }
1202 return l
1203 }
1204 name := func(b byte) [graphHashSize]byte { return [graphHashSize]byte(bytes.Repeat([]byte{b}, graphHashSize)) }
1205 chain := func(a, b byte) (*commitGraph, error) {
1206 return assembleGraph([]*graphLayer{mk(0xa1, nil), mk(0xb2, []oid{name(0xa1)})},
1207 [][graphHashSize]byte{name(a), name(b)})
1208 }
1209 if _, err := chain(0xa1, 0xb2); err != nil {
1210 t.Fatalf("matching names: %v", err)
1211 }
1212 if _, err := chain(0xa1, 0xb3); !errors.Is(err, errGraphCorrupt) {
1213 t.Errorf("top layer renamed: err = %v", err)
1214 }
1215 // The base list of the top layer names the base correctly, but the base
1216 // file itself carries another checksum.
1217 if _, err := assembleGraph([]*graphLayer{mk(0xee, nil), mk(0xb2, []oid{name(0xa1)})},
1218 [][graphHashSize]byte{name(0xa1), name(0xb2)}); !errors.Is(err, errGraphCorrupt) {
1219 t.Errorf("base layer with another checksum: err = %v", err)
1220 }
1221 // Several layers need chain names.
1222 if _, err := assembleGraph([]*graphLayer{mk(1, nil), mk(2, []oid{name(1)})}, nil); !errors.Is(err, errGraphCorrupt) {
1223 t.Errorf("two layers without names: err = %v", err)
1224 }
1225}
1226
1227// On disk: a layer copied under another name is not accepted as that layer.
1228func TestGraphRenamedLayerRejected(t *testing.T) {
1229 r := newGTRepo(t)
1230 r.commit("a", "a\n")
1231 r.git("commit-graph", "write", "--reachable", "--split")
1232 dir := filepath.Join(r.objects(), "info", "commit-graphs")
1233 chainPath := filepath.Join(dir, "commit-graph-chain")
1234 raw, err := os.ReadFile(chainPath)
1235 if err != nil {
1236 t.Fatal(err)
1237 }
1238 good := strings.TrimSpace(string(raw))
1239 fake := strings.Repeat("0", 40)
1240 b, err := os.ReadFile(filepath.Join(dir, "graph-"+good+".graph"))
1241 if err != nil {
1242 t.Fatal(err)
1243 }
1244 if err := os.WriteFile(filepath.Join(dir, "graph-"+fake+".graph"), b, 0o644); err != nil {
1245 t.Fatal(err)
1246 }
1247 if err := os.Chmod(chainPath, 0o644); err != nil {
1248 t.Fatal(err)
1249 }
1250 if err := os.WriteFile(chainPath, []byte(fake+"\n"), 0o644); err != nil {
1251 t.Fatal(err)
1252 }
1253 if g, err := openCommitGraph(r.objects()); !errors.Is(err, errGraphCorrupt) {
1254 if err == nil {
1255 _ = g.close()
1256 }
1257 t.Fatalf("err = %v, want corrupt", err)
1258 }
1259}
1260
1261// Optional chunks of the wrong size disable their feature only.
1262func TestGraphOptionalChunkSizes(t *testing.T) {
1263 const n = 4
1264 hdr := binary.BigEndian.AppendUint32(nil, 2)
1265 hdr = binary.BigEndian.AppendUint32(hdr, 7)
1266 hdr = binary.BigEndian.AppendUint32(hdr, 10)
1267 mk := func() *synthLayer {
1268 s := &synthLayer{ids: synthIDs(n), parents: make([][]uint32, n), times: make([]int64, n), levels: []uint32{5, 6, 7, 8}}
1269 s.times = []int64{100, 200, 300, 400}
1270 s.parents[1] = []uint32{0}
1271 s.gda2 = []uint32{0, 1, 2, 3}
1272 s.bdat = append(hdr[:12:12], 0x00)
1273 s.bidx = []uint32{1, 1, 1, 1}
1274 return s
1275 }
1276 t.Run("ok", func(t *testing.T) {
1277 g := mustParseSynth(t, mk().bytes())
1278 defer func() { _ = g.close() }()
1279 if !g.hasGenerationV2() || !g.layers[0].hasBloom {
1280 t.Fatal("features missing on a good layer")
1281 }
1282 if v, _ := g.generation(1); v != 201 {
1283 t.Fatalf("generation = %d, want 201", v)
1284 }
1285 })
1286 t.Run("GDA2", func(t *testing.T) {
1287 for _, size := range []int{n - 1, n + 1} {
1288 s := mk()
1289 s.gda2 = make([]uint32, size)
1290 g := mustParseSynth(t, s.bytes())
1291 if g.hasGenerationV2() {
1292 t.Errorf("GDA2 of %d entries accepted", size)
1293 }
1294 if v, err := g.generation(1); err != nil || v != 6 {
1295 t.Errorf("generation = %d, %v, want the level 6", v, err)
1296 }
1297 if !g.layers[0].hasBloom {
1298 t.Error("a bad GDA2 disabled the Bloom filters")
1299 }
1300 if _, err := g.appendParents(nil, 1); err != nil {
1301 t.Error(err)
1302 }
1303 _ = g.close()
1304 }
1305 })
1306 t.Run("BIDX", func(t *testing.T) {
1307 s := mk()
1308 s.bidx = s.bidx[:n-1]
1309 g := mustParseSynth(t, s.bytes())
1310 defer func() { _ = g.close() }()
1311 if g.layers[0].hasBloom || g.hasBloom(0) {
1312 t.Error("short BIDX accepted")
1313 }
1314 if !g.hasGenerationV2() {
1315 t.Error("a bad BIDX disabled the generation")
1316 }
1317 })
1318 t.Run("BDAT", func(t *testing.T) {
1319 s := mk()
1320 s.bdat = s.bdat[:bloomHeaderSize-1]
1321 g := mustParseSynth(t, s.bytes())
1322 defer func() { _ = g.close() }()
1323 if g.layers[0].hasBloom || g.hasBloom(0) {
1324 t.Error("short BDAT accepted")
1325 }
1326 if !g.hasGenerationV2() {
1327 t.Error("a bad BDAT disabled the generation")
1328 }
1329 })
1330}
1331
1332func TestGraphCorruptFiles(t *testing.T) {
1333 r := newGTRepo(t)
1334 r.commit("a", "a\n")
1335 r.git("commit-graph", "write", "--reachable", "--changed-paths")
1336 path := filepath.Join(r.objects(), "info", "commit-graph")
1337 good, err := os.ReadFile(path)
1338 if err != nil {
1339 t.Fatal(err)
1340 }
1341 if err := os.Chmod(path, 0o644); err != nil {
1342 t.Fatal(err)
1343 }
1344 for _, b := range [][]byte{good[:10], {}, []byte("CGPH"), bytes.Repeat([]byte{0xff}, 200)} {
1345 if err := os.WriteFile(path, b, 0o644); err != nil {
1346 t.Fatal(err)
1347 }
1348 if _, err := openCommitGraph(r.objects()); err == nil {
1349 t.Fatalf("accepted %d corrupt bytes", len(b))
1350 }
1351 }
1352 // A directory in place of the file must not panic or be mapped.
1353 _ = os.Remove(path)
1354 if err := os.Mkdir(path, 0o755); err != nil {
1355 t.Fatal(err)
1356 }
1357 if _, err := openCommitGraph(r.objects()); err == nil {
1358 t.Fatal("directory accepted")
1359 }
1360}
1361
1362// ---- fuzzing --------------------------------------------------------------
1363
1364// exerciseGraphBytes runs every accessor over a layer parsed from data, alone
1365// and stacked on itself, and must never panic.
1366func exerciseGraphBytes(data []byte) {
1367 l, err := parseGraphLayer(data)
1368 if err != nil {
1369 return
1370 }
1371 one := *l
1372 one.numBase = 0
1373 two := one
1374 two.base = one.n
1375 for _, g := range []*commitGraph{
1376 {layers: []graphLayer{one}, total: one.n, genV2: one.gda2 != nil},
1377 {layers: []graphLayer{one, two}, total: 2 * one.n, genV2: one.gda2 != nil},
1378 } {
1379 exerciseGraph(g)
1380 }
1381}
1382
1383// exerciseGraph runs every accessor over (up to 256 positions of) g.
1384func exerciseGraph(g *commitGraph) {
1385 var buf [4]uint32
1386 n := min(g.total, 256)
1387 for pos := range n {
1388 id, _ := g.commitID(pos)
1389 g.lookup(id)
1390 _, _ = g.rootTree(pos)
1391 _, _ = g.commitTime(pos)
1392 _, _ = g.topoLevel(pos)
1393 _, _ = g.generation(pos)
1394 _, _ = g.appendParents(buf[:0], pos)
1395 g.maybeChanged(pos, []byte("src/main.go"))
1396 g.maybeChanged(pos, []byte("caf\xc3\xa9/"))
1397 g.hasBloom(pos)
1398 }
1399 _, _ = g.commitID(g.total)
1400 _, _ = g.appendParents(nil, g.total+1)
1401 g.maybeChanged(g.total, nil)
1402 g.lookup(oid{0xff, 0xff})
1403 g.lookup(oid{})
1404}
1405
1406func graphSeedFiles(tb testing.TB) map[string][]byte {
1407 tb.Helper()
1408 entries, err := os.ReadDir(filepath.Join("testdata", "graph"))
1409 if err != nil {
1410 tb.Fatal(err)
1411 }
1412 seeds := map[string][]byte{}
1413 for _, e := range entries {
1414 if !strings.HasSuffix(e.Name(), ".graph") {
1415 continue
1416 }
1417 b, err := os.ReadFile(filepath.Join("testdata", "graph", e.Name()))
1418 if err != nil {
1419 tb.Fatal(err)
1420 }
1421 seeds[e.Name()] = b
1422 }
1423 if len(seeds) == 0 {
1424 tb.Fatal("no fuzz seeds in testdata/graph")
1425 }
1426 return seeds
1427}
1428
1429func FuzzGraphFile(f *testing.F) {
1430 for _, b := range graphSeedFiles(f) {
1431 f.Add(b)
1432 f.Add(b[:len(b)/2])
1433 }
1434 f.Fuzz(func(t *testing.T, data []byte) { exerciseGraphBytes(data) })
1435}
1436
1437func FuzzGraphChain(f *testing.F) {
1438 f.Add([]byte(strings.Repeat("ab", 20) + "\n"))
1439 f.Add([]byte(strings.Repeat("ab", 20) + "\n" + strings.Repeat("cd", 20) + "\n"))
1440 f.Add([]byte("\n"))
1441 f.Fuzz(func(t *testing.T, data []byte) {
1442 names, err := parseGraphChain(data)
1443 if err == nil && len(names)*41 != len(data) {
1444 t.Fatalf("parsed %d names from %d bytes", len(names), len(data))
1445 }
1446 })
1447}
1448
1449// graphChainSeeds returns, for each committed split chain, the chain file
1450// content and its layer files (base first).
1451func graphChainSeeds(tb testing.TB) (chains [][]byte, layers [][2][]byte) {
1452 tb.Helper()
1453 seeds := graphSeedFiles(tb)
1454 for _, prefix := range []string{"split-bloom-v1", "split-bloom-v2", "split-gen1"} {
1455 l0, l1 := seeds[prefix+"-layer0.graph"], seeds[prefix+"-layer1.graph"]
1456 if l0 == nil || l1 == nil {
1457 tb.Fatalf("seed %s missing", prefix)
1458 }
1459 chain := hex.EncodeToString(l0[len(l0)-graphHashSize:]) + "\n" +
1460 hex.EncodeToString(l1[len(l1)-graphHashSize:]) + "\n"
1461 chains = append(chains, []byte(chain))
1462 layers = append(layers, [2][]byte{l0, l1})
1463 }
1464 return chains, layers
1465}
1466
1467// assembleChainBytes is openCommitGraphChain on in-memory files: layer i of
1468// the chain is files[i%len(files)].
1469func assembleChainBytes(chain []byte, files ...[]byte) (*commitGraph, error) {
1470 names, err := parseGraphChain(chain)
1471 if err != nil {
1472 return nil, err
1473 }
1474 layers := make([]*graphLayer, 0, len(names))
1475 for i := range names {
1476 l, err := parseGraphLayer(files[i%len(files)])
1477 if err != nil {
1478 return nil, err
1479 }
1480 layers = append(layers, l)
1481 }
1482 return assembleGraph(layers, names)
1483}
1484
1485func TestGraphChainSeedsAssemble(t *testing.T) {
1486 chains, layers := graphChainSeeds(t)
1487 for i := range chains {
1488 g, err := assembleChainBytes(chains[i], layers[i][0], layers[i][1])
1489 if err != nil {
1490 t.Fatalf("seed %d: %v", i, err)
1491 }
1492 if g.numLayers() != 2 || g.numCommits() == 0 {
1493 t.Errorf("seed %d: %d layers, %d commits", i, g.numLayers(), g.numCommits())
1494 }
1495 exerciseGraph(g)
1496 // Swapped layers or a damaged name must be refused, not crash.
1497 if _, err := assembleChainBytes(chains[i], layers[i][1], layers[i][0]); err == nil {
1498 t.Errorf("seed %d: swapped layers accepted", i)
1499 }
1500 bad := append([]byte(nil), chains[i]...)
1501 bad[3] ^= 1
1502 if _, err := assembleChainBytes(bad, layers[i][0], layers[i][1]); !errors.Is(err, errGraphCorrupt) {
1503 t.Errorf("seed %d: wrong layer name: err = %v", i, err)
1504 }
1505 }
1506}
1507
1508// FuzzGraphAssemble reaches parseGraphChain, parseGraphLayer and
1509// assembleGraph together: a chain file and two layer files (used round-robin
1510// for the layers the chain lists).
1511func FuzzGraphAssemble(f *testing.F) {
1512 chains, layers := graphChainSeeds(f)
1513 for i := range chains {
1514 f.Add(chains[i], layers[i][0], layers[i][1])
1515 f.Add(chains[i][:41], layers[i][0], layers[i][1]) // base layer alone
1516 f.Add(append(chains[i][:41:41], chains[i][:41]...), layers[i][0], layers[i][0])
1517 }
1518 f.Add([]byte(strings.Repeat("00", 20)+"\n"), (&synthLayer{ids: synthIDs(3)}).bytes(), []byte{})
1519 f.Fuzz(func(t *testing.T, chain, l0, l1 []byte) {
1520 g, err := assembleChainBytes(chain, l0, l1)
1521 if err != nil {
1522 return
1523 }
1524 if g.numLayers() == 0 || g.numLayers() > graphMaxLayers {
1525 t.Fatalf("%d layers", g.numLayers())
1526 }
1527 exerciseGraph(g)
1528 })
1529}
1530
1531// TestGraphSeedsParse checks the committed seeds stay valid files.
1532func TestGraphSeedsParse(t *testing.T) {
1533 for name, b := range graphSeedFiles(t) {
1534 l, err := parseGraphLayer(b)
1535 if err != nil {
1536 t.Errorf("%s: %v", name, err)
1537 continue
1538 }
1539 exerciseGraphBytes(b)
1540 _ = l
1541 }
1542}
1543
1544// TestWriteGraphSeeds regenerates testdata/graph with the git binary:
1545//
1546// ERMITE_GIT_UPDATE_SEEDS=1 go test -run TestWriteGraphSeeds
1547func TestWriteGraphSeeds(t *testing.T) {
1548 if os.Getenv("ERMITE_GIT_UPDATE_SEEDS") == "" {
1549 t.Skip("set ERMITE_GIT_UPDATE_SEEDS=1 to regenerate testdata/graph")
1550 }
1551 out := filepath.Join("testdata", "graph")
1552 if err := os.MkdirAll(out, 0o755); err != nil {
1553 t.Fatal(err)
1554 }
1555 save := func(name string, b []byte) {
1556 if err := os.WriteFile(filepath.Join(out, name), b, 0o644); err != nil {
1557 t.Fatal(err)
1558 }
1559 }
1560 copyLayers := func(prefix string, r *gtRepo) {
1561 dir := filepath.Join(r.objects(), "info")
1562 if b, err := os.ReadFile(filepath.Join(dir, "commit-graph")); err == nil {
1563 save(prefix+".graph", b)
1564 return
1565 }
1566 chain, err := os.ReadFile(filepath.Join(dir, "commit-graphs", "commit-graph-chain"))
1567 if err != nil {
1568 t.Fatal(err)
1569 }
1570 for i, h := range strings.Fields(string(chain)) {
1571 b, err := os.ReadFile(filepath.Join(dir, "commit-graphs", "graph-"+h+".graph"))
1572 if err != nil {
1573 t.Fatal(err)
1574 }
1575 save(fmt.Sprintf("%s-layer%d.graph", prefix, i), b)
1576 }
1577 }
1578 for _, c := range []gcase{
1579 {name: "single-nobloom"},
1580 {name: "single-bloom-v2", bloom: true, cfg: []string{"commitGraph.changedPathsVersion=2"}},
1581 {name: "split-bloom-v2", split: true, bloom: true, cfg: []string{"commitGraph.changedPathsVersion=2"}},
1582 {name: "split-bloom-v1", split: true, bloom: true, cfg: []string{"commitGraph.changedPathsVersion=1"}},
1583 {name: "split-gen1", split: true, cfg: []string{"commitGraph.generationVersion=1"}},
1584 } {
1585 r := newGTRepo(t)
1586 r.stageOne()
1587 r.writeGraph(c)
1588 r.stageTwo()
1589 r.writeGraph(c)
1590 copyLayers(c.name, r)
1591 }
1592 // Synthetic: wide octopus, overflow generation, Bloom edge cases.
1593 s := &synthLayer{ids: synthIDs(12), parents: make([][]uint32, 12), times: make([]int64, 12)}
1594 s.parents[11] = []uint32{0, 1, 2, 3, 4, 5}
1595 s.gda2 = make([]uint32, 12)
1596 s.gda2[3] = graphGenOverflow
1597 s.gdo2 = []uint64{1 << 40}
1598 hdr := binary.BigEndian.AppendUint32(nil, 2)
1599 hdr = binary.BigEndian.AppendUint32(hdr, 7)
1600 hdr = binary.BigEndian.AppendUint32(hdr, 10)
1601 s.bdat = append(hdr, 0x00, 0xff, 0x12, 0x34, 0x56, 0x78, 0x9a, 0xbc, 0xde, 0xf0)
1602 s.bidx = []uint32{1, 2, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10}
1603 save("synthetic.graph", s.bytes())
1604}
1605
1606// ---- benchmarks -----------------------------------------------------------
1607
1608// fastImportRepo creates a bare repo with n commits (a merge every 50) using
1609// git fast-import, and writes its split commit-graph.
1610func fastImportRepo(tb testing.TB, n int) string {
1611 tb.Helper()
1612 requireGit(tb)
1613 dir := tb.TempDir()
1614 graphGit(tb, dir, 0, "init", "-q", "--bare", "-b", "main")
1615 cmd := exec.Command("git", "fast-import", "--quiet")
1616 cmd.Dir = dir
1617 cmd.Env = graphGitEnv(0)
1618 var stderr bytes.Buffer
1619 cmd.Stderr = &stderr
1620 in, err := cmd.StdinPipe()
1621 if err != nil {
1622 tb.Fatal(err)
1623 }
1624 if err := cmd.Start(); err != nil {
1625 tb.Fatal(err)
1626 }
1627 w := bufio.NewWriter(in)
1628 for i := 1; i <= n; i++ {
1629 msg := "commit " + strconv.Itoa(i)
1630 _, _ = fmt.Fprintf(w, "commit refs/heads/main\nmark :%d\ncommitter T <t@example.com> %d +0000\ndata %d\n%s\n", i, 1_600_000_000+i*30, len(msg), msg)
1631 if i > 1 {
1632 _, _ = fmt.Fprintf(w, "from :%d\n", i-1)
1633 }
1634 if i > 60 && i%50 == 0 {
1635 _, _ = fmt.Fprintf(w, "merge :%d\n", i-30)
1636 }
1637 for _, p := range []string{
1638 fmt.Sprintf("d%d/f%d.txt", i%17, i%5),
1639 fmt.Sprintf("pkg%d/sub%d/g%d.go", i%7, i%3, i),
1640 } {
1641 body := "v" + strconv.Itoa(i) + "\n"
1642 _, _ = fmt.Fprintf(w, "M 644 inline %s\ndata %d\n%s", p, len(body), body)
1643 }
1644 _, _ = w.WriteString("\n")
1645 }
1646 if err := w.Flush(); err != nil {
1647 tb.Fatal(err)
1648 }
1649 _ = in.Close()
1650 if err := cmd.Wait(); err != nil {
1651 tb.Fatalf("fast-import: %v\n%s", err, stderr.String())
1652 }
1653 graphGit(tb, dir, 0, "commit-graph", "write", "--reachable", "--changed-paths", "--split")
1654 return dir
1655}
1656
1657func benchGraph(b *testing.B) (*commitGraph, []oid) {
1658 dir := fastImportRepo(b, 5000)
1659 g, err := openCommitGraph(filepath.Join(dir, "objects"))
1660 if err != nil {
1661 b.Fatal(err)
1662 }
1663 b.Cleanup(func() { _ = g.close() })
1664 ids := make([]oid, g.numCommits())
1665 for i := range ids {
1666 ids[i], _ = g.commitID(uint32(i))
1667 }
1668 return g, ids
1669}
1670
1671func BenchmarkGraphLookup(b *testing.B) {
1672 g, ids := benchGraph(b)
1673 b.ReportAllocs()
1674 i := 0
1675 for b.Loop() {
1676 if _, ok := g.lookup(ids[i]); !ok {
1677 b.Fatal("miss")
1678 }
1679 if i++; i == len(ids) {
1680 i = 0
1681 }
1682 }
1683}
1684
1685func BenchmarkGraphParents(b *testing.B) {
1686 g, _ := benchGraph(b)
1687 var buf [8]uint32
1688 n := g.numCommits()
1689 b.ReportAllocs()
1690 var pos uint32
1691 for b.Loop() {
1692 if _, err := g.appendParents(buf[:0], pos); err != nil {
1693 b.Fatal(err)
1694 }
1695 if pos++; pos == n {
1696 pos = 0
1697 }
1698 }
1699}
1700
1701func BenchmarkGraphCommitData(b *testing.B) {
1702 g, _ := benchGraph(b)
1703 n := g.numCommits()
1704 b.ReportAllocs()
1705 var pos uint32
1706 for b.Loop() {
1707 if _, err := g.generation(pos); err != nil {
1708 b.Fatal(err)
1709 }
1710 if _, err := g.commitTime(pos); err != nil {
1711 b.Fatal(err)
1712 }
1713 if _, err := g.rootTree(pos); err != nil {
1714 b.Fatal(err)
1715 }
1716 if pos++; pos == n {
1717 pos = 0
1718 }
1719 }
1720}