[dev.ssa] cmd/compile: better register allocation

[gostls13.git] / src / runtime / malloc.go

// Copyright 2014 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Memory allocator, based on tcmalloc.
// http://goog-perftools.sourceforge.net/doc/tcmalloc.html

// The main allocator works in runs of pages.
// Small allocation sizes (up to and including 32 kB) are
// rounded to one of about 100 size classes, each of which
// has its own free list of objects of exactly that size.
// Any free page of memory can be split into a set of objects
// of one size class, which are then managed using free list
// allocators.
//
// The allocator's data structures are:
//
//      FixAlloc: a free-list allocator for fixed-size objects,
//              used to manage storage used by the allocator.
//      MHeap: the malloc heap, managed at page (4096-byte) granularity.
//      MSpan: a run of pages managed by the MHeap.
//      MCentral: a shared free list for a given size class.
//      MCache: a per-thread (in Go, per-P) cache for small objects.
//      MStats: allocation statistics.
//
// Allocating a small object proceeds up a hierarchy of caches:
//
//      1. Round the size up to one of the small size classes
//         and look in the corresponding MCache free list.
//         If the list is not empty, allocate an object from it.
//         This can all be done without acquiring a lock.
//
//      2. If the MCache free list is empty, replenish it by
//         taking a bunch of objects from the MCentral free list.
//         Moving a bunch amortizes the cost of acquiring the MCentral lock.
//
//      3. If the MCentral free list is empty, replenish it by
//         allocating a run of pages from the MHeap and then
//         chopping that memory into objects of the given size.
//         Allocating many objects amortizes the cost of locking
//         the heap.
//
//      4. If the MHeap is empty or has no page runs large enough,
//         allocate a new group of pages (at least 1MB) from the
//         operating system.  Allocating a large run of pages
//         amortizes the cost of talking to the operating system.
//
// Freeing a small object proceeds up the same hierarchy:
//
//      1. Look up the size class for the object and add it to
//         the MCache free list.
//
//      2. If the MCache free list is too long or the MCache has
//         too much memory, return some to the MCentral free lists.
//
//      3. If all the objects in a given span have returned to
//         the MCentral list, return that span to the page heap.
//
//      4. If the heap has too much memory, return some to the
//         operating system.
//
//      TODO(rsc): Step 4 is not implemented.
//
// Allocating and freeing a large object uses the page heap
// directly, bypassing the MCache and MCentral free lists.
//
// The small objects on the MCache and MCentral free lists
// may or may not be zeroed.  They are zeroed if and only if
// the second word of the object is zero.  A span in the
// page heap is zeroed unless s->needzero is set. When a span
// is allocated to break into small objects, it is zeroed if needed
// and s->needzero is set. There are two main benefits to delaying the
// zeroing this way:
//
//      1. stack frames allocated from the small object lists
//         or the page heap can avoid zeroing altogether.
//      2. the cost of zeroing when reusing a small object is
//         charged to the mutator, not the garbage collector.
//
// This code was written with an eye toward translating to Go
// in the future.  Methods have the form Type_Method(Type *t, ...).

package runtime

import "unsafe"

const (
        debugMalloc = false

        flagNoScan = _FlagNoScan
        flagNoZero = _FlagNoZero

        maxTinySize   = _TinySize
        tinySizeClass = _TinySizeClass
        maxSmallSize  = _MaxSmallSize

        pageShift = _PageShift
        pageSize  = _PageSize
        pageMask  = _PageMask

        mSpanInUse = _MSpanInUse

        concurrentSweep = _ConcurrentSweep
)

const (
        _PageShift = 13
        _PageSize  = 1 << _PageShift
        _PageMask  = _PageSize - 1
)

