hfs_btree.cpp

Go to the documentation of this file.

// hfs_btree.cpp -- HFS+ B-tree node header parsers.
//
// Implementation is intentionally minimal in session 1: we parse the
// node descriptor (14 bytes) and the BTHeaderRec (106 bytes), plus
// helpers to compute record offsets within a node. The actual B-tree
// traversal -- descending index nodes, iterating leaf records -- is
// session 2 work.
 
#include "hfs_btree.hpp"
#include "hfs_format.hpp"
 
#include <set>
#include <sstream>
 
namespace hfs {
 
bool parse_node_descriptor(const unsigned char* buf, NodeDescriptor& out) {
    if (buf == nullptr) return false;
    out = {};
    out.fLink      = be32(buf + 0x00);
    out.bLink      = be32(buf + 0x04);
    // kind is a SIGNED 8-bit value (-1 for leaf, 0/1/2 otherwise)
    out.kind       = static_cast<int8_t>(buf[0x08]);
    out.height     = buf[0x09];
    out.numRecords = be16(buf + 0x0A);
    // reserved at +0x0C..+0x0E ignored
 
    // Sanity: kind must be -1, 0, 1, or 2
    if (out.kind != kBTLeafNode &&
        out.kind != kBTIndexNode &&
        out.kind != kBTHeaderNode &&
        out.kind != kBTMapNode) {
        return false;
    }
    return true;
}
 
bool parse_header_rec(const unsigned char* buf, HeaderRec& out) {
    if (buf == nullptr) return false;
    out = {};
    out.treeDepth      = be16(buf + 0x00);
    out.rootNode       = be32(buf + 0x02);
    out.leafRecords    = be32(buf + 0x06);
    out.firstLeafNode  = be32(buf + 0x0A);
    out.lastLeafNode   = be32(buf + 0x0E);
    out.nodeSize       = be16(buf + 0x12);
    out.maxKeyLength   = be16(buf + 0x14);
    out.totalNodes     = be32(buf + 0x16);
    out.freeNodes      = be32(buf + 0x1A);
    // 2 bytes reserved at +0x1E
    out.clumpSize      = be32(buf + 0x20);
    out.btreeType      = buf[0x24];
    out.keyCompareType = buf[0x25];
    out.attributes     = be32(buf + 0x26);
    // 64 bytes of reserved at +0x2A..+0x6A
 
    // Sanity: nodeSize must be a power of 2 in [512, 32768]
    // (uint16_t max is 65535, so the upper bound is implicit; any
    // power-of-two value in our range is necessarily <= 32768)
    if (out.nodeSize < 512 ||
        (out.nodeSize & (out.nodeSize - 1)) != 0) {
        return false;
    }
    // treeDepth must agree with totalNodes (depth==0 means empty tree;
    // depth==1 means a single leaf; depth>16 is implausible).
    if (out.treeDepth > 16) return false;
    return true;
}
 
uint16_t node_record_offset(const unsigned char* node_buf,
                            uint16_t nodeSize,
                            uint16_t numRecords,
                            uint16_t i) {
    if (i >= numRecords) return 0;
    if (node_buf == nullptr) return 0;
    if (nodeSize < 14 + 2u * (static_cast<uint32_t>(numRecords) + 1)) {
        return 0;  // not enough room for offset table
    }
    // The offsets table sits at the END of the node, with one 16-bit
    // entry per record (numRecords entries) plus a "free space" offset
    // (numRecords+1 entries total). The LAST 2 bytes hold the offset
    // of record 0; the 2 before that hold record 1; and so on.
    const uint32_t off_idx = static_cast<uint32_t>(nodeSize)
                          - 2u * (static_cast<uint32_t>(i) + 1u);
    return be16(node_buf + off_idx);
}
 
uint16_t node_record_length(const unsigned char* node_buf,
                            uint16_t nodeSize,
                            uint16_t numRecords,
                            uint16_t i) {
    if (i >= numRecords) return 0;
    const uint16_t this_off = node_record_offset(node_buf, nodeSize,
                                                  numRecords, i);
    if (this_off == 0) return 0;
    // Next offset (which is at index i+1 in the descending table) gives
    // the END of record `i`. For i == numRecords-1, the next entry IS
    // the "free space" offset, which is the end of the records area.
    const uint32_t next_idx = static_cast<uint32_t>(nodeSize)
                            - 2u * (static_cast<uint32_t>(i) + 2u);
    if (next_idx + 2 > nodeSize) return 0;
    const uint16_t next_off = be16(node_buf + next_idx);
    if (next_off < this_off) return 0; // corrupt
    return next_off - this_off;
}
 
// =============================================================================
//  Catalog key parser (session 2)
// =============================================================================
 
bool parse_catalog_key(const unsigned char* key_buf,
                        uint32_t max_bytes,
                        CatalogKey& out) {
    if (key_buf == nullptr || max_bytes < 8) return false;
    out = {};
    const uint16_t keyLength = be16(key_buf + 0);
    // Total key size = 2 (length field) + keyLength bytes of payload.
    // Payload = parentID(4) + nameLength(2) + name[nameLength*2].
    if (keyLength < 6) return false;          // must include parentID + nameLen
    if (2u + keyLength > max_bytes) return false;
    out.total_key_bytes = 2u + keyLength;
    out.parentID   = be32(key_buf + 2);
    out.nameLength = be16(key_buf + 6);
    if (8u + static_cast<uint32_t>(out.nameLength) * 2u > 2u + keyLength) {
        return false;                          // name overflows declared length
    }
    out.name_utf16be = key_buf + 8;
    return true;
}
 
uint32_t catalog_record_body_offset(const unsigned char* record_buf,
                                     uint32_t record_len) {
    if (record_buf == nullptr || record_len < 8) return 0;
    const uint16_t keyLength = be16(record_buf + 0);
    const uint32_t key_total = 2u + keyLength;
    if (key_total > record_len) return 0;
    // After the key, records are aligned on a 16-bit boundary in the
    // catalog file. Round up the key end to the next even byte.
    return (key_total + 1u) & ~1u;
}
 
// =============================================================================
//  Generic B-tree walker (session 2)
// =============================================================================
//
// Standard B-tree descent:
//   1. Start at header.rootNode
//   2. Read the node, parse its descriptor
//   3. If it's an INDEX node:
//        for each record, parse the key, then read the 4-byte child
//        node pointer that immediately follows; recurse into the child
//   4. If it's a LEAF node:
//        for each record, invoke on_leaf(record_buf, record_len)
//   5. (Optional) Once we reach the leftmost leaf, we could follow
//      `fLink` siblings to enumerate all leaves without re-descending.
//      We do NOT use that here -- the recursive descent already visits
//      every leaf, and following sibling links risks infinite loops on
//      corrupted disks.
//
// Cycle detection: visited-node set, capped at 1M nodes.
 
namespace {
 
constexpr size_t MAX_NODES_VISITED = 1'000'000;
 
bool descend(uint32_t node_index, uint16_t expected_height,
             const HeaderRec& header,
             const NodeReader& read_node,
             const LeafRecordCallback& on_leaf,
             std::set<uint32_t>& visited,
             size_t& nodes_visited,
             std::vector<std::string>& logs,
             std::string& error,
             bool& callback_stopped) {
    if (callback_stopped) return true;
    if (node_index == 0) {
        // Node 0 is always the header node; descending into it from an
        // index pointer means corruption.
        return true;
    }
    if (++nodes_visited > MAX_NODES_VISITED) {
        error = "HFS+ B-tree: traversal cap reached (possible loop)";
        return false;
    }
    if (!visited.insert(node_index).second) {
        std::ostringstream m;
        m << "HFS+ B-tree: cycle detected at node " << node_index << ", skip";
        logs.push_back(m.str());
        return true;
    }
 
    std::vector<unsigned char> node;
    if (!read_node(node_index, node)) {
        std::ostringstream m;
        m << "HFS+ B-tree: read failed for node " << node_index;
        logs.push_back(m.str());
        return true; // not fatal; just lose this branch
    }
    if (node.size() < header.nodeSize) {
        std::ostringstream m;
        m << "HFS+ B-tree: short read for node " << node_index;
        logs.push_back(m.str());
        return true;
    }
 
    NodeDescriptor nd;
    if (!parse_node_descriptor(node.data(), nd)) {
        std::ostringstream m;
        m << "HFS+ B-tree: bad descriptor at node " << node_index;
        logs.push_back(m.str());
        return true;
    }
    // height check is informational; HFS+ headers historically populate
    // height in different ways across implementations. Don't enforce.
    (void)expected_height;
 
    if (nd.kind != kBTLeafNode && nd.kind != kBTIndexNode) {
        std::ostringstream m;
        m << "HFS+ B-tree: unexpected kind=" << static_cast<int>(nd.kind)
          << " at node " << node_index;
        logs.push_back(m.str());
        return true;
    }
 
    for (uint16_t i = 0; i < nd.numRecords; ++i) {
        const uint16_t rec_off = node_record_offset(node.data(),
                                                     header.nodeSize,
                                                     nd.numRecords, i);
        const uint16_t rec_len = node_record_length(node.data(),
                                                     header.nodeSize,
                                                     nd.numRecords, i);
        if (rec_off == 0 || rec_len == 0) continue;
        if (rec_off + rec_len > header.nodeSize) continue;
 
        const unsigned char* recp = node.data() + rec_off;
 
        if (nd.kind == kBTLeafNode) {
            if (!on_leaf(recp, rec_len)) {
                callback_stopped = true;
                return true;
            }
        } else {
            // Index record: [catalog key][__be32 child node pointer]
            const uint32_t body_off = catalog_record_body_offset(recp, rec_len);
            if (body_off == 0 || body_off + 4 > rec_len) continue;
            const uint32_t child = be32(recp + body_off);
            if (child == 0 || child >= header.totalNodes) {
                std::ostringstream m;
                m << "HFS+ B-tree: index node " << node_index
                  << " has implausible child pointer " << child;
                logs.push_back(m.str());
                continue;
            }
            if (!descend(child,
                          (expected_height > 0) ? expected_height - 1 : 0,
                          header, read_node, on_leaf,
                          visited, nodes_visited, logs, error,
                          callback_stopped)) {
                return false;
            }
            if (callback_stopped) return true;
        }
    }
    return true;
}
 
} // anonymous namespace
 
bool walk_btree(const HeaderRec& header,
                const NodeReader& read_node,
                const LeafRecordCallback& on_leaf,
                std::vector<std::string>& logs,
                std::string& error) {
    if (header.rootNode == 0 || header.nodeSize == 0) {
        error = "HFS+ B-tree: empty/zero rootNode";
        return false;
    }
    if (header.treeDepth > 16) {
        error = "HFS+ B-tree: implausible tree depth";
        return false;
    }
    std::set<uint32_t> visited;
    size_t nodes_visited = 0;
    bool callback_stopped = false;
    return descend(header.rootNode, header.treeDepth, header, read_node,
                   on_leaf, visited, nodes_visited, logs, error,
                   callback_stopped);
}
 
} // namespace hfs