From e2cdb05eac6726c59fe1831876fddd8037156d67 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 28 Aug 2022 17:55:36 -0600 Subject: btrfs: Split off btrfstree and btrfsprim sub-packages --- lib/btrfs/Makefile | 28 +- lib/btrfs/aliases.go | 22 - lib/btrfs/aliases_objid.go | 39 -- lib/btrfs/btree_ops.go | 503 -------------------- lib/btrfs/btree_path.go | 128 ----- lib/btrfs/btree_util.go | 84 ---- lib/btrfs/btrfsitem/item_blockgroup.go | 4 +- lib/btrfs/btrfsitem/item_chunk.go | 8 +- lib/btrfs/btrfsitem/item_dev.go | 18 +- lib/btrfs/btrfsitem/item_devextent.go | 8 +- lib/btrfs/btrfsitem/item_dir.go | 12 +- lib/btrfs/btrfsitem/item_extent.go | 12 +- lib/btrfs/btrfsitem/item_extentdataref.go | 10 +- lib/btrfs/btrfsitem/item_fileextent.go | 6 +- lib/btrfs/btrfsitem/item_inode.go | 36 +- lib/btrfs/btrfsitem/item_root.go | 26 +- lib/btrfs/btrfsitem/item_rootref.go | 8 +- lib/btrfs/btrfsitem/item_untyped.go | 10 +- lib/btrfs/btrfsitem/item_uuid.go | 4 +- lib/btrfs/btrfsitem/items.go | 6 +- lib/btrfs/btrfsitem/items_gen.go | 64 +-- lib/btrfs/btrfsitem/items_test.go | 6 +- lib/btrfs/btrfsprim/itemtype.go | 79 ++++ lib/btrfs/btrfsprim/misc.go | 48 ++ lib/btrfs/btrfsprim/objid.go | 148 ++++++ lib/btrfs/btrfsprim/uuid.go | 96 ++++ lib/btrfs/btrfsprim/uuid_test.go | 67 +++ lib/btrfs/btrfstree/ops.go | 519 +++++++++++++++++++++ lib/btrfs/btrfstree/path.go | 129 +++++ lib/btrfs/btrfstree/root.go | 81 ++++ ...775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 | 2 + ...7603487337411d9557684e849ee9457d40f8f3e5f5b2fca | 2 + ...ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 | 2 + ...f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 | 2 + lib/btrfs/btrfstree/types_node.go | 454 ++++++++++++++++++ lib/btrfs/btrfstree/types_node_test.go | 35 ++ lib/btrfs/btrfstree/types_superblock.go | 238 ++++++++++ lib/btrfs/internal/itemtype.go | 79 ---- lib/btrfs/internal/misc.go | 48 -- lib/btrfs/internal/objid.go | 148 ------ lib/btrfs/internal/uuid.go | 96 ---- lib/btrfs/internal/uuid_test.go | 67 --- lib/btrfs/io1_pv.go | 15 +- lib/btrfs/io2_lv.go | 28 +- lib/btrfs/io3_btree.go | 45 +- lib/btrfs/io4_fs.go | 42 +- ...775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 | 2 - ...7603487337411d9557684e849ee9457d40f8f3e5f5b2fca | 2 - ...ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 | 2 - ...f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 | 2 - lib/btrfs/types_node.go | 453 ------------------ lib/btrfs/types_node_test.go | 35 -- lib/btrfs/types_superblock.go | 237 ---------- lib/btrfsprogs/btrfsinspect/mount.go | 19 +- lib/btrfsprogs/btrfsinspect/print_tree.go | 82 ++-- .../btrfsinspect/rebuildnodes/rebuildnodes.go | 64 +-- lib/btrfsprogs/btrfsinspect/scandevices.go | 20 +- lib/btrfsprogs/btrfsutil/broken_btree.go | 106 +++-- lib/btrfsprogs/btrfsutil/csums.go | 7 +- lib/btrfsprogs/btrfsutil/walk.go | 26 +- 60 files changed, 2278 insertions(+), 2291 deletions(-) delete mode 100644 lib/btrfs/aliases.go delete mode 100644 lib/btrfs/aliases_objid.go delete mode 100644 lib/btrfs/btree_ops.go delete mode 100644 lib/btrfs/btree_path.go delete mode 100644 lib/btrfs/btree_util.go create mode 100644 lib/btrfs/btrfsprim/itemtype.go create mode 100644 lib/btrfs/btrfsprim/misc.go create mode 100644 lib/btrfs/btrfsprim/objid.go create mode 100644 lib/btrfs/btrfsprim/uuid.go create mode 100644 lib/btrfs/btrfsprim/uuid_test.go create mode 100644 lib/btrfs/btrfstree/ops.go create mode 100644 lib/btrfs/btrfstree/path.go create mode 100644 lib/btrfs/btrfstree/root.go create mode 100644 lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 create mode 100644 lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca create mode 100644 lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 create mode 100644 lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 create mode 100644 lib/btrfs/btrfstree/types_node.go create mode 100644 lib/btrfs/btrfstree/types_node_test.go create mode 100644 lib/btrfs/btrfstree/types_superblock.go delete mode 100644 lib/btrfs/internal/itemtype.go delete mode 100644 lib/btrfs/internal/misc.go delete mode 100644 lib/btrfs/internal/objid.go delete mode 100644 lib/btrfs/internal/uuid.go delete mode 100644 lib/btrfs/internal/uuid_test.go delete mode 100644 lib/btrfs/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 delete mode 100644 lib/btrfs/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca delete mode 100644 lib/btrfs/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 delete mode 100644 lib/btrfs/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 delete mode 100644 lib/btrfs/types_node.go delete mode 100644 lib/btrfs/types_node_test.go delete mode 100644 lib/btrfs/types_superblock.go (limited to 'lib') diff --git a/lib/btrfs/Makefile b/lib/btrfs/Makefile index 50577e0..f7f1422 100644 --- a/lib/btrfs/Makefile +++ b/lib/btrfs/Makefile @@ -26,22 +26,22 @@ btrfsitem/items_gen.go: btrfsitem/items.txt $(MAKEFILE_LIST) echo 'import ('; \ echo '"reflect"'; \ echo; \ - echo '"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal"'; \ + echo '"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"'; \ echo ')'; \ echo 'const ('; \ - sed -E 's,(.*)=(.*) (.*),\1_KEY=internal.\1_KEY,' $<; \ + sed -E 's,(.*)=(.*) (.*),\1_KEY=btrfsprim.\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 'var untypedObjID2gotype = map[btrfsprim.ObjID]reflect.Type{'; \ + sed -En 's|UNTYPED=0:(.*) (.*)|btrfsprim.\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) +btrfsprim/itemtype.go: btrfsitem/items.txt $(MAKEFILE_LIST) { \ echo '// Code generated by Make. DO NOT EDIT.'; \ echo; \ @@ -63,23 +63,7 @@ internal/itemtype.go: btrfsitem/items.txt $(MAKEFILE_LIST) 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 '// SPDX-License-Identifier: GPL-2.0-or-later'; \ - 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 +files += btrfsprim/itemtype.go all: $(files) .PHONY: all diff --git a/lib/btrfs/aliases.go b/lib/btrfs/aliases.go deleted file mode 100644 index 6fe5661..0000000 --- a/lib/btrfs/aliases.go +++ /dev/null @@ -1,22 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package btrfs - -import ( - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" -) - -type ( - // (u)int64 types - - Generation = internal.Generation - ObjID = internal.ObjID - - // complex types - - Key = internal.Key - Time = internal.Time - UUID = internal.UUID -) diff --git a/lib/btrfs/aliases_objid.go b/lib/btrfs/aliases_objid.go deleted file mode 100644 index 21309b8..0000000 --- a/lib/btrfs/aliases_objid.go +++ /dev/null @@ -1,39 +0,0 @@ -// Code generated by Make. DO NOT EDIT. - -// SPDX-License-Identifier: GPL-2.0-or-later - -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/btree_ops.go b/lib/btrfs/btree_ops.go deleted file mode 100644 index b590aa7..0000000 --- a/lib/btrfs/btree_ops.go +++ /dev/null @@ -1,503 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package btrfs - -import ( - "context" - "errors" - "fmt" - iofs "io/fs" - "math" - - "github.com/datawire/dlib/derror" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" - "git.lukeshu.com/btrfs-progs-ng/lib/slices" -) - -type Trees interface { - // TreeWalk walks a tree, triggering callbacks for every node, - // key-pointer, and item; as well as for any errors encountered. - // - // If the tree is valid, then everything is walked in key-order; but if - // the tree is broken, then ordering is not guaranteed. - // - // Canceling the Context causes TreeWalk to return early; no - // values from the Context are used. - // - // The lifecycle of callbacks is: - // - // 001 .PreNode() - // 002 (read node) - // 003 .Node() (or .BadNode()) - // for item in node.items: - // if internal: - // 004 .PreKeyPointer() - // 005 (recurse) - // 006 .PostKeyPointer() - // else: - // 004 .Item() (or .BadItem()) - // 007 .PostNode() - TreeWalk(ctx context.Context, treeID ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) - - TreeLookup(treeID ObjID, key Key) (Item, error) - TreeSearch(treeID ObjID, fn func(key Key, size uint32) int) (Item, error) // size is math.MaxUint32 for key-pointers - - // If some items are able to be read, but there is an error reading the - // full set, then it might return *both* a list of items and an error. - // - // If no such item is found, an error that is io/fs.ErrNotExist is - // returned. - TreeSearchAll(treeID ObjID, fn func(key Key, size uint32) int) ([]Item, error) // size is math.MaxUint32 for key-pointers - - // For bootstrapping purposes. - Superblock() (*Superblock, error) - - // For reading raw data extants pointed at by tree items. - ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) -} - -type TreeWalkHandler struct { - // Callbacks for entire nodes. - // - // If any of these return an error that is io/fs.SkipDir, the - // node immediately stops getting processed; if PreNode, Node, - // or BadNode return io/fs.SkipDir then key pointers and items - // within the node are not processed. - PreNode func(TreePath) error - Node func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error - BadNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) error - PostNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error - // Callbacks for items on internal nodes - PreKeyPointer func(TreePath, KeyPointer) error - PostKeyPointer func(TreePath, KeyPointer) error - // Callbacks for items on leaf nodes - Item func(TreePath, Item) error - BadItem func(TreePath, Item) error -} - -type TreeError struct { - Path TreePath - Err error -} - -func (e *TreeError) Unwrap() error { return e.Err } - -func (e *TreeError) Error() string { - return fmt.Sprintf("%v: %v", e.Path, e.Err) -} - -// TreeWalk implements the 'Trees' interface. -func (fs *FS) TreeWalk(ctx context.Context, treeID ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { - rootInfo, err := LookupTreeRoot(fs, treeID) - if err != nil { - errHandle(&TreeError{Path: TreePath{{FromTree: treeID}}, Err: err}) - return - } - fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs) -} - -// TreeWalk is a utility function to help with implementing the 'Trees' -// interface. -func (fs *FS) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { - path := TreePath{{ - FromTree: rootInfo.TreeID, - FromGeneration: rootInfo.Generation, - FromItemIdx: -1, - ToNodeAddr: rootInfo.RootNode, - ToNodeLevel: rootInfo.Level, - }} - fs.treeWalk(ctx, path, errHandle, cbs) -} - -func (fs *FS) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) { - if ctx.Err() != nil { - return - } - if path.Node(-1).ToNodeAddr == 0 { - return - } - - if cbs.PreNode != nil { - if err := cbs.PreNode(path); err != nil { - if errors.Is(err, iofs.SkipDir) { - return - } - errHandle(&TreeError{Path: path, Err: err}) - } - if ctx.Err() != nil { - return - } - } - node, err := fs.ReadNode(path) - if ctx.Err() != nil { - return - } - if err != nil && node != nil && cbs.BadNode != nil { - // opportunity to fix the node - err = cbs.BadNode(path, node, err) - if errors.Is(err, iofs.SkipDir) { - return - } - } - if err != nil { - errHandle(&TreeError{Path: path, Err: err}) - } else { - if cbs.Node != nil { - if err := cbs.Node(path, node); err != nil { - if errors.Is(err, iofs.SkipDir) { - return - } - errHandle(&TreeError{Path: path, Err: err}) - } - } - } - if ctx.Err() != nil { - return - } - if node != nil { - for i, item := range node.Data.BodyInternal { - itemPath := append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromGeneration: node.Data.Head.Generation, - FromItemIdx: i, - ToNodeAddr: item.BlockPtr, - ToNodeLevel: node.Data.Head.Level - 1, - }) - if cbs.PreKeyPointer != nil { - if err := cbs.PreKeyPointer(itemPath, item); err != nil { - errHandle(&TreeError{Path: itemPath, Err: err}) - } - if ctx.Err() != nil { - return - } - } - fs.treeWalk(ctx, itemPath, errHandle, cbs) - if cbs.PostKeyPointer != nil { - if err := cbs.PostKeyPointer(itemPath, item); err != nil { - errHandle(&TreeError{Path: itemPath, Err: err}) - } - if ctx.Err() != nil { - return - } - } - } - for i, item := range node.Data.BodyLeaf { - itemPath := append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromGeneration: node.Data.Head.Generation, - FromItemIdx: i, - }) - if errBody, isErr := item.Body.(btrfsitem.Error); isErr { - if cbs.BadItem == nil { - errHandle(&TreeError{Path: itemPath, Err: errBody.Err}) - } else { - if err := cbs.BadItem(itemPath, item); err != nil { - errHandle(&TreeError{Path: itemPath, Err: err}) - } - if ctx.Err() != nil { - return - } - } - } else { - if cbs.Item != nil { - if err := cbs.Item(itemPath, item); err != nil { - errHandle(&TreeError{Path: itemPath, Err: err}) - } - if ctx.Err() != nil { - return - } - } - } - } - } - if cbs.PostNode != nil { - if err := cbs.PostNode(path, node); err != nil { - if errors.Is(err, iofs.SkipDir) { - return - } - errHandle(&TreeError{Path: path, Err: err}) - } - } -} - -func (fs *FS) treeSearch(treeRoot TreeRoot, fn func(Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { - path := TreePath{{ - FromTree: treeRoot.TreeID, - FromGeneration: treeRoot.Generation, - FromItemIdx: -1, - ToNodeAddr: treeRoot.RootNode, - ToNodeLevel: treeRoot.Level, - }} - for { - if path.Node(-1).ToNodeAddr == 0 { - return TreePath{}, nil, iofs.ErrNotExist - } - node, err := fs.ReadNode(path) - if err != nil { - return TreePath{}, nil, err - } - - if node.Data.Head.Level > 0 { - // 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'. - // - // i.e. find the highest value that isn't too high. - lastGood, ok := slices.SearchHighest(node.Data.BodyInternal, func(kp KeyPointer) int { - return slices.Min(fn(kp.Key, math.MaxUint32), 0) // don't return >0; a key can't be "too low" - }) - if !ok { - return TreePath{}, nil, iofs.ErrNotExist - } - path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromGeneration: node.Data.Head.Generation, - FromItemIdx: lastGood, - ToNodeAddr: node.Data.BodyInternal[lastGood].BlockPtr, - ToNodeLevel: node.Data.Head.Level - 1, - }) - } else { - // leaf node - - // Search for a member of node.Data.BodyLeaf for which - // `fn(item.Head.Key) == 0`. - // - // + + + + 0 - - - - - // - // Such an item might not exist; in this case, return nil/ErrNotExist. - // Multiple such items might exist; in this case, it does not matter which - // is returned. - // - // Implement this search as a binary search. - idx, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int { - return fn(item.Key, item.BodySize) - }) - if !ok { - return TreePath{}, nil, iofs.ErrNotExist - } - path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromGeneration: node.Data.Head.Generation, - FromItemIdx: idx, - }) - return path, node, nil - } - } -} - -func (fs *FS) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { - var err error - path = path.DeepCopy() - - // go up - for path.Node(-1).FromItemIdx < 1 { - path = path.Parent() - if len(path) == 0 { - return TreePath{}, nil, nil - } - } - // go left - path.Node(-1).FromItemIdx-- - if path.Node(-1).ToNodeAddr != 0 { - if node.Addr != path.Node(-2).ToNodeAddr { - node, err = fs.ReadNode(path.Parent()) - if err != nil { - return TreePath{}, nil, err - } - path.Node(-1).ToNodeAddr = node.Data.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr - } - } - // go down - for path.Node(-1).ToNodeAddr != 0 { - if node.Addr != path.Node(-1).ToNodeAddr { - node, err = fs.ReadNode(path) - if err != nil { - return TreePath{}, nil, err - } - } - if node.Data.Head.Level > 0 { - path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromGeneration: node.Data.Head.Generation, - FromItemIdx: len(node.Data.BodyInternal) - 1, - ToNodeAddr: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr, - ToNodeLevel: node.Data.Head.Level - 1, - }) - } else { - path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromGeneration: node.Data.Head.Generation, - FromItemIdx: len(node.Data.BodyLeaf) - 1, - }) - } - } - // return - if node.Addr != path.Node(-2).ToNodeAddr { - node, err = fs.ReadNode(path.Parent()) - if err != nil { - return TreePath{}, nil, err - } - } - return path, node, nil -} - -func (fs *FS) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { - var err error - path = path.DeepCopy() - - // go up - if node.Addr != path.Node(-2).ToNodeAddr { - node, err = fs.ReadNode(path.Parent()) - if err != nil { - return TreePath{}, nil, err - } - path.Node(-2).ToNodeLevel = node.Data.Head.Level - } - for path.Node(-1).FromItemIdx+1 >= int(node.Data.Head.NumItems) { - path = path.Parent() - if len(path) == 1 { - return TreePath{}, nil, nil - } - if node.Addr != path.Node(-2).ToNodeAddr { - node, err = fs.ReadNode(path.Parent()) - if err != nil { - return TreePath{}, nil, err - } - path.Node(-2).ToNodeLevel = node.Data.Head.Level - } - } - // go right - path.Node(-1).FromItemIdx++ - if path.Node(-1).ToNodeAddr != 0 { - if node.Addr != path.Node(-2).ToNodeAddr { - node, err = fs.ReadNode(path.Parent()) - if err != nil { - return TreePath{}, nil, err - } - path.Node(-1).ToNodeAddr = node.Data.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr - } - } - // go down - for path.Node(-1).ToNodeAddr != 0 { - if node.Addr != path.Node(-1).ToNodeAddr { - node, err = fs.ReadNode(path) - if err != nil { - return TreePath{}, nil, err - } - path.Node(-1).ToNodeLevel = node.Data.Head.Level - } - if node.Data.Head.Level > 0 { - path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromGeneration: node.Data.Head.Generation, - FromItemIdx: 0, - ToNodeAddr: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr, - ToNodeLevel: node.Data.Head.Level - 1, - }) - } else { - path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromGeneration: node.Data.Head.Generation, - FromItemIdx: 0, - }) - } - } - // return - if node.Addr != path.Node(-2).ToNodeAddr { - node, err = fs.ReadNode(path.Parent()) - if err != nil { - return TreePath{}, nil, err - } - } - return path, node, nil -} - -// TreeSearch implements the 'Trees' interface. -func (fs *FS) TreeSearch(treeID ObjID, fn func(Key, uint32) int) (Item, error) { - rootInfo, err := LookupTreeRoot(fs, treeID) - if err != nil { - return Item{}, err - } - path, node, err := fs.treeSearch(*rootInfo, fn) - if err != nil { - return Item{}, err - } - return node.Data.BodyLeaf[path.Node(-1).FromItemIdx], nil -} - -// KeySearch returns a comparator suitable to be passed to TreeSearch. -func KeySearch(fn func(Key) int) func(Key, uint32) int { - return func(key Key, _ uint32) int { - return fn(key) - } -} - -// TreeLookup implements the 'Trees' interface. -func (fs *FS) TreeLookup(treeID ObjID, key Key) (Item, error) { - item, err := fs.TreeSearch(treeID, KeySearch(key.Cmp)) - if err != nil { - err = fmt.Errorf("item with key=%v: %w", key, err) - } - return item, err -} - -// TreeSearchAll implements the 'Trees' interface. -func (fs *FS) TreeSearchAll(treeID ObjID, fn func(Key, uint32) int) ([]Item, error) { - rootInfo, err := LookupTreeRoot(fs, treeID) - if err != nil { - return nil, err - } - middlePath, middleNode, err := fs.treeSearch(*rootInfo, fn) - if err != nil { - return nil, err - } - middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemIdx] - - var ret = []Item{middleItem} - var errs derror.MultiError - for prevPath, prevNode := middlePath, middleNode; true; { - prevPath, prevNode, err = fs.prev(prevPath, prevNode) - if err != nil { - errs = append(errs, err) - break - } - if len(prevPath) == 0 { - break - } - prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemIdx] - if fn(prevItem.Key, prevItem.BodySize) != 0 { - break - } - ret = append(ret, prevItem) - } - slices.Reverse(ret) - for nextPath, nextNode := middlePath, middleNode; true; { - nextPath, nextNode, err = fs.next(nextPath, nextNode) - if err != nil { - errs = append(errs, err) - break - } - if len(nextPath) == 0 { - break - } - nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemIdx] - if fn(nextItem.Key, nextItem.BodySize) != 0 { - break - } - ret = append(ret, nextItem) - } - if errs != nil { - err = errs - } - return ret, err -} diff --git a/lib/btrfs/btree_path.go b/lib/btrfs/btree_path.go deleted file mode 100644 index 0124aea..0000000 --- a/lib/btrfs/btree_path.go +++ /dev/null @@ -1,128 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package btrfs - -import ( - "fmt" - "io" - "strings" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" -) - -// - The first element will always have an ItemIdx of -1. -// -// - For .Item() callbacks, the last element will always have a -// NodeAddr of 0. -// -// For example, a path through a tree, with the associated PathElems: -// -// [superblock: tree=B, lvl=3, gen=6] -// | -// | <------------------------------------------ pathElem={from_tree:B, from_gen=6, from_idx=-1, -// | to_addr:0x01, to_lvl=3} -// +[0x01]-------------+ -// | lvl=3 gen=6 own=B | -// +-+-+-+-+-+-+-+-+-+-+ -// |0|1|2|3|4|5|6|7|8|9| -// +-+-+-+-+-+-+-+-+-+-+ -// | -// | <------------------------------ pathElem:{from_tree:B, from_gen:6, from_idx:7, -// | to_addr:0x02, to_lvl:2} -// +[0x02]--------------+ -// | lvl=2 gen=5 own=B | -// +-+-+-+-+-+-+-+-+-+-+ -// |0|1|2|3|4|5|6|7|8|9| -// +-+-+-+-+-+-+-+-+-+-+ -// | -// | <-------------------- pathElem={from_tree:B, from_gen:5, from_idx:6, -// | to_addr:0x03, to_lvl:1} -// +[0x03]-------------+ -// | lvl=1 gen=5 own=A | -// +-+-+-+-+-+-+-+-+-+-+ -// |0|1|2|3|4|5|6|7|8|9| -// +-+-+-+-+-+-+-+-+-+-+ -// | -// | <---------------- pathElem={from_tree:A, from_gen:5, from_idx:3, -// | to_addr:0x04, to_lvl:0} -// +[0x04]-------------+ -// | lvl=0 gen=2 own=A | -// +-+-+-+-+-+-+-+-+-+-+ -// |0|1|2|3|4|5|6|7|8|9| -// +-+-+-+-+-+-+-+-+-+-+ -// | -// | <--------------- pathElem={from_tree:A, from_gen:2, from_idx:1, -// | to_addr:0, to_lvl:0} -// [item] -type TreePath []TreePathElem - -// A TreePathElem essentially represents a KeyPointer. If there is an -// error looking up the tree root, everything but FromTree is zero. -type TreePathElem struct { - // FromTree is the owning tree ID of the parent node; or the - // well-known tree ID if this is the root. - FromTree ObjID - // FromGeneration is the generation of the parent node the - // parent node; or generation stored in the superblock if this - // is the root. - FromGeneration Generation - // FromItemIdx is the index of this KeyPointer in the parent - // Node; or -1 if this is the root and there is no KeyPointer. - FromItemIdx int - - // ToNodeAddr is the address of the node that the KeyPointer - // points at, or 0 if this is a leaf item and nothing is being - // pointed at. - ToNodeAddr btrfsvol.LogicalAddr - // ToNodeLevel is the expected or actual level of the node at - // ToNodeAddr, or 0 if this is a leaf item and nothing is - // being pointed at. - ToNodeLevel uint8 -} - -func (elem TreePathElem) writeNodeTo(w io.Writer) { - fmt.Fprintf(w, "node:%d@%v", elem.ToNodeLevel, elem.ToNodeAddr) -} - -func (path TreePath) String() string { - if len(path) == 0 { - return "(empty-path)" - } else { - var ret strings.Builder - fmt.Fprintf(&ret, "%s->", path[0].FromTree.Format(btrfsitem.ROOT_ITEM_KEY)) - if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree}) { - ret.WriteString("(empty-path)") - } else { - path[0].writeNodeTo(&ret) - } - for _, elem := range path[1:] { - fmt.Fprintf(&ret, "[%v]", elem.FromItemIdx) - if elem.ToNodeAddr != 0 { - ret.WriteString("->") - elem.writeNodeTo(&ret) - } - } - return ret.String() - } -} - -func (path TreePath) DeepCopy() TreePath { - return append(TreePath(nil), path...) -} - -func (path TreePath) Parent() TreePath { - return path[:len(path)-1] -} - -// path.Node(x) is like &path[x], but negative values of x move down -// from the end of path (similar to how lists work in many other -// languages, such as Python). -func (path TreePath) Node(x int) *TreePathElem { - if x < 0 { - x += len(path) - } - return &path[x] -} diff --git a/lib/btrfs/btree_util.go b/lib/btrfs/btree_util.go deleted file mode 100644 index 2076114..0000000 --- a/lib/btrfs/btree_util.go +++ /dev/null @@ -1,84 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package btrfs - -import ( - "fmt" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" -) - -// A TreeRoot is more-or-less a btrfsitem.Root, but simpler; returned by -// LookupTreeRoot. -type TreeRoot struct { - TreeID ObjID - RootNode btrfsvol.LogicalAddr - Level uint8 - Generation Generation -} - -// LookupTreeRoot is a utility function to help with implementing the 'Trees' -// interface. -func LookupTreeRoot(fs Trees, 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.RootTree, - Level: sb.RootLevel, - Generation: sb.Generation, // XXX: same generation as LOG_TREE? - }, nil - case CHUNK_TREE_OBJECTID: - return &TreeRoot{ - TreeID: treeID, - RootNode: sb.ChunkTree, - Level: sb.ChunkLevel, - Generation: sb.ChunkRootGeneration, - }, nil - case TREE_LOG_OBJECTID: - return &TreeRoot{ - TreeID: treeID, - RootNode: sb.LogTree, - Level: sb.LogLevel, - Generation: sb.Generation, // XXX: same generation as ROOT_TREE? - }, nil - case BLOCK_GROUP_TREE_OBJECTID: - return &TreeRoot{ - TreeID: treeID, - RootNode: sb.BlockGroupRoot, - Level: sb.BlockGroupRootLevel, - Generation: sb.BlockGroupRootGeneration, - }, nil - default: - rootItem, err := fs.TreeSearch(ROOT_TREE_OBJECTID, func(key Key, _ uint32) 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 - } -} diff --git a/lib/btrfs/btrfsitem/item_blockgroup.go b/lib/btrfs/btrfsitem/item_blockgroup.go index 776ff56..96ce218 100644 --- a/lib/btrfs/btrfsitem/item_blockgroup.go +++ b/lib/btrfs/btrfsitem/item_blockgroup.go @@ -6,15 +6,15 @@ package btrfsitem import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/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 + ChunkObjectID btrfsprim.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 index fe2637d..1f1d577 100644 --- a/lib/btrfs/btrfsitem/item_chunk.go +++ b/lib/btrfs/btrfsitem/item_chunk.go @@ -6,8 +6,8 @@ package btrfsitem import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" "git.lukeshu.com/btrfs-progs-ng/lib/containers" ) @@ -22,7 +22,7 @@ type Chunk struct { // CHUNK_ITEM=228 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) + Owner btrfsprim.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"` @@ -36,11 +36,11 @@ type ChunkHeader struct { type ChunkStripe struct { DeviceID btrfsvol.DeviceID `bin:"off=0x0, siz=0x8"` Offset btrfsvol.PhysicalAddr `bin:"off=0x8, siz=0x8"` - DeviceUUID internal.UUID `bin:"off=0x10, siz=0x10"` + DeviceUUID btrfsprim.UUID `bin:"off=0x10, siz=0x10"` binstruct.End `bin:"off=0x20"` } -func (chunk Chunk) Mappings(key internal.Key) []btrfsvol.Mapping { +func (chunk Chunk) Mappings(key btrfsprim.Key) []btrfsvol.Mapping { ret := make([]btrfsvol.Mapping, 0, len(chunk.Stripes)) for _, stripe := range chunk.Stripes { ret = append(ret, btrfsvol.Mapping{ diff --git a/lib/btrfs/btrfsitem/item_dev.go b/lib/btrfs/btrfsitem/item_dev.go index 020f2ca..fd7f458 100644 --- a/lib/btrfs/btrfsitem/item_dev.go +++ b/lib/btrfs/btrfsitem/item_dev.go @@ -6,8 +6,8 @@ package btrfsitem import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" ) // key.objectid = BTRFS_DEV_ITEMS_OBJECTID @@ -22,15 +22,15 @@ type Dev struct { // DEV_ITEM=216 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"` + Type uint64 `bin:"off=0x24, siz=0x8"` + Generation btrfsprim.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 internal.UUID `bin:"off=0x42, siz=0x10"` - FSUUID internal.UUID `bin:"off=0x52, siz=0x10"` + DevUUID btrfsprim.UUID `bin:"off=0x42, siz=0x10"` + FSUUID btrfsprim.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 index 4f26b27..8f5f05c 100644 --- a/lib/btrfs/btrfsitem/item_devextent.go +++ b/lib/btrfs/btrfsitem/item_devextent.go @@ -6,22 +6,22 @@ package btrfsitem import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" ) // 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"` + ChunkObjectID btrfsprim.ObjID `bin:"off=8, siz=8"` ChunkOffset btrfsvol.LogicalAddr `bin:"off=16, siz=8"` Length btrfsvol.AddrDelta `bin:"off=24, siz=8"` - ChunkTreeUUID internal.UUID `bin:"off=32, siz=16"` + ChunkTreeUUID btrfsprim.UUID `bin:"off=32, siz=16"` binstruct.End `bin:"off=48"` } -func (devext DevExtent) Mapping(key internal.Key) btrfsvol.Mapping { +func (devext DevExtent) Mapping(key btrfsprim.Key) btrfsvol.Mapping { return btrfsvol.Mapping{ LAddr: devext.ChunkOffset, PAddr: btrfsvol.QualifiedPhysicalAddr{ diff --git a/lib/btrfs/btrfsitem/item_dir.go b/lib/btrfs/btrfsitem/item_dir.go index 9df1b8d..836c477 100644 --- a/lib/btrfs/btrfsitem/item_dir.go +++ b/lib/btrfs/btrfsitem/item_dir.go @@ -10,7 +10,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" "git.lukeshu.com/btrfs-progs-ng/lib/binstruct/binutil" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" ) const MaxNameLen = 255 @@ -24,11 +24,11 @@ func NameHash(dat []byte) uint64 { // - for DIR_ITEM and XATTR_ITEM = NameHash(name) // - for DIR_INDEX = index id in the directory (starting at 2, because "." and "..") type DirEntry struct { // DIR_ITEM=84 DIR_INDEX=96 XATTR_ITEM=24 - 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"` + Location btrfsprim.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:"-"` diff --git a/lib/btrfs/btrfsitem/item_extent.go b/lib/btrfs/btrfsitem/item_extent.go index e8cd9b9..97dc105 100644 --- a/lib/btrfs/btrfsitem/item_extent.go +++ b/lib/btrfs/btrfsitem/item_extent.go @@ -8,7 +8,7 @@ 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/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" ) @@ -66,15 +66,15 @@ func (o Extent) MarshalBinary() ([]byte, error) { } 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"` + Refs int64 `bin:"off=0, siz=8"` + Generation btrfsprim.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=0x1"` + Key btrfsprim.Key `bin:"off=0, siz=0x11"` + Level uint8 `bin:"off=0x11, siz=0x1"` binstruct.End `bin:"off=0x12"` } diff --git a/lib/btrfs/btrfsitem/item_extentdataref.go b/lib/btrfs/btrfsitem/item_extentdataref.go index 6185202..74ce799 100644 --- a/lib/btrfs/btrfsitem/item_extentdataref.go +++ b/lib/btrfs/btrfsitem/item_extentdataref.go @@ -6,13 +6,13 @@ 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/btrfs/btrfsprim" ) 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"` + Root btrfsprim.ObjID `bin:"off=0, siz=8"` + ObjectID btrfsprim.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 index b7e394e..83e5d34 100644 --- a/lib/btrfs/btrfsitem/item_fileextent.go +++ b/lib/btrfs/btrfsitem/item_fileextent.go @@ -8,15 +8,15 @@ import ( "fmt" "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/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 + Generation btrfsprim.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"` diff --git a/lib/btrfs/btrfsitem/item_inode.go b/lib/btrfs/btrfsitem/item_inode.go index 49b2031..8023156 100644 --- a/lib/btrfs/btrfsitem/item_inode.go +++ b/lib/btrfs/btrfsitem/item_inode.go @@ -6,28 +6,28 @@ 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/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" ) 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"` // allocated bytes, may be larger than size (or smaller if there are holes?) - 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 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"?) + Generation btrfsprim.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"` // allocated bytes, may be larger than size (or smaller if there are holes?) + 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 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 btrfsprim.Time `bin:"off=0x70, siz=0x0c"` // stat + CTime btrfsprim.Time `bin:"off=0x7c, siz=0x0c"` // stat + MTime btrfsprim.Time `bin:"off=0x88, siz=0x0c"` // stat + OTime btrfsprim.Time `bin:"off=0x94, siz=0x0c"` // statx.stx_btime (why is this called "otime" instead of "btime"?) binstruct.End `bin:"off=0xa0"` } diff --git a/lib/btrfs/btrfsitem/item_root.go b/lib/btrfs/btrfsitem/item_root.go index 7725363..2e0b327 100644 --- a/lib/btrfs/btrfsitem/item_root.go +++ b/lib/btrfs/btrfsitem/item_root.go @@ -6,37 +6,37 @@ package btrfsitem import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" ) 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"` + Generation btrfsprim.Generation `bin:"off=0x0a0, siz=0x08"` + RootDirID btrfsprim.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"` + DropProgress btrfsprim.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 internal.UUID `bin:"off=0x0f7, siz=0x10"` - ParentUUID internal.UUID `bin:"off=0x107, siz=0x10"` - ReceivedUUID internal.UUID `bin:"off=0x117, siz=0x10"` + GenerationV2 btrfsprim.Generation `bin:"off=0x0ef, siz=0x08"` + UUID btrfsprim.UUID `bin:"off=0x0f7, siz=0x10"` + ParentUUID btrfsprim.UUID `bin:"off=0x107, siz=0x10"` + ReceivedUUID btrfsprim.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"` + CTime btrfsprim.Time `bin:"off=0x147, siz=0x0c"` + OTime btrfsprim.Time `bin:"off=0x153, siz=0x0c"` + STime btrfsprim.Time `bin:"off=0x15f, siz=0x0c"` + RTime btrfsprim.Time `bin:"off=0x16b, siz=0x0c"` + GlobalTreeID btrfsprim.ObjID `bin:"off=0x177, siz=0x08"` Reserved [7]int64 `bin:"off=0x17f, siz=0x38"` binstruct.End `bin:"off=0x1b7"` } diff --git a/lib/btrfs/btrfsitem/item_rootref.go b/lib/btrfs/btrfsitem/item_rootref.go index 1ee0ee4..d1dfd3b 100644 --- a/lib/btrfs/btrfsitem/item_rootref.go +++ b/lib/btrfs/btrfsitem/item_rootref.go @@ -9,13 +9,13 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" "git.lukeshu.com/btrfs-progs-ng/lib/binstruct/binutil" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" ) 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] + DirID btrfsprim.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:"-"` } diff --git a/lib/btrfs/btrfsitem/item_untyped.go b/lib/btrfs/btrfsitem/item_untyped.go index 04915c6..acf4ebe 100644 --- a/lib/btrfs/btrfsitem/item_untyped.go +++ b/lib/btrfs/btrfsitem/item_untyped.go @@ -6,13 +6,13 @@ 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/btrfs/btrfsprim" ) 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"` + Location btrfsprim.Key `bin:"off=0x00, siz=0x11"` + Generation btrfsprim.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 index ca82652..03823ce 100644 --- a/lib/btrfs/btrfsitem/item_uuid.go +++ b/lib/btrfs/btrfsitem/item_uuid.go @@ -6,7 +6,7 @@ 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/btrfs/btrfsprim" ) // The Key for this item is a UUID, and the item is a subvolume IDs @@ -15,6 +15,6 @@ import ( // 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"` + ObjID btrfsprim.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 index 35d8b4f..29b3cb0 100644 --- a/lib/btrfs/btrfsitem/items.go +++ b/lib/btrfs/btrfsitem/items.go @@ -9,12 +9,12 @@ import ( "reflect" "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" ) -type Type = internal.ItemType +type Type = btrfsprim.ItemType type Item interface { isItem() @@ -37,7 +37,7 @@ func (o *Error) UnmarshalBinary(dat []byte) (int, error) { } // Rather than returning a separate error value, return an Error item. -func UnmarshalItem(key internal.Key, csumType btrfssum.CSumType, dat []byte) Item { +func UnmarshalItem(key btrfsprim.Key, csumType btrfssum.CSumType, dat []byte) Item { var gotyp reflect.Type if key.ItemType == UNTYPED_KEY { var ok bool diff --git a/lib/btrfs/btrfsitem/items_gen.go b/lib/btrfs/btrfsitem/items_gen.go index d21cd3e..89bc171 100644 --- a/lib/btrfs/btrfsitem/items_gen.go +++ b/lib/btrfs/btrfsitem/items_gen.go @@ -7,39 +7,39 @@ package btrfsitem import ( "reflect" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" ) 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 + BLOCK_GROUP_ITEM_KEY = btrfsprim.BLOCK_GROUP_ITEM_KEY + CHUNK_ITEM_KEY = btrfsprim.CHUNK_ITEM_KEY + DEV_EXTENT_KEY = btrfsprim.DEV_EXTENT_KEY + DEV_ITEM_KEY = btrfsprim.DEV_ITEM_KEY + DIR_INDEX_KEY = btrfsprim.DIR_INDEX_KEY + DIR_ITEM_KEY = btrfsprim.DIR_ITEM_KEY + EXTENT_CSUM_KEY = btrfsprim.EXTENT_CSUM_KEY + EXTENT_DATA_KEY = btrfsprim.EXTENT_DATA_KEY + EXTENT_DATA_REF_KEY = btrfsprim.EXTENT_DATA_REF_KEY + EXTENT_ITEM_KEY = btrfsprim.EXTENT_ITEM_KEY + FREE_SPACE_BITMAP_KEY = btrfsprim.FREE_SPACE_BITMAP_KEY + FREE_SPACE_EXTENT_KEY = btrfsprim.FREE_SPACE_EXTENT_KEY + FREE_SPACE_INFO_KEY = btrfsprim.FREE_SPACE_INFO_KEY + INODE_ITEM_KEY = btrfsprim.INODE_ITEM_KEY + INODE_REF_KEY = btrfsprim.INODE_REF_KEY + METADATA_ITEM_KEY = btrfsprim.METADATA_ITEM_KEY + ORPHAN_ITEM_KEY = btrfsprim.ORPHAN_ITEM_KEY + PERSISTENT_ITEM_KEY = btrfsprim.PERSISTENT_ITEM_KEY + QGROUP_RELATION_KEY = btrfsprim.QGROUP_RELATION_KEY + ROOT_BACKREF_KEY = btrfsprim.ROOT_BACKREF_KEY + ROOT_ITEM_KEY = btrfsprim.ROOT_ITEM_KEY + ROOT_REF_KEY = btrfsprim.ROOT_REF_KEY + SHARED_BLOCK_REF_KEY = btrfsprim.SHARED_BLOCK_REF_KEY + SHARED_DATA_REF_KEY = btrfsprim.SHARED_DATA_REF_KEY + TREE_BLOCK_REF_KEY = btrfsprim.TREE_BLOCK_REF_KEY + UNTYPED_KEY = btrfsprim.UNTYPED_KEY + UUID_RECEIVED_SUBVOL_KEY = btrfsprim.UUID_RECEIVED_SUBVOL_KEY + UUID_SUBVOL_KEY = btrfsprim.UUID_SUBVOL_KEY + XATTR_ITEM_KEY = btrfsprim.XATTR_ITEM_KEY ) var keytype2gotype = map[Type]reflect.Type{ @@ -72,8 +72,8 @@ var keytype2gotype = map[Type]reflect.Type{ UUID_SUBVOL_KEY: reflect.TypeOf(UUIDMap{}), XATTR_ITEM_KEY: reflect.TypeOf(DirEntry{}), } -var untypedObjID2gotype = map[internal.ObjID]reflect.Type{ - internal.FREE_SPACE_OBJECTID: reflect.TypeOf(FreeSpaceHeader{}), +var untypedObjID2gotype = map[btrfsprim.ObjID]reflect.Type{ + btrfsprim.FREE_SPACE_OBJECTID: reflect.TypeOf(FreeSpaceHeader{}), } func (BlockGroup) isItem() {} diff --git a/lib/btrfs/btrfsitem/items_test.go b/lib/btrfs/btrfsitem/items_test.go index aba8ca2..46f2feb 100644 --- a/lib/btrfs/btrfsitem/items_test.go +++ b/lib/btrfs/btrfsitem/items_test.go @@ -11,12 +11,12 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" ) func FuzzRoundTrip(f *testing.F) { - keySize := binstruct.StaticSize(internal.Key{}) + keySize := binstruct.StaticSize(btrfsprim.Key{}) sumtypeSize := binstruct.StaticSize(btrfssum.CSumType(0)) f.Add(make([]byte, 256)) @@ -31,7 +31,7 @@ func FuzzRoundTrip(f *testing.F) { // key - var key internal.Key + var key btrfsprim.Key n, err := binstruct.Unmarshal(keyInDat, &key) require.NoError(t, err, "binstruct.Unmarshal(dat, &key)") require.Equal(t, keySize, n, "binstruct.Unmarshal(dat, &key)") diff --git a/lib/btrfs/btrfsprim/itemtype.go b/lib/btrfs/btrfsprim/itemtype.go new file mode 100644 index 0000000..89cff21 --- /dev/null +++ b/lib/btrfs/btrfsprim/itemtype.go @@ -0,0 +1,79 @@ +// Code generated by Make. DO NOT EDIT. + +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsprim + +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/btrfsprim/misc.go b/lib/btrfs/btrfsprim/misc.go new file mode 100644 index 0000000..0ebbe19 --- /dev/null +++ b/lib/btrfs/btrfsprim/misc.go @@ -0,0 +1,48 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsprim + +import ( + "fmt" + "time" + + "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" +) + +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 (k Key) String() string { + return fmt.Sprintf("{%v %v %v}", k.ObjectID, k.ItemType, k.Offset) +} + +func (a Key) Cmp(b Key) int { + if d := containers.NativeCmp(a.ObjectID, b.ObjectID); d != 0 { + return d + } + if d := containers.NativeCmp(a.ItemType, b.ItemType); d != 0 { + return d + } + return containers.NativeCmp(a.Offset, b.Offset) +} + +var _ containers.Ordered[Key] = Key{} + +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/btrfsprim/objid.go b/lib/btrfs/btrfsprim/objid.go new file mode 100644 index 0000000..17a0eeb --- /dev/null +++ b/lib/btrfs/btrfsprim/objid.go @@ -0,0 +1,148 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsprim + +import ( + "fmt" +) + +type ObjID uint64 + +const maxUint64pp = 0x1_00000000_00000000 + +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(maxUint64pp - 4) // for storing balance parameters in the root tree + ORPHAN_OBJECTID = ObjID(maxUint64pp - 5) // orphan objectid for tracking unlinked/truncated files + TREE_LOG_OBJECTID = ObjID(maxUint64pp - 6) // does write ahead logging to speed up fsyncs + TREE_LOG_FIXUP_OBJECTID = ObjID(maxUint64pp - 7) + TREE_RELOC_OBJECTID = ObjID(maxUint64pp - 8) // space balancing + DATA_RELOC_TREE_OBJECTID = ObjID(maxUint64pp - 9) + EXTENT_CSUM_OBJECTID = ObjID(maxUint64pp - 10) // extent checksums all have this objectid + FREE_SPACE_OBJECTID = ObjID(maxUint64pp - 11) // For storing free space cache + FREE_INO_OBJECTID = ObjID(maxUint64pp - 12) // stores the inode number for the free-ino cache + + MULTIPLE_OBJECTIDS = ObjID(maxUint64pp - 255) // dummy objectid represents multiple objectids + + // All files have objectids in this range. + FIRST_FREE_OBJECTID = ObjID(256) + LAST_FREE_OBJECTID = ObjID(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/btrfsprim/uuid.go b/lib/btrfs/btrfsprim/uuid.go new file mode 100644 index 0000000..4e3fd6b --- /dev/null +++ b/lib/btrfs/btrfsprim/uuid.go @@ -0,0 +1,96 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsprim + +import ( + "encoding" + "encoding/hex" + "fmt" + "strings" + + "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" +) + +type UUID [16]byte + +var ( + _ fmt.Stringer = UUID{} + _ fmt.Formatter = UUID{} + _ encoding.TextMarshaler = UUID{} + _ encoding.TextUnmarshaler = (*UUID)(nil) +) + +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 (uuid UUID) MarshalText() ([]byte, error) { + return []byte(uuid.String()), nil +} + +func (uuid *UUID) UnmarshalText(text []byte) error { + var err error + *uuid, err = ParseUUID(string(text)) + return err +} + +func (uuid UUID) Format(f fmt.State, verb rune) { + fmtutil.FormatByteArrayStringer(uuid, uuid[:], f, verb) +} + +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 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/btrfs/btrfsprim/uuid_test.go b/lib/btrfs/btrfsprim/uuid_test.go new file mode 100644 index 0000000..9fff760 --- /dev/null +++ b/lib/btrfs/btrfsprim/uuid_test.go @@ -0,0 +1,67 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsprim_test + +import ( + "fmt" + "testing" + + "github.com/stretchr/testify/assert" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" +) + +func TestParseUUID(t *testing.T) { + t.Parallel() + type TestCase struct { + Input string + OutputVal btrfsprim.UUID + OutputErr string + } + testcases := map[string]TestCase{ + "basic": {Input: "a0dd94ed-e60c-42e8-8632-64e8d4765a43", OutputVal: btrfsprim.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 := btrfsprim.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 btrfsprim.UUID + InputFmt string + Output string + } + uuid := btrfsprim.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: "| btrfsprim.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) + }) + } +} diff --git a/lib/btrfs/btrfstree/ops.go b/lib/btrfs/btrfstree/ops.go new file mode 100644 index 0000000..83c08c4 --- /dev/null +++ b/lib/btrfs/btrfstree/ops.go @@ -0,0 +1,519 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree + +import ( + "context" + "errors" + "fmt" + iofs "io/fs" + "math" + + "github.com/datawire/dlib/derror" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" +) + +type Trees interface { + // TreeWalk walks a tree, triggering callbacks for every node, + // key-pointer, and item; as well as for any errors encountered. + // + // If the tree is valid, then everything is walked in key-order; but if + // the tree is broken, then ordering is not guaranteed. + // + // Canceling the Context causes TreeWalk to return early; no + // values from the Context are used. + // + // The lifecycle of callbacks is: + // + // 001 .PreNode() + // 002 (read node) + // 003 .Node() (or .BadNode()) + // for item in node.items: + // if btrfsprim: + // 004 .PreKeyPointer() + // 005 (recurse) + // 006 .PostKeyPointer() + // else: + // 004 .Item() (or .BadItem()) + // 007 .PostNode() + TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) + + TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) + TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (Item, error) // size is math.MaxUint32 for key-pointers + + // If some items are able to be read, but there is an error reading the + // full set, then it might return *both* a list of items and an error. + // + // If no such item is found, an error that is io/fs.ErrNotExist is + // returned. + TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]Item, error) // size is math.MaxUint32 for key-pointers +} + +type TreeWalkHandler struct { + // Callbacks for entire nodes. + // + // If any of these return an error that is io/fs.SkipDir, the + // node immediately stops getting processed; if PreNode, Node, + // or BadNode return io/fs.SkipDir then key pointers and items + // within the node are not processed. + PreNode func(TreePath) error + Node func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error + BadNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) error + PostNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error + // Callbacks for items on btrfsprim nodes + PreKeyPointer func(TreePath, KeyPointer) error + PostKeyPointer func(TreePath, KeyPointer) error + // Callbacks for items on leaf nodes + Item func(TreePath, Item) error + BadItem func(TreePath, Item) error +} + +type TreeError struct { + Path TreePath + Err error +} + +func (e *TreeError) Unwrap() error { return e.Err } + +func (e *TreeError) Error() string { + return fmt.Sprintf("%v: %v", e.Path, e.Err) +} + +type NodeSource interface { + Superblock() (*Superblock, error) + ReadNode(TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) +} + +type TreesImpl struct { + NodeSource +} + +// TreeWalk implements the 'Trees' interface. +func (fs TreesImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { + sb, err := fs.Superblock() + if err != nil { + errHandle(&TreeError{Path: TreePath{{FromTree: treeID}}, Err: err}) + } + rootInfo, err := LookupTreeRoot(fs, *sb, treeID) + if err != nil { + errHandle(&TreeError{Path: TreePath{{FromTree: treeID}}, Err: err}) + return + } + fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs) +} + +// TreeWalk is a utility function to help with implementing the 'Trees' +// interface. +func (fs TreesImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { + path := TreePath{{ + FromTree: rootInfo.TreeID, + FromGeneration: rootInfo.Generation, + FromItemIdx: -1, + ToNodeAddr: rootInfo.RootNode, + ToNodeLevel: rootInfo.Level, + }} + fs.treeWalk(ctx, path, errHandle, cbs) +} + +func (fs TreesImpl) treeWalk(ctx context.Context, path TreePath, errHandle func(*TreeError), cbs TreeWalkHandler) { + if ctx.Err() != nil { + return + } + if path.Node(-1).ToNodeAddr == 0 { + return + } + + if cbs.PreNode != nil { + if err := cbs.PreNode(path); err != nil { + if errors.Is(err, iofs.SkipDir) { + return + } + errHandle(&TreeError{Path: path, Err: err}) + } + if ctx.Err() != nil { + return + } + } + node, err := fs.ReadNode(path) + if ctx.Err() != nil { + return + } + if err != nil && node != nil && cbs.BadNode != nil { + // opportunity to fix the node + err = cbs.BadNode(path, node, err) + if errors.Is(err, iofs.SkipDir) { + return + } + } + if err != nil { + errHandle(&TreeError{Path: path, Err: err}) + } else { + if cbs.Node != nil { + if err := cbs.Node(path, node); err != nil { + if errors.Is(err, iofs.SkipDir) { + return + } + errHandle(&TreeError{Path: path, Err: err}) + } + } + } + if ctx.Err() != nil { + return + } + if node != nil { + for i, item := range node.Data.BodyInternal { + itemPath := append(path, TreePathElem{ + FromTree: node.Data.Head.Owner, + FromGeneration: node.Data.Head.Generation, + FromItemIdx: i, + ToNodeAddr: item.BlockPtr, + ToNodeLevel: node.Data.Head.Level - 1, + }) + if cbs.PreKeyPointer != nil { + if err := cbs.PreKeyPointer(itemPath, item); err != nil { + errHandle(&TreeError{Path: itemPath, Err: err}) + } + if ctx.Err() != nil { + return + } + } + fs.treeWalk(ctx, itemPath, errHandle, cbs) + if cbs.PostKeyPointer != nil { + if err := cbs.PostKeyPointer(itemPath, item); err != nil { + errHandle(&TreeError{Path: itemPath, Err: err}) + } + if ctx.Err() != nil { + return + } + } + } + for i, item := range node.Data.BodyLeaf { + itemPath := append(path, TreePathElem{ + FromTree: node.Data.Head.Owner, + FromGeneration: node.Data.Head.Generation, + FromItemIdx: i, + }) + if errBody, isErr := item.Body.(btrfsitem.Error); isErr { + if cbs.BadItem == nil { + errHandle(&TreeError{Path: itemPath, Err: errBody.Err}) + } else { + if err := cbs.BadItem(itemPath, item); err != nil { + errHandle(&TreeError{Path: itemPath, Err: err}) + } + if ctx.Err() != nil { + return + } + } + } else { + if cbs.Item != nil { + if err := cbs.Item(itemPath, item); err != nil { + errHandle(&TreeError{Path: itemPath, Err: err}) + } + if ctx.Err() != nil { + return + } + } + } + } + } + if cbs.PostNode != nil { + if err := cbs.PostNode(path, node); err != nil { + if errors.Is(err, iofs.SkipDir) { + return + } + errHandle(&TreeError{Path: path, Err: err}) + } + } +} + +func (fs TreesImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { + path := TreePath{{ + FromTree: treeRoot.TreeID, + FromGeneration: treeRoot.Generation, + FromItemIdx: -1, + ToNodeAddr: treeRoot.RootNode, + ToNodeLevel: treeRoot.Level, + }} + for { + if path.Node(-1).ToNodeAddr == 0 { + return TreePath{}, nil, iofs.ErrNotExist + } + node, err := fs.ReadNode(path) + if err != nil { + return TreePath{}, nil, err + } + + if node.Data.Head.Level > 0 { + // btrfsprim node + + // Search for the right-most node.Data.BodyInternal item for which + // `fn(item.Key) >= 0`. + // + // + + + + 0 - - - - + // + // There may or may not be a value that returns '0'. + // + // i.e. find the highest value that isn't too high. + lastGood, ok := slices.SearchHighest(node.Data.BodyInternal, func(kp KeyPointer) int { + return slices.Min(fn(kp.Key, math.MaxUint32), 0) // don't return >0; a key can't be "too low" + }) + if !ok { + return TreePath{}, nil, iofs.ErrNotExist + } + path = append(path, TreePathElem{ + FromTree: node.Data.Head.Owner, + FromGeneration: node.Data.Head.Generation, + FromItemIdx: lastGood, + ToNodeAddr: node.Data.BodyInternal[lastGood].BlockPtr, + ToNodeLevel: node.Data.Head.Level - 1, + }) + } else { + // leaf node + + // Search for a member of node.Data.BodyLeaf for which + // `fn(item.Head.Key) == 0`. + // + // + + + + 0 - - - - + // + // Such an item might not exist; in this case, return nil/ErrNotExist. + // Multiple such items might exist; in this case, it does not matter which + // is returned. + // + // Implement this search as a binary search. + idx, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int { + return fn(item.Key, item.BodySize) + }) + if !ok { + return TreePath{}, nil, iofs.ErrNotExist + } + path = append(path, TreePathElem{ + FromTree: node.Data.Head.Owner, + FromGeneration: node.Data.Head.Generation, + FromItemIdx: idx, + }) + return path, node, nil + } + } +} + +func (fs TreesImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { + var err error + path = path.DeepCopy() + + // go up + for path.Node(-1).FromItemIdx < 1 { + path = path.Parent() + if len(path) == 0 { + return TreePath{}, nil, nil + } + } + // go left + path.Node(-1).FromItemIdx-- + if path.Node(-1).ToNodeAddr != 0 { + if node.Addr != path.Node(-2).ToNodeAddr { + node, err = fs.ReadNode(path.Parent()) + if err != nil { + return TreePath{}, nil, err + } + path.Node(-1).ToNodeAddr = node.Data.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr + } + } + // go down + for path.Node(-1).ToNodeAddr != 0 { + if node.Addr != path.Node(-1).ToNodeAddr { + node, err = fs.ReadNode(path) + if err != nil { + return TreePath{}, nil, err + } + } + if node.Data.Head.Level > 0 { + path = append(path, TreePathElem{ + FromTree: node.Data.Head.Owner, + FromGeneration: node.Data.Head.Generation, + FromItemIdx: len(node.Data.BodyInternal) - 1, + ToNodeAddr: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr, + ToNodeLevel: node.Data.Head.Level - 1, + }) + } else { + path = append(path, TreePathElem{ + FromTree: node.Data.Head.Owner, + FromGeneration: node.Data.Head.Generation, + FromItemIdx: len(node.Data.BodyLeaf) - 1, + }) + } + } + // return + if node.Addr != path.Node(-2).ToNodeAddr { + node, err = fs.ReadNode(path.Parent()) + if err != nil { + return TreePath{}, nil, err + } + } + return path, node, nil +} + +func (fs TreesImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { + var err error + path = path.DeepCopy() + + // go up + if node.Addr != path.Node(-2).ToNodeAddr { + node, err = fs.ReadNode(path.Parent()) + if err != nil { + return TreePath{}, nil, err + } + path.Node(-2).ToNodeLevel = node.Data.Head.Level + } + for path.Node(-1).FromItemIdx+1 >= int(node.Data.Head.NumItems) { + path = path.Parent() + if len(path) == 1 { + return TreePath{}, nil, nil + } + if node.Addr != path.Node(-2).ToNodeAddr { + node, err = fs.ReadNode(path.Parent()) + if err != nil { + return TreePath{}, nil, err + } + path.Node(-2).ToNodeLevel = node.Data.Head.Level + } + } + // go right + path.Node(-1).FromItemIdx++ + if path.Node(-1).ToNodeAddr != 0 { + if node.Addr != path.Node(-2).ToNodeAddr { + node, err = fs.ReadNode(path.Parent()) + if err != nil { + return TreePath{}, nil, err + } + path.Node(-1).ToNodeAddr = node.Data.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr + } + } + // go down + for path.Node(-1).ToNodeAddr != 0 { + if node.Addr != path.Node(-1).ToNodeAddr { + node, err = fs.ReadNode(path) + if err != nil { + return TreePath{}, nil, err + } + path.Node(-1).ToNodeLevel = node.Data.Head.Level + } + if node.Data.Head.Level > 0 { + path = append(path, TreePathElem{ + FromTree: node.Data.Head.Owner, + FromGeneration: node.Data.Head.Generation, + FromItemIdx: 0, + ToNodeAddr: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr, + ToNodeLevel: node.Data.Head.Level - 1, + }) + } else { + path = append(path, TreePathElem{ + FromTree: node.Data.Head.Owner, + FromGeneration: node.Data.Head.Generation, + FromItemIdx: 0, + }) + } + } + // return + if node.Addr != path.Node(-2).ToNodeAddr { + node, err = fs.ReadNode(path.Parent()) + if err != nil { + return TreePath{}, nil, err + } + } + return path, node, nil +} + +// TreeSearch implements the 'Trees' interface. +func (fs TreesImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) { + sb, err := fs.Superblock() + if err != nil { + return Item{}, err + } + rootInfo, err := LookupTreeRoot(fs, *sb, treeID) + if err != nil { + return Item{}, err + } + path, node, err := fs.treeSearch(*rootInfo, fn) + if err != nil { + return Item{}, err + } + return node.Data.BodyLeaf[path.Node(-1).FromItemIdx], nil +} + +// KeySearch returns a comparator suitable to be passed to TreeSearch. +func KeySearch(fn func(btrfsprim.Key) int) func(btrfsprim.Key, uint32) int { + return func(key btrfsprim.Key, _ uint32) int { + return fn(key) + } +} + +// TreeLookup implements the 'Trees' interface. +func (fs TreesImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { + item, err := fs.TreeSearch(treeID, KeySearch(key.Cmp)) + if err != nil { + err = fmt.Errorf("item with key=%v: %w", key, err) + } + return item, err +} + +// TreeSearchAll implements the 'Trees' interface. +func (fs TreesImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) { + sb, err := fs.Superblock() + if err != nil { + return nil, err + } + rootInfo, err := LookupTreeRoot(fs, *sb, treeID) + if err != nil { + return nil, err + } + middlePath, middleNode, err := fs.treeSearch(*rootInfo, fn) + if err != nil { + return nil, err + } + middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemIdx] + + var ret = []Item{middleItem} + var errs derror.MultiError + for prevPath, prevNode := middlePath, middleNode; true; { + prevPath, prevNode, err = fs.prev(prevPath, prevNode) + if err != nil { + errs = append(errs, err) + break + } + if len(prevPath) == 0 { + break + } + prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemIdx] + if fn(prevItem.Key, prevItem.BodySize) != 0 { + break + } + ret = append(ret, prevItem) + } + slices.Reverse(ret) + for nextPath, nextNode := middlePath, middleNode; true; { + nextPath, nextNode, err = fs.next(nextPath, nextNode) + if err != nil { + errs = append(errs, err) + break + } + if len(nextPath) == 0 { + break + } + nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemIdx] + if fn(nextItem.Key, nextItem.BodySize) != 0 { + break + } + ret = append(ret, nextItem) + } + if errs != nil { + err = errs + } + return ret, err +} diff --git a/lib/btrfs/btrfstree/path.go b/lib/btrfs/btrfstree/path.go new file mode 100644 index 0000000..99461a4 --- /dev/null +++ b/lib/btrfs/btrfstree/path.go @@ -0,0 +1,129 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree + +import ( + "fmt" + "io" + "strings" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" +) + +// - The first element will always have an ItemIdx of -1. +// +// - For .Item() callbacks, the last element will always have a +// NodeAddr of 0. +// +// For example, a path through a tree, with the associated PathElems: +// +// [superblock: tree=B, lvl=3, gen=6] +// | +// | <------------------------------------------ pathElem={from_tree:B, from_gen=6, from_idx=-1, +// | to_addr:0x01, to_lvl=3} +// +[0x01]-------------+ +// | lvl=3 gen=6 own=B | +// +-+-+-+-+-+-+-+-+-+-+ +// |0|1|2|3|4|5|6|7|8|9| +// +-+-+-+-+-+-+-+-+-+-+ +// | +// | <------------------------------ pathElem:{from_tree:B, from_gen:6, from_idx:7, +// | to_addr:0x02, to_lvl:2} +// +[0x02]--------------+ +// | lvl=2 gen=5 own=B | +// +-+-+-+-+-+-+-+-+-+-+ +// |0|1|2|3|4|5|6|7|8|9| +// +-+-+-+-+-+-+-+-+-+-+ +// | +// | <-------------------- pathElem={from_tree:B, from_gen:5, from_idx:6, +// | to_addr:0x03, to_lvl:1} +// +[0x03]-------------+ +// | lvl=1 gen=5 own=A | +// +-+-+-+-+-+-+-+-+-+-+ +// |0|1|2|3|4|5|6|7|8|9| +// +-+-+-+-+-+-+-+-+-+-+ +// | +// | <---------------- pathElem={from_tree:A, from_gen:5, from_idx:3, +// | to_addr:0x04, to_lvl:0} +// +[0x04]-------------+ +// | lvl=0 gen=2 own=A | +// +-+-+-+-+-+-+-+-+-+-+ +// |0|1|2|3|4|5|6|7|8|9| +// +-+-+-+-+-+-+-+-+-+-+ +// | +// | <--------------- pathElem={from_tree:A, from_gen:2, from_idx:1, +// | to_addr:0, to_lvl:0} +// [item] +type TreePath []TreePathElem + +// A TreePathElem essentially represents a KeyPointer. If there is an +// error looking up the tree root, everything but FromTree is zero. +type TreePathElem struct { + // FromTree is the owning tree ID of the parent node; or the + // well-known tree ID if this is the root. + FromTree btrfsprim.ObjID + // FromGeneration is the generation of the parent node the + // parent node; or generation stored in the superblock if this + // is the root. + FromGeneration btrfsprim.Generation + // FromItemIdx is the index of this KeyPointer in the parent + // Node; or -1 if this is the root and there is no KeyPointer. + FromItemIdx int + + // ToNodeAddr is the address of the node that the KeyPointer + // points at, or 0 if this is a leaf item and nothing is being + // pointed at. + ToNodeAddr btrfsvol.LogicalAddr + // ToNodeLevel is the expected or actual level of the node at + // ToNodeAddr, or 0 if this is a leaf item and nothing is + // being pointed at. + ToNodeLevel uint8 +} + +func (elem TreePathElem) writeNodeTo(w io.Writer) { + fmt.Fprintf(w, "node:%d@%v", elem.ToNodeLevel, elem.ToNodeAddr) +} + +func (path TreePath) String() string { + if len(path) == 0 { + return "(empty-path)" + } else { + var ret strings.Builder + fmt.Fprintf(&ret, "%s->", path[0].FromTree.Format(btrfsitem.ROOT_ITEM_KEY)) + if len(path) == 1 && path[0] == (TreePathElem{FromTree: path[0].FromTree}) { + ret.WriteString("(empty-path)") + } else { + path[0].writeNodeTo(&ret) + } + for _, elem := range path[1:] { + fmt.Fprintf(&ret, "[%v]", elem.FromItemIdx) + if elem.ToNodeAddr != 0 { + ret.WriteString("->") + elem.writeNodeTo(&ret) + } + } + return ret.String() + } +} + +func (path TreePath) DeepCopy() TreePath { + return append(TreePath(nil), path...) +} + +func (path TreePath) Parent() TreePath { + return path[:len(path)-1] +} + +// path.Node(x) is like &path[x], but negative values of x move down +// from the end of path (similar to how lists work in many other +// languages, such as Python). +func (path TreePath) Node(x int) *TreePathElem { + if x < 0 { + x += len(path) + } + return &path[x] +} diff --git a/lib/btrfs/btrfstree/root.go b/lib/btrfs/btrfstree/root.go new file mode 100644 index 0000000..41aac69 --- /dev/null +++ b/lib/btrfs/btrfstree/root.go @@ -0,0 +1,81 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree + +import ( + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" +) + +// A TreeRoot is more-or-less a btrfsitem.Root, but simpler; returned by +// LookupTreeRoot. +type TreeRoot struct { + TreeID btrfsprim.ObjID + RootNode btrfsvol.LogicalAddr + Level uint8 + Generation btrfsprim.Generation +} + +// LookupTreeRoot is a utility function to help with implementing the 'Trees' +// interface. +func LookupTreeRoot(fs Trees, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error) { + switch treeID { + case btrfsprim.ROOT_TREE_OBJECTID: + return &TreeRoot{ + TreeID: treeID, + RootNode: sb.RootTree, + Level: sb.RootLevel, + Generation: sb.Generation, // XXX: same generation as LOG_TREE? + }, nil + case btrfsprim.CHUNK_TREE_OBJECTID: + return &TreeRoot{ + TreeID: treeID, + RootNode: sb.ChunkTree, + Level: sb.ChunkLevel, + Generation: sb.ChunkRootGeneration, + }, nil + case btrfsprim.TREE_LOG_OBJECTID: + return &TreeRoot{ + TreeID: treeID, + RootNode: sb.LogTree, + Level: sb.LogLevel, + Generation: sb.Generation, // XXX: same generation as ROOT_TREE? + }, nil + case btrfsprim.BLOCK_GROUP_TREE_OBJECTID: + return &TreeRoot{ + TreeID: treeID, + RootNode: sb.BlockGroupRoot, + Level: sb.BlockGroupRootLevel, + Generation: sb.BlockGroupRootGeneration, + }, nil + default: + rootItem, err := fs.TreeSearch(btrfsprim.ROOT_TREE_OBJECTID, func(key btrfsprim.Key, _ uint32) int { + if key.ObjectID == treeID && key.ItemType == btrfsitem.ROOT_ITEM_KEY { + return 0 + } + return btrfsprim.Key{ + ObjectID: treeID, + ItemType: btrfsitem.ROOT_ITEM_KEY, + Offset: 0, + }.Cmp(key) + }) + if err != nil { + return nil, err + } + rootItemBody, ok := rootItem.Body.(btrfsitem.Root) + if !ok { + return nil, fmt.Errorf("malformed ROOT_ITEM for tree %v", treeID) + } + return &TreeRoot{ + TreeID: treeID, + RootNode: rootItemBody.ByteNr, + Level: rootItemBody.Level, + Generation: rootItemBody.Generation, + }, nil + } +} diff --git a/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 new file mode 100644 index 0000000..a96f559 --- /dev/null +++ b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 @@ -0,0 +1,2 @@ +go test fuzz v1 +[]byte("0") diff --git a/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca new file mode 100644 index 0000000..d5c153f --- /dev/null +++ b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca @@ -0,0 +1,2 @@ +go test fuzz v1 +[]byte("000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\x00\x00\x00\x000") diff --git a/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 new file mode 100644 index 0000000..6a2309e --- /dev/null +++ b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 @@ -0,0 +1,2 @@ +go test fuzz v1 +[]byte("00000000000000000000000000000000000000000000000000000000") diff --git a/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 new file mode 100644 index 0000000..50b960e --- /dev/null +++ b/lib/btrfs/btrfstree/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 @@ -0,0 +1,2 @@ +go test fuzz v1 +[]byte("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000") diff --git a/lib/btrfs/btrfstree/types_node.go b/lib/btrfs/btrfstree/types_node.go new file mode 100644 index 0000000..aecdf9c --- /dev/null +++ b/lib/btrfs/btrfstree/types_node.go @@ -0,0 +1,454 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree + +import ( + "encoding/binary" + "errors" + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/diskio" + "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" +) + +type NodeFlags uint64 + +func (NodeFlags) BinaryStaticSize() int { + return 7 +} +func (f NodeFlags) MarshalBinary() ([]byte, error) { + var bs [8]byte + binary.LittleEndian.PutUint64(bs[:], uint64(f)) + return bs[:7], nil +} +func (f *NodeFlags) UnmarshalBinary(dat []byte) (int, error) { + var bs [8]byte + copy(bs[:7], dat[:7]) + *f = NodeFlags(binary.LittleEndian.Uint64(bs[:])) + return 7, nil +} + +var ( + _ binstruct.StaticSizer = NodeFlags(0) + _ binstruct.Marshaler = NodeFlags(0) + _ binstruct.Unmarshaler = (*NodeFlags)(nil) +) + +const ( + NodeWritten = NodeFlags(1 << iota) + NodeReloc +) + +var nodeFlagNames = []string{ + "WRITTEN", + "RELOC", +} + +func (f NodeFlags) Has(req NodeFlags) bool { return f&req == req } +func (f NodeFlags) String() string { return fmtutil.BitfieldString(f, nodeFlagNames, fmtutil.HexLower) } + +type BackrefRev uint8 + +const ( + OldBackrefRev = BackrefRev(iota) + MixedBackrefRev = BackrefRev(iota) +) + +// Node: main ////////////////////////////////////////////////////////////////////////////////////// + +type Node struct { + // Some context from the parent filesystem + Size uint32 // superblock.NodeSize + ChecksumType btrfssum.CSumType // superblock.ChecksumType + + // The node's header (always present) + Head NodeHeader + + // The node's body (which one of these is present depends on + // the node's type, as specified in the header) + BodyInternal []KeyPointer // for btrfsprim nodes + BodyLeaf []Item // for leave nodes + + Padding []byte +} + +type NodeHeader struct { + Checksum btrfssum.CSum `bin:"off=0x0, siz=0x20"` + MetadataUUID btrfsprim.UUID `bin:"off=0x20, siz=0x10"` + Addr btrfsvol.LogicalAddr `bin:"off=0x30, siz=0x8"` // Logical address of this node + Flags NodeFlags `bin:"off=0x38, siz=0x7"` + BackrefRev BackrefRev `bin:"off=0x3f, siz=0x1"` + ChunkTreeUUID btrfsprim.UUID `bin:"off=0x40, siz=0x10"` + Generation btrfsprim.Generation `bin:"off=0x50, siz=0x8"` + Owner btrfsprim.ObjID `bin:"off=0x58, siz=0x8"` // The ID of the tree that contains this node + NumItems uint32 `bin:"off=0x60, siz=0x4"` // [ignored-when-writing] + Level uint8 `bin:"off=0x64, siz=0x1"` // 0 for leaf nodes, >=1 for btrfsprim nodes + binstruct.End `bin:"off=0x65"` +} + +// MaxItems returns the maximum possible valid value of +// .Head.NumItems. +func (node Node) MaxItems() uint32 { + bodyBytes := node.Size - uint32(binstruct.StaticSize(NodeHeader{})) + if node.Head.Level > 0 { + return bodyBytes / uint32(binstruct.StaticSize(KeyPointer{})) + } else { + return bodyBytes / uint32(binstruct.StaticSize(ItemHeader{})) + } +} + +func (node Node) MinItem() (btrfsprim.Key, bool) { + if node.Head.Level > 0 { + if len(node.BodyInternal) == 0 { + return btrfsprim.Key{}, false + } + return node.BodyInternal[0].Key, true + } else { + if len(node.BodyLeaf) == 0 { + return btrfsprim.Key{}, false + } + return node.BodyLeaf[0].Key, true + } +} + +func (node Node) MaxItem() (btrfsprim.Key, bool) { + if node.Head.Level > 0 { + if len(node.BodyInternal) == 0 { + return btrfsprim.Key{}, false + } + return node.BodyInternal[len(node.BodyInternal)-1].Key, true + } else { + if len(node.BodyLeaf) == 0 { + return btrfsprim.Key{}, false + } + return node.BodyLeaf[len(node.BodyLeaf)-1].Key, true + } +} + +func (node Node) CalculateChecksum() (btrfssum.CSum, error) { + data, err := binstruct.Marshal(node) + if err != nil { + return btrfssum.CSum{}, err + } + return node.ChecksumType.Sum(data[binstruct.StaticSize(btrfssum.CSum{}):]) +} + +func (node Node) ValidateChecksum() error { + stored := node.Head.Checksum + calced, err := node.CalculateChecksum() + if err != nil { + return err + } + if calced != stored { + return fmt.Errorf("node checksum mismatch: stored=%v calculated=%v", + stored, calced) + } + return nil +} + +func (node *Node) UnmarshalBinary(nodeBuf []byte) (int, error) { + *node = Node{ + Size: uint32(len(nodeBuf)), + ChecksumType: node.ChecksumType, + } + if len(nodeBuf) <= binstruct.StaticSize(NodeHeader{}) { + return 0, fmt.Errorf("size must be greater than %v, but is %v", + binstruct.StaticSize(NodeHeader{}), + len(nodeBuf)) + } + n, err := binstruct.Unmarshal(nodeBuf, &node.Head) + if err != nil { + return n, err + } else if n != binstruct.StaticSize(NodeHeader{}) { + return n, fmt.Errorf("header consumed %v bytes but expected %v", + n, binstruct.StaticSize(NodeHeader{})) + } + if node.Head.Level > 0 { + _n, err := node.unmarshalInternal(nodeBuf[n:]) + n += _n + if err != nil { + return n, fmt.Errorf("btrfsprim: %w", err) + } + } else { + _n, err := node.unmarshalLeaf(nodeBuf[n:]) + n += _n + if err != nil { + return n, fmt.Errorf("leaf: %w", err) + } + } + if n != len(nodeBuf) { + return n, fmt.Errorf("left over data: got %v bytes but only consumed %v", + len(nodeBuf), n) + } + return n, nil +} + +func (node Node) MarshalBinary() ([]byte, error) { + if node.Size == 0 { + return nil, fmt.Errorf(".Size must be set") + } + if node.Size <= uint32(binstruct.StaticSize(NodeHeader{})) { + return nil, fmt.Errorf(".Size must be greater than %v, but is %v", + binstruct.StaticSize(NodeHeader{}), + node.Size) + } + if node.Head.Level > 0 { + node.Head.NumItems = uint32(len(node.BodyInternal)) + } else { + node.Head.NumItems = uint32(len(node.BodyLeaf)) + } + + buf := make([]byte, node.Size) + + if bs, err := binstruct.Marshal(node.Head); err != nil { + return buf, err + } else if len(bs) != binstruct.StaticSize(NodeHeader{}) { + return nil, fmt.Errorf("header is %v bytes but expected %v", + len(bs), binstruct.StaticSize(NodeHeader{})) + } else { + copy(buf, bs) + } + + if node.Head.Level > 0 { + if err := node.marshalInternalTo(buf[binstruct.StaticSize(NodeHeader{}):]); err != nil { + return buf, err + } + } else { + if err := node.marshalLeafTo(buf[binstruct.StaticSize(NodeHeader{}):]); err != nil { + return buf, err + } + } + + return buf, nil +} + +// Node: "btrfsprim" //////////////////////////////////////////////////////////////////////////////// + +type KeyPointer struct { + Key btrfsprim.Key `bin:"off=0x0, siz=0x11"` + BlockPtr btrfsvol.LogicalAddr `bin:"off=0x11, siz=0x8"` + Generation btrfsprim.Generation `bin:"off=0x19, siz=0x8"` + binstruct.End `bin:"off=0x21"` +} + +func (node *Node) unmarshalInternal(bodyBuf []byte) (int, error) { + n := 0 + for i := uint32(0); i < node.Head.NumItems; i++ { + var item KeyPointer + _n, err := binstruct.Unmarshal(bodyBuf[n:], &item) + n += _n + if err != nil { + return n, fmt.Errorf("item %v: %w", i, err) + } + node.BodyInternal = append(node.BodyInternal, item) + } + node.Padding = bodyBuf[n:] + return len(bodyBuf), nil +} + +func (node *Node) marshalInternalTo(bodyBuf []byte) error { + n := 0 + for i, item := range node.BodyInternal { + bs, err := binstruct.Marshal(item) + if err != nil { + return fmt.Errorf("item %v: %w", i, err) + } + if copy(bodyBuf[n:], bs) < len(bs) { + return fmt.Errorf("item %v: not enough space: need at least %v+%v=%v bytes, but only have %v", + i, n, len(bs), n+len(bs), len(bodyBuf)) + } + n += len(bs) + } + if copy(bodyBuf[n:], node.Padding) < len(node.Padding) { + return fmt.Errorf("padding: not enough space: need at least %v+%v=%v bytes, but only have %v", + n, len(node.Padding), n+len(node.Padding), len(bodyBuf)) + } + return nil +} + +// Node: "leaf" //////////////////////////////////////////////////////////////////////////////////// + +type Item struct { + Key btrfsprim.Key + BodySize uint32 // [ignored-when-writing] + Body btrfsitem.Item +} + +type ItemHeader struct { + Key btrfsprim.Key `bin:"off=0x0, siz=0x11"` + DataOffset uint32 `bin:"off=0x11, siz=0x4"` // [ignored-when-writing] relative to the end of the header (0x65) + DataSize uint32 `bin:"off=0x15, siz=0x4"` // [ignored-when-writing] + binstruct.End `bin:"off=0x19"` +} + +func (node *Node) unmarshalLeaf(bodyBuf []byte) (int, error) { + head := 0 + tail := len(bodyBuf) + for i := uint32(0); i < node.Head.NumItems; i++ { + var itemHead ItemHeader + n, err := binstruct.Unmarshal(bodyBuf[head:], &itemHead) + head += n + if err != nil { + return 0, fmt.Errorf("item %v: head: %w", i, err) + } + if head > tail { + return 0, fmt.Errorf("item %v: head: end_offset=%#x is in the body section (offset>%#x)", + i, head, tail) + } + + dataOff := int(itemHead.DataOffset) + if dataOff < head { + return 0, fmt.Errorf("item %v: body: beg_offset=%#x is in the head section (offset<%#x)", + i, dataOff, head) + } + dataSize := int(itemHead.DataSize) + if dataOff+dataSize != tail { + return 0, fmt.Errorf("item %v: body: end_offset=%#x is not cur_tail=%#x)", + i, dataOff+dataSize, tail) + } + tail = dataOff + dataBuf := bodyBuf[dataOff : dataOff+dataSize] + + node.BodyLeaf = append(node.BodyLeaf, Item{ + Key: itemHead.Key, + BodySize: itemHead.DataSize, + Body: btrfsitem.UnmarshalItem(itemHead.Key, node.ChecksumType, dataBuf), + }) + } + + node.Padding = bodyBuf[head:tail] + return len(bodyBuf), nil +} + +func (node *Node) marshalLeafTo(bodyBuf []byte) error { + head := 0 + tail := len(bodyBuf) + for i, item := range node.BodyLeaf { + itemBodyBuf, err := binstruct.Marshal(item.Body) + if err != nil { + return fmt.Errorf("item %v: body: %w", i, err) + } + itemHeadBuf, err := binstruct.Marshal(ItemHeader{ + Key: item.Key, + DataSize: uint32(len(itemBodyBuf)), + DataOffset: uint32(tail - len(itemBodyBuf)), + }) + if err != nil { + return fmt.Errorf("item %v: head: %w", i, err) + } + + if tail-head < len(itemHeadBuf)+len(itemBodyBuf) { + return fmt.Errorf("item %v: not enough space: need at least (head_len:%v)+(body_len:%v)=%v free bytes, but only have %v", + i, len(itemHeadBuf), len(itemBodyBuf), len(itemHeadBuf)+len(itemBodyBuf), tail-head) + } + + copy(bodyBuf[head:], itemHeadBuf) + head += len(itemHeadBuf) + tail -= len(itemBodyBuf) + copy(bodyBuf[tail:], itemBodyBuf) + } + if copy(bodyBuf[head:tail], node.Padding) < len(node.Padding) { + return fmt.Errorf("padding: not enough space: need at least %v free bytes, but only have %v", + len(node.Padding), tail-head) + } + return nil +} + +func (node *Node) LeafFreeSpace() uint32 { + if node.Head.Level > 0 { + panic(fmt.Errorf("Node.LeafFreeSpace: not a leaf node")) + } + freeSpace := node.Size + freeSpace -= uint32(binstruct.StaticSize(NodeHeader{})) + for _, item := range node.BodyLeaf { + freeSpace -= uint32(binstruct.StaticSize(ItemHeader{})) + bs, _ := binstruct.Marshal(item.Body) + freeSpace -= uint32(len(bs)) + } + return freeSpace +} + +// Tie Nodes in to the FS ////////////////////////////////////////////////////////////////////////// + +var ErrNotANode = errors.New("does not look like a node") + +type NodeExpectations struct { + LAddr containers.Optional[btrfsvol.LogicalAddr] + // Things knowable from the parent. + Level containers.Optional[uint8] + MaxGeneration containers.Optional[btrfsprim.Generation] + Owner []btrfsprim.ObjID +} + +func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp NodeExpectations) (*diskio.Ref[Addr, Node], error) { + nodeBuf := make([]byte, sb.NodeSize) + if _, err := fs.ReadAt(nodeBuf, addr); err != nil { + return nil, err + } + + // parse (early) + + nodeRef := &diskio.Ref[Addr, Node]{ + File: fs, + Addr: addr, + Data: Node{ + Size: sb.NodeSize, + ChecksumType: sb.ChecksumType, + }, + } + if _, err := binstruct.Unmarshal(nodeBuf, &nodeRef.Data.Head); err != nil { + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err) + } + + // sanity checking + + if nodeRef.Data.Head.MetadataUUID != sb.EffectiveMetadataUUID() { + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, ErrNotANode) + } + + stored := nodeRef.Data.Head.Checksum + calced, err := nodeRef.Data.ChecksumType.Sum(nodeBuf[binstruct.StaticSize(btrfssum.CSum{}):]) + if err != nil { + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err) + } + if stored != calced { + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: looks like a node but is corrupt: checksum mismatch: stored=%v calculated=%v", + addr, stored, calced) + } + + if exp.LAddr.OK && nodeRef.Data.Head.Addr != exp.LAddr.Val { + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: read from laddr=%v but claims to be at laddr=%v", + addr, exp.LAddr.Val, nodeRef.Data.Head.Addr) + } + if exp.Level.OK && nodeRef.Data.Head.Level != exp.Level.Val { + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected level=%v but claims to be level=%v", + addr, exp.Level.Val, nodeRef.Data.Head.Level) + } + if exp.MaxGeneration.OK && nodeRef.Data.Head.Generation > exp.MaxGeneration.Val { + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected generation<=%v but claims to be generation=%v", + addr, exp.MaxGeneration.Val, nodeRef.Data.Head.Generation) + } + if len(exp.Owner) > 0 && !slices.Contains(nodeRef.Data.Head.Owner, exp.Owner) { + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected owner in %v but claims to have owner=%v", + addr, exp.Owner, nodeRef.Data.Head.Owner) + } + + // parse (main) + + if _, err := binstruct.Unmarshal(nodeBuf, &nodeRef.Data); err != nil { + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err) + } + + // return + + return nodeRef, nil +} diff --git a/lib/btrfs/btrfstree/types_node_test.go b/lib/btrfs/btrfstree/types_node_test.go new file mode 100644 index 0000000..040b90c --- /dev/null +++ b/lib/btrfs/btrfstree/types_node_test.go @@ -0,0 +1,35 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree_test + +import ( + "testing" + + "github.com/stretchr/testify/require" + + "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" +) + +func FuzzRoundTripNode(f *testing.F) { + f.Fuzz(func(t *testing.T, inDat []byte) { + t.Logf("dat=(%d)%q", len(inDat), inDat) + node := btrfstree.Node{ + ChecksumType: btrfssum.TYPE_CRC32, + } + n, err := binstruct.Unmarshal(inDat, &node) + if err != nil { + t.Logf("err=%v", err) + //require.Equal(t, 0, n) + } else { + require.Equal(t, len(inDat), n) + + outDat, err := binstruct.Marshal(node) + require.NoError(t, err) + require.Equal(t, inDat[:], outDat) + } + }) +} diff --git a/lib/btrfs/btrfstree/types_superblock.go b/lib/btrfs/btrfstree/types_superblock.go new file mode 100644 index 0000000..9258f9a --- /dev/null +++ b/lib/btrfs/btrfstree/types_superblock.go @@ -0,0 +1,238 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfstree + +import ( + "fmt" + "reflect" + + "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" +) + +type Superblock struct { + Checksum btrfssum.CSum `bin:"off=0x0, siz=0x20"` // Checksum of everything past this field (from 0x20 to 0x1000) + FSUUID btrfsprim.UUID `bin:"off=0x20, siz=0x10"` // FS UUID + Self btrfsvol.PhysicalAddr `bin:"off=0x30, siz=0x8"` // physical address of this block (different for mirrors) + Flags uint64 `bin:"off=0x38, siz=0x8"` // flags + Magic [8]byte `bin:"off=0x40, siz=0x8"` // magic ('_BHRfS_M') + Generation btrfsprim.Generation `bin:"off=0x48, siz=0x8"` + + RootTree btrfsvol.LogicalAddr `bin:"off=0x50, siz=0x8"` // logical address of the root tree root + ChunkTree btrfsvol.LogicalAddr `bin:"off=0x58, siz=0x8"` // logical address of the chunk tree root + LogTree btrfsvol.LogicalAddr `bin:"off=0x60, siz=0x8"` // logical address of the log tree root + + LogRootTransID uint64 `bin:"off=0x68, siz=0x8"` // log_root_transid + TotalBytes uint64 `bin:"off=0x70, siz=0x8"` // total_bytes + BytesUsed uint64 `bin:"off=0x78, siz=0x8"` // bytes_used + RootDirObjectID btrfsprim.ObjID `bin:"off=0x80, siz=0x8"` // root_dir_objectid (usually 6) + NumDevices uint64 `bin:"off=0x88, siz=0x8"` // num_devices + + SectorSize uint32 `bin:"off=0x90, siz=0x4"` + NodeSize uint32 `bin:"off=0x94, siz=0x4"` + LeafSize uint32 `bin:"off=0x98, siz=0x4"` // unused; must be the same as NodeSize + StripeSize uint32 `bin:"off=0x9c, siz=0x4"` + SysChunkArraySize uint32 `bin:"off=0xa0, siz=0x4"` + + ChunkRootGeneration btrfsprim.Generation `bin:"off=0xa4, siz=0x8"` + CompatFlags uint64 `bin:"off=0xac, siz=0x8"` // compat_flags + CompatROFlags uint64 `bin:"off=0xb4, siz=0x8"` // compat_ro_flags - only implementations that support the flags can write to the filesystem + IncompatFlags IncompatFlags `bin:"off=0xbc, siz=0x8"` // incompat_flags - only implementations that support the flags can use the filesystem + ChecksumType btrfssum.CSumType `bin:"off=0xc4, siz=0x2"` + + RootLevel uint8 `bin:"off=0xc6, siz=0x1"` // root_level + ChunkLevel uint8 `bin:"off=0xc7, siz=0x1"` // chunk_root_level + LogLevel uint8 `bin:"off=0xc8, siz=0x1"` // log_root_level + + DevItem btrfsitem.Dev `bin:"off=0xc9, siz=0x62"` // DEV_ITEM data for this device + Label [0x100]byte `bin:"off=0x12b, siz=0x100"` // label (may not contain '/' or '\\') + CacheGeneration btrfsprim.Generation `bin:"off=0x22b, siz=0x8"` + UUIDTreeGeneration btrfsprim.Generation `bin:"off=0x233, siz=0x8"` + + // FeatureIncompatMetadataUUID + MetadataUUID btrfsprim.UUID `bin:"off=0x23b, siz=0x10"` + + // FeatureIncompatExtentTreeV2 + NumGlobalRoots uint64 `bin:"off=0x24b, siz=0x8"` + + // FeatureIncompatExtentTreeV2 + BlockGroupRoot btrfsvol.LogicalAddr `bin:"off=0x253, siz=0x8"` + BlockGroupRootGeneration btrfsprim.Generation `bin:"off=0x25b, siz=0x8"` + BlockGroupRootLevel uint8 `bin:"off=0x263, siz=0x1"` + + Reserved [199]byte `bin:"off=0x264, siz=0xc7"` // future expansion + + SysChunkArray [0x800]byte `bin:"off=0x32b, siz=0x800"` // sys_chunk_array:(n bytes valid) Contains (KEY . CHUNK_ITEM) pairs for all SYSTEM chunks. This is needed to bootstrap the mapping from logical addresses to physical. + SuperRoots [4]RootBackup `bin:"off=0xb2b, siz=0x2a0"` + + // Padded to 4096 bytes + Padding [565]byte `bin:"off=0xdcb, siz=0x235"` + binstruct.End `bin:"off=0x1000"` +} + +func (sb Superblock) CalculateChecksum() (btrfssum.CSum, error) { + data, err := binstruct.Marshal(sb) + if err != nil { + return btrfssum.CSum{}, err + } + return sb.ChecksumType.Sum(data[binstruct.StaticSize(btrfssum.CSum{}):]) +} + +func (sb Superblock) ValidateChecksum() error { + stored := sb.Checksum + calced, err := sb.CalculateChecksum() + if err != nil { + return err + } + if calced != stored { + return fmt.Errorf("superblock checksum mismatch: stored=%v calculated=%v", + stored, calced) + } + return nil +} + +func (a Superblock) Equal(b Superblock) bool { + a.Checksum = btrfssum.CSum{} + a.Self = 0 + + b.Checksum = btrfssum.CSum{} + b.Self = 0 + + return reflect.DeepEqual(a, b) +} + +func (sb Superblock) EffectiveMetadataUUID() btrfsprim.UUID { + if !sb.IncompatFlags.Has(FeatureIncompatMetadataUUID) { + return sb.FSUUID + } + return sb.MetadataUUID +} + +type SysChunk struct { + Key btrfsprim.Key + Chunk btrfsitem.Chunk +} + +func (sc SysChunk) MarshalBinary() ([]byte, error) { + dat, err := binstruct.Marshal(sc.Key) + if err != nil { + return dat, err + } + _dat, err := binstruct.Marshal(sc.Chunk) + dat = append(dat, _dat...) + if err != nil { + return dat, err + } + return dat, nil +} + +func (sc *SysChunk) UnmarshalBinary(dat []byte) (int, error) { + n, err := binstruct.Unmarshal(dat, &sc.Key) + if err != nil { + return n, err + } + _n, err := binstruct.Unmarshal(dat[n:], &sc.Chunk) + n += _n + if err != nil { + return n, err + } + return n, nil +} + +func (sb Superblock) ParseSysChunkArray() ([]SysChunk, error) { + dat := sb.SysChunkArray[:sb.SysChunkArraySize] + var ret []SysChunk + for len(dat) > 0 { + var pair SysChunk + n, err := binstruct.Unmarshal(dat, &pair) + dat = dat[n:] + if err != nil { + return nil, err + } + ret = append(ret, pair) + } + return ret, nil +} + +type RootBackup struct { + TreeRoot btrfsprim.ObjID `bin:"off=0x0, siz=0x8"` + TreeRootGen btrfsprim.Generation `bin:"off=0x8, siz=0x8"` + + ChunkRoot btrfsprim.ObjID `bin:"off=0x10, siz=0x8"` + ChunkRootGen btrfsprim.Generation `bin:"off=0x18, siz=0x8"` + + ExtentRoot btrfsprim.ObjID `bin:"off=0x20, siz=0x8"` + ExtentRootGen btrfsprim.Generation `bin:"off=0x28, siz=0x8"` + + FSRoot btrfsprim.ObjID `bin:"off=0x30, siz=0x8"` + FSRootGen btrfsprim.Generation `bin:"off=0x38, siz=0x8"` + + DevRoot btrfsprim.ObjID `bin:"off=0x40, siz=0x8"` + DevRootGen btrfsprim.Generation `bin:"off=0x48, siz=0x8"` + + ChecksumRoot btrfsprim.ObjID `bin:"off=0x50, siz=0x8"` + ChecksumRootGen btrfsprim.Generation `bin:"off=0x58, siz=0x8"` + + TotalBytes uint64 `bin:"off=0x60, siz=0x8"` + BytesUsed uint64 `bin:"off=0x68, siz=0x8"` + NumDevices uint64 `bin:"off=0x70, siz=0x8"` + + Unused [8 * 4]byte `bin:"off=0x78, siz=0x20"` + + TreeRootLevel uint8 `bin:"off=0x98, siz=0x1"` + ChunkRootLevel uint8 `bin:"off=0x99, siz=0x1"` + ExtentRootLevel uint8 `bin:"off=0x9a, siz=0x1"` + FSRootLevel uint8 `bin:"off=0x9b, siz=0x1"` + DevRootLevel uint8 `bin:"off=0x9c, siz=0x1"` + ChecksumRootLevel uint8 `bin:"off=0x9d, siz=0x1"` + + Padding [10]byte `bin:"off=0x9e, siz=0xa"` + binstruct.End `bin:"off=0xa8"` +} + +type IncompatFlags uint64 + +const ( + FeatureIncompatMixedBackref = IncompatFlags(1 << iota) + FeatureIncompatDefaultSubvol + FeatureIncompatMixedGroups + FeatureIncompatCompressLZO + FeatureIncompatCompressZSTD + FeatureIncompatBigMetadata // buggy + FeatureIncompatExtendedIRef + FeatureIncompatRAID56 + FeatureIncompatSkinnyMetadata + FeatureIncompatNoHoles + FeatureIncompatMetadataUUID + FeatureIncompatRAID1C34 + FeatureIncompatZoned + FeatureIncompatExtentTreeV2 +) + +var incompatFlagNames = []string{ + "FeatureIncompatMixedBackref", + "FeatureIncompatDefaultSubvol", + "FeatureIncompatMixedGroups", + "FeatureIncompatCompressLZO", + "FeatureIncompatCompressZSTD", + "FeatureIncompatBigMetadata ", + "FeatureIncompatExtendedIRef", + "FeatureIncompatRAID56", + "FeatureIncompatSkinnyMetadata", + "FeatureIncompatNoHoles", + "FeatureIncompatMetadataUUID", + "FeatureIncompatRAID1C34", + "FeatureIncompatZoned", + "FeatureIncompatExtentTreeV2", +} + +func (f IncompatFlags) Has(req IncompatFlags) bool { return f&req == req } +func (f IncompatFlags) String() string { + return fmtutil.BitfieldString(f, incompatFlagNames, fmtutil.HexLower) +} diff --git a/lib/btrfs/internal/itemtype.go b/lib/btrfs/internal/itemtype.go deleted file mode 100644 index 9ba4a23..0000000 --- a/lib/btrfs/internal/itemtype.go +++ /dev/null @@ -1,79 +0,0 @@ -// Code generated by Make. DO NOT EDIT. - -// SPDX-License-Identifier: GPL-2.0-or-later - -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 deleted file mode 100644 index 3bc5402..0000000 --- a/lib/btrfs/internal/misc.go +++ /dev/null @@ -1,48 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package internal - -import ( - "fmt" - "time" - - "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" -) - -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 (k Key) String() string { - return fmt.Sprintf("{%v %v %v}", k.ObjectID, k.ItemType, k.Offset) -} - -func (a Key) Cmp(b Key) int { - if d := containers.NativeCmp(a.ObjectID, b.ObjectID); d != 0 { - return d - } - if d := containers.NativeCmp(a.ItemType, b.ItemType); d != 0 { - return d - } - return containers.NativeCmp(a.Offset, b.Offset) -} - -var _ containers.Ordered[Key] = Key{} - -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 deleted file mode 100644 index fa9eb4d..0000000 --- a/lib/btrfs/internal/objid.go +++ /dev/null @@ -1,148 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package internal - -import ( - "fmt" -) - -type ObjID uint64 - -const maxUint64pp = 0x1_00000000_00000000 - -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(maxUint64pp - 4) // for storing balance parameters in the root tree - ORPHAN_OBJECTID = ObjID(maxUint64pp - 5) // orphan objectid for tracking unlinked/truncated files - TREE_LOG_OBJECTID = ObjID(maxUint64pp - 6) // does write ahead logging to speed up fsyncs - TREE_LOG_FIXUP_OBJECTID = ObjID(maxUint64pp - 7) - TREE_RELOC_OBJECTID = ObjID(maxUint64pp - 8) // space balancing - DATA_RELOC_TREE_OBJECTID = ObjID(maxUint64pp - 9) - EXTENT_CSUM_OBJECTID = ObjID(maxUint64pp - 10) // extent checksums all have this objectid - FREE_SPACE_OBJECTID = ObjID(maxUint64pp - 11) // For storing free space cache - FREE_INO_OBJECTID = ObjID(maxUint64pp - 12) // stores the inode number for the free-ino cache - - MULTIPLE_OBJECTIDS = ObjID(maxUint64pp - 255) // dummy objectid represents multiple objectids - - // All files have objectids in this range. - FIRST_FREE_OBJECTID = ObjID(256) - LAST_FREE_OBJECTID = ObjID(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/internal/uuid.go b/lib/btrfs/internal/uuid.go deleted file mode 100644 index 96807b6..0000000 --- a/lib/btrfs/internal/uuid.go +++ /dev/null @@ -1,96 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package internal - -import ( - "encoding" - "encoding/hex" - "fmt" - "strings" - - "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" -) - -type UUID [16]byte - -var ( - _ fmt.Stringer = UUID{} - _ fmt.Formatter = UUID{} - _ encoding.TextMarshaler = UUID{} - _ encoding.TextUnmarshaler = (*UUID)(nil) -) - -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 (uuid UUID) MarshalText() ([]byte, error) { - return []byte(uuid.String()), nil -} - -func (uuid *UUID) UnmarshalText(text []byte) error { - var err error - *uuid, err = ParseUUID(string(text)) - return err -} - -func (uuid UUID) Format(f fmt.State, verb rune) { - fmtutil.FormatByteArrayStringer(uuid, uuid[:], f, verb) -} - -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 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/btrfs/internal/uuid_test.go b/lib/btrfs/internal/uuid_test.go deleted file mode 100644 index dfc3688..0000000 --- a/lib/btrfs/internal/uuid_test.go +++ /dev/null @@ -1,67 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package internal_test - -import ( - "fmt" - "testing" - - "github.com/stretchr/testify/assert" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/internal" -) - -func TestParseUUID(t *testing.T) { - t.Parallel() - type TestCase struct { - Input string - OutputVal internal.UUID - OutputErr string - } - testcases := map[string]TestCase{ - "basic": {Input: "a0dd94ed-e60c-42e8-8632-64e8d4765a43", OutputVal: internal.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 := internal.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 internal.UUID - InputFmt string - Output string - } - uuid := internal.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: "| internal.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) - }) - } -} diff --git a/lib/btrfs/io1_pv.go b/lib/btrfs/io1_pv.go index df31671..0e7cd9c 100644 --- a/lib/btrfs/io1_pv.go +++ b/lib/btrfs/io1_pv.go @@ -8,6 +8,7 @@ import ( "fmt" "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" ) @@ -15,8 +16,8 @@ import ( type Device struct { diskio.File[btrfsvol.PhysicalAddr] - cacheSuperblocks []*diskio.Ref[btrfsvol.PhysicalAddr, Superblock] - cacheSuperblock *Superblock + cacheSuperblocks []*diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Superblock] + cacheSuperblock *btrfstree.Superblock } var _ diskio.File[btrfsvol.PhysicalAddr] = (*Device)(nil) @@ -27,18 +28,18 @@ var SuperblockAddrs = []btrfsvol.PhysicalAddr{ 0x40_0000_0000, // 256GiB } -func (dev *Device) Superblocks() ([]*diskio.Ref[btrfsvol.PhysicalAddr, Superblock], error) { +func (dev *Device) Superblocks() ([]*diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Superblock], error) { if dev.cacheSuperblocks != nil { return dev.cacheSuperblocks, nil } - superblockSize := btrfsvol.PhysicalAddr(binstruct.StaticSize(Superblock{})) + superblockSize := btrfsvol.PhysicalAddr(binstruct.StaticSize(btrfstree.Superblock{})) sz := dev.Size() - var ret []*diskio.Ref[btrfsvol.PhysicalAddr, Superblock] + var ret []*diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Superblock] for i, addr := range SuperblockAddrs { if addr+superblockSize <= sz { - superblock := &diskio.Ref[btrfsvol.PhysicalAddr, Superblock]{ + superblock := &diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Superblock]{ File: dev, Addr: addr, } @@ -55,7 +56,7 @@ func (dev *Device) Superblocks() ([]*diskio.Ref[btrfsvol.PhysicalAddr, Superbloc return ret, nil } -func (dev *Device) Superblock() (*Superblock, error) { +func (dev *Device) Superblock() (*btrfstree.Superblock, error) { if dev.cacheSuperblock != nil { return dev.cacheSuperblock, nil } diff --git a/lib/btrfs/io2_lv.go b/lib/btrfs/io2_lv.go index 7fa003e..5580285 100644 --- a/lib/btrfs/io2_lv.go +++ b/lib/btrfs/io2_lv.go @@ -13,6 +13,8 @@ import ( "github.com/datawire/dlib/dlog" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" ) @@ -22,12 +24,12 @@ type FS struct { // implementing special things like fsck. LV btrfsvol.LogicalVolume[*Device] - cacheSuperblocks []*diskio.Ref[btrfsvol.PhysicalAddr, Superblock] - cacheSuperblock *Superblock + cacheSuperblocks []*diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Superblock] + cacheSuperblock *btrfstree.Superblock - cacheObjID2UUID map[ObjID]UUID - cacheUUID2ObjID map[UUID]ObjID - cacheTreeParent map[ObjID]UUID + cacheObjID2UUID map[btrfsprim.ObjID]btrfsprim.UUID + cacheUUID2ObjID map[btrfsprim.UUID]btrfsprim.ObjID + cacheTreeParent map[btrfsprim.ObjID]btrfsprim.UUID } var _ diskio.File[btrfsvol.LogicalAddr] = (*FS)(nil) @@ -72,11 +74,11 @@ func (fs *FS) WriteAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { return fs.LV.WriteAt(p, off) } -func (fs *FS) Superblocks() ([]*diskio.Ref[btrfsvol.PhysicalAddr, Superblock], error) { +func (fs *FS) Superblocks() ([]*diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Superblock], error) { if fs.cacheSuperblocks != nil { return fs.cacheSuperblocks, nil } - var ret []*diskio.Ref[btrfsvol.PhysicalAddr, Superblock] + var ret []*diskio.Ref[btrfsvol.PhysicalAddr, btrfstree.Superblock] devs := fs.LV.PhysicalVolumes() if len(devs) == 0 { return nil, fmt.Errorf("no devices") @@ -92,7 +94,7 @@ func (fs *FS) Superblocks() ([]*diskio.Ref[btrfsvol.PhysicalAddr, Superblock], e return ret, nil } -func (fs *FS) Superblock() (*Superblock, error) { +func (fs *FS) Superblock() (*btrfstree.Superblock, error) { if fs.cacheSuperblock != nil { return fs.cacheSuperblock, nil } @@ -147,7 +149,7 @@ func (fs *FS) ReInit(ctx context.Context) error { return nil } -func (fs *FS) initDev(ctx context.Context, sb Superblock) error { +func (fs *FS) initDev(ctx context.Context, sb btrfstree.Superblock) error { syschunks, err := sb.ParseSysChunkArray() if err != nil { return err @@ -160,12 +162,12 @@ func (fs *FS) initDev(ctx context.Context, sb Superblock) error { } } var errs derror.MultiError - fs.TreeWalk(ctx, CHUNK_TREE_OBJECTID, - func(err *TreeError) { + fs.TreeWalk(ctx, btrfsprim.CHUNK_TREE_OBJECTID, + func(err *btrfstree.TreeError) { errs = append(errs, err) }, - TreeWalkHandler{ - Item: func(_ TreePath, item Item) error { + btrfstree.TreeWalkHandler{ + Item: func(_ btrfstree.TreePath, item btrfstree.Item) error { if item.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY { return nil } diff --git a/lib/btrfs/io3_btree.go b/lib/btrfs/io3_btree.go index 1851508..9c4dd67 100644 --- a/lib/btrfs/io3_btree.go +++ b/lib/btrfs/io3_btree.go @@ -9,24 +9,39 @@ import ( "fmt" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" ) -var _ Trees = (*FS)(nil) +func (fs *FS) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { + btrfstree.TreesImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs) +} +func (fs *FS) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { + return btrfstree.TreesImpl{NodeSource: fs}.TreeLookup(treeID, key) +} +func (fs *FS) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) { + return btrfstree.TreesImpl{NodeSource: fs}.TreeSearch(treeID, fn) +} +func (fs *FS) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) { + return btrfstree.TreesImpl{NodeSource: fs}.TreeSearchAll(treeID, fn) +} + +var _ btrfstree.Trees = (*FS)(nil) func (fs *FS) populateTreeUUIDs(ctx context.Context) { if fs.cacheObjID2UUID == nil || fs.cacheUUID2ObjID == nil || fs.cacheTreeParent == nil { - fs.cacheObjID2UUID = make(map[ObjID]UUID) - fs.cacheUUID2ObjID = make(map[UUID]ObjID) - fs.cacheTreeParent = make(map[ObjID]UUID) - fs.TreeWalk(ctx, ROOT_TREE_OBJECTID, - func(err *TreeError) { + fs.cacheObjID2UUID = make(map[btrfsprim.ObjID]btrfsprim.UUID) + fs.cacheUUID2ObjID = make(map[btrfsprim.UUID]btrfsprim.ObjID) + fs.cacheTreeParent = make(map[btrfsprim.ObjID]btrfsprim.UUID) + fs.TreeWalk(ctx, btrfsprim.ROOT_TREE_OBJECTID, + func(err *btrfstree.TreeError) { // do nothing }, - TreeWalkHandler{ - Item: func(_ TreePath, item Item) error { + btrfstree.TreeWalkHandler{ + Item: func(_ btrfstree.TreePath, item btrfstree.Item) error { itemBody, ok := item.Body.(btrfsitem.Root) if !ok { return nil @@ -41,22 +56,22 @@ func (fs *FS) populateTreeUUIDs(ctx context.Context) { } } -func (fs *FS) ReadNode(path TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], error) { +func (fs *FS) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) { sb, err := fs.Superblock() if err != nil { return nil, fmt.Errorf("btrfs.FS.ReadNode: %w", err) } - potentialOwners := []ObjID{ + potentialOwners := []btrfsprim.ObjID{ path.Node(-1).FromTree, } - if potentialOwners[0] >= FIRST_FREE_OBJECTID { + if potentialOwners[0] >= btrfsprim.FIRST_FREE_OBJECTID { ctx := context.TODO() fs.populateTreeUUIDs(ctx) - for potentialOwners[len(potentialOwners)-1] >= FIRST_FREE_OBJECTID { + for potentialOwners[len(potentialOwners)-1] >= btrfsprim.FIRST_FREE_OBJECTID { objID := potentialOwners[len(potentialOwners)-1] parentUUID := fs.cacheTreeParent[objID] - if parentUUID == (UUID{}) { + if parentUUID == (btrfsprim.UUID{}) { break } parentObjID, ok := fs.cacheUUID2ObjID[parentUUID] @@ -67,10 +82,10 @@ func (fs *FS) ReadNode(path TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, Node], } } - return ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, NodeExpectations{ + return btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, path.Node(-1).ToNodeAddr, btrfstree.NodeExpectations{ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: path.Node(-1).ToNodeAddr}, Level: containers.Optional[uint8]{OK: true, Val: path.Node(-1).ToNodeLevel}, - MaxGeneration: containers.Optional[Generation]{OK: true, Val: path.Node(-1).FromGeneration}, + MaxGeneration: containers.Optional[btrfsprim.Generation]{OK: true, Val: path.Node(-1).FromGeneration}, Owner: potentialOwners, }) } diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index 65a7562..7bfcc00 100644 --- a/lib/btrfs/io4_fs.go +++ b/lib/btrfs/io4_fs.go @@ -15,6 +15,8 @@ import ( "github.com/datawire/dlib/derror" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" @@ -22,7 +24,7 @@ import ( ) type BareInode struct { - Inode ObjID + Inode btrfsprim.ObjID InodeItem *btrfsitem.Inode Errs derror.MultiError } @@ -30,11 +32,11 @@ type BareInode struct { type FullInode struct { BareInode XAttrs map[string]string - OtherItems []Item + OtherItems []btrfstree.Item } type InodeRef struct { - Inode ObjID + Inode btrfsprim.ObjID btrfsitem.InodeRef } @@ -58,22 +60,26 @@ type File struct { } type Subvolume struct { - FS Trees - TreeID ObjID + FS interface { + btrfstree.Trees + Superblock() (*btrfstree.Superblock, error) + ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) + } + TreeID btrfsprim.ObjID rootOnce sync.Once rootVal btrfsitem.Root rootErr error - bareInodeCache containers.LRUCache[ObjID, *BareInode] - fullInodeCache containers.LRUCache[ObjID, *FullInode] - dirCache containers.LRUCache[ObjID, *Dir] - fileCache containers.LRUCache[ObjID, *File] + bareInodeCache containers.LRUCache[btrfsprim.ObjID, *BareInode] + fullInodeCache containers.LRUCache[btrfsprim.ObjID, *FullInode] + dirCache containers.LRUCache[btrfsprim.ObjID, *Dir] + fileCache containers.LRUCache[btrfsprim.ObjID, *File] } func (sv *Subvolume) init() { sv.rootOnce.Do(func() { - root, err := sv.FS.TreeLookup(ROOT_TREE_OBJECTID, Key{ + root, err := sv.FS.TreeLookup(btrfsprim.ROOT_TREE_OBJECTID, btrfsprim.Key{ ObjectID: sv.TreeID, ItemType: btrfsitem.ROOT_ITEM_KEY, Offset: 0, @@ -93,17 +99,17 @@ func (sv *Subvolume) init() { }) } -func (sv *Subvolume) GetRootInode() (ObjID, error) { +func (sv *Subvolume) GetRootInode() (btrfsprim.ObjID, error) { sv.init() return sv.rootVal.RootDirID, sv.rootErr } -func (sv *Subvolume) LoadBareInode(inode ObjID) (*BareInode, error) { +func (sv *Subvolume) LoadBareInode(inode btrfsprim.ObjID) (*BareInode, error) { val := sv.bareInodeCache.GetOrElse(inode, func() (val *BareInode) { val = &BareInode{ Inode: inode, } - item, err := sv.FS.TreeLookup(sv.TreeID, Key{ + item, err := sv.FS.TreeLookup(sv.TreeID, btrfsprim.Key{ ObjectID: inode, ItemType: btrfsitem.INODE_ITEM_KEY, Offset: 0, @@ -128,7 +134,7 @@ func (sv *Subvolume) LoadBareInode(inode ObjID) (*BareInode, error) { return val, nil } -func (sv *Subvolume) LoadFullInode(inode ObjID) (*FullInode, error) { +func (sv *Subvolume) LoadFullInode(inode btrfsprim.ObjID) (*FullInode, error) { val := sv.fullInodeCache.GetOrElse(inode, func() (val *FullInode) { val = &FullInode{ BareInode: BareInode{ @@ -136,7 +142,7 @@ func (sv *Subvolume) LoadFullInode(inode ObjID) (*FullInode, error) { }, XAttrs: make(map[string]string), } - items, err := sv.FS.TreeSearchAll(sv.TreeID, func(key Key, _ uint32) int { + items, err := sv.FS.TreeSearchAll(sv.TreeID, func(key btrfsprim.Key, _ uint32) int { return containers.NativeCmp(inode, key.ObjectID) }) if err != nil { @@ -171,7 +177,7 @@ func (sv *Subvolume) LoadFullInode(inode ObjID) (*FullInode, error) { return val, nil } -func (sv *Subvolume) LoadDir(inode ObjID) (*Dir, error) { +func (sv *Subvolume) LoadDir(inode btrfsprim.ObjID) (*Dir, error) { val := sv.dirCache.GetOrElse(inode, func() (val *Dir) { val = new(Dir) fullInode, err := sv.LoadFullInode(inode) @@ -203,7 +209,7 @@ func (ret *Dir) populate() { continue } ref := InodeRef{ - Inode: ObjID(item.Key.Offset), + Inode: btrfsprim.ObjID(item.Key.Offset), InodeRef: body[0], } if ret.DotDot != nil { @@ -288,7 +294,7 @@ func (dir *Dir) AbsPath() (string, error) { return filepath.Join(parentName, string(dir.DotDot.Name)), nil } -func (sv *Subvolume) LoadFile(inode ObjID) (*File, error) { +func (sv *Subvolume) LoadFile(inode btrfsprim.ObjID) (*File, error) { val := sv.fileCache.GetOrElse(inode, func() (val *File) { val = new(File) fullInode, err := sv.LoadFullInode(inode) diff --git a/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 b/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 deleted file mode 100644 index a96f559..0000000 --- a/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/582528ddfad69eb57775199a43e0f9fd5c94bba343ce7bb6724d4ebafe311ed4 +++ /dev/null @@ -1,2 +0,0 @@ -go test fuzz v1 -[]byte("0") diff --git a/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca b/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca deleted file mode 100644 index d5c153f..0000000 --- a/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/8260b6cf3bc57fc7d7603487337411d9557684e849ee9457d40f8f3e5f5b2fca +++ /dev/null @@ -1,2 +0,0 @@ -go test fuzz v1 -[]byte("000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\x00\x00\x00\x000") diff --git a/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 b/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 deleted file mode 100644 index 6a2309e..0000000 --- a/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/9863f0d39958aa548ca8fa512ea6df2f483f3ffce6be73cee08059ca0bd7e8b5 +++ /dev/null @@ -1,2 +0,0 @@ -go test fuzz v1 -[]byte("00000000000000000000000000000000000000000000000000000000") diff --git a/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 b/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 deleted file mode 100644 index 50b960e..0000000 --- a/lib/btrfs/testdata/fuzz/FuzzRoundTripNode/e748e617b5b662a80f342aeda2fd101ca74ccf3bda0faae115ac338d47f195e9 +++ /dev/null @@ -1,2 +0,0 @@ -go test fuzz v1 -[]byte("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000") diff --git a/lib/btrfs/types_node.go b/lib/btrfs/types_node.go deleted file mode 100644 index 7d66f60..0000000 --- a/lib/btrfs/types_node.go +++ /dev/null @@ -1,453 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -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/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" - "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" - "git.lukeshu.com/btrfs-progs-ng/lib/slices" -) - -type NodeFlags uint64 - -func (NodeFlags) BinaryStaticSize() int { - return 7 -} -func (f NodeFlags) MarshalBinary() ([]byte, error) { - var bs [8]byte - binary.LittleEndian.PutUint64(bs[:], uint64(f)) - return bs[:7], nil -} -func (f *NodeFlags) UnmarshalBinary(dat []byte) (int, error) { - var bs [8]byte - copy(bs[:7], dat[:7]) - *f = NodeFlags(binary.LittleEndian.Uint64(bs[:])) - return 7, nil -} - -var ( - _ binstruct.StaticSizer = NodeFlags(0) - _ binstruct.Marshaler = NodeFlags(0) - _ binstruct.Unmarshaler = (*NodeFlags)(nil) -) - -const ( - NodeWritten = NodeFlags(1 << iota) - NodeReloc -) - -var nodeFlagNames = []string{ - "WRITTEN", - "RELOC", -} - -func (f NodeFlags) Has(req NodeFlags) bool { return f&req == req } -func (f NodeFlags) String() string { return fmtutil.BitfieldString(f, nodeFlagNames, fmtutil.HexLower) } - -type BackrefRev uint8 - -const ( - OldBackrefRev = BackrefRev(iota) - MixedBackrefRev = BackrefRev(iota) -) - -// Node: main ////////////////////////////////////////////////////////////////////////////////////// - -type Node struct { - // Some context from the parent filesystem - Size uint32 // superblock.NodeSize - ChecksumType btrfssum.CSumType // superblock.ChecksumType - - // The node's header (always present) - Head NodeHeader - - // The node's body (which one of these is present depends on - // the node's type, as specified in the header) - BodyInternal []KeyPointer // for 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) MinItem() (Key, bool) { - if node.Head.Level > 0 { - if len(node.BodyInternal) == 0 { - return Key{}, false - } - return node.BodyInternal[0].Key, true - } else { - if len(node.BodyLeaf) == 0 { - return Key{}, false - } - return node.BodyLeaf[0].Key, true - } -} - -func (node Node) MaxItem() (Key, bool) { - if node.Head.Level > 0 { - if len(node.BodyInternal) == 0 { - return Key{}, false - } - return node.BodyInternal[len(node.BodyInternal)-1].Key, true - } else { - if len(node.BodyLeaf) == 0 { - return Key{}, false - } - return node.BodyLeaf[len(node.BodyLeaf)-1].Key, true - } -} - -func (node Node) CalculateChecksum() (btrfssum.CSum, error) { - data, err := binstruct.Marshal(node) - if err != nil { - return btrfssum.CSum{}, err - } - return node.ChecksumType.Sum(data[binstruct.StaticSize(btrfssum.CSum{}):]) -} - -func (node Node) ValidateChecksum() error { - stored := node.Head.Checksum - calced, err := node.CalculateChecksum() - if err != nil { - return err - } - if calced != stored { - return fmt.Errorf("node checksum mismatch: stored=%v calculated=%v", - stored, calced) - } - return nil -} - -func (node *Node) UnmarshalBinary(nodeBuf []byte) (int, error) { - *node = Node{ - Size: uint32(len(nodeBuf)), - ChecksumType: node.ChecksumType, - } - if len(nodeBuf) <= binstruct.StaticSize(NodeHeader{}) { - return 0, fmt.Errorf("size must be greater than %v, but is %v", - binstruct.StaticSize(NodeHeader{}), - len(nodeBuf)) - } - n, err := binstruct.Unmarshal(nodeBuf, &node.Head) - if err != nil { - return n, err - } else if n != binstruct.StaticSize(NodeHeader{}) { - return n, fmt.Errorf("header consumed %v bytes but expected %v", - n, binstruct.StaticSize(NodeHeader{})) - } - if node.Head.Level > 0 { - _n, err := node.unmarshalInternal(nodeBuf[n:]) - n += _n - if err != nil { - return n, fmt.Errorf("internal: %w", err) - } - } else { - _n, err := node.unmarshalLeaf(nodeBuf[n:]) - n += _n - if err != nil { - return n, fmt.Errorf("leaf: %w", err) - } - } - if n != len(nodeBuf) { - return n, fmt.Errorf("left over data: got %v bytes but only consumed %v", - len(nodeBuf), n) - } - return n, nil -} - -func (node Node) MarshalBinary() ([]byte, error) { - if node.Size == 0 { - return nil, fmt.Errorf(".Size must be set") - } - if node.Size <= uint32(binstruct.StaticSize(NodeHeader{})) { - return nil, fmt.Errorf(".Size must be greater than %v, but is %v", - binstruct.StaticSize(NodeHeader{}), - node.Size) - } - if node.Head.Level > 0 { - node.Head.NumItems = uint32(len(node.BodyInternal)) - } else { - node.Head.NumItems = uint32(len(node.BodyLeaf)) - } - - buf := make([]byte, node.Size) - - if bs, err := binstruct.Marshal(node.Head); err != nil { - return buf, err - } else if len(bs) != binstruct.StaticSize(NodeHeader{}) { - return nil, fmt.Errorf("header is %v bytes but expected %v", - len(bs), binstruct.StaticSize(NodeHeader{})) - } else { - copy(buf, bs) - } - - if node.Head.Level > 0 { - if err := node.marshalInternalTo(buf[binstruct.StaticSize(NodeHeader{}):]); err != nil { - return buf, err - } - } else { - if err := node.marshalLeafTo(buf[binstruct.StaticSize(NodeHeader{}):]); err != nil { - return buf, err - } - } - - return buf, nil -} - -// Node: "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 { - Key Key - BodySize uint32 // [ignored-when-writing] - 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 itemHead ItemHeader - n, err := binstruct.Unmarshal(bodyBuf[head:], &itemHead) - head += n - if err != nil { - return 0, fmt.Errorf("item %v: head: %w", i, err) - } - if head > tail { - return 0, fmt.Errorf("item %v: head: end_offset=%#x is in the body section (offset>%#x)", - i, head, tail) - } - - dataOff := int(itemHead.DataOffset) - if dataOff < head { - return 0, fmt.Errorf("item %v: body: beg_offset=%#x is in the head section (offset<%#x)", - i, dataOff, head) - } - dataSize := int(itemHead.DataSize) - if dataOff+dataSize != tail { - return 0, fmt.Errorf("item %v: body: end_offset=%#x is not cur_tail=%#x)", - i, dataOff+dataSize, tail) - } - tail = dataOff - dataBuf := bodyBuf[dataOff : dataOff+dataSize] - - node.BodyLeaf = append(node.BodyLeaf, Item{ - Key: itemHead.Key, - BodySize: itemHead.DataSize, - Body: btrfsitem.UnmarshalItem(itemHead.Key, node.ChecksumType, dataBuf), - }) - } - - node.Padding = bodyBuf[head:tail] - return len(bodyBuf), nil -} - -func (node *Node) marshalLeafTo(bodyBuf []byte) error { - head := 0 - tail := len(bodyBuf) - for i, item := range node.BodyLeaf { - itemBodyBuf, err := binstruct.Marshal(item.Body) - if err != nil { - return fmt.Errorf("item %v: body: %w", i, err) - } - itemHeadBuf, err := binstruct.Marshal(ItemHeader{ - Key: item.Key, - DataSize: uint32(len(itemBodyBuf)), - DataOffset: uint32(tail - len(itemBodyBuf)), - }) - if err != nil { - return fmt.Errorf("item %v: head: %w", i, err) - } - - if tail-head < len(itemHeadBuf)+len(itemBodyBuf) { - return fmt.Errorf("item %v: not enough space: need at least (head_len:%v)+(body_len:%v)=%v free bytes, but only have %v", - i, len(itemHeadBuf), len(itemBodyBuf), len(itemHeadBuf)+len(itemBodyBuf), tail-head) - } - - copy(bodyBuf[head:], itemHeadBuf) - head += len(itemHeadBuf) - tail -= len(itemBodyBuf) - copy(bodyBuf[tail:], itemBodyBuf) - } - if copy(bodyBuf[head:tail], node.Padding) < len(node.Padding) { - return fmt.Errorf("padding: not enough space: need at least %v free bytes, but only have %v", - len(node.Padding), tail-head) - } - return nil -} - -func (node *Node) LeafFreeSpace() uint32 { - if node.Head.Level > 0 { - panic(fmt.Errorf("Node.LeafFreeSpace: not a leaf node")) - } - freeSpace := node.Size - freeSpace -= uint32(binstruct.StaticSize(NodeHeader{})) - for _, item := range node.BodyLeaf { - freeSpace -= uint32(binstruct.StaticSize(ItemHeader{})) - bs, _ := binstruct.Marshal(item.Body) - freeSpace -= uint32(len(bs)) - } - return freeSpace -} - -// Tie Nodes in to the FS ////////////////////////////////////////////////////////////////////////// - -var ErrNotANode = errors.New("does not look like a node") - -type NodeExpectations struct { - LAddr containers.Optional[btrfsvol.LogicalAddr] - // Things knowable from the parent. - Level containers.Optional[uint8] - MaxGeneration containers.Optional[Generation] - Owner []ObjID -} - -func ReadNode[Addr ~int64](fs diskio.File[Addr], sb Superblock, addr Addr, exp NodeExpectations) (*diskio.Ref[Addr, Node], error) { - nodeBuf := make([]byte, sb.NodeSize) - if _, err := fs.ReadAt(nodeBuf, addr); err != nil { - return nil, err - } - - // parse (early) - - nodeRef := &diskio.Ref[Addr, Node]{ - File: fs, - Addr: addr, - Data: Node{ - Size: sb.NodeSize, - ChecksumType: sb.ChecksumType, - }, - } - if _, err := binstruct.Unmarshal(nodeBuf, &nodeRef.Data.Head); err != nil { - return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err) - } - - // sanity checking - - if nodeRef.Data.Head.MetadataUUID != sb.EffectiveMetadataUUID() { - return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, ErrNotANode) - } - - stored := nodeRef.Data.Head.Checksum - calced, err := nodeRef.Data.ChecksumType.Sum(nodeBuf[binstruct.StaticSize(btrfssum.CSum{}):]) - if err != nil { - return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err) - } - if stored != calced { - return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: looks like a node but is corrupt: checksum mismatch: stored=%v calculated=%v", - addr, stored, calced) - } - - if exp.LAddr.OK && nodeRef.Data.Head.Addr != exp.LAddr.Val { - return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: read from laddr=%v but claims to be at laddr=%v", - addr, exp.LAddr.Val, nodeRef.Data.Head.Addr) - } - if exp.Level.OK && nodeRef.Data.Head.Level != exp.Level.Val { - return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected level=%v but claims to be level=%v", - addr, exp.Level.Val, nodeRef.Data.Head.Level) - } - if exp.MaxGeneration.OK && nodeRef.Data.Head.Generation > exp.MaxGeneration.Val { - return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected generation<=%v but claims to be generation=%v", - addr, exp.MaxGeneration.Val, nodeRef.Data.Head.Generation) - } - if len(exp.Owner) > 0 && !slices.Contains(nodeRef.Data.Head.Owner, exp.Owner) { - return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: expected owner in %v but claims to have owner=%v", - addr, exp.Owner, nodeRef.Data.Head.Owner) - } - - // parse (main) - - if _, err := binstruct.Unmarshal(nodeBuf, &nodeRef.Data); err != nil { - return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, err) - } - - // return - - return nodeRef, nil -} diff --git a/lib/btrfs/types_node_test.go b/lib/btrfs/types_node_test.go deleted file mode 100644 index 2748c38..0000000 --- a/lib/btrfs/types_node_test.go +++ /dev/null @@ -1,35 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package btrfs_test - -import ( - "testing" - - "github.com/stretchr/testify/require" - - "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" -) - -func FuzzRoundTripNode(f *testing.F) { - f.Fuzz(func(t *testing.T, inDat []byte) { - t.Logf("dat=(%d)%q", len(inDat), inDat) - node := btrfs.Node{ - ChecksumType: btrfssum.TYPE_CRC32, - } - n, err := binstruct.Unmarshal(inDat, &node) - if err != nil { - t.Logf("err=%v", err) - //require.Equal(t, 0, n) - } else { - require.Equal(t, len(inDat), n) - - outDat, err := binstruct.Marshal(node) - require.NoError(t, err) - require.Equal(t, inDat[:], outDat) - } - }) -} diff --git a/lib/btrfs/types_superblock.go b/lib/btrfs/types_superblock.go deleted file mode 100644 index 68c5d56..0000000 --- a/lib/btrfs/types_superblock.go +++ /dev/null @@ -1,237 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -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/fmtutil" -) - -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, err - } - _dat, err := binstruct.Marshal(sc.Chunk) - dat = append(dat, _dat...) - if err != nil { - return dat, err - } - return dat, nil -} - -func (sc *SysChunk) UnmarshalBinary(dat []byte) (int, error) { - n, err := binstruct.Unmarshal(dat, &sc.Key) - if err != nil { - return n, err - } - _n, err := binstruct.Unmarshal(dat[n:], &sc.Chunk) - n += _n - if err != nil { - return n, err - } - return n, nil -} - -func (sb Superblock) ParseSysChunkArray() ([]SysChunk, error) { - dat := sb.SysChunkArray[:sb.SysChunkArraySize] - var ret []SysChunk - for len(dat) > 0 { - var pair SysChunk - n, err := binstruct.Unmarshal(dat, &pair) - dat = dat[n:] - if err != nil { - return nil, err - } - ret = append(ret, pair) - } - return ret, nil -} - -type RootBackup struct { - TreeRoot 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 fmtutil.BitfieldString(f, incompatFlagNames, fmtutil.HexLower) -} diff --git a/lib/btrfsprogs/btrfsinspect/mount.go b/lib/btrfsprogs/btrfsinspect/mount.go index dbab7c7..5905034 100644 --- a/lib/btrfsprogs/btrfsinspect/mount.go +++ b/lib/btrfsprogs/btrfsinspect/mount.go @@ -23,6 +23,7 @@ import ( "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/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" @@ -43,7 +44,7 @@ func MountRO(ctx context.Context, fs *btrfs.FS, mountpoint string) error { rootSubvol := &subvolume{ Subvolume: btrfs.Subvolume{ FS: btrfsutil.NewBrokenTrees(ctx, fs), - TreeID: btrfs.FS_TREE_OBJECTID, + TreeID: btrfsprim.FS_TREE_OBJECTID, }, DeviceName: deviceName, Mountpoint: mountpoint, @@ -152,7 +153,7 @@ func inodeItemToFUSE(itemBody btrfsitem.Inode) fuseops.InodeAttributes { } } -func (sv *subvolume) LoadDir(inode btrfs.ObjID) (val *btrfs.Dir, err error) { +func (sv *subvolume) LoadDir(inode btrfsprim.ObjID) (val *btrfs.Dir, err error) { val, err = sv.Subvolume.LoadDir(inode) if val != nil { haveSubvolumes := false @@ -232,7 +233,7 @@ func (sv *subvolume) LookUpInode(_ context.Context, op *fuseops.LookUpInodeOp) e op.Parent = fuseops.InodeID(parent) } - dir, err := sv.LoadDir(btrfs.ObjID(op.Parent)) + dir, err := sv.LoadDir(btrfsprim.ObjID(op.Parent)) if err != nil { return err } @@ -283,7 +284,7 @@ func (sv *subvolume) GetInodeAttributes(_ context.Context, op *fuseops.GetInodeA op.Inode = fuseops.InodeID(inode) } - bareInode, err := sv.LoadBareInode(btrfs.ObjID(op.Inode)) + bareInode, err := sv.LoadBareInode(btrfsprim.ObjID(op.Inode)) if err != nil { return err } @@ -301,7 +302,7 @@ func (sv *subvolume) OpenDir(_ context.Context, op *fuseops.OpenDirOp) error { op.Inode = fuseops.InodeID(inode) } - dir, err := sv.LoadDir(btrfs.ObjID(op.Inode)) + dir, err := sv.LoadDir(btrfsprim.ObjID(op.Inode)) if err != nil { return err } @@ -354,7 +355,7 @@ func (sv *subvolume) ReleaseDirHandle(_ context.Context, op *fuseops.ReleaseDirH } func (sv *subvolume) OpenFile(_ context.Context, op *fuseops.OpenFileOp) error { - file, err := sv.LoadFile(btrfs.ObjID(op.Inode)) + file, err := sv.LoadFile(btrfsprim.ObjID(op.Inode)) if err != nil { return err } @@ -398,7 +399,7 @@ func (sv *subvolume) ReleaseFileHandle(_ context.Context, op *fuseops.ReleaseFil } func (sv *subvolume) ReadSymlink(_ context.Context, op *fuseops.ReadSymlinkOp) error { - file, err := sv.LoadFile(btrfs.ObjID(op.Inode)) + file, err := sv.LoadFile(btrfsprim.ObjID(op.Inode)) if err != nil { return err } @@ -420,7 +421,7 @@ func (sv *subvolume) ListXattr(_ context.Context, op *fuseops.ListXattrOp) error op.Inode = fuseops.InodeID(inode) } - fullInode, err := sv.LoadFullInode(btrfs.ObjID(op.Inode)) + fullInode, err := sv.LoadFullInode(btrfsprim.ObjID(op.Inode)) if err != nil { return err } @@ -452,7 +453,7 @@ func (sv *subvolume) GetXattr(_ context.Context, op *fuseops.GetXattrOp) error { op.Inode = fuseops.InodeID(inode) } - fullInode, err := sv.LoadFullInode(btrfs.ObjID(op.Inode)) + fullInode, err := sv.LoadFullInode(btrfsprim.ObjID(op.Inode)) if err != nil { return err } diff --git a/lib/btrfsprogs/btrfsinspect/print_tree.go b/lib/btrfsprogs/btrfsinspect/print_tree.go index 1568245..9e5a5d1 100644 --- a/lib/btrfsprogs/btrfsinspect/print_tree.go +++ b/lib/btrfsprogs/btrfsinspect/print_tree.go @@ -16,7 +16,9 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" "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/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" "git.lukeshu.com/btrfs-progs-ng/lib/slices" @@ -31,50 +33,50 @@ func DumpTrees(ctx context.Context, out io.Writer, fs *btrfs.FS) { if superblock.RootTree != 0 { fmt.Fprintf(out, "root tree\n") - printTree(ctx, out, fs, btrfs.ROOT_TREE_OBJECTID) + printTree(ctx, out, fs, btrfsprim.ROOT_TREE_OBJECTID) } if superblock.ChunkTree != 0 { fmt.Fprintf(out, "chunk tree\n") - printTree(ctx, out, fs, btrfs.CHUNK_TREE_OBJECTID) + printTree(ctx, out, fs, btrfsprim.CHUNK_TREE_OBJECTID) } if superblock.LogTree != 0 { fmt.Fprintf(out, "log root tree\n") - printTree(ctx, out, fs, btrfs.TREE_LOG_OBJECTID) + printTree(ctx, out, fs, btrfsprim.TREE_LOG_OBJECTID) } if superblock.BlockGroupRoot != 0 { fmt.Fprintf(out, "block group tree\n") - printTree(ctx, out, fs, btrfs.BLOCK_GROUP_TREE_OBJECTID) + printTree(ctx, out, fs, btrfsprim.BLOCK_GROUP_TREE_OBJECTID) } fs.TreeWalk( ctx, - btrfs.ROOT_TREE_OBJECTID, - func(err *btrfs.TreeError) { + btrfsprim.ROOT_TREE_OBJECTID, + func(err *btrfstree.TreeError) { dlog.Error(ctx, err) }, - btrfs.TreeWalkHandler{ - Item: func(_ btrfs.TreePath, item btrfs.Item) error { + btrfstree.TreeWalkHandler{ + Item: func(_ btrfstree.TreePath, item btrfstree.Item) error { if item.Key.ItemType != btrfsitem.ROOT_ITEM_KEY { return nil } - treeName, ok := map[btrfs.ObjID]string{ - btrfs.ROOT_TREE_OBJECTID: "root", - btrfs.EXTENT_TREE_OBJECTID: "extent", - btrfs.CHUNK_TREE_OBJECTID: "chunk", - btrfs.DEV_TREE_OBJECTID: "device", - btrfs.FS_TREE_OBJECTID: "fs", - btrfs.ROOT_TREE_DIR_OBJECTID: "directory", - btrfs.CSUM_TREE_OBJECTID: "checksum", - btrfs.ORPHAN_OBJECTID: "orphan", - btrfs.TREE_LOG_OBJECTID: "log", - btrfs.TREE_LOG_FIXUP_OBJECTID: "log fixup", - btrfs.TREE_RELOC_OBJECTID: "reloc", - btrfs.DATA_RELOC_TREE_OBJECTID: "data reloc", - btrfs.EXTENT_CSUM_OBJECTID: "extent checksum", - btrfs.QUOTA_TREE_OBJECTID: "quota", - btrfs.UUID_TREE_OBJECTID: "uuid", - btrfs.FREE_SPACE_TREE_OBJECTID: "free space", - btrfs.MULTIPLE_OBJECTIDS: "multiple", - btrfs.BLOCK_GROUP_TREE_OBJECTID: "block group", + treeName, ok := map[btrfsprim.ObjID]string{ + btrfsprim.ROOT_TREE_OBJECTID: "root", + btrfsprim.EXTENT_TREE_OBJECTID: "extent", + btrfsprim.CHUNK_TREE_OBJECTID: "chunk", + btrfsprim.DEV_TREE_OBJECTID: "device", + btrfsprim.FS_TREE_OBJECTID: "fs", + btrfsprim.ROOT_TREE_DIR_OBJECTID: "directory", + btrfsprim.CSUM_TREE_OBJECTID: "checksum", + btrfsprim.ORPHAN_OBJECTID: "orphan", + btrfsprim.TREE_LOG_OBJECTID: "log", + btrfsprim.TREE_LOG_FIXUP_OBJECTID: "log fixup", + btrfsprim.TREE_RELOC_OBJECTID: "reloc", + btrfsprim.DATA_RELOC_TREE_OBJECTID: "data reloc", + btrfsprim.EXTENT_CSUM_OBJECTID: "extent checksum", + btrfsprim.QUOTA_TREE_OBJECTID: "quota", + btrfsprim.UUID_TREE_OBJECTID: "uuid", + btrfsprim.FREE_SPACE_TREE_OBJECTID: "free space", + btrfsprim.MULTIPLE_OBJECTIDS: "multiple", + btrfsprim.BLOCK_GROUP_TREE_OBJECTID: "block group", }[item.Key.ObjectID] if !ok { treeName = "file" @@ -93,22 +95,22 @@ func DumpTrees(ctx context.Context, out io.Writer, fs *btrfs.FS) { // printTree mimics btrfs-progs // kernel-shared/print-tree.c:btrfs_print_tree() and // kernel-shared/print-tree.c:btrfs_print_leaf() -func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfs.ObjID) { +func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfsprim.ObjID) { var itemOffset uint32 - handlers := btrfs.TreeWalkHandler{ - Node: func(path btrfs.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfs.Node]) error { + handlers := btrfstree.TreeWalkHandler{ + Node: func(path btrfstree.TreePath, nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { printHeaderInfo(out, nodeRef.Data) - itemOffset = nodeRef.Data.Size - uint32(binstruct.StaticSize(btrfs.NodeHeader{})) + itemOffset = nodeRef.Data.Size - uint32(binstruct.StaticSize(btrfstree.NodeHeader{})) return nil }, - PreKeyPointer: func(_ btrfs.TreePath, item btrfs.KeyPointer) error { + PreKeyPointer: func(_ btrfstree.TreePath, item btrfstree.KeyPointer) error { fmt.Fprintf(out, "\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 { + Item: func(path btrfstree.TreePath, item btrfstree.Item) error { i := path.Node(-1).FromItemIdx bs, _ := binstruct.Marshal(item.Body) itemSize := uint32(len(bs)) @@ -303,7 +305,7 @@ func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfs.Ob fmt.Fprintf(out, "\t\tpersistent item objectid %v offset %v\n", item.Key.ObjectID.Format(item.Key.ItemType), item.Key.Offset) switch item.Key.ObjectID { - case btrfs.DEV_STATS_OBJECTID: + case btrfsprim.DEV_STATS_OBJECTID: fmt.Fprintf(out, "\t\tdevice stats\n") fmt.Fprintf(out, "\t\twrite_errs %v read_errs %v flush_errs %v corruption_errs %v generation %v\n", body.Values[btrfsitem.DEV_STAT_WRITE_ERRS], @@ -347,7 +349,7 @@ func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfs.Ob fs.TreeWalk( ctx, treeID, - func(err *btrfs.TreeError) { + func(err *btrfstree.TreeError) { dlog.Error(ctx, err) }, handlers, @@ -355,7 +357,7 @@ func printTree(ctx context.Context, out io.Writer, fs *btrfs.FS, treeID btrfs.Ob } // printHeaderInfo mimics btrfs-progs kernel-shared/print-tree.c:print_header_info() -func printHeaderInfo(out io.Writer, node btrfs.Node) { +func printHeaderInfo(out io.Writer, node btrfstree.Node) { var typename string if node.Head.Level > 0 { // internal node typename = "node" @@ -400,7 +402,7 @@ func printExtentInlineRefs(out io.Writer, refs []btrfsitem.ExtentInlineRef) { switch ref.Type { case btrfsitem.TREE_BLOCK_REF_KEY: fmt.Fprintf(out, "\t\ttree block backref root %v\n", - btrfs.ObjID(ref.Offset)) + btrfsprim.ObjID(ref.Offset)) case btrfsitem.SHARED_BLOCK_REF_KEY: fmt.Fprintf(out, "\t\tshared block backref parent %v\n", ref.Offset) @@ -420,7 +422,7 @@ func printExtentInlineRefs(out io.Writer, refs []btrfsitem.ExtentInlineRef) { } // mimics print-tree.c:btrfs_print_key() -func fmtKey(key btrfs.Key) string { +func fmtKey(key btrfsprim.Key) string { var out strings.Builder fmt.Fprintf(&out, "key (%v %v", key.ObjectID.Format(key.ItemType), key.ItemType) switch key.ItemType { @@ -429,7 +431,7 @@ func fmtKey(key btrfs.Key) string { 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)) + fmt.Fprintf(&out, " %v)", btrfsprim.ObjID(key.Offset)) default: if key.Offset == math.MaxUint64 { fmt.Fprintf(&out, " -1)") @@ -440,7 +442,7 @@ func fmtKey(key btrfs.Key) string { return out.String() } -func fmtTime(t btrfs.Time) string { +func fmtTime(t btrfsprim.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/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go index 4302d6a..5923b6c 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuildnodes.go @@ -13,6 +13,8 @@ import ( "github.com/datawire/dlib/dlog" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" @@ -45,13 +47,13 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec return rebuiltNodes, nil } -var maxKey = btrfs.Key{ +var maxKey = btrfsprim.Key{ ObjectID: math.MaxUint64, ItemType: math.MaxUint8, Offset: math.MaxUint64, } -func keyMm(key btrfs.Key) btrfs.Key { +func keyMm(key btrfsprim.Key) btrfsprim.Key { switch { case key.Offset > 0: key.Offset-- @@ -63,10 +65,10 @@ func keyMm(key btrfs.Key) btrfs.Key { return key } -func spanOfTreePath(fs *btrfs.FS, path btrfs.TreePath) (btrfs.Key, btrfs.Key) { +func spanOfTreePath(fs *btrfs.FS, path btrfstree.TreePath) (btrfsprim.Key, btrfsprim.Key) { // tree root error if len(path) == 0 { - return btrfs.Key{}, maxKey + return btrfsprim.Key{}, maxKey } // item error @@ -81,11 +83,11 @@ func spanOfTreePath(fs *btrfs.FS, path btrfs.TreePath) (btrfs.Key, btrfs.Key) { // // assume that path.Node(-1).ToNodeAddr is not readable, but that path.Node(-2).ToNodeAddr is. if len(path) == 1 { - return btrfs.Key{}, maxKey + return btrfsprim.Key{}, maxKey } parentNode, _ := fs.ReadNode(path.Parent()) low := parentNode.Data.BodyInternal[path.Node(-1).FromItemIdx].Key - var high btrfs.Key + var high btrfsprim.Key if path.Node(-1).FromItemIdx+1 < len(parentNode.Data.BodyInternal) { high = keyMm(parentNode.Data.BodyInternal[path.Node(-1).FromItemIdx+1].Key) } else { @@ -95,21 +97,21 @@ func spanOfTreePath(fs *btrfs.FS, path btrfs.TreePath) (btrfs.Key, btrfs.Key) { return low, high } -func walkFromNode(ctx context.Context, fs *btrfs.FS, nodeAddr btrfsvol.LogicalAddr, errHandle func(*btrfs.TreeError), cbs btrfs.TreeWalkHandler) { +func walkFromNode(ctx context.Context, fs *btrfs.FS, nodeAddr btrfsvol.LogicalAddr, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { sb, _ := fs.Superblock() - nodeRef, _ := btrfs.ReadNode[btrfsvol.LogicalAddr](fs, *sb, nodeAddr, btrfs.NodeExpectations{ + nodeRef, _ := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, nodeAddr, btrfstree.NodeExpectations{ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: nodeAddr}, }) if nodeRef == nil { return } - treeInfo := btrfs.TreeRoot{ + treeInfo := btrfstree.TreeRoot{ TreeID: nodeRef.Data.Head.Owner, RootNode: nodeAddr, Level: nodeRef.Data.Head.Level, Generation: nodeRef.Data.Head.Generation, } - fs.RawTreeWalk(ctx, treeInfo, errHandle, cbs) + btrfstree.TreesImpl{NodeSource: fs}.RawTreeWalk(ctx, treeInfo, errHandle, cbs) } func countNodes(nodeScanResults btrfsinspect.ScanDevicesResult) int { @@ -135,8 +137,8 @@ func lostAndFoundNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsi attachedNodes := make(map[btrfsvol.LogicalAddr]struct{}) btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ - TreeWalkHandler: btrfs.TreeWalkHandler{ - Node: func(path btrfs.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfs.Node]) error { + TreeWalkHandler: btrfstree.TreeWalkHandler{ + Node: func(path btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { attachedNodes[path.Node(-1).ToNodeAddr] = struct{}{} done++ progress(done) @@ -174,11 +176,11 @@ func lostAndFoundNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsi } walkCtx, cancel := context.WithCancel(ctx) walkFromNode(walkCtx, fs, potentialRoot, - func(err *btrfs.TreeError) { + func(err *btrfstree.TreeError) { // do nothing }, - btrfs.TreeWalkHandler{ - PreNode: func(path btrfs.TreePath) error { + btrfstree.TreeWalkHandler{ + PreNode: func(path btrfstree.TreePath) error { nodeAddr := path.Node(-1).ToNodeAddr if nodeAddr != potentialRoot { delete(orphanedRoots, nodeAddr) @@ -197,13 +199,13 @@ func lostAndFoundNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsi return orphanedRoots, nil } -func getChunkTreeUUID(ctx context.Context, fs *btrfs.FS) (btrfs.UUID, bool) { +func getChunkTreeUUID(ctx context.Context, fs *btrfs.FS) (btrfsprim.UUID, bool) { ctx, cancel := context.WithCancel(ctx) - var ret btrfs.UUID + var ret btrfsprim.UUID var retOK bool btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ - TreeWalkHandler: btrfs.TreeWalkHandler{ - Node: func(path btrfs.TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, btrfs.Node]) error { + TreeWalkHandler: btrfstree.TreeWalkHandler{ + Node: func(path btrfstree.TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { ret = node.Data.Head.ChunkTreeUUID retOK = true cancel() @@ -219,8 +221,8 @@ func getChunkTreeUUID(ctx context.Context, fs *btrfs.FS) (btrfs.UUID, bool) { type RebuiltNode struct { Err error - MinKey, MaxKey btrfs.Key - btrfs.Node + MinKey, MaxKey btrfsprim.Key + btrfstree.Node } func reInitBrokenNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult, foundRoots map[btrfsvol.LogicalAddr]struct{}) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { @@ -247,20 +249,20 @@ func reInitBrokenNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsi var done int rebuiltNodes := make(map[btrfsvol.LogicalAddr]*RebuiltNode) - walkHandler := btrfs.TreeWalkHandler{ - Node: func(_ btrfs.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfs.Node]) error { + walkHandler := btrfstree.TreeWalkHandler{ + Node: func(_ btrfstree.TreePath, _ *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { done++ progress(done) return nil }, - BadNode: func(path btrfs.TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, btrfs.Node], err error) error { + BadNode: func(path btrfstree.TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], err error) error { min, max := spanOfTreePath(fs, path) rebuiltNodes[path.Node(-1).ToNodeAddr] = &RebuiltNode{ Err: err, MinKey: min, MaxKey: max, - Node: btrfs.Node{ - Head: btrfs.NodeHeader{ + Node: btrfstree.Node{ + Head: btrfstree.NodeHeader{ MetadataUUID: sb.EffectiveMetadataUUID(), Addr: path.Node(-1).ToNodeAddr, ChunkTreeUUID: chunkTreeUUID, @@ -282,7 +284,7 @@ func reInitBrokenNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsi }) for foundRoot := range foundRoots { walkFromNode(ctx, fs, foundRoot, - func(err *btrfs.TreeError) { + func(err *btrfstree.TreeError) { // do nothing }, walkHandler) @@ -293,8 +295,8 @@ func reInitBrokenNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsi func reAttachNodes(ctx context.Context, fs *btrfs.FS, foundRoots map[btrfsvol.LogicalAddr]struct{}, rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error { // Index 'rebuiltNodes' for fast lookups. - gaps := make(map[btrfs.ObjID]map[uint8][]*RebuiltNode) - maxLevel := make(map[btrfs.ObjID]uint8) + gaps := make(map[btrfsprim.ObjID]map[uint8][]*RebuiltNode) + maxLevel := make(map[btrfsprim.ObjID]uint8) for _, node := range rebuiltNodes { maxLevel[node.Head.Owner] = slices.Max(maxLevel[node.Head.Owner], node.Head.Level) @@ -314,7 +316,7 @@ func reAttachNodes(ctx context.Context, fs *btrfs.FS, foundRoots map[btrfsvol.Lo // Attach foundRoots to the gaps. sb, _ := fs.Superblock() for foundLAddr := range foundRoots { - foundRef, err := btrfs.ReadNode[btrfsvol.LogicalAddr](fs, *sb, foundLAddr, btrfs.NodeExpectations{ + foundRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, foundLAddr, btrfstree.NodeExpectations{ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: foundLAddr}, }) if foundRef == nil { @@ -352,7 +354,7 @@ func reAttachNodes(ctx context.Context, fs *btrfs.FS, foundRoots map[btrfsvol.Lo continue } parent := parentGen[parentIdx] - parent.BodyInternal = append(parent.BodyInternal, btrfs.KeyPointer{ + parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{ Key: foundMinKey, BlockPtr: foundLAddr, Generation: foundRef.Data.Head.Generation, diff --git a/lib/btrfsprogs/btrfsinspect/scandevices.go b/lib/btrfsprogs/btrfsinspect/scandevices.go index 66a14c3..c25a86f 100644 --- a/lib/btrfsprogs/btrfsinspect/scandevices.go +++ b/lib/btrfsprogs/btrfsinspect/scandevices.go @@ -17,7 +17,9 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" "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/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" ) @@ -55,35 +57,35 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS) (ScanDevicesResult, error) { type ScanOneDeviceResult struct { Checksums btrfssum.SumRun[btrfsvol.PhysicalAddr] FoundNodes map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr - FoundChunks []btrfs.SysChunk + FoundChunks []btrfstree.SysChunk FoundBlockGroups []SysBlockGroup FoundDevExtents []SysDevExtent FoundExtentCSums []SysExtentCSum } type SysBlockGroup struct { - Key btrfs.Key + Key btrfsprim.Key BG btrfsitem.BlockGroup } type SysDevExtent struct { - Key btrfs.Key + Key btrfsprim.Key DevExt btrfsitem.DevExtent } type SysExtentCSum struct { - Generation btrfs.Generation + Generation btrfsprim.Generation Sums btrfsitem.ExtentCSum } // ScanOneDevice mostly mimics btrfs-progs // cmds/rescue-chunk-recover.c:scan_one_device(). -func ScanOneDevice(ctx context.Context, dev *btrfs.Device, sb btrfs.Superblock) (ScanOneDeviceResult, error) { +func ScanOneDevice(ctx context.Context, dev *btrfs.Device, sb btrfstree.Superblock) (ScanOneDeviceResult, error) { result := ScanOneDeviceResult{ FoundNodes: make(map[btrfsvol.LogicalAddr][]btrfsvol.PhysicalAddr), } - sbSize := btrfsvol.PhysicalAddr(binstruct.StaticSize(btrfs.Superblock{})) + sbSize := btrfsvol.PhysicalAddr(binstruct.StaticSize(btrfstree.Superblock{})) devSize := dev.Size() if sb.NodeSize < sb.SectorSize { @@ -141,9 +143,9 @@ func ScanOneDevice(ctx context.Context, dev *btrfs.Device, sb btrfs.Superblock) } if checkForNode { - nodeRef, err := btrfs.ReadNode[btrfsvol.PhysicalAddr](dev, sb, pos, btrfs.NodeExpectations{}) + nodeRef, err := btrfstree.ReadNode[btrfsvol.PhysicalAddr](dev, sb, pos, btrfstree.NodeExpectations{}) if err != nil { - if !errors.Is(err, btrfs.ErrNotANode) { + if !errors.Is(err, btrfstree.ErrNotANode) { dlog.Errorf(ctx, "... dev[%q] error: %v", dev.Name(), err) } } else { @@ -159,7 +161,7 @@ func ScanOneDevice(ctx context.Context, dev *btrfs.Device, sb btrfs.Superblock) } //dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found chunk", // dev.Name(), nodeRef.Addr, i) - result.FoundChunks = append(result.FoundChunks, btrfs.SysChunk{ + result.FoundChunks = append(result.FoundChunks, btrfstree.SysChunk{ Key: item.Key, Chunk: chunk, }) diff --git a/lib/btrfsprogs/btrfsutil/broken_btree.go b/lib/btrfsprogs/btrfsutil/broken_btree.go index 3a8fb4b..6afaceb 100644 --- a/lib/btrfsprogs/btrfsutil/broken_btree.go +++ b/lib/btrfsprogs/btrfsutil/broken_btree.go @@ -15,6 +15,8 @@ import ( "github.com/datawire/dlib/dlog" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" @@ -22,18 +24,18 @@ import ( ) type indexValue struct { - Key btrfs.Key + Key btrfsprim.Key ItemSize uint32 - Path btrfs.TreePath + Path btrfstree.TreePath } -var maxKey = btrfs.Key{ +var maxKey = btrfsprim.Key{ ObjectID: math.MaxUint64, ItemType: math.MaxUint8, Offset: math.MaxUint64, } -func keyMm(key btrfs.Key) btrfs.Key { +func keyMm(key btrfsprim.Key) btrfsprim.Key { switch { case key.Offset > 0: key.Offset-- @@ -45,10 +47,10 @@ func keyMm(key btrfs.Key) btrfs.Key { return key } -func span(fs *btrfs.FS, path btrfs.TreePath) (btrfs.Key, btrfs.Key) { +func span(fs *btrfs.FS, path btrfstree.TreePath) (btrfsprim.Key, btrfsprim.Key) { // tree root error if len(path) == 0 { - return btrfs.Key{}, maxKey + return btrfsprim.Key{}, maxKey } // item error @@ -63,11 +65,11 @@ func span(fs *btrfs.FS, path btrfs.TreePath) (btrfs.Key, btrfs.Key) { // // assume that path.Node(-1).NodeAddr is not readable, but that path.Node(-2).NodeAddr is. if len(path) == 1 { - return btrfs.Key{}, maxKey + return btrfsprim.Key{}, maxKey } parentNode, _ := fs.ReadNode(path.Parent()) low := parentNode.Data.BodyInternal[path.Node(-1).FromItemIdx].Key - var high btrfs.Key + var high btrfsprim.Key if path.Node(-1).FromItemIdx+1 < len(parentNode.Data.BodyInternal) { high = keyMm(parentNode.Data.BodyInternal[path.Node(-1).FromItemIdx+1].Key) } else { @@ -78,29 +80,29 @@ func span(fs *btrfs.FS, path btrfs.TreePath) (btrfs.Key, btrfs.Key) { } type spanError struct { - End btrfs.Key + End btrfsprim.Key Err error } type cachedIndex struct { TreeRootErr error - Items *containers.RBTree[btrfs.Key, indexValue] - Errors map[int]map[btrfs.Key][]spanError + Items *containers.RBTree[btrfsprim.Key, indexValue] + Errors map[int]map[btrfsprim.Key][]spanError } type brokenTrees struct { ctx context.Context inner *btrfs.FS - // btrfs.ROOT_TREE_OBJECTID + // btrfsprim.ROOT_TREE_OBJECTID rootTreeMu sync.Mutex rootTreeIndex *cachedIndex // for all other trees treeMu sync.Mutex - treeIndexes map[btrfs.ObjID]cachedIndex + treeIndexes map[btrfsprim.ObjID]cachedIndex } -var _ btrfs.Trees = (*brokenTrees)(nil) +var _ btrfstree.Trees = (*brokenTrees)(nil) // NewBrokenTrees wraps a *btrfs.FS to support looking up information // from broken trees. @@ -120,47 +122,59 @@ var _ btrfs.Trees = (*brokenTrees)(nil) // .TreeWalk to build an out-of-FS index of all of the items in the // tree, and re-implements TreeLookup, TreeSearch, and TreeSearchAll // using that index. -func NewBrokenTrees(ctx context.Context, inner *btrfs.FS) btrfs.Trees { +func NewBrokenTrees(ctx context.Context, inner *btrfs.FS) interface { + btrfstree.Trees + Superblock() (*btrfstree.Superblock, error) + ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) +} { return &brokenTrees{ ctx: ctx, inner: inner, } } -func (bt *brokenTrees) treeIndex(treeID btrfs.ObjID) cachedIndex { - var treeRoot *btrfs.TreeRoot +func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) cachedIndex { + var treeRoot *btrfstree.TreeRoot var err error - if treeID == btrfs.ROOT_TREE_OBJECTID { + if treeID == btrfsprim.ROOT_TREE_OBJECTID { bt.rootTreeMu.Lock() defer bt.rootTreeMu.Unlock() if bt.rootTreeIndex != nil { return *bt.rootTreeIndex } - treeRoot, err = btrfs.LookupTreeRoot(bt.inner, treeID) + var sb *btrfstree.Superblock + sb, err = bt.inner.Superblock() + if err == nil { + treeRoot, err = btrfstree.LookupTreeRoot(bt.inner, *sb, treeID) + } } else { bt.treeMu.Lock() defer bt.treeMu.Unlock() if bt.treeIndexes == nil { - bt.treeIndexes = make(map[btrfs.ObjID]cachedIndex) + bt.treeIndexes = make(map[btrfsprim.ObjID]cachedIndex) } if cacheEntry, exists := bt.treeIndexes[treeID]; exists { return cacheEntry } - treeRoot, err = btrfs.LookupTreeRoot(bt, treeID) + var sb *btrfstree.Superblock + sb, err = bt.inner.Superblock() + if err == nil { + treeRoot, err = btrfstree.LookupTreeRoot(bt, *sb, treeID) + } } var cacheEntry cachedIndex - cacheEntry.Errors = make(map[int]map[btrfs.Key][]spanError) + cacheEntry.Errors = make(map[int]map[btrfsprim.Key][]spanError) if err != nil { cacheEntry.TreeRootErr = err } else { - cacheEntry.Items = &containers.RBTree[btrfs.Key, indexValue]{ - KeyFn: func(iv indexValue) btrfs.Key { return iv.Key }, + cacheEntry.Items = &containers.RBTree[btrfsprim.Key, indexValue]{ + KeyFn: func(iv indexValue) btrfsprim.Key { return iv.Key }, } dlog.Infof(bt.ctx, "indexing tree %v...", treeID) - bt.inner.RawTreeWalk( + btrfstree.TreesImpl{NodeSource: bt.inner}.RawTreeWalk( bt.ctx, *treeRoot, - func(err *btrfs.TreeError) { + func(err *btrfstree.TreeError) { if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 { // This is a panic because on the filesystems I'm working with it more likely // indicates a bug in my item parser than a problem with the filesystem. @@ -169,7 +183,7 @@ func (bt *brokenTrees) treeIndex(treeID btrfs.ObjID) cachedIndex { invLvl := len(err.Path) lvlErrs, ok := cacheEntry.Errors[invLvl] if !ok { - lvlErrs = make(map[btrfs.Key][]spanError) + lvlErrs = make(map[btrfsprim.Key][]spanError) cacheEntry.Errors[invLvl] = lvlErrs } beg, end := span(bt.inner, err.Path) @@ -178,8 +192,8 @@ func (bt *brokenTrees) treeIndex(treeID btrfs.ObjID) cachedIndex { Err: err, }) }, - btrfs.TreeWalkHandler{ - Item: func(path btrfs.TreePath, item btrfs.Item) error { + btrfstree.TreeWalkHandler{ + Item: func(path btrfstree.TreePath, item btrfstree.Item) error { if cacheEntry.Items.Lookup(item.Key) != nil { // This is a panic because I'm not really sure what the best way to // handle this is, and so if this happens I want the program to crash @@ -197,7 +211,7 @@ func (bt *brokenTrees) treeIndex(treeID btrfs.ObjID) cachedIndex { ) dlog.Infof(bt.ctx, "... done indexing tree %v", treeID) } - if treeID == btrfs.ROOT_TREE_OBJECTID { + if treeID == btrfsprim.ROOT_TREE_OBJECTID { bt.rootTreeIndex = &cacheEntry } else { bt.treeIndexes[treeID] = cacheEntry @@ -205,29 +219,29 @@ func (bt *brokenTrees) treeIndex(treeID btrfs.ObjID) cachedIndex { return cacheEntry } -func (bt *brokenTrees) TreeLookup(treeID btrfs.ObjID, key btrfs.Key) (btrfs.Item, error) { - item, err := bt.TreeSearch(treeID, btrfs.KeySearch(key.Cmp)) +func (bt *brokenTrees) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { + item, err := bt.TreeSearch(treeID, btrfstree.KeySearch(key.Cmp)) if err != nil { err = fmt.Errorf("item with key=%v: %w", key, err) } return item, err } -func (bt *brokenTrees) TreeSearch(treeID btrfs.ObjID, fn func(btrfs.Key, uint32) int) (btrfs.Item, error) { +func (bt *brokenTrees) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (btrfstree.Item, error) { index := bt.treeIndex(treeID) if index.TreeRootErr != nil { - return btrfs.Item{}, index.TreeRootErr + return btrfstree.Item{}, index.TreeRootErr } indexItem := index.Items.Search(func(indexItem indexValue) int { return fn(indexItem.Key, indexItem.ItemSize) }) if indexItem == nil { - return btrfs.Item{}, iofs.ErrNotExist + return btrfstree.Item{}, iofs.ErrNotExist } node, err := bt.inner.ReadNode(indexItem.Value.Path.Parent()) if err != nil { - return btrfs.Item{}, err + return btrfstree.Item{}, err } item := node.Data.BodyLeaf[indexItem.Value.Path.Node(-1).FromItemIdx] @@ -235,7 +249,7 @@ func (bt *brokenTrees) TreeSearch(treeID btrfs.ObjID, fn func(btrfs.Key, uint32) return item, nil } -func (bt *brokenTrees) TreeSearchAll(treeID btrfs.ObjID, fn func(btrfs.Key, uint32) int) ([]btrfs.Item, error) { +func (bt *brokenTrees) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]btrfstree.Item, error) { index := bt.treeIndex(treeID) if index.TreeRootErr != nil { return nil, index.TreeRootErr @@ -247,8 +261,8 @@ func (bt *brokenTrees) TreeSearchAll(treeID btrfs.ObjID, fn func(btrfs.Key, uint return nil, iofs.ErrNotExist } - ret := make([]btrfs.Item, len(indexItems)) - var node *diskio.Ref[btrfsvol.LogicalAddr, btrfs.Node] + ret := make([]btrfstree.Item, len(indexItems)) + var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] for i := range indexItems { if node == nil || node.Addr != indexItems[i].Path.Node(-2).ToNodeAddr { var err error @@ -283,18 +297,18 @@ func (bt *brokenTrees) TreeSearchAll(treeID btrfs.ObjID, fn func(btrfs.Key, uint return ret, nil } -func (bt *brokenTrees) TreeWalk(ctx context.Context, treeID btrfs.ObjID, errHandle func(*btrfs.TreeError), cbs btrfs.TreeWalkHandler) { +func (bt *brokenTrees) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { index := bt.treeIndex(treeID) if index.TreeRootErr != nil { - errHandle(&btrfs.TreeError{ - Path: btrfs.TreePath{{ + errHandle(&btrfstree.TreeError{ + Path: btrfstree.TreePath{{ FromTree: treeID, }}, Err: index.TreeRootErr, }) return } - var node *diskio.Ref[btrfsvol.LogicalAddr, btrfs.Node] + var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node] _ = index.Items.Walk(func(indexItem *containers.RBNode[indexValue]) error { if ctx.Err() != nil { return ctx.Err() @@ -307,20 +321,20 @@ func (bt *brokenTrees) TreeWalk(ctx context.Context, treeID btrfs.ObjID, errHand var err error node, err = bt.inner.ReadNode(indexItem.Value.Path.Parent()) if err != nil { - errHandle(&btrfs.TreeError{Path: indexItem.Value.Path, Err: err}) + errHandle(&btrfstree.TreeError{Path: indexItem.Value.Path, Err: err}) return nil } } item := node.Data.BodyLeaf[indexItem.Value.Path.Node(-1).FromItemIdx] if err := cbs.Item(indexItem.Value.Path, item); err != nil { - errHandle(&btrfs.TreeError{Path: indexItem.Value.Path, Err: err}) + errHandle(&btrfstree.TreeError{Path: indexItem.Value.Path, Err: err}) } } return nil }) } -func (bt *brokenTrees) Superblock() (*btrfs.Superblock, error) { +func (bt *brokenTrees) Superblock() (*btrfstree.Superblock, error) { return bt.inner.Superblock() } diff --git a/lib/btrfsprogs/btrfsutil/csums.go b/lib/btrfsprogs/btrfsutil/csums.go index 3c3d85f..a49f584 100644 --- a/lib/btrfsprogs/btrfsutil/csums.go +++ b/lib/btrfsprogs/btrfsutil/csums.go @@ -9,11 +9,12 @@ import ( "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/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" ) -func ChecksumLogical(fs btrfs.Trees, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.CSum, error) { +func ChecksumLogical(fs *btrfs.FS, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.CSum, error) { var dat [btrfssum.BlockSize]byte if _, err := fs.ReadAt(dat[:], laddr); err != nil { return btrfssum.CSum{}, err @@ -37,8 +38,8 @@ func ChecksumQualifiedPhysical(fs *btrfs.FS, alg btrfssum.CSumType, paddr btrfsv return ChecksumPhysical(dev, alg, paddr.Addr) } -func LookupCSum(fs btrfs.Trees, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.SumRun[btrfsvol.LogicalAddr], error) { - item, err := fs.TreeSearch(btrfs.CSUM_TREE_OBJECTID, func(key btrfs.Key, size uint32) int { +func LookupCSum(fs *btrfs.FS, alg btrfssum.CSumType, laddr btrfsvol.LogicalAddr) (btrfssum.SumRun[btrfsvol.LogicalAddr], error) { + item, err := fs.TreeSearch(btrfsprim.CSUM_TREE_OBJECTID, func(key btrfsprim.Key, size uint32) int { itemBeg := btrfsvol.LogicalAddr(key.ObjectID) numSums := int64(size) / int64(alg.Size()) itemEnd := itemBeg + btrfsvol.LogicalAddr(numSums*btrfssum.BlockSize) diff --git a/lib/btrfsprogs/btrfsutil/walk.go b/lib/btrfsprogs/btrfsutil/walk.go index c597e5e..2809737 100644 --- a/lib/btrfsprogs/btrfsutil/walk.go +++ b/lib/btrfsprogs/btrfsutil/walk.go @@ -10,11 +10,13 @@ import ( "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/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" ) type WalkError struct { TreeName string - Err *btrfs.TreeError + Err *btrfstree.TreeError } func (e *WalkError) Unwrap() error { return e.Err } @@ -26,10 +28,10 @@ func (e *WalkError) Error() string { type WalkAllTreesHandler struct { Err func(*WalkError) // Callbacks for entire trees - PreTree func(name string, id btrfs.ObjID) - PostTree func(name string, id btrfs.ObjID) + PreTree func(name string, id btrfsprim.ObjID) + PostTree func(name string, id btrfsprim.ObjID) // Callbacks for nodes or smaller - btrfs.TreeWalkHandler + btrfstree.TreeWalkHandler } // WalkAllTrees walks all trees in a *btrfs.FS. Rather than returning @@ -40,31 +42,31 @@ func WalkAllTrees(ctx context.Context, fs *btrfs.FS, cbs WalkAllTreesHandler) { trees := []struct { Name string - ID btrfs.ObjID + ID btrfsprim.ObjID }{ { Name: "root tree", - ID: btrfs.ROOT_TREE_OBJECTID, + ID: btrfsprim.ROOT_TREE_OBJECTID, }, { Name: "chunk tree", - ID: btrfs.CHUNK_TREE_OBJECTID, + ID: btrfsprim.CHUNK_TREE_OBJECTID, }, { Name: "log tree", - ID: btrfs.TREE_LOG_OBJECTID, + ID: btrfsprim.TREE_LOG_OBJECTID, }, { Name: "block group tree", - ID: btrfs.BLOCK_GROUP_TREE_OBJECTID, + ID: btrfsprim.BLOCK_GROUP_TREE_OBJECTID, }, } origItem := cbs.Item - cbs.Item = func(path btrfs.TreePath, item btrfs.Item) error { + cbs.Item = func(path btrfstree.TreePath, item btrfstree.Item) error { if item.Key.ItemType == btrfsitem.ROOT_ITEM_KEY { trees = append(trees, struct { Name string - ID btrfs.ObjID + ID btrfsprim.ObjID }{ Name: fmt.Sprintf("tree %v (via %v %v)", item.Key.ObjectID.Format(0), treeName, path), @@ -86,7 +88,7 @@ func WalkAllTrees(ctx context.Context, fs *btrfs.FS, cbs WalkAllTreesHandler) { fs.TreeWalk( ctx, tree.ID, - func(err *btrfs.TreeError) { cbs.Err(&WalkError{TreeName: treeName, Err: err}) }, + func(err *btrfstree.TreeError) { cbs.Err(&WalkError{TreeName: treeName, Err: err}) }, cbs.TreeWalkHandler, ) if cbs.PostTree != nil { -- cgit v1.2.3-2-g168b