Tuesday, July 14, 2009

Manifesto of a Very Hard To Find Memory Leak (To Be)

I'm implementing a hash table that will become the basis of a free list memory allocator. The hash table uses singly linked list for buckets. In the list implementation, there is a RemoveAll function written like this:
void RemoveAll(Predicate& p, Consume& c)
{
Node **result;
for (result = &first_; *result != NULL; result = &(*result)->next_) {
if (p(**result)) {
Node *node = *result;
*result = node->next_;
node->next_ = NULL;
c(node);

if (*result == NULL)
break;
}
}
}
Admittedly, the code is copied from a similar function called Remove(), which removes only the first node that satisfies the predicate. However, when it is modified to remove all nodes, an unintended side effect is, if a node is to be removed, it always skips the next node. When I wrote a unit test, I inserted nodes for 0 through 16, and removed all the even nodes, so this problem was not detected. However, when I used this function with a predicate that always returns true, I noticed that the list is not cleared properly.
Now, this function is used in the hash table to clear all the buckets. Each item in the bucket would be a free list for a certain size of objects. When a free list memory allocator uses this hash table, it will see memory leak on a certain size of objects, and the size would appear to be at random.
Fortunately, when a list is destructed, I have it do nothing but to assert that the list is empty. This helped detecting the problem early. Unit test for the hash table to clear all entries helped bringing this problem to the surface.