Переполнение буфера кучи в функции стека

Question

Итак, я создал программу, которая создает стек и все его операции, используя структуру под названием stack.

Структура:

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;

Программа работает нормально, но когда я использую fsantize он говорит о переполнении буфера в куче в функции Pu sh, и я не понимаю, почему, потому что ive перераспределил байты, которые мне нужны, и освободил те, которые мне не нужны.

Программа:

#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

Эта строка:

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

содержит логическую ошибку: если s->sz+1 == s->cap вам нужно больше места. Например, если s->cap равно 4, у вас есть место только для 4 элементов (индексы от 0 до 3), но в случае s->sz == 3 вы вводите if, и результат :

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

Правильный способ проверки - if (s->sz+1 < s->cap), или даже сначала увеличить значение:

s->sz++;

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

---

Это:

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

Это тоже неправильно. Во-первых, вы предполагаете, что realloc() выделяет новую память и что вам нужно free() старый буфер: вы этого не делаете, realloc() сделает это за вас, если это необходимо. Во-вторых, вы предполагаете, что realloc() не завершается ошибкой (как вы делаете в любом другом месте вашего кода, malloc(), calloc(), et c). В-третьих, вы приводите возвращаемое значение (опять же, как и в любом другом месте вашего кода), чего не следует (см. Do I cast the result of mallo c? ).

Вместо этого вам следует сделать следующее:

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

s->v = nv;

Проверка if (nv == NULL) должна выполняться после каждого вызова malloc(), realloc() или calloc().

Answer 2

Функция push недопустима.

Это условие в операторе if

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

может быть причиной неопределенного поведения. Предположим для простоты, что s->cap равно 1. Таким образом, вы можете использовать sh только один элемент без изменения размера динамически выделяемого массива. Таким образом, после нажатия новое значение s->sz будет равно 0. И вы не можете сделать sh еще одно новое значение без изменения размера массива. Однако условие в операторе if оценивается как истинное, и вы будете записывать в память за пределами выделенного массива.

Также этот фрагмент кода

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

недействителен. В случае успешного вызова reallo c память, на которую указывает s-> v, была освобождена (или повторно использована). Таким образом, вызов free снова вызовет неопределенное поведение. То есть будет ли попытка освободить уже перераспределенную память или будет освобождена новая выделенная память.

Функция pu sh может быть определена, например, следующим образом

int push( stack *s, int e )
{
    int success = 0;

    if ( ( success = s->sz+1 < s->cap ) )
    {
        s->v[++s->sz] = e;
    }
    else
    {
        int *nv = realloc( s->v, sizeof( int ) * ( s->cap + 1 ) );
        success = nv != NULL;

        if ( success )
        {
            s->v = nv;
            ++s->cap;
            s->v[++s->sz] = e;
        }
    }

    return success;
}

Но в любом случае было бы лучше установить начальное значение для члена данных sz на 0. В этом случае элемент данных будет отражать текущий размер стека.

Возвращаемое значение функции pop неоднозначно. Возвращаемое значение 0 может быть допустимым значением, хранящимся в стеке. Также функция не должна выдавать никаких сообщений. Именно вызывающий объект функции решает, выдавать ли сообщение, если оно есть.

Также нет необходимости динамически выделять сам объект типа stack. Он может иметь автоматическую c продолжительность хранения и быть локальной переменной.

И гораздо лучше, когда функция, инициализирующая стек, также имеет второй параметр, позволяющий вместо этого указать емкость созданного стека. использования magi c число 4.

Ниже приведена демонстрационная программа, которая показывает, как можно определить стек и его функции.

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

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

int init( stack * s, size_t capacity )
{
    s->sz  = 0;
    s->cap = 0;

    s->v = calloc( capacity, sizeof( int ) );

    int success = s->v != NULL; 

    if ( success )
    {
        s->cap = capacity;;
    }       

    return success;
}

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

int push( stack *s, int e )
{
    int success = 0;

    if ( ( success = s->sz < s->cap ) )
    {
        s->v[s->sz++] = e;
    }
    else
    {
        int *nv = realloc( s->v, sizeof( int ) * ( s->cap + 1 ) );
        success = nv != NULL;

        if ( success )
        {
            s->v = nv;
            ++s->cap;
            s->v[s->sz++] = e;
        }
    }

    return success;
}

int pop( stack *s, int *value )
{
    int success = !is_empty( s );

    if ( success )
    {
        *value = s->v[--s->sz];
    }

    return success;
}

void destroy( stack *s )
{
    free( s->v );
    s->v = NULL;
    s->cap = 0;
    s->sz = 0;
}

int main( void )
{
    stack pilha;
    init( &pilha, 4 );

    if ( is_empty( &pilha ) )
    {
        printf( "The stack is empty\n" );
    }        

    const int N = 5;

    for ( int i = 0; i < 5; i++ )
    {
        push( &pilha, i );
    }

    push( &pilha, N );

    while ( ! is_empty( &pilha ) )
    {
        int value;
        pop( &pilha, &value );
        printf( "the current top value is %d\n", value );
    }

    destroy( &pilha );

    if ( is_empty( &pilha ) )
    {
        printf("The stack isn't empty\n");
    }

    return 0;
}

Результат программы:

The stack is empty
the current top value is 5
the current top value is 4
the current top value is 3
the current top value is 2
the current top value is 1
the current top value is 0
The stack isn't empty