I am trying to add a simple linked queue with enqueue() and dequeue() functions to my C library.
In all tests, the queue seems to perform as expected, without any errors. However, when testing for memory leaks by appending 200 million elements and then popping them, the memory doesn’t seem to get freed, yet the list updates correctly.
enqueue() and dequeue() functions:
usf_queue *usf_enqueue(usf_queue *queue, usf_data d) {
//Enqueue to FIFO queue
if (queue == NULL) {
//Generate new queue
queue = (usf_queue *) malloc(sizeof(usf_queue));
if (queue == NULL) return NULL; //Memory allocation failure
//Empty at first
queue -> first = queue -> last = NULL;
}
usf_queuenode *append = (usf_queuenode *) malloc(sizeof(usf_queuenode));
if (append == NULL) return NULL; //Memory allocation failure
append -> data = d;
append -> next = NULL; //Last in line
if (queue -> last == NULL) //Was empty
queue -> first = queue -> last = append;
else { //Normal adding
queue -> last -> next = append;
queue -> last = append;
}
return queue;
}
usf_data usf_dequeue(usf_queue *queue) {
//Dequeue from FIFO queue
usf_data d;
usf_queuenode *old;
if (queue -> first == NULL || queue == NULL)
return (usf_data) { .p = NULL }; //No queue, or queue is empty
old = queue -> first;
d = old -> data; //Get data
if ((queue -> first = old -> next) == NULL)
queue -> last = NULL;
free(old); //Destroy dequeued node
return d;
}
Queue structures :
typedef union usf_data {
void *p;
uint64_t u;
int64_t i;
} usf_data;
typedef struct usf_queuenode {
usf_data data;
struct usf_queuenode *next;
} usf_queuenode;
typedef struct usf_queue {
usf_queuenode *first;
usf_queuenode *last;
} usf_queue;
And, finally, the test code :
#include "usflib2.h"
#include <stdio.h>
int main() {
usf_queue *q = NULL;
q = usf_enqueue(q, (usf_data) {.u = -1 });
for (int i = 1; i < 200000000; i++)
usf_enqueue(q, (usf_data) {.u = i});
printf("Done.n");
for (int i = 0; i < 200000000; i++) {
usf_dequeue(q);
}
free(q);
printf("Finishedn");
for(;;);
return 0;
}
15
It seems the ‘leak’ was actually caused by my misunderstanding of the C free() function.
I thought freed memory was made available to the OS, and other processes, but it seems that it stays locked into the process who first allocated it (at least, on my computer, the system prefers crashing than retaking freed memory).
EDIT: as pointed out by Avi Berger, this behavior is dependent on the program’s own memory management libraries.
1
Memory leak
There is memory leak potential, even if it does not fully account for OP’s woes.
Consider what happens when code returns due to if (append == NULL) return NULL;. If that allocation was the first data of the queue, then the prior queue = (usf_queue *) malloc(sizeof(usf_queue)); allocation is lost.
Undefined behavior (UB)
With usf_dequeue(usf_queue *queue) and queue == NULL, code attempts queue -> first which is UB.
To fix, change:
// if (queue -> first == NULL || queue == NULL)
if (queue == NULL || queue -> first == NULL)
Weak test
Rather than ignore the return value, it should be tested.
for (int i = 1; i < 200000000; i++)
// usf_enqueue(q, (usf_data) {.u = i});
if (usf_enqueue(q, (usf_data) {.u = i}) == NULL) {
TBD(); //Do something.
}
Same for q = usf_enqueue(q, (usf_data) {.u = -1 });.
usf_dequeue(q); should also test the data returned to see if it is the value expected.
Conclusion
I suggest to fix these issues and see if the improved code behaves more understandably.
2