C pushing too many items on handrolled queue -- Why is this not segfaulting?

Question

I am pushing 7 items while I only malloc'd for 5 items, but I don't see any segfaults happening. What am I missing? I thought this would cause the pointer to move past the array bounds and

#include "stdlib.h"
#include "stdio.h"
#include "assert.h"

typedef struct {
    int *space;
    int size;
    int *start;
    int *end;
} queue_t;

typedef char BOOL;

#define TRUE 1
#define FALSE 0

void queue_print(queue_t *queue) {

    for (int *cur = queue->start; cur < queue->end; cur++) {
        printf("%i,", *cur);
    }

    printf("\n");
}

void queue_init(queue_t **queue, int size) {
    (*queue) = (queue_t*) malloc(sizeof(queue_t));
    (*queue)->space = (int*) malloc(sizeof(int) * size);
    (*queue)->size = size;
    (*queue)->start = (*queue)->space;
    (*queue)->end = (*queue)->space;
}

void queue_push(queue_t *queue, int elem) {
    *(queue->end) = elem;
    queue->end++;
}

int queue_pop(queue_t *queue) {
    int ret = *(queue->start);
    queue->start++;
    return ret;
}

int main(int argc, char const *argv[])
{
    queue_t *queue;
    queue_init(&queue, 5);
    queue_print(queue);
    queue_push(queue, 1);
    queue_print(queue);
    queue_push(queue, 2);
    queue_print(queue);
    queue_push(queue, 3);
    queue_print(queue);
    queue_push(queue, 4);
    queue_print(queue);
    queue_push(queue, 5);
    queue_print(queue);
    queue_push(queue, 6);
    queue_print(queue);
    queue_push(queue, 7);
    queue_print(queue);
    printf("%i\n", queue->size);
    queue->space[123] = 4;
    return 0;
}

The output is:

1,
1,2,
1,2,3,
1,2,3,4,
1,2,3,4,5,
1,2,3,4,5,6,
1,2,3,4,5,6,7,

well, you will highly probably have problem in your next malloc. :-) Just duplicate your code in the main and try to create another queue.. — Arash, Mar 08 '17 at 01:52
Interesting. The clang static analyzer warns me of a possible memory leak in the a second queue. — Rodrigo Stv, Mar 08 '17 at 02:01

DYZ · Answer 1 · 2017-03-08T01:54:22.240

0

C does not check out of bounds accesses, but your program corrupts the heap, and when you call malloc() again in the future, you will probably have a segfault.

edited Mar 08 '17 at 01:54

answered Mar 08 '17 at 01:50

DYZ

55,249
10
64
93

That is interesting. Would you be willing to explain more about it or point to some source of information that I could use for studying this case? Thanks a lot! – Rodrigo Stv Mar 08 '17 at 01:51
This may help: http://stackoverflow.com/questions/1957099/how-do-free-and-malloc-work-in-c – DYZ Mar 08 '17 at 01:52
_Will probably_ cause. Changed the answer to address the probability aspect. – DYZ Mar 08 '17 at 01:54

score 0 · Answer 2 · answered Mar 08 '17 at 02:08

0

You allocate space to hold 5 ints with your call to queue_init. If you run your code in gdb, and examine the memory at the location of queue->start you will see something like this:

(gdb) p *queue

You'll see a memory address for the start member. Use that address in the examine memory command, something like this:

(gdb) x/8 0x602450

gdb will print something like this:

0x602450:   0   0   0   0
0x602460:   0   0   134049  0

Everything after the 5th byte belongs to something either unallocated or previously allocated. After your 7th call to queue_push, and you examine memory again, you'd see something like this:

(gdb) x/8 0x602450
0x602450:   1   2   3   4
0x602460:   5   6   7   0

So, the runtime doesn't prevent you from overwriting unallocated or previously allocated memory. But, you might have written over something important that can cause problems for the runtime or maybe other threads in your process.

answered Mar 08 '17 at 02:08

bruceg

2,433
1
22
29

1

Very good explanation! So now I understand what is happening. But if I can write beyond the end of array, what is a segfault then? From http://www.cprogramming.com/debugging/segfaults.html I have: "There are four common mistakes that lead to segmentation faults: dereferencing NULL, dereferencing an uninitialized pointer, dereferencing a pointer that has been freed (or deleted, in C++) or that has gone out of scope (in the case of arrays declared in functions), and writing off the end of an array." – Rodrigo Stv Mar 08 '17 at 02:12
1

I guess writing off the end of an array won't always cause the segmentation fault. It depends what you write into. Some memory managers will automatically detect it and throw a runtime error. Also, when you free the memory it will most likely throw an error. So, maybe add these two lines before the `return` of your `main`: `free(queue->space); free(queue);` – bruceg Mar 08 '17 at 02:19
2

Yep. That throws an error straight from the memory allocator. How much fun is this? TKS! – Rodrigo Stv Mar 08 '17 at 02:28
2

Segfaults aren't like exceptions: they don't happen when you break the rules, only when the breakage is irrecoverable. You might write past the end of an array, but get "lucky" in that the array was placed near the beginning of the [page](https://en.wikipedia.org/wiki/Paging) and therefore there's "room" to wreck the rest of your memory instead of segfaulting immediately. – trent Mar 08 '17 at 02:28
1

I was thinking just this; but I supposed that the array should be placed at the end of the heap, not just the end of the page to cause segfault, because at the end of the heap it could overwrite other process' code. But maybe because of virtual memory page mapping the next page might just be other process'! – Rodrigo Stv Mar 08 '17 at 02:31
2

Right, it's wholly possible for `malloc()` to return a pointer to anywhere in the heap. I was thinking of a specific situation but pages are really irrelevant to the main point, which you seem to have understood anyway. – trent Mar 08 '17 at 02:47

C pushing too many items on handrolled queue -- Why is this not segfaulting?

2 Answers2