A scalable lock-free channel

Here's my lock-free channel impl lfchan,

I didn't want to copy/paste the code here since it is multiple files.

I'm trying to get an idea of what can be improved or if there are any bugs in it.

chan.go

type innerChan struct {
    q       []aValue
    sendIdx uint32
    recvIdx uint32
    slen    uint32
    rlen    uint32
    die     uint32
}

// Chan is a lock free channel that supports concurrent channel operations.
type Chan struct {
    *innerChan
}

// New returns a new channel with the buffer set to 1
func New() Chan {
    return NewSize(1)
}

// NewSize creates a buffered channel, with minimum length of 1
func NewSize(sz int) Chan {
    if sz  0 {
        if ch.Len() == 0 {
            if !block {
                return nilValue, false
            }
            runtime.Gosched()
            continue
        }
        i := atomic.AddUint32(&ch.recvIdx, 1)
        if v, ok := ch.q[i%ln].SwapWithNil(); ok {
            atomic.AddUint32(&ch.rlen, 1)
            return v, true
        }
        if block {
            if i%250 == 0 {
                pause(1)
            }
        } else if cnt++; cnt == ln {
            break
        }
        runtime.Gosched()
    }
    return nilValue, false
}

Out of order bug

It appears that there could be a case where the items inserted into the channel can be read out of order. From reading your test code, it seems that you want to maintain a FIFO ordering, so I am guessing this is unwanted behavior. Here's the sequence of events that can trigger the behavior:

• Initially, sendIdx recvIdx are -1, and slen rlen are 0.

• Thread 1 calls Send, and atomically increments sendIdx to 0.

• Thread 1 is context switched out before filling in q[0].

• Thread 2 calls Send, and atomically increments sendIdx to 1.

• Thread 2 fills in ch.q[1] and atomically increments slen to 1.

• Thread 3 calls Recv, and sees that there is 1 element in the queue because slen - rlen = 1.

• Thread 3 atomically increments recvIdx to 0.

• Thread 3 tries to do a read from q[0] but finds that it was empty.

• Thread 3 atomically increments recvIdx to 1.

• Thread 3 reads from q[1] and find the value placed there by Thread 2.

• Thread 1 wakes up an inserts its element into q[0].

So at this point, the item added by Thread 2 in q[1] was read before the item added by Thread 1 in q[0], but it could be argued that Thread 2 inserted its element timewise before Thread 1 so that behavior might be OK. However:

• Thread 1 calls Send again, and inserts an element into q[2].

• Thread 3 calls Recv and reads the element from q[2].

• Thread 3 calls Recv and reads the element from q[0] (after wrapping around the queue once).

Now, it is clear that Thread 1 sent q[0] before q[2], but Thread 3 received q[2] before q[0], which is out of order.

StackExchange Code Review Q#124041, answer score: 3