ext4_recovery.cpp

Go to the documentation of this file.

#include "ext4_recovery.hpp"
#include "i18n.hpp"
#include "text_utils.hpp"
 
#include <algorithm>
#include <array>
#include <cctype>
#include <cstdint>
#include <filesystem>
#include <fstream>
#include <map>
#include <set>
#include <string>
#include <vector>
 
namespace fs = std::filesystem;
 
namespace {
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);
}
uint32_t be32(const unsigned char* p) {
    return (static_cast<uint32_t>(p[0]) << 24) |
           (static_cast<uint32_t>(p[1]) << 16) |
           (static_cast<uint32_t>(p[2]) << 8) |
           static_cast<uint32_t>(p[3]);
}
 
 
// Bug #15, #18 fix: replaced the broken ASCII-only sanitize with a
// shared UTF-8-aware implementation that also handles all Windows-illegal
// characters consistently. Italian/European filenames are now preserved.
inline std::string sanitize_path_component(const std::string& in) {
    return text_utils::sanitize_component(in);
}
 
// Range descriptor for write_ranges_to_file. Each entry covers
// `length` bytes of OUTPUT FILE CONTENT. If `zero_fill` is true,
// the bytes come from a synthesized zero buffer (= sparse hole).
// If false, bytes are read from `offset` on the disk.
struct ExportRange {
    uint64_t offset {0};
    uint64_t length {0};
    bool     zero_fill {false};
};
 
template <typename ReadFn>
bool write_ranges_to_file(ReadFn&& read_fn,
                          const std::vector<ExportRange>& ranges,
                          const fs::path& out_path,
                          uint64_t expected_size,
                          std::string& error) {
    std::ofstream out(out_path, std::ios::binary);
    if (!out) {
        error = trs("Unable to create output file") + std::string(": ") + out_path.string();
        return false;
    }
    std::vector<unsigned char> buffer(1024 * 1024);
    uint64_t written = 0;
    for (const auto& r : ranges) {
        uint64_t remaining = r.length;
        uint64_t cursor = r.offset;
        while (remaining > 0 && written < expected_size) {
            const uint64_t allowed = std::min<uint64_t>(remaining, expected_size - written);
            const size_t chunk = static_cast<size_t>(std::min<uint64_t>(buffer.size(), allowed));
            if (r.zero_fill) {
                std::fill(buffer.begin(), buffer.begin() + chunk, 0u);
            } else if (!read_fn(cursor, buffer.data(), chunk)) {
                error = trs("Read error while exporting recovered file");
                return false;
            }
            out.write(reinterpret_cast<const char*>(buffer.data()), static_cast<std::streamsize>(chunk));
            if (!out) {
                error = trs("Write error while exporting recovered file");
                return false;
            }
            cursor += chunk;
            remaining -= chunk;
            written += chunk;
        }
        if (written >= expected_size) break;
    }
    return true;
}
 
struct Ext4Inode {
    uint16_t mode {0};
    uint16_t uid {0};
    uint32_t size_lo {0};
    uint32_t atime {0};
    uint32_t ctime {0};
    uint32_t mtime {0};
    uint32_t dtime {0};
    uint16_t gid {0};
    uint16_t links_count {0};
    uint32_t blocks_lo {0};
    uint32_t flags {0};
    std::array<unsigned char, 60> block{};
    uint32_t generation {0};
    uint32_t file_acl_lo {0};
    uint32_t size_high {0};
    // Bug #19 fix: allocation flag from inode bitmap. Caller decides what to do.
    bool allocated {true};
    // For ext4_inline_data overflow: bytes of the inode AFTER the
    // GOOD_OLD_INODE_SIZE (= 128) area. This is where in-inode
    // extended attributes live, including the 'system.data' xattr that
    // holds inline_data overflow beyond the first 60 bytes. Empty if
    // inode_size_ <= 128 (no in-inode xattrs possible).
    std::vector<unsigned char> extra_bytes;
    // i_extra_isize at offset 0x80: how much of the post-128 area is
    // extended inode core fields (vs xattr space).
    uint16_t extra_isize {0};
};
 
struct ExtentRef {
    uint64_t physical_block {0};
    uint64_t logical_block {0};
    uint32_t block_count {0};
    // ext4 marks extents whose data has been ALLOCATED but never written
    // (i.e. sparse holes within the file's logical address space) by
    // setting bit 15 of ee_len. When reading these blocks, the kernel
    // returns zeros instead of whatever raw bytes happen to be at the
    // physical location. We must do the same: if uninitialized, write
    // a zero range rather than reading the disk content.
    bool uninitialized {false};
};
 
struct JournalDirentCandidate {
    uint32_t inode {0};
    uint16_t rec_len {0};
    uint8_t file_type {0};
    std::string name;
    uint32_t target_block {0};
    uint32_t sequence {0};
};
 
class Ext4RecoveryImpl {
public:
    explicit Ext4RecoveryImpl(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) {
        volume_offset_ = volume_offset;
        if (!load_superblock(error)) return false;
 
        fs::path out_root = fs::path(output_dir) / "filesystem_recovered" / "ext4" / ("offset_" + std::to_string(volume_offset));
        fs::create_directories(out_root);
 
        logs.push_back(trs("ext4 recovery started at offset") + std::string(" ") + std::to_string(volume_offset));
        build_journal_replay_map(logs);
        logs.push_back(trs("ext4 block size") + std::string(": ") + std::to_string(block_size_) + ", inode size: " + std::to_string(inode_size_));
 
        std::set<uint32_t> dir_guard;
        if (!recover_directory(2, out_root, recovered, logs, error, dir_guard, 0)) {
            return false;
        }
 
        export_journal(out_root, recovered, logs);
        logs.push_back(trs("ext4 recovery completed."));
        return true;
    }
 
private:
    DiskReader& reader_;
    uint64_t volume_offset_ {0};
    uint64_t block_size_ {0};
    uint32_t blocks_per_group_ {0};
    uint32_t inodes_per_group_ {0};
    uint16_t inode_size_ {0};
    uint64_t desc_table_offset_ {0};
    uint16_t desc_size_ {32};
    uint32_t first_data_block_ {0};
    uint64_t total_inodes_ {0};
    uint32_t journal_inode_ {0};
    std::map<uint64_t, std::pair<uint32_t, std::vector<unsigned char>>> journal_replay_blocks_;
    std::set<uint64_t> journal_revoked_blocks_;
    size_t committed_transactions_ {0};
    size_t revoke_records_ {0};
 
