lockfree freelist doesn't destruct objects until its destructor is called

[toffaletti@…]

This code demonstrates the problem:

$ cat leak.cc
#include <boost/lockfree/queue.hpp>
#include <memory>
#include <vector>
#include <thread>
#include <atomic>

static std::atomic<uint64_t> count{0};

struct LeakFinder {
    LeakFinder() {
        ++count;
    }

    ~LeakFinder() {
        --count;
    }
};

static boost::lockfree::queue<std::shared_ptr<LeakFinder>> queue(128);
static bool done = false;

void producer() {
    for (int i=0; i<1; ++i) {
        queue.push(std::make_shared<LeakFinder>());
    }
}

void consumer() {
    while (!done) {
        std::shared_ptr<LeakFinder> v;
        while (queue.pop(v));
    }
}

int main() {
    std::vector<std::thread> producer_threads;
    std::vector<std::thread> consumer_threads;
    for (int i=0; i<1; ++i) {
        producer_threads.emplace_back(producer);
    }

    for (int i=0; i<1; ++i) {
        consumer_threads.emplace_back(producer);
    }

    for (auto &t : producer_threads) {
        t.join();
    }

    done = true;

    for (auto &t : consumer_threads) {
        t.join();
    }

    std::cout << "leak: " << count << "\n";
}

$ g++ -ggdb -std=c++11 -pthread -I/home/jason/boost-1.53/include leak.cc
$ ./a.out 
leak: 2

I think destructors should be called when memory is added to freelist.

[timblechmann]

destructors are called when nodes are pushed to the freelist. however your reproducer has 3 problems:

• there is no guarantee that the consumers will pop() all elements
• the queue type does not have a trivial assignment
• the queue type does not have a trivial destructor

feel free to reopen, if you think it is not a problem in your code.

[anonymous]

Reopening because I've got a few questions about your response. True my code had a race condition, but the original code I was trying to distill did not. Here is a version without a race condition that still has the leak:

#include <boost/lockfree/queue.hpp>
#include <memory>
#include <vector>
#include <thread>
#include <atomic>

static std::atomic<uint64_t> count{0};

struct LeakFinder {
    LeakFinder() {
        ++count;
    }

    ~LeakFinder() {
        --count;
    }
};

static boost::lockfree::queue<std::shared_ptr<LeakFinder>> queue(128);
static bool done = false;

void producer() {
    for (int i=0; i<1; ++i) {
        queue.push(std::make_shared<LeakFinder>());
    }
}

int main() {
    std::vector<std::thread> producer_threads;
    for (int i=0; i<1; ++i) {
        producer_threads.emplace_back(producer);
    }
                                                                                                                                                                                                                                           
    for (auto &t : producer_threads) {
        t.join();
    }

    {
        std::shared_ptr<LeakFinder> v;
        while (queue.pop(v));
    }

    std::cout << "leak: " << count << "\n";
}

I didn't see anything in the documentation that says queue can only store POD types with trivial assignment and destructor. If that is the case it should be noted and use static_assert to make it a compile time error.

[timblechmann]

check the requirements: ​http://boost-sandbox.sourceforge.net/doc/html/boost/lockfree/queue.html

you can use non-pod types, but as stated above, trivial destructors and assignments are required (by the algorithm).

maybe it can be statically asserted these days, when i wrote this code, the type traits were not widely implemented.

[anonymous]

I see, I missed that part in the docs. Thanks for being patient. boost has wrappers to make type traits and static assert work on supported compilers:

http://www.boost.org/doc/libs/1_52_0/libs/type_traits/doc/html/boost_typetraits/reference/is_pod.html http://www.boost.org/doc/libs/1_52_0/doc/html/boost_staticassert.html

What about the algorithm requires POD? It seems like it is doing everything that would be needed to support non-POD types. And indeed the destructor is called for all but 1 of the items, which sticks around until the queue goes out of scope at which point it too is destructed. Which is to say the program is valgrind clean:

==38928== HEAP SUMMARY:
==38928==     in use at exit: 0 bytes in 0 blocks
==38928==   total heap usage: 147 allocs, 147 frees, 9,088 bytes allocated
==38928== 
==38928== All heap blocks were freed -- no leaks are possible

Also, if only trivial POD types are supported, why even call the destructor? trivial destructors don't do anything.

[timblechmann]

a) check the michael/scott paper. in short: the content is copied before it is known to be valid. likewise the invalid objects can be destructed.

b) the queue uses a dummy node, probably the item you see when the queue is destructed

c) the freelist is also used by the stack, which does not have the requirements for assignment and destructor

[anonymous]

Replying to timblechmann:

a) check the michael/scott paper. in short: the content is copied before it is known to be valid. likewise the invalid objects can be destructed.

I see, that makes sense. The value is copied before the CAS, but only used if the CAS succeeds, so if it had a non-trivial destructor or assignment it could be in some invalid state. I'm probably just getting lucky with std::shared_ptr since it is meant to be thread-safe.

You probably can't sneak this into boost, but I think most types actually would work if you ignored the rules that C++ objects aren't relocatable because most are, see:

github.com/facebook/folly/blob/master/folly/docs/FBVector.md#object-relocation

Also what I said before was wrong, is_pod is too strict, and you want these:

http://www.boost.org/doc/libs/1_52_0/libs/type_traits/doc/html/boost_typetraits/reference/has_trivial_copy.html http://www.boost.org/doc/libs/1_52_0/libs/type_traits/doc/html/boost_typetraits/reference/has_trivial_destructor.html

b) the queue uses a dummy node, probably the item you see when the queue is destructed

I considered that, but the default constructor for shared_ptr wouldn't create my LeakFinder object. If I modify the program to only put 1 item in the queue and then break on the constructor of LeakFinder in gdb, the only one created is the one I push to the queue.

c) the freelist is also used by the stack, which does not have the requirements for assignment and destructor

In any case I'm satisfied. Thanks for humoring me.

[timblechmann]

closing, as neither valgrind nor totalview actually detect a memory leak. we also have static assertions now.