nushoin / RTree

N-dimensional RTree implementation in C++
Other
376 stars 109 forks source link

Fix uninitialized m_child error #31

Open GustavoSilvera opened 6 days ago

GustavoSilvera commented 6 days ago

Seeing a crash that looks like the following:

external/rtree/RTree.h:635:40: runtime error: member access within misaligned address 0x00000000007a for type 'Node', which requires 8 byte alignment
0x00000000007a: note: pointer points here
<memory cannot be printed>
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior external/rtree/RTree.h:635:40 in
external/rtree/RTree.h:635:40: runtime error: load of misaligned address 0x00000000007a for type 'int', which requires 8 byte alignment
0x00000000007a: note: pointer points here
<memory cannot be printed>

Specifically in line 635 where this logic is performed:

        if (process.branch->m_child)
        {
            // If the branch has children, add them all into the queue
            Node* node = process.branch->m_child;
            for (auto i = 0; i < node->m_count; ++i) // <-- node is an invalid pointer!
            {
                auto d = this->SquareDistance(rect, node->m_branch[i].m_rect);
                search_queue.emplace(node->m_branch + i, d);
            }
        }

Here, node, which is process.branch->m_child is not NULL, so the check above passes, but it is not a valid memory address. For instance I saw values such as 0x4051000030410 which looked to me like uninitialized memory.

Sure enough, when we initialize these Branch structs, the Node* is not NULL so I believe there are no guarantees as to if it holds NULL or not.

Regardless, this change resolved the crashes for me and I think its generally good practice to default initialize fields like this.

Some more context on C++ default initialization for PODs: https://stackoverflow.com/questions/15212261/default-and-value-initialization-of-pod-types-in-c

From that they say:

After the call to a constructor for class X has completed, if a member of X is neither specified in the constructor’s mem-initializers, nor default-initialized, nor value-initialized, nor given a value during execution of the body of the constructor, the member has indeterminate value.