From 3f027da8ec796e64b28489f8ddcc4e82e3aa595a Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 19 Oct 2022 23:30:06 -0600 Subject: skinny paths: Don't have the cache be so big --- lib/btrfsprogs/btrfsutil/skinny_paths.go | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsutil/skinny_paths.go b/lib/btrfsprogs/btrfsutil/skinny_paths.go index f7d1924..2f71968 100644 --- a/lib/btrfsprogs/btrfsutil/skinny_paths.go +++ b/lib/btrfsprogs/btrfsutil/skinny_paths.go @@ -39,8 +39,10 @@ func (a *SkinnyPathArena) init() { // item, that's about 16M items. But with overhead of the // LRUCache, it's actually a lot higher than that. So then I // cut it to .5M, and that cut my total memory use to ~8GB, - // which is a good number for me. - a.fatItems = containers.NewLRUCache[skinnyItem, btrfstree.TreePathElem](512 * 1024) + // which is a good number for me. Then I tought it to do a + // better job of recovering trees, and so the memory grew, and I + // cut it to 64K. Then to 8K. Then grew it to 128K. + a.fatItems = containers.NewLRUCache[skinnyItem, btrfstree.TreePathElem](128 * 1024) } } -- cgit v1.2.3-2-g168b From 87b11decd105d620b3ad6f56c45b9bf1cf86a1b3 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 23 Oct 2022 21:18:15 -0600 Subject: containers: Add a 'SortedMap' type --- lib/containers/sortedmap.go | 76 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 76 insertions(+) create mode 100644 lib/containers/sortedmap.go (limited to 'lib') diff --git a/lib/containers/sortedmap.go b/lib/containers/sortedmap.go new file mode 100644 index 0000000..b759fa3 --- /dev/null +++ b/lib/containers/sortedmap.go @@ -0,0 +1,76 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package containers + +import ( + "errors" +) + +type orderedKV[K Ordered[K], V any] struct { + K K + V V +} + +type SortedMap[K Ordered[K], V any] struct { + inner RBTree[K, orderedKV[K, V]] +} + +func (m *SortedMap[K, V]) init() { + if m.inner.KeyFn == nil { + m.inner.KeyFn = m.keyFn + } +} + +func (m *SortedMap[K, V]) keyFn(kv orderedKV[K, V]) K { + return kv.K +} + +func (m *SortedMap[K, V]) Delete(key K) { + m.init() + m.inner.Delete(key) +} + +func (m *SortedMap[K, V]) Load(key K) (value V, ok bool) { + m.init() + node := m.inner.Lookup(key) + if node == nil { + var zero V + return zero, false + } + return node.Value.V, true +} + +var errStop = errors.New("stop") + +func (m *SortedMap[K, V]) Range(f func(key K, value V) bool) { + m.init() + _ = m.inner.Walk(func(node *RBNode[orderedKV[K, V]]) error { + if f(node.Value.K, node.Value.V) { + return nil + } else { + return errStop + } + }) +} + +func (m *SortedMap[K, V]) Subrange(rangeFn func(K, V) int, handleFn func(K, V) bool) { + m.init() + kvs := m.inner.SearchRange(func(kv orderedKV[K, V]) int { + return rangeFn(kv.K, kv.V) + }) + for _, kv := range kvs { + if !handleFn(kv.K, kv.V) { + break + } + } +} + +func (m *SortedMap[K, V]) Store(key K, value V) { + m.init() + m.inner.Insert(orderedKV[K, V]{ + K: key, + V: value, + }) +} -- cgit v1.2.3-2-g168b From 85169c799b4a0d4ba7d39347c07690dc0b49a1d1 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 7 Dec 2022 22:08:51 -0700 Subject: containers.Set: Don't use constraints.Ordered --- lib/btrfs/btrfsvol/chunk.go | 4 +- lib/btrfs/btrfsvol/lvm.go | 8 ++- .../btrfsinspect/rebuildmappings/blockgroups.go | 7 +-- lib/containers/ordered.go | 4 +- lib/containers/set.go | 57 +++++++++++++++++++--- 5 files changed, 62 insertions(+), 18 deletions(-) (limited to 'lib') diff --git a/lib/btrfs/btrfsvol/chunk.go b/lib/btrfs/btrfsvol/chunk.go index 8a2d439..5f1baa8 100644 --- a/lib/btrfs/btrfsvol/chunk.go +++ b/lib/btrfs/btrfsvol/chunk.go @@ -70,11 +70,11 @@ func (a chunkMapping) union(rest ...chunkMapping) (chunkMapping, error) { } } // figure out the physical stripes (.PAddrs) - paddrs := make(map[QualifiedPhysicalAddr]struct{}) + paddrs := make(containers.Set[QualifiedPhysicalAddr]) for _, chunk := range chunks { offsetWithinRet := chunk.LAddr.Sub(ret.LAddr) for _, stripe := range chunk.PAddrs { - paddrs[stripe.Add(-offsetWithinRet)] = struct{}{} + paddrs.Insert(stripe.Add(-offsetWithinRet)) } } ret.PAddrs = maps.Keys(paddrs) diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go index e12e53e..c7551fc 100644 --- a/lib/btrfs/btrfsvol/lvm.go +++ b/lib/btrfs/btrfsvol/lvm.go @@ -256,9 +256,7 @@ func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping { return ret } -// paddrs isn't a containers.Set because QualifiedPhysicalAddr is not -// an ordered type. -func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs map[QualifiedPhysicalAddr]struct{}, maxlen AddrDelta) { +func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs containers.Set[QualifiedPhysicalAddr], maxlen AddrDelta) { node := lv.logical2physical.Search(func(chunk chunkMapping) int { return chunkMapping{LAddr: laddr, Size: 1}.cmpRange(chunk) }) @@ -269,10 +267,10 @@ func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs map[ chunk := node.Value offsetWithinChunk := laddr.Sub(chunk.LAddr) - paddrs = make(map[QualifiedPhysicalAddr]struct{}) + paddrs = make(containers.Set[QualifiedPhysicalAddr]) maxlen = chunk.Size - offsetWithinChunk for _, stripe := range chunk.PAddrs { - paddrs[stripe.Add(offsetWithinChunk)] = struct{}{} + paddrs.Insert(stripe.Add(offsetWithinChunk)) } return paddrs, maxlen diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go index a638f7c..0e2d5a0 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go @@ -10,6 +10,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) @@ -21,14 +22,14 @@ type BlockGroup struct { func DedupBlockGroups(scanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]BlockGroup, error) { // Dedup - bgsSet := make(map[BlockGroup]struct{}) // Can't use containers.Set because BlockGroup isn't ordered + bgsSet := make(containers.Set[BlockGroup]) for _, devResults := range scanResults { for _, bg := range devResults.FoundBlockGroups { - bgsSet[BlockGroup{ + bgsSet.Insert(BlockGroup{ LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID), Size: btrfsvol.AddrDelta(bg.Key.Offset), Flags: bg.BG.Flags, - }] = struct{}{} + }) } } diff --git a/lib/containers/ordered.go b/lib/containers/ordered.go index 038edf8..d918149 100644 --- a/lib/containers/ordered.go +++ b/lib/containers/ordered.go @@ -8,10 +8,12 @@ import ( "golang.org/x/exp/constraints" ) -type Ordered[T interface{ Cmp(T) int }] interface { +type _Ordered[T any] interface { Cmp(T) int } +type Ordered[T _Ordered[T]] _Ordered[T] + type NativeOrdered[T constraints.Ordered] struct { Val T } diff --git a/lib/containers/set.go b/lib/containers/set.go index 1c525ca..d3f8ca7 100644 --- a/lib/containers/set.go +++ b/lib/containers/set.go @@ -5,27 +5,70 @@ package containers import ( + "fmt" "io" + "sort" "git.lukeshu.com/go/lowmemjson" - "golang.org/x/exp/constraints" "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) // Set[T] is an unordered set of T. -// -// Despite Set[T] being unordered, T is required to be an ordered type -// in order that a Set[T] have a deterministic JSON representation. -type Set[T constraints.Ordered] map[T]struct{} +type Set[T comparable] map[T]struct{} var ( _ lowmemjson.Encodable = Set[int]{} _ lowmemjson.Decodable = (*Set[int])(nil) ) +func cast[T any](x any) T { return x.(T) } + func (o Set[T]) EncodeJSON(w io.Writer) error { - return lowmemjson.Encode(w, maps.SortedKeys(o)) + var less func(a, b T) bool + var zero T + switch (any(zero)).(type) { + case _Ordered[T]: + less = func(a, b T) bool { return cast[_Ordered[T]](a).Cmp(b) < 0 } + // This is the constraints.Ordered list + case string: + less = func(a, b T) bool { return cast[string](a) < cast[string](b) } + case int: + less = func(a, b T) bool { return cast[int](a) < cast[int](b) } + case int8: + less = func(a, b T) bool { return cast[int8](a) < cast[int8](b) } + case int16: + less = func(a, b T) bool { return cast[int16](a) < cast[int16](b) } + case int32: + less = func(a, b T) bool { return cast[int32](a) < cast[int32](b) } + case int64: + less = func(a, b T) bool { return cast[int64](a) < cast[int64](b) } + case uint: + less = func(a, b T) bool { return cast[uint](a) < cast[uint](b) } + case uint8: + less = func(a, b T) bool { return cast[uint8](a) < cast[uint8](b) } + case uint16: + less = func(a, b T) bool { return cast[uint16](a) < cast[uint16](b) } + case uint32: + less = func(a, b T) bool { return cast[uint32](a) < cast[uint32](b) } + case uint64: + less = func(a, b T) bool { return cast[uint64](a) < cast[uint64](b) } + case uintptr: + less = func(a, b T) bool { return cast[uintptr](a) < cast[uintptr](b) } + case float32: + less = func(a, b T) bool { return cast[float32](a) < cast[float32](b) } + case float64: + less = func(a, b T) bool { return cast[float64](a) < cast[float64](b) } + default: + less = func(a, b T) bool { return fmt.Sprint(a) < fmt.Sprint(b) } + } + + keys := maps.Keys(o) + sort.Slice(keys, func(i, j int) bool { + return less(keys[i], keys[j]) + }) + + return lowmemjson.Encode(w, keys) } func (o *Set[T]) DecodeJSON(r io.RuneScanner) error { @@ -49,7 +92,7 @@ func (o *Set[T]) DecodeJSON(r io.RuneScanner) error { }) } -func NewSet[T constraints.Ordered](values ...T) Set[T] { +func NewSet[T comparable](values ...T) Set[T] { ret := make(Set[T], len(values)) for _, value := range values { ret.Insert(value) -- cgit v1.2.3-2-g168b From 53a2ce3b4dcbfd17ac15230da17130a2aeae42dc Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 17 Oct 2022 00:15:06 -0600 Subject: Add and improve comments --- lib/btrfs/btrfsitem/item_blockgroup.go | 2 +- lib/btrfs/btrfsitem/item_devextent.go | 6 +++--- lib/btrfs/btrfsitem/item_extent.go | 2 ++ lib/btrfs/btrfsitem/item_extentdataref.go | 10 ++++++---- lib/btrfs/btrfsitem/item_freespacebitmap.go | 2 ++ lib/btrfs/btrfsitem/item_freespaceinfo.go | 22 ++++++++++++++++++++-- lib/btrfs/btrfsitem/item_inode.go | 4 +++- lib/btrfs/btrfsitem/item_root.go | 14 +++++++++----- lib/btrfs/btrfsitem/item_rootref.go | 11 +++++++++-- lib/btrfs/btrfsitem/item_shareddataref.go | 6 +++++- lib/btrfsprogs/btrfsutil/broken_btree.go | 2 +- 11 files changed, 61 insertions(+), 20 deletions(-) (limited to 'lib') diff --git a/lib/btrfs/btrfsitem/item_blockgroup.go b/lib/btrfs/btrfsitem/item_blockgroup.go index 96ce218..6fc09ac 100644 --- a/lib/btrfs/btrfsitem/item_blockgroup.go +++ b/lib/btrfs/btrfsitem/item_blockgroup.go @@ -14,7 +14,7 @@ import ( // key.offset = size of chunk type BlockGroup struct { // BLOCK_GROUP_ITEM=192 Used int64 `bin:"off=0, siz=8"` - ChunkObjectID btrfsprim.ObjID `bin:"off=8, siz=8"` // always BTRFS_FIRST_CHUNK_TREE_OBJECTID + ChunkObjectID btrfsprim.ObjID `bin:"off=8, siz=8"` // always FIRST_CHUNK_TREE_OBJECTID Flags btrfsvol.BlockGroupFlags `bin:"off=16, siz=8"` binstruct.End `bin:"off=24"` } diff --git a/lib/btrfs/btrfsitem/item_devextent.go b/lib/btrfs/btrfsitem/item_devextent.go index 8f5f05c..47bdbcf 100644 --- a/lib/btrfs/btrfsitem/item_devextent.go +++ b/lib/btrfs/btrfsitem/item_devextent.go @@ -13,9 +13,9 @@ import ( // key.objectid = device_id // key.offset = physical_addr type DevExtent struct { // DEV_EXTENT=204 - ChunkTree int64 `bin:"off=0, siz=8"` - ChunkObjectID btrfsprim.ObjID `bin:"off=8, siz=8"` - ChunkOffset btrfsvol.LogicalAddr `bin:"off=16, siz=8"` + ChunkTree btrfsprim.ObjID `bin:"off=0, siz=8"` // always CHUNK_TREE_OBJECTID + ChunkObjectID btrfsprim.ObjID `bin:"off=8, siz=8"` // which chunk within .ChunkTree owns this extent, always FIRST_CHUNK_TREE_OBJECTID + ChunkOffset btrfsvol.LogicalAddr `bin:"off=16, siz=8"` // offset of the CHUNK_ITEM that owns this extent, within the .ChunkObjectID Length btrfsvol.AddrDelta `bin:"off=24, siz=8"` ChunkTreeUUID btrfsprim.UUID `bin:"off=32, siz=16"` binstruct.End `bin:"off=48"` diff --git a/lib/btrfs/btrfsitem/item_extent.go b/lib/btrfs/btrfsitem/item_extent.go index 97dc105..66aae1d 100644 --- a/lib/btrfs/btrfsitem/item_extent.go +++ b/lib/btrfs/btrfsitem/item_extent.go @@ -12,6 +12,8 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" ) +// key.objectid = laddr of the extent +// key.offset = length of the extent type Extent struct { // EXTENT_ITEM=168 Head ExtentHeader Info TreeBlockInfo // only if .Head.Flags.Has(EXTENT_FLAG_TREE_BLOCK) diff --git a/lib/btrfs/btrfsitem/item_extentdataref.go b/lib/btrfs/btrfsitem/item_extentdataref.go index 74ce799..8c856e2 100644 --- a/lib/btrfs/btrfsitem/item_extentdataref.go +++ b/lib/btrfs/btrfsitem/item_extentdataref.go @@ -9,10 +9,12 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" ) +// key.objectid = laddr of the extent being referenced +// key.offset = crc32c([root,objectid,offset]) type ExtentDataRef struct { // EXTENT_DATA_REF=178 - Root btrfsprim.ObjID `bin:"off=0, siz=8"` - ObjectID btrfsprim.ObjID `bin:"off=8, siz=8"` - Offset int64 `bin:"off=16, siz=8"` - Count int32 `bin:"off=24, siz=4"` + Root btrfsprim.ObjID `bin:"off=0, siz=8"` // subvolume tree ID that references this extent + ObjectID btrfsprim.ObjID `bin:"off=8, siz=8"` // inode number that references this extent within the .Root subvolume + Offset int64 `bin:"off=16, siz=8"` // byte offset for the extent within the file + Count int32 `bin:"off=24, siz=4"` // reference count binstruct.End `bin:"off=28"` } diff --git a/lib/btrfs/btrfsitem/item_freespacebitmap.go b/lib/btrfs/btrfsitem/item_freespacebitmap.go index 7842785..ad46204 100644 --- a/lib/btrfs/btrfsitem/item_freespacebitmap.go +++ b/lib/btrfs/btrfsitem/item_freespacebitmap.go @@ -4,6 +4,8 @@ package btrfsitem +// key.objectid = object ID of the FreeSpaceInfo (logical_addr) +// key.offset = offset of the FreeSpaceInfo (size) type FreeSpaceBitmap []byte // FREE_SPACE_BITMAP=200 func (o *FreeSpaceBitmap) UnmarshalBinary(dat []byte) (int, error) { diff --git a/lib/btrfs/btrfsitem/item_freespaceinfo.go b/lib/btrfs/btrfsitem/item_freespaceinfo.go index 844f664..b38da20 100644 --- a/lib/btrfs/btrfsitem/item_freespaceinfo.go +++ b/lib/btrfs/btrfsitem/item_freespaceinfo.go @@ -6,10 +6,28 @@ package btrfsitem import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" + "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" ) +// key.objectid = object ID of the BlockGroup (logical_addr) +// key.offset = offset of the BlockGroup (size) type FreeSpaceInfo struct { // FREE_SPACE_INFO=198 - ExtentCount int32 `bin:"off=0, siz=4"` - Flags uint32 `bin:"off=4, siz=4"` + ExtentCount int32 `bin:"off=0, siz=4"` + Flags FreeSpaceFlags `bin:"off=4, siz=4"` binstruct.End `bin:"off=8"` } + +type FreeSpaceFlags uint32 + +const ( + FREE_SPACE_USING_BITMAPS = FreeSpaceFlags(1 << iota) +) + +var freeSpaceFlagNames = []string{ + "USING_BITMAPS", +} + +func (f FreeSpaceFlags) Has(req FreeSpaceFlags) bool { return f&req == req } +func (f FreeSpaceFlags) String() string { + return fmtutil.BitfieldString(f, freeSpaceFlagNames, fmtutil.HexNone) +} diff --git a/lib/btrfs/btrfsitem/item_inode.go b/lib/btrfs/btrfsitem/item_inode.go index 8023156..704b56a 100644 --- a/lib/btrfs/btrfsitem/item_inode.go +++ b/lib/btrfs/btrfsitem/item_inode.go @@ -10,12 +10,14 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" ) +// key.objectid = inode number +// key.offset = 0 type Inode struct { // INODE_ITEM=1 Generation btrfsprim.Generation `bin:"off=0x00, siz=0x08"` TransID int64 `bin:"off=0x08, siz=0x08"` Size int64 `bin:"off=0x10, siz=0x08"` // stat NumBytes int64 `bin:"off=0x18, siz=0x08"` // allocated bytes, may be larger than size (or smaller if there are holes?) - BlockGroup int64 `bin:"off=0x20, siz=0x08"` + BlockGroup btrfsprim.ObjID `bin:"off=0x20, siz=0x08"` // only used for freespace inodes NLink int32 `bin:"off=0x28, siz=0x04"` // stat UID int32 `bin:"off=0x2C, siz=0x04"` // stat GID int32 `bin:"off=0x30, siz=0x04"` // stat diff --git a/lib/btrfs/btrfsitem/item_root.go b/lib/btrfs/btrfsitem/item_root.go index 2e0b327..ffbbf4d 100644 --- a/lib/btrfs/btrfsitem/item_root.go +++ b/lib/btrfs/btrfsitem/item_root.go @@ -11,12 +11,16 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/fmtutil" ) +// key.objectid = tree ID +// key.offset = either +// - 0 if objectid is one of the BTRFS_*_TREE_OBJECTID defines or a non-snapshot volume; or +// - transaction_id of when this snapshot was created type Root struct { // ROOT_ITEM=132 - Inode Inode `bin:"off=0x000, siz=0xa0"` + Inode Inode `bin:"off=0x000, siz=0xa0"` // ??? Generation btrfsprim.Generation `bin:"off=0x0a0, siz=0x08"` - RootDirID btrfsprim.ObjID `bin:"off=0x0a8, siz=0x08"` - ByteNr btrfsvol.LogicalAddr `bin:"off=0x0b0, siz=0x08"` - ByteLimit int64 `bin:"off=0x0b8, siz=0x08"` + RootDirID btrfsprim.ObjID `bin:"off=0x0a8, siz=0x08"` // inode number of the root inode + ByteNr btrfsvol.LogicalAddr `bin:"off=0x0b0, siz=0x08"` // root node + ByteLimit int64 `bin:"off=0x0b8, siz=0x08"` // always 0 (unused) BytesUsed int64 `bin:"off=0x0c0, siz=0x08"` LastSnapshot int64 `bin:"off=0x0c8, siz=0x08"` Flags RootFlags `bin:"off=0x0d0, siz=0x08"` @@ -36,7 +40,7 @@ type Root struct { // ROOT_ITEM=132 OTime btrfsprim.Time `bin:"off=0x153, siz=0x0c"` STime btrfsprim.Time `bin:"off=0x15f, siz=0x0c"` RTime btrfsprim.Time `bin:"off=0x16b, siz=0x0c"` - GlobalTreeID btrfsprim.ObjID `bin:"off=0x177, siz=0x08"` + GlobalTreeID btrfsprim.ObjID `bin:"off=0x177, siz=0x08"` // ??? Reserved [7]int64 `bin:"off=0x17f, siz=0x38"` binstruct.End `bin:"off=0x1b7"` } diff --git a/lib/btrfs/btrfsitem/item_rootref.go b/lib/btrfs/btrfsitem/item_rootref.go index d1dfd3b..b33883d 100644 --- a/lib/btrfs/btrfsitem/item_rootref.go +++ b/lib/btrfs/btrfsitem/item_rootref.go @@ -12,9 +12,16 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" ) +// RootRefs link subvolumes parent→child for normal subvolumes and +// base→snapshot for snapshot subvolumes. BACKREF items go the other +// direction; child→parent and snapshot→base. +// +// ROOT_REF | ROOT_BACKREF +// key.objectid = ID of the parent subvolume | ID of the child subvolume +// key.offset = ID of the child subvolume | ID of the parent subvolume type RootRef struct { // ROOT_REF=156 ROOT_BACKREF=144 - DirID btrfsprim.ObjID `bin:"off=0x00, siz=0x8"` - Sequence int64 `bin:"off=0x08, siz=0x8"` + DirID btrfsprim.ObjID `bin:"off=0x00, siz=0x8"` // inode of the parent directory of the dir entry + Sequence int64 `bin:"off=0x08, siz=0x8"` // index of that dir entry within the parent NameLen uint16 `bin:"off=0x10, siz=0x2"` // [ignored-when-writing] binstruct.End `bin:"off=0x12"` Name []byte `bin:"-"` diff --git a/lib/btrfs/btrfsitem/item_shareddataref.go b/lib/btrfs/btrfsitem/item_shareddataref.go index 5ce4198..d7765af 100644 --- a/lib/btrfs/btrfsitem/item_shareddataref.go +++ b/lib/btrfs/btrfsitem/item_shareddataref.go @@ -8,7 +8,11 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" ) +// key.objectid = laddr of the extent being referenced +// +// key.offset = laddr of the leaf node containing the FileExtent +// (EXTENT_DATA_KEY) for this reference. type SharedDataRef struct { // SHARED_DATA_REF=184 - Count int32 `bin:"off=0, siz=4"` + Count int32 `bin:"off=0, siz=4"` // reference count binstruct.End `bin:"off=4"` } diff --git a/lib/btrfsprogs/btrfsutil/broken_btree.go b/lib/btrfsprogs/btrfsutil/broken_btree.go index 1fa84e7..0660a46 100644 --- a/lib/btrfsprogs/btrfsutil/broken_btree.go +++ b/lib/btrfsprogs/btrfsutil/broken_btree.go @@ -75,7 +75,7 @@ var _ btrfstree.TreeOperator = (*brokenTrees)(nil) // NewBrokenTrees wraps a *btrfs.FS to support looking up information // from broken trees. // -// Of the btrfs.FS.Tree{Verb}Trees methods: +// Of the btrfs.FS.Tree{Verb} methods: // // - TreeWalk works on broken trees // - TreeLookup relies on the tree being properly ordered (which a -- cgit v1.2.3-2-g168b From 7d77b89f355714da88bb1bbde5e343747bfb6a81 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 7 Dec 2022 23:04:58 -0700 Subject: rebuildmappings: Publicly expose the logicalsums RBTree --- .../btrfsinspect/rebuildmappings/logicalsums.go | 17 +++++++++++++---- .../btrfsinspect/rebuildmappings/rebuildmappings.go | 2 +- 2 files changed, 14 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go index 537a970..9b2da93 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go @@ -20,7 +20,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) -func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesResult) btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr] { +func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesResult) (addrspace *containers.RBTree[containers.NativeOrdered[btrfsvol.LogicalAddr], btrfsinspect.SysExtentCSum], sumSize int) { var records []btrfsinspect.SysExtentCSum for _, devResults := range scanResults { records = append(records, devResults.FoundExtentCSums...) @@ -38,9 +38,9 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice } }) if len(records) == 0 { - return btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]{} + return nil, 0 } - sumSize := records[0].Sums.ChecksumSize + sumSize = records[0].Sums.ChecksumSize // Now build them in to a coherent address space. // @@ -53,7 +53,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice // "AAAAAAA" shouldn't be present, and if we just discard "BBBBBBBB" // because it conflicts with "CCCCCCC", then we would erroneously // include "AAAAAAA". - addrspace := &containers.RBTree[containers.NativeOrdered[btrfsvol.LogicalAddr], btrfsinspect.SysExtentCSum]{ + addrspace = &containers.RBTree[containers.NativeOrdered[btrfsvol.LogicalAddr], btrfsinspect.SysExtentCSum]{ KeyFn: func(item btrfsinspect.SysExtentCSum) containers.NativeOrdered[btrfsvol.LogicalAddr] { return containers.NativeOrdered[btrfsvol.LogicalAddr]{Val: item.Sums.Addr} }, @@ -148,6 +148,15 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice } } + return addrspace, sumSize +} + +func ExtractAndFlattenLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevicesResult) btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr] { + addrspace, sumSize := ExtractLogicalSums(ctx, scanResults) + if addrspace == nil { + return btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr]{} + } + // Now flatten that RBTree in to a SumRunWithGaps. var flattened btrfssum.SumRunWithGaps[btrfsvol.LogicalAddr] var curAddr btrfsvol.LogicalAddr diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go index f1959b4..c391053 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/rebuildmappings.go @@ -145,7 +145,7 @@ func RebuildMappings(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect dlog.Infof(ctx, "5/6: Searching for %d block groups in checksum map (exact)...", len(bgs)) physicalSums := ExtractPhysicalSums(scanResults) - logicalSums := ExtractLogicalSums(ctx, scanResults) + logicalSums := ExtractAndFlattenLogicalSums(ctx, scanResults) if err := matchBlockGroupSums(ctx, fs, bgs, physicalSums, logicalSums); err != nil { return err } -- cgit v1.2.3-2-g168b From a71e1969a1b24500ce9885c4a3f1aeee40c421a8 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 29 Nov 2022 14:54:37 -0700 Subject: scandevices: Include a Key in SysExtentCSum --- lib/btrfsprogs/btrfsinspect/scandevices.go | 2 ++ 1 file changed, 2 insertions(+) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/scandevices.go b/lib/btrfsprogs/btrfsinspect/scandevices.go index 87dcedf..a382e17 100644 --- a/lib/btrfsprogs/btrfsinspect/scandevices.go +++ b/lib/btrfsprogs/btrfsinspect/scandevices.go @@ -73,6 +73,7 @@ type SysDevExtent struct { } type SysExtentCSum struct { + Key btrfsprim.Key Generation btrfsprim.Generation Sums btrfsitem.ExtentCSum } @@ -200,6 +201,7 @@ func ScanOneDevice(ctx context.Context, dev *btrfs.Device, sb btrfstree.Superblo //dlog.Tracef(ctx, "... dev[%q] node@%v: item %v: found csums", // dev.Name(), nodeRef.Addr, i) result.FoundExtentCSums = append(result.FoundExtentCSums, SysExtentCSum{ + Key: item.Key, Generation: nodeRef.Data.Head.Generation, Sums: sums, }) -- cgit v1.2.3-2-g168b From 580189ee3e43d5595a8700ee21b8900b0dd5389d Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 15 Nov 2022 20:57:04 -0700 Subject: Delete 'inspect visualize-nodes' --- lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go | 24 ++ lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go | 4 - .../btrfsinspect/rebuildnodes/uuidmap.go | 73 ----- .../btrfsinspect/rebuildnodes/visualizenodes.go | 300 --------------------- 4 files changed, 24 insertions(+), 377 deletions(-) delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go index fc71558..8ee53d2 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go @@ -10,9 +10,11 @@ import ( "io" "strings" + "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/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" "git.lukeshu.com/btrfs-progs-ng/lib/containers" @@ -152,3 +154,25 @@ func loopRender(out io.Writer, scanData scanResult, stack ...btrfsvol.LogicalAdd fmt.Fprintln(out, " "+line) } } + +func checkNodeExpectations(kp kpData, toNode nodeData) error { + var errs derror.MultiError + if toNode.Level != kp.ToLevel { + errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v", + kp.ToLevel, toNode.Level)) + } + if toNode.Generation != kp.ToGeneration { + errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v", + kp.ToGeneration, toNode.Generation)) + } + if toNode.NumItems == 0 { + errs = append(errs, fmt.Errorf("node.num_items=0")) + } else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey { + errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v", + kp.ToKey, toNode.MinItem)) + } + if len(errs) > 0 { + return errs + } + return nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go index 7e0eab1..f1033e6 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go @@ -10,10 +10,6 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" ) -func ptrTo[T any](x T) *T { - return &x -} - func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) error { if other, conflict := m[k]; conflict && other != v { return fmt.Errorf("conflict: %s %v can't have both %v and %v", name, k, other, v) diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go index 7be903a..4d93916 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go @@ -5,12 +5,8 @@ package rebuildnodes import ( - "fmt" - "strings" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) type uuidMap struct { @@ -57,72 +53,3 @@ func (m uuidMap) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { } return parentObjID, true } - -type fullAncestorLister struct { - uuidMap uuidMap - treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID] - - memos map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID] -} - -func newFullAncestorLister(uuidMap uuidMap, treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) fullAncestorLister { - return fullAncestorLister{ - uuidMap: uuidMap, - treeAncestors: treeAncestors, - memos: make(map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]), - } -} - -type loopError []btrfsprim.ObjID - -func (le loopError) Error() string { - var buf strings.Builder - buf.WriteString("loop: ") - for i, treeID := range le { - if i > 0 { - buf.WriteString("->") - } - fmt.Fprintf(&buf, "%d", treeID) - } - return buf.String() -} - -func (fa fullAncestorLister) GetFullAncestors(child btrfsprim.ObjID) containers.Set[btrfsprim.ObjID] { - if memoized, ok := fa.memos[child]; ok { - if memoized == nil { - panic(loopError{child}) - } - return memoized - } - fa.memos[child] = nil - defer func() { - if r := recover(); r != nil { - if le, ok := r.(loopError); ok { - r = append(loopError{child}, le...) - } - panic(r) - } - }() - - ret := make(containers.Set[btrfsprim.ObjID]) - defer func() { - fa.memos[child] = ret - }() - - // Try to use '.uuidMap' instead of '.treeAncestors' if possible. - knownAncestors := make(containers.Set[btrfsprim.ObjID]) - if parent, ok := fa.uuidMap.ParentTree(child); ok { - if parent == 0 { - return ret - } - knownAncestors.Insert(parent) - } else { - knownAncestors.InsertFrom(fa.treeAncestors[child]) - } - - for _, ancestor := range maps.SortedKeys(knownAncestors) { - ret.Insert(ancestor) - ret.InsertFrom(fa.GetFullAncestors(ancestor)) - } - return ret -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go deleted file mode 100644 index fc9d19b..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go +++ /dev/null @@ -1,300 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "archive/zip" - "context" - "fmt" - "html" - "io" - "strings" - - "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/btrfsprogs/btrfsinspect" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" -) - -func getCliques(scanData scanResult) map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID] { - cliques := make(map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID]) - - // UUID map - lister := newFullAncestorLister(scanData.uuidMap, map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]{}) - for _, treeID := range maps.SortedKeys(scanData.uuidMap.SeenTrees) { - clique := ptrTo(make(containers.Set[btrfsprim.ObjID])) - clique.Insert(treeID) - clique.InsertFrom(lister.GetFullAncestors(treeID)) - for _, id := range maps.SortedKeys(*clique) { - if existingClique, ok := cliques[id]; ok { - clique.InsertFrom(*existingClique) - } - cliques[id] = clique - } - } - - // node graph - for _, laddr := range maps.SortedKeys(scanData.nodeGraph.Nodes) { - clique := ptrTo(make(containers.Set[btrfsprim.ObjID])) - clique.Insert(scanData.nodeGraph.Nodes[laddr].Owner) - for _, edge := range scanData.nodeGraph.EdgesTo[laddr] { - clique.Insert(edge.FromTree) - } - for _, id := range maps.SortedKeys(*clique) { - if existingClique, ok := cliques[id]; ok { - clique.InsertFrom(*existingClique) - } - cliques[id] = clique - } - } - return cliques -} - -func getCliqueID(cliques map[btrfsprim.ObjID]*containers.Set[btrfsprim.ObjID], treeID btrfsprim.ObjID) btrfsprim.ObjID { - clique, ok := cliques[treeID] - if !ok { - panic(fmt.Errorf("tree ID %v was not in .SeenTrees", treeID)) - } - return maps.SortedKeys(*clique)[0] -} - -func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) error { - scanData, err := ScanDevices(ctx, fs, nodeScanResults) - if err != nil { - return err - } - - //////////////////////////////////////////////////////////////////////////////////////////// - - dlog.Info(ctx, "Building cliques...") - cliques := getCliques(*scanData) - cliqueIDs := make(containers.Set[btrfsprim.ObjID]) - for treeID := range cliques { - cliqueIDs.Insert(getCliqueID(cliques, treeID)) - } - dlog.Infof(ctx, "... built %d cliques of %d trees", len(cliqueIDs), len(cliques)) - - //////////////////////////////////////////////////////////////////////////////////////////// - - dlog.Info(ctx, "Building graphviz graphs...") - - type graph struct { - nodes map[btrfsprim.ObjID]containers.Set[string] // keyed by treeID - badNodes containers.Set[string] - edges containers.Set[string] - } - graphs := make(map[btrfsprim.ObjID]graph, len(cliques)) // keyed by cliqueID - for cliqueID := range cliqueIDs { - graphs[cliqueID] = graph{ - nodes: make(map[btrfsprim.ObjID]containers.Set[string]), - badNodes: make(containers.Set[string]), - edges: make(containers.Set[string]), - } - } - - dlog.Infof(ctx, "... processing %d nodes...", len(scanData.Nodes)) - - for _, laddr := range maps.SortedKeys(scanData.Nodes) { - nodeData := scanData.Nodes[laddr] - cliqueID := getCliqueID(cliques, nodeData.Owner) - graph, ok := graphs[cliqueID] - if !ok { - panic(cliqueID) - } - if graph.nodes[nodeData.Owner] == nil { - graph.nodes[nodeData.Owner] = make(containers.Set[string]) - } - - var buf strings.Builder - fmt.Fprintf(&buf, `n%d [shape=record label="{laddr=%v\lgen=%v\llvl=%v\litems=%v\l|{`, - laddr, - laddr, - nodeData.Generation, - nodeData.Level, - nodeData.NumItems) - if nodeData.Level == 0 { - buf.WriteString("leaf") - } else { - for i := uint32(0); i < nodeData.NumItems; i++ { - if i == 0 { - fmt.Fprintf(&buf, "%[1]d", i) - } else { - fmt.Fprintf(&buf, "|%[1]d", i) - } - } - } - buf.WriteString(`}}"]`) - graph.nodes[nodeData.Owner].Insert(buf.String()) - - if len(scanData.EdgesTo[laddr]) == 0 { - graph.edges.Insert(fmt.Sprintf("orphanRoot -> n%d", laddr)) - } - - graphs[cliqueID] = graph - } - - dlog.Infof(ctx, "... processing %d bad nodes...", len(scanData.BadNodes)) - - for _, laddr := range maps.SortedKeys(scanData.BadNodes) { - cliqueIDs := make(containers.Set[btrfsprim.ObjID]) - for _, edge := range scanData.EdgesTo[laddr] { - cliqueIDs.Insert(getCliqueID(cliques, edge.FromTree)) - } - if len(cliqueIDs) != 1 { - dlog.Errorf(ctx, "couldn't assign bad node@%v to a clique: %v", laddr, maps.SortedKeys(cliqueIDs)) - continue - } - - cliqueID := cliqueIDs.TakeOne() - graph, ok := graphs[cliqueID] - if !ok { - panic(cliqueID) - } - graph.badNodes.Insert(fmt.Sprintf(`n%d [shape=star color=red label="%v\l\lerr=%s"]`, - laddr, laddr, gvEscape(scanData.BadNodes[laddr].Error()+"\n"))) - graphs[cliqueID] = graph - } - - numEdges := 0 - for _, kps := range scanData.EdgesFrom { - numEdges += (len(kps)) - } - dlog.Infof(ctx, "... processing %d keypointers...", numEdges) - - for _, laddr := range maps.SortedKeys(scanData.EdgesFrom) { - for _, kp := range scanData.EdgesFrom[laddr] { - cliqueID := getCliqueID(cliques, kp.FromTree) - graph, ok := graphs[cliqueID] - if !ok { - panic(cliqueID) - } - - var buf strings.Builder - if kp.FromNode == 0 { - if graph.nodes[kp.FromTree] == nil { - graph.nodes[kp.FromTree] = make(containers.Set[string]) - } - graph.nodes[kp.FromTree].Insert(fmt.Sprintf(`t%d [label="root of %s"]`, kp.FromTree, gvEscape(kp.FromTree.String()))) - fmt.Fprintf(&buf, "t%d", kp.FromTree) - } else { - fmt.Fprintf(&buf, "n%d:p%d", kp.FromNode, kp.FromItem) - } - fmt.Fprintf(&buf, ` -> n%d`, kp.ToNode) - - var err error - toNode, ok := scanData.Nodes[kp.ToNode] - if !ok { - err = scanData.BadNodes[kp.ToNode] - } else { - err = checkNodeExpectations(*kp, toNode) - } - if err != nil { - fmt.Fprintf(&buf, ` [label="key=(%d,%v,%d) gen=%v\l\lerr=%s" color=red]`, - kp.ToKey.ObjectID, - kp.ToKey.ItemType, - kp.ToKey.Offset, - kp.ToGeneration, - gvEscape(err.Error()+"\n")) - } - - graph.edges.Insert(buf.String()) - graphs[cliqueID] = graph - } - } - - //////////////////////////////////////////////////////////////////////////////////////////// - - dlog.Info(ctx, "Writing graphviz output...") - - zw := zip.NewWriter(out) - for _, cliqueID := range maps.SortedKeys(graphs) { - if err := func() (err error) { - graph := graphs[cliqueID] - - buf, err := zw.Create(fmt.Sprintf("%d.dot", cliqueID)) - if err != nil { - return err - } - if _, err := fmt.Fprintf(buf, "strict digraph clique%d {\n", cliqueID); err != nil { - return err - } - if _, err := fmt.Fprintf(buf, "rankdir=LR;\n nodesep=0.1;\n ranksep=25;\n splines=line;\n"); err != nil { - return err - } - for _, treeID := range maps.SortedKeys(graph.nodes) { - nodes := graph.nodes[treeID] - - if _, err := fmt.Fprintf(buf, " subgraph cluster_tree%d {\n", treeID); err != nil { - return err - } - for _, node := range maps.SortedKeys(nodes) { - if _, err := fmt.Fprintf(buf, " %s;\n", node); err != nil { - return err - } - } - if _, err := fmt.Fprintln(buf, " }"); err != nil { - return err - } - } - for _, node := range maps.SortedKeys(graph.badNodes) { - if _, err := fmt.Fprintf(buf, " %s;\n", node); err != nil { - return err - } - } - for _, edge := range maps.SortedKeys(graph.edges) { - if _, err := fmt.Fprintf(buf, " %s;\n", edge); err != nil { - return err - } - } - - if _, err := fmt.Fprintln(buf, "}"); err != nil { - return err - } - return nil - }(); err != nil { - return err - } - } - if err := zw.Close(); err != nil { - return err - } - - dlog.Info(ctx, "... done writing") - - return nil -} - -func gvEscape(str string) string { - str = html.EscapeString(str) - str = strings.ReplaceAll(str, "\n", `\l`) - str = strings.ReplaceAll(str, `\n`, `\l`) - return str -} - -func checkNodeExpectations(kp kpData, toNode nodeData) error { - var errs derror.MultiError - if toNode.Level != kp.ToLevel { - errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v", - kp.ToLevel, toNode.Level)) - } - if toNode.Generation != kp.ToGeneration { - errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v", - kp.ToGeneration, toNode.Generation)) - } - if toNode.NumItems == 0 { - errs = append(errs, fmt.Errorf("node.num_items=0")) - } else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey { - errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v", - kp.ToKey, toNode.MinItem)) - } - if len(errs) > 0 { - return errs - } - return nil -} -- cgit v1.2.3-2-g168b From 6c03becc595c9938644e767c852a2627d4a265d3 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Mon, 17 Oct 2022 00:31:38 -0600 Subject: rebuildnodes: wip: New rebuild-nodes implementation --- .../btrfsinspect/rebuildnodes/bak_rebuildnodes.go | 102 ------- .../btrfsinspect/rebuildnodes/bak_rebuilttrees.go | 89 ------ .../btrfsinspect/rebuildnodes/bak_s3_reinit.go | 139 --------- .../rebuildnodes/bak_s3_reinit_test.go | 82 ------ .../btrfsinspect/rebuildnodes/bak_s4_reattach.go | 161 ----------- .../btrfsinspect/rebuildnodes/orphans.go | 102 +++++++ .../btrfsinspect/rebuildnodes/rebuild.go | 107 +++++++ .../btrfsinspect/rebuildnodes/rebuild_graph.go | 322 +++++++++++++++++++++ .../btrfsinspect/rebuildnodes/treeancestors.go | 76 ----- lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go | 30 +- lib/btrfsprogs/btrfsutil/broken_btree.go | 6 + 11 files changed, 547 insertions(+), 669 deletions(-) delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuildnodes.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuilttrees.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit_test.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s4_reattach.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuildnodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuildnodes.go deleted file mode 100644 index 1a9f487..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuildnodes.go +++ /dev/null @@ -1,102 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -/* -import ( - "context" - "errors" - - "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/btrfsprogs/btrfsinspect" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" - "git.lukeshu.com/btrfs-progs-ng/lib/diskio" -) - -func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { - uuidMap, err := buildUUIDMap(ctx, fs, nodeScanResults) - if err != nil { - return nil, err - } - - nfs := &RebuiltTrees{ - inner: fs, - uuidMap: uuidMap, - } - - orphanedNodes, badNodes, treeAncestors, err := classifyNodes(ctx, nfs, nodeScanResults) - if err != nil { - return nil, err - } - - uuidMap.considerAncestors(ctx, treeAncestors) - - rebuiltNodes, err := reInitBrokenNodes(ctx, nfs, badNodes) - if err != nil { - return nil, err - } - - if err := reAttachNodes(ctx, nfs, orphanedNodes, rebuiltNodes); err != nil { - return nil, err - } - - return rebuiltNodes, nil -} - -func spanOfTreePath(fs _FS, path btrfstree.TreePath) (btrfsprim.Key, btrfsprim.Key) { - // tree root error - if len(path) == 0 { - return btrfsprim.Key{}, maxKey - } - - // item error - if path.Node(-1).ToNodeAddr == 0 { - // If we got an item error, then the node is readable - node, _ := fs.ReadNode(path.Parent()) - key := node.Data.BodyLeaf[path.Node(-1).FromItemIdx].Key - return key, key - } - - // node error - // - // assume that path.Node(-1).ToNodeAddr is not readable, but that path.Node(-2).ToNodeAddr is. - if len(path) == 1 { - return btrfsprim.Key{}, maxKey - } - parentNode, _ := fs.ReadNode(path.Parent()) - low := parentNode.Data.BodyInternal[path.Node(-1).FromItemIdx].Key - var high btrfsprim.Key - if path.Node(-1).FromItemIdx+1 < len(parentNode.Data.BodyInternal) { - high = keyMm(parentNode.Data.BodyInternal[path.Node(-1).FromItemIdx+1].Key) - } else { - parentPath := path.Parent().DeepCopy() - _, high = spanOfTreePath(fs, parentPath) - } - return low, high -} - -func getChunkTreeUUID(ctx context.Context, fs _FS) (btrfsprim.UUID, bool) { - ctx, cancel := context.WithCancel(ctx) - var ret btrfsprim.UUID - var retOK bool - btrfsutil.WalkAllTrees(ctx, fs, btrfsutil.WalkAllTreesHandler{ - TreeWalkHandler: btrfstree.TreeWalkHandler{ - Node: func(path btrfstree.TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { - ret = node.Data.Head.ChunkTreeUUID - retOK = true - cancel() - return nil - }, - }, - Err: func(err *btrfsutil.WalkError) { - // do nothing - }, - }) - return ret, retOK -} -*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuilttrees.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuilttrees.go deleted file mode 100644 index 7e1a7e9..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_rebuilttrees.go +++ /dev/null @@ -1,89 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -/* -import ( - "context" - "fmt" - - "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/diskio" -) - -type RebuiltTrees struct { - inner *btrfs.FS - uuidMap uuidMap - nodes map[btrfsvol.LogicalAddr]*RebuiltNode -} - -type _FS interface { - diskio.File[btrfsvol.LogicalAddr] - btrfstree.NodeFile - btrfstree.NodeSource - btrfstree.TreeOperator -} - -// diskio.File - -func (fs *RebuiltTrees) Name() string { return fs.inner.Name() } -func (fs *RebuiltTrees) Size() btrfsvol.LogicalAddr { return fs.inner.Size() } -func (fs *RebuiltTrees) Close() error { return fs.inner.Close() } -func (fs *RebuiltTrees) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { - sb, err := fs.Superblock() - if err != nil { - return 0, err - } - if rebuilt, ok := fs.nodes[off]; ok && len(p) == int(sb.NodeSize) { - rebuilt.Node.Head.Checksum, err = rebuilt.Node.CalculateChecksum() - if err != nil { - panic(fmt.Errorf("should not happen: %w", err)) - } - bs, err := rebuilt.Node.MarshalBinary() - if err != nil { - panic(fmt.Errorf("should not happen: %w", err)) - } - if len(p) != len(bs) { - panic(fmt.Errorf("should not happen: sb.NodeSize=%v but node marshaled to %v", sb.NodeSize, len(bs))) - } - return copy(p, bs), nil - } - return fs.inner.ReadAt(p, off) -} -func (fs *RebuiltTrees) WriteAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { - return fs.inner.WriteAt(p, off) -} - -// btrfstree.NodeFile - -func (fs *RebuiltTrees) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { - return fs.uuidMap.ParentTree(tree) -} - -// btrfstree.NodeSource - -func (fs *RebuiltTrees) Superblock() (*btrfstree.Superblock, error) { return fs.inner.Superblock() } -func (fs *RebuiltTrees) ReadNode(path btrfstree.TreePath) (*diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node], error) { - return btrfstree.FSReadNode(fs, path) -} - -// btrfstree.TreeOperator - -func (fs *RebuiltTrees) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*btrfstree.TreeError), cbs btrfstree.TreeWalkHandler) { - btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeWalk(ctx, treeID, errHandle, cbs) -} -func (fs *RebuiltTrees) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeLookup(treeID, key) -} -func (fs *RebuiltTrees) TreeSearch(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) (btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearch(treeID, fn) -} -func (fs *RebuiltTrees) TreeSearchAll(treeID btrfsprim.ObjID, fn func(key btrfsprim.Key, size uint32) int) ([]btrfstree.Item, error) { - return btrfstree.TreeOperatorImpl{NodeSource: fs}.TreeSearchAll(treeID, fn) -} -*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit.go deleted file mode 100644 index 5983e2f..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit.go +++ /dev/null @@ -1,139 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -/* -import ( - "fmt" - "reflect" - - "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/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/slices" -) - -type RebuiltNode struct { - Errs containers.Set[string] - MinKey, MaxKey btrfsprim.Key - InTrees containers.Set[btrfsprim.ObjID] - btrfstree.Node -} - -func (a RebuiltNode) Compat(b RebuiltNode) bool { - a.Node.Head.Generation = b.Node.Head.Generation - return reflect.DeepEqual(a.Node, b.Node) -} - -func (a RebuiltNode) Merge(b RebuiltNode) (RebuiltNode, error) { - if !a.Compat(b) { - switch { - case a.Node.Head.Generation > b.Node.Head.Generation: - return a, nil - case a.Node.Head.Generation < b.Node.Head.Generation: - return b, nil - default: - return a, fmt.Errorf("mismatch: %v != %v", a, b) - } - } - - // take the broadest region - if a.MinKey.Cmp(b.MinKey) > 0 { // if a.MinKey > b.MinKey { - a.MinKey = b.MinKey // take the min of the two - } - if a.MaxKey.Cmp(b.MaxKey) < 0 { // if a.MaxKey < b.MaxKey { - a.MaxKey = b.MaxKey // take the min of the two - } - - // take the highest generation - a.Node.Head.Generation = slices.Max(a.Node.Head.Generation, b.Node.Head.Generation) - - // take the union - a.InTrees.InsertFrom(b.InTrees) - a.Errs.InsertFrom(b.Errs) - - return a, nil -} - -func reInitBrokenNodes(ctx context.Context, fs _FS, badNodes []badNode) (map[btrfsvol.LogicalAddr]*RebuiltNode, error) { - dlog.Info(ctx, "Re-initializing bad nodes...") - - sb, err := fs.Superblock() - if err != nil { - return nil, err - } - chunkTreeUUID, ok := getChunkTreeUUID(ctx, fs) - if !ok { - return nil, fmt.Errorf("could not look up chunk tree UUID") - } - - sort.Slice(badNodes, func(i, j int) bool { - iGen := badNodes[i].Path.Node(-1).ToNodeGeneration - jGen := badNodes[j].Path.Node(-1).ToNodeGeneration - switch { - case iGen < jGen: - return true - case iGen > jGen: - return false - default: - iAddr := badNodes[i].Path.Node(-1).ToNodeAddr - jAddr := badNodes[j].Path.Node(-1).ToNodeAddr - return iAddr < jAddr - } - }) - - lastPct := -1 - progress := func(done int) { - pct := int(100 * float64(done) / float64(len(badNodes))) - if pct != lastPct || done == len(badNodes) { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, len(badNodes)) - lastPct = pct - } - } - - rebuiltNodes := make(map[btrfsvol.LogicalAddr]*RebuiltNode) - for i, badNode := range badNodes { - progress(i) - path := badNode.Path - - min, max := spanOfTreePath(fs, path) - node := RebuiltNode{ - Errs: containers.NewSet[string]( - badNode.Err, - ), - MinKey: min, - MaxKey: max, - InTrees: containers.NewSet[btrfsprim.ObjID]( - path.Node(-1).FromTree, - ), - Node: btrfstree.Node{ - Size: sb.NodeSize, - ChecksumType: sb.ChecksumType, - Head: btrfstree.NodeHeader{ - MetadataUUID: sb.EffectiveMetadataUUID(), - Addr: path.Node(-1).ToNodeAddr, - ChunkTreeUUID: chunkTreeUUID, - //Owner: TBD, // see RebuiltNode.InTrees - Generation: path.Node(-1).ToNodeGeneration, - Level: path.Node(-1).ToNodeLevel, - }, - }, - } - if other, ok := rebuiltNodes[path.Node(-1).ToNodeAddr]; ok { - *other, err = other.Merge(node) - if err != nil { - dlog.Errorf(ctx, "... %v", err) - } - } else { - rebuiltNodes[path.Node(-1).ToNodeAddr] = &node - } - } - progress(len(badNodes)) - - dlog.Infof(ctx, "... initialized %d nodes", len(rebuiltNodes)) - return rebuiltNodes, nil -} -*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit_test.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit_test.go deleted file mode 100644 index 865cd7e..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s3_reinit_test.go +++ /dev/null @@ -1,82 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes_test - -/* -import ( - "strings" - "testing" - - "git.lukeshu.com/go/lowmemjson" - "github.com/stretchr/testify/assert" - - "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/btrfsprogs/btrfsinspect/rebuildnodes" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" -) - -func TestEncodeRebuiltNodes(t *testing.T) { - dat := map[btrfsvol.LogicalAddr]*rebuildnodes.RebuiltNode{ - 100007133184: { - Errs: containers.NewSet[string]( - "btrfs.ReadNode: node@0x0000001748e3c000: expected generation\u003c=6596014 but claims to be generation=6596025", - ), - MinKey: btrfsprim.Key{}, - MaxKey: btrfsprim.Key{}, - InTrees: containers.NewSet[btrfsprim.ObjID]( - 257, - ), - Node: btrfstree.Node{}, - }, - } - var buf strings.Builder - assert.NoError(t, lowmemjson.Encode(&lowmemjson.ReEncoder{ - Out: &buf, - - Indent: "\t", - ForceTrailingNewlines: true, - }, dat)) - assert.Equal(t, `{ - "100007133184": { - "Errs": [ - "btrfs.ReadNode: node@0x0000001748e3c000: expected generation\u003c=6596014 but claims to be generation=6596025" - ], - "MinKey": { - "ObjectID": 0, - "ItemType": 0, - "Offset": 0 - }, - "MaxKey": { - "ObjectID": 0, - "ItemType": 0, - "Offset": 0 - }, - "InTrees": [ - 257 - ], - "Size": 0, - "ChecksumType": 0, - "Head": { - "Checksum": "0000000000000000000000000000000000000000000000000000000000000000", - "MetadataUUID": "00000000-0000-0000-0000-000000000000", - "Addr": 0, - "Flags": 0, - "BackrefRev": 0, - "ChunkTreeUUID": "00000000-0000-0000-0000-000000000000", - "Generation": 0, - "Owner": 0, - "NumItems": 0, - "Level": 0 - }, - "BodyInternal": null, - "BodyLeaf": null, - "Padding": null - } -} -`, buf.String()) -} -*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s4_reattach.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s4_reattach.go deleted file mode 100644 index a78d964..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/bak_s4_reattach.go +++ /dev/null @@ -1,161 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -/* -import ( - "context" - "sort" - - "github.com/datawire/dlib/dlog" - - "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/maps" -) - -func (a RebuiltNode) ContainsWholeRegion(min, max btrfsprim.Key) int { - switch { - case min.Cmp(a.MinKey) < 0: - // 'a' is too far right - return -1 - case max.Cmp(a.MaxKey) > 0: - // 'a' is too far left - return 1 - default: - // just right - return 0 - } -} - -func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes containers.Set[btrfsvol.LogicalAddr], rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error { - dlog.Info(ctx, "Attaching orphaned nodes to rebuilt nodes...") - - sb, err := fs.Superblock() - if err != nil { - return err - } - - // Index 'rebuiltNodes' for fast lookups. - dlog.Info(ctx, "... indexing rebuilt nodes...") - var byLevel [][]*RebuiltNode - for _, node := range rebuiltNodes { - for int(node.Head.Level) >= len(byLevel) { - byLevel = append(byLevel, []*RebuiltNode(nil)) - } - byLevel[node.Head.Level] = append(byLevel[node.Head.Level], node) - } - for _, slice := range byLevel { - sort.Slice(slice, func(i, j int) bool { - return slice[i].MinKey.Cmp(slice[j].MinKey) < 0 - }) - } - dlog.Info(ctx, "... done indexing") - - // Attach orphanedNodes to the gaps. - dlog.Info(ctx, "... attaching nodes...") - lastPct := -1 - progress := func(done int) { - pct := int(100 * float64(done) / float64(len(orphanedNodes))) - if pct != lastPct || done == len(orphanedNodes) { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, len(orphanedNodes)) - lastPct = pct - } - } - numAttached := 0 - for i, foundLAddr := range maps.SortedKeys(orphanedNodes) { - progress(i) - foundRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, foundLAddr, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: foundLAddr}, - }) - if foundRef == nil { - return err - } - foundMinKey, ok := foundRef.Data.MinItem() - if !ok { - continue - } - foundMaxKey, ok := foundRef.Data.MaxItem() - if !ok { - continue - } - - // `trees` is the set of trees that the node may be - // placed in; '0' is a wildcard that means "any tree". - // We still keep track of the others, in order to try - // to avoid using the wildcard. - trees := make(containers.Set[btrfsprim.ObjID]) - tree := foundRef.Data.Head.Owner - for { - trees.Insert(tree) - var ok bool - tree, ok = fs.ParentTree(tree) - if !ok { - // error; accept anything - trees.Insert(0) - break - } - if tree == 0 { - // end of the line - break - } - } - attached := make(containers.Set[btrfsprim.ObjID]) - for level := int(foundRef.Data.Head.Level) + 1; level < len(byLevel) && len(attached) == 0; level++ { - for _, parent := range byLevel[level] { - if parent.ContainsWholeRegion(foundMinKey, foundMaxKey) != 0 { - continue - } - if parent.Node.Head.Generation < foundRef.Data.Head.Generation { - continue - } - if !trees.HasAny(parent.InTrees) { - continue - } - parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{ - Key: foundMinKey, - BlockPtr: foundLAddr, - Generation: foundRef.Data.Head.Generation, - }) - attached.InsertFrom(parent.InTrees) - } - } - if _, wildcard := trees[0]; wildcard && len(attached) == 0 { - for level := int(foundRef.Data.Head.Level) + 1; level < len(byLevel) && len(attached) == 0; level++ { - for _, parent := range byLevel[level] { - if parent.ContainsWholeRegion(foundMinKey, foundMaxKey) != 0 { - continue - } - if parent.Node.Head.Generation < foundRef.Data.Head.Generation { - continue - } - parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{ - Key: foundMinKey, - BlockPtr: foundLAddr, - Generation: foundRef.Data.Head.Generation, - }) - attached.InsertFrom(parent.InTrees) - } - } - } - - if len(attached) > 0 { - numAttached++ - } else { - dlog.Errorf(ctx, "could not find a broken node to attach node to reattach node@%v to", - foundRef.Addr) - } - } - progress(len(orphanedNodes)) - dlog.Info(ctx, "... ... done attaching") - - dlog.Infof(ctx, "... re-attached %d nodes (%v%% success rate)", - numAttached, int(100*float64(numAttached)/float64(len(orphanedNodes)))) - return nil -} -*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go new file mode 100644 index 0000000..3d375f0 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -0,0 +1,102 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "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" +) + +func listRoots(graph nodeGraph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { + kps := graph.EdgesTo[leaf] + if len(kps) == 0 { + return containers.NewSet(leaf) + } + ret := make(containers.Set[btrfsvol.LogicalAddr]) + for _, kp := range kps { + ret.InsertFrom(listRoots(graph, kp.FromNode)) + } + return ret +} + +func walk(graph nodeGraph, root btrfsvol.LogicalAddr, fn func(btrfsvol.LogicalAddr) bool) { + if _, ok := graph.Nodes[root]; !ok { + return + } + if !fn(root) { + return + } + for _, kp := range graph.EdgesFrom[root] { + walk(graph, kp.ToNode, fn) + } +} + +type keyAndTree struct { + btrfsprim.Key + TreeID btrfsprim.ObjID +} + +func (a keyAndTree) Cmp(b keyAndTree) int { + if d := a.Key.Cmp(b.Key); d != 0 { + return d + } + return containers.NativeCmp(a.TreeID, b.TreeID) +} + +func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph nodeGraph) ( + orphans containers.Set[btrfsvol.LogicalAddr], + leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], + key2leaf *containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr], + err error, +) { + orphans = make(containers.Set[btrfsvol.LogicalAddr]) + for node := range graph.Nodes { + if len(graph.EdgesTo[node]) == 0 { + orphans.Insert(node) + } + } + + leaf2orphans = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) + visited := make(containers.Set[btrfsvol.LogicalAddr]) + for orphan := range orphans { + walk(graph, orphan, func(node btrfsvol.LogicalAddr) bool { + if visited.Has(node) { + return false + } + visited.Insert(node) + if graph.Nodes[node].Level == 0 { + if roots := listRoots(graph, node); !roots.Has(0) { + leaf2orphans[node] = roots + } + } + return true + }) + } + + key2leaf = new(containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr]) + for laddr := range leaf2orphans { + nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, + Level: containers.Optional[uint8]{OK: true, Val: 0}, + }) + if err != nil { + return nil, nil, nil, err + } + + for _, item := range nodeRef.Data.BodyLeaf { + k := keyAndTree{ + Key: item.Key, + TreeID: nodeRef.Data.Head.Owner, + } + if cur, ok := key2leaf.Load(k); !ok || graph.Nodes[cur].Generation < nodeRef.Data.Head.Generation { + key2leaf.Store(k, laddr) + } + } + } + return orphans, leaf2orphans, key2leaf, nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go new file mode 100644 index 0000000..536b61d --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -0,0 +1,107 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "context" + + "github.com/datawire/dlib/dlog" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "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/btrfsprogs/btrfsinspect" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" +) + +type Rebuilder struct { + inner interface { + btrfstree.TreeOperator + Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error) + } + + orphans containers.Set[btrfsvol.LogicalAddr] + leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] + key2leaf containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr] + + augments map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] +} + +func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], error) { + scanData, err := ScanDevices(ctx, fs, nodeScanResults) // ScanDevices does its own logging + if err != nil { + return nil, err + } + + dlog.Info(ctx, "Reading superblock...") + sb, err := fs.Superblock() + if err != nil { + return nil, err + } + + dlog.Info(ctx, "Indexing orphans...") + orphans, leaf2orphans, key2leaf, err := indexOrphans(fs, *sb, scanData.nodeGraph) + if err != nil { + return nil, err + } + + dlog.Info(ctx, "Rebuilding node tree...") + o := &Rebuilder{ + inner: btrfsutil.NewBrokenTrees(ctx, fs), + + orphans: orphans, + leaf2orphans: leaf2orphans, + key2leaf: *key2leaf, + + augments: make(map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr]), + } + if err := o.rebuild(ctx); err != nil { + return nil, err + } + + return o.augments, nil +} + +func (o *Rebuilder) rebuild(ctx context.Context) error { + // TODO + //btrfsutil.WalkAllTrees(ctx, o.inner) + handleItem(o, ctx, 0, btrfstree.Item{}) + return nil +} + +// err implements rebuildCallbacks. +func (o *Rebuilder) err(ctx context.Context, e error) { + // TODO +} + +// want implements rebuildCallbacks. +func (o *Rebuilder) want(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) { + // TODO +} + +// wantOff implements rebuildCallbacks. +func (o *Rebuilder) wantOff(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) { + // TODO +} + +// wantFunc implements rebuildCallbacks. +func (o *Rebuilder) wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(btrfsitem.Item) bool) { + // TODO +} + +// func implements rebuildCallbacks. +// +// interval is [beg, end) +func (o *Rebuilder) wantCSum(ctx context.Context, beg, end btrfsvol.LogicalAddr) { + // TODO +} + +// wantFileExt implements rebuildCallbacks. +func (o *Rebuilder) wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) { + // TODO +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go new file mode 100644 index 0000000..8247651 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go @@ -0,0 +1,322 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package rebuildnodes + +import ( + "context" + "fmt" + "reflect" + + "github.com/datawire/dlib/dlog" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" +) + +type rebuildCallbacks interface { + err(ctx context.Context, e error) + want(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) + wantOff(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) + wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(btrfsitem.Item) bool) + wantCSum(ctx context.Context, beg, end btrfsvol.LogicalAddr) // interval is [beg, end) + wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) +} + +func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, item btrfstree.Item) { + ctx = dlog.WithField(ctx, "tree", treeID) + ctx = dlog.WithField(ctx, "key", item.Key) + + // Notionally, just express the relationships shown in + // https://btrfs.wiki.kernel.org/index.php/File:References.png (from the page + // https://btrfs.wiki.kernel.org/index.php/Data_Structures ) + switch body := item.Body.(type) { + case btrfsitem.BlockGroup: + o.want(dlog.WithField(ctx, "wants", "Chunk"), + btrfsprim.CHUNK_TREE_OBJECTID, + body.ChunkObjectID, + btrfsitem.CHUNK_ITEM_KEY) + o.wantOff(dlog.WithField(ctx, "wants", "FreeSpaceInfo"), + btrfsprim.FREE_SPACE_TREE_OBJECTID, + item.Key.ObjectID, + btrfsitem.FREE_SPACE_INFO_KEY, + item.Key.Offset) + case btrfsitem.Chunk: + o.want(dlog.WithField(ctx, "wants", "owning Root"), + btrfsprim.ROOT_TREE_OBJECTID, + body.Head.Owner, + btrfsitem.ROOT_ITEM_KEY) + case btrfsitem.Dev: + // nothing + case btrfsitem.DevExtent: + o.wantOff(dlog.WithField(ctx, "wants", "Chunk"), + body.ChunkTree, + body.ChunkObjectID, + btrfsitem.CHUNK_ITEM_KEY, + uint64(body.ChunkOffset)) + case btrfsitem.DevStats: + // nothing + case btrfsitem.DirEntry: + // containing-directory + o.wantOff(dlog.WithField(ctx, "wants", "containing dir inode"), + treeID, + item.Key.ObjectID, + btrfsitem.INODE_ITEM_KEY, + 0) + // siblings + switch item.Key.ItemType { + case btrfsitem.DIR_ITEM_KEY: + o.wantFunc(dlog.WithField(ctx, "wants", "corresponding DIR_INDEX"), + treeID, + item.Key.ObjectID, + btrfsitem.DIR_INDEX_KEY, + func(peerItem btrfsitem.Item) bool { + return reflect.DeepEqual(item, peerItem) + }) + case btrfsitem.DIR_INDEX_KEY: + o.wantOff(dlog.WithField(ctx, "wants", "corresponding DIR_ITEM"), + treeID, + item.Key.ObjectID, + btrfsitem.DIR_ITEM_KEY, + btrfsitem.NameHash(body.Name)) + case btrfsitem.XATTR_ITEM_KEY: + // nothing + } + // item-within-directory + if body.Location != (btrfsprim.Key{}) { + switch body.Location.ItemType { + case btrfsitem.INODE_ITEM_KEY: + o.wantOff(dlog.WithField(ctx, "wants", "item being pointed to"), + treeID, + body.Location.ObjectID, + body.Location.ItemType, + body.Location.Offset) + o.wantOff(dlog.WithField(ctx, "wants", "backref from item being pointed to"), + treeID, + body.Location.ObjectID, + btrfsitem.INODE_REF_KEY, + uint64(item.Key.ObjectID)) + case btrfsitem.ROOT_ITEM_KEY: + o.want(dlog.WithField(ctx, "wants", "Root of subvolume being pointed to"), + btrfsprim.ROOT_TREE_OBJECTID, + body.Location.ObjectID, + body.Location.ItemType) + default: + o.err(ctx, fmt.Errorf("DirEntry: unexpected .Location.ItemType: %v", body.Location.ItemType)) + } + } + case btrfsitem.Empty: + // nothing + case btrfsitem.Extent: + //if body.Head.Flags.Has(btrfsitem.EXTENT_FLAG_TREE_BLOCK) { + // // Supposedly this flag indicates that that + // // body.Info.Key identifies a node by the + // // first key in the node. But nothing in the + // // kernel ever reads this, so who knows if it + // // always gets updated correctly? + //} + for _, ref := range body.Refs { + switch refBody := ref.Body.(type) { + case nil: + // nothing + case btrfsitem.ExtentDataRef: + o.wantOff(dlog.WithField(ctx, "wants", "referencing Inode"), + refBody.Root, + refBody.ObjectID, + btrfsitem.INODE_ITEM_KEY, + 0) + o.wantOff(dlog.WithField(ctx, "wants", "referencing FileExtent"), + refBody.Root, + refBody.ObjectID, + btrfsitem.EXTENT_DATA_KEY, + uint64(refBody.Offset)) + case btrfsitem.SharedDataRef: + // nothing + default: + panic("should not happen") + } + } + case btrfsitem.ExtentCSum: + // nothing + case btrfsitem.ExtentDataRef: + o.want(dlog.WithField(ctx, "wants", "Extent being referenced"), + btrfsprim.EXTENT_TREE_OBJECTID, + item.Key.ObjectID, + btrfsitem.EXTENT_ITEM_KEY) + o.wantOff(dlog.WithField(ctx, "wants", "referencing Inode"), + body.Root, + body.ObjectID, + btrfsitem.INODE_ITEM_KEY, + 0) + o.wantOff(dlog.WithField(ctx, "wants", "referencing FileExtent"), + body.Root, + body.ObjectID, + btrfsitem.EXTENT_DATA_KEY, + uint64(body.Offset)) + case btrfsitem.FileExtent: + o.wantOff(dlog.WithField(ctx, "wants", "containing Inode"), + treeID, + item.Key.ObjectID, + btrfsitem.INODE_ITEM_KEY, + 0) + switch body.Type { + case btrfsitem.FILE_EXTENT_INLINE: + // nothing + case btrfsitem.FILE_EXTENT_REG, btrfsitem.FILE_EXTENT_PREALLOC: + // TODO: Check if inodeBody.Flags.Has(btrfsitem.INODE_NODATASUM) + o.wantCSum(dlog.WithField(ctx, "wants", "data sum"), + roundDown(body.BodyExtent.DiskByteNr, btrfssum.BlockSize), + roundUp(body.BodyExtent.DiskByteNr.Add(body.BodyExtent.DiskNumBytes), btrfssum.BlockSize)) + default: + o.err(ctx, fmt.Errorf("FileExtent: unexpected body.Type: %v", body.Type)) + } + case btrfsitem.FreeSpaceBitmap: + o.wantOff(dlog.WithField(ctx, "wants", "FreeSpaceInfo"), + treeID, + item.Key.ObjectID, + btrfsitem.FREE_SPACE_INFO_KEY, + item.Key.Offset) + case btrfsitem.FreeSpaceHeader: + o.wantOff(dlog.WithField(ctx, "wants", ".Location"), + treeID, + body.Location.ObjectID, + body.Location.ItemType, + body.Location.Offset) + case btrfsitem.FreeSpaceInfo: + if body.Flags.Has(btrfsitem.FREE_SPACE_USING_BITMAPS) { + o.wantOff(dlog.WithField(ctx, "wants", "FreeSpaceBitmap"), + treeID, + item.Key.ObjectID, + btrfsitem.FREE_SPACE_BITMAP_KEY, + item.Key.Offset) + } + case btrfsitem.Inode: + o.want(dlog.WithField(ctx, "wants", "backrefs"), + treeID, // TODO: validate the number of these against body.NLink + item.Key.ObjectID, + btrfsitem.INODE_REF_KEY) + o.wantFileExt(dlog.WithField(ctx, "wants", "FileExtents"), + treeID, item.Key.ObjectID, body.Size) + if body.BlockGroup != 0 { + o.want(dlog.WithField(ctx, "wants", "BlockGroup"), + btrfsprim.EXTENT_TREE_OBJECTID, + body.BlockGroup, + btrfsitem.BLOCK_GROUP_ITEM_KEY) + } + case btrfsitem.InodeRefs: + o.wantOff(dlog.WithField(ctx, "wants", "child Inode"), + treeID, + item.Key.ObjectID, + btrfsitem.INODE_ITEM_KEY, + 0) + o.wantOff(dlog.WithField(ctx, "wants", "parent Inode"), + treeID, + btrfsprim.ObjID(item.Key.Offset), + btrfsitem.INODE_ITEM_KEY, + 0) + for _, ref := range body { + o.wantOff(dlog.WithField(ctx, "wants", "DIR_ITEM"), + treeID, + btrfsprim.ObjID(item.Key.Offset), + btrfsitem.DIR_ITEM_KEY, + btrfsitem.NameHash(ref.Name)) + o.wantOff(dlog.WithField(ctx, "wants", "DIR_INDEX"), + treeID, + btrfsprim.ObjID(item.Key.Offset), + btrfsitem.DIR_INDEX_KEY, + uint64(ref.Index)) + } + case btrfsitem.Metadata: + for _, ref := range body.Refs { + switch refBody := ref.Body.(type) { + case nil: + // nothing + case btrfsitem.ExtentDataRef: + o.wantOff(dlog.WithField(ctx, "wants", "referencing INode"), + refBody.Root, + refBody.ObjectID, + btrfsitem.INODE_ITEM_KEY, + 0) + o.wantOff(dlog.WithField(ctx, "wants", "referencing FileExtent"), + refBody.Root, + refBody.ObjectID, + btrfsitem.EXTENT_DATA_KEY, + uint64(refBody.Offset)) + case btrfsitem.SharedDataRef: + // nothing + default: + panic("should not happen") + } + } + case btrfsitem.Root: + if body.RootDirID != 0 { + o.wantOff(dlog.WithField(ctx, "wants", "root directory"), + item.Key.ObjectID, + body.RootDirID, + btrfsitem.INODE_ITEM_KEY, + 0) + } + case btrfsitem.RootRef: + var otherType btrfsprim.ItemType + var parent, child btrfsprim.ObjID + switch item.Key.ItemType { + case btrfsitem.ROOT_REF_KEY: + otherType = btrfsitem.ROOT_BACKREF_KEY + parent = item.Key.ObjectID + child = btrfsprim.ObjID(item.Key.Offset) + case btrfsitem.ROOT_BACKREF_KEY: + otherType = btrfsitem.ROOT_REF_KEY + parent = btrfsprim.ObjID(item.Key.Offset) + child = item.Key.ObjectID + default: + panic("should not happen") + } + // sibling + o.wantOff(dlog.WithField(ctx, "wants", fmt.Sprintf("corresponding %v", otherType)), + treeID, + btrfsprim.ObjID(item.Key.Offset), + otherType, + uint64(item.Key.ObjectID)) + // parent + o.want(dlog.WithField(ctx, "wants", "parent subvolume: Root"), + treeID, + parent, + btrfsitem.ROOT_ITEM_KEY) + o.wantOff(dlog.WithField(ctx, "wants", "parent subvolume: Inode of parent dir"), + parent, + body.DirID, + btrfsitem.INODE_ITEM_KEY, + 0) + o.wantOff(dlog.WithField(ctx, "wants", "parent subvolume: DIR_ITEM in parent dir"), + parent, + body.DirID, + btrfsitem.DIR_ITEM_KEY, + btrfsitem.NameHash(body.Name)) + o.wantOff(dlog.WithField(ctx, "wants", "parent subvolume: DIR_INDEX in parent dir"), + parent, + body.DirID, + btrfsitem.DIR_INDEX_KEY, + uint64(body.Sequence)) + // child + o.want(dlog.WithField(ctx, "wants", "child subvolume: Root"), + treeID, + child, + btrfsitem.ROOT_ITEM_KEY) + case btrfsitem.SharedDataRef: + o.want(dlog.WithField(ctx, "wants", "Extent"), + btrfsprim.EXTENT_TREE_OBJECTID, + item.Key.ObjectID, + btrfsitem.EXTENT_ITEM_KEY) + case btrfsitem.UUIDMap: + o.want(dlog.WithField(ctx, "wants", "subvolume Root"), + btrfsprim.ROOT_TREE_OBJECTID, + body.ObjID, + btrfsitem.ROOT_ITEM_KEY) + default: + panic(fmt.Errorf("unsupported item type: %T", body)) + } +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go deleted file mode 100644 index 42228ae..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/treeancestors.go +++ /dev/null @@ -1,76 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -/* -import ( - "context" - - //"github.com/datawire/dlib/dlog" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" -) - -func getTreeAncestors(ctx context.Context, scanData scanResult) map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID] { - treeAncestors := make(map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) - - for laddr, node := range scanData.Nodes { - if _, ok := treeAncestors[node.Owner]; !ok { - treeAncestors[node.Owner] = make(containers.Set[btrfsprim.ObjID]) - } - for _, edge := range scanData.EdgesTo[laddr] { - if edge.FromTree != node.Owner { - if err := checkNodeExpectations(*edge, node); err != nil { - //dlog.Errorf(ctx, "... ignoring keypointer %v because %v", edge.String(), err) - } else { - treeAncestors[node.Owner].Insert(edge.FromTree) - } - } - } - } - - return treeAncestors -} - -func (m uuidMap) considerAncestors(ctx context.Context, treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID]) { - if missing := m.missingRootItems(); len(missing) == 0 { - return - } else { - dlog.Infof(ctx, "Rebuilding %d root items...", len(missing)) - } - - fa := newFullAncestorLister(m, treeAncestors) - - for _, missingRoot := range maps.SortedKeys(m.missingRootItems()) { - if _, ok := m.TreeParent[missingRoot]; ok { - // This one is incomplete because it doesn't have a UUID, not - // because it doesn't have a parent. - continue - } - potentialParents := make(containers.Set[btrfsprim.ObjID]) - potentialParents.InsertFrom(fa.GetFullAncestors(missingRoot)) - for _, ancestor := range maps.SortedKeys(fa.GetFullAncestors(missingRoot)) { - potentialParents.DeleteFrom(fa.GetFullAncestors(ancestor)) - } - if len(potentialParents) == 1 { - parent := potentialParents.TakeOne() - dlog.Infof(ctx, "... the parent of %v is %v", missingRoot, parent) - parentUUID, ok := m.ObjID2UUID[parent] - if !ok { - dlog.Errorf(ctx, "... but can't synthesize a root item because UUID of %v is unknown", parent) - continue - } - m.TreeParent[missingRoot] = parentUUID - } - } - - if missing := m.missingRootItems(); len(missing) > 0 { - dlog.Errorf(ctx, "... could not rebuild root items for %d trees: %v", len(missing), maps.SortedKeys(missing)) - } else { - dlog.Info(ctx, "... rebuilt all root items") - } -} -*/ diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go index f1033e6..bdaa0c4 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go @@ -7,6 +7,8 @@ package rebuildnodes import ( "fmt" + "golang.org/x/exp/constraints" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" ) @@ -18,26 +20,6 @@ func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) error { return nil } -/* -var maxKey = btrfsprim.Key{ - ObjectID: math.MaxUint64, - ItemType: math.MaxUint8, - Offset: math.MaxUint64, -} - -func keyMm(key btrfsprim.Key) btrfsprim.Key { - switch { - case key.Offset > 0: - key.Offset-- - case key.ItemType > 0: - key.ItemType-- - case key.ObjectID > 0: - key.ObjectID-- - } - return key -} -*/ - func countNodes(nodeScanResults btrfsinspect.ScanDevicesResult) int { var cnt int for _, devResults := range nodeScanResults { @@ -45,3 +27,11 @@ func countNodes(nodeScanResults btrfsinspect.ScanDevicesResult) int { } return cnt } + +func roundDown[T constraints.Integer](n, d T) T { + return (n / d) * d +} + +func roundUp[T constraints.Integer](n, d T) T { + return ((n + d - 1) / d) * d +} diff --git a/lib/btrfsprogs/btrfsutil/broken_btree.go b/lib/btrfsprogs/btrfsutil/broken_btree.go index 0660a46..8833937 100644 --- a/lib/btrfsprogs/btrfsutil/broken_btree.go +++ b/lib/btrfsprogs/btrfsutil/broken_btree.go @@ -94,6 +94,7 @@ 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, @@ -315,3 +316,8 @@ func (bt *brokenTrees) Superblock() (*btrfstree.Superblock, error) { 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) { + // TODO + return nil, nil +} -- cgit v1.2.3-2-g168b From 168e5afbf903fb17ca4680deae2b2716d11f1d03 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 26 Nov 2022 11:56:32 -0700 Subject: broken_btree: Implement .Augment() --- lib/btrfsprogs/btrfsutil/broken_btree.go | 91 ++++++++++++++++++++------------ 1 file changed, 58 insertions(+), 33 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsutil/broken_btree.go b/lib/btrfsprogs/btrfsutil/broken_btree.go index 8833937..e44c9e1 100644 --- a/lib/btrfsprogs/btrfsutil/broken_btree.go +++ b/lib/btrfsprogs/btrfsutil/broken_btree.go @@ -145,37 +145,7 @@ func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex { cacheEntry.TreeRootErr = err } else { dlog.Infof(bt.ctx, "indexing tree %v...", treeID) - btrfstree.TreeOperatorImpl{NodeSource: bt.inner}.RawTreeWalk( - bt.ctx, - *treeRoot, - 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.Lookup(item.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, treeID)) - } - cacheEntry.Items.Insert(treeIndexValue{ - Path: bt.arena.Deflate(path), - Key: item.Key, - ItemSize: item.BodySize, - }) - return nil - }, - }, - ) + bt.rawTreeWalk(*treeRoot, cacheEntry, nil) dlog.Infof(bt.ctx, "... done indexing tree %v", treeID) } if treeID == btrfsprim.ROOT_TREE_OBJECTID { @@ -186,6 +156,43 @@ func (bt *brokenTrees) treeIndex(treeID btrfsprim.ObjID) treeIndex { 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.Lookup(item.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.Cmp)) if err != nil { @@ -318,6 +325,24 @@ func (bt *brokenTrees) ReadAt(p []byte, off btrfsvol.LogicalAddr) (int, error) { } func (bt *brokenTrees) Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error) { - // TODO - return nil, nil + 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{}) + 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 } -- cgit v1.2.3-2-g168b From 77046dcf26687fd74df0f7966d7d469f6b6de717 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 27 Nov 2022 16:41:44 -0700 Subject: rebuildnodes: Refactor the node-graph stuff in to a separate sub-package --- .../btrfsinspect/rebuildnodes/graph/graph.go | 157 ++++++++++++++++++++ .../btrfsinspect/rebuildnodes/graph/loops.go | 165 +++++++++++++++++++++ lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go | 153 +------------------ .../btrfsinspect/rebuildnodes/orphans.go | 7 +- .../btrfsinspect/rebuildnodes/rebuild.go | 2 +- lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go | 135 ++--------------- 6 files changed, 337 insertions(+), 282 deletions(-) create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go new file mode 100644 index 0000000..7ae3b89 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/graph.go @@ -0,0 +1,157 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package graph + +import ( + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "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 Node struct { + Level uint8 + Generation btrfsprim.Generation + Owner btrfsprim.ObjID + NumItems uint32 + MinItem btrfsprim.Key + MaxItem btrfsprim.Key +} + +type Edge struct { + FromTree btrfsprim.ObjID + FromNode btrfsvol.LogicalAddr + FromItem int + + ToNode btrfsvol.LogicalAddr + ToLevel uint8 + ToKey btrfsprim.Key + ToGeneration btrfsprim.Generation +} + +func (kp Edge) String() string { + return fmt.Sprintf(`{t:%v,n:%v}[%d]->{n:%v,l:%v,g:%v,k:(%d,%v,%d)}`, + kp.FromTree, kp.FromNode, kp.FromItem, + kp.ToNode, kp.ToLevel, kp.ToGeneration, + kp.ToKey.ObjectID, + kp.ToKey.ItemType, + kp.ToKey.Offset) +} + +type Graph struct { + Nodes map[btrfsvol.LogicalAddr]Node + BadNodes map[btrfsvol.LogicalAddr]error + EdgesFrom map[btrfsvol.LogicalAddr][]*Edge + EdgesTo map[btrfsvol.LogicalAddr][]*Edge +} + +func (g Graph) insertEdge(kp Edge) { + ptr := &kp + if kp.ToNode == 0 { + panic("kp.ToNode should not be zero") + } + g.EdgesFrom[kp.FromNode] = append(g.EdgesFrom[kp.FromNode], ptr) + g.EdgesTo[kp.ToNode] = append(g.EdgesTo[kp.ToNode], ptr) +} + +func (g Graph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) { + treeInfo, err := btrfstree.LookupTreeRoot(nil, sb, treeID) + if err != nil { + // This shouldn't ever happen for treeIDs that are + // mentioned directly in the superblock; which are the + // only trees for which we should call + // .insertTreeRoot(). + panic(fmt.Errorf("LookupTreeRoot(%v): %w", treeID, err)) + } + if treeInfo.RootNode == 0 { + return + } + g.insertEdge(Edge{ + FromTree: treeID, + ToNode: treeInfo.RootNode, + ToLevel: treeInfo.Level, + ToGeneration: treeInfo.Generation, + }) +} + +func New(sb btrfstree.Superblock) *Graph { + g := &Graph{ + Nodes: make(map[btrfsvol.LogicalAddr]Node), + BadNodes: make(map[btrfsvol.LogicalAddr]error), + EdgesFrom: make(map[btrfsvol.LogicalAddr][]*Edge), + EdgesTo: make(map[btrfsvol.LogicalAddr][]*Edge), + } + + // These 4 trees are mentioned directly in the superblock, so + // they are always seen. + g.insertTreeRoot(sb, btrfsprim.ROOT_TREE_OBJECTID) + g.insertTreeRoot(sb, btrfsprim.CHUNK_TREE_OBJECTID) + g.insertTreeRoot(sb, btrfsprim.TREE_LOG_OBJECTID) + g.insertTreeRoot(sb, btrfsprim.BLOCK_GROUP_TREE_OBJECTID) + + return g +} + +func (g *Graph) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) { + for _, item := range nodeRef.Data.BodyLeaf { + switch itemBody := item.Body.(type) { + case btrfsitem.Root: + g.insertEdge(Edge{ + FromTree: item.Key.ObjectID, + ToNode: itemBody.ByteNr, + ToLevel: itemBody.Level, + ToGeneration: itemBody.Generation, + }) + } + } + + g.Nodes[nodeRef.Addr] = Node{ + Level: nodeRef.Data.Head.Level, + Generation: nodeRef.Data.Head.Generation, + Owner: nodeRef.Data.Head.Owner, + NumItems: nodeRef.Data.Head.NumItems, + MinItem: discardOK(nodeRef.Data.MinItem()), + MaxItem: discardOK(nodeRef.Data.MaxItem()), + } + for i, kp := range nodeRef.Data.BodyInternal { + g.insertEdge(Edge{ + FromTree: nodeRef.Data.Head.Owner, + FromNode: nodeRef.Addr, + FromItem: i, + ToNode: kp.BlockPtr, + ToLevel: nodeRef.Data.Head.Level - 1, + ToKey: kp.Key, + ToGeneration: kp.Generation, + }) + } +} + +func (g *Graph) FinalCheck(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, progress func(n, d int)) error { + total := len(g.EdgesTo) + done := 0 + progress(done, total) + for laddr := range g.EdgesTo { + if _, ok := g.Nodes[laddr]; !ok { + _, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, + }) + if err == nil { + return fmt.Errorf("node@%v exists but was not in node scan results", laddr) + } + g.BadNodes[laddr] = err + } + done++ + progress(done, total) + } + return nil +} + +func discardOK[T any](val T, _ bool) T { + return val +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go new file mode 100644 index 0000000..e76985c --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph/loops.go @@ -0,0 +1,165 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package graph + +import ( + "fmt" + "io" + "strings" + + "github.com/datawire/dlib/derror" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" + "git.lukeshu.com/btrfs-progs-ng/lib/slices" +) + +func (g Graph) ShowLoops(out io.Writer) { + orphans := make(containers.Set[btrfsvol.LogicalAddr]) + for node := range g.Nodes { + if len(g.EdgesTo[node]) == 0 { + orphans.Insert(node) + } + } + + loopWalk(out, g, 0) + for _, orphan := range maps.SortedKeys(orphans) { + loopWalk(out, g, orphan) + } +} + +func loopWalk(out io.Writer, scanData Graph, stack ...btrfsvol.LogicalAddr) { + for _, kp := range scanData.EdgesFrom[stack[len(stack)-1]] { + childStack := append(stack, kp.ToNode) + if slices.Contains(kp.ToNode, stack) { + loopRender(out, scanData, childStack...) + } else { + loopWalk(out, scanData, childStack...) + } + } +} + +func nodeRender(scanData Graph, node btrfsvol.LogicalAddr) []string { + if node == 0 { + return []string{"root"} + } else if nodeData, ok := scanData.Nodes[node]; ok { + return []string{ + fmt.Sprintf("{addr: %v,", node), + fmt.Sprintf(" level: %v,", nodeData.Level), + fmt.Sprintf(" gen: %v,", nodeData.Generation), + fmt.Sprintf(" num_items: %v,", nodeData.NumItems), + fmt.Sprintf(" min_item: {%d,%v,%d},", + nodeData.MinItem.ObjectID, + nodeData.MinItem.ItemType, + nodeData.MinItem.Offset), + fmt.Sprintf(" max_item: {%d,%v,%d}}", + nodeData.MaxItem.ObjectID, + nodeData.MaxItem.ItemType, + nodeData.MaxItem.Offset), + } + } else if nodeErr, ok := scanData.BadNodes[node]; ok { + return []string{ + fmt.Sprintf("{addr:%v,", node), + fmt.Sprintf(" err:%q}", nodeErr.Error()), + } + } else { + panic("should not happen") + } +} + +func edgeRender(scanData Graph, kp Edge) []string { + a := fmt.Sprintf("[%d]={", kp.FromItem) + b := strings.Repeat(" ", len(a)) + ret := []string{ + a + fmt.Sprintf("ToNode: %v,", kp.ToNode), + b + fmt.Sprintf("ToLevel: %v,", kp.ToLevel), + b + fmt.Sprintf("ToGen: %v,", kp.ToGeneration), + b + fmt.Sprintf("ToKey: {%d,%v,%d}}", + kp.ToKey.ObjectID, + kp.ToKey.ItemType, + kp.ToKey.Offset), + } + + var err error + if toNode, ok := scanData.Nodes[kp.ToNode]; !ok { + err = scanData.BadNodes[kp.ToNode] + } else { + err = checkNodeExpectations(kp, toNode) + } + if err != nil { + c := strings.Repeat(" ", len(a)-1) + ret = append(ret, + c+"^", + c+"`-err="+strings.ReplaceAll(err.Error(), "\n", "\n"+c+" "), + ) + } + return ret +} + +func loopRender(out io.Writer, scanData Graph, stack ...btrfsvol.LogicalAddr) { + var lines []string + add := func(suffixes []string) { + curLen := 0 + for _, line := range lines { + if len(line) > curLen { + curLen = len(line) + } + } + for i, suffix := range suffixes { + if len(lines) <= i { + lines = append(lines, "") + } + if len(lines[i]) < curLen { + if i == 0 { + lines[i] += strings.Repeat("-", curLen-len(lines[i])-1) + ">" + } else { + lines[i] += strings.Repeat(" ", curLen-len(lines[i])) + } + } + lines[i] += suffix + } + } + + for i, node := range stack { + if i > 0 { + for _, kp := range scanData.EdgesTo[node] { + if kp.FromNode == stack[i-1] { + add(edgeRender(scanData, *kp)) + break + } + } + } + add(nodeRender(scanData, node)) + } + + fmt.Fprintln(out, "loop:") + for _, line := range lines { + fmt.Fprintln(out, " "+line) + } +} + +func checkNodeExpectations(kp Edge, toNode Node) error { + var errs derror.MultiError + if toNode.Level != kp.ToLevel { + errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v", + kp.ToLevel, toNode.Level)) + } + if toNode.Generation != kp.ToGeneration { + errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v", + kp.ToGeneration, toNode.Generation)) + } + if toNode.NumItems == 0 { + errs = append(errs, fmt.Errorf("node.num_items=0")) + } else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey { + errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v", + kp.ToKey, toNode.MinItem)) + } + if len(errs) > 0 { + return errs + } + return nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go index 8ee53d2..57eb139 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go @@ -6,20 +6,12 @@ package rebuildnodes import ( "context" - "fmt" "io" - "strings" - "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/btrfsvol" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" - "git.lukeshu.com/btrfs-progs-ng/lib/maps" - "git.lukeshu.com/btrfs-progs-ng/lib/slices" ) func ShowLoops(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) error { @@ -28,151 +20,8 @@ func ShowLoops(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanResults return err } - dlog.Info(ctx, "Collecting orphans...") - orphans := make(containers.Set[btrfsvol.LogicalAddr]) - for node := range scanData.Nodes { - if len(scanData.EdgesTo[node]) == 0 { - orphans.Insert(node) - } - } - dlog.Info(ctx, "Walking graph...") - loopWalk(out, *scanData, 0) - for _, orphan := range maps.SortedKeys(orphans) { - loopWalk(out, *scanData, orphan) - } - - return nil -} - -func loopWalk(out io.Writer, scanData scanResult, stack ...btrfsvol.LogicalAddr) { - for _, kp := range scanData.EdgesFrom[stack[len(stack)-1]] { - childStack := append(stack, kp.ToNode) - if slices.Contains(kp.ToNode, stack) { - loopRender(out, scanData, childStack...) - } else { - loopWalk(out, scanData, childStack...) - } - } -} - -func nodeRender(scanData scanResult, node btrfsvol.LogicalAddr) []string { - if node == 0 { - return []string{"root"} - } else if nodeData, ok := scanData.Nodes[node]; ok { - return []string{ - fmt.Sprintf("{addr: %v,", node), - fmt.Sprintf(" level: %v,", nodeData.Level), - fmt.Sprintf(" gen: %v,", nodeData.Generation), - fmt.Sprintf(" num_items: %v,", nodeData.NumItems), - fmt.Sprintf(" min_item: {%d,%v,%d},", - nodeData.MinItem.ObjectID, - nodeData.MinItem.ItemType, - nodeData.MinItem.Offset), - fmt.Sprintf(" max_item: {%d,%v,%d}}", - nodeData.MaxItem.ObjectID, - nodeData.MaxItem.ItemType, - nodeData.MaxItem.Offset), - } - } else if nodeErr, ok := scanData.BadNodes[node]; ok { - return []string{ - fmt.Sprintf("{addr:%v,", node), - fmt.Sprintf(" err:%q}", nodeErr.Error()), - } - } else { - panic("should not happen") - } -} - -func edgeRender(scanData scanResult, kp kpData) []string { - a := fmt.Sprintf("[%d]={", kp.FromItem) - b := strings.Repeat(" ", len(a)) - ret := []string{ - a + fmt.Sprintf("ToNode: %v,", kp.ToNode), - b + fmt.Sprintf("ToLevel: %v,", kp.ToLevel), - b + fmt.Sprintf("ToGen: %v,", kp.ToGeneration), - b + fmt.Sprintf("ToKey: {%d,%v,%d}}", - kp.ToKey.ObjectID, - kp.ToKey.ItemType, - kp.ToKey.Offset), - } - - var err error - if toNode, ok := scanData.Nodes[kp.ToNode]; !ok { - err = scanData.BadNodes[kp.ToNode] - } else { - err = checkNodeExpectations(kp, toNode) - } - if err != nil { - c := strings.Repeat(" ", len(a)-1) - ret = append(ret, - c+"^", - c+"`-err="+strings.ReplaceAll(err.Error(), "\n", "\n"+c+" "), - ) - } - return ret -} - -func loopRender(out io.Writer, scanData scanResult, stack ...btrfsvol.LogicalAddr) { - var lines []string - add := func(suffixes []string) { - curLen := 0 - for _, line := range lines { - if len(line) > curLen { - curLen = len(line) - } - } - for i, suffix := range suffixes { - if len(lines) <= i { - lines = append(lines, "") - } - if len(lines[i]) < curLen { - if i == 0 { - lines[i] += strings.Repeat("-", curLen-len(lines[i])-1) + ">" - } else { - lines[i] += strings.Repeat(" ", curLen-len(lines[i])) - } - } - lines[i] += suffix - } - } - - for i, node := range stack { - if i > 0 { - for _, kp := range scanData.EdgesTo[node] { - if kp.FromNode == stack[i-1] { - add(edgeRender(scanData, *kp)) - break - } - } - } - add(nodeRender(scanData, node)) - } + scanData.nodeGraph.ShowLoops(out) - fmt.Fprintln(out, "loop:") - for _, line := range lines { - fmt.Fprintln(out, " "+line) - } -} - -func checkNodeExpectations(kp kpData, toNode nodeData) error { - var errs derror.MultiError - if toNode.Level != kp.ToLevel { - errs = append(errs, fmt.Errorf("kp.level=%v != node.level=%v", - kp.ToLevel, toNode.Level)) - } - if toNode.Generation != kp.ToGeneration { - errs = append(errs, fmt.Errorf("kp.generation=%v != node.generation=%v", - kp.ToGeneration, toNode.Generation)) - } - if toNode.NumItems == 0 { - errs = append(errs, fmt.Errorf("node.num_items=0")) - } else if kp.ToKey != (btrfsprim.Key{}) && toNode.MinItem != kp.ToKey { - errs = append(errs, fmt.Errorf("kp.key=%v != node.items[0].key=%v", - kp.ToKey, toNode.MinItem)) - } - if len(errs) > 0 { - return errs - } return nil } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go index 3d375f0..70bd128 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -8,11 +8,12 @@ import ( "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/btrfsprogs/btrfsinspect/rebuildnodes/graph" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" ) -func listRoots(graph nodeGraph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { +func listRoots(graph graph.Graph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { kps := graph.EdgesTo[leaf] if len(kps) == 0 { return containers.NewSet(leaf) @@ -24,7 +25,7 @@ func listRoots(graph nodeGraph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsv return ret } -func walk(graph nodeGraph, root btrfsvol.LogicalAddr, fn func(btrfsvol.LogicalAddr) bool) { +func walk(graph graph.Graph, root btrfsvol.LogicalAddr, fn func(btrfsvol.LogicalAddr) bool) { if _, ok := graph.Nodes[root]; !ok { return } @@ -48,7 +49,7 @@ func (a keyAndTree) Cmp(b keyAndTree) int { return containers.NativeCmp(a.TreeID, b.TreeID) } -func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph nodeGraph) ( +func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph graph.Graph) ( orphans containers.Set[btrfsvol.LogicalAddr], leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], key2leaf *containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr], diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 536b61d..5a28008 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -45,7 +45,7 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec } dlog.Info(ctx, "Indexing orphans...") - orphans, leaf2orphans, key2leaf, err := indexOrphans(fs, *sb, scanData.nodeGraph) + orphans, leaf2orphans, key2leaf, err := indexOrphans(fs, *sb, *scanData.nodeGraph) if err != nil { return nil, err } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go index c32ae8e..40ace46 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go @@ -6,7 +6,6 @@ package rebuildnodes import ( "context" - "fmt" "github.com/datawire/dlib/dlog" @@ -16,78 +15,14 @@ import ( "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/btrfsprogs/btrfsinspect" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) -type nodeData struct { - Level uint8 - Generation btrfsprim.Generation - Owner btrfsprim.ObjID - NumItems uint32 - MinItem btrfsprim.Key - MaxItem btrfsprim.Key -} - -type kpData struct { - FromTree btrfsprim.ObjID - FromNode btrfsvol.LogicalAddr - FromItem int - - ToNode btrfsvol.LogicalAddr - ToLevel uint8 - ToKey btrfsprim.Key - ToGeneration btrfsprim.Generation -} - -func (kp kpData) String() string { - return fmt.Sprintf(`{t:%v,n:%v}[%d]->{n:%v,l:%v,g:%v,k:(%d,%v,%d)}`, - kp.FromTree, kp.FromNode, kp.FromItem, - kp.ToNode, kp.ToLevel, kp.ToGeneration, - kp.ToKey.ObjectID, - kp.ToKey.ItemType, - kp.ToKey.Offset) -} - -type nodeGraph struct { - Nodes map[btrfsvol.LogicalAddr]nodeData - BadNodes map[btrfsvol.LogicalAddr]error - EdgesFrom map[btrfsvol.LogicalAddr][]*kpData - EdgesTo map[btrfsvol.LogicalAddr][]*kpData -} - -func (g nodeGraph) insertEdge(kp kpData) { - ptr := &kp - if kp.ToNode == 0 { - panic("kp.ToNode should not be zero") - } - g.EdgesFrom[kp.FromNode] = append(g.EdgesFrom[kp.FromNode], ptr) - g.EdgesTo[kp.ToNode] = append(g.EdgesTo[kp.ToNode], ptr) -} - -func (g nodeGraph) insertTreeRoot(sb btrfstree.Superblock, treeID btrfsprim.ObjID) { - treeInfo, err := btrfstree.LookupTreeRoot(nil, sb, treeID) - if err != nil { - // This shouldn't ever happen for treeIDs that are - // mentioned directly in the superblock; which are the - // only trees for which we should call - // .insertTreeRoot(). - panic(fmt.Errorf("LookupTreeRoot(%v): %w", treeID, err)) - } - if treeInfo.RootNode == 0 { - return - } - g.insertEdge(kpData{ - FromTree: treeID, - ToNode: treeInfo.RootNode, - ToLevel: treeInfo.Level, - ToGeneration: treeInfo.Generation, - }) -} - type scanResult struct { uuidMap - nodeGraph + nodeGraph *graph.Graph } func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (*scanResult, error) { @@ -101,7 +36,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca lastPct := -1 total := countNodes(scanResults) done := 0 - progress := func() { + progress := func(done, total int) { pct := int(100 * float64(done) / float64(total)) if pct != lastPct || done == total { dlog.Infof(ctx, "... %v%% (%v/%v)", @@ -118,31 +53,17 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca SeenTrees: make(containers.Set[btrfsprim.ObjID]), }, - nodeGraph: nodeGraph{ - Nodes: make(map[btrfsvol.LogicalAddr]nodeData), - BadNodes: make(map[btrfsvol.LogicalAddr]error), - EdgesFrom: make(map[btrfsvol.LogicalAddr][]*kpData), - EdgesTo: make(map[btrfsvol.LogicalAddr][]*kpData), - }, + nodeGraph: graph.New(*sb), } // These 4 trees are mentioned directly in the superblock, so // they are always seen. - // - // 1 ret.SeenTrees.Insert(btrfsprim.ROOT_TREE_OBJECTID) - ret.insertTreeRoot(*sb, btrfsprim.ROOT_TREE_OBJECTID) - // 2 ret.SeenTrees.Insert(btrfsprim.CHUNK_TREE_OBJECTID) - ret.insertTreeRoot(*sb, btrfsprim.CHUNK_TREE_OBJECTID) - // 3 ret.SeenTrees.Insert(btrfsprim.TREE_LOG_OBJECTID) - ret.insertTreeRoot(*sb, btrfsprim.TREE_LOG_OBJECTID) - // 4 ret.SeenTrees.Insert(btrfsprim.BLOCK_GROUP_TREE_OBJECTID) - ret.insertTreeRoot(*sb, btrfsprim.BLOCK_GROUP_TREE_OBJECTID) - progress() + progress(done, total) for _, devResults := range scanResults { for laddr := range devResults.FoundNodes { nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ @@ -168,13 +89,6 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca return nil, err } ret.SeenTrees.Insert(item.Key.ObjectID) - // graph building - ret.insertEdge(kpData{ - FromTree: item.Key.ObjectID, - ToNode: itemBody.ByteNr, - ToLevel: itemBody.Level, - ToGeneration: itemBody.Generation, - }) case btrfsitem.UUIDMap: uuid := btrfsitem.KeyToUUID(item.Key) if err := maybeSet("ObjID2UUID", ret.ObjID2UUID, itemBody.ObjID, uuid); err != nil { @@ -188,28 +102,10 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca ret.SeenTrees.Insert(nodeRef.Data.Head.Owner) // graph building - ret.Nodes[laddr] = nodeData{ - Level: nodeRef.Data.Head.Level, - Generation: nodeRef.Data.Head.Generation, - Owner: nodeRef.Data.Head.Owner, - NumItems: nodeRef.Data.Head.NumItems, - MinItem: func() btrfsprim.Key { k, _ := nodeRef.Data.MinItem(); return k }(), - MaxItem: func() btrfsprim.Key { k, _ := nodeRef.Data.MaxItem(); return k }(), - } - for i, kp := range nodeRef.Data.BodyInternal { - ret.insertEdge(kpData{ - FromTree: nodeRef.Data.Head.Owner, - FromNode: laddr, - FromItem: i, - ToNode: kp.BlockPtr, - ToLevel: nodeRef.Data.Head.Level - 1, - ToKey: kp.Key, - ToGeneration: kp.Generation, - }) - } + ret.nodeGraph.InsertNode(nodeRef) done++ - progress() + progress(done, total) } } @@ -225,21 +121,8 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca dlog.Info(ctx, "... done reading node data") dlog.Infof(ctx, "Checking keypointers for dead-ends...") - total = len(ret.EdgesTo) - done = 0 - progress() - for laddr := range ret.EdgesTo { - if _, ok := ret.Nodes[laddr]; !ok { - _, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{ - LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, - }) - if err == nil { - return nil, fmt.Errorf("node@%v exists but was not in node scan results", laddr) - } - ret.BadNodes[laddr] = err - } - done++ - progress() + if err := ret.nodeGraph.FinalCheck(fs, *sb, progress); err != nil { + return nil, err } dlog.Info(ctx, "... done checking keypointers") -- cgit v1.2.3-2-g168b From 60ca1cb76b2fef0a74cfb17837e90212631affea Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 27 Nov 2022 20:13:22 -0700 Subject: Delete 'inspect show-loops' --- lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go | 27 ----------------------- 1 file changed, 27 deletions(-) delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go deleted file mode 100644 index 57eb139..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/loops.go +++ /dev/null @@ -1,27 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "context" - "io" - - "github.com/datawire/dlib/dlog" - - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" -) - -func ShowLoops(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) error { - scanData, err := ScanDevices(ctx, fs, nodeScanResults) - if err != nil { - return err - } - - dlog.Info(ctx, "Walking graph...") - scanData.nodeGraph.ShowLoops(out) - - return nil -} -- cgit v1.2.3-2-g168b From 182bab3aa8b8e08d6a35d344c32d93a4293a36f4 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 29 Nov 2022 14:42:30 -0700 Subject: rebuildnodes: Refactor uuidMap in to a separate sub-package --- lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go | 51 ++------------- lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go | 10 --- .../btrfsinspect/rebuildnodes/uuidmap.go | 55 ---------------- .../btrfsinspect/rebuildnodes/uuidmap/scan.go | 73 ++++++++++++++++++++++ .../btrfsinspect/rebuildnodes/uuidmap/uuidmap.go | 55 ++++++++++++++++ 5 files changed, 134 insertions(+), 110 deletions(-) delete mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap/scan.go create mode 100644 lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap/uuidmap.go (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go index 40ace46..9174035 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go @@ -10,18 +10,17 @@ import ( "github.com/datawire/dlib/dlog" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" - "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/btrfsprogs/btrfsinspect" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) type scanResult struct { - uuidMap + uuidMap *uuidmap.UUIDMap nodeGraph *graph.Graph } @@ -46,23 +45,10 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca } ret := &scanResult{ - uuidMap: uuidMap{ - ObjID2UUID: make(map[btrfsprim.ObjID]btrfsprim.UUID), - UUID2ObjID: make(map[btrfsprim.UUID]btrfsprim.ObjID), - TreeParent: make(map[btrfsprim.ObjID]btrfsprim.UUID), - - SeenTrees: make(containers.Set[btrfsprim.ObjID]), - }, + uuidMap: uuidmap.New(), nodeGraph: graph.New(*sb), } - // These 4 trees are mentioned directly in the superblock, so - // they are always seen. - ret.SeenTrees.Insert(btrfsprim.ROOT_TREE_OBJECTID) - ret.SeenTrees.Insert(btrfsprim.CHUNK_TREE_OBJECTID) - ret.SeenTrees.Insert(btrfsprim.TREE_LOG_OBJECTID) - ret.SeenTrees.Insert(btrfsprim.BLOCK_GROUP_TREE_OBJECTID) - progress(done, total) for _, devResults := range scanResults { for laddr := range devResults.FoundNodes { @@ -73,35 +59,10 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca return nil, err } - // UUID map rebuilding - for _, item := range nodeRef.Data.BodyLeaf { - switch itemBody := item.Body.(type) { - case btrfsitem.Root: - if err := maybeSet("ObjID2UUID", ret.ObjID2UUID, item.Key.ObjectID, itemBody.UUID); err != nil { - return nil, err - } - if itemBody.UUID != (btrfsprim.UUID{}) { - if err := maybeSet("UUID2ObjID", ret.UUID2ObjID, itemBody.UUID, item.Key.ObjectID); err != nil { - return nil, err - } - } - if err := maybeSet("ParentUUID", ret.TreeParent, item.Key.ObjectID, itemBody.ParentUUID); err != nil { - return nil, err - } - ret.SeenTrees.Insert(item.Key.ObjectID) - case btrfsitem.UUIDMap: - uuid := btrfsitem.KeyToUUID(item.Key) - if err := maybeSet("ObjID2UUID", ret.ObjID2UUID, itemBody.ObjID, uuid); err != nil { - return nil, err - } - if err := maybeSet("UUID2ObjID", ret.UUID2ObjID, uuid, itemBody.ObjID); err != nil { - return nil, err - } - } + if err := ret.uuidMap.InsertNode(nodeRef); err != nil { + return nil, err } - ret.SeenTrees.Insert(nodeRef.Data.Head.Owner) - // graph building ret.nodeGraph.InsertNode(nodeRef) done++ @@ -113,7 +74,7 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca panic("should not happen") } - missing := ret.missingRootItems() + missing := ret.uuidMap.MissingRootItems() if len(missing) > 0 { dlog.Errorf(ctx, "... could not find root items for %d trees: %v", len(missing), maps.SortedKeys(missing)) } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go index bdaa0c4..8c43dad 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/util.go @@ -5,21 +5,11 @@ package rebuildnodes import ( - "fmt" - "golang.org/x/exp/constraints" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" ) -func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) error { - if other, conflict := m[k]; conflict && other != v { - return fmt.Errorf("conflict: %s %v can't have both %v and %v", name, k, other, v) - } - m[k] = v - return nil -} - func countNodes(nodeScanResults btrfsinspect.ScanDevicesResult) int { var cnt int for _, devResults := range nodeScanResults { diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go deleted file mode 100644 index 4d93916..0000000 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap.go +++ /dev/null @@ -1,55 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rebuildnodes - -import ( - "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" - "git.lukeshu.com/btrfs-progs-ng/lib/containers" -) - -type uuidMap struct { - ObjID2UUID map[btrfsprim.ObjID]btrfsprim.UUID - UUID2ObjID map[btrfsprim.UUID]btrfsprim.ObjID - TreeParent map[btrfsprim.ObjID]btrfsprim.UUID - - SeenTrees containers.Set[btrfsprim.ObjID] -} - -func (m uuidMap) missingRootItems() containers.Set[btrfsprim.ObjID] { - missing := make(containers.Set[btrfsprim.ObjID]) - for treeID := range m.SeenTrees { - if _, ok := m.ObjID2UUID[treeID]; !ok && treeID != btrfsprim.ROOT_TREE_OBJECTID { - missing.Insert(treeID) - continue - } - if _, ok := m.TreeParent[treeID]; !ok && treeID >= btrfsprim.FIRST_FREE_OBJECTID && treeID <= btrfsprim.LAST_FREE_OBJECTID { - missing.Insert(treeID) - } - } - return missing -} - -// ParentTree implements btrfstree.NodeFile. -func (m uuidMap) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { - if tree < btrfsprim.FIRST_FREE_OBJECTID || tree > btrfsprim.LAST_FREE_OBJECTID { - // no parent - return 0, true - } - parentUUID, ok := m.TreeParent[tree] - if !ok { - // could not look up parent info - return 0, false - } - if parentUUID == (btrfsprim.UUID{}) { - // no parent - return 0, true - } - parentObjID, ok := m.UUID2ObjID[parentUUID] - if !ok { - // could not look up parent info - return 0, false - } - return parentObjID, true -} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap/scan.go new file mode 100644 index 0000000..98ed097 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap/scan.go @@ -0,0 +1,73 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package uuidmap + +import ( + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" + "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" +) + +func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) error { + if other, conflict := m[k]; conflict && other != v { + return fmt.Errorf("conflict: %s %v can't have both %v and %v", name, k, other, v) + } + m[k] = v + return nil +} + +func New() *UUIDMap { + ret := &UUIDMap{ + ObjID2UUID: make(map[btrfsprim.ObjID]btrfsprim.UUID), + UUID2ObjID: make(map[btrfsprim.UUID]btrfsprim.ObjID), + TreeParent: make(map[btrfsprim.ObjID]btrfsprim.UUID), + + SeenTrees: make(containers.Set[btrfsprim.ObjID]), + } + + // These 4 trees are mentioned directly in the superblock, so + // they are always seen. + ret.SeenTrees.Insert(btrfsprim.ROOT_TREE_OBJECTID) + ret.SeenTrees.Insert(btrfsprim.CHUNK_TREE_OBJECTID) + ret.SeenTrees.Insert(btrfsprim.TREE_LOG_OBJECTID) + ret.SeenTrees.Insert(btrfsprim.BLOCK_GROUP_TREE_OBJECTID) + + return ret +} + +func (m *UUIDMap) InsertNode(nodeRef *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error { + for _, item := range nodeRef.Data.BodyLeaf { + switch itemBody := item.Body.(type) { + case btrfsitem.Root: + if err := maybeSet("ObjID2UUID", m.ObjID2UUID, item.Key.ObjectID, itemBody.UUID); err != nil { + return err + } + if itemBody.UUID != (btrfsprim.UUID{}) { + if err := maybeSet("UUID2ObjID", m.UUID2ObjID, itemBody.UUID, item.Key.ObjectID); err != nil { + return err + } + } + if err := maybeSet("ParentUUID", m.TreeParent, item.Key.ObjectID, itemBody.ParentUUID); err != nil { + return err + } + m.SeenTrees.Insert(item.Key.ObjectID) + case btrfsitem.UUIDMap: + uuid := btrfsitem.KeyToUUID(item.Key) + if err := maybeSet("ObjID2UUID", m.ObjID2UUID, itemBody.ObjID, uuid); err != nil { + return err + } + if err := maybeSet("UUID2ObjID", m.UUID2ObjID, uuid, itemBody.ObjID); err != nil { + return err + } + } + } + m.SeenTrees.Insert(nodeRef.Data.Head.Owner) + return nil +} diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap/uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap/uuidmap.go new file mode 100644 index 0000000..32a34d1 --- /dev/null +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap/uuidmap.go @@ -0,0 +1,55 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package uuidmap + +import ( + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" +) + +type UUIDMap struct { + ObjID2UUID map[btrfsprim.ObjID]btrfsprim.UUID + UUID2ObjID map[btrfsprim.UUID]btrfsprim.ObjID + TreeParent map[btrfsprim.ObjID]btrfsprim.UUID + + SeenTrees containers.Set[btrfsprim.ObjID] +} + +func (m UUIDMap) MissingRootItems() containers.Set[btrfsprim.ObjID] { + missing := make(containers.Set[btrfsprim.ObjID]) + for treeID := range m.SeenTrees { + if _, ok := m.ObjID2UUID[treeID]; !ok && treeID != btrfsprim.ROOT_TREE_OBJECTID { + missing.Insert(treeID) + continue + } + if _, ok := m.TreeParent[treeID]; !ok && treeID >= btrfsprim.FIRST_FREE_OBJECTID && treeID <= btrfsprim.LAST_FREE_OBJECTID { + missing.Insert(treeID) + } + } + return missing +} + +// ParentTree implements btrfstree.NodeFile. +func (m UUIDMap) ParentTree(tree btrfsprim.ObjID) (btrfsprim.ObjID, bool) { + if tree < btrfsprim.FIRST_FREE_OBJECTID || tree > btrfsprim.LAST_FREE_OBJECTID { + // no parent + return 0, true + } + parentUUID, ok := m.TreeParent[tree] + if !ok { + // could not look up parent info + return 0, false + } + if parentUUID == (btrfsprim.UUID{}) { + // no parent + return 0, true + } + parentObjID, ok := m.UUID2ObjID[parentUUID] + if !ok { + // could not look up parent info + return 0, false + } + return parentObjID, true +} -- cgit v1.2.3-2-g168b From e141c95dc00d261de788b0d35e5e5527a0a308ba Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 29 Nov 2022 14:54:37 -0700 Subject: rebuildnodes: wip: Implement all the rebuildCallbacks functions --- .../btrfsinspect/rebuildnodes/rebuild.go | 296 ++++++++++++++++++++- 1 file changed, 290 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 5a28008..92fb3ad 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -6,25 +6,33 @@ package rebuildnodes import ( "context" + "fmt" "github.com/datawire/dlib/dlog" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" "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/btrfsprogs/btrfsinspect" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildmappings" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" "git.lukeshu.com/btrfs-progs-ng/lib/containers" ) type Rebuilder struct { + raw *btrfs.FS inner interface { btrfstree.TreeOperator Augment(treeID btrfsprim.ObjID, nodeAddr btrfsvol.LogicalAddr) ([]btrfsprim.Key, error) } + sb btrfstree.Superblock + graph graph.Graph + csums containers.RBTree[containers.NativeOrdered[btrfsvol.LogicalAddr], btrfsinspect.SysExtentCSum] orphans containers.Set[btrfsvol.LogicalAddr] leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] key2leaf containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr] @@ -44,6 +52,12 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec return nil, err } + dlog.Info(ctx, "Indexing checksums...") + csums, _ := rebuildmappings.ExtractLogicalSums(ctx, nodeScanResults) + if csums == nil { + csums = new(containers.RBTree[containers.NativeOrdered[btrfsvol.LogicalAddr], btrfsinspect.SysExtentCSum]) + } + dlog.Info(ctx, "Indexing orphans...") orphans, leaf2orphans, key2leaf, err := indexOrphans(fs, *sb, *scanData.nodeGraph) if err != nil { @@ -52,8 +66,12 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec dlog.Info(ctx, "Rebuilding node tree...") o := &Rebuilder{ + raw: fs, inner: btrfsutil.NewBrokenTrees(ctx, fs), + sb: *sb, + graph: *scanData.nodeGraph, + csums: *csums, orphans: orphans, leaf2orphans: leaf2orphans, key2leaf: *key2leaf, @@ -74,34 +92,300 @@ func (o *Rebuilder) rebuild(ctx context.Context) error { return nil } +func (o *Rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, choices containers.Set[btrfsvol.LogicalAddr]) { + // TODO +} + // err implements rebuildCallbacks. func (o *Rebuilder) err(ctx context.Context, e error) { - // TODO + dlog.Errorf(ctx, "rebuild error: %v", e) } // want implements rebuildCallbacks. func (o *Rebuilder) want(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) { - // TODO + // check if we already have it + + tgt := btrfsprim.Key{ + ObjectID: objID, + ItemType: typ, + } + if _, err := o.inner.TreeSearch(treeID, func(key btrfsprim.Key, _ uint32) int { + key.Offset = 0 + return tgt.Cmp(key) + }); err == nil { + return + } + + // OK, we need to insert it + + wants := make(containers.Set[btrfsvol.LogicalAddr]) + o.key2leaf.Subrange( + func(k keyAndTree, _ btrfsvol.LogicalAddr) int { k.Key.Offset = 0; return tgt.Cmp(k.Key) }, + func(_ keyAndTree, v btrfsvol.LogicalAddr) bool { + wants.InsertFrom(o.leaf2orphans[v]) + return true + }) + o.wantAugment(ctx, treeID, wants) } // wantOff implements rebuildCallbacks. func (o *Rebuilder) wantOff(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) { - // TODO + // check if we already have it + + tgt := btrfsprim.Key{ + ObjectID: objID, + ItemType: typ, + Offset: off, + } + if _, err := o.inner.TreeLookup(treeID, tgt); err == nil { + return + } + + // OK, we need to insert it + + wants := make(containers.Set[btrfsvol.LogicalAddr]) + o.key2leaf.Subrange( + func(k keyAndTree, _ btrfsvol.LogicalAddr) int { return tgt.Cmp(k.Key) }, + func(_ keyAndTree, v btrfsvol.LogicalAddr) bool { + wants.InsertFrom(o.leaf2orphans[v]) + return true + }) + o.wantAugment(ctx, treeID, wants) } // wantFunc implements rebuildCallbacks. func (o *Rebuilder) wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(btrfsitem.Item) bool) { - // TODO + // check if we already have it + + tgt := btrfsprim.Key{ + ObjectID: objID, + ItemType: typ, + } + items, _ := o.inner.TreeSearchAll(treeID, func(key btrfsprim.Key, _ uint32) int { + key.Offset = 0 + return tgt.Cmp(key) + }) + for _, item := range items { + if fn(item.Body) { + return + } + } + + // OK, we need to insert it + + wants := make(containers.Set[btrfsvol.LogicalAddr]) + o.key2leaf.Subrange( + func(k keyAndTree, _ btrfsvol.LogicalAddr) int { k.Key.Offset = 0; return tgt.Cmp(k.Key) }, + func(k keyAndTree, v btrfsvol.LogicalAddr) bool { + nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](o.raw, o.sb, v, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: v}, + Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: o.graph.Nodes[v].Generation}, + }) + if err != nil { + o.err(ctx, err) + return true + } + for _, item := range nodeRef.Data.BodyLeaf { + if k.Key == item.Key && fn(item.Body) { + wants.InsertFrom(o.leaf2orphans[v]) + } + } + return true + }) + o.wantAugment(ctx, treeID, wants) } // func implements rebuildCallbacks. // // interval is [beg, end) func (o *Rebuilder) wantCSum(ctx context.Context, beg, end btrfsvol.LogicalAddr) { - // TODO + for beg < end { + // check if we already have it + if run, err := btrfs.LookupCSum(o.inner, o.sb.ChecksumType, beg); err == nil { + // we already have it + beg = run.Addr.Add(run.Size()) + } else { + // we need to insert it + rbNode := o.csums.Search(func(item btrfsinspect.SysExtentCSum) int { + switch { + case item.Sums.Addr > beg: + return -1 + case item.Sums.Addr.Add(item.Sums.Size()) <= beg: + return 1 + default: + return 0 + } + + }) + if rbNode == nil { + o.err(ctx, fmt.Errorf("could not find csum for laddr=%v", beg)) + beg += btrfssum.BlockSize + continue + } + run := rbNode.Value.Sums + key := keyAndTree{ + Key: rbNode.Value.Key, + TreeID: btrfsprim.CSUM_TREE_OBJECTID, + } + leaf, ok := o.key2leaf.Load(key) + if !ok { + panic(fmt.Errorf("no orphan contains %v", key.Key)) + } + o.wantAugment(ctx, key.TreeID, o.leaf2orphans[leaf]) + + beg = run.Addr.Add(run.Size()) + } + } } // wantFileExt implements rebuildCallbacks. func (o *Rebuilder) wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino btrfsprim.ObjID, size int64) { - // TODO + min := btrfsprim.Key{ + ObjectID: ino, + ItemType: btrfsitem.EXTENT_DATA_KEY, + Offset: 0, + } + max := btrfsprim.Key{ + ObjectID: ino, + ItemType: btrfsitem.EXTENT_DATA_KEY, + Offset: uint64(size - 1), + } + exts, err := o.inner.TreeSearchAll(treeID, func(key btrfsprim.Key, _ uint32) int { + switch { + case min.Cmp(key) < 0: + return 1 + case max.Cmp(key) > 0: + return -1 + default: + return 0 + } + }) + if err != nil { + o.err(ctx, err) + return + } + + type gap struct { + // range is [Beg,End) + Beg, End int64 + } + gaps := &containers.RBTree[containers.NativeOrdered[int64], gap]{ + KeyFn: func(gap gap) containers.NativeOrdered[int64] { + return containers.NativeOrdered[int64]{Val: gap.Beg} + }, + } + gaps.Insert(gap{ + Beg: 0, + End: size, + }) + for _, ext := range exts { + extBody, ok := ext.Body.(btrfsitem.FileExtent) + if !ok { + o.err(ctx, fmt.Errorf("EXTENT_DATA is %T", ext.Body)) + continue + } + extBeg := int64(ext.Key.Offset) + extSize, err := extBody.Size() + if err != nil { + o.err(ctx, err) + continue + } + extEnd := extBeg + extSize + overlappingGaps := gaps.SearchRange(func(gap gap) int { + switch { + case gap.End <= extBeg: + return 1 + case extEnd <= gap.Beg: + return -1 + default: + return 0 + } + }) + if len(overlappingGaps) == 0 { + continue + } + beg := overlappingGaps[0].Beg + end := overlappingGaps[len(overlappingGaps)-1].End + for _, gap := range overlappingGaps { + gaps.Delete(containers.NativeOrdered[int64]{Val: gap.Beg}) + } + if beg < extBeg { + gaps.Insert(gap{ + Beg: beg, + End: extBeg, + }) + } + if end > extEnd { + gaps.Insert(gap{ + Beg: extEnd, + End: end, + }) + } + } + if err := gaps.Walk(func(rbNode *containers.RBNode[gap]) error { + gap := rbNode.Value + min := btrfsprim.Key{ + ObjectID: ino, + ItemType: btrfsitem.EXTENT_DATA_KEY, + Offset: 0, + } + max := btrfsprim.Key{ + ObjectID: ino, + ItemType: btrfsitem.EXTENT_DATA_KEY, + Offset: uint64(gap.End - 1), + } + wants := make(containers.Set[btrfsvol.LogicalAddr]) + o.key2leaf.Subrange( + func(k keyAndTree, _ btrfsvol.LogicalAddr) int { + switch { + case min.Cmp(k.Key) < 0: + return 1 + case max.Cmp(k.Key) > 0: + return -1 + default: + return 0 + } + }, + func(k keyAndTree, v btrfsvol.LogicalAddr) bool { + nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](o.raw, o.sb, v, btrfstree.NodeExpectations{ + LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: v}, + Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: o.graph.Nodes[v].Generation}, + }) + if err != nil { + o.err(ctx, err) + return true + } + for _, item := range nodeRef.Data.BodyLeaf { + if k.Key == item.Key { + itemBeg := int64(item.Key.Offset) + itemBody, ok := item.Body.(btrfsitem.FileExtent) + if !ok { + o.err(ctx, fmt.Errorf("EXTENT_DATA is %T", item.Body)) + continue + } + itemSize, err := itemBody.Size() + if err != nil { + o.err(ctx, err) + continue + } + itemEnd := itemBeg + itemSize + // We're being and "wanting" any extent that has any overlap with the + // gap. But maybe instead we sould only want extents that are + // *entirely* within the gap. I'll have to run it on real filesystems + // to see what works better. + // + // TODO(lukeshu): Re-evaluate whether being greedy here is the right + // thing. + if itemEnd > gap.Beg && itemBeg < gap.End { + wants.InsertFrom(o.leaf2orphans[v]) + } + } + } + return true + }) + o.wantAugment(ctx, treeID, wants) + return nil + }); err != nil { + o.err(ctx, err) + } } -- cgit v1.2.3-2-g168b From 61c06798430e68acc748a6a681a88dda9d5e203d Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 10 Dec 2022 23:51:41 -0700 Subject: rebuildnodes: wip: Implement the main loop --- .../btrfsinspect/rebuildnodes/rebuild.go | 98 +++++++++++++++++++++- 1 file changed, 95 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 92fb3ad..c5f51ca 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -19,8 +19,10 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildmappings" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/graph" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap" "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsutil" "git.lukeshu.com/btrfs-progs-ng/lib/containers" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) type Rebuilder struct { @@ -32,12 +34,15 @@ type Rebuilder struct { sb btrfstree.Superblock graph graph.Graph + uuidMap uuidmap.UUIDMap csums containers.RBTree[containers.NativeOrdered[btrfsvol.LogicalAddr], btrfsinspect.SysExtentCSum] orphans containers.Set[btrfsvol.LogicalAddr] leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr] key2leaf containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr] augments map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr] + + pendingAugments map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int } func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspect.ScanDevicesResult) (map[btrfsprim.ObjID]containers.Set[btrfsvol.LogicalAddr], error) { @@ -71,6 +76,7 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec sb: *sb, graph: *scanData.nodeGraph, + uuidMap: *scanData.uuidMap, csums: *csums, orphans: orphans, leaf2orphans: leaf2orphans, @@ -86,16 +92,102 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec } func (o *Rebuilder) rebuild(ctx context.Context) error { + o.pendingAugments = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int) + btrfsutil.WalkAllTrees(ctx, o.inner, btrfsutil.WalkAllTreesHandler{ + Err: func(*btrfsutil.WalkError) {}, + TreeWalkHandler: btrfstree.TreeWalkHandler{ + Item: func(path btrfstree.TreePath, item btrfstree.Item) error { + handleItem(o, ctx, path[0].FromTree, item) + return nil + }, + }, + }) + for len(o.pendingAugments) > 0 { + // Apply the augments, keeping track of what keys are added to what tree. + newKeys := make(map[btrfsprim.ObjID][]btrfsprim.Key) + for _, treeID := range maps.SortedKeys(o.pendingAugments) { + treeAugments := o.resolveTreeAugments(ctx, o.pendingAugments[treeID]) + for _, nodeAddr := range maps.SortedKeys(treeAugments) { + added, err := o.inner.Augment(treeID, nodeAddr) + if err != nil { + o.err(ctx, err) + continue + } + newKeys[treeID] = append(newKeys[treeID], added...) + + set := o.augments[treeID] + if set == nil { + set = make(containers.Set[btrfsvol.LogicalAddr]) + o.augments[treeID] = set + } + set.Insert(nodeAddr) + } + } + // Clear the list of pending augments. + o.pendingAugments = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int) + // Call handleItem() for each of the added keys. + for _, treeID := range maps.SortedKeys(newKeys) { + for _, key := range newKeys[treeID] { + item, err := o.inner.TreeLookup(treeID, key) + if err != nil { + o.err(ctx, err) + continue + } + handleItem(o, ctx, treeID, item) + } + } + } + return nil +} + +func (o *Rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances []map[btrfsvol.LogicalAddr]int) containers.Set[btrfsvol.LogicalAddr] { // TODO - //btrfsutil.WalkAllTrees(ctx, o.inner) - handleItem(o, ctx, 0, btrfstree.Item{}) return nil } +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +// _NodeFile is a subset of btrfstree.NodeFile. +type _NodeFile interface { + ParentTree(btrfsprim.ObjID) (btrfsprim.ObjID, bool) +} + +func treeDistance(fs _NodeFile, tree, leaf btrfsprim.ObjID) (int, bool) { + dist := 0 + for { + if tree == leaf { + return dist, true + } + + parentTree, ok := fs.ParentTree(tree) + if !ok { + // Failed to look up parent info. + return 0, false + } + if parentTree == 0 { + // End of the line. + return 0, false + } + + tree = parentTree + dist++ + } +} + func (o *Rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, choices containers.Set[btrfsvol.LogicalAddr]) { - // TODO + choicesWithDist := make(map[btrfsvol.LogicalAddr]int) + for choice := range choices { + if dist, ok := treeDistance(o.uuidMap, treeID, o.graph.Nodes[choice].Owner); ok { + choicesWithDist[choice] = dist + } + } + if len(choicesWithDist) > 0 { + o.pendingAugments[treeID] = append(o.pendingAugments[treeID], choicesWithDist) + } } +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + // err implements rebuildCallbacks. func (o *Rebuilder) err(ctx context.Context, e error) { dlog.Errorf(ctx, "rebuild error: %v", e) -- cgit v1.2.3-2-g168b From 69464c7bb48872c3403e208c492d2b3e1d87812a Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 11 Dec 2022 20:34:30 -0700 Subject: rebuildnodes: wip: Implement resolveTreeAugments --- .../btrfsinspect/rebuildnodes/rebuild.go | 109 ++++++++++++++++++++- 1 file changed, 107 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index c5f51ca..be2834b 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -7,6 +7,7 @@ package rebuildnodes import ( "context" "fmt" + "sort" "github.com/datawire/dlib/dlog" @@ -141,8 +142,112 @@ func (o *Rebuilder) rebuild(ctx context.Context) error { } func (o *Rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances []map[btrfsvol.LogicalAddr]int) containers.Set[btrfsvol.LogicalAddr] { - // TODO - return nil + distances := make(map[btrfsvol.LogicalAddr]int) + generations := make(map[btrfsvol.LogicalAddr]btrfsprim.Generation) + lists := make([]containers.Set[btrfsvol.LogicalAddr], len(listsWithDistances)) + for i, listWithDistances := range listsWithDistances { + lists[i] = make(containers.Set[btrfsvol.LogicalAddr], len(listWithDistances)) + for item, dist := range listWithDistances { + lists[i].Insert(item) + distances[item] = dist + generations[item] = o.graph.Nodes[item].Generation + } + } + + // Define an algorithm that takes several lists of items, and returns a + // set of those items such that each input list contains zero or one of + // the items from your return set. The same item may appear in multiple + // of the input lists. + // + // > Example 1: Given the input lists + // > + // > 0: [A, B] + // > 2: [A, C] + // > + // > legal solutions would be `[]`, `[A]`, `[B]`, `[C]`, or `[B, C]`. It + // > would not be legal to return `[A, B]` or `[A, C]`. + // + // > Example 2: Given the input lists + // > + // > 1: [A, B] + // > 2: [A] + // > 3: [B] + // > + // > legal solution woudl be `[]`, `[A]` or `[B]`. It would not be legal + // > to return `[A, B]`. + // + // The algorithm should optimize for the following goals: + // + // - We prefer that each input list have an item in the return set. + // + // > In Example 1, while `[]`, `[B]`, and `[C]` are permissable + // > solutions, they are not optimal, because one or both of the input + // > lists are not represented. + // > + // > It may be the case that it is not possible to represent all lists + // > in the result; in Example 2, either list 2 or list 3 must be + // > unrepresented. + // + // - Each item has a non-negative scalar "distance" score, we prefer + // lower distances. Distance scores are comparable; 0 is preferred, + // and a distance of 4 is twice as bad as a distance of 2. + // + // - Each item has a "generation" score, we prefer higher generations. + // Generation scores should not be treated as a linear scale; the + // magnitude of deltas is meaningless; only the sign of a delta is + // meaningful. + // + // > So it would be wrong to say something like + // > + // > desirability = (-a*distance) + (b*generation) // for some constants `a` and `b` + // > + // > because `generation` can't be used that way + // + // - We prefer items that appear in more lists over items that appear in + // fewer lists. + // + // The relative priority of these 4 goals is undefined; preferrably the + // algorithm should be defined in a way that makes it easy to adjust the + // relative priorities. + + ret := make(containers.Set[btrfsvol.LogicalAddr]) + illegal := make(containers.Set[btrfsvol.LogicalAddr]) // cannot-be-accepted and already-accepted + accept := func(item btrfsvol.LogicalAddr) { + ret.Insert(item) + for _, list := range lists { + if list.Has(item) { + illegal.InsertFrom(list) + } + } + } + + counts := make(map[btrfsvol.LogicalAddr]int) + for _, list := range lists { + for item := range list { + counts[item] = counts[item] + 1 + } + } + + sortedItems := maps.Keys(distances) + sort.Slice(sortedItems, func(i, j int) bool { + iItem, jItem := sortedItems[i], sortedItems[j] + if counts[iItem] != counts[jItem] { + return counts[iItem] > counts[jItem] // reverse this check; higher counts should sort lower + } + if distances[iItem] != distances[jItem] { + return distances[iItem] < distances[jItem] + } + if generations[iItem] != generations[jItem] { + return generations[iItem] > generations[jItem] // reverse this check; higher generations should sort lower + } + return iItem < jItem // laddr is as good a tiebreaker as anything + }) + for _, item := range sortedItems { + if !illegal.Has(item) { + accept(item) + } + } + return ret } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -- cgit v1.2.3-2-g168b From 0ba5538b7faba51474c7fd4c5512f795e05a787c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sun, 11 Dec 2022 22:29:05 -0700 Subject: rebuildnodes: Improve logging --- .../btrfsinspect/rebuildnodes/orphans.go | 43 ++++++++++++++++++++-- .../btrfsinspect/rebuildnodes/rebuild.go | 14 ++++++- lib/containers/set.go | 13 +++++++ 3 files changed, 66 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go index 70bd128..55cf95b 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -5,12 +5,17 @@ package rebuildnodes import ( + "context" + + "github.com/datawire/dlib/dlog" + "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/btrfsprogs/btrfsinspect/rebuildnodes/graph" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" + "git.lukeshu.com/btrfs-progs-ng/lib/maps" ) func listRoots(graph graph.Graph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { @@ -49,12 +54,13 @@ func (a keyAndTree) Cmp(b keyAndTree) int { return containers.NativeCmp(a.TreeID, b.TreeID) } -func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph graph.Graph) ( +func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph graph.Graph) ( orphans containers.Set[btrfsvol.LogicalAddr], leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], key2leaf *containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr], err error, ) { + dlog.Info(ctx, "... counting orphans") orphans = make(containers.Set[btrfsvol.LogicalAddr]) for node := range graph.Nodes { if len(graph.EdgesTo[node]) == 0 { @@ -64,7 +70,22 @@ func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, leaf2orphans = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) visited := make(containers.Set[btrfsvol.LogicalAddr]) - for orphan := range orphans { + + lastPct, lastVisited, lastLeafs := -1, 0, 0 + total := len(orphans) + done := 0 + progress := func() { + pct := int(100 * float64(done) / float64(total)) + if pct != lastPct || (len(visited) != lastVisited && len(visited)%500 == 0) || len(leaf2orphans) != lastLeafs || done == total { + dlog.Infof(ctx, "... crawling orphans %v%% (%v/%v); visited %d nodes, found %d leaf nodes", + pct, done, total, len(visited), len(leaf2orphans)) + lastPct = pct + lastVisited = len(visited) + lastLeafs = len(leaf2orphans) + } + } + progress() + for _, orphan := range maps.SortedKeys(orphans) { walk(graph, orphan, func(node btrfsvol.LogicalAddr) bool { if visited.Has(node) { return false @@ -75,12 +96,26 @@ func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, leaf2orphans[node] = roots } } + progress() return true }) + done++ + progress() } key2leaf = new(containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr]) - for laddr := range leaf2orphans { + total = len(leaf2orphans) + done = 0 + progress = func() { + pct := int(100 * float64(done) / float64(total)) + if pct != lastPct || done == total { + dlog.Infof(ctx, "... reading leafs %v%% (%v/%v)", + pct, done, total) + lastPct = pct + } + } + progress() + for _, laddr := range maps.SortedKeys(leaf2orphans) { nodeRef, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, sb, laddr, btrfstree.NodeExpectations{ LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr}, Level: containers.Optional[uint8]{OK: true, Val: 0}, @@ -98,6 +133,8 @@ func indexOrphans(fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, key2leaf.Store(k, laddr) } } + done++ + progress() } return orphans, leaf2orphans, key2leaf, nil } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index be2834b..5dc4fa6 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -65,7 +65,7 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec } dlog.Info(ctx, "Indexing orphans...") - orphans, leaf2orphans, key2leaf, err := indexOrphans(fs, *sb, *scanData.nodeGraph) + orphans, leaf2orphans, key2leaf, err := indexOrphans(ctx, fs, *sb, *scanData.nodeGraph) if err != nil { return nil, err } @@ -93,6 +93,8 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec } func (o *Rebuilder) rebuild(ctx context.Context) error { + passNum := 0 + dlog.Infof(ctx, "... pass %d: scanning for implied items", passNum) o.pendingAugments = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int) btrfsutil.WalkAllTrees(ctx, o.inner, btrfsutil.WalkAllTreesHandler{ Err: func(*btrfsutil.WalkError) {}, @@ -105,8 +107,10 @@ func (o *Rebuilder) rebuild(ctx context.Context) error { }) for len(o.pendingAugments) > 0 { // Apply the augments, keeping track of what keys are added to what tree. + dlog.Infof(ctx, "... pass %d: augmenting trees to add implied items", passNum) newKeys := make(map[btrfsprim.ObjID][]btrfsprim.Key) for _, treeID := range maps.SortedKeys(o.pendingAugments) { + dlog.Infof(ctx, "... ... augmenting tree %v:", treeID) treeAugments := o.resolveTreeAugments(ctx, o.pendingAugments[treeID]) for _, nodeAddr := range maps.SortedKeys(treeAugments) { added, err := o.inner.Augment(treeID, nodeAddr) @@ -126,7 +130,9 @@ func (o *Rebuilder) rebuild(ctx context.Context) error { } // Clear the list of pending augments. o.pendingAugments = make(map[btrfsprim.ObjID][]map[btrfsvol.LogicalAddr]int) + passNum++ // Call handleItem() for each of the added keys. + dlog.Infof(ctx, "... pass %d: scanning for implied items", passNum) for _, treeID := range maps.SortedKeys(newKeys) { for _, key := range newKeys[treeID] { item, err := o.inner.TreeLookup(treeID, key) @@ -247,6 +253,11 @@ func (o *Rebuilder) resolveTreeAugments(ctx context.Context, listsWithDistances accept(item) } } + + for i, list := range lists { + dlog.Infof(ctx, "... ... ... %d: %v: %v", i, list.Intersection(ret).TakeOne(), maps.SortedKeys(list)) + } + return ret } @@ -287,6 +298,7 @@ func (o *Rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, cho } } if len(choicesWithDist) > 0 { + dlog.Infof(ctx, "augment(tree=%v): %v", treeID, maps.SortedKeys(choicesWithDist)) o.pendingAugments[treeID] = append(o.pendingAugments[treeID], choicesWithDist) } } diff --git a/lib/containers/set.go b/lib/containers/set.go index d3f8ca7..67ba7ac 100644 --- a/lib/containers/set.go +++ b/lib/containers/set.go @@ -150,3 +150,16 @@ func (small Set[T]) HasAny(big Set[T]) bool { } return false } + +func (small Set[T]) Intersection(big Set[T]) Set[T] { + if len(big) < len(small) { + small, big = big, small + } + ret := make(Set[T]) + for v := range small { + if _, ok := big[v]; ok { + ret.Insert(v) + } + } + return ret +} -- cgit v1.2.3-2-g168b From ddc5ba0fa1a51636352e345d05cf8c6229d85535 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 13 Dec 2022 13:52:01 -0700 Subject: rebuildnodes: rebuild_graph.go: Audit for error handling --- .../btrfsinspect/rebuildnodes/rebuild_graph.go | 32 ++++++++++++++++------ 1 file changed, 24 insertions(+), 8 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go index 8247651..af8417a 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go @@ -85,6 +85,11 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, btrfsitem.NameHash(body.Name)) case btrfsitem.XATTR_ITEM_KEY: // nothing + default: + // This is a panic because the item decoder should not emit a + // btrfsitem.DirEntry for other item types without this code also being + // updated. + panic(fmt.Errorf("should not happen: DirEntry: unexpected ItemType=%v", item.Key.ItemType)) } // item-within-directory if body.Location != (btrfsprim.Key{}) { @@ -106,7 +111,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, body.Location.ObjectID, body.Location.ItemType) default: - o.err(ctx, fmt.Errorf("DirEntry: unexpected .Location.ItemType: %v", body.Location.ItemType)) + o.err(ctx, fmt.Errorf("DirEntry: unexpected .Location.ItemType=%v", body.Location.ItemType)) } } case btrfsitem.Empty: @@ -119,7 +124,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, // // kernel ever reads this, so who knows if it // // always gets updated correctly? //} - for _, ref := range body.Refs { + for i, ref := range body.Refs { switch refBody := ref.Body.(type) { case nil: // nothing @@ -137,7 +142,9 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, case btrfsitem.SharedDataRef: // nothing default: - panic("should not happen") + // This is a panic because the item decoder should not emit a new + // type to ref.Body without this code also being updated. + panic(fmt.Errorf("should not happen: Extent: unexpected .Refs[%d].Body type %T", i, refBody)) } } case btrfsitem.ExtentCSum: @@ -172,7 +179,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, roundDown(body.BodyExtent.DiskByteNr, btrfssum.BlockSize), roundUp(body.BodyExtent.DiskByteNr.Add(body.BodyExtent.DiskNumBytes), btrfssum.BlockSize)) default: - o.err(ctx, fmt.Errorf("FileExtent: unexpected body.Type: %v", body.Type)) + o.err(ctx, fmt.Errorf("FileExtent: unexpected body.Type=%v", body.Type)) } case btrfsitem.FreeSpaceBitmap: o.wantOff(dlog.WithField(ctx, "wants", "FreeSpaceInfo"), @@ -231,7 +238,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, uint64(ref.Index)) } case btrfsitem.Metadata: - for _, ref := range body.Refs { + for i, ref := range body.Refs { switch refBody := ref.Body.(type) { case nil: // nothing @@ -249,7 +256,9 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, case btrfsitem.SharedDataRef: // nothing default: - panic("should not happen") + // This is a panic because the item decoder should not emit a new + // type to ref.Body without this code also being updated. + panic(fmt.Errorf("should not happen: Metadata: unexpected .Refs[%d].Body type %T", i, refBody)) } } case btrfsitem.Root: @@ -273,7 +282,10 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, parent = btrfsprim.ObjID(item.Key.Offset) child = item.Key.ObjectID default: - panic("should not happen") + // This is a panic because the item decoder should not emit a + // btrfsitem.RootRef for other item types without this code also being + // updated. + panic(fmt.Errorf("should not happen: RootRef: unexpected ItemType=%v", item.Key.ItemType)) } // sibling o.wantOff(dlog.WithField(ctx, "wants", fmt.Sprintf("corresponding %v", otherType)), @@ -316,7 +328,11 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, btrfsprim.ROOT_TREE_OBJECTID, body.ObjID, btrfsitem.ROOT_ITEM_KEY) + case btrfsitem.Error: + o.err(ctx, fmt.Errorf("error decoding item: %w", body.Err)) default: - panic(fmt.Errorf("unsupported item type: %T", body)) + // This is a panic because the item decoder should not emit new types without this + // code also being updated. + panic(fmt.Errorf("should not happen: unexpected item type: %T", body)) } } -- cgit v1.2.3-2-g168b From 0dae1561100c68567ca79f9cc3a11f2d03019eb3 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 13 Dec 2022 22:43:45 -0700 Subject: rebuildnodes: rebuild.go: Audit error handling --- .../btrfsinspect/rebuildnodes/rebuild.go | 159 ++++++++++++--------- .../btrfsinspect/rebuildnodes/rebuild_graph.go | 8 +- 2 files changed, 93 insertions(+), 74 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go index 5dc4fa6..ef50653 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go @@ -92,6 +92,12 @@ func RebuildNodes(ctx context.Context, fs *btrfs.FS, nodeScanResults btrfsinspec return o.augments, nil } +func (o *Rebuilder) ioErr(ctx context.Context, err error) { + err = fmt.Errorf("should not happen: i/o error: %w", err) + dlog.Error(ctx, err) + panic(err) +} + func (o *Rebuilder) rebuild(ctx context.Context) error { passNum := 0 dlog.Infof(ctx, "... pass %d: scanning for implied items", passNum) @@ -115,7 +121,7 @@ func (o *Rebuilder) rebuild(ctx context.Context) error { for _, nodeAddr := range maps.SortedKeys(treeAugments) { added, err := o.inner.Augment(treeID, nodeAddr) if err != nil { - o.err(ctx, err) + dlog.Errorf(ctx, "error augmenting: %v", err) continue } newKeys[treeID] = append(newKeys[treeID], added...) @@ -137,8 +143,8 @@ func (o *Rebuilder) rebuild(ctx context.Context) error { for _, key := range newKeys[treeID] { item, err := o.inner.TreeLookup(treeID, key) if err != nil { - o.err(ctx, err) - continue + o.ioErr(ctx, fmt.Errorf("error looking up already-inserted item: tree=%v key=%v: %w", + treeID, key, err)) } handleItem(o, ctx, treeID, item) } @@ -297,17 +303,19 @@ func (o *Rebuilder) wantAugment(ctx context.Context, treeID btrfsprim.ObjID, cho choicesWithDist[choice] = dist } } - if len(choicesWithDist) > 0 { - dlog.Infof(ctx, "augment(tree=%v): %v", treeID, maps.SortedKeys(choicesWithDist)) - o.pendingAugments[treeID] = append(o.pendingAugments[treeID], choicesWithDist) + if len(choicesWithDist) == 0 { + dlog.Errorf(ctx, "augment(tree=%v): could not find wanted item", treeID) + return } + dlog.Infof(ctx, "augment(tree=%v): %v", treeID, maps.SortedKeys(choicesWithDist)) + o.pendingAugments[treeID] = append(o.pendingAugments[treeID], choicesWithDist) } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -// err implements rebuildCallbacks. -func (o *Rebuilder) err(ctx context.Context, e error) { - dlog.Errorf(ctx, "rebuild error: %v", e) +// fsErr implements rebuildCallbacks. +func (o *Rebuilder) fsErr(ctx context.Context, e error) { + dlog.Errorf(ctx, "filesystem error: %v", e) } // want implements rebuildCallbacks. @@ -327,6 +335,7 @@ func (o *Rebuilder) want(ctx context.Context, treeID btrfsprim.ObjID, objID btrf // OK, we need to insert it + ctx = dlog.WithField(ctx, "want_key", fmt.Sprintf("tree=%v key={%v %v ?}", treeID, objID, typ)) wants := make(containers.Set[btrfsvol.LogicalAddr]) o.key2leaf.Subrange( func(k keyAndTree, _ btrfsvol.LogicalAddr) int { k.Key.Offset = 0; return tgt.Cmp(k.Key) }, @@ -352,6 +361,7 @@ func (o *Rebuilder) wantOff(ctx context.Context, treeID btrfsprim.ObjID, objID b // OK, we need to insert it + ctx = dlog.WithField(ctx, "want_key", fmt.Sprintf("tree=%v key=%v", treeID, tgt)) wants := make(containers.Set[btrfsvol.LogicalAddr]) o.key2leaf.Subrange( func(k keyAndTree, _ btrfsvol.LogicalAddr) int { return tgt.Cmp(k.Key) }, @@ -382,6 +392,7 @@ func (o *Rebuilder) wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID // OK, we need to insert it + ctx = dlog.WithField(ctx, "want_key", fmt.Sprintf("tree=%v key=%v +func", treeID, tgt)) wants := make(containers.Set[btrfsvol.LogicalAddr]) o.key2leaf.Subrange( func(k keyAndTree, _ btrfsvol.LogicalAddr) int { k.Key.Offset = 0; return tgt.Cmp(k.Key) }, @@ -391,8 +402,7 @@ func (o *Rebuilder) wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: o.graph.Nodes[v].Generation}, }) if err != nil { - o.err(ctx, err) - return true + o.ioErr(ctx, err) } for _, item := range nodeRef.Data.BodyLeaf { if k.Key == item.Key && fn(item.Body) { @@ -415,6 +425,7 @@ func (o *Rebuilder) wantCSum(ctx context.Context, beg, end btrfsvol.LogicalAddr) beg = run.Addr.Add(run.Size()) } else { // we need to insert it + ctx := dlog.WithField(ctx, "want_key", fmt.Sprintf("csum for laddr=%v", beg)) rbNode := o.csums.Search(func(item btrfsinspect.SysExtentCSum) int { switch { case item.Sums.Addr > beg: @@ -427,7 +438,7 @@ func (o *Rebuilder) wantCSum(ctx context.Context, beg, end btrfsvol.LogicalAddr) }) if rbNode == nil { - o.err(ctx, fmt.Errorf("could not find csum for laddr=%v", beg)) + o.wantAugment(ctx, btrfsprim.CSUM_TREE_OBJECTID, nil) // log an error beg += btrfssum.BlockSize continue } @@ -438,7 +449,10 @@ func (o *Rebuilder) wantCSum(ctx context.Context, beg, end btrfsvol.LogicalAddr) } leaf, ok := o.key2leaf.Load(key) if !ok { - panic(fmt.Errorf("no orphan contains %v", key.Key)) + // This is a panic because if we found it in `o.csums` then it has + // to be in some Node, and if we didn't find it from + // btrfs.LookupCSum(), then that Node must be an orphan. + panic(fmt.Errorf("should not happen: no orphan contains %v", key.Key)) } o.wantAugment(ctx, key.TreeID, o.leaf2orphans[leaf]) @@ -459,7 +473,7 @@ func (o *Rebuilder) wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino ItemType: btrfsitem.EXTENT_DATA_KEY, Offset: uint64(size - 1), } - exts, err := o.inner.TreeSearchAll(treeID, func(key btrfsprim.Key, _ uint32) int { + exts, _ := o.inner.TreeSearchAll(treeID, func(key btrfsprim.Key, _ uint32) int { switch { case min.Cmp(key) < 0: return 1 @@ -469,10 +483,6 @@ func (o *Rebuilder) wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino return 0 } }) - if err != nil { - o.err(ctx, err) - return - } type gap struct { // range is [Beg,End) @@ -488,50 +498,55 @@ func (o *Rebuilder) wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino End: size, }) for _, ext := range exts { - extBody, ok := ext.Body.(btrfsitem.FileExtent) - if !ok { - o.err(ctx, fmt.Errorf("EXTENT_DATA is %T", ext.Body)) - continue - } - extBeg := int64(ext.Key.Offset) - extSize, err := extBody.Size() - if err != nil { - o.err(ctx, err) - continue - } - extEnd := extBeg + extSize - overlappingGaps := gaps.SearchRange(func(gap gap) int { - switch { - case gap.End <= extBeg: - return 1 - case extEnd <= gap.Beg: - return -1 - default: - return 0 + switch extBody := ext.Body.(type) { + case btrfsitem.FileExtent: + extBeg := int64(ext.Key.Offset) + extSize, err := extBody.Size() + if err != nil { + o.fsErr(ctx, fmt.Errorf("FileExtent: tree=%v key=%v: %w", treeID, ext.Key, err)) + continue } - }) - if len(overlappingGaps) == 0 { - continue - } - beg := overlappingGaps[0].Beg - end := overlappingGaps[len(overlappingGaps)-1].End - for _, gap := range overlappingGaps { - gaps.Delete(containers.NativeOrdered[int64]{Val: gap.Beg}) - } - if beg < extBeg { - gaps.Insert(gap{ - Beg: beg, - End: extBeg, - }) - } - if end > extEnd { - gaps.Insert(gap{ - Beg: extEnd, - End: end, + extEnd := extBeg + extSize + overlappingGaps := gaps.SearchRange(func(gap gap) int { + switch { + case gap.End <= extBeg: + return 1 + case extEnd <= gap.Beg: + return -1 + default: + return 0 + } }) + if len(overlappingGaps) == 0 { + continue + } + beg := overlappingGaps[0].Beg + end := overlappingGaps[len(overlappingGaps)-1].End + for _, gap := range overlappingGaps { + gaps.Delete(containers.NativeOrdered[int64]{Val: gap.Beg}) + } + if beg < extBeg { + gaps.Insert(gap{ + Beg: beg, + End: extBeg, + }) + } + if end > extEnd { + gaps.Insert(gap{ + Beg: extEnd, + End: end, + }) + } + case btrfsitem.Error: + o.fsErr(ctx, fmt.Errorf("error decoding item: tree=%v key=%v: %w", treeID, ext.Key, extBody.Err)) + default: + // This is a panic because the item decoder should not emit EXTENT_DATA + // items as anything but btrfsitem.FileExtent or btrfsitem.Error without + // this code also being updated. + panic(fmt.Errorf("should not happen: EXTENT_DATA item has unexpected type: %T", extBody)) } } - if err := gaps.Walk(func(rbNode *containers.RBNode[gap]) error { + _ = gaps.Walk(func(rbNode *containers.RBNode[gap]) error { gap := rbNode.Value min := btrfsprim.Key{ ObjectID: ino, @@ -543,6 +558,7 @@ func (o *Rebuilder) wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino ItemType: btrfsitem.EXTENT_DATA_KEY, Offset: uint64(gap.End - 1), } + ctx := dlog.WithField(ctx, "want_key", fmt.Sprintf("file extent for tree=%v inode=%v bytes [%v, %v)", treeID, ino, gap.Beg, gap.End)) wants := make(containers.Set[btrfsvol.LogicalAddr]) o.key2leaf.Subrange( func(k keyAndTree, _ btrfsvol.LogicalAddr) int { @@ -561,20 +577,18 @@ func (o *Rebuilder) wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino Generation: containers.Optional[btrfsprim.Generation]{OK: true, Val: o.graph.Nodes[v].Generation}, }) if err != nil { - o.err(ctx, err) - return true + o.ioErr(ctx, fmt.Errorf("error reading previously read node@%v: %w", v, err)) } for _, item := range nodeRef.Data.BodyLeaf { - if k.Key == item.Key { + if k.Key != item.Key { + continue + } + switch itemBody := item.Body.(type) { + case btrfsitem.FileExtent: itemBeg := int64(item.Key.Offset) - itemBody, ok := item.Body.(btrfsitem.FileExtent) - if !ok { - o.err(ctx, fmt.Errorf("EXTENT_DATA is %T", item.Body)) - continue - } itemSize, err := itemBody.Size() if err != nil { - o.err(ctx, err) + o.fsErr(ctx, fmt.Errorf("FileExtent: tree=%v key=%v: %w", treeID, item.Key, err)) continue } itemEnd := itemBeg + itemSize @@ -588,13 +602,18 @@ func (o *Rebuilder) wantFileExt(ctx context.Context, treeID btrfsprim.ObjID, ino if itemEnd > gap.Beg && itemBeg < gap.End { wants.InsertFrom(o.leaf2orphans[v]) } + case btrfsitem.Error: + o.fsErr(ctx, fmt.Errorf("error decoding item: tree=%v key=%v: %w", treeID, item.Key, itemBody.Err)) + default: + // This is a panic because the item decoder should not emit EXTENT_DATA + // items as anything but btrfsitem.FileExtent or btrfsitem.Error without + // this code also being updated. + panic(fmt.Errorf("should not happen: EXTENT_DATA item has unexpected type: %T", itemBody)) } } return true }) o.wantAugment(ctx, treeID, wants) return nil - }); err != nil { - o.err(ctx, err) - } + }) } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go index af8417a..976716d 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild_graph.go @@ -19,7 +19,7 @@ import ( ) type rebuildCallbacks interface { - err(ctx context.Context, e error) + fsErr(ctx context.Context, e error) want(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType) wantOff(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, off uint64) wantFunc(ctx context.Context, treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType, fn func(btrfsitem.Item) bool) @@ -111,7 +111,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, body.Location.ObjectID, body.Location.ItemType) default: - o.err(ctx, fmt.Errorf("DirEntry: unexpected .Location.ItemType=%v", body.Location.ItemType)) + o.fsErr(ctx, fmt.Errorf("DirEntry: unexpected .Location.ItemType=%v", body.Location.ItemType)) } } case btrfsitem.Empty: @@ -179,7 +179,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, roundDown(body.BodyExtent.DiskByteNr, btrfssum.BlockSize), roundUp(body.BodyExtent.DiskByteNr.Add(body.BodyExtent.DiskNumBytes), btrfssum.BlockSize)) default: - o.err(ctx, fmt.Errorf("FileExtent: unexpected body.Type=%v", body.Type)) + o.fsErr(ctx, fmt.Errorf("FileExtent: unexpected body.Type=%v", body.Type)) } case btrfsitem.FreeSpaceBitmap: o.wantOff(dlog.WithField(ctx, "wants", "FreeSpaceInfo"), @@ -329,7 +329,7 @@ func handleItem(o rebuildCallbacks, ctx context.Context, treeID btrfsprim.ObjID, body.ObjID, btrfsitem.ROOT_ITEM_KEY) case btrfsitem.Error: - o.err(ctx, fmt.Errorf("error decoding item: %w", body.Err)) + o.fsErr(ctx, fmt.Errorf("error decoding item: %w", body.Err)) default: // This is a panic because the item decoder should not emit new types without this // code also being updated. -- cgit v1.2.3-2-g168b From 88cad1bad73897b38de4c0628ace8c99efbc421c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 13 Dec 2022 23:12:37 -0700 Subject: containers: rbtree.go: Track size of the tree --- lib/containers/rbtree.go | 7 +++++++ lib/containers/rbtree_test.go | 1 + 2 files changed, 8 insertions(+) (limited to 'lib') diff --git a/lib/containers/rbtree.go b/lib/containers/rbtree.go index ab79a26..e2d8f8a 100644 --- a/lib/containers/rbtree.go +++ b/lib/containers/rbtree.go @@ -37,6 +37,11 @@ type RBTree[K Ordered[K], V any] struct { KeyFn func(V) K AttrFn func(*RBNode[V]) root *RBNode[V] + len int +} + +func (t *RBTree[K, V]) Len() int { + return t.len } func (t *RBTree[K, V]) Walk(fn func(*RBNode[V]) error) error { @@ -324,6 +329,7 @@ func (t *RBTree[K, V]) Insert(val V) { exact.Value = val return } + t.len++ node := &RBNode[V]{ Color: Red, @@ -394,6 +400,7 @@ func (t *RBTree[K, V]) Delete(key K) { if nodeToDelete == nil { return } + t.len-- // This is closely based on the algorithm presented in CLRS // 3e. diff --git a/lib/containers/rbtree_test.go b/lib/containers/rbtree_test.go index 9841d26..a487c52 100644 --- a/lib/containers/rbtree_test.go +++ b/lib/containers/rbtree_test.go @@ -112,6 +112,7 @@ func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet Set[K], return nil })) require.Equal(t, expectedOrder, actOrder) + require.Equal(t, tree.Len(), len(expectedSet)) } func FuzzRBTree(f *testing.F) { -- cgit v1.2.3-2-g168b From c93fbf4918b18606e50385c577ee9d6be701f370 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Tue, 13 Dec 2022 23:12:52 -0700 Subject: containers: intervaltree_test.go: Touch up logging --- lib/containers/intervaltree_test.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/containers/intervaltree_test.go b/lib/containers/intervaltree_test.go index 7a4689b..88c3003 100644 --- a/lib/containers/intervaltree_test.go +++ b/lib/containers/intervaltree_test.go @@ -56,7 +56,7 @@ func TestIntervalTree(t *testing.T) { tree.Insert(SimpleInterval{6, 10}) tree.Insert(SimpleInterval{19, 20}) - t.Log(tree.ASCIIArt()) + t.Log("\n" + tree.ASCIIArt()) // find intervals that touch [9,20] intervals := tree.SearchAll(func(k NativeOrdered[int]) int { -- cgit v1.2.3-2-g168b From 1674500388d1e0837103a870f0b96f1f1dab2206 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 14 Dec 2022 00:28:43 -0700 Subject: textui: Implement a reusable progress module To replace all of the ad-hoc hacks --- lib/textui/progress.go | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 88 insertions(+) create mode 100644 lib/textui/progress.go (limited to 'lib') diff --git a/lib/textui/progress.go b/lib/textui/progress.go new file mode 100644 index 0000000..7b3f63a --- /dev/null +++ b/lib/textui/progress.go @@ -0,0 +1,88 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package textui + +import ( + "context" + "fmt" + "sync/atomic" + "time" + + "github.com/datawire/dlib/dlog" +) + +type Stats interface { + comparable + fmt.Stringer +} + +type Progress[T Stats] struct { + ctx context.Context + lvl dlog.LogLevel + interval time.Duration + + cancel context.CancelFunc + done chan struct{} + + cur atomic.Value // Value[T] + oldStat T + oldLine string +} + +func NewProgress[T Stats](ctx context.Context, lvl dlog.LogLevel, interval time.Duration) *Progress[T] { + ctx, cancel := context.WithCancel(ctx) + ret := &Progress[T]{ + ctx: ctx, + lvl: lvl, + interval: interval, + + cancel: cancel, + done: make(chan struct{}), + } + return ret +} + +func (p *Progress[T]) Set(val T) { + if p.cur.Swap(val) == nil { + go p.run() + } +} + +func (p *Progress[T]) Done() { + p.cancel() + <-p.done +} + +func (p *Progress[T]) flush(force bool) { + cur := p.cur.Load().(T) + if !force && cur == p.oldStat { + return + } + defer func() { p.oldStat = cur }() + + line := cur.String() + if !force && line == p.oldLine { + return + } + defer func() { p.oldLine = line }() + + dlog.Log(p.ctx, p.lvl, line) +} + +func (p *Progress[T]) run() { + p.flush(true) + ticker := time.NewTicker(p.interval) + for { + select { + case <-p.ctx.Done(): + ticker.Stop() + p.flush(false) + close(p.done) + return + case <-ticker.C: + p.flush(false) + } + } +} -- cgit v1.2.3-2-g168b From 94a86a763157327ac969c98e19d7770db477a6a3 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 14 Dec 2022 16:19:07 -0700 Subject: Migrate existing progress logs to textui.NewProgress --- .../btrfsinspect/rebuildnodes/orphans.go | 60 ++++++++++++++++------ lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go | 26 +++++++--- lib/btrfsprogs/btrfsinspect/scandevices.go | 51 +++++++++++++----- 3 files changed, 100 insertions(+), 37 deletions(-) (limited to 'lib') diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go index 55cf95b..51313a9 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/orphans.go @@ -6,6 +6,8 @@ package rebuildnodes import ( "context" + "fmt" + "time" "github.com/datawire/dlib/dlog" @@ -16,6 +18,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/diskio" "git.lukeshu.com/btrfs-progs-ng/lib/maps" + "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) func listRoots(graph graph.Graph, leaf btrfsvol.LogicalAddr) containers.Set[btrfsvol.LogicalAddr] { @@ -54,6 +57,31 @@ func (a keyAndTree) Cmp(b keyAndTree) int { return containers.NativeCmp(a.TreeID, b.TreeID) } +type crawlStats struct { + DoneOrphans int + TotalOrphans int + + VisitedNodes int + FoundLeafs int +} + +func (s crawlStats) String() string { + return fmt.Sprintf("... crawling orphans %v%% (%v/%v); visited %d nodes, found %d leaf nodes", + int(100*float64(s.DoneOrphans)/float64(s.TotalOrphans)), + s.DoneOrphans, s.TotalOrphans, s.VisitedNodes, s.FoundLeafs) +} + +type readStats struct { + DoneLeafNodes int + TotalLeafNodes int +} + +func (s readStats) String() string { + return fmt.Sprintf("... reading leafs %v%% (%v/%v)", + int(100*float64(s.DoneLeafNodes)/float64(s.TotalLeafNodes)), + s.DoneLeafNodes, s.TotalLeafNodes) +} + func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb btrfstree.Superblock, graph graph.Graph) ( orphans containers.Set[btrfsvol.LogicalAddr], leaf2orphans map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr], @@ -71,18 +99,15 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb leaf2orphans = make(map[btrfsvol.LogicalAddr]containers.Set[btrfsvol.LogicalAddr]) visited := make(containers.Set[btrfsvol.LogicalAddr]) - lastPct, lastVisited, lastLeafs := -1, 0, 0 - total := len(orphans) done := 0 + crawlProgressWriter := textui.NewProgress[crawlStats](ctx, dlog.LogLevelInfo, 1*time.Second) progress := func() { - pct := int(100 * float64(done) / float64(total)) - if pct != lastPct || (len(visited) != lastVisited && len(visited)%500 == 0) || len(leaf2orphans) != lastLeafs || done == total { - dlog.Infof(ctx, "... crawling orphans %v%% (%v/%v); visited %d nodes, found %d leaf nodes", - pct, done, total, len(visited), len(leaf2orphans)) - lastPct = pct - lastVisited = len(visited) - lastLeafs = len(leaf2orphans) - } + crawlProgressWriter.Set(crawlStats{ + DoneOrphans: done, + TotalOrphans: len(orphans), + VisitedNodes: len(visited), + FoundLeafs: len(leaf2orphans), + }) } progress() for _, orphan := range maps.SortedKeys(orphans) { @@ -102,17 +127,16 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb done++ progress() } + crawlProgressWriter.Done() key2leaf = new(containers.SortedMap[keyAndTree, btrfsvol.LogicalAddr]) - total = len(leaf2orphans) done = 0 + readProgressWriter := textui.NewProgress[readStats](ctx, dlog.LogLevelInfo, 1*time.Second) progress = func() { - pct := int(100 * float64(done) / float64(total)) - if pct != lastPct || done == total { - dlog.Infof(ctx, "... reading leafs %v%% (%v/%v)", - pct, done, total) - lastPct = pct - } + readProgressWriter.Set(readStats{ + DoneLeafNodes: done, + TotalLeafNodes: len(leaf2orphans), + }) } progress() for _, laddr := range maps.SortedKeys(leaf2orphans) { @@ -136,5 +160,7 @@ func indexOrphans(ctx context.Context, fs diskio.File[btrfsvol.LogicalAddr], sb done++ progress() } + readProgressWriter.Done() + return orphans, leaf2orphans, key2leaf, nil } diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go index 9174035..3575534 100644 --- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go +++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/scan.go @@ -6,6 +6,8 @@ package rebuildnodes import ( "context" + "fmt" + "time" "github.com/datawire/dlib/dlog" @@ -17,6 +19,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect/rebuildnodes/uuidmap" "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/maps" + "git.lukeshu.com/btrfs-progs-ng/lib/textui" ) type scanResult struct { @@ -24,6 +27,16 @@ type scanResult struct { nodeGraph *graph.Graph } +type scanStats struct { + N, D int +} + +func (s scanStats) String() string { + return fmt.Sprintf("... %v%% (%v/%v)", + int(100*float64(s.N)/float64(s.D)), + s.N, s.D) +} + func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.ScanDevicesResult) (*scanResult, error) { dlog.Infof(ctx, "Reading node data from FS...") @@ -32,16 +45,11 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca return nil, err } - lastPct := -1 total := countNodes(scanResults) done := 0 + progressWriter := textui.NewProgress[scanStats](ctx, dlog.LogLevelInfo, 1*time.Second) progress := func(done, total int) { - pct := int(100 * float64(done) / float64(total)) - if pct != lastPct || done == total { - dlog.Infof(ctx, "... %v%% (%v/%v)", - pct, done, total) - lastPct = pct - } + progressWriter.Set(scanStats{N: done, D: total}) } ret := &scanResult{ @@ -69,10 +77,10 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca progress(done, total) } } - if done != total { panic("should not happen") } + progressWriter.Done() missing := ret.uuidMap.MissingRootItems() if len(missing) > 0 { @@ -81,10 +89,12 @@ func ScanDevices(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sca dlog.Info(ctx, "... done reading node data") + progressWriter = textui.NewProgress[scanStats](ctx, dlog.LogLevelInfo, 1*time.Second) dlog.Infof(ctx, "Checking keypointers for dead-ends...") if err := ret.nodeGraph.FinalCheck(fs, *sb, progress); err != nil { return nil, err } + progressWriter.Done() dlog.Info(ctx, "... done checking keypointers") return ret, nil diff --git a/lib/btrfsprogs/btrfsinspect/scandevices.go b/lib/btrfsprogs/btrfsinspect/scandevices.go index a382e17..4834826 100644 --- a/lib/btrfsprogs/btrfsinspect/scandevices.go +++ b/lib/btrfsprogs/btrfsinspect/scandevices.go @@ -10,6 +10,7 @@ import ( "fmt" "strings" "sync" + "time" "github.com/datawire/dlib/dgroup" "github.com/datawire/dlib/dlog" @@ -21,6 +22,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum" "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/textui" ) type ScanDevicesResult map[btrfsvol.DeviceID]ScanOneDeviceResult @@ -78,6 +80,31 @@ type SysExtentCSum struct { Sums btrfsitem.ExtentCSum } +type scanStats struct { + DevName string + DevSize btrfsvol.PhysicalAddr + + Pos btrfsvol.PhysicalAddr + + NumFoundNodes int + NumFoundChunks int + NumFoundBlockGroups int + NumFoundDevExtents int + NumFoundExtentCSums int +} + +func (s scanStats) String() string { + return fmt.Sprintf("... dev[%q] scanned %v%% (%d/%d) (found: %v nodes, %v chunks, %v block groups, %v dev extents, %v sum items)", + s.DevName, + int(100*float64(s.Pos)/float64(s.DevSize)), + s.Pos, s.DevSize, + s.NumFoundNodes, + s.NumFoundChunks, + s.NumFoundBlockGroups, + s.NumFoundDevExtents, + s.NumFoundExtentCSums) +} + // ScanOneDevice mostly mimics btrfs-progs // cmds/rescue-chunk-recover.c:scan_one_device(). func ScanOneDevice(ctx context.Context, dev *btrfs.Device, sb btrfstree.Superblock) (ScanOneDeviceResult, error) { @@ -103,19 +130,18 @@ func ScanOneDevice(ctx context.Context, dev *btrfs.Device, sb btrfstree.Superblo var sums strings.Builder sums.Grow(numSums * csumSize) - lastProgress := -1 + progressWriter := textui.NewProgress[scanStats](ctx, dlog.LogLevelInfo, 1*time.Second) progress := func(pos btrfsvol.PhysicalAddr) { - pct := int(100 * float64(pos) / float64(devSize)) - if pct != lastProgress || pos == devSize { - dlog.Infof(ctx, "... dev[%q] scanned %v%% (found: %v nodes, %v chunks, %v block groups, %v dev extents, %v sum items)", - dev.Name(), pct, - len(result.FoundNodes), - len(result.FoundChunks), - len(result.FoundBlockGroups), - len(result.FoundDevExtents), - len(result.FoundExtentCSums)) - lastProgress = pct - } + progressWriter.Set(scanStats{ + DevName: dev.Name(), + DevSize: devSize, + Pos: pos, + NumFoundNodes: len(result.FoundNodes), + NumFoundChunks: len(result.FoundChunks), + NumFoundBlockGroups: len(result.FoundBlockGroups), + NumFoundDevExtents: len(result.FoundDevExtents), + NumFoundExtentCSums: len(result.FoundExtentCSums), + }) } var minNextNode btrfsvol.PhysicalAddr @@ -212,6 +238,7 @@ func ScanOneDevice(ctx context.Context, dev *btrfs.Device, sb btrfstree.Superblo } } progress(devSize) + progressWriter.Done() result.Checksums = btrfssum.SumRun[btrfsvol.PhysicalAddr]{ ChecksumSize: csumSize, -- cgit v1.2.3-2-g168b