path: root/lib/btrfsprogs/btrfsutil/broken_btree.go

// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later

package btrfsutil

import (
	"context"
	"fmt"
	iofs "io/fs"
	"sync"

	"github.com/datawire/dlib/derror"
	"github.com/datawire/dlib/dlog"

	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
	"git.lukeshu.com/btrfs-progs-ng/lib/diskio"
)

type treeIndex struct {
	TreeRootErr error
	Items       *containers.RBTree[treeIndexValue]
	Errors      *containers.IntervalTree[btrfsprim.Key, treeIndexError]
}

type treeIndexError struct {
	Path SkinnyPath
	Err  error
}

type treeIndexValue struct {
	Path     SkinnyPath
	Key      btrfsprim.Key
	ItemSize uint32
}

// Compare implements containers.Ordered.
func (a treeIndexValue) Compare(b treeIndexValue) int {
	return a.Key.Compare(b.Key)
}

func newTreeIndex(arena *SkinnyPathArena) treeIndex {
	return treeIndex{
		Items: new(containers.RBTree[treeIndexValue]),
		Errors: &containers.IntervalTree[btrfsprim.Key, treeIndexError]{
			MinFn: func(err treeIndexError) btrfsprim.Key {
				return arena.Inflate(err.Path).Node(-1).ToKey
			},
			MaxFn: func(err treeIndexError) btrfsprim.Key {
				return arena.Inflate(err.Path).Node(-1).ToMaxKey
			},
		},
	}
}

type brokenTrees struct {
	ctx   context.Context //nolint:containedctx // don't have an option while keeping the same API
	inner *btrfs.FS

	arena *SkinnyPathArena

	// btrfsprim.ROOT_TREE_OBJECTID
	rootTreeMu    sync.Mutex
	rootTreeIndex *treeIndex
	// for all other trees
	treeMu      sync.Mutex
	treeIndexes map[btrfsprim.ObjID]treeIndex
}

var _ btrfstree.TreeOperator = (*brokenTrees)(nil)

// NewBrokenTrees wraps a *btrfs.FS to support looking up information
// from broken trees.
//
// Of the btrfstree.TreeOperator methods:
//
//   - TreeWalk works on broken trees
//   - TreeLookup relies on the tree being properly ordered (which a
//     broken tree might not be).
//   - TreeSearch relies on the tree being properly ordered (which a
//     broken tree might not be).
//   - TreeSearchAll relies on the tree being properly ordered (which a
//     broken tree might not be), and a bad node may cause it to not
//     return a truncated list of results.
//
// NewBrokenTrees attempts to remedy these deficiencies by using
// .TreeWalk to build an out-of-FS index of all of the items in the
// tree, and re-implements TreeLookup, TreeSearch, and TreeSearchAll
// using that index.
func NewBrokenTrees(ctx context.Context, inner *btrfs.FS) interface {
	btrfstree.TreeOperator
	Superblock() (*btrfstree.Superblock, error)
	ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error)
	Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error)
} {
	return &brokenTrees{
		ctx:   ctx,
		inner: inner,
	}
}

