Source file src/runtime/lock_spinbit.go
1 // Copyright 2024 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 //go:build !wasm 6 7 package runtime 8 9 import ( 10 "internal/goarch" 11 "internal/runtime/atomic" 12 "internal/runtime/gc" 13 "unsafe" 14 ) 15 16 // This implementation depends on OS-specific implementations of 17 // 18 // func semacreate(mp *m) 19 // Create a semaphore for mp, if it does not already have one. 20 // 21 // func semasleep(ns int64) int32 22 // If ns < 0, acquire m's semaphore and return 0. 23 // If ns >= 0, try to acquire m's semaphore for at most ns nanoseconds. 24 // Return 0 if the semaphore was acquired, -1 if interrupted or timed out. 25 // 26 // func semawakeup(mp *m) 27 // Wake up mp, which is or will soon be sleeping on its semaphore. 28 29 // The mutex state consists of four flags and a pointer. The flag at bit 0, 30 // mutexLocked, represents the lock itself. Bit 1, mutexSleeping, is a hint that 31 // the pointer is non-nil. The fast paths for locking and unlocking the mutex 32 // are based on atomic 8-bit swap operations on the low byte; bits 2 through 7 33 // are unused. 34 // 35 // Bit 8, mutexSpinning, is a try-lock that grants a waiting M permission to 36 // spin on the state word. Most other Ms must attempt to spend their time 37 // sleeping to reduce traffic on the cache line. This is the "spin bit" for 38 // which the implementation is named. (The anti-starvation mechanism also grants 39 // temporary permission for an M to spin.) 40 // 41 // Bit 9, mutexStackLocked, is a try-lock that grants an unlocking M permission 42 // to inspect the list of waiting Ms and to pop an M off of that stack. 43 // 44 // The upper bits hold a (partial) pointer to the M that most recently went to 45 // sleep. The sleeping Ms form a stack linked by their mWaitList.next fields. 46 // Because the fast paths use an 8-bit swap on the low byte of the state word, 47 // we'll need to reconstruct the full M pointer from the bits we have. Most Ms 48 // are allocated on the heap, and have a known alignment and base offset. (The 49 // offset is due to mallocgc's allocation headers.) The main program thread uses 50 // a static M value, m0. We check for m0 specifically and add a known offset 51 // otherwise. 52 53 const ( 54 active_spin = 4 // referenced in proc.go for sync.Mutex implementation 55 active_spin_cnt = 30 // referenced in proc.go for sync.Mutex implementation 56 ) 57 58 const ( 59 mutexLocked = 0x001 60 mutexSleeping = 0x002 61 mutexSpinning = 0x100 62 mutexStackLocked = 0x200 63 mutexMMask = 0x3FF 64 mutexMOffset = gc.MallocHeaderSize // alignment of heap-allocated Ms (those other than m0) 65 66 mutexActiveSpinCount = 4 67 mutexActiveSpinSize = 30 68 mutexPassiveSpinCount = 1 69 70 mutexTailWakePeriod = 16 71 72 // mutexMLocksDelta is the change in gp.m.locks for each lock/unlock of a 73 // mutex. The gp.m.locks field is shared with acquirem/releasem, and with 74 // other code that needs to disable preemption, which changes its value by 75 // 1. Using a different delta for mutex in particular lets us notice when 76 // the M is releasing its last mutex (so it can safely acquire another 77 // mutex, for profiling), even if the M has preemption disabled for other 78 // reasons. 79 mutexMLocksDelta = 16 80 ) 81 82 //go:nosplit 83 func key8(p *uintptr) *uint8 { 84 if goarch.BigEndian { 85 return &(*[8]uint8)(unsafe.Pointer(p))[goarch.PtrSize/1-1] 86 } 87 return &(*[8]uint8)(unsafe.Pointer(p))[0] 88 } 89 90 // mWaitList is part of the M struct, and holds the list of Ms that are waiting 91 // for a particular runtime.mutex. 92 // 93 // When an M is unable to immediately obtain a lock, it adds itself to the list 94 // of Ms waiting for the lock. It does that via this struct's next field, 95 // forming a singly-linked list with the mutex's key field pointing to the head 96 // of the list. 97 type mWaitList struct { 98 next muintptr // next m waiting for lock 99 startTicks int64 // when this m started waiting for the current lock holder, in cputicks 100 } 101 102 // lockVerifyMSize confirms that we can recreate the low bits of the M pointer. 103 func lockVerifyMSize() { 104 size := roundupsize(unsafe.Sizeof(mPadded{}), false) + gc.MallocHeaderSize 105 if size&mutexMMask != 0 { 106 print("M structure uses sizeclass ", size, "/", hex(size), " bytes; ", 107 "incompatible with mutex flag mask ", hex(mutexMMask), "\n") 108 throw("runtime.m memory alignment too small for spinbit mutex") 109 } 110 } 111 112 // mutexWaitListHead recovers a full muintptr that was missing its low bits. 113 // With the exception of the static m0 value, it requires allocating runtime.m 114 // values in a size class with a particular minimum alignment. The 2048-byte 115 // size class allows recovering the full muintptr value even after overwriting 116 // the low 11 bits with flags. We can use those 11 bits as 3 flags and an 117 // atomically-swapped byte. 118 // 119 //go:nosplit 120 func mutexWaitListHead(v uintptr) muintptr { 121 if highBits := v &^ mutexMMask; highBits == 0 { 122 return 0 123 } else if m0bits := muintptr(unsafe.Pointer(&m0)); highBits == uintptr(m0bits)&^mutexMMask { 124 return m0bits 125 } else { 126 return muintptr(highBits + mutexMOffset) 127 } 128 } 129 130 // mutexPreferLowLatency reports if this mutex prefers low latency at the risk 131 // of performance collapse. If so, we can allow all waiting threads to spin on 132 // the state word rather than go to sleep. 133 // 134 // TODO: We could have the waiting Ms each spin on their own private cache line, 135 // especially if we can put a bound on the on-CPU time that would consume. 136 // 137 // TODO: If there's a small set of mutex values with special requirements, they 138 // could make use of a more specialized lock2/unlock2 implementation. Otherwise, 139 // we're constrained to what we can fit within a single uintptr with no 140 // additional storage on the M for each lock held. 141 // 142 //go:nosplit 143 func mutexPreferLowLatency(l *mutex) bool { 144 switch l { 145 default: 146 return false 147 case &sched.lock: 148 // We often expect sched.lock to pass quickly between Ms in a way that 149 // each M has unique work to do: for instance when we stop-the-world 150 // (bringing each P to idle) or add new netpoller-triggered work to the 151 // global run queue. 152 return true 153 } 154 } 155 156 func mutexContended(l *mutex) bool { 157 return atomic.Loaduintptr(&l.key)&^mutexMMask != 0 158 } 159 160 func lock(l *mutex) { 161 lockWithRank(l, getLockRank(l)) 162 } 163 164 func lock2(l *mutex) { 165 gp := getg() 166 if gp.m.locks < 0 { 167 throw("runtime·lock: lock count") 168 } 169 gp.m.locks += mutexMLocksDelta 170 171 k8 := key8(&l.key) 172 173 // Speculative grab for lock. 174 v8 := atomic.Xchg8(k8, mutexLocked) 175 if v8&mutexLocked == 0 { 176 if v8&mutexSleeping != 0 { 177 atomic.Or8(k8, mutexSleeping) 178 } 179 return 180 } 181 semacreate(gp.m) 182 183 var startTime int64 184 // On uniprocessors, no point spinning. 185 // On multiprocessors, spin for mutexActiveSpinCount attempts. 186 spin := 0 187 if numCPUStartup > 1 { 188 spin = mutexActiveSpinCount 189 } 190 191 var weSpin, atTail, haveTimers bool 192 v := atomic.Loaduintptr(&l.key) 193 tryAcquire: 194 for i := 0; ; i++ { 195 if v&mutexLocked == 0 { 196 if weSpin { 197 next := (v &^ mutexSpinning) | mutexSleeping | mutexLocked 198 if next&^mutexMMask == 0 { 199 // The fast-path Xchg8 may have cleared mutexSleeping. Fix 200 // the hint so unlock2 knows when to use its slow path. 201 next = next &^ mutexSleeping 202 } 203 if atomic.Casuintptr(&l.key, v, next) { 204 gp.m.mLockProfile.end(startTime) 205 return 206 } 207 } else { 208 prev8 := atomic.Xchg8(k8, mutexLocked|mutexSleeping) 209 if prev8&mutexLocked == 0 { 210 gp.m.mLockProfile.end(startTime) 211 return 212 } 213 } 214 v = atomic.Loaduintptr(&l.key) 215 continue tryAcquire 216 } 217 218 if !weSpin && v&mutexSpinning == 0 && atomic.Casuintptr(&l.key, v, v|mutexSpinning) { 219 v |= mutexSpinning 220 weSpin = true 221 } 222 223 if weSpin || atTail || mutexPreferLowLatency(l) { 224 if i < spin { 225 procyield(mutexActiveSpinSize) 226 v = atomic.Loaduintptr(&l.key) 227 continue tryAcquire 228 } else if i < spin+mutexPassiveSpinCount { 229 osyield() // TODO: Consider removing this step. See https://go.dev/issue/69268. 230 v = atomic.Loaduintptr(&l.key) 231 continue tryAcquire 232 } 233 } 234 235 // Go to sleep 236 if v&mutexLocked == 0 { 237 throw("runtime·lock: sleeping while lock is available") 238 } 239 240 // Collect times for mutex profile (seen in unlock2 only via mWaitList), 241 // and for "/sync/mutex/wait/total:seconds" metric (to match). 242 if !haveTimers { 243 gp.m.mWaitList.startTicks = cputicks() 244 startTime = gp.m.mLockProfile.start() 245 haveTimers = true 246 } 247 // Store the current head of the list of sleeping Ms in our gp.m.mWaitList.next field 248 gp.m.mWaitList.next = mutexWaitListHead(v) 249 250 // Pack a (partial) pointer to this M with the current lock state bits 251 next := (uintptr(unsafe.Pointer(gp.m)) &^ mutexMMask) | v&mutexMMask | mutexSleeping 252 if weSpin { // If we were spinning, prepare to retire 253 next = next &^ mutexSpinning 254 } 255 256 if atomic.Casuintptr(&l.key, v, next) { 257 weSpin = false 258 // We've pushed ourselves onto the stack of waiters. Wait. 259 semasleep(-1) 260 atTail = gp.m.mWaitList.next == 0 // we were at risk of starving 261 i = 0 262 } 263 264 gp.m.mWaitList.next = 0 265 v = atomic.Loaduintptr(&l.key) 266 } 267 } 268 269 func unlock(l *mutex) { 270 unlockWithRank(l) 271 } 272 273 // We might not be holding a p in this code. 274 // 275 //go:nowritebarrier 276 func unlock2(l *mutex) { 277 gp := getg() 278 279 var prev8 uint8 280 var haveStackLock bool 281 var endTicks int64 282 if !mutexSampleContention() { 283 // Not collecting a sample for the contention profile, do the quick release 284 prev8 = atomic.Xchg8(key8(&l.key), 0) 285 } else { 286 // If there's contention, we'll sample it. Don't allow another 287 // lock2/unlock2 pair to finish before us and take our blame. Prevent 288 // that by trading for the stack lock with a CAS. 289 v := atomic.Loaduintptr(&l.key) 290 for { 291 if v&^mutexMMask == 0 || v&mutexStackLocked != 0 { 292 // No contention, or (stack lock unavailable) no way to calculate it 293 prev8 = atomic.Xchg8(key8(&l.key), 0) 294 endTicks = 0 295 break 296 } 297 298 // There's contention, the stack lock appeared to be available, and 299 // we'd like to collect a sample for the contention profile. 300 if endTicks == 0 { 301 // Read the time before releasing the lock. The profile will be 302 // strictly smaller than what other threads would see by timing 303 // their lock calls. 304 endTicks = cputicks() 305 } 306 next := (v | mutexStackLocked) &^ (mutexLocked | mutexSleeping) 307 if atomic.Casuintptr(&l.key, v, next) { 308 haveStackLock = true 309 prev8 = uint8(v) 310 // The fast path of lock2 may have cleared mutexSleeping. 311 // Restore it so we're sure to call unlock2Wake below. 312 prev8 |= mutexSleeping 313 break 314 } 315 v = atomic.Loaduintptr(&l.key) 316 } 317 } 318 if prev8&mutexLocked == 0 { 319 throw("unlock of unlocked lock") 320 } 321 322 if prev8&mutexSleeping != 0 { 323 unlock2Wake(l, haveStackLock, endTicks) 324 } 325 326 gp.m.mLockProfile.store() 327 gp.m.locks -= mutexMLocksDelta 328 if gp.m.locks < 0 { 329 throw("runtime·unlock: lock count") 330 } 331 if gp.m.locks == 0 && gp.preempt { // restore the preemption request in case we've cleared it in newstack 332 gp.stackguard0 = stackPreempt 333 } 334 } 335 336 // mutexSampleContention returns whether the current mutex operation should 337 // report any contention it discovers. 338 func mutexSampleContention() bool { 339 rate := atomic.Load64(&mutexprofilerate) 340 return rate > 0 && cheaprandu64()%rate == 0 341 } 342 343 // unlock2Wake updates the list of Ms waiting on l, waking an M if necessary. 344 // 345 //go:nowritebarrier 346 func unlock2Wake(l *mutex, haveStackLock bool, endTicks int64) { 347 v := atomic.Loaduintptr(&l.key) 348 349 // On occasion, seek out and wake the M at the bottom of the stack so it 350 // doesn't starve. 351 antiStarve := cheaprandn(mutexTailWakePeriod) == 0 352 353 if haveStackLock { 354 goto useStackLock 355 } 356 357 if !(antiStarve || // avoiding starvation may require a wake 358 v&mutexSpinning == 0 || // no spinners means we must wake 359 mutexPreferLowLatency(l)) { // prefer waiters be awake as much as possible 360 return 361 } 362 363 for { 364 if v&^mutexMMask == 0 || v&mutexStackLocked != 0 { 365 // No waiting Ms means nothing to do. 366 // 367 // If the stack lock is unavailable, its owner would make the same 368 // wake decisions that we would, so there's nothing for us to do. 369 // 370 // Although: This thread may have a different call stack, which 371 // would result in a different entry in the mutex contention profile 372 // (upon completion of go.dev/issue/66999). That could lead to weird 373 // results if a slow critical section ends but another thread 374 // quickly takes the lock, finishes its own critical section, 375 // releases the lock, and then grabs the stack lock. That quick 376 // thread would then take credit (blame) for the delay that this 377 // slow thread caused. The alternative is to have more expensive 378 // atomic operations (a CAS) on the critical path of unlock2. 379 return 380 } 381 // Other M's are waiting for the lock. 382 // Obtain the stack lock, and pop off an M. 383 next := v | mutexStackLocked 384 if atomic.Casuintptr(&l.key, v, next) { 385 break 386 } 387 v = atomic.Loaduintptr(&l.key) 388 } 389 390 // We own the mutexStackLocked flag. New Ms may push themselves onto the 391 // stack concurrently, but we're now the only thread that can remove or 392 // modify the Ms that are sleeping in the list. 393 useStackLock: 394 395 if endTicks != 0 { 396 // Find the M at the bottom of the stack of waiters, which has been 397 // asleep for the longest. Take the average of its wait time and the 398 // head M's wait time for the mutex contention profile, matching the 399 // estimate we do in semrelease1 (for sync.Mutex contention). 400 // 401 // We don't keep track of the tail node (we don't need it often), so do 402 // an O(N) walk on the list of sleeping Ms to find it. 403 head := mutexWaitListHead(v).ptr() 404 for node, n := head, 0; ; { 405 n++ 406 next := node.mWaitList.next.ptr() 407 if next == nil { 408 cycles := ((endTicks - head.mWaitList.startTicks) + (endTicks - node.mWaitList.startTicks)) / 2 409 node.mWaitList.startTicks = endTicks 410 head.mWaitList.startTicks = endTicks 411 getg().m.mLockProfile.recordUnlock(cycles * int64(n)) 412 break 413 } 414 node = next 415 } 416 } 417 418 var committed *m // If we choose an M within the stack, we've made a promise to wake it 419 for { 420 headM := v &^ mutexMMask 421 flags := v & (mutexMMask &^ mutexStackLocked) // preserve low bits, but release stack lock 422 423 mp := mutexWaitListHead(v).ptr() 424 wakem := committed 425 if committed == nil { 426 if v&mutexSpinning == 0 || mutexPreferLowLatency(l) { 427 wakem = mp 428 } 429 if antiStarve { 430 // Wake the M at the bottom of the stack of waiters. (This is 431 // O(N) with the number of waiters.) 432 wakem = mp 433 prev := mp 434 for { 435 next := wakem.mWaitList.next.ptr() 436 if next == nil { 437 break 438 } 439 prev, wakem = wakem, next 440 } 441 if wakem != mp { 442 committed = wakem 443 prev.mWaitList.next = wakem.mWaitList.next 444 // An M sets its own startTicks when it first goes to sleep. 445 // When an unlock operation is sampled for the mutex 446 // contention profile, it takes blame for the entire list of 447 // waiting Ms but only updates the startTicks value at the 448 // tail. Copy any updates to the next-oldest M. 449 prev.mWaitList.startTicks = wakem.mWaitList.startTicks 450 } 451 } 452 } 453 454 if wakem == mp { 455 headM = uintptr(mp.mWaitList.next) &^ mutexMMask 456 } 457 458 next := headM | flags 459 if atomic.Casuintptr(&l.key, v, next) { 460 if wakem != nil { 461 // Claimed an M. Wake it. 462 semawakeup(wakem) 463 } 464 return 465 } 466 467 v = atomic.Loaduintptr(&l.key) 468 } 469 } 470