summaryrefslogtreecommitdiff
path: root/public/btrfs-rec.md
diff options
context:
space:
mode:
Diffstat (limited to 'public/btrfs-rec.md')
-rw-r--r--public/btrfs-rec.md122
1 files 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
+<code>btrfs-rec inspect <var>SUBCMD</var></code> and <code>btrfs-rec repair <var>SUBCMD</var></code>, 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
+<code>btrfs-rec inspect <var>SUBCMD</var></code> 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
+<code>btrfs-rec repair <var>SUBCMD</var></code> commands open the filesystem read+write, and
+consume information from <code>btrfs-rec inspect <var>SUBCMD</var></code> 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.
+ <code>cmd/btrfs-rec/inspect_<var>SUBCMD</var>.go</code>, otherwise, it's in a separate
+ <code>cmd/btrfs-rec/inspect/<var>SUBCMD</var>/</code> 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
+<code>btrfs-rec repair <var>SOME_SUBCMD_I_HAVENT_WRITTEN_YET</var></code> 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 <code>btrfs-rec inspect <var>SUBCMD</var></code> 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 <code>btrfs-rec repair <var>SUBCMD</var></code>.
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 <code>btrfs-rec inspect rebuild-mappings <var>SUBCMD</var></code> 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 <code>Want<var>XXX</var></code> 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 <code>btrfs-rec repair <var>SUBCMD</var></code> 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,<br/>
~ Luke Shumaker<br/>
</div>
+
+[`./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