Debugging a Quadtree in C
I've been working on a project that simulates stars or particles and the forces of attraction between them. To make the simulation more efficient and able to handle more particles, I've been working on implementing a Barnes-Hut Algorithm by using a quadtree to partition the simulation space. When it works, it's beautiful:
Today made a breakthrough on a bug in my quadtree implementation. I had been getting very occasional segfaults, and Valgrind was complaining of invalid reads and free()s. I haven't had much time to work on the problem for the past two weeks, but I was often thinking about it (and even, with an unnerving frequency, dreaming about it). When I had an hour here or there, I would return to my investigation and continue my attempt to understand the cause of the problem. Eventually I made the minimal working example below.
//qt_test.c
#include <stdio.h>
#include <stdlib.h>
#define NUM_UPDATES 10
#define QUAD_TREE_LEVELS 3
struct QuadTreeNode
{
struct QuadTreeNode *ne;
struct QuadTreeNode *nw;
struct QuadTreeNode *sw;
struct QuadTreeNode *se;
};
struct QuadTree
{
struct QuadTreeNode *root;
};
struct QuadTreeNode* quad_tree_node_init(void)
{
struct QuadTreeNode *node = (struct QuadTreeNode*)malloc(sizeof (struct QuadTreeNode));
if (node)
{
node->ne = NULL;
node->nw = NULL;
node->sw = NULL;
node->se = NULL;
}
return node;
}
void quad_tree_node_free(struct QuadTreeNode *node)
{
if (node)
{
quad_tree_node_free(node->ne);
quad_tree_node_free(node->nw);
quad_tree_node_free(node->sw);
quad_tree_node_free(node->se);
free(node);
}
}
void quad_tree_node_subdivide(struct QuadTreeNode *node, int remaining_levels)
{
if (node && remaining_levels > 0)
{
remaining_levels--;
node->ne = quad_tree_node_init();
node->nw = quad_tree_node_init();
node->sw = quad_tree_node_init();
node->se = quad_tree_node_init();
quad_tree_node_subdivide(node->ne, remaining_levels);
quad_tree_node_subdivide(node->nw, remaining_levels);
quad_tree_node_subdivide(node->sw, remaining_levels);
quad_tree_node_subdivide(node->se, remaining_levels);
}
}
struct QuadTree* quad_tree_init(void)
{
struct QuadTree *qt = (struct QuadTree*)malloc(sizeof (struct QuadTree));
if (qt)
{
qt->root = quad_tree_node_init();
quad_tree_node_subdivide(qt->root, QUAD_TREE_LEVELS - 1);
}
return qt;
}
void quad_tree_free(struct QuadTree *qt)
{
if (qt)
{
quad_tree_node_free(qt->root);
free(qt);
}
}
void update(struct QuadTree *qt)
{
quad_tree_free(qt);
qt = quad_tree_init();
}
int main(void)
{
struct QuadTree *qt = quad_tree_init();
for (int i = 0; i < NUM_UPDATES; ++i)
{
printf("Update %d\n", i+1);
update(qt);
}
quad_tree_free(qt);
return 0;
}
Here's a sample from the output of valgrind --track-origins=yes ./qt_test:
Invalid read of size 8
==16345== at 0x1088B7: quad_tree_node_free (qt_test.c:43)
==16345== by 0x1089DB: quad_tree_free (qt_test.c:82)
==16345== by 0x108A00: update (qt_test.c:90)
==16345== by 0x108A5D: main (qt_test.c:102)
==16345== Address 0x5e350a0 is 16 bytes inside a block of size 32 free'd
==16345== at 0x4C2C14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==16345== by 0x1088D0: quad_tree_node_free (qt_test.c:45)
==16345== by 0x1089DB: quad_tree_free (qt_test.c:82)
==16345== by 0x108A00: update (qt_test.c:90)
==16345== by 0x108A5D: main (qt_test.c:102)
==16345== Block was alloc'd at
==16345== at 0x4C2AF1F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==16345== by 0x10885E: quad_tree_node_init (qt_test.c:25)
==16345== by 0x1089A0: quad_tree_init (qt_test.c:71)
==16345== by 0x108A30: main (qt_test.c:97)
[...]
==16345== Invalid free() / delete / delete[] / realloc()
==16345== at 0x4C2C14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==16345== by 0x1088D0: quad_tree_node_free (qt_test.c:45)
==16345== by 0x1088AD: quad_tree_node_free (qt_test.c:41)
==16345== by 0x1088BF: quad_tree_node_free (qt_test.c:43)
==16345== by 0x1089DB: quad_tree_free (qt_test.c:82)
==16345== by 0x108A00: update (qt_test.c:90)
==16345== by 0x108A5D: main (qt_test.c:102)
==16345== Address 0x5e35570 is 0 bytes inside a block of size 32 free'd
==16345== at 0x4C2C14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==16345== by 0x1088D0: quad_tree_node_free (qt_test.c:45)
==16345== by 0x1088AD: quad_tree_node_free (qt_test.c:41)
==16345== by 0x1088BF: quad_tree_node_free (qt_test.c:43)
==16345== by 0x1089DB: quad_tree_free (qt_test.c:82)
==16345== by 0x108A00: update (qt_test.c:90)
==16345== by 0x108A5D: main (qt_test.c:102)
==16345== Block was alloc'd at
==16345== at 0x4C2AF1F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==16345== by 0x10885E: quad_tree_node_init (qt_test.c:25)
==16345== by 0x10890B: quad_tree_node_subdivide (qt_test.c:54)
==16345== by 0x108958: quad_tree_node_subdivide (qt_test.c:61)
==16345== by 0x1089B0: quad_tree_init (qt_test.c:72)
==16345== by 0x108A30: main (qt_test.c:97)
I was baffled for quite a while by these errors. I spent a lot of time checking and re-checking all the functions that init and free the quadtree and quadtree nodes. Only after expending great effort did I finally determine the cause.
The problem turned out to lie with the way I was passing my struct around to
different functions. I'm used to C++, in which one can pass things either by
value or by reference, but in C, everything is passed by value. My update()
function was changing its local copy of the QuadTree *, qt, but that change
did not apply to the original qt in main(). That meant that all the calls to
qt in main() were accessing the old memory that had been freed.
Another Level of Indirection
The first solution I found was to change update() to take a QuadTree **
parameter:
void update(struct QuadTree **qt)
{
quad_tree_free(*qt);
*qt = quad_tree_init();
}
Then in main() I called it like:
update(&qt);
Now that the qt parameter was wrapped in an extra pointer, changes to it in
update() were now being properly applied to qt in main(). Valgrind's
previous complaints were gone. It was a nice example to support the claim that
"All problems in computer science can be solved by another level of
indirection."
Change Only What Needs Changing
I also found another way of solving the problem. I already had a QuadTree
struct which conveniently wrapped the rest of the actual tree and kept track of
the root. I realized that there was no reason to continually be freeing and
reallocating qt itself.
I simplified the QuadTree functions to basically be "run-once".
struct QuadTree* quad_tree_init(void)
{
struct QuadTree *qt = (struct QuadTree*)malloc(sizeof (struct QuadTree));
qt->root = NULL;
return qt;
}
void quad_tree_free(struct QuadTree *qt)
{
if (qt)
{
quad_tree_node_free(qt->root);
free(qt);
}
}
I changed my update function to only operate on qt->root.
void update(struct QuadTree *qt)
{
quad_tree_node_free(qt->root);
qt->root = quad_tree_node_init();
quad_tree_node_subdivide(qt->root, QUAD_TREE_LEVELS - 1);
}
And I updated my main function accordingly:
int main(void)
{
struct QuadTree *qt = quad_tree_init();
qt->root = quad_tree_node_init();
quad_tree_node_subdivide(qt->root, QUAD_TREE_LEVELS - 1);
for (int i = 0; i < NUM_UPDATES; ++i)
{
printf("Update %d\n", i+1);
update(qt);
}
quad_tree_free(qt);
return 0;
}
Still no errors from Valgrind! qt is happy to point to the same memory address
for most of the program.
I'm not sure which of these solutions is more appropriate, but that will become clear with time. I'm happy to have gained a deeper understanding of pointers, the implications of pass-by-value in C, and some C idioms with which to deal with similar situations.