Race detector compatible ring buffer Part II

[Cameron Elliott]

Ian, thank you very much for the suggestion to use atomics.
Unfortunately, for a standard SPSC ring buffer, I don't think it does the trick.


I am attaching a simple ring buffer program at the end.

If you run 'go run -race main.go' on the example,
a race will occur.
The race that occurs is a write, then read to the
same element of a slice on two different goroutines.

Of course a race-detected is expected.

This can be fixed by mutexing Put() and Get(),
because through some magic, mutexs affect the tables/tags
the race detector maintains in order to catch races.

Using sync.atomic on the ring buffer indexes doesn't
affect the race-detector state for read and writes.

I spent more time investigating, it seems there are
two ways to make a traditional ring buffer compatible
with the race detector:

1. Use build tags to conditionally Lock/Unlock mutexes
where you would not actually need them, in order to reset
the race detector on the object crossing goroutines.

2. Use the pragma //go:linkname to get access to the 'runtime.race'
functions, in order to call Enable()/Disable/ReleaseMerge/Aquire
as sync.Pool does in order to make the race detector happy.

If there are other methods, please let me know!
Thanks for any feedback!

Cameron/Seattle







package main

import (
        "sync/atomic"
        "time"
)

type RB struct {
    //mu sync.Mutex
        buf        []interface{}
        start, end int64
}


const N = 10

func NewRB() *RB {
        return &RB{buf: make([]interface{}, N)}
}

func (r *RB) Put(x interface{}) {
//    mu.Lock()
//    defer mu.Unlock()

        r.buf[r.end] = x
        atomic.AddInt64(&r.end,1)
        //r.end++
        r.end %= N

}

func (r *RB) Get() interface{} {
//    mu.Lock()
//    defer mu.Unlock()

        v := r.buf[r.start]
        atomic.AddInt64(&r.start,1)
        //r.start++
        r.start %= N

        return v
}

func main() {

        r := NewRB()

        go func() {
                r.Put(12345)
        }()

        time.Sleep(time.Millisecond)

        a := r.Get().(int)
        println(a)
}

[Axel Wagner]

You probably want to make the element type of the slice an atomic.Value, instead of an interface{}. You shouldn't need a mutex then.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/d7cc3410-c0bb-40d6-bf75-5e655ba3136en%40googlegroups.com.

[Axel Wagner]

Uhm, I just actually looked at the code.

You still use `r.start %= N`, which is a non-atomic access to r.start.

AIUI, SPSC stands for "single producer, single consumer", i.e. you know that Get and Put will only be called from a single goroutine, respectively? In that case, you wouldn't even need atomics to manipulate r.start/r.end. Of course, you can't have a guarantee that your ringbuffer does not overflow, that way.

But ISTM to make the conceptual code work with the race detector, you should use atomic.Values for the elements of the slice and then can use non-atomic accesses to r.start/r.end.

[Axel Wagner]

I found a lock-free ringbuffer implementation written in C, which seems to do what you want:

https://github.com/QuantumLeaps/lock-free-ring-buffer/blob/main/src/

This is a relatively direct translation to Go, using generics from go 1.18 (to be released very soon):

https://go.dev/play/p/nNEt66r71Yf?v=gotip

I tried running it with -race and got no complaints.

[Gregg Townsend]

Well, the suggested code passes the race detector, but shouldn't it also be *correct*?

Two concurrent calls of Put can load identical head and tail values and then store in the same slot.

See

https://go.dev/play/p/gagBCCj2n2g?v=gotip

for a demonstration.

[Ian Lance Taylor]

You are getting a warning from the race detector on your code because
your code is unsafe. Nothing ensures that the CPU running the Get
method will see the value stored by the CPU running the Put method.

You would need to use atomic operations also for storing and
retrieving the stored values. But then they couldn't have type
interface{}. So I don't know if there is a perfect solution here.

Ian

[Brian Candler]

On Friday, 11 March 2022 at 15:52:04 UTC Gregg Townsend wrote:

Two concurrent calls of Put can load identical head and tail values and then store in the same slot.

Correct, but that's not a valid way to use this code. See https://github.com/QuantumLeaps/lock-free-ring-buffer#lock-free-restrictions

"The ring buffer does not require any "locking" (mutual exclusion mechanism) as long as the following restrictions are met:

1. Only one thread/interrupt can produce data into the ring buffer
2. Only one thread/interrupt can consume data from the ring buffer

In other words, a given LFRB can be used only by one pair of producer/ consumer threads/interrupts. Fortunately, this is the most frequently encountered scenario."

[Ian Lance Taylor]

I haven't looked at the web page, but OK, I think that can work if the
memory loads and stores are correctly ordered, *provided* you take
steps to ensure that the goroutine stays on the same CPU core. By
default nothing guarantees that, and there is no portable way to
require it.

Ian

[Axel Wagner]

On Fri, Mar 11, 2022 at 4:51 PM Gregg Townsend <gtow...@gmail.com> wrote:

Well, the suggested code passes the race detector, but shouldn't it also be *correct*?

Two concurrent calls of Put can load identical head and tail values and then store in the same slot.

The premise is that there is a single consumer and a single producer (hence "SPSC").

The assumption was that OP specifically wanted something fitting that use-case.

If you have multiple producers/consumers, a buffered channel is obviously a better alternative.

 

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/900d07ba-ce11-4f1a-94d2-609b5b8260c7n%40googlegroups.com.

[Robert Engels]

“Usually” SPSC means it is optimized for that case but it doesn’t fail in case of multiple writers. It it usually easier to prevent multiple readers as the reader can be controlled during init and hidden. 

On Mar 11, 2022, at 4:41 PM, 'Axel Wagner' via golang-nuts <golan...@googlegroups.com> wrote:



To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfFmgxpJpj8zSpMWtnAK6qkkvzuR4%3DFUJriZF_Jku6PGDg%40mail.gmail.com.

[Robert Engels]

Btw, for those interesting in some neat highly optimized queue patterns check out https://lmax-exchange.github.io/disruptor/

On Mar 11, 2022, at 5:58 PM, Robert Engels <ren...@ix.netcom.com> wrote:



[Gregg Townsend]

Or the same demonstration without a very confusing overloaded identifier (sorry!):

https://go.dev/play/p/ChOkAyV8imA?v=gotip