mercredi 3 février 2016

Is it a correct implementation of interlocked singly linked list in C++11

I have the following implementation of interlocked singly linked list using C++11 atomics:

struct notag {};

template<class T, class Tag=notag>
struct s_list_base
{
};

template<class T, class Tag = notag>
struct s_list : s_list_base<T, Tag>
{
    s_list_base<T, Tag> *next_ptr;
};

template<bool auto_destruct, class T, class Tag = notag>
class atomic_s_list
{
    struct s_head : s_list_base<T, Tag>
    {
        std::atomic<s_list_base<T, Tag > *> next_ptr { this };
    };
    using LinkType = s_list<T, Tag> *;

    s_head head;

public:
    atomic_s_list() = default;
    atomic_s_list(const atomic_s_list &) = delete;
    atomic_s_list &operator =(const atomic_s_list &) = delete;

    ~atomic_s_list()
    {
        clear();
    }

    void clear() noexcept
    {
        if (auto_destruct)
        {
            T *item;
            do
            {
                item = pop();
                delete item;
            } while (item);
        }
        else
            head.next_ptr = &head;
    }

    void push(T *pItem) noexcept
    {
        auto p = static_cast<LinkType>(pItem);
        auto phead = head.next_ptr.load(std::memory_order_relaxed);
        do
        {
            p->next_ptr = phead;
        } while (!head.next_ptr.compare_exchange_weak(phead, p));
    }

    T *pop() noexcept
    {
        auto result = head.next_ptr.load(std::memory_order_relaxed);
        while (!head.next_ptr.compare_exchange_weak(result, static_cast<LinkType>(result)->next_ptr))
            ;
        return result == &head ? nullptr : static_cast<T *>(result);
    }
};

The problem is that in real program I have several concurrently running threads that take an object from this list with pop, work with it and then put it back with push and it seems like I have a race when sometimes two threads end up getting the same object from a list.

I have tried to make a simple example out of that program, but it does not appear to have the same problems. Of course, the real program executes quite complex CPU-intensive work, allocates and frees memory and theoretically may have some memory corruption that eventually causes the assertion to fail, but right now it looks like sometimes the same object is obtained by two threads.

Here's a test program:

struct item : s_list<item>
{
    std::atomic<int> use{ 0 };
};

atomic_s_list<true, item> items;

item *allocate()
{
    auto *result = items.pop();
    if (!result)
        return new item;
}

void free(item *p)
{
    items.push(p);
}

int main()
{
    using namespace std::chrono_literals;
    static const int N = 20;
    std::vector<std::thread> threads;
    threads.reserve(N);


    for (int i = 0; i < 20; ++i)
    {
        threads.push_back(std::thread([&]
        {
            std::random_device seeder;
            std::mt19937 rd(seeder());
            std::uniform_int_distribution<int> uid(10, 500);

            while (true)
            {
                auto time = uid(rd);

                auto item = allocate();
                if (0 != item->use.fetch_add(1, std::memory_order_relaxed))
                    std::terminate(); // this test fails in real program. Does not fail in this test one, though

                // simulate some work
                std::this_thread::sleep_for(std::chrono::milliseconds(time));
                item->use.fetch_sub(1, std::memory_order_relaxed);
                free(item);
            }
        }));
    }

    std::this_thread::sleep_for(20min);
}

So the question is: is this implementation of interlocked singly-linked list correct?

Aucun commentaire:

Enregistrer un commentaire