The "paranoid malloc" we use in game debugging does all that
stuff and adds one more wrinkle: freed memory blocks are immediately
scrubbed with a fill pattern but those blocks are put on a free list
and not allowed to be recycled for any other allocation til they cool
off a bit (seconds to minutes, depending how much bloat you can
tolerate and how much RAM you have).
We have a watchdog that runs around all the freed blocks
periodically to make sure they are still scrubbed - if one isn't
scrubbed any more, it barks about it and dumps out the "who
allocated" and "who freed" call stacks, as well as showing which
offsets went sour. Conversely any faulty code that reads from freed
blocks usually fails spectacularly enough that it's easy to spot
(regs full of F1F1F1F1 etc). We call that "lazy free". The same
watchdog also scans the live block list to make sure no block-end has
been overrun etc.
Hashing call stacks / stack-crawls is very useful - we use 8 or
16 deep crawls. So the meta data we have to keep for each live block
is just a uint for the allocator-path and the freer-path, an index
into the stack-crawl hash table. That said we only invoke this tool
on machines with 2GB or more RAM handy.
You mentioned that this is for debugging games. Does that mean you get to do all this in user space? Half your luck ;o)