How would you unittest a memory allocator?

Question

There's a lot of people today who sell unittesting as bread-and-butter of development. That might even work for strongly algorithmically-oriented routines. However, how would you unit-test, for example, a memory allocator (think malloc()/realloc()/free()). It's not hard to produce a working (but absolutely useless) memory allocator that satisfies the specified interface. But how to provide the proper context for unit-testing functionality that is absolutely desired, yet not part of the contract: coalescing free blocks, reusing free blocks on next allocations, returning excess free memory to the system, asserting that the allocation policy (e.g. first-fit) really is respected, etc.

My experience is that assertions, even if complex and time-consuming (e.g. traversing the whole free list to check invariants) are much less work and are more reliable than unit-testing, esp. when coding complex, time-dependent algorithms.

Any thoughts?

Answer 1

Highly testable code tends to be structured differently than other code.

You describe several tasks that you want an allocator to do:

• coalescing free blocks
• reusing free blocks on next allocations
• returning excess free memory to the system
• asserting that the allocation policy (e.g. first-fit) really is respected

While you might write your allocation code to be very coupled, as in doing several of those things inside one function body, you could also break each task out into code that is a testable chunk. This is almost an inversion of what you may be used to. I find that testable code tends to be very transparent and built from more small pieces.

Next, I would say is that within reason automated testing of any sort is better than no automated testing. I would definitely focus more on making sure your tests do something useful than worrying if you've properly used mocks, whether you've ensured it's properly isolated and whether it's a true unit test. Those are all admirable goals that will hopefully make 99% of tests better. On the other hand, please use common sense and your best engineering judgment to get the job done.

Without code samples I don't think I can be more specific.