const (
        // _64bit = 1 on 64-bit systems, 0 on 32-bit systems
        _64bit = 1 << (^uintptr(0) >> 63) / 2

        // Computed constant.  The definition of MaxSmallSize and the
        // algorithm in msize.go produces some number of different allocation
        // size classes.  NumSizeClasses is that number.  It's needed here
        // because there are static arrays of this length; when msize runs its
        // size choosing algorithm it double-checks that NumSizeClasses agrees.
        _NumSizeClasses = 67

        // Tunable constants.
        _MaxSmallSize = 32 << 10

        // Tiny allocator parameters, see "Tiny allocator" comment in malloc.go.
        _TinySize      = 16
        _TinySizeClass = 2

        _FixAllocChunk  = 16 << 10               // Chunk size for FixAlloc
        _MaxMHeapList   = 1 << (20 - _PageShift) // Maximum page length for fixed-size list in MHeap.
        _HeapAllocChunk = 1 << 20                // Chunk size for heap growth

        // Per-P, per order stack segment cache size.
        _StackCacheSize = 32 * 1024

        // Number of orders that get caching.  Order 0 is FixedStack
        // and each successive order is twice as large.
        // We want to cache 2KB, 4KB, 8KB, and 16KB stacks.  Larger stacks
        // will be allocated directly.
        // Since FixedStack is different on different systems, we
        // must vary NumStackOrders to keep the same maximum cached size.
        //   OS               | FixedStack | NumStackOrders
        //   -----------------+------------+---------------
        //   linux/darwin/bsd | 2KB        | 4
        //   windows/32       | 4KB        | 3
        //   windows/64       | 8KB        | 2
        //   plan9            | 4KB        | 3
        _NumStackOrders = 4 - ptrSize/4*goos_windows - 1*goos_plan9

        // Number of bits in page to span calculations (4k pages).
        // On Windows 64-bit we limit the arena to 32GB or 35 bits.
        // Windows counts memory used by page table into committed memory
        // of the process, so we can't reserve too much memory.
        // See https://golang.org/issue/5402 and https://golang.org/issue/5236.
        // On other 64-bit platforms, we limit the arena to 512GB, or 39 bits.
        // On 32-bit, we don't bother limiting anything, so we use the full 32-bit address.
        // On Darwin/arm64, we cannot reserve more than ~5GB of virtual memory,
        // but as most devices have less than 4GB of physical memory anyway, we
        // try to be conservative here, and only ask for a 2GB heap.
        _MHeapMap_TotalBits = (_64bit*goos_windows)*35 + (_64bit*(1-goos_windows)*(1-goos_darwin*goarch_arm64))*39 + goos_darwin*goarch_arm64*31 + (1-_64bit)*32
        _MHeapMap_Bits      = _MHeapMap_TotalBits - _PageShift

        _MaxMem = uintptr(1<<_MHeapMap_TotalBits - 1)

        // Max number of threads to run garbage collection.
        // 2, 3, and 4 are all plausible maximums depending
        // on the hardware details of the machine.  The garbage
        // collector scales well to 32 cpus.
        _MaxGcproc = 32
)

// Page number (address>>pageShift)
type pageID uintptr

const _MaxArena32 = 2 << 30

// OS-defined helpers:
//
// sysAlloc obtains a large chunk of zeroed memory from the
// operating system, typically on the order of a hundred kilobytes
// or a megabyte.
// NOTE: sysAlloc returns OS-aligned memory, but the heap allocator
// may use larger alignment, so the caller must be careful to realign the
// memory obtained by sysAlloc.
//
// SysUnused notifies the operating system that the contents
// of the memory region are no longer needed and can be reused
// for other purposes.
// SysUsed notifies the operating system that the contents
// of the memory region are needed again.
//
// SysFree returns it unconditionally; this is only used if
// an out-of-memory error has been detected midway through
// an allocation.  It is okay if SysFree is a no-op.
//
// SysReserve reserves address space without allocating memory.
// If the pointer passed to it is non-nil, the caller wants the
// reservation there, but SysReserve can still choose another
// location if that one is unavailable.  On some systems and in some
// cases SysReserve will simply check that the address space is
// available and not actually reserve it.  If SysReserve returns
// non-nil, it sets *reserved to true if the address space is
// reserved, false if it has merely been checked.
// NOTE: SysReserve returns OS-aligned memory, but the heap allocator
// may use larger alignment, so the caller must be careful to realign the
// memory obtained by sysAlloc.
//
// SysMap maps previously reserved address space for use.
// The reserved argument is true if the address space was really
// reserved, not merely checked.
//
// SysFault marks a (already sysAlloc'd) region to fault
// if accessed.  Used only for debugging the runtime.

