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	"internal/runtime/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 atomic.Int32 // number of pending readers
27	readerWait  atomic.Int32 // number of departing readers
28
29	readRank lockRank // semantic lock rank for read locking
30}
31
32// Lock ranking an rwmutex has two aspects:
33//
34// Semantic ranking: this rwmutex represents some higher level lock that
35// protects some resource (e.g., allocmLock protects creation of new Ms). The
36// read and write locks of that resource need to be represented in the lock
37// rank.
38//
39// Internal ranking: as an implementation detail, rwmutex uses two mutexes:
40// rLock and wLock. These have lock order requirements: wLock must be locked
41// before rLock. This also needs to be represented in the lock rank.
42//
43// Semantic ranking is represented by acquiring readRank during read lock and
44// writeRank during write lock.
45//
46// wLock is held for the duration of a write lock, so it uses writeRank
47// directly, both for semantic and internal ranking. rLock is only held
48// temporarily inside the rlock/lock methods, so it uses readRankInternal to
49// represent internal ranking. Semantic ranking is represented by a separate
50// acquire of readRank for the duration of a read lock.
51//
52// The lock ranking must document this ordering:
53//   - readRankInternal is a leaf lock.
54//   - readRank is taken before readRankInternal.
55//   - writeRank is taken before readRankInternal.
56//   - readRank is placed in the lock order wherever a read lock of this rwmutex
57//     belongs.
58//   - writeRank is placed in the lock order wherever a write lock of this
59//     rwmutex belongs.
60func (rw *rwmutex) init(readRank, readRankInternal, writeRank lockRank) {
61	rw.readRank = readRank
62
63	lockInit(&rw.rLock, readRankInternal)
64	lockInit(&rw.wLock, writeRank)
65}
66
67const rwmutexMaxReaders = 1 << 30
68
69// rlock locks rw for reading.
70func (rw *rwmutex) rlock() {
71	// The reader must not be allowed to lose its P or else other
72	// things blocking on the lock may consume all of the Ps and
73	// deadlock (issue #20903). Alternatively, we could drop the P
74	// while sleeping.
75	acquireLockRankAndM(rw.readRank)
76	lockWithRankMayAcquire(&rw.rLock, getLockRank(&rw.rLock))
77
78	if rw.readerCount.Add(1) < 0 {
79		// A writer is pending. Park on the reader queue.
80		systemstack(func() {
81			lock(&rw.rLock)
82			if rw.readerPass > 0 {
83				// Writer finished.
84				rw.readerPass -= 1
85				unlock(&rw.rLock)
86			} else {
87				// Queue this reader to be woken by
88				// the writer.
89				m := getg().m
90				m.schedlink = rw.readers
91				rw.readers.set(m)
92				unlock(&rw.rLock)
93				notesleep(&m.park)
94				noteclear(&m.park)
95			}
96		})
97	}
98}
99
100// runlock undoes a single rlock call on rw.
101func (rw *rwmutex) runlock() {
102	if r := rw.readerCount.Add(-1); r < 0 {
103		if r+1 == 0 || r+1 == -rwmutexMaxReaders {
104			throw("runlock of unlocked rwmutex")
105		}
106		// A writer is pending.
107		if rw.readerWait.Add(-1) == 0 {
108			// The last reader unblocks the writer.
109			lock(&rw.rLock)
110			w := rw.writer.ptr()
111			if w != nil {
112				notewakeup(&w.park)
113			}
114			unlock(&rw.rLock)
115		}
116	}
117	releaseLockRankAndM(rw.readRank)
118}
119
120// lock locks rw for writing.
121func (rw *rwmutex) lock() {
122	// Resolve competition with other writers and stick to our P.
123	lock(&rw.wLock)
124	m := getg().m
125	// Announce that there is a pending writer.
126	r := rw.readerCount.Add(-rwmutexMaxReaders) + rwmutexMaxReaders
127	// Wait for any active readers to complete.
128	lock(&rw.rLock)
129	if r != 0 && rw.readerWait.Add(r) != 0 {
130		// Wait for reader to wake us up.
131		systemstack(func() {
132			rw.writer.set(m)
133			unlock(&rw.rLock)
134			notesleep(&m.park)
135			noteclear(&m.park)
136		})
137	} else {
138		unlock(&rw.rLock)
139	}
140}
141
142// unlock unlocks rw for writing.
143func (rw *rwmutex) unlock() {
144	// Announce to readers that there is no active writer.
145	r := rw.readerCount.Add(rwmutexMaxReaders)
146	if r >= rwmutexMaxReaders {
147		throw("unlock of unlocked rwmutex")
148	}
149	// Unblock blocked readers.
150	lock(&rw.rLock)
151	for rw.readers.ptr() != nil {
152		reader := rw.readers.ptr()
153		rw.readers = reader.schedlink
154		reader.schedlink.set(nil)
155		notewakeup(&reader.park)
156		r -= 1
157	}
158	// If r > 0, there are pending readers that aren't on the
159	// queue. Tell them to skip waiting.
160	rw.readerPass += uint32(r)
161	unlock(&rw.rLock)
162	// Allow other writers to proceed.
163	unlock(&rw.wLock)
164}
165