Why a destroyed linked-list still could be read

Question

I'm trying to destroy a single-linked-list, at first, my code of the destroy function like this:

void destroy_list_v0 (SLINK *list)
{   
SLINK ptr = *list;

while (NULL != *list)
    {
    ptr = *list;
    *list = (*list)->next;
    free (ptr);
    }
}

Function v0 performs perfect. here is output.

Input a number for length of the link.
init_start.
init_end & traverset_start.
The 0th element is 0.
The 1st element is 5.
The 2nd element is 93.
The 3rd element is 92.
The 4th element is 70.
The 5th element is 92.
traverse_end & destroy_start.
destroy_end & traverse_start.
traverse_end.
All operations done.

Then I thought that single ponter is enough, so I adjust the function into single pointer version:

void destroy_list_v1 (SLINK list)
{
SLINK ptr = list;   
while (NULL != list)
    {
    ptr = list;
    list = list->next;
    free (ptr);
    }
}

Here is v1's output:

Input a number for length of the link.
init_start.
init_end & traverset_start.
The 0th element is 0.
The 1st element is 27.
The 2nd element is 38.
The 3rd element is 20.
The 4th element is 66.
The 5th element is 30.
traverse_end & destroy_start.
destroy_end & traverse_start.
The 0th element is 0.
The 1st element is 32759808.
The 2nd element is 32759968.
The 3rd element is 32759936.
The 4th element is 32759904.
The 5th element is 32759872.
traverse_end.
All operations done.

To confirm that the destroy function is working fine, I traverse the linked list after it is destroyed. I found that the list could be read(in case of v0, it could not be read), though the value of every node has changed and indeterminacy. I thought after v0 performs, the pointer of the list point to NULL, but after v1 performs, it still point to original address. To test this idea, I adjust the v0 to v2:

void destroy_list_v2 (SLINK *list)
{   
SLINK p_list = *list;
SLINK ptr = *list;
while (NULL != *p_list)
    {
    ptr = *p_list;
    p_list = p_list->next;
    free (ptr);
    }
}

here is the v2 output:

Input a number for length of the link.
init_start.
init_end & traverset_start.
The 0th element is 0.
The 1st element is 76.
The 2nd element is 53.
The 3rd element is 80.
The 4th element is 31.
The 5th element is 97.
traverse_end & destroy_start.
destroy_end & traverse_start.
The 0th element is 0.
The 1st element is 13860864.
The 2nd element is 13861024.
The 3rd element is 13860992.
The 4th element is 13860960.
The 5th element is 13860928.
traverse_end.
All operations done.

I think my analysis is right, but it lead to new question.

The node struct is here:

typedef struct tag_node
{
int elem;
struct tag_node *next;
}NODE, *SLINK; //SLINK means SINGLE LINK

I have 2 questions:

1: The pointer 'next' is stored in the memory space which current pointer point to, after free current node, why the memory space of the pointer 'next' still could be read? Is the pointer 'next' still alive? I have this question because I thought that after v1 or v2 performs, it should be only the header node that could be read.

2: I thoutht v1 and v2 destroy the whole list, after v1 or v2 performs, why the value of header is still? I thought it should be like 1st to 5th that had changed to an indeterminate number.

Here is the whole code and the environment is Debian, clang:

#include    <stdio.h>
#include    <stdlib.h>
#include    <time.h>
#include    <string.h>

#define     i_track(n)  printf ("The %s's is %d.\n", #n, (n))
#define     s_track(n)  printf ("%s.\n", #n);

typedef struct tag_node
{
int elem;
struct tag_node *next;
}NODE, *SLINK; //SLINK means SINGLE LINK

void  node_track (SLINK list);

NODE *node_generate (void);
SLINK init_list (int len);
SLINK locate_cur (SLINK list, int target_elem);
void insert_node (SLINK *list, int new_elem, int tag_elem);
SLINK traverse_list (SLINK list);
void clear_list (SLINK list);
void destroy_list_v0 (SLINK *list);
void destroy_list_v1 (SLINK list);
void destroy_list_v2 (SLINK *list);
void list_info (SLINK list, int node_elem);

int main (int argc, char *argv[])
{
int len;
SLINK list;
printf ("Input a number for length of the link.\n");
scanf ("%d", &len);
s_track(init_start);
list = init_list (len);
s_track(init_end & traverset_start);
traverse_list (list);
s_track(traverse_end & destroy_start);
//  destroy_list_v0 (&list);
//  destroy_list_v1 (list);
destroy_list_v2 (&list);
s_track(destroy_end & traverse_start);
traverse_list (list);
s_track(traverse_end);
s_track(All operations done);

return EXIT_SUCCESS;
}               /* ----------  end of function main  ---------- */

NODE *node_generate (void)
{
NODE *new_node = malloc (sizeof (NODE));
if (NULL == new_node)
{
    printf ("ERROR: malloc failed.\n");
    exit (EXIT_FAILURE);
}
memset (new_node, 0, sizeof(NODE));
return new_node;
}

SLINK locate_cur (SLINK list, int target_elem)
{
NODE *prev, *cur;
prev = node_generate ();
cur = node_generate ();
for (prev = list, cur = list->next; NULL != cur && target_elem != cur->elem; prev = cur, cur = cur->next)
    ;
return cur;
}

