Classes
struct	BtrfsKey
struct	BtrfsItem
struct	BtrfsKeyPtr
struct	ChunkStripe
struct	ChunkMapEntry
struct	RootEntry
struct	InodeInfo
struct	DirEdge
struct	FileExtentInfo
struct	FsRootState

Functions
uint16_t	le16 (const unsigned char *p)
uint32_t	le32 (const unsigned char *p)
uint64_t	le64 (const unsigned char *p)
std::string	sanitize (const std::string &in)
std::string	to_hex (uint64_t v)
BtrfsKey	parse_key (const unsigned char *p)
bool	decompress_payload (const std::vector< unsigned char > &in, uint8_t compression, size_t expected_size, std::vector< unsigned char > &out)
uint8_t	gf_mul_byte (uint8_t a, uint8_t b)
uint8_t	gf_pow2 (size_t exp)
uint8_t	gf_inv_byte (uint8_t a)
uint32_t	crc32c_update (uint32_t crc, const unsigned char *data, size_t len)
bool	validate_tree_block_checksum (const std::vector< unsigned char > &block)
bool	validate_tree_block_header (const std::vector< unsigned char > &block, uint64_t logical_bytenr, uint32_t nodesize, const std::array< unsigned char, 16 > *fsid=nullptr, uint64_t max_generation=0)

Variables
constexpr uint8_t	BTRFS_INODE_ITEM_KEY = 1
constexpr uint8_t	BTRFS_INODE_REF_KEY = 12
constexpr uint8_t	BTRFS_DIR_ITEM_KEY = 84
constexpr uint8_t	BTRFS_DIR_INDEX_KEY = 96
constexpr uint8_t	BTRFS_EXTENT_DATA_KEY = 108
constexpr uint8_t	BTRFS_ROOT_ITEM_KEY = 132
constexpr uint8_t	BTRFS_ROOT_BACKREF_KEY = 144
constexpr uint8_t	BTRFS_ROOT_REF_KEY = 156
constexpr uint8_t	BTRFS_CHUNK_ITEM_KEY = 228
constexpr uint8_t	BTRFS_FILE_EXTENT_INLINE = 0
constexpr uint8_t	BTRFS_FILE_EXTENT_REG = 1
constexpr uint8_t	BTRFS_FILE_EXTENT_PREALLOC = 2
constexpr uint64_t	BTRFS_BLOCK_GROUP_RAID0 = 1ull << 3
constexpr uint64_t	BTRFS_BLOCK_GROUP_RAID1 = 1ull << 4
constexpr uint64_t	BTRFS_BLOCK_GROUP_DUP = 1ull << 5
constexpr uint64_t	BTRFS_BLOCK_GROUP_RAID10 = 1ull << 6
constexpr uint64_t	BTRFS_BLOCK_GROUP_RAID5 = 1ull << 7
constexpr uint64_t	BTRFS_BLOCK_GROUP_RAID6 = 1ull << 8

Function Documentation

◆ crc32c_update()

uint32_t anonymous_namespace{btrfs_recovery.cpp}::crc32c_update	(	uint32_t	crc,
		const unsigned char *	data,
		size_t	len )

Definition at line 301 of file btrfs_recovery.cpp.

                                                                            {
    static uint32_t table[256]{};
    static bool init = false;
    if (!init) {
        for (uint32_t i = 0; i < 256; ++i) {
            uint32_t r = i;
            for (int j = 0; j < 8; ++j) r = (r >> 1) ^ (0x82F63B78u & static_cast<uint32_t>(-(static_cast<int32_t>(r & 1u))));
            table[i] = r;
        }
        init = true;
    }
    crc = ~crc;
    for (size_t i = 0; i < len; ++i) crc = table[(crc ^ data[i]) & 0xFFu] ^ (crc >> 8);
    return ~crc;
}

References crc32c_update().

Referenced by crc32c_update(), and validate_tree_block_checksum().

◆ decompress_payload()

bool anonymous_namespace{btrfs_recovery.cpp}::decompress_payload	(	const std::vector< unsigned char > &	in,
		uint8_t	compression,
		size_t	expected_size,
		std::vector< unsigned char > &	out )

