CODEWITHSUNDEEP
carraysmemorystackvalgrind
Adam R
Adam R

Reputation: 141

C - strange Valgrind complaint in array code

I have an array-backed stack implementation working for my operating systems course in C. I've nailed down all of the leaks, but Valgrind is still complaining about something that I can't grok:

==8162== Invalid read of size 8
==8162==    at 0x400E90: shift_left (stack.c:54)
==8162==    by 0x400E90: pop (stack.c:86)
==8162==    by 0x40104D: process_rpn (rpn.c:59)
==8162==    by 0x4009DF: main (main.c:43)
==8162==  Address 0x54f8100 is 0 bytes after a block of size 16 alloc'd
==8162==    at 0x4C2AC9B: realloc (vg_replace_malloc.c:785)
==8162==    by 0x400E45: resize_internal (stack.c:25)
==8162==    by 0x400E45: shift_right (stack.c:40)
==8162==    by 0x400E45: push (stack.c:71)
==8162==    by 0x400FF3: process_rpn (rpn.c:50)
==8162==    by 0x4009DF: main (main.c:43)

This occurs in both my shift_left and shift_right routines. Neither my instructor nor I can figure out what's wrong; here is the code. I'm about ready to call this a false positive in Valgrind, but I wanted another set of eyes before I did:

// shift internal array elements all left by one
void shift_left(stack_t* shift) {
    for(int i = 0; i < shift->elements; i++) {
        shift->backing[i] = shift->backing[i + 1];
        shift->backing[i + 1] = 0;
    }
}

where stack_t is a struct so defined:

typedef struct stack_t {
    double* backing;
    size_t capacity;
    size_t elements;
} stack_t;

and backing is allocated either with malloc, or realloc, in the case of an insertion resulting in a resize of the backing array.

Upvotes: 0

Views: 61

Answers (2)

chqrlie
chqrlie

Reputation: 145277

Your code is incorrect for multiple reasons:

  • You might access the backing array one position beyond the end of the array.
  • You overwrite the second and subsequent elements before copying them.

Here is a corrected version:

// shift internal array elements all left by one
void shift_left(stack_t *shift) {
    if (shift->elements > 0) {
        for (int i = 1; i < shift->elements; i++) {
            shift->backing[i - 1] = shift->backing[i];
        }
        shift->backing[shift->elements - 1] = 0;
    }
}

Upvotes: 0

Joachim Isaksson
Joachim Isaksson

Reputation: 181047

When elements == capacity and i has reached the index of the last element, 

shift->backing[i + 1]

...will index outside of allocated memory.

For example, when (as it looks like it is the case in your valgrind), capacity == elements == 2, i will loop up to 1 and shift->backing[i + 1] will reference shift->backing[2] which is outside the allocated array.

Upvotes: 2

Related Questions