C "pointer being freed was not allocated" error

Question

I'm experimenting with a quadtree implementation found online, but am receiving "pointer being freed was not allocated" errors intermittently as part of the following (stripped down) _node_release function:

static void _node_release(node* node)
{
    if(node->subnodes[0])
    {
        for(size_t i=0;i<4;i++)
        {
            _node_release(node->subnodes[i]);
            free(node->subnodes[i]); // this causes "pointer being freed was not allocated" errors
        }
    }
    // ...

    free(node); // the node passed to _node_release is free'd here
}

Would I be correct to assume that node is being incorrectly free'd twice here? The _node_release function free's the node passed to it, but the code is also attempting to free each subsequent subnode after making a recursive call to _node_release.

Answer 1

Yes you are correct with this assumption.

The problem is in your recursive call. Suppose I am a subnode in the recursive call. When I am done calling free on my subnodes, i then execute my last line, free(node) to free myself.

Now i'm the parent of this node. I do the same routine. One of my subnodes, however, was the guy who just freed himself. So when I call free(node->subnodes[i]) I get the error that you see

Answer 2

Yes you are freeing your nodes twice.

 1: static void _node_release(node* node)
 2: {
 3:    if(node->subnodes[0])
 4:    {
 5:        for(size_t i=0;i<4;i++)
 6:        {
 7:            _node_release(node->subnodes[i]);
 8:            free(node->subnodes[i]); // this causes "pointer being freed was not allocated" errors
 9:        }
10:     }
11:     // ...
12: 
13:     free(node); // the node passed to _node_release is free'd here
14: }

Lets say you have NodeB as a child of NodeA

_free_release(NodeA)
    _free_release(NodeB) – line 7
        free(NodeB) - line 14
    free(NodeB) - line 8

To fix this just remove the free on line 8

static void _node_release(node* node)
{
    if(node->subnodes[0])
    {
        for(size_t i=0;i<4;i++)
        {
            _node_release(node->subnodes[i]);
        }
    }
    // ...

    free(node); // the node passed to _node_release is free'd here
}