code 7. introduce mfence to prevent CPU reordering

The above code has introduce a full memory fence, which is relative heavy operation, of code 6,

4.2.2.2 Locked instruction

Locked instructions will lock the bus and synchronize all the caches of CPU,

Intel 64 and IA-32 processors provide a LOCK# signal that is asserted automatically during certain critical memory operations to lock the system bus or equivalent link. While this output signal is asserted, requests from other processors or bus agents for control of the bus are blocked.

which is usually a read-modify-write(RMW) does, the common case is a compare-and-swap operation

// cpp code                            | ; asm code
std::atomic<int> ai = { 0 };           |
                                       |
void cas() {                           | cas():
  int a;                               |    xor     eax, eax
  ai.compare_exchange_weak(a, 10086,   |    mov     edx, 10086
      std::memory_order_relaxed);      |    lock cmpxchg  DWORD PTR ai[rip], edx
}                                      |    ret

§8.1 “LOCKED ATOMIC OPERATIONS” of Intel’s developer manual volume 3 has described how does the locked instruction work and how the atomic operations are guaranteed.

5 Acquire and Release semantics

先总结什么是Acquire and Release semantics:

• acquire semantics, 硬件层面就是保证在此之后的所有指令在执行的时候都不能重排到这 个指令之前, 软件层面在此之后的所有操作都不能重排到这个语义(fence)之前
• release semantics, 硬件层面就是保证在此之前的所有store都已经”release”可见, 软件层面在此之前的所有操作都不能重排到这个语义(fence)之后

这个概念是对各个核对内存的变更在其他核的可见性, 这个也是和CPU cache 的复杂实现是息息相关的, 因为各个厂商实现不一样, 但是这些内存的可见顺序的 行为是可以通过这个抽象出来的概念来描述的. 这个概念不仅仅是对CPU reordering的约束也是对compiler reordering的约束.

Acquire semantics is a property that can only apply to operations that read from shared memory, whether they are read-modify-write operations or plain loads. The operation is then considered a read-acquire. Acquire semantics prevent memory reordering of the read-acquire with any read or write operation that follows it in program order.

acquire和release是配对的, 硬件层面, 这个语义(也许是一条CPU instruction)在执行 这个”指令”之后的所有内存的load操作都看到的 其他核”最新”的变更(depends on memory model of the CPU), 也就是说在这个”指令”之后 的所有对的指令都不能reorder 到这个”指令”之前. 同样的, 在ARM上这个”指令”是dmb, 在PowerPC上是lwsync, 在x86-64上不需要单独的指令.

软件层面, 如果我们所编写代码包含了这个语义, 编译器在翻译成汇编的时候要在优化的时 候考虑程序字面的要求意思, 确保

prevent memory reordering of the read-acquire with any read or write operation that follows it in program order.

能够满足.

Release semantics is a property that can only apply to operations that write to shared memory, whether they are read-modify-write operations or plain stores. The operation is then considered a write-release. Release semantics prevent memory reordering of the write-release with any read or write operation that precedes it in program order.

release samentic和字面意思很像. 硬件层面, 这个语义(也许是一条CPU instruction)在执行这个 “指令”之后, 发生在这个”指令”之前(happens-before)的所有内存的store/load操作在所有 核都可见, 更直观的解释就是在这个”指令”, 之后的所有指令不能reorder到这个”指令” 之前. 在ARM上这个”指令”是dmb, 在PowerPC上是lwsync, 在x86-64的CPU上不需要 单独 的一个”指令”完成这个事情, 因为x86-64的strong hardware memory model类型的处 理器. 软件层面, 如果我们所编写代码包含了这个语义, 编译器在翻译成汇编的时候要在优化的时 候考虑程序字面的要求意思, 确保

prevent memory reordering of the write-release with any read or write operation that precedes it in program order

能够满足.

memory order有软件层面的也有硬件层面的order, 对应的就是compile-time reordering和runtime reordering.

这也稍微从更抽象的层面解释了为什么用C++11标准使用说明里说 std::memory_order_relase和std::memory_order_acquire要配对使用了, 如果不配对 使用, 其实只限制了其中一部分reordering的行为, 另外一部分reordering的行为未限制, 不会达到期望的reordering效果.

关于acquire and release semantics, 还可以参考这个文章 以及这个视频”Herb Sutter - atomic Weapons 1 of 2” 获取更多地对于这个概念的讲解和讨论.

5.1 Sequential Consistency

讲完Acquire and Release semantics, 就需要详细讲一下”Sequential Consistency” (顺序一致)这个概念, 这个概念是Lamport大神在1979年提出的, 一般在分布式系统里用的比较多, 但是一个multi-core CPU+内存何尝不是一个非常典型的multiprocessing system呢?

Leslie Lamport, 1979, who defined that a multiprocessing system had sequential consistency if:

“…the results of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.”

This definition was one of the first statements on what constituted “correct” behavior for a symmetric multiprocessing (SMP) system. It has been restated in various forms, among them the following:

Sequential consistency requires that a shared memory multiprocessor appear to be a multiprogramming uniprocessor system to any program running on it.

Sequential consistency requires that:

1. All instructions are executed in order, result in a single total order
2. Every write operation becomes instantaneously visible throughout the system

如figure 6中所示(纵向是时间). 考虑有两个线程, 线程1需要执行AB, 线程2需要执行CD, 如果ABCD每个操作都是原子的, 在并行系统中, 如果这个系统是保持sequential consistency的, 那么最终的执行顺序是类似左边中的一种, 但是绝对不会是类似于最右边 的那种, 并且对于每个线程, 最终看到的执行顺序也只有一种–各个线程(核)达成一致.

figure 6. shows that what is sequential consistency and what is not

考虑如下程序执行顺序

std::atomic_bool x, y;
std::atomic_int z;

void write_x() {
  x.store(true, std::memory_order_seq_cst); //2
}

void write_y() {
  y.store(true, std::memory_order_seq_cst); //3
}

void read_x_then_y() {
  while (!x.load(std::memory_order_seq_cst));
  if (y.load(std::memory_order_seq_cst)) //4
    ++z;
}

void read_y_then_x() {
  while (!y.load(std::memory_order_seq_cst));
  if (x.load(std::memory_order_seq_cst)) //5
    ++z;
}

int main() {
  x = false;
  y = false;
  z = 0;
  std::thread a(write_x);
  std::thread b(write_y);
  std::thread c(read_x_then_y);
  std::thread d(read_y_then_x);
  a.join(); b.join(); c.join(); d.join();
  assert(z.load() != 0); //1, z must be 1 or 2
}

code 8. demo of sequential consistency in C++

在多线程情况下, 只要不产生data race的(data race means undefined behavior), 我们都能为多线程程序找到一个total order, 不管在总体时序上每个指令在各个线程是如何交织(interleaving)的, code 8 中, 对于所有的变量(例子中的都是原子变量), 都使用了std::memory_order_seq_cst, 意思就是说对于说有相关的变量(包括上下文出现的变量)在编译优化时不能破坏 sequential consistency, 同时在生成的CPU指令里加入一些额外的同步指令使其在运行时也到保证. 所以无论程序以何种方式运行, code 8最后一行assert都会成立, 并且各个 线程只看到同一个程序执行顺序的total order.