void insert_node (SLINK *list, int new_elem, int tag_elem)
{
NODE *new_node = node_generate ();
NODE *cur = *list;
new_node->elem = new_elem;
if ((int)NULL == tag_elem)
{
    new_node->next = (*list)->next;
    (*list)->next = new_node;
}
else
{
    *list = locate_cur (cur, tag_elem);
    new_node->next = (*list)->next;
    (*list)->next = new_node;
}
}

SLINK init_list (int len)
{
SLINK header = node_generate ();
srand ((unsigned) time(0));
int elem;
for (int i = 0; i < len; i++)
    {
        elem = rand () % 100;

        if (4 == elem / 10)
        {
            elem = elem + 50;
        }
        if (4 == elem % 10)
        {
            elem = elem + 5;
        }
        if (0 == elem % 100)
        {
            elem = elem + 999;
        }
        insert_node (&header, elem, (int)NULL); 
    }
return header;
}

void clear_list (SLINK list)
{
for (SLINK cur = list->next; NULL != cur; )
{
    cur = cur->next;
    free (list->next);
    list->next = cur;
}
}

void destroy_list_v0 (SLINK *list)
{   
SLINK ptr = *list;

while (NULL != *list)
{
    ptr = *list;
    *list = (*list)->next;
    free (ptr);
}
}

void destroy_list_v1 (SLINK list)
{   
SLINK ptr = list;

while (NULL != list)
{
    ptr = list;
    list = list->next;
    free (ptr);
}
}

void destroy_list_v2 (SLINK *list)
{
SLINK p_list = *list;
SLINK ptr = *list;
while (NULL != p_list)
{
    ptr = p_list;
    p_list = p_list->next;  
    free (ptr);
}
}

SLINK traverse_list (SLINK list)
{
SLINK ptr = list;
for (int node_num = 0; ptr != NULL; ptr = ptr->next)
{
    list_info (ptr, node_num);
    ++node_num;
}
return list;
}

void list_info (SLINK list, int node_num)
{
if (1 == node_num % 10 && 11 != node_num)
{
    printf ("The %dst element is %d.\n", node_num, list->elem);
}
else if (2 == node_num % 10 && 12 != node_num)
{
    printf ("The %dnd element is %d.\n", node_num, list->elem);
}
else if (3 == node_num % 10 && 13 != node_num)
{
    printf ("The %drd element is %d.\n", node_num, list->elem);
}
else
{
    printf ("The %dth element is %d.\n", node_num, list->elem);
}
}

void node_track (NODE *flag)
{
printf ("The flag element is %d.\n", flag->elem);
}

Answer 1

C99 says:

The free function causes the space pointed to by ptr to be deallocated, that is, made available for further allocation. If ptr is a null pointer, no action occurs. Otherwise, if the argument does not match a pointer earlier returned by the calloc, malloc, or realloc function, or if the space has been deallocated by a call to free or realloc, the behavior is undefined.

Answer 2

Get used to this in C. The phrase "the behavior is undefined" is a mantra you will soon get used to, and it means doing certain things can lead to anything from a crash to apparently perfect behavior.

Pointers are a classic case of this mantra. You freed the memory and can still access it? Well, it's undefined. Wait, it's daylight savings time and now it crashed? Well it's undefined. Wait, you ran it on Windows and it works fine except on days ending in Y? Well it's undefined.

Remember the mantra; it will serve you well. Expecting C to complain loudly when you do something wrong is the wrong expectation, and keeping this in mind can save you much grief and tears.

Answer 3

1. Welcome to the land of C, where you can do anything (even if it's not legal). What you've done is invoked undefined behavior. You're not allowed to access the deleted memory anymore, but no one is stopping you from trying. C doesn't check that you are indeed accessing valid memory. It just goes ahead and does what you tell it to, even if you tell it to do something wrong. The fact that it "worked" is a mixture of luck and implementation defined stuff. Bugs like these are hard to find because instead of crashing, the program continues, and you don't find the bug until a long while later when it finally does start crashing. Once you invoke undefined behavior (which is what happens when you access deleted memory), anything can happen, from a black hole opening up and swallowing us all, to the program crashing, to the program appearing to work just fine.

2. v1 and v2 do destroy the whole list, but freeing memory doesn't mean you also erase the values in memory. The values are still there, you just no longer are allowed to access them because you've given those memory buckets back to the OS. The buckets still hold values. They're just not yours anymore.

Answer 4

free() marks the buffer as free, which means that subsequent malloc() could use the same date area, it doesn't mean that it will be erased or anything, but it could be returned to the operating system (and hence accessing it could cause a segmentation fault).

Accessing the freed memory is a bug because even if it usually is still there untouched, you could be accessing memory used by some other functions.

Answer 5

Freeing the memory is not the same thing as changing the address contained in the pointer variable.

The call to free releases the memory back to the heap managed by malloc. If you have a variable still pointing to the memory you had previously allocated, it is still pointing there after the free operation. However, it is a bug to use the pointer for anything after the free.

If you want to ensure your linked list does not still point to freed memory, you can assign NULL to each pointer in the structure after the associated memory has been freed.