Heap buffer overflow in stack function

Question

So i created a program that makes a stack and all of its operations, using a structure called stack.

Structure:

typedef struct {
        int *v;     /* contents of the stack */
        int cap;    /* capacity of v, i.e. how many elements can fit in v */
        int sz;     /* number of elements currently stored in v */
    } stack;

The program works fine but when i use fsantize it says that there is a buffer overflow on the heap in the Push function and i dont understand why because ive reallocated the bytes that i needed and freed the ones that i didnt need.

Program:

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

typedef struct {
        int *v;     /* contents of the stack */
        int cap;    /* capacity of v, i.e. how many elements can fit in v */
        int sz;     /* number of elements currently stored in v */
    } stack;

void init(stack * s)
{
    s->v = (int*) calloc(4,sizeof(int));
    s->cap = 4;
    s->sz = -1;
}

int is_empty(stack * s)
{
    if (s->sz == -1)
        return 1;
    else
        return 0;
}

void push(stack * s, int e)
{
    if (s->sz+1 <= s->cap)
    {
        s->sz++;
        s->v[s->sz] = e;
    }
    else
    {
        int *nv;
        s->cap++;
        s->sz++;
        nv = (int*) realloc(s->v, sizeof(int)*s->cap);
        free(s->v);
        s->v = nv;
        s->v[s->sz] = e;
    }
}

int pop(stack * s)
{
    if (is_empty(s) == 0)
    {
        int top = s->v[s->sz];
        s->sz--;
        return top;
    }
    else
    {
        printf("Impossible the stack isn't empty\n");
        return 0;
    }

}

void destroy(stack * s)
{
    //frees the stack bytes that were allocated
    free(s->v);
    free(s);
}

int main()
{
    int i;
    stack *pilha = (stack*) malloc(sizeof(stack));
    init(pilha);
    if (is_empty(pilha) == 1)
        printf("The stack is empty\n");
    pop(pilha);
    for (i = 0; i<=4;i++)
        push(pilha,i);
    push(pilha,5);
    printf("The top is:%d\n",pilha->v[pilha->sz]);
    if (is_empty(pilha) == 0)
        printf("The stack isn't empty\n");
    destroy(pilha);
    return 0;
}

Answer 1

This line:

if (s->sz+1 <= s->cap)

contains a logical error: if s->sz+1 == s->cap you need more space. For example, if s->cap is 4 you only have space for 4 elements (indexes from 0 to 3), but in the case of s->sz == 3 you enter the if and the result is:

s->sz++;         // 4
s->v[s->sz] = e; // s->v[4] overflow!

The right way to check would be if (s->sz+1 < s->cap), or even incrementing the value first:

s->sz++;

if (s->sz < s->cap) {
    // ...

---

This:

nv = (int*) realloc(s->v, sizeof(int)*s->cap);
free(s->v);
s->v = nv;

Is also wrong. First, you are assuming that realloc() allocates new memory and that you need to free() the old buffer: you don't, realloc() does that for you if needed. Secondly, you are assuming that realloc() does not fail (as you are doing anywhere else in your code, malloc(), calloc(), etc). Third, you are casting the return value (again as you are doing anywhere else in your code), which you shouldn't (see Do I cast the result of malloc?).

What you should do instead is:

nv = realloc(s->v, sizeof(int)*s->cap);
if (nv == NULL) {
    // Handle error, abort execution.
}

s->v = nv;

The check if (nv == NULL) should be done after every single call of malloc(), realloc() or calloc().