For the scanning allocator another possibility is to use two magic values:
-1 = the row is freed and the link count is up to date
-2 = the row is freed but the link count hasn't been decremented.
This would potentially allow the release to be completely atomic operation free, and also remove the atomic operation from the allocate.
However the link count is currently used to determine:
- Is the heap free (for reclaiming the memory)
- Is the heap full (to avoid allocating from it)
- Is the heap reasonably full (to extend rather than scan).
Assuming an extra flag PotentialFree is set, how could the functions above be coded?
Note, each of these functions should only be called within a spin lock - which means that potentialFree cannot be cleared, and rows cannot be mapped from -2 to -1 by any other concurrent thread.
Is HeapFull (similar to hasAtLeastN below):
Need to carefully check through the code to see if there are any other uses of count that need adapting.
Also experiment with always extending before scanning with the old code - since something like that is likely to be required for this situation.