jnk0le / ring-buffer

simple C++11 ring buffer implementation, allocated and evaluated at compile time

Ring Buffer

• pure C++11, no OS dependency
• lock and wait free bounded SPSC operation
• no exceptions, RTTI, virtual functions and dynamic memory allocation
• designed for compile time (static) allocation and type evaluation
• no wasted slots (in powers of 2 granularity)
• underrun and overrun checks in insert/remove functions
• highly efficient on most microcontroller architectures (nearly equal performance as in 'wasted-slot' implemetation)

notes

• index_t of size less than architecture reg size (size_t) might not be most efficient (known gcc bug)
• Only lamda expressions or functor callbacks can be inlined into buffWrite/buffRead functions
• 8 bit architectures are not supported in master branch at the moment. Broken code is likely to be generated
• relaxed atomic stores on RISC-V gcc port may be inefficient
• the DEC Alpha ultra-weak memory model is not supported

example

jnk0le::Ringbuffer<const char*, 256> message;

int main()
{
	//...
	while(1)
	{
		const char* tmp = nullptr;
		while(!message.remove(tmp));
		printf("%s fired\n", tmp);
		//...
	}
}

extern "C" void SysTick_Handler(void)
{
	message.insert("SysTick_Handler");
}

ring-buffer's Issues

unncessary void in parameter list

Hi,
some functions have a void parameter instead of an empty parameter list.

Ring-Buffer/ringbuffer.hpp

Line 52 in dade967