如果assert失败了(z==0), c, d两个线程执行结果都是0 线程c执行结果是0, 那么就意味着它看到”store to x happens before store to y”, 线程d执行结果是0, 那么就意味着它看到”store to y happens before store to x”, 从全局来看是两个完全相反的执行顺序, 就是说”store to x”和”store to y”的执行效果的 在各个核的可见性是不统一的, 这是一种data race的表现.

但是如果把上述的memory order换成relaxed 或者 load acquire + store release, 最后的assert 就不一定会成立了(虽然很难复现).

操作原子变量时, relaxed确保的是 对内存的操作都是原子可见, 核内不进行reorder限制, 同时核之间的同步性能损耗最少, 可能只需要在RMW时, 部分lock一下总线即可, 不是相同地址的操作还是可 以往总线上读写, 这个同步的过程对总线利用比较高.

acquire或者release 语义在保证原子性的同时还限制本核内的reorder行为, 但并不会进行多核同步(同relaxed), 多核之间可见性的行为限制不了, 所以使用这两个语义也达不到顺序一致的效果.

seq_cst除了保证relaxed的原子性以及本核内的reorder行为(acqure+release), 同时还确保本核对其他核同步时, 使用时总线达到一个”独占”的效果, 显然, 这个同步的过程时间相对比较长.

load acquire 和 store release 只能保证一个核的序不能保证全局序, relaxed, acquire 以及 release 只能保证原子性, 以及本核上对应语义的序, 但是不能保 证其他核看到本核同步结果的顺序. 而seq_cst在同步结果时向其他核进行同步, 确定了一 个全局序.

下图解释了 thread c 和 thread d 两个线程可能看到的 x y的顺序不一样, a 完成x=1之后向其他核同步结果, 同时 b 完成y=1也向其他核同步结果, 但是这个同步的 过程并不确保所有的核在”同一时间”内都看到了自己写的值. c 先看到了 a 的结果, 然后看到了b的结果, 所以认为 x 先写了. d 先看到了 b 的结果, 然后看到了a的结果, 所以认为 y 先写了.

c和d对于序的理解冲突了, 要理解这个原因, 我们简化模型, 考虑a在写x=1时, b也在同时写 y=1, 而片上总线是同一个, 这就和我们并发操作同个数据类似, core3 先看到 x=1 后看到 y=1 core4 先看到 y=1 后看到 x=1

thread a         thread b          thread c         thread d
+-----+          +-----+           +-----+          +-----+
|core1|          |core2|           |core3|          |core4|
|     |          |     |           |     |          |     |
+-----+          +-----+           +-----+          +-----+
  x=1              y=1              x==1?            y==1?
   |                |               ^ ^              ^ ^
   |                |               | |              | |
   \________________|_______________/ |              | |
    \               |                 |              | |
     \              \_________________|______________/ |
      \              \                |                |
       \______________\_______________|________________/
                       \              |
                        \_____________/

如果加上了全局序的限制(seq_cst), 一个可能的序如下, 各个核都会先看到x=1, 然后才看到y=1, 各个核都会认同这个序.

thread a         thread b          thread c         thread d
+-----+          +-----+           +-----+          +-----+
|core1|          |core2|           |core3|          |core4|
|     |          |     |           |     |          |     |
+-----+          +-----+           +-----+          +-----+
  x=1              y=1              x==1?            y==1?
   |                |               ^ ^              ^ ^
   |                |               | |              | |
   \________________|_______________|_|______________/ |
                    |                 |                |
                    |                 |                |
                    \_________________|________________/

(这个例子几乎对所有支持SC memory model的语言都成立, 比如rust)

sequential consistency在有些时候, 可能会有性能瓶颈, 因为它需要确保操作在所有线程 之前全局同步, 一些操作需要进行排队吞吐就降低了.

C++ 11默认的memory model就是sequential consistency, 后文会进行详细描述.

为了加深印象, 我们再来看Herb举的两个描述SC更加直观简单例子, 不管执行顺序如何, 全局所有线程看 到一个相同的顺序(total order).

Transitivity/causality: x and y are std::atomic, all variables initially zero.

Thread 1        Thread 2                 Thread 3
g = 1;          if(x == 1) y = 1;        if(y == 1) assert(g == 1);
x = 1;

It must be impossible for the assertion to fail – wouldn’t be SC.

Total store order: x and y are std::atomic and initially zero.

Thread 1      Thread 2      Thread 3                 Thread 4
x = 1;        y = 1;        if (x==1 && y==0)        if (y==1 && x==0)
                              print("x first");        print("y first");

It must be impossible to print both messages – wouldn’t be SC.

5.2 Out of thin air

如果编译器对我们编译出来的代码进行了一些(指令重排的)优化, 这些优化并不影响其在单 线程执行的结果, 但是如果编译器不遵循一定的memory model, 那么很有可能会编译出在多 线程环境下运行是带有bug 的汇编代码.

比如说如下例子, out-of-thin-air, compiled with x86-64 gcc 4.1.2 -O3.

// cpp                     | ;asm code
int v = 0;                 |
                           |
void foo(int set_v) {      | foo(int):
  if (set_v) {             |   mov     %eax, 10086
    v = 10086;             |   test    %edi, %edi               ;test condition
  }                        |   cmove   %eax, DWORD PTR v(%rip)  ;load maybe
}                          |   mov     DWORD PTR v(%rip), %eax  ;store always
                           |   ret

code 7. out of thin air

可以看到, 编译器在优化编译的时候, 为了节省跳转指令, 用了一个trick, 这个trick 会导致左边源代码的if条件里边每次都会走到, 也就是说即使条件没有满足, 每次v都 会被赋值, 这个在单线程里执行是没有问题的, 但是如果在多线程环境下, v被别的线程引 用了, 并且变更了这个值, 事情就变得复杂了, 比如说另外一个线程2执行如下语句

v = 10010;

线程2对v的变更可能永远未可见

note: gcc 4.4.7之后就已经修复了这个问题

Sequentially Consistent概念跟Acquire and Release semantics是息息相关的, 我们知道, 程序的编译以及指令的执行在单线程内如果都遵循指令重排的基本原则 Acquire and Release semantics可以控制单线程内部的顺序, 通过配对使用, 可以使 线程间构成synchronizes-with

5.3 Full Fence

A full fence is a bidirectional restriction fence which has both acquire and relese semantics.

Nothing goes up and nothing goes down.

Sequential consistency is usually implemented with full fence.

6 Control instruction reordering

编译器和CPU在背地里做了一些”勾当”, 目的都是优化, 如果我们不知道他们做了什么, 很 可能会写出有bug的代码, 类似这个例子所示, 所以在多线程的系统/环境中, 我们需要了解并且掌控程序的reordering.

6.1 Low-level reordering constraints

在code 4中我们在c++代码中插入了一条汇编语句

    asm volatile("" ::: "memory");

这一句其实没有产生任何汇编指令, 而是告诉编译器, 不要将这一句周围(上下)的指令进行 重排, 就是编译期的限制, 是一个编译期的release + acquire semantics.

如前文所述, code 4例子中还是能在runtime捕获到捕获到指令重排, 如果要阻止这种行为, 我们需要

    asm volatile("mfence" ::: "memory");

