atomic compare and conditionally subtract if less

Question

I manage some memory that is used by concurrent threads, and I have a variable

unsigned int freeBytes

When I request some memory from a task

unsigned int bytesNeeded

I must check if

bytesNeeded<=freeBytes

and if yes keep the old value of freeBytes and subtract atomically from freeBytes bytesNeeded.

Does the atomic library OR the x86 offers such possibilities ?

Answer 1

Use an atomic compare-and-swap operation. In pseudo-code:

do {
    unsigned int n = load(freeBytes);

    if (n < bytesNeeded) { return NOT_ENOUGH_MEMORY; }

    unsigned int new_n = n - bytesNeeded;

} while (!compare_and_swap(&freeBytes, n, new_n));

With real C++ <atomic> variables the actual could would look pretty similar:

#include <atomic>

// Global counter for the amount of available bytes
std::atomic<unsigned int> freeBytes;    // global

// attempt to decrement the counter by bytesNeeded; returns whether
// decrementing succeeded.
bool allocate(unsigned int bytesNeeded)
{
    for (unsigned int n = freeBytes.load(); ; )
    {
        if (n < bytesNeeded) { return false; }

        unsigned int new_n = n - bytesNeeded;

        if (freeBytes.compare_exchange_weak(n, new_n)) { return true; }
    }
}

(Note that the final compare_exchange_weak takes the first argument by reference and updates it with the current value of the atomic variable in the event that the exchange fails.)

By contrast, incrementing the value ("deallocate?) can be done with a simple atomic addition (unless you want to check for overflow). This is to some extent symptomatic of lock-free containers: Creating something is relatively easy, assuming infinite resources, but removing requires trying in a loop.