```C++ 不对称围栏详解```

原文

While browsing through Folly’s synchronization primitives to study up on concurrency concepts, one familiar-looking name in the codebase caught my attention: Asymmetric Thread Fence. I already knew what std::atomic_thread_fence is meant to achieve, but what does this construct do? And what exactly is asymmetric about it?

That question led me down an interesting rabbit hole: understanding the details of asymmetric thread fences and what they are actually doing underneath the hood (at least on Linux). We’ll start with the C++ proposal for this construct, then work our way down into the implementation details.

We’ll walk through the mechanics in a later section, but for now it suffices to understand what these fences are trying to achieve. Referring to the proposal, let’s look at the overview:

Some types of concurrent algorithms can be split into a common path and an uncommon path, both of which require fences (or other operations with non-relaxed memory orders) for correctness. On many platforms, it’s possible to speed up the common path by adding an even stronger fence type (stronger than memory_order_seq_cst) down the uncommon path. These facilities are being used in an increasing number of concurrency libraries. We propose standardizing these asymmetric fences, and incorporating them into the memory model.

Essentially, a concurrent algorithm may originally require a fence on both sides. However, if one path is significantly more common than the other, we may optimize for the common path by using a lighter fence there, while shifting the heavier synchronization cost onto the uncommon path. This can result in an overall performance improvement if we ensure the performance gain from the common path is much more than the overhead from the heavier fence of the uncommon path.

This pattern is more common than it may first appear. If you browse through Folly’s codebase, you can find several uses of it:

folly/synchronization/HazptrDomain.h: Hazard Pointers
folly/synchronization/detail/ThreadCachedReaders.h: RCU
folly/executors/ThreadPoolExecutor.cpp: Thread Pool ExWcutor

Let’s begin with a modified example from the paper, known as Dekker’s example:

atomic_int x{0}, y{0};
int r1, r2;

// Path A:
x.store(1, memory_order_relaxed);
atomic_thread_fence(memory_order_seq_cst);
r1 = y.load(memory_order_relaxed);

// Path B:
y.store(1, memory_order_relaxed);
atomic_thread_fence(memory_order_seq_cst);
r2 = x.load(memory_order_relaxed);

// Happens after both paths are completed.
assert(!(r1 == 0 && r2 == 0)); // Never fails.

We know the assertion cannot fail. Let’s examine why under the C++ memory model:

Constraint $(1) \rightarrow (2)$ and $(1) \rightarrow (5)$ arise from the synchronizes-with relationship between thread construction and the start of the thread function [thread.thread.constr]/6. This also establishes the modification order of both X and Y via the write-write coherence guarantees described in [intro.races]/15.
Constraint $(4) \rightarrow (5)$ and $(7) \rightarrow (2)$ are coherence-orderings that arise from the requirements in [atomics.order]/3.3. For example, $(4)$ and $(5)$ are not the same atomic read-modify-write operation, and $(4)$ reads the value stored by $(1)$, and $(1)$ precedes $(5)$ in the modification order of Y.
From [atomics.order]/4.4, memory_order::seq_cst fence $A$ happens-before $(4)$, and $(5)$ happens-before memory_order::seq_cst fence $B$, therefore $(3)$ must precede $(6)$ in the single total order $S$ on all memory_order::seq_cst operations. By symmetric reasoning, $(6)$ must also precede $(3)$ in the same total order $S$.

This is impossible, hence a contradiction. Therefore the execution where r1 == 0 && r2 == 0 is forbidden.

Now, returning to asymmetric thread fences. The key idea is that in some concurrent algorithms, we care about optimizing a common path at the expense of an uncommon path. If we are willing to let the slow path absorb stronger synchronization costs, we can restructure the code using asymmetric fences. The paper illustrates this with the following transformation:

// Globals:
atomic_int x{0}, y{0};
int r1, r2;

// Fast path:
x.store(1, memory_order_relaxed);
asymmetric_thread_fence_light(); // Like atomic_signal_fence;
// only inhibits compiler reordering
r1 = y.load(memory_order_relaxed);

// Slow path:
y.store(1, memory_order_relaxed);
asymmetric_thread_fence_heavy(); // Stronger than atomic_thread_fence(memory_order_seq_cst);
r2 = x.load(memory_order_relaxed);

// Happens after both fast path and slow path are complete.
assert(!(r1 == 0 && r2 == 0)); // Never fails.

That’s all we need to know about them for now. Let’s now move on to how these asymmetric fences are implemented.

