C Memory leak with valgrind

Question

I'm trying to implement a Queue using a linked list in C, in an open-source project. I'm at the point where I've implemented the Queue, wrote unit tests, and worked out most of the memory leaks using valgrind.

The problem now is that I've been trying to find the leak for these last 8 bytes for a couple hours now, and I can't seem to figure it out.

Here is the output from valgrind:

==25806== 8 bytes in 1 blocks are definitely lost in loss record 1 of 1
==25806==    at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==25806==    by 0x80484E3: node_create (in /home/karysto/c-datastructures/queue/tests.out)
==25806==    by 0x8048511: enqueue (in /home/karysto/c-datastructures/queue/tests.out)
==25806==    by 0x8048851: test_dequeue_updates_size (in /home/karysto/c-datastructures/queue/tests.out)
==25806==    by 0x8048978: test_suite (in /home/karysto/c-datastructures/queue/tests.out)
==25806==    by 0x80489B0: main (in /home/karysto/c-datastructures/queue/tests.out)
==25806== 
==25806== LEAK SUMMARY:
==25806==    definitely lost: 8 bytes in 1 blocks
==25806==    indirectly lost: 0 bytes in 0 blocks
==25806==      possibly lost: 0 bytes in 0 blocks
==25806==    still reachable: 0 bytes in 0 blocks
==25806==         suppressed: 0 bytes in 0 blocks
==25806==

Here's my structs for the queue linked list:

struct Queue {
    int size;
    struct Node *front;
    struct Node *back;
};

struct Node {
    int data;
    struct Node *next;
};

Here's queue.c, the implementation for dequeue.

void
dequeue(struct Queue *q) {

    /* Dequeue from an empty queue. */
    if (q->size == 0) {
        return;
    }

    /* Dequeue the only node. */
    else if (q->size == 1) {
        q->front = NULL;
        q->back  = NULL;
        free(q->front);
        free(q->back);
    }

    /* Regular case. */
    else if (q->size > 1) {
        struct Node *temp;
        temp = q->front;
        q->front = q->front->next;
        free(temp);
    }

    --(q->size);
    return;
}

And here's the enqueue in the same file.

void
enqueue(struct Queue *q, int data) {
    struct Node *head = node_create(data);

    /* First enqueue on empty. */
    if (q->front == NULL && q->back == NULL) {
        q->front = head;
        q->back  = head;
    }

    else {
        q->back->next = head;
        q->back       = head;
    }

    ++(q->size);
    return;
}

For completness, here's the node_create function that is being referenced from enqueue:

struct Node*
node_create(int d) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = d;
    n->next = NULL;
    return n;
}

`q->front = NULL; free(q->front)` - shouldn't that be the other way round? And aren't `q->front` and `q->back` the same in a single-node queue? — M Oehm, Apr 21 '15 at 09:55
You're right in that the `q->front = NULL` should be after, but if I switch them around, the compilation produces a `*** glibc detected *** ./tests.out: double free or corruption (fasttop)` error. — CisBae, Apr 21 '15 at 10:02
Yes, that's the second logical error in your snippet. You can only free the same node once, no matter via which pointer you access it. — M Oehm, Apr 21 '15 at 10:04

M Oehm · Accepted Answer · 2015-04-21T10:41:54.563

5

I think that your problem lies in dequeuing the last node:

/* Dequeue the only node. */
else if (q->size == 1) {
    q->front = NULL;
    q->back  = NULL;
    free(q->front);
    free(q->back);
}

You effectively call free(NULL) twice. free(NULL) is allowed, but it doesn't do anything. So you end up not freeing the node and lose the memory. You should assign NULL to the front and back after freeing and you should also free the last node only once:

/* Dequeue the only node. */
else if (q->size == 1) {
    free(q->front);
    q->front = NULL;
    q->back  = NULL;
}

(Here, the front and back are the same. You are also remobving at most one node when dequeuing, so you should only free at most one node.)

edited Apr 21 '15 at 10:41

answered Apr 21 '15 at 10:02

M Oehm

28,726
3
31
42

Thank you so much @M Oehm! Your explaination is clear and it fixed the memory leak :) I'll upvote that. – CisBae Apr 21 '15 at 10:05
`free(NULL)` is _not_ the cause of the memory leak (it is a no-op), which may confuse readers. The cause is _omitting to free_ the node which is allocated. – Betamos Apr 21 '15 at 10:09
@Betamos: `free(NULL)` leads to the memory leak, because the OP thought he'd freed the memory, but hadn't. I agree that the explanation was confusing and have rewritten it. – M Oehm Apr 21 '15 at 10:43

score 1 · Answer 2 · edited May 23 '17 at 10:24

1

How about:

/* Dequeue the only node. */
    else if (q->size == 1) {
        free(q->front);
        q->front = NULL;
        q->back  = NULL;
    }

Explanation: In your original solution you were first pointing both q->front and q->back to NULL before free()ing them. Running free() on NULL doesn't destroy the universe but it doesn't do very much, i.e. not free()ing your last node.

edited May 23 '17 at 10:24

Community

1
1

answered Apr 21 '15 at 10:02

Betamos

26,448
9
23
28

Thanks for the solution @Betamos, it works! I chose Oehm's answer for the explanation behind it. – CisBae Apr 21 '15 at 10:06

C Memory leak with valgrind

2 Answers2