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/types_node.go | 454 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 454 insertions(+) create mode 100644 lib/btrfs/btrfstree/types_node.go (limited to 'lib/btrfs/btrfstree/types_node.go') 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 +} -- cgit v1.2.3-54-g00ecf