3
\$\begingroup\$

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 < 1 {
        panic("sz < 1")
    }
    return Chan{&innerChan{
        q:       make([]aValue, sz),
        sendIdx: ^uint32(0),
        recvIdx: ^uint32(0),
    }}
}

// Send adds v to the buffer of the channel and returns true, if the channel is closed it returns false
func (ch Chan) Send(v interface{}, block bool) bool {
    if !block && ch.Len() == ch.Cap() {
        return false
    }
    ln, cnt := uint32(len(ch.q)), uint32(0)
    for !ch.Closed() {
        if ch.Len() == ch.Cap() {
            if !block {
                return false
            }
            runtime.Gosched()
            continue
        }
        i := atomic.AddUint32(&ch.sendIdx, 1)
        if ch.q[i%ln].CompareAndSwapIfNil(v) {
            atomic.AddUint32(&ch.slen, 1)
            return true
        }
        if block {
            if i%250 == 0 {
                pause(1)
            }
        } else if cnt++; cnt == ln {
            break
        }
        runtime.Gosched()
    }
    return false
}

// Recv blocks until a value is available and returns v, true, or if the channel is closed and
// the buffer is empty, it will return nil, false
func (ch Chan) Recv(block bool) (interface{}, bool) {
    if !block && ch.Len() == 0 { // fast path
        return nilValue, false
    }
    ln, cnt := uint32(len(ch.q)), uint32(0)
    for !ch.Closed() || ch.Len() > 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
}
\$\endgroup\$
2
\$\begingroup\$

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:

  1. Initially, sendIdx recvIdx are -1, and slen rlen are 0.
  2. Thread 1 calls Send, and atomically increments sendIdx to 0.
  3. Thread 1 is context switched out before filling in q[0].
  4. Thread 2 calls Send, and atomically increments sendIdx to 1.
  5. Thread 2 fills in ch.q[1] and atomically increments slen to 1.
  6. Thread 3 calls Recv, and sees that there is 1 element in the queue because slen - rlen = 1.
  7. Thread 3 atomically increments recvIdx to 0.
  8. Thread 3 tries to do a read from q[0] but finds that it was empty.
  9. Thread 3 atomically increments recvIdx to 1.
  10. Thread 3 reads from q[1] and find the value placed there by Thread 2.
  11. 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:

  1. Thread 1 calls Send again, and inserts an element into q[2].
  2. Thread 3 calls Recv and reads the element from q[2].
  3. 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.

\$\endgroup\$
  • \$\begingroup\$ recvIdx/sendIdx are initalized to ^uint32(0) which is uint(0) - 1, so the first call either Send or Recv would set them to 0 not 1. \$\endgroup\$ – OneOfOne Mar 28 '16 at 6:56
  • \$\begingroup\$ @OneOfOne Ok I fixed the answer to reflect that. But the out of order problem remains. \$\endgroup\$ – JS1 Mar 28 '16 at 8:46
  • \$\begingroup\$ I see it, although I can't reproduce it, any suggestions? \$\endgroup\$ – OneOfOne Mar 28 '16 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.