btrfs_recovery.cpp

Go to the documentation of this file.

#include "btrfs_recovery.hpp"
#include "i18n.hpp"
#include "text_utils.hpp"
 
#include <algorithm>
#include <array>
#include <cstdint>
#include <filesystem>
#include <fstream>
#include <iomanip>
#include <map>
#include <optional>
#include <set>
#include <sstream>
#include <string>
#include <vector>
 
#ifdef HAVE_ZLIB
#include <zlib.h>
#endif
#ifdef HAVE_ZSTD
#include <zstd.h>
#endif
#ifdef HAVE_LZO
#include <lzo/lzo1x.h>
#endif
 
namespace fs = std::filesystem;
 
namespace {
constexpr uint8_t BTRFS_INODE_ITEM_KEY = 1;
constexpr uint8_t BTRFS_INODE_REF_KEY = 12;
constexpr uint8_t BTRFS_DIR_ITEM_KEY = 84;
constexpr uint8_t BTRFS_DIR_INDEX_KEY = 96;
constexpr uint8_t BTRFS_EXTENT_DATA_KEY = 108;
constexpr uint8_t BTRFS_ROOT_ITEM_KEY = 132;
constexpr uint8_t BTRFS_ROOT_BACKREF_KEY = 144;
constexpr uint8_t BTRFS_ROOT_REF_KEY = 156;
constexpr uint8_t BTRFS_CHUNK_ITEM_KEY = 228;
 
constexpr uint8_t BTRFS_FILE_EXTENT_INLINE = 0;
constexpr uint8_t BTRFS_FILE_EXTENT_REG = 1;
constexpr uint8_t BTRFS_FILE_EXTENT_PREALLOC = 2;
 
constexpr uint64_t BTRFS_BLOCK_GROUP_RAID0 = 1ull << 3;
constexpr uint64_t BTRFS_BLOCK_GROUP_RAID1 = 1ull << 4;
constexpr uint64_t BTRFS_BLOCK_GROUP_DUP = 1ull << 5;
constexpr uint64_t BTRFS_BLOCK_GROUP_RAID10 = 1ull << 6;
constexpr uint64_t BTRFS_BLOCK_GROUP_RAID5 = 1ull << 7;
constexpr uint64_t BTRFS_BLOCK_GROUP_RAID6 = 1ull << 8;
 
uint16_t le16(const unsigned char* p) {
    return static_cast<uint16_t>(p[0]) | (static_cast<uint16_t>(p[1]) << 8);
}
 
uint32_t le32(const unsigned char* p) {
    return static_cast<uint32_t>(p[0]) |
           (static_cast<uint32_t>(p[1]) << 8) |
           (static_cast<uint32_t>(p[2]) << 16) |
           (static_cast<uint32_t>(p[3]) << 24);
}
 
uint64_t le64(const unsigned char* p) {
    return static_cast<uint64_t>(p[0]) |
           (static_cast<uint64_t>(p[1]) << 8) |
           (static_cast<uint64_t>(p[2]) << 16) |
           (static_cast<uint64_t>(p[3]) << 24) |
           (static_cast<uint64_t>(p[4]) << 32) |
           (static_cast<uint64_t>(p[5]) << 40) |
           (static_cast<uint64_t>(p[6]) << 48) |
           (static_cast<uint64_t>(p[7]) << 56);
}
 
std::string sanitize(const std::string& in) {
    // Bug #15 fix: btrfs filenames are stored as UTF-8 byte sequences. The
    // previous ASCII-only sanitizer turned every accented character into '_'.
    // We reuse the shared helper which preserves valid UTF-8 multibyte runs.
    auto out = text_utils::sanitize_component(in);
    if (out == "unnamed") out = "item";
    return out;
}
 
std::string to_hex(uint64_t v) {
    std::ostringstream oss;
    oss << "0x" << std::hex << std::uppercase << v;
    return oss.str();
}
 
struct BtrfsKey {
    uint64_t objectid {0};
    uint8_t type {0};
    uint64_t offset {0};
};
 
struct BtrfsItem {
    BtrfsKey key;
    uint32_t data_offset {0};
    uint32_t data_size {0};
};
 
struct BtrfsKeyPtr {
    BtrfsKey key;
    uint64_t blockptr {0};
    uint64_t generation {0};
};
 
struct ChunkStripe {
    uint64_t physical {0};
    uint64_t devid {0};
};
 
struct ChunkMapEntry {
    uint64_t logical {0};
    uint64_t length {0};
    uint64_t stripe_length {0};
    uint64_t type {0};
    uint16_t num_stripes {0};
    std::vector<ChunkStripe> stripes;
};
 
struct RootEntry {
    uint64_t bytenr {0};
    uint8_t level {0};
    std::string name;
};
 
struct InodeInfo {
    uint64_t size {0};
    uint32_t mode {0};
};
 
struct DirEdge {
    uint64_t parent {0};
    uint64_t child {0};
    std::string name;
};
 
struct FileExtentInfo {
    uint64_t file_offset {0};
    uint64_t ram_bytes {0};
    uint8_t compression {0};
    uint8_t type {0};
    uint64_t disk_bytenr {0};
    uint64_t disk_num_bytes {0};
    uint64_t extent_offset {0};
    uint64_t num_bytes {0};
    std::vector<unsigned char> inline_data;
};
 
struct FsRootState {
    std::map<uint64_t, InodeInfo> inodes;
    std::map<uint64_t, std::vector<FileExtentInfo>> extents;
    std::map<uint64_t, DirEdge> parent_edge;
};
 
BtrfsKey parse_key(const unsigned char* p) {
    return {le64(p), p[8], le64(p + 9)};
}
 
// Btrfs compression on-disk format notes (per fs/btrfs/{zlib,lzo,zstd}.c):
//
//   ZLIB:  the entire input is a SINGLE zlib stream (with its own
//          deflate dictionary); since each Btrfs extent is at most
//          128 KiB of uncompressed data ("BTRFS_COMPRESSION_BLOCKSIZE"),
//          the stream is small and uncompress() works directly. No
//          chunk framing.
//
//   LZO:   chunked format with explicit framing:
//             __le32 total_compressed_len  (whole payload)
//             per chunk:
//               __le32 chunk_compressed_len
//               <chunk_compressed_len bytes of LZO1X data>
//          Each chunk decompresses to up to one page (4 KiB) of output.
//          Padding may bring chunks to PAGE_SIZE boundaries.
//
//   ZSTD:  chunked similarly to LZO:
//             __le32 chunk_compressed_len
//             <chunk_compressed_len bytes of zstd frame>
//          Each chunk decompresses to up to BTRFS_COMPRESSION_BLOCKSIZE
//          (128 KiB) of output.
 
bool decompress_payload(const std::vector<unsigned char>& in,
                        uint8_t compression,
                        size_t expected_size,
                        std::vector<unsigned char>& out) {
    if (compression == 0) {
        out = in;
        if (out.size() > expected_size) out.resize(expected_size);
        return true;
    }
#ifdef HAVE_ZLIB
    if (compression == 1) {
        // Btrfs zlib: single zlib stream per extent (max 128 KiB output).
        out.resize(expected_size);
        uLongf dest_len = static_cast<uLongf>(out.size());
        int rc = ::uncompress(out.data(), &dest_len, in.data(), static_cast<uLong>(in.size()));
        if (rc != Z_OK) return false;
        out.resize(static_cast<size_t>(dest_len));
        return true;
    }
#endif
#ifdef HAVE_LZO
    if (compression == 2) {
        // Btrfs LZO chunked decoder.
        constexpr size_t kBtrfsLzoPageSize = 4096;
        if (in.size() < 4) return false;
        const uint32_t total_len = le32(in.data());
        if (total_len > in.size()) return false;
        // Chunks start at offset 4 (after the total length header).
        // The kernel writer pads chunks so that no chunk header straddles
        // a 4 KiB page boundary in the COMPRESSED stream. We mirror that:
        // when the next chunk header would straddle a page, we skip to
        // the next page.
        size_t pos = 4;
        out.clear();
        out.reserve(expected_size);
        while (pos + 4 <= total_len && out.size() < expected_size) {
            // Page-boundary skip: if a 4-byte chunk header would not fit
            // in the remaining bytes of the current page, advance to the
            // next page.
            const size_t page_off = pos % kBtrfsLzoPageSize;
            if (page_off + 4 > kBtrfsLzoPageSize) {
                pos += kBtrfsLzoPageSize - page_off;
                if (pos + 4 > total_len) break;
            }
            const uint32_t chunk_len = le32(in.data() + pos);
            pos += 4;
            if (chunk_len == 0 || chunk_len > total_len - pos) return false;
 
            std::vector<unsigned char> chunk_out(kBtrfsLzoPageSize);
            lzo_uint dest_len = static_cast<lzo_uint>(chunk_out.size());
            const int rc = lzo1x_decompress_safe(
                in.data() + pos, static_cast<lzo_uint>(chunk_len),
                chunk_out.data(), &dest_len, nullptr);
            if (rc != LZO_E_OK) return false;
            chunk_out.resize(static_cast<size_t>(dest_len));
            out.insert(out.end(), chunk_out.begin(), chunk_out.end());
            pos += chunk_len;
        }
        if (out.size() > expected_size) out.resize(expected_size);
        return true;
    }
#endif
#ifdef HAVE_ZSTD
    if (compression == 3) {
        // Btrfs zstd chunked decoder.
        // Format: per-chunk: __le32 chunk_len + <chunk_len bytes zstd frame>.
        // Each chunk decompresses to up to 128 KiB.
        constexpr size_t kBtrfsZstdMaxChunkOutput = 128 * 1024;
        size_t pos = 0;
        out.clear();
        out.reserve(expected_size);
        while (pos + 4 <= in.size() && out.size() < expected_size) {
            const uint32_t chunk_len = le32(in.data() + pos);
            pos += 4;
            if (chunk_len == 0 || chunk_len > in.size() - pos) return false;
 
            std::vector<unsigned char> chunk_out(kBtrfsZstdMaxChunkOutput);
            const size_t rc = ZSTD_decompress(
                chunk_out.data(), chunk_out.size(),
                in.data() + pos, chunk_len);
            if (ZSTD_isError(rc)) return false;
            chunk_out.resize(rc);
            out.insert(out.end(), chunk_out.begin(), chunk_out.end());
            pos += chunk_len;
        }
        if (out.size() > expected_size) out.resize(expected_size);
        return true;
    }
#endif
    return false;
}
 
uint8_t gf_mul_byte(uint8_t a, uint8_t b) {
    uint8_t p = 0;
    for (int i = 0; i < 8; ++i) {
        if (b & 1u) p ^= a;
        const bool hi = (a & 0x80u) != 0;
        a = static_cast<uint8_t>(a << 1u);
        if (hi) a ^= 0x1du;
        b = static_cast<uint8_t>(b >> 1u);
    }
    return p;
}
 
uint8_t gf_pow2(size_t exp) {
    uint8_t v = 1;
    for (size_t i = 0; i < exp; ++i) v = gf_mul_byte(v, 2);
    return v;
}
 
uint8_t gf_inv_byte(uint8_t a) {
    if (a == 0) return 0;
    for (int i = 1; i < 256; ++i) {
        if (gf_mul_byte(a, static_cast<uint8_t>(i)) == 1u) return static_cast<uint8_t>(i);
    }
    return 0;
}
 
 
uint32_t crc32c_update(uint32_t crc, const unsigned char* data, size_t len) {
    static uint32_t table[256]{};
    static bool init = false;
    if (!init) {
        for (uint32_t i = 0; i < 256; ++i) {
            uint32_t r = i;
            for (int j = 0; j < 8; ++j) r = (r >> 1) ^ (0x82F63B78u & static_cast<uint32_t>(-(static_cast<int32_t>(r & 1u))));
            table[i] = r;
        }
        init = true;
    }
    crc = ~crc;
    for (size_t i = 0; i < len; ++i) crc = table[(crc ^ data[i]) & 0xFFu] ^ (crc >> 8);
    return ~crc;
}
 
bool validate_tree_block_checksum(const std::vector<unsigned char>& block) {
    if (block.size() < 0x100) return false;
    const uint32_t stored = le32(block.data());
    const uint32_t calc = crc32c_update(0, block.data() + 0x20, block.size() - 0x20);
    return stored == calc;
}
 
bool validate_tree_block_header(const std::vector<unsigned char>& block,
                                uint64_t logical_bytenr,
                                uint32_t nodesize,
                                const std::array<unsigned char, 16>* fsid = nullptr,
                                uint64_t max_generation = 0) {
    if (block.size() < 101) return false;
    if (!validate_tree_block_checksum(block)) return false;
    if (le64(block.data() + 48) != logical_bytenr) return false;
    if (fsid != nullptr && !std::equal(fsid->begin(), fsid->end(), block.data() + 32)) return false;
    const uint64_t generation = le64(block.data() + 80);
    if (generation == 0) return false;
    if (max_generation != 0 && generation > max_generation + 1024) return false;
    const uint32_t nritems = le32(block.data() + 96);
    const uint8_t level = block[100];
    if (level > 8) return false;
    const size_t header_size = 101;
    const size_t item_size = (level == 0) ? 25 : 33;
    const uint64_t need = static_cast<uint64_t>(header_size) + static_cast<uint64_t>(nritems) * item_size;
    if (need > nodesize) return false;
    return true;
}
 
} // namespace
 