Let’s start with the simpler primitive: asymmetric_thread_fence_light. In Folly’s implementation, this is implemented using asm volatile("" : : : "memory") on GCC/Clang or _ReadWriteBarrier() on MSVC, with std::atomic_thread_fence(order) used as a fallback. As a side note, asm declarations are only conditionally supported in C++ according to [dcl.asm]/1, so we will refer to GCC’s documentation, specifically the extended asm section for the exact semantics here.

asm asm-qualifiers ( AssemblerTemplate 
                 : OutputOperands 
                 [ : InputOperands
                 [ : Clobbers ] ])

Here, we only care about the clobber list, specifically the special "memory" clobber argument:

The "memory" clobber tells the compiler that the assembly code performs memory reads or writes to items other than those listed in the input and output operands (for example, accessing the memory pointed to by one of the input parameters). To ensure memory contains correct values, GCC may need to flush specific register values to memory before executing the asm. Further, the compiler does not assume that any values read from memory before an asm remain unchanged after that asm; it reloads them as needed. Using the "memory" clobber effectively forms a read/write memory barrier for the compiler.
Note that this clobber does not prevent the processor from doing speculative reads past the asm statement. To prevent that, you need processor-specific fence instructions.

This means that the compiler must preserve the ordering of memory reads and writes with respect to asm volatile("" : : : "memory"), effectively making it a compiler barrier. However, this places constraints only on instruction reordering performed by the compiler, not on the processor itself. The CPU may still execute memory operations out-of-order at runtime.

As an additional note, we can also examine what the volatile qualifier does here:

GCC’s optimizers sometimes discard asm statements if they determine there is no need for the output variables. Also, the optimizers may move code out of loops if they believe that the code will always return the same result (i.e. none of its input values change between calls). Using the volatile qualifier disables these optimizations. asm statements that have no output operands and asm goto statements, are implicitly volatile.

Here, volatile simply prevents unwanted compiler optimizations on the asm statement itself. Strictly speaking, it is not necessary in this case since an asm statement without output operands is already implicitly volatile.

The key synchronization mechanism behind asymmetric fences lies in asymmetric_thread_fence_heavy. There are several implementation strategies, but we will focus on the usual Linux path: relying on the membarrier() syscall (Another alternative is to force a TLB shootdown, though I am not familiar enough with that approach to discuss it in detail). As before, std::atomic_thread_fence(order) is used as a fallback.

Let’s take a look at the documentation:

The membarrier() system call helps reducing the overhead of the memory barrier instructions required to order memory accesses on multi-core systems. However, this system call is heavier than a memory barrier, so using it effectively is not as simple as replacing memory barriers with this system call, but requires understanding of the details below.
Use of memory barriers needs to be done taking into account that a memory barrier always needs to be either matched with its memory barrier counterparts, or that the architecture’s memory model doesn’t require the matching barriers.
There are cases where one side of the matching barriers (which we will refer to as “fast side”) is executed much more often than the other (which we will refer to as “slow side”). This is a prime target for the use of membarrier(). The key idea is to replace, for these matching barriers, the fast-side memory barriers by simple compiler barriers, for example: asm volatile ("" : : : "memory") and replace the slow-side memory barriers by calls to membarrier().
This will add overhead to the slow side, and remove overhead from the fast side, thus resulting in an overall performance increase as long as the slow side is infrequent enough that the overhead of the membarrier() calls does not outweigh the performance gain on the fast side.

This is exactly the asymmetric tradeoff we discussed earlier, that is replacing the fast path’s hardware fence with a compiler barrier, while shifting the heavier synchronization cost onto the infrequent slow path. The syscall signature for membarrier() is:

int syscall(SYS_membarrier, int cmd, unsigned int flags, int cpu_id);

For this post, we will focus primarily on the 2 specific cmd arguments used by Folly: MEMBARRIER_CMD_PRIVATE_EXPEDITED and MEMBARRIER_CMD_REGISTER_PRIVATE_EXPEDITED. Let’s have a quick look on the documentation for that:

MEMBARRIER_CMD_REGISTER_PRIVATE_EXPEDITED (since Linux 4.14) Register the process’s intent to use MEMBARRIER_CMD_PRIVATE_EXPEDITED.

This command simply registers the process’s intent to later use membarrier() with MEMBARRIER_CMD_PRIVATE_EXPEDITED.

