Search code examples
cheap-memoryheap-corruption

In C language, there is an error when deallocating memory in the implementation of dynamic arrays


I want to simulate a C++ vector in C language, and inside my vector structure, I maintain an array of type void*, defined as follows:

struct vector
{
//"base" is used to indicate the initial position of the maintained array, while "_end" represents //the position immediately after the last stored data.
    void** _end;
    void** base;
    size_t _capacity;
    size_t _increment;
};
typedef struct vector* vector;

The following code is used to initialize a vector structure.

vector create_vector()
{
    vector vec = (vector)malloc(sizeof(struct vector));
    if (!vec) {
        fprintf(stderr, "error occurred when creating the vector");
        return NULL;
    }
    vec->base = (void**)malloc(2*sizeof(void*));//The initial capacity is 2.
    if (!vec->base) {
        fprintf(stderr, "error occurred when allocating the vector base");
        free(vec); // deallocating memory of vec.
        return NULL;
    }
    vec->_end = vec->base;
    vec->_capacity = 2;
    vec->_increment = DEFAULT_INCREMENT;
}

To dispose a vector:

void dispose_vector(vector vec)
{
    if (vec)
    {
        free(vec->base);//This is where the bug happens, but I don't know how this occurs //and how to solve that.  
        vec -> base = NULL;
        vec->_end = NULL;
                free(vec);
         }
}

Adding elements from the tail (end):

void push_back(vector vec, void* _val_ptr)
{
    if (vec->_end - vec->base >= vec->_capacity)
    {
        vec->base = (void* *)realloc(vec->base, vec->_capacity + vec->_increment);
        if (vec->base == NULL)fprintf(stderr, "reallocating space failed.");        
        vec->_end = vec->base + vec->_capacity;
            vec->_capacity += vec->_increment;

            for (void** it = vec->_end; it != vec->base + vec->_capacity-1; it = it + 1)
                *it = NULL;
    }
    *(vec->_end++) = _val_ptr;
}

This is the code in the main function.

int main()
{   
    vector vec = create_vector();
    for (int i = 1; i <= 80; ++i)//add 80 elemments to the vector
    {
        char* p = (char*)malloc(sizeof(char));
        *p = 'c';
        push_back(vec,p);
    }
    for (size_t pos = 0; pos != 80; ++pos)
    {
        
        putchar(*(char*)(vec->base[pos]));
        free(vec->base[pos]);
        vec->base[pos] = NULL;
    }
    dispose_vector(vec);
    return 0;
}/

Solution

  • This line:

            vec->base = (void* *)realloc(vec->base, vec->_capacity + vec->_increment);
    

    You need to scale by sizeof *vec->base:

            size_t nsize = sizeof(*vec->base) * (vec->_capacity+vec->_increment);
            /* never cast alloc */
            void **nbase = realloc(vec->base, nsize);
            if (nbase == NULL) {
                /* what to do, well at least we know what vec->base is */
            } else {
                vec->base = nbase;
            }
    

    My best guess is you have corrupted your heap by undersizing >base; so when your allocator attempts to release it, its free list is corrupt.