Ringbuffers claims to be 1 element bigger

[amstan]

Let's say I want to create a ringbuffer of size 16, i pass 16 to jack_ringbuffer_create, the resulting struct's .size is 16. All is well, right? No, jack_ringbuffer_write will only let me write 15 items, as confirmed by jack_ringbuffer_write_space.

Allow me to demonstrate with a python wrapper:

>>> a=jack.RingBuffer(16)
>>> a.write_space
15
>>> # D: :(
>>> a.write(b"1"*16)
15
>>> a      
<jack.RingBuffer 15/16>
>>> a.write(b"1")
0
>>> a
<jack.RingBuffer 15/16>
>>> len(a.read(16))
15
>>> a
<jack.RingBuffer 0/16>
>>> a.size
16
>>> # What????

I understand this is an artifact on how the ringbuffer is stored, but i still think it's the wrong behavior.

jack_ringbuffer_create should perhaps allocate cnt+1 memory, .size should stay the same (should still match what the caller requested), and everywhere in the internal code .size+1 should be used.

[amstan]

Actually, I just noticed that jack_ringbuffer_create(15) still gives me a 16 sized array. So scratch my suggestions. So most of the time the behavior is correct, the caller gets a ringbuffer that's at least that size.

What seems to be broken here is the check for the next power of 2. If i want to store 16 items, 32 elements need to be allocated.

Though.. .size should still match whatever .write_space says when the buffer is empty.

[x42]

Yep, this is indeed intentional. The size is always rounded up to the next power of two (2^n memory can be aligned in memory and fits in pages, the modulo operation boils down to an "and", etc etc, 2^n+1 can't)

Since the use-case for lock-free ringbuffers is cross-thread communication, requesting a specific size down to the byte for the data to transfer makes no sense. Read and write operations are not in lock-step. If you know precisely hat you can always process 16 items before 16 more items are written you must have a lock somewhere to ensure that and in that case don't need a lock-free ringbuffer in the first place.

Long story short: the buffer just needs to be large enough, exact size does not matter.

[amstan]

Long story short: the buffer just needs to be large enough, exact size does not matter.

I'm OK with the buffer being a little larger than I requested. But for powers of 2 sizes you don't actually get that size, you get size-1, which is actually smaller.

[mgeier]

I think this is a matter of documentation. Alexandru's arguments make sense from a user's perspective, and Robin's arguments make sense from an efficiency (memory and CPU) standpoint.

I think it would be best to mention in the documentation that the size is rounded up to the next power of two (if it's not already), but there is always one byte less available to the user (as correctly shown by jack_ringbuffer_*_space()).

I think it would be really surprising if a user requests 16 bytes but 32 bytes are actually allocated.

[x42]

@mgeier yes, you're spot on.

[7890]

I just experienced the same effect. Creating a buffer of size 2^n indicates a write space of only 2^n -1 bytes, while ->size tells 2^n

To be absolutely sure to always get at least the requested size with the current ringbuffer implementation, 1 must be added to the request (in order to catch the next power of two). I.e. want size 8, will request 9, will get 15. This can be confusing, mentioning it in the docs seems reasonable.

[7890]

Documentation proposal for function jack_ringbuffer_t *jack_ringbuffer_create(size_t sz); in common/jack/ringbuffer.h

/**
 * Allocates a ringbuffer data structure of a specified size. The
 * caller must arrange for a call to jack_ringbuffer_free() to release
 * the memory associated with the ringbuffer.
 *
 * A caller will usually get a buffer that can hold AT LEAST the
 * requested size.
 *
 * The space available for read and write operations is the
 * smallest power of two greater or equal to sz, MINUS ONE.
 * Example: sz=5; smallest power of two greater or equal to sz: 2^3=8.
 * Usable: 2^3 - 1 = 7.
 *
 * The usable size is thus 2^n - 1 bytes.
 * The size_t size member from jack_ringbuffer_t indicates 2^n
 * (and not the space available for read and write which is one less).
 *
 * A case that needs special attention is if the buffer needs to hold
 * AT LEAST 2^n bytes:
 * The requested size sz must be > 2^n bytes to get 2^(n+1)-1 usable space.
 *
 * @param sz the ringbuffer size in bytes.
 *
 * @return a pointer to a new jack_ringbuffer_t, if successful; NULL
 * otherwise.
 */