MEMBARRIER_CMD_PRIVATE_EXPEDITED (since Linux 4.14)
Execute a memory barrier on each running thread belonging to the same process as the calling thread.
Upon return from the system call, the calling thread has a guarantee that all its running thread siblings have passed through a state where all memory accesses to user-space addresses match program order between entry to and return from the system call (non-running threads are de facto in such a state). This guarantee is provided only for threads in the same process as the calling thread.
The “expedited” commands complete faster than the non-expedited ones; they never block, but have the downside of causing extra overhead.
A process must register its intent to use the private expedited command prior to using it. We choose MEMBARRIER_CMD_PRIVATE_EXPEDITED instead of MEMBARRIER_CMD_GLOBAL or MEMBARRIER_CMD_GLOBAL_EXPEDITED because we only require the barrier to affect threads within a single process.

The documentation also gives us the guarantee for each targeted thread, there exists some time $T$ during the interval between the invocation and return of membarrier() at which its memory accesses to user-space addresses are consistent with the program order in the emitted assembly. That is, for each targeted thread, there exists some point $T$ during that interval where no memory accesses $A$ and $B$ can exist such that $A$ is program-ordered before $B$, yet the effects of $B$ are observable before those of $A$.

Additionally, to ensure this works as intended, membarrier() enforces an ordering guarantee on the targeted threads, stated as follows:

All memory accesses performed in program order from each targeted thread are guaranteed to be ordered with respect to membarrier().

In short, a thread’s program-order memory accesses are ordered with respect to membarrier(), thereby separating operations that occur before the barrier from those that occur after it. Within a thread, writes (and reads) deemed to have happened before the membarrier() must be globally visible (and satisfied) before writes (and reads) that are deemed to happen after the membarrier(). If you remember from my previous blog, this is basically what sync/hwsync does for PowerPC, as we will see shortly.

The Linux manual page summarizes the pairwise ordering relationships between these primitives with the following table (O: ordered, X: not ordered):

	barrier()	smp_mb()	membarrier()
barrier()	X	X	O
smp_mb()	X	O	O
membarrier()	O	O	O

I’m no Linux kernel expert, and this is actually my first time poking around in Linux source code. Because of that, we won’t be doing an exhaustive deep dive, but we will look at how it is implemented under the hood and why it works. To keep things manageable, we will focus specifically on the expedited private membarrier() call used by Facebook’s Folly library, which fundamentally boils down to call_membarrier(MEMBARRIER_CMD_PRIVATE_EXPEDITED):

FOLLY_ERASE int call_membarrier(int cmd, unsigned int flags = 0) {
  if (linux_syscall_nr_membarrier < 0) {
    errno = ENOSYS;
    return -1;
  }
  return linux_syscall(linux_syscall_nr_membarrier, cmd, flags);
}

If we trace this down into the Linux kernel source and strip away the comments and conditional branches that don’t apply to our specific arguments, we are left with the following skeleton:

static void ipi_mb(void *info)
{
	smp_mb();	/* IPIs should be serializing but paranoid. */
}

static int membarrier_private_expedited(int flags, int cpu_id)
{
	cpumask_var_t tmpmask;
	struct mm_struct *mm = current->mm;
	smp_call_func_t ipi_func = ipi_mb;

	{ // Removed other if cases
		WARN_ON_ONCE(flags);
		if (!(atomic_read(&mm->membarrier_state) &
				MEMBARRIER_STATE_PRIVATE_EXPEDITED_READY))
			return -EPERM;
	}

	if (flags != MEMBARRIER_FLAG_SYNC_CORE &&
	    (atomic_read(&mm->mm_users) == 1 || num_online_cpus() == 1))
		return 0;

	smp_mb(); // (1)

	if (cpu_id < 0 && !zalloc_cpumask_var(&tmpmask, GFP_KERNEL))
		return -ENOMEM;

	SERIALIZE_IPI();
	cpus_read_lock();

	{
		int cpu;

		rcu_read_lock();

		for_each_online_cpu(cpu) {
			struct task_struct *p;

			p = rcu_dereference(cpu_rq(cpu)->curr);
			if (p && p->mm == mm)
				__cpumask_set_cpu(cpu, tmpmask);
		}

		rcu_read_unlock(); 
	}

	{
		if (flags != MEMBARRIER_FLAG_SYNC_CORE) {
			preempt_disable();
			smp_call_function_many(tmpmask, ipi_func, NULL, true); // (2)
			preempt_enable();
		}
	}

	if (cpu_id < 0)
		free_cpumask_var(tmpmask);
	cpus_read_unlock();

	smp_mb(); // (3)
	return 0;
}

The core execution flow of the implementation involves $(1) \rightarrow (2) \rightarrow (3)$, that simply involves smp_mb() $\rightarrow$ send inter-processor interrupts(IPI) to call smp_mb() on other cores $\rightarrow$ wait for the execution of smp_mb() on the targeted cores to complete $\rightarrow$ smp_mb(). There are 2 helpful documentation regarding this: the top-level comments in kernel/sched/membarrier.c and Documentation/scheduler/membarrier.rst. We’ll explore the main cases to see how this actually works.

