Thread: Whaddya mean I clobbered past the mem block?

As far as I can tell, memory clobbering is the same as memory corruption (caused by writing). Since you're clobbering past the end of the allocated block, you're likely doing something along these lines:

Code:

char *block = malloc(10);
block[20] = 0;

In your case, it looks like it might be an off-by-one bug, like not allocating space for the null in a C string. Try allocating enough memory for one more item or setting new->max to INIT_HEAP_SIZE-1.

Oh, I hadn't realized that the error only occurs when you try to free the memory.

Google finds many definitions of heap corruption.
http://www.windowsitpro.com/Article/...275/22275.html
http://www.ogre3d.org/wiki/index.php/Heap_Corruption

Anyway, I don't get how you can corrupt the heap without Valgrind realizing it until you try to free the memory. The only thing that makes sense is that this pointer is invalid somehow.

Say, for example, you had some memory that looked like this.

Code:

<random>
char *one's dynamically allocated data (100 bytes)
char *two's dynamically allocated data (100 bytes)
<random>

If you set one[101] to something, you'd likely make two point to somewhere else. Valgrind should detect this, since one[101] is an invalid index, but if you did some funky pointer arithmetic or something it might not, I don't know.

If I'm right, you can fire up your debugger and watch the value of that items array. If it changes value somewhere it shouldn't be, then that's your problem. It's unlikely that that stab in the dark is right, however.

How large is your code?

BTW, since you seem to be going

Code:

p = malloc(size);
HANDLE_OUT_OF_MEM(p);

a lot, consider wrapping it in a function.

Well yeah I've fired my debugger and looked at what heap->items is pointing to...so far I haven't caught anything fishy

If you have the patience to look over the code, here it is (at least the relevant parts):

The tester:

Code:

