Linux 5.10 Will Have a Fully Lock-Less Ring Buffer

https://linuxreviews.org/Linux_5.10_Will_Have_A_Fully_Lock-Less_Ring_Buffer

by wailin • 6 years ago

33 6 6 years ago

cmonfeat• 6 years ago

Anyone have a ELI5 version of the architecture of lockless buffer? I'm trying to wrap my head around how something like this can operate without locks and I just can't grock it.

sgtnoodle• 6 years ago

I'm not familiar with the Linux ring buffer specifically. It is presumably a multiple producer single or multiple consumer circular buffer, though.

Single producer single consumer circular buffers can be made pretty easily without locks. The producer writes to the buffer then atomically increments the head pointer. The consumer reads the buffer and then atomically increments the tail pointer.

Multiple producers get tricky without locking because they need to coordinate with each other enough to not write over the same part of the buffer. This can still be done via atomically incrementing a head pointer, though. The trick is that the increment has to happen before writing to the buffer rather than after. The buffer therefore needs to have a marker in it to indicate that it's ready to be read. A producer allocates the buffer with the atomic increment, writes it's data at it's leasure, then marks it ready to be read. The consumer looks at both the head pointer and the markers to tell how much data can be read.

Multiple consumers can be implemented by simply maintaining a tail pointer for each consumer. In order to be truly lock free, though, producers can't be blocked by slow consumers. Instead, producers simply write as fast as they want, and consumers do their best to keep up. A consumer can detect when it falls too far behind if you use counters rather than pointers or indexes; rather than wrapping around on increment, you wrap around on access to the circular buffer. That way, you can tell when you've fallen behind when your counter is more than the buffer size behind the head counter. You can either use 64 bit counters and never worry about roll over, or you can use a smaller data type for the counter and then size your buffer to be a power of two so that integer rollover doesn't cause a discontinuity.

dsamarin• 6 years ago

How will these Linux developers know that it is lock free without any race conditions?

guenthert• 6 years ago

Que? It is claimed to be lock free, not race condition free (now if it weren't also race condition free, no one would care). In the absence of locks it is lock-free. Not sure, what you were asking.

nextaccountic• 6 years ago

It uses synchronization primitives, just not locking.

rurban• 6 years ago

Looks not yet fully yet, maybe for 5.11.

"The access is still serialized by logbuf_lock. It synchronizes few more operations, for example, temporary buffer for formatting the message, syslog and kmsg_dump operations. The lock removal is being discussed and should be ready for the next release."

So I'll rather prefer to skip the halfway lockfree 5.10. looks deadlock-problematic to me.

Linux 5.10 Will Have a Fully Lock-Less Ring Buffer

Related Stories