C Linked list size not limited by malloc

Question

I have created a linked list with the following code. As you can see, I have used malloc to created a list of size 3. But I ran the for loop over size 10 to initialize and print.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

struct node {
        int value;
        struct node *next;
};

int main() {
        //code
        struct node **head;
        struct node *curr;
        curr = (struct node *) malloc(sizeof(struct node)*3);
        head = &curr;
        printf("done 1\n");
        (*head)->value = 0;
        (*head)->next = NULL;
        for(int i = 1; i < 10; i++) {
                (*head+i-1)->next = (*head+i);
                (*head+i)->value = i;
                (*head+i)->next = NULL;
        }
        curr = *head;
        printf("done 2\n");
        for(int i = 0; i < 10; i++) {
                printf("%d\t", (*head + i)->value);
                //curr = curr->next;
        }
        printf("\ndone 3\n");
        //free(curr);
        return 0;
}

when I compile and run the code, the result obtained is,

done 1
done 2
0   1   2   3   154208560   842282289   876087600   154744882   808859448   875837236
done 3

Why am I able to assign values to the 4th node and access it when I actually created a list of size 3?

I see that garbage values were being printed from 5th to 10th node access. But how is the 4th node being created?

P.S:

I know that 10!=3. The code ran properly when I put the loop in its limits. I wanted to see what will happen when we go out of bounds. I see that the 4th node was also created as I was able to assign value when I actually created a list of size 3.

This is purely to see if I will get seg fault or not.

Accessing beyond the end of the allocated memory is [undefined behavior](https://stackoverflow.com/questions/2397984/undefined-unspecified-and-implementation-defined-behavior). Anything can happen, including appearing to work. — user3386109, Jun 12 '16 at 00:17
Is it? I didn't knew it! I know that 10!=3. The code ran properly when I put the loop in its limits. I wanted to see what will happen when we go out of bounds. I see that the 4th node was also created as I was able to assign value when I actually created a list of size 3. — Aspirant9, Jun 12 '16 at 00:20
You're trampling through memory and it's undefined behavior. Sometimes programs with undefined behavior don't crash, and sometimes you can be unlucky and your fundamentally broken program appears to work. — Paul Hankin, Jun 12 '16 at 00:22

score 7 · Accepted Answer · edited Jun 12 '16 at 00:38

7

You're invoking undefined behavior. When you do this, the program may crash, it may appear to work properly, or it might behave in a seemingly random manner.

C doesn't perform any kind of bounds checks on arrays or allocated memory. It's one of the things that makes it fast. What that also means is that it will allow you to do things you're not supposed to do. It trusts the programmer to "do the right thing".

On your particular machine, you see random data after the third element. When I run the same code on my machine, I happen to get the expected output as though enough memory was allocated. Also, if I uncomment the call to free, the program crashes. That's undefined behavior.

Trying to understand undefined behavior is usually a futile effort. It all depends on the implementation details of your compiler and the machine it runs on. In this case, the memory being written to was probably unallocated memory in the heap after the memory that was properly allocated. Depending on how malloc is implemented, that part of memory may contain data needed for malloc and other functions to run properly. The point is that writing past the end of an array does not guarantee a crash, so you need to be careful.

edited Jun 12 '16 at 00:38

Aspirant9

163
1
13

answered Jun 12 '16 at 00:18

dbush

205,898
23
218
273

You mean that the 4th node value you got was a garbage value too? – Aspirant9 Jun 12 '16 at 00:22
No, my machine outputted `0 1 2 3 4 5 6 7 8 9`. Also, if I uncomment the `free` function call, the program crashes. – dbush Jun 12 '16 at 00:24
Yes. I understand that, but how was your program was able to assign the values 3 to 9 to the list when infact your array size was 3? Is it because the program tried to access the memory location as a struct pointer to the location(struct node) and access the first location(node->value) to save data and hence the data was able to be saved?? – Aspirant9 Jun 12 '16 at 00:30
2

Trying to understand undefined behavior is usually a futile effort. It all depends on the implementation details of your compiler and the machine it runs on. In this case, the memory being written to was probably unallocated memory in the heap after the memory that was properly allocated. Depending on how `malloc` is implemented, that part of memory may contain data needed for `malloc` and other functions to run properly. The point is that writing past the end of an array does not guarantee a crash, so you need to be careful. – dbush Jun 12 '16 at 00:33
"C doesn't perform any kind of bounds checks on arrays or allocated memory." --> C is not required to check bounds. A given implementation _might_ check bounds and still be a conforming compiler. Still UV – chux - Reinstate Monica Jun 12 '16 at 04:33

score 1 · Answer 2 · answered Jun 12 '16 at 00:22

This code will behave differently on the different operating systems.

You may get away even with assigning all 10 integers and print then correctly.

Your code puts the beginning of list on the heap with allocations for only 3 elements.

You may get lucky and use memory for all 10 element or your program will crash on the 4-th!

C Linked list size not limited by malloc

2 Answers2