Abnormal behaviour of free() in C

Question

Note: I apologise if the question is too long or does not fit the format for SO. If not on the proper site, pls suggest for which StackExchange sites the question would be more appropriate.

I have been following this tutorial about AVL Trees and decided to add a BFS search for the tree. This is my implementation (parts of it) -

void *dequeue(struct q *q_instance)
{
    struct q_node *temp;
    void *jsw_node_ptr;

    if (q_instance->beg == NULL)
        return NULL;

    temp = q_instance->beg;
    jsw_node_ptr = temp->node;

    if (q_instance->beg == q_instance->end)
        q_instance->beg = q_instance->end = NULL;
    else
        q_instance->beg = q_instance->beg->next;

    free(temp);

    return jsw_node_ptr;
}

void bfs_order(struct jsw_node *root)
{
    struct q *q_instance = NULL;
    struct jsw_node *temp;
    if (root == NULL)
        return;

    q_instance = init_q();
    enqueue(q_instance, root);

    while (q_instance->beg) {
        temp = /*(struct jsw_node *)*/dequeue(q_instance);
        fprintf(stdout, "%d\t", temp->data);
        if (temp->link[0])
            enqueue(q_instance, temp->link[0]);
        if (temp->link[1])
            enqueue(q_instance, temp->link[1]);
        free(temp); /* Here is my confusion */
    }

    free(q_instance);
}

Now, even if I free() the variable returned from the function dequeue() it causes me no harm. However, the value returned has been assigned dynamically in some other function. How doesn't it cause any problem with my tree? Isn't free() supposed to free the allocated space?

Answer 1

I'm using the C99 standard as an example here, which may or may not be what you're using. It should apply, though. In the C99 standard, appendix J.2 lists undefined behavior. You'd want to note:

• An object is referred to outside of its lifetime (6.2.4).

• The value of a pointer to an object whose lifetime has ended is used (6.2.4).

mah alluded to this above - since the behavior is undefined, you don't know what will happen. In your case, the data is probably left behind and you're now improperly accessing free'd data which just so happens to still be accurate. Give it time and more malloc's and that data will likely/eventually change out from under you.

Edit: Link to the document for reference: http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf

Answer 2

The space is deallocated and returned to the heap. The data is not modified by free(), so the code may continue to appear to work (for a while at least). However that memory is available for use by any subsequent memory allocation, and when that happens, either the tree data will be modified by the new owner and your tree will be broken, or you will modify the tree and the new owner of the memory will be broken.

The actual behaviour will always depend on when gets corrupted, when, and how the corrupted data is used. In the worst case you can corrupt the entire heap, and many things will be broken, in ways that are very hard to trace to the original cause.

Continuing to use memory that is free'd is not detected at runtime without using analysis tools such as Valgrind for example, and you may not observe any particular adverse behaviour at all. This kind of bug may be in your code for a long time, only to cause a failure after some unrelated code change many months later.