class BtrfsRecoveryImpl {
public:
    explicit BtrfsRecoveryImpl(DiskReader& reader) : reader_(reader) {}
 
    bool recover(uint64_t volume_offset,
                 const std::string& output_dir,
                 std::vector<RecoveredFileRecord>& recovered,
                 std::vector<std::string>& logs,
                 std::string& error) {
        std::array<unsigned char, 0x2000> sb{};
        if (!reader_.read_at(volume_offset + 0x10000, sb.data(), sb.size())) {
            error = trs("Failed to read Btrfs superblock");
            return false;
        }
        if (std::string(reinterpret_cast<const char*>(sb.data() + 0x40), 8) != "_BHRfS_M") {
            error = trs("Invalid Btrfs superblock magic");
            return false;
        }
 
        volume_offset_ = volume_offset;
        std::copy(sb.begin() + 0x20, sb.begin() + 0x20 + 16, fsid_.begin());
        root_tree_bytenr_ = le64(sb.data() + 0x50);
        chunk_root_bytenr_ = le64(sb.data() + 0x58);
        const uint64_t log_root = le64(sb.data() + 0x68);
        const uint64_t total_bytes = le64(sb.data() + 0x70);
        const uint64_t bytes_used = le64(sb.data() + 0x78);
        root_dir_objectid_ = le64(sb.data() + 0x80);
        nodesize_ = le32(sb.data() + 0x94);
        const uint32_t sectorsize = le32(sb.data() + 0x90);
        const uint32_t stripesize = le32(sb.data() + 0x9C);
        const uint32_t sys_chunk_array_size = le32(sb.data() + 0xA0);
        const uint64_t generation = le64(sb.data() + 0x10);
        super_generation_ = generation;
        if (nodesize_ == 0 || nodesize_ > 16u * 1024u * 1024u) {
            error = trs("Invalid Btrfs nodesize");
            return false;
        }
 
        out_root_ = fs::path(output_dir) / "filesystem_recovered" / "btrfs" / ("offset_" + std::to_string(volume_offset));
        fs::create_directories(out_root_ / "trees");
        fs::create_directories(out_root_ / "files");
 
        parse_system_chunk_array(sb.data() + 0x32B, sys_chunk_array_size);
        if (chunk_map_.empty()) {
            error = trs("Unable to parse Btrfs system chunk array");
            return false;
        }
 
        std::ofstream meta(out_root_ / "btrfs_metadata.txt", std::ios::binary);
        if (!meta) {
            error = trs("Unable to create output file") + std::string(": ") + (out_root_ / "btrfs_metadata.txt").string();
            return false;
        }
        meta << "Btrfs recovery metadata\n";
        meta << "volume_offset=" << volume_offset << "\n";
        meta << "root=" << root_tree_bytenr_ << " (" << to_hex(root_tree_bytenr_) << ")\n";
        meta << "chunk_root=" << chunk_root_bytenr_ << " (" << to_hex(chunk_root_bytenr_) << ")\n";
        meta << "log_root=" << log_root << " (" << to_hex(log_root) << ")\n";
        meta << "generation=" << generation << "\n";
        meta << "total_bytes=" << total_bytes << "\n";
        meta << "bytes_used=" << bytes_used << "\n";
        meta << "sectorsize=" << sectorsize << "\n";
        meta << "nodesize=" << nodesize_ << "\n";
        meta << "stripesize=" << stripesize << "\n";
        meta << "root_dir_objectid=" << root_dir_objectid_ << "\n";
        meta << "chunk_mappings=" << chunk_map_.size() << "\n";
        meta.close();
 
        if (!load_chunk_tree(logs)) {
            logs.push_back(trs("Btrfs chunk tree load was partial; continuing with system chunk mappings only."));
        }
        if (!load_root_tree(logs, error)) return false;
 
        size_t files_exported = 0;
        size_t compressed_exported = 0;
        size_t compressed_skipped = 0;
        for (const auto& [root_id, root] : roots_) {
            FsRootState state;
            if (!collect_fs_root(root_id, root, state, logs)) continue;
            files_exported += export_fs_root(root_id, root, state, recovered, compressed_exported, compressed_skipped, logs);
        }
 
        recovered.push_back({(out_root_ / "btrfs_metadata.txt").string(), "Btrfs", "/", 0, "metadata", "tree metadata"});
        logs.push_back(trs("Btrfs file recovery completed at offset") + std::string(" ") + std::to_string(volume_offset));
        logs.push_back(trs("Btrfs chunk mappings loaded") + std::string(": ") + std::to_string(chunk_map_.size()));
        logs.push_back(trs("Btrfs filesystem roots discovered") + std::string(": ") + std::to_string(roots_.size()));
        logs.push_back(trs("Btrfs files exported") + std::string(": ") + std::to_string(files_exported));
        logs.push_back(trs("Btrfs compressed extents exported") + std::string(": ") + std::to_string(compressed_exported));
        logs.push_back(trs("Btrfs compressed extents skipped") + std::string(": ") + std::to_string(compressed_skipped));
        return true;
    }
 
private:
    DiskReader& reader_;
    uint64_t volume_offset_ {0};
    uint64_t root_tree_bytenr_ {0};
    uint64_t chunk_root_bytenr_ {0};
    uint64_t root_dir_objectid_ {256};
    uint32_t nodesize_ {0};
    uint64_t super_generation_ {0};
    std::array<unsigned char, 16> fsid_{};
    fs::path out_root_;
    std::vector<ChunkMapEntry> chunk_map_;
    std::map<uint64_t, RootEntry> roots_;
    std::set<uint64_t> visited_tree_blocks_;
 
