Heap corruption in an intrusive data structure example

Question

Here is a doubly linked list, with the node/link carrying the information needed in order to be stored in the list (intrusive):

dlist.h:

#ifndef DLIST_H
#define DLIST_H

//--------------------------------------------------------------------------

typedef struct Link
{
    struct Link* succ;
    struct Link* prev;
} Link;

//--------------------------------------------------------------------------

typedef struct List
{
    Link* first;
    Link* last;
} List;

//--------------------------------------------------------------------------

void init(List* lst)
{
    assert(lst);

    lst->first = 0;
    lst->last = 0;
}

//--------------------------------------------------------------------------

List* create()
{
    List* lst = (List*) malloc(sizeof(List*));

    init(lst);

    return lst;
}

//--------------------------------------------------------------------------

void push_back(List* lst, Link* l)
{
    assert(l);
    assert(lst);
    {
        Link* last = lst->last;

        if (last)
        {
            last->succ = l;
            l->prev = last;
        }
        else
        {
            lst->first = l;
            l->prev = 0;
        }

        lst->last = l;
        l->succ = 0;
    }
}

//--------------------------------------------------------------------------

void clear (List* lst)
{
    assert(lst);
    {
        Link* curr = lst->first;
        Link* next = 0;

        while (curr)
        {
            next = curr->succ;

            free(curr);

            curr = next;
        }

        lst->first = 0;
        lst->last = 0;
    }
}

//--------------------------------------------------------------------------

void destroy (List* lst)
{
    assert(lst);

    clear(lst);

    free(lst);
}

//--------------------------------------------------------------------------

typedef struct Name
{
    Link l;
    char* s;
} Name;

//--------------------------------------------------------------------------

Name* make_name(char* str)
{
    Name* n = (Name*) malloc(sizeof(Name*));
    n->s = str;

    return n;
}

//--------------------------------------------------------------------------

#endif

main.c:

#include <stdlib.h>     // malloc
#include <stdio.h>      // printf
#include <assert.h>     // assert


#ifdef __cplusplus  


#else  // compiling in C. 

int main ()
{
    List* lst = create();

    char* names[ ] = { "Giorikas", "Kostikas", "Foo", "Bar", "Gosho", "Pesho" };
    char* name;

    int i = 0;
    int size = 6;

    for (i; i < size; ++i)
    {
        push_back(lst, (Link*)(make_name(names[i])));

        name = ((Name*)(lst->last))->s;
        printf("Name: %s \n", name);
    }

    destroy(lst);

    getchar();

    return 0;
}

#endif

Stepping with the debugger I get the names printed and in function clear(), at the first attempt of freeing a link, I get two warnings and finally:

_CrtIsValidHeapPointer(pUserData)

Note: after a bit of research I understand that: "you'll receive heap corruption not immediately on rewrite occurs, but on the next heap check, which will be performed on any next memory allocation/deallocation.". So, probably, what happens in clear()is the heap check that triggers the error.

Where is this heap corruption taking place?

Answer 1

You make bad allocations. You need to allocate objects not pointer to, so:

List* lst = (List*) malloc(sizeof(List*));

should be

List* lst = (List*) malloc(sizeof(List));

and the same for Nameat least. You can also remove the cast:

List* lst = malloc(sizeof(List));

-----EDIT----

and a much better idiom is:

List* lst = malloc(sizeof(*lst));