Valgrind invalid write / address 0 after alloc'd in simple queue code

Question

I don't understand why the following code for a queue is making valgrind warn about a invalid write and a address is 0 bytes after allocation. The code looks sane to be, it is very simple.

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

typedef struct {
    int size;
    int head;
    int count;
    int *items;
} queue_t;

void push(queue_t *q, int item) {
    if (q->count == q->size) {
        printf("overflow\n");
        exit(1);
    }
    q->items[q->count + q->head] = item;
    q->count++;
}

int pop(queue_t *q) {
    if (q->count == 0) {
        printf("underflow\n");
        exit(1);
    }
    int x = q->items[q->head];
    q->head++;
    q->head = q->head % q->size;
    q->count--;
    return x;
}

int main () {
    queue_t *q = (queue_t*) malloc(sizeof(queue_t));
    q->head = q->count = 0;
    q->size = 3;
    q->items = (int*) malloc(sizeof(int) * q->size);

    push(q,4);
    push(q,4);
    push(q,4);

    pop(q);
    push(q, 4);
    printf("%i\n", pop(q));
    free(q->items);
    free(q);
}

Output from valgrind:

==5930== Memcheck, a memory error detector
==5930== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==5930== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==5930== Command: ./array-queue
==5930== 
==5930== Invalid write of size 4
==5930==    at 0x40066E: push (array-queue.c:17)
==5930==    by 0x4007B1: main (array-queue.c:44)
==5930==  Address 0x51d50ac is 0 bytes after a block of size 12 alloc'd
==5930==    at 0x4C2AB8D: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==5930==    by 0x400756: main (array-queue.c:37)
==5930== 
4
==5930== 
==5930== HEAP SUMMARY:
==5930==     in use at exit: 0 bytes in 0 blocks
==5930==   total heap usage: 3 allocs, 3 frees, 1,060 bytes allocated
==5930== 
==5930== All heap blocks were freed -- no leaks are possible
==5930== 
==5930== For counts of detected and suppressed errors, rerun with: -v
==5930== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Do *NOT* cast the return of `malloc`, it is unnecessary. See: [**Do I cast the result of malloc?**](http://stackoverflow.com/q/605845/995714) for thorough explanation. All you need is `queue_t *q = malloc (sizeof *q);` and `q->items = malloc (sizeof q->items * q->size);`. — David C. Rankin, Mar 17 '17 at 02:29

score 3 · Accepted Answer · answered Mar 17 '17 at 02:23

3

You accounted for wraparound of the list in your pop function, but forgot to account for it in your push function. As a result, the fourth call to push reads past the end of the allocated buffer.

This:

q->items[q->count + q->head] = item;

Should be:

q->items[(q->count + q->head) % q->size] = item;

answered Mar 17 '17 at 02:23

dbush

205,898
23
218
273

Thanks for the answer, and hey what an amazing tool. – Rodrigo Stv Mar 17 '17 at 02:24
@RodrigoStv Glad I could help. Feel free to [accept this answer](http://stackoverflow.com/help/accepted-answer) if you found it useful. – dbush Mar 17 '17 at 02:46

Valgrind invalid write / address 0 after alloc'd in simple queue code

1 Answers1