    void parse_system_chunk_array(const unsigned char* data, uint32_t size) {
        uint32_t pos = 0;
        while (pos + 17 + 48 <= size) {
            BtrfsKey key = parse_key(data + pos);
            pos += 17;
            if (key.type != BTRFS_CHUNK_ITEM_KEY) break;
            const uint64_t length = le64(data + pos + 0);
            const uint64_t stripe_len = le64(data + pos + 16);
            const uint64_t type = le64(data + pos + 24);
            const uint16_t num_stripes = le16(data + pos + 40);
            const size_t chunk_size = 48 + static_cast<size_t>(num_stripes) * 48;
            if (pos + chunk_size > size || num_stripes == 0) break;
            std::vector<ChunkStripe> stripes;
            stripes.reserve(num_stripes);
            for (uint16_t i = 0; i < num_stripes; ++i) {
                const unsigned char* sp = data + pos + 48 + static_cast<size_t>(i) * 48;
                stripes.push_back({le64(sp + 8), le64(sp + 0)});
            }
            chunk_map_.push_back({key.offset, length, stripe_len, type, num_stripes, std::move(stripes)});
            pos += static_cast<uint32_t>(chunk_size);
        }
        sort_chunk_map();
    }
 
    const ChunkMapEntry* find_chunk_entry(uint64_t logical) const {
        for (const auto& entry : chunk_map_) {
            if (logical >= entry.logical && logical < entry.logical + entry.length) return &entry;
        }
        return nullptr;
    }
 
