![]() ![]() An infinite while-loop is used instead of a do-while, to avoid * since calloc will align by the type size, which in this case * or equivelant, is that the memory should still be aligned, * The theory behind using calloc and not aligned_alloc "Can't use non-copyable, non-assignable, non-movable, or non-constructible type!" Static_assert(queue_size > 0, "Can't have a queue size || Struct alignas(CACHE_LINE_SIZE) circular_buffer_data * Both are accessed at the same time, so they are not seperated by padding. * Strucutre that contains the index mask, and the circular buffer. Uint8_t padding_bytes_1[CACHE_LINE_SIZE. Uint8_t padding_bytes_0[CACHE_LINE_SIZE. * that in low contention cases, they will be accessed together, and thus * together in the case mentioned previously. * padding to put them in differnet cache lines, since they are not accessed The data and the spin lock are seperated by * someone else has finished working with it. * to prevent the case where a producer/consumer may try work with an element before * Contention on the spin lock should be minimal, as it's only there * Access to the data is protected by a spin lock. * Structure that represents each node in the circular buffer. * atomic variable, so we must align the atomic variable instead.Ĭursor_data(const uint_fast32_t in_producer_cursor = 0,Ĭonst uint_fast32_t in_consumer_cursor = 0) * We don't directly align the struct because we need to use it as an * The cursors are held together because we'll only ever be accessing Lock_flag.store(false, std::memory_order_release) Should_yield_not_pause ? std::this_thread::yield() : HARDWARE_PAUSE() While (lock_flag.load(std::memory_order_relaxed)) If (!lock_flag.exchange(true, std::memory_order_acquire)) Void do_work_through_lock(const std::function functor) * conveiniently do something which will be protected by the lock. * A function that takes a void lambda function can be used to * Simple, efficient spin-lock implementation. * inbetween member variables if the variables are accessed seperatley. * The sub-types are all padded to fit within cache lines. * The type is intended to be light weight & portable. * Lockless, Multi-Producer, Multi-Consumer, Bounded Circular Queue type. #define HARDWARE_PAUSE() _builtin_ia32_pause() #define _ENABLE_ATOMIC_ALIGNMENT_FIX 1 // MSVC atomic alignment fix. * C++14 32bit Lockless Bounded Circular MPMC Queue type. SPDX-License-Identifier: GPL-2.0-or-later Here's the full source, with many Doxygen style comments removed for clarity. Or the opposite case, where a producer tries to add some data before a consumer has finished reading it. This is to prevent the case where a consumer may try to read some data before a producer has finished putting it in. While the cursors maybe be protected by a CAS operation, each node on the buffer is protected by a spin-lock. For this to work the queue size must be a power of two, so the size specified by the user is raised up to the next power of two. In order to calculate the index on the buffer, an index-mask is used which will be one less than a power of two because we can use a bitwise-and instead of modulo to have the index wrap back to zero. When the CAS succeeds, the data can be put into or removed from the buffer. If either of the cursors has changed in the interim, the CAS will fail and another attempt is made. Once the cursors have been loaded, a fullness/emptiness check is performed before a CAS on the object holding both cursors. This is intended to ensure true-sharing of access to the cursors because they are never loaded individually. When a producer/consumer wishes to increment their respective cursor, both cursors are loaded at the same time, as they are both contained within an aligned structure. And it still uses two cursors which indicate to the next producer/consumer which index on the buffer they should be working with. I'm still using a bounded circular buffer to store/load the data. The new queue is 32bit and is intended to be portable and light-weight Bounded Circular Buffer & Two Cursors So this is an updated version, created using the feedback I got in the previous thread. Some people pointed out some fundamental errors I had made, and I came to learn that I was very naive when it comes to how I was padding variables. This is a follow-up to a previous question of mine, where I presented another queue of the same type to get some feedback on it. ![]()
0 Comments
Leave a Reply. |