Rename the module, mv pkg lib

71 files changed, 6857 insertions, 0 deletions

diff --git a/lib/binstruct/binint.go b/lib/binstruct/binint.go
new file mode 100644
index 0000000..89bb4f6
--- /dev/null
+++ b/lib/binstruct/binint.go
@@ -0,0 +1,35 @@
+package binstruct
+
+import (
+	"reflect"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct/binint"
+)
+
+type (
+	U8    = binint.U8
+	U16le = binint.U16le
+	U32le = binint.U32le
+	U64le = binint.U64le
+	U16be = binint.U16be
+	U32be = binint.U32be
+	U64be = binint.U64be
+	I8    = binint.I8
+	I16le = binint.I16le
+	I32le = binint.I32le
+	I64le = binint.I64le
+	I16be = binint.I16be
+	I32be = binint.I32be
+	I64be = binint.I64be
+)
+
+var intKind2Type = map[reflect.Kind]reflect.Type{
+	reflect.Uint8:  reflect.TypeOf(U8(0)),
+	reflect.Int8:   reflect.TypeOf(I8(0)),
+	reflect.Uint16: reflect.TypeOf(U16le(0)),
+	reflect.Int16:  reflect.TypeOf(I16le(0)),
+	reflect.Uint32: reflect.TypeOf(U32le(0)),
+	reflect.Int32:  reflect.TypeOf(I32le(0)),
+	reflect.Uint64: reflect.TypeOf(U64le(0)),
+	reflect.Int64:  reflect.TypeOf(I64le(0)),
+}
diff --git a/lib/binstruct/binint/builtins.go b/lib/binstruct/binint/builtins.go
new file mode 100644
index 0000000..04fc477
--- /dev/null
+++ b/lib/binstruct/binint/builtins.go
@@ -0,0 +1,241 @@
+package binint
+
+import (
+	"encoding/binary"
+	"fmt"
+)
+
+func needNBytes(t interface{}, dat []byte, n int) error {
+	if len(dat) < n {
+		return fmt.Errorf("%T.UnmarshalBinary: need at least %v bytes, only have %v", t, n, len(dat))
+	}
+	return nil
+}
+
+// unsigned
+
+type U8 uint8
+
+func (U8) BinaryStaticSize() int            { return 1 }
+func (x U8) MarshalBinary() ([]byte, error) { return []byte{byte(x)}, nil }
+func (x *U8) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 1); err != nil {
+		return 0, err
+	}
+	*x = U8(dat[0])
+	return 1, nil
+}
+
+// unsigned little endian
+
+type U16le uint16
+
+func (U16le) BinaryStaticSize() int { return 2 }
+func (x U16le) MarshalBinary() ([]byte, error) {
+	var buf [2]byte
+	binary.LittleEndian.PutUint16(buf[:], uint16(x))
+	return buf[:], nil
+}
+func (x *U16le) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 2); err != nil {
+		return 0, err
+	}
+	*x = U16le(binary.LittleEndian.Uint16(dat))
+	return 2, nil
+}
+
+type U32le uint32
+
+func (U32le) BinaryStaticSize() int { return 4 }
+func (x U32le) MarshalBinary() ([]byte, error) {
+	var buf [4]byte
+	binary.LittleEndian.PutUint32(buf[:], uint32(x))
+	return buf[:], nil
+}
+func (x *U32le) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 4); err != nil {
+		return 0, err
+	}
+	*x = U32le(binary.LittleEndian.Uint32(dat))
+	return 4, nil
+}
+
+type U64le uint64
+
+func (U64le) BinaryStaticSize() int { return 8 }
+func (x U64le) MarshalBinary() ([]byte, error) {
+	var buf [8]byte
+	binary.LittleEndian.PutUint64(buf[:], uint64(x))
+	return buf[:], nil
+}
+func (x *U64le) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 8); err != nil {
+		return 0, err
+	}
+	*x = U64le(binary.LittleEndian.Uint64(dat))
+	return 8, nil
+}
+
+// unsigned big endian
+
+type U16be uint16
+
+func (U16be) BinaryStaticSize() int { return 2 }
+func (x U16be) MarshalBinary() ([]byte, error) {
+	var buf [2]byte
+	binary.BigEndian.PutUint16(buf[:], uint16(x))
+	return buf[:], nil
+}
+func (x *U16be) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 2); err != nil {
+		return 0, err
+	}
+	*x = U16be(binary.BigEndian.Uint16(dat))
+	return 2, nil
+}
+
+type U32be uint32
+
+func (U32be) BinaryStaticSize() int { return 4 }
+func (x U32be) MarshalBinary() ([]byte, error) {
+	var buf [4]byte
+	binary.BigEndian.PutUint32(buf[:], uint32(x))
+	return buf[:], nil
+}
+func (x *U32be) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 4); err != nil {
+		return 0, err
+	}
+	*x = U32be(binary.BigEndian.Uint32(dat))
+	return 4, nil
+}
+
+type U64be uint64
+
+func (U64be) BinaryStaticSize() int { return 8 }
+func (x U64be) MarshalBinary() ([]byte, error) {
+	var buf [8]byte
+	binary.BigEndian.PutUint64(buf[:], uint64(x))
+	return buf[:], nil
+}
+func (x *U64be) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 8); err != nil {
+		return 0, err
+	}
+	*x = U64be(binary.BigEndian.Uint64(dat))
+	return 8, nil
+}
+
+// signed
+
+type I8 int8
+
+func (I8) BinaryStaticSize() int            { return 1 }
+func (x I8) MarshalBinary() ([]byte, error) { return []byte{byte(x)}, nil }
+func (x *I8) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 1); err != nil {
+		return 0, err
+	}
+	*x = I8(dat[0])
+	return 1, nil
+}
+
+// signed little endian
+
+type I16le int16
+
+func (I16le) BinaryStaticSize() int { return 2 }
+func (x I16le) MarshalBinary() ([]byte, error) {
+	var buf [2]byte
+	binary.LittleEndian.PutUint16(buf[:], uint16(x))
+	return buf[:], nil
+}
+func (x *I16le) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 2); err != nil {
+		return 0, err
+	}
+	*x = I16le(binary.LittleEndian.Uint16(dat))
+	return 2, nil
+}
+
+type I32le int32
+
+func (I32le) BinaryStaticSize() int { return 4 }
+func (x I32le) MarshalBinary() ([]byte, error) {
+	var buf [4]byte
+	binary.LittleEndian.PutUint32(buf[:], uint32(x))
+	return buf[:], nil
+}
+func (x *I32le) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 4); err != nil {
+		return 0, err
+	}
+	*x = I32le(binary.LittleEndian.Uint32(dat))
+	return 4, nil
+}
+
+type I64le int64
+
+func (I64le) BinaryStaticSize() int { return 8 }
+func (x I64le) MarshalBinary() ([]byte, error) {
+	var buf [8]byte
+	binary.LittleEndian.PutUint64(buf[:], uint64(x))
+	return buf[:], nil
+}
+func (x *I64le) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 8); err != nil {
+		return 0, err
+	}
+	*x = I64le(binary.LittleEndian.Uint64(dat))
+	return 8, nil
+}
+
+// signed big endian
+
+type I16be int16
+
+func (I16be) BinaryStaticSize() int { return 2 }
+func (x I16be) MarshalBinary() ([]byte, error) {
+	var buf [2]byte
+	binary.BigEndian.PutUint16(buf[:], uint16(x))
+	return buf[:], nil
+}
+func (x *I16be) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 2); err != nil {
+		return 0, err
+	}
+	*x = I16be(binary.BigEndian.Uint16(dat))
+	return 2, nil
+}
+
+type I32be int32
+
+func (I32be) BinaryStaticSize() int { return 4 }
+func (x I32be) MarshalBinary() ([]byte, error) {
+	var buf [4]byte
+	binary.BigEndian.PutUint32(buf[:], uint32(x))
+	return buf[:], nil
+}
+func (x *I32be) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 4); err != nil {
+		return 0, err
+	}
+	*x = I32be(binary.BigEndian.Uint32(dat))
+	return 4, nil
+}
+
+type I64be int64
+
+func (I64be) BinaryStaticSize() int { return 8 }
+func (x I64be) MarshalBinary() ([]byte, error) {
+	var buf [8]byte
+	binary.BigEndian.PutUint64(buf[:], uint64(x))
+	return buf[:], nil
+}
+func (x *I64be) UnmarshalBinary(dat []byte) (int, error) {
+	if err := needNBytes(*x, dat, 8); err != nil {
+		return 0, err
+	}
+	*x = I64be(binary.BigEndian.Uint64(dat))
+	return 8, nil
+}
diff --git a/lib/binstruct/binstruct_test.go b/lib/binstruct/binstruct_test.go
new file mode 100644
index 0000000..542746f
--- /dev/null
+++ b/lib/binstruct/binstruct_test.go
@@ -0,0 +1,60 @@
+package binstruct_test
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+)
+
+func TestSmoke(t *testing.T) {
+	type UUID [16]byte
+	type PhysicalAddr int64
+	type DevItem struct {
+		DeviceID uint64 `bin:"off=0x0,    siz=0x8"` // device id
+
+		NumBytes     uint64 `bin:"off=0x8,    siz=0x8"` // number of bytes
+		NumBytesUsed uint64 `bin:"off=0x10,   siz=0x8"` // number of bytes used
+
+		IOOptimalAlign uint32 `bin:"off=0x18,   siz=0x4"` // optimal I/O align
+		IOOptimalWidth uint32 `bin:"off=0x1c,   siz=0x4"` // optimal I/O width
+		IOMinSize      uint32 `bin:"off=0x20,   siz=0x4"` // minimal I/O size (sector size)
+
+		Type        uint64 `bin:"off=0x24,   siz=0x8"` // type
+		Generation  uint64 `bin:"off=0x2c,   siz=0x8"` // generation
+		StartOffset uint64 `bin:"off=0x34,   siz=0x8"` // start offset
+		DevGroup    uint32 `bin:"off=0x3c,   siz=0x4"` // dev group
+		SeekSpeed   uint8  `bin:"off=0x40,   siz=0x1"` // seek speed
+		Bandwidth   uint8  `bin:"off=0x41,   siz=0x1"` // bandwidth
+
+		DevUUID UUID `bin:"off=0x42,   siz=0x10"` // device UUID
+		FSUUID  UUID `bin:"off=0x52,   siz=0x10"` // FS UUID
+
+		binstruct.End `bin:"off=0x62"`
+	}
+	type TestType struct {
+		Magic [5]byte      `bin:"off=0x0,siz=0x5"`
+		Dev   DevItem      `bin:"off=0x5,siz=0x62"`
+		Addr  PhysicalAddr `bin:"off=0x67, siz=0x8"`
+
+		binstruct.End `bin:"off=0x6F"`
+	}
+
+	assert.Equal(t, 0x6F, binstruct.StaticSize(TestType{}))
+
+	input := TestType{}
+	copy(input.Magic[:], "mAgIc")
+	input.Dev.DeviceID = 12
+	input.Addr = 0xBEEF
+
+	bs, err := binstruct.Marshal(input)
+	assert.NoError(t, err)
+	assert.Equal(t, 0x6F, len(bs))
+
+	var output TestType
+	n, err := binstruct.Unmarshal(bs, &output)
+	assert.NoError(t, err)
+	assert.Equal(t, 0x6F, n)
+	assert.Equal(t, input, output)
+}
diff --git a/lib/binstruct/marshal.go b/lib/binstruct/marshal.go
new file mode 100644
index 0000000..684d2f3
--- /dev/null
+++ b/lib/binstruct/marshal.go
@@ -0,0 +1,42 @@
+package binstruct
+
+import (
+	"encoding"
+	"fmt"
+	"reflect"
+)
+
+type Marshaler = encoding.BinaryMarshaler
+
+func Marshal(obj any) ([]byte, error) {
+	if mar, ok := obj.(Marshaler); ok {
+		return mar.MarshalBinary()
+	}
+	return MarshalWithoutInterface(obj)
+}
+
+func MarshalWithoutInterface(obj any) ([]byte, error) {
+	val := reflect.ValueOf(obj)
+	switch val.Kind() {
+	case reflect.Uint8, reflect.Int8, reflect.Uint16, reflect.Int16, reflect.Uint32, reflect.Int32, reflect.Uint64, reflect.Int64:
+		typ := intKind2Type[val.Kind()]
+		return val.Convert(typ).Interface().(Marshaler).MarshalBinary()
+	case reflect.Ptr:
+		return Marshal(val.Elem().Interface())
+	case reflect.Array:
+		var ret []byte
+		for i := 0; i < val.Len(); i++ {
+			bs, err := Marshal(val.Index(i).Interface())
+			ret = append(ret, bs...)
+			if err != nil {
+				return ret, err
+			}
+		}
+		return ret, nil
+	case reflect.Struct:
+		return getStructHandler(val.Type()).Marshal(val)
+	default:
+		panic(fmt.Errorf("type=%v does not implement binfmt.Marshaler and kind=%v is not a supported statically-sized kind",
+			val.Type(), val.Kind()))
+	}
+}
diff --git a/lib/binstruct/size.go b/lib/binstruct/size.go
new file mode 100644
index 0000000..6563455
--- /dev/null
+++ b/lib/binstruct/size.go
@@ -0,0 +1,57 @@
+package binstruct
+
+import (
+	"fmt"
+	"reflect"
+)
+
+type StaticSizer interface {
+	BinaryStaticSize() int
+}
+
+func StaticSize(obj any) int {
+	sz, err := staticSize(reflect.TypeOf(obj))
+	if err != nil {
+		panic(err)
+	}
+	return sz
+}
+
+var (
+	staticSizerType = reflect.TypeOf((*StaticSizer)(nil)).Elem()
+	marshalerType   = reflect.TypeOf((*Marshaler)(nil)).Elem()
+	unmarshalerType = reflect.TypeOf((*Unmarshaler)(nil)).Elem()
+)
+
+func staticSize(typ reflect.Type) (int, error) {
+	if typ.Implements(staticSizerType) {
+		return reflect.New(typ).Elem().Interface().(StaticSizer).BinaryStaticSize(), nil
+	}
+	switch typ.Kind() {
+	case reflect.Uint8, reflect.Int8:
+		return 1, nil
+	case reflect.Uint16, reflect.Int16:
+		return 2, nil
+	case reflect.Uint32, reflect.Int32:
+		return 4, nil
+	case reflect.Uint64, reflect.Int64:
+		return 8, nil
+	case reflect.Ptr:
+		return staticSize(typ.Elem())
+	case reflect.Array:
+		elemSize, err := staticSize(typ.Elem())
+		if err != nil {
+			return 0, err
+		}
+		return elemSize * typ.Len(), nil
+	case reflect.Struct:
+		if !(typ.Implements(marshalerType) || typ.Implements(unmarshalerType)) {
+			return getStructHandler(typ).Size, nil
+		}
+		return 0, fmt.Errorf("type=%v (kind=%v) does not implement binfmt.StaticSizer but does implement binfmt.Marshaler or binfmt.Unmarshaler",
+			typ, typ.Kind())
+	default:
+		return 0, fmt.Errorf("type=%v does not implement binfmt.StaticSizer and kind=%v is not a supported statically-sized kind",
+			typ, typ.Kind())
+	}
+}
diff --git a/lib/binstruct/structs.go b/lib/binstruct/structs.go
new file mode 100644
index 0000000..ec2bb7d
--- /dev/null
+++ b/lib/binstruct/structs.go
@@ -0,0 +1,186 @@
+package binstruct
+
+import (
+	"fmt"
+	"reflect"
+	"strconv"
+	"strings"
+)
+
+type End struct{}
+
+var endType = reflect.TypeOf(End{})
+
+type tag struct {
+	skip bool
+
+	off int
+	siz int
+}
+
+func parseStructTag(str string) (tag, error) {
+	var ret tag
+	for _, part := range strings.Split(str, ",") {
+		part = strings.TrimSpace(part)
+		if part == "" {
+			continue
+		}
+		if part == "-" {
+			return tag{skip: true}, nil
+		}
+		keyval := strings.SplitN(part, "=", 2)
+		if len(keyval) != 2 {
+			return tag{}, fmt.Errorf("option is not a key=value pair: %q", part)
+		}
+		key := keyval[0]
+		val := keyval[1]
+		switch key {
+		case "off":
+			vint, err := strconv.ParseInt(val, 0, 0)
+			if err != nil {
+				return tag{}, err
+			}
+			ret.off = int(vint)
+		case "siz":
+			vint, err := strconv.ParseInt(val, 0, 0)
+			if err != nil {
+				return tag{}, err
+			}
+			ret.siz = int(vint)
+		default:
+			return tag{}, fmt.Errorf("unrecognized option %q", key)
+		}
+	}
+	return ret, nil
+}
+
+type structHandler struct {
+	name   string
+	Size   int
+	fields []structField
+}
+
+type structField struct {
+	name string
+	tag
+}
+
+func (sh structHandler) Unmarshal(dat []byte, dst reflect.Value) (int, error) {
+	var n int
+	for i, field := range sh.fields {
+		if field.skip {
+			continue
+		}
+		_n, err := Unmarshal(dat[n:], dst.Field(i).Addr().Interface())
+		if err != nil {
+			if _n >= 0 {
+				n += _n
+			}
+			return n, fmt.Errorf("struct %q field %v %q: %w",
+				sh.name, i, field.name, err)
+		}
+		if _n != field.siz {
+			return n, fmt.Errorf("struct %q field %v %q: consumed %v bytes but should have consumed %v bytes",
+				sh.name, i, field.name, _n, field.siz)
+		}
+		n += _n
+	}
+	return n, nil
+}
+
+func (sh structHandler) Marshal(val reflect.Value) ([]byte, error) {
+	ret := make([]byte, 0, sh.Size)
+	for i, field := range sh.fields {
+		if field.skip {
+			continue
+		}
+		bs, err := Marshal(val.Field(i).Interface())
+		ret = append(ret, bs...)
+		if err != nil {
+			return ret, fmt.Errorf("struct %q field %v %q: %w",
+				sh.name, i, field.name, err)
+		}
+	}
+	return ret, nil
+}
+
+func genStructHandler(structInfo reflect.Type) (structHandler, error) {
+	var ret structHandler
+
+	ret.name = structInfo.String()
+
+	var curOffset, endOffset int
+	for i := 0; i < structInfo.NumField(); i++ {
+		var fieldInfo reflect.StructField = structInfo.Field(i)
+
+		if fieldInfo.Anonymous && fieldInfo.Type != endType {
+			err := fmt.Errorf("binstruct does not support embedded fields")
+			return ret, fmt.Errorf("struct %q field %v %q: %w",
+				ret.name, i, fieldInfo.Name, err)
+		}
+
+		fieldTag, err := parseStructTag(fieldInfo.Tag.Get("bin"))
+		if err != nil {
+			return ret, fmt.Errorf("struct %q field %v %q: %w",
+				ret.name, i, fieldInfo.Name, err)
+		}
+		if fieldTag.skip {
+			ret.fields = append(ret.fields, structField{
+				tag:  fieldTag,
+				name: fieldInfo.Name,
+			})
+			continue
+		}
+
+		if fieldTag.off != curOffset {
+			err := fmt.Errorf("tag says off=%#x but curOffset=%#x", fieldTag.off, curOffset)
+			return ret, fmt.Errorf("struct %q field %v %q: %w",
+				ret.name, i, fieldInfo.Name, err)
+		}
+		if fieldInfo.Type == endType {
+			endOffset = curOffset
+		}
+
+		fieldSize, err := staticSize(fieldInfo.Type)
+		if err != nil {
+			return ret, fmt.Errorf("struct %q field %v %q: %w",
+				ret.name, i, fieldInfo.Name, err)
+		}
+
+		if fieldTag.siz != fieldSize {
+			err := fmt.Errorf("tag says siz=%#x but StaticSize(typ)=%#x", fieldTag.siz, fieldSize)
+			return ret, fmt.Errorf("struct %q field %v %q: %w",
+				ret.name, i, fieldInfo.Name, err)
+		}
+		curOffset += fieldTag.siz
+
+		ret.fields = append(ret.fields, structField{
+			name: fieldInfo.Name,
+			tag:  fieldTag,
+		})
+	}
+	ret.Size = curOffset
+
+	if ret.Size != endOffset {
+		return ret, fmt.Errorf("struct %q: .Size=%v but endOffset=%v",
+			ret.name, ret.Size, endOffset)
+	}
+
+	return ret, nil
+}
+
+var structCache = make(map[reflect.Type]structHandler)
+
+func getStructHandler(typ reflect.Type) structHandler {
+	h, ok := structCache[typ]
+	if ok {
+		return h
+	}
+
+	h, err := genStructHandler(typ)
+	if err != nil {
+		panic(err)
+	}
+	structCache[typ] = h
+	return h
+}
diff --git a/lib/binstruct/unmarshal.go b/lib/binstruct/unmarshal.go
new file mode 100644
index 0000000..1959d45
--- /dev/null
+++ b/lib/binstruct/unmarshal.go
@@ -0,0 +1,54 @@
+package binstruct
+
+import (
+	"fmt"
+	"reflect"
+)
+
+type Unmarshaler interface {
+	UnmarshalBinary([]byte) (int, error)
+}
+
+func Unmarshal(dat []byte, dstPtr any) (int, error) {
+	if unmar, ok := dstPtr.(Unmarshaler); ok {
+		return unmar.UnmarshalBinary(dat)
+	}
+	return UnmarshalWithoutInterface(dat, dstPtr)
+}
+
+func UnmarshalWithoutInterface(dat []byte, dstPtr any) (int, error) {
+	_dstPtr := reflect.ValueOf(dstPtr)
+	if _dstPtr.Kind() != reflect.Ptr {
+		return 0, fmt.Errorf("not a pointer: %v", _dstPtr.Type())
+	}
+	dst := _dstPtr.Elem()
+
+	switch dst.Kind() {
+	case reflect.Uint8, reflect.Int8, reflect.Uint16, reflect.Int16, reflect.Uint32, reflect.Int32, reflect.Uint64, reflect.Int64:
+		typ := intKind2Type[dst.Kind()]
+		newDstPtr := reflect.New(typ)
+		n, err := Unmarshal(dat, newDstPtr.Interface())
+		dst.Set(newDstPtr.Elem().Convert(dst.Type()))
+		return n, err
+	case reflect.Ptr:
+		elemPtr := reflect.New(dst.Type().Elem())
+		n, err := Unmarshal(dat, elemPtr.Interface())
+		dst.Set(elemPtr.Convert(dst.Type()))
+		return n, err
+	case reflect.Array:
+		var n int
+		for i := 0; i < dst.Len(); i++ {
+			_n, err := Unmarshal(dat[n:], dst.Index(i).Addr().Interface())
+			n += _n
+			if err != nil {
+				return n, err
+			}
+		}
+		return n, nil
+	case reflect.Struct:
+		return getStructHandler(dst.Type()).Unmarshal(dat, dst)
+	default:
+		panic(fmt.Errorf("type=%v does not implement binfmt.Unmarshaler and kind=%v is not a supported statically-sized kind",
+			dst.Type(), dst.Kind()))
+	}
+}
diff --git a/lib/btrfs/Makefile b/lib/btrfs/Makefile
new file mode 100644
index 0000000..43d665f
--- /dev/null
+++ b/lib/btrfs/Makefile
@@ -0,0 +1,79 @@
+.DEFAULT_GOAL = all
+.SECONDARY:
+.DELETE_ON_ERROR:
+
+btrfsitem/items.txt: btrfsitem $(wildcard btrfsitem/item_*.go) $(MAKEFILE_LIST)
+	{ \
+	  sed -En 's,^type (\S+) .* // (.*=.*),\1 \2,p' $(filter btrfsitem/item_%.go,$^) | while read -r typ keys; do \
+	    for key in $$keys; do \
+	      echo "$$key" "$$typ"; \
+	    done; \
+	  done; \
+	} | LC_COLLATE=C sort >$@
+files += btrfsitem/items.txt
+
+btrfsitem/items_gen.go: btrfsitem/items.txt $(MAKEFILE_LIST)
+	{ \
+	  echo '// Code generated by Make.  DO NOT EDIT.'; \
+	  echo; \
+	  echo 'package $(@D)'; \
+	  echo 'import ('; \
+	  echo   '"reflect"'; \
+	  echo; \
+	  echo   '"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"'; \
+	  echo ')'; \
+	  echo 'const ('; \
+	  sed -E 's,(.*)=(.*) (.*),\1_KEY=internal.\1_KEY,' $<; \
+	  echo ')'; \
+	  echo 'var keytype2gotype = map[Type]reflect.Type{'; \
+	  sed -En 's|(.*)=([^:]*) (.*)|\1_KEY: reflect.TypeOf(\3{}),|p' $<; \
+	  echo '}'; \
+	  echo 'var untypedObjID2gotype = map[internal.ObjID]reflect.Type{'; \
+	  sed -En 's|UNTYPED=0:(.*) (.*)|internal.\1: reflect.TypeOf(\2{}),|p' $<; \
+	  echo '}'; \
+	  sed -En 's,(.*)=(.*) (.+),\3,p' $< | LC_COLLATE=C sort -u | sed 's,.*,func (&) isItem() {},'; \
+	} | gofmt >$@
+files += btrfsitem/items_gen.go
+
+internal/itemtype.go: btrfsitem/items.txt $(MAKEFILE_LIST)
+	{ \
+	  echo '// Code generated by Make.  DO NOT EDIT.'; \
+	  echo; \
+	  echo 'package $(@D)'; \
+	  echo 'import "fmt"'; \
+	  echo 'type ItemType uint8'; \
+	  echo 'const ('; \
+	  sed -E 's,(.*)=([^:]*)(:.*)? (.*),\1_KEY=ItemType(\2),' $< | uniq; \
+	  echo ')'; \
+	  echo 'func (t ItemType) String() string {'; \
+	  echo '  names := map[ItemType]string{'; \
+	  sed -E 's@(.*)=(.*) (.*)@\1_KEY: "\1",@' $< | sed 's/"UUID_/&KEY_/'; \
+	  echo '  }'; \
+	  echo '  if name, ok := names[t]; ok {'; \
+	  echo '    return name'; \
+	  echo '  }'; \
+	  echo '  return fmt.Sprintf("%d", t)'; \
+	  echo '}'; \
+	} | gofmt >$@
+files += internal/itemtype.go
+
+aliases_objid.go: internal/objid.go $(MAKEFILE_LIST)
+	{ \
+	  echo '// Code generated by Make.  DO NOT EDIT.'; \
+	  echo; \
+	  echo 'package btrfs'; \
+	  echo 'import ('; \
+	  echo   '"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"'; \
+	  echo ')'; \
+	  echo 'const('; \
+	  sed -En 's/^\s*(\S*_OBJECTIDS?)\s*=.*/\1 = internal.\1/p' <$<; \
+	  echo ')'; \
+	} | gofmt >$@
+files += aliases_objid.go
+
+all: $(files)
+.PHONY: all
+
+clean:
+	rm -f -- $(files)
+.PHONY: all
diff --git a/lib/btrfs/aliases.go b/lib/btrfs/aliases.go
new file mode 100644
index 0000000..75cbf8b
--- /dev/null
+++ b/lib/btrfs/aliases.go
@@ -0,0 +1,19 @@
+package btrfs
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type (
+	// (u)int64 types
+
+	Generation = internal.Generation
+	ObjID      = internal.ObjID
+
+	// complex types
+
+	Key  = internal.Key
+	Time = internal.Time
+	UUID = util.UUID
+)
diff --git a/lib/btrfs/aliases_objid.go b/lib/btrfs/aliases_objid.go
new file mode 100644
index 0000000..6ccbbad
--- /dev/null
+++ b/lib/btrfs/aliases_objid.go
@@ -0,0 +1,37 @@
+// Code generated by Make.  DO NOT EDIT.
+
+package btrfs
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+)
+
+const (
+	ROOT_TREE_OBJECTID        = internal.ROOT_TREE_OBJECTID
+	EXTENT_TREE_OBJECTID      = internal.EXTENT_TREE_OBJECTID
+	CHUNK_TREE_OBJECTID       = internal.CHUNK_TREE_OBJECTID
+	DEV_TREE_OBJECTID         = internal.DEV_TREE_OBJECTID
+	FS_TREE_OBJECTID          = internal.FS_TREE_OBJECTID
+	ROOT_TREE_DIR_OBJECTID    = internal.ROOT_TREE_DIR_OBJECTID
+	CSUM_TREE_OBJECTID        = internal.CSUM_TREE_OBJECTID
+	QUOTA_TREE_OBJECTID       = internal.QUOTA_TREE_OBJECTID
+	UUID_TREE_OBJECTID        = internal.UUID_TREE_OBJECTID
+	FREE_SPACE_TREE_OBJECTID  = internal.FREE_SPACE_TREE_OBJECTID
+	BLOCK_GROUP_TREE_OBJECTID = internal.BLOCK_GROUP_TREE_OBJECTID
+	DEV_STATS_OBJECTID        = internal.DEV_STATS_OBJECTID
+	BALANCE_OBJECTID          = internal.BALANCE_OBJECTID
+	ORPHAN_OBJECTID           = internal.ORPHAN_OBJECTID
+	TREE_LOG_OBJECTID         = internal.TREE_LOG_OBJECTID
+	TREE_LOG_FIXUP_OBJECTID   = internal.TREE_LOG_FIXUP_OBJECTID
+	TREE_RELOC_OBJECTID       = internal.TREE_RELOC_OBJECTID
+	DATA_RELOC_TREE_OBJECTID  = internal.DATA_RELOC_TREE_OBJECTID
+	EXTENT_CSUM_OBJECTID      = internal.EXTENT_CSUM_OBJECTID
+	FREE_SPACE_OBJECTID       = internal.FREE_SPACE_OBJECTID
+	FREE_INO_OBJECTID         = internal.FREE_INO_OBJECTID
+	MULTIPLE_OBJECTIDS        = internal.MULTIPLE_OBJECTIDS
+	FIRST_FREE_OBJECTID       = internal.FIRST_FREE_OBJECTID
+	LAST_FREE_OBJECTID        = internal.LAST_FREE_OBJECTID
+	FIRST_CHUNK_TREE_OBJECTID = internal.FIRST_CHUNK_TREE_OBJECTID
+	DEV_ITEMS_OBJECTID        = internal.DEV_ITEMS_OBJECTID
+	EMPTY_SUBVOL_DIR_OBJECTID = internal.EMPTY_SUBVOL_DIR_OBJECTID
+)
diff --git a/lib/btrfs/btrfsitem/item_blockgroup.go b/lib/btrfs/btrfsitem/item_blockgroup.go
new file mode 100644
index 0000000..71d960d
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_blockgroup.go
@@ -0,0 +1,16 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+)
+
+// key.objectid = logical_addr
+// key.offset = size of chunk
+type BlockGroup struct { // BLOCK_GROUP_ITEM=192
+	Used          int64                    `bin:"off=0, siz=8"`
+	ChunkObjectID internal.ObjID           `bin:"off=8, siz=8"` // always BTRFS_FIRST_CHUNK_TREE_OBJECTID
+	Flags         btrfsvol.BlockGroupFlags `bin:"off=16, siz=8"`
+	binstruct.End `bin:"off=24"`
+}
diff --git a/lib/btrfs/btrfsitem/item_chunk.go b/lib/btrfs/btrfsitem/item_chunk.go
new file mode 100644
index 0000000..9256651
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_chunk.go
@@ -0,0 +1,90 @@
+package btrfsitem
+
+import (
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+// Maps logical address to physical.
+//
+// key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID
+// key.offset = logical_addr
+type Chunk struct { // CHUNK_ITEM=228
+	Head    ChunkHeader
+	Stripes []ChunkStripe
+}
+
+type ChunkHeader struct {
+	Size           btrfsvol.AddrDelta       `bin:"off=0x0,  siz=0x8"`
+	Owner          internal.ObjID           `bin:"off=0x8,  siz=0x8"` // root referencing this chunk (always EXTENT_TREE_OBJECTID=2)
+	StripeLen      uint64                   `bin:"off=0x10, siz=0x8"` // ???
+	Type           btrfsvol.BlockGroupFlags `bin:"off=0x18, siz=0x8"`
+	IOOptimalAlign uint32                   `bin:"off=0x20, siz=0x4"`
+	IOOptimalWidth uint32                   `bin:"off=0x24, siz=0x4"`
+	IOMinSize      uint32                   `bin:"off=0x28, siz=0x4"` // sector size
+	NumStripes     uint16                   `bin:"off=0x2c, siz=0x2"` // [ignored-when-writing]
+	SubStripes     uint16                   `bin:"off=0x2e, siz=0x2"` // ???
+	binstruct.End  `bin:"off=0x30"`
+}
+
+type ChunkStripe struct {
+	DeviceID      btrfsvol.DeviceID     `bin:"off=0x0,  siz=0x8"`
+	Offset        btrfsvol.PhysicalAddr `bin:"off=0x8,  siz=0x8"`
+	DeviceUUID    util.UUID             `bin:"off=0x10, siz=0x10"`
+	binstruct.End `bin:"off=0x20"`
+}
+
+func (chunk Chunk) Mappings(key internal.Key) []btrfsvol.Mapping {
+	ret := make([]btrfsvol.Mapping, 0, len(chunk.Stripes))
+	for _, stripe := range chunk.Stripes {
+		ret = append(ret, btrfsvol.Mapping{
+			LAddr: btrfsvol.LogicalAddr(key.Offset),
+			PAddr: btrfsvol.QualifiedPhysicalAddr{
+				Dev:  stripe.DeviceID,
+				Addr: stripe.Offset,
+			},
+			Size:       chunk.Head.Size,
+			SizeLocked: true,
+			Flags:      &chunk.Head.Type,
+		})
+	}
+	return ret
+}
+
+func (chunk *Chunk) UnmarshalBinary(dat []byte) (int, error) {
+	n, err := binstruct.Unmarshal(dat, &chunk.Head)
+	if err != nil {
+		return n, err
+	}
+	chunk.Stripes = nil
+	for i := 0; i < int(chunk.Head.NumStripes); i++ {
+		var stripe ChunkStripe
+		_n, err := binstruct.Unmarshal(dat[n:], &stripe)
+		n += _n
+		if err != nil {
+			return n, fmt.Errorf("%T.UnmarshalBinary: %w", *chunk, err)
+		}
+		chunk.Stripes = append(chunk.Stripes, stripe)
+	}
+	return n, nil
+}
+
+func (chunk Chunk) MarshalBinary() ([]byte, error) {
+	chunk.Head.NumStripes = uint16(len(chunk.Stripes))
+	ret, err := binstruct.Marshal(chunk.Head)
+	if err != nil {
+		return ret, err
+	}
+	for _, stripe := range chunk.Stripes {
+		_ret, err := binstruct.Marshal(stripe)
+		ret = append(ret, _ret...)
+		if err != nil {
+			return ret, fmt.Errorf("%T.MarshalBinary: %w", chunk, err)
+		}
+	}
+	return ret, nil
+}
diff --git a/lib/btrfs/btrfsitem/item_dev.go b/lib/btrfs/btrfsitem/item_dev.go
new file mode 100644
index 0000000..d3fe582
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_dev.go
@@ -0,0 +1,33 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+// key.objectid = BTRFS_DEV_ITEMS_OBJECTID
+// key.offset = device_id (starting at 1)
+type Dev struct { // DEV_ITEM=216
+	DevID btrfsvol.DeviceID `bin:"off=0x0,    siz=0x8"`
+
+	NumBytes     uint64 `bin:"off=0x8,    siz=0x8"`
+	NumBytesUsed uint64 `bin:"off=0x10,   siz=0x8"`
+
+	IOOptimalAlign uint32 `bin:"off=0x18,   siz=0x4"`
+	IOOptimalWidth uint32 `bin:"off=0x1c,   siz=0x4"`
+	IOMinSize      uint32 `bin:"off=0x20,   siz=0x4"` // sector size
+
+	Type        uint64              `bin:"off=0x24,   siz=0x8"`
+	Generation  internal.Generation `bin:"off=0x2c,   siz=0x8"`
+	StartOffset uint64              `bin:"off=0x34,   siz=0x8"`
+	DevGroup    uint32              `bin:"off=0x3c,   siz=0x4"`
+	SeekSpeed   uint8               `bin:"off=0x40,   siz=0x1"`
+	Bandwidth   uint8               `bin:"off=0x41,   siz=0x1"`
+
+	DevUUID util.UUID `bin:"off=0x42,   siz=0x10"`
+	FSUUID  util.UUID `bin:"off=0x52,   siz=0x10"`
+
+	binstruct.End `bin:"off=0x62"`
+}
diff --git a/lib/btrfs/btrfsitem/item_devextent.go b/lib/btrfs/btrfsitem/item_devextent.go
new file mode 100644
index 0000000..c346d85
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_devextent.go
@@ -0,0 +1,32 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+// key.objectid = device_id
+// key.offset = physical_addr
+type DevExtent struct { // DEV_EXTENT=204
+	ChunkTree     int64                `bin:"off=0, siz=8"`
+	ChunkObjectID internal.ObjID       `bin:"off=8, siz=8"`
+	ChunkOffset   btrfsvol.LogicalAddr `bin:"off=16, siz=8"`
+	Length        btrfsvol.AddrDelta   `bin:"off=24, siz=8"`
+	ChunkTreeUUID util.UUID            `bin:"off=32, siz=16"`
+	binstruct.End `bin:"off=48"`
+}
+
+func (devext DevExtent) Mapping(key internal.Key) btrfsvol.Mapping {
+	return btrfsvol.Mapping{
+		LAddr: devext.ChunkOffset,
+		PAddr: btrfsvol.QualifiedPhysicalAddr{
+			Dev:  btrfsvol.DeviceID(key.ObjectID),
+			Addr: btrfsvol.PhysicalAddr(key.Offset),
+		},
+		Size:       devext.Length,
+		SizeLocked: true,
+		Flags:      nil,
+	}
+}
diff --git a/lib/btrfs/btrfsitem/item_dir.go b/lib/btrfs/btrfsitem/item_dir.go
new file mode 100644
index 0000000..57f6d6d
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_dir.go
@@ -0,0 +1,115 @@
+package btrfsitem
+
+import (
+	"fmt"
+	"hash/crc32"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+)
+
+// key.objectid = inode of directory containing this entry
+// key.offset =
+//    for DIR_ITEM and XATTR_ITEM = NameHash(name)
+//    for DIR_INDEX               = index id in the directory (starting at 2, because "." and "..")
+type DirEntries []DirEntry // DIR_ITEM=84 DIR_INDEX=96 XATTR_ITEM=24
+
+func NameHash(dat []byte) uint64 {
+	return uint64(^crc32.Update(1, crc32.MakeTable(crc32.Castagnoli), dat))
+}
+
+func (o *DirEntries) UnmarshalBinary(dat []byte) (int, error) {
+	*o = nil
+	n := 0
+	for n < len(dat) {
+		var ref DirEntry
+		_n, err := binstruct.Unmarshal(dat, &ref)
+		n += _n
+		if err != nil {
+			return n, err
+		}
+		*o = append(*o, ref)
+	}
+	return n, nil
+}
+
+func (o DirEntries) MarshalBinary() ([]byte, error) {
+	var ret []byte
+	for _, ref := range o {
+		bs, err := binstruct.Marshal(ref)
+		ret = append(ret, bs...)
+		if err != nil {
+			return ret, err
+		}
+	}
+	return ret, nil
+}
+
+type DirEntry struct {
+	Location      internal.Key `bin:"off=0x0, siz=0x11"`
+	TransID       int64        `bin:"off=0x11, siz=8"`
+	DataLen       uint16       `bin:"off=0x19, siz=2"` // [ignored-when-writing]
+	NameLen       uint16       `bin:"off=0x1b, siz=2"` // [ignored-when-writing]
+	Type          FileType     `bin:"off=0x1d, siz=1"`
+	binstruct.End `bin:"off=0x1e"`
+	Data          []byte `bin:"-"`
+	Name          []byte `bin:"-"`
+}
+
+func (o *DirEntry) UnmarshalBinary(dat []byte) (int, error) {
+	n, err := binstruct.UnmarshalWithoutInterface(dat, o)
+	if err != nil {
+		return n, err
+	}
+	o.Data = dat[n : n+int(o.DataLen)]
+	n += int(o.DataLen)
+	o.Name = dat[n : n+int(o.NameLen)]
+	n += int(o.NameLen)
+	return n, nil
+}
+
+func (o DirEntry) MarshalBinary() ([]byte, error) {
+	o.DataLen = uint16(len(o.Data))
+	o.NameLen = uint16(len(o.Name))
+	dat, err := binstruct.MarshalWithoutInterface(o)
+	if err != nil {
+		return dat, err
+	}
+	dat = append(dat, o.Data...)
+	dat = append(dat, o.Name...)
+	return dat, nil
+}
+
+type FileType uint8
+
+const (
+	FT_UNKNOWN  = FileType(0)
+	FT_REG_FILE = FileType(1)
+	FT_DIR      = FileType(2)
+	FT_CHRDEV   = FileType(3)
+	FT_BLKDEV   = FileType(4)
+	FT_FIFO     = FileType(5)
+	FT_SOCK     = FileType(6)
+	FT_SYMLINK  = FileType(7)
+	FT_XATTR    = FileType(8)
+
+	FT_MAX = FileType(9)
+)
+
+func (ft FileType) String() string {
+	names := map[FileType]string{
+		FT_UNKNOWN:  "UNKNOWN",
+		FT_REG_FILE: "FILE", // XXX
+		FT_DIR:      "DIR",
+		FT_CHRDEV:   "CHRDEV",
+		FT_BLKDEV:   "BLKDEV",
+		FT_FIFO:     "FIFO",
+		FT_SOCK:     "SOCK",
+		FT_SYMLINK:  "SYMLINK",
+		FT_XATTR:    "XATTR",
+	}
+	if name, ok := names[ft]; ok {
+		return name
+	}
+	return fmt.Sprintf("DIR_ITEM.%d", uint8(ft))
+}
diff --git a/lib/btrfs/btrfsitem/item_empty.go b/lib/btrfs/btrfsitem/item_empty.go
new file mode 100644
index 0000000..209b2fc
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_empty.go
@@ -0,0 +1,9 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+)
+
+type Empty struct { // ORPHAN_ITEM=48 TREE_BLOCK_REF=176 SHARED_BLOCK_REF=182 FREE_SPACE_EXTENT=199 QGROUP_RELATION=246
+	binstruct.End `bin:"off=0"`
+}
diff --git a/lib/btrfs/btrfsitem/item_extent.go b/lib/btrfs/btrfsitem/item_extent.go
new file mode 100644
index 0000000..9a9ea55
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_extent.go
@@ -0,0 +1,165 @@
+package btrfsitem
+
+import (
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type Extent struct { // EXTENT_ITEM=168
+	Head ExtentHeader
+	Info TreeBlockInfo // only if .Head.Flags.Has(EXTENT_FLAG_TREE_BLOCK)
+	Refs []ExtentInlineRef
+}
+
+func (o *Extent) UnmarshalBinary(dat []byte) (int, error) {
+	n, err := binstruct.Unmarshal(dat, &o.Head)
+	if err != nil {
+		return n, err
+	}
+	if o.Head.Flags.Has(EXTENT_FLAG_TREE_BLOCK) {
+		_n, err := binstruct.Unmarshal(dat[n:], &o.Info)
+		n += _n
+		if err != nil {
+			return n, err
+		}
+	}
+	o.Refs = nil
+	for n < len(dat) {
+		var ref ExtentInlineRef
+		_n, err := binstruct.Unmarshal(dat[n:], &ref)
+		n += _n
+		o.Refs = append(o.Refs, ref)
+		if err != nil {
+			return n, err
+		}
+	}
+	return n, nil
+}
+
+func (o Extent) MarshalBinary() ([]byte, error) {
+	dat, err := binstruct.Marshal(o.Head)
+	if err != nil {
+		return dat, err
+	}
+	if o.Head.Flags.Has(EXTENT_FLAG_TREE_BLOCK) {
+		bs, err := binstruct.Marshal(o.Info)
+		dat = append(dat, bs...)
+		if err != nil {
+			return dat, err
+		}
+	}
+	for _, ref := range o.Refs {
+		bs, err := binstruct.Marshal(ref)
+		dat = append(dat, bs...)
+		if err != nil {
+			return dat, err
+		}
+	}
+	return dat, nil
+}
+
+type ExtentHeader struct {
+	Refs          int64               `bin:"off=0, siz=8"`
+	Generation    internal.Generation `bin:"off=8, siz=8"`
+	Flags         ExtentFlags         `bin:"off=16, siz=8"`
+	binstruct.End `bin:"off=24"`
+}
+
+type TreeBlockInfo struct {
+	Key           internal.Key `bin:"off=0, siz=0x11"`
+	Level         uint8        `bin:"off=0x11, siz=0x8"`
+	binstruct.End `bin:"off=0x19"`
+}
+
+type ExtentFlags uint64
+
+const (
+	EXTENT_FLAG_DATA = ExtentFlags(1 << iota)
+	EXTENT_FLAG_TREE_BLOCK
+)
+
+var extentFlagNames = []string{
+	"DATA",
+	"TREE_BLOCK",
+}
+
+func (f ExtentFlags) Has(req ExtentFlags) bool { return f&req == req }
+func (f ExtentFlags) String() string           { return util.BitfieldString(f, extentFlagNames, util.HexNone) }
+
+type ExtentInlineRef struct {
+	Type   Type   // only 4 valid values: {TREE,SHARED}_BLOCK_REF_KEY, {EXTENT,SHARED}_DATA_REF_KEY
+	Offset uint64 // only when Type != EXTENT_DATA_REF_KEY
+	Body   Item   // only when Type == *_DATA_REF_KEY
+}
+
+func (o *ExtentInlineRef) UnmarshalBinary(dat []byte) (int, error) {
+	o.Type = Type(dat[0])
+	n := 1
+	switch o.Type {
+	case TREE_BLOCK_REF_KEY, SHARED_BLOCK_REF_KEY:
+		_n, err := binstruct.Unmarshal(dat[n:], &o.Offset)
+		n += _n
+		if err != nil {
+			return n, err
+		}
+	case EXTENT_DATA_REF_KEY:
+		var dref ExtentDataRef
+		_n, err := binstruct.Unmarshal(dat[n:], &dref)
+		n += _n
+		o.Body = dref
+		if err != nil {
+			return n, err
+		}
+	case SHARED_DATA_REF_KEY:
+		_n, err := binstruct.Unmarshal(dat[n:], &o.Offset)
+		n += _n
+		if err != nil {
+			return n, err
+		}
+		var sref SharedDataRef
+		_n, err = binstruct.Unmarshal(dat[n:], &sref)
+		n += _n
+		o.Body = sref
+		if err != nil {
+			return n, err
+		}
+	default:
+		return n, fmt.Errorf("btrfsitem.ExtentInlineRef.UnmarshalBinary: unexpected item type %v", o.Type)
+	}
+	return n, nil
+}
+
+func (o ExtentInlineRef) MarshalBinary() ([]byte, error) {
+	dat := []byte{byte(o.Type)}
+	switch o.Type {
+	case TREE_BLOCK_REF_KEY, SHARED_BLOCK_REF_KEY:
+		_dat, err := binstruct.Marshal(o.Offset)
+		dat = append(dat, _dat...)
+		if err != nil {
+			return dat, err
+		}
+	case EXTENT_DATA_REF_KEY:
+		_dat, err := binstruct.Marshal(o.Body)
+		dat = append(dat, _dat...)
+		if err != nil {
+			return dat, err
+		}
+	case SHARED_DATA_REF_KEY:
+		_dat, err := binstruct.Marshal(o.Offset)
+		dat = append(dat, _dat...)
+		if err != nil {
+			return dat, err
+		}
+		_dat, err = binstruct.Marshal(o.Body)
+		dat = append(dat, _dat...)
+		if err != nil {
+			return dat, err
+		}
+	default:
+		return dat, fmt.Errorf("btrfsitem.ExtentInlineRef.MarshalBinary: unexpected item type %v", o.Type)
+	}
+	return dat, nil
+}
diff --git a/lib/btrfs/btrfsitem/item_extentcsum.go b/lib/btrfs/btrfsitem/item_extentcsum.go
new file mode 100644
index 0000000..b27dbde
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_extentcsum.go
@@ -0,0 +1,39 @@
+package btrfsitem
+
+import (
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
+)
+
+// key.objectid = BTRFS_EXTENT_CSUM_OBJECTID
+// key.offset = laddr of checksummed region
+type ExtentCSum struct { // EXTENT_CSUM=128
+	ChecksumSize int
+	// Checksum of each sector starting at key.offset
+	Sums []btrfssum.CSum
+}
+
+func (o *ExtentCSum) UnmarshalBinary(dat []byte) (int, error) {
+	if o.ChecksumSize == 0 {
+		return 0, fmt.Errorf("btrfs.ExtentCSum.UnmarshalBinary: .ChecksumSize must be set")
+	}
+	for len(dat) >= o.ChecksumSize {
+		var csum btrfssum.CSum
+		copy(csum[:], dat[:o.ChecksumSize])
+		dat = dat[o.ChecksumSize:]
+		o.Sums = append(o.Sums, csum)
+	}
+	return len(o.Sums) * o.ChecksumSize, nil
+}
+
+func (o ExtentCSum) MarshalBinary() ([]byte, error) {
+	if o.ChecksumSize == 0 {
+		return nil, fmt.Errorf("btrfs.ExtentCSum.MarshalBinary: .ChecksumSize must be set")
+	}
+	var dat []byte
+	for _, csum := range o.Sums {
+		dat = append(dat, csum[:o.ChecksumSize]...)
+	}
+	return dat, nil
+}
diff --git a/lib/btrfs/btrfsitem/item_extentdataref.go b/lib/btrfs/btrfsitem/item_extentdataref.go
new file mode 100644
index 0000000..aab5426
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_extentdataref.go
@@ -0,0 +1,14 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+)
+
+type ExtentDataRef struct { // EXTENT_DATA_REF=178
+	Root          internal.ObjID `bin:"off=0, siz=8"`
+	ObjectID      internal.ObjID `bin:"off=8, siz=8"`
+	Offset        int64          `bin:"off=16, siz=8"`
+	Count         int32          `bin:"off=24, siz=4"`
+	binstruct.End `bin:"off=28"`
+}
diff --git a/lib/btrfs/btrfsitem/item_fileextent.go b/lib/btrfs/btrfsitem/item_fileextent.go
new file mode 100644
index 0000000..2f3ac2b
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_fileextent.go
@@ -0,0 +1,137 @@
+package btrfsitem
+
+import (
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+)
+
+// key.objectid = inode
+// key.offset = offset within file
+type FileExtent struct { // EXTENT_DATA=108
+	Generation internal.Generation `bin:"off=0x0, siz=0x8"` // transaction ID that created this extent
+	RAMBytes   int64               `bin:"off=0x8, siz=0x8"` // upper bound of what compressed data will decompress to
+
+	// 32 bits describing the data encoding
+	Compression   CompressionType `bin:"off=0x10, siz=0x1"`
+	Encryption    uint8           `bin:"off=0x11, siz=0x1"`
+	OtherEncoding uint16          `bin:"off=0x12, siz=0x2"` // reserved for later use
+
+	Type FileExtentType `bin:"off=0x14, siz=0x1"` // inline data or real extent
+
+	binstruct.End `bin:"off=0x15"`
+
+	// only one of these, depending on .Type
+	BodyInline []byte   `bin:"-"` // .Type == FILE_EXTENT_INLINE
+	BodyExtent struct { // .Type == FILE_EXTENT_REG or FILE_EXTENT_PREALLOC
+		// Position and size of extent within the device
+		DiskByteNr   btrfsvol.LogicalAddr `bin:"off=0x0, siz=0x8"`
+		DiskNumBytes btrfsvol.AddrDelta   `bin:"off=0x8, siz=0x8"`
+
+		// Position of data within the extent
+		Offset btrfsvol.AddrDelta `bin:"off=0x10, siz=0x8"`
+
+		// Decompressed/unencrypted size
+		NumBytes int64 `bin:"off=0x18, siz=0x8"`
+
+		binstruct.End `bin:"off=0x20"`
+	} `bin:"-"`
+}
+
+func (o *FileExtent) UnmarshalBinary(dat []byte) (int, error) {
+	n, err := binstruct.UnmarshalWithoutInterface(dat, o)
+	if err != nil {
+		return n, err
+	}
+	switch o.Type {
+	case FILE_EXTENT_INLINE:
+		o.BodyInline = dat[n:]
+		n += len(o.BodyInline)
+	case FILE_EXTENT_REG, FILE_EXTENT_PREALLOC:
+		_n, err := binstruct.Unmarshal(dat[n:], &o.BodyExtent)
+		n += _n
+		if err != nil {
+			return n, err
+		}
+	default:
+		return n, fmt.Errorf("unknown file extent type %v", o.Type)
+	}
+	return n, nil
+}
+
+func (o FileExtent) MarshalBinary() ([]byte, error) {
+	dat, err := binstruct.MarshalWithoutInterface(o)
+	if err != nil {
+		return dat, err
+	}
+	switch o.Type {
+	case FILE_EXTENT_INLINE:
+		dat = append(dat, o.BodyInline...)
+	case FILE_EXTENT_REG, FILE_EXTENT_PREALLOC:
+		bs, err := binstruct.Marshal(o.BodyExtent)
+		dat = append(dat, bs...)
+		if err != nil {
+			return dat, err
+		}
+	default:
+		return dat, fmt.Errorf("unknown file extent type %v", o.Type)
+	}
+	return dat, nil
+}
+
+type FileExtentType uint8
+
+const (
+	FILE_EXTENT_INLINE = FileExtentType(iota)
+	FILE_EXTENT_REG
+	FILE_EXTENT_PREALLOC
+)
+
+func (o FileExtent) Size() (int64, error) {
+	switch o.Type {
+	case FILE_EXTENT_INLINE:
+		return int64(len(o.BodyInline)), nil
+	case FILE_EXTENT_REG, FILE_EXTENT_PREALLOC:
+		return o.BodyExtent.NumBytes, nil
+	default:
+		return 0, fmt.Errorf("unknown file extent type %v", o.Type)
+	}
+}
+
+func (fet FileExtentType) String() string {
+	names := map[FileExtentType]string{
+		FILE_EXTENT_INLINE:   "inline",
+		FILE_EXTENT_REG:      "regular",
+		FILE_EXTENT_PREALLOC: "prealloc",
+	}
+	name, ok := names[fet]
+	if !ok {
+		name = "unknown"
+	}
+	return fmt.Sprintf("%d (%s)", fet, name)
+}
+
+type CompressionType uint8
+
+const (
+	COMPRESS_NONE = CompressionType(iota)
+	COMPRESS_ZLIB
+	COMPRESS_LZO
+	COMPRESS_ZSTD
+)
+
+func (ct CompressionType) String() string {
+	names := map[CompressionType]string{
+		COMPRESS_NONE: "none",
+		COMPRESS_ZLIB: "zlib",
+		COMPRESS_LZO:  "lzo",
+		COMPRESS_ZSTD: "zstd",
+	}
+	name, ok := names[ct]
+	if !ok {
+		name = "unknown"
+	}
+	return fmt.Sprintf("%d (%s)", ct, name)
+}
diff --git a/lib/btrfs/btrfsitem/item_freespacebitmap.go b/lib/btrfs/btrfsitem/item_freespacebitmap.go
new file mode 100644
index 0000000..6158eb0
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_freespacebitmap.go
@@ -0,0 +1,12 @@
+package btrfsitem
+
+type FreeSpaceBitmap []byte // FREE_SPACE_BITMAP=200
+
+func (o *FreeSpaceBitmap) UnmarshalBinary(dat []byte) (int, error) {
+	*o = dat
+	return len(dat), nil
+}
+
+func (o FreeSpaceBitmap) MarshalBinary() ([]byte, error) {
+	return []byte(o), nil
+}
diff --git a/lib/btrfs/btrfsitem/item_freespaceinfo.go b/lib/btrfs/btrfsitem/item_freespaceinfo.go
new file mode 100644
index 0000000..89f555e
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_freespaceinfo.go
@@ -0,0 +1,11 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+)
+
+type FreeSpaceInfo struct { // FREE_SPACE_INFO=198
+	ExtentCount   int32  `bin:"off=0, siz=4"`
+	Flags         uint32 `bin:"off=4, siz=4"`
+	binstruct.End `bin:"off=8"`
+}
diff --git a/lib/btrfs/btrfsitem/item_inode.go b/lib/btrfs/btrfsitem/item_inode.go
new file mode 100644
index 0000000..9b1b91b
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_inode.go
@@ -0,0 +1,64 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+	"git.lukeshu.com/btrfs-progs-ng/lib/linux"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type Inode struct { // INODE_ITEM=1
+	Generation    internal.Generation `bin:"off=0x00, siz=0x08"`
+	TransID       int64               `bin:"off=0x08, siz=0x08"`
+	Size          int64               `bin:"off=0x10, siz=0x08"` // stat
+	NumBytes      int64               `bin:"off=0x18, siz=0x08"`
+	BlockGroup    int64               `bin:"off=0x20, siz=0x08"`
+	NLink         int32               `bin:"off=0x28, siz=0x04"` // stat
+	UID           int32               `bin:"off=0x2C, siz=0x04"` // stat
+	GID           int32               `bin:"off=0x30, siz=0x04"` // stat
+	Mode          linux.StatMode      `bin:"off=0x34, siz=0x04"` // stat
+	RDev          int64               `bin:"off=0x38, siz=0x08"` // stat
+	Flags         InodeFlags          `bin:"off=0x40, siz=0x08"` // statx.stx_attributes, sorta
+	Sequence      int64               `bin:"off=0x48, siz=0x08"` // NFS
+	Reserved      [4]int64            `bin:"off=0x50, siz=0x20"`
+	ATime         internal.Time       `bin:"off=0x70, siz=0x0c"` // stat
+	CTime         internal.Time       `bin:"off=0x7c, siz=0x0c"` // stat
+	MTime         internal.Time       `bin:"off=0x88, siz=0x0c"` // stat
+	OTime         internal.Time       `bin:"off=0x94, siz=0x0c"` // statx.stx_btime (why is this called "otime" instead of "btime"?)
+	binstruct.End `bin:"off=0xa0"`
+}
+
+type InodeFlags uint64
+
+const (
+	INODE_NODATASUM = InodeFlags(1 << iota)
+	INODE_NODATACOW
+	INODE_READONLY
+	INODE_NOCOMPRESS
+	INODE_PREALLOC
+	INODE_SYNC
+	INODE_IMMUTABLE
+	INODE_APPEND
+	INODE_NODUMP
+	INODE_NOATIME
+	INODE_DIRSYNC
+	INODE_COMPRESS
+)
+
+var inodeFlagNames = []string{
+	"NODATASUM",
+	"NODATACOW",
+	"READONLY",
+	"NOCOMPRESS",
+	"PREALLOC",
+	"SYNC",
+	"IMMUTABLE",
+	"APPEND",
+	"NODUMP",
+	"NOATIME",
+	"DIRSYNC",
+	"COMPRESS",
+}
+
+func (f InodeFlags) Has(req InodeFlags) bool { return f&req == req }
+func (f InodeFlags) String() string          { return util.BitfieldString(f, inodeFlagNames, util.HexLower) }
diff --git a/lib/btrfs/btrfsitem/item_inoderef.go b/lib/btrfs/btrfsitem/item_inoderef.go
new file mode 100644
index 0000000..80d70e1
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_inoderef.go
@@ -0,0 +1,35 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+)
+
+// key.objectid = inode number of the file
+// key.offset = inode number of the parent file
+type InodeRef struct { // INODE_REF=12
+	Index         int64  `bin:"off=0x0, siz=0x8"`
+	NameLen       uint16 `bin:"off=0x8, siz=0x2"` // [ignored-when-writing]
+	binstruct.End `bin:"off=0xa"`
+	Name          []byte `bin:"-"`
+}
+
+func (o *InodeRef) UnmarshalBinary(dat []byte) (int, error) {
+	n, err := binstruct.UnmarshalWithoutInterface(dat, o)
+	if err != nil {
+		return n, err
+	}
+	dat = dat[n:]
+	o.Name = dat[:o.NameLen]
+	n += int(o.NameLen)
+	return n, nil
+}
+
+func (o InodeRef) MarshalBinary() ([]byte, error) {
+	o.NameLen = uint16(len(o.Name))
+	dat, err := binstruct.MarshalWithoutInterface(o)
+	if err != nil {
+		return dat, err
+	}
+	dat = append(dat, o.Name...)
+	return dat, nil
+}
diff --git a/lib/btrfs/btrfsitem/item_metadata.go b/lib/btrfs/btrfsitem/item_metadata.go
new file mode 100644
index 0000000..d51a340
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_metadata.go
@@ -0,0 +1,44 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+)
+
+// Metadata is like Extent, but doesn't have .Info.
+type Metadata struct { // METADATA_ITEM=169
+	Head ExtentHeader
+	Refs []ExtentInlineRef
+}
+
+func (o *Metadata) UnmarshalBinary(dat []byte) (int, error) {
+	n, err := binstruct.Unmarshal(dat, &o.Head)
+	if err != nil {
+		return n, err
+	}
+	o.Refs = nil
+	for n < len(dat) {
+		var ref ExtentInlineRef
+		_n, err := binstruct.Unmarshal(dat[n:], &ref)
+		n += _n
+		o.Refs = append(o.Refs, ref)
+		if err != nil {
+			return n, err
+		}
+	}
+	return n, nil
+}
+
+func (o Metadata) MarshalBinary() ([]byte, error) {
+	dat, err := binstruct.Marshal(o.Head)
+	if err != nil {
+		return dat, err
+	}
+	for _, ref := range o.Refs {
+		bs, err := binstruct.Marshal(ref)
+		dat = append(dat, bs...)
+		if err != nil {
+			return dat, err
+		}
+	}
+	return dat, nil
+}
diff --git a/lib/btrfs/btrfsitem/item_persistent.go b/lib/btrfs/btrfsitem/item_persistent.go
new file mode 100644
index 0000000..cbbae76
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_persistent.go
@@ -0,0 +1,19 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+)
+
+const (
+	DEV_STAT_WRITE_ERRS = iota
+	DEV_STAT_READ_ERRS
+	DEV_STAT_FLUSH_ERRS
+	DEV_STAT_CORRUPTION_ERRS
+	DEV_STAT_GENERATION_ERRS
+	DEV_STAT_VALUES_MAX
+)
+
+type DevStats struct { // PERSISTENT_ITEM=249
+	Values        [DEV_STAT_VALUES_MAX]int64 `bin:"off=0, siz=40"`
+	binstruct.End `bin:"off=40"`
+}
diff --git a/lib/btrfs/btrfsitem/item_root.go b/lib/btrfs/btrfsitem/item_root.go
new file mode 100644
index 0000000..ff9311f
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_root.go
@@ -0,0 +1,51 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type Root struct { // ROOT_ITEM=132
+	Inode         Inode                `bin:"off=0x000, siz=0xa0"`
+	Generation    internal.Generation  `bin:"off=0x0a0, siz=0x08"`
+	RootDirID     internal.ObjID       `bin:"off=0x0a8, siz=0x08"`
+	ByteNr        btrfsvol.LogicalAddr `bin:"off=0x0b0, siz=0x08"`
+	ByteLimit     int64                `bin:"off=0x0b8, siz=0x08"`
+	BytesUsed     int64                `bin:"off=0x0c0, siz=0x08"`
+	LastSnapshot  int64                `bin:"off=0x0c8, siz=0x08"`
+	Flags         RootFlags            `bin:"off=0x0d0, siz=0x08"`
+	Refs          int32                `bin:"off=0x0d8, siz=0x04"`
+	DropProgress  internal.Key         `bin:"off=0x0dc, siz=0x11"`
+	DropLevel     uint8                `bin:"off=0x0ed, siz=0x01"`
+	Level         uint8                `bin:"off=0x0ee, siz=0x01"`
+	GenerationV2  internal.Generation  `bin:"off=0x0ef, siz=0x08"`
+	UUID          util.UUID            `bin:"off=0x0f7, siz=0x10"`
+	ParentUUID    util.UUID            `bin:"off=0x107, siz=0x10"`
+	ReceivedUUID  util.UUID            `bin:"off=0x117, siz=0x10"`
+	CTransID      int64                `bin:"off=0x127, siz=0x08"`
+	OTransID      int64                `bin:"off=0x12f, siz=0x08"`
+	STransID      int64                `bin:"off=0x137, siz=0x08"`
+	RTransID      int64                `bin:"off=0x13f, siz=0x08"`
+	CTime         internal.Time        `bin:"off=0x147, siz=0x0c"`
+	OTime         internal.Time        `bin:"off=0x153, siz=0x0c"`
+	STime         internal.Time        `bin:"off=0x15f, siz=0x0c"`
+	RTime         internal.Time        `bin:"off=0x16b, siz=0x0c"`
+	GlobalTreeID  internal.ObjID       `bin:"off=0x177, siz=0x08"`
+	Reserved      [7]int64             `bin:"off=0x17f, siz=0x38"`
+	binstruct.End `bin:"off=0x1b7"`
+}
+
+type RootFlags uint64
+
+const (
+	ROOT_SUBVOL_RDONLY = RootFlags(1 << iota)
+)
+
+var rootFlagNames = []string{
+	"SUBVOL_RDONLY",
+}
+
+func (f RootFlags) Has(req RootFlags) bool { return f&req == req }
+func (f RootFlags) String() string         { return util.BitfieldString(f, rootFlagNames, util.HexLower) }
diff --git a/lib/btrfs/btrfsitem/item_rootref.go b/lib/btrfs/btrfsitem/item_rootref.go
new file mode 100644
index 0000000..c851474
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_rootref.go
@@ -0,0 +1,34 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+)
+
+type RootRef struct { // ROOT_REF=156 ROOT_BACKREF=144
+	DirID         internal.ObjID `bin:"off=0x00, siz=0x8"`
+	Sequence      int64          `bin:"off=0x08, siz=0x8"`
+	NameLen       uint16         `bin:"off=0x10, siz=0x2"` // [ignored-when-writing]
+	binstruct.End `bin:"off=0x12"`
+	Name          []byte `bin:"-"`
+}
+
+func (o *RootRef) UnmarshalBinary(dat []byte) (int, error) {
+	n, err := binstruct.UnmarshalWithoutInterface(dat, o)
+	if err != nil {
+		return n, err
+	}
+	o.Name = dat[n : n+int(o.NameLen)]
+	n += int(o.NameLen)
+	return n, nil
+}
+
+func (o RootRef) MarshalBinary() ([]byte, error) {
+	o.NameLen = uint16(len(o.Name))
+	dat, err := binstruct.MarshalWithoutInterface(o)
+	if err != nil {
+		return dat, err
+	}
+	dat = append(dat, o.Name...)
+	return dat, nil
+}
diff --git a/lib/btrfs/btrfsitem/item_shareddataref.go b/lib/btrfs/btrfsitem/item_shareddataref.go
new file mode 100644
index 0000000..63897aa
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_shareddataref.go
@@ -0,0 +1,10 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+)
+
+type SharedDataRef struct { // SHARED_DATA_REF=184
+	Count         int32 `bin:"off=0, siz=4"`
+	binstruct.End `bin:"off=4"`
+}
diff --git a/lib/btrfs/btrfsitem/item_untyped.go b/lib/btrfs/btrfsitem/item_untyped.go
new file mode 100644
index 0000000..71a9af4
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_untyped.go
@@ -0,0 +1,14 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+)
+
+type FreeSpaceHeader struct { // UNTYPED=0:FREE_SPACE_OBJECTID
+	Location      internal.Key        `bin:"off=0x00, siz=0x11"`
+	Generation    internal.Generation `bin:"off=0x11, siz=0x8"`
+	NumEntries    int64               `bin:"off=0x19, siz=0x8"`
+	NumBitmaps    int64               `bin:"off=0x21, siz=0x8"`
+	binstruct.End `bin:"off=0x29"`
+}
diff --git a/lib/btrfs/btrfsitem/item_uuid.go b/lib/btrfs/btrfsitem/item_uuid.go
new file mode 100644
index 0000000..6c7d4f0
--- /dev/null
+++ b/lib/btrfs/btrfsitem/item_uuid.go
@@ -0,0 +1,16 @@
+package btrfsitem
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+)
+
+// The Key for this item is a UUID, and the item is a subvolume IDs
+// that that UUID maps to.
+//
+// key.objectid = first half of UUID
+// key.offset = second half of UUID
+type UUIDMap struct { // UUID_SUBVOL=251 UUID_RECEIVED_SUBVOL=252
+	ObjID         internal.ObjID `bin:"off=0, siz=8"`
+	binstruct.End `bin:"off=8"`
+}
diff --git a/lib/btrfs/btrfsitem/items.go b/lib/btrfs/btrfsitem/items.go
new file mode 100644
index 0000000..33ff390
--- /dev/null
+++ b/lib/btrfs/btrfsitem/items.go
@@ -0,0 +1,77 @@
+package btrfsitem
+
+import (
+	"fmt"
+	"reflect"
+
+	"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/internal"
+)
+
+type Type = internal.ItemType
+
+type Item interface {
+	isItem()
+}
+
+type Error struct {
+	Dat []byte
+	Err error
+}
+
+func (Error) isItem() {}
+
+func (o Error) MarshalBinary() ([]byte, error) {
+	return o.Dat, nil
+}
+
+func (o *Error) UnmarshalBinary(dat []byte) (int, error) {
+	o.Dat = dat
+	return len(dat), nil
+}
+
+// Rather than returning a separate error  value, return an Error item.
+func UnmarshalItem(key internal.Key, csumType btrfssum.CSumType, dat []byte) Item {
+	var gotyp reflect.Type
+	if key.ItemType == UNTYPED_KEY {
+		var ok bool
+		gotyp, ok = untypedObjID2gotype[key.ObjectID]
+		if !ok {
+			return Error{
+				Dat: dat,
+				Err: fmt.Errorf("btrfsitem.UnmarshalItem({ItemType:%v, ObjectID:%v}, dat): unknown object ID for untyped item",
+					key.ItemType, key.ObjectID),
+			}
+		}
+	} else {
+		var ok bool
+		gotyp, ok = keytype2gotype[key.ItemType]
+		if !ok {
+			return Error{
+				Dat: dat,
+				Err: fmt.Errorf("btrfsitem.UnmarshalItem({ItemType:%v}, dat): unknown item type", key.ItemType),
+			}
+		}
+	}
+	retPtr := reflect.New(gotyp)
+	if csums, ok := retPtr.Interface().(*ExtentCSum); ok {
+		csums.ChecksumSize = csumType.Size()
+	}
+	n, err := binstruct.Unmarshal(dat, retPtr.Interface())
+	if err != nil {
+		return Error{
+			Dat: dat,
+			Err: fmt.Errorf("btrfsitem.UnmarshalItem({ItemType:%v}, dat): %w", key.ItemType, err),
+		}
+
+	}
+	if n < len(dat) {
+		return Error{
+			Dat: dat,
+			Err: fmt.Errorf("btrfsitem.UnmarshalItem({ItemType:%v}, dat): left over data: got %v bytes but only consumed %v",
+				key.ItemType, len(dat), n),
+		}
+	}
+	return retPtr.Elem().Interface().(Item)
+}
diff --git a/lib/btrfs/btrfsitem/items.txt b/lib/btrfs/btrfsitem/items.txt
new file mode 100644
index 0000000..7898775
--- /dev/null
+++ b/lib/btrfs/btrfsitem/items.txt
@@ -0,0 +1,29 @@
+BLOCK_GROUP_ITEM=192 BlockGroup
+CHUNK_ITEM=228 Chunk
+DEV_EXTENT=204 DevExtent
+DEV_ITEM=216 Dev
+DIR_INDEX=96 DirEntries
+DIR_ITEM=84 DirEntries
+EXTENT_CSUM=128 ExtentCSum
+EXTENT_DATA=108 FileExtent
+EXTENT_DATA_REF=178 ExtentDataRef
+EXTENT_ITEM=168 Extent
+FREE_SPACE_BITMAP=200 FreeSpaceBitmap
+FREE_SPACE_EXTENT=199 Empty
+FREE_SPACE_INFO=198 FreeSpaceInfo
+INODE_ITEM=1 Inode
+INODE_REF=12 InodeRef
+METADATA_ITEM=169 Metadata
+ORPHAN_ITEM=48 Empty
+PERSISTENT_ITEM=249 DevStats
+QGROUP_RELATION=246 Empty
+ROOT_BACKREF=144 RootRef
+ROOT_ITEM=132 Root
+ROOT_REF=156 RootRef
+SHARED_BLOCK_REF=182 Empty
+SHARED_DATA_REF=184 SharedDataRef
+TREE_BLOCK_REF=176 Empty
+UNTYPED=0:FREE_SPACE_OBJECTID FreeSpaceHeader
+UUID_RECEIVED_SUBVOL=252 UUIDMap
+UUID_SUBVOL=251 UUIDMap
+XATTR_ITEM=24 DirEntries
diff --git a/lib/btrfs/btrfsitem/items_gen.go b/lib/btrfs/btrfsitem/items_gen.go
new file mode 100644
index 0000000..3b84d60
--- /dev/null
+++ b/lib/btrfs/btrfsitem/items_gen.go
@@ -0,0 +1,97 @@
+// Code generated by Make.  DO NOT EDIT.
+
+package btrfsitem
+
+import (
+	"reflect"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"
+)
+
+const (
+	BLOCK_GROUP_ITEM_KEY     = internal.BLOCK_GROUP_ITEM_KEY
+	CHUNK_ITEM_KEY           = internal.CHUNK_ITEM_KEY
+	DEV_EXTENT_KEY           = internal.DEV_EXTENT_KEY
+	DEV_ITEM_KEY             = internal.DEV_ITEM_KEY
+	DIR_INDEX_KEY            = internal.DIR_INDEX_KEY
+	DIR_ITEM_KEY             = internal.DIR_ITEM_KEY
+	EXTENT_CSUM_KEY          = internal.EXTENT_CSUM_KEY
+	EXTENT_DATA_KEY          = internal.EXTENT_DATA_KEY
+	EXTENT_DATA_REF_KEY      = internal.EXTENT_DATA_REF_KEY
+	EXTENT_ITEM_KEY          = internal.EXTENT_ITEM_KEY
+	FREE_SPACE_BITMAP_KEY    = internal.FREE_SPACE_BITMAP_KEY
+	FREE_SPACE_EXTENT_KEY    = internal.FREE_SPACE_EXTENT_KEY
+	FREE_SPACE_INFO_KEY      = internal.FREE_SPACE_INFO_KEY
+	INODE_ITEM_KEY           = internal.INODE_ITEM_KEY
+	INODE_REF_KEY            = internal.INODE_REF_KEY
+	METADATA_ITEM_KEY        = internal.METADATA_ITEM_KEY
+	ORPHAN_ITEM_KEY          = internal.ORPHAN_ITEM_KEY
+	PERSISTENT_ITEM_KEY      = internal.PERSISTENT_ITEM_KEY
+	QGROUP_RELATION_KEY      = internal.QGROUP_RELATION_KEY
+	ROOT_BACKREF_KEY         = internal.ROOT_BACKREF_KEY
+	ROOT_ITEM_KEY            = internal.ROOT_ITEM_KEY
+	ROOT_REF_KEY             = internal.ROOT_REF_KEY
+	SHARED_BLOCK_REF_KEY     = internal.SHARED_BLOCK_REF_KEY
+	SHARED_DATA_REF_KEY      = internal.SHARED_DATA_REF_KEY
+	TREE_BLOCK_REF_KEY       = internal.TREE_BLOCK_REF_KEY
+	UNTYPED_KEY              = internal.UNTYPED_KEY
+	UUID_RECEIVED_SUBVOL_KEY = internal.UUID_RECEIVED_SUBVOL_KEY
+	UUID_SUBVOL_KEY          = internal.UUID_SUBVOL_KEY
+	XATTR_ITEM_KEY           = internal.XATTR_ITEM_KEY
+)
+
+var keytype2gotype = map[Type]reflect.Type{
+	BLOCK_GROUP_ITEM_KEY:     reflect.TypeOf(BlockGroup{}),
+	CHUNK_ITEM_KEY:           reflect.TypeOf(Chunk{}),
+	DEV_EXTENT_KEY:           reflect.TypeOf(DevExtent{}),
+	DEV_ITEM_KEY:             reflect.TypeOf(Dev{}),
+	DIR_INDEX_KEY:            reflect.TypeOf(DirEntries{}),
+	DIR_ITEM_KEY:             reflect.TypeOf(DirEntries{}),
+	EXTENT_CSUM_KEY:          reflect.TypeOf(ExtentCSum{}),
+	EXTENT_DATA_KEY:          reflect.TypeOf(FileExtent{}),
+	EXTENT_DATA_REF_KEY:      reflect.TypeOf(ExtentDataRef{}),
+	EXTENT_ITEM_KEY:          reflect.TypeOf(Extent{}),
+	FREE_SPACE_BITMAP_KEY:    reflect.TypeOf(FreeSpaceBitmap{}),
+	FREE_SPACE_EXTENT_KEY:    reflect.TypeOf(Empty{}),
+	FREE_SPACE_INFO_KEY:      reflect.TypeOf(FreeSpaceInfo{}),
+	INODE_ITEM_KEY:           reflect.TypeOf(Inode{}),
+	INODE_REF_KEY:            reflect.TypeOf(InodeRef{}),
+	METADATA_ITEM_KEY:        reflect.TypeOf(Metadata{}),
+	ORPHAN_ITEM_KEY:          reflect.TypeOf(Empty{}),
+	PERSISTENT_ITEM_KEY:      reflect.TypeOf(DevStats{}),
+	QGROUP_RELATION_KEY:      reflect.TypeOf(Empty{}),
+	ROOT_BACKREF_KEY:         reflect.TypeOf(RootRef{}),
+	ROOT_ITEM_KEY:            reflect.TypeOf(Root{}),
+	ROOT_REF_KEY:             reflect.TypeOf(RootRef{}),
+	SHARED_BLOCK_REF_KEY:     reflect.TypeOf(Empty{}),
+	SHARED_DATA_REF_KEY:      reflect.TypeOf(SharedDataRef{}),
+	TREE_BLOCK_REF_KEY:       reflect.TypeOf(Empty{}),
+	UUID_RECEIVED_SUBVOL_KEY: reflect.TypeOf(UUIDMap{}),
+	UUID_SUBVOL_KEY:          reflect.TypeOf(UUIDMap{}),
+	XATTR_ITEM_KEY:           reflect.TypeOf(DirEntries{}),
+}
+var untypedObjID2gotype = map[internal.ObjID]reflect.Type{
+	internal.FREE_SPACE_OBJECTID: reflect.TypeOf(FreeSpaceHeader{}),
+}
+
+func (BlockGroup) isItem()      {}
+func (Chunk) isItem()           {}
+func (Dev) isItem()             {}
+func (DevExtent) isItem()       {}
+func (DevStats) isItem()        {}
+func (DirEntries) isItem()      {}
+func (Empty) isItem()           {}
+func (Extent) isItem()          {}
+func (ExtentCSum) isItem()      {}
+func (ExtentDataRef) isItem()   {}
+func (FileExtent) isItem()      {}
+func (FreeSpaceBitmap) isItem() {}
+func (FreeSpaceHeader) isItem() {}
+func (FreeSpaceInfo) isItem()   {}
+func (Inode) isItem()           {}
+func (InodeRef) isItem()        {}
+func (Metadata) isItem()        {}
+func (Root) isItem()            {}
+func (RootRef) isItem()         {}
+func (SharedDataRef) isItem()   {}
+func (UUIDMap) isItem()         {}
diff --git a/lib/btrfs/btrfssum/csum.go b/lib/btrfs/btrfssum/csum.go
new file mode 100644
index 0000000..11a8385
--- /dev/null
+++ b/lib/btrfs/btrfssum/csum.go
@@ -0,0 +1,78 @@
+package btrfssum
+
+import (
+	"encoding/binary"
+	"encoding/hex"
+	"fmt"
+	"hash/crc32"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type CSum [0x20]byte
+
+func (csum CSum) String() string {
+	return hex.EncodeToString(csum[:])
+}
+
+func (csum CSum) Fmt(typ CSumType) string {
+	return hex.EncodeToString(csum[:typ.Size()])
+}
+
+func (csum CSum) Format(f fmt.State, verb rune) {
+	util.FormatByteArrayStringer(csum, csum[:], f, verb)
+}
+
+type CSumType uint16
+
+const (
+	TYPE_CRC32 = CSumType(iota)
+	TYPE_XXHASH
+	TYPE_SHA256
+	TYPE_BLAKE2
+)
+
+func (typ CSumType) String() string {
+	names := map[CSumType]string{
+		TYPE_CRC32:  "crc32c",
+		TYPE_XXHASH: "xxhash64",
+		TYPE_SHA256: "sha256",
+		TYPE_BLAKE2: "blake2",
+	}
+	if name, ok := names[typ]; ok {
+		return name
+	}
+	return fmt.Sprintf("%d", typ)
+}
+
+func (typ CSumType) Size() int {
+	sizes := map[CSumType]int{
+		TYPE_CRC32:  4,
+		TYPE_XXHASH: 8,
+		TYPE_SHA256: 32,
+		TYPE_BLAKE2: 32,
+	}
+	if size, ok := sizes[typ]; ok {
+		return size
+	}
+	return len(CSum{})
+}
+
+func (typ CSumType) Sum(data []byte) (CSum, error) {
+	switch typ {
+	case TYPE_CRC32:
+		crc := crc32.Update(0, crc32.MakeTable(crc32.Castagnoli), data)
+
+		var ret CSum
+		binary.LittleEndian.PutUint32(ret[:], crc)
+		return ret, nil
+	case TYPE_XXHASH:
+		panic("not implemented")
+	case TYPE_SHA256:
+		panic("not implemented")
+	case TYPE_BLAKE2:
+		panic("not implemented")
+	default:
+		return CSum{}, fmt.Errorf("unknown checksum type: %v", typ)
+	}
+}
diff --git a/lib/btrfs/btrfssum/csum_test.go b/lib/btrfs/btrfssum/csum_test.go
new file mode 100644
index 0000000..755ecc1
--- /dev/null
+++ b/lib/btrfs/btrfssum/csum_test.go
@@ -0,0 +1,35 @@
+package btrfssum_test
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
+)
+
+func TestCSumFormat(t *testing.T) {
+	t.Parallel()
+	type TestCase struct {
+		InputSum btrfssum.CSum
+		InputFmt string
+		Output   string
+	}
+	csum := btrfssum.CSum{0xbd, 0x7b, 0x41, 0xf4, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}
+	testcases := map[string]TestCase{
+		"s":     {InputSum: csum, InputFmt: "%s", Output: "bd7b41f400000000000000000000000000000000000000000000000000000000"},
+		"x":     {InputSum: csum, InputFmt: "%x", Output: "bd7b41f400000000000000000000000000000000000000000000000000000000"},
+		"v":     {InputSum: csum, InputFmt: "%v", Output: "bd7b41f400000000000000000000000000000000000000000000000000000000"},
+		"70s":   {InputSum: csum, InputFmt: "|% 70s", Output: "|      bd7b41f400000000000000000000000000000000000000000000000000000000"},
+		"#180v": {InputSum: csum, InputFmt: "%#180v", Output: "   btrfssum.CSum{0xbd, 0x7b, 0x41, 0xf4, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}"},
+	}
+	for tcName, tc := range testcases {
+		tc := tc
+		t.Run(tcName, func(t *testing.T) {
+			t.Parallel()
+			actual := fmt.Sprintf(tc.InputFmt, tc.InputSum)
+			assert.Equal(t, tc.Output, actual)
+		})
+	}
+}
diff --git a/lib/btrfs/btrfsvol/addr.go b/lib/btrfs/btrfsvol/addr.go
new file mode 100644
index 0000000..6c67826
--- /dev/null
+++ b/lib/btrfs/btrfsvol/addr.go
@@ -0,0 +1,47 @@
+package btrfsvol
+
+import (
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type (
+	PhysicalAddr int64
+	LogicalAddr  int64
+	AddrDelta    int64
+)
+
+func formatAddr(addr int64, f fmt.State, verb rune) {
+	switch verb {
+	case 'v', 's', 'q':
+		str := fmt.Sprintf("%#016x", addr)
+		fmt.Fprintf(f, util.FmtStateString(f, verb), str)
+	default:
+		fmt.Fprintf(f, util.FmtStateString(f, verb), addr)
+	}
+}
+
+func (a PhysicalAddr) Format(f fmt.State, verb rune) { formatAddr(int64(a), f, verb) }
+func (a LogicalAddr) Format(f fmt.State, verb rune)  { formatAddr(int64(a), f, verb) }
+func (d AddrDelta) Format(f fmt.State, verb rune)    { formatAddr(int64(d), f, verb) }
+
+func (a PhysicalAddr) Sub(b PhysicalAddr) AddrDelta { return AddrDelta(a - b) }
+func (a LogicalAddr) Sub(b LogicalAddr) AddrDelta   { return AddrDelta(a - b) }
+
+func (a PhysicalAddr) Add(b AddrDelta) PhysicalAddr { return a + PhysicalAddr(b) }
+func (a LogicalAddr) Add(b AddrDelta) LogicalAddr   { return a + LogicalAddr(b) }
+
+type DeviceID uint64
+
+type QualifiedPhysicalAddr struct {
+	Dev  DeviceID
+	Addr PhysicalAddr
+}
+
+func (a QualifiedPhysicalAddr) Cmp(b QualifiedPhysicalAddr) int {
+	if d := int(a.Dev - b.Dev); d != 0 {
+		return d
+	}
+	return int(a.Addr - b.Addr)
+}
diff --git a/lib/btrfs/btrfsvol/addr_test.go b/lib/btrfs/btrfsvol/addr_test.go
new file mode 100644
index 0000000..aae6378
--- /dev/null
+++ b/lib/btrfs/btrfsvol/addr_test.go
@@ -0,0 +1,36 @@
+package btrfsvol_test
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+)
+
+func TestAddrFormat(t *testing.T) {
+	t.Parallel()
+	type TestCase struct {
+		InputAddr btrfsvol.LogicalAddr
+		InputFmt  string
+		Output    string
+	}
+	addr := btrfsvol.LogicalAddr(0x3a41678000)
+	testcases := map[string]TestCase{
+		"v":   {InputAddr: addr, InputFmt: "%v", Output: "0x0000003a41678000"},
+		"s":   {InputAddr: addr, InputFmt: "%s", Output: "0x0000003a41678000"},
+		"q":   {InputAddr: addr, InputFmt: "%q", Output: `"0x0000003a41678000"`},
+		"x":   {InputAddr: addr, InputFmt: "%x", Output: "3a41678000"},
+		"d":   {InputAddr: addr, InputFmt: "%d", Output: "250205405184"},
+		"neg": {InputAddr: -1, InputFmt: "%v", Output: "-0x000000000000001"},
+	}
+	for tcName, tc := range testcases {
+		tc := tc
+		t.Run(tcName, func(t *testing.T) {
+			t.Parallel()
+			actual := fmt.Sprintf(tc.InputFmt, tc.InputAddr)
+			assert.Equal(t, tc.Output, actual)
+		})
+	}
+}
diff --git a/lib/btrfs/btrfsvol/blockgroupflags.go b/lib/btrfs/btrfsvol/blockgroupflags.go
new file mode 100644
index 0000000..1a194d7
--- /dev/null
+++ b/lib/btrfs/btrfsvol/blockgroupflags.go
@@ -0,0 +1,51 @@
+package btrfsvol
+
+import (
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type BlockGroupFlags uint64
+
+const (
+	BLOCK_GROUP_DATA = BlockGroupFlags(1 << iota)
+	BLOCK_GROUP_SYSTEM
+	BLOCK_GROUP_METADATA
+	BLOCK_GROUP_RAID0
+	BLOCK_GROUP_RAID1
+	BLOCK_GROUP_DUP
+	BLOCK_GROUP_RAID10
+	BLOCK_GROUP_RAID5
+	BLOCK_GROUP_RAID6
+	BLOCK_GROUP_RAID1C3
+	BLOCK_GROUP_RAID1C4
+
+	BLOCK_GROUP_RAID_MASK = (BLOCK_GROUP_RAID1 | BLOCK_GROUP_DUP | BLOCK_GROUP_RAID10 | BLOCK_GROUP_RAID5 | BLOCK_GROUP_RAID6 | BLOCK_GROUP_RAID1C3 | BLOCK_GROUP_RAID1C4)
+)
+
+var blockGroupFlagNames = []string{
+	"DATA",
+	"SYSTEM",
+	"METADATA",
+
+	"RAID0",
+	"RAID1",
+	"DUP",
+	"RAID10",
+	"RAID5",
+	"RAID6",
+	"RAID1C3",
+	"RAID1C4",
+}
+
+func (f BlockGroupFlags) Has(req BlockGroupFlags) bool { return f&req == req }
+func (f BlockGroupFlags) String() string {
+	ret := util.BitfieldString(f, blockGroupFlagNames, util.HexNone)
+	if f&BLOCK_GROUP_RAID_MASK == 0 {
+		if ret == "" {
+			ret = "single"
+		} else {
+			ret += "|single"
+		}
+	}
+	return ret
+}
diff --git a/lib/btrfs/btrfsvol/chunk.go b/lib/btrfs/btrfsvol/chunk.go
new file mode 100644
index 0000000..6aea483
--- /dev/null
+++ b/lib/btrfs/btrfsvol/chunk.go
@@ -0,0 +1,96 @@
+package btrfsvol
+
+import (
+	"fmt"
+	"sort"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+// logical => []physical
+type chunkMapping struct {
+	LAddr      LogicalAddr
+	PAddrs     []QualifiedPhysicalAddr
+	Size       AddrDelta
+	SizeLocked bool
+	Flags      *BlockGroupFlags
+}
+
+type ChunkMapping = chunkMapping
+
+// return -1 if 'a' is wholly to the left of 'b'
+// return 0 if there is some overlap between 'a' and 'b'
+// return 1 if 'a is wholly to the right of 'b'
+func (a chunkMapping) cmpRange(b chunkMapping) int {
+	switch {
+	case a.LAddr.Add(a.Size) <= b.LAddr:
+		// 'a' is wholly to the left of 'b'.
+		return -1
+	case b.LAddr.Add(b.Size) <= a.LAddr:
+		// 'a' is wholly to the right of 'b'.
+		return 1
+	default:
+		// There is some overlap.
+		return 0
+	}
+}
+
+func (a chunkMapping) union(rest ...chunkMapping) (chunkMapping, error) {
+	// sanity check
+	for _, chunk := range rest {
+		if a.cmpRange(chunk) != 0 {
+			return chunkMapping{}, fmt.Errorf("chunks don't overlap")
+		}
+	}
+	chunks := append([]chunkMapping{a}, rest...)
+	// figure out the logical range (.LAddr and .Size)
+	beg := chunks[0].LAddr
+	end := chunks[0].LAddr.Add(chunks[0].Size)
+	for _, chunk := range chunks {
+		beg = util.Min(beg, chunk.LAddr)
+		end = util.Max(end, chunk.LAddr.Add(chunk.Size))
+	}
+	ret := chunkMapping{
+		LAddr: beg,
+		Size:  end.Sub(beg),
+	}
+	for _, chunk := range chunks {
+		if chunk.SizeLocked {
+			ret.SizeLocked = true
+			if ret.Size != chunk.Size {
+				return chunkMapping{}, fmt.Errorf("member chunk has locked size=%v, but union would have size=%v",
+					chunk.Size, ret.Size)
+			}
+		}
+	}
+	// figure out the physical stripes (.PAddrs)
+	paddrs := make(map[QualifiedPhysicalAddr]struct{})
+	for _, chunk := range chunks {
+		offsetWithinRet := chunk.LAddr.Sub(ret.LAddr)
+		for _, stripe := range chunk.PAddrs {
+			paddrs[QualifiedPhysicalAddr{
+				Dev:  stripe.Dev,
+				Addr: stripe.Addr.Add(-offsetWithinRet),
+			}] = struct{}{}
+		}
+	}
+	ret.PAddrs = util.MapKeys(paddrs)
+	sort.Slice(ret.PAddrs, func(i, j int) bool {
+		return ret.PAddrs[i].Cmp(ret.PAddrs[j]) < 0
+	})
+	// figure out the flags (.Flags)
+	for _, chunk := range chunks {
+		if chunk.Flags == nil {
+			continue
+		}
+		if ret.Flags == nil {
+			val := *chunk.Flags
+			ret.Flags = &val
+		}
+		if *ret.Flags != *chunk.Flags {
+			return ret, fmt.Errorf("mismatch flags: %v != %v", *ret.Flags, *chunk.Flags)
+		}
+	}
+	// done
+	return ret, nil
+}
diff --git a/lib/btrfs/btrfsvol/devext.go b/lib/btrfs/btrfsvol/devext.go
new file mode 100644
index 0000000..43c6255
--- /dev/null
+++ b/lib/btrfs/btrfsvol/devext.go
@@ -0,0 +1,89 @@
+package btrfsvol
+
+import (
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+// physical => logical
+type devextMapping struct {
+	PAddr      PhysicalAddr
+	LAddr      LogicalAddr
+	Size       AddrDelta
+	SizeLocked bool
+	Flags      *BlockGroupFlags
+}
+
+// return -1 if 'a' is wholly to the left of 'b'
+// return 0 if there is some overlap between 'a' and 'b'
+// return 1 if 'a is wholly to the right of 'b'
+func (a devextMapping) cmpRange(b devextMapping) int {
+	switch {
+	case a.PAddr.Add(a.Size) <= b.PAddr:
+		// 'a' is wholly to the left of 'b'.
+		return -1
+	case b.PAddr.Add(b.Size) <= a.PAddr:
+		// 'a' is wholly to the right of 'b'.
+		return 1
+	default:
+		// There is some overlap.
+		return 0
+	}
+}
+
+func (a devextMapping) union(rest ...devextMapping) (devextMapping, error) {
+	// sanity check
+	for _, ext := range rest {
+		if a.cmpRange(ext) != 0 {
+			return devextMapping{}, fmt.Errorf("devexts don't overlap")
+		}
+	}
+	exts := append([]devextMapping{a}, rest...)
+	// figure out the physical range (.PAddr and .Size)
+	beg := exts[0].PAddr
+	end := beg.Add(exts[0].Size)
+	for _, ext := range exts {
+		beg = util.Min(beg, ext.PAddr)
+		end = util.Max(end, ext.PAddr.Add(ext.Size))
+	}
+	ret := devextMapping{
+		PAddr: beg,
+		Size:  end.Sub(beg),
+	}
+	for _, ext := range exts {
+		if ext.SizeLocked {
+			ret.SizeLocked = true
+			if ret.Size != ext.Size {
+				return devextMapping{}, fmt.Errorf("member devext has locked size=%v, but union would have size=%v",
+					ext.Size, ret.Size)
+			}
+		}
+	}
+	// figure out the logical range (.LAddr)
+	first := true
+	for _, ext := range exts {
+		offsetWithinRet := ext.PAddr.Sub(ret.PAddr)
+		laddr := ext.LAddr.Add(-offsetWithinRet)
+		if first {
+			ret.LAddr = laddr
+		} else if laddr != ret.LAddr {
+			return ret, fmt.Errorf("devexts don't agree on laddr: %v != %v", ret.LAddr, laddr)
+		}
+	}
+	// figure out the flags (.Flags)
+	for _, ext := range exts {
+		if ext.Flags == nil {
+			continue
+		}
+		if ret.Flags == nil {
+			val := *ext.Flags
+			ret.Flags = &val
+		}
+		if *ret.Flags != *ext.Flags {
+			return ret, fmt.Errorf("mismatch flags: %v != %v", *ret.Flags, *ext.Flags)
+		}
+	}
+	// done
+	return ret, nil
+}
diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go
new file mode 100644
index 0000000..3b9ccf6
--- /dev/null
+++ b/lib/btrfs/btrfsvol/lvm.go
@@ -0,0 +1,355 @@
+package btrfsvol
+
+import (
+	"bytes"
+	"fmt"
+	"os"
+	"reflect"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/rbtree"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type LogicalVolume[PhysicalVolume util.File[PhysicalAddr]] struct {
+	name string
+
+	id2pv map[DeviceID]PhysicalVolume
+
+	logical2physical *rbtree.Tree[LogicalAddr, chunkMapping]
+	physical2logical map[DeviceID]*rbtree.Tree[PhysicalAddr, devextMapping]
+}
+
+var _ util.File[LogicalAddr] = (*LogicalVolume[util.File[PhysicalAddr]])(nil)
+
+func (lv *LogicalVolume[PhysicalVolume]) init() {
+	if lv.id2pv == nil {
+		lv.id2pv = make(map[DeviceID]PhysicalVolume)
+	}
+	if lv.logical2physical == nil {
+		lv.logical2physical = &rbtree.Tree[LogicalAddr, chunkMapping]{
+			KeyFn: func(chunk chunkMapping) LogicalAddr {
+				return chunk.LAddr
+			},
+		}
+	}
+	if lv.physical2logical == nil {
+		lv.physical2logical = make(map[DeviceID]*rbtree.Tree[PhysicalAddr, devextMapping], len(lv.id2pv))
+	}
+	for devid := range lv.id2pv {
+		if _, ok := lv.physical2logical[devid]; !ok {
+			lv.physical2logical[devid] = &rbtree.Tree[PhysicalAddr, devextMapping]{
+				KeyFn: func(ext devextMapping) PhysicalAddr {
+					return ext.PAddr
+				},
+			}
+		}
+	}
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) SetName(name string) {
+	lv.name = name
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) Name() string {
+	return lv.name
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) Size() (LogicalAddr, error) {
+	lv.init()
+	lastChunk := lv.logical2physical.Max()
+	if lastChunk == nil {
+		return 0, nil
+	}
+	return lastChunk.Value.LAddr.Add(lastChunk.Value.Size), nil
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) AddPhysicalVolume(id DeviceID, dev PhysicalVolume) error {
+	lv.init()
+	if other, exists := lv.id2pv[id]; exists {
+		return fmt.Errorf("(%p).AddPhysicalVolume: cannot add physical volume %q: already have physical volume %q with id=%v",
+			lv, dev.Name(), other.Name(), id)
+	}
+	lv.id2pv[id] = dev
+	lv.physical2logical[id] = &rbtree.Tree[PhysicalAddr, devextMapping]{
+		KeyFn: func(ext devextMapping) PhysicalAddr {
+			return ext.PAddr
+		},
+	}
+	return nil
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) PhysicalVolumes() map[DeviceID]PhysicalVolume {
+	dup := make(map[DeviceID]PhysicalVolume, len(lv.id2pv))
+	for k, v := range lv.id2pv {
+		dup[k] = v
+	}
+	return dup
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) ClearMappings() {
+	lv.logical2physical = nil
+	lv.physical2logical = nil
+}
+
+type Mapping struct {
+	LAddr      LogicalAddr
+	PAddr      QualifiedPhysicalAddr
+	Size       AddrDelta
+	SizeLocked bool
+	Flags      *BlockGroupFlags
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) AddMapping(m Mapping) error {
+	lv.init()
+	// sanity check
+	if _, haveDev := lv.id2pv[m.PAddr.Dev]; !haveDev {
+		return fmt.Errorf("(%p).AddMapping: do not have a physical volume with id=%v",
+			lv, m.PAddr.Dev)
+	}
+
+	// logical2physical
+	newChunk := chunkMapping{
+		LAddr:      m.LAddr,
+		PAddrs:     []QualifiedPhysicalAddr{m.PAddr},
+		Size:       m.Size,
+		SizeLocked: m.SizeLocked,
+		Flags:      m.Flags,
+	}
+	logicalOverlaps := lv.logical2physical.SearchRange(newChunk.cmpRange)
+	var err error
+	newChunk, err = newChunk.union(logicalOverlaps...)
+	if err != nil {
+		return fmt.Errorf("(%p).AddMapping: %w", lv, err)
+	}
+
+	// physical2logical
+	newExt := devextMapping{
+		PAddr:      m.PAddr.Addr,
+		LAddr:      m.LAddr,
+		Size:       m.Size,
+		SizeLocked: m.SizeLocked,
+		Flags:      m.Flags,
+	}
+	physicalOverlaps := lv.physical2logical[m.PAddr.Dev].SearchRange(newExt.cmpRange)
+	newExt, err = newExt.union(physicalOverlaps...)
+	if err != nil {
+		return fmt.Errorf("(%p).AddMapping: %w", lv, err)
+	}
+
+	// optimize
+	if len(logicalOverlaps) == 1 && reflect.DeepEqual(newChunk, logicalOverlaps[0]) &&
+		len(physicalOverlaps) == 1 && reflect.DeepEqual(newExt, physicalOverlaps[0]) {
+		return nil
+	}
+
+	// logical2physical
+	for _, chunk := range logicalOverlaps {
+		lv.logical2physical.Delete(chunk.LAddr)
+	}
+	lv.logical2physical.Insert(newChunk)
+
+	// physical2logical
+	for _, ext := range physicalOverlaps {
+		lv.physical2logical[m.PAddr.Dev].Delete(ext.PAddr)
+	}
+	lv.physical2logical[m.PAddr.Dev].Insert(newExt)
+
+	// sanity check
+	//
+	// This is in-theory unnescessary, but that assumes that I
+	// made no mistakes in my algorithm above.
+	if os.Getenv("PARANOID") != "" {
+		if err := lv.fsck(); err != nil {
+			return err
+		}
+	}
+
+	// done
+	return nil
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) fsck() error {
+	physical2logical := make(map[DeviceID]*rbtree.Tree[PhysicalAddr, devextMapping])
+	if err := lv.logical2physical.Walk(func(node *rbtree.Node[chunkMapping]) error {
+		chunk := node.Value
+		for _, stripe := range chunk.PAddrs {
+			if _, devOK := lv.id2pv[stripe.Dev]; !devOK {
+				return fmt.Errorf("(%p).fsck: chunk references physical volume %v which does not exist",
+					lv, stripe.Dev)
+			}
+			if _, exists := physical2logical[stripe.Dev]; !exists {
+				physical2logical[stripe.Dev] = &rbtree.Tree[PhysicalAddr, devextMapping]{
+					KeyFn: func(ext devextMapping) PhysicalAddr {
+						return ext.PAddr
+					},
+				}
+			}
+			physical2logical[stripe.Dev].Insert(devextMapping{
+				PAddr: stripe.Addr,
+				LAddr: chunk.LAddr,
+				Size:  chunk.Size,
+				Flags: chunk.Flags,
+			})
+		}
+		return nil
+	}); err != nil {
+		return err
+	}
+
+	if len(lv.physical2logical) != len(physical2logical) {
+		return fmt.Errorf("(%p).fsck: skew between chunk tree and devext tree",
+			lv)
+	}
+	for devid := range lv.physical2logical {
+		if !lv.physical2logical[devid].Equal(physical2logical[devid]) {
+			return fmt.Errorf("(%p).fsck: skew between chunk tree and devext tree",
+				lv)
+		}
+	}
+
+	return nil
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping {
+	var ret []Mapping
+	_ = lv.logical2physical.Walk(func(node *rbtree.Node[chunkMapping]) error {
+		chunk := node.Value
+		var flags *BlockGroupFlags
+		if chunk.Flags != nil {
+			val := *chunk.Flags
+			flags = &val
+		}
+		for _, slice := range chunk.PAddrs {
+			ret = append(ret, Mapping{
+				LAddr: chunk.LAddr,
+				PAddr: slice,
+				Size:  chunk.Size,
+				Flags: flags,
+			})
+		}
+		return nil
+	})
+	return ret
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs map[QualifiedPhysicalAddr]struct{}, maxlen AddrDelta) {
+	node := lv.logical2physical.Search(func(chunk chunkMapping) int {
+		return chunkMapping{LAddr: laddr, Size: 1}.cmpRange(chunk)
+	})
+	if node == nil {
+		return nil, 0
+	}
+
+	chunk := node.Value
+
+	offsetWithinChunk := laddr.Sub(chunk.LAddr)
+	paddrs = make(map[QualifiedPhysicalAddr]struct{})
+	maxlen = chunk.Size - offsetWithinChunk
+	for _, stripe := range chunk.PAddrs {
+		paddrs[QualifiedPhysicalAddr{
+			Dev:  stripe.Dev,
+			Addr: stripe.Addr.Add(offsetWithinChunk),
+		}] = struct{}{}
+	}
+
+	return paddrs, maxlen
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) ResolveAny(laddr LogicalAddr, size AddrDelta) (LogicalAddr, QualifiedPhysicalAddr) {
+	node := lv.logical2physical.Search(func(chunk chunkMapping) int {
+		return chunkMapping{LAddr: laddr, Size: size}.cmpRange(chunk)
+	})
+	if node == nil {
+		return -1, QualifiedPhysicalAddr{0, -1}
+	}
+	return node.Value.LAddr, node.Value.PAddrs[0]
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) UnResolve(paddr QualifiedPhysicalAddr) LogicalAddr {
+	node := lv.physical2logical[paddr.Dev].Search(func(ext devextMapping) int {
+		return devextMapping{PAddr: paddr.Addr, Size: 1}.cmpRange(ext)
+	})
+	if node == nil {
+		return -1
+	}
+
+	ext := node.Value
+
+	offsetWithinExt := paddr.Addr.Sub(ext.PAddr)
+	return ext.LAddr.Add(offsetWithinExt)
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) ReadAt(dat []byte, laddr LogicalAddr) (int, error) {
+	done := 0
+	for done < len(dat) {
+		n, err := lv.maybeShortReadAt(dat[done:], laddr+LogicalAddr(done))
+		done += n
+		if err != nil {
+			return done, err
+		}
+	}
+	return done, nil
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) maybeShortReadAt(dat []byte, laddr LogicalAddr) (int, error) {
+	paddrs, maxlen := lv.Resolve(laddr)
+	if len(paddrs) == 0 {
+		return 0, fmt.Errorf("read: could not map logical address %v", laddr)
+	}
+	if AddrDelta(len(dat)) > maxlen {
+		dat = dat[:maxlen]
+	}
+
+	buf := make([]byte, len(dat))
+	first := true
+	for paddr := range paddrs {
+		dev, ok := lv.id2pv[paddr.Dev]
+		if !ok {
+			return 0, fmt.Errorf("device=%v does not exist", paddr.Dev)
+		}
+		if _, err := dev.ReadAt(buf, paddr.Addr); err != nil {
+			return 0, fmt.Errorf("read device=%v paddr=%v: %w", paddr.Dev, paddr.Addr, err)
+		}
+		if first {
+			copy(dat, buf)
+		} else {
+			if !bytes.Equal(dat, buf) {
+				return 0, fmt.Errorf("inconsistent stripes at laddr=%v len=%v", laddr, len(dat))
+			}
+		}
+	}
+	return len(dat), nil
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) WriteAt(dat []byte, laddr LogicalAddr) (int, error) {
+	done := 0
+	for done < len(dat) {
+		n, err := lv.maybeShortWriteAt(dat[done:], laddr+LogicalAddr(done))
+		done += n
+		if err != nil {
+			return done, err
+		}
+	}
+	return done, nil
+}
+
+func (lv *LogicalVolume[PhysicalVolume]) maybeShortWriteAt(dat []byte, laddr LogicalAddr) (int, error) {
+	paddrs, maxlen := lv.Resolve(laddr)
+	if len(paddrs) == 0 {
+		return 0, fmt.Errorf("write: could not map logical address %v", laddr)
+	}
+	if AddrDelta(len(dat)) > maxlen {
+		dat = dat[:maxlen]
+	}
+
+	for paddr := range paddrs {
+		dev, ok := lv.id2pv[paddr.Dev]
+		if !ok {
+			return 0, fmt.Errorf("device=%v does not exist", paddr.Dev)
+		}
+		if _, err := dev.WriteAt(dat, paddr.Addr); err != nil {
+			return 0, fmt.Errorf("write device=%v paddr=%v: %w", paddr.Dev, paddr.Addr, err)
+		}
+	}
+	return len(dat), nil
+}
diff --git a/lib/btrfs/internal/itemtype.go b/lib/btrfs/internal/itemtype.go
new file mode 100644
index 0000000..60731aa
--- /dev/null
+++ b/lib/btrfs/internal/itemtype.go
@@ -0,0 +1,77 @@
+// Code generated by Make.  DO NOT EDIT.
+
+package internal
+
+import "fmt"
+
+type ItemType uint8
+
+const (
+	BLOCK_GROUP_ITEM_KEY     = ItemType(192)
+	CHUNK_ITEM_KEY           = ItemType(228)
+	DEV_EXTENT_KEY           = ItemType(204)
+	DEV_ITEM_KEY             = ItemType(216)
+	DIR_INDEX_KEY            = ItemType(96)
+	DIR_ITEM_KEY             = ItemType(84)
+	EXTENT_CSUM_KEY          = ItemType(128)
+	EXTENT_DATA_KEY          = ItemType(108)
+	EXTENT_DATA_REF_KEY      = ItemType(178)
+	EXTENT_ITEM_KEY          = ItemType(168)
+	FREE_SPACE_BITMAP_KEY    = ItemType(200)
+	FREE_SPACE_EXTENT_KEY    = ItemType(199)
+	FREE_SPACE_INFO_KEY      = ItemType(198)
+	INODE_ITEM_KEY           = ItemType(1)
+	INODE_REF_KEY            = ItemType(12)
+	METADATA_ITEM_KEY        = ItemType(169)
+	ORPHAN_ITEM_KEY          = ItemType(48)
+	PERSISTENT_ITEM_KEY      = ItemType(249)
+	QGROUP_RELATION_KEY      = ItemType(246)
+	ROOT_BACKREF_KEY         = ItemType(144)
+	ROOT_ITEM_KEY            = ItemType(132)
+	ROOT_REF_KEY             = ItemType(156)
+	SHARED_BLOCK_REF_KEY     = ItemType(182)
+	SHARED_DATA_REF_KEY      = ItemType(184)
+	TREE_BLOCK_REF_KEY       = ItemType(176)
+	UNTYPED_KEY              = ItemType(0)
+	UUID_RECEIVED_SUBVOL_KEY = ItemType(252)
+	UUID_SUBVOL_KEY          = ItemType(251)
+	XATTR_ITEM_KEY           = ItemType(24)
+)
+
+func (t ItemType) String() string {
+	names := map[ItemType]string{
+		BLOCK_GROUP_ITEM_KEY:     "BLOCK_GROUP_ITEM",
+		CHUNK_ITEM_KEY:           "CHUNK_ITEM",
+		DEV_EXTENT_KEY:           "DEV_EXTENT",
+		DEV_ITEM_KEY:             "DEV_ITEM",
+		DIR_INDEX_KEY:            "DIR_INDEX",
+		DIR_ITEM_KEY:             "DIR_ITEM",
+		EXTENT_CSUM_KEY:          "EXTENT_CSUM",
+		EXTENT_DATA_KEY:          "EXTENT_DATA",
+		EXTENT_DATA_REF_KEY:      "EXTENT_DATA_REF",
+		EXTENT_ITEM_KEY:          "EXTENT_ITEM",
+		FREE_SPACE_BITMAP_KEY:    "FREE_SPACE_BITMAP",
+		FREE_SPACE_EXTENT_KEY:    "FREE_SPACE_EXTENT",
+		FREE_SPACE_INFO_KEY:      "FREE_SPACE_INFO",
+		INODE_ITEM_KEY:           "INODE_ITEM",
+		INODE_REF_KEY:            "INODE_REF",
+		METADATA_ITEM_KEY:        "METADATA_ITEM",
+		ORPHAN_ITEM_KEY:          "ORPHAN_ITEM",
+		PERSISTENT_ITEM_KEY:      "PERSISTENT_ITEM",
+		QGROUP_RELATION_KEY:      "QGROUP_RELATION",
+		ROOT_BACKREF_KEY:         "ROOT_BACKREF",
+		ROOT_ITEM_KEY:            "ROOT_ITEM",
+		ROOT_REF_KEY:             "ROOT_REF",
+		SHARED_BLOCK_REF_KEY:     "SHARED_BLOCK_REF",
+		SHARED_DATA_REF_KEY:      "SHARED_DATA_REF",
+		TREE_BLOCK_REF_KEY:       "TREE_BLOCK_REF",
+		UNTYPED_KEY:              "UNTYPED",
+		UUID_RECEIVED_SUBVOL_KEY: "UUID_KEY_RECEIVED_SUBVOL",
+		UUID_SUBVOL_KEY:          "UUID_KEY_SUBVOL",
+		XATTR_ITEM_KEY:           "XATTR_ITEM",
+	}
+	if name, ok := names[t]; ok {
+		return name
+	}
+	return fmt.Sprintf("%d", t)
+}
diff --git a/lib/btrfs/internal/misc.go b/lib/btrfs/internal/misc.go
new file mode 100644
index 0000000..fba1d38
--- /dev/null
+++ b/lib/btrfs/internal/misc.go
@@ -0,0 +1,37 @@
+package internal
+
+import (
+	"time"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type Generation uint64
+
+type Key struct {
+	ObjectID      ObjID    `bin:"off=0x0, siz=0x8"` // Each tree has its own set of Object IDs.
+	ItemType      ItemType `bin:"off=0x8, siz=0x1"`
+	Offset        uint64   `bin:"off=0x9, siz=0x8"` // The meaning depends on the item type.
+	binstruct.End `bin:"off=0x11"`
+}
+
+func (a Key) Cmp(b Key) int {
+	if d := util.CmpUint(a.ObjectID, b.ObjectID); d != 0 {
+		return d
+	}
+	if d := util.CmpUint(a.ItemType, b.ItemType); d != 0 {
+		return d
+	}
+	return util.CmpUint(a.Offset, b.Offset)
+}
+
+type Time struct {
+	Sec           int64  `bin:"off=0x0, siz=0x8"` // Number of seconds since 1970-01-01T00:00:00Z.
+	NSec          uint32 `bin:"off=0x8, siz=0x4"` // Number of nanoseconds since the beginning of the second.
+	binstruct.End `bin:"off=0xc"`
+}
+
+func (t Time) ToStd() time.Time {
+	return time.Unix(t.Sec, int64(t.NSec))
+}
diff --git a/lib/btrfs/internal/objid.go b/lib/btrfs/internal/objid.go
new file mode 100644
index 0000000..8c9c002
--- /dev/null
+++ b/lib/btrfs/internal/objid.go
@@ -0,0 +1,144 @@
+package internal
+
+import (
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type ObjID uint64
+
+const (
+	// The IDs of the various trees
+	ROOT_TREE_OBJECTID        = ObjID(1) // holds pointers to all of the tree roots
+	EXTENT_TREE_OBJECTID      = ObjID(2) // stores information about which extents are in use, and reference counts
+	CHUNK_TREE_OBJECTID       = ObjID(3) // chunk tree stores translations from logical -> physical block numbering
+	DEV_TREE_OBJECTID         = ObjID(4) // stores info about which areas of a given device are in use; one per device
+	FS_TREE_OBJECTID          = ObjID(5) // one per subvolume, storing files and directories
+	ROOT_TREE_DIR_OBJECTID    = ObjID(6) // directory objectid inside the root tree
+	CSUM_TREE_OBJECTID        = ObjID(7) // holds checksums of all the data extents
+	QUOTA_TREE_OBJECTID       = ObjID(8)
+	UUID_TREE_OBJECTID        = ObjID(9)  // for storing items that use the UUID_*_KEY
+	FREE_SPACE_TREE_OBJECTID  = ObjID(10) // tracks free space in block groups.
+	BLOCK_GROUP_TREE_OBJECTID = ObjID(11) // hold the block group items.
+
+	// Objects in the DEV_TREE
+	DEV_STATS_OBJECTID = ObjID(0) // device stats in the device tree
+
+	// ???
+	BALANCE_OBJECTID         = ObjID(util.MaxUint64pp - 4) // for storing balance parameters in the root tree
+	ORPHAN_OBJECTID          = ObjID(util.MaxUint64pp - 5) // orphan objectid for tracking unlinked/truncated files
+	TREE_LOG_OBJECTID        = ObjID(util.MaxUint64pp - 6) // does write ahead logging to speed up fsyncs
+	TREE_LOG_FIXUP_OBJECTID  = ObjID(util.MaxUint64pp - 7)
+	TREE_RELOC_OBJECTID      = ObjID(util.MaxUint64pp - 8) // space balancing
+	DATA_RELOC_TREE_OBJECTID = ObjID(util.MaxUint64pp - 9)
+	EXTENT_CSUM_OBJECTID     = ObjID(util.MaxUint64pp - 10) // extent checksums all have this objectid
+	FREE_SPACE_OBJECTID      = ObjID(util.MaxUint64pp - 11) // For storing free space cache
+	FREE_INO_OBJECTID        = ObjID(util.MaxUint64pp - 12) // stores the inode number for the free-ino cache
+
+	MULTIPLE_OBJECTIDS = ObjID(util.MaxUint64pp - 255) // dummy objectid represents multiple objectids
+
+	// All files have objectids in this range.
+	FIRST_FREE_OBJECTID = ObjID(256)
+	LAST_FREE_OBJECTID  = ObjID(util.MaxUint64pp - 256)
+
+	FIRST_CHUNK_TREE_OBJECTID = ObjID(256)
+
+	// Objects in the CHUNK_TREE
+	DEV_ITEMS_OBJECTID = ObjID(1)
+
+	// ???
+	EMPTY_SUBVOL_DIR_OBJECTID = ObjID(2)
+)
+
+func (id ObjID) Format(typ ItemType) string {
+	switch typ {
+	case PERSISTENT_ITEM_KEY:
+		names := map[ObjID]string{
+			DEV_STATS_OBJECTID: "DEV_STATS",
+		}
+		if name, ok := names[id]; ok {
+			return name
+		}
+		return fmt.Sprintf("%d", int64(id))
+	case DEV_EXTENT_KEY:
+		return fmt.Sprintf("%d", int64(id))
+	case QGROUP_RELATION_KEY:
+		return fmt.Sprintf("%d/%d",
+			uint64(id)>>48,
+			uint64(id)&((1<<48)-1))
+	case UUID_SUBVOL_KEY, UUID_RECEIVED_SUBVOL_KEY:
+		return fmt.Sprintf("%#016x", uint64(id))
+	case DEV_ITEM_KEY:
+		names := map[ObjID]string{
+			BALANCE_OBJECTID:         "BALANCE",
+			ORPHAN_OBJECTID:          "ORPHAN",
+			TREE_LOG_OBJECTID:        "TREE_LOG",
+			TREE_LOG_FIXUP_OBJECTID:  "TREE_LOG_FIXUP",
+			TREE_RELOC_OBJECTID:      "TREE_RELOC",
+			DATA_RELOC_TREE_OBJECTID: "DATA_RELOC_TREE",
+			EXTENT_CSUM_OBJECTID:     "EXTENT_CSUM",
+			FREE_SPACE_OBJECTID:      "FREE_SPACE",
+			FREE_INO_OBJECTID:        "FREE_INO",
+			MULTIPLE_OBJECTIDS:       "MULTIPLE",
+
+			DEV_ITEMS_OBJECTID: "DEV_ITEMS",
+		}
+		if name, ok := names[id]; ok {
+			return name
+		}
+		return fmt.Sprintf("%d", int64(id))
+	case CHUNK_ITEM_KEY:
+		names := map[ObjID]string{
+			BALANCE_OBJECTID:         "BALANCE",
+			ORPHAN_OBJECTID:          "ORPHAN",
+			TREE_LOG_OBJECTID:        "TREE_LOG",
+			TREE_LOG_FIXUP_OBJECTID:  "TREE_LOG_FIXUP",
+			TREE_RELOC_OBJECTID:      "TREE_RELOC",
+			DATA_RELOC_TREE_OBJECTID: "DATA_RELOC_TREE",
+			EXTENT_CSUM_OBJECTID:     "EXTENT_CSUM",
+			FREE_SPACE_OBJECTID:      "FREE_SPACE",
+			FREE_INO_OBJECTID:        "FREE_INO",
+			MULTIPLE_OBJECTIDS:       "MULTIPLE",
+
+			FIRST_CHUNK_TREE_OBJECTID: "FIRST_CHUNK_TREE",
+		}
+		if name, ok := names[id]; ok {
+			return name
+		}
+		return fmt.Sprintf("%d", int64(id))
+	default:
+		names := map[ObjID]string{
+			BALANCE_OBJECTID:         "BALANCE",
+			ORPHAN_OBJECTID:          "ORPHAN",
+			TREE_LOG_OBJECTID:        "TREE_LOG",
+			TREE_LOG_FIXUP_OBJECTID:  "TREE_LOG_FIXUP",
+			TREE_RELOC_OBJECTID:      "TREE_RELOC",
+			DATA_RELOC_TREE_OBJECTID: "DATA_RELOC_TREE",
+			EXTENT_CSUM_OBJECTID:     "EXTENT_CSUM",
+			FREE_SPACE_OBJECTID:      "FREE_SPACE",
+			FREE_INO_OBJECTID:        "FREE_INO",
+			MULTIPLE_OBJECTIDS:       "MULTIPLE",
+
+			ROOT_TREE_OBJECTID:        "ROOT_TREE",
+			EXTENT_TREE_OBJECTID:      "EXTENT_TREE",
+			CHUNK_TREE_OBJECTID:       "CHUNK_TREE",
+			DEV_TREE_OBJECTID:         "DEV_TREE",
+			FS_TREE_OBJECTID:          "FS_TREE",
+			ROOT_TREE_DIR_OBJECTID:    "ROOT_TREE_DIR",
+			CSUM_TREE_OBJECTID:        "CSUM_TREE",
+			QUOTA_TREE_OBJECTID:       "QUOTA_TREE",
+			UUID_TREE_OBJECTID:        "UUID_TREE",
+			FREE_SPACE_TREE_OBJECTID:  "FREE_SPACE_TREE",
+			BLOCK_GROUP_TREE_OBJECTID: "BLOCK_GROUP_TREE",
+		}
+		if name, ok := names[id]; ok {
+			return name
+		}
+		return fmt.Sprintf("%d", int64(id))
+	}
+}
+
+func (id ObjID) String() string {
+	return id.Format(UNTYPED_KEY)
+}
diff --git a/lib/btrfs/io1_pv.go b/lib/btrfs/io1_pv.go
new file mode 100644
index 0000000..cababaf
--- /dev/null
+++ b/lib/btrfs/io1_pv.go
@@ -0,0 +1,96 @@
+package btrfs
+
+import (
+	"fmt"
+	"os"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type Device struct {
+	*os.File
+
+	cacheSuperblocks []*util.Ref[btrfsvol.PhysicalAddr, Superblock]
+	cacheSuperblock  *util.Ref[btrfsvol.PhysicalAddr, Superblock]
+}
+
+var _ util.File[btrfsvol.PhysicalAddr] = (*Device)(nil)
+
+func (dev Device) Size() (btrfsvol.PhysicalAddr, error) {
+	fi, err := dev.Stat()
+	if err != nil {
+		return 0, err
+	}
+	return btrfsvol.PhysicalAddr(fi.Size()), nil
+}
+
+func (dev *Device) ReadAt(dat []byte, paddr btrfsvol.PhysicalAddr) (int, error) {
+	return dev.File.ReadAt(dat, int64(paddr))
+}
+
+func (dev *Device) WriteAt(dat []byte, paddr btrfsvol.PhysicalAddr) (int, error) {
+	return dev.File.WriteAt(dat, int64(paddr))
+}
+
+var SuperblockAddrs = []btrfsvol.PhysicalAddr{
+	0x00_0001_0000, // 64KiB
+	0x00_0400_0000, // 64MiB
+	0x40_0000_0000, // 256GiB
+}
+
+func (dev *Device) Superblocks() ([]*util.Ref[btrfsvol.PhysicalAddr, Superblock], error) {
+	if dev.cacheSuperblocks != nil {
+		return dev.cacheSuperblocks, nil
+	}
+	superblockSize := btrfsvol.PhysicalAddr(binstruct.StaticSize(Superblock{}))
+
+	sz, err := dev.Size()
+	if err != nil {
+		return nil, err
+	}
+
+	var ret []*util.Ref[btrfsvol.PhysicalAddr, Superblock]
+	for i, addr := range SuperblockAddrs {
+		if addr+superblockSize <= sz {
+			superblock := &util.Ref[btrfsvol.PhysicalAddr, Superblock]{
+				File: dev,
+				Addr: addr,
+			}
+			if err := superblock.Read(); err != nil {
+				return nil, fmt.Errorf("superblock %v: %w", i, err)
+			}
+			ret = append(ret, superblock)
+		}
+	}
+	if len(ret) == 0 {
+		return nil, fmt.Errorf("no superblocks")
+	}
+	dev.cacheSuperblocks = ret
+	return ret, nil
+}
+
+func (dev *Device) Superblock() (*util.Ref[btrfsvol.PhysicalAddr, Superblock], error) {
+	if dev.cacheSuperblock != nil {
+		return dev.cacheSuperblock, nil
+	}
+	sbs, err := dev.Superblocks()
+	if err != nil {
+		return nil, err
+	}
+
+	for i, sb := range sbs {
+		if err := sb.Data.ValidateChecksum(); err != nil {
+			return nil, fmt.Errorf("superblock %v: %w", i, err)
+		}
+		if i > 0 {
+			if !sb.Data.Equal(sbs[0].Data) {
+				return nil, fmt.Errorf("superblock %v and superblock %v disagree", 0, i)
+			}
+		}
+	}
+
+	dev.cacheSuperblock = sbs[0]
+	return sbs[0], nil
+}
diff --git a/lib/btrfs/io2_lv.go b/lib/btrfs/io2_lv.go
new file mode 100644
index 0000000..c6ef9e0
--- /dev/null
+++ b/lib/btrfs/io2_lv.go
@@ -0,0 +1,187 @@
+package btrfs
+
+import (
+	"fmt"
+	"io"
+
+	"github.com/datawire/dlib/derror"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type FS struct {
+	// You should probably not access .LV directly, except when
+	// implementing special things like fsck.
+	LV btrfsvol.LogicalVolume[*Device]
+
+	cacheSuperblocks []*util.Ref[btrfsvol.PhysicalAddr, Superblock]
+	cacheSuperblock  *util.Ref[btrfsvol.PhysicalAddr, Superblock]
+}
+
+var _ util.File[btrfsvol.LogicalAddr] = (*FS)(nil)
+
+func (fs *FS) AddDevice(dev *Device) error {
+	sb, err := dev.Superblock()
+	if err != nil {
+		return err
+	}
+	if err := fs.LV.AddPhysicalVolume(sb.Data.DevItem.DevID, dev); err != nil {
+		return err
+	}
+	fs.cacheSuperblocks = nil
+	fs.cacheSuperblock = nil
+	if err := fs.initDev(sb); err != nil {
+		return err
+	}
+	return nil
+}
+
+func (fs *FS) Name() string {
+	if name := fs.LV.Name(); name != "" {
+		return name
+	}
+	sb, err := fs.Superblock()
+	if err != nil {
+		return fmt.Sprintf("fs_uuid=%v", "(unreadable)")
+	}
+	name := fmt.Sprintf("fs_uuid=%v", sb.Data.FSUUID)
+	fs.LV.SetName(name)
+	return name
+}
+
+func (fs *FS) Size() (btrfsvol.LogicalAddr, error) {
+	return fs.LV.Size()
+}
+
+func (fs *FS) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
+	return fs.LV.ReadAt(p, off)
+}
+func (fs *FS) WriteAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
+	return fs.LV.WriteAt(p, off)
+}
+
+func (fs *FS) Resolve(laddr btrfsvol.LogicalAddr) (paddrs map[btrfsvol.QualifiedPhysicalAddr]struct{}, maxlen btrfsvol.AddrDelta) {
+	return fs.LV.Resolve(laddr)
+}
+
+func (fs *FS) Superblocks() ([]*util.Ref[btrfsvol.PhysicalAddr, Superblock], error) {
+	if fs.cacheSuperblocks != nil {
+		return fs.cacheSuperblocks, nil
+	}
+	var ret []*util.Ref[btrfsvol.PhysicalAddr, Superblock]
+	devs := fs.LV.PhysicalVolumes()
+	if len(devs) == 0 {
+		return nil, fmt.Errorf("no devices")
+	}
+	for _, dev := range devs {
+		sbs, err := dev.Superblocks()
+		if err != nil {
+			return nil, fmt.Errorf("file %q: %w", dev.Name(), err)
+		}
+		ret = append(ret, sbs...)
+	}
+	fs.cacheSuperblocks = ret
+	return ret, nil
+}
+
+func (fs *FS) Superblock() (*util.Ref[btrfsvol.PhysicalAddr, Superblock], error) {
+	if fs.cacheSuperblock != nil {
+		return fs.cacheSuperblock, nil
+	}
+	sbs, err := fs.Superblocks()
+	if err != nil {
+		return nil, err
+	}
+	if len(sbs) == 0 {
+		return nil, fmt.Errorf("no superblocks")
+	}
+
+	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 nil, fmt.Errorf("file %q superblock %v: %w", sb.File.Name(), sbi, err)
+		}
+		if i > 0 {
+			// FIXME(lukeshu): This is probably wrong, but
+			// lots of my multi-device code is probably
+			// wrong.
+			if !sb.Data.Equal(sbs[0].Data) {
+				return nil, fmt.Errorf("file %q superblock %v and file %q superblock %v disagree",
+					sbs[0].File.Name(), 0,
+					sb.File.Name(), sbi)
+			}
+		}
+	}
+
+	fs.cacheSuperblock = sbs[0]
+	return sbs[0], nil
+}
+
+func (fs *FS) ReInit() error {
+	fs.LV.ClearMappings()
+	for _, dev := range fs.LV.PhysicalVolumes() {
+		sb, err := dev.Superblock()
+		if err != nil {
+			return fmt.Errorf("file %q: %w", dev.Name(), err)
+		}
+		if err := fs.initDev(sb); err != nil {
+			return fmt.Errorf("file %q: %w", dev.Name(), err)
+		}
+	}
+	return nil
+}
+
+func (fs *FS) initDev(sb *util.Ref[btrfsvol.PhysicalAddr, Superblock]) error {
+	syschunks, err := sb.Data.ParseSysChunkArray()
+	if err != nil {
+		return err
+	}
+	for _, chunk := range syschunks {
+		for _, mapping := range chunk.Chunk.Mappings(chunk.Key) {
+			if err := fs.LV.AddMapping(mapping); err != nil {
+				return err
+			}
+		}
+	}
+	if err := fs.TreeWalk(CHUNK_TREE_OBJECTID, TreeWalkHandler{
+		Item: func(_ TreePath, item Item) error {
+			if item.Head.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY {
+				return nil
+			}
+			for _, mapping := range item.Body.(btrfsitem.Chunk).Mappings(item.Head.Key) {
+				if err := fs.LV.AddMapping(mapping); err != nil {
+					return err
+				}
+			}
+			return nil
+		},
+	}); err != nil {
+		return err
+	}
+	return nil
+}
+
+func (fs *FS) Close() error {
+	var errs derror.MultiError
+	for _, dev := range fs.LV.PhysicalVolumes() {
+		if err := dev.Close(); err != nil && err == nil {
+			errs = append(errs, err)
+		}
+	}
+	if errs != nil {
+		return errs
+	}
+	return nil
+}
+
+var _ io.Closer = (*FS)(nil)
diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go
new file mode 100644
index 0000000..dbc2ac1
--- /dev/null
+++ b/lib/btrfs/io3_btree.go
@@ -0,0 +1,562 @@
+package btrfs
+
+import (
+	"errors"
+	"fmt"
+	"io"
+	iofs "io/fs"
+	"strings"
+
+	"github.com/datawire/dlib/derror"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+// - 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, given the tree structure
+//
+//   [superblock]
+//        |
+//        | <------------------------------------------ pathElem={idx:-1, addr:0x01, lvl:3}
+//        |
+//     +[0x01]-----------+
+//     | lvl=3           |
+//     +-+-+-+-+-+-+-+-+-+
+//     |1|2|3|4|5|6|7|8|9|
+//     +---+---+---+---+-+
+//                    |
+//                    | <------------------------------ pathElem={idx:8, addr:0x02, lvl:2}
+//                    |
+//                 +[0x02]-----------+
+//                 | lvl=2           |
+//                 +-+-+-+-+-+-+-+-+-+
+//                 |1|2|3|4|5|6|7|8|9|
+//                 +---+---+---+---+-+
+//                              |
+//                              | <-------------------- pathElem={idx:7, addr:0x03, lvl:1}
+//                              |
+//                           +[0x03]-----------+
+//                           | lvl=1           |
+//                           +-+-+-+-+-+-+-+-+-+
+//                           |1|2|3|4|5|6|7|8|9|
+//                           +---+---+---+---+-+
+//                                  |
+//                                  | <---------------- pathElem={idx:4, addr:0x04, lvl:0}
+//                                  |
+//                                +[0x04]-----------+
+//                                | lvl=0           |
+//                                +-+-+-+-+-+-+-+-+-+
+//                                |1|2|3|4|5|6|7|8|9|
+//                                +---+---+---+---+-+
+//                                   |
+//                                   | <--------------- pathElem={idx:5, addr:0, lvl:0}
+//                                   |
+//                                 [item]
+//
+// the path would be
+//
+//     {-1, 0x01, 3}→{8, 0x02, 2}→{7, 0x03, 1}→{4, 0x04, 0}→{2, 0, 0}
+type TreePath []TreePathElem
+
+// A TreePathElem essentially represents a KeyPointer.
+type TreePathElem struct {
+	// ItemIdx is the index of this KeyPointer in the parent Node;
+	// or -1 if this is the root and there is no KeyPointer.
+	ItemIdx int
+	// NodeAddr 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.
+	NodeAddr btrfsvol.LogicalAddr
+	// NodeLevel is the expected or actual level of the node at
+	// NodeAddr.
+	NodeLevel uint8
+}
+
+func (elem TreePathElem) writeNodeTo(w io.Writer) {
+	fmt.Fprintf(w, "node:%d@%v", elem.NodeLevel, elem.NodeAddr)
+}
+
+func (path TreePath) String() string {
+	if len(path) == 0 {
+		return "(empty-path)"
+	}
+	var ret strings.Builder
+	path[0].writeNodeTo(&ret)
+	for _, elem := range path[1:] {
+		fmt.Fprintf(&ret, "[%v]", elem.ItemIdx)
+		if elem.NodeAddr != 0 {
+			ret.WriteString("->")
+			elem.writeNodeTo(&ret)
+		}
+	}
+	return ret.String()
+}
+
+// A treeRoot is more-or-less a btrfsitem.Root, but simpler and generalized for
+type treeRoot struct {
+	TreeID     ObjID
+	RootNode   btrfsvol.LogicalAddr
+	Level      uint8
+	Generation Generation
+}
+
+func (fs *FS) lookupTree(treeID ObjID) (*treeRoot, error) {
+	sb, err := fs.Superblock()
+	if err != nil {
+		return nil, err
+	}
+	switch treeID {
+	case ROOT_TREE_OBJECTID:
+		return &treeRoot{
+			TreeID:     treeID,
+			RootNode:   sb.Data.RootTree,
+			Level:      sb.Data.RootLevel,
+			Generation: sb.Data.Generation, // XXX: same generation as LOG_TREE?
+		}, nil
+	case CHUNK_TREE_OBJECTID:
+		return &treeRoot{
+			TreeID:     treeID,
+			RootNode:   sb.Data.ChunkTree,
+			Level:      sb.Data.ChunkLevel,
+			Generation: sb.Data.ChunkRootGeneration,
+		}, nil
+	case TREE_LOG_OBJECTID:
+		return &treeRoot{
+			TreeID:     treeID,
+			RootNode:   sb.Data.LogTree,
+			Level:      sb.Data.LogLevel,
+			Generation: sb.Data.Generation, // XXX: same generation as ROOT_TREE?
+		}, nil
+	case BLOCK_GROUP_TREE_OBJECTID:
+		return &treeRoot{
+			TreeID:     treeID,
+			RootNode:   sb.Data.BlockGroupRoot,
+			Level:      sb.Data.BlockGroupRootLevel,
+			Generation: sb.Data.BlockGroupRootGeneration,
+		}, nil
+	default:
+		rootItem, err := fs.TreeSearch(ROOT_TREE_OBJECTID, func(key Key) int {
+			if key.ObjectID == treeID && key.ItemType == btrfsitem.ROOT_ITEM_KEY {
+				return 0
+			}
+			return 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
+	}
+}
+
+type TreeWalkHandler struct {
+	// Callbacks for entire nodes
+	PreNode  func(TreePath) error
+	Node     func(TreePath, *util.Ref[btrfsvol.LogicalAddr, Node], error) error
+	PostNode func(TreePath, *util.Ref[btrfsvol.LogicalAddr, Node]) error
+	// Callbacks for items on internal nodes
+	PreKeyPointer  func(TreePath, KeyPointer) error
+	PostKeyPointer func(TreePath, KeyPointer) error
+	// Callbacks for items on leaf nodes
+	Item func(TreePath, Item) error
+}
+
+// The lifecycle of callbacks is:
+//
+//     001 .PreNode()
+//     002 (read node)
+//     003 .Node()
+//         for item in node.items:
+//           if internal:
+//     004     .PreKeyPointer()
+//     005     (recurse)
+//     006     .PostKeyPointer()
+//           else:
+//     004     .Item()
+//     007 .PostNode()
+func (fs *FS) TreeWalk(treeID ObjID, cbs TreeWalkHandler) error {
+	rootInfo, err := fs.lookupTree(treeID)
+	if err != nil {
+		return err
+	}
+	path := TreePath{
+		TreePathElem{
+			ItemIdx:   -1,
+			NodeAddr:  rootInfo.RootNode,
+			NodeLevel: rootInfo.Level,
+		},
+	}
+	return fs.treeWalk(path, cbs)
+}
+
+func (fs *FS) treeWalk(path TreePath, cbs TreeWalkHandler) error {
+	if path[len(path)-1].NodeAddr == 0 {
+		return nil
+	}
+
+	if cbs.PreNode != nil {
+		if err := cbs.PreNode(path); err != nil {
+			if errors.Is(err, iofs.SkipDir) {
+				return nil
+			}
+			return err
+		}
+	}
+	node, err := fs.readNodeAtLevel(path[len(path)-1].NodeAddr, path[len(path)-1].NodeLevel)
+	if node != nil && err == nil {
+		path[len(path)-1].NodeLevel = node.Data.Head.Level
+	}
+	if cbs.Node != nil {
+		err = cbs.Node(path, node, err)
+	}
+	if err != nil {
+		if errors.Is(err, iofs.SkipDir) {
+			return nil
+		}
+		return fmt.Errorf("btrfs.FS.TreeWalk: %w", err)
+	}
+	if node != nil {
+		for i, item := range node.Data.BodyInternal {
+			itemPath := append(path, TreePathElem{
+				ItemIdx:   i,
+				NodeAddr:  item.BlockPtr,
+				NodeLevel: node.Data.Head.Level - 1,
+			})
+			if cbs.PreKeyPointer != nil {
+				if err := cbs.PreKeyPointer(itemPath, item); err != nil {
+					if errors.Is(err, iofs.SkipDir) {
+						continue
+					}
+					return err
+				}
+			}
+			if err := fs.treeWalk(itemPath, cbs); err != nil {
+				return err
+			}
+			if cbs.PostKeyPointer != nil {
+				if err := cbs.PostKeyPointer(itemPath, item); err != nil {
+					if errors.Is(err, iofs.SkipDir) {
+						continue
+					}
+					return err
+				}
+			}
+		}
+		for i, item := range node.Data.BodyLeaf {
+			if cbs.Item != nil {
+				itemPath := append(path, TreePathElem{
+					ItemIdx: i,
+				})
+				if err := cbs.Item(itemPath, item); err != nil {
+					if errors.Is(err, iofs.SkipDir) {
+						continue
+					}
+					return fmt.Errorf("btrfs.FS.TreeWalk: callback: %w", err)
+				}
+			}
+		}
+	}
+	if cbs.PostNode != nil {
+		if err := cbs.PostNode(path, node); err != nil {
+			if errors.Is(err, iofs.SkipDir) {
+				return nil
+			}
+			return err
+		}
+	}
+	return nil
+}
+
+func (fs *FS) treeSearch(treeRoot treeRoot, fn func(Key) int) (TreePath, *util.Ref[btrfsvol.LogicalAddr, Node], error) {
+	path := TreePath{
+		TreePathElem{
+			ItemIdx:   -1,
+			NodeAddr:  treeRoot.RootNode,
+			NodeLevel: treeRoot.Level,
+		},
+	}
+	for {
+		if path[len(path)-1].NodeAddr == 0 {
+			return nil, nil, iofs.ErrNotExist
+		}
+		node, err := fs.readNodeAtLevel(path[len(path)-1].NodeAddr, path[len(path)-1].NodeLevel)
+		if err != nil {
+			return nil, nil, err
+		}
+		path[len(path)-1].NodeLevel = node.Data.Head.Level
+
+		if node.Data.Head.Level > 0 {
+			// internal 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'.
+			//
+			// Implement this search as a binary search.
+			lastGood := -1
+			firstBad := len(node.Data.BodyInternal)
+			for firstBad > lastGood+1 {
+				midpoint := (lastGood + firstBad) / 2
+				direction := fn(node.Data.BodyInternal[midpoint].Key)
+				if direction < 0 {
+					firstBad = midpoint
+				} else {
+					lastGood = midpoint
+				}
+			}
+			if lastGood < 0 {
+				return nil, nil, iofs.ErrNotExist
+			}
+			path = append(path, TreePathElem{
+				ItemIdx:   lastGood,
+				NodeAddr:  node.Data.BodyInternal[lastGood].BlockPtr,
+				NodeLevel: 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.
+			beg := 0
+			end := len(node.Data.BodyLeaf)
+			for beg < end {
+				midpoint := (beg + end) / 2
+				direction := fn(node.Data.BodyLeaf[midpoint].Head.Key)
+				switch {
+				case direction < 0:
+					end = midpoint
+				case direction > 0:
+					beg = midpoint + 1
+				case direction == 0:
+					path = append(path, TreePathElem{
+						ItemIdx: midpoint,
+					})
+					return path, node, nil
+				}
+			}
+			return nil, nil, iofs.ErrNotExist
+		}
+	}
+}
+
+func (fs *FS) prev(path TreePath, node *util.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *util.Ref[btrfsvol.LogicalAddr, Node], error) {
+	var err error
+	path = append(TreePath(nil), path...)
+
+	// go up
+	for path[len(path)-1].ItemIdx < 1 {
+		path = path[:len(path)-1]
+		if len(path) == 0 {
+			return nil, nil, nil
+		}
+	}
+	// go left
+	path[len(path)-1].ItemIdx--
+	if path[len(path)-1].NodeAddr != 0 {
+		if node.Addr != path[len(path)-2].NodeAddr {
+			node, err = fs.readNodeAtLevel(path[len(path)-2].NodeAddr, path[len(path)-2].NodeLevel)
+			if err != nil {
+				return nil, nil, err
+			}
+			path[len(path)-1].NodeAddr = node.Data.BodyInternal[path[len(path)-1].ItemIdx].BlockPtr
+		}
+	}
+	// go down
+	for path[len(path)-1].NodeAddr != 0 {
+		if node.Addr != path[len(path)-1].NodeAddr {
+			node, err = fs.readNodeAtLevel(path[len(path)-1].NodeAddr, path[len(path)-1].NodeLevel)
+			if err != nil {
+				return nil, nil, err
+			}
+		}
+		if node.Data.Head.Level > 0 {
+			path = append(path, TreePathElem{
+				ItemIdx:   len(node.Data.BodyInternal) - 1,
+				NodeAddr:  node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr,
+				NodeLevel: node.Data.Head.Level - 1,
+			})
+		} else {
+			path = append(path, TreePathElem{
+				ItemIdx: len(node.Data.BodyLeaf) - 1,
+			})
+		}
+	}
+	// return
+	if node.Addr != path[len(path)-2].NodeAddr {
+		node, err = fs.readNodeAtLevel(path[len(path)-2].NodeAddr, path[len(path)-2].NodeLevel)
+		if err != nil {
+			return nil, nil, err
+		}
+	}
+	return path, node, nil
+}
+
+func (fs *FS) next(path TreePath, node *util.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *util.Ref[btrfsvol.LogicalAddr, Node], error) {
+	var err error
+	path = append(TreePath(nil), path...)
+
+	// go up
+	if node.Addr != path[len(path)-2].NodeAddr {
+		node, err = fs.readNodeAtLevel(path[len(path)-2].NodeAddr, path[len(path)-2].NodeLevel)
+		if err != nil {
+			return nil, nil, err
+		}
+		path[len(path)-2].NodeLevel = node.Data.Head.Level
+	}
+	for path[len(path)-1].ItemIdx+1 >= int(node.Data.Head.NumItems) {
+		path = path[:len(path)-1]
+		if len(path) == 1 {
+			return nil, nil, nil
+		}
+		if node.Addr != path[len(path)-2].NodeAddr {
+			node, err = fs.readNodeAtLevel(path[len(path)-2].NodeAddr, path[len(path)-2].NodeLevel)
+			if err != nil {
+				return nil, nil, err
+			}
+			path[len(path)-2].NodeLevel = node.Data.Head.Level
+		}
+	}
+	// go left
+	path[len(path)-1].ItemIdx++
+	if path[len(path)-1].NodeAddr != 0 {
+		if node.Addr != path[len(path)-2].NodeAddr {
+			node, err = fs.readNodeAtLevel(path[len(path)-2].NodeAddr, path[len(path)-2].NodeLevel)
+			if err != nil {
+				return nil, nil, err
+			}
+			path[len(path)-1].NodeAddr = node.Data.BodyInternal[path[len(path)-1].ItemIdx].BlockPtr
+		}
+	}
+	// go down
+	for path[len(path)-1].NodeAddr != 0 {
+		if node.Addr != path[len(path)-1].NodeAddr {
+			node, err = fs.readNodeAtLevel(path[len(path)-1].NodeAddr, path[len(path)-1].NodeLevel)
+			if err != nil {
+				return nil, nil, err
+			}
+			path[len(path)-1].NodeLevel = node.Data.Head.Level
+		}
+		if node.Data.Head.Level > 0 {
+			path = append(path, TreePathElem{
+				ItemIdx:   0,
+				NodeAddr:  node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr,
+				NodeLevel: node.Data.Head.Level - 1,
+			})
+		} else {
+			path = append(path, TreePathElem{
+				ItemIdx: 0,
+			})
+		}
+	}
+	// return
+	if node.Addr != path[len(path)-2].NodeAddr {
+		node, err = fs.readNodeAtLevel(path[len(path)-2].NodeAddr, path[len(path)-2].NodeLevel)
+		if err != nil {
+			return nil, nil, err
+		}
+	}
+	return path, node, nil
+}
+
+func (fs *FS) TreeSearch(treeID ObjID, fn func(Key) int) (Item, error) {
+	rootInfo, err := fs.lookupTree(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[len(path)-1].ItemIdx], nil
+}
+
+func (fs *FS) TreeLookup(treeID ObjID, key Key) (Item, error) {
+	item, err := fs.TreeSearch(treeID, key.Cmp)
+	if err != nil {
+		err = fmt.Errorf("item with key=%v: %w", key, err)
+	}
+	return item, err
+}
+
+// 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.
+func (fs *FS) TreeSearchAll(treeID ObjID, fn func(Key) int) ([]Item, error) {
+	rootInfo, err := fs.lookupTree(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[len(middlePath)-1].ItemIdx]
+
+	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 prevPath == nil {
+			break
+		}
+		prevItem := prevNode.Data.BodyLeaf[prevPath[len(prevPath)-1].ItemIdx]
+		if fn(prevItem.Head.Key) != 0 {
+			break
+		}
+		ret = append(ret, prevItem)
+	}
+	util.ReverseSlice(ret)
+	for nextPath, nextNode := middlePath, middleNode; true; {
+		nextPath, nextNode, err = fs.next(nextPath, nextNode)
+		if err != nil {
+			errs = append(errs, err)
+			break
+		}
+		if nextPath == nil {
+			break
+		}
+		nextItem := nextNode.Data.BodyLeaf[nextPath[len(nextPath)-1].ItemIdx]
+		if fn(nextItem.Head.Key) != 0 {
+			break
+		}
+		ret = append(ret, nextItem)
+	}
+	if errs != nil {
+		err = errs
+	}
+	return ret, err
+}
diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go
new file mode 100644
index 0000000..7ae30cb
--- /dev/null
+++ b/lib/btrfs/io4_fs.go
@@ -0,0 +1,404 @@
+package btrfs
+
+import (
+	"fmt"
+	"io"
+	"path/filepath"
+	"reflect"
+	"sort"
+	"sync"
+
+	"github.com/datawire/dlib/derror"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type BareInode struct {
+	Inode     ObjID
+	InodeItem *btrfsitem.Inode
+	Errs      derror.MultiError
+}
+
+type FullInode struct {
+	BareInode
+	OtherItems []Item
+}
+
+type InodeRef struct {
+	Inode ObjID
+	btrfsitem.InodeRef
+}
+
+type Dir struct {
+	FullInode
+	DotDot          *InodeRef
+	ChildrenByName  map[string]btrfsitem.DirEntry
+	ChildrenByIndex map[uint64]btrfsitem.DirEntry
+	SV              *Subvolume
+}
+
+type FileExtent struct {
+	OffsetWithinFile int64
+	btrfsitem.FileExtent
+}
+
+type File struct {
+	FullInode
+	Extents []FileExtent
+	SV      *Subvolume
+}
+
+type Subvolume struct {
+	FS     *FS
+	TreeID ObjID
+
+	rootOnce sync.Once
+	rootVal  btrfsitem.Root
+	rootErr  error
+
+	bareInodeCache util.LRUCache[ObjID, *BareInode]
+	fullInodeCache util.LRUCache[ObjID, *FullInode]
+	dirCache       util.LRUCache[ObjID, *Dir]
+	fileCache      util.LRUCache[ObjID, *File]
+}
+
+func (sv *Subvolume) init() {
+	sv.rootOnce.Do(func() {
+		root, err := sv.FS.TreeLookup(ROOT_TREE_OBJECTID, Key{
+			ObjectID: sv.TreeID,
+			ItemType: btrfsitem.ROOT_ITEM_KEY,
+			Offset:   0,
+		})
+		if err != nil {
+			sv.rootErr = err
+			return
+		}
+
+		rootBody, ok := root.Body.(btrfsitem.Root)
+		if !ok {
+			sv.rootErr = fmt.Errorf("FS_TREE ROOT_ITEM has malformed body")
+			return
+		}
+
+		sv.rootVal = rootBody
+	})
+}
+
+func (sv *Subvolume) GetRootInode() (ObjID, error) {
+	sv.init()
+	return sv.rootVal.RootDirID, sv.rootErr
+}
+
+func (sv *Subvolume) LoadBareInode(inode ObjID) (*BareInode, error) {
+	val := sv.bareInodeCache.GetOrElse(inode, func() (val *BareInode) {
+		val = &BareInode{
+			Inode: inode,
+		}
+		item, err := sv.FS.TreeLookup(sv.TreeID, Key{
+			ObjectID: inode,
+			ItemType: btrfsitem.INODE_ITEM_KEY,
+			Offset:   0,
+		})
+		if err != nil {
+			val.Errs = append(val.Errs, err)
+			return
+		}
+
+		itemBody, ok := item.Body.(btrfsitem.Inode)
+		if !ok {
+			val.Errs = append(val.Errs, fmt.Errorf("malformed inode"))
+			return
+		}
+		val.InodeItem = &itemBody
+
+		return
+	})
+	if val.InodeItem == nil {
+		return nil, val.Errs
+	}
+	return val, nil
+}
+
+func (sv *Subvolume) LoadFullInode(inode ObjID) (*FullInode, error) {
+	val := sv.fullInodeCache.GetOrElse(inode, func() (val *FullInode) {
+		val = &FullInode{
+			BareInode: BareInode{
+				Inode: inode,
+			},
+		}
+		items, err := sv.FS.TreeSearchAll(sv.TreeID, func(key Key) int {
+			return util.CmpUint(inode, key.ObjectID)
+		})
+		if err != nil {
+			val.Errs = append(val.Errs, err)
+			if len(items) == 0 {
+				return
+			}
+		}
+		for _, item := range items {
+			switch item.Head.Key.ItemType {
+			case btrfsitem.INODE_ITEM_KEY:
+				itemBody := item.Body.(btrfsitem.Inode)
+				if val.InodeItem != nil {
+					if !reflect.DeepEqual(itemBody, *val.InodeItem) {
+						val.Errs = append(val.Errs, fmt.Errorf("multiple inodes"))
+					}
+					continue
+				}
+				val.InodeItem = &itemBody
+			default:
+				val.OtherItems = append(val.OtherItems, item)
+			}
+		}
+		return
+	})
+	if val.InodeItem == nil && val.OtherItems == nil {
+		return nil, val.Errs
+	}
+	return val, nil
+}
+
+func (sv *Subvolume) LoadDir(inode ObjID) (*Dir, error) {
+	val := sv.dirCache.GetOrElse(inode, func() (val *Dir) {
+		val = new(Dir)
+		fullInode, err := sv.LoadFullInode(inode)
+		if err != nil {
+			val.Errs = append(val.Errs, err)
+			return
+		}
+		val.FullInode = *fullInode
+		val.SV = sv
+		val.populate()
+		return
+	})
+	if val.Inode == 0 {
+		return nil, val.Errs
+	}
+	return val, nil
+}
+
+func (ret *Dir) populate() {
+	ret.ChildrenByName = make(map[string]btrfsitem.DirEntry)
+	ret.ChildrenByIndex = make(map[uint64]btrfsitem.DirEntry)
+	for _, item := range ret.OtherItems {
+		switch item.Head.Key.ItemType {
+		case btrfsitem.INODE_REF_KEY:
+			ref := InodeRef{
+				Inode:    ObjID(item.Head.Key.Offset),
+				InodeRef: item.Body.(btrfsitem.InodeRef),
+			}
+			if ret.DotDot != nil {
+				if !reflect.DeepEqual(ref, *ret.DotDot) {
+					ret.Errs = append(ret.Errs, fmt.Errorf("multiple INODE_REF items on a directory"))
+				}
+				continue
+			}
+			ret.DotDot = &ref
+		case btrfsitem.DIR_ITEM_KEY:
+			body := item.Body.(btrfsitem.DirEntries)
+			if len(body) != 1 {
+				ret.Errs = append(ret.Errs, fmt.Errorf("multiple direntries in single DIR_ITEM?"))
+				continue
+			}
+			for _, entry := range body {
+				namehash := btrfsitem.NameHash(entry.Name)
+				if namehash != item.Head.Key.Offset {
+					ret.Errs = append(ret.Errs, fmt.Errorf("direntry crc32c mismatch: key=%#x crc32c(%q)=%#x",
+						item.Head.Key.Offset, entry.Name, namehash))
+					continue
+				}
+				if other, exists := ret.ChildrenByName[string(entry.Name)]; exists {
+					if !reflect.DeepEqual(entry, other) {
+						ret.Errs = append(ret.Errs, fmt.Errorf("multiple instances of direntry name %q", entry.Name))
+					}
+					continue
+				}
+				ret.ChildrenByName[string(entry.Name)] = entry
+			}
+		case btrfsitem.DIR_INDEX_KEY:
+			index := item.Head.Key.Offset
+			body := item.Body.(btrfsitem.DirEntries)
+			if len(body) != 1 {
+				ret.Errs = append(ret.Errs, fmt.Errorf("multiple direntries in single DIR_INDEX?"))
+				continue
+			}
+			for _, entry := range body {
+				if other, exists := ret.ChildrenByIndex[index]; exists {
+					if !reflect.DeepEqual(entry, other) {
+						ret.Errs = append(ret.Errs, fmt.Errorf("multiple instances of direntry index %v", index))
+					}
+					continue
+				}
+				ret.ChildrenByIndex[index] = entry
+			}
+		//case btrfsitem.XATTR_ITEM_KEY:
+		default:
+			panic(fmt.Errorf("TODO: handle item type %v", item.Head.Key.ItemType))
+		}
+	}
+	entriesWithIndexes := make(map[string]struct{})
+	nextIndex := uint64(2)
+	for index, entry := range ret.ChildrenByIndex {
+		if index+1 > nextIndex {
+			nextIndex = index + 1
+		}
+		entriesWithIndexes[string(entry.Name)] = struct{}{}
+		if other, exists := ret.ChildrenByName[string(entry.Name)]; !exists {
+			ret.Errs = append(ret.Errs, fmt.Errorf("missing by-name direntry for %q", entry.Name))
+			ret.ChildrenByName[string(entry.Name)] = entry
+		} else if !reflect.DeepEqual(entry, other) {
+			ret.Errs = append(ret.Errs, fmt.Errorf("direntry index %v and direntry name %q disagree", index, entry.Name))
+			ret.ChildrenByName[string(entry.Name)] = entry
+		}
+	}
+	for _, name := range util.SortedMapKeys(ret.ChildrenByName) {
+		if _, exists := entriesWithIndexes[name]; !exists {
+			ret.Errs = append(ret.Errs, fmt.Errorf("missing by-index direntry for %q", name))
+			ret.ChildrenByIndex[nextIndex] = ret.ChildrenByName[name]
+			nextIndex++
+		}
+	}
+}
+
+func (dir *Dir) AbsPath() (string, error) {
+	rootInode, err := dir.SV.GetRootInode()
+	if err != nil {
+		return "", err
+	}
+	if rootInode == dir.Inode {
+		return "/", nil
+	}
+	if dir.DotDot == nil {
+		return "", fmt.Errorf("missing .. entry in dir inode %v", dir.Inode)
+	}
+	parent, err := dir.SV.LoadDir(dir.DotDot.Inode)
+	if err != nil {
+		return "", err
+	}
+	parentName, err := parent.AbsPath()
+	if err != nil {
+		return "", err
+	}
+	return filepath.Join(parentName, string(dir.DotDot.Name)), nil
+}
+
+func (sv *Subvolume) LoadFile(inode ObjID) (*File, error) {
+	val := sv.fileCache.GetOrElse(inode, func() (val *File) {
+		val = new(File)
+		fullInode, err := sv.LoadFullInode(inode)
+		if err != nil {
+			val.Errs = append(val.Errs, err)
+			return
+		}
+		val.FullInode = *fullInode
+		val.SV = sv
+		val.populate()
+		return
+	})
+	if val.Inode == 0 {
+		return nil, val.Errs
+	}
+	return val, nil
+}
+
+func (ret *File) populate() {
+	for _, item := range ret.OtherItems {
+		switch item.Head.Key.ItemType {
+		case btrfsitem.INODE_REF_KEY:
+			// TODO
+		case btrfsitem.EXTENT_DATA_KEY:
+			ret.Extents = append(ret.Extents, FileExtent{
+				OffsetWithinFile: int64(item.Head.Key.Offset),
+				FileExtent:       item.Body.(btrfsitem.FileExtent),
+			})
+		default:
+			panic(fmt.Errorf("TODO: handle item type %v", item.Head.Key.ItemType))
+		}
+	}
+
+	// These should already be sorted, because of the nature of
+	// the btree; but this is a recovery tool for corrupt
+	// filesystems, so go ahead and ensure that it's sorted.
+	sort.Slice(ret.Extents, func(i, j int) bool {
+		return ret.Extents[i].OffsetWithinFile < ret.Extents[j].OffsetWithinFile
+	})
+
+	pos := int64(0)
+	for _, extent := range ret.Extents {
+		if extent.OffsetWithinFile != pos {
+			if extent.OffsetWithinFile > pos {
+				ret.Errs = append(ret.Errs, fmt.Errorf("extent gap from %v to %v",
+					pos, extent.OffsetWithinFile))
+			} else {
+				ret.Errs = append(ret.Errs, fmt.Errorf("extent overlap from %v to %v",
+					extent.OffsetWithinFile, pos))
+			}
+		}
+		size, err := extent.Size()
+		if err != nil {
+			ret.Errs = append(ret.Errs, fmt.Errorf("extent %v: %w", extent.OffsetWithinFile, err))
+		}
+		pos += size
+	}
+	if ret.InodeItem != nil && pos != ret.InodeItem.Size {
+		if ret.InodeItem.Size > pos {
+			ret.Errs = append(ret.Errs, fmt.Errorf("extent gap from %v to %v",
+				pos, ret.InodeItem.Size))
+		} else {
+			ret.Errs = append(ret.Errs, fmt.Errorf("extent mapped past end of file from %v to %v",
+				ret.InodeItem.Size, pos))
+		}
+	}
+}
+
+func (file *File) ReadAt(dat []byte, off int64) (int, error) {
+	// These stateles maybe-short-reads each do an O(n) extent
+	// lookup, so reading a file is O(n^2), but we expect n to be
+	// small, so whatev.  Turn file.Extents it in to an rbtree if
+	// it becomes a problem.
+	done := 0
+	for done < len(dat) {
+		n, err := file.maybeShortReadAt(dat[done:], off+int64(done))
+		done += n
+		if err != nil {
+			return done, err
+		}
+	}
+	return done, nil
+}
+
+func (file *File) maybeShortReadAt(dat []byte, off int64) (int, error) {
+	for _, extent := range file.Extents {
+		extBeg := extent.OffsetWithinFile
+		if extBeg > off {
+			break
+		}
+		extLen, err := extent.Size()
+		if err != nil {
+			continue
+		}
+		extEnd := extBeg + extLen
+		if extEnd <= off {
+			continue
+		}
+		offsetWithinExt := off - extent.OffsetWithinFile
+		readSize := util.Min(int64(len(dat)), extLen-offsetWithinExt)
+		switch extent.Type {
+		case btrfsitem.FILE_EXTENT_INLINE:
+			return copy(dat, extent.BodyInline[offsetWithinExt:offsetWithinExt+readSize]), nil
+		case btrfsitem.FILE_EXTENT_REG, btrfsitem.FILE_EXTENT_PREALLOC:
+			return file.SV.FS.ReadAt(dat[:readSize],
+				extent.BodyExtent.DiskByteNr.
+					Add(extent.BodyExtent.Offset).
+					Add(btrfsvol.AddrDelta(offsetWithinExt)))
+		}
+	}
+	if file.InodeItem != nil && off >= file.InodeItem.Size {
+		return 0, io.EOF
+	}
+	return 0, fmt.Errorf("read: could not map position %v", off)
+}
+
+var _ io.ReaderAt = (*File)(nil)
diff --git a/lib/btrfs/types_node.go b/lib/btrfs/types_node.go
new file mode 100644
index 0000000..5934f40
--- /dev/null
+++ b/lib/btrfs/types_node.go
@@ -0,0 +1,411 @@
+package btrfs
+
+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/btrfssum"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+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 util.BitfieldString(f, nodeFlagNames, util.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 internal nodes
+	BodyLeaf     []Item       // for leave nodes
+
+	Padding []byte
+}
+
+type NodeHeader struct {
+	Checksum      btrfssum.CSum        `bin:"off=0x0,  siz=0x20"`
+	MetadataUUID  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 UUID                 `bin:"off=0x40, siz=0x10"`
+	Generation    Generation           `bin:"off=0x50, siz=0x8"`
+	Owner         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 internal 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) 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,
+	}
+	n, err := binstruct.Unmarshal(nodeBuf, &node.Head)
+	if err != nil {
+		return n, fmt.Errorf("btrfs.Node.UnmarshalBinary: %w", err)
+	}
+	if node.Head.Level > 0 {
+		_n, err := node.unmarshalInternal(nodeBuf[n:])
+		n += _n
+		if err != nil {
+			return n, fmt.Errorf("btrfs.Node.UnmarshalBinary: internal: %w", err)
+		}
+	} else {
+		_n, err := node.unmarshalLeaf(nodeBuf[n:])
+		n += _n
+		if err != nil {
+			return n, fmt.Errorf("btrfs.Node.UnmarshalBinary: leaf: %w", err)
+		}
+	}
+	if n != len(nodeBuf) {
+		return n, fmt.Errorf("btrfs.Node.UnmarshalBinary: 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("btrfs.Node.MarshalBinary: .Size must be set")
+	}
+	if node.Size <= uint32(binstruct.StaticSize(NodeHeader{})) {
+		return nil, fmt.Errorf("btrfs.Node.MarshalBinary: .Size must be greater than %v",
+			binstruct.StaticSize(NodeHeader{}))
+	}
+	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("btrfs.Node.MarshalBinary: 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: "internal" ////////////////////////////////////////////////////////////////////////////////
+
+type KeyPointer struct {
+	Key           Key                  `bin:"off=0x0, siz=0x11"`
+	BlockPtr      btrfsvol.LogicalAddr `bin:"off=0x11, siz=0x8"`
+	Generation    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 {
+	Head ItemHeader
+	Body btrfsitem.Item
+}
+
+type ItemHeader struct {
+	Key           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 item Item
+
+		n, err := binstruct.Unmarshal(bodyBuf[head:], &item.Head)
+		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(item.Head.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(item.Head.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]
+		item.Body = btrfsitem.UnmarshalItem(item.Head.Key, node.ChecksumType, dataBuf)
+
+		node.BodyLeaf = append(node.BodyLeaf, item)
+	}
+
+	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)
+		}
+		item.Head.DataSize = uint32(len(itemBodyBuf))
+		item.Head.DataOffset = uint32(tail - len(itemBodyBuf))
+		itemHeadBuf, err := binstruct.Marshal(item.Head)
+		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{}))
+		freeSpace -= item.Head.DataSize
+	}
+	return freeSpace
+}
+
+// Tie Nodes in to the FS //////////////////////////////////////////////////////////////////////////
+
+var ErrNotANode = errors.New("does not look like a node")
+
+func ReadNode[Addr ~int64](fs util.File[Addr], sb Superblock, addr Addr, laddrCB func(btrfsvol.LogicalAddr) error) (*util.Ref[Addr, Node], error) {
+	nodeBuf := make([]byte, sb.NodeSize)
+	if _, err := fs.ReadAt(nodeBuf, addr); err != nil {
+		return nil, err
+	}
+
+	// parse (early)
+
+	nodeRef := &util.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 laddrCB != nil {
+		if err := laddrCB(nodeRef.Data.Head.Addr); err != nil {
+			return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err)
+		}
+	}
+
+	// parse (main)
+
+	if _, err := nodeRef.Data.UnmarshalBinary(nodeBuf); err != nil {
+		return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err)
+	}
+
+	// return
+
+	return nodeRef, nil
+}
+
+func (fs *FS) ReadNode(addr btrfsvol.LogicalAddr) (*util.Ref[btrfsvol.LogicalAddr, Node], error) {
+	sb, err := fs.Superblock()
+	if err != nil {
+		return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err)
+	}
+
+	return ReadNode[btrfsvol.LogicalAddr](fs, sb.Data, addr, func(claimAddr btrfsvol.LogicalAddr) error {
+		if claimAddr != addr {
+			return fmt.Errorf("read from laddr=%v but claims to be at laddr=%v",
+				addr, claimAddr)
+		}
+		return nil
+	})
+}
+
+func (fs *FS) readNodeAtLevel(addr btrfsvol.LogicalAddr, expLevel uint8) (*util.Ref[btrfsvol.LogicalAddr, Node], error) {
+	node, err := fs.ReadNode(addr)
+	if err != nil {
+		return node, err
+	}
+	if node.Data.Head.Level != expLevel {
+		return node, fmt.Errorf("btrfs.FS.ReadNode: node@%v: expected level %v but has level %v",
+			node.Addr, expLevel, node.Data.Head.Level)
+	}
+	return node, nil
+}
diff --git a/lib/btrfs/types_superblock.go b/lib/btrfs/types_superblock.go
new file mode 100644
index 0000000..373de48
--- /dev/null
+++ b/lib/btrfs/types_superblock.go
@@ -0,0 +1,233 @@
+package btrfs
+
+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/btrfssum"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type Superblock struct {
+	Checksum   btrfssum.CSum         `bin:"off=0x0,  siz=0x20"` // Checksum of everything past this field (from 0x20 to 0x1000)
+	FSUUID     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 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 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 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    Generation    `bin:"off=0x22b, siz=0x8"`
+	UUIDTreeGeneration Generation    `bin:"off=0x233, siz=0x8"`
+
+	// FeatureIncompatMetadataUUID
+	MetadataUUID UUID `bin:"off=0x23b, siz=0x10"`
+
+	// FeatureIncompatExtentTreeV2
+	NumGlobalRoots uint64 `bin:"off=0x24b, siz=0x8"`
+
+	// FeatureIncompatExtentTreeV2
+	BlockGroupRoot           btrfsvol.LogicalAddr `bin:"off=0x253, siz=0x8"`
+	BlockGroupRootGeneration 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() UUID {
+	if !sb.IncompatFlags.Has(FeatureIncompatMetadataUUID) {
+		return sb.FSUUID
+	}
+	return sb.MetadataUUID
+}
+
+type SysChunk struct {
+	Key   Key
+	Chunk btrfsitem.Chunk
+}
+
+func (sc SysChunk) MarshalBinary() ([]byte, error) {
+	dat, err := binstruct.Marshal(sc.Key)
+	if err != nil {
+		return dat, fmt.Errorf("%T.MarshalBinary: %w", sc, err)
+	}
+	_dat, err := binstruct.Marshal(sc.Chunk)
+	dat = append(dat, _dat...)
+	if err != nil {
+		return dat, fmt.Errorf("%T.MarshalBinary: %w", sc, err)
+	}
+	return dat, nil
+}
+
+func (sc *SysChunk) UnmarshalBinary(dat []byte) (int, error) {
+	n, err := binstruct.Unmarshal(dat, &sc.Key)
+	if err != nil {
+		return n, fmt.Errorf("%T.UnmarshalBinary: %w", *sc, err)
+	}
+	_n, err := binstruct.Unmarshal(dat[n:], &sc.Chunk)
+	n += _n
+	if err != nil {
+		return n, fmt.Errorf("%T.UnmarshalBinary: %w", *sc, 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    ObjID      `bin:"off=0x0, siz=0x8"`
+	TreeRootGen Generation `bin:"off=0x8, siz=0x8"`
+
+	ChunkRoot    ObjID      `bin:"off=0x10, siz=0x8"`
+	ChunkRootGen Generation `bin:"off=0x18, siz=0x8"`
+
+	ExtentRoot    ObjID      `bin:"off=0x20, siz=0x8"`
+	ExtentRootGen Generation `bin:"off=0x28, siz=0x8"`
+
+	FSRoot    ObjID      `bin:"off=0x30, siz=0x8"`
+	FSRootGen Generation `bin:"off=0x38, siz=0x8"`
+
+	DevRoot    ObjID      `bin:"off=0x40, siz=0x8"`
+	DevRootGen Generation `bin:"off=0x48, siz=0x8"`
+
+	ChecksumRoot    ObjID      `bin:"off=0x50, siz=0x8"`
+	ChecksumRootGen 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 util.BitfieldString(f, incompatFlagNames, util.HexLower)
+}
diff --git a/lib/btrfsmisc/fsck.go b/lib/btrfsmisc/fsck.go
new file mode 100644
index 0000000..9567bdf
--- /dev/null
+++ b/lib/btrfsmisc/fsck.go
@@ -0,0 +1,51 @@
+package btrfsmisc
+
+import (
+	"errors"
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+// ScanForNodes mimics btrfs-progs
+// cmds/rescue-chunk-recover.c:scan_one_device(), except rather than
+// doing something itself when it finds a node, it simply calls a
+// callback function.
+func ScanForNodes(dev *btrfs.Device, sb btrfs.Superblock, fn func(*util.Ref[btrfsvol.PhysicalAddr, btrfs.Node], error), prog func(btrfsvol.PhysicalAddr)) error {
+	devSize, err := dev.Size()
+	if err != nil {
+		return err
+	}
+
+	if sb.NodeSize < sb.SectorSize {
+		return fmt.Errorf("node_size(%v) < sector_size(%v)",
+			sb.NodeSize, sb.SectorSize)
+	}
+
+	for pos := btrfsvol.PhysicalAddr(0); pos+btrfsvol.PhysicalAddr(sb.NodeSize) < devSize; pos += btrfsvol.PhysicalAddr(sb.SectorSize) {
+		if util.InSlice(pos, btrfs.SuperblockAddrs) {
+			//fmt.Printf("sector@%v is a superblock\n", pos)
+			continue
+		}
+
+		if prog != nil {
+			prog(pos)
+		}
+
+		nodeRef, err := btrfs.ReadNode[btrfsvol.PhysicalAddr](dev, sb, pos, nil)
+		if err != nil && errors.Is(err, btrfs.ErrNotANode) {
+			continue
+		}
+		fn(nodeRef, err)
+
+		pos += btrfsvol.PhysicalAddr(sb.NodeSize) - btrfsvol.PhysicalAddr(sb.SectorSize)
+	}
+
+	if prog != nil {
+		prog(devSize)
+	}
+
+	return nil
+}
diff --git a/lib/btrfsmisc/open.go b/lib/btrfsmisc/open.go
new file mode 100644
index 0000000..a52926f
--- /dev/null
+++ b/lib/btrfsmisc/open.go
@@ -0,0 +1,24 @@
+package btrfsmisc
+
+import (
+	"fmt"
+	"os"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+)
+
+func Open(flag int, filenames ...string) (*btrfs.FS, error) {
+	fs := new(btrfs.FS)
+	for _, filename := range filenames {
+		fh, err := os.OpenFile(filename, flag, 0)
+		if err != nil {
+			_ = fs.Close()
+			return nil, fmt.Errorf("file %q: %w", filename, err)
+		}
+		if err := fs.AddDevice(&btrfs.Device{File: fh}); err != nil {
+			_ = fs.Close()
+			return nil, fmt.Errorf("file %q: %w", filename, err)
+		}
+	}
+	return fs, nil
+}
diff --git a/lib/btrfsmisc/print_tree.go b/lib/btrfsmisc/print_tree.go
new file mode 100644
index 0000000..69692e7
--- /dev/null
+++ b/lib/btrfsmisc/print_tree.go
@@ -0,0 +1,362 @@
+package btrfsmisc
+
+import (
+	"fmt"
+	"os"
+	"strings"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"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/util"
+)
+
+// PrintTree mimics btrfs-progs
+// kernel-shared/print-tree.c:btrfs_print_tree() and
+// kernel-shared/print-tree.c:btrfs_print_leaf()
+func PrintTree(fs *btrfs.FS, treeID btrfs.ObjID) error {
+	return fs.TreeWalk(treeID, btrfs.TreeWalkHandler{
+		Node: func(path btrfs.TreePath, nodeRef *util.Ref[btrfsvol.LogicalAddr, btrfs.Node], err error) error {
+			if err != nil {
+				fmt.Fprintf(os.Stderr, "error: %v: %v\n", path, err)
+			}
+			if nodeRef != nil {
+				printHeaderInfo(nodeRef.Data)
+			}
+			return nil
+		},
+		PreKeyPointer: func(_ btrfs.TreePath, item btrfs.KeyPointer) error {
+			fmt.Printf("\t%v block %v gen %v\n",
+				FmtKey(item.Key),
+				item.BlockPtr,
+				item.Generation)
+			return nil
+		},
+		Item: func(path btrfs.TreePath, item btrfs.Item) error {
+			i := path[len(path)-1].ItemIdx
+			fmt.Printf("\titem %v %v itemoff %v itemsize %v\n",
+				i,
+				FmtKey(item.Head.Key),
+				item.Head.DataOffset,
+				item.Head.DataSize)
+			switch body := item.Body.(type) {
+			case btrfsitem.FreeSpaceHeader:
+				fmt.Printf("\t\tlocation %v\n", FmtKey(body.Location))
+				fmt.Printf("\t\tcache generation %v entries %v bitmaps %v\n",
+					body.Generation, body.NumEntries, body.NumBitmaps)
+			case btrfsitem.Inode:
+				fmt.Printf(""+
+					"\t\tgeneration %v transid %v size %v nbytes %v\n"+
+					"\t\tblock group %v mode %o links %v uid %v gid %v rdev %v\n"+
+					"\t\tsequence %v flags %v\n",
+					body.Generation, body.TransID, body.Size, body.NumBytes,
+					body.BlockGroup, body.Mode, body.NLink, body.UID, body.GID, body.RDev,
+					body.Sequence, body.Flags)
+				fmt.Printf("\t\tatime %v\n", fmtTime(body.ATime))
+				fmt.Printf("\t\tctime %v\n", fmtTime(body.CTime))
+				fmt.Printf("\t\tmtime %v\n", fmtTime(body.MTime))
+				fmt.Printf("\t\totime %v\n", fmtTime(body.OTime))
+			case btrfsitem.InodeRef:
+				fmt.Printf("\t\tindex %v namelen %v name: %s\n",
+					body.Index, body.NameLen, body.Name)
+			//case btrfsitem.INODE_EXTREF_KEY:
+			//	// TODO
+			case btrfsitem.DirEntries:
+				for _, dir := range body {
+					fmt.Printf("\t\tlocation %v type %v\n",
+						FmtKey(dir.Location), dir.Type)
+					fmt.Printf("\t\ttransid %v data_len %v name_len %v\n",
+						dir.TransID, dir.DataLen, dir.NameLen)
+					fmt.Printf("\t\tname: %s\n", dir.Name)
+					if len(dir.Data) > 0 {
+						fmt.Printf("\t\tdata %v\n", dir.Data)
+					}
+				}
+			//case btrfsitem.DIR_LOG_INDEX_KEY, btrfsitem.DIR_LOG_ITEM_KEY:
+			//	// TODO
+			case btrfsitem.Root:
+				fmt.Printf("\t\tgeneration %v root_dirid %v bytenr %d byte_limit %v bytes_used %v\n",
+					body.Generation, body.RootDirID, body.ByteNr, body.ByteLimit, body.BytesUsed)
+				fmt.Printf("\t\tlast_snapshot %v flags %v refs %v\n",
+					body.LastSnapshot, body.Flags, body.Refs)
+				fmt.Printf("\t\tdrop_progress %v drop_level %v\n",
+					FmtKey(body.DropProgress), body.DropLevel)
+				fmt.Printf("\t\tlevel %v generation_v2 %v\n",
+					body.Level, body.GenerationV2)
+				if body.Generation == body.GenerationV2 {
+					fmt.Printf("\t\tuuid %v\n", body.UUID)
+					fmt.Printf("\t\tparent_uuid %v\n", body.ParentUUID)
+					fmt.Printf("\t\treceived_uuid %v\n", body.ReceivedUUID)
+					fmt.Printf("\t\tctransid %v otransid %v stransid %v rtransid %v\n",
+						body.CTransID, body.OTransID, body.STransID, body.RTransID)
+					fmt.Printf("\t\tctime %v\n", fmtTime(body.CTime))
+					fmt.Printf("\t\totime %v\n", fmtTime(body.OTime))
+					fmt.Printf("\t\tstime %v\n", fmtTime(body.STime))
+					fmt.Printf("\t\trtime %v\n", fmtTime(body.RTime))
+				}
+			case btrfsitem.RootRef:
+				var tag string
+				switch item.Head.Key.ItemType {
+				case btrfsitem.ROOT_REF_KEY:
+					tag = "ref"
+				case btrfsitem.ROOT_BACKREF_KEY:
+					tag = "backref"
+				default:
+					tag = fmt.Sprintf("(error: unhandled RootRef item type: %v)", item.Head.Key.ItemType)
+				}
+				fmt.Printf("\t\troot %v key dirid %v sequence %v name %s\n",
+					tag, body.DirID, body.Sequence, body.Name)
+			case btrfsitem.Extent:
+				fmt.Printf("\t\trefs %v gen %v flags %v\n",
+					body.Head.Refs, body.Head.Generation, body.Head.Flags)
+				if body.Head.Flags.Has(btrfsitem.EXTENT_FLAG_TREE_BLOCK) {
+					fmt.Printf("\t\ttree block %v level %v\n",
+						FmtKey(body.Info.Key), body.Info.Level)
+				}
+				printExtentInlineRefs(body.Refs)
+			case btrfsitem.Metadata:
+				fmt.Printf("\t\trefs %v gen %v flags %v\n",
+					body.Head.Refs, body.Head.Generation, body.Head.Flags)
+				fmt.Printf("\t\ttree block skinny level %v\n", item.Head.Key.Offset)
+				printExtentInlineRefs(body.Refs)
+			//case btrfsitem.EXTENT_DATA_REF_KEY:
+			//	// TODO
+			//case btrfsitem.SHARED_DATA_REF_KEY:
+			//	// TODO
+			case btrfsitem.ExtentCSum:
+				sb, _ := fs.Superblock()
+				sectorSize := btrfsvol.AddrDelta(sb.Data.SectorSize)
+
+				start := btrfsvol.LogicalAddr(item.Head.Key.Offset)
+				itemSize := btrfsvol.AddrDelta(len(body.Sums)) * sectorSize
+				fmt.Printf("\t\trange start %d end %d length %d",
+					start, start.Add(itemSize), itemSize)
+				sumsPerLine := util.Max(1, len(btrfssum.CSum{})/body.ChecksumSize/2)
+
+				pos := start
+				for i, sum := range body.Sums {
+					if i%sumsPerLine == 0 {
+						fmt.Printf("\n\t\t")
+					} else {
+						fmt.Printf(" ")
+					}
+					fmt.Printf("[%d] 0x%s", pos, sum.Fmt(sb.Data.ChecksumType))
+					pos = pos.Add(sectorSize)
+				}
+				fmt.Printf("\n")
+			case btrfsitem.FileExtent:
+				fmt.Printf("\t\tgeneration %v type %v\n",
+					body.Generation, body.Type)
+				switch body.Type {
+				case btrfsitem.FILE_EXTENT_INLINE:
+					fmt.Printf("\t\tinline extent data size %v ram_bytes %v compression %v\n",
+						len(body.BodyInline), body.RAMBytes, body.Compression)
+				case btrfsitem.FILE_EXTENT_PREALLOC:
+					fmt.Printf("\t\tprealloc data disk byte %v nr %v\n",
+						body.BodyExtent.DiskByteNr,
+						body.BodyExtent.DiskNumBytes)
+					fmt.Printf("\t\tprealloc data offset %v nr %v\n",
+						body.BodyExtent.Offset,
+						body.BodyExtent.NumBytes)
+				case btrfsitem.FILE_EXTENT_REG:
+					fmt.Printf("\t\textent data disk byte %d nr %d\n",
+						body.BodyExtent.DiskByteNr,
+						body.BodyExtent.DiskNumBytes)
+					fmt.Printf("\t\textent data offset %d nr %d ram %v\n",
+						body.BodyExtent.Offset,
+						body.BodyExtent.NumBytes,
+						body.RAMBytes)
+					fmt.Printf("\t\textent compression %v\n",
+						body.Compression)
+				default:
+					fmt.Printf("\t\t(error) unknown file extent type %v", body.Type)
+				}
+			case btrfsitem.BlockGroup:
+				fmt.Printf("\t\tblock group used %v chunk_objectid %v flags %v\n",
+					body.Used, body.ChunkObjectID, body.Flags)
+			case btrfsitem.FreeSpaceInfo:
+				fmt.Printf("\t\tfree space info extent count %v flags %v\n",
+					body.ExtentCount, body.Flags)
+			case btrfsitem.FreeSpaceBitmap:
+				fmt.Printf("\t\tfree space bitmap\n")
+			case btrfsitem.Chunk:
+				fmt.Printf("\t\tlength %d owner %d stripe_len %v type %v\n",
+					body.Head.Size, body.Head.Owner, body.Head.StripeLen, body.Head.Type)
+				fmt.Printf("\t\tio_align %v io_width %v sector_size %v\n",
+					body.Head.IOOptimalAlign, body.Head.IOOptimalWidth, body.Head.IOMinSize)
+				fmt.Printf("\t\tnum_stripes %v sub_stripes %v\n",
+					body.Head.NumStripes, body.Head.SubStripes)
+				for i, stripe := range body.Stripes {
+					fmt.Printf("\t\t\tstripe %v devid %d offset %d\n",
+						i, stripe.DeviceID, stripe.Offset)
+					fmt.Printf("\t\t\tdev_uuid %v\n",
+						stripe.DeviceUUID)
+				}
+			case btrfsitem.Dev:
+				fmt.Printf(""+
+					"\t\tdevid %d total_bytes %v bytes_used %v\n"+
+					"\t\tio_align %v io_width %v sector_size %v type %v\n"+
+					"\t\tgeneration %v start_offset %v dev_group %v\n"+
+					"\t\tseek_speed %v bandwidth %v\n"+
+					"\t\tuuid %v\n"+
+					"\t\tfsid %v\n",
+					body.DevID, body.NumBytes, body.NumBytesUsed,
+					body.IOOptimalAlign, body.IOOptimalWidth, body.IOMinSize, body.Type,
+					body.Generation, body.StartOffset, body.DevGroup,
+					body.SeekSpeed, body.Bandwidth,
+					body.DevUUID,
+					body.FSUUID)
+			case btrfsitem.DevExtent:
+				fmt.Printf(""+
+					"\t\tdev extent chunk_tree %v\n"+
+					"\t\tchunk_objectid %v chunk_offset %d length %d\n"+
+					"\t\tchunk_tree_uuid %v\n",
+					body.ChunkTree, body.ChunkObjectID, body.ChunkOffset, body.Length,
+					body.ChunkTreeUUID)
+			//case btrfsitem.QGROUP_STATUS_KEY:
+			//	// TODO
+			//case btrfsitem.QGROUP_INFO_KEY:
+			//	// TODO
+			//case btrfsitem.QGROUP_LIMIT_KEY:
+			//	// TODO
+			case btrfsitem.UUIDMap:
+				fmt.Printf("\t\tsubvol_id %d\n", body.ObjID)
+			//case btrfsitem.STRING_ITEM_KEY:
+			//	// TODO
+			case btrfsitem.DevStats:
+				fmt.Printf("\t\tpersistent item objectid %v offset %v\n",
+					item.Head.Key.ObjectID.Format(item.Head.Key.ItemType), item.Head.Key.Offset)
+				switch item.Head.Key.ObjectID {
+				case btrfs.DEV_STATS_OBJECTID:
+					fmt.Printf("\t\tdevice stats\n")
+					fmt.Printf("\t\twrite_errs %v read_errs %v flush_errs %v corruption_errs %v generation %v\n",
+						body.Values[btrfsitem.DEV_STAT_WRITE_ERRS],
+						body.Values[btrfsitem.DEV_STAT_READ_ERRS],
+						body.Values[btrfsitem.DEV_STAT_FLUSH_ERRS],
+						body.Values[btrfsitem.DEV_STAT_CORRUPTION_ERRS],
+						body.Values[btrfsitem.DEV_STAT_GENERATION_ERRS])
+				default:
+					fmt.Printf("\t\tunknown persistent item objectid %v\n", item.Head.Key.ObjectID)
+				}
+			//case btrfsitem.TEMPORARY_ITEM_KEY:
+			//	// TODO
+			case btrfsitem.Empty:
+				switch item.Head.Key.ItemType {
+				case btrfsitem.ORPHAN_ITEM_KEY: // 48
+					fmt.Printf("\t\torphan item\n")
+				case btrfsitem.TREE_BLOCK_REF_KEY: // 176
+					fmt.Printf("\t\ttree block backref\n")
+				case btrfsitem.SHARED_BLOCK_REF_KEY: // 182
+					fmt.Printf("\t\tshared block backref\n")
+				case btrfsitem.FREE_SPACE_EXTENT_KEY: // 199
+					fmt.Printf("\t\tfree space extent\n")
+				case btrfsitem.QGROUP_RELATION_KEY: // 246
+					// do nothing
+				//case btrfsitem.EXTENT_REF_V0_KEY:
+				//	fmt.Printf("\t\textent ref v0 (deprecated)\n")
+				//case btrfsitem.CSUM_ITEM_KEY:
+				//	fmt.Printf("\t\tcsum item\n")
+				default:
+					fmt.Printf("\t\t(error) unhandled empty item type: %v\n", item.Head.Key.ItemType)
+				}
+			case btrfsitem.Error:
+				fmt.Printf("\t\t(error) error item: %v\n", body.Err)
+			default:
+				fmt.Printf("\t\t(error) unhandled item type: %T\n", body)
+			}
+			return nil
+		},
+	})
+}
+
+// printHeaderInfo mimics btrfs-progs kernel-shared/print-tree.c:print_header_info()
+func printHeaderInfo(node btrfs.Node) {
+	var typename string
+	if node.Head.Level > 0 { // internal node
+		typename = "node"
+		fmt.Printf("node %v level %v items %v free space %v",
+			node.Head.Addr,
+			node.Head.Level,
+			node.Head.NumItems,
+			node.MaxItems()-node.Head.NumItems)
+	} else { // leaf node
+		typename = "leaf"
+		fmt.Printf("leaf %d items %v free space %v",
+			node.Head.Addr,
+			node.Head.NumItems,
+			node.LeafFreeSpace())
+	}
+	fmt.Printf(" generation %v owner %v\n",
+		node.Head.Generation,
+		node.Head.Owner)
+
+	fmt.Printf("%v %d flags %v backref revision %v\n",
+		typename,
+		node.Head.Addr,
+		node.Head.Flags,
+		node.Head.BackrefRev)
+
+	fmt.Printf("checksum stored %v\n", node.Head.Checksum.Fmt(node.ChecksumType))
+	if calcSum, err := node.CalculateChecksum(); err != nil {
+		fmt.Printf("checksum calced %v\n", err)
+	} else {
+		fmt.Printf("checksum calced %v\n", calcSum.Fmt(node.ChecksumType))
+	}
+
+	fmt.Printf("fs uuid %v\n", node.Head.MetadataUUID)
+	fmt.Printf("chunk uuid %v\n", node.Head.ChunkTreeUUID)
+}
+
+// printExtentInlineRefs mimics part of btrfs-progs kernel-shared/print-tree.c:print_extent_item()
+func printExtentInlineRefs(refs []btrfsitem.ExtentInlineRef) {
+	for _, ref := range refs {
+		switch subitem := ref.Body.(type) {
+		case nil:
+			switch ref.Type {
+			case btrfsitem.TREE_BLOCK_REF_KEY:
+				fmt.Printf("\t\ttree block backref root %v\n",
+					btrfs.ObjID(ref.Offset))
+			case btrfsitem.SHARED_BLOCK_REF_KEY:
+				fmt.Printf("\t\tshared block backref parent %v\n",
+					ref.Offset)
+			default:
+				fmt.Printf("\t\t(error) unexpected empty sub-item type: %v\n", ref.Type)
+			}
+		case btrfsitem.ExtentDataRef:
+			fmt.Printf("\t\textent data backref root %v objectid %v offset %v count %v\n",
+				subitem.Root, subitem.ObjectID, subitem.Offset, subitem.Count)
+		case btrfsitem.SharedDataRef:
+			fmt.Printf("\t\tshared data backref parent %v count %v\n",
+				ref.Offset, subitem.Count)
+		default:
+			fmt.Printf("\t\t(error) unexpected sub-item type: %T\n", subitem)
+		}
+	}
+}
+
+// mimics print-tree.c:btrfs_print_key()
+func FmtKey(key btrfs.Key) string {
+	var out strings.Builder
+	fmt.Fprintf(&out, "key (%v %v", key.ObjectID.Format(key.ItemType), key.ItemType)
+	switch key.ItemType {
+	case btrfsitem.QGROUP_RELATION_KEY: //TODO, btrfsitem.QGROUP_INFO_KEY, btrfsitem.QGROUP_LIMIT_KEY:
+		panic("not implemented")
+	case btrfsitem.UUID_SUBVOL_KEY, btrfsitem.UUID_RECEIVED_SUBVOL_KEY:
+		fmt.Fprintf(&out, " %#08x)", key.Offset)
+	case btrfsitem.ROOT_ITEM_KEY:
+		fmt.Fprintf(&out, " %v)", btrfs.ObjID(key.Offset))
+	default:
+		if key.Offset == util.MaxUint64pp-1 {
+			fmt.Fprintf(&out, " -1)")
+		} else {
+			fmt.Fprintf(&out, " %v)", key.Offset)
+		}
+	}
+	return out.String()
+}
+
+func fmtTime(t btrfs.Time) string {
+	return fmt.Sprintf("%v.%v (%v)",
+		t.Sec, t.NSec, t.ToStd().Format("2006-01-02 15:04:05"))
+}
diff --git a/lib/btrfsmisc/walk.go b/lib/btrfsmisc/walk.go
new file mode 100644
index 0000000..ba0444f
--- /dev/null
+++ b/lib/btrfsmisc/walk.go
@@ -0,0 +1,115 @@
+package btrfsmisc
+
+import (
+	"fmt"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type WalkErr struct {
+	TreeName string
+	Path     btrfs.TreePath
+	Err      error
+}
+
+func (e WalkErr) Unwrap() error { return e.Err }
+
+func (e WalkErr) Error() string {
+	if len(e.Path) == 0 {
+		return fmt.Sprintf("%v: %v", e.TreeName, e.Err)
+	}
+	return fmt.Sprintf("%v: %v: %v", e.TreeName, e.Path, e.Err)
+}
+
+type WalkAllTreesHandler struct {
+	Err func(error)
+	// Callbacks for entire trees
+	PreTree  func(name string, id btrfs.ObjID)
+	PostTree func(name string, id btrfs.ObjID)
+	// Callbacks for nodes or smaller
+	UnsafeNodes bool
+	btrfs.TreeWalkHandler
+}
+
+// WalkAllTrees walks all trees in a *btrfs.FS.  Rather than returning
+// an error, it calls errCb each time an error is encountered.  The
+// error will always be of type WalkErr.
+func WalkAllTrees(fs *btrfs.FS, cbs WalkAllTreesHandler) {
+	var treeName string
+	handleErr := func(path btrfs.TreePath, err error) {
+		cbs.Err(WalkErr{
+			TreeName: treeName,
+			Path:     path,
+			Err:      err,
+		})
+	}
+
+	trees := []struct {
+		Name string
+		ID   btrfs.ObjID
+	}{
+		{
+			Name: "root tree",
+			ID:   btrfs.ROOT_TREE_OBJECTID,
+		},
+		{
+			Name: "chunk tree",
+			ID:   btrfs.CHUNK_TREE_OBJECTID,
+		},
+		{
+			Name: "log tree",
+			ID:   btrfs.TREE_LOG_OBJECTID,
+		},
+		{
+			Name: "block group tree",
+			ID:   btrfs.BLOCK_GROUP_TREE_OBJECTID,
+		},
+	}
+	origItem := cbs.Item
+	cbs.Item = func(path btrfs.TreePath, item btrfs.Item) error {
+		if item.Head.Key.ItemType == btrfsitem.ROOT_ITEM_KEY {
+			trees = append(trees, struct {
+				Name string
+				ID   btrfs.ObjID
+			}{
+				Name: fmt.Sprintf("tree %v (via %v %v)",
+					item.Head.Key.ObjectID.Format(0), treeName, path),
+				ID: item.Head.Key.ObjectID,
+			})
+		}
+		if origItem != nil {
+			return origItem(path, item)
+		}
+		return nil
+	}
+
+	if !cbs.UnsafeNodes {
+		origNode := cbs.Node
+		cbs.Node = func(path btrfs.TreePath, node *util.Ref[btrfsvol.LogicalAddr, btrfs.Node], err error) error {
+			if err != nil {
+				handleErr(path, err)
+			}
+			if node != nil && origNode != nil {
+				return origNode(path, node, nil)
+			}
+			return nil
+		}
+	}
+
+	for i := 0; i < len(trees); i++ {
+		tree := trees[i]
+		treeName = tree.Name
+		if cbs.PreTree != nil {
+			cbs.PreTree(treeName, tree.ID)
+		}
+		if err := fs.TreeWalk(tree.ID, cbs.TreeWalkHandler); err != nil {
+			handleErr(nil, err)
+		}
+		if cbs.PostTree != nil {
+			cbs.PostTree(treeName, tree.ID)
+		}
+	}
+}
diff --git a/lib/linux/stat.go b/lib/linux/stat.go
new file mode 100644
index 0000000..c4d4ad9
--- /dev/null
+++ b/lib/linux/stat.go
@@ -0,0 +1,95 @@
+// Based on https://github.com/datawire/ocibuild/blob/master/pkg/python/stat.go
+
+package linux
+
+type StatMode uint32
+
+//nolint:deadcode,varcheck // not all of these modes will be used
+const (
+	// 16 bits = 5⅓ octal characters
+
+	ModeFmt StatMode = 0o17_0000 // mask for the type bits
+
+	_ModeFmtUnused000  StatMode = 0o00_0000
+	ModeFmtNamedPipe   StatMode = 0o01_0000 // type: named pipe (FIFO)
+	ModeFmtCharDevice  StatMode = 0o02_0000 // type: character device
+	_ModeFmtUnused003  StatMode = 0o03_0000
+	ModeFmtDir         StatMode = 0o04_0000 // type: directory
+	_ModeFmtUnused005  StatMode = 0o05_0000
+	ModeFmtBlockDevice StatMode = 0o06_0000 // type: block device
+	_ModeFmtUnused007  StatMode = 0o07_0000
+	ModeFmtRegular     StatMode = 0o10_0000 // type: regular file
+	_ModeFmtUnused011  StatMode = 0o11_0000
+	ModeFmtSymlink     StatMode = 0o12_0000 // type: symbolic link
+	_ModeFmtUnused013  StatMode = 0o13_0000
+	ModeFmtSocket      StatMode = 0o14_0000 // type: socket file
+	_ModeFmtUnused015  StatMode = 0o15_0000
+	_ModeFmtUnused016  StatMode = 0o16_0000
+	_ModeFmtUnused017  StatMode = 0o17_0000
+
+	ModePerm StatMode = 0o00_7777 // mask for permission bits
+
+	ModePermSetUID StatMode = 0o00_4000 // permission: set user id
+	ModePermSetGID StatMode = 0o00_2000 // permission: set group ID
+	ModePermSticky StatMode = 0o00_1000 // permission: sticky bit
+
+	ModePermUsrR StatMode = 0o00_0400 // permission: user: read
+	ModePermUsrW StatMode = 0o00_0200 // permission: user: write
+	ModePermUsrX StatMode = 0o00_0100 // permission: user: execute
+
+	ModePermGrpR StatMode = 0o00_0040 // permission: group: read
+	ModePermGrpW StatMode = 0o00_0020 // permission: group: write
+	ModePermGrpX StatMode = 0o00_0010 // permission: group: execute
+
+	ModePermOthR StatMode = 0o00_0004 // permission: other: read
+	ModePermOthW StatMode = 0o00_0002 // permission: other: write
+	ModePermOthX StatMode = 0o00_0001 // permission: other: execute
+)
+
+// IsDir reports whether mode describes a directory.
+//
+// That is, it tests that the ModeFmt bits are set to ModeFmtDir.
+func (mode StatMode) IsDir() bool {
+	return mode&ModeFmt == ModeFmtDir
+}
+
+// IsRegular reports whether m describes a regular file.
+//
+// That is, it tests that the ModeFmt bits are set to ModeFmtRegular.
+func (mode StatMode) IsRegular() bool {
+	return mode&ModeFmt == ModeFmtRegular
+}
+
+// String returns a textual representation of the mode.
+//
+// This is the format that POSIX specifies for showing the mode in the
+// output of the `ls -l` command.  POSIX does not specify the
+// character to use to indicate a ModeFmtSocket file; this method uses
+// 's' (GNU `ls` behavior; though POSIX notes that many
+// implementations use '=' for sockets).
+func (mode StatMode) String() string {
+	buf := [10]byte{
+		// type: This string is easy; it directly pairs with
+		// the above ModeFmtXXX list above; the character in
+		// the string left-to-right corresponds with the
+		// constant in the list top-to-bottom.
+		"?pc?d?b?-?l?s???"[mode>>12],
+
+		// owner
+		"-r"[(mode>>8)&0o1],
+		"-w"[(mode>>7)&0o1],
+		"-xSs"[((mode>>6)&0o1)|((mode>>10)&0o2)],
+
+		// group
+		"-r"[(mode>>5)&0o1],
+		"-w"[(mode>>4)&0o1],
+		"-xSs"[((mode>>3)&0o1)|((mode>>9)&0o2)],
+
+		// group
+		"-r"[(mode>>2)&0o1],
+		"-w"[(mode>>1)&0o1],
+		"-xTt"[((mode>>0)&0o1)|((mode>>8)&0o2)],
+	}
+
+	return string(buf[:])
+}
diff --git a/lib/rbtree/print_test.go b/lib/rbtree/print_test.go
new file mode 100644
index 0000000..3e37cf2
--- /dev/null
+++ b/lib/rbtree/print_test.go
@@ -0,0 +1,41 @@
+package rbtree
+
+import (
+	"fmt"
+	"io"
+	"strings"
+)
+
+func (t *Tree[K, V]) ASCIIArt() string {
+	var out strings.Builder
+	t.root.asciiArt(&out, "", "", "")
+	return out.String()
+}
+
+func (node *Node[V]) String() string {
+	switch {
+	case node == nil:
+		return "nil"
+	case node.Color == Red:
+		return fmt.Sprintf("R(%v)", node.Value)
+	default:
+		return fmt.Sprintf("B(%v)", node.Value)
+	}
+}
+
+func (node *Node[V]) asciiArt(w io.Writer, u, m, l string) {
+	if node == nil {
+		fmt.Fprintf(w, "%snil\n", m)
+		return
+	}
+
+	node.Right.asciiArt(w, u+"     ", u+"  ,--", u+"  |  ")
+
+	if node.Color == Red {
+		fmt.Fprintf(w, "%s%v\n", m, node)
+	} else {
+		fmt.Fprintf(w, "%s%v\n", m, node)
+	}
+
+	node.Left.asciiArt(w, l+"  |  ", l+"  `--", l+"     ")
+}
diff --git a/lib/rbtree/rbtree.go b/lib/rbtree/rbtree.go
new file mode 100644
index 0000000..7927307
--- /dev/null
+++ b/lib/rbtree/rbtree.go
@@ -0,0 +1,477 @@
+package rbtree
+
+import (
+	"fmt"
+
+	"golang.org/x/exp/constraints"
+)
+
+type Color bool
+
+const (
+	Black = Color(false)
+	Red   = Color(true)
+)
+
+type Node[V any] struct {
+	Parent, Left, Right *Node[V]
+
+	Color Color
+
+	Value V
+}
+
+func (node *Node[V]) getColor() Color {
+	if node == nil {
+		return Black
+	}
+	return node.Color
+}
+
+type Tree[K constraints.Ordered, V any] struct {
+	KeyFn func(V) K
+	root  *Node[V]
+}
+
+func (t *Tree[K, V]) Walk(fn func(*Node[V]) error) error {
+	return t.root.walk(fn)
+}
+
+func (node *Node[V]) walk(fn func(*Node[V]) error) error {
+	if node == nil {
+		return nil
+	}
+	if err := node.Left.walk(fn); err != nil {
+		return err
+	}
+	if err := fn(node); err != nil {
+		return err
+	}
+	if err := node.Right.walk(fn); err != nil {
+		return err
+	}
+	return nil
+}
+
+// Search the tree for a value that satisfied the given callbackk
+// function.  A return value of 0 means to to return this value; <0
+// means to go left on the tree (the value is too high), >0 means to
+// go right on th etree (the value is too low).
+//
+//             +-----+
+//             | v=8 | == 0 : this is it
+//             +-----+
+//            /       \
+//           /         \
+//     <0 : go left   >0 : go right
+//         /             \
+//      +---+          +---+
+//      | 7 |          | 9 |
+//      +---+          +---+
+//
+// Returns nil if no such value is found.
+//
+// Search is good for advanced lookup, like when a range of values is
+// acceptable.  For simple exact-value lookup, use Lookup.
+func (t *Tree[K, V]) Search(fn func(V) int) *Node[V] {
+	ret, _ := t.root.search(fn)
+	return ret
+}
+
+func (node *Node[V]) search(fn func(V) int) (exact, nearest *Node[V]) {
+	var prev *Node[V]
+	for {
+		if node == nil {
+			return nil, prev
+		}
+		direction := fn(node.Value)
+		prev = node
+		switch {
+		case direction < 0:
+			node = node.Left
+		case direction == 0:
+			return node, nil
+		case direction > 0:
+			node = node.Right
+		}
+	}
+}
+
+func (t *Tree[K, V]) exactKey(key K) func(V) int {
+	return func(val V) int {
+		valKey := t.KeyFn(val)
+		switch {
+		case key < valKey:
+			return -1
+		case key > valKey:
+			return 1
+		default: // key == valKey:
+			return 0
+		}
+	}
+}
+
+// Lookup looks up the value for an exact key.  If no such value
+// exists, nil is returned.
+func (t *Tree[K, V]) Lookup(key K) *Node[V] {
+	return t.Search(t.exactKey(key))
+}
+
+// Min returns the minimum value stored in the tree, or nil if the
+// tree is empty.
+func (t *Tree[K, V]) Min() *Node[V] {
+	return t.root.min()
+}
+
+func (node *Node[V]) min() *Node[V] {
+	if node == nil {
+		return nil
+	}
+	for {
+		if node.Left == nil {
+			return node
+		}
+		node = node.Left
+	}
+}
+
+// Max returns the maximum value stored in the tree, or nil if the
+// tree is empty.
+func (t *Tree[K, V]) Max() *Node[V] {
+	return t.root.max()
+}
+
+func (node *Node[V]) max() *Node[V] {
+	if node == nil {
+		return nil
+	}
+	for {
+		if node.Right == nil {
+			return node
+		}
+		node = node.Right
+	}
+}
+
+func (t *Tree[K, V]) Next(cur *Node[V]) *Node[V] {
+	return cur.next()
+}
+
+func (cur *Node[V]) next() *Node[V] {
+	if cur.Right != nil {
+		return cur.Right.min()
+	}
+	child, parent := cur, cur.Parent
+	for parent != nil && child == parent.Right {
+		child, parent = parent, parent.Parent
+	}
+	return parent
+}
+
+func (t *Tree[K, V]) Prev(cur *Node[V]) *Node[V] {
+	return cur.prev()
+}
+
+func (cur *Node[V]) prev() *Node[V] {
+	if cur.Left != nil {
+		return cur.Left.max()
+	}
+	child, parent := cur, cur.Parent
+	for parent != nil && child == parent.Left {
+		child, parent = parent, parent.Parent
+	}
+	return parent
+}
+
+func (t *Tree[K, V]) parentChild(node *Node[V]) **Node[V] {
+	switch {
+	case node.Parent == nil:
+		return &t.root
+	case node.Parent.Left == node:
+		return &node.Parent.Left
+	case node.Parent.Right == node:
+		return &node.Parent.Right
+	default:
+		panic(fmt.Errorf("node %p is not a child of its parent %p", node, node.Parent))
+	}
+}
+
+func (t *Tree[K, V]) leftRotate(x *Node[V]) {
+	//        p                        p
+	//        |                        |
+	//      +---+                    +---+
+	//      | x |                    | y |
+	//      +---+                    +---+
+	//     /     \         =>       /     \
+	//    a    +---+              +---+    c
+	//         | y |              | x |
+	//         +---+              +---+
+	//        /     \            /     \
+	//       b       c          a       b
+
+	// Define 'p', 'x', 'y', and 'b' per the above diagram.
+	p := x.Parent
+	pChild := t.parentChild(x)
+	y := x.Right
+	b := y.Left
+
+	// Move things around
+
+	y.Parent = p
+	*pChild = y
+
+	x.Parent = y
+	y.Left = x
+
+	if b != nil {
+		b.Parent = x
+	}
+	x.Right = b
+}
+
+func (t *Tree[K, V]) rightRotate(y *Node[V]) {
+	//           |                |
+	//         +---+            +---+
+	//         | y |            | x |
+	//         +---+            +---+
+	//        /     \    =>    /     \
+	//      +---+    c        a    +---+
+	//      | x |                  | y |
+	//      +---+                  +---+
+	//     /     \                /     \
+	//    a       b              b       c
+
+	// Define 'p', 'x', 'y', and 'b' per the above diagram.
+	p := y.Parent
+	pChild := t.parentChild(y)
+	x := y.Left
+	b := x.Right
+
+	// Move things around
+
+	x.Parent = p
+	*pChild = x
+
+	y.Parent = x
+	x.Right = y
+
+	if b != nil {
+		b.Parent = y
+	}
+	y.Left = b
+}
+
+func (t *Tree[K, V]) Insert(val V) {
+	// Naive-insert
+
+	key := t.KeyFn(val)
+	exact, parent := t.root.search(t.exactKey(key))
+	if exact != nil {
+		exact.Value = val
+		return
+	}
+
+	node := &Node[V]{
+		Color:  Red,
+		Parent: parent,
+		Value:  val,
+	}
+	if parent == nil {
+		t.root = node
+	} else if key < t.KeyFn(parent.Value) {
+		parent.Left = node
+	} else {
+		parent.Right = node
+	}
+
+	// Re-balance
+
+	for node.Parent.getColor() == Red {
+		if node.Parent == node.Parent.Parent.Left {
+			uncle := node.Parent.Parent.Right
+			if uncle.getColor() == Red {
+				node.Parent.Color = Black
+				uncle.Color = Black
+				node.Parent.Parent.Color = Red
+				node = node.Parent.Parent
+			} else {
+				if node == node.Parent.Right {
+					node = node.Parent
+					t.leftRotate(node)
+				}
+				node.Parent.Color = Black
+				node.Parent.Parent.Color = Red
+				t.rightRotate(node.Parent.Parent)
+			}
+		} else {
+			uncle := node.Parent.Parent.Left
+			if uncle.getColor() == Red {
+				node.Parent.Color = Black
+				uncle.Color = Black
+				node.Parent.Parent.Color = Red
+				node = node.Parent.Parent
+			} else {
+				if node == node.Parent.Left {
+					node = node.Parent
+					t.rightRotate(node)
+				}
+				node.Parent.Color = Black
+				node.Parent.Parent.Color = Red
+				t.leftRotate(node.Parent.Parent)
+			}
+		}
+	}
+	t.root.Color = Black
+}
+
+func (t *Tree[K, V]) transplant(old, new *Node[V]) {
+	*t.parentChild(old) = new
+	if new != nil {
+		new.Parent = old.Parent
+	}
+}
+
+func (t *Tree[K, V]) Delete(key K) {
+	nodeToDelete := t.Lookup(key)
+	if nodeToDelete == nil {
+		return
+	}
+
+	var nodeToRebalance *Node[V]
+	var nodeToRebalanceParent *Node[V] // in case 'nodeToRebalance' is nil, which it can be
+	needsRebalance := nodeToDelete.Color == Black
+
+	switch {
+	case nodeToDelete.Left == nil:
+		nodeToRebalance = nodeToDelete.Right
+		nodeToRebalanceParent = nodeToDelete.Parent
+		t.transplant(nodeToDelete, nodeToDelete.Right)
+	case nodeToDelete.Right == nil:
+		nodeToRebalance = nodeToDelete.Left
+		nodeToRebalanceParent = nodeToDelete.Parent
+		t.transplant(nodeToDelete, nodeToDelete.Left)
+	default:
+		// The node being deleted has a child on both sides,
+		// so we've go to reshuffle the parents a bit to make
+		// room for those children.
+		next := nodeToDelete.next()
+		if next.Parent == nodeToDelete {
+			//         p                  p
+			//         |                  |
+			//      +-----+            +-----+
+			//      | ntd |            | nxt |
+			//      +-----+            +-----+
+			//      /     \       =>   /     \
+			//     a     +-----+      a      b
+			//           | nxt |
+			//           +-----+
+			//            /   \
+			//          nil   b
+			nodeToRebalance = next.Right
+			nodeToRebalanceParent = next
+
+			*t.parentChild(nodeToDelete) = next
+			next.Parent = nodeToDelete.Parent
+
+			next.Left = nodeToDelete.Left
+			next.Left.Parent = next
+		} else {
+			//         p                 p
+			//         |                 |
+			//      +-----+           +-----+
+			//      | ntd |           | nxt |
+			//      +-----+           +-----+
+			//      /     \           /     \
+			//     a       x         a       x
+			//            / \    =>         / \
+			//           y   z             y   z
+			//          / \               / \
+			//    +-----+  c             b   c
+			//    | nxt |
+			//    +-----+
+			//    /     \
+			//  nil     b
+			y := next.Parent
+			b := next.Right
+			nodeToRebalance = b
+			nodeToRebalanceParent = y
+
+			*t.parentChild(nodeToDelete) = next
+			next.Parent = nodeToDelete.Parent
+
+			next.Left = nodeToDelete.Left
+			next.Left.Parent = next
+
+			next.Right = nodeToDelete.Right
+			next.Right.Parent = next
+
+			y.Left = b
+			if b != nil {
+				b.Parent = y
+			}
+		}
+
+		// idk
+		needsRebalance = next.Color == Black
+		next.Color = nodeToDelete.Color
+	}
+
+	if needsRebalance {
+		node := nodeToRebalance
+		nodeParent := nodeToRebalanceParent
+		for node != t.root && node.getColor() == Black {
+			if node == nodeParent.Left {
+				sibling := nodeParent.Right
+				if sibling.getColor() == Red {
+					sibling.Color = Black
+					nodeParent.Color = Red
+					t.leftRotate(nodeParent)
+					sibling = nodeParent.Right
+				}
+				if sibling.Left.getColor() == Black && sibling.Right.getColor() == Black {
+					sibling.Color = Red
+					node, nodeParent = nodeParent, nodeParent.Parent
+				} else {
+					if sibling.Right.getColor() == Black {
+						sibling.Left.Color = Black
+						sibling.Color = Red
+						t.rightRotate(sibling)
+						sibling = nodeParent.Right
+					}
+					sibling.Color = nodeParent.Color
+					nodeParent.Color = Black
+					sibling.Right.Color = Black
+					t.leftRotate(nodeParent)
+					node, nodeParent = t.root, nil
+				}
+			} else {
+				sibling := nodeParent.Left
+				if sibling.getColor() == Red {
+					sibling.Color = Black
+					nodeParent.Color = Red
+					t.rightRotate(nodeParent)
+					sibling = nodeParent.Left
+				}
+				if sibling.Right.getColor() == Black && sibling.Left.getColor() == Black {
+					sibling.Color = Red
+					node, nodeParent = nodeParent, nodeParent.Parent
+				} else {
+					if sibling.Left.getColor() == Black {
+						sibling.Right.Color = Black
+						sibling.Color = Red
+						t.leftRotate(sibling)
+						sibling = nodeParent.Left
+					}
+					sibling.Color = nodeParent.Color
+					nodeParent.Color = Black
+					sibling.Left.Color = Black
+					t.rightRotate(nodeParent)
+					node, nodeParent = t.root, nil
+				}
+			}
+		}
+		if node != nil {
+			node.Color = Black
+		}
+	}
+}
diff --git a/lib/rbtree/rbtree_test.go b/lib/rbtree/rbtree_test.go
new file mode 100644
index 0000000..9b8e02c
--- /dev/null
+++ b/lib/rbtree/rbtree_test.go
@@ -0,0 +1,126 @@
+package rbtree
+
+import (
+	"sort"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+	"golang.org/x/exp/constraints"
+)
+
+func checkTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]struct{}, tree *Tree[K, V]) {
+	// 1. Every node is either red or black
+
+	// 2. The root is black.
+	require.Equal(t, Black, tree.root.getColor())
+
+	// 3. Every nil is black.
+
+	// 4. If a node is red, then both its children are black.
+	require.NoError(t, tree.Walk(func(node *Node[V]) error {
+		if node.getColor() == Red {
+			require.Equal(t, Black, node.Left.getColor())
+			require.Equal(t, Black, node.Right.getColor())
+		}
+		return nil
+	}))
+
+	// 5. For each node, all simple paths from the node to
+	//    descendent leaves contain the same number of black
+	//    nodes.
+	var walkCnt func(node *Node[V], cnt int, leafFn func(int))
+	walkCnt = func(node *Node[V], cnt int, leafFn func(int)) {
+		if node.getColor() == Black {
+			cnt++
+		}
+		if node == nil {
+			leafFn(cnt)
+			return
+		}
+		walkCnt(node.Left, cnt, leafFn)
+		walkCnt(node.Right, cnt, leafFn)
+	}
+	require.NoError(t, tree.Walk(func(node *Node[V]) error {
+		var cnts []int
+		walkCnt(node, 0, func(cnt int) {
+			cnts = append(cnts, cnt)
+		})
+		for i := range cnts {
+			if cnts[0] != cnts[i] {
+				require.Truef(t, false, "node %v: not all leafs have same black-count: %v", node.Value, cnts)
+				break
+			}
+		}
+		return nil
+	}))
+
+	// expected contents
+	expectedOrder := make([]K, 0, len(expectedSet))
+	for k := range expectedSet {
+		expectedOrder = append(expectedOrder, k)
+		node := tree.Lookup(k)
+		require.NotNil(t, tree, node)
+		require.Equal(t, k, tree.KeyFn(node.Value))
+	}
+	sort.Slice(expectedOrder, func(i, j int) bool {
+		return expectedOrder[i] < expectedOrder[j]
+	})
+	actOrder := make([]K, 0, len(expectedSet))
+	require.NoError(t, tree.Walk(func(node *Node[V]) error {
+		actOrder = append(actOrder, tree.KeyFn(node.Value))
+		return nil
+	}))
+	require.Equal(t, expectedOrder, actOrder)
+}
+
+func FuzzTree(f *testing.F) {
+	Ins := uint8(0b0100_0000)
+	Del := uint8(0)
+
+	f.Add([]uint8{})
+	f.Add([]uint8{Ins | 5, Del | 5})
+	f.Add([]uint8{Ins | 5, Del | 6})
+	f.Add([]uint8{Del | 6})
+
+	f.Add([]uint8{ // CLRS Figure 14.4
+		Ins | 1,
+		Ins | 2,
+		Ins | 5,
+		Ins | 7,
+		Ins | 8,
+		Ins | 11,
+		Ins | 14,
+		Ins | 15,
+
+		Ins | 4,
+	})
+
+	f.Fuzz(func(t *testing.T, dat []uint8) {
+		tree := &Tree[uint8, uint8]{
+			KeyFn: func(x uint8) uint8 { return x },
+		}
+		set := make(map[uint8]struct{})
+		checkTree(t, set, tree)
+		t.Logf("\n%s\n", tree.ASCIIArt())
+		for _, b := range dat {
+			ins := (b & 0b0100_0000) != 0
+			val := (b & 0b0011_1111)
+			if ins {
+				t.Logf("Insert(%v)", val)
+				tree.Insert(val)
+				set[val] = struct{}{}
+				t.Logf("\n%s\n", tree.ASCIIArt())
+				node := tree.Lookup(val)
+				require.NotNil(t, node)
+				require.Equal(t, val, node.Value)
+			} else {
+				t.Logf("Delete(%v)", val)
+				tree.Delete(val)
+				delete(set, val)
+				t.Logf("\n%s\n", tree.ASCIIArt())
+				require.Nil(t, tree.Lookup(val))
+			}
+			checkTree(t, set, tree)
+		}
+	})
+}
diff --git a/lib/rbtree/rbtree_util.go b/lib/rbtree/rbtree_util.go
new file mode 100644
index 0000000..252d8fe
--- /dev/null
+++ b/lib/rbtree/rbtree_util.go
@@ -0,0 +1,48 @@
+package rbtree
+
+import (
+	"reflect"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+// SearchRange is like Search, but returns all nodes that match the
+// function; assuming that they are contiguous.
+func (t *Tree[K, V]) SearchRange(fn func(V) int) []V {
+	middle := t.Search(fn)
+	if middle == nil {
+		return nil
+	}
+	ret := []V{middle.Value}
+	for node := t.Prev(middle); node != nil && fn(node.Value) == 0; node = t.Prev(node) {
+		ret = append(ret, node.Value)
+	}
+	util.ReverseSlice(ret)
+	for node := t.Next(middle); node != nil && fn(node.Value) == 0; node = t.Next(node) {
+		ret = append(ret, node.Value)
+	}
+	return ret
+}
+
+func (t *Tree[K, V]) Equal(u *Tree[K, V]) bool {
+	if (t == nil) != (u == nil) {
+		return false
+	}
+	if t == nil {
+		return true
+	}
+
+	var tSlice []V
+	_ = t.Walk(func(node *Node[V]) error {
+		tSlice = append(tSlice, node.Value)
+		return nil
+	})
+
+	var uSlice []V
+	_ = u.Walk(func(node *Node[V]) error {
+		uSlice = append(uSlice, node.Value)
+		return nil
+	})
+
+	return reflect.DeepEqual(tSlice, uSlice)
+}
diff --git a/lib/rbtree/testdata/fuzz/FuzzTree/be408ce7760bc8ced841300ea7e6bac1a1e9505b1535810083d18db95d86f489 b/lib/rbtree/testdata/fuzz/FuzzTree/be408ce7760bc8ced841300ea7e6bac1a1e9505b1535810083d18db95d86f489
new file mode 100644
index 0000000..40318c6
--- /dev/null
+++ b/lib/rbtree/testdata/fuzz/FuzzTree/be408ce7760bc8ced841300ea7e6bac1a1e9505b1535810083d18db95d86f489
@@ -0,0 +1,2 @@
+go test fuzz v1
+[]byte("aAm0BCrb0x00!0000000000000")
diff --git a/lib/rbtree/testdata/fuzz/FuzzTree/f9e6421dacf921f7bb25d402bffbfdce114baad0b1c8b9a9189b5a97fda27e41 b/lib/rbtree/testdata/fuzz/FuzzTree/f9e6421dacf921f7bb25d402bffbfdce114baad0b1c8b9a9189b5a97fda27e41
new file mode 100644
index 0000000..238e44f
--- /dev/null
+++ b/lib/rbtree/testdata/fuzz/FuzzTree/f9e6421dacf921f7bb25d402bffbfdce114baad0b1c8b9a9189b5a97fda27e41
@@ -0,0 +1,2 @@
+go test fuzz v1
+[]byte("YZAB\x990")
diff --git a/lib/util/bitfield.go b/lib/util/bitfield.go
new file mode 100644
index 0000000..23da17a
--- /dev/null
+++ b/lib/util/bitfield.go
@@ -0,0 +1,50 @@
+package util
+
+import (
+	"fmt"
+	"strings"
+)
+
+type BitfieldFormat uint8
+
+const (
+	HexNone = BitfieldFormat(iota)
+	HexLower
+	HexUpper
+)
+
+func BitfieldString[T ~uint8 | ~uint16 | ~uint32 | ~uint64](bitfield T, bitnames []string, cfg BitfieldFormat) string {
+	var out strings.Builder
+	switch cfg {
+	case HexNone:
+		// do nothing
+	case HexLower:
+		fmt.Fprintf(&out, "0x%0x(", uint64(bitfield))
+	case HexUpper:
+		fmt.Fprintf(&out, "0x%0X(", uint64(bitfield))
+	}
+	if bitfield == 0 {
+		out.WriteString("none")
+	} else {
+		rest := bitfield
+		first := true
+		for i := 0; rest != 0; i++ {
+			if rest&(1<<i) != 0 {
+				if !first {
+					out.WriteRune('|')
+				}
+				if i < len(bitnames) {
+					out.WriteString(bitnames[i])
+				} else {
+					fmt.Fprintf(&out, "(1<<%v)", i)
+				}
+				first = false
+			}
+			rest &^= 1 << i
+		}
+	}
+	if cfg != HexNone {
+		out.WriteRune(')')
+	}
+	return out.String()
+}
diff --git a/lib/util/fmt.go b/lib/util/fmt.go
new file mode 100644
index 0000000..af7404c
--- /dev/null
+++ b/lib/util/fmt.go
@@ -0,0 +1,67 @@
+package util
+
+import (
+	"fmt"
+	"strings"
+)
+
+// FmtStateString returns the fmt.Printf string that produced a given
+// fmt.State and verb.
+func FmtStateString(st fmt.State, verb rune) string {
+	var ret strings.Builder
+	ret.WriteByte('%')
+	for _, flag := range []int{'-', '+', '#', ' ', '0'} {
+		if st.Flag(flag) {
+			ret.WriteByte(byte(flag))
+		}
+	}
+	if width, ok := st.Width(); ok {
+		fmt.Fprintf(&ret, "%v", width)
+	}
+	if prec, ok := st.Precision(); ok {
+		if prec == 0 {
+			ret.WriteByte('.')
+		} else {
+			fmt.Fprintf(&ret, ".%v", prec)
+		}
+	}
+	ret.WriteRune(verb)
+	return ret.String()
+}
+
+// FormatByteArrayStringer is function for helping to implement
+// fmt.Formatter for []byte or [n]byte types that have a custom string
+// representation.  Use it like:
+//
+//     type MyType [16]byte
+//
+//     func (val MyType) String() string {
+//         …
+//     }
+//
+//     func (val MyType) Format(f fmt.State, verb rune) {
+//         util.FormatByteArrayStringer(val, val[:], f, verb)
+//     }
+func FormatByteArrayStringer(
+	obj interface {
+		fmt.Stringer
+		fmt.Formatter
+	},
+	objBytes []byte,
+	f fmt.State, verb rune) {
+	switch verb {
+	case 'v':
+		if !f.Flag('#') {
+			FormatByteArrayStringer(obj, objBytes, f, 's') // as a string
+		} else {
+			byteStr := fmt.Sprintf("%#v", objBytes)
+			objType := fmt.Sprintf("%T", obj)
+			objStr := objType + strings.TrimPrefix(byteStr, "[]byte")
+			fmt.Fprintf(f, FmtStateString(f, 's'), objStr)
+		}
+	case 's', 'q': // string
+		fmt.Fprintf(f, FmtStateString(f, verb), obj.String())
+	default:
+		fmt.Fprintf(f, FmtStateString(f, verb), objBytes)
+	}
+}
diff --git a/lib/util/fmt_test.go b/lib/util/fmt_test.go
new file mode 100644
index 0000000..4251ecf
--- /dev/null
+++ b/lib/util/fmt_test.go
@@ -0,0 +1,99 @@
+package util_test
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type FmtState struct {
+	MWidth     int
+	MPrec      int
+	MFlagMinus bool
+	MFlagPlus  bool
+	MFlagSharp bool
+	MFlagSpace bool
+	MFlagZero  bool
+}
+
+func (st FmtState) Width() (int, bool) {
+	if st.MWidth < 1 {
+		return 0, false
+	}
+	return st.MWidth, true
+}
+
+func (st FmtState) Precision() (int, bool) {
+	if st.MPrec < 1 {
+		return 0, false
+	}
+	return st.MPrec, true
+}
+
+func (st FmtState) Flag(b int) bool {
+	switch b {
+	case '-':
+		return st.MFlagMinus
+	case '+':
+		return st.MFlagPlus
+	case '#':
+		return st.MFlagSharp
+	case ' ':
+		return st.MFlagSpace
+	case '0':
+		return st.MFlagZero
+	}
+	return false
+}
+
+func (st FmtState) Write([]byte) (int, error) {
+	panic("not implemented")
+}
+
+func (dst *FmtState) Format(src fmt.State, verb rune) {
+	if width, ok := src.Width(); ok {
+		dst.MWidth = width
+	}
+	if prec, ok := src.Precision(); ok {
+		dst.MPrec = prec
+	}
+	dst.MFlagMinus = src.Flag('-')
+	dst.MFlagPlus = src.Flag('+')
+	dst.MFlagSharp = src.Flag('#')
+	dst.MFlagSpace = src.Flag(' ')
+	dst.MFlagZero = src.Flag('0')
+}
+
+// letters only? No 'p', 'T', or 'w'.
+const verbs = "abcdefghijklmnoqrstuvxyzABCDEFGHIJKLMNOPQRSUVWXYZ"
+
+func FuzzFmtStateString(f *testing.F) {
+	f.Fuzz(func(t *testing.T,
+		width, prec uint8,
+		flagMinus, flagPlus, flagSharp, flagSpace, flagZero bool,
+		verbIdx uint8,
+	) {
+		if flagMinus {
+			flagZero = false
+		}
+		input := FmtState{
+			MWidth:     int(width),
+			MPrec:      int(prec),
+			MFlagMinus: flagMinus,
+			MFlagPlus:  flagPlus,
+			MFlagSharp: flagSharp,
+			MFlagSpace: flagSpace,
+			MFlagZero:  flagZero,
+		}
+		verb := rune(verbs[int(verbIdx)%len(verbs)])
+
+		t.Logf("(%#v, %c) => %q", input, verb, util.FmtStateString(input, verb))
+
+		var output FmtState
+		assert.Equal(t, "", fmt.Sprintf(util.FmtStateString(input, verb), &output))
+		assert.Equal(t, input, output)
+	})
+}
diff --git a/lib/util/generic.go b/lib/util/generic.go
new file mode 100644
index 0000000..6882724
--- /dev/null
+++ b/lib/util/generic.go
@@ -0,0 +1,122 @@
+package util
+
+import (
+	"sort"
+	"sync"
+
+	"golang.org/x/exp/constraints"
+)
+
+func InSlice[T comparable](needle T, haystack []T) bool {
+	for _, straw := range haystack {
+		if needle == straw {
+			return true
+		}
+	}
+	return false
+}
+
+func RemoveAllFromSlice[T comparable](haystack []T, needle T) []T {
+	for i, straw := range haystack {
+		if needle == straw {
+			return append(
+				haystack[:i],
+				RemoveAllFromSlice(haystack[i+1:], needle)...)
+		}
+	}
+	return haystack
+}
+
+func RemoveAllFromSliceFunc[T any](haystack []T, f func(T) bool) []T {
+	for i, straw := range haystack {
+		if f(straw) {
+			return append(
+				haystack[:i],
+				RemoveAllFromSliceFunc(haystack[i+1:], f)...)
+		}
+	}
+	return haystack
+}
+
+func ReverseSlice[T any](slice []T) {
+	for i := 0; i < len(slice)/2; i++ {
+		j := (len(slice) - 1) - i
+		slice[i], slice[j] = slice[j], slice[i]
+	}
+}
+
+func Max[T constraints.Ordered](a, b T) T {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func Min[T constraints.Ordered](a, b T) T {
+	if a < b {
+		return a
+	}
+	return b
+}
+
+func MapKeys[K comparable, V any](m map[K]V) []K {
+	ret := make([]K, 0, len(m))
+	for k := range m {
+		ret = append(ret, k)
+	}
+	return ret
+}
+
+func SortSlice[T constraints.Ordered](slice []T) {
+	sort.Slice(slice, func(i, j int) bool {
+		return slice[i] < slice[j]
+	})
+}
+
+func SortedMapKeys[K constraints.Ordered, V any](m map[K]V) []K {
+	ret := MapKeys(m)
+	SortSlice(ret)
+	return ret
+}
+
+func CmpUint[T constraints.Unsigned](a, b T) int {
+	switch {
+	case a < b:
+		return -1
+	case a == b:
+		return 0
+	default:
+		return 1
+	}
+}
+
+type SyncMap[K comparable, V any] struct {
+	inner sync.Map
+}
+
+func (m *SyncMap[K, V]) Delete(key K) { m.inner.Delete(key) }
+func (m *SyncMap[K, V]) Load(key K) (value V, ok bool) {
+	_value, ok := m.inner.Load(key)
+	if ok {
+		value = _value.(V)
+	}
+	return value, ok
+}
+func (m *SyncMap[K, V]) LoadAndDelete(key K) (value V, loaded bool) {
+	_value, ok := m.inner.LoadAndDelete(key)
+	if ok {
+		value = _value.(V)
+	}
+	return value, ok
+}
+func (m *SyncMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) {
+	_actual, loaded := m.inner.LoadOrStore(key, value)
+	actual = _actual.(V)
+	return actual, loaded
+}
+func (m *SyncMap[K, V]) Range(f func(key K, value V) bool) {
+	m.inner.Range(func(key, value any) bool {
+		return f(key.(K), value.(V))
+	})
+}
+func (m *SyncMap[K, V]) Store(key K, value V) { m.inner.Store(key, value) }
diff --git a/lib/util/int.go b/lib/util/int.go
new file mode 100644
index 0000000..fab553d
--- /dev/null
+++ b/lib/util/int.go
@@ -0,0 +1,3 @@
+package util
+
+const MaxUint64pp = 0x1_00000000_00000000
diff --git a/lib/util/lru.go b/lib/util/lru.go
new file mode 100644
index 0000000..2b62e69
--- /dev/null
+++ b/lib/util/lru.go
@@ -0,0 +1,73 @@
+package util
+
+import (
+	"sync"
+
+	lru "github.com/hashicorp/golang-lru"
+)
+
+type LRUCache[K comparable, V any] struct {
+	initOnce sync.Once
+	inner    *lru.ARCCache
+}
+
+func (c *LRUCache[K, V]) init() {
+	c.initOnce.Do(func() {
+		c.inner, _ = lru.NewARC(128)
+	})
+}
+
+func (c *LRUCache[K, V]) Add(key K, value V) {
+	c.init()
+	c.inner.Add(key, value)
+}
+func (c *LRUCache[K, V]) Contains(key K) bool {
+	c.init()
+	return c.inner.Contains(key)
+}
+func (c *LRUCache[K, V]) Get(key K) (value V, ok bool) {
+	c.init()
+	_value, ok := c.inner.Get(key)
+	if ok {
+		value = _value.(V)
+	}
+	return value, ok
+}
+func (c *LRUCache[K, V]) Keys() []K {
+	c.init()
+	untyped := c.inner.Keys()
+	typed := make([]K, len(untyped))
+	for i := range untyped {
+		typed[i] = untyped[i].(K)
+	}
+	return typed
+}
+func (c *LRUCache[K, V]) Len() int {
+	c.init()
+	return c.inner.Len()
+}
+func (c *LRUCache[K, V]) Peek(key K) (value V, ok bool) {
+	c.init()
+	_value, ok := c.inner.Peek(key)
+	if ok {
+		value = _value.(V)
+	}
+	return value, ok
+}
+func (c *LRUCache[K, V]) Purge() {
+	c.init()
+	c.inner.Purge()
+}
+func (c *LRUCache[K, V]) Remove(key K) {
+	c.init()
+	c.inner.Remove(key)
+}
+
+func (c *LRUCache[K, V]) GetOrElse(key K, fn func() V) V {
+	var value V
+	var ok bool
+	for value, ok = c.Get(key); !ok; value, ok = c.Get(key) {
+		c.Add(key, fn())
+	}
+	return value
+}
diff --git a/lib/util/ref.go b/lib/util/ref.go
new file mode 100644
index 0000000..1ac48c9
--- /dev/null
+++ b/lib/util/ref.go
@@ -0,0 +1,54 @@
+package util
+
+import (
+	"fmt"
+	"io"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/binstruct"
+)
+
+type File[A ~int64] interface {
+	Name() string
+	Size() (A, error)
+	ReadAt(p []byte, off A) (n int, err error)
+	WriteAt(p []byte, off A) (n int, err error)
+}
+
+var (
+	_ io.WriterAt = File[int64](nil)
+	_ io.ReaderAt = File[int64](nil)
+)
+
+type Ref[A ~int64, T any] struct {
+	File File[A]
+	Addr A
+	Data T
+}
+
+func (r *Ref[A, T]) Read() error {
+	size := binstruct.StaticSize(r.Data)
+	buf := make([]byte, size)
+	if _, err := r.File.ReadAt(buf, r.Addr); err != nil {
+		return err
+	}
+	n, err := binstruct.Unmarshal(buf, &r.Data)
+	if err != nil {
+		return err
+	}
+	if n != size {
+		return fmt.Errorf("util.Ref[%T].Read: left over data: read %v bytes but only consumed %v",
+			r.Data, size, n)
+	}
+	return nil
+}
+
+func (r *Ref[A, T]) Write() error {
+	buf, err := binstruct.Marshal(r.Data)
+	if err != nil {
+		return err
+	}
+	if _, err = r.File.WriteAt(buf, r.Addr); err != nil {
+		return err
+	}
+	return nil
+}
diff --git a/lib/util/uuid.go b/lib/util/uuid.go
new file mode 100644
index 0000000..3b4cbaf
--- /dev/null
+++ b/lib/util/uuid.go
@@ -0,0 +1,72 @@
+package util
+
+import (
+	"encoding/hex"
+	"fmt"
+	"strings"
+)
+
+type UUID [16]byte
+
+func (uuid UUID) String() string {
+	str := hex.EncodeToString(uuid[:])
+	return strings.Join([]string{
+		str[:8],
+		str[8:12],
+		str[12:16],
+		str[16:20],
+		str[20:32],
+	}, "-")
+}
+
+func (a UUID) Cmp(b UUID) int {
+	for i := range a {
+		if d := int(a[i]) - int(b[i]); d != 0 {
+			return d
+		}
+	}
+	return 0
+}
+
+func (uuid UUID) Format(f fmt.State, verb rune) {
+	FormatByteArrayStringer(uuid, uuid[:], f, verb)
+}
+
+func ParseUUID(str string) (UUID, error) {
+	var ret UUID
+	j := 0
+	for i := 0; i < len(str); i++ {
+		if j >= len(ret)*2 {
+			return UUID{}, fmt.Errorf("too long to be a UUID: %q|%q", str[:i], str[i:])
+		}
+		c := str[i]
+		var v byte
+		switch {
+		case '0' <= c && c <= '9':
+			v = c - '0'
+		case 'a' <= c && c <= 'f':
+			v = c - 'a' + 10
+		case 'A' <= c && c <= 'F':
+			v = c - 'A' + 10
+		case c == '-':
+			continue
+		default:
+			return UUID{}, fmt.Errorf("illegal byte in UUID: %q|%q|%q", str[:i], str[i:i+1], str[i+1:])
+		}
+		if j%2 == 0 {
+			ret[j/2] = v << 4
+		} else {
+			ret[j/2] = (ret[j/2] & 0xf0) | (v & 0x0f)
+		}
+		j++
+	}
+	return ret, nil
+}
+
+func MustParseUUID(str string) UUID {
+	ret, err := ParseUUID(str)
+	if err != nil {
+		panic(err)
+	}
+	return ret
+}
diff --git a/lib/util/uuid_test.go b/lib/util/uuid_test.go
new file mode 100644
index 0000000..7e0e07a
--- /dev/null
+++ b/lib/util/uuid_test.go
@@ -0,0 +1,63 @@
+package util_test
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+func TestParseUUID(t *testing.T) {
+	t.Parallel()
+	type TestCase struct {
+		Input     string
+		OutputVal util.UUID
+		OutputErr string
+	}
+	testcases := map[string]TestCase{
+		"basic":    {Input: "a0dd94ed-e60c-42e8-8632-64e8d4765a43", OutputVal: util.UUID{0xa0, 0xdd, 0x94, 0xed, 0xe6, 0x0c, 0x42, 0xe8, 0x86, 0x32, 0x64, 0xe8, 0xd4, 0x76, 0x5a, 0x43}},
+		"too-long": {Input: "a0dd94ed-e60c-42e8-8632-64e8d4765a43a", OutputErr: `too long to be a UUID: "a0dd94ed-e60c-42e8-8632-64e8d4765a43"|"a"`},
+		"bad char": {Input: "a0dd94ej-e60c-42e8-8632-64e8d4765a43a", OutputErr: `illegal byte in UUID: "a0dd94e"|"j"|"-e60c-42e8-8632-64e8d4765a43a"`},
+	}
+	for tcName, tc := range testcases {
+		tc := tc
+		t.Run(tcName, func(t *testing.T) {
+			t.Parallel()
+			val, err := util.ParseUUID(tc.Input)
+			assert.Equal(t, tc.OutputVal, val)
+			if tc.OutputErr == "" {
+				assert.NoError(t, err)
+			} else {
+				assert.EqualError(t, err, tc.OutputErr)
+			}
+		})
+	}
+}
+
+func TestUUIDFormat(t *testing.T) {
+	t.Parallel()
+	type TestCase struct {
+		InputUUID util.UUID
+		InputFmt  string
+		Output    string
+	}
+	uuid := util.MustParseUUID("a0dd94ed-e60c-42e8-8632-64e8d4765a43")
+	testcases := map[string]TestCase{
+		"s":     {InputUUID: uuid, InputFmt: "%s", Output: "a0dd94ed-e60c-42e8-8632-64e8d4765a43"},
+		"x":     {InputUUID: uuid, InputFmt: "%x", Output: "a0dd94ede60c42e8863264e8d4765a43"},
+		"X":     {InputUUID: uuid, InputFmt: "%X", Output: "A0DD94EDE60C42E8863264E8D4765A43"},
+		"v":     {InputUUID: uuid, InputFmt: "%v", Output: "a0dd94ed-e60c-42e8-8632-64e8d4765a43"},
+		"40s":   {InputUUID: uuid, InputFmt: "|% 40s", Output: "|    a0dd94ed-e60c-42e8-8632-64e8d4765a43"},
+		"#115v": {InputUUID: uuid, InputFmt: "|%#115v", Output: "|           util.UUID{0xa0, 0xdd, 0x94, 0xed, 0xe6, 0xc, 0x42, 0xe8, 0x86, 0x32, 0x64, 0xe8, 0xd4, 0x76, 0x5a, 0x43}"},
+	}
+	for tcName, tc := range testcases {
+		tc := tc
+		t.Run(tcName, func(t *testing.T) {
+			t.Parallel()
+			actual := fmt.Sprintf(tc.InputFmt, tc.InputUUID)
+			assert.Equal(t, tc.Output, actual)
+		})
+	}
+}