mfence是一条Intel汇编指令, 在Fence Instruction章节中我们 介绍了几种现代Intel CPU的memory fence指令, 简单再来再提一下

• sfence, store fence, 在instruction stream中, 所有在sfence之前的store指令都不能 重排到sfence之后, 但是不影响sfence之前的load指令重排到sfence之后
• lfence, load fence, 在instruction stream中, 所有在lfence之前的load指令不能重排 到lfence之后, 但是不影响lfence之前的store令重排到lfence之后
• mfence, “full fence”, 在instruction stream中, 所有在mfence之前的store/load指令 都不能重排到mfence之后

汇编是一个非常底层的语言, 也是能精确控制每一步的ordering, 如下代码中, 我们可以用 一个mfence来解决重排的问题, 也可以根据实际情况使用sfence or lfence

// cpp                                  | ;asm
                                        |
extern int a, b;                        |  bar():
                                        |      mov     eax, DWORD PTR b[rip]
void bar() {                            |      mov     DWORD PTR a[rip], eax
  a = b;                                |      mfence
  asm volatile("mfence" ::: "memory");  |      mov     DWORD PTR b[rip], 1
  b = 1;                                |      ret
}                                       |
                                        |

code 9. constrains reordering with low-level fence instruction

6.2 Lock, Mutex

Locks/Mutexes are a system level mechanism that ensures there is only one thread run at a time, which “perfectly” prevent concurrency and data races.

If we run the program with a single thread, due to the rule of reordering. There won’t be any undefined behaviors introduce by reordering because there is only one thread can stay in critical section protected by the lock.

// cpp                        | ;asm
std::mutex mtx;               | bar():
void bar() {                  |   push    rbx
  {                           |   mov     ebx, OFFSET FLAT:_ZL28__gthrw___pth...
    lock_guard<mutex> l(mtx); |   test    rbx, rbx
    a = b;                    |   je      .L9
  }                           |   mov     edi, OFFSET FLAT:mtx
  b = 1;                      |   call    __gthrw_pthread_mutex_lock(pthread_mutex_t*)
}                             |   test    eax, eax
                              |   jne     .L21
                              | .L9:
                              |   mov     eax, DWORD PTR b[rip]
                              |   mov     DWORD PTR a[rip], eax ;;;assign a;;;;
                              |   test    rbx, rbx
                              |   je      .L10
                              |   mov     edi, OFFSET FLAT:mtx
                              |   call    __gthrw_pthread_mutex_unlock(pthread_mutex_t*)
                              | .L10:
                              |   mov     DWORD PTR b[rip], 1   ;;;assign b;;;;
                              |   pop     rbx
                              |   ret
                              | .L21:
                              |   mov     edi, eax
                              |   call    std::__throw_system_error(int)

code 10. prevent reordering with lock, compiled with x86-64 gcc 8.2 -O3

BTW, a lock carries the acquire and release semantics, usually both of them, the underlying implementation of locks/mutexes usually introduces low-level full memory fences, and also work as a full fence at runtime – nothing can pass the lock.

Briefly speaking, lock – acquire semantics, unlock – release semantics.

  std::unique_lock<std::mutex> lock(mtx);

  lock.lock();  // nothing following in the critical section reordered
                // above this lock(), acquire semantics

  // critical section
  ...

  lock.unlock(); // nothing prior in the critical section reordered
                 // past this unlock(), release semantics

6.3 Memory Fences

Memory Fence和Memory Barrier其实是同个意思, 中文翻译应该都叫内存屏障 (叫内存栅栏好像有点不那么顺口:smirk:), 只是英文叫法不一样, 看多了Linux内核的人可能更加习惯叫barrier, 但是我更习惯叫Memory Fence, 因为相关的 汇编指令就叫fence.

在之前的code 4和code 2b, 我们已经展示了从编程语言层面 如何通过添加语句asm volatile("" ::: "memory")(汇编, 关于gcc asm使用的说明在 这里) 或者std::atomice_thread_fence(C++11)来限制编译期(乃至运行期)的reordering.

语言层面对于memory fence这个概念的抽象和支持, 将会在接下来的章节 详细阐述, 一个好的抽象可以非常好地实现memory fence并且在各种场景下得到很好的优化 .

7 Synchronizes-with relation

The following concepts are used to describe sequence of each operation in multi-thread environment, we just need to know that:

• synchronizes-with inter thread, release and acquire semantics description
• sequenced-before intra thread order description
• happens-before inter thread order description

Michael Wong’s slides shows the idea of sequenced-before + memory-ordering to implement happens-before and synchronizes-with.

8 Memory Model of C++11

What is software memory model:

• A set of rules that describe allowable semantics for memory accesses on a computer program
  • Defines the expected value or values returned by any loads in the program
  • Determines when a program produces undefined behavior (e.g load from uninitialized variables)
• Stroustrup, The C++ Programming Language 4th Edition §41.2 represents a contract between the implementers and the programmers to ensure that most programmers do not have to think about the details of modern computer hardware
• Critical component of concurrent programming

The default memory model is sequentially consistent, and the memory order is a very important, may be the most important, part of C++ memory model.

8.1 Memory Order of C++11

The C++ standard says that (namespace std is omitted here):

• memory_order_relaxed: allow reordering, no explicit fence

  Relaxed operation: there are no synchronization or ordering constraints imposed on other reads or writes, only this operation’s atomicity is guaranteed.

• memory_order_consume: keep data dependency only, reordering may still happen, weaker than acquire and can be replaced entirely with acquire. It’s discouraged to use consume.

  A load operation with this memory order performs a consume operation on the affected memory location: no reads or writes in the current thread dependent on the value currently loaded can be reordered before this load. Writes to data-dependent variables in other threads that release the same atomic variable are visible in the current thread. On most platforms, this affects compiler optimizations only.

• memory_order_acquire: any memory access cannot be reordered upwards this point, any associated atomic variables can be accessed correctly

  A load operation with this memory order performs the acquire operation on the affected memory location: no reads or writes in the current thread can be reordered before this load. All writes in other threads that release the same atomic variable are visible in the current thread.

• memory_order_release: any memory access cannot be reordered downwards this point, all memory precedes this point is visible to other threads

  A store operation with this memory order performs the release operation: no reads or writes in the current thread can be reordered after this store. All writes in the current thread are visible in other threads that acquire the same atomic variable (see Release-Acquire ordering below) and writes that carry a dependency into the atomic variable become visible in other threads that consume the same atomic.

• memory_order_acq_rel: acquire + release, works for RMW operation such as fetch_add

  A read-modify-write(RMW) operation with this memory order is both an acquire operation and a release operation. No memory reads or writes in the current thread can be reordered before or after this store. All writes in other threads that release the same atomic variable are visible before the modification and the modification is visible in other threads that acquire the same atomic variable.

• memory_order_seq_cst: load acquire + store release + single total order

  A load operation with this memory order performs an acquire operation, a store performs a release operation, and read-modify-write performs both an acquire operation and a release operation, plus a single total order exists in which all threads observe all modifications in the same order.

The definition of each memory ordering is very clear, they intend to fulfill the C++ memory model, and they can be applied to the function families as following, see <atomic> for more info.

