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