int main() {
  int memory_used;
  Table *heap;

  mcheck_pedantic(NULL);

  heap= create(); /* code posted in my initial post */

  insert(&heap, 1, 100);
  delete(&heap, 1);
  printf("Size: %d\n", size(heap));

  insert(&heap, 2, 200);
  if (delete(&heap, 3) == 1)
    printf("removed a non-existent key\n");
  else printf("Size: %d\n", size(heap));

  clear(&heap);

  mcheck_check_all();

the insert function

Code:

 

Data insert(Table **table, Key key, Data item)
{
	Table *t = *table;
	Item new_item;
	Item *exists = contains(t, key), *new_item_pntr = NULL, 
		*new_item_parent_pntr = NULL;
	Item * first_item = t->items; /* should be read-only! */
	int index = 0;
	
	if (table == NULL)
		return 0;
	
	new_item.key = key;
	new_item.data = item;
	
	/* case where key already exists in table */
	if (exists != NULL)
	{
		exists->data = item;
		return exists->data;
	}
	
	
	
	
	
	/* case where key doesn't exist in table */
	
	if (t->size == t->max) /* need to make table bigger*/
	{
		int new_max = (t->max*2) + 1;
		Item *items = realloc(t->items, new_max);
		HANDLE_OUT_OF_MEM(items);
		t->items = items;
		t->max = new_max;
		/* update first_item variable */
		first_item = t->items;
	}
	
	
	
	/* 
	 * add new_item into table
	 */
	index = t->size;
	new_item_pntr = first_item + GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
	
	*new_item_pntr = new_item;
	memcpy(new_item_pntr, &new_item, sizeof(Item));
	printf("Adding %d, %d to %d\n", key, item, (int)new_item_pntr);
	/*
	 * if it is first item to be inserted, so no need to bother
	 * bubbling up the item
	 */
	if (t->size == 0) /* using == 0 because size isn't updated yet*/
	{
		++(t->size);
		*table = t;
		return new_item_pntr->data;
	}
	
	
	
	index = GET_PARENT_OF_INDEX(index);
	new_item_parent_pntr = first_item + 
							GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
	
	/* bubble new_item up */
	while (new_item_pntr->key < new_item_parent_pntr->key)
	{
		
		item_memswap(new_item_pntr, new_item_parent_pntr);
		
		index = GET_PARENT_OF_INDEX(index);
		
		new_item_pntr = new_item_parent_pntr;
		new_item_parent_pntr = first_item + 
								GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
		
	}
	
	++(t->size);
	*table = t;
	return new_item_pntr->data; /* could just return data, but this
									serves as a debugging statement 
									also */
}

the delete

Code:

int delete(Table **table, Key key)
{
	Item * to_remove, *last, *temp, *first;
	Table * t;
	int index = 0, direction = 0;
	
	if (table == NULL || (*table)->size == 0)
		return 0;
	
	t = *table;
	first = t->items;
	to_remove = contains(t, key);
	if (to_remove == NULL)
		return 0;
	
	last = first + GET_RELATIVE_MEM_ADDR_OF_INDEX((t->size)-1);
	index = get_item_index(t, to_remove->key);
	
	if (t->size > 1)
		item_memswap(last, to_remove);
	
	
	temp = last;
	last = to_remove;
	to_remove = temp;
	
	--(t->size); /* this is the removal part, the next item 
	 				to be inserted will overwrite the last element
	 				which was to be removed anyways */
	
	/* bubble last up or down */
	direction = 0; /* direction 1 means bubble up, 0 means
					bubble down */
	if (last->key < (first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
									GET_PARENT_OF_INDEX(index)
															 ))->key)
		direction = 1;
	
	if (t->size > 1)
	{
		if (direction) /* bubble up */
		{
			Item * parent = first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
										GET_PARENT_OF_INDEX(index)
											 						);
			while (last->key < parent->key)
			{
				item_memswap(last, parent);
				index = GET_PARENT_OF_INDEX(index);				
				last = parent;
				parent = first + GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
			}
		}
		else /* bubble down */
		{
			Item *right_child, *left_child, *changed = NULL;
			right_child = first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
										GET_RIGHT_CHILD_OF_INDEX(index)
																  );
			left_child = first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
										GET_LEFT_CHILD_OF_INDEX(index)
																);
			while (last->key > right_child->key ||
				last->key > left_child->key )
			{	
				if (right_child->key > left_child->key)
					changed = right_child;
				else
					changed = left_child;
				
				item_memswap(last, changed);
				
				index = get_item_index(t, changed->key);				
				last = changed;
				right_child = first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
											GET_RIGHT_CHILD_OF_INDEX(index)
																	  );
				left_child = first + GET_RELATIVE_MEM_ADDR_OF_INDEX (
											GET_LEFT_CHILD_OF_INDEX(index)
																	);
				
			}
																			
		}
	}	
	
	
	/* update the capacity of the table */
	if ((double)size(t)/(double)capacity(t) < 0.25)
	{
		int new_max = ((t->size)-1)/2;
		Item *items = realloc(t->items, new_max*sizeof(Item));
		
		HANDLE_OUT_OF_MEM(items);
		t->items = items;
		printf("new items at %d\n", (int)(t->items));
		t->max = new_max;

	}
	*table = t;
	return 1;
	
}

and finally the clear

Code:

void clear(Table **table)
{
	if (table != NULL && *table != NULL)
	{
		printf("table at %d\n", (int)(*table));
		printf("Items at %d\n", (int)((*table)->items));
		free(((*table)->items));
		(*table)->size = 0;
		
		(*table)->max = 0;
		free(*table);
	}
}

Wait a minute. Are you using Valgrind? If so, why are you calling those mcheck_*() functions? Are they your functions?

Code:

	index = t->size;
	new_item_pntr = first_item + GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
	
	*new_item_pntr = new_item;
	memcpy(new_item_pntr, &new_item, sizeof(Item));

That memcpy() is overwriting the data that the previous line puts into new_item_pntr. Actually, the two lines both do exactly the same thing, assuming that .items is declared as something like

Code:

Items *items;

Code:

		++(t->size);
		*table = t;
		return new_item_pntr->data;

That code is duplicated in two places. If you invert the if conditional, you should be able to avoid this duplication.

Anyhow, here's what I imagine is your main problem.

Code:

Item *items = realloc(t->items, new_max);

You need new_max*sizeof(Item) for the size. Oops.

Having a function called delete() is probably a bad idea, because delete is a C++ keyword -- so if your code ever needed to be compiled as or used in C++, the name would have to be changed.

