hfs::anonymous_namespace{hfs_btree.cpp} Namespace Reference

Functions
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)

Variables
constexpr size_t	MAX_NODES_VISITED = 1'000'000

Function Documentation

descend()

bool hfs::anonymous_namespace{hfs_btree.cpp}::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 )

Definition at line 166 of file hfs_btree.cpp.

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

References hfs::be32(), hfs::catalog_record_body_offset(), descend(), hfs::kBTIndexNode, hfs::kBTLeafNode, hfs::NodeDescriptor::kind, MAX_NODES_VISITED, hfs::node_record_length(), hfs::node_record_offset(), hfs::HeaderRec::nodeSize, hfs::NodeDescriptor::numRecords, hfs::parse_node_descriptor(), and hfs::HeaderRec::totalNodes.

Referenced by descend().

Variable Documentation

MAX_NODES_VISITED

size_t hfs::anonymous_namespace{hfs_btree.cpp}::MAX_NODES_VISITED = 1'000'000

constexpr

Definition at line 164 of file hfs_btree.cpp.

Referenced by descend().