std::atomic<T>::load()
std::atomic<T>::store()
std::atomic<T>::compare_and_exchange_*()
std::atomic<T>::exchange()
std::atomic_thread_fence() // standalone fence
std::atomic_load()
std::atomic_store()
std::atomic_compare_and_exchange()
std::atomic_exchange()

(from here on in this section, namespace std may be omitted in code snippet)

We can conclude the strength of constraints of the memory ordering as follows:

                  /----------> release ----------\
                 /                                \
     relaxed --->                                  ---> acq_res ---> seq_cst
                 \                                /
                  \---> consume ---> acquire ----/

an arrow A -> B means constraint of B is stronger than A

And we should note that, by definition in the c++ standard of acquire and release semantics, memory_order_consume and memory_order_acquire will not make sense for atomic load operations; memory_order_release will not make sense for atomic store operations.

atomic<int> A;

A.store(10086, memory_order_acquire); // does not make sense, may be undefined behavior
A.store(10086, memory_order_consume); // does not make sense, may be undefined behavior
A.load(10086, memory_order_release); // does not make sense, may be undefined behavior

A.store(10086, memory_order_relaxed); // store-relaxed operation
A.store(10086, memory_order_release); // store-release operation
A.store(10086, memory_order_acq_rel); // store-release operation
A.store(10086, memory_order_seq_cst); // SC store-release operation

A.load(10086, memory_order_relaxed); // load-relaxed operation
A.load(10086, memory_order_consume); // load-consume operation
A.load(10086, memory_order_acquire); // load-acquire operation
A.load(10086, memory_order_acq_rel); // load-acquire operation
A.load(10086, memory_order_seq_cst); // SC load-acquire operation

A.fetch_add(10086, memory_order_relaxed); // store-relaxed operation
A.fetch_add(10086, memory_order_release); // store-release operation
A.fetch_add(10086, memory_order_acq_rel); // load-acquire + store-release operation
A.fetch_add(10086, memory_order_seq_cst); // SC load-acquire + store-release operation

memory_order_consume may be a little confusing, this memory order looses the load-acquire constraint by considering the data dependency, to explain it in detail I illustrate a code snippet here.

extern int X;
void foo() {
  atomic<int> A {10086};
  int B = 10010;
  int C = 10000;

  X = A.load(memory_order_consume); // a "consume fence"

  B = B + 1; // may/can be reordered before x
  C = A.load(memory_order_relaxed) + 1; // can not be reordered before X
                                        // because it depends on A
}

Note that every consume can be replaced with acquire, but not vice versa, the data dependency is some time hard to figure out, and don’t be clever when you don’t fully understand the consequences by replacing acquire with consume if you think it “may” improve the performance.

consume in most cases is a compiler option, the code gen is almost the same as acquire, consume is a compiler optimization option only.

8.2 Standalone fence, stronger but slower

Standalone fence is described in section 29.8 of working draft.

Fences can have acquire semantics, release semantics, or both. A fence with acquire semantics is called an acquire fence. A fence with release semantics is called a release fence.

A fence can be generated with std::atomic_thread_fence() and corresponding std::memory_order.

A fence with acquire semantics is called an acquire fence, std::atomic_thread_fence(std::memory_order_acquire). A fence with release semantics is called a release fence, std::atomic_thread_fence(std::memory_order_release).

Let’s analyse a code snippet:

extern int tmp;

tmp = 10086;
A.store(10010, std::memory_order_release);

is it equivalent to the following?

extern int tmp;

tmp = 10086;
std::atomic_thread_fence(std::memory_order_release); // release fence
// can be reorded? float up?
A.store(10010, std::memory_order_relaxed);

There may be a mis-concept that store to A with memory_order_relaxed can be reordered upwards that standalone release fence, due to mis-understanding of release operation

Release semantics is a property that can only apply to operations that write to shared memory, whether they are read-modify-write operations or plain stores. The operation is then considered a write-release. Release semantics prevent memory reordering of the write-release with any read or write operation that precedes it in program order.

Release semantics constrains nothing will be reordered after the write-release, but cannot prevent some other operations from floating past the write-release, and even past that store tmp = 10086 before release fence, if standalone release fence performs in the same way, it won’t make any sense that we still need a standalone fence.

Fortunately, C++ standard disallows that reordering before release fence, its the same for the acquire fence too.

N3337 29.8.2 says:

A release fence A synchronizes with an acquire fence B if there exist atomic operations X and Y, both operating on some atomic object M, such that A is sequenced before X, X modifies M, Y is sequenced before B, and Y reads the value written by X or a value written by any side effect in the hypothetical release sequence X would head if it were a release operation.

It may be a little hard to understand, to explain this, I draw this figure:

                               sync      Y          M.load
A   ===^===^===^===^===^===   ------>    B   ===v===v===v===v===v===
X          M.store

The constraints/consequences are:

1. A synchronizes with B
2. X cannot float past A — X cannot be reordered. X is allowed to be reordered before A if it is pure release semantics
3. Y cannot sink past B — Y cannot be reordered. Y is allowed to be reordered past B if it is pure acquire semantics

In other words by cppreference:

atomic_thread_fence imposes stronger synchronization constraints than an atomic store operation with the same std::memory_order. While an atomic store-release operation prevents all preceding writes from moving past the store-release, an atomic_thread_fence with memory_order_release ordering prevents all preceding writes from moving past all subsequent stores.

Standalone atomic_thread_fence with memory_order_release or memory_order_acquire is stricter than store-release or load-acquire operation.

This post by Jeff Preshing discusses the example given previously in details.

And what we need to notice is that standalone fences are sub-optimal and it is a performance pessimization.

8.3 compare_exchange_weak or compare_exchange_strong?

Sometimes it maybe confusing that which one to use for CAS, compare_exchange_weak or compare_exchange_strong, for cpp users, as always we should analyse the difference and than choose which on to use.

Here is my conclusion on this question:

• compare_exchange_weak may fail with spurious error, even if the expected value matched due to some reasons (system level or hardware level)
• compare_exchange_weak is “cheaper” than compare_exchange_strong, as if the strong one keeps trying in a loop to exchange when “spurious error” occurs with the weak one
• conventionally, which to use:
  • if there is a CAS loop (spin), use compare_exchange_weak

      while (compare_exchange_weak(:::)) { ::: }
    

  • if there is a single test, use compare_exchange_strong

      if (compare_exchange_strong(:::)) { ::: }
    

compare_exchange_strong/weak is conditional read-write-modify operation, also called compare-and-swap (CAS).

Naive CAS implementation on hardware may look like this (pseudo code):

bool compare_exchange_strong(T& old_v, T new_v) {
 Lock L;        // Get exclusive access
 T tmp = value; // Current value of the atomic
 if (tmp != old_v) { old_v = tmp; return false; }
 value = new_v;
 return true;
}

// Lock is not a real mutex but some form of exclusive access implemented in hardware

Notice that read is faster than write, we can read first and than lock, the implementation can be faster:

bool compare_exchange_strong(T& old_v, T new_v) {
 T tmp = value;                                   // Current value of the atomic
 if (tmp != old_v) { old_v = tmp; return false; }
 Lock L;                                          // Get exclusive access
 tmp = value;                                     // value could have changed!
 if (tmp != olv_v) { old_v = tmp; return false; }
 value = new_v;
 return true;
}

