Public Member Functions
	BtrfsRecoveryImpl (DiskReader &reader)
bool	recover (uint64_t volume_offset, const std::string &output_dir, std::vector< RecoveredFileRecord > &recovered, std::vector< std::string > &logs, std::string &error)

Private Member Functions
void	parse_system_chunk_array (const unsigned char *data, uint32_t size)
const ChunkMapEntry *	find_chunk_entry (uint64_t logical) const
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)
bool	reconstruct_raid56_read (const ChunkMapEntry &entry, uint64_t logical, unsigned char *out, size_t chunk)
void	sort_chunk_map ()
bool	logical_to_physical (uint64_t logical, std::vector< uint64_t > &physical_candidates, uint64_t &available) const
bool	read_logical (uint64_t logical, void *buffer, size_t len)
bool	read_tree_block (uint64_t logical_bytenr, std::vector< unsigned char > &block)
bool	load_chunk_tree (std::vector< std::string > &logs)
bool	load_root_tree (std::vector< std::string > &logs, std::string &error)
template<typename LeafFn>
void	walk_tree (uint64_t logical_bytenr, LeafFn &&leaf_fn)
template<typename LeafFn>
void	walk_tree_internal (uint64_t logical_bytenr, LeafFn &leaf_fn)
bool	collect_fs_root (uint64_t root_id, const RootEntry &root, FsRootState &state, std::vector< std::string > &logs)
fs::path	inode_relative_path (uint64_t inode, const FsRootState &state) const
bool	read_logical_bytes (uint64_t logical, uint64_t length, std::vector< unsigned char > &out)
bool	render_extent (const FileExtentInfo &extent, std::vector< unsigned char > &out, bool &compressed_ok, bool &compressed_skipped)
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)

Private Attributes
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_

Detailed Description

Definition at line 348 of file btrfs_recovery.cpp.

Constructor & Destructor Documentation

◆ BtrfsRecoveryImpl()

BtrfsRecoveryImpl::BtrfsRecoveryImpl ( DiskReader & reader )

inlineexplicit

Definition at line 350 of file btrfs_recovery.cpp.

350: reader_(reader) {}

BtrfsRecoveryImpl::reader_

DiskReader & reader_

Definition btrfs_recovery.cpp:441

References reader_.

Member Function Documentation

◆ collect_fs_root()

bool BtrfsRecoveryImpl::collect_fs_root	(	uint64_t	root_id,
		const RootEntry &	root,
		FsRootState &	state,
		std::vector< std::string > &	logs )

inlineprivate

Definition at line 895 of file btrfs_recovery.cpp.

                                                     {
        (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;
    }

References anonymous_namespace{btrfs_recovery.cpp}::BTRFS_DIR_INDEX_KEY, anonymous_namespace{btrfs_recovery.cpp}::BTRFS_DIR_ITEM_KEY, anonymous_namespace{btrfs_recovery.cpp}::RootEntry::bytenr, anonymous_namespace{btrfs_recovery.cpp}::BtrfsItem::key, anonymous_namespace{btrfs_recovery.cpp}::BtrfsKey::type, and walk_tree().

Referenced by recover().

◆ export_fs_root()

size_t BtrfsRecoveryImpl::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 )

inlineprivate

Definition at line 1012 of file btrfs_recovery.cpp.

                                                      {
        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;
    }

References anonymous_namespace{btrfs_recovery.cpp}::FsRootState::extents, inode_relative_path(), anonymous_namespace{btrfs_recovery.cpp}::FsRootState::inodes, anonymous_namespace{btrfs_recovery.cpp}::RootEntry::name, out_root_, render_extent(), anonymous_namespace{btrfs_recovery.cpp}::sanitize(), and trs().

Referenced by recover().

◆ find_chunk_entry()

const ChunkMapEntry * BtrfsRecoveryImpl::find_chunk_entry ( uint64_t logical ) const

inlineprivate

Definition at line 478 of file btrfs_recovery.cpp.

                                                                  {
        for (const auto& entry : chunk_map_) {
            if (logical >= entry.logical && logical < entry.logical + entry.length) return &entry;
        }
        return nullptr;
    }

References chunk_map_.

Referenced by read_logical(), and read_tree_block().

◆ inode_relative_path()

fs::path BtrfsRecoveryImpl::inode_relative_path	(	uint64_t	inode,
		const FsRootState &	state ) const

inlineprivate

Definition at line 943 of file btrfs_recovery.cpp.

                                                                               {
        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;
    }

References anonymous_namespace{btrfs_recovery.cpp}::FsRootState::parent_edge, and root_dir_objectid_.

Referenced by export_fs_root().

◆ load_chunk_tree()

bool BtrfsRecoveryImpl::load_chunk_tree ( std::vector< std::string > & logs )

inlineprivate

Definition at line 802 of file btrfs_recovery.cpp.

                                                     {
        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();
    }

Referenced by recover().

◆ load_root_tree()

bool BtrfsRecoveryImpl::load_root_tree	(	std::vector< std::string > &	logs,
		std::string &	error )

inlineprivate

Definition at line 826 of file btrfs_recovery.cpp.

                                                                      {
        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;
    }