Case 1: Userspace Thread Execution after Membarrier-Induced IPI

// Globals:
atomic_int x{0}, y{0}, z{0};
int r1, r2, r3;

// T0
x.store(1, memory_order_relaxed);
asymmetric_thread_fence_light();
r1 = y.load(memory_order_relaxed);

// T1
y.store(1, memory_order_relaxed);
asymmetric_thread_fence_heavy();
r2 = z.load(memory_order_relaxed);

// T2
z.store(1, memory_order_relaxed);
asymmetric_thread_fence_light();
r3 = x.load(memory_order_relaxed);

assert(!(r1 == 0 && r2 == 0 && r3 == 0));

// Globals
int data{0};
atomic_int x{0};
atomic_bool P0_won_the_race{false};

// P0
data = 0x123456;
fence0();
if (x.load(std::memory_order_relaxed) == 0) {
    P0_won_the_race.store(true, std::memory_order_relaxed);
}

// P1
x.store(1, std::memory_order_relaxed);
fence1();
if (P0_won_the_race.load(std::memory_order_relaxed)) {
    assert(data == 0x123456);
}

C membarrier_pre_switch_race

{}

P0(int *data, int *x, int *P0_won_the_race, int *rq_state)
{
    // Plain write to data payload
    *data = 1;               // TEST: race condition case
    // WRITE_ONCE(*data, 1); // TEST: No race condition case

    // ====================================================
    // fence0(): sys_membarrier() path on CPU0
    // ====================================================
    smp_mb();                        // (1) entry barrier
    int r_rq = READ_ONCE(*rq_state); // (2) read rq->curr->mm == NULL
    smp_mb();                        // (3) exit barrier
    // ====================================================

    // if (x.load(relaxed) == 0)
    int r0 = READ_ONCE(*x);
    if (r0 == 0) {
        WRITE_ONCE(*P0_won_the_race, 1);
    }
}

P1(int *data, int *x, int *P0_won_the_race, int *rq_state)
{
    // ====================================================
    // Context switch happens at the VERY BEGINNING of P1
    // ====================================================
    smp_mb();                        // rq_lock(); smp_mb__after_spinlock() in __schedule()
    WRITE_ONCE(*rq_state, 1);        // (4) switch to kthread (simulate setting rq->curr->mm = NULL)
    smp_mb();                        // inherent barrier in context_switch()
    
    smp_mb();                        // rq_lock(); smp_mb__after_spinlock() in __schedule()
    WRITE_ONCE(*rq_state, 2);        // (5) switch back to user thread (simulate setting rq->curr->mm != NULL)
    smp_mb();                        // inherent barrier in context_switch()
    // ====================================================

    // x.store(1, relaxed);
    WRITE_ONCE(*x, 1);

    // fence1(): Pure Compiler Barrier
    barrier(); 

    // if (P0_won_the_race.load(relaxed))
    int r1 = READ_ONCE(*P0_won_the_race);
    if (r1 == 1) {
        int r2 = *data;               // TEST: race condition case
        // int r2 = READ_ONCE(*data); // TEST: No race condition case
    }
}

// Can P1 confirm P0 won the race (r1 == 1) but see stale data (r2 == 0)?
// If r_rq is not 1, it will send out IPIs
filter (0:r_rq = 1) 
exists (1:r1 = 1 /\ 1:r2 = 0)

Test membarrier_pre_switch_race Allowed
States 3
1:r1=0; 1:r2=0;
1:r1=1; 1:r2=0;
1:r1=1; 1:r2=1;
Ok
Witnesses
Positive: 1 Negative: 3
Flag data-race
Condition exists (1:r1=1 /\ 1:r2=0)
Observation membarrier_pre_switch_race Sometimes 1 3
Time membarrier_pre_switch_race 0.01
Hash=2b7111a8ad77523d6b4f25c0844e6ec7

```C++ 不对称围栏详解``` C++ Details of Asymmetric Fences

Case 1: Userspace Thread Execution after Membarrier-Induced IPI

Case 2: Userspace Thread Execution before Membarrier-Induced IPI

Case 3: Context Switching - Scheduling Userspace Thread $\rightarrow$ Kthread $\rightarrow$ Userspace Thread

The Memory Ordering Gurantees of IPIs

Fast Path for membarrier()

Quick Note on smp_mb()

Other Minor Implementation Details

The Straightforward Idea

Preventing Transitivity

The Current Wording

```C++ 不对称围栏详解```
C++ Details of Asymmetric Fences