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

Both things have their place. Use unit tests to check the interfaces behave as expected and assertions to check that the contract is respected.

Answer 2

If there is any logic in there, it can be unit-tested.
If your logic involves making decisions and calling OS/hardware/system APIs, fake/mock out the device dependent calls and unit test your logic to verify if the right decisions are made under a given set of pre-conditions. Follow the Arrange-Act-Assert triad in your unit test.
Assertions are no replacement for automated unit-tests. They dont tell you which scenario failed, they don't provide feedback during development, they can't be used to prove that all specs are being met by the code among other things.

Non-vague Update: I don't know the exact method calls.. I think I'll 'roll my own' Let's say your code examines current conditions, makes a decision and make calls to the OS as required. Lets say your OS calls are (you may have many more):

void* AllocateMemory(int size); 
bool FreeMemory(void* handle);
int MemoryAvailable();

First turn this into an interface, I_OS_MemoryFacade. Create an implementation of this interface to make the actual calls to the OS. Now make your code use this interface - you now have decoupled your code/logic from the device/OS. Next in your unit test, you use a mock framework (its purpose is to give you a mock implementation of a specified interface. You can then tell the mock framework that expect these calls to be made, with these params and return this when they are made. At the end of the test, you can ask the mock framework to verify if all the expectations were met. (e.g. In this test, AllocateMemory should be called thrice with 10, 30, 50 as params followed by 3 FreeMemory calls. Check if MemoryAvailable returns the initial value.)
Since your code depends on an interface, it doesn't know the difference between the real implementation and a fake/mock implementation that you use for testing. Google out 'mock frameworks' for more information on this.

Answer 3

Personally I find most of the unit tests like someone else's desire rather than mine. I think that any unit test should be written just like a normal program except the fact that it doesn't do anything other than testing a library/algorithm or any part of code.

My unit tests usually don't use tools like CUnit, CppUnit and similar software. I create my own tests. For example not long ago I needed to test a fresh implementation of a container in usual cases for memory leaks. A unit test was not helpful enough for providing a nice test. Instead I created my own allocator and made it fail to allocate memory after a certain (adjustable) number of allocations to see if my application has memory leaks in these case ( and it had :) ).

How can this be made by a unit test? With more effort to make your code fit into the unit test "pattern".

So I strongly recommend not using unit test every time just because it is "trendy", but only when it is really easy to integrate them with the code you like to test.

Answer 4

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.

Answer 5

You may also want to include performance testing, stress testing etc. They wouldn't be unit tests, because it would test entire thing, but they're very valuable in case of memory allocator.

Unit testing does not exclude these kinds of tests. It's best to have both of them.

Answer 6

I also think unit tests are overrated. They have their usefulness, but what really increases the quality of a program is to review it. On the other hand I'm really fond of assertions, but they don't replace unit testing.

I'm not talking about peer-review, but simply reread what you wrote, possibly while stepping through it with a debugger and checking that each line does what it's supposed to do will sky rocket software quality.

I'd recommend "high level" unit tests that test a chunk of functionality rather than a tiny method call. The later tend to make any code change extremely painful and expensive.

Answer 7

Unit testing isn't just to make sure your code works. It is also a very good design methodology. For tests to be useful, as mentioned previously, the code needs to be as decoupled as possible, such as using interfaces where needed.

I don't always write tests first, but very often if I am having trouble getting started on something, I will write a simple test, experiment with the design and go from there. Also, good unit tests serve as good documentation. At work when I need to see how to use a specific class or similar, I look at the unit tests for it.

Just remember that Unit Testing is not integration testing. Unit testing does have its limits but overall I think a very good tool to know how to use appropriately.