1// Copyright 2017 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package runtime
6
7import (
8	"runtime/internal/atomic"
9)
10
11// This is a copy of sync/rwmutex.go rewritten to work in the runtime.
12
13// A rwmutex is a reader/writer mutual exclusion lock.
14// The lock can be held by an arbitrary number of readers or a single writer.
15// This is a variant of sync.RWMutex, for the runtime package.
16// Like mutex, rwmutex blocks the calling M.
17// It does not interact with the goroutine scheduler.
18type rwmutex struct {
19	rLock      mutex    // protects readers, readerPass, writer
20	readers    muintptr // list of pending readers
21	readerPass uint32   // number of pending readers to skip readers list
22
23	wLock  mutex    // serializes writers
24	writer muintptr // pending writer waiting for completing readers
25
26	readerCount uint32 // number of pending readers
27	readerWait  uint32 // number of departing readers
28}
29
30const rwmutexMaxReaders = 1 << 30
31
32// rlock locks rw for reading.
33func (rw *rwmutex) rlock() {
34	// The reader must not be allowed to lose its P or else other
35	// things blocking on the lock may consume all of the Ps and
36	// deadlock (issue #20903). Alternatively, we could drop the P
37	// while sleeping.
38	acquirem()
39	if int32(atomic.Xadd(&rw.readerCount, 1)) < 0 {
40		// A writer is pending. Park on the reader queue.
41		systemstack(func() {
42			lock(&rw.rLock)
43			if rw.readerPass > 0 {
44				// Writer finished.
45				rw.readerPass -= 1
46				unlock(&rw.rLock)
47			} else {
48				// Queue this reader to be woken by
49				// the writer.
50				m := getg().m
51				m.schedlink = rw.readers
52				rw.readers.set(m)
53				unlock(&rw.rLock)
54				notesleep(&m.park)
55				noteclear(&m.park)
56			}
57		})
58	}
59}
60
61// runlock undoes a single rlock call on rw.
62func (rw *rwmutex) runlock() {
63	if r := int32(atomic.Xadd(&rw.readerCount, -1)); r < 0 {
64		if r+1 == 0 || r+1 == -rwmutexMaxReaders {
65			throw("runlock of unlocked rwmutex")
66		}
67		// A writer is pending.
68		if atomic.Xadd(&rw.readerWait, -1) == 0 {
69			// The last reader unblocks the writer.
70			lock(&rw.rLock)
71			w := rw.writer.ptr()
72			if w != nil {
73				notewakeup(&w.park)
74			}
75			unlock(&rw.rLock)
76		}
77	}
78	releasem(getg().m)
79}
80
81// lock locks rw for writing.
82func (rw *rwmutex) lock() {
83	// Resolve competition with other writers and stick to our P.
84	lock(&rw.wLock)
85	m := getg().m
86	// Announce that there is a pending writer.
87	r := int32(atomic.Xadd(&rw.readerCount, -rwmutexMaxReaders)) + rwmutexMaxReaders
88	// Wait for any active readers to complete.
89	lock(&rw.rLock)
90	if r != 0 && atomic.Xadd(&rw.readerWait, r) != 0 {
91		// Wait for reader to wake us up.
92		systemstack(func() {
93			rw.writer.set(m)
94			unlock(&rw.rLock)
95			notesleep(&m.park)
96			noteclear(&m.park)
97		})
98	} else {
99		unlock(&rw.rLock)
100	}
101}
102
103// unlock unlocks rw for writing.
104func (rw *rwmutex) unlock() {
105	// Announce to readers that there is no active writer.
106	r := int32(atomic.Xadd(&rw.readerCount, rwmutexMaxReaders))
107	if r >= rwmutexMaxReaders {
108		throw("unlock of unlocked rwmutex")
109	}
110	// Unblock blocked readers.
111	lock(&rw.rLock)
112	for rw.readers.ptr() != nil {
113		reader := rw.readers.ptr()
114		rw.readers = reader.schedlink
115		reader.schedlink.set(nil)
116		notewakeup(&reader.park)
117		r -= 1
118	}
119	// If r > 0, there are pending readers that aren't on the
120	// queue. Tell them to skip waiting.
121	rw.readerPass += uint32(r)
122	unlock(&rw.rLock)
123	// Allow other writers to proceed.
124	unlock(&rw.wLock)
125}
126