为什么基于通道的锁定块？

Question

Hi i'm writing a Lock using channel, which aims to Lock/Unlock an operation for a given 'app'.

The general idea is that, one goroutine keeps listening on two channels: lockCh and unlockCh. Any Lock() operation sends a self-made channel to lockCh, and waits for reading from that self-made channel, done from reading this channel means Lock() succeed.

Similar process applies to Unlock().

To the listener gorouting, it checks if an 'app' is already locked when accepting a Lock(), if so, it puts that self-made channel to the tail of waiters-list. If somebody Unlock(), it wakes up (by sending message to channel) next waiter or delete the waiters-list if nobody else is waiting for the lock.

Code is put at below, I don't know where is wrong but the test cases just don't pass (it blocks after several Lock() and Unlock()!)

Thanks for giving me some advice.

type receiver struct {
            app  string
            ch   chan struct{}
            next *receiver
}

type receiveList struct {
            head *receiver
            tail *receiver
}

type AppLock struct {
            lockCh   chan receiver
            unlockCh chan receiver

            // Consider lock x:
            // if map[x] doesn't exist, x is unlocked
            // if map[x] exist but head is nil, x is locked but no waiter
            // if map[x] exist and head isn't nil, x is locked and there're waiters
            m map[string]receiveList
}

func NewAppLock() *AppLock {
            l := new(AppLock)
            l.lockCh = make(chan receiver)
            l.unlockCh = make(chan receiver)
            l.m = make(map[string]receiveList)

            go l.lockRoutine()
            return l
}

func (l *AppLock) Lock(app string) {
            ch := make(chan struct{})
            l.lockCh <- receiver{
                app: app,
                ch:  ch,
            }
            <-ch
}

func (l *AppLock) Unlock(app string) {
            ch := make(chan struct{})
            l.unlockCh <- receiver{
                app: app,
                ch:  ch,
            }
            <-ch
}

func (l *AppLock) lockRoutine() {
            for {
                select {
                case r := <-l.lockCh:
                    rlist, ok := l.m[r.app]
                    if ok { // already locked
                        if rlist.head == nil { // no waiter
                            rlist.head = &r
                            rlist.tail = &r
                        } else { // there're waiters, wait in queue
                            rlist.tail.next = &r
                            rlist.tail = &r
                        }
                    } else { // unlocked
                        rlist = receiveList{}
                        l.m[r.app] = rlist
                        r.ch <- struct{}{}
                    }
                case r := <-l.unlockCh:
                    rlist, ok := l.m[r.app]
                    if ok {
                        if rlist.head == nil { // no waiter
                            delete(l.m, r.app)
                            r.ch <- struct{}{}
                        } else { // there're waiters
                            candidate := rlist.head
                            if rlist.head == rlist.tail {
                                rlist.head = nil
                                rlist.tail = nil
                            } else {
                                rlist.head = rlist.head.next
                            }
                            candidate.ch <- struct{}{}
                            r.ch <- struct{}{}
                        }
                    } else {
                        panic("AppLock: inconsistent lock state")
                    }
                }
            }
}

Test:

func main() {
        app := "APP"
        appLock := NewAppLock()
        c := make(chan bool)

        for i := 0; i < 10; i++ {
            go func(l *AppLock, loops int, cdone chan bool) {
                for i := 0; i < loops; i++ {
                    l.Lock(app)
                    l.Unlock(app)
                }
                cdone <- true
            }(appLock, 1, c)
        }

        for i := 0; i < 10; i++ {
            <-c
        }

    fmt.Println("DONE")
}

Answer 1

I just found the mistake in my code.

type AppLock struct {
    lockCh   chan receiver
    unlockCh chan receiver

    // Consider lock x:
    // if map[x] doesn't exist, x is unlocked
    // if map[x] exist but head is nil, x is locked but no waiter
    // if map[x] exist and head isn't nil, x is locked and there're waiters
    m map[string]receiveList
}

Originally, I thought head and tail inside receiveList are all pointers, so we can always operate on the same waiters-list even though the receiveList isn't a Pointer type. (Obviously it's wrong)

Indeed, it's okay if we only read from head and tail without using Pointer type for receiveList. However, I do write to them inside the lockRoutine, which is writing to a copy of them. That's the problem.