Did you try fixing the problem that I pointed out? You have this:

Code:

Item *items = realloc(t->items, new_max);

And undoubtably you want this:

Code:

Item *items = realloc(t->items, new_max * sizeof(Item));

yes i changed that but it still doesnt work.

Originally Posted by dwks

Wait a minute. Are you using Valgrind? If so, why are you calling those mcheck_*() functions? Are they your functions?

Code:

	index = t->size;
	new_item_pntr = first_item + GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
	
	*new_item_pntr = new_item;
	memcpy(new_item_pntr, &new_item, sizeof(Item));

That memcpy() is overwriting the data that the previous line puts into new_item_pntr. Actually, the two lines both do exactly the same thing, assuming that .items is declared as something like

Code:

Items *items;

Code:

		++(t->size);
		*table = t;
		return new_item_pntr->data;

That code is duplicated in two places. If you invert the if conditional, you should be able to avoid this duplication.

Anyhow, here's what I imagine is your main problem.

Code:

Item *items = realloc(t->items, new_max);

You need new_max*sizeof(Item) for the size. Oops.

Having a function called delete() is probably a bad idea, because delete is a C++ keyword -- so if your code ever needed to be compiled as or used in C++, the name would have to be changed.

well this is actually a project for my class. The professor provided us with the tests (which we shouldn't modify) that use the mcheck funcs. So i have no control over that... ditto with the delete function.

Well, ask your professor if they've ever needed to use their C code in C++. Never mind that some "C" IDEs have C++ syntax highlighting, so "delete" will be highlighted like a keyword . . . .

What does GET_RELATIVE_MEM_ADDR_OF_INDEX() do? What is its code? Or is that part of the professor's code? Because, really, this is overly verbose and complicated.

Code:

	Item * first_item = t->items; /* should be read-only! */

    /* ... */

	index = t->size;
	new_item_pntr = first_item + GET_RELATIVE_MEM_ADDR_OF_INDEX(index);
	
	*new_item_pntr = new_item;
	memcpy(new_item_pntr, &new_item, sizeof(Item));

You could get away with

Code:

t->items[t->size] = new_item;

assuming GET_RELATIVE_MEM_ADDR_OF_INDEX() does what I think it does. That is, something like

Code:

#define GET_RELATIVE_MEM_ADDR_OF_INDEX(x) (x)

You're going way over the bounds of your array.

Here's how pointers work in C. When you have an int pointer, this is how you access the first element in the array: data[0]. The second element is data[1], the third is data[2], and so on. However, this takes into account the size of each element in data! data[1] is four bytes farther along in memory that data[0] (assuming four-byte ints). If you use *(data + 1*4), you're actually going 16 bytes past the beginning of the array, which is not what you want. However, this is exactly what you're doing.

Does this work if the item is a structure?

Structures can be assigned with a single assignment statement. Every element in the array is copied over. This can cause troubles if the structure contains pointers, but never mind. If it does, you'll need to do a "deep copy" yourself, duplicating strings and so on. Most of the time, this works.

Code:

struct whatever one = something(), two = one;

Just try the code I gave you. Really, it should be that simple.

When you allocate memory like this

Code:

int *p = malloc(4 * sizeof(int));

just treat it as if you'd gone

Code:

int p[4];

You can use p[0], p[1], p[2], and p[3] in both cases. Using

Code:

int *first = p;
*(first + 2 * sizeof(int)) = 0;

to access the second element is not what you want.

I don't really understand it either. The only thing that sort of makes sense is that the memory that you're overwriting into is your memory, and you can legitimately write to it. Otherwise, like you say, mcheck_*() should catch it. How this creates a situation that can only be detected when you call free() I'm not sure.

But anything can happen with a buffer overrun. "Undefined behaviour" is a synonym for "un-understandable, random, and wacky things" -- or so it seems sometimes.

Actually, I think those mcheck_*() functions aren't working properly -- because Valgrind detected that stuff immediately, right? Invalid read, invalid write, all of that . . . that means that you shouldn't be reading and writing to those memory locations.

Anyway, it doesn't matter too much as long as your code works in the end (according to Valgrind, because it seems to be more accurate). Does it work? (I realize that that's a lot of code to change.)