Lock-free bounded stack atomics

Question

I was thinking about using very basic bounded (preallocated) stack to keep track of my threads IDs in correct LIFO order. I was wondering if my implementation is thread safe:

// we use maximum 8 workers
size_t idle_ids_stack[8];
// position current write happening at
std::atomic_uint_fast8_t idle_pos(0);

// this function is called by each thread when it is about to sleep
void register_idle(size_t thread_id) 
{
    std::atomic_thread_fence(std::memory_order_release);
    idle_ids_stack[idle_pos.fetch_add(1, std::memory_order_relaxed)] = thread_id;
}

// this function can be called from anywhere at anytime
void wakeup_one() 
{
    uint_fast8_t old_pos(idle_pos.load(std::memory_order_relaxed));
    std::atomic_thread_fence(std::memory_order_acquire);
    size_t id;
    do
    {
        if(old_pos == 0) return; // no idle threads in stack; exit;
        id = idle_ids_stack[old_pos-1];
    }
    while (!idle_pos.compare_exchange_weak(old_pos, old_pos-1, std::memory_order_acquire, std::memory_order_relaxed));
    // wakeup single thread
    signal_thread(id);
}

---

Please see latest changes: Gist

Answer 1

Problem 1

Consider that register_idle() is equivalent to this slightly rewritten version:

// this function is called by each thread when it is about to sleep
void register_idle(size_t thread_id) 
{
    std::atomic_thread_fence(std::memory_order_release);
    uint8_t pos = idle_pos.fetch_add(1, std::memory_order_relaxed);

    // What happens when this thread stops right here?

    idle_ids_stack[pos] = thread_id;
}

If the thread stops after incrementing idle_pos, but before writing the actual thread id to the stack, you will be in trouble when another thread tries to wake up the thread at the top of stack. It will try to read a thread id from the stack that has not yet been written.

Problem 2

(Credit @MikeMB for correcting me on my previous answer)

You have a problem in wakeup_one() as well. Suppose idle_pos is 2 and idle_ids_stack[1] is 5. Now consider the following sequence of events:

1. Thread 1 runs wakeup_one() and executes id = idle_ids_stack[old_pos-1], so at this point, id is 5. But now thread 1 sleeps for a little while.
2. Thread 2 runs wakeup_one(), grabs the same id (5), and returns it, setting idle_pos to 1 in the process.
3. Thread 3 runs register_idle(), puts its id (3) into idle_ids_stack[1] and increments idle_pos back to 2.
4. Now thread 1 resumes, and compare-exchanges idle_pos from 2 to 1 successfully. But it returns id as 5 (a duplicate thread id), instead of 3 (the proper one).