btrfs: Split off btrfstree and btrfsprim sub-packages

10 files changed, 1464 insertions, 0 deletions

diff --git a/lib/btrfs/btrfstree/ops.go b/lib/btrfs/btrfstree/ops.go
new file mode 100644
index 0000000..83c08c4
--- /dev/null
+++ b/lib/btrfs/btrfstree/ops.go
@@ -0,0 +1,519 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfstree
+
+import (
+	"context"
+	"errors"
+	"fmt"
+	iofs "io/fs"
+	"math"
+
+	"github.com/datawire/dlib/derror"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"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/diskio"
+	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
+)
+
+type Trees interface {
+	// TreeWalk walks a tree, triggering callbacks for every node,
+	// key-pointer, and item; as well as for any errors encountered.
+	//
+	// If the tree is valid, then everything is walked in key-order; but if
+	// the tree is broken, then ordering is not guaranteed.
+	//
+	// Canceling the Context causes TreeWalk to return early; no
+	// values from the Context are used.
+	//
+	// The lifecycle of callbacks is:
+	//
+	//     001 .PreNode()
+	//     002 (read node)
+	//     003 .Node() (or .BadNode())
+	//         for item in node.items:
+	//           if btrfsprim:
+	//     004     .PreKeyPointer()
+	//     005     (recurse)
+	//     006     .PostKeyPointer()
+	//           else:
+	//     004     .Item() (or .BadItem())
+	//     007 .PostNode()
+	TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler)
+
+	TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error)
+	TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (Item, error) // size is math.MaxUint32 for key-pointers
+
+	// If some items are able to be read, but there is an error reading the
+	// full set, then it might return *both* a list of items and an error.
+	//
+	// If no such item is found, an error that is io/fs.ErrNotExist is
+	// returned.
+	TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]Item, error) // size is math.MaxUint32 for key-pointers
+}
+
+type TreeWalkHandler struct {
+	// Callbacks for entire nodes.
+	//
+	// If any of these return an error that is io/fs.SkipDir, the
+	// node immediately stops getting processed; if PreNode, Node,
+	// or BadNode return io/fs.SkipDir then key pointers and items
+	// within the node are not processed.
+	PreNode  func(TreePath) error
+	Node     func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error
+	BadNode  func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) error
+	PostNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error
+	// Callbacks for items on btrfsprim nodes
+	PreKeyPointer  func(TreePath, KeyPointer) error
+	PostKeyPointer func(TreePath, KeyPointer) error
+	// Callbacks for items on leaf nodes
+	Item    func(TreePath, Item) error
+	BadItem func(TreePath, Item) error
+}
+
+type TreeError struct {
+	Path TreePath
+	Err  error
+}
+
+func (e *TreeError) Unwrap() error { return e.Err }
+
+func (e *TreeError) Error() string {
+	return fmt.Sprintf("%v: %v", e.Path, e.Err)
+}
+
+type NodeSource interface {
+	Superblock() (*Superblock, error)
+	ReadNode(TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error)
+}
+
+type TreesImpl struct {
+	NodeSource
+}
+
+// TreeWalk implements the 'Trees' interface.
+func (fs TreesImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) {
+	sb, err := fs.Superblock()
+	if err != nil {
+		errHandle(&TreeError{Path: TreePath{{FromTree: treeID}}, Err: err})
+	}
+	rootInfo, err := LookupTreeRoot(fs, *sb, treeID)
+	if err != nil {
+		errHandle(&TreeError{Path: TreePath{{FromTree: treeID}}, Err: err})
+		return
+	}
+	fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs)
+}
+
+// TreeWalk is a utility function to help with implementing the 'Trees'
+// interface.
+func (fs TreesImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) {
+	path := TreePath{{
+		FromTree:       rootInfo.TreeID,
+		FromGeneration: rootInfo.Generation,
+		FromItemIdx:    -1,
+		ToNodeAddr:     rootInfo.RootNode,
+		ToNodeLevel:    rootInfo.Level,
+	}}
+	fs.treeWalk(ctx, path, errHandle, cbs)
+}
+
+func (fs TreesImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) {
+	if ctx.Err() != nil {
+		return
+	}
+	if path.Node(-1).ToNodeAddr == 0 {
+		return
+	}
+
+	if cbs.PreNode != nil {
+		if err := cbs.PreNode(path); err != nil {
+			if errors.Is(err, iofs.SkipDir) {
+				return
+			}
+			errHandle(&TreeError{Path: path, Err: err})
+		}
+		if ctx.Err() != nil {
+			return
+		}
+	}
+	node, err := fs.ReadNode(path)
+	if ctx.Err() != nil {
+		return
+	}
+	if err != nil && node != nil && cbs.BadNode != nil {
+		// opportunity to fix the node
+		err = cbs.BadNode(path, node, err)
+		if errors.Is(err, iofs.SkipDir) {
+			return
+		}
+	}
+	if err != nil {
+		errHandle(&TreeError{Path: path, Err: err})
+	} else {
+		if cbs.Node != nil {
+			if err := cbs.Node(path, node); err != nil {
+				if errors.Is(err, iofs.SkipDir) {
+					return
+				}
+				errHandle(&TreeError{Path: path, Err: err})
+			}
+		}
+	}
+	if ctx.Err() != nil {
+		return
+	}
+	if node != nil {
+		for i, item := range node.Data.BodyInternal {
+			itemPath := append(path, TreePathElem{
+				FromTree:       node.Data.Head.Owner,
+				FromGeneration: node.Data.Head.Generation,
+				FromItemIdx:    i,
+				ToNodeAddr:     item.BlockPtr,
+				ToNodeLevel:    node.Data.Head.Level - 1,
+			})
+			if cbs.PreKeyPointer != nil {
+				if err := cbs.PreKeyPointer(itemPath, item); err != nil {
+					errHandle(&TreeError{Path: itemPath, Err: err})
+				}
+				if ctx.Err() != nil {
+					return
+				}
+			}
+			fs.treeWalk(ctx, itemPath, errHandle, cbs)
+			if cbs.PostKeyPointer != nil {
+				if err := cbs.PostKeyPointer(itemPath, item); err != nil {
+					errHandle(&TreeError{Path: itemPath, Err: err})
+				}
+				if ctx.Err() != nil {
+					return
+				}
+			}
+		}
+		for i, item := range node.Data.BodyLeaf {
+			itemPath := append(path, TreePathElem{
+				FromTree:       node.Data.Head.Owner,
+				FromGeneration: node.Data.Head.Generation,
+				FromItemIdx:    i,
+			})
+			if errBody, isErr := item.Body.(btrfsitem.Error); isErr {
+				if cbs.BadItem == nil {
+					errHandle(&TreeError{Path: itemPath, Err: errBody.Err})
+				} else {
+					if err := cbs.BadItem(itemPath, item); err != nil {
+						errHandle(&TreeError{Path: itemPath, Err: err})
+					}
+					if ctx.Err() != nil {
+						return
+					}
+				}
+			} else {
+				if cbs.Item != nil {
+					if err := cbs.Item(itemPath, item); err != nil {
+						errHandle(&TreeError{Path: itemPath, Err: err})
+					}
+					if ctx.Err() != nil {
+						return
+					}
+				}
+			}
+		}
+	}
+	if cbs.PostNode != nil {
+		if err := cbs.PostNode(path, node); err != nil {
+			if errors.Is(err, iofs.SkipDir) {
+				return
+			}
+			errHandle(&TreeError{Path: path, Err: err})
+		}
+	}
+}
+
+func (fs TreesImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+	path := TreePath{{
+		FromTree:       treeRoot.TreeID,
+		FromGeneration: treeRoot.Generation,
+		FromItemIdx:    -1,
+		ToNodeAddr:     treeRoot.RootNode,
+		ToNodeLevel:    treeRoot.Level,
+	}}
+	for {
+		if path.Node(-1).ToNodeAddr == 0 {
+			return TreePath{}, nil, iofs.ErrNotExist
+		}
+		node, err := fs.ReadNode(path)
+		if err != nil {
+			return TreePath{}, nil, err
+		}
+
+		if node.Data.Head.Level > 0 {
+			// btrfsprim node
+
+			// Search for the right-most node.Data.BodyInternal item for which
+			// `fn(item.Key) >= 0`.
+			//
+			//    + + + + 0 - - - -
+			//
+			// There may or may not be a value that returns '0'.
+			//
+			// i.e. find the highest value that isn't too high.
+			lastGood, ok := slices.SearchHighest(node.Data.BodyInternal, func(kp KeyPointer) int {
+				return slices.Min(fn(kp.Key, math.MaxUint32), 0) // don't return >0; a key can't be "too low"
+			})
+			if !ok {
+				return TreePath{}, nil, iofs.ErrNotExist
+			}
+			path = append(path, TreePathElem{
+				FromTree:       node.Data.Head.Owner,
+				FromGeneration: node.Data.Head.Generation,
+				FromItemIdx:    lastGood,
+				ToNodeAddr:     node.Data.BodyInternal[lastGood].BlockPtr,
+				ToNodeLevel:    node.Data.Head.Level - 1,
+			})
+		} else {
+			// leaf node
+
+			// Search for a member of node.Data.BodyLeaf for which
+			// `fn(item.Head.Key) == 0`.
+			//
+			//    + + + + 0 - - - -
+			//
+			// Such an item might not exist; in this case, return nil/ErrNotExist.
+			// Multiple such items might exist; in this case, it does not matter which
+			// is returned.
+			//
+			// Implement this search as a binary search.
+			idx, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int {
+				return fn(item.Key, item.BodySize)
+			})
+			if !ok {
+				return TreePath{}, nil, iofs.ErrNotExist
+			}
+			path = append(path, TreePathElem{
+				FromTree:       node.Data.Head.Owner,
+				FromGeneration: node.Data.Head.Generation,
+				FromItemIdx:    idx,
+			})
+			return path, node, nil
+		}
+	}
+}
+
+func (fs TreesImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+	var err error
+	path = path.DeepCopy()
+
+	// go up
+	for path.Node(-1).FromItemIdx < 1 {
+		path = path.Parent()
+		if len(path) == 0 {
+			return TreePath{}, nil, nil
+		}
+	}
+	// go left
+	path.Node(-1).FromItemIdx--
+	if path.Node(-1).ToNodeAddr != 0 {
+		if node.Addr != path.Node(-2).ToNodeAddr {
+			node, err = fs.ReadNode(path.Parent())
+			if err != nil {
+				return TreePath{}, nil, err
+			}
+			path.Node(-1).ToNodeAddr = node.Data.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr
+		}
+	}
+	// go down
+	for path.Node(-1).ToNodeAddr != 0 {
+		if node.Addr != path.Node(-1).ToNodeAddr {
+			node, err = fs.ReadNode(path)
+			if err != nil {
+				return TreePath{}, nil, err
+			}
+		}
+		if node.Data.Head.Level > 0 {
+			path = append(path, TreePathElem{
+				FromTree:       node.Data.Head.Owner,
+				FromGeneration: node.Data.Head.Generation,
+				FromItemIdx:    len(node.Data.BodyInternal) - 1,
+				ToNodeAddr:     node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr,
+				ToNodeLevel:    node.Data.Head.Level - 1,
+			})
+		} else {
+			path = append(path, TreePathElem{
+				FromTree:       node.Data.Head.Owner,
+				FromGeneration: node.Data.Head.Generation,
+				FromItemIdx:    len(node.Data.BodyLeaf) - 1,
+			})
+		}
+	}
+	// return
+	if node.Addr != path.Node(-2).ToNodeAddr {
+		node, err = fs.ReadNode(path.Parent())
+		if err != nil {
+			return TreePath{}, nil, err
+		}
+	}
+	return path, node, nil
+}
+
+func (fs TreesImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+	var err error
+	path = path.DeepCopy()
+
+	// go up
+	if node.Addr != path.Node(-2).ToNodeAddr {
+		node, err = fs.ReadNode(path.Parent())
+		if err != nil {
+			return TreePath{}, nil, err
+		}
+		path.Node(-2).ToNodeLevel = node.Data.Head.Level
+	}
+	for path.Node(-1).FromItemIdx+1 >= int(node.Data.Head.NumItems) {
+		path = path.Parent()
+		if len(path) == 1 {
+			return TreePath{}, nil, nil
+		}
+		if node.Addr != path.Node(-2).ToNodeAddr {
+			node, err = fs.ReadNode(path.Parent())
+			if err != nil {
+				return TreePath{}, nil, err
+			}
+			path.Node(-2).ToNodeLevel = node.Data.Head.Level
+		}
+	}
+	// go right
+	path.Node(-1).FromItemIdx++
+	if path.Node(-1).ToNodeAddr != 0 {
+		if node.Addr != path.Node(-2).ToNodeAddr {
+			node, err = fs.ReadNode(path.Parent())
+			if err != nil {
+				return TreePath{}, nil, err
+			}
+			path.Node(-1).ToNodeAddr = node.Data.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr
+		}
+	}
+	// go down
+	for path.Node(-1).ToNodeAddr != 0 {
+		if node.Addr != path.Node(-1).ToNodeAddr {
+			node, err = fs.ReadNode(path)
+			if err != nil {
+				return TreePath{}, nil, err
+			}
+			path.Node(-1).ToNodeLevel = node.Data.Head.Level
+		}
+		if node.Data.Head.Level > 0 {
+			path = append(path, TreePathElem{
+				FromTree:       node.Data.Head.Owner,
+				FromGeneration: node.Data.Head.Generation,
+				FromItemIdx:    0,
+				ToNodeAddr:     node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr,
+				ToNodeLevel:    node.Data.Head.Level - 1,
+			})
+		} else {
+			path = append(path, TreePathElem{
+				FromTree:       node.Data.Head.Owner,
+				FromGeneration: node.Data.Head.Generation,
+				FromItemIdx:    0,
+			})
+		}
+	}
+	// return
+	if node.Addr != path.Node(-2).ToNodeAddr {
+		node, err = fs.ReadNode(path.Parent())
+		if err != nil {
+			return TreePath{}, nil, err
+		}
+	}
+	return path, node, nil
+}
+
+// TreeSearch implements the 'Trees' interface.
+func (fs TreesImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) {
+	sb, err := fs.Superblock()
+	if err != nil {
+		return Item{}, err
+	}
+	rootInfo, err := LookupTreeRoot(fs, *sb, treeID)
+	if err != nil {
+		return Item{}, err
+	}
+	path, node, err := fs.treeSearch(*rootInfo, fn)
+	if err != nil {
+		return Item{}, err
+	}
+	return node.Data.BodyLeaf[path.Node(-1).FromItemIdx], nil
+}
+
+// KeySearch returns a comparator suitable to be passed to TreeSearch.
+func KeySearch(fn func(btrfsprim.Key) int) func(btrfsprim.Key, uint32) int {
+	return func(key btrfsprim.Key, _ uint32) int {
+		return fn(key)
+	}
+}
+
+// TreeLookup implements the 'Trees' interface.
+func (fs TreesImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) {
+	item, err := fs.TreeSearch(treeID, KeySearch(key.Cmp))
+	if err != nil {
+		err = fmt.Errorf("item with key=%v: %w", key, err)
+	}
+	return item, err
+}
+
+// TreeSearchAll implements the 'Trees' interface.
+func (fs TreesImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) {
+	sb, err := fs.Superblock()
+	if err != nil {
+		return nil, err
+	}
+	rootInfo, err := LookupTreeRoot(fs, *sb, treeID)
+	if err != nil {
+		return nil, err
+	}
+	middlePath, middleNode, err := fs.treeSearch(*rootInfo, fn)
+	if err != nil {
+		return nil, err
+	}
+	middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemIdx]
+
+	var ret = []Item{middleItem}
+	var errs derror.MultiError
+	for prevPath, prevNode := middlePath, middleNode; true; {
+		prevPath, prevNode, err = fs.prev(prevPath, prevNode)
+		if err != nil {
+			errs = append(errs, err)
+			break
+		}
+		if len(prevPath) == 0 {
+			break
+		}
+		prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemIdx]
+		if fn(prevItem.Key, prevItem.BodySize) != 0 {
+			break
+		}
+		ret = append(ret, prevItem)
+	}
+	slices.Reverse(ret)
+	for nextPath, nextNode := middlePath, middleNode; true; {
+		nextPath, nextNode, err = fs.next(nextPath, nextNode)
+		if err != nil {
+			errs = append(errs, err)
+			break
+		}
+		if len(nextPath) == 0 {
+			break
+		}
+		nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemIdx]
+		if fn(nextItem.Key, nextItem.BodySize) != 0 {
+			break
+		}
+		ret = append(ret, nextItem)
+	}
+	if errs != nil {
+		err = errs
+	}
+	return ret, err
+}
diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go
new file mode 100644
index 0000000..99461a4
--- /dev/null
+++ b/lib/btrfs/btrfstree/path.go
@@ -0,0 +1,129 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfstree
+
+import (
+	"fmt"
+	"io"
+	"strings"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+)
+
+// - The first element will always have an ItemIdx of -1.
+//
+//   - For .Item() callbacks, the last element will always have a
+//     NodeAddr of 0.
+//
+// For example, a path through a tree, with the associated PathElems:
+//
+//	[superblock: tree=B, lvl=3, gen=6]
+//	     |
+//	     | <------------------------------------------ pathElem={from_tree:B, from_gen=6, from_idx=-1,
+//	     |                                                       to_addr:0x01, to_lvl=3}
+//	  +[0x01]-------------+
+//	  | lvl=3 gen=6 own=B |
+//	  +-+-+-+-+-+-+-+-+-+-+
+//	  |0|1|2|3|4|5|6|7|8|9|
+//	  +-+-+-+-+-+-+-+-+-+-+
+//	                 |
+//	                 | <------------------------------ pathElem:{from_tree:B, from_gen:6, from_idx:7,
+//	                 |                                           to_addr:0x02, to_lvl:2}
+//	              +[0x02]--------------+
+//	              | lvl=2 gen=5 own=B  |
+//	              +-+-+-+-+-+-+-+-+-+-+
+//	              |0|1|2|3|4|5|6|7|8|9|
+//	              +-+-+-+-+-+-+-+-+-+-+
+//	                           |
+//	                           | <-------------------- pathElem={from_tree:B, from_gen:5, from_idx:6,
+//	                           |                                 to_addr:0x03, to_lvl:1}
+//	                        +[0x03]-------------+
+//	                        | lvl=1 gen=5 own=A |
+//	                        +-+-+-+-+-+-+-+-+-+-+
+//	                        |0|1|2|3|4|5|6|7|8|9|
+//	                        +-+-+-+-+-+-+-+-+-+-+
+//	                               |
+//	                               | <---------------- pathElem={from_tree:A, from_gen:5, from_idx:3,
+//	                               |                             to_addr:0x04, to_lvl:0}
+//	                             +[0x04]-------------+
+//	                             | lvl=0 gen=2 own=A |
+//	                             +-+-+-+-+-+-+-+-+-+-+
+//	                             |0|1|2|3|4|5|6|7|8|9|
+//	                             +-+-+-+-+-+-+-+-+-+-+
+//	                                |
+//	                                | <--------------- pathElem={from_tree:A, from_gen:2, from_idx:1,
+//	                                |                            to_addr:0, to_lvl:0}
+//	                              [item]
+type TreePath []TreePathElem
+
+// A TreePathElem essentially represents a KeyPointer.  If there is an
+// error looking up the tree root, everything but FromTree is zero.
+type TreePathElem 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
+	// FromGeneration is the generation of the parent node the
+	// parent node; or generation stored in the superblock if this
+	// is the root.
+	FromGeneration btrfsprim.Generation
+	// FromItemIdx is the index of this KeyPointer in the parent
+	// Node; or -1 if this is the root and there is no KeyPointer.
+	FromItemIdx int
+
+	// 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
+	// ToNodeLevel is the expected or actual level of the node at
+	// ToNodeAddr, or 0 if this is a leaf item and nothing is
+	// being pointed at.
+	ToNodeLevel uint8
+}
+
+func (elem TreePathElem) writeNodeTo(w io.Writer) {
+	fmt.Fprintf(w, "node:%d@%v", elem.ToNodeLevel, elem.ToNodeAddr)
+}
+
+func (path TreePath) String() string {
+	if len(path) == 0 {
+		return "(empty-path)"
+	} else {
+		var ret strings.Builder
+		fmt.Fprintf(&ret, "%s->", path[0].FromTree.Format(btrfsitem.ROOT_ITEM_KEY))
+		if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree}) {
+			ret.WriteString("(empty-path)")
+		} else {
+			path[0].writeNodeTo(&ret)
+		}
+		for _, elem := range path[1:] {
+			fmt.Fprintf(&ret, "[%v]", elem.FromItemIdx)
+			if elem.ToNodeAddr != 0 {
+				ret.WriteString("->")
+				elem.writeNodeTo(&ret)
+			}
+		}
+		return ret.String()
+	}
+}
+
+func (path TreePath) DeepCopy() TreePath {
+	return append(TreePath(nil), path...)
+}
+
+func (path TreePath) Parent() TreePath {
+	return path[:len(path)-1]
+}
+
+// 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 TreePath) Node(x int) *TreePathElem {
+	if x < 0 {
+		x += len(path)
+	}
+	return &path[x]
+}
diff --git a/lib/btrfs/btrfstree/root.go b/lib/btrfs/btrfstree/root.go
new file mode 100644
index 0000000..41aac69
--- /dev/null
+++ b/lib/btrfs/btrfstree/root.go
@@ -0,0 +1,81 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfstree
+
+import (
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+)
+
+// A TreeRoot is more-or-less a btrfsitem.Root, but simpler; returned by
+// LookupTreeRoot.
+type TreeRoot struct {
+	TreeID     btrfsprim.ObjID
+	RootNode   btrfsvol.LogicalAddr
+	Level      uint8
+	Generation btrfsprim.Generation
+}
+
+// LookupTreeRoot is a utility function to help with implementing the 'Trees'
+// interface.
+func LookupTreeRoot(fs Trees, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) {
+	switch treeID {
+	case btrfsprim.ROOT_TREE_OBJECTID:
+		return &TreeRoot{
+			TreeID:     treeID,
+			RootNode:   sb.RootTree,
+			Level:      sb.RootLevel,
+			Generation: sb.Generation, // XXX: same generation as LOG_TREE?
+		}, nil
+	case btrfsprim.CHUNK_TREE_OBJECTID:
+		return &TreeRoot{
+			TreeID:     treeID,
+			RootNode:   sb.ChunkTree,
+			Level:      sb.ChunkLevel,
+			Generation: sb.ChunkRootGeneration,
+		}, nil
+	case btrfsprim.TREE_LOG_OBJECTID:
+		return &TreeRoot{
+			TreeID:     treeID,
+			RootNode:   sb.LogTree,
+			Level:      sb.LogLevel,
+			Generation: sb.Generation, // XXX: same generation as ROOT_TREE?
+		}, nil
+	case btrfsprim.BLOCK_GROUP_TREE_OBJECTID:
+		return &TreeRoot{
+			TreeID:     treeID,
+			RootNode:   sb.BlockGroupRoot,
+			Level:      sb.BlockGroupRootLevel,
+			Generation: sb.BlockGroupRootGeneration,
+		}, nil
+	default:
+		rootItem, err := fs.TreeSearch(btrfsprim.ROOT_TREE_OBJECTID, func(key btrfsprim.Key, _ uint32) int {
+			if key.ObjectID == treeID && key.ItemType == btrfsitem.ROOT_ITEM_KEY {
+				return 0
+			}
+			return btrfsprim.Key{
+				ObjectID: treeID,
+				ItemType: btrfsitem.ROOT_ITEM_KEY,
+				Offset:   0,
+			}.Cmp(key)
+		})
+		if err != nil {
+			return nil, err
+		}
+		rootItemBody, ok := rootItem.Body.(btrfsitem.Root)
+		if !ok {
+			return nil, fmt.Errorf("malformed ROOT_ITEM for tree %v", treeID)
+		}
+		return &TreeRoot{
+			TreeID:     treeID,
+			RootNode:   rootItemBody.ByteNr,
+			Level:      rootItemBody.Level,
+			Generation: rootItemBody.Generation,
+		}, nil
+	}
+}
diff --git a/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4
new file mode 100644
index 0000000..a96f559
--- /dev/null
+++ b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4
@@ -0,0 +1,2 @@
+go test fuzz v1
+[]byte("0")
diff --git a/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca
new file mode 100644
index 0000000..d5c153f
--- /dev/null
+++ b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca
@@ -0,0 +1,2 @@
+go test fuzz v1
+[]byte("000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\x00\x00\x00\x000")
diff --git a/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5
new file mode 100644
index 0000000..6a2309e
--- /dev/null
+++ b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5
@@ -0,0 +1,2 @@
+go test fuzz v1
+[]byte("00000000000000000000000000000000000000000000000000000000")
diff --git a/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9
new file mode 100644
index 0000000..50b960e
--- /dev/null
+++ b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9
@@ -0,0 +1,2 @@
+go test fuzz v1
+[]byte("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")
diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go
new file mode 100644
index 0000000..aecdf9c
--- /dev/null
+++ b/lib/btrfs/btrfstree/types_node.go
@@ -0,0 +1,454 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfstree
+
+import (
+	"encoding/binary"
+	"errors"
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
+	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
+	"git.lukeshu.com/btrfs-progs-ng/lib/fmtutil"
+	"git.lukeshu.com/btrfs-progs-ng/lib/slices"
+)
+
+type NodeFlags uint64
+
+func (NodeFlags) BinaryStaticSize() int {
+	return 7
+}
+func (f NodeFlags) MarshalBinary() ([]byte, error) {
+	var bs [8]byte
+	binary.LittleEndian.PutUint64(bs[:], uint64(f))
+	return bs[:7], nil
+}
+func (f *NodeFlags) UnmarshalBinary(dat []byte) (int, error) {
+	var bs [8]byte
+	copy(bs[:7], dat[:7])
+	*f = NodeFlags(binary.LittleEndian.Uint64(bs[:]))
+	return 7, nil
+}
+
+var (
+	_ binstruct.StaticSizer = NodeFlags(0)
+	_ binstruct.Marshaler   = NodeFlags(0)
+	_ binstruct.Unmarshaler = (*NodeFlags)(nil)
+)
+
+const (
+	NodeWritten = NodeFlags(1 << iota)
+	NodeReloc
+)
+
+var nodeFlagNames = []string{
+	"WRITTEN",
+	"RELOC",
+}
+
+func (f NodeFlags) Has(req NodeFlags) bool { return f&req == req }
+func (f NodeFlags) String() string         { return fmtutil.BitfieldString(f, nodeFlagNames, fmtutil.HexLower) }
+
+type BackrefRev uint8
+
+const (
+	OldBackrefRev   = BackrefRev(iota)
+	MixedBackrefRev = BackrefRev(iota)
+)
+
+// Node: main //////////////////////////////////////////////////////////////////////////////////////
+
+type Node struct {
+	// Some context from the parent filesystem
+	Size         uint32            // superblock.NodeSize
+	ChecksumType btrfssum.CSumType // superblock.ChecksumType
+
+	// The node's header (always present)
+	Head NodeHeader
+
+	// The node's body (which one of these is present depends on
+	// the node's type, as specified in the header)
+	BodyInternal []KeyPointer // for btrfsprim nodes
+	BodyLeaf     []Item       // for leave nodes
+
+	Padding []byte
+}
+
+type NodeHeader struct {
+	Checksum      btrfssum.CSum        `bin:"off=0x0,  siz=0x20"`
+	MetadataUUID  btrfsprim.UUID       `bin:"off=0x20, siz=0x10"`
+	Addr          btrfsvol.LogicalAddr `bin:"off=0x30, siz=0x8"` // Logical address of this node
+	Flags         NodeFlags            `bin:"off=0x38, siz=0x7"`
+	BackrefRev    BackrefRev           `bin:"off=0x3f, siz=0x1"`
+	ChunkTreeUUID btrfsprim.UUID       `bin:"off=0x40, siz=0x10"`
+	Generation    btrfsprim.Generation `bin:"off=0x50, siz=0x8"`
+	Owner         btrfsprim.ObjID      `bin:"off=0x58, siz=0x8"` // The ID of the tree that contains this node
+	NumItems      uint32               `bin:"off=0x60, siz=0x4"` // [ignored-when-writing]
+	Level         uint8                `bin:"off=0x64, siz=0x1"` // 0 for leaf nodes, >=1 for btrfsprim nodes
+	binstruct.End `bin:"off=0x65"`
+}
+
+// MaxItems returns the maximum possible valid value of
+// .Head.NumItems.
+func (node Node) MaxItems() uint32 {
+	bodyBytes := node.Size - uint32(binstruct.StaticSize(NodeHeader{}))
+	if node.Head.Level > 0 {
+		return bodyBytes / uint32(binstruct.StaticSize(KeyPointer{}))
+	} else {
+		return bodyBytes / uint32(binstruct.StaticSize(ItemHeader{}))
+	}
+}
+
+func (node Node) MinItem() (btrfsprim.Key, bool) {
+	if node.Head.Level > 0 {
+		if len(node.BodyInternal) == 0 {
+			return btrfsprim.Key{}, false
+		}
+		return node.BodyInternal[0].Key, true
+	} else {
+		if len(node.BodyLeaf) == 0 {
+			return btrfsprim.Key{}, false
+		}
+		return node.BodyLeaf[0].Key, true
+	}
+}
+
+func (node Node) MaxItem() (btrfsprim.Key, bool) {
+	if node.Head.Level > 0 {
+		if len(node.BodyInternal) == 0 {
+			return btrfsprim.Key{}, false
+		}
+		return node.BodyInternal[len(node.BodyInternal)-1].Key, true
+	} else {
+		if len(node.BodyLeaf) == 0 {
+			return btrfsprim.Key{}, false
+		}
+		return node.BodyLeaf[len(node.BodyLeaf)-1].Key, true
+	}
+}
+
+func (node Node) CalculateChecksum() (btrfssum.CSum, error) {
+	data, err := binstruct.Marshal(node)
+	if err != nil {
+		return btrfssum.CSum{}, err
+	}
+	return node.ChecksumType.Sum(data[binstruct.StaticSize(btrfssum.CSum{}):])
+}
+
+func (node Node) ValidateChecksum() error {
+	stored := node.Head.Checksum
+	calced, err := node.CalculateChecksum()
+	if err != nil {
+		return err
+	}
+	if calced != stored {
+		return fmt.Errorf("node checksum mismatch: stored=%v calculated=%v",
+			stored, calced)
+	}
+	return nil
+}
+
+func (node *Node) UnmarshalBinary(nodeBuf []byte) (int, error) {
+	*node = Node{
+		Size:         uint32(len(nodeBuf)),
+		ChecksumType: node.ChecksumType,
+	}
+	if len(nodeBuf) <= binstruct.StaticSize(NodeHeader{}) {
+		return 0, fmt.Errorf("size must be greater than %v, but is %v",
+			binstruct.StaticSize(NodeHeader{}),
+			len(nodeBuf))
+	}
+	n, err := binstruct.Unmarshal(nodeBuf, &node.Head)
+	if err != nil {
+		return n, err
+	} else if n != binstruct.StaticSize(NodeHeader{}) {
+		return n, fmt.Errorf("header consumed %v bytes but expected %v",
+			n, binstruct.StaticSize(NodeHeader{}))
+	}
+	if node.Head.Level > 0 {
+		_n, err := node.unmarshalInternal(nodeBuf[n:])
+		n += _n
+		if err != nil {
+			return n, fmt.Errorf("btrfsprim: %w", err)
+		}
+	} else {
+		_n, err := node.unmarshalLeaf(nodeBuf[n:])
+		n += _n
+		if err != nil {
+			return n, fmt.Errorf("leaf: %w", err)
+		}
+	}
+	if n != len(nodeBuf) {
+		return n, fmt.Errorf("left over data: got %v bytes but only consumed %v",
+			len(nodeBuf), n)
+	}
+	return n, nil
+}
+
+func (node Node) MarshalBinary() ([]byte, error) {
+	if node.Size == 0 {
+		return nil, fmt.Errorf(".Size must be set")
+	}
+	if node.Size <= uint32(binstruct.StaticSize(NodeHeader{})) {
+		return nil, fmt.Errorf(".Size must be greater than %v, but is %v",
+			binstruct.StaticSize(NodeHeader{}),
+			node.Size)
+	}
+	if node.Head.Level > 0 {
+		node.Head.NumItems = uint32(len(node.BodyInternal))
+	} else {
+		node.Head.NumItems = uint32(len(node.BodyLeaf))
+	}
+
+	buf := make([]byte, node.Size)
+
+	if bs, err := binstruct.Marshal(node.Head); err != nil {
+		return buf, err
+	} else if len(bs) != binstruct.StaticSize(NodeHeader{}) {
+		return nil, fmt.Errorf("header is %v bytes but expected %v",
+			len(bs), binstruct.StaticSize(NodeHeader{}))
+	} else {
+		copy(buf, bs)
+	}
+
+	if node.Head.Level > 0 {
+		if err := node.marshalInternalTo(buf[binstruct.StaticSize(NodeHeader{}):]); err != nil {
+			return buf, err
+		}
+	} else {
+		if err := node.marshalLeafTo(buf[binstruct.StaticSize(NodeHeader{}):]); err != nil {
+			return buf, err
+		}
+	}
+
+	return buf, nil
+}
+
+// Node: "btrfsprim" ////////////////////////////////////////////////////////////////////////////////
+
+type KeyPointer struct {
+	Key           btrfsprim.Key        `bin:"off=0x0, siz=0x11"`
+	BlockPtr      btrfsvol.LogicalAddr `bin:"off=0x11, siz=0x8"`
+	Generation    btrfsprim.Generation `bin:"off=0x19, siz=0x8"`
+	binstruct.End `bin:"off=0x21"`
+}
+
+func (node *Node) unmarshalInternal(bodyBuf []byte) (int, error) {
+	n := 0
+	for i := uint32(0); i < node.Head.NumItems; i++ {
+		var item KeyPointer
+		_n, err := binstruct.Unmarshal(bodyBuf[n:], &item)
+		n += _n
+		if err != nil {
+			return n, fmt.Errorf("item %v: %w", i, err)
+		}
+		node.BodyInternal = append(node.BodyInternal, item)
+	}
+	node.Padding = bodyBuf[n:]
+	return len(bodyBuf), nil
+}
+
+func (node *Node) marshalInternalTo(bodyBuf []byte) error {
+	n := 0
+	for i, item := range node.BodyInternal {
+		bs, err := binstruct.Marshal(item)
+		if err != nil {
+			return fmt.Errorf("item %v: %w", i, err)
+		}
+		if copy(bodyBuf[n:], bs) < len(bs) {
+			return fmt.Errorf("item %v: not enough space: need at least %v+%v=%v bytes, but only have %v",
+				i, n, len(bs), n+len(bs), len(bodyBuf))
+		}
+		n += len(bs)
+	}
+	if copy(bodyBuf[n:], node.Padding) < len(node.Padding) {
+		return fmt.Errorf("padding: not enough space: need at least %v+%v=%v bytes, but only have %v",
+			n, len(node.Padding), n+len(node.Padding), len(bodyBuf))
+	}
+	return nil
+}
+
+// Node: "leaf" ////////////////////////////////////////////////////////////////////////////////////
+
+type Item struct {
+	Key      btrfsprim.Key
+	BodySize uint32 // [ignored-when-writing]
+	Body     btrfsitem.Item
+}
+
+type ItemHeader struct {
+	Key           btrfsprim.Key `bin:"off=0x0, siz=0x11"`
+	DataOffset    uint32        `bin:"off=0x11, siz=0x4"` // [ignored-when-writing] relative to the end of the header (0x65)
+	DataSize      uint32        `bin:"off=0x15, siz=0x4"` // [ignored-when-writing]
+	binstruct.End `bin:"off=0x19"`
+}
+
+func (node *Node) unmarshalLeaf(bodyBuf []byte) (int, error) {
+	head := 0
+	tail := len(bodyBuf)
+	for i := uint32(0); i < node.Head.NumItems; i++ {
+		var itemHead ItemHeader
+		n, err := binstruct.Unmarshal(bodyBuf[head:], &itemHead)
+		head += n
+		if err != nil {
+			return 0, fmt.Errorf("item %v: head: %w", i, err)
+		}
+		if head > tail {
+			return 0, fmt.Errorf("item %v: head: end_offset=%#x is in the body section (offset>%#x)",
+				i, head, tail)
+		}
+
+		dataOff := int(itemHead.DataOffset)
+		if dataOff < head {
+			return 0, fmt.Errorf("item %v: body: beg_offset=%#x is in the head section (offset<%#x)",
+				i, dataOff, head)
+		}
+		dataSize := int(itemHead.DataSize)
+		if dataOff+dataSize != tail {
+			return 0, fmt.Errorf("item %v: body: end_offset=%#x is not cur_tail=%#x)",
+				i, dataOff+dataSize, tail)
+		}
+		tail = dataOff
+		dataBuf := bodyBuf[dataOff : dataOff+dataSize]
+
+		node.BodyLeaf = append(node.BodyLeaf, Item{
+			Key:      itemHead.Key,
+			BodySize: itemHead.DataSize,
+			Body:     btrfsitem.UnmarshalItem(itemHead.Key, node.ChecksumType, dataBuf),
+		})
+	}
+
+	node.Padding = bodyBuf[head:tail]
+	return len(bodyBuf), nil
+}
+
+func (node *Node) marshalLeafTo(bodyBuf []byte) error {
+	head := 0
+	tail := len(bodyBuf)
+	for i, item := range node.BodyLeaf {
+		itemBodyBuf, err := binstruct.Marshal(item.Body)
+		if err != nil {
+			return fmt.Errorf("item %v: body: %w", i, err)
+		}
+		itemHeadBuf, err := binstruct.Marshal(ItemHeader{
+			Key:        item.Key,
+			DataSize:   uint32(len(itemBodyBuf)),
+			DataOffset: uint32(tail - len(itemBodyBuf)),
+		})
+		if err != nil {
+			return fmt.Errorf("item %v: head: %w", i, err)
+		}
+
+		if tail-head < len(itemHeadBuf)+len(itemBodyBuf) {
+			return fmt.Errorf("item %v: not enough space: need at least (head_len:%v)+(body_len:%v)=%v free bytes, but only have %v",
+				i, len(itemHeadBuf), len(itemBodyBuf), len(itemHeadBuf)+len(itemBodyBuf), tail-head)
+		}
+
+		copy(bodyBuf[head:], itemHeadBuf)
+		head += len(itemHeadBuf)
+		tail -= len(itemBodyBuf)
+		copy(bodyBuf[tail:], itemBodyBuf)
+	}
+	if copy(bodyBuf[head:tail], node.Padding) < len(node.Padding) {
+		return fmt.Errorf("padding: not enough space: need at least %v free bytes, but only have %v",
+			len(node.Padding), tail-head)
+	}
+	return nil
+}
+
+func (node *Node) LeafFreeSpace() uint32 {
+	if node.Head.Level > 0 {
+		panic(fmt.Errorf("Node.LeafFreeSpace: not a leaf node"))
+	}
+	freeSpace := node.Size
+	freeSpace -= uint32(binstruct.StaticSize(NodeHeader{}))
+	for _, item := range node.BodyLeaf {
+		freeSpace -= uint32(binstruct.StaticSize(ItemHeader{}))
+		bs, _ := binstruct.Marshal(item.Body)
+		freeSpace -= uint32(len(bs))
+	}
+	return freeSpace
+}
+
+// Tie Nodes in to the FS //////////////////////////////////////////////////////////////////////////
+
+var ErrNotANode = errors.New("does not look like a node")
+
+type NodeExpectations struct {
+	LAddr containers.Optional[btrfsvol.LogicalAddr]
+	// Things knowable from the parent.
+	Level         containers.Optional[uint8]
+	MaxGeneration containers.Optional[btrfsprim.Generation]
+	Owner         []btrfsprim.ObjID
+}
+
+func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp NodeExpectations) (*diskio.Ref[Addr, Node], error) {
+	nodeBuf := make([]byte, sb.NodeSize)
+	if _, err := fs.ReadAt(nodeBuf, addr); err != nil {
+		return nil, err
+	}
+
+	// parse (early)
+
+	nodeRef := &diskio.Ref[Addr, Node]{
+		File: fs,
+		Addr: addr,
+		Data: Node{
+			Size:         sb.NodeSize,
+			ChecksumType: sb.ChecksumType,
+		},
+	}
+	if _, err := binstruct.Unmarshal(nodeBuf, &nodeRef.Data.Head); err != nil {
+		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err)
+	}
+
+	// sanity checking
+
+	if nodeRef.Data.Head.MetadataUUID != sb.EffectiveMetadataUUID() {
+		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, ErrNotANode)
+	}
+
+	stored := nodeRef.Data.Head.Checksum
+	calced, err := nodeRef.Data.ChecksumType.Sum(nodeBuf[binstruct.StaticSize(btrfssum.CSum{}):])
+	if err != nil {
+		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err)
+	}
+	if stored != calced {
+		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: looks like a node but is corrupt: checksum mismatch: stored=%v calculated=%v",
+			addr, stored, calced)
+	}
+
+	if exp.LAddr.OK && nodeRef.Data.Head.Addr != exp.LAddr.Val {
+		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: read from laddr=%v but claims to be at laddr=%v",
+			addr, exp.LAddr.Val, nodeRef.Data.Head.Addr)
+	}
+	if exp.Level.OK && nodeRef.Data.Head.Level != exp.Level.Val {
+		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected level=%v but claims to be level=%v",
+			addr, exp.Level.Val, nodeRef.Data.Head.Level)
+	}
+	if exp.MaxGeneration.OK && nodeRef.Data.Head.Generation > exp.MaxGeneration.Val {
+		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected generation<=%v but claims to be generation=%v",
+			addr, exp.MaxGeneration.Val, nodeRef.Data.Head.Generation)
+	}
+	if len(exp.Owner) > 0 && !slices.Contains(nodeRef.Data.Head.Owner, exp.Owner) {
+		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected owner in %v but claims to have owner=%v",
+			addr, exp.Owner, nodeRef.Data.Head.Owner)
+	}
+
+	// parse (main)
+
+	if _, err := binstruct.Unmarshal(nodeBuf, &nodeRef.Data); err != nil {
+		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err)
+	}
+
+	// return
+
+	return nodeRef, nil
+}
diff --git a/lib/btrfs/btrfstree/types_node_test.go b/lib/btrfs/btrfstree/types_node_test.go
new file mode 100644
index 0000000..040b90c
--- /dev/null
+++ b/lib/btrfs/btrfstree/types_node_test.go
@@ -0,0 +1,35 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfstree_test
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/require"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
+)
+
+func FuzzRoundTripNode(f *testing.F) {
+	f.Fuzz(func(t *testing.T, inDat []byte) {
+		t.Logf("dat=(%d)%q", len(inDat), inDat)
+		node := btrfstree.Node{
+			ChecksumType: btrfssum.TYPE_CRC32,
+		}
+		n, err := binstruct.Unmarshal(inDat, &node)
+		if err != nil {
+			t.Logf("err=%v", err)
+			//require.Equal(t, 0, n)
+		} else {
+			require.Equal(t, len(inDat), n)
+
+			outDat, err := binstruct.Marshal(node)
+			require.NoError(t, err)
+			require.Equal(t, inDat[:], outDat)
+		}
+	})
+}
diff --git a/lib/btrfs/btrfstree/types_superblock.go b/lib/btrfs/btrfstree/types_superblock.go
new file mode 100644
index 0000000..9258f9a
--- /dev/null
+++ b/lib/btrfs/btrfstree/types_superblock.go
@@ -0,0 +1,238 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package btrfstree
+
+import (
+	"fmt"
+	"reflect"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/fmtutil"
+)
+
+type Superblock struct {
+	Checksum   btrfssum.CSum         `bin:"off=0x0,  siz=0x20"` // Checksum of everything past this field (from 0x20 to 0x1000)
+	FSUUID     btrfsprim.UUID        `bin:"off=0x20, siz=0x10"` // FS UUID
+	Self       btrfsvol.PhysicalAddr `bin:"off=0x30, siz=0x8"`  // physical address of this block (different for mirrors)
+	Flags      uint64                `bin:"off=0x38, siz=0x8"`  // flags
+	Magic      [8]byte               `bin:"off=0x40, siz=0x8"`  // magic ('_BHRfS_M')
+	Generation btrfsprim.Generation  `bin:"off=0x48, siz=0x8"`
+
+	RootTree  btrfsvol.LogicalAddr `bin:"off=0x50, siz=0x8"` // logical address of the root tree root
+	ChunkTree btrfsvol.LogicalAddr `bin:"off=0x58, siz=0x8"` // logical address of the chunk tree root
+	LogTree   btrfsvol.LogicalAddr `bin:"off=0x60, siz=0x8"` // logical address of the log tree root
+
+	LogRootTransID  uint64          `bin:"off=0x68, siz=0x8"` // log_root_transid
+	TotalBytes      uint64          `bin:"off=0x70, siz=0x8"` // total_bytes
+	BytesUsed       uint64          `bin:"off=0x78, siz=0x8"` // bytes_used
+	RootDirObjectID btrfsprim.ObjID `bin:"off=0x80, siz=0x8"` // root_dir_objectid (usually 6)
+	NumDevices      uint64          `bin:"off=0x88, siz=0x8"` // num_devices
+
+	SectorSize        uint32 `bin:"off=0x90, siz=0x4"`
+	NodeSize          uint32 `bin:"off=0x94, siz=0x4"`
+	LeafSize          uint32 `bin:"off=0x98, siz=0x4"` // unused; must be the same as NodeSize
+	StripeSize        uint32 `bin:"off=0x9c, siz=0x4"`
+	SysChunkArraySize uint32 `bin:"off=0xa0, siz=0x4"`
+
+	ChunkRootGeneration btrfsprim.Generation `bin:"off=0xa4, siz=0x8"`
+	CompatFlags         uint64               `bin:"off=0xac, siz=0x8"` // compat_flags
+	CompatROFlags       uint64               `bin:"off=0xb4, siz=0x8"` // compat_ro_flags - only implementations that support the flags can write to the filesystem
+	IncompatFlags       IncompatFlags        `bin:"off=0xbc, siz=0x8"` // incompat_flags - only implementations that support the flags can use the filesystem
+	ChecksumType        btrfssum.CSumType    `bin:"off=0xc4, siz=0x2"`
+
+	RootLevel  uint8 `bin:"off=0xc6, siz=0x1"` // root_level
+	ChunkLevel uint8 `bin:"off=0xc7, siz=0x1"` // chunk_root_level
+	LogLevel   uint8 `bin:"off=0xc8, siz=0x1"` // log_root_level
+
+	DevItem            btrfsitem.Dev        `bin:"off=0xc9,  siz=0x62"`  // DEV_ITEM data for this device
+	Label              [0x100]byte          `bin:"off=0x12b, siz=0x100"` // label (may not contain '/' or '\\')
+	CacheGeneration    btrfsprim.Generation `bin:"off=0x22b, siz=0x8"`
+	UUIDTreeGeneration btrfsprim.Generation `bin:"off=0x233, siz=0x8"`
+
+	// FeatureIncompatMetadataUUID
+	MetadataUUID btrfsprim.UUID `bin:"off=0x23b, siz=0x10"`
+
+	// FeatureIncompatExtentTreeV2
+	NumGlobalRoots uint64 `bin:"off=0x24b, siz=0x8"`
+
+	// FeatureIncompatExtentTreeV2
+	BlockGroupRoot           btrfsvol.LogicalAddr `bin:"off=0x253, siz=0x8"`
+	BlockGroupRootGeneration btrfsprim.Generation `bin:"off=0x25b, siz=0x8"`
+	BlockGroupRootLevel      uint8                `bin:"off=0x263, siz=0x1"`
+
+	Reserved [199]byte `bin:"off=0x264, siz=0xc7"` // future expansion
+
+	SysChunkArray [0x800]byte   `bin:"off=0x32b, siz=0x800"` // sys_chunk_array:(n bytes valid) Contains (KEY . CHUNK_ITEM) pairs for all SYSTEM chunks. This is needed to bootstrap the mapping from logical addresses to physical.
+	SuperRoots    [4]RootBackup `bin:"off=0xb2b, siz=0x2a0"`
+
+	// Padded to 4096 bytes
+	Padding       [565]byte `bin:"off=0xdcb, siz=0x235"`
+	binstruct.End `bin:"off=0x1000"`
+}
+
+func (sb Superblock) CalculateChecksum() (btrfssum.CSum, error) {
+	data, err := binstruct.Marshal(sb)
+	if err != nil {
+		return btrfssum.CSum{}, err
+	}
+	return sb.ChecksumType.Sum(data[binstruct.StaticSize(btrfssum.CSum{}):])
+}
+
+func (sb Superblock) ValidateChecksum() error {
+	stored := sb.Checksum
+	calced, err := sb.CalculateChecksum()
+	if err != nil {
+		return err
+	}
+	if calced != stored {
+		return fmt.Errorf("superblock checksum mismatch: stored=%v calculated=%v",
+			stored, calced)
+	}
+	return nil
+}
+
+func (a Superblock) Equal(b Superblock) bool {
+	a.Checksum = btrfssum.CSum{}
+	a.Self = 0
+
+	b.Checksum = btrfssum.CSum{}
+	b.Self = 0
+
+	return reflect.DeepEqual(a, b)
+}
+
+func (sb Superblock) EffectiveMetadataUUID() btrfsprim.UUID {
+	if !sb.IncompatFlags.Has(FeatureIncompatMetadataUUID) {
+		return sb.FSUUID
+	}
+	return sb.MetadataUUID
+}
+
+type SysChunk struct {
+	Key   btrfsprim.Key
+	Chunk btrfsitem.Chunk
+}
+
+func (sc SysChunk) MarshalBinary() ([]byte, error) {
+	dat, err := binstruct.Marshal(sc.Key)
+	if err != nil {
+		return dat, err
+	}
+	_dat, err := binstruct.Marshal(sc.Chunk)
+	dat = append(dat, _dat...)
+	if err != nil {
+		return dat, err
+	}
+	return dat, nil
+}
+
+func (sc *SysChunk) UnmarshalBinary(dat []byte) (int, error) {
+	n, err := binstruct.Unmarshal(dat, &sc.Key)
+	if err != nil {
+		return n, err
+	}
+	_n, err := binstruct.Unmarshal(dat[n:], &sc.Chunk)
+	n += _n
+	if err != nil {
+		return n, err
+	}
+	return n, nil
+}
+
+func (sb Superblock) ParseSysChunkArray() ([]SysChunk, error) {
+	dat := sb.SysChunkArray[:sb.SysChunkArraySize]
+	var ret []SysChunk
+	for len(dat) > 0 {
+		var pair SysChunk
+		n, err := binstruct.Unmarshal(dat, &pair)
+		dat = dat[n:]
+		if err != nil {
+			return nil, err
+		}
+		ret = append(ret, pair)
+	}
+	return ret, nil
+}
+
+type RootBackup struct {
+	TreeRoot    btrfsprim.ObjID      `bin:"off=0x0, siz=0x8"`
+	TreeRootGen btrfsprim.Generation `bin:"off=0x8, siz=0x8"`
+
+	ChunkRoot    btrfsprim.ObjID      `bin:"off=0x10, siz=0x8"`
+	ChunkRootGen btrfsprim.Generation `bin:"off=0x18, siz=0x8"`
+
+	ExtentRoot    btrfsprim.ObjID      `bin:"off=0x20, siz=0x8"`
+	ExtentRootGen btrfsprim.Generation `bin:"off=0x28, siz=0x8"`
+
+	FSRoot    btrfsprim.ObjID      `bin:"off=0x30, siz=0x8"`
+	FSRootGen btrfsprim.Generation `bin:"off=0x38, siz=0x8"`
+
+	DevRoot    btrfsprim.ObjID      `bin:"off=0x40, siz=0x8"`
+	DevRootGen btrfsprim.Generation `bin:"off=0x48, siz=0x8"`
+
+	ChecksumRoot    btrfsprim.ObjID      `bin:"off=0x50, siz=0x8"`
+	ChecksumRootGen btrfsprim.Generation `bin:"off=0x58, siz=0x8"`
+
+	TotalBytes uint64 `bin:"off=0x60, siz=0x8"`
+	BytesUsed  uint64 `bin:"off=0x68, siz=0x8"`
+	NumDevices uint64 `bin:"off=0x70, siz=0x8"`
+
+	Unused [8 * 4]byte `bin:"off=0x78, siz=0x20"`
+
+	TreeRootLevel     uint8 `bin:"off=0x98, siz=0x1"`
+	ChunkRootLevel    uint8 `bin:"off=0x99, siz=0x1"`
+	ExtentRootLevel   uint8 `bin:"off=0x9a, siz=0x1"`
+	FSRootLevel       uint8 `bin:"off=0x9b, siz=0x1"`
+	DevRootLevel      uint8 `bin:"off=0x9c, siz=0x1"`
+	ChecksumRootLevel uint8 `bin:"off=0x9d, siz=0x1"`
+
+	Padding       [10]byte `bin:"off=0x9e, siz=0xa"`
+	binstruct.End `bin:"off=0xa8"`
+}
+
+type IncompatFlags uint64
+
+const (
+	FeatureIncompatMixedBackref = IncompatFlags(1 << iota)
+	FeatureIncompatDefaultSubvol
+	FeatureIncompatMixedGroups
+	FeatureIncompatCompressLZO
+	FeatureIncompatCompressZSTD
+	FeatureIncompatBigMetadata // buggy
+	FeatureIncompatExtendedIRef
+	FeatureIncompatRAID56
+	FeatureIncompatSkinnyMetadata
+	FeatureIncompatNoHoles
+	FeatureIncompatMetadataUUID
+	FeatureIncompatRAID1C34
+	FeatureIncompatZoned
+	FeatureIncompatExtentTreeV2
+)
+
+var incompatFlagNames = []string{
+	"FeatureIncompatMixedBackref",
+	"FeatureIncompatDefaultSubvol",
+	"FeatureIncompatMixedGroups",
+	"FeatureIncompatCompressLZO",
+	"FeatureIncompatCompressZSTD",
+	"FeatureIncompatBigMetadata ",
+	"FeatureIncompatExtendedIRef",
+	"FeatureIncompatRAID56",
+	"FeatureIncompatSkinnyMetadata",
+	"FeatureIncompatNoHoles",
+	"FeatureIncompatMetadataUUID",
+	"FeatureIncompatRAID1C34",
+	"FeatureIncompatZoned",
+	"FeatureIncompatExtentTreeV2",
+}
+
+func (f IncompatFlags) Has(req IncompatFlags) bool { return f&req == req }
+func (f IncompatFlags) String() string {
+	return fmtutil.BitfieldString(f, incompatFlagNames, fmtutil.HexLower)
+}