// Double-checked locking pattern is back!

If exclusive access is hard(expensive) to get, use weak lock other than strong lock, let someone else try:

bool compare_exchange_weak(T& old_v, T new_v) {
 T tmp = value;                                   // Current value of the atomic
 if (tmp != old_v) { old_v = tmp; return false; }
 TimedLock L;                                     // Get exclusive access or fail
 if (!L.locked()) return false;                   // old_v is correct
 tmp = value;                                     // value could have changed!
 if (tmp != olv_v) { old_v = tmp; return false; }
 value = new_v;
 return true;
}

We can see why there is spurious error for compare_exchange_weak by explaining with pseudo code: CPU reads the value and passes the check but it fails to “lock” the “bus”, the call of compare_exchange_weak returns false.

From the pseudo code implementations, compare_exchange_weak and compare_exchange_strong seems to be the same expensive, why do we say that compare_exchange_weak is cheaper/faster? When TimedLock fails, there is another core succeeds, if TimedLock is much easier or more light-weight than Lock to make progress, the overall performance will be better with compare_exchange_weak.

compare_exchange_weak and compare_exchange_strong act the same on x86-64, however, on SPARC or ARM, they are not the same. Performance varies from platform to platform.

9 volatile

volatile in C++ is only a compile-time keyword which prevents the compiler reordering the specified (such as redundant read), that a hint only, but no atomicity at runtime guaranteed.

A typical case

extern int a;
volatile int b = a; // load a
// do somthing that not related to a
...
b = a; // load a again, this redundant statement won't be reordered or optimized

volatile in Java or C#, it kind of means atomic, the write or read to the specified var is “atomic”, no partial write or read will happen.

And also, note that

• in .NET and Java key word volatile ensures sequentially consistent memory order, kind of like atomic with default memory order in C++
• C++ std::atomic default memory order is sequential-consistency we can weaken that, but I didn’t find out how to do that with volatile in .NET or Java.

10 Code generation

This section introduces the code generation that implements C++ memory model on different types of processors.

They are compiled with gcc 8.2, 8.2, 6.3, 5.4 with option -std=c++17 -O3. The versions of gcc varies because they are the newest gcc version for corresponding processors on .

int a = 1;
int b = 2;
std::atomic<int> a1 {3};
extern int c;

void foo() {
  a = 1;
  b = 2;
  a1.compare_exchange_strong(a, 10086, std::memory_order_relaxed);
  a = c;
}

code. code snippet for code generation

table. code generation part 1

the fetch_add/fetch_sub will generate add or xadd on x86-64 according to the use of reuturn value, if not used simple lock add is enough.

table. code generation part 2

* means there is a loop

x86-64’s code generation is much simpler compared to the rest due to it’s strong hardware memory model, but there is no free lunch, the lock instruction locks the whole bus, it’s very expensive.

With stronger constraints, comes less flexibility for optimization.

There is no free lunch for ARM, POWER and MIPS too. Although they are weaker than x86-64 and more flexible, however, it’s easier to write buggy code while doing optimization.

11 Lock-free programming

Definition, examples of lock-free programming, and usage of atomics and memory ordering for lock-free.

Lock-free programming is doing trick with CAS at most of time, we need to consider all of the corner cases under concurrent situations.

In my point of view, it’s the key factor to ensure your lock-free program is correct iff what you operate is what you want to operate, even if it keeps changing all the time

11.1 Definition - what is lock-free

The Lock-Free property guarantees that at least some thread is doing progress on its work. In theory this means that a method may take an infinite amount of operations to complete, but in practice it takes a short amount, otherwise it won’t be much useful.

Definition: A method is Lock-Free if it guarantees that infinitely often some thread calling this method finishes in a finite number of steps.

The Wait-Free property guarantees that any given thread provided with a time-slice will be able to make some progress and eventually complete. It guarantees that the number of steps is finite, but in practice it may be extremely large and depend on the number of active threads, which is why there aren’t many practical Wait-Free data structures.

Definition: A method is Wait-Free if it guarantees that every call finishes its execution in a finite number of steps.

The above is quoted from this article, which is explained very well.

To understand it in a simple way, I put strengths of lock-freedom and properties as following:

• Not lock-free
  • explicit lock/mutex
• Lock-free, “someone makes progress”
  • no explicit lock/mutex
  • every step taken achieves global progress (for some sensible definition of progress)
  • guarantee system-wide throughput
• Wait-free, “no one ever waits”
  • every operation will complete in a bounded #steps no matter what else is going on
  • guarantee system-wide throughput and starvation-freedom
  • all wait-free algorithms are lock-free, but not vice versa

When we say that a particular data structure is Lock-Free it means that all its operations are Lock-Free, or better.

We should analyse the program to see what kind of “lock-free” it is, program without explicit locks is lock-free but performance varies among different implementations.

11.1.1 Lock-freedom examples

This is a piece of code that is lock-free but not wait-free.

size_t sleep_micro_sec = 5;
std::atomic<bool> locked_flag_ = ATOMIC_VAR_INIT(false);

void foo() {
  bool exp = false;
  while (!locked_flag_.compare_exchange_strong(exp, true)) {
    exp = false;
    if (sleep_micro_sec == 0) {
      std::this_thread::yield();
    } else if (sleep_micro_sec != 0) {
      std::this_thread::sleep_for(std::chrono::microseconds(sleep_micro_sec));
    }
  }
}

This is a piece of code that is (usually) wait-free with low(not that high) contention. We said it is “usually” because it may spin for long with high contention.

template<typename T>
void slist<T>::push_front(const T& t) {
  auto p = new Node;
  p->t = t;
  p->next = head;
  // spin until success
  // try to prepend to head when we see the head
  while (!head.compare_exchange_weak(p->next, p)) { }
}

11.2 Double-checked lock pattern, DCLP

GOF’s singleton pattern, lazy evaluation

Singleton* Singleton::instance = nullptr;

Singleton* Singleton::get_instance() {
  if (instance == nullptr) {
    lock_guard<mutex> lock(mtx);
    if (instance == nullptr) {
      instance = new Singleton(); // reordering or visibility of instance issue
    }
  }
  return instance;
}

This may not work, due to other threads may see partially constructed instance, if Singleton() is inlined explicitly or optimized by compiler.

The writes that initialize the Singleton object and the write to the instance field can be done or perceived out of order.

Even if the compiler does not reorder those writes, on a multiprocessor the processor or the memory system may reorder those writes, as perceived by a thread running on another processor.

To rescue that, use atomic for variable instance:

atomic<Singleton*> Singleton::instance {nullptr};

It’s sequential consistency by default, all write in Singleton() will and must be done before assigning to instance, no reordering to the assignment.

There are also other approach, like Scott Mayer’s, easy and simple

Singleton* Singleton::get_instance() {
  static Singleton a;
  return &a;
}

Here’s another variant, a lock free approach with an extra flag.

atomic<Singleton*> Singleton::instance {nullptr};
atomic<bool> Singleton::create {false};

Singleton* Singleton::get_instance() {
  if (instance.load() == nullptr) {
    if (!create.exchange(true)) // try to construct
      instance = new Singleton(); // construct
    else while(instance.load() == nullptr) { } // spin
  }
  return instance.load();
}

