From 22c32850798c264b6a20539b9cd1699228368ce9 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 7 Jul 2022 02:51:57 -0600 Subject: write btrfs-clear-bad-nodes --- pkg/btrfs/io3_btree.go | 44 ++++- pkg/btrfs/io3_fs.go | 426 ------------------------------------------------ pkg/btrfs/io4_fs.go | 426 ++++++++++++++++++++++++++++++++++++++++++++++++ pkg/btrfs/types_node.go | 11 +- pkg/btrfsmisc/walk.go | 59 +++++-- 5 files changed, 518 insertions(+), 448 deletions(-) delete mode 100644 pkg/btrfs/io3_fs.go create mode 100644 pkg/btrfs/io4_fs.go (limited to 'pkg') diff --git a/pkg/btrfs/io3_btree.go b/pkg/btrfs/io3_btree.go index 01da746..3c1535b 100644 --- a/pkg/btrfs/io3_btree.go +++ b/pkg/btrfs/io3_btree.go @@ -19,9 +19,49 @@ import ( // - For .Item() callbacks, the last element will always have a // NodeAddr of 0. // -// ex: +// For example, given the tree structure // -// {-1, 0x01, 3}→{9, 0x02, 2}→{9, 0x03, 1}→{9, 0x04, 0}→{9, 0, 0} +// [superblock] +// | +// | <------------------------------------------ pathElem={idx:-1, addr:0x01, lvl:3} +// | +// +[0x01]-----------+ +// | lvl=3 | +// +-+-+-+-+-+-+-+-+-+ +// |1|2|3|4|5|6|7|8|9| +// +---+---+---+---+-+ +// | +// | <------------------------------ pathElem={idx:8, addr:0x02, lvl:2} +// | +// +[0x02]-----------+ +// | lvl=2 | +// +-+-+-+-+-+-+-+-+-+ +// |1|2|3|4|5|6|7|8|9| +// +---+---+---+---+-+ +// | +// | <-------------------- pathElem={idx:7, addr:0x03, lvl:1} +// | +// +[0x03]-----------+ +// | lvl=1 | +// +-+-+-+-+-+-+-+-+-+ +// |1|2|3|4|5|6|7|8|9| +// +---+---+---+---+-+ +// | +// | <---------------- pathElem={idx:4, addr:0x04, lvl:0} +// | +// +[0x04]-----------+ +// | lvl=0 | +// +-+-+-+-+-+-+-+-+-+ +// |1|2|3|4|5|6|7|8|9| +// +---+---+---+---+-+ +// | +// | <--------------- pathElem={idx:5, addr:0, lvl:0} +// | +// [item] +// +// the path would be +// +// {-1, 0x01, 3}→{8, 0x02, 2}→{7, 0x03, 1}→{4, 0x04, 0}→{2, 0, 0} type TreePath []TreePathElem // A TreePathElem essentially represents a KeyPointer. diff --git a/pkg/btrfs/io3_fs.go b/pkg/btrfs/io3_fs.go deleted file mode 100644 index 75b973b..0000000 --- a/pkg/btrfs/io3_fs.go +++ /dev/null @@ -1,426 +0,0 @@ -package btrfs - -import ( - "fmt" - "io" - "path/filepath" - "reflect" - "sort" - "sync" - - "github.com/datawire/dlib/derror" - - "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" - "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol" - "lukeshu.com/btrfs-tools/pkg/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() { - sb, err := sv.FS.Superblock() - if err != nil { - sv.rootErr = err - return - } - - root, err := sv.FS.TreeLookup(sb.Data.RootTree, 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) GetFSTree() (btrfsvol.LogicalAddr, error) { - sv.init() - return sv.rootVal.ByteNr, sv.rootErr -} - -func (sv *Subvolume) LoadBareInode(inode ObjID) (*BareInode, error) { - val := sv.bareInodeCache.GetOrElse(inode, func() (val *BareInode) { - val = &BareInode{ - Inode: inode, - } - tree, err := sv.GetFSTree() - if err != nil { - val.Errs = append(val.Errs, err) - return - } - item, err := sv.FS.TreeLookup(tree, 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, - }, - } - tree, err := sv.GetFSTree() - if err != nil { - val.Errs = append(val.Errs, err) - return - } - items, err := sv.FS.TreeSearchAll(tree, 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++ - } - } - return -} - -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) diff --git a/pkg/btrfs/io4_fs.go b/pkg/btrfs/io4_fs.go new file mode 100644 index 0000000..75b973b --- /dev/null +++ b/pkg/btrfs/io4_fs.go @@ -0,0 +1,426 @@ +package btrfs + +import ( + "fmt" + "io" + "path/filepath" + "reflect" + "sort" + "sync" + + "github.com/datawire/dlib/derror" + + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsvol" + "lukeshu.com/btrfs-tools/pkg/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() { + sb, err := sv.FS.Superblock() + if err != nil { + sv.rootErr = err + return + } + + root, err := sv.FS.TreeLookup(sb.Data.RootTree, 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) GetFSTree() (btrfsvol.LogicalAddr, error) { + sv.init() + return sv.rootVal.ByteNr, sv.rootErr +} + +func (sv *Subvolume) LoadBareInode(inode ObjID) (*BareInode, error) { + val := sv.bareInodeCache.GetOrElse(inode, func() (val *BareInode) { + val = &BareInode{ + Inode: inode, + } + tree, err := sv.GetFSTree() + if err != nil { + val.Errs = append(val.Errs, err) + return + } + item, err := sv.FS.TreeLookup(tree, 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, + }, + } + tree, err := sv.GetFSTree() + if err != nil { + val.Errs = append(val.Errs, err) + return + } + items, err := sv.FS.TreeSearchAll(tree, 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++ + } + } + return +} + +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) diff --git a/pkg/btrfs/types_node.go b/pkg/btrfs/types_node.go index 8aafc49..92f7513 100644 --- a/pkg/btrfs/types_node.go +++ b/pkg/btrfs/types_node.go @@ -49,6 +49,13 @@ var nodeFlagNames = []string{ func (f NodeFlags) Has(req NodeFlags) bool { return f&req == req } func (f NodeFlags) String() string { return util.BitfieldString(f, nodeFlagNames, util.HexLower) } +type BackrefRev uint8 + +const ( + OldBackrefRev = BackrefRev(iota) + MixedBackrefRev = BackrefRev(iota) +) + // Node: main ////////////////////////////////////////////////////////////////////////////////////// type Node struct { @@ -72,7 +79,7 @@ type NodeHeader struct { MetadataUUID 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 uint8 `bin:"off=0x3f, siz=0x1"` + BackrefRev BackrefRev `bin:"off=0x3f, siz=0x1"` ChunkTreeUUID UUID `bin:"off=0x40, siz=0x10"` Generation Generation `bin:"off=0x50, siz=0x8"` Owner ObjID `bin:"off=0x58, siz=0x8"` // The ID of the tree that contains this node @@ -347,7 +354,7 @@ func ReadNode[Addr ~int64](fs util.File[Addr], sb Superblock, addr Addr, laddrCB // sanity checking if nodeRef.Data.Head.MetadataUUID != sb.EffectiveMetadataUUID() { - return nil, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, ErrNotANode) + return nodeRef, fmt.Errorf("btrfs.ReadNode: node@%v: %w", addr, ErrNotANode) } stored := nodeRef.Data.Head.Checksum diff --git a/pkg/btrfsmisc/walk.go b/pkg/btrfsmisc/walk.go index 7d08394..0f3f811 100644 --- a/pkg/btrfsmisc/walk.go +++ b/pkg/btrfsmisc/walk.go @@ -30,6 +30,7 @@ type WalkFSHandler struct { PreTree func(name string, laddr btrfsvol.LogicalAddr) PostTree func(name string, laddr btrfsvol.LogicalAddr) // Callbacks for nodes or smaller + UnsafeNodes bool btrfs.TreeWalkHandler } @@ -73,15 +74,17 @@ func WalkFS(fs *btrfs.FS, cbs WalkFSHandler) { return nil } - origNode := cbs.Node - cbs.Node = func(path btrfs.TreePath, node *util.Ref[btrfsvol.LogicalAddr, btrfs.Node], err error) error { - if err != nil { - handleErr(path, err) - } - if node != nil && origNode != nil { - return origNode(path, node, nil) + if !cbs.UnsafeNodes { + origNode := cbs.Node + cbs.Node = func(path btrfs.TreePath, node *util.Ref[btrfsvol.LogicalAddr, btrfs.Node], err error) error { + if err != nil { + handleErr(path, err) + } + if node != nil && origNode != nil { + return origNode(path, node, nil) + } + return nil } - return nil } treeName = "superblock" @@ -92,39 +95,59 @@ func WalkFS(fs *btrfs.FS, cbs WalkFSHandler) { } treeName = "root tree" - cbs.PreTree(treeName, superblock.Data.RootTree) + if cbs.PreTree != nil { + cbs.PreTree(treeName, superblock.Data.RootTree) + } if err := fs.TreeWalk(superblock.Data.RootTree, cbs.TreeWalkHandler); err != nil { handleErr(nil, err) } - cbs.PostTree(treeName, superblock.Data.RootTree) + if cbs.PostTree != nil { + cbs.PostTree(treeName, superblock.Data.RootTree) + } treeName = "chunk tree" - cbs.PreTree(treeName, superblock.Data.ChunkTree) + if cbs.PreTree != nil { + cbs.PreTree(treeName, superblock.Data.ChunkTree) + } if err := fs.TreeWalk(superblock.Data.ChunkTree, cbs.TreeWalkHandler); err != nil { handleErr(nil, err) } - cbs.PostTree(treeName, superblock.Data.ChunkTree) + if cbs.PostTree != nil { + cbs.PostTree(treeName, superblock.Data.ChunkTree) + } treeName = "log tree" - cbs.PreTree(treeName, superblock.Data.LogTree) + if cbs.PreTree != nil { + cbs.PreTree(treeName, superblock.Data.LogTree) + } if err := fs.TreeWalk(superblock.Data.LogTree, cbs.TreeWalkHandler); err != nil { handleErr(nil, err) } - cbs.PostTree(treeName, superblock.Data.LogTree) + if cbs.PostTree != nil { + cbs.PostTree(treeName, superblock.Data.LogTree) + } treeName = "block group tree" - cbs.PreTree(treeName, superblock.Data.BlockGroupRoot) + if cbs.PreTree != nil { + cbs.PreTree(treeName, superblock.Data.BlockGroupRoot) + } if err := fs.TreeWalk(superblock.Data.BlockGroupRoot, cbs.TreeWalkHandler); err != nil { handleErr(nil, err) } - cbs.PostTree(treeName, superblock.Data.BlockGroupRoot) + if cbs.PostTree != nil { + cbs.PostTree(treeName, superblock.Data.BlockGroupRoot) + } for _, tree := range foundTrees { treeName = tree.Name - cbs.PreTree(treeName, tree.Root) + if cbs.PreTree != nil { + cbs.PreTree(treeName, tree.Root) + } if err := fs.TreeWalk(tree.Root, cbs.TreeWalkHandler); err != nil { handleErr(nil, err) } - cbs.PostTree(treeName, tree.Root) + if cbs.PostTree != nil { + cbs.PostTree(treeName, tree.Root) + } } } -- cgit v1.2.3-2-g168b