Definition at line 182 of file btrfs_recovery.cpp.

                                                       {
    if (compression == 0) {
        out = in;
        if (out.size() > expected_size) out.resize(expected_size);
        return true;
    }
#ifdef HAVE_ZLIB
    if (compression == 1) {
        // Btrfs zlib: single zlib stream per extent (max 128 KiB output).
        out.resize(expected_size);
        uLongf dest_len = static_cast<uLongf>(out.size());
        int rc = ::uncompress(out.data(), &dest_len, in.data(), static_cast<uLong>(in.size()));
        if (rc != Z_OK) return false;
        out.resize(static_cast<size_t>(dest_len));
        return true;
    }
#endif
#ifdef HAVE_LZO
    if (compression == 2) {
        // Btrfs LZO chunked decoder.
        constexpr size_t kBtrfsLzoPageSize = 4096;
        if (in.size() < 4) return false;
        const uint32_t total_len = le32(in.data());
        if (total_len > in.size()) return false;
        // Chunks start at offset 4 (after the total length header).
        // The kernel writer pads chunks so that no chunk header straddles
        // a 4 KiB page boundary in the COMPRESSED stream. We mirror that:
        // when the next chunk header would straddle a page, we skip to
        // the next page.
        size_t pos = 4;
        out.clear();
        out.reserve(expected_size);
        while (pos + 4 <= total_len && out.size() < expected_size) {
            // Page-boundary skip: if a 4-byte chunk header would not fit
            // in the remaining bytes of the current page, advance to the
            // next page.
            const size_t page_off = pos % kBtrfsLzoPageSize;
            if (page_off + 4 > kBtrfsLzoPageSize) {
                pos += kBtrfsLzoPageSize - page_off;
                if (pos + 4 > total_len) break;
            }
            const uint32_t chunk_len = le32(in.data() + pos);
            pos += 4;
            if (chunk_len == 0 || chunk_len > total_len - pos) return false;
 
            std::vector<unsigned char> chunk_out(kBtrfsLzoPageSize);
            lzo_uint dest_len = static_cast<lzo_uint>(chunk_out.size());
            const int rc = lzo1x_decompress_safe(
                in.data() + pos, static_cast<lzo_uint>(chunk_len),
                chunk_out.data(), &dest_len, nullptr);
            if (rc != LZO_E_OK) return false;
            chunk_out.resize(static_cast<size_t>(dest_len));
            out.insert(out.end(), chunk_out.begin(), chunk_out.end());
            pos += chunk_len;
        }
        if (out.size() > expected_size) out.resize(expected_size);
        return true;
    }
#endif
#ifdef HAVE_ZSTD
    if (compression == 3) {
        // Btrfs zstd chunked decoder.
        // Format: per-chunk: __le32 chunk_len + <chunk_len bytes zstd frame>.
        // Each chunk decompresses to up to 128 KiB.
        constexpr size_t kBtrfsZstdMaxChunkOutput = 128 * 1024;
        size_t pos = 0;
        out.clear();
        out.reserve(expected_size);
        while (pos + 4 <= in.size() && out.size() < expected_size) {
            const uint32_t chunk_len = le32(in.data() + pos);
            pos += 4;
            if (chunk_len == 0 || chunk_len > in.size() - pos) return false;
 
            std::vector<unsigned char> chunk_out(kBtrfsZstdMaxChunkOutput);
            const size_t rc = ZSTD_decompress(
                chunk_out.data(), chunk_out.size(),
                in.data() + pos, chunk_len);
            if (ZSTD_isError(rc)) return false;
            chunk_out.resize(rc);
            out.insert(out.end(), chunk_out.begin(), chunk_out.end());
            pos += chunk_len;
        }
        if (out.size() > expected_size) out.resize(expected_size);
        return true;
    }
#endif
    return false;
}

References decompress_payload(), and le32().

Referenced by decompress_payload(), and BtrfsRecoveryImpl::render_extent().

◆ gf_inv_byte()

