6 Feb
2023
6 Feb
'23
3:58 p.m.
On Mon Feb 6 15:54:47 2023 +0000, Jinoh Kang wrote:
This is correct but a little hard to verify. Multiple isolated atomic operations update the same variable `free_bits` in sequence, and they can be concurrently interleaved with accesses from other threads. Verifying their correctness requires knowledge of _partial_ ownership, that all set (1) bits in `free_bits` are owned by `find_free_bin_block` (i.e. cannot be transitioned by `InterlockedOr`) while all unset (0) bits in `free_bits` are owned by `heap_free_block_lfh` (i.e. can be transitioned by `InterlockedOr`). Instead, how about merging all four atomic operations into one like this?
/* look up and acquire a free block using the group free_bits */ static inline LONG group_find_free_block( struct group *group, SIZE_T block_size, struct block **block ) { ULONG i; LONG old_free_bits, new_free_bits, prev_free_bits; prev_free_bits = ReadNoFence( &group->free_bits ); do { old_free_bits = prev_free_bits; /* unset the least set bit */ new_free_bits = old_free_bits & (old_free_bits - 1); /* set GROUP_FLAG_FREE if and only if other bits are 0. */ new_free_bits &= ~GROUP_FLAG_FREE; if (new_free_bits == 0) new_free_bits = GROUP_FLAG_FREE; prev_free_bits = InterlockedCompareExchange( &group->free_bits, new_free_bits, old_free_bits ); } while (prev_free_bits != old_free_bits); if (BitScanForward( &i, old_free_bits & ~GROUP_FLAG_FREE )) *block = group_get_block( group, block_size, i ); else *block = NULL; /* heap corrupted */ return new_free_bits; }
(Note that this comment is no longer necessary if you're going to switch to my proposal above.)