    bool load_superblock(std::string& error) {
        std::array<unsigned char, 1024> super{};
        if (!reader_.read_at(volume_offset_ + 1024, super.data(), super.size())) {
            error = trs("Failed to read ext4 superblock");
            return false;
        }
        if (le16(super.data() + 0x38) != 0xEF53) {
            error = trs("Invalid ext4 superblock magic");
            return false;
        }
 
        const uint32_t log_block_size = le32(super.data() + 0x18);
        block_size_ = 1024ull << log_block_size;
        first_data_block_ = le32(super.data() + 0x14);
        blocks_per_group_ = le32(super.data() + 0x20);
        inodes_per_group_ = le32(super.data() + 0x28);
        inode_size_ = le16(super.data() + 0x58);
        desc_size_ = le16(super.data() + 0xFE);
        total_inodes_ = le32(super.data() + 0x00);
        journal_inode_ = le32(super.data() + 0xE0);
 
        if (inode_size_ < 128) inode_size_ = 128;
        if (desc_size_ < 32) desc_size_ = 32;
        if (blocks_per_group_ == 0 || inodes_per_group_ == 0 || block_size_ < 1024) {
            error = trs("Unsupported ext4 geometry");
            return false;
        }
 
        const uint64_t desc_block = (block_size_ == 1024) ? 2 : 1;
        desc_table_offset_ = volume_offset_ + desc_block * block_size_;
        return true;
    }
 
    uint64_t block_to_offset(uint64_t block) const {
        return volume_offset_ + block * block_size_;
    }
 
    bool read_fs_block(uint64_t block_no, unsigned char* buffer, size_t len) {
        if (len > block_size_) return false;
        if (journal_revoked_blocks_.find(block_no) == journal_revoked_blocks_.end()) {
            auto it = journal_replay_blocks_.find(block_no);
            if (it != journal_replay_blocks_.end() && it->second.second.size() >= len) {
                std::copy_n(it->second.second.data(), len, buffer);
                return true;
            }
        }
        return reader_.read_at(block_to_offset(block_no), buffer, len);
    }
 
    bool read_volume_bytes_replayed(uint64_t volume_rel_offset, unsigned char* buffer, size_t len) {
        if (len == 0) return true;
        uint64_t pos = volume_rel_offset;
        size_t done = 0;
        while (done < len) {
            const uint64_t block_no = pos / block_size_;
            const size_t within = static_cast<size_t>(pos % block_size_);
            const size_t take = std::min<size_t>(len - done, static_cast<size_t>(block_size_ - within));
            std::vector<unsigned char> tmp(static_cast<size_t>(block_size_));
            if (!read_fs_block(block_no, tmp.data(), tmp.size())) return false;
            std::copy_n(tmp.data() + within, take, buffer + done);
            pos += take;
            done += take;
        }
        return true;
    }
 
    void build_journal_replay_map(std::vector<std::string>& logs) {
        journal_replay_blocks_.clear();
        journal_revoked_blocks_.clear();
        committed_transactions_ = 0;
        revoke_records_ = 0;
        if (journal_inode_ == 0) return;
        Ext4Inode journal_inode{};
        std::string local_error;
        if (!read_inode(journal_inode_, journal_inode, local_error)) return;
        std::vector<ExportRange> ranges;
        if (!inode_ranges(journal_inode, ranges, local_error)) return;
        std::vector<unsigned char> block(static_cast<size_t>(block_size_));
        uint64_t remaining_total = inode_size_bytes(journal_inode);
        std::vector<std::pair<uint32_t, uint32_t>> pending_tags;
        std::map<uint32_t, std::vector<unsigned char>> pending_data;
        std::set<uint32_t> pending_revokes;
        uint32_t pending_sequence = 0;
        bool transaction_open = false;
 
        auto apply_transaction = [&]() {
            if (!transaction_open) return;
            for (uint32_t blk : pending_revokes) {
                journal_revoked_blocks_.insert(blk);
                journal_replay_blocks_.erase(blk);
            }
            for (const auto& [target_block, payload] : pending_data) {
                if (pending_revokes.find(target_block) != pending_revokes.end()) continue;
                auto& slot = journal_replay_blocks_[target_block];
                if (slot.second.empty() || pending_sequence >= slot.first) {
                    slot.first = pending_sequence;
                    slot.second = payload;
                }
                journal_revoked_blocks_.erase(target_block);
            }
            if (!pending_data.empty() || !pending_revokes.empty()) ++committed_transactions_;
            revoke_records_ += pending_revokes.size();
            pending_tags.clear();
            pending_data.clear();
            pending_revokes.clear();
            transaction_open = false;
            pending_sequence = 0;
        };
 
        for (const auto& r : ranges) {
            const uint64_t offset = r.offset;
            const uint64_t length = r.length;
            uint64_t cursor = offset;
            uint64_t remaining = std::min<uint64_t>(length, remaining_total);
            while (remaining >= block_size_) {
                const uint64_t fs_block = (cursor - volume_offset_) / block_size_;
                if (!reader_.read_at(block_to_offset(fs_block), block.data(), block.size())) break;
                const uint32_t magic = be32(block.data());
                if (magic == 0xC03B3998u) {
                    const uint32_t type = be32(block.data() + 4);
                    const uint32_t sequence = be32(block.data() + 8);
                    if (type == 1u) {
                        if (transaction_open && sequence != pending_sequence && (!pending_data.empty() || !pending_revokes.empty())) {
                            apply_transaction();
                        }
                        if (!transaction_open) {
                            pending_data.clear();
                            pending_revokes.clear();
                        }
                        pending_tags.clear();
                        pending_sequence = sequence;
                        transaction_open = true;
                        size_t pos = 12;
                        while (pos + 8 <= block.size()) {
                            const uint32_t target_block = be32(block.data() + pos + 0);
                            const uint32_t flags = be32(block.data() + pos + 4);
                            if (target_block == 0) break;
                            pending_tags.push_back({target_block, flags});
                            pos += 8;
                            if ((flags & 0x8u) != 0) break;
                        }
                    } else if (type == 2u) {
                        if (transaction_open && sequence == pending_sequence) apply_transaction();
                    } else if (type == 5u) {
                        if (!transaction_open || sequence != pending_sequence) {
                            pending_data.clear();
                            pending_revokes.clear();
                            pending_tags.clear();
                            pending_sequence = sequence;
                            transaction_open = true;
                        }
                        for (size_t pos = 12; pos + 4 <= block.size(); pos += 4) {
                            const uint32_t revoked_block = be32(block.data() + pos);
                            if (revoked_block == 0) break;
                            pending_revokes.insert(revoked_block);
                        }
                    }
                } else if (transaction_open && !pending_tags.empty()) {
                    const auto [target_block, _flags] = pending_tags.front();
                    pending_tags.erase(pending_tags.begin());
                    pending_data[target_block] = block;
                }
                cursor += block_size_;
                remaining -= block_size_;
                remaining_total = remaining_total >= block_size_ ? remaining_total - block_size_ : 0;
                if (remaining_total < block_size_) break;
            }
            if (remaining_total < block_size_) break;
        }
        if (!journal_replay_blocks_.empty()) logs.push_back(trs("ext4 journal replay overlay blocks") + std::string(": ") + std::to_string(journal_replay_blocks_.size()));
        if (committed_transactions_ > 0) logs.push_back(trs("ext4 committed journal transactions") + std::string(": ") + std::to_string(committed_transactions_));
        if (revoke_records_ > 0) logs.push_back(trs("ext4 journal revoke records") + std::string(": ") + std::to_string(revoke_records_));
    }
 