Referenced by recover().

◆ logical_to_physical()

bool BtrfsRecoveryImpl::logical_to_physical	(	uint64_t	logical,
		std::vector< uint64_t > &	physical_candidates,
		uint64_t &	available ) const

inlineprivate

Definition at line 663 of file btrfs_recovery.cpp.

                                                                                                                    {
        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;
    }

References anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_DUP, anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID0, anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID1, anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID10, anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID5, anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID6, chunk_map_, and volume_offset_.

Referenced by read_logical().

◆ parse_system_chunk_array()

void BtrfsRecoveryImpl::parse_system_chunk_array	(	const unsigned char *	data,
		uint32_t	size )

inlineprivate

Definition at line 454 of file btrfs_recovery.cpp.

                                                                            {
        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();
    }

References anonymous_namespace{btrfs_recovery.cpp}::BTRFS_CHUNK_ITEM_KEY, chunk_map_, anonymous_namespace{btrfs_recovery.cpp}::le16(), anonymous_namespace{btrfs_recovery.cpp}::le64(), anonymous_namespace{btrfs_recovery.cpp}::BtrfsKey::offset, anonymous_namespace{btrfs_recovery.cpp}::parse_key(), sort_chunk_map(), and anonymous_namespace{btrfs_recovery.cpp}::BtrfsKey::type.

Referenced by recover().

◆ read_logical()

bool BtrfsRecoveryImpl::read_logical	(	uint64_t	logical,
		void *	buffer,
		size_t	len )

inlineprivate

Definition at line 758 of file btrfs_recovery.cpp.

                                                                  {
        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;
    }

References find_chunk_entry(), logical_to_physical(), DiskReader::read_at(), reader_, and reconstruct_raid56_read().

Referenced by read_logical_bytes(), and read_tree_block().

◆ read_logical_bytes()

bool BtrfsRecoveryImpl::read_logical_bytes	(	uint64_t	logical,
		uint64_t	length,
		std::vector< unsigned char > &	out )

inlineprivate

Definition at line 960 of file btrfs_recovery.cpp.

                                                                                              {
        out.resize(static_cast<size_t>(length));
        return read_logical(logical, out.data(), out.size());
    }

References read_logical().

Referenced by render_extent().

◆ read_tree_block()

bool BtrfsRecoveryImpl::read_tree_block	(	uint64_t	logical_bytenr,
		std::vector< unsigned char > &	block )

inlineprivate

Definition at line 785 of file btrfs_recovery.cpp.

                                                                                   {
        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;
    }

References anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID5, anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID6, find_chunk_entry(), fsid_, nodesize_, read_logical(), reconstruct_raid56_read(), super_generation_, anonymous_namespace{btrfs_recovery.cpp}::ChunkMapEntry::type, and anonymous_namespace{btrfs_recovery.cpp}::validate_tree_block_header().

Referenced by walk_tree_internal().

◆ reconstruct_raid56_read()

bool BtrfsRecoveryImpl::reconstruct_raid56_read	(	const ChunkMapEntry &	entry,
		uint64_t	logical,
		unsigned char *	out,
		size_t	chunk )

inlineprivate

Definition at line 518 of file btrfs_recovery.cpp.

                                               {
        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;
    }

Referenced by read_logical(), and read_tree_block().

◆ recover()

bool BtrfsRecoveryImpl::recover	(	uint64_t	volume_offset,
		const std::string &	output_dir,
		std::vector< RecoveredFileRecord > &	recovered,
		std::vector< std::string > &	logs,
		std::string &	error )

inline

Definition at line 352 of file btrfs_recovery.cpp.

                                   {
        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;
    }

References chunk_map_, chunk_root_bytenr_, collect_fs_root(), export_fs_root(), fsid_, anonymous_namespace{btrfs_recovery.cpp}::le32(), anonymous_namespace{btrfs_recovery.cpp}::le64(), load_chunk_tree(), load_root_tree(), nodesize_, out_root_, parse_system_chunk_array(), DiskReader::read_at(), reader_, root_dir_objectid_, root_tree_bytenr_, roots_, super_generation_, anonymous_namespace{btrfs_recovery.cpp}::to_hex(), trs(), and volume_offset_.

Referenced by BtrfsRecovery::recover().

◆ render_extent()

bool BtrfsRecoveryImpl::render_extent	(	const FileExtentInfo &	extent,
		std::vector< unsigned char > &	out,
		bool &	compressed_ok,
		bool &	compressed_skipped )

inlineprivate

Definition at line 965 of file btrfs_recovery.cpp.

                                                 {
        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;
    }

Referenced by export_fs_root().

◆ sort_chunk_map()

void BtrfsRecoveryImpl::sort_chunk_map ( )

inlineprivate

Definition at line 657 of file btrfs_recovery.cpp.

                          {
        std::sort(chunk_map_.begin(), chunk_map_.end(), [](const ChunkMapEntry& a, const ChunkMapEntry& b) {
            return a.logical < b.logical;
        });
    }

References chunk_map_.

Referenced by load_chunk_tree(), and parse_system_chunk_array().

◆ validate_raid6_candidate()