func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex {
	var treeRoot *btrfstree.TreeRoot
	var sb *btrfstree.Superblock
	var err error
	if treeID == btrfsprim.ROOT_TREE_OBJECTID {
		bt.rootTreeMu.Lock()
		defer bt.rootTreeMu.Unlock()
		if bt.rootTreeIndex != nil {
			return *bt.rootTreeIndex
		}
		sb, err = bt.inner.Superblock()
		if err == nil {
			treeRoot, err = btrfstree.LookupTreeRoot(bt.inner, *sb, treeID)
		}
	} else {
		bt.treeMu.Lock()
		defer bt.treeMu.Unlock()
		if bt.treeIndexes == nil {
			bt.treeIndexes = make(map[btrfsprim.ObjID]treeIndex)
		}
		if cacheEntry, exists := bt.treeIndexes[treeID]; exists {
			return cacheEntry
		}
		sb, err = bt.inner.Superblock()
		if err == nil {
			treeRoot, err = btrfstree.LookupTreeRoot(bt, *sb, treeID)
		}
	}
	if bt.arena == nil {
		var _sb btrfstree.Superblock
		if sb != nil {
			_sb = *sb
		}
		bt.arena = &SkinnyPathArena{
			FS: bt.inner,
			SB: _sb,
		}
	}
	cacheEntry := newTreeIndex(bt.arena)
	if err != nil {
		cacheEntry.TreeRootErr = err
	} else {
		dlog.Infof(bt.ctx, "indexing tree %v...", treeID)
		bt.rawTreeWalk(*treeRoot, cacheEntry, nil)
		dlog.Infof(bt.ctx, "... done indexing tree %v", treeID)
	}
	if treeID == btrfsprim.ROOT_TREE_OBJECTID {
		bt.rootTreeIndex = &cacheEntry
	} else {
		bt.treeIndexes[treeID] = cacheEntry
	}
	return cacheEntry
}

func (bt *brokenTrees) rawTreeWalk(root btrfstree.TreeRoot, cacheEntry treeIndex, walked *[]btrfsprim.Key) {
	btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk(
		bt.ctx,
		root,
		func(err *btrfstree.TreeError) {
			if len(err.Path) > 0 && err.Path.Node(-1).ToNodeAddr == 0 {
				// This is a panic because on the filesystems I'm working with it more likely
				// indicates a bug in my item parser than a problem with the filesystem.
				panic(fmt.Errorf("TODO: error parsing item: %w", err))
			}
			cacheEntry.Errors.Insert(treeIndexError{
				Path: bt.arena.Deflate(err.Path),
				Err:  err.Err,
			})
		},
		btrfstree.TreeWalkHandler{
			Item: func(path btrfstree.TreePath, item btrfstree.Item) error {
				if cacheEntry.Items.Search(func(v treeIndexValue) int { return item.Key.Compare(v.Key) }) != nil {
					// This is a panic because I'm not really sure what the best way to
					// handle this is, and so if this happens I want the program to crash
					// and force me to figure out how to handle it.
					panic(fmt.Errorf("dup key=%v in tree=%v", item.Key, root.TreeID))
				}
				cacheEntry.Items.Insert(treeIndexValue{
					Path:     bt.arena.Deflate(path),
					Key:      item.Key,
					ItemSize: item.BodySize,
				})
				if walked != nil {
					*walked = append(*walked, item.Key)
				}
				return nil
			},
		},
	)
}

func (bt *brokenTrees) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) {
	item, err := bt.TreeSearch(treeID, btrfstree.KeySearch(key.Compare))
	if err != nil {
		err = fmt.Errorf("item with key=%v: %w", key, err)
	}
	return item, err
}

func (bt *brokenTrees) addErrs(index treeIndex, fn func(btrfsprim.Key, uint32) int, err error) error {
	var errs derror.MultiError
	index.Errors.Subrange(
		func(k btrfsprim.Key) int { return fn(k, 0) },
		func(v treeIndexError) bool {
			errs = append(errs, &btrfstree.TreeError{
				Path: bt.arena.Inflate(v.Path),
				Err:  v.Err,
			})
			return true
		})
	if len(errs) == 0 {
		return err
	}
	if err != nil {
		errs = append(errs, err)
	}
	return errs
}

func (bt *brokenTrees) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (btrfstree.Item, error) {
	index := bt.treeIndex(treeID)
	if index.TreeRootErr != nil {
		return btrfstree.Item{}, index.TreeRootErr
	}

	indexItem := index.Items.Search(func(indexItem treeIndexValue) int {
		return fn(indexItem.Key, indexItem.ItemSize)
	})
	if indexItem == nil {
		return btrfstree.Item{}, bt.addErrs(index, fn, iofs.ErrNotExist)
	}

	itemPath := bt.arena.Inflate(indexItem.Value.Path)
	node, err := bt.inner.ReadNode(itemPath.Parent())
	defer btrfstree.FreeNodeRef(node)
	if err != nil {
		return btrfstree.Item{}, bt.addErrs(index, fn, err)
	}

	item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
	item.Body = item.Body.CloneItem()

	// Since we were only asked to return 1 item, it isn't
	// necessary to augment this `nil` with bt.addErrs().
	return item, nil
}

