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/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 ++++++++++ 10 files changed, 1464 insertions(+) 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 (limited to 'lib/btrfs/btrfstree') 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) +} -- cgit v1.2.3-2-g168b