1 files changed, 404 insertions, 0 deletions
diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go
new file mode 100644
index 0000000..7ae30cb
--- /dev/null
+++ b/lib/btrfs/io4_fs.go
@@ -0,0 +1,404 @@
+package btrfs
+
+import (
+	"fmt"
+	"io"
+	"path/filepath"
+	"reflect"
+	"sort"
+	"sync"
+
+	"github.com/datawire/dlib/derror"
+
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
+	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/util"
+)
+
+type BareInode struct {
+	Inode     ObjID
+	InodeItem *btrfsitem.Inode
+	Errs      derror.MultiError
+}
+
+type FullInode struct {
+	BareInode
+	OtherItems []Item
+}
+
+type InodeRef struct {
+	Inode ObjID
+	btrfsitem.InodeRef
+}
+
+type Dir struct {
+	FullInode
+	DotDot          *InodeRef
+	ChildrenByName  map[string]btrfsitem.DirEntry
+	ChildrenByIndex map[uint64]btrfsitem.DirEntry
+	SV              *Subvolume
+}
+
+type FileExtent struct {
+	OffsetWithinFile int64
+	btrfsitem.FileExtent
+}
+
+type File struct {
+	FullInode
+	Extents []FileExtent
+	SV      *Subvolume
+}
+
+type Subvolume struct {
+	FS     *FS
+	TreeID ObjID
+
+	rootOnce sync.Once
+	rootVal  btrfsitem.Root
+	rootErr  error
+
+	bareInodeCache util.LRUCache[ObjID, *BareInode]
+	fullInodeCache util.LRUCache[ObjID, *FullInode]
+	dirCache       util.LRUCache[ObjID, *Dir]
+	fileCache      util.LRUCache[ObjID, *File]
+}
+
+func (sv *Subvolume) init() {
+	sv.rootOnce.Do(func() {
+		root, err := sv.FS.TreeLookup(ROOT_TREE_OBJECTID, Key{
+			ObjectID: sv.TreeID,
+			ItemType: btrfsitem.ROOT_ITEM_KEY,
+			Offset:   0,
+		})
+		if err != nil {
+			sv.rootErr = err
+			return
+		}
+
+		rootBody, ok := root.Body.(btrfsitem.Root)
+		if !ok {
+			sv.rootErr = fmt.Errorf("FS_TREE ROOT_ITEM has malformed body")
+			return
+		}
+
+		sv.rootVal = rootBody
+	})
+}
+
+func (sv *Subvolume) GetRootInode() (ObjID, error) {
+	sv.init()
+	return sv.rootVal.RootDirID, sv.rootErr
+}
+
+func (sv *Subvolume) LoadBareInode(inode ObjID) (*BareInode, error) {
+	val := sv.bareInodeCache.GetOrElse(inode, func() (val *BareInode) {
+		val = &BareInode{
+			Inode: inode,
+		}
+		item, err := sv.FS.TreeLookup(sv.TreeID, Key{
+			ObjectID: inode,
+			ItemType: btrfsitem.INODE_ITEM_KEY,
+			Offset:   0,
+		})
+		if err != nil {
+			val.Errs = append(val.Errs, err)
+			return
+		}
+
+		itemBody, ok := item.Body.(btrfsitem.Inode)
+		if !ok {
+			val.Errs = append(val.Errs, fmt.Errorf("malformed inode"))
+			return
+		}
+		val.InodeItem = &itemBody
+
+		return
+	})
+	if val.InodeItem == nil {
+		return nil, val.Errs
+	}
+	return val, nil
+}
+
+func (sv *Subvolume) LoadFullInode(inode ObjID) (*FullInode, error) {
+	val := sv.fullInodeCache.GetOrElse(inode, func() (val *FullInode) {
+		val = &FullInode{
+			BareInode: BareInode{
+				Inode: inode,
+			},
+		}
+		items, err := sv.FS.TreeSearchAll(sv.TreeID, func(key Key) int {
+			return util.CmpUint(inode, key.ObjectID)
+		})
+		if err != nil {
+			val.Errs = append(val.Errs, err)
+			if len(items) == 0 {
+				return
+			}
+		}
+		for _, item := range items {
+			switch item.Head.Key.ItemType {
+			case btrfsitem.INODE_ITEM_KEY:
+				itemBody := item.Body.(btrfsitem.Inode)
+				if val.InodeItem != nil {
+					if !reflect.DeepEqual(itemBody, *val.InodeItem) {
+						val.Errs = append(val.Errs, fmt.Errorf("multiple inodes"))
+					}
+					continue
+				}
+				val.InodeItem = &itemBody
+			default:
+				val.OtherItems = append(val.OtherItems, item)
+			}
+		}
+		return
+	})
+	if val.InodeItem == nil && val.OtherItems == nil {
+		return nil, val.Errs
+	}
+	return val, nil
+}
+
+func (sv *Subvolume) LoadDir(inode ObjID) (*Dir, error) {
+	val := sv.dirCache.GetOrElse(inode, func() (val *Dir) {
+		val = new(Dir)
+		fullInode, err := sv.LoadFullInode(inode)
+		if err != nil {
+			val.Errs = append(val.Errs, err)
+			return
+		}
+		val.FullInode = *fullInode
+		val.SV = sv
+		val.populate()
+		return
+	})
+	if val.Inode == 0 {
+		return nil, val.Errs
+	}
+	return val, nil
+}
+
+func (ret *Dir) populate() {
+	ret.ChildrenByName = make(map[string]btrfsitem.DirEntry)
+	ret.ChildrenByIndex = make(map[uint64]btrfsitem.DirEntry)
+	for _, item := range ret.OtherItems {
+		switch item.Head.Key.ItemType {
+		case btrfsitem.INODE_REF_KEY:
+			ref := InodeRef{
+				Inode:    ObjID(item.Head.Key.Offset),
+				InodeRef: item.Body.(btrfsitem.InodeRef),
+			}
+			if ret.DotDot != nil {
+				if !reflect.DeepEqual(ref, *ret.DotDot) {
+					ret.Errs = append(ret.Errs, fmt.Errorf("multiple INODE_REF items on a directory"))
+				}
+				continue
+			}
+			ret.DotDot = &ref
+		case btrfsitem.DIR_ITEM_KEY:
+			body := item.Body.(btrfsitem.DirEntries)
+			if len(body) != 1 {
+				ret.Errs = append(ret.Errs, fmt.Errorf("multiple direntries in single DIR_ITEM?"))
+				continue
+			}
+			for _, entry := range body {
+				namehash := btrfsitem.NameHash(entry.Name)
+				if namehash != item.Head.Key.Offset {
+					ret.Errs = append(ret.Errs, fmt.Errorf("direntry crc32c mismatch: key=%#x crc32c(%q)=%#x",
+						item.Head.Key.Offset, entry.Name, namehash))
+					continue
+				}
+				if other, exists := ret.ChildrenByName[string(entry.Name)]; exists {
+					if !reflect.DeepEqual(entry, other) {
+						ret.Errs = append(ret.Errs, fmt.Errorf("multiple instances of direntry name %q", entry.Name))
+					}
+					continue
+				}
+				ret.ChildrenByName[string(entry.Name)] = entry
+			}
+		case btrfsitem.DIR_INDEX_KEY:
+			index := item.Head.Key.Offset
+			body := item.Body.(btrfsitem.DirEntries)
+			if len(body) != 1 {
+				ret.Errs = append(ret.Errs, fmt.Errorf("multiple direntries in single DIR_INDEX?"))
+				continue
+			}
+			for _, entry := range body {
+				if other, exists := ret.ChildrenByIndex[index]; exists {
+					if !reflect.DeepEqual(entry, other) {
+						ret.Errs = append(ret.Errs, fmt.Errorf("multiple instances of direntry index %v", index))
+					}
+					continue
+				}
+				ret.ChildrenByIndex[index] = entry
+			}
+		//case btrfsitem.XATTR_ITEM_KEY:
+		default:
+			panic(fmt.Errorf("TODO: handle item type %v", item.Head.Key.ItemType))
+		}
+	}
+	entriesWithIndexes := make(map[string]struct{})
+	nextIndex := uint64(2)
+	for index, entry := range ret.ChildrenByIndex {
+		if index+1 > nextIndex {
+			nextIndex = index + 1
+		}
+		entriesWithIndexes[string(entry.Name)] = struct{}{}
+		if other, exists := ret.ChildrenByName[string(entry.Name)]; !exists {
+			ret.Errs = append(ret.Errs, fmt.Errorf("missing by-name direntry for %q", entry.Name))
+			ret.ChildrenByName[string(entry.Name)] = entry
+		} else if !reflect.DeepEqual(entry, other) {
+			ret.Errs = append(ret.Errs, fmt.Errorf("direntry index %v and direntry name %q disagree", index, entry.Name))
+			ret.ChildrenByName[string(entry.Name)] = entry
+		}
+	}
+	for _, name := range util.SortedMapKeys(ret.ChildrenByName) {
+		if _, exists := entriesWithIndexes[name]; !exists {
+			ret.Errs = append(ret.Errs, fmt.Errorf("missing by-index direntry for %q", name))
+			ret.ChildrenByIndex[nextIndex] = ret.ChildrenByName[name]
+			nextIndex++
+		}
+	}
+}
+
+func (dir *Dir) AbsPath() (string, error) {
+	rootInode, err := dir.SV.GetRootInode()
+	if err != nil {
+		return "", err
+	}
+	if rootInode == dir.Inode {
+		return "/", nil
+	}
+	if dir.DotDot == nil {
+		return "", fmt.Errorf("missing .. entry in dir inode %v", dir.Inode)
+	}
+	parent, err := dir.SV.LoadDir(dir.DotDot.Inode)
+	if err != nil {
+		return "", err
+	}
+	parentName, err := parent.AbsPath()
+	if err != nil {
+		return "", err
+	}
+	return filepath.Join(parentName, string(dir.DotDot.Name)), nil
+}
+
+func (sv *Subvolume) LoadFile(inode ObjID) (*File, error) {
+	val := sv.fileCache.GetOrElse(inode, func() (val *File) {
+		val = new(File)
+		fullInode, err := sv.LoadFullInode(inode)
+		if err != nil {
+			val.Errs = append(val.Errs, err)
+			return
+		}
+		val.FullInode = *fullInode
+		val.SV = sv
+		val.populate()
+		return
+	})
+	if val.Inode == 0 {
+		return nil, val.Errs
+	}
+	return val, nil
+}
+
+func (ret *File) populate() {
+	for _, item := range ret.OtherItems {
+		switch item.Head.Key.ItemType {
+		case btrfsitem.INODE_REF_KEY:
+			// TODO
+		case btrfsitem.EXTENT_DATA_KEY:
+			ret.Extents = append(ret.Extents, FileExtent{
+				OffsetWithinFile: int64(item.Head.Key.Offset),
+				FileExtent:       item.Body.(btrfsitem.FileExtent),
+			})
+		default:
+			panic(fmt.Errorf("TODO: handle item type %v", item.Head.Key.ItemType))
+		}
+	}
+
+	// These should already be sorted, because of the nature of
+	// the btree; but this is a recovery tool for corrupt
+	// filesystems, so go ahead and ensure that it's sorted.
+	sort.Slice(ret.Extents, func(i, j int) bool {
+		return ret.Extents[i].OffsetWithinFile < ret.Extents[j].OffsetWithinFile
+	})
+
+	pos := int64(0)
+	for _, extent := range ret.Extents {
+		if extent.OffsetWithinFile != pos {
+			if extent.OffsetWithinFile > pos {
+				ret.Errs = append(ret.Errs, fmt.Errorf("extent gap from %v to %v",
+					pos, extent.OffsetWithinFile))
+			} else {
+				ret.Errs = append(ret.Errs, fmt.Errorf("extent overlap from %v to %v",
+					extent.OffsetWithinFile, pos))
+			}
+		}
+		size, err := extent.Size()
+		if err != nil {
+			ret.Errs = append(ret.Errs, fmt.Errorf("extent %v: %w", extent.OffsetWithinFile, err))
+		}
+		pos += size
+	}
+	if ret.InodeItem != nil && pos != ret.InodeItem.Size {
+		if ret.InodeItem.Size > pos {
+			ret.Errs = append(ret.Errs, fmt.Errorf("extent gap from %v to %v",
+				pos, ret.InodeItem.Size))
+		} else {
+			ret.Errs = append(ret.Errs, fmt.Errorf("extent mapped past end of file from %v to %v",
+				ret.InodeItem.Size, pos))
+		}
+	}
+}
+
+func (file *File) ReadAt(dat []byte, off int64) (int, error) {
+	// These stateles maybe-short-reads each do an O(n) extent
+	// lookup, so reading a file is O(n^2), but we expect n to be
+	// small, so whatev.  Turn file.Extents it in to an rbtree if
+	// it becomes a problem.
+	done := 0
+	for done < len(dat) {
+		n, err := file.maybeShortReadAt(dat[done:], off+int64(done))
+		done += n
+		if err != nil {
+			return done, err
+		}
+	}
+	return done, nil
+}
+
+func (file *File) maybeShortReadAt(dat []byte, off int64) (int, error) {
+	for _, extent := range file.Extents {
+		extBeg := extent.OffsetWithinFile
+		if extBeg > off {
+			break
+		}
+		extLen, err := extent.Size()
+		if err != nil {
+			continue
+		}
+		extEnd := extBeg + extLen
+		if extEnd <= off {
+			continue
+		}
+		offsetWithinExt := off - extent.OffsetWithinFile
+		readSize := util.Min(int64(len(dat)), extLen-offsetWithinExt)
+		switch extent.Type {
+		case btrfsitem.FILE_EXTENT_INLINE:
+			return copy(dat, extent.BodyInline[offsetWithinExt:offsetWithinExt+readSize]), nil
+		case btrfsitem.FILE_EXTENT_REG, btrfsitem.FILE_EXTENT_PREALLOC:
+			return file.SV.FS.ReadAt(dat[:readSize],
+				extent.BodyExtent.DiskByteNr.
+					Add(extent.BodyExtent.Offset).
+					Add(btrfsvol.AddrDelta(offsetWithinExt)))
+		}
+	}
+	if file.InodeItem != nil && off >= file.InodeItem.Size {
+		return 0, io.EOF
+	}
+	return 0, fmt.Errorf("read: could not map position %v", off)
+}
+
+var _ io.ReaderAt = (*File)(nil)