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.
7 // This was originally based on tcmalloc, but has diverged quite a bit.
8 // http://goog-perftools.sourceforge.net/doc/tcmalloc.html
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.
17 // The allocator's data structures are:
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 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.
27 // Allocating a small object proceeds up a hierarchy of caches:
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.
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
41 // 3. If the mcentral's mspan list is empty, obtain a run
42 // of pages from the mheap to use for the mspan.
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.
49 // Sweeping an mspan and freeing objects on it proceeds up a similar
52 // 1. If the mspan is being swept in response to allocation, it
53 // is returned to the mcache to satisfy the allocation.
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
59 // 3. Otherwise, if all objects in the mspan are free, the mspan
60 // is now "idle", so it is returned to the mheap and no longer
62 // This may coalesce it with adjacent idle mspans.
64 // 4. If an mspan remains idle for long enough, return its pages
65 // to the operating system.
67 // Allocating and freeing a large object uses the mheap
68 // directly, bypassing the mcache and mcentral.
70 // Free object slots in an mspan are zeroed only if mspan.needzero is
71 // false. If needzero is true, objects are zeroed as they are
72 // allocated. There are various benefits to delaying zeroing this way:
74 // 1. Stack frame allocation can avoid zeroing altogether.
76 // 2. It exhibits better temporal locality, since the program is
77 // probably about to write to the memory.
79 // 3. We don't zero pages that never get reused.
84 "runtime/internal/sys"
88 // C function to get the end of the program's memory.
91 // For gccgo, use go:linkname to rename compiler-called functions to
92 // themselves, so that the compiler will export them.
94 //go:linkname newobject runtime.newobject
96 // Functions called by C code.
97 //go:linkname mallocgc runtime.mallocgc
102 maxTinySize
= _TinySize
103 tinySizeClass
= _TinySizeClass
104 maxSmallSize
= _MaxSmallSize
106 pageShift
= _PageShift
109 // By construction, single page spans of the smallest object class
110 // have the most objects per span.
111 maxObjsPerSpan
= pageSize
/ 8
113 mSpanInUse
= _MSpanInUse
115 concurrentSweep
= _ConcurrentSweep
117 _PageSize
= 1 << _PageShift
118 _PageMask
= _PageSize
- 1
120 // _64bit = 1 on 64-bit systems, 0 on 32-bit systems
121 _64bit
= 1 << (^uintptr(0) >> 63) / 2
123 // Tiny allocator parameters, see "Tiny allocator" comment in malloc.go.
127 _FixAllocChunk
= 16 << 10 // Chunk size for FixAlloc
128 _MaxMHeapList
= 1 << (20 - _PageShift
) // Maximum page length for fixed-size list in MHeap.
129 _HeapAllocChunk
= 1 << 20 // Chunk size for heap growth
131 // Per-P, per order stack segment cache size.
132 _StackCacheSize
= 32 * 1024
134 // Number of orders that get caching. Order 0 is FixedStack
135 // and each successive order is twice as large.
136 // We want to cache 2KB, 4KB, 8KB, and 16KB stacks. Larger stacks
137 // will be allocated directly.
138 // Since FixedStack is different on different systems, we
139 // must vary NumStackOrders to keep the same maximum cached size.
140 // OS | FixedStack | NumStackOrders
141 // -----------------+------------+---------------
142 // linux/darwin/bsd | 2KB | 4
143 // windows/32 | 4KB | 3
144 // windows/64 | 8KB | 2
146 _NumStackOrders
= 4 - sys
.PtrSize
/4*sys
.GoosWindows
- 1*sys
.GoosPlan9
148 // Number of bits in page to span calculations (4k pages).
149 // On Windows 64-bit we limit the arena to 32GB or 35 bits.
150 // Windows counts memory used by page table into committed memory
151 // of the process, so we can't reserve too much memory.
152 // See https://golang.org/issue/5402 and https://golang.org/issue/5236.
153 // On other 64-bit platforms, we limit the arena to 512GB, or 39 bits.
154 // On 32-bit, we don't bother limiting anything, so we use the full 32-bit address.
155 // The only exception is mips32 which only has access to low 2GB of virtual memory.
156 // On Darwin/arm64, we cannot reserve more than ~5GB of virtual memory,
157 // but as most devices have less than 4GB of physical memory anyway, we
158 // try to be conservative here, and only ask for a 2GB heap.
159 _MHeapMap_TotalBits
= (_64bit
*sys
.GoosWindows
)*35 + (_64bit
*(1-sys
.GoosWindows
)*(1-sys
.GoosDarwin
*sys
.GoarchArm64
))*39 + sys
.GoosDarwin
*sys
.GoarchArm64
*31 + (1-_64bit
)*(32-(sys
.GoarchMips
+sys
.GoarchMipsle
))
160 _MHeapMap_Bits
= _MHeapMap_TotalBits
- _PageShift
162 _MaxMem
= uintptr(1<<_MHeapMap_TotalBits
- 1)
164 // Max number of threads to run garbage collection.
165 // 2, 3, and 4 are all plausible maximums depending
166 // on the hardware details of the machine. The garbage
167 // collector scales well to 32 cpus.
170 _MaxArena32
= 1<<32 - 1
172 // minLegalPointer is the smallest possible legal pointer.
173 // This is the smallest possible architectural page size,
174 // since we assume that the first page is never mapped.
176 // This should agree with minZeroPage in the compiler.
177 minLegalPointer
uintptr = 4096
180 // physPageSize is the size in bytes of the OS's physical pages.
181 // Mapping and unmapping operations must be done at multiples of
184 // This must be set by the OS init code (typically in osinit) before
186 var physPageSize
uintptr
188 // OS-defined helpers:
190 // sysAlloc obtains a large chunk of zeroed memory from the
191 // operating system, typically on the order of a hundred kilobytes
193 // NOTE: sysAlloc returns OS-aligned memory, but the heap allocator
194 // may use larger alignment, so the caller must be careful to realign the
195 // memory obtained by sysAlloc.
197 // SysUnused notifies the operating system that the contents
198 // of the memory region are no longer needed and can be reused
199 // for other purposes.
200 // SysUsed notifies the operating system that the contents
201 // of the memory region are needed again.
203 // SysFree returns it unconditionally; this is only used if
204 // an out-of-memory error has been detected midway through
205 // an allocation. It is okay if SysFree is a no-op.
207 // SysReserve reserves address space without allocating memory.
208 // If the pointer passed to it is non-nil, the caller wants the
209 // reservation there, but SysReserve can still choose another
210 // location if that one is unavailable. On some systems and in some
211 // cases SysReserve will simply check that the address space is
212 // available and not actually reserve it. If SysReserve returns
213 // non-nil, it sets *reserved to true if the address space is
214 // reserved, false if it has merely been checked.
215 // NOTE: SysReserve returns OS-aligned memory, but the heap allocator
216 // may use larger alignment, so the caller must be careful to realign the
217 // memory obtained by sysAlloc.
219 // SysMap maps previously reserved address space for use.
220 // The reserved argument is true if the address space was really
221 // reserved, not merely checked.
223 // SysFault marks a (already sysAlloc'd) region to fault
224 // if accessed. Used only for debugging the runtime.
227 if class_to_size
[_TinySizeClass
] != _TinySize
{
228 throw("bad TinySizeClass")
231 // Not used for gccgo.
234 // Copy class sizes out for statistics table.
235 for i
:= range class_to_size
{
236 memstats
.by_size
[i
].size
= uint32(class_to_size
[i
])
239 // Check physPageSize.
240 if physPageSize
== 0 {
241 // The OS init code failed to fetch the physical page size.
242 throw("failed to get system page size")
244 if physPageSize
< minPhysPageSize
{
245 print("system page size (", physPageSize
, ") is smaller than minimum page size (", minPhysPageSize
, ")\n")
246 throw("bad system page size")
248 if physPageSize
&(physPageSize
-1) != 0 {
249 print("system page size (", physPageSize
, ") must be a power of 2\n")
250 throw("bad system page size")
253 var p
, bitmapSize
, spansSize
, pSize
, limit
uintptr
256 // limit = runtime.memlimit();
257 // See https://golang.org/issue/5049
258 // TODO(rsc): Fix after 1.1.
261 // Set up the allocation arena, a contiguous area of memory where
262 // allocated data will be found. The arena begins with a bitmap large
263 // enough to hold 2 bits per allocated word.
264 if sys
.PtrSize
== 8 && (limit
== 0 || limit
> 1<<30) {
265 // On a 64-bit machine, allocate from a single contiguous reservation.
266 // 512 GB (MaxMem) should be big enough for now.
268 // The code will work with the reservation at any address, but ask
269 // SysReserve to use 0x0000XXc000000000 if possible (XX=00...7f).
270 // Allocating a 512 GB region takes away 39 bits, and the amd64
271 // doesn't let us choose the top 17 bits, so that leaves the 9 bits
272 // in the middle of 0x00c0 for us to choose. Choosing 0x00c0 means
273 // that the valid memory addresses will begin 0x00c0, 0x00c1, ..., 0x00df.
274 // In little-endian, that's c0 00, c1 00, ..., df 00. None of those are valid
275 // UTF-8 sequences, and they are otherwise as far away from
276 // ff (likely a common byte) as possible. If that fails, we try other 0xXXc0
277 // addresses. An earlier attempt to use 0x11f8 caused out of memory errors
278 // on OS X during thread allocations. 0x00c0 causes conflicts with
279 // AddressSanitizer which reserves all memory up to 0x0100.
280 // These choices are both for debuggability and to reduce the
281 // odds of a conservative garbage collector (as is still used in gccgo)
282 // not collecting memory because some non-pointer block of memory
283 // had a bit pattern that matched a memory address.
285 // Actually we reserve 544 GB (because the bitmap ends up being 32 GB)
286 // but it hardly matters: e0 00 is not valid UTF-8 either.
288 // If this fails we fall back to the 32 bit memory mechanism
290 // However, on arm64, we ignore all this advice above and slam the
291 // allocation at 0x40 << 32 because when using 4k pages with 3-level
292 // translation buffers, the user address space is limited to 39 bits
293 // On darwin/arm64, the address space is even smaller.
294 // On AIX, mmap adresses range start at 0x07000000_00000000 for 64 bits
296 arenaSize
:= round(_MaxMem
, _PageSize
)
297 bitmapSize
= arenaSize
/ (sys
.PtrSize
* 8 / 2)
298 spansSize
= arenaSize
/ _PageSize
* sys
.PtrSize
299 spansSize
= round(spansSize
, _PageSize
)
300 for i
:= 0; i
<= 0x7f; i
++ {
302 case GOARCH
== "arm64" && GOOS
== "darwin":
303 p
= uintptr(i
)<<40 | uintptrMask
&(0x0013<<28)
304 case GOARCH
== "arm64":
305 p
= uintptr(i
)<<40 | uintptrMask
&(0x0040<<32)
308 p
= uintptr(i
)<<32 | uintptrMask
&(0x70<<52)
310 p
= uintptr(i
)<<40 | uintptrMask
&(0x00c0<<32)
312 pSize
= bitmapSize
+ spansSize
+ arenaSize
+ _PageSize
313 p
= uintptr(sysReserve(unsafe
.Pointer(p
), pSize
, &reserved
))
314 if p
!= 0 || GOOS
== "aix" { // Useless to loop on AIX, as i is forced to 1
321 // On a 32-bit machine, we can't typically get away
322 // with a giant virtual address space reservation.
323 // Instead we map the memory information bitmap
324 // immediately after the data segment, large enough
325 // to handle the entire 4GB address space (256 MB),
326 // along with a reservation for an initial arena.
327 // When that gets used up, we'll start asking the kernel
328 // for any memory anywhere.
330 // If we fail to allocate, try again with a smaller arena.
331 // This is necessary on Android L where we share a process
332 // with ART, which reserves virtual memory aggressively.
333 // In the worst case, fall back to a 0-sized initial arena,
334 // in the hope that subsequent reservations will succeed.
335 arenaSizes
:= [...]uintptr{
342 for _
, arenaSize
:= range &arenaSizes
{
343 bitmapSize
= (_MaxArena32
+ 1) / (sys
.PtrSize
* 8 / 2)
344 spansSize
= (_MaxArena32
+ 1) / _PageSize
* sys
.PtrSize
345 if limit
> 0 && arenaSize
+bitmapSize
+spansSize
> limit
{
346 bitmapSize
= (limit
/ 9) &^ ((1 << _PageShift
) - 1)
347 arenaSize
= bitmapSize
* 8
348 spansSize
= arenaSize
/ _PageSize
* sys
.PtrSize
350 spansSize
= round(spansSize
, _PageSize
)
352 // SysReserve treats the address we ask for, end, as a hint,
353 // not as an absolute requirement. If we ask for the end
354 // of the data segment but the operating system requires
355 // a little more space before we can start allocating, it will
356 // give out a slightly higher pointer. Except QEMU, which
357 // is buggy, as usual: it won't adjust the pointer upward.
358 // So adjust it upward a little bit ourselves: 1/4 MB to get
359 // away from the running binary image and then round up
361 p
= round(getEnd()+(1<<18), 1<<20)
362 pSize
= bitmapSize
+ spansSize
+ arenaSize
+ _PageSize
363 p
= uintptr(sysReserve(unsafe
.Pointer(p
), pSize
, &reserved
))
369 throw("runtime: cannot reserve arena virtual address space")
373 // PageSize can be larger than OS definition of page size,
374 // so SysReserve can give us a PageSize-unaligned pointer.
375 // To overcome this we ask for PageSize more and round up the pointer.
376 p1
:= round(p
, _PageSize
)
379 mheap_
.bitmap
= p1
+ spansSize
+ bitmapSize
380 if sys
.PtrSize
== 4 {
381 // Set arena_start such that we can accept memory
382 // reservations located anywhere in the 4GB virtual space.
383 mheap_
.arena_start
= 0
385 mheap_
.arena_start
= p1
+ (spansSize
+ bitmapSize
)
387 mheap_
.arena_end
= p
+ pSize
388 mheap_
.arena_used
= p1
+ (spansSize
+ bitmapSize
)
389 mheap_
.arena_reserved
= reserved
391 if mheap_
.arena_start
&(_PageSize
-1) != 0 {
392 println("bad pagesize", hex(p
), hex(p1
), hex(spansSize
), hex(bitmapSize
), hex(_PageSize
), "start", hex(mheap_
.arena_start
))
393 throw("misrounded allocation in mallocinit")
396 // Initialize the rest of the allocator.
397 mheap_
.init(spansStart
, spansSize
)
399 _g_
.m
.mcache
= allocmcache()
402 // sysAlloc allocates the next n bytes from the heap arena. The
403 // returned pointer is always _PageSize aligned and between
404 // h.arena_start and h.arena_end. sysAlloc returns nil on failure.
405 // There is no corresponding free function.
406 func (h
*mheap
) sysAlloc(n
uintptr) unsafe
.Pointer
{
407 if n
> h
.arena_end
-h
.arena_used
{
408 // We are in 32-bit mode, maybe we didn't use all possible address space yet.
409 // Reserve some more space.
410 p_size
:= round(n
+_PageSize
, 256<<20)
411 new_end
:= h
.arena_end
+ p_size
// Careful: can overflow
412 if h
.arena_end
<= new_end
&& new_end
-h
.arena_start
-1 <= _MaxArena32
{
413 // TODO: It would be bad if part of the arena
414 // is reserved and part is not.
416 p
:= uintptr(sysReserve(unsafe
.Pointer(h
.arena_end
), p_size
, &reserved
))
420 // p can be just about anywhere in the address
421 // space, including before arena_end.
422 if p
== h
.arena_end
{
423 h
.arena_end
= new_end
424 h
.arena_reserved
= reserved
425 } else if h
.arena_end
< p
&& p
+p_size
-h
.arena_start
-1 <= _MaxArena32
{
426 // Keep everything page-aligned.
427 // Our pages are bigger than hardware pages.
428 h
.arena_end
= p
+ p_size
429 used
:= p
+ (-p
& (_PageSize
- 1))
433 h
.arena_reserved
= reserved
435 // We got a mapping, but it's not
436 // linear with our current arena, so
439 // TODO: Make it possible to allocate
440 // from this. We can't decrease
441 // arena_used, but we could introduce
442 // a new variable for the current
443 // allocation position.
445 // We haven't added this allocation to
446 // the stats, so subtract it from a
447 // fake stat (but avoid underflow).
448 stat
:= uint64(p_size
)
449 sysFree(unsafe
.Pointer(p
), p_size
, &stat
)
454 if n
<= h
.arena_end
-h
.arena_used
{
455 // Keep taking from our reservation.
457 sysMap(unsafe
.Pointer(p
), n
, h
.arena_reserved
, &memstats
.heap_sys
)
462 racemapshadow(unsafe
.Pointer(p
), n
)
465 if p
&(_PageSize
-1) != 0 {
466 throw("misrounded allocation in MHeap_SysAlloc")
468 return unsafe
.Pointer(p
)
471 // If using 64-bit, our reservation is all we have.
472 if h
.arena_end
-h
.arena_start
> _MaxArena32
{
476 // On 32-bit, once the reservation is gone we can
477 // try to get memory at a location chosen by the OS.
478 p_size
:= round(n
, _PageSize
) + _PageSize
479 p
:= uintptr(sysAlloc(p_size
, &memstats
.heap_sys
))
484 if p
< h
.arena_start || p
+p_size
-h
.arena_start
> _MaxArena32
{
486 if top
-h
.arena_start
-1 > _MaxArena32
{
487 top
= h
.arena_start
+ _MaxArena32
+ 1
489 print("runtime: memory allocated by OS (", hex(p
), ") not in usable range [", hex(h
.arena_start
), ",", hex(top
), ")\n")
490 sysFree(unsafe
.Pointer(p
), p_size
, &memstats
.heap_sys
)
495 p
+= -p
& (_PageSize
- 1)
496 if p
+n
> h
.arena_used
{
500 if p_end
> h
.arena_end
{
504 racemapshadow(unsafe
.Pointer(p
), n
)
508 if p
&(_PageSize
-1) != 0 {
509 throw("misrounded allocation in MHeap_SysAlloc")
511 return unsafe
.Pointer(p
)
514 // base address for all 0-byte allocations
517 // nextFreeFast returns the next free object if one is quickly available.
518 // Otherwise it returns 0.
519 func nextFreeFast(s
*mspan
) gclinkptr
{
520 theBit
:= sys
.Ctz64(s
.allocCache
) // Is there a free object in the allocCache?
522 result
:= s
.freeindex
+ uintptr(theBit
)
523 if result
< s
.nelems
{
524 freeidx
:= result
+ 1
525 if freeidx%64
== 0 && freeidx
!= s
.nelems
{
528 s
.allocCache
>>= (theBit
+ 1)
529 s
.freeindex
= freeidx
530 v
:= gclinkptr(result
*s
.elemsize
+ s
.base())
538 // nextFree returns the next free object from the cached span if one is available.
539 // Otherwise it refills the cache with a span with an available object and
540 // returns that object along with a flag indicating that this was a heavy
541 // weight allocation. If it is a heavy weight allocation the caller must
542 // determine whether a new GC cycle needs to be started or if the GC is active
543 // whether this goroutine needs to assist the GC.
544 func (c
*mcache
) nextFree(sizeclass
uint8) (v gclinkptr
, s
*mspan
, shouldhelpgc
bool) {
545 s
= c
.alloc
[sizeclass
]
547 freeIndex
:= s
.nextFreeIndex()
548 if freeIndex
== s
.nelems
{
550 if uintptr(s
.allocCount
) != s
.nelems
{
551 println("runtime: s.allocCount=", s
.allocCount
, "s.nelems=", s
.nelems
)
552 throw("s.allocCount != s.nelems && freeIndex == s.nelems")
555 c
.refill(int32(sizeclass
))
558 s
= c
.alloc
[sizeclass
]
560 freeIndex
= s
.nextFreeIndex()
563 if freeIndex
>= s
.nelems
{
564 throw("freeIndex is not valid")
567 v
= gclinkptr(freeIndex
*s
.elemsize
+ s
.base())
569 if uintptr(s
.allocCount
) > s
.nelems
{
570 println("s.allocCount=", s
.allocCount
, "s.nelems=", s
.nelems
)
571 throw("s.allocCount > s.nelems")
576 // Allocate an object of size bytes.
577 // Small objects are allocated from the per-P cache's free lists.
578 // Large objects (> 32 kB) are allocated straight from the heap.
579 func mallocgc(size
uintptr, typ
*_type
, needzero
bool) unsafe
.Pointer
{
580 if gcphase
== _GCmarktermination
{
581 throw("mallocgc called with gcphase == _GCmarktermination")
585 return unsafe
.Pointer(&zerobase
)
591 align
= uintptr(typ
.align
)
593 return persistentalloc(size
, align
, &memstats
.other_sys
)
596 // When using gccgo, when a cgo or SWIG function has an
597 // interface return type and the function returns a
598 // non-pointer, memory allocation occurs after syscall.Cgocall
599 // but before syscall.CgocallDone. Treat this allocation as a
602 if gomcache() == nil && getg().m
.ncgo
> 0 {
607 // assistG is the G to charge for this allocation, or nil if
608 // GC is not currently active.
610 if gcBlackenEnabled
!= 0 {
611 // Charge the current user G for this allocation.
613 if assistG
.m
.curg
!= nil {
614 assistG
= assistG
.m
.curg
616 // Charge the allocation against the G. We'll account
617 // for internal fragmentation at the end of mallocgc.
618 assistG
.gcAssistBytes
-= int64(size
)
620 if assistG
.gcAssistBytes
< 0 {
621 // This G is in debt. Assist the GC to correct
622 // this before allocating. This must happen
623 // before disabling preemption.
624 gcAssistAlloc(assistG
)
628 // Set mp.mallocing to keep from being preempted by GC.
630 if mp
.mallocing
!= 0 {
631 throw("malloc deadlock")
633 if mp
.gsignal
== getg() {
634 throw("malloc during signal")
638 shouldhelpgc
:= false
642 noscan
:= typ
== nil || typ
.kind
&kindNoPointers
!= 0
643 if size
<= maxSmallSize
{
644 if noscan
&& size
< maxTinySize
{
647 // Tiny allocator combines several tiny allocation requests
648 // into a single memory block. The resulting memory block
649 // is freed when all subobjects are unreachable. The subobjects
650 // must be noscan (don't have pointers), this ensures that
651 // the amount of potentially wasted memory is bounded.
653 // Size of the memory block used for combining (maxTinySize) is tunable.
654 // Current setting is 16 bytes, which relates to 2x worst case memory
655 // wastage (when all but one subobjects are unreachable).
656 // 8 bytes would result in no wastage at all, but provides less
657 // opportunities for combining.
658 // 32 bytes provides more opportunities for combining,
659 // but can lead to 4x worst case wastage.
660 // The best case winning is 8x regardless of block size.
662 // Objects obtained from tiny allocator must not be freed explicitly.
663 // So when an object will be freed explicitly, we ensure that
664 // its size >= maxTinySize.
666 // SetFinalizer has a special case for objects potentially coming
667 // from tiny allocator, it such case it allows to set finalizers
668 // for an inner byte of a memory block.
670 // The main targets of tiny allocator are small strings and
671 // standalone escaping variables. On a json benchmark
672 // the allocator reduces number of allocations by ~12% and
673 // reduces heap size by ~20%.
675 // Align tiny pointer for required (conservative) alignment.
678 } else if size
&3 == 0 {
680 } else if size
&1 == 0 {
683 if off
+size
<= maxTinySize
&& c
.tiny
!= 0 {
684 // The object fits into existing tiny block.
685 x
= unsafe
.Pointer(c
.tiny
+ off
)
686 c
.tinyoffset
= off
+ size
695 // Allocate a new maxTinySize block.
696 span
:= c
.alloc
[tinySizeClass
]
697 v
:= nextFreeFast(span
)
699 v
, _
, shouldhelpgc
= c
.nextFree(tinySizeClass
)
701 x
= unsafe
.Pointer(v
)
702 (*[2]uint64)(x
)[0] = 0
703 (*[2]uint64)(x
)[1] = 0
704 // See if we need to replace the existing tiny block with the new one
705 // based on amount of remaining free space.
706 if size
< c
.tinyoffset || c
.tiny
== 0 {
713 if size
<= smallSizeMax
-8 {
714 sizeclass
= size_to_class8
[(size
+smallSizeDiv
-1)/smallSizeDiv
]
716 sizeclass
= size_to_class128
[(size
-smallSizeMax
+largeSizeDiv
-1)/largeSizeDiv
]
718 size
= uintptr(class_to_size
[sizeclass
])
719 span
:= c
.alloc
[sizeclass
]
720 v
:= nextFreeFast(span
)
722 v
, span
, shouldhelpgc
= c
.nextFree(sizeclass
)
724 x
= unsafe
.Pointer(v
)
725 if needzero
&& span
.needzero
!= 0 {
726 memclrNoHeapPointers(unsafe
.Pointer(v
), size
)
733 s
= largeAlloc(size
, needzero
)
737 x
= unsafe
.Pointer(s
.base())
743 heapBitsSetTypeNoScan(uintptr(x
))
745 heapBitsSetType(uintptr(x
), size
, dataSize
, typ
)
746 if dataSize
> typ
.size
{
747 // Array allocation. If there are any
748 // pointers, GC has to scan to the last
750 if typ
.ptrdata
!= 0 {
751 scanSize
= dataSize
- typ
.size
+ typ
.ptrdata
754 scanSize
= typ
.ptrdata
756 c
.local_scan
+= scanSize
759 // Ensure that the stores above that initialize x to
760 // type-safe memory and set the heap bits occur before
761 // the caller can make x observable to the garbage
762 // collector. Otherwise, on weakly ordered machines,
763 // the garbage collector could follow a pointer to x,
764 // but see uninitialized memory or stale heap bits.
767 // Allocate black during GC.
768 // All slots hold nil so no scanning is needed.
769 // This may be racing with GC so do it atomically if there can be
770 // a race marking the bit.
771 if gcphase
!= _GCoff
{
772 gcmarknewobject(uintptr(x
), size
, scanSize
)
786 if debug
.allocfreetrace
!= 0 {
787 tracealloc(x
, size
, typ
)
790 if rate
:= MemProfileRate
; rate
> 0 {
791 if size
< uintptr(rate
) && int32(size
) < c
.next_sample
{
792 c
.next_sample
-= int32(size
)
795 profilealloc(mp
, x
, size
)
801 // Account for internal fragmentation in the assist
802 // debt now that we know it.
803 assistG
.gcAssistBytes
-= int64(size
- dataSize
)
806 if shouldhelpgc
&& gcShouldStart(false) {
807 gcStart(gcBackgroundMode
, false)
821 func largeAlloc(size
uintptr, needzero
bool) *mspan
{
822 // print("largeAlloc size=", size, "\n")
824 if size
+_PageSize
< size
{
825 throw("out of memory")
827 npages
:= size
>> _PageShift
828 if size
&_PageMask
!= 0 {
832 // Deduct credit for this span allocation and sweep if
833 // necessary. mHeap_Alloc will also sweep npages, so this only
834 // pays the debt down to npage pages.
835 deductSweepCredit(npages
*_PageSize
, npages
)
837 s
:= mheap_
.alloc(npages
, 0, true, needzero
)
839 throw("out of memory")
841 s
.limit
= s
.base() + size
842 heapBitsForSpan(s
.base()).initSpan(s
)
846 // implementation of new builtin
847 // compiler (both frontend and SSA backend) knows the signature
849 func newobject(typ
*_type
) unsafe
.Pointer
{
850 return mallocgc(typ
.size
, typ
, true)
853 //go:linkname reflect_unsafe_New reflect.unsafe_New
854 func reflect_unsafe_New(typ
*_type
) unsafe
.Pointer
{
855 return newobject(typ
)
858 // newarray allocates an array of n elements of type typ.
859 func newarray(typ
*_type
, n
int) unsafe
.Pointer
{
860 if n
< 0 ||
uintptr(n
) > maxSliceCap(typ
.size
) {
861 panic(plainError("runtime: allocation size out of range"))
863 return mallocgc(typ
.size
*uintptr(n
), typ
, true)
866 //go:linkname reflect_unsafe_NewArray reflect.unsafe_NewArray
867 func reflect_unsafe_NewArray(typ
*_type
, n
int) unsafe
.Pointer
{
868 return newarray(typ
, n
)
871 func profilealloc(mp
*m
, x unsafe
.Pointer
, size
uintptr) {
872 mp
.mcache
.next_sample
= nextSample()
873 mProf_Malloc(x
, size
)
876 // nextSample returns the next sampling point for heap profiling.
877 // It produces a random variable with a geometric distribution and
878 // mean MemProfileRate. This is done by generating a uniformly
879 // distributed random number and applying the cumulative distribution
880 // function for an exponential.
881 func nextSample() int32 {
883 // Plan 9 doesn't support floating point in note handler.
884 if g
:= getg(); g
== g
.m
.gsignal
{
885 return nextSampleNoFP()
889 period
:= MemProfileRate
891 // make nextSample not overflow. Maximum possible step is
892 // -ln(1/(1<<kRandomBitCount)) * period, approximately 20 * period.
894 case period
> 0x7000000:
900 // Let m be the sample rate,
901 // the probability distribution function is m*exp(-mx), so the CDF is
902 // p = 1 - exp(-mx), so
903 // q = 1 - p == exp(-mx)
906 // x = -log_e(q) * period
907 // x = log_2(q) * (-log_e(2)) * period ; Using log_2 for efficiency
908 const randomBitCount
= 26
909 q
:= fastrand()%(1<<randomBitCount
) + 1
910 qlog
:= fastlog2(float64(q
)) - randomBitCount
914 const minusLog2
= -0.6931471805599453 // -ln(2)
915 return int32(qlog
*(minusLog2
*float64(period
))) + 1
918 // nextSampleNoFP is similar to nextSample, but uses older,
919 // simpler code to avoid floating point.
920 func nextSampleNoFP() int32 {
921 // Set first allocation sample size.
922 rate
:= MemProfileRate
923 if rate
> 0x3fffffff { // make 2*rate not overflow
927 return int32(int(fastrand()) % (2 * rate
))
932 type persistentAlloc
struct {
937 var globalAlloc
struct {
942 // Wrapper around sysAlloc that can allocate small chunks.
943 // There is no associated free operation.
944 // Intended for things like function/type/debug-related persistent data.
945 // If align is 0, uses default align (currently 8).
946 // The returned memory will be zeroed.
948 // Consider marking persistentalloc'd types go:notinheap.
949 func persistentalloc(size
, align
uintptr, sysStat
*uint64) unsafe
.Pointer
{
952 p
= persistentalloc1(size
, align
, sysStat
)
957 // Must run on system stack because stack growth can (re)invoke it.
960 func persistentalloc1(size
, align
uintptr, sysStat
*uint64) unsafe
.Pointer
{
963 maxBlock
= 64 << 10 // VM reservation granularity is 64K on windows
967 throw("persistentalloc: size == 0")
970 if align
&(align
-1) != 0 {
971 throw("persistentalloc: align is not a power of 2")
973 if align
> _PageSize
{
974 throw("persistentalloc: align is too large")
980 if size
>= maxBlock
{
981 return sysAlloc(size
, sysStat
)
985 var persistent
*persistentAlloc
986 if mp
!= nil && mp
.p
!= 0 {
987 persistent
= &mp
.p
.ptr().palloc
989 lock(&globalAlloc
.mutex
)
990 persistent
= &globalAlloc
.persistentAlloc
992 persistent
.off
= round(persistent
.off
, align
)
993 if persistent
.off
+size
> chunk || persistent
.base
== nil {
994 persistent
.base
= sysAlloc(chunk
, &memstats
.other_sys
)
995 if persistent
.base
== nil {
996 if persistent
== &globalAlloc
.persistentAlloc
{
997 unlock(&globalAlloc
.mutex
)
999 throw("runtime: cannot allocate memory")
1003 p
:= add(persistent
.base
, persistent
.off
)
1004 persistent
.off
+= size
1006 if persistent
== &globalAlloc
.persistentAlloc
{
1007 unlock(&globalAlloc
.mutex
)
1010 if sysStat
!= &memstats
.other_sys
{
1011 mSysStatInc(sysStat
, size
)
1012 mSysStatDec(&memstats
.other_sys
, size
)