[k4st]

I semi-recently implemented a malloc tester (am TAing an OS course). Students write their own implementation of malloc and free, and then I "intercept" their calls to brk and sbrk by using macros to re-define those symbols as my own versions of those functions.

It is quite nice: I have knobs to "fuzz" the alignment of returned addresses from sbrk, as well as to inject arbitrary EAGAINs, to see if they're following the man pages. Another thing that I looked for was re-entrancy. This was a bit hand-wavy, but ultimately took the form of a try-lock in my sbrk implementation, where if the try-lock fails, their invocations of sbrk are not being synchronized.

Another thing I did to evaluate their implementations was to poison the entire unallocated and allocated sbrk space, poison all allocated memory blocks that my test runner allocates, and poison all freed memory blocks before my test runner frees memory. This all enabled me to estimate the meta-data overhead of their malloc implementation at a byte-granularity. That is, I can search the sbrk space for the various poisons, and then report on their relative frequency. If the sum of the frequencies is under 100%, then I claim the remaining percent as meta-data overhead.

The poisoning also also allowed me to detect simple bugs: if they write beyond the returned sbrk pointer, then I can potentially catch that because the values in memory don't match the expected poison.

Overall, it was fun to do and I could present some nice stats. For example, I produced a histogram of malloc call sizes and sbrk call sizes. This allowed one to quickly see if they're invoking sbrk unnecessarily often.

[aktau]

This sounds like a generally useful thing. It would wager that any non-toy malloc implementation has such a thing. Perhaps it's a good idea to open-source it so we all benefit from this spec-testing, fuzzing and histogramming?