    bool validate_raid6_candidate(const std::vector<std::vector<unsigned char>>& bufs,
                                 const std::vector<bool>& ok,
                                 const std::vector<size_t>& data_cols,
                                 const std::map<size_t, size_t>& data_index,
                                 size_t p_col,
                                 size_t q_col,
                                 const unsigned char* candidate,
                                 size_t candidate_col,
                                 size_t chunk) {
        if (chunk == 0) return true;
        if (ok[p_col]) {
            for (size_t j = 0; j < chunk; ++j) {
                uint8_t parity = 0;
                for (size_t c : data_cols) {
                    const uint8_t v = (c == candidate_col) ? candidate[j] : bufs[c][j];
                    parity ^= v;
                }
                if (parity != bufs[p_col][j]) return false;
            }
        }
        if (ok[q_col]) {
            for (size_t j = 0; j < chunk; ++j) {
                uint8_t parity = 0;
                for (size_t c : data_cols) {
                    const uint8_t v = (c == candidate_col) ? candidate[j] : bufs[c][j];
                    parity ^= gf_mul_byte(v, gf_pow2(data_index.at(c)));
                }
                if (parity != bufs[q_col][j]) return false;
            }
        }
        return true;
    }
 
    bool reconstruct_raid56_read(const ChunkMapEntry& entry,
                                 uint64_t logical,
                                 unsigned char* out,
                                 size_t chunk) {
        if (entry.stripes.empty() || entry.stripe_length == 0 || chunk == 0) return false;
        const uint64_t inner = logical - entry.logical;
        const uint64_t stripe_len = entry.stripe_length;
        const uint64_t stripe_inner = inner % stripe_len;
 
        auto read_piece = [&](size_t stripe_index, std::vector<unsigned char>& buf) -> bool {
            if (stripe_index >= entry.stripes.size()) return false;
            buf.resize(chunk);
            const uint64_t stripe_unit = (entry.type & BTRFS_BLOCK_GROUP_RAID5) ?
                ((inner / stripe_len) / (entry.stripes.size() - 1)) :
                ((inner / stripe_len) / (entry.stripes.size() - 2));
            const uint64_t physical = volume_offset_ + entry.stripes[stripe_index].physical + stripe_unit * stripe_len + stripe_inner;
            return reader_.read_at(physical, buf.data(), chunk);
        };
 
        if ((entry.type & BTRFS_BLOCK_GROUP_RAID5) != 0 && entry.stripes.size() >= 2) {
            const size_t n = entry.stripes.size();
            const uint64_t data_stripes = n - 1;
            const uint64_t stripe_unit = inner / stripe_len;
            const uint64_t row = stripe_unit / data_stripes;
            const size_t col_in_row = static_cast<size_t>(stripe_unit % data_stripes);
            const size_t parity_col = static_cast<size_t>((n - 1 - (row % n)) % n);
            size_t data_col = 0;
            std::vector<size_t> data_cols;
            for (size_t phys_col = 0, logical_col = 0; phys_col < n; ++phys_col) {
                if (phys_col == parity_col) continue;
                data_cols.push_back(phys_col);
                if (logical_col == col_in_row) data_col = phys_col;
                ++logical_col;
            }
            std::vector<std::vector<unsigned char>> bufs(n);
            std::vector<bool> ok(n, false);
            for (size_t i = 0; i < n; ++i) ok[i] = read_piece(i, bufs[i]);
            if (ok[data_col]) {
                std::copy(bufs[data_col].begin(), bufs[data_col].end(), out);
                return true;
            }
            if (!ok[parity_col]) return false;
            std::copy(bufs[parity_col].begin(), bufs[parity_col].end(), out);
            for (size_t c : data_cols) {
                if (c == data_col) continue;
                if (!ok[c]) return false;
                for (size_t j = 0; j < chunk; ++j) out[j] ^= bufs[c][j];
            }
            return true;
        }
 
        if ((entry.type & BTRFS_BLOCK_GROUP_RAID6) != 0 && entry.stripes.size() >= 3) {
            const size_t n = entry.stripes.size();
            const uint64_t data_stripes = n - 2;
            const uint64_t stripe_unit = inner / stripe_len;
            const uint64_t row = stripe_unit / data_stripes;
            const size_t col_in_row = static_cast<size_t>(stripe_unit % data_stripes);
            const size_t p_col = static_cast<size_t>((n - 1 - (row % n)) % n);
            const size_t q_col = static_cast<size_t>((n - 2 - (row % n) + n) % n);
            size_t data_col = 0;
            std::vector<size_t> data_cols;
            std::map<size_t, size_t> data_index;
            for (size_t phys_col = 0, logical_col = 0; phys_col < n; ++phys_col) {
                if (phys_col == p_col || phys_col == q_col) continue;
                data_cols.push_back(phys_col);
                data_index[phys_col] = logical_col;
                if (logical_col == col_in_row) data_col = phys_col;
                ++logical_col;
            }
            std::vector<std::vector<unsigned char>> bufs(n);
            std::vector<bool> ok(n, false);
            for (size_t i = 0; i < n; ++i) ok[i] = read_piece(i, bufs[i]);
            if (ok[data_col]) {
                std::copy(bufs[data_col].begin(), bufs[data_col].end(), out);
                return true;
            }
            std::vector<size_t> missing;
            for (size_t i = 0; i < n; ++i) if (!ok[i]) missing.push_back(i);
            if (missing.empty()) return false;
            if (missing.size() == 1) {
                if (!ok[p_col]) return false;
                std::copy(bufs[p_col].begin(), bufs[p_col].end(), out);
                for (size_t c : data_cols) {
                    if (c == data_col) continue;
                    if (!ok[c]) return false;
                    for (size_t j = 0; j < chunk; ++j) out[j] ^= bufs[c][j];
                }
                return true;
            }
            if (missing.size() > 2 || !ok[q_col]) return false;
            const size_t other = (missing[0] == data_col) ? missing[1] : missing[0];
            if (other == q_col) {
                if (!ok[p_col]) return false;
                std::copy(bufs[p_col].begin(), bufs[p_col].end(), out);
                for (size_t c : data_cols) {
                    if (c == data_col) continue;
                    if (!ok[c]) return false;
                    for (size_t j = 0; j < chunk; ++j) out[j] ^= bufs[c][j];
                }
                return true;
            }
            if (other == p_col) {
                const uint8_t a = gf_pow2(data_index[data_col]);
                const uint8_t inv = gf_inv_byte(a);
                if (inv == 0) return false;
                for (size_t j = 0; j < chunk; ++j) {
                    uint8_t acc = bufs[q_col][j];
                    for (size_t c : data_cols) {
                        if (c == data_col) continue;
                        if (!ok[c]) return false;
                        acc ^= gf_mul_byte(bufs[c][j], gf_pow2(data_index[c]));
                    }
                    out[j] = gf_mul_byte(acc, inv);
                }
                return validate_raid6_candidate(bufs, ok, data_cols, data_index, p_col, q_col, out, data_col, chunk);
            }
            if (!ok[p_col]) return false;
            if (data_index.find(other) == data_index.end()) return false;
            const uint8_t a = gf_pow2(data_index[data_col]);
            const uint8_t b = gf_pow2(data_index[other]);
            const uint8_t denom = static_cast<uint8_t>(a ^ b);
            const uint8_t denom_inv = gf_inv_byte(denom);
            if (denom_inv == 0) return false;
            for (size_t j = 0; j < chunk; ++j) {
                uint8_t s1 = bufs[p_col][j];
                uint8_t s2 = bufs[q_col][j];
                for (size_t c : data_cols) {
                    if (c == data_col || c == other) continue;
                    if (!ok[c]) return false;
                    s1 ^= bufs[c][j];
                    s2 ^= gf_mul_byte(bufs[c][j], gf_pow2(data_index[c]));
                }
                out[j] = gf_mul_byte(static_cast<uint8_t>(s2 ^ gf_mul_byte(b, s1)), denom_inv);
            }
            return validate_raid6_candidate(bufs, ok, data_cols, data_index, p_col, q_col, out, data_col, chunk);
        }
        return false;
    }
 
