Freeing memory in recursive function: free(): double free detected in tcache2 (beginner question)
ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
Freeing memory in recursive function: free(): double free detected in tcache2 (beginner question)
Hi
I have a section of code that should loop through a hash table and delete a linked list if present, for a cs50 problem set.
Code:
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
} node;
// Number of buckets
const unsigned int N = 500041;
// Hash table
node *table[N];
// ... lines omitted
bool unload(void)
{
// Uncomment for loop method
// node *ptr, *ptr2;
for (int a = 0; a < (N + 1); a++)
{
// Loop method
/*
ptr = table[a];
while(ptr != NULL)
{
ptr2 = ptr;
ptr = ptr->next;
free(ptr2);
}
*/
// Recursion method
if (table[a] != NULL)
{
delete_node(table[a]);
}
}
// used in separate functions earlier in code:
free(counter);
return (!fclose(dictfile));
}
void delete_node(node *ptr)
{
if (ptr != NULL)
{
delete_node(ptr->next);
free(ptr);
}
return;
}
I have a looped method (commented out) and a recursive method, but both give me the error in the subject line, which shows I am trying to free the same node twice.
I assume I have misunderstood something. What have I got wrong?
I have written what I think ought to be happening in pseudocode below:
- Recursive method: delete_node:
Quote:
1. If pointer is not null, then run delete_node again with the pointer to the next node.
2. This will run recursively, passing along the linked list, until null is reached. when delete_node will return.
3. The second-to-last call to delete_node will then run, and free the final node in the linked list, and return, allowing the third-to-last call to delete_node to run, and so on down the stack.
- Looped method:
Quote:
1. Until ptr reaches null, at the end of the linked list,
2. Point ptr2 to ptr (e.g. to memory address "0x100")
3. Point ptr to the next node in the linked list (e.g. at memory address "0x101"), while ptr2 remains pointing to where ptr was (at "0x100") (is this right?)
4. Now free memory at ptr2 (at "0x100"), then while loop runs again for ptr (at "0x101"), if it is not null.
#include <malloc.h> // free
#include <stdio.h>
#define LENGTH 1023
char* counter = NULL;
FILE* dictfile = NULL;
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}node;
void delete_node(node *ptr);
// Number of buckets
const unsigned int N = 500041;
// Hash table
node* table[N];
// ... lines omitted
bool unload(void)
{
#ifdef DEBUG
printf( "Function: unload START %s %02d\n", __FILE__, __LINE__);
#endif
// Uncomment for loop method
// node *ptr, *ptr2;
for( unsigned int a = 0; (N+1) > a; ++a)
// for( int a = 0; (N+1) > a; ++a)
{
// Loop method
/*
ptr = table[a];
while(ptr != NULL)
{
ptr2 = ptr;
ptr = ptr->next;
free(ptr2);
}
*/
// Recursion method
// if( NULL != table[(unsigned int)a] )
if( NULL != table[a] )
{
delete_node(table[a]);
}
}
// used in separate functions earlier in code:
if( NULL != counter )
{
free(counter);
}
int dictFileRet = 0;
if ( NULL != dictfile )
{
dictFileRet = fclose(dictfile);
dictfile = NULL;
}
#ifdef DEBUG
printf( "Function: unload END %s %02d\n", __FILE__, __LINE__);
#endif
return dictFileRet;
}
void delete_node(node *ptr)
{
#ifdef DEBUG
printf( "Function: delete_node START %s %02d\n", __FILE__, __LINE__);
#endif
if (ptr != NULL)
{
delete_node(ptr->next);
free(ptr);
}
#ifdef DEBUG
printf( "Function: delete_node END %s %02d\n", __FILE__, __LINE__);
#endif
return;
}
int main()
{
node* NullPtr = NULL;
unload();
delete_node(NullPtr);
delete_node(NullPtr);
delete_node(NullPtr);
return 0;
}
/*
01)
always use:
if ( 12 != variable )
instead of using
if ( variable != 12 )
new joinee may miss ! operator
02)
reset back to NULL after using free
03)
when using malloc validate malloc did not fail
04)
++a better than a++ related to object oriented programming.
05)
free only if not NULL
06)
initialize the variable at the location of definition.
07)
Compile using -g option to debug program/core dump files
08)
$ #Following output was obtained using old source code.
$ ./a.out
Function: unload START tcache2.C 21
Function: unload END tcache2.C 56
Function: delete_node START tcache2.C 63
Function: delete_node END tcache2.C 71
Function: delete_node START tcache2.C 63
Function: delete_node END tcache2.C 71
Function: delete_node START tcache2.C 63
Function: delete_node END tcache2.C 71
$ gcc.exe -g tcache2.C -o ./a.out -DDEBUG
*/
Quote:
This isn't needed, free() already checks for NULL pointer and does nothing in that case.
Above code I have written was a sample code.
It is always better to handle pointers using related null pointer exceptions.
Reason:
Same pointer might be used by other functions/process/thread/external libraries Since I have faced these kind of errors a lot through out my career and reported related bug report(a lot) at external libraries.
Last edited by murugesandins; 05-08-2024 at 05:55 AM.
Reason: a.out output inside source file was obtained using old source code.
you can use valgrind to check the code, you can add more logging to see what's going on and also you can debug your code (and compile with -g). The main question is the value of a.
I don't know how do you create that table array, usually table[N+1] is invalid, as it was already mentioned.
When I went back to the to the other two methods, they are now working, and I don't know why. As far as I know, I made no changes except to add the new code above, and a couple of suggestions made here.
Earlier in the day yesterday, I found that the programme alternated between two different outputs when run in short succession (without no recompiling etc.). As a spell-check programme, it switched between finding 6, and then occasionally 4, misspelled words, on the same input and dictionary file.
Are the memory leaks affecting this? I am using the remote Visual Studio environment provided by cs50/github at https://cs50.dev .
For reference, the full code of dictionary.c is below. (Other files in the programme are provided - links below for reference)
Code:
// Implements a dictionary's functionality
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dictionary.h"
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
} node;
void delete_node(node *ptr);
char wordlc[LENGTH + 1];
// TODO: Choose number of buckets in hash table - lowest prime number > 500,000
const unsigned int N = 500041;
// Hash table
node *table[N];
// Dictionary word counter
unsigned int *dictword_counter;
// Loaded dictionary file
FILE *dictfile;
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// Convert word to lowercase
short counter = 0;
while (*word != '\0')
{
wordlc[counter] = tolower(*word++);
counter++;
}
wordlc[counter] = '\0';
// Search linked list in the array at the hashed lowercase word
node *temp_node = table[hash(wordlc)];
while (temp_node != NULL)
{
if (!strcmp(wordlc, temp_node->word))
{
return true;
}
temp_node = temp_node->next;
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// Hash function inspired by djb2 (http://www.cse.yorku.ca/~oz/hash.html)
// Cycle through *word characters until "\0" null character at end of word
short counter = 0;
while (*word != '\0')
{
wordlc[counter] = tolower(*word++);
counter++;
}
wordlc[counter] = '\0';
// magic number 52711 is prime
unsigned int hash = 52711;
int i = 1;
for (short b = 1; i != 0; b++)
{
// hash * 127, but written bitwise for speed
hash = ((hash << 7) - hash) + i;
i = wordlc[b];
}
// Use remainder (modulo %) of division by number of buckets N, so output is less than N.
hash = hash % N;
// printf("return hash: %u\n", hash);
return hash;
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// Allocate memory for dict_word counter;
dictword_counter = malloc(sizeof(unsigned int));
if (dictword_counter == NULL)
{
printf("Could not allocate memory to load dictionary file.\n");
return 0;
}
// Open dictionary
dictfile = fopen(dictionary, "r");
if (dictfile == NULL)
{
printf("Could not open dictionary file.\n");
return 0;
}
// Read each word from dictionary file and load to hash table
// Also count the number of dictionary words, for later
*dictword_counter = 0;
char word_buffer[LENGTH];
while (fscanf(dictfile, "%s", word_buffer) != EOF)
{
// Allocate memory for new node and check success
// printf("%s\n", word_buffer);
node *n = malloc(sizeof(node));
if (n == NULL)
{
printf("Failed to allocate memory to new node.\n");
return 0;
}
// Define node word from the buffer
strcpy(n->word, word_buffer);
unsigned int i = hash(word_buffer);
// printf("hash value (modulo N): %i\n", i);
// Prepend new node to location of hash in the array:
// 1. Point the node to the first node in the linked list
n->next = table[i];
// 2. Point the table array to the new node, which is now first in the linked list.
table[i] = n;
// Not " *dictword_counter++; ", as returns "expression result unused" error
*dictword_counter = *dictword_counter + 1;
}
return 1;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// TODO
return *dictword_counter;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
// Uncomment for loop methods
// node *ptr, *ptr2;
for (int a = 0; a < N; a++)
{
// Loop through table with two pointers (working)
/*ptr = table[a];
while (ptr != NULL)
{
ptr2 = ptr;
ptr = ptr->next;
free(ptr2);
}*/
// Double loop method
/* printf("a: %i\n", a);
while (table[a] != NULL)
{
ptr = table[a];
printf("a: %i\n", a);
while (ptr != NULL)
{
// ptr2 = ptr;
ptr = ptr->next;
printf("*ptr: %s\n", ptr->word);
printf("*ptr: %p\n", &ptr);
}
free(ptr);
a++;
} */
// Recursion method
delete_node(table[a]);
}
free(dictword_counter);
return (!fclose(dictfile));
}
void delete_node(node *ptr)
{
if (ptr != NULL)
{
delete_node(ptr->next);
}
//strcpy(ptr->word, '\0');
ptr->next = NULL;
free(ptr);
return;
}
Earlier, I have written old output inside that source code.
Pasting updated code using updated output:
Code:
printf( "Function: delete_node END %s %02d\n", __FILE__, __LINE__);
Hence this was displaying:
Function: delete_node END tcache2.C Old line number
Updated code
Code:
$ /cygdrive/c/Users/murugesandins/cygwin/bin/cat.exe tcache2.C
#include <malloc.h> // free
#include <stdio.h>
#define LENGTH 1023
char* counter = NULL;
FILE* dictfile = NULL;
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
}node;
void delete_node(node *ptr);
// Number of buckets
const unsigned int N = 500041;
// Hash table
node* table[N];
// ... lines omitted
bool unload(void)
{
#ifdef DEBUG
printf( "Function: unload START %s %02d\n", __FILE__, __LINE__);
#endif
// Uncomment for loop method
// node *ptr, *ptr2;
for( unsigned int a = 0; (N+1) > a; ++a)
// for( int a = 0; (N+1) > a; ++a)
{
// Loop method
/*
ptr = table[a];
while(ptr != NULL)
{
ptr2 = ptr;
ptr = ptr->next;
free(ptr2);
}
*/
// Recursion method
// if( NULL != table[(unsigned int)a] )
if( NULL != table[a] )
{
delete_node(table[a]);
}
}
// used in separate functions earlier in code:
if( NULL != counter )
{
free(counter);
}
int dictFileRet = 0;
if ( NULL != dictfile )
{
dictFileRet = fclose(dictfile);
dictfile = NULL;
}
#ifdef DEBUG
printf( "Function: unload END %s %02d\n", __FILE__, __LINE__);
#endif
return dictFileRet;
}
void delete_node(node *ptr)
{
#ifdef DEBUG
printf( "Function: delete_node START %s %02d\n", __FILE__, __LINE__);
#endif
if (ptr != NULL)
{
delete_node(ptr->next);
free(ptr);
}
#ifdef DEBUG
printf( "Function: delete_node END %s %02d\n", __FILE__, __LINE__);
#endif
return;
}
int main()
{
node* NullPtr = NULL;
unload();
delete_node(NullPtr);
delete_node(NullPtr);
delete_node(NullPtr);
return 0;
}
/*
01)
always use:
if ( 12 != variable )
instead of using
if ( variable != 12 )
new joinee may miss ! operator
02)
reset back to NULL after using free
03)
when using malloc validate malloc did not fail
04)
++a better than a++ related to object oriented programming.
05)
free only if not NULL
06)
initialize the variable at the location of definition.
07)
Compile using -g option to debug program/core dump files
08)
$ gcc.exe -g tcache2.C -o ./a.out -DDEBUG
$ ./a.out
Function: unload START tcache2.C 21
Function: unload END tcache2.C 58
Function: delete_node START tcache2.C 65
Function: delete_node END tcache2.C 73
Function: delete_node START tcache2.C 65
Function: delete_node END tcache2.C 73
Function: delete_node START tcache2.C 65
Function: delete_node END tcache2.C 73
*/
Code:
$ /cygdrive/c/Users/murugesandins/cygwin/bin/gcc.exe tcache2.C -DDEBUG dictionary2.cc -o ./a.out
$ /usr/bin/file.exe tcache2.C dictionary2.cc
tcache2.cc: C source, ASCII text
dictionary2.cc: empty
$# I tried sample program hence I am using dictionary2.cc empty file.
$ ./a.out
Function: unload START tcache2.C 21
Function: unload END tcache2.C 58
Function: delete_node START tcache2.C 65
Function: delete_node END tcache2.C 73
Function: delete_node START tcache2.C 65
Function: delete_node END tcache2.C 73
Function: delete_node START tcache2.C 65
Function: delete_node END tcache2.C 73
Quote:
free only if not NULL
I have seen these kind of exception when I have used nwrfcsdk during 2012 SAP library.
Hence this is also required when parsing IDOC files and using external libraries.
One piece of "vital(!) battle wisdom" that I long-ago learned was: "as soon as you 'free' something that was referred-to by a pointer, immediately set that pointer (and all copies of it ...) to NULL/nil."
"Now, every reference to the storage is gone: you just made sure of that."
The "nanoseconds" required to perform this "extra" step literally do not matter, but your code will "in a stroke" become much more reliable. Because: "one piece of code" no longer has to worry about what "some other piece of code" might later be doing.
(Every "free()" routine knows to ignore a NULL/nil pointer ...)
Last edited by sundialsvcs; 04-27-2024 at 07:54 PM.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.