问题描述
#include <iostream>
#include <atomic>
#include <memory>
template<typename T>
class LockFreeQueue {
public:
struct CountedNode;
private:
std::atomic<CountedNode> head;
public:
struct Node{
explicit Node(const T& d) : next(CountedNode()), data(std::make_shared<T>(d)), node_counter(0) { }
std::atomic<CountedNode> next;
std::shared_ptr<T> data;
std::atomic<unsigned> node_counter;
};
struct CountedNode {
CountedNode() noexcept : node(nullptr), counter(0) {}
explicit CountedNode( const T& data) noexcept : node(new Node(data) /* $4 */), counter(0) {}
Node* node;
int counter;
};
void push( const T& data)
{
CountedNode new_node(data), curr, incrementedNext, next /*($2) */;
CountedNode empty; /*($3) */
if (head.compare_exchange_strong(empty, new_node)) std::cout << "EQUALS\n"; // $1
else std::cout << "NOT EQUALS\n";
if (head.compare_exchange_strong(next, new_node)) std::cout << "EQUALS\n"; // $1
else std::cout << "NOT EQUALS\n";
}
};
int main() {
LockFreeQueue<int> Q;
Q.push(2);
return 0;
}
int main(){
LockFreeQueue<int> Q;
Q.push(2);
return 0;
}
好的。它编译和执行没有错误。但是，仍然有问题，我在下面描述。
Ok. It compiled and executed without error. But, there is still problem, which I described below.
在我看来，结果不是预期的：
注意
等于
On my eye, result it is not expected: NOTEQUALS EQUALS
我对上面的代码有一个很大的问题。
I have a wild problem with above piece of code.
特别是， $ 1 使我成为一个问题。我的意思是，这个比较总是返回false，虽然它应该在第一次返回true。
Especially, the comparison in the line $1 makes me a problem. I mean, this comparison always returns false though it should returns true at the first time.
我很困惑，所以我看看内存 / code>和 head ，实际上它们是不同的。 head 等于 0x00000000 0x00000000 0x00000000 0x00000000 （当它涉及字节），似乎是好的。但 empty 等于：
0x00000000 0x00000000 0x00000000 0x7f7f7f7f7f 。在 $ 2 中更有趣的是 next 等于 0x00000000 0x00000000 0x00000000 0x00000000 所以事实上，它等于 head 。但是，例如， curr ， incrementedNext 等于 0x00000000 0x00000000 0x00000000 0x7f7f7f7f7f 。
所以这种行为是不确定的，所以我想任何未定义的行为，但为什么？我不正确，请向我解释这个行为。
I was confused so I look into memory for empty and head and actually they are different. head is equal to 0x00000000 0x00000000 0x00000000 0x00000000 ( when it comes to bytes) and it seems to be OK. But empty is equal to:0x00000000 0x00000000 0x00000000 0x7f7f7f7f7f. What is more interesting next in the $2 is equal to 0x00000000 0x00000000 0x00000000 0x00000000 so in fact, it is equals to head. But, for example, curr, incrementedNext are equal to 0x00000000 0x00000000 0x00000000 0x7f7f7f7f7f.So the behaviour of that is undeterministic so I suppose any undefined behaviour, but why? What I do not correctly, please explain me this behaviour.
我知道在 $ 4 中的内存泄漏，但现在我忽略它。
P.S. I know about memory leak in the $4 but now I'm ignoring it.
我编译它：
g ++ -latomic main.cpp -std = c ++ 14 。
我的gcc版本是6.1.0。我测试了gcc 5.1.0以及。
I compiled it with:g++ -latomic main.cpp -std=c++14.My version of gcc is 6.1.0. I tested on gcc 5.1.0 as well. The result is same.
由@PeterCordes创建的源的链接：
The link to the source created by @PeterCordes: https://godbolt.org/g/X02QV8
推荐答案
填充。 std :: atomic :: compare_exchange * 比较两个对象的内存表示，就像 memcmp 。如果结构有paddding，它的内容是不确定的，并且可以使两个实例看起来不同，即使它们是成员相等的（注意 CountedNode 甚至不定义 operator == ）。
Padding. std::atomic::compare_exchange* compares memory representation of the two objects, as if by memcmp. If the structure has paddding, its contents are indeterminate, and may make two instances look distinct even if they are member-wise equal (note that CountedNode doesn't even define operator==).
在64位版本中， c $ c>，你会看到问题。在32位版本中，没有，你不会。
In 64-bit build, there's padding after counter, and you see the issue. In 32-bit build, there isn't, and you don't.
EDIT ：我现在相信，错误;只保留完整性。 std :: atomic_init 不执行任何操作以清零填充;
EDIT: the part below is, I now believe, wrong; only preserved for completeness. std::atomic_init doesn't do anything to zero out padding; the example only appears to work by accident.
head 以及 Node :: next ）应使用 std :: atomic_init 进行初始化：
head (as well as Node::next) should be initialized with std::atomic_init:
std::atomic_init(&head, CountedNode());
到那里，
这篇关于同一个类但是不同行为的相同实例。可能的UB的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！