From 997b21c0c3aa7aee8fb56ed94d0419e46816e8ac Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Fri, 21 Jul 2023 23:41:26 -0600 Subject: btrfs-rec.md: Improve the markup --- public/btrfs-rec.md | 122 ++++++++++++++++++++++++++++++++++------------------ 1 file changed, 80 insertions(+), 42 deletions(-) diff --git a/public/btrfs-rec.md b/public/btrfs-rec.md index 8519969..f5d8dc6 100644 --- a/public/btrfs-rec.md +++ b/public/btrfs-rec.md @@ -2,6 +2,7 @@ Announcing: btrfs-rec: Recover (data from) a broken btrfs filesystem ==================================================================== --- date: "2023-07-10" +markdown_options: "-smart" --- > I originally sent this email on 2023-07-10, but it has been caught @@ -170,14 +171,14 @@ btrfs-progs.) # 2. Overview of use There are two `btrfs-rec` sub-command groups: -`btrfs-rec inspect SUBCMD` and `btrfs-rec repair SUBCMD`, and you can +btrfs-rec inspect SUBCMD and btrfs-rec repair SUBCMD, and you can find out about various sub-commands with `btrfs-rec help`. These are both told about devices or images with the `--pv` flag. -`btrfs-rec inspect SUBCMD` commands open the filesystem read-only, and +btrfs-rec inspect SUBCMD commands open the filesystem read-only, and (generally speaking) write extracted or rebuilt information to stdout. -`btrfs-rec repair SUBCMD` commands open the filesystem read+write, and -consume information from `btrfs-rec inspect SUBCMD` commands to +btrfs-rec repair SUBCMD commands open the filesystem read+write, and +consume information from btrfs-rec inspect SUBCMD commands to actually repair the filesystem (except I haven't actually implemented any `repair` commands yet... despite the lack of `repair` commands, I believe that `btrfs-rec` is already a useful because of the `btrfs-rec @@ -231,7 +232,7 @@ I'd: ./mnt This example is fleshed out more (and the manual edits to -`mappings.json` explained more) in `./examples/main.sh`. +`mappings.json` explained more) in [`./examples/main.sh`]. # 3. Prior art @@ -251,30 +252,30 @@ https://github.com/adam900710/btrfs-fuse project: ## 4.1. Overview of the source tree layout - - `examples/` has example scripts showing how to use `btrfs-rec`. + - [`examples/`] has example scripts showing how to use `btrfs-rec`. - - `lib/btrfs/` is the core btrfs implementation. + - [`lib/btrfs/`] is the core btrfs implementation. - - `lib/btrfscheck/` and `lib/btrfsutil/` are libraries for + - [`lib/btrfscheck/`] and [`lib/btrfsutil/`] are libraries for "btrfs-progs" type programs, that are userland-y things that I thought should be separate from the core implementation; something that frustrated me about libbtrfs was having to figure out "is this thing here in support of btrfs bits-on-disk, or in support of a higher-level 'how btrfs-progs wants to think about things'?" - - `cmd/btrfs-rec/` is where the command implementations live. If a + - [`cmd/btrfs-rec/`] is where the command implementations live. If a sub-command fits in a single file, it's - `cmd/btrfs-rec/inspect_SUBCMD.go`, otherwise, it's in a separate - `cmd/btrfs-rec/inspect/SUBCMD/` package. + cmd/btrfs-rec/inspect_SUBCMD.go, otherwise, it's in a separate + cmd/btrfs-rec/inspect/SUBCMD/ package. - - `lib/textui/` is reasonably central to how the commands implement a + - [`lib/textui/`] is reasonably central to how the commands implement a text/CLI user-interface. - - `lib/binstruct/`, `lib/diskio/`, and `lib/streamio/` are + - [`lib/binstruct/`], [`lib/diskio/`], and [`lib/streamio/`] are non-btrfs-specific libraries related to the problem domain. - - `lib/containers/`, `lib/fmtutil/`, `lib/maps/`, `lib/slices/`, and - `lib/profile/` are all generic Go libraries that have nothing to do + - [`lib/containers/`], [`lib/fmtutil/`], [`lib/maps/`], [`lib/slices/`], and + [`lib/profile/`] are all generic Go libraries that have nothing to do with btrfs or the problem domain, but weren't in the Go standard library and I didn't find/know-of exiting implementations that I liked. Of these, all but `containers` are pretty simple utility @@ -324,17 +325,17 @@ can consume that `mappings.json` to use that instead of trying to read the chunk tree from the actual FS, so that you don't have to make potentially destructive writes to inspect an FS with a broken chunk tree, and can inspect it more forensically. Or then use -`btrfs-rec repair SOME_SUBCMD_I_HAVENT_WRITTEN_YET` to write that +btrfs-rec repair SOME_SUBCMD_I_HAVENT_WRITTEN_YET to write that chunk tree in `mappings.json` back to the filesystem. (But also, the separate steps thing was useful just so I could iterate on the algorithms of `rebuild-mappings process` separately from having to scan the entire FS) -So, I made the decision that `btrfs-rec inspect SUBCMD` commands +So, I made the decision that btrfs-rec inspect SUBCMD commands should all only open the FS read-only, and output their work to a separate file; that writing that info back to the FS should be -separate in `btrfs-rec repair SUBCMD`. +separate in btrfs-rec repair SUBCMD. For connecting those parts of the pipeline, I chose JSON, for a few reasons: @@ -344,7 +345,7 @@ reasons: - I wanted something reasonably human-readable, so that human end-users could make manual edits; for example, in - `examples/main.sh` I have an example of manually editing + [`examples/main.sh`] I have an example of manually editing `mappings.json` to resolve a region that the algorithm couldn't figure out, but with knowledge of what caused the corruption a human can. @@ -364,7 +365,7 @@ OK, so: Go and/or JSON maybe being mistakes: - I spent a lot of time getting the garbage collector to not just kill performance. - - The `btrfs-rec inspect rebuild-mappings SUBCMD` subcommands all + - The btrfs-rec inspect rebuild-mappings SUBCMD subcommands all throw a lot of data through the JSON encoder/decoder, and I learned that the Go stdlib `encoding/json` package has memory use that grows O(n^2) (-ish? I didn't study the implementation, but that's @@ -394,8 +395,8 @@ doesn't get in: ### 4.3.1. The `rebuild-mappings` algorithm (This step-zero scan is `btrfs-rec inspect rebuild-mappings scan`, and -principally lives in `./lib/btrfsutil/scan.go` and -`./cmd/btrfs-rec/inspect/rebuidmappings/scan.go`) +principally lives in [`./lib/btrfsutil/scan.go`] and +[`./cmd/btrfs-rec/inspect/rebuildmappings/scan.go`]) 0. Similar to `btrfs rescue chunk-recover`, scan each device for things that look like nodes; keep track of: @@ -410,7 +411,7 @@ Create a bucket of the data from Chunks, DevExtents, and BlockGroups; since these are mostly a Chunk and a DevExtent+BlockGroup store pretty much the same information; we can use one to reconstruct the other. How we "merge" these and handle conflicts is in -`./lib/btrfs/btrfsvol/lvm.go:addMapping()`, I don't think this +[`./lib/btrfs/btrfsvol/lvm.go:addMapping()`], I don't think this part is particularly clever, but given that `btrfs rescue chunk-recover` crashes if it encounters two overlapping chunks, I suppose I should spell it out: @@ -445,7 +446,7 @@ Now that we know how to "add a mapping", let's do that: (The following main-steps are `btrfs-rec inspect rebuild-mappings process`, and principally live in -`./cmd/btrfs-rec/inspect/rebuidmappings/process.go`) +[`./cmd/btrfs-rec/inspect/rebuildmappings/process.go`]) 1. Add all found Chunks. @@ -469,7 +470,7 @@ process`, and principally live in by a filesystem bug (i.e. not by a failing drive or other external corruption), so I wasn't too concerned about it, so I just log an error on stderr and skip the later-processed item. See - `./cmd/btrfs-rec/inspect/rebuidmappings/process_sums_logical.go`. + [`./cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go`]. Look at regions of the logical address space that meet all the 3 criteria: @@ -510,11 +511,11 @@ probably should have tried to understand the `btrfs restore` algorithm, maybe I reinvented the wheel... This algorithm requires a list of all nodes on the filesystem; we find -these using the same scan as above (`./lib/btrfsutil/scan.go`), the +these using the same scan as above ([`./lib/btrfsutil/scan.go`]), the same procedure as `btrfs rescue chunk-recover`. We walk all of those nodes, and build a reasonably lightweight -in-memory graph of all nodes (`./lib/btrfsutil/graph.go`), tracking +in-memory graph of all nodes ([`./lib/btrfsutil/graph.go`]), tracking - each node's + logical address @@ -540,7 +541,7 @@ in-memory graph of all nodes (`./lib/btrfsutil/graph.go`), tracking #### 4.3.2.1. rebuilt forrest behavior (looking up trees) -(see: `./lib/btrfsutil/rebuilt_forrest.go`) +(see: [`./lib/btrfsutil/rebuilt_forrest.go`]) - The `ROOT_TREE`, `CHUNK_TREE`, `TREE_LOG`, and `BLOCK_GROUP_TREE` (the trees pointed to directy by the superblock) work as you'd @@ -564,7 +565,7 @@ in-memory graph of all nodes (`./lib/btrfsutil/graph.go`), tracking #### 4.3.2.2. rebuilt individual tree behavior -(see: `./lib/btrfsutil/rebuilt_tree.go`) +(see: [`./lib/btrfsutil/rebuilt_tree.go`]) In order to read from a tree, we first have to build a few indexes. We store these indexes in an Adaptive Replacement Cache; they are all @@ -748,7 +749,7 @@ The `btrfs inspect rebuild-trees` algorithm finds nodes to attach as extra roots to trees. I think that conceptually it's the the simplest of the 3 algorithms, but turned out to be the hardest to get right. So... maybe more than the others reference the source code too -(`./cmd/btrfs-rec/inspect/rebuildtrees/`) because I might forget some +([`./cmd/btrfs-rec/inspect/rebuildtrees/`]) because I might forget some small but important detail. The core idea here is that we're just going to walk each tree, @@ -778,7 +779,7 @@ But this time, while we're reading the nodes to do that, we're also going to watch for some specific items and record a few things about them. -(see: `./cmd/btrfs-rec/inspect/rebuildtrees/scan.go`) +(see: [`./cmd/btrfs-rec/inspect/rebuildtrees/scan.go`]) For each {`nodeID`, `slotNumber`} pair that matches one of these item types, we're going to record: @@ -804,7 +805,7 @@ types, we're going to record: #### 4.3.3.2. the main loop -(see: `./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go`) +(see: [`./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go`]) Start with that scan data (graph + info about items), and also a rebuilt forrest from the above algorithm, but with: @@ -831,7 +832,7 @@ rebuilt forrest from the above algorithm, but with: + a callback that intercepts resolving an UUID to an object ID. (The callbacks are in - `./cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go`) + [`./cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go`]) We have 5 unordered queues ("work lists"?); these are sets that when it's time to drain them we'll sort the members and process them in @@ -892,7 +893,7 @@ OK, let's look at those 3 substeps in more detail: looking up of root items and resolving UUIDs; we override the forrest's "lookup root item" routine and "resolve UUID" routine to instead of doing normal lookups on the `ROOT_TREE` and - `UUID_TREE`, use the above `WantXXX` routines that we'll define + `UUID_TREE`, use the above WantXXX routines that we'll define below in the "graph callbacks" section. It shouldn't matter what order this queue is processed in, but I @@ -948,7 +949,7 @@ OK, let's look at those 3 substeps in more detail: to solve MinLA, which is NP-hard and also an optimal MinLA solution I still think would perform worse than this; there is a reasonably lengthy discussion of this in a comment in - `./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go:sortSettledItemQueue()`. + [`./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go:sortSettledItemQueue()`]. Now we loop over that sorted queue. In the code, this loop is deceptively simple. Read the item, then pass it to a function @@ -967,7 +968,7 @@ OK, let's look at those 3 substeps in more detail: (Both the "can this item even imply the existence of another item" check and the "what items are implied by this item" routine are in - `./lib/btrfscheck/graph.go`) + [`./lib/btrfscheck/graph.go`]) 3. Apply augments; drain the augment queue (and maybe the retry-item queue), fill the added-item queuee. @@ -1007,7 +1008,7 @@ OK, let's look at those 3 substeps in more detail: this tree to the added-item queue. How do we decide between choices of root nodes to add? - `./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go:resolveTreeAugments()` + [`./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go:resolveTreeAugments()`] has a good comment explaining the criteria we'd like to optimize for, and then code that does an OK-ish job of actually optimizing for that: @@ -1044,7 +1045,7 @@ once the loop terminates, and then re-seed the tree queue with each #### 4.3.3.3. graph callbacks -(see: `./cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go`) +(see: [`./cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go`]) The graph callbacks are what tie the above together. @@ -1106,8 +1107,8 @@ The 6 methods in the `brfscheck.GraphCallbacks` interface are: First we walk that range in the item index, to build a list of the gaps that we need to fill ("Step 1" in - `rebuild_wantcb.go:_wantRange()`). This walk - (`rebuild_wantcb.go:_walkRange()`) requires knowing the size of + [`rebuild_wantcb.go:_wantRange()`]). This walk + ([`rebuild_wantcb.go:_walkRange()`]) requires knowing the size of each file extent; so doing this quickly without hitting disk is why we recorded the size of each file extent in our initialization step. @@ -1155,7 +1156,7 @@ do: inodes that are included in the subvolume's tree but aren't reachable from the tree's root inode - - I still need to implement `btrfs-rec repair SUBCMD` subcommands to + - I still need to implement btrfs-rec repair SUBCMD subcommands to write rebuilt-information from `btrfs-rec inspect` back to the filesystem. @@ -1204,7 +1205,7 @@ do: could be parallelized. - There are a lot of "tunable" values that I haven't really spent - time tuning. These are all annotated with `textui.Tunable()`. I + time tuning. These are all annotated with [`textui.Tunable()`]. I sort-of intended for them to be adjustable on the CLI. - Perhaps the `btrfs inspect rebuild-trees` algorithm could be @@ -1232,3 +1233,40 @@ do: Happy hacking,
~ Luke Shumaker
+ +[`./examples/main.sh`]: https://git.lukeshu.com/btrfs-progs-ng/tree/examples/main.sh?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`examples/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/examples?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/btrfs/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/btrfs?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/btrfscheck/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/btrfscheck?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/btrfsutil/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/btrfsutil?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`cmd/btrfs-rec/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/textui/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/textui?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/binstruct/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/binstruct?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/diskio/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/diskio?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/streamio/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/streamio?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/containers/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/containers?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/fmtutil/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/fmtutil?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/maps/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/maps?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/slices/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/slices?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`lib/profile/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/profile?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`examples/main.sh`]: https://git.lukeshu.com/btrfs-progs-ng/tree/examples/main.sh?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./lib/btrfsutil/scan.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/btrfsutil/scan.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./cmd/btrfs-rec/inspect/rebuildmappings/scan.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildmappings/scan.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./lib/btrfs/btrfsvol/lvm.go:addMapping()`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/btrfs/btrfsvol/lvm.go?id=18e6066c241cf3d252b6521150843ffc858d8434#n121 +[`./cmd/btrfs-rec/inspect/rebuildmappings/process.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildmappings/process.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildmappings/process_sums_logical.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./lib/btrfsutil/scan.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/btrfsutil/scan.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./lib/btrfsutil/graph.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/btrfsutil/graph.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./lib/btrfsutil/rebuilt_forrest.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/btrfsutil/rebuilt_forrest.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./lib/btrfsutil/rebuilt_tree.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/btrfsutil/rebuilt_tree.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./cmd/btrfs-rec/inspect/rebuildtrees/`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildtrees?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./cmd/btrfs-rec/inspect/rebuildtrees/scan.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildtrees/scan.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_treecb.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go:sortSettledItemQueue()`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go?id=18e6066c241cf3d252b6521150843ffc858d8434#n251 +[`./lib/btrfscheck/graph.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/btrfscheck/graph.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`./cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go:resolveTreeAugments()`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildtrees/rebuild.go?id=18e6066c241cf3d252b6521150843ffc858d8434#n528 +[`./cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go?id=18e6066c241cf3d252b6521150843ffc858d8434 +[`rebuild_wantcb.go:_wantRange()`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go?id=18e6066c241cf3d252b6521150843ffc858d8434#n260 +[`rebuild_wantcb.go:_walkRange()`]: https://git.lukeshu.com/btrfs-progs-ng/tree/cmd/btrfs-rec/inspect/rebuildtrees/rebuild_wantcb.go?id=18e6066c241cf3d252b6521150843ffc858d8434#n195 +[`textui.Tunable()`]: https://git.lukeshu.com/btrfs-progs-ng/tree/lib/textui/tunable.go?id=18e6066c241cf3d252b6521150843ffc858d8434 -- cgit v1.1-4-g5e80