func mallocinit() {
        initSizes()

        if class_to_size[_TinySizeClass] != _TinySize {
                throw("bad TinySizeClass")
        }

        var p, bitmapSize, spansSize, pSize, limit uintptr
        var reserved bool

        // limit = runtime.memlimit();
        // See https://golang.org/issue/5049
        // TODO(rsc): Fix after 1.1.
        limit = 0

        // Set up the allocation arena, a contiguous area of memory where
        // allocated data will be found.  The arena begins with a bitmap large
        // enough to hold 4 bits per allocated word.
        if ptrSize == 8 && (limit == 0 || limit > 1<<30) {
                // On a 64-bit machine, allocate from a single contiguous reservation.
                // 512 GB (MaxMem) should be big enough for now.
                //
                // The code will work with the reservation at any address, but ask
                // SysReserve to use 0x0000XXc000000000 if possible (XX=00...7f).
                // Allocating a 512 GB region takes away 39 bits, and the amd64
                // doesn't let us choose the top 17 bits, so that leaves the 9 bits
                // in the middle of 0x00c0 for us to choose.  Choosing 0x00c0 means
                // that the valid memory addresses will begin 0x00c0, 0x00c1, ..., 0x00df.
                // In little-endian, that's c0 00, c1 00, ..., df 00. None of those are valid
                // UTF-8 sequences, and they are otherwise as far away from
                // ff (likely a common byte) as possible.  If that fails, we try other 0xXXc0
                // addresses.  An earlier attempt to use 0x11f8 caused out of memory errors
                // on OS X during thread allocations.  0x00c0 causes conflicts with
                // AddressSanitizer which reserves all memory up to 0x0100.
                // These choices are both for debuggability and to reduce the
                // odds of a conservative garbage collector (as is still used in gccgo)
                // not collecting memory because some non-pointer block of memory
                // had a bit pattern that matched a memory address.
                //
                // Actually we reserve 544 GB (because the bitmap ends up being 32 GB)
                // but it hardly matters: e0 00 is not valid UTF-8 either.
                //
                // If this fails we fall back to the 32 bit memory mechanism
                //
                // However, on arm64, we ignore all this advice above and slam the
                // allocation at 0x40 << 32 because when using 4k pages with 3-level
                // translation buffers, the user address space is limited to 39 bits
                // On darwin/arm64, the address space is even smaller.
                arenaSize := round(_MaxMem, _PageSize)
                bitmapSize = arenaSize / (ptrSize * 8 / 4)
                spansSize = arenaSize / _PageSize * ptrSize
                spansSize = round(spansSize, _PageSize)
                for i := 0; i <= 0x7f; i++ {
                        switch {
                        case GOARCH == "arm64" && GOOS == "darwin":
                                p = uintptr(i)<<40 | uintptrMask&(0x0013<<28)
                        case GOARCH == "arm64":
                                p = uintptr(i)<<40 | uintptrMask&(0x0040<<32)
                        default:
                                p = uintptr(i)<<40 | uintptrMask&(0x00c0<<32)
                        }
                        pSize = bitmapSize + spansSize + arenaSize + _PageSize
                        p = uintptr(sysReserve(unsafe.Pointer(p), pSize, &reserved))
                        if p != 0 {
                                break
                        }
                }
        }

        if p == 0 {
                // On a 32-bit machine, we can't typically get away
                // with a giant virtual address space reservation.
                // Instead we map the memory information bitmap
                // immediately after the data segment, large enough
                // to handle another 2GB of mappings (256 MB),
                // along with a reservation for an initial arena.
                // When that gets used up, we'll start asking the kernel
                // for any memory anywhere and hope it's in the 2GB
                // following the bitmap (presumably the executable begins
                // near the bottom of memory, so we'll have to use up
                // most of memory before the kernel resorts to giving out
                // memory before the beginning of the text segment).
                //
                // Alternatively we could reserve 512 MB bitmap, enough
                // for 4GB of mappings, and then accept any memory the
                // kernel threw at us, but normally that's a waste of 512 MB
                // of address space, which is probably too much in a 32-bit world.

                // If we fail to allocate, try again with a smaller arena.
                // This is necessary on Android L where we share a process
                // with ART, which reserves virtual memory aggressively.
                arenaSizes := []uintptr{
                        512 << 20,
                        256 << 20,
                        128 << 20,
                }

                for _, arenaSize := range arenaSizes {
                        bitmapSize = _MaxArena32 / (ptrSize * 8 / 4)
                        spansSize = _MaxArena32 / _PageSize * ptrSize
                        if limit > 0 && arenaSize+bitmapSize+spansSize > limit {
                                bitmapSize = (limit / 9) &^ ((1 << _PageShift) - 1)
                                arenaSize = bitmapSize * 8
                                spansSize = arenaSize / _PageSize * ptrSize
                        }
                        spansSize = round(spansSize, _PageSize)

                        // SysReserve treats the address we ask for, end, as a hint,
                        // not as an absolute requirement.  If we ask for the end
                        // of the data segment but the operating system requires
                        // a little more space before we can start allocating, it will
                        // give out a slightly higher pointer.  Except QEMU, which
                        // is buggy, as usual: it won't adjust the pointer upward.
                        // So adjust it upward a little bit ourselves: 1/4 MB to get
                        // away from the running binary image and then round up
                        // to a MB boundary.
                        p = round(firstmoduledata.end+(1<<18), 1<<20)
                        pSize = bitmapSize + spansSize + arenaSize + _PageSize
                        p = uintptr(sysReserve(unsafe.Pointer(p), pSize, &reserved))
                        if p != 0 {
                                break
                        }
                }
                if p == 0 {
                        throw("runtime: cannot reserve arena virtual address space")
                }
        }

        // PageSize can be larger than OS definition of page size,
        // so SysReserve can give us a PageSize-unaligned pointer.
        // To overcome this we ask for PageSize more and round up the pointer.
        p1 := round(p, _PageSize)

        mheap_.spans = (**mspan)(unsafe.Pointer(p1))
        mheap_.bitmap = p1 + spansSize
        mheap_.arena_start = p1 + (spansSize + bitmapSize)
        mheap_.arena_used = mheap_.arena_start
        mheap_.arena_end = p + pSize
        mheap_.arena_reserved = reserved

        if mheap_.arena_start&(_PageSize-1) != 0 {
                println("bad pagesize", hex(p), hex(p1), hex(spansSize), hex(bitmapSize), hex(_PageSize), "start", hex(mheap_.arena_start))
                throw("misrounded allocation in mallocinit")
        }

        // Initialize the rest of the allocator.
        mHeap_Init(&mheap_, spansSize)
        _g_ := getg()
        _g_.m.mcache = allocmcache()
}