uint8_t anonymous_namespace{btrfs_recovery.cpp}::gf_inv_byte ( uint8_t a )

Definition at line 292 of file btrfs_recovery.cpp.

                               {
    if (a == 0) return 0;
    for (int i = 1; i < 256; ++i) {
        if (gf_mul_byte(a, static_cast<uint8_t>(i)) == 1u) return static_cast<uint8_t>(i);
    }
    return 0;
}

References gf_inv_byte(), and gf_mul_byte().

Referenced by gf_inv_byte(), and BtrfsRecoveryImpl::reconstruct_raid56_read().

◆ gf_mul_byte()

uint8_t anonymous_namespace{btrfs_recovery.cpp}::gf_mul_byte	(	uint8_t	a,
		uint8_t	b )

Definition at line 274 of file btrfs_recovery.cpp.

                                          {
    uint8_t p = 0;
    for (int i = 0; i < 8; ++i) {
        if (b & 1u) p ^= a;
        const bool hi = (a & 0x80u) != 0;
        a = static_cast<uint8_t>(a << 1u);
        if (hi) a ^= 0x1du;
        b = static_cast<uint8_t>(b >> 1u);
    }
    return p;
}

References gf_mul_byte().

Referenced by gf_inv_byte(), gf_mul_byte(), gf_pow2(), BtrfsRecoveryImpl::reconstruct_raid56_read(), and BtrfsRecoveryImpl::validate_raid6_candidate().

◆ gf_pow2()

uint8_t anonymous_namespace{btrfs_recovery.cpp}::gf_pow2 ( size_t exp )

Definition at line 286 of file btrfs_recovery.cpp.

                            {
    uint8_t v = 1;
    for (size_t i = 0; i < exp; ++i) v = gf_mul_byte(v, 2);
    return v;
}

References gf_mul_byte(), and gf_pow2().

Referenced by gf_pow2(), BtrfsRecoveryImpl::reconstruct_raid56_read(), and BtrfsRecoveryImpl::validate_raid6_candidate().

◆ le16()

uint16_t anonymous_namespace{btrfs_recovery.cpp}::le16 ( const unsigned char * p )

Definition at line 52 of file btrfs_recovery.cpp.

                                      {
    return static_cast<uint16_t>(p[0]) | (static_cast<uint16_t>(p[1]) << 8);
}

References le16().

Referenced by le16(), BtrfsRecoveryImpl::load_chunk_tree(), BtrfsRecoveryImpl::load_root_tree(), and BtrfsRecoveryImpl::parse_system_chunk_array().

◆ le32()

uint32_t anonymous_namespace{btrfs_recovery.cpp}::le32 ( const unsigned char * p )

Definition at line 56 of file btrfs_recovery.cpp.

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

References le32().

Referenced by decompress_payload(), le32(), BtrfsRecoveryImpl::recover(), validate_tree_block_checksum(), validate_tree_block_header(), and BtrfsRecoveryImpl::walk_tree_internal().

◆ le64()

uint64_t anonymous_namespace{btrfs_recovery.cpp}::le64 ( const unsigned char * p )

Definition at line 63 of file btrfs_recovery.cpp.

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

References le64().

Referenced by le64(), BtrfsRecoveryImpl::load_chunk_tree(), BtrfsRecoveryImpl::load_root_tree(), parse_key(), BtrfsRecoveryImpl::parse_system_chunk_array(), BtrfsRecoveryImpl::recover(), validate_tree_block_header(), and BtrfsRecoveryImpl::walk_tree_internal().

◆ parse_key()

BtrfsKey anonymous_namespace{btrfs_recovery.cpp}::parse_key ( const unsigned char * p )

Definition at line 156 of file btrfs_recovery.cpp.

                                           {
    return {le64(p), p[8], le64(p + 9)};
}

References le64(), and parse_key().

Referenced by parse_key(), BtrfsRecoveryImpl::parse_system_chunk_array(), and BtrfsRecoveryImpl::walk_tree_internal().

◆ sanitize()

std::string anonymous_namespace{btrfs_recovery.cpp}::sanitize ( const std::string & in )