the above code use default memory order – sequential consistency, too strong for this snippet.

atomic<Singleton*> Singleton::instance {nullptr};
atomic<bool> Singleton::create {false};

Singleton* Singleton::get_instance() {
  if (instance.load(memory_order_acquire) == nullptr) {
    if (!create.exchange(true, memory_order_acq_rel)) // strong enough?
      instance.store(new Singleton(), memory_order_release); // construct
    else while(instance.load(memory_order_acquire) == nullptr) { } // spin
  }
  return instance.load(memory_order_acquire);
}

11.2.1 Lazy evaluation

The right way for lazy evaluation, using std::call_once

Singleton* Singleton::get_instance() {
  static std::once_flag create;
  std::call_once(create, [] { instance = new Singleton(); });
  return instance;
}

11.3 Lock-free queue

“Brute-force” lock-free singly-linked list, no pop.

Fixed size vector with atomic cursor and semaphore, one-to-many producer-consumer pattern.

11.3.1 Lock-free singly-linked list

template <typename T>
class slist {
public:
  slist();
  ~slist();
  void push_front(const T& t);
  void pop_front();
private:
  struct Node {
    T t;
    Node* next;
  }
  atomic<Node*> head {nulllptr};
};

Constructor doesn’t need to do anything, but destructor need to recycle internal nodes.

Destructor

template<typename T>
slist<T>::~slist() {
  auto first = head.load();
  while (first != nullptr) {
    auto unliked = first;
    first = first-next;
    delete unliked;
  }
}

push_front() is easy with atomic weapons, to deal with concurrent insertions, we just need to prepend to the head we see exactly with CAS.

template<typename T>
void slist<T>::push_front(const T& t) {
  auto p = new Node;
  p->t = t;
  p->next = head;
  // spin until success
  // try to prepend to head when we see the head
  while (!head.compare_exchange_weak(p->next, p)) { }
}

pop_front() is that easy too?

template<typename T>
void slist<T>::pop_front() {
  auto p = head.load(); // load once
  // spin until success
  // move head pointer "backwards" if we see the head
  while (p != nullptr
         && !head.compare_exchange_weak(p, p->next)) { }
  // problem:
  // ABA and dereferrencing deleted p by p->next in other threads after deletion
  delete p;
}

It seems that works fine, but there are problems:

1. ABA problem
2. Deference deleted pointer

case for ABA problem:

Initial state:
  +------+    +-------+    +-------+    +-------+    +-------+
  | head o--->| addr5 o--->| addr4 o--->| addr3 o--->| addr2 o--->
  +------+    +-------+    +-------+    +-------+    +-------+

Modify the list:

   |     Thread 1                Thread 2                   Thread3
   |     // pop                  // pop                     // push
   t
   i     head = 5
   m t1 -------------------------------------------------------------
   e                             head = 5
   |                             CAS(5, 4)
   | t2 -------------------------------------------------------------
   |                                                        head = 4
   l                                                        CAS(4, 9)
   i                                                        head = 9
   n                                                        CAS(9, 5)
   e t2 -------------------------------------------------------------
   |     CAS(5, 4)
   | t4 -------------------------------------------------------------
   v

t4:
  +------+    +=======+    +=======+    +-------+    +-------+    +-------+
  | head o    | addr5'o--->| addr9 o--->| addr4 o--->| addr3 o--->| addr2 o--->
  +---o--+    +=======+    +=======+    +-------+    +-------+    +-------+
       \                                    ^
        \__________________________________/

case for dereferencing deleted pointer problem (thread 2 dereference a mangling pointer deleted by thread 1):

// for convinence of explaination, pop_front() also can be written as
template<typename T>
void slist<T>::pop_front() {
  auto p = head.load();
  do {
    p = head.load();
    auto n = p->next; // dereference p, which is mean to be head
  } while (p != nullptr && !head.compare_exchange_weak(p, n));
  delete p;
}

// think of 2 concurrent pops, vertical direction shows in which time elapses

//  thread 1                               |  thread 2
                                           |
void slist<T>::pop_front() {               | void slist<T>::pop_front() {
  auto p = head.load();                    |   auto p = head.load();
  do {                                     |   do {
    p = head.load();                       |
    auto n = p->next;                      |     p = head.load();
  } while (p != nullptr                    |
    && !head.compare_exchange_weak(p, n)); |
  delete p;                                |
}                                          |      auto n = p->next; // BANG!
                                           |    } while (p != nullptr
                                           |      && !head.compare_exchange_weak(p, n));
                                           |    delete p;
                                           v  }

There are some (common and may be more) hints to solve the ABA problem:

We need to solve the ABA issue: Two nodes with the same address, but different identities (existing at different times).

1. Option 1: Use lazy garbage collection.
   • Solves the problem. Memory can’t be reused while pointers to it exist.
   • But: Not an option (yet) in portable C++ code, and destruction of nodes becomes nondeterministic.
2. Option 2: Use reference counting (garbage collection).
   • Solves the problem in cases without cycles. Again, avoids memory reuse.
3. Option 3: Make each pointer unique by appending a serial number, and increment the serial number each time it’s set.
   • This way we can always distinguish between A and A’.
   • But: Requires an atomic compare-and-swap on a value that’s larger than the size of a pointer. Not available on all hardware & bit-nesses.
4. Option 4: Use hazard pointers.
   • Maged Michael and Andrei Alexandrescu have covered this in detail.
   • But: It’s very intricate. Tread with caution.
5. …

It’s getting complicated and hard, and of course, if we don’t recycle memory there won’t be any ABA problem at all! :smirk: Think about it and don’t recycle anything if you push a lot and pop is much less, it will work well.

There is an attempt for option 1, 2 and 4 https://stidio.github.io/2017/01/cpp11_atomic_and_lockfree_program/, it may be a bit more complicated, I will discus it in future post (lock-free application series?), if I had time and found that this topic is still interesting.

For option 3, here is an attempt, apparently this attempt has hardware limitation. The idea is using a separate head structure with version.

template <typename T>
class slist {
...
  struct Node {
    T t;
    Node* next;
  }
  struct HeadNode { // 128 bit
    size_t ver = 0;
    Node* ptr = nullptr;
  }
  // this may be an issue
  atomic<HeadNode> head {0, nulllptr};
};

template<typename T>
void slist<T>::push_front(const T& t) {
  auto p = new Node;
  auto h = head.load();
  do {
    p->next = h.ptr;
    p->t = t;
    HeadNode new_head {h.ver + 1, p}; // increase ver
  } while (!head.compare_exchange_weak(h, new_head));
}

template<typename T>
void slist<T>::pop_front(T** t) {
  auto h = head.load();
  do {
    HeadNode new_head {h.ver + 1, h.ptr->next}; // increase ver
  } while (!head.compare_exchange_weak(h, new_head));
  *t = h.ptr; // delay reclamation of h.ptr
}

It resolves some of problems mentioned before:

• every time the head has been updated, version of head increased, ABA problem resolved
• no immediately reclamation of data when pop, leave the reclamation problem to user (it’s ugly…)