// sysReserveHigh reserves space somewhere high in the address space.
// sysReserve doesn't actually reserve the full amount requested on
// 64-bit systems, because of problems with ulimit. Instead it checks
// that it can get the first 64 kB and assumes it can grab the rest as
// needed. This doesn't work well with the "let the kernel pick an address"
// mode, so don't do that. Pick a high address instead.
func sysReserveHigh(n uintptr, reserved *bool) unsafe.Pointer {
        if ptrSize == 4 {
                return sysReserve(nil, n, reserved)
        }

        for i := 0; i <= 0x7f; i++ {
                p := uintptr(i)<<40 | uintptrMask&(0x00c0<<32)
                *reserved = false
                p = uintptr(sysReserve(unsafe.Pointer(p), n, reserved))
                if p != 0 {
                        return unsafe.Pointer(p)
                }
        }

        return sysReserve(nil, n, reserved)
}

func mHeap_SysAlloc(h *mheap, n uintptr) unsafe.Pointer {
        if n > uintptr(h.arena_end)-uintptr(h.arena_used) {
                // We are in 32-bit mode, maybe we didn't use all possible address space yet.
                // Reserve some more space.
                p_size := round(n+_PageSize, 256<<20)
                new_end := h.arena_end + p_size
                if new_end <= h.arena_start+_MaxArena32 {
                        // TODO: It would be bad if part of the arena
                        // is reserved and part is not.
                        var reserved bool
                        p := uintptr(sysReserve(unsafe.Pointer(h.arena_end), p_size, &reserved))
                        if p == 0 {
                                return nil
                        }
                        if p == h.arena_end {
                                h.arena_end = new_end
                                h.arena_reserved = reserved
                        } else if p+p_size <= h.arena_start+_MaxArena32 {
                                // Keep everything page-aligned.
                                // Our pages are bigger than hardware pages.
                                h.arena_end = p + p_size
                                used := p + (-uintptr(p) & (_PageSize - 1))
                                mHeap_MapBits(h, used)
                                mHeap_MapSpans(h, used)
                                h.arena_used = used
                                h.arena_reserved = reserved
                        } else {
                                var stat uint64
                                sysFree(unsafe.Pointer(p), p_size, &stat)
                        }
                }
        }

        if n <= uintptr(h.arena_end)-uintptr(h.arena_used) {
                // Keep taking from our reservation.
                p := h.arena_used
                sysMap(unsafe.Pointer(p), n, h.arena_reserved, &memstats.heap_sys)
                mHeap_MapBits(h, p+n)
                mHeap_MapSpans(h, p+n)
                h.arena_used = p + n
                if raceenabled {
                        racemapshadow(unsafe.Pointer(p), n)
                }

                if uintptr(p)&(_PageSize-1) != 0 {
                        throw("misrounded allocation in MHeap_SysAlloc")
                }
                return unsafe.Pointer(p)
        }

        // If using 64-bit, our reservation is all we have.
        if uintptr(h.arena_end)-uintptr(h.arena_start) >= _MaxArena32 {
                return nil
        }

        // On 32-bit, once the reservation is gone we can
        // try to get memory at a location chosen by the OS
        // and hope that it is in the range we allocated bitmap for.
        p_size := round(n, _PageSize) + _PageSize
        p := uintptr(sysAlloc(p_size, &memstats.heap_sys))
        if p == 0 {
                return nil
        }

        if p < h.arena_start || uintptr(p)+p_size-uintptr(h.arena_start) >= _MaxArena32 {
                print("runtime: memory allocated by OS (", p, ") not in usable range [", hex(h.arena_start), ",", hex(h.arena_start+_MaxArena32), ")\n")
                sysFree(unsafe.Pointer(p), p_size, &memstats.heap_sys)
                return nil
        }

        p_end := p + p_size
        p += -p & (_PageSize - 1)
        if uintptr(p)+n > uintptr(h.arena_used) {
                mHeap_MapBits(h, p+n)
                mHeap_MapSpans(h, p+n)
                h.arena_used = p + n
                if p_end > h.arena_end {
                        h.arena_end = p_end
                }
                if raceenabled {
                        racemapshadow(unsafe.Pointer(p), n)
                }
        }

        if uintptr(p)&(_PageSize-1) != 0 {
                throw("misrounded allocation in MHeap_SysAlloc")
        }
        return unsafe.Pointer(p)
}

