diff options
author | Luke Shumaker <lukeshu@lukeshu.com> | 2022-06-06 22:30:48 -0600 |
---|---|---|
committer | Luke Shumaker <lukeshu@lukeshu.com> | 2022-06-06 22:31:08 -0600 |
commit | 27cbe48c9ea535d12670d307a8dbbd5427a0ce1c (patch) | |
tree | b3bcfb4d9eae4f61ccf1a6d2a4b16bb300a7b5ce /cmd/btrfs-fsck | |
parent | 31f242bf094494054be15d9d56c85019287c520e (diff) |
fsck: organize, update item-gen code
Diffstat (limited to 'cmd/btrfs-fsck')
-rw-r--r-- | cmd/btrfs-fsck/main.go | 230 | ||||
-rw-r--r-- | cmd/btrfs-fsck/pass0.go | 19 | ||||
-rw-r--r-- | cmd/btrfs-fsck/pass1.go | 296 |
3 files changed, 319 insertions, 226 deletions
diff --git a/cmd/btrfs-fsck/main.go b/cmd/btrfs-fsck/main.go index 1147acf..2c52627 100644 --- a/cmd/btrfs-fsck/main.go +++ b/cmd/btrfs-fsck/main.go @@ -3,13 +3,9 @@ package main import ( "fmt" "os" - "sort" - "lukeshu.com/btrfs-tools/pkg/binstruct" "lukeshu.com/btrfs-tools/pkg/btrfs" "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" - "lukeshu.com/btrfs-tools/pkg/btrfsmisc" - "lukeshu.com/btrfs-tools/pkg/util" ) func main() { @@ -41,232 +37,14 @@ func Main(imgfilename string) (err error) { }, } - fmt.Printf("\nPass 0: superblocks...\n") /////////////////////////////////////////////////// - - superblock, err := fs.Superblock() + superblock, err := pass0(fs) if err != nil { - return fmt.Errorf("superblock: %w", err) - } - - fmt.Printf("\nPass 1: chunk mappings...\n") //////////////////////////////////////////////// - - fmt.Printf("Pass 1: ... initializing chunk mappings\n") - if err := fs.Init(); err != nil { - fmt.Printf("Pass 1: ... init chunk tree: error: %v\n", err) - } - - fmt.Printf("Pass 1: ... walking chunk tree\n") - visitedChunkNodes := make(map[btrfs.LogicalAddr]struct{}) - if err := fs.WalkTree(superblock.Data.ChunkTree, btrfs.WalkTreeHandler{ - Node: func(node *util.Ref[btrfs.LogicalAddr, btrfs.Node], err error) error { - if err != nil { - fmt.Printf("Pass 1: ... walk chunk tree: error: %v\n", err) - } - if node != nil { - visitedChunkNodes[node.Addr] = struct{}{} - } - return err - }, - }); err != nil { - fmt.Printf("Pass 1: ... walk chunk tree: error: %v\n", err) - } - - type reconstructedStripe struct { - Size uint64 - Dev *btrfs.Device - Addr btrfs.PhysicalAddr + return err } - reconstructedChunks := make(map[btrfs.LogicalAddr][]reconstructedStripe) - for _, dev := range fs.Devices { - fmt.Printf("Pass 1: ... dev[%q] scanning for nodes...\n", dev.Name()) - superblock, _ := dev.Superblock() - foundNodes := make(map[btrfs.LogicalAddr][]btrfs.PhysicalAddr) - var lostAndFoundChunks []btrfs.SysChunk - devSize, _ := dev.Size() - lastProgress := -1 - if err := btrfsmisc.ScanForNodes(dev, superblock.Data, func(nodeRef *util.Ref[btrfs.PhysicalAddr, btrfs.Node], err error) { - if err != nil { - fmt.Printf("Pass 1: ... dev[%q] error: %v\n", dev.Name(), err) - return - } - foundNodes[nodeRef.Data.Head.Addr] = append(foundNodes[nodeRef.Data.Head.Addr], nodeRef.Addr) - _, alreadyVisited := visitedChunkNodes[nodeRef.Data.Head.Addr] - if nodeRef.Data.Head.Owner == btrfs.CHUNK_TREE_OBJECTID && !alreadyVisited { - for i, item := range nodeRef.Data.BodyLeaf { - if item.Head.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY { - continue - } - chunk, ok := item.Body.(btrfsitem.Chunk) - if !ok { - fmt.Printf("Pass 1: ... dev[%q] node@%d: item %d: error: type is CHUNK_ITEM_KEY, but struct is %T\n", - dev.Name(), nodeRef.Addr, i, item.Body) - continue - } - fmt.Printf("Pass 1: ... dev[%q] node@%d: item %d: found chunk\n", - dev.Name(), nodeRef.Addr, i) - lostAndFoundChunks = append(lostAndFoundChunks, btrfs.SysChunk{ - Key: item.Head.Key, - Chunk: chunk, - }) - } - } - }, func(pos btrfs.PhysicalAddr) { - pct := int(100 * float64(pos) / float64(devSize)) - if pct != lastProgress || pos == devSize { - fmt.Printf("Pass 1: ... dev[%q] scanned %v%% (found %d nodes)\n", - dev.Name(), pct, len(foundNodes)) - lastProgress = pct - } - }); err != nil { - return err - } - - fmt.Printf("Pass 1: ... dev[%q] re-inserting lost+found chunks\n", dev.Name()) - if len(lostAndFoundChunks) > 0 { - panic("TODO") - } - fmt.Printf("Pass 1: ... dev[%q] re-constructing stripes for lost+found nodes\n", dev.Name()) - lostAndFoundNodes := make(map[btrfs.PhysicalAddr]btrfs.LogicalAddr) - for laddr, readPaddrs := range foundNodes { - resolvedPaddrs, _ := fs.Resolve(laddr) - for _, readPaddr := range readPaddrs { - if _, ok := resolvedPaddrs[btrfs.QualifiedPhysicalAddr{ - Dev: superblock.Data.DevItem.DevUUID, - Addr: readPaddr, - }]; !ok { - lostAndFoundNodes[readPaddr] = laddr - } - } - } - sortedPaddrs := make([]btrfs.PhysicalAddr, 0, len(lostAndFoundNodes)) - for paddr := range lostAndFoundNodes { - sortedPaddrs = append(sortedPaddrs, paddr) - } - sort.Slice(sortedPaddrs, func(i, j int) bool { - return sortedPaddrs[i] < sortedPaddrs[j] - }) - type stripe struct { - PAddr btrfs.PhysicalAddr - LAddr btrfs.LogicalAddr - Size uint64 - } - var stripes []stripe - for _, paddr := range sortedPaddrs { - var lastStripe *stripe - if len(stripes) > 0 { - lastStripe = &stripes[len(stripes)-1] - } - if lastStripe != nil && (lastStripe.PAddr+btrfs.PhysicalAddr(lastStripe.Size)) == paddr { - lastStripe.Size += uint64(superblock.Data.NodeSize) - } else { - stripes = append(stripes, stripe{ - PAddr: paddr, - LAddr: lostAndFoundNodes[paddr], - Size: uint64(superblock.Data.NodeSize), - }) - } - } - //fmt.Printf("Pass 1: ... dev[%q] reconstructed stripes: %#v\n", dev.Name(), stripes) - for _, stripe := range stripes { - reconstructedChunks[stripe.LAddr] = append(reconstructedChunks[stripe.LAddr], reconstructedStripe{ - Size: stripe.Size, - Dev: dev, - Addr: stripe.PAddr, - }) - } - } - // FIXME(lukeshu): OK, so this just assumes that all the - // reconstructed stripes fit in one node, and that we can just - // store that node at the root node of the chunk tree. This - // isn't true in general, but it's true of my particular - // filesystem. - reconstructedNode := &util.Ref[btrfs.LogicalAddr, btrfs.Node]{ - File: fs, - Addr: superblock.Data.ChunkTree, - Data: btrfs.Node{ - Size: superblock.Data.NodeSize, - Head: btrfs.NodeHeader{ - MetadataUUID: superblock.Data.EffectiveMetadataUUID(), - Addr: superblock.Data.ChunkTree, - Flags: btrfs.NodeWritten, - //BackrefRef: ???, - //ChunkTreeUUID: ???, - Generation: superblock.Data.ChunkRootGeneration, - Owner: btrfs.CHUNK_TREE_OBJECTID, - Level: 0, - }, - }, - } - itemOff := uint32(uint64(superblock.Data.NodeSize) - uint64(binstruct.StaticSize(btrfs.ItemHeader{}))) - for _, dev := range fs.Devices { - itemSize := uint32(binstruct.StaticSize(btrfsitem.Dev{})) - itemOff -= itemSize - superblock, _ := dev.Superblock() - reconstructedNode.Data.BodyLeaf = append(reconstructedNode.Data.BodyLeaf, btrfs.Item{ - Head: btrfs.ItemHeader{ - Key: btrfs.Key{ - ObjectID: btrfs.DEV_ITEMS_OBJECTID, - ItemType: btrfsitem.DEV_ITEM_KEY, - Offset: 1, // ??? - }, - DataOffset: itemOff, - DataSize: itemSize, - }, - Body: superblock.Data.DevItem, - }) - } - for laddr, stripes := range reconstructedChunks { - stripeSize := stripes[0].Size - for _, stripe := range stripes { - if stripe.Size != stripeSize { - panic("TODO: mismatch") - } - } - itemSize := uint32(binstruct.StaticSize(btrfsitem.ChunkHeader{}) + (len(stripes) * binstruct.StaticSize(btrfsitem.ChunkStripe{}))) - itemOff -= itemSize - chunkStripes := make([]btrfsitem.ChunkStripe, len(stripes)) - for i := range stripes { - superblock, _ := stripes[i].Dev.Superblock() - chunkStripes[i] = btrfsitem.ChunkStripe{ - DeviceID: superblock.Data.DevItem.DeviceID, - DeviceUUID: superblock.Data.DevItem.DevUUID, - Offset: stripes[i].Addr, - } - } - reconstructedNode.Data.BodyLeaf = append(reconstructedNode.Data.BodyLeaf, btrfs.Item{ - Head: btrfs.ItemHeader{ - Key: btrfs.Key{ - ObjectID: btrfs.FIRST_CHUNK_TREE_OBJECTID, - ItemType: btrfsitem.CHUNK_ITEM_KEY, - Offset: uint64(laddr), - }, - DataOffset: itemOff, - DataSize: itemSize, - }, - Body: btrfsitem.Chunk{ - Head: btrfsitem.ChunkHeader{ - Size: stripeSize, - Owner: btrfs.EXTENT_TREE_OBJECTID, - StripeLen: 65536, // ??? - Type: 0, // TODO - IOOptimalAlign: superblock.Data.DevItem.IOOptimalAlign, - IOOptimalWidth: superblock.Data.DevItem.IOOptimalWidth, - IOMinSize: superblock.Data.DevItem.IOMinSize, - NumStripes: uint16(len(stripes)), - SubStripes: 1, - }, - Stripes: chunkStripes, - }, - }) - } - reconstructedNode.Data.Head.NumItems = uint32(len(reconstructedNode.Data.BodyLeaf)) - reconstructedNode.Data.Head.Checksum, err = reconstructedNode.Data.CalculateChecksum() + _ /*allNodes*/, err = pass1(fs, superblock) if err != nil { - fmt.Printf("Pass 1: ... new node checksum: error: %v\n", err) - } - if err := reconstructedNode.Write(); err != nil { - fmt.Printf("Pass 1: ... write new node: error: %v\n", err) + return err } fmt.Printf("\nPass 2: orphaned nodes\n") /////////////////////////////////////////////////// diff --git a/cmd/btrfs-fsck/pass0.go b/cmd/btrfs-fsck/pass0.go new file mode 100644 index 0000000..8482826 --- /dev/null +++ b/cmd/btrfs-fsck/pass0.go @@ -0,0 +1,19 @@ +package main + +import ( + "fmt" + + "lukeshu.com/btrfs-tools/pkg/btrfs" + "lukeshu.com/btrfs-tools/pkg/util" +) + +func pass0(fs *btrfs.FS) (*util.Ref[btrfs.PhysicalAddr, btrfs.Superblock], error) { + fmt.Printf("\nPass 0: superblocks...\n") + + superblock, err := fs.Superblock() + if err != nil { + return nil, fmt.Errorf("superblock: %w", err) + } + + return superblock, nil +} diff --git a/cmd/btrfs-fsck/pass1.go b/cmd/btrfs-fsck/pass1.go new file mode 100644 index 0000000..5bbdf15 --- /dev/null +++ b/cmd/btrfs-fsck/pass1.go @@ -0,0 +1,296 @@ +package main + +import ( + "fmt" + "sort" + + "lukeshu.com/btrfs-tools/pkg/btrfs" + "lukeshu.com/btrfs-tools/pkg/btrfs/btrfsitem" + "lukeshu.com/btrfs-tools/pkg/btrfsmisc" + "lukeshu.com/btrfs-tools/pkg/util" +) + +func pass1(fs *btrfs.FS, superblock *util.Ref[btrfs.PhysicalAddr, btrfs.Superblock]) (map[btrfs.LogicalAddr]struct{}, error) { + fmt.Printf("\nPass 1: chunk mappings...\n") + + fmt.Printf("Pass 1: ... initializing chunk mappings\n") + if err := fs.Init(); err != nil { + fmt.Printf("Pass 1: ... init chunk tree: error: %v\n", err) + } + + fmt.Printf("Pass 1: ... walking chunk tree\n") + visitedChunkNodes := make(map[btrfs.LogicalAddr]struct{}) + if err := fs.WalkTree(superblock.Data.ChunkTree, btrfs.WalkTreeHandler{ + Node: func(node *util.Ref[btrfs.LogicalAddr, btrfs.Node], err error) error { + if err != nil { + fmt.Printf("Pass 1: ... walk chunk tree: error: %v\n", err) + } + if node != nil { + visitedChunkNodes[node.Addr] = struct{}{} + } + return err + }, + }); err != nil { + fmt.Printf("Pass 1: ... walk chunk tree: error: %v\n", err) + } + + fsFoundNodes := make(map[btrfs.LogicalAddr]struct{}) + fsReconstructedChunks := make(map[btrfs.LogicalAddr]struct { + Size uint64 + Stripes []btrfsitem.ChunkStripe + }) + for _, dev := range fs.Devices { + fmt.Printf("Pass 1: ... dev[%q] scanning for nodes...\n", dev.Name()) + devSuperblock, devFoundNodes, devLostAndFoundChunks, err := pass1ScanOneDev(dev, visitedChunkNodes) + if err != nil { + return nil, err + } + + fmt.Printf("Pass 1: ... dev[%q] re-inserting lost+found chunks\n", dev.Name()) + if len(devLostAndFoundChunks) > 0 { + panic("TODO") + } + + fmt.Printf("Pass 1: ... dev[%q] re-constructing stripes for lost+found nodes\n", dev.Name()) + devReconstructedChunks := pass1ReconstructChunksOneDev(fs, devSuperblock, devFoundNodes) + + // merge those results in to the total-fs results + for laddr := range devFoundNodes { + fsFoundNodes[laddr] = struct{}{} + } + for laddr, _chunk := range devReconstructedChunks { + chunk, ok := fsReconstructedChunks[laddr] + if !ok { + chunk.Size = _chunk.Size + } + if chunk.Size != _chunk.Size { + panic("TODO: mismatch") + } + chunk.Stripes = append(chunk.Stripes, _chunk.Stripes...) + fsReconstructedChunks[laddr] = chunk + } + } + + fmt.Printf("Pass 1: ... writing re-constructed chunks\n") + pass1WriteReconstructedChunks(fs, fsReconstructedChunks) + + return fsFoundNodes, nil +} + +func pass1ScanOneDev( + dev *btrfs.Device, + visitedChunkNodes map[btrfs.LogicalAddr]struct{}, +) ( + superblock *util.Ref[btrfs.PhysicalAddr, btrfs.Superblock], + foundNodes map[btrfs.LogicalAddr][]btrfs.PhysicalAddr, + lostAndFoundChunks []btrfs.SysChunk, + err error, +) { + foundNodes = make(map[btrfs.LogicalAddr][]btrfs.PhysicalAddr) + + superblock, _ = dev.Superblock() + + devSize, _ := dev.Size() + lastProgress := -1 + + err = btrfsmisc.ScanForNodes(dev, superblock.Data, func(nodeRef *util.Ref[btrfs.PhysicalAddr, btrfs.Node], err error) { + if err != nil { + fmt.Printf("Pass 1: ... dev[%q] error: %v\n", dev.Name(), err) + return + } + foundNodes[nodeRef.Data.Head.Addr] = append(foundNodes[nodeRef.Data.Head.Addr], nodeRef.Addr) + _, alreadyVisited := visitedChunkNodes[nodeRef.Data.Head.Addr] + if nodeRef.Data.Head.Owner == btrfs.CHUNK_TREE_OBJECTID && !alreadyVisited { + for i, item := range nodeRef.Data.BodyLeaf { + if item.Head.Key.ItemType != btrfsitem.CHUNK_ITEM_KEY { + continue + } + chunk, ok := item.Body.(btrfsitem.Chunk) + if !ok { + fmt.Printf("Pass 1: ... dev[%q] node@%d: item %d: error: type is CHUNK_ITEM_KEY, but struct is %T\n", + dev.Name(), nodeRef.Addr, i, item.Body) + continue + } + fmt.Printf("Pass 1: ... dev[%q] node@%d: item %d: found chunk\n", + dev.Name(), nodeRef.Addr, i) + lostAndFoundChunks = append(lostAndFoundChunks, btrfs.SysChunk{ + Key: item.Head.Key, + Chunk: chunk, + }) + } + } + }, func(pos btrfs.PhysicalAddr) { + pct := int(100 * float64(pos) / float64(devSize)) + if pct != lastProgress || pos == devSize { + fmt.Printf("Pass 1: ... dev[%q] scanned %v%% (found %d nodes)\n", + dev.Name(), pct, len(foundNodes)) + lastProgress = pct + } + }) + + return +} + +func pass1ReconstructChunksOneDev( + fs *btrfs.FS, + superblock *util.Ref[btrfs.PhysicalAddr, btrfs.Superblock], + foundNodes map[btrfs.LogicalAddr][]btrfs.PhysicalAddr, +) ( + chunks map[btrfs.LogicalAddr]struct { + Size uint64 + Stripes []btrfsitem.ChunkStripe + }, +) { + // find the subset of `foundNodes` that are lost + lostAndFoundNodes := make(map[btrfs.PhysicalAddr]btrfs.LogicalAddr) + for laddr, readPaddrs := range foundNodes { + resolvedPaddrs, _ := fs.Resolve(laddr) + for _, readPaddr := range readPaddrs { + if _, ok := resolvedPaddrs[btrfs.QualifiedPhysicalAddr{ + Dev: superblock.Data.DevItem.DevUUID, + Addr: readPaddr, + }]; !ok { + lostAndFoundNodes[readPaddr] = laddr + } + } + } + + // sort the keys to that set + sortedPaddrs := make([]btrfs.PhysicalAddr, 0, len(lostAndFoundNodes)) + for paddr := range lostAndFoundNodes { + sortedPaddrs = append(sortedPaddrs, paddr) + } + sort.Slice(sortedPaddrs, func(i, j int) bool { + return sortedPaddrs[i] < sortedPaddrs[j] + }) + + // build a list of stripes from that sorted set + type stripe struct { + PAddr btrfs.PhysicalAddr + LAddr btrfs.LogicalAddr + Size uint64 + } + var stripes []stripe + for _, paddr := range sortedPaddrs { + var lastStripe *stripe + if len(stripes) > 0 { + lastStripe = &stripes[len(stripes)-1] + } + if lastStripe != nil && (lastStripe.PAddr+btrfs.PhysicalAddr(lastStripe.Size)) == paddr { + lastStripe.Size += uint64(superblock.Data.NodeSize) + } else { + stripes = append(stripes, stripe{ + PAddr: paddr, + LAddr: lostAndFoundNodes[paddr], + Size: uint64(superblock.Data.NodeSize), + }) + } + } + //fmt.Printf("Pass 1: ... dev[%q] reconstructed stripes: %#v\n", dev.Name(), stripes) + + // organize those stripes in to chunks + chunks = make(map[btrfs.LogicalAddr]struct { + Size uint64 + Stripes []btrfsitem.ChunkStripe + }) + for _, stripe := range stripes { + chunk, ok := chunks[stripe.LAddr] + if !ok { + chunk.Size = stripe.Size + } + if chunk.Size != stripe.Size { + panic("TODO: mismatch") + } + chunk.Stripes = append(chunk.Stripes, btrfsitem.ChunkStripe{ + DeviceID: superblock.Data.DevItem.DeviceID, + DeviceUUID: superblock.Data.DevItem.DevUUID, + Offset: stripe.PAddr, + }) + chunks[stripe.LAddr] = chunk + } + + return chunks +} + +func pass1WriteReconstructedChunks( + fs *btrfs.FS, + fsReconstructedChunks map[btrfs.LogicalAddr]struct { + Size uint64 + Stripes []btrfsitem.ChunkStripe + }, +) { + superblock, _ := fs.Superblock() + + // FIXME(lukeshu): OK, so this just assumes that all the + // reconstructed stripes fit in one node, and that we can just + // store that node at the root node of the chunk tree. This + // isn't true in general, but it's true of my particular + // filesystem. + reconstructedNode := &util.Ref[btrfs.LogicalAddr, btrfs.Node]{ + File: fs, + Addr: superblock.Data.ChunkTree, + Data: btrfs.Node{ + Size: superblock.Data.NodeSize, + Head: btrfs.NodeHeader{ + MetadataUUID: superblock.Data.EffectiveMetadataUUID(), + Addr: superblock.Data.ChunkTree, + Flags: btrfs.NodeWritten, + //BackrefRef: ???, + //ChunkTreeUUID: ???, + Generation: superblock.Data.ChunkRootGeneration, + Owner: btrfs.CHUNK_TREE_OBJECTID, + Level: 0, + }, + }, + } + for _, dev := range fs.Devices { + superblock, _ := dev.Superblock() + reconstructedNode.Data.BodyLeaf = append(reconstructedNode.Data.BodyLeaf, btrfs.Item{ + Head: btrfs.ItemHeader{ + Key: btrfs.Key{ + ObjectID: btrfs.DEV_ITEMS_OBJECTID, + ItemType: btrfsitem.DEV_ITEM_KEY, + Offset: 1, // ??? + }, + }, + Body: superblock.Data.DevItem, + }) + } + for laddr, chunk := range fsReconstructedChunks { + reconstructedNode.Data.BodyLeaf = append(reconstructedNode.Data.BodyLeaf, btrfs.Item{ + Head: btrfs.ItemHeader{ + Key: btrfs.Key{ + ObjectID: btrfs.FIRST_CHUNK_TREE_OBJECTID, + ItemType: btrfsitem.CHUNK_ITEM_KEY, + Offset: uint64(laddr), + }, + }, + Body: btrfsitem.Chunk{ + Head: btrfsitem.ChunkHeader{ + Size: chunk.Size, + Owner: btrfs.EXTENT_TREE_OBJECTID, + StripeLen: 65536, // ??? + Type: 0, // TODO + IOOptimalAlign: superblock.Data.DevItem.IOOptimalAlign, + IOOptimalWidth: superblock.Data.DevItem.IOOptimalWidth, + IOMinSize: superblock.Data.DevItem.IOMinSize, + NumStripes: uint16(len(chunk.Stripes)), + SubStripes: 1, + }, + Stripes: chunk.Stripes, + }, + }) + } + var err error + reconstructedNode.Data.Head.Checksum, err = reconstructedNode.Data.CalculateChecksum() + if err != nil { + fmt.Printf("Pass 1: ... new node checksum: error: %v\n", err) + } + if err := reconstructedNode.Write(); err != nil { + fmt.Printf("Pass 1: ... write new node: error: %v\n", err) + } + + if err := fs.Init(); err != nil { + fmt.Printf("Pass 1: ... re-init mappings: %v\n", err) + } +} |