From 6f1914f5db33a0d4431069eb9378cac68daf8cc0 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 9 Mar 2023 16:43:39 -0700 Subject: btrfstree: Rethink 'Path' yet again --- lib/btrfs/btrfstree/path.go | 211 +++++++++++++++++++++----------------------- 1 file changed, 101 insertions(+), 110 deletions(-) (limited to 'lib/btrfs/btrfstree/path.go') diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go index 1335b76..537df9a 100644 --- a/lib/btrfs/btrfstree/path.go +++ b/lib/btrfs/btrfstree/path.go @@ -5,8 +5,8 @@ package btrfstree import ( + "context" "fmt" - "io" "strings" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" @@ -14,11 +14,10 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/containers" ) -// Path is a path from the superblock (i.e. the root of the btrfs -// system) to the a node or item within one of the btrees in the -// system. +// Path is a path from the superblock or a ROOT_ITEM to a node or +// item within one of the btrees in the system. // -// - The first element will always have an ItemSlot of -1. +// - The first element will always have a FromSlot of -1. // // - For .Item() callbacks, the last element will always have a // NodeAddr of 0. @@ -27,164 +26,156 @@ import ( // // [superblock: tree=B, lvl=3, gen=6] // | -// | <------------------------------------------ pathElem={from_tree:B, from_slot=-1, -// | to_addr:0x01, to_gen=6, to_lvl=3} +// | <------------------------------------------ PathRoot={Tree:B, +// | ToAddr:0x01, ToGen=6, ToLvl=3} // +[0x01]-------------+ // | lvl=3 gen=6 own=B | // +-+-+-+-+-+-+-+-+-+-+ // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <------------------------------ pathElem:{from_tree:B, from_slot:7, -// | to_addr:0x02, to_gen:5, to_lvl:2} +// | <------------------------------ PathKP={FromTree:B, FromSlot:7, +// | ToAddr:0x02, ToGen:5, ToLvl:2} // +[0x02]--------------+ // | lvl=2 gen=5 own=B | // +-+-+-+-+-+-+-+-+-+-+ // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <-------------------- pathElem={from_tree:B, from_slot:6, -// | to_addr:0x03, to_gen:5, to_lvl:1} +// | <-------------------- PathKP={FromTree:B, FromSlot:6, +// | ToAddr:0x03, ToGen:5, ToLvl:1} // +[0x03]-------------+ // | lvl=1 gen=5 own=A | // +-+-+-+-+-+-+-+-+-+-+ // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <---------------- pathElem={from_tree:A, from_slot:3, -// | to_addr:0x04, to_gen:2, lvl:0} +// | <---------------- PathKP={FromTree:A, FromSlot:3, +// | ToAddr:0x04, ToGen:2, ToLvl:0} // +[0x04]-------------+ // | lvl=0 gen=2 own=A | // +-+-+-+-+-+-+-+-+-+-+ // |0|1|2|3|4|5|6|7|8|9| // +-+-+-+-+-+-+-+-+-+-+ // | -// | <--------------- pathElem={from_tree:A, from_slot:1, -// | to_addr:0, to_gen: 0, to_lvl:0} +// | <--------------- PathItem={FromTree:A, FromSlot:1} +// | // [item] type Path []PathElem -// A PathElem essentially represents a KeyPointer. -type PathElem struct { - // FromTree is the owning tree ID of the parent node; or the - // well-known tree ID if this is the root. - FromTree btrfsprim.ObjID - // FromItemSlot is the index of this KeyPointer in the parent - // Node; or -1 if this is the root and there is no KeyPointer. - FromItemSlot int +// A PathElem is either a PathRoot, a PathKP, or a PathItem. +type PathElem interface { + isPathElem() +} - // ToNodeAddr is the address of the node that the KeyPointer - // points at, or 0 if this is a leaf item and nothing is being - // pointed at. - ToNodeAddr btrfsvol.LogicalAddr - // ToNodeGeneration is the expected generation of the node at - // ToNodeAddr, or 0 if this is a leaf item and nothing is - // being pointed at. - ToNodeGeneration btrfsprim.Generation - // ToNodeLevel is the expected level of the node at - // ToNodeAddr, or 0 if this is a leaf item and nothing is - // being pointed at. - ToNodeLevel uint8 - // ToKey is either - // - btrfprim.Key{} if this is the root node being pointed - // to, - // - the KeyPointer.Key if this is a non-root node being - // pointed to, or - // - the key of the leaf item being pointed to. - ToKey btrfsprim.Key +type PathRoot struct { + Tree Tree + // It should be no surprise that these 4 members mimic the 4 + // members of a 'RawTree'. + TreeID btrfsprim.ObjID + ToAddr btrfsvol.LogicalAddr + ToGeneration btrfsprim.Generation + ToLevel uint8 +} + +func (PathRoot) isPathElem() {} + +type PathKP struct { + // From the containing Node. + FromTree btrfsprim.ObjID + FromSlot int + // From the KP itself. + ToAddr btrfsvol.LogicalAddr + ToGeneration btrfsprim.Generation + ToMinKey btrfsprim.Key + // From the structure of the tree. ToMaxKey btrfsprim.Key + ToLevel uint8 } -func (elem PathElem) writeNodeTo(w io.Writer) { - fmt.Fprintf(w, "node:%d@%v", elem.ToNodeLevel, elem.ToNodeAddr) +func (PathKP) isPathElem() {} + +type PathItem struct { + // From the containing Node. + FromTree btrfsprim.ObjID + FromSlot int + // From the Item itself. + ToKey btrfsprim.Key } +func (PathItem) isPathElem() {} + func (path Path) String() string { if len(path) == 0 { return "(empty-path)" } var ret strings.Builder - fmt.Fprintf(&ret, "%s->", path[0].FromTree.Format(btrfsprim.ROOT_TREE_OBJECTID)) - if len(path) == 1 && path[0] == (PathElem{FromTree: path[0].FromTree, FromItemSlot: -1}) { - ret.WriteString("(empty-path)") - } else { - path[0].writeNodeTo(&ret) - } - for _, elem := range path[1:] { - fmt.Fprintf(&ret, "[%v]", elem.FromItemSlot) - if elem.ToNodeAddr != 0 { - ret.WriteString("->") - elem.writeNodeTo(&ret) + for _, elem := range path { + switch elem := elem.(type) { + case PathRoot: + fmt.Fprintf(&ret, "%s->node:%d@%v", + elem.TreeID.Format(btrfsprim.ROOT_TREE_OBJECTID), + elem.ToLevel, elem.ToAddr) + case PathKP: + fmt.Fprintf(&ret, "[%d]->node:%d@%v", + elem.FromSlot, + elem.ToLevel, elem.ToAddr) + case PathItem: + // fmt.Fprintf(&ret, "[%d]->item:%v", + // elem.FromSlot, + // elem.ToKey) + fmt.Fprintf(&ret, "[%d]", + elem.FromSlot) + default: + panic(fmt.Errorf("should not happen: unexpected PathElem type: %T", elem)) } } return ret.String() } -func (path Path) DeepCopy() Path { - return append(Path(nil), path...) -} - // NodeExpectations returns the address to read and the expectations // to have when reading the node pointed to by this Path. // // `ok` is false if the path is empty or if this Path points to an // item rather than a node. -func (path Path) NodeExpectations(fs NodeFile) (_ btrfsvol.LogicalAddr, _ NodeExpectations, ok bool) { - if path.Node(-1).ToNodeAddr == 0 && path.Node(-1).ToNodeGeneration == 0 && path.Node(-1).ToNodeLevel == 0 { +func (path Path) NodeExpectations(ctx context.Context, failOpen bool) (_ btrfsvol.LogicalAddr, _ NodeExpectations, ok bool) { + if len(path) == 0 { return 0, NodeExpectations{}, false } - - checkOwner := func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error { - var treeParents []btrfsprim.ObjID - - tree := path.Node(-1).FromTree - for { - if owner == tree { - // OK! - return nil - } - - treeParents = append(treeParents, tree) - parent, parentGen, parentOK := fs.ParentTree(tree) - if !parentOK { - // Failed look up parent info; fail open. - return nil - } - - if parent == 0 { - // End of the line. - return fmt.Errorf("expected owner in %v but claims to have owner=%v", - treeParents, owner) - } - if gen > parentGen { - return fmt.Errorf("claimed owner=%v might be acceptable in this tree (if generation<=%v) but not with claimed generation=%v", - owner, parentGen, gen) - } - tree = parent - } + firstElem, ok := path[0].(PathRoot) + if !ok { + panic(fmt.Errorf("should not happen: first PathElem is not PathRoot: %T", path[0])) + } + switch lastElem := path[len(path)-1].(type) { + case PathRoot: + return lastElem.ToAddr, NodeExpectations{ + LAddr: containers.OptionalValue(lastElem.ToAddr), + Level: containers.OptionalValue(lastElem.ToLevel), + Generation: containers.OptionalValue(lastElem.ToGeneration), + Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error { + return firstElem.Tree.TreeCheckOwner(ctx, failOpen, owner, gen) + }, + MinItem: containers.OptionalValue(btrfsprim.Key{}), + MaxItem: containers.OptionalValue(btrfsprim.MaxKey), + }, true + case PathKP: + return lastElem.ToAddr, NodeExpectations{ + LAddr: containers.OptionalValue(lastElem.ToAddr), + Level: containers.OptionalValue(lastElem.ToLevel), + Generation: containers.OptionalValue(lastElem.ToGeneration), + Owner: func(owner btrfsprim.ObjID, gen btrfsprim.Generation) error { + return firstElem.Tree.TreeCheckOwner(ctx, failOpen, owner, gen) + }, + MinItem: containers.OptionalValue(lastElem.ToMinKey), + MaxItem: containers.OptionalValue(lastElem.ToMaxKey), + }, true + case PathItem: + return 0, NodeExpectations{}, false + default: + panic(fmt.Errorf("should not happen: unexpected PathElem type: %T", lastElem)) } - - return path.Node(-1).ToNodeAddr, NodeExpectations{ - LAddr: containers.OptionalValue(path.Node(-1).ToNodeAddr), - Level: containers.OptionalValue(path.Node(-1).ToNodeLevel), - Generation: containers.OptionalValue(path.Node(-1).ToNodeGeneration), - Owner: checkOwner, - MinItem: containers.OptionalValue(path.Node(-1).ToKey), - MaxItem: containers.OptionalValue(path.Node(-1).ToMaxKey), - }, true } func (path Path) Parent() Path { return path[:len(path)-1] } - -// Node is returns an element from the path; `path.Node(x)` is like -// `&path[x]`, but negative values of x move down from the end of path -// (similar to how lists work in many other languages, such as -// Python). -func (path Path) Node(x int) *PathElem { - if x < 0 { - x += len(path) - } - return &path[x] -} -- cgit v1.2.3-2-g168b