wip

10 files changed, 564 insertions, 89 deletions

diff --git a/cmd/btrfs-dump-tree/ldd.txt b/cmd/btrfs-dump-tree/ldd.txt
new file mode 100644
index 0000000..2560bd9
--- /dev/null
+++ b/cmd/btrfs-dump-tree/ldd.txt
@@ -0,0 +1,198 @@
+/usr/bin/avahi-discover-standalone:
+	libgtk-3.so.0 => not found
+--
+/usr/lib/libavahi-libevent.so:
+	libevent-2.1.so.7 => not found
+/usr/lib/libavahi-libevent.so.1:
+	libevent-2.1.so.7 => not found
+/usr/lib/libavahi-libevent.so.1.0.0:
+	libevent-2.1.so.7 => not found
+/usr/lib/libavahi-qt5.so:
+	libQt5Core.so.5 => not found
+/usr/lib/libavahi-qt5.so.1:
+	libQt5Core.so.5 => not found
+/usr/lib/libavahi-qt5.so.1.0.2:
+	libQt5Core.so.5 => not found
+/usr/lib/libavahi-ui-gtk3.so:
+	libgtk-3.so.0 => not found
+	libgdk-3.so.0 => not found
+/usr/lib/libavahi-ui-gtk3.so.0:
+	libgtk-3.so.0 => not found
+	libgdk-3.so.0 => not found
+/usr/lib/libavahi-ui-gtk3.so.0.1.4:
+	libgtk-3.so.0 => not found
+	libgdk-3.so.0 => not found
+--
+/usr/bin/btrfs-convert:
+	libreiserfscore.so.0 => not found
+--
+/usr/lib/collectd/amqp.so:
+	librabbitmq.so.4 => not found
+	libyajl.so.2 => not found
+--
+/usr/lib/collectd/ceph.so:
+	libyajl.so.2 => not found
+--
+/usr/lib/collectd/connectivity.so:
+	libyajl.so.2 => not found
+--
+/usr/lib/collectd/curl_json.so:
+	libyajl.so.2 => not found
+--
+/usr/lib/collectd/dbi.so:
+	libdbi.so.1 => not found
+--
+/usr/lib/collectd/ipmi.so:
+	libOpenIPMIpthread.so.0 => not found
+	libOpenIPMIutils.so.0 => not found
+	libOpenIPMI.so.0 => not found
+--
+/usr/lib/collectd/log_logstash.so:
+	libyajl.so.2 => not found
+--
+/usr/lib/collectd/memcachec.so:
+	libmemcached.so.11 => not found
+--
+/usr/lib/collectd/mqtt.so:
+	libmosquitto.so.1 => not found
+--
+/usr/lib/collectd/mysql.so:
+	libmariadb.so.3 => not found
+--
+/usr/lib/collectd/notify_desktop.so:
+	libnotify.so.4 => not found
+	libgdk_pixbuf-2.0.so.0 => not found
+/usr/lib/collectd/notify_email.so:
+	libesmtp.so.6 => not found
+--
+/usr/lib/collectd/nut.so:
+	libupsclient.so.4 => not found
+--
+/usr/lib/collectd/ovs_events.so:
+	libyajl.so.2 => not found
+/usr/lib/collectd/ovs_stats.so:
+	libyajl.so.2 => not found
+--
+/usr/lib/collectd/pinba.so:
+	libprotobuf-c.so.1 => not found
+/usr/lib/collectd/ping.so:
+	liboping.so.0 => not found
+/usr/lib/collectd/postgresql.so:
+	libpq.so.5 => not found
+--
+/usr/lib/collectd/procevent.so:
+	libyajl.so.2 => not found
+--
+/usr/lib/collectd/snmp.so:
+	libnetsnmp.so.40 => not found
+/usr/lib/collectd/snmp_agent.so:
+	libnetsnmpagent.so.40 => not found
+--
+/usr/lib/collectd/sysevent.so:
+	libyajl.so.2 => not found
+--
+/usr/lib/collectd/virt.so:
+	libvirt.so.0 => not found
+--
+/usr/lib/collectd/write_http.so:
+	libyajl.so.2 => not found
+--
+/usr/lib/collectd/write_log.so:
+	libyajl.so.2 => not found
+/usr/lib/collectd/write_prometheus.so:
+	libprotobuf-c.so.1 => not found
+--
+/usr/lib/collectd/write_stackdriver.so:
+	libyajl.so.2 => not found
+--
+/usr/lib/git-core/git-credential-gnome-keyring:
+	libgnome-keyring.so.0 => not found
+--
+/usr/bin/memusagestat:
+	libgd.so.3 => not found
+--
+/usr/lib/guile/2.2/extensions/guile-gnutls-v-2.so:
+	libcrypt.so.1 => not found
+/usr/lib/guile/2.2/extensions/guile-gnutls-v-2.so.0:
+	libcrypt.so.1 => not found
+/usr/lib/guile/2.2/extensions/guile-gnutls-v-2.so.0.0.0:
+	libcrypt.so.1 => not found
+--
+/usr/bin/gxditview:
+	libXaw.so.7 => not found
+	libXmu.so.6 => not found
+	libXt.so.6 => not found
+--
+/usr/bin/xtotroff:
+	libXt.so.6 => not found
+--
+/usr/bin/grub-mount:
+	libfuse.so.2 => not found
+--
+/usr/bin/guile:
+	libcrypt.so.1 => not found
+--
+/usr/lib/guile/2.2/extensions/guile-readline.so:
+	libcrypt.so.1 => not found
+/usr/lib/guile/2.2/extensions/guile-readline.so.0:
+	libcrypt.so.1 => not found
+/usr/lib/guile/2.2/extensions/guile-readline.so.0.0.0:
+	libcrypt.so.1 => not found
+/usr/lib/libguile-2.2.so:
+	libcrypt.so.1 => not found
+/usr/lib/libguile-2.2.so.1:
+	libcrypt.so.1 => not found
+/usr/lib/libguile-2.2.so.1.4.1:
+	libcrypt.so.1 => not found
+--
+/usr/bin/ftpd:
+	libcrypt.so.1 => not found
+--
+/usr/lib/tc/q_atm.so:
+	libatm.so.1 => not found
+--
+/usr/bin/make:
+	libcrypt.so.1 => not found
+--
+/usr/lib/ssh/ssh-sk-helper:
+	libfido2.so.1 => not found
+--
+/usr/bin/pinentry-gnome3:
+	libgcr-base-3.so.1 => not found
+/usr/bin/pinentry-gtk-2:
+	libgtk-x11-2.0.so.0 => not found
+	libgdk-x11-2.0.so.0 => not found
+/usr/bin/pinentry-qt:
+	libQt5Widgets.so.5 => not found
+	libQt5Gui.so.5 => not found
+	libQt5Core.so.5 => not found
+--
+/usr/lib/python3.9/lib-dynload/_decimal.cpython-39-x86_64-linux-gnu.so:
+	libmpdec.so.2 => not found
+--
+/usr/lib/python3.9/lib-dynload/_tkinter.cpython-39-x86_64-linux-gnu.so:
+	libtk8.6.so => not found
+	libtcl8.6.so => not found
+--
+/usr/lib/python2.7/lib-dynload/_ctypes.so:
+	libffi.so.8 => not found
+--
+/usr/lib/python2.7/lib-dynload/_tkinter.so:
+	libtk8.6.so => not found
+	libtcl8.6.so => not found
+--
+/usr/lib/python2.7/lib-dynload/nis.so:
+	libnsl.so.3 => not found
+--
+/usr/bin/qemu-keymap:
+	libxkbcommon.so.0 => not found
+--
+/usr/lib/lua/5.1/rrd.so:
+	liblua5.1.so.5.1 => not found
+/usr/lib/lua/5.1/rrd.so.0:
+	liblua5.1.so.5.1 => not found
+/usr/lib/lua/5.1/rrd.so.0.0.0:
+	liblua5.1.so.5.1 => not found
+--
+/usr/lib/ruby/vendor_ruby/2.7.0/x86_64-linux/RRD.so:
+	libruby.so.2.7 => not found
diff --git a/cmd/btrfs-dump-tree/main.go b/cmd/btrfs-dump-tree/main.go
index 1b3b993..bdfd339 100644
--- a/cmd/btrfs-dump-tree/main.go
+++ b/cmd/btrfs-dump-tree/main.go
@@ -4,8 +4,6 @@ import (
 	"fmt"
 	"os"
 
-	"github.com/davecgh/go-spew/spew"
-
 	"lukeshu.com/btrfs-tools/pkg/btrfs"
 )
 