However, it’s not perfect, it may not work as lock-free on all hardwares due to the “big” structure NodeHead, some hardware may not have large enough register, here may be 128 bits, to complete CAS within one instruction. To check if it works, the simplest way may be using std::atomic_is_lock_free() to determine it.

The following show that atomicity is hardware dependent. (__atomic_load)

gcc8.2 -std=c++17 -O3

// cpp                                | ; asm
struct alignas(16) BigStruct16 {      | test_big_struct_lock_free1():
  size_t ver;                         |        sub     rsp, 24
  int64_t data;                       |        mov     esi, 5
};                                    |        mov     rdi, rsp
                                      |        call    __atomic_load_16
struct alignas(64) BigStruct64 {      |        add     rsp, 24
  size_t ver;                         |        ret
  int64_t data;                       |
};                                    | test_big_struct_lock_free2():
                                      |         push    rbp
void test_big_struct_lock_free1() {   |         mov     ecx, 5
  std::atomic<BigStruct64> a64;       |         mov     edi, 32
  auto c = a64.load();                |         mov     rbp, rsp
}                                     |         and     rsp, -32
                                      |         sub     rsp, 64
void test_big_struct_lock_free2() {   |         lea     rdx, [rsp+32]
  std::atomic<BigStruct64> a64;       |         mov     rsi, rsp
  auto c = a64.load();                |         call    __atomic_load
}                                     |         leave
                                      |         ret
// on most of modern Intel's x86-64 processors there are 128-bit registers
// BigStruct16 is lock free

11.3.1.1 Conclusion

To make this list pop single element is not that easy, to get rid of ABA, we may also first pop all the elements at once?

template<typename T>
auto slist<T>::pop_all() {
  return head.exchange(nullptr);
}

Nice, we are finally done.

(Wait, we didn’t talk about which memory order to be apply to atomic operations yet?)

11.4 shared_ptr ref_count

Bug mentioned by Herb in his talk atomic weapons.

It is very interesting and helpful for us to understand memory order much better.

Fist, we give the correct (fixed) code for shared ptr’s reference counting.

Increment

control_block_ptr = other->control_block_ptr;
control_block_ptr->refs.fetch_add(1, memory_order_relaxed);

Decrement

if (!control_block_ptr->refs
      .fetch_sub(1, memory_order_acq_rel)) { // key
  delete control_block_ptr;
}

Increment can be relaxed (not a publish operation, no one depends on this increment). Decrement can be acq_rel (both acq+rel necessary, probably sufficient).

Let’s analyse the wrong one that fetch_sub uses pure memory_order_release.

VS2012’s bug with ARM architecture, x86-64 is much stronger it’s OK with it.

if (!control_block_ptr->refs
      .fetch_sub(1, memory_order_release)) { // buggy
  delete control_block_ptr;
}

e.g, wrong memory order, pure release, consider 2 threads need to decrement

// Thread 1, 2->1                      |    // Thread 2, 1->0
// A: use of object                    |    :::
if (!control_block_ptr->refs           |    if (!control_block_ptr->refs
      .fetch_sub(                      |          .fetch_sub(
        1, memory_order_release)) {    |            1, memory_order_release)) {
  // branch not taken                  |       delete control_block_ptr; // B
}                                      |    }

The explanation given by Herb Sutter

• No acquire/release => no coherent communication guarantee that thread 2 sees thread 1’s writes in the right order. To thread 2, line A could appear to move below thread 1’s decrement even though it’s a release(!).
• Release doesn’t keep line B below decrement in thread 2.

The second reason is obvious, because it’s a release-operation, it’s free to reorder that delete floating up.

It’s hard to understand the first one for the first time, to there are 2 questions:

1. how can decrementing from 2 to 1 goes before line A
2. how can line A come after line B

To figure it out, we need to some transformations that compiler and CPU will do with the pure release semantics.

Transformation 1, break thread 1 into pieces (the load and store is for demonstration, they actually may be a single instruction on some hardwares)

// Thread 1, 2->1


// A: use of object

load ref_cnt
decrement ref_cnt 2->1
store ref_cnt
"release fence"
if (ref_cnt == 0) { // ref_cnt in register
  // branch not taken
}

Transformation 2, reordering happens to decrementing of ref_cnt

// Thread 1, 2->1

load ref_cnt
decrement ref_cnt 2->1 // reordered
store ref_cnt

// A: use of object

"release fence"
if (ref_cnt == 0) { // ref_cnt in register
  // branch not taken
}

Transformation 3, break thread 2 into pieces

// Thread 2, 1->0
:::
load ref_cnt
decrement ref_cnt 1->0
store ref_cnt
"release fence"
if (ref_cnt == 0) { // ref_cnt in register
  delete control_block_ptr; // B
}

Transformation 4, reordering happens to that delete

// Thread 2, 1->0
:::
load ref_cnt
decrement ref_cnt 1->0
store ref_cnt
if (ref_cnt == 0) { // ref_cnt in register
  delete control_block_ptr; // B
}
"release fence"

Transformation 2 and 4 are both legal forms according to the standard:

N3337 29.3.2

An atomic operation A that performs a release operation on an atomic object M synchronizes with an atomic operation B that performs an acquire operation on M and takes its value from any side effect in the release sequence headed by A.

in other words, by cppreference:

All writes in the current thread are visible in other threads that acquire the same atomic variable, and writes that carry a dependency into the atomic variable become visible in other threads that consume the same atomic

Contrast transformation 2 with 4, vertical direction is the execution order.

