CODEWITHSUNDEEP
c++concurrencyatomiclock-freewait-free
plasmacel
plasmacel

Reputation: 8530

Improving lock-free linear allocation to be wait-free

Given the following simple lock-free linear allocation algorithm I made:

bool allocate(size_type size, size_type& offset)
{
    size_type pos;
    size_type new_pos;
    
    pos = m_pos.load(std::memory_order_acquire);

    do
    {
        new_pos = pos + size;

        if (new_pos > m_end)
            return false;
    }
    while (!m_pos.compare_exchange_weak(pos, new_pos, std::memory_order_acq_rel, std::memory_order_acquire));

    offset = pos;
    return true;
}

I would like to improve it further to be wait-free on the fast path, discarding the CAS-loop completely and preferably using fetch_add, however I'm not sure how to handle the case when the allocation fails because the the requested size is greater than the available size - when this is detected the fetch_add is already incremented the position which is now over the valid range which may be simultaneously loaded by other threads, which would increment it further and have the false illusion that there is no space for the allocation. Some kind of spin-wait loop is still required in this path, however I can't come up with a valid solution.

Any idea?

Upvotes: 2

Views: 375

Answers (1)

Mascarpone
Mascarpone

Reputation: 2556

Let's say we have 256MB of space. The first thread tries to allocate 257MB of space, which obviously returns false.

To handle that, you can store two ints:

  • One atomic, with current_pos
  • One non atomic, with capacity

then:


// first attempt, atomic load current_pos
// to early exit when the allocation would certainly fail,
// which will reduce wasting memory

current := atomic_load(current_pos)
if ( current + required > capacity) { return error }

// second attempt, atomic fetch_and_add current_pos
// it can still fail, since other threads may advanced current_pos
// in the background since the previous load

current := fetch_and_add(current_pos, required)
if ( current + required > capacity) {return error}

This is wait free, and can handle OOM errors.

Upvotes: 1

Related Questions