mempool allocator is broken #11022
Description
There is a bug in mempool implementation. When memory is allocated allocator gets an available block and if it is large enough it splits these block into 4 smaller blocks. This is repeated until allocator reaches the smallest block that satisfies the request. When block_free is called situation is reversed and when 4 neighboring blocks are found to be free allocator concatenates them and returns to the pool as one larger block.
The problem is that to avoid the locking allocator allows a situation when big block or 4 smaller blocks are taken from the pool before the split or merge. Author seemed to know about this limitation and added -EAGAIN that would allow alloc to retry but:
- first, when there are no free blocks
-ENOMEMis returned: even though these blocks may be at the moment be reserved for concatenation_sys_mem_pool_block_allocwill not be able to see them, the same happens whenblock_freeis merging blocks, - second, this solution is non-stable: when free is performed by lower priority context and will be interrupted by high priority context just before
block_freeis about to be recursively called, memory will never be reported as free even if we switch to-EAGAINin the_sys_mem_pool_block_alloc.
To replicate the problem with higher probability create two context competing for allocation (threads or thread/interrupt) and add busy wait just before block_free is recursively called.
There is also question of performance impact. Note that at the moment code is merging smaller blocks in every call to free and break it again with every alloc. Note that in normal situation application will be allocating small blocks only to free them short time later. Wouldn't it be better to merge blocks only when application requests bigger chunk?
I also think that operation of split and merge should be done atomically with free/alloc. If merge is done only on big chunk request the impact may not be big and the code would be stable.