    bool read_group_desc(uint32_t group, std::vector<unsigned char>& out) {
        out.resize(desc_size_);
        const uint64_t rel = desc_table_offset_ - volume_offset_ + static_cast<uint64_t>(group) * desc_size_;
        return read_volume_bytes_replayed(rel, out.data(), out.size());
    }
 
    bool inode_marked_allocated(uint32_t inode_no) {
        if (inode_no == 0 || inode_no > total_inodes_) return false;
        const uint32_t group = (inode_no - 1) / inodes_per_group_;
        const uint32_t index = (inode_no - 1) % inodes_per_group_;
        std::vector<unsigned char> gd;
        if (!read_group_desc(group, gd) || gd.size() < 12) return false;
        uint64_t inode_bitmap_block = le32(gd.data() + 4);
        if (desc_size_ >= 64 && gd.size() >= 40) {
            inode_bitmap_block |= static_cast<uint64_t>(le32(gd.data() + 0x24)) << 32;
        }
        if (inode_bitmap_block == 0) return false;
        std::vector<unsigned char> bitmap(static_cast<size_t>(block_size_));
        if (!read_fs_block(inode_bitmap_block, bitmap.data(), bitmap.size())) return false;
        const uint32_t byte_index = index / 8;
        const uint32_t bit_index = index % 8;
        if (byte_index >= bitmap.size()) return false;
        return (bitmap[byte_index] & static_cast<unsigned char>(1u << bit_index)) != 0;
    }
 
    bool read_inode(uint32_t inode_no, Ext4Inode& inode, std::string& error) {
        if (inode_no == 0 || inode_no > total_inodes_) {
            error = trs("Invalid ext4 inode number");
            return false;
        }
        const uint32_t group = (inode_no - 1) / inodes_per_group_;
        const uint32_t index = (inode_no - 1) % inodes_per_group_;
        std::vector<unsigned char> gd;
        if (!read_group_desc(group, gd)) {
            error = trs("Failed to read ext4 group descriptor");
            return false;
        }
        uint64_t inode_table_block = le32(gd.data() + 8);
        if (desc_size_ >= 64) {
            inode_table_block |= static_cast<uint64_t>(le32(gd.data() + 40)) << 32;
        }
        if (inode_table_block == 0) {
            error = trs("Invalid ext4 inode table pointer");
            return false;
        }
        const uint64_t inode_rel_offset = inode_table_block * block_size_ + static_cast<uint64_t>(index) * inode_size_;
        std::vector<unsigned char> raw(inode_size_);
        if (!read_volume_bytes_replayed(inode_rel_offset, raw.data(), raw.size())) {
            error = trs("Failed to read ext4 inode");
            return false;
        }
        inode.mode = le16(raw.data() + 0x0);
        inode.uid = le16(raw.data() + 0x2);
        inode.size_lo = le32(raw.data() + 0x4);
        inode.atime = le32(raw.data() + 0x8);
        inode.ctime = le32(raw.data() + 0xC);
        inode.mtime = le32(raw.data() + 0x10);
        inode.dtime = le32(raw.data() + 0x14);
        inode.gid = le16(raw.data() + 0x18);
        inode.links_count = le16(raw.data() + 0x1A);
        inode.blocks_lo = le32(raw.data() + 0x1C);
        inode.flags = le32(raw.data() + 0x20);
        std::copy(raw.begin() + 0x28, raw.begin() + 0x28 + 60, inode.block.begin());
        inode.generation = le32(raw.data() + 0x64);
        inode.file_acl_lo = le32(raw.data() + 0x68);
        inode.size_high = le32(raw.data() + 0x6C);
        // i_extra_isize at offset 0x80: tells us how much of the
        // post-128 area is reserved for extended inode core (vs
        // available for in-inode xattrs).
        if (inode_size_ >= 0x82) {
            inode.extra_isize = le16(raw.data() + 0x80);
            // Sanity-bound to inode_size - 128 - 4 (we need at least the
            // xattr magic to fit)
            if (inode.extra_isize > inode_size_ - 132) {
                inode.extra_isize = 0;
            }
        }
        // Save the post-128 region for xattr parsing
        if (inode_size_ > 128) {
            inode.extra_bytes.assign(raw.begin() + 128, raw.end());
        }
        // Bug #19 fix: track allocation status as a flag instead of rejecting.
        // Recovery of DELETED files MUST read unallocated inodes (dtime != 0).
        // The previous code aborted on exactly that case, making deleted-file
        // recovery silently impossible on ext4. Now we report the status and
        // let the caller decide.
        inode.allocated = inode_marked_allocated(inode_no);
        return true;
    }
 
