rwmutex.go

     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  
     5  package runtime
     6  
     7  import (
     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.
    18  type 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.
    60  func (rw *rwmutex) init(readRank, readRankInternal, writeRank lockRank) {
    61  	rw.readRank = readRank
    62  
    63  	lockInit(&rw.rLock, readRankInternal)
    64  	lockInit(&rw.wLock, writeRank)
    65  }
    66  
    67  const rwmutexMaxReaders = 1 << 30
    68  
    69  // rlock locks rw for reading.
    70  func (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.
   101  func (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.
   121  func (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.
   143  func (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
View as plain text