// Thread 1, 2->1                     |         // Thread 2, 1->0
load ref_cnt                          |         :::
decrement ref_cnt 2->1                |
store ref_cnt                         |
                                      |         load ref_cnt
                                      |         decrement ref_cnt 1->0
                                      |         store ref_cnt
                                      |         if (ref_cnt == 0) { // reg
                                      |           delete control_block_ptr; // B
// A: use of object                   |         }
"release fence"                       |         "release fence"
if (ref_cnt == 0) { // reg            |
  // branch not taken                 |
}                                     |

figure , release doesn’t keep synchronizes-with relation

Thread 1’s use of object comes after thread 2’s delete of that object, bang! This is the situation Herb describes, when 2 threads try to decrement, there actually is a data dependency, one must “wait” for, synchronizes-with another, if using release only, there is no such a synchronize with semantics.

With synchronizes-with, there won’t be any transforms like figure given above with fetch_sub(memory_order_acq_rel).

With semantics of “acquire + release”, “A: use of object” cannot move down into or past the “critical section”, and “delete control_block_ptr” cannot move up into or past “critical section”, problem solved.

// Thread 1, 2->1                     |        // Thread 2, 1->0
// A: use of object //cannot move down|
"acquire & release fence"             |
load ref_cnt                          |
decrement ref_cnt 2->1                |        :::
store ref_cnt               synchronizes-with
"acquire & release fence"  ----------------->  "acquire & release fence"
                                      |        load ref_cnt
                                      |        decrement ref_cnt 1->0
                                      |        store ref_cnt
                                      |        "acquire & release fence"
if (ref_cnt == 0) {                   |        if (ref_cnt == 0) { // can not move up
  // branch not taken                 |          delete control_block_ptr; // B
}                                     |        }

Note: Putting the term “release fence” and “acquire fence” in double quote is to distinguish with the standalone fence in C++11.

11.5 rwlock of glibc

From version 2.28 on, rwlock in glibc is implemented with lock-free technique, which may be faster than shared lock provided by C++ standard lib (since c++14), although there are still some low level locks required.

This is a very difficult lock-free algorithm, if you understand all the purposes of the atomic operations, you may be good to say that you understand lock-free programming well.:smirk:

glibc 2.28 release https://www.sourceware.org/ml/libc-alpha/2018-08/msg00003.html

nptl/pthread_rwlock_common.c contains most of the implementation.

12 Recap and conclusion

This post first introduces the hardware architecture cache and cache line, which may introduce OoO, and then discusses about runtime and compile-time reordering introduced by optimization, and later on, we discusses about how to control the reordering. Hence, we introduce the hardware and software memory model. After Introduction of MM, we talk lots of c++ memory ordering, and MM of C++11. And finally we bring up the lock-free programming which is the real application of MM.

Hardware, compiler and C++ are complicated and powerful, we may not know all the stuffs they’ve done for us, but we need to know the principle, that’s what this post tries todo.

Modern C++, especially C++11, abstracts the memory model very well, the concepts and potability of <atomic> are very good, helps C++ users a lot, it’s very hard to do that, but C++ standard committee actually did, many thanks to them!

We talked lock-free programing at last, and found it’s a very tough task to do general tasks with lock-free technique, we have to do a lot trade-offs and be very very very careful when we are doing lock-free programming.

Finally,

With Great Power Comes Lots Of Fun!

13 Useful resources

13.1 Static materials

an-introduction-to-lock-free-programming
memory-ordering-at-compile-time
memory-barriers-are-like-source-control-operations
acquire-and-release-semantics
acquire-and-release-fences
weak-vs-strong-memory-models
the-synchronizes-with-relation
double-checked-locking-is-fixed-in-cpp11
acquire-and-release-fences-dont-work-the-way-youd-expect
the-purpose-of-memory_order_consume-in-cpp11
can-reordering-of-release-acquire-operations-introduce-deadlock

Jeff Preshing’s posts of “lock-free programing” series, if you are new to lock-free programming or software/hardware memory ordering, read them in the given order, I can ensure that it may enlighten you greatly.

And you are welcomed to discuss with me about any

Intel Software Developer Manuals Combined Volumes: 3a, 3b, 3c and 3d - System programming guide

Volume 3 §8.1 and §8.2 are the same important reference, they show the Intel x86-64 family processors’ reordering detailed specification, which is worth reading.

GCC’s reordering of read/write instructions

what is the benefit of instruction at compile time and runtime

CPU cache
CPU cache coherence
intel coherence protocol
hyper threading
intel-introduction-to-x64-assembly

The above materials are about hardware level that related to memory order.

double-checked locking is broken for java

This post shows and analyses the broken DLCP for java in compile-time, the constructor is inlined by javac.

However, I do not see any thing wrong with gcc, the generated assembly code is just fine, the memory order is correct… Maybe explicit or compiler optimization inline is needed, that a complicated case.

c++ working drat

Here is the C++ Standard Draft Sources, check it for the latest C++ working draft.

C++ working draft N3337

This is the latest publication of C++11 working draft.

Single Threaded Memory Model - an example of out of thin air Optimization of conditional access to globals: thread-unsafe?

This mailing list about the conditional access to memory, which covers the discussion about out-of-thin-air, and it may affect sequentially consistency when compiler optimize this kind of conditional access.

The C++ Programming Language 4th Edition by Bjarne Stroustrup

Chapter 41 talks about concurrency, memory model and atomic, which is really helpful for understanding these concepts.

The purpose/definition of memory model is defined in §41.1.

obstruction-freedom

Lock-Free and Wait-Free, definition and examples

An article puts definitions of blocking, lock-free, wait-free and obstruciton-free all together.

Blocking 1. Blocking 2. Starvation-Free Obstruction-Free 3. Obstruction-Free Lock-Free 4. Lock-Free (LF) Wait-Free 5. Wait-Free (WF) 6. Wait-Free Bounded (WFB) 7. Wait-Free Population Oblivious (WFPO)

rust memory ordering

Introduces the memory ordering in rust.

lock-free statck written with C11

This is a versioning solution to solve the ABA problem of lock-free singly-liked list.

lock-free singly-linked list written with C++11

This is an attempt to implement a lock-free singly-linked list using hazard pointer and reference counting technique.

lock-free data structure lib in C

Learn from others! This lock-free lib is written in C, may lack of portibility.

linus’ comment on store buffer store buffer

Some disscusion on store buffer.

A primer on memory consistency and cache coherence

一本书, 有pdf版本. 从硬件设计的角度阐述如何设计原子指令, 硬件的内存模型是什么, 如何保证内存模型的 正确性

C++ Concurrency in Action, 2nd Edition

一本书, 有pdf版本. C++ 并行编程, 有锁无锁, 内存模型讲的比较清楚. 附带了一些例子.

MESI cache coherence protocol

“Memory System (Memory Coherency and Protocol)” (PDF). AMD64 Technology. September 2006.

13.2 Videos and talks

CppCon 2014: Herb Sutter “Lock-Free Programming” 1/2
CppCon 2014: Herb Sutter “Lock-Free Programming” 2/2

Herb Sutter’s talk about lock-free programming, part 1 introduce some fundamentals, and part 2 is mainly about some concrete examples like: lock-free single list with push and pop and some analysis. Herb Sutter also implicitly talks

C++ and Beyond 2012: Herb Sutter - atomic Weapons 1 of 2
C++ and Beyond 2012: Herb Sutter - atomic Weapons 2 of 2

Herb Sutter’s talk about atomic, part 1 is mainly about the fundamentals that what is memory order and why they exists, and what is acquire and release semantics, what does the compiler do for optimization related with instruction compile-time reordering.

Part 2 is mainly about the optimization that the compiler does about memory order. In this part Herb shows the emitted assembly code for different architecture CPUs under different circumstances, which can help understanding the software acquire and release semantics on hardware level.

CppCon 2014: Jeff Preshing “How Ubisoft Develops Games for Multicore - Before and After C++11”

Jeff’s talk about atomic lib of C++11.

ACCU 2017 - Atomic’s memory orders, what for? - Frank Birbacher

This talk is mainly about “synchronize-with” relation explanation.

The C++ Memory Model - Valentin Ziegler @ Meeting C++ 2014

This talk is about memory model of C++11, the first half explains “Sequential Consistency” in CPP memory model very well, the second half is not that informative.

CppCon 2015: Michael Wong “C++11/14/17 atomics and memory mode

This talk introduce the memory model of C++11/14/17 on a high level. The speaker introduces a lot of concepts and definitions of design of memory model of C++11/14/17, like:

1. sequential consistency
2. what is memory model.
3. synchronizes-with, sequenced-before, happens-before
4. etc. it’s worth watching though the content arrangement seems a little messy.

CppCon 2017: Fedor Pikus “C++ atomics, from basic to advanced. What do they really do?”

This talk gives very clear explanation of CAS weak/strong, Fedor uses DCLP to explain CAS implementation, which is impressive. And he also talks about performance compared to non-atomic operations and mutex operations.