// base address for all 0-byte allocations
var zerobase uintptr

const (
        // flags to malloc
        _FlagNoScan = 1 << 0 // GC doesn't have to scan object
        _FlagNoZero = 1 << 1 // don't zero memory
)

// Allocate an object of size bytes.
// Small objects are allocated from the per-P cache's free lists.
// Large objects (> 32 kB) are allocated straight from the heap.
func mallocgc(size uintptr, typ *_type, flags uint32) unsafe.Pointer {
        if gcphase == _GCmarktermination {
                throw("mallocgc called with gcphase == _GCmarktermination")
        }

        if size == 0 {
                return unsafe.Pointer(&zerobase)
        }

        if flags&flagNoScan == 0 && typ == nil {
                throw("malloc missing type")
        }

        if debug.sbrk != 0 {
                align := uintptr(16)
                if typ != nil {
                        align = uintptr(typ.align)
                }
                return persistentalloc(size, align, &memstats.other_sys)
        }

        // assistG is the G to charge for this allocation, or nil if
        // GC is not currently active.
        var assistG *g
        if gcBlackenEnabled != 0 {
                // Charge the current user G for this allocation.
                assistG = getg()
                if assistG.m.curg != nil {
                        assistG = assistG.m.curg
                }
                // Charge the allocation against the G. We'll account
                // for internal fragmentation at the end of mallocgc.
                assistG.gcAssistBytes -= int64(size)

                if assistG.gcAssistBytes < 0 {
                        // This G is in debt. Assist the GC to correct
                        // this before allocating. This must happen
                        // before disabling preemption.
                        gcAssistAlloc(assistG)
                }
        }

        // Set mp.mallocing to keep from being preempted by GC.
        mp := acquirem()
        if mp.mallocing != 0 {
                throw("malloc deadlock")
        }
        if mp.gsignal == getg() {
                throw("malloc during signal")
        }
        mp.mallocing = 1

        shouldhelpgc := false
        dataSize := size
        c := gomcache()
        var s *mspan
        var x unsafe.Pointer
        if size <= maxSmallSize {
                if flags&flagNoScan != 0 && size < maxTinySize {
                        // Tiny allocator.
                        //
                        // Tiny allocator combines several tiny allocation requests
                        // into a single memory block. The resulting memory block
                        // is freed when all subobjects are unreachable. The subobjects
                        // must be FlagNoScan (don't have pointers), this ensures that
                        // the amount of potentially wasted memory is bounded.
                        //
                        // Size of the memory block used for combining (maxTinySize) is tunable.
                        // Current setting is 16 bytes, which relates to 2x worst case memory
                        // wastage (when all but one subobjects are unreachable).
                        // 8 bytes would result in no wastage at all, but provides less
                        // opportunities for combining.
                        // 32 bytes provides more opportunities for combining,
                        // but can lead to 4x worst case wastage.
                        // The best case winning is 8x regardless of block size.
                        //
                        // Objects obtained from tiny allocator must not be freed explicitly.
                        // So when an object will be freed explicitly, we ensure that
                        // its size >= maxTinySize.
                        //
                        // SetFinalizer has a special case for objects potentially coming
                        // from tiny allocator, it such case it allows to set finalizers
                        // for an inner byte of a memory block.
                        //
                        // The main targets of tiny allocator are small strings and
                        // standalone escaping variables. On a json benchmark
                        // the allocator reduces number of allocations by ~12% and
                        // reduces heap size by ~20%.
                        off := c.tinyoffset
                        // Align tiny pointer for required (conservative) alignment.
                        if size&7 == 0 {
                                off = round(off, 8)
                        } else if size&3 == 0 {
                                off = round(off, 4)
                        } else if size&1 == 0 {
                                off = round(off, 2)
                        }
                        if off+size <= maxTinySize && c.tiny != nil {
                                // The object fits into existing tiny block.
                                x = add(c.tiny, off)
                                c.tinyoffset = off + size
                                c.local_tinyallocs++
                                mp.mallocing = 0
                                releasem(mp)
                                return x
                        }
                        // Allocate a new maxTinySize block.
                        s = c.alloc[tinySizeClass]
                        v := s.freelist
                        if v.ptr() == nil {
                                systemstack(func() {
                                        mCache_Refill(c, tinySizeClass)
                                })
                                shouldhelpgc = true
                                s = c.alloc[tinySizeClass]
                                v = s.freelist
                        }
                        s.freelist = v.ptr().next
                        s.ref++
                        // prefetchnta offers best performance, see change list message.
                        prefetchnta(uintptr(v.ptr().next))
                        x = unsafe.Pointer(v)
                        (*[2]uint64)(x)[0] = 0
                        (*[2]uint64)(x)[1] = 0
                        // See if we need to replace the existing tiny block with the new one
                        // based on amount of remaining free space.
                        if size < c.tinyoffset {
                                c.tiny = x
                                c.tinyoffset = size
                        }
                        size = maxTinySize
                } else {
                        var sizeclass int8
                        if size <= 1024-8 {
                                sizeclass = size_to_class8[(size+7)>>3]
                        } else {
                                sizeclass = size_to_class128[(size-1024+127)>>7]
                        }
                        size = uintptr(class_to_size[sizeclass])
                        s = c.alloc[sizeclass]
                        v := s.freelist
                        if v.ptr() == nil {
                                systemstack(func() {
                                        mCache_Refill(c, int32(sizeclass))
                                })
                                shouldhelpgc = true
                                s = c.alloc[sizeclass]
                                v = s.freelist
                        }
                        s.freelist = v.ptr().next
                        s.ref++
                        // prefetchnta offers best performance, see change list message.
                        prefetchnta(uintptr(v.ptr().next))
                        x = unsafe.Pointer(v)
                        if flags&flagNoZero == 0 {
                                v.ptr().next = 0
                                if size > 2*ptrSize && ((*[2]uintptr)(x))[1] != 0 {
                                        memclr(unsafe.Pointer(v), size)
                                }
                        }
                }
                c.local_cachealloc += size
        } else {
                var s *mspan
                shouldhelpgc = true
                systemstack(func() {
                        s = largeAlloc(size, uint32(flags))
                })
                x = unsafe.Pointer(uintptr(s.start << pageShift))
                size = uintptr(s.elemsize)
        }

        if flags&flagNoScan != 0 {
                // All objects are pre-marked as noscan. Nothing to do.
        } else {
                // If allocating a defer+arg block, now that we've picked a malloc size
                // large enough to hold everything, cut the "asked for" size down to
                // just the defer header, so that the GC bitmap will record the arg block
                // as containing nothing at all (as if it were unused space at the end of
                // a malloc block caused by size rounding).
                // The defer arg areas are scanned as part of scanstack.
                if typ == deferType {
                        dataSize = unsafe.Sizeof(_defer{})
                }
                heapBitsSetType(uintptr(x), size, dataSize, typ)
                if dataSize > typ.size {
                        // Array allocation. If there are any
                        // pointers, GC has to scan to the last
                        // element.
                        if typ.ptrdata != 0 {
                                c.local_scan += dataSize - typ.size + typ.ptrdata
                        }
                } else {
                        c.local_scan += typ.ptrdata
                }

                // Ensure that the stores above that initialize x to
                // type-safe memory and set the heap bits occur before
                // the caller can make x observable to the garbage
                // collector. Otherwise, on weakly ordered machines,
                // the garbage collector could follow a pointer to x,
                // but see uninitialized memory or stale heap bits.
                publicationBarrier()
        }

        // GCmarkterminate allocates black
        // All slots hold nil so no scanning is needed.
        // This may be racing with GC so do it atomically if there can be
        // a race marking the bit.
        if gcphase == _GCmarktermination || gcBlackenPromptly {
                systemstack(func() {
                        gcmarknewobject_m(uintptr(x), size)
                })
        }

        if raceenabled {
                racemalloc(x, size)
        }

        mp.mallocing = 0
        releasem(mp)

        if debug.allocfreetrace != 0 {
                tracealloc(x, size, typ)
        }

        if rate := MemProfileRate; rate > 0 {
                if size < uintptr(rate) && int32(size) < c.next_sample {
                        c.next_sample -= int32(size)
                } else {
                        mp := acquirem()
                        profilealloc(mp, x, size)
                        releasem(mp)
                }
        }

        if assistG != nil {
                // Account for internal fragmentation in the assist
                // debt now that we know it.
                assistG.gcAssistBytes -= int64(size - dataSize)
        }

        if shouldhelpgc && shouldtriggergc() {
                startGC(gcBackgroundMode, false)
        } else if shouldhelpgc && bggc.working != 0 && gcBlackenEnabled == 0 {
                // The GC is starting up or shutting down, so we can't
                // assist, but we also can't allocate unabated. Slow
                // down this G's allocation and help the GC stay
                // scheduled by yielding.
                //
                // TODO: This is a workaround. Either help the GC make
                // the transition or block.
                gp := getg()
                if gp != gp.m.g0 && gp.m.locks == 0 && gp.m.preemptoff == "" {
                        Gosched()
                }
        }

        return x
}

