Ziezi Ziezi -4 years ago 63
C Question

Heap corruption in an intrusive data structure example

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 Source

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));
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download