3
\$\begingroup\$

This is a modern C++ implementation of a thread-safe memory pool -- I want to make sure I am solving the critical section problem correctly (no deadlocks, starvation, bounded waiting) and I am getting details like the rule of five correct (copy not allowed, move doesn't trigger double release). Design criteria:

  • Small number of items in pool (e.g. 5 to 10) since each may have a large memory footprint -- the number can be decided / fixed when the pool is created.
  • Uses RAII to guarantee an object is released when code leaves scope.
  • If there are no items available in the pool, the code blocks until one is available.

The typical usage pattern would be:

ObjectPool<Foo> pool(5, Foo_ctor_args);
...
{
     ObjectPool<Foo>::Item foo = pool.acquire()
     foo.object.doSomething();
} 

Class template:

    #include <vector>
    #include <mutex>
    #include <condition_variable>
    #include <cassert>
    #include <iostream>
    
    template <typename T>
    class ObjectPool {
    private:
        std::vector<T> objects;
        std::vector<bool> inUse;
        std::mutex mutex;
        std::condition_variable cond;
    public:
        
        class Item {
        public:
            T& object;
            Item(T& o, size_t i, ObjectPool& p) : object{o}, index{i}, pool{p} {}
            Item(const Item&) = delete;
            Item(Item&& other) : object{other.object}, index{other.index}, pool{other.pool} {
                other.index = bogusIndex;  // <-- don't release
            }
            Item& operator=(const Item&) = delete;
            Item& operator=(Item&& other) {
                if (this != &other) {
                    object = other.object;
                    index = other.index;
                    pool = other.pool;
                    other.index = bogusIndex;  // <-- don't release
                }
                return *this;
            }
            ~Item() {
                if (index != bogusIndex) {
                    pool.release(index);
                    index = bogusIndex;  // <-- avoid double release
                }
            }
        private:
            constexpr static size_t bogusIndex = 65535;
            size_t index;
            ObjectPool<T>& pool;
        };
        
        template<typename... Args>
        ObjectPool(size_t maxElems, Args&&... args) : inUse(maxElems, false) {
            for (size_t i = 0; i < maxElems; i++)
                objects.emplace_back(std::forward<Args>(args)...);
        }
        
        Item acquire() {
            std::unique_lock<std::mutex> guard(mutex);
            while (true) {
                for (size_t i = 0; i < objects.size(); i++)
                    if (!inUse[i]) {
                        inUse[i] = true;
                        return Item{objects[i], i, *this};
                    }
                cond.wait(guard);
            }
        }
    
    private:
        void release(size_t index) {
            std::unique_lock<std::mutex> guard(mutex);
            assert(index < objects.size());
            assert(inUse[index]);
            inUse[index] = false;
            cond.notify_all();
        }
    };
\$\endgroup\$
3
  • \$\begingroup\$ Use std::size_t instead of size_t. Because size_t is implementation defined and can cause problems on different compilers. \$\endgroup\$
    – digito_evo
    Jan 27 at 21:39
  • 1
    \$\begingroup\$ Incorporating advice from an answer into the question violates the question-and-answer nature of this site. You could post improved code as a new question, as an answer, or as a link to an external site - as described in I improved my code based on the reviews. What next?. I have rolled back the edit, so the answers make sense again. \$\endgroup\$ Jan 28 at 8:05
  • \$\begingroup\$ What? I left the original code completely intact so folks can see the original version. I clearly marked the part that was improved from the comments. \$\endgroup\$
    – wcochran
    Jan 28 at 15:59

1 Answer 1

3
\$\begingroup\$

Only allow ObjectPool to create Items

The rule of five is used correctly as far as I can see, but there are still some ways to create an incorrect Item, and use that to corrupt an existing ObjectPool. Consider:

ObjectPool<int> pool(10);
int value = 42;
decltype(foo)::Item item(value, 0, pool);

To prevent this from happening, make all constructors private, and make Item a friend of ObjectPool:

template <typename T>
class ObjectPool {
    ...
    class Item {
        friend ObjectPool;

        Item(T& o, size_t i, ObjectPool& p) : object{o}, index{i}, pool{p} {}
        Item(const Item&) = delete;
        Item(Item&& other) : object{other.object}, index{other.index}, pool{other.pool} {
            other.index = bogusIndex;  // <-- don't release
        }

    public:
        T& object;
        ...
    };
    ...
};

Make Item work like a std::unique_ptr

An Item is almost like a std::unique_ptr; while the pool is the actual owner, Item acts like a unique reference. I would make the member variable object private, and instead add these member functions to access it:

T& operator*() {
    return object;
}

T* operator->() {
    return &object;
}

T* get() {
    return &object;
}

Then you can do:

auto foo = pool.acquire();
foo->doSomething();

Consider adding a constructor that takes an initizalier list

An object pool is like a container. Consider that most STL containers allow initializing using a std::initializer_list, you might want to add that for your object pool, so that you could write something like:

ObjectPool<std::string> pool = {"foo", "bar", "baz", ...};

Set bogusIndex to std::numeric_limits<std::size_t>::max()

Even if you cannot think of a use case for an object pool of 65535 or more items now, consider that you might need it in the future, or someone else using your code might. If you are going to use a special value for index to indicate that an Item doesn't need to be released, give it a value that really can never be a valid index, like the maximum possible value for a std::size_t.

Use notify_one()

When you release an Item back to the pool, it doesn't make sense to wake up all threads that are waiting. Only one will be able to get the Item that was just released. So use notify_one() instead.

Consider supporting non-copyable value types

Since you store the objects in a std::vector, this requires T to be copy-assignable and copy-constructible. Consider storing them in some way that does not have this limitation, for example by using a std::deque instead.

Item's move constructor should std::move the object

If you are moving one Item into another, it makes sense to also use move-assignment on object. It should be as simple as:

object = std::move(other.object)

acquire() is an \$O(N)\$ operation

It is unfortunate that acquire() does a linear scan through inUse[]. It should be possible to turn this into an \$O(1)\$ operation. One possibility is to use a std::set to store the indices of the items that are in use, but while technically \$O(1)\$ amortized, that might involve a lot of unwanted allocations. There are other ways to keep track of this though.

\$\endgroup\$
3
  • \$\begingroup\$ Great. This is exactly the kind of feedback I was hoping for. I was paranoid about using notify_one but it certainly seems safe. I didn't know std::deque supported non-copyable types -- hmm. I wasn't worried about the linear access time, but speeding this up would allow other use cases. thanks! \$\endgroup\$
    – wcochran
    Jan 28 at 0:31
  • 1
    \$\begingroup\$ I did the std::unique_ptr mimicry, but I made move ctor and move assignment public so user can move them around. Return type not Item here:T* operator->() {return &object;}; Again ... thanks for the help there are great ideas. \$\endgroup\$
    – wcochran
    Jan 28 at 1:02
  • \$\begingroup\$ Ah yes, that should be T not Item. Making the move constructor and assignment operator public is indeed fine. \$\endgroup\$
    – G. Sliepen
    Jan 28 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.