func largeAlloc(size uintptr, flag uint32) *mspan {
        // print("largeAlloc size=", size, "\n")

        if size+_PageSize < size {
                throw("out of memory")
        }
        npages := size >> _PageShift
        if size&_PageMask != 0 {
                npages++
        }

        // Deduct credit for this span allocation and sweep if
        // necessary. mHeap_Alloc will also sweep npages, so this only
        // pays the debt down to npage pages.
        deductSweepCredit(npages*_PageSize, npages)

        s := mHeap_Alloc(&mheap_, npages, 0, true, flag&_FlagNoZero == 0)
        if s == nil {
                throw("out of memory")
        }
        s.limit = uintptr(s.start)<<_PageShift + size
        heapBitsForSpan(s.base()).initSpan(s.layout())
        return s
}

// implementation of new builtin
func newobject(typ *_type) unsafe.Pointer {
        flags := uint32(0)
        if typ.kind&kindNoPointers != 0 {
                flags |= flagNoScan
        }
        return mallocgc(uintptr(typ.size), typ, flags)
}

//go:linkname reflect_unsafe_New reflect.unsafe_New
func reflect_unsafe_New(typ *_type) unsafe.Pointer {
        return newobject(typ)
}

// implementation of make builtin for slices
func newarray(typ *_type, n uintptr) unsafe.Pointer {
        flags := uint32(0)
        if typ.kind&kindNoPointers != 0 {
                flags |= flagNoScan
        }
        if int(n) < 0 || (typ.size > 0 && n > _MaxMem/uintptr(typ.size)) {
                panic("runtime: allocation size out of range")
        }
        return mallocgc(uintptr(typ.size)*n, typ, flags)
}