Definition at line 74 of file btrfs_recovery.cpp.

                                        {
    // Bug #15 fix: btrfs filenames are stored as UTF-8 byte sequences. The
    // previous ASCII-only sanitizer turned every accented character into '_'.
    // We reuse the shared helper which preserves valid UTF-8 multibyte runs.
    auto out = text_utils::sanitize_component(in);
    if (out == "unnamed") out = "item";
    return out;
}

References sanitize(), and text_utils::sanitize_component().

Referenced by BtrfsRecoveryImpl::export_fs_root(), BtrfsRecoveryImpl::load_root_tree(), and sanitize().

◆ to_hex()

std::string anonymous_namespace{btrfs_recovery.cpp}::to_hex ( uint64_t v )

Definition at line 83 of file btrfs_recovery.cpp.

                             {
    std::ostringstream oss;
    oss << "0x" << std::hex << std::uppercase << v;
    return oss.str();
}

References to_hex().

Referenced by BtrfsRecoveryImpl::recover(), and to_hex().

◆ validate_tree_block_checksum()

bool anonymous_namespace{btrfs_recovery.cpp}::validate_tree_block_checksum ( const std::vector< unsigned char > & block )

Definition at line 317 of file btrfs_recovery.cpp.

                                                                         {
    if (block.size() < 0x100) return false;
    const uint32_t stored = le32(block.data());
    const uint32_t calc = crc32c_update(0, block.data() + 0x20, block.size() - 0x20);
    return stored == calc;
}

References crc32c_update(), le32(), and validate_tree_block_checksum().

Referenced by validate_tree_block_checksum(), and validate_tree_block_header().

◆ validate_tree_block_header()

bool anonymous_namespace{btrfs_recovery.cpp}::validate_tree_block_header	(	const std::vector< unsigned char > &	block,
		uint64_t	logical_bytenr,
		uint32_t	nodesize,
		const std::array< unsigned char, 16 > *	fsid = nullptr,
		uint64_t	max_generation = 0 )

Definition at line 324 of file btrfs_recovery.cpp.

                                                           {
    if (block.size() < 101) return false;
    if (!validate_tree_block_checksum(block)) return false;
    if (le64(block.data() + 48) != logical_bytenr) return false;
    if (fsid != nullptr && !std::equal(fsid->begin(), fsid->end(), block.data() + 32)) return false;
    const uint64_t generation = le64(block.data() + 80);
    if (generation == 0) return false;
    if (max_generation != 0 && generation > max_generation + 1024) return false;
    const uint32_t nritems = le32(block.data() + 96);
    const uint8_t level = block[100];
    if (level > 8) return false;
    const size_t header_size = 101;
    const size_t item_size = (level == 0) ? 25 : 33;
    const uint64_t need = static_cast<uint64_t>(header_size) + static_cast<uint64_t>(nritems) * item_size;
    if (need > nodesize) return false;
    return true;
}

References le32(), le64(), validate_tree_block_checksum(), and validate_tree_block_header().

Referenced by BtrfsRecoveryImpl::read_tree_block(), and validate_tree_block_header().

Variable Documentation

◆ BTRFS_BLOCK_GROUP_DUP

uint64_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_DUP = 1ull << 5

constexpr

Definition at line 47 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::logical_to_physical().

◆ BTRFS_BLOCK_GROUP_RAID0

uint64_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID0 = 1ull << 3

constexpr

Definition at line 45 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::logical_to_physical().

◆ BTRFS_BLOCK_GROUP_RAID1

uint64_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID1 = 1ull << 4

constexpr

Definition at line 46 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::logical_to_physical().

◆ BTRFS_BLOCK_GROUP_RAID10

uint64_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID10 = 1ull << 6

constexpr

Definition at line 48 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::logical_to_physical().

◆ BTRFS_BLOCK_GROUP_RAID5

uint64_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID5 = 1ull << 7

constexpr

Definition at line 49 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::logical_to_physical(), BtrfsRecoveryImpl::read_tree_block(), and BtrfsRecoveryImpl::reconstruct_raid56_read().