func (bt *brokenTrees) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]btrfstree.Item, error) {
	index := bt.treeIndex(treeID)
	if index.TreeRootErr != nil {
		return nil, index.TreeRootErr
	}

	var indexItems []treeIndexValue
	index.Items.Subrange(
		func(indexItem treeIndexValue) int { return fn(indexItem.Key, indexItem.ItemSize) },
		func(node *containers.RBNode[treeIndexValue]) bool {
			indexItems = append(indexItems, node.Value)
			return true
		})
	if len(indexItems) == 0 {
		return nil, bt.addErrs(index, fn, iofs.ErrNotExist)
	}

	ret := make([]btrfstree.Item, len(indexItems))
	var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
	for i := range indexItems {
		itemPath := bt.arena.Inflate(indexItems[i].Path)
		if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
			var err error
			btrfstree.FreeNodeRef(node)
			node, err = bt.inner.ReadNode(itemPath.Parent())
			if err != nil {
				btrfstree.FreeNodeRef(node)
				return nil, bt.addErrs(index, fn, err)
			}
		}
		ret[i] = node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
	}
	btrfstree.FreeNodeRef(node)

	return ret, bt.addErrs(index, fn, nil)
}

func (bt *brokenTrees) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) {
	index := bt.treeIndex(treeID)
	if index.TreeRootErr != nil {
		errHandle(&btrfstree.TreeError{
			Path: btrfstree.TreePath{{
				FromTree: treeID,
				ToMaxKey: btrfsprim.MaxKey,
			}},
			Err: index.TreeRootErr,
		})
		return
	}
	var node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]
	index.Items.Range(func(indexItem *containers.RBNode[treeIndexValue]) bool {
		if ctx.Err() != nil {
			return false
		}
		if bt.ctx.Err() != nil {
			return false
		}
		if cbs.Item != nil {
			itemPath := bt.arena.Inflate(indexItem.Value.Path)
			if node == nil || node.Addr != itemPath.Node(-2).ToNodeAddr {
				var err error
				btrfstree.FreeNodeRef(node)
				node, err = bt.inner.ReadNode(itemPath.Parent())
				if err != nil {
					btrfstree.FreeNodeRef(node)
					errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
					return true
				}
			}
			item := node.Data.BodyLeaf[itemPath.Node(-1).FromItemIdx]
			if err := cbs.Item(itemPath, item); err != nil {
				errHandle(&btrfstree.TreeError{Path: itemPath, Err: err})
			}
		}
		return true
	})
	btrfstree.FreeNodeRef(node)
}

func (bt *brokenTrees) Superblock() (*btrfstree.Superblock, error) {
	return bt.inner.Superblock()
}

func (bt *brokenTrees) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) {
	return bt.inner.ReadAt(p, off)
}

func (bt *brokenTrees) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error) {
	sb, err := bt.Superblock()
	if err != nil {
		return nil, err
	}
	index := bt.treeIndex(treeID)
	if index.TreeRootErr != nil {
		return nil, index.TreeRootErr
	}
	nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](bt.inner, *sb, nodeAddr, btrfstree.NodeExpectations{})
	defer btrfstree.FreeNodeRef(nodeRef)
	if err != nil {
		return nil, err
	}
	var ret []btrfsprim.Key
	bt.rawTreeWalk(btrfstree.TreeRoot{
		TreeID:     treeID,
		RootNode:   nodeAddr,
		Level:      nodeRef.Data.Head.Level,
		Generation: nodeRef.Data.Head.Generation,
	}, index, &ret)
	return ret, nil
}