void producerClear(void) {

How to use for multi-consumer multi-producer

If I want a ring-buffer for the multi-producer multi-consumer case, and I protect access to the buffer with a mutex, am I correct that fake_tso should be true in the constructor and otherwise the defaults are correct?

Perhaps add this to the readme? I saw someone else asked about an exception in the MPMC case.

Thanks!

Add template parameter to make it a overwriting ring buffer

Hi,

how about adding a template parameter which makes it an overwriting ring buffer?
I.e. when buffer is full, calling insert() replaces the oldest value with the new value. Then the tail also has to be updated, which means the ring buffer cannot be lock free anymore.

I really like your implementation and this addition would make it even more generalized.

Generalize ring buffer, differentiate between atomic ring buffer non-atomic ring buffer

Hi,

as I understand your ring buffer is targeted for embedded systems, which is exactly what I am using it for.

I think it can be even more generalized, by adding a template option to omit any synchronization and atomicity guarantees for the case that the ringbuffer is not shared between user and interrupt context.

The impact on the generated instructions might be negligible currently, but if PR #9 were implemented, it would make a difference as one would not have to use locks / disable interrupts.

If this ring buffer would provide both an atomic and a non-atomic version, one could truly use it for all usecases 👍
(unless you need a stack :D)

sometimes stuck on isempty function and cache padding

again, thank you very much for your effort and sharing. In my tests sometimes isEmpty function consumes too much time (30-50 ms) which is too much for a lock-free queue. Other is a question is there a reason why you dont use cache padding to avoid head-tail ping pong in cache ?

thanks

As in the description, this is for embedded targents, can I use it for x86 PC?

Well, I know this may be a silly question.... I just want to make sure if I need to pay attention to something.

警告 C26495

警告 C26495 未初始化变量 jnk0le::Ringbuffer<char const *,256,0,0,unsigned __int64>::data_buff。始终初始化成员变量(type.6)。

const consumerClear producerClear compile errors

having const { on these functions produces an incorrect function resolution of <index_t, false> for store

/Users/smallville7123/Desktop/AAudioTrack/AAudioTrack2/src/main/cpp/ardour/Backends/../AudioEngine/../../smallville7123/plugins/../../ringbuffer/ringbuffer.hpp:62:10: error: no matching member function for call to 'store'
                                  tail.store(head.load(std::memory_order_relaxed), std::memory_order_relaxed);
                                  ~~~~~^~~~~
  /Users/smallville7123/Desktop/AAudioTrack/AAudioTrack2/src/main/cpp/ardour/Backends/../AudioEngine/../../smallville7123/plugins/../PianoRoll.h:35:24: note: in instantiation of member function 'jnk0le::Ringbuffer<std::__ndk1::pair<unsigned long long, bool>, 1048576, false, 0, unsigned int>::consumerClear' requested here
          this->noteData.consumerClear();
                         ^
  /Users/smallville7123/Library/Android/sdk/ndk/21.1.6352462/toolchains/llvm/prebuilt/darwin-x86_64/sysroot/usr/include/c++/v1/atomic:1473:10: note: candidate function not viable: no known conversion from 'const std::atomic<unsigned int>' to 'volatile std::__ndk1::__atomic_base<unsigned int, false>' for object argument
      void store(_Tp __d, memory_order __m = memory_order_seq_cst) volatile _NOEXCEPT
           ^
  /Users/smallville7123/Library/Android/sdk/ndk/21.1.6352462/toolchains/llvm/prebuilt/darwin-x86_64/sysroot/usr/include/c++/v1/atomic:1477:10: note: candidate function not viable: no known conversion from 'const std::atomic<unsigned int>' to 'std::__ndk1::__atomic_base<unsigned int, false>' for object argument
      void store(_Tp __d, memory_order __m = memory_order_seq_cst) _NOEXCEPT
           ^
  1 warning and 1 error generated.

removing const resolves this and allows the store to be resolved correctly

			/*!
			 * \brief Clear buffer from producer side
			 */
			void producerClear(void) {
				//this may fail
				head.store(tail.load(std::memory_order_relaxed), std::memory_order_relaxed);
			}

			/*!
			 * \brief Clear buffer from consumer side
			 */
			void consumerClear(void) {
				tail.store(head.load(std::memory_order_relaxed), std::memory_order_relaxed);
			}

readBuff(T*, size_t) never actually reads

Thank you for making this nice implementation!
I tried to use it in a project and discovered that there is small issue in the implementation of readBuff(T*, size_t) — the head is used instead of tail. This always results in available being 0 and thus the read is never performed.

Ring-Buffer/ringbuffer.hpp

Line 426 in 757b4f5

index_t tmp_tail = head;

I believe the fix is too small for making a fork, but I can do it if you want.

Thanks!

Add find function

Could you add find function by self-defined find expression?

isnt std::atomic_thread_fence more appropriate ?

Great ring buffer implementation but let me ask that, why you used std::atomic_signal_fence ?

"no wasted slots" is only true if you need power of 2 size

Assuming you need 10 slots in the ring-buffer, your implementation will waste 6 slots to be at a power of 2 while the traditional one will only waste only one slot.

This might be a deal-breaker on resource restricted device as such I would change the description from

• pure C++11, no OS dependency
• no exceptions, RTTI, virtual functions and dynamic memory allocation
• designed for compile time (static) allocation and type evaluation
• no wasted slots
• lock and wait free SPSC operation
• underrun and overrun checks in insert/remove functions
• highly efficient on most microcontroller architectures (nearly equal performance as in 'wasted-slot' implemetation)

to

• pure C++11, no OS dependency
• no exceptions, RTTI, virtual functions and dynamic memory allocation
• designed for compile time (static) allocation and type evaluation
• no wasted slots if you use power of 2 sizes
• lock and wait free SPSC operation
• underrun and overrun checks in insert/remove functions
• highly efficient on most microcontroller architectures (nearly equal performance as in 'wasted-slot' implemetation)

Add way to remove arbitrary element

Yeah, it's O(n) and will need to be protected with mutexes, but still useful when it's a rare case...

add support for non trivial objects

should use move mechanic or put another static assert

peek() is not right

shouldn't it be return &data_buff[tmp_tail & buffer_mask]; instead of return &data_buff[tmp_tail];, because head and tail keep growing, which may exceed the array boundary.

There is a compiling error in Visual Studio 2015 on Windows 7

Hello, jnk0le

While I try to use your ringbuffer.hpp, I got this following compiling error:

1>------ Rebuild All started: Project: xxxdump, Configuration: Debug Win32 ------ 1> main.cpp 1> ....................\ringbuffer.hpp(338): error C2675: unary '!': 'const index_t' does not define this operator or a conversion to a type acceptable to the predefined operator 1> ....................\ringbuffer.hpp(346): note: see reference to class template instantiation 'Ringbuffer<T,buffer_size,wmo_multi_core,cacheline_size,index_t>' being compiled ========== Rebuild All: 0 succeeded, 1 failed, 0 skipped ==========

alignas(0) causes gcc warnings

warning: requested alignment '0' is not a positive power of 2 [-Wattributes]

according to the c++11 standard zero alignment should be ignored.

"— if the constant expression evaluates to zero, the alignment specifier shall have no effect"

Does this ringbuffer thread safe?

Hi, here is a question about data racing.

Ring-Buffer/ringbuffer.hpp

Line 352 in e93d9af

size_t Ringbuffer<T, buffer_size, fake_tso, cacheline_size, index_t>::writeBuff(const T* buff, size_t count)

Assuming we have two threads to write buffer, how do you avoid data racing if two threads writing buffer at the same time ? I don't think the function above could handle the issue.

Multiple producers, a single consumer situation will produce a crash

#include "memory"
#include "thread"
#include "iostream"
#include "RingBuffer.hpp"
#include "vector"
#include "sstream"

struct ProfileInfo {
std::string device_id_;
std::shared_ptr<std::vector<std::tuple<double, double>>> points_;
};

utility::Ringbuffer<std::shared_ptr> buffer_;

void Consumer(void) {
while (true){

    std::shared_ptr<ProfileInfo> tempPtr;
    const bool readResult = buffer_.remove(tempPtr);
    if (!readResult) {
        continue;
    }
    std::cout << tempPtr->device_id_ << std::endl;
    std::this_thread::sleep_for(std::chrono::milliseconds(1));
}

}

void Producer() {
while (true) {

    std::shared_ptr<ProfileInfo> tempPtr =
        std::make_shared<ProfileInfo>();
    std::ostringstream os;
    os << std::this_thread::get_id();  
    tempPtr->device_id_ = os.str();
    const bool insertResult = buffer_.insert(tempPtr);
    std::this_thread::sleep_for(std::chrono::milliseconds(2));

}

}

int main() {

std::thread producer1(Producer);
std::thread producer2(Producer);
std::thread consumer(Consumer);
producer1.join();
producer2.join();
consumer.join();
return 0;

}

Implement iterator

It would be nice to have an iterator interface on the RingBuffer, then you can use the STL algorithms on the RingBuffer.
All required for that is a begin and end method returning the iterators.
You could then, for instance, sum up the values in the BufferEasily using std::accumulate.