    void sort_chunk_map() {
        std::sort(chunk_map_.begin(), chunk_map_.end(), [](const ChunkMapEntry& a, const ChunkMapEntry& b) {
            return a.logical < b.logical;
        });
    }
 
    bool logical_to_physical(uint64_t logical, std::vector<uint64_t>& physical_candidates, uint64_t& available) const {
        physical_candidates.clear();
        for (const auto& entry : chunk_map_) {
            if (logical < entry.logical || logical >= entry.logical + entry.length) continue;
            const uint64_t inner = logical - entry.logical;
            const uint64_t stripe_len = entry.stripe_length == 0 ? entry.length : entry.stripe_length;
            const uint64_t stripe_inner = stripe_len == 0 ? 0 : (inner % stripe_len);
            available = std::min<uint64_t>(entry.length - inner, stripe_len == 0 ? entry.length - inner : stripe_len - stripe_inner);
 
            auto add_candidate = [&](size_t idx, uint64_t offset_inside) {
                if (idx >= entry.stripes.size()) return;
                physical_candidates.push_back(volume_offset_ + entry.stripes[idx].physical + offset_inside);
            };
 
            if ((entry.type & BTRFS_BLOCK_GROUP_RAID0) != 0 && !entry.stripes.empty() && stripe_len > 0) {
                const uint64_t stripe_unit = inner / stripe_len;
                const size_t stripe_index = static_cast<size_t>(stripe_unit % entry.stripes.size());
                const uint64_t stripe_round = stripe_unit / entry.stripes.size();
                add_candidate(stripe_index, stripe_round * stripe_len + stripe_inner);
                return !physical_candidates.empty();
            }
 
            if ((entry.type & BTRFS_BLOCK_GROUP_RAID10) != 0 && !entry.stripes.empty() && stripe_len > 0) {
                const uint64_t stripe_unit = inner / stripe_len;
                const size_t stripe_index = static_cast<size_t>(stripe_unit % entry.stripes.size());
                const uint64_t stripe_round = stripe_unit / entry.stripes.size();
                add_candidate(stripe_index, stripe_round * stripe_len + stripe_inner);
                for (size_t i = 0; i < entry.stripes.size(); ++i) {
                    if (i != stripe_index) add_candidate(i, stripe_round * stripe_len + stripe_inner);
                }
                return !physical_candidates.empty();
            }
 
            if (((entry.type & BTRFS_BLOCK_GROUP_RAID1) != 0) ||
                ((entry.type & BTRFS_BLOCK_GROUP_DUP) != 0)) {
                for (size_t i = 0; i < entry.stripes.size(); ++i) add_candidate(i, inner);
                return !physical_candidates.empty();
            }
 
            if ((entry.type & BTRFS_BLOCK_GROUP_RAID5) != 0 && entry.stripes.size() >= 2 && stripe_len > 0) {
                const size_t n = entry.stripes.size();
                const uint64_t data_stripes = n - 1;
                const uint64_t stripe_unit = inner / stripe_len;
                const uint64_t row = stripe_unit / data_stripes;
                const size_t col_in_row = static_cast<size_t>(stripe_unit % data_stripes);
                const size_t parity_col = static_cast<size_t>((n - 1 - (row % n)) % n);
                size_t data_col = 0;
                for (size_t phys_col = 0, logical_col = 0; phys_col < n; ++phys_col) {
                    if (phys_col == parity_col) continue;
                    if (logical_col == col_in_row) {
                        data_col = phys_col;
                        break;
                    }
                    ++logical_col;
                }
                add_candidate(data_col, row * stripe_len + stripe_inner);
                for (size_t i = 0; i < n; ++i) {
                    if (i != data_col && i != parity_col) add_candidate(i, row * stripe_len + stripe_inner);
                }
                return !physical_candidates.empty();
            }
 
            if ((entry.type & BTRFS_BLOCK_GROUP_RAID6) != 0 && entry.stripes.size() >= 3 && stripe_len > 0) {
                const size_t n = entry.stripes.size();
                const uint64_t data_stripes = n - 2;
                const uint64_t stripe_unit = inner / stripe_len;
                const uint64_t row = stripe_unit / data_stripes;
                const size_t col_in_row = static_cast<size_t>(stripe_unit % data_stripes);
                const size_t p_col = static_cast<size_t>((n - 1 - (row % n)) % n);
                const size_t q_col = static_cast<size_t>((n - 2 - (row % n) + n) % n);
                size_t data_col = 0;
                for (size_t phys_col = 0, logical_col = 0; phys_col < n; ++phys_col) {
                    if (phys_col == p_col || phys_col == q_col) continue;
                    if (logical_col == col_in_row) {
                        data_col = phys_col;
                        break;
                    }
                    ++logical_col;
                }
                add_candidate(data_col, row * stripe_len + stripe_inner);
                for (size_t i = 0; i < n; ++i) {
                    if (i != data_col && i != p_col && i != q_col) add_candidate(i, row * stripe_len + stripe_inner);
                }
                return !physical_candidates.empty();
            }
 
            if (!entry.stripes.empty()) {
                add_candidate(0, inner);
                return !physical_candidates.empty();
            }
            return false;
        }
        return false;
    }
 
