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