summaryrefslogtreecommitdiff
path: root/lib/btrfs/btrfstree/path.go
diff options
context:
space:
mode:
Diffstat (limited to 'lib/btrfs/btrfstree/path.go')
-rw-r--r--lib/btrfs/btrfstree/path.go211
1 files changed, 101 insertions, 110 deletions
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]
-}
generated by cgit v1.1-4-g5e80 at 2024-07-02 16:53:35 +0000