bool BtrfsRecoveryImpl::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 )

inlineprivate

Definition at line 485 of file btrfs_recovery.cpp.

                                               {
        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;
    }

References anonymous_namespace{btrfs_recovery.cpp}::gf_mul_byte(), and anonymous_namespace{btrfs_recovery.cpp}::gf_pow2().

Referenced by reconstruct_raid56_read().

◆ walk_tree()

template<typename LeafFn>

void BtrfsRecoveryImpl::walk_tree	(	uint64_t	logical_bytenr,
		LeafFn &&	leaf_fn )

inlineprivate

Definition at line 855 of file btrfs_recovery.cpp.

                                                              {
        visited_tree_blocks_.clear();
        walk_tree_internal(logical_bytenr, leaf_fn);
    }

References visited_tree_blocks_, and walk_tree_internal().

Referenced by collect_fs_root(), load_chunk_tree(), and load_root_tree().

◆ walk_tree_internal()

template<typename LeafFn>

void BtrfsRecoveryImpl::walk_tree_internal	(	uint64_t	logical_bytenr,
		LeafFn &	leaf_fn )

inlineprivate

Definition at line 861 of file btrfs_recovery.cpp.

                                                                      {
        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);
        }
    }

Referenced by walk_tree(), and walk_tree_internal().

Member Data Documentation

◆ chunk_map_

std::vector<ChunkMapEntry> BtrfsRecoveryImpl::chunk_map_

private

Definition at line 450 of file btrfs_recovery.cpp.

Referenced by find_chunk_entry(), load_chunk_tree(), logical_to_physical(), parse_system_chunk_array(), recover(), and sort_chunk_map().

◆ chunk_root_bytenr_

uint64_t BtrfsRecoveryImpl::chunk_root_bytenr_ {0}

private

Definition at line 444 of file btrfs_recovery.cpp.

Referenced by load_chunk_tree(), and recover().

◆ fsid_

std::array<unsigned char, 16> BtrfsRecoveryImpl::fsid_ {}

private

Definition at line 448 of file btrfs_recovery.cpp.

Referenced by read_tree_block(), and recover().

◆ nodesize_

uint32_t BtrfsRecoveryImpl::nodesize_ {0}

private

Definition at line 446 of file btrfs_recovery.cpp.

Referenced by read_tree_block(), and recover().

◆ out_root_

fs::path BtrfsRecoveryImpl::out_root_

private

Definition at line 449 of file btrfs_recovery.cpp.

Referenced by export_fs_root(), and recover().

◆ reader_

DiskReader& BtrfsRecoveryImpl::reader_

private

Definition at line 441 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl(), read_logical(), reconstruct_raid56_read(), and recover().

◆ root_dir_objectid_

uint64_t BtrfsRecoveryImpl::root_dir_objectid_ {256}

private

Definition at line 445 of file btrfs_recovery.cpp.

Referenced by inode_relative_path(), load_root_tree(), and recover().

◆ root_tree_bytenr_

uint64_t BtrfsRecoveryImpl::root_tree_bytenr_ {0}

private

Definition at line 443 of file btrfs_recovery.cpp.

Referenced by load_root_tree(), and recover().

◆ roots_

std::map<uint64_t, RootEntry> BtrfsRecoveryImpl::roots_

private

Definition at line 451 of file btrfs_recovery.cpp.

Referenced by load_root_tree(), and recover().

◆ super_generation_

uint64_t BtrfsRecoveryImpl::super_generation_ {0}

private

Definition at line 447 of file btrfs_recovery.cpp.

Referenced by read_tree_block(), and recover().

◆ visited_tree_blocks_

std::set<uint64_t> BtrfsRecoveryImpl::visited_tree_blocks_

private

Definition at line 452 of file btrfs_recovery.cpp.

Referenced by walk_tree(), and walk_tree_internal().

◆ volume_offset_

uint64_t BtrfsRecoveryImpl::volume_offset_ {0}

private

Definition at line 442 of file btrfs_recovery.cpp.

Referenced by logical_to_physical(), reconstruct_raid56_read(), and recover().

The documentation for this class was generated from the following file:

BastionGuard/thirdparty/bastionguard-recovery-data/src/btrfs_recovery.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ BtrfsRecoveryImpl()

Member Function Documentation

◆ collect_fs_root()

◆ export_fs_root()

◆ find_chunk_entry()

◆ inode_relative_path()

◆ load_chunk_tree()

◆ load_root_tree()

◆ logical_to_physical()

◆ parse_system_chunk_array()

◆ read_logical()

◆ read_logical_bytes()

◆ read_tree_block()

◆ reconstruct_raid56_read()

◆ recover()

◆ render_extent()

◆ sort_chunk_map()

◆ validate_raid6_candidate()

◆ walk_tree()

◆ walk_tree_internal()

Member Data Documentation

◆ chunk_map_

◆ chunk_root_bytenr_

◆ fsid_

◆ nodesize_

◆ out_root_

◆ reader_

◆ root_dir_objectid_

◆ root_tree_bytenr_

◆ roots_

◆ super_generation_

◆ visited_tree_blocks_

◆ volume_offset_