Source file src/runtime/malloc.go
1 // Copyright 2014 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 // Memory allocator. 6 // 7 // This was originally based on tcmalloc, but has diverged quite a bit. 8 // http://goog-perftools.sourceforge.net/doc/tcmalloc.html 9 10 // The main allocator works in runs of pages. 11 // Small allocation sizes (up to and including 32 kB) are 12 // rounded to one of about 70 size classes, each of which 13 // has its own free set of objects of exactly that size. 14 // Any free page of memory can be split into a set of objects 15 // of one size class, which are then managed using a free bitmap. 16 // 17 // The allocator's data structures are: 18 // 19 // fixalloc: a free-list allocator for fixed-size off-heap objects, 20 // used to manage storage used by the allocator. 21 // mheap: the malloc heap, managed at page (8192-byte) granularity. 22 // mspan: a run of in-use pages managed by the mheap. 23 // mcentral: collects all spans of a given size class. 24 // mcache: a per-P cache of mspans with free space. 25 // mstats: allocation statistics. 26 // 27 // Allocating a small object proceeds up a hierarchy of caches: 28 // 29 // 1. Round the size up to one of the small size classes 30 // and look in the corresponding mspan in this P's mcache. 31 // Scan the mspan's free bitmap to find a free slot. 32 // If there is a free slot, allocate it. 33 // This can all be done without acquiring a lock. 34 // 35 // 2. If the mspan has no free slots, obtain a new mspan 36 // from the mcentral's list of mspans of the required size 37 // class that have free space. 38 // Obtaining a whole span amortizes the cost of locking 39 // the mcentral. 40 // 41 // 3. If the mcentral's mspan list is empty, obtain a run 42 // of pages from the mheap to use for the mspan. 43 // 44 // 4. If the mheap is empty or has no page runs large enough, 45 // allocate a new group of pages (at least 1MB) from the 46 // operating system. Allocating a large run of pages 47 // amortizes the cost of talking to the operating system. 48 // 49 // Sweeping an mspan and freeing objects on it proceeds up a similar 50 // hierarchy: 51 // 52 // 1. If the mspan is being swept in response to allocation, it 53 // is returned to the mcache to satisfy the allocation. 54 // 55 // 2. Otherwise, if the mspan still has allocated objects in it, 56 // it is placed on the mcentral free list for the mspan's size 57 // class. 58 // 59 // 3. Otherwise, if all objects in the mspan are free, the mspan's 60 // pages are returned to the mheap and the mspan is now dead. 61 // 62 // Allocating and freeing a large object uses the mheap 63 // directly, bypassing the mcache and mcentral. 64 // 65 // If mspan.needzero is false, then free object slots in the mspan are 66 // already zeroed. Otherwise if needzero is true, objects are zeroed as 67 // they are allocated. There are various benefits to delaying zeroing 68 // this way: 69 // 70 // 1. Stack frame allocation can avoid zeroing altogether. 71 // 72 // 2. It exhibits better temporal locality, since the program is 73 // probably about to write to the memory. 74 // 75 // 3. We don't zero pages that never get reused. 76 77 // Virtual memory layout 78 // 79 // The heap consists of a set of arenas, which are 64MB on 64-bit and 80 // 4MB on 32-bit (heapArenaBytes). Each arena's start address is also 81 // aligned to the arena size. 82 // 83 // Each arena has an associated heapArena object that stores the 84 // metadata for that arena: the heap bitmap for all words in the arena 85 // and the span map for all pages in the arena. heapArena objects are 86 // themselves allocated off-heap. 87 // 88 // Since arenas are aligned, the address space can be viewed as a 89 // series of arena frames. The arena map (mheap_.arenas) maps from 90 // arena frame number to *heapArena, or nil for parts of the address 91 // space not backed by the Go heap. The arena map is structured as a 92 // two-level array consisting of a "L1" arena map and many "L2" arena 93 // maps; however, since arenas are large, on many architectures, the 94 // arena map consists of a single, large L2 map. 95 // 96 // The arena map covers the entire possible address space, allowing 97 // the Go heap to use any part of the address space. The allocator 98 // attempts to keep arenas contiguous so that large spans (and hence 99 // large objects) can cross arenas. 100 101 package runtime 102 103 import ( 104 "internal/goarch" 105 "internal/goos" 106 "internal/runtime/atomic" 107 "internal/runtime/gc" 108 "internal/runtime/math" 109 "internal/runtime/sys" 110 "unsafe" 111 ) 112 113 const ( 114 maxTinySize = _TinySize 115 tinySizeClass = _TinySizeClass 116 maxSmallSize = gc.MaxSmallSize 117 pageSize = 1 << gc.PageShift 118 pageMask = pageSize - 1 119 120 // Unused. Left for viewcore. 121 _PageSize = pageSize 122 minSizeForMallocHeader = gc.MinSizeForMallocHeader 123 mallocHeaderSize = gc.MallocHeaderSize 124 125 // _64bit = 1 on 64-bit systems, 0 on 32-bit systems 126 _64bit = 1 << (^uintptr(0) >> 63) / 2 127 128 // Tiny allocator parameters, see "Tiny allocator" comment in malloc.go. 129 _TinySize = 16 130 _TinySizeClass = int8(2) 131 132 _FixAllocChunk = 16 << 10 // Chunk size for FixAlloc 133 134 // Per-P, per order stack segment cache size. 135 _StackCacheSize = 32 * 1024 136 137 // Number of orders that get caching. Order 0 is FixedStack 138 // and each successive order is twice as large. 139 // We want to cache 2KB, 4KB, 8KB, and 16KB stacks. Larger stacks 140 // will be allocated directly. 141 // Since FixedStack is different on different systems, we 142 // must vary NumStackOrders to keep the same maximum cached size. 143 // OS | FixedStack | NumStackOrders 144 // -----------------+------------+--------------- 145 // linux/darwin/bsd | 2KB | 4 146 // windows/32 | 4KB | 3 147 // windows/64 | 8KB | 2 148 // plan9 | 4KB | 3 149 _NumStackOrders = 4 - goarch.PtrSize/4*goos.IsWindows - 1*goos.IsPlan9 150 151 // heapAddrBits is the number of bits in a heap address. On 152 // amd64, addresses are sign-extended beyond heapAddrBits. On 153 // other arches, they are zero-extended. 154 // 155 // On most 64-bit platforms, we limit this to 48 bits based on a 156 // combination of hardware and OS limitations. 157 // 158 // amd64 hardware limits addresses to 48 bits, sign-extended 159 // to 64 bits. Addresses where the top 16 bits are not either 160 // all 0 or all 1 are "non-canonical" and invalid. Because of 161 // these "negative" addresses, we offset addresses by 1<<47 162 // (arenaBaseOffset) on amd64 before computing indexes into 163 // the heap arenas index. In 2017, amd64 hardware added 164 // support for 57 bit addresses; however, currently only Linux 165 // supports this extension and the kernel will never choose an 166 // address above 1<<47 unless mmap is called with a hint 167 // address above 1<<47 (which we never do). 168 // 169 // arm64 hardware (as of ARMv8) limits user addresses to 48 170 // bits, in the range [0, 1<<48). 171 // 172 // ppc64, mips64, and s390x support arbitrary 64 bit addresses 173 // in hardware. On Linux, Go leans on stricter OS limits. Based 174 // on Linux's processor.h, the user address space is limited as 175 // follows on 64-bit architectures: 176 // 177 // Architecture Name Maximum Value (exclusive) 178 // --------------------------------------------------------------------- 179 // amd64 TASK_SIZE_MAX 0x007ffffffff000 (47 bit addresses) 180 // arm64 TASK_SIZE_64 0x01000000000000 (48 bit addresses) 181 // ppc64{,le} TASK_SIZE_USER64 0x00400000000000 (46 bit addresses) 182 // mips64{,le} TASK_SIZE64 0x00010000000000 (40 bit addresses) 183 // s390x TASK_SIZE 1<<64 (64 bit addresses) 184 // 185 // These limits may increase over time, but are currently at 186 // most 48 bits except on s390x. On all architectures, Linux 187 // starts placing mmap'd regions at addresses that are 188 // significantly below 48 bits, so even if it's possible to 189 // exceed Go's 48 bit limit, it's extremely unlikely in 190 // practice. 191 // 192 // On 32-bit platforms, we accept the full 32-bit address 193 // space because doing so is cheap. 194 // mips32 only has access to the low 2GB of virtual memory, so 195 // we further limit it to 31 bits. 196 // 197 // On ios/arm64, although 64-bit pointers are presumably 198 // available, pointers are truncated to 33 bits in iOS <14. 199 // Furthermore, only the top 4 GiB of the address space are 200 // actually available to the application. In iOS >=14, more 201 // of the address space is available, and the OS can now 202 // provide addresses outside of those 33 bits. Pick 40 bits 203 // as a reasonable balance between address space usage by the 204 // page allocator, and flexibility for what mmap'd regions 205 // we'll accept for the heap. We can't just move to the full 206 // 48 bits because this uses too much address space for older 207 // iOS versions. 208 // TODO(mknyszek): Once iOS <14 is deprecated, promote ios/arm64 209 // to a 48-bit address space like every other arm64 platform. 210 // 211 // WebAssembly currently has a limit of 4GB linear memory. 212 heapAddrBits = (_64bit*(1-goarch.IsWasm)*(1-goos.IsIos*goarch.IsArm64))*48 + (1-_64bit+goarch.IsWasm)*(32-(goarch.IsMips+goarch.IsMipsle)) + 40*goos.IsIos*goarch.IsArm64 213 214 // maxAlloc is the maximum size of an allocation. On 64-bit, 215 // it's theoretically possible to allocate 1<<heapAddrBits bytes. On 216 // 32-bit, however, this is one less than 1<<32 because the 217 // number of bytes in the address space doesn't actually fit 218 // in a uintptr. 219 maxAlloc = (1 << heapAddrBits) - (1-_64bit)*1 220 221 // The number of bits in a heap address, the size of heap 222 // arenas, and the L1 and L2 arena map sizes are related by 223 // 224 // (1 << addr bits) = arena size * L1 entries * L2 entries 225 // 226 // Currently, we balance these as follows: 227 // 228 // Platform Addr bits Arena size L1 entries L2 entries 229 // -------------- --------- ---------- ---------- ----------- 230 // */64-bit 48 64MB 1 4M (32MB) 231 // windows/64-bit 48 4MB 64 1M (8MB) 232 // ios/arm64 40 4MB 1 256K (2MB) 233 // */32-bit 32 4MB 1 1024 (4KB) 234 // */mips(le) 31 4MB 1 512 (2KB) 235 236 // heapArenaBytes is the size of a heap arena. The heap 237 // consists of mappings of size heapArenaBytes, aligned to 238 // heapArenaBytes. The initial heap mapping is one arena. 239 // 240 // This is currently 64MB on 64-bit non-Windows and 4MB on 241 // 32-bit and on Windows. We use smaller arenas on Windows 242 // because all committed memory is charged to the process, 243 // even if it's not touched. Hence, for processes with small 244 // heaps, the mapped arena space needs to be commensurate. 245 // This is particularly important with the race detector, 246 // since it significantly amplifies the cost of committed 247 // memory. 248 heapArenaBytes = 1 << logHeapArenaBytes 249 250 heapArenaWords = heapArenaBytes / goarch.PtrSize 251 252 // logHeapArenaBytes is log_2 of heapArenaBytes. For clarity, 253 // prefer using heapArenaBytes where possible (we need the 254 // constant to compute some other constants). 255 logHeapArenaBytes = (6+20)*(_64bit*(1-goos.IsWindows)*(1-goarch.IsWasm)*(1-goos.IsIos*goarch.IsArm64)) + (2+20)*(_64bit*goos.IsWindows) + (2+20)*(1-_64bit) + (2+20)*goarch.IsWasm + (2+20)*goos.IsIos*goarch.IsArm64 256 257 // heapArenaBitmapWords is the size of each heap arena's bitmap in uintptrs. 258 heapArenaBitmapWords = heapArenaWords / (8 * goarch.PtrSize) 259 260 pagesPerArena = heapArenaBytes / pageSize 261 262 // arenaL1Bits is the number of bits of the arena number 263 // covered by the first level arena map. 264 // 265 // This number should be small, since the first level arena 266 // map requires PtrSize*(1<<arenaL1Bits) of space in the 267 // binary's BSS. It can be zero, in which case the first level 268 // index is effectively unused. There is a performance benefit 269 // to this, since the generated code can be more efficient, 270 // but comes at the cost of having a large L2 mapping. 271 // 272 // We use the L1 map on 64-bit Windows because the arena size 273 // is small, but the address space is still 48 bits, and 274 // there's a high cost to having a large L2. 275 arenaL1Bits = 6 * (_64bit * goos.IsWindows) 276 277 // arenaL2Bits is the number of bits of the arena number 278 // covered by the second level arena index. 279 // 280 // The size of each arena map allocation is proportional to 281 // 1<<arenaL2Bits, so it's important that this not be too 282 // large. 48 bits leads to 32MB arena index allocations, which 283 // is about the practical threshold. 284 arenaL2Bits = heapAddrBits - logHeapArenaBytes - arenaL1Bits 285 286 // arenaL1Shift is the number of bits to shift an arena frame 287 // number by to compute an index into the first level arena map. 288 arenaL1Shift = arenaL2Bits 289 290 // arenaBits is the total bits in a combined arena map index. 291 // This is split between the index into the L1 arena map and 292 // the L2 arena map. 293 arenaBits = arenaL1Bits + arenaL2Bits 294 295 // arenaBaseOffset is the pointer value that corresponds to 296 // index 0 in the heap arena map. 297 // 298 // On amd64, the address space is 48 bits, sign extended to 64 299 // bits. This offset lets us handle "negative" addresses (or 300 // high addresses if viewed as unsigned). 301 // 302 // On aix/ppc64, this offset allows to keep the heapAddrBits to 303 // 48. Otherwise, it would be 60 in order to handle mmap addresses 304 // (in range 0x0a00000000000000 - 0x0afffffffffffff). But in this 305 // case, the memory reserved in (s *pageAlloc).init for chunks 306 // is causing important slowdowns. 307 // 308 // On other platforms, the user address space is contiguous 309 // and starts at 0, so no offset is necessary. 310 arenaBaseOffset = 0xffff800000000000*goarch.IsAmd64 + 0x0a00000000000000*goos.IsAix 311 // A typed version of this constant that will make it into DWARF (for viewcore). 312 arenaBaseOffsetUintptr = uintptr(arenaBaseOffset) 313 314 // Max number of threads to run garbage collection. 315 // 2, 3, and 4 are all plausible maximums depending 316 // on the hardware details of the machine. The garbage 317 // collector scales well to 32 cpus. 318 _MaxGcproc = 32 319 320 // minLegalPointer is the smallest possible legal pointer. 321 // This is the smallest possible architectural page size, 322 // since we assume that the first page is never mapped. 323 // 324 // This should agree with minZeroPage in the compiler. 325 minLegalPointer uintptr = 4096 326 327 // minHeapForMetadataHugePages sets a threshold on when certain kinds of 328 // heap metadata, currently the arenas map L2 entries and page alloc bitmap 329 // mappings, are allowed to be backed by huge pages. If the heap goal ever 330 // exceeds this threshold, then huge pages are enabled. 331 // 332 // These numbers are chosen with the assumption that huge pages are on the 333 // order of a few MiB in size. 334 // 335 // The kind of metadata this applies to has a very low overhead when compared 336 // to address space used, but their constant overheads for small heaps would 337 // be very high if they were to be backed by huge pages (e.g. a few MiB makes 338 // a huge difference for an 8 MiB heap, but barely any difference for a 1 GiB 339 // heap). The benefit of huge pages is also not worth it for small heaps, 340 // because only a very, very small part of the metadata is used for small heaps. 341 // 342 // N.B. If the heap goal exceeds the threshold then shrinks to a very small size 343 // again, then huge pages will still be enabled for this mapping. The reason is that 344 // there's no point unless we're also returning the physical memory for these 345 // metadata mappings back to the OS. That would be quite complex to do in general 346 // as the heap is likely fragmented after a reduction in heap size. 347 minHeapForMetadataHugePages = 1 << 30 348 ) 349 350 // physPageSize is the size in bytes of the OS's physical pages. 351 // Mapping and unmapping operations must be done at multiples of 352 // physPageSize. 353 // 354 // This must be set by the OS init code (typically in osinit) before 355 // mallocinit. 356 var physPageSize uintptr 357 358 // physHugePageSize is the size in bytes of the OS's default physical huge 359 // page size whose allocation is opaque to the application. It is assumed 360 // and verified to be a power of two. 361 // 362 // If set, this must be set by the OS init code (typically in osinit) before 363 // mallocinit. However, setting it at all is optional, and leaving the default 364 // value is always safe (though potentially less efficient). 365 // 366 // Since physHugePageSize is always assumed to be a power of two, 367 // physHugePageShift is defined as physHugePageSize == 1 << physHugePageShift. 368 // The purpose of physHugePageShift is to avoid doing divisions in 369 // performance critical functions. 370 var ( 371 physHugePageSize uintptr 372 physHugePageShift uint 373 ) 374 375 func mallocinit() { 376 if gc.SizeClassToSize[tinySizeClass] != maxTinySize { 377 throw("bad TinySizeClass") 378 } 379 380 if heapArenaBitmapWords&(heapArenaBitmapWords-1) != 0 { 381 // heapBits expects modular arithmetic on bitmap 382 // addresses to work. 383 throw("heapArenaBitmapWords not a power of 2") 384 } 385 386 // Check physPageSize. 387 if physPageSize == 0 { 388 // The OS init code failed to fetch the physical page size. 389 throw("failed to get system page size") 390 } 391 if physPageSize > maxPhysPageSize { 392 print("system page size (", physPageSize, ") is larger than maximum page size (", maxPhysPageSize, ")\n") 393 throw("bad system page size") 394 } 395 if physPageSize < minPhysPageSize { 396 print("system page size (", physPageSize, ") is smaller than minimum page size (", minPhysPageSize, ")\n") 397 throw("bad system page size") 398 } 399 if physPageSize&(physPageSize-1) != 0 { 400 print("system page size (", physPageSize, ") must be a power of 2\n") 401 throw("bad system page size") 402 } 403 if physHugePageSize&(physHugePageSize-1) != 0 { 404 print("system huge page size (", physHugePageSize, ") must be a power of 2\n") 405 throw("bad system huge page size") 406 } 407 if physHugePageSize > maxPhysHugePageSize { 408 // physHugePageSize is greater than the maximum supported huge page size. 409 // Don't throw here, like in the other cases, since a system configured 410 // in this way isn't wrong, we just don't have the code to support them. 411 // Instead, silently set the huge page size to zero. 412 physHugePageSize = 0 413 } 414 if physHugePageSize != 0 { 415 // Since physHugePageSize is a power of 2, it suffices to increase 416 // physHugePageShift until 1<<physHugePageShift == physHugePageSize. 417 for 1<<physHugePageShift != physHugePageSize { 418 physHugePageShift++ 419 } 420 } 421 if pagesPerArena%pagesPerSpanRoot != 0 { 422 print("pagesPerArena (", pagesPerArena, ") is not divisible by pagesPerSpanRoot (", pagesPerSpanRoot, ")\n") 423 throw("bad pagesPerSpanRoot") 424 } 425 if pagesPerArena%pagesPerReclaimerChunk != 0 { 426 print("pagesPerArena (", pagesPerArena, ") is not divisible by pagesPerReclaimerChunk (", pagesPerReclaimerChunk, ")\n") 427 throw("bad pagesPerReclaimerChunk") 428 } 429 // Check that the minimum size (exclusive) for a malloc header is also 430 // a size class boundary. This is important to making sure checks align 431 // across different parts of the runtime. 432 // 433 // While we're here, also check to make sure all these size classes' 434 // span sizes are one page. Some code relies on this. 435 minSizeForMallocHeaderIsSizeClass := false 436 sizeClassesUpToMinSizeForMallocHeaderAreOnePage := true 437 for i := 0; i < len(gc.SizeClassToSize); i++ { 438 if gc.SizeClassToNPages[i] > 1 { 439 sizeClassesUpToMinSizeForMallocHeaderAreOnePage = false 440 } 441 if gc.MinSizeForMallocHeader == uintptr(gc.SizeClassToSize[i]) { 442 minSizeForMallocHeaderIsSizeClass = true 443 break 444 } 445 } 446 if !minSizeForMallocHeaderIsSizeClass { 447 throw("min size of malloc header is not a size class boundary") 448 } 449 if !sizeClassesUpToMinSizeForMallocHeaderAreOnePage { 450 throw("expected all size classes up to min size for malloc header to fit in one-page spans") 451 } 452 // Check that the pointer bitmap for all small sizes without a malloc header 453 // fits in a word. 454 if gc.MinSizeForMallocHeader/goarch.PtrSize > 8*goarch.PtrSize { 455 throw("max pointer/scan bitmap size for headerless objects is too large") 456 } 457 458 if minTagBits > tagBits { 459 throw("tagBits too small") 460 } 461 462 // Initialize the heap. 463 mheap_.init() 464 mcache0 = allocmcache() 465 lockInit(&gcBitsArenas.lock, lockRankGcBitsArenas) 466 lockInit(&profInsertLock, lockRankProfInsert) 467 lockInit(&profBlockLock, lockRankProfBlock) 468 lockInit(&profMemActiveLock, lockRankProfMemActive) 469 for i := range profMemFutureLock { 470 lockInit(&profMemFutureLock[i], lockRankProfMemFuture) 471 } 472 lockInit(&globalAlloc.mutex, lockRankGlobalAlloc) 473 474 // Create initial arena growth hints. 475 if isSbrkPlatform { 476 // Don't generate hints on sbrk platforms. We can 477 // only grow the break sequentially. 478 } else if goarch.PtrSize == 8 { 479 // On a 64-bit machine, we pick the following hints 480 // because: 481 // 482 // 1. Starting from the middle of the address space 483 // makes it easier to grow out a contiguous range 484 // without running in to some other mapping. 485 // 486 // 2. This makes Go heap addresses more easily 487 // recognizable when debugging. 488 // 489 // 3. Stack scanning in gccgo is still conservative, 490 // so it's important that addresses be distinguishable 491 // from other data. 492 // 493 // Starting at 0x00c0 means that the valid memory addresses 494 // will begin 0x00c0, 0x00c1, ... 495 // In little-endian, that's c0 00, c1 00, ... None of those are valid 496 // UTF-8 sequences, and they are otherwise as far away from 497 // ff (likely a common byte) as possible. If that fails, we try other 0xXXc0 498 // addresses. An earlier attempt to use 0x11f8 caused out of memory errors 499 // on OS X during thread allocations. 0x00c0 causes conflicts with 500 // AddressSanitizer which reserves all memory up to 0x0100. 501 // These choices reduce the odds of a conservative garbage collector 502 // not collecting memory because some non-pointer block of memory 503 // had a bit pattern that matched a memory address. 504 // 505 // However, on arm64, we ignore all this advice above and slam the 506 // allocation at 0x40 << 32 because when using 4k pages with 3-level 507 // translation buffers, the user address space is limited to 39 bits 508 // On ios/arm64, the address space is even smaller. 509 // 510 // On AIX, mmaps starts at 0x0A00000000000000 for 64-bit. 511 // processes. 512 // 513 // Space mapped for user arenas comes immediately after the range 514 // originally reserved for the regular heap when race mode is not 515 // enabled because user arena chunks can never be used for regular heap 516 // allocations and we want to avoid fragmenting the address space. 517 // 518 // In race mode we have no choice but to just use the same hints because 519 // the race detector requires that the heap be mapped contiguously. 520 for i := 0x7f; i >= 0; i-- { 521 var p uintptr 522 switch { 523 case raceenabled: 524 // The TSAN runtime requires the heap 525 // to be in the range [0x00c000000000, 526 // 0x00e000000000). 527 p = uintptr(i)<<32 | uintptrMask&(0x00c0<<32) 528 if p >= uintptrMask&0x00e000000000 { 529 continue 530 } 531 case GOARCH == "arm64" && GOOS == "ios": 532 p = uintptr(i)<<40 | uintptrMask&(0x0013<<28) 533 case GOARCH == "arm64": 534 p = uintptr(i)<<40 | uintptrMask&(0x0040<<32) 535 case GOOS == "aix": 536 if i == 0 { 537 // We don't use addresses directly after 0x0A00000000000000 538 // to avoid collisions with others mmaps done by non-go programs. 539 continue 540 } 541 p = uintptr(i)<<40 | uintptrMask&(0xa0<<52) 542 default: 543 p = uintptr(i)<<40 | uintptrMask&(0x00c0<<32) 544 } 545 // Switch to generating hints for user arenas if we've gone 546 // through about half the hints. In race mode, take only about 547 // a quarter; we don't have very much space to work with. 548 hintList := &mheap_.arenaHints 549 if (!raceenabled && i > 0x3f) || (raceenabled && i > 0x5f) { 550 hintList = &mheap_.userArena.arenaHints 551 } 552 hint := (*arenaHint)(mheap_.arenaHintAlloc.alloc()) 553 hint.addr = p 554 hint.next, *hintList = *hintList, hint 555 } 556 } else { 557 // On a 32-bit machine, we're much more concerned 558 // about keeping the usable heap contiguous. 559 // Hence: 560 // 561 // 1. We reserve space for all heapArenas up front so 562 // they don't get interleaved with the heap. They're 563 // ~258MB, so this isn't too bad. (We could reserve a 564 // smaller amount of space up front if this is a 565 // problem.) 566 // 567 // 2. We hint the heap to start right above the end of 568 // the binary so we have the best chance of keeping it 569 // contiguous. 570 // 571 // 3. We try to stake out a reasonably large initial 572 // heap reservation. 573 574 const arenaMetaSize = (1 << arenaBits) * unsafe.Sizeof(heapArena{}) 575 meta := uintptr(sysReserve(nil, arenaMetaSize, "heap reservation")) 576 if meta != 0 { 577 mheap_.heapArenaAlloc.init(meta, arenaMetaSize, true) 578 } 579 580 // We want to start the arena low, but if we're linked 581 // against C code, it's possible global constructors 582 // have called malloc and adjusted the process' brk. 583 // Query the brk so we can avoid trying to map the 584 // region over it (which will cause the kernel to put 585 // the region somewhere else, likely at a high 586 // address). 587 procBrk := sbrk0() 588 589 // If we ask for the end of the data segment but the 590 // operating system requires a little more space 591 // before we can start allocating, it will give out a 592 // slightly higher pointer. Except QEMU, which is 593 // buggy, as usual: it won't adjust the pointer 594 // upward. So adjust it upward a little bit ourselves: 595 // 1/4 MB to get away from the running binary image. 596 p := firstmoduledata.end 597 if p < procBrk { 598 p = procBrk 599 } 600 if mheap_.heapArenaAlloc.next <= p && p < mheap_.heapArenaAlloc.end { 601 p = mheap_.heapArenaAlloc.end 602 } 603 p = alignUp(p+(256<<10), heapArenaBytes) 604 // Because we're worried about fragmentation on 605 // 32-bit, we try to make a large initial reservation. 606 arenaSizes := []uintptr{ 607 512 << 20, 608 256 << 20, 609 128 << 20, 610 } 611 for _, arenaSize := range arenaSizes { 612 a, size := sysReserveAligned(unsafe.Pointer(p), arenaSize, heapArenaBytes, "heap reservation") 613 if a != nil { 614 mheap_.arena.init(uintptr(a), size, false) 615 p = mheap_.arena.end // For hint below 616 break 617 } 618 } 619 hint := (*arenaHint)(mheap_.arenaHintAlloc.alloc()) 620 hint.addr = p 621 hint.next, mheap_.arenaHints = mheap_.arenaHints, hint 622 623 // Place the hint for user arenas just after the large reservation. 624 // 625 // While this potentially competes with the hint above, in practice we probably 626 // aren't going to be getting this far anyway on 32-bit platforms. 627 userArenaHint := (*arenaHint)(mheap_.arenaHintAlloc.alloc()) 628 userArenaHint.addr = p 629 userArenaHint.next, mheap_.userArena.arenaHints = mheap_.userArena.arenaHints, userArenaHint 630 } 631 // Initialize the memory limit here because the allocator is going to look at it 632 // but we haven't called gcinit yet and we're definitely going to allocate memory before then. 633 gcController.memoryLimit.Store(math.MaxInt64) 634 } 635 636 // sysAlloc allocates heap arena space for at least n bytes. The 637 // returned pointer is always heapArenaBytes-aligned and backed by 638 // h.arenas metadata. The returned size is always a multiple of 639 // heapArenaBytes. sysAlloc returns nil on failure. 640 // There is no corresponding free function. 641 // 642 // hintList is a list of hint addresses for where to allocate new 643 // heap arenas. It must be non-nil. 644 // 645 // sysAlloc returns a memory region in the Reserved state. This region must 646 // be transitioned to Prepared and then Ready before use. 647 // 648 // arenaList is the list the arena should be added to. 649 // 650 // h must be locked. 651 func (h *mheap) sysAlloc(n uintptr, hintList **arenaHint, arenaList *[]arenaIdx) (v unsafe.Pointer, size uintptr) { 652 assertLockHeld(&h.lock) 653 654 n = alignUp(n, heapArenaBytes) 655 656 if hintList == &h.arenaHints { 657 // First, try the arena pre-reservation. 658 // Newly-used mappings are considered released. 659 // 660 // Only do this if we're using the regular heap arena hints. 661 // This behavior is only for the heap. 662 v = h.arena.alloc(n, heapArenaBytes, &gcController.heapReleased, "heap") 663 if v != nil { 664 size = n 665 goto mapped 666 } 667 } 668 669 // Try to grow the heap at a hint address. 670 for *hintList != nil { 671 hint := *hintList 672 p := hint.addr 673 if hint.down { 674 p -= n 675 } 676 if p+n < p { 677 // We can't use this, so don't ask. 678 v = nil 679 } else if arenaIndex(p+n-1) >= 1<<arenaBits { 680 // Outside addressable heap. Can't use. 681 v = nil 682 } else { 683 v = sysReserve(unsafe.Pointer(p), n, "heap reservation") 684 } 685 if p == uintptr(v) { 686 // Success. Update the hint. 687 if !hint.down { 688 p += n 689 } 690 hint.addr = p 691 size = n 692 break 693 } 694 // Failed. Discard this hint and try the next. 695 // 696 // TODO: This would be cleaner if sysReserve could be 697 // told to only return the requested address. In 698 // particular, this is already how Windows behaves, so 699 // it would simplify things there. 700 if v != nil { 701 sysUnreserve(v, n) 702 } 703 *hintList = hint.next 704 h.arenaHintAlloc.free(unsafe.Pointer(hint)) 705 } 706 707 if size == 0 { 708 if raceenabled { 709 // The race detector assumes the heap lives in 710 // [0x00c000000000, 0x00e000000000), but we 711 // just ran out of hints in this region. Give 712 // a nice failure. 713 throw("too many address space collisions for -race mode") 714 } 715 716 // All of the hints failed, so we'll take any 717 // (sufficiently aligned) address the kernel will give 718 // us. 719 v, size = sysReserveAligned(nil, n, heapArenaBytes, "heap") 720 if v == nil { 721 return nil, 0 722 } 723 724 // Create new hints for extending this region. 725 hint := (*arenaHint)(h.arenaHintAlloc.alloc()) 726 hint.addr, hint.down = uintptr(v), true 727 hint.next, mheap_.arenaHints = mheap_.arenaHints, hint 728 hint = (*arenaHint)(h.arenaHintAlloc.alloc()) 729 hint.addr = uintptr(v) + size 730 hint.next, mheap_.arenaHints = mheap_.arenaHints, hint 731 } 732 733 // Check for bad pointers or pointers we can't use. 734 { 735 var bad string 736 p := uintptr(v) 737 if p+size < p { 738 bad = "region exceeds uintptr range" 739 } else if arenaIndex(p) >= 1<<arenaBits { 740 bad = "base outside usable address space" 741 } else if arenaIndex(p+size-1) >= 1<<arenaBits { 742 bad = "end outside usable address space" 743 } 744 if bad != "" { 745 // This should be impossible on most architectures, 746 // but it would be really confusing to debug. 747 print("runtime: memory allocated by OS [", hex(p), ", ", hex(p+size), ") not in usable address space: ", bad, "\n") 748 throw("memory reservation exceeds address space limit") 749 } 750 } 751 752 if uintptr(v)&(heapArenaBytes-1) != 0 { 753 throw("misrounded allocation in sysAlloc") 754 } 755 756 mapped: 757 if valgrindenabled { 758 valgrindCreateMempool(v) 759 valgrindMakeMemNoAccess(v, size) 760 } 761 762 // Create arena metadata. 763 for ri := arenaIndex(uintptr(v)); ri <= arenaIndex(uintptr(v)+size-1); ri++ { 764 l2 := h.arenas[ri.l1()] 765 if l2 == nil { 766 // Allocate an L2 arena map. 767 // 768 // Use sysAllocOS instead of sysAlloc or persistentalloc because there's no 769 // statistic we can comfortably account for this space in. With this structure, 770 // we rely on demand paging to avoid large overheads, but tracking which memory 771 // is paged in is too expensive. Trying to account for the whole region means 772 // that it will appear like an enormous memory overhead in statistics, even though 773 // it is not. 774 l2 = (*[1 << arenaL2Bits]*heapArena)(sysAllocOS(unsafe.Sizeof(*l2), "heap index")) 775 if l2 == nil { 776 throw("out of memory allocating heap arena map") 777 } 778 if h.arenasHugePages { 779 sysHugePage(unsafe.Pointer(l2), unsafe.Sizeof(*l2)) 780 } else { 781 sysNoHugePage(unsafe.Pointer(l2), unsafe.Sizeof(*l2)) 782 } 783 atomic.StorepNoWB(unsafe.Pointer(&h.arenas[ri.l1()]), unsafe.Pointer(l2)) 784 } 785 786 if l2[ri.l2()] != nil { 787 throw("arena already initialized") 788 } 789 var r *heapArena 790 r = (*heapArena)(h.heapArenaAlloc.alloc(unsafe.Sizeof(*r), goarch.PtrSize, &memstats.gcMiscSys, "heap metadata")) 791 if r == nil { 792 r = (*heapArena)(persistentalloc(unsafe.Sizeof(*r), goarch.PtrSize, &memstats.gcMiscSys)) 793 if r == nil { 794 throw("out of memory allocating heap arena metadata") 795 } 796 } 797 798 // Register the arena in allArenas if requested. 799 if len((*arenaList)) == cap((*arenaList)) { 800 size := 2 * uintptr(cap((*arenaList))) * goarch.PtrSize 801 if size == 0 { 802 size = physPageSize 803 } 804 newArray := (*notInHeap)(persistentalloc(size, goarch.PtrSize, &memstats.gcMiscSys)) 805 if newArray == nil { 806 throw("out of memory allocating allArenas") 807 } 808 oldSlice := (*arenaList) 809 *(*notInHeapSlice)(unsafe.Pointer(&(*arenaList))) = notInHeapSlice{newArray, len((*arenaList)), int(size / goarch.PtrSize)} 810 copy((*arenaList), oldSlice) 811 // Do not free the old backing array because 812 // there may be concurrent readers. Since we 813 // double the array each time, this can lead 814 // to at most 2x waste. 815 } 816 (*arenaList) = (*arenaList)[:len((*arenaList))+1] 817 (*arenaList)[len((*arenaList))-1] = ri 818 819 // Store atomically just in case an object from the 820 // new heap arena becomes visible before the heap lock 821 // is released (which shouldn't happen, but there's 822 // little downside to this). 823 atomic.StorepNoWB(unsafe.Pointer(&l2[ri.l2()]), unsafe.Pointer(r)) 824 } 825 826 // Tell the race detector about the new heap memory. 827 if raceenabled { 828 racemapshadow(v, size) 829 } 830 831 return 832 } 833 834 // enableMetadataHugePages enables huge pages for various sources of heap metadata. 835 // 836 // A note on latency: for sufficiently small heaps (<10s of GiB) this function will take constant 837 // time, but may take time proportional to the size of the mapped heap beyond that. 838 // 839 // This function is idempotent. 840 // 841 // The heap lock must not be held over this operation, since it will briefly acquire 842 // the heap lock. 843 // 844 // Must be called on the system stack because it acquires the heap lock. 845 // 846 //go:systemstack 847 func (h *mheap) enableMetadataHugePages() { 848 // Enable huge pages for page structure. 849 h.pages.enableChunkHugePages() 850 851 // Grab the lock and set arenasHugePages if it's not. 852 // 853 // Once arenasHugePages is set, all new L2 entries will be eligible for 854 // huge pages. We'll set all the old entries after we release the lock. 855 lock(&h.lock) 856 if h.arenasHugePages { 857 unlock(&h.lock) 858 return 859 } 860 h.arenasHugePages = true 861 unlock(&h.lock) 862 863 // N.B. The arenas L1 map is quite small on all platforms, so it's fine to 864 // just iterate over the whole thing. 865 for i := range h.arenas { 866 l2 := (*[1 << arenaL2Bits]*heapArena)(atomic.Loadp(unsafe.Pointer(&h.arenas[i]))) 867 if l2 == nil { 868 continue 869 } 870 sysHugePage(unsafe.Pointer(l2), unsafe.Sizeof(*l2)) 871 } 872 } 873 874 // base address for all 0-byte allocations 875 var zerobase uintptr 876 877 // nextFreeFast returns the next free object if one is quickly available. 878 // Otherwise it returns 0. 879 func nextFreeFast(s *mspan) gclinkptr { 880 theBit := sys.TrailingZeros64(s.allocCache) // Is there a free object in the allocCache? 881 if theBit < 64 { 882 result := s.freeindex + uint16(theBit) 883 if result < s.nelems { 884 freeidx := result + 1 885 if freeidx%64 == 0 && freeidx != s.nelems { 886 return 0 887 } 888 s.allocCache >>= uint(theBit + 1) 889 s.freeindex = freeidx 890 s.allocCount++ 891 return gclinkptr(uintptr(result)*s.elemsize + s.base()) 892 } 893 } 894 return 0 895 } 896 897 // nextFree returns the next free object from the cached span if one is available. 898 // Otherwise it refills the cache with a span with an available object and 899 // returns that object along with a flag indicating that this was a heavy 900 // weight allocation. If it is a heavy weight allocation the caller must 901 // determine whether a new GC cycle needs to be started or if the GC is active 902 // whether this goroutine needs to assist the GC. 903 // 904 // Must run in a non-preemptible context since otherwise the owner of 905 // c could change. 906 func (c *mcache) nextFree(spc spanClass) (v gclinkptr, s *mspan, checkGCTrigger bool) { 907 s = c.alloc[spc] 908 checkGCTrigger = false 909 freeIndex := s.nextFreeIndex() 910 if freeIndex == s.nelems { 911 // The span is full. 912 if s.allocCount != s.nelems { 913 println("runtime: s.allocCount=", s.allocCount, "s.nelems=", s.nelems) 914 throw("s.allocCount != s.nelems && freeIndex == s.nelems") 915 } 916 c.refill(spc) 917 checkGCTrigger = true 918 s = c.alloc[spc] 919 920 freeIndex = s.nextFreeIndex() 921 } 922 923 if freeIndex >= s.nelems { 924 throw("freeIndex is not valid") 925 } 926 927 v = gclinkptr(uintptr(freeIndex)*s.elemsize + s.base()) 928 s.allocCount++ 929 if s.allocCount > s.nelems { 930 println("s.allocCount=", s.allocCount, "s.nelems=", s.nelems) 931 throw("s.allocCount > s.nelems") 932 } 933 return 934 } 935 936 // doubleCheckMalloc enables a bunch of extra checks to malloc to double-check 937 // that various invariants are upheld. 938 // 939 // We might consider turning these on by default; many of them previously were. 940 // They account for a few % of mallocgc's cost though, which does matter somewhat 941 // at scale. 942 const doubleCheckMalloc = false 943 944 // Allocate an object of size bytes. 945 // Small objects are allocated from the per-P cache's free lists. 946 // Large objects (> 32 kB) are allocated straight from the heap. 947 // 948 // mallocgc should be an internal detail, 949 // but widely used packages access it using linkname. 950 // Notable members of the hall of shame include: 951 // - github.com/bytedance/gopkg 952 // - github.com/bytedance/sonic 953 // - github.com/cloudwego/frugal 954 // - github.com/cockroachdb/cockroach 955 // - github.com/cockroachdb/pebble 956 // - github.com/ugorji/go/codec 957 // 958 // Do not remove or change the type signature. 959 // See go.dev/issue/67401. 960 // 961 //go:linkname mallocgc 962 func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer { 963 if doubleCheckMalloc { 964 if gcphase == _GCmarktermination { 965 throw("mallocgc called with gcphase == _GCmarktermination") 966 } 967 } 968 969 // Short-circuit zero-sized allocation requests. 970 if size == 0 { 971 return unsafe.Pointer(&zerobase) 972 } 973 974 // It's possible for any malloc to trigger sweeping, which may in 975 // turn queue finalizers. Record this dynamic lock edge. 976 // N.B. Compiled away if lockrank experiment is not enabled. 977 lockRankMayQueueFinalizer() 978 979 // Pre-malloc debug hooks. 980 if debug.malloc { 981 if x := preMallocgcDebug(size, typ); x != nil { 982 return x 983 } 984 } 985 986 // For ASAN, we allocate extra memory around each allocation called the "redzone." 987 // These "redzones" are marked as unaddressable. 988 var asanRZ uintptr 989 if asanenabled { 990 asanRZ = redZoneSize(size) 991 size += asanRZ 992 } 993 994 // Assist the GC if needed. 995 if gcBlackenEnabled != 0 { 996 deductAssistCredit(size) 997 } 998 999 // Actually do the allocation. 1000 var x unsafe.Pointer 1001 var elemsize uintptr 1002 if size <= maxSmallSize-gc.MallocHeaderSize { 1003 if typ == nil || !typ.Pointers() { 1004 if size < maxTinySize { 1005 x, elemsize = mallocgcTiny(size, typ) 1006 } else { 1007 x, elemsize = mallocgcSmallNoscan(size, typ, needzero) 1008 } 1009 } else { 1010 if !needzero { 1011 throw("objects with pointers must be zeroed") 1012 } 1013 if heapBitsInSpan(size) { 1014 x, elemsize = mallocgcSmallScanNoHeader(size, typ) 1015 } else { 1016 x, elemsize = mallocgcSmallScanHeader(size, typ) 1017 } 1018 } 1019 } else { 1020 x, elemsize = mallocgcLarge(size, typ, needzero) 1021 } 1022 1023 // Notify sanitizers, if enabled. 1024 if raceenabled { 1025 racemalloc(x, size-asanRZ) 1026 } 1027 if msanenabled { 1028 msanmalloc(x, size-asanRZ) 1029 } 1030 if asanenabled { 1031 // Poison the space between the end of the requested size of x 1032 // and the end of the slot. Unpoison the requested allocation. 1033 frag := elemsize - size 1034 if typ != nil && typ.Pointers() && !heapBitsInSpan(elemsize) && size <= maxSmallSize-gc.MallocHeaderSize { 1035 frag -= gc.MallocHeaderSize 1036 } 1037 asanpoison(unsafe.Add(x, size-asanRZ), asanRZ) 1038 asanunpoison(x, size-asanRZ) 1039 } 1040 if valgrindenabled { 1041 valgrindMalloc(x, size-asanRZ) 1042 } 1043 1044 // Adjust our GC assist debt to account for internal fragmentation. 1045 if gcBlackenEnabled != 0 && elemsize != 0 { 1046 if assistG := getg().m.curg; assistG != nil { 1047 assistG.gcAssistBytes -= int64(elemsize - size) 1048 } 1049 } 1050 1051 // Post-malloc debug hooks. 1052 if debug.malloc { 1053 postMallocgcDebug(x, elemsize, typ) 1054 } 1055 return x 1056 } 1057 1058 func mallocgcTiny(size uintptr, typ *_type) (unsafe.Pointer, uintptr) { 1059 // Set mp.mallocing to keep from being preempted by GC. 1060 mp := acquirem() 1061 if doubleCheckMalloc { 1062 if mp.mallocing != 0 { 1063 throw("malloc deadlock") 1064 } 1065 if mp.gsignal == getg() { 1066 throw("malloc during signal") 1067 } 1068 if typ != nil && typ.Pointers() { 1069 throw("expected noscan for tiny alloc") 1070 } 1071 } 1072 mp.mallocing = 1 1073 1074 // Tiny allocator. 1075 // 1076 // Tiny allocator combines several tiny allocation requests 1077 // into a single memory block. The resulting memory block 1078 // is freed when all subobjects are unreachable. The subobjects 1079 // must be noscan (don't have pointers), this ensures that 1080 // the amount of potentially wasted memory is bounded. 1081 // 1082 // Size of the memory block used for combining (maxTinySize) is tunable. 1083 // Current setting is 16 bytes, which relates to 2x worst case memory 1084 // wastage (when all but one subobjects are unreachable). 1085 // 8 bytes would result in no wastage at all, but provides less 1086 // opportunities for combining. 1087 // 32 bytes provides more opportunities for combining, 1088 // but can lead to 4x worst case wastage. 1089 // The best case winning is 8x regardless of block size. 1090 // 1091 // Objects obtained from tiny allocator must not be freed explicitly. 1092 // So when an object will be freed explicitly, we ensure that 1093 // its size >= maxTinySize. 1094 // 1095 // SetFinalizer has a special case for objects potentially coming 1096 // from tiny allocator, it such case it allows to set finalizers 1097 // for an inner byte of a memory block. 1098 // 1099 // The main targets of tiny allocator are small strings and 1100 // standalone escaping variables. On a json benchmark 1101 // the allocator reduces number of allocations by ~12% and 1102 // reduces heap size by ~20%. 1103 c := getMCache(mp) 1104 off := c.tinyoffset 1105 // Align tiny pointer for required (conservative) alignment. 1106 if size&7 == 0 { 1107 off = alignUp(off, 8) 1108 } else if goarch.PtrSize == 4 && size == 12 { 1109 // Conservatively align 12-byte objects to 8 bytes on 32-bit 1110 // systems so that objects whose first field is a 64-bit 1111 // value is aligned to 8 bytes and does not cause a fault on 1112 // atomic access. See issue 37262. 1113 // TODO(mknyszek): Remove this workaround if/when issue 36606 1114 // is resolved. 1115 off = alignUp(off, 8) 1116 } else if size&3 == 0 { 1117 off = alignUp(off, 4) 1118 } else if size&1 == 0 { 1119 off = alignUp(off, 2) 1120 } 1121 if off+size <= maxTinySize && c.tiny != 0 { 1122 // The object fits into existing tiny block. 1123 x := unsafe.Pointer(c.tiny + off) 1124 c.tinyoffset = off + size 1125 c.tinyAllocs++ 1126 mp.mallocing = 0 1127 releasem(mp) 1128 return x, 0 1129 } 1130 // Allocate a new maxTinySize block. 1131 checkGCTrigger := false 1132 span := c.alloc[tinySpanClass] 1133 v := nextFreeFast(span) 1134 if v == 0 { 1135 v, span, checkGCTrigger = c.nextFree(tinySpanClass) 1136 } 1137 x := unsafe.Pointer(v) 1138 (*[2]uint64)(x)[0] = 0 // Always zero 1139 (*[2]uint64)(x)[1] = 0 1140 // See if we need to replace the existing tiny block with the new one 1141 // based on amount of remaining free space. 1142 if !raceenabled && (size < c.tinyoffset || c.tiny == 0) { 1143 // Note: disabled when race detector is on, see comment near end of this function. 1144 c.tiny = uintptr(x) 1145 c.tinyoffset = size 1146 } 1147 1148 // Ensure that the stores above that initialize x to 1149 // type-safe memory and set the heap bits occur before 1150 // the caller can make x observable to the garbage 1151 // collector. Otherwise, on weakly ordered machines, 1152 // the garbage collector could follow a pointer to x, 1153 // but see uninitialized memory or stale heap bits. 1154 publicationBarrier() 1155 1156 if writeBarrier.enabled { 1157 // Allocate black during GC. 1158 // All slots hold nil so no scanning is needed. 1159 // This may be racing with GC so do it atomically if there can be 1160 // a race marking the bit. 1161 gcmarknewobject(span, uintptr(x)) 1162 } else { 1163 // Track the last free index before the mark phase. This field 1164 // is only used by the garbage collector. During the mark phase 1165 // this is used by the conservative scanner to filter out objects 1166 // that are both free and recently-allocated. It's safe to do that 1167 // because we allocate-black if the GC is enabled. The conservative 1168 // scanner produces pointers out of thin air, so without additional 1169 // synchronization it might otherwise observe a partially-initialized 1170 // object, which could crash the program. 1171 span.freeIndexForScan = span.freeindex 1172 } 1173 1174 // Note cache c only valid while m acquired; see #47302 1175 // 1176 // N.B. Use the full size because that matches how the GC 1177 // will update the mem profile on the "free" side. 1178 // 1179 // TODO(mknyszek): We should really count the header as part 1180 // of gc_sys or something. The code below just pretends it is 1181 // internal fragmentation and matches the GC's accounting by 1182 // using the whole allocation slot. 1183 c.nextSample -= int64(span.elemsize) 1184 if c.nextSample < 0 || MemProfileRate != c.memProfRate { 1185 profilealloc(mp, x, span.elemsize) 1186 } 1187 mp.mallocing = 0 1188 releasem(mp) 1189 1190 if checkGCTrigger { 1191 if t := (gcTrigger{kind: gcTriggerHeap}); t.test() { 1192 gcStart(t) 1193 } 1194 } 1195 1196 if raceenabled { 1197 // Pad tinysize allocations so they are aligned with the end 1198 // of the tinyalloc region. This ensures that any arithmetic 1199 // that goes off the top end of the object will be detectable 1200 // by checkptr (issue 38872). 1201 // Note that we disable tinyalloc when raceenabled for this to work. 1202 // TODO: This padding is only performed when the race detector 1203 // is enabled. It would be nice to enable it if any package 1204 // was compiled with checkptr, but there's no easy way to 1205 // detect that (especially at compile time). 1206 // TODO: enable this padding for all allocations, not just 1207 // tinyalloc ones. It's tricky because of pointer maps. 1208 // Maybe just all noscan objects? 1209 x = add(x, span.elemsize-size) 1210 } 1211 return x, span.elemsize 1212 } 1213 1214 func mallocgcSmallNoscan(size uintptr, typ *_type, needzero bool) (unsafe.Pointer, uintptr) { 1215 // Set mp.mallocing to keep from being preempted by GC. 1216 mp := acquirem() 1217 if doubleCheckMalloc { 1218 if mp.mallocing != 0 { 1219 throw("malloc deadlock") 1220 } 1221 if mp.gsignal == getg() { 1222 throw("malloc during signal") 1223 } 1224 if typ != nil && typ.Pointers() { 1225 throw("expected noscan type for noscan alloc") 1226 } 1227 } 1228 mp.mallocing = 1 1229 1230 checkGCTrigger := false 1231 c := getMCache(mp) 1232 var sizeclass uint8 1233 if size <= gc.SmallSizeMax-8 { 1234 sizeclass = gc.SizeToSizeClass8[divRoundUp(size, gc.SmallSizeDiv)] 1235 } else { 1236 sizeclass = gc.SizeToSizeClass128[divRoundUp(size-gc.SmallSizeMax, gc.LargeSizeDiv)] 1237 } 1238 size = uintptr(gc.SizeClassToSize[sizeclass]) 1239 spc := makeSpanClass(sizeclass, true) 1240 span := c.alloc[spc] 1241 v := nextFreeFast(span) 1242 if v == 0 { 1243 v, span, checkGCTrigger = c.nextFree(spc) 1244 } 1245 x := unsafe.Pointer(v) 1246 if needzero && span.needzero != 0 { 1247 memclrNoHeapPointers(x, size) 1248 } 1249 1250 // Ensure that the stores above that initialize x to 1251 // type-safe memory and set the heap bits occur before 1252 // the caller can make x observable to the garbage 1253 // collector. Otherwise, on weakly ordered machines, 1254 // the garbage collector could follow a pointer to x, 1255 // but see uninitialized memory or stale heap bits. 1256 publicationBarrier() 1257 1258 if writeBarrier.enabled { 1259 // Allocate black during GC. 1260 // All slots hold nil so no scanning is needed. 1261 // This may be racing with GC so do it atomically if there can be 1262 // a race marking the bit. 1263 gcmarknewobject(span, uintptr(x)) 1264 } else { 1265 // Track the last free index before the mark phase. This field 1266 // is only used by the garbage collector. During the mark phase 1267 // this is used by the conservative scanner to filter out objects 1268 // that are both free and recently-allocated. It's safe to do that 1269 // because we allocate-black if the GC is enabled. The conservative 1270 // scanner produces pointers out of thin air, so without additional 1271 // synchronization it might otherwise observe a partially-initialized 1272 // object, which could crash the program. 1273 span.freeIndexForScan = span.freeindex 1274 } 1275 1276 // Note cache c only valid while m acquired; see #47302 1277 // 1278 // N.B. Use the full size because that matches how the GC 1279 // will update the mem profile on the "free" side. 1280 // 1281 // TODO(mknyszek): We should really count the header as part 1282 // of gc_sys or something. The code below just pretends it is 1283 // internal fragmentation and matches the GC's accounting by 1284 // using the whole allocation slot. 1285 c.nextSample -= int64(size) 1286 if c.nextSample < 0 || MemProfileRate != c.memProfRate { 1287 profilealloc(mp, x, size) 1288 } 1289 mp.mallocing = 0 1290 releasem(mp) 1291 1292 if checkGCTrigger { 1293 if t := (gcTrigger{kind: gcTriggerHeap}); t.test() { 1294 gcStart(t) 1295 } 1296 } 1297 return x, size 1298 } 1299 1300 func mallocgcSmallScanNoHeader(size uintptr, typ *_type) (unsafe.Pointer, uintptr) { 1301 // Set mp.mallocing to keep from being preempted by GC. 1302 mp := acquirem() 1303 if doubleCheckMalloc { 1304 if mp.mallocing != 0 { 1305 throw("malloc deadlock") 1306 } 1307 if mp.gsignal == getg() { 1308 throw("malloc during signal") 1309 } 1310 if typ == nil || !typ.Pointers() { 1311 throw("noscan allocated in scan-only path") 1312 } 1313 if !heapBitsInSpan(size) { 1314 throw("heap bits in not in span for non-header-only path") 1315 } 1316 } 1317 mp.mallocing = 1 1318 1319 checkGCTrigger := false 1320 c := getMCache(mp) 1321 sizeclass := gc.SizeToSizeClass8[divRoundUp(size, gc.SmallSizeDiv)] 1322 spc := makeSpanClass(sizeclass, false) 1323 span := c.alloc[spc] 1324 v := nextFreeFast(span) 1325 if v == 0 { 1326 v, span, checkGCTrigger = c.nextFree(spc) 1327 } 1328 x := unsafe.Pointer(v) 1329 if span.needzero != 0 { 1330 memclrNoHeapPointers(x, size) 1331 } 1332 if goarch.PtrSize == 8 && sizeclass == 1 { 1333 // initHeapBits already set the pointer bits for the 8-byte sizeclass 1334 // on 64-bit platforms. 1335 c.scanAlloc += 8 1336 } else { 1337 c.scanAlloc += heapSetTypeNoHeader(uintptr(x), size, typ, span) 1338 } 1339 size = uintptr(gc.SizeClassToSize[sizeclass]) 1340 1341 // Ensure that the stores above that initialize x to 1342 // type-safe memory and set the heap bits occur before 1343 // the caller can make x observable to the garbage 1344 // collector. Otherwise, on weakly ordered machines, 1345 // the garbage collector could follow a pointer to x, 1346 // but see uninitialized memory or stale heap bits. 1347 publicationBarrier() 1348 1349 if writeBarrier.enabled { 1350 // Allocate black during GC. 1351 // All slots hold nil so no scanning is needed. 1352 // This may be racing with GC so do it atomically if there can be 1353 // a race marking the bit. 1354 gcmarknewobject(span, uintptr(x)) 1355 } else { 1356 // Track the last free index before the mark phase. This field 1357 // is only used by the garbage collector. During the mark phase 1358 // this is used by the conservative scanner to filter out objects 1359 // that are both free and recently-allocated. It's safe to do that 1360 // because we allocate-black if the GC is enabled. The conservative 1361 // scanner produces pointers out of thin air, so without additional 1362 // synchronization it might otherwise observe a partially-initialized 1363 // object, which could crash the program. 1364 span.freeIndexForScan = span.freeindex 1365 } 1366 1367 // Note cache c only valid while m acquired; see #47302 1368 // 1369 // N.B. Use the full size because that matches how the GC 1370 // will update the mem profile on the "free" side. 1371 // 1372 // TODO(mknyszek): We should really count the header as part 1373 // of gc_sys or something. The code below just pretends it is 1374 // internal fragmentation and matches the GC's accounting by 1375 // using the whole allocation slot. 1376 c.nextSample -= int64(size) 1377 if c.nextSample < 0 || MemProfileRate != c.memProfRate { 1378 profilealloc(mp, x, size) 1379 } 1380 mp.mallocing = 0 1381 releasem(mp) 1382 1383 if checkGCTrigger { 1384 if t := (gcTrigger{kind: gcTriggerHeap}); t.test() { 1385 gcStart(t) 1386 } 1387 } 1388 return x, size 1389 } 1390 1391 func mallocgcSmallScanHeader(size uintptr, typ *_type) (unsafe.Pointer, uintptr) { 1392 // Set mp.mallocing to keep from being preempted by GC. 1393 mp := acquirem() 1394 if doubleCheckMalloc { 1395 if mp.mallocing != 0 { 1396 throw("malloc deadlock") 1397 } 1398 if mp.gsignal == getg() { 1399 throw("malloc during signal") 1400 } 1401 if typ == nil || !typ.Pointers() { 1402 throw("noscan allocated in scan-only path") 1403 } 1404 if heapBitsInSpan(size) { 1405 throw("heap bits in span for header-only path") 1406 } 1407 } 1408 mp.mallocing = 1 1409 1410 checkGCTrigger := false 1411 c := getMCache(mp) 1412 size += gc.MallocHeaderSize 1413 var sizeclass uint8 1414 if size <= gc.SmallSizeMax-8 { 1415 sizeclass = gc.SizeToSizeClass8[divRoundUp(size, gc.SmallSizeDiv)] 1416 } else { 1417 sizeclass = gc.SizeToSizeClass128[divRoundUp(size-gc.SmallSizeMax, gc.LargeSizeDiv)] 1418 } 1419 size = uintptr(gc.SizeClassToSize[sizeclass]) 1420 spc := makeSpanClass(sizeclass, false) 1421 span := c.alloc[spc] 1422 v := nextFreeFast(span) 1423 if v == 0 { 1424 v, span, checkGCTrigger = c.nextFree(spc) 1425 } 1426 x := unsafe.Pointer(v) 1427 if span.needzero != 0 { 1428 memclrNoHeapPointers(x, size) 1429 } 1430 header := (**_type)(x) 1431 x = add(x, gc.MallocHeaderSize) 1432 c.scanAlloc += heapSetTypeSmallHeader(uintptr(x), size-gc.MallocHeaderSize, typ, header, span) 1433 1434 // Ensure that the stores above that initialize x to 1435 // type-safe memory and set the heap bits occur before 1436 // the caller can make x observable to the garbage 1437 // collector. Otherwise, on weakly ordered machines, 1438 // the garbage collector could follow a pointer to x, 1439 // but see uninitialized memory or stale heap bits. 1440 publicationBarrier() 1441 1442 if writeBarrier.enabled { 1443 // Allocate black during GC. 1444 // All slots hold nil so no scanning is needed. 1445 // This may be racing with GC so do it atomically if there can be 1446 // a race marking the bit. 1447 gcmarknewobject(span, uintptr(x)) 1448 } else { 1449 // Track the last free index before the mark phase. This field 1450 // is only used by the garbage collector. During the mark phase 1451 // this is used by the conservative scanner to filter out objects 1452 // that are both free and recently-allocated. It's safe to do that 1453 // because we allocate-black if the GC is enabled. The conservative 1454 // scanner produces pointers out of thin air, so without additional 1455 // synchronization it might otherwise observe a partially-initialized 1456 // object, which could crash the program. 1457 span.freeIndexForScan = span.freeindex 1458 } 1459 1460 // Note cache c only valid while m acquired; see #47302 1461 // 1462 // N.B. Use the full size because that matches how the GC 1463 // will update the mem profile on the "free" side. 1464 // 1465 // TODO(mknyszek): We should really count the header as part 1466 // of gc_sys or something. The code below just pretends it is 1467 // internal fragmentation and matches the GC's accounting by 1468 // using the whole allocation slot. 1469 c.nextSample -= int64(size) 1470 if c.nextSample < 0 || MemProfileRate != c.memProfRate { 1471 profilealloc(mp, x, size) 1472 } 1473 mp.mallocing = 0 1474 releasem(mp) 1475 1476 if checkGCTrigger { 1477 if t := (gcTrigger{kind: gcTriggerHeap}); t.test() { 1478 gcStart(t) 1479 } 1480 } 1481 return x, size 1482 } 1483 1484 func mallocgcLarge(size uintptr, typ *_type, needzero bool) (unsafe.Pointer, uintptr) { 1485 // Set mp.mallocing to keep from being preempted by GC. 1486 mp := acquirem() 1487 if doubleCheckMalloc { 1488 if mp.mallocing != 0 { 1489 throw("malloc deadlock") 1490 } 1491 if mp.gsignal == getg() { 1492 throw("malloc during signal") 1493 } 1494 } 1495 mp.mallocing = 1 1496 1497 c := getMCache(mp) 1498 // For large allocations, keep track of zeroed state so that 1499 // bulk zeroing can be happen later in a preemptible context. 1500 span := c.allocLarge(size, typ == nil || !typ.Pointers()) 1501 span.freeindex = 1 1502 span.allocCount = 1 1503 span.largeType = nil // Tell the GC not to look at this yet. 1504 size = span.elemsize 1505 x := unsafe.Pointer(span.base()) 1506 1507 // Ensure that the store above that sets largeType to 1508 // nil happens before the caller can make x observable 1509 // to the garbage collector. 1510 // 1511 // Otherwise, on weakly ordered machines, the garbage 1512 // collector could follow a pointer to x, but see a stale 1513 // largeType value. 1514 publicationBarrier() 1515 1516 if writeBarrier.enabled { 1517 // Allocate black during GC. 1518 // All slots hold nil so no scanning is needed. 1519 // This may be racing with GC so do it atomically if there can be 1520 // a race marking the bit. 1521 gcmarknewobject(span, uintptr(x)) 1522 } else { 1523 // Track the last free index before the mark phase. This field 1524 // is only used by the garbage collector. During the mark phase 1525 // this is used by the conservative scanner to filter out objects 1526 // that are both free and recently-allocated. It's safe to do that 1527 // because we allocate-black if the GC is enabled. The conservative 1528 // scanner produces pointers out of thin air, so without additional 1529 // synchronization it might otherwise observe a partially-initialized 1530 // object, which could crash the program. 1531 span.freeIndexForScan = span.freeindex 1532 } 1533 1534 // Note cache c only valid while m acquired; see #47302 1535 // 1536 // N.B. Use the full size because that matches how the GC 1537 // will update the mem profile on the "free" side. 1538 // 1539 // TODO(mknyszek): We should really count the header as part 1540 // of gc_sys or something. The code below just pretends it is 1541 // internal fragmentation and matches the GC's accounting by 1542 // using the whole allocation slot. 1543 c.nextSample -= int64(size) 1544 if c.nextSample < 0 || MemProfileRate != c.memProfRate { 1545 profilealloc(mp, x, size) 1546 } 1547 mp.mallocing = 0 1548 releasem(mp) 1549 1550 // Check to see if we need to trigger the GC. 1551 if t := (gcTrigger{kind: gcTriggerHeap}); t.test() { 1552 gcStart(t) 1553 } 1554 1555 // Objects can be zeroed late in a context where preemption can occur. 1556 // 1557 // x will keep the memory alive. 1558 if needzero && span.needzero != 0 { 1559 // N.B. size == fullSize always in this case. 1560 memclrNoHeapPointersChunked(size, x) // This is a possible preemption point: see #47302 1561 } 1562 1563 // Set the type and run the publication barrier while non-preemptible. We need to make 1564 // sure that between heapSetTypeLarge and publicationBarrier we cannot get preempted, 1565 // otherwise the GC could potentially observe non-zeroed memory but largeType set on weak 1566 // memory architectures. 1567 // 1568 // The GC can also potentially observe non-zeroed memory if conservative scanning spuriously 1569 // observes a partially-allocated object, see the freeIndexForScan update above. This case is 1570 // handled by synchronization inside heapSetTypeLarge. 1571 mp = acquirem() 1572 if typ != nil && typ.Pointers() { 1573 // Finish storing the type information, now that we're certain the memory is zeroed. 1574 getMCache(mp).scanAlloc += heapSetTypeLarge(uintptr(x), size, typ, span) 1575 } 1576 // Publish the object again, now with zeroed memory and initialized type information. 1577 // 1578 // Even if we didn't update any type information, this is necessary to ensure that, for example, 1579 // x written to a global without any synchronization still results in other goroutines observing 1580 // zeroed memory. 1581 publicationBarrier() 1582 releasem(mp) 1583 return x, size 1584 } 1585 1586 func preMallocgcDebug(size uintptr, typ *_type) unsafe.Pointer { 1587 if debug.sbrk != 0 { 1588 align := uintptr(16) 1589 if typ != nil { 1590 // TODO(austin): This should be just 1591 // align = uintptr(typ.align) 1592 // but that's only 4 on 32-bit platforms, 1593 // even if there's a uint64 field in typ (see #599). 1594 // This causes 64-bit atomic accesses to panic. 1595 // Hence, we use stricter alignment that matches 1596 // the normal allocator better. 1597 if size&7 == 0 { 1598 align = 8 1599 } else if size&3 == 0 { 1600 align = 4 1601 } else if size&1 == 0 { 1602 align = 2 1603 } else { 1604 align = 1 1605 } 1606 } 1607 return persistentalloc(size, align, &memstats.other_sys) 1608 } 1609 if inittrace.active && inittrace.id == getg().goid { 1610 // Init functions are executed sequentially in a single goroutine. 1611 inittrace.allocs += 1 1612 } 1613 return nil 1614 } 1615 1616 func postMallocgcDebug(x unsafe.Pointer, elemsize uintptr, typ *_type) { 1617 if inittrace.active && inittrace.id == getg().goid { 1618 // Init functions are executed sequentially in a single goroutine. 1619 inittrace.bytes += uint64(elemsize) 1620 } 1621 1622 if traceAllocFreeEnabled() { 1623 trace := traceAcquire() 1624 if trace.ok() { 1625 trace.HeapObjectAlloc(uintptr(x), typ) 1626 traceRelease(trace) 1627 } 1628 } 1629 1630 // N.B. elemsize == 0 indicates a tiny allocation, since no new slot was 1631 // allocated to fulfill this call to mallocgc. This means checkfinalizer 1632 // will only flag an error if there is actually any risk. If an allocation 1633 // has the tiny block to itself, it will not get flagged, because we won't 1634 // mark the block as a tiny block. 1635 if debug.checkfinalizers != 0 && elemsize == 0 { 1636 setTinyBlockContext(unsafe.Pointer(alignDown(uintptr(x), maxTinySize))) 1637 } 1638 } 1639 1640 // deductAssistCredit reduces the current G's assist credit 1641 // by size bytes, and assists the GC if necessary. 1642 // 1643 // Caller must be preemptible. 1644 // 1645 // Returns the G for which the assist credit was accounted. 1646 func deductAssistCredit(size uintptr) { 1647 // Charge the current user G for this allocation. 1648 assistG := getg() 1649 if assistG.m.curg != nil { 1650 assistG = assistG.m.curg 1651 } 1652 // Charge the allocation against the G. We'll account 1653 // for internal fragmentation at the end of mallocgc. 1654 assistG.gcAssistBytes -= int64(size) 1655 1656 if assistG.gcAssistBytes < 0 { 1657 // This G is in debt. Assist the GC to correct 1658 // this before allocating. This must happen 1659 // before disabling preemption. 1660 gcAssistAlloc(assistG) 1661 } 1662 } 1663 1664 // memclrNoHeapPointersChunked repeatedly calls memclrNoHeapPointers 1665 // on chunks of the buffer to be zeroed, with opportunities for preemption 1666 // along the way. memclrNoHeapPointers contains no safepoints and also 1667 // cannot be preemptively scheduled, so this provides a still-efficient 1668 // block copy that can also be preempted on a reasonable granularity. 1669 // 1670 // Use this with care; if the data being cleared is tagged to contain 1671 // pointers, this allows the GC to run before it is all cleared. 1672 func memclrNoHeapPointersChunked(size uintptr, x unsafe.Pointer) { 1673 v := uintptr(x) 1674 // got this from benchmarking. 128k is too small, 512k is too large. 1675 const chunkBytes = 256 * 1024 1676 vsize := v + size 1677 for voff := v; voff < vsize; voff = voff + chunkBytes { 1678 if getg().preempt { 1679 // may hold locks, e.g., profiling 1680 goschedguarded() 1681 } 1682 // clear min(avail, lump) bytes 1683 n := vsize - voff 1684 if n > chunkBytes { 1685 n = chunkBytes 1686 } 1687 memclrNoHeapPointers(unsafe.Pointer(voff), n) 1688 } 1689 } 1690 1691 // implementation of new builtin 1692 // compiler (both frontend and SSA backend) knows the signature 1693 // of this function. 1694 func newobject(typ *_type) unsafe.Pointer { 1695 return mallocgc(typ.Size_, typ, true) 1696 } 1697 1698 //go:linkname maps_newobject internal/runtime/maps.newobject 1699 func maps_newobject(typ *_type) unsafe.Pointer { 1700 return newobject(typ) 1701 } 1702 1703 // reflect_unsafe_New is meant for package reflect, 1704 // but widely used packages access it using linkname. 1705 // Notable members of the hall of shame include: 1706 // - gitee.com/quant1x/gox 1707 // - github.com/goccy/json 1708 // - github.com/modern-go/reflect2 1709 // - github.com/v2pro/plz 1710 // 1711 // Do not remove or change the type signature. 1712 // See go.dev/issue/67401. 1713 // 1714 //go:linkname reflect_unsafe_New reflect.unsafe_New 1715 func reflect_unsafe_New(typ *_type) unsafe.Pointer { 1716 return mallocgc(typ.Size_, typ, true) 1717 } 1718 1719 //go:linkname reflectlite_unsafe_New internal/reflectlite.unsafe_New 1720 func reflectlite_unsafe_New(typ *_type) unsafe.Pointer { 1721 return mallocgc(typ.Size_, typ, true) 1722 } 1723 1724 // newarray allocates an array of n elements of type typ. 1725 // 1726 // newarray should be an internal detail, 1727 // but widely used packages access it using linkname. 1728 // Notable members of the hall of shame include: 1729 // - github.com/RomiChan/protobuf 1730 // - github.com/segmentio/encoding 1731 // - github.com/ugorji/go/codec 1732 // 1733 // Do not remove or change the type signature. 1734 // See go.dev/issue/67401. 1735 // 1736 //go:linkname newarray 1737 func newarray(typ *_type, n int) unsafe.Pointer { 1738 if n == 1 { 1739 return mallocgc(typ.Size_, typ, true) 1740 } 1741 mem, overflow := math.MulUintptr(typ.Size_, uintptr(n)) 1742 if overflow || mem > maxAlloc || n < 0 { 1743 panic(plainError("runtime: allocation size out of range")) 1744 } 1745 return mallocgc(mem, typ, true) 1746 } 1747 1748 // reflect_unsafe_NewArray is meant for package reflect, 1749 // but widely used packages access it using linkname. 1750 // Notable members of the hall of shame include: 1751 // - gitee.com/quant1x/gox 1752 // - github.com/bytedance/sonic 1753 // - github.com/goccy/json 1754 // - github.com/modern-go/reflect2 1755 // - github.com/segmentio/encoding 1756 // - github.com/segmentio/kafka-go 1757 // - github.com/v2pro/plz 1758 // 1759 // Do not remove or change the type signature. 1760 // See go.dev/issue/67401. 1761 // 1762 //go:linkname reflect_unsafe_NewArray reflect.unsafe_NewArray 1763 func reflect_unsafe_NewArray(typ *_type, n int) unsafe.Pointer { 1764 return newarray(typ, n) 1765 } 1766 1767 //go:linkname maps_newarray internal/runtime/maps.newarray 1768 func maps_newarray(typ *_type, n int) unsafe.Pointer { 1769 return newarray(typ, n) 1770 } 1771 1772 // profilealloc resets the current mcache's nextSample counter and 1773 // records a memory profile sample. 1774 // 1775 // The caller must be non-preemptible and have a P. 1776 func profilealloc(mp *m, x unsafe.Pointer, size uintptr) { 1777 c := getMCache(mp) 1778 if c == nil { 1779 throw("profilealloc called without a P or outside bootstrapping") 1780 } 1781 c.memProfRate = MemProfileRate 1782 c.nextSample = nextSample() 1783 mProf_Malloc(mp, x, size) 1784 } 1785 1786 // nextSample returns the next sampling point for heap profiling. The goal is 1787 // to sample allocations on average every MemProfileRate bytes, but with a 1788 // completely random distribution over the allocation timeline; this 1789 // corresponds to a Poisson process with parameter MemProfileRate. In Poisson 1790 // processes, the distance between two samples follows the exponential 1791 // distribution (exp(MemProfileRate)), so the best return value is a random 1792 // number taken from an exponential distribution whose mean is MemProfileRate. 1793 func nextSample() int64 { 1794 if MemProfileRate == 0 { 1795 // Basically never sample. 1796 return math.MaxInt64 1797 } 1798 if MemProfileRate == 1 { 1799 // Sample immediately. 1800 return 0 1801 } 1802 return int64(fastexprand(MemProfileRate)) 1803 } 1804 1805 // fastexprand returns a random number from an exponential distribution with 1806 // the specified mean. 1807 func fastexprand(mean int) int32 { 1808 // Avoid overflow. Maximum possible step is 1809 // -ln(1/(1<<randomBitCount)) * mean, approximately 20 * mean. 1810 switch { 1811 case mean > 0x7000000: 1812 mean = 0x7000000 1813 case mean == 0: 1814 return 0 1815 } 1816 1817 // Take a random sample of the exponential distribution exp(-mean*x). 1818 // The probability distribution function is mean*exp(-mean*x), so the CDF is 1819 // p = 1 - exp(-mean*x), so 1820 // q = 1 - p == exp(-mean*x) 1821 // log_e(q) = -mean*x 1822 // -log_e(q)/mean = x 1823 // x = -log_e(q) * mean 1824 // x = log_2(q) * (-log_e(2)) * mean ; Using log_2 for efficiency 1825 const randomBitCount = 26 1826 q := cheaprandn(1<<randomBitCount) + 1 1827 qlog := fastlog2(float64(q)) - randomBitCount 1828 if qlog > 0 { 1829 qlog = 0 1830 } 1831 const minusLog2 = -0.6931471805599453 // -ln(2) 1832 return int32(qlog*(minusLog2*float64(mean))) + 1 1833 } 1834 1835 type persistentAlloc struct { 1836 base *notInHeap 1837 off uintptr 1838 } 1839 1840 var globalAlloc struct { 1841 mutex 1842 persistentAlloc 1843 } 1844 1845 // persistentChunkSize is the number of bytes we allocate when we grow 1846 // a persistentAlloc. 1847 const persistentChunkSize = 256 << 10 1848 1849 // persistentChunks is a list of all the persistent chunks we have 1850 // allocated. The list is maintained through the first word in the 1851 // persistent chunk. This is updated atomically. 1852 var persistentChunks *notInHeap 1853 1854 // Wrapper around sysAlloc that can allocate small chunks. 1855 // There is no associated free operation. 1856 // Intended for things like function/type/debug-related persistent data. 1857 // If align is 0, uses default align (currently 8). 1858 // The returned memory will be zeroed. 1859 // sysStat must be non-nil. 1860 // 1861 // Consider marking persistentalloc'd types not in heap by embedding 1862 // internal/runtime/sys.NotInHeap. 1863 // 1864 // nosplit because it is used during write barriers and must not be preempted. 1865 // 1866 //go:nosplit 1867 func persistentalloc(size, align uintptr, sysStat *sysMemStat) unsafe.Pointer { 1868 var p *notInHeap 1869 systemstack(func() { 1870 p = persistentalloc1(size, align, sysStat) 1871 }) 1872 return unsafe.Pointer(p) 1873 } 1874 1875 // Must run on system stack because stack growth can (re)invoke it. 1876 // See issue 9174. 1877 // 1878 //go:systemstack 1879 func persistentalloc1(size, align uintptr, sysStat *sysMemStat) *notInHeap { 1880 const ( 1881 maxBlock = 64 << 10 // VM reservation granularity is 64K on windows 1882 ) 1883 1884 if size == 0 { 1885 throw("persistentalloc: size == 0") 1886 } 1887 if align != 0 { 1888 if align&(align-1) != 0 { 1889 throw("persistentalloc: align is not a power of 2") 1890 } 1891 if align > pageSize { 1892 throw("persistentalloc: align is too large") 1893 } 1894 } else { 1895 align = 8 1896 } 1897 1898 if size >= maxBlock { 1899 return (*notInHeap)(sysAlloc(size, sysStat, "immortal metadata")) 1900 } 1901 1902 mp := acquirem() 1903 var persistent *persistentAlloc 1904 if mp != nil && mp.p != 0 { 1905 persistent = &mp.p.ptr().palloc 1906 } else { 1907 lock(&globalAlloc.mutex) 1908 persistent = &globalAlloc.persistentAlloc 1909 } 1910 persistent.off = alignUp(persistent.off, align) 1911 if persistent.off+size > persistentChunkSize || persistent.base == nil { 1912 persistent.base = (*notInHeap)(sysAlloc(persistentChunkSize, &memstats.other_sys, "immortal metadata")) 1913 if persistent.base == nil { 1914 if persistent == &globalAlloc.persistentAlloc { 1915 unlock(&globalAlloc.mutex) 1916 } 1917 throw("runtime: cannot allocate memory") 1918 } 1919 1920 // Add the new chunk to the persistentChunks list. 1921 for { 1922 chunks := uintptr(unsafe.Pointer(persistentChunks)) 1923 *(*uintptr)(unsafe.Pointer(persistent.base)) = chunks 1924 if atomic.Casuintptr((*uintptr)(unsafe.Pointer(&persistentChunks)), chunks, uintptr(unsafe.Pointer(persistent.base))) { 1925 break 1926 } 1927 } 1928 persistent.off = alignUp(goarch.PtrSize, align) 1929 } 1930 p := persistent.base.add(persistent.off) 1931 persistent.off += size 1932 releasem(mp) 1933 if persistent == &globalAlloc.persistentAlloc { 1934 unlock(&globalAlloc.mutex) 1935 } 1936 1937 if sysStat != &memstats.other_sys { 1938 sysStat.add(int64(size)) 1939 memstats.other_sys.add(-int64(size)) 1940 } 1941 return p 1942 } 1943 1944 // inPersistentAlloc reports whether p points to memory allocated by 1945 // persistentalloc. This must be nosplit because it is called by the 1946 // cgo checker code, which is called by the write barrier code. 1947 // 1948 //go:nosplit 1949 func inPersistentAlloc(p uintptr) bool { 1950 chunk := atomic.Loaduintptr((*uintptr)(unsafe.Pointer(&persistentChunks))) 1951 for chunk != 0 { 1952 if p >= chunk && p < chunk+persistentChunkSize { 1953 return true 1954 } 1955 chunk = *(*uintptr)(unsafe.Pointer(chunk)) 1956 } 1957 return false 1958 } 1959 1960 // linearAlloc is a simple linear allocator that pre-reserves a region 1961 // of memory and then optionally maps that region into the Ready state 1962 // as needed. 1963 // 1964 // The caller is responsible for locking. 1965 type linearAlloc struct { 1966 next uintptr // next free byte 1967 mapped uintptr // one byte past end of mapped space 1968 end uintptr // end of reserved space 1969 1970 mapMemory bool // transition memory from Reserved to Ready if true 1971 } 1972 1973 func (l *linearAlloc) init(base, size uintptr, mapMemory bool) { 1974 if base+size < base { 1975 // Chop off the last byte. The runtime isn't prepared 1976 // to deal with situations where the bounds could overflow. 1977 // Leave that memory reserved, though, so we don't map it 1978 // later. 1979 size -= 1 1980 } 1981 l.next, l.mapped = base, base 1982 l.end = base + size 1983 l.mapMemory = mapMemory 1984 } 1985 1986 func (l *linearAlloc) alloc(size, align uintptr, sysStat *sysMemStat, vmaName string) unsafe.Pointer { 1987 p := alignUp(l.next, align) 1988 if p+size > l.end { 1989 return nil 1990 } 1991 l.next = p + size 1992 if pEnd := alignUp(l.next-1, physPageSize); pEnd > l.mapped { 1993 if l.mapMemory { 1994 // Transition from Reserved to Prepared to Ready. 1995 n := pEnd - l.mapped 1996 sysMap(unsafe.Pointer(l.mapped), n, sysStat, vmaName) 1997 sysUsed(unsafe.Pointer(l.mapped), n, n) 1998 } 1999 l.mapped = pEnd 2000 } 2001 return unsafe.Pointer(p) 2002 } 2003 2004 // notInHeap is off-heap memory allocated by a lower-level allocator 2005 // like sysAlloc or persistentAlloc. 2006 // 2007 // In general, it's better to use real types which embed 2008 // internal/runtime/sys.NotInHeap, but this serves as a generic type 2009 // for situations where that isn't possible (like in the allocators). 2010 // 2011 // TODO: Use this as the return type of sysAlloc, persistentAlloc, etc? 2012 type notInHeap struct{ _ sys.NotInHeap } 2013 2014 func (p *notInHeap) add(bytes uintptr) *notInHeap { 2015 return (*notInHeap)(unsafe.Pointer(uintptr(unsafe.Pointer(p)) + bytes)) 2016 } 2017 2018 // redZoneSize computes the size of the redzone for a given allocation. 2019 // Refer to the implementation of the compiler-rt. 2020 func redZoneSize(userSize uintptr) uintptr { 2021 switch { 2022 case userSize <= (64 - 16): 2023 return 16 << 0 2024 case userSize <= (128 - 32): 2025 return 16 << 1 2026 case userSize <= (512 - 64): 2027 return 16 << 2 2028 case userSize <= (4096 - 128): 2029 return 16 << 3 2030 case userSize <= (1<<14)-256: 2031 return 16 << 4 2032 case userSize <= (1<<15)-512: 2033 return 16 << 5 2034 case userSize <= (1<<16)-1024: 2035 return 16 << 6 2036 default: 2037 return 16 << 7 2038 } 2039 } 2040