I'm trying to get the lockfree queue example from the book C++ Concurrency in Action (A. Williams) running. Since I initialized the "null" counter_node_ptr objects with a sinlge {0} I get no aborts. But now I still have memory leaks and jumps that depend on uninitialised values. The latter may be an issue of valgrind, but the former is a problem for me and I would like to get rid of it. So here is the complete example. Any help is welcome:
// c++ -g lock_free_queue.cpp -latomic -pthread -o lock_free_queue
// valgrind ./lock_free_queue
#include <memory>
#include <atomic>
#include <thread>
#include <chrono>
using namespace std::chrono_literals;
// leaking memory
template<typename T>
class lock_free_queue
{
private:
struct node;
struct counted_node_ptr
{
int external_count;
node* ptr;
/*
counted_node_ptr() noexcept
: external_count(0)
, ptr(nullptr) {}
*/
};
std::atomic<counted_node_ptr> head;
std::atomic<counted_node_ptr> tail;
struct node_counter
{
unsigned internal_count:30;
unsigned external_counters:2;
node_counter() noexcept
: internal_count(0)
, external_counters(2) {}
};
struct node
{
std::atomic<T*> data;
std::atomic<node_counter> count;
std::atomic<counted_node_ptr> next;
node() noexcept
{
data.store(nullptr);
node_counter new_count;
count.store(new_count);
next.store(counted_node_ptr());
}
void release_ref()
{
node_counter old_counter=
count.load(std::memory_order_relaxed);
node_counter new_counter;
do
{
new_counter=old_counter;
--new_counter.internal_count;
}
while(!count.compare_exchange_strong
(old_counter,new_counter,
std::memory_order_acquire,std::memory_order_relaxed));
if(!new_counter.internal_count &&
!new_counter.external_counters)
{
delete this;
}
}
};
static void increase_external_count(
std::atomic<counted_node_ptr>& counter,
counted_node_ptr& old_counter)
{
counted_node_ptr new_counter;
do
{
new_counter=old_counter;
++new_counter.external_count;
}
while(!counter.compare_exchange_strong(
old_counter,new_counter,
std::memory_order_acquire,std::memory_order_relaxed));
old_counter.external_count=new_counter.external_count;
}
static void free_external_counter(counted_node_ptr &old_node_ptr)
{
node* const ptr=old_node_ptr.ptr;
int const count_increase=old_node_ptr.external_count-2;
node_counter old_counter=
ptr->count.load(std::memory_order_relaxed);
node_counter new_counter;
do
{
new_counter=old_counter;
--new_counter.external_counters;
new_counter.internal_count+=count_increase;
}
while(!ptr->count.compare_exchange_strong(
old_counter,new_counter,
std::memory_order_acquire,std::memory_order_relaxed));
if(!new_counter.internal_count &&
!new_counter.external_counters)
{
delete ptr;
}
}
void set_new_tail(counted_node_ptr &old_tail,
counted_node_ptr const &new_tail)
{
node* const current_tail_ptr=old_tail.ptr;
while(!tail.compare_exchange_weak(old_tail,new_tail) &&
old_tail.ptr==current_tail_ptr);
if(old_tail.ptr==current_tail_ptr)
free_external_counter(old_tail);
else
current_tail_ptr->release_ref();
}
public:
lock_free_queue()
{
counted_node_ptr new_head;
new_head.ptr = new node;
new_head.external_count = 1;
head.store(new_head);
tail = head.load();
}
lock_free_queue(const lock_free_queue& other)=delete;
lock_free_queue& operator=(const lock_free_queue& other)=delete;
~lock_free_queue()
{
while(pop());
delete head.load().ptr;
}
void push(T new_value)
{
std::unique_ptr<T> new_data(new T(new_value));
counted_node_ptr new_next;
new_next.ptr=new node;
new_next.external_count=1;
counted_node_ptr old_tail=tail.load();
for(;;)
{
increase_external_count(tail,old_tail);
T* old_data=nullptr;
if(old_tail.ptr->data.compare_exchange_strong(
old_data,new_data.get()))
{
counted_node_ptr old_next{0};
if(!old_tail.ptr->next.compare_exchange_strong
(old_next,new_next))
{
delete new_next.ptr;
new_next=old_next;
}
set_new_tail(old_tail, new_next);
new_data.release();
break;
}
else
{
counted_node_ptr old_next{0};
if(old_tail.ptr->next.compare_exchange_strong(
old_next,new_next))
{
old_next=new_next;
new_next.ptr=new node;
}
set_new_tail(old_tail, old_next);
}
}
}
std::unique_ptr<T> pop()
{
counted_node_ptr old_head=head.load(std::memory_order_relaxed);
for(;;)
{
increase_external_count(head,old_head);
node* const ptr=old_head.ptr;
if(ptr==tail.load().ptr)
{
return std::unique_ptr<T>();
}
counted_node_ptr next=ptr->next.load();
if(head.compare_exchange_strong(old_head,next))
{
T* const res=ptr->data.exchange(nullptr);
free_external_counter(old_head);
return std::unique_ptr<T>(res);
}
ptr->release_ref();
}
}
std::shared_ptr<T> wait_and_pop()
{
std::unique_ptr<T> value_ptr = pop();
while (!value_ptr)
{
std::this_thread::yield();
value_ptr = pop();
}
return value_ptr;
}
};
#define MAIN
#ifdef MAIN
#include <iostream>
int main()
{
lock_free_queue<int> hallo;
int a = 0;
int b = 0;
int c = 0;
int d = 0;
int e = 0;
int f = 0;
//#define WAIT_AND_POP
#ifdef WAIT_AND_POP
std::thread task2 = std::thread( [&] () {
//std::this_thread::sleep_for(2s);
a = *(hallo.wait_and_pop());
b = *(hallo.wait_and_pop());
});
std::thread task3 = std::thread( [&] () {
//std::this_thread::sleep_for(2s);g
c = *(hallo.wait_and_pop());
d = *(hallo.wait_and_pop());
});
#else // #findef WAIT_AND_POP
std::thread task2 = std::thread( [&] () {
//std::this_thread::sleep_for(2s);
std::unique_ptr<int> ap = hallo.pop();
a = (ap ? *(ap.get()) : 0);
std::unique_ptr<int> bp = hallo.pop();
b = (bp ? *(bp.get()) : 0);
std::unique_ptr<int> ep = hallo.pop();
e = (ep ? *(ep.get()) : 0);
});
std::thread task3 = std::thread( [&] () {
//std::this_thread::sleep_for(2s);
std::unique_ptr<int> cp = hallo.pop();
c = (cp ? *(cp.get()) : 0);
std::unique_ptr<int> dp = hallo.pop();
d = (dp ? *(dp.get()) : 0);
std::unique_ptr<int> fp = hallo.pop();
f = (fp ? *(fp.get()) : 0);
});
#endif
std::this_thread::sleep_for(1s);
std::thread task0 = std::thread( [&] () {
hallo.push(10);
hallo.push(2);
});
std::thread task1 = std::thread( [&] () {
hallo.push(5);
hallo.push(6);
});
std::thread task4 = std::thread( [&] () {
hallo.push(5);
hallo.push(6);
});
task1.join();
task2.join();
task3.join();
task0.join();
task4.join();
std::cout << "a = " << a << " b = " << b << " c = " << c << " d = " << d << std::endl;
if (hallo.pop())
{
std::cout << "more data than expected" << std::endl;
}
else
{
std::cout << "ok" << std::endl;
}
}
#endif
Aucun commentaire:
Enregistrer un commentaire