Source file src/runtime/mheap.go
1 // Copyright 2009 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 // Page heap. 6 // 7 // See malloc.go for overview. 8 9 package runtime 10 11 import ( 12 "internal/cpu" 13 "internal/goarch" 14 "runtime/internal/atomic" 15 "unsafe" 16 ) 17 18 const ( 19 // minPhysPageSize is a lower-bound on the physical page size. The 20 // true physical page size may be larger than this. In contrast, 21 // sys.PhysPageSize is an upper-bound on the physical page size. 22 minPhysPageSize = 4096 23 24 // maxPhysPageSize is the maximum page size the runtime supports. 25 maxPhysPageSize = 512 << 10 26 27 // maxPhysHugePageSize sets an upper-bound on the maximum huge page size 28 // that the runtime supports. 29 maxPhysHugePageSize = pallocChunkBytes 30 31 // pagesPerReclaimerChunk indicates how many pages to scan from the 32 // pageInUse bitmap at a time. Used by the page reclaimer. 33 // 34 // Higher values reduce contention on scanning indexes (such as 35 // h.reclaimIndex), but increase the minimum latency of the 36 // operation. 37 // 38 // The time required to scan this many pages can vary a lot depending 39 // on how many spans are actually freed. Experimentally, it can 40 // scan for pages at ~300 GB/ms on a 2.6GHz Core i7, but can only 41 // free spans at ~32 MB/ms. Using 512 pages bounds this at 42 // roughly 100µs. 43 // 44 // Must be a multiple of the pageInUse bitmap element size and 45 // must also evenly divide pagesPerArena. 46 pagesPerReclaimerChunk = 512 47 48 // physPageAlignedStacks indicates whether stack allocations must be 49 // physical page aligned. This is a requirement for MAP_STACK on 50 // OpenBSD. 51 physPageAlignedStacks = GOOS == "openbsd" 52 ) 53 54 // Main malloc heap. 55 // The heap itself is the "free" and "scav" treaps, 56 // but all the other global data is here too. 57 // 58 // mheap must not be heap-allocated because it contains mSpanLists, 59 // which must not be heap-allocated. 60 // 61 //go:notinheap 62 type mheap struct { 63 // lock must only be acquired on the system stack, otherwise a g 64 // could self-deadlock if its stack grows with the lock held. 65 lock mutex 66 pages pageAlloc // page allocation data structure 67 68 sweepgen uint32 // sweep generation, see comment in mspan; written during STW 69 70 // allspans is a slice of all mspans ever created. Each mspan 71 // appears exactly once. 72 // 73 // The memory for allspans is manually managed and can be 74 // reallocated and move as the heap grows. 75 // 76 // In general, allspans is protected by mheap_.lock, which 77 // prevents concurrent access as well as freeing the backing 78 // store. Accesses during STW might not hold the lock, but 79 // must ensure that allocation cannot happen around the 80 // access (since that may free the backing store). 81 allspans []*mspan // all spans out there 82 83 // _ uint32 // align uint64 fields on 32-bit for atomics 84 85 // Proportional sweep 86 // 87 // These parameters represent a linear function from gcController.heapLive 88 // to page sweep count. The proportional sweep system works to 89 // stay in the black by keeping the current page sweep count 90 // above this line at the current gcController.heapLive. 91 // 92 // The line has slope sweepPagesPerByte and passes through a 93 // basis point at (sweepHeapLiveBasis, pagesSweptBasis). At 94 // any given time, the system is at (gcController.heapLive, 95 // pagesSwept) in this space. 96 // 97 // It is important that the line pass through a point we 98 // control rather than simply starting at a 0,0 origin 99 // because that lets us adjust sweep pacing at any time while 100 // accounting for current progress. If we could only adjust 101 // the slope, it would create a discontinuity in debt if any 102 // progress has already been made. 103 pagesInUse atomic.Uint64 // pages of spans in stats mSpanInUse 104 pagesSwept atomic.Uint64 // pages swept this cycle 105 pagesSweptBasis atomic.Uint64 // pagesSwept to use as the origin of the sweep ratio 106 sweepHeapLiveBasis uint64 // value of gcController.heapLive to use as the origin of sweep ratio; written with lock, read without 107 sweepPagesPerByte float64 // proportional sweep ratio; written with lock, read without 108 // TODO(austin): pagesInUse should be a uintptr, but the 386 109 // compiler can't 8-byte align fields. 110 111 // scavengeGoal is the amount of total retained heap memory (measured by 112 // heapRetained) that the runtime will try to maintain by returning memory 113 // to the OS. 114 // 115 // Accessed atomically. 116 scavengeGoal uint64 117 118 // Page reclaimer state 119 120 // reclaimIndex is the page index in allArenas of next page to 121 // reclaim. Specifically, it refers to page (i % 122 // pagesPerArena) of arena allArenas[i / pagesPerArena]. 123 // 124 // If this is >= 1<<63, the page reclaimer is done scanning 125 // the page marks. 126 reclaimIndex atomic.Uint64 127 128 // reclaimCredit is spare credit for extra pages swept. Since 129 // the page reclaimer works in large chunks, it may reclaim 130 // more than requested. Any spare pages released go to this 131 // credit pool. 132 reclaimCredit atomic.Uintptr 133 134 // arenas is the heap arena map. It points to the metadata for 135 // the heap for every arena frame of the entire usable virtual 136 // address space. 137 // 138 // Use arenaIndex to compute indexes into this array. 139 // 140 // For regions of the address space that are not backed by the 141 // Go heap, the arena map contains nil. 142 // 143 // Modifications are protected by mheap_.lock. Reads can be 144 // performed without locking; however, a given entry can 145 // transition from nil to non-nil at any time when the lock 146 // isn't held. (Entries never transitions back to nil.) 147 // 148 // In general, this is a two-level mapping consisting of an L1 149 // map and possibly many L2 maps. This saves space when there 150 // are a huge number of arena frames. However, on many 151 // platforms (even 64-bit), arenaL1Bits is 0, making this 152 // effectively a single-level map. In this case, arenas[0] 153 // will never be nil. 154 arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena 155 156 // heapArenaAlloc is pre-reserved space for allocating heapArena 157 // objects. This is only used on 32-bit, where we pre-reserve 158 // this space to avoid interleaving it with the heap itself. 159 heapArenaAlloc linearAlloc 160 161 // arenaHints is a list of addresses at which to attempt to 162 // add more heap arenas. This is initially populated with a 163 // set of general hint addresses, and grown with the bounds of 164 // actual heap arena ranges. 165 arenaHints *arenaHint 166 167 // arena is a pre-reserved space for allocating heap arenas 168 // (the actual arenas). This is only used on 32-bit. 169 arena linearAlloc 170 171 // allArenas is the arenaIndex of every mapped arena. This can 172 // be used to iterate through the address space. 173 // 174 // Access is protected by mheap_.lock. However, since this is 175 // append-only and old backing arrays are never freed, it is 176 // safe to acquire mheap_.lock, copy the slice header, and 177 // then release mheap_.lock. 178 allArenas []arenaIdx 179 180 // sweepArenas is a snapshot of allArenas taken at the 181 // beginning of the sweep cycle. This can be read safely by 182 // simply blocking GC (by disabling preemption). 183 sweepArenas []arenaIdx 184 185 // markArenas is a snapshot of allArenas taken at the beginning 186 // of the mark cycle. Because allArenas is append-only, neither 187 // this slice nor its contents will change during the mark, so 188 // it can be read safely. 189 markArenas []arenaIdx 190 191 // curArena is the arena that the heap is currently growing 192 // into. This should always be physPageSize-aligned. 193 curArena struct { 194 base, end uintptr 195 } 196 197 _ uint32 // ensure 64-bit alignment of central 198 199 // central free lists for small size classes. 200 // the padding makes sure that the mcentrals are 201 // spaced CacheLinePadSize bytes apart, so that each mcentral.lock 202 // gets its own cache line. 203 // central is indexed by spanClass. 204 central [numSpanClasses]struct { 205 mcentral mcentral 206 pad [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte 207 } 208 209 spanalloc fixalloc // allocator for span* 210 cachealloc fixalloc // allocator for mcache* 211 specialfinalizeralloc fixalloc // allocator for specialfinalizer* 212 specialprofilealloc fixalloc // allocator for specialprofile* 213 specialReachableAlloc fixalloc // allocator for specialReachable 214 speciallock mutex // lock for special record allocators. 215 arenaHintAlloc fixalloc // allocator for arenaHints 216 217 unused *specialfinalizer // never set, just here to force the specialfinalizer type into DWARF 218 } 219 220 var mheap_ mheap 221 222 // A heapArena stores metadata for a heap arena. heapArenas are stored 223 // outside of the Go heap and accessed via the mheap_.arenas index. 224 // 225 //go:notinheap 226 type heapArena struct { 227 // bitmap stores the pointer/scalar bitmap for the words in 228 // this arena. See mbitmap.go for a description. Use the 229 // heapBits type to access this. 230 bitmap [heapArenaBitmapBytes]byte 231 232 // spans maps from virtual address page ID within this arena to *mspan. 233 // For allocated spans, their pages map to the span itself. 234 // For free spans, only the lowest and highest pages map to the span itself. 235 // Internal pages map to an arbitrary span. 236 // For pages that have never been allocated, spans entries are nil. 237 // 238 // Modifications are protected by mheap.lock. Reads can be 239 // performed without locking, but ONLY from indexes that are 240 // known to contain in-use or stack spans. This means there 241 // must not be a safe-point between establishing that an 242 // address is live and looking it up in the spans array. 243 spans [pagesPerArena]*mspan 244 245 // pageInUse is a bitmap that indicates which spans are in 246 // state mSpanInUse. This bitmap is indexed by page number, 247 // but only the bit corresponding to the first page in each 248 // span is used. 249 // 250 // Reads and writes are atomic. 251 pageInUse [pagesPerArena / 8]uint8 252 253 // pageMarks is a bitmap that indicates which spans have any 254 // marked objects on them. Like pageInUse, only the bit 255 // corresponding to the first page in each span is used. 256 // 257 // Writes are done atomically during marking. Reads are 258 // non-atomic and lock-free since they only occur during 259 // sweeping (and hence never race with writes). 260 // 261 // This is used to quickly find whole spans that can be freed. 262 // 263 // TODO(austin): It would be nice if this was uint64 for 264 // faster scanning, but we don't have 64-bit atomic bit 265 // operations. 266 pageMarks [pagesPerArena / 8]uint8 267 268 // pageSpecials is a bitmap that indicates which spans have 269 // specials (finalizers or other). Like pageInUse, only the bit 270 // corresponding to the first page in each span is used. 271 // 272 // Writes are done atomically whenever a special is added to 273 // a span and whenever the last special is removed from a span. 274 // Reads are done atomically to find spans containing specials 275 // during marking. 276 pageSpecials [pagesPerArena / 8]uint8 277 278 // checkmarks stores the debug.gccheckmark state. It is only 279 // used if debug.gccheckmark > 0. 280 checkmarks *checkmarksMap 281 282 // zeroedBase marks the first byte of the first page in this 283 // arena which hasn't been used yet and is therefore already 284 // zero. zeroedBase is relative to the arena base. 285 // Increases monotonically until it hits heapArenaBytes. 286 // 287 // This field is sufficient to determine if an allocation 288 // needs to be zeroed because the page allocator follows an 289 // address-ordered first-fit policy. 290 // 291 // Read atomically and written with an atomic CAS. 292 zeroedBase uintptr 293 } 294 295 // arenaHint is a hint for where to grow the heap arenas. See 296 // mheap_.arenaHints. 297 // 298 //go:notinheap 299 type arenaHint struct { 300 addr uintptr 301 down bool 302 next *arenaHint 303 } 304 305 // An mspan is a run of pages. 306 // 307 // When a mspan is in the heap free treap, state == mSpanFree 308 // and heapmap(s->start) == span, heapmap(s->start+s->npages-1) == span. 309 // If the mspan is in the heap scav treap, then in addition to the 310 // above scavenged == true. scavenged == false in all other cases. 311 // 312 // When a mspan is allocated, state == mSpanInUse or mSpanManual 313 // and heapmap(i) == span for all s->start <= i < s->start+s->npages. 314 315 // Every mspan is in one doubly-linked list, either in the mheap's 316 // busy list or one of the mcentral's span lists. 317 318 // An mspan representing actual memory has state mSpanInUse, 319 // mSpanManual, or mSpanFree. Transitions between these states are 320 // constrained as follows: 321 // 322 // * A span may transition from free to in-use or manual during any GC 323 // phase. 324 // 325 // * During sweeping (gcphase == _GCoff), a span may transition from 326 // in-use to free (as a result of sweeping) or manual to free (as a 327 // result of stacks being freed). 328 // 329 // * During GC (gcphase != _GCoff), a span *must not* transition from 330 // manual or in-use to free. Because concurrent GC may read a pointer 331 // and then look up its span, the span state must be monotonic. 332 // 333 // Setting mspan.state to mSpanInUse or mSpanManual must be done 334 // atomically and only after all other span fields are valid. 335 // Likewise, if inspecting a span is contingent on it being 336 // mSpanInUse, the state should be loaded atomically and checked 337 // before depending on other fields. This allows the garbage collector 338 // to safely deal with potentially invalid pointers, since resolving 339 // such pointers may race with a span being allocated. 340 type mSpanState uint8 341 342 const ( 343 mSpanDead mSpanState = iota 344 mSpanInUse // allocated for garbage collected heap 345 mSpanManual // allocated for manual management (e.g., stack allocator) 346 ) 347 348 // mSpanStateNames are the names of the span states, indexed by 349 // mSpanState. 350 var mSpanStateNames = []string{ 351 "mSpanDead", 352 "mSpanInUse", 353 "mSpanManual", 354 "mSpanFree", 355 } 356 357 // mSpanStateBox holds an mSpanState and provides atomic operations on 358 // it. This is a separate type to disallow accidental comparison or 359 // assignment with mSpanState. 360 type mSpanStateBox struct { 361 s mSpanState 362 } 363 364 func (b *mSpanStateBox) set(s mSpanState) { 365 atomic.Store8((*uint8)(&b.s), uint8(s)) 366 } 367 368 func (b *mSpanStateBox) get() mSpanState { 369 return mSpanState(atomic.Load8((*uint8)(&b.s))) 370 } 371 372 // mSpanList heads a linked list of spans. 373 // 374 //go:notinheap 375 type mSpanList struct { 376 first *mspan // first span in list, or nil if none 377 last *mspan // last span in list, or nil if none 378 } 379 380 //go:notinheap 381 type mspan struct { 382 next *mspan // next span in list, or nil if none 383 prev *mspan // previous span in list, or nil if none 384 list *mSpanList // For debugging. TODO: Remove. 385 386 startAddr uintptr // address of first byte of span aka s.base() 387 npages uintptr // number of pages in span 388 389 manualFreeList gclinkptr // list of free objects in mSpanManual spans 390 391 // freeindex is the slot index between 0 and nelems at which to begin scanning 392 // for the next free object in this span. 393 // Each allocation scans allocBits starting at freeindex until it encounters a 0 394 // indicating a free object. freeindex is then adjusted so that subsequent scans begin 395 // just past the newly discovered free object. 396 // 397 // If freeindex == nelem, this span has no free objects. 398 // 399 // allocBits is a bitmap of objects in this span. 400 // If n >= freeindex and allocBits[n/8] & (1<<(n%8)) is 0 401 // then object n is free; 402 // otherwise, object n is allocated. Bits starting at nelem are 403 // undefined and should never be referenced. 404 // 405 // Object n starts at address n*elemsize + (start << pageShift). 406 freeindex uintptr 407 // TODO: Look up nelems from sizeclass and remove this field if it 408 // helps performance. 409 nelems uintptr // number of object in the span. 410 411 // Cache of the allocBits at freeindex. allocCache is shifted 412 // such that the lowest bit corresponds to the bit freeindex. 413 // allocCache holds the complement of allocBits, thus allowing 414 // ctz (count trailing zero) to use it directly. 415 // allocCache may contain bits beyond s.nelems; the caller must ignore 416 // these. 417 allocCache uint64 418 419 // allocBits and gcmarkBits hold pointers to a span's mark and 420 // allocation bits. The pointers are 8 byte aligned. 421 // There are three arenas where this data is held. 422 // free: Dirty arenas that are no longer accessed 423 // and can be reused. 424 // next: Holds information to be used in the next GC cycle. 425 // current: Information being used during this GC cycle. 426 // previous: Information being used during the last GC cycle. 427 // A new GC cycle starts with the call to finishsweep_m. 428 // finishsweep_m moves the previous arena to the free arena, 429 // the current arena to the previous arena, and 430 // the next arena to the current arena. 431 // The next arena is populated as the spans request 432 // memory to hold gcmarkBits for the next GC cycle as well 433 // as allocBits for newly allocated spans. 434 // 435 // The pointer arithmetic is done "by hand" instead of using 436 // arrays to avoid bounds checks along critical performance 437 // paths. 438 // The sweep will free the old allocBits and set allocBits to the 439 // gcmarkBits. The gcmarkBits are replaced with a fresh zeroed 440 // out memory. 441 allocBits *gcBits 442 gcmarkBits *gcBits 443 444 // sweep generation: 445 // if sweepgen == h->sweepgen - 2, the span needs sweeping 446 // if sweepgen == h->sweepgen - 1, the span is currently being swept 447 // if sweepgen == h->sweepgen, the span is swept and ready to use 448 // if sweepgen == h->sweepgen + 1, the span was cached before sweep began and is still cached, and needs sweeping 449 // if sweepgen == h->sweepgen + 3, the span was swept and then cached and is still cached 450 // h->sweepgen is incremented by 2 after every GC 451 452 sweepgen uint32 453 divMul uint32 // for divide by elemsize 454 allocCount uint16 // number of allocated objects 455 spanclass spanClass // size class and noscan (uint8) 456 state mSpanStateBox // mSpanInUse etc; accessed atomically (get/set methods) 457 needzero uint8 // needs to be zeroed before allocation 458 elemsize uintptr // computed from sizeclass or from npages 459 limit uintptr // end of data in span 460 speciallock mutex // guards specials list 461 specials *special // linked list of special records sorted by offset. 462 } 463 464 func (s *mspan) base() uintptr { 465 return s.startAddr 466 } 467 468 func (s *mspan) layout() (size, n, total uintptr) { 469 total = s.npages << _PageShift 470 size = s.elemsize 471 if size > 0 { 472 n = total / size 473 } 474 return 475 } 476 477 // recordspan adds a newly allocated span to h.allspans. 478 // 479 // This only happens the first time a span is allocated from 480 // mheap.spanalloc (it is not called when a span is reused). 481 // 482 // Write barriers are disallowed here because it can be called from 483 // gcWork when allocating new workbufs. However, because it's an 484 // indirect call from the fixalloc initializer, the compiler can't see 485 // this. 486 // 487 // The heap lock must be held. 488 // 489 //go:nowritebarrierrec 490 func recordspan(vh unsafe.Pointer, p unsafe.Pointer) { 491 h := (*mheap)(vh) 492 s := (*mspan)(p) 493 494 assertLockHeld(&h.lock) 495 496 if len(h.allspans) >= cap(h.allspans) { 497 n := 64 * 1024 / goarch.PtrSize 498 if n < cap(h.allspans)*3/2 { 499 n = cap(h.allspans) * 3 / 2 500 } 501 var new []*mspan 502 sp := (*slice)(unsafe.Pointer(&new)) 503 sp.array = sysAlloc(uintptr(n)*goarch.PtrSize, &memstats.other_sys) 504 if sp.array == nil { 505 throw("runtime: cannot allocate memory") 506 } 507 sp.len = len(h.allspans) 508 sp.cap = n 509 if len(h.allspans) > 0 { 510 copy(new, h.allspans) 511 } 512 oldAllspans := h.allspans 513 *(*notInHeapSlice)(unsafe.Pointer(&h.allspans)) = *(*notInHeapSlice)(unsafe.Pointer(&new)) 514 if len(oldAllspans) != 0 { 515 sysFree(unsafe.Pointer(&oldAllspans[0]), uintptr(cap(oldAllspans))*unsafe.Sizeof(oldAllspans[0]), &memstats.other_sys) 516 } 517 } 518 h.allspans = h.allspans[:len(h.allspans)+1] 519 h.allspans[len(h.allspans)-1] = s 520 } 521 522 // A spanClass represents the size class and noscan-ness of a span. 523 // 524 // Each size class has a noscan spanClass and a scan spanClass. The 525 // noscan spanClass contains only noscan objects, which do not contain 526 // pointers and thus do not need to be scanned by the garbage 527 // collector. 528 type spanClass uint8 529 530 const ( 531 numSpanClasses = _NumSizeClasses << 1 532 tinySpanClass = spanClass(tinySizeClass<<1 | 1) 533 ) 534 535 func makeSpanClass(sizeclass uint8, noscan bool) spanClass { 536 return spanClass(sizeclass<<1) | spanClass(bool2int(noscan)) 537 } 538 539 func (sc spanClass) sizeclass() int8 { 540 return int8(sc >> 1) 541 } 542 543 func (sc spanClass) noscan() bool { 544 return sc&1 != 0 545 } 546 547 // arenaIndex returns the index into mheap_.arenas of the arena 548 // containing metadata for p. This index combines of an index into the 549 // L1 map and an index into the L2 map and should be used as 550 // mheap_.arenas[ai.l1()][ai.l2()]. 551 // 552 // If p is outside the range of valid heap addresses, either l1() or 553 // l2() will be out of bounds. 554 // 555 // It is nosplit because it's called by spanOf and several other 556 // nosplit functions. 557 // 558 //go:nosplit 559 func arenaIndex(p uintptr) arenaIdx { 560 return arenaIdx((p - arenaBaseOffset) / heapArenaBytes) 561 } 562 563 // arenaBase returns the low address of the region covered by heap 564 // arena i. 565 func arenaBase(i arenaIdx) uintptr { 566 return uintptr(i)*heapArenaBytes + arenaBaseOffset 567 } 568 569 type arenaIdx uint 570 571 func (i arenaIdx) l1() uint { 572 if arenaL1Bits == 0 { 573 // Let the compiler optimize this away if there's no 574 // L1 map. 575 return 0 576 } else { 577 return uint(i) >> arenaL1Shift 578 } 579 } 580 581 func (i arenaIdx) l2() uint { 582 if arenaL1Bits == 0 { 583 return uint(i) 584 } else { 585 return uint(i) & (1<<arenaL2Bits - 1) 586 } 587 } 588 589 // inheap reports whether b is a pointer into a (potentially dead) heap object. 590 // It returns false for pointers into mSpanManual spans. 591 // Non-preemptible because it is used by write barriers. 592 //go:nowritebarrier 593 //go:nosplit 594 func inheap(b uintptr) bool { 595 return spanOfHeap(b) != nil 596 } 597 598 // inHeapOrStack is a variant of inheap that returns true for pointers 599 // into any allocated heap span. 600 // 601 //go:nowritebarrier 602 //go:nosplit 603 func inHeapOrStack(b uintptr) bool { 604 s := spanOf(b) 605 if s == nil || b < s.base() { 606 return false 607 } 608 switch s.state.get() { 609 case mSpanInUse, mSpanManual: 610 return b < s.limit 611 default: 612 return false 613 } 614 } 615 616 // spanOf returns the span of p. If p does not point into the heap 617 // arena or no span has ever contained p, spanOf returns nil. 618 // 619 // If p does not point to allocated memory, this may return a non-nil 620 // span that does *not* contain p. If this is a possibility, the 621 // caller should either call spanOfHeap or check the span bounds 622 // explicitly. 623 // 624 // Must be nosplit because it has callers that are nosplit. 625 // 626 //go:nosplit 627 func spanOf(p uintptr) *mspan { 628 // This function looks big, but we use a lot of constant 629 // folding around arenaL1Bits to get it under the inlining 630 // budget. Also, many of the checks here are safety checks 631 // that Go needs to do anyway, so the generated code is quite 632 // short. 633 ri := arenaIndex(p) 634 if arenaL1Bits == 0 { 635 // If there's no L1, then ri.l1() can't be out of bounds but ri.l2() can. 636 if ri.l2() >= uint(len(mheap_.arenas[0])) { 637 return nil 638 } 639 } else { 640 // If there's an L1, then ri.l1() can be out of bounds but ri.l2() can't. 641 if ri.l1() >= uint(len(mheap_.arenas)) { 642 return nil 643 } 644 } 645 l2 := mheap_.arenas[ri.l1()] 646 if arenaL1Bits != 0 && l2 == nil { // Should never happen if there's no L1. 647 return nil 648 } 649 ha := l2[ri.l2()] 650 if ha == nil { 651 return nil 652 } 653 return ha.spans[(p/pageSize)%pagesPerArena] 654 } 655 656 // spanOfUnchecked is equivalent to spanOf, but the caller must ensure 657 // that p points into an allocated heap arena. 658 // 659 // Must be nosplit because it has callers that are nosplit. 660 // 661 //go:nosplit 662 func spanOfUnchecked(p uintptr) *mspan { 663 ai := arenaIndex(p) 664 return mheap_.arenas[ai.l1()][ai.l2()].spans[(p/pageSize)%pagesPerArena] 665 } 666 667 // spanOfHeap is like spanOf, but returns nil if p does not point to a 668 // heap object. 669 // 670 // Must be nosplit because it has callers that are nosplit. 671 // 672 //go:nosplit 673 func spanOfHeap(p uintptr) *mspan { 674 s := spanOf(p) 675 // s is nil if it's never been allocated. Otherwise, we check 676 // its state first because we don't trust this pointer, so we 677 // have to synchronize with span initialization. Then, it's 678 // still possible we picked up a stale span pointer, so we 679 // have to check the span's bounds. 680 if s == nil || s.state.get() != mSpanInUse || p < s.base() || p >= s.limit { 681 return nil 682 } 683 return s 684 } 685 686 // pageIndexOf returns the arena, page index, and page mask for pointer p. 687 // The caller must ensure p is in the heap. 688 func pageIndexOf(p uintptr) (arena *heapArena, pageIdx uintptr, pageMask uint8) { 689 ai := arenaIndex(p) 690 arena = mheap_.arenas[ai.l1()][ai.l2()] 691 pageIdx = ((p / pageSize) / 8) % uintptr(len(arena.pageInUse)) 692 pageMask = byte(1 << ((p / pageSize) % 8)) 693 return 694 } 695 696 // Initialize the heap. 697 func (h *mheap) init() { 698 lockInit(&h.lock, lockRankMheap) 699 lockInit(&h.speciallock, lockRankMheapSpecial) 700 701 h.spanalloc.init(unsafe.Sizeof(mspan{}), recordspan, unsafe.Pointer(h), &memstats.mspan_sys) 702 h.cachealloc.init(unsafe.Sizeof(mcache{}), nil, nil, &memstats.mcache_sys) 703 h.specialfinalizeralloc.init(unsafe.Sizeof(specialfinalizer{}), nil, nil, &memstats.other_sys) 704 h.specialprofilealloc.init(unsafe.Sizeof(specialprofile{}), nil, nil, &memstats.other_sys) 705 h.specialReachableAlloc.init(unsafe.Sizeof(specialReachable{}), nil, nil, &memstats.other_sys) 706 h.arenaHintAlloc.init(unsafe.Sizeof(arenaHint{}), nil, nil, &memstats.other_sys) 707 708 // Don't zero mspan allocations. Background sweeping can 709 // inspect a span concurrently with allocating it, so it's 710 // important that the span's sweepgen survive across freeing 711 // and re-allocating a span to prevent background sweeping 712 // from improperly cas'ing it from 0. 713 // 714 // This is safe because mspan contains no heap pointers. 715 h.spanalloc.zero = false 716 717 // h->mapcache needs no init 718 719 for i := range h.central { 720 h.central[i].mcentral.init(spanClass(i)) 721 } 722 723 h.pages.init(&h.lock, &memstats.gcMiscSys) 724 } 725 726 // reclaim sweeps and reclaims at least npage pages into the heap. 727 // It is called before allocating npage pages to keep growth in check. 728 // 729 // reclaim implements the page-reclaimer half of the sweeper. 730 // 731 // h.lock must NOT be held. 732 func (h *mheap) reclaim(npage uintptr) { 733 // TODO(austin): Half of the time spent freeing spans is in 734 // locking/unlocking the heap (even with low contention). We 735 // could make the slow path here several times faster by 736 // batching heap frees. 737 738 // Bail early if there's no more reclaim work. 739 if h.reclaimIndex.Load() >= 1<<63 { 740 return 741 } 742 743 // Disable preemption so the GC can't start while we're 744 // sweeping, so we can read h.sweepArenas, and so 745 // traceGCSweepStart/Done pair on the P. 746 mp := acquirem() 747 748 if trace.enabled { 749 traceGCSweepStart() 750 } 751 752 arenas := h.sweepArenas 753 locked := false 754 for npage > 0 { 755 // Pull from accumulated credit first. 756 if credit := h.reclaimCredit.Load(); credit > 0 { 757 take := credit 758 if take > npage { 759 // Take only what we need. 760 take = npage 761 } 762 if h.reclaimCredit.CompareAndSwap(credit, credit-take) { 763 npage -= take 764 } 765 continue 766 } 767 768 // Claim a chunk of work. 769 idx := uintptr(h.reclaimIndex.Add(pagesPerReclaimerChunk) - pagesPerReclaimerChunk) 770 if idx/pagesPerArena >= uintptr(len(arenas)) { 771 // Page reclaiming is done. 772 h.reclaimIndex.Store(1 << 63) 773 break 774 } 775 776 if !locked { 777 // Lock the heap for reclaimChunk. 778 lock(&h.lock) 779 locked = true 780 } 781 782 // Scan this chunk. 783 nfound := h.reclaimChunk(arenas, idx, pagesPerReclaimerChunk) 784 if nfound <= npage { 785 npage -= nfound 786 } else { 787 // Put spare pages toward global credit. 788 h.reclaimCredit.Add(nfound - npage) 789 npage = 0 790 } 791 } 792 if locked { 793 unlock(&h.lock) 794 } 795 796 if trace.enabled { 797 traceGCSweepDone() 798 } 799 releasem(mp) 800 } 801 802 // reclaimChunk sweeps unmarked spans that start at page indexes [pageIdx, pageIdx+n). 803 // It returns the number of pages returned to the heap. 804 // 805 // h.lock must be held and the caller must be non-preemptible. Note: h.lock may be 806 // temporarily unlocked and re-locked in order to do sweeping or if tracing is 807 // enabled. 808 func (h *mheap) reclaimChunk(arenas []arenaIdx, pageIdx, n uintptr) uintptr { 809 // The heap lock must be held because this accesses the 810 // heapArena.spans arrays using potentially non-live pointers. 811 // In particular, if a span were freed and merged concurrently 812 // with this probing heapArena.spans, it would be possible to 813 // observe arbitrary, stale span pointers. 814 assertLockHeld(&h.lock) 815 816 n0 := n 817 var nFreed uintptr 818 sl := sweep.active.begin() 819 if !sl.valid { 820 return 0 821 } 822 for n > 0 { 823 ai := arenas[pageIdx/pagesPerArena] 824 ha := h.arenas[ai.l1()][ai.l2()] 825 826 // Get a chunk of the bitmap to work on. 827 arenaPage := uint(pageIdx % pagesPerArena) 828 inUse := ha.pageInUse[arenaPage/8:] 829 marked := ha.pageMarks[arenaPage/8:] 830 if uintptr(len(inUse)) > n/8 { 831 inUse = inUse[:n/8] 832 marked = marked[:n/8] 833 } 834 835 // Scan this bitmap chunk for spans that are in-use 836 // but have no marked objects on them. 837 for i := range inUse { 838 inUseUnmarked := atomic.Load8(&inUse[i]) &^ marked[i] 839 if inUseUnmarked == 0 { 840 continue 841 } 842 843 for j := uint(0); j < 8; j++ { 844 if inUseUnmarked&(1<<j) != 0 { 845 s := ha.spans[arenaPage+uint(i)*8+j] 846 if s, ok := sl.tryAcquire(s); ok { 847 npages := s.npages 848 unlock(&h.lock) 849 if s.sweep(false) { 850 nFreed += npages 851 } 852 lock(&h.lock) 853 // Reload inUse. It's possible nearby 854 // spans were freed when we dropped the 855 // lock and we don't want to get stale 856 // pointers from the spans array. 857 inUseUnmarked = atomic.Load8(&inUse[i]) &^ marked[i] 858 } 859 } 860 } 861 } 862 863 // Advance. 864 pageIdx += uintptr(len(inUse) * 8) 865 n -= uintptr(len(inUse) * 8) 866 } 867 sweep.active.end(sl) 868 if trace.enabled { 869 unlock(&h.lock) 870 // Account for pages scanned but not reclaimed. 871 traceGCSweepSpan((n0 - nFreed) * pageSize) 872 lock(&h.lock) 873 } 874 875 assertLockHeld(&h.lock) // Must be locked on return. 876 return nFreed 877 } 878 879 // spanAllocType represents the type of allocation to make, or 880 // the type of allocation to be freed. 881 type spanAllocType uint8 882 883 const ( 884 spanAllocHeap spanAllocType = iota // heap span 885 spanAllocStack // stack span 886 spanAllocPtrScalarBits // unrolled GC prog bitmap span 887 spanAllocWorkBuf // work buf span 888 ) 889 890 // manual returns true if the span allocation is manually managed. 891 func (s spanAllocType) manual() bool { 892 return s != spanAllocHeap 893 } 894 895 // alloc allocates a new span of npage pages from the GC'd heap. 896 // 897 // spanclass indicates the span's size class and scannability. 898 // 899 // Returns a span that has been fully initialized. span.needzero indicates 900 // whether the span has been zeroed. Note that it may not be. 901 func (h *mheap) alloc(npages uintptr, spanclass spanClass) *mspan { 902 // Don't do any operations that lock the heap on the G stack. 903 // It might trigger stack growth, and the stack growth code needs 904 // to be able to allocate heap. 905 var s *mspan 906 systemstack(func() { 907 // To prevent excessive heap growth, before allocating n pages 908 // we need to sweep and reclaim at least n pages. 909 if !isSweepDone() { 910 h.reclaim(npages) 911 } 912 s = h.allocSpan(npages, spanAllocHeap, spanclass) 913 }) 914 return s 915 } 916 917 // allocManual allocates a manually-managed span of npage pages. 918 // allocManual returns nil if allocation fails. 919 // 920 // allocManual adds the bytes used to *stat, which should be a 921 // memstats in-use field. Unlike allocations in the GC'd heap, the 922 // allocation does *not* count toward heap_inuse or heap_sys. 923 // 924 // The memory backing the returned span may not be zeroed if 925 // span.needzero is set. 926 // 927 // allocManual must be called on the system stack because it may 928 // acquire the heap lock via allocSpan. See mheap for details. 929 // 930 // If new code is written to call allocManual, do NOT use an 931 // existing spanAllocType value and instead declare a new one. 932 // 933 //go:systemstack 934 func (h *mheap) allocManual(npages uintptr, typ spanAllocType) *mspan { 935 if !typ.manual() { 936 throw("manual span allocation called with non-manually-managed type") 937 } 938 return h.allocSpan(npages, typ, 0) 939 } 940 941 // setSpans modifies the span map so [spanOf(base), spanOf(base+npage*pageSize)) 942 // is s. 943 func (h *mheap) setSpans(base, npage uintptr, s *mspan) { 944 p := base / pageSize 945 ai := arenaIndex(base) 946 ha := h.arenas[ai.l1()][ai.l2()] 947 for n := uintptr(0); n < npage; n++ { 948 i := (p + n) % pagesPerArena 949 if i == 0 { 950 ai = arenaIndex(base + n*pageSize) 951 ha = h.arenas[ai.l1()][ai.l2()] 952 } 953 ha.spans[i] = s 954 } 955 } 956 957 // allocNeedsZero checks if the region of address space [base, base+npage*pageSize), 958 // assumed to be allocated, needs to be zeroed, updating heap arena metadata for 959 // future allocations. 960 // 961 // This must be called each time pages are allocated from the heap, even if the page 962 // allocator can otherwise prove the memory it's allocating is already zero because 963 // they're fresh from the operating system. It updates heapArena metadata that is 964 // critical for future page allocations. 965 // 966 // There are no locking constraints on this method. 967 func (h *mheap) allocNeedsZero(base, npage uintptr) (needZero bool) { 968 for npage > 0 { 969 ai := arenaIndex(base) 970 ha := h.arenas[ai.l1()][ai.l2()] 971 972 zeroedBase := atomic.Loaduintptr(&ha.zeroedBase) 973 arenaBase := base % heapArenaBytes 974 if arenaBase < zeroedBase { 975 // We extended into the non-zeroed part of the 976 // arena, so this region needs to be zeroed before use. 977 // 978 // zeroedBase is monotonically increasing, so if we see this now then 979 // we can be sure we need to zero this memory region. 980 // 981 // We still need to update zeroedBase for this arena, and 982 // potentially more arenas. 983 needZero = true 984 } 985 // We may observe arenaBase > zeroedBase if we're racing with one or more 986 // allocations which are acquiring memory directly before us in the address 987 // space. But, because we know no one else is acquiring *this* memory, it's 988 // still safe to not zero. 989 990 // Compute how far into the arena we extend into, capped 991 // at heapArenaBytes. 992 arenaLimit := arenaBase + npage*pageSize 993 if arenaLimit > heapArenaBytes { 994 arenaLimit = heapArenaBytes 995 } 996 // Increase ha.zeroedBase so it's >= arenaLimit. 997 // We may be racing with other updates. 998 for arenaLimit > zeroedBase { 999 if atomic.Casuintptr(&ha.zeroedBase, zeroedBase, arenaLimit) { 1000 break 1001 } 1002 zeroedBase = atomic.Loaduintptr(&ha.zeroedBase) 1003 // Double check basic conditions of zeroedBase. 1004 if zeroedBase <= arenaLimit && zeroedBase > arenaBase { 1005 // The zeroedBase moved into the space we were trying to 1006 // claim. That's very bad, and indicates someone allocated 1007 // the same region we did. 1008 throw("potentially overlapping in-use allocations detected") 1009 } 1010 } 1011 1012 // Move base forward and subtract from npage to move into 1013 // the next arena, or finish. 1014 base += arenaLimit - arenaBase 1015 npage -= (arenaLimit - arenaBase) / pageSize 1016 } 1017 return 1018 } 1019 1020 // tryAllocMSpan attempts to allocate an mspan object from 1021 // the P-local cache, but may fail. 1022 // 1023 // h.lock need not be held. 1024 // 1025 // This caller must ensure that its P won't change underneath 1026 // it during this function. Currently to ensure that we enforce 1027 // that the function is run on the system stack, because that's 1028 // the only place it is used now. In the future, this requirement 1029 // may be relaxed if its use is necessary elsewhere. 1030 // 1031 //go:systemstack 1032 func (h *mheap) tryAllocMSpan() *mspan { 1033 pp := getg().m.p.ptr() 1034 // If we don't have a p or the cache is empty, we can't do 1035 // anything here. 1036 if pp == nil || pp.mspancache.len == 0 { 1037 return nil 1038 } 1039 // Pull off the last entry in the cache. 1040 s := pp.mspancache.buf[pp.mspancache.len-1] 1041 pp.mspancache.len-- 1042 return s 1043 } 1044 1045 // allocMSpanLocked allocates an mspan object. 1046 // 1047 // h.lock must be held. 1048 // 1049 // allocMSpanLocked must be called on the system stack because 1050 // its caller holds the heap lock. See mheap for details. 1051 // Running on the system stack also ensures that we won't 1052 // switch Ps during this function. See tryAllocMSpan for details. 1053 // 1054 //go:systemstack 1055 func (h *mheap) allocMSpanLocked() *mspan { 1056 assertLockHeld(&h.lock) 1057 1058 pp := getg().m.p.ptr() 1059 if pp == nil { 1060 // We don't have a p so just do the normal thing. 1061 return (*mspan)(h.spanalloc.alloc()) 1062 } 1063 // Refill the cache if necessary. 1064 if pp.mspancache.len == 0 { 1065 const refillCount = len(pp.mspancache.buf) / 2 1066 for i := 0; i < refillCount; i++ { 1067 pp.mspancache.buf[i] = (*mspan)(h.spanalloc.alloc()) 1068 } 1069 pp.mspancache.len = refillCount 1070 } 1071 // Pull off the last entry in the cache. 1072 s := pp.mspancache.buf[pp.mspancache.len-1] 1073 pp.mspancache.len-- 1074 return s 1075 } 1076 1077 // freeMSpanLocked free an mspan object. 1078 // 1079 // h.lock must be held. 1080 // 1081 // freeMSpanLocked must be called on the system stack because 1082 // its caller holds the heap lock. See mheap for details. 1083 // Running on the system stack also ensures that we won't 1084 // switch Ps during this function. See tryAllocMSpan for details. 1085 // 1086 //go:systemstack 1087 func (h *mheap) freeMSpanLocked(s *mspan) { 1088 assertLockHeld(&h.lock) 1089 1090 pp := getg().m.p.ptr() 1091 // First try to free the mspan directly to the cache. 1092 if pp != nil && pp.mspancache.len < len(pp.mspancache.buf) { 1093 pp.mspancache.buf[pp.mspancache.len] = s 1094 pp.mspancache.len++ 1095 return 1096 } 1097 // Failing that (or if we don't have a p), just free it to 1098 // the heap. 1099 h.spanalloc.free(unsafe.Pointer(s)) 1100 } 1101 1102 // allocSpan allocates an mspan which owns npages worth of memory. 1103 // 1104 // If typ.manual() == false, allocSpan allocates a heap span of class spanclass 1105 // and updates heap accounting. If manual == true, allocSpan allocates a 1106 // manually-managed span (spanclass is ignored), and the caller is 1107 // responsible for any accounting related to its use of the span. Either 1108 // way, allocSpan will atomically add the bytes in the newly allocated 1109 // span to *sysStat. 1110 // 1111 // The returned span is fully initialized. 1112 // 1113 // h.lock must not be held. 1114 // 1115 // allocSpan must be called on the system stack both because it acquires 1116 // the heap lock and because it must block GC transitions. 1117 // 1118 //go:systemstack 1119 func (h *mheap) allocSpan(npages uintptr, typ spanAllocType, spanclass spanClass) (s *mspan) { 1120 // Function-global state. 1121 gp := getg() 1122 base, scav := uintptr(0), uintptr(0) 1123 growth := uintptr(0) 1124 1125 // On some platforms we need to provide physical page aligned stack 1126 // allocations. Where the page size is less than the physical page 1127 // size, we already manage to do this by default. 1128 needPhysPageAlign := physPageAlignedStacks && typ == spanAllocStack && pageSize < physPageSize 1129 1130 // If the allocation is small enough, try the page cache! 1131 // The page cache does not support aligned allocations, so we cannot use 1132 // it if we need to provide a physical page aligned stack allocation. 1133 pp := gp.m.p.ptr() 1134 if !needPhysPageAlign && pp != nil && npages < pageCachePages/4 { 1135 c := &pp.pcache 1136 1137 // If the cache is empty, refill it. 1138 if c.empty() { 1139 lock(&h.lock) 1140 *c = h.pages.allocToCache() 1141 unlock(&h.lock) 1142 } 1143 1144 // Try to allocate from the cache. 1145 base, scav = c.alloc(npages) 1146 if base != 0 { 1147 s = h.tryAllocMSpan() 1148 if s != nil { 1149 goto HaveSpan 1150 } 1151 // We have a base but no mspan, so we need 1152 // to lock the heap. 1153 } 1154 } 1155 1156 // For one reason or another, we couldn't get the 1157 // whole job done without the heap lock. 1158 lock(&h.lock) 1159 1160 if needPhysPageAlign { 1161 // Overallocate by a physical page to allow for later alignment. 1162 npages += physPageSize / pageSize 1163 } 1164 1165 if base == 0 { 1166 // Try to acquire a base address. 1167 base, scav = h.pages.alloc(npages) 1168 if base == 0 { 1169 var ok bool 1170 growth, ok = h.grow(npages) 1171 if !ok { 1172 unlock(&h.lock) 1173 return nil 1174 } 1175 base, scav = h.pages.alloc(npages) 1176 if base == 0 { 1177 throw("grew heap, but no adequate free space found") 1178 } 1179 } 1180 } 1181 if s == nil { 1182 // We failed to get an mspan earlier, so grab 1183 // one now that we have the heap lock. 1184 s = h.allocMSpanLocked() 1185 } 1186 1187 if needPhysPageAlign { 1188 allocBase, allocPages := base, npages 1189 base = alignUp(allocBase, physPageSize) 1190 npages -= physPageSize / pageSize 1191 1192 // Return memory around the aligned allocation. 1193 spaceBefore := base - allocBase 1194 if spaceBefore > 0 { 1195 h.pages.free(allocBase, spaceBefore/pageSize, false) 1196 } 1197 spaceAfter := (allocPages-npages)*pageSize - spaceBefore 1198 if spaceAfter > 0 { 1199 h.pages.free(base+npages*pageSize, spaceAfter/pageSize, false) 1200 } 1201 } 1202 1203 unlock(&h.lock) 1204 1205 if growth > 0 { 1206 // We just caused a heap growth, so scavenge down what will soon be used. 1207 // By scavenging inline we deal with the failure to allocate out of 1208 // memory fragments by scavenging the memory fragments that are least 1209 // likely to be re-used. 1210 scavengeGoal := atomic.Load64(&h.scavengeGoal) 1211 if retained := heapRetained(); retained+uint64(growth) > scavengeGoal { 1212 // The scavenging algorithm requires the heap lock to be dropped so it 1213 // can acquire it only sparingly. This is a potentially expensive operation 1214 // so it frees up other goroutines to allocate in the meanwhile. In fact, 1215 // they can make use of the growth we just created. 1216 todo := growth 1217 if overage := uintptr(retained + uint64(growth) - scavengeGoal); todo > overage { 1218 todo = overage 1219 } 1220 h.pages.scavenge(todo) 1221 } 1222 } 1223 1224 HaveSpan: 1225 // At this point, both s != nil and base != 0, and the heap 1226 // lock is no longer held. Initialize the span. 1227 s.init(base, npages) 1228 if h.allocNeedsZero(base, npages) { 1229 s.needzero = 1 1230 } 1231 nbytes := npages * pageSize 1232 if typ.manual() { 1233 s.manualFreeList = 0 1234 s.nelems = 0 1235 s.limit = s.base() + s.npages*pageSize 1236 s.state.set(mSpanManual) 1237 } else { 1238 // We must set span properties before the span is published anywhere 1239 // since we're not holding the heap lock. 1240 s.spanclass = spanclass 1241 if sizeclass := spanclass.sizeclass(); sizeclass == 0 { 1242 s.elemsize = nbytes 1243 s.nelems = 1 1244 s.divMul = 0 1245 } else { 1246 s.elemsize = uintptr(class_to_size[sizeclass]) 1247 s.nelems = nbytes / s.elemsize 1248 s.divMul = class_to_divmagic[sizeclass] 1249 } 1250 1251 // Initialize mark and allocation structures. 1252 s.freeindex = 0 1253 s.allocCache = ^uint64(0) // all 1s indicating all free. 1254 s.gcmarkBits = newMarkBits(s.nelems) 1255 s.allocBits = newAllocBits(s.nelems) 1256 1257 // It's safe to access h.sweepgen without the heap lock because it's 1258 // only ever updated with the world stopped and we run on the 1259 // systemstack which blocks a STW transition. 1260 atomic.Store(&s.sweepgen, h.sweepgen) 1261 1262 // Now that the span is filled in, set its state. This 1263 // is a publication barrier for the other fields in 1264 // the span. While valid pointers into this span 1265 // should never be visible until the span is returned, 1266 // if the garbage collector finds an invalid pointer, 1267 // access to the span may race with initialization of 1268 // the span. We resolve this race by atomically 1269 // setting the state after the span is fully 1270 // initialized, and atomically checking the state in 1271 // any situation where a pointer is suspect. 1272 s.state.set(mSpanInUse) 1273 } 1274 1275 // Commit and account for any scavenged memory that the span now owns. 1276 if scav != 0 { 1277 // sysUsed all the pages that are actually available 1278 // in the span since some of them might be scavenged. 1279 sysUsed(unsafe.Pointer(base), nbytes) 1280 atomic.Xadd64(&memstats.heap_released, -int64(scav)) 1281 } 1282 // Update stats. 1283 if typ == spanAllocHeap { 1284 atomic.Xadd64(&memstats.heap_inuse, int64(nbytes)) 1285 } 1286 if typ.manual() { 1287 // Manually managed memory doesn't count toward heap_sys. 1288 memstats.heap_sys.add(-int64(nbytes)) 1289 } 1290 // Update consistent stats. 1291 stats := memstats.heapStats.acquire() 1292 atomic.Xaddint64(&stats.committed, int64(scav)) 1293 atomic.Xaddint64(&stats.released, -int64(scav)) 1294 switch typ { 1295 case spanAllocHeap: 1296 atomic.Xaddint64(&stats.inHeap, int64(nbytes)) 1297 case spanAllocStack: 1298 atomic.Xaddint64(&stats.inStacks, int64(nbytes)) 1299 case spanAllocPtrScalarBits: 1300 atomic.Xaddint64(&stats.inPtrScalarBits, int64(nbytes)) 1301 case spanAllocWorkBuf: 1302 atomic.Xaddint64(&stats.inWorkBufs, int64(nbytes)) 1303 } 1304 memstats.heapStats.release() 1305 1306 // Publish the span in various locations. 1307 1308 // This is safe to call without the lock held because the slots 1309 // related to this span will only ever be read or modified by 1310 // this thread until pointers into the span are published (and 1311 // we execute a publication barrier at the end of this function 1312 // before that happens) or pageInUse is updated. 1313 h.setSpans(s.base(), npages, s) 1314 1315 if !typ.manual() { 1316 // Mark in-use span in arena page bitmap. 1317 // 1318 // This publishes the span to the page sweeper, so 1319 // it's imperative that the span be completely initialized 1320 // prior to this line. 1321 arena, pageIdx, pageMask := pageIndexOf(s.base()) 1322 atomic.Or8(&arena.pageInUse[pageIdx], pageMask) 1323 1324 // Update related page sweeper stats. 1325 h.pagesInUse.Add(int64(npages)) 1326 } 1327 1328 // Make sure the newly allocated span will be observed 1329 // by the GC before pointers into the span are published. 1330 publicationBarrier() 1331 1332 return s 1333 } 1334 1335 // Try to add at least npage pages of memory to the heap, 1336 // returning how much the heap grew by and whether it worked. 1337 // 1338 // h.lock must be held. 1339 func (h *mheap) grow(npage uintptr) (uintptr, bool) { 1340 assertLockHeld(&h.lock) 1341 1342 // We must grow the heap in whole palloc chunks. 1343 // We call sysMap below but note that because we 1344 // round up to pallocChunkPages which is on the order 1345 // of MiB (generally >= to the huge page size) we 1346 // won't be calling it too much. 1347 ask := alignUp(npage, pallocChunkPages) * pageSize 1348 1349 totalGrowth := uintptr(0) 1350 // This may overflow because ask could be very large 1351 // and is otherwise unrelated to h.curArena.base. 1352 end := h.curArena.base + ask 1353 nBase := alignUp(end, physPageSize) 1354 if nBase > h.curArena.end || /* overflow */ end < h.curArena.base { 1355 // Not enough room in the current arena. Allocate more 1356 // arena space. This may not be contiguous with the 1357 // current arena, so we have to request the full ask. 1358 av, asize := h.sysAlloc(ask) 1359 if av == nil { 1360 print("runtime: out of memory: cannot allocate ", ask, "-byte block (", memstats.heap_sys, " in use)\n") 1361 return 0, false 1362 } 1363 1364 if uintptr(av) == h.curArena.end { 1365 // The new space is contiguous with the old 1366 // space, so just extend the current space. 1367 h.curArena.end = uintptr(av) + asize 1368 } else { 1369 // The new space is discontiguous. Track what 1370 // remains of the current space and switch to 1371 // the new space. This should be rare. 1372 if size := h.curArena.end - h.curArena.base; size != 0 { 1373 // Transition this space from Reserved to Prepared and mark it 1374 // as released since we'll be able to start using it after updating 1375 // the page allocator and releasing the lock at any time. 1376 sysMap(unsafe.Pointer(h.curArena.base), size, &memstats.heap_sys) 1377 // Update stats. 1378 atomic.Xadd64(&memstats.heap_released, int64(size)) 1379 stats := memstats.heapStats.acquire() 1380 atomic.Xaddint64(&stats.released, int64(size)) 1381 memstats.heapStats.release() 1382 // Update the page allocator's structures to make this 1383 // space ready for allocation. 1384 h.pages.grow(h.curArena.base, size) 1385 totalGrowth += size 1386 } 1387 // Switch to the new space. 1388 h.curArena.base = uintptr(av) 1389 h.curArena.end = uintptr(av) + asize 1390 } 1391 1392 // Recalculate nBase. 1393 // We know this won't overflow, because sysAlloc returned 1394 // a valid region starting at h.curArena.base which is at 1395 // least ask bytes in size. 1396 nBase = alignUp(h.curArena.base+ask, physPageSize) 1397 } 1398 1399 // Grow into the current arena. 1400 v := h.curArena.base 1401 h.curArena.base = nBase 1402 1403 // Transition the space we're going to use from Reserved to Prepared. 1404 sysMap(unsafe.Pointer(v), nBase-v, &memstats.heap_sys) 1405 1406 // The memory just allocated counts as both released 1407 // and idle, even though it's not yet backed by spans. 1408 // 1409 // The allocation is always aligned to the heap arena 1410 // size which is always > physPageSize, so its safe to 1411 // just add directly to heap_released. 1412 atomic.Xadd64(&memstats.heap_released, int64(nBase-v)) 1413 stats := memstats.heapStats.acquire() 1414 atomic.Xaddint64(&stats.released, int64(nBase-v)) 1415 memstats.heapStats.release() 1416 1417 // Update the page allocator's structures to make this 1418 // space ready for allocation. 1419 h.pages.grow(v, nBase-v) 1420 totalGrowth += nBase - v 1421 return totalGrowth, true 1422 } 1423 1424 // Free the span back into the heap. 1425 func (h *mheap) freeSpan(s *mspan) { 1426 systemstack(func() { 1427 lock(&h.lock) 1428 if msanenabled { 1429 // Tell msan that this entire span is no longer in use. 1430 base := unsafe.Pointer(s.base()) 1431 bytes := s.npages << _PageShift 1432 msanfree(base, bytes) 1433 } 1434 if asanenabled { 1435 // Tell asan that this entire span is no longer in use. 1436 base := unsafe.Pointer(s.base()) 1437 bytes := s.npages << _PageShift 1438 asanpoison(base, bytes) 1439 } 1440 h.freeSpanLocked(s, spanAllocHeap) 1441 unlock(&h.lock) 1442 }) 1443 } 1444 1445 // freeManual frees a manually-managed span returned by allocManual. 1446 // typ must be the same as the spanAllocType passed to the allocManual that 1447 // allocated s. 1448 // 1449 // This must only be called when gcphase == _GCoff. See mSpanState for 1450 // an explanation. 1451 // 1452 // freeManual must be called on the system stack because it acquires 1453 // the heap lock. See mheap for details. 1454 // 1455 //go:systemstack 1456 func (h *mheap) freeManual(s *mspan, typ spanAllocType) { 1457 s.needzero = 1 1458 lock(&h.lock) 1459 h.freeSpanLocked(s, typ) 1460 unlock(&h.lock) 1461 } 1462 1463 func (h *mheap) freeSpanLocked(s *mspan, typ spanAllocType) { 1464 assertLockHeld(&h.lock) 1465 1466 switch s.state.get() { 1467 case mSpanManual: 1468 if s.allocCount != 0 { 1469 throw("mheap.freeSpanLocked - invalid stack free") 1470 } 1471 case mSpanInUse: 1472 if s.allocCount != 0 || s.sweepgen != h.sweepgen { 1473 print("mheap.freeSpanLocked - span ", s, " ptr ", hex(s.base()), " allocCount ", s.allocCount, " sweepgen ", s.sweepgen, "/", h.sweepgen, "\n") 1474 throw("mheap.freeSpanLocked - invalid free") 1475 } 1476 h.pagesInUse.Add(-int64(s.npages)) 1477 1478 // Clear in-use bit in arena page bitmap. 1479 arena, pageIdx, pageMask := pageIndexOf(s.base()) 1480 atomic.And8(&arena.pageInUse[pageIdx], ^pageMask) 1481 default: 1482 throw("mheap.freeSpanLocked - invalid span state") 1483 } 1484 1485 // Update stats. 1486 // 1487 // Mirrors the code in allocSpan. 1488 nbytes := s.npages * pageSize 1489 if typ == spanAllocHeap { 1490 atomic.Xadd64(&memstats.heap_inuse, -int64(nbytes)) 1491 } 1492 if typ.manual() { 1493 // Manually managed memory doesn't count toward heap_sys, so add it back. 1494 memstats.heap_sys.add(int64(nbytes)) 1495 } 1496 // Update consistent stats. 1497 stats := memstats.heapStats.acquire() 1498 switch typ { 1499 case spanAllocHeap: 1500 atomic.Xaddint64(&stats.inHeap, -int64(nbytes)) 1501 case spanAllocStack: 1502 atomic.Xaddint64(&stats.inStacks, -int64(nbytes)) 1503 case spanAllocPtrScalarBits: 1504 atomic.Xaddint64(&stats.inPtrScalarBits, -int64(nbytes)) 1505 case spanAllocWorkBuf: 1506 atomic.Xaddint64(&stats.inWorkBufs, -int64(nbytes)) 1507 } 1508 memstats.heapStats.release() 1509 1510 // Mark the space as free. 1511 h.pages.free(s.base(), s.npages, false) 1512 1513 // Free the span structure. We no longer have a use for it. 1514 s.state.set(mSpanDead) 1515 h.freeMSpanLocked(s) 1516 } 1517 1518 // scavengeAll acquires the heap lock (blocking any additional 1519 // manipulation of the page allocator) and iterates over the whole 1520 // heap, scavenging every free page available. 1521 func (h *mheap) scavengeAll() { 1522 // Disallow malloc or panic while holding the heap lock. We do 1523 // this here because this is a non-mallocgc entry-point to 1524 // the mheap API. 1525 gp := getg() 1526 gp.m.mallocing++ 1527 1528 lock(&h.lock) 1529 // Start a new scavenge generation so we have a chance to walk 1530 // over the whole heap. 1531 h.pages.scavengeStartGen() 1532 unlock(&h.lock) 1533 1534 released := h.pages.scavenge(^uintptr(0)) 1535 1536 lock(&h.pages.scav.lock) 1537 gen := h.pages.scav.gen 1538 unlock(&h.pages.scav.lock) 1539 1540 gp.m.mallocing-- 1541 1542 if debug.scavtrace > 0 { 1543 printScavTrace(gen, released, true) 1544 } 1545 } 1546 1547 //go:linkname runtime_debug_freeOSMemory runtime/debug.freeOSMemory 1548 func runtime_debug_freeOSMemory() { 1549 GC() 1550 systemstack(func() { mheap_.scavengeAll() }) 1551 } 1552 1553 // Initialize a new span with the given start and npages. 1554 func (span *mspan) init(base uintptr, npages uintptr) { 1555 // span is *not* zeroed. 1556 span.next = nil 1557 span.prev = nil 1558 span.list = nil 1559 span.startAddr = base 1560 span.npages = npages 1561 span.allocCount = 0 1562 span.spanclass = 0 1563 span.elemsize = 0 1564 span.speciallock.key = 0 1565 span.specials = nil 1566 span.needzero = 0 1567 span.freeindex = 0 1568 span.allocBits = nil 1569 span.gcmarkBits = nil 1570 span.state.set(mSpanDead) 1571 lockInit(&span.speciallock, lockRankMspanSpecial) 1572 } 1573 1574 func (span *mspan) inList() bool { 1575 return span.list != nil 1576 } 1577 1578 // Initialize an empty doubly-linked list. 1579 func (list *mSpanList) init() { 1580 list.first = nil 1581 list.last = nil 1582 } 1583 1584 func (list *mSpanList) remove(span *mspan) { 1585 if span.list != list { 1586 print("runtime: failed mSpanList.remove span.npages=", span.npages, 1587 " span=", span, " prev=", span.prev, " span.list=", span.list, " list=", list, "\n") 1588 throw("mSpanList.remove") 1589 } 1590 if list.first == span { 1591 list.first = span.next 1592 } else { 1593 span.prev.next = span.next 1594 } 1595 if list.last == span { 1596 list.last = span.prev 1597 } else { 1598 span.next.prev = span.prev 1599 } 1600 span.next = nil 1601 span.prev = nil 1602 span.list = nil 1603 } 1604 1605 func (list *mSpanList) isEmpty() bool { 1606 return list.first == nil 1607 } 1608 1609 func (list *mSpanList) insert(span *mspan) { 1610 if span.next != nil || span.prev != nil || span.list != nil { 1611 println("runtime: failed mSpanList.insert", span, span.next, span.prev, span.list) 1612 throw("mSpanList.insert") 1613 } 1614 span.next = list.first 1615 if list.first != nil { 1616 // The list contains at least one span; link it in. 1617 // The last span in the list doesn't change. 1618 list.first.prev = span 1619 } else { 1620 // The list contains no spans, so this is also the last span. 1621 list.last = span 1622 } 1623 list.first = span 1624 span.list = list 1625 } 1626 1627 func (list *mSpanList) insertBack(span *mspan) { 1628 if span.next != nil || span.prev != nil || span.list != nil { 1629 println("runtime: failed mSpanList.insertBack", span, span.next, span.prev, span.list) 1630 throw("mSpanList.insertBack") 1631 } 1632 span.prev = list.last 1633 if list.last != nil { 1634 // The list contains at least one span. 1635 list.last.next = span 1636 } else { 1637 // The list contains no spans, so this is also the first span. 1638 list.first = span 1639 } 1640 list.last = span 1641 span.list = list 1642 } 1643 1644 // takeAll removes all spans from other and inserts them at the front 1645 // of list. 1646 func (list *mSpanList) takeAll(other *mSpanList) { 1647 if other.isEmpty() { 1648 return 1649 } 1650 1651 // Reparent everything in other to list. 1652 for s := other.first; s != nil; s = s.next { 1653 s.list = list 1654 } 1655 1656 // Concatenate the lists. 1657 if list.isEmpty() { 1658 *list = *other 1659 } else { 1660 // Neither list is empty. Put other before list. 1661 other.last.next = list.first 1662 list.first.prev = other.last 1663 list.first = other.first 1664 } 1665 1666 other.first, other.last = nil, nil 1667 } 1668 1669 const ( 1670 _KindSpecialFinalizer = 1 1671 _KindSpecialProfile = 2 1672 // _KindSpecialReachable is a special used for tracking 1673 // reachability during testing. 1674 _KindSpecialReachable = 3 1675 // Note: The finalizer special must be first because if we're freeing 1676 // an object, a finalizer special will cause the freeing operation 1677 // to abort, and we want to keep the other special records around 1678 // if that happens. 1679 ) 1680 1681 //go:notinheap 1682 type special struct { 1683 next *special // linked list in span 1684 offset uint16 // span offset of object 1685 kind byte // kind of special 1686 } 1687 1688 // spanHasSpecials marks a span as having specials in the arena bitmap. 1689 func spanHasSpecials(s *mspan) { 1690 arenaPage := (s.base() / pageSize) % pagesPerArena 1691 ai := arenaIndex(s.base()) 1692 ha := mheap_.arenas[ai.l1()][ai.l2()] 1693 atomic.Or8(&ha.pageSpecials[arenaPage/8], uint8(1)<<(arenaPage%8)) 1694 } 1695 1696 // spanHasNoSpecials marks a span as having no specials in the arena bitmap. 1697 func spanHasNoSpecials(s *mspan) { 1698 arenaPage := (s.base() / pageSize) % pagesPerArena 1699 ai := arenaIndex(s.base()) 1700 ha := mheap_.arenas[ai.l1()][ai.l2()] 1701 atomic.And8(&ha.pageSpecials[arenaPage/8], ^(uint8(1) << (arenaPage % 8))) 1702 } 1703 1704 // Adds the special record s to the list of special records for 1705 // the object p. All fields of s should be filled in except for 1706 // offset & next, which this routine will fill in. 1707 // Returns true if the special was successfully added, false otherwise. 1708 // (The add will fail only if a record with the same p and s->kind 1709 // already exists.) 1710 func addspecial(p unsafe.Pointer, s *special) bool { 1711 span := spanOfHeap(uintptr(p)) 1712 if span == nil { 1713 throw("addspecial on invalid pointer") 1714 } 1715 1716 // Ensure that the span is swept. 1717 // Sweeping accesses the specials list w/o locks, so we have 1718 // to synchronize with it. And it's just much safer. 1719 mp := acquirem() 1720 span.ensureSwept() 1721 1722 offset := uintptr(p) - span.base() 1723 kind := s.kind 1724 1725 lock(&span.speciallock) 1726 1727 // Find splice point, check for existing record. 1728 t := &span.specials 1729 for { 1730 x := *t 1731 if x == nil { 1732 break 1733 } 1734 if offset == uintptr(x.offset) && kind == x.kind { 1735 unlock(&span.speciallock) 1736 releasem(mp) 1737 return false // already exists 1738 } 1739 if offset < uintptr(x.offset) || (offset == uintptr(x.offset) && kind < x.kind) { 1740 break 1741 } 1742 t = &x.next 1743 } 1744 1745 // Splice in record, fill in offset. 1746 s.offset = uint16(offset) 1747 s.next = *t 1748 *t = s 1749 spanHasSpecials(span) 1750 unlock(&span.speciallock) 1751 releasem(mp) 1752 1753 return true 1754 } 1755 1756 // Removes the Special record of the given kind for the object p. 1757 // Returns the record if the record existed, nil otherwise. 1758 // The caller must FixAlloc_Free the result. 1759 func removespecial(p unsafe.Pointer, kind uint8) *special { 1760 span := spanOfHeap(uintptr(p)) 1761 if span == nil { 1762 throw("removespecial on invalid pointer") 1763 } 1764 1765 // Ensure that the span is swept. 1766 // Sweeping accesses the specials list w/o locks, so we have 1767 // to synchronize with it. And it's just much safer. 1768 mp := acquirem() 1769 span.ensureSwept() 1770 1771 offset := uintptr(p) - span.base() 1772 1773 var result *special 1774 lock(&span.speciallock) 1775 t := &span.specials 1776 for { 1777 s := *t 1778 if s == nil { 1779 break 1780 } 1781 // This function is used for finalizers only, so we don't check for 1782 // "interior" specials (p must be exactly equal to s->offset). 1783 if offset == uintptr(s.offset) && kind == s.kind { 1784 *t = s.next 1785 result = s 1786 break 1787 } 1788 t = &s.next 1789 } 1790 if span.specials == nil { 1791 spanHasNoSpecials(span) 1792 } 1793 unlock(&span.speciallock) 1794 releasem(mp) 1795 return result 1796 } 1797 1798 // The described object has a finalizer set for it. 1799 // 1800 // specialfinalizer is allocated from non-GC'd memory, so any heap 1801 // pointers must be specially handled. 1802 // 1803 //go:notinheap 1804 type specialfinalizer struct { 1805 special special 1806 fn *funcval // May be a heap pointer. 1807 nret uintptr 1808 fint *_type // May be a heap pointer, but always live. 1809 ot *ptrtype // May be a heap pointer, but always live. 1810 } 1811 1812 // Adds a finalizer to the object p. Returns true if it succeeded. 1813 func addfinalizer(p unsafe.Pointer, f *funcval, nret uintptr, fint *_type, ot *ptrtype) bool { 1814 lock(&mheap_.speciallock) 1815 s := (*specialfinalizer)(mheap_.specialfinalizeralloc.alloc()) 1816 unlock(&mheap_.speciallock) 1817 s.special.kind = _KindSpecialFinalizer 1818 s.fn = f 1819 s.nret = nret 1820 s.fint = fint 1821 s.ot = ot 1822 if addspecial(p, &s.special) { 1823 // This is responsible for maintaining the same 1824 // GC-related invariants as markrootSpans in any 1825 // situation where it's possible that markrootSpans 1826 // has already run but mark termination hasn't yet. 1827 if gcphase != _GCoff { 1828 base, _, _ := findObject(uintptr(p), 0, 0) 1829 mp := acquirem() 1830 gcw := &mp.p.ptr().gcw 1831 // Mark everything reachable from the object 1832 // so it's retained for the finalizer. 1833 scanobject(base, gcw) 1834 // Mark the finalizer itself, since the 1835 // special isn't part of the GC'd heap. 1836 scanblock(uintptr(unsafe.Pointer(&s.fn)), goarch.PtrSize, &oneptrmask[0], gcw, nil) 1837 releasem(mp) 1838 } 1839 return true 1840 } 1841 1842 // There was an old finalizer 1843 lock(&mheap_.speciallock) 1844 mheap_.specialfinalizeralloc.free(unsafe.Pointer(s)) 1845 unlock(&mheap_.speciallock) 1846 return false 1847 } 1848 1849 // Removes the finalizer (if any) from the object p. 1850 func removefinalizer(p unsafe.Pointer) { 1851 s := (*specialfinalizer)(unsafe.Pointer(removespecial(p, _KindSpecialFinalizer))) 1852 if s == nil { 1853 return // there wasn't a finalizer to remove 1854 } 1855 lock(&mheap_.speciallock) 1856 mheap_.specialfinalizeralloc.free(unsafe.Pointer(s)) 1857 unlock(&mheap_.speciallock) 1858 } 1859 1860 // The described object is being heap profiled. 1861 // 1862 //go:notinheap 1863 type specialprofile struct { 1864 special special 1865 b *bucket 1866 } 1867 1868 // Set the heap profile bucket associated with addr to b. 1869 func setprofilebucket(p unsafe.Pointer, b *bucket) { 1870 lock(&mheap_.speciallock) 1871 s := (*specialprofile)(mheap_.specialprofilealloc.alloc()) 1872 unlock(&mheap_.speciallock) 1873 s.special.kind = _KindSpecialProfile 1874 s.b = b 1875 if !addspecial(p, &s.special) { 1876 throw("setprofilebucket: profile already set") 1877 } 1878 } 1879 1880 // specialReachable tracks whether an object is reachable on the next 1881 // GC cycle. This is used by testing. 1882 type specialReachable struct { 1883 special special 1884 done bool 1885 reachable bool 1886 } 1887 1888 // specialsIter helps iterate over specials lists. 1889 type specialsIter struct { 1890 pprev **special 1891 s *special 1892 } 1893 1894 func newSpecialsIter(span *mspan) specialsIter { 1895 return specialsIter{&span.specials, span.specials} 1896 } 1897 1898 func (i *specialsIter) valid() bool { 1899 return i.s != nil 1900 } 1901 1902 func (i *specialsIter) next() { 1903 i.pprev = &i.s.next 1904 i.s = *i.pprev 1905 } 1906 1907 // unlinkAndNext removes the current special from the list and moves 1908 // the iterator to the next special. It returns the unlinked special. 1909 func (i *specialsIter) unlinkAndNext() *special { 1910 cur := i.s 1911 i.s = cur.next 1912 *i.pprev = i.s 1913 return cur 1914 } 1915 1916 // freeSpecial performs any cleanup on special s and deallocates it. 1917 // s must already be unlinked from the specials list. 1918 func freeSpecial(s *special, p unsafe.Pointer, size uintptr) { 1919 switch s.kind { 1920 case _KindSpecialFinalizer: 1921 sf := (*specialfinalizer)(unsafe.Pointer(s)) 1922 queuefinalizer(p, sf.fn, sf.nret, sf.fint, sf.ot) 1923 lock(&mheap_.speciallock) 1924 mheap_.specialfinalizeralloc.free(unsafe.Pointer(sf)) 1925 unlock(&mheap_.speciallock) 1926 case _KindSpecialProfile: 1927 sp := (*specialprofile)(unsafe.Pointer(s)) 1928 mProf_Free(sp.b, size) 1929 lock(&mheap_.speciallock) 1930 mheap_.specialprofilealloc.free(unsafe.Pointer(sp)) 1931 unlock(&mheap_.speciallock) 1932 case _KindSpecialReachable: 1933 sp := (*specialReachable)(unsafe.Pointer(s)) 1934 sp.done = true 1935 // The creator frees these. 1936 default: 1937 throw("bad special kind") 1938 panic("not reached") 1939 } 1940 } 1941 1942 // gcBits is an alloc/mark bitmap. This is always used as *gcBits. 1943 // 1944 //go:notinheap 1945 type gcBits uint8 1946 1947 // bytep returns a pointer to the n'th byte of b. 1948 func (b *gcBits) bytep(n uintptr) *uint8 { 1949 return addb((*uint8)(b), n) 1950 } 1951 1952 // bitp returns a pointer to the byte containing bit n and a mask for 1953 // selecting that bit from *bytep. 1954 func (b *gcBits) bitp(n uintptr) (bytep *uint8, mask uint8) { 1955 return b.bytep(n / 8), 1 << (n % 8) 1956 } 1957 1958 const gcBitsChunkBytes = uintptr(64 << 10) 1959 const gcBitsHeaderBytes = unsafe.Sizeof(gcBitsHeader{}) 1960 1961 type gcBitsHeader struct { 1962 free uintptr // free is the index into bits of the next free byte. 1963 next uintptr // *gcBits triggers recursive type bug. (issue 14620) 1964 } 1965 1966 //go:notinheap 1967 type gcBitsArena struct { 1968 // gcBitsHeader // side step recursive type bug (issue 14620) by including fields by hand. 1969 free uintptr // free is the index into bits of the next free byte; read/write atomically 1970 next *gcBitsArena 1971 bits [gcBitsChunkBytes - gcBitsHeaderBytes]gcBits 1972 } 1973 1974 var gcBitsArenas struct { 1975 lock mutex 1976 free *gcBitsArena 1977 next *gcBitsArena // Read atomically. Write atomically under lock. 1978 current *gcBitsArena 1979 previous *gcBitsArena 1980 } 1981 1982 // tryAlloc allocates from b or returns nil if b does not have enough room. 1983 // This is safe to call concurrently. 1984 func (b *gcBitsArena) tryAlloc(bytes uintptr) *gcBits { 1985 if b == nil || atomic.Loaduintptr(&b.free)+bytes > uintptr(len(b.bits)) { 1986 return nil 1987 } 1988 // Try to allocate from this block. 1989 end := atomic.Xadduintptr(&b.free, bytes) 1990 if end > uintptr(len(b.bits)) { 1991 return nil 1992 } 1993 // There was enough room. 1994 start := end - bytes 1995 return &b.bits[start] 1996 } 1997 1998 // newMarkBits returns a pointer to 8 byte aligned bytes 1999 // to be used for a span's mark bits. 2000 func newMarkBits(nelems uintptr) *gcBits { 2001 blocksNeeded := uintptr((nelems + 63) / 64) 2002 bytesNeeded := blocksNeeded * 8 2003 2004 // Try directly allocating from the current head arena. 2005 head := (*gcBitsArena)(atomic.Loadp(unsafe.Pointer(&gcBitsArenas.next))) 2006 if p := head.tryAlloc(bytesNeeded); p != nil { 2007 return p 2008 } 2009 2010 // There's not enough room in the head arena. We may need to 2011 // allocate a new arena. 2012 lock(&gcBitsArenas.lock) 2013 // Try the head arena again, since it may have changed. Now 2014 // that we hold the lock, the list head can't change, but its 2015 // free position still can. 2016 if p := gcBitsArenas.next.tryAlloc(bytesNeeded); p != nil { 2017 unlock(&gcBitsArenas.lock) 2018 return p 2019 } 2020 2021 // Allocate a new arena. This may temporarily drop the lock. 2022 fresh := newArenaMayUnlock() 2023 // If newArenaMayUnlock dropped the lock, another thread may 2024 // have put a fresh arena on the "next" list. Try allocating 2025 // from next again. 2026 if p := gcBitsArenas.next.tryAlloc(bytesNeeded); p != nil { 2027 // Put fresh back on the free list. 2028 // TODO: Mark it "already zeroed" 2029 fresh.next = gcBitsArenas.free 2030 gcBitsArenas.free = fresh 2031 unlock(&gcBitsArenas.lock) 2032 return p 2033 } 2034 2035 // Allocate from the fresh arena. We haven't linked it in yet, so 2036 // this cannot race and is guaranteed to succeed. 2037 p := fresh.tryAlloc(bytesNeeded) 2038 if p == nil { 2039 throw("markBits overflow") 2040 } 2041 2042 // Add the fresh arena to the "next" list. 2043 fresh.next = gcBitsArenas.next 2044 atomic.StorepNoWB(unsafe.Pointer(&gcBitsArenas.next), unsafe.Pointer(fresh)) 2045 2046 unlock(&gcBitsArenas.lock) 2047 return p 2048 } 2049 2050 // newAllocBits returns a pointer to 8 byte aligned bytes 2051 // to be used for this span's alloc bits. 2052 // newAllocBits is used to provide newly initialized spans 2053 // allocation bits. For spans not being initialized the 2054 // mark bits are repurposed as allocation bits when 2055 // the span is swept. 2056 func newAllocBits(nelems uintptr) *gcBits { 2057 return newMarkBits(nelems) 2058 } 2059 2060 // nextMarkBitArenaEpoch establishes a new epoch for the arenas 2061 // holding the mark bits. The arenas are named relative to the 2062 // current GC cycle which is demarcated by the call to finishweep_m. 2063 // 2064 // All current spans have been swept. 2065 // During that sweep each span allocated room for its gcmarkBits in 2066 // gcBitsArenas.next block. gcBitsArenas.next becomes the gcBitsArenas.current 2067 // where the GC will mark objects and after each span is swept these bits 2068 // will be used to allocate objects. 2069 // gcBitsArenas.current becomes gcBitsArenas.previous where the span's 2070 // gcAllocBits live until all the spans have been swept during this GC cycle. 2071 // The span's sweep extinguishes all the references to gcBitsArenas.previous 2072 // by pointing gcAllocBits into the gcBitsArenas.current. 2073 // The gcBitsArenas.previous is released to the gcBitsArenas.free list. 2074 func nextMarkBitArenaEpoch() { 2075 lock(&gcBitsArenas.lock) 2076 if gcBitsArenas.previous != nil { 2077 if gcBitsArenas.free == nil { 2078 gcBitsArenas.free = gcBitsArenas.previous 2079 } else { 2080 // Find end of previous arenas. 2081 last := gcBitsArenas.previous 2082 for last = gcBitsArenas.previous; last.next != nil; last = last.next { 2083 } 2084 last.next = gcBitsArenas.free 2085 gcBitsArenas.free = gcBitsArenas.previous 2086 } 2087 } 2088 gcBitsArenas.previous = gcBitsArenas.current 2089 gcBitsArenas.current = gcBitsArenas.next 2090 atomic.StorepNoWB(unsafe.Pointer(&gcBitsArenas.next), nil) // newMarkBits calls newArena when needed 2091 unlock(&gcBitsArenas.lock) 2092 } 2093 2094 // newArenaMayUnlock allocates and zeroes a gcBits arena. 2095 // The caller must hold gcBitsArena.lock. This may temporarily release it. 2096 func newArenaMayUnlock() *gcBitsArena { 2097 var result *gcBitsArena 2098 if gcBitsArenas.free == nil { 2099 unlock(&gcBitsArenas.lock) 2100 result = (*gcBitsArena)(sysAlloc(gcBitsChunkBytes, &memstats.gcMiscSys)) 2101 if result == nil { 2102 throw("runtime: cannot allocate memory") 2103 } 2104 lock(&gcBitsArenas.lock) 2105 } else { 2106 result = gcBitsArenas.free 2107 gcBitsArenas.free = gcBitsArenas.free.next 2108 memclrNoHeapPointers(unsafe.Pointer(result), gcBitsChunkBytes) 2109 } 2110 result.next = nil 2111 // If result.bits is not 8 byte aligned adjust index so 2112 // that &result.bits[result.free] is 8 byte aligned. 2113 if uintptr(unsafe.Offsetof(gcBitsArena{}.bits))&7 == 0 { 2114 result.free = 0 2115 } else { 2116 result.free = 8 - (uintptr(unsafe.Pointer(&result.bits[0])) & 7) 2117 } 2118 return result 2119 } 2120