我正在尝试使用 64 位积分作为位图，并以原子方式获取/释放各个位的所有权。

为此，我编写了以下无锁代码:

#include <cstdint>
#include <atomic>

static constexpr std::uint64_t NO_INDEX = ~std::uint64_t(0);

class AtomicBitMap {
public:
    static constexpr std::uint64_t occupied() noexcept {
        return ~std::uint64_t(0);
    }

    std::uint64_t acquire() noexcept {
        while (true) {
            auto map = mData.load(std::memory_order_relaxed);
            if (map == occupied()) {
                return NO_INDEX;
            }

            std::uint64_t index = __builtin_ctzl(~map);
            auto previous =
                mData.fetch_or(bit(index), std::memory_order_relaxed);
            if ((previous & bit(index)) == 0) {
                return index;
            }
        }
    }

private:
    static constexpr std::uint64_t bit(std::uint64_t index) noexcept {
        return std::uint64_t(1) << index;
    }

    std::atomic_uint64_t mData{ 0 };
};

int main() {
    AtomicBitMap map;
    return map.acquire();
}

其中，on godbolt , 单独生成以下程序集:

main:
  mov QWORD PTR [rsp-8], 0
  jmp .L3
.L10:
  not rax
  rep bsf rax, rax
  mov edx, eax
  mov eax, eax
  lock bts QWORD PTR [rsp-8], rax
  jnc .L9
.L3:
  mov rax, QWORD PTR [rsp-8]
  cmp rax, -1
  jne .L10
  ret
.L9:
  movsx rax, edx
  ret

这正是我所期望的¹。

@Jester英勇地减少了my 97 lines reproducer到一个更简单的 44 lines reproducer我进一步减少到35 lines :

using u64 = unsigned long long;

struct Bucket {
    u64 mLeaves[16] = {};
};

struct BucketMap {
    u64 acquire() noexcept {
        while (true) {
            u64 map = mData;

            u64 index = (map & 1) ? 1 : 0;
            auto mask = u64(1) << index;

            auto previous =
                __atomic_fetch_or(&mData, mask, __ATOMIC_SEQ_CST);
            if ((previous & mask) == 0) {
                return index;
            }
        }
    }

    __attribute__((noinline)) Bucket acquireBucket() noexcept {
        acquire();
        return Bucket();
    }

    volatile u64 mData = 1;
};

int main() {
    BucketMap map;
    map.acquireBucket();
    return 0;
}

生成以下程序集:

BucketMap::acquireBucket():
  mov r8, rdi
  mov rdx, rsi

.L2:
  mov rax, QWORD PTR [rsi]
  xor eax, eax
  lock bts QWORD PTR [rdx], rax
  setc al
  jc .L2
  mov rdi, r8
  mov ecx, 16
  rep stosq
  mov rax, r8
  ret

main:
  sub rsp, 152
  lea rsi, [rsp+8]
  lea rdi, [rsp+16]
  mov QWORD PTR [rsp+8], 1
  call BucketMap::acquireBucket()
  xor eax, eax
  add rsp, 152
  ret

xor eax,eax 表示这里的程序集总是试图获取索引0...导致无限循环。

对于这个程序集，我只能看到两种解释:

1. 我以某种方式触发了未定义行为。
2. gcc 中存在代码生成错误。

关于什么会触发 UB，我已经用尽了所有想法。

谁能解释一下为什么 gcc 会生成这个 xor eax,eax？

注意:暂时向 gcc 报告为 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86314 .

使用的编译器版本:

$ gcc --version
gcc (GCC) 7.3.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is 
NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR 
PURPOSE.

编译器标志:

-Wall -Wextra -Werror -Wduplicated-cond -Wnon-virtual-dtor -Wvla 
-rdynamic -Wno-deprecated-declarations -Wno-type-limits 
-Wno-unused-parameter -Wno-unused-local-typedefs -Wno-unused-value 
-Wno-aligned-new -Wno-implicit-fallthrough -Wno-deprecated 
-Wno-noexcept-type -Wno-register -ggdb -fno-strict-aliasing 
-std=c++17 -Wl,--no-undefined -Wno-sign-compare 
-g -O3 -mpopcnt

¹ 其实比我预想的要好，编译器理解为 fetch_or(bit(index)) 后跟 previous & bit( index) 相当于使用 bts 并检查 CF 标志是纯金。

最佳答案

这是 gcc 中的窥孔优化错误，请参阅 #86413影响版本 7.1、7.2、7.3 和 8.1。该修复程序已经存在，并将分别在版本 7.4 和 8.2 中提供。

简短的回答是特定的代码序列(fetch_or + 检查结果)生成 setcc (设置条件，也就是基于标志的状态)后跟 movzbl (移动和零扩展)；在 7.x 中引入了优化，它转换了 setcc紧随其后的是 movzbl变成 xor紧随其后的是 setcc ，但是此优化缺少一些检查，导致 xor可能会破坏仍然需要的寄存器(在本例中为 eax)。

更长的答案是fetch_or可以实现为 cmpxchg为了完全通用，或者，如果只设置一位，则为 bts (位测试和设置)。作为 7.x 中引入的另一个优化，gcc 现在生成 bts在这里(gcc 6.4 仍然生成 cmpxchg )。 bts将进位标志 (CF) 设置为该位的前一个值。

也就是说，auto previous = a.fetch_or(bit); auto n = previous & bit;将生成:

• lock bts QWORD PTR [<address of a>], <bit index>设置位，并捕获其先前的值，
• setc <n>l设置 r<n>x 的低 8 位到进位标志的值( CF )，
• movzx e<n>x, <n>l将 r<n>x 的高位清零.

然后会应用窥视孔优化，这会搞砸。

gcc 中继现在生成 proper assembly :

BucketMap::acquireBucket():
    mov rdx, rdi
    mov rcx, rsi
.L2:
    mov rax, QWORD PTR [rsi]
    and eax, 1
    lock bts QWORD PTR [rcx], rax
    setc al
    movzx eax, al
    jc .L2
    mov rdi, rdx
    mov ecx, 16
    rep stosq
    mov rax, rdx
    ret
main:
    sub rsp, 152
    lea rsi, [rsp+8]
    lea rdi, [rsp+16]
    mov QWORD PTR [rsp+8], 1
    call BucketMap::acquireBucket()
    xor eax, eax
    add rsp, 152
    ret

虽然不幸的是优化不再适用，所以我们只剩下 setc + mov而不是 xor + setc ...但至少它是正确的!

关于c++ - 带有 gcc 7.3 的 __atomic_fetch_or 的意外 x64 程序集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51020541/