From 9ddcd2c3ed2f85247161c5ffa653f33e6a01a9cd Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 2 Jul 2022 16:25:03 -0600 Subject: move things around --- pkg/btrfs/aliases.go | 15 +- pkg/btrfs/btree.go | 439 --------------------------------------- pkg/btrfs/btrfssum/csum.go | 78 +++++++ pkg/btrfs/btrfssum/csum_test.go | 35 ++++ pkg/btrfs/csum.go | 78 ------- pkg/btrfs/csum_test.go | 35 ---- pkg/btrfs/io1_device.go | 95 --------- pkg/btrfs/io1_pv.go | 96 +++++++++ pkg/btrfs/io2_fs.go | 186 ----------------- pkg/btrfs/io2_lv.go | 187 +++++++++++++++++ pkg/btrfs/io3_btree.go | 440 ++++++++++++++++++++++++++++++++++++++++ pkg/btrfs/types_btree.go | 403 ------------------------------------ pkg/btrfs/types_node.go | 405 ++++++++++++++++++++++++++++++++++++ pkg/btrfs/types_superblock.go | 46 +++-- 14 files changed, 1270 insertions(+), 1268 deletions(-) delete mode 100644 pkg/btrfs/btree.go create mode 100644 pkg/btrfs/btrfssum/csum.go create mode 100644 pkg/btrfs/btrfssum/csum_test.go delete mode 100644 pkg/btrfs/csum.go delete mode 100644 pkg/btrfs/csum_test.go delete mode 100644 pkg/btrfs/io1_device.go create mode 100644 pkg/btrfs/io1_pv.go delete mode 100644 pkg/btrfs/io2_fs.go create mode 100644 pkg/btrfs/io2_lv.go create mode 100644 pkg/btrfs/io3_btree.go delete mode 100644 pkg/btrfs/types_btree.go create mode 100644 pkg/btrfs/types_node.go (limited to 'pkg/btrfs') diff --git a/pkg/btrfs/aliases.go b/pkg/btrfs/aliases.go index 22508c3..1a18ae6 100644 --- a/pkg/btrfs/aliases.go +++ b/pkg/btrfs/aliases.go @@ -1,7 +1,6 @@ package btrfs import ( - "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol" "lukeshu.com/btrfs-tools/pkg/btrfs/internal" "lukeshu.com/btrfs-tools/pkg/util" ) @@ -9,16 +8,12 @@ import ( type ( // (u)int64 types - Generation = internal.Generation - ObjID = internal.ObjID - LogicalAddr = btrfsvol.LogicalAddr - PhysicalAddr = btrfsvol.PhysicalAddr - AddrDelta = btrfsvol.AddrDelta + Generation = internal.Generation + ObjID = internal.ObjID // complex types - Key = internal.Key - Time = internal.Time - UUID = util.UUID - QualifiedPhysicalAddr = btrfsvol.QualifiedPhysicalAddr + Key = internal.Key + Time = internal.Time + UUID = util.UUID ) diff --git a/pkg/btrfs/btree.go b/pkg/btrfs/btree.go deleted file mode 100644 index cc68002..0000000 --- a/pkg/btrfs/btree.go +++ /dev/null @@ -1,439 +0,0 @@ -package btrfs - -import ( - "errors" - "fmt" - "io" - iofs "io/fs" - "math" - "strings" - - "github.com/datawire/dlib/derror" - - "lukeshu.com/btrfs-tools/pkg/util" -) - -// - The first element will always have an ItemIdx of -1. -// -// - For .Item() callbacks, the last element will always have a -// NodeAddr of 0. -// -// ex: -// -// {-1, 0x01, 3}→{9, 0x02, 2}→{9, 0x03, 1}→{9, 0x04, 0}→{9, 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 LogicalAddr - // NodeLevel is the expected or actual level of the node at - // NodeAddr, or 255 if there is no knowledge of the level. - NodeLevel uint8 -} - -func (elem TreePathElem) writeNodeTo(w io.Writer) { - if elem.NodeLevel != math.MaxUint8 { - fmt.Fprintf(w, "node:%d@%v", elem.NodeLevel, elem.NodeAddr) - } else { - fmt.Fprintf(w, "node@%v", 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() -} - -type TreeWalkHandler struct { - // Callbacks for entire nodes - PreNode func(TreePath) error - Node func(TreePath, *util.Ref[LogicalAddr, Node], error) error - PostNode func(TreePath, *util.Ref[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(treeRoot LogicalAddr, cbs TreeWalkHandler) error { - path := TreePath{ - TreePathElem{ - ItemIdx: -1, - NodeAddr: treeRoot, - NodeLevel: math.MaxUint8, - }, - } - 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 { - 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 LogicalAddr, fn func(Key) int) (TreePath, *util.Ref[LogicalAddr, Node], error) { - path := TreePath{ - TreePathElem{ - ItemIdx: -1, - NodeAddr: treeRoot, - NodeLevel: math.MaxUint8, - }, - } - 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. - items := node.Data.BodyLeaf - for len(items) > 0 { - midpoint := len(items) / 2 - direction := fn(items[midpoint].Head.Key) - switch { - case direction < 0: - items = items[:midpoint] - case direction > 0: - items = items[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[LogicalAddr, Node]) (TreePath, *util.Ref[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[LogicalAddr, Node]) (TreePath, *util.Ref[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) == 0 { - 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(treeRoot LogicalAddr, fn func(Key) int) (Item, error) { - path, node, err := fs.treeSearch(treeRoot, fn) - if err != nil { - return Item{}, err - } - return node.Data.BodyLeaf[path[len(path)-1].ItemIdx], nil -} - -func (fs *FS) TreeLookup(treeRoot LogicalAddr, key Key) (Item, error) { - return fs.TreeSearch(treeRoot, key.Cmp) -} - -// 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(treeRoot LogicalAddr, fn func(Key) int) ([]Item, error) { - middlePath, middleNode, err := fs.treeSearch(treeRoot, 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/pkg/btrfs/btrfssum/csum.go b/pkg/btrfs/btrfssum/csum.go new file mode 100644 index 0000000..22d8149 --- /dev/null +++ b/pkg/btrfs/btrfssum/csum.go @@ -0,0 +1,78 @@ +package btrfssum + +import ( + "encoding/binary" + "encoding/hex" + "fmt" + "hash/crc32" + + "lukeshu.com/btrfs-tools/pkg/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/pkg/btrfs/btrfssum/csum_test.go b/pkg/btrfs/btrfssum/csum_test.go new file mode 100644 index 0000000..c47409c --- /dev/null +++ b/pkg/btrfs/btrfssum/csum_test.go @@ -0,0 +1,35 @@ +package btrfssum_test + +import ( + "fmt" + "testing" + + "github.com/stretchr/testify/assert" + + "lukeshu.com/btrfs-tools/pkg/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/pkg/btrfs/csum.go b/pkg/btrfs/csum.go deleted file mode 100644 index 6245fa4..0000000 --- a/pkg/btrfs/csum.go +++ /dev/null @@ -1,78 +0,0 @@ -package btrfs - -import ( - "encoding/binary" - "encoding/hex" - "fmt" - "hash/crc32" - - "lukeshu.com/btrfs-tools/pkg/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 ( - CSUM_TYPE_CRC32 = CSumType(iota) - CSUM_TYPE_XXHASH - CSUM_TYPE_SHA256 - CSUM_TYPE_BLAKE2 -) - -func (typ CSumType) String() string { - names := map[CSumType]string{ - CSUM_TYPE_CRC32: "crc32c", - CSUM_TYPE_XXHASH: "xxhash64", - CSUM_TYPE_SHA256: "sha256", - CSUM_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{ - CSUM_TYPE_CRC32: 4, - CSUM_TYPE_XXHASH: 8, - CSUM_TYPE_SHA256: 32, - CSUM_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 CSUM_TYPE_CRC32: - crc := crc32.Update(0, crc32.MakeTable(crc32.Castagnoli), data) - - var ret CSum - binary.LittleEndian.PutUint32(ret[:], crc) - return ret, nil - case CSUM_TYPE_XXHASH: - panic("not implemented") - case CSUM_TYPE_SHA256: - panic("not implemented") - case CSUM_TYPE_BLAKE2: - panic("not implemented") - default: - return CSum{}, fmt.Errorf("unknown checksum type: %v", typ) - } -} diff --git a/pkg/btrfs/csum_test.go b/pkg/btrfs/csum_test.go deleted file mode 100644 index 8c2d544..0000000 --- a/pkg/btrfs/csum_test.go +++ /dev/null @@ -1,35 +0,0 @@ -package btrfs_test - -import ( - "fmt" - "testing" - - "github.com/stretchr/testify/assert" - - "lukeshu.com/btrfs-tools/pkg/btrfs" -) - -func TestCSumFormat(t *testing.T) { - t.Parallel() - type TestCase struct { - InputSum btrfs.CSum - InputFmt string - Output string - } - csum := btrfs.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: " btrfs.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/pkg/btrfs/io1_device.go b/pkg/btrfs/io1_device.go deleted file mode 100644 index 29af11c..0000000 --- a/pkg/btrfs/io1_device.go +++ /dev/null @@ -1,95 +0,0 @@ -package btrfs - -import ( - "fmt" - "os" - - "lukeshu.com/btrfs-tools/pkg/binstruct" - "lukeshu.com/btrfs-tools/pkg/util" -) - -type Device struct { - *os.File - - cacheSuperblocks []*util.Ref[PhysicalAddr, Superblock] - cacheSuperblock *util.Ref[PhysicalAddr, Superblock] -} - -var _ util.File[PhysicalAddr] = (*Device)(nil) - -func (dev Device) Size() (PhysicalAddr, error) { - fi, err := dev.Stat() - if err != nil { - return 0, err - } - return PhysicalAddr(fi.Size()), nil -} - -func (dev *Device) ReadAt(dat []byte, paddr PhysicalAddr) (int, error) { - return dev.File.ReadAt(dat, int64(paddr)) -} - -func (dev *Device) WriteAt(dat []byte, paddr PhysicalAddr) (int, error) { - return dev.File.WriteAt(dat, int64(paddr)) -} - -var SuperblockAddrs = []PhysicalAddr{ - 0x00_0001_0000, // 64KiB - 0x00_0400_0000, // 64MiB - 0x40_0000_0000, // 256GiB -} - -func (dev *Device) Superblocks() ([]*util.Ref[PhysicalAddr, Superblock], error) { - if dev.cacheSuperblocks != nil { - return dev.cacheSuperblocks, nil - } - superblockSize := PhysicalAddr(binstruct.StaticSize(Superblock{})) - - sz, err := dev.Size() - if err != nil { - return nil, err - } - - var ret []*util.Ref[PhysicalAddr, Superblock] - for i, addr := range SuperblockAddrs { - if addr+superblockSize <= sz { - superblock := &util.Ref[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[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/pkg/btrfs/io1_pv.go b/pkg/btrfs/io1_pv.go new file mode 100644 index 0000000..b9f7ea4 --- /dev/null +++ b/pkg/btrfs/io1_pv.go @@ -0,0 +1,96 @@ +package btrfs + +import ( + "fmt" + "os" + + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol" + "lukeshu.com/btrfs-tools/pkg/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/pkg/btrfs/io2_fs.go b/pkg/btrfs/io2_fs.go deleted file mode 100644 index 5129329..0000000 --- a/pkg/btrfs/io2_fs.go +++ /dev/null @@ -1,186 +0,0 @@ -package btrfs - -import ( - "fmt" - "io" - - "github.com/datawire/dlib/derror" - - "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" - "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol" - "lukeshu.com/btrfs-tools/pkg/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[PhysicalAddr, Superblock] - cacheSuperblock *util.Ref[PhysicalAddr, Superblock] -} - -var _ util.File[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() (LogicalAddr, error) { - return fs.LV.Size() -} - -func (fs *FS) ReadAt(p []byte, off LogicalAddr) (int, error) { - return fs.LV.ReadAt(p, off) -} -func (fs *FS) WriteAt(p []byte, off LogicalAddr) (int, error) { - return fs.LV.WriteAt(p, off) -} - -func (fs *FS) Resolve(laddr LogicalAddr) (paddrs map[QualifiedPhysicalAddr]struct{}, maxlen AddrDelta) { - return fs.LV.Resolve(laddr) -} - -func (fs *FS) Superblocks() ([]*util.Ref[PhysicalAddr, Superblock], error) { - if fs.cacheSuperblocks != nil { - return fs.cacheSuperblocks, nil - } - var ret []*util.Ref[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[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 { - // 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[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(sb.Data.ChunkTree, 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/pkg/btrfs/io2_lv.go b/pkg/btrfs/io2_lv.go new file mode 100644 index 0000000..0564066 --- /dev/null +++ b/pkg/btrfs/io2_lv.go @@ -0,0 +1,187 @@ +package btrfs + +import ( + "fmt" + "io" + + "github.com/datawire/dlib/derror" + + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol" + "lukeshu.com/btrfs-tools/pkg/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(sb.Data.ChunkTree, 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/pkg/btrfs/io3_btree.go b/pkg/btrfs/io3_btree.go new file mode 100644 index 0000000..b4eb4cb --- /dev/null +++ b/pkg/btrfs/io3_btree.go @@ -0,0 +1,440 @@ +package btrfs + +import ( + "errors" + "fmt" + "io" + iofs "io/fs" + "math" + "strings" + + "github.com/datawire/dlib/derror" + + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol" + "lukeshu.com/btrfs-tools/pkg/util" +) + +// - The first element will always have an ItemIdx of -1. +// +// - For .Item() callbacks, the last element will always have a +// NodeAddr of 0. +// +// ex: +// +// {-1, 0x01, 3}→{9, 0x02, 2}→{9, 0x03, 1}→{9, 0x04, 0}→{9, 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, or 255 if there is no knowledge of the level. + NodeLevel uint8 +} + +func (elem TreePathElem) writeNodeTo(w io.Writer) { + if elem.NodeLevel != math.MaxUint8 { + fmt.Fprintf(w, "node:%d@%v", elem.NodeLevel, elem.NodeAddr) + } else { + fmt.Fprintf(w, "node@%v", 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() +} + +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(treeRoot btrfsvol.LogicalAddr, cbs TreeWalkHandler) error { + path := TreePath{ + TreePathElem{ + ItemIdx: -1, + NodeAddr: treeRoot, + NodeLevel: math.MaxUint8, + }, + } + 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 { + 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 btrfsvol.LogicalAddr, fn func(Key) int) (TreePath, *util.Ref[btrfsvol.LogicalAddr, Node], error) { + path := TreePath{ + TreePathElem{ + ItemIdx: -1, + NodeAddr: treeRoot, + NodeLevel: math.MaxUint8, + }, + } + 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. + items := node.Data.BodyLeaf + for len(items) > 0 { + midpoint := len(items) / 2 + direction := fn(items[midpoint].Head.Key) + switch { + case direction < 0: + items = items[:midpoint] + case direction > 0: + items = items[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) == 0 { + 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(treeRoot btrfsvol.LogicalAddr, fn func(Key) int) (Item, error) { + path, node, err := fs.treeSearch(treeRoot, fn) + if err != nil { + return Item{}, err + } + return node.Data.BodyLeaf[path[len(path)-1].ItemIdx], nil +} + +func (fs *FS) TreeLookup(treeRoot btrfsvol.LogicalAddr, key Key) (Item, error) { + return fs.TreeSearch(treeRoot, key.Cmp) +} + +// 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(treeRoot btrfsvol.LogicalAddr, fn func(Key) int) ([]Item, error) { + middlePath, middleNode, err := fs.treeSearch(treeRoot, 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/pkg/btrfs/types_btree.go b/pkg/btrfs/types_btree.go deleted file mode 100644 index 58a08e0..0000000 --- a/pkg/btrfs/types_btree.go +++ /dev/null @@ -1,403 +0,0 @@ -package btrfs - -import ( - "encoding/binary" - "errors" - "fmt" - "math" - - "lukeshu.com/btrfs-tools/pkg/binstruct" - "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" - "lukeshu.com/btrfs-tools/pkg/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) } - -// Node: main ////////////////////////////////////////////////////////////////////////////////////// - -type Node struct { - // Some context from the parent filesystem - Size uint32 // superblock.NodeSize - ChecksumType 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 CSum `bin:"off=0x0, siz=0x20"` - MetadataUUID UUID `bin:"off=0x20, siz=0x10"` - Addr LogicalAddr `bin:"off=0x30, siz=0x8"` // Logical address of this node - Flags NodeFlags `bin:"off=0x38, siz=0x7"` - BackrefRev uint8 `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() (CSum, error) { - data, err := binstruct.Marshal(node) - if err != nil { - return CSum{}, err - } - return node.ChecksumType.Sum(data[binstruct.StaticSize(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 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, 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(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 nil, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, ErrNotANode) - } - - stored := nodeRef.Data.Head.Checksum - calced, err := nodeRef.Data.ChecksumType.Sum(nodeBuf[binstruct.StaticSize(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 LogicalAddr) (*util.Ref[LogicalAddr, Node], error) { - sb, err := fs.Superblock() - if err != nil { - return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err) - } - - return ReadNode[LogicalAddr](fs, sb.Data, addr, func(claimAddr 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 LogicalAddr, expLevel uint8) (*util.Ref[LogicalAddr, Node], error) { - node, err := fs.ReadNode(addr) - if err != nil { - return node, err - } - if expLevel != math.MaxUint8 && 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/pkg/btrfs/types_node.go b/pkg/btrfs/types_node.go new file mode 100644 index 0000000..24a02e5 --- /dev/null +++ b/pkg/btrfs/types_node.go @@ -0,0 +1,405 @@ +package btrfs + +import ( + "encoding/binary" + "errors" + "fmt" + "math" + + "lukeshu.com/btrfs-tools/pkg/binstruct" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfssum" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol" + "lukeshu.com/btrfs-tools/pkg/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) } + +// 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 uint8 `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, 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 nil, 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 expLevel != math.MaxUint8 && 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/pkg/btrfs/types_superblock.go b/pkg/btrfs/types_superblock.go index 3ed1055..413e5da 100644 --- a/pkg/btrfs/types_superblock.go +++ b/pkg/btrfs/types_superblock.go @@ -6,20 +6,22 @@ import ( "lukeshu.com/btrfs-tools/pkg/binstruct" "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfssum" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol" "lukeshu.com/btrfs-tools/pkg/util" ) type Superblock struct { - Checksum CSum `bin:"off=0x0, siz=0x20"` // Checksum of everything past this field (from 20 to 1000) - FSUUID UUID `bin:"off=0x20, siz=0x10"` // FS UUID - Self 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"` + 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 LogicalAddr `bin:"off=0x50, siz=0x8"` // logical address of the root tree root - ChunkTree LogicalAddr `bin:"off=0x58, siz=0x8"` // logical address of the chunk tree root - LogTree LogicalAddr `bin:"off=0x60, siz=0x8"` // logical address of the log tree root + 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 @@ -33,11 +35,11 @@ type Superblock struct { 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 CSumType `bin:"off=0xc4, siz=0x2"` + 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 @@ -55,9 +57,9 @@ type Superblock struct { NumGlobalRoots uint64 `bin:"off=0x24b, siz=0x8"` // FeatureIncompatExtentTreeV2 - BlockGroupRoot LogicalAddr `bin:"off=0x253, siz=0x8"` - BlockGroupRootGeneration Generation `bin:"off=0x25b, siz=0x8"` - BlockGroupRootLevel uint8 `bin:"off=0x263, siz=0x1"` + 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 @@ -69,12 +71,12 @@ type Superblock struct { binstruct.End `bin:"off=0x1000"` } -func (sb Superblock) CalculateChecksum() (CSum, error) { +func (sb Superblock) CalculateChecksum() (btrfssum.CSum, error) { data, err := binstruct.Marshal(sb) if err != nil { - return CSum{}, err + return btrfssum.CSum{}, err } - return sb.ChecksumType.Sum(data[binstruct.StaticSize(CSum{}):]) + return sb.ChecksumType.Sum(data[binstruct.StaticSize(btrfssum.CSum{}):]) } func (sb Superblock) ValidateChecksum() error { @@ -91,10 +93,10 @@ func (sb Superblock) ValidateChecksum() error { } func (a Superblock) Equal(b Superblock) bool { - a.Checksum = CSum{} + a.Checksum = btrfssum.CSum{} a.Self = 0 - b.Checksum = CSum{} + b.Checksum = btrfssum.CSum{} b.Self = 0 return reflect.DeepEqual(a, b) -- cgit v1.2.3-2-g168b