    bool read_logical(uint64_t logical, void* buffer, size_t len) {
        unsigned char* out = static_cast<unsigned char*>(buffer);
        uint64_t cur = logical;
        size_t remaining = len;
        while (remaining > 0) {
            std::vector<uint64_t> physical_candidates;
            uint64_t available = 0;
            if (!logical_to_physical(cur, physical_candidates, available) || physical_candidates.empty()) return false;
            const size_t chunk = static_cast<size_t>(std::min<uint64_t>(remaining, available));
            bool ok = false;
            for (uint64_t physical : physical_candidates) {
                if (reader_.read_at(physical, out, chunk)) {
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                const ChunkMapEntry* entry = find_chunk_entry(cur);
                if (entry == nullptr || !reconstruct_raid56_read(*entry, cur, out, chunk)) return false;
            }
            cur += chunk;
            out += chunk;
            remaining -= chunk;
        }
        return true;
    }
 
    bool read_tree_block(uint64_t logical_bytenr, std::vector<unsigned char>& block) {
        block.resize(nodesize_);
        if (!read_logical(logical_bytenr, block.data(), block.size())) return false;
        if (validate_tree_block_header(block, logical_bytenr, nodesize_, &fsid_, super_generation_)) return true;
 
        const ChunkMapEntry* entry = find_chunk_entry(logical_bytenr);
        if (entry == nullptr) return false;
        const bool is_raid56 = ((entry->type & BTRFS_BLOCK_GROUP_RAID5) != 0) ||
                               ((entry->type & BTRFS_BLOCK_GROUP_RAID6) != 0);
        if (!is_raid56) return false;
        std::vector<unsigned char> rebuilt(nodesize_);
        if (!reconstruct_raid56_read(*entry, logical_bytenr, rebuilt.data(), rebuilt.size())) return false;
        if (!validate_tree_block_header(rebuilt, logical_bytenr, nodesize_, &fsid_, super_generation_)) return false;
        block.swap(rebuilt);
        return true;
    }
 
    bool load_chunk_tree(std::vector<std::string>& logs) {
        size_t before = chunk_map_.size();
        walk_tree(chunk_root_bytenr_, [&](uint64_t, uint64_t, const std::vector<unsigned char>& block, const BtrfsItem& item) {
            if (item.key.type != BTRFS_CHUNK_ITEM_KEY) return;
            if (item.data_offset + item.data_size > block.size() || item.data_size < 48) return;
            const unsigned char* p = block.data() + item.data_offset;
            const uint64_t length = le64(p + 0);
            const uint64_t stripe_len = le64(p + 16);
            const uint64_t type = le64(p + 24);
            const uint16_t num_stripes = le16(p + 40);
            if (num_stripes == 0 || item.data_size < 48u + static_cast<uint32_t>(num_stripes) * 48u) return;
            std::vector<ChunkStripe> stripes;
            stripes.reserve(num_stripes);
            for (uint16_t i = 0; i < num_stripes; ++i) {
                const unsigned char* sp = p + 48 + static_cast<size_t>(i) * 48;
                stripes.push_back({le64(sp + 8), le64(sp + 0)});
            }
            chunk_map_.push_back({item.key.offset, length, stripe_len, type, num_stripes, std::move(stripes)});
        });
        sort_chunk_map();
        logs.push_back(trs("Btrfs chunk tree parsed") + std::string(": ") + std::to_string(chunk_map_.size() - before) + " new mappings");
        return !chunk_map_.empty();
    }
 
    bool load_root_tree(std::vector<std::string>& logs, std::string& error) {
        if (root_tree_bytenr_ == 0) {
            error = trs("Invalid Btrfs root tree");
            return false;
        }
        walk_tree(root_tree_bytenr_, [&](uint64_t, uint64_t, const std::vector<unsigned char>& block, const BtrfsItem& item) {
            if (item.key.type == BTRFS_ROOT_ITEM_KEY) {
                if (item.data_offset + item.data_size > block.size() || item.data_size < 375) return;
                const unsigned char* p = block.data() + item.data_offset;
                const uint64_t root_bytenr = le64(p + 176);
                const uint8_t level = p[265];
                if (item.key.objectid >= root_dir_objectid_ && root_bytenr != 0) {
                    roots_[item.key.objectid] = {root_bytenr, level, "subvolume_" + std::to_string(item.key.objectid)};
                }
            } else if (item.key.type == BTRFS_ROOT_REF_KEY || item.key.type == BTRFS_ROOT_BACKREF_KEY) {
                if (item.data_offset + item.data_size > block.size() || item.data_size < 18) return;
                const unsigned char* p = block.data() + item.data_offset;
                const uint16_t name_len = le16(p + 16);
                if (18u + name_len > item.data_size) return;
                std::string name(reinterpret_cast<const char*>(p + 18), reinterpret_cast<const char*>(p + 18 + name_len));
                auto it = roots_.find(item.key.offset);
                if (it != roots_.end() && !name.empty()) it->second.name = sanitize(name);
            }
        });
        logs.push_back(trs("Btrfs root tree parsed") + std::string(": ") + std::to_string(roots_.size()) + " filesystem roots");
        return true;
    }
 
    template <typename LeafFn>
    void walk_tree(uint64_t logical_bytenr, LeafFn&& leaf_fn) {
        visited_tree_blocks_.clear();
        walk_tree_internal(logical_bytenr, leaf_fn);
    }
 
    template <typename LeafFn>
    void walk_tree_internal(uint64_t logical_bytenr, LeafFn& leaf_fn) {
        if (logical_bytenr == 0 || !visited_tree_blocks_.insert(logical_bytenr).second) return;
        std::vector<unsigned char> block;
        if (!read_tree_block(logical_bytenr, block) || block.size() < 101) return;
        const uint64_t owner = le64(block.data() + 88);
        const uint32_t nritems = le32(block.data() + 96);
        const uint8_t level = block[100];
        if (level == 0) {
            const size_t header_size = 101;
            const size_t item_size = 25;
            for (uint32_t i = 0; i < nritems; ++i) {
                const size_t off = header_size + static_cast<size_t>(i) * item_size;
                if (off + item_size > block.size()) break;
                BtrfsItem item;
                item.key = parse_key(block.data() + off);
                item.data_offset = le32(block.data() + off + 17);
                item.data_size = le32(block.data() + off + 21);
                leaf_fn(logical_bytenr, owner, block, item);
            }
            return;
        }
        const size_t header_size = 101;
        const size_t ptr_size = 33;
        for (uint32_t i = 0; i < nritems; ++i) {
            const size_t off = header_size + static_cast<size_t>(i) * ptr_size;
            if (off + ptr_size > block.size()) break;
            BtrfsKeyPtr ptr;
            ptr.key = parse_key(block.data() + off);
            ptr.blockptr = le64(block.data() + off + 17);
            ptr.generation = le64(block.data() + off + 25);
            walk_tree_internal(ptr.blockptr, leaf_fn);
        }
    }
 
    bool collect_fs_root(uint64_t root_id,
                         const RootEntry& root,
                         FsRootState& state,
                         std::vector<std::string>& logs) {
        (void)root_id;
        if (root.bytenr == 0) return false;
        walk_tree(root.bytenr, [&](uint64_t, uint64_t, const std::vector<unsigned char>& block, const BtrfsItem& item) {
            if (item.data_offset + item.data_size > block.size()) return;
            const unsigned char* p = block.data() + item.data_offset;
            if (item.key.type == BTRFS_INODE_ITEM_KEY) {
                if (item.data_size < 56) return;
                state.inodes[item.key.objectid] = {le64(p + 16), le32(p + 52)};
            } else if (item.key.type == BTRFS_DIR_ITEM_KEY || item.key.type == BTRFS_DIR_INDEX_KEY) {
                size_t pos = 0;
                while (pos + 30 <= item.data_size) {
                    const uint64_t child = le64(p + pos + 0);
                    const uint16_t data_len = le16(p + pos + 25);
                    const uint16_t name_len = le16(p + pos + 27);
                    if (pos + 30 + name_len + data_len > item.data_size) break;
                    std::string name(reinterpret_cast<const char*>(p + pos + 30), reinterpret_cast<const char*>(p + pos + 30 + name_len));
                    if (!name.empty() && name != "." && name != "..") {
                        state.parent_edge.try_emplace(child, DirEdge{item.key.objectid, child, sanitize(name)});
                    }
                    pos += 30 + name_len + data_len;
                }
            } else if (item.key.type == BTRFS_EXTENT_DATA_KEY) {
                if (item.data_size < 21) return;
                FileExtentInfo fe;
                fe.file_offset = item.key.offset;
                fe.ram_bytes = le64(p + 8);
                fe.compression = p[16];
                fe.type = p[20];
                if (fe.type == BTRFS_FILE_EXTENT_INLINE) {
                    fe.inline_data.assign(p + 21, p + item.data_size);
                } else if (fe.type == BTRFS_FILE_EXTENT_REG || fe.type == BTRFS_FILE_EXTENT_PREALLOC) {
                    if (item.data_size < 53) return;
                    fe.disk_bytenr = le64(p + 21);
                    fe.disk_num_bytes = le64(p + 29);
                    fe.extent_offset = le64(p + 37);
                    fe.num_bytes = le64(p + 45);
                }
                state.extents[item.key.objectid].push_back(std::move(fe));
            }
        });
        logs.push_back(trs("Btrfs fs root parsed") + std::string(": ") + root.name);
        return true;
    }
 
    fs::path inode_relative_path(uint64_t inode, const FsRootState& state) const {
        std::vector<std::string> parts;
        std::set<uint64_t> seen;
        uint64_t cur = inode;
        while (seen.insert(cur).second) {
            auto it = state.parent_edge.find(cur);
            if (it == state.parent_edge.end()) break;
            parts.push_back(it->second.name);
            cur = it->second.parent;
            if (cur == root_dir_objectid_) break;
        }
        fs::path out;
        for (auto it = parts.rbegin(); it != parts.rend(); ++it) out /= *it;
        if (out.empty()) out = fs::path("orphaned") / ("inode_" + std::to_string(inode));
        return out;
    }
 
    bool read_logical_bytes(uint64_t logical, uint64_t length, std::vector<unsigned char>& out) {
        out.resize(static_cast<size_t>(length));
        return read_logical(logical, out.data(), out.size());
    }
 
    bool render_extent(const FileExtentInfo& extent,
                       std::vector<unsigned char>& out,
                       bool& compressed_ok,
                       bool& compressed_skipped) {
        compressed_ok = false;
        compressed_skipped = false;
        if (extent.type == BTRFS_FILE_EXTENT_INLINE) {
            if (extent.compression == 0) {
                out = extent.inline_data;
                return true;
            }
            if (decompress_payload(extent.inline_data, extent.compression, static_cast<size_t>(extent.ram_bytes), out)) {
                compressed_ok = true;
                return true;
            }
            compressed_skipped = true;
            return false;
        }
        if (extent.type != BTRFS_FILE_EXTENT_REG && extent.type != BTRFS_FILE_EXTENT_PREALLOC) return false;
        if (extent.disk_bytenr == 0) {
            out.assign(static_cast<size_t>(extent.num_bytes), 0);
            return true;
        }
        std::vector<unsigned char> raw;
        if (!read_logical_bytes(extent.disk_bytenr, extent.disk_num_bytes, raw)) return false;
        if (extent.compression == 0) {
            if (extent.extent_offset > raw.size()) return false;
            const uint64_t avail = std::min<uint64_t>(extent.num_bytes, raw.size() - extent.extent_offset);
            out.assign(raw.begin() + static_cast<long>(extent.extent_offset),
                       raw.begin() + static_cast<long>(extent.extent_offset + avail));
            if (out.size() < extent.num_bytes) out.resize(static_cast<size_t>(extent.num_bytes), 0);
            return true;
        }
        std::vector<unsigned char> decomp;
        if (!decompress_payload(raw, extent.compression, static_cast<size_t>(extent.ram_bytes), decomp)) {
            compressed_skipped = true;
            return false;
        }
        compressed_ok = true;
        if (extent.extent_offset > decomp.size()) return false;
        const uint64_t avail = std::min<uint64_t>(extent.num_bytes, decomp.size() - extent.extent_offset);
        out.assign(decomp.begin() + static_cast<long>(extent.extent_offset),
                   decomp.begin() + static_cast<long>(extent.extent_offset + avail));
        if (out.size() < extent.num_bytes) out.resize(static_cast<size_t>(extent.num_bytes), 0);
        return true;
    }
 
    size_t export_fs_root(uint64_t root_id,
                          const RootEntry& root,
                          const FsRootState& state,
                          std::vector<RecoveredFileRecord>& recovered,
                          size_t& compressed_exported,
                          size_t& compressed_skipped,
                          std::vector<std::string>& logs) {
        size_t count = 0;
        fs::path root_out = out_root_ / "files" / sanitize(root.name.empty() ? ("subvolume_" + std::to_string(root_id)) : root.name);
        fs::create_directories(root_out);
        for (const auto& [inode, ino] : state.inodes) {
            const uint32_t type_bits = ino.mode & 0170000u;
            if (type_bits == 0040000u) continue;
            fs::path rel = inode_relative_path(inode, state);
            fs::path final = root_out / rel;
            fs::create_directories(final.parent_path());
            std::vector<unsigned char> file_data;
            auto ext_it = state.extents.find(inode);
            if (ext_it != state.extents.end()) {
                auto extents = ext_it->second;
                std::sort(extents.begin(), extents.end(), [](const FileExtentInfo& a, const FileExtentInfo& b) {
                    return a.file_offset < b.file_offset;
                });
                uint64_t written = 0;
                for (const auto& ext : extents) {
                    if (ext.file_offset > written) file_data.resize(static_cast<size_t>(ext.file_offset), 0);
                    std::vector<unsigned char> part;
                    bool c_ok = false;
                    bool c_skip = false;
                    if (!render_extent(ext, part, c_ok, c_skip)) {
                        if (c_skip) ++compressed_skipped;
                        part.assign(static_cast<size_t>(ext.num_bytes), 0);
                    } else if (c_ok) {
                        ++compressed_exported;
                    }
                    if (file_data.size() < ext.file_offset) file_data.resize(static_cast<size_t>(ext.file_offset), 0);
                    if (file_data.size() == ext.file_offset) {
                        file_data.insert(file_data.end(), part.begin(), part.end());
                    } else {
                        if (file_data.size() < ext.file_offset + part.size()) file_data.resize(static_cast<size_t>(ext.file_offset + part.size()), 0);
                        std::copy(part.begin(), part.end(), file_data.begin() + static_cast<long>(ext.file_offset));
                    }
                    written = std::max<uint64_t>(written, ext.file_offset + part.size());
                }
            }
            if (file_data.size() > ino.size) file_data.resize(static_cast<size_t>(ino.size));
            if (file_data.size() < ino.size) file_data.resize(static_cast<size_t>(ino.size), 0);
 
            std::ofstream out(final, std::ios::binary);
            if (!out) {
                logs.push_back(trs("Btrfs export failed") + std::string(": ") + final.string());
                continue;
            }
            if (!file_data.empty()) out.write(reinterpret_cast<const char*>(file_data.data()), static_cast<std::streamsize>(file_data.size()));
            if (!out) {
                logs.push_back(trs("Btrfs export failed") + std::string(": ") + final.string());
                continue;
            }
            recovered.push_back({final.string(), "Btrfs", final.lexically_relative(out_root_ / "files").string(), ino.size, "full", "filesystem export"});
            ++count;
        }
        return count;
    }
};
 
BtrfsRecovery::BtrfsRecovery(DiskReader& reader) : reader_(reader) {}
 
bool BtrfsRecovery::recover(uint64_t volume_offset,
                            const std::string& output_dir,
                            std::vector<RecoveredFileRecord>& recovered,
                            std::vector<std::string>& logs,
                            std::string& error) {
    BtrfsRecoveryImpl impl(reader_);
    return impl.recover(volume_offset, output_dir, recovered, logs, error);
}