    uint64_t inode_size_bytes(const Ext4Inode& inode) const {
        // Bug #12 fix: size_high (i_size_high) is valid for any file/dir when the
        // huge_file feature is on. The previous code restricted it to regular
        // files only (mode == 0x8000), which gave wrong sizes for large dirs and
        // for symlinks/special files >4GB on filesystems with that feature.
        const uint64_t high = static_cast<uint64_t>(inode.size_high) << 32;
        return high | inode.size_lo;
    }
 
    bool inode_is_dir(const Ext4Inode& inode) const { return (inode.mode & 0xF000) == 0x4000; }
    bool inode_is_reg(const Ext4Inode& inode) const { return (inode.mode & 0xF000) == 0x8000; }
    bool inode_uses_extents(const Ext4Inode& inode) const { return (inode.flags & 0x00080000u) != 0; }
 
    // Find the value of the in-inode xattr "system.data" (used by ext4
    // inline_data feature for the overflow beyond the first 60 bytes
    // stored in i_block[]).
    //
    // The in-inode xattr region starts at:
    //   raw_inode + 128 + i_extra_isize     (= start of xattr area)
    // Header is __le32 magic = 0xEA020000, followed by xattr entries.
    //
    // Each entry is 16 bytes + name (padded to 4-byte boundary):
    //   __u8   e_name_len
    //   __u8   e_name_index
    //   __le16 e_value_offs   (offset within xattr area, AFTER the
    //                           entries-list end)
    //   __le32 e_value_inum   (= 0 for inline value)
    //   __le32 e_value_size
    //   __le32 e_hash
    //   char   e_name[e_name_len]   (NOT null-terminated)
    //
    // For "system.data": e_name_index = 7 (system), e_name = "data"
    // (4 bytes).
    //
    // Returns true and fills `out` on success.
    bool find_inline_xattr_system_data(const Ext4Inode& inode,
                                        std::vector<unsigned char>& out) const {
        out.clear();
        if (inode.extra_bytes.empty()) return false;
        const size_t xattr_start_in_extra = inode.extra_isize;
        if (xattr_start_in_extra + 4 > inode.extra_bytes.size()) return false;
        const unsigned char* xattr_area = inode.extra_bytes.data() + xattr_start_in_extra;
        const size_t xattr_area_len = inode.extra_bytes.size() - xattr_start_in_extra;
        // Magic check: 0xEA020000 little-endian = bytes EA 02 00 00
        if (xattr_area[0] != 0xEA || xattr_area[1] != 0x02 ||
            xattr_area[2] != 0x00 || xattr_area[3] != 0x00) return false;
        // Entries start after the 4-byte magic
        size_t entry_off = 4;
        while (entry_off + 16 <= xattr_area_len) {
            const unsigned char* e = xattr_area + entry_off;
            const uint8_t e_name_len   = e[0];
            const uint8_t e_name_index = e[1];
            const uint16_t e_value_offs = le16(e + 2);
            const uint32_t e_value_inum = le32(e + 4);
            const uint32_t e_value_size = le32(e + 8);
            // Zero-name terminator
            if (e_name_len == 0 && e_name_index == 0 &&
                e_value_offs == 0 && e_value_inum == 0 &&
                e_value_size == 0) break;
            // Name padded to 4-byte boundary
            const size_t name_padded = (e_name_len + 3u) & ~3u;
            if (entry_off + 16 + name_padded > xattr_area_len) break;
            const char* name = reinterpret_cast<const char*>(e + 16);
            // Match "system.data": index 7, name "data"
            const bool is_system_data =
                e_name_index == 7 && e_name_len == 4 &&
                std::string(name, 4) == "data";
            if (is_system_data && e_value_inum == 0) {
                // Value is at e_value_offs from the START of the xattr
                // area (= where the magic is)
                if (e_value_offs + e_value_size <= xattr_area_len) {
                    out.assign(xattr_area + e_value_offs,
                                xattr_area + e_value_offs + e_value_size);
                    return true;
                }
                return false;
            }
            entry_off += 16 + name_padded;
        }
        return false;
    }
 
    bool collect_extents_from_node(uint64_t node_phys_block,
                                   std::vector<ExtentRef>& extents,
                                   std::string& error) {
        std::vector<unsigned char> block(static_cast<size_t>(block_size_));
        if (!read_fs_block(node_phys_block, block.data(), block.size())) {
            error = trs("Failed to read ext4 extent node");
            return false;
        }
        const uint16_t magic = le16(block.data() + 0);
        const uint16_t entries = le16(block.data() + 2);
        const uint16_t node_depth = le16(block.data() + 6);
        if (magic != 0xF30A) {
            error = trs("Invalid ext4 extent header");
            return false;
        }
        const unsigned char* p = block.data() + 12;
        if (node_depth == 0) {
            for (uint16_t i = 0; i < entries; ++i, p += 12) {
                const uint32_t ee_block = le32(p + 0);
                const uint16_t ee_len = le16(p + 4);
                const uint16_t ee_start_hi = le16(p + 6);
                const uint32_t ee_start_lo = le32(p + 8);
                const bool uninit = (ee_len & 0x8000u) != 0;
                const uint32_t count = uninit ? (ee_len & 0x7FFFu) : ee_len;
                if (count == 0) continue;
                ExtentRef ref;
                ref.physical_block = (static_cast<uint64_t>(ee_start_hi) << 32) | ee_start_lo;
                ref.logical_block = ee_block;
                ref.block_count = count;
                ref.uninitialized = uninit;
                extents.push_back(ref);
            }
            return true;
        }
        for (uint16_t i = 0; i < entries; ++i, p += 12) {
            const uint32_t ei_leaf_lo = le32(p + 4);
            const uint16_t ei_leaf_hi = le16(p + 8);
            const uint64_t child = (static_cast<uint64_t>(ei_leaf_hi) << 32) | ei_leaf_lo;
            if (!collect_extents_from_node(child, extents, error)) return false;
        }
        return true;
    }
 