//go:linkname reflect_unsafe_NewArray reflect.unsafe_NewArray
func reflect_unsafe_NewArray(typ *_type, n uintptr) unsafe.Pointer {
        return newarray(typ, n)
}

// rawmem returns a chunk of pointerless memory.  It is
// not zeroed.
func rawmem(size uintptr) unsafe.Pointer {
        return mallocgc(size, nil, flagNoScan|flagNoZero)
}

func profilealloc(mp *m, x unsafe.Pointer, size uintptr) {
        mp.mcache.next_sample = nextSample()
        mProf_Malloc(x, size)
}

// nextSample returns the next sampling point for heap profiling.
// It produces a random variable with a geometric distribution and
// mean MemProfileRate. This is done by generating a uniformly
// distributed random number and applying the cumulative distribution
// function for an exponential.
func nextSample() int32 {
        period := MemProfileRate

        // make nextSample not overflow. Maximum possible step is
        // -ln(1/(1<<kRandomBitCount)) * period, approximately 20 * period.
        switch {
        case period > 0x7000000:
                period = 0x7000000
        case period == 0:
                return 0
        }

        // Let m be the sample rate,
        // the probability distribution function is m*exp(-mx), so the CDF is
        // p = 1 - exp(-mx), so
        // q = 1 - p == exp(-mx)
        // log_e(q) = -mx
        // -log_e(q)/m = x
        // x = -log_e(q) * period
        // x = log_2(q) * (-log_e(2)) * period    ; Using log_2 for efficiency
        const randomBitCount = 26
        q := uint32(fastrand1())%(1<<randomBitCount) + 1
        qlog := fastlog2(float64(q)) - randomBitCount
        if qlog > 0 {
                qlog = 0
        }
        const minusLog2 = -0.6931471805599453 // -ln(2)
        return int32(qlog*(minusLog2*float64(period))) + 1
}

