[scudo] Add ConditionVariable in SizeClassAllocator64

[Chia-hungDuan]

Summary

This may improve the waiting of Region->MMLock while trying to refill
the freelist. Instead of always waiting on the completion of
populateFreeListAndPopBatch() or releaseToOSMaybe(), pushBlocks()
also refills the freelist. This increases the chance of earlier return
from popBatches().

The support of condition variable hasn't been done for all platforms.
Therefore, add another popBatchWithCV() and it can be configured in
the allocator configuration by setting Primary::UseConditionVariable
and the desired ConditionVariableT.

[Chia-hungDuan]

Minor build fix

[Chia-hungDuan]

1. Fix potential ABA problem
2. Switch to detect the condition variable config so that the exisiting custom config doesn't need to add new parameters
3. Add condition variable test

[cferris]

Just a few comment nits.

compiler-rt/lib/scudo/standalone/primary64.h

158

from the wrong

258

to call

902

populating the freelist.

[cferris]

Looks good to me, but it's good to wait for Hans to take one last look.

[hboehm]

compiler-rt/lib/scudo/standalone/condition_variable.h

34–35

Is it possible to do something more like sched_yield here? Or there isn't a portable call along these lines. This clearly breaks completely if the waiting thread can't be preempted, e.g. because it has a higher real-time priority that the thread for which it's waiting, and there is a single hardware thread. I don't know if that matters here.

compiler-rt/lib/scudo/standalone/condition_variable_linux.cpp

26

It appears to me that all updates to Counter are lock-protected. So a non-atomic add with separate loads and stores should be fine. Since the only concurrent access is the futex read, I would expect this to have a release or relaxed store, and a relaxed load.

31

It seems to me that this makes the second notification in a row, without intervening waits cheap. But the third one will again perform a system call, even without an intervening wait. Intended? Do you want separate counters for notifications and waits?

[Chia-hungDuan]

Address review comments

compiler-rt/lib/scudo/standalone/condition_variable.h

34–35

So far we don't have a portable version here.

This implementation is supposed to be only used in the tests only. The busy-wait here is supposed to be something like sleep or yield hint. The reason we have the busy-wait is to simulate the same idea of waiting in usual condition variable implementation. It only waits for a short time and then wait on the mutex again.

Or do you think we can remove the busy-wait instead?

compiler-rt/lib/scudo/standalone/condition_variable_linux.cpp

31

Sorry I may miss something here. I think the notify and wait are put in a total order. LastNotifyAll will always record the last notify. We only call the system call to wake up waiters when the difference between the Counter and LastNotifyAll greater than 1, i.e., there are waiters.

Could you share more details about in what case we may have redundant notify calls?