diff options
Diffstat (limited to 'lib/btrfs/btrfstree/path.go')
-rw-r--r-- | lib/btrfs/btrfstree/path.go | 178 |
1 files changed, 110 insertions, 68 deletions
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go index c07d8a0..537df9a 100644 --- a/lib/btrfs/btrfstree/path.go +++ b/lib/btrfs/btrfstree/path.go @@ -5,19 +5,19 @@ package btrfstree import ( + "context" "fmt" - "io" "strings" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "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. @@ -26,114 +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() +} + +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 +} - // 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 +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(ctx context.Context, failOpen bool) (_ btrfsvol.LogicalAddr, _ NodeExpectations, ok bool) { + if len(path) == 0 { + return 0, NodeExpectations{}, false + } + 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)) + } } 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] -} |