btrfstree

package
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 11, 2023 License: Apache-2.0, GPL-2.0, GPL-3.0-or-later, + 1 more Imports: 19 Imported by: 0

Documentation

Overview

Package btrfstree contains core b+-tree implementation and interfaces.

Index

Constants

View Source 
const MaxLevel = 8

MaxLevel is the maximum valid NodeHeader.Level.

Variables

View Source 
var (
	ErrNoItem = errNotExist("item")
	ErrNoTree = errNotExist("tree")
)

For both ErrNoItem and ErrNoTree, `errors.Is(err, io/fs.ErrNotExist)` returns true.

View Source 
var ErrNotANode = errors.New("does not look like a node")

Functions

func CheckOwner 

func CheckOwner(
	ctx context.Context, forrest Forrest, treeID btrfsprim.ObjID,
	ownerToCheck btrfsprim.ObjID, genToCheck btrfsprim.Generation,
) error

Types

type BackrefRev 

type BackrefRev uint8
const (
	OldBackrefRev BackrefRev = iota
	MixedBackrefRev
)

type Forrest 

type Forrest interface {
	// ForrestLookup returns (nil, ErrNoTree) if the tree does not
	// exist but there is otherwise no error.
	ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (Tree, error)
}

type IOError 

type IOError struct {
	Err error
}

func (*IOError) Error 

func (e *IOError) Error() string

func (*IOError) Unwrap 

func (e *IOError) Unwrap() error

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 Item struct {
	Key      btrfsprim.Key
	BodySize uint32 // [ignored-when-writing]
	Body     btrfsitem.Item
}

type ItemHeader 

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"`
}

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 

func ReadNode[Addr ~int64](fs diskio.ReaderAt[Addr], sb Superblock, addr Addr) (*Node, error)

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) CalculateChecksum 

func (node Node) CalculateChecksum() (btrfssum.CSum, error)

func (*Node) LeafFreeSpace 

func (node *Node) LeafFreeSpace() uint32

func (Node) MarshalBinary 

func (node Node) MarshalBinary() ([]byte, error)

func (Node) MaxItem 

func (node Node) MaxItem() (btrfsprim.Key, bool)

func (Node) MaxItems 

func (node Node) MaxItems() uint32

MaxItems returns the maximum possible valid value of .Head.NumItems.

func (Node) MinItem 

func (node Node) MinItem() (btrfsprim.Key, bool)

func (*Node) RawFree 

func (node *Node) RawFree()

RawFree is for low-level use by caches; don't use .RawFree, use ReleaseNode.

func (*Node) UnmarshalBinary 

func (node *Node) UnmarshalBinary(nodeBuf []byte) (int, error)

func (Node) ValidateChecksum 

func (node Node) ValidateChecksum() error

type NodeError 

type NodeError[Addr ~int64] struct {
	Op       string
	NodeAddr Addr
	Err      error
}

func (*NodeError[Addr]) Error 

func (e *NodeError[Addr]) Error() string

func (*NodeError[Addr]) Unwrap 

func (e *NodeError[Addr]) Unwrap() error

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 NodeFlags 

type NodeFlags uint64
const (
	NodeWritten NodeFlags = 1 << iota
	NodeReloc
)

func (NodeFlags) BinaryStaticSize 

func (NodeFlags) BinaryStaticSize() int

func (NodeFlags) Has 

func (f NodeFlags) Has(req NodeFlags) bool

func (NodeFlags) MarshalBinary 

func (f NodeFlags) MarshalBinary() ([]byte, error)

func (NodeFlags) String 

func (f NodeFlags) String() string

func (*NodeFlags) UnmarshalBinary 

func (f *NodeFlags) UnmarshalBinary(dat []byte) (int, 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.

func (Path) Parent 

func (path Path) Parent() Path

func (Path) String 

func (path Path) String() string

type PathElem 

type PathElem interface {
	// contains filtered or unexported methods
}

A PathElem is either a PathRoot, a PathKP, or a PathItem.

type PathItem 

type PathItem struct {
	// From the containing Node.
	FromTree btrfsprim.ObjID
	FromSlot int
	// From the Item itself.
	ToKey btrfsprim.Key
}

type PathKP 

type PathKP struct {
	// From the containing Node.
	FromTree btrfsprim.ObjID
	FromSlot int
	// From the KP itself.
	ToAddr       btrfsvol.LogicalAddr
	ToGeneration btrfsprim.Generation
	ToMinKey     btrfsprim.Key
	// From the structure of the tree.
	ToMaxKey btrfsprim.Key
	ToLevel  uint8
}

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 

func (forrest RawForrest) ForrestLookup(ctx context.Context, treeID btrfsprim.ObjID) (Tree, error)

ForrestLookup implements Forrest.

func (RawForrest) RawTree 

func (forrest RawForrest) RawTree(ctx context.Context, treeID btrfsprim.ObjID) (*RawTree, error)

RawTree is a variant of ForrestLookup that returns a concrete type instead of an interface.

type RawTree 

type RawTree struct {
	Forrest RawForrest
	TreeRoot
}

RawTree implements Tree.

func (*RawTree) TreeLookup 

func (tree *RawTree) TreeLookup(ctx context.Context, key btrfsprim.Key) (Item, error)

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 

func (tree *RawTree) TreeRange(ctx context.Context, handleFn func(Item) bool) error

TreeRange implements the 'Tree' interface.

func (*RawTree) TreeSearch 

func (tree *RawTree) TreeSearch(ctx context.Context, searcher TreeSearcher) (Item, error)

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 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 

func SearchExactKey(k btrfsprim.Key) Search

SearchExactKey returns a Search that searches for the exact key.

func SearchObject 

func SearchObject(objID btrfsprim.ObjID) Search

SearchObject returns a Search that searches all items belonging to a given object.

func SearchRootItem 

func SearchRootItem(treeID btrfsprim.ObjID) Search

SearchRootItem returns a Search that searches for the root item for the given tree.

func (Search) Compare 

func (a Search) Compare(b Search) int

Compare implements containers.Ordered.

func (Search) Search 

func (o Search) Search(k btrfsprim.Key, _ uint32) int

Search implements TreeSearcher.

func (Search) String 

func (o Search) String() string

String implements fmt.Stringer (and 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 SysChunk struct {
	Key   btrfsprim.Key
	Chunk btrfsitem.Chunk
}

func (SysChunk) MarshalBinary 

func (sc SysChunk) MarshalBinary() ([]byte, error)

func (*SysChunk) UnmarshalBinary 

func (sc *SysChunk) UnmarshalBinary(dat []byte) (int, error)

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)
}

Source Files

  • btree.go
  • btree_err.go
  • btree_forrest.go
  • btree_searchers.go
  • btree_tree.go
  • node_exp.go
  • path.go
  • types_node.go
  • types_superblock.go

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.