    bool inode_extents(const Ext4Inode& inode, std::vector<ExtentRef>& extents, std::string& error) {
        if (!inode_uses_extents(inode)) {
            error = trs("ext4 inode does not use extents");
            return false;
        }
        const unsigned char* p = inode.block.data();
        const uint16_t magic = le16(p + 0);
        const uint16_t entries = le16(p + 2);
        const uint16_t depth = le16(p + 6);
        if (magic != 0xF30A) {
            error = trs("Invalid ext4 inode extent header");
            return false;
        }
        p += 12;
        if (depth == 0) {
            for (uint16_t i = 0; i < entries; ++i, p += 12) {
                const uint32_t ee_block = le32(p + 0);
                const uint16_t ee_len = le16(p + 4);
                const uint16_t ee_start_hi = le16(p + 6);
                const uint32_t ee_start_lo = le32(p + 8);
                const bool uninit = (ee_len & 0x8000u) != 0;
                const uint32_t count = uninit ? (ee_len & 0x7FFFu) : ee_len;
                if (count == 0) continue;
                ExtentRef ref;
                ref.physical_block = (static_cast<uint64_t>(ee_start_hi) << 32) | ee_start_lo;
                ref.logical_block = ee_block;
                ref.block_count = count;
                ref.uninitialized = uninit;
                extents.push_back(ref);
            }
            return true;
        }
        for (uint16_t i = 0; i < entries; ++i, p += 12) {
            const uint32_t ei_leaf_lo = le32(p + 4);
            const uint16_t ei_leaf_hi = le16(p + 8);
            const uint64_t child = (static_cast<uint64_t>(ei_leaf_hi) << 32) | ei_leaf_lo;
            if (!collect_extents_from_node(child, extents, error)) return false;
        }
        return true;
    }
 
    bool read_u32_block(uint64_t block_no, std::vector<uint32_t>& out, std::string& error) {
        std::vector<unsigned char> raw(static_cast<size_t>(block_size_));
        if (!read_fs_block(block_no, raw.data(), raw.size())) {
            error = trs("Failed to read ext4 indirect block");
            return false;
        }
        out.resize(raw.size() / 4);
        for (size_t i = 0; i < out.size(); ++i) out[i] = le32(raw.data() + i * 4);
        return true;
    }
 
    bool inode_block_map_classic(const Ext4Inode& inode, std::vector<uint64_t>& blocks, std::string& error) {
        blocks.clear();
        const uint64_t size_bytes = inode_size_bytes(inode);
        const uint64_t needed_blocks = (size_bytes + block_size_ - 1) / block_size_;
        if (needed_blocks == 0) return true;
 
        std::array<uint32_t, 15> ptrs{};
        for (size_t i = 0; i < ptrs.size(); ++i) ptrs[i] = le32(inode.block.data() + i * 4);
 
        for (size_t i = 0; i < 12 && blocks.size() < needed_blocks; ++i) {
            if (ptrs[i] != 0) blocks.push_back(ptrs[i]);
        }
 
        std::vector<uint32_t> level1;
        std::vector<uint32_t> level2;
        std::vector<uint32_t> level3;
 
        auto append_ptrs = [&](const std::vector<uint32_t>& src) {
            for (uint32_t block : src) {
                if (blocks.size() >= needed_blocks) break;
                if (block != 0) blocks.push_back(block);
            }
        };
 
        if (blocks.size() < needed_blocks && ptrs[12] != 0) {
            if (!read_u32_block(ptrs[12], level1, error)) return false;
            append_ptrs(level1);
        }
        if (blocks.size() < needed_blocks && ptrs[13] != 0) {
            if (!read_u32_block(ptrs[13], level1, error)) return false;
            for (uint32_t indirect : level1) {
                if (indirect == 0 || blocks.size() >= needed_blocks) continue;
                if (!read_u32_block(indirect, level2, error)) return false;
                append_ptrs(level2);
            }
        }
        if (blocks.size() < needed_blocks && ptrs[14] != 0) {
            if (!read_u32_block(ptrs[14], level1, error)) return false;
            for (uint32_t doubly : level1) {
                if (doubly == 0 || blocks.size() >= needed_blocks) continue;
                if (!read_u32_block(doubly, level2, error)) return false;
                for (uint32_t indirect : level2) {
                    if (indirect == 0 || blocks.size() >= needed_blocks) continue;
                    if (!read_u32_block(indirect, level3, error)) return false;
                    append_ptrs(level3);
                }
            }
        }
 
        if (blocks.size() > needed_blocks) blocks.resize(static_cast<size_t>(needed_blocks));
        return true;
    }
 
