I'm writing a data structure to solve a problem related to servicing hardware interrupts. I have to translate a 64-bit pointer to a 16-bit handle and back again. Unfortunately the hardware completions aren't guaranteed to be in order, and some conventional solutions like lock-free stacks cause a lot of contention as the workload can be quite bursty. I've created a concurrent handle class where: - Multiple threads can create handles, only one thread destroys. (MPSC) - Handles can be produced and destroyed "out of order". - Producer (Binding Handles) is lock-free. - Consumer (Reading and destroying handles) is wait-free for use in an IRQ context. - Iterate over active handles to handle stalled requests/debugging. This is a simplified version of my first attempt (optimisations and error handling removed). The core idea is to probe an array of atomic values until it finds a free slot, then try to claim it. I'm mostly wanting feedback on if the memory barriers are correct. ``` using Handle = uint16_t; struct HandleTable { HandleTable() { clear(); } ~HandleTable() { clear(); } // Tries to bind a pointer to a handle Handle try_bind(void* ptr) { // The virtual address is unique for a request in flight uintptr_t offset = hash(reinterpret_cast<uintptr_t>(ptr)); for(size_t i = 0; i < slots.size(); ++i) { size_t idx = (offset + i) % slots.size(); // Is the current slot occupied (should this be acquire?) // Producers don't touch this object after submitting void* current = slots[idx].load(std::memory_order_relaxed); if(current) { continue; } // Try to claim the slot // Synchronize with "acquire" in getter functions if(slots[idx].compare_exchange_strong(current, ptr, std::memory_order_release, std::memory_order_relaxed)) { return Handle(idx + 1); } } return Handle(0); } // Destroys a handle (called from IRQ) void release(Handle val) { // Does this need to be memory_order_release? // We don't need to synchronize non-atomic data here slots[val + 1].store(nullptr, std::memory_order_relaxed); } // Gets the pointer referred to by handle void* get(Handle val) { // Synchronize with "release" in setter return slots[val + 1].load(std::memory_order_acquire); } // Clears the handle table (not thread safe) void clear() { for(size_t i = 0; i < slots.size() ++i) { if(void* res = slots.load(std::memory_order_relaxed) { // Synchronise "release" from setter std::atomic_thread_fence(std::memory_order_acquire); // Do something with the dangling handle } } // Syncrhonise any changes before clearing the table std::atomic_thread_fence(std::memory_order_release); for(auto& val : slots) { val.store(nullptr, std::memory_order_relaxed); } } std::array<std::atomic<void*>, 1024> slots; };