Make core::Pool lock-free

[gavv]

Last revised: Jun 2024

core::SlabPool implements slab pool. (Actual implementation is in core::SlabPoolImpl).

When an object is allocated, there are two main paths:

• hot path - object is available in free list (src)
• cold path - freelist is empty, we need to grow the pool (src)

Currently, both paths runs under a mutex. Hot path uses a doubly linked-list of free slots.

We should update pool so that hot path will not use mutex, and will use lock-free freelist instead.

This is important to prevent priority inversion problems, because shared pools are used by both realtime and non-realtime threads.

Steps:

• Add new class core::Freelist<T>. It should be modeled after core::List<T>. It should implement lock-free LIFO based on singly linked list, with just two operations: push_back() and pop_back(). It should be intrusive, just like core::List, i.e. elements should inherit node class, so that node data is embedded into element instead of being allocated separately.

  Extracted into subtask: #734

• Use it in core::SlabPoolImpl for the hot path.

This excellent article provides ABA-free implementation of lock-free freelist: Solving the ABA Problem for Lock-Free Free Lists

[Hassall]

can you assign it to me?

[gavv]

Sure, you're welcome

[Hassall]

@gavv

because shared pools are used by both realtime and non-realtime threads

are these long lived threads? I was thinking about a different approach where we could use thread_local storage which would avoid dealing with mutexes and atomics.

[gavv]

Hi,

I thought about TLS too, but there are several objections for it here:

• we don't control all threads that may access pools; some of the threads may belong to user of C library and we don't know anything about them

• one of the patterns of using pool is that network thread allocates buffers, and audio thread releases them; it means that even if you use TLS, you'll anyway need some lock-free logic on top of it to exchange data between threads, so this implementation would be more complicated

• TLS is not supported on all platforms that we'd like to target in future, e.g. not always available on Zephyr

Using TLS probably can be additional optimization enabled only for some use-cases / platforms, though I'm not sure we need it at current point.

[Hassall]

I'll try to have a PR out sometime this weekend.

[gavv]

Awesome, thanks

[Hassall]

hey @gavv, sorry for getting to this late.

elements should inherit node class, so that node data is embedded into element instead of being allocated separately.

Question:

The lock-free ABA solution leverages a tag (std::uint32_t). To avoid the FreeList class from making allocations separately, ListNode::ListNodaData would then need a new member (...or perhaps some hack to repurpose ListNode::ListNodeData.prev since it's not used in FreeList).

What are your thoughts?

(Another issue I thought I was going to run into was that none of the ListNode::ListNodeData members are of type std::atomic but it seems by using AtomicOps, I can perform atomic operations on any type)

[gavv]

I think we need a separate class for freelist nodes (FreelistNode), that will have whatever fields we need. Usually each intrusive container has its own base class for nodes.

We don't use std::atomic because we use C++98. We have two classes for atomics: core::AtomicOps and core::Atomic<T>. In this case, I think we need AtomicOps because it allows to control which memory order to use. Yes, it operates on regular types like int or pointer. You can take a look how it's done in core::MpscQueue.

[Hassall]

I think we need a separate class for freelist nodes (FreelistNode), that will have whatever fields we need. Usually each intrusive container has its own base class for nodes.

~I see. In that case we wouldn't be able to do an in-place swap of List with FreeList? Curious what the plan is on how to proceed once FreeList and FreeListNode classes are completed~.

I see we just need to make Slab and Slot inherit from FreeListNode.

[gavv]

I see we just need to make Slab and Slot inherit from FreeListNode.

Exactly

[gavv]

@Hassall Hi, do you still have plans on this?

[gavv]

Unassigning, so that someone could pick this up.