Whaddya mean I clobbered past the mem block?

[TalonStriker]

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.

but this is precisely the sort of thing that mcheck is supposed to prevent right? If you do overrun, mcheck will start complaining. Or does mcheck only complain when you overwrite the memory-block's headers in the heap?

[TalonStriker]

edit: I found the bug!!!!!!!

Turns out that it had nothing to do with overwriting memory at all.

In this code in delete()

	/* 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;

When t->size was 0, the new_max becomes 0. Then I try to realloc 0 bytes of memory by accident. Turns out that the realloc function was messing up something in the heap because I was allocing 0 bytes. Once I added a condition (purely by accident) that prevented new_max from being 0, the free() worked fine.

[dwks]

Well, that's good that you found one of the problems. But your array indexing definitely needed an overhaul, so you learned something at least. You'll have to let us know if anything else strange happens.

For what it's worth, calling realloc() with a size of 0 is exactly like calling free().

[robatino]

> For what it's worth, calling realloc() with a size of 0 is exactly like calling free().

I thought that when allocating a 0-element dynamic array, upon success you get a non-NULL pointer, and that there are some resources associated with it that you would have to call free() to free up. But I'm not sure.

Edit: Actually, I'm fairly sure - on my Linux box,

#include <stdlib.h>

int main(void) {
  int *p;

  while (1) {
    p = malloc(0);
    free(p);
  }
}

uses relatively little memory, but the same code without the free(p) quickly sucks up memory and starts swapping.

[iMalc]

I don't know why you're assuming that this mcheck_ thingy can magically detect all buffer overruns. That simply isn't possible. It most likely just puts a few special tag values at the start and end of the allocated block. If you happen to overwrite those special values with a different value, then yes it will see it when you free the memory or exit the program. But if you happen to write the same value there, or happen to change it back before you free the memory, or happen to write past those, or happen to write to a different yet valid block of memory etc... then it wont see any problem.

The best buffer overrun detection possible, is to switch on page-heap-allocation (assuming Windows), which can then detect the overrun at the moment it is attempted. Even then though, you're only going to catch overruns by an amount of more than the padding bytes, and only in one direction, not on both ends of the allocated block (so not underrun and overrun at the same time).

These kind of things only ever attempt to catch such bugs.

[matsp]

I don't know why you're assuming that this mcheck_ thingy can magically detect all buffer overruns. That simply isn't possible. It most likely just puts a few special tag values at the start and end of the allocated block. If you happen to overwrite those special values with a different value, then yes it will see it when you free the memory or exit the program. But if you happen to write the same value there, or happen to change it back before you free the memory, or happen to write past those, or happen to write to a different yet valid block of memory etc... then it wont see any problem.

The best buffer overrun detection possible, is to switch on page-heap-allocation (assuming Windows), which can then detect the overrun at the moment it is attempted. Even then though, you're only going to catch overruns by an amount of more than the padding bytes, and only in one direction, not on both ends of the allocated block (so not underrun and overrun at the same time).

These kind of things only ever attempt to catch such bugs.

Actually, x86 has a feature what WOULD, if it was ever used, catch every single buffer overrun you could imagine. Unfortunately, it's also messy in all sorts of other ways, and it's called "segmented memory model". I think the biggest reason it's not popular is that it's time-consuming to set up each segment, and because of it's lack of popularity, it was never expanded beyond the 64KB segment descriptor table, which in turn means that only 16K segments can ever be in use at any given time. But it will catch a one-byte out of range on memory up to 1MB - then it's a 4KB granularity.

--
Mats

[iMalc]

Interesting, I didn't know about that one.

I guess the other potential way would be to run the program inside some kind of interpreter, much like VirtualPC, which checks every memory access. Would be extremely slow though.

[matsp]

Interesting, I didn't know about that one.

I guess the other potential way would be to run the program inside some kind of interpreter, much like VirtualPC, which checks every memory access. Would be extremely slow though.

Yes, that WOULD be slow - and you would have to teach the virtualization engine about what is a valid and invalid write, which would be a pain too, as the virutalization happens at a much lower level than the allocation of the memory block. No real good way to solve it - other than the already described methods of "barriers" around the allocated area and safety checks - and when possible, allocate at the end of a page, with an empty page next after.

--
Mats

[dwks]

Valgrind does check every single access. It emulates every single instruction that a program executes. When you run a program with Valgrind, not one of its instructions is actually executed directly.

Valgrind run with its memcheck tool will catch every invalid access (that gets executed), in theory at least. You don't have to compile your program with any special flags, you don't need to do anything -- you can take any existing executable and run it with Valgrind.

It's true that Valgrind slows down your program a lot, but you only have to run it during testing. With my SDL programs, my code often executes five to two hundred (at a guess) times slower than usual. But it's worth it, believe me.

Oh, and Valgrind only works under Linux.

That's why I was confused as to what the OP was doing. They said that Valgrind reported an out-of-memory error; that the output of their program included the message "memory clobbered past end of allocated block"; and their code had all these calls to mcheck_*().

BTW, I think the "mcheck_ thingy" in question is the GNU one: http://www.delorie.com/gnu/docs/glibc/libc_33.html

> For what it's worth, calling realloc() with a size of 0 is exactly like calling free().

I thought that when allocating a 0-element dynamic array, upon success you get a non-NULL pointer, and that there are some resources associated with it that you would have to call free() to free up. But I'm not sure.

When you pass a size of 0, this occurs:

If size is 0 and ptr is not a null pointer, the object pointed to is freed.

(From http://www.opengroup.org/onlinepubs/...s/realloc.html.)

I took that to mean that it would be the same as calling free().

malloc() is different, it's true.

If the size of the space requested is 0, the behavior is implementation-defined: the value returned shall be either a null pointer or a unique pointer.

(From http://www.opengroup.org/onlinepubs/...ns/malloc.html.)

So the way to test this would be

#include <stdlib.h>

int main() {
    for(;;) {
        realloc(0, 0);
    }
}

without optimisations, in case it gets optimised out.

Furthur evidence for realloc(p, 0) being equivalent to free(p):
This thread agrees with me: http://www.thescripts.com/forum/thread626315.html

But a call to realloc() with size set to zero is equivalent to free() ...

So does this IBM reference: http://publib.boulder.ibm.com/infoce...rf1/malloc.htm

If the Size parameter is 0 and the Pointer parameter is not null, the realloc subroutine is equivalent to a free subroutine of the same size.

(Not sure what that "of the same size" is all about.)
Even this man page agrees: http://linux.die.net/man/3/realloc

... if size is equal to zero, the call is equivalent to free(ptr).

I think we can safely say that realloc(p, 0) is equivalent to free(p).

malloc(0), on the other hand, is implementation-defined, as I noted and you discovered.

[robatino]

> malloc(0), on the other hand, is implementation-defined, as I noted and you discovered.

That's too bad. I used to think that malloc(len) was guaranteed to return non-NULL upon success and NULL on failure, whether len was zero or not. That would have made it possible to write code that doesn't have to treat len == 0 as a special case. I found the following thread:

what malloc(0) should returns?

I normally write C++ code, and hopefully the behavior there is to guarantee that an allocation for a container of length len doesn't throw an exception unless it actually fails, whether len is zero or not.

[dwks]

Wow, that's an incredible number of posts discussing such an apparently simple topic . . . .

In C++, when you use the non-array version of new, you have to specify a type, so unless you used new void (and void isn't a type) you're always specifying a size of at least 1. This means that you never run into the malloc(0) problem.

And when you allocate arrays with new[], you always get a pointer and never NULL. (Assuming you don't run out of memory or something.)

You can create an array with zero bounds with the new operator. For example:

char * c = new char[0];

In this case, a pointer to a unique object is returned.

From http://publib.boulder.ibm.com/infoce...c05cplr199.htm

Something else I discovered while searching: delete 0 is defined to do nothing.