__atomic_fetch_or 与 gcc 7.3 的意外 x64 程序集
Unexpected x64 assembly for __atomic_fetch_or with gcc 7.3
我正在尝试使用 64 位整数作为位图，并且 acquire/release 原子地拥有各个位。
为此，我编写了以下无锁代码：
#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
这正是我所期望的1.
@Jester has heroically managed to reduce my 97 lines reproducer to a much simpler 44 lines reproducer which I further reduced to 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...导致无限循环。
这个程序集我只能看到两个解释：
- 我以某种方式触发了未定义的行为。
- 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
1 实际上，它比我预期的要好，编译器理解 fetch_or(bit(index)) 后跟 previous & bit(index) 相当于使用 bts 并检查 CF 标志是否为纯金。
作为旁注，您可以通过直接的位操作找到最低的 0 位：
template<class T>
T find_lowest_0_bit_mask(T value) {
T t = value + 1;
return (t ^ value) & t;
}
Returns 位掩码，而不是位索引。
预编码：T 必须是无符号的，value 必须至少包含 1 个零位。
mData.load必须与mData.fetch_or同步，所以应该是
mData.load(std::memory_order_acquire)
和
mData.fetch_or(..., std::memory_order_release)
而且，IMO，这些位内在函数中有些东西会导致它使用 clang 生成错误的程序集，请参阅 .LBB0_5 loop that is clearly wrong because it keeps trying to set the same bit rather than recalculating another bit to set. A version that generates correct assembly:
#include <cstdint>
#include <atomic>
static constexpr int NO_INDEX = -1;
template<class T>
T find_lowest_0_bit_mask(T value) {
T t = value + 1;
return (t ^ value) & t;
}
class AtomicBitMap {
public:
static constexpr std::uint64_t occupied() noexcept { return ~std::uint64_t(0); }
int acquire() noexcept {
auto map = mData.load(std::memory_order_acquire);
while(map != occupied()) {
std::uint64_t mask = find_lowest_0_bit_mask(map);
if(mData.compare_exchange_weak(map, map | mask, std::memory_order_release))
return __builtin_ffsl(mask) - 1;
}
return NO_INDEX;
}
void release(int i) noexcept {
mData.fetch_and(~bit(i), std::memory_order_release);
}
private:
static constexpr std::uint64_t bit(int index) noexcept {
return std::uint64_t(1) << index;
}
std::atomic_uint64_t mData{ 0 };
};
xor-zero / set flags / setcc 通常是创建 32 位 0/1 整数的最佳方法。
显然，只有在不破坏标志设置指令的任何输入的情况下将备用寄存器设为 xor-0 时，这样做才是安全的，所以这显然是一个错误。
（否则你可以 setcc dl / movzx eax,dl。单独的 regs 更可取，这样 movzx 在某些 CPU 上可以是零延迟（移动消除），但它在其他 CPU 上的关键路径上所以 xor/set-flags / setcc 习惯用法更可取，因为关键路径上的指令更少。）
IDK 为什么 gcc 会在寄存器中创建 (previous & mask) == 0 的整数值；这可能是错误的一部分。
这是 gcc 中的窥孔优化错误，请参阅影响版本 7.1、7.2、7.3 和 8.1 的 #86413。修复已经在，并将分别在版本 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...但至少它是正确的！
我正在尝试使用 64 位整数作为位图，并且 acquire/release 原子地拥有各个位。
为此，我编写了以下无锁代码：
#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
这正是我所期望的1.
@Jester has heroically managed to reduce my 97 lines reproducer to a much simpler 44 lines reproducer which I further reduced to 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...导致无限循环。
这个程序集我只能看到两个解释：
- 我以某种方式触发了未定义的行为。
- 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
1 实际上，它比我预期的要好，编译器理解 fetch_or(bit(index)) 后跟 previous & bit(index) 相当于使用 bts 并检查 CF 标志是否为纯金。
作为旁注，您可以通过直接的位操作找到最低的 0 位：
template<class T>
T find_lowest_0_bit_mask(T value) {
T t = value + 1;
return (t ^ value) & t;
}
Returns 位掩码，而不是位索引。
预编码：T 必须是无符号的，value 必须至少包含 1 个零位。
mData.load必须与mData.fetch_or同步，所以应该是
mData.load(std::memory_order_acquire)
和
mData.fetch_or(..., std::memory_order_release)
而且，IMO，这些位内在函数中有些东西会导致它使用 clang 生成错误的程序集，请参阅 .LBB0_5 loop that is clearly wrong because it keeps trying to set the same bit rather than recalculating another bit to set. A version that generates correct assembly:
#include <cstdint>
#include <atomic>
static constexpr int NO_INDEX = -1;
template<class T>
T find_lowest_0_bit_mask(T value) {
T t = value + 1;
return (t ^ value) & t;
}
class AtomicBitMap {
public:
static constexpr std::uint64_t occupied() noexcept { return ~std::uint64_t(0); }
int acquire() noexcept {
auto map = mData.load(std::memory_order_acquire);
while(map != occupied()) {
std::uint64_t mask = find_lowest_0_bit_mask(map);
if(mData.compare_exchange_weak(map, map | mask, std::memory_order_release))
return __builtin_ffsl(mask) - 1;
}
return NO_INDEX;
}
void release(int i) noexcept {
mData.fetch_and(~bit(i), std::memory_order_release);
}
private:
static constexpr std::uint64_t bit(int index) noexcept {
return std::uint64_t(1) << index;
}
std::atomic_uint64_t mData{ 0 };
};
xor-zero / set flags / setcc 通常是创建 32 位 0/1 整数的最佳方法。
显然，只有在不破坏标志设置指令的任何输入的情况下将备用寄存器设为 xor-0 时，这样做才是安全的，所以这显然是一个错误。
（否则你可以 setcc dl / movzx eax,dl。单独的 regs 更可取，这样 movzx 在某些 CPU 上可以是零延迟（移动消除），但它在其他 CPU 上的关键路径上所以 xor/set-flags / setcc 习惯用法更可取，因为关键路径上的指令更少。）
IDK 为什么 gcc 会在寄存器中创建 (previous & mask) == 0 的整数值；这可能是错误的一部分。
这是 gcc 中的窥孔优化错误，请参阅影响版本 7.1、7.2、7.3 和 8.1 的 #86413。修复已经在，并将分别在版本 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...但至少它是正确的！