Q:

How would you unittest a memory allocator?

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?

A:

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.

A:

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.

