Source file src/runtime/mspanset.go
1 // Copyright 2020 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/cpu" 9 "internal/goarch" 10 "internal/runtime/atomic" 11 "unsafe" 12 ) 13 14 // A spanSet is a set of *mspans. 15 // 16 // spanSet is safe for concurrent push and pop operations. 17 type spanSet struct { 18 // A spanSet is a two-level data structure consisting of a 19 // growable spine that points to fixed-sized blocks. The spine 20 // can be accessed without locks, but adding a block or 21 // growing it requires taking the spine lock. 22 // 23 // Because each mspan covers at least 8K of heap and takes at 24 // most 8 bytes in the spanSet, the growth of the spine is 25 // quite limited. 26 // 27 // The spine and all blocks are allocated off-heap, which 28 // allows this to be used in the memory manager and avoids the 29 // need for write barriers on all of these. spanSetBlocks are 30 // managed in a pool, though never freed back to the operating 31 // system. We never release spine memory because there could be 32 // concurrent lock-free access and we're likely to reuse it 33 // anyway. (In principle, we could do this during STW.) 34 35 spineLock mutex 36 spine atomicSpanSetSpinePointer // *[N]atomic.Pointer[spanSetBlock] 37 spineLen atomic.Uintptr // Spine array length 38 spineCap uintptr // Spine array cap, accessed under spineLock 39 40 // index is the head and tail of the spanSet in a single field. 41 // The head and the tail both represent an index into the logical 42 // concatenation of all blocks, with the head always behind or 43 // equal to the tail (indicating an empty set). This field is 44 // always accessed atomically. 45 // 46 // The head and the tail are only 32 bits wide, which means we 47 // can only support up to 2^32 pushes before a reset. If every 48 // span in the heap were stored in this set, and each span were 49 // the minimum size (1 runtime page, 8 KiB), then roughly the 50 // smallest heap which would be unrepresentable is 32 TiB in size. 51 index atomicHeadTailIndex 52 } 53 54 const ( 55 spanSetBlockEntries = 512 // 4KB on 64-bit 56 spanSetInitSpineCap = 256 // Enough for 1GB heap on 64-bit 57 ) 58 59 type spanSetBlockHeader struct { 60 // Free spanSetBlocks are managed via a lock-free stack. 61 lfnode 62 63 // popped is the number of pop operations that have occurred on 64 // this block. This number is used to help determine when a block 65 // may be safely recycled. 66 popped atomic.Uint32 67 } 68 69 type spanSetBlockHeader2 struct { 70 spanSetBlockHeader 71 pad [tagAlign - unsafe.Sizeof(spanSetBlockHeader{})]byte 72 } 73 74 type spanSetBlock struct { 75 spanSetBlockHeader2 76 77 // spans is the set of spans in this block. 78 spans [spanSetBlockEntries]atomicMSpanPointer 79 } 80 81 // push adds span s to buffer b. push is safe to call concurrently 82 // with other push and pop operations. 83 func (b *spanSet) push(s *mspan) { 84 // Obtain our slot. 85 cursor := uintptr(b.index.incTail().tail() - 1) 86 top, bottom := cursor/spanSetBlockEntries, cursor%spanSetBlockEntries 87 88 // Do we need to add a block? 89 spineLen := b.spineLen.Load() 90 var block *spanSetBlock 91 retry: 92 if top < spineLen { 93 block = b.spine.Load().lookup(top).Load() 94 } else { 95 // Add a new block to the spine, potentially growing 96 // the spine. 97 lock(&b.spineLock) 98 // spineLen cannot change until we release the lock, 99 // but may have changed while we were waiting. 100 spineLen = b.spineLen.Load() 101 if top < spineLen { 102 unlock(&b.spineLock) 103 goto retry 104 } 105 106 spine := b.spine.Load() 107 if spineLen == b.spineCap { 108 // Grow the spine. 109 newCap := b.spineCap * 2 110 if newCap == 0 { 111 newCap = spanSetInitSpineCap 112 } 113 newSpine := persistentalloc(newCap*goarch.PtrSize, cpu.CacheLineSize, &memstats.gcMiscSys) 114 if b.spineCap != 0 { 115 // Blocks are allocated off-heap, so 116 // no write barriers. 117 memmove(newSpine, spine.p, b.spineCap*goarch.PtrSize) 118 } 119 spine = spanSetSpinePointer{newSpine} 120 121 // Spine is allocated off-heap, so no write barrier. 122 b.spine.StoreNoWB(spine) 123 b.spineCap = newCap 124 // We can't immediately free the old spine 125 // since a concurrent push with a lower index 126 // could still be reading from it. We let it 127 // leak because even a 1TB heap would waste 128 // less than 2MB of memory on old spines. If 129 // this is a problem, we could free old spines 130 // during STW. 131 } 132 133 // Allocate a new block from the pool. 134 block = spanSetBlockPool.alloc() 135 136 // Add it to the spine. 137 // Blocks are allocated off-heap, so no write barrier. 138 spine.lookup(top).StoreNoWB(block) 139 b.spineLen.Store(spineLen + 1) 140 unlock(&b.spineLock) 141 } 142 143 // We have a block. Insert the span atomically, since there may be 144 // concurrent readers via the block API. 145 block.spans[bottom].StoreNoWB(s) 146 } 147 148 // pop removes and returns a span from buffer b, or nil if b is empty. 149 // pop is safe to call concurrently with other pop and push operations. 150 func (b *spanSet) pop() *mspan { 151 var head, tail uint32 152 claimLoop: 153 for { 154 headtail := b.index.load() 155 head, tail = headtail.split() 156 if head >= tail { 157 // The buf is empty, as far as we can tell. 158 return nil 159 } 160 // Check if the head position we want to claim is actually 161 // backed by a block. 162 spineLen := b.spineLen.Load() 163 if spineLen <= uintptr(head)/spanSetBlockEntries { 164 // We're racing with a spine growth and the allocation of 165 // a new block (and maybe a new spine!), and trying to grab 166 // the span at the index which is currently being pushed. 167 // Instead of spinning, let's just notify the caller that 168 // there's nothing currently here. Spinning on this is 169 // almost definitely not worth it. 170 return nil 171 } 172 // Try to claim the current head by CASing in an updated head. 173 // This may fail transiently due to a push which modifies the 174 // tail, so keep trying while the head isn't changing. 175 want := head 176 for want == head { 177 if b.index.cas(headtail, makeHeadTailIndex(want+1, tail)) { 178 break claimLoop 179 } 180 headtail = b.index.load() 181 head, tail = headtail.split() 182 } 183 // We failed to claim the spot we were after and the head changed, 184 // meaning a popper got ahead of us. Try again from the top because 185 // the buf may not be empty. 186 } 187 top, bottom := head/spanSetBlockEntries, head%spanSetBlockEntries 188 189 // We may be reading a stale spine pointer, but because the length 190 // grows monotonically and we've already verified it, we'll definitely 191 // be reading from a valid block. 192 blockp := b.spine.Load().lookup(uintptr(top)) 193 194 // Given that the spine length is correct, we know we will never 195 // see a nil block here, since the length is always updated after 196 // the block is set. 197 block := blockp.Load() 198 s := block.spans[bottom].Load() 199 for s == nil { 200 // We raced with the span actually being set, but given that we 201 // know a block for this span exists, the race window here is 202 // extremely small. Try again. 203 s = block.spans[bottom].Load() 204 } 205 // Clear the pointer. This isn't strictly necessary, but defensively 206 // avoids accidentally re-using blocks which could lead to memory 207 // corruption. This way, we'll get a nil pointer access instead. 208 block.spans[bottom].StoreNoWB(nil) 209 210 // Increase the popped count. If we are the last possible popper 211 // in the block (note that bottom need not equal spanSetBlockEntries-1 212 // due to races) then it's our responsibility to free the block. 213 // 214 // If we increment popped to spanSetBlockEntries, we can be sure that 215 // we're the last popper for this block, and it's thus safe to free it. 216 // Every other popper must have crossed this barrier (and thus finished 217 // popping its corresponding mspan) by the time we get here. Because 218 // we're the last popper, we also don't have to worry about concurrent 219 // pushers (there can't be any). Note that we may not be the popper 220 // which claimed the last slot in the block, we're just the last one 221 // to finish popping. 222 if block.popped.Add(1) == spanSetBlockEntries { 223 // Clear the block's pointer. 224 blockp.StoreNoWB(nil) 225 226 // Return the block to the block pool. 227 spanSetBlockPool.free(block) 228 } 229 return s 230 } 231 232 // reset resets a spanSet which is empty. It will also clean up 233 // any left over blocks. 234 // 235 // Throws if the buf is not empty. 236 // 237 // reset may not be called concurrently with any other operations 238 // on the span set. 239 func (b *spanSet) reset() { 240 head, tail := b.index.load().split() 241 if head < tail { 242 print("head = ", head, ", tail = ", tail, "\n") 243 throw("attempt to clear non-empty span set") 244 } 245 top := head / spanSetBlockEntries 246 if uintptr(top) < b.spineLen.Load() { 247 // If the head catches up to the tail and the set is empty, 248 // we may not clean up the block containing the head and tail 249 // since it may be pushed into again. In order to avoid leaking 250 // memory since we're going to reset the head and tail, clean 251 // up such a block now, if it exists. 252 blockp := b.spine.Load().lookup(uintptr(top)) 253 block := blockp.Load() 254 if block != nil { 255 // Check the popped value. 256 if block.popped.Load() == 0 { 257 // popped should never be zero because that means we have 258 // pushed at least one value but not yet popped if this 259 // block pointer is not nil. 260 throw("span set block with unpopped elements found in reset") 261 } 262 if block.popped.Load() == spanSetBlockEntries { 263 // popped should also never be equal to spanSetBlockEntries 264 // because the last popper should have made the block pointer 265 // in this slot nil. 266 throw("fully empty unfreed span set block found in reset") 267 } 268 269 // Clear the pointer to the block. 270 blockp.StoreNoWB(nil) 271 272 // Return the block to the block pool. 273 spanSetBlockPool.free(block) 274 } 275 } 276 b.index.reset() 277 b.spineLen.Store(0) 278 } 279 280 // atomicSpanSetSpinePointer is an atomically-accessed spanSetSpinePointer. 281 // 282 // It has the same semantics as atomic.UnsafePointer. 283 type atomicSpanSetSpinePointer struct { 284 a atomic.UnsafePointer 285 } 286 287 // Loads the spanSetSpinePointer and returns it. 288 // 289 // It has the same semantics as atomic.UnsafePointer. 290 func (s *atomicSpanSetSpinePointer) Load() spanSetSpinePointer { 291 return spanSetSpinePointer{s.a.Load()} 292 } 293 294 // Stores the spanSetSpinePointer. 295 // 296 // It has the same semantics as [atomic.UnsafePointer]. 297 func (s *atomicSpanSetSpinePointer) StoreNoWB(p spanSetSpinePointer) { 298 s.a.StoreNoWB(p.p) 299 } 300 301 // spanSetSpinePointer represents a pointer to a contiguous block of atomic.Pointer[spanSetBlock]. 302 type spanSetSpinePointer struct { 303 p unsafe.Pointer 304 } 305 306 // lookup returns &s[idx]. 307 func (s spanSetSpinePointer) lookup(idx uintptr) *atomic.Pointer[spanSetBlock] { 308 return (*atomic.Pointer[spanSetBlock])(add(s.p, goarch.PtrSize*idx)) 309 } 310 311 // spanSetBlockPool is a global pool of spanSetBlocks. 312 var spanSetBlockPool spanSetBlockAlloc 313 314 // spanSetBlockAlloc represents a concurrent pool of spanSetBlocks. 315 type spanSetBlockAlloc struct { 316 stack lfstack 317 } 318 319 // alloc tries to grab a spanSetBlock out of the pool, and if it fails 320 // persistentallocs a new one and returns it. 321 func (p *spanSetBlockAlloc) alloc() *spanSetBlock { 322 if s := (*spanSetBlock)(p.stack.pop()); s != nil { 323 return s 324 } 325 return (*spanSetBlock)(persistentalloc(unsafe.Sizeof(spanSetBlock{}), max(cpu.CacheLineSize, tagAlign), &memstats.gcMiscSys)) 326 } 327 328 // free returns a spanSetBlock back to the pool. 329 func (p *spanSetBlockAlloc) free(block *spanSetBlock) { 330 block.popped.Store(0) 331 p.stack.push(&block.lfnode) 332 } 333 334 // headTailIndex represents a combined 32-bit head and 32-bit tail 335 // of a queue into a single 64-bit value. 336 type headTailIndex uint64 337 338 // makeHeadTailIndex creates a headTailIndex value from a separate 339 // head and tail. 340 func makeHeadTailIndex(head, tail uint32) headTailIndex { 341 return headTailIndex(uint64(head)<<32 | uint64(tail)) 342 } 343 344 // head returns the head of a headTailIndex value. 345 func (h headTailIndex) head() uint32 { 346 return uint32(h >> 32) 347 } 348 349 // tail returns the tail of a headTailIndex value. 350 func (h headTailIndex) tail() uint32 { 351 return uint32(h) 352 } 353 354 // split splits the headTailIndex value into its parts. 355 func (h headTailIndex) split() (head uint32, tail uint32) { 356 return h.head(), h.tail() 357 } 358 359 // atomicHeadTailIndex is an atomically-accessed headTailIndex. 360 type atomicHeadTailIndex struct { 361 u atomic.Uint64 362 } 363 364 // load atomically reads a headTailIndex value. 365 func (h *atomicHeadTailIndex) load() headTailIndex { 366 return headTailIndex(h.u.Load()) 367 } 368 369 // cas atomically compares-and-swaps a headTailIndex value. 370 func (h *atomicHeadTailIndex) cas(old, new headTailIndex) bool { 371 return h.u.CompareAndSwap(uint64(old), uint64(new)) 372 } 373 374 // incHead atomically increments the head of a headTailIndex. 375 func (h *atomicHeadTailIndex) incHead() headTailIndex { 376 return headTailIndex(h.u.Add(1 << 32)) 377 } 378 379 // decHead atomically decrements the head of a headTailIndex. 380 func (h *atomicHeadTailIndex) decHead() headTailIndex { 381 return headTailIndex(h.u.Add(-(1 << 32))) 382 } 383 384 // incTail atomically increments the tail of a headTailIndex. 385 func (h *atomicHeadTailIndex) incTail() headTailIndex { 386 ht := headTailIndex(h.u.Add(1)) 387 // Check for overflow. 388 if ht.tail() == 0 { 389 print("runtime: head = ", ht.head(), ", tail = ", ht.tail(), "\n") 390 throw("headTailIndex overflow") 391 } 392 return ht 393 } 394 395 // reset clears the headTailIndex to (0, 0). 396 func (h *atomicHeadTailIndex) reset() { 397 h.u.Store(0) 398 } 399 400 // atomicMSpanPointer is an atomic.Pointer[mspan]. Can't use generics because it's NotInHeap. 401 type atomicMSpanPointer struct { 402 p atomic.UnsafePointer 403 } 404 405 // Load returns the *mspan. 406 func (p *atomicMSpanPointer) Load() *mspan { 407 return (*mspan)(p.p.Load()) 408 } 409 410 // Store stores an *mspan. 411 func (p *atomicMSpanPointer) StoreNoWB(s *mspan) { 412 p.p.StoreNoWB(unsafe.Pointer(s)) 413 } 414