Re: [PATCH v6 0/7] MR1628: ntdll: Implement Low Fragmentation Heap.

[Jinoh Kang (＠iamahuman)]

Jinoh Kang (@iamahuman) commented about dlls/ntdll/heap.c:
> +{
> - ULONG affinity = heap_current_thread_affinity();
> - struct block *block;
> - struct group *group;
> -
> - /* acquire a group, the thread will own it and no other thread can clear free bits.
> -
> * some other thread might still set the free bits if they are freeing blocks.
> -
> */
> - if (!(group = heap_acquire_bin_group( heap, flags, block_size, bin ))) return NULL;
> - group->affinity = affinity;
> -
> - /* serialize with heap_free_block_lfh: atomically set GROUP_FLAG_FREE when the free bits are all 0. */
> - if (group_find_free_block( group, block_size, &block ))
> -
>    InterlockedAnd( &group->free_bits, ~GROUP_FLAG_FREE );
> - else
> -
>    InterlockedCompareExchange( &group->free_bits, GROUP_FLAG_FREE, 0 );

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?

```c
/* 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;
}
```