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