    bool inode_ranges(const Ext4Inode& inode,
                      std::vector<ExportRange>& ranges,
                      std::string& error) {
        ranges.clear();
        if (inode_uses_extents(inode)) {
            std::vector<ExtentRef> extents;
            if (!inode_extents(inode, extents, error)) return false;
            std::sort(extents.begin(), extents.end(),
                      [](const auto& a, const auto& b){
                          return a.logical_block < b.logical_block;
                      });
            // Walk extents in logical-block order. Fill any GAP between
            // consecutive extents (= sparse hole) with a zero-fill range
            // sized exactly hole_blocks * block_size_. Mark
            // UNINITIALIZED extents as zero-fill (their physical content
            // is undefined; the kernel returns zeros).
            uint64_t logical_cursor = 0;
            for (const auto& e : extents) {
                if (e.logical_block > logical_cursor) {
                    // Sparse hole between previous extent and this one
                    const uint64_t hole_blocks = e.logical_block - logical_cursor;
                    ExportRange zr;
                    zr.length = hole_blocks * block_size_;
                    zr.zero_fill = true;
                    ranges.push_back(zr);
                }
                ExportRange r;
                r.length = static_cast<uint64_t>(e.block_count) * block_size_;
                if (e.uninitialized) {
                    r.zero_fill = true;
                } else {
                    r.offset = block_to_offset(e.physical_block);
                    r.zero_fill = false;
                }
                ranges.push_back(r);
                logical_cursor = e.logical_block + e.block_count;
            }
            return true;
        }
 
        std::vector<uint64_t> blocks;
        if (!inode_block_map_classic(inode, blocks, error)) return false;
        // For classic block map: a zero entry means a sparse hole.
        for (uint64_t block : blocks) {
            ExportRange r;
            r.length = block_size_;
            if (block == 0) {
                r.zero_fill = true;
            } else {
                r.offset = block_to_offset(block);
                r.zero_fill = false;
            }
            ranges.push_back(r);
        }
        return true;
    }
 
    bool export_file(uint32_t inode_no,
                     const std::string& name,
                     const Ext4Inode& inode,
                     const fs::path& out_dir,
                     std::vector<RecoveredFileRecord>& recovered,
                     std::vector<std::string>& logs,
                     std::string& error) {
        if (!inode_is_reg(inode)) return true;
        const uint64_t size_bytes = inode_size_bytes(inode);
        if (size_bytes == 0) {
            fs::create_directories(out_dir);
            fs::path out_path = out_dir / sanitize_path_component(name);
            std::ofstream(out_path, std::ios::binary);
            recovered.push_back({out_path.string(), "ext4", name, 0, "empty", "zero-length file"});
            return true;
        }
 
        // ext4 inline_data: when EXT4_INLINE_DATA_FL (0x10000000) is set,
        // the file content lives in i_block[60] for the first 60 bytes
        // (and optionally in an xattr 'system.data' for the overflow
        // beyond 60 bytes).
        constexpr uint32_t EXT4_INLINE_DATA_FL = 0x10000000u;
        if (inode.flags & EXT4_INLINE_DATA_FL) {
            fs::create_directories(out_dir);
            fs::path out_path = out_dir / sanitize_path_component(name);
            std::string unique = out_path.string();
            int suffix = 1;
            while (fs::exists(unique)) {
                unique = (out_dir / (sanitize_path_component(name) + "_" +
                                     std::to_string(suffix++))).string();
            }
            out_path = unique;
 
            constexpr uint64_t inline_iblock_bytes = 60;  // bytes in i_block[]
 
            std::ofstream out(out_path, std::ios::binary | std::ios::trunc);
            if (!out) {
                error = trs("Cannot create ext4 file");
                return false;
            }
 
            // First 60 bytes from i_block[]
            const uint64_t first_chunk = std::min<uint64_t>(size_bytes, inline_iblock_bytes);
            out.write(reinterpret_cast<const char*>(inode.block.data()),
                      static_cast<std::streamsize>(first_chunk));
            uint64_t written = first_chunk;
 
            // Beyond 60 bytes: look up 'system.data' xattr
            if (size_bytes > inline_iblock_bytes) {
                std::vector<unsigned char> xattr_data;
                if (find_inline_xattr_system_data(inode, xattr_data)) {
                    const uint64_t need = size_bytes - inline_iblock_bytes;
                    const uint64_t can = std::min<uint64_t>(need, xattr_data.size());
                    out.write(reinterpret_cast<const char*>(xattr_data.data()),
                              static_cast<std::streamsize>(can));
                    written += can;
                    if (written == size_bytes) {
                        recovered.push_back({out_path.string(), "ext4", name,
                                             written, "full",
                                             "inline-data+xattr-overflow"});
                        logs.push_back(trs("Recovered ext4 inline-data file with "
                                           "xattr overflow:") +
                                       std::string(" ") + out_path.string());
                    } else {
                        logs.push_back(trs("ext4 inline_data file truncated "
                                           "(xattr 'system.data' too short):") +
                                       std::string(" ") + name);
                        recovered.push_back({out_path.string(), "ext4", name,
                                             written, "partial",
                                             "inline-data+xattr-partial"});
                    }
                } else {
                    logs.push_back(trs("ext4 inline_data file truncated to 60 bytes "
                                       "(xattr 'system.data' not found):") +
                                   std::string(" ") + name);
                    recovered.push_back({out_path.string(), "ext4", name,
                                         written, "partial", "inline-data-60B"});
                }
            } else {
                recovered.push_back({out_path.string(), "ext4", name,
                                     written, "full", "inline-data"});
                logs.push_back(trs("Recovered ext4 inline-data file:") +
                               std::string(" ") + out_path.string());
            }
            return true;
        }
 
        std::vector<ExportRange> ranges;
        if (!inode_ranges(inode, ranges, error)) {
            logs.push_back(trs("Skipped ext4 file without supported data mapping") + std::string(": inode ") + std::to_string(inode_no));
            error.clear();
            return true;
        }
 
        fs::create_directories(out_dir);
        fs::path out_path = out_dir / sanitize_path_component(name);
        std::string unique = out_path.string();
        int suffix = 1;
        while (fs::exists(unique)) {
            unique = (out_dir / (sanitize_path_component(name) + "_" + std::to_string(suffix++))).string();
        }
        out_path = unique;
 
        if (!write_ranges_to_file([&](uint64_t offset, unsigned char* buffer, size_t len) {
            return read_volume_bytes_replayed(offset - volume_offset_, buffer, len);
        }, ranges, out_path, size_bytes, error)) return false;
        recovered.push_back({out_path.string(), "ext4", name, size_bytes, "full", "filesystem export"});
        logs.push_back(trs("Recovered ext4 file:") + std::string(" ") + out_path.string());
        return true;
    }
 
 
    static bool looks_like_printable_name(const unsigned char* p, size_t len) {
        if (len == 0 || len > 255) return false;
        for (size_t i = 0; i < len; ++i) {
            unsigned char c = p[i];
            if (c == 0) return false;
            if (c < 32 || c == '/' || c == '\\') return false;
        }
        return true;
    }
 
