This may be a really simple question, but I could not find an answer any place on the internet. I am working on a linked list implementation in C, and am checking the memory usage and de-allocation with valgrind. I have created the following implementation which works properly. The only place that malloc is called is in the push_int_list function, which allows a user to create and insert a struct to any index in the linked list. Yes, I know that it is not a true index like an array, but i am using the same lingo to describe the location of a data point. Furthermore, the push_int_list function will will iterate from the head or tail of the linked list depending on where the struct is to be inserted.
The implementation shown below works correctly; however, when I check the memory allocation and de-allocation with valgrind, it shows that I execute 6 allocs, and 6 frees. As you can see, I only call the push_int_list function 5 times, and therefore should only be executing 5 allocs and 5 frees. If I change the number of push statements, the number of allocs and frees in valgrind is always one more than I actually execute. Why does valgrind always show one more malloc than I actually execute.
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
// --------------------------------------------------------------------------------
// Linked list Struct to containt data
typedef struct int_list
{
int data;
struct int_list *next;
struct int_list *previous;
} int_list;
// --------------------------------------------------------------------------------
// Struct to track linked list data
typedef struct
{
size_t active_length;
struct int_list *head;
struct int_list *tail;
} Int;
// --------------------------------------------------------------------------------
// Basic initialization of data tracking struct
void init_int_list(Int *list) {
list->active_length = 0;
list->head = NULL;
list->tail = NULL;
}
// --------------------------------------------------------------------------------
// Function that allows user to push a struct to any indice
int push_int_list(Int *list, int data, size_t index) {
if (index < 0 || index > list->active_length) {
fprintf(stderr, "INdex out of range\n");
return -1;
}
struct int_list *dat = malloc(sizeof(int_list));
if (!dat) {
fprintf(stderr, "malloc failed in file %s at line %d\n", __FILE__, __LINE__);
return -1;
}
if (list->active_length == 0) {
// populate struct
dat->data = data;
dat->previous = NULL;
dat->next = NULL;
// Update linked list tracking struct
list->head = dat;
list->tail = dat;
list->active_length += 1;
}
else if (index == 0 && list->active_length > 0) {
// populate struct
dat->previous = NULL;
dat->next = list->head;
dat->data = data;
// Update data in the struct occupying hte next index
(list->head)->previous = dat;
// Update linked list tracking struct
list->head = dat;
list->active_length += 1;
}
else if (list->active_length > 0 && index == list->active_length) {
// populate struct
dat->data = data;
dat->next = NULL;
dat->previous = list->tail;
// Update struct occupying previous index
(list->tail)->next = dat;
// Update linked list tracking struct
list->tail = dat;
list->active_length += 1;
}
// The next two if statements are mean to reduce the iteration time by half
// if the index to be inserted is between 0 and active_length
else if (index < list->active_length / 2) {
struct int_list *current = list->head;
struct int_list *previous = NULL;
for (size_t i = 0; i < index; i++) {
previous = current;
current = current->next;
}
// populate struct
dat->data = data;
dat->next = current;
dat->previous = previous;
// Update previous and next struct
previous->next = dat;
current->previous = dat;
// Update linked list tracking struct
list->active_length += 1;
}
else {
struct int_list *current = list->tail;
struct int_list *next = NULL;
for (size_t i = list->active_length; i > index; i--) {
next = current;
current = current->previous;
}
// Update struct
dat->data = data;
dat->next = next;
dat->previous = current;
// Update previous and next struct
next->previous = dat;
current->next = dat;
// Update linked list tracking struct
list->active_length += 1;
}
return 1;
}
void free_int_list(Int *list) {
if (list->active_length > 0) {
struct int_list *tmp = NULL;
struct int_list *head = list->head;
while (head->next != NULL) {
tmp = head;
head = tmp->next;
free(tmp);
}
free(head);
}
}
// Begin code
int main() {
Int list;
init_int_list(&list);
push_int_list(&list, 1, 0);
push_int_list(&list, 2, 1);
push_int_list(&list, 3, 2);
push_int_list(&list, 4, 3);
push_int_list(&list, 8, 0);
// Print linked list
struct int_list *current = list.head;
for (size_t i = 0; i < list.active_length; i++) {
printf("%d\n", current->data);
current = current->next;
}
free_int_list(&list);
return 0;
}
valgrind information shown below
==10074== Memcheck, a memory error detector
==10074== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==10074== Using Valgrind-3.19.0 and LibVEX; rerun with -h for copyright info
==10074== Command: ./test
==10074==
8
1
2
3
4
==10074==
==10074== HEAP SUMMARY:
==10074== in use at exit: 0 bytes in 0 blocks
==10074== total heap usage: 6 allocs, 6 frees, 1,144 bytes allocated
==10074==
==10074== All heap blocks were freed -- no leaks are possible
==10074==
==10074== For lists of detected and suppressed errors, rerun with: -s
==10074== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
I have wondered if it is tracking the instantiation of the Int struct as a malloc, but this is created in stack memory as a static allocation, so I cant see why this would be tracked as a malloc in valgrind!
You are overthinking the problem. If Valgrind says "no leaks are possible" then you should believe it.
The memory is allocated for your call to printf. Since this memory is allocated in a 'singleton' manner, glibc does not free that memory when running outside of Valgrind. You should be able to confirm that by using gdb and putting breakpoints on malloc and free. Several other functions in glibc allocate singleton buffers.
Valgrind contains a hack to free this memory. When the guest starts it adds a redirection to exit() to call __libc_freeres() and then exit(). The freeres function doesn't get called normally and only exists for tools like Valgrind.
If you run Valgrind with --run-libc-freeres=no then memcheck will ho longer call __libc_freeres and so "detect" this allocation as a "reachable" leak.