Function TestFindPathsToKey_CycleDetected

internal/surgeon/xray_test.go:42–84

TestFindPathsToKey_CycleDetected corrupts the db so that a branch page points at its own ancestor, then verifies that FindPathsToKey returns an error instead of recursing until stack overflow. See issue #701 for the real-world corruption pattern (power-off creating a page cycle).

(t *testing.T)

// error instead of recursing until stack overflow. See issue #701 for the
// real-world corruption pattern (power-off creating a page cycle).
func TestFindPathsToKey_CycleDetected(t *testing.T) {
	db := btesting.MustCreateDB(t)
	require.NoError(t,
		db.Fill([]byte("data"), 1, 500,
			func(tx int, k int) []byte { return []byte(fmt.Sprintf("%04d", k)) },
			func(tx int, k int) []byte { return make([]byte, 100) },
		))
	require.NoError(t, db.Close())

	// Find the path to an arbitrary key so we can pick a branch ancestor
	// and one of its leaf descendants to corrupt.
	navigator := surgeon.NewXRay(db.Path())
	paths, err := navigator.FindPathsToKey([]byte("0001"))
	require.NoError(t, err)
	require.NotEmpty(t, paths)
	path := paths[0]
	require.GreaterOrEqual(t, len(path), 2, "need at least one branch above the leaf")

	// Overwrite the leaf page with a copy of its branch ancestor. The
	// rewritten page is still a branch and now references its own pgid
	// through the ancestor's element list, forming a cycle.
	ancestor := path[len(path)-2]
	leaf := path[len(path)-1]
	require.NoError(t, surgeon.CopyPage(db.Path(), ancestor, leaf))

	// Confirm the ancestor actually lists the leaf as one of its children,
	// so copying creates a real cycle rather than two disjoint branches.
	ancestorPage, _, err := guts_cli.ReadPage(db.Path(), uint64(ancestor))
	require.NoError(t, err)
	require.True(t, ancestorPage.IsBranchPage())
	var hasLeafAsChild bool
	for i := uint16(0); i < ancestorPage.Count(); i++ {
		if ancestorPage.BranchPageElement(i).Pgid() == common.Pgid(leaf) {
			hasLeafAsChild = true
			break
		}
	}
	require.True(t, hasLeafAsChild, "expected ancestor to reference the leaf directly")

	_, err = surgeon.NewXRay(db.Path()).FindPathsToKey([]byte("0001"))
	require.Error(t, err)
	require.Contains(t, err.Error(), "cycle detected")
}

// TestFindPathsToKey_MultipleBuckets ensures the shared visited map in
// traverse does not suppress legitimate paths when the same key appears