    static std::string ext4_file_type_name(uint8_t t) {
        switch (t) {
            case 1: return "file";
            case 2: return "dir";
            case 3: return "char";
            case 4: return "block";
            case 5: return "fifo";
            case 6: return "socket";
            case 7: return "symlink";
            default: return "unknown";
        }
    }
 
    void scan_journal_dirents(const std::vector<unsigned char>& block,
                              uint32_t target_block,
                              uint32_t sequence,
                              std::vector<JournalDirentCandidate>& out) {
        size_t pos = 0;
        while (pos + 8 <= block.size()) {
            const uint32_t inode = le32(block.data() + pos + 0);
            const uint16_t rec_len = le16(block.data() + pos + 4);
            const uint8_t name_len = block[pos + 6];
            const uint8_t file_type = block[pos + 7];
            if (rec_len < 8 || rec_len > block.size() - pos) {
                ++pos;
                continue;
            }
            if (inode != 0 && name_len > 0 && 8u + name_len <= rec_len && looks_like_printable_name(block.data() + pos + 8, name_len)) {
                std::string name(reinterpret_cast<const char*>(block.data() + pos + 8), name_len);
                if (name != "." && name != "..") {
                    out.push_back({inode, rec_len, file_type, name, target_block, sequence});
                }
            }
            pos += rec_len;
        }
    }
 
    void export_journal(const fs::path& out_root,
                        std::vector<RecoveredFileRecord>& recovered,
                        std::vector<std::string>& logs) {
        if (journal_inode_ == 0) return;
 
        Ext4Inode journal_inode{};
        std::string local_error;
        if (!read_inode(journal_inode_, journal_inode, local_error)) {
            logs.push_back(trs("ext4 journal inode could not be read"));
            return;
        }
 
        std::vector<ExportRange> ranges;
        if (!inode_ranges(journal_inode, ranges, local_error)) {
            logs.push_back(trs("ext4 journal mapping unsupported or unreadable"));
            return;
        }
 
        const fs::path journal_root = out_root / "journal";
        fs::create_directories(journal_root);
        const uint64_t journal_size = inode_size_bytes(journal_inode);
        const fs::path journal_copy = journal_root / "journal_copy.bin";
        if (!write_ranges_to_file([&](uint64_t offset, unsigned char* buffer, size_t len) {
                return reader_.read_at(offset, buffer, len);
            }, ranges, journal_copy, journal_size, local_error)) {
            logs.push_back(trs("ext4 journal export failed") + std::string(": ") + local_error);
            return;
        }
        recovered.push_back({journal_copy.string(), "ext4", "journal/journal_copy.bin", journal_size, "metadata", "journal copy"});
 
        std::ofstream info(journal_root / "journal_info.txt", std::ios::binary);
        if (!info) return;
 
        std::map<uint32_t, size_t> type_counts;
        std::vector<unsigned char> block(static_cast<size_t>(block_size_));
        uint64_t remaining_total = journal_size;
        size_t metadata_blocks_exported = 0;
        size_t payload_blocks_exported = 0;
        const fs::path replay_dir = journal_root / "replayed_metadata";
        fs::create_directories(replay_dir);
 
        std::vector<std::pair<uint32_t, uint32_t>> pending_tags;
        std::vector<JournalDirentCandidate> journal_dirents;
        uint32_t pending_sequence = 0;
        uint64_t block_index = 0;
        for (const auto& r : ranges) {
            const uint64_t offset = r.offset;
            const uint64_t length = r.length;
            uint64_t cursor = offset;
            uint64_t remaining = std::min<uint64_t>(length, remaining_total);
            while (remaining >= block_size_) {
                if (!reader_.read_at(cursor, block.data(), block.size())) break;
                const uint32_t magic = be32(block.data());
                if (magic == 0xC03B3998u) {
                    const uint32_t type = be32(block.data() + 4);
                    const uint32_t sequence = be32(block.data() + 8);
                    type_counts[type]++;
                    info << "block=" << block_index << " type=" << type << " sequence=" << sequence << "\n";
                    pending_tags.clear();
                    pending_sequence = sequence;
                    if (type == 1u) {
                        size_t pos = 12;
                        while (pos + 8 <= block.size()) {
                            const uint32_t target_block = be32(block.data() + pos + 0);
                            const uint32_t flags = be32(block.data() + pos + 4);
                            if (target_block == 0) break;
                            pending_tags.push_back({target_block, flags});
                            info << "descriptor[" << block_index << "].tag_target=" << target_block
                                 << " flags=" << flags << "\n";
                            pos += 8;
                            if ((flags & 0x8u) != 0) break;
                        }
                    } else if (type == 5u) {
                        const fs::path block_file = replay_dir / ("journal_block_" + std::to_string(block_index) + "_revoke.bin");
                        std::ofstream bout(block_file, std::ios::binary);
                        if (bout) {
                            bout.write(reinterpret_cast<const char*>(block.data()), static_cast<std::streamsize>(block.size()));
                            ++metadata_blocks_exported;
                        }
                        for (size_t pos = 12; pos + 4 <= block.size(); pos += 4) {
                            const uint32_t revoked_block = be32(block.data() + pos);
                            if (revoked_block == 0) break;
                            info << "revoke[" << block_index << "].target_block=" << revoked_block << " sequence=" << sequence << "\n";
                        }
                    }
                } else if (!pending_tags.empty()) {
                    const auto [target_block, flags] = pending_tags.front();
                    pending_tags.erase(pending_tags.begin());
                    const fs::path block_file = replay_dir /
                        ("journal_payload_" + std::to_string(block_index) +
                         "_target_" + std::to_string(target_block) +
                         "_seq_" + std::to_string(pending_sequence) + ".bin");
                    std::ofstream bout(block_file, std::ios::binary);
                    if (bout) {
                        bout.write(reinterpret_cast<const char*>(block.data()), static_cast<std::streamsize>(block.size()));
                        ++payload_blocks_exported;
                    }
                    info << "payload[" << block_index << "].target_block=" << target_block
                         << " flags=" << flags << " sequence=" << pending_sequence << "\n";
                    scan_journal_dirents(block, target_block, pending_sequence, journal_dirents);
                }
                cursor += block_size_;
                remaining -= block_size_;
                remaining_total = remaining_total >= block_size_ ? remaining_total - block_size_ : 0;
                ++block_index;
                if (remaining_total < block_size_) break;
            }
            if (remaining_total < block_size_) break;
        }
 
        info << "journal_inode=" << journal_inode_ << "\n";
        info << "journal_size=" << journal_size << "\n";
        for (const auto& [type, count] : type_counts) {
            info << "type_" << type << "=" << count << "\n";
        }
        info << "metadata_blocks_exported=" << metadata_blocks_exported << "\n";
        info << "payload_blocks_exported=" << payload_blocks_exported << "\n";
        info << "replay_overlay_blocks=" << journal_replay_blocks_.size() << "\n";
        if (!journal_dirents.empty()) {
            std::ofstream dirent_out(journal_root / "recovered_dirents.txt", std::ios::binary);
            std::set<uint32_t> exported_candidate_inodes;
            const fs::path candidate_dir = journal_root / "candidate_files";
            fs::create_directories(candidate_dir);
            for (const auto& d : journal_dirents) {
                dirent_out << "inode=" << d.inode << " type=" << ext4_file_type_name(d.file_type)
                           << " name=" << d.name << " target_block=" << d.target_block
                           << " sequence=" << d.sequence << "\n";
                if (d.file_type == 1 && exported_candidate_inodes.insert(d.inode).second) {
                    if (!inode_marked_allocated(d.inode)) continue;
                    Ext4Inode cand{};
                    std::string cand_error;
                    if (read_inode(d.inode, cand, cand_error) && inode_is_reg(cand)) {
                        export_file(d.inode, sanitize_path_component(d.name), cand, candidate_dir, recovered, logs, cand_error);
                    }
                }
            }
            info << "dirent_candidates=" << journal_dirents.size() << "\n";
        } else {
            info << "dirent_candidates=0\n";
        }
        logs.push_back(trs("ext4 journal exported") + std::string(": ") + journal_copy.string());
    }
 
