|
From: Nicholas N. <nj...@cs...> - 2005-05-10 13:43:52
|
Hi,
It's possible for a client to trash the metadata associated with a heap
block, causing Valgrind to fail. For example,
#include <stdlib.h>
int main(void)
{
int i;
int* x = malloc(sizeof(int));
for (i = 0; i < 10; i++) {
x[i] = 0;
}
free(x);
x = malloc(sizeof(int));
return 0;
}
causes Memcheck to barf:
==26401== Invalid write of size 4
==26401== at 0x80483FD: main (a.c:8)
==26401== Address 0x1BA3C02C is 0 bytes after a block of size 4 alloc'd
==26401== at 0x1B8FB652: malloc (vg_replace_malloc.c:219)
==26401== by 0x80483E7: main (a.c:5)
valgrind: m_mallocfree.c:157 (mk_plain_bszB): Assertion `bszB != 0' failed.
==26401== at 0xB001E7C9: ???
==26401== by 0xB001E7C8: ???
==26401== by 0xB00127B3: ???
==26401== by 0xB000EB6B: ???
==26401== by 0xB115C2D3: ???
==26401== by 0xB0017242: ???
==26401== by 0xB0016ACA: ???
==26401== by 0xB005B167: ???
and the assertion failure doesn't explain well to the user what's
happened.
Admittedly, because of the redzones this requires a quite substantial heap
block overrun from the user, but it does happen every now and then.
I had a thought: what about storing the heap block metadata separate from
the heap blocks themselves? It seems like a not-bad idea for any
allocator in general, and in Valgrind we'd have the advantage that the
metadata would be in Valgrind's protected address space, untrashable by
the client.
The downside would be that you'd need an extra data structure like a hash
table to hold the metadata, and the insertions and lookups would slow down
allocation and deallocation a bit. But probably not much. You could have
a separate hash table for each arena. You'd want a pretty scalable data
structure to handle potentially many entries (eg. VgHashTable would not
suffice, maybe the skip-list would be ok).
Comments? Maybe I'm just inventing a solution for something that's not
really a problem in the first place.
N
|
|
From: Oswald B. <os...@kd...> - 2005-05-10 17:06:25
|
On Tue, May 10, 2005 at 08:43:49AM -0500, Nicholas Nethercote wrote: > I had a thought: what about storing the heap block metadata separate from > the heap blocks themselves? > i think freebsd (or some other *bsd) does/did this in the standard allocator. so it can't be _that_ a bad idea. ;) -- Hi! I'm a .signature virus! Copy me into your ~/.signature, please! -- Chaos, panic, and disorder - my work here is done. |
|
From: Nicholas N. <nj...@cs...> - 2005-05-10 19:05:33
|
On Tue, 10 May 2005, Oswald Buddenhagen wrote: >> I had a thought: what about storing the heap block metadata separate from >> the heap blocks themselves? > > i think freebsd (or some other *bsd) does/did this in the standard > allocator. so it can't be _that_ a bad idea. ;) I see. Do you know how the metadata is stored? Eg. in a hash table, or something cleverer like a bitmap? Thanks. N |
|
From: Oswald B. <os...@kd...> - 2005-05-10 21:03:11
|
On Tue, May 10, 2005 at 02:05:20PM -0500, Nicholas Nethercote wrote: > On Tue, 10 May 2005, Oswald Buddenhagen wrote: > >>I had a thought: what about storing the heap block metadata separate from > >>the heap blocks themselves? > > > >i think freebsd (or some other *bsd) does/did this in the standard > >allocator. so it can't be _that_ a bad idea. ;) > > I see. Do you know how the metadata is stored? Eg. in a hash table, or > something cleverer like a bitmap? > zero idea. i read it in a man page, now i think it was openbsd. but after a first look it seems like it's the same as freebsd anyway. http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/malloc.c -- Hi! I'm a .signature virus! Copy me into your ~/.signature, please! -- Chaos, panic, and disorder - my work here is done. |