◆ BTRFS_BLOCK_GROUP_RAID6

uint64_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_BLOCK_GROUP_RAID6 = 1ull << 8

constexpr

Definition at line 50 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::logical_to_physical(), BtrfsRecoveryImpl::read_tree_block(), and BtrfsRecoveryImpl::reconstruct_raid56_read().

◆ BTRFS_CHUNK_ITEM_KEY

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_CHUNK_ITEM_KEY = 228

constexpr

Definition at line 39 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::load_chunk_tree(), and BtrfsRecoveryImpl::parse_system_chunk_array().

◆ BTRFS_DIR_INDEX_KEY

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_DIR_INDEX_KEY = 96

constexpr

Definition at line 34 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::collect_fs_root().

◆ BTRFS_DIR_ITEM_KEY

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_DIR_ITEM_KEY = 84

constexpr

Definition at line 33 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::collect_fs_root().

◆ BTRFS_EXTENT_DATA_KEY

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_EXTENT_DATA_KEY = 108

constexpr

Definition at line 35 of file btrfs_recovery.cpp.

◆ BTRFS_FILE_EXTENT_INLINE

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_FILE_EXTENT_INLINE = 0

constexpr

Definition at line 41 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::render_extent().

◆ BTRFS_FILE_EXTENT_PREALLOC

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_FILE_EXTENT_PREALLOC = 2

constexpr

Definition at line 43 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::render_extent().

◆ BTRFS_FILE_EXTENT_REG

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_FILE_EXTENT_REG = 1

constexpr

Definition at line 42 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::render_extent().

◆ BTRFS_INODE_ITEM_KEY

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_INODE_ITEM_KEY = 1

constexpr

Definition at line 31 of file btrfs_recovery.cpp.

◆ BTRFS_INODE_REF_KEY

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_INODE_REF_KEY = 12

constexpr

Definition at line 32 of file btrfs_recovery.cpp.

◆ BTRFS_ROOT_BACKREF_KEY

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_ROOT_BACKREF_KEY = 144

constexpr

Definition at line 37 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::load_root_tree().

◆ BTRFS_ROOT_ITEM_KEY

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_ROOT_ITEM_KEY = 132

constexpr

Definition at line 36 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::load_root_tree().

◆ BTRFS_ROOT_REF_KEY

uint8_t anonymous_namespace{btrfs_recovery.cpp}::BTRFS_ROOT_REF_KEY = 156

constexpr

Definition at line 38 of file btrfs_recovery.cpp.

Referenced by BtrfsRecoveryImpl::load_root_tree().

Classes

Functions

Variables

Function Documentation

◆ crc32c_update()

◆ decompress_payload()

◆ gf_inv_byte()

◆ gf_mul_byte()

◆ gf_pow2()

◆ le16()

◆ le32()

◆ le64()

◆ parse_key()

◆ sanitize()

◆ to_hex()

◆ validate_tree_block_checksum()

◆ validate_tree_block_header()

Variable Documentation

◆ BTRFS_BLOCK_GROUP_DUP

◆ BTRFS_BLOCK_GROUP_RAID0

◆ BTRFS_BLOCK_GROUP_RAID1

◆ BTRFS_BLOCK_GROUP_RAID10

◆ BTRFS_BLOCK_GROUP_RAID5

◆ BTRFS_BLOCK_GROUP_RAID6

◆ BTRFS_CHUNK_ITEM_KEY

◆ BTRFS_DIR_INDEX_KEY

◆ BTRFS_DIR_ITEM_KEY

◆ BTRFS_EXTENT_DATA_KEY

◆ BTRFS_FILE_EXTENT_INLINE

◆ BTRFS_FILE_EXTENT_PREALLOC

◆ BTRFS_FILE_EXTENT_REG

◆ BTRFS_INODE_ITEM_KEY

◆ BTRFS_INODE_REF_KEY

◆ BTRFS_ROOT_BACKREF_KEY

◆ BTRFS_ROOT_ITEM_KEY

◆ BTRFS_ROOT_REF_KEY