    bool recover_directory(uint32_t inode_no,
                           const fs::path& out_dir,
                           std::vector<RecoveredFileRecord>& recovered,
                           std::vector<std::string>& logs,
                           std::string& error,
                           std::set<uint32_t>& dir_guard,
                           int depth) {
        if (depth > 64) return true;
        if (!dir_guard.insert(inode_no).second) return true;
 
        Ext4Inode inode;
        if (!read_inode(inode_no, inode, error)) return false;
        if (!inode_is_dir(inode)) return true;
 
        std::vector<ExportRange> ranges;
        if (!inode_ranges(inode, ranges, error)) {
            logs.push_back(trs("Skipped ext4 directory without supported data mapping") + std::string(": inode ") + std::to_string(inode_no));
            error.clear();
            return true;
        }
 
        std::vector<unsigned char> block(static_cast<size_t>(block_size_));
        for (const auto& r : ranges) {
            const uint64_t offset = r.offset;
            const uint64_t length = r.length;
            uint64_t cursor = offset;
            uint64_t remaining = length;
            while (remaining >= block_size_) {
                if (!read_volume_bytes_replayed(cursor - volume_offset_, block.data(), block.size())) break;
                size_t pos = 0;
                while (pos + 8 <= block.size()) {
                    const uint32_t entry_inode = le32(block.data() + pos + 0);
                    const uint16_t rec_len = le16(block.data() + pos + 4);
                    const uint8_t name_len = block[pos + 6];
                    const uint8_t file_type = block[pos + 7];
                    if (rec_len < 8 || pos + rec_len > block.size()) break;
                    if (entry_inode == 0) { pos += rec_len; continue; }
                    std::string name(reinterpret_cast<const char*>(block.data() + pos + 8),
                                     reinterpret_cast<const char*>(block.data() + pos + 8 + std::min<uint16_t>(name_len, rec_len - 8)));
                    name = sanitize_path_component(name);
                    if (name.empty() || name == "." || name == "..") {
                        pos += rec_len;
                        continue;
                    }
                    if (file_type == 2) {
                        fs::path subdir = out_dir / name;
                        fs::create_directories(subdir);
                        if (!recover_directory(entry_inode, subdir, recovered, logs, error, dir_guard, depth + 1)) return false;
                    } else if (file_type == 1 || file_type == 7 || file_type == 0) {
                        Ext4Inode child;
                        if (read_inode(entry_inode, child, error)) {
                            if (!export_file(entry_inode, name, child, out_dir, recovered, logs, error)) return false;
                        } else {
                            error.clear();
                        }
                    }
                    pos += rec_len;
                }
                cursor += block_size_;
                remaining -= block_size_;
            }
        }
        return true;
    }
};
} // namespace
 
Ext4Recovery::Ext4Recovery(DiskReader& reader) : reader_(reader) {}
 
bool Ext4Recovery::recover(uint64_t volume_offset,
                           const std::string& output_dir,
                           std::vector<RecoveredFileRecord>& recovered,
                           std::vector<std::string>& logs,
                           std::string& error) {
    Ext4RecoveryImpl impl(reader_);
    return impl.recover(volume_offset, output_dir, recovered, logs, error);
}