@@ -16,6 +14,8 @@ func main() {
 	}
 }
 
+const version = "5.17"
+
 func Main(imgfilename string) (err error) {
 	maybeSetErr := func(_err error) {
 		if _err != nil && err == nil {
@@ -38,30 +38,68 @@ func Main(imgfilename string) (err error) {
 		},
 	}
 
-	superblocks, err := fs.Devices[0].Superblocks()
+	superblock, err := fs.Superblock()
 	if err != nil {
 		return err
 	}
 
-	spew := spew.NewDefaultConfig()
-	spew.DisablePointerAddresses = true
-
-	sum, err := superblocks[0].Data.CalculateChecksum()
-	if err != nil {
-		return err
+	fmt.Printf("btrfs-progs v%s \n", version)
+	if superblock.Data.RootTree != 0 && false { // XXX
+		fmt.Printf("root tree\n")
+		printTree(fs, superblock.Data.RootTree)
+	}
+	if superblock.Data.ChunkTree != 0 {
+		fmt.Printf("chunk tree\n")
+		printTree(fs, superblock.Data.ChunkTree)
+	}
+	if superblock.Data.LogTree != 0 {
+		fmt.Printf("log root tree\n")
+		printTree(fs, superblock.Data.LogTree)
+	}
+	if superblock.Data.BlockGroupRoot != 0 {
+		fmt.Printf("block group tree\n")
+		printTree(fs, superblock.Data.BlockGroupRoot)
 	}
-	fmt.Printf("superblock checksum: %x\n", sum)
-	spew.Dump(superblocks[0].Data)
 
-	syschunks, err := superblocks[0].Data.ParseSysChunkArray()
+	return nil
+}
+
+// printTree mimics btrfs-progs kernel-shared/print-tree.c:btrfs_print_tree()
+func printTree(fs *btrfs.FS, root btrfs.LogicalAddr) {
+	node, err := fs.ReadNode(root)
 	if err != nil {
-		return err
+		fmt.Printf("error: %v\n", err)
+		return
 	}
-	spew.Dump(syschunks)
+	printHeaderInfo(node)
+	// TODO
+}
 
-	if err := btrfs.ScanForNodes(fs.Devices[0], superblocks[0].Data); err != nil {
-		return err
+// printHeaderInfo mimics btrfs-progs kernel-shared/print-tree.c:print_header_info()
+func printHeaderInfo(node btrfs.Node) {
+	var typename string
+	switch node := node.(type) {
+	case *btrfs.InternalNode:
+		typename = "node"
+		fmt.Printf("node %d level %d items %d free space %d",
+			node.Header.Addr,
+			node.Header.Data.Level,
+			node.Header.Data.NumItems,
+			node.Header.Data.MaxItems-node.Header.Data.NumItems)
+	case *btrfs.LeafNode:
+		typename = "leaf"
+		fmt.Printf("leaf %d items %d free space %d",
+			node.Header.Addr,
+			node.Header.Data.NumItems,
+			node.FreeSpace())
 	}
+	fmt.Printf(" generation %d owner %v\n",
+		node.GetNodeHeader().Data.Generation,
+		node.GetNodeHeader().Data.Owner)
 
-	return nil
+	fmt.Printf("%s %d flags %s backref revision %d\n",
+		typename,
+		node.GetNodeHeader().Addr,
+		node.GetNodeHeader().Data.Flags,
+		node.GetNodeHeader().Data.BackrefRev)
 }
diff --git a/pkg/binstruct/l1.go b/pkg/binstruct/l1.go
index d90ecba..367dd28 100644
--- a/pkg/binstruct/l1.go
+++ b/pkg/binstruct/l1.go
@@ -7,9 +7,13 @@ import (
 )
 
 type Marshaler interface {
+	BinarySize() int64
 	MarshalBinary() []byte
+}
+
+type Unmarshaler interface {
+	Marshaler
 	UnmarshalBinary([]byte)
-	BinarySize() int64
 }
 
 type handler interface {
@@ -26,9 +30,9 @@ func (_ extHandler) Marshal(val interface{}) []byte {
 	return val.(Marshaler).MarshalBinary()
 }
 func (e extHandler) Unmarshal(dat []byte) interface{} {
-	val := reflect.New(e.typ).Elem().Interface().(Marshaler)
-	val.UnmarshalBinary(dat)
-	return val
+	valPtr := reflect.New(e.typ).Interface().(Unmarshaler)
+	valPtr.UnmarshalBinary(dat)
+	return reflect.ValueOf(valPtr).Elem().Interface()
 }
 func (e extHandler) Size() int64 {
 	val := reflect.New(e.typ).Elem().Interface().(Marshaler)
@@ -53,7 +57,9 @@ func convert[T any](in interface{}) T {
 }
 
 func genHandler(typ reflect.Type) (handler, error) {
-	if _, ok := reflect.New(typ).Elem().Interface().(Marshaler); ok {
+	_, marOK := reflect.New(typ).Elem().Interface().(Marshaler)
+	_, unmarOK := reflect.New(typ).Interface().(Unmarshaler)
+	if marOK && unmarOK {
 		return extHandler{
 			typ: typ,
 		}, nil
@@ -112,7 +118,7 @@ func genHandler(typ reflect.Type) (handler, error) {
 	case reflect.Int8:
 		return primitive{
 			unmarshal: func(dat []byte) interface{} { return int8(dat[0]) },
-			marshal:   func(val interface{}) []byte { return []byte{uint8(convert[int8](val))}},
+			marshal:   func(val interface{}) []byte { return []byte{uint8(convert[int8](val))} },
 			size:      1,
 		}, nil
 	case reflect.Int16:
diff --git a/pkg/btrfs/fsck.go b/pkg/btrfs/fsck.go
index d31735e..b6c80e5 100644
--- a/pkg/btrfs/fsck.go
+++ b/pkg/btrfs/fsck.go
@@ -21,7 +21,7 @@ func ScanForNodes(dev *Device, sb Superblock) error {
 	}
 
 	nodeBuf := make([]byte, sb.NodeSize)
-	for pos := int64(0); pos+int64(sb.SectorSize) < devSize; pos += int64(sb.SectorSize) {
+	for pos := PhysicalAddr(0); pos+PhysicalAddr(sb.SectorSize) < devSize; pos += PhysicalAddr(sb.SectorSize) {
 		if inSlice(pos, superblockAddrs) {
 			fmt.Printf("sector@%d is a superblock\n", pos)
 			continue
@@ -45,7 +45,7 @@ func ScanForNodes(dev *Device, sb Superblock) error {
 		fmt.Printf("node@%d: physical_addr=0x%0X logical_addr=0x%0X generation=%d owner=%v level=%d\n",
 			pos, pos, nodeHeader.Addr, nodeHeader.Generation, nodeHeader.Owner, nodeHeader.Level)
 
-		pos += int64(sb.NodeSize) - int64(sb.SectorSize)
+		pos += PhysicalAddr(sb.NodeSize) - PhysicalAddr(sb.SectorSize)
 	}
 
 	return nil
diff --git a/pkg/btrfs/io_device.go b/pkg/btrfs/io_device.go
index 26450b7..042c9f2 100644
--- a/pkg/btrfs/io_device.go
+++ b/pkg/btrfs/io_device.go
@@ -9,21 +9,25 @@ type Device struct {
 	*os.File
 }
 
-func (dev Device) Size() (int64, error) {
+func (dev Device) Size() (PhysicalAddr, error) {
 	fi, err := dev.Stat()
 	if err != nil {
 		return 0, err
 	}
-	return fi.Size(), nil
+	return PhysicalAddr(fi.Size()), nil
 }
 
-var superblockAddrs = []int64{
+var superblockAddrs = []PhysicalAddr{
 	0x00_0001_0000, // 64KiB
 	0x00_0400_0000, // 64MiB
 	0x40_0000_0000, // 256GiB
 }
 
-func (dev *Device) Superblocks() ([]Ref[Superblock], error) {
+func (dev *Device) ReadAt(dat []byte, paddr PhysicalAddr) (int, error) {
+	return dev.File.ReadAt(dat, int64(paddr))
+}
+
+func (dev *Device) Superblocks() ([]Ref[PhysicalAddr, Superblock], error) {
 	const superblockSize = 0x1000
 
 	sz, err := dev.Size()
@@ -31,12 +35,12 @@ func (dev *Device) Superblocks() ([]Ref[Superblock], error) {
 		return nil, err
 	}
 
-	var ret []Ref[Superblock]
+	var ret []Ref[PhysicalAddr, Superblock]
 	for i, addr := range superblockAddrs {
 		if addr+superblockSize <= sz {
-			superblock := Ref[Superblock]{
-				dev:  dev,
-				addr: addr,
+			superblock := Ref[PhysicalAddr, Superblock]{
+				File: dev,
+				Addr: addr,
 			}
 			if err := superblock.Read(); err != nil {
 				return nil, fmt.Errorf("superblock %d: %w", i, err)
@@ -50,7 +54,7 @@ func (dev *Device) Superblocks() ([]Ref[Superblock], error) {
 	return ret, nil
 }
 
-func (dev *Device) superblock() (ret Ref[Superblock], err error) {
+func (dev *Device) Superblock() (ret Ref[PhysicalAddr, Superblock], err error) {
 	sbs, err := dev.Superblocks()
 	if err != nil {
 		return ret, err
diff --git a/pkg/btrfs/io_fs.go b/pkg/btrfs/io_fs.go
index 52f742a..5dee6dc 100644
--- a/pkg/btrfs/io_fs.go
+++ b/pkg/btrfs/io_fs.go
@@ -4,6 +4,8 @@ import (
 	"bytes"
 	"fmt"
 	"reflect"
+
+	"lukeshu.com/btrfs-tools/pkg/binstruct"
 )
 
 type FS struct {
@@ -14,6 +16,71 @@ type FS struct {
 	chunks   []SysChunk
 }
 
+func (fs *FS) Name() string {
+	sb, err := fs.Superblock()
+	if err != nil {
+		return fmt.Sprintf("fs_uuid=%s", "(unreadable)")
+	}
+	return fmt.Sprintf("fs_uuid=%s", sb.Data.FSUUID)
+}
+
+func (fs *FS) Size() (LogicalAddr, error) {
+	var ret LogicalAddr
+	for _, dev := range fs.Devices {
+		sz, err := dev.Size()
+		if err != nil {
+			return 0, fmt.Errorf("file %q: %w", dev.Name(), err)
+		}
+		ret += LogicalAddr(sz)
+	}
+	return ret, nil
+}
+
+func (fs *FS) Superblocks() ([]Ref[PhysicalAddr, Superblock], error) {
+	var ret []Ref[PhysicalAddr, Superblock]
+	for _, dev := range fs.Devices {
+		sbs, err := dev.Superblocks()
+		if err != nil {
+			return nil, fmt.Errorf("file %q: %w", dev.Name(), err)
+		}
+		ret = append(ret, sbs...)
+	}
+	return ret, nil
+}
+
+func (fs *FS) Superblock() (ret Ref[PhysicalAddr, Superblock], err error) {
+	sbs, err := fs.Superblocks()
+	if err != nil {
+		return ret, err
+	}
+
+	fname := ""
+	sbi := 0
+	for i, sb := range sbs {
+		if sb.File.Name() != fname {
+			fname = sb.File.Name()
+			sbi = 0
+		} else {
+			sbi++
+		}
+
+		if err := sb.Data.ValidateChecksum(); err != nil {
+			return ret, fmt.Errorf("file %q superblock %d: %w", sb.File.Name(), sbi, err)
+		}
+		if i > 0 {
+			// This is probably wrong, but lots of my
+			// multi-device code is probably wrong.
+			if !sb.Data.Equal(sbs[0].Data) {
+				return ret, fmt.Errorf("file %q superblock %d and file %q superblock %d disagree",
+					sbs[0].File.Name(), 0,
+					sb.File.Name(), sbi)
+			}
+		}
+	}
+
+	return sbs[0], nil
+}
+
 func (fs *FS) init() error {
 	if fs.uuid2dev != nil {
 		return fs.initErr
@@ -58,19 +125,19 @@ func (fs *FS) init() error {
 	return nil
 }
 
-func (fs *FS) ReadLogicalFull(laddr LogicalAddr, dat []byte) error {
-	done := LogicalAddr(0)
-	for done < LogicalAddr(len(dat)) {
-		n, err := fs.readLogicalMaybeShort(laddr+done, dat[done:])
+func (fs *FS) ReadAt(dat []byte, laddr LogicalAddr) (int, error) {
+	done := 0
+	for done < len(dat) {
+		n, err := fs.maybeShortReadAt(dat[done:], laddr+LogicalAddr(done))
+		done += n
 		if err != nil {
-			return err
+			return done, err
 		}
-		done += LogicalAddr(n)
 	}
-	return nil
+	return done, nil
 }
 
-func (fs *FS) readLogicalMaybeShort(laddr LogicalAddr, dat []byte) (int, error) {
+func (fs *FS) maybeShortReadAt(dat []byte, laddr LogicalAddr) (int, error) {
 	if err := fs.init(); err != nil {
 		return 0, err
 	}
@@ -108,7 +175,7 @@ func (fs *FS) readLogicalMaybeShort(laddr LogicalAddr, dat []byte) (int, error)
 		if !ok {
 			return 0, fmt.Errorf("device=%s does not exist", paddr.Dev)
 		}
-		if _, err := dev.ReadAt(buf, int64(paddr.Addr)); err != nil {
+		if _, err := dev.ReadAt(buf, paddr.Addr); err != nil {
 			return 0, fmt.Errorf("read device=%s paddr=%v: %w", paddr.Dev, paddr.Addr, err)
 		}
 		if first {
@@ -121,3 +188,90 @@ func (fs *FS) readLogicalMaybeShort(laddr LogicalAddr, dat []byte) (int, error)
 	}
 	return len(dat), nil
 }
+
+func (fs *FS) ReadNode(addr LogicalAddr) (Node, error) {
+	sb, err := fs.Superblock()
+	if err != nil {
+		return nil, err
+	}
+
+	nodeBuf := make([]byte, sb.Data.NodeSize)
+	if _, err := fs.ReadAt(nodeBuf, addr); err != nil {
+		return nil, err
+	}
+
+	var nodeHeader NodeHeader
+	if err := binstruct.Unmarshal(nodeBuf, &nodeHeader); err != nil {
+		return nil, fmt.Errorf("node@%d: %w", addr, err)
+	}
+
+	if !nodeHeader.MetadataUUID.Equal(sb.Data.EffectiveMetadataUUID()) {
+		return nil, fmt.Errorf("node@%d: does not look like a node", addr)
+	}
+
+	stored := nodeHeader.Checksum
+	calced := CRC32c(nodeBuf[0x20:])
+	if !calced.Equal(stored) {
+		return nil, fmt.Errorf("node@%d: checksum mismatch: stored=%s calculated=%s",
+			addr, stored, calced)
+	}
+
+	nodeHeader.Size = sb.Data.NodeSize
+
+	if nodeHeader.Level > 0 {
+		// internal node
+		nodeHeader.MaxItems = (sb.Data.NodeSize - 0x65) / 0x21
+		ret := &InternalNode{
+			Header: Ref[LogicalAddr, NodeHeader]{
+				File: fs,
+				Addr: addr,
+				Data: nodeHeader,
+			},
+			Body: nil,
+		}
+		for i := uint32(0); i < nodeHeader.NumItems; i++ {
+			itemOff := 0x65 + (0x21 * int(i))
+			var item KeyPointer
+			if err := binstruct.Unmarshal(nodeBuf[itemOff:], &item); err != nil {
+				return nil, fmt.Errorf("node@%d (internal): item %d: %w", addr, i, err)
+			}
+			ret.Body = append(ret.Body, Ref[LogicalAddr, KeyPointer]{
+				File: fs,
+				Addr: addr + LogicalAddr(itemOff),
+				Data: item,
+			})
+		}
+		return ret, nil
+	} else {
+		// leaf node
+		nodeHeader.MaxItems = (sb.Data.NodeSize - 0x65) / 0x19
+		ret := &LeafNode{
+			Header: Ref[LogicalAddr, NodeHeader]{
+				File: fs,
+				Addr: addr,
+				Data: nodeHeader,
+			},
+			Body: nil,
+		}
+		for i := uint32(0); i < nodeHeader.NumItems; i++ {
+			itemOff := 0x65 + (0x19 * int(i))
+			var item Item
+			if err := binstruct.Unmarshal(nodeBuf[itemOff:], &item); err != nil {
+				return nil, fmt.Errorf("node@%d (leaf): item %d: %w", addr, i, err)
+			}
+			dataOff := 0x65 + int(item.DataOffset)
+			dataSize := int(item.DataSize)
+			item.Data = Ref[LogicalAddr, []byte]{
+				File: fs,
+				Addr: addr + LogicalAddr(dataOff),
+				Data: nodeBuf[dataOff : dataOff+dataSize],
+			}
+			ret.Body = append(ret.Body, Ref[LogicalAddr, Item]{
+				File: fs,
+				Addr: addr + LogicalAddr(itemOff),
+				Data: item,
+			})
+		}
+		return ret, nil
+	}
+}
diff --git a/pkg/btrfs/io_ref.go b/pkg/btrfs/io_ref.go
index aa37fee..a91b691 100644
--- a/pkg/btrfs/io_ref.go
+++ b/pkg/btrfs/io_ref.go
@@ -4,19 +4,25 @@ import (
 	"lukeshu.com/btrfs-tools/pkg/binstruct"
 )
 
-type Ref[T any] struct {
-	dev  *Device
-	addr int64
+type File[A ~int64] interface {
+	Name() string
+	Size() (A, error)
+	ReadAt(p []byte, off A) (n int, err error)
+}
+
+type Ref[A ~int64, T any] struct {
+	File File[A]
+	Addr A
 	Data T
 }
 
-func (r *Ref[T]) Read() error {
+func (r *Ref[A, T]) Read() error {
 	size, err := binstruct.Size(r.Data)
 	if err != nil {
 		return err
 	}
 	buf := make([]byte, size)
-	if _, err := r.dev.ReadAt(buf, r.addr); err != nil {
+	if _, err := r.File.ReadAt(buf, r.Addr); err != nil {
 		return err
 	}
 	return binstruct.Unmarshal(buf, &r.Data)
diff --git a/pkg/btrfs/types_bitfields.go b/pkg/btrfs/types_bitfields.go
index ead4b0f..5c09b0a 100644
--- a/pkg/btrfs/types_bitfields.go
+++ b/pkg/btrfs/types_bitfields.go
@@ -1,8 +1,11 @@
 package btrfs
 
 import (
+	"encoding/binary"
 	"fmt"
 	"strings"
+
+	"lukeshu.com/btrfs-tools/pkg/binstruct"
 )
 
 func bitfieldString[T ~uint8 | ~uint16 | ~uint32 | ~uint64](bitfield T, bitnames []string) string {
@@ -10,20 +13,25 @@ func bitfieldString[T ~uint8 | ~uint16 | ~uint32 | ~uint64](bitfield T, bitnames
 		return "0"
 	}
 	var out strings.Builder
-	fmt.Fprintf(&out, "(0x%0X)", uint64(bitfield))
-	rest := bitfield
-	sep := ' '
-	for i := 0; rest != 0; i++ {
-		if rest&(1<<i) != 0 {
-			out.WriteRune(sep)
-			if i < len(bitnames) {
-				out.WriteString(bitnames[i])
-			} else {
-				fmt.Fprintf(&out, "(1<<%d)", i)
+	fmt.Fprintf(&out, "0x%0X", uint64(bitfield))
+	if bitfield == 0 {
+		out.WriteString("(none)")
+	} else {
+		rest := bitfield
+		sep := '('
+		for i := 0; rest != 0; i++ {
+			if rest&(1<<i) != 0 {
+				out.WriteRune(sep)
+				if i < len(bitnames) {
+					out.WriteString(bitnames[i])
+				} else {
+					fmt.Fprintf(&out, "(1<<%d)", i)
+				}
+				sep = '|'
 			}
-			sep = '|'
+			rest &^= 1 << i
 		}
-		rest &^= 1 << i
+		out.WriteRune(')')
 	}
 	return out.String()
 }
@@ -66,3 +74,37 @@ var incompatFlagNames = []string{
 
 func (f IncompatFlags) Has(req IncompatFlags) bool { return f&req == req }
 func (f IncompatFlags) String() string             { return bitfieldString(f, incompatFlagNames) }
+
+type NodeFlags uint64
+
+func (NodeFlags) BinarySize() int64 {
+	return 7
+}
+func (f NodeFlags) MarshalBinary() []byte {
+	var bs [8]byte
+	binary.LittleEndian.PutUint64(bs[:], uint64(f))
+	return bs[:7]
+}
+func (f *NodeFlags) UnmarshalBinary(dat []byte) {
+	var bs [8]byte
+	copy(bs[:7], dat[:7])
+	*f = NodeFlags(binary.LittleEndian.Uint64(bs[:]))
+}
+
+var (
+	_ 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 bitfieldString(f, nodeFlagNames) }
diff --git a/pkg/btrfs/types_objid.go b/pkg/btrfs/types_objid.go
index 9d707db..6213167 100644
--- a/pkg/btrfs/types_objid.go
+++ b/pkg/btrfs/types_objid.go
@@ -54,16 +54,16 @@ const (
 func (id ObjID) String() string {
 	if id > BTRFS_LAST_FREE_OBJECTID {
 		names := map[ObjID]string{
-			BTRFS_BALANCE_OBJECTID:         "BTRFS_BALANCE_OBJECTID",
-			BTRFS_ORPHAN_OBJECTID:          "BTRFS_ORPHAN_OBJECTID",
-			BTRFS_TREE_LOG_OBJECTID:        "BTRFS_TREE_LOG_OBJECTID",
-			BTRFS_TREE_LOG_FIXUP_OBJECTID:  "BTRFS_TREE_LOG_FIXUP_OBJECTID",
-			BTRFS_TREE_RELOC_OBJECTID:      "BTRFS_TREE_RELOC_OBJECTID",
-			BTRFS_DATA_RELOC_TREE_OBJECTID: "BTRFS_DATA_RELOC_TREE_OBJECTID",
-			BTRFS_EXTENT_CSUM_OBJECTID:     "BTRFS_EXTENT_CSUM_OBJECTID",
-			BTRFS_FREE_SPACE_OBJECTID:      "BTRFS_FREE_SPACE_OBJECTID",
-			BTRFS_FREE_INO_OBJECTID:        "BTRFS_FREE_INO_OBJECTID",
-			BTRFS_MULTIPLE_OBJECTIDS:       "BTRFS_MULTIPLE_OBJECTIDS",
+			BTRFS_BALANCE_OBJECTID:         "BALANCE",
+			BTRFS_ORPHAN_OBJECTID:          "ORPHAN",
+			BTRFS_TREE_LOG_OBJECTID:        "TREE_LOG",
+			BTRFS_TREE_LOG_FIXUP_OBJECTID:  "TREE_LOG_FIXUP",
+			BTRFS_TREE_RELOC_OBJECTID:      "TREE_RELOC",
+			BTRFS_DATA_RELOC_TREE_OBJECTID: "DATA_RELOC_TREE",
+			BTRFS_EXTENT_CSUM_OBJECTID:     "EXTENT_CSUM",
+			BTRFS_FREE_SPACE_OBJECTID:      "FREE_SPACE",
+			BTRFS_FREE_INO_OBJECTID:        "FREE_INO",
+			BTRFS_MULTIPLE_OBJECTIDS:       "MULTIPLE",
 		}
 		if name, ok := names[id]; ok {
 			return name
@@ -77,17 +77,17 @@ type TreeObjID ObjID
 
 func (id TreeObjID) String() string {
 	names := map[ObjID]string{
-		BTRFS_ROOT_TREE_OBJECTID:        "BTRFS_ROOT_TREE_OBJECTID",
-		BTRFS_EXTENT_TREE_OBJECTID:      "BTRFS_EXTENT_TREE_OBJECTID",
-		BTRFS_CHUNK_TREE_OBJECTID:       "BTRFS_CHUNK_TREE_OBJECTID",
-		BTRFS_DEV_TREE_OBJECTID:         "BTRFS_DEV_TREE_OBJECTID",
-		BTRFS_FS_TREE_OBJECTID:          "BTRFS_FS_TREE_OBJECTID",
-		BTRFS_ROOT_TREE_DIR_OBJECTID:    "BTRFS_ROOT_TREE_DIR_OBJECTID",
-		BTRFS_CSUM_TREE_OBJECTID:        "BTRFS_CSUM_TREE_OBJECTID",
-		BTRFS_QUOTA_TREE_OBJECTID:       "BTRFS_QUOTA_TREE_OBJECTID",
-		BTRFS_UUID_TREE_OBJECTID:        "BTRFS_UUID_TREE_OBJECTID",
-		BTRFS_FREE_SPACE_TREE_OBJECTID:  "BTRFS_FREE_SPACE_TREE_OBJECTID",
-		BTRFS_BLOCK_GROUP_TREE_OBJECTID: "BTRFS_BLOCK_GROUP_TREE_OBJECTID",
+		BTRFS_ROOT_TREE_OBJECTID:        "ROOT_TREE",
+		BTRFS_EXTENT_TREE_OBJECTID:      "EXTENT_TREE",
+		BTRFS_CHUNK_TREE_OBJECTID:       "CHUNK_TREE",
+		BTRFS_DEV_TREE_OBJECTID:         "DEV_TREE",
+		BTRFS_FS_TREE_OBJECTID:          "FS_TREE",
+		BTRFS_ROOT_TREE_DIR_OBJECTID:    "ROOT_TREE_DIR",
+		BTRFS_CSUM_TREE_OBJECTID:        "CSUM_TREE",
+		BTRFS_QUOTA_TREE_OBJECTID:       "QUOTA_TREE",
+		BTRFS_UUID_TREE_OBJECTID:        "UUID_TREE",
+		BTRFS_FREE_SPACE_TREE_OBJECTID:  "FREE_SPACE_TREE",
+		BTRFS_BLOCK_GROUP_TREE_OBJECTID: "BLOCK_GROUP_TREE",
 	}
 	if name, ok := names[ObjID(id)]; ok {
 		return name
diff --git a/pkg/btrfs/types_structs.go b/pkg/btrfs/types_structs.go
index 6ab3b93..5063d86 100644
--- a/pkg/btrfs/types_structs.go
+++ b/pkg/btrfs/types_structs.go
@@ -77,9 +77,9 @@ type Superblock struct {
 	NumGlobalRoots uint64 `bin:"off=24b, siz=8"`
 
 	// FeatureIncompatExtentTreeV2
-	BlockGroupRoot           ObjID      `bin:"off=253, siz=8"`
-	BlockGroupRootGeneration Generation `bin:"off=25b, siz=8"`
-	BlockGroupRootLevel      uint8      `bin:"off=263, siz=1"`
+	BlockGroupRoot           LogicalAddr `bin:"off=253, siz=8"`
+	BlockGroupRootGeneration Generation  `bin:"off=25b, siz=8"`
+	BlockGroupRootLevel      uint8       `bin:"off=263, siz=1"`
 
 	Reserved [199]byte `bin:"off=264, siz=c7"` // future expansion
 
@@ -195,22 +195,34 @@ type RootBackup struct {
 	binstruct.End `bin:"off=a8"`
 }
 
+type Node interface {
+	GetNodeHeader() Ref[LogicalAddr, NodeHeader]
+}
+
 type NodeHeader struct {
 	Checksum      CSum        `bin:"off=0,  siz=20"` // Checksum of everything after this field (from 20 to the end of the node)
 	MetadataUUID  UUID        `bin:"off=20, siz=10"` // FS UUID
 	Addr          LogicalAddr `bin:"off=30, siz=8"`  // Logical address of this node
-	Flags         uint64      `bin:"off=38, siz=8"`  // Flags
+	Flags         NodeFlags   `bin:"off=38, siz=7"`
+	BackrefRev    uint8       `bin:"off=3f, siz=1"`
 	ChunkTreeUUID UUID        `bin:"off=40, siz=10"` // Chunk tree UUID
 	Generation    Generation  `bin:"off=50, siz=8"`  // Generation
 	Owner         TreeObjID   `bin:"off=58, siz=8"`  // The ID of the tree that contains this node
 	NumItems      uint32      `bin:"off=60, siz=4"`  // Number of items
 	Level         uint8       `bin:"off=64, siz=1"`  // Level (0 for leaf nodes)
 	binstruct.End `bin:"off=65"`
+
+	Size     uint32 `bin:"-"` // superblock.NodeSize
+	MaxItems uint32 `bin:"-"` // Maximum possible value of NumItems
 }
 
 type InternalNode struct {
-	NodeHeader
-	Body []KeyPointer
+	Header Ref[LogicalAddr, NodeHeader]
+	Body   []Ref[LogicalAddr, KeyPointer]
+}
+
+func (in *InternalNode) GetNodeHeader() Ref[LogicalAddr, NodeHeader] {
+	return in.Header
 }
 
 type KeyPointer struct {
@@ -221,8 +233,22 @@ type KeyPointer struct {
 }
 
 type LeafNode struct {
-	NodeHeader
-	Body []Item
+	Header Ref[LogicalAddr, NodeHeader]
+	Body   []Ref[LogicalAddr, Item]
+}
+
+func (ln *LeafNode) GetNodeHeader() Ref[LogicalAddr, NodeHeader] {
+	return ln.Header
+}
+
+func (ln *LeafNode) FreeSpace() uint32 {
+	freeSpace := ln.Header.Data.Size
+	freeSpace -= 0x65
+	for _, item := range ln.Body {
+		freeSpace -= 0x19
+		freeSpace -= item.Data.DataSize
+	}
+	return freeSpace
 }
 
 type Item struct {
@@ -230,6 +256,7 @@ type Item struct {
 	DataOffset    uint32 `bin:"off=11, siz=4"` // relative to the end of the header (0x65)
 	DataSize      uint32 `bin:"off=15, siz=4"`
 	binstruct.End `bin:"off=19"`
+	Data          Ref[LogicalAddr, []byte] `bin:"-"`
 }
 
 type DevItem struct {