w4d1: balloc() lower bounds

Allocation does what it's supposed to, according to the printout of the memory layout. Good!

Chunks and calculating memory usage

Writing a test case for how much RAM is available is not straight-forward.  Simply counting blocks of the  size used for the requested size does not work, e.g. balloc(5000) = 8192 nibble used, subtract from the total amount of memory available, and keep on until available memory < requested nibble size. For the following series (with 16M of starting RAM):

1. allocated 5316418 bytes to nibble 0xa25e0008 (k 11)
2. allocated 3142922 bytes to nibble 0xa2de0008 (k 10)
3. allocated 479360 bytes to nibble 0xa31e0008 (k 7)
4. allocated 1359988 bytes to nibble 0xa33e0008 (k 9)
5. allocated 55739 bytes to nibble 0xa3260008 (k 4)
6. allocated 232232 bytes to nibble 0xa32a0008 (k 6)
7. allocated 160914 bytes to nibble 0xa32e0008 (k 6)
8. allocated 23031 bytes to nibble 0xa3270008 (k 3)
9. allocated 284332 bytes to nibble 0xa3360008 (k 7)
10. allocated 208094 bytes to nibble 0xa3320008 (k 6)
11. allocated 121497 bytes to nibble 0xa3280008 (k 5)
12. allocated 4092 bytes to nibble 0xa3278008 (k 0)
13. allocated 11350 bytes to nibble 0xa327c008 (k 2)
14. allocated 2033 bytes to nibble 0xa3279008 (k 0)
15. allocated 6196 bytes to nibble 0xa327a008 (k 1)
16. allocated 431 bytes to nibble (nil) (k 0)

After #15, there is 2048 bytes left and a block of size k=0 is requested. However, as I write this, I realize that you must check for available memory >= minimum nibble size (4kb), or the allocation will, of course, fail. But, that is not enough.  There are situations in which there's enough memory available from just counting allocated blocks, but because how the blocks are fit into memory (greedily), there aren't any spare blocks of appropriate size available. Knapsack problem.  

There is a upper and higher bound on how much spill memory (i.e. internal fragmentation) you can have before you can't allocate another minimum nibble sized-block. My guess is that it's not only related to allocated memory vs. memory left, but also the distribution of the earlier block allocations.  However, as this is still the buddy allocator prototype, I'll test allocation until a semi-arbitrary threshold of block size*2-1. i.e. available memory + maximum spill in one chunk.

And in the end, it all turned out to be my boundary checking: bytes = up2(size); balloc(bytes); without checking for bytes < MIN_CHUNK_SIZE. Test now passes.

Visualizing

...as a flat image is tricky since earlier memory addresses are modified (= split) as smaller chunks are requested. The final memory layout can easily be dumped and drawn, but how useful will it be for performance evaluation?  It gives the layout at the end, but could miss interesting data in the middle.