无锁原子C/C++编程中，内存重排是否会影响预期结果？

背景 #

我并非无锁编程新手，熟悉memory_order、内存屏障、全局可见性等概念。希望在无锁编程中使用更轻量的memory_order（如用acquire/release甚至relaxed替代memory_order_seq_cst）以提升性能，但不确定是否会引发意外结果。

问题 #

我将通过几个抽象的具体案例说明问题，这些案例仅为思想实验，无实际意义。

前提条件 #

• 对于多线程同时读写同一非原子变量的情况（C/C++标准中为UB），假设读写值未定义（如同随机数）且无其他副作用；也可将这类变量替换为原子类型并以relaxed属性读写，符合标准且不影响讨论。
• 所有内存不会被释放，无需考虑UAF问题。

Case1 #

假设有一个单链表，多个reader线程并发遍历，writer线程尝试破坏节点：

1. 链表初始化后全局可见；
2. 长度任意（示例为10000000个节点）；
3. 仅包含初始化时的节点，不会插入已遍历或新节点；
4. 节点地址无关（内存访问可重排），示例用全局数组实现。

C代码如下：

#define NODES_NUM 10000000ULL
struct node {
    struct node *next;
} __attribute__((aligned(512))) nodes[NODES_NUM]; // align to cache line to make memory reorder happen

_Atomic(struct node *) head __attribute__((aligned(512))) = &nodes[0];

void __attribute__((constructor)) init(void)
{
    for (size_t i = 0; i < NODES_NUM - 1; ++i)
        nodes[i].next = &nodes[i + 1];
}

void *reader(void *arg)
{
    struct node *cur = atomic_load_explicit(&head, memory_order_relaxed);
    while (cur != NULL) {
        struct node *next = cur->next;
        if (atomic_compare_exchange_weak_explicit(&head, &cur, next, memory_order_release, memory_order_relaxed))
            cur = next;
    }
    return NULL;
}

void *writer(void *arg)
{
    struct node *cur;
    while ((cur = atomic_load_explicit(&head, memory_order_acquire)) != NULL) {
        if (cur > &nodes[0])
            (cur - 1)->next = (void *)(uintptr_t)rand(); // any invalid pointer
    }
    return NULL;
}

int main(void)
{
    pthread_t th;

    for (size_t i = 0; i < xxx; ++i) // xxx > 1
        pthread_create(&th, NULL, writer, NULL);
    for (size_t i = 0; i < xxx; ++i) // xxx > 1
        pthread_create(&th, NULL, reader, NULL);

    while (1)
        pause();
    return 0;
}

能否成功遍历链表（遍历所有节点且无线程访问非法内存）？
答案是肯定的。

以node[49]为例：多个reader可能同时读取node[49].next并尝试将head从&node[49]改为node[49]->next，但最终仅一个reader成功，其余读取不影响遍历。

同时，多个writer尝试修改node[49].next前，需读取到head == &node[50]，这对应成功修改head的reader的release操作，意味着修改node[49].next与上述读取不会并发，reader读到的node[49]->next始终正确。

若将所有memory_order改为relaxed，writer与reader的读取可并发，但仍能成功遍历：writer仅在看到head == &node[50]时修改node[49]，即若node[49]被修改，head == &node[50]必然已发生，即使修改的全局可见性早于head赋值。

Case2 #

本案例与Case1类似，但每个线程修改已遍历的节点。

C代码如下：

#define NODES_NUM 10000000ULL
struct node {
    struct node *next;
} __attribute__((aligned(512))) nodes[NODES_NUM]; // align to cache line to make memory reorder happen

_Atomic(struct node *) head __attribute__((aligned(512))) = &nodes[0];

void __attribute__((constructor)) init(void)
{
    for (size_t i = 0; i < NODES_NUM - 1; ++i)
        nodes[i].next = &nodes[i + 1];
}

void *thread(void *arg)
{
    struct node *cur = atomic_load_explicit(&head, memory_order_relaxed);
    while (cur != NULL) {
        struct node *next = cur->next;

        if (atomic_compare_exchange_weak_explicit(&head, &cur, next, memory_order_relaxed, memory_order_relaxed)) {
            cur->next = (void *)(uintptr_t)rand(); // any invalid pointer
            cur = next;
        }
    }
    return NULL;
}

int main(void)
{
    pthread_t th;

    for (size_t i = 0; i < xxx; ++i) // xxx > 1
        pthread_create(&th, NULL, thread, NULL);

    while (1)
        pause();
    return 0;
}

能否成功遍历链表？
答案是肯定的，即使所有memory_order为relaxed。这与Case1逻辑一致，修改节点的线程与成功读取该节点并修改head的是同一线程，同一线程不受内存重排影响，无并发问题。

Case3 #

若认同Case1/2的结论，可探讨Case3，代码如下：

int x __attribute__((aligned(4096))) = 1;
atomic_int y __attribute__((aligned(4096))) = 0;

void thread1(void)
{
    int tmp = 0, tmp_x = x;
    bool success = atomic_compare_exchange_strong_explicit(&y, &tmp, tmp_x, memory_order_relaxed, memory_order_relaxed);

    assert(!success || tmp_x == 1);
}

void thread2(void)
{
    int tmp = 0;

    atomic_compare_exchange_strong_explicit(&y, &tmp, 1, memory_order_relaxed, memory_order_relaxed);
    x = 2;
}

所有memory_order为relaxed，assert()是否会触发？
当然会！编译器可能将x = 2重排至cmpxchg前，可能出现以下流程：

1. thread2写入x = 2；
2. thread1读取tmp_x = 2；
3. thread1成功执行cmpxchg，将y改为2；
4. assert触发。

Case4 #

稍作修改后的代码：

int x __attribute__((aligned(4096)))  = 1;
atomic_int y __attribute__((aligned(4096))) = 0;

void thread1(void)
{
    int tmp = 0, tmp_x = x;
    bool success = atomic_compare_exchange_strong_explicit(&y, &tmp, tmp_x, memory_order_relaxed, memory_order_relaxed);

    assert(!success || tmp_x == 1);
}

void thread2(void)
{
    int tmp = 0;

    if (atomic_compare_exchange_strong_explicit(&y, &tmp, 1, memory_order_relaxed, memory_order_relaxed) || tmp == 1)
        x = 2;
    else
        abort();
}

abort()或assert()是否会触发？
先分析abort()：若触发，说明thread2的cmpxchg未修改y，即y已被thread1改为2，但else分支不会执行x=2，thread1无法读到x=2，矛盾。

再分析assert()：若触发，说明thread1成功将y改为非1值，此时thread2的if条件不成立，不会执行x=2，thread1无法读到x≠1，矛盾。

但Case3与Case4逻辑等价，若thread2的if条件始终为真，可移除该条件。

内容的提问来源于stack exchange，提问作者untitled