Documentation ¶
Overview ¶
Package btrfstree contains core b+-tree implementation and interfaces.
Index ¶
- Constants
- Variables
- func CheckOwner(ctx context.Context, forrest Forrest, treeID btrfsprim.ObjID, ...) error
- type BackrefRev
- type Forrest
- type IOError
- type IncompatFlags
- type Item
- type ItemHeader
- type KeyPointer
- type Node
- func (node Node) CalculateChecksum() (btrfssum.CSum, error)
- func (node *Node) LeafFreeSpace() uint32
- func (node Node) MarshalBinary() ([]byte, error)
- func (node Node) MaxItem() (btrfsprim.Key, bool)
- func (node Node) MaxItems() uint32
- func (node Node) MinItem() (btrfsprim.Key, bool)
- func (node *Node) RawFree()
- func (node *Node) UnmarshalBinary(nodeBuf []byte) (int, error)
- func (node Node) ValidateChecksum() error
- type NodeError
- type NodeExpectations
- type NodeFlags
- type NodeHeader
- type NodeSource
- type Path
- type PathElem
- type PathItem
- type PathKP
- type PathRoot
- type RawForrest
- type RawTree
- func (tree *RawTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (Item, error)
- func (tree *RawTree) TreeParentID(ctx context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error)
- func (tree *RawTree) TreeRange(ctx context.Context, handleFn func(Item) bool) error
- func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Item, error)
- func (tree *RawTree) TreeSubrange(ctx context.Context, min int, searcher TreeSearcher, handleFn func(Item) bool) error
- func (tree *RawTree) TreeWalk(ctx context.Context, cbs TreeWalkHandler)
- type RootBackup
- type Search
- type SearchItemType
- type SearchOffset
- type Superblock
- type SysChunk
- type Tree
- type TreeRoot
- type TreeSearcher
- type TreeWalkHandler
Constants ¶
const MaxLevel = 8
MaxLevel is the maximum valid NodeHeader.Level.
Variables ¶
var ( ErrNoItem = errNotExist("item") ErrNoTree = errNotExist("tree") )
For both ErrNoItem and ErrNoTree, `errors.Is(err, io/fs.ErrNotExist)` returns true.
Functions ¶
Types ¶
type Forrest ¶
type IncompatFlags ¶
type IncompatFlags uint64
const ( FeatureIncompatMixedBackref IncompatFlags = 1 << iota FeatureIncompatDefaultSubvol FeatureIncompatMixedGroups FeatureIncompatCompressLZO FeatureIncompatCompressZSTD FeatureIncompatBigMetadata // buggy FeatureIncompatExtendedIRef FeatureIncompatRAID56 FeatureIncompatSkinnyMetadata FeatureIncompatNoHoles FeatureIncompatMetadataUUID FeatureIncompatRAID1C34 FeatureIncompatZoned FeatureIncompatExtentTreeV2 )
func (IncompatFlags) Has ¶
func (f IncompatFlags) Has(req IncompatFlags) bool
func (IncompatFlags) String ¶
func (f IncompatFlags) String() string
type Item ¶
type ItemHeader ¶
type KeyPointer ¶
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"` }
type Node ¶
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) BodyInterior []KeyPointer // for interior nodes BodyLeaf []Item // for leave nodes Padding []byte }
func ReadNode ¶
ReadNode reads a node from the given file.
It is possible that both a non-nil diskio.Ref and an error are returned. The error returned (if non-nil) is always of type *NodeError[Addr]. Notable errors that may be inside of the NodeError are ErrNotANode and *IOError.
func (Node) MaxItems ¶
MaxItems returns the maximum possible valid value of .Head.NumItems.
type NodeError ¶
type NodeExpectations ¶
type NodeExpectations struct { LAddr containers.Optional[btrfsvol.LogicalAddr] // Things knowable from the parent. Level containers.Optional[uint8] Generation containers.Optional[btrfsprim.Generation] Owner func(btrfsprim.ObjID, btrfsprim.Generation) error MinItem containers.Optional[btrfsprim.Key] // Things knowable from the structure of the tree. MaxItem containers.Optional[btrfsprim.Key] }
func (NodeExpectations) Check ¶
func (exp NodeExpectations) Check(node *Node) error
type NodeHeader ¶
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 interior nodes (max 8) binstruct.End `bin:"off=0x65"` }
type NodeSource ¶
type NodeSource interface { Superblock() (*Superblock, error) AcquireNode(ctx context.Context, addr btrfsvol.LogicalAddr, exp NodeExpectations) (*Node, error) ReleaseNode(*Node) }
type Path ¶
type Path []PathElem
Path is a path from the superblock or a ROOT_ITEM to a node or item within one of the btrees in the system.
The first element will always have a FromSlot 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] | | <------------------------------------------ PathRoot={Tree:B, | ToAddr:0x01, ToGen=6, ToLvl=3} +[0x01]-------------+ | lvl=3 gen=6 own=B | +-+-+-+-+-+-+-+-+-+-+ |0|1|2|3|4|5|6|7|8|9| +-+-+-+-+-+-+-+-+-+-+ | | <------------------------------ PathKP={FromTree:B, FromSlot:7, | ToAddr:0x02, ToGen:5, ToLvl:2} +[0x02]--------------+ | lvl=2 gen=5 own=B | +-+-+-+-+-+-+-+-+-+-+ |0|1|2|3|4|5|6|7|8|9| +-+-+-+-+-+-+-+-+-+-+ | | <-------------------- PathKP={FromTree:B, FromSlot:6, | ToAddr:0x03, ToGen:5, ToLvl:1} +[0x03]-------------+ | lvl=1 gen=5 own=A | +-+-+-+-+-+-+-+-+-+-+ |0|1|2|3|4|5|6|7|8|9| +-+-+-+-+-+-+-+-+-+-+ | | <---------------- PathKP={FromTree:A, FromSlot:3, | ToAddr:0x04, ToGen:2, ToLvl:0} +[0x04]-------------+ | lvl=0 gen=2 own=A | +-+-+-+-+-+-+-+-+-+-+ |0|1|2|3|4|5|6|7|8|9| +-+-+-+-+-+-+-+-+-+-+ | | <--------------- PathItem={FromTree:A, FromSlot:1} | [item]
func (Path) NodeExpectations ¶
func (path Path) NodeExpectations(ctx context.Context) (_ btrfsvol.LogicalAddr, _ NodeExpectations, ok bool)
NodeExpectations returns the address to read and the expectations to have when reading the node pointed to by this Path.
`ok` is false if the path is empty or if this Path points to an item rather than a node.
type PathElem ¶
type PathElem interface {
// contains filtered or unexported methods
}
A PathElem is either a PathRoot, a PathKP, or a PathItem.
type PathItem ¶
type PathKP ¶
type PathRoot ¶
type PathRoot struct { Forrest Forrest // It should be no surprise that these 4 members mimic the 4 // members of a 'RawTree'. TreeID btrfsprim.ObjID ToAddr btrfsvol.LogicalAddr ToGeneration btrfsprim.Generation ToLevel uint8 }
type RawForrest ¶
type RawForrest struct {
NodeSource NodeSource
}
RawForrest implements Forrest.
func (RawForrest) ForrestLookup ¶
ForrestLookup implements Forrest.
type RawTree ¶
type RawTree struct { Forrest RawForrest TreeRoot }
RawTree implements Tree.
func (*RawTree) TreeLookup ¶
TreeLookup implements the 'Tree' interface.
func (*RawTree) TreeParentID ¶
func (tree *RawTree) TreeParentID(ctx context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error)
TreeParentID implements the 'Tree' interface.
func (*RawTree) TreeRange ¶
TreeRange implements the 'Tree' interface.
func (*RawTree) TreeSearch ¶
TreeSearch implements the 'Tree' interface.
func (*RawTree) TreeSubrange ¶
func (tree *RawTree) TreeSubrange(ctx context.Context, min int, searcher TreeSearcher, handleFn func(Item) bool) error
TreeSubrange implements the 'Tree' interface.
func (*RawTree) TreeWalk ¶
func (tree *RawTree) TreeWalk(ctx context.Context, cbs TreeWalkHandler)
TreeWalk implements the 'Tree' interface.
type RootBackup ¶
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 Search ¶
type Search struct { ObjectID btrfsprim.ObjID ItemTypeMatching SearchItemType ItemType btrfsprim.ItemType // Offset is totally ignored if .ItemTypeMatching=ItemTypeany. OffsetMatching SearchOffset OffsetLow uint64 // only for .OffsetMatching==OffsetExact or .OffsetMatching==OffsetRange OffsetHigh uint64 // only for .OffsetMatching==OffsetRange OffsetName string // only for .OffsetMatching==OffsetName }
Search is a fairly generic and reusable implementation of TreeSearcher.
func SearchExactKey ¶
SearchExactKey returns a Search that searches for the exact key.
func SearchObject ¶
SearchObject returns a Search that searches all items belonging to a given object.
func SearchRootItem ¶
SearchRootItem returns a Search that searches for the root item for the given tree.
func (Search) Compare ¶
Compare implements containers.Ordered.
func (Search) Search ¶
Search implements TreeSearcher.
type SearchItemType ¶
type SearchItemType int8
const ( ItemTypeAny SearchItemType = iota ItemTypeExact )
type SearchOffset ¶
type SearchOffset int8
const ( OffsetAny SearchOffset = iota OffsetExact OffsetRange // .Search behaves same as OffsetAny (TODO?) OffsetName // .Search behaves same as OffsetAny )
type Superblock ¶
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 (Superblock) CalculateChecksum ¶
func (sb Superblock) CalculateChecksum() (btrfssum.CSum, error)
func (Superblock) EffectiveMetadataUUID ¶
func (sb Superblock) EffectiveMetadataUUID() btrfsprim.UUID
func (Superblock) Equal ¶
func (a Superblock) Equal(b Superblock) bool
func (Superblock) ParseSysChunkArray ¶
func (sb Superblock) ParseSysChunkArray() ([]SysChunk, error)
func (Superblock) ValidateChecksum ¶
func (sb Superblock) ValidateChecksum() error
type SysChunk ¶
type Tree ¶
type Tree interface { // TreeParentID returns the ID of this tree's parent and the // generation that this tree was split from its parent. If // this tree has no parent, then (0, 0, nil) is returned. TreeParentID(ctx context.Context) (btrfsprim.ObjID, btrfsprim.Generation, error) // TreeLookup looks up the Item for a given key. // // If no such Item exists, but there is otherwise no error, // then ErrNoItem is returned. TreeLookup(ctx context.Context, key btrfsprim.Key) (Item, error) // TreeSearch searches the Tree for a value for which // `search.Search(itemKey, itemSize) == 0`. // // : + + + 0 0 0 - - - // : ^ ^ ^ // : any of // // You can conceptualize `search.Search` as subtraction: // // func(strawKey btrfsprim.Key, strawSize uint32) int { // return needle - straw // } // // `search.Search` may be called with key/size pairs that do not // correspond to an existing Item (for key-pointers in // interior nodes in the tree); in which case the size // math.MaxUint32. // // If no such Item exists, but there is otherwise no error, // then an error that is ErrNoItem is returned. TreeSearch(ctx context.Context, search TreeSearcher) (Item, error) // TreeRange iterates over the Tree in order, calling // `handleFn` for each Item. TreeRange(ctx context.Context, handleFn func(Item) bool) error // TreeSubrange iterates over the Tree in order, calling // `handleFn` for all Items for which `search.Search` returns // 0. // // `search.Search` may be called with key/size pairs that do // not correspond to an existing Item (for key-pointers in // interior nodes in the tree); in which case the size // math.MaxUint32. // // If handleFn is called for fewer than `min` items, an error // that is ErrNoItem is returned. TreeSubrange(ctx context.Context, min int, search TreeSearcher, handleFn func(Item) bool, ) error // TreeWalk is a lower-level call than TreeSubrange. Use with // hesitancy. // // It 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: // // 000 (read superblock) (maybe cbs.BadSuperblock()) // // 001 (read node) // 002 cbs.Node() or cbs.BadNode() // if interior: // for kp in node.items: // 003a if cbs.PreKeyPointer == nil || cbs.PreKeyPointer() { // 004b (recurse) // else: // for item in node.items: // 003b cbs.Item() or cbs.BadItem() TreeWalk(ctx context.Context, cbs TreeWalkHandler) }
type TreeRoot ¶
type TreeRoot struct { ID btrfsprim.ObjID RootNode btrfsvol.LogicalAddr Level uint8 Generation btrfsprim.Generation RootInode btrfsprim.ObjID // only for subvolume trees ParentUUID btrfsprim.UUID ParentGen btrfsprim.Generation // offset of this tree's root item }
A TreeRoot is more-or-less a btrfsitem.Root, but simpler; returned by LookupTreeRoot.
func LookupTreeRoot ¶
func LookupTreeRoot(ctx context.Context, forrest Forrest, sb Superblock, treeID btrfsprim.ObjID) (*TreeRoot, error)
LookupTreeRoot is a utility function to help with implementing the 'Forrest' interface.
The 'forrest' passed to LookupTreeRoot must handle:
forrest.ForrestLookup(ctx, btrfsprim.ROOT_TREE_OBJECTID)
It is OK for forrest.ForrestLookup to recurse and call LookupTreeRoot, as LookupTreeRoot will not call ForrestLookup for ROOT_TREE_OBJECTID; so it will not be an infinite recursion.
type TreeSearcher ¶
type TreeSearcher interface { // How the search should be described in the event of an // error. fmt.Stringer // size is math.MaxUint32 for key-pointers Search(key btrfsprim.Key, size uint32) int }
func SearchCSum ¶
func SearchCSum(laddr btrfsvol.LogicalAddr, algSize int) TreeSearcher
SearchCSum returns a TreeSearcher that searches for a csum-run containing the csum for a given LogicalAddress.
type TreeWalkHandler ¶
type TreeWalkHandler struct { BadSuperblock func(error) // Callbacks for entire nodes. // // The return value from BadNode is whether to process the // slots in this node or not; if no BadNode function is given, // then it is not processed. Node func(Path, *Node) BadNode func(Path, *Node, error) bool // Callbacks for slots in nodes. // // The return value from KeyPointer is whether to recurse or // not; if no KeyPointer function is given, then it is // recursed. KeyPointer func(Path, KeyPointer) bool Item func(Path, Item) BadItem func(Path, Item) }