type persistentAlloc struct {
        base unsafe.Pointer
        off  uintptr
}

var globalAlloc struct {
        mutex
        persistentAlloc
}

// Wrapper around sysAlloc that can allocate small chunks.
// There is no associated free operation.
// Intended for things like function/type/debug-related persistent data.
// If align is 0, uses default align (currently 8).
func persistentalloc(size, align uintptr, sysStat *uint64) unsafe.Pointer {
        var p unsafe.Pointer
        systemstack(func() {
                p = persistentalloc1(size, align, sysStat)
        })
        return p
}

// Must run on system stack because stack growth can (re)invoke it.
// See issue 9174.
//go:systemstack
func persistentalloc1(size, align uintptr, sysStat *uint64) unsafe.Pointer {
        const (
                chunk    = 256 << 10
                maxBlock = 64 << 10 // VM reservation granularity is 64K on windows
        )

        if size == 0 {
                throw("persistentalloc: size == 0")
        }
        if align != 0 {
                if align&(align-1) != 0 {
                        throw("persistentalloc: align is not a power of 2")
                }
                if align > _PageSize {
                        throw("persistentalloc: align is too large")
                }
        } else {
                align = 8
        }

        if size >= maxBlock {
                return sysAlloc(size, sysStat)
        }

        mp := acquirem()
        var persistent *persistentAlloc
        if mp != nil && mp.p != 0 {
                persistent = &mp.p.ptr().palloc
        } else {
                lock(&globalAlloc.mutex)
                persistent = &globalAlloc.persistentAlloc
        }
        persistent.off = round(persistent.off, align)
        if persistent.off+size > chunk || persistent.base == nil {
                persistent.base = sysAlloc(chunk, &memstats.other_sys)
                if persistent.base == nil {
                        if persistent == &globalAlloc.persistentAlloc {
                                unlock(&globalAlloc.mutex)
                        }
                        throw("runtime: cannot allocate memory")
                }
                persistent.off = 0
        }
        p := add(persistent.base, persistent.off)
        persistent.off += size
        releasem(mp)
        if persistent == &globalAlloc.persistentAlloc {
                unlock(&globalAlloc.mutex)
        }

        if sysStat != &memstats.other_sys {
                mSysStatInc(sysStat, size)
                mSysStatDec(&memstats.other_sys, size)
        }
        return p
}