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