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